On Thursday, September 16, 2010 1:42 AM, JinHyeock Choi wrote: > Dmitri
JinHyeock, > This is very interesting scheme with unbelievable results. thanks! :) > I just wonder how you come to an idea of > mapping the Internet into Poincaré disk. hard question :) -- "Geographic routing using hyperbolic space" by R. Kleinberg in INFOCOM 2007 was quite inspirational, but many other pieces as well.. > Let me ask you a few clarifying questions. > > I assume > the mapping is relevant > (i.e. resulting in efficient greedy routing) > only when it satisfies congruence condition. yes. > Does your mapping (into hyperbolic space) > satisfy the congruence condition? yes. > I understand that > the congruence condition means > among any two connected nodes, > there exists a path similar to geometric geodesic, > right? yes. we explicitly say, in a different paper, though http://arxiv.org/abs/1006.5169 that the hyperbolic stretches (s_2 and s_3 there) must be small. > I can only find in FIG 4 > the similarities of connection probability. > Is that enough? obviously if all stretches are 1 (s_1=s_2=s_3=1 as defined in http://arxiv.org/abs/1006.5169 ) then it's definitely enough. we believe that the match of connection probabilities is also "good enough", but we don't have any proof. > In general how can you determine whether > a mapping (into any geometric space) satisfies congruence condition? see above. > When you compute a path between two nodes with greedy routing, > is the path (avg stretch 1.1) similar to the hyperbolic geodesic? yes. >> topology dynamics is >> concern #1 in geometric routing. that's why we considered both >> short- and long-term dynamics, all in the paper. we emulate the >> former (by killing a percentage of links and nodes) and >> replayed the latter using the measurable history of internet >> evolution over the past few years with ASs and AS connections >> appearing, disappearing, etc., and the results are still very >> good, pretty much the same as for the static case. amazing, >> isn't it? i know it's hard to believe, and even we can't stop being >> surprised how well it works. > > Yes, it really is amazing. > Especially it’s hard to believe the second part that > hyperbolic coordinate is static even after AS changes indeed, you got it! > Intuitively it feels likely that > a few new undersea cable would disrupt entire hyperbolic space. and that's NOT what happens! > Any idea of underlying principle/ theory of how it works? it's pre-explained in the paper: -- "The explanation for the surprising efficiency of greedy forwarding with respect to random failures lies in the unique combination of the following two properties exhibited by scale-free, strongly clustered networks: high path diversity24, and congruency between hyperbolic geodesics and topologically shortest paths13, 15. The latter is illustrated by the similar path patterns of the hyperbolic geodesic and topologically shortest path between nodes a and b in Figure 2: they both first go to the high-degree core of the network, and then exit it in the appropriate direction to the destination. Owing to high path diversity, there are many disjoint shortest paths between the same source and destination, and thanks to the congruency, they all stay close to the corresponding hyperbolic geodesics. Link and node failures affect some shortest paths, but others remain, and greedy forwarding can still find them using the same hyperbolic map." -- a bit mode detailed explanation is sec.X.E in http://arxiv.org/abs/1006.5169 and even more detailed one (with examples on the real internet) will be in the next paper on this subject. >> we have another paper in submission, >> where we take space to explain why it works so well, and where >> we discuss some aspects of what it would take to implement >> and use this stuff in practice. > > that would be great. > >> no, since those are not globally known or even measurable! >> we used the AS relationship inferences in >> http://www.caida.org/data/active/as-relationships/ >> to check how many greedy paths are compliant with >> *inferred* AS-level policies, and how many non-compliant >> paths can be fixed by what Sampo alludes to >> (specifically by the policy bit from "M. Motiwala, M. Elmore, >> N. Feamster, and S. Vempala. Path splicing. SIGCOMM, 2008"). >> the result is 99+% of paths are policy-compliant. > > Your results are hard-to-believe good. > It would be great to find out underlying principles > to understand how it works so well. > > Thanks for your kind consideration. > > Best regards > > JinHyeock Choi best, -- dima. http://www.caida.org/~dima/ > On Thu, Sep 16, 2010 at 2:04 AM, Dmitri Krioukov <[email protected]> wrote: >> hi yangyang, >> >> no, since those are not globally known or even measurable! >> we used the AS relationship inferences in >> http://www.caida.org/data/active/as-relationships/ >> to check how many greedy paths are compliant with >> *inferred* AS-level policies, and how many non-compliant >> paths can be fixed by what Sampo alludes to >> (specifically by the policy bit from "M. Motiwala, M. Elmore, >> N. Feamster, and S. Vempala. Path splicing. SIGCOMM, 2008"). >> the result is 99+% of paths are policy-compliant. >> >> best, >> -- >> dima. >> http://www.caida.org/~dima/ >> >> On Tuesday, September 14, 2010 3:42 AM, Yangyang Wang wrote: >> >>> Hi Dmitri, >>> >>> I don't understand. Do you mean that this kind of greedy routing can >>> generate routing paths that satisfy all possible routing policies in TE, >>> load balancing, etc. >>> >>> >>> Thanks >>> >>> Yangyang >>> >>> ----- Original Message ----- >>> From: "Dmitri Krioukov" <[email protected]> >>> To: "'Tony Li'" <[email protected]> >>> Cc: "'IRTF Routing RG'" <[email protected]> >>> Sent: Tuesday, September 14, 2010 6:52 AM >>> Subject: Re: [rrg] Fwd: Sustaining the Internet with hyperbolic mapping >>> >>> >>>> thanks, sure, this subject is also in that other in-submission paper. >>>> in a nutshell: almost all greedy paths are policy-compliant paths! >>>> BUT: if we want to *actively* manage mapping as a function of >>>> policies, then it's currently impossible, although we have some >>>> ideas on how to achieve this.. >>>> -- >>>> dima. >>>> http://www.caida.org/~dima/ >>>> >>>> On Monday, September 13, 2010 3:24 PM, Tony Li wrote: >>>> >>>>> Hi Dmitri, >>>>> >>>>> Might I suggest that a discussion of transit policies might also be in >>>>> order? >>>>> >>>>> Thanks, >>>>> Tony >>>>> >>>>> >>>>> On Sep 13, 2010, at 3:08 PM, Dmitri Krioukov wrote: >>>>> >>>>>> thanks much for you comments! indeed, topology dynamics is >>>>>> concern #1 in geometric routing. that's why we considered both >>>>>> short- and long-term dynamics, all in the paper. we emulate the >>>>>> former (by killing a percentage of links and nodes) and >>>>>> replayed the latter using the measurable history of internet >>>>>> evolution over the past few years with ASs and AS connections >>>>>> appearing, disappearing, etc., and the results are still very >>>>>> good, pretty much the same as for the static case. amazing, >>>>>> isn't it? i know it's hard to believe, and even we can't stop being >>>>>> surprised how well it works. we have another paper in submission, >>>>>> where we take space to explain why it works so well, and where >>>>>> we discuss some aspects of what it would take to implement >>>>>> and use this stuff in practice. >>>>>> -- >>>>>> dima. >>>>>> http://www.caida.org/~dima/ >>>>>> >>>>>> On Friday, September 10, 2010 4:29 PM, Sampo Syreeni wrote: >>>>>> >>>>>>> On 2010-09-09, Dmitri Krioukov wrote: >>>>>>> >>>>>>>> marshall, thanks for posting it here. i also thinks it's relevant :) >>>>>>> >>>>>>> Thanks from me too, and it's certainly relevant. Still, it might not be >>>>>>> as good an idea as it sells itself as. >>>>>>> >>>>>>> Geometric routing ideas have been around for quite a while now. They >>>>>>> certainly do this sort of thing within manets right now, because of the >>>>>>> spatial nature of a cloud of terminals/sensors. So in certain ways the >>>>>>> idea works well indeed. >>>>>>> >>>>>>> I'd be the first to say that geometric routing is a swell and elegant >>>>>>> idea. Yet, it tends to have some inherent problems in the wired setting >>>>>>> where a) the topology and the geometry of the network isn't as static as >>>>>>> a cloud of 3D sensors would see, b) where we have to have static contact >>>>>>> points like DNS fully available at more or less fixed destination >>>>>>> addresses all of the time, to map from points of interest to >>>>>>> topological/geometrical addresses/locations, c) any static mapping like >>>>>>> the one proposed in the paper could *severely* undercut routing >>>>>>> efficiency as soon as someboby built a new undersea cable, which of >>>>>>> course severely changes the routing landscape in one fell swoop, and d) >>>>>>> when we then probably would go with an adaptive routing protocol, there >>>>>>> is a serious problem with asymmetric paths. That final problem doesn't >>>>>>> plague just Euclidean distance measures, but all of the metric ones as >>>>>>> well, including the hyperbolic. >>>>>>> >>>>>>> As regards an adaptive geometric routing protocol, IRTF's ALTO group has >>>>>>> charted this stuff quite extensively already in the context of routing >>>>>>> within overlay networks. I suggest everybody look into that body if they >>>>>>> haven't already, if interested in geometric routing. >>>>>>> >>>>>>> In my opinion, this particular article is a nice touch onto how best >>>>>>> parametrize network distance. Based on the article and the references, a >>>>>>> hyperbolic space might well provide us with a better parametrization of >>>>>>> distance in a scale-free network within the geometric routing paradigm. >>>>>>> But it won't solve the more fundamental problems which have stopped us >>>>>>> from adopting geometric routing in the past. >>>>>>> >>>>>>> I'd say this body of work is a building block for further research, more >>>>>>> than the showstopper it'd like us to see itself as. >>>>>>> -- >>>>>>> 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 >>>> >>>> _______________________________________________ >>>> rrg mailing list >>>> [email protected] >>>> http://www.irtf.org/mailman/listinfo/rrg >> >> _______________________________________________ >> rrg mailing list >> [email protected] >> http://www.irtf.org/mailman/listinfo/rrg _______________________________________________ rrg mailing list [email protected] http://www.irtf.org/mailman/listinfo/rrg
