Project

General

Profile

Statistics
| Branch: | Tag: | Revision:

gdp / doc / internal / gdp-proto-v4-proposal.md @ master

History | View | Annotate | Download (11 KB)

1 7f982ac3 Eric Allman
% GDP Protocol Version 4 Proposal
2
% Eric Allman
3
% 2018-01-30
4 e253c81d Eric Allman
5 b71091a6 Eric Allman
Everything here is for discussion.
6
7
Principles
8 7f982ac3 Eric Allman
==========
9 b71091a6 Eric Allman
10
These are guiding principles for this proposal.
11
12
* What we have previously called the routing layer is broken up
13 afab5d96 Eric Allman
  into three sub-layers: a "forwarding" (a.k.a. "switch") layer that
14 b71091a6 Eric Allman
  shovels PDUs from a source to a destination as quickly as
15 afab5d96 Eric Allman
  possible, a "routing" layer that deals with advertisements,
16
  DHT lookup, etc., and an "ingress/egress layer" that deals with
17
  communications between GDP Principals (notably clients and log
18
  servers) and the rest of the routing/switching infrastructure.
19
20
* This description defines only the PDU used for the ingress/egress
21
  layer.  Other details such as Time to Live (TTL), fragmentation,
22
  and sequencing are not discussed.
23 b71091a6 Eric Allman
24
* "End to end" PDU contents should be in some language-agnostic format
25
  (such as Protocol Buffers or Cap'n Proto).
26
27
* End-to-end PDU contents should be opaque to the switching layer; in
28
  particular, it should be possible for it to be encrypted.
29
30
* Implementation of some operations (e.g., delivery of subscribed
31
  data) should play well with multicast.
32
33
* Size matters.  PDU headers need to be constrained.  In particular,
34
  the addresses (totaling 64 bytes when expanded) are just too large;
35
  they need to be encodable into a "FlowID", which can be thought of
36
  as a cache of common header information.
37
38
* Implementation matters.  Notably, forwarders should be able to view
39
  most of the PDU as opaque (not just the data), and should be optimized
40
  for speed.  In particular, forwarder-based header information should
41
  _not_ be encoded in a format that requires that a complex data
42
  structure be unserialized and reserialized.
43
44
45
Definitions
46 7f982ac3 Eric Allman
===========
47 b71091a6 Eric Allman
48
* FlowID: a mechanism for encoding source and destination information
49
  into a smaller size to optimize bandwidth utilization.
50
51
* Forwarding: the process of transmitting a PDU from a source to
52
  a destination, with the assumption that the endpoints are already
53
  known.  If they are unknown, the Routing layer must get involved.
54
55
* Octet: a single eight-bit data element.  This is the network term
56
  for a "byte" (but since some architectures have non-eight-bit
57
  bytes, "octet" is used instead).
58
59
* Packet: A data block that can be transmitted intact over an
60
  underlying network protocol.  Depending on the context, this might
61
  be limited by physical constraints (e.g., the maximum size of an
62
  ethernet frame) or by logical constraints (e.g., the maximum
63
  chunk size in SCTP).
64
65
* PDU (Protocol Data Unit): A block of data representing a single
66
  actionable unit (e.g., command or response).  In some cases
67
  multiple PDUs might be encoded into a larger "Transport PDU".
68
69
* Routing: determining the location of a destination.
70
71
72 e253c81d Eric Allman
Protocol Overview
73 7f982ac3 Eric Allman
=================
74 b71091a6 Eric Allman
75 afab5d96 Eric Allman
Every PDU consists of two parts.  The first portion is the Protocol
76
Header.  This is binary encoded, and intended to contain all the
77
information that the Switching Layer needs to route packets
78
(assuming that layer has the necessary routing information already
79
cached).  It is designed to be small and fast.
80 b71091a6 Eric Allman
81
The second portion is the Payload.  This is intended to be encoded
82
in some industry-standard, platform agnostic encoding.  Popular
83
examples include ProtoBuf and Cap'n Proto.  The contents of the
84 afab5d96 Eric Allman
Payload is message dependent.
85 b71091a6 Eric Allman
86
This alternative assumes that we are running over some Layer 4
87
protocol that gives us reliable, ordered transmission of arbitrarily
88
sized PDUs (for example, TCP).  That would make this a Layer 5
89
protocol.
90
91
92
### Protocol Header
93
94
Details are shown after the table.  The **Alternative** field
95 afab5d96 Eric Allman
relates to the flags indicated in the **Flags** field.  [[_Note:
96
these have been changed, so the **Alternative** column is not
97
accurate at this time._]]
98 b71091a6 Eric Allman
99
100
| Offset 	| Len 	| Alternative 	| Detail								|
101
|-------:	|----:	|-------------	|-------------------					|
102
|      0	|   1	|				| Magic/Version [1]						|
103 afab5d96 Eric Allman
|	   1	|   1	|				| Header Length	/ 4 [2]					|
104
|	   2	|   1	|				| Flags/Control [3]						|
105
|      3	|   1	|				| Reserved (MBZ) [4]					|
106
|      4	|   2	|				| Payload Length [5]					|
107
|      6 	|   4?  | IFLOWID      	| Initiator FlowID						|
108
|      - 	|   4?  | RFLOWID      	| Return FlowID							|
109 b71091a6 Eric Allman
|      - 	|  32  	| GDPADDR     	| Destination Addr						|
110
|      - 	|  32  	| GDPADDR     	| Source Addr							|
111
|      -	|   V	|				| Options								|
112 afab5d96 Eric Allman
|	   -	| 0-3	|				| padding								|
113 b71091a6 Eric Allman
114
115 8597bd33 Eric Allman
[1]	Magic and Version identify this PDU.  Must be 4.
116 b71091a6 Eric Allman
117
[2] Size of header in units of 32 bits.  This starts at offset
118
	zero and includes the options.  This constrains the header to at
119 afab5d96 Eric Allman
	most 1020 octets.  It must be at least 2 [or more for addresses
120
	and flow ids?].
121
122
[3] Flags/Control is a multipurpose field.  The low-order three
123
	bits define the address fields.  If zero, there are two 32
124
	octet (256 bit) fields designating the destination and source
125
	addresses.  Other values are to support address compression
126
	and are reserved.  If the high order (0x80) bit is set, the
127
	next four bits are a command for Principal-Router communication,
128
	where a Principal can be either a GDP client or a GDP log
129
	server.  Such values are defined below.  If the high order
130
	bit is zero the remaining bits must be zero as well.  This is
131
	reserved for future expansion.
132
133
[4] The reserved field is partly to improve memory alignment but
134
	more importantly to allow for future expansion.  It is
135
	immediately before Payload Length so that it could be used
136
	to allow larger payloads, should they become necessary.
137
	It must be zero when the PDU is generated, and ignored when
138
	the PDU is read.
139
140
[5] Size of Payload in units of 8 bits.  It is represented in network
141 b71091a6 Eric Allman
	byte order (big endian).  This constrains the maximum size of a
142 7f68506d Eric Allman
	PDU payload to 2 ^ 16 - 1 = 65,535 octets.
143 b71091a6 Eric Allman
144 afab5d96 Eric Allman
The total size of the PDU is the sum of the Header Length and the
145
Payload Length.  Note that since the header length must be a multiple
146
of four there will always be two octets of options which will
147
often be zero.  If this is a problem we can reduce the header size
148
to be in units of 16 bits, at the cost of allowing less space for
149
options.  However, since IPv4 only allows 40 octets for options,
150
this is unlikely to be a big issue.
151 b71091a6 Eric Allman
152
The source and destination address can be specified either explicitly
153
or by encoding into a FlowID.  Mechanisms for managing FlowIDs are
154
[[_being explored by Nitesh_]].
155
156
[[_Note to Nitesh: I'm using "Initiator FlowID" instead of just
157
"FlowID" to avoid confusion between the specific and the generic.
158
For example, consider the statement "the FlowID and the Return
159
FlowID are both FlowIDs."_]]
160
161
162
### Flag Bits
163
164 afab5d96 Eric Allman
None defined at this time — must be zero when a PDU is
165
created.  PDU interpreters should ignore these bits.
166 8597bd33 Eric Allman
167 b71091a6 Eric Allman
168
### Options
169
170
Options are used to convey additional information to the switching
171 8597bd33 Eric Allman
layer, e.g., Quality of Service.  These are for future use.  Note
172
that options are included in the header size, so routers that do
173
not support options can skip this part without additional processing.
174 b71091a6 Eric Allman
175 d173aaa7 Eric Allman
Each Option starts with a single octet of option id.  The bottom
176
three bits of the option id also contains the length of the option
177
value as a power of two (e.g., a value of zero means zero bytes, one
178
one means one octet, two means two octets, four means eight octets,
179
etc.).  If the bottom three bits are 0x7 then the length is taken
180
from the octet immediately following the id without scaling (that
181
is, a value of five means five octets, not 2^5 = 32).
182 b71091a6 Eric Allman
If the length is encoded in in the option id octet, that length is
183 d173aaa7 Eric Allman
part of the option id.  For example, option 0x10 and 0x13 are
184 b71091a6 Eric Allman
different options, the former of length zero and the latter of length
185 d173aaa7 Eric Allman
four.  In comparison, the size of option 0x87 is contained in the
186 b71091a6 Eric Allman
following octet, and the size is not part of the option id, so
187 d173aaa7 Eric Allman
0x87 0x00 and 0x87 0x04 are the same option, with values of length
188 b71091a6 Eric Allman
zero and four respectively.
189
190
Unrecognized options must be ignored (but passed on).
191
[[_Perhaps there should be some encoding that indicates that an
192
option is essential, in the sense of the CoAP [RFC7252] distinction
193
between "Critical" and "Elective" options._]]
194
195
Options:
196
197 afab5d96 Eric Allman
| Value		| Name			| Detail					|
198
|------:	|-----:			| -----------------			|
199
| 0x00		| OPT\_END		| End of Option List		|
200 b71091a6 Eric Allman
201
[[_Need to define other options._]]
202
203
Note that some Options may be implied by a FlowID, in the same way
204
that a 256-bit address is implied by a FlowID.
205
206 afab5d96 Eric Allman
[[_It might be useful to have a compact (single octet) encoding
207
for options with length 32, since that is the length of a GDP
208
address._]]
209
210 b71091a6 Eric Allman
211 e253c81d Eric Allman
Payload Encoding
212 7f982ac3 Eric Allman
================
213 b71091a6 Eric Allman
214 8597bd33 Eric Allman
[[_Move this into another document, or see the code._]]
215 b71091a6 Eric Allman
216
217 afab5d96 Eric Allman
Client-Router Protocol
218 7f982ac3 Eric Allman
======================
219 b71091a6 Eric Allman
220 afab5d96 Eric Allman
Sometimes a GDP principal (client or log server) needs to communicate
221
with the routing layer, for example, for advertising known names.
222
This is done using the Flags/Control field.  If the high order (0x80)
223
bit is set in that octet, this PDU is either directed to or sent
224
from the routing layer.  This approximates ICMP in IP networks.
225
226
Note that the bottom three bits of this octet are not part of the
227
Client-Router protocol, as they are used to represent the address
228
format.
229
230
[[_This is temporary, just so Rick and Eric can get something, anything,
231
working.  We know advertising has to be done using certs._]]
232
233
The following table assumes that the Flags/Control field is masked
234
with 0xf8 (i.e., the bottom three bits are ignored):
235
236
| Value		| Name			| Detail							|
237
|------:	|-----:			| -----------------					|
238
| 0x80		| FORWARD		| Forward PDU [1]					|
239
| 0x90		| ADVERTISE		| Advertise names [2]				|
240
| 0x98		| WITHDRAW		| Withdraw names [2]				|
241
| 0xF0		| NOROUTE		| Cannot find route [3]				|
242
243
[1] FORWARD passes the PDU to another entity (which could be a
244
    router or a server), strips off the header, and processes
245
	the payload as though it were a PDU.  This can be used for
246
	source routing, particularly during some operations
247
	associated with replication.  It is the equivalent of the
248
	IP-in-IP protocol (4) in IPv4.
249
250
[2]	ADVERTISE asserts to the routing layer that the source is
251
	willing to respond on behalf of the list of 256-bit names
252 e35bf5f3 Eric Allman
	listed in the payload.  WITHDRAW removes that assertion.
253 afab5d96 Eric Allman
	[[_These need to be replaced with a challenge-response
254
	certificate exchange._]]
255
256
[3]	Sent from the routing layer to a GDP Principal when that
257
	Principal has sent to an address that cannot be found.
258
	Approximately equivalent to an ICMP "unreachable" code.
259
	The source address must be the unroutable name.
260 b71091a6 Eric Allman
261
262
Things to Address
263
=================
264
265
* Should multiple commands be permitted in one PDU?  If so, the
266
  Payload and Trailer information needs to be in some sort of
267
  array.  Everything in these commands MUST have the same
268
  source and destination addresses, since this is specific to the
269
  routing/forwarding layer (i.e, forwarding of a partial PDU is not
270
  permitted).
271 8597bd33 Eric Allman
272 afab5d96 Eric Allman
* Because the header length is specified as the number of 32 bit
273
  words, and header with no options ends on a 16-bit boundary, most
274
  headers will probably have two bytes of padding.  This seems
275
  wasteful.
276
277
* Nitesh doesn't include WITHDRAW in his prototype, using timeouts
278
  instead.  Do we need it?
279 7f982ac3 Eric Allman
280
<!-- vim: set ai sw=4 sts=4 ts=4 : -->