mailing list archives
Re: "Selfish Routing"
From: Iljitsch van Beijnum <iljitsch () muada com>
Date: Sun, 16 Feb 2003 00:45:10 +0100 (CET)
On Sat, 15 Feb 2003, Mike Lloyd wrote:
Stephen Sprunk wrote:
The problem is eliminating the possibility of a packet taking a "near
optimal" path from A to B, and then taking another "near optimal" path from
B back to A
I suspect this is impossible to fix while retaining hop-by-hop routing.
Looping does indeed present a problem. If you want all nodes to play
the "near optimality" game, you have to move very slowly - if I choose
you, then we need a sensible way to guarantee that you won't choose me
at the same instant.
Or you can precompute potential paths and remove the paths that may
introduce loops. One way to do this would be with diffserv. You could
have different paths for different traffic classes. As long as each path
is loopfree and there can't be any oscillating between classes (router A
makes the packet CP X that must be routed over B, router B rewrites the
codepoint to Y that must be routed over A) you're homefree. And this is
easily accomplished by limiting the class transitions to one way only.
For instance, the traffic class may be upgraded if there is room in a
higher class but never downgraded.
> i dunno, i don't think igrp would scale to the size of the internet.
> wasn't there a 1/(n^2) relationship between metadata size and
> network capacity as a function of total delay*bandwidth product
> in the whole system?
Combining the scale problem and the looping problem suggests
optimization would fit most sensibly in an environment where the number
of choices under consideration is small, and some loop-free properties
Such conditions happen to occur where autonomous systems meet, and
especially for a stub AS. Careful inter-AS BGP optimization makes a
good deal more practical sense than, say, hysterically
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.
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.
Iljitsch van Beijnum - http://www.bgpexpert.com/ (updated: Feb 14, 14:12:15)
Re: "Selfish Routing" Paul Vixie (Feb 15)
Re: "Selfish Routing" Vadim Antonov (Feb 15)
Re: "Selfish Routing" Mikael Abrahamsson (Feb 15)