8 presotto,philw@plan9.bell-labs.com
10 To transport the remote procedure call messages of the Plan 9 file system
11 protocol 9P, we have implemented a new network protocol, called IL.
12 It is a connection-based, lightweight transport protocol that carries
13 datagrams encapsulated by IP.
14 IL provides retransmission of lost messages and in-sequence delivery, but has
15 no flow control and no blind retransmission.
20 Plan 9 uses a file system protocol, called 9P [PPTTW93], that assumes
21 in-sequence guaranteed delivery of delimited messages
22 holding remote procedure call
23 (RPC) requests and responses.
24 None of the standard IP protocols [RFC791] is suitable for transmission of
25 9P messages over an Ethernet or the Internet.
26 TCP [RFC793] has a high overhead and does not preserve delimiters.
27 UDP [RFC768], while cheap and preserving message delimiters, does not provide
28 reliable sequenced delivery.
29 When we were implementing IP, TCP, and UDP in our system we
30 tried to choose a protocol suitable for carrying 9P.
31 The properties we desired were:
33 Reliable datagram service
37 Internetworking using IP
39 Low complexity, high performance
43 No standard protocol met our needs so we designed a new one,
44 called IL (Internet Link).
46 IL is a lightweight protocol encapsulated by IP.
47 It is connection-based and
48 provides reliable transmission of sequenced messages.
49 No provision is made for flow control since the protocol
50 is designed to transport RPC
51 messages between client and server, a structure with inherent flow limitations.
52 A small window for outstanding messages prevents too
53 many incoming messages from being buffered;
54 messages outside the window are discarded
55 and must be retransmitted.
56 Connection setup uses a two-way handshake to generate
57 initial sequence numbers at each end of the connection;
58 subsequent data messages increment the
59 sequence numbers to allow
60 the receiver to resequence out of order messages.
61 In contrast to other protocols, IL avoids blind retransmission.
62 This helps performance in congested networks,
63 where blind retransmission could cause further
65 Like TCP, IL has adaptive timeouts,
66 so the protocol performs well both on the
67 Internet and on local Ethernets.
68 A round-trip timer is used
69 to calculate acknowledge and retransmission times
70 that match the network speed.
74 An IL connection carries a stream of data between two end points.
75 While the connection persists,
76 data entering one side is sent to the other side in the same sequence.
77 The functioning of a connection is described by the state machine in Figure 1,
78 which shows the states (circles) and transitions between them (arcs).
79 Each transition is labeled with the list of events that can cause
80 the transition and, separated by a horizontal line,
81 the messages sent or received on that transition.
82 The remainder of this paper is a discussion of this state machine.
91 any sequence number between id0 and next inclusive
99 .I "Figure 1 - IL State Transitions
102 The IL state machine has five states:
109 The connection is identified by the IP address and port number used at each end.
110 The addresses ride in the IP protocol header, while the ports are part of the
112 The local variables identifying the state of a connection are:
117 32-bit local IP address
121 32-bit remote IP address
123 16-bit remote IL port
125 32-bit starting sequence number of the local side
127 32-bit starting sequence number of the remote side
129 sequence number of the next message to be sent from the local side
131 the last in-sequence message received from the remote side
133 sequence number of the first unacked message
136 Unused connections are in the
138 state with no assigned addresses or ports.
139 Two events open a connection: the reception of
140 a message whose addresses and ports match no open connection
141 or a user explicitly opening a connection.
142 In the first case, the message's source address and port become the
143 connection's remote address and port and the message's destination address
144 and port become the local address and port.
145 The connection state is set to
147 and the message is processed.
148 In the second case, the user specifies both local and remote addresses and ports.
149 The connection's state is set to
153 message is sent to the remote side.
154 The legal values for the local address are constrained by the IP implementation.
158 IL carries data messages.
159 Each message corresponds to a single write from
160 the operating system and is identified by a 32-bit
162 The starting sequence number for each direction in a
163 connection is picked at random and transmitted in the initial
166 The number is incremented for each subsequent data message.
167 A retransmitted message contains its original sequence number.
169 Transmission/Retransmission
171 Each message contains two sequence numbers:
172 an identifier (ID) and an acknowledgement.
173 The acknowledgement is the last in-sequence
174 data message received by the transmitter of the message.
179 messages, the ID is its sequence number.
180 For the control messages
187 the ID is one greater than the sequence number of
188 the highest sent data message.
190 The sender transmits data messages with type
192 Any messages traveling in the opposite direction carry acknowledgements.
195 message will be sent within 200 milliseconds of receiving the data message
196 unless a returning message has already piggy-backed an
197 acknowledgement to the sender.
199 In IP, messages may be delivered out of order or
200 may be lost due to congestion or faults.
202 IL uses a modified ``go back n'' protocol that also attempts
203 to avoid aggravating network congestion.
204 An average round trip time is maintained by measuring the delay between
205 the transmission of a message and the
206 receipt of its acknowledgement.
207 Until the first acknowledge is received, the average round trip time
208 is assumed to be 100ms.
209 If an acknowledgement is not received within four round trip times
210 of the first unacknowledged message
211 .I "rexmit timeout" "" (
212 in Figure 1), IL assumes the message or the acknowledgement
214 The sender then resends only the first unacknowledged message,
217 When the receiver receives a
221 message acknowledging the highest received in-sequence data message.
222 This may be the retransmitted message or, if the receiver has been
223 saving up out-of-sequence messages, some higher numbered message.
224 Implementations of the receiver are free to choose whether to save out-of-sequence messages.
225 Our implementation saves up to 10 packets ahead.
226 When the sender receives the
228 message, it will immediately resend the next unacknowledged message
231 This continues until all messages are acknowledged.
233 If no acknowledgement is received after the first
235 the transmitter continues to timeout and resend the
238 The intervals between retransmissions increase exponentially.
239 After 300 times the round trip time
240 .I "death timeout" "" (
241 in Figure 1), the sender gives up and
242 assumes the connection is dead.
244 Retransmission also occurs in the states
249 The retransmission intervals are the same as for data messages.
253 Connections to dead systems must be discovered and torn down
254 lest they consume resources.
255 If the surviving system does not need to send any data and
256 all data it has sent has been acknowledged, the protocol
257 described so far will not discover these connections.
260 state, if no other messages are sent for a 6 second period,
264 The receiver always replies to a
269 If no messages are received for 30 seconds, the
270 connection is torn down.
271 This is not shown in Figure 1.
275 All 32- and 16-bit quantities are transmitted high-order byte first, as
280 The following is a C language description of an IP+IL
281 header, assuming no IP options:
283 typedef unsigned char byte;
286 byte vihl; /* Version and header length */
287 byte tos; /* Type of service */
288 byte length[2]; /* packet length */
289 byte id[2]; /* Identification */
290 byte frag[2]; /* Fragment information */
291 byte ttl; /* Time to live */
292 byte proto; /* Protocol */
293 byte cksum[2]; /* Header checksum */
294 byte src[4]; /* Ip source */
295 byte dst[4]; /* Ip destination */
296 byte ilsum[2]; /* Checksum including header */
297 byte illen[2]; /* Packet length */
298 byte iltype; /* Packet type */
299 byte ilspec; /* Special */
300 byte ilsrc[2]; /* Src port */
301 byte ildst[2]; /* Dst port */
302 byte ilid[4]; /* Sequence id */
303 byte ilack[4]; /* Acked sequence */
307 Data is assumed to immediately follow the header in the message.
309 is an extension reserved for future protocol changes.
311 The checksum is calculated with
316 It is the standard IP checksum, that is, the 16-bit one's complement of the one's
317 complement sum of all 16 bit words in the header and text. If a
318 message contains an odd number of header and text bytes to be
319 checksummed, the last byte is padded on the right with zeros to
320 form a 16-bit word for the checksum.
321 The checksum covers from
323 to the end of the data.
342 field is the size in bytes of the IL header (18 bytes) plus the size of the data.
346 The IP protocol number for IL is 40.
348 The assigned IL port numbers are:
351 echo all input to output
355 send a standard pattern to output
357 send IP addresses of caller and callee to output
359 Plan 9 authentication protocol
361 Plan 9 CPU service, data
363 Plan 9 CPU service, notes
365 Plan 9 exported file systems
369 Plan 9 remote execution
376 [PPTTW93] Rob Pike, Dave Presotto, Ken Thompson, Howard Trickey, and Phil Winterbottom,
377 ``The Use of Name Spaces in Plan 9'',
379 Vol. 27, No. 2, April 1993, pp. 72-76,
380 reprinted in this volume.
383 .I "Internet Protocol,
384 .I "DARPA Internet Program Protocol Specification,
388 .I "Transmission Control Protocol,
389 .I "DARPA Internet Program Protocol Specification,
392 [RFC768] J. Postel, RFC768,
393 .I "User Datagram Protocol,
394 .I "DARPA Internet Program Protocol Specification,
projects / plan9front.git / blob