Date: Tue, 16 Feb 2016 08:38:55 +0000
   From: Roy Marples <>

   The queue can be kept quite short because we don't care about any prior 
   entries each time state changes to LINK_STATE_DOWN.
   Also, we don't care about any prior entries (other than LINK_STATE_DOWN) 
   Finally we set LINK_STATE_UP.

   So the queue should only ever hold a maximum of 3 items. Could even work it 
   like so

Sounds better than my suggestion, from someone who knows better how
the link state events are used!  Maybe I should have looked at the
list of valid states, too -- all three of them.

We don't even need an array, really.  If I understand correctly, we
obviously have the following equivalences of queues:

(1) unknown/unknown = unknown
(2) unknown/down    = down
(3) unknown/up      = down/up
(4)    down/unknown = down/unknown
(5)    down/down    = down
(6)    down/up      = down/up
(7)      up/unknown = up/unknown
(8)      up/down    = up/down
(9)      up/up      = up

I can reasonably believe (10) up/down/up = down/up and (11)
down/up/down = down, too.  From these, we can reduce almost all
3-queues to 2-queues:

unknown/unknown/unknown =(1) unknown/unknown =(1) unknown
unknown/unknown/down =(1) unknown/down =(2) down
unknown/unknown/up =(3) unknown/up =(2) down/up
unknown/down/unknown =(2) down/unknown
unknown/down/down =(2) down/down =(5) down
unknown/down/up =(2) down/down/up =(5) down/up
unknown/up/unknown =(3) down/up/unknown ?
unknown/up/down =(3) down/up/down =(11) down
unknown/up/up =(3) down/up/up =(9) down/up
down/unknown/unknown =(1) down/unknown
down/unknown/down =(2) down/down =(5) down
down/unknown/up =(3) down/down/up =(5) down/up
down/down/unknown =(5) down/unknown
down/down/down =(5) down/down =(5) down
down/down/up =(5) down/up
down/up/unknown ?
down/up/down =(11) down
down/up/up =(9) down/up
up/unknown/unknown =(1) up/unknown
up/unknown/down =(2) up/down
up/unknown/up = up/down/up =(10) down/up
up/down/unknown ?
up/down/down =(5) up/down
up/down/up =(10) down/up
up/up/unknown = up/unknown
up/up/down = up/down
up/up/up = up/up = up

That leaves us with only two cases where a 3-queue stays a 3-queue and
doesn't reduce to a 2-queue.  For those cases, the possible 4-queues

down/up/unknown/unknown =(1) down/up/unknown
down/up/unknown/down =(2) down/up/down =(11) down
down/up/unknown/up =(3) down/up/down/up =(10) down/up
up/down/unknown/unknown =(1) up/down/unknown
up/down/unknown/down =(2) up/down/down =(5) up/down
up/down/unknown/up =(3) up/down/down/up =(5) up/down/up =(10) down/up

Collecting all the possible queues, we get only nine possibilities:


We could store it as a single int (numbered densely, or by 1 <<
LINK_STATE_*) and write the queue-append operation all as one switch.

Perhaps there are more equivalences I didn't capture, or cases that
are never going to occur -- for example, do we ever actually
transition from up/down to unknown, or does unknown only happen when
the interface is first attached?  (I'm not sure.)

Reply via email to