Routing Protocol

Distance Vector Routing Protocols

Introduction

Distance Vector routing protocols use frequent broadcasts (255.255.255.255 or FF:FF:FF:FF) of their entire routing table every 30 sec. on all their interfaces in order to communicate with their neighbours. The bigger the routing tables, the more broadcasts. This methodology limits significantly the size of network on which Distance Vector can be used.

Routing Information Protocol (RIP) and Interior Gateway Routing Protocol (IGRP) are two very popular Distance Vector routing protocols. You can find links to more information on these protocols at the bottom of the page. (That's if you haven't had enough by the time you get there !)

Distance Vector protocols view networks in terms of adjacent routers and hop counts, which also happens to be the metric used. The "hop" count (max of 15 for RIP, 16 is deemed unreachable and 255 for IGMP), will increase by one every time the packet transits through a router.

So the router makes decisions about the way a packet will travel, based on the amount of hops it takes to reach the destination and if it had 2 different ways to get there, it will simply send it via the shortest path, regardless of the connection speed. This is known as pinhole congestion.

Below is a typical routing table of a router which uses Distance Vector routing protocols:

Let's explain what is happening here:

In the above picture, you see 4 routers, each connected with its neighbour via some type of WAN link e.g ISDN.

Now, when a router is powered on, it will immediately know about the networks to which each interface is directly connected. In this case Router B knows that interface E0 is connected to the 192.168.0.0 network and the S0 interface is connected to the 192.168.10.0network.

Looking again at the routing table for Router B, the numbers you see on the right hand side of the interfaces are the "hop counts" which, as mentioned, is the metric that distance vector protocols use to keep track on how far away a particular network is. Since these 2 networks are connected directly to the router's interface, they will have a value of zero (0) in the router's table entry. The same rule applies for every router in our example.

Remember we have "just turn the routers on", so the network is now converging and that means that there is no data being passed. When I say "no data" I mean data from any computer or server that might be on any of the networks. During this "convergence" time, the only type of data being passed between the routers is that which allows them to populate their routing tables and after that's done, the routers will pass all other types of data between them. That's why a fast convergence time is a big advantage.

One of the problems with RIP is that it has a slow convergence time.

 

Let's explain the above diagram:

In the above picture, the network is said to have "converged", in other words, all routers on the network have populated their routing table and are completly aware of the networks they can contact. Since the network is now converged, computers in any of the above networks can contact each other.

Again, looking at one of the routing tables, you will notice the network address with the exit interface on the right and next to that is the hop count to that network. Remember that RIP will only count up to 15 hops, after which the packet is discarded (on hop 16).

Each router will broadcast its entire routing table every 30 seconds.

Routing based on Distance Vector can cause a lot of problems when links go up and down, this could result in infinite loops and can also de-synchronise the network.

Routing loops can occur when every router is not updated close to the same time.

Let's have a look at the problem before we look at the various solutions:

 

Let's explain the above:

In the above picture you can see 5 routers of which routers A and B are connected with Router C, and they all end up connecting via routers D and E to Network 5.

As the above diagram shows, Network 5 suddenly fails.

 

All routers know about Network 5 from Router E. For example, Router A, in its tables, has a path to Network 5 through routers B, D andE.

When Network 5 fails, Router E knows about it since it's directly connected to it and tells Router D about it on its next update (when it will broadcast its entire routing table). This will result in Router D stopping routing data to Network 5 through Router E. But as you can see in the above picture, routers A B and C don't know about Network 5 yet, so they keep sending out update information. Router D will eventually send out its update and cause Router B to stop routing to Network 5, but routers A and C are still not updated. To them, it appear that Network 5 is still available through Router B with a metric of 3 !

 

Now Router A sends its regular broadcast of its entire routing table which includes reachability for Network 5. Routers C and B receive the wonderful news that Network 5 can be reached from Router A, so they send out the information that Network 5 is now available !

From now on, any packet with a destination of Network 5 will go to Router A then to Router B and from there back to Router A (remember that Router B got the good news that Network 5 is available via Router A).

So this is where things get a bit messy and you have that wonderful loop, where data just gets passed around from one router to another. Seems like they are playing ping pong :)

To deal with these problems we use the following techniques:

Maximum Hop Count

The routing loop we just looked at is called "counting to infinity" and it is caused by gossip and wrong information being communicated between the routers. Without something to protect against this type of a loop, the hop count will keep on increasing each time the packet goes through a router ! One way of solving this problem is to define a maximum hop count. Distance Vector (RIP) permits a hop count of up to 15, so anything that needs 16 hops is unreachable. So if a loop occurred, it would go around the network until the packet reached a hop count of 15 and the next router would simply discard the packet.

Split Horizon

Works on the principle that it's never useful to send information about a router back to the destination from which the original packet came. So if for example I told you a joke, it's pointless you telling me that joke again !

In our example it would have prevented Router A from sending the updated information it received from Router B back to Router B.

Route Poisoning

Alternative to split horizon, when a router receives information about a route from a particular network, the router advertises the route back to that network with the metric of 16, indicating that the destination is unreachable.

In our example, this means that when Network 5 goes down, Router E initiates router poisoning by entering a table entry for Network 5 as 16, which basically means it's unreachable. This way, Router D is not susceptible to any incorrect updates about the route to Network 5. When Router D receives a router poisoning from Router E, it sends an update called a poison reverse, back to Router E. This make sure all routes on the segment have received the poisoned route information.

Route poisoning, used with hold-downs (see section below) will certainly speed up convergence time because the neighboring routers don't have to wait 30 seconds before advertising the poisoned route.

Hold-Down Timers

Routers keep an entry for the network-down state, allowing time for other routers to recompute for this topology change, this way, allowing time for either the downed router to come back or the network to stabilise somewhat before changing to the next best route.

When a router receives an update from a neighbor indicating that a previously accessible network is not working and is inaccessible, the hold-down timer will start. If a new update arrives from a neighbor with a better metric than the original network entry, the hold-down is removed and data is passed. But an update is received from a neighbor router before the hold-down timer expires and it has a lower metric than the previous route, therefore the update is ignored and the hold-down timer keeps ticking. This allows more time for the network to converge.

Hold-down timers use triggered updates, which reset the hold-down timer, to alert the neighbor's routers of a change in the network. Unlike update messages from neighbor routers, triggered updates create a new routing table that is sent immediatley to neighbor routers because a change was detected in the network.

There are three instances when triggered updates will reset the hold-down timer:

1) The hold-down timer expires

2) The router received a processing task proportional to the number of links in the internetwork.

3) Another update is received indicating the network status has changed.

In our example, any update received by Router B from Router A, would not be accepted until the hold-down timer expires. This will ensure that Router B will not receive a "false" update from any routers that are not aware that Network 5 is unreachable. Router B will then send a update and correct the other routers' tables.

Link State Routing Protocols

Introduction

Link State routing protocols do not view networks in terms of adjacent routers and hop counts, but they build a comprehensive view of the overall network which fully describes the all possible routes along with their costs. Using the SPF (Shortest Path First) algorithm, the router creates a "topological database" which is a hierarchy reflecting the network routers it knows about. It then puts it's self on the top of this hierarchy, and has a complete picture from it's own perspective.

Link State protocols, unlike Distance Vector broadcasts, use multicast.

Multicast is a "broadcast" to a group of hosts, in this case routers (Please see the multicast page for more information). So if I had 10 router of which 4 where part of a "mutilcast group" then, when I send out a multicast packet to this group, only these 4 routers will receive the updates, while the rest of them will simply ignore the data. The multicast address is usually 224.0.0.5 & 224.0.0.6, this address is defined by the IGRP (Interior Gateway Routing Protocol).

When a router using a Link State protocol, such a OSPF (Open Shortest Path First) knows about a change on the network, it will multicast this change instantly, there for flooding the network with this information. The information routers require to build their databases is provided in the form of Link State advertisement packets (LSAP). Routers do not advertise their entire routing tables, instead each router advertises only its information regarding immediately adjacent routers.

Link State protocols in comparison to Distance Vector protocols have:

• Big memory requirements
• Shortest path computations require many CPU circles
• If network is stable little bandwidth is used; react quickly to topology changes
• Announcements cannot be “filtered”. All items in the database must be sent to neighbors
• All neighbors must be trusted
• Authentication mechanisms can be used to avoid undesired adjacencies
• No split horizon techniques are possible

Even though Link State protocols work more efficiently, problem can arise. Usually problems occur cause of changes in the network topology (links go up-down), and all routers don't get updated immediately cause they might be on different line speeds, there for, routers connected via a fast link will receive these changes faster than the others on a slower link.

Different techniques have been developed to deal with these problem and these are :

1) Dampen update frequency

2) Target link-state updates to multicast

3) Use link-state area hierarchy for topology

4) Exchange route summaries at area borders

5) Use Time-stamps Update numbering & counters

6) Manage partitions using a area hierarchy

Please select one of the following Link State routing protocols:

Open Shortest Path First - OSPF

Hybrid Routing Protocols

Hybrid routing protocols are something inbetween Distance Vector and Link State routing protocols.

Please select the Hybrid protocol you want to read about:

Enhanced Interior Gateway Routing Protocol - EIGRP

Introduction to RIP

Routing Information Protocol (RIP) is a true Distance-Vector routing protocol. It sends the complete routing table out to all active interfaces every 30 seconds. RIP only uses hop count to determine the best way to a remote network, but it has a maximum allowable hop count of 15, meaning that 16 is deemed unreachable. RIP works well in small networks, but it is inefficient on large networks with slow WAN links or on networks with large number of routers installed.

RIP comes in two different versions. RIP version 1 uses only classful routing, which means that all devices in the network must use the same subnet mask. This is because RIP version 1 does not include the subnet mask when it sends updates. RIP v1 uses broadcasts (255.255.255.255).

RIP version 2 does, however, and this is what we call classless routing (check the Subnetting section for more details). RIP v2 uses multicasts (224.0.0.9) to update its routing tables.

Route Update Timer: Sets the interval, usually 30 seconds, between periodic routing updates, in which the router sends a complete copy of its routing table out to all neighbor routers.

Route Invalid Timer: Determines the length of time that must expire, usually 90 seconds, before the router determines that a route is invalid. It will come to this conclusion if it doesn't hear any updates about that route for that period. When the timer expires, the router will send out an update to its neighbors letting them know that the route is invalid.

Route Flush Timer: Sets the time between a route becoming invalid and its removal from the routing table (240 secs). Before it's removed, the router will notify its neighbors of that route's impending doom ! The value of the route invalid timer must be less than that of the route flush timer. This is to provide the router with enough time to tell its neighbors about the invalid route before the routing table is updated.

Enhanced Interior Gateway Routing Protocol - EIGRP

Introduction

Enhanced Interior Gateway Routing Protocol (EIGRP) is another Cisco proprietary, hybrid (has feature of Distance Vector and Link State protocols), interior gateway protocol (IGP) used by routers to exchange routing information. EIGRP uses a composite metric composed of Bandwidth, Delay, Reliability, and Loading to determine the best path between two locations.

EIGRP can route IP, IPX and Appletalk. Along with IS-IS, it is one of the few multi-protocol routing protocols.

The Diffusing Update Algorithm (DUAL) is the heart of EIGRP. In essence, DUAL always keeps a backup route in mind, in case the primary route goes down. DUAL also limits how many routers are affected when a change occurs to the network.

There is no maximum allowable number of hops. In a EIGRP network, each router multi-casts "hello" packs to discover its adjacent neighbor. This adjcency database is shared with other router to build a topology database. From the topology database the best route (Successor) and the second best route (Feasible Successor) is found.

EIGRP is classless, meaning it does include the subnet mask in routing updates. However, by default 'auto-summary' is enable. You must disable if you want subnet information from other major networks.

The EIGRP metric is a can be a complex calculation, but by default it only uses bandwidth and delay to determine the best path.

Open Shortest Path First (OSPF) Routing Protocol

Introduction

Open Shortest Path First (OSPF) is a routing protocol developed for Internet Protocol (IP) networks by the interior gateway protocol (IGP) working group of the Internet Engineering Task Force (IETF). The working group was formed in 1988 to design an IGP based on the shortest path first (SPF) algorithm for use in the Internet. Similar to the Interior Gateway Routing Protocol (IGRP), OSPF was created because in the mid-1980s, the Routing Information Protocol (RIP) was increasingly unable to serve large, heterogeneous internetworks.

OSPF is a classless routing protocol, which means that in its updates, it includes the subnet of each route it knows about, thus, enabling variable-length subnet masks. With variable-length subnet masks, an IP network can be broken into many subnets of various sizes. This provides network administrators with extra network-configuration flexibility.These updates are multicasts at specific addresses (224.0.0.5 and 224.0.0.6).

The 3D diagram below shows us the information that each field of an OSPF packet contains:

Analysis Of "Type" Field

All OSPF packets begin with a 24-byte header, which is shown right above. There is however one field I would like to give a bit more attention to, and this is the "Type" field which is 1 byte long.

As illustrated in the diagram, the "Type" field identifies the OSPF packet type as one of the following:

• Hello: Establishes and maintains neighbor relationships.
• Database Description: Describes the contents of the topological database. These messages are exchanged when an adjacency is initialized.
• Link-state Request: Requests pieces of the topological database from neighbor routers. These messages are exchanged after a router discovers (by examining database-description packets) that parts of its topological database are out of date.
• Link-state Update: Responds to a link-state request packet. These messages also are used for the regular dispersal of Link-State Acknowledgments (LSA). Several LSAs can be included within a single link-state update packet.
• Link-state Acknowledgment: Acknowledges link-state update packets.

OSPF has two primary characteristics:

1) The protocol is open (non proprietary), which means that its specification is in the public domain. The OSPF specification is published as Request For Comments (RFC) 1247.

2) The second principal characteristic is that OSPF is based on the SPF algorithm, which sometimes is referred to as the Dijkstra algorithm, named for the person credited with its creation.

OSPF is a Link State routing protocol that calls for the sending of link-state advertisements (LSAs) to all other routers within the same hierarchical area. Information on attached interfaces, metrics used, and other variables is included in OSPF LSAs. As OSPF routers accumulate link-state information, they use the SPF algorithm to calculate the shortest path to each node.

As a Link State routing protocol, OSPF contrasts with RIP and IGRP, which are Distance Vector routing protocols. Routers running the Distance Vector algorithm send all or a portion of their routing tables in routing-update messages to their neighbors.

Additional OSPF features include equal-cost, multipath routing, and routing based on upper-layer type-of-service (TOS) requests. TOS-based routing supports those upper-layer protocols that can specify particular types of service. An application, for example, might specify that certain data is urgent. If OSPF has high-priority links at its disposal, these can be used to transport the urgent datagram.

OSPF supports one or more metrics. If only one metric is used, it is considered to be arbitrary, and TOS is not supported. If more than one metric is used, TOS is optionally supported through the use of a separate metric (and, therefore, a separate routing table) for each of the eight combinations created by the three IP TOS bits (the delay, throughput, and reliability bits). If, for example, the IP TOS bits specify low delay, low throughput, and high reliability, OSPF calculates routes to all destinations based on this TOS designation.

Interior Gateway Protocol - IGRP

Introduction

Interior Gateway Routing Protocol (IGRP) is a Cisco proprietary Distance-Vector routing protocol. This means that all your routers must be Cisco routers in order to use IGRP in your network, keep in mind that Windows 2000 now supports it as well because they have bought a licence from Cisco to use the protocol !

Cisco created this routing protocol to overcome the problems associated with RIP.

IGRP has a maximum hop count of 255 with a default of 100. This is helpful in larger networks and solves the problem of there being only 15 hops maximum possible in a RIP network. IGRP also uses a different metric from RIP. IGRP uses bandwidth and delay of the line by default as a metric for determining the best route to an internetwork. This is called a composite metric. Reliability, load and Maximum Transmission Unit (MTU) can also be used, although they are not used by default.

IGRP has a set of timers to enhance its performance and functionality:

Update Timer: These specify how frequently routing-update messages should be sent. The default is 90 seconds.

Invalid Timers: These specify how long a router should wait before declaring a route invalid if it doesn't receive a specific update about it. The default is three times the update period.

Hold-down Timers: These specify the hold-down period. The default is three times the update timer period plus 10 seconds.

Route Flush Timer:These indicate how much time should pass before a route should be flushed from the routing table. The default is seven times the routing period.