physical properties of the underlying networks. Moreover, the use of
tunnels means that the host on which the router daemon is running
need not be connected to more than one subnet in order for the router
to forward GPS messages. This virtual internetwork would be
responsible for routing GPS address messages only. This virtual
network, however, is not intended to be a permanent solution and is
only intended to provide a means of supporting GPS address routing
until it gains wider acceptance and support in the Internet
infrastructure.
4c-i. Configuration
When a GPSRouteD initially executes, it first checks the file
/etc/GPSRouteD.conf for configuration commands to add tunnel and
multicast links to other GPS address routers. There are two kinds of
configuration commands:
multicast <multicast-address> <peer|child>
tunnel <local-addr> <remote-addr>
<parent|peer|child|host> <service-area>
The tunnel command is used to create a tunnel between the local host
on which the GPSRouteD executes and a remote host on which another
GPSRouteD executes. The tunnel must be set up in the GPSRouteD.conf
files at both ends before it will be used.
The multicast command tells the router which multicast addresses to
join. These addresses will carry IGPSMP messages and replies. The
router will use these IGPSMP messages to build up and keep current
its own internal routing table.
4d. Multicast Address Resolution Protocol (MARP)
Of course, this begs the question, how will the individual computers
know which multicast addresses to join? For example, an MH would
have to join the multicast address of its current cell so that it can
receive GPScast messages (using application-level filtering) or
directions to join other multicast groups (using multicast
filtering). We have designed a protocol called Multicast Address
Resolution Protocol (MARP) that works the same way as Reverse Address
Resolution Protocol (RARP). However, instead of returning the IP
address of the MH, it will return multicast group address of the cell
the MH is currently in. The MH would then join this multicast group.
4e. Internet GPS Management Protocol (IGPSMP)
The Internet GPS Management Protocol (IGPSMP) is used by GPS routers
to report, query, and inform their router counterparts about their
geographical service areas. The IGPSMP will also be used to verify
that routers are correctly functioning.
The vocabulary of IGPSMP will consist of six words:
o set service area - Used by the parent router to set the
geographic service area of a router. This is needed in
order to automatically respond to router failure or new
router boot-up.
o confirm service area - confirms that a router has received
its service area.
o geographical service area query - This message will be used
by a router to build up its geographical routing table.
It is sent to all routers on the same level.
o service area report - This message is sent in response to a
query request. It contains a bounding closed polygon
described using GPS coordinates which contains the service
area for the router.
o ping - This message is sent periodically to ascertain whether
the router is currently functioning properly. Usually sent
by the parent router in the hierarchy tree.
o alive signal - Usually sent as a reply to the ping message.
Used by a router to indicate that it is functioning
correctly. It is also sent immediately after a router
boots.
All of IGPSMP messages will be sent on an all-routers multicast
address for a particular hierarchy level. The exact multicast
address can be set in the router configuration file.
Note that for the GPS-Multicast routing scheme, the time-to-live
value of the service area reports will be varied in order to control
the distribution of the information. In GPS-Multicast routing, only
the multicast group membership for very large partitions will be
distributed throughout the country. Smaller partition may only be
distributed to neighbor routers.
5. Working Without GPS Information
5a. Users Without GPS Modules
Mobile users without GPS modules can still participate - though at a
very reduced level. When an MH enters a cell, it can use an MARP to
discover the local multicast group for that cell or atom. As the
user roams from cell to cell, the mobile host can keep track of the
current cell that the user is in and adds or drops the multicast
groups pertaining to those cells. The user's GPS address can be set
to be the center of the current cell.
5b. Buildings block GPS radio frequencies. What then?
Each room can have a radio beacon placed on the ceiling. The beacon
will be weak enough so that it will not penetrate walls. Each radio
beacon will have its own GPS-address associated with it which it will
broadcast. When a mobile user enters a room, his MH will detect the
beacon and read the beacon's GPS address. The GPS-address of the MH
will be set to the GPS-address of the beacon. The MH will then use
this beacon's GPS address in order to perform any message filtering
that it needs to do. Now the mobile user can have a GPS-address
associated with him even though he is indoors and his GPS-module is
useless.
6. Application Layer Solution
In this subsection we sketch a third solution which relies more
heavily on the DNS.
In the application layer solution the geographic information is added
to the DNS which provides the full directory information down to the
level of the IP address of each base station and its area of coverage
represented as a polygon of coordinates.
A new first level domain - "geographic" is added to the set of first
level domains. The second level domain names include states, the
third, counties and finally, the fourth: polygons of coordinates, or
so called points of interests. We can also allow, polygons to occur
as elements of second, third domains to enable sending messages to
larger areas.
Thus a typical geographic address can look like
city-hall-Palo-Alto.San-Mateo-County.California.geographic
or
Polygon.San-Mateo-County.California.geographic
where Polygon is a sequence of coordinates.
This geographic address is resolved in a similar way as the standard
domain addresses are resolved today into a set of IP addresses of
base stations which cover that geographic area. There are several
possibilities here:
a. A set of unicast messages is sent to all base stations
corresponding to the IP addresses returned by the DNS. Each base
station then forwards the message using either of the two last link
solutions: application level or network level filtering.
b. All the base stations join the temporary multicast group for the
geographic area specified in the message. In this way we may avoid
sending the same message across the same link several times. Thus,
after the set of relevant base stations is determined by the DNS, the
temporary multicast group is established and all packets with that
multicast address are sent on that multicast address.
c. Only one, central to the polygon base station is returned by the
DNS just as in the IP unicast solution. However that "central" base
station will have to forward messages to the other base stations
within the polygon.
Notice that we should distinguish between "small area" and "wide
area" geographic mail. The "small area" mail will be most common and
will most likely involve just one base station, favoring a simple
form of solution (a).
7. Reliability
Should the geographic messages be acknowledged?
Since we have no control if users are present in the target
geographic area where the mail is distributed we do not see a need
for individual acknowledgments from the message recipients. However,
we believe that the base stations (MSS) covering the target area of
geographic mail should acknowledge the messages.
Typically only a few base stations will be involved since typically
we will not cover very broad geographic areas anyway. We assume that
the base stations, additionally to forwarding the the messages on
their wireless interfaces will buffer them, either to periodically
multicast them (emergency response) or to provide them to users who
just entered a cell and download the "emergency stack" of messages
for that area as a part of the service hand-off protocol.
8. Security Considerations
Some method of determining who has permission to send messages to a
large geographical area is needed. For instance, perhaps only the
mayor of New York City has permission to send a message to all of New
York City.
9. References
Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC1112,
August 1989.
S. Deering. Multicast Routing in a Datagram Internetwork. Ph.D.
Thesis, Stanford University, (December 1991).
J. O'Rourke, C.B. Chien, T. Olson, and D. Naddor, A new linear
algorithm for intersecting convex polygons, Computer Graphics and
Image Processing 19, 384-391 (1982).
J. Ioannidis, D. Duchamp, and G. Q. Maquire. IP-Based Protocols for
Mobile Internetworking. Proc. of ACM SIGCOMM Symposium on
Communication, Architectures and Protocols, pages 235-245,
(September, 1991).
10. Authors' Addresses
Tomasz Imielinski and Julio C. Navas
Computer Science Department
Busch Campus
Rutgers, The State University
Piscataway, NJ
08855
Phone: 908-445-3551
EMail: {imielins,navas}@cs.rutgers.edu