Loop Detection for MANET
draft-mase-manet-loopdetect-00

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 May 13, 2008.

Abstract

We consider looping issue of a mobile ad hoc network (MANET). Transient routing loops have been observed to form in Ad-hoc Networks running the MANET routing protocol with Link Layer Notification (LLN). Even when only a small quantity of the traffic may enter these loops and only for brief time, the effect is to significantly increase the impact on the surrounding network and its traffic thus degrading end-to-end transmission. The use of MANET routing protocols with LLN, together with loop detection and discarding of looping packet to negate the detrimental effects on surrounding traffic is found to improve performance significantly.

Table of Contents

1.  Introduction
2.  Terminology
3.  Overview
4.  Loop Detection
    4.1.  Mid Detection
    4.2.  Post Detection
5.  Packet Discard
6.  MANET Routing Protocol Considerations
7.  Security Considerations
8.  References
§  Authors' Addresses
§  Intellectual Property and Copyright Statements

1.  Introduction

Some MANET routing protocols define Link Layer Notification (LLN). This allows a node's interface over which a unicast packet is sent to notify the routing protocol if the link layer fails to receive an acknowledgment of reception, indicating that the packet has likely been lost.

The routing protocol may then act on the given LLN trigger, usually simply by removing a record of link from its Information Bases that store necessary information for routing and neighbor discovery to be able to calculate and update routing table.

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 a network operating under routing is not always loop-free, and therefore is exacerbated by the use of LLN. Although LLN may result in a performance gain, the loops may have been seen to increase the hop-by-hop datagrams in networks and to also significantly impact the surrounding traffic.

In this document, we propose novel loop detection method to negate the detrimental effects of looping and improve performance significantly.

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [1].

2.  Terminology

This document uses the terminology defined in [2]-[4], as well as the following terms:

Loop Detection:

Detecting looping unicast IP packets.

Mid Detection:

Loop detection before actual looping occur by chcking source and next hop of unicast IP packets.

Post Detection:

Loop detection after actual looping have occurred by using DPD algorithms.

Duplicate Packet Detection (DPD):

Detecting packet which have been received.

Packet Discard:

Discarding unicast IP packet which is in the loop to suppress the effect of packet looping.

3.  Overview

In this document, novel "Loop Detection" methods for MANET are defined. There is LS (Loop Suppression) approach that can be used to avoid or suppress the effect of loops. "Loop Detection" techniques can be implemented separately from routing protocol. There are two different approaches called "Mid Detection" and "Post Detection" that can be used to detect loop in this document.

"Mid Detection" is loop detection algorithm before actual packet looping occur, and it is performed between MAC Layer and Network Layer. Each node checks received packet and its routing table. If source MAC address of received unicast IP packet is equal to next hop MAC address associate with destination of this unicast IP packet, node consider that loop will occur.

"Post Detection" is loop detection algorithm after actual packet looping have occurred, and it is performed at Network Layer. Each node use Duplicate Packet Detection (DPD) algorithms for unicast IP packets in the Post Detection, and duplicate packets are detected. These detected duplicate packet indicate packet looping. Thus node consider that loop have occurred. Note that DPD means duplicate unicast IP packet detection in this document. DPD algorithms specified in [2] is based on multicast packets, and it is different from algorithms specified in this document.

Even when only a small quantity of the traffic may enter these loops and only for brief time, the effect of this packet looping is to siginificantly increase the impact on the surrounding network. Therefore, detected loop must be removed from routing table and packet in the loop must be discarded. In case that node detect loop in this method, node stops forwarding and discards looping packet to negate the detriminal effects of looping traffic in this method.

Fig. 1 shows an example topology of these algorithms, and Fig. 2 shows protocol stack model for loop detection.

                      +--------+
                      |        | Destination
	    	      +--------+
		     /          \  (1)Link breakage
            +--------+           X
	    |        |            \
            +--------+             \
		   |                +--------+ (2)update
		   |      Mid       |        |    routing
            +--------+    Detection +--------+    table
	    |        |          ^  /
            +--------+  Packet /  /  /
                     \        /  /  / Looping Packet
                      \         /  v
                      +--------+ Post
                      |        | Detection
                      +--------+
                          |
                      +--------+
                      |        | Source
                      +--------+

   Fig. 1  An example topology of loop detection algorithms

               +---------------------------------------+
               |              Transport Layer          |
               +---------------------------------------+
               |               ip_output()             | \
               +-------- ^ ----------------------------+  +
               |         |          +----------------+ |  | Network
               |         +--------->| Packet Forward | |  | Layer
               |         |          +----------------+ |  |
   +---------+ | +----------------+          |         |  |
   | Packet  |<--| Post Detection |          |         |  |
   | Discard | | +----------------+          |         |  |
   +---------+ |         ^                   |         |  |
               +-------- | --------+-------- v --------+  +
               |      ip_input()   |     ip_output()   | /
               +-------- ^ --------+-------- | --------+
               |         |         |         |         |
   +---------+ | +---------------+ |         |         |
   | Packet  |<--| Mid Detection | |         |         |
   | Discard | | +---------------+ |         |         |
   +---------+ +-------- ^ --------+-------- v --------+
               |         |      MAC Layer              |
               +---------------------------------------+

    Fig. 2  Protocol stack model for loop detection.

4.  Loop Detection

This section defines two algorithms of the loop detection to avoid the effect of loops.

4.1.  Mid Detection

"Mid Detection" is loop detection algorithm, and it detects looping before actual looping occur, and basically, it is performed between MAC Layer and Network Layer. When a unicast IP packet are received, the following tasks MUST be performed.

1.

Source MAC address of received frame is temporary stored. Afterwards, it is named source MAC address.

2.

To check the next hop MAC address equal to the source MAC address, the next hop MAC address is resolved from the destination IP address of received frame. This address resolution would be achievwd from routing table and address resolution protocols, shown as follows,

*

In case of IPv4, Mid Detection gets MAC address from Address Resolution Protocol [3] cash.

*

In case of IPv6, Mid Detection gets MAC address information from Neighbor Discovery Protocol for IP Version 6 (NDP) [4].

3.

If source MAC address is equal to next hop MAC address, then Mid Detection consider that loop occur. Therefore "Packet Discard" MUST be performed to suppress the effect of looping packets.

4.2.  Post Detection

"Post Detection" is loop detection algorithm after actual packet looping have occurred, and basically, it is performed at Network Layer.

"Post Detection" mechanism is based on DPD technique. DPD detects packet which have been received already. DPD algorithms such as S-DPD and H-DPD specified in [2] MAY be sufficiently usable in this "Post Detection" mechanism. But DPD algorithms specified in [2] are only for multicast IP packets, and they are operated 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.

Duplicate packet which detected by DPD algorithms indicates that packet looping have occured. Therefore "Packet Discard" MUST be performed to suppress the effect of looping packets.

5.  Packet Discard

In case that looping is detected by "Mid Detection" or "Post Detection", following tasks MUST be performed about received unicast IP packets which is in loop.

-

In case that looping is detected by "Mid Detection", received unicast IP packet MUST NOT be send to Network Layer, and this received unicast IP packet MUST be discarded.

-

In case that looping is detected by "Post Ditection", received unicast IP packet MUST NOT be forwarded even if it is considered to be forwarded, and this received IP packet MUST be discarded.

6.  MANET Routing Protocol Considerations

This loop detection techniques are implemented separately from routing protocol. Thus both pro-active and re-active routing can be applied this loop detection. Detected loop information MAY be used by routing protocol for route calculation and other purposes. How this detected loop informations are used in routing protocol is out of the specification.

7.  Security Considerations

This document does not specify any security considerations.

8.  References

[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.

[2] J.Macker, et al., "Simplified Multicast Forwarding for MANET", draft-ietf-manet-smf-05 (work in progress), June 2007

[3] David C. Plummer, "An Ethernet Address Resolution Protocol", RFC 826, November 1982

[4] T. Narten, E. Nordmark, W. Simpson, "Neighbor Discovery for IP Version 6 (IPv6)", RFC 2461, December 1998

Authors' Addresses

Full Copyright Statement

Copyright © The IETF Trust (2007).

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.

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, THE IETF TRUST 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.

Intellectual Property

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.