Network

Layer
Routing
Algorithms
Inroduction

► The algorithms that choose the routes and the data structures that they
use are a major area of network layer design.
► The routing algorithm is responsible for deciding which output line an
incoming packet should be transmitted on.
► Routing Vs. Forwarding
► Properties of a routing algorithm:
► (i) correctness
► (ii) simplicity
► (iii) robustness
► (iv) stability
► (v) fairness
► (vi) efficiency.
Devices of Network Layer
 Repeater: A repeater is a network device that amplifies and
rebroadcasts incoming signals over a wider area or network layer
than the original signal.
 Bridges:A network bridge is a computer networking device that
creates a single, aggregate network from multiple communication
networks or network segments.
 Routers:A router is a network hardware device that connects
multiple computer networks and allows them to communicate with
each other.
 Gateway:A network gateway is a device or node that connects
different networks by translating communications from one protocol
Classification of Routing
Algorithms

Routing
Algorith
ms

Non- Adaptive
Adaptiv /
e/ Static Dynami
c
Principle of Optimality & Sink
tree
► if router J is on the optimal path from router I to router K, then the
optimal path from J to K also falls along the same route.
► The set of optimal routes from all sources to a given destination
form a tree rooted at the destination called a sink tree.
Routing Models

► Shortest Path Routing (Dijkstra’s shortest

path)
► Flooding
► Distance Vector Routing (Bellman Ford
Algorithm)
► Link state Routing
► Hierarchical Routing
► Broadcast Routing
► Multicast Routing
► Anycast Routing
► Routing for Mobile Hosts
► Routing in Ad-Hoc Networks
Shortest Path Algorithm

► Dijkstra Algorithm
► Each node of the graph representing a router and each edge of
the graph representing a communication line, or link.
► Each node is labeled with its distance from the source node along
the best known path.
► Initially, no paths are known, so all nodes are labeled with infinity.
► As the algorithm proceeds and paths are found, the labels may
change, reflecting better paths.
► A label may be either tentative or permanent. Initially, all labels are
tentative. When it is discovered that a label represents the shortest
possible path from the source to that node, it is made permanent
and never changed thereafter.
Shortest Path Algorithm
Flooding Algorithm

► Every incoming packet is sent out on every outgoing line except

the one it arrived on.
► Generates vast numbers of duplicate packets
► Hop counter
► Routers keep track of which packets have been flooded
► Advantages
► Ensures that a packet is delivered to every node in the network.
► Tremendously robust
► Used as a metric against which other routing algorithms can be
compared.
Distance Vector Routing

► Dynamic Routing Algorithm

► Operates by having each router maintain a table giving the
best known distance to each destination and which link to use
to get there.
► Bellman-Ford routing algorithm
► Each router maintains a routing table indexed by, and containing
one entry for each router in the network.
► This entry has two parts: the preferred outgoing line to use
for that destination and an estimate of the distance to that
destination.
Distance Vector Routing -
Example

(a) A subnet. (b) Input from A, I, H, K, and the new routing table for J.
The Count-to-infinity Problem
The Count-to-infinity Problem -
Example A
B
C
A 0
D0
B
E
C A 1 D A
D 2 B
E C
2
10 E D
2 E 0
A B C A
B 0 B
C C 0 Initialization
D D
E E
The Count-to-infinity Problem -
Example A1
A 0 B
B 10 C 2
C D0
D 1 E 2
A 1 D A
E
2 B
C 2
2
10 E D 2
2 E 0
A 10 B C A
B 0
B
C
C 0 Direct
D
D 2 Neighbours
E
E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B
C 2
2
10 E D 2
2 E 0
A 10 B C A 3
B 0 Neighbours
B
C of neighbours
C 0
D11
D 2
E
E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B 13
C 2
2
10 E D 2
2 E 0
A 10 B C A 3 Neighbours
B 0
B 13 of neighbours
C 13
C 0
D11 of neighbours
D 2
E 13
E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B 13
C 2
2
10 E D 2
2 E 0
A 10 B C A 3
B 0 Stable
B 13
C 13 convergence
C 0
D11
D 2
E 13
E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B 13
C 2
2
10 E D 2
2 E 0
B 1
A 10 C A 3
B 0 Good news:
B 13
C 13 C 0
A new link!
D11 D 2
E 13 E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B 13
C 2
2
10 E D 2
2 E 0
A 10 B 1 C A 3
B 0 Direct
B1
C 1 endpoints
C 0
D11 know
D 2
E 13
E2
The Count-to-infinity Problem -
Example A1
A 0 B3
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B3
C 2
2
10 E D 2
2 E 0
A4 B 1 C A 3
B 0 Neighbours
B1
C 1 C 0 know
D3 D 2
E3 E2
The Count-to-infinity Problem -
Example A1
A 0 B3
B4 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B3
C 2
2
10 E D 2
2 E 0
A4 B 1 C A 3
B 0 Neighbours
B1
C 1 C 0
of neighbours
D3 D 2
know
E3 E2
The Count-to-infinity Problem -
Example A1
A 0 B3
B4 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B3
C 2
2
10 E D 2
2 E 0
A4 B 1 C A 3
B 0 B1 A happy and
C 1 C 0 stable network
D3 D 2
E3 E2
The Count-to-infinity Problem -
Example A1
A 0 B3
B4 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B3
C 2
2
10 E D 2
2 E 0
A4 B C A 3 Bad news:
B 0 B1
C 1 Link crash!!
C 0
D3 D 2
E3 E2
The Count-to-infinity Problem -
Example A1
A 0 B3
B4 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B3
C 2
2
10 E D 2
2 E 0
A B C A 3
B 0 Direct
B
C
C 0
endpoints
D
D 2
know
E
E2
The Count-to-infinity Problem -
Example A1
A 0 B3
B4 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B3
C 2
2
10 E D 2
2 E 0
A 10 B C A 3
B 0 B
C C 0
D D 2
E E2
The Count-to-infinity Problem -
Example A1
A 0 B3
B4 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B3
C 2
2
10 E D 2
2 E 0
A 10 B C A 3 Get help
B 0 B5
C 13 from
C 0
D 11 neighbours
D 2
E 13 E2
The Count-to-infinity Problem -
Example A1
A 0 B7
B4 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B7
C 2
2
10 E D 2
2 E 0
A 10 B C A 3 Routing loop
B 0 B5
C 13 (due to
C 0
D 11 inconsistent
D 2
E 13 state info)
E2
The Count-to-infinity Problem -
Example A1
A 0 B7
B8 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B7
C 2
2
10 E D 2
2 E 0
A 10 B C A 3
B 0
B9
C 13
C 0
D 11
D 2
E 13
E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B8 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B 11
C 2
2
10 E D 2
2 E 0
A 10 B C A 3
B 0 Counting
B9
C 13 C 0 to infinity…
D 11 D 2
E 13 E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B 11
C 2
2
10 E D 2
2 E 0
A 10 B C A 3
B 0 B 13
C 13 C 0
D 11 D 2
E 13 E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B 13
C 2
2
10 E D 2
2 E 0
A 10 B C A 3
B 0 B 13
C 13 C 0
D 11 D 2
E 13 E2
The Count-to-infinity Problem -
Example A1
A 0 B 11
B 10 C 2
C 3 D0
D 1 E 2
A 1 D A3
E 3
2 B 13
C 2
2
10 E D 2
2 E 0
A 10 B C A 3
B 0 Stability
B 13
C 13 C 0 again
D 11 D 2
E 13 E2
Link State
Routing
Each router does the following:
► Step 1 : Discover its neighbors, learn their network address.
► When a router is booted, its send a special HELLO packet on each point-to-point
line.
► The router on the other end sends back a reply giving its name.
► These names must be globally unique.
► Step 2 : Measure the delay or cost to each of its
neighbors.
► Each link has a distance or cost metric for finding shortest
paths.
► Step 3 : Construct a packet telling all it has just
learnt.
► The packet starts with the identity of the sender, followed by a sequence
number and age and a list of neighbors along with the cost to each neighbor.
► Link packets may be built either periodically or when any significant event
occurs.
►
Link State Packets
Hierarchical Routing
► The routers are divided into regions.
► Each router knows all the details about how to route packets to
destinations within its own region but knows nothing about the internal
structure of other regions.
► For huge networks, a two-level hierarchy may be insufficient; it may be
necessary to group the regions into clusters, the clusters into zones, the
zones into groups, and so on.
► Reduces table entries, but increases path length.
► For example, consider a network with 720 routers.
► If there is no hierarchy, each router needs 720 routing table entries.
► If the network is partitioned into 24 regions of 30 routers each, each router needs
30 local entries plus 23 remote entries for a total of 53 entries.
► If a three-level hierarchy is chosen, with 8 clusters each containing 9 regions of
10 routers, each router needs 10 entries for local routers, 8 entries for routing to
other regions within its own cluster, and 7 entries for distant clusters, for a total
of 25 entries.
► The optimal number of levels for an N router network is ln N, requiring a
total of
e ln N entries per router.
Hierarchical Routing – Sneak
Peak
Broadcast Routing
► Sending a packet to all destinations simultaneously is called
broadcasting.
► One broadcasting method is for the source to simply send a distinct
packet to each destination.
► This is wasteful of bandwidth and slow, and also requires the source
to have a complete list of all destinations.
► This method is not desirable in practice, even though it is widely
applicable.
► Multi-destination routing
► Each packet contains a list of destinations
► The router checks all the destinations to determine the set of output lines
that will be needed.
► The router generates a new copy of the packet for each output line to be
used and includes in each packet only those destinations that are to use
the line.
► The destination set is partitioned among the output lines.
►
Broadcast Routing
► Flooding
► When implemented with a sequence number per source, flooding
uses links efficiently with a decision rule at routers that is relatively
simple.
► Flooding though not suited for ordinary point-to-point communication,
it rates serious consideration for broadcasting.
► Reverse Path Forwarding
► When a broadcast packet arrives at a router, the router checks to see if
the packet arrived on the link that is normally used for sending packets
toward the source of the broadcast.
► If so, there is an excellent chance that the broadcast packet itself
followed the best route from the router and is therefore the first copy to
arrive at the router.
► This being the case, the router forwards copies of it onto all links except
the one it arrived on.
► If, however, the broadcast packet arrived on a link other than the
preferred one for reaching the source, the packet is discarded as a likely
duplicate.
Reverse Path Forwarding -
Example

On the first hop, I sends packets to F, H, J, and N, as indicated by the second row of
the tree. Each of these packets arrives on the preferred path to I and is so indicated
by a circle around the letter. On the second hop, eight packets are generated, two
by each of the routers that received a packet on the first hop. As it turns out, all
eight of these arrive at previously unvisited routers, and five of these arrive along
the preferred line. Of the six packets generated on the third hop, only three arrive
on the preferred path (at C, E, and K); the others are duplicates. After five hops
and 24 packets, the broadcasting terminates, compared with four hops and 14
packets had the sink tree been followed exactly.
Broadcast Routing
► A spanning tree is a subset of the network that includes all the
routers but contains no loops.
► Sink trees are spanning trees.
► If each router knows which of its lines belong to the spanning tree,
it can copy an incoming broadcast packet onto all the spanning tree
lines except the one it arrived on.
► This method makes excellent use of bandwidth, generating the
absolute minimum number of packets necessary to do the job.
► The only problem is that each router must have knowledge of some
spanning tree for the method to be applicable.
Multicast Routing
► Sending messages to well-defined groups that are numerically large
in size but small compared to the network as a whole is called
Multicasting.
► Each group is identified by a multicast address and that routers
know the groups to which they belong.
► Multicast routing schemes build on the broadcast routing
schemes.
► Broadcast spanning tree
► Multicast spanning tree
► MOSPF (Multicast OSPF) - link state routing
► DVMRP (Distance Vector Multicast Routing Protocol)
► Disadvantage
► Lot of work for routers
► Solution
► Core-based trees - PIM (Protocol Independent Multicast)
Multicast Routing – Spanning
Tree
Multicast Routing – Core based
Tree
Anycast Routing

► A packet is delivered to the nearest member of a group.

► Why would we want anycast?
► Sometimes nodes provide a service, such as time of day or
content distribution for which it is getting the right information
all that matters, not the node that is contacted; any node will
do.
► Routing models employed
► Distance Vector Routing
► Link State Routing
Routing for Mobile Hosts
► Mobile hosts introduce a new complication: to route a
packet to a mobile host, the network first has to find the
host first.
► Home location and Home address
► Recompute routes as the mobile host moves and the
topology changes.
► Provide mobility above the network layer
► When moved to new locations, new network addresses
are acquired.
► Tunneling
Routing in Ad Hoc Networks
► Each node communicates wirelessly and acts as both a
host and a router.
► Networks of nodes that just happen to be near each other
are called
ad hoc networks or MANETs (Mobile Ad hoc
NETworks).
► AODV (Ad hoc On-demand Distance Vector) - the
distance vector algorithm that has been adapted to work in a
mobile environment.
► Route discovery
► ROUTE REQUEST
► ROUTE REPLY
► Route Maintenance
► Hello message
Routing in Ad Hoc Networks :
Route Discovery

(a) Range of A's broadcast.

(b) After B and D have received A's broadcast.
(c) After C, F, and G have received A's broadcast.
(d) After E, H, and I have received A's broadcast.
Shaded nodes are new recipients. Arrows show possible
reverse routes.
Routing in Ad Hoc Networks :
Route Discovery

Format of a ROUTE REQUEST

packet.

Format of a ROUTE REPLY

packet.
Routing in Ad Hoc Networks :
Route Maintenance

(a) D's routing table before G goes

down.
(b) The graph after G has gone
down.