Routing
Routing is the method by which network devices direct messages across networks to arrive at the correct destination.
All routers must make routing decisions. They do this by looking up information stored in their routing tables. Every router contains a table of all locally-connected networks and the interfaces that connect to them. These routing tables also contain information about the routes, or paths, that the router uses to reach other remote networks that are not locally attached.
These routes can be statically assigned to the router by an administrator, or they can be dynamically given to the router by another router via a program called a routing protocol.
Every router uses a routing table to make decisions where to send packets. The routing table contains a set of routes, where each route describes which gateway or interface the router needs to use to reach a specified network.
A route has four main components:
Destination value
Mask
Gateway or interface address
Route cost or metric
To direct a message to the correct destination, the router looks at the destination IP address in the packet and then looks for a matching route in the routing table.
The destination values in a routing table refer to destination network addresses.
In order for the router to determine if it has a route to the destination IP address in its table, it must first find out which bits represent the destination network address.
The router looks up the subnet mask assigned to each potential route in the table. The router applies each subnet mask to the destination IP address in the packet. The resulting network address is then compared to the network address of the route in the table.
If a match is found, the packet is forwarded out the correct interface, or to the appropriate gateway.
When the network address matches more than one route in the routing table, the router uses the route that has the most specific, or longest, network address match from its routing table.
Sometimes there is more than one equal cost route to the same destination network. There are routing protocol rules that determine which route the router will use.
If none of the route entries match, the router directs the message to the gateway specified by the default route if it has been configured.
For a Cisco router, the IOS command show ip route displays the routes in the routing table. There are several types of routes that can appear in the routing table:
Directly-Connected Routes
When the router powers up, the configured interfaces are enabled. As they become operational, the router stores the directly attached local network addresses as connected routes in the routing table. For Cisco routers, these routes are identified in the routing table with the prefix C. These routes are automatically updated whenever the interface is reconfigured or shutdown.
Static Routes
A network administrator can manually configure a static route to a specific network. A static route does not change until the administrator manually reconfigures it. These routes are identified in the routing table with the prefix S.
Dynamically-Updated Routes (Dynamic Routes)
Dynamic routes are automatically created and maintained by routing protocols. Routing protocols are implemented in programs that run on routers and that exchange routing information with other routers in the network. Dynamically-updated routes are identified in the routing table with the prefix that corresponds to the type of routing protocol that created the route, for example R is used for the Routing Information Protocol (RIP).
Default Route
The default route is a type of static route which specifies a gateway to use when the routing table does not contain a path to use to reach the destination network. It is common for default routes to point to the next router in the path to the Internet Service Provider. If a subnet has only one router, then that router is automatically the default gateway, because all network traffic to and from that local network has no option but to travel through that router.
Configuring Static Routes
The steps to configure a static route on a Cisco router are as follows:
1. Connect to the router using a console cable.
2. Open a HyperTerminal window to connect with the first router that you want to configure.
3. Enter privileged mode, by typing enable at the Router1> prompt. Note how the > symbol changes to a # to indicate that privilege mode is operative.
Router1>enable
Router1#
4. Enter global configuration mode.
Router1#config terminal
Router1(config)#
5. Use the ip route IOS command to configure the static route, with the following format:
ip route [destination_network] [subnet_mask] [gateway_address]
For example, to enable Router1 to reach a host on network 192.168.16.0, the administrator configures a static route on Router1 with the following IOS command in the global configuration mode:
Router1(config) #ip route 192.168.16.0 255.255.255.0 192.168.15.1
To enable two-way communication with a host on network 192.168.16.0, the administrator also configures a static route on Router 2.
Since static routes are configured manually, network administrators must add and delete static routes to reflect any changes in network topology. On small networks with few possible changes, static routes require very little maintenance. In a large network, the manual maintenance of routing tables could require significant administrative time. For this reason, larger networks generally use dynamic routing rather than static routes.
Routing Protocols
Routes can change very quickly. Problems with cables and hardware failures can make destinations unreachable through the designated interface. Routers need a way to quickly update routes that does not depend on the administrator to make changes.
Routers use routing protocols to dynamically manage information received from their own interfaces and from other routers. Routing protocols can also be configured to manage manually entered routes.
Dynamic routing makes it possible to avoid the time-consuming and exacting process of configuring static routes. Dynamic routing enables routers to react to changes in the network and to adjust their routing tables accordingly, without the intervention of the network administrator.
A dynamic routing protocol learns all available routes, places the best routes into the routing table, and removes routes when they are no longer valid.
The method that a routing protocol uses to determine the best route to a destination network is called a routing algorithm.
There are two main classes of routing algorithms: distance vector and link state. Each type uses a different method for determining the best route to a destination network.
The routing algorithm is very important to dynamic routing. Whenever the topology of a network changes because of reconfiguration or failure, the routing tables in all the routers must also change to reflect an accurate view of the new topology. When all the routers in a network have updated their tables to reflect the new route, the routers are said to have converged.
In order for two routers to exchange routes, they must be using the same routing protocol and therefore the same routing algorithm.
The distance vector routing algorithm passes periodic copies of a routing table from router to router. These regular updates between routers communicate topology changes.
The distance vector algorithm evaluates the route information it receives from other routers in terms of two basic criteria:
Distance – How far away is the network from this router?
Vector – In what direction should the packet be sent to reach this network?
The distance component of a route is expressed in terms of a route cost, or metric, that can represent:
Number of hops
Administrative cost
Bandwidth
Transmission speed
Likelihood of delays
Reliability
The vector or direction component of a route is the address of the next hop along the path to the network named in the route.
An analogy for distance vectors are the highway signs found at intersections. A sign points toward a destination and indicates the distance that must be traveled to reach that destination. Further down the highway, another sign points toward the same destination, but now the distance remaining to that destination is shorter. As long as the distance is shorter, the traffic is on the best path.
Each router that uses distance vector routing communicates its routing information to its neighbors. Neighbor routers share a directly connected network. The interface that leads to each directly connected network has a distance of 0.
Each router receives a routing table from its directly connected neighbor routers. For example, Router R2 receives information from Router R1. Router R2 adds to the metric, in this case hop count, to show that there is now one more hop to get to the destination network. Then Router R2 sends this new routing table to its neighbors, including Router R3. This same step-by-step process occurs in all directions between neighbor routers.
Eventually, each router learns about other more remote networks based on the information that it receives from its neighbors. Each of the network entries in the routing table has an accumulated distance vector to show how far away that network is in a given direction.
As the distance vector discovery process proceeds, routers discover the best path to destination networks based on the information they receive from each neighbor. The best path is the path with the shortest distance or smallest metric.
Routing table updates also occur when the topology changes, for example, when a new network is added or when a router fails, causing a network to be no longer reachable. As with the network discovery process, topology change updates proceed step-by-step by sending copies of routing tables from router to router.
Common Interior Routing Command
RIP
Routing Information Protocol (RIP) is a distance vector routing protocol that is used in thousands of networks throughout the world.
The key characteristics of RIP include the following:
Initially specified in RFC 1058
Is a distance vector routing protocol
Uses hop count as the metric for path selection
Defines a hop count greater than 15 as an unreachable route
Sends routing table contents every 30 seconds, by default
When a router receives a routing update that includes a new or changed route, the router updates its routing table to reflect this new route. At each router, the hop count value is increased by one. The router uses the local network address of the directly connected router which sent the update as the next hop address.
After updating its routing table, the router immediately begins transmitting routing updates in order to inform other network routers of the change. These updates, called triggered updates, are sent independently of the regularly scheduled updates that RIP routers forward.
The RIP protocol is simple, easy to implement, and is available free of cost with most routers. These advantages make RIP a widely used and popular routing protocol.
However, RIP has several disadvantages:
Allows a maximum of 15 hops, so it can only be used for networks that connect no more than 16 routers in series.
Periodically sends complete copies of the entire routing table to directly connected neighbors. In a large network, this can cause a significant amount of network traffic each time there is an update.
Converges slowly on larger networks, when the network changes.
There are currently two versions of RIP available. These are known as RIPv1 and RIPv2. RIPv2 has many advantages over RIPv1 and is usually used unless the equipment cannot support RIPv2. The most significant difference between RIP version 1 and 2 is that RIPv2 can support classless routing, because it includes the subnet mask information in routing updates. RIPv1 does not send subnet mask information in the updates; therefore it must rely on the classfull default subnet masks.
EIGRP
Enhanced Interior Gateway Routing Protocol (EIGRP) is a Cisco proprietary enhanced distance vector routing protocol. EIGRP was developed to address some of the limitations of other distance vector routing protocols such as RIP. These limitations include the use of the hop count metric and the maximum network size of 15 hops.
Instead of hop count, EIGRP uses a number of metrics, including a configured bandwidth value, and the delay encountered when a packet travels a particular route.
The key characteristics of EIGRP are:
Uses a variety of metrics to calculate the cost of a route
Combines the next hop and metric features of distance vector protocols, with additional database and update features
Has a maximum hop count of 224 hops
Unlike RIP, EIGRP does not rely only on the routing table in the router to hold all of the information it needs to operate. EIGRP creates two additional database tables: the neighbor table and the topology table.
The neighbor table stores data about the neighboring routers that are on directly connected local networks. This neighbor table includes information such as the interface IP addresses, interface type and bandwidth.
EIGRP builds the topology table from each of the advertisements of its neighbors. The topology table contains all of the routes advertised by the neighbor routers. EIGRP depends on a routing algorithm called Diffused Update Algorithm (DUAL) to calculate the shortest path to a destination within a network and to install this route into the routing table. The topology table enables a router running EIGRP to find the best alternate path quickly when a network change occurs. If no alternate route exists in the topology table, EIGRP queries its neighbors to find a new path to the destination.
Unlike RIP, which is limited to small simple networks of less than 15 hops, EIGRP is ideal for larger, more complex networks up to 224 hops in size that require fast convergence.
Routers that use the distance vector routing algorithm have little information about distant networks and none about distant routers. The link-state routing algorithm maintains a full database of distant routers and how they interconnect.
Link-state routing uses the following features:
Routing table – List of the known paths and interfaces
Link-state advertisement (LSA) – Small packet of routing information that is sent between routers. LSAs describe the state of the interfaces (links) of a router, as well as other information, such as the IP address of each link
Topological database – Collection of information gathered from all the LSAs received by the router
SPF (Shortest Path First) algorithm – Calculation performed on the database that results in the SPF tree. The SPF tree is a map of the network as seen from the point of view of the router. The information in this tree is used to build the routing table
When LSAs are received from other routers the SPF algorithm analyzes the information in the database to construct the SPF tree. Based on the SPF tree, the SPF algorithm then calculates the shortest paths to other networks. Each time a new LSA packet causes a change to the link-state database; SPF recalculates the best paths and updates the routing table.
OSPF
Open Shortest Path First (OSPF) is a non-proprietary link-state routing protocol described in RFC 2328. The key characteristics of OSPF are:
Uses the SPF algorithm to calculate the lowest cost to a destination
Sends routing updates only when the topology changes; does not send periodic updates of the entire routing table.
Provides fast convergence
Supports VLSM and discontiguous subnets
Provides route authentication
In OSPF enabled networks, routers send link state advertisements to each other when a change occurs, for example:
A new neighbor is added
A link fails
A link is restored
If the network topology changes, for example if a link goes down or a new router is added, those routers affected by the change send update LSAs to the rest of the network. All routers update their topology databases accordingly, regenerate their SPF trees to find new shortest paths to each network, and update their routing tables with the changed routes.
Routing Within Organization
Choosing one routing protocol over another can be difficult even for expert network designers. The following guidelines may help when designing a network.
Small networks with only one gateway to the Internet can probably use static routes. Such a topology rarely needs dynamic routing.
As an organization grows and adds routers to its network topology, RIPv2 can be used. It is easy to configure and in small networks can work well. When a network begins to exceed 15 routers, RIP is no longer a good choice.
For larger networks, EIGRP and OSPF are common, but there is no simple principle that makes it obvious to choose one over the other. Each network has to be considered independently, and the three main criteria in helping settle on a protocol are:
Ease of management – What information does the protocol keep about itself? What show commands are available?
Ease of configuration – How many commands will the average configuration require? Is it possible to configure several routers in your network with the same configuration?
Efficiency – How much bandwidth does the routing protocol take up while in steady state, and how much could it take up, when converging in response to a major network event?
Configure And Verify RIP
RIP is a popular distance vector protocol supported by most routers. It is an appropriate choice for small networks containing multiple routers. Before configuring RIP on a router, think about the networks a router serves, and the interfaces on the router that connect to these networks.
The figure shows three routers. Each router serves a separate private local network, so there are three LANs. The routers are connected by separate networks as well, so there are a total of six networks shown.
With a topology like this, be careful not to assume that R1 links directly to 10.0.0.0/8 and 172.16.17.0/16. R1 will be able to reach those networks once RIP routing is properly configured.
Before configuring RIP, assign an IP address and enable all the physical interfaces that will participate in routing. On serial links, set the clock rate on the master router. After this is done, configure RIP.
For the most basic RIP configuration, there are three commands to remember:
Router(config)#router rip
Router (config-router)#version 2
Router(config-router)#network [network-number]
Enter the router rip command in global configuration mode to enable RIP on the router. Enter the network command from router configuration mode to tell the router which networks will be part of the RIP routing process. The routing process associates specific interfaces with the network-numbers and begins to send and receive RIP updates on these interfaces.
Once a configuration is done, it is a good idea to compare the running configuration with an accurate topology diagram to verify network numbers and interface IP addresses. This is good practice because, sometimes, it is easy to make a simple data entry error.
There are several ways to verify that RIP is functioning properly in the network.
If the configuration is correct, one way to verify that routing is working properly is to ping devices on remote networks. If a ping is successful, it is likely that routing is working.
Run the IP routing verification commands show ip protocols and show ip route at the CLI command prompt.
The show ip protocols command verifies that RIP routing is configured, that the correct interfaces are sending and receiving RIP updates, and that the router is advertising the correct networks.
The show ip route command shows the routing table, which verifies that routes received by RIP neighbors are installed in the routing table.
The debug ip rip command can be used to observe the networks advertised in the routing updates as they are sent and received. Debug commands display router activity in real time. Because debug activity uses router processor resources, debug should be used with care in a production network, because it can affect network operation.
Atonomous System
Internet routing architecture has evolved over the years into a distributed system of interconnected networks. The Internet is now so vast and involves so many networks that it would be impossible for a single organization to manage all the routing information needed to reach every destination around the world.
Instead, the Internet is divided up into collections of networks called Autonomous Systems (AS) that are independently controlled by different organizations and companies.
An AS is a set of networks controlled by a single administrative authority using the same internal routing policy throughout. Each AS is identified by a unique AS number (ASN). ASNs are controlled and registered on the Internet.
The most common example of an AS is the ISP. Most businesses connect to the Internet through an ISP, and so become part of the routing domain of that ISP. The AS is administered by the ISP and therefore not only includes its own network routes, but also manages the routes to all the business and other customer networks that are connected to it.
The same ASN applies to all network devices within the AS routing domain.
ISP A is an AS whose routing domain includes a local business that directly connects to that ISP for Internet access. That business does not have a separate ASN. Instead it uses the AS number of ISP A (ASN 100) in its routing information.
Also shown is a large global business with corporate offices located in Hong Kong and New York. Because they are located in different countries, each office connects to a different local ISP for Internet access. This means that the business is connected to two ISPs. Which AS does it belong to and which ASN does it use?
Because the company communicates through both ISP B and ISP C, this will cause routing confusion in terms of connectivity. Traffic from the internet does not know which AS to use to reach the large global business. To solve the problem, the business registers as an AS in its own right and is assigned an ASN of 400.
Routing Between Atonoous System
Interior Gateway Protocols (IGP) are used to exchange routing information within an autonomous system or individual organization. The purpose of an interior routing protocol is to find the best path through the internal network. IGPs run on the interior routers, that is, the routers inside an organization. Examples of interior gateway protocols are RIP, EIGRP and OSPF.
By contrast, exterior gateway protocols (EGP) are designed to exchange routing information between different Autonomous Systems. Because each AS is managed by a different administration and may use different interior protocols, networks must use a protocol that can communicate between diverse systems. The EGP serves as a translator for ensuring that external routing information gets successful interpreted inside each AS network.
EGP protocols run on the exterior routers, that is, the routers that are located at the border of an AS. Exterior routers are also called border gateways.
Unlike interior routers, which exchange individual routes with each other using IGPs, exterior routers exchange information about how to reach various networks using exterior protocols. Exterior routing protocols seek to find the best path through the Internet as a sequence of Autonomous Systems.
The most common exterior routing protocol on the Internet today is Border Gateway Protocol (BGP). It is estimated that 95% of Autonomous Systems use BGP. The most current version of BGP is version 4 (BGP-4) for which the latest description is provided in RFC 4271.
Routing Accross The Internet
Each AS is responsible for informing other ASs about which networks they can reach through that AS. ASs exchange this reachability information with each other through exterior routing protocols that run on dedicated routers, called border gateways.
Packets are routed across the Internet in several steps:
1. The source host sends a packet destined for a remote host located in another AS.
2. Since the destination IP address of the packet is not a local network, the interior routers keep passing the packet along their default routes, until eventually it arrives at an exterior router at the edge of the local AS.
3. The exterior router maintains a database for all the Autonomous Systems with which it connects. This reachability database tells the router that the path to the destination network passes through several ASs, and that the next hop on the path is through a directly-connected exterior router on a neighboring AS.
4. The exterior router directs the packet to its next hop on the path, which is the exterior router at the neighboring AS.
5. The packet arrives at the neighboring AS, where the exterior router checks its own reachability database and forwards the packet to the next AS on the path.
6. The process is repeated at each AS until the exterior router at the destination AS recognizes the destination IP address of the packet as an internal network in that AS.
7. The final exterior router then directs the packet to the next hop interior router listed in its routing table. From then on, the packet is treated just like any local packet and is directed through interior routing protocols through a series of internal next hops until it arrives at the destination host.
Exterior Routing Protocols And The ISP
Exterior gateway protocols provide many useful features for ISPs. Not only do exterior protocols allow traffic to be routed across the Internet to remote destinations, but they also provide the method by which ISPs can set and enforce policies and local preferences so that the traffic flow through the ISP is efficient and that none of the internal routes are overloaded with transit traffic.
Business customers insist on reliability for their Internet service, and so ISPs must make sure that the Internet connection for those customers is always available. They do this by providing backup routes and routers in case the regular route fails. During normal conditions, the ISP advertises the regular route to other Autonomous Systems. If that regular route fails, then the ISP sends an exterior protocol update message to advertise the backup route instead.
The flow of messages in the Internet is called traffic. Internet traffic can be categorized in one of two ways:
Local Traffic – Traffic carried within an AS that either originated in that same AS, or is intended to be delivered within that AS. This is like local traffic on a street.
Transit Traffic – Traffic that was generated outside that AS and can travel through the internal AS network in route to be delivered to destinations outside the AS. This is like through traffic on a street.
The flow of traffic between Autonomous Systems is carefully controlled. It is important to be able to limit or even prohibit certain types of messages from going to or from an AS, for security reasons or to prevent overloading.
Many Autonomous Systems are not willing to carry transit traffic. Transit traffic can cause routers to overload and fail, if those routers do not have the capacity to handle large amounts of traffic.
Configurte And Verify BGP
When an ISP puts a border router at a customer location, they usually configure it with a default static route to the ISP. Sometimes, though, an ISP may want the router to be included in its autonomous system and to participate in BGP. In these cases, it is necessary to configure the customer premise router with the commands necessary to enable BGP.
The first step in enabling BGP on a router is to configure the AS number. This step is done with the command:
router bgp [AS number]
The next step is to identify the ISP router that is the BGP neighbor with which the Customer Premise Equipment (CPE) router exchanges information. The command to identify the neighbor router is:
neighbor [IP Address] remote-as [AS number]
When an ISP customer has its own registered IP address block, it may want the routes to some of its internal networks to be known on the Internet. To use BGP to advertise an internal route, a network command is needed. The format of the network command is:
network [network address]
Once all of the customer premise equipment is installed and the routing protocols configured, the customer has both local and Internet connectivity. Now the customer is able to fully participate in other services the ISP may offer.
The IP addresses used for BGP are normally registered, routable addresses which identify unique organizations. In very large organizations private addresses may be used in the BGP process as illustrated. On the Internet, BGP should never be used to advertise a private network address.
