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

Ibrahim Matta matta at cs.bu.edu
Mon Dec 12 20:50:29 PST 2005

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)  
Authors  A. Khanna, J. Zinky   BBN Communications Corporation 

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 = 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 - 

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