[Irtf-rr] draft-irtf-routing-reqs-00.txt

[avri]

On fredag, aug 15, 2003, at 09:51 Asia/Seoul, Dmitri Krioukov wrote:

> Avri,
>
> I'd like to comment on those TBDs you're concerned with.

thanks

>
> I don't think we'd be able to come up with any reasonable
> numbers for stability/convergence-related TBDs. There are
> two reasons for that.

Sort of my feeling too.  while editing the documents i felt an urge to 
switch TBD to something else, but could not come up with a reasonable 
answer.

>
> First, there are very few results on the theoretical
> lower and upper bounds for adaptation costs (i.e.
> number of messages generated per topology change,
> their sizes, etc.) for dynamic routing on graphs
> with arbitrary topology (i.e. generic graphs). The
> progress on this subject in distributed computing has
> been *very slow* over the past 20 years, one of the
> reasons being, I think, that the problem is quite hard.
> (I'm talking not about BGP convergence, but about
> fundamental bounds for any kind of routing algorithms.)
> Furthermore, the results that do exist are quite pessimistic
> (for example, for *any* shortest-path routing
> algorithm, there *exist* an n-node graph and such
> topology change in it that *not less* than n messages
> are required to process this topology change).
> And there are no theoretical results at all
> for routing (dynamic or static) on networks with
> Internet-like topologies (scale-free networks)
> (except our latest publication :)
>
> Given this fundamental lack of knowledge, how can
> we come up with any realistic numbers for convergence
> then?

While I agree this is difficult, I assume that while it is not possible 
to find the theoretical limits, it may be possible to determine 
requirements that hit within bounds that can be calculated.  As this is 
a research group instead of an engineering group I did not want to 
preclude the possibility just because it was hard.

While I am quite skeptical of out being able to fill those TBDs with 
numbers at this point, I am hoping we can fill them with an expression 
of what needs to be done to work our way towards understanding the 
numbers.  I think in the end it is important to know, to some 
approximation, the requiremtn fo convergence - even just local 
convergence.

>
> The second reason is related to p.3.10.1 in the draft.
> If we allow for freedom in network modeling, then
> convergence might not be an issue at all (recall
> the physical routing discussion, etc.).

True.

>
> So that, I'd propose either to leave it as is or
> to restructure the whole thing to something like:
> --
> Given the fact that there are currently no known bounds
> for adaptations costs for dynamic routing on scale-free
> networks, the precise formulation of the convergence
> requirements is a subject of future research.
> --

This works for me.  though perhaps a bit more could be said about the 
kinds of research needed to arrive at an answer.

and, perhaps, if this RG does survive, this is an area that a few 
people could delve into.

>
> I think that scalability related part (i.e. ~"should scale
> indefinitely") is OK.
>

a.