11.26.06
Geographic addressing in WANs to simplify routing and enable new services
Network addressing and routing protocols have received enormous attention since the inception of the Internet. Any addressing scheme used in the Internet must serve three fundamental objectives: identity (so that end nodes can be identifiable), location (so that packets destined for the end nodes can be routed), and reachability (which links should be taken to route messages from one node to the other, note that in the current Internet, by default, every connected node is reachable).
At one side of the addressing spectrum, the most comprehensive addressing approach will be to allocate distinct identities for each of the above three functional requirements. Clearly, such addressing will require mapping functions to map identities to locations and reachability. It appears that it is difficult to keep these mapping functions up-to-date, when the hosts are highly mobile; whenever the location of a host will change, its mapping function will have to be updated, and moreover, every node in the network has to be notified of the changes in this mapping. On the other side of the addressing spectrum, the simplest addressing scheme is to allocate such addresses to the hosts, which will not only uniquely identify them, but will also allow the network to determine their location in the network.
The current Internet uses such addressing: the IP addresses are used to represent both the location as well as the identity of the hosts. There are two primary reasons behind such a design choice: i) when the Internet was developed, most of the participating nodes were static in location, therefore their location and identity were more or less the same, and ii) The hierarchical structured form of the IP addresses and the location information embedded within them, enables highly scalable routing, and millions of addresses can be handled efficiently (the routing tables at each router remains small and easy to maintain). While efficient, and scalable, this architectural choice now has become source of many limitations of the current Internet.
Two of the most important concerns are related to security and mobility. Since the location information is only weakly coupled to the identity, and since the identities themselves are not allocated in a secured fashion, it has become exceedingly easy to misuse the Internet infrastructure. One can easily harvest many unused IP addresses, and use them to launch Denial of Service attacks; in such situations, it is difficult to track down the misbehaving entities. Another security issue with the current Internet addressing stems from the fact that one can easily do source address spoofing and launch new types of attacks. Since the location information is not used to perform routing, it becomes difficult to combat against such attacks.
The second important concern is inability of the current Internet addressing to properly incorporate mobility. With the rapid proliferation of mobile devices which are connected to the Internet, and with the introduction of multihoming in which a node may have multiple identities, the structured addressing of the current Internet appears to be problematic. As early as 1993, many have suggested that in any network architecture, host identity should be cleanly separated from the host’s location. Consequently, a large variety of such addressing schemes have been proposed, and most of these involve some form of resolution, where the host name is translated into the location at some point, which is used to deliver the data. One of the most widely advocated addressing in this category is called geographic addressing, where the hosts will have a unique static identity, which will be linked to a dynamic geographic location; geographic locations will be indicated by the two dimensional vector , and will be used to route the messages.
With such addressing, the Internet routing protocols will have to be overhauled so that the routers are geographically-aware, and are able to deliver packets based upon the geographic information of the destination. Such geographically-aware routers will use the polygonal geographic destination information (which is part of the geographic message header) directly for the routing. In order to enable incremental deployment of geographic routing in the Internet, it can be implemented in the application layer (multicast routing was also implemented initially in this way). Thus, a virtual network will be overlayed over the current IP infrastructure, which will use geographic addresses for routing. These virtual networks will contain geographically-aware routers, which will perform geographic routing (these routers would use IP tunnels to route packets through those areas which do not yet support geographic routing). At this point in discussion, we postpone further implementation details of the geographic routing, and focus on its advantages.
First and foremost, geographic routing capability will allow mobility features to be integrated into the network, much more cleanly and efficiently. Today, mobile hosts (e.g. laptops, cell phones) form a sizeable fraction of the total number of hosts connected to the Internet. When these hosts move from one location to the other, they either have to be assigned a new IP address, or they require some mechanism to update their location and reachability mappings, which is used by the network to route packets to them. With no clear separation of the location and identity in the current Internet, it often becomes problematic for the mobile hosts to stay connected.
When the network will route packets based upon both the geographic location information (which will keep changing) and hosts identity (which will be unique), then the mobility will become a natural feature of the network. However, in order for the hosts to stay connected, they will need some mechanism to quickly update their location information, whenever they will move from one location to the other. This is not difficult; today every host can cost effectively integrate Global Positioning Systems (GPS) cards, which will not only allow them to quickly get the precise location information, but will also provide additional information like direction and speed of the movement. Availability of such information can enable a wide range of services which can be deployed in both the application level and the network level software. The network will be aware of the precise location of every user, therefore several new services can be introduced, in addition to the enhanced mobility, some of which are listed below:
1. “Who is near” service will allow one to find all users who are in a specific geographic area. Such a service can be easily implemented over a geographically-aware network, and can be extremely useful for various mapping applications, and search and rescue operations. This service will likely find several use in the future, e.g. it can aid a globally distributed team to better collaborate in their effort.
2. On-line advertising has become one of the most important revenue generating network service. With the introduction of geographic addressing capabilities, the effectiveness of on-line advertising can be enhanced dramatically and it can truly become the mainstream advertising medium. For example, it will allow the advertisers to present selective advertisements to only those people who are for instance geographically close to a store. Think about the situations when the advertisements of a MacDonald’s burger will only appear at the screen of those people who are crossing a MacDonald’s outlet. Such selective and focused advertising is clearly much more effective than today’s carpet bombing techniques.
3. Geographic addressing will enable one with the capability to send messages to specific subareas defined by latitude and longitude. For example, it will allow one to multicast emergency messages to everyone who is currently in an airport or in a railway station. On a highway, messages can be selectively delivered to only those people who are, for example, driving a motorcycle. Another application may be to send selective messages to only those car drivers who are likely to get stuck in a traffic jam, down to road.
4. With geographic addressing, another type of services can be provided by those senders who themselves are mobile. For instance, mobile servers can now multicast messages to only those receivers which are, say within 10 miles from the server. Alternatively, a collection of servers which are all mobile can collaborate to efficiently distribute messages to users around selected regions.
While these are the obvious revenue generating services, which can be realized with the help of geographic addressing schemes, there is another class of services (not directly revenue generating) which can be of great use to the service providers. With geographic addressing, it will become extremely easy for anyone to visualize or analyze their customers based upon their location. Thus, the service providers can fine tune their services based upon the customer’s habits. This can also help them in determining the patterns of usage of their network infrastructure and how and where the future investments should be made. For instance, such addressing may allow content providers like Youtube to decide the locations where they need additional video servers.
With the previous discussion, it is clear, that the geographic addressing will help spur new Internet services, which are otherwise unimaginable with the current Internet addressing. However, in order to make a strong case for the geographic addressing, we need to perform a feasibility study and show that such addressing scheme will indeed scale to a network consisting of billions of hosts and millions of intermediate nodes.
A first order look into such addressing and the associated routing suggests that geographic routing will be difficult to implement. In fact, most of the known Internet architectural proposals, which attempt to decouple the location from identity, appear to lack scalability. The recently proposed Routing on Flat Labels (ROFL), for instance, goes to an extreme and gets rid of the location altogether, in order to enhance mobility. Thus, a ROFL based network needs to route packets directly looking at the destination names, without any associated location information. While it is a first stab at a radically different clean slate design approach, which attempts to address many problems with the current Internet addressing, at this point, it appears difficult to make a case in favor of the ROFL. It is not clear, how the benefits of ROFL will overpower its obvious limitations in terms of scalability. The number of hosts connected to the Internet is likely to grow continuously in the future in which case ROFL based network may further suffer from the performance and scalability issues.
Alternative methods to implement geographic addressing will have to provide some function to map the identities, which will be static in nature to locations, which will be dynamic. An obvious approach to provide such mapping will be a mechanism similar to the DNS. Whenever hosts will change their location, they will register their new location with the DNS server, which will accordingly update the mapping for the host’s identity. While it appears to be a feasible approach, it is not clear how scalable such a solution will be. When millions of hosts will move quickly from one point to another, it will be daunting to update the location mapping of each of them.
Another complication with the geographic addressing may arise with the routing mechanism and the ability to monitor and control traffic at various links (traffic engineering). With such addressing, routing will be performed over the location identifier, thus it may appear that it will simplify the routing process, as no complex routing protocols will be needed to keep the forwarding tables at the routers up-to-date. However, in reality, if the granularity of the location identifier will be too low (within meters of accuracy), then there may be millions of distinct location identifiers and regions, and routing may become infeasible. An effective and scalable approach will be based upon hierarchical polygonal routing. In such routing, the earth will be divided into hierarchy of polygons, and the routing will be first performed over the larger polygons and then over relatively smaller polygons, as the packet gets closer to the destination. In such routing processes, it will be difficult to apply any traffic engineering policy, and it may also become difficult to guarantee good delay properties.
With these concerns, it clearly appears difficult to implement geographic addressing in a network, which is as large as the Internet. However, geographic addressing undoubtedly has several benefits. First and foremost, with the precise locations readily available, and with the control to selectively send messages only to select geographic regions, it will become feasible to introduce a large variety of new revenue generating services, which are location aware. It will also become easy to implement multicasting and select broadcasting capabilities and such addressing will also help combat against the mounting security concerns. However, only time will tell if such a geographic addressing makes it to the reality.
References:
[1] M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, S. Shenker, and I. Stoica, “ROFL: Routing on Flat Labels”, in Proceedings of the ACM SIGCOMM 2006, Pisa, Italy, September 2006.
[2] Julio C. Navas and Tomasz Imielinski, “Geocastgeographic addressing and routing,” in Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking. 1997, pp. 66–76, ACM Press.
[3] Geoff Huston , IP Addressing Schemes - A Comparison of Geographic and Provider-based IP Address Schemes, http://ispcolumn.isoc.org/2004-12/addressing.html
[4] IETF RFC 2009 / RFC2009, GPS-Based Addressing and Routing.