Network Construction and Routing in Geographic Overlays

Gregory G. Finn, Joseph D. Touch
USC/Information Sciences Institute
July 10, 2002

Abstract—Geographic networks use physical location as destination addresses, and forward packets topographically. These networks enable geographic and proximity-sensitive applications, unlike the current Internet naming and routing architecture. Geographic routing applied to a native network generally suffers from routing inconsistencies and inefficiencies. A geographic overlay can be incrementally deployed on the current Internet, in ways that ensure routing completeness and consistency. The result is a network with finite, degree 6 routing tables, which are both complete and consistent. The resulting overlay achieves constant-time route calculation, robust unicast and spatialcast forwarding, and supports hierarchical extensions having an expected hop count that is log proportional to network size.

Index Terms—geographic routing, overlay, tunnel, spatialcast

I. Introduction

The Internet uses a hierarchical address and routing scheme that reflects customer/provider relationships. Packets are forwarded toward an address, rather than a geophysical location. Hosts may be physically adjacent, but the distance between them could be many hops, interfering with applications that depend on physical location or proximity.

A geographic network, or GNet, would enable new location-based, proximity-based and spatial application classes. The latter two utilize spatialcast, analogous to multicast, but where membership is implicitly defined by location.

Location-based applications depend upon known host location, e.g., reading only those sensors at particular map positions and tracking. Proximity-based applications depend upon discovery of nearby hosts, e.g., to correlate events, or to find resources such as printers or caches. Spatial applications affect hosts in a delimited area, e.g., communicating with planes in a region of airspace, vehicles on a section of road, or evacuating an affected area during an emergency.

Native networks have an interconnection topography defined by their physical, wired or wireless links. Unless the interconnection topography is very carefully constrained, determining which neighbors are physically near can require global knowledge of network topology. Imposing a native GNet onto a network of irregular interconnection topography implies the global exchange of topographic information. Disabled or insufficient links at a node can create geographic routing inconsistencies, which require difficult, global compensation.

A GNet can also be deployed as an overlay network, on top of an existing (e.g., Internet) network. An overlay network is composed of virtual links added to an underlying network interconnection topography. This ability to tailor interconnection topography allows creation of topographies well suited to geographic network requirements. A geographic overlay network (GONet) can thus ensure consistency and completeness.

A GONet, besides providing support for geographic addressing and routing, also enables networks to be incrementally deployed with routing tables that are tightly bounded and small. The ability to recursively build overlays on overlays allows creation of a routing hierarchy in a GONet to achieve typical hop counts that are log proportional to network size.

The remainder of this paper is organized as follows: Section II discusses the gross requirements of geographic unicast routing topographies and introduces a general methodology for achieving a sufficient and complete geographic network. Section III introduces two algorithms, Voronoi and Greedy Edge, that determine suitable interconnection topographies for a GONet. Section IV analyzes the greedy edge algorithm. Recursive application of greedy edge is then discussed as a means to achieve typical hop counts that are log proportional to network size. Section V defines spatialcast and demonstrates that it is compatible with geographic unicast routing topographies. The subject of bootstrapping is also briefly discussed and some open issues are mentioned. Section VI produces confirming results from simulations and Section VII covers related work.

II. Geographic Networking

A GNet routes packets toward geographic locations. Because multiple hosts can be at the same location, a complete address also requires a unique host identifier. Without loss of generality assume an address consists of <geo, id> portions, where packets are routed toward the geo portion, and the id portion is used as a filter. The geo part, e.g., may be some combination of latitude, longitude and altitude.

II.1. Geographic Network Graphs

In [1], networks were broken into classes defined by the maximum number of hops necessary to forward any packet closer to its geographic destination. If all routers could forward any packet closer to its destination in n or fewer hops, the network was said to be n-hop consistent. The following mechanism generates the edges that transform an inconsistent graph into one that is 1-hop consistent.

For the following discussion, assume all hosts are sites on a Euclidean plane; extensions to volumes and compensations for curved surfaces (of the earth) are omitted for simplicity. Also assume that sites are unique; as above, the id combined with a filter provides sufficient further resolution.

Consider two sites S_i, S_j and a line segment R between them depicted in Figure 1. The perpendicular bisection of edge R, shown as B, defines two half planes, the left (unshaded) route-from half plane, and the right (shaded) route-to half plane. S_i can move any packet, whose destination lies within the route-to half plane containing S_j, closer to its destination (make progress) by forwarding that packet to S_j. The edge R thus represents a forwarding table entry at S_i.

Figure 1 Forward Progress

Consider sets of neighbor sites {S} around a router at site S_i, and for each set, consider its effectiveness as a list of forwarding entries at S_i. For some of these sets, the intersection of route-from half planes outlines a convex polygonal region that contains only S_i. In that case, S_i can make progress to any location by forwarding to some member of {S}. The graph of edges between S_i and {S} is 1-hop consistent with respect to S_i. This approach generalizes to three dimensions, and assumes only that the space remains Euclidean.

Applying this procedure to all sites in a network will transform a network graph into a 1-hop consistent GNet. The procedure assumes that any two sites can be connected by an edge. In a native GNet, this requires full, or at least heavy, local connectivity. Incomplete connectivity can cause forwarding dead-ends. If there exists a site that has no set {S} producing an appropriate convex routing polygon, it results in a local dead-end. There is no global way to avoid paths involving such dead ends.

II.2. Virtual Geographic Networking

The links of a geographic network can be created from tunnels in an underlying, existing base network, resulting in a geographic overlay network. The sites in a GONet rely on the base network for link connectivity and can avoid generating inconsistent routing tables. Paths in the base network may take a large number of hops to reach a geographically nearby neighbor, however. Although efficiency is compromised, it produces the desired geographic network topography, which allows unicast geographic routing and spatialcasting.

Methods to discover physically close neighbors in a network and the edges needed to produce a consistent geographic network were studied in [1]. The new edges corresponded to source routes from one to n hops long in a base network. The flooding methodology developed there did not scale to large networks. The use of tunnels greatly simplifies that procedure, because source routes need not be discovered nor maintained. Only edge endpoints need be known. Maintaining the route between endpoints becomes the responsibility of the underlying network.

Hosts in a geographic overlay require distinct addresses in both base and overlay networks, with edges to neighbors in the overlay implemented as tunnels in the base. Overlays were developed to deploy new protocols, most notably the M-Bone for multicast IPv4, and have been extended as a general mechanism for network virtualization known as the X-Bone [21]. An X-Bone overlay includes both end hosts and routers in the overlay, and includes support for overlays at all points in the virtual network. A GONet is an X-Bone style overlay where the virtual network is a geographic network.

Because tunnels encapsulate overlay payloads in base packets, the base is isolated from overlay packet formats. Overlay packets are exposed only at tunnel endpoints, where the appropriate overlay stack is implemented. Thus, the overlay may support a differing form of host address and protocol stack from that in the base. In particular, it may implement a geographic address. Not all base components need participate in the overlay; those that do not, are expected to at least forward encapsulated overlay packets.

III. Computing Edge Sets

There are various methods for computing specific edge sets needed to create a 1-hop consistent network graph. In a GNet, these are the equivalent of the routing protocol. Various sets of nearby neighbors are discovered and considered. Any set whose route-from half planes outline a convex polygon around the router site that contains no other sites is sufficient as a table for that site. Note that computing an edge set may itself use the GNet, as nearby neighbor location requires a proximity discovery mechanism.

There are two algorithms for computing edge sets. The first is a derived from Computational Geometry, and the second was developed to address problems with the first.

III.1. Voronoi Edge Generation

The description above of the solution space for 1-hop consistent graphs is based on the intersection of half-planes around each site. This is strikingly similar to the partition method that defines Voronoi graphs [2][3]. The Voronoi region around a site contains all the points that are closer to that site than to any other site. For each point, take the perpendicular to the bisector as in Figure 1; the intersection of these perpendiculars forms a polygon (Figure 2). Voronoi regions necessarily partition a plane into convex polygons.

Figure 2 Voronoi Polygon for S_i

By placing an edge between any two sites whose Voronoi polygons share an edge, the space can be triangulated, producing a Delaunay graph (Figure 3). If each site is assigned a geographic address, it can be seen that a Delaunay graph is a 1-hop consistent network. The corresponding routing table for each site would have an entry for each edge of its Voronoi polygon.

Figure 3 Delaunay Graph for S_i

There are two difficulties in using Voronoi polygons to define the interconnection graph of a GNet. First, Voronoi polygons are not straightforward to calculate in two dimensions and are even more difficult to calculate in three dimensions. Second, the upper bound on the number of edges of a Voronoi polygon is N‑1, where N is the number of sites, an example of which is a spiral (Figure 4). Thus, if the Delaunay triangulation is used to define site routing tables, some tables may be large.

Figure 4 Delaunay Graph for Spiral Pattern

Routing tables are more efficient when bounded. It is thus preferable to find an algorithm for generating edge sets that produces a similar convex polygon but that has a small upper bound on the number of its vertices, regardless of site location patterns. It would also be desirable if that algorithm were both simple and easily extended to three dimensions.

III.2. Greedy Edge Generating Algorithm

Consider a population of sites on a plane and assign them geographic addresses. Consider now a site H and the non-empty set {S} of its neighbor sites. From {S} choose the site closest to H, call it N₁. Place N₁ into neighbor set {N} and place an edge from H to N₁. The bisection of that edge defines half planes. For any destination that lies in the half plane containing N₁, H can make progress by forwarding to N₁. Call that the covered region about H defined by N₁. The half plane that contains H and the line of bisection constitutes an uncovered region, U₁, for which H cannot make progress by forwarding to N₁. Discard from {S} all sites that lie in the covered region. Now iterate. The algorithm halts when {S} is empty, which implies that, with respect to {S}, there are no sites within H's uncovered region but H itself.

Figure 5 Geometry Imposed by Edge

The intersection of U_i forms a convex routing polygon around H. Each edge defined by {N} determines an entry in H’s routing table. If the routing polygon is closed, those entries constitute a complete routing table for H, since no site other than H resides in that polygon and all other sites from the population reside within a region covered by some N_i. If the routing polygon is not closed, either that polygon contains no sites other than H or another set {S} is needed. Unlike Voronoi polygons, the convex polygons generated by this algorithm can overlap.

IV. Characterizing Greedy edge Algorithm

Several practical issues remain to be discussed regarding the greedy edge generating algorithm and the networks that result from its use. What is the upper bound on the number of edges that the polygons generated by the algorithm have and so therefore the number of entries in routing tables? How many hops will the typical path have? How might a host H find its geographic neighbors and their addresses?

IV.1. Routing Table Bounds

Consider a population of hosts {S} as sites on a plane. Identify one of those sites as H. Determine a closest site in {S} to H at distance . Call that site . The bisection of the line segment defines two half-planes. Any site within the half-plane that contains is closer to than to H.

See Figure 5. The bisector of the segment also defines a chord in the circle centered at H of radius . The segments and are of length /2, right angles are formed by and , thus, triangles and are congruent. Because is of length , so is and is equilateral. By symmetry, so is.

Thus, the angle C₁HC₃ sweeps is 120 degrees. Since no hosts in {S} other than H lie within the circle defined by H and r₁, N₁ covers the interior of the 120 degree region defined by C₁HC₃ of H's routing space. Note that C₁ and C₃ are limit points of open line segments not covered. Thus, each site provides up to 120 degrees of coverage.

Discard from {S} all sites that lie in the N₁ half-plane and presume {S} not empty. Choose the next closest site in {S} to H at distance r₂. Call that site N₂. The distance r₂