Wang Yonggong (王永功)

(*Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, P.R.China)(**The Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory,the 54th Research Institute of China Electronics Technology Group Corporation, Beijing 100701, P.R.China)

?

A self-organized locator obtaining method driven by local minima①

Wang Yonggong (王永功)②

(*Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, P.R.China)(**The Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory,the 54th Research Institute of China Electronics Technology Group Corporation, Beijing 100701, P.R.China)

The scalability of routing architectures for large networks is one of the biggest challenges that the Internet faces today. Greedy routing, in which each node is assigned a locator used as a distance metric, recently received increased attention from researchers and is considered as a potential solution for scalable routing. In this paper, LMD — a local minimum driven method is proposed to compute the topology-based locator. To eliminate the negative effect of the “quasi” greedy property—transfer routes longer than the shortest routes, a two-stage routing strategy is introduced, which combines the greedy routing with source routing. The greedy routing path discovered and compressed in the first stage is then used by the following source-routing stage. Through extensive evaluations, based on synthetic topologies as well as on a snapshot of the real Internet AS (autonomous system) topology, it is shown that LMD guarantees 100% delivery rate on large networks with low stretch.

greedy routing， locator, self-organized, local minimum, topology

0 Introduction

The information-centric networking (ICN) paradigm is one of the new trends in future Internet research[1], where a “name” is the primary identifier, instead of the IP address. However, the well-known Rekhter’s Law: “Addressing can follow topology or topology can follow addressing. Choose one.”[2]does not hold in ICN, exposing their routing system to even greater scalability issues.

Distributing “names” rather than IP addresses will make the situation much worse than in today’s Internet. For example, Ref.[3] reported that a name-based routing table carrying only the top-level domains as prefixes would have to hold 2×108routes, compared with the only 4×104in today’s Internet.

Arguably, topology-based identifiers, also called locators[4]are needed, as an intermediate layer on top of which more scalable routing systems can be built in ICN. In recent work[5-8], greedy routing has been identified as a potential solution to answer the scalability needs. In greedy routing, the “name” is first translated into a locator by a mapping service comparable to the current DNS service. Then, the packets are greedily routed according to the locator.

Greedy routing in large networks has already been studied in the past[9]. However, it was not started to be considered as an attractive routing solution until Kleinberg’s seminal work[10]was conducted. In Ref.[10], each node is assigned a synthetic coordinate, called locator (in our study denoting its virtual location), and it can route greedily by selecting a neighbor that is the closest to the destination.

Unlike traditional routing protocols that require routers to maintain the next hops for every destination, greedy routing only relies on local information: the locators of its neighbors. This localized routing strategy has two advantages: 1) the size of the routing tables is significantly reduced, from the number of nodes in network to the number of neighbors; 2) the router only needs to process update messages originated from its neighbors, which is a very desirable feature for large networks. However, greedy routing suffers from the “l(fā)ocal minimum problem”, which sometimes prevents the routing from reaching the destination.

In this paper, a greedy routing protocol is presented to compute locators, called LMD (local minimum driven). Unlike previous work depending on the global knowledge of the topology, this method is self-organized and configuration-free. However, LMD still suffers from local minima. To overcome this issue, we enhance the greedy routing and not only resolve the local minimum issue, but also compress the length of the greedy forwarding path.

The rest of this paper is organized as follows. The LMD (Local Minimum Driven) method and the enhanced greedy routing algorithm are detailed in Section 1. Section 2 evaluates LMD. In Section 3, we discuss related work. Section 4 concludes the paper.

1 LMD: a local minimum driven locator calculation

1.1 Algorithm design philosophy

Greedy routing is typically made of two components: (1) the greedy embedding (computing the locator) and (2) the greedy forwarding algorithm (using the locator to forward packets). Each component’s success depends on the other’s completeness and complexity. In other words, if the greedy embedding process is well designed, the greedy forwarding process should be trivial. Otherwise, forwarding must compensate for the shortcomings of the embedding, to guarantee packet delivery.

In LMD, a simple greedy embedding algorithm is chosen in combination with a complex forwarding algorithm. Despite the complexity of a self-organized and configuration-free greedy embedding, it is believed that it is important to make progress in “autonomic networking”[11,12]. To compensate for the lack of guarantees in packet delivery, it relies on a mechanism to compress the routing path. The two corresponding components of LMD, the local minimum driven method (LMD embedding) and the corresponding enhanced greedy routing (LMD forwarding), are detailed in the following two subsections.

1.2 Local minimum driven method

Local minima are typically due to the short-comings of locators. The rigorous greedy embedding is defined as a mapping f:V(G)→(X, ρ) such that ?s≠t, s∈V(G), t∈V(G), it holds that s has a neighbor w with ρ(f(w), f(t))<ρ(f(s), f(t)). Similarly, the local minimum is defined as node s of which neighbors are farther to t than themselves. For example, in Fig.1(a), packets to node t might be stuck at node s, which is called a local minimum node. While in Fig.1(b), a better greedy embedding is constructed, where no local minimum exists. Calculating the embedding locators for a small graph is straightforward. In large networks, on the other hand, it can be computationally challenging.

Inspired by the difference between two sets of locators in Fig.1, it is found that slightly moving the node stuck in the local minimum, s, away from the destination node t, will make the embedding. It is noted that, though both s and t are “correctly” embedded, while the neighbors of s may lead to the local minimum at s. It prefers, in LMD, to move the local minimum node s to satisfy the self-organized constraint in our design principle.

Fig.1 Local minima in locators

Furthermore, the locators of neighboring nodes are required to be close to each other. This is quite reasonable in light of the definition of the hidden metric space[13]: The smaller the distance between two nodes in the hidden metric space, the more likely they are connected. Given that we only allow using local information, a spring is created between any pair of neighbors. The pull force between connected nodes will help to prevent the locator space from inflating infinitely. The attraction forces between neighbors can be described as follows: F=1/log(d), where d is the metric distance between neighbors.

The complete LMD embedding algorithm is described in Fig.2, which is executed once a packet is stuck at a local minimum node v. The step factor c is a constant in the LMD algorithm, but it could also be a random perturbation. If c is too large, the correcting process may overshoot with infinite oscillations. A too small value will make the time to leave the local optimum longer. In the experiments, a value of 0 is used, 1 for c.

Fig.2 Local minimum driven algorithm

At the very beginning, each node will choose a random vector as its initial locator. Fig.3 illustrates how LMD constructs the locators gradually in a 10×10 grid network. In this example, all packets are sent randomly between sources and destinations. The locators are expressed in a 2-dimensional Euclidean metric space. The number of packets from the beginning of simulation and the corresponding success rate of greedy routing are shown in the brackets below the sub-graphs. Even though the success rate of greedy routing in the final graph is very high, i.e., 99%, there are still about 1% of the packets stuck at the local minima. To deal with the local minima due to the LMD embedding, we present an enhanced greedy routing (LMD forwarding) in the following subsection.

Fig.3 LMD in a 10×10 grid network

1.3 Enhanced greedy routing

In a standard greedy forwarding algorithm, two conditions are used to select the neighbor to which packets are forwarded: 1) it is closest to the destination among all the neighbors and, 2) it is closer to the destination than the current node. Among the possible neighbors, none satisfies condition 2, the forwarding process is stuck in a local minimum and fails.

As mentioned in the previous subsection, LMD embedding cannot generate the perfect greedy locators, i.e., distances might not be monotonously decreasing on the path of a packet. Therefore, the second condition in LMD should be dropped: packets are always forwarded to the closest neighbor towards the destination. However, this condition relaxation in turn can create forwarding loops, which in standard greedy forwarding is avoided by design. To resolve the loop, all the visited nodes are recorded in the packet and will be avoided by subsequent forwarding. If all the neighbors of a given node have been visited, a random neighbor is chosen as the next hop to break ties.

Although a 100% successful delivery rate can be ultimately guaranteed through random walks, it will be at the expense of a much longer path than the actual shortest path[14]. In order to reduce the length of the greedy path, a distributed path compressing method is proposed and implemented in LMD. Rather than forwarding all the packets greedily as suggested in previous work[6,15-17], a two-stage routing scheme is designed. During the first stage, routing discovery, the enhanced greedy forwarding is performed. In the second stage, data packets are routed on the “compressed” route obtained from the routing discovery stage. In LMD, the path learned in the first stage can be compressed thanking the following two rules:

1) If a node occurred in the path more than once, the edges between the occurrences are removed.

2) If both a node and its neighbor occurr in a path, the edges connecting the node and its neighbor in the path should be replaced by the direct edge.

The asymmetric routing means that source-destination and destination-source paths are not always equal during a topology discovery. We further compress the path by exploiting the asymmetry in the paths. Fig.4 illustrates the asymmetry in routing discovery and the corresponding path compression. The forward path (7 hops) and the backward path (7 hops) are connected by edge AB. The final path after compression has only 5 hops.

Fig.4 Both-way path compression

2 Evaluation

2.1 Experiment settings

As discussed in the previous sections, LMD does not make assumptions about the network topology structure. In this paper, we focus on scale-free networks, because they have been identified throughout multiple natural and engineering areas, including the Internet[18]. The scale-free networks in our study are generated by the Barabási-Albert (BA) model[19], in which each node is added to the network with m connections at each step. The probability of attaching to an existing node of degree k is proportional to k. This model yields a power-law degree distribution with exponent γ between 2 and 3. The default parameters of the network topology used in our experiments is N=1,000, m=2, k=4, γ=2.5, unless otherwise specified.

Since the locator is corrected gradually by the packets stuck at local minima, the traffic distribution, or called traffic model, is important in the LMD evaluation. Thus, traffic following Zipf-law and uniformly distributed traffic is used to evaluate the performance of LMD. Unless otherwise specified, the source nodes and the target nodes of the packets are randomly and uniformly chosen in our evaluation.

2.2 LMD on synthetic scale-free networks

As the quality of greedy embedding which can be evaluated by the success rate is the basis of greedy routing, first, the embedding performance of LMD is compared with three existing decentralized embedding methods in Fig.5, where Refs[16,20] are two recent work constructing greedy embedding by self-organized methods, which are labeled as AVE and FPC separately. Vivaldi[21]is a well-known work in network coordinates which can be seen as an isometric embedding. Considering the fact that a perfect isometric embedding is also a guaranteed greedy embedding (but not the converse), it is chosen as a candidate greedy embedding algorithm, where the packet delay between nodes in Ref.[22] is replaced by the hops of the shortest path. It can be seen that LMD outperforms Refs[16,20] up to 20% with different dimensions. Though all the pair-wise distance are known in Ref.[21], our method still gets better success rate.

(There are 1000 nodes in this scale-free network, γ=2.5)

The dimensionality of the metric space is a critical factor for LMD, as well as for most similar methods[16,20,22]. Fig.6 illustrates how the dimension of the metric space affects the performance of LMD. The raw stretch is the ratio of the greedy forwarding path length in the routing discovery stage to the theoretical shortest path length. The compressed stretch is the ratio of the final data path length to the shortest path length. Remarkably, the success rate is the ratio of packets successfully received by the target nodes only using classic greedy forwarding, not our enhanced greedy routing, to the total number of packets, which reflects the quality of locators.

(There are 1000 nodes in this scale-free network,γ=2.5)

Higher dimensions are expected to give better routing performance. This comes at the cost of a larger locator, as well as more overhead in locator computation and packet forwarding. As expected, we observe on Fig.6 that the path stretch gets close to 1 when the dimensionality reaches log(N). This is consistent with previous work[23]proving log(N) to be the lower bound of a no-stretch greedy embedding, where N is the number of nodes in network.

2.3 LMD on Internet AS topology

Scalable routing in large network has been widely studied. LMD is chosen to be compared with two other routing schemes, PIE[17]and TZ[25]. PIE is a recently proposed method to extract multi-level trees to embed a topology. We also compare LMD to PIE with a single global tree, because its routing stretch is theoretically equal to many other single tree based methods, e.g. in Refs[15,16]. TZ[25]is an optimal version of the classic compact routing[27]for scale-free networks.

A recent snapshot of the AS level topology[28]of the Internet is relied on for the comparison. This topology was collected in November 2011 and contains 39973 ASes and 251630 edges. The main parameters of each routing method are the following:

TZ: The core size is 200, similar to the square of the AS number, as required by the routing protocol.

PIE1: Only one global tree rooted at the highest degree node.

PIE12: The embedding contains 12 levels of tree hierarchy, which approximates to log(N), N being the number of ASes. log(N) is the preferred level in PIE.

LMD12: LMD with 12 dimensions locator, whose space overhead is similar to PIE1.

LMD144: LMD with 144 dimensions locator, whose space overhead is similar to PIE12.

Fig.7 compares the CDF of the path stretch of the different methods. As expected, the stretch of PIE1 and LMD12 is worse due to their low overhead and dimensionality. Despite that TZ is the only method that guarantees a maximum stretch of 3, CDF of the path stretch of TZ is worse than PIE12 and LMD144. Indeed, the average stretch of both PIE12 and LMD 144 are slightly above 1, at 1.03. While PIE and LMD have similar performance in path stretch, they are very different: PIE focuses on guaranteeing the success rate, while LMD ensures that no global coordination is necessary, i.e., it is a self-organized protocol.

Fig.7 The comparison of LMD with other scalable routing methods

3 Related work

Greedy routing, also called geometric routing or geographic routing, has been studied for over a decade, especially in ad-hoc wireless networks[29]. The two most popular approaches in this area, i.e., planar graph and UDG (Unit Disk Graph), either does not work with arbitrary networks, or are costly or unrealistic. Recent work[13,15-17,26,30,31]questions the design rules for greedy routing in arbitrary graphs. Most of the early work can be grouped into three categories: routing on planar or “quasi” planar graphs, routing on spanning trees, and routing on general graphs.

3.1 Greedy routing on planar or “quasi” planar graph

Almost all the greedy routing algorithms in wireless networks belong to this category because of a widely used hypothesis: a link between any two nodes is considered if the two nodes are located in each other’s transmission range (or radius), which makes planar graphs an appropriate approximation for wireless networks. This assumption makes sense in wireless environments, but unfortunately does not match networks such as the Internet.

GSpring[32]adjusts the node’s coordinates by simulating a system of springs and repulsive forces. Ref.[32] defined the concept of the ownership region of each node (analogous to a Voronoi diagram), and used the conflict region to adjust coordinates iteratively. Another well-known routing algorithm in this category is NoGeo in Ref.[33], which also creates synthetic coordinates through an iterative relaxation algorithm. BVR[34]does not require a planar network. Even though it performs well in wireless environments, it experiences poor performance for low degree networks, such as Internet.

3.2 Greedy routing on spanning tree

Greedy routing on spanning trees can be considered as a special case of planar graphs. We review this category separately because of the large body of recent literature[6,17,26,31,35,36], most of which fix at the aspects of the seminal[15]. Computing the spanning tree of the whole network is a common step for this class of algorithms. In Ref.[15], a strictly greedy embedding algorithm is proposed such that any connected finite graph can be embedded in a two-dimension hyperbolic metric space. Ref.[26] removed the need for global knowledge in Ref.[15] (the tree’s maximum degree) and presented an online greedy embedding. Furthermore, Ref.[26] proposed a Gravity-Pressure routing method to deal with the greedy routing failure caused by network dynamics. The size of the coordinates was improved by Ref.[35], from O(n) bits to O(log n) bits. Ref.[6] presented a greedy routing with bounded stretch by constructing a constant-stretch tree, while in Ref.[36] authors proposed a way of approximately projecting the greedy embedding into an O(log n)-dimension metric space where each coordinate only needs O(log n) bits. Recently, Ref.[17] extracted several trees with different locality levels and combined them together to perform a greedy routing.

Although the spanning tree protocol, a precondition for all the algorithms mentioned above, has been widely used in real networks for many years[37], it is not trivial to make it work in large networks for two reasons: 1) Choosing the root node is challenging; 2) The robustness of the routing protocol might be questioned as the graph is cut into trees.

3.3 Greedy routing on general graphs

The origin of greedy navigability in scale-free network is explored in Ref.[13]. A hidden metric space is defined for the first time to explain the connectivity of a given network: The smaller the distance between two nodes in the hidden metric space, the more likely they are connected. Ref.[22] claimed to propose a self-organized greedy routing method, but their scheme only guarantees the delivery to a sink node, and no complete point-to-point routing is evaluated. Ref.[31] approached the problem from the opposite direction: the hyperbolic space is fixed and a graph is constructed in it.

The LMD algorithm belongs to the 3rd category. As opposed to the previous algorithms in this category that completely depends on the hidden metric space, this paper presents a two-stage routing scheme that combines greedy routing with source routing, which yields a high success rate and reasonably low stretch values on general networks.

4 Conclusion

In this work, LMD — a self-organized and configuration-free greedy routing scheme is presented. The key idea in our design is using the local minimum information in greedy routing to correct the locators in the network. Additionally, LMD combines a quasi-greedy but robust embedding method with an enhanced greedy routing. Experiments on an Internet topology show that LMD can achieve a high success rate on large networks with low stretch.

Reference

[ 1] Ahlgren B, Dannewitz C, Imbrenda C, et al. A survey of information-centric networking. Communications Magazine, IEEE, 2012, 50(7): 26-36

[ 2] Meyer D, Zhang L, Fall K. Report from the IAB Workshop on Routing and Addressing. RFC 4984, 2007

[ 3] Narayanan A, Oran D. NDN and IP Routing: Can It Scale? http://trac.tools.ietf.org/:Cisco, 2011

[ 4] Meyer D. The locator identifier separation protocol (LISP). Internet Protocol Journal, 2008, 11(1): 23-36

[ 5] Rodrigues P, Martins J L. Greedy Routing in the Internet: Is it a Solution? In: Proceedings of Conference on Computer Networks, Braga, Portugal, 2010

[ 6] Flury R, Pemmaraju S, Wattenhofer R. Greedy routing with bounded stretch. In: Proceedings of IEEE Conference on Computer Communications, Rio, Brazil, 2009. 1737-1745

[ 7] Boguná M, Krioukov D. Navigating ultrasmall worlds in ultrashort time. Physical review letters, 2009, 102(5): 058701

[ 8] Greedy Forwarding on the NDN Testbed. http://www.caida. org/research/routing/greedy forwarding ndn/:CAIDA, 2013

[ 9] Finn G. Routing and addressing problems in large metropolitan-scale internetworks. USC Technology Report ISI/RR-87-180, 1987

[10] Boguná M, Krioukov D. Navigating ultrasmall worlds in ultrashort time. Physical review letters, 2009, 102(5): 058701

[11] Kephart J O, Chess D M. The vision of autonomic computing. Computer, 2003, 36(1): 41-50

[12] Autonomic Network Architecture, http://www.ana-project. org: ANA, 2011

[13] Boguna M, Krioukov D, Claffy K C. Navigability of complex networks. Nature Physics, 2009, 5(1): 74-80

[14] Tian H, Shen H, Matsuzawa T. Random walk routing for wireless sensor networks. In: Proceedings of the Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies, Dalian, China, 2005. 196-200

[15] Kleinberg R. Geographic routing using hyperbolic space. In: Proceedings of the Conference on Computer Communications, Alaska, USA, 2007. 1902-1909

[16] Zhuo Z, Cai S M, Fu Z Q, et al. Self-organized emergence of navigability on small-world networks. New Journal of Physics, 2011, 13(5): 053030

[17] Herzen J, Westphal C, Thiran P. Scalable routing easy as PIE: A practical isometric embedding protocol. In: Proceedings of IEEE International Conference on Network Protocols (ICNP), 2011. 49-58

[18] Barabási A L. Scale-free networks: a decade and beyond. Science, 2009, 325(5939): 412-413

[19] Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509-512

[20] Wang Y, Xie G, Kaafar M. FPC: A self-organized greedy routing in scale-free networks. In: Proceedings of the 17th IEEE Symposium on Computers and Communications, Cappadocia, Turkey, 2012. 102-107

[21] Dabek F, Cox R, Kaashoek F, et al. Vivaldi: A decentralized network coordinate system. In: Proceedings of the Conference of the Special Interest Group on Data Communication, Portland, USA, 2004. 15-26

[22] Watteyne T, Augé-Blum I, Dohler M, et al. Centroid virtual coordinates-A novel near-shortest path routing paradigm. Computer Networks, 2009, 53(10): 1697-1711

[23] Maymounkov P. Greedy embeddings, trees and Euclidian vs. Lobachevsky geometry: [Technical Report]. http://pdos. csail.mit.edu/petar/pubs.html, 2006

[24] Chang H, Roughan M, Uhlig S, et al. The many facets of Internet topology and traffic. Networks and Heterogeneous Media, 2006, 1(4): 569-600

[25] Chen W, Sommer C, Teng S, et al. Compact routing in power-law graphs. In: Proceedings of the 23rd International Conference on Distributed Computing, Montreal, Canada, 2009. 379-391

[26] Cvetkovski A, Crovella M. Hyperbolic embedding and routing for dynamic graphs. In: Proceedings of the IEEE Conference on Computer Communications, Rio, Brazil, 2009. 1647-1655

[27] Thorup M, Zwick U. Compact routing schemes. In: Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures. Crete Island, 2001. 1-10

[28] Internet Topology Collection. http://irl.cs.ucla.edu/ topology/: IRL 2013

[29] Chen D, Varshney P K. A survey of void handling techniques for geographic routing in wireless networks. Communications Surveys & Tutorials, 2007, 9(1): 50-67

[30] Flury R, Wattenhofer R. Randomized 3D Geographic Routing. In: Proceedings of the 27th Conference on Computer Communications, Phoenix, USA, 2008. Doi: 10.1109 /INFOCOM.2008.135

[31] Papadopoulos F, Krioukov D, Vahdat A. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In: Proceedings of the 29th Conference on Computer Communications, San Diego, USA, 2010. 1-9

[32] Leong B, Liskov B, Morris R. Greedy virtual coordinates for geographic routing. In: Proceedings of IEEE International Conference on Network Protocols, Beijing, China, 2007. 71-80

[33] Rao A, Ratnasamy S, Papadimitriou C, et al. Geographic routing without location information. In: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. San Diego, USA, 2003. 96-108

[34] Fonseca R, Ratnasamy S, Zhao J, et al. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In: Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation, San Francisco, USA, 2005. 329-342

[35] Eppstein D, Goodrich M T. Succinct greedy graph drawing in the hyperbolic plane In: Proceedings of Graph Drawing. Springer Berlin Heidelberg, 2009. 14-25

[36] Westphal C, Pei G H. Scalable routing via greedy embedding. In: Proceedings of INFOCOM, Rio de Janeiro, Brazil, 2009. 2826-2830

[37] ANSI/IEEE Standard 802.1D, LAN/MAN Standards Committee of the IEEE Computer Society, 1990

Wang Yonggong, born in 1983. He is currently working at the Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory, 54th Research Institute of China Electronics Technology Group Corporation. He received his a Ph.D. degree from the Institute of Computing Technology, Chinese Academy of Sciences. He received his M.S. and B.S. degrees from Xidian University in 2008 and 2005 separately. His research interests include scalable routing protocol, and caching in information-centric networking.

10.3772/j.issn.1006-6748.2015.02.006

①Supported by the National High Technology Research and Development Program of China (No. 2013AA013501), the National Program on Key Basic Research Project (No. 2012CB315801), the National Natural Science Foundation of China (No. 61133015) and the Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory, CETC54.

②To whom correspondence should be addressed. E-mail: wangyonggong@ict.ac.cn Received on Feb. 27， 2014***, Xie Gaogang*