Subject: 16 bit interpretation of sequence checking?

From: Björn Berglöf <[email-masked]>
Date: Wed, 3 Mar 2004 12:38:33 +0100

BACKGROUND:
==========
In "draft-ietf-pwe3-atm-encap-04.txt" section 4.3.4 describes
the sequence number processing as:
     ----------------------------------------------------------------------
     - if the sequence number on the packet is 0, then the packet passes
       the sequence number check.

     - otherwise if the packet sequence number >= the expected sequence
       number and the packet sequence number - the expected sequence
       number < 32768, then the packet is in order.

     - otherwise if the packet sequence number < the expected sequence
       number and the expected sequence number - the packet sequence
       number >= 32768, then the packet is in order.

     - otherwise the packet is out of order.

   If a packet is in order then, it can be delivered immediately. If the
   packet is in order, then the expected sequence number MUST be set
   using the algorithm:

   expected_sequence_number := packet_sequence_number + 1 mod 2**16
   if (expected_sequence_number = 0) then expected_sequence_number:= 1;
     ----------------------------------------------------------------------

QUESTION 1:
==========
Is "the packet passes the sequence number check" the same as 
"the packet is in order" ? I.e, Should the expected_sequence_number
be updated if the sequence number i 0 ?

QUESTION 2:
==========
I enterpret this rather complex description above as a way to map 16 bit 
behaviour into a 32 bit environment. As a hardware designer I have 
a hard time convincing myself (and others) that the above is equivalent 
to the following psueudo-code:

      diff = SeqNo - ExpNo;
      if ((SeqNo=0) or (diff[15]=0) then OK;
      else NOT_OK;
      end if;
      if OK then NewExpNo = (SeqNo=FFFF) ? 1 : SeqNo+1;
      end if;

where all variables are 16 bit and count operations allow wrap-around.
All comments are appreciated.
      / Björn

     =================================================================
    / Björn 'Mr Bear' Berglöf
   /  Xelerated:   08  - 506 257 94  mailto:[email-masked]
  /   Mobile:      0733- 277 808     http://www.mrbear.se
 /    Home office: 08  - 532 532 69  mailto:[email-masked]
=================================================================

---

From: "Yaakov Stein" <[email-masked]>
Date: Wed, 3 Mar 2004 15:46:29 +0200

> "the packet is in order" ? I.e, Should the 
> expected_sequence_number be updated if the sequence number i 0 ?

Passes the sequence number check == is in order == has not arrived
later than a packet sent earlier (although packets may be missing).

If the sequence number is zero, it is IMMEDIATELY incremented
before the test. After the test passes the expected sequence number
is incremented. If the test fails (i.e. the packet received was sent
earlier
than a packet previously received) then the epected number is not
incremented.
 
> QUESTION 2:
> ==========
> I enterpret this rather complex description above as a way to 
> map 16 bit behaviour into a 32 bit environment. As a hardware 
> designer I have a hard time convincing myself (and others) 
> that the above is equivalent to the following psueudo-code:
> 
>       diff = SeqNo - ExpNo;

You are have a hard time because it isn't the same.
You are checking for equality with the next packet number,
while the test in the draft is for equal OR AFTER the expected
sequence number.

Try thinking about it in the following way:

   if received = expected then
       treat packet as in-order 
       set expected = (received + 1) mod 2^16
   else
       calculate D = ( (expected-received) mod 2^16 ) - 2^15
       if D > 0 then
           packets expected, expected+1, ... received-1 have not been
received 
           set expected = (received + 1) mod 2^16
       else  
           late packet arrived
           do NOT update expected

Y(J)S