Network Working Group F. Baker Internet-Draft Cisco Systems Expires: August 23, 2002 February 22, 2002 An outsider's view of MANET draft-baker-manet-review-00 Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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 August 23, 2002. Copyright Notice Copyright (C) The Internet Society (2002). All Rights Reserved. Abstract This note addresses routing in chaotic non-engineered radio networks. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [1]. Baker Expires August 23, 2002 [Page 1] Internet-Draft Document February 2002 1. Overview and disclaimer This note addresses routing in chaotic non-engineered radio networks. Examples of such networks vary from webs of radio-linked sensors distributed like seed by air drop, to the behavior of satellites in random orbits, to automotive applications in which cars and traffic lights are communicating nodes, to military applications such as battlefield communications among soldiers, unmanned reconnaissance platforms, vehicle-mounted devices, fixed bases, and field encampments. Such networks have been the subject of significant research over the past several years, with numerous routing proposals, and offers to re-engineer TCP to make applications operate well in the network. The fundamental bent of this note, however, differs from this research in intent. Mobile ad hoc networks, or manets, are not seen as networks in their own right any more than local area networks are networks in their own right. Instead, manets are seen as localities within networks, much as LANs operate as the local access to a wider area Internet. The operation of manets in isolation is a special case of their operation as part of a larger network. Taken from this perspective, the important question is not so much "please design a routing protocol that will be useful in a manet", as it is "please design a routing protocol that will be useful in a network that contains one or more manets". Baker Expires August 23, 2002 [Page 2] Internet-Draft Document February 2002 2. IETF History and Work: the MANET Working Group The MANET working group was chartered in 1997, to discuss and develop solutions for what were described as Mobile Ad Hoc Networks. Although it was chartered as an engineering group, one could argue that it was then and is now a research organization. There has been little if any commercial activity related to this type of network; activity has been focused in the research divisions of various companies, notably Nokia, Inria, SRI, Intel, and others, and with academic institutions such as UCSB, Rice, and so on. 2.1 Problem Statement The problem statement that the MANET working group was given, which may be found at http://www.ietf.org/html.charters/manet-charter.html, says: A "mobile ad hoc network" (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links--the union of which form an arbitrary graph. The routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet. The primary focus of the working group is to develop and evolve MANET routing specification(s) and introduce them to the Internet Standards track. The goal is to support networks scaling up to hundreds of routers. If this proves successful, future work may include development of other protocols to support additional routing functionality. The working group will also serve as a meeting place and forum for those developing and experimenting with MANET approaches. The working group will examine related security issues around MANET. It will consider the intended usage environments, and the threats that are (or are not) meaningful within that environment. In general, a MANET network is very similar to any other Internet technology; one researcher, in a discussion of how to manage low signal-to-noise ratio channels, ruefully remarked that the researchers in the area frequently find themselves re-inventing wheels. Where it differs from standard routing, however, is the structure and characteristics of a low-power radio network. Baker Expires August 23, 2002 [Page 3] Internet-Draft Document February 2002 As an example of the kind of interesting radio environment that can exist, consider the sad case of Alice, Bob, and Carol in figure 1. An environmental obstacle separates Alice and Bob, so their radios cannot "hear" each other, but Carol can "hear" them both quite well, as long as they don't happen to "speak" at the same time. Carol can interconnect them by repeating their messages; they might also be able to correct the problem by taking a few steps or lifting their radios - anything that would obviate the obstacle. Clearly, these devices are in close physical proximity, but their views of the network are very different, and their ability to use it differ markedly as well. As they move, or as their environment changes around them, this view of the network will also change - often appearing to change randomly. | Environmental | Obstacle (metal building, | hill, vegetation, etc) | Alice | Bob / \ | / \ / \ | / \ / \ / \ / \ / \ / \/ \ / /\ \ / / \ \ / / \ \ / /Carol \ \ Figure 1: Varying views in a radio network 2.1.1 Neighbor sets Unlike wired networks, each device in a radio network has a slightly different view of its world. From the router's perspective, a LAN is an essentially fixed set of routing neighbors, which changes only on administrative action, with additional end systems, which may come and go. It is therefore rational and desirable to have the routers elect one among them to perform coordination tasks - what is called a "designated router" in OSPF and IS-IS. In a MANET, however, any system might be called upon to relay traffic for others. Signal quality will also vary dramatically, as any mobile phone user can attest; signal quality, usually measured as a signal-to-noise ratio, is inversely proportional to the square of the distance between the radios, and is modified by environmental hazards such as metal (buildings) and moisture (weather, topography, and vegetation). Baker Expires August 23, 2002 [Page 4] Internet-Draft Document February 2002 Since systems are in different locations, each system may have a different set of neighbors that it is able to communicate effectively with, which overlay each other haphazardly. For this reason, the rules that allow OSPF to reduce its flooding statistics from an exponential to linear behavior by electing a designated router to perform the job are unusable in a radio network. 2.1.2 Random Interconnection Topology Another issue is the aspect of mobility, which is different from what has traditionally been termed "IP mobility". The concept in IP Mobility is that a device has a normal home in some topological part of a stable network, as indicated by its address, but may temporarily move somewhere else. That "address" then becomes something more like a name. A home agent translates it into a second address, which represents the device's current actual topological location, and the packet stream is forwarded there. The device may then advise its correspondent of its current topological "care-of" address, facilitating more direct routing. In a MANET, the address is tied to the device, not a topological location, as there is no fixed network infrastructure. When the addressed device moves, therefore, the motion changes the routing infrastructure. There is no question of the correspondent transmitting to the new care-of address, or of a home agent forwarding traffic from "the right place" to "somewhere else" along a dog-leg path; standard routing will get the packets there as a direct outcome as routing tracks the motion of the device. Mobility is not an aspect of all MANETs; some varieties of sensor networks (such as forest fire sensors scattered by airdrop in the region of a fire) can be expected to be stationary once deployed. However, even in this case, topological relationships are arbitrary and unengineered. In applications where node mobility is in view, it can be haphazard, and in extreme cases can result in entire networks randomly partitioning and joining together. The fundamental behavior of a manet is that a routing node carries with it an address or address prefix, and when it moves, it moves the actual address. When this happens, routing must be recalculated in accordance with the new topology. This has ramifications for such normal behaviors as autoconfiguration of address prefixes and router IDs, which can be replicated in separate networks and will require resolution when they join. It also has ramifications for movement among what OSPF or IS-IS would call "areas"; if an address is "known" to be someplace and suddenly pops up somewhere else, it will need to change areas as well. IP Mobility solves an issue in addressing caused by temporary Baker Expires August 23, 2002 [Page 5] Internet-Draft Document February 2002 mobility; MANET routing solves a routing problem in a network where mobility is normal. When mobility is solved using routing, addressing-based solutions are irrelevant. 2.1.3 Carrier Sense Multiple Access Interconnection The radio networks that typically connect manets have all of the radios on the same frequency, using a CSMA discipline. In other words, if the receiver can tell that someone else is transmitting, it may attempt to not interrupt, but there is no guarantee that it will be able to sense collisions. In such cases, since all radios use the same frequency and spread spectrum patterns, the transmitters effectively jam each other. One could imagine solving that using disciplines similar to that used in LDDI, wherein each system has a sequence number and transmissions are made in that order, to generate a form of Slotted ALOHA. What many of the MANET routing protocols are doing, though, is finding reasons to not have correlated reasons to transmit, such as acknowledging multicast messages, and relying then on randomization to evade the problem. 2.1.4 Convergence Requirements Internet routing protocols, such as RIP, OSPF, IS-IS, and BGP, have always been developed on the assumption that networks proceed from a converged state to a converged state through epochal transitions such as changes to router configurations, loss or restoration of links, or loss or restoration of routers. For this reason, instability in networks is viewed with some alarm. OSPF and IS-IS were developed in large part because it was increasingly observed that existing distance-vector IGPs displayed unacceptably long convergence intervals or were not sufficiently resilient. The increased expressiveness of what were then called "variable length subnets", and are now called Classless Inter-Domain Routing (CIDR) was also a significant factor. At this time, concern is raised in many quarters because the BGP4+ backbone displays significant instability and long convergence intervals. MANET networks display exactly the opposite characteristic: due to node mobility and constantly changing neighbor interconnectivity, the network may display episodes in which it converges, but normally is in a state of flux. The question becomes what level of convergence is required: is it worthwhile to expend a great deal of effort to attempt to maintain a higher level of convergence, or is it better to accept partial convergence? The answer to that is not obvious, and most likely varies from network to network and application to application. Baker Expires August 23, 2002 [Page 6] Internet-Draft Document February 2002 2.1.5 Solution Approaches There are a number of ways to solve these issues, as the number of proposals made to the MANET working group attests. They are commonly broken down into two broad classes: reactive protocols, which determine what route to use when the route is needed, and proactive protocols, that predetermine routes on the assumption that they may be needed. Reactive protocols follow approaches such as source routing or some form of routing on demand. These are designed with the premises: o Network locality is strong: most active routes are topologically local, within one or two hops. o The application can work around occasional routing glitches if recovery is expedited o While routing may change continuously in the global sense, individual routes generally survive long enough to perform common application tasks. o The overhead of searching for a route when it is needed (which may take several round trip times) is acceptable. If one accepts these premises, then it is reasonable to assume that one will search for paths when they are needed, and save them either in the source system or the intervening nodes. Proactive protocols generally follow some form of link-state algorithm, such as SPF (Dijkstra) or of map-based explicit routing. These are designed with the premises: o Network locality is indeterminate; routes of any length may be commonly used, or not at all. o The application can work around occasional routing glitches, but recovery must be almost immediate. o The constant route changes that happen globally may materially affect the correct operation of individual nodes. o The overhead of calculation and information flooding is acceptable, but the overhead of searching is not. It is possible to mix the two models as well; a link state database could be maintained through the network, but inspected only when it changes the routing behavior of a network node known to be relevant Baker Expires August 23, 2002 [Page 7] Internet-Draft Document February 2002 to a route that is currently in use or a new route is needed. 2.2 Progress of the group Since 1997, at least ten protocols have been proposed. These fall into several categories. Dynamic Source Routing (DSR) is similar in many respects to IEEE 802.5 Source Route Bridging. Ad hoc On-Demand Distance Vector (AODV) is a reactive protocol that introduces routing state in a network only when needed. Topology Multicast Reverse Path Forwarding (TBRPF) and Optimized Link State Routing (OLSR) are SPF- based protocols, which may be compared to OSPF or IS-IS. They differ from these in operational detail, and in the way they flood routing database information. Security is an issue that none of these protocols has directly addressed, although some general analyses have been floated in the working group. Security flaws exist in many of them, which could be exploited; for example, DSR is subject to man-in-the-middle attacks, and according to one of the authors has experienced them (in the form of a lack of routing robustness when stations move) in field-testing. Similarly, scaling is an issue that has been dealt with only on the surface. The stated goal of these protocols is "scaling up to hundreds of routers"; whether or not the features that allow this level of scaling will in turn enable scaling to thousands or tens of thousands of routers remains to be shown. The difference between proactive and reactive protocols is intended to address some issues in scaling, with different trade-offs. A reactive protocol might be appropriate in a network where most connectivity is local and non- local routes tend to remain fairly stable for the duration of a typical session; the router maintains no state that is not in current use, and is willing to perform an expensive set-up when it needs non- local routing state. A proactive protocol might be appropriate in network in which non-local communications are normal and route maintenance must be rapid. The trade-off is that in a proactive protocol, topological turbulence causes nodes to constantly store, propagate, and adjust routing information that has no current utility. Quality of Service (important for voice applications) is also not addressed, except in AODV. There is a draft that describes QoS use of the routing protocol, which would have it seek a path in which certain bandwidth and delay bounds are met, and in which the request for a route would fail if its conditions cannot be satisfied. Baker Expires August 23, 2002 [Page 8] Internet-Draft Document February 2002 While extending any of these protocols to IPv6 is straightforward, in publicly available documents, only AODV has materially addressed IPv6. There are drafts on stateless autoconfiguration of IPv6 networks in a MANET, but it is independent of the routing protocol, and apply to non-routing hosts which neighbor with routers, rather than to systems capable of forwarding packets. OLSR mentions how it could be extended to address IPv6. Likewise, TBRPF states (section 9.7.2) that Transition mechanisms described in the IETF NGTRANS working group (e.g. ISATAP) enable IPv6 operation over IPv4 routing infrastructures. ISATAP [19] can be used on TBRPF MANETs to enable automatic IPv6-in-IPv4 operation regardless of route changes due to mobility. Future versions of this draft will specify a native IPv6 capability for TBRPF using mechanisms similar to those specified in [21]. Packet formats which implement such mechanisms will use 4-octet router ID's instead of 16-octet IPv6 addresses for greater efficiency. DHCP is not mentioned in any posted draft, although there are an argument that some form of address assignment protocol adapted to MANET networks is required. IP Mobility is not addressed either. An initial requirements document has been published, as RFC 2501 [4]. DSR and AODV have been proposed to the IESG for publication as Experimental RFCs. No other drafts have been sent to the IESG. 2.3 Probable directions The Working Group expects to publish several protocols as Experimental, including DSR and AODV, but expect to take one reactive and one proactive protocol onto the IETF standards track. These will likely be AODV and OLSR. In 1997, the working group chairs asked the authors of OLSR to publish their work in the IETF context (although one of the working group chairs is the author of a competing proposal), because they considered it a well architected solution to the problem. Although some details remain to be worked out, they still consider it among the better proposals on the table. AODV is likewise a quite workable solution, with an interoperability test of as many as fifteen academic implementations scheduled in March 2002. It alone, of the candidates, addresses IPv6 or Quality of Service issues. Baker Expires August 23, 2002 [Page 9] Internet-Draft Document February 2002 TBRPF is interesting, and should work correctly, although the operational utility of some of its optimizations may be open to question in a given network. SRI has aggressively marketed TBRPF and its IPRs to the working group. The fact that a patent has been applied for on certain aspects is, however, severely limiting politically. If there is any way in which the IETF is absolutely predictable, it is that when confronted with a choice between a proposal encumbered with IPR issues and an unencumbered proposal, it will choose the unencumbered one. The other proposals are either not as far along, have encountered problems, or have less traction in the working group. Baker Expires August 23, 2002 [Page 10] Internet-Draft Document February 2002 3. Market issues From the perspective of the marketplace, at this time there is little commercial demand for MANET-style protocols. This is not an issue in the protocols themselves; it is an issue of the applications in which they might be used. While interactive automotive mapping services are common in Japan and some European countries, these use direct- connect short-reach radio technologies or third generation wireless, rather than packet networks. Sensor networks remain the realm of research, and military uses are in research. As a result, not only are we limited by the lack of standards, but by a distinct lack of market interest. Baker Expires August 23, 2002 [Page 11] Internet-Draft Document February 2002 4. Protocol Proposals For completeness, I will now discuss various possible approaches to MANET routing as described in some of the leading protocols. I will first discuss the use of OSPF Version 2 [3] as a MANET protocol, which has both issues and opportunities. I will also discuss the proposals that I perceive to be leading in the MANET working group, for comparison. 4.1 OSPF Version 2 and IS-IS From the perspective of a commercial vendor, the most obvious routing protocol to use for any application is one that is already implemented. For this reason, Cisco would likely look first to such standard protocols as OSPF, IS-IS, or possibly proprietary protocols such as EIGRP. It also serves as a point of perspective, defining terms and surfacing issues, which the remaining discussion may refer to. If a workable scenario can be found for OSPF or IS-IS in a MANET, interoperation with wired internet components, including wired networks within vehicles, wired bases, and the internet proper, becomes within the grasp of a MANET network, which is one of MANET's clear expectations in its charter. IS-IS and OSPF V2 mirror each other in many respects. Each is an SPF-based protocol, which means that link connectivity information is advertised by each router in the network and maintained in a database by every node. Routes are then calculated through the network by each router separately, but in a consistent manner and using consistent information, which results in rapid convergence on a usable set of routes. The interfaces in an IS-IS or OSPF network fall into four categories: o Local Area Network: A LAN is viewed as a stable and consistent set of neighbors with consistent addressing within an address prefix, which can use LAN multicast or multicast technology for communications. This permits several optimizations over describing them as pairwise point to point connections. o Non-Multicast Multi-Access: OSPF defines an NBMA interface as a special case of a LAN, which does not support a multicast or multicast capability. It is primarily used in Frame Relay and ATM networks. o Point to Point: A point-to-point interface is an interface on which there are exactly two neighbors. o Point to Multipoint: OSPF defines a Point to Multipoint is a Baker Expires August 23, 2002 [Page 12] Internet-Draft Document February 2002 grouping of point-to-point relationships over a common interface. It is primarily used in Frame Relay and ATM networks. Of these types, it will be observed that only two support a multicast or multicast capability - the LAN and the Point to Multipoint Interface. The fundamental issue relates to the process of bringing up a new routing neighbor. In an SPF-based routing network, all routing databases must be consistent to guarantee consistent results. As a result, it is necessary only for a router joining an operational network to synchronize with one router in order to obtain that database. The routers on a LAN elect one among them (called the "designated router") to perform synchronization tasks; as a result, rather than experiencing database flooding traffic on the order of the square of the number of routers on the LAN, that traffic is linear with the number of routers on the LAN. Points to point links, of course, require no such optimization. In the design of OSPF, Frame Relay was originally viewed as being much like a LAN, with internal connectivity that need not be visible to the routing protocol. For this reason, Frame Relay was modeled as an NBMA network, using a designated router like a LAN to make traffic distributions linear. A problem was discovered in Frame Relay networks, however, which used switching equipment that did not support dynamic rerouting around failed internal trunks. In this case, a failure of the trunk connecting the designated router and its backup (showin in figure 2) would cause a designated router election, in which various systems elected different designated routers. OSPF's solution to this is to wait for a uniform election result before continuing, resulting in a complete failure of routing. Other Router | Switch / \ / \ Switch -- Switch | | | | Designated Backup Router Designated Router Figure 2: Routed IP network surrounding a Frame Relay network The solution was to view a Frame Relay network as a bundle of point- Baker Expires August 23, 2002 [Page 13] Internet-Draft Document February 2002 to-point connections, which was called a point to multipoint network interface. While this is subject to traffic volumes on the order of the square of the number of connected routers, the loss of an internal trunk does not result in the loss of external connectivity unless no connectivity exists. In MANET environments, OSPF V2 or IS-IS is likely to encounter a number of challenges. The radio network is a multicast network, so it is tempting to think of it as a LAN. However, in this environment several issues immediately result: o When routers with different parameters on an interface, including area number or address prefix, find themselves in communication, they each assume that the other is misconfigured. As a result, they refuse to accept each other as routing neighbors. o Because each router's view is slightly different, even among routers that choose to become neighbors, the designated router election has inconsistent and inconclusive results. While some sets of routers may converge on consistent designated router choices, the network does not, and routing is not even unstable - it is non-existent. o If the router did calculate routes, other routers would understand from its advertisement that it was able to deliver traffic directly to any router using the same prefix, which would be untrue. o Since flooding occurs away from the interface that information is received on, the only routers that will receive a given bit of routing information will be those within radio range of the originating router. o If N routers advertise an LSA among themselves, in the average case each will send with a link state update or a link state acknowledge to the DR and from the DR to the others, for O(3N) messages. o If a multicast link state update is sent, OSPF has each recipient respond with a unicast acknowledgement right away. In a CSMA network, this is a recipe for disaster; the various senders have a high probability of colliding. If acknowledgements or retransmissions are delayed for a random interval long enough to materially reduce the probability of collision, network convergence is delayed by the same amount. o Since OSPF uses only provably bidirectional links, unidirectional links will be excluded from use. Baker Expires August 23, 2002 [Page 14] Internet-Draft Document February 2002 The most straightforward repair within the existing specification is to consider the MANET to be a point-to-multipoint link, and allocate the interface addresses from a single large prefix per area. In this environment, routing through the MANET is straightforward, and the other issues are resolved. However, these issues remain: o A router that is not configured for a certain OSPF area will not neighbor with routers in that area. o In a multi-area, should a router change its area but retain the same prefix on the radio link, the prefix will appear to be in both areas, and devices in those or other areas will have incorrect routing to some subset of the addresses in that prefix. o Link state updates can be multicast, but the acknowledgements are unicast. Thus, total transmissions are on the order of the square of the number of neighboring routers. o Since OSPF uses only provably bidirectional links, unidirectional links will be excluded from use. 4.2 Ad hoc On-Demand Distance Vector (AODV) Routing AODV is an example of a reactive protocol developed in the MANET context. The authors are Charles Perkins (Nokia Research Center), Elizabeth Belding-Royer (University of California, Santa Barbara) and Samir Das (University of Cincinnati). It has, in draft 9, three messages: a Route Request, and Route Reply, and a Route Error. The Route Reply is essentially a route announcement or update, in the parlance of more traditional distance vector protocols; it says, "You can get to this IP Prefix via me". A Route Request, as its name suggests, searches for a route to an address. When a system needs a route from here to there, it emits a local multicast that floods to all systems within some number of hops away; those systems also learn from the Route Request a least hop count path to the originator of the request. If a copy of the Route Request gets to the target or to any system which has a route to the target, that system issues a Route Reply, which is forwarded along the best path to the source, and installs a route to the destination. This route has a timer on it; it will survive until a movement of one of the devices en route changes it, or until the timer expires. A route reply is used in another way as well. It can optionally be periodically flooded to all neighbors within a certain distance; the specification refers to such behavior as a "hello", and suggests limiting the flood to directly accessible routers. In this way, all Baker Expires August 23, 2002 [Page 15] Internet-Draft Document February 2002 neighboring systems normally have routes, and need not search among immediate neighbors. The routers also keep state on any route that is in use; if a packet is sent from "here" to "there", each system en route tags the route with the fact that the previous hop router to "here" recently used the route. In the event that a route fails (the route is in use and times out, the next hop is lost, or the next hop issues a Route Error to it), it issues a Route Error to its neighbors that are using the route. This gets back to the source of the traffic. The source recalls how many hops away the destination was and issues a slightly wider diameter search, to set up a new route to the destination. The protocol was originally specified to support IPv4 in a best effort model. It has been extended, in separate drafts, to carry IPv6 information, and to eschew routes that fail specified criteria. The latter is referred to as "QoS Routing", on the premise that a route which has no more than a certain percentage utilization of the link and no more than a specified worst case delay will deliver a specified quality of service. One issue in robustness has been reported; it is possible to receive a Route Reply hello through a link that has a poor signal to noise ratio, and be unable to actually use the route for communication. Unfortunately, drivers may or may not report the signal to noise ratio, the signal to noise ratio does not necessarily translate into a statement that a certain percentage of traffic will survive a link, and mechanisms in 802.11b that should mitigate this are unimplemented and perhaps unimplementable in most drivers. Experimentation is ongoing with filters to detect and deal with this issue. 4.3 Optimized Link State Routing (OLSR) Protocol OLSR is an example of a proactive protocol using Dijkstra's algorithm to calculate routes. Thomas Clausen, Philippe Jacquet, Anis Laouiti, Pascale Minet, Paul Muhlethaler, Amir Qayyum, and Laurent Viennot, all of INRIA Rocquencourt in France, originally developed it. Comparisons are made to OSPF, of the form "it is a simplified version of OSPF". It is fairer to say that it uses similar fundamental algorithms; it distributes connectivity information using a flooding algorithm, and maintains a route table calculated using the SPF algorithm. Unlike OSPF, the flooding algorithm is unreliable. Fundamentally, the protocol consists of two message exchanges: hello messages and link state flooding (which includes both connectivity information and withdrawal of the same). Each system in the network emits a periodic hello, which lists the systems whose hellos it is hearing. If those systems can also hear it, the message identifies Baker Expires August 23, 2002 [Page 16] Internet-Draft Document February 2002 bidirectional channels (channels which carry control traffic in both directions). As they listen to each other, they can determine that they may be in possession of information from some of their neighbors that other neighbors don't have; they are therefore also able to forward these link connectivity messages (or the withdrawal of those messages) to their peers. They can then run an SPF calculation to calculate the correct routes. This breaks down in two places. One is that, since every system has a slightly different set of neighbors, every system can often justify repeating its message to someone. However, this logic results in far more relay transmission of the link state database than is actually necessary. A small subset of those relay systems is capable of delivering the same effectiveness in flooding. The difficult question is "what subset should be used?" OLSR provides a way of resolving this, by asking each system to identify the neighboring system that seems most capable of giving it information about the part of the network it is not hearing from somewhere else, and designate that system as a MultiPoint Relay (MPR). The systems so designated form a lattice across the larger network, relaying routing information and multihop route messages among themselves, and relegating the other systems to a status more similar to that of hosts in the general Internet. This provides no area hierarchy, in the OSPF sense, but does provide a way to minimize the remulticast of routing information, and settles the network on a backbone of sorts. This backbone shifts, as the network itself shifts. The other problem inherent in OLSR is the same robustness issue found in AODV. It is possible to receive a Hello through a link that has a poor signal to noise ratio, and be unable to actually use the route for communication. As with AODV, experimentation is ongoing with filters to detect and deal with this issue. The robustness issue has another side effect, however, this more serious. Since flooding is unreliable and links are error-prone, there is a nontrivial chance that the information fails to be delivered everywhere. In such cases, routing may recover; the best route may not be calculated, but the network may succeed in calculating one that works. If routing does not, one can only hope that the route is not used until it is corrected. Ongoing research is looking at the MPR determination heuristic and the use of filters to identify unacceptably lossy links. Baker Expires August 23, 2002 [Page 17] Internet-Draft Document February 2002 4.4 Extensions to OSPF Version 3 OSPF Version 3 [6] is an extension of OSPF to IPv6, and uses IPv6 to accomplish its goals. It is quite similar to OSPF V2 in most respects, but an important consideration is that it uses the IPv6 link-local address for all inter-router links. This reduces or eliminates complexities related to un-numbered links, choice of prefix, and so on. Two properly configured routers can neighbor even if they have no prefixes in common, as a result. In a MANET, this is an important result. MANET routing should be manageable in OSPF V3 if two extensions are adopted: area mobility and a "MANET" interface type with appropriate procedure and metric accommodation to the MANET network. If these two modifications are accepted, then the only remaining issue is that OSPF only uses bidirectional links 4.4.1 Area Mobility One issue in MANET routing using OSPF is what happens when a router finds itself faced with someone of a different area. For example, if a vehicle associated with one battalion goes around a hill to a region occupied by another battalion, it still needs to communicate with its home base, but the only available connectivity may be through the new OSPF area. It is possible to configure the use of every possible area on the MANET interface, but this is problematic. It seems like a better approach would be to autodetect the area and join it. Apart from administrative issues, autodetection is itself straightforward: as the device moves into the new area, it will start receiving hellos from neighbors in it, which carry the configuration of the interface that they use. When configured to do so, and assuming that appropriate authentication has taken place, the router would auto-create an OSPF interface on the MANET interface, which adopts those parameters. The hellos initiated on that OSPF interface would neighbor with the new devices. Several problems instantly materialize, however. A router which automatically discovers a new area needs an algorithm to determine when it should adopt or discard it, and therefore to create or collapse the auto-generated area configuration and database. The simplest approach I have come up with involves noticing whether a route exists to an ABR. If the device has a concept of a "home area", and it has network connectivity to an ABR in that area, it should avoid neighboring with routers in another area. If it is coming into contact with devices from another area Baker Expires August 23, 2002 [Page 18] Internet-Draft Document February 2002 and still has connectivity in its home area, it should require them to accommodate themselves to it, and not the other way around. If it is coming from the other area and gains new connectivity to the home area, this means that it should destroy its connectivity in the non- home area once routing in the home area has been established. In short, area mobility is a solution for a router displaced from its home area. A router which is in two areas, in OSPF, is considered to be an Area Border Router. As an ABR, one of the areas it must support is area 0.0.0.0, the backbone area, and if there is only an indirect connection to other ABRs, a direct connection should be created using a virtual link. For several reasons, this is problematic. Unless the device is configured to be an ABR, it would be better if it would advertise all of its prefixes in both areas, and depend on the multipath routing characteristics of OSPF to resolve the issue. This may be considered similar to running multiple instances of an OSPF process, and advertising all local prefixes in both. 4.4.2 MANET Interface Type Section 4.1 details the behavior and issues of either the point to multipoint interface or a multicast interface. In context, it seems that MANET calls for an interface type which o Is multicast capable, and uses multicast for link state flooding. o Does not elect a designated router. o Enables a router that becomes active with a large number of communicating routers simultaneously to synchronize its LSA database with them serially (or at least one of them first) on a unicast basis, on the assumption that they are likely to already be synchronized among themselves. o Results in a set of point to point relationships with its neighbors being advertised in its router links LSA. o Repeats a new LSA in a multicast on the interface it was received on, both to implicitly acknowledge its receipt and to propagate it to neighbors who may not have received the initial multicast. This is very similar to the point to multipoint interface type, with the possible exception of the final bullet. The implication is that it need not respond to a multicast announcement with a unicast acknowledgement; the multicast retransmission implicitly acknowledges the update. However, a unicast retransmission of the update needs to result in a unicast acknowledgement. In the ideal case, this means Baker Expires August 23, 2002 [Page 19] Internet-Draft Document February 2002 that an LSA update requires each router in the area to make a single multicast transmission (linear distribution effects), and in the less than ideal case there is some level of unicast retransmission. There is one side-effect of this behavior that bears investigation: sending a multicast which requires its receivers to each potentially send a message has correlated transmissions as a necessary result. In a CSMA environment, the implication is that they are likely to collide, resulting in a high rate of loss. Many of the MANET routing protocols find ways to not have correlated reasons to transmit, by not acknowledging, or by including the acknowledgements in uncorrelated messages. On multiplexed interfaces, OSPF is often implemented with some form of randomized delay or link layer serialization prior to acknowledgement, to limit this effect. There is an issue in randomized delays, however, in a radio environment: for the randomization to have the necessary effect, the interval must me long enough that any two transmitters have a very low probability of collision, such that the period over which the transmissions occur is a multiple of the message duration and the number of relevant routers. This tends to result in an arbitrary extension of the convergence interval. One could also imagine solving that using disciplines similar to that used in LDDI, wherein each router generates a link layer sequence number and transmissions are made in that order. The routing protocol could carry in its "hello" message a "transmission sequence number", which is essentially a random number that the routers verify is different among neighboring routers. In LDDI, the link protocol assigns each device a time slot by giving it a sequence number in a range 1..N. System number 1 gets the first turn; it either leaves a minimum-sized message duration idle, or transmits a message. System 2 listens, and when System 1's message duration or transmission is done, leaves a minimum-sized interval or transmits a message. The process repeats through system N, who will have waited through N-M idle time slots and seen M messages. System N then sends its own message, if it has one, followed by a short message as though from system 0, triggering the start of a new round. Through this scheme, they effectively pass a token for access to the otherwise-CSMA link, but do so without a "token" message. In a radio network, when acknowledging a multicast message, this could be emulated if every router organized a sequence number among its neighbors. This would be a random integer not duplicated among neighboring routers, an a relatively small range such as 1..twice the number of neighboring routers. It is transmitted in the "hello" message, and any router receiving its own number from a neighboring system is obligated to change its number. When a multicast link state advertisement is received, or similar message which the router Baker Expires August 23, 2002 [Page 20] Internet-Draft Document February 2002 realizes that it must acknowledge and is likely to collide with others while doing, it schedules the message sequence*interval time units in the future, to limit the probability of collision; with CSMA techniques, there is an improved chance of collision avoidance. "Interval", of course, must be defined; one might expect it to be the MANET interface's MTU in bits divided by its link speed, perhaps with some randomization. A simple way to generate the sequence number would be to sort the addresses listed in the combined hellos of a set of neighbors. If a system has N neighbors, and constructs the union of the link addresses or router ids that they are advertising, and sorts them numerically as unsigned numbers, any given system's sequence number may be its own index in that array. While every system will have a slightly different view of the array, the approach at least has the possibility of distributing the traffic. There are good reasons to put this behavior in the link layer protocol, as the designers of LDDI did. However, if the MANET routing protocol is the only protocol that has a message-burst issue, one could also argue for putting it in the routing protocol. 4.4.3 Metric issues: selecting a path with adequate link quality OSPF leaves the design of the routing metric to the administration, with only the proviso that it will use the route that minimizes the sum of the metrics en route, and they must fit in a specified range. In a MANET network, one could argue that links tend to have comparable speed and capacity, as they are all the same radio network. The metric, then gives us an opportunity to represent other kinds of information. Baker Expires August 23, 2002 [Page 21] Internet-Draft Document February 2002 One example might be a hierarchical function metric = willingness*2^k + f(S/N Ratio) where Metric OSPF metric is in 1..2^16-1, and specifies "goodness" of the link. The "best" links have small numbers. Willingness 0..2^(16-k)-1; lower numbers are used by systems more "willing" (in a policy sense) to act as routing relays. f(S/N Ratio) A number in 1..2^16-1, indicating the utility of the link for radio purposes. Desirable links exhibit small numbers. This would allow stations to indicate the link quality perceived between themselves and their neighbors, and also permit simple policies. By policy, a station might prefer to not relay messages if its batteries are low, for example. The downside of this approach is that the utility of links can change rapidly and dramatically, changing the routing. The changes in routing, of course, are to work around problems in the network, and without the changes, communication is hindered. However, oscillation is itself problematic (as the BBN SPF experience demonstrated), and to be minimized. A technique which has been effective in this is called "multiplicative decrease and additive increase." In TCP, for example, we halve the effective window in response to congestion, and increase it slowly to probe the available bandwidth. The function of the signal to noise ratio might use the same model. If the S/N becomes dramatically worse, the function should become dramatically worse, and should be announced fairly soon. As the S/N improves, the function may improve, but the improvement should be at a more leisurely pace, and announced with greater delay. Baker Expires August 23, 2002 [Page 22] Internet-Draft Document February 2002 5. Conclusions The discussion yields no strong conclusions at this time. A number of protocols have been considered in research, with the result that we have learned quite a bit about these networks. Some of that learning has been relearning lessons already learned in the Internet itself, with the resultant reinvention of related solutions, or remembering the reasons they were invented. It is not obvious that a single protocol is an adequate solution for all MANET problems. As in wired networks, there is room for creativity, and for difference of opinion. Commercially, if I had to hang my hat on two solutions, one reactive and one proactive, at this time I would go with AODV and some extensions to OSPF V3. The reasons for those choices are: o AODV is well advanced and has good capabilities for its target networks. o AODV is publicly documented, as opposed to being partially documented in corporate research reports or intellectual property declarations. o AODV has preliminary work on QoS Routing and IPv6 routing in place; for other protocols, these are futures. o OSPF has significant market traction. o OSPF can be extended to include MANET-type interfaces, incorporating lessons from OLSR, TBRPF, and so on. o If this is done, OSPF can span wired and wireless networks. Baker Expires August 23, 2002 [Page 23] Internet-Draft Document February 2002 6. Security Considerations In routing, beside the fundamental faults of undebugged code, there are three primary threats. A network may require privacy in order to not give away important information. A network device may be improperly configured. A rogue system may mimic, inject, or remove routes in order to disrupt traffic flow. Neither AODV nor OLSR explicitly addresses any of these. In MANET networks where link privacy is a significant consideration, it is logical to presume physical or link layer encryption. IPSEC encryption could be used, but a radio listener who read the IP headers could deduce much of the routing information. OSPF V3 presumes the use of IPSEC Authentication, with a symmetric key in LANs and a symmetric or an asymmetric key on point to point links. This is an improvement over OSPF V2's MD5 algorithm. It secures the relationship between neighbors, ensuring that routes are learned from trusted devices. Physical or link layer encryption also provides this protection, though; if a neighbor's transmissions can be decrypted, the neighbor must have known how to encrypt them. None of these, however, place a signature on an LSA, such as is suggested in RFC 2154 [2], or otherwise address the issues raised in RFC 2725 [5]. Thus, these protocols do not secure the network against a rogue system once its neighbors decide to trust it. Baker Expires August 23, 2002 [Page 24] Internet-Draft Document February 2002 7. Acknowledgements The author acknowledges the inputs of many in this document, most especially Joe Macker, Scott Corson, Abhay Roy, Alexander Zinin, Elizabeth Belding-Royce, and Charlie Perkins. Baker Expires August 23, 2002 [Page 25] Internet-Draft Document February 2002 References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Murphy, S., Badger, M. and B. Wellington, "OSPF with Digital Signatures", RFC 2154, June 1997. [3] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [4] Corson, M. and J. Macker, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999. [5] Villamizar, C., Alaettinoglu, C., Meyer, D. and S. Murphy, "Routing Policy System Security", RFC 2725, December 1999. [6] Coltun, R., Ferguson, D. and J. Moy, "OSPF for IPv6", RFC 2740, December 1999. [7] Das, S., Perkins, C. and E. Royer, "Ad Hoc On Demand Distance Vector (AODV) Routing", draft-ietf-manet-aodv-10 (work in progress), January 2002. [8] Perkins, C., Royer, E. and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing for IP version 6", draft-perkins-aodv6-01 (work in progress), November 2001. [9] Perkins, C. and E. Belding-Royer, "Quality of Service for Ad hoc On-Demand Distance Vector Routing", draft-perkins-manet- aodvqos-00 (work in progress), November 2001. [10] Jacquet, P. and T. Clausen, "Optimized Link State Routing Protocol", draft-ietf-manet-olsr-05 (work in progress), October 2001. [11] Jacquet, P., "Multicast Optimized Link State Routing", draft- jacquet-olsr-molsr-00 (work in progress), November 2001. [12] Lewis, M., Templin, F., Bellur, B. and R. Ogier, "Topology Broadcast based on Reverse-Path Forwarding (TBRPF)", draft- ietf-manet-tbrpf-04 (work in progress), January 2002. Baker Expires August 23, 2002 [Page 26] Internet-Draft Document February 2002 Author's Address Fred Baker Cisco Systems 1121 Via Del Rey Santa Barbara, CA 93117 US Phone: +1-408-526-4257 Fax: +1-413-473-2403 Baker Expires August 23, 2002 [Page 27] Internet-Draft Document February 2002 Full Copyright Statement Copyright (C) The Internet Society (2002). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS 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. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society. Baker Expires August 23, 2002 [Page 28]