Jim Mulder wrote:
O(n) - searching a list of n elements
O(n ** 2) - bubble sort of n elements
O(n * log(n)) - heap sort of n elements
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, assuming the number of
items on the FINWAIT list were relatively few (in part because of
assumptions 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 assumptions 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
http://www.garlic.com/~lynn/rfcietff.htm
RFC793 summary:
http://www.garlic.com/~lynn/rfcidx2.htm#793
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, 1693,
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)
http://mail-index.netbsd.org/tech-net/2002/11/07/0000.html
from above:
The first FIN from either side (after passing 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.
The state will be removed after no packet has been associated 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:
http://www.garlic.com/~lynn/99.html#1 Early tcp development?
http://www.garlic.com/~lynn/99.html#164 Uptime (was Re: Q: S/390 on
PowerPC?)
http://www.garlic.com/~lynn/2002.html#3 The demise of compaq
http://www.garlic.com/~lynn/2002.html#14 index searching
http://www.garlic.com/~lynn/2004m.html#46 Shipwrecks
http://www.garlic.com/~lynn/2005g.html#42 TCP channel half closed
http://www.garlic.com/~lynn/aadsm23.htm#21 Reliable Connections Are Not
http://www.garlic.com/~lynn/2006f.html#33 X.509 and ssh
http://www.garlic.com/~lynn/2006k.html#2 Hey! Keep Your Hands Out Of My
Abstraction Layer!
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to [EMAIL PROTECTED] with the message: GET IBM-MAIN INFO
Search the archives at http://bama.ua.edu/archives/ibm-main.html
