Subject: Re: [manet] 802.11 - minor optimization

From: Yang Xiao <[email-masked]>
Date: Tue, 15 Apr 2003 13:22:21 -0700 (PDT)

nitin

I am sorry that my response to this email is quick late.

I read your email today and feel that I can not understand your
argument. I might be missing something.

In your example, 

> and 1, 2, 3, 4 with the new modification.
  
> With the modification:
> 
>    A will transmit DIFS + 0 slot after current transmission ends.
>    B will transmit DIFS + 0 slot after A's transmission.
>    C will transmit DIFS + 0 slot after B's transmission.
>    D will transmit DIFS + 0 slot after C's transmission.

I am not sure how you get above observations. Since the backoff counter
is stopped when busy, it seems to me that the above argument might not
be correct. It seems to me that

    A will transmit DIFS + 1 slot after current transmission ends.
    B will transmit DIFS + 1 slot after A's transmission.
    C will transmit DIFS + 1 slot after B's transmission.
    D will transmit DIFS + 1 slot after C's transmission.

Therefore, backoff [1 CW] seems to me "did not gain 1 slot"

I might be wrong. Please let me know.

Sorry for the late response

Best Regards

Yang

--- "Nitin H. Vaidya" <[email-masked]> wrote:
> 
> Hello all:
> 
> Anyone on the list from 802.11 standards group ?
> Here is a trivial idea worth 2 cents (more like 5%) ...
> 
> A simple optimization for 802.11 that might improve
> performance 5% without any real change to the protocol :
> 
> As I understand 802.11 DCF, the backoff intervals are chosen
> in the range of [0,CW] and then the backoff counter is
> decremented at the END of each idle slot. Transmit immediately
> when counter reaches 0.
> 
> Suggested modification:
> 
>   Choose backoff interval in the range [1,cw], and decrement
>   backoff counter at the START of each slot. Transmit immediately
>   when counter reaches 0.
> 
> CW in 802.11 is specifed as 2^k-1 for interger k. With the above
> change CW should be simply 2^k so that the range of values
> for backoff remains same as 802.11 (or, to put it differently,
> choose new backoff as 802.11 backoff + 1).
> 
> Unless I am mistaken, the above change can save 1 idle
> slot for each transmitted packets (with some exceptions).
> 
> To see this consider the case when 4 nodes (A, B, C, D) receive
> a packet from upper layers while the channel is busy. Let us say that
> they choose backoff intervals 0, 1, 2, 3 with the original 802.11,
> and 1, 2, 3, 4 with the new modification.
> 
> In the original 802.11:
> 
>    A will transmit DIFS + 0 slot after current transmission ends.
>    B will transmit DIFS + 1 slot after A's transmission.
>    C will transmit DIFS + 1 slot after B's transmission.
>    D will transmit DIFS + 1 slot after C's transmission.
> 
> With the modification:
> 
>    A will transmit DIFS + 0 slot after current transmission ends.
>    B will transmit DIFS + 0 slot after A's transmission.
>    C will transmit DIFS + 0 slot after B's transmission.
>    D will transmit DIFS + 0 slot after C's transmission.
> 
> So we save 1 slot for each of the last 3 transmissions -- in general,
> 1 slot may be saved whenever a non-zero backoff counter is chosen
> by original 802.11 for a packet that arrives on a busy channel.
> 
> Any reason not to use the above modification to 802.11 ?
> About 5 minutes of thought went into this suggestion, so if there
> is a bug in my argument, feel free to point it out.
> 
> Happy holidays!
> 
> - nitin
> 
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet

__________________________________________________
Do you Yahoo!?
The New Yahoo! Search - Faster. Easier. Bingo
http://search.yahoo.com
_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Nitin H. Vaidya" <[email-masked]>
Date: Tue, 15 Apr 2003 15:40:53 -0500 (CDT)

Yang:

On Tue, 15 Apr 2003, Yang Xiao wrote:

.  >>nitin
.  >>
.  >>I am sorry that my response to this email is quick late.
.  >>
.  >>I read your email today and feel that I can not understand your
.  >>argument. I might be missing something.
.  >>
.  >>In your example, 
.  >>
.  >>> and 1, 2, 3, 4 with the new modification.
.  >>  
.  >>> With the modification:
.  >>> 
.  >>>    A will transmit DIFS + 0 slot after current transmission ends.
.  >>>    B will transmit DIFS + 0 slot after A's transmission.
.  >>>    C will transmit DIFS + 0 slot after B's transmission.
.  >>>    D will transmit DIFS + 0 slot after C's transmission.
.  >>
.  >>I am not sure how you get above observations. Since the backoff counter
.  >>is stopped when busy, it seems to me that the above argument might not
.  >>be correct. It seems to me that
.  >>
.  >>    A will transmit DIFS + 1 slot after current transmission ends.

Node A decrements at the START of an idle slot (so it will decrement after
DIFS interval, reach 0 at that time, and transmit).
- nitin

.  >>    B will transmit DIFS + 1 slot after A's transmission.
.  >>    C will transmit DIFS + 1 slot after B's transmission.
.  >>    D will transmit DIFS + 1 slot after C's transmission.
.  >>
.  >>Therefore, backoff [1 CW] seems to me "did not gain 1 slot"
.  >>
.  >>I might be wrong. Please let me know.
.  >>
.  >>Sorry for the late response
.  >>
.  >>Best Regards
.  >>
.  >>Yang
.  >>
.  >>
.  >>--- "Nitin H. Vaidya" <[email-masked]> wrote:
.  >>> 
.  >>> Hello all:
.  >>> 
.  >>> Anyone on the list from 802.11 standards group ?
.  >>> Here is a trivial idea worth 2 cents (more like 5%) ...
.  >>> 
.  >>> A simple optimization for 802.11 that might improve
.  >>> performance 5% without any real change to the protocol :
.  >>> 
.  >>> As I understand 802.11 DCF, the backoff intervals are chosen
.  >>> in the range of [0,CW] and then the backoff counter is
.  >>> decremented at the END of each idle slot. Transmit immediately
.  >>> when counter reaches 0.
.  >>> 
.  >>> Suggested modification:
.  >>> 
.  >>>   Choose backoff interval in the range [1,cw], and decrement
.  >>>   backoff counter at the START of each slot. Transmit immediately
.  >>>   when counter reaches 0.
.  >>> 
.  >>> CW in 802.11 is specifed as 2^k-1 for interger k. With the above
.  >>> change CW should be simply 2^k so that the range of values
.  >>> for backoff remains same as 802.11 (or, to put it differently,
.  >>> choose new backoff as 802.11 backoff + 1).
.  >>> 
.  >>> Unless I am mistaken, the above change can save 1 idle
.  >>> slot for each transmitted packets (with some exceptions).
.  >>> 
.  >>> To see this consider the case when 4 nodes (A, B, C, D) receive
.  >>> a packet from upper layers while the channel is busy. Let us say that
.  >>> they choose backoff intervals 0, 1, 2, 3 with the original 802.11,
.  >>> and 1, 2, 3, 4 with the new modification.
.  >>> 
.  >>> In the original 802.11:
.  >>> 
.  >>>    A will transmit DIFS + 0 slot after current transmission ends.
.  >>>    B will transmit DIFS + 1 slot after A's transmission.
.  >>>    C will transmit DIFS + 1 slot after B's transmission.
.  >>>    D will transmit DIFS + 1 slot after C's transmission.
.  >>> 
.  >>> With the modification:
.  >>> 
.  >>>    A will transmit DIFS + 0 slot after current transmission ends.
.  >>>    B will transmit DIFS + 0 slot after A's transmission.
.  >>>    C will transmit DIFS + 0 slot after B's transmission.
.  >>>    D will transmit DIFS + 0 slot after C's transmission.
.  >>> 
.  >>> So we save 1 slot for each of the last 3 transmissions -- in general,
.  >>> 1 slot may be saved whenever a non-zero backoff counter is chosen
.  >>> by original 802.11 for a packet that arrives on a busy channel.
.  >>> 
.  >>> Any reason not to use the above modification to 802.11 ?
.  >>> About 5 minutes of thought went into this suggestion, so if there
.  >>> is a bug in my argument, feel free to point it out.
.  >>> 
.  >>> Happy holidays!
.  >>> 
.  >>> - nitin
.  >>> 
.  >>> _______________________________________________
.  >>> manet mailing list
.  >>> [email-masked]
.  >>> https://www1.ietf.org/mailman/listinfo/manet
.  >>
.  >>
.  >>__________________________________________________
.  >>Do you Yahoo!?
.  >>The New Yahoo! Search - Faster. Easier. Bingo
.  >>http://search.yahoo.com
.  >>

---

From: Yang Xiao <[email-masked]>
Date: Tue, 15 Apr 2003 15:02:13 -0700 (PDT)

Nitin

Thanks for the comments. 

Now I understand your point.

You are saying that instead of 

"Decrementing backoff counter at the END of each slot. Transmit in the
next slot if it reaches zero"

you modify it as 

"Decrement backoff counter at the START of each slot. Transmit
immediately when counter reaches 0."

However, as for my impression, the device may not sense that "fast" so
that it can not sense the channel idle and transmit at the same slot.
It will takes D1 time that the device to get a conclusion that the slot
is idle. D1<a slot time. Then the device needs to change from a
"listening status" to a "transmitting status" which is called
"turned-around time". The time (D1+ the turned around time) is almost a
slot time. Therefore, the earliest time to transmit is the next slot
time.

In summary, it is because of the physical implementation limitation
that your modification might not work. I may be wrong.
 
I hope I explain it clear, but I might be wrong.

Please let me if you think me wrong. 

Thanks

Best Regards

Yang

---

From: "Nitin H. Vaidya" <[email-masked]>
Date: Tue, 15 Apr 2003 18:19:33 -0500 (CDT)

.  >>Nitin
.  >>
.  >>Thanks for the comments. 
.  >>
.  >>Now I understand your point.
.  >>
.  >>You are saying that instead of 
.  >>
.  >>"Decrementing backoff counter at the END of each slot. Transmit in the
.  >>next slot if it reaches zero"
.  >>
.  >>you modify it as 
.  >>
.  >>"Decrement backoff counter at the START of each slot. Transmit
.  >>immediately when counter reaches 0."
.  >>
.  >>However, as for my impression, the device may not sense that "fast" so
.  >>that it can not sense the channel idle and transmit at the same slot.
.  >>It will takes D1 time that the device to get a conclusion that the slot
.  >>is idle. D1<a slot time. Then the device needs to change from a
.  >>"listening status" to a "transmitting status" which is called
.  >>"turned-around time". The time (D1+ the turned around time) is almost a
.  >>slot time. Therefore, the earliest time to transmit is the next slot
.  >>time.
.  >>
.  >>In summary, it is because of the physical implementation limitation
.  >>that your modification might not work. I may be wrong.
.  >> 
.  >>I hope I explain it clear, but I might be wrong.

With current 802.11, a node can in fact choose backoff interval = 0
for a packet. So, whenever current 802.11 would decide to
transmit with backoff =0 (after DIFS), is the time when the backoff
would be decremented with the modification I was suggesting. I do not have
the 802.11 specs handy, but I vaguely recall that the D1 interval is
already built into the IFSs.
- nitin

.  >>
.  >>Please let me if you think me wrong. 
.  >>
.  >>Thanks
.  >>
.  >>Best Regards
.  >>
.  >>Yang
.  >>
.  >> 
.  >> 
.  >> 
.  >>--- "Nitin H. Vaidya" <[email-masked]> wrote:
.  >>> 
.  >>> Yang:
.  >>> 
.  >>> On Tue, 15 Apr 2003, Yang Xiao wrote:
.  >>> 
.  >>> .  >>nitin
.  >>> .  >>
.  >>> .  >>I am sorry that my response to this email is quick late.
.  >>> .  >>
.  >>> .  >>I read your email today and feel that I can not understand your
.  >>> .  >>argument. I might be missing something.
.  >>> .  >>
.  >>> .  >>In your example, 
.  >>> .  >>
.  >>> .  >>> and 1, 2, 3, 4 with the new modification.
.  >>> .  >>  
.  >>> .  >>> With the modification:
.  >>> .  >>> 
.  >>> .  >>>    A will transmit DIFS + 0 slot after current transmission
.  >>> ends.
.  >>> .  >>>    B will transmit DIFS + 0 slot after A's transmission.
.  >>> .  >>>    C will transmit DIFS + 0 slot after B's transmission.
.  >>> .  >>>    D will transmit DIFS + 0 slot after C's transmission.
.  >>> .  >>
.  >>> .  >>I am not sure how you get above observations. Since the backoff
.  >>> counter
.  >>> .  >>is stopped when busy, it seems to me that the above argument
.  >>> might not
.  >>> .  >>be correct. It seems to me that
.  >>> .  >>
.  >>> .  >>    A will transmit DIFS + 1 slot after current transmission
.  >>> ends.
.  >>> 
.  >>> Node A decrements at the START of an idle slot (so it will decrement
.  >>> after
.  >>> DIFS interval, reach 0 at that time, and transmit).
.  >>> - nitin
.  >>> 
.  >>> .  >>    B will transmit DIFS + 1 slot after A's transmission.
.  >>> .  >>    C will transmit DIFS + 1 slot after B's transmission.
.  >>> .  >>    D will transmit DIFS + 1 slot after C's transmission.
.  >>> .  >>
.  >>> .  >>Therefore, backoff [1 CW] seems to me "did not gain 1 slot"
.  >>> .  >>
.  >>> .  >>I might be wrong. Please let me know.
.  >>> .  >>
.  >>> .  >>Sorry for the late response
.  >>> .  >>
.  >>> .  >>Best Regards
.  >>> .  >>
.  >>> .  >>Yang
.  >>> .  >>
.  >>> .  >>
.  >>> .  >>--- "Nitin H. Vaidya" <[email-masked]> wrote:
.  >>> .  >>> 
.  >>> .  >>> Hello all:
.  >>> .  >>> 
.  >>> .  >>> Anyone on the list from 802.11 standards group ?
.  >>> .  >>> Here is a trivial idea worth 2 cents (more like 5%) ...
.  >>> .  >>> 
.  >>> .  >>> A simple optimization for 802.11 that might improve
.  >>> .  >>> performance 5% without any real change to the protocol :
.  >>> .  >>> 
.  >>> .  >>> As I understand 802.11 DCF, the backoff intervals are chosen
.  >>> .  >>> in the range of [0,CW] and then the backoff counter is
.  >>> .  >>> decremented at the END of each idle slot. Transmit immediately
.  >>> .  >>> when counter reaches 0.
.  >>> .  >>> 
.  >>> .  >>> Suggested modification:
.  >>> .  >>> 
.  >>> .  >>>   Choose backoff interval in the range [1,cw], and decrement
.  >>> .  >>>   backoff counter at the START of each slot. Transmit
.  >>> immediately
.  >>> .  >>>   when counter reaches 0.
.  >>> .  >>> 
.  >>> .  >>> CW in 802.11 is specifed as 2^k-1 for interger k. With the
.  >>> above
.  >>> .  >>> change CW should be simply 2^k so that the range of values
.  >>> .  >>> for backoff remains same as 802.11 (or, to put it differently,
.  >>> .  >>> choose new backoff as 802.11 backoff + 1).
.  >>> .  >>> 
.  >>> .  >>> Unless I am mistaken, the above change can save 1 idle
.  >>> .  >>> slot for each transmitted packets (with some exceptions).
.  >>> .  >>> 
.  >>> .  >>> To see this consider the case when 4 nodes (A, B, C, D)
.  >>> receive
.  >>> .  >>> a packet from upper layers while the channel is busy. Let us
.  >>> say that
.  >>> .  >>> they choose backoff intervals 0, 1, 2, 3 with the original
.  >>> 802.11,
.  >>> .  >>> and 1, 2, 3, 4 with the new modification.
.  >>> .  >>> 
.  >>> .  >>> In the original 802.11:
.  >>> .  >>> 
.  >>> .  >>>    A will transmit DIFS + 0 slot after current transmission
.  >>> ends.
.  >>> .  >>>    B will transmit DIFS + 1 slot after A's transmission.
.  >>> .  >>>    C will transmit DIFS + 1 slot after B's transmission.
.  >>> .  >>>    D will transmit DIFS + 1 slot after C's transmission.
.  >>> .  >>> 
.  >>> .  >>> With the modification:
.  >>> .  >>> 
.  >>> .  >>>    A will transmit DIFS + 0 slot after current transmission
.  >>> ends.
.  >>> .  >>>    B will transmit DIFS + 0 slot after A's transmission.
.  >>> .  >>>    C will transmit DIFS + 0 slot after B's transmission.
.  >>> .  >>>    D will transmit DIFS + 0 slot after C's transmission.
.  >>> .  >>> 
.  >>> .  >>> So we save 1 slot for each of the last 3 transmissions -- in
.  >>> general,
.  >>> .  >>> 1 slot may be saved whenever a non-zero backoff counter is
.  >>> chosen
.  >>> .  >>> by original 802.11 for a packet that arrives on a busy
.  >>> channel.
.  >>> .  >>> 
.  >>> .  >>> Any reason not to use the above modification to 802.11 ?
.  >>> .  >>> About 5 minutes of thought went into this suggestion, so if
.  >>> there
.  >>> .  >>> is a bug in my argument, feel free to point it out.
.  >>> .  >>> 
.  >>> .  >>> Happy holidays!
.  >>> .  >>> 
.  >>> .  >>> - nitin
.  >>> .  >>> 
.  >>> .  >>> _______________________________________________
.  >>> .  >>> manet mailing list
.  >>> .  >>> [email-masked]
.  >>> .  >>> https://www1.ietf.org/mailman/listinfo/manet
.  >>> .  >>
.  >>> .  >>
.  >>> .  >>__________________________________________________
.  >>> .  >>Do you Yahoo!?
.  >>> .  >>The New Yahoo! Search - Faster. Easier. Bingo
.  >>> .  >>http://search.yahoo.com
.  >>> .  >>
.  >>> 
.  >>
.  >>
.  >>__________________________________________________
.  >>Do you Yahoo!?
.  >>The New Yahoo! Search - Faster. Easier. Bingo
.  >>http://search.yahoo.com
.  >>