INTERNET-DRAFT Bhargav Bellur Richard G. Ogier Fred L. Templin SRI International 2 March 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 2 September 2001 [Page i] INTERNET-DRAFT TBRPF 2 March 2001 Contents Status of This Memo ............................................... i Abstract .......................................................... i 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 ................... 4 5. Neighbor Discovery ............................................. 6 5.1. Overview .................................................. 7 5.2. Neighbor Table ............................................ 8 5.3. Sending HELLO Messages .................................... 9 5.4. Processing a Received HELLO Message ....................... 9 5.5. Processing a Received UPDATE REQUEST Message .............. 10 5.6. Processing a received UPDATE REPLY message ................ 10 5.7. Sending an UPDATE REQUEST message ......................... 11 5.8. Expiration of the Timer nbr_life .......................... 11 5.9. Events Causing a Link to be Declared Down ................. 11 6. Reliable Delivery to Neighbors ................................. 12 6.1. Reliable, Sequenced Delivery Using NACKs .................. 12 6.2. Reliable Delivery Using ACKs .............................. 13 7. TBRPF-PT ....................................................... 14 7.1. Conceptual Data Structures and Messages ................... 15 7.2. Operation of TBRPF-PT ..................................... 16 7.2.1. Computing the Source Tree ............................ 17 7.2.2. Generating Tree Updates .............................. 17 7.2.3. Updating Parents ..................................... 18 7.2.4. Sending NEW PARENT Messages .......................... 18 7.2.5. Processing TREE UPDATE Messages ...................... 18 7.2.6. Processing NEW PARENT Messages ....................... 19 7.2.7. Processing a New Neighbor ............................ 19 7.2.8. Processing a Lost Neighbor ........................... 20 7.2.9. Packet Forwarding .................................... 20 7.3. Pseudocode for TBRPF-PT ................................... 20 7.4. Configurable Parameters ................................... 23 Bellur, Ogier, and Templin Expires 2 September 2001 [Page ii] INTERNET-DRAFT TBRPF 2 March 2001 8. TBRPF-FT ....................................................... 23 8.1. Conceptual Data Structures and Messages ................... 24 8.2. Operation of TBRPF-FT ..................................... 26 8.3. Pseudocode for TBRPF-FT ................................... 30 8.4. Configurable Parameters ................................... 34 9. Application of TBRPF In Mobile Ad-hoc Networks (MANETs) ........ 34 9.1. Data Link Layer Assumptions ............................... 35 9.2. Internetworking Assumptions ............................... 36 9.3. Address Resolution Extensions for TBRPF Neighbor Discovery. 36 10. TBRPF Packets and TBRPF Protocol Messages ..................... 37 10.1. TBRPF Packet Header ...................................... 39 10.2. TBRPF Packet Body ........................................ 42 11. IANA Considerations ........................................... 69 12. Security Considerations ....................................... 70 13. Implementation Status ......................................... 70 Acknowledgments ................................................... 70 References ........................................................ 70 Bellur, Ogier, and Templin Expires 2 September 2001 [Page iii] INTERNET-DRAFT TBRPF 2 March 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 2 September 2001 [Page 1] INTERNET-DRAFT TBRPF 2 March 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 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. - 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 2] INTERNET-DRAFT TBRPF 2 March 2001 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. 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. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 3] INTERNET-DRAFT TBRPF 2 March 2001 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 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 4] INTERNET-DRAFT TBRPF 2 March 2001 * 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. * 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?) Bellur, Ogier, and Templin Expires 2 September 2001 [Page 5] INTERNET-DRAFT TBRPF 2 March 2001 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. * 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, designed for mobile ad-hoc networks. The purpose of the protocol is to allow each node in the network to quickly detect the neighboring Bellur, Ogier, and Templin Expires 2 September 2001 [Page 6] INTERNET-DRAFT TBRPF 2 March 2001 nodes with which the node has a direct and symmetric 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 symmetric link to some neigh- bor no longer exists. TBRPF neighbor discovery operates correctly even under the following harsh conditions: (1) an asymmetric (unidirectional) link can exist between any two nodes at any time, (2) link states can change fre- quently due to mobility and interference, and (3) the channel is noisy so that not all transmitted packets are successfully received by all neighbors. The main advantage of TND over existing neighbor discovery protocols, such as the one used by OSPF [OSPF], is that the average size of a HELLO message is much smaller, resulting in reduced message overhead. In addition, since HELLO messages are smaller, they can be sent more frequently, resulting in a faster response to topology changes. 5.1. Overview Each node transmits a HELLO message periodically, every HELLO_INTERVAL seconds. Each HELLO message contains a list of node IDs, called the neighbor request list, which includes neighbors from which HELLO messages have recently been heard but for which a 2-way link has not yet been established. (Message formats are given in Section 10.2.) Upon receiving a HELLO message from a neighbor that has not been heard from recently, a node includes the neighbor's ID in each transmitted HELLO message until a 2-way indication (defined below) is received from the neighbor, but for at most NBR_HOLD_TIME seconds (typically equivalent to 3 HELLO messages). A 2-way indication can be either a received HELLO that includes the node's own ID, or an UPDATE REQUEST message. Upon receiving a 2-way indication, the node sends an UPDATE REQUEST message to the new neighbor and waits for the neighbor to respond with an UPDATE REPLY message. The UPDATE REPLY message serves two purposes: (1) to confirm that the other node agrees that the link is 2-way, and (2) for the exchange of topology information. Depending on the routing protocol, an update for the new link may be generated upon receiving a 2-way indication, or (similarly to OSPF) after topology information is exchanged (i.e., the UPDATE REPLY is received). In this section, an "update" refers to a TREE UPDATE in TBRPF-PT or an LSU in TBRPF-FT. Upon receiving a 2-way indication from a new neighbor, the node copies the current NACK sequence number (NSEQ) of the neighbor from the packet, and thus becomes capable of sending a NACK when a missed sequence number is detected. (The use of NSEQ is described in Sec- tion 6.) Bellur, Ogier, and Templin Expires 2 September 2001 [Page 7] INTERNET-DRAFT TBRPF 2 March 2001 If an UPDATE REQUEST message is retransmitted MAX_NUM_RXMT times to a given neighbor, and no UPDATE REPLY is received from the neighbor, the link is declared down and an update reporting the link failure is sent reliably to all neighbors (using NACKs). If the neighbor that was sent the UPDATE REQUEST message has already received a 2-way indication, then it is capable of sending NACKs and will thus either receive the update, or will declare the link down after sending a NACK MAX_NUM_RXMT times, or will stop hearing HELLO messages and thus declare the link down after NBR_HOLD_TIME seconds. In this manner, both nodes will agree that the link is up if it is 2-way, and will otherwise agree that the link is down. If a link (i,j) has been up (2-way) for some time and then becomes unidirectional from node i to node j, then node i will stop hearing HELLO messages from node j, will declare the link down after NBR_HOLD_TIME seconds, and will send an update reporting the link failure. The neighbor will either receive the update or will declare the link down after sending a NACK MAX_NUM_RXMT times. In this manner, both nodes will agree that the link is down. The different events that result in a link being declared down are listed in Sec- tion 5.9. The contents and formats of the UPDATE REQUEST and UPDATE REPLY mes- sages depend on the routing protocol, and are different for the FT and PT modes of TBRPF. These formats, and the specific procedures for sending and processing these messages, are given in the sections describing each mode of TBRPF. For the FT mode, the UPDATE REQUEST and UPDATE REPLY messages are the same as the NEW PARENT and NEW PARENT REPLY messages, respectively. This section describes the gen- eral neighbor discovery procedure that is common to both the FT and PT modes of TBRPF. 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 of the link to node j, which can be LOST, 1-WAY, 2-WAY, or SYNC. 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_request_time(j) - The amount of remaining time (in seconds) during which the ID of node j is included in each transmitted HELLO message. Set to NBR_HOLD_TIME if a HELLO is received from node j when nbr_level(j) = LOST. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 8] INTERNET-DRAFT TBRPF 2 March 2001 The table entry for a neighbor j may be deleted at any time after nbr_level(j) becomes LOST. 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. 1-WAY The link is 1-way. A HELLO message was received recently from node j, but the link is not 2-way. 2-WAY The link is 2-way. Node i recently received from node j either a HELLO message that contains the ID of node i, or an UPDATE REQUEST message. SYNC An UPDATE REPLY message has been received from node j. The topology information at the two nodes is consistent for routes that pass through node j. Depending on the routing protocol, an update reporting that the link (i,j) is UP can be generated either when nbr_level(j) changes to 2- WAY or when it changes to SYNC. 5.3. Sending HELLO Messages Each node sends a HELLO message periodically every HELLO_INTERVAL seconds, possibly with a small jitter. Each HELLO message includes a (possibly empty) list (called the neighbor request list) including the identities of all neighbors j such that nbr_level(j) = 1-WAY and nbr_request_time(j) has not expired. In this manner, upon receiving a HELLO message from a neighbor that has not been heard from recently, the neighbor's ID is included in each HELLO message for at most NBR_HOLD_TIME seconds (sooner if a 2-way indication is received from the neighbor). 5.4. Processing a Received HELLO Message Upon receiving a HELLO message from node j, node i performs the fol- lowing steps: 1. If a neighbor table entry does not exist for node j, create one with nbr_level(j) = LOST (temporarily). Bellur, Ogier, and Templin Expires 2 September 2001 [Page 9] INTERNET-DRAFT TBRPF 2 March 2001 2. If nbr_level(j) = LOST, then set nbr_level(j) = 1-WAY and nbr_request_time(j) = NBR_HOLD_TIME. 3. Set nbr_life(j) = NBR_HOLD_TIME. 4. If the ID of node i appears in the HELLO message, and nbr_level(j) is not 2-WAY, then: a. Set nbr_level(j) = 2-WAY b. Send an UPDATE REQUEST message to node j (see the section below on sending an UPDATE REQUEST message) c. Copy the current NACK sequence number (NSEQ) of node j from the TBRPF packet header. d. An update reporting that link (i,j) is UP MAY be generated at this time. 5.5. Processing a Received UPDATE REQUEST Message Upon receiving an UPDATE REQUEST message from node j, node i performs the following steps: 1. If nbr_level(j) is LOST or 1-WAY, then (the UPDATE REQUEST is a 2-WAY indication): a. Set nbr_level(j) = 2-WAY b. Send an UPDATE REQUEST message to node j c. Copy the current NACK sequence number (NSEQ) of node j from the TBRPF packet header. d. An update reporting that link (i,j) is UP MAY be generated at this time. 2. Send an UPDATE REPLY message to node j (same as NEW PARENT REPLY message for the FT mode, details are given in the sections for TBRPF-FT and TBRPF-PT). 5.6. Processing a Received UPDATE REPLY Message Upon receiving an UPDATE REPLY message (or a NEW PARENT REPLY message for the FT mode) from node j, node i performs the following steps: Bellur, Ogier, and Templin Expires 2 September 2001 [Page 10] INTERNET-DRAFT TBRPF 2 March 2001 1. Set nbr_level(j) to SYNC. 2. An update reporting that link (i,j) is UP is generated if not already generated when the link became 2-WAY. 3. Process the message as described in the sections for TBRPF-FT and TBRPF-PT. 5.7. Sending an UPDATE REQUEST message The contents of the UPDATE REQUEST message depends on the routing protocol used. For TBRPF-FT, it is the same as a NEW PARENT message. An UPDATE REQUEST message can be delayed, typically until the next HELLO message is scheduled, in order to allow message aggregation. An UPDATE REQUEST for a given neighbor j is retransmitted after RXMT_INTERVAL if an UPDATE REPLY has not yet been received. Node i performs the following steps if an UPDATE REQUEST has been transmitted MAX_NUM_RXMT times to node j with no reply: 1. Generate an update reporting that link (i,j) is DOWN. 2. Set nbr_level(j) = LOST and nbr_life(j) = 0. In Step 1, if node j has received a 2-WAY indication, then it is capable of sending NACKs and will therefore receive the update correctly, or will declare the link DOWN after sending MAX_NUM_RXMT NACKs for this update. If node j receives the update, it will declare link (j,i) DOWN. 5.8. Expiration of the Timer nbr_life The timer nbr_life(j) is set to NBR_HOLD_TIME whenever a HELLO is received from node j. If nbr_life(j) expires (becomes zero), node i performs the following steps: 1. If nbr_level(j) is 2-WAY or SYNC, generate an update reporting that link (i,j) is DOWN. 2. Set nbr_level(j) = LOST. 5.9. Events Causing a Link to be Declared Down The following events at node i result in link (i,j) being declared DOWN, if it is currently UP. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 11] INTERNET-DRAFT TBRPF 2 March 2001 1. No HELLO message is received from node j for NBR_HOLD_TIME seconds. 2. An update is received from node j reporting that link (j,i) is DOWN. 3. An UPDATE REQUEST or NEW PARENT message is transmitted MAX_NUM_RXMT times to node j, and no reply is received within RXMT_INTERVAL of the last transmission. 4. A NACK is sent to node j for the same message MAX_NUM_RXMT times, and the message is not received within RXMT_INTERVAL of the last NACK. 5. A failure notification is received from the link layer (e.g., based on the maximum number of retransmissions being reached for a data packet). In each of these cases, an update is generated reporting the link failure. In most cases, this update can be delayed (typically until the next HELLO message) to allow message aggregation. However, since a failure notification from the link layer implies that the link is currently being used for data traffic, in this case the update is sent immediately, subject to the minimum time between updates (MIN_UPDATE_INTERVAL). 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 12] INTERNET-DRAFT TBRPF 2 March 2001 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. 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 13] INTERNET-DRAFT TBRPF 2 March 2001 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. 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 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 14] INTERNET-DRAFT TBRPF 2 March 2001 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 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. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 15] INTERNET-DRAFT TBRPF 2 March 2001 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. 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 16] INTERNET-DRAFT TBRPF 2 March 2001 messages 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 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 17] INTERNET-DRAFT TBRPF 2 March 2001 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. 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 18] INTERNET-DRAFT TBRPF 2 March 2001 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 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 19] INTERNET-DRAFT TBRPF 2 March 2001 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. 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. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 20] INTERNET-DRAFT TBRPF 2 March 2001 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 with minimum d(u). 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 (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).}}} Bellur, Ogier, and Templin Expires 2 September 2001 [Page 21] INTERNET-DRAFT TBRPF 2 March 2001 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 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. } Bellur, Ogier, and Templin Expires 2 September 2001 [Page 22] INTERNET-DRAFT TBRPF 2 March 2001 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). } 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 23] INTERNET-DRAFT TBRPF 2 March 2001 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 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 24] INTERNET-DRAFT TBRPF 2 March 2001 (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. 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. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 25] INTERNET-DRAFT TBRPF 2 March 2001 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 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, Bellur, Ogier, and Templin Expires 2 September 2001 [Page 26] INTERNET-DRAFT TBRPF 2 March 2001 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). 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 27] INTERNET-DRAFT TBRPF 2 March 2001 (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. 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 28] INTERNET-DRAFT TBRPF 2 March 2001 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. 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 29] INTERNET-DRAFT TBRPF 2 March 2001 originating 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 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) Bellur, Ogier, and Templin Expires 2 September 2001 [Page 30] INTERNET-DRAFT TBRPF 2 March 2001 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. 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. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 31] INTERNET-DRAFT TBRPF 2 March 2001 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). 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) { Bellur, Ogier, and Templin Expires 2 September 2001 [Page 32] INTERNET-DRAFT TBRPF 2 March 2001 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 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 */ Bellur, Ogier, and Templin Expires 2 September 2001 [Page 33] INTERNET-DRAFT TBRPF 2 March 2001 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){ 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 (MANETs) 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 34] INTERNET-DRAFT TBRPF 2 March 2001 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 chan- nel. (An example is the IEEE 802.11 Distributed Coordination Function (DCF) [13], in which the mobile nodes collectively arbitrate channel access via a Carrier Sense, Multiple Access with Collision Avoidance (CSMA/CA) strategy for unicast, multicast and broadcast packet transmissions.) Although applicable across a much broader field of use, TBRPF is particularly well suited for carrying routing informa- tion that supports the standard DARPA Internet protocols (IPv4) [10] as per current practices, as advocated by the IETF MANET working group [RFC2501]. We therefore target this document toward the appli- cation of TBRPF over MANETs that observe these current practices. In the following sections, we discuss assumptions for the data link layer, Internetworking assumptions, and address resolution extensions for TBRPF neighbor discovery in a MANET environment. 9.1. Data Link Layer Assumptions We assume a data link layer broadcast channel with multiple access capabilities, such that nodes wishing to transmit unicast, broadcast and/or multicast packets must arbitrate with other nodes for channel access before doing so. We further assume that packets transmitted over the data link layer broadcast channel will be received by only a proper subset of the collection of nodes on the multiple access data link, due to wireless interface range limitations, terrain features, and other hidden terminal conditions incurred in a mobile environ- ment. We consider a pair of nodes (A and B) to have a bidirectional link (or simply "link") if and only if both node A can receive pack- ets sent from node B and node B can receive packets sent from node A at a given instant in time. While TBRPF can be readily applied to a fixed network (in which no link state changes due to node mobility occur) such a static network configuration merely represents a simplified case of the general mobile ad-hoc network model. We therefore assume a highly dynamic mobile environment at the data link layer, in which link state changes occur frequently and rapidly. We further assume a data link layer addressing scheme that supports broadcast, multicast and uni- cast addressing with best-effort (not guaranteed) delivery services between nodes with bidirectional links. Finally, we assume that each node in the MANET is assigned a unique data link layer unicast address. While uniqueness for data link layer address assignments is difficult to guarantee, 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. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 35] INTERNET-DRAFT TBRPF 2 March 2001 9.2. Internetworking Assumptions We assume that each MANET router [14] is assigned at least one unique IPv4 address, but may have multiple interfaces; each identified by one or more IPv4 address. For the purpose of TBRPF protocol message exchanges, each MANET router is identified by a unique Router ID (RID). While not a requirement, the RID is typically selected from one of the IPv4 addresses assigned to one of the MANET router's interface(s). As with data link level addressing assumptions described in the previous section, we require each node to provide a means for duplicate IPv4 address detection. The next section provides a method for duplicate IPv4 address detection, but methods for dupli- cate IPv4 address deconfliction are beyond the scope of this docu- ment. Since each MANET router participates in the TBRPF neighbor discovery process, TBRPF provides a means for automatic (rather than on-demand) address resolution. Thus, the requirement for on-demand discovery through the Address Resolution Protocol (ARP) [9] is obviated. More- over, we suggest that ARP need not be used on TBRPF interfaces, since the ARP discovery process adds unnecessary broadcast traffic overhead and the on-demand table management policies in most ARP implementa- tions (e.g. flushing entries which have not been used for data traffic within a certain timeout period) conflict with the automatic nature of TBRPF neighbor discovery. We further assume that each MANET router supports the multi-hop relay paradigm; in other words, each MANET router must be prepared to provide a third-party relay service as dictated by the instantaneous MANET topology. Finally, we note that the multi-hop relay paradigm occurs at a lower network sub-layer than standard Internet routing. The multi-hop relay paradigm provides intra-MANET forwarding services which may result in multiple hops within a single logical IPv4 subnet. Conversely, standard Internet routing provides forwarding between distinct IPv4 networks only. 9.3. Address Resolution Extensions for TBRPF Neighbor Discovery TBRPF employs a neighbor discovery protocol that dynamically estab- lishes bidirectional links and detects bidirectional link failures through the periodic transmission of HELLO messages. To enable an automatic address resolution capability, a TBRPF router MUST ensure the following information is encoded in each packet that contains a HELLO message: - the unicast data link address of the sending interface - the primary unicast IPv4 address of the sending interface The choice of whether TBRPF neighbor discovery messages are sent as transport level, network level or data link-level entities is an implementation and/or configuration dependent decision that must be Bellur, Ogier, and Templin Expires 2 September 2001 [Page 36] INTERNET-DRAFT TBRPF 2 March 2001 consistent among all MANET routers in the network. In the case that HELLOs are sent as UDP/IPv4 packets, the above information is automatically encoded in the headers of the UDP/IPv4 packets that carry the HELLO messages. In other cases, mechanisms are provided to encode this information within the HELLO message body as described in Section 10.2.2. Given the above information in HELLO messages, a MANET router that forms a bidirectional link to a neighbor can use TBRPF address resolution to simply bind the neighbor's IPv4 address to the neighbor's data link level address UNLESS duplicate address detection determines that the IPv4 address is already in use. A duplicate address is detected when: 1. Two or more nodes in the MANET that are actively sending HELLOs are using the same IPv4 address. 2. An existing node in the MANET has changed its data link layer address. 3. A new node is now using the IPv4 address of a former node that has ceased sending HELLOs - perhaps indicating that the former node MAY have recently left the MANET. In all cases, the receiver MUST NOT form a link with the MANET router that is sending the duplicate address. In case 1, the receiver SHOULD print some form of "duplicate IPv4 address detected" warning to the console and/or system log file. In case 2, the MANET router will cease sending HELLO messages with its *old* data link address and begin sending HELLO messages with its *new* data link address. Neigh- bors of this MANET router will perceive messages containing the new data link address as originating from a *different* node that uses a duplicate IPv4 addresses UNTIL the existing state information con- taining the *old* data link address expires. But, since the MANET router no longer sends HELLO messages using its *old* data link address, state expiration is guaranteed. At this point, neighbors will re-negotiate their bidirectional links to the MANET router and cache its *new* data link address to IPv4 address resolution. Case 3 is handled in an identical manner to case 2. 10. TBRPF Packets and TBRPF Protocol Messages TBRPF protocol messages (or simply, TBRPF *messages*) encode the individual TBRPF protocol primitives described in earlier sections. TBRPF messages are embedded within the bodies of TBRPF *packets*, which may contain one or more TBRPF message(s) as described in the following section. All TBRPF packets are sent to the "All_TBRPF_Neighbors" multicast address. Each packet sent to the "All_TBRPF_Neighbors" multicast address is accepted by all TBRPF Bellur, Ogier, and Templin Expires 2 September 2001 [Page 37] INTERNET-DRAFT TBRPF 2 March 2001 routers that physically receive the packet, whether or not they have established a link to the sender via TBRPF neighbor discovery. Pack- ets sent to the "All_TBRPF_Neighbors" multicast address MUST NOT be multi-hopped to MANET routers that are not single-hop neighbors of the sender. See: "IANA Considerations" for more information. Since packets sent to the "All_TBRPF_Neighbors" multicast address 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). Since packet loss due to link failure, interference, etc can occur, implementations MUST choose a maximum TBRPF packet length that is less than the interface MTU to avoid IPv4 fragmentation and reassembly (*). IN ALL CASES, the absolute maximum TBRPF packet length for packets sent on a particular interface is calculated as MIN(interface MTU, 64KB). (*) Although it may seem reasonable to allow implementations to send larger-than-MTU sized TBRPF packets (up to the maximum of 64KB) with the understanding that such packets will incur IPv4 fragmentation, it should be noted that the loss of ANY fragment will result in the loss of the ENTIRE TBRPF packet, which must then be retransmitted. Thus, to avoid the unnecessary retransmis- sion of data, we mandate IPv4 fragmentation avoidance as described above. For the application of TBRPF in IPv4 MANETs, implementations MUST send and receive TBRPF packets via the User Datagram Protocol (UDP) [11] as the default. This approach requires an official UDP service port number registration (see: IANA Considerations). The use of UDP/IPv4 provides: - A UDP message length field - UDP checksum facilities - Simple application level access for routing daemons - IPv4 multicast addressing - Internet security mechanisms with policy-based address filtering Implementations MAY OPTIONALLY employ an alternate data delivery ser- vice other than UDP/IPv4 for the transmission of some or all TBRPF packets. The choice of an alternate data delivery service 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, message options, one or more TBRPF message(s) and padding options as needed. As noted above, the total length of all packet components must be less than the max- imum TBRPF packet length as calculated by MIN(interface MTU, 64KB). Bellur, Ogier, and Templin Expires 2 September 2001 [Page 38] INTERNET-DRAFT TBRPF 2 March 2001 In the following sections, we describe the elements of a TBRPF packet in detail. 10.1. TBRPF Packet Header TBRPF packet headers are variable-length (minimum of two octets) with length determined by the sense of "flag" bits found in the first octet. Implementations MUST ensure that the first octet of the TBRPF packet header is aligned on an even 8-octet boundary. (The 8-octet alignment requirement 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.) IT SHOULD BE NOTED 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 detailed description of the individual 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 2 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - -+ |C|L|R|Z| Vers | Current NSEQ | Extension Fields (optional) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - -+ Flags (4 bits): Three flag bits (C, L, R) that 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) specifies alignment/compression considerations for the TBRPF message. The flag bits and their usage are described in detail below: C - Checksum Field Included: When the underlying delivery service provides a checksum facil- ity (e.g. UDP/IPv4), a sender normally sets C = '0' to indicate that NO checksum field is included in the TBRPF packet header. If C = '0', the sender MUST enable the checksum facility pro- vided by the underlying delivery service. If the underlying delivery service DOES NOT provide a checksum facility (or, if the sender chooses to avoid the underlying delivery service checksum facility) the sender MUST set C = '1' to indicate that a 16-bit TBRPF checksum field follows immedi- ately after the "Current LSEQ" field. When C = '1', the sender MUST calculate the checksum of the TBRPF packet in the manner described in [11] and write the resulting sum into the 16-bit message checksum field. The checksum is calculated across ALL Bellur, Ogier, and Templin Expires 2 September 2001 [Page 39] INTERNET-DRAFT TBRPF 2 March 2001 data bytes in the packet header, header extension fields, and packet body, but DOES NOT include a pseudo-header of the under- lying delivery service. A receiver 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 TBRPF checksum field as described in [11] to ensure TBRPF packet data integrity. When C = '1', checksum verification is required WHETHER OR NOT the underlying delivery service also provides a checksum facility. The receiver MUST discard any TBRPF packet that contains an incorrect checksum. Additionally, the receiver MUST discard any TBRPF packet that is not protected by either a checksum facil- ity provided by the underlying delivery service or a checksum field encoded by the sender in the TBRPF packet header. L - Length Field Included: When the underlying delivery service provides a length field (e.g. UDP/IPv4), a sender SHOULD set L = '0' to indicate that NO TBRPF packet length field is included. If the underlying delivery service DOES NOT provide a length field, the sender MUST set L = '1' to indicate that a 16-bit unsigned integer TBRPF packet length field follows immediately after any previ- ous 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.) A receiver MUST examine the L bit to determine whether a length field is included. If a length field is included, the receiver must convert the length field 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, the receiver MUST verify that the length pro- vided by the underlying delivery service matches the length provided by the length field in the TBRPF packet header. (The receiver MUST discard any TBRPF packet in which the two lengths do not match.) Similarly, the receiver MUST discard any TBRPF packet if neither the underlying delivery service nor the TBRPF packet header provide packet length. Since the TBRPF packet header is guaranteed to begin on an even 8-octet boundary, and since all preceding header fields are guaranteed to end on an even 2-octet boundary, the length field is guaranteed to begin on an even 2-octet boundary. Thus, software MAY access the 2-octet length field as a single 16-bit unsigned integer rather than two independent 8-bit integers. (See the following sections for more information regarding "natural" N-bit word alignment.) Bellur, Ogier, and Templin Expires 2 September 2001 [Page 40] INTERNET-DRAFT TBRPF 2 March 2001 R - Reserved: The R bit is RESERVED for future use. The R bit may be used in the future to indicate that an additional header extension field follows immediately after any previous header fields. Z - Message Alignment/Compression: If the Z bit is '0', the sender MUST align 64-bit, 32-bit and 16-bit words within the TBRPF packet body on on "natural" boun- daries. (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.) If the Z bit is '0', the sender MUST use Pad1 and/or PadN padding options (see the description of these options in the next section) where necessary to ensure natural word alignment. If the Z bit is '1', the sender MAY OPTIONALLY omit padding in the interest of providing compression. Since the omission of padding options may result in 64-bit, 32-bit and 16-bit words aligned non-integral byte boundaries, a receiver MUST NOT pro- cess such multi-octet words as atomic data units if Z is '1'. Instead, the receiver must process multi-octet words "byte-by- byte" as 8-octet, 4-octet and 2-octet arrays, respectively. Due to the considerable additional overhead for processing non-aligned words, it is RECOMMENDED that senders set the Z bit to '0' and insert Pad1 and PadN options where necessary. How- ever, it may be preferable in some contexts to set the Z bit to '1' in order to save transmission overhead at the cost of extra processing. Receivers MUST be able to process both aligned and compressed packets. Version (4 bits): The TBRPF protocol version field provides a transition mechanism for future versions of the TBRPF protocol. Also provides a sanity check for host software to identify bogus messages purporting to be TBRPF protocol messages. 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. Implementations which transmit packets as defined in the previous draft version set the value TBRPFVERSION_1 in the version field. TBRPF version 2 implementations MAY OPTIONALLY provide backwards compatibility for TBRPFVERSION_1 packets. Current NSEQ (8 bits): The current NACK sequence number. Allows each neighbor to Bellur, Ogier, and Templin Expires 2 September 2001 [Page 41] INTERNET-DRAFT TBRPF 2 March 2001 determine the sequence numbers of transmitted NACKable messages that it did not receive. For further information, see Section 6.1: "Reliable, Sequenced Delivery Using NACKs". 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 ele- ments 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 will 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 for- mat: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -+- - - - | TYPE |P|L| LEN(0) | LEN(1) | VALUE +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -+- - - - TYPE (6 bits): A 6-bit identifier that gives the type of the T_TLV Element. NOTE: Although the TYPE field is in the first octet of the T_TLV Element, the TYPE field itself may NOT always begin on an n-octet natural word boundary. Following sections will describe TYPE- dependent alignment considerations for T_TLV Elements. P - Partial message bit (1 bit): A 1-bit flag; if P = '0', this T_TLV Element contains either a complete TBRPF message in its entirety, or the final segment of a TBRPF message that spans multiple T_TLV Elements. If P = '1', this T_TLV Element contains a partial segment of a TBRPF message that spans multiple T_TLV Elements. L - Length extension bit (1 bit): A 1-bit flag; if L = '0', the T_TLV Element is said to be in SHORT format, and the LEN field is a single octet. If L = '1', the T_TLV Element is said to be in LONG format, and the LEN field comprises 2 octets. LEN (8/16 bits): The length of the VALUE field, in octets. Note that this length excludes the lengths of the TYPE and LEN fields themselves. If L = '0', the T_TLV Element is in SHORT format, and 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 42] INTERNET-DRAFT TBRPF 2 March 2001 LEN fields in SHORT format is 255 octets.) If L = '1', the T_TLV Element is in LONG format, and 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', the length calculated by the above equation MUST be within the range from 0 - 65532. (Thus, the maximum length of the T_TLV Element *including* the TYPE and LEN fields in LONG format is 65535 octets.) When LONG format is used, implementations MUST NOT access the two-octet LEN field as a 16-bit unsigned integer, since the first octet of the LEN field is NOT guaranteed to fall on a natural 16-bit word alignment. 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 and process that element prior to processing all preceding elements. Also as described in [15], 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 Ele- ment is specified using the notation xn+y, meaning the element type must appear at an integer multiple of x octets from the start of the TBRPF packet header, plus y octets. For example: 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. When the Z bit in the TBRPF packet header is '0', the insertion of padding options to satisfy the alignment requirements of T_TLV Ele- ments is MANDATORY. When Z = '1', padding options MAY be omitted and natural word alignment is NOT guaranteed. 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. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 43] INTERNET-DRAFT TBRPF 2 March 2001 10.2.1. T_TLV Padding Options (TYPE = 0 thru 1) As described in [15], there are two padding options which senders insert where necessary to satisfy the alignment requirements of 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', pad- ding options MUST be inserted to ensure that the alignment require- ments 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| +-+-+-+-+-+-+-+-+ Pad1 is indicated by TYPE = 0. The P, L bits MUST be '0', and the LEN and VALUE fields are omitted. The Pad1 option is used to insert 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - PadN is indicated by TYPE = 1. PadN is used to insert 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. 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 Bellur, Ogier, and Templin Expires 2 September 2001 [Page 44] INTERNET-DRAFT TBRPF 2 March 2001 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 RID header option is indicated by TYPE = 2. 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 significant byte first). Senders MUST encode the RID 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.) If a sender's RID and the sender's source address as it appears in the IPv4 header are one and the same, NO RID option is required and 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 an 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, a receiver MUST accept the RID that appears in the first such option and skip past any subsequent RID options. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 45] INTERNET-DRAFT TBRPF 2 March 2001 Alias Address (ALIASADDR) option (TYPE = 3) - Alignment requirement: 4n+3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 3 |AF | NUMADDR | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Alias Address (1) (N octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Alias Address (2) (N octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Alias Address (NUMADDR) (N octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The ALIASADDR header option is indicated by TYPE = 3. The P, L bits are used to encode a 2-bit Address Family (AF) field. The LEN field is used to contain a value (NUMADDR) which gives the number of Alias Addresses of the specific Address Family given in the AF field encoded back-to-back. (The length of each encoded Alias Address (N) is inferred from the value in the AF field as specified below.) The VALUE field contains NUMADDR many N-octet Alias Address encoded back-to-back; each in network byte order (least significant byte first). The following AF field bit values are defined, where the bits shown are ordered as MOST significant bit followed by LEAST signifi- cant bit: (Note that for AF values '00' and '01', each ALIASADDR is guaranteed to begin on a natural 4-octet boundary if the 'Z' bit in the TBRPF packet header is '0'.) Senders MAY OPTIONALLY encode the ALIASADDR option when they wish to publish one or more Alias Addresses that differ from their Router ID (RID). 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| NUMADDR | MAC(1) (N octets) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - ~ ... ~ - - - - - - - - +-+-+-+-+-+-+-+-+ MAC(NUMADDR) (N octets) | (May end on an arbitrary boundary) - - - - - - - - +-+-+-+-+-+-+-+-+ The MACADDR header option is indicated by TYPE = 4. The P, L bits are used to encode a 2-bit "Format" (FMT) field. The LEN field is used to Bellur, Ogier, and Templin Expires 2 September 2001 [Page 46] INTERNET-DRAFT TBRPF 2 March 2001 contain a value (NUMADDR) which gives the number of MAC addresses of the specific Format given in the FMT field encoded back-to-back. (The length of each encoded MAC Address (N) is inferred from the value in the Format field as specified below.) The VALUE field contains NUMADDR-many N-octet MAC addresses encoded back-to-back in network byte order (least significant byte first). The following FMT field bit values are defined where the bits shown are ordered as MOST sig- nificant bit followed by LEAST significant bit: commonly referred to as "EUI-48 Format" commonly referred to as "EUI-64 Format" Senders MUST encode a MACADDR option when the MAC address cannot be derived directly from header information transmitted by the underly- ing 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 current UNDEFINED. A receiver MUST accept the first such MAC address encoded in a MACADDR option and MAY OPTIONALLY cache the values encoded in any subsequent MACADDRs encoded 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: NONACKable Block (NONACKBLK) option (TYPE = 8) - Alignment requirement: none +-+-+-+-+-+-+-+-+ | 8 |0|0| +-+-+-+-+-+-+-+-+ The NONACKBLK message option is indicated by TYPE = 8. The P, L bits MUST be '0', and both the LEN and VALUE fields are omitted. The Bellur, Ogier, and Templin Expires 2 September 2001 [Page 47] INTERNET-DRAFT TBRPF 2 March 2001 presence of a NONACKBLK message option delineates the beginning of a "NONACK Block" that consists of one or more T_TLV messages for which neither NACK nor ACK messages occur. We refer to this class of T_TLV messages as "NONACKable". The initial segment of the TBRPF packet is considered a NONACK Block by default, and the encoding of a NONACKBLK message option in the initial segment is NOT REQUIRED. The NONACK 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 A sender MAY encode multiple NONACK Blocks within a single TBRPF packet. Under ordinary circumstances, NONACKable T_TLV messages are encoded within the initial segment of the TBRPF packet body. Thus, the NONACKBLK message option is rarely used. ACK Block (ACKBLK) option (TYPE = 9) - Alignment requirement: none +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 9 |0|0| ASEQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The ACKBLK message option is indicated by TYPE = 9. 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 presence of an ACKBLK message option delineates the beginning of an "ACK Block" consisting of one or more "ACKable" T_TLV messages belonging to the ACK sequence number in the VALUE field. As described in Section 6.2: "Reliable Delivery Using ACKs", each T_TLV message within an ACK Block MUST be ACK'd via a positive acknowledgment. The ACK Block ends when: - a NONACKBLK message option occurs - another ACKBLK message option occurs - a NACKBLK message option occurs (see below) - the end of the TBRPF packet is reached A sender 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. As a receiver processes each ACK Block within the TBRPF packet, it MUST prepare a positive acknowledgment message for each ACKable message for which it is the specified receiver. (NOTE: the receiver SHOULD process the entire TBRPF packet before sending a positive acknowledgment, since the TBRPF packet may contain MULTIPLE ACKable messages for that receiver.) Bellur, Ogier, and Templin Expires 2 September 2001 [Page 48] INTERNET-DRAFT TBRPF 2 March 2001 NACK Block (NACKBLK) option (TYPE = 10) - Alignment requirement: none +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 10 |0|0| NSEQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The NACKBLK message option is indicated by TYPE = 10. 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 presence of a NACKBLK message option delineates the beginning of a "NACK Block" consisting of one or more "NACKable" T_TLV messages belonging to the NACK sequence number in the VALUE field. As described in Section 6.1: "Reliable, Sequenced Delivery Using NACKs", each receiver must note the most recent NACK sequence numbers it processes from a particular sender to detect whether any have been missed. The NACK Block ends when: - another NACKBLK message option occurs - an ACKBLK message option occurs - a NONACKBLK message option occurs - the end of the TBRPF packet is reached 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. Some protocol messages apply to both the TBRPF-FT and TBRPF-PT protocol variants, while other messages are specific to one of the two variants. As described in previous sections, T_TLV mes- sages are said to be NONACKable, ACKable, or NACKable. NONACKable message are encoded as TYPE = 16 thru 31 and contain T_TLV messages for which neither ACK nor NACK messages occur. ACKable messages are encoded as TYPE = 32 thru 47 and contain T_TLV messages for which the sender requires an ACK message or some other form of positive ack- nowledgment. Finally, NACKable messages are encoded as TYPE = 48 thru 63 and contain T_TLV messages for which NACK messages MAY occur. T_TLV messages that require a LEN field may be encoded in either SHORT or LONG format, as described in previous sections. If the T_TLV message also has an alignment requirement, alignment is based on the Bellur, Ogier, and Templin Expires 2 September 2001 [Page 49] INTERNET-DRAFT TBRPF 2 March 2001 decision of whether SHORT or LONG format is used. In the following subsections, we provide formats for T_TLV messages belonging to each of the three categories using SHORT format when a LEN field is required. (LONG format encoding can be inferred from the alignment requirement and text in the earlier sections.) For each T_TLV mes- sage, we note the message alignment requirements for both SHORT and LONG format, the protocol variant(s) for which the message applies (TBRPF-FT and/or TBRPF-PT) and message format. 10.2.4.1. NONACKable Messages (TYPE = 16 thru 31) As described above, NONACKable T_TLV messages are those for which neither ACK nor NACK messages occur. NONACKable T_TLV messages may occur ONLY within a NONACK Block delineated by either the beginning of the TBRPF message body or the presence of a NONACKBLK message option. The following NONACKable messages are defined: HELLO (TYPE = 16) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 - Applies to: both TBRPF-FT and TBRPF-PT +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 16 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The body of the HELLO message consists of N 4-octet Neighbor Router IDs (RIDs), where N is derived from the T_TLV LEN field as follows: N = LEN / 4 NOTE that LEN modulo 4 MUST be ZERO. If LEN modulo 4 != 0, a FORMAT ERROR is said to occur and a receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 50] INTERNET-DRAFT TBRPF 2 March 2001 ACK (TYPE = 17) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 - Applies to: both TBRPF-FT and TBRPF-PT +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 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) - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - The body of the ACK message consists of N 4-octet Neighbor Router IDs (RIDs) followed by N 1-octet ACK Sequence Numbers, where Neighbor RID(i) corresponds to ASEQ(i) for 1 <= i <= N. N is derived from the T_TLV LEN field as follows: N = LEN / 5 NOTE that LEN modulo 5 MUST be ZERO. If LEN modulo 5 != 0, a FORMAT ERROR is said to occur and a receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 51] INTERNET-DRAFT TBRPF 2 March 2001 NACK (TYPE = 18) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 - Applies to: both TBRPF-FT and TBRPF-PT +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 18 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NSEQ(1) | NSEQ(2) | NSEQ(3) | NSEQ(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - | NSEQ(N) | (Ends on an arbitrary bondary) - - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - - The body of the NACK message consists of N 4-octet Neighbor Router IDs (RIDs) followed by N 1-octet NACK Sequence Numbers, where Neigh- bor RID(i) corresponds to NSEQ(i) for 1 <= i <= N. N is derived from the T_TLV LEN field as follows: N = LEN / 5 NOTE that LEN modulo 5 MUST be ZERO. If LEN modulo 5 != 0, a FORMAT ERROR is said to occur and a receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 52] INTERNET-DRAFT TBRPF 2 March 2001 NEW_PARENT_REPLY (TYPE = 19) - SHORT format alignment requirement: 4n+1 - LONG format alignment requirement: 4n - Applies to: TBRPF-FT ONLY +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 19 |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_B 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) | +-------------------------------+-------------------------------+ | 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]) | +-------------------------------+-------------------------------+ Bellur, Ogier, and Templin Expires 2 September 2001 [Page 53] INTERNET-DRAFT TBRPF 2 March 2001 ********************** LSU_B 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_B 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]) | +-------------------------------+-------------------------------+ The NEW_PARENT_REPLY message provides positive acknowledgment to one or more NEW_PARENT messages (described in the following section). The body of the NEW_PARENT_REPLY message contains the concatenation of an ACK Block with a number of Link State Update (LSU_B) Blocks. The LEN field provides the total length (in octets) of the ACK Block and all LSU_B Blocks thus concatenated. The ACK Block is preceded by a single octet (included in the LEN cal- culation) that encodes an 8-bit unsigned integer containing N = the number of neighbors being acknowledged. As described in the ACK mes- sage format, the body of the ACK Block consists of N 4-octet Neighbor Bellur, Ogier, and Templin Expires 2 September 2001 [Page 54] INTERNET-DRAFT TBRPF 2 March 2001 Router IDs (RIDs) followed by N 1-octet ACK Sequence Numbers, where Neighbor RID(i) corresponds to ASEQ(i) for 1 <= i <= N. If the ACK block ends on a non-integral 4-octet boundary, and if the Z bit in the TBRPF packet header is '0', ZERO PADDING bytes are inserted to the nearest 4-octet boundary. If Z = '1', however the ZERO PADDING octets are OMITTED, and the first octet of the first LSU_B Block immediately follows. Thus, the total length of the ACK Block is cal- culated as: length = 1 + (N * 5) + # padding octets This length is deducted from LEN BEFORE the ACK Block is processed. If LEN is decremented below 0, an UNDERFLOW ERROR is said to occur, and the receiver MUST stop processing the current TBRPF packet; dis- carding the remainder of its contents. The ACK Block is immediately followed by a number of concatenated LSU_B Blocks. Each LSU_B Block begins with the 4-octet Router ID (RID) for the Source (SRC) for which he LSU_B Block applies. The next 2-octet field contains an unsigned 16-bit integer with the number of neighbors (NNBR) for this SRC. If Z = '0', the NNBR field is followed by a 2-octet ZERO PADDING field; otherwise, the ZERO PADDING field is OMITTED. Following the (optional) ZERO PADDING field are NNBR-many 8-octet chunks which contain: - the 4-octet RID for a NBR of SRC - the 2-octet Link Metrics for this NBR - the 2-octet Link State Update sequence number (LSUSEQ) for the NBR Thus, if Z = '0', the total length of each LSU_B Block is calculated as: length = 4 + 2 + 2 + (NNBR * 8) else, (if Z = '1') the length is calculated as: length = 4 + 2 + (NNBR * 8) LSU_B Blocks are processed consecutively, with the total length of each LSU_B Block deducted from LEN BEFORE the LSU_B Block is pro- cessed. If LEN is decremented below 0, and UNDERFLOW ERROR is said to occur, and the receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. The final LSU_B Block is detected when LEN is decremented to ZERO. TYPE = 20 thru 31 are RESERVED for future use. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 55] INTERNET-DRAFT TBRPF 2 March 2001 10.2.4.2. ACKable Messages (TYPE = 32 thru 47) As described above, ACKable T_TLV messages are those for which a receiver must send an ACK message or some other positive acknowledg- ment. ACKable T_TLV messages may occur ONLY within an ACK Block del- ineated by the presence of an ACKBLK message option. The following ACKable messages are defined: NEW_PARENT (TYPE = 32) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 - Applies to: TBRPF-FT and TBRPF_PT +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 32 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The body of the NEW_PARENT message consists of 1 4-octet Neighbor RID and N 4-octet Source RIDs. The Neighbor RID is the neighbor to which this NEW_PARENT message is directed. The next N RIDs are the RIDs of the Sources for which the Neighbor must become the NEW_PARENT. N is derived from the T_TLV LEN field as follows: N = (LEN / 4) - 1 NOTE that LEN modulo 4 MUST be ZERO. If LEN modulo 4 != 0, a FORMAT ERROR is said to occur and the receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. If N <= 0, the NEW_PARENT message contains a NULL list of Source RIDs, and the receiver MUST skip the current VALUE field and begin processing the next T_TLV message in the TBRPF packet body. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 56] INTERNET-DRAFT TBRPF 2 March 2001 NEW_PARENT_SEQ (TYPE = 33) - SHORT format alignment requirement: 4n+1 - LONG format alignment requirement: 4n - Applies to: TBRPF-FT ONLY +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 33 |P|L| LEN | N (= # NSRC) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ **************** N Source RIDs WITHOUT LSUSEQs ****************** +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NSRC RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NSRC RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NSRC RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ****************** M Source RIDs WITH LSUSEQs ******************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC ID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSUSEQ for SSRC(1) | LSUSEQ for SSRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC ID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC ID(3) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSUSEQ for SSRC(3) | LSUSEQ for SSRC(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC ID(4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC ID(5) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSUSEQ for SSRC(5) | LSUSEQ for SSRC(6) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC ID(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The body of the NEW_PARENT_SEQ message consists of a 1-octet field that encodes an 8-bit unsigned integer N, a 1-octet Neighbor RID, N 4-octet Source RIDs (NSRCs) that do NOT include Link State Update sequence numbers (LSUSEQs) and M 6-octet (Source RID (SSRC), LSUSEQ) tuples. The Neighbor RID is the neighbor to which the NEW_PARENT_SEQ message is directed. The next N RIDs are the RIDs of the Sources for which the Neighbor must become the NEW_PARENT. (As mentioned, these N Source RIDs DO NOT include LSUSEQs.) If LEN < ((N+1) * 4) + 1, an Bellur, Ogier, and Templin Expires 2 September 2001 [Page 57] INTERNET-DRAFT TBRPF 2 March 2001 UNDERFLOW ERROR is said to occur, and the receiver MUST stop process- ing the current TBRPF packet; discarding the remainder of its con- tents. M is derived from the T_TLV LEN field as follows: REMAINDER = LEN - ((N+1) * 4) -1 M = REMAINDER / 6 NOTE that REMAINDER modulo 6 MUST be ZERO. If REMAINDER modulo 6 != 0, a FORMAT ERROR is said to occur and the receiver MUST stop pro- cessing the current TBRPF packet; discarding the remainder of its contents. If M > 0 the next M 6-octet tuples contain the 4-octet RID and 2-octet LSUSEQ for which the Neighbor must become the NEW_PARENT. The RIDs and LSUSEQs are "tiled" in the manner shown in the diagram to avoid "holes" in the packet body. NB: The above diagram shows the message format for 'M' being an even number. For 'M' being an odd number, the message ends as follows: ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC RID(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSUSEQ for SSRC(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ CANCEL_PARENT (TYPE = 34) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 - Applies to: TBRPF-FT ONLY +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 34 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The body of the CANCEL_PARENT message consists of 1 4-octet Neighbor RID and N 4-octet Source RIDs. The Neighbor RID is the neighbor to which this CANCEL_PARENT message is directed. The next N RIDs are the RIDs of the Sources for which the sender is requesting CANCEL_PARENT. N is derived from the T_TLV LEN field as follows: Bellur, Ogier, and Templin Expires 2 September 2001 [Page 58] INTERNET-DRAFT TBRPF 2 March 2001 N = (LEN / 4) - 1 NOTE that LEN modulo 4 MUST be ZERO. If LEN modulo 4 != 0, a FORMAT ERROR is said to occur and the receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. If N <= 0, the CANCEL_PARENT message contains a NULL list of Source RIDs, and the receiver MUST skip the current VALUE field and begin process- ing the next T_TLV message in the TBRPF packet body. UPDATE_REQUEST (TYPE = 35) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 - Applies to: TBRPF-PT ONLY +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 35 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The body of the UPDATE_REQUEST message consists of N 4-octet Neighbor RIDs. N is derived from the T_TLV LEN field as follows: N = (LEN / 4) NOTE that LEN modulo 4 MUST be ZERO. If LEN modulo 4 != 0, a FORMAT ERROR is said to occur and the receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. If N <= 0, the UPDATE_REQUEST message contains a NULL list of Neighbor RIDs, and the receiver MUST skip the current VALUE field and begin processing the next T_TLV message in the TBRPF packet body, if any. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 59] INTERNET-DRAFT TBRPF 2 March 2001 UPDATE_REPLY (TYPE = 36) (SHORT format alignment requirement: 4n+2) (LONG format alignment requirement: 4n+1) (Applies to: TBRPF-PT ONLY) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 36 |P|L| LEN | N (= # NBRs) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor RID(N) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ *********************** LSU_C 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bellur, Ogier, and Templin Expires 2 September 2001 [Page 60] INTERNET-DRAFT TBRPF 2 March 2001 ********************** LSU_C 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for NBR(k[1]) of SRC(2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ... ~ ~ ... ~ ~ ... ~ ********************** LSU_C 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The UPDATE_REPLY message provides positive acknowledgment to one or more UPDATE_REQUEST messages (described in the following section). The body of the UPDATE_REPLY message contains the concatenation of an ACK Block with a number of Link State Update (LSU_C) Blocks. The LEN field provides the total length (in octets) of the ACK Block and all LSU_C Blocks thus concatenated. The ACK Block is preceded by a single octet (included in the LEN cal- culation) that encodes an 8-bit unsigned integer containing N = the number of neighbors being acknowledged. As described in the ACK mes- sage format, the body of the ACK Block consists of N 4-octet Neighbor Router IDs (RIDs), however ACK Sequence Numbers (ASEQs) are not necessary and thus not encoded. Thus, the total length of the ACK Block is calculated as: length = 1 + (N * 4) This length is deducted from LEN BEFORE the ACK Block is processed. If LEN is decremented below 0, an UNDERFLOW ERROR is said to occur, Bellur, Ogier, and Templin Expires 2 September 2001 [Page 61] INTERNET-DRAFT TBRPF 2 March 2001 and the receiver MUST stop processing the current TBRPF packet; dis- carding the remainder of its contents. The ACK Block is immediately followed by a number of LSU_C Blocks concatenated together. Each LSU_C Block begins with the 4-octet Router ID (RID) for the Source (SRC) for which the LSU_C Block applies. The next 2-octet field contains an unsigned 16-bit integer with the number of neighbors (NNBR) for this SRC. UNLIKE the TREE_UPDATE message (see the following section), ALL LSU_C Blocks in an UPDATE reply encode an ADD update for their SRC. If Z = '0', the 2-octet NNBR field is immediately followed by a 2- octet ZERO PADDING field as shown above. Otherwise, the ZERO PADDING field is OMITTED, and the first NBR RID begins immediately after the NNBR field. Following the ZERO PADDING field (if any), are NNBR-many 4-octet RIDs for NBRs of the SRC. If Z = '0', the ZERO PADDING field is present and the length for the LSU_C Block is calculated as: length = 4 + 4 + (NNBR * 4) Otherwise, the ZERO PADDING field is omitted and the length of the LSU_C Block is calculated as: length = 4 + 2 + (NNBR * 4) LSU_C Blocks are processed consecutively, with the total length of each LSU_C Block deducted from LEN BEFORE the LSU_C Block is pro- cessed. If LEN is decremented below 0, and UNDERFLOW ERROR is said to occur, and the receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. The final LSU_C Block is detected when LEN is decremented to ZERO. TYPE = 37 thru 47 are RESERVED for future use. 10.2.4.3. NACKable Messages (TYPE = 48 thru 63) As described above, NACKable T_TLV messages are those for which the sender may receive a NACK message from one or more receivers that detect a gap in the NACK sequence number space. NACKable T_TLV mes- sages may occur ONLY within a NACK Block delineated by the presence of a NACKBLK message option. The following NACKable messages are defined: Bellur, Ogier, and Templin Expires 2 September 2001 [Page 62] INTERNET-DRAFT TBRPF 2 March 2001 LINK_STATE_UPDATE (TYPE = 48) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 - Applies to: TBRPF-FT ONLY +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 48 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ *********************** LSU_A 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bellur, Ogier, and Templin Expires 2 September 2001 [Page 63] INTERNET-DRAFT TBRPF 2 March 2001 ********************** LSU_A 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_A 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bellur, Ogier, and Templin Expires 2 September 2001 [Page 64] INTERNET-DRAFT TBRPF 2 March 2001 The LINK_STATE_UPDATE message consists of a number of LSU_A Blocks concatenated together. Each LSU_A Block begins with the 4-octet Router ID (RID) for the Source (SRC) for which the LSU_A Block applies. The next 2-octet field contains an unsigned 16-bit integer with the number of neighbors (NNBR) for this SRC. This field is immediately followed by another 2-octet field containing that LSUSEQ for the SRC. Following the LSUSEQ field are NNBR-many 6-octet chunks which con- tain: - the 4-octet RID for a NBR of SRC - the 2-octet Link Metrics for this NBR The order in which the two elements in each 6-octet chunk are coded is staggered in the manner shown in the diagram to avoid unused "holes" in the message. Note that if NNBR is an EVEN number, the LSU_A chunk will end on an even 4-octet boundary. But, if NNBR is ODD, the LSU_A chunk will end as follows: ~ ... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SSRC RID(M) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSUSEQ for SSRC(M) | ZERO PADDING | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ If Z = '0', the LSU_A chunk is terminated by a 2-octet ZERO PADDING field as shown above. Otherwise, the ZERO PADDING field is OMITTED, and the NEXT LSU_A chunk begins immediately after the final LSUSEQ field. Thus, if NNBR is EVEN, OR if Z = '1', the total length of the LSU_A Block is calculated as: length = 4 + 2 + 2 + (NNBR * 6) Otherwise, if NNBR is ODD AND Z = '0', the length of the LSU_A Block is calculated as: length = 4 + 2 + 2 + (NNBR * 6) +2 LSU_A Blocks are processed consecutively, with the total length of each LSU_A Block deducted from LEN BEFORE the LSU_A Block is pro- cessed. If LEN is decremented below 0, and UNDERFLOW ERROR is said to occur, and the receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. The final LSU_A Block is detected when LEN is decremented to ZERO. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 65] INTERNET-DRAFT TBRPF 2 March 2001 TREE_UPDATE (TYPE = 49) - SHORT format alignment requirement: 4n+2 - LONG format alignment requirement: 4n+1 - Applies to: TBRPF-PT ONLY +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 49 |P|L| LEN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ *********************** LSU_C for SRC(1) ************************ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RID for SRC(1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Bellur, Ogier, and Templin Expires 2 September 2001 [Page 66] INTERNET-DRAFT TBRPF 2 March 2001 ********************** LSU_C 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_C 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The TREE_UPDATE message consists of a number of LSU_C Blocks con- catenated together. Each LSU_C Block begins with the 4-octet Router ID (RID) for the Source (SRC) for which the LSU_C Block applies. The next 2-octet field contains an unsigned 15-bit integer with the number of neighbors (NNBR) for this SRC. The most significant bit of this 2-octet field (the 'A' bit) signifies the type of update. If A = '1', the LSU_C Block encodes an ADD update for this SRC. If A = '0', the LSU_C Block encodes a DELETE update. If Z = '0', the 2-octet NNBR field is immediately followed by a 2- octet ZERO PADDING field as shown above. Otherwise, the ZERO PADDING field is OMITTED, and the first NBR RID begins immediately after the NBR field. Following the ZERO PADDING field (if any), are NNBR-many 4-octet RIDs for NBRs of the SRC. If Z = '0', the ZERO PADDING field is present and the length for the LSU_C Block is calculated as: length = 4 + 4 + (NNBR * 4) Otherwise, the ZERO PADDING field is omitted and the length of the Bellur, Ogier, and Templin Expires 2 September 2001 [Page 67] INTERNET-DRAFT TBRPF 2 March 2001 LSU_C Block is calculated as: length = 4 + 2 + (NNBR * 4) LSU_C Blocks are processed consecutively, with the total length of each LSU_C Block deducted from LEN BEFORE the LSU_C Block is pro- cessed. If LEN is decremented below 0, and UNDERFLOW ERROR is said to occur, and the receiver MUST stop processing the current TBRPF packet; discarding the remainder of its contents. The final LSU_C Block is detected when LEN is decremented to ZERO. TYPE = 50 thru 63 are RESERVED for future use. 10.2.5. Implementation Considerations for SHORT and LONG Format Encoding A sender that encodes a T_TLV message with both a LEN field and an alignment requirement may know a priori whether SHORT format will suffice or whether LONG format will be necessary. In this case, the implementation SHOULD choose the appropriate LEN format and MUST align the T_TLV message properly based on the specific LEN format chosen. If the implementation DOES NOT have a priori knowledge of the LEN requirement, but the current offset within the TBRPF packet would allow for either SHORT or LONG format T_TLV message alignment with minimal/no insertion of padding octets, the implementation may first encode the T_TLV message VALUE at the first properly-aligned octet beyond the current offset, then prepend the TYPE and LEN fields (pre- ceded by any Pad0/PadN options required) in the space before the beginning of the VALUE field. If the implementation DOES NOT have a priori knowledge of the LEN requirement, AND the current offset within the TBRPF packet would allow for a SHORT format T_TLV message with no padding octets but NOT a LONG format, the implementation may employ one of a number of stra- tegies to ensure that T_TLV message are both efficiently coded and properly aligned. The implementation may optionally: - Insert padding octets into the TBRPF packet body until the padding requirement for LONG format is met. Then, begin writing the T_TLV message into the TBRPF packet body using LONG format whether/not the encoded T_TLV message exceeds 255 octets in length. (May result in wasted space for padding options if LONG format was not required. - Pre-process the T_TLV message into a temporary data buffer. Then, append the temporary data buffer to the TBRPF packet body using the appropriate LEN format (SHORT or LONG). (Results in an extra Bellur, Ogier, and Templin Expires 2 September 2001 [Page 68] INTERNET-DRAFT TBRPF 2 March 2001 data copy operation if vectored I/O data buffer chaining is not available.) - Begin writing the T_TLV message into the TBRPF packet body using SHORT format. Then, if the maximum length for a SHORT format T_TLV message is reached, terminate the construction of the current SHORT format T_TLV message and begin the construction of a NEW T_TLV message *of the same type*. Note that this final consideration implies that a "jumbo" TBRPF message MAY be split into multiple, independently-coded T_TLV messages. When a jumbo TBRPF message is split in this manner, each T_TLV message that encodes a portion of the jumbo TBRPF message MUST be wholly self-contained; that is, a receiver MUST be able to process any T_TLV message independently of any other T_TLV message(s). In summary, while a jumbo TBRPF message may be split into multiple T_TLV messages, each T_TLV message must be self-contained and properly contained within a single TBRPF packet. 11. IANA Considerations An application of TBRPF for IPv4-based MANETs will require the fol- lowing assigned number procurements from IANA: 1. an official IPv4 multicast address assignment for All_TBRPF_Neighbors, 2. an official UDP service port number for TBRPF protocol messages, 3. an official IEEE Ethertype assignment for TBRPF messages not sent via UDP (OPTIONAL) Note that the IPv4 Multicast assignment implied by 1. MAY have gen- eral application for MANET beyond its anticipated use for TBRPF. Specifically, IANA designates IPv4 Multicast assignments within the range 224.0.0.0 thru 224.0.0.255 as "NON-ROUTEABLE", meaning that messages sent to those addresses MUST NOT be routed to a different logical IPv4 subnet regardless of the TTL in the IPv4 header. How- ever, MANET applications may require one or more multicast address assignments that are "NON-RELAYABLE", meaning that messages sent to those addresses MUST NOT be relayed beyond a single hop within the same logical IPv4 subnet. We therefore propose that MANET consider the procurement of one or more "NON-RELAYABLE" IPv4 Multicast assignments from IANA. For exam- ple, MANET could register an "All_MANET_Neighbors" IPv4 multicast address with IANA, specifying that messages sent to that address MUST NOT be relayed. The existence of such assignments would obviate the requirement for an "All_TBRPF_Neighbors" multicast address assign- ment. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 69] INTERNET-DRAFT TBRPF 2 March 2001 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. 13. Implementation Status The TBRPF Version 1 protocol (as described in the previous draft ver- sion) 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 experiments since June 1999. As of January 2001, the TBRPF Version 1 protocol 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. 14. Acknowledgments The authors would like to thank ASEO/CECOM 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. 15. 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. [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. Bellur, Ogier, and Templin Expires 2 September 2001 [Page 70] INTERNET-DRAFT TBRPF 2 March 2001 [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-03.txt, November 2000 (work in progress). Bellur, Ogier, and Templin Expires 2 September 2001 [Page 71] INTERNET-DRAFT TBRPF 2 March 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 2 September 2001 [Page 72]