[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [PWE3] 16 bit interpretation of sequence checking?
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: Bjorn.Berglof@xelerated.com
> [mailto:Bjorn.Berglof@xelerated.com]
> 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:yaakov_s@rad.com]
> > 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:bjorn.berglof@xelerated.com
> > > / Mobile: 0733- 277 808 http://www.mrbear.se
> > > / Home office: 08 - 532 532 69 mailto:bjorn@mrbear.se
> > > =================================================================
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > > -----Original Message-----
> > > > From: Yaakov Stein [mailto:yaakov_s@rad.com]
> > > > Sent: Wednesday, March 03, 2004 14:46
> > > > To: Bj?rn Bergl?f; pwe3@ietf.org
> > > > 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:yaakov_s@rad.com]
> Sent: Wednesday, March 03, 2004 14:46
> To: Björn Berglöf; pwe3@ietf.org
> 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:bjorn.berglof@xelerated.com
/ Mobile: 0733- 277 808 http://www.mrbear.se
/ Home office: 08 - 532 532 69 mailto:bjorn@mrbear.se
=================================================================
>
_______________________________________________
pwe3 mailing list
pwe3@ietf.org
https://www1.ietf.org/mailman/listinfo/pwe3