"Selfish Routing"

Sun Feb 16 01:15:46 UTC 2003

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