Date: Thu, 8 Jan 2004 11:59:09 -0500 (EST) From: <silby@silby.com> To: <andre@freebsd.org> Cc: rw@codeburst.co.uk Subject: Re: kern/60889 - zero IP id change issues in 5.2RC2 Message-ID: <60755.158.6.15.27.1073581149.squirrel@webmail.pair.com> In-Reply-To: <3FFD4533.A35B6CD0@freebsd.org> References: <200401080202.CAA20485@starburst.demon.co.uk> <3FFD4533.A35B6CD0@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
> Richard Wendland wrote: > Haven't read all of that yet. >> It's important to remember that if fragmentation takes place, and a >> fragment is lost, the other fragment(s) will wait for quite some time >> in a re-assembly buffer (maybe up to 63 seconds). While they are >> waiting they are at quite some risk of being joined onto a fragment >> from the next ip_id cycle if a lot of packets are flowing: IMO, that's not really a "risk" anymore than packet loss is a risk. If two different IP packets are joined together, the subsequent TCP / UDP checksum will be incorrect, and the packet will be dropped. This is equivalent to a packet being dropped by the network; if we can't handle a few lost packets, then we have a big problem. Now, on to likelihood. Since IP IDs are per (IP source, dest) pair, let's consider two computers talking together, and assume that all packets are fragmented. If all packets are received in order, then we could actually get away with using the same ID over and over; each packet would be removed from the reassmebly queue when the final fragment arrived, and the next packet would create a new reassembly queue when its first fragment arrives. Assuming that some packet reordering occurs, but no packet loss, we're still in good shape, and can get away with only as many IP IDs as we have packets in flight. Even if we have slight packet loss, there should still be very few problems, as a collision in the 2^16 space will be unlikely if we have only a few incompletely reassembled packets hanging around. Of course, you can make the argument that if we have frequent packet loss, collisions become a common occurance. I agree... however, if you have frequent packet loss, TCP will backoff to a lower transmission rate, add delays, etc, which will help mitigate the problem. And if you have an app which keeps sending UDP packets at crazy rates which causes fragment loss and the resulting collisions, well, your performance will already be so bad that I doubt the additional few packets dropped due to collisions will matter one bit. So, to sum up my position on IP ID collisions: they cause no more problems than random packet loss would, and hence are not something we need to worry about much at all. Now, on to what we should do... > I have an idea how to something like this in an efficient manner. > Have a global incrementing ip_id counter and a small fixed size > hash table. The hash is computed from faddr/fport (see tcp_hostcache > for a good hash function). The hash table contains seeds in every > bucket which are refreshed periodically (every second or ten or > whatever). For an outgoing packet you take the global ip_id counter, > increment it by one, take the result and XOR it with the seed in > the apropriate bucket. The chance of collisions is very low and > you get the full 64k cycle (globally). Or you can do it the other way > around and have a counter in every bucket and a global seed. > Need to think about which is actually better. > > -- > Andre Could you just use the tcp host cache for this purpose? The simplest solution I can think of is to use the host cache to provide seperate IP ID sequences for hosts in the cache, and to use arc4random for all other hosts. This could result in a few collisions under certain situations, but I think that is an acceptable risk. If that requires extra host cache lookups, we could use the host cache provided sequence space for TCP packets only (one sequence space for all TCP sessions, of course), and arc4random for UDP / etc. I had considered some sort of hash table type system as you propose above, I came to the conclusion that it wouldn't be that much faster than arc4random and would provide much less randomness. Oh, I also wanted to reinforce a point Richard had made in his post on the problems with our id = 0 change: randomization becomes _more_ important as we move away from a global counter. If we use the tcp host cache to provide individual sequence spaces for TCP connections, we need to make sure that we address all the other packets, or we will be increasing the amount of information we're revealing. Mike "Silby" Silbersack
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?60755.158.6.15.27.1073581149.squirrel>