Project Links Logo Artwork
Graph Theory: Networking
Home > Graph Theory: Networking > The Internet > Link-State Routing
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Link-State Routing

What Can Go Wrong?

The strategy (called control flooding) just described works fine when all routers and links function properly. However, the strategy may fail when some links and/or nodes go down, or simply change relative to the rest of the network.

When something like this happens, how can knowledge of the change be propagated among all the nodes of the network? Every router's LSP database will contain an obsolete LSP until routers are informed of the change in the network.

Sequence Numbers

One solution is to give every LSP a sequence number.

If a router receives an LSP with a newer sequence number than that of an LSP in its database describing the same link, it will update its database with the new LSP.

But, there's still a problem. The sequence numbers must be of finite length. So, after a router has been on the network for a sufficient amount of time, the number of times it has sent out LSPs (incrementing the sequence numbers each time), the current sequence number will exceed the maximal number that can be represented.

This will cause the number to "wrap around" back to 0 (assuming the valid range is a subset of the non-negative integers). As a result, new LSPs may have a lower sequence number, and will therefore "look" older to routers receiving them.

For example, if sequence numbers are 32 bits long, they span the interval from 0 to 4,294,967,295 (inclusive). Then, after changes (a number reachable in a large, long-lived network), no incoming LSP will ever replace a previous one in a router's database.

Here's The Fix:

If the difference between the sequence numbers of an existing and an incoming LSP is very large, then assume that the LSP with the smaller number is actually newer, and must take the place of the existing LSP.

Thus, the rule for comparing the "age" of LSPs is:

If all LSP sequence numbers are in an interval of length ( in our example above), then the LSP with sequence number is older than the LSP with sequence number

if and

or and

Problem 11:

Can in the condition above be replaced with a different number? Such as , or ?

 
 
go backgo forward
go backgo forward