Routing is the process of moving traffic across an internetwork from one place to another. Intermediate devices called routers (or gateways) determine the traffic’s path along the way. Routing is often confused with bridging in that both are responsible for making forwarding decisions. However, routing involves Layer 3 (network) decision-making, whereas bridging makes decisions based on Layer 2 (data link) information.
Routers perform two basic functions:
Path determination
Packet switching
Routers use metrics to determine optimal paths in a network. Metrics can range from the bandwidth of a particular path to the relative distance of one router from another. Routers maintain tables called routing tables that aid in the process of path determination.
Routing algorithms populate the routing tables with the information a router needs to make forwarding decisions. The primary piece of information stored in routing tables is the correlation of a destination with the nearest next-hop router. Destination/next-hop associations tell a router that it can reach a particular destination by forwarding the traffic to another router on the way to the packet’s final destination. A router checks the destination address of an incoming packet and then attempts to associate the address with a possible next hop.
Routing tables can store other information that affect how a router makes a forwarding decision. For example, they can store the desirability of one route over another.
Routers communicate with one another by exchanging routing update messages. This way, all routers can synchronize their routing tables and agree on optimal paths. By analyzing the updates from other routers, a router can build a detailed view of the network. The router can also determine if a path changes or a router goes away.
Aside from path determination, routers also provide packet-switching services. This process receives a packet on one interface and forwards the packet out the interface that gets the packet closer to its destination. The router uses the destination address in the packet as the indicator of where the packet is headed.
Upon inspecting the destination address in a packet, the router must determine whether it knows how to reach the destination. It makes this determination by consulting the routing table. If the destination is known, the routing table contains which interface the router should transmit the packet from. If the destination is unknown, the router typically throws the packet away.
The next hop on a packet’s path to its destination is either the actual host the packet is destined to or another router. If the next hop is a router, that router performs the same analysis as the previous one.
As a packet traverses a network, the Layer 3 source and destination addresses remain the same. (They indicate the original sender and intended receiver.) However, the Layer 2 Media Access Control (MAC) addresses change from router to router and from router to destination host. This change is how a router indicates the intended next-hop device.
Routing-protocol algorithms vary in how they determine optimal paths in a network. A routing protocol typically has one or more of the following design goals:
Path optimality—. Ability to select the best path based on certain metrics.
Simplicity and low overhead—. Use of minimal router resources as possible and efficient operation.
Robustness and stability—. Algorithm performing correctly under undue circumstances, such as hardware failure, high load, or incorrect implementation.
Rapid convergence—. Process of all routers agreeing on the optimal paths. The time it takes for all routers to exchange routing updates and agree on routes must be fast. Slow convergence can result in routing loops or network outages.
Flexibility—. Algorithm adapting to network-circumstance changes quickly and accurately. Routing algorithms can adapt to changes in variables such as network bandwidth, router queue size, and network delay.
Routing algorithms determine path optimality according to some or all of the following metrics:
Path length—. Based on assignment of arbitrary cost to each network link.
Reliability—. Dependability of each network link.
Delay—. Time it takes to move a packet from one end of a network link to the other.
Bandwidth—. Available traffic capacity of a link.
Load—. How busy a router is.
Communication cost—. Monetary cost of a network link. Although one link might be slower than another, it might be cheaper to use the slower link.
Six types of routing-algorithm differentiators make each routing protocol unique.
The first type of differentiator is static versus dynamic. Static algorithms are simple in that the network administrator statically defines all routes, and the routes do not change unless the administrator changes them. Static routes make sense in simple network designs with predictable traffic. However, static routes cannot react to network changes automatically. Dynamic algorithms can adapt, and for that reason, they are more suitable for most networks. A router running a dynamic algorithm analyzes incoming routing-update messages and recalculates routes if a network change is detected.
The second type of differentiator is single-path versus multipath. Multipath algorithms support the multiplexing of traffic across multiple simultaneous paths to a destination, whereas single-path algorithms support only a single path. The advantage of multipath is that the algorithm offers substantially better throughput and reliability through load balancing.
The third type of differentiator is flat versus hierarchical. A flat routing structure means all routers communicate with each other. With a hierarchical structure, some routers form a routing backbone, and all messages outside a particular area must go through the backbone. This setup reduces the amount of routing information each router must maintain and exchange and therefore simplifies the routing algorithm on each router.
The fourth type of differentiator is host-intelligent versus router-intelligent. Some routing protocols require that the transmitting hosts be able to determine the route to the destination. The routers simply act as store-and-forward devices. This method is typically called source-routing. Router-intelligent routing assumes the hosts know little about routes, and the routers themselves contain the information necessary to route a packet through the network.
The fifth type of differentiator is intradomain (interior) versus interdomain (exterior). Intradomain algorithms are tuned to most efficiently exchange routes with peer devices in a single routing domain. Interdomain algorithms exchange routes among different routing domains.
The final type of differentiator is link state versus distance vector. Link-state algorithms, also known as shortest path first, flood routing information to all nodes in the network. Each router only sends information concerning the state of its own links. Distance-vector algorithms instead have routers send all or part of their routing tables to only neighboring routers. In other words, link-state protocols send small updates everywhere, whereas distance-vector protocols send large updates only to neighbors.
Open Shortest Path First (OSPF), Enhanced Internet Gateway Routing Protocol (EIGRP), and Routing Information Protocol (RIP) are examples of intradomain IP routing protocols. OSPF is a link-state protocol, whereas RIP is a distance-vector protocol. EIGRP is Cisco’s proprietary distance-vector protocol that incorporates some link-state characteristics. All three protocols (RIP v2 included) provide the ability to summarize routes. Border Gateway Protocol (BGP) and Intermediate System-to-Intermediate System (IS-IS) Protocol, which are examples of interdomain routing protocols, are the primary protocols used on the Internet.
AppleTalk and Novell Internetwork Packet Exchange (IPX), which each implement their own types of Layer 3 routing strategies, are examples of non-IP routing protocols.