Chương 1. Internet & kết nối liên mạng với giao thức IP
1.4.2 Types of IP routing and IP routing algorithms
Routing algorithms build and maintain the IP routing table on a device. There are two primary methods used to build the routing table:
_ Static routing: Static routing uses preprogrammed definitions representing paths through the network.
_ Dynamic routing: Dynamic routing algorithms allow routers to automatically discover and maintain awareness of the paths through the network. This automatic discovery can use a number of currently available dynamic routing protocols. The difference between these protocols is the way they discover and calculate new routes to destination networks. They can be classified into four broad categories:
– Distance vector protocols – Link state protocols – Path vector protocols – Hybrid protocols
The remainder of this section describes the operation of each algorithm.
There are several reasons for the multiplicity of protocols:
_ Routing within a network and routing between networks typically have different requirements for security, stability, and scalability. Different routing protocols have been developed to address these requirements.
_ New protocols have been developed to address the observed deficiencies in established protocols.
_ Different-sized networks can use different routing algorithms. Small to medium-sized networks often use routing protocols that reflect the simplicity
of the environment.
However, these protocols do not scale to support large, interconnected networks.
More complex routing algorithms are required to support these environments.
1.4.2.1 Static routing
Static routing is manually performed by the network administrator. The
administrator is responsible for discovering and propagating routes through the network. These definitions are manually programmed in every routing device in the environment.
After a device has been configured, it simply forwards packets out the
predetermined ports. There is no communication between routers regarding the current topology of the network.
In small networks with minimal redundancy, this process is relatively simple to administer. However, there are several disadvantages to this approach for maintaining IP routing tables:
_ Static routes require a considerable amount of coordination and maintenance in non-trivial network environments.
_ Static routes cannot dynamically adapt to the current operational state of the network. If a destination subnetwork becomes unreachable, the static routes pointing to that network remain in the routing table. Traffic continues to be forwarded toward that destination. Unless the network administrator updates the static routes to reflect the new topology, traffic is unable to use any alternate paths that may exist.
Normally, static routes are used only in simple network topologies. However, there are additional circumstances when static routing can be attractive. For example, static routes can be used:
_ To manually define a default route. This route is used to forward traffic when the routing table does not contain a more specific route to the destination.
_ To define a route that is not automatically advertised within a network.
_ When utilization or line tariffs make it undesirable to send routing advertisement traffic through lower-capacity WAN connections.
_ When complex routing policies are required. For example, static routes can be used to guarantee that traffic destined for a specific host traverses a designated network path.
_ To provide a more secure network environment. The administrator is aware of all subnetworks defined in the environment. The administrator specifically
authorizes all communication permitted between these subnetworks.
To provide more efficient resource utilization. This method of routing table management requires no network bandwidth to advertise routes between neighboring devices. It also uses less processor memory and CPU cycles to calculate network paths.
1.4.2.2 Distance vector routing
Distance vector algorithms are examples of dynamic routing protocols. These algorithms allow each device in the network to automatically build and maintain a local IP routing table.
The principle behind distance vector routing is simple. Each router in the
internetwork maintains the distance or cost from itself to every known destination.
This value represents the overall desirability of the path. Paths associated with a smaller cost value are more attractive to use than paths associated with a larger value. The path represented by the smallest cost becomes the preferred path to reach the destination.
This information is maintained in a distance vector table. The table is periodically advertised to each neighboring router. Each router processes these
advertisements to determine the best paths through the network.
The main advantage of distance vector algorithms is that they are typically easy to implement and debug. They are very useful in small networks with limited redundancy. However, there are several disadvantages with this type of protocol:
_ During an adverse condition, the length of time for every device in the network to produce an accurate routing table is called the convergence time. In large, complex internetworks using distance vector algorithms, this time can be excessive. While the routing tables are converging, networks are susceptible to inconsistent routing behavior. This can cause routing loops or other types of unstable packet forwarding.
_ To reduce convergence time, a limit is often placed on the maximum number of hops contained in a single route. Valid paths exceeding this limit are not usable in distance vector networks.
_ Distance vector routing tables are periodically transmitted to neighboring devices. They are sent even if no changes have been made to the contents of the table. This can cause noticeable periods of increased utilization in
reduced capacity environments.
Enhancements to the basic distance vector algorithm have been developed to reduce the convergence and instability exposures. We describe these
enhancements in 5.3.5, “Convergence and counting to infinity” on page 185.
RIP is a popular example of a distance vector routing protocol.
1.4.2.3 Link state routing
The growth in the size and complexity of networks in recent years has necessitated the development of more robust routing algorithms. These algorithms address the shortcoming observed in distance vector protocols.
These algorithms use the principle of a link state to determine network topology.
A link state is the description of an interface on a router (for example, IP address, subnet mask, type of network) and its relationship to neighboring routers. The collection of these link states forms a link state database.
The process used by link state algorithms to determine network topology is straightforward:
1. Each router identifies all other routing devices on the directly connected networks.
2. Each router advertises a list of all directly connected network links and the associated cost of each link. This is performed through the exchange of link state advertisements (LSAs) with other routers in the network.
3. Using these advertisements, each router creates a database detailing the current network topology. The topology database in each router is identical.
4. Each router uses the information in the topology database to compute the most desirable routes to each destination network. This information is used to update the IP routing table.
Shortest-Path First (SPF) algorithm
The SPF algorithm is used to process the information in the topology database. It provides a tree-representation of the network. The device running the SPF algorithm is the root of the tree. The output of the algorithm is the list of
shortest-paths to each destination network. Figure 5-3 on page 178 provides an example of the shortest-path algorithm executed on router A.
Because each router is processing the same set of LSAs, each router creates an identical link state database. However, because each device occupies a different place in the network topology, the application of the SPF algorithm produces a different tree for each router.
The OSPF protocol is a popular example of a link state routing protocol.
1.4.2.4 Path vector routing
Path vector routing is discussed in RFC 1322; the following paragraphs are based on the RFC.
The path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those
destinations.
A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path vector routing, where the routers receive a vector that contains paths to a set of destinations.
The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed. The path represented by the smallest number of domains becomes the preferred path to reach the destination.
The main advantage of a path vector protocol is its flexibility. There are several other advantages regarding using a path vector protocol:
_ The computational complexity is smaller than that of the link state protocol.
The path vector computation consists of evaluating a newly arrived route and comparing it with the existing one, while conventional link state computation requires execution of an SPF algorithm.
_ Path vector routing does not require all routing domains to have
homogeneous policies for route selection; route selection policies used by one routing domain are not necessarily known to other routing domains. The support for heterogeneous route selection policies has serious implications for the computational complexity. The path vector protocol allows each domain to make its route selection autonomously, based only on local policies. However, path vector routing can accommodate heterogeneous
route selection with little additional cost.
_ Only the domains whose routes are affected by the changes have to recompute.
_ Suppression of routing loops is implemented through the path attribute, in contrast to link state and distance vector, which use a globally-defined monotonically thereby increasing metric for route selection. Therefore, different confederation definitions are accommodated because looping is avoided by the use of full path information.
_ Route computation precedes routing information dissemination. Therefore, only routing information associated with the routes selected by a domain is distributed to adjacent domains.
_ Path vector routing has the ability to selectively hide information.
However, there are disadvantages to this approach, including:
_ Topology changes only result in the recomputation of routes affected by these changes, which is more efficient than complete recomputation. However, because of the inclusion of full path information with each distance vector, the effect of a topology change can propagate farther than in traditional distance
vector algorithms.
_ Unless the network topology is fully meshed or is able to appear so, routing loops can become an issue.
BGP is a popular example of a path vector routing protocol.