Actually, the lollipop space does work. But linear is better.

The original link state routing scheme was the ARPANET scheme, which
had the problem that 3 LSPs with the same source with sequence numbers
spaced around the circle would bring the network down forever.

My 1983 paper with the lollipop space analyzed the problem and the
solution it presented does work. The one necessary thing
to require self-stabilization was requiring the packets to age...the
ARPANET thing didn't age an LSP until it had held onto it for 8 seconds,
and in the 3-bad-sequence-numbers
state the bad LSPs would be immediately forwarded, so they'd never age.

In the 1983 paper there were further improvements in robustness and efficiency.
The ARPANET algorithm, for instance, required routers to generate new LS
info every 60 seconds, and to wait for 90 seconds before starting up.
The paper explained how to get rid of both of those problems to be more
efficient.

Then in 1988 I did my thesis on routing algorithms invulnerable to
sabotage, even by trusted routers, and a component of the design was
a robust flooding mechanism. I realized that by taking that design and removing
the
cryptography, it was a simpler design than the one in the 1983 paper.
This happens sometimes when rethinking the problem in a different light
a few years later.

The simplification over the 1983 paper
was using a linear space. Although a circular (or
lollipop) space works also (assuming you require
the LS info to age before a router is allowed to
forward it), the failure mode in the circular space,
in the case of bad LS info floating around
is that the network will temporarily be
juggling packets around the circle, bothering all the routers. The
failure mode in the corrupted database case in the linear space is
that the one router whose behavior caused transmission of an LSA with
a bogus sequence number very near the top will need to stay offline until
its LSA expires, as opposed to the entire network having a headache
of juggling the bad router's LSAs until they expire. But they do expire.

So the linear space is better than the lollipop space, but the lollipop
space also works. It was a sufficiently trivial enhancement to the
1983 paper that I never wrote it down as a separate paper, but just
explained it to the
relevant people, so that both IS-IS and OSPF now use a linear space.

My reasoning at the time for lollipop space was that it required a double
failure:
  a) it would require bad LSA sequence number generation to ever get out
  of the linear portion of the lollipop
  b) once in the circular portion, it would requre more bad LS sequence
  number to get into the a<b<c<a state.
  
It's even possible that for some situations the lollipop would be better,
but certain the linear is simpler, and I really prefer simpler.

Radia

        X-Unix-From: buaazhangYAHOO.COM.CN Tue Sep 11 07:33:48 2001
        MIME-Version: 1.0
        Content-Transfer-Encoding: 8bit
        From: ÕÅ ½­Æ½ <buaazhangYAHOO.COM.CN>
        Subject: about the sequence number
        To: OSPFDISCUSS.MICROSOFT.COM
        
        Hi all,
        
           In RFC2328, the sequence number of LSA is linearly
        ordered(Page 120),i.e., it is linearly number space,
        why it is not lollipop-shaped sequence number space?
           Thanks!
        
        Regards,
        zhang
        
        _________________________________________________________
        Do You Yahoo!? µÇ¼Ãâ·ÑÑÅ»¢µçÓÊ! http://mail.yahoo.com.cn
        
        <font color=#6666FF>ÎÞÁÄ£¿ÓôÃÆ£¿¸ßÐË£¿Ã»ÀíÓÉ£¿¶¼À´ÁÄÌì°É£¡</font>¡ª¡ª
        ÑÅ»¢È«ÐÂÁÄÌìÊÒ! http://cn.chat.yahoo.com/c/roomlist.html

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]