IBM EX. 1019
`
`IBM EX. 1019
`
`1 of 11
`
`
`
`

`

`U'C' DAV'S
`April I999
`Table of C onten APR “ 5 '9‘”
`. REC. LIBRARY
`
`Open-Source Software Development
`32 Introduction Tim O’Reilly, Gum Editor
`38 The Linux Edge Linus Torvalds
`
`40 The Origin of the Camel Lot in the Breakdown of
`
`the Bilingual Unix Larry Wall
`
`42 Shared Leadership in the Apache Project
`
`Roy T. Fielding
`44 Free Software Needs Profit John Ousterhout
`
`Evolvable Hardware
`
`46 Introduction Xin Yao, @estEditor
`
`50 Quo Vadis Evolvable Hardware? Moshe Sipper,
`Daniel Mange, and Eduardo Sanchez
`
`57 Field-Programmable Gate Arrays Pierre Marchal
`
`60 Evolvable Hardware Chips for Industrial Applications
`
`Tetsuya Higuchi and Nobuki Kajihara
`64 Hardware Evolution System AdAM Tomofiimi Hikage, Hitoshi Hemmi, and Katsunori Shimohara
`67 Experiments on Evolving Software Models of Analog Circuits
`Jason D. Lohn
`
`
`
`71 Analysis of Unconventional Evolved Electronics Adrian Thompson
`and Paul Layzell
`
`Article 5
`
`80 Building Consumer Trust Online Donna L. Hoffman,
`Thomas P. Novak, and Marcos Peralta
`
`86 GPS-Based Geographic Addressing, Routing, and Resource
`Discovery Tomasz Imielinski and Julio C. Navas
`
`93 Top Management Toolbox for Managing Corporate IT
`Niv Ahituv, Moshe Zviran, and Chanan Glezer
`
`C o | u m n 5
`
`I7 Practical Programmer Inspections—Some Surprising Findings Robert L. Glzm
`21 SharingStandards lT Skills Standards Roy Rabid
`
`27 Viewpoint Taking the Lead in Licensing Software Engineers Donaldj. Bagert
`
`101 Thinking Objectively OO Distributed Programming Is Not Distributed 00 Programming
`Raf/lid, Guerraauz' and Mohamed E. Fag/ad
`I 20 Inside Risks Just a Matter of Bandwidth Lauren Wez'nrtein
`
`De pa rtments
`11 NewsTrack
`13 Forum
`
`105 Career Opportunities
`117 Calendar of Events
`
`Digital Library
`Enhancements
`
`see page 30
`
`29 Index for Advertisers
`
`I 19 Calls for Participation
`
`Cover by Terry Miura
`
`3 2
`
`2 of 11
`0f11
`
`
`
`COMMUNICATIONS OF THE ACM April I999/Vol. 42, No 4
`
`

`

`
`
`Editorial Pointers
`
`
`
`THIS month, we look at the evolutions unfolding in the worlds of
`hardware and software, both surely representing milestones in their
`respective spheres.
`We begin with a discussion of the value of free software, a contro—
`versial topic that has recently achieved new dimensions and spawned
`powerful and influential alliances—and foes. Our focus is the open—
`source process of making source code freely available online to all to
`use and cusiomize as needed. Four pioneering players—Linus
`Torvalds, Larry Wall, Roy Fielding, and John Ousterhout—elaborate
`on their own experiences, as well as debate the ramifications of the
`open-source practice on collaborative software development.
`Orchestrating this effort along with Managing Editor Tom Lambert
`is Tim O’Reilly, a respected book publisher noted for his leadership in
`the open-source community. Indeed, shortly before press time O’Reilly
`was awarded Infl) VVorldi Industry Achievement award as a representa—
`tive of the collaborative software community. He responded by point-
`ing out that open—source software is reinvigoratng the computing
`industry. “The momentum behind Linux, the development of hybrid
`business models that include both open—source and propriety software
`by companies like Sendmail and Scriptics, and the continuing strength
`of open—source software, such as Apache and Perl, all point to a robust,
`diverse future for a spectrum of development models that leverage the
`strengths of collaborative development and open standards.”
`
`OUR special section this month details the emerging field of evolv—
`able hardware, that is, hardware capable of changing its structure and
`behavior by interacting with its environment. Guest editor Xin Yao
`explains one of the key motivating factors behind EHW is the inflexi-
`bility of current tools and the need to build hardware that can learn
`and adapt dynamically online. The challenge is how to find the most
`effective methods for making hardware soft.
`This section pulls together some of the most intriguing work in
`FHW from around the globe. Experts in the field evaluate how exist—
`ing EHW systems are performing, and predict the future directions
`the field will take. We hope you find this select group of articles an
`ideal introduction to a fascinating field we have only begun to exploit.
`
`COMING NEXT MONTH: The May issue will spotlight new
`developments in computer—human interaction with a special
`Station on the captivating field of persuasive computing centering
`on interfaces designed to influence human behavior: Another
`valuable section will explore the diversity of usability practices.
`
`
`
`
`llllMMNIlllTlflNS
`
`OF THE ACM
`
`A monthly publication of the ACM
`
`Publications Office
`ACM, ISIS Broadway.
`New York. New York l0036-570I USA
`(2|2) 869-7440 FAX: (2l2) 869-0481
`
`Editor: Diane Crawford
`Managing Editor: Thomas E. Lambert
`Senior Editor: Andrew Rosenbloom
`Associate Editor: Robert Fox
`Editorial Assistant: Helen Pacheco
`Copyright: Deborah Cotton
`
`Contributing Editors
`John Perry Barlow; Mohamed E. Fayad;
`Robert L. Glass; Seymour Goodman;
`Brock N, Meeks; Neil Munro;
`Peter G, Neumann; Larry Press; Roy Rada;
`Pamela Samuelson; Elliot Soloway
`Art Director: Caren Rosenblatt
`Production Manager:
`Lynn D’Addesio
`
`Advertising Director: Walter Andrzeiewski
`Coordinator: Ted Mainwaring
`
`l
`
`Contact Points
`CACM editorial: crawford7d@acm.org
`' CACM advertising: acm»advertising@acm.org
`l Copyright permission: permissions@acm.org
`Calendar items: calendar@acm.org
`Change of address: acmcoa@acm.org
`ACM Member Services Information:
`acmhelp@acm.org
`
`I
`
`‘
`
`Display Advertising Representatives
`Southeast/Foreign:
`Walter Andrzejewski
`(2l2) 626-0685; Fax: (2|2) 869-048I
`email: andneiewski@acm.org
`Northeast:
`The Summit Group
`(908) 876-l249, Fax: (908) 876-9332
`email: hersh@ibm.net
`Midwest:
`Bart Engels
`(847) 854-6050. Fax: (847) 854-8I83
`email: enge|s|@ao|.com
`West:
`Marshall Rubin and Associates
`(BIS) 995-8828; Fax: (818) 995—6366
`email: mrubin@westwor|d.com
`
`Classified Advertising
`ACM Advertising Department,
`ISIS Broadway. New York, NY |0036-570l.
`(2|2) 869-7440: Fax: (2|2) 869-048I.
`email: acm-advertising@acm.org.
`Communications ofthe ACM
`(ISSN com—0782) is published monthly by the
`ACM.
`|5l5 Broadway, New York, NY
`I0036-57OI. Periodicals postage paid at
`New York, NY |000 l, and other mailing offices.
`POSTMASTER: Please send address changes to
`Communications of the ACM,
`|5|5 Broadway,
`New York, NY |0036-570| USA.
`
`Printed in the U.S.A.
`
`@ V/BPA
`
`COMMUNICATIONS OF THE ACM April l999/Vol. 42, No. 4
`
`5 3
`
`3 of 11
`of11
`
`
`
`

`

`
`
`llllMll/[NIUI’I‘IIINS
`
`OF THE ACM
`A monthly publication of
`The Association for Computing
`Machinery
`
`Advisory Board
`Gordon Bell; Hal Berghel; Grady Booch;
`Nathaniel Borenstein; Vinton G. Cerf.
`Kilnam Chon; Jacques Cohen;
`Larry L. Constantine; Jon Crowcroft:
`Peter]. Denning; Mohamed E. Fayad'.
`Usama Fayyad; Christopher Fox; Ravi Ganesan:
`Don Gentner: Don Hardamy; Karen Holablati:
`Barry M. Leiner. Pattie Maes; Eli Noam:
`Cherri Pancake; Yakov Rekhter: Douglas Rlecken;
`Ted Selker, Dennis Tsichritzis; Ronald Vetter;
`Pierre Wellner
`
`Publications Board
`Chair: William Arms; Peter J. Denning: Robert
`Allen: Ronald F. Boisvert; Jim Cohoon:
`Lorrie F. Cranor; Joseph Halpern;
`Carol Hutchins; David Wise.
`
`ACM Copyright Notice
`Copyright © I999 by Association for Computing
`Machinery, Inc. (ACM). Permission to make
`digital or hard copies of part or all ofthls work
`for personal or classroom use is glanted without
`fee provided that copies are not made or
`distributed for profit or commercial advantage
`and that copies bear this notice and full citation
`on the first page. Copyright for components of
`this work owned by others than ACM must be
`honored. Abstracting with credit is permitted. To
`copy otherwise, to republish. to post on servers,
`or to redistribute to lisis. requires prior specific
`permission and/or fee. Request permission to
`publish from: Publications Dept. ACM, Inc.
`Fax +| (2|2) 869-048I or email
`<permissions@acm.org>
`For other copying of articles that carry a code
`at the bottom of the first or last page or screen
`display, copying is permitted provided that the
`per-copy fee indicated in the code is paid through
`the Copyright Clearance Center, 222 Rosewood
`Drive, Danvers, MA 0|923. 508-750-8500.
`508-750-4470 (fax).
`
`Subscriptions
`is included in the
`Annual subscription cost
`society member dues of $9l.00 (for studens.
`cost is included in $35.00 dues): the nonmember
`annual subscription is $|54. See top line of
`mailing label for subscription expiration date
`coded in four digits: the first two are year.
`last two. month of expiration. Microfilm and
`microfiche are available from University
`Microfilms international. 300 North Zeeb Road.
`Dept. PR, Ann Arbor, MI 48l06; (BOO) 52l-0600.
`
`Single Copies are $8 to members and SW to
`nonmembers. Please send orders prepaid plus $7
`for shipping and handling to ACM Order Dept.
`P.O. Box |l4|4. New York. NY |0286—|4l4 or
`call (2|2) 626-0500. For credit card orders call
`(800) 342-6626. Order personnel on duty 8:30-
`4:30 EST, After hours. please leave message and
`order personnel will return your call.
`
`@
`
`
`
`
`
`
`
`ACM
`The Association for Computing Machinery
`ACM (founded I947) is an international scientific and educational
`organization dedicated to advancing the art, science, engineering,
`and application of information technology, sewing both professional and
`public interests by fostering the open interchange of information and by
`promoting the highest professional and ethical standards.
`
`Executive Director and CEO:
`Associate Director. Office of
`External and International Relations:
`
`John White
`Fred Aronson
`
`Deputy Executive Director and COO:
`Director, Office of Information Systems:
`Director, Office of Financial Services:
`Associate Director. SIG Financial Reporting:
`Associate Director, Budgeting and
`Financial Operations Planning:
`
`Director, Office of Membership:
`Director, Office of Publications:
`Deputy Director:
`Deputy Director, Magazine Development:
`Publisher, ACM Books and journals:
`
`Patricia Ryan
`Wayne Graves
`Michael Lichtenstein
`John DeLorenzo
`Russell Harris
`
`Lillian Israel
`
`Mark Mandelbaum
`Bernard Rous
`Diane Crawford
`Jono Hardiowirogo
`
`Director, Office of SIG Services; PLAN: Donna Baglio; COMM, GRAPH, MM, SOUND:
`Associate Director Patrick McCarren; ACT, APL. DOC, NUM, SAM. SOFT, 3C: Julie Goetz;
`ARCH. DA, MICRO, MOBILE, SIM: Lisette Burgos; CHI: David Riederman;
`Ada, APP, BIO, CA5, CSE, CUE, METRICS, MOD, OPS, SAC: Heather Levell;
`ART, CAPH, CPR. GROUP, IR, KDD, UCCS, WEB: Alisa Rivkin.
`ACM Council
`President
`Barbara Simons
`Vice-President
`A. Joseph Turner
`Secretary/Treasurer
`Claus Unger
`Past President
`Charles H. House
`William Arms
`Chair, Publications Board
`Carla Schlatter Ellis
`Chair, SIG Board
`
`Members-at-Large; David 5. Johnson (1996-2000); Robert Ritchie {19962000}:
`David Brown (7998-2002): Maria Klawe (l99a-2002l;
`Regional Representatives: Central Region. David 5. Wise “9964999): Eastern Region,
`Frances E. Allen {I997QOOO}: \‘ir'cslcm Region. Bryan Pi’eas “9934001): International
`Region, David E. Arnold 0997-2000)
`SIG Council Representative: Mary Whitton
`
`Board Chairs and Standing Committees
`Education Board: Peter Denning; SIG Board: Carla Schlatter Ellis:
`Membership Activities Board: David Arnold;
`Publications Board: William Arms; USACM Committee: Charles Brownstein;
`Committee for Scientific Freedom and Human Rights: Marc Rotenberg
`
`SIG Chairs
`SIGACT: Jeffrey S. Vitter: SIGAda: Benjamin Brosgol; SIGAPL: David Siegel:
`SIGAPP: Gary Lamont; SIGARCH: Jean-Loup Baer: SIGART: Lewis Johnson:
`SIGBIO: Edward Lamie; SIGCAPH: Ephraim P. Glinert: SIGCAS: C. Dianne Martin;
`SIGCCC: Karl Klee; SIGCHI: Michael Atwood; SIGCOMM: Jon Crowcroft;
`SIGCPR: Albert Lederer; SIGCSE: Bruce Klein; SIGCUE: Jim Hightower;
`SIGDA: Steven Levitan; SIGDOC: Katherine Haramundanis; SIGGRAPH: Steve Cunningham;
`SIGGROUP: Dirk E. Mahling: SIGIR: Nicholas Belkin; SIGKDD: Won Kim;
`SIGMETRICS: Murray Woodside: SIGMICRO: Jim Bondi: SIGMIS: George Kasper;
`SIGMOBILE: Imrich Chlamtac: SIGMOD: Richard Snodgrass;
`SIGMULTIMEDIA: Lawrence Rowe: SIGNUM: Christian Bischof;
`SIGOPS: Carla Ellis; SIGPLAN: Mary Lou Sofia; SIGSAC: Ravi S. Sandhu;
`SIGSAM: Bruce W. Char; SIGSIM: Roger Smith: SIGSOFT: David Notkin:
`SIGSOUND: Carla Scaletti; SIGUCCS: John Bucher; SIGWEB: Marc Nanard
`For information from Headquarters: (2I2) 869-7440
`ACM European Service Centre:
`ACM US. Public Policy Office:
`|08 Cowley Road
`Marc Rotenberg
`666 Pennsylvania Avenue, SE, Suite 3023
`Oxford, OX4|JF, UK
`+44- | 865-3823387office
`Washington. DC 20003
`+44-l865-38l338—fax
`+ | -202-544-4859—office
`+ | -202-547-5482—fax
`acmgeurope@acm.org
`URL: http://www.acm.org
`USACMiDC@acm.org
`
` 6
`
`April I999/Vol. 47.. No. 4 COMMUNICATIONS OF THE ACM
`
`
`
`4 of 11
`4of11
`
`
`
`

`

`Tomasz Imielinski and Julio C. Navas
`
`GPS-Based Geographic
`Addressing, Routing, and
`Resource Discovery
`
`The Global Positioning System can be used to give every
`terminal a geographic address for multicasting to and from
`recipients within specified geographical areas.
`
`86
`
`April 1999/Vol. 42, No. 4 COMMUNICATIONS OF THE ACM
`
`5 of 11
`
`
`
`

`

`GPS cards will soon be included in cars manufactured in the U.S. and Europe and possibly in every
`
`other form of mobile computer as well. A user’s location will be another piece of information—as com-
`
`mon as the date is today—getting input from the GPS when outdoors and from other location-provid-
`
`ing devices when indoors. The availability of location information will have a broad effect on both
`
`application-level and network-level software. Possible new services and functions include geographic
`
`messaging, advertising, and resource discovery.
`
`Geographic messaging is the ability to send a mes-
`sage selectively to specific geographic subareas defined
`by latitude and longitude—for example, sending an
`emergency message to everyone in a specific area, such
`as a building, train station, or highway. The ability to
`send a message to a distinct geographical area would
`make it possible to perform geographically targeted
`advertising through the Internet. For example, a busi-
`ness might want to advertise a given service only to
`clients within a certain geographic range, say, within
`two miles of the company’s store. Conversely, users
`could use geographic messaging to locate services or
`resources within a geographical region, such as in their
`direct proximity. One can imagine a “Who is around?’’
`service that would locate and identify the people pre-
`sent in a given geographic area. Assuming that termi-
`nals are also equipped with cameras, users could point
`their terminals in a specific direction and get annota-
`tion (links) on and to the objects displayed by camera
`viewers; the whole external world could be viewed as
`one large Web page, so a building, for example, might
`include a link explaining its business function. Links
`could also be attached to mobile objects appearing on
`the camera viewer.
`To support such applications, location has to be a
`first-class citizen in networking protocols, like the
`Internet Protocol (IP) and Asynchronous Transfer
`Mode (ATM) and those in the application layer. Rout-
`ing protocols for geographic messages should therefore
`be developed to allow routing to a specific area defined
`by a polygon of geographic coordinates. Location
`should also be a parameter in Web access protocols to
`deliver pages on servers within a given distance from
`the user. Distance-based Web bookmarks could help
`define the relevance of Web pages by using distance as
`an extra criterion when accessing material on the Web.
`Our main objective here is to show how new ser-
`
`vices and new network functions could emerge as a
`consequence of location being universally available to
`mobile terminals. But how do the protocols have to be
`rewritten to support location-aware services, such as
`geographic messaging, geographic service discovery,
`and geographic service advertising? Geographic rout-
`ing is a key requirement, and the exact routing mech-
`anisms to make it happen are critical. We also look
`into geocasting, or broadcasting to geographical areas
`defined as arbitrary polygons, as well as the intersec-
`tion of geocasting and multicasting.
`Linking an IP address with a geographic location
`has been of interest to network researchers for quite
`some time. The first attempt to design a system that
`routes packets according to their geographic destina-
`tion, and the work most like ours, was dubbed “Carte-
`sian routing” by Gregory Finn in 1987 [5]. Xerox’s
`PARC research laboratory also pioneered location-
`dependent services [10].
`The recently proposed redesign of IP and the
`advent of the GPS [11,12] has given new impetus for
`this work. In the proposed redesign of IP [2], IP
`address type space was specifically allocated for geo-
`graphic addresses [3, 9] that would be assigned to sub-
`nets and hosts based on geographic criteria. However,
`the sender of a “geographic message’’ would be unicas-
`ting messages only to hosts with geographic IP
`addresses. Our methods seek to provide the more gen-
`eral ability of sending a message to all recipients within
`a geographical area, regardless of whether or not the
`hosts have geographical addresses.
`
`Addressing Model
`2D geographic positioning offers latitude and longi-
`tude information as a 2D vector < latitude,
`longitude >, where longitude ranges from ⫺180º
`(west) to 180º (east) and latitude ranges from ⫺90º
`
`COMMUNICATIONS OF THE ACM April 1999/Vol. 42, No. 4
`
`87
`
`6 of 11
`
`
`
`

`

`Routing Geographically
`In trying to deliver a message to any
`geographical destination, three basic
`types of solutions seem to work best—
`the geographic routing method, the
`geographic-multicast routing method,
`and the domain name service (DNS)
`method. We chose these solutions so
`the necessary geographic routing infra-
`structure in the Internet would vary
`from very little to significant. So far, we
`have implemented geographically aware
`software routers employing the geo-
`graphic routing method. Evaluations of
`these geographic routers were published
`in [7] and demonstrated to the U.S.
`Defense Advanced Research Projects
`Agency (DARPA) and members of the
`DARPA research community during
`the DARPA/ITO Global Mobility
`(GloMo) meetings in 1997 and 1998.
`All three of these solutions assume users can deter-
`mine their own locations. While outdoors, they can
`use the GPS to determine their locations. When
`indoors, they have to use a different method; one pos-
`sible solution is for each room in any building to
`include a radio beacon embedded in its ceiling. Each
`beacon would have its own geographic address, which
`it would broadcast periodically. The geographic
`address of the mobile hosts would be the same as that
`of the beacon. Therefore, mobile users would have an
`associated geographic address, even though they are
`indoors and their GPS modules are useless.
`Geographic routing method. For routing, the
`GEO (short for geographic) routing method uses the
`geographic destination area information directly, in a
`form represented by a closed polygon, and includes it
`in the header information of a geographic message.
`Ideally, geographic routing would be implemented as
`part of the Network Layer (Layer 3) of the Open Sys-
`tems Interconnect (OSI) protocol stack. However, to
`facilitate research and testing, we implemented the
`routing and forwarding logic in GEO as an applica-
`tion-layer software router. The software routers are
`designed to create a virtual internetwork overlaid onto
`the current IP network by using multicasting to dis-
`cover neighbor routers and IP tunnels to transport
`data packets through areas that do not support geo-
`graphic routing.
`The GEO system includes three main compo-
`nents: GeoRouters, GeoHosts, and GeoNodes (see
`Figure 2). GeoRouters, or geographic routers, are in
`charge of moving a geographic message from a
`sender to a set of receivers. They are essentially IP
`
`
`
`Figure 1. Interacting with a zoomable map interface.
`
`(south) to 90º (north). Thus, < 40.48640, -
`74.44513 > are the geographic coordinates for
`New Brunswick, N.J., U.S.A.
`Assuming the use of single precision floating-point
`numbers, 4B of addressing space are needed to store
`latitude and 4B to store longitude. Thus, a total of
`only 8B are needed to address the Earth’s entire surface
`with precision down to 0.1 mile. A destination geo-
`graphic address would be represented by some closed
`polygon, such as: point; circle( center point, radius );
`polygon (point1, point2, ... , pointn⫺1, pointn, point1),
`where each vertex of the polygon is represented by
`geographic coordinates. This notation would be used
`to send a message to everyone or to a group of people
`within a specified geographical area defined by the
`closed polygon.
`Consider sending a message to the city hall of
`Fresno, Calif. We would specify its geographic limits
`as a series of connected lines forming a closed polygon
`surrounding city hall. Therefore, the address of Fresno
`city hall could look like: polygon([36.80,⫺119.80],
`[36.85,⫺119.76], ... )
`In this hypothetical Fresno scenario, a user interacts
`with a zoomable map through a graphical user inter-
`face. The address of the message is specified as a poly-
`gon on the map. The polygon is then translated into
`geographic coordinates, and the message is sent to
`clients located within the bounds of that polygon. Fig-
`ure 1 shows such a scenario, in which a polygon is
`drawn around the banks of a river.
`
`88
`
`April 1999/Vol. 42, No. 4 COMMUNICATIONS OF THE ACM
`
`7 of 11
`
`

`

`GeoNode
`
`GeoRouter
`
`InterNetwork
`
`GeoAPI
`
`GeoHost
`
`GPS Monitor and
`GEOFiltering
`
`GPS
`
`routers that are geographically
`aware. Each is charged with per-
`forming geographic
`routing
`functions for the networks to
`which it is attached directly.
`Each GeoRouter keeps track of
`the geographic area it services
`(called its service area) by calculat-
`ing the union of the geographic
`areas covered by the networks
`attached to it. A GeoRouter’s ser-
`vice area is represented as a single
`simple closed polygon whose ver-
`tices are denoted by geographic
`coordinates.
`Before a geographic router can
`determine where to forward an incoming packet, it
`must first have a routing table containing information
`about the network topology and geography. Several
`protocols are available today for discovering the net-
`work topology and automatically configuring a rout-
`ing table; they can be adapted to distribute a router’s
`geographic location information, in addition to the
`other information already being passed along. For the
`purposes of geographic messaging, we extended the
`popular Routing Information Protocol (RIP) to
`include geographic location information. Using this
`protocol, which we call GeoRIP, a router has a routing
`table entry for each destination in the network. Each
`entry contains information on a destination’s geo-
`graphic location, its IP address, the shortest number of
`intermediate routers between the current router and
`the destination, and the preferred neighbor router to
`use as the next step on the path to the destination.
`When forwarding an incoming packet, a router uses
`the routing table information to determine where the
`final destinations for the message reside and which
`neighbor routers have to be sent a copy of the packet.
`First, the geographic router uses the information in the
`routing table to search for and discover where to send
`the packet. The router then creates a list of the neigh-
`bor routers on the shortest paths to the destinations,
`and a copy of the message is sent to each neighbor
`router on the list. When a geographic message has
`been forwarded all the way from the sender to all the
`receivers, the routers will have created a shortest-path
`routing tree with the root at the sender and the leaves
`at all the receivers.
`In order to reduce forwarding costs, the router
`keeps a cache of the next-hop destinations of the most
`recent geographic message packets. When a router
`receives a geographic message packet, it uses the
`incoming packet’s sender IP address and destination
`polygon together as a key into the cache. If this is not
`
`Figure 2. Components of the geographic routing system.
`
`the first packet to arrive for this destination and if the
`timer on the cache entry has not yet expired, the cache
`returns a list of all of the neighbor routers to which
`copies of the packet must be sent.
`GeoHost software, which has to be installed on all
`computer hosts, consists of an application program-
`ming interface (API) and a location-monitoring
`process. The API can be used to create programs for
`sending and receiving geographic messages. The loca-
`tion-monitoring process continually updates the host
`computer’s knowledge of its location by interfacing
`with GPS devices (if available) and by determining the
`address of the local geographic router.
`A GeoNode is a buffer for messages whose lifetimes
`are due to expire. The GeoNode’s main function is
`storing incoming geographic messages with lifetimes
`greater than zero for the duration of their lifetimes and
`periodically multicasting them on all the subnets or
`wireless cells to which they are attached. Each subnet
`and each wireless cell would have at most one GeoN-
`ode; it could also lack a GeoNode, but the geographic
`messages would lack lifetime expirations. The sender
`of the message would specify the lifetime of a geo-
`graphic message; specifying message lifetimes might be
`necessary, because mobile receivers of geographic mes-
`sages might arrive at the message destination some
`time after the geographic message first arrives.
`Moreover, because several geographic messages
`would probably reside in a GeoNode at one time, the
`multicasting of the various messages would have to be
`scheduled. The scheduling algorithm would have to
`take into account the size of the message, its priority,
`and the speed of the subnet’s transport medium. The
`GeoNode stores the message locally and assigns a mul-
`ticast group to it. It periodically multicasts the message
`
`8 of 11
`
`COMMUNICATIONS OF THE ACM April 1999/Vol. 42, No. 4
`
`89
`
`
`

`

`College Ave.
`Campus Router
`
`County Router
`
`Busch
`Campus
`Router
`
`Figure 3. Geometric routing.
`
`schedule to a well-known group address and multi-
`casts each message to its assigned group. The Geo-
`Hosts receive the message schedule and determine
`whether the host computer is located inside the mes-
`sage’s destination area. Software clients that want to
`receive a geographic message would then tune in to the
`appropriate multicast group to receive it.
`In Figure 3, a user on Rutgers University’s Busch
`Campus wants to send a message to the destination
`polygon around the Rutgers College Ave. Campus.
`The message is first passed to the Busch Campus
`router. Using the information in its routing table, the
`router determines that it does not service the target
`area, but it also realizes that the College Ave. router
`services the destination area. So it forwards the mes-
`sage to the county router, because the county router is
`the next router on the shortest path to the destination.
`Using the same algorithm, the county router decides
`to forward the message to the College Ave. router. The
`College Ave. router then transmits the message to all
`the wireless cells intersecting the destination area.
`Geographic-multicast routing method. The geo-
`graphic-multicast routing method leverages the
`power of multicasting to transport geographic mes-
`sages to their destinations. We use two terms—
`“atoms” and “partitions”—to describe its operation.
`Atoms are the smallest geographical areas with geo-
`graphic-multicast addresses. Partitions are larger geo-
`graphical areas that also have geographic addresses. A
`state, county, or town might constitute a partition.
`Partitions and atoms are arranged in a hierarchical
`fashion. Each partition contains either a whole num-
`ber of atoms or a whole number of smaller partitions.
`The sizes and shapes of the atoms and partitions are
`determined by the density of subnets and wireless
`
`90
`
`April 1999/Vol. 42, No. 4 COMMUNICATIONS OF THE ACM
`
`9 of 11
`
`Destination
`Polygon
`
`cells in a particular geographic
`area.
`Each partition and atom
`would have a geographic-mul-
`ticast address
`for use by
`routers. By “geographic-multi-
`cast address,” we mean each
`partition and atom would be
`mapped to a multicast address.
`The multicast group address
`would be chosen so it could be
`calculated using the geographic
`position of the atom or parti-
`tion. With the large address
`space available through IPv.6,
`the multicast address itself
`could be encoded using longitude and latitude, sim-
`plifying the calculation of the appropriate group
`address for an atom or partition. Every GeoNode has
`to join the multicast groups for the atoms and parti-
`tions intersecting its geographic range. Thus, a GeoN-
`ode has to know not only its own range but also
`information about the partitions intersecting its range.
`The key idea here is to approximate the destination
`polygon with the smallest partition or atom that con-
`tains it and use the multicast address corresponding to
`that partition or atom as the address of that message.
`Since the partition or atom being used is only an
`approximation of the destination polygon, some
`GeoNodes outside the destination polygon erro-
`neously receive the geographic messages.
`In order to counter the erroneous receipt of mes-
`sages, the original destination polygon is inserted into
`the multicast packet body. The GeoNodes then use
`the destination polygon to determine whether they
`should have actually received the message; if not, the
`message is ignored.
`Multicast group information has to be propagated
`carefully. Because of the large number of atoms and
`partitions and the resulting large number of multicast
`groups, we will modify the Protocol Independent
`Multicast Sparse Mode (PIM-SM) [4], which is slated
`by the Internet Engineering Task Force to be the
`future standard multicast protocol. PIM-SM is meant
`to be used in wide-area networks, networks in which
`bandwidth is poor, and multicast groups with few or
`widely scattered members. PIM-SM assumes that not
`everyone wants to receive the multicast packets and
`relies on explicit join messages from group members.
`As a result, PIM-SM has the advantage of having to
`send multicast packets only to where they have been
`requested and not having to broadcast the initial pack-
`ets, as the current multicast protocol does. PIM-SM is
`similar to core-based multicast trees [1] in that it uses
`
`
`
`

`

`a rendezvous point (RP) to
`arrange meetings between
`senders and receivers of a mul-
`ticast group. This RP also
`becomes the root of a sparsely
`populated multicast tree, with
`the multicast group members
`being the leaves of the tree. All
`senders ship their packets to
`the RP for distribution.
`The current PIM proposal
`calls for the RP to be selected
`by the first member of the
`group set to receive the mes-
`sage. Alternative RPs are also
`selected in case the primary RP
`fails. The PIM-SM specifica-
`tions call for the multicast
`group address and its list of
`primary and alternative RPs to
`be broadcast to all PIM
`routers. However, we have
`extended the PIM specifica-
`tion by implementing the fol-
`lowing intuitive guideline: The
`smaller the size of the partition
`or atom, the more locally the
`information about that partition or atom is propa-
`gated. Thus, only multicast group membership for
`very large partitions or atoms would be propagated
`across the country or around the world.
`Domain name server solution. This solution relies
`on having the DNS add geographic information to
`DNS servers. These servers will provide the full direc-
`tory information down to the level of the IP address of
`each GeoNode and its area of coverage.
`A new first-level domain—we call “.geo’’—is added
`to the set of first-level domains. Second-level domain
`names represent states, third-level names counties,
`and, finally, fourth-level names polygons of geographic
`coordinates. We can also allow polygons to occur as
`elements of second- or third-level domains to enable
`the sending of messages to larger areas. Thus, a typical
`geographic
`address
`can
`look
`like
`city-
`hall-Palo-Alto.San-Mateo-County.California.geo or
`Polygon.San-Mateo-County.California.geo, where
`Polygon is a sequence of coordinates.
`This geographic address is resolved into a set of IP
`addresses of the GeoNodes covering a particular geo-
`graphic area. Depending on the size of the message,
`the geographic destination may be transported to the
`GeoNodes in one of two ways. A small message is sent
`as a set of unicast messages to all of the GeoNodes cor-
`responding to the addresses returned by the DNS. For
`
`Figure 4. Geographic email user interface.
`
`a large message, it is more efficient to first ask all of
`these GeoNodes to join a temporary multicast group
`for the geographic area specified in the message; the
`message content is