As per Relevance of the word addressing, we have this rfc below:
Network Working Group T.
Request for Comments: 2009 J.
Category: Experimental Rutgers
November 1996
GPS-Based Addressing and
Status of this
This memo defines an Experimental Protocol for the
community. This memo does not specify an Internet standard of
kind. Discussion and suggestions for improvement are requested
Distribution of this memo is unlimited
IANA Note
This document describes a possible experiment with
addresses. It uses several specific IP addresses and domain names
the discussion as concrete examples to aid in understanding
concepts. Please note that these addresses and names are
registered, assigned, allocated, or delegated to the use
here
Table of
1. Introduction...................................... 2
1b. General Architecture...................... 3
1c. Scenarios of Usage: Interface Issues...... 3
2. Addressing Model.................................. 4
2a. Using GPS for Destination Addresses....... 5
3. Routing........................................... 7
3a. GPS Multicast Routing Scheme (GPSM)...... 7
3a-i. Multicast Trees................... 8
3a-ii. Determining the GPS
Addressing........................ 10
3a-iii. Building Multicast Trees.......... 11
3a-iv. Routing........................... 12
3a-v. DNS Issues........................ 12
3a-vi. Estimations....................... 12
3b. "Last Mile" Routing..................... 13
3b-i. Application Level Filtering....... 13
3b-ii. Multicast Filtering............... 13
3b-iii. Computers on Fixed Networks....... 14
3c. Geometric Routing Scheme (GEO)........... 14
3c-i. Routing Overview.................. 14
3c-ii. Supporting Long-Duration GPScasts. 16
3c-iii. Discovering A Router's Service Area 17
Imielinski & Navas Experimental [Page 1]
RFC 2009 GPS-Based Addressing and Routing November 1996
3c-iv. Hierarchical Router Structure
Multicast Groups.................. 18
3c-v. Routing Optimizations............. 19
3c-vi. Router-Failure Recovery Scheme.... 19
3c-vii. Domain Name Service Issues........ 20
4. Router Daemon and Host Library.................... 21
4a. GPS Address Library - SendToGPS()......... 21
4b. Establishing A Default GPS Router......... 22
4c. GPSRouteD................................. 22
4c-i. Configuration...................... 23
4d. Multicast Address Resolution Protocol (MARP) 23
4e. Internet GPS Management Protocol (IGPSMP). 24
5. Working Without GPS Information................... 25
5a. Users Without GPS Modules................. 25
5b. Buildings block GPS radio
What then?................................ 25
6. Application Layer Solution........................ 25
7. Reliability....................................... 26
8. Security Considerations........................... 27
9. References........................................ 27
10. Authors' Addresses................................ 27
1.
In the near future GPS will be widely used allowing a broad
of location dependent services such as direction giving, navigation
etc. In this document we propose a family of protocols and
methods to integrate GPS into the Internet Protocol to enable
creation of location dependent services such as
o Multicasting selectively only to specific
regions defined by latitude and longitude. For example
sending an emergency message to everyone who is
in a specific area, such as a building or train station
o Providing a given service only to clients who are within
certain geographic range from the server (which may be
itself), say within 2 miles
o Advertising a given service in a range restricted way, say
within 2 miles from the server
Imielinski & Navas Experimental [Page 2]
RFC 2009 GPS-Based Addressing and Routing November 1996
o Providing contiguous information services for mobile
when information depends on the user's location.
particular providing location dependent book-marks,
provides the user with any important information
happens to be local (within a certain range)
including other mobile servers
The solutions which we present are flexible (scalable) in terms
the target accuracy of the GPS. We also discuss cases when GPS
be used (like inside buildings).
The main challenge is to integrate the concept of physical
into the current design of the Internet which relies on
addressing. We see the following general families of solutions
a) Unicast IP routing extended to deal with GPS
b) GPS-Multicast
c) Application Layer Solution using extended
The first two solutions are presented in this memo. We only
the third solution
1b. General
We will assume a general cellular architecture with base
called Mobile Support Stations (MSS). We will consider a wide
of cells, including outdoor and indoor cells. We will discuss
cases when the mobile client has a GPS card on his machine and
when the GPS card does not work (i.e. - inside buildings).
We will assume that each MSS covers a cell with a well defined
specified as a polygon of spatial coordinates and that the MSS
aware of its own range
1c. Scenarios of Usage and Interface
Below, we list some possible scenarios of usage for the
messaging
Consider an example situation, of an area of land near a river
During a severe rain storm, the local authorities may wish to send
flood warning to all people living within a hundred meters of
river
Imielinski & Navas Experimental [Page 3]
RFC 2009 GPS-Based Addressing and Routing November 1996
For the interface to such messaging system we propose to use a zoom
able map similar to the U.S. Census Bureau's Tiger Map Service.
map would allow a user to view a geographical area at varying
of magnitude. He could then use a pointing device, such as a mouse
to draw a bounding polygon around the area which will receive
message to be sent. The computer would then translate the
polygon into GPS coordinates and use those coordinates when
and routing the message. Geographical regions specified using
zoom-able map could be stored and recalled at a later time.
zoom-able map is analogous to the IP address books found in
email programs
To continue with the above example, local officials would call up
map containing the river in danger of overflowing. They would
hand-draw a bounding polygon around all of the areas at least
hundred yards from the river. They would specify this to be
destination for a flood warning email to all residents in the area
The warning email would then be sent. Similar applications
traffic management (for example, reaching vehicles which are stuck
traffic) and security enforcement
Other applications involve general client server applications
servers are selected on the basis of the geographic distance.
example, one may be interested in finding out all car dealers
2 miles from his/her location. This leads to an extension of the
concept in which location and distance play important roles
selecting information. We are currently in the process
implementing location dependent book-marks (hot lists) in which
associated with static and mobile servers which are present within
certain distance from the client are displayed on the client'
terminal
2. Addressing
Two-dimensional GPS positioning offers latitude and
information as a four dimensional vector
<Direction, hours, minutes, seconds
where Direction is one of the four basic values: N, S, W, E;
ranges from 0 to 180 (for latitude) and 0 to 90 for longitude, and
finally, minutes and seconds range from 0 to 60.
Thus is an example of longitude and
is an example of latitude
Imielinski & Navas Experimental [Page 4]
RFC 2009 GPS-Based Addressing and Routing November 1996
Four bytes of addressing space (one byte for each of the
dimensions) are necessary to store latitude and four bytes are
sufficient to store longitude. Thus eight bytes total are
to address the whole surface of earth with precision down to 0.1
mile! Notice that if we desired precision down to 0.001 mile (1.8
meters) then we would need just five bytes for each component, or
bytes together for the full address (as military versions provide).
The future version of IP (IP v6) will certainly have a
number of bits in its addressing space to provide an address for
smaller GPS addressable units. In this proposal, however, we
the current version of IP (IP v4) and we make sure that we manage
addressing space more economically than that. We will call
smallest GPS addressable unit a GPS-square
2a. Using GPS for Destination
A destination GPS address would be represented by one of
following
o Some closed polygon such as
circle( center point, radius )
polygon( point1, point2, point3, ... , pointn
where each point would be expressed using GPS-
addresses. This notation would send a message to
within the specified geographical area defined by the
polygon
o site-name as a geographic access
This notation would simulate the postal mail service.
this manner, a message can be sent to a specific site
specifying its location in terms of real-world
such as the name of a specific site, city, township
county, state, etc. This format would make use of
directory service detailed later
Imielinski & Navas Experimental [Page 5]
RFC 2009 GPS-Based Addressing and Routing November 1996
For example, if we were to send a message to city hall in Fresno
California, we could send it by specifying either a bounding
or the mail address. If we specify a bounding polygon, then we
specify the GPS limits of the city hall as a series of
lines that form a closed polygon surrounding it. Since we have
list of connected lines, we just have to record the endpoints of
lines. Therefore the address of the city hall in Fresno could
like
polygon([N 45 58 23, W 34 56 12], [N 23 45 56, W 12 23 34], ... )
Alternatively, since city hall in Fresno is a well-
geographical area, it would be simpler to merely name
destination. This would be done by specifying "postal-like"
such as city_hall.Fresno.California.USA
For "ad hoc" specified areas such as, say a quad between 5th and 6
Avenue and 43 and 46 street in New York, the polygon addressing
be used
Unfortunately, we will not be able to assume that we have
addressing space available in the IP packet addressing space
address all GPS squares. Instead we will propose a solution which
flexible in terms of the smallest GPS addressable units which we
atoms. In our solution, a smaller available addressing space (in
IP packet) will translate into bigger atoms. Obviously, we can
as precise addressing as we want to in the body of the
messages - the space limitations apply only to the IP
space
By a geographic address we mean an IP address assigned to
geographic area or point of interest. Our solution will be
in terms of the geographic addressing space
Below, we will use the following two terms
o Atoms: for smallest geographic areas which
geographic address
Thus, atoms could be as small as GPS squares but could
o Partitions: These are larger, geographical areas, which
also have a geographic address. A state, county, town etc
may constitute a partition. A partition will contain a
of atoms
Imielinski & Navas Experimental [Page 6]
RFC 2009 GPS-Based Addressing and Routing November 1996
Here are some examples of possible atoms and partitions
o A rectangle, defined by truncating either longitude
latitude part of the GPS address by skipping one or
least significant
o A circle, centered in a specific GPS address with
prespecified radius
o Irregular shapes such as administrative domains: states
counties, townships, boroughs, cities
Partitions and Atoms (which are of course special atomic partitions
will therefore have geographic addresses which will be used
routers. Areas of smaller size than atoms, or of "irregular shape
will not have corresponding geographic addresses and will have
handled with the help of application layer
3.
Let us now describe the suggested routing schemes responsible
delivering a message to any geographical destination
We will distinguish between two legs of the connection from
sender to the receiver: the first leg from the sender to the
(base station) and the second leg from the MSS to the
residing in its cell. Our two solutions will differ on the first
of the connection and use the same options for the second leg,
we call "last mile".
3a. GPS-Multicast Routing
Here, we discuss the first leg of routing: from the sender to
MSS. We start with the multicasting solution
Each partition and atom is mapped to a multicast address. The
form of this mapping is discussed further in this subsection.
first sketch the basic idea
Imielinski & Navas Experimental [Page 7]
RFC 2009 GPS-Based Addressing and Routing November 1996
This solution provides flexible mix of the multicast and
level filtering for the geographic addressing. The key idea here
to approximate the addressing polygon of the smallest partition
contains it and using the multicast address corresponding to
partition as the IP address of that message. The original polygon
a part of the packet's body and the exact matching is done on
application layer in the second leg of the route
How is the multicast routing performed
3a-i. Multicast
The basic idea for the first level of routing using multicast is
have each base station join multicast groups for all partitions
intersect its range. Thus, MSS is not only aware of its own
but also has a complete information about system defined
which its range intersects. This information can be obtained upon
installation, from the geographic database stored as a part of DNS
If the proper multicast trees are constructed (using for example
state multicast protocol) than the sender can simply determine
multicast address of the partition which covers the original
he wants to send his message to, use this multicast address as
address on the packet and put the original polygon specification
the packet content. In this way, multicast will assure that
packet will be delivered to the proper MSS
For instance the MSS in New Brunswick may have its range
the following atoms and partitions: Busch, College Avenue,
and Livingston Campuses of Rutgers University (atoms), New
downtown area (atom), the Middlesex county partition and the NJ
partition. Each of these atoms and partitions will be mapped into
multicast address and the New Brunswick's MSS will have to join
such multicast groups
The message will be then specified and sent as follows
The user will obtain the map of the New Brunswick area possibly
the DNS extended properly with relevant maps. He will specify
intended destination by drawing a polygon on the map which will
translated into the sequence of coordinates. In the same time
polygon will be "approximated" by the smallest partition
contains that polygon. The multicast address corresponding to
partition will be the IP address for packets carrying our message
The exact destination polygon will be a part of each packet's body
In this way the packet will be delivered using multicast routing
Imielinski & Navas Experimental [Page 8]
RFC 2009 GPS-Based Addressing and Routing November 1996
the set of MSS which are members of the specified multicast
(that is all MSS whose ranges intersect the given partition).
such MSS now will follow the "last mile" routing which is
in detail, further in the proposal. Briefly speaking, the MSS
then multicast the message further on the same multicast address
the client will perform the final filtering o application layer
matching its location (obtained from GPS) with the polygon
in the packet's body. Other solutions based entirely on
are also possible as described below
End_
However, things cannot be as simple as described. For such a
potential number of multicast groups if we build entire
trees, the routing tables could be too large. Fortunately it is
necessary to build complete multicast trees. Indeed, it in
important to know precise location of each atom in California, from
remote location, say in NJ
Thus, we modify our simple solution by implementing the
intuition
The smaller is the size of the partition (atom) the more locally
the information about that partition (atom) propagated
Thus, only multicast group membership for very large partitions
be propagated across the whole country
For example, a base station in Menlo Park, California can
several atoms ) and several larger which cover Menlo Park, such
a partition which covers the entire San Mateo county, next
cover the entire California and finally next which may cover
entire west coast. This base station will have to join
groups which correspond to all these rectangles. However, only
information about multicast group corresponding to the West
partition will be propagated to the East Coast routers
However, a simple address aggregation scheme in which only a "
significant portion" of address propagates far away would not work
Indeed, in this case a remote router, say in NJ, could have
aggregate links leading to California - in fact, in the worst case
all its links could point to California since it could have
a routing information to some location in California on any of
links
To avoid this, for each partition we distinguish one or a few
which act as designated router(s) for that partition. For example
the California partition, may have only three designated routers,
Imielinski & Navas Experimental [Page 9]
RFC 2009 GPS-Based Addressing and Routing November 1996
in Eureka, another in Sacramento and yet another in LA. Only
routing entries from the designated routers would be aggregated
the aggregate address for California. Information coming from
city routers will simply be dropped and not aggregated at all. This
in addition to a standard selection of the shortest routes,
restrict the number of links which lead to an aggregate address.
particular, when there is only one designated router per partition
there would only be one aggregate link in any router. This could
to non-optimal routing but will solve the problem of redundant links
Even with a designated routers, it may happen that the same
will arrive at a given base station more than once due to
alternative routes. Thus, a proper mechanism for discarding
copies of the same packet should still be in place. In fact, due
the possible intersections between ranges of the base stations
possibility of receiving redundant copies of the same packets
exist and has to be dealt with as a part of any solution
3a-ii. Determining the geographic Multicast
Here we describe more specifically, the proposed addressing
and the corresponding routing
The addressing will be hierarchical. We will use the
convention - each multicast address corresponding to a partitions
an atoms will have the following format
1111.GPS.S.C.
where GPS is the specific code corresponding to the
addressing subspace of the overall multicast addressing space. The S
C and x parts are described below
S - Encoding of the state
Each state partition will have the address S/0/0.
C - County within a state
Each county partition having the address S/C/0.
x - Atom within a county
where 0's refer to the sequences of 0 bits on positions
to the "C part" and "x part" of address
For example if GPS part is 6 bit,s which gives 1/64 of
multicast addresses to the geographic addressing we have 22
left. The S part will take first 6 bits, C part next 6 bits (say
and then the next 10 bits encode different atoms (within a county).
Imielinski & Navas Experimental [Page 10]
RFC 2009 GPS-Based Addressing and Routing November 1996
Thus, in our terminology the proposed addressing scheme has two
of partitions: states and counties
We will assume that the GPS network will consist of all base
(MSS) in addition the rest of the fixed network infrastructure.
designated GPS routers however, will only be selected from
population of MSS. Specifically, there will be state dedicated
county dedicated routers
The concept of the designation will be implemented as follows.
the set of all MSS, only certain MSS will play a role of
routers for county and state partitions. Non-designated MSS
only join multicast groups which correspond to the GPS atoms but
GPS partitions that they intersect. The MSS which is a
router for a county partition will join the multicast group of
county in which it is located, but not the state. Finally the
designated router will also join the multicast address
to the state it is located in
3a-iii. Building Multicast
We assume that each router has geographic information attached to
- in the same format as we use for multicast mapping, S/C/x -
encodes the atom that contains the router
The multicast tree is built by a router propagating its
memberships to the neighboring routers. A given router will
retain certain addresses though, to follow the intuition of
retaining a specific information which is far away
This is done as follows: the router (not necessarily the MSS
router) with the address S/C/x will only retain addresses
S'/0/0, S/C'/0 for S' and C' different from S and C and S/C/x for
x. Thus, it will drop all the addresses of the form S'/C'/y for
S' different that S except those with C'=0 and y=0, as well as
the addresses of the form S/C'/y with C' different from C
those with y=0. Hence, these addresses will not be forwarded
further either
Thus, notice that only the information coming from designated
will be forwarded further away, since the non-designated routers
not allowed to join the multicast groups which correspond to
states and counties. Consequently, their multicast
information will be not be propagated
In this way a router at S/C/x will not bother about
locations within S'/C'/y since they are "too far".
Imielinski & Navas Experimental [Page 11]
RFC 2009 GPS-Based Addressing and Routing November 1996
Notice that this service may not be provided everywhere so we may
have to use all multicast addresses even within those assigned
geographic addresses
Notice also that all of this is flexible - if we have more
addresses available (IP v 6) we will get more precise addressing
to smaller atoms
3a-iv. GPS
Given a packet we always look for the "closest" match in the
table. If there is a complete match we follow such a link, if not
follow the address with the x-part 0'd in (county address) if
is none with the county which agrees with the destination county
we look at the entry which agrees with the state part of
destination address
3a-v. DNS
How does the client find out the multicast address on which
packet is to be sent? We assume that the local name server has
complete state/county hierarchy and that each county map can
provided possibly with the "grid" of atoms and partitions
clearly marked
Points of interests within a county can be attached multicast
just as atoms. Then a given base station would have to join
groups of the points of interests that it covers
The final stage is for the receiver to look at the polygon (point
interest) which is encoded in the body of the multicast packet
decide on the basis of its own GPS location if this packet is to
received or not. Doing it on the application layer simplifies
routing issues. There is a tradeoff, however, specially when we
very short S/C/x addresses and base stations which do not cover
given polygon in fact are reached unnecessarily. This may happen
it needs to be determined what is the number of the
addresses which are necessary to reduce this "false" alarms to
minimum
3a-vi.
Assume average cell size of, say, 2km x 2km and the average
size: say 200,000 square km, the average county size: say 4,000
square km
A reasonable size of the atom is around the size of the cell
then we do not hit wrong cells too often
Imielinski & Navas Experimental [Page 12]
RFC 2009 GPS-Based Addressing and Routing November 1996
Therefore we need the x addressing part of the S/C/x to
4,000/4 cells: 1.000 atoms. Thus we need 10 bits for x part. With 6
bits for the state and 6 bits for the county that gives 22 bits
is 1/64 of the total IP v4 multicast addressing space
With IPv6 we will have, of course, much more addressing space
we can use for the GPS multicast routing
3b. "Last Mile"
Multicasting will be used for the last mile routing in both
solutions (i.e the one just discussed and the geometric
solution described next), but in different ways
3b-i. Application Level
The MSS will forward the geographic message on its wireless
under a multicast address. This multicast address will either be
same for all locations in the range of the MSS's cell or, there
be several addresses corresponding to atoms which intersect the
cell. Additionally, a complete GPS address (for example in the
of the polygon) will be provided in the body of the packet and
exact address matching will be performed on the application layer
The receiver, knowing its GPS position uses it to match against
polygon address. The GPS position can be obtained by the
either from the GPS card or, indoors, from the indoor base
which itself knows its GPS position as a part of configuration file
3b-ii. Multicast
In multicast level filtering, the base station assigns a
multicast address to the addressing polygon in a message. It
send out a directive on the cell's specially assigned
address. All mobile clients who reside in that cell are members
that special multicast group (one per MSS). The directive sent by
MSS will contain the pair consisting of the temporary
address together with the polygon. To improve the reliability
message will be multicast several times. The clients, knowing
GPS positions will than join the temporary multicast groups if
current locations are within the advertised polygon. The MSS
then send out the real message using the temporary multicast address
The temporary multicast address would be cached for a period of time
If more packets for the same polygon arrive in a short period
time, they will be sent out on the same multicast address. If not
then the multicast address is dropped and purged from the cache
Filtering on the client's station is then performed entirely on
IP level. This solution introduces additional delay (needed to
Imielinski & Navas Experimental [Page 13]
RFC 2009 GPS-Based Addressing and Routing November 1996
the temporary multicast group) but reduces the number of
packets received by the client. This especially important for
long messages
3b-iii. Computers on Fixed
Fixed-network computers should also monitor all of the
multicast addresses for their site and GPS square. In this manner
the fixed computers will also receive messages sent to specific GPS
addresses
Modified base stations would still be in charge of multicasting
messages to the computers. These base stations would have the
GPS-routing functionality as the mobile computer base stations
Their main difference would be that the mobile computer base
would use radio frequencies to multicast their messages and the
network base stations use the local Ethernet or Token Ring network
The next scheme differs from the GPS multicast scheme described
only on the first leg of the route, from the sender to the MSS.
"last mile" from the MSS to the final destination will have the
options as described above
3c. Geometric Routing Scheme (GEO
The Geometric Routing Scheme (GEO) uses the polygonal
destination information in the GPScast header directly for routing
GEO routing is going to be implemented in the Internet Protocol (IP
Network layer in a manner similar to the way multicast routing
first implemented. That is, a virtual network which uses
addresses for routing will be overlayed onto the current
internetwork. We would accomplish this by creating our own GPS
address routers. These routers would use tunnels to ship
packets between them and between the routers and base stations
3c-i. Routing
Sending a GPScast message involves three steps: sending the message
shuttling the message between routers, and receiving the message
Sending a GPScast message is very similar to sending a UDP datagram
The programmer would use the GPScast library routine SendToGPS().
Among other parameters, this routine will accept the GPS
destination address and the body of the message. The SendToGPS()
routine will encapsulate the GPScast message in a UDP datagram
send it to the class E address 240.0.0.0. Previously, the
administrator will have specified in the /etc/rc.local or /etc/rc.
file a route command that will specify that packets with the
Imielinski & Navas Experimental [Page 14]
RFC 2009 GPS-Based Addressing and Routing November 1996
240.0.0.0 will instead be sent to the address of the local
router. This will have the effect of sending the datagram to
nearest GPS router
Before explaining how the GPS routers shuttle the GPScast message
its destination, an introduction to routers and their different
is in order. For scalability purposes, GPS routers are arranged in
hierarchical fashion. Each layer would correspond to a
geographic area, such as a state or a city. At the top would
country-wide routers in charge of moving messages from one end of
country to another. At the bottom would be campus or
routers in charge of moving messages between the base stations.
Figure 1.
Country-Router(s
/ \
State-Router(s
/ \
City-Router(s
/ \
Router
/ | \ | \
Base Base Base Base
Figure 1: Hierarchy of routers
A GPS router essentially consists of three parts: a service
table containing the geographic area serviced by the router and
of its hierarchical children, a hashed cache of previous actions,
a table containing the IP addresses of at least the router's
and the router's parent. In the case of a bottom-layer
router, the service area table will contain polygons describing
geographic reach of each child base station's cell. The
created from the union of all of the router's child base stations
polygons defines the service area of the router
Once the datagram arrives at a GPS router, the router strips
datagram off, thereby, leaving it with the original GPScast message
First the router must determine if it services any part of the
of the destination polygon. To do this, the router finds
intersection between the destination polygon and the
describing the router's service area. The polygon
algorithm used is described by O'Rourke in his paper, A New
Algorithm for Intersecting Convex Polygons. This algorithm
order N-squared time in the worst case. If the intersection
is null, then the router simply sends the message to its
router
Imielinski & Navas Experimental [Page 15]
RFC 2009 GPS-Based Addressing and Routing November 1996
------ Destination
| A |
--------------
| | B | | Router's Service Area
--------------
| C |
------
Figure 2: Polygon
However, if the result is not null, then the router does service
area described by the intersection polygon. The router now
its service area from the destination polygon and sends the rest
it's parent router. This subtraction step is actually a by-
of the intersection algorithm. Using the example in Figure 2,
destination polygon and the router's service area polygon
at the region labeled B. Therefore, the router will subtract out
B section and send the remaining sections A and C to its
router
Continuing with the example, the router now uses the
polygon B to to determine which base station (or stations)
receive the GPScast message. The router finds the
between the region B and the polygon of each base station's cell
Those base station polygons which intersect the region B will be
the GPScast message. Processes on Mobile Hosts serviced by
base stations will now use the routine RecvFromGPS() to receive
GPScast message
3c-ii. Supporting Long-Duration
Most likely, there will be a need to support sending real-
continuous media to a GPS destination. This continuous media
be an audio GPScast or a video GPScast. This would require
jitter be reduced in order to minimize disturbing artifacts in
audio or video playback. Continually checking the
geometry of each packet would incur unnecessary delays and
promote jitter
Therefore, the router will keep a hashed cache of the latest
packets and their destinations. Each cache item will be hashed
the Sender Identification included in the header of GPScast
as the key. Each cache item will contain a time stamp and a list
the next hops for that GPScast. When the time stamp exceeds
certain limit, then the cache item will be dropped. The list of
hops is a list of the IP addresses of the base stations,
routers, and parent router which are to receive a copy of the
messages
Imielinski & Navas Experimental [Page 16]
RFC 2009 GPS-Based Addressing and Routing November 1996
When a router receives a GPScast packet, it will use the
packet's Sender Id as a key into the hashed cache. If this is
the first packet to arrive for this destination and if the timer
the hash table entry has not yet expired, then the hashed cache
return a list of all of the destination addresses to which copies
the packet must be sent. Copies of the packet are sent to all
these destinations and the hash entry's time stamp is updated
If no hash table entry is found (i.e.- this is the first
encountered for this destination address), then the normal
checking routine would take over. A new cache entry is
recording all of the next-hop destination addresses of the GPScast
In this manner, if several other packets with the same
destination follow this first packet, the router can use the
table to look-up the destination base stations instead of
it using geometry
3c-iii. Discovering A Router's Service
When the router is initiated, it will consult its configuration file
One of the items it will find in the file will be the
address of the base station group to which all of its child
stations are members. The router will join this group and then
out Service Area Query messages to this multicast group
to discover and to refresh its knowledge of its children
stations and the geographical areas serviced by them
Queries are issued infrequently (no more than once every
minutes) so as to keep the IGPSMP overhead on the network very low
However, since the query is issued using unreliable
datagrams, there is a chance that some base stations may not
the query. This is important in two cases: when a child node
and when a router first boots up. The case of a failed child
will be explained later. However, when a router first boots up,
can issue several queries in a small amount of time in order
guarantee that base stations will receive the query and to
therefore, build up its knowledge about its child base
quickly
Base stations respond to a Service Area Query by issuing a
Area Report. This report is issued on the same multicast
address that all of the base stations have joined. The
contains the geographical service area of the base station. In
to avoid a sudden congestion of reports being sent at the same time
each base station will initiate a random delay timer. Only when
timer expires will the base station send its report
Imielinski & Navas Experimental [Page 17]
RFC 2009 GPS-Based Addressing and Routing November 1996
For every base station that responds, the router will create an
tunnel between it and the base station. This tunnel will carry
GPScast packet traffic between the base station and the router.
responding base station and its geographic area of service will
be included in the router's geometric routing table as a
destination for GPScast packets. Any base station that does
respond for ten continuous Service Area Queries will be
unreachable and will be dropped from the routing table
3c-iv. Hierarchical Router Structure and Multicast
R5----------------------R
/ \ / \
R1---------R2 R3---------R
/ | \ / | \ / | \ / | \
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12
Figure 3: Two peer routers (R5 and R6) cooperatively servicing
child routers (R1 - R4).
For scalability purposes, a hierarchy of routers is used to
messages from a sender to a receiver. Each layer of peer
would have its own multicast group address for the exchange
Service Area Queries and Reports between the peer routers. However
routers in distinct subtrees need not know about the routers in
subtrees. Therefore, multicast group addresses will also
between hierarchy subtrees. See figure 3. For instance, routers R
and R2 would share a multicast group and would know about each other
At the same time, routers R3 and R4 would share a different
group and would know about each other. However, routers R1 and R
would not know about R3 and R4, and vice versa
But how will the router know the location and number of its
routers and who its parent router is? As mentioned before,
router consults its configuration file upon start-up. Included
this configuration file will be the the address of its parent
and the multicast group address that the peer routers will use.
peer multicast group address will be used in the same manner as
base station multicast group address. It will be used to send
receive Service Area Queries and Reports between the parent
and the peer routers. There is only one difference. When a
sends a Service Area Report, in addition to reporting
geographical service area, a router will include the
address of its children base stations. The reason for this
explained in the router-failure recovery scheme described below
Imielinski & Navas Experimental [Page 18]
RFC 2009 GPS-Based Addressing and Routing November 1996
3c-v. Routing
The optimization described here attempts to reduce the latency of
GPScast. It does so by reducing the the number of hops a packet
traverse before finding its destination. The intuition behind
idea is this: instead of going to the parent router and then to
sibling, simply go to the sibling directly. As an
benefit, this method prevents the parent router from becoming
bottleneck or a point of failure in the routing scheme
In this optimization, when a router attempts to determine who
receive the GPS packet, it considers its peer routers as if they
also its children in the routing hierarchy. This means that
router will consider its service area to be the union of the
areas of its children and its peer routers. Also, when
destination polygon intersects the router's service area polygon,
router will forward a copy of the GPScast packet to any child or
router whose geographic service area contains or touches the packet'
GPS destination polygon
However, before it sends a copy of the packet to a peer router,
first finds the polygon
P = D /\
where D stands for the packet's destination GPS polygon, S is
polygon representing the service area of the peer router, and P
the polygon that represents the intersection of D and S. The
P is substituted for the destination polygon D in the packet and
then is the packet forwarded to the peer router. This is
because the peer router will be using that same routing algorithm
Therefore, if the peer router receives a packet with the
destination polygon D, it will also route copies of the packet to
of its qualifying peer routers causing a chain of packet copies
bounced back and forth
3c-vi. Router-Failure Recovery
In the case of a router failure, the system should be able to
around the failed router and continue to service GPScast messages
The responsibility of detecting whether a router has failed or
falls to the parent router. Using Figure 3 as an example
hierarchy, the parent router R5 periodically sends out Service
Query IGPSMP messages on its children's multicast group address
Thus, the child routers R1 and R2 will both receive this query
Normally, both routers will respond with a Service Area
message. This message contains a polygon describing their
areas and the multicast group address of their children
Imielinski & Navas Experimental [Page 19]
RFC 2009 GPS-Based Addressing and Routing November 1996
However, if a router, R1, does not respond to ten continuous queries
then it must be considered to have failed. Upon detecting this,
parent router R5 will send a Set Service Area message to the
router, R2 telling it to assume responsibility for the base
underneath the failed R1 router. In this Set Service Area message
the parent router includes the multicast group address of R1'
children. The R2 router uses this multicast address to learn
service areas and IP addresses of R1's children. The R2 router
issues a Service Area Report advertising its new enlarged
area responsibilities. All peer and parent routers will then
their routing tables to include this new information. When
failed router, R1, restarts, it will declare that it is alive
that it is again servicing its area. All routers will then
update their routing tables
In the case that there is no parent router, such as at the top of
routing hierarchy, then each peer router will keep track of
neighbors. If a neighbor router fails, then the first
router to declare that it is taking over the base stations for
failed router will take responsibility. The rest continues
before
3c-vii. Domain Name Service
Domain Name Servers (DNS) could be used to facilitate the use of
geographic addressing for sites of interest. The aim is to
specific geographic sites in a more natural and real-world
using a postal-service like addressing method. Essentially, the
would resolve a postal-service like address, such
City_Hall.New_York_City.New_York, into the IP address of the
router responsible for that site. The GPS router would then
the message to all available recipients in the site
The DNS would be used when a message is sent using
site-code.city-code.state-code.country-
addressing scheme. The DNS would evaluate the address in
starting with the country code, then the state code, etc. This
the same method used currently by the IP DNS service to return
addresses based on the country or geographic domains
Imielinski & Navas Experimental [Page 20]
RFC 2009 GPS-Based Addressing and Routing November 1996
4. Router Daemon and Host
4a. GPS Address Library - SendToGPS()
A library for GPS address routing will be constructed. The
routines contained in this library will be the SendToGPS()
RecvFromGPS() commands. SendToGPS() has the following syntax
SendToGPS(int socket, GPS-Address *address, char *message, int size
where socket is a previously created datagram socket, address is
filled GPS-Address structure with the following form
typedef _GPS-Address {
enum { point, circle, polygon } type
char *mail-address
{
enum { North, South, West, East } dir
int hours, minutes, seconds
} *points
} GPS-Address
and message and size specify the actual message and its size.
SendToGPS() routine will take the GPS-addressed message,
it in an IP packet, and then send it as a normal IP datagram.
message is encapsulated in the following manner
--------------------------------------------------------
| IP Header with destination address set to 240.0.0.0 |
--------------------------------------------------------
| Sender Identifier |
--------------------------------------------------------
| Address Type - Circle|Polygon |
--------------------------------------------------------
| Actual GPS Address (see below) |
--------------------------------------------------------
| Body of Message |
--------------------------------------------------------
where the Sender Identifier would consist of a combination of
sender's process id, host IP address, and the center of
destination polygon. The Actual Address would be one of
following
circle - single GPS address and range measured in centiminutes
Imielinski & Navas Experimental [Page 21]
RFC 2009 GPS-Based Addressing and Routing November 1996
polygon - list of GPS addresses terminated by the
address: N 255 255 255.
RecvFromGPS() has the following syntax
RecvFromGPS(int socket,GPS-Address *address,char *message,int size
where socket is a previously created datagram socket, address is
empty GPS-Address structure, and message and size specify
buffer and its size
4b. Establishing A Default GPS
The default GPS router is determined using the unicast routing
found in the UNIX kernel. The local system administrator will
previously adjusted the table so that all GPScast messages are
to the local GPS router. However, if there is no route for
messages in the table, then all messages will, by default, be sent
the default gateway. If the default gateway does not support
messages, then all attempts to send a GPScast will return an error
By default, all GPScast messages will initially have as
destination the class E address 240.0.0.0. A route will be added
the kernel routing table by the system administrator for
address. The route will specify the location of the local
router. The "route" command will be used to affect the routing
and it can be placed in the /etc/rc.local or /etc/rc.ip files so
it will take effect each time the computer is booted. For example
to specify that GPScast messages addressed to 240.0.0.0 should,
default, be sent to the router which resides on a computer on
same subnet with local address 128.6.5.53, use the following
/etc/route add host 240.0.0.0 128.6.5.53 0
If the default destination for GPScast messages is a host that
not support GPS addressing, then Network Unreachable errors will
returned to any process attempting to route GPScasts through
host
4c.
In order to provide the capability of GPS address routing
an IPv4-based internetwork, special-purpose routers will be
to support GPS address routing on top of the current Internet.
routers, which will be called GPSRouteD, will use virtual point-to
point links called tunnels in order to connect two
together over regular unicast networks. The tunnels work
encapsulating the GPS address messages in IP datagrams and
Imielinski & Navas Experimental [Page 22]
RFC 2009 GPS-Based Addressing and Routing November 1996
transmitting the message to the host on the other end of the tunnel
In this manner, the GPS address messages look like normal
packets to all IPv4 routers in between the two GPS address routers
At the end of the tunnel, the receiving GPSRouteD removes the
address message from the datagram and continues the routing process
By using tunnels, the GPS routers can be established as a
internetwork throughout the current Internet without regard for
physical properties of the underlying networks. Moreover, the use
tunnels means that the host on which the router daemon is
need not be connected to more than one subnet in order for the
to forward GPS messages. This virtual internetwork would
responsible for routing GPS address messages only. This
network, however, is not intended to be a permanent solution and
only intended to provide a means of supporting GPS address
until it gains wider acceptance and support in the
infrastructure
4c-i.
When a GPSRouteD initially executes, it first checks the
/etc/GPSRouteD.conf for configuration commands to add tunnel
multicast links to other GPS address routers. There are two kinds
configuration commands
multicast <multicast-address>
tunnel
The tunnel command is used to create a tunnel between the local
on which the GPSRouteD executes and a remote host on which
GPSRouteD executes. The tunnel must be set up in the GPSRouteD.
files at both ends before it will be used
The multicast command tells the router which multicast addresses
join. These addresses will carry IGPSMP messages and replies.
router will use these IGPSMP messages to build up and keep
its own internal routing table
4d. Multicast Address Resolution Protocol (MARP
Of course, this begs the question, how will the individual
know which multicast addresses to join? For example, an MH
have to join the multicast address of its current cell so that it
receive GPScast messages (using application-level filtering)
directions to join other multicast groups (using
filtering). We have designed a protocol called Multicast
Imielinski & Navas Experimental [Page 23]
RFC 2009 GPS-Based Addressing and Routing November 1996
Resolution Protocol (MARP) that works the same way as Reverse
Resolution Protocol (RARP). However, instead of returning the
address of the MH, it will return multicast group address of the
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
to report, query, and inform their router counterparts about
geographical service areas. The IGPSMP will also be used to
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
geographic service area of a router. This is needed
order to automatically respond to router failure or
router boot-up
o confirm service area - confirms that a router has
its service area
o geographical service area query - This message will be
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
query request. It contains a bounding closed
described using GPS coordinates which contains the
area for the router
o ping - This message is sent periodically to ascertain
the router is currently functioning properly. Usually
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
correctly. It is also sent immediately after a
boots
All of IGPSMP messages will be sent on an all-routers
address for a particular hierarchy level. The exact
address can be set in the router configuration file
Note that for the GPS-Multicast routing scheme, the time-to-
value of the service area reports will be varied in order to
the distribution of the information. In GPS-Multicast routing,
Imielinski & Navas Experimental [Page 24]
RFC 2009 GPS-Based Addressing and Routing November 1996
the multicast group membership for very large partitions will
distributed throughout the country. Smaller partition may only
distributed to neighbor routers
5. Working Without GPS
5a. Users Without GPS
Mobile users without GPS modules can still participate - though at
very reduced level. When an MH enters a cell, it can use an MARP
discover the local multicast group for that cell or atom. As
user roams from cell to cell, the mobile host can keep track of
current cell that the user is in and adds or drops the
groups pertaining to those cells. The user's GPS address can be
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
will be weak enough so that it will not penetrate walls. Each
beacon will have its own GPS-address associated with it which it
broadcast. When a mobile user enters a room, his MH will detect
beacon and read the beacon's GPS address. The GPS-address of the
will be set to the GPS-address of the beacon. The MH will then
this beacon's GPS address in order to perform any message
that it needs to do. Now the mobile user can have a GPS-
associated with him even though he is indoors and his GPS-module
useless
6. Application Layer
In this subsection we sketch a third solution which relies
heavily on the DNS
In the application layer solution the geographic information is
to the DNS which provides the full directory information down to
level of the IP address of each base station and its area of
represented as a polygon of coordinates
A new first level domain - "geographic" is added to the set of
level domains. The second level domain names include states,
third, counties and finally, the fourth: polygons of coordinates,
so called points of interests. We can also allow, polygons to
as elements of second, third domains to enable sending messages
larger areas
Imielinski & Navas Experimental [Page 25]
RFC 2009 GPS-Based Addressing and Routing November 1996
Thus a typical geographic address can look
city-hall-Palo-Alto.San-Mateo-County.California.
Polygon.San-Mateo-County.California.
where Polygon is a sequence of coordinates
This geographic address is resolved in a similar way as the
domain addresses are resolved today into a set of IP addresses
base stations which cover that geographic area. There are
possibilities here
a. A set of unicast messages is sent to all base
corresponding to the IP addresses returned by the DNS. Each
station then forwards the message using either of the two last
solutions: application level or network level filtering
b. All the base stations join the temporary multicast group for
geographic area specified in the message. In this way we may
sending the same message across the same link several times. Thus
after the set of relevant base stations is determined by the DNS,
temporary multicast group is established and all packets with
multicast address are sent on that multicast address
c. Only one, central to the polygon base station is returned by
DNS just as in the IP unicast solution. However that "central"
station will have to forward messages to the other base
within the polygon
Notice that we should distinguish between "small area" and "
area" geographic mail. The "small area" mail will be most common
will most likely involve just one base station, favoring a
form of solution (a).
7.
Should the geographic messages be acknowledged
Since we have no control if users are present in the
geographic area where the mail is distributed we do not see a
for individual acknowledgments from the message recipients. However
we believe that the base stations (MSS) covering the target area
geographic mail should acknowledge the messages
Imielinski & Navas Experimental [Page 26]
RFC 2009 GPS-Based Addressing and Routing November 1996
Typically only a few base stations will be involved since
we will not cover very broad geographic areas anyway. We assume
the base stations, additionally to forwarding the the messages
their wireless interfaces will buffer them, either to
multicast them (emergency response) or to provide them to users
just entered a cell and download the "emergency stack" of
for that area as a part of the service hand-off protocol
8. Security
Some method of determining who has permission to send messages to
large geographical area is needed. For instance, perhaps only
mayor of New York City has permission to send a message to all of
York City
9.
Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC 1112,
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
algorithm for intersecting convex polygons, Computer Graphics
Image Processing 19, 384-391 (1982).
J. Ioannidis, D. Duchamp, and G. Q. Maquire. IP-Based Protocols
Mobile Internetworking. Proc. of ACM SIGCOMM Symposium
Communication, Architectures and Protocols, pages 235-245,
(September, 1991).
10. Authors'
Tomasz Imielinski and Julio C.
Computer Science
Busch
Rutgers, The State
Piscataway,
08855
Phone: 908-445-3551
EMail: {imielins,navas}@cs.rutgers.
Imielinski & Navas Experimental [Page 27]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
