Mobile Ad hoc Networking (MANET) L. Speakman Internet-Draft Research Center for Natural Hazard Intended status: Informational and Disaster Recovery, Niigata Expires: November 25, 2009 University K. Mase Graduate School of Science and Technology, Niigata University May 25, 2009 Routing Loop Issue in Mobile Ad Hoc Networks (MANETs) draft-speakman-looping-issue-00 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. 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 November 25, 2009. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. Speakman, Mase Expires November 25, 2009 [Page 1] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 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. Abstract This document describes the routing loop and packet looping issues in mobile ad hoc network (MANET) running proactive routing protocols using hop count metric. Mechanisms of loop formation are identified and how the problem of loop formation is exacerbated by the use of Link Layer Notification is described. The effect of the looping packets on the network are shown by comparing against the case where the looping packets are detected and discarded, showing the need for routing loops or looping packets to be dealt with in MANETs. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4. Mechanism of looping . . . . . . . . . . . . . . . . . . . . . 5 4.1. Loop Formation under plain OLSRv2 . . . . . . . . . . . . 6 5. LLN and its effect on looping . . . . . . . . . . . . . . . . 8 6. Effect of looping on network performance . . . . . . . . . . . 9 7. Effect of looping detection and looping packet discard on network performance . . . . . . . . . . . . . . . . . . . . . 9 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 9. Security Considerations . . . . . . . . . . . . . . . . . . . 11 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 12 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 11.1. Normative References . . . . . . . . . . . . . . . . . 13 11.2. Informative References . . . . . . . . . . . . . . . . 13 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14 Speakman, Mase Expires November 25, 2009 [Page 2] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 1. Introduction To maintain loop-free routes to a destination, it is necessary that the same topological image is perceived between neighboring nodes and thus across the network as a whole, and to make routing and forwarding decision which are consistent with this. However, it has been observed that transient routing loops form in Ad-hoc Networks running MANET proactive routing protocols using hop count metric. These transient routing loops may only appear for a very short amount of time and may not be the result of malevolent nodes but nodes that are unable to adequately maintain a coherent and up to date perception of the network topology for a short amount of time, thus leading to the formation of the transient routing loop. This may occur due to normal operation of the routing protocol. Even when only a small portion of the traffic enters these loops and only for a brief time, the effect is to increase the impact on the surrounding medium and its supported traffic thus degrading overall network performance. A packet may circulate around a loop for some time before its TTL or Hop Count field goes to zero. Due to the mobile nature of mobile ad-hoc networks and the transient nature of the wireless medium, links may form and then disappear on a short time scale. In order to respond to these rapid changes, some routing protocols rely on the link layer being able to notify the routing protocol as soon as a packet fails to be forwarded over that link as determined by the lack of an acknowledgement when bidirectional links are being used or by some other means in networks where unidirectional links are supported. Loop formation is exacerbated by the use of these Link Layer Notifications techniques in acknowledgement-enabled link layers in which the link layer informs the routing protocol when the sending node is unable to receive an acknowledgment of the successful forwarding of a unicast packet to the next hop. The Routing Loop may be attempted to be directly avoided by careful design of the routing protocol, to establish links and topological maps that are coherent between nodes and to only make changes that can be accounted for in the wider network without ambiguity leading to routing loops. However, this may be difficult with the need for routing protocols to quickly update their Information Bases if local links fail to perform as expected, thus requiring a sudden change in local link state or network topology that may inadvertently lead to adjacent nodes' topology maps of the network becoming non-coherent between them. Furthermore, larger networks in which there are a large number of Speakman, Mase Expires November 25, 2009 [Page 3] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 hops between any source-destination pair may be unable to use low TTL (Time to Live) or Hop Count that limit the effects of circulating packets that are caught in loops earlier in their path. This document identifies the loop formation in proactive link-state based routing protocol, OLSRv2 and their transient nature based on simulation of networks in which multiple hops are required from source to destination. The detrimental effect on the surrounding network traffic of the transient routing loops, in particular the packets that loop over them, are shown by comparing against the case where the looping packets are detected and immediately discarded, showing the need for routing loops or looping packets to be dealt with in a timely manner. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [1]. This document uses the terminology defined in [2, 3, 4], as well as the following terms: Routing Loop: An aggregate state existing in two or more nodes such that if a packet was routed over them for a particular destination, the packet would circulate. Loop Detection: Detection of looping unicast IP packets. Post-Loop Detection: Looping packet detection after one complete looping of unicast IP packet has occurred by using DPD-based algorithm. Duplicate Packet Detection (DPD): Detection of packets which have previously been received. Packet Discard: A loop suppression action that may be triggered on looping packet detection in which the packet is immediately discarded. 3. Overview Transient routing loops have been observed to form in Ad-hoc Networks running MANET proactive routing protocols using hop count metric. Even when only a small portion of the traffic enters these loops and only for brief time, the effect is to increase the impact on the Speakman, Mase Expires November 25, 2009 [Page 4] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 surrounding medium and its supported traffic thus degrading overall network performance. The effect is exacerbated by the use of Link Layer Notifications techniques in acknowledgement-enabled link layers in which the link layer informs the routing protocol when the sending node is unable to receive an acknowledgment of the successful forwarding of a unicast packet to the next hop. This document identifies how routing loops form in proactive routing protocols with the use of simulation. Natural incoherency in adjacent topology maps are shown to lead to the formation of routing loops. Loop formation is then shown to be exacerbated by the use of Link Layer Notification that causes a large increase in local changes in the link state and thus the perceived topology map of the network as seen by different nodes. The detrimental effects of the looping packets are significantly increased on the network at higher loads. The introduction of a Loop Detection technique that triggers a Packet Discard action on the detection of looping packets reveals the extent to which looping packets have on the network in simulation based on OLSRv2 with LLN. These comparisons made against discarding looping packets directly show the necessity of routing loops or looping packets to be dealt with. 4. Mechanism of looping The mechanism of loop formation is shown with the help of figure 1 for the case of the proactive link-state routing protocol, OLSRv2. Consider the partial network as shown in figure 1. This partial network is given with the first assumption that it exists as part of a larger and denser network with other nodes and links not shown, and the second assumption that the shortest route to the destination D from 1 is via the left; 1-3-5 and the second shortest route from 1 is towards the right; 2-4-6, and similarly for node 2 in a symmetrically reversed fashion. Other longer routes to the destination exist in the wider network, and node 5 and 6 may necessarily be the same node. Such a partial network may appear very often in most networks. Each node advertises itself by Hello Packet as defined in NHDP [3]. Once each node receives the advertised interfaces of the neighboring nodes from the Hello Packet, it advertises the heard links with the neighboring nodes allowing each node to build up a Link Set including Symmetric (bi-direction) links. Each Symmetric link is advertised in the next round of Hello broadcasts allowing each node to build up a map of all symmetrical 2-hop links in the 2-Hop Neighbor Set. In this way, from Figure 1, Node 2 will be aware of the symmetric links 1-3 via node 1 and so on. Speakman, Mase Expires November 25, 2009 [Page 5] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 +--------+ | node D | Destination +--------+ / \ / \ +--------+ +--------+ | node 5 | | node 6 | +--------+ +--------+ / \ / \ +--------+ +--------+ | node 3 | | node 4 | +--------+ +--------+ \ / \ / +--------+ +--------+ | node 1 |------| node 2 | +--------+ +--------+ Figure 1. Partial network of nodes with routes to destination D considered to be part of a larger and denser network with other nodes and links not shown. 4.1. Loop Formation under plain OLSRv2 To maintain loop-free routes to a destination it is necessary that the same topological image is perceived between neighboring nodes and thus across the network as a whole, and any changes to the network be advertised in such a way that loops do not form. In Figure 1, under standard OLSRv2 operation [3, 4], consider the shortest path chosen by each node to the destination D. For example, node 1 would choose the route 1-3-5-D along the left whilst node 2 would choose the route 2-4-6-D along the right. This is a partial network conveying topology which is seen to commonly exist in ad-hoc networks. Each node broadcasts a Hello Packet every 2 seconds advertising its Symmetric, Asymmetric and Lost links, and each node broadcasts a TC Packet every 5 seconds advertising the Topology as perceived by each node which is efficiently flooded through the network by the use of MPRs (Multi Point Relays) as defined in [4] At startup, links 3-5 and 4-6 are considered to exist as well as the other links as given in Figure 1. Node 5 fails to receive the Hello Packet broadcast by node 3 for three consecutive occasions leading to the timeout of link 3-5 in node 5's Link Set. Node 5 also updates its 2 Hop Neighbor Set and Topology Set removing the respective link. This timeout occurs at three times the Hello Interval after the last successfully received Hello Packet that indicated that a symmetric Speakman, Mase Expires November 25, 2009 [Page 6] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 link with node 3 was still formable. At this time, node 3 is unawares that link 3-5 has timed out in node 5, and for the time being continues to consider the link as symmetric. The loss of link 3-5 is advertised in the next Hello Packet broadcast by node 5, and is received by node 3 which updates its Link Set, setting the link to Asymmetric, and updating its 2 Hop Neighbor Set, Topology Set, Routing and other Sets, and the Routing Table - removing the link from use. From this point, any data packets that are forwarded to node 3 to route to destination D would not use link 3-5 but would choose a different longer route through the surrounding network (not shown). As such, it is assumed that node 1 forwarding packets to node 3 for Destination D will have its packets routed via a different path but the network would be sufficiently dense such that the packets still reach the destination. On the next Hello Packet broadcast by 3, the change in state of link 3-5 to Asymmetric is advertised. Node 1 receives this broadcast and updates its 2-Hop Neighbor Set removing the link and its Topology Set and other respective Sets. The routing calculation would result in the next best route being chosen to destination D, and this would be via node 2 along the right; 2-4-6-D, as seen in Figure 1. A similar pattern of events that happened in nodes 5, 3 and 1 also occur respectively in nodes 6, 4 and 2. The inability of node 6 to receive the Hello Packet broadcast by node 4 results in a timeout of link 4-6 in node 6. This change is then advertised in the Hello Packet broadcast by node 6 resulting in node 4 updating its respective state. The change is then advertised by Hello Packet by node 4, and node 2 updates its 2-Hop Neighbor Set and Topology Set removing link 4-6. Node 2 then performs a routing calculation resulting in the next best route being chosen to destination D via node 1 along the left; 1-3-5-D, as seen in Figure 1. Node 1 is momentarily unawares of the link break 4-6 and similarly node 2 is unawares of the link break 3-5, thus leading to a temporary loop forming whereby for every packet for destination D, node 1 routes via node 2 and node 2 routes via node 1 causing the routing loop. This is independent of how the loss of link 3-5 and 4-6 formed, and the routing loop between 1 and 2 is corrected in some time. The correction takes place and the routing loop vanishes when node 1 becomes aware of link break 4-6, node 2 becomes aware of link break 3-5, or other shorter routes become available. As seen in simulation, routing loops are created and corrected on a Speakman, Mase Expires November 25, 2009 [Page 7] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 continual basis in the network, however, under 'plain' OLSRv2 are seen to be relatively few in number and don't have a significant negative impact on total network performance [6]. 5. LLN and its effect on looping Loop formation described in section 4 is a temporal effect. It has only a minor impact on packet delivery performance in plain OLSRv2. In plain OLSRv2 packets are often attempted to be forwarded over links that cannot physically support packets as the link may remain in the Link Set for some time even after the physical link has been lost. This false perception can persists for up to three Hello Intervals from which the last Hello Packet was received, which is designed to avoid unnecessary link removals due to the failure of Hello receptions in the radio environment. To rectify the problem of continuing to attempt to forward packets over a link that has been physically lost, LLN (Link Layer Notification) is enabled in order to detect when links are no longer physically viable. With LLN, if a node tries to forward a packet over a link, but it cannot receive any link-layer acknowledgement after a certain number of retries depending on the Data-Link Protocol in use, the Link Layer will notify the routing protocol via the LLN mechanism. The routing protocol will act on this, marking the link as Lost in the Link Set, updating the 2-Hop Neighbor Set, calculating a new Routing Set, followed by updating the Routing Table. LLN can significantly improve packet delivery ratio by early detection of link breaks and rerouting. The effect of this is to cause the Link Set in the node that has the LLN to change the link over which the packet was dropped from Symmetric to Lost ahead of the symmetric link timeouts between the nodes. The surrounding nodes will still have knowledge of the existence of this link, and the link will still exist in the Topology Sets in the rest of the network for some time, possibly leading to the formation of a loop. The effect of LLN is to ultimately speed the process by which a routing loop forms. Node 3 or node 4 in Figure 1 may not have to wait for a full three times the Hello Interval before the Link Set changes its state from Symmetric. As LLN is triggered on the failure of a data packet to be forwarded over a link and the number of LLNs increases with the amount of traffic in the network, the number of routing loops also increases with the amount traffic in the network. Furthermore, as LLN results in the removal of links at a rate over and above that by timeouts in 'plain' OLSRv2, the total number of links in the network is further Speakman, Mase Expires November 25, 2009 [Page 8] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 reduced thus increasing the average distance from any source to destination. A larger number of the packets remain in the network, taking a longer route, thus adding extra to the network load, impacting the surrounding traffic within interference range of the loop, and further encouraging a higher chance of an LLN occurring in a node along the route supporting the traffic by collision. The negative effect of increased packet looping caused by LLN works against the gains from avoiding dropping packets over broken links that plagues 'plain' OLSRv2. The negative effect as load increases may exceed the gains, thus causing a greater overall loss. 6. Effect of looping on network performance The detrimental effect of looping packets on the network for the case of OLSRv2 is found from simulation given in [6]. Simulations are performed with 60 nodes in an area of 1km by 2km to establish a MANET using OLSRv2. The nodes have mobility of between 0 and 5m/s and the applied load on the network is varied by increasing the number of applications flows. Each application flow consists of a separate client and server that sends 512 Byte application packets from the client to the server at a rate of 4 per second. In OLSRv2, the problem of looping is relatively small, however, high loss is observed as packets are forwarded over links which are no longer physically able to support traffic. The simulated results show from the PDR (Packet Delivery Ratio) is 0.75 to 0.8 under given simulation conditions and slowly decrease with supplied load. The low performance of OLSRv2 reveals the need for LLN. In OLSRv2 with LLN at low loads the PDR is raised to 0.95 for the same conditions, however, the problem of looping packets grows as the load in the network is increased, causing a direct detrimental effect on the performance of the network. The PDR begins to decline rapidly with increasing load as a direct consequence of the looping packets, with a much steeper negative slope against increasing load than for OLSRv2. Due to the looping packets in the network at higher loads under OLSRv2 with LLN, it underperforms that of OLSRv2, rapidly declining to a PDR of below 0.75 as load is increased to moderate values. 7. Effect of looping packet detection and looping packet discard on network performance To directly compare against the effect of removing the looping packets from the network, a looping packet detection technique is Speakman, Mase Expires November 25, 2009 [Page 9] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 introduced, henceforth known as Loop Detection, and an action to discard the looping packet on loop detection, henceforth known as Packet Discard. The loop detection technique, called "Post-Loop Detection", is a looping packet detection algorithm that detects a looping packet after one complete packet loop occurs. Detection is performed at the Network layer, for incoming packets that are not destined to this node, immediately before being further processed by the Network Layer. For every unicast packet outgoing that is destined to a node that is not the immediate next hop, the immutable header fields, option fields and data content of the outgoing IP packet is used to generate a hash digest of a set size of only a few bytes or tens of bytes. All incoming unicast packets are then hashed in the same way and compared against the existing hashed outgoing packets using an efficient search algorithm, as specified in [6], similar to a DPD- based algorithm as specified in [5]. DPD algorithms such as S-DPD and H-DPD specified in [5] MAY be sufficiently usable in this "Post-Loop Detection" mechanism. But DPD algorithms specified in [5] are only for multicast IP packets, and they operate only when node receives packets with multicast address. Therefore these DPD algorithms MUST be extended for unicast IP packets, and they MUST be operated when node receives ANY packets to detect the loops. Once a looping packet is detected, a Packet Discard action is triggered. The packet will not continue to circulate around the loop unnecessarily, therefore reducing the demand on the surrounding wireless medium. The simulation results in [6] indicate that the Packet Discard action on Post-Loop Detection when used with OLSRv2 with LLN is able to raise the PDR (Packet Delivery Ratio), particularly at higher loads where looping packets are greater in number. Using the simulation data results as expressed in section 6, when using Packet Discard the PDR is always increased over that of OLSRv2 with LLN. At low loads, the PDR is raised from 0.95 to 0.96 As load increases, and the number of looping packets increase, the Packet Discard action is able to discard the looping packets thus maintaining PDR relatively high. The PDR is maintained above 0.9 for more than double the applied load as seen in OLSRv2 with LLN and no Loop Detection, and always achieves greater PDR than that of OLSRv2 or OLSRv2 with LLN. Speakman, Mase Expires November 25, 2009 [Page 10] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 Figure 2 gives a qualitative and rough quantitative expression of the results of employing Link Layer Notification techniques that leads to more loops, and the Packet Discard action on Loop Detection that suppresses the effect of these looping packets. PDR (Packet Delivery Ration) 1.00 - | | 0.96 - |---------------- OLSRv2 + LLN + PD (Packet Discard) 0.95 - |------- ---------- | ----- ----- | --- ---- | -- --- | \ -- | \ OLSRv2 + LLN -- | \ | OLSRv2 \ 0.77 - |---------------- \ | ------------ | \ -------- | \ ------ | -- | -- | -- 0.60 - |_____________________________________________ load (number of applications) Figure 2. The end-to-end delivery ratio of packets as seen in simulation. Load is increased (x-axis) by increasing the number of application flows. The use of LLN increases the number of loops as the load is increased, thus having a detrimental effect on the network. The use of PD on Loop Detection suppresses the effects of these looping packets thus revealing to what extent the looping packets have on the network. 8. IANA Considerations This document presents no IANA considerations. 9. Security Considerations This document provides recommendations for mechanisms to be used in protocols; full security considerations are to be provided by those protocols, rather than in this document. Speakman, Mase Expires November 25, 2009 [Page 11] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 It may however be noted that introduction of approaches in consideration of dealing with the looping issue may provide security advantages or disadvantages to the protocol. 10. Acknowledgements This research was supported by the Strategic Information and Communication R&D Promotion Programme (SCOPE). Speakman, Mase Expires November 25, 2009 [Page 12] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 11. References 11.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 11.2. Informative References [2] T. Clausen, C. Dearlove, J. Dean & C. Adith, "Generalized MANET Packet/Message Format", RFC5444, February 2009. [3] T. Clausen, C. Dearlove & J. Dean, "MANET Neighborhood Discovery Protocol (NHDP)", draft-ietf-manet-nhdp-09 (work in progress), 2009.03.26. [4] T. Clausen, C. Dearlove & P. Jacquet, "The Optimized Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-08 (work in progress), 2009.03.10. [5] J.Macker, et al., "Simplified Multicast Forwarding for MANET", draft-ietf-manet-smf-08 (work in progress), 2008.11.03. [6] L. Speakman, Y. Owada, K. Mase, "Looping in OLSRv2 in Mobile Ad- hoc Networks, Loop Suppression and Loop Correction", IEICE Trans. Commun. Vol. E92-B, No. 04, April 2009. Speakman, Mase Expires November 25, 2009 [Page 13] Internet Draft draft-speakman-looping-issue-00 May 25, 2009 Authors' Addresses Kenichi Mase Graduate School of Science and Technology, Niigata University Phone: +81 25 262 7446 Email: mase@ie.niigata-u.ac.jp URL: http://www2.net.ie.niigata-u.ac.jp/ Lee Speakman Graduate School of Science and Technology, Niigata University Email: delta@net.ie.niigata-u.ac.jp URL: http://www2.net.ie.niigata-u.ac.jp/ Speakman, Mase Expires November 25, 2009 [Page 14]