11.26.06
Geographic addressing in WANs to simplify routing and enable new services
The question I want to address is the following: which, if any, would be the advantages of having geographic addressing in WANs? In order to analyze this problem, I will first summarize how routing is performed on WANs, what geographic routing is and in which context it has been deeply studied. The objective is to find out whether some of the requirements which motivated the idea of geographic routing apply also to WANs.
Background
WAN routing: basic concepts
WANs consist of many Autonomous Systems (AS), that is, many subnets each one under the control of a distinct administrative authority. Routing in WAN encompasses therefore two different aspects: intra-AS and inter-AS routing. The protocols for intra-AS routing can be classified into two categories: distance vector and link state routing protocols. Inter-AS routing is nowadays performed through the Border Getaway Protocol (BGP), sometimes used also within the same AS (internal-BGP, or iBGP).
Distance vector protocols associate a cost to every link in the network and use the Bellman-Ford algorithm in order to find the minimum cost path between any pair of nodes (routers). Each router periodically sends to all its neighbors its current cost-routing table (initially, such table will contain a finite cost path only to the neighbor nodes). Additionally, each router uses the information received by the neighbors in order to recompute its routing information. Distance vector based protocols (e.g. RIP) suffer from lack of scalability (each node must periodically forward its complete routing table) and convergence problems.
Link-state protocols (e.g.: IS-IS, OSPF) are based on a graph representation of the network at each router. Such graph is built by having each router flood the network with the information about which router it is connected to. Each node will then compute the shortest path to any other node locally through the Dijkstra’s algorithm. Link-state protocols require less information to be propagated than distance vector ones and react more quickly to connectivity changes.
BGP stores the reachability state between AS in a table, where each entry indicates the prefix (or IP network) to be routed and the next hop information. Classless inter-domain routing and route aggregation are exploited to decrease the routing table size. The content of the routing table is built after the information exchanged between neighboring BGPs.
Notice that none of the above protocols makes use of the concept of geographic coordinates. Instead, the distance between two routers is in general measured in terms of number of hops between them.
Geographic routing in Wireless networks
Geographic routing, that is, routing on the base of geographic information, has been proposed in the context of wireless networks (in particular, in the case of ad hoc networking). Two main observations are at the basis of this idea. First, ad hoc environments exhibit a high degree of dynamicity, in that the number of components and their location continuously vary over time. Not only does this fact complicate the algorithms required in order to constantly exchange and actualize routing information, but it also implies a not negligible bandwidth requirement just for the propagating routing state. Secondly, because of mobility itself, the identifiers of networking devices located in close areas are not necessarily similar. Therefore, route aggregation basing on the identifiers’ prefixes as in BGP is not possible.
The basic ideas of geographic routing in the context of ad hoc networking are the following. Each node knows its geographic coordinates and the ones of its neighbors. The packets contain the information about the destination’s coordinates. Routing is performed in a greedy fashion [7] by forwarding the packet to the neighbor node which has the lowest distance from the destination. This way, the only information which needs be propagated in order to perform routing is the geographic coordinates, which are sent just to the neighboring nodes. Some problematic situations may arise when none of the neighbors is less distant from the destination than the current one. Mechanisms based on face routing are proposed in order to get out of these local minima conditions. However, these mechanisms are based on theoretical assumptions about the network graph which are hardly satisfied in practice ([8]), and more work is needed for this purpose.
Discussion
Given the above background information, I come back to the original question: does geographic addressing make sense in the context of wired WANs?
It is clear that the basic requirement which motivates geographic routing in ad hoc networks does not apply to WANs as well. In fact, even if wired scenarios are not completely static (due to link outages, introduction of new routers and of new ISPs, and so on), the degree of dynamicity present in wired WANs is not comparable to the one characterizing ad hoc networking environments. Moreover, in a WAN, the bandwidth available to connect nodes is in general greater and available in a more stable way. Therefore, optimizing the dissemination of routing state is not a big issue in this context. However, there are other reasons which may motivate geographic addressing in WANs. In what follows, I’ll classify them into three groups: i) traffic control, ii) technical and iii) application-specific goals.
i) Traffic control
As pointed out above, routing in WAN is nowadays completely oblivious of geographic information. Therefore, traffic sent to St. Louis towards California may, for instance, be routed through New York. This may imply a propagation overhead which could be avoided by exploiting geographic information.
Quantifying the potential improvement in bandwidth usage and delay which could be achieved in case of geographic routing is difficult and surely impossible without performing simulations. One could expect that geographic routing would not be optimal if used alone, but that augmenting the actual routing with geographic information could be the right thing to do. On an intra-AS level, that could signify introducing a geographic distance factor in the weights used in the Bellman-Ford algorithm in case of distance vector protocols and in the Dijkstra’s algorithm in case of link-state protocols. In case of inter-AS routing, it would be possible to consider the geographic coordinates of the border routers and of the centers of mass of the sub-networks represented by prefixes when building the routing table.
ii) Technical goals
One could wonder whether the use of geographic addressing could be motivated by technical purposes, as the one of diminishing the routing state or the amount of routing information which needs to be disseminated. The authors of [10], for instance, argue that geographic addressing would allow a router to store information only related to its immediate and at most two-hop distant neighbors, thus limiting the amount of state needed on each router. However, I cannot see a strong point here. For what concerns inter-domain routing, even if the size of the BGP tables tends to increase, a great deal of techniques to efficiently store and query such tables has been already proposed. Moreover, as mentioned above, dynamicity in WAN contexts is limited and so I don’t see the bandwidth needed in order to propagate routing information as being a big concern. For what concerns intra-domain routing, the routing state should be anyway limited, and thus not constitute a concern at all.
iii) Application-specific goals
More interestingly, geographic addressing could be exploited in order to support and facilitate specific services and applications, for which the relationship between the geographic location of the sender and the one of the recipient is of significance.
Let’s assume, for instance, that a potential customer wants to browse the online catalog of a multinational company. If routing takes into account geographic information, the customer will be directed to the servers in his own country. The company may differently distribute and present the content on servers located in different countries depending on the specific cultural tastes. So, not only would the customer have a benefit in terms of access time, but he would be qualitatively more satisfied by the service in that he would be displayed information which is more relevant to him without the need of extra browsing.
Similar considerations apply also to other applications. In the case of video streaming, for instance, one could imagine having several servers in several countries. Servers in Italy would privilege the Italian language selection, sports like soccer and Italian news, whereas in the US the English language would be offered by default, football would be given a better treatment among the sports and US news would be the only ones available.
Finally, the sender’s geographic location may also affect the result of search operations. If, for instance, a user living in St. Louis searched Google for “cheap restaurants”, not only would he be directed to a US server close to St. Louis, but the results would display St. Louis restaurants in the first hits.
Notice that geographic routing is not fundamental to implement the services above. Nonetheless, it would facilitate their implementation and deployment.
Conclusions
To sum up geographic addressing, which has been widely studied in the context of ad hoc networking, could exhibit advantages also in the very different WANs scenario. In particular, augmenting routing with geographic information could avoid taking unnecessary “long” routes in the Internet and thus allow better distributing the traffic. Additionally, geographic routing could better support the needs of services and applications for which geographic information is relevant. However, a pure geographic routing could probably not be beneficial in a WAN, and combining geographic information with the mechanisms used nowadays sounds more promising. Additionally, geographic addressing makes in my opinion more sense for inter-domain rather than for intra-domain routing.
References
[1] D. E. Comer, “INTERNETworking with TCP/IP”, Prentice Hall International, Jan 2000
[2] Wikipedia: Routing, http://en.wikipedia.org/wiki/Routing
[3] Wikipedia: Open Shortest Path First, http://en.wikipedia.org/wiki/Open_Shortest_Path_First
[4] Wikipedia: IS-IS: http://en.wikipedia.org/wiki/IS-IS
[5] Wikipedia: BGP: http://en.wikipedia.org/wiki/BGP
[6] Border Getaway Protocol: http://www.bgp4.as/
[7] Karp, B. and Kung, H.T., “Greedy Perimeter Stateless Routing for Wireless Networks”, in Proc. of MobiCom 2000, pp. 243-254
[8] Y-J. Kim, R. Govindan, B. Karp, and S. Shenker, “Geographic Routing made practical”, Proc. of NSDI 2005 
[9] A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica, “Geographic routing without location information.” In ACM MobiCom Conference, pages 96 — 108, Sept. 2003
[10] A. Gummadi, R. Govindan, N. Kothari, B. Karp, Y. –J. Kim and S. Shenker, “Reduced State Routing in the Internet”, in Proc. of ACM Hotnets III, 2004
traviskeshav said,
December 1, 2006 at 4:34 pm
I’d agree that geographic routing might be beneficial for some services and some routing applications. However, I also wonder for geographical routing would handle such issues as load-balancing; there are several large metropolitan cities in the United States such as New York, and with geographic routing, all traffic towards the rest of the country might attempt to follow one direct path and series of links. While this certainly might reduce propagation delay in theory, wouldn’t it also cause excessive congestion on some overused links? I don’t think geographic routing is entirely unfeasible, but it’d certainly cause some extra implementation issues.
Also, I’m not sure geographic is all that essential for some of the application-specific goals listed; as is, most commercial and ‘important’ sites host country and language-specific websites that are accessible enough as is through either suffix specification (.fr, .jp, etc.) or from links from the main .com portal page.
mbecchi said,
December 8, 2006 at 5:49 pm
I’ll try to address the issue you raised.
1) I am not proposing to use *solely* geographic routing, but rather to take advantage also of geographic information in order to take routing decisions. One could envision to have situations where multiple paths are possible, one optimal from a geographic point of view and some suboptimal, and to use information concerning traffic activity (either based on traffic monitoring or congestion information) in order to dynamically select the path to be used.
2) I agree that geographic routing is not “essential” for those applications (and I also stated this in the essay). Nonetheless, it could be an alternative. If geographic routing was implemented, then one could think about hiding the server location from the URL. Introducing geographic routing just in order to support this kind of service would not be worth.