grass@unipas.fmi.uni-passau.de (Grass) (10/19/90)
Recently some colleagues and me discussed the above question. As we found from the CSMA/CD ANSI/IEEE standard, there exists a *set* of individual/multicast/broadcast addresses for each single station. Addresses are 48 bits wide and the first bit (LSB) distinguishes individual (0) and group (1) addresses. Group addresses may be multicast addresses (specified by higher protocol layers!) or a particular broadcast address. This unique broadcast address has to be predefined for the network and must be known by every station. Usually 11...1 is chosen, but the standard leaves it open to choose another address pattern. This sounds that at least group address recognition is done by software: all messages with its first destination address bit set are received by every station, transferred to some place in memory and examined by some software routines. If the destination address does not match with the actual set of active group addresses the whole message is discarded from memory. What a waste of cpu/memory/bus ressources! To save up these ressources the Ethernet controller hardware (chip?) could be provided with *all* addresses it shall respond to. Address decoding is done by hardware. Only messages with according destination addresses are passed. Here we are back to our question: is hardware address decoding done in practice? If yes, how many address pattern have to be buffered (adjusted by switches??? 48-bit?) on average/maximum? Please enlighten some curious greenhorns. Thank you in advance. Wolf-Dieter Tiedemann University of Passau email: grass@unipas.fmi.uni-passau.de Dpt. Mathematics and Computer Science D-8390 Passau (F R Germany)
ckollars@deitrick.East.Sun.COM (Chuck Kollars - DSGG Technical Marketing - Boston) (10/20/90)
In article <1990Oct18.172918.24929@forwiss.uni-passau.de> grass@unipas.fmi.uni-passau.de (Grass) writes: >As we found from the CSMA/CD ANSI/IEEE standard, there exists a *set* of >individual/multicast/broadcast addresses for each single station. Addresses >are 48 bits wide and the first bit (LSB) distinguishes individual (0) and >group (1) addresses. Group addresses may be multicast addresses (specified >by higher protocol layers!) or a particular broadcast address. This unique >broadcast address has to be predefined for the network and must be known by >every station. Usually 11...1 is chosen, but the standard leaves it open to >choose another address pattern. In practice, every station has one individual address, one broadcast address, and zero or more multicast addresses. The individual address is usually read from an internal PROM and should be world-unique. (The first 24 bits are allocated to "vendors" by the IEEE, and each "vendor" then assigns the second 24 bits. Rather like the Universal Price Codes you see at the grocery store in the US, where the first five digits encode "manufacturer" and the second five digits encode "product".) In practice the broadcast address on all Ethernet networks is always all ones. The zero or more multicast addresses recognized will be enabled by higher layer software--the startup default is that no multicast addresses will be recognized. To date the multicast capability is not used very much. Many ethernet hardware vendors use one multicast address to exchange "private" management information. You may see more use of Ethernet multicast addresses in the future: 1) The newest version of Apple's EtherTalk uses one for distributing routing information. 2) The NetBIOS-over-TCP/IP protocol (RFC 1001) may use a few for more efficient group distribution. 3) IP multicast, which is not yet widely deployed, probably uses one. 4) The VMTP protocol probably uses some. I don't know of any "standard/portable" applications program interface to the multicast address capability, which may be why the feature is used by so few application programs. >This sounds that at least group address recognition is done by software: all >messages with its first destination address bit set are received by every >station, transferred to some place in memory and examined by some software >routines. If the destination address does not match with the actual set of >active group addresses the whole message is discarded from memory. What a >waste of cpu/memory/bus ressources! The standard says what to do, but not how to do it. Fortunately available silicon is smarter than your worst-cast scenario. The hardware does first-pass filtering of received multicast packets, and passes only packets that are "probably" for this station up to software. The Intel 82586 chip for example hashes all incoming multicast addresses into one of 64 internal buckets. Each bucket can be individually enabled by software. If the incoming multicast address doesn't hash to an enabled bucket, the packet is silently discarded. The chip's interface to this functionality is friendly--software specifies the multicast address of interest and the chip figures out which bucket to enable. >To save up these ressources the Ethernet controller hardware (chip?) could >be provided with *all* addresses it shall respond to. Address decoding is >done by hardware. Only messages with according destination addresses are >passed. Although a chip could in theory filter *all* incoming multicast addresses, doing so would make the chip significantly more complex. As you point out, having all filtering done in software would degrade performance. So a combintion solution seems called for--make the chip do the first-pass filtering and discard "most" unwanted multicast packets, and let the software do the second-pass filtering to render an "exact" decision about whether or not to examine each packet. --- chuck kollars <ckollars@East.Sun.COM> DSGG Technical Marketing, Sun's Boston Development Center
vjs@rhyolite.wpd.sgi.com (Vernon Schryver) (10/21/90)
In article <2988@jaytee.East.Sun.COM>, ckollars@deitrick.East.Sun.COM (Chuck Kollars - DSGG Technical Marketing - Boston) writes: > ... > To date the multicast capability is not used very much. Many ethernet > hardware vendors use one multicast address to exchange "private" management > information. You may see more use of Ethernet multicast addresses in >the future:... IGMP (see, for example, RFC-1112) involves a mapping from Class D network numbers to Ethernet and FDDI multicast addresses. IGMP is coming. At least one host vendor is currently shipping it. I've been told that IGMP will arrive in force on the Internet with OSPF. Multicast makes for good network games, and there is already one game with an assigned number. It would have been a better way to do network databases like YP/NIS. I think one network name service compeating with YP/NIS and the Internet DNS is using multicast. There is at least one protocol, XTP, which uses multicast MAC addresses to implement "reliable multicast datagrams." There are Class D numbers assigned to rwho and NetworkTimeProtocol. See the current Assigned Numbers RFC. Vernon Schryver, vjs@sgi.com P.S. It would have been nice if the AMD FORMAC (FDDI MAC chip) had some reasonable support for multicast. Unfortunately, the only apparent way to make the FORMAC do multicast, "external address detection," causes it to generate a "non-maskable interrupt" on each multicast or broadcast frame received. That is compared to the nice multicast filter on the AMD ethernet LANCE.
alanj@nevermore.WV.TEK.COM (Alan Jeddeloh;685-2991;61-201;292-9740;orca) (10/23/90)
In article <1990Oct18.172918.24929@forwiss.uni-passau.de> grass@unipas.fmi.uni-passau.de (Grass) writes: >Here we are back to our question: is hardware address decoding done in >practice? If yes, how many address pattern have to be buffered (adjusted by >switches??? 48-bit?) on average/maximum? All Ethernet controller chips can filter incoming packets on the basis of the destination address. All can filter directly addressed packets (leading address bit == 0). All (that I am familiar with) turn on or off receipt of broadcast packets (all address bits 1's). Chips vary in the scheme used to filter multicast addresses. The AMD 7990 "LANCE" and the Intel 80586 use a hash scheme: Multicast addresses are hashed into some small number (e.g. 64) and a corresponding bit vector loaded into the chip determine whether the packet is accepted. Software then must double check the received packet address, but this is a low-overhead check since the multicast address space is sparse and the chance of two different multicast addresses appearing on the same wire having the same hash value is small. I am not familiar with the SEEQ chip. I believe the National NIC (number?) chip uses a similar scheme. The second generation chips have a little more power. The Intel 80596 can hash physical addresses as well as multicast addresses. (I found that buried in a preliminary data sheet.) This allows efficient filtering on multiple physical addresses. This is useful for network monitors and diagnostic equipment, a possibly multi-protocol routers. The National 83932 SONIC uses a 16-entry content-addressable memory to filter incoming packets. The enties in the CAM can be any combination of multicast addresses or physical addresses. This limits you to 16 different addresses, but eliminates the need to do the software check. Broadcast address filtering is a separate control. Most (all?) chips also allow a "promiscuous" mode where all packets are accepted. Most (all?) allow a mode to accept all multicast packets as well. -Alan Jeddeloh (503) 685-2991 Tektronix Network (Yes, we're still here) Displays D/S 60-180; PO Box 1000; Wilsonville, OR 97070 alanj@nevermore.wv.tek.com Quoth the printer, "Nevermore!"
morgan@jessica.stanford.edu (RL "Bob" Morgan) (10/23/90)
In article <9380@orca.wv.tek.com> alanj@nevermore.WV.TEK.COM (Alan Jeddeloh) writes: >The National 83932 SONIC uses a 16-entry content-addressable memory to filter >incoming packets. The enties in the CAM can be any combination of multicast >addresses or physical addresses. This limits you to 16 different addresses, >but eliminates the need to do the software check. It seems as though 16 entries will get used up in a hurry once multicast gets going. And since the software that's wanting the different addresses lives at many different layers (eg, Ethernet, IP, some application like file service), and in many protocols (eg, IP, AppleTalk, OSI, etc), and the failure condition (running out of multicast slots) occurs at a very low level, I can foresee some very obscure error messages, and confused users. I'd suggest that any chip without a at least fallback to some soft-failure solution (like the AMD and Intel hash bucket scheme) would be a major lose. - RL "Bob" Morgan Stanford
lars@spectrum.CMC.COM (Lars Poulsen) (10/24/90)
In article <1990Oct18.172918.24929@forwiss.uni-passau.de> grass@unipas.fmi.uni-passau.de (Grass) writes: [How does Ethernet address recognition work ?] >As we found from the CSMA/CD ANSI/IEEE standard, there exists a *set* of >individual/multicast/broadcast addresses for each single station. Addresses >are 48 bits wide and the first bit (LSB) distinguishes individual (0) and >group (1) addresses. Group addresses may be multicast addresses (specified >by higher protocol layers!) or a particular broadcast address. This unique >broadcast address has to be predefined for the network and must be known by >every station. Usually 11...1 is chosen, but the standard leaves it open to >choose another address pattern. > >This sounds that at least group address recognition is done by software: all >messages with its first destination address bit set are received by every >station, transferred to some place in memory and examined by some software >routines. If the destination address does not match with the actual set of >active group addresses the whole message is discarded from memory. What a >waste of cpu/memory/bus ressources! Early Ethernet controllers did exactly that. It is simple, and not really all that much work. Computers already "waste" a lot of cycles. Just think of all the cycles that go into displaying windows on your desk top ... >To save up these ressources the Ethernet controller hardware (chip?) could >be provided with *all* addresses it shall respond to. Address decoding is >done by hardware. Only messages with according destination addresses are >passed. Providing a list of all active group addresses is not really practical. The list could be very long .. a hundred would be fairly typical. It takes a lot of silicon to do it, and to do it on the fly requires scanning the on-chip table during a very short window after the address is complete, before the data starts to flow. >Here we are back to our question: is hardware address decoding done in >practice? If yes, how many address pattern have to be buffered (adjusted by >switches??? 48-bit?) on average/maximum? "Modern" Ethernet controllers such as the AMD LANCE use a hash scheme, where a function is calculated over the set of active multicast addresses, and a bit mask allows the controller to discard a large subset of multicasts that are not desired at the station. What passes through the filter still needs to be checked in software, though. The proliferation of MAC-level bridges have forced an interesting solution to the problem. A bridge must pick up a large subset of traffic, delimited not by multicast addresses, but by "regular" addresses. Typically several hundred addresses are known, and partitioned into a set of "local" addresses, which can be ignored, and "remote" addresses, which must be forwarded. Since commodity ethernet controller chips do not support this, they must be configured in "promiscuous" mode, and receive ALL traffic, which is then filtered in software. This is very hairy on a loaded network (about 5000 frames per second; at least an order of magnitude above the commodity affordable class of processing power for embedded systems). The solution is to store the address table in a bank of "content-addressable memory". The ethernet chip is set in promiscuous mode, but the incoming address is loaded into a shift register in parallel with being fed to the ethernet chip. WHen the address is complete, a lookup is done on the CAM, which will tell in a single cycle, whetehr a match was found. If there is no match, a collision detect is generated to the ethernet chip, which then resumes scanning for the next frame without needing memory access to the receive buffer, and without generating any interrupts. Of course, this is a little out of range for your generic desktop system. >Please enlighten some curious greenhorns. Thank you in advance. Always a pleasure to enlighten the world. -- / Lars Poulsen, SMTS Software Engineer CMC Rockwell lars@CMC.COM
phil@brahms.amd.com (Phil Ngai) (10/26/90)
In article <1990Oct18.172918.24929@forwiss.uni-passau.de> grass@unipas.fmi.uni-passau.de (Grass) writes: |To save up these ressources the Ethernet controller hardware (chip?) could |be provided with *all* addresses it shall respond to. Address decoding is |done by hardware. Only messages with according destination addresses are |passed. HP has a new bridge which uses a pair of Am99C10A Content Addressable Memories. These devices can compare up to 256 48-bit addresses in 70 ns. HP's bridge also had a 32-bit RISC processor (Am29000). -- The Bill of Rights isn't perfect, but it's better than what we have now.