rfc2009.txt

来自「著名的RFC文档,其中有一些文档是已经翻译成中文的的.」· 文本 代码 · 共 1,486 行 · 第 1/5 页

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 incoming
   packet's Sender Id as a key into the hashed cache.  If this is not
   the first packet to arrive for this destination and if the timer on
   the hash table entry has not yet expired, then the hashed cache will
   return a list of all of the destination addresses to which copies of
   the packet must be sent.  Copies of the packet are sent to all of
   these destinations and the hash entry's time stamp is updated.

   If no hash table entry is found (i.e.- this is the first packet
   encountered for this destination address), then the normal geometry
   checking routine would take over.  A new cache entry is made
   recording all of the next-hop destination addresses of the GPScast.
   In this manner, if several other packets with the same GPS
   destination follow this first packet, the router can use the hash
   table to look-up the destination base stations instead of calculating
   it using geometry.

3c-iii.          Discovering A Router's Service Area

   When the router is initiated, it will consult its configuration file.
   One of the items it will find in the file will be the multicast
   address of the base station group to which all of its child base
   stations are members.  The router will join this group and then send
   out Service Area Query messages to this multicast group periodically
   to discover and to refresh its knowledge of its children base
   stations and the geographical areas serviced by them.

   Queries are issued infrequently (no more than once every five
   minutes) so as to keep the IGPSMP overhead on the network very low.
   However, since the query is issued using unreliable multicast
   datagrams, there is a chance that some base stations may not receive
   the query.  This is important in two cases: when a child node fails
   and when a router first boots up.  The case of a failed child node
   will be explained later.  However, when a router first boots up, it
   can issue several queries in a small amount of time in order to
   guarantee that base stations will receive the query and to,
   therefore, build up its knowledge about its child base stations
   quickly.

   Base stations respond to a Service Area Query by issuing a Service
   Area Report.  This report is issued on the same multicast group
   address that all of the base stations have joined.  The report
   contains the geographical service area of the base station.  In order
   to avoid a sudden congestion of reports being sent at the same time,
   each base station will initiate a random delay timer.  Only when the
   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 IP
   tunnel between it and the base station.  This tunnel will carry the
   GPScast packet traffic between the base station and the router.  Each
   responding base station and its geographic area of service will also
   be included in the router's geometric routing table as a possible
   destination for GPScast packets.  Any base station that does not
   respond for ten continuous Service Area Queries will be considered
   unreachable and will be dropped from the routing table.

3c-iv.         Hierarchical Router Structure and Multicast Groups

                       R5----------------------R6
                    /      \                /     \
                  R1---------R2           R3---------R4
                / | \      / | \        / | \      / | \
               b1 b2 b3   b4 b5 b6     b7 b8 b9 b10 b11 b12

   Figure 3: Two peer routers (R5 and R6) cooperatively servicing four
                   child routers (R1 - R4).

   For scalability purposes, a hierarchy of routers is used to transport
   messages from a sender to a receiver.  Each layer of peer routers
   would have its own multicast group address for the exchange of
   Service Area Queries and Reports between the peer routers.  However,
   routers in distinct subtrees need not know about the routers in other
   subtrees.  Therefore, multicast group addresses will also differ
   between hierarchy subtrees.  See figure 3.  For instance, routers R1
   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 multicast
   group and would know about each other.  However, routers R1 and R2
   would not know about R3 and R4, and vice versa.

   But how will the router know the location and number of its peer
   routers and who its parent router is?  As mentioned before, the
   router consults its configuration file upon start-up.  Included in
   this configuration file will be the the address of its parent router
   and the multicast group address that the peer routers will use.  This
   peer multicast group address will be used in the same manner as the
   base station multicast group address.  It will be used to send and
   receive Service Area Queries and Reports between the parent router
   and the peer routers.  There is only one difference.  When a router
   sends a Service Area Report, in addition to reporting its
   geographical service area, a router will include the multicast
   address of its children base stations.  The reason for this is
   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 Optimizations

   The optimization described here attempts to reduce the latency of a
   GPScast.  It does so by reducing the the number of hops a packet must
   traverse before finding its destination.  The intuition behind the
   idea is this:  instead of going to the parent router and then to the
   sibling, simply go to the sibling directly.  As an additional
   benefit, this method prevents the parent router from becoming a
   bottleneck or a point of failure in the routing scheme.

   In this optimization, when a router attempts to determine who will
   receive the GPS packet, it considers its peer routers as if they were
   also its children in the routing hierarchy.  This means that the
   router will consider its service area to be the union of the service
   areas of its children and its peer routers.  Also, when the
   destination polygon intersects the router's service area polygon, the
   router will forward a copy of the GPScast packet to any child or peer
   router whose geographic service area contains or touches the packet's
   GPS destination polygon.

   However, before it sends a copy of the packet to a peer router, it
   first finds the polygon:

                               P = D /\ S

   where D stands for the packet's destination GPS polygon, S is the
   polygon representing the service area of the peer router, and P is
   the polygon that represents the intersection of D and S.  The polygon
   P is substituted for the destination polygon D in the packet and only
   then is the packet forwarded to the peer router.  This is necessary
   because the peer router will be using that same routing algorithm.
   Therefore, if the peer router receives a packet with the original
   destination polygon D, it will also route copies of the packet to all
   of its qualifying peer routers causing a chain of packet copies being
   bounced back and forth.

3c-vi.          Router-Failure Recovery Scheme

   In the case of a router failure, the system should be able to route
   around the failed router and continue to service GPScast messages.
   The responsibility of detecting whether a router has failed or not
   falls to the parent router.  Using Figure 3 as an example router
   hierarchy, the parent router R5 periodically sends out Service Area
   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 Report
   message.  This message contains a polygon describing their service
   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, the
   parent router R5 will send a Set Service Area message to the child
   router, R2 telling it to assume responsibility for the base stations
   underneath the failed R1 router.  In this Set Service Area message,
   the parent router includes the multicast group address of R1's
   children.  The R2 router uses this multicast address to learn the
   service areas and IP addresses of R1's children.  The R2 router then
   issues a Service Area Report advertising its new enlarged service
   area responsibilities.  All peer and parent routers will then update
   their routing tables to include this new information.  When the
   failed router, R1, restarts, it will declare that it is alive and
   that it is again servicing its area.  All routers will then again
   update their routing tables.

   In the case that there is no parent router, such as at the top of the
   routing hierarchy, then each peer router will keep track of its
   neighbors.  If a neighbor router fails, then the first neighbor
   router to declare that it is taking over the base stations for the
   failed router will take responsibility.  The rest continues as
   before.

3c-vii.   Domain Name Service Issues

   Domain Name Servers (DNS) could be used to facilitate the use of GPS
   geographic addressing for sites of interest.  The aim is to describe
   specific geographic sites in a more natural and real-world manner
   using a postal-service like addressing method.  Essentially, the DNS
   would resolve a postal-service like address, such as
   City_Hall.New_York_City.New_York, into the IP address of the GPS
   router responsible for that site.  The GPS router would then route
   the message to all available recipients in the site.

   The DNS would be used when a message is sent using the

              site-code.city-code.state-code.country-code

   addressing scheme.  The DNS would evaluate the address in reverse
   starting with the country code, then the state code, etc.  This is
   the same method used currently by the IP DNS service to return IP
   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 Library

4a. GPS Address Library - SendToGPS()

   A library for GPS address routing will be constructed.  The main
   routines contained in this library will be the SendToGPS() and
   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 a
   filled GPS-Address structure with the following form:
   typedef _GPS-Address {
           enum { point, circle, polygon } type;
           char *mail-address;
           struct
           {
                   enum { North, South, West, East } dir;
                   int hours, minutes, seconds;
           } *points;

   } GPS-Address;

   and message and size specify the actual message and its size.  The
   SendToGPS() routine will take the GPS-addressed message, encapsulate
   it in an IP packet, and then send it as a normal IP datagram.  The
   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 the
   sender's process id, host IP address, and the center of the
   destination polygon.  The Actual Address would be one of the
   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  impossible
                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 an
   empty GPS-Address structure, and message and size specify message
   buffer and its size.