Mobile Ad hoc Networks Working Group P. Lau Internet-Draft The University of Memphis Intended status: Experimental December 31,2016 Expires: July 3, 2017 Topology Refresh Protocol (TRP) draft-peterlau-manet-topology-refresh-00 Abstract The topology refresh protocol is intended for use in mobile social networks where user nodes announce their presence when they move into contact with the network, see all existing users, know when old users have left the network and new ones join the network, and communicate with each other over optimal paths established on the fly. TRP is a very lightweight protocol but does require user nodes periodically broadcast their ids along with some personal information to the network. These broadcasts serve the dual purpose of announcing users' presence in the social network and establishing a complete topology of end-to-end optimal paths. Individual user controls her "radius of users" based on the number of hops and physical distance between her and the others. User nodes independently choose their ids and dynamically resolve any duplicated ones. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on July 3, 2017. Copyright Notice Copyright (c) 2016 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 3 5. Applicability Statement . . . . . . . . . . . . . . . . . . . 3 6. Generic Message Formats . . . . . . . . . . . . . . . . . . . 4 7. Forwarding Table Entry . . . . . . . . . . . . . . . . . . . 6 8. Type 2 Control Messages . . . . . . . . . . . . . . . . . . . 6 8.1. Generating Type 2 Control Messages . . . . . . . . . . . . 6 8.2. Processing Type 2 Control Messages . . . . . . . . . . . . 7 8.3. Transmitting Type 2 Control Messages . . . . . . . . . . . 8 9. Resolving Duplicated Node Identifications (Id's) . . . . . . 8 10. Generating Type 8 and 9 User Messages . . . . . . . . . . . . 8 11. Generating of Type 10 Acknowledgement Messages . . . . . . . 9 12. Processing of Transit Type 8 and 9 Messages . . . . . . . . . 9 13. Transmitting Type 8 and 9 Messages . . . . . . . . . . . . . 9 14. IANA Consideration . . . . . . . . . . . . . . . . . . . . . 10 15. Security Considerations . . . . . . . . . . . . . . . . . . . 10 16. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 16.1. Normative References . . . . . . . . . . . . . . . . . . 10 16.2. Informative References . . . . . . . . . . . . . . . . . 10 1. Introduction The intended application of this memo is nearby mobile social network in which users would like to know who are nearby and socialize with them on the fly. The delay performance study, carried out in [WTS2015], demonstrates the adequacy of TRP for mobile social network application. Existing protocols and methods were not conceived to support such an application. The delay sensitive nature of the application renders the methods and protocols like [Epidemic] [Abhijeet] [RFC6693] designed for delay-tolerant mobile ad-hoc network inapplicable. The expected frequent path breaks and numerous simultaneous user conversions in a social network make the on-demand routing protocols [RFC3561] [RFC4728] inefficient. Proactive protocols like [RFC3626] [RFC3684] are complex and heavy on CPU. Most important, all of these protocols require prior knowledge of the identification of participating nodes. Generally, membership of mobile social networks is open to anyone coming into contact with the network and is constantly changing as users are moving in and out of the network from time to time. Thus, acquiring prior knowledge of dynamic membership is difficult, if not impossible. This memo defines a light weight protocol motivated to enable nearby social network that requires neither prior knowledge of membership nor infrastructure support (such as sending GPS coordinates to a central site for processing). TRP user nodes cooperate to forward data for each other. 2. Requirements The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT" "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL", when they appear in this document, are to be interpreted as described in BCP 14, RFC 2119 [RFC2119]. 3. Terminology Radius of users With respect to user A, radius of users are those users around A that are either within the maximum hop count or maximum physical distance from A, or both, specified by the users. 4. Protocol Overview TRP is a table-driven proactive data forwarding protocol and at the same time allows users to announce their presence to the network. A node, wishing to be contacted, periodically broadcasts control messages about itself to the network. A node, receiving control messages, caches an optimal path to each of the originators of the control messages. The result is four-fold: (1) a complete topology of end-to-end paths is constantly evolving that closely follows the movement of user nodes; (2) a complete list of current users is constantly updating at every user node; (3) the need for neighbor discovery is obviated; and (4) the need for link break detection and repair is also obviated. 5. Applicability Statement The TRP is designed for high mobility infrastructureless nearby social network for users of smart phone or any devices equipped with wifi. The network is expected to be small controlled by individual users to around one hundred nodes. Anyone can join and leave a TRP enabled social network anytime and anywhere at their pleasure. No confidential information is expected to be exchanged between users and generally security is not a concern. Establishing a secured connection between two TRP users is beyond the scope of this memo. 6. Generic Message Formats 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version|Msg Typ|B|D|R|R|R|R|R|R| Next Node Id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Recipient Node Id | Sender Node Id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Max Hop | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time To Live (TTL) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | Type 2 Period | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | This Node Id | Signature | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Battery | Distance | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | GPS Coordinate | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Body | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Version Protocol version. The initial version is 0. Message Type Type 0-1: Reserved. Type 2: Control messages. Type 3-7: Reserved. Type 8: Variable length user messages that require the destination nodes to acknowledge the receipt of them. Type 9: Variable length user messages that do not require Acknowledgement. Type 10: Acknowledgement messages. Type 11-15: Reserved. B Battery flag. A '1' indicates the use of battery energy to select optimal paths, '0' indicates otherwise. D Distance flag. A '1' indicates the use of Distance field to limit the maximum distance from this node to other nodes and '0' indicates otherwise. If both B and D are '0', the Battery, Distance, and GPS Coordinate bytes SHOULD BE removed. If B is '1' and D is '0', the GPS Coordinate bytes SHOULD BE removed. R Reserved. Sent as 0 and ignored on reception. Next Node Id The node to which this message is forwarded. All ones if this message is broadcast to all the neighbors. Recipient Node Id The target node of this message. All ones if this message is broadcast to all the nodes. Sender Node Id The originator node of this message. Max Hop The number of hops this message can traverse before being dropped. Default to 20 hops. Hop Count The number of hops the message has traversed so far. Set to 1 at the originating node. Time To Live Message delay, in msec. The message is dropped when TTL has reached 0. Default to 10 seconds. Sequence Number The sequence number for this message. Type 2 Period The frequency of sending type 2 messages. Default to 3 seconds or adjusted by the TRP. This Node Id The node from which this message was forwarded. Signature A changing random number for detecting duplicated node id. Battery The smallest remaining energy amount the nodes along the path from the sender to this node. Distance A value for limiting the distance between the originator node and this node. Default to 100 (1 mile, in unit of 0.01 mile). GPS Coordinate GPS coordinate of the message originator node. Message Body Type 2: Originator's personal information. The content and format are out of the scope of this memo. How the user list is generated and presented to the user is application dependent. Type 8-9: Variable length user message. Type 10: Null. The Type 2 Period, This Node Id, Signature, Battery, Distance, and GPS Coordinate fields are used in type 2 control messages only. 7. Forwarding Table Entry Each node SHALL maintain a message forwarding table. Each table entry has the following six fields: Destination Node Id The node id of the recipient node. Forwarding Node Id The next hop node id. Sequence Number The value copied from the type 2 message with which this entry is created or updated. Hop Count A value for keeping track of the number of hops from this node to the destination node. Remaining Energy The value copied from the type 2 message. Time Out The entry age beyond which it is deleted. Default to Type 2 Period + 5 seconds. 8. Type 2 Control Messages 8.1 Generating Type 2 Control Messages If a node desires to participate in a TRP enabled social network, it SHALL periodically broadcast type 2 messages for the purpose of identifying itself to the network, making any new nodes aware of its existence, and reaffirming its presence to existing ones. The period of sending type 2 messages SHOULD BE default to 3 seconds. A node SHALL compose a type 2 message with the following fields and values: Message Type 2. B and D 0 or 1 depending on the application. R 0. Next Node Id All one's. Recipient Node Id All one's. Sender Node Id This node's own id. Max Hop 20 or user provided value. Hop Count 1. Time To Live 10,000 or user provided value. Sequence Number Current sequence number + 1. Type 2 Period 3 or user provided value. This Node Id This node's own id. Signature Currently used random number or a new one. Battery Remaining energy of this node. Distance 100 or user provided value. GPS Coordinate The current GPS coordinate of this node. Message Body Information supplied by users. 8.2 Processing Type 2 Control Messages When a node receives a type 2 message, it SHOULD discard the message if the message's Sender Node Id matches its own id (because a node may receive its own control messages through other nodes). When the message is originated from another node but with the D flag set, the node SHOULD discard the message if the distance between itself and the originating node exceeds the message's Distance value. If the message has not been discarded in the above, the node SHOULD search its forwarding table using the Sender Node Id extracted from the message as the search key. If the search returns an entry, the node SHOULD take the following actions in order they are listed: If the entry is timed out, delete the entry. If the entry's sequence number is smaller than the message's sequence number, delete the entry. If the entry's sequence number is larger than the message's sequence number, delete the message. If the two sequence numbers are the same, the node SHOULD take the following actions in the order the are listed: If the entry's hop count is larger than the message's hop count, delete the entry. If the entry's hop count is smaller than the message's hop count, delete the message. If the two hop counts are the same and the entry's Remaining Energy is smaller than the message's Battery, delete the entry; otherwise delete the message. If the search returns "entry not found" or the entry is deleted as described above, the node SHALL create a new entry with the destination Node Id, Forwarding Node Id, Sequence Number, Hop Count, and Remaining Energy fields copied from the message's Sender Node Id, This Node Id, Sequence Number, Hop Count, and Battery. Time out is set to the message's Type 2 Period + 5. 8.3 Transmitting Type 2 Control Messages The node SHOULD transmit local type 2 messages without modification. If the message is forwarded, the node SHOULD set the Hop Count, TTL, This Node Id, and Battery fields to the message's Hop Count + 1, message's TTL - time spent in the node, the node's own id, and the minimum of the message's Battery and the node's remaining energy. The node SHOULD drop the message if the updated Hop Count exceeds MAX Hop or the updated TTL drops below zero. 9. Resolving Duplicated Node Identifications Each node independently chooses its own id. Inadvertently, two or more nodes may have chosen the same value. To detect id collisions, a sender node SHOULD periodically sign its control messages with a different random number in the Signature field. A sender SHOULD sign a new signature every 100 type 2 messages sent. Anytime a node receives a control message containing in the Sender Node Id field its own id but does not match its signature, the node SHOULD use a different id in the subsequent control messages. To minimize the probability of id collision, when the TRP is first turned on, the node MAY wait 10 seconds and pick a value, from outside the user list, for its own node id. 10. Generating Type 8 and 9 User Messages Users are periodically updated with a list of nearby users. If two users on the list desire to communicate, they exchange user messages. A user SHOULD send type 8 messages if she wants to make sure that the messages are received at the destination node. A user SHOULD send type 9 messages if she has no desire to know whether the messages have arrived at the destination. Type 8 and 9 messages SHOULD conform to the generic message format as follows: Message Type 8 or 9. B, G, and R 0. Recipient Node Id A value chosen from the user list. Sender Node Id The node id of the node sending this message. Max Hop The value used in the generated type 2 messages. Hop Count 1. Time To Live The value used in the generated type 2 messages. Sequence Number Current sequence number + 1. Message Body Variable length information supplied by users. 11. Generating of Type 10 Acknowledgement Messages Upon receiving a type 8 message, the recipient node SHALL return a type 10 message to the sender. Type 10 messages SHOULD conform to the generic message format as follows: Message Type 10. B, G, and R 0. Recipient Node Id Type 8 message's Sender Node Id. Sender Node Id Type 8 message's Recipient Node Id. Max Hop Type 8 message's Max Hop. Hop Count 1. Time To Live The value used in the generated type 2 messages. Sequence Number Type 8 message's sequence number. Message Body Null. 12. Processing of Transit Type 8, 9, and 10 Messages A type 8, 9, 10 message, upon arrival to a node, SHALL BE delivered to the user if the Recipient Node Id matches the node's id. If the Recipient Node Id does not match the node's id, the message SHOULD be queued waiting to be forwarded to the next node. 13. Transmitting Type 8, 9, and 10 Messages The node SHALL look up the forwarding table for the Next Node Id using the message's Recipient Node Id as the search key. The node SHOULD transmit local type 8, 9, and 10 messages without further modification. If the message is forwarded, the node SHOULD increment the Hop Count by one, and decrement the TTL by the amount of time the message has spent in this node. If the look up does not return an entry, the node SHOULD buffer the message for the next transmission opportunity. If Hop Count exceeds Max Hop or TTL drops below zero, the node SHOULD drop the message. 14. IANA Considerations This memo has no IANA actions.SHOULD BE 15. Security Considerations Currently, TRP does not specify any special security measures. 16. References 16.1 Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [WTS2015] Peter S. Lau, "Topology refresh data forwarding protocol for opportunistic networks", Wireless Telecommunications Symposium (WTS), New York, New York, USA, April, 2015. 16.2 Informative References [Epidemic] A. Vahdat and D. Becker, "Epidemic routing for partially connected ad hoc networks," Technical Report CS-200006, Duke University, Apr. 2000. [Abhijeet] Abhijeet A. Bhorkar and Mohammad Naghshvar, "Adaptive Opportunistic Routing for Wireless Ad Hoc Networks" ACM Transactions on Networking, vol. 20, no. 1, pp. 243-256, Feb. 2012. [RFC6693] Lindgren, A., Doria, A., Davies, E., Grasic, S., "Probabilistic Routing Protocol for Intermittently Connected Networks", RFC 6693], August 2012. [RFC3561] Perkins, C., Belding-Royer, E., and Das S., "Ad hoc On-Demand Distance Vector (AODV) Routing", RFC 3561, July 2003. [RFC4728] Johnson, D., Hu, Y., and Maltz D., "The Dynamic Source Routing Protocol (DSR)for Mobile Ad Hoc Networks for IPv4", RFC 4728], February, 2007. [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. [RFC3684] Ogier, T., Templin F., and Lewis, M., "Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)", RFC 3684, February 2004. Author's Address Peter S. Lau Department of Electrical and Computer Engineering The University of Memphis Memphis, TN 35152 USA Email: peterlau@memphis.edu