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