INTERNET-DRAFT Bhargav Bellur Richard G. Ogier Fred L. Templin SRI International 11 July 2000 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 link-state routing protocol designed for use in a mobile ad-hoc network (MANET) or an internet. TBRPF provides each node with the state of each link in the network, but does so much more efficiently than flooding (e.g., OSPF). TBRPF uses the concept of reverse-path forwarding to efficiently and reliably broadcast each link-state update along the minimum-hop-path tree rooted at the source of the update. The broadcast trees (one tree per source) are updated dynamically using the topology information that is received along the trees themselves, thus requiring very little additional overhead for maintaining the trees. This document describes TBRPF and discusses details for the implementation of TBRPF in IPv4-based MANETs. Bellur, Ogier, and Templin Expires 11 January 2001 [Page i] INTERNET-DRAFT TBRPF 11 July 2000 Contents Status of This Memo ............................................. i Abstract ........................................................ i 1. Introduction ................................................. 1 2. Assumptions and Terminology .................................. 3 3. Conceptual Data Structures and Messages ...................... 3 4. TBRPF Operation .............................................. 6 4.1. TBRPF Pseudocode ........................................ 9 5. Link-Level Functions ......................................... 11 5.1. Neighbor Discovery ...................................... 11 5.2. Reliable Link-Level Transmission of Control Messages .... 12 6. TBRPF Implementation for IPv4-based MANETs ................... 16 6.1. Data Link Layer Assumptions ............................. 16 6.2. Internetworking Assumptions ............................. 17 6.3. TBRPF Neighbor Discovery in IPv4 MANETs ................. 18 6.4. TBRPF Protocol Messages in IPv4 MANETs .................. 21 7. IANA Considerations .......................................... 32 8. Security Considerations ...................................... 32 9. Implementation Status ........................................ 32 References ...................................................... 33 Authors' Addresses .............................................. 34 Bellur, Ogier, and Templin Expires 11 January 2001 [Page ii] INTERNET-DRAFT TBRPF 11 July 2000 1. Introduction This document describes the Topology Broadcast based on Reverse-Path Forwarding (TBRPF) protocol [1], developed in the DARPA Small Unit Operations (SUO) program. TBRPF addresses the problem of efficient routing in a communication network, where by efficient we mean that the amount of update and control traffic required to maintain shor- test (or nearly shortest) paths to all destinations is minimized. This problem is important if the network incurs frequent topology and link-cost changes, or must use links of limited bandwidth, or if the network is very large (for scalable routing). In particular, this problem is important for mobile ad-hoc networks (MANETs). Routing protocols can be classified as proactive protocols, in which each node maintains paths at all times to all possible destinations, and reactive (or on-demand) protocols, in which paths are found (using route discovery) only when they are required. TBRPF is a proactive, link-state protocol, as are flooding (e.g., OSPF) and STAR (Source Tree Adaptive Routing) [4]. Examples of reactive protocols are DSR [6] and AODV [8]. Reactive protocols tend to be more efficient when route requests are infrequent, while proactive protocols tend to be more efficient when route requests are frequent (since route discovery typically involves flooding). In addition, the delay required by reactive protocols for route discovery may be too large for some applications. Therefore, the best solution may be a hybrid routing solution that combines proactive and reactive techniques, or a protocol that changes dynami- cally between proactive and reactive methods, based on network meas- urements. TBRPF can be used as the proactive part of such a hybrid solution. Routing protocols can also be classified according to whether they find optimal (shortest) routes or suboptimal routes. By not requir- ing routes to be optimal, it is possible to reduce the amount of con- trol traffic (including routing updates) necessary to maintain the routes. However, optimal routes are desirable because they minimize delay and the amount of resources (e.g., bandwidth and power) con- sumed. TBRPF computes optimal routes based on the advertised link states; however, the advertised link states themselves may be approx- imate in order to reduce the frequency at which each link is updated. TBRPF is a full-topology link-state protocol: each node is provided with the state of each link in the network (or within a cluster if hierarchical routing is used). Flooding is another full-topology link-state protocol, but is very inefficient due to the following redundancies: (1) updates are sent over multiple paths to each node; and (2) every node forwards every update to all neighbors, even if Bellur, Ogier, and Templin Expires 11 January 2001 [Page 1] INTERNET-DRAFT TBRPF 11 July 2000 none or only one neighbor needs to receive it. TBRPF removes these redundancies, thus providing the same routing information as flooding with much greater efficiency. In fact, in simulation experiments [7], TBRPF generated up to 85% less update/control traffic than an efficient version of 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 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. The broad- cast trees (one tree per source) are updated dynamically using the topology information that is received along the trees themselves, thus requiring very little additional overhead for maintaining the trees. (The fact that this is possible in a dynamic network is a new result.) Minimum-hop-path trees are used because they change less frequently than shortest-path trees based on a metric such as delay. Based on the information received along the broadcast trees, each node computes its parent and children for the broadcast tree rooted at each source u. Each node forwards updates originating from source u to its children on the tree rooted at source u. TBRPF achieves reliability despite topology changes, using sequence numbers. The correctness of TBRPF has been proven [1]. For point-to-point links (or receiver-directed transmissions), each link-state update is sent on only |V|-1 tree links in TBRPF versus approximately |E| links for flooding, where |V| and |E| are the number of nodes and links, respectively. For networks that allow broadcast transmissions, a node having no children for source u is a leaf and need not forward updates generated by u. In typical net- works, most nodes are leaves. In addition, a node having only only one child for source u can send the updates generated by u to only that child (receiver directed), instead of broadcasting the updates to all neighbors. TBRPF can be easily extended to hierarchical link-state 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, they Bellur, Ogier, and Templin Expires 11 January 2001 [Page 2] INTERNET-DRAFT TBRPF 11 July 2000 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. Assumptions and Terminology TBRPF requires very few assumptions regarding the network model. TBRPF can operate in any internet or subnet in which IP hosts are connected through broadcast or point-to-point links to routers. The current implementation of TBRPF operates on top of IP, similarly to an internet routing protocol such as OSPF. TBRPF can operate in ad- hoc networks that use different medium access control (MAC) proto- cols, which need not permit promiscuous listening of transmissions. To describe TBRPF, the topology of a network is modeled as a directed graph G = (V, E), where V is the set of nodes and E is the set of edges or links. Each node has a unique identifier and represents a router that runs TBRPF. In a wireless network, a node can have con- nectivity with multiple nodes over a single physical radio link. We consider two nodes u and v to be adjacent (i.e., neighbors) if each node can reliably receive messages from the other. Thus, we map a physical broadcast link connecting multiple nodes into multiple point-to-point bidirectional links. Such a bidirectional link between two nodes u and v is represented by a pair of links (u,v) and (v,u). Each link has a positive cost that can vary in time, and the cost of (u,v) may be different from that of (v,u). Each router u is responsible for updating and reporting the cost and up/down status of each outgoing link (u,v) to neighbors. TBRPF can also support the broadcast of multiple link costs (or link metrics) for purposes of quality-of-service routing. TBRPF uses a neighbor discovery protocol based on hello packets to establish links to new neighbors and to detect link failures. TBRPF supports both unicast transmissions (e.g., point-to-point or receiver directed), in which a packet reaches only a single neighbor; and broadcast transmissions, in which a single packet is transmitted simultaneously to all neighbors. In particular, TBRPF allows an update to be sent either on a common broadcast channel or on one or more unicast channels, depending on the number of neighbors that need to receive the update. 3. 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 Bellur, Ogier, and Templin Expires 11 January 2001 [Page 3] INTERNET-DRAFT TBRPF 11 July 2000 associated 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). There- fore, 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. TBRPF stores the following information at each node i of the network: 1. A topology table, denoted TT_i, consisting of all link-states stored at node i. The entry for link (u,v) in this table is denoted TT_i(u,v) and consists of the most recent update (u,v,c,sn) received for this link. The components c and sn of the entry for link (u,v) will be denoted TT_i(u,v).c and TT_i(u,v).sn. TBRPF 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. A list of children, denoted children_i(u). c. The sequence number of the most recent link-state update ori- ginating from node u received by node i, denoted sn_i(u). d. The routing table entry for node u, consisting of the next node on the preferred path to u. 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. Bellur, Ogier, and Templin Expires 11 January 2001 [Page 4] INTERNET-DRAFT TBRPF 11 July 2000 TBRPF uses the following message types. Message formats for the current implementation of TBRPF are specified in Section 6. However, as TBRPF is work in progress, message formats are subject to change. Link-State Update (LSU) A 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. CANCEL PARENT A message informing a neighbor that it is no longer a parent with respect to one or more sources. HELLO A message sent periodically by each node i for neighbor discovery. NEIGHBOR A message sent in response to a HELLO message. NEIGHBOR ACK A message sent in response to a NEIGHBOR message. ACK A link-level acknowledgment to a unicast transmission. NACK A link-level negative acknowledgment reporting that one or more update messages sent on the broadcast channel were not received. RETRANSMISSION OF BROADCAST A retransmission, on a unicast channel, of link-state updates belonging to an update message for which a NACK was received. HEARTBEAT A message sent periodically on the broadcast channel when there are no updates to be sent on this channel, used to achieve reliable link-level broadcast of update messages based on NACKs. END OF BROADCAST A message sent to a neighbor over a unicast channel, to report that updates originating from one or more sources are now being sent on the unicast channel instead of the broadcast channel. Bellur, Ogier, and Templin Expires 11 January 2001 [Page 5] INTERNET-DRAFT TBRPF 11 July 2000 4. TBRPF Operation This section describes the network-level operation of TBRPF, with the aid of the pseudocode given at the end of the section. The next sec- tion describes the link-level functions of TBRPF, i.e., neighbor discovery and reliable transmission of control packets. Examples illustrating the operation of TBRPF and the the proof of correctness for TBRPF 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 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 selects a neighbor as the parent for source src by sending a NEW PARENT(src, sn) message containing the identity of node src and the sequence number sn = sn_i(src). A node cancels an existing parent by sending a CANCEL PARENT(src) message containing the iden- tity 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 message with source src. In general, a node will simultaneously select a neighbor as the parent for multiple sources, so that it sends a NEW PARENT(src_list, sn_list) message to the new parent, where src_list is the list of sources and sn_list is the corresponding list of sequence numbers. Similarly, a CANCEL PARENT message will generally 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. If accepted, the link-state update is entered into the topology table of node i, and then for- warded to every node in children_i(src) (see the procedures Update_Topology_Table and Process_Update). Bellur, Ogier, and Templin Expires 11 January 2001 [Page 6] INTERNET-DRAFT TBRPF 11 July 2000 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 or change in cost of a link to an existing neighbor. A node computes its parents by (1) computing minimum-hop paths to all other nodes using Dijkstra's algo- rithm, 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 sends the message CANCEL PARENT(src) to the current (old) parent if it exists. It also sends the message NEW PARENT(src, sn) to the newly computed parent if it exists, where 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 from the old parent, and after which the new parent should commence. Upon receiving the CANCEL PARENT(src) message, the old parent k removes node i from the list children_k(src). Upon receiving the NEW PARENT(src, sn) message, the new parent j = p_i(src) adds node i to the list children_j(src) and sends to node i a link-state update mes- sage consisting 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). Thus, only updates not yet known to node i are sent to node i. 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 sent to all neighbors in children_i(i). As noted above, node i also recomputes its parent node p_i(src) for every node src, in response to this topological change. In a similar manner, when node i detects the loss of connectivity to an existing neighbor nbr, it executes Link_Down(i, nbr). Link_Change(i, nbr) is likewise exe- cuted at node i in response to a change in the cost to an existing neighbor node nbr. However, this procedure does not recompute 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 Bellur, Ogier, and Templin Expires 11 January 2001 [Page 7] INTERNET-DRAFT TBRPF 11 July 2000 set, and sn_i(src) = 0 for every node src. Every node then executes 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. There- fore, 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 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. TBRPF does not require an age field in link-state updates. However, 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 MAX_AGE seconds (e.g., 1 hour) in order to conserve memory. The reason these updates are not deleted immedi- ately 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) dur- ing 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 dif- ferent 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 recov- ers 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 important to ensure the efficiency of TBRPF 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 MAX_AGE seconds. Periodic updates are not strictly required for the correctness of TBRPF. However, we allow infrequent periodic updates to correct errors that may occur in table entries or update messages. (See Send_Periodic_Updates.) As discussed above, periodic updates are Bellur, Ogier, and Templin Expires 11 January 2001 [Page 8] INTERNET-DRAFT TBRPF 11 July 2000 also useful if the sequence number space is not large enough to avoid wraparound. TBRPF provides each node with complete link-state information. Each node can then apply a path selection algorithm to compute preferred paths to all possible destinations, and to update these paths when link states are updated. The default path selection algorithm for TBRPF is to apply Dijkstra's algorithm to compute shortest paths (with respect to c) to all destinations. However, TBRPF can employ any path selection algorithm. Once preferred paths are computed, the routing table entry for node u is set to the next node on the pre- ferred 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, data packets are forwarded based on the routing table as in IP routing. However, source routing can also be used. 4.1. Pseudocode The following pseudocode describes the network-level procedures per- formed at node i by TBRPF. The notation LSU(update_list) represents a link-state-update message that includes the updates (u,v,c,sn) in update_list. Process_Update(i, nbr, in_message){ (Called when an update message in_message is received from nbr.) Update_Topology_Table(i, nbr, in_message, update_list). Update_Parents(i). 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 update_list(src) is nonempty Send message LSU(update_list(src)) to children_i(src).}} 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 ((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 ((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.}}}} Bellur, Ogier, and Templin Expires 11 January 2001 [Page 9] INTERNET-DRAFT TBRPF 11 July 2000 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)}. Send message LSU(update_list) to children_i(i).}} Link_Down(i,j){ (Called when link (i,j) goes down.) Remove j from N_i. Set TT_i(i,j).c = infinity. Set TT_i(i,j).sn = current time stamp SN_i. Update_Parents(i). For each (node src in TT_i) remove j from children_i(src). Set update_list = {(i,j, infinity, TT_i(i,j).sn)}. Send message LSU(update_list) to children_i(i).} 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)}. Send message LSU(update_list) to children_i(i).} Update_Parents(i){ Compute_New_Parents(i). 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).} 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).}}} For each (node k in N_i){ If (src_list(k) is nonempty) Send message NEW PARENT(src_list(k), sn_list(k)) to k. If (cancel_src_list(k) is nonempty) Send message CANCEL PARENT(cancel_src_list(k)) to k.}} Bellur, Ogier, and Templin Expires 11 January 2001 [Page 10] INTERNET-DRAFT TBRPF 11 July 2000 Compute_New_Parents(i){ For each (node src in TT_i such that src != i) Set new_p_i(src) = NULL. 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.} Process_New_Parent(i, nbr, src_list, sn_list){ (Called when node i receives a NEW PARENT(src_list, sn_list) message from nbr.) 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 = {(k,l,c,sn) in TT_i such that k = src and sn > sn_list.src}. Add new_updates to update_list.} Send message LSU(update_list) to nbr.} Process_Cancel_Parent(i,nbr,src_list ) (Called when node i receives a CANCEL PARENT(src_list) message from nbr.) For each (node src in src_list) remove nbr from children_i(src). 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. } Send message LSU(update_list) to children_i(i).} 5. Link-Level Functions This section describes the link-level functions of TBRPF, i.e., neighbor discovery and the reliable link-level transmission of control messages. 5.1. Neighbor Discovery The neighbor discovery protocol detects the following events: 1. A link to a new neighbor is established, 2. The link to an existing neighbor goes down. Bellur, Ogier, and Templin Expires 11 January 2001 [Page 11] INTERNET-DRAFT TBRPF 11 July 2000 Neighbor discovery uses the following three types of control messages: HELLO, NEIGHBOR, and NEIGHBOR ACK. Every HELLO_INTVL seconds, each node i transmits, on the broadcast channel, a HELLO message containing the identity of node i. Upon receiving a HELLO message from a new neighbor i, a node j responds with a NEIGHBOR mes- sage containing the identity of node j. Finally, upon receiving the NEIGHBOR message, node i sends to node j a NEIGHBOR ACK containing the identity of node i. NEIGHBOR and NEIGHBOR ACK messages also con- tain the current link-level sequence number for the broadcast channel (discussed below). A link from node i to node j is established if node i receives a NEIGHBOR packet or NEIGHBOR ACK from node j. The link to an existing neighbor is declared to be down if no traffic (including HELLO messages and ACKs) has been received from the neigh- bor in the last LINKDOWN_INTVL seconds. 5.2. Reliable Link-Level Transmission of Control Messages In most link-state routing protocols, e.g., OSPF, each node forwards the same link-state information to all neighbors. In contrast, in TBRPF each node sends each link-state update only to neighbors that are children on the minimum-hop path tree rooted at the source of the update. TBRPF can therefore utilize bandwidth more efficiently by using unicast transmissions if only one child (or a few children) exists for the update source, and broadcast transmissions when several children exist for the update. Therefore, TBRPF uses a rule to decide whether to use unicast or broadcast transmissions, depending on the number of children and the total number of neighbors. Updates with only one intended receiver (e.g., only one child), should use unicast transmissions. Updates with several intended receivers should use broadcast transmissions, to avoid transmitting the message several times. Therefore, it is reasonable to use the following simple transmission rule, where k is the number of intended receivers: Use unicast if k = 1 and use broadcast if k > 1. This simple rule has the following possible drawback, where n is the number of neighbors. If k = 2 and n = 20, then 18 neighbors are wasting time listening to a message not intended for them when they could be sending or receiving another message. To avoid this draw- back, another (optional) rule is to use broadcast if k > (n+1)/2 and unicast otherwise. In general, any rule of the form k > g(n) can be used. We note that, for update messages, the number of children k may be different for different update sources. Therefore, it is pos- sible to use unicast for some sources and broadcast for other sources, and the transmission mode for a given source u, denoted mode_i(u), can change dynamically between unicast and broadcast as the number of children changes. Bellur, Ogier, and Templin Expires 11 January 2001 [Page 12] INTERNET-DRAFT TBRPF 11 July 2000 While Link-State Update messages can be transmitted in either unicast or broadcast mode, HELLO messages and HEARTBEAT messages (discussed below) are always transmitted on the broadcast channel, and the fol- lowing messages are always transmitted on the unicast channel (to a single neighbor): NEIGHBOR, NEIGHBOR ACK, ACK, NACK, NEW PARENT, CANCEL PARENT, RETRANSMISSION OF BROADCAST, END OF BROADCAST, and Link-State Update messages sent in response to a NEW PARENT message. The procedure for sending a Link-State Update message (that is not a response to a NEW PARENT message) on the broadcast or unicast channel is as follows: If (mode_i(src) == BROADCAST) Append the message update_msg to the message queue associated with the broadcast channel. If (mode_i(src) == UNICAST) For (each node k in children_i(src)) Append the message update_msg to the message queue associated with the unicast channel to node k. The reliable unicast transmission of control packets MUST be pro- vided, either by an underlying link-layer protocol or by TBRPF itself. Any existing method for reliable link-layer unicast transmis- sion can be used. Such methods typically use sequence numbers and ACKs, in which a packet is retransmitted if an ACK for it is not received within a given amount of time. The method used for reliable unicast of control packets is not part of the TBRPF specification. The following two subsections describe the mechanism for the reliable transmission of update messages in broadcast mode, and the procedure for dynamically selecting the transmission mode. 5.2.1. Reliable Transmission of Update Messages in Broadcast Mode In this subsection, we describe the procedure for the reliable transmission of Link-State Update messages in broadcast mode. A broadcast update message includes one or more link-state updates, denoted lsu(src), originating from sources src for which the transmission mode is BROADCAST. Each broadcast control packet is identified by a sequence number that is incremented each time a new broadcast control packet is transmitted. Before describing the procedure, we discuss a few of its properties. NACKs are used instead of ACKs for reliable transmission, so that the amount of ACK/NACK traffic is minimized if most transmissions are successful. Suppose node i receives a NACK from a neighbor k for a broadcast update message. Then all updates lsu(src) in the original Bellur, Ogier, and Templin Expires 11 January 2001 [Page 13] INTERNET-DRAFT TBRPF 11 July 2000 message, for each node src such that k belongs to children_i(src), are retransmitted (reliably) on the UNICAST channel to neighbor k, in a RETRANSMISSION OF BROADCAST message. This message includes the original broadcast sequence number to allow node k to process the updates in the correct order. The procedure for the reliable transmission of broadcast update pack- ets uses the following message types (in addition to Link-State Update messages): HEARTBEAT(sn), NACK(sn, bit_map), and RETRANSMIS- SION OF BROADCAST(sn, update_msg). A NACK(sn, bit_map) message con- tains the sequence number (sn) of the last received broadcast control packet, and a 16-bit vector (bit_map) specifying which of the 16 broadcast control packets from sn-15 to sn have been successfully received. The description of the procedure at node i requires the following notation: Pkt(sn) Control packet with sequence number sn transmitted on the broadcast channel by node i. MsgQ Message queue for new control messages to be sent on the broadcast channel from node i. brdcst_sn_i sequence number of the last packet transmitted on the broadcast channel by node i. Heartbeat_Timer Timer used in the transmission of the Heartbeat message. Following the transmission of the broadcast control packet Pkt(brdcst_sn_i) on the broadcast channel, node i increments brdcst_sn_i and reinitializes Heartbeat_Timer. When Heartbeat_Timer expires at node i, the node appends the control message HEARTBEAT(brdcst_sn_i) to the message queue associated with the broadcast channel, and reinitializes Heartbeat_Timer. When node i receives NACK(sn, bit_map) from node nbr, node i performs the following: For each (sn' not received as indicated by bit_map){ Let update_msg = {(src*, v*, sn*, c*) in Pkt(sn') such that nbr is in children_i(src*)}. Append the message RETRANSMISSION OF BROADCAST(sn', update_msg) Bellur, Ogier, and Templin Expires 11 January 2001 [Page 14] INTERNET-DRAFT TBRPF 11 July 2000 to the message queue associated with the unicast channel to node nbr. (Message must be sent even if update_msg is empty.)} Upon receipt at node nbr of control packet Pkt(sn) transmitted on the broadcast channel by node i, node nbr performs the following: If the control packet Pkt(sn) is received in error{ Append the control message NACK(sn, bit_map) to the message queue associated with the unicast channel to node i.} If the control packet Pkt(sn) is received out of order (i.e., at least one previous sequence number is skipped){ Withhold the processing of the control packet Pkt(sn). Append the control message NACK(sn, bit_map') to the message queue associated with the unicast channel to node i.} Else (control packet Pkt(sn) is received correctly and in order){ For each Link-State Update message update_msg in Pkt(sn), call Process_Update(i, nbr, update_msg).} When a link is established from node i to a new neighbor k, node i obtains the current value of brdcst_sn_k from the NEIGHBOR message or NEIGHBOR ACK that was received from node k. 5.2.2. Changing the Transmission Mode Between Unicast and Broadcast This subsection describes the mechanism used by each node i to dynam- ically select the transmission mode for link-state updates originat- ing from each source node src. As discussed above, this decision uses a rule of the form k > g(n), where k is the number of children (for src) and n is the number of neighbors of node i. However, addi- tional care must be taken to ensure that updates are received in the correct order, or that the receiver has enough information to reorder the updates. This is accomplished by sending an END OF BROADCAST(last_seq_no, src) message on the unicast channel to each child when the mode changes to UNICAST, and by waiting for all update packets sent on unicast channels to be acked on before changing to BROADCAST mode. To facilitate this process, each node i maintains a binary variable unacked_i(nbr, src) for each neighbor nbr and source src, indicating whether there are any unacked control packets sent to nbr containing link-state updates originating at node src. The following procedure is executed periodically at each node i. For each (node src){ If (mode_i(src) = BROADCAST and |children_i(src)| <= g(n)){ For each (node k in children_i(src)){ Append the message END OF BROADCAST(brdcst_sn_i, src) to the Bellur, Ogier, and Templin Expires 11 January 2001 [Page 15] INTERNET-DRAFT TBRPF 11 July 2000 message queue associated with the unicast channel to node k.} Set mode_i(src) = UNICAST.} If (mode_i(src) = UNICAST and |children_i(src)| > g(n)){ Set switch_flag = YES. For each (node k in children_i(src)){ If (unacked_i(k,src) = YES) Set switch_flag = NO.} If (switch_flag = YES) Set mode_i(src) = BROADCAST.}} 6. TBRPF Implementation for IPv4-based MANETs The TBRPF routing protocols provide automatic full topology discovery with dynamic adaptation to link state changes in highly mobile environments. TBRPF is particularly well suited to MANETs consisting of mobile nodes with wireless data link interfaces operating in peer-to-peer fashion over either a single multiple access communica- tions channel or a collection of receiver directed point-to-point channels with a multiple access broadcast channel. (An example of the former 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 all unicast, multicast and broadcast message transmissions.) Additionally, TBRPF is particularly well suited for carrying routing information that supports the standard DARPA Inter- net protocols (IPv4) [10]. In the following sections, we discuss assumptions for the data link layer, Internetworking assumptions, and TBRPF neighbor discovery and routing protocol message transmission in an Internet addressing environment. 6.1. Data Link Layer Assumptions We assume a data link layer broadcast channel (*) with multiple access capabilities, such that nodes wishing to transmit IPv4 broad- cast and/or multicast messages must arbitrate with other nodes for channel access before doing so. We further assume that messages 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 limita- tions, terrain features, and other hidden terminal conditions incurred in a mobile environment. We consider a pair of nodes (A and B) to have a bi-directional link (or simply "link") if and only if both node A can receive messages sent from node B and node B can receive messages sent from node A at a given instant in time. (*) Some wireless data link layer protocols may provide point-to- point receiver directed (unicast) channels which operate out-of- Bellur, Ogier, and Templin Expires 11 January 2001 [Page 16] INTERNET-DRAFT TBRPF 11 July 2000 band with respect to the multiple access broadcast channel while others (such as IEEE 802.11) utilize a single multiple access channel for all unicast and broadcast/multicast message transmis- sions. 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) message delivery services between nodes with instantaneous bi-directional links. Finally, we assume that each node in the MANET has a unique data link layer unicast address assignment. 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. 6.2. Internetworking Assumptions While TBRPF can be readily extended to support hierarchical address- ing compatible with the generalized Internet addressing architecture, we assume a "flat" addressing scheme within a singe MANET. In the flat addressing model, we assume that each node is assigned an IPv4 address [10] which presumably has some topological relevance to its "home" MANET, but we do not assume that all nodes within the MANET share a common IPv4 network prefix. While it may be reasonable to assume that all nodes in a MANET might initially be assigned IPv4 addresses with a common network prefix, dynamic topology changes may result in nodes leaving their home MANETs and subsequently joining foreign MANETs. Such mobility factors may result in an heterogeneous conglomerate of IPv4 network prefixes within a single MANET unless some form of dynamic address assignment (or other address renumbering method) is used. As with data link layer addressing, we assume that each node in the MANET is assigned a unique IPv4 address, but we require each node to provide a means for duplicate IPv4 address detection. Again, methods for duplicate address deconfliction are beyond the scope of this document. While we make no assumptions regarding IPv4 network address prefix assignments within a MANET, we assume that each node in the MANET will participate in the TBRPF routing protocol scheme. Therefore, since each node in the MANET participates in the TBRPF dynamic full Bellur, Ogier, and Templin Expires 11 January 2001 [Page 17] INTERNET-DRAFT TBRPF 11 July 2000 topology discovery process, the requirement for on-demand discovery through the Address Resolution Protocol (ARP) [9] is obviated. We further assume that each node in the MANET supports the multi-hop relaying paradigm; in other words, each node in the MANET must be prepared to provide a third-party message 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 relaying paradigm provides intra- MANET message forwarding services, whereas standard Internet routing provides message forwarding between distinct IPv4 networks. 6.3. TBRPF Neighbor Discovery in IPv4 MANETs 6.3.1. Address Resolution Extensions for TBRPF Neighbor Discovery TBRPF is an automatic, full topology discovery protocol that provides dynamic reaction to link state changes. TBRPF employs a neighbor discovery protocol that dynamically establishes bi-directional links and detects bi-directional link failures through the periodic transmission of HELLO messages. Thus, since the TBRPF neighbor discovery process is both automatic and continuous, we piggyback a data link-to-IPv4 address resolution capability onto the neighbor discovery protocol messages in MANET applications. Since address resolution is built-in to the TBRPF neighbor discovery protocol, the use of ARP [9] is deprecated for TBRPF-based MANETs. Additionally, since link state changes occur dynamically, stale ARP cache issues are avoided by handling address resolution from within the TBRPF neighbor discovery protocol itself. 6.3.2. TBRPF Neighbor Discovery Message Transmission As discussed in the previous section, TBRPF neighbor discovery is responsible for both link state maintenance and data link-to-IPv4 address resolution in MANETs. Therefore, TBRPF neighbor discovery operates as a data link level protocol on MANETs. In the future, a new IANA [12] Ethernet protocol ID assignment for TBRPF neighbor discovery will be procured. Currently, the Ethernet protocol ID assignment for ARP (0x806) is used, since the use of ARP is depre- cated for TBRPF-based MANETs. As described in Section 5.1, TBRPF neighbor discovery message types include HELLO, NEIGHBOR, and NEIGHBOR_ACK. TBRPF HELLO messages MUST be sent to the data link level broadcast address, while NEIGHBOR and NEIGHBOR_ACK messages MUST be sent to the data link level unicast address of a neighboring node on the MANET. Implementations SHOULD Bellur, Ogier, and Templin Expires 11 January 2001 [Page 18] INTERNET-DRAFT TBRPF 11 July 2000 detect the event of a data link-to-IPv4 address mapping change for existing links. This may occur in one of the following instances: 1. Two or more nodes in the MANET 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 which MAY have left the MANET. In case 1, the implementation SHOULD print some form of "duplicate IPv4 address detected" message to the console. In cases 2 and 3, the cached link state SHOULD be updated to reflect the new data link-to- IPv4 address mapping. 6.3.3. TBRPF Neighbor Discovery Packet Format We now present the packet format for the TBRPF HELLO, NEIGHBOR, and NEIGHBOR_ACK neighbor discovery protocol messages on MANETs. Note that the packet format is similar to the format used by ARP [9]. The data link header for each message is not shown, since it is specific to the underlying data link layer. TBRPF places no requirements on the underlying data link layer other than those described under "data link layer assumptions" above. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | H/W Address Space | Protocol Address Space | +-------------------------------+---------------+---------------+ | H/W Len (=n) | Proto Len (=m)| Type | BCAST Seq# | +-------------------------------+---------------+---------------+ ~ Sender Hardware Address (m bytes) ~ ~ ... ~ +-------------------------------+-------------------------------+ ~ Sender Protocol Address (n bytes) ~ ~ ... ~ +-------------------------------+-------------------------------+ ~ Target Hardware Address (m bytes) ~ ~ ... ~ +-------------------------------+-------------------------------+ ~ Target Protocol Address (n bytes) ~ ~ ... ~ +-------------------------------+-------------------------------+ Bellur, Ogier, and Templin Expires 11 January 2001 [Page 19] INTERNET-DRAFT TBRPF 11 July 2000 Type (8 bits): HELLO 10 NEIGHBOR 11 NEIGHBOR_ACK 12 BCAST Seq# (8 bits): A sequence number from 0...15 (effectively, only 4 bits), used in NEIGHBOR and NEIGHBOR_ACK messages as described in Section 5.1. All Other Fields: Identical to their usage in ARP [9]. The TBRPF neighbor discovery protocol requires that each node in the MANET MUST send periodic HELLO messages to the data link broadcast address at HELLO_INTVL timeout intervals. (The HELLO_INTVL value MUST be common to all nodes within a MANET, but different MANETs MAY use different HELLO_INTVL values.) A node receiving a HELLO message from a new neighbor MUST send a NEIGHBOR message to the new neighbor's data link unicast address. Finally, a node receiving a NEIGHBOR mes- sage from a new neighbor MUST send a NEIGHBOR_ACK message to the new neighbor's data link unicast address. As with standard ARP, the four address fields (sender hardware address; sender protocol address; target hardware address; target protocol address) facilitate the address resolution process. The fields contain the following values, based on the TBRPF neighbor discovery message opcode: HELLO Sender Hardware Address: data link address of sender Sender Protocol Address: IPv4 address of sender Target Hardware Address: data link broadcast address Target Protocol Address: unused NEIGHBOR Sender Hardware Address: data link address of sender Sender Protocol Address: IPv4 address of sender Target Hardware Address: sender H/W Address from HELLO Target Protocol Address: sender IPv4 Address from HELLO NEIGHBOR_ACK Sender Hardware Address: data link address of sender Sender Protocol Address: IPv4 address of sender Target Hardware Address: sender H/W address from NEIGHBOR Target Protocol Address: sender IPv4 address from NEIGHBOR Bellur, Ogier, and Templin Expires 11 January 2001 [Page 20] INTERNET-DRAFT TBRPF 11 July 2000 6.4. TBRPF Protocol Messages in IPv4 MANETs TBRPF protocol messages are exchanged between current neighbor nodes which have established bi-directional links and performed data link to IPv4 address resolution via TBRPF neighbor discovery as described in the previous section. IPv4 addresses are therefore available for use as node IDs in TBRPF protocol messages. TBRPF protocol messages are sent via the User Datagram Protocol (UDP) [11]. This approach requires an official UDP service port number registration (see: IANA Considerations). The use of UDP/IPv4 provides several advantages over a data link level approach, including: - IP segmentation/reassembly facilities - UDP checksum facilities - Simple application level access for routing daemons - IPv4 multicast addressing for link state messages TBRPF protocol messages are sent to either the IPv4 unicast address of a current neighbor or the "All_TBRPF_Neighbors" IPv4 multicast address (see: IANA Considerations). In most cases, a message SHOULD be sent to the IPv4 unicast address of a current neighbor if ALL com- ponents of the message pertain ONLY to that neighbor. Similarly, a message SHOULD be sent to the All_TBRPF_Neighbors IPv4 multicast address if the message contains components which pertain to more than one neighbor neighbors. Receivers MUST be prepared to receive TBRPF protocol messages sent either to their own IPV4 unicast address or the All_TBRPF_Neighbors multicast address. Actual addressing stra- tegies are highly dependent on the underlying data link layer. (**) (**) For data links such as IEEE 802.11, a single, multiple access channel is available for all unicast and broadcast/multicast mes- sages. In such cases, since channel occupancy for unicast and multicast messages is identical, it would seem frugal to send a single message to the All_TBRPF_Neighbors multicast address rather than multiple unicast messages even if the message contains com- ponents which pertain to only a subset of the current neighbors. In other cases, in which point-to-point receiver directed channels are available, sending multiple unicast messages may reduce con- tention on the multiple access broadcast channel. Specific link layer strategies are beyond the scope of the current document. 6.4.1. Atomic TBRPF Message Format Individual (atomic) TBRPF messages consist of a message header fol- lowed by a message body. Atomic messages may be transmitted either individually or as components of a compound TBRPF message consisting of multiple atomic messages within a single UDP/IPv4 datagram. See Bellur, Ogier, and Templin Expires 11 January 2001 [Page 21] INTERNET-DRAFT TBRPF 11 July 2000 Section 6.4.2 for the compound message format. TBRPF message headers are either 32-bits or 64-bits in length depend- ing on whether the atomic message is BROADCAST or UNICAST. The format for the TBRPF message header (and a detailed description of the indi- vidual fields) is 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Vers|M| Num_sources | Offset | LSEQ | +---------------+---------------+-------------------------------+ | Identity of Receiver (ONLY present if M=UNICAST) | +---------------------------------------------------------------+ where the header fields are defined as follows: Type (4 bits): The atomic message type. The following types are currently defined: ACK 1 NACK 2 NEW_PARENT 3 CANCEL_PARENT 4 HEARTBEAT 5 END_OF_BROADCAST 6 LINK_STATE_UPDATE_A 7 LINK_STATE_UPDATE_B 8 RETRANSMISSION_OF_BROADCAST 9 Version (3 bits): The TBRPF protocol version field provides a transition mechan- ism for future versions of the TBRPF protocol. Also provides a sanity check for host software to identify bogus messages pur- porting to be TBRPF control messages. We currently define a single value for TBRPF version 1: TBRPFVERSION_1 1 Mode (1 bit): The transmission mode for this atomic TBRPF message; either UNICAST or BROADCAST. UNICAST refers to an atomic message which must be processed by only a single neighbor. BROADCAST refers to an atomic message which must be processed by ALL neighbor nodes. (NB: For IPv4 MANETs, UNICAST implies a specific IPv4 unicast address while BROADCAST implies the All_TBRPF_Neighbors Bellur, Ogier, and Templin Expires 11 January 2001 [Page 22] INTERNET-DRAFT TBRPF 11 July 2000 IPv4 multicast address.) The following mode bits are defined: UNICAST 0 BROADCAST 1 Messages of type ACK, NACK, NEW_PARENT, and CANCEL_PARENT MUST be sent as UNICAST. Messages of type LINK_STATE_UPDATE_A and LINK_STATE_UPDATE_B MAY be sent as either UNICAST or BROADCAST. Messages of type RETRANSMISSION_OF_BROADCAST and END_OF_BROADCAST MUST be sent as UNICAST. Num_Sources (==m) (8 bits): Number of sources 'm' included in the atomic message. Takes on a value from 1...255 for messages of type: NEW_PARENT, CANCEL_PARENT, LINK_STATE_UPDATE_A, and LINK_STATE_UPDATE_B. All other message types SHOULD set Num_Sources = 0. Offset (12 bits): Offset (in bytes) from the 0'th byte of the current atomic message header to the 0'th byte of the NEXT atomic message header in the "compound message" (see the following section for the compound message specification.) Offset == 0 indicates no further atomic messages follow. The 12-bit offset field imposes a 4 kilobyte length restriction on individual atomic messages. LSEQ (4 bits): The link sequence number for this message. Identity of Receiver (32 bits): The IPv4 address of the receiving node which MUST process this atomic message. All other nodes MUST NOT process this atomic message. This field exists ONLY if the M bit is set to UNICAST. 6.4.2. Compound TBRPF Message Format Multiple atomic TBRPF messages may be concatenated to form a compound message within a single UDP/IPv4 packet. Atomic message headers MUST be aligned on 32-bit boundaries, therefore an atomic message body with a non-integral number of 32-bit words will include 1, 2 or 3 padding bytes preceding a subsequent message header. NO additional header is required for a compound message; the header from the 1st atomic message serves as the initial header for the compound message. The format for a compound TBRPF message is shown below (where N is the number of concatenated atomic messages): Bellur, Ogier, and Templin Expires 11 January 2001 [Page 23] INTERNET-DRAFT TBRPF 11 July 2000 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ TBRPF atomic message header (1) ~ +---------------------------------------------------------------+ | | ~ TBRPF atomic message body (1) ~ ~ (variable length) ~ ~ +---------------+ | |PAD (0-3 bytes)| +-----------------------------------------------+---------------+ ~ TBRPF atomic message header (2) ~ +---------------------------------------------------------------+ | | ~ TBRPF atomic message body (2) ~ ~ (variable length) ~ ~ +---------------+ | |PAD (0-3 bytes)| +---------------+---------------+---------------+---------------+ ~ ... ~ ~ ... ~ ~ ... ~ +---------------+---------------+---------------+---------------+ ~ TBRPF atomic message header (N) ~ +---------------+---------------+-------------------------------+ | | ~ TBRPF atomic message body (N) ~ ~ (variable length) ~ ~ ~ | (NO Padding bytes required on final message body) | +---------------+---------------+---------------+---------------+ 6.4.3. TBRPF Atomic Message Body Format The format of the atomic message body depends on the 'Type' field in the corresponding message header. The following sections define the formats for atomic message bodies for TBRPF Version 1. 6.4.3.1. ACK The ACK message carries a NULL message body. The 4-bit acknowledgment sequence number (from 0...15) is carried in the TBRPF message header LSEQ field. Bellur, Ogier, and Templin Expires 11 January 2001 [Page 24] INTERNET-DRAFT TBRPF 11 July 2000 6.4.3.2. NACK 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bitmap | +-------------------------------+ Bitmap (16 bits): A 16-bit vector; bits indicate messages lost/received for the 16 messages prior to the 4-bit sequence number supplied in the TBRPF message header LSEQ field. As described in Section 5.2.1, the LSEQ field is set to the sequence number of the last broadcast control message received from the neighbor to which the NACK is being sent. 6.4.3.3. NEW_PARENT: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Identity for Src(1) | +-------------------------------+-------------------------------+ | Identity for Src(2) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Identity for Src(m) | +-------------------------------+-------------------------------+ | Sequence Number for Src(1) | Sequence Number for Src(2) | +-------------------------------+-------------------------------+ | Sequence Number for Src(3) | Sequence Number for Src(4) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Sequence Number for Src(m-1) | Sequence Number for Src(m) | +-------------------------------+-------------------------------+ Identity for Src(i) (32 bits): The IPv4 address of the ith Source (1 <= i <= m) Sequence Number for Src(i) (16 bits): A sequence number from 0...65535 Bellur, Ogier, and Templin Expires 11 January 2001 [Page 25] INTERNET-DRAFT TBRPF 11 July 2000 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: ~ ... ~ +-------------------------------+-------------------------------+ | Sequence Number for Src(m-2) | Sequence Number for Src(m-1) | +-------------------------------+-------------------------------+ | Sequence Number for Src(m) | +-------------------------------+ 6.4.3.4. CANCEL_PARENT: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Identity for Src(1) | +-------------------------------+-------------------------------+ | Identity for Src(2) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Identity for Src(m) | +-------------------------------+-------------------------------+ Identity for Src(i) (32 bits): The IPv4 address of the ith Source (1 <= i <= m) 6.4.3.5. HEARTBEAT 0 0 1 2 3 4 5 6 7 8 +-+-+-+-+-+-+-+-+ |BCAST Sequence#| +---------------+ Sequence # for BCAST Channel (8 bits): A sequence number from 0...15 (effectively, only 4 bits) Bellur, Ogier, and Templin Expires 11 January 2001 [Page 26] INTERNET-DRAFT TBRPF 11 July 2000 6.4.3.6. END_OF_BROADCAST 0 0 1 2 3 4 5 6 7 8 +-+-+-+-+-+-+-+-+ |BCAST Sequence#| +---------------+ Sequence # for BCAST Channel (8 bits): A sequence number from 0...15 (effectively, only 4 bits) 6.4.3.7. LINK_STATE_UPDATE_A TBRPF provides two formats for link-state update messages. Messages of type LINK_STATE_UPDATE_A include a single sequence number per source, and is therefore used only if the updates for all links com- ing out of the same source have the same sequence number. (For exam- ple, periodic updates have this property.) This is done to reduce the message size. Messages of type LINK_STATE_UPDATE_B include a separate sequence number for each link. 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 *********************** lsuA for Src(1) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Identity of node Src(1) | +-------------------------------+-------------------------------+ | Num_Neighbors (==k[1]) | Sequence Number for Src(1) | +-------------------------------+-------------------------------+ | Identity for Nbr(1) of Src(1) | +-------------------------------+-------------------------------+ | Metrics for Nbr(1) of Src(1) | +-------------------------------+-------------------------------+ | Identity for Nbr(2) of Src(1) | +-------------------------------+-------------------------------+ | Metrics for Nbr(2) of Src(1) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Identity for Nbr(k[1]) of Src(1) | +-------------------------------+-------------------------------+ | Metrics for Nbr(k[1]) of Src(1) | +-------------------------------+-------------------------------+ Bellur, Ogier, and Templin Expires 11 January 2001 [Page 27] INTERNET-DRAFT TBRPF 11 July 2000 *********************** lsuA for Src(2) ************************* +-------------------------------+-------------------------------+ | Identity of node Src(2) | +-------------------------------+-------------------------------+ | Num_Neighbors (==k[2]) | Sequence Number for Src(2) | +-------------------------------+-------------------------------+ | Identity for Nbr(1) of Src(2) | +-------------------------------+-------------------------------+ | Metrics for Nbr(1) of Src(2) | +-------------------------------+-------------------------------+ | Identity for Nbr(2) of Src(2) | +-------------------------------+-------------------------------+ | Metrics for Nbr(2) of Src(2) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Identity for Nbr(k[2]) of Src(2) | +-------------------------------+-------------------------------+ | Metrics for Nbr(k[2]) of Src(2) | +-------------------------------+-------------------------------+ ~ ... ~ ~ ... ~ *********************** lsuA for Src(m) ************************* +-------------------------------+-------------------------------+ | Identity of node Src(m) | +---------------------------------------------------------------+ | Num_Neighbors (==k[m]) | Sequence Number for Src(m) | +---------------------------------------------------------------+ | Identity for Nbr(1) of Src(m) | +-------------------------------+-------------------------------+ | Metrics for Nbr(1) of Src(m) | +-------------------------------+-------------------------------+ | Identity for Nbr(2) of Src(m) | +-------------------------------+-------------------------------+ | Metrics for Nbr(2) of Src(m) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Identity for Nbr(k[m]) of Src(m) | +-------------------------------+-------------------------------+ | Metrics for Nbr(k[m]) of Src(m) | +-------------------------------+-------------------------------+ Each lsuA for Src(i), for (1 <= i <= m), contains: Identity for Src(i) (32 bits): The IPv4 address of Src(i) Bellur, Ogier, and Templin Expires 11 January 2001 [Page 28] INTERNET-DRAFT TBRPF 11 July 2000 Num_Neighbors (==k[i]) (16 bits): The number of neighbors 'k[i]' of Src(i) Sequence Number for Src(i) (16 bits): A sequence number from 0...65535 Identity for Nbr(j), for (1 <= j <= k[i]) (32 bits): The IPv4 address of Nbr(j) of Src(i) Link Metrics for Nbr(j), for (1 <= j <= k[i]) (32 bits): The link metrics associated with Nbr(j) of Src(i) 6.4.3.8. LINK_STATE_UPDATE_B 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 *********************** lsuB for Src(1) ************************* +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Identity of node Src(1) | +---------------------------------------------------------------+ | Num_Neighbors (==k[1]) | Reserved | +---------------------------------------------------------------+ | Identity for Nbr(1) of Src(1) | +-------------------------------+-------------------------------+ | Link Metrics for Nbr(1) | Sequence # for Src(1),Nbr(1) | +-------------------------------+-------------------------------+ | Identity for Nbr(2) of Src(1) | +-------------------------------+-------------------------------+ | Link Metrics for Nbr(2) | Sequence # for Src(1),Nbr(2) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Identity for Nbr(k[1]) of Src(1) | +-------------------------------+-------------------------------+ | Link Metrics for Nbr(k) | Sequence # for Src(1),Nbr(k) | +-------------------------------+-------------------------------+ Bellur, Ogier, and Templin Expires 11 January 2001 [Page 29] INTERNET-DRAFT TBRPF 11 July 2000 *********************** lsuB for Src(2) ************************* +-------------------------------+-------------------------------+ | Identity of node Src(2) | +---------------------------------------------------------------+ | Num_Neighbors (==k[2]) | Reserved | +-------------------------------+-------------------------------+ | Identity for Nbr(1) of Src(2) | +-------------------------------+-------------------------------+ | Link Metrics for Nbr(1) | Sequence # for Src(2),Nbr(1) | +---------------------------------------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Identity for Nbr(k[m-1]) of Src(m-1) | +-------------------------------+-------------------------------+ | Link Metrics for Nbr(k[m-1]) | Seq. # for Src(m), Nbr(k[m-1])| +-------------------------------+-------------------------------+ ~ ... ~ ~ ... ~ ~ ... ~ *********************** lsuB for Src(m) ************************* +-------------------------------+-------------------------------+ | Identity of node Src(m) | +---------------------------------------------------------------+ | Num_Neighbors (==k[m]) | Reserved | +---------------------------------------------------------------+ | Identity for Nbr(1) of Src(m) | +-------------------------------+-------------------------------+ | Link Metrics for Nbr(1) | Sequence # for Src(m),Nbr(1) | +-------------------------------+-------------------------------+ ~ ... ~ +-------------------------------+-------------------------------+ | Identity for Nbr(k[m]) of Src(m) | +-------------------------------+-------------------------------+ | Link Metrics for Nbr(k[m]) | Seq. # for Src(m),Nbr(k[m]) | +-------------------------------+-------------------------------+ Each lsuB for Src(i), for (1 <= i <= m), contains: Identity for Src(i) (32 bits): The IPv4 address of Src(i) Num_Neighbors (==k[i]) (16 bits): The number of neighbors 'k[i]' of Src(i) Identity for Nbr(j), for (1 <= j <= k[i]) (32 bits): The IPv4 address of Nbr(j) of Src(i) Bellur, Ogier, and Templin Expires 11 January 2001 [Page 30] INTERNET-DRAFT TBRPF 11 July 2000 Link Metrics for Nbr(j), for (1 <= j <= k[i]) (16 bits): The link metrics associated with Nbr(j) of Src(i) (really, only 8 bits are used) Sequence # for Src(i), Nbr(j) for (1 <= j <= k[i]) (16 bits): Sequence number associated with link Src(i), Nbr(j) 6.4.3.9. RETRANSMISSION_OF_BROADCAST The RETRANSMISSION_OF_BROADCAST message provides the retransmission of a compound update message in response to a NACK message. As described in Section 5.2.1, broadcast update messages are retransmit- ted only on unicast channels. The compound message has the same form as that shown in Section 6.4.2, and may contain one or more atomic messages of type LINK_STATE_UPDATE_A or LINK_STATE_UPDATE_B con- catenated together. The compound message is preceded by an atomic message header, where LSEQ is the sequence number corresponding to the unicast channel on which the message is sent. The LSEQ of each atomic message in the compound message is the broadcast sequence number that was included in the original (broadcast) transmission of the message. Multiple RETRANSMISSION_OF_BROADCAST messages can be bundled into a compound message as described in Section 6.4.2. The RETRANSMISSION_OF_BROADCAST message has the following format: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Vers|M| Num_sources | Offset | LSEQ | +-------------------------------+-------------------------------+ | | ~ Compound Message ~ | | +-------------------------------+-------------------------------+ where the header fields have the following values: Type (4 bits): MUST be set to RETRANSMISSION_OF_BROADCAST (=9). Version (3 bits): Set to TBRPFVERSION_1 (=1) for the initial version. Mode (1 bit): MUST be set to UNICAST (=0). Bellur, Ogier, and Templin Expires 11 January 2001 [Page 31] INTERNET-DRAFT TBRPF 11 July 2000 Num_Sources (8 bits): SHOULD be set to 0. Offset (16 bits): Offset (in bytes) from the 0'th byte of the current compound message header to the 0'th byte of the NEXT compound message header in the RETRANSMISSION_OF_BROADCAST message. Allows con- catenation of compound messages up to 64 kilobytes in length. 7. 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 ETHERTYPE assignment for TBRPF Neighbor Discovery. As an alternative to 3., TBRPF could continue to use the existing ETHERTYPE assignment for ARP and new ARP opcodes could be reserved for the three TBRPF neighbor discovery message types presented in Section 6.3. It must be noted, however, that TBRPF neighbor discovery and ARP are mutually exclusive. TBRPF neighbor discovery is NOT an extension of ARP. 8. 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/all of these issues. 9. Implementation Status The current version of the TBRPF protocol as it applies to IPv4 MANETs (as described in this document) has been implemented in the FreeBSD V3.2 operating system with the Merit Multi-Threaded Routing Toolkit daemon (mrtd). The current implementation has been in use for laboratory and fielded experiments since June 1999. Bellur, Ogier, and Templin Expires 11 January 2001 [Page 32] INTERNET-DRAFT TBRPF 11 July 2000 10. 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. [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] David C. Plummer. An Ethernet address resolution protocol: Or converting 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. Bellur, Ogier, and Templin Expires 11 January 2001 [Page 33] INTERNET-DRAFT TBRPF 11 July 2000 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 11 January 2001 [Page 34]