Mobile Ad hoc Networking (MANET) Y. Lacharite Internet-Draft M. Wang Intended status: Experimental Communications Research Centre Expires: January 14, 2010 Canada P. Minet INRIA T. Clausen LIX, Ecole polytechnique July 13, 2009 Hierarchical OLSR draft-lacharite-manet-holsr-02 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." 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 on January 14, 2010. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Lacharite, et al. Expires January 14, 2010 [Page 1] Internet-Draft HOLSR July 2009 Abstract This document describes the Hierarchical Optimized Link State Routing (HOLSR) mechanism for heterogeneous mobile ad hoc networks. In this specification a heterogeneous mobile ad hoc network is defined as a network of mobile routers that are characterized by different communication capabilities, such as communication channels, processing powers or energy levels. The HOLSR mechanism is an extension to the OLSRv2 protocol. HOLSR takes advantage of the router's distinct communications capabilities to reduce the routing control overhead in large heterogeneous ad hoc networks, thus improving the performance of the routing mechanism. More precisely, HOLSR defines a hierarchy in the network and presents a routing scheme for this hierarchical structure with a better scalability. Lacharite, et al. Expires January 14, 2010 [Page 2] Internet-Draft HOLSR July 2009 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 7 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 8 4.1. Hierarchy Building . . . . . . . . . . . . . . . . . . . . 8 4.2. Hierarchy Routing . . . . . . . . . . . . . . . . . . . . 11 5. Protocol Parameters . . . . . . . . . . . . . . . . . . . . . 11 5.1. Message Intervals . . . . . . . . . . . . . . . . . . . . 11 5.1.1. CIA Messages . . . . . . . . . . . . . . . . . . . . . 12 5.1.2. HTC Messages . . . . . . . . . . . . . . . . . . . . . 12 5.2. Information Validity Times . . . . . . . . . . . . . . . . 13 5.2.1. CIA Validity Times . . . . . . . . . . . . . . . . . . 13 5.2.2. HTC Validity Times . . . . . . . . . . . . . . . . . . 13 5.3. Cluster Intersection Depth . . . . . . . . . . . . . . . . 14 5.4. Cluster Critical Path . . . . . . . . . . . . . . . . . . 14 6. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 14 6.1. Description of HOLSR Logical Topology Levels . . . . . . . 15 6.1.1. Example . . . . . . . . . . . . . . . . . . . . . . . 15 6.2. Cluster Formation . . . . . . . . . . . . . . . . . . . . 16 6.2.1. Particular Case: Cluster Intersections . . . . . . . . 17 6.2.2. Cluster ID Announcement Validity Timer . . . . . . . . 17 6.3. Cluster Interaction . . . . . . . . . . . . . . . . . . . 18 6.3.1. Types of Hierarchical Topology Control Message . . . . 18 6.3.2. HTC and TC Message Propagation . . . . . . . . . . . . 19 6.4. Clusters Decommission . . . . . . . . . . . . . . . . . . 19 6.5. HOLSR Repositories . . . . . . . . . . . . . . . . . . . . 20 6.6. HOLSR Messages . . . . . . . . . . . . . . . . . . . . . . 21 6.6.1. CIA Messages . . . . . . . . . . . . . . . . . . . . . 21 6.6.1.1. CIA Message TLVs . . . . . . . . . . . . . . . . . 22 6.6.2. HTC Messages . . . . . . . . . . . . . . . . . . . . . 22 6.6.2.1. HTC Message TLVs . . . . . . . . . . . . . . . . . 23 6.7. HOLSR Algorithm . . . . . . . . . . . . . . . . . . . . . 23 6.7.1. Processing and Broadcasting CIA Message . . . . . . . 23 6.7.2. Processing and Forwarding HTC Message . . . . . . . . 24 6.7.3. Cluster Intersection Handling . . . . . . . . . . . . 25 7. Proposed Values for Parameters . . . . . . . . . . . . . . . . 26 7.1. Message Intervals Parameter Defaults . . . . . . . . . . . 26 7.1.1. CIA Messages . . . . . . . . . . . . . . . . . . . . . 26 7.1.2. HTC Messages . . . . . . . . . . . . . . . . . . . . . 27 7.2. Information Validity Times Parameters . . . . . . . . . . 27 7.2.1. CIA Messages . . . . . . . . . . . . . . . . . . . . . 27 7.2.2. HTC Messages . . . . . . . . . . . . . . . . . . . . . 27 7.3. Cluster Intersection Depth . . . . . . . . . . . . . . . . 27 7.4. Cluster Critical Path . . . . . . . . . . . . . . . . . . 27 8. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 27 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 28 Lacharite, et al. Expires January 14, 2010 [Page 3] Internet-Draft HOLSR July 2009 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 10.1. Message Types . . . . . . . . . . . . . . . . . . . . . . 28 10.2. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 29 10.3. HTC_MSG_TYPE Values . . . . . . . . . . . . . . . . . . . 29 11. Security Considerations . . . . . . . . . . . . . . . . . . . 30 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 12.1. Normative References . . . . . . . . . . . . . . . . . . . 30 12.2. Informative References . . . . . . . . . . . . . . . . . . 30 Appendix A. Example of Data Transfer using Clusters . . . . . . . 30 Appendix B. Example of Cluster Decommission Handling . . . . . . 33 Appendix C. Packet and Message Layout . . . . . . . . . . . . . . 35 C.1. Packet and Message Options . . . . . . . . . . . . . . . . 35 C.2. Example CIA Message . . . . . . . . . . . . . . . . . . . 35 C.3. Example HTC Message . . . . . . . . . . . . . . . . . . . 36 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 37 Lacharite, et al. Expires January 14, 2010 [Page 4] Internet-Draft HOLSR July 2009 1. Introduction The Hierarchical Optimized Link State Routing Protocol (HOLSR) is designed for heterogeneous ad hoc networks, and is an extension to the OLSRv2 [I-D.ietf-manet-olsrv2] routing protocol. HOLSR has two main functionalities: o Hierarchy building: HOLSR organizes routers into hierarchical levels according to their capacities (e.g. radio, energy, processing) and dynamically groups routers into clusters at each level. o Hierarchical routing: HOLSR provides a hierarchical routing that supports random movement of the routers among and between clusters, and can dynamically adapt to topology changes at different levels. Within each cluster, the OLSRv2 routing protocol, as specified in [I-D.ietf-manet-olsrv2], is used. The main improvements realized by the HOLSR protocol are a reduction in the amount of topology control information that needs to be exchanged at different levels of the hierarchical network topology, and the efficient use of high capacity routers. Another significant benefit is a reduction in routing computational cost: if a link in one part of the network is broken, only those routers within the cluster in which the link exists need to re-calculate the routing table, while routers in other clusters are not affected. HOLSR is versatile in that it does not require a logical hierarchical addressing scheme but can accommodate one if required. In an HOLSR network structure, the routers equipped with high capacity links form the higher-level network, while the routers with low capacity links form the lower-level network. At a given level, cluster heads are selected from the routers with higher capabilities. The choice of the cluster head or the establishment of its capability criteria (e.g. multiple interfaces, more processing power, increased memory, etc.), is out of scope of this document. It is left to the implementer or the administrator, who can select the best criteria adapted to the specific network deployment. Routers can move from one cluster to another, and can associate with the nearest cluster head, while the cluster heads propagate updated membership information among each other using Hierarchical Topology Control (HTC) messages. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and Lacharite, et al. Expires January 14, 2010 [Page 5] Internet-Draft HOLSR July 2009 "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. This document uses OLSR terminology as defined in OLSRv1 [RFC3626] and OLSRv2 [I-D.ietf-manet-olsrv2]. MANET specific terminology is to be interpreted as described in [RFC5444] and NHDP [I-D.ietf-manet-nhdp]. Additionally, this document uses the following terminology: Cluster A small group or gathering of MANET routers that have the same cluster head. Cluster Head A MANET router can become a cluster head at level i if: * it possesses a "higher capability" besides the one it shares with its cluster neighbor routers, and * it participates in communication level i+1. The definition of "higher capability" is a deployment issue, out of scope of this document. Cluster Member A MANET router that is associated with a cluster head. CIA Cluster Id Announcement. A control message initiated periodically by a cluster head to declare its leadership and invite other routers to join its cluster. Cluster members generate CIA messages including a distance field set to their distance (in terms of number of hops) to the cluster head). The message is generated by cluster members until it reaches the edge of the cluster. Cluster Edge Cluster Edge. Distinguishes routers belonging to the cluster from others. Cluster Intersection Depth When routers from one cluster can hear Cluster Id Announcements from another cluster, it is said that these two clusters intersect, i.e. a router on the edge of one cluster is in radio communication range from the edge of a neighbor cluster. The depth of the intersection depends on the permissions given to edge routers from different clusters to inter-communicate without going Lacharite, et al. Expires January 14, 2010 [Page 6] Internet-Draft HOLSR July 2009 through (and bypassing) their respective cluster heads. For a depth value of '1', edge routers from two different clusters within radio range can communicate, but they cannot forward messages from each other within their own cluster. For a depth value of '2', the same two edge routers are permitted to forward neighbor cluster's messages once (Time to live (TTL) = '1'). For a depth value of '3', TTL = '2', etc. HTC Hierarchical Topology Control (TC). A control message sent periodically that is used to propagate the membership information of a cluster to the higher hierarchical level routers. OLSRv2 The Optimized Link State Routing protocol version 2 is an update to OLSRv1 as published in [RFC3626]. Router A MANET router which implements the Hierarchical OLSRv2 protocol as specified in this document. Topology level A logical level that is composed of links and routers that share similar characteristics (e.g. bandwidth, transmission range, energy capacity, processing capacity). The higher the level gets, the "better" the characteristics are. 3. Applicability Statement Many contemporary ad hoc wireless networks are heterogeneous in nature, being comprised of mobile devices with heterogeneous capacities. For instance, these devices can have distinct communications capabilities with respect to data rate, radio range, frequency band, etc. They can also have different energy capacities and different processing capacities. We can cite two examples of networks where HOLSR provides high benefits: military networks and sensor networks. In military networks for instance, soldiers, tanks and headquarters might each be given wireless communication equipment that is appropriate to their communication needs. Soldiers are usually equipped with wireless communication devices characterized by limited resources in terms of radio bandwidth, energy capacity and processing capacity. Those devices can only handle limited transmission range and have restricted communications bandwidth. Vehicles, on the other hand, are outfitted with more powerful equipments providing extended communication coverage with higher communication bandwidth Lacharite, et al. Expires January 14, 2010 [Page 7] Internet-Draft HOLSR July 2009 capability. In data gathering applications supported by wireless sensor networks, the aim is to maximize network lifetime. Energy efficient strategies are used such as clustering. Cluster heads are selected among the routers with a sufficient energy level, and rotate in order to balance energy consumption. Cluster heads can also be chosen with an additional applicative criterion: they represent routers having the same data value to transmit to the data sink. HOLSR is also beneficial to mesh networks in general, where there can be limited or no mobility such as sensor networks. HOLSR can manage a combination of mobile and non-mobile components. Scalability is one of the most important factors governing the efficiencies of heterogeneous wireless networks. Scalability may be defined as the ability of a network to adjust or maintain its performance when its size increases. That also includes the increase in traffic load that is handled. Yet under a "flat" routing protocol, the performance of an ad hoc network tends to degrade as the number of mobile routers increases. When a flat routing protocol is used, the resulting control overhead increases, depending on the number of interfaces possessed by each router since more links need to be propagated for each router in order to share the topology information. Concerning data gathering applications, the use of hierarchical routing enables reducing the amount of data transferred to the sink, and hence to maximize network lifetime. 4. Protocol Overview and Functioning HOLSR consists of 2 main functionalities: enabling the creation of a hierarchy structure on top of a standard OLSR network; and providing the control messaging tools to transmit the hierarchy topology and enable routing through the use of gateway routers, defined as cluster heads. The criteria used to define and select cluster heads unto which to construct the HOLSR hierarchical structure is outside the scope of this protocol. 4.1. Hierarchy Building In HOLSR, a hierarchical structure is constructed over the network based on its member routers' capabilities. In the following description, the criteria selected for higher capabilities is linked to the amount and properties of each router's wireless interfaces. Lacharite, et al. Expires January 14, 2010 [Page 8] Internet-Draft HOLSR July 2009 Let us demonstrate the idea using figures 1 and 2, composed of 23 MANET routers. In figure 1, routers are denoted by letters, and their preceding character determines their capabilities and available interfaces. Thus a "." identifies regular MANET routers, a "#" identifies routers with 2 interfaces ("low" and "medium" range radio); a "&" identifies routers with 3 interfaces (low, medium, and "long" range radio); and a "@" identifies routers with 2 interfaces (medium and long range radios). For this example, it is decided that the routers with multiple interfaces be used as cluster heads. From then on, MANET routers start organizing themselves into clusters around their cluster heads. There are 4 cluster heads (a, f, p, and t) that have dual low and medium transmission range interfaces. These form 4 intersecting clusters at level 1 (see figure 2). Routers are identified with their cluster id (capital character followed by a number, or 'H' for a cluster head), cluster A members are now AH, A1, A2, and A3 (respectively a, b, c and d), etc. Clusters at level 2 are formed by routers that possess at least one interface with medium transmission range. This requirement is matched by routers a, f, p, r, and u. From these routers, the ones that contain an additional long transmission range radio interface (level 3) become cluster heads at level 2 (this applies to routers f and r). Hence 2 clusters are created at level 2 (E and F with cluster heads EH and FH). The level 3 "overall" cluster is formed by routers f and r, since they share the long transmission range capabilities. No cluster head is required at level 3 since 1) there is no higher level; 2) the 2 members are in transmission range of each other. Lacharite, et al. Expires January 14, 2010 [Page 9] Internet-Draft HOLSR July 2009 _.--------------------------. _.------'' .h .m #p `--------. ,--'' &f .k @r `---. ,-' `-. / .d .g .j .o .s .v \ ( #a .e .l #u ) \ .q / `-. .b .i .w ,-' `---. .c .n .t _.--' `--------. _.------'' `--------------------------'' Figure 1 - Typical MANET Example . . . . . . . . .. .. .. . . .. . | | | | | | | | || || || | | || | +--- ---+ _.--------------------------. L _.----'' `------. e ,-'' `--. v ,' `. e ( E.f.....................F.r ) L `. | | ,' `--. | | _.-' 3 `------. | |_.----'' `---+----------------------'' +--- | Overall Cluster | ---+ _.----------| _.---+------. L ,-'' |`--. ,-'' ,'FH.r. `--. e / | \ / ,' '-. \ v ( A.a.............EH.f ) ( C.p..........D.u ) e \| | / \ | | / l |--. |_.-' `--.| |.-' | `----------'| |----------''| 2 | Cluster E | ,------+. Cluster F | | ,---+-------.,-' | `-. | +--- | ,-' | B1.h,'`-. C1.m CH.p `. | ---+ | ,----,'---. BH.f / C4.k. \,----+----. L ,+' / `-. ; \ ,-': | `-. e / | ( A3.d \B2.g| B5.j ) C2.o /C6.s| | D1.v\ v / AH.a \ B4.e\ : C5.l/ / ; DH.u \ e ( `. ) \ ,' (D4.q/ ) l \ A1.b '-. / B3.i`.,-' \ ,' D2.w / \ A2.c `---+-------''-. C3.n ,-\ D3.t / 1 `-. ,-'Cluster B `-------' `-. ,-' `---------' Cluster C `---------' +--- Cluster A Cluster D ---+ Figure 2 - Hierarchical MANET Example Lacharite, et al. Expires January 14, 2010 [Page 10] Internet-Draft HOLSR July 2009 Cluster formation of the hierarchy structure is made possible by the addition of Cluster Id Announcement (CIA) messages. Every router selected as a cluster head sends CIA messages periodically to declare its leadership and invite other routers to join its cluster. Section 6 provides complete details. 4.2. Hierarchy Routing In HOLSR, at a given level, routers can move from one cluster to another and associate with the nearest cluster head. For routing purposes, the information about cluster membership is transmitted to higher levels by the cluster heads. The following denotes the routing structure within HOLSR: o Within each cluster, OLSRv2 [I-D.ietf-manet-olsrv2] runs unaltered, providing routing topology information about router destinations within the same cluster. TC message propagation is limited within the local cluster. o Between clusters, the information about cluster membership and topology information is transmitted to higher levels by the cluster heads using Hierarchical Topology Control (HTC) messages. o For routers located in overlapping regions of multiple clusters, OLSRv2 TC messages can (with restrictions) be propagated not only within the cluster but to the neighbor clusters as well. This feature is controlled by the C_INTER_DEPTH parameter defined in Section 5.3. Section 6.7.3provides complete details. o Traffic from one cluster with destination to another cluster will travel up the levels through cluster heads (acting as gateways) and then down to reach their destination. Routers set their cluster head as default gateway in their routing table. Hence, every traffic request for destinations outside of their cluster will go through their cluster head. 5. Protocol Parameters The parameters used in this specification are those defined in OLSRv2 [I-D.ietf-manet-olsrv2] plus those described in this section. 5.1. Message Intervals The following parameters regulate CIA and HTC message transmissions by a router. Lacharite, et al. Expires January 14, 2010 [Page 11] Internet-Draft HOLSR July 2009 5.1.1. CIA Messages CIA messages are transmitted periodically to advertise a router's cluster head id and its distance from that cluster head. The frequency of these advertisements is regulated by the parameters CIA_INTERVAL and CIA_MIN_INTERVAL. Specifically, these parameters are as follows: CIA_INTERVAL the maximum time between the transmission of two successive CIA messages by a given cluster head. If using periodic transmission of CIA messages for a given cluster head, these SHOULD be at a separation of CIA_INTERVAL, and MAY be modified by jitter as specified in [RFC5148]. CIA_MIN_INTERVAL the minimum interval between transmission of two successive CIA messages by a given cluster head. (This minimum interval MAY be modified by jitter, as defined in [RFC5148].) The following constraints apply to these parameters: o CIA_INTERVAL > 0 o CIA_MIN_INTERVAL >= 0 o CIA_INTERVAL >= CIA_MIN_INTERVAL o If INTERVAL_TIME message TLVs as defined in [RFC5497] are included in CIA messages, then CIA_INTERVAL MUST be representable as described in [RFC5497]. 5.1.2. HTC Messages HTC messages are transmitted periodically by a cluster head to advertise its membership information to routers at the higher hierarchical level. The frequency of these advertisements is regulated by the parameters HTC_INTERVAL and HTC_MIN_INTERVAL. HTC messages are an extension to the TC messages from OLSRv2 [I-D.ietf-manet-olsrv2], and as such they MAY use the same message interval parameters, and the same message validity times: HTC_INTERVAL the maximum time between the transmission of two successive HTC messages by a cluster head. When no HTC messages are sent in response to local network changes under the cluster head, then HTC messages SHOULD be sent at a regular interval HTC_INTERVAL, Lacharite, et al. Expires January 14, 2010 [Page 12] Internet-Draft HOLSR July 2009 possibly modified by jitter as specified in [RFC5148]. HTC_MIN_INTERVAL the minimum interval between transmission of two successive HTC messages by a cluster head. (This minimum interval MAY be modified by jitter, as defined in [RFC5148].) The following constraints apply to these parameters: o HTC_INTERVAL > 0 o HTC_MIN_INTERVAL >= 0 o HTC_INTERVAL >= HTC_MIN_INTERVAL o If INTERVAL_TIME message TLVs as defined in [RFC5497] are included in HTC messages, then HTC_INTERVAL MUST be representable as described in [RFC5497]. 5.2. Information Validity Times 5.2.1. CIA Validity Times The following parameters manage the validity time of CIA information: CIA_HOLD_TIME the value in the VALIDITY_TIME message TLV included in the CIA message. The following constraints apply to this parameter: o CIA_HOLD_TIME >= CIA_INTERVAL o CIA_HOLD_TIME MUST be representable as described in [RFC5497]. 5.2.2. HTC Validity Times HOLSR HTC messages SHOULD use the same validity time parameters as for TC messages in OLSRv2 [I-D.ietf-manet-olsrv2]. OLSRv2 TC parameters for validity times are (refer to OLSRv2 [I-D.ietf-manet-olsrv2] for definitions): o T_HOLD_TIME o A_HOLD_TIME Lacharite, et al. Expires January 14, 2010 [Page 13] Internet-Draft HOLSR July 2009 o RX_HOLD_TIME o P_HOLD_TIME o F_HOLD_TIME 5.3. Cluster Intersection Depth The following parameter regulates the communication between clusters that are intersecting. This parameter has a direct impact on the decision to route traffic through cluster heads are directly between clusters at the same level. C_INTER_DEPTH the maximum depth that routers from different clusters in an intersected area can include routers from another cluster than their own in their routing tables (routers can only select one cluster head ID). The following constraints apply to this parameter: C_INTER_DEPTH >= 0 5.4. Cluster Critical Path The following parameter is used to identify cluster heads located on critical paths on the HOLSR architecture. A router is considered to be on a critical path if its failure causes network partition. C_CRITICAL_PATH - identifies a cluster head as being on the critical path of the hierarchical structure. The following constraints apply to this parameter: C_CRITICAL_PATH = [0,1], where 0 is 'false', and 1 is 'true' 6. Protocol Details This section describes the HOLSR routing protocol by specifying: o HOLSR logical topology levels o Cluster formation o Cluster interaction Lacharite, et al. Expires January 14, 2010 [Page 14] Internet-Draft HOLSR July 2009 o Cluster decommission o HOLSR repositories o HOLSR Algorithm 6.1. Description of HOLSR Logical Topology Levels Based on different communication capacities, routers are organized into logical topology levels. A logical topology level is constituted by routers having similar capacities (e.g. radio bandwidth, radio interface, energy capacity, processing capacity). The grouping and ordering of routers with similar capacities (to determine which to assign to higher or lower layers) is an administrator and deployment issue. Since one router can have multiple communication capacities (by possessing different wireless interfaces, for example), it can be visible as a router in different logical topology levels. Usually, low-power routers are equipped with only one interface offering limited data rate and transmission range. Such routers participate at the lowest topology Level 1. Routers at topology level i+1, with i greater than or equal to 1, have higher capacities than routers at level i. Any router at level i must be able to communicate, via a multi-hop path if necessary, with a router at level i that is able to communicate with a router at level i+1. In the same manner, if the level i+2 exists, then any router at level i+1 must be able to communicate with a router at level i+1 that is able to communicate with a router at level i+2. 6.1.1. Example An example of a three levels hierarchy can be described as follows. Routers at topology level 2 are equipped with a wireless interface that can provide a higher data rate and longer transmission range than the interfaces present on the level 1 routers. Some of the routers in topology level 2 possess up to two wireless interfaces, one of which is a wireless interface capable of communicating with level 1 routers. These routers can relay messages at topology level 2 using a frequency band or a medium access control (MAC) protocol that can differ from the one used for communication at topology level 1. Topology level 3 routers represent routers with the highest capacity. These routers can be equipped with up to three wireless interfaces capable of communicating in turn with level 1 and 2 routers and with other level 3 routers via high-speed point-to-point direct wireless links. It should be noted that routers in level 3 or 2 can have fewer than three or two wireless interfaces, respectively, and the Lacharite, et al. Expires January 14, 2010 [Page 15] Internet-Draft HOLSR July 2009 only requirement is that level 3 or 2 routers should be equipped with at least one wireless interface for communications at level 3 or 2, respectively. For example, a level 3 router could possess only one high-speed point-to-point interface for ensuring communication with level 3 routers. The rules governing these first three levels can be scaled to additional topology levels, as the HOLSR network increases in size. 6.2. Cluster Formation Under the HOLSR mechanism, in each logical topology level, (the last one possibly excepted), the mobile routers form multiple clusters upon cluster heads' invitation, which in turn can be organized into a hierarchical architecture. Unlike (flat) OLSRv2, HOLSR routers can restrict exchange of Topology Control (TC) messages within clusters, thus reducing the amount of control information that is broadcast throughout the entire network. The topology control information between clusters is exchanged via specialized HOLSR routers designated as cluster heads. The HOLSR cluster heads are selected among those higher-capacity routers. However, the choice of the cluster head is not ruled by HOLSR, it is left to the administrator of the network. Similarly, the level at which a router exists or can exist is determined and assigned administratively, and according to specific network deployment requirements. Mobile routers can be organized into clusters at different topology levels. A cluster comprises a group of mobile routers (at the same topology level) that are associated with a common cluster head. At each level, the multiple mobile routers that have been selected as cluster heads declare their status and thereby invite other routers to join their cluster by periodically sending out Cluster ID Announcement (CIA) messages. CIA messages contain two fields: cluster head, which identifies the interface address of the cluster head generating the CIA message, and distance (in hops) to that cluster head. CIA messages are sent with Time to live (TTL) = '1', i.e. they only travel one hop. When a cluster head generates a CIA message, it identifies itself within the cluster head field, with distance being 0. After reception of a CIA message, the routers in proximity to the cluster head will join that cluster, given that these routers are not part of any cluster, or that the distance to this advertized cluster head is less than the distance to another cluster head they might already be associated with. Lacharite, et al. Expires January 14, 2010 [Page 16] Internet-Draft HOLSR July 2009 Once a router joins a cluster, it begins to broadcast CIA messages, where the cluster head field contains the ID of the cluster head it is associated with, and the distance field containing the distance, in hops, from that router to the cluster head. In a nutshell, every router within a cluster, once associated with a cluster head, generates CIA messages with ID field set to cluster head ID, the distance field set to the distance from the router and its cluster head (in hops), and a TTL value of '1'. 6.2.1. Particular Case: Cluster Intersections A given router may receive CIA messages from different cluster heads, indicating that it is located in the overlapping regions of multiple clusters. In such cases, the router joins whichever cluster is closer in terms of hop count and generates CIA messages only with the ID of the cluster head chosen. There may also be scenarios where multiple routers with the same capabilities are located in the vicinity of each other. In this situation, a lower-level router may receive CIA messages with the same hop count from various cluster heads. The router will on this case attach itself to the cluster head from which it receives the first CIA and remain with that cluster head for as long as the topology does not change. It should be noted that given the random movement of mobile routers, a router might find a cluster head closer that the one to which it is currently attached. In this case, the mobile router will proceed to change its cluster and attach itself to the closest cluster head. Following this process, each router in the lowest level joins a selected cluster, and the mechanism is in turn applied at the different topology levels. 6.2.2. Cluster ID Announcement Validity Timer A built-in diagnostic feature helps ensure the robustness of the HOLSR clustering mechanism: each router registers a timeout value for the CIA messages received. Should a cluster head become inactive or move away, routers in its cluster will stop receiving the CIA messages. Eventually the CIA message timeout value will expire and cached CIA information will become invalid. At this point the mobile routers will start to process CIA messages from another cluster and join that cluster, should an opportunity present itself. If no more CIA messages are received, then the routers will behave following the OLSRv2 specifications. Lacharite, et al. Expires January 14, 2010 [Page 17] Internet-Draft HOLSR July 2009 6.3. Cluster Interaction One of the main challenges in the HOLSR hierarchical architecture is support for exchange of topology information between clusters at the same or different topology levels without introducing too much overhead. In HOLSR, a cluster head acts as a gateway through which messages from cluster members are relayed to other parts of the network. Under the HOLSR network architecture each cluster head at level i needs to advertise the membership information of routers under its hierarchy to level i+1. This is done with the use of the Hierarchical TC message. 6.3.1. Types of Hierarchical Topology Control Message A Hierarchical Topology Control (HTC) message is generated by a cluster head and used to transmit the membership information of a cluster (under this cluster head) to the higher hierarchical level routers. Three basic types of HTC messages are used: Full membership Full membership messages are periodically transmitted by a cluster head to provide information about its cluster members, including members of any lower-level clusters beneath it. Update Update HTC messages provide information with respect to cluster membership changes (i.e., the update HTC messages are used when mobile routers join or leave a cluster). Request As HTC messages carry a sequence number field, it is possible to determine whether any HTC packet loss has occurred, in which case a request for retransmission of a full membership HTC message is sent by the receiving router. In topological terms, the higher a given router is located, the more information it obtains about the network. Routers at the highest topology level possess full knowledge of all the routers in the network; consequently, the sizes of their routing tables are as large as they would be under OLSRv2. Routers at lowest topology level are limited in scope; and consequently the size of their routing tables are reduced. I.e. They set their cluster head as default gateway in their routing tables, and all traffic route requests for routers outside their cluster is routed through the cluster head; which is exactly the way it is intended to be. Lacharite, et al. Expires January 14, 2010 [Page 18] Internet-Draft HOLSR July 2009 6.3.2. HTC and TC Message Propagation Routers at each hierarchical level independently select MPRs in their respective cluster level. HTC is generated by a cluster head at level i for the level i+1, if this level exists. It is forwarded by MPRs at level i+1 within this single cluster. At each hierarchical level, TC messages are generated independently. The propagation of the TC is restricted within a cluster, unless a router is located in the overlapping regions of several clusters. Therefore, an HOLSR router's location directly determines the required scope of its knowledge of network topology: for routers located toward the center of the cluster, TC propagation is limited to the local cluster; for routers located in overlapping regions of multiple clusters, the TC message is propagated not only within the local cluster but one hop further to the neighbor routers in other clusters as well. This approach offers two main advantages: o The control message reflecting local movement is restricted within the local area, which largely reduces protocol overhead as well as routing table computation overhead o Nearby routers in different clusters at the same topology level can communicate directly without having to follow the strict clustering hierarchy, which decreases delay and reduces the load on the cluster head. 6.4. Clusters Decommission To increase robustness of the HOLSR architecture and to avoid possible network partitions, cluster heads are permitted, in very specific cases, to abandon their "head" status. If a router that was initialized as a cluster head satisfies the requirements for decommissioning, it starts to emit CIA message announcements with the distance parameter (CLUSTER_HEAD_DIST) set to '255'. Cluster members, with matching cluster head ID, receiving such a message will de-associate from that cluster head. A router that is de-associated will then be able to process CIA messages from neighbor clusters. The requirements to decommission are (i) to have the parameter C_CRITICAL_PATH set to "true" on one level/interface, and (ii) to lose all connections/links on that interface. It is up to the network administrator to determine what routers on what interfaces could cause network partition if failure occurs. A decommissioned cluster head will revive its "head" status when the interface with the C_CRITICAL_PATH set to "true" has at least one Lacharite, et al. Expires January 14, 2010 [Page 19] Internet-Draft HOLSR July 2009 link successfully reinstated. The cluster head will then publish CIA announcements with the distance parameter set to '0'. As a result, routers closer to this cluster head will re-associate with it. 6.5. HOLSR Repositories In addition to the repositories maintained by OLSRv2, HOLSR maintains the following repositories: o A Cluster Information Base. It contains one entry describing the head of the cluster to which that routers belongs, its relative distance (in hop counts) to the cluster head, and an expiry time. This repository is populated and updated upon receipt of a Cluster Identifier Announcement (CIA) message. The repository entry is timestamped with the time of the last update +. When the repository entry expires (as consequence of not receiving any CIA message for an period), the entry is deleted, and the router looses its association to its cluster head. Particular cases: * At the cluster head: Cluster ID is one-self, distance is '0', and expiry_time is 0 or ignored. * At the cluster members: Cluster Head ID is cluster head, distance is ]0, 255[, and expiry_time is > 0. o Hierarchical Topology Information Base (cluster membership). This repository is populated and updated upon receipt of Hierarchical Topology Control messages. It contains one entry for each HTC message originator (cluster head) received. Each entry is tupled with the list of member routers, the sequence number it was assigned by the cluster head, and the interface it was retrieved from. Each repository entry is timestamped with the time of the last update +. Particular cases: * At the cluster head: one of the HTC originator entry contains information about this cluster head router membership. This entry is generated by the router without reception of an HTC message. * At the cluster member routers that are not cluster heads themselves: none of the originator entries matches the router's own address. Lacharite, et al. Expires January 14, 2010 [Page 20] Internet-Draft HOLSR July 2009 6.6. HOLSR Messages HOLSR uses the Generalized MANET Packet/Message Format as defined in [RFC5444], and adds 2 new message types and 4 new TLVs, as described below. 6.6.1. CIA Messages At each level, the multiple mobile routers that have been defined to become cluster heads declare their status and invite other routers to join their cluster by periodically sending out Cluster ID Announcement (CIA) messages. CIA messages MUST NOT be forwarded, as their expected recipients are the immediate neighbors of the emitting router(s). CIA messages MUST contain the following 2 TLV messages: o CLUSTER_HEAD_ID message TLV identifying the interface address of the cluster head generating the CIA message o CLUSTER_HEAD_DIST message TLV specifying the distance in hops to that cluster head. There are 3 particular cases for CLUSTER_HEAD_DIST values; * CLUSTER_HEAD_DIST = '0': Identifies and is generated by the cluster head. * CLUSTER_HEAD_DIST is '255': Cluster decommission message generated by the cluster head first, and consequently by its member routers. * CLUSTER_HEAD_DIST is > '0' and < '255': Generated by routers associating with the cluster head, and which are not themselves cluster heads. CIA messages MAY contain the following 2 TLV messages: o VALIDITY_TIME message TLV as specified in [RFC5497], representing CIA_HOLD_TIME for the transmitting MANET interface. The options included in time in [RFC5497], for representing zero and infinite time MUST NOT be used. o INTERVAL_TIME message TLV as specified in [RFC5497], representing CIA_INTERVAL for the transmitting MANET interface. The options included in time in [RFC5497], for representing zero and infinite time MUST NOT be used. Lacharite, et al. Expires January 14, 2010 [Page 21] Internet-Draft HOLSR July 2009 6.6.1.1. CIA Message TLVs In a CIA message, a router must include a single CLUSTER_HEAD_ID message TLV and a single CLUSTER_HEAD_DIST, as specified in Table 1. +-------------------+--------+--------------------------------------+ | Type | Value | Value | | | Length | | +-------------------+--------+--------------------------------------+ | CLUSTER_HEAD_ID | 1 | Specifies the cluster head ID | | | octet | selected by this router (generator | | | | of the CIA message) | | CLUSTER_HEAD_DIST | 1 | Specifies the distance, in hops, | | | octet | between the cluster head and this | | | | router (generator of the CIA | | | | message) | +-------------------+--------+--------------------------------------+ Table 1 6.6.2. HTC Messages A Hierarchical TC (HTC) message is used to transmit membership information of a cluster to higher hierarchical level routers. There are 3 basic types of HTC messages: o FULL_MEMBERSHIP Full membership HTC messages are periodically transmitted by a cluster head to provide information about its cluster members, including members of any lower-level clusters beneath it. o UPDATE Update HTC messages provide information with respect to cluster membership changes (i.e., the update HTC messages are used when mobile routers join or leave a cluster). As HTC messages carry a sequence number field, it is possible to determine whether any HTC packet loss has occurred, in which case a request for retransmission of a full membership HTC message is sent by the receiving router. HTC forwarding is enabled by MPRs, and is restricted within a cluster. o REQUEST Request HTC messages are used to request retransmission of full membership HTC messages. An HTC message MUST contain an HTC message type TLV: Lacharite, et al. Expires January 14, 2010 [Page 22] Internet-Draft HOLSR July 2009 o HTC_MSG_TYPE message TLV that is one of FULL_MEMBERSHIP, UPDATE or REQUEST. An HTC message of type FULL_MEMBERSHIP or UPDATE MUST contain a sequence number message TLV. REQUEST type message do not need to include this TLV: o HTC_SEQ_NUM message TLV, specified by an incrementing counter on the HTC message generation at the cluster head router. 6.6.2.1. HTC Message TLVs TLV messages used within the HTC messages: +--------------+--------+-------------------------------------------+ | Type | Value | Value | | | Length | | +--------------+--------+-------------------------------------------+ | HTC_MSG_TYPE | 1 | Specifies the type of HTC message | | | octet | | | HTC_SEQ_NUM | 2 | Specifies the sequence number of the HTC | | | octets | generator counter at the cluster head | | | | router | +--------------+--------+-------------------------------------------+ Table 2 6.7. HOLSR Algorithm 6.7.1. Processing and Broadcasting CIA Message A CIA message is periodically generated and sent by a router that has been configured as cluster head. A CIA message generated from a cluster head has its distance value set to 0. Routers that join the cluster identified by the cluster head also generate CIA messages periodically. CIA message generated from these routers are sent with their distance value equal to the hop count between themselves and the cluster head. When a router receives a CIA message, three cases are possible: o the router does not yet belong to a cluster: it joins the cluster by (i) populating its cluster head repository and (ii) starting to broadcast CIA messages, inviting other routers to join this cluster. The cluster head distance value stored in its repository is the value received from the CIA message processed plus one. Lacharite, et al. Expires January 14, 2010 [Page 23] Internet-Draft HOLSR July 2009 o the router already belongs to a cluster: it checks if its distance to the cluster head indicated in the received CIA message is smaller than its distance to its current cluster head. If yes, it joins the new cluster, updates its cluster head repository and starts broadcasting CIA messages with the newly selected cluster ID (and distance set accordingly). Otherwise, it continues to broadcast CIA messages with the distance and cluster ID values from its repository. o the router receives a decommission message (CLUSTER_HEAD_DIST = 255). If the router's cluster head matches the cluster's ID from the CIA message, it will de-associate from that cluster head. The router will forward that decommission message until it associates itself with another cluster head. 6.7.2. Processing and Forwarding HTC Message Cluster heads generate different types of HTC messages. For all message types, only one sequence number is stored. Every time an HTC message is generated, the sequence number is incremented and included in that message (regardless of its type). Cluster heads generate HTC messages of type FULL_MEMBERSHIP and UPDATE. Cluster members generate HTC messages of type REQUEST. Concerning HTC messages, we distinguish: o a HTC message with full membership that is periodically generated and sent by a cluster head of level i to the level i+1. This message contains a sequence number that is incremented, as well as the list of routers in the cluster membership (hierarchical topology information base) repository. o an update HTC message is generated by a cluster head of level i to notify cluster membership changes to level i+1. This message contains a sequence number that is incremented, as well as the new routers having joined the cluster and the old routers having left. It is computed from the cluster membership repository, after addition or removal of a member router entry. o a request HTC message is generated by a router that has received a HTC message with a sequence number higher than its last one plus one. This router asks for transmission of a full membership message. Upon receipt of a full membership HTC message, a router checks the Lacharite, et al. Expires January 14, 2010 [Page 24] Internet-Draft HOLSR July 2009 received sequence number: o if it is smaller or equal, the message is silently discarded. o otherwise, the received membership information replaces the old one in the cluster membership repository. The message is forwarded according to the OLSRv2 forwarding rule. Upon receipt of an update HTC message, a router checks the received sequence number: o if it is smaller or equal, the message is silently discarded. o if it is greater by 1 than the sequence number maintained in the repository, the received membership information is used to update the information in the cluster membership repository. The message is forwarded according to OLSRv2 forwarding rule. o otherwise, if it is greater by more than 1, a request HTC message is generated and sent to get the missing HTC messages. Upon receipt of a request HTC message, a router checks if it is the originator of the HTC message for which a request is made (usually the originator router is a cluster head): o if yes, it sends a full membership message back to the sender. o otherwise, this message is forwarded according to OLSR forwarding rule. 6.7.3. Cluster Intersection Handling Routers located within the intersecting domain of 2 or more clusters are allowed to communicate directly (by-passing their respective cluster heads) by setting the C_INTER_DEPTH parameter to a value greater than 0. In the intersection domain, routers SHOULD process all HELLO and TC messages, even those not pertaining to their own cluster Id. The use of a neighbor cluster's HELLO and TC message information to build up the routing tables is constrained by the C_INTER_DEPTH parameter. If C_INTER_DEPTH is greater than 1, an MPR in the intersecting domain is allowed to forward a TC message originating from a router not pertaining to its own cluster. Lacharite, et al. Expires January 14, 2010 [Page 25] Internet-Draft HOLSR July 2009 Example where Clusters A and B have routers in an intersection vicinity. _.--------------. ,--'' `---. ,' `. ( .A---------------------B. ) `./ \,' `---. _.--' | `--------------'' | |cluster A cluster B | _|----------. _.----------.| ,-'' | A2 ,-''--. |--. ,' A1 | ,' `. B1 B2| `. / AH .'A6. \ | \ ( A3..+ ( `>B7......B3 BH ) \ A4 \`-.A7' / B4 / `. A5 `. ,' B5 ,' '--. '--..-' B6 _.-' `----------'' `----------'' Figure 3 - Intersecting Clusters Example Clusters A and B intersect because routers in the intersection area (A6, A7, B7) are able to hear CIA announcements from 2 different cluster heads (AH and BH). If C_INTER_DEPTH is set to 1, then the direct communication between A6 <--> B7, and A7 <--> B7 is enabled. If routers A7 wants to communicate with router B3, it will have to do so going through its cluster head AH (A7 -> A3 -> AH -> BH -> B3). If C_INTER_DEPTH is set to 2, then router A7 is allowed to communicate directly with router B3 (bypassing its cluster head) by using the path provided by router B7; Hence A7 -> B7 -> B3. 7. Proposed Values for Parameters This section lists the parameters and their default proposed values used in the specification of the protocol. 7.1. Message Intervals Parameter Defaults 7.1.1. CIA Messages By default these parameters are set to be identical to those used within NHDP [I-D.ietf-manet-nhdp] for HELLO messages and intervals. Lacharite, et al. Expires January 14, 2010 [Page 26] Internet-Draft HOLSR July 2009 o CIA INTERVAL = 2 seconds o CIA_MIN_INTERVAL = CIA_INTERVAL/4 = 0.5 seconds 7.1.2. HTC Messages By default these parameters are set to be identical to those used within OLSRv2 [I-D.ietf-manet-olsrv2] for TC messages and intervals. o HTC_INTERVAL = 5 seconds o HTC_MIN_INTERVAL = HTC_INTERVAL/4 = 1.25 seconds 7.2. Information Validity Times Parameters 7.2.1. CIA Messages o CIA_HOLD_TIME = 3 x CIA_INTERVAL 7.2.2. HTC Messages Since HTC validity times parameter refer to TC parameters, their default parameters SHOULD use the same values at the ones used in OLSRv2 [I-D.ietf-manet-olsrv2]. o T_HOLD_TIME = 3 x TC_INTERVAL o A_HOLD_TIME = T_HOLD_TIME o RX_HOLD_TIME = 30 seconds o P_HOLD_TIME = 30 seconds o F_HOLD_TIME = 30 seconds 7.3. Cluster Intersection Depth o C_INTER_DEPTH = 1 7.4. Cluster Critical Path o C_CRITICAL_PATH = 0 (false) 8. Contributors This specification is the result of the joint efforts of the following contributors, listed alphabetically. Lacharite, et al. Expires January 14, 2010 [Page 27] Internet-Draft HOLSR July 2009 o Thomas Heide Clausen, LIX, France, o Ying Ge, CRC, Canada, o Yannick Lacharite, CRC, Canada o Pascale Minet, INRIA, France, o Maoyu Wang, CRC, Canada, 9. Acknowledgements The authors would like to acknowledge the authors of OLSRv2 for their guidance in the production of this specification. We want to acknowledge the work done by Ying Ge (CRC), who implemented a version HOLSR for OLSRv1 for her numerous inputs, reviews and comments. Also the authors would like to gratefully acknowledge the following people for intense technical discussions, early reviews and comments on the specification and its components (listed alphabetically): Ulrich Herberg (LIX), Louise Lamont (CRC), Henning Rogge (FGAN), and the entire IETF MANET working group. This document was written with the xml2rfc tool described in [RFC2629]. 10. IANA Considerations 10.1. Message Types This specification defines two message types, which must be allocated from the "Assigned Message Types" repository of [RFC5444] with assignment as specified in Table 3. +------+------+---------------------------------------+ | Name | Type | Description | +------+------+---------------------------------------+ | CIA | TBD | Cluster ID Announcement message | | HTC | TBD | Hierarchical Topology Control message | +------+------+---------------------------------------+ Table 3 Lacharite, et al. Expires January 14, 2010 [Page 28] Internet-Draft HOLSR July 2009 10.2. TLV Types This specification defines four message TLV types, which must be allocated from the "Message TLV Types" namespace defined in [RFC5444]. IANA are requested to make allocations in the 8-127 range for these types. This will create four new type extension registries with assignments as specified in Table 4. Specifications of these TLVs are in Section 6.6.1 and Section 6.6.2. +-------------------+------+-----------+----------------------------+ | Name | Type | Type | Description | | | | Extension | | +-------------------+------+-----------+----------------------------+ | CLUSTER_HEAD_ID | TBD | 0 | Specifies the cluster head | | | | | ID selected by this router | | | | | (generator of the CIA | | | | | message) | | | | 1-255 | RESERVED | | CLUSTER_HEAD_DIST | TBD | 0 | Specifies the distance, in | | | | | hops, between the cluster | | | | | head and this router | | | | | (generator of the CIA | | | | | message) | | | | 1-255 | RESERVED | | HTC_MSG_TYPE | TBD | 0 | Specifies the type of HTC | | | | | message | | | | 1-255 | RESERVED | | HTC_MSG_NUM | TBD | 0 | Specifies the sequence | | | | | number of the HTC | | | | | generator counter at the | | | | | cluster head router | | | | 1-255 | RESERVED | +-------------------+------+-----------+----------------------------+ Table 4 10.3. HTC_MSG_TYPE Values The values which HTC_MSG_TYPE can use are the following: o FULL_MEMBERSHIP = 0 o UPDATE = 1 o REQUEST = 2 Lacharite, et al. Expires January 14, 2010 [Page 29] Internet-Draft HOLSR July 2009 11. Security Considerations All drafts are required to have a security considerations section. 12. References 12.1. Normative References [I-D.ietf-manet-olsrv2] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-09 (work in progress), July 2009. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter Considerations in Mobile Ad Hoc Networks (MANETs)", RFC 5148, February 2008. [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format", RFC 5444, February 2009. [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, March 2009. 12.2. Informative References [I-D.ietf-manet-nhdp] Clausen, T., Dearlove, C., and J. Dean, "MANET Neighborhood Discovery Protocol (NHDP)", draft-ietf-manet-nhdp-10 (work in progress), July 2009. [RFC2629] Rose, M., "Writing I-Ds and RFCs using XML", RFC 2629, June 1999. [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. Appendix A. Example of Data Transfer using Clusters This appendix gives an example of data transfer in a hierarchical network with three levels. It reuses the figure presented in the Protocol Overview (Section 4). Lacharite, et al. Expires January 14, 2010 [Page 30] Internet-Draft HOLSR July 2009 +--- ---+ _.--------------------------. L _.----'' `------. e ,-'' `--. v ,' `. e ( E.f.....................F.r ) l `. | | ,' `--. | | _.-' 3 `------. | |_.----'' `---+----------------------'' +--- | Overall Cluster | ---+ _.----------| _.---+------. L ,-'' |`--. ,-'' ,'FH.r. `--. e / | \ / ,' '-. \ v ( A.a.............EH.f ) ( C.p..........D.u ) e \| | / \ | | / l |--. |_.-' `--.| |.-' | `----------'| |----------''| 2 | Cluster E | ,------+. Cluster F | | ,---+-------.,-' | `-. | +--- | ,-' | B1.h,'`-. C1.m CH.p `. | ---+ | ,----,'---. BH.f / C4.k. \,----+----. L ,+' / `-. ; \ ,-': | `-. e / | ( A3.d \B2.g| B5.j ) C2.o /C6.s| | D1.v\ v / AH.a \ B4.e\ : C5.l/ / ; DH.u \ e ( `. ) \ ,' (D4.q/ ) l \ A1.b '-. / B3.i`.,-' \ ,' D2.w / \ A2.c `---+-------''-. C3.n ,-\ D3.t / 1 `-. ,-'Cluster B `-------' `-. ,-' `---------' Cluster C `---------' +--- Cluster A Cluster D ---+ Figure 4 - Data Transfer using Hierarchical Structure Routing information is updated by all the routers in a given cluster. Thus, communication between routers in a cluster is achieved via the routing information in the routing tables. For data transmissions outside the cluster, the cluster heads are used as gateways. To describe the communication between clusters, lets look at an example network with 3 levels. First, lets specify the terminology of the example. Routers are represented by a "." followed by a lowercase letter. Figure 4 contains 23 routers labeled from ".a" to ".w". Prefixed to the router id is a capital character followed by a number, or an H. It defines the cluster membership of a router and its cluster head status. In the case where a router is involved in many clusters, on many levels (because it contains multiple interfaces), the capital Lacharite, et al. Expires January 14, 2010 [Page 31] Internet-Draft HOLSR July 2009 letter references the cluster membership from the lowest level. For example "AH.a" denotes router "a" which is the cluster head "H" of cluster "A". Similarly, "D3.t" denotes router "t", the 3rd router member of cluster D, and not a cluster head. On level 2, "C.p" is member of cluster F, but it is also the same router as level 1 "CH.p" which is the cluster head of cluster C. A bit more complex, router "BH.f" is the cluster head of cluster B at level 1, it is the same router as "EH.f" which is a cluster head of cluster E at level 2, and it is also the same router as "E.f" which is a member of the overall cluster at level 3. Hence for the purpose of our example, router .f has 3 interfaces each one participating at a different level of the hierarchy. Additionally, in the text description we denote levels with the prefix , e.g. applies to level 1. Now, the example: Starting from the base topology level 1, when a router .b (l1-A1.b) of cluster A wants to transmit data to router .t (l1-D3.t) from another cluster D; it will route through the hierarchy levels instead of communicating directly at level 1. Here is the actual path taken by the data. Router l1-A1.b first sends its traffic to its cluster head router AH.a (l1-AH.a) -- On the next topology level 2, cluster head l1-AH.a corresponds to l2-A.a and is a member of Cluster E -- Router l2-A.a transmits in turn to its cluster head router l2-EH.f -- which corresponds to l3-E.f on level 3 -- Router l3-E.f transmits to its neighbor l3-F.r -- equivalent to l2- FH.r on level 2 -- l2-FH.r forwards to l2-D.u -- cluster head of level one l1-DH.u -- Finally l1-DH.u transmits data to its destination l1-D3.t. In summary, the data path can be represented by: l1-D3.t --> l1-AH.a == l2-A.a --> l2-EH.f == l3-E.f --> l3-F.r == l2-FH.r --> l2-D.u == l1-DH.u --> l1-D3.t. Or, abstracting the level/cluster information, traffic traversed 5 hops: .t --> .a --> .f --> .r --> .u --> .t. As we trace the path traveled by the data packets, we see that the cluster head is always used as the gateway by its member routers at lower hierarchical levels, for destinations outside the cluster. The rules governing the three levels network can be scaled to a network with additional topology levels. Normally, data transmission between clusters follows clustering hierarchy described above. However, a different transmission path is used when transmitting data between neighboring routers that belong to different clusters at the same topology level; in this situation, the cluster head is not used as a gateway to relay the information to the destination router in a different cluster. Instead, data is sent to the neighbor router directly since TC messages are propagated one hop further on cluster edges to neighbor routers in other clusters. The depth of the routing infiltration at the edge of clusters is configurable via the C_INTER_DEPTH parameter. With this strategy the Lacharite, et al. Expires January 14, 2010 [Page 32] Internet-Draft HOLSR July 2009 HOLSR makes efficient use of the high-capacity routers without overloading them. Appendix B. Example of Cluster Decommission Handling This appendix gives an example of cluster decommission handling in a hierarchical network with three levels. It reuses the figure presented in the Protocol Overview (Section 4). In this example, node .f has an interface at level 3 that is set to C_CRITICAL_PATH = '1' (true). +--- ---+ _.-------\ \----------. L _.----'' `------. e ,-'' \ \ `--. v ,' `. e ( _.f......\ \......F.r ) L `. | | ,' `--. | \ \ | _.-' 3 `------. | |_.----'' `---+------------\ \-'' +--- | Overall Cluster | ---+ | _.---+------. L | ,-'' ,'FH.r. `--. e | / ,' '-. \ v _.a............._.f ( C.p..........D.u ) e | <--CIA-1--> | \ | | / l | | `--.| |.-' | | |----------''| 2 | | ,------+. Cluster F | | | ,-' | `-. | +--- | | _.h,' C1.m CH.p `. | ---+ | _.f / C4.k \,----+----. L | <--CIA-1-->; ,-': | `-. e | _.d _.g| _.j C2.o /C6.s| | D1.v\ v _.a _.e : C5.l / ; DH.u \ e <--CIA-1--> \ (D4.q/ ) l _.b _.i`. \ ,' D2.w / _.c '-. C3.n ,-\ D3.t / 1 `-------' `-. ,-' Cluster C `---------' +--- Cluster D ---+ Figure 5 - Cluster Head Decommissioning When the link on layer 3 in-between router .f and .r is broken, the decommission requirement on router .f is met. Hence, router .f stops Lacharite, et al. Expires January 14, 2010 [Page 33] Internet-Draft HOLSR July 2009 being a cluster head on layer 2 and layer 1, and starts to generate CIA decommission message (CIA-1 in the example, as shown in Figure 5). The immediate impact, is that we see clusters A, B and E de- associate completely. De-associated routers will now process and generate CIA messages from cluster C. +--- ---+ _.-------\ \----------. L _.----'' `------. e ,-'' \ \ `--. v ,' `. e ( C11.f......\ \......F.r ) L `. | | ,' `--. | \ \ | _.-' 3 `------. | |_.----'' `---+------------\ \-'' +--- | Overall Cluster | ---+ | _.---+------. L | ,-'' ,'FH.r. `--. e | / ,' '-. \ v | ( C.p..........D.u ) e | \ | | / l | `--.| |.-' | |----------''| 2 _,,...+----------....__ | Cluster F | _,,-'' | ``+.._ | +--- ,-' | C8.h C1.m CH.p`-. | ---+ ,-' _,.........-C11.f C4.k `,=---+----. L / / ,-' \ | `-. e | | C13.d C10.g C7.j C2.o /C6.s | | D1.v\ v '.C16.a C12.e C5.l / .' DH.u \ e `. (D4.q ,' ) l C15.b C9.i \ ,' D2.w / `-._C14.c C3.n _.-' D3.t / 1 ``-...__ _,,.,-'' `-. ,-' `''-----------''' `---------' +--- Cluster C Cluster D ---+ Figure 6 - Updated Architecture As shown Figure 6, de-associated routers end up joining cluster C, which now contains all routers from previous clusters A, B, and E. Routers .a and .f still are still linked via their second interface (higher capabability), but their multiple interfaces are now handled by OLSRv2 (no more HTC messaging required from routers .a and .f since they are no longer cluster heads). Note. From this example, it can also be shown that routers .f and .r Lacharite, et al. Expires January 14, 2010 [Page 34] Internet-Draft HOLSR July 2009 at level 1 shall not be both set with parameter C_CRITICAL_PATH = 1. Doing so, if the link in-between these 2 routers fails, all the network cluster heads would be decommission. It it the responsibility of the network administrator to ensure that the C_CRITICAL_PATH parameter gets set properly on strategically selected routers. Appendix C. Packet and Message Layout This appendix illustrates the translation from the abstract descriptions of packets employed in the protocol specification, and the bit-layout packets actually exchanged between MANET routers. C.1. Packet and Message Options The basic layout of an HOLSR packet, message body, address block, TLV block, and TLV is as described in [RFC5444], allowing all options. C.2. Example CIA Message An example CIA message, using IPv4 (four octet) addresses is as follows. The overall message length is 37 octets. The message has the mhasorig, mhashoplimit, mhashopcount, and mhasseqnum flags of its four-bit flags field set (value 15), and hence includes an Originator Address, a Hop Limit, a Hop Count, and a Message Sequence Number (which is type independent). Its four-bit message Address Length field has value 3, indicating that the message uses IPv4 address. Thus, the overall message flags octet is of value 243. The message has a Message TLV block with content length 16 octets, containing four message TLVs. These TLVs represent message validity time, message interval time, CIA Cluster Head Id, and CIA Cluster Head Distance. Each message TLV has the thasvalue flag of its flag octet set (value 16), and hence contains a Value field, with preceding Value Length 1 octet. The message has one Address Block. It contains the interface address of the cluster head. The first octet indicates that it contains one address. The flags octet has the ahashead flag set indicating it has a head. Its head length is 4, this is equal to the address length, it thus has no mid section. This Address Block has no TLVs (TLV block content length is 0 octets). Lacharite, et al. Expires January 14, 2010 [Page 35] Internet-Draft HOLSR July 2009 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CIA |1 1 1 1 0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Limit | Hop Count | Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0| VALIDITY_TIME |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Value | CLUSTER_HD_ID |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Value | CLUSTER_HD_DST|0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Value |0 0 0 0 0 0 0 1|1 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 1 0 0| Head | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Head (cont) | +-+-+-+-+-+-+-+-+ C.3. Example HTC Message An example HTC message, using IPv4 (four octet) addresses, is as follows. The overall message length is 48 octets. The message has the mhasorig, mhashoplimit, mhashopcount, and mhasseqnum flags of its four-bit flags field set (value 15), and hence includes an Originator Address, a Hop Limit, a Hop Count, and a Message Sequence Number (which is type independent). Its four-bit message Address Length field has value 3, indicating that the message uses IPv4 address. Thus, the overall message flags octet is of value 243. The message has a Message TLV block with content length 17 octets containing four TLVs. The first two TLVs are validity and interval times as for the CIA message above. The third TLV is the HTC message type. The fourth TLV is the HTC sequence number TLV used to carry the 2 octet HTC_SEQ_NUM. Each message TLV has the thasvalue flag of its flag octet set (value 16), and hence contains a Value field. First three TLVs have a preceding Value Length 1 octet, and the last TLV has a preceding Value Length 2 octets. The message has one Address Block. It contains 6 cluster members' addresses. The first octet indicates that it contains 6 addresses. The flag octet has the ahashead flag set indicating it has a head. Its head length is 2 octets, hence mid sections length is two octets. Lacharite, et al. Expires January 14, 2010 [Page 36] Internet-Draft HOLSR July 2009 This Address Block has no TLVs (TLV block content length 0 octets). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HTC |1 1 1 1 0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Limit | Hop Count | Message Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1| VALIDITY_TIME |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Value | HTC_MSG_TYPE |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Value | HTC_SEQ_NUM |0 0 0 1 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 1 0| Value |0 0 0 0 0 1 1 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0| Head | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid | Mid | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid | Mid | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid | Mid | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Authors' Addresses Yannick Lacharite Communications Research Centre Canada 3701 Carling Avenue Ottawa, Ontario K2H 8S2 Canada Phone: +1 613 998 1207 Fax: Email: yannick.lacharite@crc.gc.ca URI: Lacharite, et al. Expires January 14, 2010 [Page 37] Internet-Draft HOLSR July 2009 Maoyu Wang Communications Research Centre Canada 3701 Carling Avenue Ottawa, Ontario K2H 8S2 Canada Phone: +1 613 991 1671 Fax: Email: maoyu.wang@crc.gc.ca URI: Pascale Minet INRIA Rocquencourt, 78153 Le Chesnay Cedex France Phone: +33 1 3963 5233 Fax: Email: pascale.minet@inria.fr URI: http://hipercom.inria.fr/~minet Thomas Clausen LIX, Ecole polytechnique 92128 Palaiseau Cedex France Phone: +33 6 6058 9349 Fax: Email: t.clausen@computer.org URI: http://www.thomasclausen.org Lacharite, et al. Expires January 14, 2010 [Page 38]