I am trying to keep last acknowledged numbers (most recent) for
both side of channel.
Currently i am using simpel check like if (last_ack <
new_ack_num ) && packet has ACK flag set, then update my last_ack .
So trying to update my last_ack only when i see *new* /next ack . But
this is not going to work if seq/ack numbers gets wrapped around.
because my condition should be exactly reversed of original and
should be (last_ack > new_ack_num). Till i see all the
acknowlegements upto FFFFFFFF and after that again it can be
(last_ack < new_ack_num ).

But i do not know how this can be done ?? Simple arithmatic does not
seem to .(Correct me if i am wrong). Looks like i need to use
some mechanism that TCP uses to detect SEQ number wrap around. But
again i do not know peer are using 2 different TCP implementation
which DETECTION scheme is used by TCP.(to detect SEQ number wrap
around ). Is there anything that some RFC enforces and all TCP
implemenations adhere to it.

I need a way to detect this wrap around and change my checking
conditions accordingly.

Anything u wud like to tell me ??

Thanks ,
Rohit

In article <1178778543.599186.16570@n59g2000hsh.googlegroups. com>,
Rohit <will.u.tellmemore@gmail.com> wrote:

> I am trying to keep last acknowledged numbers (most recent) for
> both side of channel.
> Currently i am using simpel check like if (last_ack <
> new_ack_num ) && packet has ACK flag set, then update my last_ack .
> So trying to update my last_ack only when i see *new* /next ack . But
> this is not going to work if seq/ack numbers gets wrapped around.
> because my condition should be exactly reversed of original and
> should be (last_ack > new_ack_num). Till i see all the
> acknowlegements upto FFFFFFFF and after that again it can be
> (last_ack < new_ack_num ).
>
> But i do not know how this can be done ?? Simple arithmatic does not
> seem to .(Correct me if i am wrong). Looks like i need to use
> some mechanism that TCP uses to detect SEQ number wrap around. But
> again i do not know peer are using 2 different TCP implementation
> which DETECTION scheme is used by TCP.(to detect SEQ number wrap
> around ). Is there anything that some RFC enforces and all TCP
> implemenations adhere to it.
>
> I need a way to detect this wrap around and change my checking
> conditions accordingly.
>
> Anything u wud like to tell me ??

Consider the sequence numbers as a circle, like a clock face. You want
to use clock arithmetic to tell whether new_ack is between last_ack and
last_ack + 2^31-1. What this translates to is:

if (last_ack <= 2^31)
if (new_ack > last_ack && new_ack <= last_ack+2^31-1)
else
if (new_ack > last_ack || new_ack < last_ack-2^31)

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***

"Barry Margolin" <barmar@alum.mit.edu> wrote in message
news:barmar-48F7FD.00134511052007@comcast.dca.giganews.com...
> In article <1178778543.599186.16570@n59g2000hsh.googlegroups. com>,
> Rohit <will.u.tellmemore@gmail.com> wrote:
>
>> I am trying to keep last acknowledged numbers (most recent) for
>> both side of channel.
>> Currently i am using simpel check like if (last_ack <
>> new_ack_num ) && packet has ACK flag set, then update my last_ack .
>> So trying to update my last_ack only when i see *new* /next ack . But
>> this is not going to work if seq/ack numbers gets wrapped around.
>> because my condition should be exactly reversed of original and
>> should be (last_ack > new_ack_num). Till i see all the
>> acknowlegements upto FFFFFFFF and after that again it can be
>> (last_ack < new_ack_num ).
>>
>> But i do not know how this can be done ?? Simple arithmatic does not
>> seem to .(Correct me if i am wrong). Looks like i need to use
>> some mechanism that TCP uses to detect SEQ number wrap around. But
>> again i do not know peer are using 2 different TCP implementation
>> which DETECTION scheme is used by TCP.(to detect SEQ number wrap
>> around ). Is there anything that some RFC enforces and all TCP
>> implemenations adhere to it.
>>
>> I need a way to detect this wrap around and change my checking
>> conditions accordingly.
>>
>> Anything u wud like to tell me ??
>
> Consider the sequence numbers as a circle, like a clock face. You want
> to use clock arithmetic to tell whether new_ack is between last_ack and
> last_ack + 2^31-1. What this translates to is:
>
> if (last_ack <= 2^31)
> if (new_ack > last_ack && new_ack <= last_ack+2^31-1)
> else
> if (new_ack > last_ack || new_ack < last_ack-2^31)

Won't work:

last_ack = 2147483648
new_ack = 0


if (2147483648 <= 2147483648) true
if (0> 2147483648 false
else
if (0 > 2147483648 false, or 0 < 0) false

Failed to detect even the most basic wrap around.

Here's a hint:

Try a ping pong approach, use negative and positive sequences numbers.

First positive, then switch to negative, use a large enough range to detect
wrap around from positive to negative or vice versa

Bye,
Skybuck.

In article <f255o2$gn1$1@news6.zwoll1.ov.home.nl>,
"Skybuck Flying" <spam@hotmail.com> wrote:

> "Barry Margolin" <barmar@alum.mit.edu> wrote in message
> news:barmar-48F7FD.00134511052007@comcast.dca.giganews.com...
> > In article <1178778543.599186.16570@n59g2000hsh.googlegroups. com>,
> > Rohit <will.u.tellmemore@gmail.com> wrote:
> >
> >> I am trying to keep last acknowledged numbers (most recent) for
> >> both side of channel.
> >> Currently i am using simpel check like if (last_ack <
> >> new_ack_num ) && packet has ACK flag set, then update my last_ack .
> >> So trying to update my last_ack only when i see *new* /next ack . But
> >> this is not going to work if seq/ack numbers gets wrapped around.
> >> because my condition should be exactly reversed of original and
> >> should be (last_ack > new_ack_num). Till i see all the
> >> acknowlegements upto FFFFFFFF and after that again it can be
> >> (last_ack < new_ack_num ).
> >>
> >> But i do not know how this can be done ?? Simple arithmatic does not
> >> seem to .(Correct me if i am wrong). Looks like i need to use
> >> some mechanism that TCP uses to detect SEQ number wrap around. But
> >> again i do not know peer are using 2 different TCP implementation
> >> which DETECTION scheme is used by TCP.(to detect SEQ number wrap
> >> around ). Is there anything that some RFC enforces and all TCP
> >> implemenations adhere to it.
> >>
> >> I need a way to detect this wrap around and change my checking
> >> conditions accordingly.
> >>
> >> Anything u wud like to tell me ??
> >
> > Consider the sequence numbers as a circle, like a clock face. You want
> > to use clock arithmetic to tell whether new_ack is between last_ack and
> > last_ack + 2^31-1. What this translates to is:
> >
> > if (last_ack <= 2^31)
> > if (new_ack > last_ack && new_ack <= last_ack+2^31-1)
> > else
> > if (new_ack > last_ack || new_ack < last_ack-2^31)
>
> Won't work:
>
> last_ack = 2147483648
> new_ack = 0
>
>
> if (2147483648 <= 2147483648) true
> if (0> 2147483648 false
> else
> if (0 > 2147483648 false, or 0 < 0) false
>
> Failed to detect even the most basic wrap around.

Those numbers are exactly halfway around the circle from each other.
It's ambiguous whether new_ack should be considred higher or lower than
last_ack when the difference is exactly 2^31.

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***

"Barry Margolin" <barmar@alum.mit.edu> wrote in message
news:barmar-BBA650.22164712052007@comcast.dca.giganews.com...
> In article <f255o2$gn1$1@news6.zwoll1.ov.home.nl>,
> "Skybuck Flying" <spam@hotmail.com> wrote:
>
>> "Barry Margolin" <barmar@alum.mit.edu> wrote in message
>> news:barmar-48F7FD.00134511052007@comcast.dca.giganews.com...
>> > In article <1178778543.599186.16570@n59g2000hsh.googlegroups. com>,
>> > Rohit <will.u.tellmemore@gmail.com> wrote:
>> >
>> >> I am trying to keep last acknowledged numbers (most recent) for
>> >> both side of channel.
>> >> Currently i am using simpel check like if (last_ack <
>> >> new_ack_num ) && packet has ACK flag set, then update my last_ack .
>> >> So trying to update my last_ack only when i see *new* /next ack . But
>> >> this is not going to work if seq/ack numbers gets wrapped around.
>> >> because my condition should be exactly reversed of original and
>> >> should be (last_ack > new_ack_num). Till i see all the
>> >> acknowlegements upto FFFFFFFF and after that again it can be
>> >> (last_ack < new_ack_num ).
>> >>
>> >> But i do not know how this can be done ?? Simple arithmatic does not
>> >> seem to .(Correct me if i am wrong). Looks like i need to use
>> >> some mechanism that TCP uses to detect SEQ number wrap around. But
>> >> again i do not know peer are using 2 different TCP implementation
>> >> which DETECTION scheme is used by TCP.(to detect SEQ number wrap
>> >> around ). Is there anything that some RFC enforces and all TCP
>> >> implemenations adhere to it.
>> >>
>> >> I need a way to detect this wrap around and change my checking
>> >> conditions accordingly.
>> >>
>> >> Anything u wud like to tell me ??
>> >
>> > Consider the sequence numbers as a circle, like a clock face. You want
>> > to use clock arithmetic to tell whether new_ack is between last_ack and
>> > last_ack + 2^31-1. What this translates to is:
>> >
>> > if (last_ack <= 2^31)
>> > if (new_ack > last_ack && new_ack <= last_ack+2^31-1)
>> > else
>> > if (new_ack > last_ack || new_ack < last_ack-2^31)
>>
>> Won't work:
>>
>> last_ack = 2147483648
>> new_ack = 0
>>
>>
>> if (2147483648 <= 2147483648) true
>> if (0> 2147483648 false
>> else
>> if (0 > 2147483648 false, or 0 < 0) false
>>
>> Failed to detect even the most basic wrap around.
>
> Those numbers are exactly halfway around the circle from each other.
> It's ambiguous whether new_ack should be considred higher or lower than
> last_ack when the difference is exactly 2^31.

There are two possibilities:

new_ack zero is an old ack..
new_ack zero is a new ack

Under normal circumstances, new_ack is a new acknowledgement.

Your code fails to detect it as a new valid acknowledgement.

Bye,
Skybuck.

"Barry Margolin" <barmar@alum.mit.edu> wrote in message
news:barmar-48F7FD.00134511052007@comcast.dca.giganews.com...
> In article <1178778543.599186.16570@n59g2000hsh.googlegroups. com>,
> Rohit <will.u.tellmemore@gmail.com> wrote:
>
>> I am trying to keep last acknowledged numbers (most recent) for
>> both side of channel.
>> Currently i am using simpel check like if (last_ack <
>> new_ack_num ) && packet has ACK flag set, then update my last_ack .
>> So trying to update my last_ack only when i see *new* /next ack . But
>> this is not going to work if seq/ack numbers gets wrapped around.
>> because my condition should be exactly reversed of original and
>> should be (last_ack > new_ack_num). Till i see all the
>> acknowlegements upto FFFFFFFF and after that again it can be
>> (last_ack < new_ack_num ).
>>
>> But i do not know how this can be done ?? Simple arithmatic does not
>> seem to .(Correct me if i am wrong). Looks like i need to use
>> some mechanism that TCP uses to detect SEQ number wrap around. But
>> again i do not know peer are using 2 different TCP implementation
>> which DETECTION scheme is used by TCP.(to detect SEQ number wrap
>> around ). Is there anything that some RFC enforces and all TCP
>> implemenations adhere to it.
>>
>> I need a way to detect this wrap around and change my checking
>> conditions accordingly.
>>
>> Anything u wud like to tell me ??
>
> Consider the sequence numbers as a circle, like a clock face. You want
> to use clock arithmetic to tell whether new_ack is between last_ack and
> last_ack + 2^31-1. What this translates to is:
>
> if (last_ack <= 2^31)
> if (new_ack > last_ack && new_ack <= last_ack+2^31-1)
> else
> if (new_ack > last_ack || new_ack < last_ack-2^31)

Let's look at this again assuming 2^31 is not the limit for sequence
numbers, but 2^32 is the limit.

last_ack = 2^32 -1 = 4294967295;
new_ack = 0;

if (last_ack <= 2^31)
false
if (new_ack > last_ack && new_ack <= last_ack+2^31-1)
skipped
else
if (new_ack > last_ack || new_ack < last_ack-2^31)
(0 > 4294967295=false) or (0 < 2147483647 = true )

With this new limit assumption it seems your code does work for now

Bye,
Skybuck.

I think Skybuck is right here.
But Skybuck , i still have not completely understood trick the you
have suggested with ping pong appoach. Can u elaborate more on that ??

"Rohit" <will.u.tellmemore@gmail.com> wrote in message
news:1179125480.313911.246680@u30g2000hsc.googlegr oups.com...
>I think Skybuck is right here.
> But Skybuck , i still have not completely understood trick the you
> have suggested with ping pong appoach. Can u elaborate more on that ??

// new idea/code:

// receiver:
if packet.number > 0 then
begin

// if in negative mode then
if last_accepted_number < 0 then
begin

// negative mode must be far enough for positive switch
// this is to prevent flipping back and furth between positive and
negative mode for when
// old packets happen to arrive.
if last_accepted_number < -1 000 000 000 then
begin
last_accepted_number := packet.number;
end;
end else
// normale positive mode...
if last_accept_number > 0 then
begin
if packet.number > last_accepted_number then
begin
last_accepted_number := packet.number;
end;
end;
end else
if packet.number < 0 then
begin
// same but vice versa.
if last_accepted_number > 0 then
begin
if last_accepted_number > +1 000 000 000 then
begin
last_accepted_number := packet.number;
end;
end else
// normal negative mode.
if last_accept_number < 0 then
begin
if packet.number < last_accepted_number then
begin
last_accepted_number := packet.number;
end;
end;
end;

// sender:

if packet.number > 0 then
begin
if packet.number = MaxInt then
begin
packet.number := -1; // switch to negative.
end else
begin
packet.number := packet.number + 1;
end;
end else
if packet.number < 0 then
begin
if packet.number = -MaxInt then
begin
packet.number := +1; // switch to positive
end else
begin
packet.number := packet.number - 1;
end;
end;

I have added a new idea as I write this code... I haven't tested the new
idea yet but it should work and improve on the idea.

The new part is to make sure the positive or negative mode has passed a
certain number before switching to negative or positive mode is allowed...

Otherwise it would be possible that it would switch back from positive to
negative or vice versa mode because of an old positive packet which came to
late etc.. for example the old code/idea looked like:

if packet.number > 0 then
begin
if packet.number > last_accepted_number then
begin
last_accepted_number := packet.number;
end;
end;

if packet.number < 0 then
begin
if packet.number < last_accepted_number then
begin
last_accepted_number := packet.number;
end;
end;

This old code could create a little problem, for example:

PacketNumber: MaxInt
PacketNumber: -1
OldPacketNumber: MaxInt arrives double..

Now it switches back from negative to positive again... which is not really
that good...

Now that should be prevented because first a billion positive or negative
packet numbers should have arrived.... so then it's highly likely that no
more "opposite" packet will arrive.

Pretty cool code, and pretty simply to understand.

The objective of the code is too only accept the higher packet numbers
compared to the last known accepted packet number.

This could be interesting for tcp, since tcp uses an cumilative ack... or
something like... that last ack can acknowledge multiple
segment/packets/bytes up to a certain point.

Further more... it will take:

1 000 000 000 billion packets to reach a point where a switch would be
allowed.

There is room for maxint - 1 000 000 billion packets to go lost as long as
the 1 000 000 000 + 1 packet is still received.. the switch will happen...
otherwise the receiver will never enter the negative mode and will have to
wait until the sender returns to positive mode if he ever returns

So the old code has an adventage there and doesn't have that problem but
does have the flipping problem around the wrapping point.

Then it takes another billion packets before another switch from negative to
positive can be made.

So at least 2 billion packets of room... actually still 4 billion since the
sender wraps at the fartest point.

And finally packet number 0 is not to be used.

Using the packet number as an offset now becomes difficult... if one is just
looking to acknowledge a packet number then it's still ok.

Instead of 1 000 000 00 I would use: MaxInt div 2.

Give it a try I would say

For my own file transer protocols I would never use a wrapping technique...
but for other less important stuff, it's pretty nice.

Bye,
Skybuck.

Update:

more efficient code for receiver, completely untested, but should work,
probably also easier to understand/cleaner

// initialization:

last_accepted_number := 0;
packet_number := 1; // start with 1

// receiver:

// if in positive mode then, make exception for zero to get algo started.
if last_accepted_number >= 0 then
begin
// check for normal positive situation.
if packet_number > last_accepted_number then
begin
last_accepted_number := packet_number;
end else
// else check for switch to negative
if packet_number < 0 then
begin
// switch only allowed if we were in positive mode for a while.
// to make "sure" any old negative low number packets are out of the
network
if last_accepted_number > 1 000 000 000 then
begin
last_accepted_number := packet_number;
end;
end;

end else
// if in negative mode then
if last_accepted_number < 0 then
begin

// check for normal negative situation
if packet_number < last_accepted_number then
begin
last_accepted_number := packet_number;
end else
if packet_number > 0 then
begin
// switch only allowed if we were in negative mode for a while
// to make "sure" any old positive low number packets are out of the
network
if last_accepted_number < -1 000 000 000 then
begin
last_accepted_number := packet_number;
end;
end;

end;

// code for sender remains the same.

Bye,
Skybuck.

"Skybuck Flying" <spam@hotmail.com> wrote in message
news:f298qb$u2i$1@news4.zwoll1.ov.home.nl...
> Update:
>
> more efficient code for receiver, completely untested, but should work,
> probably also easier to understand/cleaner
>
> // initialization:
>
> last_accepted_number := 0;
> packet_number := 1; // start with 1
>
> // receiver:
>
> // if in positive mode then, make exception for zero to get algo started.
> if last_accepted_number >= 0 then
> begin
> // check for normal positive situation.
> if packet_number > last_accepted_number then
> begin
> last_accepted_number := packet_number;
> end else
> // else check for switch to negative
> if packet_number < 0 then
> begin
> // switch only allowed if we were in positive mode for a while.
> // to make "sure" any old negative low number packets are out of the
> network
> if last_accepted_number > 1 000 000 000 then

I like it better this way, equal too:

if last_accepted_number >= 1 000 000 000 then

> begin
> last_accepted_number := packet_number;
> end;
> end;
>
> end else
> // if in negative mode then
> if last_accepted_number < 0 then
> begin
>
> // check for normal negative situation
> if packet_number < last_accepted_number then
> begin
> last_accepted_number := packet_number;
> end else
> if packet_number > 0 then
> begin
> // switch only allowed if we were in negative mode for a while
> // to make "sure" any old positive low number packets are out of the
> network
> if last_accepted_number < -1 000 000 000 then

I like it better this way, equal too:

if last_accepted_number <= -1 000 000 000 then


> begin
> last_accepted_number := packet_number;
> end;
> end;
>
> end;
>
> // code for sender remains the same.
>
> Bye,
> Skybuck.
>

Little update.

Bye,
Skybuck.

Further improvements otherwise I don't sleep well and to get some more
closure on this, and in case you can't figure out the improvements yourself:

Making exception for last message 0 could be bad in case the sender doesn't
use restart per receiver and just uses one seq number... unlikely though...
but still... better to initialize
last_accepted_number with the first number received... when
last_accepted_number is zero that indicates no packets were received yet so
that can be used to initialize it as follows:

Also comments little bit improved.

// initialization:

last_accepted_number := 0;
packet_number := 1; // start with 1

// receiver:

// if in positive mode then
if last_accepted_number > 0 then
begin
// check for normal positive situation.
if packet_number > last_accepted_number then
begin
last_accepted_number := packet_number;
end else
// else check for switch to negative
if packet_number < 0 then
begin
// switch only allowed if we were in positive mode for a while.
// to make "sure" any old negative low number packets are out of the
network
if last_accepted_number >= 1 000 000 000 then
begin
last_accepted_number := packet_number;
end;
end;

end else
// if in negative mode then
if last_accepted_number < 0 then
begin

// check for normal negative situation
if packet_number < last_accepted_number then
begin
last_accepted_number := packet_number;
end else
// else check for switch to positive
if packet_number > 0 then
begin
// switch only allowed if we were in negative mode for a while
// to make "sure" any old positive high number packets are out of the
network
if last_accepted_number <= -1 000 000 000 then
begin
last_accepted_number := packet_number;
end;
end;

end else
// if no numbers received yet (last_accepted_number is 0) then
if last_accepted_number = 0 then
begin
// initialize last_accepted_number with first packet number received, to
match the mode of the sender.
last_accepted_number := packet_number;
end;

Also little improvement for sender... I hope you would have figured it
out... that if you really wanna match it with tcp... that's probably
possible...

maybe you would have to change the algorithm a little bit to go from high
negative to low negative instead of vice versa.. but I don't care about
tcp... so that's up to you to figure out.

And finally to squeeze one more packet number out of it... I think negative
integers have one more value... so substract one from the negative maxint.

// sender:

if packet.number > 0 then
begin
if packet.number = MaxInt then
begin
packet.number := -1; // switch to negative.
end else
begin
packet.number := packet.number + 1;
end;
end else
if packet.number < 0 then
begin
if packet.number = (-MaxInt)-1 then
begin
packet.number := +1; // switch to positive
end else
begin
packet.number := packet.number - 1;
end;
end;

There that should do it.

Now if you don't like it go fuck yourself ! =D

Bye,
Skybuck.

Barry Margolin <barmar@alum.mit.edu> writes:

> if (last_ack <= 2^31)
> if (new_ack > last_ack && new_ack <= last_ack+2^31-1)
> else
> if (new_ack > last_ack || new_ack < last_ack-2^31)

I feel like I'm missing something. Isn't this just

if ((s32)((u32)new_ack - (u32)last_ack) > 0)

? That's the "traditional" wrap protected greater than.

-don