Re: "Selfish Routing"

[Iljitsch van Beijnum <iljitsch () muada com>]

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
> already exist.

> 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
> self-reconfiguring OSPF.

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)