[e2e] traffic dispersion and blocking probality

Jon Crowcroft Jon.Crowcroft at cl.cam.ac.uk
Mon Apr 1 23:38:24 PST 2002


ok - here is a practical proposal

called ECN++

ECN is a mechanism for a bottleneck to give explicit, but also
early congestion notification - it is early for two reasons

1/ it arrives at the receiver as a mark in an IP packet that went thru
a bottleneck (a queueing device on the current IP path which had
incipient congestion) - this means it is as fast as a packet, ratehr
than an RTT estimate and timeout....
2/ it typically is implemented via RED rather than tail queue marking, 
and increasingly, researchers advise using virtual queues, which give
good responsiveness....

ECN++ records the position of the bottleneck in the packet - there are
several ways that this could be done

i) route record (problem with option space and with MTU of packet)
ii) hash the packet header (in the same way as DDOS traceback) and
keep it til you see an ACK packet flow the other way
(multicast tbd later, though this would work ok for pgmcc)
then when the receiver gets a packet with ECN, it sources a pure ack
(change to TCP) which _always has space for a route record_, so then
the congested router tags the ack with  its ip address - problem:
paths are assymetric; although often, bottlenckeszx are at edges, so
this aint a problem; except if bottlenckes are at edges, alternate
paths and dispersive routign arent really relevant - oh well)
iii) record the ttl of the packet in the ECN marked packet somewhere
(e.g. assume (probably ok, ) that all ECN++ capable end systems do MTU
discivery, so we can (yet again) overload the fragment fields:-)

then the source can distribute this information to nearby Congestion
Managers (see work of Hari Balakrishnan et al) who can implement an
overlay of application layer routers (see RON in previous email), 
and route around where the congestion was seen....by running traceroutes 
to each other and discovering who shares bottlenecks indicated in the ECN++
above....and then implementing tunnels...

tunnel/CM servers can use a shortest widest multipath routing, and select the
n-th shortest, lesst congested routes - or even do
best bandwidth+lowest delay + least congested:
there are now some very good
fast polynomial approximation algorithsm for doing this to good
accuract in very double quick time....so we can do multiple additive
metrics even here if we like (after all the congestion estimat is only
an approximation anyhow)...see any good operations research journal in
last 3 years for recent advances here

ok?

should keep a couple of PhD's busy for a couple of years...


some problems:
	- stability
	- economics (shadow price)
	- partial deployment 
	- security (ISPs HATE giving out info on who is worse provisioned
        etc etc)

In message <3CA95CCE.F672B90F at cad.zju.edu.cn>, Jing Shen typed:

 >>My question is with multipath dispersion, that is : if there exist multiple pathes
 >> for a source-destination pair.  when new flow arrives at source node for destionation,
 >>how could source determine  a path for this flow  which is estimated to have least
 >>possibility of congestion.
 
 >>I think this problem is of  greate relationship with traffic pattern,  time sequence analysis
 >>and route computation.   To your suggestion, I'll try to read some thing about Resilient Overlay Networking,
 >>would you please recommend some thing on RON?
 >>
 >>Regards
 >>
 >>> well, if "blocking probability" == "not making useful progress due to
 >>> congestion, and trying to avoid minor congestion collapse of even
 >>> probing/trying", yes - there's Reslient Overlay Networking - uese
 >>> altertante routes if the default ones are bust, and the Global Grid
 >>> Forum people have built a simular system...
 >>>
 >>> ip routes around problems - if it doesnt, recurse - route around ip...
 >>>
 >>> j.
 >>
 >>--
 >>Jing Shen
 >>
 >>State Key Lab of CAD&CG
 >>ZheJiang University (YuQuan)
 >>HangZhou, ZheJiang Province 310027
 >>P.R.China
 >>
 >>**********************************************************************
 >>* The SunShine of life is made up of very little beams which is      *
 >>*  bright all the time                                               *
 >>**********************************************************************
 >>
 >>
 >>
 >>--------------751746AB49E5B2CCE71DB62F
 >>Content-Type: text/html; charset=gb2312
 >>Content-Transfer-Encoding: 7bit
 >>
 >><!doctype html public "-//w3c//dtd html 4.0 transitional//en">
 >><html>
 >>Thanks for your comment.
 >><p>My question is with multipath dispersion, that is : if there exist multiple
 >>pathes
 >><br>&nbsp;for a source-destination pair.&nbsp; when new flow arrives at
 >>source node for destionation,
 >><br>how could source determine&nbsp; a path for this flow&nbsp; which is
 >>estimated to have least
 >><br>possibility of congestion.
 >><p>I think this problem is of&nbsp; greate relationship with traffic pattern,&nbsp;
 >>time sequence analysis
 >><br>and route computation.&nbsp;&nbsp; To your suggestion, I'll try to
 >>read some thing about Resilient Overlay Networking,
 >><br>would you please recommend some thing on RON?
 >><p>Regards
 >><blockquote TYPE=CITE>well, if "blocking probability" == "not making useful
 >>progress due to
 >><br>congestion, and trying to avoid minor congestion collapse of even
 >><br>probing/trying", yes - there's Reslient Overlay Networking - uese
 >><br>altertante routes if the default ones are bust, and the Global Grid
 >><br>Forum people have built a simular system...
 >><p>ip routes around problems - if it doesnt, recurse - route around ip...
 >><p>j.</blockquote>
 >>
 >><pre>--&nbsp;
 >>Jing Shen
 >>
 >>State Key Lab of CAD&amp;CG
 >>ZheJiang University (YuQuan)
 >>HangZhou, ZheJiang Province 310027
 >>P.R.China
 >>
 >>
 >>**********************************************************************
 >>* The SunShine of life is made up of very little beams which is&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *
 >>*&nbsp; bright all the time&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *
 >>**********************************************************************</pre>
 >>&nbsp;</html>
 >>
 >>--------------751746AB49E5B2CCE71DB62F--
 >>

 cheers

   jon




More information about the end2end-interest mailing list