Link state routing The idea behind link state routing is fairly simple and can be stated as five parts Each router must do the following
1 Discover its neighbors, learn their network address.
2.Set the distance or cost metric to each of its neighbors.
3.Construct a packet containing 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.
•Step 1: 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 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
When two or more routers are connected by a broadcast link (e g a switch, ring, or classic Ethernet), the situation is slightly more complicated Fig illustrates a broadcast 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
• A better way to model the LAN is to consider it as a node itself, as shown in Fig 5 11
• Here we have introduced a new, artificial node, N, to which A, C, and F are connected
• One designated router on the LAN is selected to play the role of N in the routing protocol
• The fact that it is possible to go from A to C on the LAN is represented by the path ANC here
•Step 2: Setting Link Costs
– To determine the 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 2, the sending router can get a reasonable estimate of the delay.
– Average delay value can be better.
•Steps 3: Building link state packets
– Each router builds 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.
– To build them is easy, but when to build them is difficult to determine:
• To build them periodically (at regular intervals)
• To build them when some significant event occurs, such as a line or neighbor going down or coming back up again or changing its properties appreciably.
• The cost to each neighbor is also given
• An example network is presented in Fig 5 12 ( with costs shown as labels on the lines
• The corresponding link state packets for all six routers are shown in Fig 5 12 (b)
• Steps 4: Distributing the link state packets
– The fundamental idea is to use flooding to distribute the link state packets to all routers.
– 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 (source router, sequence) pairs they see. When a new link state packet comes in, it is checked against the list of packets already seen.
– If it is new, it is forwarded on all lines except the one it arrived on. If it is a duplicate, it is discarded.
– If a packet with a sequence number lower than the highest one seen so far ever arrives, it is rejected as being obsolete as the router has more recent data
• Steps 5: 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.
– 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
• Link state, distance vector, and other algorithms rely on processing at all the routers to compute routes
• Problems with the hardware or software at even a small number of routers can wreak havoc across the network
• For example, if a router claims to have a link it does not have or forgets a link it does have, the network graph will be incorrect
• If a router fails to forward packets or corrupts them while forwarding them, the route will not work as expected
• Finally if it runs out of memory or does the routing calculation wrong bad things will happen
• As the network grows into the range of tens or hundreds of thousands of nodes the probability of some router failing occasionally becomes non negligible