Routing Algorithms and Protocols
| Routers choose the optimal or best route based on the available route information. A routing algorithm aids in the collection of route information and the determination of the best path . These algorithms may vary in several aspects. They may differ based on the goals they were designed to achieve within an internetwork. In addition, several types of routing algorithms exist to suit specific internetwork requirements. The metrics used by different routing algorithms also vary. A routing protocol is a standard method of implementing a particular routing algorithm. For the purpose of our discussions, routing protocols mean the routing algorithms or the protocols that implement them. Please do not confuse them with routed protocols; they are very different. Goals of Routing ProtocolsTechnology and internetworks change on a regular basis and because of this change, new needs arise and thus new routing protocols are created. For example, a routing protocol that functioned well in a small internetwork two years ago may certainly experience problems in the large internetworks in use today. Routing protocols have been designed to meet one or more of the following design goals:
FlexibilityA routing protocol has to be flexible. It should be able to adapt quickly to its ever-changing network environment. If a network segment goes down, a flexible routing protocol is able to detect that event and determine the next best path to use while the segment is down. When the network segment becomes available, the routing protocol should also update its route table to reflect that event. Flexible routing protocols can also adapt to changes in network variables , such as network bandwidth and delay. OptimizationThe optimization of a routing protocol gauges its capability to choose the best route correctly. The metrics used by the protocol affect its optimality. For example, one protocol may heavily weight the number of hops as its metric, whereas another may use a combination of a number of hops and network delay. Rapid ConvergenceConvergence occurs when all routers within an internetwork agree on the optimal routes through the internetwork. In other words, an update has been disseminated throughout the internetwork and all routers are working with the same updated table. Network events, such as routes going down or becoming available, cause routers to recalculate optimal paths and distribute update messages about network routes. These messages permeate the entire network until all routes converge and agree on optimal routes. Slow convergence of the routing protocol can cause problems, such as a routing loop. A routing loop occurs when two or more routers have not yet converged and are broadcasting their inaccurate route tables. In addition, they are most likely still switching packets based on their inaccurate route tables. Figure 7.1 illustrates this case. An event has just occurred within the network ”router A lost its path to network 5. While router A is updating its route table, it receives an update from router B that says network 5 is one hop away. Figure 7.1. Illustration of a potential routing loop. Router A increases the counter by 1 and adds this new information to its route tables. In turn , router A broadcasts its updated route table to router C, which updates its table and broadcasts the erroneous information to router D. Router D updates its table and propagates the misinformation to router B. This cycle will continue ad infinitum. If packets traversing the network are destined for network 5, they will loop between router A and router B until the packet becomes too old and is discarded. Figure 7.2 illustrates this situation. Figure 7.2. Illustration of the end result of a routing loop. RobustnessRobust and stable routing protocols perform correctly during unusual and unpredictable network events. High utilization, hardware failures, and incorrect configurations can create significant problems within a network. A robust routing protocol is stable during a variety of network situations. SimplicityThe simplicity of a routing protocol refers to its ability to operate efficiently . Because routing protocols collect and store route information, a protocol is competing for the router's limited physical resources. A routing protocol must perform its functions with minimal administrative overhead. Types of Routing ProtocolsIt is very common in technology reference materials for routing protocols to be categorized by type. The type of routing protocol deployed within an internetwork should be based on the organizational requirements. Types of routing protocols include
Static or DynamicA network administrator configures a static route manually. When defining a static route , the administrator configures the destination network, next hop, and appropriate metrics. The route does not change until the network administrator changes it. Static routes function well in environments where the network is simple and network traffic is predictable. Dynamic routes change and adjust to changes within the internetwork environment automatically. When network changes occur, routers begin to converge by recalculating routes and distributing route updates. The route-update messages permeate the network, which causes more routers to recalculate their routes. This route-update process continues until all routers have converged. Occasionally, static routes augment dynamic routes. In a dynamically routed environment, a router discards a packet if the destination network does not appear in the route table. To avoid this, a static route called a default route can be configured. The default route points to a router that has been specifically configured to receive and process packets that do not have routes listed in the routing tables. Single Path or MultipathWhen calculating the optimal path for a particular network, some routing protocols simply choose the best single path to a destination network. Others allow more than one optimal path if the paths have equal metric values. A multipath protocol enables traffic load-balancing using the multiple paths and offers additional advantages over single-path protocols, such as reliability. Flat or HierarchicalA routing environment is considered flat if all routers are peers to each other. Routers that use a flat routing protocol may communicate with any other router in the network as directly as possible. Like static routing, a flat routing protocol functions well in simple and predictable network environments. Alternatively, a hierarchical routing environment contains several routers that compose a backbone. Most traffic from non-backbone routers usually traverses the backbone routers (or at least travels to the backbone) in order to reach another non-backbone router. Within a hierarchical routing environment, autonomous systems (sometimes referred to as domains or areas ) can be established. Being part of the same autonomous system enables a group of routers to share network topology information with each other, but that same information is not shared outside the group . Although several layers or tiers may exist within the hierarchy, the routers at the highest level comprise the backbone. Cisco, as of publication of this book, is eager to promote a three- tier system. The Cisco system has a backbone, distribution, and access layer. Equipment is being manufactured and marketed according to these layers. The backbone must provide the fastest throughput possible, without making any routing decisions (or as few as possible). Those are high-end expensive and complex routers and switches. Distribution level is where most of the routing is happening. Those are mid-level boxes. Access level is where hosts are connected to the network, and they are mostly 2000 series of switches and routers.
Interior or ExteriorAn interior routing protocol operates within a single autonomous system or domain. These protocols are typically implemented within an organization's private network. Routers that are running interior routing protocols are considered intradomain routers ; they only need to know about other routers within their domain. Conversely, an exterior routing protocol conveys routing information between domains. Exterior routing protocols are in use within the Internet. Interdomain routers need to know how to route traffic between autonomous systems and can protect against errors or problems with one domain affecting another. Distance Vector or Link StateDistance vector protocols require each router to send all or a large part of its route table to its neighboring routers. Link state protocols require each router to send the state of its own interfaces to every router in the internetwork. Distance vector protocols are simple and straightforward, but they converge slowly and consume a significant amount of bandwidth because they have to send updates every set amount of time, and they send entire tables as opposed to the updated entries, which can cause routing loops . Link state protocols converge quickly, but they require more of the router's central processing unit (CPU) and memory resources. Each routed protocol can be implemented in one or more routing protocols. The routing protocols (or standard set of rules) actually enable the router to determine the best path. Common routing protocols include
Table 7.1. Interior Routing Protocols
Routing MetricsRouting protocols use many different metrics to determine the optimal route. These variables can be used individually or in combination with one another to create the metric defined within a given routing protocol. Metrics used in routing protocols include
BandwidthThe available capacity of a network link is known as its bandwidth . Typically, a 10Mbps Ethernet link is preferable to a 56Kbps Frame Relay link. However, if other metrics such as delay are considered, the Ethernet link may not be the optimal path. DelayNetwork delay refers to the amount of time necessary to move a packet through the internetwork from source to destination. Delay is a conglomeration of several other variables, including physical distance between source and destination, bandwidth and congestion of intermediate links, and port queues of intermediate routers. LoadLoad is an indication of how busy a network resource is. CPU utilization and packets processed per second are two valuable factors when calculating the load. Path LengthIn some routing protocols, path length refers to the sum of the costs of each link traversed up to the destination network. Other routing protocols refer to path length as the hop count , which is the number of passes through a router that a packet makes on its way to the destination network. ReliabilityThis metric allows the network administrator to assign a numeric value arbitrarily to indicate a reliability factor for the link. Some network links go down more than others do; some are easily repaired and become available relatively quickly. The reliability metric is simply a method used to capture an administrator's experience with a given network link.
|
![CCNA Exam Cram[tm] 2 (Exams 640-821, 640-811, 640-801)](/icons/blank_book.jpg "CCNA Exam Cram[tm] 2 (Exams 640-821, 640-811, 640-801)"){kind=icon}
EAN: N/A
Pages: 155