folks, thanks much for comments/questions! we try to address most (not all though) of these questions in the upcoming paper. some are easy, some have no answer so far :( i won't repeat them here now. for now, i'd comment only on the main one, the key message in the paper, which some have some difficulties with.
today, bgp speakers in the dfz keep... yes, not full, but almost full topological information about the more-or-less current state of the global internet AS-level topology. specifically, the union of bgp AS paths kept by a dfz bgp speaker forms something close to the spanning tree of the AS graph rooted at the AS where the speaker resides. of course, it's not exactly a tree, but it's pretty close to a directed acyclic graph (DAG) rooted at this this AS. so, this information is not exactly the *full* topological information (it would be exactly full if bgp was link-state!), but notice that the union of these DAGs across all ASs is pretty close to exactly the full knowledge of the global AS topology, distributed stored in the network. (of course, we couldn't go into such detailed explanations in nature, as the paper would get immediately rejected as too specialized and not interesting for general audience, so please be forgiving for that high-level language there :) and now a couple of obvious well-known observations re: bgp: 1) the amount of routing information each bgp speaker maintains is of the order of the number of destinations in the internet (be it prefixes, or ASs (if per-~AS aggregation ever happens)) 2) any AS topology change leads to exchange of bgp updates, path recomputations, etc., affecting, in the worst case, all ASs in the internet, and in the worst-worst case, may lead to persistent oscillations, i.e., *infinite* amount of routing information exchanged. and now a couple of maybe-not-so-obvious observations re: greedy routing using the map presented in the paper (if you read it carefully): 1) the amount of routing information an interdomain router maintains is of the order of the number of AS neighbors of the AS where the router resides. (indeed, the router needs to know only the coordinates of neighboring ASs; no per-destination information is required by routing.) 2) NO AS topology change ever leads to ANY exchange of ANY routing information; NO path recomputations ever occur. (well, if we indeed want NO updates, then when AS topology changes are very catastrophic (say 10% of internet fails!), then some small percentage of AS pairs cannot reach each other. in order to avoid this, one has to use some more sophisticated greedy routing algorithms, which require some very small amount of routing updates sent very locally -- details in the upcoming paper.) taken together, these two properties essentially say, that this routing is as good and as scalable as theoretically possible. if someone thinks that these results cannot potentially simplify routing in the internet making it more scalable, then... s/he might as well think that moving the center of the universe out from the center of the earth cannot potentially simplify celestial dynamics :) -- dima. http://www.caida.org/~dima/ On Friday, September 17, 2010 3:09 PM, Sampo Syreeni wrote: > On 2010-09-16, Robin Whittle wrote: > >> Nor does it appear to address the problems we have identified - a more >> scalable method than the current BGP-based DFZ for providing >> multihoming, inbound TE (traffic engineering) and mobility. > > Agreed. The paper only addresses what happens if the location based > routing table blows up as well. Essentially it is a geometrical routing > variant of CIDR, where the geometrical part enables some hop-by-hop > aggregation. Eventhough elegant in the routing metric sense, it doesn't > answer the core problems you just identified above without something > like locator/identifier separation. > > Still, this is an RG, not a WG. If a scenario where a location based > blowup is expected could be argued for, perhaps these kinds of ideas > would be of interest. My candidate for the scenario would be something > which causes the end user's local (sensor? adhoc?) network to enter the > DFZ en masse. I mean, there's no rule against future, fully routing > end-users in the Internet architecture. There's only the current, > justified, fear of what they might do the BGP core if they did enter. > > Then e.g. safety critical remotely controlled home networks could > benefit enormously from multihoming, and they're clearly coming. To wit, > I live in Finland, and will one day inevitably own a remotely controlled > sauna. If the stove, temperature sensor or smoke alarm go offline > because of a network outage, my house would literally burn down. I'm > guessing my insurance company would then argue due diligence for me to > multihome. So just there you might have a million new AS's, right there, > even with location/identifier separation. With route aggregation, that > won't blow up the core, but it sure will annoy penultimate routers at > the edge, unless there's a simpler way, like the geometric routing > solutions we're now talking about. > >> The biggest challenge, I think, is mobility for billions of devices, >> each responding to its own IP address, so it can interoperate with all >> other hosts using standard stack and application protocols [...] > > Very much agreed. But to amplify the point, we have to be able to > support a growing number of network locations as well, in addition to > identities/endpoints. For example, everybody's putting up open WiFi > hotspots in their home network nowadays, and a good netizen will soon > start to multihome those as well. Especially after common carrier phones > are finally killed as the only means of reliable emergency service. > Multimodal wireless technology *is* going to force that in the market. > > The end customer, he's going to have at least a backup connection via > wireless, which again means multihoming wrt the network topology. > > So as long as there's a competitive service landscape out there, > geography rarely aligns with network topology, and so multihoming will > yield limited returns in route aggregation over time. SO I think it's a > question where these kinds of geometric routing ideas might be employed. > Probably not as the primary routing paradigm. But deeper down, the work > seems like a valuable building block within an increasingly messy > topology. > >> The only way I can see of doing it is TTR Mobility: >> >> http://www.firstpr.com.au/ip/ivip/#mobile > > Frankly, I don't see IVIP's value proposition. Even with TTR-M. Could > you perhaps boil it down for me/us on-list? > > Personally I like HIP because it's truly end-to-end, thus core-neutral, > plus its progress on the IETF side is pretty far along. LISP is nice > since it's so eclectic and user-invisible, and since the LISP/ALT split > has a certain symmetry wrt location/identity. Most of all, the > combination's deployed and works all ways, having the "running code". I > just hope the robustness of the HIP protocol could somehow be combined > with LISP+ALT's benefits to the Unwashed Masses, plus that the total > expected loc/id mapping latency could be reduced to the absolute > minimum. > > I should also say, a number of papers on id/loc separating protocols > seem to be really close to each other. Unless I'm totally mistaken, they > could probably be mashed up together right now. I think it'd only > require a little bit of good will on all sides of the debate, such as it > did in the final stages of IPng or MPLS standardization. At the very > least we, as an RG, should start pegging some known-to-be-true design > criteria which could help weed stuff on its own merits. > >>> The scaling limitations of the existing Internet routing stem from >>> the requirement to have a current state of the Internet topology >>> distributed globally. >> >> This doesn't accord with my understanding. BGP doesn't generate or >> distribute a map or anything resembling "the current state of the >> Internet". > > A benevolent interpretation would be that "BGP lets faraway and even > inconsequential things affect your local routing state. We might not > want that." > >>> Such global knowledge is unavoidable, as routing has no source of >>> information other than the network topology. >> >> I think this too is incorrect. >> >> The BGP routing daemon in each BGP router certainly does have another >> source of information: the routes advertised by its neighbours. > > That is by definition topology within a connectivity graph, even if > incomplete. Not geometry e.g. in the sense of cost or real-world > distance, which the paper advocates. But still topology. > >> No BGP router has a clue about topology. > > It has hints of it, as restricted and aggregated along the path to any > given prefix, yet also knowable from as many distinct points as there > are links. We might say it has a "wary gossiper-told topology". > Geometry, BGP is by design oblivious about it, unlike what is being > proposed. > >> This has nothing to do with how a BGP router chooses the best path for >> packets addressed to a given BGP-advertised prefix. > > Agreed. BGP has nothing at all to do with this. Modifying it to do > geometric routing of any kind would be a major undertaking, because the > path vector model and the geometric one are so different. Essentially > building this proposal into BGP would bring about a new, very different > and higher in address overhead protocol, while perhaps cutting routing > table size and changing the basic routing algorithm. After that, it > probably shouldn't be called BGP to begin with. > >> How would this approach be adopted? > > Probably like LISP does. Using mapping of some kind from endpoint > addresses into geometrical ones. Then growing out the mapping > architecture piece by piece from the IS to the AS level, and with the > help of cooperating ASs, finally to the edge. At the very end the edge > nodes would start to use hyperbolically addressed geometrically routed > IPv7, if there was some benefit to it above IPv6 plus LISP/HIP/whatever. > > So perhaps the most forceful argument isn't something that can be said > on this list. Perhaps it's just "you talk the talk, but do you walk the > walk". There is an incremental upgrade path. Use it, and bid your money > on it as well. Let's see if it survives the test of real network > economics. > >> What changes to routers would be required? > > Massive. This stuff would blow every piece of silicon out of the water. > Thus, flag days are out of question, and we're still expecting proof of > concrete benefits. Still, would Eugene have passed it onto the list > unless it had some promise, as a building block? > >> How could this work with BGP? Modifications to BGP, creating a new >> network to replace the BGP-based DFZ? > > New. As I said, it's paradigm-shift material -- which I don't even think > should happen now. > >> Why would anyone adopt it? > > Perhaps because of the asymptotics? Even considering the worst case > scenario, this stuff scales very well in total address entropy, the > entropy of network distance in the typical networks which were analysed, > and the entropy of time-change of all of that data. The suggestion an > sich might be a stupid one, but the underlying ideas seem sound to me. > > But, of course, it won't solve the most pressing problems we have. It's > aimed at another direction entirely, I think. > >> As far as I can see, this is a paper about some new approach to >> constructing maps in coordinate systems which do not resemble ordinary >> Cartesian coordinates. > > That, and only that. > > I wouldn't trust my packets on that sort of thing. Not fully and only. > But at the very least TE heuristics and overlay networks coulds rely on > this stuff. If you then look at what ALT is in the contect of LISP, it's > also an overlay network... > >> Can anyone point out exactly why the techniques in this article could >> help with scalable routing? Without using an analogy, such as "The >> Internet's routing system operates like a road map. We have developed >> an improved way of making a map for this purpose." - because that >> analogy is false. > > Suppose you live on Earth. As far as humanity goes, it's pretty much a > thin shell on top of a ball; a sphere. With lots of interconnections > all-round. If the connections were neatly distributed all-round, they > would approximate a spherical topology, and their minimum delays should > yield and approximate geometry. So, we might try to route by absolute > location over the sphere: just bring this packet to any target which is > precisely there. No matter the route, just diffuse the packet into there > any which way. > > That sort of stuff can be done very easily. There are proven, local > search algorithms for that sort of forwarding. And they work even in the > context of heuristics, as in A* search. As long as your local search is > good enough and either a) your network is convex or b) your search > algorithm is guaranteed to backtrack far enough, you will find the > target. > > In this sort of application, the "curse of dimension" works backwards: > suddenly your ability to embed the whole routing graph into Euclidean > space where it's easy to calculate things becomes so much easier. Now we > then have the hyperbolic embedding, which seems to be even better. That > should cut down on coordinate lengths, lead to higher average stability > even as nodes move around, and thus forth. The paper we're tálking about > really does hold promise. > > For some limited things. > > (BTW, these ideas have been around for awhile, at least in scifi: just > tell the ICBM address and let the packet diffuse through omnipresent > motes. The scifi ideas didn't work well with practical economics (e.g. > who's gonna pay for the motes over any given area?). Why would the > economics play out better in here? Thus, I once again see the idea as a > building block, not as a final solution.) > -- > Sampo Syreeni, aka decoy - [email protected], http://decoy.iki.fi/front > +358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2 _______________________________________________ rrg mailing list [email protected] http://www.irtf.org/mailman/listinfo/rrg
