Curiosity
Jim Mulder
I kind of doubt the 360-20 was even in the same league as an 8 MHz MC68000. IIRC the 8 MHz...
there are many cases of searching list of n elements ... which can result in non-linear overhead increases. this typically happens when the frequency of searching is possibly related to load, but the length of the list can increase much faster than increase in processing (say a queue).
early implementations of TCP "FINWAIT" were linear lists. as part of closing TCP session, in part, because IP packets arrive out-of-order ... a list of sessions in the process of being closed and recently closed sessions were kept. in early implementations, buttuming the number of items on the FINWAIT list were relatively few (in part because of buttumptions that TCP sessions were relatively long lived), they used linear list. In any case, when packet arrives, there is (quick?) search of FINWAIT list to see if it is related to such a session.
HTTP came along and used TCP for transaction operations (TCP session requires a minimum of 7 packet exchange; by comparison VMTP-RFC1045, more oriented towards reliable transaction, has minimum 5 packet exchange; and XTP for reliable transaction has minimum 3 packet exchange). This violated various buttumptions about TCP sessions being long lived, frequency of TCP session termination and probable number of items on lists.
As some web servers became popular, they started running into horrible processing bottlenecks with 99percent of the processor devoted to searching the FINWAIT list (in some cases with over 10,000 items). Each search of the list was linear, but the total time-spent searching the list, increased non-linear ... since the length of the list increased dramatically (because of the humongous number of closing short-lived HTTP TCP sessions).
in any case, overhead of O(n) implementations can increase non-linearly when the number of "n" shows large increases (because of load and-or the frequency of the searching also increases).
RFC763 talks about FIN processing ...
my RFC index
RFC793 summary:
from above:
793 S Transmission Control Protocol, Postel J., 1981-09-01 (85pp) (.txt=172710) (STD-7) (Updated by 3168) (Obsoletes 761) (Ref'ed By 788, 821, 879, 882, 883, 915, 916, 959, 964, 977, 983, 1001, 1006, 1034, 1035, 1050, 1057, 1063, 1072, 1085, 1086, 1095, 1105, 1106, 1122, 1163, 1177, 1185, 1189, 1190, 1201, 1206, 1241, 1244, 1254, 1267, 1270, 1301, 1323, 1325, 1349, 1379, 1475, 1538, 1561, 1594, 1626, 1644, 1654, 168 plus 13, 1700, 1705, 1707, 1726, 1770, 1771, 1812, 1831, 1858, 1859, 1936, 1948, 1953, 1982, 2012, 2018, 2074, 2126, 2140, 2219, 2246, 2326, 2391, 2428, 2481, 2488, 2507, 2525, 2577, 2581, 2637, 2663, 2675, 2747, 2760, 2775, 2780, 2795, 2821, 2828, 2873, 2885, 2896, 2914, 2960, 2975, 2988, 2993, 3015, 3018, 3022, 3033, 3042, 3080, 3081, 3093, 3094, 3117, 3124, 3135, 3142, 3148, 3155, 3168, 3196, 3237, 3242, 3252, 3322, 3360, 3366, 3430, 3436, 3449, 3481, 3511, 3517, 3522, 3525, 3530, 3539, 3588, 3639, 3708, 3715, 3720, 3723, 3724, 3730, 3734, 3748, 3783, 3819, 3821, 3828, 3836, 3920, 3955, 4138, 4145, 4163, 4180, 4294, 4297, 4340, 4341, 4347, 4362, 4413, 4497) (TCP)
... snip ...
clicking on the ".txt=nnn" field in an RFC summary, retrieves the actual RFC.
so here is random reference from the web on how long something is kept on lists (i.e. particular session kept in particular state)
from above:
The first FIN from either side (after pbutting sequence number checks, of course) puts the state entry into tcp.closing, and a subsequent ACK from the other side puts the state into tcp.finwait.
In my never-ending quest for new ways to modify the instruction formats in my example architecture so as to minimize the memory bandwidth used for fetching instructions, I have come up with yet...
The state will be removed after no packet has been buttociated with it for a number of seconds, the default timeout values are 900 seconds for tcp.closing and 45 seconds for tcp.finwait. If subsequent packets like retransmissions or parts of a simultanous close match the state entry, the timer is reset again (to tcp.closing or tcp.finwait, respectively).
Timeouts can be set globally and overriden per rule for tcp.first, .opening, .established, .closing, .finwait and .closed.
... snip ...
random past postings retelling the HTTP-FINWAIT story: PowerPC?) Abstraction Layer!
Calling all Music Lovers! Just another addressing mode
Alt Folklore Computers from Newsgroups