RFC 6130
Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)
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
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.
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.
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
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.
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:
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.
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
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
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.
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.
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
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
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
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 LostE.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.
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).
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 AddressAppendix 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.
__________ __________ | | | {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)
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.
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}.
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.
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}.
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.
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).
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}.
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/