Subject: Re: [rrg] Fwd: RRG Recommendation

From: [email-masked] (Noel Chiappa)
Date: Tue, 5 Oct 2010 10:55:15 -0400 (EDT)

> From: Brian E Carpenter <[email-masked]>

    > I wouldn't object to the document title being made more bland

I too would be fine with that (of course).

	Noel

---

From: [email-masked]
Date: Fri, 22 Oct 2010 16:00:49 EDT

Dima, I like to contradict strongly having read (once more) what you refer  
to:
  ------------quote----------------
 
The  Internet's routing system is facing stresses due to its poor 
fundamental scaling  properties. Compact routing is a research field that studies 
fundamental limits  of routing scalability and designs algorithms that try to 
meet these limits. In  particular, compact routing research shows that 
shortest-path routing, forming a  core of traditional routing algorithms, cannot 
guarantee routing table (RT)  sizes that on all network topologies grow 
slower than linearly as functions of  the network size. However, there are plenty 
of compact routing schemes that  relax the shortest-path requirement and 
allow for improved, sublinear RT size  scaling that is mathematically provable 
for all static network topologies. In  particular, there exist compact 
routing schemes designed for grids, trees, and  Internet-like topologies that 
offer RT sizes that scale logarithmically with the  network size. 
In  this paper, we demonstrate that in view of recent results in compact 
routing  research, such logarithmic scaling on Internet-like topologies is 
fundamentally  impossible in the presence of topology dynamics or 
topology-independent (flat)  addressing. We use analytic arguments to show that the 
number of routing control  messages per topology change cannot scale better than 
linearly on Internet-like  topologies. We also employ simulations to confirm 
that logarithmic RT size  scaling gets broken by topology-independent 
addressing, a cornerstone of popular  locator-identifier split proposals aiming 
at improving routing scaling in the  presence of network topology dynamics or 
host mobility. These pessimistic  findings lead us to the conclusion that a 
fundamental re-examination of  assumptions behind routing models and 
abstractions is needed in order to find a  routing architecture that would be able 
to scale  "indefinitely.
------------end of quote ----------------------
 
Even studies made at universities can be completely off road. Let me give  
you an example that everyone can easily judge by himself/herself. Years ago 
when  I was studying your compact routing   a well US-funded routing project 
 caught my interest. Title: Capacity Constrained Routing Algorithms for  
Evacuation Planing (by Quingsong Lu et.al. University of Minnesota,  
Minneapolis). Hurricane Katrina ! New Orleans! How to evacuate a city! These  folks 
computed a huge number of routes (Dijkstras) while considering the  capacity 
constrains in particular.
But they did not even envision or discuss how to increase the capacity as  
much as possible.
 
For comparison: My own algorithm  assumes knowlege about the  network 
topology (e.g. the city map of New Orleans) plus a markation of all  those nodes 
at the rim of New Orleans, which people have to reach in order to be  safe. 
Within a second all links will be converted to arrows towards these exits,  
loop-free! Which means: all  streets become one-way roads, i.e. all  lanes 
of the entire street can be used, i.e. the capacity would be doubled. 
 
I say this because all these university researches didn't even scratch at  
what to do in order to do it right.
(And also, because  I still need this algorithm for TARA).
 
So again, I disagree. Furthermore, I am the best counter example: Because I 
 do not know as well as you size and structure of the internet, I can only 
deal  with any arbitrary topology, for which you claim scalable solutions 
can't be  found.
 
Heiner
 
In einer eMail vom 22.10.2010 20:49:22 Westeuropäische Sommerzeit schreibt  
[email-masked]:

folks,  the lack of consensus is quite expected.
putting many low-level details  aside, the deep
reason for that is the following, i think.

it  occurred to me in some off-line discussions here,
that folks are still  looking for scalable routing
which would work for any possible network  topology.
as mentioned way back  in
http://dx.doi.org/10.1145/1273445.1273450
scalable routing for  arbitrary networks cannot
exist. in fact, it's intuitively easy to  see,
but it's also a proven fact, like a theorem.
therefore the task of  building a scalable routing
solution for *arbitrary* networks cannot  succeed
in principle. the only option is to look for
solutions which  would work only for *specific*
networks, e.g., the global internet :) such  solutions
may be efficient and scalable if they find a way
to  intelligently utilize network  peculiarities.

best,
--
dima.
http://www.caida.org/~dima/

_______________________________________________
rrg  mailing  list
[email-masked]
http://www.irtf.org/mailman/listinfo/rrg