Cartesian routing

Cartesian routing is a novel packet routing methodology in which a packet's route is determined by the position of the router relative to that of the destination. Cartesian routing differs from existing provider-based unicast routing in that routing tables are unnecessary since communications are to pologically dependent, thereby potentially reducing router and network over heads. For example, routing decisions, which can take O(log(n)) to O(n) tim e using routing tables is reduced to O(1) in Cartesian routing. This paper describes Cartesian routing for unicast communications within a local or me tropolitan environment (e.g., limited areas, including buildings, suburbs, and small towns that exhibit an anthropogenic ordering) using two-dimension al address structures, such as latitude and longitude. A Cartesian network is constructed from two types of router: collector (for horizontal communic ations) and arterial (for both 'horizontal' and 'vertical' communications). Cartesian routing requires minimal state: typically, routers need only kno w their location and the reachability of arterial routers on their collecto r. The paper also shows how the proposed 128-bit IPv6 address structure is an ideal candidate for Cartesian addresses. (C) 2000 Elsevier Science B.V. All rights reserved.