Project

General

Profile

NDN Over WiFi Direct Protocol Specification

: Last Updated: 12/28/2016
: Allen Gong, UCLA

1. Introduction

1.1 Motivation

The following protocol design is intended for use in ad-hoc environments wherein there are no available WiFi or cellular networks. This protocol provides a means to which two WiFi Direct compatible devices can connect to one another in order to exchange and maintain information about available NDN Data prefixes. The following specification does not touch upon multi-hop communication, but its design is such that it should easily accommodate it if implemented.

1.2 Interfaces

The protocol assumes the existence of an underlying NDN forwarding layer, by which Interest and corresponding Data packets can be sent and received, among other common use cases. The following design also utilizes the Android WiFi Direct API as implemented by December 2016.

2. Overview

2.1 Model of Operation

The protocol design is focused on establishing not only connectivity but communication between multiple WiFi Direct enabled devices. For the protocol, devices are connected at the link layer via WiFi Direct, and all further communication is carried out through NDN semantics, including but not limited to: Face creation, packet exchange, etc.

The model of operation is easiest understood via the example. Let’s say that there are two appropriate Android devices, A and B, that wish to connect under this protocol.

+----------+
|    A     |
+----------+

+----------+
|    B     |
+----------+

A and B will call discoverPeers(), as specified in the Android WiFi Direct documentation, and eventually be presented with their own view/list of available devices. For this example, we assume A and B are the only devices within range of each other, so A would only see B, and vice versa.

Currently, the protocol is aggressive in that it will attempt to connect() to as many appropriate peers up to a maximum as possible. Both A and B will attempt to connect to one another. Assuming both devices accept the WiFi P2p group invitations, A and B will negotiate and finally connect, with one device chosen as the Group Owner (GO) and the other a Non-Group Owner (Non-GO). At this stage, the only addressing information presented by the API to developers is the WiFi Direct IP address of the GO, which is hardcoded to 192.168.49.1. Let’s say device A here is the GO, and B is a Non-GO. For completeness, let’s say that B therefore has the WiFi Direct IP of 192.168.49.142.

+------------+
|   A (GO)   | // (Group Owner) IP: 192.168.49.1
+------------+
      |
      |
+------------+
|  B (N-GO)  | // (Not Group Owner) IP: IP: 192.168.49.142
+------------+

After successful group formation, both devices will register their local-hop probe routes, by which will satisfy incoming probe Interests, discussed later. An example could be that A registers /localhop/wifidirect/192.168.49.1 expecting other nodes to use it to probe. Exact format specifications are discussed in section 3.

Both devices then begin the Probe Procedure, which can be summarized as:
Enumerate all entries in the FIB relevant to probing (excluding local ones)
For each entry
Send a probe Interest, with more information appended to the name
On response to a), parse the Data prefixes and update (register/unregister) state as necessary
Set a timer that on timeout will restart the entire procedure again

Since device B knows that it is not the Group Owner and A only knows about itself, B must take initiative to make itself known to the GO. Device B will create a unicast Face using the WiFi Direct IP address (provided by the API) to the GO, and register the “/localhop/wifidirect/” route to this Face. Thus, the next time the Probe Procedure runs, a probe Interest will be sent to the GO.

Probe Procedure - Interest sent

+------------+
|   A (GO)   | (Group Owner) IP: 192.168.49.1
+------------+
      |   ^
      |   |  Send Interest with name
      |   |  /localhop/wifidirect/<GO-IP>/<IP>/probe
      |   |
+------------+
|  B (N-GO)  | (Not Group Owner) IP: IP: 192.168.49.142
+------------+

The GO (Device A) will realize that it has yet to have seen this new peer, Device B, and immediately create a complementary Face towards B. B’s IP address can be found in the name of the incoming Interest (see section 3). In addition, A will respond to B’s probe Interest with information regarding available Data prefixes. This is done via enumerating FIB entries once more, and including only those deemed pertinent to Data. More about this can be found in section 2.2.

On the next iteration of Probe Procedure, both Device A and B will send probe Interests to one another, again, updating any state (registered routes, etc.) as necessary. The only difference is that where the GO will return all registered Data prefixes, the Non-GO only returns those that are handled locally, for instance, by an upper level application. This is to avoid temporary circular routing, wherein a GO may end up believing a locally handled prefix is available at another node.

To handle coming and going peers, all peers in the group will keep track of the number of consecutive timeouts for expressed probe interests. If the number reaches a specified threshold, the device will remove all state pertaining to that peer, including but not limited to: Faces, routes, and peer information. If the peer is to later re-join the group, the protocol will treat this just like it would for any new peer.

New peers will simply follow the same logic above.

2.2 Model Specifics

The following section describes the specifics of the values used in the protocol, and especially those that were left vague in the previous subsection.

2.2.1 Peer Discovery

Given that peers come and go and the current implementation of WiFi Direct does not persistently check for peers, the discoverPeers() call must be called periodically. This should be done no more than once every 30 seconds, as frequent calls may cause large overhead and energy consumption on certain devices.

The current implementation runs peer discovery every 30 seconds.

2.2.2 Peer Connection Limit

As stated in 2.2, the protocol is aggressive when it comes to connecting to available peers. However, for now, there should be a maximum of 5 peers automatically connected to at any time. No assumptions are made about “group affinity”, such as if one device leaves momentarily and another takes its place, there is no guarantee that it will be able to rejoin that same group if there is no available space.

2.2.3 Local-hop Probe Routes

On successful group formation or join, devices will register an important route to some localhost Face. This is the local hop probe route, which has the form:

/localhop/wifidirect/<This Device’s IP>

Other peers will express Interests with more information appended to the name to this route in order to retrieve information on Data prefixes.

2.2.4 Face Creation

Faces can be either UDP or TCP unicast.

2.2.5 Probe Procedure

To clarify the specifics:

  • When enumerating all entries in the FIB, look for instances of /localhop/wifidirect/192.168.49.x or simply /localhop/wifidirect. The latter assumes that /localhop/wifidirect will be a protocol specific name and is unused outside of the implementation. Exclude any localhost Faces.

  • For each appropriate entry:

    • Construct an Interest with name

      /localhop/wifidirect/192.168.49.x/<This Device’s WiFi D. IP>/probe?MustBeFresh=True

    • Express the above Interest

    • On Data response, parse the response of Data prefixes, and registe or unregister routes as necessary. The end effect is replacing all previously registered routes for this peer with the prefixes found in this response. Reset timeout counter for this peer to zero.

  • Set a timer for the next iteration.

2.2.6 Probe Procedure Timer

The delay between successful iterations of the Probe Procedure should be no more frequent than once per every 10 seconds. There are considerations as to what this value should be set to, as one should balance consistency and performance cost.

The current implementation runs the Probe Procedure every 12 seconds.

2.2.6 Probe Response

When a node receives a probe Interest, it responds by enumerating all FIB entries registered with the local NFD, and excludes any entries with prefixes beginning with “/localhop” or “/localhost”. Further filtering is left up to upper layer applications using this protocol.

2.2.7 Peer/Group changes

Peers will come and go. All peers in a group will keep track of the number of successive timeouts encountered during operation. If this number exceeds 5 (i.e. the peer did not respond to 5 consecutive probe Interests), the probing peer will declare this other peer as no longer available.

The probing peer should destroy any created Faces and routes, and remove any state about the peer. This is to allow the protocol to treat potential re-joins just as it would any other new one.

3. Formats

3.1 Probe Interest

Probe Interests should always have the form:

/localhop/wifidirect/<Other Peer’s IP>/<This Device’s IP>/probe?MustBeFresh=True

Recall all IP addresses here are WiFi Direct (192.168.49.x) addresses.

The MustBeFresh flag is set to True so that nodes will always return their most up to date Data prefixes. The inclusion of the WiFi Direct IP of the probing device allows the receiving node to distinguish the sender (e.g. to create new Faces if necessary).

3.2 Probe Data

Probe Data packets should be in the form:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           4-Byte number N of Data prefixes in response        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| prefix1\n                                                     |
| prefix2\n                                                     |
| ...                                                           |
| prefixN\n                                                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

In other words, it should be a header containing the number of prefixes in this response, immediately followed by newline separated Data prefixes. This way, if we wanted to add new sections to the response, we would immediately know where the beginning and ending of the Data prefixes were.

4. Discussion

There are a few points of the protocol that are still very debatable. Timer values are always tricky, as one is trying to balance performance and energy costs with consistency and availability. One thing that should be considered in any implementation is to set the timer values to important events in a way such that probing and peer discovery never occur at the same time. That is, to avoid setting one as a multiple of the other. The above specification gives the developer freedom to manipulate these timer values as needed, with some lenient lower bounds.

The response format for probe Data packets could have been in a compact form, such as JSON. There is nothing wrong with using JSON, and this is something that can be looked into when there is more information transferred while probing.

One last interesting thing to note is multi-hop support. The current protocol inherently supports multi-hop communication, with the exception of one point. The constraint that Non-GOs will return only the Data prefixes handled locally when probed must be relaxed so that if a device is a part of multiple groups (i.e. it connects two groups enabling multi-hop communication) it will return all data prefixes it has knowledge about. This is but one possible solution. The other semantics of the protocol will work just fine otherwise.