[55904] in North American Network Operators' Group
Re: "Selfish Routing"
daemon@ATHENA.MIT.EDU (Mike Lloyd)
Sat Feb 15 20:17:20 2003
Date: Sat, 15 Feb 2003 17:15:46 -0800
From: Mike Lloyd <drmike@routescience.com>
To: Iljitsch van Beijnum <iljitsch@muada.com>
Cc: nanog@merit.edu
In-Reply-To: <20030216002855.N61596-100000@sequoia.muada.com>
Errors-To: owner-nanog-outgoing@merit.edu
Iljitsch van Beijnum wrote:
> Utilization-based routing between two ASes is an excercise in futility
> if it's in a single location (load balancing is simpler and just as
> effective) and isn't simpler than across multiple ASes if the
> interconnects are in different places of the network topology
Pure utilization-based routing between 2 AS's is, in effect, load
balancing, so I'm not sure how to interpret your first instance. But in
any case, adding performance objectives to a load optimization problem
makes the solution more demanding. (It is possible in practice to
observe performance differences between 2 paths from AS A to directly
connected AS B - not as many as you see comparing different transit
choices to a far point, but they still exist.)
Optimization across topologically distant egress points from AS A to AS
B is harder, and if the choice is a nearby link to B and a far link to
some other AS C, harder still. But in practical networking, this is not
the common problem.
Practically speaking, most AS's fall between your two cases - that is,
they have at least one place in their topology where they border several
other AS's. This provides multiple pre-computed, loop-free paths to the
same end point. Picking the "best" one for near-optimal performance and
low congestion in this context is, I would suggest, beneficial, and if
done correctly, not prone to the suboptimality discussed in the paper
that started this thread.
> Besides, the whole point is that you'd be able to go from New York to
> London over Tokio if the direct line is congested.
Given good end to end performance measurement as part of the path
selection, a planet-circling route is unlikely. Few apps will perform
well if packets have to circumnavigate (streaming and email are among
the only candidates).
So to an extent, I agree - performing dynamic re-routing over arbitrary
paths purely to avoid congestion isn't a great idea. You can indeed end
up bouncing of satellites. But if you add performance sensitivity, you
have a harder optimization challenge, but a much more worthwhile result.
Mike
