INTERNET-DRAFT Bhargav Bellur Richard G. Ogier Fred L. Templin SRI International 6 September 2001 Topology Broadcast based on Reverse-Path Forwarding (TBRPF) Status of This Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026 except that the right to produce derivative works is not granted. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract Topology Broadcast based on Reverse-Path Forwarding (TBRPF) is a proactive, link-state routing protocol designed for use in mobile ad-hoc networks. TBRPF has two modes: full topology (FT) and partial topology (PT). TBRPF-FT uses the concept of reverse-path forwarding to reliably and efficiently broadcast each topology update in the reverse direction along the dynamically changing broadcast tree formed by the min-hop paths from all nodes to the source of the update. TBRPF-PT achieves a further reduction in control traffic, especially in large, dense networks, by providing each node with the state of only a relatively small subset of the network links, sufficient to compute minimum-hop paths to all other nodes. In both the FT and PT modes, a node forwards an update only if the node is not a leaf of the broadcast tree rooted at the source of the update. In addition, in the PT mode, a node forwards an update only if it results in a change to the node's source tree. As a result, each node reports only changes to a relatively small portion of its source tree. Bellur, Ogier, and Templin Expires 6 March 2002 [Page i] INTERNET-DRAFT TBRPF 6 September 2001 Contents 1. Introduction ................................................... 1 2. Changes ........................................................ 2 3. TBRPF Terminology .............................................. 3 4. Applicability Section .......................................... 4 4.1. Networking Context ........................................ 4 4.2. Protocol Characteristics and Mechanisms ................... 5 5. Neighbor Discovery ............................................. 7 5.1. Overview .................................................. 7 5.2. Neighbor Table ............................................ 9 5.3. Configurable Parameters ................................... 10 5.4. Sending HELLO Messages .................................... 11 5.5. Processing a Received HELLO Message ....................... 11 5.6. Expiration of Timers ...................................... 12 6. Reliable Delivery to Neighbors ................................. 13 6.1. Reliable, Sequenced Delivery Using NACKs .................. 13 6.2. Reliable Delivery Using ACKs .............................. 14 7. TBRPF-PT ....................................................... 15 7.1. Conceptual Data Structures and Messages ................... 15 7.2. Operation of TBRPF-PT ..................................... 17 7.2.1. Computing the Source Tree ............................ 17 7.2.2. Generating Tree Updates .............................. 18 7.2.3. Updating Parents ..................................... 18 7.2.4. Sending NEW PARENT Messages .......................... 19 7.2.5. Processing TREE UPDATE Messages ...................... 19 7.2.6. Processing NEW PARENT Messages ....................... 19 7.2.7. Processing a New Neighbor ............................ 20 7.2.8. Processing a Lost Neighbor ........................... 21 7.2.9. Packet Forwarding .................................... 21 7.3. Pseudocode for TBRPF-PT ................................... 21 7.4. Configurable Parameters ................................... 24 8. TBRPF-FT ....................................................... 24 8.1. Conceptual Data Structures and Messages ................... 25 8.2. Operation of TBRPF-FT ..................................... 26 8.3. Pseudocode for TBRPF-FT ................................... 31 8.4. Configurable Parameters ................................... 35 9. Application of TBRPF In Mobile Ad-hoc Networks ................. 35 9.1. Data Link Layer Assumptions ............................... 36 9.2. Network Layer Assumptions ................................. 36 9.3. Automatic Address Resolution .............................. 36 10. TBRPF Packets and TBRPF Protocol Messages ..................... 37 10.1. TBRPF Packet Header ...................................... 38 10.2. TBRPF Packet Body ........................................ 40 11. IANA Considerations ........................................... 58 12. Security Considerations ....................................... 58 13. Implementation Status ......................................... 59 14. Patent Rights Statement ....................................... 59 15. Acknowledgments ............................................... 59 16. References .................................................... 59 Bellur, Ogier, and Templin Expires 6 March 2002 [Page ii] INTERNET-DRAFT TBRPF 6 September 2001 1. Introduction TBRPF is a proactive, link-state routing protocol designed for mobile ad hoc networks. It maintains optimal paths to all destinations at all times, unlike on-demand routing protocols. It does not require the periodic broadcast of topology information, unlike OLSR [18]. Instead, only differential changes in topology are reported in order to minimize overhead. TBRPF has two modes: full topology (FT) and partial topology (PT). TBRPF-FT uses the concept of reverse-path forwarding to reliably broadcast each topology update in the reverse direction along the dynamically changing broadcast tree formed by the min-hop paths from all nodes to the source of the update. Each node is thus provided with the state of each link in the network. Since the leaves of the broadcast tree rooted at a particular source do not forward updates originating from that source, a dramatic reduction in control traffic is achieved compared to link-state flooding (e.g., OSPF), as shown in simulations [7]. TBRPF-FT is recommended for sparse networks and when full topology information is needed (e.g., if multiple paths need to be computed to each destination). A previous version of TBRPF-FT (called just TBRPF) was presented in [1]. TBRPF-PT achieves a further reduction in control traffic, especially in large, dense networks, by providing each node with the state of only a relatively small subset of the network links, sufficient to compute minimum-hop paths to all other nodes. As in the FT mode, a node forwards an update only if the node is not a leaf of the broad- cast tree rooted at the source of the update. In addition, a node forwards an update only if it results in a change to the node's source tree (which provides min-hop paths to all other nodes). As a result, each node reports only changes to a relatively small portion of its source tree, in contrast to FTSP [7] and STAR [4], in which each node reports changes to its entire source tree. TBRPF-PT also allows the computation of *approximately* optimal paths (with the degree of approximation determined by a configurable param- eter), in order to achieve a further reduction in control traffic and scalability to networks having a large diameter. TBRPF-PT has some features in common with PTSP (Partial Tree Sharing Protocol) [7], which also has the property that each node reports changes to a small portion of its source tree. However, in PTSP, a node sends each update only to a subset of neighbors (the children with respect to the broadcast tree), whereas TBRPF-PT takes advantage of the broadcast nature of wireless networks by sending each update to *all* neighbors. Also PTSP does not allow path optimality to be traded off to reduce control traffic. (We note that PTSP allows the computation of shortest paths with respect to any metric, but control traffic is reduced significantly if min-hop paths are computed.) Bellur, Ogier, and Templin Expires 6 March 2002 [Page 1] INTERNET-DRAFT TBRPF 6 September 2001 The FT and PT modes of TBRPF use the same neighbor discovery protocol (TND). TND is a new protocol whose HELLO messages are much smaller than existing neighbor discovery protocols such as the one use by OSPF [17]. A HELLO message in TND contains only the IDs of nodes that have recently been heard but with which a 2-way link has not yet been established. In contrast, a HELLO message in OSPF contains the IDs of *all* neighbors, resulting in a much larger message, espe- cially in dense networks. The use of TND thus contributes to the efficiency of TBRPF. In addition, since HELLO messages are smaller, they can be sent more frequently, resulting in a faster response to topology changes. TBRPF can easily be extended to hierarchical routing, in which the network is divided into areas or clusters. However, in this paper we focus on flat (non-hierarchical) networks. Because TBRPF reduces update traffic dramatically compared to flooding, it can be used instead of hierarchical routing or in combination with hierarchical routing, to reduce update traffic more than is possible by using hierarchical routing alone. 2. Changes Major changes from version 01 to version 02: - The neighbor discovery protocol has been modified so that it is simpler and is independent of the routing protocol. - Sections 9 and 10 have been shortened considerably. - The IANA considerations section has been revised to bring it up to date with recent discussions on the MANET email list. Major changes from version 00 to version 01: - A partial-topology mode (TBRPF-PT) has been introduced to achieve a further reduction in control traffic in large, dense networks. - The neighbor discovery protocol has been improved significantly. - The unicast mode for transmitting TBRPF messages has been elim- inated: each TBRPF packet is now broadcast to all neighbors. If a message is to be processed by only a few neighbor nodes, their identities are included in the message. - All topology updates are now sent reliably to all neighbors using NACKs. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 2] INTERNET-DRAFT TBRPF 6 September 2001 - Two new configurable parameters, MIN_UPDATE_INTERVAL and MIN_FORW_UPDATE_INTERVAL, have been introduced to minimize fre- quent generation and forwarding of topology updates. - TBRPF-FT includes a new message type NEW PARENT REPLY, which is sent in response to one or more NEW PARENT messages. A single mes- sage is sent in response to multiple NEW PARENT messages that are received at about the same time. - A new packet formatting scheme is used that provides optimal pack- ing of TBRPF protocol elements with minimal insertion of header and null padding octets. A packet compression mechanism is included that eliminates all null padding octets when enabled. - Formats have been added for new TBRPF-FT and TBRPF-PT message types. Formats have been revised for some existing TBRPF-FT mes- sage types. - An implicit NARP mechanism has been provided for binding one or more IP addresses to a Router ID. - Optional checksum facilities have been provided for data integrity. 3. TBRPF Terminology The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [2]. The fol- lowing terms are also used to describe TBRPF: node A router that implements TBRPF, identified by a unique router ID (RID), also called a node ID. link A logical connection from one node to another, identified by a pair (u,v), where u and v represent nodes. Nodes u and v are called the "head" and "tail" of the link, respectively. A link is said to be bidirectional or 2-way if each node can receive messages from the other. A bidirectional link need not use the same interfaces or media in both directions. neighbor A node v is said to be a neighbor of node u if there is a bidirectional link (u,v) between them. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 3] INTERNET-DRAFT TBRPF 6 September 2001 topology The topology of the network is described by a graph G = (V, E), where V is the set of nodes u and E is the set of links (u,v) in the network. directed tree A subset of (directed) links (u,v) that does not contain any loops. The root of a directed tree is the only node u such that the tree contains no link whose tail is u. topology update or link-state update (LSU) A message or part of a message that reports a state change for one or more links. update source The node that originated a given topology update. broadcast tree A directed tree rooted at an update source that is used to broadcast topology updates in TBRPF-FT. parent The parent of a node i for an update source u is the next node on the computed minimum-hop path to node u. It is also the node preceding node i in the broadcast tree rooted at u. child The inverse of the parent relationship. A node j is a child of node i for source u if and only if node i is the parent of node j for source u. leaf A node is a leaf of the broadcast tree rooted at source u if it has no children for source u. source tree The directed tree computed by each node that provides shortest paths to all other nodes. Not the same as a broadcast tree. 4. Applicability Section This section describes the networking context and protocol charac- teristics of the TBRPF protocol as specified in the MANET Routing Protocol Applicability Statement [16]. 4.1. Networking Context TBRPF-PT is appropriate for large, dense networks, including networks with a large diameter, in which only min-hop routing is needed and Bellur, Ogier, and Templin Expires 6 March 2002 [Page 4] INTERNET-DRAFT TBRPF 6 September 2001 bandwidth or power is limited. Simulation experiments are needed to determine the range of network parameters, such as degree of mobility and number of communicating pairs, for which TBRPF-PT performs better than on-demand protocols. TBRPF-FT is appropriate for sparse networks, and when full topology information is useful, such as for computing multiple disjoint paths or paths subject to quality-of-service objectives and constraints. 4.2. Protocol Characteristics and Mechanisms * Does the protocol provide shortest path routes? Yes. * Does the protocol provide support for unidirectional links? (if so, how?) No. It uses only bidirectional links (as in 802.11). * Does the protocol require the use of tunneling? (if so, how?) No. * Does the protocol require using some form of source routing? (if so, how?) No. The protocol uses hop-by-hop routing. However, since the entire path is known, source routing can be used as an option. * Does the protocol require the use of periodic messaging? (if so, how?) Each node transmits a HELLO message periodically. Topology updates and other messages are transmitted only when the topology changes. * Does the protocol require the use of reliable or sequenced packet delivery? (if so, how?) The protocol provides reliable, sequenced delivery of topology updates using NACKs. It also provides reliable delivery of other messages using ACKs. * Does the protocol provide support for routing through a multi- technology routing fabric? (if so, how?) Yes. Each network interface is assigned a unique IP address. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 5] INTERNET-DRAFT TBRPF 6 September 2001 * Does the protocol provide support for multiple hosts per router? (if so, how?) Yes. The concept of a Router ID (RID) [3,14,17] can be used to associate multiple hosts with a single RID. * Does the protocol support the IP addressing architecture? (if so, how?) Yes. * Does the protocol require link or neighbor status sensing (if so, how?) Yes. A new, efficient neighbor discovery protocol is presented, in which each HELLO message contains only the IDs of nodes that have recently been heard but with which a 2-way link has not yet been established. * Does the protocol depend on a central entity? (if so, how?) No. * Does the protocol function reactively? (if so, how?) The protocol reacts to topology changes, but not to traffic demand. * Does the protocol function proactively? (if so, how?) Yes. It maintains optimal paths to all reachable destinations at all times. * Does the protocol provide loop-free routing? (if so, how?) Yes. Since routing is based on link states, it provides loop-free routing when the topology is stable. * Does the protocol provide for sleep period operation? (if so, how?) TBRPF (FT and PT) operates correctly even if nodes can go into and out of sleep mode at arbitrary times. Other features can be added, such as assigning awake routers to store packets for sleep- ing nodes, and determining when a node can go into sleep mode without partitioning the network. * Does the protocol provide some form of security? (if so, how?) No. Other other protocols (such as IMEP [14]) can be used to pro- vide security. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 6] INTERNET-DRAFT TBRPF 6 September 2001 * Does the protocol provide support for utilizing multi-channel, link-layer technologies? (if so, how?) Yes. A network using multiple radio channels can be represented by a single logical topology in which any link can use any channel or combination of channels. 5. Neighbor Discovery This section describes the TBRPF Neighbor Discovery (TND) protocol. TND is designed to be independent of the routing protocol, so that it allows much flexibility in the design of the routing protocol that uses it. The purpose of the protocol is to allow each node in the network to quickly detect the neighboring nodes with which the node has a direct, bidirectional (2-WAY) link, i.e., a link such that the node at each end of the link can hear the other node. The protocol also detects when a bidirectional link to some neighbor no longer exists. It also provides the reliable reporting of changes in the up/down status of local links (i.e., links to neighbors) to all current neighbors. The reporting of the status of local links to *new* neighbors is done by the routing protocol. The key feature of TND is that it uses "differential" HELLO messages which report only *changes* in the status of neighbors, resulting in HELLO messages that are much smaller than those of other link-state routing protocols such as OSPF. 5.1. Overview Each node sends a HELLO message periodically every HELLO_INTERVAL seconds, possibly with a small jitter. Each HELLO message contains three (possibly empty) lists of router IDs, formatted as the follow- ing three (sub)message types: NEIGHBOR REQUEST, NEIGHBOR UP, and NEIGHBOR DOWN. A NEIGHBOR REQUEST message is always included in a HELLO, even if its list of router IDs is empty. However, a NEIGHBOR UP or NEIGHBOR DOWN message is included only if its list of router IDs is nonempty. Each HELLO message also contains the current HELLO sequence number (HSEQ), which is incremented with each transmitted HELLO. For con- venience, we say that "node i sends a NEIGHBOR REQUEST message for node j" if node i sends such a message that includes the ID of node j, and similarly for NEIGHBOR UP and NEIGHBOR DOWN messages. The NEIGHBOR REQUEST message includes a list of neighbors from which HELLO messages have recently been heard but for which a 2-WAY link is not currently established. To avoid establishing a link that is likely to be short lived, a node i must receive at least 2 of the last NBR_HOLD_COUNT (typically 3) HELLOs from another node j before Bellur, Ogier, and Templin Expires 6 March 2002 [Page 7] INTERNET-DRAFT TBRPF 6 September 2001 sending a NEIGHBOR REQUEST message for node j. In this case, node i sends a NEIGHBOR REQUEST message for node j in each of its next NBR_HOLD_COUNT (typically 3) HELLO messages, or until a NEIGHBOR UP message for node i is received from node j. The NEIGHBOR REQUEST message also informs the other neighbors that the link to node j is currently down, equivalent to a NEIGHBOR DOWN. (This fact is important if a NEIGHBOR DOWN is sent less than NBR_HOLD_COUNT times because the state changed to 1-WAY.) The sequence number HSEQ is used to determine whether another node may have sent a NEIGHBOR REQUEST that was missed, as follows. If node i has declared node j to be 1-WAY, but receives no HELLO from node j within NBR_HOLD_TIME seconds, or receives a HELLO whose HSEQ indicates that at least NBR_HOLD_COUNT HELLOs were missed, then node i declares node j to be LOST. This technique makes it unnecessary for a node to include each 1-WAY neighbor in HELLOs indefinitely, unlike OSPF and OLSR. If node j receives a NEIGHBOR REQUEST from node i, then node j declares the link to node i to be 2-WAY (if it is not already 2-WAY), and includes a NEIGHBOR UP message for node i in its next NBR_HOLD_COUNT transmitted HELLO messages. Upon receiving the NEIGH- BOR UP message, node i declares the link to node j to be 2-WAY and sends a NEIGHBOR UP message for node j in its next NBR_HOLD_COUNT transmitted HELLO messages. The NEIGHBOR UP message informs all current neighbors (not just the new neighbor) of the new link. (The procedure for reporting local links to new neighbors is separated from the neighbor discovery protocol, to allow the latter to be independent of the specific routing protocol or the protocol mode, e.g., periodic vs. differential updates.) It is possible that node i does not receive the NEIGHBOR UP message sent by node j, and therefore does not declare the link (i,j) to be 2-WAY, even though node j has declared the reverse link (j,i) to be 2-WAY. To correct this situation, if node j does not receive a NEIGHBOR UP message (for node j) from node i within NBR_HOLD_TIME seconds after the last time it transmitted a NEIGHBOR UP message for node i, then node j declares the link to node i to be 1-WAY (unless the link is declared LOST as described below), and sends a NEIGHBOR DOWN message for node i in its next NBR_HOLD_COUNT transmitted HELLO messages (unless the link becomes 2-WAY again before these transmis- sions are complete). We next describe events that cause a 2-WAY neighbor to be declared LOST or HEARD. If node i receives a NEIGHBOR DOWN from a 2-WAY node j for the reverse link (j,i), or receives a HELLO whose HSEQ indi- cates that at least NBR_HOLD_COUNT HELLOs were missed, then node i changes the status of node j to HEARD. If node i receives no HELLO from a 2-WAY node j within NBR_HOLD_TIME seconds, then node i changes the status of node j to LOST. In either case, node j sends a Bellur, Ogier, and Templin Expires 6 March 2002 [Page 8] INTERNET-DRAFT TBRPF 6 September 2001 NEIGHBOR DOWN message for node i in its next NBR_HOLD_COUNT transmit- ted HELLO messages (unless the link changes state before these transmissions are complete). In this manner, both nodes will agree that the link is no longer bidirectional, even if node j can still hear HELLOs from node i. Note that since HELLO messages report only *changes* to neighbor states, these messages will typically be much smaller than those of OSPF, in which each HELLO message includes the IDs of *all* neigh- bors. Therefore, a HELLO message will usually be small enough to fit into a single packet without fragmentation, assuming that each node does not have more than a few hundred neighbors. The NEIGHBOR REQUEST, NEIGHBOR UP, and NEIGHBOR DOWN messages all have the following format, where HSEQ is used only for NEIGHBOR REQUEST. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TYPE |P|L| N (# RIDs) | HSEQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ A HELLO message is a concatenation of a NEIGHBOR REQUEST message, a NEIGHBOR UP message, and a NEIGHOBR DOWN message, where each of the last two messages is omitted if its list of router IDs is empty. 5.2. Neighbor Table Each node maintains a neighbor table, which stores state information for each known neighbor. The entry for neighbor j contains the fol- lowing variables: nbr_level(j) - The current level (or status) of the link to node j, which can be LOST, HEARD, 1-WAY, or 2-WAY. nbr_life(j) - The amount of time (in seconds) remaining before nbr_level(j) must be changed to LOST if no further HELLO message from node j is received. Set to NBR_HOLD_TIME whenever a HELLO is received from node j. nbr_hseq(j) - The last value of HSEQ received from node j. Used to determine the number of HELLOs have been missed. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 9] INTERNET-DRAFT TBRPF 6 September 2001 nbr_count(j) - The number of times a NEIGHBOR REQUEST/UP/DOWN mes- sage has been sent for node j since nbr_level(j) has changed. nbr_wait_time(j) - The amount of time (in seconds) remaining before the link to node j must be declared down if a NEIGHBOR UP (for node i) is not received from node j. The table entry for a neighbor j may be deleted at any time after NBR_HOLD_TIME seconds after nbr_level(j) becomes LOST. (It is kept while the NEIGHBOR DOWN for node j is being transmitted.) The absence of an entry for a given node j is equivalent to an entry with nbr_level(j) = LOST. The four possible values of nbr_level(j) at node i have the following meaning: LOST No HELLO message has been received from node j within the last NBR_HOLD_TIME seconds. HEARD A HELLO message has been received from node j within the last NBR_HOLD_TIME seconds, but the link is not 1-WAY or 2-WAY. 1-WAY Two of the last NBR_HOLD_COUNT HELLOs from node j have been received, but the link is not 2-WAY. 2-WAY Node i has received from node j either a NEIGHBOR REQUEST or a NEIGHBOR UP from node j, and no event has since occurred to change this status. A link that is 2-WAY is considered "UP" and may be included in periodic and/or differential update messages, depending on the rout- ing protocol. 5.3. Configurable Parameters This section lists the parameters used in the description of the neighbor discovery protocol, and their proposed default values. HELLO_INTERVAL (1 seconds) NBR_HOLD_TIME (3 seconds) NBR_HOLD_COUNT (3) Bellur, Ogier, and Templin Expires 6 March 2002 [Page 10] INTERNET-DRAFT TBRPF 6 September 2001 5.4. Sending HELLO Messages Each node sends a HELLO message periodically every HELLO_INTERVAL seconds, possibly with a small jitter. Each HELLO message always includes a NEIGHBOR REQUEST message, even if its router ID list is empty. The NEIGHBOR REQUEST message includes the sequence number HSEQ, which is incremented each time a HELLO is sent. The HELLO mes- sage also includes a NEIGHBOR UP message if its router ID list is nonempty, and a NEIGHBOR DOWN message if its router ID list is nonempty. The contents of these three messages are determined by the following steps at node i: 1. For each node j such that nbr_level(j) = DOWN or HEARD and nbr_count(j) > 0, include node j in the NEIGHBOR DOWN message and decrement nbr_count(j). 2. For each node j such that nbr_level(j) = 1-WAY and nbr_count(j) > 0, include node j in the NEIGHBOR REQUEST message and decrement nbr_count(j). 3. For each node j such that nbr_level(j) = 2-WAY and nbr_count(j) > 0, include node j in the NEIGHBOR UP message and decrement nbr_count(j). 5.5. Processing a Received HELLO Message Upon receiving a HELLO message with sequence number HSEQ from node j, node i performs the following steps: 1. If a neighbor table entry does not exist for node j, create one with nbr_level(j) = LOST (temporarily) and nbr_count(j) = 0. 2. If nbr_level(j) = LOST, then set nbr_level(j) = HEARD. 3. Else if nbr_level(j) = HEARD and HSEQ - nbr_hseq(j) <= NBR_HOLD_COUNT: a. If node i does not appear in the NEIGHBOR REQUEST list, set nbr_level(j) = 1-WAY and nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR REQUEST will be sent). b. If node i appears in the NEIGHBOR REQUEST list, set nbr_level(j) = 2-WAY and nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR UP will be sent). 4. Else if nbr_level(j) = 1-WAY: a. If node i appears in the NEIGHBOR REQUEST list, then set nbr_level(j) = 2-WAY, nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR Bellur, Ogier, and Templin Expires 6 March 2002 [Page 11] INTERNET-DRAFT TBRPF 6 September 2001 UP will be sent), and nbr_wait_time(j) = 2 * NBR_HOLD_TIME (timer for receiving a NEIGHBOR UP from node j). b. Else if node i appears in the NEIGHBOR UP list, then set nbr_level(j) = 2-WAY and nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR UP will be sent). c. Else if HSEQ - nbr_hseq(j) > NBR_HOLD_COUNT, then set nbr_level(j) = HEARD and nbr_count(j) = 0. 5. Else nbr_level(j) = 2-WAY: a. If node i appears in the NEIGHBOR UP list and nbr_wait_time(j) > 0, then set nbr_wait_time(j) = 0. b. Else if node i appears in the NEIGHBOR DOWN list, then set nbr_level(j) = HEARD and nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR DOWN will be sent). c. Else if HSEQ - nbr_hseq(j) > NBR_HOLD_COUNT, then set nbr_level(j) = HEARD and nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR DOWN will be sent). d. Else if node i appears in the NEIGHBOR REQUEST list and nbr_count(j) = 0, then set nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR UP will be sent). 6. Set nbr_life(j) = NBR_HOLD_TIME and nbr_hseq(j) = HSEQ. 5.6. Expiration of Timers Upon expiration of the timer nbr_life(j), node i performs the follow- ing steps: 1. If nbr_level(j) = HEARD or 1-WAY, set nbr_level(j) = LOST and nbr_count(j) = 0 (no message is sent). 2. If nbr_level(j) = 2-WAY, set nbr_level(j) = LOST and nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR DOWN will be sent). Upon expiration of the timer nbr_wait_time(j), node i performs the following step: If nbr_level(j) = 2-WAY, set nbr_level(j) = HEARD and nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR DOWN will be sent). Upon receipt of a link-level failure indication for the link to node j, node i performs the following step: Bellur, Ogier, and Templin Expires 6 March 2002 [Page 12] INTERNET-DRAFT TBRPF 6 September 2001 If nbr_level(j) = 2-WAY, set nbr_level(j) = LOST and nbr_count(j) = NBR_HOLD_COUNT, and immediately send a NEIGHBOR DOWN for node j. 6. Reliable Delivery to Neighbors A TBRPF packet can contain multiple messages, some of which must be delivered reliably to some or to all neighbors. TBRPF uses NACKs to deliver topology updates reliably and in the correct order to all neighbors. Using NACKs results in less ACK/NACK overhead than using ACKs if links are mostly reliable. A message that is sent reliably using NACKs is called NACKable. Some messages, such as NEW PARENT messages, are sent reliably to one or more neighbors by requiring each intended recipient to send an ACK or another message in response. Such a message will be called ACK- able. The same TBRPF packet can contain NACKable and ACKable mes- sages, together with messages that do not require reliable delivery (e.g., HELLO, ACK). This section describes the procedures used by TBRPF to provide reliable delivery using NACKs and ACKs. 6.1. Reliable, Sequenced Delivery Using NACKs Each node maintains an 8-bit sequence number NSEQ, which is incre- mented whenever a packet is sent that contains one or more new NACK- able messages. Each NACKable message in a packet contains a sequence number which is the value of NSEQ when the message was first transmitted. Each TBRPF packet also contains the current value of NSEQ in its header, whether or not the packet contains any NACKable messages. This allows each neighbor to determine the sequence numbers of transmitted NACKable messages that it did not receive. For example, if a node i receives a TBRPF packet from node j that contains no NACKable messages and whose header contains NSEQ = 32, and if the node i has not yet received any NACKable message from node j with sequence number 32, then node i knows that it should have received a packet from node j containing one or more NACKable mes- sages with sequence number 32. Node i will then send a NACK message to node j requesting the retransmission of these NACKable messages. (Only the NACKable messages are retransmitted, not the entire packet.) NACKs and ACKs can be delayed (typically until the next HELLO is scheduled) to allow message aggregation, in order to minimize the number of packets transmitted. Thus, a single packet can contain NACKs for several neighbors and for several sequence numbers per neighbor. A NACK is retransmitted after RXMT_INTERVAL if no response is received. If a NACK for a given neighbor and sequence number is retransmitted MAX_NUM_RXMT times with no response, the link to the neighbor is declared down. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 13] INTERNET-DRAFT TBRPF 6 September 2001 Since since each TBRPF packet contains the latest value of NSEQ, each node will learn this value for each neighbor whenever it receives a HELLO message from the neighbor. Therefore, if node i sends a NACK- able message that is not received by neighbor node j, then node j will either detect the missed sequence number within NBR_HOLD_TIME seconds, or will declare the link to node i down. If node j detects the missed sequence number, it will send a NACK up to MAX_NUM_RXMT times every RXMT_INTERVAL seconds. Therefore, a node that has sent a NACKable message must store the message for NBR_HOLD_TIME + MAX_NUM_RXMT * RXMT_INTERVAL seconds for possible retransmission. 6.2. Reliable Delivery Using ACKs Each node maintains an 8-bit sequence number ASEQ, which is incre- mented whenever a packet is sent that contains one or more new ACK- able messages. Each ACKable message in a packet contains a sequence number which is the value of ASEQ when the message was first transmitted. The intended recipients of an ACKable message is determined from the contents of the message. For example, in TBRPF-PT a NEW PARENT mes- sage must be ACKed by the new parent (whose ID is included in the message) and the old parent (if it exists and is still a neighbor). The ACK message includes the neighbor's ID and the value of ASEQ in the received packet. A packet may contain multiple new ACKable mes- sages having the same sequence number, along with retransmitted ACK- able messages having older sequence numbers. A single ACK is used to acknowledge all ACKable messages having a given sequence number. An ACKable message is retransmitted after RXMT_INTERVAL seconds if an ACK for the message has not been received from each intended reci- pient that is still a neighbor. If the message contains a list of intended recipients, then the neighbors from which an ACK has been received may be removed from this list in the retransmitted message. If an ACK from an intended recipient is not received after the mes- sage is retransmitted MAX_NUM_RXMT times, the link to that neighbor is declared down. The message is discarded after an ACK has been received from each intended recipient that is still a neighbor. Since not all neighbors are required to receive each ACKable message, the above mechanism does not ensure sequenced delivery, which may or may not be required, depending on the protocol. Sequenced delivery can be achieved by including additional sequence information in each message, or by other means. A mechanism for ensuring that NEW PARENT messages are processed in the correct order is described in Section 7.2.4. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 14] INTERNET-DRAFT TBRPF 6 September 2001 7. TBRPF-PT TBRPF-PT is a proactive, link-state routing protocol that provides hop-by-hop routing along minimum-hop paths to each destination. Each node running TBRPF-PT computes a source tree (providing minimum-hop paths to all reachable nodes) based on partial topology information stored in its topology table, using a modification of Dijkstra's algorithm called Restricted Approximate Dijkstra (RAD). RAD is a modification of Dijkstra's algorithm that computes min-hop paths subject to restrictions that ensure correctness despite the fact that each neighbor is reporting only part of its source tree. Another feature of RAD is that it allows path optimality to be traded off in order to reduce the amount of control traffic in networks with a large diameter, where the degree of approximation is determined by the configurable parameter NONTREE_PENALTY. Each node computes the next node p(u) on the computed path to each destination (or update source) u, called the *parent* of the node for source u, and informs its parent of this selection by sending a NEW PARENT message, so that each parent becomes aware of its *children* for each source u. A link (u,v) in a node's source tree is defined to be *reportable* if the node has at least one child for source u. A node reports changes (additions and deletions) to the reportable portion of its source tree in TREE UPDATE messages, which are sent reliably to all neigh- bors using NACKs. In dense networks, most nodes will have no children for a given source; thus, on average, a node will report only a small portion of its source tree. When a node discovers one or more new neighbors (using TND), an UPDATE REPLY message is sent to inform the new neighbors of the reportable portion of the node's source tree. To minimize the number of packets transmitted, multiple control messages are aggregated into a single packet whenever possible. TBRPF-PT does not use per-source sequence numbers for updates (unlike TBRPF-FT), and does not require the periodic broadcast of topology updates (unlike OLSR). 7.1. Conceptual Data Structures and Messages In addition to the information required by the neighbor discovery protocol (Section 5) and for reliable, sequenced delivery (Section 6), each node running TBRPF-PT contains a topology table (TT) that stores information for each known link and node in the network. The following information is stored at node i for each known link (u,v) and node u: T(u,v) - Equal to 1 if (u,v) is in node i's source tree, and 0 Bellur, Ogier, and Templin Expires 6 March 2002 [Page 15] INTERNET-DRAFT TBRPF 6 September 2001 otherwise. The set of links in the source tree is denoted T. r(u,v) - The list of neighbors that are currently reporting link (u,v) in their source tree. The set of links reported by a given neighbor j is denoted T(j). (Each node reports only part of its source tree.) r(u) - The list of neighbors that are reporting for source u, i.e., that have at least one child for source u. p(u) - The current parent for source u, equal to the next node on the min-hop path to u. prev_p(u) - The last parent for source u that was confirmed. A new parent p(u) is confirmed when the list r(u) contains p(u). If the current parent is confirmed, then prev_p(u) = p(u). children(u) - The list of children for source u. pred(u) - The node preceding node u in node i's source tree. Equal to NULL if node u is not reachable. next(u) - The next node on the min-hop path to desination u, used for forwarding data packets. In the current version, next(u) is always equal to p(u). dist(u) - The number of hops on the shortest path to u. Each node also maintains the following information: N_i - the set of neighbors to which 2-way communication has been established via the neighbor discovery protocol. next_update_time - timer that specifies the earliest time the source tree may next be updated. update_flag - indicates whether the topology information has been modified since the source tree was last updated. TBRPF-PT uses the following message types, in addition to the HELLO, ACK, and NACK messages described in other sections. All messages are broadcast to all neighbors. Message formats are specified in Section 10.2. TREE UPDATE A message containing one or more updates of the form (u, v, ADD) (u, v, DEL), (u, ADD), and/or (u, DEL), reporting that a link (u,v) or a node u has been added to or deleted from the reportable part of the router's source tree. This is the only NACKable message type used by TBRPF-PT. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 16] INTERNET-DRAFT TBRPF 6 September 2001 NEW PARENT A message informing a neighbor that it has been selected as a parent for one or more sources. Contains the ID of the neighbor and a list of source nodes. UPDATE REQUEST A message requesting an UPDATE REPLY from one or more new neighbors. Contains a list of neighbor IDs. UPDATE REPLY A message describing the reportable part of the router's source tree to one or more new neighbors. Contains a list of neighbor IDs and updates of the form (u, v, ADD) and (u, ADD). 7.2. Operation of TBRPF-PT This section describes the operation of TBRPF-PT, with the aid of the pseudocode given in the next section. The main computation of TBRPF-PT occurs in the procedure Update_Source_Tree, which is called after a TREE UPDATE message is received, either immediately or delayed (typically until the next HELLO is scheduled) to allow mes- sage aggregation. The variables update_flag and next_update_time are used to determine whether an update has been received (update_flag = 1) and the next time that Update_Source_Tree should be executed if update_flag = 1. The parameter MIN_UPDATE_INTERVAL determines the minimum time between executions of Update_Source_Tree. However, Update_Source_Tree SHOULD be executed immediately if a failure notif- ication is received from the link layer. Update_Source_Tree first calls Restricted_Approx_Dijkstra (RAD), which computes the new source tree and new parents based on informa- tion stored in the topology table. Generate_Tree_Updates is then called to generate ADD and DELETE updates by comparing the new source tree to the old one. (As described below, some delete updates are implied.) Update_Parents is then called to generate NEW PARENT mes- sages for parents that have changed. Finally, the generated TREE UPDATE and NEW PARENT messages are sent. Whenever possible, these messages are aggregated with a HELLO message into a single packet, in order to minimize the number of transmitted packets. Each TBRPF packet is broadcast to all neighbors. TREE UPDATE mes- sages are delivered reliably to all neighbors using NACKs, as described in Section 6. NEW PARENT messages are delivered reliably to the new parent and old parent (if it exists) using ACKs. 7.2.1. Computing the Source Tree RAD is a modification of Dijkstra's algorithm that computes min-hop paths subject to the following "reporting neighbor restriction": a Bellur, Ogier, and Templin Expires 6 March 2002 [Page 17] INTERNET-DRAFT TBRPF 6 September 2001 link can belong to a path only if the second node of the path is a reporting neighbor for the link. This restriction ensures correctness and avoids routing loops. To allow immediate rerouting without having to wait for the new parent to report links on the new path to u, the reporting neighbor restriction is relaxed temporarily for links (u,v) leaving node u, when the parent p(u) changes to a neighbor that does not yet belong to r(u), i.e., that does not yet have any children for u. When a new parent belongs to r(u), it is said to be "confirmed", which implies that the new parent is a reporting neighbor for links (u,v) leaving node u. When a new parent p(u) is confirmed, prev_p(u) is set to p(u), as specified in the procedure Confirm_Parent. When NONTREE_PENALTY > 0, RAD computes paths that are approximately minimum hop, in exchange for reducing the number of tree updates gen- erated. This is accomplished by penalizing the addition of new links to the source tree. Using a positive value for NONTREE_PENALTY (e.g., 0.25) provides improved scalability for networks of large diameter. For each node u, RAD sets next(u) equal to the next node on the min- hop (or approximately min-hop) path to desination u. 7.2.2. Generating Tree Updates The procedure Generate_Tree_Updates compares the new source tree to the old source tree and generates ADD and DELETE updates. Updates are generated only for links (u,v) such that children(u) is not NULL. (In dense networks, children(u) will be NULL in most cases.) If such a link belongs to the new tree but not the old tree, then an ADD update (u, v, ADD) is generated. If such a link belongs to the old tree but not the new tree, then a DELETE update (u, v, DEL) is gen- erated only if node u is reachable (pred(u) is not NULL) and node v is not reachable via reportable links (pred(v) is NULL or children(pred(v)) is NULL). Otherwise, the DELETE update is implied by an ADD update. 7.2.3. Updating Parents The procedure Updating_Parents generates, for each neighbor j, a source list that, if nonempty, will be sent in a NEW PARENT message to that neighbor. The source list for neighbor j includes all sources u such that the new parent for source u is j and the old parent was not j. In addition, if the new parent belongs to r(u), then it is already confirmed, and Confirm_Parent is called. Other- wise, the parent p(u) will be confirmed when a TREE UPDATE is received from p(u) that contains either (u, ADD) or (u, v, ADD) for some v. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 18] INTERNET-DRAFT TBRPF 6 September 2001 7.2.4. Sending NEW PARENT Messages NEW PARENT messages are sent reliably using ACKs. A NEW PARENT mes- sage that is transmitted for the first time contains the current value of the sequence number ASEQ (see Section 6). A NEW PARENT mes- sage is retransmitted (with the same sequence number) after RXMT_INTERVAL seconds if an ACK is not received from both the new parent and the old parent (if it exists and is still a neighbor). If the source list is too large to include in a single packet (due to message size limitations), multiple NEW PARENT messages are sent, each having a different ASEQ value and a different source list. To ensure that NEW PARENT messages containing the same source are processed in the correct order, if the parent p(u) for some source u changes while a previously generated NEW PARENT message containing source u is still being retransmitted, then u is removed from the previously generated NEW PARENT message, and is included in a new NEW PARENT message having a larger sequence number. 7.2.5. Processing TREE UPDATE Messages All TREE UPDATE messages are processed by all neighbors. When a TREE UPDATE is received from a neighbor j, update_flag is set. For each add update (u, v, ADD) in the message, node j is added to r(u,v), and if node j is not already reporting for source u, node j is added to r(u) and Confirm_Parent(i,u) is called if j = p(u). In addition, since a source tree cannot contain two links entering the same node, the add update (u, v, ADD) implies a delete update (w, v, DEL) for any other link entering node v that is reported by node j. For each (explicit) delete update (u, v, DEL) in the message, node j is removed from r(u,v) and r(v), and from r(w) for all nodes w down- stream of v on the neighbor tree T(j). If the delete update is for the link (j,i) from the neighbor j sending the update, then link (i,j) is declared down. For each add source update (u, ADD) in the message, node j is added to r(u), and Confirm_Parent(i,u) is called if j = p(u). Finally, for each delete source update (u, DEL) in the message, node j is removed from r(u) and from r(w) for all nodes w downstream of u on the neigh- bor tree T(j). 7.2.6. Processing NEW PARENT Messages A NEW PARENT message is processed and ACKed by the new parent (whose ID is included in the message), and by the existing parent for any source u listed in the message. The new parent sends a TREE UPDATE in response to the message only if children(u) = NULL for some source u listed in the NEW PARENT message. In that case, the new parent Bellur, Ogier, and Templin Expires 6 March 2002 [Page 19] INTERNET-DRAFT TBRPF 6 September 2001 sends a TREE UPDATE (to all neighbors) containing the add update (u, v, ADD) for each such node u and for each node v such that (u,v) is on its source tree. The new parent also adds the sender of the NEW PARENT message to children(u) for each source u listed in the mes- sage. A node i that receives a NEW PARENT message from node j, but is not the new parent, processes the message as follows. For each source u listed in the message such that node j belongs to children(u) (i.e., node i is the existing parent of j for source u), node j is removed from children(u), and if this causes children(u) to be NULL, a delete source update (u, DEL) is sent, indicating that node i is no longer reporting for source u. 7.2.7. Processing a New Neighbor When a node i receives a 2-way indication (see Section 5) from a node j that does not belong to N_i, i.e., when node i sees its own ID in the neighbor request list of a HELLO message or in an UPDATE REQUEST message sent by node j, it adds node j to N_i, sets update_flag = 1, and sends an UPDATE REQUEST message to node j. The UPDATE REQUEST message can be delayed, typically until the next HELLO message is scheduled, to allow message aggregation. The UPDATE REQUEST is retransmitted every RMXT_INTERVAL seconds, up to MAX_NUM_RXMT times, until an UPDATE REPLY message is received. (As described in the neighbor discovery section, the link is declared down if no response is received.) The UPDATE REPLY message contains the IDs of neighbors that are being replied to, and describes the reportable part of the router's current source tree. I.e., for each source u such that children(u) is nonempty, it contains the set of links (u,v) in the source tree whose head node is u, or only the ID of node u if the source tree contains no links with head u. An UPDATE REPLY can be partial (due to message size limitations), in which case the P (partial) bit (defined in Section 10.2) is set and the information is sent in multiple packets having different sequence numbers. Each partial UPDATE REPLY must be ACKed by the neighbors listed in the message, and is retransmitted (removing the IDs of neighbors for which an ACK was received) after RXMT_INTERVAL seconds if an ACK has not been received by all listed neighbors. If the P bit is not set, then the UPDATE REPLY message need not be ACKed, since the listed neighbors that do not receive it will retransmit the UPDATE REQUEST. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 20] INTERNET-DRAFT TBRPF 6 September 2001 7.2.8. Processing a Lost Neighbor If any event occurs that results in a neighbor j being declared down (see Section 5.9), node i removes node j from N_i, removes j from children(u), and sets update_flag = 1. A TREE UPDATE reporting the deletion of link (i,j) from node i's source tree will be generated the next time Update_Source_Tree is executed. As stated above, Update_Source_Tree SHOULD be executed immediately if a failure notif- ication is received from the link layer. 7.2.9. Packet Forwarding TBRPF-PT forwards data packets on a hop-by-hop basis. At any node that is not the destination, an IP packet whose destination address is that of node u is forwarded to the node given by next(u). 7.3. Pseudocode for TBRPF-PT Update_Source_Tree(i){ Restricted_Approx_Dijkstra(i). Generate_Tree_Updates(i, tree_update). Update_Parents(i, src_list[]). If (tree_update is not empty) { Send tree_update to all neighbors. } For each neighbor k in N_i { Send New_Parent(src_list[k]) to node k. Set update_flag = 0. Set next_update_time = current_time + MIN_UPDATE_INTERVAL.}} Restricted_Approx_Dijkstra(i){ For each link (u,v) in T, set c(u,v) = 1. For each link (u,v) not in T, set c(u,v) = 1 + NONTREE_PENALTY. For each node v in TT { Set d(v) = infinity. Set pred(v) = NULL. Set new_p(v) = NULL.} Set d(i) = 0. Set S = {i} (labeled nodes). For each node j in N_i { Set d(j) = c(i,j). Set new_p(j) = j. } While there exists a node v in TT - S s.t. d(v) < infinity { Let u be a node in TT - S that minimizes (d(u), ID(u)). (Minimization is lexicographic.) Add u to S. For each node v s.t. (u,v) is in TT { If ([d(u) + c(u,v) < d(v) AND (new_p(u) or prev_p(u) is in r(u,v))] OR [d(u) + c(u,v) = d(v) AND Bellur, Ogier, and Templin Expires 6 March 2002 [Page 21] INTERNET-DRAFT TBRPF 6 September 2001 (new_p(u) is in both r(u,v) and r(v))]) Set d(v) = d(u) + c(u,v). Set pred(v) = u. Set new_p(v) = new_p(u).}} Set old_T = T and T = empty set. For each node u in TT { dist(u) = d(u). next(u) = new_p(u). Add (pred(u), u) to T. }} Generate_Tree_Updates(i, tree_update) { Set tree_update = empty. For each link (u,v) in TT s.t. children(u) != NULL { If (u,v) is in T but not in old_T { Add the update (u, v, ADD) to tree_update. } Else if ([(u,v) is in old_T but not in T] AND [pred(u) != NULL] AND [pred(v) = NULL OR children(pred(v)) = NULL]) { (Node v is not reachable using only reportable links.) Add the update (u, v, DEL) to tree_update. } If new_p(u) = NULL, remove (u,v) from TT. If r(u,v) is empty, remove (u,v) from TT. }} Update_Parents(i, src_list[]) { For each node j in N_i, set src_list[j] = empty. For each node u != i in TT { If (new_p(u) != p(u) AND new_p(u) != NULL) { Add u to src_list[new_p(u)].} Set p(u) = new_p(u). If (p(u) belongs to r(u) AND prev_p(u) != p(u)) { Confirm_Parent(i, u).}} Confirm_Parent(i, u){ Set prev_p(u) = p(u). For each neighbor j in N_i { For each node v s.t. (u,v) is in TT { If j is in r(u,v) - r(u), remove j from r(u,v).}}} Process_Tree_Update(i, j, tree_update) { (TREE UPDATE received from neighbor j.) Set update_flag = 1. For each add update (u, v, ADD) in tree_update { Add node j to r(u,v). If r(u) does not contain node j { Add node j to r(u). If (p(u) = j AND prev_p(u) != p(u)) { Confirm_Parent(i, u).}} For each w other than u such that r(w,v) contains j { Remove j from r(w,v). (Implicit delete update.) }} For each delete update (u, v, DEL) in tree_update { Remove node j from r(u,v) and r(v). Remove node j from r(w) for all nodes w downstream of v Bellur, Ogier, and Templin Expires 6 March 2002 [Page 22] INTERNET-DRAFT TBRPF 6 September 2001 on the neighbor tree T(j). If (u = j and v = i) { (Link (j,i) from neighbor failed.) Link_Down(i,j).}} For each add source update (u, ADD) in tree_update { Add node j to r(u). If (p(u) = j AND prev_p(u) != p(u)) { Confirm_Parent(i, u).}} For each delete source update (u, DEL) in tree_update { Remove node j from r(u) and from r(w) for all nodes w downstream of u on the neighbor tree T(j). }} Process_New_Parent(i, j, parent, src_list) { (NEW PARENT message received from neighbor j.) Set tree_update = empty. If (parent = i) { For each node u in src_list { If (children(u) = NULL) { If node u is a leaf of T { Add the update (u, ADD) to tree_update.} Else { For each v s.t. (u,v) is in T { Add the update (u, v, ADD) to tree_update.}}} Add j to children(u).}} If (parent != i) { For each node u in src_list { If (j is in children(u)) { Remove j from children(u). If (children(u) = NULL) { Add the update (u, DEL) to tree_update.}}}} If (tree_update is not empty) { Send tree_update to all neighbors. }} Process_Update_Requests(i, update_request_list) { Set update_reply = empty. For each neighbor j in update_request_list { Add the ID of node j to update_reply. } For each node u s.t. children(u) != NULL { If node u is a leaf of T { Add the update (u, ADD) to update_reply.} Else { For each v s.t. (u,v) is in T { Add the update (u, v, ADD) to tree_update.}}} Send update_reply.} Process_Update_Reply(i, j, update_reply) { If update_reply includes node i in the neighbor list { Set update_flag = 1. For each update (u, v, ADD) in tree_update { Add node j to r(u,v). Add node j to r(u). } Bellur, Ogier, and Templin Expires 6 March 2002 [Page 23] INTERNET-DRAFT TBRPF 6 September 2001 For each update (u, ADD) in tree_update { Add node j to r(u). }}} 7.4. Configurable Parameters This section lists the values of the parameters used in the descrip- tion of the protocol, and their proposed default values. HELLO_INTERVAL (2 seconds) NBR_HOLD_TIME (6 seconds) RXMT_INTERVAL (2 seconds) MAX_NUM_RXMT (3) MIN_UPDATE_INTERVAL (2 seconds) NONTREE_PENALTY (0.25) 8. TBRPF-FT Unlike TBRPF-PT, the full topology (FT) mode of TBRPF provides each node with the state of every link in the network. TBRPF-FT uses the concept of reverse-path forwarding to broadcast each link-state update in the reverse direction along the spanning tree formed by the minimum-hop paths from all nodes to the source of the update. That is, each link-state update is broadcast along the minimum-hop-path tree rooted at the source of the update, there being one tree per source. The broadcast trees are updated dynamically using the topology infor- mation that is received along the trees themselves, thus requiring very little additional overhead for maintaining the trees. Minimum- hop-path trees are used because they change less frequently than shortest-path trees based on a metric such as delay. Based on the information received along the broadcast trees, each node computes its parent and children for the broadcast tree rooted at each source u. Each node forwards updates originating from source u to its chil- dren on the tree rooted at source u. TBRPF-FT achieves reliability despite topology changes, using sequence numbers. The correctness of TBRPF-FT has been proven [1]. A node having no children for source u is a leaf and need not forward updates generated by u. In dense net- works, most nodes are leaves. In simulation experiments [7], TBRPF- FT generated up to 85% less update/control traffic than an efficient version of link-state flooding. Full-topology link-state protocols have the following advantages over partial-topology protocols: (1) alternate paths and disjoint paths Bellur, Ogier, and Templin Expires 6 March 2002 [Page 24] INTERNET-DRAFT TBRPF 6 September 2001 are immediately available, allowing faster recovery from failures and topology changes; and (2) paths can be computed subject to any combi- nation of quality-of-service (QoS) constraints and objectives. Exam- ples of partial-topology link-state protocols include STAR and OLSR. These protocols provide each node with sufficient topology informa- tion to compute at least one path to each destination. TBRPF-FT computes optimal routes based on the advertised link states; however, the advertised link states themselves may be approximate in order to reduce the frequency at which each link is updated. 8.1. Conceptual Data Structures and Messages A link-state update reporting the state of the link (u,v) is a tuple (u,v,c,sn), where c and sn are the cost and the sequence number asso- ciated with the update. A cost of infinity represents a failed link. We say that node u is the head node of link (u,v). It is the only node that can report changes to parameters of link (u,v). Therefore, any link-state update (u,v,c,sn) originates from node u. Each node i maintains a counter SN_i, which is incremented by at least one each time the cost of one or more outgoing links (i,v) changes value. For example, SN_i can be a time stamp that represents the number of seconds (or other units of time) elapsed from some fixed time. When node i generates a link-state update (i,v,c,sn), the sequence number sn is set to the current value of SN_i. We note that, unlike most link-state protocols, TBRPF does not require link- state updates to contain an age field. In addition to the information required by the neighbor discovery protocol (Section 5) and for reliable, sequenced delivery (Section 6), each node i running TBRPF-FT stores the following information: 1. A topology table, denoted TT_i, consisting of all link-states stored at node i. The entry for link (u,v) in this table is denoted TT_i(u,v) and consists of the most recent update (u,v,c,sn) received for this link. The components c and sn of the entry for link (u,v) will be denoted TT_i(u,v).c and TT_i(u,v).sn. TBRPF-FT can optionally support the dissemination of multiple link metrics, in which case the single cost c would be replaced by a vector of multiple metrics. 2. The list of neighbor nodes, denoted N_i. 3. The following is maintained for each node u not equal to i: a. The parent, denoted p_i(u), which is the neighbor of i that is the next node on the minimum-hop path from node i to node u, as obtained from TT_i. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 25] INTERNET-DRAFT TBRPF 6 September 2001 b. The state of the neighboring node nbr as a parent of node i with respect to node u, denoted pstate_i(u, nbr). pstate_i(u, nbr) can take on the values Null_Parent, Inactive_Parent, Pending_Parent, or Active_Parent. c. A list of children, denoted children_i(u). d. The sequence number of the most recent link-state update ori- ginating from node u received by node i, denoted sn_i(u). e. The routing table entry for node u, consisting of the next node on the preferred path to u. 4. The list of NEW PARENT and CANCEL PARENT messages, denoted ACK_i, sent to neighboring nodes for which a acknowledgment has not yet been received. We note that the routing table entry for node u can be equal to the parent p_i(u) if minimum-hop routing is used for data packets. How- ever, in general, the routing table entry for node u is not p_i(u), since the selection of routes for data traffic can be based on any objective. TBRPF-FT uses the following message types. Message formats are specified in Section 10.2. Link-State Update (LSU) A NACKable message containing one or more link-state updates (u,v,c,sn). NEW PARENT A message informing a neighbor that it has been selected as a parent with respect to one or more sources. NEW PARENT REPLY A message sent in response to a NEW PARENT message. CANCEL PARENT An ACKable message informing a neighbor that it is no longer a parent with respect to one or more sources. 8.2. Operation of TBRPF-FT This section describes the network-level operation of TBRPF-FT, with the aid of the pseudocode given at the end of the section. Examples illustrating the operation of TBRPF-FT and the the proof of correct- ness for TBRPF-FT can be found in [1]. For a given node u, the parents p_i(u) for all i not equal to u define a minimum-hop spanning tree rooted at u (assuming the protocol Bellur, Ogier, and Templin Expires 6 March 2002 [Page 26] INTERNET-DRAFT TBRPF 6 September 2001 has converged). The basic idea of TBRPF-FT is to broadcast link- state updates generated by u along this spanning tree, while at the same time modifying this tree based on the link-state information received along the tree. To simplify the presentation, we assume that the sequence number space is large enough so that wraparound does not occur. However, if a smaller space is used, wraparound can be handled by employing infrequent periodic updates with a period that is less than half the minimum wraparound period, and by using a cyclic comparison of sequence numbers: i.e., sn is considered less than sn' if either sn < sn' and their difference is less than half the largest possible sequence number, or sn' < sn and their difference is greater than half the largest possible sequence number. A node i selects a neighboring node nbr as the parent for source src by broadcasting a NEW PARENT(nbr, src, sn) message containing the identity of node src and the sequence number sn = sn_i(src). A node cancels an existing parent nbr' by broadcasting a CANCEL PARENT(nbr', src) message containing the identity of the source. Consequently, the set of children, children_i(src), at node i with respect to node src is the set of neighbors from which it has received a NEW PARENT(i, src, -) message. In general, a node will simultaneously select a neighboring node nbr as the parent for multiple sources, when it broadcasts a NEW PARENT(nbr, src_list, sn_list) message, where src_list is the list of sources and sn_list is the correspond- ing list of sequence numbers. Like the NEW PARENT message, a CANCEL PARENT message may contain a list of sources. The broadcast of link-state information is achieved in the following manner. Any link-state update originating from node src is accepted by node i if (1) it is received from the parent node p_i(src), and (2) it has a larger sequence number than the corresponding link-state entry in the topology table at node i. The processing of the link state updates received from node p_i(src), denoted nbr, is delayed until pstate_i(src, nbr) is equal to Active_Parent. When processed, the link-state update is entered into the topology table of node i, and then broadcast to neighbors of node i if children_i(src) is nonempty. (see the procedures Update_Topology_Table and Process_Update). Whenever its topology table changes, a node recomputes its parent with respect to every source node (see the procedure Update_Parents). This happens when the node receives a topology update, establishes a link to a new neighbor, or detects the failure of a link to an exist- ing neighbor. A node computes its parents by (1) computing minimum- hop paths to all other nodes using Dijkstra's algorithm, and then (2) selecting the parent for each source src to be the next node on the min-hop path to src (see the procedure Compute_New_Parents). A variant of Dijkstra's algorithm is used in which nodes that are the Bellur, Ogier, and Templin Expires 6 March 2002 [Page 27] INTERNET-DRAFT TBRPF 6 September 2001 same distance from the source are labeled in order of increasing node ID (as in TBRPF-PT), so that each node selects each parent to have the minimum possible ID. This minimizes the number of nodes that are selected as parents. Then, if the parent p_i(src) has changed, node i performs the follow- ing actions. It broadcasts the message CANCEL PARENT(nbr', src) if the old parent nbr' exists. In addition, node i broadcasts the mes- sage NEW PARENT(nbr, src, sn) if the newly computed parent exists, where nbr denotes the new parent and sn = sn_i(src) is the sequence number of the most recent link-state update originating from node src received by node i. This number indicates the "position" up to which node i has received updates (originating from node src) from the old parent, and after which the new parent should commence. However, if node i has no information regarding link-state updates originating from node src in its topology database, the "sn" field of the NEW PARENT(nbr, src, sn) message is set to NULL. Upon receiving the CANCEL PARENT(k, src) message from node i, the old parent k removes node i from the list children_k(src). Upon receiv- ing the NEW PARENT(j, src, sn) message from node i, the new parent j = p_i(src) adds node i to the list children_j(src). In addition, node j sends (to node i) a NEW PARENT REPLY(i, update_list) message, where update_list consists of all the link states originating from node src in its topology table which have sequence number greater than sn (see the procedure Process_New_Parent). However, if the "sn" field of the NEW PARENT(j, src, sn) message is equal to NULL, the new parent should respond by transmitting a NEW PARENT REPLY(i, update_list) message, where update_list now consists of all link-state updates in its topology database that originate from node src. Thus, only updates not yet known to node i are sent to node i. NEW PARENT and CANCEL PARENT messages are transmitted reliably using positive acknowledgments (see Section 6). Therefore, each message contains a sequence number, denoted ack_sn, which is the value of the ACK sequence number (ASEQ) when the message was first transmitted. The NEW PARENT REPLY message serves as an acknowledgment for the NEW PARENT message, and the ACK message is used to acknowledge the CANCEL PARENT message. Both the NEW PARENT REPLY and ACK messages contain the sequence number of the corresponding NEW PARENT or CANCEL PARENT message. To achieve reliable transmission, both the NEW PARENT and CANCEL PARENT messages are retransmitted (for upto MAX_NUM_RXMT times) if no acknowledgment is received within a given timeout period (RXMT_INTERVAL). To ensure that NEW PARENT messages containing the same source are processed in the correct order, if the parent p_i(u) for some source u changes while a previously generated NEW PARENT message containing source u is still being retransmitted, then source u is removed from the previously generated NEW PARENT message, and is included in a new NEW PARENT message having a larger sequence number. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 28] INTERNET-DRAFT TBRPF 6 September 2001 After transmitting a NEW PARENT(nbr, src, sn) message, node i changes the state of the newly computed parent node nbr to Pending_Parent i.e., pstate_i(src, nbr) = Pending_Parent. As mentioned above, the sequence number of the NEW PARENT message, denoted ack_sn, is used by the parent node in the NEW PARENT REPLY message. In addition, node i stores the tuple (ack_sn, nbr, src) in the list, ACK_i, which includes the list of NEW PARENT messages sent to neighboring nodes for which a response has not yet been received. Upon receiving a NEW PARENT REPLY(i, update_list) message with the appropriate sequence number ack_sn, node i retrieves and deletes the appropriate tuple (ack_sn, nbr, src) from ACK_i. At this time, if the NEW PARENT REPLY message is received from the parent node p_i(src), node i changes pstate_i(src, nbr) (i.e, the state of the neighboring node nbr as a parent of node i with respect to source node src) from Pending_Parent to Active_Parent (see the procedure Proc_New_Parent_Reply). From this point on, node i can accept and process link-state updates originat- ing from node src from the parent node p_i(src) beginning with the link-states in the NEW PARENT REPLY message. If a node receives several NEW PARENT messages from different neigh- bors at around the same time, it is possible to efficiently combine the different responses into one NEW PARENT REPLY message transmis- sion. In this case, the NEW PARENT REPLY message should contain for each NEW PARENT message that is being acknowledged (i) the identity of the neighboring node from which the NEW PARENT message was received, followed by (ii) the sequence number, ack_sn, of the NEW PARENT message. Finally, the NEW PARENT REPLY message contains a set of link-state updates, which can be computed as follows. Suppose each of the NEW PARENT messages was being acknowledged indi- vidually in a separate NEW PARENT REPLY message, each of which con- tains a set of link-state updates. The union of the link-state updates in each of these NEW PARENT REPLY messages is present in the single NEW PARENT REPLY message transmission. When a node i detects the existence of a new neighbor nbr, it exe- cutes Link_Up(i, nbr) to process this newly established link. The link cost and sequence number fields for this link in the topology table at node i are updated. Then, the corresponding link-state message is broadcast to all neighbors if children_i(i) is not empty. As noted above, node i also recomputes its parent node p_i(src) for every node src, in response to this topological change. In a similar manner, when node i detects the loss of connectivity to an existing neighbor nbr, it executes Link_Down(i, nbr). Link_Change(i, nbr) is likewise executed at node i in response to a change in the cost to an existing neighbor node nbr. However, this procedure does not recom- pute parents. The method for assigning costs to links is beyond the scope of this specification. As an example, the cost of a link could simply be one (for min-hop routing), or the link delay plus a constant bias. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 29] INTERNET-DRAFT TBRPF 6 September 2001 We assume that, initially, a node has no links to neighbors, and that its topology table is empty. Also initially, at each node i, p_i(src) = NULL (i.e., not defined), children_i(src) is the empty set, and sn_i(src) = NULL for every node src. Every node then exe- cutes Link_Up to process each link established with a neighbor, which will result in a NEW PARENT message being sent to each neighbor. Since each neighbor j of node i is (trivially) the next node on the min-hop path from i to j, p_i(j) = j whenever j is a neighbor of i. Therefore, the NEW PARENT message sent to a new neighbor j contains j (and possibly other sources) in its source list. It is helpful to understand how TBRPF-FT works when initially all nodes of an ad-hoc network have no topology information. Each node i will first select each of its neighbor j as a new parent p_i(j) for source j. Then each neighbor j will inform node i of its outgoing links, which will allow node i to compute min-hop paths, and thus new parents p_i(u), for all sources u that are two hops away. Then each parent p_i(u) for each such u will inform node i of node u's outgoing links, which will allow node i to compute new parents for all sources that are three hops away. This process continues until node i has computed parents for all sources u. To minimize the amount of link-state update traffic that is transmit- ted within the network, TBRPF-FT makes use of the following two parameters. The parameter MIN_FORW_UPDATE_INTERVAL specifies the minimum time between forwarding link-state updates at a given node. In addition, the parameter MIN_UPDATE_INTERVAL specifies the minimum time between link-state updates generated at a given node regarding its outgoing links. TBRPF-FT does not require an age field in link-state updates. How- ever, failed links (represented by an infinite cost) and links that are unreachable (i.e., links (u,v) such that p_i(u) = NULL) are deleted from the topology table after a certain time in order to con- serve memory. When an update is received reporting a link failure, the link remains in the topology table for DOWN_LINK_HOLD_TIME (default 120 sec) and is then deleted. When node i detects that source node u becomes unreachable for UNREACHABLE_HOLD_TIME (default 60 sec), all links outgoing from that source are deleted from the topology table. In addition, sn_i(u) is set to NULL which indicates that node i has no information regarding link-state updates originat- ing from source node u. For correct operation of TBRPF-FT, it is required that UNREACHABLE_HOLD_TIME is less than DOWN_LINK_HOLD_TIME. The reason these updates are not deleted immediately is as follows. Failed links (u,v) must be maintained for some time in the topology table to ensure that a node i that changes its parent p_i(u) near the time of failure (or had no parent p_i(u) during the failure) is informed of the failure by the new parent. Unreachable links, i.e., links (u,v) such that i and u are on different sides of a network partition, are maintained for a period of time to avoid having to Bellur, Ogier, and Templin Expires 6 March 2002 [Page 30] INTERNET-DRAFT TBRPF 6 September 2001 rebroadcast the old link state for (u,v) throughout i's side of the partition, if the network partition recovers soon (which is likely to happen if the network partition is caused by a marginal link that oscillates between the up and down states). This property is impor- tant to ensure the efficiency of TBRPF-FT when network partitions are common. A node that is turned off (or goes to sleep) operates as if the links to all neighbors have gone down. Thus, the node remembers the link- state information it had when it was turned off. Since all such links are either down or unreachable, these link states are deleted from the topology table if the node awakens after being in sleep mode for more than DOWN_LINK_HOLD_TIME seconds. Periodic updates are not strictly required for the correctness of TBRPF-FT. However, infrequent periodic updates can be used to correct rare errors that may occur. As discussed above, periodic updates are also required if the sequence number space is not large enough to avoid wraparound. Periodic updates are generated as described in the procedure Send_Periodic_Updates. TBRPF-FT provides each node with complete link-state information. Each node can then apply a path selection algorithm to compute pre- ferred paths to all possible destinations, and to update these paths when link states are updated. The default path selection algorithm for TBRPF-FT is to apply Dijkstra's algorithm to compute shortest paths (with respect to c) to all destinations. However, TBRPF-FT can employ any path selection algorithm. Once preferred paths are com- puted, the routing table entry for node u is set to the next node on the preferred path to u. If min-hop routing is desired, then the routing table entry for u can be set to the parent p_i(u). In the current implementation of TBRPF-FT, data packets are forwarded based on the routing table as in IP routing. However, source routing can also be used. 8.3. Pseudocode for TBRPF-FT The following pseudocode describes the network-level procedures per- formed at node i by TBRPF-FT. The notation LSU(update_list) represents a link-state-update message that includes the updates (u,v,c,sn) in update_list. Process_Update(i, nbr, in_message){ (Called when an update message in_message is received from nbr.) Update_Topology_Table(i, nbr, in_message, update_list). Update_Parents(i). Set send_list to empty For each (node src in TT_i) { Let update_list(src) consist of all tuples (k,l,c,sn) in update_list such that k = src. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 31] INTERNET-DRAFT TBRPF 6 September 2001 If (children_i(src) is nonempty) Add update_list(src) to send_list } If (send_list is nonempty) Broadcast the message LSU(send_list) to all neighbors.} Update_Topology_Table(i, nbr, in_message, update_list){ Set update_list to empty list. For each ((u,v,c,sn) in in_message) { If (p_i(u) == nbr) { If(pstate_i(u, nbr) == Pending_Parent) Withhold processing of link state updates in update_list until pstate_i(u, nbr) is equal to Active_Parent. If ((u,v) is in TT_i and sn > TT_i(u,v).sn) { Add (u,v,c,sn) to update_list. Set TT_i(u,v).sn = sn. Set TT_i(u,v).c = c. If (sn > sn_i(u)) Set sn_i(u) = sn. If((v == i) and (u belongs to N_i) and (c == infinity)) Link_Down(i, u) } If ((u,v) is not in TT_i) { Add (u,v,c,sn) to TT_i. Add (u,v,c,sn) to update_list. If (sn > sn_i(u)) Set sn_i(u) = sn. If((v == i) and (u belongs to N_i) and (c == infinity)) Link_Down(i, u) }}}} Link_Change(i,j){ (Called when the cost of link (i,j) changes.) If (|TT_i(i,j).c - cost(i,j)|/TT_i(i,j).c > epsilon) { Set TT_i(i,j).c = cost(i,j). Set TT_i(i,j).sn = current time stamp SN_i. Set update_list = {(i, j, TT_i(i, j).c, TT_i(i, j).sn)}. If (children_i(i) is nonempty) Broadcast the message LSU(update_list) to all neighbors.}} Link_Down(i,j){ (Called when link (i,j) goes down.) Remove j from N_i. Set TT_i(i,j).c = infinity. Set TT_i(i,j).sn = current time stamp SN_i. Update_Parents(i). For each (node src in TT_i) remove j from children_i(src). Set update_list = {(i,j, infinity, TT_i(i,j).sn)}. If (children_i(i) is nonempty) Broadcast the message LSU(update_list) to all neighbors.} Link_Up(i,j){ (Called when link (i,j) comes up.) Add j to N_i. Set TT_i(i,j).c = cost(i,j). Bellur, Ogier, and Templin Expires 6 March 2002 [Page 32] INTERNET-DRAFT TBRPF 6 September 2001 Set TT_i(i,j).sn = current time stamp SN_i. Update_Parents(i). Set update_list = {(i, j, TT_i(i,j).c, TT_i(i,j).sn)}. If (children_i(i) is nonempty) Broadcast message LSU(update_list) to all neighbors.} Update_Parents(i){ Compute_New_Parents(i). Set cancel_parent_msgs and new_parent_msgs to empty. For each (node k in N_i) { Set cancel_src_list(k), src_list(k), and sn_list(k) to empty.} For each (node src in TT_i such that src != i){ If (new_p_i(src) != p_i(src)){ If (p_i(src) != NULL){ Set k = p_i(src) Add src to cancel_src_list(k) pstate_i(src, k) = Inactive_Parent. } Set p_i(src) = new_p_i(src). If (new_p_i(src) != NULL){ Set k = new_p_i(src). Add src to src_list(k). Add sn_i(src) to sn_list(k). pstate_i(src, k) = Pending_Parent. }}} For each (node k in N_i){ If (src_list(k) is nonempty){ Add (ack_sn_i, k, src_list(k), sn_list(k)) to new_parent_msgs. Add (ack_sn_i, k, src_list(k)) to ACK_i. Set ack_sn_i = ack_sn_i + 1} If (cancel_src_list(k) is nonempty){ Add (ack_sn_i, k, cancel_src_list(k)) to cancel_parent_msgs. Add (ack_sn_i, k, cancel_src_list(k)) to ACK_i. Set ack_sn_i = ack_sn_i + 1 }} If(new_parent_msgs is nonempty) Broadcast message NEW PARENT(new_parent_msgs) to all neighbors. If(cancel_parent_msgs is nonempty) Broadcast message CANCEL PARENT(cancel_parent_msgs) to all neighbors.} Increment_nontree_edge_cost(i){ Compute min-hop paths using Dijkstra. For each (node src in TT_i such that src != i) { Set q_i(src) equal to the neighbor of node src along the minimum hop path from i to src. } For each ((u, v, c, sn) in TT_i) { if(u != q_i(v)){ /* nontree edge */ TT_i(u, v).c = TT_i(u, v).c + 0.001 TT_i(u, v).nontree_edge = YES }}} Decrement_nontree_edge_cost(i){ For each ((u, v, c, sn) in TT_i) if(TT_i(u, v).nontree_edge == YES){ TT_i(u, v).c = TT_i(u, v).c - 0.001 Bellur, Ogier, and Templin Expires 6 March 2002 [Page 33] INTERNET-DRAFT TBRPF 6 September 2001 TT_i(u, v).nontree_edge = NO }} Compute_New_Parents(i){ For each (node src in TT_i such that src != i) Set new_p_i(src) = NULL. Increment_nontree_edge_cost(i) Compute min-hop paths using Dijkstra. For each (node src in TT_i such that src != i) { Set new_p_i(src) equal to the neighbor of node i along the minimum hop path from i to src. } Decrement_nontree_edge_cost(i) } Process_New_Parent(i, nbr, new_parent_msgs){ (Called when node i receives a NEW PARENT(new_parent_msgs) message from nbr.) For each ((newpsn, k, src_list, sn_list) in new_parent_msgs) { if (k == i){ /* This part of the NEW PARENT message is for node i. */ Set update_list to empty list. For each (node src in src_list) { Let sn_list.src denote the sequence number corresponding to src in sn_list. Add nbr to children_i(src). Set new_updates = {(x,y,c,sn) in TT_i such that x = src and sn > sn_list.src}. Add new_updates to update_list.} Broadcast the message NEW PARENT REPLY(nbr, newpsn, update_list) to all neighbors. }}} Process_Cancel_Parent(i, nbr, cancel_parent_msgs) { (Called when node i receives a CANCEL PARENT(cancel_parent_msgs) message from node nbr.) For each ((cnclpsn, k, src_list) in cancel_parent_msgs) { if(k == i){ For each (node src in src_list) remove nbr from children_i(src). Send the message ACK (nbr, cnclpsn) }}} Proc_New_Parent_Reply(i, nbr, nbr', newpsn, update_list){ (Called when node i receives a NEW PARENT REPLY(nbr', newpsn, update_list) message from nbr.) if(nbr' == i){ /* The NEW PARENT REPLY is for node i */ Retrieve (and delete) the tuple (newpsn, nbr, src_list') from the list ACK_i. For each (node src in src_list') if((pstate_i(src, nbr) == Pending_Parent) and (p_i(src) == nbr)) Set pstate_i(src, nbr) = Active_Parent. Process_Update(i, nbr, update_list) }} Proc_Cancel_Parent_Ack(i, nbr, nbr', cnclpsn){ (Called when node i receives an ACK (nbr', cnclpsn) message from nbr.) if(nbr' == i){ Bellur, Ogier, and Templin Expires 6 March 2002 [Page 34] INTERNET-DRAFT TBRPF 6 September 2001 Retrieve (and delete) the tuple (cnclpsn, nbr, src_list') from the list ACK_i. For each (node src in src_list') pstate_i(src, nbr) = Null_Parent }} Send_Periodic_Updates(i){ Set update_list to empty. For each (j in N_i such that TT_i(i,j). c != infinity){ Set TT_i(i,j).sn = current time stamp SN_i. Add (i, j, TT_i(i,j).c, TT_i(i,j).sn) to update_list. } If (children_i(i) is nonempty) Broadcast message LSU(update_list) to all neighbors.} 8.4. Configurable Parameters This section lists the values of the parameters used in the descrip- tion of the protocol, and their proposed default values. HELLO_INTERVAL (2 seconds) NBR_HOLD_TIME (6 seconds) RXMT_INTERVAL (2 seconds) MAX_NUM_RXMT (3) DOWN_LINK_HOLD_TIME (120 seconds) UNREACHABLE_HOLD_TIME (60 seconds) MIN_UPDATE_INTERVAL (2 seconds) MIN_FORW_UPDATE_INTERVAL (1 second) 9. Application of TBRPF In Mobile Ad-hoc Networks The TBRPF routing protocols provide proactive, automatic topology discovery with dynamic adaptation to link state changes in both fixed and mobile environments whether the topology is relatively static or highly dynamic in nature. TBRPF is particularly well suited to MANETs consisting of mobile nodes with wireless network interfaces operating in peer-to-peer fashion over a multiple access communications channel (e.g. the IEEE 802.11 Distributed Coordination Function (DCF) [13].) Although applicable across a much broader field of use, TBRPF is par- ticularly well suited for supporting the standard DARPA Internet pro- tocols (IPv4) [10] as per current practices advocated by the IETF MANET working group. In the following sections, we discuss assumptions for the data link and network layers. We further discuss an optional automatic address Bellur, Ogier, and Templin Expires 6 March 2002 [Page 35] INTERNET-DRAFT TBRPF 6 September 2001 resolution mechanism for TBRPF nodes in a MANET environment. 9.1. Data Link Layer Assumptions We assume a data link layer that supports broadcast, multicast and unicast addressing with best-effort (not guaranteed) delivery ser- vices between neighbors (i.e. a pair of nodes within operational com- munications range of one another). We further assume that each data link layer interface belonging to a node in a MANET is assigned a unicast address that is unique within that particular MANET. While uniqueness for data link layer address assignments is not strictly guaranteed, the assumption of uniqueness is consistent with current practices for the deployment of IPv4 on specific link layers, such as Ethernet [5]. Methods for duplicate data link layer address detection and deconfliction are beyond the scope of this document. 9.2. Network Layer Assumptions MANETs are formed as collections of MANET routers [14] and non- routing nodes. We assume that each MANET router has at least one data link layer interface (as described above) with an IPv4 address that is unique within the MANET and thus may be used as a Router ID (RID) for TBRPF protocol message exchanges. MANET routers may optionally comprise multiple interfaces with additional IPv4 addresses that are also unique within the MANET. We further assume that each MANET router supports the multi-hop relay paradigm; in other words, each router provides an inter-node forwarding service via IPv4 host routes which reflect the current MANET topology as perceived by TBRPF. 9.3. Automatic Address Resolution TBRPF employs a proactive neighbor discovery protocol that maintains bi-directional link state for neighboring nodes through the periodic transmission of messages. Since the protocol provides unambiguous link state information, and since each neighbor discovery messages contain both the data link layer address and IPv4 address of the sender, implementations MAY OPTIONALLY employ automatic IPv4-to-data link layer address resolution for the nodes with which they form links. An implementation may use such a mechanism to avoid the addi- tional message overhead required for sending on-demand resolution requests via the Address Resolution Protocol (ARP) [9] and to allow proactive (rather than demand-driven) management of ARP cache. Since this behavior is optional, however, implementations MUST respond to ARP requests in the normal manner. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 36] INTERNET-DRAFT TBRPF 6 September 2001 10. TBRPF Packets and TBRPF Protocol Messages TBRPF *messages* encode protocol primitives described in earlier sec- tions. One or more TBRPF messages are embedded within each TBRPF *packet*, as described in this section. All TBRPF packets are sent to the "All_MANET_Neighbors" multicast address and thus reach all MANET routers within single-hop transmission range of the sender. (MANET routers MUST NOT forward packets sent to the "All_MANET_Neighbors" multicast address to other nodes. See: "IANA Considerations" for more information.) Since packet loss due to link failure, interference, etc. can occur, implementations SHOULD split large TBRPF protocol packets into several smaller packets to avoid IPv4 fragmentation/reassembly. Since packets sent to "All_MANET_Neighbors" are delivered only to single- hop neighbors, Path MTU Discovery is not required. Instead, MANET routers can derive the maximum TBRPF packet length(s) directly from the maximum transmission unit(s) (MTUs) of their attached interface(s). Implementations MUST send and receive TBRPF packets via the User Datagram Protocol (UDP) [11]. This approach requires an official UDP service port number registration (see: "IANA Considerations"). UDP/IPv4 provides: - a message length field - checksum facilities for data integrity - simple application level access for routing daemons - IPv4 multicast addressing - Internet security mechanisms with policy-based address filtering While the use of UDP is required, implementations MAY OPTIONALLY employ alternate data delivery services for the transmission of some or all TBRPF packets. The choice of an alternate data delivery ser- vice MUST be presented as a configurable option beyond the default of using UDP/IPv4. Any such configuration choice MUST be consistent among all MANET routers in the network. All TBRPF packets consist of two components: (1) a packet header (with optional header extension fields) immediately followed by (2) a packet body that includes header options, one or more TBRPF message(s) and padding options as needed. The total length of all packet components must be less than the maximum UDP/IPv4 packet length of 64KB. In the following sections, we describe the elements of a TBRPF packet in detail. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 37] INTERNET-DRAFT TBRPF 6 September 2001 10.1. TBRPF Packet Header TBRPF packet headers are variable-length (minimum two octets) as determined by the "flag" bits found in the first octet. Implementa- tions MUST ensure that the first octet of the TBRPF packet header is aligned on an even 8-octet boundary. (The 8-octet alignment require- ment provides a natural boundary for the alignment of n-octet data elements up to 8-octets in length for anticipated future use in 64- bit architectures.) Note that all further alignment requirements discussed throughout this section are relative to the first octet of the tbrpf packet header. Therefore, bit ordering beginning at bit 0 is shown ONLY in the TBRPF packet header diagram; other diagrams in this section omit the bit ordering notation. The format for the TBRPF packet header and a description of the indi- vidual fields are given below: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - -+ |C|L|R|Z| Vers | Current NSEQ | Extension Fields (optional) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - -+ Flags (4 bits): Three flag bits (C, L, R) specify which header extension fields (if any) are present. Any header extension fields enabled by these bits MUST appear in canonical order (i.e. first C, then L, then R). A fourth flag bit (Z) selects either aligned or compressed format for the TBRPF message. The flag bits and their usage are described in detail below: C - Checksum Field Included: If the underlying delivery service provides a checksum facility (e.g. UDP/IPv4) AND the facility is enabled, the sender MAY set C = '0' to indicate no checksum extension field present. Other- wise, the sender MUST set C = '1' to indicate that a 16-bit TBRPF checksum field follows immediately after the "Current NSEQ" field. When C = '1', the sender MUST calculate the check- sum of the TBRPF packet in the manner described in [11] and write the resultant sum into the 16-bit checksum extension field. The checksum is calculated across ALL data bytes in the packet header, header extension fields, and packet body, but DOES NOT include a pseudo-header of the underlying delivery service. Receivers MUST examine the C bit to determine whether a check- sum field is present. If C = '1', the receiver MUST verify the checksum encoded in the 16-bit message checksum field as described in [11] to ensure TBRPF packet data integrity (i.e. if C = '1', checksum verification is required WHETHER OR NOT a checksum was performed by the underlying delivery service.) Bellur, Ogier, and Templin Expires 6 March 2002 [Page 38] INTERNET-DRAFT TBRPF 6 September 2001 Receivers MUST discard any TBRPF packet that contains an incorrect checksum. Similarly, receivers MUST discard any TBRPF packet with neither a checksum provided by the underlying delivery service nor a checksum in the TBRPF packet header. L - Length Field Included: When the underlying delivery service provides a length field (e.g. UDP/IPv4), a sender MAY set L = '0' to indicate that NO packet length extension field is included. Otherwise, the sender MUST set L = '1' to indicate that a 16-bit unsigned integer TBRPF packet length field follows immediately after any previous header fields. When L = '1', the sender MUST calculate the length of the TBRPF packet (including all header and data bytes) and write the resulting length into the 16-bit unsigned integer packet length field in network byte order. (If a check- sum field is also provided, the sender MUST write the length field BEFORE the checksum is calculated.) Receivers MUST examine the L bit to determine whether a length field is included. If a length field is included, receivers must convert it to host byte order and treat the result as the length of the TBRPF packet, including the TBRPF packet header. If the underlying delivery service ALSO provides a length field, receivers MUST verify that the length provided by the underlying delivery service matches the length provided by the TBRPF packet header. Receivers MUST discard any TBRPF packet in which the two lengths do not match. Similarly, receivers MUST discard any TBRPF packet if neither the underlying delivery service nor the TBRPF packet header provide packet length. R - Reserved: The R bit is RESERVED, and may be used in the future to indi- cate that an additional header extension field follows immedi- ately after any previous fields. Z - Message Alignment/Compression: If Z = '0', the sender MUST align multi-octet words within the TBRPF packet body on "natural" boundaries (i.e. 64-bit words MUST begin on integral modulo-8 byte addresses, 32-bit words MUST begin on integral modulo-4 byte addresses and 16-bit words MUST begin on integral module-2 byte addresses.) The sender MUST use Pad1 and/or PadN options (described in the next sec- tion) where necessary to achieve natural alignment. If Z = '1', the sender MAY OPTIONALLY omit padding options to provide message compression; since this may result in multi- octet words aligned non-integral byte boundaries, receivers MUST process such multi-octet words "byte-by-byte" rather than as atomic n-byte data units. Senders SHOULD avoid message compression to minimize processing overhead for receivers unless maximal message compression is required (e.g. for low- Bellur, Ogier, and Templin Expires 6 March 2002 [Page 39] INTERNET-DRAFT TBRPF 6 September 2001 bandwidth links). Receivers MUST be able to process both aligned and compressed packets. Version (4 bits): Identifies TBRPF protocol version and provides a sanity check for host software to detect TBRPF protocol message corruption. The following version field values are defined: TBRPFVERSION_2 2 TBRPFVERSION_1 1 The packet formats defined in this draft represent TBRPF version 2 and MUST be transmitted with the value TBRPFVERSION_2 in the ver- sion field. TBRPF version 2 implementations MAY OPTIONALLY provide backwards compatibility for TBRPFVERSION_1 packets (specified in earlier versions of this draft). Current NSEQ (8 bits): The current NACK sequence number. 10.2. TBRPF Packet Body The TBRPF packet body consists of the concatenation of a number of elements including: header options, message options, one or more TBRPF message(s), and padding options where necessary. These elements are encoded using a method derived directly from the type-length- value (TLV) encoding method described in pp. 9-10 of Internet RFC 2460 [15]. We refer to our adaptation of this method as TBRPF TLV (or, T_TLV) to distinguish it from the original TLV method described in [15], but otherwise adopt the same terminology whenever possible. This method encodes elements within the TBRPF packet body (heretofore referred to as "T_TLV Elements") using the following format: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -+- - - - | TYPE |P|L| LEN(0) | LEN(1) | VALUE +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -+- - - - TYPE (6 bits): A 6-bit identifier with value 0 - 63 that gives the type of the T_TLV Element. NB: Although the TYPE field is in the first octet of the T_TLV Element, it may NOT always begin on an n-octet natural word boundary. Following sections will describe TYPE- dependent alignment considerations for T_TLV Elements. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 40] INTERNET-DRAFT TBRPF 6 September 2001 P - Partial message bit (1 bit): A 1-bit flag; if P = '0', the T_TLV Element contains either a complete TBRPF message, or the final segment of a TBRPF message that spans multiple TBRPF packets. If P = '1', the T_TLV Element contains a partial segment of a TBRPF message that spans multiple TBRPF packets. L - Length extension bit (1 bit): A 1-bit flag; if L = '0', the T_TLV Element is in SHORT format, and the LEN field is a single octet. If L = '1', the T_TLV Element is in LONG format, and the LEN field comprises 2 octets. LEN (8/16 bits): The length of the VALUE field, in octets. If L = '0', the LEN field is a single octet that encodes an 8-bit unsigned integer which MUST contain a value within the range from 0 - 253. (Thus, the maximum length of the T_TLV Element *including* the TYPE and LEN fields is 255 octets in SHORT format.) If L = '1', the LEN field comprises TWO octets; each encoding an 8-bit unsigned integer. The FIRST 8-bit unsigned integer encodes the least significant byte and the SECOND 8-bit unsigned integer encodes the most significant byte of the length of the VALUE field, in octets. If L = '1', the length of the value field is calculated as a 16-bit unsigned integer as follows: length = (LEN(1) * 256) + LEN(0) If L = '1', this calculated length MUST be within the range from 0 - 65532. (Thus, the maximum length of the T_TLV Element *including* the TYPE and LEN fields is 65535 octets in LONG format.) Since the first octet of the LEN field is NOT guaranteed to fall on a natural 16-bit word alignment, implementations MUST NOT access the two-octet LEN field as a 16-bit unsigned integer when LONG format is used. VALUE Variable-length field. Format and length depends on TYPE, as described in the following sections. As described in [15], the sequence of T_TLV Elements MUST be pro- cessed strictly in the order they appear within the TBRPF packet body; a receiver must not, for example, scan through the TBRPF packet body looking for a particular type of T_TLV Element prior to process- ing all preceding elements. Additionally, individual T_TLV Elements may have specific alignment requirements to ensure that multi-octet values fall on natural boundaries. The alignment requirement of a T_TLV Element is specified using the notation xn+y, meaning the ele- ment type must appear at an integer multiple of x octets from the start of the TBRPF packet header, plus y octets. For example: Bellur, Ogier, and Templin Expires 6 March 2002 [Page 41] INTERNET-DRAFT TBRPF 6 September 2001 2n means any 2-octet offset from the start of the TBRPF packet header. 8n+2 means any 8-octet offset from the start of the TBRPF packet header, plus 2 octets. T_TLV Elements are grouped into four categories: padding options, header options, message options, and TBRPF messages. The following subsections describe these four categories in detail. 10.2.1. T_TLV Padding Options (TYPE = 0 thru 1) As described in [15], senders may insert two types of padding options where necessary to satisfy alignment requirements for other T_TLV Elements. Padding options may occur anywhere within the TBRPF packet body. When the Z bit in the TBRPF packet header is '0', senders MUST insert padding options to ensure that the alignment requirements for other T_TLV Elements are met. When Z = '1', padding options MAY be omitted and alignment is NOT guaranteed. The following two padding options are defined: Pad1 option (TYPE = 0) - Alignment requirement: none +-+-+-+-+-+-+-+-+ | 0 |0|0| +-+-+-+-+-+-+-+-+ The P, L bits MUST be '0', and the LEN and VALUE fields are omitted. The Pad1 option inserts one octet of padding into the TBRPF packet body. If more than one octet of padding is required, the PadN option, described next, should be used, rather than multiple Pad1 options. PadN option (TYPE = 1) - Alignment requirement: none +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - | 1 |0|L| LEN(0) | LEN(1) | VALUE +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - The PadN option inserts two or more octets of padding into the TBRPF packet body. The P bit MUST be '0'. If L = '0', the LEN field is one octet in length and contains the value N-2. The VALUE field consists of N-2 zero-valued octets up to a maximum of 253 octets, for a maximum of N = 255 padding bytes, including the TYPE and LEN fields themselves. If L = '1', the LEN field is TWO octets in length and contains the value N-3. The VALUE field consists of N-3 zero-valued octets up to a maximum of 65,532 octets, for a maximum of N = 65,535 padding bytes, including the TYPE and LEN fields themselves. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 42] INTERNET-DRAFT TBRPF 6 September 2001 10.2.2. T_TLV Header Options (TYPE = 2 thru 7) T_TLV header options provide packet parameters in addition to the information encoded in the TBRPF packet header. T_TLV header options MUST appear immediately after the TBRPF packet header and BEFORE any T_TLV Elements with TYPE > 7 within the message body. (Note that pad- ding options may be intermixed with T_TLV header options.) If a receiver detects a T_TLV header option AFTER processing any T_TLV Element(s) with TYPE > 7, the receiver MUST skip past the VALUE field (ignoring its contents) and resume processing at the next T_TLV Ele- ment, if any. The following T_TLV header options are defined: Router ID (RID) option (TYPE = 2) - Alignment requirement: 4n+3 +-+-+-+-+-+-+-+-+ | 2 |0|0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID (4 octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The P, L bits MUST be '0', and the LEN field is omitted. The VALUE field contains the 4-octet IPv4 address corresponding to the Router ID (RID) of the sender, encoded in network byte order (least signifi- cant byte first). Senders MUST encode this option when the RID cannot be derived from header information transmitted by the underlying data delivery service. (For example, when the IPv4 header contains an IPv4 source address that is *different* than the RID.) Otherwise, senders should avoid encoding an RID option to eliminate unnecessary data octets. The RID option provides a mechanism for implicit Network-level Address Resolution (NARP) as described in [14]. A receiver that detects an RID option MUST create a NARP binding between the RID and any network level address(es) that appear either in the network-level header or in any Alias Address header options (see the following sec- tion) that appear within the same TBRPF packet. A sender SHOULD encode at most one RID option within each TBRPF packet. If multiple RID options occur, receivers MUST accept the RID that appears in the first such option and ignore any subsequent RID options. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 43] INTERNET-DRAFT TBRPF 6 September 2001 Alias Address (ALIASADDR) option (TYPE = 3) - Alignment requirement: 4n+3 +-+-+-+-+-+-+-+-+ | 3 |AF | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Alias Address (N octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The P, L bits are used to encode a 2-bit Address Family (AF) field. The LEN field is omitted, and the length of the encoded Alias Address is inferred from the value in the Address Family field. The VALUE field contains an N-octet Alias Address encoded in network byte order (least significant byte first), where N is implicitly derived from the value in the AF field. The following AF field values are defined: 00 - The encoded Alias Address is a 4-octet IPv4 protocol address 01 - The encoded Alias Address is a 16-octet IPv6 protocol address 10, 11 - RESERVED for future use Senders MAY OPTIONALLY encode the ALIASADDR option when they wish to publish one or more Alias Addresses that differ from their Router ID (RID). Senders MAY encode multiple ALIASADDR options within each TBRPF packet. Receivers MUST accept each alias address thus encoded and create a NARP binding between the sender's RID and each alias address. MAC Address (MACADDR) option (TYPE = 4) - Alignment requirement: none +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4 |FMT| MAC(0) | MAC(1) | MAC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - | MAC(N-1) | (Ends on an arbitrary boundary) - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - The P, L bits are used to encode a 2-bit "Format" (FMT) field. The LEN field is omitted, and the length of the encoded MAC address is inferred from the value in the FMT field. The VALUE field contains an N-octet MAC address corresponding to the sender's network interface, encoded in network byte order (least significant byte first), where N is implicitly derived from the value in the FMT field. The following FMT field values are defined: 00 - The encoded MAC address is a 6-octet IEEE 802 MAC address, commonly referred to as "EUI-48 Format" 00 - The encoded MAC address is an 8-octet IEEE 802 MAC address, commonly referred to as "EUI-64 Format" 10, 11 - RESERVED for future use Bellur, Ogier, and Templin Expires 6 March 2002 [Page 44] INTERNET-DRAFT TBRPF 6 September 2001 Senders MUST encode the MACADDR option when the MAC address cannot be derived directly from header information transmitted by the underlying data delivery service. (The MAC address is ALWAYS available in the MAC header when IEEE 802-compliant data link interfaces are used. Thus the transmission of MACADDR is OPTIONAL when such interfaces are used.) Senders MAY encode multiple MACADDR options within each TBRPF packet, but the purpose of encoding multiple MACADDR options in this manner is currently UNDEFINED. A receiver MUST accept the MAC address encoded in the first occurrence of a MACADDR option in each TBRPF packet and MAY OPTIONALLY cache the values encoded in any subsequent MACADDR option within the same packet. TYPE = 5 thru 7 are RESERVED for future use. 10.2.3. T_TLV Message Options (TYPE = 8 thru 15) T_TLV message options provide parameters that apply to subsequent T_TLV messages within the packet body. T_TLV message options MAY appear anywhere within the TBRPF packet body after the TBRPF packet header and T_TLV header options if any are present. Senders MAY encode MULTIPLE instances of the same T_TLV message option type within each TBRPF packet. If a receiver detects multiple occurrences of the same T_TLV message option type within the same packet body, the VALUE of the MOST RECENT such option overrides the VALUE from any previous occurrence. The following T_TLV message options are defined: Unacknowledged Block (UNACKBLK) option (TYPE = 8) - Alignment requirement: none +-+-+-+-+-+-+-+-+ | 8 |0|0| +-+-+-+-+-+-+-+-+ The P, L bits MUST be '0', and both the LEN and VALUE fields are omitted. The UNACKBLK message option delineates the beginning of an "unacknowledged block" that consists of one or more T_TLV messages for which neither NACK nor ACK messages occur. The initial segment of the TBRPF packet is considered an unacknowledged block by default, and the encoding of an UNACKBLK message option in the initial segment is NOT REQUIRED. The unacknowledged block ends when: - an ACKBLK message option occurs (see below) - a NACKBLK message option occurs (see below) - the end of the TBRPF packet is reached Bellur, Ogier, and Templin Expires 6 March 2002 [Page 45] INTERNET-DRAFT TBRPF 6 September 2001 ACK Block (ACKBLK) option (TYPE = 9) - Alignment requirement: none +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 9 |0|0| ASEQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The P, L bits MUST be '0', and the LEN field is omitted. The VALUE field contains a single octet with an ACK Sequence Number. The pres- ence of an ACKBLK message option delineates the beginning of block of one or more T_TLV messages belonging to the ACK sequence number in the VALUE field. As described in earlier sections, each T_TLV message within an ACK Block MUST be ACK'd via a positive acknowledgment. The ACK Block ends when: - an UNACKBLK message option occurs - another ACKBLK message option occurs - a NACKBLK message option occurs (see below) - the end of the TBRPF packet is reached Senders MAY encode multiple ACK Blocks within a single TBRPF packet. The T_TLV messages encoded in each ACK Block represent either new transmissions or retransmissions of messages for which the sender has not yet received a positive acknowledgment. A receiver that processes an ACK Block within the TBRPF packet MUST send a positive acknowledg- ment for each ACKable message for which it is the specified receiver. (NB: the receiver SHOULD process the entire TBRPF packet before sending a positive acknowledgment, since the TBRPF packet may contain MULTIPLE messages which require acknowledgements from that receiver.) NACK Block (NACKBLK) option (TYPE = 10) - Alignment requirement: none +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 10 |0|0| NSEQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The P, L bits MUST be '0', and the LEN field is omitted. The VALUE field contains a single octet with a NACK sequence number. The pres- ence of a NACKBLK message option delineates the beginning of a block of one or more T_TLV messages belonging to the NACK sequence number in the VALUE field. As described in earlier sections, each receiver must remember the most recent NACK sequence number it has processed from a particular sender to detect whether any messages have been missed. The NACK Block ends when: - an UNACKBLK message option occurs - an ACKBLK message option occurs - another NACKBLK message option occurs - the end of the TBRPF packet is reached Bellur, Ogier, and Templin Expires 6 March 2002 [Page 46] INTERNET-DRAFT TBRPF 6 September 2001 A sender MAY encode multiple NACK Blocks within a single TBRPF packet. The T_TLV messages encoded in each NACK Block represent either new transmissions or retransmissions of messages for which the sender has received one or more NACK(s). After a receiver has pro- cessed ALL NACK Blocks in the TBRPF packet, it MUST send a NACK mes- sage to the sender if it detects missing NACK sequence numbers. TYPE = 11 thru 15 are reserved for future use. 10.2.4. T_TLV Messages (TYPE = 16 thru 63) T_TLV messages encode the TBRPF protocol messages described in sec- tions 5-8. T_TLV messages are categorized as: - Common (apply to both TBRPF-PT and TBRPF-FT) - TBRFP-PT only - TBRPF-FT only The following subsections provide formats for T_TLV messages in each of these three categories. Alignment requirements for each T_TLV mes- sage type are listed for both SHORT and LONG formats, and a detailed message format diagram is given. Each message format diagram is fol- lowed by a brief description along with any error conditions that may occur during processing, including: - FORMAT ERROR: message has non integral number of elements - UNDERFLOW ERROR: message has fewer elements than expected In all cases, upon detecting an error receivers MUST discontinue pro- cessing the current TBRPF packet and discard any remaining portions. 10.2.4.1. Common Messages (TYPE = 16 thru 31) HELLO (TYPE = 16) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 16 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(N) | Bellur, Ogier, and Templin Expires 6 March 2002 [Page 47] INTERNET-DRAFT TBRPF 6 September 2001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - message body contains N 4-octet Neighbor RIDs, where N = LEN / 4 - LEN modulo 4 MUST be zero; else FORMAT ERROR ACK (TYPE = 17) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 17 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ASEQ(1) | ASEQ(2) | ASEQ(3) | ASEQ(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - | ASEQ(N) | (Ends on an arbitrary boundary) - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - - message body contains N 4-octet Neighbor RIDs followed by N 1-octet ACK sequence numbers, where N = LEN / 5 - LEN modulo 5 MUST be zero; else FORMAT ERROR NACK (TYPE = 18) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 18 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bellur, Ogier, and Templin Expires 6 March 2002 [Page 48] INTERNET-DRAFT TBRPF 6 September 2001 | NSEQ(1) | NSEQ(2) | NSEQ(3) | NSEQ(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - | NSEQ(N) | (Ends on an arbitrary boundary) - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - - message body contains N 4-octet Neighbor RIDs followed by N 1-octet NACK sequence Numbers, where N = LEN / 5 - LEN modulo 5 MUST be zero; else FORMAT ERROR NEW_PARENT (TYPE = 19) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 19 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - message body contains 1 4-octet Neighbor RID and N 4-octet Source RIDs, where N = (LEN / 4) -1 - LEN modulo 4 MUST be zero; else FORMAT ERROR - N MUST be > 0; else UNDERFLOW ERROR TYPE = 20 thru 31 are RESERVED for future use. 10.2.4.2. TBRPF-PT Only Messages (TYPE = 32 thru 47) UPDATE_REQUEST (TYPE = 32) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 32 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bellur, Ogier, and Templin Expires 6 March 2002 [Page 49] INTERNET-DRAFT TBRPF 6 September 2001 | Neighbor RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - message body contains N 4-octet Neighbor RIDs, where N = LEN / 4 - LEN modulo 4 MUST be zero; else FORMAT ERROR UPDATE_REPLY (TYPE = 33) (SHORT format alignment requirement: 4n+2) (LONG format alignment requirement: 4n+1) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 33 |P|L| LEN | N (= # NBRs) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ************************ LSU for SRC(1) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NNBR (==k[1]) | ZERO PADDING | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ************************ LSU for SRC(2) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NNBR (==k[2]) | ZERO PADDING | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bellur, Ogier, and Templin Expires 6 March 2002 [Page 50] INTERNET-DRAFT TBRPF 6 September 2001 ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ ~ ... ~ ~ ... ~ ************************ LSU for SRC(M) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NNBR (==k[M]) | ZERO PADDING | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - message body contains "ACK Block" with N 4-octet Neighbor RIDs (where N is encoded in an 8-bit unsigned integer). ACK Block is followed by M Link State Update (LSU) Blocks - ACK Block length = 1 + (N * 4) and MUST be <= LEN; else UNDERFLOW ERROR - LSU blocks encode 4-octet SRC RID, 2-octet NNBR field in network byte order, optional padding, and NNBR-many NBR RIDs - If Z = '0' in packet header, 2-octet ZERO PADDING field inserted as shown above and LSU Block length = 4 + 2 + 2 + (NNBR * 4); else PADDING OMITTED and LSU Block Length = 4 + 2 + (NNBR * 4) - LSU blocks MUST be processed consecutively, with length of each block deducted from LEN BEFORE processing; if LEN decremented below 0, FORMAT ERROR - final (Mth) LSU detected when LEN decremented to ZERO. TREE_UPDATE (TYPE = 34) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 34 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ************************ LSU for SRC(1) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bellur, Ogier, and Templin Expires 6 March 2002 [Page 51] INTERNET-DRAFT TBRPF 6 September 2001 | NNBR (==k[1]) |A| ZERO PADDING | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ************************ LSU for SRC(2) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NNBR (==k[2]) |A| ZERO PADDING | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ ~ ... ~ ~ ... ~ ************************ LSU for SRC(M) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NNBR (==k[M]) |A| ZERO PADDING | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - message body contains M Link State Update (LSU) Blocks - LSU blocks encode 4-octet SRC RID, 15-bit NNBR field in network byte order, 1-bit 'A' field, optional padding, and NNBR-many NBR RIDs - If A = '1', LSU Block encodes ADD operation; else DELETE - If Z = '0' in packet header, 2-octet ZERO PADDING field inserted and LSU Block length = 4 + 2 + 2 + (NNBR * 4); else PADDING OMITTED and LSU Block Length = 4 + 2 + (NNBR * 4) - LSU blocks MUST be processed consecutively, with length Bellur, Ogier, and Templin Expires 6 March 2002 [Page 52] INTERNET-DRAFT TBRPF 6 September 2001 of each block deducted from LEN BEFORE processing; if LEN decremented below 0, FORMAT ERROR - final (Mth) LSU detected when LEN decremented to ZERO. TYPE = 35 thru 47 are RESERVED for future use. 10.2.4.3. TBRPF-FT Only Messages (TYPE = 48 thru 63) CANCEL_PARENT (TYPE = 48) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 48 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - message body contains 1 4-octet Neighbor RID and N 4-octet Source RIDs, where N = (LEN / 4) -1 - LEN modulo 4 MUST be zero; else FORMAT ERROR - N MUST be > 0; else UNDERFLOW ERROR LINK_STATE_UPDATE (TYPE = 49) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 49 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ************************ LSU for SRC(1) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NNBR (==k[1]) | LSUSEQ for SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Metrics for NBR(1) | Link Metrics for NBR(2) | Bellur, Ogier, and Templin Expires 6 March 2002 [Page 53] INTERNET-DRAFT TBRPF 6 September 2001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(3) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Metrics for NBR(3) | Link Metrics for NBR(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(4) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(5) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ************************ LSU for SRC(2) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NNBR (==k[2]) | LSUSEQ for SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Metrics for NBR(1) | Link Metrics for NBR(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(3) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Metrics for NBR(3) | Link Metrics for NBR(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(4) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(5) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ ~ ... ~ ~ ... ~ ************************ LSU for SRC(M) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NNBR (==k[M]) | LSUSEQ for SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(1) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Metrics for NBR(1) | Link Metrics for NBR(2) | Bellur, Ogier, and Templin Expires 6 March 2002 [Page 54] INTERNET-DRAFT TBRPF 6 September 2001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(2) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(3) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Metrics for NBR(3) | Link Metrics for NBR(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(4) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(5) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - message body contains M Link State Update (LSU) Blocks - LSU blocks encode 4-octet SRC RID, 2-octet NNBR field in network byte order, 2-octet LSUSEQ for SRC, and NNBR-many 6-octet (NBR RID, NBR Link Metric) pairs as shown above - LSU Block length = 4 + 2 + 2 + (NNBR * 6) - If NNBR is ODD, and 'Z' bit in packet header is '0', 2-octet ZERO PADDING field added before beginning of next LSU Block and '2' added to LSU Block length; else no padding - LSU blocks MUST be processed consecutively, with length of each block deducted from LEN BEFORE processing; if LEN decremented below 0, FORMAT ERROR - final (Mth) LSU detected when LEN decremented to ZERO. NEW_PARENT_SEQ (TYPE = 50) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 50 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSUSEQ for Source RID(1) | LSUSEQ for Source RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSUSEQ for Source RID(3) | LSUSEQ for Source RID(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(4) | Bellur, Ogier, and Templin Expires 6 March 2002 [Page 55] INTERNET-DRAFT TBRPF 6 September 2001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(5) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSUSEQ for Source RID(5) | LSUSEQ for Source RID(6) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - message body contains 4-octet NBR RID followed by N 6-octet (Source RID, Source LSUSEQ) pairs encoded as shown above, where N = (LEN - 4) / 6 - (LEN - 4) modulo 6 MUST be zero; else FORMAT ERROR - N MUST be > 0; else UNDERFLOW ERROR NEW_PARENT_REPLY (TYPE = 51) - SHORT format alignment requirement: 4n+1 - LONG format alignment requirement: 4n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 51 |P|L| LEN | N (= # NBRs) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ASEQ(1) | ASEQ(2) | ASEQ(3) | ASEQ(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +- - - - - +-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - - - - + | ... | ASEQ(N) | ZERO-PADDING TO 4-OCTET BOUNDARY | +- - - - - +-+-+-+-+-+-+-+-+- - - - - - - - - - - - -- - - - - -+ ********************** LSU for SRC(1) *************************** +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(1) | +---------------------------------------------------------------+ | NNBR (==k[1]) | ZERO PADDING | +---------------------------------------------------------------+ | RID for NBR(1) of SRC(1) | +-------------------------------+-------------------------------+ | Link Metrics for NBR(1) | LSUSEQ for SRC(1),NBR(1) | +-------------------------------+-------------------------------+ | RID for NBR(2) of SRC(1) | +-------------------------------+-------------------------------+ Bellur, Ogier, and Templin Expires 6 March 2002 [Page 56] INTERNET-DRAFT TBRPF 6 September 2001 | Link Metrics for NBR(2) | LSUSEQ for SRC(1),NBR(2) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | RID for NBR(k[1]) of SRC(1) | +-------------------------------+-------------------------------+ | Link Metrics for NBR(k[1]) | LSUSEQ for SRC(1),NBR(k[1]) | +-------------------------------+-------------------------------+ ********************** LSU for SRC(2) *************************** +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(2) | +---------------------------------------------------------------+ | NNBR (==k[2]) | ZERO PADDING | +---------------------------------------------------------------+ | RID for NBR(1) of SRC(2) | +-------------------------------+-------------------------------+ | Link Metrics for NBR(1) | LSUSEQ for SRC(2),NBR(1) | +-------------------------------+-------------------------------+ | RID for NBR(2) of SRC(2) | +-------------------------------+-------------------------------+ | Link Metrics for NBR(2) | LSUSEQ for SRC(2),NBR(2) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | RID for NBR(k[2]) of SRC(2) | +-------------------------------+-------------------------------+ | Link Metrics for NBR(k[2]) | LSUSEQ for SRC(2),NBR(k[2]) | +-------------------------------+-------------------------------+ ~ ... ~ ~ ... ~ ~ ... ~ ********************** LSU for SRC(M) *************************** +-------------------------------+-------------------------------+ | RID for SRC(M) | +---------------------------------------------------------------+ | NNBR (==k[M]) | ZERO PADDING | +---------------------------------------------------------------+ | RID for NBR(1) of SRC(M) | +-------------------------------+-------------------------------+ | Link Metrics for NBR(1) | LSUSEQ for SRC(M),NBR(1) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | RID for NBR(k[m]) of SRC(m) | +-------------------------------+-------------------------------+ | Link Metrics for NBR(k[M]) | LSUSEQ for SRC(M),NBR(k[M]) | +-------------------------------+-------------------------------+ - message body contains "ACK Block" with N 4-octet Neighbor RIDs followed by N 1-octet Neighbor ASEQs pairs (where N is encoded in an 8-bit unsigned integer). ACK Block Bellur, Ogier, and Templin Expires 6 March 2002 [Page 57] INTERNET-DRAFT TBRPF 6 September 2001 followed by M Link State Update (LSU) Blocks - If Z = '0' in packet header, 0-3 octet ZERO PADDING field added at end of ACK Block as shown above; else PADDING OMITTED - ACK Block length = 1 + (N * 5) + # padding octets, and MUST be <= LEN; else UNDERFLOW ERROR - LSU blocks encode 4-octet SRC RID, 2-octet NNBR field in network byte order, optional padding, and NNBR-many 8-octet (NBR RID, NBR Link Metric, NBR LSUSEQ) triples - If Z = '0' in packet header, 2-octet ZERO PADDING field added as shown above and LSU Block length = 4 + 2 + 2 + (NNBR * 8); else PADDING OMITTED and LSU Block Length = 4 + 2 + (NNBR * 8) - LSU blocks MUST be processed consecutively, with length of each block deducted from LEN BEFORE processing; If LEN decremented below 0, FORMAT ERROR - final (Mth) LSU detected when LEN decremented to ZERO. TYPE = 52 thru 63 are RESERVED for future use. 11. IANA Considerations An official IANA UDP service port number assignment is required for TBRPF protocol messages. Additionally, an IANA IPv4 multicast address assignment for "All_TBRPF_Neighbors" is required from the range of addresses between 224.0.0.0 and 224.0.0.255 inclusive. This range of addresses is reserved for the use of routing protocols and other low-level topology discovery or maintenance protocols, such as gate- way discovery and group membership reporting. Multicast routers should not forward any multicast datagram with destination addresses in this range, regardless of its TTL [12]. Note that such an IPv4 multicast address assignment may have general application for MANET beyond its anticipated use for TBRPF. We there- fore propose that MANET consider the procurement of an "All_MANET_Neighbors" IPv4 multicast address from the range of addresses between 224.0.0.0 and 224.0.0.255. Such a procurement by MANET would obviate the requirement for an "All_TBRPF_Neighbors" mul- ticast address assignment. 12. Security Considerations Authentication issues exist for allowing "foreign" nodes to join a MANET via TBRPF neighbor discovery. Additionally, privacy issues exist for any networking protocols run over unencrypted wireless data links such as IEEE 802.11. Finally, denial-of-service attacks are possible if rogue nodes join a TBRPF MANET and offer to provide a multi-hop relay service, but then fail to perform the service when it is required. We believe that IPSec may be useful in addressing some or all of these issues. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 58] INTERNET-DRAFT TBRPF 6 September 2001 13. Implementation Status TBRPF version 1 (as described in version 0 of the draft) has been implemented in the FreeBSD V3.2 operating system with the Merit Multi-Threaded Routing Toolkit daemon (mrtd). The initial FreeBSD V3.2 implementation has been in use for laboratory and fielded exper- iments since June 1999. TBRPF version 1 has been ported to Linux. The current port runs on RedHat Version 7.0 and has been tested under multiple Linux kernel releases including 2.2.16 and a 2.4 pre-release. Additionally, the Linux and FreeBSD ports are fully interoperable under TBRPF Version 1. The neighbor discovery protocol described in the current version of the draft has been implemented on Linux. 14. Patent Rights Statement SRI International has filed one or more patents protecting the inven- tions described in this submission. If SRI's submission (or portions thereof) is accepted and becomes part of the IETF standard, then SRI will grant royalty-free permission under such patents for both com- mercial and non-commercial uses, to the extent necessary for compli- ance with the standard. Any aspects or variants of SRI's submission that are not included in the IETF standard and/or are not necessary for compliance with the standard may require an additional license from SRI under terms to be negotiated by the parties. 15. Acknowledgments The authors would like to thank ASEO for funding this work, ONR for funding the Linux port, and the following people for helping in the development of TBRPF: Mark G. Lewis, Yonael Gorfu, and Julie S. Wong. 16. References [1] Bhargav Bellur and Richard G. Ogier. A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks. Proc. IEEE INFOCOM '99, New York, March 1999. [2] Scott Bradner. Key words for use in RFCs to Indicate Require- ment Levels. RFC 2119, March 1997. [3] M. Scott Corson and Joe Macker. Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Con- sideration. RFC 2501, 1999. Bellur, Ogier, and Templin Expires 6 March 2002 [Page 59] INTERNET-DRAFT TBRPF 6 September 2001 [4] J.J. Garcia-Luna-Aceves and M. Spohn. Efficient Routing in Packet-Radio Networks Using Link-State Information. Proc. IEEE WCNC '99, September 1999. [5] C. Hornig. Standard for the Transmission of IP Datagrams over Ethernet Networks. STD0041, April 1984. [6] David B. Johnson and David A. Maltz. Protocols for Adaptive Wireless and Mobile Networking. IEEE Personal Communications, Vol. 3, No. 1, pp 34-42, February 1996. [7] Richard G. Ogier. Efficient Routing Protocols for Packet-Radio Networks Based on Tree Sharing. Proc. Sixth IEEE Intl. Workshop on Mobile Multimedia Communications (MOMUC'99), November 1999. [8] Charles E. Perkins, Elizabeth M Royer, and Samir R. Das. Ad Hoc On-Demand Distance Vector (AODV) Routing. draft-ietf-manet- aodv-05.txt, March 2000 (work in progress). [9] D.C. Plummer. An Ethernet address resolution protocol: Or con- verting network protocol addresses to 48.bit Ethernet addresses for transmission on Ethernet hardware. RFC 826, November 1982. [10] J. Postel. Internet Protocol. RFC 791, September 1981. [11] J. Postel. User Datagram Protocol. RFC 768, August 1980. [12] J. Reynolds and J. Postel. Assigned Numbers. RFC 1700, October 1994. [13] Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, ISO/IEC Std. 8802-11, ANSI/IEEE Std 802.11, 1999. [14] An Internet MANET Encapsulation Protocol (IMEP) Specification, draft-ietf-manet-imep-spec-01.txt [15] S. Deering and R. Hinden. Internet Protocol Version 6 (IPv6) Specification. RFC 2460, December 1998. [16] S. Corson. MANET Routing Protocol Applicability Statement, draft-ietf-manet-appl-00.txt, November 1998 (work in progress). [17] J. Moy. OSPF Version 2. RFC 1583, March 1994. [18] P. Jacquet et al. Optimized Link State Routing Protocol, draft-ietf-manet-olsr-04.txt, March 2001 (work in progress). Bellur, Ogier, and Templin Expires 6 March 2002 [Page 60] INTERNET-DRAFT TBRPF 6 September 2001 Authors' Addresses Bhargav Bellur SRI International 333 Ravenswood Ave. Menlo Park, CA 94025 USA Phone: +1 650 859-6335 Fax: +1 650 859-4812 Email: bhargav@erg.sri.com Richard Ogier SRI International 333 Ravenswood Ave. Menlo Park, CA 94025 USA Phone: +1 650 859-4216 Fax: +1 650 859-4812 Email: ogier@erg.sri.com Fred L. Templin SRI International 333 Ravenswood Ave. Menlo Park, CA 94025 USA Phone: +1 650 859-3144 Fax: +1 650 859-4812 Email: templin@erg.sri.com Bellur, Ogier, and Templin Expires 6 March 2002 [Page 61]