MANET Autoconfiguration (AUTOCONF) I. Chakeres Internet-Draft Boeing Expires: April 6, 2007 J. Macker Naval Research Laboratory T. Clausen LIX, Ecole Polytechnique October 3, 2006 Mobile Ad hoc Network Architecture draft-chakeres-manet-arch-01 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of 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 April 6, 2007. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document discusses Mobile Ad hoc NETworks (MANETs). It introduces basic MANET terms, characteristics, and challenges. This document also defines several MANET entities and architectural concepts. Chakeres, et al. Expires April 6, 2007 [Page 1] Internet-Draft MANET Architecture October 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. MANET Architectural Terms . . . . . . . . . . . . . . . . . . 4 4. MANET Motivation Discussion . . . . . . . . . . . . . . . . . 5 5. Qualities - Wireless, Mobile, Ad hoc . . . . . . . . . . . . . 6 6. Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6.1. Semi-Broadcast Interface . . . . . . . . . . . . . . . . . 7 6.2. Fuzzy Neighbor Relationship & Extended Neighborhood . . . 8 6.3. MANET Membership . . . . . . . . . . . . . . . . . . . . . 9 7. Other Important Discussion . . . . . . . . . . . . . . . . . . 10 7.1. MANETs' Place in the Network Stack . . . . . . . . . . . . 10 7.2. Cross Layering . . . . . . . . . . . . . . . . . . . . . . 10 8. Deployment Taxonomy . . . . . . . . . . . . . . . . . . . . . 11 8.1. Service Availability . . . . . . . . . . . . . . . . . . . 11 8.2. Number of Peer MANET Routers . . . . . . . . . . . . . . . 11 8.3. Example Deployments . . . . . . . . . . . . . . . . . . . 12 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 13 12. Informative References . . . . . . . . . . . . . . . . . . . . 14 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16 Intellectual Property and Copyright Statements . . . . . . . . . . 17 Chakeres, et al. Expires April 6, 2007 [Page 2] Internet-Draft MANET Architecture October 2006 1. Introduction A Mobile Ad hoc NETwork (MANET) consists of a loosely connected set of MANET routers. These routers organize and maintain a routing structure among themselves. These routers often communicate over wireless links and are often mobile. MANETs' characteristics create challenges in several areas, and often require protocol extensions or new MANET protocols altogether. This document is focused on IP networking, though many of MANETs' concepts and issues span the protocol stack. This document is meant to complement [RFC2501] in describing and defining MANET. 2. Terminology Much of the terminology in this document was borrowed from existing documents, to list a few [RFC1812], [RFC2328], [RFC2453], [RFC2460], [RFC2461], [RFC3513], [RFC3753], [I-D.thaler-autoconf-multisubnet- manets], [I-D.templin-autoconf-dhcp], and [I-D.ietf-ipv6-2461bis]. Note that the original text for the terms is often modified, though we have attempted to maintain the same meaning. In the future, terms defined elsewhere will likely be cited instead of included. This document employs the following definitions: Node any device (router or host) that implements IP. Router a node that forwards IP packets not explicitly addressed to itself. Host any node that is not a router, i.e. it does not forward packets addressed to others. Link A communications facility at a layer below IP, over which nodes exchange IP packets directly without decrementing IP TTL (Hop Limit). Asymmetric Reachability A link where non-reflexive and/or non-transitive reachability is part of normal operation. Non-reflexive reachability means packets from X reach Y but packets from Y don't reach X. Non- Chakeres, et al. Expires April 6, 2007 [Page 3] Internet-Draft MANET Architecture October 2006 transitive reachability means packets from X reach Y, and packets from Y reach Z, but packets from X don't reach Z. Many radio/ wireless interfaces exhibit these properties. Neighbor If node X can directly exchange IP packets with node Y, then node Y is node X's neighbor. Packet reception characteristics are often used to assist devices in determining the quality of neighbors' communication. Interface A node's point of attachment to a communication link. Broadcast Interface An interface supporting many attached nodes, together with the capability to address a single link layer message to all of the attached nodes (broadcast). The set of nodes receiving a given physical broadcast message are the neighbors of the node originating the message. Full-Broadcast Interface (FBI) A broadcast interface with reflexive and transitive reachability. All nodes on the interface can send and receive IP packets directly, all nodes are symmetric neighbors. An Ethernet segment is an example of a FBI. Semi-Broadcast Interface (SBI) A broadcast interface that may exhibit non-reflexive and/or non- transitive reachability. A FBI is a special case of SBI. Multiple access wireless radio interfaces are often SBI. Site a set of one or more links. Flooding The process of forwarding information to as many MANET routers as possible. 3. MANET Architectural Terms In MANET there are two important entities. We define the following entities: MANET Router a node that engages in a MANET routing protocol. Chakeres, et al. Expires April 6, 2007 [Page 4] Internet-Draft MANET Architecture October 2006 MANET Border Router (MBR) a MANET router that also participates in multiple routing regions, and often multiple routing protocols. A MBR forms a border between its multiple routing regions. A MBR is responsible for presenting a consistent picture of the nodes reachable through itself to each routing region. A MBR chooses the routing information to propagate between different regions. In MANET there are several architectural scopes. We define the following scopes: MANET Neighbors a set of MANET routers that is reachable in one hop. MANET Neighborhood a set of MANET routers that is reachable in a few hops, generally two hops. These routers often have a large number of common neighbors and often compete for shared wireless resources. MANET a set of MANET routers that is reachable via multiple IP hops. A MANET is smaller than or equal to a site. If a link forms between two previously separated MANET routers or MANETs, the two MANETs will merge to form a single larger MANET. Similarly, if a critical link between two MANET routers is lost the MANET will partition into two MANETs. When discussing MANETs' connectivity to other networks, like the Internet, a MANET is bounded by MANET border routers. That is a MANETs' MBR form a border between a MANET and other routing regions. 4. MANET Motivation Discussion The Internet Protocol (IP) core design tenets -- connectionless networking and packet-based forwarding -- are ideally suited for use in highly dynamic contexts, such as MANETs. Yet, some additional functionality is required to meet the unique challenges and opportunities present in MANETs. The initial motivation for MANETs was called Packet Radio (PR) networking [FL01]. In PR, each router is equipped with a single SBI. This is the simplest MANET router configuration. Each router may be mobile, and the routers may be or may become spatially distributed such that all routers cannot communicate directly. That is, two routers might require one or more other intermediate routers to forward (route) packets on their behalf. In the example shown in Chakeres, et al. Expires April 6, 2007 [Page 5] Internet-Draft MANET Architecture October 2006 Figure 1, for RT1 to send packets to RT3, the intermediary RT2 must relay the packets. This implies that RT2 must receive the packet from RT1 on its interface and determine that it must retransmit the packet over the same interface as the one where the packet was received, in order for the packet to reach RT3. This example also illustrates how SBIs differ from FBIs: from the point of view of RT2, both RT1 and RT3 are neighbors, whereas RT1 and RT3 are not themselves neighbors with one another. Communication Range <~~~~~~+~~~~~~> <~~~~~~+~~~~~~> Single | <~~~~~~+~~~~~~> | SBI +-|-+ +-|-+ +-|-+ |RT1| |RT2| |RT3| +---+ +---+ +---+ Figure 1: Basic MANET Network In addition to addressing nodes' asymmetric reachability other challenges exist. In PR networks, shared wireless resources result in interdependence between nearby nodes, and these nodes often communicate directly or indirectly. The dynamic wireless interface characteristics and node mobility often manifest as frequent network topology changes. PR networks also lead to several other architecture related challenges. One challenge was to attach these PR networks to other networks, especially fixed networks like the ARPANET. Another related challenge was how to deal with the large disparity between different node and interface characteristics. These PR network challenges helped stimulate the Internet Protocol; an architecture based on connectionless networking and packet-based forwarding that enables interconnection of heterogeneous devices over heterogeneous interfaces. 5. Qualities - Wireless, Mobile, Ad hoc In MANET several qualities impact protocol design. The most fundamental qualities are wireless interface characteristics, mobility, and ad hoc interaction. Wireless interfaces exhibit challenging characteristics when compared with wired interfaces. Many protocols (e.g. neighbor discovery) do Chakeres, et al. Expires April 6, 2007 [Page 6] Internet-Draft MANET Architecture October 2006 not operate in wireless networks with asymmetric reachability. Wireless interfaces also exhibit time varying performance that can significantly impact local communication. Mobility also exacerbates wireless communication issues, making it difficult to attain, establish, and maintain relationships between nodes. Ad hoc networking further compounds problems by allowing nodes to join and leave the network, or even form new networks, at will. 6. Challenges MANETs characteristics result in many challenges. These challenges reveal themselves in many forms, and MANET specific protocols must often be developed. 6.1. Semi-Broadcast Interface Given a wireless SBI (with non-transitive and non-reflexive properties) and spatially distributed nodes, each node may have a different unique partial view of the MANET. That is, each node may have a different set of adjacent nodes. Communication Range <~~~~~~+~~~~~~> <~~~~~~+~~~~~~> Single | <~~~~~~+~~~~~~> | SBI +-|-+ +-|-+ +-|-+ |RT1| |RT2| |RT3| +---+ +---+ +---+ RT1 RT2 RT3 ------------------------- Neighbors * RT2 RT1 RT2 * RT3 Figure 2: Semi-Broadcast Interface (SBI) Neighbors The possibly unique set of adjacent nodes in each node often requires nodes to forward packets out the same wireless interface as the one over which they were received. Topologically, this act of forwarding out the same interface causes a packet to reach a possibly different set of nodes by traversing the wireless communication medium in a new location. An example is provided in Figure 2, where each router is Chakeres, et al. Expires April 6, 2007 [Page 7] Internet-Draft MANET Architecture October 2006 capable of reaching a different set of routers. The act of forwarding packets out of the same interface as the one over which they were received often results in duplicate IP packets being received at nodes with more than one neighbor, while also reaching a new subset of nodes. 6.2. Fuzzy Neighbor Relationship & Extended Neighborhood Defining the process of determining a neighbor's existence, continued existence, and loss of existence in MANET is arguably the fundamental challenge in MANETs. Neighbors are hard to define due to the expected interface characteristics: non-transitive, non-reflexive, time varying, and other wireless properties. Historically, two nodes are either neighbors or not neighbors and several simple mechanisms have been used to determine a neighbor relationship: single packet reception, acceptable loss rates, and simple handshakes. In wireless networks the types of neighbor relationships expand, as do the mechanisms to detect the state of such relationships. In wireless networks, nodes may often have non-reflexive (also often seen called unidirectional or asymmetric) communication links. Wireless networks also experience significant time varying packet delivery, so simple loss rates may not be sufficient to define a neighbor relationship. Similarly, as nodes move in relationship to each other past loss rates may not reflect future communication capabilities. In wireless systems there is often a lot of communication connectivty between nearby nodes. These nodes form an extended neighbor relationships that is referred to as a neighborhood. A neighborhood is typically composed of several nodes, where each node densely connected to other nodes. These complex neighbor relationships do not sit well with certain Internet Protocols designed assuming an Ethernet like model to communication links (reflexive, transitive, and stable). Given the unknown neighbor relationships, the addressing model often associated with a Ethernet link is not valid. For example, in an Ethernet network routers are often told that a particular range of addresses are directly reachable. In MANETs' a node often cannot make assumptions that a particular set of addressable nodes is always reachable. Instead, nodes must detect and determine their neighbors, and handle the changes to their neighbors over time. Chakeres, et al. Expires April 6, 2007 [Page 8] Internet-Draft MANET Architecture October 2006 6.3. MANET Membership Given MANETs' characteristics (mobile, wireless, ad hoc) determining a MANETs' membership is difficult, if not impossible in certain scenarios. /----------------------\ /----------------------\ | MANET | | MANET | | +---+ +---+ +---+ | | +---+ +---+ +---+ | | |RT1+-+RT2+-+RT3| | | |RT1+-+RT2+-+RT3| | | +-+-+ +---+ +---+ | | +---+ +---+ +-+-+ | | | | | | | | +-+-+ | Change | +-+-+ | | |RT4+ | in | |RT7| | | +---+\ | Time | +---+ | | \+---+ | \----------------------/ | +RT5+ | /----------------------\ | /+---+\ | | MANET | | +---+/ \+---+ | | +---+ +---+ +---+ | | |RT6+ +RT7| | | |RT6+--+RT4+--+RT5| | | +---+ +---+ | | +---+ +---+ +---+ | \----------------------/ \----------------------/ Figure 3: MANET(s) At one moment a MANET might consist of a certain set of nodes, and the next the MANET could partition into several MANETs. Later it might re-merge or merge with a new set of nodes and form a larger MANET. To assist in coordinating among a loosely connected set of MANET routers, a procedure called flooding is used. MANET flooding consist of disseminating a packet to all connected MANET routers. Certain routers in a MANET might connect to other routing regions. These routers are called MANET Border Routers (MBR), and they often run multiple routing protocol instances. The MBR are responsible for choosing the routing information to share between the various attached routing regions. The MBR should also present a consistent picture of the nodes reachable through them. As MANET membership changes, so does the connectivty of MBR within the MANET. Therefore, a MBR may be challenged to present a consistent set of reachable nodes. It may even choose not to share routing information about the MANET topology to other routing regions. Chakeres, et al. Expires April 6, 2007 [Page 9] Internet-Draft MANET Architecture October 2006 7. Other Important Discussion 7.1. MANETs' Place in the Network Stack While the MANET WG is focused upon network (L3) routing, that does not imply that MANETs and their protocols are limited to L3. Several previous and existing efforts are applying MANET protocols at various layers. The challenges discussed above, exist independent of at which layer MANET protocols are deployed. Of course, the protocols themselves may need to be retooled slightly to accommodate the information available to the deployed layer. MANET MAC layer (L2) routing, more often called bridging, works well in homogeneous wireless networks for delivering frames over multiple hops. One example of L2 MANET is being developed in the IEEE 802.11s WG. L2 routing/bridging hides the multiple L2 hops from L3. This behavior can be advantageous as this network can transparently mimic an Ethernet, to some extent. The ability to mimic Ethernet allows the L2 MANET to utilize existing L3 network protocols. L2 MANET does not enable heterogeneity. That is, L2 MANET is not capable of bridging across heterogeneous interfaces. For example, L2 bridging cannot directly bridge two L2 technologies with different addressing schemes. It can also be difficult if the frame sizes of two L2 vary, as this could require breaking a single frame into multiple frames of a different format. L3 MANET enables heterogeneous networking, as IP was built with this feature in mind. Forming a MANET at L3 implies that the L3 protocols must handle the challenges presented in this document. MANET like protocols can also be used at higher layers. One example is peer-to-peer (P2P) networks. These networks have some of the same challenges as MANET, e.g. variable neighbor relationships and changing membership. 7.2. Cross Layering In wireless networks, and especially in MANET, extended interfacing among the network layers (physical, MAC, link, network, etc) can be extremely useful. Arguably, MANET may not be capable of successful deployment without some degree of cross layering. For example, link layer feedback that a packet/frame was not able to be sent or that it was not received could be used by the network layer to indicate that a neighbor is no longer reachable. This information and other extended interfacing could reduce, or eliminate, some upper layer Chakeres, et al. Expires April 6, 2007 [Page 10] Internet-Draft MANET Architecture October 2006 messaging. Further, it could significantly reduce the latency in decision making. Note that though a certain lower information is valuable, it likely needs to be extrapolated or filtered before accurate assumptions about the network state can be made. For example, failure to deliver a frame by itself may not be a good indicator that a node is or is not reachable. In networks with several different layers of MANET mechanism, the sharing of information across different layers can be even more vital to creating and maintaining the network. For example, if a P2P network is run on top of a L3 MANET, the two networks can share information to use a similar optimized topology. Similarly, they could share neighbor state changes to reduce the messaging or latency in making decisions. 8. Deployment Taxonomy The present and future proliferation of inexpensive wireless interfaces continues to stimulate technical interest and developments in the area of MANET for a wide variety of deployment scenarios. In this section, we present several characteristics for describing expected MANET deployments. 8.1. Service Availability Nodes often expect certain services/servers to be available. When describing a deployment scenario, it is important to specify the expected services available and the distance between the servers and the clients. In MANET, nodes might assume a service is available locally (within one IP hop) or within a particular scope (one or more IP hops - MANET, site, global). Nodes might assume in certain deployments that no special servers/services are available. Finally, nodes might assume that servers are sometimes available, but their availability is not guaranteed or ensured. Different frameworks for autoconfiguration, network management, and intra-AS routing can be developed based upon the expected constraints and operating conditions. 8.2. Number of Peer MANET Routers The number of peer MRs in a MANET is an important consideration. This number is not the complete number of nodes in a MANET (since MRs may support an arbitrary number of connected nodes) but a measure of the number of peer MR participating as a cohesive flat routing area. While the number of MRs does not define scalability of a MANET protocol, it is often useful discuss the number of peer MR to get a Chakeres, et al. Expires April 6, 2007 [Page 11] Internet-Draft MANET Architecture October 2006 feel for maturity of typical deployment solutions. For simplicity we define the following network sizes to aid in discussion: Small 2-30 MANET peers Moderate 30-100 MANET peers Large 100-1000 MANET peers Very large Larger than 1000 MANET peers At the time of writing, small and moderate size peer MANET routing scenarios have matured and have reasonable testing and deployment experience. These sizes can perform reasonably well in many cases without hierarchy. MANET architectures can, of course, support routing hierarchies to improve scaling. Large and very large MANET routing areas that are flat are still a topic of active research and are not considered here. Existing MANET routing developments, such as SMF [I-D.ietf-manet-smf], have shown significant performance improvements and capabilities even in small peer router size deployments and experiments. 8.3. Example Deployments Here we provide a short list of example deployment scenarios: Home, office, campus, and community mesh networks Disaster relief and first responder networks Sensor networks Range extension Military communications Automotive networks 9. Security Considerations TBD Chakeres, et al. Expires April 6, 2007 [Page 12] Internet-Draft MANET Architecture October 2006 10. IANA Considerations This is an informational document. IANA requirements for MANET related protocols will be developed within the protocol specifications for MANET protocols. 11. Acknowledgments Discussions and developments concepts and architectural issues have evolved over many years of discussion of related work within the MANET WG. There are obviously many people that have contributed to past discussions and related draft documents within the WG that have influenced the development of these concepts that deserve acknowledgment. The authors would like to thank all contributors to the MANET and AUTOCONF WG efforts and those that have helped in the review and content process. While not entirely complete the authors would like to in particular thank the following individuals for there discussions and contributions: Fred Templin Christopher Dearlove Charles Perkins Justin Dean Subhranshu Singh Tom Henderson Emmanuel Baccelli Dave Thaler Jari Akko Thomas Narten Seung Yi Chakeres, et al. Expires April 6, 2007 [Page 13] Internet-Draft MANET Architecture October 2006 12. Informative References [FL01] Freebersyser, J. and B. Leiner, "A DoD perspective on mobile ad hoc networks", Addison Wesley C. E. Perkin, Ed., 2001, pp. 29--51, July 2001. [I-D.ietf-ipv6-2461bis] Narten, T., "Neighbor Discovery for IP version 6 (IPv6)", draft-ietf-ipv6-2461bis-08 (work in progress), September 2006. [I-D.ietf-manet-smf] Macker, J., "Simplified Multicast Forwarding for MANET", draft-ietf-manet-smf-02 (work in progress), March 2006. [I-D.templin-autoconf-dhcp] Templin, F., "MANET Autoconfiguration using DHCP", draft-templin-autoconf-dhcp-01 (work in progress), June 2006. [I-D.thaler-autoconf-multisubnet-manets] Thaler, D., "Multi-Subnet MANETs", draft-thaler-autoconf-multisubnet-manets-00 (work in progress), February 2006. [RFC1812] Baker, F., "Requirements for IP Version 4 Routers", RFC 1812, June 1995. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, November 1998. [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998. [RFC2461] Narten, T., Nordmark, E., and W. Simpson, "Neighbor Discovery for IP Version 6 (IPv6)", RFC 2461, December 1998. [RFC2501] Corson, M. and J. Macker, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999. [RFC3513] Hinden, R. and S. Deering, "Internet Protocol Version 6 (IPv6) Addressing Architecture", RFC 3513, April 2003. [RFC3753] Manner, J. and M. Kojo, "Mobility Related Terminology", Chakeres, et al. Expires April 6, 2007 [Page 14] Internet-Draft MANET Architecture October 2006 RFC 3753, June 2004. Chakeres, et al. Expires April 6, 2007 [Page 15] Internet-Draft MANET Architecture October 2006 Authors' Addresses Ian Chakeres Boeing The Boeing Company P.O. Box 3707 Mailcode 7L-49 Seattle, WA 98124-2207 USA Email: ian.chakeres@gmail.com Joe Macker Naval Research Laboratory Washington, DC 20375 USA Email: macker@itd.nrl.navy.mil Thomas Heide Clausen LIX, Ecole Polytechnique 91128 Palaiseau CEDEX France Email: T.Clausen@computer.org URI: http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/ Chakeres, et al. Expires April 6, 2007 [Page 16] Internet-Draft MANET Architecture October 2006 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Chakeres, et al. Expires April 6, 2007 [Page 17]