Subject: [manet] MAC queuing delay

From: Yougu Yuan <[email-masked]>
Date: Mon, 08 Jul 2002 14:41:50 -0400

Hi, all,

I'm doing validation of a wireless network simulation testbed, and have 
some problem regarding MAC 802.11.

With somewhat "heavy" traffic (100 nodes, 100 sessions, 2 512 byte 
packets per second per session) , we noticed that the MAC layer queuing 
delay in our simulation could be several hundred of millisecond or even 
a couple of seconds. This will break some assumptions of routing 
protocols and cause problems like route loops.

A little bit more about the setup: in the experiment, the maximum queue 
length for the MAC is set to 100 packets, and the routing packets and 
normal packets use separate queues.  A distance-fading radio propagation 
model is used by the physical layer.

Is there some work about the MAC layer delay statistics that one can 
expect? If any, can someone give me a reference for that? Another 
related question is,  if the assumption of hop-by-hop delay is broken, 
 does any known routing protocol has a way to detect/adjust, or it just 
has to live with the situation?

If you can spot any obvious problem with the delay we observed, please 
also let me know.

Thanks in advance.

-Yougu

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Xiaowen (Jason) Liu" <[email-masked]>
Date: Mon, 08 Jul 2002 14:56:22 -0400

Just to make Yougu's question a bit clearer: we're validating an AODV 
(draft 10) implementation; we found loop routes as a result of the 
exaggerated MAC layer delays. We know that AODV can adjust its 
hop-by-hop delay parameter, but it seems unclear to us how large would 
be enough. Is it "normal", if the assumption is broken, we would find 
loop routes in AODV ?

-jason.

-- 
Xiaowen (Jason) Liu          ([email-masked])
---------------------------------------------------------------
Computer Science Department  ISTS, Cybersecurity Research Group
Dartmouth College            Dartmouth College
6211 Sudikoff Laboratory     45 Lyme Road, Suite 201
Hanover, NH 03755            Hanover, NH 03755

Telephone: 603-646-0676      Fax: 603-646-0660
WWW Home Page: http://www.cs.dartmouth.edu/~jasonliu/
---------------------------------------------------------------

---

From: "Xiaowen (Jason) Liu" <[email-masked]>
Date: Mon, 08 Jul 2002 14:56:22 -0400

-jason.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 08 Jul 2002 12:08:52 -0700

Hello Yougu and Jason,

This is something that needs to be fixed.  I am not yet
understanding how the route loops form as a result of the
variable per-node delay setting.  Could one of you be
specific about the kinds of loops that occur, in order
that we can try to devise a solution.  With queues as
long as 100 packets, it may be unreasonable to set that
parameter to be as long as the maximum time for waiting
in the queue.  Then it could be that sometimes a new
RREQ is transmitted by the source prematurely.  But I
don't see that causing any route loops.  There must be
something else!

Thanks for any more information you can provide...

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 08 Jul 2002 12:08:52 -0700

Hello Yougu and Jason,

Regards,
Charlie P.

---

From: Yang Xiao <[email-masked]>
Date: Mon, 8 Jul 2002 12:52:04 -0700 (PDT)

Yougu,

I know little about MANET routing. However, I did a lot of IEEE 802.11
simulations, basically in MAC layer.

I am not sure how you can calculate delays in IEEE 802.11 very well
since delays depends a lot of factors. One important factor is the
traffic load. Different traffic load will result different delays. What
platform are you using? I use OPNET to do simulations. In OPNET, delays
become a little difficult to calculate. The built-in delays measures in
OPNET are not very accurate. In OPNET, delays involve the features of
traffic generators, queue sizes, the number of nodes, and etc. My point
is that you must make sure that your settings are good enough to obtain
accurate delay measures. If you use OPNET, please let me know so that
we can have further discussions.

Regards

Yang

> If you can spot any obvious problem with the delay we observed,

__________________________________________________
Do You Yahoo!?
Sign up for SBC Yahoo! Dial - First Month Free
http://sbc.yahoo.com

---

From: Yang Xiao <[email-masked]>
Date: Mon, 8 Jul 2002 12:52:04 -0700 (PDT)

Yougu,

Regards

Yang

---

From: Yougu Yuan <[email-masked]>
Date: Mon, 8 Jul 2002 16:02:57 -0400

Hi, Prof. Perkins,

Let me explain in detail how a loop can be formed within AODV if the
assumption about the one hop delay is broken. 

I will use AODV draft 10 in the example. I haven't read draft 11 very 
carefully yet, but I think it won't change much on the result. In AODV, the 
one hop round trip delay (NODE_TRAVERSAL_TIME) is by default 40 ms, and the 
PATH_DISCOVERY_TIME is computed to 4.2 second with NET_DIAMETER 35.

After an RREQ has been received, a node will keep a record of its
originator and its rreq id for PATH_DISCOVERY_TIME, ignoring any
rreq with the same values in this period of time. So far so good.

Here comes the scenario, in which I will exagerate the MAC queuing delay a 
little bit more to make the story shorter.

1) Node S sended out a request for Node D with rreq ID i: RREQ(D, i), and 
after some hops, it's picked up and forwarded by Node X. X created its 
reverse route to S and kept the rreq record as specified. Unfortunately, the 
request sent out by X is delayed in the MAC layer a lot, say, for 2.5 second.
 
2) Then Node Y received this forwarded request RREQ(D, i). Y did the same 
thing as X, put a reverse route **Y->S (through X)** in its table and 
forwarded the request, really bad luck, it's again delayed in the MAC layer 
for 2.5 second. 

3) So after 5 seconds, X received this RREQ(D,i) again, but this time from Y.
If X were to ignore this old RREQ from Y, everything would be fine. However, 
at this moment, the PATH_DISCOVERY_TIME has been exceeded, X has discarded 
the record for the previous RREQ(D, i), and the reverse route to S has been 
invalidated because its lifetime expired. Given all above conditions, X would 
update its reverse route to S: **X->S (through Y)**, and this created a loop 
because the route to S in Y was still active, and it used X as the next hop.

-Yougu

-- 
Yougu Yuan

----------------------------------------------------
Office Phone 603-646-0679    [email-masked]
Dept. of Computer Science, Dartmouth College

---

From: "Kaixin Xu" <[email-masked]>
Date: Mon, 8 Jul 2002 13:42:21 -0700

Yougu,

I think hundreds of milliseconds are not a surprise. From my experience,
this is due to the binary exponential backoff of IEEE 802.11 DCF. Actually
you can build a Markov Chain model to calculate the average delay using the
retry counter as state variable. The key point I think is that in ad hoc
networks, the delay at the MAC layer is more important than queuing delay at
the network layer buffers. This is partly due to the feature that the MAC
layer will drop packet after 7 retries. Thus, long queue is unlikely to
build up.

The default values of IEEE 802.11 are 1) short retry limit 7 . 2) The
minimal backoff time is 31 slots and 3) the maximum backoff time is 1023
slots 4) the slot is 20us for DHSS and 50us for FHSS. So, the longest
backoff time would be (31+63+127+255+511+1023+1023+1023)*20us = 82 ms. If
you then consider the time the backoff timer is suspended when the node
sensing the media is busy and the time for transmitting the RTS  and time
for waitting CTS timeout several times, blah, blah. I think hundreds of ms
delay is not rare. However, if you get delay in several seconds, that should
not be common. I guess that means the network is really overloaded. Hope
this is helpful.

Kaixin

---

From: "Kaixin Xu" <[email-masked]>
Date: Mon, 8 Jul 2002 13:42:21 -0700

Yougu,

Kaixin

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 08 Jul 2002 13:43:04 -0700

Hello Yougu,

If I may summarize, the route loop is caused if a node forgets
about the RREQ too soon, and then sets up the reverse route
through a neighbor to whom it had recently transmitted the RREQ.

The solution to this problem is to require nodes to remember
the RRED_ID for a long time.  This time can be made very long,
at the cost of increased memory requirement.  But I think the
extra memory is a matter of a few dozen bytes, and that's not
so terrible.

Maybe we should re-institute the "RREQ_RECORD_TIME", and
cause it to be (10 * PATH_DISCOVERY_TIME).  Would you be
willing to try this in your simulation to see if it fixes
the problem?

Also, I think it is worthwhile to observe that this is a basic
problem with any flooding scheme.  In the scenario you describe,
node X would not only set up the reverse route incorrectly, but
it would also retransmit the RREQ.  All of X's neighbors that
had themselves forgotten about the RREQ, would react similarly.
In other reasonable flooding schemes, there will typically be
some other parameter that has exactly the same functionality
of the RREQ_ID.

The RREQ_ID really has to be remembered for a long-enough
time so that this cannot happen.

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 08 Jul 2002 13:43:04 -0700

Hello Yougu,

Regards,
Charlie P.

---

From: "Xiaowen (Jason) Liu" <[email-masked]>
Date: Mon, 08 Jul 2002 16:48:05 -0400

Yang,

We ported GloMoSim's 802.11 layer to our simulator and we instrumented 
the simulator to observe the delays at the MAC layer. In the experiment 
setup, the network is highly congested. Hence the multi-second delay.

-jason.

---

From: "Xiaowen (Jason) Liu" <[email-masked]>
Date: Mon, 08 Jul 2002 16:48:05 -0400

Yang,

-jason.

---

From: Yougu Yuan <[email-masked]>
Date: Mon, 8 Jul 2002 16:02:57 -0400

Hi, Prof. Perkins,

 

-Yougu

-- 
Yougu Yuan

---

From: Yougu Yuan <[email-masked]>
Date: Mon, 8 Jul 2002 17:11:40 -0400

Prof. Perkins, 

Actually we did the test with an extended time for RREQ record, and yes
it fixed the problem of route loops. The summary you have done is almost 
exact except that the scenario I described could happen in a multi-hop 
fashion as well, that is, multi-hop loops can be formed.

The reason we raised the question about the MAC layer delay is not only 
because of the route loop although it is the largest problem. There may be 
some other issues too. For example, this is one that I can think of right 
now: AODV estimates the round trip time of a request, and initialize another 
round if it hasn't received any reply after the timer expires. The round trip 
time is also computed based on NODE_TRAVERSAL_TIME. Underestimate the 
NODE_TRAVERSAL_TIME means that the node can send out unnecessary broadcasting 
requests, putting more burden on the network.

-Yougu

On Monday 08 July 2002 16:43, Charles E. Perkins wrote:
> > carefully yet, but I think it won't change much on the result. In AODV,
> > the one hop round trip delay (NODE_TRAVERSAL_TIME) is by default 40 ms,
> > and the PATH_DISCOVERY_TIME is computed to 4.2 second with NET_DIAMETER
> > 35.
> >
> > Here comes the scenario, in which I will exagerate the MAC queuing delay
> > a little bit more to make the story shorter.
> >
> > reverse route to S and kept the rreq record as specified. Unfortunately,
> > the request sent out by X is delayed in the MAC layer a lot, say, for 2.5
> > second.
> >
> > forwarded the request, really bad luck, it's again delayed in the MAC
> > layer for 2.5 second.
> >
> > 3) So after 5 seconds, X received this RREQ(D,i) again, but this time
> > from Y. If X were to ignore this old RREQ from Y, everything would be
> > fine. However, at this moment, the PATH_DISCOVERY_TIME has been exceeded,
> > X has discarded the record for the previous RREQ(D, i), and the reverse
> > route to S has been invalidated because its lifetime expired. Given all
> > above conditions, X would update its reverse route to S: **X->S (through
> > Y)**, and this created a loop because the route to S in Y was still
> > active, and it used X as the next hop.
> >
> > -Yougu
> >
> > > > I'm doing validation of a wireless network simulation testbed, and
> > > > have some problem regarding MAC 802.11.
> > > >
> > > > packets per second per session) , we noticed that the MAC layer
> > > > queuing delay in our simulation could be several hundred of
> > > > millisecond or even a couple of seconds. This will break some
> > > > assumptions of routing protocols and cause problems like route loops.
> > > >
> > > > A little bit more about the setup: in the experiment, the maximum
> > > > queue length for the MAC is set to 100 packets, and the routing
> > > > packets and normal packets use separate queues.  A distance-fading
> > > > radio propagation model is used by the physical layer.
> > > >
> > > > related question is,  if the assumption of hop-by-hop delay is
> > > > broken, does any known routing protocol has a way to detect/adjust,
> > > > or it just has to live with the situation?
> > > >
> > > > If you can spot any obvious problem with the delay we observed,
> > > > please also let me know.
> > > >
> > > > Thanks in advance.
> > > >
> > > > -Yougu
> > > >

-- 
Yougu Yuan

---

From: Yougu Yuan <[email-masked]>
Date: Mon, 8 Jul 2002 17:11:40 -0400

Prof. Perkins, 

-Yougu

-- 
Yougu Yuan

---

From: "Xiaowen (Jason) Liu" <[email-masked]>
Date: Mon, 08 Jul 2002 17:24:18 -0400

Kaixin,

The estimate is correct for one packet. But if there're 100 packets in 
the queue, each one will experience 100 times the worst delay of the one 
packet. It could sum to as much as tens of seconds. Well, I'm talking 
about the worst scenario. The network is really really overloaded...

-jason.

---

From: "Xiaowen (Jason) Liu" <[email-masked]>
Date: Mon, 08 Jul 2002 17:24:18 -0400

Kaixin,

-jason.

---

From: Sumeeth Nagaraj <[email-masked]>
Date: Mon, 08 Jul 2002 16:52:35 -0600

Hi,

NET_TRAVERSAL_TIME = 2* 35*40 milliseconds, In the scenario described below,
I think the source would generate a new RREQ and each time a new RREQ ID is
used so when X receives a new RREQ before it can hear from Y then it would
discard the RREQ from Y right. I think still no loops are formed.

I think I understand the problem in case I am wrong please let me know.

Regards,
Sumeeth

----- Original Message -----
From: "Yougu Yuan" <[email-masked]>
To: "Charles E. Perkins" <[email-masked]>
Cc: <[email-masked]>; "Xiaowen (Jason) Liu" <[email-masked]>
Sent: Monday, July 08, 2002 2:02 PM
Subject: Re: [manet] MAC queuing delay

> carefully yet, but I think it won't change much on the result. In AODV,
the
> reverse route to S and kept the rreq record as specified. Unfortunately,
the
> forwarded the request, really bad luck, it's again delayed in the MAC
layer
> > > I'm doing validation of a wireless network simulation testbed, and
have
> > > packets per second per session) , we noticed that the MAC layer
queuing
> > > A little bit more about the setup: in the experiment, the maximum
queue

---

From: Sumeeth Nagaraj <[email-masked]>
Date: Mon, 08 Jul 2002 16:52:35 -0600

Hi,

Regards,
Sumeeth

----- Original Message -----
From: "Yougu Yuan" <[email-masked]>
To: "Charles E. Perkins" <[email-masked]>
Cc: <[email-masked]>; "Xiaowen (Jason) Liu" <[email-masked]>
Sent: Monday, July 08, 2002 2:02 PM
Subject: Re: [manet] MAC queuing delay

the
the
layer
have
queuing
queue

---

From: Yougu Yuan <[email-masked]>
Date: Mon, 8 Jul 2002 18:57:15 -0400

Sumeeth, your observation is correct, but there are exceptions. 
1) This may happen for the last try of RREQ_RETRIES, which means there won't 
be a new RREQ for a while.
2) With mobility, ad-hoc network has very high error rate as we observed in 
the simulation, and the new RREQ, if any, might be tossed and hasn't been 
received correctly by X.

-Yougu

On Monday 08 July 2002 18:52, Sumeeth Nagaraj wrote:
> Hi,
>
> NET_TRAVERSAL_TIME = 2* 35*40 milliseconds, In the scenario described
> below, I think the source would generate a new RREQ and each time a new
> RREQ ID is used so when X receives a new RREQ before it can hear from Y
> then it would discard the RREQ from Y right. I think still no loops are
> formed.
>
> > one hop round trip delay (NODE_TRAVERSAL_TIME) is by default 40 ms, and
>
> the
>
> > request sent out by X is delayed in the MAC layer a lot, say, for 2.5
>
> second.
>
> > from
> Y.
> > If X were to ignore this old RREQ from Y, everything would be fine.
>
> However,
>
> > at this moment, the PATH_DISCOVERY_TIME has been exceeded, X has
> > discarded the record for the previous RREQ(D, i), and the reverse route
> > to S has
>
> been
>
> > invalidated because its lifetime expired. Given all above conditions, X
>
> would
>
> > update its reverse route to S: **X->S (through Y)**, and this created a
>
> loop
>
> > because the route to S in Y was still active, and it used X as the next
>
> hop.
>
> > -Yougu
> >
> > > > delay in our simulation could be several hundred of millisecond or
>
> even
>
> > > > normal packets use separate queues.  A distance-fading radio
>
> propagation
>
> > > > or it
> just

-- 
Yougu Yuan

---

From: Yougu Yuan <[email-masked]>
Date: Mon, 8 Jul 2002 18:57:15 -0400

-Yougu

-- 
Yougu Yuan

---

From: Yougu Yuan <[email-masked]>
Date: Mon, 8 Jul 2002 19:17:57 -0400

I forgot to mention another "exception" in the last e-mail. The newly sent 
RREQ also suffers the same problem of MAC layer delay, so it might be stuck 
in the MAC layer of some node in the middle and hasn't arrived at X yet.

-Yougu

-- 
Yougu Yuan

---

From: Yougu Yuan <[email-masked]>
Date: Mon, 8 Jul 2002 19:17:57 -0400

-Yougu

-- 
Yougu Yuan

---

From: Imad AAD <[email-masked]>
Date: Tue, 9 Jul 2002 12:11:09 +0200 (MEST)

On Mon, 8 Jul 2002, Kaixin Xu wrote:

> not be common.

Hi,

You should also consider the packet retransmissions' effect on delays.

long delays are common as long you have several collisions and
retransmissions, e.g. your scenario.

The average delay a packet observes (in a single hop, can be generalized
for multi-hop of course) is:
(avrg successful pkt. transmission delay) x (avrg number of pkts in the queue)

the average number of packets in the queue is high in your simulations
(~100)

due to high collisions and retransmissions (+ IFSs + increasing backoffs),
the "average successful packet transmission delay" is considerably high too,
so it's not weird to observe delays of several seconds.

hope it helps,

imad

---

From: Imad AAD <[email-masked]>
Date: Tue, 9 Jul 2002 12:11:09 +0200 (MEST)

Hi,

hope it helps,

imad

---

From: "Xiaowen (Jason) Liu" <[email-masked]>
Date: Tue, 09 Jul 2002 11:00:05 -0400

Hi.

I have another question related to MAC queuing delay. The MAC layer 
maintains a separate queue for each priority. Data packets are normally 
assigned with a lower priority than control packets from the routing 
protocols. Is this a common practice? In another word, should it be a 
requirment in routing protocol specifications or at least a "strong" 
recommendation? In the simulation, at least in one setup, we observed 
much smaller delays for routing packets through the MAC layer if we 
assign a higher prirority to them than to normal packets. I assume 
smaller delays for routing packets would have nontrivial impact to the 
throughput, etc.

Also, can someone tell me whether broadcast messages are treated the 
same as unicast messages in 802.11 in terms of queuing? It seems to me 
broadcast messages should be given higher priority, even if they come 
from the same routing protocol.

Thanks.

-jason.

Dartmouth College.

---

From: Yang Xiao <[email-masked]>
Date: Tue, 9 Jul 2002 08:38:43 -0700 (PDT)

Jason

In current IEEE 802.11 standards, there is not priority at all. Only
one queue should be used, and all packets (data or control) are FIFO in
the queue. MAC should have no knowledge about the important data or
non-important data from higher layer, such as "control packets from the
routing protocols" will be treated as normal payloads.

Regards

Yang

---

From: Yang Xiao <[email-masked]>
Date: Tue, 9 Jul 2002 08:38:43 -0700 (PDT)

Jason

Regards

Yang

---

From: Vikram Kanodia <[email-masked]>
Date: Tue, 9 Jul 2002 10:43:44 -0500 (CDT)

delay of couple of seconds in high load scenarios (total offered load ~
80% capacity, number of nodes > 25) is consistent with what we observed in
some of our ns simulations. We traced the cause back to mainly, large
number of collissions (in the heavy load case) leading to queue buildup at
the interface queue (the queue length was set to a large value in our case
to avoid dropping) leading to high delay.

-Vikram

-- 

Department of ECE, Rice University | 713 348 3786 (O)| 713 664 5650(H)
WWW: http://www.ece.rice.edu/~kanodia

---

From: Vikram Kanodia <[email-masked]>
Date: Tue, 9 Jul 2002 10:43:44 -0500 (CDT)

-Vikram

--

---

From: "Xiaowen (Jason) Liu" <[email-masked]>
Date: Tue, 09 Jul 2002 11:00:05 -0400

Hi.

Thanks.

-jason.

Dartmouth College.