`
`409563821EXPIRE99041991UNTIL
`
`SERIALSRECORDSSECTIONOFCALIFORNIA
`
`MARIZ
`
`jppepepsebepee:S-DIGIT95616
`VWabosabalastbvsssaVaMvnaelad
`
`
`
`
`
`O01
`
`027
`
`IBM EX. 1019
`IBM EX
`
`1 of 11
`1 of 11
`
`
`
`PieceAe)
`
`
`
`THELIBRARYDS33235&
`iSoASSéie
`
`.
`
`
`
`
`
`
`
`
`U.C. DAVIS
`April 1999
`Table of Contents, i. 50
`. REC. LIBRARY
`
`Open-Source Software Development
`32 Introduction Tim O'Reilly, Guest Editor
`38 The Linux Edge Linus Torvalds
`40 The Origin of the Camel Lot in the Breakdownof
`the Bilingual Unix 1 arry Wall
`42 Shared Leadership in the Apache Project
`Roy T. Fielding
`44 Free Software NeedsProfit John Ousterhout
`
`Evolvable Hardware
`46 Introduction Xin Yao, Guest Editor
`50 Quo Vadis Evolvable Hardware? MosheSipper,
`Daniel Mange, and Eduardo Sanchez
`57 Field-Programmable Gate Arrays Pierre Marchal
`6o Evolvable Hardware Chips for Industrial Applications
`Tetsuya Higuchi and Nobuki Kajihara
`64 Hardware Evolution System AdAM Tomofumi 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
`
`Coverby Terry Miura
`
`Articles
`
`80 Building Consumer Trust Online Donna L. Hoffman,
`Thomas P. Novak, and MarcosPeralta
`86 GPS-Based Geographic Addressing, Routing, and Resource
`Discovery Tomasz Imielinskt and Julio C. Navas
`93 Top ManagementToolbox for Managing Corporate IT
`Niv Ahituv, Moshe Zviran, and Chanan Glezer
`
`Columns
`
`17 Practical ProgrammerInspections—SomeSurprising Findings Robert L. Glass
`21 Sharing Standards IT Skills Standards Roy Rada
`27 Viewpoint Taking the Lead in Licensing Software Engineers Donald/. Bagert
`ror Thinking Objectively OO Distributed Programming Is Not Distributed OO Programming
`Rachid Guerraoui and Mohamed E. Fayad
`120 Inside Risks Just a Matter of Bandwidth Lauren Weinstein
`
`Departments
`tr News Track
`13 Forum
`29 Index for Advertisers
`
`105 Career Opportunities
`117 Calendar of Events
`119 Calls for Participation
`
`Digital Library
`Enhancements
`
`see page 30
`
`COMMUNICATIONS OF THE ACM April 1999/Vol, 42, No. 4
`
`2 of 11
`
`2 of 11
`
`
`
`COMMUNICATIONS
`
`OF THE ACM
`
`A monthly publication of the ACM
`
`Publications Office
`ACM, 1515 Broadway,
`New York, New York 10036-5701 USA
`(212) 869-7440 FAX: (212) 869-048 |
`
`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; MohamedE. Fayad;
`Robert L. Glass; Seymour Goodman;
`Brack 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 Andrzejewski
`Coordinator: Ted Mainwaring
`
`|
`
`Contact Points
`CACM editorial: crawford_d@acm.org
`| CACMadvertising: acm-advertising@acm.org
`| Copyright permission: permissions@acm.org
`Calendar items: calendar@acm.org
`Changeof address: acmcoa@acm.org
`ACM MemberServices Information:
`acmhelp@acm.org
`
`|
`
`|
`
`Display Advertising Representatives
`Southeast/Forelgn:
`Walter Andrzejewski
`(212) 626-0685; Fax: (212) 869-048 |
`email: andrzejewski@acm.org
`Northeast:
`The Summit Group
`(908) 876-1249, Fax: (908) 876-9332
`email: hersh@ibm.net
`Midwest:
`Bart Engels
`(847) 854-6050, Fax: (847) 854-8183
`email: engels| @aol.com
`West:
`Marshall Rubin and Associates
`(818) 995-8828; Fax: (818) 995-6366
`email: mrubin@westworld.com
`
`Classified Advertising
`ACM Advertising Department,
`1515 Broadway, New York, NY 10036-5701.
`(212) 869-7440; Fax: (212) 869-0481.
`email: acmn-advertising@acm.org.
`Communications of the ACM
`(ISSN 0001-0782) is published monthly by the
`ACM, 1515 Broadway, New York, NY
`10036-5701. Periodicals postage paid at
`New York, NY 10001, and other mailing offices.
`POSTMASTER:Please send address changes to
`Communications of the ACM, 1515 Broadway,
`New York, NY 10036-5701 USA.
`
`Printed in the U.S.A.
`
`cen) VBPA
`
`
`
`
`Editorial Pointers
`
`THIS month,we look at the evolutions unfolding in the worlds of
`hardware and software, both surcly representing milestones in their
`respective spheres.
`We begin with a discussion of the value offree 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 customize 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 forhis leadership in
`the open-source community. Indeed, shortly before press time O’Reilly
`was awarded nfo World’ Industry Achievement award as a representa-
`tive of the collaborative software community. He responded by point-
`ing out that open-source softwareis reinvigorating the computing
`industry. “The momentum behind Linux, the developmentofhybrid
`business models that include both open-source and propriety software
`by companies like Sendmail and Scriptics, and the continuingstrength
`of open-source software, such as Apache andPerl, all point to a robust,
`diverse future for a spectrumof development models thatleverage the
`strengths of collaborative developmentand open standards.”
`
`OURspecial section this month details the emerging field of evoly-
`able hardware, thatis, hardware capable of changingits 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 howto find the most
`effective methods for making hardware soft.
`This section pulls together some of the most intriguing work in
`EHW from aroundthe globe. Experts in the field evaluate how exist-
`ing EHW systems are performing, and predict the future directions
`thefield will take. We hope youfind this select group ofarticles an
`ideal introduction to a fascinating field we have only begun to exploit.
`
`COMING NEXT MONTH: The Mayissue will spotlight new
`developments in computer-human interaction with a special
`section 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.
`
`
`COMMUNICATIONSOF THE ACM April 1999/Val, 42, No, 4
`
`5 3
`
`3 of 11
`of 11
`
`
`
`
`
`
`
`
`
`
`COMMUVICATIONS
`
`OF THE ACM
`A monthly publication of
`The Association for Computing
`Machinery
`
`Advisory Board
`GordonBell; Hal Berghel; Grady Booch;
`Nathaniel Borenstein; Vinton G. Cerf;
`Kilnam Chon; Jacques Cohen;
`Larry L. Constantine; Jon Crowcroft;
`PeterJ. Denning; Mohamed E. Fayad;
`Usama Fayyad; Christopher Fox; Ravi Ganesan;
`Don Gentner; Don Hardaway; Karen Holtzblatt;
`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 Natice
`Copyright © 1999 by Association for Computing
`Machinery, Inc. (ACM). Permission to make
`digital or hard copies of part orall of thls work
`for personal or classroom useis granted without
`fee provided that copies are not made or
`distributed for profit or commercial advantage
`and that copies bear this notice andfull citation
`onthefirst 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 redistributetolists, requires prior specific
`permission and/orfee. Request permission to
`publish from: Publications Dept. ACM,Inc.
`Fax +1 (212) 869-0481 or email
`<permissions@acm.org>
`For other copying ofarticles that carry a code
`at the battom ofthefirst or last page or screen
`display, copying is permitted provided that the
`per-copy fee indicated in the codeis paid through
`the Copyright Clearance Center, 222 Rosewood
`Drive, Danvers, MA 01923, 508-750-8500,
`508-750-4470 (fax).
`
`Subscriptions
`is included in the
`Annual subscription cost
`society member duesof $91.00 (for students,
`costis included in $35.00 dues); the nonmember
`annual subscription is $154. See topline of
`mailing label for subscription expiration date
`codedin fourdigits: the first two are year,
`last two, month of expiration. Microfilm and
`microfiche are available from University
`Microfilms tnternational, 300 North Zeeb Road,
`Dept. PR, Ann Arbor, MI 48106; (800) 521-0600.
`
`Single Capiesare $8 to members and $17 to
`nonmembers. Please send orders prepaid plus $7
`for shipping and handling to ACM Order Dept,
`P.O. Box 11414, New York, NY 10286-1414 or
`call (212) 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 recurn yourcall.
`
`e
`
`
`
`ACM
`The Association for Computing Machinery
`ACM (founded | 947) is an international scientific and educational
`organization dedicated to advancing the art, science, engineering,
`and application of information technology, serving 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:
`
`Patricia Ryan
`Wayne Graves
`Michael Lichtenstein
`John DeLorenzo
`Russell Harris
`
`Director, Office of Membership:
`Director, Office of Publications:
`Deputy Director:
`Deputy Director, Magazine Development:
`Publisher, ACM Books and Journals:
`
`Lillian Israel
`
`Mark Mandelbaum
`Bernard Rous
`Diane Crawford
`Jono Hardjowirogo
`
`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, CAS, 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 S. Johnson (1996-2000); Robert Ritchie (1996-2000);
`David Brown (1998-2002); Maria Klawe (1998-2002);
`Regional Representatives: Central Region, David S$. Wise (1996-1999); Eastern Region,
`Frances E. Allen (1997-2000); Western Region, Bryan Preas (1998-2001); Internacional
`Region, David B. Arnold (1997-2000)
`SIG Council Representative: Mary Whitton
`
`Board Chairs and Standing Committees
`Education Board: Peter Denning; SIG Board: Carla SchlatterEllis;
`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 Soffa; SIGSAC: Ravi S. Sandhu;
`SIGSAM: Bruce W. Char; SIGSIM: Roger Smith; SIGSOFT: David Notkin;
`SIGSOUND:Carla Scaietti; SIGUCCS: John Bucher; SIGWEB: Marc Nanard
`For information from Headquarters: (212) 869-7440
`ACM EuropeanService Centre:
`ACM U.S.Public Policy Office:
`108 Cowley Road
`Marc Rotenberg
`666 Pennsylvania Avenue, SE, Suite 302B
`Oxford, OX4IJF, UK
`+44-|865-382338-—office
`Washington, DC 20003
`+44-1865-381338—fax
`+1-202-544-4859—office
`+|-202-547-5482—fax
`acm_europe@acm.org
`URL: http://www.acm.org
`USACM_DC@acm.org
`
` 6
`
`April 1999/Vol.42,No.4 COMMUNICATIONS OF THE ACM
`
`
`
`4 of 11
`4 of 11
`
`
`
`
`
`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 G