An Introduction to Routing

Easiest possible definition to routing is, process of finding a path to a destination address.

(you are invited to make a more dumb attempt to define routing).

Now, let us start digging deeper, there could be two ways for a data packet to reach from one source computer to a destination computer; either a direct or an indirect delivery mechanism.

Direct vs Indirect Delivery

Direct delivery is performed by the source computer on its own, if destination computer network is the same as source computer network. Source computer determines the destination network by applying its own ip subnet mask to destination IP address. If destination network is same then source host uses ARP to determine L2 address for actual delivery. ARP cache for L2 addresses is also maintained in the host computer for a limited interval.

Indirect delivery is performed through router (one or a series of routers), this method is used when the destination computer network is not the same as source computer network. Data packet is first handled to a default gateway, which subsequently handles the packet routing.

Default gateway delivers packet using a routing table. A typical routing table contains following components:

• Destination network with its subnet mask
• Next Hop address including outgoing interface
• Metric and administrative distance  

This default gateway may be a linux machine with multiple NICs or may be any purpose built hardware router like a cisco or Juniper box.

Next stop in this routing basics tour is difference between static and dynamic routing.

Static Routing vs Dynamic Routing

Static routing entriies are configured manually, which overide routes learned via dynamic routing protocols. Static routing is normally employed if only very low bandwidth links are available and/or explicit administrative control is needed over the link and/or link is only path to a stub network and/or router has very limited resources and cannot run a dynamic routing protocol.

Another typical scenario for static routes could be a router of last resort (a router to which all unroutable packets are sent), it may be configured using a routing table entry like "0.0.0.0 0.0.0.0". This helps in achieving smaller routing tables (a highly desired characteristic).

Cisco Only! In most hub-and-spoke topologies while working on all cisco network using On Demand Routing (odr) is a simple routing method.  

Dynamic routing protocols are used to learn dynamic routing entries in a routing table. These routing protocols adapt dynamically to network topology changes. More than one routing protocols may be employed on a router to create routing table.

Metric

A routing protocol typically find out more than one route to a destination. Metric is used by a single routing protocol to determine which route to include in the routing table when it has two available routes to the same destination. The router will include the route with the smallest metric because it considers this route to be the shortest, therefore best.
Common metric values include Hop count, cost (recipocal value of bandwidth), load, reliability, delay and MTU.

Administrative Distance

A router may be employing several routing protocols at the same time. Multiple routing protocols may independently find out different routes to same destination, then which route to choose? , answer administrative distance.
It is the feature that routers use in order to select the best path when there are two or more different routes to the same destination from two different routing protocols.
Administrative distance defines the reliability of a routing protocol. Smaller the AD, more trust worthy a routing protocol. Routing protocols have default values for AD, however these can be changed.
Default values of AD in isco IOS are as under:

One notable difference between Cisco IOS to UNIX forwarding tables is that in IOS static routes differ from each other in terms of administrative distance. Each static route can be given a different administrative distance. This way it is possible to configure fall back routes.

Next stop, in this routing basic tour is classification of routing protocols:

Classification of Dynamic Routing Protocols

• Depending on age; could be classful (no subnet masks) and classless(VLSM/CIDR supported)
• Depending on scope; Interior Gateway Protocol (IGP) working inside an autonomous system and Exterior Gateway Protocol (EGP) working between autonomous systems
• Depending on algoritham used; distance vector using signpost principle and link state employing roadmap principle

Distant Vector (Signpost Principle, Bellman-Ford algo)

• Distant vector protocols include RIP, RIPv2 and Cisco proprietry IGRP.
• Each router knows only about directly attached networks.
• Routing table is sent periodically to all neighbour routers.
• Received updates are examined, changes are adopted in own routing table.
• Hop count is used as metric.
• Topology behind next hop is not known. (Signpost principle)
• Loops can occur; which are mitigated using additional mechanisms, like, max hop count, split horizon (with poison reverse), triggered update and hold down timers.

Loop avoidance in Distant Vector Protocols

Following modifications to the distance vector protocol have been developed in an attempt to reduce the chance of routing loops:

• Split horizon prevents loops between adjacent routers, by never advertising a route out of the interface through which router learned it.
• Poison reverse prevents larger loops. Once a router learns a route through an interface, it advertises it as unreachable back through that same interface.
• Holddown timer prevents incorrect route information from entering routing tables. After a route is advertised as down, router do not listen to routing updates on that route for a specific period of time.

Link State Protocols (Roadmap principle, Dijkistra Algorithm)

• Examples of link state include OSPF and IS-IS.
• Each two neighboured routers establish adjacencies and learn real network topology information through "link state advertisements" (LSA).
• LSA are stored in link state database (LSDB).
• Updates are issued only upon topolgy changes, which is propogated through flooding.
• Routing table entries are calculated by applying the shortest path first (SPF) algorithm on the LSDB.
• It is a loop safe algorithm, where alternative paths are immediately known after topolgy change as topology chages are broadcasted to all routers (in a defined area) as soon as they happen.
• Large networks are usually split in to areas.
• Link state protocols are CPU and memory intensive.

Final words, Routing is the art of finding the best way to a given destination. Feat can be performed either statically or dynamically. Static means network administrator defines the way packets are moving, while in dynamic routing, a routing protocol is trying to find the best way to a given destination.