Project

General

Profile

NDN Over WiFi Direct Protocol Specification » History » Version 3

Alex Afanasyev, 01/31/2017 12:33 PM

1 1 Alex Afanasyev
# NDN Over WiFi Direct Protocol Specification
2
3
: Last Updated: 12/28/2016
4
: Allen Gong, UCLA
5
6 3 Alex Afanasyev
{{>toc}}
7 1 Alex Afanasyev
8
## 1. Introduction
9
10
### 1.1 Motivation
11
12
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.
13
14
### 1.2 Interfaces
15
16
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.
17
18
## 2. Overview
19
20
## 2.1 Model of Operation
21
22
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.
23
24
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.
25
26
    +----------+
27
    |    A     |
28
    +----------+
29
30
    +----------+
31
    |    B     |
32
    +----------+
33
34
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.
35
36
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.
37
38
    +------------+
39
    |   A (GO)   | // (Group Owner) IP: 192.168.49.1
40
    +------------+
41
          |
42
          |
43
    +------------+
44
    |  B (N-GO)  | // (Not Group Owner) IP: IP: 192.168.49.142
45
    +------------+
46
47
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.
48
49
50
Both devices then begin the Probe Procedure, which can be summarized as:
51
Enumerate all entries in the FIB relevant to probing (excluding local ones)
52
For each entry
53
Send a probe Interest, with more information appended to the name
54
On response to a), parse the Data prefixes and update (register/unregister) state as necessary
55
Set a timer that on timeout will restart the entire procedure again
56
57
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/<GO IP>” route to this Face. Thus, the next time the Probe Procedure runs, a probe Interest will be sent to the GO.
58
59
Probe Procedure - Interest sent
60
61
    +------------+
62
    |   A (GO)   | (Group Owner) IP: 192.168.49.1
63
    +------------+
64
          |   ^
65
          |   |  Send Interest with name
66
          |   |  /localhop/wifidirect/<GO-IP>/<IP>/probe
67
          |   |
68
    +------------+
69
    |  B (N-GO)  | (Not Group Owner) IP: IP: 192.168.49.142
70
    +------------+
71
72
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.
73
74
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.
75
76
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.
77
78
New peers will simply follow the same logic above.
79
80
### 2.2 Model Specifics
81
82
The following section describes the specifics of the values used in the protocol, and especially those that were left vague in the previous subsection.
83
84
#### 2.2.1 Peer Discovery
85
86
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.
87
88
The current implementation runs peer discovery every 30 seconds.
89
90
#### 2.2.2 Peer Connection Limit
91
92
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.
93
94
#### 2.2.3 Local-hop Probe Routes
95
96
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:
97
98
    /localhop/wifidirect/<This Device’s IP>
99
100
Other peers will express Interests with more information appended to the name to this route in order to retrieve information on Data prefixes.
101
102
#### 2.2.4 Face Creation
103
104
Faces can be either UDP or TCP unicast.
105
106
#### 2.2.5 Probe Procedure
107
108
To clarify the specifics:
109
110
- 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.
111
112
- For each appropriate entry:
113
114
  * Construct an Interest with name
115
116
        `/localhop/wifidirect/192.168.49.x/<This Device’s WiFi D. IP>/probe?MustBeFresh=True`
117
118
  * Express the above Interest
119
120
  * 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.
121
122
- Set a timer for the next iteration.
123
124
#### 2.2.6 Probe Procedure Timer
125
126
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.
127
128
The current implementation runs the Probe Procedure every 12 seconds.
129
130
#### 2.2.6 Probe Response
131
132
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.
133
134
#### 2.2.7 Peer/Group changes
135
136
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.
137
138
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.
139
140
## 3. Formats
141
142
### 3.1 Probe Interest
143
144
Probe Interests should always have the form:
145
146
    /localhop/wifidirect/<Other Peer’s IP>/<This Device’s IP>/probe?MustBeFresh=True
147
148
Recall all IP addresses here are WiFi Direct (192.168.49.x) addresses.
149
150
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).
151
152
### 3.2 Probe Data
153
154
Probe Data packets should be in the form:
155
156
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
157
    |           4-Byte number N of Data prefixes in response        |
158
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
159
    | prefix1\n                                                     |
160
    | prefix2\n                                                     |
161
    | ...                                                           |
162
    | prefixN\n                                                     |
163
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
164
165
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.
166
167
## 4. Discussion
168
169
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.
170
171
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.
172
173
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.