Routing Protocols

Link State (LS) Algorithm

• Every router performs these steps:
  1. Identify physically connected routers and get their IP addresses:
     • Routers send "HELLO" packets upon starting.
     • Receiving routers reply with their IP addresses.
  2. Measure delay time (or other parameters like average traffic) for neighbor routers:
     • Routers send echo packets and measure round trip time (RTT).
     • Delay time is estimated by dividing RTT by 2 (includes transmission and processing times).
  3. Broadcast information over the network and receive information from other routers:
     • Routers share knowledge of network structure and status.
  4. Identify the best route between two nodes:
     • Routers use algorithms like Dijkstra's shortest path algorithm.
     • Routers build a graph showing router locations and links.
     • Links are labeled with a weight/cost (function of delay time, average traffic, or hop count).
     • The link with the lowest weight is chosen.

Dijkstra's Algorithm

• Computes the least-cost path from a source node (A) to all other nodes.

• Iterative; after the kth iteration, the least-cost paths to k destination nodes are known.

• Notation:

  • $c(i,j)$: Link cost from node i to node j. If i and j are not directly connected, $c(i,j) = \infty$. Assumes $c(i,j) = c(j,i)$.
  • $D(v)$: Cost of the path from the source node to destination v with the least cost (as of the current iteration).
  • $p(v)$: Previous node (neighbor of v) along the current least-cost path from source to v.
  • $N$: Set of nodes whose shortest path from the source is definitively known.

• Algorithm Steps:

  1. Initialization:
     • $N = {A}$
     • For all nodes v:
       • If v is adjacent to A, then $D(v) = c(A,v)$
       • Else $D(v) = \infty$
  2. Loop:
     • Find w not in N such that D(w) is a minimum.
     • Add w to N.
     • Update D(v) for all v adjacent to w and not in N:
       • $D(v) = min( D(v), D(w) + c(w,v) )$
  3. Repeat until all nodes are in N.

Link State Routing

• Each router shares knowledge of its neighborhood with every other router in the internetwork.

• Three keys:

  • Knowledge about the neighborhood: Routers send information about their directly attached links (identities and costs).
  • Flooding: Each router sends information to every other router (except neighbors). Every router receiving sends copies to all its neighbors, ensuring all receive the information.
  • Information sharing: Routers only send information when changes occur.

• Two phases:

  • Reliable Flooding:
    • Initial state: Each node knows the cost to its neighbors.
    • Final state: Each node knows the entire graph.
  • Route Calculation: Each node uses Dijkstra's algorithm to calculate optimal routes to all nodes.

Dijkstra's Algorithm Details

• Link-state routing algorithm, finds the shortest path from one node to every other node in the network.
• Iterative: The least-cost paths are well known for k destination nodes after kth iteration.
• Notations:
  • $c(i, j)$: Link cost from node i to node j. If i and j are not directly linked, then $c(i, j) = \infty$.
  • $D(v)$: Cost of the path from source to destination v that has the least cost currently.
  • $P(v)$: Previous node (neighbor of v) along with the current least cost path from source to v.
  • $N$: Total number of nodes available in the network.

Link State Algorithm - Example Walkthrough

• Network topology includes nodes A, B, C, D, E, F with link costs.
• Step 1: Initialization
  • Known least cost paths from A to directly attached neighbors B, C, D are 2, 5, 1 respectively.
  • Cost from A to E and F is set to infinity as they are not directly linked to A.
• Step 2:
  • Vertex D has the least cost path in step 1 and is added to N.
  • Determine the least-cost path through D vertex.
    • Calculating shortest path from A to B:
      • $v = B, w = D$
      • $D(B) = min( D(B) , D(D) + c(D,B) )$
      • $= min( 2, 1+2)$
      • $= min( 2, 3)$
      • The minimum value is 2. Therefore, the currently shortest path from A to B is 2.
    • Calculating shortest path from A to C:
      • $v = C, w = D$
      • $D(B) = min( D(C) , D(D) + c(D,C) )$
      • $= min( 5, 1+3)$
      • $= min( 5, 4)$
      • The minimum value is 4. Therefore, the currently shortest path from A to C is 4.
    • Calculating shortest path from A to E:
      • $v = E, w = D$
      • $D(B) = min( D(E) , D(D) + c(D,E) )$
      • $= min( \infty, 1+1)$
      • $= min(\infty, 2)$
      • The minimum value is 2. Therefore, the currently shortest path from A to E is 2.
• Step 3:
  • E and B have the least cost path in step 2. Consider the E vertex and determine the least cost path of remaining vertices through E.

Distance Vector Routing Algorithm

• Iterative, asynchronous, and distributed.

  • Distributed: Each node receives information from neighbors, calculates, and distributes the result back to neighbors.
  • Iterative: Continues until no more information exchange between neighbors.
  • Asynchronous: Nodes do not operate in lock step.

• Dynamic algorithm.

• Used in ARPANET and RIP.

• Each router maintains a distance table (Vector).

• Three Keys:

  • Knowledge about the whole network: Each router shares its knowledge through the entire network. The Router sends its collected knowledge about the network to its neighbors.
  • Routing only to neighbors: The router sends its knowledge about the network to only those routers which have direct links. The router sends whatever it has about the network through the ports. The information is received by the router and uses the information to update its own routing table.
  • Information sharing at regular intervals: Within 30 seconds, the router sends the information to the neighboring routers.

• Let $dx(y)$ be the cost of the least-cost path from node x to node y. Related by Bellman-Ford equation.

• Bellman-Ford Equation:

  • $dx(y) = minv{c(x,v) + dv(y)}$

  • minv is the equation taken for all x neighbors.

  • Cost after traveling from x to v, considering least-cost path from v to y: $c(x,v)+dv(y)$.

  • Least cost from x to y is the minimum of $c(x,v)+dv(y)$ taken over all neighbors.

• Node x contains the following routing information:

  • For each neighbor v, the cost $c(x,v)$ is the path cost from x to directly attached neighbor, v.
  • The distance vector x, i.e., $Dx = [ Dx(y) : y in N ]$, containing its cost to all destinations, y, in N.
  • The distance vector of each of its neighbors, i.e., $Dv = [ Dv(y) : y in N ]$ for each neighbor v of x.

• Distance vector routing is an asynchronous algorithm.

• Node x sends a copy of its distance vector to all its neighbors.

• When node x receives a new distance vector from one of its neighboring vector, v, it saves the distance vector of v and uses the Bellman-Ford equation to update its own distance vector. The equation is given below:

• 
  dx(y) = minv{ c(x,v) + dv(y)}
  

  for each node y in N

• The node x has updated its own distance vector table by using the above equation and sends its updated table to all its neighbors so that they can update their own distance vectors

• Algorithm:

• At each node x,

  • Initialization
    • for all destinations y in N:
      • $Dx(y) = c(x,y)$ If y is not a neighbor then $c(x,y) = \infty$
    • for each neighbor w
      • $Dw(y) = ?$ for all destination y in N.
    • for each neighbor w
      • send distance vector $Dx = [ Dx(y) : y in N ]$ to w
  • loop
    • wait(until I receive any distance vector from some neighbor w)
    • for each y in N:
      • $Dx(y) = minv{c(x,v)+Dv(y)}$
    • If Dx(y) is changed for any destination y
      • Send distance vector $Dx = [ Dx(y) : y in N ]$ to all neighbors
  • forever

Distance Vector Routing Algorithm

• Distance vector routing algorithm simplifies the routing process by assuming the cost of every link is one unit.
• Therefore, the efficiency of transmission can be measured by the number of links to reach the destination.
• In Distance vector routing, the cost is based on hop count

Distance Vector Routing Algorithm

• The router sends the knowledge to the immediate neighbors.
• The neighbors add this knowledge to their own knowledge and sends the updated table to their own neighbors.
• In this way, routers get its own information plus the new information about the neighbors.
• Initially, the routing table is created for each router that contains at least three types of information such as Network ID, the cost and the next hop.

Distance Vector Routing Algorithm

• NET ID: The Network ID defines the final destination of the packet.

• Cost: The cost is the number of hops that packet must take to get there.

• Next hop: It is the router to which the packet must be delivered.

• The router sends its knowledge to the immediate neighbors.

• The neighbors add this knowledge to their own knowledge and sends the updated table to their own neighbors.

• In this way, routers get its own information plus the new information about the neighbors.

Distance Vector Routing Algorithm - Updating the Table

• When A receives a routing table from B, then it uses its information to update the table.
• The routing table of B shows how the packets can move to the networks 1 and 4.
• The B is a neighbor to the A router, the packets from A to B can reach in one hop. So, 1 is added to all the costs given in the B's table and the sum will be the cost to reach a particular network.
• Process of creating the routing table continues for all routers.
• Every router receives the information from the neighbors, and update the routing table.

Routing Information Protocol(RIP)

• Routers need to determine the best output port to reach a destination address by consulting a forwarding table.

• Routing algorithms are required to build routing tables.

• The routing problem involves finding the lowest-cost path between nodes.

  • Where the cost of a path is the sum of the costs of all edges that make up the path.

• Routing is achieved by running routing protocols among the nodes.

• The protocols provide a distributed, dynamic way to solve the problem of finding the lowest-cost path in the presence of link and node failures and changing edge costs.

• Distance-vector algorithm

• Each node constructs a vector containing the distances/(costs) to all other nodes and distributes that vector to its immediate neighbors.

• RIP is the canonical example of a routing protocol built on the distance-vector algorithm.

• Routers running RIP send their advertisements regularly (e.g., every 30 seconds).

• A router also sends an update message whenever a triggered update from another router causes it to change its routing table.

Routing Information Protocol(RIP)

• Packets may pass through several networks on their way to destination

• Each network carries a price tag, or a metric Metric of a network:

• constant (i.e., each network costs one hop).

• service type-dependent.

• Policy-dependent- a policy defines what paths should, or should not, be followed The router uses a "routing table".

• Static vs. Dynamic routing tables.

• Some of the most notable RIPv2 enhancements are:

  • Next hop.
  • Network mask.
  • Authentication.
  • RIP tag field.

Routing Information Protocol(RIP)

• A router running RIP will send updates to its neighbors, thus allowing the convergence to a known topology.
• In each update, the distance of any given router will be broadcast to its neighbor.
• RIP classifies routers as active and passive (silent).
• Active routers advertise their routes (reachability information) to others.
• Passive routers listen and update their routes based on advertisements but do not advertise.
• Typically, routers run RIP in active mode, while hosts use passive mode.
  Timers
• Periodic Timer (25 < random < 35): Controls advertising of update messages: One Timer
• Expiration Timer: governs route validity: Reset upon receipt of an update: Destination is considered unreachable if expires: If entry is not removed from the table it continues to be advertised with the hop count = 16
• Garbage Collection Timer: Reset to 120sec when a route is invalidated.
  • If it expires, the route entry is completely removed from routing table

Routing Information Protocol(RIP)

• Receive: a response RIP message
  • Add one to the hop count for each advertised destination: Repeat for each advertised destination

Open Shortest Path First (OSPF)

• OSPF is defined in RFC 2328 which is an interior Gateway Protocol used to distribute routing information within an AS (Autonomous System).
• Among all the three chosen samples, OSPF is the most widely used routing protocol in large enterprise networks.
• OSPF is based on link-state technology by using SPF algorithm which calculates the shortest path.

SPF calculation

• Requires all routers in the network to know about all the other routers in the same network and the links among them.
• Calculate the shortest path between each single router. For all the routers they exchange link-states which would be stored in the link-state database.
• Every time a router receives a link-state update, the information stores into the database and this router propagate the updated information to all the other routers.

Open Shortest Path First (OSPF)

• Links database for the above model is: [A, B, 3], [A, C, 6], [B, A, 3], [B, D, 3], [B, E, 5], [C, A, 6], [C, D, 9], [D, C, 9], [D, B, 3], [D, E, 3] , [E, B, 5] and [E, D, 3].
• Each term is referred to the originating router, the router connected to and the cost of the link between the two routers.
• Once the database of each router is finished, the router determines the Shortest Path Tree to all the destinations.

Open Shortest Path First (OSPF)

• Dijkstra Shortest Path First is then running to determine the shortest path from a specific router to all the other routers in the network.
• Each router is put at the root of the Shortest Path Tree and then the shortest path to each destination is calculated. The accumulated cost to reach the destination would be the shortest path.

Open Shortest Path First (OSPF)

• The cost (metric) of OSPF is the cost of sending packets across a certain interface.
• If the bandwidth is wider, the cost would be lower.
• When the Shortest Path Tree is completed, the router will work on the routing table.

Open Shortest Path First (OSPF)

• In OSPF protocol, an Autonomous System can be divided into sections. A section and a nearby router can dorm an AREA.
• Since each section calculate the Shortest Path using the same algorithm as above, each section has its own database and path tree and the information are invisible outside this section.

OSPF Design Characteristics

• OSPF adheres to the following Link State characteristics:
• OSPF employs a hierarchical network design using Areas.
• OSPF will form neighbor relationships with adjacent routers in the same Area.
• Instead of advertising the distance to connected networks, OSPF advertises the status of directly connected links using Link-State Advertisements (LSAs).
• OSPF sends updates (LSAs) when there is a change to one of its links and will only send the change in the update. LSAs are additionally refreshed every 30 minutes.
• OSPF traffic is multicast either to address 224.0.0.5 (all OSPF routers) or 224.0.0.6 (all Designated Routers).
• OSPF uses the Dijkstra Shortest Path First algorithm to determine the shortest path.
• OSPF is a classless protocol and thus supports VLSMs.

OSPF Characteristics

• OSPF supports only IP routing.
• OSPF routes have an administrative distance is 110.
• OSPF uses cost as its metric, which is computed based on the bandwidth of the link.
• OSPF has no hop-count limit.
• The OSPF process builds and maintains three separate tables:

OSPF Tables

• A neighbor table contains a list of all neighboring routers.
• A topology table contains a list of all possible routes to all known networks within an area.
• A routing table contains the best route for each known network.

OSPF Neighbors

• OSPF forms neighbor relationships, called adjacencies, with other routers in the same Area by exchanging Hello packets to multicast address 224.0.0.5.
• Only after an adjacency is formed can routers share routing information.
• Each OSPF router is identified by a unique Router ID. The Router ID can be determined in one of three ways:
  • The Router ID can be manually specified.
  • If not manually specified, the highest IP address configured on any Loopback interface on the router will become the Router ID.
  • If no loopback interface exists, the highest IP address configured on any Physical interface will become the Router ID.
  • loopback is use for testing purpose its a cisco catalyst the loopback address is 127.0.0.0. its like duplicate address we need to ping particular network.

OSPF Timers

• By default, Hello packets are sent out OSPF-enabled interfaces every 10 seconds for broadcast and point-to-point interfaces, and 30 seconds for non- broadcast and point-to-multipoint interfaces.
• OSPF also has a Dead Interval, which indicates how long a router will wait without hearing any hellos before announcing a neighbor as “down.”
• Default for the Dead Interval is 40 seconds for broadcast and point-to- point interfaces, and 120 seconds for non-broadcast and point-to-multipoint interfaces
• Notice that, by default, the dead interval timer is four times the Hello interval.

Popular Routing Protocol Classes

• Interior
  • RIP
  • OSPF
• Exterior
  • BGP

Inter-AS Routing: BGP

• BGP provides each AS a means to:
  • Obtain subnet reachability information from neighboring ASs.
  • Propagate the reachability information to all routers internal to the AS.
  • Determine “good” routes to subnets based on the reachability information and on AS policy.

BGP

• BGP allows each subnet to advertise its existence to the rest of the Internet.
  Sessions
• In BGP, pairs of routers exchange routing information over semipermanent TCP connections using port 179

BGP Basics

• There are also semi permanent BGP/TCP connections between routers within an AS.
• For each TCP connection, the two routers at the end of the connection are called BGP peers, and the TCP connection along with all the BGP messages sent over the connection is called a BGPsession.
• A BGP session that spans two ASs is called an external BGP (eBGP) session, and a BGP session between routers in the same AS is called an internal BGP (iBGP) session.

BGP Distribution

• BGP allows each AS to learn which destinations are reachable via its neighboring ASs.
• In BGP, destinations are not hosts but instead are prefixes, with each prefix representing a subnet or a collection of subnets.
• suppose there are four subnets attached to AS2: 138.16.64/24, 138.16.65/24, 138.16.66/24, and 138.16.67/24.
  Then AS2 could aggregate the prefixes for these four subnets and use BGP to advertise the single prefix to 138.16.64/22 to AS1.

BGP and distribution

• Distribute prefix reachability information over the BGP sessions. using the eBGP session between the gateway routers 3a and 1c, AS3 sends AS1 the list of prefixes that are reachable from AS3; and AS1 sends AS3 the list of prefixes that are reachable from AS1.
• AS1 and AS2 exchange prefix reachability information through their gateway routers 1b and 2a.

Prefix Distribution

• Also as you may expect, when a gateway router (in any AS) receives eBGP-learned prefixes, the gateway router uses its iBGP sessions to distribute the prefixes to the other routers in the AS.
• Thus, all the routers in AS1 learn about AS3 prefixes, including the gateway router 1b. The gateway router 1b (in AS1) can therefore re-advertise AS3’s prefixes to AS2. When a router (gateway or not) learns about a new prefix, it creates an entry for the prefix in its forwarding table.

Path Attributes and BGP Routes

• In BGP, an autonomous system is identified by its globally unique autonomous system number (ASN) [RFC 1930]. When a router advertises a prefix across a BGP session, it includes with the prefix a number of BGP attributes. In BGP jargon, a prefix along with its attributes is called a route Then BGP peers advertise routes to each other. Two of the more important attributes are AS-PATH and NEXT-HOP:
  • AS-PATH This attribute contains the ASs through which the advertisement for the prefix has passed. When a prefix is passed into an AS, the AS adds its ASN to the AS PATH attribute.

Path Attributes and BGP Routes

• Providing the critical link between the inter-AS and intra-AS routing protocols, the NEXT-HOP attribute has a subtle but important use. The NEXT-HOP is the router interface that begins the AS-PATH To gain insight into this attribute.
• Consider what happens when router 1d learns about this route from iBGP.
  After learning about this route to x, router 1d may want to forward packets to x along the route, where l is its interface that begins the least-cost path from 1d towards the gateway router 1c To determine l, 1d provides the IP address in the NEXT-HOP attribute to its intra-AS routing module.

Path Attributes and BGP Routes

• The intra-AS routing algorithm has determined the least-cost path to all subnets attached to the routers in AS1, including to the subnet for the link between 1c and 3a. From this least-cost path from 1d to the 1c-3a subnet, 1d determines its router interface l that begins this path and then adds the entry (x,l) to its forwarding table.
• Also Includes attributes that allow routers to assign preference metrics to the routes, and an attribute that indicates how the prefix was inserted into BGP at the origin AS.

Next hop

• When a gateway router receives a route advertisement, it uses its import policy to decide whether to accept or filter the route and whether to set certain attributes such as the router preference metrics.
• The import policy may filter a route because the AS may not want to send traffic over one of the ASs in the route’s AS-PATH.

BGP Route Selection

• BGP uses eBGP and iBGP to distribute routes to all the routers within ASs.
• From this distribution, a router may learn about more than one route to any one prefix, in which case the router must select one of the possible routes.
• The input into this route selection process is the set of all routes that have been learned and accepted by the router. If there are two or more routes to the same prefix, then BGP sequentially invokes the following elimination rules until one route remains:

BGP - Route selection

• Routes are assigned a local preference value as one of their attributes. The local preference of a route could have been set by the router or could have been learned by another router in the same AS. This is a policy decision that is left up to the AS’s network administrator.
• From the remaining routes (all with the same local preference value), the route with the shortest AS-PATH is selected. If this rule were the only rule for route selection, then BGP would be using a DV algorithm for path determination, where the distance metric uses the number of AS hops rather than the number of router hops.
  From the remaining routes (all with the same local preference value and the same AS-PATH length), the route with the closest NEXT-HOP router is selected.