CCNP Enterprise Core (350-401) Cisco Routing

Link State Algorithms

A link state algorithm advertises the link state and link metric for each of the connected links and directly connected routers to every router in the network.

OSPF and IS-IS are two link state routing protocols commonly used in enterprise and service provider networks.

Advertisements sent by OSPF are known as link-state advertisements, or LSAs. Advertisements sent by IS-IS are known as link-state packets or LSPs.

When a router receives an advertisement from a neighbour, the information is stored in a local database called the link state database. The link state information is passed on to each of the neighbouring routers of the local router in the same way that is was received – flooding through the network. The end result of this information flood is all routers in the network will have a synchronised and identical map of the network topology.

With the complete network topology, every router can run the Dijkstra shortest path first (SPF) algorithm calculation to determine the best shortest loop-free path. The routing table can be populated with this information.

In comparison to distance vector protocols, a link state protocol can consume much more CPU cycles and memory due to having a complete map of the network. The detailed map of the network works in the networks favour however with a reduced risk of routing loops and better network path decisions based on other factors rather than ‘hop count’.

Link state protocols are easily equipped with additional abilities, such as opaque LSAs for OSPF and TVLs (type/length/value) for IS-IS that allow features commonly used by service providers such as MPLS traffic engineering.

CCNP Enterprise Core (350-401) Cisco Routing

Enhanced Distance Vector Algorithms

Diffusing Update Algorithm, or DUAL, is an enhanced distance vector algorithm. EIGRP uses it to calculate the shortest path to a destination within a network.

Whilst EIGRP acts in a similar way to advertising its networks as other distance vector protocols do, there are some enhancements:

  • Rapid convergence time when the network topology changes
  • Updates are only sent when there is a change in the network. Full updates are not sent periodically as other distance vector protocols do.
  • Hellos and neighbour relationships are formed in the same way as link state protocols.
  • Factors other than hop count are taken into consideration, such as
    • Bandwidth
    • Delay
    • Reliability
    • Load
    • Maximum Transmission Unit (MTU) setting
  • There is an option to load balance across equal or unequal cost paths.

With this additional link-state style features on top of being a distance vector protocol, EIGRP can be referred to as a hybrid routing protocol since it can refer on other vectors that just simply hop-count.

On EIGRPs default setting, EIGRP just advertises the total path delay and minimum bandwidth for a route to every neighbour. Each neighbour can perform calculations to determine the best path based on information collected from its directly attached neighbours.

CCNP Enterprise Core (350-401) Routing

Distance Vector Algorithms

Routing protocols such as RIP advertise routes as vectors, where distance is the cost measured in network hops.

When the router receives routing information from a neighbour, it will store it in a local routing database when received. Distance vector algorithms such as the Bellman-Ford and Ford-Fulkerson algorithms are used to determined which paths are the best loop free paths to reachable destinations. Once the best paths have been determined they are installed into the routers routing table and advertised to neighbouring routers.

Routers utilising distance vector protocols advertise their routing information to their neighbours from their own perspective, not from where the original route was received. This means that the router does not have a complete map of the entire network topology, rather just how to reach a network via a nearby destination router and how far away it is.

This incomplete topology brings the advantage that overheads with running a distance vector protocol can be low in terms of CPU usage and memory.

It is important to note that distance vector protocols take no notice of link speeds and congestion, just purely the hop counts to reach the destination. One slow link will be favoured over 2 fast ones.

CCNP Enterprise Core (350-401) Routing

Overview of Routing Protocols

The routers main function is to move an IP packet from one network to another.

The router learns of these networks through a direct connection to them, being statically configured to know of them but a network administrator, and learned automatically through dynamic routing protocols.

There a number of common routing protocols used across LANs and the Internet:

RIPv2 – Routing Information Protocol Version 2

EIGRP – Enhanced Interior Gateway Routing

OSPF – Open Shortest Path First

IS-IS – Intermediate System to Intermediate System

BGP – Border Gateway Protocol

With the exception of BGP, all of the protocols are designed for use in an internally owned network and are known as Interior Gateway Protocols, or IGPs.

Exterior Gateway Protocols such as BGP can route between different organisational networks or autonomous systems.

Whilst BGP is an Exterior Gateway Protocol it can be used as an IGP, known as interior BGP or iBGP.