Mobile Ad hoc Networking (MANET) R. Ghanadan Internet-Draft J. Hsu Intended status: Informational P. Khuu Expires: September, 2010 G. Sadosuk BAE Systems March 2010 Adaptive Hybrid Domain Routing (AHDR) draft-ghanadan-manet-ahdr-00 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. 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." This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. 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. This Internet-Draft will expire in September, 2010. Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. Abstract This document describes the Adaptive Hybrid Domain Routing (AHDR) protocol. It describes the parts of the protocol that are required of all implementations as well as optional requirements that each implementation may include. AHDR allows router nodes to form far- reaching ad-hoc networks, especially in wireless environments. AHDR uses a combination of proactive and reactive routing schemes to be Ghanadan, et al. Expires September 2010 [Page 1] Internet-Draft AHDR March 2010 responsive to topology changes without incurring high protocol overhead. AHDR adapts to network conditions in order to minimize network overhead and maximize network reachability. Document Conventions The key words "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 [1]. The use of "." character to specify a software or message structure indicates a value or field in a hierarchy of data structures. For instance "Reader.Hair.Color" would indicate the color of the reader's hair. The value might be Blonde or Black or even None. The use of "[]" characters specifies a table of elements. A value within braces indicates a particular element (all indexes begin with 0). For instance, "George.Children[0].Name" would indicate the name of George's first child. Every table also has an implied .Count field that indicates how many elements are currently present in the table. Table of Contents 1. Introduction ................................................... 4 2. Applicability .................................................. 5 3. Terminology .................................................... 6 4. AHDR Protocol Overview ......................................... 9 4.1. Proactive Routing ........................................ 9 4.2. Reactive Routing ........................................ 10 4.3. Domain Architecture ..................................... 11 5. AHDR Data Structures .......................................... 13 5.1. AHDR Nodeid Length (Node.IDLength) ...................... 13 5.2. AHDR Nodeid (Node.Nodeid) ............................... 13 5.3. AHDR Networkid (Node.Networkid) ......................... 14 5.4. Topology Timeout (Node.Timeout.Topology) ................ 14 5.5. Link Timeout (Node.Timeout.Link) ........................ 14 5.6. LCI -- Link Congestion Indicator (Node.LCI) ............. 14 5.7. IP Address ReDistribution Data (IPAD) ................... 15 5.8. Configured IP Addresses for ReDistribution (Node.IPAD.Configured[]) ..................................... 15 5.9. Advertised IP Addresses for ReDistribution (Node.IPAD.Advertised[]) ..................................... 16 5.10. HOPK Timeout (Node.Timeout.HOPK) ....................... 16 5.11. IPAD Timeout (Node.Timeout.IPAD) ....................... 16 5.12. Checksum Use (Node.Checksum) ........................... 16 5.13. AHDR Timer (Timer) ..................................... 17 5.14. Node Timer (Node.Timer) ................................ 17 Ghanadan, et al. Expires September 2010 [Page 2] Internet-Draft AHDR March 2010 6. AHDR Network Information ...................................... 17 6.1. Network Coverage (Node.Coverage) ........................ 18 6.2. HOP1 Table (Node.HOP1[]) ................................ 18 6.3. HOP2 Table (Node.HOP2[]) ................................ 19 6.4. HOPK Table (Node.HOPK[]) ................................ 20 6.5. Bridge Table (NODE.Bridge[]) ............................ 21 6.6. Domain Lead Table (Node.DomainLead[]) ................... 22 6.7. Domain Coverage Table (Node.DomainCoverage[]) ........... 23 6.8. IPAD Learned Address Table (Node.IPAD.Learned[]) ........ 23 7. AHDR Messages ................................................. 23 7.1. AHDR Message Header ..................................... 24 7.2. AHDR Message Body ....................................... 25 7.3. AHDR Message Checksum ................................... 25 7.4. TU0 -- Topology Update 0 Message ........................ 26 7.5. TU1 -- Topology Update 1 Message ........................ 26 7.6. TUD -- Topology Update Domain Message ................... 29 7.7. DLA -- Domain Lead Announcement Message ................. 36 7.8. DLR -- Domain Lead Renouncement Message ................. 36 7.9. RDISC -- Route Discovery Message ........................ 37 7.10. RRES -- Route resolution Message ....................... 41 7.11. RERR -- Route Error Message ............................ 42 7.12. IPAD -- IP Address ReDistribution Message .............. 43 8. AHDR Processes ................................................ 48 8.1. Main Process ............................................ 48 8.2. Message Receive Process ................................. 49 8.3. Maintain Link Process ................................... 50 8.4. Link Lost Process ....................................... 51 8.5. Message Send Process .................................... 52 8.6. Calculate Domain Lead Process ........................... 52 8.7. Route Discovery Process ................................. 54 8.8. Bridge Selection Process ................................ 55 8.9. Domain Lead Tracking Process ............................ 57 8.10. Create Checksum Process ................................ 57 8.11. Check Checksum Process ................................. 58 8.12. TU0 Processes .......................................... 58 8.13. TU1 Processes .......................................... 59 8.14. TUD Processes .......................................... 60 8.15. DLA Processes .......................................... 61 8.16. DLR Processes .......................................... 62 8.17. RDISC Processes ........................................ 63 8.18. RRES Processes ......................................... 64 8.19. RERR Processes ......................................... 65 8.20. IPAD Processes ......................................... 66 9. Security Considerations ....................................... 67 10. References ................................................... 67 11. Acknowledgments .............................................. 67 12. Author's Addresses ........................................... 67 Ghanadan, et al. Expires September 2010 [Page 3] Internet-Draft AHDR March 2010 1. Introduction Adaptive Hybrid Domain Routing (AHDR) is a MANET routing protocol. AHDR implements a strategic hybrid combination of proactive and reactive routing schemes. Both routing schemes use a cluster-based organization to efficiently disseminate AHDR information through the network. To form these clusters, every AHDR node periodically announces its presence plus its 1-hop neighbors. AHDR uses this information to organize nodes within a 2-hop neighborhood into logical groups called Domains. Each Domain elects a Domain Lead that has the highest 1-hop coverage in terms of link metrics. The proactive routing scheme disseminates Domain topology information through the network. As Domain topology (i.e., membership) changes, each Domain Lead announces the topology changes to all other Domain Leads in the network. To forward this information, each node in the domain selects a set of Bridge Nodes--a subset of nodes that have links to nearby Domain Leads. Only Bridge Nodes are used to forward the topology updates between the Domain Leads. The goal is to have only a small subset of the network nodes (the Domain Lead and the Bridge Node) carry the topology information through the entire network. This reduces the AHDR overhead in the network. Nodes that receive the topology information use it to build up their routing tables to the distant Domain Nodes. The reactive routing scheme is used when a source AHDR node does not have a known route to a required destination. The source sends a route discovery message first to its Domain Lead. If the Domain Lead does not know a route for that destination it forwards the request to other nearby Domain Leads via its Bridge Nodes. The results of the route request return to the originator via Bridge Nodes as well. Again, this scheme uses only a small subset of the network nodes carry the network routing messages through the network which reduces the AHDR overhead. AHDR does not impose either a flat or hierarchical routing scheme that is a function of the router forwarding engine which is not a part of the AHDR specification. This document specifies the AHDR protocol including the information elements, and their exchange requirements with the neighboring routers supporting AHDR, the associated message formats, and the message processing procedures to realize the protocol. The general operation for the protocol will be specified so that any node using a conforming implementation of AHDR will be able to form a network with nodes running any other conforming implementation. This document Ghanadan, et al. Expires September 2010 [Page 4] Internet-Draft AHDR March 2010 also specifies optional features which will allow each implementation to be tailored to specific wireless conditions. Specifications for the optional features include behaviors that MAY be implemented as well as different algorithms that MAY be used to implement required behavior. 2. Applicability AHDR is a hybrid proactive and reactive routing protocol. It is designed to provide network routing services for networks with the following characteristics: o high topological rate of change o large network size o networks with high 1-hop density o limited link capacity where network routing overhead per node must be carefully controlled In networks that are large, dense and highly mobile, a high topology rate of change can introduce excessive control overhead into the network. In such conditions, it is important to prevent each node from independently flooding the network with its topology update messages. But instead, have only a small subset of nodes in AHDR generate the topology update messages and flood them into the network. AHDR does this by abstracting the physical network topology into logical groups called Domains. Each Domain has a Domain Lead (Domain Lead). Only the Domain Lead generates the topology update messages for the whole Domain, and forwards this information through a set of Bridge Nodes. Although fewer nodes are responsible for generating the topology update messages, the messages still contain complete information about the latest topology information in that respective Domain. Thus, AHDR does not compromise in terms of network reachability. To further help reduce the routing overhead in networks with potentially low channel capacity, the frequency at which the Domain Lead generates the topology update message is user configurable. However, a lower frequency for topology update implies that it will take relatively longer time for node(s) from one side of the network to be informed about changes to the network topology on the other side of the network. In this case, AHDR provides the reactive routing component so that the route can be discovered faster. Again, instead of flooding the route discovery messages to all nodes in the network, these messages are only forwarded to the Domain Leads through a set of Bridge Nodes. Using a combination of proactive routing, reactive routing, and its Domain architecture, AHDR is suitable in networks where the user Ghanadan, et al. Expires September 2010 [Page 5] Internet-Draft AHDR March 2010 application traffic may be sporadic and the number of traffic flows may be relatively high or low. AHDR supports network operation where the network node(s) may be equipped with multiple interfaces. In this case, AHDR may be reconfigured to operate over all interfaces. Alternatively, a subset of the interfaces may be configured to run AHDR while the remaining interfaces are configured to run other routing protocols. In either case, AHDR supports the route redistribution function where the network address(es) learned via one interface is shared with the others. Although the protocol is designed to accommodate specific networks as described above, AHDR has also been shown to generate low network routing overhead while still providing high and accurate network reachability in networks with lower mobility pattern, smaller network size, and sparse 1-hop density. 3. Terminology To discuss the AHDR design, the following terms are used. Each has a specific meaning that must remain consistent throughout this document, but the existence of these terms does not impose any specific requirements. 3.1. Implementation An AHDR implementation is software that conforms to the requirements in this document. A conforming implementation MAY support any number of optional features or optional algorithms as long as all required features and algorithms are supported. 3.2. AHDR Node An AHDR node is a logical, not a physical, entity which is a single executing instance of an AHDR implementation. Therefore, an AHDR node does not describe an entire hardware platform. On default, an AHDR node corresponds to a single physical interface on a hardware platform. This is not a requirement; multiple AHDR nodes can be run on a single physical interface, and a single AHDR node can be run on multiple physical interfaces. The AHDR node is only the instance of the implementation. Every AHDR node is supported by the platform on which it is executing by having all of the following capabilities available to it: (1) Storing and exchanging AHDR Network information, AND Ghanadan, et al. Expires September 2010 [Page 6] Internet-Draft AHDR March 2010 (2) Receiving AHDR Messages from other AHDR Nodes, AND (3) Sending AHDR Messages to other AHDR Nodes, AND (4) Deciding that some time interval has expired. 3.3. AHDR Link An AHDR link is a 1-hop communications link between two AHDR nodes. An AHDR link can be confirmed or unconfirmed. A confirmed is a symmetrical link exists when both A and B acknowledge through AHDR messages that the link to the other exists. 3.4. AHDR Network An AHDR network is a collection of AHDR nodes and AHDR links. Each AHDR node in a network has identified itself with the same AHDR Networkid as all the other nodes in the network. An AHDR node is an executing instance of an AHDR implementation and is independent of the hardware platform. Because the networks are logical only, multiple AHDR networks could overlay each other on a single set of physical hardware. 3.5. HOP1 Table The HOP1 table is a list of all AHDR links (confirmed and unconfirmed) that a node has to other AHDR nodes. All nodes in the HOP1 Table are therefore 1-hop neighbors. Each HOP1 Table entry contains the 1-hop Nodeid and other network information. 3.6. HOP2 Table A HOP2 Table is a list of all 2-hop neighbor nodes. Both hops of the 2-hop path to the HOP2 neighbor are confirmed links. Each HOP2 Table entry contains the 2-hop Nodeid, the 1-hop neighbor that can reach it, and other network information. 3.7. HOPK Table A HOPK Table is a list of all other AHDR nodes that are 3 or more network hops away. All network hops are confirmed links. Each HOPK Table entry contains the destination Nodeid, the 1-hop neighbor that can reach it, and other link related information. 3.8. Link State Level (LSL) An LSL is a value that quantifies the overall character of an AHDR link. It is a combination of the Link Congestion Indicator (LCI-- Ghanadan, et al. Expires September 2010 [Page 7] Internet-Draft AHDR March 2010 this node's congestion metric) and Link Quality Indicator (LQI--the receive quality at the other node in the link) of a given AHDR link. 3.9. Domain Lead A Domain Lead node is a node within a Domain which is a 1-hop neighbor of all nodes in the Domain and has the highest Network Coverage of all nodes in the Domain. Domain Leads exchange Topology Update (TUD) messages with all other Domain Leads. Domain Leads also send route discovery messages to other Domain Leads when searching for a destination Node that is currently unknown. Domain Leads also broadcast Topology Update (TU1) messages periodically to keep local topology information current. Domain Leads in a network will always be 2 or 3 network hops apart due to the method in which Domain Leads are selected. 3.10. Domain Node A Domain Node is a node which has selected a confirmed 1-hop neighbor as its Domain Lead. Each Domain Node in a Domain is within two network hops of all other Domain Nodes in the same Domain. Domain Nodes broadcast Topology Update (TU1) messages periodically that the Domain Lead uses to keep local topology information current. 3.11. Domain An AHDR Domain is a logical group of nodes that consists of a Domain Lead along with all Domain Nodes that have selected the same Domain Lead. Domains are used to organize the network to make topology updates and route resolution more efficient. 3.12. Bridge Node A Bridge Node is any node selected to most efficiently forward AHDR messages from one Domain Lead node to all other Domain Lead nodes in the network. Every node in the network will select a set of Bridge Nodes through which that node can reach node known neighboring domains. If the Domain Lead is more than 1-hop away, the Bridge Node will forward to its own Bridge Node(s) to get to the neighboring Domain Lead(s). Any Domain Lead or Domain Node may be selected as a Bridge Node. The conditions are not exclusive. Ghanadan, et al. Expires September 2010 [Page 8] Internet-Draft AHDR March 2010 3.13. Network Coverage Network Coverage is used in determining the Domain Lead for a given Domain. Network Coverage may be expressed in terms of a weighted function derived from the number of HOP1 nodes and their corresponding LSL values. Bridge Nodes are selected based on their Domain Coverage of neighboring domains. 3.14. Domain Coverage Domain Coverage is used in determining Bridge Nodes. Each node evaluates information from its 1-hop neighbors to determine neighboring Domains accessible by each neighbor and how many nodes in each neighboring Domain it can reach. This helps the node determine an optimal set of Bridge Nodes. 4. AHDR Protocol Overview The protocol is comprised of three main components: o Proactive Routing - advertisement of known routes through the network o Reactive Routing - discovery of unknown routes as required o Domain Architecture - grouping of nodes into logical Domains for efficient information dissemination and loop control 4.1. Proactive Routing The proactive portion of AHDR periodically exchanges network information with 1-hop neighbors and between Domain Leads, regardless of topology conditions. The following subsections will focus on the details of the proactive core, from neighbor discovery to network formation. 4.1.1. Neighbor and Network Discovery A node with no known neighbors will broadcast Topology Update 0 (TU0) messages until a neighbor is detected. Neighbors are detected when AHDR messages are received from them. The node records the detected neighbor node's Nodeid and Link State Level (LSL) into its Hop 1 (HOP1) Table. When the HOP1 table is no longer empty (but does not yet contain a Domain Lead), the node begins to broadcast periodic Topology Update (TU1) messages containing its HOP1 neighbor information. Upon receiving TU1 messages, each node is able to build up its HOP1 and HOP2 tables (see section 3.5 and 3.6 for more information on Ghanadan, et al. Expires September 2010 [Page 9] Internet-Draft AHDR March 2010 these tables). The LSL of a given link between two nodes is calculated based on conditions at the receiving node (e.g., signal strength of the received message or congestion of the receiving node). The received TU1 message contains the link quality and congestion information of the one way link from the sender to the receiver. Therefore, after a node transmits a TU0 or TU1, and a successive TU1 is received with an LSL value associated with the SID of the node as a 1-hop neighbor, the link becomes confirmed. This establishes a symmetric link between the nodes. An entry in the HOP1 table is removed if its unconfirmed timer expires. 4.1.2. Network Topology Update Domain Leads send periodic updates of its Domain Node membership to other Domain Leads. The Domain Topology Update (TUD) message is exchanged between Domain Leads to provide topology information on an inter-Domain level. The TUD is propagated to all known Domain Leads via Bridge Nodes. From TUDs, each Domain Lead learns of the HOP1 neighbors of every other Domain Lead. Partial TUDs are sent between full TUDs, containing only information about nodes added or dropped from the Domain. From the received TUD messages, each Domain Lead learns the return path to the originating TUD source Domain Lead and the Domain Nodes of the given Domain Lead. Thus each Domain Lead builds up a complete routing table to all known network nodes. To further limit network control overhead, the inter-Domain TUD updates could be configured to only contain HOP1 neighbors that have selected the Domain Lead as their Domain Lead to avoid multiple TUD entries of a single node in overlapping domains. A configurable option also enables Domain Leads to include all HOP1 nodes in its TUD update for cases such as fast changing topology with small Domain sizes. 4.2. Reactive Routing When a Domain Node needs to send a message to a destination with an unknown route, the next hop node is determined by sending a Route Discovery (RDISC) message to the Domain Lead, and receiving a Route Resolution (RRES) in reply. The Domain Lead serves to resolve queries for unknown routes among its Domain Nodes. 4.2.1. Route Discovery (RDISC) and Route Resolution (RRES) Ghanadan, et al. Expires September 2010 [Page 10] Internet-Draft AHDR March 2010 When a source node generates an RDISC message and sends it to its Domain Lead, the source node expects an RRES back from the Domain Lead indicating a next hop node that can reach the destination node. Upon receiving the RDISC message, the Domain Lead of the source Domain will reply with a RRES if it is able to locate the destination within its own routing tables. If not, it will forward the RDISC message to other Domain Leads in the network. The RDISC is forwarded through Bridge Nodes to other Domain Leads. If a DL is able to resolve the requested route it will stop the RDISC forwarding. An RRES message is generated once the destination node in the RDISC message is resolved by either the Domain Lead or the Bride Nodes receiving the RDISC. The RRES message is unicast hop-by-hop back to the original source node. As the RRES message propagates, each intermediate node (including the Bridge Nodes and Domain Leads) updates their routing tables. If more than 1 reply is received, one or more entries could be stored in the HOPK table of the source node. 4.3. Domain Architecture AHDR uses a logical two-tiered architecture (but physically flat architecture) to minimize the number of routing control messages generated and to more efficiently flood these control messages. A tracking mechanism is used to control the looping of routing control message due to network mobility. 4.3.1. Domain Formation and Maintenance An AHDR network is composed of logical groups called Domains, which may physically overlap. Initial network formation takes place when a node designates itself as Domain Lead with a Domain Lead Announcement (DLA), and all nodes (at least one) within a 1-hop range acknowledge this node as their Domain Lead. This acknowledgement is contained in the TU1 messages. More than one Domain Lead within range of a given node could be included in the TU1 message, but the node's Domain Lead will be listed first in the Domain Lead table. A Domain Lead is designated based on HOP1 Network Coverage, which is shared among 1-hop neighbors in the TU1 message exchange. This designation is contingent upon the condition that none of its 1-hop neighbors is already a Domain Lead. Otherwise, the new Domain Lead must surpass the Network Coverage of the existing Domain Lead by a certain threshold before it can designate itself the new Domain Lead. In the case where this threshold is surpassed, the previous Domain Ghanadan, et al. Expires September 2010 [Page 11] Internet-Draft AHDR March 2010 Lead will acknowledge the new Domain Lead by broadcasting a Domain Lead Renouncement (DLR). 4.3.2. Topology Change Propagation Local topology changes are shared among 1-hop nodes through TU1 messages. Topology changes detected by a node are shared with 1-hop neighbors through TU1 messages. The Domain architecture collects topology change information for an entire Domain. To reduce the number of announcements, inter-Domain topology changes and updates are announced in a single message instead of announcing each topology change in a separate message. The inter-Domain topology updates (TUD) are forwarded through Bridge Nodes as part of the Domain architecture. Bridge nodes are selected either for minimal transmissions or maximum path diversity. Bridge Nodes are continuously evaluated at every Node in the network and updated to reflect topology changes. The Domain architecture also provides loop-free propagation of the topology change announcements through Bridge Nodes to each Domain. Topology changes are tracked by forwarding Bridge Nodes and redundant messages are eliminated as messages propagate through the entire network. 4.3.3. Loop Free Broadcast AHDR logical hierarchy enables efficient tracking of messages that are broadcast throughout the network, such as TUD and RDISC messages. These messages include a sender Nodeid and a sequence number which are used to ensure that a given message is not forwarded more than once by any node. Furthermore, each forwarded message is tracked and marked as it passes through Domains to eliminate redundant message broadcasts within the same area. The sequence number is a unique value generated by the originator of the message. As a TUD or RDISC is broadcasted, the Bridge Nodes IDs are embedded within the payload. Every node within one hop distance will receive the message, but only Bridge Nodes whose IDs are included in the message will take action and forward the message to their Bridge Nodes and DL(s). Subsequent TUD or RDISC messages from the same Node will have a sequence number one higher than the previous message. Keeping track of sequence numbers seen will allow nodes to detect and discard old messages and to control the retransmission of messages that have already been forwarded. Ghanadan, et al. Expires September 2010 [Page 12] Internet-Draft AHDR March 2010 To prevent routing loops and redundant dissemination of messages, the Domain Lead of each intermediate Bridge Node is tracked and the number of times a message can be propagated within a single Domain is limited. The Domain Lead Track contains information that will limit redundant messages from propagating forward. 5. AHDR Data Structures Following are the configurable parameters on a per interface basis. Those marked as [REQUIRED] must be maintained by the host platform and SHALL be configurable by the network user. Each parameter has a proposed default value which may be overwritten via configuration. Those marked as [OPTIONAL] SHALL be maintained by the host platform if configured by the network user. For each item, the following additional information is provided: o SOURCE - How AHDR learns the information o USES - How AHDR uses the information Where values are required to fit into AHDR message fields, refer to the AHDR message definitions in Section 7 for information about the size of the field and its valid values. 5.1. AHDR Nodeid Length (Node.IDLength) [REQUIRED] This value SHALL indicate the length of all .Nodeid fields for this Node. The value SHALL fit in the .Header.IDLength field. A value of 0 SHALL indicate .Nodeids are 16 bits, a values of 1 SHALL indicate .Nodeids are 32 bits, etc., up to value 15 which indicates 256 bits. o SOURCE: Configuration o USES: .Header.IDLength field 5.2. AHDR Nodeid (Node.Nodeid) [REQUIRED] The Nodeid is used to identify the AHDR node in the AHDR network. The value SHALL be any value other than 0 that fits in a field whose size is indicated by Node.IDLength. The combination of Node.Nodeid and Node.Networkid SHALL uniquely identify an AHDR node. If two AHDR nodes have the same Node.Nodeid and Node.Networkid, the results are unpredictable. Future version of AHDR may provide a method for resolving the conflict. o SOURCE: Configuration o USES: Sent in all AHDR messages Ghanadan, et al. Expires September 2010 [Page 13] Internet-Draft AHDR March 2010 5.3. AHDR Networkid (Node.Networkid) [REQUIRED] The Networkid is used to identify the AHDR network that the AHDR node belongs to. The value SHALL fit in the .Header.Networkid field. The default value is 0. Nodes with no particular need to distinguish among networks should use the default Networkid value. o SOURCE: Configuration o USES: Sent in all AHDR messages 5.4. Topology Timeout (Node.Timeout.Topology) [REQUIRED] The Topology Timeout is used to time the intervals between sending AHDR Topology Messages. It is included in some AHDR messages so that other nodes can calculate when they should next hear from a node again. The value SHALL fit in the TU1.Timeout field when expressed in milliseconds. o SOURCE: Configuration o USES: Sent in TU1 and TUD messages 5.5. Link Timeout (Node.Timeout.Link) [OPTIONAL] The Link Timeout is used to calculate how long an AHDR link is maintained when no messages are being received from the node at the other end of the link. o SOURCE: Configuration o USES: HOP1 Table entry expiration 5.6. LCI -- Link Congestion Indicator (Node.LCI) [REQUIRED] The LCI is used to indicate to other Nodes any routing delay that may occur in network traffic passing through the Node. The value SHALL fit in the .Header.Con field. The value 0 indicates the node is very congested and a value of 3 indicates the node is not congested. The values 1 and 2 represent some congestion level in between the two extremes. The criteria for determining the LCI value are implementation specific. If the LCI determination function is not supported, the value 3 SHALL be used. o SOURCE: Calculated based on current condition; the default value can be configured a priori o USES: Sent in all AHDR messages Ghanadan, et al. Expires September 2010 [Page 14] Internet-Draft AHDR March 2010 5.7. IP Address ReDistribution Data (IPAD) This structure is used in various tables in the Node. An IPAD address entry has a variable length based on the IP address version being stored. Fields are: Type: Type of address. Value must fit into IPAD.Address[].Type field. Values SHALL be: 2: IPv4 (32 bits) 3: IPv6 (128 bits) All remaining values are reserved. Action: Value SHALL fit into IPAD.Address[].Action field. Values SHALL be 0 for no action, 1 for add, 2 for delete, 3 for modify. Other values are reserved. Networkid: AHDR Networkid for both IPAD.Source and IPAD.Address field. Value SHALL fit into .Header.Networkid field. IDLength: Length of .Source in 2-byte WORDs (i.e., one-half of byte length or 1/16th of the bit length) minus one. Value SHALL fit into .Header.IDLength field. Source: Where address was learned from. Size of address SHALL be indicated by IDLength. Metric: Routing metric. Value SHALL fit into IPAD.Address[].Metric field. Address: Address being advertised. Size of address SHALL be indicated by Type. Mask: Mask for address being advertised. Size of mask SHALL be indicated by Type. o SOURCE: depends on table entry is used in o USES: Entry in various IPAD tables. 5.8. Configured IP Addresses for ReDistribution (Node.IPAD.Configured[]) [OPTIONAL] The Configured IP Address Table contains a list of IP network addresses that this Node must advertise in its IPAD messages. The configure network addresses SHALL be used to populate the IPAD Advertised Address Table. The number of addresses allowed is not specified here, but consideration should be given to the size and number of IPAD messages that will result from an excessive number of addresses. Ghanadan, et al. Expires September 2010 [Page 15] Internet-Draft AHDR March 2010 o SOURCE: Configuration o USES: Sent in IPAD messages 5.9. Advertised IP Addresses for ReDistribution (Node.IPAD.Advertised[]) [OPTIONAL] The Advertised IP Address Table contains a list of routing addresses that this Node must advertise in its IPAD messages. These addresses SHALL be used when constructing IPAD messages. o SOURCE: Configuration o USES: Send in IPAD messages 5.10. HOPK Timeout (Node.Timeout.HOPK) [OPTIONAL] The HOPK Timeout is the number of Node.Timeout.Topology intervals to wait between sending full TUDs from a Domain Lead Node. Update TUDs may be sent no more often than every other Node.Timeout.Topology interval. It is also the number of OtherNode.Timeout.Topology intervals to keep a Node.HOPK[] table entry until it is deleted (where OtherNode is the source of the TUD entry). If a TUD message is received from OtherNode that confirms an existing entry, the timer on the entry is reset. o SOURCE: Configuration o USES: HOPK Table entry expiration 5.11. IPAD Timeout (Node.Timeout.IPAD) [OPTIONAL] The IPAD Timeout is the number of Node.Timeout.Topology intervals between sending full IPAD messages from a Node. Update IPADs may be sent no more often than 1/3 of this value. It is also the number of OtherNode.Timeout.Topology intervals to keep a Node.IPAD.Learned[] tables entry until it is deleted (where OtherNode is the source of the IPAD entry). If an IPAD message is received from OtherNode that confirms an existing entry, the timer on the entry is reset. o SOURCE: Configuration o USES: Learned IPAD Table entry expiration 5.12. Checksum Use (Node.Checksum) Ghanadan, et al. Expires September 2010 [Page 16] Internet-Draft AHDR March 2010 [REQUIRED] A value of 1 SHALL indicate that the Node will include a checksum in all its AHDR messages. A value of 0 SHALL indicate that it will not. This will affect the length of AHDR messages. o SOURCE: Configuration o USES: .Header.C field 5.13. AHDR Timer (Timer) AHDR Timer is the general timer structure consisting of an .Interval and a .Countdown field. When a timer, T, is SET, T.Interval and T.Countdown SHALL both given the same value. When a Timer is RESET, T.Countdown SHALL be given the T.Interval value. T.Countdown SHALL be decremented appropriately as time passes. If T.Countdown reaches 0, then T SHALL expire and T SHALL be RESET. The TU1.Timeout is a 16-bit timer value carried in the TU1 message (see Section 8.5.1). The TU1.Timeout value is used to derive the Node.HOP1[].Timer. Therefore, the .Interval and .Countdown fields SHALL be able to accommodate the TU1.Timeout value. The granularity of timers SHOULD be 250ms or smaller in order to make AHDR reasonably accurate. 5.14. Node Timer (Node.Timer) Node.Timer is an instance of an AHDR Timer. It is used to determine the AHDR message transmit frequency. Depending on the current status of the AHDR node, different message types may be sent. Details specifying the conditions governing the transmission of each of the AHDR message types are in Section 7. 6. AHDR Network Information The data structures outlined in this section SHALL be organized and tracked by each AHDR node. They represent data about the network that each node learns from AHDR Messages received during operation. The information is used, in turn, to populate the AHDR Messages that each node sends. Each AHDR node SHALL maintain all of the data structures in this section that are marked "[REQUIRED]". Each AHDR may optionally maintain any of the data structures in this section that are marked "[OPTIONAL]". o SOURCE - How AHDR learns the information o USES - How AHDR uses the information Ghanadan, et al. Expires September 2010 [Page 17] Internet-Draft AHDR March 2010 6.1. Network Coverage (Node.Coverage) [REQUIRED] Each Node SHALL calculate a Network Coverage value that quantifies its suitability to be a Domain Lead. Normally, this value is calculated based on the number of confirmed AHDR links in the HOP1 Table. A suggested algorithm selects the node with the most AHDR links with each link weighted by its LSL value. The algorithm selected to calculate this value will affect network performance. Careful consideration should be given in the following areas: (1) Evaluation: The quantity as well as the quality of confirmed links should be given consideration in the calculation. (2) Hysteresis: Once a node becomes a Domain Lead, some consideration should be given to leaving it as a Domain Lead unless local conditions change a great deal. Too many Domain Lead changes will adversely affect Network performance. (3) Privileged/Underprivileged Nodes: Certain nodes in the Network may make better or worse Domain lead candidates based on their location, mobility, power consumption, or other considerations. Here is an example Coverage calculation: NC = WDL * { W0 + N1(LINK+LSL) + N2(LINK+LSL) + ... + Nn(LINK+LSL) } Where: WDL (Weighted Domain Lead) is set to 1.0 for non-Domain Leads and >1.0 for Domain Leads W0 is some constant based on node's innate suitability to be a Domain Lead Nx(LINK+LSL) is the total weight assigned for 1-hop neighbors 1-n where: LINK is some constant added for the existence of a link (quantity) LSL is some value derived link state level (LCI + LQI) o SOURCE: Calculated from HOP1 Table data o USES: Sent in the Coverage information element of the TU1, DLA, and DLR message. 6.2. HOP1 Table (Node.HOP1[]) [REQUIRED] Each node SHALL maintain a HOP1 Table which contains information (learned from TU1 Messages) about the 1-hop links from this Node to other AHDR Nodes in the Network. The maximum number of Ghanadan, et al. Expires September 2010 [Page 18] Internet-Draft AHDR March 2010 entries in the table SHALL be limited to a value that will fit into the .HOP1s field in a TU1 message. Each entry in Node.HOP1[] describes an AHDR link. An entry SHALL be created, deleted, or updated when an AHDR message is received. See Section 8.2, Section 8.3, Section and 8.4 for more details. An entry SHALL be deleted if its .Timer expires. An entry SHALL consist of at least the following information. Additional information MAY be maintained by the implementation. .HOP1Node: The TU1.Header.Sender field from a received TU1 message. Value SHALL NOT be repeated within the HOP1 Table. This is the index field for the table used to uniquely identify each entry. .Confirmed: Indicates whether the link to the .HOP1Node is a confirmed link (value=1) or unconfirmed (value=0). .Coverage: This is the TU1.Coverage value from the most recent TU1 message received from the .HOP1Node. .DomainLead: Domain Lead Nodeid from the most recently received TU1 message from .HOP1Node. .ReceiveLSL: LSL value of received messages from most recent TU1 from .HOP1Node. Value SHALL fit into TU1.LSLTable[].From field. .SendLSL: LSL value of messages sent to .HOP1node. Value SHALL fit into TU1.LSLTable[].From field. .Timeout: TU1.Timeout value from most recent TU1 from .HOP1Node. .Timer: An AHDR Timer used to determine when a Confirmed entry should become Unconfirmed. The .Interval is Calculated as (Node.HOP1[].Timeout * Node.Timeout.Link * 2). .Timer is RESET each time the Confirmed link is reconfirmed by a received message. If .Timer expires, Node.HOP1[].Confirmed SHALL be changed to 0 (Unconfirmed). Once all effects of the entry becoming Unconfirmed (from the Confirmed state) are completed, the Unconfirmed entry MAY be removed from the HOP1 Table. o SOURCE: Received TU1 messages o USES: Route resolution; Sent in TU1 and TUD messages 6.3. HOP2 Table (Node.HOP2[]) [REQUIRED] Each Node SHALL maintain a HOP2 Table which contains information (learned from received TU1 Messages) about AHDR nodes Ghanadan, et al. Expires September 2010 [Page 19] Internet-Draft AHDR March 2010 that can be reached via a 1-hop neighboring node. The maximum size of Node.HOP2Table is left to the implementation. (For planning purposes, a full-mesh of N Nodes will require (N-1)! entries.) Each entry in the HOP2 Table describes a two hop route to another node. Entries SHALL be created or updated when a TU1 message is received. If a HOP2 entry with .Nexthop=TU1.Sender and .HOP2Node=TU1.Neighbor[].Nodeid does not exist, a new entry SHALL be created with those values. If entry does exist, it SHALL be updated. A HOP2 Table entry SHALL be deleted if the .Nexthop does not have a confirmed entry in the Node.HOP1[] table. Each HOP2 Entry SHALL consist of at least the following information. Additional information MAY be maintained by the implementation. .HOP2Node: AHDR Nodeid from TU1.Neighbor of a received TU1 Message. Value SHALL NOT be Node.Nodeid. The combination of .HOP2Node and .Nexthop SHALL NOT be repeated in Node.HOP2Table. .Nexthop: TU1.Sender from TU1 Message that created this entry. Value must not be Node.Nodeid. No entry SHALL exist if there is no confirmed entry in Node.HOP1[] for the .Nexthop. .HOP2LSL: TU1.LSLTable[HOP2Node].To value from most recent TU1 message from .Nexthop node. o SOURCE: Configuration o USES: Route resolution 6.4. HOPK Table (Node.HOPK[]) [REQUIRED] Each Node SHALL maintain a HOPK Table which contains information (learned from TUD Messages) about AHDR Nodes that can be reached in 3 or more hops in the AHDR Network. The HOPK Table is a table of HOPK Entries. The number of entries is left to the implementation as the entries are not exchanged. Each HOPK Entry describes a route of 3 or more hops to another node. Entries SHALL be created or updated when a TUD message is received. If a HOPK entry with .Nexthop=TUD.Sender and .HOPKNode=TUD.Domain[].Nodeid does not exist (and the number of calculated hops to the .HOPKNode is 3 or more), a new entry SHALL be created with those values. If entry does exist, it SHALL be updated. A HOPK Table entry SHALL be deleted if it has .Nexthop=TU1.Sender of a received TUD message and the TUD.Full value is 1, but the TUD does not have the HOPK entry's .HOPKNode in its TUD.Domain[] table. A Ghanadan, et al. Expires September 2010 [Page 20] Internet-Draft AHDR March 2010 HOPK Table entry SHALL be deleted if there is no Node.HOP1[] table entry for the entry's .Nexthop node. A HOPK Table entry SHALL be deleted if there is no Node.HOP1[] table entry for the entry's .Nexthop node. A HOPK Table entry SHALL be deleted if its .Timer expires. Each HOPK Entry SHALL consist of at least the following information. Additional information MAY be maintained by the implementation. .HOPKNode: TUD.Domain[].Nodeid that is calculated to be 3 or more network hops away from Node. Value SHALL NOT be Node.Nodeid. .Nexthop: TUD.Sender value from TUD Message that created this table entry. Value SHALL NOT be Node.Nodeid. No entry SHALL exist if Node.HOP1[.Nexthop].Confirmed value is 0. .Source: TUD.Source from TUD message that created this entry. Value SHALL NOT be Node.Nodeid. .LSL: LSL value from .Nexthop to .HOPKNode. Value calculated from information received in the TUD message. Value SHALL fit into TUD.Domain[].LSLTotal field. .Hops: Number of hops from Node to .HOPKNode. Value SHALL fit into TUD.Hops field. .Domain Lead: Domain Lead of .HOPKNode from TUD.Source. .Timer: Use to determine if entry should be removed. .Interval is Calculated as (Node.HOP1[.NextHop].Timeout * Node.Timeout.HOPK * 2). .Timer is RESET each time the HOPK entry is reconfirmed by a received TUD message. If .Timer expires, this HOPK Entry SHALL be deleted. o SOURCE: Received TUD messages o USES: Route resolution 6.5. Bridge Table (NODE.Bridge[]) [REQUIRED] The Bridge Table is a table of AHDR Nodes that allows messages to be forwarded to known Domains that lie within 2-hops of this node. Different algorithms to calculate Bridge Nodes will result in different Network performance. It is suggested that a minimum set of Bridge Nodes be calculated in mediums where broadcast messages cause excessive interference with network traffic. A Bridge Table is optional if a node elects to select Bridge Nodes based on information contained in the message to be forwarded. For instance, the Domain Lead Tracks contain information about domains Ghanadan, et al. Expires September 2010 [Page 21] Internet-Draft AHDR March 2010 already visited by the message. If those domains are eliminated from the Bridge Node calculation, a smaller set of Bridge Nodes may be found. The designation as a Bridge Node does not affect Node operation except when forwarding AHDR messages. o SOURCE: HOP1 and HOP2 Tables, Domain Coverage Table o USES: Forwarding TUD, RDISC, and IPAD messages 6.6. Domain Lead Table (Node.DomainLead[]) [REQUIRED] The Domain Lead Table SHALL contain at least one entry for the primary Domain Lead. If multiple Domain Leads that are within 1 hop of this Node, an implementation may add more entries. The additional entries are backup Domain Leads that SHALL only be used if the Node loses contact with the primary Domain Lead. The size of this table SHALL be limited to a value that fits in the TU1.DLs field. Information from additional Domain Leads may be stored in the Node.DomainCoverage[] table. An entry SHALL be created in the Domain Lead table if a DLA is received and the DLA.Sender does not have an entry in the table. If an entry does exist already, it SHALL be updated. The .Coverage field of an entry, E, SHALL be updated with the TU1.Coverage value when TU1.Sender equals E.Nodeid in a received TU1. A Domain Lead entry, E, SHALL be deleted from the table if a DLR is received where DLR.Sender equals Node.DomainLead[E].Nodeid. An entry, E, SHALL also be deleted if the Node.HOP1[E.Nodeid] entry is deleted or if Node.HOP1[E.Nodeid].Confirmed becomes 0. Each Entry SHALL consist of at least the following fields. Additional information MAY be maintained by the implementation. .Nodeid: A Domain Lead Node within 1 hop of this Node. Value SHALL NOT be repeated within the Domain Lead Table. Value must be a Nodeid from a Confirmed HOP1 Entry. No entry SHALL exist if Node.HOP1[.Nexthop].Confirmed value is 0. Domain Lead Coverage: The DLA.Coverage, DLR.Coverage or TU1.Coverage value for .Nodeid, whichever was received most recently. Value SHALL fit into TU1.Coverage field of an AHDR TU1 Message. SOURCE: Received in TU1, DLA, and DLR messages USES: Sent in TU1, TUD, DLA, and DLR messages Ghanadan, et al. Expires September 2010 [Page 22] Internet-Draft AHDR March 2010 6.7. Domain Coverage Table (Node.DomainCoverage[]) [REQUIRED] The Domain Coverage Table is a table of known Domains within 2 hops of a given node and the coverage of those Domains by the Node and by each of the Node's 1-hop neighbors. The known Domains SHALL be collected from the Node.HOP1[].DomainLead fields and from received TU1.LeadCoverage[] and TU1.DomainCoverage[] tables. The Domain Coverage Table SHALL consist of Domain Coverage Entries. The size of this table SHALL be limited to a value that fits in the TU1.DCs field. Each Domain Coverage entry SHALL consist of at least the following fields. Additional information MAY be maintained by the implementation. .CoveredNode: Nodeid of Domain Lead of known Domain. .Cover[] Table: A table of which Nodeids cover the CoveredNode and their coverage values. The Cover Table SHALL consist of Cover Table Entries. The size of this table SHALL be at least as large as the TU1.DCs field. Each Cover Table Entry SHALL consist of at least the following fields: .CoveringNode: Nodeid that covers the.CoveredNode (Domain Lead). .Coverage: Corresponding Domain Coverage value for .CoveringNode in the .CoveredNode Domain. Value depends on the number of Domain Nodes in the .CoveredNode's Domain that are 1-hop neighbors of .CoveringNode. SOURCE: Calculated from Node.HOP1[] table and read from TU1 messages USES: Sent in TU1 messages; Forming Bridge Table 6.8. IPAD Learned Address Table (Node.IPAD.Learned[]) [OPTIONAL] The IPAD Learned Address Table contains a list of routing addresses that this Node has learned from received IPAD messages. The values SHALL conform to the IPAD Address format. The number of addresses allowed is not specified here, but consideration should be given to the size and number of IPAD messages that will result from an excessive number of addresses. SOURCE: Received in IPAD messages USES: Sent in IPAD messages 7. AHDR Messages Ghanadan, et al. Expires September 2010 [Page 23] Internet-Draft AHDR March 2010 AHDR nodes communicate with each other using AHDR messages. Each AHDR message, M, SHALL consist of an AHDR message header (M.Header) followed by an optional AHDR message body (M.Body) followed by an optional AHDR message checksum (M.Checksum). All fields in AHDR messages SHALL be unsigned integer values unless otherwise noted. Valid values SHALL be any value that fits in the field unless otherwise noted. Any bits in an AHDR message marked "N/A" SHOULD be set to 0 upon transmit and SHALL be ignored upon receive. 7.1. AHDR Message Header This header (.Header) appears at the beginning of every AHDR message. The node sending the message, SenderNode, fills in all fields before sending the message. 7.1.1. Header Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Length(10) | .Type(6) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |.C |.Version(3)|.Con(2)| N/A | .Networkid(4) | .IDLength(4) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Sender | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Header.Length (10 bits): Length of AHDR message expressed in number of 16-bit words (i.e., 1/16th of the bit length). Length includes all message bytes. Legal values SHALL be 3 - 1023. This field limits the maximum length of a single AHDR message to (2 * (2^10 - 1)) or 2046 bytes. .Header.Type (6 bits): AHDR message type Value Type Full Name -------------------------------- 0 ---- Illegal value 1 TU0 Topology Update 0 (see Section 7.4) 2 TU1 Topology Update 1 (see Section 7.5) 3 TUD Topology Update Domain (see Section 7.6) 4 DLA Domain Lead Announcement (see Section 7.7) 5 DLR Domain Lead Renouncement (see Section 7.8) Ghanadan, et al. Expires September 2010 [Page 24] Internet-Draft AHDR March 2010 6 ---- Reserved 7 RDISC Route Discovery (see Section 7.9) 8 RRES Route resolution (see Section 7.10) 9 RERR Route Error (see Section 7.11) 10 ---- Reserved 11 ---- Reserved 12 ---- Reserved 13 ---- Reserved 14 ---- Reserved 15 ---- Reserved 16 IPAD IP Address Distribution (see Section 7.12) 17 ---- Reserved 18-31 ---- Reserved .Header.C (1 bit): SenderNode.Checksum. Value of 1 SHALL indicate presence of .Checksum field. Value of 0 SHALL indicate the field is not present. The .Checksum field, if present, SHALL appear as the last 16 bits of the AHDR messages (after the body of the message). .Header.Version (3 bits): AHDR version number for compatibility purposes. The version in this document is Version 0. .Header.Con (2 bits): SenderNode.LCI. .Header.Networkid(4 bits): SenderNode.Networkid. With the exception of IPAD messages, all AHDR Nodeids that appear in an AHDR message SHALL have the same Networkid as the sending node. .Header.IDLength (4 bits): SenderNode.IDLength. Length of all AHDR Nodeids in 2-byte WORDs (i.e., one-half of byte length or 1/16th of the bit length) minus one. Therefore, value of 0 indicates 16 bits and 1 indicates 32 bits up to 15 which indicates 256 bits. .Header.Sender (16 or more bits): SenderNode.Nodeid. The length in bits SHALL be 16 + (.Header.IDLength * 16). 7.2. AHDR Message Body The body (.Body) of an AHDR message SHALL appear directly following the .Header of the message. The number of bits in .Body SHALL be any value greater than or equal to 0. The number of bits in .Body SHALL be any value less than or equal to 16 * (1023 - (3 + Node.IDLength + Node.Checksum)). 7.3. AHDR Message Checksum The following 16-bit structure SHALL appear at the end of the AHDR message if, and only if, the .Header.C field equals 1. Ghanadan, et al. Expires September 2010 [Page 25] Internet-Draft AHDR March 2010 7.3.1. Checksum Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum(16) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Checksum (16 bits): A checksum value which SHALL be calculated by the Calculate Checksum Process before the message is sent. 7.4. TU0 -- Topology Update 0 Message A TU0 message announces an AHDR node to the network. A TU0 message is used when the Node.HOP1[] table is empty. Since the TU0 message does not contain any neighbor data (no HOP1 table) sending a TU0 breaks all confirmed links to and from the node. 7.4.1. TU0 Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=1) | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ See .Header and .Checksum specifications in Section 7.1 and 7.3 respectively. 7.5. TU1 -- Topology Update 1 Message A TU1 message announces an AHDR node and its HOP1 table and additional information. Other Nodes use the information from the received TU1 messages to form and maintain confirmed links to 1-hop neighbor nodes. 7.5.1. TU1 Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=2) | | . | | . | Ghanadan, et al. Expires September 2010 [Page 26] Internet-Draft AHDR March 2010 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Timeout(16) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | N/A | .Coverage(14) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .HOP1s(10) | .DCs(4) |.DLs(2)| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Neighbor[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .DomainCoverage[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .LeadCoverage[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ The SenderNode is the TU1.Header.Sender node. This will be the local Node during construction for transmit and some other Node during processing after receive. .Timeout: SenderNode.Timeout.Topology value in 1/10s of seconds; .Coverage: SenderNode.Coverage; .DLs(2): SenderNode.DomainLeads[].Count; .DCs(4): SenderNode.DomainCoverage[].Count - SenderNode.DomainLeads[].Count; .HOP1s(10): SenderNode.HOP1[].Count (if this value is 0, the TU0 message should be used instead of TU1); .Neighbor[]: Table built from SenderNode.HOP1[] entries. .DomainCoverage[]: Table built from SenderNode.DomainCoverage[] entries. .LeadCoverage[]: Table built from SenderNode.DomainLead[] entries. Bits marked "N/A" SHOULD be set to 0 upon transmit and SHALL be ignored upon receive. Ghanadan, et al. Expires September 2010 [Page 27] Internet-Draft AHDR March 2010 7.5.1.1 TU1.Neighbor[] Table This is a table of one or more entries. The entry count SHALL be given by TU1.HOP1s. Entries SHALL be formed as follows: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | N/A | .DI()| .ToLSL(4) | .FromLSL(4) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid: Neighbor's Nodeid from SenderNode.HOP1[].Nodeid. Size the same as TU1.Header.Sender. .DI: Index (plus 1) of .Nodeid's entry in the TU1.LeadCoverage[] table. If 0, .Nodeid has no entry in the table. A value greater than 0 indicates that the .Nodeid is a Domain Lead and that the (.DI - 1) value is the index into TU1.LeadCoverage[] for the .Nodeid coverage. Values SHALL range from 0 to TU1.DLs. Only value 0 may be repeated. .ToLSL: LSL cost from SenderNode.HOP1[.Nodeid].SendLSL. .FromLSL: LSL cost from SenderNode.HOP1[.Nodeid].ReceiveLSL. Bits marked "N/A" SHOULD be set to 0 upon transmit and SHALL be ignored upon receive. 7.5.1.2 TU1.DomainCoverage[] Table This table announces Domains that the SenderNode can reach within 2 network hops and the SenderNode's DomainCoverage value for those Domains. This information SHALL be used by the receiver to evaluate the Sender as a possible Bridge Node to the Domain. This table SHALL contain 1-15 entries. The entry count SHALL be given by TU1.DCs. When the TU1.DCs field is 0, the TU1.DomainCoverage[] table is not included. TU1.DomainCoverage[] entries SHALL be formed as follows: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | Ghanadan, et al. Expires September 2010 [Page 28] Internet-Draft AHDR March 2010 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |.Dst(2)| .Coverage(14) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid: Domain Lead from SenderNode.DomainCoverage[].CoveredNode. Size the same as TU1.Header.Sender. Field SHALL NOT contain any Nodeid that appears in the TU1.Neighbor[] table with a TU1.Neighbor[].DI value greater than 0. The Domain Coverage values for those Nodeids appear only in the TU1.LeadCoverage[] table. .Dst: Distance from SenderNode to .Nodeid (0=1 hop, 1=2 hops, 2=3+ hops, 3 reserved for later use) .Coverage: Value from SenderNode.DomainCoverage[].Coverage for the .Nodeid. 7.5.1.3 TU1.LeadCoverage[] Table This table announces the SenderNode's DomainCoverage for up to 3 Domain Leads within one hop of the SenderNode. The Nodeid for each entry SHALL be found in the TU1.Neighbor[] table where the .DI field is non-zero. When the TU1.DLs field is 0, the TU1.LeadCoverage[] table is not included. This table SHALL contain 1-3 entries. The entry count SHALL be given by TU1.DCs. Entries SHALL be formed thus: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | N/A | .Coverage(14) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Coverage: Value for covered Domain from SenderNode.DomainCoverage[].Coverage Bits marked "N/A" SHOULD be set to 0 upon transmit and SHALL be ignored upon receive. 7.6. TUD -- Topology Update Domain Message A TUD message announces an AHDR node as a Domain Lead. The message also advertises the Domain Nodes and additional information. 7.6.1. TUD Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=3) | Ghanadan, et al. Expires September 2010 [Page 29] Internet-Draft AHDR March 2010 | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Source | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Previous | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Hops(8) | .Sequence(8) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .LSLTotal(16) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .LT1(4) | .LT2(4) | .LT3(4) | .LT4(4) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | N/A |.F | .HOP1s(8) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .BNs(8) | .DLs(8) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Domain[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Bridge[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .DomainTrack[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .BNForwardRef[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ The SenderNode is the TUD.Header.Sender node. This will be the local Node during construction for transmit and some other Node during processing after receive. The "Exit Node" is a node one hop from the SenderNode that last forwards the TUD out of the SenderNode's Domain. Ghanadan, et al. Expires September 2010 [Page 30] Internet-Draft AHDR March 2010 .Source: Nodeid of original source of TUD. This field SHALL NOT be updated by any Node forwarding the TUD. .Previous: Nodeid of node previous to SenderNode. Set to 0 by SenderNode that creates the TUD. This field SHALL be updated by each Node that forwards the TUD. .Hops(8): Number of hops from SenderNode to Exit Node. This value SHALL be updated by each Node that forwards the TUD. .Sequence(8): TUD sequence number for identification. First value SHALL be 1, then each subsequent TUD SHALL increment the value. After the value 255 is used, the value 1 SHALL be used again. The value 0 SHALL never be used. This field SHALL NOT be updated by any Node forwarding the TUD. .LSLTotal(8): LSL from SenderNode to Exit Node. This value SHALL be updated by each Node that forwards the TUD. .LT1(4): Count of return links that have LSL values 0-3 (i.e., worst links). .LT2(4): Count of return links that have LSL values 4-7. .LT3(4): Count of return links that have LSL values 8-11. .LT4(4): Count of return links that have LSL values 12-15 (i.e., best links). These fields MAY be updated by each Node that forwards the TUD. .HOP1s(8): SenderNode.HOP1[].Count (the size of .Domain[] Table included in message). To reduce message sizes, TUD.Source Node MAY limit entries to those where SenderNode.HOP1[].DomainLead is SenderNode, but this may also reduce the number of available routes to each Node. This field SHALL NOT be updated by any Node forwarding the TUD. .BNs(8): Size of .Bridge[] Table included in message. This value is set by the "Bridge Selection Process". See Section 8.8. .DLs(8): Size of .DomainTrack[] Table included in message. This table is set by the "Domain Lead Tracking Process". See Section 8.9. .F(1): Value of 1 indicates a full TUD (all Domain Nodes included). Value of 0 indicates an update TUD (only Domains Nodes changed since previous TUD included) .Domain[]: if .F = 1, .Domain[] is built from all SenderNode.HOP1[] entries (or, optionally, only those entries whose .DomainLead value is SenderNode). If .F = 0, .Domain[] only include entries from SenderNode.HOP1[] that changed (i.e., added, modified, or removed) Ghanadan, et al. Expires September 2010 [Page 31] Internet-Draft AHDR March 2010 since the previous TUD message. This table MAY be updated by each Node that forwards the TUD. .Bridge[]: Table of Nodeids that have been selected to forward the TUD message. Filled from SenderNode.Bridge[]. This table is set by the "Bridge Selection Process". See Section 8.8. .DomainTrack[]: Table of Domains (identified by the Nodeid of the Domain Lead) this message has visited or has been directed to. This table is set by the "Domain Lead Tracking Process". See Section 8.9. .BNForwardRef[]: Table that indicates which .DomainTrack[] entries correspond to each .Bridge[] entry. This table MAY be updated by each Node that forwards the TUD. Bits marked "N/A" SHOULD be set to 0 upon transmit and SHALL be ignored upon receive. 7.6.2. TUD.Domain[] Table The number of entries in TUD.Domain[] SHALL be given by TUD.HOP1s. The entries SHALL be formed as follows: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Type | N/A | .Hops(4) | .LSL(4) | .OLSL(4) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid (16 or more bits): SenderNode.HOP1[].Nodeid where SenderNode.HOP1[].Confirmed is 1. .Type (2 bits): Entry type (0=OLD, 1=ADD, 2=DELETE, 3=REFRESH). OLD: Entry has not changed since the previous TUD ADD: Entry was added since the previous TUD DELETE: Entry was removed since the previous TUD REFRESH: Entry was modified since the previous TUD .Hops (4 bits): Hop count from .Nodeid to Exit Node. Only the Exit Node may use the value 0. .LSL (4 bits): If .Hops is 0, LSL from Exit Node to TUD.Source. If .Hops is 1, LSL from .Nodeid to Exit Node. If .Hops is > 1, LSL from TUD.Source to .Nodeid. Ghanadan, et al. Expires September 2010 [Page 32] Internet-Draft AHDR March 2010 .OLSL (4 bits): LSL from TUD.Source to .Nodeid Bits marked "N/A" SHOULD be set to 0 upon transmit and SHALL be ignored upon receive. 7.6.3. TUD.Bridge[] Table The .Bridge[] table SHALL consist of entries which indicate which Nodes may forward this TUD message. As the TUD message is forwarded throughout the network, TUD.Bridge[] SHALL be updated to prevent routing loops and limit retransmissions. The number of entries in the TUD.Bridge[] table SHALL be given by TUD.BNs. The Entries SHALL be formed as follows: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid (16 or more bits): .Nodeid that should forward this message. This table is set by the "Bridge Selection Process". See Section 8.8. 7.6.4. TUD.DomainTrack[]Table The TUD.DomainTrack[] SHALL consist of entries that show which Domains this message has already visited and which Domains it should visit next. As the TUD message is forwarded throughout the network, TUD.Domaintrack[] SHALL be updated to prevent routing loops and limit retransmissions. The number of table entries SHALL be given by TUD.DLs(8). TUD.DomainTrack[] SHALL be a list of Nodeids: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid (16+ bits): Nodeid of a Domain Lead. This table is set by the "Domain Lead Tracking Process". See Section 8.9. Ghanadan, et al. Expires September 2010 [Page 33] Internet-Draft AHDR March 2010 7.6.5. TUD.BNForwardRef[] Table The TUD.BNForwardRef[] table indicates which Domain Leads each Bridge Node should forward the TUD to. The TUD.BNForwardRef[] table SHALL consist of one entry for each node in the TUD.Bridge[] table. The number of table entries is therefore given by TUD.BNs(8). Each TUD.BNForwardRef[] entry shows which TUD.DomainTrack[] entry the Bridge Node is required to cover. Each entry lists only the indexes into the TUD.DomainTrack[] table to avoid repeating the Nodeids of the Domains. The format of an entry SHALL be as follows: 00 01 02 03 04 05 06 07 +---+---+---+---+---+---+---+---+ | .Count(8) | +---+---+---+---+---+---+---+---+ | .DLIndex[] | | . | +---+---+---+---+---+---+---+---+ .Count: Number of entries in following .DLIndex[] table associated with a given Bridge Node. The value SHALL NOT be 0. Any Bridge Node that does not cover a Domain SHALL NOT be included in the TUD.Bridge[] table. .DLIndex[]: Table of 0-up indexes into the .DomainTrack[] table. Each index SHALL be 8 bits long. The total size of the table in bits SHALL be (8 * .Count). Entries consist of 8-bit values (counts and indexes). Once one entry ends, the next one begins immediately with another .Count field in the next 8 bits. The length of the entire TUD.BNForwardRef[] table MUST be rounded up to a multiple of 16 bits. Any value MAY be used for padding. Any index that appears in a .BNForwardRef[].DLIndex[] table MUST NOT be repeated in a different .BNForwardRef[].DLIndex[] table in the same TUD. A Domain SHALL be covered by only one Bridge Node, but a Bridge node MAY cover more than one Domain. This eliminates messages from getting resent to Domains that the message has already propagated through. Each Bridge Node SHALL forward the TUD towards the Domain Lead(s) indicated in its TUD.BNForwardRef[] table entry. Because TUDs are broadcast, other Domain Leads might overhear and process TUDs that are not specifically intended for them. Those other Domain Leads may process those TUDs as specified in Section 7.6. Ghanadan, et al. Expires September 2010 [Page 34] Internet-Draft AHDR March 2010 Example: +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | TUD | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .BNs = 3 | .DLs = 5 | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Domain[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Bridge[3] | | 121 | | 66 | | 9 | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .DomainTrack[5] | | 116 | | 44 | | 87 | | 39 | | 5 | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .BNForwardRef[3] | | .BNForwardRef[0].Count=1 | .BNForwardRef[0].DLIndex[0]=4 | | .BNForwardRef[1].Count=2 | .BNForwardRef[1].DLIndex[0]=2 | | .BNForwardRef[1].DLIndex[1]=3 | .BNForwardRef[2].Count=1 | | .BNForwardRef[2].DLIndex[0]=0 | 0 (Padding) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .BNForwardRef[0].Count=1 : Bridge Node 121 (.Bridge[] index 0) forwards this TUD towards 1 Domain Lead. .BNForwardRef[0].DLIndex[0]=4 : Domain Lead to forward to is Node 5 (.DomainTrack[] index 4). This may require forwarding through another node if Node 4 is not a 1-hop neighbor. .BNForwardRef[1].Count=2 : Bridge Node 66 (.Bridge[] index 1) forwards this TUD towards 2 Domain Leads. .BNForwardRef[1].DLIndex[0]=2 : Domain Lead to forward to is Node 87 (.DomainTrack[] index 2). .BNForwardRef[1].DLIndex[1]=3 : Domain Lead to forward to is Node 39 (.DomainTrack[] index 3). Ghanadan, et al. Expires September 2010 [Page 35] Internet-Draft AHDR March 2010 .BNForwardRef[2].Count=1 : Bridge Node 9 (.Bridge[] index 1) forwards this TUD towards 1 Domain Lead. .BNForwardRef[2].DLIndex[0]=0 : Domain Lead to forward to is Node 116 (.DomainTrack[] index 2). No Bridge Node forwards this TUD to Domain Lead 44 because no .DLIndex[] in any entry contained the index 1. 7.7. DLA -- Domain Lead Announcement Message A DLA message is sent by a node to declare its intention to serve as the Domain Lead. 7.7.1. DLA Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=4) | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | N/A | .Coverage(14) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ The SenderNode is the DLA.Header.Sender node. This will be the local Node during construction for transmit and some other Node during processing after receive. .Coverage (14 bits): Value from SenderNode.Coverage. Bits marked "N/A" SHOULD be set to 0 upon transmit and SHALL be ignored upon receive. 7.8. DLR -- Domain Lead Renouncement Message A DLR is sent by a node to announce its intention to relinquish the Domain Lead role. 7.8.1. DLR Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=5) | Ghanadan, et al. Expires September 2010 [Page 36] Internet-Draft AHDR March 2010 | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | N/A | .Coverage(14) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .NewLead | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | N/A | .NewCoverage(14) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ The SenderNode is the DLR.Header.Sender node. This will be the local Node during construction for transmit and some other Node during processing after receive. .Coverage (14 bits): SenderNode.Coverage .NewLead (16 or more bits): SenderNode.HOP1[].Nodeid with highest SenderNode.HOP1[].Coverage value in table. .NewCoverage (14 bits): SenderNode.HOP1[.NewLead].Coverage value. Bits marked "N/A" SHOULD be set to 0 upon transmit and SHALL be ignored upon receive. 7.9. RDISC -- Route Discovery Message RDISC is sent by a source Node to discover a route to a destination Node. 7.9.1. RDISC Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=7) | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Source | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Sequence(8) |DNR| .Hopcount(7) | Ghanadan, et al. Expires September 2010 [Page 37] Internet-Draft AHDR March 2010 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Destination | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .BNs(8) | .DLs(8) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Bridge | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .DomainTrack[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .BNForwardRef[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ The SenderNode is the RDISC.Header.Sender node. This will be the local Node during construction for transmit and some other Node during processing after receive. .Source (16+ bits): Nodeid of original source of RDISC message .Sequence (8 bits): RDISC sequence number for identification. The value 0 indicates a local RDISC that MUST not be forwarded by any node that receives it. For non-local RDISCs, the first value used SHALL be 1 and each subsequent non-local RDISC SHALL increment the value by 1. After the value 255 is used, the sequence SHALL start over using the value 1. The .Sequence value MUST NOT be modified by any Node forwarding the RDISC message. .DNR (1 bit): Do Not Reply. If set to 1, receiver SHALL NOT reply to the RDISC. If 0, the receiver MUST reply. An RDISC with .DNR set will continue on to the .Destination Node. This will ensure that a return path from .Destination to .Source will exist. .Hopcount (7 bits): Accumulated hop count as RDISC is forwarded through the network. .Hopcount is set to 0 by the RDISC source node. Each node that forwards the RDISC SHALL add 1 to the field. If the field reaches its maximum value, the maximum value shall be retained for the rest of the life of the message. Ghanadan, et al. Expires September 2010 [Page 38] Internet-Draft AHDR March 2010 .Destination (16+ bits): The Nodeid that the .Source node is trying to locate. .Bridge[]: Table of Nodeids that have been selected to forward the RDISC message. . .DomainTrack[]: Table of Domains this message has visited. .BNForwardRef[]: Table that indicates which .DomainTrack[] entries correspond to each .Bridge[] entry. 7.9.2. RDISC.Bridge[] The number of entries in the RDISC.Bridge[] table SHALL be given by RDISC.BNs(8). The Entries SHALL be formed as follows: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid (16 or more bits): .Nodeid that should forward this message. At the Domain Lead Node originating the RDISC message, the .Bridge[] table SHALL be filled with the entries from the Node.Bridge[] table. The RDISC.BNs is set to the number of identifiers or entries in Node.Bridge[] table. At the Bridge Node(s) selected to forward the RDISC message, the .Bridge[] table of the RDISC message to be forwarded is filled with Node.Bridge[] entries one for each NEW Domain Lead entry that was appended to the TUD.DomainTrack[] table; See Section 8.8 "Bridge Selection Process" for details on the process to select the Bridge Node(s) to forward the RDISC message. 7.9.3. RDISC.DomainTrack[] Table The RDISC.DomainTrack[] consists of entries that keep track of which domains this message has already visited and which domains it should visit next. The number of table entries for both tables SHALL be given by RDISC.DLs(8). RDISC.DomainTrack[] SHALL be a list of Nodeids: Ghanadan, et al. Expires September 2010 [Page 39] Internet-Draft AHDR March 2010 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid (16+ bits): Nodeid of a Domain Lead 7.9.4. RDISC.BNForwardRef[] Table The RDISC.BNForwardRef[] table shows which Domain Leads each Bridge Node should forward the RDISC to. The RDISC.BNForwardRef[] table SHALL consist of one entry for each node in the RDISC.Bridge[] table. The number of table entries SHALL be given by RDISC.BNs(8). Each RDISC.BNForwardRef[] entry SHALL show which RDISC.DomainTrack[] entry the Bridge Node is required to cover. Each entry SHALL list only the indexes into the RDISC.DomainTrack[] table to avoid repeating the Nodeids of the Domains. The format of an entry SHALL be as follows: 00 01 02 03 04 05 06 07 +---+---+---+---+---+---+---+---+ | .Count(8) | +---+---+---+---+---+---+---+---+ | .DLIndex[] | | . | +---+---+---+---+---+---+---+---+ .Count: Number of entries in following .DLIndex[] table. The value SHALL NOT be 0. Any Bridge Node that does not cover a Domain SHALL NOT be included in the RDISC.Bridge[] table. .DLIndex[]: Table of 0-up indexes into the .DomainTrack[] table. Each index SHALL be 8 bits long. The total size of the table in bits SHALL be (8 * .Count). Entries consist of 8-bit values (counts and indexes). Once one entry ends, the next one begins immediately with another .Count field in the next 8 bits. The length of the entire RDISC.BNForwardRef[] table MUST be rounded up to a multiple of 16 bits. Any value MAY be used for padding. Any index that appears in a .BNForwardRef[].DLIndex[] table MUST NOT be repeated in a different .BNForwardRef[].DLIndex[] table in the same RDISC. Only one Bridge Node covers a Domain. Ghanadan, et al. Expires September 2010 [Page 40] Internet-Draft AHDR March 2010 Each Bridge Node SHALL forward the RDISC towards the Domain Leads indicated in its RDISC.BNForwardRef[] table entry. Because RDISCs are broadcast, other Domain Leads might overhear and process RDISCs that are not specifically intended for them. Those other Domain Leads may process those RDISCs as specified in Section 7.9. 7.10. RRES -- Route resolution Message RRES is sent by any Node with a route to the destination node i.e., the node has the destination address in its HOP1, and/or HOP2, or HOPK tables. 7.10.1. RRES Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=8) | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Source | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Sequence(8) | .Hopcount(8) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Destination | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .PrevLSL(4) | .DestLSL(12) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Previous | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ The SenderNode is the RRES.Header.Sender node. This will be the local Node during construction for transmit and some other Node during processing after receive. .Source (16+ bits): Nodeid of original source of RDISC message that RRES is replying to. Ghanadan, et al. Expires September 2010 [Page 41] Internet-Draft AHDR March 2010 .Sequence (8 bits): RDISC sequence number from RDISC message that RRES is replying to. The .Sequence value MUST NOT be modified by the nodes forwarding the RDISC message. .Hopcount (8 bits): Hop count from RRES.Source to RRES.Destination. Accumulated hop count as RDISC is forwarded through the network. .Hopcount is set to 0 by the RRES source node. Each node that forwards the RRES SHALL add 1 to the field. If the field reaches its maximum value, the maximum value shall be retained for the rest of the life of the message. .Destination (16+ bits): = RDISC.Destination. .PrevLSL (4 bits): LSL to send from RRES.Sender to RRES.Previous node. .DestLSL (12 bits): LSL to send from RRES.Previous to RRES.Destination. .Previous (16+ bits): Nodeid that forwarded the RRES to RRES.Sender. Field SHALL be set to 0 by the node which creates the RRES. 7.11. RERR -- Route Error Message The RERR message is sent to notify the RDISC originating node that a route to the destination cannot be found. The RERR message is sent by all Bridge Nodes that received the corresponding RDISC but were not able to resolve a route to the destination node and could not forward the RDISC any further. The RERR message is also sent by Domain Lead Node(s) that received the RDISC and had their RDISC timers expire without a route resolution. 7.11.1. RERR Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=9) | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Source | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ Ghanadan, et al. Expires September 2010 [Page 42] Internet-Draft AHDR March 2010 | N/A | .Sequence(8) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Destination | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ The SenderNode is the RERR.Header.Sender node. This will be the local Node during construction for transmit and some other Node during processing after receive. .Source (16+ bits): Nodeid of original source of RDISC message that RRES is replying to. .Sequence (8 bits): RDISC sequence number from RDISC message that RRES is replying to. The .Sequence value MUST NOT be modified by the nodes forwarding the RDISC message. .Destination (16+ bits): The Nodeid that the RRES message located. 7.12. IPAD -- IP Address ReDistribution Message The IPAD message is sent to advertise the network addresses which the originating Node has a route to. 7.12.1. IPAD Fields 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Header (.Type=16) | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Source | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Previous | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Count(8) | .Sequence(8) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .BNs(8) | .DLs(8) | Ghanadan, et al. Expires September 2010 [Page 43] Internet-Draft AHDR March 2010 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Address[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Bridge[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .DomainTrack[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .BNForwardRef[] | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Checksum (if .Header.C=1) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ The SenderNode is the IPAD.Header.Sender node. This will be the local Node during construction for transmit and some other Node during processing after receive. .Source (16+ bits): Nodeid of original source of IPAD message .Previous: Nodeid of node previous to sender that forwarded this IPAD. Value set to 0 by creator of RERR message. .Count (8 bits): Size of .Address table included in message. .Sequence (8 bits): IPAD sequence number for identification. .BNs (8 bits): Size of .Bridge table included in message. .DLs (8 bits): Size of .DomainTrack table included in message. .Address[]: Table of network addresses that are available via the IPAD.Source node. See details below. .Bridge[]: Table of Nodeids that have been selected to forward the TUD message. If Node.Nodeid is not in TUD.Bridge[], then the receiving node SHALL NOT forward the TUD message. .DomainTrack[]: Table of Domains this message has visited. .BNForwardRef[]: Table that indicates which .DomainTrack[] entries go with each .Bridge[] entry. Ghanadan, et al. Expires September 2010 [Page 44] Internet-Draft AHDR March 2010 7.12.2. IPAD.Address[] The IPAD.Address[] table SHALL be a list of network addresses that comes from the Node.IPAD.Advertised[] table. The table size SHALL be given by IPAD.Count. The entries SHALL be formed as follows: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Type(4) | .Action(4) | .NetworkID(4) | .IDLength(4) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Source | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Metric(16) | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Address | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Mask | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Type (4 bits): Type of address in .Address and .Mask fields. Value 0 SHALL mean none, used to indicate empty entries in tables. Value 2 SHALL mean IPv4 (32 bits). Value 3 SHALL mean IPv6 (128 bits). All remaining values SHALL be reserved for other types. .Action (4 bits): Action. Values SHALL be 0 for no action, 1 for add, 2 for delete, 3 for modify. For values 0, 1 or 3, the receiver SHOULD add a new entry if no entry exists. For value 2, the receiver SHOULD delete the entry if the entry exists. For value 3, the receiver SHOULD update the entry if the entry exists. .Networkid (4 bits): AHDR Networkid for both IPAD.Source and IPAD.Address field. .IDLength (4 bits): Length of .Source in 2-byte WORDs (i.e., one- half of byte length or 1/16th of the bit length) minus one. .Source (16+ bits): The initial source of the address being advertised. This will help prevent advertising loops. Ghanadan, et al. Expires September 2010 [Page 45] Internet-Draft AHDR March 2010 .Metric (16 bits): Routing metric. .Address (16+ bits): Address being advertised. .Mask (16+ bits): Mask for address being advertised. 7.12.3. IPAD.Bridge[] The number of entries in the IPAD.Bridge[] table SHALL be given by IPAD.BNs(8). The Entries SHALL be formed as follows: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid (16 or more bits): .Nodeid that should forward this message. At the Domain Lead Node originating the IPAD message, the .Bridge[] table SHALL be filled with the entries from the Node.Bridge[] table. The IPAD.BNs is set to the number of identifiers or entries in Node.Bridge[] table. At the Bridge Node(s) selected to forward the IPAD message, the .Bridge[] table of the RDISC message to be forwarded is filled with Node.Bridge[] entries one for each NEW Domain Lead entry that was appended to the IPAD.DomainTrack[] table; See Section 8.8 "Bridge Selection Process" for details on the process to select the Bridge Node(s) to forward the RDISC message. 7.12.4. IPAD.DomainTrack[] Table The IPAD.DomainTrack[] consist of entries that keep track of which domains this message has already visited and which domains it should visit next. The number of table entries for both tables SHALL be given by IPAD.DLs(8). IPAD.DomainTrack[] SHALL be a list of Nodeids: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | .Nodeid | | . | | . | Ghanadan, et al. Expires September 2010 [Page 46] Internet-Draft AHDR March 2010 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ .Nodeid (16+ bits): Nodeid of a Domain Lead The sending node SHALL use the specifications found in Section 8.9 "Domain Lead Tracking Process" to construct this table. The .DLs field is set to the number of derived Domain Lead identifiers. 7.12.5. IPAD.BNForwardRef[] Table The IPAD.BNForwardRef[] table shows which Domain Leads each Bridge Node should forward the IPAD to. The IPAD.BNForwardRef[] table SHALL consist of one entry for each node in the IPAD.Bridge[] table. The number of table entries SHALL be given by IPAD.BNs(8). Each IPAD.BNForwardRef[] entry SHALL show which IPAD.DomainTrack[] entry the Bridge Node is required to cover. Each entry SHALL list only the indexes into the IPAD.DomainTrack[] table to avoid repeating the Nodeids of the Domains. The format of an entry SHALL be as follows: 00 01 02 03 04 05 06 07 +---+---+---+---+---+---+---+---+ | .Count(8) | +---+---+---+---+---+---+---+---+ | .DLIndex[] | | . | +---+---+---+---+---+---+---+---+ .Count: Number of entries in following .DLIndex[] table. The value SHALL NOT be 0. Any Bridge Node that does not cover a Domain SHALL NOT be included in the IPAD.Bridge[] table. .DLIndex[]: Table of 0-up indexes into the .DomainTrack[] table. Each index SHALL be 8 bits long. The total size of the table in bits SHALL be (8 * .Count). Entries consist of 8-bit values (counts and indexes). Once one entry ends, the next one begins immediately with another .Count field in the next 8 bits. The length of the entire IPAD.BNForwardRef[] table MUST be rounded up to a multiple of 16 bits. Any value MAY be used for padding. Any index that appears in a .BNForwardRef[].DLIndex[] table MUST NOT be repeated in a different .BNForwardRef[].DLIndex[] table in the same IPAD. Only one Bridge Node covers a Domain. Ghanadan, et al. Expires September 2010 [Page 47] Internet-Draft AHDR March 2010 Each Bridge Node SHALL forward the IPAD towards the Domain Leads indicated in its IPAD.BNForwardRef[] table entry. Because IPADs are broadcast, other Domain Leads might overhear and process IPADs that are not specifically intended for them. Those other Domain Leads may process those IPADs as specified in Section 7.12. 8. AHDR Processes This section specifies the required AHDR processes and algorithms. The description of a process consists of the following: o TRIGGER - a set of occurrences which cause the process to execute. o INPUT - information the process needs. All of the Node Data Structures and Node Network Information are implied in every INPUT set. o RESULT - a list of possible results. A calling process may use the result of a process it calls to determine its next action. This field is omitted when the process has no result. o ACTIONs - a list of actions that the process SHALL perform in order. All actions are requirements unless otherwise noted. A Process can perform the following actions which each have a specific meaning as explained: o Stop Process - When this action is indicated, the Node SHALL end the current Process and set the Result of the Process as shown. The Node SHALL not execute any other actions in the Process. o Execute - When this action is indicated, the Node SHALL suspend execution of the current Process (the "old" Process) and begin execution of another Process indicated by the execute action (the "new" Process). When the new Process stops, execution of the old Process SHALL resume just after the execute action in the old Process. Executions can be nested several layers deep. o Goto - Jump from one Step in a Process directly to another Step in the same Process without executing any intervening Steps. 8.1. Main Process Ghanadan, et al. Expires September 2010 [Page 48] Internet-Draft AHDR March 2010 The Main Process is AHDR's initial Process. It is executed once the Node is ready for use. It exists to respond to events that affect Node operation. The Main Process will never stop unless the AHDR Node is shut down. TRIGGER: o AHDR Node initialization. INPUT: o None. ACTIONS: 1) Execute "Send TU0 Message Process" and set Node.Timer to the TU0 interval. 2) If an AHDR message, M, has been received from the network, then execute "Message Receive Process" using M as an input parameter. 3) If a Node.HOP1[].Timer has expired, then set that entry's Node.HOP1[].Confirmed to 0 and execute "Link Lost Process". 4) If a Node.HOPK[].Timer has expired, then delete that HOPK entry. 5) If Node.Timer has expired, then reset Node.Timer and check the following conditions: a. If Node.HOP1[].Count is 0, then execute "TU0 Send Process, reset Node.Timer to TU0 interval, and Goto Step 2. b. If Node is a Domain Lead, then execute "TUD Send Process"; Reset Node.Timer to the Node.Timeout.Topology interval; If Result from the "Send TUD Message Process" is Message Sent, then Goto Step 2. c. execute "TU1 Send Process"; Reset Node.Timer to the Node.Timeout.Topology interval; If Result from the "TU1 Send Process" is Message Sent then Goto Step 2. d. If IPAD is enabled, then execute "IPAD Send Process". 6) Goto Step 2 8.2. Message Receive Process This process specifies common procedure applicable to all received AHDR messages. TRIGGER: o Message is received from network (Main Process). INPUT: Ghanadan, et al. Expires September 2010 [Page 49] Internet-Draft AHDR March 2010 o M - Message received. ACTIONS: 1) If M.Header.C is 1, the Node MAY execute the "Check Checksum Process" on message M. If the Result is Fail, the Node MAY discard the message AND stop Process. 2) If M.Header.Length is less than (3 + M.Header.C + M.Header.IDLength), then discard the message AND Stop Process. 3) If any of the following are true, then discard the message and Stop Process: a. M.Header.Version is not 0. b. M.Header.Networkid does not match Node.Networkid c. M.Header.IDLength does not match Node.IDLength d. M.Header.Sender is 0 or M.Header.Sender matches Node.Nodeid e. M.Header.Type is a Reserved value 4) Search Node.HOP1[] for an entry, E, where .Nodeid matches M.Header.Sender. If a matching entry E is not found, then create E as a new unconfirmed HOP1 Table entry (with .Nodeid = M.Header.Sender and .Confirmed = 0 and .Timeout = Node.Timeout.Topology * Node.Timeout.Link *2) If a matching entry E is found, Save E.SendLSL and E.Confirmed value (to determine if need to recalculate the Domain Lead role in step 6)). Use M.Header.Con to update E.SendLSL value. Use available physical layer receive statistics (e.g., RSSI) for M to update E.ReceiveLSL value. 5) Execute "Maintain Link Process". 6) If there are any confirmed entries in Node.HOP1[] and E.SendLSL or E.Confirmed value changed from saved values, then execute "Calculate Domain Lead Process". 7) If E.Confirmed is 0, then discard the message and Stop Process. 8) Execute the specific Receive Process for the M.Header.Type. 8.3. Maintain Link Process Ghanadan, et al. Expires - September 2010 [Page 50] Internet-Draft AHDR March 2010 This process specifies the link maintenance and update for the Node.HOP1[] entries. TRIGGER: o TU0 message received (from "Message Receive Process"). o TU1 message received (from "Message Receive Process"). o TUD message received (from "Message Receive Process"). INPUT: o M - Received message (TU0, TU1, or TUD). o E - Node.HOP1[] entry for M.Header.Sender. ACTIONS: little 1) If M.Header.Type is TU0, then set E.Confirmed to 0. 2) If M.Header.Type is TU1, then check TU1.Neighbor[]'s table for entry where .Nodeid matches Node.Nodeid. If entry is found, then set E.Confirmed to 1, update E using information from found entry, and set E.Timeout to (TU1.Timeout * Node.Timeout.Link * 2). If no entry is found, then set E.Confirmed to 0. 3) If M.Header.Type is TUD and TUD.Sender matches TUD.Source, then check TUD.Domain[] table for entry where .Nodeid is Node.Nodeid. If entry is found, then set E.Confirmed to 1, update E using information from the found entry. If no entry is found, then set E.Confirmed to 0. 4) If E.Confirmed value has changed from 1 to 0, execute "Link Lost Process". 8.4. Link Lost Process This process specifies the procedures to update various data structures when a Confirmed link is lost. TRIGGER: o Node.HOP1[].Timer expires (from the "Main Process"). o Node.HOP1[].Confirmed changes from 1 to 0 (from the "Maintain Link Process"). INPUT: o E - Node.HOP1[] entry. o LinkNode - Node.HOP1[].Nodeid value of unconfirmed link. ACTIONS: 1) Calculate Node.Coverage and Node.DomainCoverage[]. Ghanadan, et al. Expires September 2010 [Page 51] Internet-Draft AHDR March 2010 2) Remove all Node.HOPK[] entries where .Nexthop is LinkNode. 3) Remove all Node.HOP2[] entries where .Nexthop is LinkNode. 4) Remove all Node.IPAD.Learned[] entries where .Source is LinkNode. 5) If any Node.DomainLead[] entry where .Nodeid is LinkNode, then remove entry, pack remaining entries, and reduce Node.DomainLead[].Count by 1. 6) If E.Timer expired, remove entry E from Node.HOP1[] table. 7) If Node.HOP1[].Count > 0, then execute Calculate Domain Lead Process. If Node.HOP1[].Count is 0, then execute Send TU0 Message Process and reset Node.Timer to desired TU0 timeout value. 8.5. Message Send Process This process specifies the procedure for setting the M.Header and M.Checksum fields of the message to be transmitted. TRIGGER: o All AHDR messages to be transmitted . INPUT: o M -- Message with M.Header.Type and M.Body filled in. o LEN -- Length of M.Body in bits. ACTIONS: 1) Set WLEN = ((LEN+15)/16) where the quotient is truncated to an integer value. If the value (3 + WLEN + Node.Checksum + node.IDLength) is too large to fit in the M.Header.Length field, discard M and Stop Process. 2) If LEN and (WLEN*16) not equal, pad M.Body by adding ((WLEN*16) - LEN) bits of any value. 3) Set the M.Header fields other than M.Header.Type. 4) If Node.Checksum is 1, Execute Create Checksum Process on message M to set the M.Checksum field. 5) Send M on the AHDR network. 8.6. Calculate Domain Lead Process Ghanadan, et al. Expires September 2010 [Page 52] Internet-Draft AHDR March 2010 This process specifies the procedure to determine if a Node should take on the Domain Lead role and provide an example algorithm for calculating Domain Lead role metric. TRIGGER: o Each time the Node.Coverage changes, or .Coverage value from another node changes (as detected via a received TU1), or Node.HOP1[].ReceiveLSL changes, or any time a Node.HOP1[] entry is added or removed (from "Maintain Link Process", "Link Lost Process", and "Message Receive Process"). ACTIONS: 1) Calculate Node.Coverage and Node.DomainCoverage[]. 2) Find HIGHEST, the Node.HOP1[] entry with the highest .Coverage value. Here is an example .Coverage calculation: .Coverage = WDL * { W0 + N1(LINK+LSL) + N2(LINK+LSL) + ... + Nn(LINK+LSL) } Where: WDL (Weighted Domain Lead) is set to 1.0 for non-Domain Leads and >1.0 for Domain Leads W0 is some constant based on node's innate suitability to be a Domain Lead Nx(LINK+LSL) is the total weight assigned for 1-hop neighbors 1-n where: LINK is some constant added for the existence of a link (quantity) LSL is some value derived link state level (LCI + LQI) Nx is some weight given to each neighbor node where o low mobility nodes have a higher N-weight than relatively mobile nodes o higher stability (in terms of topology change, link variations, etc.) correlates to a higher N-weight 3) If Node is Domain Lead and HIGHEST.Coverage is greater than Node.Coverage, then a. Remove Node.DomainLead[0] entry. Ghanadan, et al. Expires September 2010 [Page 53] Internet-Draft AHDR March 2010 b. Update Node.DomainLead[] entry where .Nodeid is highest .Nodeid or insert new Node.DomainLead[] entry setting .Nodeid and .Coverage to highest values. Sort Node.DomainLead[] by descending .Coverage value. c. Send a DLR message and Stop Process 4) If Node is NOT Domain Lead and HIGHEST.Coverage is less than Node.Coverage, then a. Shift all Node.DomainLead[] entries by one entry position. b. Set Node.DomainLead[0].Nodeid to Node.Nodeid and Node.DomainLead[0].Coverage to Node.Coverage. c. Send a DLA message and Stop Process. 8.7. Route Discovery Process This process specifies the procedure to reactively discover a route from a source node to a destination node when the destination address can not be found in the source node's routing tables (HOP1, HOP2, and HOPK) TRIGGER: o As requested by the router forwarding engine. RESULT: o Next hop Nodeid that toward the DESTNODE. o Not Found. ACTIONS: 1) Search the Node.HOP1[], Node.HOP2[], and Node.HOPK[] tables for the "best" entry for DESTNODE. The definition of "best" is implementation specific. 2) If an entry, E, is found, then Result is E.Nexthop (which is DESTNODE itself if the entry is from the HOP1 Table) and Stop Process. 3) If no entry is found, execute "RDISC Send Process" with DESTNODE for Local lookup. 4) If an RRES message is received within 1 second, then Result is RRES.Nexthop and Stop Process. Ghanadan, et al. Expires September 2010 [Page 54] Internet-Draft AHDR March 2010 5) If an RERR message is received or if no RRES message is received within 1 second, then execute "RDISC Send Process" with DESTNODE for Distant lookup. 6) If a RRES message is received within 3 second, then Result is RRES.Nexthop and Stop Process. 7) Result is Not Found. 8.8. Bridge Selection Process This process specifies the algorithms to determine a set of the Bridge Nodes for a given set of Domains that need to be reached. The derived Bridge Node listing (i.e., Node.Bridge[]) will be used to fill in the M.Bridge[] field where M is the TUD, the RDISC, and the IPAD messages. TRIGGER: Each time there is a change in the Node.Hop1[] table which may impact the Node.Bridge[] table. INPUT: o Needed - Set of Domain Lead Nodeids that need to be reached. RESULT: o Node.Bridge[] updated. ACTIONS: 1) Calculate Node.DomainCoverage[].Cover[].Coverage for each known Node.DomainCoverage[].CoveredNode Domain Lead. Store values in Node.DomainCoverage[] table. Following is an example algorithm the Node uses for each known Domain Lead, D: DomainCoverage[D] = { N1(LINK+LSL) + N2(LINK+LSL) + ... + Nn(LINK+LSL) } Where: N1...Nn are all nodes in Node.HOP1[] that are in the D Domain. Nx(LINK+LSL) is the total weight assigned for 1-hop neighbors 1-n where: LINK is some constant added for the existence of a link (quantity) Ghanadan, et al. Expires September 2010 [Page 55] Internet-Draft AHDR March 2010 LSL is some value derived link state level (LCI + LQI) Nx is some weight given to each neighbor node where o low mobility nodes have a higher N-weight than relatively mobile nodes o higher stability (in terms of topology change, link variations, etc.) correlates to a higher N-weight 2) For each Domain Lead Nodeid in Node.DomainCoverage[].CoveredNode 3) Store Node.DomainCoverage[].Cover[].CoveringNode values of each corresponding neighbor node in Node.Bridge[] based on each neighbor with the HIGHEST Node.DomainCoverage[].Cover[].Coverage for given Domain, for all Domains within 2 hops of this node. 4) If a TU1 is received from a neighbor node and TU1.LeadCoverage[] contains HIGHEST .Coverage for a given Domain compared to existing .Coverage value for corresponding Node.DomainCoverage[].CoveredNode, then a. Set Node.Bridge[] entry for corresponding Domain Lead coverage to this neighbor node. 5) Upon forwarding RDISC, TUD, or IPAD messages, M.Bridge[] is populated with 1-hop or 2-hop neighbor Nodes to reach a given DESTNODE, or to reach all Domains in the network. The Bridge Nodes selection algorithm is based on neighboring Domain coverage, represented by corresponding Node.DomainCoverage[], but the number of Bridge Nodes selected depends on implementation. The following two algorithms may be used in two different scenarios: Optimizing for the fewest Bridge Nodes for minimal transmissions: o Determine whether or not there is a single Node that has covers (i.e., has a value for all Node.DomainCoverage[].CoveredNode entries) for all neighboring Domains 1-hop away Add this Node to the M.Bridge[] o If not, determine whether or not there are a pair of nodes that cover all neighboring Domains Add these two Nodes to the M.Bridge[] o If not, select a Node that covers the highest number of neighboring Domains Add this Node to the M.Bridge[] Determine whether or not there is a single Node that covers the remaining Domains Repeat o Repeat for 2-hop Domains Ghanadan, et al. Expires September 2010 [Page 56] Internet-Draft AHDR March 2010 Optimizing for path diversity: o For each neighboring 1-hop or 2-hop Domain, select the Node with the HIGHEST Node.DomainCoverage[].Cover[].Coverage for the corresponding Domain ( Node.DomainCoverage[].Cover[].CoveredNode) as a Bridge Node o Add these Nodes to the M.Bridge[] 8.9. Domain Lead Tracking Process This process specifies the procedure to determine if the received TUD, RDISC, and IPAD messages should be forwarded and to which domain(s). The process seeks to prevent the redundant TUD message dissemination and loops within the message propagation path. The derived Bridge Node listing will be used to fill in the M.Bridge[] field where M is the TDU, the RDISC, and the IPAD messages. TRIGGERING EVENTS: o Each time the TDU, RDISC, and IPAD message is received and the receiving node needs to determine whether to forward the message and to which domain(s). ACTIONS: 1) Find index, II, of the M.Bridge[] table where M.Bridge[II].Nodeid is Node.Nodeid. If II not found, discard the message and Stop Process. 2) Make Covered, the set of all Domains from M.DomainTrack[]. Find MyList, the set of Domains indicated by the M.BNForwardRef[II] table entry. Find NotMyList = Covered - MyList. Make Needed, the set of all Node.DomainCoverage[].Nodeid Domains. Set Needed to Needed - Node.Nodeid. Set Needed to Needed - NotMyList. 3) If Needed is empty, discard message and Stop Process. 4) Clear M.Bridge[] and M.BNForwardRef[] tables and set M.BNs to 0. 5) Set M.DomainTrack[] to the set (Covered union Needed). Set M.DLs to the size of the set. Because Covered does decrease, the DomainTrack may only stay the same size or increase. 8.10. Create Checksum Process Ghanadan, et al. Expires September 2010 [Page 57] Internet-Draft AHDR March 2010 TRIGGERING EVENTS: o When filling in the M.Checksum field. ACTIONS: 1) Set CHECKSUM to 0. Check M.Checksum to 0. 2) Starting with M.Header, loop through M.Header.Length 16-bit values adding each to CHECKSUM. If CHECKSUM exceeds a 32 bit value, add the overflow bit back into CHECKSUM. 3) Set M.Checksum = bitwise NOT of CHECKSUM. 8.11. Check Checksum Process TRIGGERING EVENTS: o Received message with .Header.C set to 1. RESULT: o Pass. o Fail. ACTIONS: 1) Set CHECKSUM to 0. 2) Starting with M.Header, loop through M.Header.Length 16-bit values adding each to CHECKSUM. If CHECKSUM exceeds a 32 bit value, add the overflow bit back into CHECKSUM. 3) If CHECKSUM is 0, then RESULT is Pass, else RESULT is Fail. 8.12. TU0 Processes 8.12.1. TU0 Send Process TRIGGERING EVENTS: o Node startup (from "Main Process"). o Last Node.HOP1[] entry removed from table (from "Link Lost Process"). o Node.Timer expires when Node.HOP1[] table is empty (from "Main Process"). ACTIONS: 1) Set M.Header.Type to TU0 and execute "Message Send Process". 8.12.2. TU0 Receive Process ACTIONS: Ghanadan, et al. Expires September 2010 [Page 58] Internet-Draft AHDR March 2010 1) None. All necessary actions are handled in the "Message Receive Process". 8.13. TU1 Processes 8.13.1. TU1 Send Process TRIGGERING EVENTS: o Node.Timer expires and Node.HOP1[] table not empty (from "Main Process"). The TU1 message is transmitted by all nodes in the network. ACTIONS: 1) Set M.Header.Type to TU1 and construct the TU1 Fields per section 7.5.1. 2) Execute "Message Send Process". 8.13.2. TU1 Receive Process TRIGGERING EVENTS: o TU1 message received and being processed by the "Message Receive Process". ACTIONS: 1) The receiving Node SHALL update its HOP1 Entry, E, with the following fields from the TU1 message: o E.Timer.Interval = E.Timeout o E.Timer.Countdown = E.Timeout o E.SendLSL = TU1.Neighbor[N].FromLSL o E.ReceiveLSL = TU1.Neighbor[N].ToLSL o E.Coverage = TU1.Coverage o E.DomainLead = TU1.Neighbor[].Nodeid (where .Neighbor[].DI is 1). 2) Loop through the TU1.LeadCoverage[] table and TU1.DomainCoverage[] table to maintain the Node.DomainCoverage[] table with up-to-date values from TU1.Header.Sender. 3) Use the "Calculate Domain Lead Process" to decide if a Domain Lead change is needed. 4) Use the "Bridge Selection Process" to decide if the Node.Bridge[] should be updated. Ghanadan, et al. Expires September 2010 [Page 59] Internet-Draft AHDR March 2010 8.14. TUD Processes 8.14.1. TUD Send Process TRIGGERING EVENTS: o The full TUD message is broadcast by the Domain Lead Node every user configurable multiple of the Node.Timeout.Topology interval. o If the Domain membership changes (i.e., a Node joins or leaves the Domain Lead's domain or the link to an existing Domain Node changes LSL) the corresponding Domain Lead Node MAY broadcast an Update TUD message. To minimize the routing overhead, the Update TUD should not be generated more than once per 2x Node.Timeout.Topology interval. If the full TUD message is due for a transmission, the Update TUD should not be transmitted at the same time. o A TUD was received that needs to be forwarded through the network. See the TUD Receive Process for details. ACTIONS: 1) Set M.Header.Type to TUD and construct the TUD Fields per section 7.6.1 according to the full or update TUD required. 2) Execute "Message Send Process". 8.14.2. TUD Receive Process TRIGGERING EVENTS: o TUD message received. ACTIONS: 1) If the most recent TUD.Sequence from the same TUD.Header.Sender (called Last.Sequence) is newer than the received TUD.Sequence, then discard the message and Stop Process. Because sequence numbers may be reused (due to the field value rolling over), the following SHALL be the definition of "newer": ( (TUD.Sequence < Last.Sequence) AND ((Last.Sequence - TUD.Sequence) < (MAX.Sequence/2) ) ) OR ( (TUD.Sequence > Last.Sequence) AND ((TUD.Sequence - Last.Sequence) > (MAX.Sequence/2) ) ) Note that MAX.Sequence is the maximum value that the TUD.Sequence field in the message can have. Ghanadan, et al. Expires September 2010 [Page 60] Internet-Draft AHDR March 2010 2) The receiving Node SHALL update its HOP1 Entry, E, with the following fields from the TUD message: o E.Timer.Interval = E.Timeout o E.Timer.Countdown = E.Timeout o E.SendLSL = TUD.Domain[].LSL for the receiving node. o E.ReceiveLSL = TUD.Domain[].OLSL for the receiving node. o E.DomainLead = TUD.Header.Sender. 3) The Node SHALL use the information in the TUD message to update its own Node.HOPK[] table. 4) To determine whether to forward the received TUD message, the Node SHALL execute the "Domain Lead Tracking Process" using the received TUD message as input. The TUD message may be updated by the Process. 5) To determine which Bridge Nodes will be used to forward the TUD, the Node SHALL execute the "Bridge Update Process" using received TUD message as input. The TUD message may be updated by the Process. 6) If the TUD.BNs is 0 and the Node is not a Domain Lead, discard the message and Stop Process. 7) If the TUD.BNs is 0 and the Node is a Domain Lead, the Node MAY choose to broadcast the TUD a final time (the empty TUD.Bridge[] table means it won't get forwarded). Doing this will ensure that all the Node's 1-hop neighbors will receive the TUD and update their HOPK tables. If the Node does not choose to do this, discard the message and Stop Process. 8) Update the following fields per Section 7.6.1: TUD.Hops, TUD.LSLTotal, TUD.LT1 - TUD.LT4, TUD.Previous. 9) Execute the "Message Send Process" with the updated TUD. 8.15. DLA Processes 8.15.1. DLA Send Process TRIGGERING EVENTS: o A node SHALL send a DLA message when its Node.Coverage value is greater than all of Node.HOP1[].Coverage value. ACTIONS: Ghanadan, et al. Expires September 2010 [Page 61] Internet-Draft AHDR March 2010 1) Set M.Header.Type to DLA and construct the DLA fields per section 7.7.1 2) Execute "Message Send Process". 8.15.2. DLA Receive Process TRIGGERING EVENTS: o DLA message received. ACTIONS: 1) Add or update Node.DomainLead[] table entry using DLA.Header.Sender and DLA.Coverage values. 2) Add or update Node.DomainCoverage[] table entry using DLA.Header.Sender and DLA.Coverage values. 3) Update Node.HOP1[] table entry for DLA.Header.Sender with DLA.Coverage value. 4) Execute "Calculate Domain Lead Process". 8.16. DLR Processes 8.16.1. DLR Send Process TRIGGERING EVENTS: o A Domain Lead node SHALL send a DLR message when its Node.Coverage value is less than any Node.HOP1[].Coverage value. ACTIONS: 1) Set M.Header.Type to DLR and construct the DLR fields per section 7.8.1 2) Execute "Message Send Process". 8.16.2. DLR Receive Process TRIGGERING EVENTS: o DLR message received. Ghanadan, et al. Expires September 2010 [Page 62] Internet-Draft AHDR March 2010 ACTIONS: 1) Remove the DLA.Header.Sender entry from the Node.DomainLead[] table. 3) Add or update Node.DomainCoverage[] table entry using DLA.Header.Sender and DLA.Coverage values. 4) Update Node.HOP1[] table entry for DLA.Header.Sender with DLA.Coverage value. 5) Add or update Node.DomainLead[] table entry using DLA.Header.NewLead and DLA.NewCoverage values. 6) Add or update Node.DomainCoverage[] table entry using DLA.Header.NewLead and DLA.NewCoverage values. 7) Update Node.HOP1[] table entry for DLA.Header.NewLead with DLA.NewCoverage value. 8) Execute "Calculate Domain Lead Process". 8.17. RDISC Processes 8.17.1. RDISC Send Process TRIGGERING EVENTS: o The RDISC message is used to discovery route to a destination address not found in the node's HOP1, HOP2, and HOPK tables. ACTIONS: 1) Set M.Header.Type to RDISC and construct the RDISC fields per section 7.9.1 2) When an RDISC is generated or forwarded from a Node, the Node SHALL keep a copy of the RDISC for processing when response messages (RRES or RERR) are received. 3) Execute "Message Send Process". 8.17.2. RDISC Receive Process TRIGGERING EVENTS: o RDISC message received. ACTIONS: Ghanadan, et al. Expires September 2010 [Page 63] Internet-Draft AHDR March 2010 1) If the most recent RDISC.Sequence from the same RDISC.Header.Sender (called Last.Sequence) is newer than the received RDISC.Sequence, then discard the message and Stop Process. Because sequence numbers may be reused (due to the field value rolling over), the following SHALL be the definition of "newer": ( (RDISC.Sequence < Last.Sequence) AND ((Last.Sequence - RDISC.Sequence) < (MAX.Sequence/2) ) ) OR ( (RDISC.Sequence > Last.Sequence) AND ((RDISC.Sequence - Last.Sequence) > (MAX.Sequence/2) ) ) Note that MAX.Sequence is the maximum value that the RDISC.Sequence field can have. 2) If the Node is not a Domain Lead and the Node does not find its own Nodeid in the RDISC.Bridge[] table the message SHALL be discarded. 3) Depending on the circumstances, the Node MAY generate an RRES Message or and RERR Message in reply to the RDISC. See the "RRES Send Process" and "RERR Send Process" sections for details. 4) If the Node does not generate an RRES or an RERR message AND there are Domains that the RDISC has not visited, AND the Node is in the RDISC.Bridge[] table, the Node will forward a copy of the RDISC message towards those Domains. Before forwarding, the Node will update the RDISC.Bridge[], RDISC.DomainTrack[] and RDISC.BNForwardRef[] tables to show which Domains have been covered and which Domains have yet to receive the RDISC message. 5) FOr each received RDISC store the RDISC.Header.Sender, the RDISC.Source, RDISC.BNs, RDISC.Sequence, RDISC.Destination. 8.18. RRES Processes 8.18.1. RRES Send Process TRIGGERING EVENTS: o The node receives an RDISC and it has at least one route to the destination node i.e., the node has the RDISC.Destination address in its HOP1, and/or HOP2, or HOPK tables. ACTIONS: 1) Set M.Header.Type to RRES and construct the RRES fields per section 7.10.1 Ghanadan, et al. Expires September 2010 [Page 64] Internet-Draft AHDR March 2010 2) Execute "Message Send Process". 8.18.2. RRES Receive Process TRIGGERING EVENTS: o RRES message received. ACTIONS: 1) Find a saved RDISC message, saveRDISC, where saveRDISC.Sequence matches RRES.Sequence. 2) If saveRDISC is found, then forward the RRES via the saveRDISC.Header.Sender node. If saveRDISC is not found, then forward the RRES via the best known NextHop for the RRES.Destination Node. If the receiving node does not have a route to the RRES.Destination node, then silently discard RRES message and Stop Process. 3) Before forwarding the RRES message, the following fields in the RRES message SHALL be updated per section 7.10.1: RRES.Hopcount, RRES.PrevLSL, RRES.DestLSL, and RRES.Previous. 8.19. RERR Processes 8.19.1. RERR Send Process TRIGGERING EVENTS: o Upon receipt of an RDISC message, the node does not have any route to the RDISC.Destination node AND it knows no other Domains to forward the RDISC message to. Note that only BN and Domain Lead nodes generate the RERR message. o Received an RERR message from RDISC.BNs nodes, then an RERR message SHALL be forwarded to the RDISC.Header.Sender node. ACTIONS: 1) Set M.Header.Type to RERR and construct the RERR fields per section 7.11.1 2) Execute "Message Send Process". 8.19.2. RERR Receive Process TRIGGERING EVENTS: o RERR message received. Ghanadan, et al. Expires September 2010 [Page 65] Internet-Draft AHDR March 2010 ACTIONS: 1) If the RERR.Sequence does NOT RDISC.Sequence value of any of the stored RDISC message, the received RERR message SHALL be silently discarded. 2) If RERR.Header.Sender is one of the nodes in RDISC.Bridge[], the Node SHALL record the response from that RERR.Header.Sender node. If an RERR has been received from all RDISC.Bridge[] nodes, then an RERR message SHALL be forwarded to the RDISC.Header.Sender node. See "RERR Send Process" for details. 8.20. IPAD Processes 8.20.1. IPAD Send Process TRIGGERING EVENTS: o An IPAD message is sent per expiration of the Node.Timeout.IPAD timer; o Node MAY transmit a full IPAD message containing all of the Node.IPAD.Advertised[] table entries. o When the Node.IPAD.Advertised[] table changes for any reason, the Node MAY transmit an update IPAD message containing only those Node.IPAD.Advertised[] table entries that have changed. o Once an IPAD message has been sent (either full or update), another IPAD message may not be sent until at least another (Node.Timeout.IPAD / 3) expirations of Node.Timeout.Topology have occurred. ACTIONS: 1) Set M.Header.Type to IPAD and construct the IPAD fields per section 7.12.1 2) Execute "Message Send Process". 8.20.2. IPAD Receive Process TRIGGERING EVENTS: o IPAD message received. ACTIONS: o Upon receipt of an IPAD message, the receiving Node will process the IPAD.Address[] table entries in order to update its own Node.IPAD.Learned[] table entries. Ghanadan, et al. Expires September 2010 [Page 66] Internet-Draft AHDR March 2010 o If there are Domains that the IPAD has not visited, the Node will forward a copy of the IPAD message towards those Domains. Before forwarding, the Node will update the IPAD.Bridge[], IPAD.DomainTrack[] and IPAD.BNForwardRef[] tables to show which Domains have been covered and which Domains have yet to receive the IPAD message. The IPAD.BNs and IPAD.DLs must be updated accordingly. The IPAD.Count and IPAD.Sequence fields for the message to be forwarded are copied from the received IPAD message. The message M.Header and M.Checksum SHALL be constructed per "Message Send Process" 9. Security Considerations AHDR does not provide any additional security to a network. AHDR also does not contain any security measures that would prevent an outside agency from inserting malicious AHDR messages. 10. References [1] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996. 11. Acknowledgments The authors wish to thanks BAE Systems for their support as we explore the possibilities of AHDR. The following programs or projects were especially useful as proving grounds for our concepts: FAST - Flexible Access, Secure Transfer: An enhanced access mode for Link-16. META-MANET - Mesh Enabled Tactical Adaptive MANET: A mobile, multihop mesh networking waveform. TWNN - Tactical Wideband Network Node: A multichannel radio networking platform. 12. Author's Addresses Reza Ghanadan Jessica Hsu BAE Systems BAE Systems 164 Totowa Road 164 Totowa Road Wayne, NJ 07474 Wayne, NJ 07474 reza.ghanadan@baesystems.com jessica.hsu@baesystems.com Phong Khuu Gregory S. Sadosuk BAE Systems BAE Systems 11487 Sunset Hills Road 11487 Sunset Hills Road Ghanadan, et al. Expires September 2010 [Page 67] Internet-Draft AHDR March 2010 Reston, VA 20190 Reston, VA 20190 phong.khuu@baesystems.com gregory.sadosuk@baesystems.com In addition to the authors, the following people were instrumental in the design and realization of AHDR: John Gu BAE Systems, Wayne, NJ Brian Loop BAE Systems, Reston, VA Michael J. Weber BAE Systems, Reston, VA Ghanadan, et al. Expires September 2010 [Page 68]