At 08:38 AM 9/7/01 -0700, Christian Huitema wrote: >In fact, one of the points that were made clear in the debate is that >the router manufacturers will never "just trust the host", i.e. just >trust that the "flow label" is sufficiently random and sufficiently >unique that they could use it without looking at the addresses. Then, >even if the flow was unique, we should note that even 20 bits would be >two small to be practical: the birthday paradox would kick in as soon as >the router processes 1,024 flows, which is not a very large number; you >would need some kind of tie-breaking logic, which means that you would >have at a minimum to process the source address. So, it is much safer to >assume that the primary classification will be based on the address >pair, and that the label is just a differentiator for packets that carry >the same address pair and require specific treatment; Mike points out >one possible solution; there are certainly others; hashing 256 bits of >source-destination should not require an inordinate number of gates in a >VLSI.
Christian, It's not the gates to calculate the hash key that's the issue. The problem is that hashing has a whole pile of memory access issues surrounding the possibility of collisions. First, it requires keeping a linked-list (or the like) of "flow descriptors" in the memory. This list has to be readable by the ASIC, but it also is written by the CPU as new flows are added and old ones deleted. This leads to the the classic multiple-accessor problems. Locking and write-snooping and so on are all doable -- but they add complexity that is very hard to verify and leads to less-robust designs. Second, since we can not know how many different flows will map to a given hash bucket. This means that the number of memory-accesses-per-packet is indeterminate. This is bad -- the memory system can not be well designed, so the packet rate can not be determined (which means that buffer sizes can not be determined, system performance can not be characterized, and so on) Frank Kastenholz -------------------------------------------------------------------- IETF IPng Working Group Mailing List IPng Home Page: http://playground.sun.com/ipng FTP archive: ftp://playground.sun.com/pub/ipng Direct all administrative requests to [EMAIL PROTECTED] --------------------------------------------------------------------
