As networks grow, routing protocols need to handle issues associated with larger networks.
|
Scalability is the ability of routing protocols to scale up to larger networks.
|
Most routing algorithms can be classified as either distance vector or link-state.
|
Whatever routing algorithm is used, the following scalability concerns have to be addressed:

• convergence
|
• update traffic
|
• metric limitations
|
Convergence is the process of agreement, by all routers, on optimal routes.
|
Fast convergence is desirable in internetworks because it reduces the period during which routers rely on outdated routing information.
|
When a network event causes routes either to go down or become available, routers distribute routing update messages.
|
Routing update messages permeate networks, stimulating recalculation of optimal routes.
|
Eventually they will cause all routers using the same routing algorithms to agree on available and optimal routes.
|
Routing algorithms that converge slowly can cause routing loops or network outages.
@@
The ability of the routing algorithm to select an optimal route depends on the metrics and metric weightings used to make the calculation.
|
For instance, the ^Rhop count ^rmetric indicates the distance in number of hops, or routers, to the destination.
|
Besides hop count, routing algorithms often use ^Rdelay^r as another useful metric.
|
Delay is the length of time required to move a packet from source to destination over a given path.
|
Delay depends on the bandwidth of intermediate network links and the port queues at each router along the way.
|
Also important is network congestion on all intermediate network links and the physical distance to be traveled.
@@
The distance vector routing approach determines the direction (vector) and distance to any link in the internetwork.
|
Distance vector routing protocols are widely used.
|
They have a simple configuration and only require commonly available skills.
|
Distance vector routing algorithms periodically pass copies of a routing table sequentially from router to neighboring router.
|
Regular updates between routers communicate topology changes.
|
In the graphic, Router B receives information from Router A.
|
Router B adds a distance vector number, for example a number of hops, which increases the distance vector.
|
Router B passes the routing table to its other neighbor, Router C.
|
This step-by-step process occurs in all directions between direct neighbor routers.
@@
Each router using distance vector routing begins by identifying its own neighbors.
|
As the network discovery process proceeds, routers discover the best path to destination networks.
|
This is based on accumulated metrics, such as network distances, from each router's neighbors.
|
Metrics are used to maintain a database of internetwork topology information.
|
Distance vector algorithms do not allow a router to know the exact topology of an entire internetwork.
|
Let's see why.
|
Here, Router A learns about other noncontiguous networks based on information it receives from Router B.
|
The table entry for each of these other networks has an accumulated distance vector.
|
This shows how far away that network is in the given direction.
@@
When the topology in a distance vector protocol internetwork changes, routing table updates must occur.
|
The updates proceed step-by-step from router to router.
|
Distance vector routing tables include information about the total path cost, which is defined by its metric.
|
A router's routing table will also include information on the address of the first router on the path to each network that the router knows about.
|
When a router receives an update from a neighboring router, it compares the update to its own routing tables.
|
If the neighbor tells it about a better route to a network, that is, one with a smaller metric, the router updates its own routing table.
|
When it updates its own table the router establishes a new metric.
|
It does this by adding the cost of reaching the neighboring router to the path cost reported by the neighbor.
|
In this example, Router B is one unit of cost from Router A.
|
Router B adds 1 to all costs reported by Router A when it runs the distance vector processes to update the routing table it received from Router B.
|
So in distance vector routing, topological data is seen from the perspective of processing a neighboring router's routing table information.
|
Since at any one time a router is only updated regarding topology changes in its immediate neighborhood, it cannot form a map of the entire internetwork from its routing table.
@@
With most distance vector routing protocols, updates for topology changes come in periodic table updates.
|
These tables pass incrementally from router to neighboring router.
|
This usually results in slow convergence because routers are aware only of local topology changes and not remote ones which also have an effect on which optimal route should be chosen.
|
An internetwork's slow convergence on a new configuration can cause inconsistent routing entries.
|
And routing loops may result.
|
Let's look at an example of how a routing loop can occur.
|
Here, all routers have consistent knowledge and correct routing tables.
|
Router C's preferred path to Network 1 is via Router B.
|
And Router C has a distance of 3 to Network 1 in its routing table.
|
Let's suppose Network 1 fails.
|
Router E sends an update to Router A, which stops it routing packets to Network 1.
|
But Routers B, C, and D continue to do so because they have not yet been informed about the failure.
|
When Router A sends out its update, Routers B and D stop routing to Network 1.
|
But Router C is still not updated, and believes Network 1 is still reachable via Router B.
|
Router C sends a periodic update to Router D indicating a path to Network 1 via Router B.
|
So Router D changes its routing table to reflect this erroneous news.
|
It then passes the information on to Router A.
|
Router A sends the information to Routers B and E, and so on.
|
Any packet destined for Network 1 will now loop from Router C to B to A to D and back to C.
|
The invalid updates about Network 1 continue to loop.
|
This problem of endless network routing loops is called ^Rcount to infinity^r.
|
Routers continuously increment the hop count to particular networks, until some external boundary condition is imposed.
@@
Distance vector protocols have techniques available to counter problems with looping.
|
To avoid the count to infinity problem, distance vector protocols define infinity as some maximum number.
|
This number refers to a routing metric, for example, a simple hop count.
|
Now the routing protocol permits the routing loop only until the metric exceeds its maximum allowed value.
|
For hop count distance vectors such as the Routing Information Protocol (RIP), a maximum of 15 hops is commonly used.
|
For more information on RIP see the CBT Systems course ^RImplementing Distant Vector Routing Protocols^r.
|
Once the metric value exceeds 15 hops, the network is considered unreachable.
|
A maximum hop count of 15 for distance vector routing algorithms greatly restricts their use in large internetworks.
|
The count to infinity problem can also be solved using ^Rholddown timers^r.
|
You can use holddowns to prevent regular update messages from incorrectly reinstating a route that has gone bad.
|
A router receives an update from a neighbor indicating that a route is now inaccessible.
|
The router marks that route as inaccessible and starts a holddown timer.
|
If, at any time before the holddown timer expires, the same neighbor sends a message to say that the network is now accessible, the router

• marks the network as accessible
|
• removes the holddown timer
|
The same steps are taken if an update arrives from a different neighboring router with a better metric.
|
If the update has a poorer metric and the holddown-timer has not expired the update is ignored.
|
This allows more time for the knowledge of a disruptive change to propagate through the network.
|
The holddown period is calculated to be just greater than the period necessary to update the entire network with a routing change.
@@
You can also use the following options to handle convergence on internetworks using distance vector routing algorithms:

• poison reverse (poison reverse enabled)
|
• split horizon (poison reverse disabled)
|
Poison reverse is used to defeat routing loops on large internetworks.
|
When poison reverse is enabled, the router sets a table entry assigning an infinite cost to a nonaccessible route.
|
For example, in RIP the cost might be 16.
|
Assigning an infinite cost to a nonaccessible route keeps the network state consistent.
|
It also gives other routers time to converge on the topology change.
|
Here, for example, when Network 1 goes down, Router E enters an infinite cost in its table for that network.
|
This ^Rpoisons^r its route to Network 1.
|
Router E is no longer susceptible to incorrect updates about the network coming from neighboring routers.
|
The router will keep the poison-route entry for several update cycles.
|
After a variable amount of time, the router can trigger an update about the network in its neighbors.
|
All routers recompute their distance vector tables and converge on the topology change.
|
If the split horizon method is used route information is not sent back to the source from which it came.
|
This reduces incorrect routing information and the endless looping that results.
|
Split horizon is used to solve routing loops between adjacent routers.
|
In this example, Router A passes an update to Router B and D indicating that Network 1 is down.
|
However, Router C has not yet been informed and passes an incorrect update to Router B indicating that the network is available by way of Router D.
|
Router B is now ready to transmit this now incorrect information to Router A.
|
However using split horizon means that neither Router B or D can send information about Network 1 back to Router A.
|
Whether you enable or disable poison reverse, you reduce the time required for convergence on, for example, RIP internetworks.
|
But you increase the amount of RIP traffic on the network.
|
Update traffic generated by distance vector protocols is a concern when scaling up a network.
|
For example, RIP requires that each router broadcast its entire database every 30 seconds.
|
And traffic from looping solutions reduces bandwidth for data-carrying packets.
|
But distance vector traffic demands are not as heavy as those of link-state protocols.
@@
Link-state routing uses

• link-state packets (LSPs)
|
• topological databases
|
• shortest path first (SPF)
  algorithms
|
• SPF trees
|
• routing tables
|
Link-state routing protocols send routing information to all nodes in the internetwork.
|
Routing information is contained in what are known as "link-state packets" (LSPs).
|
Each router sends only that portion of the routing table that describes the state of its own links.
|
The router has received link-state information from other routers.
|
Next each router in parallel constructs a database.
|
This database represents a map of the internetwork.
|
Using this topological database, each router runs a shortest path first (SPF) algorithm.
|
The SPF algorithm constructs a path tree to each destination within the internetwork.
|
The link-state protocol most commonly used on IP internetworks is the Open Shortest Path First (OSPF) protocol.
|
RFC 1247 contains a description of OSPF link-state concepts and operations.
|
For more information on OSPF see the CBT Systems course ^RImplementing OSPF on Cisco Routers^r.
@@
Link-state protocols work on event-triggered updates.
|
Small LSPs are sent to routers or groups of routers.
|
And when a topology change occurs, link-state algorithms used for updating routing tables rely on using the same link-state updates.
|
An initial router notices a change in link-state topology.
|
It first advertises the change to all routers.
|
Or it will notify a designated router that other routers use for updates.
|
This process is called ^Rflooding.^r
|
In this way, each router's database is updated and the topology map of the internetwork is maintained.
|
To achieve convergence, each router will keep track of its neighbors.
|
The router then constructs a LSP which lists its neighbor's

• router names
|
• link costs
|
Other information in the LSP includes:

• new neighbors
|
• changes in link costs
|
• links to neighbors who have gone down
|
Each router sends its LSP to the others.
|
The latest LSP that has been received by each router is recorded in a database.
|
Accumulated LSP data is used to construct a complete map of the current internetwork topology.
|
The SPF algorithm is then rerun to compute routes to every network destination.
|
Each time an LSP causes a change to the link-state database, the link-state algorithm

• recalculates the best paths
|
• updates the routing table
|
Then every router takes topology changes into account to determine shortest paths for packet switching.
|
Distance vector routing determines the best path by adding to the metric value it receives as tables move from router to router.
|
But in link-state routing, each router works in parallel to calculate its own shortest path.
|
Using link-state protocols allows for fast convergence on the internetwork.
|
Rapid convergence in link-state protocols makes them less prone to routing loops than distance vector protocols.
@@
In terms of scalability, there are some concerns with regard to link-state.
|
These are

• heavy memory, processing,
  and bandwidth requirements
|
• problems with 
  unsynchronized updates
  and segmentation
|
Using link-state protocols places very high memory demands on routers.
|
This is because routers must hold information from various databases, the topology tree, and the routing table.
|
Routers use Dijkstra's algorithm to compute the shortest path first to a network node.
|
This algorithm requires a processing task proportional to the number of links, multiplied by the number of routers in the internetwork.
|
However, as the size of internetworks increases, using this algorithm makes consistently higher demands on routers' processing power.
|
The packet flooding caused by routers sending LSPs to other routers reduces bandwidth available to routed traffic carrying user data.
|
After the initial flooding, bandwidth is only required for sending infrequent or event-triggered LSPs that reflect topology changes.
@@
There are ways of solving link-state protocol resource related problems.
|
For example, a network administrator can reduce the periodic distribution of LSPs.
|
Updates will only occur at less frequent intervals.
|
The process of reducing LSP distribution frequency is called ^Rdampening^r.
|
Dampening the update frequency does not interfere with LSP updates triggered by topology changes.
|
LSP updates can go to a ^Rmulticast^r group rather than flood to all routers.
|
For instance, on interconnected LANs, you can use one or more designated routers as the target depository for LSP transmissions.
|
Other routers can use their designated routers as a specialized source of consistent topological data.
|
Another solution of resource problems is setting up a ^Rhierarchy ^rof different router levels.
|
A router in one area of a hierarchical domain does not need to store and process LSPs from other routers not located in its area.
@@
There may be problems with unsynchronized updates when using link-state routing protocols.
|
For example, suppose that here, Network 1 between Routers C and D goes down.
|
Both routers construct an LSP to reflect this unreachable status.
|
But soon afterwards Network 1 comes back up and another LSP reflecting this next topology change is needed.
|
The original "Network 1 unreachable" message from Router C may use a slow path for its update.
|
If so, this LSP can arrive at Router A after Router D's "Network 1 back up now" LSP.
|
With unsynchronized LSPs, Router A will face a dilemma about which SPF tree to construct.
|
It will also be unclear whether it should use paths that include Network 1, since Network 1 was most recently reported as unreachable.
|
If LSP distribution to all routers is not done correctly, link-state routing can result in invalid routes.
|
The problem of faulty LSP distribution is intensified when scaling up with link-state protocols on very large internetworks.
|
If one part of the internetwork comes up before the others, the order for sending and receiving LSPs will vary.
|
This variation can alter and impair convergence.
|
This is because routers might learn about different versions of the topology before they construct SPF trees and routing tables.
|
On a large internetwork, parts that update quickly cause problems for parts that update slowly.
|
Routers sending out LSPs cannot assume they will be transported correctly by routers that use table entries which may not reflect the current topology.
|
When updates are faulty, LSPs can multiply through the network and consume more and more bandwidth.
|
Differences in update speed may eventually result in ^Rsegmentation ^ror^R partitioning^r.
|
The internetwork becomes split into fast-updating and slow-updating parts.
@@
For LSP co-ordination problems, link-state implementations allow certain LSP controls.
|
The following controls help administrators to avoid inaccurate LSP distribution or unsynchronized updates

• time stamps
|
• sequence numbers
|
• aging schemes
|
Partitioning can be managed using an area hierarchy.
|
However the particular link-state protocol used must allow hierarchical management.
|
In this procedure, routers can concentrate on just the routers within their own domain or area.
|
And they can depend on special routers at the domain borders for external routing information.
|
The link-state protocol's sophisticated controls for troubleshooting its scalability problems is a considerable advantage.
|
Despite their differences both link-state and distance vector algorithms perform well in most circumstances.
@@
