Lecture 3

Link State Routing
The idea behind link state routing is simple and can be stated as five parts. Each router must do the
following:
• Discover its neighbors and learn their network addresses.
• Measure the delay or cost to each of its neighbors.
• Construct a packet telling all it has just learned.
• Send this packet to all other routers.
• Compute the shortest path to every other router

Learning about the Neighbors
When a router is booted, its first task is to learn who its neighbours 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.
(a ) Nine routers and a LAN. (b) A graph model of (a).

(b)
Measuring Line Cost
 The link state routing algorithm requires each router to know, or at least have a reasonable estimate of, the delay
to each of its neighbors. The most direct way to determine this delay is to send over the line a special ECHO
packet that the other side is required to send back immediately.
 By measuring the round-trip time and dividing it by two, the sending router can get a reasonable estimate of the
delay.
 For even better results, the test can be conducted several times, and the average used. Of course, this method
implicitly assumes the delays are symmetric, which may not always be the case.
• Unfortunately, there is also an argument against including the load in the delay calculation. Consider the subnet of
Fig. which is divided into two parts, East and West,
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 , and a list of neighbors.
 For each neighbour, the delay to that neighbor is given.
 An example subnet is given in Fig.(a) with delays shown as labels on
the lines. The corresponding link state packets for all six routers are
shown in Fig.(b).
HIERARCHICAL ROUTING
• The routers are divided into what we will call regions, with each
router knowing all the details about how to route packets to
destinations within its own region, but knowing 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, until we run out of
names for aggregations.
BROADCAST ROUTING
• Sending a packet to all destinations simultaneously is called broadcasting.
1) The source simply sends a distinct packet to each destination. Not only is
the method wasteful of bandwidth, but it also requires the source to have a
complete list of all destinations.
2) Flooding.
•The problem with flooding as a broadcast technique is that it generates
too many packets and consumes too much bandwidth.
•
Part (a) shows a subnet, part (b) shows a sink tree for router I of that subnet, and part
(c) shows how the reverse path algorithm works.
 When a broadcast packet arrives at a router, the router checks to see 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.
This being the case, 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
MULTICAST ROUTING
 To do multicast routing, each router computes a spanning tree covering all other
routers. For example, in Fig.(a) we have two groups, 1 and 2.
 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). When a process sends a
multicast packet to a group, the first router examines its spanning tree and prunes it,
removing all lines that do not lead to hosts that are members of the group.
 In our example, Fig.(c) shows the pruned spanning tree for group 1. Similarly, Fig.(d)
shows the pruned spanning tree for group 2. Multicast packets are forwarded only
along the appropriate spanning tree.

Lecture 3

Uploaded by

Copyright:

Available Formats

Lecture 3

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 3

Uploaded by

Copyright:

Available Formats

Link State Routing

• Discover its neighbors and learn their network addresses.

• Measure the delay or cost to each of its neighbors.

• Construct a packet telling all it has just learned.

• Send this packet to all other routers.

• Compute the shortest path to every other router

(a ) Nine routers and a LAN. (b) A graph model of (a).

You might also like