tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 6130

 
 
 

Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)

Part 4 of 4, p. 63 to 88
Prev RFC Part

 


prevText      Top      Up      ToC       Page 63 
Appendix A.  Address Block TLV Combinations

   The algorithm for generating HELLO messages in Section 11 specifies
   which 1-hop neighbor network addresses may be included in the Address
   Blocks, and with which associated Address Block TLVs.  These Address
   Block TLVs may have Type = LINK_STATUS or Type = OTHER_NEIGHB, or
   both.  Address Block TLVs with Type = LINK_STATUS may have three
   possible Values (Value = HEARD, Value = SYMMETRIC, or Value = LOST),
   and Address Block TLVs of TYPE = OTHER_NEIGHB may have two possible
   Values (Value = SYMMETRIC or Value = LOST).  When both Address Block
   TLVs are associated with the same network address only certain
   combinations of these Address Block TLV Values are necessary, and are
   the only combinations generated by the algorithm in Section 11.
   These combinations are indicated in Table 9.

   Cells labeled with "Yes" indicate the possible combinations that are
   generated by the algorithm in Section 11.  Cells labeled with "No"
   indicate combinations not generated by the algorithm in Section 11
   but that are correctly parsed and interpreted by the algorithm in
   Section 12.  The cell labeled with "No*" is actually inconsistent, it
   is handled by ignoring the Address Block TLV with Type =
   OTHER_NEIGHB, but SHOULD NOT be used.

   +----------------+----------------+----------------+----------------+
   |                |     Type =     |     Type =     |     Type =     |
   |                |  OTHER_NEIGHB  |  OTHER_NEIGHB, |  OTHER_NEIGHB, |
   |                |    (absent)    |     Value =    |  Value = LOST  |
   |                |                |    SYMMETRIC   |                |
   +----------------+----------------+----------------+----------------+
   | Type =         |       No       |       Yes      |       Yes      |
   | LINK_STATUS    |                |                |                |
   | (absent)       |                |                |                |
   | Type =         |       Yes      |       Yes      |       Yes      |
   | LINK_STATUS,   |                |                |                |
   | Value = HEARD  |                |                |                |
   | Type =         |       Yes      |       No       |       No*      |
   | LINK_STATUS,   |                |                |                |
   | Value =        |                |                |                |
   | SYMMETRIC      |                |                |                |
   | Type =         |       Yes      |       Yes      |       No       |
   | LINK_STATUS,   |                |                |                |
   | Value = LOST   |                |                |                |
   +----------------+----------------+----------------+----------------+

          Table 9: LINK_STATUS and OTHER_NEIGHB TLV Combinations

Top      Up      ToC       Page 64 
Appendix B.  Constraints

   Any process that updates the Local Information Base or the Neighbor
   Information Base MUST ensure that all constraints specified in this
   appendix are maintained.

   In each Local Interface Tuple:

   o  I_local_iface_addr_list MUST NOT be empty.

   o  I_local_iface_addr_list MUST NOT contain any duplicated network
      addresses.

   o  If I_manet = true, then I_local_iface_addr_list MUST NOT contain
      any network address that overlaps any network address in the
      I_local_iface_addr_list of any other Local Interface Tuple with
      I_manet = true, unless it is known that the corresponding MANET
      interfaces will always communicate with separate sets of MANET
      interfaces on other routers.

   In each Removed Interface Address Tuple:

   o  IR_local_iface_addr MUST NOT contain any network address that is
      in the I_local_iface_addr_list of any Local Interface Tuple.

   o  IR_local_iface_addr MUST NOT equal the IR_local_iface_addr of any
      other Removed Interface Address Tuple.

   In each Link Tuple:

   o  L_neighbor_iface_addr_list MUST NOT be empty.

   o  L_neighbor_iface_addr_list MUST NOT contain any network address
      that overlaps any network address in the I_local_iface_addr_list
      of any Local Interface Tuple or the IR_local_iface_addr of any
      Removed Interface Address Tuple.

   o  L_neighbor_iface_addr_list MUST NOT contain any duplicated network
      addresses.

   o  L_neighbor_iface_addr_list MUST NOT contain any network address
      which is in the L_neighbor_iface_addr_list of any other Link Tuple
      in the same Link Set.

   o  If L_HEARD_time has not expired, then there MUST be a Neighbor
      Tuple whose N_neighbor_addr_list contains
      L_neighbor_iface_addr_list.

Top      Up      ToC       Page 65 
   o  L_HEARD_time MUST NOT be greater than L_time.

   o  L_SYM_time MUST NOT be greater than L_HEARD_time (unless both are
      expired).

   o  L_quality MUST NOT be less than 0 or greater than 1.

   o  If L_quality >= HYST_ACCEPT, then L_pending MUST be false.

   o  If L_quality < HYST_REJECT, then L_status MUST be PENDING or LOST.

   o  L_pending MUST NOT be set to true if it is currently false.

   In each Neighbor Tuple:

   o  N_neighbor_addr_list MUST NOT contain any network address that
      overlaps any network address in the I_local_iface_addr_list of any
      Local Interface Tuple or the IR_local_iface_addr of any Removed
      Interface Address Tuple.

   o  N_neighbor_addr_list MUST NOT contain any duplicated network
      addresses.

   o  N_neighbor_addr_list MUST NOT contain any network address that is
      in the N_neighbor_addr_list of any other Neighbor Tuple.

   o  If N_symmetric is = true, then there MUST be one or more Link
      Tuples with:

      o  L_neighbor_iface_addr_list contained in N_neighbor_addr_list;
         AND

      o  L_status = SYMMETRIC.

   o  If N_symmetric is = false, then there MUST be one or more Link
      Tuples with:

      o  L_neighbor_iface_addr_list contained in N_neighbor_addr_list.

      All such Link Tuples MUST NOT have L_status = SYMMETRIC.  At least
      one such Link Tuple MUST have L_HEARD_time not expired.

   In each Lost Neighbor Tuple:

   o  NL_neighbor_addr MUST NOT overlap any network address in the
      I_local_iface_addr_list of any Local Interface Tuple or the
      IR_local_iface_addr of any Removed Interface Address Tuple.

Top      Up      ToC       Page 66 
   o  NL_neighbor_addr MUST NOT equal the NL_neighbor_addr of any other
      Lost Neighbor Tuple.

   o  NL_neighbor_addr MUST NOT be in the N_neighbor_addr_list of any
      Neighbor Tuple with N_symmetric = true.

   In each 2-Hop Tuple:

   o  There MUST be a Link Tuple associated with the same MANET
      interface with:

      o  L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list; AND

      o  L_status = SYMMETRIC.

   o  N2_2hop_addr MUST NOT overlap any network address in the
      I_local_iface_addr_list of any Local Interface Tuple or the
      IR_local_iface_addr of any Removed Interface Address Tuple.

   o  N2_2hop_addr MUST NOT be the N2_2hop_addr of any other 2-Hop Tuple
      in the same 2-Hop Set and with the same
      N2_neighbor_iface_addr_list.

   o  N2_2hop_addr MUST NOT be in the N2_neighbor_iface_addr_list of the
      same 2-Hop Tuple.

Appendix C.  HELLO Message Example

   HELLO messages are instances of [RFC5444] messages, and this protocol
   supports any combination of message header options and address
   encodings, enabled by [RFC5444] that convey the required information.
   As a consequence, there is no single way to represent how all HELLO
   messages look.  This appendix illustrates two HELLO message with
   similar content, the exact values included are explained in the
   following text.

   The HELLO message's four bit Message Flags (MF) field has value 7
   indicating that the message header contains hop limit, hop count, and
   message sequence number fields.  Its four bit Message Address Length
   (MAL) field has value 3, indicating addresses in the message have a
   length of four octets, here being IPv4 addresses.  The message is as
   transmitted, with a hop limit of 1 and a hop count of 0.  The overall
   message length is 45 octets.

   The message contains a Message TLV Block with content length 8 octets
   containing two Message TLVs, of types VALIDITY_TIME and
   INTERVAL_TIME.  Each uses a Message TLV with Flags octet (MTLVF)
   value 16, indicating that each has a Value, and each has a Value

Top      Up      ToC       Page 67 
   Length of 1 octet.  The Values included are time codes (as defined in
   [RFC5497]) representing the parameters H_HOLD_TIME and
   HELLO_INTERVAL, respectively.

   The message has a single Address Block containing 5 addresses.  The
   Address Block Flags octet (ABF) value 128 indicates an address Head
   but no address Tail, and no address prefixes.  The Head Length of 3
   octets indicates address Mid sections of one octet each (Mid 0 to Mid
   4).

   The following Address Block TLV Block (content length 14 octets)
   includes two Address Block TLVs.  The first is a LOCAL_IF Address
   Block TLV with Flags octet (ATLVF) value 80, which indicates that a
   single address, with index 0 (i.e., the address Head:Mid 0) is the
   single local interface address of this router (the one octet Value
   THIS_IF indicates that this address is of this interface).  The
   second is a LINK_STATUS Address Block TLV with Flags octet (ATLVF)
   value 52, which specifies the link status values of all reported
   neighbors in a single multivalue Address Block TLV that covers the
   addresses with indexes 1 to 4, inclusive.  The Address Block TLV
   Value Length of 4 octets indicates one octet per Value per address.
   The last four addresses thus are of neighbors, each an with
   associated link status: the first and second HEARD, the third
   SYMMETRIC, and the fourth LOST.

Top      Up      ToC       Page 68 
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     HELLO     | MF=7  | MAL=3 |      Message Length = 45      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Hop Limit = 1 | Hop Count = 0 |    Message Sequence Number    |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Message TLV Block Length = 8  | VALIDITY_TIME |  MTLVF = 16   |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Value Len = 1 | Value (Time)  | INTERVAL_TIME |  MTLVF = 16   |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Value Len = 1 | Value (Time)  | Num Addrs = 5 |   ABF = 128   |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Head Len = 3  |                     Head                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     Mid 0     |     Mid 1     |     Mid 2     |     Mid 3     |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     Mid 4     | Address TLV Block Length = 14 |   LOCAL_IF    |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |  ATLVF = 80   |   Index = 0   | Value Len = 1 |    THIS_IF    |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |  LINK_STATUS  |   ATLV = 52   | Strt Indx = 1 | Stop Indx = 4 |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | Value Len = 4 |     HEARD     |     HEARD     |   SYMMETRIC   |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     LOST      |
     +-+-+-+-+-+-+-+-+

   Note that this example is for illustrative purposes.  The essential
   information can be conveyed, more efficiently (assuming that the
   local interface address will be supplied by IP, and that the
   INTERVAL_TIME TLV is not needed) by the 29 octets:

Top      Up      ToC       Page 69 
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     HELLO     |0 0 0 0 0 0 1 1|0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1|
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0| VALIDITY_TIME |0 0 0 1 0 0 0 0|
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |0 0 0 0 0 0 0 1|0 1 1 0 0 1 0 0|0 0 0 0 0 1 0 0|1 0 0 0 0 0 0 0|
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |0 0 0 0 0 0 1 1|                     Head                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     Mid 1     |     Mid 2     |     Mid 3     |     Mid 4     |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1|  LINK_STATUS  |0 0 0 1 0 1 0 0|
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |0 0 0 0 0 1 0 0|     HEARD     |     HEARD     |   SYMMETRIC   |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     LOST      |
     +-+-+-+-+-+-+-+-+

   Note that the above example assumes that H_HOLD_TIME and C have their
   default values of 6 seconds and 1/1024 second, and thus result in a
   time code of 100 (hexadecimal 64).

Appendix D.  Flow and Congestion Control

   This protocol specifies one Message Type, the HELLO message.  The
   maximum size of a HELLO message is proportional to the size of the
   originating router's 1-hop neighborhood.  HELLO messages MUST NOT be
   forwarded.

   A router MUST report its 1-hop neighborhood in HELLO messages on each
   of its MANET interfaces at least each REFRESH_INTERVAL.  This puts a
   lower bound on the control traffic generated by each router in the
   network employing this protocol.

   A router MUST ensure that two successive HELLO messages sent on the
   same MANET interface are separated by at least HELLO_MIN_INTERVAL.
   (If using jitter, then this may be reduced to a mean minimum value of
   HELLO_MIN_INTERVAL - HP_MAXJITTER/2.)  Thus, this puts an upper bound
   on the control traffic generated by each router in the network
   employing this protocol.

Top      Up      ToC       Page 70 
Appendix E.  Interval and Timer Illustrations

   This informative appendix illustrates the relationship between
   message timers and intervals.  (The adjustments to this timing when
   using timing jitter, as defined in [RFC5148], are not shown.)

E.1.  HELLO Message Generation Timing

   Figure 1 illustrates a basic HELLO message schedule for a router, on
   a MANET interface, employing strictly periodic transmission of HELLO
   messages.  The router transmits a HELLO message each HELLO_INTERVAL.
   Each HELLO message contains all 1-hop neighbor network addresses of
   the router that are to be reported in any such HELLO message.  (The
   parameter REFRESH_INTERVAL, not shown, is in this example equal to
   the parameter HELLO_INTERVAL.)

   The router includes a VALIDITY_TIME TLV in each HELLO message,
   encoding the parameter H_HOLD_TIME, the duration for which
   information received in the HELLO message should be considered valid
   by receiving routers.  Receiving routers will, when recording the
   information received in the HELLO message, each use this for setting
   the L_HEARD_time, L_SYM_time and L_time elements of their
   corresponding Link Tuple, and the N2_time in the corresponding 2-Hop
   Tuple for each network address.  Only L_time is illustrated in
   Figure 1.

     H_HOLD_TIME:         |-----------------------------|   ...

     HELLO_INTERVAL:      |---------|---------|---------|   ...

     Time:             ---*---------*---------*---------*------>

                          ^         ^         ^         ^
                          |         |         |         |
         HELLO (a, b, c, d)         |         |         |
                                    |         |         |
                   HELLO (a, b, c, d)         |         |   ...
                                              |         |
                             HELLO (a, b, c, d)         |
                                                        |
                                       HELLO (a, b, c, d)

     L_time:              |-----------------------------|
                                    |--------------------   ...
                                              |----------   ...
                                                        |   ...

           Figure 1: HELLO Message Generation: Regular Schedule

Top      Up      ToC       Page 71 
   Figure 2 illustrates a message schedule similar to Figure 1, where
   the router announces its own presence more frequently by sending
   additional HELLO messages.  HELLO messages are still sent regularly,
   at a reduced interval defined by a new value of HELLO_INTERVAL.
   However, REFRESH_INTERVAL has not been reduced.  Each 1-hop neighbor
   network address included in these HELLO messages need be advertised
   only once within each REFRESH_INTERVAL.  Consequently, the additional
   HELLO messages due to the reduced value of HELLO_INTERVAL may
   therefore be empty.  (This is not the only allowed distribution of
   1-hop neighbor network addresses, they could, for example, be sent
   alternately a, b and c, d.)

     H_HOLD_TIME:         |-----------------------------|   ...

     REFRESH_INTERVAL:    |---------|---------|---------|   ...

     HELLO_INTERVAL:      |----|----|----|----|----|----|   ...

     Time:             ---*---------*---------*---------*------>

                          ^    ^    ^    ^    ^    ^    ^
                          |    |    |    |    |    |    |
         HELLO (a, b, c, d)    |    |    |    |    |    |
                               |    |    |    |    |    |
                        HELLO ()    |    |    |    |    |
                                    |    |    |    |    |
                   HELLO (a, b, c, d)    |    |    |    |
                                         |    |    |    |   ...
                                  HELLO ()    |    |    |
                                              |    |    |
                             HELLO (a, b, c, d)    |    |
                                                   |    |
                                            HELLO ()    |
                                                        |
                                       HELLO (a, b, c, d)

     L_time:              |-----------------------------|
                               |-------------------------   ...
                                    |--------------------   ...
                                         |---------------   ...
                                              |----------   ...
                                                   |-----   ...
                                                        |   ...

    Figure 2: HELLO Message Generation: Regular Schedule with Different
                    HELLO_INTERVAL and REFRESH_INTERVAL

Top      Up      ToC       Page 72 
   HELLO messages may also be sent in response to events.  The minimal
   interval between two successive HELLO message transmissions by a
   router is HELLO_MIN_INTERVAL, setting an upper bound of the HELLO
   message emission rate.  Hence, for each HELLO message transmission, a
   router must wait at least HELLO_MIN_INTERVAL before the next HELLO
   message transmission.  Similarly, the maximum interval between two
   successive HELLO message transmissions is HELLO_INTERVAL, setting a
   lower bound on the message transmission rate.  Hence, for each HELLO
   message transmission, the router must ensure that the next HELLO
   message transmission must not wait more than HELLO_INTERVAL.

   Figure 3 illustrates a message schedule similar to Figure 1, but with
   HELLO messages responding to events at maximum rate, i.e., with HELLO
   messages being sent each HELLO_MIN_INTERVAL.  Note that when a HELLO
   message is sent, it is assumed that the following messages may all be
   scheduled at an interval of HELLO_INTERVAL, and hence each HELLO
   message contains all 1-hop neighbor network addresses.  In each HELLO
   message in this example, a new 1-hop neighbor network address is
   added, reflecting the changes occurring since the last HELLO message
   was sent.  HELLO messages are sent at the maximum allowed rate in
   order to signal these changes as rapidly as possible.

Top      Up      ToC       Page 73 
     H_HOLD_TIME:         |-----------------------------|   ...

     HELLO_INTERVAL:      |---------|---------|---------|   ...

     HELLO_MIN_INTERVAL:  |----|----|----|----|----|----|   ...

     Time:             ---*---------*---------*---------*------>

                          ^    ^    ^    ^    ^    ^    ^
                          |    |    |    |    |    |    |
                   HELLO ()    |    |    |    |    |    |
                               |    |    |    |    |    |
                       HELLO (a)    |    |    |    |    |
                                    |    |    |    |    |
                         HELLO (a, b)    |    |    |    |
                                         |    |    |    |   ...
                           HELLO (a, b, c)    |    |    |
                                              |    |    |
                             HELLO (a, b, c, d)    |    |
                                                   |    |
                               HELLO (a, b, c, d, e)    |
                                                        |
                                 HELLO (a, b, c, d, e, f)

     L_time:              |-----------------------------|
                               |-------------------------   ...
                                    |--------------------   ...
                                         |---------------   ...
                                              |----------   ...
                                                   |-----   ...
                                                        |   ...

   Figure 3: HELLO Message Generation: Regular Schedule with Responsive
                                 Messages

   Figure 4 shows the same example as Figure 3, but with an increased
   REFRESH_INTERVAL, and showing partial HELLO messages that include
   only the necessary network addresses.

Top      Up      ToC       Page 74 
     H_HOLD_TIME:         |-----------------------------|   ...

     REFRESH_INTERVAL:    |-------------------|----------   ...
                               |-------------------|-----   ...
                                    |-------------------|   ...
                                         |---------------   ...
                                              |----------   ...
                                                   |-----   ...
                                                        |   ...

     HELLO_INTERVAL:      |---------|---------|---------|   ...

     HELLO_MIN_INTERVAL:  |----|----|----|----|----|----|   ...

     Time:             ---*---------*---------*---------*------>

                          ^    ^    ^    ^    ^    ^    ^
                          |    |    |    |    |    |    |
                   HELLO ()    |    |    |    |    |    |
                               |    |    |    |    |    |
                       HELLO (a)    |    |    |    |    |
                                    |    |    |    |    |
                            HELLO (b)    |    |    |    |
                                         |    |    |    |   ...
                                 HELLO (c)    |    |    |
                                              |    |    |
                                   HELLO (a, d)    |    |
                                                   |    |
                                        HELLO (b, e)    |
                                                        |
                                             HELLO (c, f)

     L_time:              |-----------------------------|
                               |-------------------------   ...
                                    |--------------------   ...
                                         |---------------   ...
                                              |----------   ...
                                                   |-----   ...
                                                        |   ...

   Figure 4: HELLO Message Generation: Regular Schedule with Responsive
        Messages and Different HELLO_INTERVAL and REFRESH_INTERVAL

Top      Up      ToC       Page 75 
   Figure 5 summarizes the overall relationship between the intervals
   governing HELLO message transmissions by a router.

     H_HOLD_TIME:         |------------------------------------|

     REFRESH_INTERVAL:    |----------------|

     HELLO_INTERVAL:      |----------|

     HELLO_MIN_INTERVAL:  |---|

     Time:             ----------------------------------------------->

                          ^   ^      ^     ^                   ^
                          |   |      |     |                   |
                          |   |      |     |           Time up to which
              HELLO message   |      |     |           received HELLO
              transmission    |      |     |           message content
                              |      |     |           is valid.
                              |      |     |
                              |      |     Time before which all
                              |      |     neighbor information must
                              |      |     be transmitted in HELLO
                              |      |     messages (one or more)
                              |      |
                              |      Latest time for next HELLO message
                              |      transmission
                              |
                              Earliest time for next HELLO message
                              transmission

               Figure 5: HELLO Message Generation Intervals

Top      Up      ToC       Page 76 
E.2.  HELLO Message Processing Timing

   Figure 6 illustrates the Link Set timers when receiving a HELLO
   message not including the network address of the receiving MANET
   interface.

     VALIDITY_TIME:    |--------------------------|

     L_time:           |--------------------------|

     L_HEARD_time:     |--------------------------|

     L_SYM_time:     *-| (i.e.,  expired)

     Time:          ---*-------------------------------->
                       ^
                       |
                HELLO () received

      Figure 6: HELLO Message Processing: Network Address Not Present

   Figure 7 illustrates the Link Set timers when, following the received
   HELLO message illustrated in Figure 6, a router receives a HELLO
   message including the network address (a) of the receiving interface
   with link status = HEARD (or SYM).

     VALIDITY_TIME:    |--------------------------|
                             |--------------------------|

     L_time:           |--------------------------|
                             |--------------------------|

     L_HEARD_time:     |--------------------------|
                             |--------------------------|

     L_SYM_time:     *-| (i.e.,  expired)
     L_SYM_time:             |--------------------------|

     Time:            -*-----*--------------------------------->
                       ^     ^
                       |     |
      HELLO () received      |
                             |
      HELLO (a:HEARD) received

        Figure 7: HELLO Message Processing: Network Address Present

Top      Up      ToC       Page 77 
   Figure 8 illustrates the Link Set timers when, following the received
   HELLO messages illustrated in Figure 7, a router receives a HELLO
   message including the network address (a) of the receiving interface
   with link status = LOST.

     VALIDITY_TIME:    |--------------------------|
                             |--------------------------|
                                   |--------------------------|

     L_time:           |--------------------------|
                             |--------------------------|
                                   |--------------------------|

     L_HEARD_time:     |--------------------------|
                             |--------------------------|
                                   |--------------------------|

     L_SYM_time:     *-| (i.e.,  expired)
                             |--------------------------|
                                 *-| (i.e.,  expired)

     Time:            -*-----*-----*--------------------------------->
                       ^     ^     ^
                       |     |     |
       HELLO () received     |     |
                             |     |
      HELLO (a:HEARD) received     |
                                   |
             HELLO (a:LOST) received

         Figure 8: HELLO Message Processing: Network Address Lost

E.3.  Other HELLO Message Timing

   There are three other timing parameters that are used by a router to
   control HELLO message generation and processing.

   Figure 9 illustrates the time, with duration L_HOLD_TIME, during
   which the appropriate network addresses of a formerly, but no longer,
   symmetric 1-hop neighbor, as connected by this MANET interface, are
   advertised as LOST using a LINK_STATUS TLV in HELLO messages on this
   MANET interface, thus allowing that 1-hop neighbor to update its Link
   Set accordingly.

Top      Up      ToC       Page 78 
     L_HOLD_TIME:   |----------------------------|

     Time:       ---*---------------------------------->
                    ^                            ^
                    |                            |
         Formerly symmetric 1-hop neighbor       |
         ceases to be symmetric on this          |
         MANET interface                         |
                                                 |
                      Time up to which network addresses of
                      this neighbor connected using this MANET
                      interface are advertised in HELLO
                      messages on this MANET interface
                      using a LINK_STATUS TLV, Value = LOST

       Figure 9: HELLO Message Generation: Advertisement of Formerly
         Symmetric 1-Hop Neighbor on This MANET Interface as Lost

   Figure 10 illustrates the time, with duration N_HOLD_TIME, during
   which all network addresses of a formerly, but no longer, symmetric
   1-hop neighbor, are advertised as LOST in HELLO messages on all MANET
   interfaces using an OTHER_NEIGHB TLV (if not also reported using a
   LINK_STATUS TLV) thus allowing all other symmetric 1-hop neighbors to
   update their 2-Hop Sets accordingly.

     L_HOLD_TIME:   |----------------------------|

     Time:       ---*---------------------------------->
                    ^                            ^
                    |                            |
         Formerly symmetric 1-hop neighbor       |
         ceases to be symmetric                  |
                                                 |
                      Time up to which network addresses of
                      this neighbor are advertised in HELLO
                      messages on all MANET interfaces
                      using an OTHER_NEIGHB TLV,
                      Value = LOST

      Figure 10: HELLO Message Generation: Advertisement of Formerly
          Symmetric 1-Hop Neighbor on Any MANET Interface as Lost

   Figure 11 illustrates the time, with duration I_HOLD_TIME, during
   which a formerly, but no longer, used local interface network address
   is excluded from being considered as a 2-hop neighbor network address
   (in order that a router is not recorded as its own 2-hop neighbor
   during that period).

Top      Up      ToC       Page 79 
     I_HOLD_TIME:      |----------------------------|

     Time:          ---*----------------------------------->
                       ^                            ^
                       |                            |
       Formerly used local interface                |
       network address ceases to be                 |
       assigned to a local interface                |
                                                    |
                               Time up to which this network
                               address is excluded from being
                               included in this router's 2-Hop Set

            Figure 11: Local Interface Removed Network Address

Appendix F.  Topology Pictures

   This appendix illustrates various examples of physical topologies, as
   well as how these are logically recorded by NHDP from the point of
   view of the router A.  This representation is a composite of
   information that would be contained within A's various Information
   Bases after NHDP has been running for sufficiently long time for the
   state to converge.

   Note that the examples given in this appendix are NOT exhaustive, but
   are selected to be illustrative of NHDP neighborhood representations
   of physical MANET topologies.

   The example topologies presented contain 3 physical routers A, B, and
   C.   Each of these routers has one or two distinct interfaces,
   denoted "top" and "bottom".  Each interface has one or two addresses,
   and symmetric connectivity between a pair of interfaces is
   illustrated by these being connected by a line.

   In all examples, the topology is described as it is recorded by NHDP
   in router A.

F.1.  Example 1: Standard Single Interface Topology

   In Figure 12, each router has a single interface, each with a single
   IP address.  This is the simplest possible network, and the resulting
   representation is given to the right in Figure 12.

Top      Up      ToC       Page 80 
         __________ __________
        |          |          |
       {1}        {2}        {3}
        |          |          |              {1}--------{2}--------{3}
     +--'--+    +--'--+    +--'--+
     |  A  |    |  B  |    |  C  |
     +-----+    +-----+    +-----+

         Figure 12: Standard Single Interface Topology (Left), and
                 Corresponding NHDP Representation (Right)

   The Local Information Set in A contains a single Local Interface
   Tuple that has an I_local_iface_addr_list of {1}.  This value is
   denoted with a {1} on the leftmost part of the resulting
   representation.

   The Interface Information Base has only one Link Set, which
   represents the "top" interface of A, or {1}.  This Link Set's only
   Link Tuple has an L_neighbor_iface_addr_list containing {2}; this
   corresponds to the dashed line from {1} to {2} to the right in
   Figure 12.  The 2-Hop Set contains a single 2-Hop Tuple, with
   N2_neighbor_iface_addr_list being {2} and N2_2hop_addr being {3};
   this corresponds to the dashed line from {2} to {3} to the right in
   Figure 12.

   The descriptions of the following examples in this appendix will be
   derived similarly, and use the same notational conventions.

F.2.  Example 2: Dual Addressed Interface on 1-Hop Neighbor

   In Figure 13, the network is identical to that in Example 1, except
   that the middle router, B, has two IP addresses on its single
   interface.

         __________ __________
        |          |          |
       {1}       {2,4}       {3}
        |          |          |              {1}-------{2,4}-------{3}
     +--'--+    +--'--+    +--'--+
     |  A  |    |  B  |    |  C  |
     +-----+    +-----+    +-----+

      Figure 13: Single Interfaces, with 1-Hop Neighbor B Having Two
      Addresses (Left), and Corresponding NHDP Representation (Right)

Top      Up      ToC       Page 81 
   The content of the Interface Information Base is in this case
   identical to Example 1, except that L_neighbor_iface_addr_list is
   {2,4} and N2_neighbor_iface_addr_list is {2,4}.

F.3.  Example 3: Dual Addressed Interface on 2-Hop Neighbor

   In Figure 14, the network is identical to that in Example 1, except
   that the rightmost router, C, has two IP addresses on its interface.

         __________ __________
        |          |          |
       {1}        {2}       {3,4}                             +----{3}
        |          |          |              {1}--------{2}---+
     +--'--+    +--'--+    +--'--+                            +----{4}
     |  A  |    |  B  |    |  C  |
     +-----+    +-----+    +-----+

      Figure 14: Single Interfaces, with 2-Hop Neighbor C Having Two
      Addresses (Left), and Corresponding NHDP Representation (Right)

   The content of the Interface Information Base is in this case
   identical to than in Example 1, except that the 2-Hop Set contains an
   extra 2-Hop Tuple with N2_neighbor_iface_addr_list being {2} and
   N2_2hop_addr being {4}.  These two 2-Hop Tuples are illustrated by
   the two lines from {2} to {3} and (2) to {4}, respectively.

F.4.  Example 4: Dual Addressed Interfaces

   In Figure 15, the network is identical to that in Example 1, except
   that all routers have two IP addresses on their interface.  The Local
   Information Base in router A is the same as in Example 1, except that
   I_local_iface_addr_list is {1,5}.

         __________ __________
        |          |          |
      {1,5}      {2,6}      {3,4}                             +----{3}
        |          |          |             {1,5}------{2,6}--+
     +--'--+    +--'--+    +--'--+                            +----{4}
     |  A  |    |  B  |    |  C  |
     +-----+    +-----+    +-----+

      Figure 15: Single interfaces, all routers having two addresses
           (left), and corresponding NHDP representation (right)

   The content of the Interface Information Base is in this case a
   combination of the Interface Information Bases from Examples 1, 2,
   and 3.

Top      Up      ToC       Page 82 
F.5.  Example 5: Dual Interface on 2-Hop Neighbor

   In Figure 16, all routers have a single IP address on each interface,
   and with the 2-hop neighbor having two interfaces.

         __________ __________
        |          |          |
       {1}        {2}        {3}                              +----{3}
        |          |          |              {1}--------{2}---+
     +--'--+    +--'--+    +-----+                            +----{4}
     |  A  |    |  B  |    |  C  |
     +-----+    +-----+    +-----+
                              |
                             {4}

       Figure 16: Single Addresses, with 2-Hop Neighbor C Having Two
     Interfaces (Left), and Corresponding NHDP Representation (Right)

   The Interface Information Base is identical to that in Example 3;
   NHDP does not distinguish topologically between this example and
   Example 3.

F.6.  Example 6: Dual interface on 1-Hop Neighbor

   In Figure 17, all routers have a single IP address on each interface,
   and with the 1-hop neighbor having two interfaces.

         __________
        |          |
       {1}        {2}                                  +-----+
        |          |                         {1}-------| {2} |------{4}
     +--'--+    +--'--+    +-----+                     | {5} |
     |  A  |    |  B  |    |  C  |                     +-----+
     +-----+    +-----+    +-----+
                   |          |
                  {5}        {4}
                   |__________|

       Figure 17: Single Addresses, with 1-Hop Neighbor B Having Two
     Interfaces (Left), and Corresponding NHDP Representation (Right)

   The Local Information Base is identical to that in Example 1.

   The Interface Information Base has only one Link Set containing one
   Link Tuple with L_neighbor_iface_addr_list being {2}.  The 2-Hop Set
   contains a single 2-Hop Tuple, with N2_neighbor_iface_addr_list being
   {2} and N2_2hop_addr being {4}.

Top      Up      ToC       Page 83 
   The Neighbor Information Base contains a Neighbor Set containing a
   single Neighbor Tuple, which represents router B, with
   N_neighbor_addr_list being {2,5}.  This entry is represented on the
   right of Figure 17 by boxing {2} with {5}.

   Note that router A does not have information indicating which of
   router B's interfaces is connected to router C.  However, router A
   knows that the address {4} (and thus router C) is reachable by using
   {2} as next hop.

F.7.  Example 7: Dual Interface on 1-Hop and 2-Hop Neighbors

   In Figure 18, all routers have a single IP address on each interface,
   and both the 1-hop and 2-hop neighbors have two interfaces.
   Furthermore, there are now two physical links between routers B and
   C, over distinct interface pairs.

         __________ __________
        |          |          |
       {1}        {2}        {3}                      +-----+   +----{3}
        |          |          |             {1}-------| {2} |---+
     +--'--+    +--'--+    +-----+                    | {5} |   +----{4}
     |  A  |    |  B  |    |  C  |                    +-----+
     +-----+    +-----+    +-----+
                   |          |
                  {5}        {4}
                   |__________|

    Figure 18: Single Addresses, with 1-Hop and 2-Hop Neighbors B and C
    Having Two Interfaces (Left), and Corresponding NHDP Representation
                                  (Right)

   The Local Information Base is identical to that in Example 1.

   The Link Set is identical to that in Example 6, and the 2-Hop Set
   contains, as in Example 5 (and similarly to Examples 3 and 4), two
   2-Hop Tuples representing the two links between routers B and C.

   Note that router A does not have information describing which of
   router B's interfaces is connected to which interfaces of router C,
   or even that the interfaces with addresses {3} and {4} are interfaces
   of the same router.  However, router A knows that the addresses {3}
   and {4} (and thus router C) are reachable using {2} as next hop.

Top      Up      ToC       Page 84 
F.8.  Example 8: Dual Interface Locally and on 1-Hop Neighbor

   In Figure 19, all routers have a single IP address on each interface,
   and both A and its the 1-hop neighbor B have two interfaces.
   Furthermore, there are now two physical links between routers A and
   B, over distinct interface pairs.

         __________ __________
        |          |          |                       +-----+
       {1}        {2}        {3}            {1}-------| {2} |--------{3}
        |          |          |                       | {5} |
     +--'--+    +--'--+    +-----+                    +-----+
     |  A  |    |  B  |    |  C  |
     +-----+    +-----+    +-----+                    +-----+
        |          |                                  | {2} |
       {6}        {5}                       {6}-------| {5} |--------{3}
        |__________|                                  +-----+

   Figure 19: Single Addresses, with Both A and 1-Hop Neighbor B Having
   Two Interfaces (Left), and Corresponding NHDP Representation (Right)

   The Local Information Set contains two Local Interface Tuples, with
   I_local_iface_addr_list of {1} and {6}, respectively.

   Each Interface Information Base's Link Set contains one Link Tuple,
   representing the links between {1} and {2}, and between {6} and {5},
   respectively.  The 2-Hop Set for interface {1} contains a single
   2-Hop Tuple, with N2_neighbor_iface_addr_list being {2} and
   N2_2hop_addr being {3}.  The 2-Hop Set for interface {6} contains a
   single 2-Hop Tuple, with N2_neighbor_iface_addr_list being {5} and
   N2_2hop_addr being {3}.

   The Neighbor Information Base contains a Neighbor Set containing a
   single Neighbor Tuple, which represents router B, with
   N_neighbor_addr_list being {2,5}.  This entry is denoted by boxing
   {2} with {5}.

Top      Up      ToC       Page 85 
F.9.  Example 9: Dual Interface on All Routers

   In Figure 20, all routers have a single IP address on each interface,
   and all routers have two interfaces.  Furthermore, there are now two
   physical links between A and B, over distinct interface pairs, and
   two physical links between B and C, also over distinct interface
   pairs.

         __________ __________
        |          |          |                       +-----+   +----{3}
       {1}        {2}        {3}            {1}-------| {2} |---+
        |          |          |                       | {5} |   +----{4}
     +--'--+    +--'--+    +-----+                    +-----+
     |  A  |    |  B  |    |  C  |
     +-----+    +-----+    +-----+                    +-----+
        |          |          |                       | {2} |   +----{3}
       {6}        {5}        {4}            {6}-------| {5} |---+
        |__________|__________|                       +-----+   +----{4}

    Figure 20: Single Addresses, with All Routers Having Two Interfaces
           (Left), and Corresponding NHDP Representation (Right)

   The Local Information Set is identical to that in Example 8.  The
   Interface Information Base for each interface in A is also identical
   to that in Example 8, except that an additional 2-Hop Tuple is
   present in each 2-Hop Set, each representing the link between router
   B and the interface of router C with address {4}.

   As in Example 7, router A does not have information describing which
   of router B's interfaces is connected to which interface of C, or
   even that the interfaces with addresses {3} and {4} are interfaces of
   the same router.  However, router A knows that the addresses {3} and
   {4} (and router C) are reachable by using {2} or {5} (depending on
   via which of its local interfaces) as next hop.

Top      Up      ToC       Page 86 
F.10.  Example 10: Dual Addressed Dual Interfaces on All Routers

   In Figure 21, all routers have two IP addresses on each interface,
   and all routers have two interfaces.  Furthermore, there are now two
   physical links between A and B, over distinct interface pairs, and
   two physical links between B and C, also over distinct interface
   pairs.

                                                                 +--{9}
         __________ __________                            +------|
        |          |          |                 +-----+   |      +--{10}
      {1,2}      {5,6}      {9,10}       {1,2}--|{5,6}|---+
        |          |          |                 |{7,8}|   |      +--{11}
     +--'--+    +--'--+    +-----+              +-----+   +------|
     |  A  |    |  B  |    |  C  |                               +--{12}
     +-----+    +-----+    +-----+
        |          |          |                                  +--{9}
        |          |          |                 +-----+   +------|
        |          |          |                 |{5,6}|   |      +--{10}
      {3,4}      {7,8}     {11,12}       {3,4}--|{7,8}|---+
        |__________|__________|                 +-----+   |      +--{11}
                                                          +------|
                                                                 +--{12}

     Figure 21: Dual Addresses, with All Routers Having Two Interfaces
           (Left) and Corresponding NHDP Representation (Right)

   This example is the combination of all the preceding examples in this
   appendix.  The Local Information Set in A contains Local Information
   Tuples for each of its interfaces, and each Interface Information
   Base contains in its Link Set a representation of links {1,2}-{5,6}
   or {3,4}-{7,8}, respectively.  The Neighbor Set (in the Neighbor
   Information Base) records the existence of router B and all of its
   addresses on all its interfaces, i.e., {5,6,7,8}.

   As in Example 9, each interface address of router C is represented in
   the 2-Hop Set of each Interface Information Base as a link from
   router B to each of these addresses.  Router A does not have
   information describing which of router B's interfaces is connected to
   which interface of C, nor that the addresses {9}, {10}, {11}, and
   {12} are addresses of the same router (or that some of these, such as
   {9} and {10}, are addresses on the same interface of the router).

Top      Up      ToC       Page 87 
F.11.  Example 11: Single Addressed Dual Interface Locally

   In Figure 22, all routers have a single interface, except for router
   A which has two.  Each of A's two interfaces has a link with the
   single interface of router B.  All interfaces have a single address.

         __________ __________
        |     _____|          |
       {1}   |    {2}        {3}             {1}--------{2}---------{3}
        |    |     |          |
     +--'--+ |  +--'--+    +-----+
     |  A  | |  |  B  |    |  C  |
     +-----+ |  +-----+    +-----+
        |    |
       {6}   |                               {6}--------{2}---------{3}
        |____|

      Figure 22: Single Addresses, with A Having Two Interfaces, Both
    Linked to the Single Interface of B (Left), and Corresponding NHDP
                          Representation (Right)

   This is similar to Example 8, except that the single address {2} also
   replaces the address {5}.  In particular, both Link Tuples (one in
   each Link Set, each in its corresponding Interface Information Base)
   have L_neighbor_iface_addr_list being {2}, the Neighbor Set (in the
   Neighbor Information Base) contains a single Neighbor Tuple with
   N_neighbor_addr_list being {2}, and both 2-Hop Tuples (one in each
   2-Hop Set, each in its corresponding Interface Information Base) have
   N2_neighbor_iface_addr_list being {2} and N2_2hop_addr being {3}.

Top      Up      ToC       Page 88 
Authors' Addresses

   Thomas Heide Clausen
   LIX, Ecole Polytechnique

   Phone: +33 6 6058 9349
   EMail: T.Clausen@computer.org
   URI:   http://www.ThomasClausen.org/


   Christopher Dearlove
   BAE Systems ATC

   Phone: +44 1245 242194
   EMail: chris.dearlove@baesystems.com
   URI:   http://www.baesystems.com/


   Justin W. Dean
   Naval Research Laboratory

   Phone: +1 202 767 3397
   EMail: jdean@itd.nrl.navy.mil
   URI:   http://pf.itd.nrl.navy.mil/