Switching ethernet controller

Abstract

An Ethernet controller, for use within an Ethernet network of other Ethernet controller connected together by a bus, is provided. The Ethernet controller includes a plurality of ports including at least one bus port associated with ports connected to other switching Ethernet controllers, a hash table for storing addresses of ports within the Ethernet network, a hash table address control, a storage buffer including a multiplicity of contiguous buffers in which to temporarily store said packet, an empty list including a multiplicity of single bit buffers, a packet storage manager, a packet transfer manager and a write-only bus communication unit. The hash table address control hashes the address of a packet to initial hash table location values, changes the hash table location values by a fixed jump amount if the address values stored in the initial hash table location do not match the received address, and provides at least an output port number of the port associated with the received address. The packet storage manager associates the state of the bit of a single bit buffer with the empty or full state of an associated contiguous buffer and generates the address of a contiguous buffer. The packet transfer manager directs the temporarily stored packet to the port determined by said hash table control unit. The write-only bus communication unit is activated by the packet transfer manager, for transferring the packet out of the bus port by utilizing the bus for write only operations.

We claim: 
     
       1. A generally full-wire throughput, switching Ethernet controller for use within an Ethernet network of other switching Ethernet controllers connected together by a bus, the controller comprising:
 a. a plurality of ports including at least one bus port associated with ports connected to other switching Ethernet controllers;   b. a hash table for storing addresses of ports within said Ethernet network;   c. hash table address control for hashing the address of a packet to initial hash table location values, for changing the hash table location values by a fixed jump amount if the address values stored in said initial hash table location does not match the received address, and for providing at least an output port number of the port associated with the received address;   d. a storage buffer including a multiplicity of contiguous buffers in which to temporarily store said packet;   e. an empty list including a multiplicity of single bit buffers;   f. a packet storage manager for associating the state of the bit of a single bit buffer with the empty or full state of an associated contiguous buffer and for generating the address of a contiguous buffer through a simple function of the address or number of its associated single bit buffer;   g. a packet transfer manager for directing said temporarily stored packet to the port determined by said hash table control unit; and   h. a write-only bus communication unit, activated by said packet transfer manager, for transferring said packet out said at least one bus port by utilizing said bus only for write operations.   
     
     
       2. A controller according to  claim 1  and wherein said write-only bus communication unit includes a direct memory access controller. 
     
     
       3. A switching controller comprising:
 a hash table including a plurality of entries, each entry storing a destination address tag and forwarding information;   a hash table controller that selects a first entry of the hash table based on a hash of a destination address of a packet; and   a packet transfer manager that
 (i) forwards the packet according to the forwarding information of the first entry when the destination address of the packet matches the destination address tag of the first entry, and 
 (ii) forwards the packet according to the forwarding information of a second entry of the hash table when the destination address of the packet does not match the destination address tag of the first entry but does match the destination address tag of the second entry.  
   
     
     
       4. The switching controller of claim 3 wherein:
 for each of the entries of the hash table, the forwarding information specifies a destination port; and   the packet transfer manager forwards the packet to the destination port specified by the first entry when the destination address of the packet matches the destination address tag of the first entry.    
     
     
       5. The switching controller of claim 3 wherein the packet transfer manager forwards the packet according to the forwarding information of a third entry of the hash table when the destination address of the packet matches neither the destination address tag of the first entry nor the destination address tag of the second entry.  
     
     
       6. The switching controller of claim 3 wherein:
 the hash table stores each of the entries of the hash table at a respective address within the hash table;   the hash table controller determines a first hash table address based on a hash of the destination address of the packet;   the hash table controller selects the entry stored at the first hash table address as the first entry;   the hash table controller determines a second hash table address based on the first hash table address; and   the hash table controller selects the entry stored at the second hash table address as the second entry.    
     
     
       7. The switching controller of claim 6 wherein the hash table controller determines the second hash table address based on a sum of the first hash table address and a predetermined offset.  
     
     
       8. The switching controller of claim 7 wherein the predetermined offset is a prime number.  
     
     
       9. The switching controller of claim 7 wherein the hash table has an address space size and the hash table controller calculates the sum modulo the address space size.  
     
     
       10. The switching controller of claim 6 wherein:
 before comparing the destination address of the packet to the destination address tag of the first entry, the hash table controller generates a plurality of hash table addresses including the first hash table address and the second hash table address; and   after determining the first hash table address, the hash table controller generates remaining ones of the hash table addresses by repeatedly determining a sum of a previous one of the hash table addresses and a predetermined offset.    
     
     
       11. The switching controller of claim 10 wherein the packet transfer manager concurrently compares the destination address of the packet to the destination address tags of the entries stored at the plurality of hash table addresses.  
     
     
       12. The switching controller of claim 10 wherein:
 when the destination address of the packet does not match any of the destination address tags of the entries stored at the plurality of hash table addresses, the hash table controller generates a second plurality of hash table addresses; and   the hash table controller generates a first one of the second plurality of hash table addresses based on a sum of a last one of the plurality of hash table addresses and the predetermined offset.    
     
     
       13. The switching controller of claim 12 wherein the hash table has an address space size, and wherein the hash table controller calculates the sums modulo the address space size.  
     
     
       14. A method for operating a switching controller, the method comprising:
 storing a plurality of entries in a hash table, each entry including a destination address tag and forwarding information;   receiving a packet;   selecting a first entry of the hash table based on a hash of a destination address of the packet;   forwarding the packet according to the forwarding information of the first entry when the destination address of the packet matches the destination address tag of the first entry; and   forwarding the packet according to the forwarding information of a second entry of the hash table when the destination address of the packet does not match the destination address tag of the first entry but does match the destination address tag of the second entry.    
     
     
       15. The method of claim 14 wherein for each of the entries of the hash table, the forwarding information specifies a destination port, the method further comprising forwarding the packet to the destination port specified by the first entry when the destination address of the packet matches the destination address tag of the first entry.  
     
     
       16. The method of claim 14 further comprising forwarding the packet according to the forwarding information of a third entry of the hash table when the destination address of the packet matches neither the destination address tag of the first entry nor the destination address tag of the second entry.  
     
     
       17. The method of claim 14 further comprising:
 storing each of the entries of the hash table at a respective address within the hash table;   determining a first hash table address based on a hash of the destination address of the packet;   selecting the entry stored at the first hash table address as the first entry;   determining a second hash table address based on the first hash table address; and   selecting the entry stored at the second hash table address as the second entry.    
     
     
       18. The method of claim 17 further comprising determining the second hash table address based on a sum of the first hash table address and a predetermined offset.  
     
     
       19. The method of claim 18 wherein the predetermined offset is a prime number.  
     
     
       20. The method of claim 17 further comprising:
 before comparing the destination address of the packet to the destination address tag of the first entry, generating a plurality of hash table addresses including the first hash table address and the second hash table address; and   after determining the first hash table address, generating remaining ones of the hash table addresses by repeatedly determining a sum of a previous one of the hash table addresses and a predetermined offset.    
     
     
       21. The method of claim 20 further comprising concurrently comparing the destination address of the packet to the destination address tags of the entries stored at the plurality of hash table addresses.  
     
     
       22. The method of claim 20 further comprising:
 when the destination address of the packet does not match any of the destination address tags of the entries stored at the plurality of hash table addresses, generating a second plurality of hash table addresses; and   generating a first one of the second plurality of hash table addresses based on a sum of a last one of the plurality of hash table addresses and the predetermined offset.