rfc2009.txt

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

   geographical area, it would be simpler to merely name the
   destination. This would be done by specifying "postal-like" address
   such as city_hall.Fresno.California.USA.

   For "ad hoc" specified areas such as, say a quad between 5th and 6th
   Avenue and 43 and 46 street in New York, the polygon addressing will
   be used.

   Unfortunately, we will not be able to assume that we have enough
   addressing space available in the IP packet addressing space to
   address all GPS squares. Instead we will propose a solution which is
   flexible in terms of the smallest GPS addressable units which we call
   atoms.  In our solution, a smaller available addressing space (in the
   IP packet) will translate into bigger atoms.  Obviously, we can use
   as precise addressing as we want to in the body of the geographic
   messages - the space limitations apply only to the IP addressing
   space.

   By a geographic address we mean an IP address assigned to a
   geographic area or point of interest.  Our solution will be flexible
   in terms of the geographic addressing space.

   Below, we will use the following two terms:

     o     Atoms: for smallest geographic  areas which have
           geographic address.

           Thus, atoms could be as small as GPS squares but could be
           larger

     o     Partitions: These are larger, geographical areas, which will
           also have a geographic address. A state, county, town etc.
           may constitute a partition. A partition will contain a number
           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 or
           latitude part of the GPS address by skipping one or more
           least significant digits

     o     A circle, centered in a specific GPS address with a
           prespecified radius.

     o     Irregular shapes such as administrative domains: states,
           counties, townships, boroughs, cities etc

   Partitions and Atoms (which are of course special atomic partitions)
   will therefore have geographic addresses which will be used by
   routers. Areas of smaller size than atoms, or of "irregular shape"
   will not have corresponding geographic addresses and will have to
   handled with the help of application layer.

3.      Routing

   Let us now describe the suggested routing schemes responsible for
   delivering a message to any geographical destination.

   We will distinguish between two legs of the connection from the
   sender to the receiver: the first leg from the sender to the MSS
   (base station) and the second leg from the MSS to the receiver
   residing in its cell.  Our two solutions will differ on the first leg
   of the connection and use the same options for the second leg, which
   we call "last mile".

3a.     GPS-Multicast Routing Scheme

   Here, we discuss the first leg of routing: from the sender to the
   MSS. We start with the multicasting solution.

   Each partition and atom is mapped to a multicast address. The exact
   form of this mapping is discussed further in this subsection.  We
   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 application
   level filtering for the geographic addressing.  The key idea here is
   to approximate the addressing polygon of the smallest partition which
   contains it and using the multicast address corresponding to that
   partition as the IP address of that message. The original polygon is
   a part of the packet's body and the exact matching is done on the
   application layer in the second leg of the route.

   How is the multicast routing performed?

3a-i.           Multicast Trees

   The basic idea for the first level of routing using multicast is to
   have each base station join multicast groups for all partitions which
   intersect its range.  Thus, MSS is not only aware of its own range
   but also has a complete information about system defined partitions
   which its range intersects. This information can be obtained upon MSS
   installation, from the geographic database stored as a part of DNS.

   If the proper multicast trees are constructed (using for example link
   state multicast protocol) than the sender can simply determine the
   multicast address of the partition which covers the original polygon
   he wants to send his message to, use this multicast address as the
   address on the packet and put the original polygon specification into
   the packet content.  In this way, multicast will assure that the
   packet will be delivered to the proper MSS.

   Example

   For instance the MSS in New Brunswick may have its range intersect
   the following atoms and partitions: Busch, College Avenue, Douglass
   and Livingston Campuses of Rutgers University (atoms), New Brunswick
   downtown area (atom), the Middlesex county partition and the NJ state
   partition. Each of these atoms and partitions will be mapped into a
   multicast address and the New Brunswick's MSS will have to join all
   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 from
   the DNS extended properly with relevant maps. He will specify the
   intended destination by drawing a polygon on the map which will be
   translated into the sequence of coordinates. In the same time the
   polygon will be "approximated" by the smallest partition which
   contains that polygon. The multicast address corresponding to that
   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 to



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 group
   (that is all MSS whose ranges intersect the given partition). Each
   such MSS now will follow the "last mile" routing which is described
   in detail, further in the proposal. Briefly speaking, the MSS could
   then multicast the message further on the same multicast address and
   the client will perform the final filtering o application layer,
   matching its location (obtained from GPS) with the polygon specified
   in the packet's body.  Other solutions based entirely on multicasting
   are also possible as described below.

   End_Example

   However, things cannot be as simple as described.  For such a large
   potential number of multicast groups if we build entire multicast
   trees, the routing tables could  be too large.  Fortunately it is not
   necessary to build complete multicast trees. Indeed, it in not
   important to know precise location of each atom in California, from a
   remote location, say in NJ.

   Thus, we modify our simple solution by implementing the following
   intuition:

   The smaller is the size of the partition (atom) the more locally is
   the information about that partition (atom) propagated.

   Thus, only multicast group membership for very large partitions will
   be propagated across the whole country.

   For example, a base station in Menlo Park, California can intersect
   several atoms ) and several larger  which cover Menlo Park, such say
   a partition which covers the entire San Mateo county, next which
   cover the entire California and finally next which may cover the
   entire west coast.  This base station will have to join multicast
   groups which correspond to all these rectangles. However, only the
   information about multicast group corresponding to the West Coast
   partition will be propagated to the East Coast routers.

   However, a simple address aggregation scheme in which only a "more
   significant portion" of address propagates far away would not work.
   Indeed, in this case a remote router, say in NJ, could have several
   aggregate links leading to California - in fact, in the worst case,
   all its links could point to California since it could have received
   a routing information to some location in California on any of those
   links.

   To avoid this, for each partition we distinguish one or a few MSS
   which act as designated router(s) for that partition.  For example,
   the California partition, may have only three designated routers, one



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 the
   routing entries from the designated routers would be aggregated into
   the aggregate address for California. Information coming from other
   city routers will simply be dropped and not aggregated at all. This,
   in addition to a standard selection of the shortest routes, would
   restrict the number of links which lead to an aggregate address.  In
   particular, when there is only one designated router per partition,
   there would only be one aggregate link in any router. This could lead
   to non-optimal routing but will solve the problem of redundant links.

   Even with a designated routers, it may happen that the same packet
   will arrive at a given base station more than once due to different
   alternative routes. Thus, a proper mechanism for discarding redundant
   copies of the same packet should still be in place.  In fact, due to
   the possible intersections between ranges of the base stations the
   possibility of receiving redundant copies of the same packets always
   exist and has to be dealt with as a part of any solution.

3a-ii.         Determining the geographic Multicast Addressing

   Here we describe more specifically, the proposed addressing scheme
   and the corresponding routing.

   The addressing will be hierarchical.  We will use the following
   convention - each multicast address corresponding to a partitions or
   an atoms will have the following format:

                            1111.GPS.S.C.x

   where GPS is the specific code corresponding to the geographic
   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 corresponding
   to the  "C part"  and "x part" of address.

   For example if GPS part is 6 bit,s which gives 1/64 of existing
   multicast addresses to the geographic addressing we have 22 bits
   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 types
   of partitions: states and counties.

   We will assume that the GPS network will consist of all base stations
   (MSS) in addition the rest of the fixed network infrastructure. The
   designated GPS routers however, will only be selected from the
   population of MSS.  Specifically, there will be state dedicated and
   county dedicated routers.

   The concept of the designation will be implemented as follows.  From
   the set of all MSS, only certain MSS will play a role of designated
   routers for county  and state partitions.  Non-designated MSS will
   only join multicast groups which correspond to the GPS atoms but not
   GPS partitions that they intersect. The MSS which is a designated
   router for a county partition will join the multicast group of the
   county in which it is located, but not the state. Finally the state
   designated router will also join the multicast address corresponding
   to the state it is located in.

3a-iii.  Building Multicast Trees

   We assume that each router has geographic information attached to it
   - in the same format as we use for multicast mapping, S/C/x - it
   encodes the atom that contains the router.

   The multicast tree is built by a router propagating its multicast
   memberships to the neighboring routers. A given router will only
   retain certain addresses though, to follow the intuition of not
   retaining a specific information which is far away.