[RRG] recent progress in routing research

["Dmitri Krioukov" <dima@caida.org>]

Below is my review of few recent results in routing research. I
select the papers to discuss based mostly on my current interests. I
split the review into the following two parts: papers from
theoretical computer science and from networking.

I. Theoretical computer science

For a list of most important papers on compact routing, see Section
5 of http://arxiv.org/abs/cs.NI/0508021 Of course, there are much
more results in this area. One can find them following the reference
links. On the other hand, for a somewhat *shorter* version of the
compact routing reference list, see 'Compact routing background
reading' section at http://rr-fs.caida.org/

Note that the compact routing framework is to construct algorithms
achieving optimal balance between routing table size and stretch for
a set of graphs, effectively assuming the 'global knowledge' of the
graph topology. There is an alternative but closely related problem
formulation and an associated set of recent results. The idea is to
explain Milgram's letter-passing experiments in 1966 in which a
number people (source nodes) were asked to pass letters (data
packets) to addressees (destination nodes) whom the source nodes did
not personally know---only destinations' geographical locations
(places of living), occupations, and other metadata, were written on
packets. The next hops were the current nodes' friends maximizing,
in the current node's opinion, probability of letter's moving closer
to the destination. The average path length was found to be around
6, which later gave rise to "Six degrees of separation". Milgram's
experiments were the first demonstration that the social networks
are small-world. The latter is now widely known fact, but there is
another more interesting aspect to the story.

Indeed, what those experiments effectively showed was not only that
paths were short, but that nodes could efficiently find them.
'Efficiently' mean here that nodes did not have any global knowledge
of the network topology: their routing tables were small and
contained information only about nodes' neighbors---that is, their
friends. At the same time, having succinct routing tables at the
nodes, packets followed paths of small stretch.

The first popular attempt to model this effect was due to Kleinberg
in 2000 http://www.cs.cornell.edu/home/kleinber/swn.ps His model
assumes that the real network topology consists of two parts: 1)
d-dimensional grid, and 2) long-range links: one link per node
leading to a destination selected according to a specific
distribution. The rationale behind the model is that the grid
represents a relatively regular network part induced by people's
place of living, occupation, etc., while long-range links represent
random connections, e.g., people meeting on a plane. Note that all
nodes in the model have fixed small routing tables of the size equal
to the number of directly attached links (2d+1). Routing is greedy:
a current node selects the next hop which is closest to the
destination, but distances are calculated in the grid only, i.e.,
disregarding the long-range links. In other words, a given node
knows only about its own long-range link and no other long-range
links. Kleinberg shows that if the long-range link distribution is
harmonic, then the expected number of hops to reach destination is
polylogarithmic, otherwise it's polynomial.

Clearly, the key component of Kleinberg's model is the assumption
about the d-dimensional grid, which is the simplest example of a
network embedable in the d-dimensional Euclidian space, and compact
routing on Euclidean metrics is easy
http://www.cs.huji.ac.il/~ittaia/papers/AM-PODC04.pdf since there is
a sense of direction: you are "here", the destination is "there", so
just "go there". Keeping your position information takes a little
memory and following a specified direction guarantees low stretch.
Such familiar, to the networking community, concepts as geographical
routing or P2P/overlay routing in carefully designed metric spaces
are classic examples of attempts trying to utilize this routing
easiness.

However, Kleinberg's assumption about the underlying grid, along
with the requirement that the long-range link distribution is
harmonic, is obviously too strong. No one in fact believes that the
actual acquaintance network topology looks like that. That's why I
think that the recent paper by Fraigniaud
http://www.lri.fr/~pierre/POSTSCRIPTS/tech_report_LRI_1397.ps makes
a huge progress in the area by significantly relaxing these
assumptions. Fraigniaud shows that the underlying graph can simply
be either of low treewidth
http://citeseer.ist.psu.edu/bodlaender93tourist.html or, almost
equivalently, high clustering, and we know that all complex networks
observed in reality are strongly clustered.

II. Networking

1. The RSR paper
http://enl.usc.edu/papers/cache/gummadi_hotnets04.pdf suggests to
reduce routing state in the Internet by a variant of geographical
routing (see above!). Few other highlights:

a) Interestingly, the authors are concerned not with the control
plane (RIBs) whose scalability is a major concern today, but with
the data plane (FIBs), where forwarding lookups can scale up to
millions of entries thanks to recent developments in IP lookup
algorithm research. I guess this interest can be explained by
authors' work in wireless where FIB sizes also matter.

b) The authors propose to use routing on AS numbers, i.e., AS
numbers replace IP prefixes in their role of interdomain routing
addresses (see the discussion in Section 2 of
http://arxiv.org/abs/cs.NI/0508021 ).

c) The state reduction achievable by MPLS is similar RSR: in MPLS,
the state is reduced only at the core routers that can keep
forwarding information (labels) only for the LSPs passing through a
given router, while the edge routers must still have to keep the
full state.

2. The HLP paper
http://www.acm.org/sigs/sigcomm/sigcomm2005/paper-SubCae.pdf is
infiltrated with interesting ideas. The core of the paper is to
reduce BGP churn by utilizing the hierarchical structure of the AS
business relationships. Few other highlights:

a) The authors propose to use routing on AS numbers to reduce
routing state. The paper does not try to reduce the routing table
size below the total number of ASs.

b) While the authors propose to use hierarchical routing, they use
it to reduce churn and to better isolate instabilities, but not to
reduce the routing table size (below the total number of ASs).
Therefore, the standard criticism of hierarchical routing, e.g., in
Section 4 of http://arxiv.org/abs/cs.NI/0508021 , does not apply to
HLP.

c) The standard criticism from http://arxiv.org/abs/cs.NI/0508021
that can be applied to HLP is that it discusses only a one-time
(constant-factor) improvements, and not the scaling behavior of the
proposal. However, this lack of scaling guarantees is a too common
problem within networking.

d) One of the more specific sources of concerns is that HLP's
performance degrades, possibly significantly, if the numbers of
non-standard (exceptional) AS relationships is not small. Related to
exceptional relationships is the number of cycles in
customer-provider hierarchy: this number is said to be small in the
paper. However, the accuracy of calculations of this number depends
on a choice of the AS relationship inference techniques, and they
have seen significant progress recently. This progress specifically
shows that this number is not negligible. More generally, there are
no reasons to believe that the relative number of the exceptional
relationships will decrease.

e) The authors propose to use hybrid LS/DV routing and they might
have benefited from explicit building on the several previous
results in this area, e.g.,
http://portal.acm.org/citation.cfm?id=190327
http://portal.acm.org/citation.cfm?id=881243 etc.

3. Finally, I'd like to point out that importance of the research
direction established in the breakthrough metarouting paper
http://www.acm.org/sigs/sigcomm/sigcomm2005/paper-GriSob.pdf can
hardly be overestimated.
--
dima.
http://www.caida.org/~dima/




--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg