rfc2009.txt

来自「中、英文RFC文档大全打包下载完全版 .」· 文本 代码 · 共 1,486 行 · 第 1/5 页

   This is done as follows: the router (not necessarily the MSS based
   router) with the address S/C/x will only retain addresses about
   S'/0/0, S/C'/0 for S' and C' different from S and C and S/C/x for all
   x.  Thus, it will drop all the addresses of the form S'/C'/y for all
   S' different that S except those with C'=0 and y=0, as well as all
   the addresses of the form S/C'/y with C' different from C except
   those with y=0.  Hence, these addresses will not be forwarded any
   further either.

   Thus, notice that only the information coming from designated routers
   will be forwarded further away, since the non-designated routers are
   not allowed to join the multicast groups which correspond to the
   states and counties. Consequently, their multicast membership
   information will be not be propagated.

   In this way a router at S/C/x will not bother about specific
   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 not
   have to use all multicast addresses even within those assigned for
   geographic addresses.

   Notice also that all of this is flexible - if we have more multicast
   addresses available (IP v 6) we will get more precise addressing due
   to smaller atoms.

3a-iv.           GPS Routing

   Given a packet we always look for the "closest" match in the routing
   table. If there is a complete match we follow such a link, if not we
   follow the address with the x-part 0'd in (county address) if there
   is none with the county which agrees with the destination county than
   we look at the entry which agrees with the state part of the
   destination address.

3a-v.          DNS Issues

   How does the client find out the multicast address on which the
   packet is to be sent?  We assume that the local name server has the
   complete state/county hierarchy and that each county map can be
   provided possibly with the "grid" of atoms and partitions already
   clearly marked.

   Points of interests within a county can be attached multicast address
   just as atoms. Then a given base station would have to join multicast
   groups of the points of interests that it covers.

   The final stage is for the receiver to look at the polygon (point of
   interest) which is encoded in the body of the multicast packet and
   decide on the basis of its own GPS location if this packet is to be
   received or not. Doing it on the application layer simplifies many
   routing issues. There is a tradeoff, however, specially when we have
   very short S/C/x addresses and base stations which do not cover the
   given polygon in fact are reached unnecessarily.  This may happen and
   it needs to be determined what is the number of the multicast
   addresses which are necessary to reduce this "false" alarms to the
   minimum.

3a-vi.                Estimations

   Assume average cell size of, say, 2km x 2km and the average state
   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 since
   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 encode
   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 which
   is 1/64 of the total IP v4 multicast addressing space.

   With IPv6 we will have, of course, much more addressing space which
   we can use for the GPS multicast routing.

3b.  "Last Mile"  Routing

   Multicasting will be used for the last mile routing in both our
   solutions (i.e the one just discussed and the geometric routing
   solution described next), but in different ways.

3b-i.           Application Level Filtering

   The MSS will forward the geographic message on its wireless link
   under a multicast address. This multicast address will either be the
   same for all locations in the range of the MSS's cell or, there will
   be several addresses corresponding to atoms which intersect the given
   cell. Additionally, a complete GPS address (for example in the form
   of the polygon) will be provided in the body of the packet and the
   exact address matching will be performed on the application layer.
   The receiver, knowing its GPS position uses it to match against the
   polygon address. The GPS position can be obtained by the receiver
   either from the GPS card or, indoors, from the indoor base station
   which itself knows its GPS position as a part of configuration file.

3b-ii.          Multicast Filtering

   In multicast level filtering, the base station assigns a temporary
   multicast address to the addressing polygon in a message.  It will
   send out a directive on the cell's specially assigned multicast
   address. All mobile clients who reside in that cell are members of
   that special multicast group (one per MSS). The directive sent by the
   MSS will contain the pair consisting of  the temporary multicast
   address together with the polygon. To improve the reliability this
   message will be multicast several times. The clients, knowing their
   GPS positions will than join the temporary multicast groups if their
   current locations are within the advertised polygon.  The MSS will
   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 of
   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 the
   IP level. This solution introduces additional delay (needed to join



Imielinski & Navas            Experimental                     [Page 13]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   the temporary multicast group) but reduces the number of irrelevant
   packets received by the client. This especially important for very
   long messages.

3b-iii.         Computers on Fixed Networks

   Fixed-network computers should also monitor all of the mandatory
   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 the
   messages to the computers.  These base stations would have the same
   GPS-routing functionality as the mobile computer base stations.
   Their main difference would be that the mobile computer base stations
   would use radio frequencies to multicast their messages and the fixed
   network base stations use the local Ethernet or Token Ring network.

   The next scheme differs from the GPS multicast scheme described above
   only on the first leg of the route, from the sender to the MSS. The
   "last mile" from the MSS to the final destination will have the same
   options as described above.

3c.             Geometric Routing Scheme (GEO)

   The Geometric Routing Scheme (GEO) uses the polygonal geographic
   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 was
   first implemented.  That is, a virtual network which uses GPS
   addresses for routing will be overlayed onto the current IP
   internetwork.  We would accomplish this by creating our own GPS-
   address routers.  These routers would use tunnels to ship data
   packets between them and between the routers and base stations.

3c-i.           Routing Overview

   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 polygonal
   destination address and the body of the message.  The SendToGPS()
   routine will encapsulate the GPScast message in a UDP datagram and
   send it to the class E address 240.0.0.0.  Previously, the system
   administrator will have specified in the /etc/rc.local or /etc/rc.ip
   file a route command that will specify that packets with the address



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 GPS
   router.  This will have the effect of sending the datagram to the
   nearest GPS router.

   Before explaining how the GPS routers shuttle the GPScast message to
   its destination, an introduction to routers and their different parts
   is in order.  For scalability purposes, GPS routers are arranged in a
   hierarchical fashion.  Each layer would correspond to a distinct
   geographic area, such as a state or a city.  At the top would be
   country-wide routers in charge of moving messages from one end of the
   country to another.  At the bottom would be campus or department
   routers in charge of moving messages between the base stations.  See
   Figure 1.


                                   Country-Router(s)
                                   /              \
                           State-Router(s)
                           /             \
                     City-Router(s)
                      /      \
                Router        Router
               /  |   \      |    \
           Base  Base  Base   Base  Base

   Figure 1: Hierarchy of routers.

   A GPS router essentially consists of three parts: a service area
   table containing the geographic area serviced by the router and each
   of its hierarchical children, a hashed cache of previous actions, and
   a table containing the IP addresses of at least the router's children
   and the router's parent.  In the case of a bottom-layer campus
   router, the service area table will contain polygons describing the
   geographic reach of each child base station's cell.  The polygon
   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 the
   datagram off, thereby, leaving it with the original GPScast message.
   First the router must determine if it services any part of the area
   of the destination polygon.  To do this, the router finds the
   intersection between the destination polygon and the polygon
   describing the router's service area.  The polygon intersection
   algorithm used is described by O'Rourke in his paper, A New Linear
   Algorithm for Intersecting Convex Polygons.  This algorithm requires
   order N-squared time in the worst case.  If the intersection result
   is null, then the router simply sends the message to its parent
   router.



Imielinski & Navas            Experimental                     [Page 15]

RFC 2009            GPS-Based Addressing and Routing       November 1996


           ------ Destination Polygon
           | A  |
       --------------
       |   | B  |   | Router's Service Area Polygon
       --------------
           | C  |
           ------

   Figure 2: Polygon Difference

   However, if the result is not null, then the router does service the
   area described by the intersection polygon.  The router now subtracts
   its service area from the destination polygon and sends the rest to
   it's parent router.  This subtraction step is actually a by-product
   of the intersection algorithm.  Using the example in Figure 2, the
   destination polygon and the router's service area polygon intersect
   at the region labeled B.  Therefore, the router will subtract out the
   B section and send the remaining sections A and C to its parent
   router.

   Continuing with the example, the router now uses the intersection
   polygon B to to determine which base station (or stations) will
   receive the GPScast message.  The router finds the intersection
   between the region B and the polygon of each base station's cell.
   Those base station polygons which intersect the region B will be sent
   the GPScast message.  Processes on Mobile Hosts serviced by these
   base stations will now use the routine RecvFromGPS() to receive the
   GPScast message.

3c-ii.  Supporting Long-Duration GPScasts

   Most likely, there will be a need to support sending real-time
   continuous media to a GPS destination.  This continuous media could
   be an audio GPScast or a video GPScast.  This would require that
   jitter be reduced in order to minimize disturbing artifacts in the
   audio or video playback.  Continually checking the destination
   geometry of each packet would incur unnecessary delays and may
   promote jitter.

   Therefore, the router will keep a hashed cache of the latest GPScast
   packets and their destinations.  Each cache item will be hashed using
   the Sender Identification included in the header of GPScast messages
   as the key.  Each cache item will contain a time stamp and a list of
   the next hops for that GPScast.  When the time stamp exceeds a
   certain limit, then the cache item will be dropped.  The list of next
   hops is a list of the IP addresses of the base stations, peer
   routers, and parent router which are to receive a copy of the GPScast
   messages.