1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
|
<pre>Network Working Group V. Cerf
Request for Comments: 442 24 January 1973
NIC: 13774
The Current Flow-Control Scheme for IMPSYS
BB&N quarterly report #13 outlines part of the current flow control
scheme in the IMP operating system. A meeting held March 16, 1972,
at BB&N was devoted to the description of this new scheme for the
benefit of interested network participants.
This note represents my understanding of the flow control mechanism.
The essential goal is to eliminate unnecessary retransmissions when
the load is heavy, eliminate the retransmission time-out period when
the load is light, increase bandwidth, prevent re-assembly lock-up,
control traffic from HOSTS into the net more strictly than the
earlier link blocking method, and secure the rights of life, liberty,
and the pursuit of happiness for ourselves and our posterity,...oops.
Source IMP-to-Destination IMP Protocol
There are two different protocols depending on message length (i.e.
single or multi-packet). We illustrate first the single packet case.
Source Imp Destination Imp
---------- ---------------
case 1) message (1) + implicit req (1)--->
<--- RFNM (arrived ok)
[discard copy of msg]
case 2) message (1) + implicit req (1)---> no room, don't respond
<--- All (1) (room available)
message (1) --->
[discard copy of msg] <--- RFNM (arrived ok)
In the first case, a single packet message is sent to the destination
IMP. This message acts as an implicit request for single packet
buffer space. If there is room, as in case 1, the destination IMP
responds with a RFNM. The source IMP, which has retained a copy of
the message, deletes its copy and goes on.
The second case illustrates what happens when the source IMP sends a
message to a destination IMP at which there is no room for the one-
packet message. The arrival of the single packet message constitutes
a request for single packet buffer space, and is recorded as such by
the destination IMP in a first-come-first-served buffer reservation
<span class="grey">Cerf [Page 1]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
<span class="grey"><a href="./rfc442">RFC 442</a> The Current Flow-Control Scheme for IMPSYS January 1973</span>
request queue. When space is available, the destination IMP will
transmit an ALL (1) to the requesting source IMP which can then send
the single packet message again, this time knowing that space has
been reserved at the destination.
For multi-packet messages, the procedure is somewhat different. When
a message enters an IMP from a HOST, and the "last bit" flag is not
set when the number of bits in a maximum length single packet have
arrived, the IMP halts the HOST->IMP transmission line while it
determines whether space has been reserved at the dest. IMP. If
space (8 packets worth) has been reserved, the HOST->IMP line is re-
opened, and the message is sent out normally. If space has not been
reserved, the HOST->IMP line is kept closed while the source IMP
makes a request for multi-packet buffer storage at the destination
IMP. When 8 buffers are available, the destination IMP responds with
an ALL (8). The source IMP then transmits the message, and waits for
a combination RFNM and ALL (8) from the destination IMP. The
destination IMP will delay its RFNM, if necessary, until it has
another 8 buffers available for the next multipacket message.
This sequence is illustrated below:
Source IMP Destination IMP
---------- ---------------
H-> I line
----------> First packet of multipacket
arrives. Halt H->I line and
send REQ (8) -------------->
start 30 sec. Time-out
If time-out, resend
REQ (8) and restart -------->
time-out.
<--------ALL (8) when available. Start
long term (2 min.) time-out.
On time-out, reset all
outstanding reservations.
Send the message:
| ----------->
Start 30 sec. time-out
for INComplete transmission.
If time-out, send INC?----->
<span class="grey">Cerf [Page 2]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
<span class="grey"><a href="./rfc442">RFC 442</a> The Current Flow-Control Scheme for IMPSYS January 1973</span>
<------On recept of message, send
RFNM + implicit ALL (8). On
receipt of INC? send RFNM +
ALL(8) if MSG(8) received,
or send INC! if MSG(8) not
received. Start 2 min. time-out
on ALL(8).
Queue ALL(8); start 125 ms.
time-out when it reaches
head of queue. If time-out
on ALL(8), send GVB(8)----->
<----- Ack.
else send next message ----->
A key point in this protocol is that a source IMP, after receipt of a
RFNM and implicit ALL(8) from the destination IMP, has 125 msec. in
which to initiate the transfer of at least the first packet of a
multi-packet message to the destination IMP. The source IMP may have
several allocate responses queued up in which case these time-outs
occur one after the other (one has to time-out before the next 125
msec time-out starts).
Time-outs exist in the source IMP which cause it to send INC?
messages to the destination IMP if it has received no response from
some earlier message.
Buffer Allocation
A total of 40 buffers are available for store/forward and re-assembly
purposes. At most 32 can be allocated for re-assembly, and at most
24-25 can be allocated for store and forward use. This prevents
either kind of traffic from completely shutting out the other kind.
Message Ordering (Source IMP-to-Destination IMP).
As an aid to congestion control, an IMP can have at most 4 messages
outstanding (un-RFNMed) for each other IMP. Link numbers in the
message leader are ignored by the IMPs. Instead, IMPs mark messages
leaving for other destinations with an 8-bit message number. In
addition, a 2-bit priority number is also used in case a HOST has
marked a message as a priority message. The key notion here is that
the IMPs treat all HOSTs on a given IMP as if they were a single
HOST. A single sequence of message and priority numbers is used in
each direction between each pair of sites.
<span class="grey">Cerf [Page 3]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
<span class="grey"><a href="./rfc442">RFC 442</a> The Current Flow-Control Scheme for IMPSYS January 1973</span>
The receiving IMP remembers the message number of the last message
delivered, as well as the priority number of the last priority
message delivered. It uses this information to correctly sequence
messages out the IMP-HOST line (s). Since there is only one sequence
of numbers for each pair of sites, messages for one HOST at a site
may get in the way of messages for another HOST at the same site. In
fact, if some message, m, is the next in line to go to some HOST, and
that HOST delays receipt for 30 seconds, any messages for another
HOST may be delayed that long also. However, only the first message
is lost, since the second one could not even start into its
destination HOST until the first one had been delivered. There is a
tighter coupling between HOSTs sharing an IMP than before, but not
much tighter.
An example of the use of message and priority numbers is given below.
Order sent by Order received by Order received by
Source IMP Dest. IMP HOST
---------- --------- ----
11,12P(1),13P(2),14 --> 13P(2),12P(1),14,11 --> 12P(1),13P(2),11,14
11,12P(1),13P(2),14 --> 13P(2),11,14,12P(1) --> 11,12P(1),13P(2),14
where 13P(2) is interpreted to mean message #13, priority number(2).
Note that there are only 2 classes of messages, priority and non-
priority, and that the priority numbers simply allow ordering at the
destination of multiple outstanding priority transmissions from the
same site.
If HOSTs use link numbers to de-multiplex messages to processes, then
it would be a mistake to arbitrarily assign short messages priority.
If a file transmission were carried out such that the last short
message had priority, the file might not enter the receiving HOST in
the same order it was sent!
ACK Mechanism
IMPs treat their physical channels (phone lines) as if they were
pairs of simplex communications paths. Each IMPSYS has a sender and
receiver module for each full duplex channel. Each module has an
"ODD/EVEN" bit which is used to keep track of the state of the last
packet on the line. The object is for the sender module to "block" a
channel until the corresponding receiver has received a packet
indicating that the send packet was received on the other end (i.e.
an acknowledgment).
<span class="grey">Cerf [Page 4]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
<span class="grey"><a href="./rfc442">RFC 442</a> The Current Flow-Control Scheme for IMPSYS January 1973</span>
In the present system, acknowledgments are separate IMP-IMP packets.
In the new system, they are a single bit in a packet flowing in the
opposite direction on the reverse path of a full duplex channel.
Every packet sent between IMPs has an ACK bit and an OE bit, as shown
below.
P A
O C
E K
+-------+-----+------------------------+-----+----------+
typical packet | | | | | |
| | | | | |
+-------+-----+------------------------+-----+----------+
We need some terminology: Let POE be the packet OE bit, and SOE, ROE
be the send module OE bit and Receive module OE bit respectively.
For two IMPs, A and B, we distinguish SOE/A and SOE/B as the two send
module OE bits at IMPs A and B respectively.
The rules of operation are as follow:
Sender
------
if ACK != SOE then do nothing
--
else SOE <- !SOE (i.e. flip SOE bit) and free channel.
----
Receiver
--------
if POE = ROE then packet is a duplicate so throw it away.
--
else ROE <- !ROE
----
Whenever a packet is sent by the sent module, its two bits, POE and
ACK are set up by:
POE <- SOE
ACK <- ROE
The mechanism is designed to use real traffic to accomplish the
acknowledgment protocol by piggy-backing the ACK bits in the header
of real packets. If there is no real packet waiting for transmission
in the opposite direction, a fake packet is assembled which carries
the ACK, but which is not acknowledged by the receiving side.
<span class="grey">Cerf [Page 5]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
<span class="grey"><a href="./rfc442">RFC 442</a> The Current Flow-Control Scheme for IMPSYS January 1973</span>
We give an example of the operation of this mechanism between two
IMPs.
IMP A IMP B
----- -----
ROE | SOE ROE | SOE
| POE ACK |
| +-----------+ |
IMP A blocks send 1 | 0 (1)| 0 1 |-> 1 | 0 IMP B NOPS,
channel. | +-----------+ | flips ROE
| |
| POE ACK |
| +-----------+ |
IMP A frees send 0 | 1 <-| 0 0 |(2) 0 | 0 IMP B blocks
channel, | +-----------+ | channel for
Flips SOE | | new traffic
| POE ACK |
IMP A blocks send | +-----------+ crashes|
channel | (3)| 1 0 |->or gets|
| +-----------+ lost |
| |
| POE ACK |
IMP A detects packet | +-----------+ |
duplicate (POE=ROE) 0 | 1 <-| 0 0 |(2) 0 | 0 IMP B
so does not change | +-----------+ | retransmits no
SOE bit. | | ACK received
| POE ACK |
IMP A retransmits | +-----------+ | IMP B flips
packet 3 | (3)| 1 0 |-> 1 | 1 SOE, unblocks
| +-----------+ | channel, and
| | flips ROE.
| POE ACK |
IMP A flips ROE, | +-----------+ |
flips SOE 1 | 0 <-| 1 1 |(4) |
| +-----------+ |
| |
In fact each send/receive module has 8 OE bits, so up to 8 packets
can be outstanding in either direction.
How things really work
Actually, a single send module is responsible for trying to transmit
packets out on the 8 pseudo-channels. Each channel has a two-bit
state (in addition to an OE bit). Each channel is either FREE or IN
USE and if IN USE, it may be sending OLD or NEW packet.
<span class="grey">Cerf [Page 6]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
<span class="grey"><a href="./rfc442">RFC 442</a> The Current Flow-Control Scheme for IMPSYS January 1973</span>
start state F = free
| I = in use
V X = don_t care
+-----+ +------+ N = new packet
| FX | --------------> | I, N | O = old packet
+-----+ +------+
^ |
| |
| |
| |
ACK | |
received | |
| V
| +------+
+-------------------| I, O |---+
+------+ |
^ | re-transmissions
+------+
Between IMPs, packets are sent repeatedly, until they are
acknowledged. However, the choice of what to send is ordered by
priority as follows:
1. Priority Packets (as marked by HOST)
2. Non-Priority Packet
3. Unacknowledged packets (on I,O state channels)
4. Others
It was pointed out that a heavy load of type (1) and (2) traffic
might prevent retransmissions from occurring at all, and W. Crowther
responded that the bug would be fixed by a 125 ms time-out which
forces retransmission of old packets in class (3).
Note that each packet must carry a "pseudo-channel" number to
identify the POE-to-channel association, and 8 ACK bits (which are
positionally associated with the pseudo-channels). Thus a single
packet can ACK up to 8 packets at once.
[This RFC was put into machine readable form for entry]
[into the online RFC archives by Helene Morin, Via Genie, 12/99]
Cerf [Page 7]
</pre>
|
