Mumbai University > Electronics and Telecommunication > Sem 6 > Computer Communication and Telecom Network

Marks: 10M

Year: May 2015

Routing protocols can be classified into different groups according to their characteristics. Specifically, routing protocols can be classified by their,

• Purpose: Interior Gateway Protocol (IGP) or Exterior Gateway Protocol (EGP)
• Operation: Distance vector protocol, link-state protocol, or path-vector protocol
• Behavior: Classful (legacy) or classless protocol

For example, IPv4 routing protocols are classified as follows:

• RIPv1 (legacy): IGP, distance vector, classful protocol
• IGRP (legacy): IGP, distance vector, classful protocol developed by Cisco (deprecated from 12.2 IOS and later)
• RIPv2: IGP, distance vector, classless protocol
• EIGRP: IGP, distance vector, classless protocol developed by Cisco
• OSPF: IGP, link-state, classless protocol
• IS-IS: IGP, link-state, classless protocol
• BGP: EGP, path-vector, classless protocol

Link State Routing:

i. Link state routing has a different philosophy from that of distance vector routing. In link state routing, if each node in the domain has the entire topology of the domain the list of nodes and links, how they are connected including the type, cost (metric), and the condition of the links (up or down) the node can use the Dijkstra algorithm to build a routing table. Figure 2 shows the concept.

ii. The topology must be dynamic, representing the latest situation of each node and each link. If there are changes in any point in the network (a link is down, for example), the topology must be updated for each node.

Building Routing Tables:

In link state routing, four sets of actions are required to ensure that each node has the routing table showing the least-cost node to every other node.

1. Creation of the states of the links by each node, called the link state packet or LSP.
2. Dissemination of LSPs to every other router, called flooding, in an efficient and reliable way.
3. Formation of a shortest path tree for each node.
4. Calculation of a routing table based on the shortest path tree.

Distance Vector Routing Algorithm:

1. In distance vector routing, the cost is normally hop counts (how many networks are passed before reaching the destination). So the cost between any two neighbors is set to 1.
2. Each router needs to update its routing table asynchronously, whenever it has received some information from its neighbors. In other words, each router executes part of the whole algorithm in the Bellman-Ford algorithm. Processing is distributive.
3. After a router has updated its routing table, it should send the result to its neighbors so that they can also update their routing table.
4. Each router should keep at least three pieces of information for each route: destination network, the cost, and the next hop. We refer to the whole routing table as Table, to the row i in the table as Tablei, to the three columns in row i as Tablei.dest, Tablei.cost, and Tablei.next.
5. We refer to information about each route received from a neighbor as R (record), which has only two pieces of information: R.dest and R.cost. The next hop is not included in the received record because it is the source address of the sender. Table1 shows the algorithm in pseudocode.

Table1: Distance Vector Algorithm Used by Each Router

Lines 23 to 47 give the details of updating process. When a record arrives, the router searches for the destination address in the routing table.

1. If the corresponding entry is found, two cases need to be checked and the route information should be changed.

   a. If the record cost plus 1 is smaller than the corresponding cost in the table, it means the neighbors have found a better route to that destination. .

   b. If the next hop is the same, it means some change has happened in some part of the network. For example, suppose a neighbor has previously advertised a route to a destination with cost 3, but now there is no path between this neighbor and that destination. The neighbor advertises this destination with cost value infinity.

   The receiving router must not ignore this value even though its old entry is smaller. The old route does not exist anymore.

2. If the entry is not in the table, the router adds it to the table and sorts the table according to the destination address.

Example: Figure 3 shows the initial routing table for an AS. The figure does not mean that all routing tables have been created at the same time; each router creates its own routing table when it is booted.