UNIT IV ROUTING

Routing and protocols: Unicast routing - Distance Vector Routing - RIP - Link State Routing
– OSPF – Path-vector routing - BGP - Multicast Routing: DVMRP – PIM.

4.1 UNICAST ROUTING

Routing is the process of selecting best paths in a network. In unicast routing, a packet is
routed, hop by hop, from its source to itsdestination by the help of forwarding tables.

 Routing a packet from its source to its destination means routing the packet from a
source router (the default router of the source host) to a destination router (the router
connected to the destination network).
 The source host needs no forwarding table because it delivers its packet to the default
router in its local network.
 The destination host needs no forwarding table either because it receives the packet
from its default router in its local network. Only the intermediate routers in the
networks need forwarding tables.

NETWORK AS A GRAPH

The Figure below shows a graph representing a network.

 The nodes of the graph, labeled A through G, may be hosts, switches, routers, or
networks.
 The edges of the graph correspond to the network links.
 Each edge has an associated cost.

The basic problem of routing is to find the lowest-cost path between any two nodes, where
the cost of a path equals the sum of the costs of all the edges that make up the path. This
static approach has several problems:

 It does not deal with node or link failures.

 It does not consider the addition of new nodes or links.
 It implies that edge costs cannot change.
 For these reasons, routing is achieved by running routing protocols among the nodes.
These 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.
UNICAST ROUTING ALGORITHMS

There are three main classes of routing protocols:

1) Distance Vector Routing Algorithm – Routing Information Protocol

2) Link State Routing Algorithm – Open Shortest Path First Protocol

3) Path-Vector Routing Algorithm - Border Gateway Protocol

4.2DISTANCE VECTOR ROUTING (DSR) ROUTING INFORMATION PROTOCOL

(RIP) BELLMAN - FORD ALGORITHM

Distance vector routing is distributed, i.e., algorithm is run on all nodes. Each node knows the
distance (cost) to each of its directly connected neighbors. Nodes construct a vector
(Destination, Cost, NextHop) and distributes to its neighbors. Nodes compute routing table
of minimum distance to every other node via NextHop using information obtained from its
neighbors.

Eg: Refer your class notes

Periodic Update

In this case, each node automatically sends an update message every so often, even if
nothing has changed. The frequency of these periodic updates varies from protocol to
protocol, but it is typically on the order of several seconds to several minutes.

Triggered Update

In this case, whenever a node notices a link failure or receives an update from one of its
neighbors that causes it to change one of the routes in its routing table.

ROUTING INFORMATION PROTOCOL (RIP)

 RIP is an intra-domain routing protocol based on distance-vector algorithm.

 Routers advertise the cost of reaching networks. Cost of reaching each link is 1 hop. For
example, router C advertises to A that it can reach network 2, 3 at cost 0 (directly connected),
networks 5, 6 at cost 1 and network 4 at cost 2.
 Each router updates cost and next hop for each network number.
 Infinity is defined as 16, i.e., any route cannot have more than 15 hops. Therefore RIP can
be implemented on small-sized networks only.
 Advertisements are sent every 30 seconds or in case of triggered update.

 Command - It indicates the packet type. Value 1 represents a request packet. Value 2
represents a response packet.
 Version - It indicates the RIP version number. For RIPv1, the value is 0x01.
 Address Family Identifier - When the value is 2, it represents the IP protocol.
 IP Address - It indicates the destination IP address of the route. It can be the addresses of
only the natural network segment.
 Metric - It indicates the hop count of a route to its destination.
Count-To-Infinity (or) Loop Instability Problem
 Suppose link from node A to E goes down.
 Node A advertises a distance of ∞ to E to its neighbors
 Node B receives periodic update from C before A’s update reaches B
 Node B updated by C, concludes that E can be reached in 3 hops via C
 Node B advertises to A as 3 hops to reach E

 Node A in turn updates C with a distance of 4 hops to E and so on

 Thus nodes update each other until cost to E reaches infinity, i.e., no convergence.
 Routing table does not stabilize.
 This problem is called loop instability or count to infinity

Solution to Count-To-Infinity (or) Loop Instability Problem :

 Infinity is redefined to a small number, say 16.
 Distance between any two nodes can be 15 hops maximum. Thus distance vector routing
cannot be used in large networks.
 When a node updates its neighbors, it does not send those routes it learned from each
neighbor back to that neighbor. This is known as split horizon.
 Split horizon with poison reverse allows nodes to advertise routes it learnt from a node
back to that node, but with a warning message.

4.3 LINK STATE ROUTING (LSR) OPEN SHORTEST PATH

PROTOCOL (OSPF) DIJKSTRA’S ALGORITHM
 Each node knows state of link to its neighbors and cost.
 Nodes create an update packet called link-state packet (LSP) that contains:
o ID of the node
o List of neighbors for that node and associated cost
o 64-bit Sequence number
o Time to live
  Link-State routing protocols rely on two mechanisms:
 Reliable flooding of link-state information to all other nodes
 Route calculation from the accumulated link-state knowledge

Reliable Flooding
 Each node sends its LSP out on each of its directly connected links.
 When a node receives LSP of another node, checks if it has an LSP already for
that node.
 If not, it stores and forwards the LSP on all other links except the incoming
one.
 Else if the received LSP has a bigger sequence number, then it is stored and
forwarded. Older LSP for that node is discarded.
 Otherwise discard the received LSP, since it is not latest for that node.
 Thus recent LSP of a node eventually reaches all nodes, i.e., reliable flooding.

 Flooding of LSP in a small network is as follows:

 When node X receives Y’s LSP (fig a), it floods onto its neighbors A and C (fig
b)
 Nodes A and C forward it to B, but does not sends it back to X (fig c).
 Node B receives two copies of LSP with same sequence number.
 Accepts one LSP and forwards it to D (fig d). Flooding is complete.
 LSP is generated either periodically or when there is a change in the
topology.

Route Calculation
 Each node knows the entire topology, once it has LSP from every other node.
 Forward search algorithm is used to compute routing table from the received
 LSPs.
 Each node maintains two lists, namely Tentative and Confirmed with entries
ofthe form (Destination, Cost, NextHop).

DIJKSTRA’S SHORTEST PATH ALGORITHM

(FORWARD SEARCH ALGORITHM)
1. Each host maintains two lists, known as Tentative and Confirmed
2. Initialize the Confirmed list with an entry for the Node (Cost = 0).
3. Node just added to Confirmed list is called Next. Its LSP is examined.
4. For each neighbor of Next, calculate cost to reach each neighbor as Cost (Node to
Next) + Cost (Next to Neighbor).
a. If Neighbor is neither in Confirmed nor in Tentative list, then add (Neighbor, Cost,
NextHop) to Tentative list.
b. If Neighbor is in Tentative list, and Cost is less than existing cost, then replace the
entry with (Neighbor, Cost, NextHop).
5. If Tentative list is empty then Stop, otherwise move least cost entry from Tentative
list to Confirmed list. Go to Step 2.

Example :

4.4 OPEN SHORTEST PATH FIRST PROTOCOL (OSPF)

 OSPF is a non-proprietary widely used link-state routing protocol.
 OSPF Features are:
 Authentication―Malicious host can collapse a network by advertising
to reach every host with cost 0. Such disasters are averted by authenticating routing
updates.
 Additional hierarchy―Domain is partitioned into areas, i.e., OSPF is
more scalable.
 Load balancing―Multiple routes to the same place are assigned same cost. Thus
traffic is distributed evenly.

Link State Packet Format

 Version ― represents the current version, i.e., 2.

 Type ― represents the type (1–5) of OSPF message.
Type 1 - “hello” message, Type 2 - request, Type 3 – send ,
Type 4 - acknowledge the receipt of link state messages ,
Type 5 - reserved
 SourceAddr ― identifies the sender
 AreaId ― 32-bit identifier of the area in which the node is located
 Checksum ― 16-bit internet checksum
 Authentication type ― 1 (simple password), 2 (cryptographic authentication).
 Authentication ― contains password or cryptographic checksum

Difference Between Distance-Vector And Link-State Algorithms

4.5 PATH VECTOR ROUTING (PVR)

 Path-vector routing is an asynchronous and distributed routing algorithm.
 The Path-vector routing is not based on least-cost routing.
 The best route is determined by the source using the policy it imposes on the route.
 In other words, the source can control the path.
 Path-vector routing is not actually used in an internet, and is mostly designed to
route a packet between ISPs.

Spanning Trees
 In path-vector routing, the path from a source to all destinations is determined
by the best spanning tree.
 The best spanning tree is not the least-cost tree.
 It is the tree determined by the source when it imposes its own policy.
 If there is more than one route to a destination, the source can choose the route that
meets its policy best.
 A source may apply several policies at the same time.
 One of the common policies uses the minimum number of nodes to be visited.
Another common policy is to avoid some nodes as the middle node in a route.
 The spanning trees are made, gradually and asynchronously, by each node. When a
node is booted, it creates a path vector based on the information it can obtain about its
immediate neighbor.
 A node sends greeting messages to its immediate neighbors to collect these pieces
of information.
 Each node, after the creation of the initial path vector, sends it to all its immediate
neighbors.
 Each node, when it receives a path vector from a neighbor, updates its path vector
using the formula

 The policy is defined by selecting the best of multiple paths.

 Path-vector routing also imposes one more condition on this equation.
 If Path (v, y) includes x, that path is discarded to avoid a loop in the path.
 In other words, x does not want to visit itself when it selects a path to y.

Example:
 The Figure below shows a small internet with only five nodes.
 Each source has created its own spanning tree that meets its policy.
 The policy imposed by all sources is to use the minimum number of nodes to
reach a destination.
 The spanning tree selected by A and E is such that the communication does not pass
through D as a middle node.
 Similarly, the spanning tree selected by B is such that the communication does not
pass through C as a middle node.

Path Vectors made at booting time

 The Figure below shows all of these path vectors for the example.
 Not all of these tables are created simultaneously.
 They are created when each node is booted.
 The figure also shows how these path vectors are sent to immediate neighbors
after they have been created.

Updating Path Vectors

 The Figure below shows the path vector of node C after two events.
 In the first event, node C receives a copy of B’s vector, which improves its vector:
now it knows how to reach node A.
 In the second event, node C receives a copy of D’s vector, which does not change
its vector.
 The vector for node C after the first event is stabilized and serves as its forwarding
table.
4.6 BORDER GATEWAY PROTOCOL (BGP)
 The Border Gateway Protocol version (BGP) is the only interdomain routing
protocol used in the Internet today.
 BGP4 is based on the path-vector algorithm. It provides information about the
reachability of networks in the Internet.
 BGP views internet as a set of autonomous systems interconnected arbitrarily.

 Each AS have a border router (gateway), by which packets enter and leave that
AS. In above figure, R3 and R4 are border routers.
 One of the router in each autonomous system is designated as BGP speaker.
 BGP Speaker exchange reachability information with other BGP speakers, known
as external BGP session.
 BGP advertises complete path as enumerated list of AS (path vector) to reach a
particular network.
 Paths must be without any loop, i.e., AS list is unique.
 For example, backbone network advertises that networks 128.96 and 192.4.153 can
be reached along the path <AS1, AS2, AS4>.

iBGP - interior BGP

 A Variant of BGP
 Used by routers to update routing information learnt from other speakers to routers
inside the autonomous system.
 Each router in the AS is able to determine the appropriate next hop for all prefixes.
4.7 MULTICAST ROUTING
 To support multicast, a router must additionally have multicast forwarding tables
that indicate, based on multicast address, which links to use to forward the multicast
packet.
 Unicast forwarding tables collectively specify a set of paths.
 Multicast forwarding tables collectively specify a set of trees –Multicast
distribution trees.
 Multicast routing is the process by which multicast distribution trees are
determined.
 To support multicasting, routers additionally build multicast forwarding
tables.
 Multicast forwarding table is a tree structure, known as multicast
distribution trees.
 Internet multicast is implemented on physical networks that support broadcasting
by extending forwarding functions.

MULTICAST DISTRIBUTION TREES

There are two types of Multicast Distribution Trees used in multicast routing.
They are
 Source-Based Tree: (DVMRP)
 For each combination of (source , group), there is a shortest path spanning tree.
 Flood and prune
 Send multicast traffic everywhere
 Prune edges that are not actively subscribed to group
 Link-state
o Routers flood groups they would like to receive
o Compute shortest-path trees on demand

 Shared Tree (PIM)

o Single distributed tree shared among all sources
o Does not include its own topology discovery mechanism, but instead
uses routing information supplied by other routing protocols
o Specify rendezvous point (RP) for group
o Senders send packets to RP, receivers join at RP
 RP multicasts to receivers; Fix-up tree for optimization
 Rendezvous-Point Tree: one router is the center of the group and therefore the
root of the tree.

MULTICAST ROUTING PROTOCOLS

 Internet multicast is implemented on physical networks that support broadcasting by
extending forwarding functions.
 Major multicast routing protocols are:
1. Distance-Vector Multicast Routing Protocol (DVMRP)
2. Protocol Independent Multicast (PIM)
4.8 Distance Vector Multicast Routing Protocol
 The DVMRP, is a routing protocol used to share information between routers to
facilitate the transportation of IP multicast packets among networks.
 It formed the basis of the Internet's historic multicast backbone.
 Distance vector routing for unicast is extended to support multicast routing.
 Each router maintains a routing table for all destination through exchange of
distance vectors.
 DVMRP is also known as flood-and-prune protocol.
 DVMRP consists of two major components:
 A conventional distance-vector routing protocol, like RIP
 A protocol for determining how to forward multicast packets, based on the routing
table
 DVMRP router forwards a packet if
 The packet arrived from the link used to reach the source of the packet
 If downstream links have not pruned the tree
 DVMRP protocol uses the basic packet types as follows:

 The forwarding table of DVMRP is as follows:

 Multicasting is added to distance-vector routing in four stages.

 Flooding
 Reverse Path Forwarding (RPF)
 Reverse Path Broadcasting (RPB)
 Reverse Path Multicast (RPM)
Flooding
 Router on receiving a multicast packet from source S to a Destination from
 NextHop, forwards the packet on all out-going links.
 Packet is flooded and looped back to S.
 The drawbacks are:
 It floods a network, even if it has no members for that group.
  Packets are forwarded by each router connected to a LAN, i.e., duplicate
flooding

Reverse Path Forwarding (RPF)

 RPF eliminates the looping problem in the flooding process.
 Only one copy is forwarded and the other copies are discarded.
 RPF forces the router to forward a multicast packet from one specific interface: the
one which has come through the shortest path from the source to the router.
 Packet is flooded but not looped back to S.

Reverse-Path Broadcasting (RPB)

 RPB does not multicast the packet, it broadcasts it.
 RPB creates a shortest path broadcast tree from the source to each destination.
 It guarantees that each destination receives one and only one copy of the packet.
 We need to prevent each network from receiving more than one copy of the
packet.
 If a network is connected to more than one router, it may receive a copy of the
packet from each router.
 One router identified as parent called designated Router (DR).
 Only parent router forwards multicast packets from source S to the attached
network.
 When a router that is not the parent of the attached network receives a multicast
packet, it simply drops the packet.
Reverse-Path Multicasting (RPM)
 To increase efficiency, the multicast packet must reach only those networks that
have active members for that particular group.
 RPM adds pruning and grafting to RPB to create a multicast shortest path tree that
supports dynamic membership changes.
Pruning:
 Sent from routers receiving multicast traffic for which they have no active group
members
 “Prunes” the tree created by DVMRP
 Stops needless data from being sent

Grafting:
 Used after a branch has been pruned back
 Sent by a router that has a host that joins a multicast group
 Goes from router to router until a router active on the multicast group is reached
 Sent for the following cases
 A new host member joins a group
 A new dependent router joins a pruned branch
 A dependent router restarts on a pruned branch
4.9 Protocol Independent Multicast (PIM)
 PIM divides multicast routing problem into sparse and dense mode.
 PIM sparse mode (PIM-SM) is widely used.
 PIM does not rely on any type of unicast routing protocol, hence protocol
independent.
 Routers explicitly join and leave multicast group using Join and Prune
messages.
 One of the router is designated as rendezvous point (RP) for each group in a domain
to receive PIM messages.
 Multicast forwarding tree is built as a result of routers sending Join messages to RP.
 Two types of trees to be constructed:
 Shared tree - used by all senders
 Source-specific tree - used only by a specific sending host
 The normal mode of operation creates the shared tree first, followed by one or more
source-specific trees

Shared Tree
 When a router sends Join message for group G to RP, it goes through a set
of routers.
 Join message is wildcarded (*), i.e., it is applicable to all senders.
 Routers create an entry (*, G) in its forwarding table for the shared tree.
 Interface on which the Join arrived is marked to forward packets for that group.
 Forwards Join towards rendezvous router RP.
 Eventually, the message arrives at RP. Thus a shared tree with RP as root is
formed.

Example
 Router R4 sends Join message for group G to rendezvous router RP.
 Join message is received by router R2. It makes an entry (*, G) in its table and
forwards the message to RP.
 When R5 sends Join message for group G, R2 does not forwards the Join. It adds an
outgoing interface to the forwarding table created for that group.

 As routers send Join message for a group, branches are added to the tree, i.e.,
shared.
 Multicast packets sent from hosts are forwarded to designated router RP.
 Suppose router R1, receives a message to group G.
 o R1 has no state for group G.
o Encapsulates the multicast packet in a Register message.
o Multicast packet is tunneled along the way to RP.
 RP decapsulates the packet and sends multicast packet onto the shared tree, towards
R2.
 R2 forwards the multicast packet to routers R4 and R5 that have members for group
G.

Source-Specific Tree
 RP can force routers to know about group G, by sending Join message to the
sending host, so that tunneling can be avoided.
 Intermediary routers create sender-specific entry (S, G) in their tables. Thus
a source-specific route from R1 to RP is formed.
 If there is high rate of packets sent from a sender to a group G, then sharedtree is
replaced by source-specific tree with sender as root.
Example

 Router R3 learns about group G through the message sent by RP.

 Router R4 send a source-specific Join due to high rate of packets from sender.
 Router R2 learns about group G through the message sent by R4.
 Eventually a source-specific tree is formed with R1 as root.

Analysis of PIM
 Protocol independent because, tree is based on Join messages via shortest path.
 Shared trees are more scalable than source-specific trees.
 Source-specific trees enable efficient routing than shared trees.