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:
|