This whimsically-named construct was proposed by Dr. Radia Perlman[9] . Lollipop-shaped sequence
number spaces are a hybrid of linear and circular sequence number spaces; if you think about it, a lollipop
has a linear component and a circular component. The problem with circular spaces is that there is no
number less than all other numbers. The problem with linear spaces is that they are—well—not circular.
That is, their set of sequence numbers is finite.
[9] R. Perlman."Fault-Tolerant Broadcasting of Routing Information." Computer Networks, Vol. 7, December 1983, pp. 395–405.
When router A restarts, it would be nice to begin with a number a that is less than all other numbers.
Neighbors will recognize this number for what it is, and if they have a pre-restart number b in their
databases from router A, they can send that number to router A and router A will jump to that sequence
number. Router A might be able to send more than one LSA before hearing about the sequence number it
had been using before restarting. Therefore, it is important to have enough restart numbers so that A
cannot use them all before neighbors either inform it of a previously used number or the previously used
number ages out of all databases.
These linear restart numbers form the stick of the lollipop. When they have been used up, or after a
neighbor has provided a sequence number to which A can jump, A enters a circular number space, the
candy part of the lollipop.
One way of designing a lollipop address space is to use signed sequence numbers, where –k <> 0, a <> 0, b > 0, a > b, and (a – b) > n/2.
Figure 4.10 shows an implementation of the lollipop-shaped sequence number space. A 32-bit signed
number space N is used, yielding 231 positive numbers and 231 negative numbers. –N (–231, or
0x80000000) and N – 1 (231 – 1, or 0x7FFFFFFF) are not used. A router coming online will begin its
sequence numbers at –N + 1 (0x80000001) and increment up to zero, at which time it has entered the
circular number space. When the sequence reaches N – 2 (0x7FFFFFFE), the sequence wraps back to
zero (again, N–1 is unused).
Next, suppose the router restarts. The sequence number of the last LSA sent before the restart is
0x00005de3 (part of the circular sequence space). As it synchronizes its database with its neighbor after
the restart, the router sends an LSA with a sequence number of 0x80000001 (–N + 1). The neighbor looks
into its own database and finds the pre-restart LSA with a sequence number of 0x00005de3. The neighbor
sends this LSA to the restarted router, essentially saying, "This is where you left off." The restarted router
then records the LSA with the positive sequence number. If it needs to send a new copy of the LSA at
some future time, the new sequence number will be 0x00005de6.
Lollipop sequence spaces were used with the original version of OSPF, OSPFv1 (RFC 1131). Although
the use of signed numbers was an improvement over the linear number space, the circular part was found
to be vulnerable to the same ambiguities as a purely circular space. The deployment of OSPFv1 never
progressed beyond the experimental stage. The current version of OSPF, OSPFv2 (originally specified in
RFC 1247) adopts the best features of linear and lollipop sequence number spaces. It uses a signed
number space like lollipop sequence numbers, beginning with 0x80000001. However, when the sequence
number goes positive, the sequence space continues to be linear until it reaches the maximum of
0x7fffffff. At that point the OSPF process must flush the LSA from all link state databases before
restarting.