Subject: RE: 16 bit interpretation of sequence checking?

From: Björn Berglöf <[email-masked]>
Date: Mon, 29 Mar 2004 10:24:59 +0200

For completeness, I want to share that the algorithm in 
"draft-ietf-pwe3-atm-encap-04.txt" CAN be simplified 
using pure 16 bit arithmetic in stead of assuming 32 bit 
logic and having to use cumbersome range checking.

    diff <- SeqNo - ExpNo;
    if ((SeqNo=0) or (diff[15]=0) then OK<-True;
    else OK<-False;
    end if;
    if (OK=True) then NewExpNo <- (SeqNo=FFFFh) ? 1 : SeqNo+1;
    end if;

Regards,
    / Björn

-------------------------------------------------
OK, in that case I think it is all right. 

Of course, if SeqNo=0 then there is no need to compute
diff or to check its sign, but that might not matter in your case.

Y(J)S

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] 
> Sent: Tuesday, March 09, 2004 15:18
> To: Yaakov Stein
> Cc: Bj?rn Bergl?f
> Subject: Again: Still do not get the difference; 16 bit 
> interpretation of sequence checking?
> 
> 
> Thanks Yaakov,
> I think we are closer to understand each other...
> First to answer your questions/comments:
> 
>  - I see your point about using side-effects. They are 
>    however inpractical in hardware modelling languages,
>    while multi-output functions is sort of 'normal'.
> 
>  - I also see that our different understandings of the code comes 
>    from this difference in sequential/parallel views of the world. 
>    As you may note the 'SeqNo' never changes value during the 
>    evaluation of the function. Rather the NewExpNo is 'saved'
>    and used next time the function is called.
> 
>  - Yes I assume bit 15 is MSB.
>    But my code uses unsigned logic which means that the 
>    number should be interpreded as 0->65536. (However signed 
>    (2-complement) or unsigned does not matter in my code since
>    I look at subtraction bits directly, not using outcome
>    of status bits.)
> 
>  - You probably noticed that I avoid the '-2^15' stuff in your
>    code since it will only invert the bit 15. 
> 
>  - I actually meant => to mean "leads to" or "results in".
>    Rather sloppy writing actually.
> 
> > First, you are missing the following in each update of the expected 
> > number
> >   NewExpNo <- SeqNo+1
> >   (NewExpNo = 0) => NewExpNo <- 1
> 
>  - No, I do not believe I missed that. In my original psueudo-code
>    I use a ? : operator whenever I set the new sequence value which
>    takes care of the 'skip-the-zero-in-a-sequence', only I check
>    for the FFFFh value in stead of doing 'inc' and then check for 
>    zero (again because it is more effective H/W-wise). Same, yes ? 
> 
>  - Regarding late packets, I do not reorder any packets. The aim
>    is mainly to simplify the sequence check operation, when the 
>    rate is very high and the number of sequency counters are high.
>    The H/W function will only return the OK/Not-OK back to the 
>    processor. 
> 
>  - Rewriting my psueudo-code in line with your terminology:
> 
>    diff <- SeqNo - ExpNo;
>    if ((SeqNo=0) or (diff[15]=0) then OK<-True;
>    else OK<-False;
>    end if;
>    if (OK=True) then NewExpNo <- (SeqNo=FFFFh) ? 1 : SeqNo+1;
>    end if;
> 
> Given the claerifications above, have I still missed something?
> Best regards,
>     / Bj?rn
> 
> 
> 
> > -----Original Message-----
> > From: Yaakov Stein [mailto:[email-masked]]
> > Sent: Sunday, March 07, 2004 07:49
> > To: Bj?rn Bergl?f
> > Subject: RE: Still do not get the difference; 16 bit 
> interpretation of 
> > sequence checking?
> > 
> > 
> > Bjorn,
> >  
> > 
> > > Hi,
> > > thanks for your reply. I've still a bit confused; hope it's OK to 
> > > send a follow-up question 'off-line'.
> > 
> > Of course !
> > 
> > 
> > > First a question:
> > >  Do you not mean (received-expected) in stead of
> > >  (expected-received) in your psueudo-code ?
> > 
> > ooops!  yes, that is right.
> > 
> > >  That would fit better withe the paper and my thinking.
> > >  Anyway, I asume that in the following...
> > > 
> > > I'm a bit confused of your uses of 'IMMEDIATELY' and 'AFTER'.
> > > The way I see it is that sequence checking is a function with two 
> > > input data and two output data:
> > >    
> > >    SeqNo     : The packet seq number. (16b)
> > >    ExpNo     : The saved value between packet processings. (16b)
> > >    OK        : Pass/Packet is in order. Controls what to do with 
> > >                the packet. (1b)
> > >    NewExpNo  : Updated value to be saved. (16b)
> > 
> > OK, although I would think of it as a function returning an 
> OK value, 
> > and updating the ExpNo, i.e.
> >      function IsCorrectSN( in RecSeqNo, inout ExpNo) : boolean
> > 
> > > 
> > > Given this, I can not see any difference between mine 
> psueudo-code 
> > > and yours :
> > > 
> > > ---------------------------- Equality case. Same, yes ?
> > > Mine:
> > >    (SeqNo=ExpNo) => Diff=0 => Diff bit 15=0 => 
> > >    OK=1, NewExpNo=SeqNo+1.
> > > Yours:
> > >    if received = expected then 
> > >         treat packet as in-order 
> > >         set expected = (received + 1) mod 2^16
> > 
> > To ensure that this is the same I have to understand your 
> erminology. 
> > I assume that bit 15 is the MSB of a 16 bit register  (i.e. 
> the LSB is 
> > numbered 0) and that you are using 2s complement 
> arithmetic, and that 
> > 1 is considered "true".
> > Furthermore, I assume that => means if .. then and = means equality 
> > check (not asignment).
> > Then there shouldn't be so many => (causes) but rather separate 
> > assignment statements (I use <- to mean assignment).
> > 
> >   Diff <- (SeqNo-ExpNo)
> >   Diff = 0 => OK <- 1; NewExpNo <- SeqNo+1
> > 
> > > ----------------------------- In-order case. Same, yes ?
> > > Mine:
> > >    (SeqNo-ExpNo) => Diff is positive => Diff bit 15=0 =>
> > >    OK=1, NewExpNo=SeqNo+1.
> > > 
> > > Yours:
> > >     calculate D = ((received-expected) 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
> > 
> > Do you mean the following?
> > 
> >   Diff <- (SeqNo-ExpNo)
> >   Diff bit 15 = 0 => OK <- 1; NewExpNo <- SeqNo+1
> >  
> > > ----------------------------- Out-of-order case. Same, yes ?
> > > Mine:
> > >     (SeqNo-ExpNo) => Diff is negative => Diff bit 15=1
> > >     OK=0;
> > > 
> > > Yuors
> > >     calculate D = ((received-expected) mod 2^16 ) - 2^15
> > >     if D > 0 then  ...
> > >     else  
> > >             late packet arrived
> > >             do NOT update expected
> > 
> >   Diff bit 15 = 1  => OK=0;
> >  
> > > ------------------------------------------------------------------
> > > 
> > > Please help me see in which aspect the codes differ. Since we are 
> > > looking at implementing this in hardware (to support 100M 
> checks/s 
> > > or so) it is important that no mistakes slips through.
> > 
> > First, you are missing the following in each update of the expected 
> > number
> >   NewExpNo <- SeqNo+1
> >   (NewExpNo = 0) => NewExpNo <- 1
> > 
> > Second, this handles the sequence numbers, but what do you do about 
> > late packets?
> > Do you allow them (and re-order) if they are still "in time" ?
> > 
> > 
> > > 
> > > Best regards,
> > >      / 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]
> > > =================================================================
> > >  
> > > 
> > > 
> > > 
> > > 
> > > 
> > > 
> > > 
> > > 
> > > 
> > > > -----Original Message-----
> > > > From: Yaakov Stein [mailto:[email-masked]]
> > > > Sent: Wednesday, March 03, 2004 14:46
> > > > To: Bj?rn Bergl?f; [email-masked]
> > > > Subject: RE: [PWE3] 16 bit interpretation of sequence checking?
> > > > 
> > > > 
> > > > > 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 ?
> > > > 
> > > > 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;
> > > > >       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.
> > > > 
> > > > 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
> > > > 
> > > > 
> > > 
> > > 
> > 
> 
> 

> -----Original Message-----
> From: Yaakov Stein [mailto:[email-masked]] 
> Sent: Wednesday, March 03, 2004 14:46
> To: Björn Berglöf; [email-masked]
> Subject: RE: [PWE3] 16 bit interpretation of sequence checking?
> 
> 
> > 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 ?
> 
> 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;
> >       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.
> 
> 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
> 

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]
=================================================================