View source for Switches, Routers, Bridges and LANs/Routers/Basics of Routing

{{formatting}}

===What Is Routing?===
Routing is the process of moving information across an internetwork from source to destination. At least one intermediate node must be encountered along the way. Routing and bridging look similar but the primary difference between the two is that bridging occurs at Layer 2 (the link layer) of the OSI reference model, whereas routing occurs at Layer 3 (network layer). One important difference between routing and bridging is that the layer 3 addresses are allocated hierarchically, so it is possible for a router to have a single rule allowing it to route to an entire address range of thousands or millions of addresses. This is an important advantage in dealing with the scale of the internet, where hosts are too numerous (and are added and removed too quickly) for any router to know about all hosts on the internet.

The role of routing the information in network layer is performed by routers. Routers are the heart of the network layer. Now first we look the architecture of the router, processing of datagram in routers and then we will learn about routing algorithms.

===The Architecture of a router===
A router will include the following components:

====Input ports====
Input port performs several functions. The physical layer function is performed by the line termination unit. Protocol decapsulation is performed by data link processing. Input port also performs lookup and forwarding function so that packets are forwarded into the switching fabric of the router emerges at the appropriate output port. Control packets like packets carrying routing protocol information for RIP, OSPF etc. are forwarded to routing processor. Input port also performs input queuing when output line is busy.  

====Output ports====
Output port forwards the packets coming from switching fabric to the corresponding output line. It performs exact reverse physical and data link functionality than the input port. Output port also performs queuing of packets which comes from switching fabric. 

====Routing processor====
Routing processor executes routing protocols. It maintains routing information and forwarding table. It also performs network management functions within the router.

====Switching Fabric====
The job of moving the packets to particular ports is performed by switching fabrics. Switching can be accomplished in number of ways:
* '''Switching via Memory:''' The simplest, easiest routers, with switching between output and input ports being done under direct control of CPU (router processor). Whenever a packet arrives at input port routing processor will come to know about it via interrupt. It then copies the incoming packets from input buffer to processor memory. Processor then extracts the destination address look up from appropriate forwarding table and copies the packet to output port’s buffer. In modern routers the lookup for destination address and the storing (switching) of the packet into the appropriate memory location is performed by processors input line cards.
* '''Switching via Bus:''' Input port transfers packet directly to the output port over a shared bus, without intervention by the routing processor. As the bus is shared only one packet is transferred at a time over the bus. If the bus is busy the incoming packets has to wait in queue. Bandwidth of router is limited by shared bus as every packet must cross the single bus. Examples: Bus switching CISCO-1900, 3-COM’s care builder5.
* '''Switching via Interconnection Networks:''' To overcome the bandwidth problem of a shared bus cross bar switching networks is used. In cross-bar switching networks input and output ports are connected by horizontal and vertical buses. If we have N input ports and N output ports it requires 2N buses to connect them. To transfer a packet from the input port to corresponding output port, the packet travels along the horizontal bus until it intersects with vertical bus which leads to destination port. If vertical is free the packet is transferred. But if vertical bus is busy because of some other input line must be transferring packets to same destination port. The packets are blocked and queued in same input port.

===Processing the IP datagram===
The incoming packets to the input port are stored in queue to wait for processing.  As the processing begins, the IP header is processed first. The error checksum is performed to identify the errors in transmission. If it does not contain error then the destination IP address field is check. If it is for the local host then taking into account the protocol UDP, TCP or ICMP etc. the data field is passed to the corresponding module.

If the destination IP address is not for local host then it will check for the destination IP address in its routing table. Routing table consist of the address of next router to which the packet should be forwarded. Then the output operation are performed on the outgoing packet such as its TTL field must be decrease by one and checksum bits are again calculated and the packet is forwarded to the output port which leads to the corresponding destination. If the output port is busy then packet has to wait in output queue.

Packet scheduler at the output port must choose the packet from the queue for transmission. The selection of packet may be on the basis of First-come-first-serve (FCFS) or priority or waited fair queuing (WFQ), which shares the outgoing link “fairly” among the different end-to-end connections that have packets queued for transmission. For quality-of-service packet scheduling plays very crucial role.
If the incoming datagram contains the routing information then the packet is send to the routing protocol which will modify the routing table entry accordingly.

===Routing Algorithms===
Now we will take into consideration different routing algorithms. There are two types of protocol for transferring information form source to destination.

===Routed vs Routing Protocol===
Routed protocols are used to direct user traffic such as IP or IPX between routers.
Routed packet contains enough information to enable router to direct the traffic.
Routed protocol defines the fields and how to use those fields.

Routed protocols include:

* Internet Protocol 
** Telnet 
** Remote Procedure Call (RPC) 
** SNMP 
** SMTP 
* Novell IPX 
* Open Standards Institute networking protocol 
* DECnet 
* Appletalk 
* Banyan Vines 
* Xerox Network System (XNS) 

Routing protocol allow routers to gather and share the routing information to maintain and update routing table which in turn used  to find the most efficient route to destination.

Routing protocol includes:

* Routing Information Protocol (RIP and RIP II) 
* Open Shortest Path First (OSPF) 
* Intermediate System to Intermediate System (IS-IS) 
* Interior Gateway Routing Protocol (IGRP) 
* Cisco's Enhanced Interior Gateway Routing Protocol (EIGRP) 
* Border Gateway Protocol (BGP)

===Design Goals of Routing Algorithms=== 
Routing algorithms have one or more of the following design goals:

* '''Optimality''': This is the capability of the routing protocol to search and get the best route. Routing metrics are used for finding best router. The number of hops or delay can be used to find the best path. Paths with fewer hops or paths having least delay should be preferred as the best route.
* '''Simplicity and low overhead''': Routing algorithms also are designed to be as simple as possible. The routing algorithm must offer its functionality efficiently, with a minimum of software overhead. Efficiency is particularly important when the software implementing the routing algorithm must run on a computer with limited physical resources, or work with large volumes of routes.
* '''Robustness and stability''': Routing protocol should perform correctly in the face of unusual or unforeseen circumstances, such as hardware failures, high load conditions, and incorrect implementations. This property of routing protocols is known as robustness. The best routing algorithms are often those that have withstood the test of time and that have proven stable under a variety of network conditions.
* '''Rapid convergence''':  Routing algorithms must converge rapidly. Convergence is the process of agreement, by all routers, on optimal routes. In a network when a network event causes routes to either go down or become available or cost of link changes, routers distribute routing update messages which causes the other network routers to recalculate optimal routes and eventually cause other routers in networks to agree on these routes.
* '''Flexibility''': Routing algorithms should also be flexible. They should quickly and accurately adapt to a variety of network circumstances.

===Classification of routing algorithms===
Routing algorithms are mainly are of two types

* '''Static routing:''' In static routing algorithms the route followed by the packet always remains the same. Static routing algorithm is used when routes change very slowly. In this network administrator computes the routing table in advance, the path a packet takes between two destinations is always known precisely, and can be controlled exactly.
**'''Advantages:'''
***Predictability: Because the network administrator computes the routing table in advance, the path a packet takes between two destinations is always known precisely, and can be controlled exactly.
***No overhead on routers or network links: In static routing there is no need for all the routers to send a periodic update containing reachability information, so the overhead on routers or network links is low.
*** Simplicity: Configuration for small networks is easy.
** '''Disadvantages:'''
***Lack of scalability: Computing the static routing for small number of hosts and routers is easy. But for larger networks finding static routes becomes cumbersome and may lead to errors.
***If a network segment moves or is added: To implement the change, you would have to update the configuration for every router on the network. If you miss one, in the best case, segments attached to that router will be unable to reach the moved or added segment. In the worst case, you'll create a routing loop that affects many routers
***It cannot adapt failure in a network: If a link fails on a network using static routing, then even if an alternative link is available that could serve as a backup, the routers won't know to use it.
* '''Dynamic routing:''' Machines can communicate to each other through a routing protocol and build the routing table. The router then forwards the packets to the next hop, which is nearer to the destination. With dynamic routing, routes change more quickly. Periodic updates are send on the network, so that if there is change in link cost then all the routers on the network come to know it and will change there routing table accordingly.
** '''Advantages:'''
***Scalability and adaptability: A dynamically routed network can grow more quickly and grow larger without becoming unmanageable. It is able to adapt to changes in the network topology brought about by this growth.
***Adaptation to failures in a network: In dynamic routing routers learn about the network topology by communicating with other routers. Each router announces its presence. It also announces the routes it has available to the other routers on the network. Because of this if you add a new router, or add an additional segment to an existing router, the other routers will hear about the addition and adjust their routing tables accordingly. 
** '''Disadvantages:'''
***Increase in complexity: In dynamic routing it has to send periodic updates about the communicating information about the topology. The router has to decide exactly what information it must send. When the router comes to know about the network information from other routers it is very difficult to correctly adapt to changes in the network and it must prepare to remove old or unusable routes, which adds to more complexity.
*** Overhead on the lines and routers: Routers periodically send communication information in packets to the other router about the topology of the network. These packets does not contain user information  but only the information necessary for the routers so it is nothing but the extra overhead on the lines and routers.

===Classification of Dynamic Routing Protocols=== 
The first classification is based on where a protocol is intended to be used: between your network and another's network, or within your network: this is the distinction between ''interior'' and ''exterior''. The second classification has to do with the kind of information the protocol carries and the way each router makes its decision about how to fill in its routing table which is link-state vs. distance vector.

===Link State Routing=== 
In a link-state protocol, a router provides information about the topology of the network in its immediate vicinity and does not provide information about destinations it knows how to reach. This information consists of a list of the network segments, or links, to which it is attached, and the state of those links (functioning or not functioning). This information is then broadcasted throughout the network. Every router can build its own picture of the current state of all of the links in the network because of the information broadcast throughout the network. As every router sees the same information, all of these pictures should be the same. From this picture, each router computes its best path to all destinations, and populates its routing table with this information.
Now we will see the link state algorithm known as Dijkstra’s algorithm.

The notation and there meanings are as follows:

* <math>N</math> Denotes set of all nodes in graph.
* <math>l(i,j)</math> is the link cost from node <math>i</math> to node <math>j</math> which are in <math>N</math>. If both nodes are not directly connected, then <math>l(i,j) = \infty</math>. The most general form of the algorithm doesn't require that <math>l(i,j) \neq l(j,i)</math>, but for simplicity we assumed that they are equal.
* <math>s</math> is the node executing the algorithm to find the shortest path to all the other nodes.
* <math>M</math> denotes the set of nodes incorporated so far by the algorithm to find the shortest path to all the other nodes in <math>N</math>.
* <math>C(n)</math> cost of the path from the source node <math>s</math> to destination node <math>n</math>.

====Definition of the Algorithm====
 
In practice each router maintins two lists, known as Tentative and Confirmed. Each of these lists contains a set of entries of the form (Destination, Cost, Nexthop).
 
The algorithm works as follows:

# Initialize the Confirmed list with an entry for myself; this entry has a cost of 0.
# For the node just added to the Confirmed list in the previous step, call it node Next, select its LSP.
# For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach this Neighbor as the sum of the cost from myself to Next and from to Neighbor.                                    
##If Neighbor is currently on neither the Confirmed not the Tentative list, then add (Neighbor, Cost, NextHop) to the Tentative list, where NextHop is the direction I go to reach Next.
##If Neighbor is currently on the  Tentative list, and the Cost is  less than the currently listed cost for Neighbor, then replace the current entry with (Neighbor , Cost, NextHop), where NextHop is the direction I go to reach Next.
# If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative  
list with the lowest cost, move it to the Confirmed list, and return to step 2.

[algorithm from Computer Networks a system approach – Peterson and Davie.] 
 
Now lets look at example :
Consider the Network depicted below.
 
Steps for building routing table for A is as follows:

{|
!Step
!Confirmed
!Tentative
!Comments
|-
|1
|( A,0,-)
|
|Since A is the only new member of the confirmed list, look at its LSP.
|-
|2
|(A,0,-)
|(B,9,B) (C,3,C) (D,8,D)
|A’s LSP says we can reach B through B at cost 9, which is better than anything else on either list, similarly for C and D.
|-
|3
|(A,0,-) (C,3,C)
|(B,9,B) (D,8,D)
|Put lowest-cost member of Tentative (C) onto Confirmed list. Next, examine LSP of newly confirmed member (C)
|-
|4
|(A,0,-) (C,3,C)
|(D,4,C)
|Cost to reach E through C is 4, so replace (B, infinity,-).
|-
|5
|(A,0,-) (C,3,C) (D,4,C)
|(B,6,E) (D,6,E)
|Cost to reach B through E is 6, so replace (B, 9, B).
|-
|6
|(A,0,-) (C,3,C) (D,4,C) (B,6,E)
|
|The only node remains is D perform the steps 2 to 6 again and we will get distance of D from A through E is 6 by following algorithm. So next iteration add (D,6,E) 
|-
|7
|(A,0,-) (C,3,C) (D,4,C) (B,6,E) (D,6,E)
|
|We are done. Now shortest path to all the destinations are know.
|}

====Distance vector routing====
Distance vector algorithm is iterative, asynchronous, and distributed. In distance vector each node receives some information from one or more of its directly attached neighbors. It then performs some calculation and may then distribute the result of calculation to its neighbors. Hence it is distributive. It is interactive because this process of exchanging information continues until no more information is exchanged between the neighbors.

Let <math>dx(y)</math> be the cost of the least-cost path from node <math>x</math> to node y. The least cost are related by Bellman-Ford equation:

<math>Dx(y) = \min v \left \{ C(x, V) + dv(y) \right \}</math>

where min v in the equation is taken over all of x’s neighbors. After traveling from x to v , then we take the shortest path from v to y, the shortest path from x to y will be C(x, V) + dv(y). As we begin to travel to some neighbor v, the least cost from x to y is minimum of  C(x, V) + dv(y) taken over all neighbours v.

In distance vector algorithm each node x maintains routing data. It should maintain :

# The cost of each link attached to neighbors i.e. for attach node v it should know C(x,v).
# It also maintains its routing table which is nothing but the x’s estimate of its cost to all destinations, y, in N.
# It also maintains distance vectors of each of its neighbors. i.e. Dv = [Dv(y): y in N]

In distributed , asynchronous algorithm  each node sends a copy of distance vector time to time from each of the neighbors. When a node x receives a its neighbors distance vector then it saves it and update its distance vector as:

<math>Dx(y) = \min v \left \{ C(x,v) + Dv(y) \right \} \text{for each node } y \text{ in } N</math>

when node update its distance vector then it will send it to its neighbors. The neighbor performs the same actions this process continues until there is no information to send for each node.

Distance vector algorithm [ from kurose] is as follows : 

At each node , x :  
		
Lets consider the example: the network topology is given as 
 
Now we will look at the steps for building the router table for R8
after step 1:
after step 2:
after step 3:
and it is the solution. For node R8 now the routing table contains.

{|
!Destination
!Next hop
!Cost to
|-
|R1
|R5
|5
|-
|R2
|R5
|4
|-
|R3
|R3
|4
|-
|R4
|R5
|5
|-
|R5
|R5
|2
|-
|R6
|R6
|2
|-
|R7
|R7
|3
|}

===Count-to-infinity problem:=== 
“In the network bad news travels slowly”. 
Consider R1, R2, R3 and R4 are the four routers connected in a following way.
   
The routing information of the routers to go from them to router R4 is 
R1	R2	R3
3, R2	2, R3	1, R4
Suppose R4 is failed.  Then as there is no direct path between R3 and R4 it makes its distance to infinity. But in next data exchange R3 recognize that R2 has a path to R4 with hop 2 so it will update its entry from infinity to 2 + 1 = 3 i.e. (3,R3). 
In the second data exchange R2 come to know that both R1 and  R2 goes to R4 with a distance of 3 so it updates its entry for R4 as 3 + 1 = 4 i.e. (4, R3).
In the third the data exchange the router R1 will change its entry to 4 + 1 = 5 ie ( 5, R2).
This process will continue to increase the distance. The summary to this is given in following table.

{|
!Exchange
!R1
!R2
!R3
|-
|0
|3, R2
|2, R3
|1, R4
|-
|1
|3, R2
|2, R3
|3, R3
|-
|2
|3, R2
|4, R3
|3, R3
|-
|3
|5, R2
|4, R3
|5, R3
|-
|colspan="4"|.. Count to infinity ...
|}

===Solutions of count-to-infinity problem:===
;Defining the maximum count
:For example, define the maximum count as 16 in RFC 1058 [2]. This means that if all else fails the counting to infinity stops at the 16th iteration. 
;Split Horizon:
:Use of Split Horizon.. Split Horizon means that if node A has learned a route to node C through node B, then node A does not send the distance vector of C to node B during a routing update.
;Poisoned Reverse:
:Poisoned Reverse is an additional technique to be used with Split Horizon. Split Horizon is modified so that instead of not sending the routing data, the node sends the data but puts the cost of the link to infinity. Split horizon with poisoned reserve prevents routing loops involving only two routers. For loops involving more routers on the same link, split horizon with poisoned reverse will not suffice.

{{BookCat}}