We present PIE, a scalable routing scheme that achieves 100 packet delivery and low path stretch. It is easy to implement in a distributed fashion and works well when costs are associated to links. Scalability is achieved by using virtual coordinates in a space of concise dimensionality, which enables greedy routing based only on local knowledge. PIE is a general routing scheme, meaning that it works on any graph. We focus however on the Internet, where routing scalability is an urgent concern. We show analytically and by using simulation that the scheme scales extremely well on Internet-like graphs. In addition, its geometric nature allows it to react efficiently to topological changes or failures by finding new paths in the network at no cost, yielding better delivery ratios than standard algorithms. The proposed routing scheme needs an amount of memory polylogarithmic in the size of the network and requires only local communication between the nodes. Although each node constructs its coordinates and routes packets locally, the path stretch remains extremely low, even lower than for centralized or less scalable state-of-the-art algorithms: PIE always finds short paths and often enough finds the shortest paths.
Solutions such as have been proposed to guarantee the success of geographic routing when local minima are present, see for instance @cite_21 . These methods apply greedy routing by default and use a recovery mechanism when the packet is trapped in a local minimum. These deterministic recovery mechanisms only guarantee success of routing when the dimensionality of the underlying space is no more than two @cite_42 . In addition, backtracking out of local minima significantly inflates paths lengths and induce high congestion @cite_32 .
@cite_21 @cite_42 @cite_32
2085463780 2110348561
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we consider two aspects: We propose a new geometric routing algorithm which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal. On the other hand we are able to drop the formerly necessary assumption that the distance between network nodes may not fall below a constant value, an assumption that cannot be maintained for practical networks. Abandoning this assumption we identify from a theoretical point of view two fundamentamentally different classes of cost metrics for routing in ad-hoc networks. Geographic forwarding has been widely studied as a routing strategy for large wireless networks, mainly due to the low complexity of the routing algorithm, scalability of the routing information with network size and fast convergence times of routes. On a planar network with no holes, Gupta and Kumar (2000) have shown that a uniform traffic demand of ominus(1 radicn log n) is achievable. However, in a network with routing holes (regions on the plane which do not have active nodes), geographic routing schemes such as GPSR or GOAFR could cause the throughput capacity to significantly drop due to concentration of traffic on the face of the holes. Similarly, geographic schemes could fail to support non-uniform traffic patterns due to spatial congestion (traffic concentration) caused by greedy "straight-line" routing. In this paper, we first propose a randomized geographic routing scheme that can achieve a throughput capacity of ominus(1 radicn) (within a poly-logarithmic factor) even in networks with routing holes. Thus, we show that our scheme is throughput optimal (up to a poly-logarithmic factor) while preserving the inherent advantages of geographic routing. We also show that the routing delay incurred by our scheme is within a poly-logarithmic factor of the optimal throughput-delay trade-off curve. Next, we construct a geographic forwarding based routing scheme that can support wide variations in the traffic requirements (as much as ominus(1) rates for some nodes, while supporting ominus(1 radicn) for others). We finally show that the above two schemes can be combined to support non-uniform traffic demands in networks with holes.