Subject: RE: [manet] Re: [ns] Dealing with congested networks [was: Re: DSRand DSDV simulation problem analysis results ...]

From: "Liaw, Yong Shyang - LIAYS001" <[email-masked]>
Date: Fri, 18 Mar 2005 17:15:31 +1030

I read your paper, and below are MHO:
 
You tried to find alternative route around the congested node.  I think if a node is congested, the surrounding nodes near the congested node are likely to be congested as well, so you may find another route that is congested as well.  In fact in DSR, when there is a link break, it also reroutes the packet (i.e. salvaging).  In your paper you did not specify the time-interval over which the forward-limit is applied.  It is possible that route break may occur before you reach the forward-limit, depending the time-interval.  Of course, rerouting will have some benefits of "distributing load" over the network.
 
Rerouting may not avoid congestion if the problem is that the source's sending rate is too fast -- it may just move one congestion node to another node in the network.  You will still need somekind of flow control at the source.  On this matter I have a paper under review.

________________________________

From: [email-masked] on behalf of Bryan Hogan
Sent: Wed 16/03/2005 10:43 PM
To: NS Mailing
Cc: Manet Mailing
Subject: Re: [manet] Re: [ns] Dealing with congested networks [was: Re: DSRand DSDV simulation problem analysis results ...]

Should have included link to publication on this solution...

Congestion Avoidance in Source Routed Ad Hoc Networks - 13th IST Mobile
and Wireless Communications Summit, Lyon, 2004

http://www.geocities.com/b_j_hogan/files/congestion_avoidance.pdf

Bryan J. Hogan

On Thu, 10 Mar 2005, Bryan Hogan wrote:

> Hello,
>
> I have been following this thread and would like to add to the list of
> solutions provided by David Maltz with the following
>
> I have conducted research on congestion in DSR with the aim of
> implementing a congestion control algorithm.
> >From this research I found that a substantial amount of congestion
> occurred as a result of the reuse and propagation of known routes, and
> that this was more prevalent at low mobility rates that at high mobility
> rates.
>
> I was able to mitigate the effects of this in the following manner -
> At the onset of congestion a node alerts its adjacent nodes of this by
> broadcasting a prioritised congestion notification packet. These adjacent
> nodes subsequently reduce the volume of data they are forwarding through
> the congested node and also seek alternate routes (from its own cache)
> to the destination.
>
> Using this method I achieved improvements in packet delivery rates which
> varied(between approx 3% and 8%) depending on the number of nodes, data
> rates and mobility rates.
>
> I would appreciate any comments on this solution.
>
> Bryan Hogan
>
> >
> >--On Thursday, March 03, 2005 10:10 PM -0800 Shahriar Shamil
> >Uulu <[email-masked]> wrote:
> >
> >> Just yesterday i have posted my question that DSR's
> >> performance degrading drastically after 100 seconds.
> >> So i have analysed the reason why DSR drops the
> >> packets and came to know that (-Nw from trace):
> >> All results based on "ns-2.1b8a-allinone" and 50 nodes
> >> with 10 sources.
> >
> >Integrating information from a side conversation that Uulu and I
> >have been having, I'm assuming cbr traffic sources, 512B
> >packets.
> >
> >I think there is no simple answer --- this is a real research
> >problem.
> >
> >[I have attached a figure produced by Uulu showing PDR as a
> >function of time during his simulation.]
> >
> >
> >>For DSR the trace levels(-Nl) [shows that dropped packets] are mostly
> >"IFQ":
> >> 1.80% droped due to "IFQ" mean no buffer space in IFQ
> >> 2.15% droped due to "ARP" droped by ARP
> >> 3.and around 5% by "SAL" i think it couldnot salvage
> >> the packet.
> >> ---------------------------------------------------------
> >> For DSDV the trace levels(-Nl) [shows that dropped packets]
> >are mostly
> >"RTR" and "IFQ":
> >> 1. 45% droped due to "CBK",
> >> 2. 40% droped due to "IFQ",
> >> 3. 15% "ARP"+others
> >
> >The reason DSR's PDR starts out high and then drops over the
> >first 100 s is probably that the connections are starting up
> >over the first 100 s, so the load
> >on the network is constantly increasing over that time.
> >
> >Unlike TCP, CBR sources are non-conforming --- they keep pumping
> >out data regardless of how congested the network is, and your
> >network is pretty congested.
> >With 10 sources * 4 pkts/s *  512B/pkt = 163 Kbps, that's a high
> >average offered load on the network considering that: (1) max
> >data rate in your simulator is
> >probably 2 Mbps; (2) 802.11 reacts to collisions by backing off,
> >converting what would have been a MAC layer packet loss into
> >increased latency.
> >Unfortunately, backing off decreases the effective throughput of
> >each node, which increases the backlog of packets at each node
> >and eventually converts into
> >IFQ layer packet drops; (3) in a multi-hop network, each of
> >those CBR packets needs to be sent multiple times, so the
> >effective load is roughly (mean path
> >length + 1) * offered load.
> >
> >If you measured Fraction Free Air Time for each of the nodes, I
> >predict that you'd see that many nodes see no more capacity in
> >the medium.
> >
> >The congestion is presumably so severe that DSDV can't even
> >track routes to all destinations. That's why DSDV nodes are
> >dropping packets in the RTR level (no
> >route).  The surprising result is that more of the originated
> >packets actually make it to their destination.  DSDV is, in
> >effect, shedding enough of the
> >offered load to bring the network slightly out of congestion
> >collapse.
> >
> >Potential solutions?
> >
> >1) Evaluating results from experiments run on congested networks
> >is very tricky as congestion effects dominate protocol
> >performance.  If the IFQ drop rate is
> >large, or the PDR low (less than 90 percent or so), or the FFAT
> >low, then your experiment is in a congested state.  Either
> >reduce the offered load, use
> >conforming sources (e.g., TCP), or resign yourself to tackling
> >the challenge of making a congested network run better.
> >
> >2) Make a congested network run better:
> >- tune parameters: use shorter IFQs
> >- use path/flow state, reservations, admission control, etc
> >- change the MAC protocol to back off less and give up on
> >packets faster in a congested situation (e.g., when FFAT goes to
> >zero over some time interval, just
> >drop the packet at the head of the queue)
> >- implement back pressure or flow control at either the MAC or
> >the RTR layer (e.g., once a data packet leaves its originating
> >node, it gets preferential
> >access to the media at all future forwarding nodes)
> >- use power control to increase the total aggregate carrying
> >capacity of the network
> >- MobiCom proceedings over the past several years contain many
> >additional ideas
> >
> >Cheers,
> >-dam
>
>
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet
>

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

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

---

From: Bryan Hogan <[email-masked]>
Date: Tue, 29 Mar 2005 16:40:05 +0100 (IST)

Hi,

Thank you for reading the paper and for your comments.

I have found that in a high number of cases the surrounding nodes are
capable of taking some of the load from the congested node. This is
because, particularly in low mobility scenarios, know routes are used very
heavily. However, forcing the use of alternate routes allows the congested
nodes to recover.

With regard to the time interval, I am presently (in my spare time)
working on a change to the algorithm that allows the time interval and a
few other parameters alter dynamically to suit network conditions.

Finally, in relation to moving the congestion from one node to another-
1. In a scenario where a source is sending data at far too high a rate,
its neighbour will very soon become congested. The congested node then
broadcasts a congestion notification. The source recieves this
notification and must stop sending data to the congested node because
it(the source) will have exceeded the forwarding limit.

2. In a less extreme scenario, where a source sending data at
moderate rates causes congestion, your assertion is correct.
However, the algorith does handle this to a certain extent.

When ongestion occurs, the node forwarding to the congested node
will be stopped from forwarding more packets, it (the forwarding node) in
turn will become congested and tell its neighbour to stop forwarding
packets, and so on, until this ripple reaches the source.

When designing the algorithm, I included both local and source controls.
The local measures act initially and if they fail, the source controls
will take effect. For obvious reasons, I did not think it would be
possible to use a system which relies on notifying the source by use of
a congestion notification packet and so relied on a the ripple affect
described above.

I would appreciate any further comments or suggestions regarding this.

Thanks,

Bryan Hogan

On Fri, 18 Mar