Short version: I still think this Hyperbolic mapping work:
http://www.nature.com/ncomms/journal/v1/n6/full/ncomms1063.html
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:
http://arxiv.org/abs/1006.5169
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:
http://www.nature.com/ncomms/journal/v1/n6/full/ncomms1063.html
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):
http://www.ietf.org/mail-archive/web/rrg/current/msg06219.html
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:
> 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.
I think this is still far overstating the information which a BGP
router obtains from its neighbors.
> 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.
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:
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 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
> close to a directed acyclic graph (DAG) rooted at this this AS.
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.
> 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.
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
> 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 :)
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:
http://arxiv.org/abs/1006.5169
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.
> 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))
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.
> 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.
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.
> 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.)
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.
> 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.
Sure - but I think your proposed system does not look useful for the
Internet.
> 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 :)
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
_______________________________________________
rrg mailing list
[email protected]
http://www.irtf.org/mailman/listinfo/rrg
