Operation of RIP
RIP Timers and Stability Features
RIP Message Format
Request Message Types
Classful Routing
Configuring RIP
Case Study: A Basic RIP Configuration
Case Study: Passive Interfaces
Configuring Unicast Updates
Case Study: Discontiguous Subnets
Case Study: Manipulating RIP Metrics
Troubleshooting RIP
The oldest of the distance vector IP routing protocols still in widespread use, RIP currently exists in two
versions. This chapter deals with version 1 of RIP. Chapter 7, "Routing Information Protocol Version 2,"
covers version 2, which adds several enhancements to RIPv1. Most notably, RIPv1 is a classful routing
protocol, whereas RIPv2 is classless. This chapter introduces classful routing, and Chapter 7 introduces
classless routing.
Distance vector protocols, based on the algorithms developed by Bellman,[1] Ford, and Fulkerson,[2] were
implemented as early as 1969 in networks such as ARPANET and CYCLADES. In the mid-1970s Xerox
developed a protocol called PARC[3] Universal Protocol, or PUP, to run on its 3Mbps experimental
predecessor to modern Ethernet. PUP was routed by the Gateway Information Protocol (GWINFO). PUP
evolved into the Xerox Network Systems (XNS) protocol suite; concurrently, the Gateway Information
Protocol became the XNS Routing Information Protocol. In turn, XNS RIP has become the precursor of
such common routing protocols as Novell's IPX RIP, AppleTalk's Routing Table Maintenance Protocol
(RTMP), and, of course, IP RIP.
The 4.2 Berkeley Software Distribution of UNIX, released in 1982, implemented RIP in a daemon called
routed; many more recent versions of UNIX are based on the popular 4.2BSD and implement RIP in
either routed or gated. [4] Oddly enough, a standard for RIP was not released until 1988, after the protocol
was in extensive deployment. That was RFC 1058, written by Charles Hedrick, and it remains the only
formal standard of RIPv1.
Depending on the literature one reads, RIP is either unjustly maligned or undeservedly popular. Although
it does not have the capabilities of many of its successors, its simplicity and widespread use mean that compatibility problems between implementations are rare. RIP was designed for smaller internetworks in
which the data links are fairly homogeneous. Within these constraints, and especially within many UNIX
environments, RIP will continue to be a popular routing protocol. 112
IT Certification CCIE,CCNP,CCIP,CCNA,CCSP,Cisco Network Optimization and Security Tips
Static or Dynamic Routing?
When reading (or being lectured about ) all the glorious details of dynamic routing protocols, it's hard not
to come away with the impression that dynamic routing is always better than static routing. It's important
to keep in mind that the primary duty of a dynamic routing protocol is to automatically detect and adapt to
topological changes in the internetwork. The price of this "automation" is paid in bandwidth and maybe
queue space, in memory, and in processing time.
A frequent objection to static routing is that it is hard to administer. This criticism may be true of medium
to large topologies with many alternative routes, but it is certainly not true of small internetworks with
few or no alternative routes.
The internetwork in Figure 4.14 has a hub-and-spoke topology popular in smaller internetworks. If a
spoke to any router breaks, is there another route for a dynamic routing protocol to choose? This
internetwork is an ideal candidate for static routing. Configure one static route in the hub router for each
spoke router and a single default route in each spoke router pointing to the hub, and the internetwork is
ready to go. (Default routes are covered in Chapter 12, "Default Routes and On-Demand Routing." )
to come away with the impression that dynamic routing is always better than static routing. It's important
to keep in mind that the primary duty of a dynamic routing protocol is to automatically detect and adapt to
topological changes in the internetwork. The price of this "automation" is paid in bandwidth and maybe
queue space, in memory, and in processing time.
A frequent objection to static routing is that it is hard to administer. This criticism may be true of medium
to large topologies with many alternative routes, but it is certainly not true of small internetworks with
few or no alternative routes.
The internetwork in Figure 4.14 has a hub-and-spoke topology popular in smaller internetworks. If a
spoke to any router breaks, is there another route for a dynamic routing protocol to choose? This
internetwork is an ideal candidate for static routing. Configure one static route in the hub router for each
spoke router and a single default route in each spoke router pointing to the hub, and the internetwork is
ready to go. (Default routes are covered in Chapter 12, "Default Routes and On-Demand Routing." )
Interior and Exterior Gateway Protocols
Areas introduce a hierarchy to the internetwork architecture. Another layer is added to this hierarchical
structure by grouping areas into larger areas. These higher-level areas are called autonomous systems in
the IP world and routing domains in the ISO world.
An autonomous system was once defined as a group of routers under a common administrative domain
running a common routing protocol. Given the fluidity of modern internetworking life, the latter part of
the definition is no longer very accurate. Departments, divisions, and even entire companies frequently
merge, and internetworks that were designed with different routing protocols merge along with them. The
result is that many internetworks nowadays combine multiple routing protocols with multiple degrees of
inelegance, all under common administrations. So a contemporary definition of an autonomous system is
an internetwork under a common administration.
NOTE
Automonous system
The routing protocols that run within an autonomous system are referred to as Interior Gateway Protocols
(IGPs). All the protocols given in this chapter as examples of distance vector or link state protocols are
IGPs.
Routing protocols that route between autonomous systems or routing domains are referred to as Exterior
Gateway Protocols (EGPs). Whereas IGPs discover paths between networks, EGPs discover paths
between autonomous systems. Examples of EGPs include the following:
Border Gateway Protocol (BGP) for IP
Exterior Gateway Protocol (EGP) for IP (yes, an EGP named EGP)
The ISO's InterDomain Routing Protocol (IDRP)
Novell also incorporates an EGP functionality, called Level 3 Routing, into NLSP.
Having given these definitions, it must be said that the common usage of the term autonomous system is
not so absolute. Various standards documents, literature, and people tend to give various meanings to the
term. As a result, it is important to understand the context in which one is reading or hearing the term.
This book uses autonomous system in one of two contexts:
Autonomous system may refer to a routing domain, as defined at the beginning of this section. In
this context, an autonomous system is a system of one or more IGPs that is autonomous from
other systems of IGPs. An EGP is used to route between these autonomous systems.
Autonomous system may also refer to a process domain, or a single IGP process that is
autonomous from other IGP processes. For example, a system of OSPF-speaking routers may be
referred to as an OSPF autonomous system. The chapters on IGRP and EIGRP also use
autonomous system in this context. Redistribution is used to route between these autonomous
systems.
The context will indicate which form of autonomous system is under discussion at different points
throughout this book.
structure by grouping areas into larger areas. These higher-level areas are called autonomous systems in
the IP world and routing domains in the ISO world.
An autonomous system was once defined as a group of routers under a common administrative domain
running a common routing protocol. Given the fluidity of modern internetworking life, the latter part of
the definition is no longer very accurate. Departments, divisions, and even entire companies frequently
merge, and internetworks that were designed with different routing protocols merge along with them. The
result is that many internetworks nowadays combine multiple routing protocols with multiple degrees of
inelegance, all under common administrations. So a contemporary definition of an autonomous system is
an internetwork under a common administration.
NOTE
Automonous system
The routing protocols that run within an autonomous system are referred to as Interior Gateway Protocols
(IGPs). All the protocols given in this chapter as examples of distance vector or link state protocols are
IGPs.
Routing protocols that route between autonomous systems or routing domains are referred to as Exterior
Gateway Protocols (EGPs). Whereas IGPs discover paths between networks, EGPs discover paths
between autonomous systems. Examples of EGPs include the following:
Border Gateway Protocol (BGP) for IP
Exterior Gateway Protocol (EGP) for IP (yes, an EGP named EGP)
The ISO's InterDomain Routing Protocol (IDRP)
Novell also incorporates an EGP functionality, called Level 3 Routing, into NLSP.
Having given these definitions, it must be said that the common usage of the term autonomous system is
not so absolute. Various standards documents, literature, and people tend to give various meanings to the
term. As a result, it is important to understand the context in which one is reading or hearing the term.
This book uses autonomous system in one of two contexts:
Autonomous system may refer to a routing domain, as defined at the beginning of this section. In
this context, an autonomous system is a system of one or more IGPs that is autonomous from
other systems of IGPs. An EGP is used to route between these autonomous systems.
Autonomous system may also refer to a process domain, or a single IGP process that is
autonomous from other IGP processes. For example, a system of OSPF-speaking routers may be
referred to as an OSPF autonomous system. The chapters on IGRP and EIGRP also use
autonomous system in this context. Redistribution is used to route between these autonomous
systems.
The context will indicate which form of autonomous system is under discussion at different points
throughout this book.
Areas
NOTE
Potential shortcomings of link state routing
An area is a subset of the routers that make up an internetwork. Dividing an internetwork into areas is a
response to three concerns commonly expressed about link state protocols:
The necessary databases require more memory than a distance vector protocol requires.
The complex algorithm requires more CPU time than a distance vector protocol requires.
The flooding of link state packets adversely affects available bandwidth, particularly in unstable
internetworks.
Modern link state protocols and the routers that run them are designed to reduce these effects, but cannot
eliminate them. The last section examined what the link state database might look like, and how an SPF
algorithm might work, for a small eight-router internetwork. Remember that the stub networks that would
be connected to those eight routers and that would form the leaves of the SPF tree were not even taken
into consideration. Now imagine an 8000-router internetwork, and you can understand the concern about
the impact on memory, CPU, and bandwidth.
This impact can be greatly reduced by the use of areas, as in Figure 4.13. When an internetwork is
subdivided into areas, the routers within an area need to flood LSAs only within that area and therefore
need to maintain a link state database only for that area. The smaller database means less required
memory in each router and fewer CPU cycles to run the SPF algorithm on that database. If frequent
topology changes occur, the resulting flooding will be confined to the area of the instability.
The routers connecting two areas (Area Border Routers, in OSPF terminology) belong to both areas and
must maintain separate topological databases for each. Just as a host on one network that wants to send a
packet to another network only needs to know how to find its local router, a router in one area that wants
to send a packet to another area only needs to know how to find its local Area Border Router. In other
words, the intra-area router/inter-area router relationship is the same as the host/router relationship but at
a higher hierarchical level.
Distance vector protocols, such as RIP and IGRP, do not use areas. Given that these protocols have no
recourse but to see a large internetwork as a single entity, must calculate a route to every network, and
must broadcast the resulting huge route table every 30 or 90 seconds, it becomes clear that link state
protocols utilizing areas can actually save system resources.
Potential shortcomings of link state routing
An area is a subset of the routers that make up an internetwork. Dividing an internetwork into areas is a
response to three concerns commonly expressed about link state protocols:
The necessary databases require more memory than a distance vector protocol requires.
The complex algorithm requires more CPU time than a distance vector protocol requires.
The flooding of link state packets adversely affects available bandwidth, particularly in unstable
internetworks.
Modern link state protocols and the routers that run them are designed to reduce these effects, but cannot
eliminate them. The last section examined what the link state database might look like, and how an SPF
algorithm might work, for a small eight-router internetwork. Remember that the stub networks that would
be connected to those eight routers and that would form the leaves of the SPF tree were not even taken
into consideration. Now imagine an 8000-router internetwork, and you can understand the concern about
the impact on memory, CPU, and bandwidth.
This impact can be greatly reduced by the use of areas, as in Figure 4.13. When an internetwork is
subdivided into areas, the routers within an area need to flood LSAs only within that area and therefore
need to maintain a link state database only for that area. The smaller database means less required
memory in each router and fewer CPU cycles to run the SPF algorithm on that database. If frequent
topology changes occur, the resulting flooding will be confined to the area of the instability.
The routers connecting two areas (Area Border Routers, in OSPF terminology) belong to both areas and
must maintain separate topological databases for each. Just as a host on one network that wants to send a
packet to another network only needs to know how to find its local router, a router in one area that wants
to send a packet to another area only needs to know how to find its local Area Border Router. In other
words, the intra-area router/inter-area router relationship is the same as the host/router relationship but at
a higher hierarchical level.
Distance vector protocols, such as RIP and IGRP, do not use areas. Given that these protocols have no
recourse but to see a large internetwork as a single entity, must calculate a route to every network, and
must broadcast the resulting huge route table every 30 or 90 seconds, it becomes clear that link state
protocols utilizing areas can actually save system resources.
The SPF Algorithm
It is unfortunate that Dijkstra's algorithm is so commonly referred to in the routing world as the shortest
path first algorithm. After all, the objective of every routing protocol is to calculate shortest paths. It is
also unfortunate that Dijkstra's algorithm is often made to appear more esoteric than it really is; many
writers just can't resist putting it in set theory notation. The clearest description of the algorithm comes E.
W. Dijkstra's original paper. Here it is in his own words, followed by a "translation" for the link state
routing protocol:
Construct [a] tree of minimum total length between the n nodes. (The tree is a graph with one and only
one path between every two nodes.)
In the course of the construction that we present here, the branches are divided into three sets:
I. the branches definitely assigned to the tree under construction (they will be in a subtree);
II. the branches from which the next branch to be added to set I, will be selected;
III. the remaining branches (rejected or not considered).
The nodes are divided into two sets:
A. the nodes connected by the branches of set I,.
B. the remaining nodes (one and only one branch of set II will lead to each of these nodes).
We start the construction by choosing an arbitrary node as the only member of set A, and by placing all
branches that end in this node in set II. To start with, set I is empty. From then onwards we perform the
following two steps repeatedly.
Step 1. The shortest branch of set II is removed from this set and added to set I. As a result, one node is
transferred from set B to set A.
Step 2. Consider the branches leading from the node, that has just been transferred to set A, to the nodes
that are still in set B. If the branch under construction is longer than the corresponding branch in set II, it
is rejected; if it is shorter, it replaces the corresponding branch in set II, and the latter is rejected.
We then return to step 1 and repeat the process until sets II and B are empty. The branches in set I form
the tree required.[13]
[13] E. W. Dijkstra. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik, Vol. 1, 1959, pp. 269–271.
Adapting the algorithm for routers, first note that Dijkstra describes three sets of branches: I, II, and III. In
the router, three databases represent the three sets:
The Tree Database.
This database represents set I. Links (branches) are added to the shortest path tree by adding them
here. When the algorithm is finished, this database will describe the shortest path tree.
The Candidate Database.
This database corresponds to set II. Links are copied from the link state database to this list in a
prescribed order, where they become candidates to be added to the tree.
The Link State Database.
The repository of all links, as has been previously described. This topological database
corresponds to set III.
Dijkstra also specifies two sets of nodes, set A and set B. Here the nodes are routers. Specifically, they are
the routers represented by Neighbor ID in the Router Links triples (Router ID, Neighbor ID, Cost). Set A
comprises the routers connected by the links in the Tree database. Set B is all other routers. Since the
whole point is to find a shortest path to every router, set B should be empty when the algorithm is
finished.
Here's a version of Dijkstra's algorithm adapted for routers:
1. A router initializes the Tree database by adding itself as the root. This entry shows the router as its
own neighbor, with a cost of 0.
2. All triples in the link state database describing links to the root router's neighbors are added to the
Candidate database.
3. The cost from the root to each link in the Candidate database is calculated. The link in the
Candidate database with the lowest cost is moved to the Tree database. If two or more links are an
equally low cost from the root, choose one.
4. The Neighbor ID of the link just added to the Tree database is examined. With the exception of
any triples whose Neighbor ID is already in the Tree database, triples in the link state database
describing that router's neighbors are added to the Candidate database.
5. If entries remain in the Candidate database, return to step 3. If the Candidate database is empty,
then terminate the algorithm. At termination, a single Neighbor ID entry in the Tree database
should represent every router, and the shortest path tree is complete.
Table 4.3 summarizes the process and results of applying Dijkstra's algorithm to build a shortest path tree
for the network in Figure 4.11. Router RA from Figure 4.11 is running the algorithm, using the link state
database of Table 4.2. Figure 4.12 shows the shortest path tree constructed for router RA by this
algorithm. After each router calculates its own tree, it can examine the other routers' network link
path first algorithm. After all, the objective of every routing protocol is to calculate shortest paths. It is
also unfortunate that Dijkstra's algorithm is often made to appear more esoteric than it really is; many
writers just can't resist putting it in set theory notation. The clearest description of the algorithm comes E.
W. Dijkstra's original paper. Here it is in his own words, followed by a "translation" for the link state
routing protocol:
Construct [a] tree of minimum total length between the n nodes. (The tree is a graph with one and only
one path between every two nodes.)
In the course of the construction that we present here, the branches are divided into three sets:
I. the branches definitely assigned to the tree under construction (they will be in a subtree);
II. the branches from which the next branch to be added to set I, will be selected;
III. the remaining branches (rejected or not considered).
The nodes are divided into two sets:
A. the nodes connected by the branches of set I,.
B. the remaining nodes (one and only one branch of set II will lead to each of these nodes).
We start the construction by choosing an arbitrary node as the only member of set A, and by placing all
branches that end in this node in set II. To start with, set I is empty. From then onwards we perform the
following two steps repeatedly.
Step 1. The shortest branch of set II is removed from this set and added to set I. As a result, one node is
transferred from set B to set A.
Step 2. Consider the branches leading from the node, that has just been transferred to set A, to the nodes
that are still in set B. If the branch under construction is longer than the corresponding branch in set II, it
is rejected; if it is shorter, it replaces the corresponding branch in set II, and the latter is rejected.
We then return to step 1 and repeat the process until sets II and B are empty. The branches in set I form
the tree required.[13]
[13] E. W. Dijkstra. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik, Vol. 1, 1959, pp. 269–271.
Adapting the algorithm for routers, first note that Dijkstra describes three sets of branches: I, II, and III. In
the router, three databases represent the three sets:
The Tree Database.
This database represents set I. Links (branches) are added to the shortest path tree by adding them
here. When the algorithm is finished, this database will describe the shortest path tree.
The Candidate Database.
This database corresponds to set II. Links are copied from the link state database to this list in a
prescribed order, where they become candidates to be added to the tree.
The Link State Database.
The repository of all links, as has been previously described. This topological database
corresponds to set III.
Dijkstra also specifies two sets of nodes, set A and set B. Here the nodes are routers. Specifically, they are
the routers represented by Neighbor ID in the Router Links triples (Router ID, Neighbor ID, Cost). Set A
comprises the routers connected by the links in the Tree database. Set B is all other routers. Since the
whole point is to find a shortest path to every router, set B should be empty when the algorithm is
finished.
Here's a version of Dijkstra's algorithm adapted for routers:
1. A router initializes the Tree database by adding itself as the root. This entry shows the router as its
own neighbor, with a cost of 0.
2. All triples in the link state database describing links to the root router's neighbors are added to the
Candidate database.
3. The cost from the root to each link in the Candidate database is calculated. The link in the
Candidate database with the lowest cost is moved to the Tree database. If two or more links are an
equally low cost from the root, choose one.
4. The Neighbor ID of the link just added to the Tree database is examined. With the exception of
any triples whose Neighbor ID is already in the Tree database, triples in the link state database
describing that router's neighbors are added to the Candidate database.
5. If entries remain in the Candidate database, return to step 3. If the Candidate database is empty,
then terminate the algorithm. At termination, a single Neighbor ID entry in the Tree database
should represent every router, and the shortest path tree is complete.
Table 4.3 summarizes the process and results of applying Dijkstra's algorithm to build a shortest path tree
for the network in Figure 4.11. Router RA from Figure 4.11 is running the algorithm, using the link state
database of Table 4.2. Figure 4.12 shows the shortest path tree constructed for router RA by this
algorithm. After each router calculates its own tree, it can examine the other routers' network link
The Link State Database
In addition to flooding LSAs and discovering neighbors, a third major task of the link state routing
protocol is establishing the link state database. The link state or topological database stores the LSAs as a
series of records. Although a sequence number and age and possibly other information are included in the
LSA, these variables exist mainly to manage the flooding process. The important information for the
shortest path determination process is the advertising router's ID, its attached networks and neighboring
routers, and the cost associated with those networks or neighbors. As the previous sentence implies, LSAs
may include two types of generic information:
The shortest path first (SPF) algorithm is run once for the router link information to establish shortest
paths to each router, and then stub network information is used to add these networks to the routers.
Figure 4.11 shows an internetwork of routers and the links between them; stub networks are not shown
for the sake of simplicity. Notice that several links have different costs associated with them at each end.
A cost is associated with the outgoing direction of an interface. For instance, the link from RB to RC has
a cost of 1, but the same link has a cost of 5 in the RC to RB direction.
protocol is establishing the link state database. The link state or topological database stores the LSAs as a
series of records. Although a sequence number and age and possibly other information are included in the
LSA, these variables exist mainly to manage the flooding process. The important information for the
shortest path determination process is the advertising router's ID, its attached networks and neighboring
routers, and the cost associated with those networks or neighbors. As the previous sentence implies, LSAs
may include two types of generic information:
The shortest path first (SPF) algorithm is run once for the router link information to establish shortest
paths to each router, and then stub network information is used to add these networks to the routers.
Figure 4.11 shows an internetwork of routers and the links between them; stub networks are not shown
for the sake of simplicity. Notice that several links have different costs associated with them at each end.
A cost is associated with the outgoing direction of an interface. For instance, the link from RB to RC has
a cost of 1, but the same link has a cost of 5 in the RC to RB direction.
Subscribe to:
Posts (Atom)