[55900] in North American Network Operators' Group
Re: "Selfish Routing"
daemon@ATHENA.MIT.EDU (Mike Lloyd)
Sat Feb 15 16:12:40 2003
Date: Sat, 15 Feb 2003 13:11:45 -0800
From: Mike Lloyd <drmike@routescience.com>
To: Stephen Sprunk <stephen@sprunk.org>
Cc: Sean Finn <seanf@routescience.com>,
Pete Kruckenberg <pete@kruckenberg.com>, nanog@merit.edu
In-Reply-To: <01de01c2d49b$e3f3cba0$93b58742@ssprunk>
Errors-To: owner-nanog-outgoing@merit.edu
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. A mechanism to do so will slow all decisions down,
potentially beyond the point of usefulness. However, I don't quite get
from this problem to a need to abandon hop-by-hop routing.
Paul Vixie wrote:
> 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.
I could observe that the edge of a BGP AS is also a place where money
sometimes changes hands, but I wouldn't want to infect a nice academic
discussion with anything too commercial :-)
Mike
