Subject: [rrg] Fwd: Sustaining the Internet with hyperbolic mapping

From: Marshall Eubanks <[email-masked]>
Date: Thu, 9 Sep 2010 08:43:51 -0400

This seems like it would be of interest to RRG members.

Regards
Marshall

Begin forwarded message:

> From: Eugen Leitl <[email-masked]>
> Date: September 9, 2010 6:23:26 AM EDT
> To: NANOG list <[email-masked]>
> Cc: [email-masked], forkit! <[email-masked]>
> Subject: Sustaining the Internet with hyperbolic mapping
> 
> 
> http://www.nature.com/ncomms/journal/v1/n6/full/ncomms1063.html 
> 
> Sustaining the Internet with hyperbolic mapping
> 
> Marián Boguñá, Fragkiskos Papadopoulos & Dmitri Krioukov
> 
> Nature Communications 1 , Article number: 62 doi:10.1038/ncomms1063
> 
> Received 06 April 2010 Accepted 06 August 2010 Published 07 September 2010
> 
> Abstract
> 
> The Internet infrastructure is severely stressed. Rapidly growing overheads 
> associated with the primary function of the Internet—routing information 
> packets between any two computers in the world—cause concerns among Internet 
> experts that the existing Internet routing architecture may not sustain even 
> another decade. In this paper, we present a method to map the Internet to a 
> hyperbolic space. Guided by a constructed map, which we release with this 
> paper, Internet routing exhibits scaling properties that are theoretically 
> close to the best possible, thus resolving serious scaling limitations that 
> the Internet faces today. Besides this immediate practical viability, our 
> network mapping method can provide a different perspective on the community structure 
> in complex networks.
> 
> [full text snipped]
> 
> -- 
> Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
> ______________________________________________________________
> ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
> 8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE
> 
>

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Thu, 9 Sep 2010 12:46:14 -0700

marshall, thanks for posting it here.
i also thinks it's relevant :)
-- 
dima.
http://www.caida.org/~dima/

On Thursday, September 09, 2010 5:44 AM, Marshall Eubanks wrote:

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

---

From: Sampo Syreeni <[email-masked]>
Date: Sat, 11 Sep 2010 02:29:27 +0300 (EEST)

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-masked], http://decoy.iki.fi/front
+358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Mon, 13 Sep 2010 15:08:58 -0700

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/

---

From: Tony Li <[email-masked]>
Date: Mon, 13 Sep 2010 15:24:05 -0700

Hi Dmitri,

Might I suggest that a discussion of transit policies might also be in order?

Thanks,
Tony

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Mon, 13 Sep 2010 15:52:35 -0700

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/

---

From: Sampo Syreeni <[email-masked]>
Date: Tue, 14 Sep 2010 02:08:10 +0300 (EEST)

> Might I suggest that a discussion of transit policies might also be in 

The way I see geometric routing is that it is fundamentally different 
from the normal kind, because it's not about discrete topology, but a 
continuous geometry. It doesn't much matter which way you throw a 
packet, as long as it travels somewhat towards the right target. This, I 
believe, is what is also mostly behind the stability results presented 
above. So as long as you respect the fact that the geometric distance 
towards the target is diminishing with each routing hop (perhaps with 
minor, guaranteed to be bounded deviations e.g. for dead hops) you can 
be reasonably sure, especially within scale-free networks that the paper 
relies on, that the packet will arrive at the correct destination.

In that case it should be possible to do policy routing as well. As a 
first approximation it would be purely at the local, per-router level. 
Whatever metric you were using, you could use it like you would use a 
heuristic distance in an A* search, and forward based on policy as long 
as you didn't violate the heuristic. The proof of why A* goes through 
could be used to show why the packet will eventually be forwarded, using 
similar assumptions. I'm far from sure what else could be done with some 
further refinement, but that seems like a reasonable and well-documented 
starting point.

The more basic problem remains that asymmetry breaks every proof of this 
kind I've seen. Topology propagation is at least a theoretical problem, 
evenas the paper does present concrete empirical evidence that a static 
geometric routing paradigm could perhaps be surprisingly stable. There 
is also no substantive analysis of when drift in the routing geometry 
(here we cannot talk about topology alone) might necessitate the 
equivalent of renumbering the network, and how to maintain those stable 
reference points I already mentioned. As you already hinted at, policy 
routing based on AS's down the path do not seem too easy to incorporate. 
And then there is also the overall question of what the distance metric 
should be in the first place, especially keeping in mind that we might 
have IntServ/DiffServ objectives in mind as well, with multiple 
simultaneous traffic engineering constraints, and their mutual 
interactions. After all, here we're working with a very real distance 
measure just like in distance vector protocols, and that was given up 
for paths for a reason in BGP. (OTOH, the paper might also allow highly 
compressed and computationally efficient representations of multiple 
distance metrics at the same time, with little temporal instability. If 
so, that's again interesting.)
-- 
Sampo Syreeni, aka decoy - [email-masked], http://decoy.iki.fi/front
+358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2

---

From: Mikael Abrahamsson <[email-masked]>
Date: Tue, 14 Sep 2010 07:43:57 +0200 (CEST)

> as good an idea as it sells itself as.

I agree.

If it makes economic and technical sense (and it probably will) then more 
and more peering will be done locally and we will achieve more 
geographically optimized routing anyway.

I don't believe in overlay networks. It's generally expensive to do 
encapsulation/decapsulation, I've always avoided it as much as been 
possible.

-- 
Mikael Abrahamsson    email: [email-masked]

---

From: Mikael Abrahamsson <[email-masked]>
Date: Tue, 14 Sep 2010 12:04:34 +0200 (CEST)

On Tue, 14 Sep 2010, Mikael Abrahamsson wrote:

I just realised I probably spoke without understanding what the paper 
really was about. It's only about mapping, right? There is nothing in 
there as to what this information could actually be used for?

So after doing this mapping, what can be done with it? I haven't 
really studied math at university level, only been doing networking for 
10+ years :P

Could someone please write a bit more about the practical implications?

---

From: "Yangyang Wang" <[email-masked]>
Date: Tue, 14 Sep 2010 18:41:56 +0800

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

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Wed, 15 Sep 2010 10:04:59 -0700

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,

---

From: Sampo Syreeni <[email-masked]>
Date: Wed, 15 Sep 2010 23:50:00 +0300 (EEST)

On 2010-09-14, Yangyang Wang wrote:

> generate routing paths that satisfy all possible routing policies in 
> TE, load balancing, etc.

It cannot, in full generality. As I already said, the ALTO people and 
other people in that department have some expertise under their belt in 
the overlay context with geometric routing. Perhaps we should refer the 
article to them for some independent background and commentary? On the 
side, without stopping the discussion here?
-- 
Sampo Syreeni, aka decoy - [email-masked], http://decoy.iki.fi/front
+358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2

---

From: JinHyeock Choi <[email-masked]>
Date: Thu, 16 Sep 2010 17:42:10 +0900

Dmitri

This is very interesting scheme with unbelievable results.

I just wonder how you come to an idea of
mapping the Internet into Poincaré disk.

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.

Does your mapping (into hyperbolic space)
satisfy the congruence condition?

I understand that
the congruence condition means
among any two connected nodes,
there exists a path similar to geometric geodesic,
right?

I can only find in FIG 4
the similarities of connection probability.
Is that enough?

In general how can you determine whether
a mapping (into any geometric space) satisfies congruence condition?

When you compute a path between two nodes with greedy routing,
is the path (avg stretch 1.1) similar to the hyperbolic geodesic?

> topology dynamics is
> 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

Intuitively it feels likely that
a few new undersea cable would disrupt entire hyperbolic space.

Any idea of underlying principle/ theory of how it works?

> we have another paper in submission,

that would be great.

> 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

---

From: Robin Whittle <[email-masked]>
Date: Thu, 16 Sep 2010 21:33:29 +1000

Short version:   I think this article has nothing to do with
                 Internet routing and so does not provide any
                 significant insights into or practical solutions
                 to the routing scalability problem.

This article:

  Sustaining the Internet with Hyperbolic Mapping
  http://www.nature.com/ncomms/journal/v1/n6/full/ncomms1063.html
  http://www.nature.com/ncomms/journal/v1/n6/pdf/ncomms1063.pdf

doesn't seem to be relevant to AS networks and the BGP-based
interdomain routing system as I understand them.  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.

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 - with
generally optimal or close to optimal paths and session survival via a
persistent IP address, no matter how the "care of" address(es) change.
 The only way I can see of doing it is TTR Mobility:

  http://www.firstpr.com.au/ip/ivip/#mobile

To see my understanding of the goals of scalable routing, please see
section 17.2 of:

   http://www.ietf.org/mail-archive/web/rrg/current/msg06219.html

My sense that the article's premises don't accord with reality begins
with the 3rd paragraph:

   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".  It is simply a method by which the routers can work
together so that each router can, decide which neighbor to forward a
packet to, based on the shortest BGP-advertised prefix the destination
address matches.  This is done in a manner by which outages and
topology changes result in changed route advertisements by each
router, and so to changed choices and further changes of route
advertisements by other connected routers.

For some routers - such as those where "the rest of the Internet" is
reached by a single neighbor, this means that packets addressed to
pretty much every BGP advertised prefix are all sent to one particular
neighbor.  For other routers in the "DFZ" (Default-Free Zone), there
will be two or more neighbours which the router decides are the best
ones to handle packets addressed to "the rest of the Internet" (that
is, the prefixes which are not ones this router handles itself).

   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.  This
is what it uses.  No BGP router has a clue about topology.

   Routing in these conditions is equivalent to routing using a
   hypothetical road atlas, which has no geographical information
   but merely lists road network links, which are pairs of
   connected road intersections, abstractly identified.

This describes a text-form of a map, similar to a printed circuit
board netlist - where distances between connected items are
irrelevant, but the total set of connections is specified exactly.

This has nothing to do with how a BGP router chooses the best path for
packets addressed to a given BGP-advertised prefix.  There's nothing
resembling a road map or any other map.  There's just a bunch of
advertised routes from neighbours, each with its own list of ASes
which must be traversed to reach the destination.  Then the router has
its BGP algorithm and local policy for choosing one of these.  It then
advertises this path to its other neighbours, perhaps with extra AS
numbers added.

So how does the rest of the article relate to the Internet in general,
or to the interdomain routing system in particular?  As far as I can
see, it doesn't.

How would this approach be adopted?

What changes to routers would be required?

How could this work with BGP?  Modifications to BGP, creating a new
network to replace the BGP-based DFZ?

Why would anyone adopt it?

When would they derive any benefits?  After the rest of the world
adopts it too?

If it was adopted, how would ASes get their routers to implement the
policies they current set for them?

How would this provide multihoming to more end-user networks?  I guess
this would have to be either without requiring each to have an ASN, or
allowing millions of such networks to get an ASN, but somehow have
this not matter.

How would mobility be achieved in a robust and scalable manner, for
hundreds of millions or billions of devices - with IPv4 or IPv6?

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.  I guess this is of interest to some folks -
but I don't agree with the central premise that these techniques are
relevant to Internet routing or to a new approach to routing which
would better meet the needs of ASes.

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.

 - Robin

---

From: Heath Jones <[email-masked]>
Date: Thu, 16 Sep 2010 12:46:15 +0100

Hi Robin

I'm very new to this list, so apologies if I'm not posting in a correct
format / method. My very simple question is this:

The paper discusses connectivity to AS's and a method of 'guessing' where an
AS is, at the advantage of not needing to store as much topographical
information. Atleast that is my take on it..

The thing I don't get is how does that relate to prefixes. Is the
implication that the router will keep just a list of origin AS's and the
prefixes advertised by each, as opposed to full path information?

Cheers
Heath

---

From: Robin Whittle <[email-masked]>
Date: Thu, 16 Sep 2010 22:08:17 +1000

Hi Heath,

You wrote:

> I'm very new to this list, so apologies if I'm not posting in a
> correct format / method. My very simple question is this:

Chair Tony Li is the one to judge that, but your message looks good to me.

> The paper discusses connectivity to AS's and a method of 'guessing'
> where an AS is, at the advantage of not needing to store as much
> topographical information. Atleast that is my take on it..

That is my impression.  My point is that DFZ routers don't store any
topographical information - so the paper seems to have nothing to do
with today's routers.

> implication that the router will keep just a list of origin AS's and
> the prefixes advertised by each, as opposed to full path information?

Maybe so - that's for the authors and others to respond to.

An AS could span the entire world, and have routers all over the Net,
with one or more of these routers advertising a particular prefix.  As
I understand the operation of the interdomain routing system, its not
good enough to forward the packets whose destination addresses match
this prefix to any router which belongs to this AS.  They should be
forward to the one or more routers which advertises the prefix.

 - Robin

---

From: Sampo Syreeni <[email-masked]>
Date: Fri, 17 Sep 2010 23:35:26 +0300 (EEST)

> encapsulation/decapsulation, I've always avoided it as much as been 

It should be avoided as much as possible, but then, it usually cannot be 
fully avoided thanks to layer-to-layer translations. Take for instance 
DNS; it's a full-blown overlay in itself already, yet a necessary one. 
It's just that we shouldn't be building an overlay on top of another 
overlay without a very good reason.

I think the way towards such a goal is to build more expressive 
interfaces between the different layers, as need arises. That way 
functionality doesn't have to be rebuilt at higher and/or inappropriate 
layers, since everything that is needed to implement it at the proper 
layer is already present.

Of course such interface/layer definitions are hard to do. But not 
*that* hard at the edge. They tend not to involve hardware today.
-- 
Sampo Syreeni, aka decoy - [email-masked], http://decoy.iki.fi/front
+358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2

---

From: Sampo Syreeni <[email-masked]>
Date: Sat, 18 Sep 2010 01:09:05 +0300 (EEST)

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.

> 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.

> 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.
>
> 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.
>
> 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.

> 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?

> 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.

> 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...

> an improved way of making a map for this purpose." - because that 

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-masked], http://decoy.iki.fi/front
+358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Sat, 18 Sep 2010 15:09:08 -0700

> Dmitri

JinHyeock,

> This is very interesting scheme with unbelievable results.

thanks! :)

> 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..

> only when it satisfies congruence condition.

yes.

> satisfy the congruence condition?

yes.

> there exists a path similar to geometric geodesic,

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.

> the similarities of connection probability.

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.

> a mapping (into any geometric space) satisfies congruence condition?

see above.

> is the path (avg stretch 1.1) similar to the hyperbolic geodesic?

yes.

> hyperbolic coordinate is static even after AS changes

indeed, you got it!

> 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.

best,

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Sat, 18 Sep 2010 15:09:20 -0700

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/

---

From: Robin Whittle <[email-masked]>
Date: Tue, 21 Sep 2010 02:56:01 +1000

Short version:   I still think this Hyperbolic mapping work:

                 is based on a false premise, and has not yet been
                 demonstrated to actually apply to the Internet's
                 routing scaling problems, much less solve them.

Hi Dmitri,

Thanks for your response.  I am not suggesting that your research can
have no importance for some communication networks.  I think its great
that you are able to cross-pollinate fields as diverse as graph theory
and statistical mechanics:

     We then establish a mapping between our geometric framework
     and statistical mechanics of complex networks. This mapping
     interprets edges in a network as non-interacting fermions
     whose energies are hyperbolic distances between nodes, while
     the auxiliary fields coupled to edges are linear functions
     of these energies or distances.

Hopefully there will be some hybrid vigour!

My critique of your paper:

is twofold:

  1 - The starting premise of the paper is incorrect.

  2 - The claim that your approaches could be of practical use
      in improving Internet routing, is subject to critiques
      including:

        a - Your theoretical framework does not adequately match
            the needs of ASes - that there is more to the behavior
            required of routers than is captured in your conceptual
            framework.

        b - Even if some benefits could be shown from your approach
            there are profound practical barriers in implementing it
            - either by modifying the BGP system as it operates or
            building an alternative system in parallel with it to
            eventually replace it.

        c - You haven't identified particular problems in the current
            system which your approach would solve - and then shown
            how this would achieve the goals which are widely agreed
            upon, such as:

               More scalable portability (or at least ability to
               change providers without disruption or excessive
               risk and cost), multihoming and inbound TE.

               Global mobility, with generally optimal path lengths
               and ideally full support for existing IPv4 and IPv6
               application protocols, application software and
               stacks.

            Nor have you evaluated alternative approaches which would
            be easier develop and and have widely adopted.

        d - You haven't presented any account, much less a
            sufficiently detailed account, of how various types of
            ASes want and need to run their routers.  In particular,
            I think your AS-centric focus seems to assume that an
            AS would be happy to receive packets on any of its BRs.
            Yet this is often not the case, since its network could
            be very large and not well meshed and because it wants
            packets for particular prefixes to arrive at particular
            BRs, for reason of policy, load balancing or other
            reasons of inbound TE.

My proposal: http://www.firstpr.com.au/ip/ivip/ is intended to do
achieve goals which I believe will solve the problems we face.  My
understanding of these goals is stated more fully in this evaluation
of all the proposals (though IRON has changed since then,
and though it later emerged that ILNP appears to be incapable of
working with existing IPv6 applications):

Ivip wouldn't warrant a paper in Nature.  There's no great conceptual
framework, invoking particular branches of graph theory - or need
for equations.  There are several novel mechanisms in it, but they are
of technological interest.  I don't think there's anything of interest
to mathematicians in Ivip.

I think the fact that you can get your paper accepted in Nature - I
guess in part because of your claim that it is relevant to the
important question of Internet routing - and the fact that four teams
of researchers can be funded to the tune of $8M each for elaborate
research proposals:

  http://www.nsf.gov/news/news_summ.jsp?cntn_id=117611

indicates that there is strong interest in some quarters for
networking solutions involving great elaboration and the sort of
mathematically complex work usually performed by academics.

I provide a reasonably well explained set of mechanisms which I think
will do the trick.  There's no high-flying theoretical flourishes, but
the task of in-flight upgrades to the worlds largest IT system means
that there's quite a lot to write about the problem and the proposed
enhancements.

You wrote:

> of the global internet AS-level topology. 

I think this is still far overstating the information which a BGP
router obtains from its neighbors.

> specifically, the union
> the speaker resides. 

I think this is not the case.  The paths in each route advertisement
from a neighbor mention ASes but each route is for a particular
prefix.  Its purpose is not to tell something about the final AS in
the path - and there could be thousands of separate routes with the
one AS as the final ASN, but they could be for different routers in
the one AS, and these routers could be all over the world.

Your notion of an AS being a unitary vertex in any kind of graph
doesn't accord with my understanding of the interdomain routing system.

BGP routers deal with routes which their neighbors advertise to them,
one for each of hundreds of thousands of prefixes.  Each route
contains a sequence of ASNs, with the final ASN being that of the
router at the end of the path - which is the router, or one of the
routers, which advertised this prefix from the edge of the DFZ to its
neighboring DFZ routers.

Each router doesn't care much about the AS at the end of the list, but
it does check all the ASNs in the list to make sure none of them match
its own ASN.  If any do, then it doesn't bother using this advertised
route for its own packets.  Therefore, it won't propagate such a route
to its neighbors.

Your statement might be true if:

   1 - All BGP routers dealt not with routes for prefixes of address
       space, but with some other kind of "route" - a body of
       information about how packets can be sent to a given AS.

   2 - If every such "route" was propagated by BGP routers
       irrespective of any local policy.

   3 - If the way it was propagated did not involve any extra padding
       of duplicate ASNs - or alternatively if those duplicate ASNs
       were ignored for the purpose of developing what you claim is
       is the BGP router's information about the topology of the Net.

But BGP routers work with routes for prefixes.  One complication is
that AS-1111 might advertise a short prefix 12.34.0.0/16 and another
AS-2222 might advertise a longer prefix 12.34.56.0/24 which matches a
subset of the /16.

Another is that with anycast, multiple routers in multiple ASes may
advertise the same prefix.  So a given BGP router A might be offered
two or more routes by its neighbors, for the one prefix, and the end
routers in each route are in different ASes.   This is of no concern
to router A when choosing which one of these routes to use, and so to
offer to its neighbors, with its own ASN appended one or more times.

So BGP routers really don't care much about how ASes are
interconnected - except with the algorithm just mentioned, which is
there to avoid routing loops at least, and perhaps for no other purpose..

I agree that it would be possible for a router A to infer some
topological information about how the ASes in the Net connect to each
other based on the routes it is offered by its neighbours.  However,
for two prefixes XX and YY, both of which are advertised by a router
(perhaps the same router) in AS-3333, the router A might be offered
completely different, or very different, routes by its neighbors I and J.

  Neighbor I:   XX  AS-5555, AS-6666, AS-3333
                YY  AS-5555, AS-8888, AS-9999, AS-3333

  Neighbor J:   XX  AS-4444, AS-7777, AS-6666, AS-3333
                YY  AS-4444, AS-2222, AS-3333

So what can router A make of all this in terms of topology?  It could
take the whole set and infer something about connections between these
ASes, but it is not useful information for its purposes.  The fact
that it can get packets addressed to YY to a router in AS-3333 via
neighbor I, via AS-5555, AS-8888 and AS-9999 is of no general
interest.  This only applies to prefix YY via neighbor I.  This
information is of no importance for deciding how to handle packets
addressed to prefix XX, via neighbor J, since the route neighbor J
advertised is completely different.

Router A will only pass on to its neighbours a single route for XX and
a single route for YY.  So at each point in the BGP network, such as
router A, the flow of supposedly topographical information (or
information from which some topology might be inferred) is affected by
local policy decisions and the BGP algorithm for choosing between
multiple routes.

The basic things BGP routers are dealing with do not relate to ASes at
all - they are for address prefixes.

Furthermore, whether a given BGP router accepts or rejects a route
based on policy depends on many things which are not related to
topology.  The rejection, including the de-preferencing of one route
over another route for a given prefix may have nothing to do with the
ASNs on the routes, but may be due to a policy which concerns the
prefix and some local preference for a given link to a particular
neighbour.

So I stand by my critique of a central premise of your paper:

  This describes a text-form of a map, similar to a printed circuit
  board net-list - where distances between connected items are
  irrelevant, but the total set of connections is specified exactly.

> of course, it's not exactly a tree, but it's pretty

The routes offered by neighbors of router A in AS-1111 can have paths
which include AS-1111.  So at that level, the information is not
acyclic.  Router A chooses to ignore those routes which include
AS-1111, which makes the set of routes not rejected by this mechanism
acyclic.

> in the network. 

If you somehow could grab every BGP router's advertised routes, you
could probably build a map of how the ASes interconnect.  However, it
is a mathematical convenience - a fiction, I think - to portray an AS
as a vertex in a DAG.

An AS could have 30 routers all over the world, each of them not
connected directly to the others.  In no sense is such an ASN a
vertex-like point in a network.

If all these conditions were met:

   1 - Every AS had all its border routers (BRs) fully meshed or
       efficiently forwarding packets to each other within its own
       network.

   2 - Every BR in the AS advertised the same set of prefixes.

   3 - If no other AS advertised the prefixes advertised by other
       ASes.

   4 - If there were no overlapping prefixes (e.g. 12.34.0.0/16
       covering the more-specific 12.34.56.0/24).

Then, you would be closer to being able to build a topological
understanding of the Net from access to the advertised routes of all
BGP routers.  Then, there would be some validity to treating each AS
as a single unit - something which could be reasonably regarded as a
vertex in a directed acyclic graph or similar topological construct.

However, the pattern of "AS connectivity" which emerges from the
advertised routes for one prefix may differ from that which emerges
from the advertised routes for another prefix.

A BGP router doesn't care about AS connectivity.  All it wants to know
is which of the router's neighbours to forward packets to, where those
packets match a particular prefix.

> (of course, we couldn't go into such detailed

You think that a general audience is interested in and ready to
understand several thousand words concerning a specialised area of
graph theory?!   Even in Nature Communications, with articles (from
the most recent issue):

   No-go theorem for superradiant quantum phase transitions in
   cavity QED and counter-example in circuit QED

   Non-muscle myosin II regulates survival threshold of
   pluripotent stem cells

   Upright human gait did not provide a major mechanical
   challenge for our ancestors

   Phase seeding of a terahertz quantum cascade laser

   Automated home-cage behavioural phenotyping of mice

   Breeding latitude drives individual schedules in a trans-
   hemispheric migrant bird

I think only a small subset of readers are going to be able to follow
your graph theory material.  I haven't tried to follow it.  I have
broad interests and general knowledge, but I guess it would take me a
week or two to learn even the basics of graph theory to be able to
understand exactly what "hyperbolic mapping" means.  Your paper for
Physical Review E:

contain a tutorial on hyperbolic geometry, which I think would be
essential reading for anyone who is not already versed in the field.
But to understand and evaluate your hypothesis and claims would be a
lot of work.  So I don't think you could argue that a bunch of readers
are already up to speed on graph theory, but were not prepared for a
more carefully defined link between your work and the Internet.

Given the sophistication you assume in your audience, I think you
could have done much better in explaining the premise of your paper -
with description of the behavior required of BGP routers.

However, if you had done so - and the Nature word count limit may have
precluded this - I think you would find that your premise is false.
BGP routers are not concerned with the interconnection of ASes.  So
your solution - which I think is concerned with optimising their
ability to route packets based on AS connections - does not seem to me
to be applicable to the BGP system or the problems it faces.

Neither of your papers mention "BGP" or "prefix".  "Policy" is only
mentioned once in the Pys Rev E paper.

I believe the BGP system works very well.  I believe it scales well as
long as the number of prefixes it handles is sufficient for the needs
of the world's current and future ISPs.  I believe it can't scale to
the number of prefixes which would be required to use existing
BGP-based techniques for providing portability, multihoming and TE for
the millions or hundreds of millions of end-user networks which want
or need this.  There's no way the BGP system can provide global
mobility for billions of physically mobile devices.

I think my beliefs are in accordance with most people who know more
about BGP and Internet routing than I do.  The most obvious place to
start with the recognised problems of the BGP system is to soup it up
or replace it with something else.  Yet since RAWS, as far as I know,
everyone who considered it soon decided BGP should be left alone.
There are real practical difficulties making any changes to it, or
replacing it with something else.  However, I believe the BGP system
as it stands is A Very Good Thing and would be hard to improve upon -
except by fine-tuning things such as trying to reduce the unwanted
emergent behaviour of propagating undesirable routes, by careful
consideration of problems which are currently addressed with the MRAI
timer and other algorithms.

You are suggesting that the problems of the Internet can be solved by
replacing the BGP system with something else, or by drastically
transforming the BGP system into something which works on very
different principles.

I and (I think) many other people on the RRG believe the solution is
to leave BGP as it is.

Some folks, like me, believe in retaining existing host protocols and
addressing arrangements - so we propose architectural additions of the
Core Edge Separation type: such as LISP, Ivip and IRON.  Other people
believe there should be no additions to the routing system such as
this, and that hosts should take full responsibility for solving the
problems: Core Edge Elimination architectures such as ILNP and Name
Based Sockets.

> (be it prefixes, or ASs (if per-~AS aggregation ever happens))

I disagree with this.

A unique prefix does not necessarily mean a unique physical
destination.  If I had an AS end-user network with two upstream ISPs,
and I wanted to split my PA prefix into 16 longer (less address space)
prefixes, I could advertise each one independently via either ISP-A or
ISP-B, for the purposes of inbound traffic engineering and
multihoming.   I could, at any time, set up a branch office in another
country and then advertise one of these longer prefixes there, through
an ISP-P and potentially other ISPs Q, R etc.  I could, if I wanted
to, advertise the same prefix in India on ISP-P, in Germany on ISP-V,
in the USA on ISP-G and here in Australia on ISP-A.  That would be
anycasting this prefix, which is a perfectly valid technique with
genuine uses - and the BGP system copes with this without any special
mechanisms or problems.

So while your statement is very approximately true, I don't think it
is true enough to use as an argument for the validity of your
conceptual framework without great care.

> oscillations, i.e., *infinite* amount of routing information exchanged.

If you remove the first instance of "AS", I would agree with this
statement.

There may, in a general sense, be a notion of "AS topology" in terms
of an AS with a fully meshed network behaving in an atomistic manner -
all its BRs being affected by the sum total of all its BRs'
connections to the BRs of other ASes.  However, I don't think this is
a solid enough concept to base further arguments on without great care.

Routers connect to each other.  Each router is part of an AS.
However, any one BR of an AS doesn't necessarily advertise all the
same prefixes as every other BR of the AS.  The BRs of an AS might not
have any direct links between them.  I could have my routers all over
the world, without any direct links.  So my AS is in no way a unified
object for the purpose of handling packets.

So I don't think that "AS topology" is a sufficiently clear and robust
concept on which to base your work.

> the coordinates of neighboring ASs; no per-destination information

I think you believe that BGP routers can do what people require of
them simply by working at an AS level.  I believe they can't.  As far
as I can see, you haven't given an analysis of what ASes require of
their routers, and how this would be achieved in your proposed system.

People who know more about BGP than I do - many or most of the people
who regularly contribute to the RRG - would be able to give a long and
detailed account of the various things ASes might require of their BRs.

I understand that the above statement is true in your system.  But I
think you have not shown how your system meets the needs of ASes.

> routing is as good and as scalable as theoretically possible.

Sure - but I think your proposed system does not look useful for the
Internet.

> center of the earth cannot potentially simplify celestial dynamics :) 

This last sentence applies to me.  I think your approach is not
relevant to the Internet.  But you are wrong to think that I support
pre-Copernican cosmology!

I think your work a solution in search of a problem.

This is a harsh criticism - but you are making great claims for your
hypothesis.  Your claims are just made on this on this list, which is
probably the best venue for discussing and evaluating them - but in
peer-reviewed journals where most readers are unfamiliar with the
routing scaling problems of the IPv4 and IPv6 Internets.  Not least,
one of your papers is in one of the Nature family of journals - albeit
one of the two of these 32 or so journals which is online only.

I don't need to read your discussion of hyperbolic geometry in any
detail to develop an informed opinion that your work doesn't connect
substantially with the Internets BGP system, or with the the scaling
problems the Internet faces.   I have argued that your central premise
- that BGP routers are concerned with topology - is incorrect.

You may be able to propose an entirely new approach to Interdomain
routing, based on "hyperbolic mapping".  However, you haven't stated
the goals and problems you are tackling, or how such a scheme would be
introduced, or why it would be preferable to other approaches, such
as the various CES and CEE architectures, which accept that the BGP
system is working well and will continue to work well if we can
somehow limit the number of prefixes it handles to approximately the
number needed by ISPs.  This involves making new routing and
addressing arrangements for end-user networks - and the CES approaches
for this are entirely different from the CEE approaches.

Your solution falls into the classification of "Soup up or replace the
BGP system".  While there has been some discussion of such things on
the RRG, I think only Heiner Hummel has consistently proposed such a
solution.  As far as I know (and I have tried to understand what he
proposes) whatever it is which he is proposing has no chance of
meeting the needs of ASes.

  - Robin