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.

1. 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' means 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) a 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, of high clustering, and we know that all complex networks observed in reality are strongly clustered.
   
   

2. 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:
      1. 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.
      2. 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 ).
      3. 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 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:
      1. 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.
      2. 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.
      3. 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.
      4. More specifically, HLP essentially proposes a form of topology clustering with questionable optimality. Indeed, HLP's clusters are customer-provider cones---sets of ASs reachable by customer-provider links only. The average size of these clusters is likely to scale linearly since its lower bound is Ω(n/t), where n is the total number of ASs and t is the number of 'top clique' ('Tier-1') ISPs and also the number of clusters. This lower bound is obtained by splitting all ASs evenly between the top t providers. The size of the top clique t is definitely not of the order of n^1/2 today, and it does not appear to grow polynomially: it either stays constant or grows polylogarithmically at best. Thus, even if one decides to utilize the proposed clustering for routing state scaling, he would gain only a constant-factor one-time improvement since the routing table size upper bound stays linear. From the compact routing standpoint, this inefficiency signifies suboptimal clustering: the core of compact algorithms is all about construction of efficient topology clustering with both the number of clusters and their sizes being upper bounded by O(n^1/2), for stretch-3 compact routing.
      5. Another source of specific 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.
      6. 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.