Friday, September 14, 2012

Part 3: Evaluate the Characteristics of Routing Protocols

Routers do their thing at layer 3 of the OSI model, so they are responsible for choosing the best path for a layer 3 pdu (packet, remember?) based on its layer 3, or IP address.
But how do routers know the best path for a packet to be sent down? Well, you have two choices.
  • The router could learn the route itself by using a dynamic routing protocol, which allows the router to find out about the network topology and build itself a routing table, or...
  • You manually configure a static route, and tell the router where it needs to send traffic destined for particular destinations.
Once you configure a static route, the router adds it to the routing table, and gives it an administrative distance of 1. Let's look into this a little.

The Administrative Distance is basically a measure of trustworthiness.  In its uh, "career", a router can receive routing information from a variety of sources, various routing protocols etc, and it needs to know which routing protocols to prioritise. For example, a router receives two seperate routes to the same place, one route uses IGRP, which is old and outdated, and the second uses EIGRP, which is the new(ish) standard.
Administrative Distance is what allows the router to say "well actually I'll trust EIGRP on this one, if you don't mind".

 Here are the administrative distances that we, as CCNA students, will most frequently come across:

Directly Connected Route: 0
Manually Configured Static Route: 1
EIGRP Summary Route: 5
EIGRP (Internal) 90
OSPF 110
RIP 120

Note that the aforementioned IGRP, which has an admin distance of 100, is not listed above. This is because IGRP is now outdated and has been largely replaced by EIGRP now. Note also that these administrative distances can be modified from their default values. This allows you to, for example, configure a static route as a backup route, if you give it an administrative distance that is higher than a dynamic route in the routing table.

Routers use Routing protocols to pass information about networks and network locations to each other. Examples of these routing protocols include RIP, OSPF and EIGRP.
It's important not to confuse routing protocols (the protocols that facilitate routing) with the routed protocols, that is, the protocols that define the information contained in a packet.

Autonomous System Numbers are assigned to portions of a larger network, enabling the administrator/architect to break the network in its entirety down into smaller portions. A routing protocol such as BGP (Border Gateway Protocol) is required to route between autonomous systems, even if these disparate autonomous systems are part of a single physically contiguous network.
On the internet, that is, on public networks outside of enterprise/private networks, autonomous system numbers are assigned by ARIN - The American Registry of Internet Numbers.

Routers (and therefore the network) achieve convergence when all routers share a common view of the network. If the network changes, routers must recalculate their routing tables using a dynamic routing protocol. A major advantage of AS numbers is that they break the network into manageable groups, allowing the routers to converge more quickly.

Types of Routing Protocols:

 Routing protocols are divided into two types, depending on their method of operation. Link State, and Distance Vector.
  • Link-State protocols build a topology of the entire network, and send Link State Advertisements (LSAs) to update other routers. LSAs are used to build a full topology of the network (or AS?), and are flooded throughout the network only when there is a topology change. Routers use the SPF (Shortest Path First) algorithm and LSAs to build both a shortest path tree, as well as a routing table. Using LSAs requires a more powerful router, as the process of maintaining a full loop-free topological database requires more memory than Distance Vector protocols.
  • Distance-Vector protocols on the other hand send periodic updates containing the entire routing table, whether the topology changes or not. In addition, as there is no topology table in D-V routing protocols, each router is only aware of its immediate neighbours. Without the routing table, routers running distance-vector protocols use metrics (such as hop count) to determine the best path to its neighbours. 
 When a router receives a packet on a port, it examines the destination address and compares it to the routing table. The routing table is used to determine the best path for the packet, which is then forwarded out of the appropriate port.

Each of the following protocols functions at the internet layer of the TCP/IP model, that is, layer 3 (the network layer) of the OSI model. 

RIP: Distance Vector. Broadcasts updates every 30 seconds and uses hop count as the metric. The maximum hop count is 15 (Literature says that the maximum hop count is 16, but in practical use, anything over 15 hops away is deemed to be unreachable). 
IGRP: Distance Vector protocol, now outdated. Broadcasts updates every 90 seconds, and uses a composite metric of bandwidth, delay, load, and reliability.
OSPF: Link-State protocol. Updates only when there is a change in topology.
EIGRP: Hybrid: Uses features of both link state and distance vector protocols, and multicasts any updates on

As mentioned previously, BGP can be used to route between autonomous systems. It can also be used to route between seperate routing protocols.


Metrics are used to aid routers in discovering the best path to forward packets. The metrics used vary from routing protocol to routing protocol, and can be one or more of the
  • Internetwork Delay
  • Bandwidth
  • Hop Count
  • Reliability
  • Load
Distance Vector routing protocols exchange routing tables with their neighbours in order to ascertain the metric and the best path. If these routers don't exchange their routing tables quickly enough in a changing network, a loop can occur.

A router may not receive an update that a link is down, and proceed to advertise that it can, in fact, get to the network. If these updates are passed to other routers, packets destined for this network could continue to pass around the network continuously. 

Distance vector routing protocols monitor the distance that a packet has travelled as it passes over the network, to avoid this kind of loop. RIP tracks the packet with hop count as a metric, and as mentioned above, deems the network unreachable if it appears to be over 15 hops away. The maximum hop count of 16 ends the routing loop.

Split Horizon: 

If router A updates two connected routers that network 1 is down, but then accepts a later update from one of those two routers that network 1 is reachable, there may be a loop.
This scenario is possible because one of the connected routers may be getting old information from another part of the network, that was originally sent out by router A itself. Split Horizonprevents this type of loop, when it states that router A cannot receive an update that concerns routes that router A originally advertised. 
A router can also prevent loops by poisoning a route for a network that has gone down. A router can accomplish this by sending out the maximum hop count for a route as soon as it sees the network is unreachable. As mentioned, this process is called route poisoning

Distance Vector protocols typically update only on a set interval. This can cause routing issues if a network goes down, as the router that notices it would have to wait up to 30 seconds to send its next update. 
This problem is avoided with triggered updates. With route poisoning and triggered updates working together, a router overrides its regular schedule and as soon as it notices that the network is down, it sends out the poisoned information straight away.
This doesn't mean that the routers immediately remove the route from the routing table, instead it just means that routers know about the change. 
Routers implement a holddown timer that causes them to wait a set amount of time before actually removing the route from the table.

Routing updates occur every 30 seconds with RIP. If RIP does not receive an update about a particular route for 180 seconds, that route is marked as invalid. RIP waits another 60 seconds (for a total of 240) and if information is still not received about the route, the route is removed from the routing table. These two timers are the Invalid timer, and the flush timer, respectively.
The third type of timer that RIP uses is the holddown timer. Once RIP receives a warning that a route is invalid, it immediately assigns a holddown timer to the route.

If the route comes back up, during the holddown timer being active, the route is still "on probation" and is not fully reinstated until the holddown timer expires. If the holddown timer expires, the flush timer kicks in and removes the route shortly afterwards.

IGRP Is also a distance vector routing protocol, but this one forwards routing updates every 90 seconds, rather than every 30 seconds. IGRP focuses on speed as the main reason to use a particular route. The default metrics used by IGRP are bandwidth and delay, but load and reliability can also be considered.
IGRP can advertise interior, system, and exterior routes.
  • Interior routes are between networks that are connected to a router and that have been divided into subnets.
  • System routes are between networks inside of an autonomous system.
  • Exterior routes define access to networks outside of an autonomous system.
IGRP makes use of hold-down timers, split horizon, and poison reverse.

RIP V2: Rip V2 adds authentication and ability to send a subnet mask with routing updates. This means that RIP V2 supports VLSM and classless inter-domain routing.

Another difference between RIP versions 1 and 2 is in how each protocol sends updates.
RIP V1 broadcasts on RIP V2 more efficiently multicasts on (similar to for EIGRP).

Summary Routes: All routers on the internet cannot possibly contain a route for every network that exists. Routers can learn about other networks through static and dynamic routes, but for traffic destined outside of the immediate network, an administrator can add a default route. A default route provides a destination for a router to forward all packets for which it does not have an entry in its routing table.

Link State Advertisements: Link state protocols actually send little hello messages periodically to obtain information about neighbouring routers. These are seperate and distinct from LSAs, which remain the key way that link state protocols discover information across the entire network.
When a network changes, a router will flood LSAs on a specific multicast address across the specified network area. These LSAs allow the router to create a topological database of the network, to use the Dijkstra algorithm to determine the shortest path for each network, to build the shortest path tree, and to use the resulting tree to build the routing table. Flooding LSAs across a network can
affect overall bandwidth on the network and cause each router to recalculate the full topological database. For this reason, a network using link state protocols must be broken up into small enough areas to maintain network efficiency, and sufficiently powerful routers must be used.

OSPF: Is an open (non-proprietary) link state protocol that allows you to control the flow of updates with areas. OSPF is a good choice for a large network because unlike RIP, it allows more than 15 maximum hops, and networks can be divided into areas.
These areas communicate with a backbone area to reduce routing protocol traffic and routing table size.

OSPF routers do indeed maintain a full loop-free topological database of the network. In addition to this topological database, each OSPF enabled router maintains a unique adjacency database that tracks only neighboring routers.
OSPF routers elect a designated router, and a backup designated router, as central points for routing updates.
VLSM support, A bandwidth based metric, a loop free SPF tree and rapid convergence through LSAs are key features of OSPF.

OSPF adjacency databases are fine if you're - for example - on a lab network that has four routers each connected with point to point connections. Each router will have two adjacencies: One for each directly connected neighbor. If you're using fiber though, (FDDI for example), all routers would technically be connected on the ring to each other, making every router, the neighbour of every other router.
OSPF avoids the situation of never ending neighbours with an election.
Routers that are connected on broadcast multiaccess networks, like fiber or ethernet, OR nonbroadcast multiaccess networks such as frame relay, all elect a single router called the DR - Designated Router - to handle updates.
To avoid a single point of failure, the routers also elect a backup designated router.

OSPF hello packets go out on the multicast address (remember, for EIGRP and for RIPv2).
If the connection is broadcast or point to point, the hellos are sent every 10 seconds.
If the connection is NBMA (like frame relay), the packets are sent every 30 seconds.

The packets contain the following:
  • Version
  • Type
  • Packet Length
  • Router ID
  • Area ID
  • Checksum
  • Authentication Type
  • Authentication Data
 The OSPF process starts with hello packets to find neighbouring routers, so that adjacencies can be developed.
First of all, routers need to establish if they are on a point to point or a multiaccess link. If on a multiaccess link, the DR and BDR election then occurs. Once adjacencies exist between neighbours, the routers then forward LSAs and add the resulting information to their topological databases. Once the topological databases are complete, the routers use the SPF (Shortest Path First) algorithm to create the SPF tree, and then a routing table.
Periodic hello packets can alert routers to a change in the topology that would restart the process.

EIGRP and IGRP routing protocols function together well despite the fact that EIGRP offers multiprotocol support and functions as a hybrid routing protocol. EIGRP also supports VLSM whereas IGRP does not,. A router running only IGRP will see EIGRP routes as IGRP routes.

As a hybrid multiprotocol routing protocol, EIGRP uses functions from both link state and distance vector protocols. Like OSPF, EIGRP collects multiple databases of network information to build a routing table.
EIGRP uses a neighbour table in the same way that OSPF uses an adjacency database to maintain information about adjacent routers.
EIGRP however uses DUAL (Diffusing Update Algorithm) to recalculate a topology.
EIGRP also maintains a topology table that contains routes learned from all configured network protocols. In this table, the following fields are present:
  • Feasible Distance: The lowest cost to each destination.
  • Route Source: The router identification number for externally learned routes.
  • Reported Distance: A neighbouring router's reported distance to a destination. 
  • Interface Information: Which interface is used to reach a destination. 
  • Route Status: The status of a route, where ready to use routes are identified as passive, and routes that are being recalculated are identified as Active. REMEMBER: If it's passive, it's because it doesn't need recalculating and is ready to use/in use. 
The neighbour and topology tables allow EIGRP to use DUAL to identify the best route, or the successor (think "successful) route, and enter it into the routing table. Backup routes, or feasible successors, are kept only in the topology table.
If a network goes down and there is no feasible successor, the router sets the route to active, sends query packets out to neighbours, and begins to rebuild the topology.
In the topology table, EIGRP can also tag routes as external or internal.
Internal routes come from inside the EIGRP AS, and external routes come from other routing protocols, and outside the EIGRP AS.

Advanced features of EIGRP that set it apart from other distance vector routing protocols include:
  • Rapid Convergence: EIGRP uses the DUAL FSM (Flying Spaghetti Monster/Finite State Machine) to develop a full loop free topology of the network, allowing all routers to converge at the same time.
  • Efficient Use of Bandwidth: Like OSPF, EIGRP sends out partial updates and hello packets, but these packets only go to routers that need the information. EIGRP also develops neighbour relationships with other routers.
  • Support for VLSM and CIDR: EIGRP sends the subnet mask information,  allowing the network to be divided beyond default subnet masks.
  • Multiple Network Layer Support: Rather than relying on TCP/IP to send and receive updates, EIGRP uses the reliable transport protocol (RTP) as its own proprietary means of sending updates.
  • Independence from Routed Protocols: EIGRP supports UP, IPX, and AppleTalk. EIGRP has a modular design that uses Protocol Dependent Modules (PDMs) to support other routing (routed, surely?) protocols, so changes to reflect revisions in the other protocols have to be made only to the PDM and not to EIGRP.
EIGRP uses five different types of packets to communicate with other routers:
  • Hello: Sent on to communicate with neighbours.
  • Acknowledgement: Hello packets without any data, sent to acknowledge receipt of a message.
  • Update: Used to update new neighbours so that they in turn can update their topology.
  • Query: Used to gather information from one or many neighbours.
  • Reply: Sent as a response to a query packet.
As described, EIGRP routers build a topology table that uses DUAL to select the successor  routes that will populate the routing table. If a link goes down, DUAL selects a feasible successor from the topology table, and promotes it to the successor route.
If there is no feasible successor, EIGRP recalculates the topology table. This process and DUAL enable EIGRP to achieve rapid convergence.

No comments: