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

Initial Sequence Numbers

The sequence-number strategy outlined on the previous page works well, except in a special situation:

If a router restarts after a failure, what should the initial sequence number be for the LSPs it begins sending?

A restarted router will not remember the LSPs it sent in the past. If an initial sequence number is incorrectly selected, it may send out new LSPs which will be ignored.

For example, if a router has in its database an LSP from router with sequence number 10, and , after a restart, chooses 0 as its initial sequence number, will ignore new LSPs sent by .

A Solution

A solution to this problem is called the lollipop sequence space. The idea of this method is for a router to use, upon restart, a sequence number that is different from any sequence number that router could have used in the past.

In this scheme, the sequence numbers used by routers are either negative, zero, or positive. Upon a router's restart, it begins assigning the smallest possible negative sequence number to the LSPs it sends out. If is the size of the range, this number will be (and the largest possible sequence number will be ). Subsequent LSPs are numbered , and so on.

When the sequence number becomes positive, the subsequent numbers "wrap around" in the "circular" part of the sequence space (as we saw on the previous page).

The new 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

or ,

and

 
 
go backgo forward
go backgo forward