11.26.06

Why geographic addressing has no place in WANs (and maybe not LANs)

Posted in Essays, naming/addressing at 7:05 pm by BrandonHeller

The routers on today’s Internet forward packets based on the layout of the IP address, in a method called Longest Prefix Matching (LPM). Unfortunately, LPM becomes harder as line speeds get faster. Direct lookups are one method for LPM and complete in O(1) time, but would require an exorbitant 17GB of memory. Trie representation enables a tradeoff between memory and lookup speed, but is held back by the glacial pace of memory latency improvements, making trie lookup a challenge for rates greater than 10 Gbps. Ternary Content Addressable Memories (TCAMs) enable O(1) associative lookups, and thus line rate speeds, but are expensive and power-hungry. What if there was a method of addressing that could enable line-rate lookups with minimal memory, power, and cost?

One method seems to fit these requirements: geographic addressing.

In geographic addressing, the destination of a packet is typically represented as a latitude and longitude pair. If the destination location matches the router or end system’s location, the packet’s journey is complete. If not, all neighbors are checked, and the one that brings the packet closest to the destination is used. The most important effect of geographic addressing is scalability. Router state becomes independent of the number of nodes in network, and only depends on the density of the network. The scalability and low resource requirements of geographic addressing make it a good fit for sensor networks.

Unfortunately, as will soon become clear, fundamental deployment issues prevent geographic addressing from having any place in both Wide Area Networks (WANs) and Local Area Networks (LANs).

Geographic Addressing in Sensor Networks

Sensor networks are characterized by limited memory and limited battery power, and typically communicate over radio links. To better understand geographic routing, we’ll look at Greedy Perimeter State Routing (GPSR) [2]. GPSR forwards to the neighbor closest to the destination, but also senses when a packet has been forwarded to a local geographic minima. In that case, it uses face routing, where the packet routes around a polygon. The algorithm’s input graph must be planar; in other words, the graph must be two-dimensional, with only straight, uncrossed edges. Deriving the planar subgraph of an original node graph in a distributed way can be tough, due to assumptions that reality is happy to violate. One example is the unit graph assumption, which states that each node is connected to all neighbors within a unit range, such as a radio transmission range, and disconnected from all neighbors outside that unit range [1]. Older techniques like Relative Neighbor Graphs and Gabriel Graphs produce a planar subgraph, but only if the unit assumption is valid. Obstacles such as buildings easily violate this assumption.

Recent Developments in Geographic Addressing

The last two years have seen significant developments in geographic routing. Recent work [1] has proposed a distributed algorithm, Cross-Link Detection Protocol (CLDP), for extracting the planar subgraph and enabling connectivity between all network nodes in realistic topologies. However, the resulting subgraph is often suboptimal, with an increased path stretch of up to 100 (!) for some nodes.

A newer routing algorithm, Greedy Distributed Spanning Tree Routing (GDSTR), follows greedy routing in the common case, but switches to a backup routing mode that uses hull trees to ensure correct routing when a packet becomes stuck in a local minima [5]. GDSTR is notable in that it does not require a planar subgraph; precomputation of routing structures ensures quality routing, and it can work in n dimensions. Along this line of removing the planarization requirement is Lazy Cross-Link Removal (LCLR), described in a paper less than a month old [6]. LCLR performs a low-cost approximate planarization, then routes assuming a planar graph. Only when routing fails does it removes crossing edges, resulting in significantly less control overhead than GDSTR. Other work has improved on geographic routing efficiency [4], used modified physically embedded coordinates [5], or proposed using geographic routing with virtual coordinates [7].

Note that the simplest form of geographic addressing has many cases where it simply doesn’t work; nodes can be permanently disconnected. More complicated versions that route on a planar subgraph carry increased complexity, greater control traffic, and often monster stretch, due to inefficient face routing. Dual-phase and lazy algorithms improve the situation, but have only been looked at for homogeneous wireless topologies. Importantly, none of these algorithms bound the worst-case path stretch. Centralized planar subgraph production might be a solution, but adds its own issues of reliability and control.

Geographic Addressing in the Inter-Domain WAN

At first glance, one might see the WAN as a domain in which geographic addressing could make some sense. While much of the complexity of wireless GR algorithms goes away when fixed WAN nodes are used, many of the benefits disappear as well, and newer, more insurmountable issues arise. In addition, virtually all research has looked only looked at the wireless domain.

Zeroth, the backbone of our wired IP networks can be viewed as a mesh, which sounds like a candidate for geographic routing. However, the backbone is really multiple overlapping meshes, owned by companies with different interests. ISP traffic enters and exits at border routers, which would confuse the heck out of a geographic routing algorithm. Direct geographic routes assumes one network owner, so you’d have to rip up the current ISP payment structure and traffic boundaries. This requirement alone is enough to prevent any feasible inter-domain WAN deployment.

First, all but one geographic routing algorithm requires a planar subgraph of the underlying graph topology to route traffic properly. What exactly is the planar subgraph of all the active fiber in the US? The distributed algorithms are nondeterministic, which may result in the path taken by a packet depending on the time at which a router comes online.

Second, who has the authority to decide which links to deactivate to enable a planar subgraph? How do you decide who shuts off the links in a way that is fair to all ISPs? Is it the US government or an international body? How do you tell an ISP that they must deactivate a major $40M cross-country fiber link? If cooperation is a huge financial risk, then what motivation do they have to buy new routers with geographic support?

Third, what is the business motivation for ISPs who must implement the idea? It doesn’t help them sell new services; older services may break. It doesn’t increase their backbone capacity; if anything, deactivated redundant links reduce their capacity. It doesn’t improve the service quality; suboptimal routing may lead to greater path stretch. It doesn’t give them more control over their network; it removes control and places it in a central authority. It doesn’t improve their ability to engineer traffic; in fact, it disables the current mechanisms for traffic engineering. It doesn’t save them money; carrier routers are not yet a commoditized market, so pricing is dominated by demand rather than cost. You might argue that router vendors have a business motivation to reduce the complexity of their routers, but support for IPv4/v6 demands fast LPM support, which kills the primary reason for choosing geographic addressing in the first place. Without a compelling business model, geographic routing is dead in the water.

Fourth, there is no recent well-defined standard for geographic addressing and routing. Addressing could be simple latitude and longitude pairs, but addressing is useless without routing. RFC2009 came out on the subject in 1996, but has not been updated since then [3]. The most likely proposals to become a standard, CLDP, GDSTR, or LCLR, are all less than two years old, with no journal papers. Reserve at least 4 years for an IEEE 802 standard, add 2 years for router implementations, and only then would the potential for deployment exist. By then, other routing protocols may have been developed with more desirable properties.

Fifth, there has been no wide-scale test implementation of wired geographic routing. This is a prerequisite for any new addressing/routing proposal. The ISPs would laugh at you for even suggesting a change whose effects are not yet understood at the global level.

To summarize: with geographic addressing in the WAN, nobody would make any money, the political hurdles are imposing, ISPs lose control over their traffic, a number of other outstanding issues would need to be solved, and IPv4/v6 inertia nullifies the raison d’être of reduced router state.

Geographic Addressing in the Intra-Domain WAN

When we look within a domain, rather than between domains, many of the deal-killers for geographic addressing go away. For example, the fairness, trust, and deployment issues disappear. Within a domain, the business considerations for such a change, namely implementation costs, new services to deliver, and traffic quality, dominate. Let’s look at those.

The realistic cost to implement a new routing protocol is probably not so bad when we consider access routers, which get replaced frequently. New technologies like faster DSL, 10 Mbps cable service, and fiber-to-the-home certainly require new routers anyway. The location requirement could be handled by giving each router installer a GPS device.

Still, note that the changeover must be handled all at once. A packet arriving at an access router can be destined for any other access router; thus, the entire network must support geographic addressing before it is useful. Also, no ISP wants to be the first to try out the new protocol, and the first ISP to deploy must contend with higher first-adopter prices and an unknown financial risk if serious issues are only discovered after deployment.

Geographic addressing seems to enable no useful new services for fixed routers, or ways to improve traffic quality. Without knowing the topology of the transit portion of an ISP’s network, it is not clear if geographic routing provides any path benefit. If the network is a fully connected mesh, its performance will be satisfactory. In the more likely case that a few of the highest-speed routers form a mesh and the majority of routers are on tree branches, geographic routing should perform poorly, especially where the first hop takes the packet in the wrong direction. Again, many links would have to be deactivated to satisfy a planar graph assumption. Traffic “engineering” would then refer to carefully choosing which links get deactivated. Any router idea that nullifies existing fiber investment is a hard sell.

Another problem arises: for incoming packets, how is the location of the destination known? DNS could be modified to add coordinates to the entry for each server, but how would this information be delivered to the ingress routers? More importantly, if only one ISP adds this information, why should all of them deal with a change to DNS?

A more deployable solution would be a middlebox to modify every ingress packet to include the destination location, like an ISP-wide distributed NAT. However, this mapping from destination IP to router location adds router state, and must be known for every router on the network. Now we’ve turned a deployability problem into a scalability problem for larger networks, and it’s not clear that our traffic is even equally manageable or equally fast compared with the current setup. You might argue that the scalability problem is no worse than before, but there’s no benefit, so why bother?

To summarize: geographic addressing is more deployable within a domain than between them, but seems to present zero business advantage for an implementing ISP, and the disconnect between geography and network topology may significantly worsen paths.

Geographic Addressing in the LAN

Alright, you say, maybe there’s still hope for geographic addressing in the LAN. Sorry; even if you replace every wired Ethernet switch and Ethernet port on every computer, there’s no real benefit. LANs are trees, plain and simple. Yet again, the physical topology does not match the network topology, and we don’t even know the physical locations of most devices! I don’t have a GPS or accurate plans of the building I’m in; how do I know my location? Even worse, consider multi-story office buildings, and mobile devices without location knowledge. The majority of geographic algorithms are 2D on planar graphs, so cross them off for the LAN. End users should never have to concern themselves with such details as their location, nor should every device or Ethernet port require location information. Your network admin might know these details, but he or she would be dismayed to learn that they could have no effect on network traffic. Also consider the privacy issues that geographic addressing raises: do you want your exact position known to others, even within the LAN?

Conclusion

I have tried to present geographic addressing and routing in the most positive light, by considering the most up-to-date research and trying to imagine ways around its issues. However, I have to conclude that in any real network (i.e. where the money is, and where traffic quality matters) geographic addressing and routing make little business sense. I haven’t even attacked other major issues, such as overlapping locations, how to trust node location, and geographic DoS mechanisms. These would add pages to this essay, all arguing against the feasibility of geographic techniques.

In cost-sensitive, non-bandwidth-critical networks with one controlling identity, such as a mesh topology where every node is a router, geographic routing is a sensible choice. Examples include sensor networks and peer-to-peer wireless mesh networks in developing countries. New developments provide hope of greater geographic routing applicability, but these techniques are too young and untested to be seriously considered for a large, expensive network. High speeds, traffic engineering, and federation are unaddressed or poorly served by geographic addressing and routing. Not only are these required components of WANs and most LANs missing, but the inevitable cost advantages of Ethernet and IPv4/v6 kill any chance of large-scale geographic network deployment.

References

[1] Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S. Geographic routing made practical. In Proc. USENIX Symposium on Network Systems Design and Implementation (May 2005), USENIX.

[2] Karp, B., and Kung, H. GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States

[3] RFC 2009. GPS-Based Addressing and Routing November 1996.

[4] Kuhn, F. et al. Geometric ad-hoc routing: of theory and practice. In Proc. ACM PODC, Boston, M, USA, July 2003.

[5] Leong, B. New Techniques in Geographic Routing. PhD Thesis, May 2006.

[6] Govindan, Y. K., Karp, B., and Shenker, S. 2006. Lazy cross-link removal for geographic routing. In Proceedings of the 4th international Conference on Embedded Networked Sensor Systems (November 2006). SenSys ‘06

[7] Gummadi, R., et al. Reduced State Routing in the Internet. Hot Nets III (2004).

Permalink