[e2e] YNT: A Question on the TCP handoff/incremental routechange

Jon Crowcroft Jon.Crowcroft at cl.cam.ac.uk
Tue Dec 13 01:18:42 PST 2005

hmm, interesting - so basically another way of thinking about this is
to greatly expand the metric space over which routes are computed, so
that routes that are sort of a bit better but not as good as the best
route after a change can look good enough for a while....time
dependent metrics (rather than my scheme which was scope based)...

seems like somethign one could look at - there's work by randy bush
that shows that when the routing control plane is attacked, the
forwarding/data plane is remarkably stable despite inability of 
new routes to be  computed - i wonder if path vector sort of has a
behaviour that is a bit like this anyway, and what we are skating
around the edges of is some formalisation of a way to make routing
vary more smoothly...

seems like a good masters project to evaluate your and my proposasl...
In missive <0511C607B17F804EBE96FFECD1FD98595E51E7 at cs-exs2.cs-nt.bu.edu>, "Ibra
him Matta" typed:

 >>Jon, how about easing the failure of a link (or introduction of a new
 >>link) by gradually changing the "cost" ("metric") of the link? E.g.,
 >> The revised ARPANET routing metric, ACM SIGCOMM Computer Communication
 >>Volume 19 ,  Issue 4  (September 1989) =20
 >>Authors  A. Khanna, J. Zinky   BBN Communications Corporation=20

 >>By limiting the change in successively advertized link cost (cf.
 >>"movement limit" in this paper), you can avoid abrupt changes (e.g. due
 >>to "infinite" link cost) and show better convergence by contractive
 >>mapping of routing metric =3D function(traffic load) and traffic load =
 >>function(routing metric)...
 >>In general, abrupt changes in routes can be avoided by making sure the
 >>link in question does not look all of a sudden too attractive or too
 >>unattractive compared to other links.
 >>-----Original Message-----
 >>From: end2end-interest-bounces at postel.org
 >>[mailto:end2end-interest-bounces at postel.org] On Behalf Of Jon Crowcroft
 >>Sent: Sunday, December 11, 2005 8:39 AM
 >>To: end2end-interest at postel.org
 >>Subject: Re: [e2e] YNT: A Question on the TCP handoff/incremental
 >>increasing resolution so we can read between the pixels:
 >>so the idea i was getting at was to do with the way both distance/path
 >>vector, and link state algorithms choose one route, then, when a better
 >>route is discovered, switch abruptly to it.
 >>To mitigate the effect (not to get rid of it completely, but to reduce
 >>the size of one potential step function in rtt and bottleneck capacity
 >>to a set of smaller changes), one can think of routing as a process of
 >>recursive re-routing - the idea is quite simple -=20
 >>a current route gets from A to B. There is an outage, or else a new
 >>route appears because of the end of an outage (or the introduction of a
 >>new link, but lets leave that for now as its occasional)
 >>so we can think of the routers either side of the outage and see if
 >>there are routes from any router on the A-B path to the routers either
 >>side of an old outage, or if its a new outage on A-B, from the routers
 >>either side of the broken link (yes, and router:), to a better route.
 >>How to do this in a distributed way without incurring some huge overhead
 >>compared to normal link state?
 >>well, lets assume ISPs aren't mad, and that a lot of links that are
 >>avaialble for alternate routes are actually part of some planned
 >>redundent capacity/topology, rather than accidental (I know this is
 >>contraversal, as most papers on multipath routing seem to assume that we
 >>consier all links in the world, but thats researchers for you - most
 >>network providers don't work that way).
 >>so then we actually cosider the problem _inside out_ - start as reaching
 >>points either side of potential and actual outages, and create a set of
 >>routes - how will that work? consider hierarchical OSPF - and you are
 >>just laberling routers at each end of outages as in the same level
 >>hierarchy, and links further on as the next level of the hierarchy (can
 >>do similar for BGP). how to _stage_ the handover ?
 >>ok - so we need to cascade the timers for the route update in each level
 >>of the hierarchy. How to do that? that's where control theory comes in,
 >>maybe although I was thinking of using a process algebra like stochastic
 >>pi calculus myself.



More information about the end2end-interest mailing list