Computer Network
Network Layer
Routing Algorithm
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Routing Algorithm
• The routing algorithm is that part of the network layer software
• It is responsible for deciding which output line an incoming packet
should be transmitted on.
• If the subnet uses datagrams internally, this decision must be made a
new for every arriving data packet since the best route may have
changed since last time.
• If the subnet uses virtual circuits internally, routing decisions are
made only when a new virtual circuit is being set up. Thereafter, data
packets just follow the previously-established route.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Routing Algorithm Continue
• Routing algorithms can be grouped into two major classes
• Nonadaptive algorithms-static routing
• Do not base their routing decisions on measurements or estimates of the current traffic
and topology
• Computed in advance, off-line, and downloaded to the routers when the network is
booted.
• Adaptive algorithms- Dynamic
• Change their routing decisions to reflect changes in the topology, and usually the traffic
as well
• Change the routes based on
• distance, number of hops, or estimated transit time
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
The Optimality Principle
• It states that 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.
• To see this, call the part of the route from I to Jr1 and the rest of the route
r2. If a route better than r2 existed from J to K, it could be concatenated
with r1 to improve the route from I to K, contradicting our statement that
r1r2 is optimal.
• The optimality principle, we can see that the set of optimal routes from all
sources to a given destination form a tree rooted at the destination. Such
a tree is called a sink tree
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Sink tree
SubNet Sink tree
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Sink tree
• Since a sink tree is indeed a tree, it does not contain any loops, so
each packet will be delivered within a finite and bounded number of
hops.
• In practice, life is not quite this easy. Links and routers can go down
and come back up during operation, so different routers may have
different ideas about the current topology.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Shortest Path Routing
• To choose a route between a given pair of
routers, the algorithm just finds the
shortest path between them on the graph.
• The concept of a shortest path deserves
some explanation.
• One way of measuring path length is the
number of hops
• Another metric is the geographic distance
in kilometers.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Shortest Path Routing Continue…
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Flooding
• Another static algorithm is flooding, in which every incoming packet is
sent out on every outgoing line except the one it arrived on.
• Flooding obviously generates vast numbers of duplicate packets
• hop counter is used to avoid infinite number of duplicate packets.
• Hop counter contained in the header of each packet, which is
decremented at each hop, with the packet being discarded when the
counter reaches zero.
• Ideally, the hop counter should be initialized to the length of the path
from source to destination.
• If the sender does not know the path is, it can initialize the counter to
the worst case, namely, the full diameter of the subnet.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Flooding Conti…
• An alternative technique for damming the flood is to keep track of
which packets have been flooded
• To achieve this goal, source router put a sequence number in each
packet it receives from its hosts.
• Each router needs a list which sequence numbers originating at that
source have already been seen.
• If an incoming packet is on the list, it is not flooded.
• Selective flooding
• Every incoming packet is sent out on only on those lines that are
going approximately in the right direction.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Distance Vector Routing
• Dynamic algorithms-Distance vector routing and Link state routing
• Distance vector routing algorithms operate by having each router
maintain a table giving the best known distance to each destination
and which line to use to get there.
• These tables are updated by exchanging information with the
neighbors.
• The distance vector routing algorithm is sometimes called by other
names - Bellman-Ford routing algorithm and Ford-Fulkerson
algorithm (Bellman, 1957; and Ford and Fulkerson, 1962).
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Distance Vector Routing Conti….
• In distance vector routing, each router maintains a routing table
indexed by, and containing one entry for, each router in the subnet.
• This entry contains two parts: the preferred outgoing line to use for
that destination and an estimated time or distance to that
destination.
• The metric used might be
• number of hops
• time delay in milliseconds- ECHO packets
• total number of packets queued along the path, or something similar.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Distance Vector Routing Conti….
• As an example, assume that delay is used as a metric and that the
router knows the delay to each of its neighbors.
• Once every T msec each router sends to each neighbor a list of its
estimated delays to each destination.
• It also receives a similar list from each neighbor.
• Imagine that one of these tables has just come in from neighbor X,
with Xi being X's estimate of how long it takes to get to router i.
• If the router knows that the delay to X is m msec, it also knows that it
can reach router i via X in Xi + m msec.
• By performing this calculation for each neighbor, a router can find out
which estimate seems the best and use that estimate and the
corresponding line in its new routing table.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Distance Vector Routing Conti….
• This updating process is illustrated below
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Distance Vector Routing Conti….
• The first four columns of part (b) show the delay vectors received from the
neighbors of router J.
• A claims to have a 12-msec delay to B, a 25-msec delay to C, a 40-msec delay to D,
etc.
• Suppose that J has measured or estimated its delay to its neighbors, A, I, H, and K
as 8, 10, 12, and 6 msec, respectively.
• Consider how J computes its new route to router G. It knows that it can get to A
in 8 msec, and A claims to be able to get to G in 18 msec, so J knows it can count
on a delay of 26 msec to G if it forwards packets bound for G to A.
• Similarly, it computes the delay to G via I, H, and K as 41 (31 + 10), 18 (6 + 12),
and 37 (31 + 6) msec, respectively.
• The best of these values is 18, so it makes an entry in its routing table that the
delay to G is 18 msec and that the route to use is via H.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Distance Vector Routing Conti….
• Two primary problems caused its demise.
• First, since the delay metric was queue length, it did not take line bandwidth into
account when choosing routes. Of course, it would have been possible to change
the delay metric to factor in line bandwidth.
• Second problem also existed, namely, the algorithm often took too long to
converge (the count-to-infinity problem). For these reasons, it was replaced by an
entirely new algorithm, now called link state routing.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
The Count-to-Infinity Problem
• Distance vector routing works in theory but has a serious drawback in practice:
• it may do so slowly.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Link State Routing
• Variants of link state routing are now widely used.
• The idea behind link state routing is simple and can be stated as five
parts. Each router must do the following:
1. Discover its neighbors and learn their network addresses.
2. Measure the delay or cost to each of its neighbors.
3. Construct a packet telling all it has just learned.
4. Send this packet to all other routers.
5. Compute the shortest path to every other router.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Link State Routing Conti…
• Learning about the Neighbors
• When a router is booted, its first task is to learn who its
neighbors are. It accomplishes this goal by sending a
special HELLO packet on each point-to-point line.
• The router on the other end is expected to send back a
reply telling who it is.
• When two or more routers are connected by a LAN, the
situation is slightly more complicated.
• The following figure illustrates a LAN to which three
routers, A, C, and F, are directly connected.
• Each of these routers is connected to one or more
additional routers, as shown.
• One way to model the LAN is to consider it as a node itself
• Here we have introduced a new, artificial node, N, to which
A, C, and F are connected.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Link State Routing Conti…
• Measuring Line Cost
• The link state routing algorithm requires each router to know a
reasonable estimate delay to each of its neighbors.
• The most direct way to determine this delay is to send the a special
ECHO packet that the other side is required to send back immediately .
• By measuring the round-trip time the delay is dividing it by two.
• For even better results, the test can be conducted several times, and
the average used.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Link State Routing Conti…
• Building Link State Packets
• Once the information needed for the exchange has
been collected, the next step is for each router to build
a packet containing all the data.
• The packet starts with the identity of the sender,
followed by a sequence number and age (to be
described later), and a list of neighbors.
• For each neighbor, the delay to that neighbor is given.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Link State Routing Conti…
• Distributing the Link State Packets
• The fundamental idea is to use flooding to distribute the link state
packets.
• To keep the flood in check, each packet contains a sequence number
that is incremented for each new packet sent.
• Routers keep track of all the pairs they see.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Link State Routing Conti…
• Computing the New Routes
• Once a router has accumulated a full set of link state packets, it can construct
the entire subnet graph because every link is represented.
• Now Dijkstra's algorithm can be run locally to construct the shortest path to all
possible destinations.
• The results of this algorithm can be installed in the routing tables, and normal
operation resumed.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Hierarchical Routing
• As networks grow in size, the router routing tables grow proportionally.
• At a certain point no longer feasible for every router to have an entry for every
other router
• So the routing will have to be done hierarchically
• In hierarchical routing, the routers are divided into regions, with each router
knowing all the details about how to route packets to destinations within its own
region, but not knowing about the internal structure of other regions.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Hierarchical Routing
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Hierarchical Routing
• The above Figure gives a quantitative example of routing in a two-
level hierarchy with five regions.
• The full routing table for router 1A has 17 entries, as shown in Fig. (b).
• When routing is done hierarchically, as in Fig. (c), there are entries for
all the local routers as before, but all other regions have been
condensed into a single router, so all traffic for region 2 goes via the
1B -2A line, but the rest of the remote traffic goes via the 1C -3B line.
• Hierarchical routing has reduced the table from 17 to 7 entries.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Broadcast Routing
• In some applications, hosts need to send messages to many or all
other hosts.
• For example, a service distributing weather reports, stock market updates, or
live radio programs might work best by broadcasting to all machines and
letting those that are interested read the data.
• Sending a packet to all destinations simultaneously is called
broadcasting.
• Various methods have been proposed for doing it.
• The source to simply send a distinct packet to each destination
• It also requires the source to have a complete list of all destinations.
• Flooding
• Flooding is ill-suited for ordinary point-to-point communication, for broadcasting it might
rate serious consideration.
• it generates too many packets and consumes too much bandwidth
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Broadcast Routing
• Multidestination routing
• In this method, each packet contains either a list of destinations or a bit map indicating the desired
destinations.
• When a packet arrives at a router, 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 sink tree
• A spanning tree is a subset of the subnet that includes all the routers but contains no loops.
• Reverse path forwarding
• Reverse path forwarding, is remarkably simple once it has been pointed out.
• When a broadcast packet arrives at a router, the router checks, if the packet arrived on the line that is
normally used for sending packets to 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.
• The router forwards copies of it onto all lines except the one it arrived on.
• If, however, the broadcast packet arrived on a line other than the preferred one for reaching the source,
the packet is discarded as a likely duplicate.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Broadcast Routing
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Multicast Routing
• Sending a message to such a group is called multicasting, and its
routing algorithm is called multicast routing
• Multicasting requires group management. Some way is needed to
create and destroy groups, and to allow processes to join and leave
groups. How these tasks are accomplished is not of concern to the
routing algorithm.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Multicast Routing
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].
Multicast Routing(core-based trees )
• An alternative design uses core-based trees.
• Here, a single spanning tree per group is computed, with the root (the
core) near the middle of the group.
• To send a multicast message, a host sends it to the core, which then
does the multicast along the spanning tree.
DRBCCC HINDU COLLEGE(SHIFT-II) Dept. of Computer Science By [Link],M.C.A.,[Link].