Mills@UDEL.EDU (07/27/87)
Folks, As you may know, the NSFNET Backbone network has recently been upgraded to a fuzzware version that supports selective buffer preemption. In this version an input buffer is almost always available for an arriving packet. Upon arrival and inspection for correct format and IP checksum, the (sometimes considerable) unused space at the end of the buffer is returned to the buffer pool and the packet inserted on the correct output queue, as determined by the routing algorithm. A preemption is necessary when an input buffer must be allocated for the next following packet. When preemption is necessary, each output queue is scanned separately to find the customer with the largest number of 512-octet blocks. Then the queue with the largest number of such blocks is determined and the last buffer for the associated customer is preempted, even if the buffer preempted was the one just filled. In case of ties, the queue with the most packets transmitted since the last preemption is chosen. The entire process is repeated until sufficient buffer space is available for the input buffer request. It turns out rusty old soldier linkabit-gw is carrying much more traffic than it should, for reasonse that are temporary and irrelevant to the discussion anyway. There is a bottleneck between the inbound 56-Kbps line from ARPANET and an outbound 7.2-Kbps serial line to U Maryland. There is only about 8K octets of buffering in this machine, so one would expect preemption to occur fairly often. One would then be keenly interested in how the selection strategy operates. Following is an edited extract from the log file for linkabit-gw covering an interval of about eight hours on a weekend morning (UT). Each line reveals a single buffer preemption, the interface it occured on and the interface the packet came in on. For the purposes here, only the time and IP source address shown are relevant. The data are arranged chronologically and grouped according to "events," which evidently consist of traffic surges separated by at least five seconds. I have reduced the bulk of the data considerably and deleted, with note, duplicate traps for the same hosts. The fun thing here is to look at the patterns, trends and so forth in order to gain some insight on the behavior of various IP/TCP implementations. The data show 321 packets preempted in 64 surge events during an interval of about 504 minutes. Each surge event consists of from one to 17 preemptions (mean five) and lasts from one to several seconds (typically two). Thus, about two minutes of the 504-minute interval represents congestion severe enough to result in preemption and when this occurs about five packets will be preempted. There are 18 surge events with two or more traps involving a single host, 13 involving two hosts and eight involving three. There were eight more events involving from four to six hosts, most of which occur toward the end of the period when overall network traffic is increasing. Of these 47 events, over a third apparently involve a single host, which suggests further examination of its packetization and queueing mechanisms. Host [10.3.0.11] (SCORE.STANFORD.EDU) seems to be well represented in the data; however, it is also possible that this host may simply have more traffic than the others represented here. I think the data confirms earlier suspicions of many of us that only a few hosts are causing most of the surge events, whether due to defective implementations, antisocial queueing policies or simply too much traffic. Also, note the surges are quite short, in many cases about the same duration as the round-trip interval between the source and its destination. Clearly, ICMP Source Quench messages will have little effect in such cases, especially if the throttling mechanism they operate upon is simply to squeeze the TCP window. On the other hand, note that the intervals between successive surges sometimes is not very large, especially near the end of the period shown, where it ranges from a few seconds to about thirty seconds. This suggests TCP window-throttling might have some beneficial effect if its time constant were comparatively long, like in the order of a minute or more. Since many mail transfers complete in less time, this means that flow information of this type must span more than just a single connection and suggests it be recorded as a state variable in the IP layer and made available on a continuous basis to the TCP layer. I'm inserting the actual data last in this message if you want to skip it. Dave 06:38:07 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] *** 3 deleted 06:38:07 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 06:38:07 010 ?TRAP-I-Buffer preemption 002 [192.5.53.170] 06:38:08 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] *** 5 deleted 06:38:09 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 06:38:09 010 ?TRAP-I-Buffer preemption 002 [192.5.53.170] 06:38:09 010 ?TRAP-I-Buffer preemption 002 [192.5.53.170] 06:38:09 010 ?TRAP-I-Buffer preemption 002 [192.5.53.170] 06:51:50 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 06:51:50 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 06:51:50 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 06:51:50 010 ?TRAP-I-Buffer preemption 002 [26.0.0.74] 06:51:51 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 06:51:51 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 3 deleted 06:51:51 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 06:51:51 010 ?TRAP-I-Buffer preemption 002 [26.0.0.74] 06:51:52 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 06:58:39 010 ?TRAP-I-Buffer preemption 002 [128.210.1.4] *** 4 deleted 06:58:40 010 ?TRAP-I-Buffer preemption 002 [128.210.1.4] 07:12:59 010 ?TRAP-I-Buffer preemption 002 [192.5.53.170] *** 3 deleted 07:13:00 010 ?TRAP-I-Buffer preemption 002 [192.5.53.170] 07:19:51 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:19:53 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:21:57 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 07:21:57 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 07:21:58 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:24:52 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:24:52 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:24:52 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:24:52 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:24:53 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:24:53 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:24:53 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:25:38 014 ?TRAP-I-Buffer preemption 002 [192.5.45.21] 07:25:38 014 ?TRAP-I-Buffer preemption 002 [192.5.45.21] 07:25:45 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:27:03 004 ?TRAP-I-Buffer preemption 012 [128.5.32.1] 07:27:05 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:27:06 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:27:06 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:27:24 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:27:25 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] *** 2 deleted 07:27:25 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:27:25 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 07:27:47 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:27:48 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:27:48 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:27:49 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 07:33:16 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:33:16 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:33:16 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:33:32 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:33:32 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:33:32 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:33:57 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:34:14 010 ?TRAP-I-Buffer preemption 002 [10.1.0.2] 07:34:35 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:35:09 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:35:09 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:35:27 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:35:27 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:35:28 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:35:58 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:35:59 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:35:59 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:36:32 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:36:32 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:37:00 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:37:00 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:37:00 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:37:29 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:37:30 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:37:30 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:37:30 010 ?TRAP-I-Buffer preemption 002 [10.4.0.5] 07:37:30 010 ?TRAP-I-Buffer preemption 002 [128.36.0.1] 07:37:30 010 ?TRAP-I-Buffer preemption 002 [128.95.1.4] 07:37:31 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:38:04 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:38:04 010 ?TRAP-I-Buffer preemption 002 [128.95.1.4] 07:39:13 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:39:13 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:40:48 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] *** 2 deleted 07:40:49 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:41:16 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:41:16 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:41:54 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] *** 3 deleted 07:42:58 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 07:55:11 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 2 deleted 07:55:11 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 07:55:12 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 07:55:12 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 4 deleted 07:55:12 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 08:30:00 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 2 deleted 08:30:01 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 08:30:01 010 ?TRAP-I-Buffer preemption 002 [26.0.0.21] 08:30:01 010 ?TRAP-I-Buffer preemption 002 [26.0.0.21] 08:34:16 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 08:46:40 010 ?TRAP-I-Buffer preemption 002 [10.0.0.52] 08:54:03 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] *** 3 deleted 08:54:04 010 ?TRAP-I-Buffer preemption 002 [10.3.0.11] 09:20:12 010 ?TRAP-I-Buffer preemption 002 [192.5.23.8] 09:24:43 014 ?TRAP-I-Buffer preemption 002 [192.5.8.1] 09:30:52 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 09:30:52 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 09:30:53 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 09:30:53 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 7 deleted 09:30:54 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 09:44:38 010 ?TRAP-I-Buffer preemption 002 [10.0.0.52] 09:44:38 010 ?TRAP-I-Buffer preemption 002 [10.0.0.52] 09:44:38 010 ?TRAP-I-Buffer preemption 002 [10.0.0.52] 09:44:38 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 09:44:38 010 ?TRAP-I-Buffer preemption 002 [128.105.2.1] 09:44:38 010 ?TRAP-I-Buffer preemption 002 [128.89.0.208] 10:00:14 010 ?TRAP-I-Buffer preemption 002 [10.0.0.52] 10:00:16 010 ?TRAP-I-Buffer preemption 002 [10.0.0.52] 10:00:16 010 ?TRAP-I-Buffer preemption 002 [128.102.2.3] 10:33:12 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 3 deleted 10:33:12 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 10:33:13 010 ?TRAP-I-Buffer preemption 002 [128.101.1.1] 10:33:13 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 3 deleted 10:33:13 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 11:03:39 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 7 deleted 11:03:40 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 11:03:41 010 ?TRAP-I-Buffer preemption 002 [26.2.0.104] 11:19:41 010 ?TRAP-I-Buffer preemption 002 [128.2.249.105] *** 4 deleted 11:19:42 010 ?TRAP-I-Buffer preemption 002 [128.2.249.105] 11:43:20 010 ?TRAP-I-Buffer preemption 002 [192.5.23.8] 12:06:11 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] *** 11 deleted 12:06:13 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 12:06:13 010 ?TRAP-I-Buffer preemption 002 [128.46.131.21] 12:06:13 010 ?TRAP-I-Buffer preemption 002 [128.46.131.21] 12:06:14 010 ?TRAP-I-Buffer preemption 002 [128.46.131.21] 12:06:14 010 ?TRAP-I-Buffer preemption 002 [192.12.8.9] 12:38:01 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 12:38:02 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 13:32:08 010 ?TRAP-I-Buffer preemption 002 [10.1.0.2] *** 6 deleted 13:32:09 010 ?TRAP-I-Buffer preemption 002 [10.1.0.2] 13:32:09 010 ?TRAP-I-Buffer preemption 002 [192.12.141.25] 13:33:38 014 ?TRAP-I-Buffer preemption 002 [192.5.8.1] 13:34:44 010 ?TRAP-I-Buffer preemption 002 [192.12.141.25] 13:34:45 010 ?TRAP-I-Buffer preemption 002 [128.20.1.1] 13:34:45 010 ?TRAP-I-Buffer preemption 002 [192.12.141.25] 13:34:45 010 ?TRAP-I-Buffer preemption 002 [192.5.48.3] 13:47:54 010 ?TRAP-I-Buffer preemption 002 [10.7.0.82] 13:47:54 010 ?TRAP-I-Buffer preemption 002 [192.12.141.25] 13:47:55 010 ?TRAP-I-Buffer preemption 002 [128.110.4.22] 13:47:55 010 ?TRAP-I-Buffer preemption 002 [128.165.4.4] 13:47:55 010 ?TRAP-I-Buffer preemption 002 [192.12.141.25] 13:47:55 014 ?TRAP-I-Buffer preemption 002 [192.5.8.5] 13:47:55 014 ?TRAP-I-Buffer preemption 002 [192.5.8.5] 14:41:41 010 ?TRAP-I-Buffer preemption 002 [128.89.0.92] 14:43:09 004 ?TRAP-I-Buffer preemption 012 [128.5.34.1] 14:43:09 014 ?TRAP-I-Buffer preemption 002 [192.12.33.99] 14:43:11 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:43:11 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:43:11 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:43:12 010 ?TRAP-I-Buffer preemption 002 [128.89.0.92] 14:43:33 010 ?TRAP-I-Buffer preemption 002 [128.89.0.92] 14:46:31 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:48:09 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:48:27 010 ?TRAP-I-Buffer preemption 002 [128.97.2.16] *** 3 deleted 14:48:28 010 ?TRAP-I-Buffer preemption 002 [128.97.2.16] 14:48:28 010 ?TRAP-I-Buffer preemption 002 [128.97.2.16] 14:48:46 010 ?TRAP-I-Buffer preemption 002 [10.3.0.44] 14:48:46 010 ?TRAP-I-Buffer preemption 002 [10.3.0.44] 14:51:08 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:51:09 010 ?TRAP-I-Buffer preemption 002 [10.3.0.44] *** 2 deleted 14:51:09 010 ?TRAP-I-Buffer preemption 002 [10.3.0.44] 14:51:09 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:51:09 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:51:10 010 ?TRAP-I-Buffer preemption 002 [10.3.0.44] 14:51:10 010 ?TRAP-I-Buffer preemption 002 [10.3.0.44] 14:51:10 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:51:10 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:51:10 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:55:31 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:55:31 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:55:31 010 ?TRAP-I-Buffer preemption 002 [128.165.4.4] 14:55:32 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:55:32 010 ?TRAP-I-Buffer preemption 002 [128.165.4.4] 14:55:32 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:55:32 010 ?TRAP-I-Buffer preemption 002 [18.72.0.205] 14:55:32 010 ?TRAP-I-Buffer preemption 002 [192.12.141.129] 14:56:04 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:56:04 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:56:04 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:56:04 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:56:04 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:56:05 010 ?TRAP-I-Buffer preemption 002 [10.1.0.96] 14:56:05 010 ?TRAP-I-Buffer preemption 002 [10.1.0.96] 14:56:05 010 ?TRAP-I-Buffer preemption 002 [10.1.0.96] 14:56:05 010 ?TRAP-I-Buffer preemption 002 [128.110.4.22] 14:56:05 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:56:05 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:56:05 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:56:06 010 ?TRAP-I-Buffer preemption 002 [128.2.30.1] 14:56:30 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:56:31 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:56:31 010 ?TRAP-I-Buffer preemption 002 [128.165.4.4] 14:56:31 010 ?TRAP-I-Buffer preemption 002 [128.41.9.3] 14:56:31 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:56:31 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:56:31 010 ?TRAP-I-Buffer preemption 002 [18.72.0.205] 14:56:32 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:56:32 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:56:52 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:56:53 010 ?TRAP-I-Buffer preemption 002 [128.110.4.22] 14:56:53 010 ?TRAP-I-Buffer preemption 002 [128.110.4.22] 14:56:53 010 ?TRAP-I-Buffer preemption 002 [128.165.4.4] 14:56:53 010 ?TRAP-I-Buffer preemption 002 [128.165.4.4] 14:57:18 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:57:18 010 ?TRAP-I-Buffer preemption 002 [18.63.0.3] 14:57:19 010 ?TRAP-I-Buffer preemption 002 [128.105.2.13] 14:57:19 010 ?TRAP-I-Buffer preemption 002 [128.110.4.22] 14:57:19 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:57:19 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:57:19 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:58:13 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:58:13 010 ?TRAP-I-Buffer preemption 002 [128.83.144.1] 14:58:13 010 ?TRAP-I-Buffer preemption 002 [26.2.0.4] 14:58:13 010 ?TRAP-I-Buffer preemption 002 [26.2.0.4] 14:58:13 010 ?TRAP-I-Buffer preemption 002 [26.2.0.4] 14:58:14 010 ?TRAP-I-Buffer preemption 002 [10.0.0.51] 14:58:14 010 ?TRAP-I-Buffer preemption 002 [26.2.0.4] 14:58:14 010 ?TRAP-I-Buffer preemption 002 [26.2.0.4] 14:58:14 010 ?TRAP-I-Buffer preemption 002 [26.2.0.4] 14:58:15 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:58:15 010 ?TRAP-I-Buffer preemption 002 [192.26.86.5] 14:58:15 010 ?TRAP-I-Buffer preemption 002 [26.2.0.4] 15:02:06 010 ?TRAP-I-Buffer preemption 002 [10.1.0.2] *** 10 deleted 15:02:08 010 ?TRAP-I-Buffer preemption 002 [10.1.0.2] 15:06:46 010 ?TRAP-I-Buffer preemption 002 [128.110.192.2] la di da di da