 The idea behind link state routing is fairly simple

and can be stated as five parts. Each router must do

the following things to make it work:

 1. Discover its neighbors and learn their network

addresses.
 2. Set the distance or cost metric to each of its
neighbors.
 3. Construct a packet telling all it has just learned.
 4. Send this packet to and receive packets from all
other routers.
 5. Compute the shortest path to every other router.
 In effect, the complete topology is distributed to
every router.

 Then Dijkstra’s algorithm can be run at each router

to find the shortest path to every other router.

 Learning about the Neighbours

 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 giving its name. These names must be
globally unique because when a distant router later
hears that three routers are all connected to F, it is
essential that it can determine whether all three
mean the same F.
 Setting Link Costs
 The link state routing algorithm requires each link to
have a distance or cost metric for finding shortest paths.

 The cost to reach neighbours can be set automatically, or

configured by the network operator.

 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 neighbours. The cost to each
neighbour is also given. An example network is
presented in Fig
 Building the link state packets is easy. The hard part
is determining when to build them.

 One possibility is to build them periodically, that is,

at regular intervals.

 Another possibility is to build them when some

significant event occurs, such as a line or neighbour
going down or coming back up again or changing
its properties appreciably.
 As networks grow in size, the router routing tables
grow proportionally. Not only is router memory
consumed by ever-increasing tables, but more CPU
time is needed to scan them and more bandwidth is
needed to send status reports about them.

 At a certain point, the network may grow to the

point where it is no longer feasible for every router
to have an entry for every other router, so the
routing will have to be done hierarchically.

 When hierarchical routing is used, the routers are

divided into what we will call 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.

 When different networks are interconnected, it is

natural to regard each one as a separate region to
free the routers in one network from having to know
the topological structure of the other ones.
 Figure shows 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 are 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.
 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 sending to all machines and letting
those that are interested read the data.

 Sending a packet to all destinations simultaneously

is called broadcasting.

 One broadcasting method that requires no special

features from the network is for the source to
simply send a distinct packet to each destination.
 Not only is the method wasteful of bandwidth and
slow, but it also requires the source to have a
complete list of all destinations.

 Multidestination routing, in which 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.
 After a sufficient number of hops, each packet will
carry only one destination like a normal packet.

 Multidestination routing is like using separately

addressed packets, except that when several
packets must follow the same route, one of them
pays full fare and the rest ride free.

 The network bandwidth is therefore used more

efficiently.

 In reverse path forwarding is elegant and

remarkably simple 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.

 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.

 An example of reverse path forwarding is shown in

Fig. Part (a) shows a network, part (b) shows a sink
tree for router I of that network, and part (c) shows
how the reverse path algorithm works.
 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
(assuming that the preferred path falls along the
sink tree) 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. 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.

 The principal advantage of reverse path forwarding

is that it is efficient while being easy to implement.

 It sends the broadcast packet over each link only

once in each direction, just as in flooding, yet it
requires only that routers know how to reach all
destinations, without needing to remember
sequence numbers or list all destinations in the
packet.
 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.
 Some applications, such as a multiplayer game or live
video of a sports event streamed to many viewing
locations, send packets to multiple receivers.

 Unless the group is very small, sending a distinct

packet to each receiver is expensive.

 we need a way to send messages to well-defined

groups that are numerically large in size but small
compared to the network as a whole.

 Sending a message to such a group is called

multicasting, and the routing algorithm used is called
multicast routing.
 All multicasting schemes require some way to create and
destroy groups and to identify which routers are members
of a group.

 Multicast routing schemes build on the broadcast routing

schemes I,e sending packets along spanning trees to
deliver the packets to the members of the group while
making efficient use of bandwidth.

 The best spanning tree to use depends on whether the

group is dense, with receivers scattered over most of the
network, or sparse, with much of the network not
belonging to the group.

 If the group is dense, broadcast is a good start because it

efficiently gets the packet to all parts of the network. But
broadcast will reach some routers that are not members
of the group, which is wasteful.
 As an example, consider the two groups, 1 and 2, in the network
shown in Fig. (a). Some routers are attached to hosts that belong to
one or both of these groups, as indicated in the figure.

 A spanning tree for the leftmost router is shown in Fig.(b). This

tree can be used for broadcast but is overkill for multicast, as can
be seen from the two pruned versions that are shown next.

 In Fig. (c), all the links that do not lead to hosts that are members
of group 1 have been removed. The result is the multicast
spanning tree for the leftmost router to send to group 1.

 Packets are forwarded only along this spanning tree, which is

more efficient than the broadcast tree because there are 7 links
instead of 10.

 Fig.(d) shows the multicast spanning tree after pruning for group
2. It is efficient too, with only five links this time. It also shows that
different multicast groups have different spanning trees.
 Models in which a source sends to a single destination
(called unicast), to all destinations (called broadcast),
and to a group of destinations (called multicast).

 Another delivery model, called anycast is sometimes

also useful. In anycast, a packet is delivered to the
nearest member of a group.

 Schemes that find these paths are called anycast

routing. Distance vector routing will distribute vectors
as usual, and nodes will choose the shortest path to
destination 1. This will result in nodes sending to the
nearest instance of destination 1. The routes are
shown in Fig.(a).
 This procedure works because the routing protocol
does not realize that there are multiple instances of
destination 1.

 That is, it believes that all the instances of node 1 are

the same node, as in the topology shown in Fig (b).
 Too many packets present in (a part of) the network
causes packet delay and loss that degrades
performance. This situation is called congestion.

 The network and transport layers share the

responsibility for handling congestion.

 The presence of congestion means that the load is

(temporarily) greater than the resources (in a part of the
network) can handle.

 Two solutions come to mind: increase the resources or

decrease the load. The most basic way to avoid
congestion is to build a network that is well matched
to the traffic that it carries.
 Provisioning
 When there is serious congestion due to resources
deficit, resources can be added dynamically, for
example, turning on spare routers or enabling lines
that are normally used only as backups (to make the
system fault tolerant) or purchasing bandwidth on the
open market.

 More often, links and routers that are regularly

heavily utilized are upgraded at the earliest
opportunity. This is called provisioning and happens
on a time scale of months, driven by long-term traffic
trends.
 Traffic Aware Routing
 The most of the existing network capacity, routes can
be tailored to traffic patterns that change during the
day as network users wake and sleep in different time
zones.

 For example, routes may be changed to shift traffic

away from heavily used paths by changing the
shortest path weights This is called traffic-aware
routing. Splitting traffic across multiple paths.
 Load Shedding
 when all else fails, the network is forced to discard
packets that it cannot deliver. The general name for
this is load shedding. A good policy for choosing
which packets to discard can help to prevent
congestion collapse.

 Admission Control
 Sometimes it is not possible to increase capacity. The
only way then to beat back the congestion is to
decrease the load.

 In a virtual-circuit network, new connections can be

refused if they would cause the network to become
congested. This is called admission control.
 The idea is simple: do not set up a new virtual circuit
unless the network can carry the added traffic without
becoming congested.

 Thus, attempts to set up a virtual circuit may fail. This

is better than the alternative, as letting more people
in when the network is busy just makes matters
worse.

 By analogy, in the telephone system, when a switch

gets overloaded it practices admission control by not
giving dial tones.
 Traffic Shaping
 Traffic shaping is a technique for regulating the
average rate and burstiness of a flow of data that
enters the network.

 The goal is to allow applications to transmit a wide

variety of traffic that suits their needs, including some
bursts, yet have a simple and useful way to describe
the possible traffic patterns to the network.

 When a flow is set up, the user and the network (i.e.,
the customer and the provider) agree on a certain
traffic pattern (i.e., shape) for that flow.
 Traffic policing
 Traffic shaping reduces congestion and thus helps the
network live up to its promise. However, to make it
work, there is also the issue of how the provider can
tell if the customer is following the agreement and
what to do if the customer is not.

 Packets in excess of the agreed pattern might be

dropped by the network, or they might be marked as
having lower priority. Monitoring a traffic flow is
called traffic policing.
 Leaky And Token Buckets
 Try to imagine a bucket with a small hole in the
bottom, as illustrated in Fig.(b). No matter the rate at
which water enters the bucket, the outflow is at a
constant rate, R, when there is any water in the bucket
and zero when the bucket is empty.

 Also, once the bucket is full to capacity B, any

additional water entering it spills over the sides and is
lost.

 This bucket can be used to shape or police packets

entering the network, as shown in Fig.(a).
Conceptually, each host is connected to the network
by an interface containing a leaky bucket.
 To send a packet into the network, it must be possible
to put more water into the bucket.

 If a packet arrives when the bucket is full, the packet

must either be queued until enough water leaks out to
hold it or be discarded.

 The former might happen at a host shaping its traffic

for the network as part of the operating system. The
latter might happen in hardware at a provider network
interface that is policing traffic entering the network.

This technique was proposed by and is called the leaky

bucket algorithm.
 Leaky and token buckets limit the long-term rate of a
flow but allow short term bursts up to a maximum
regulated length to pass through unaltered and
without suffering any artificial delays.

 Large bursts will be smoothed by a leaky bucket

traffic shaper to reduce congestion in the network.