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 protected]:
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 protected] http://www.irtf.org/mailman/listinfo/rrg
_______________________________________________ rrg mailing list [email protected] http://www.irtf.org/mailman/listinfo/rrg
