Switching ethernet controller

• US RE38,821 E1
• Filed: 07/12/2001
• Issued: 10/11/2005
• Est. Priority Date: 01/31/1996
• Status: Expired due to Term

• Current Assignee: Marvell Israel Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell Semiconductor Israel, Ltd.
• Inventors: Shemla, David, Willenz, Avigdor
• Primary Examiner(s): Pezzlo, John
• Application Number:
  US09/903,808
• Time in Patent Office: 1,552 Days
• Field of Search: 370/389, 370/392, 370/400, 370/401, 370/402, 370/403, 370/445, 370/910, 370/912, 370/412, 711/200, 711/202, 711/216, 711/221
• US Class Current: 370/402
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

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.

Claims

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 to store addresses of ports within said Ethernet network;

c. a hash table address control for hashing to hash 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 to associate 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 to direct 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 to transfer the directed 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 network controller, comprising:

a plurality of ports including (i) at least a source port capable of communicating with a source device, and (ii) a destination port capable of communicating with a destination device, the source device having a source address and the destination device having a destination address, wherein the source device transmits at least one packet to the destination device, the packet comprising at least one of the destination address and a combination of the destination address and data;

a hash table comprising a plurality of hash table locations to store destination addresses;

a hash table address controller to hash the destination address from the at least one packet for comparison with the addresses stored in at least one of said plurality of hash table locations;

an empty list including a multiplicity of single bit buffers; and

a packet storage manager to associate a state of the bit of a single bit buffer with one of an empty state and a full state of an associated contiguous buffer and for generating the address of a contiguous buffer through a simple function of one of an address and a number of its associated single bit buffer,

wherein if an address stored in one of said plurality of hash table locations matches the destination address, said hash table address controller provides information that causes data to be transmitted from said source port to said destination port, and

wherein if an address stored in the one of said plurality of hash table locations does not match the destination address, said hash table address controller changes the address stored in the one of said plurality of hash table locations by a predetermined amount.

4. A network controller according to claim 3, wherein the predetermined amount is a prime number.

5. A network controller according to claim 3, further comprising a memory having a plurality of buffers, wherein each of said plurality of ports corresponds to a respective one of said plurality of buffers.

6. A network controller according to claim 3, further comprising a data transfer manager, said hash table address controller providing information to said data transfer manager for directing the data from said source port to said destination port.

7. A network controller according to claim 3, wherein said hash table address controller compares the destination address from the packet with the addresses stored in at least two of said plurality of hash table locations.

8. A network controller according to claim 7, wherein the hash table controller compares the destination address from the packet with the addresses stored in at least two of said plurality of hash table locations by continuing to fetch additional addresses stored in the hash table locations, up to a predetermined amount.

9. A network controller, comprising:

a plurality of ports including (i) at least a source port capable of communicating with a source device, and (ii) at least a destination port capable of communicating with a destination device, the source device having a source address and the destination device having a destination address, wherein the source device transmits at least one packet to the destination device, the packet comprising at least one of the destination address and a combination of the destination address and data;

a hash table comprising a plurality of hash table locations to store destination addresses;

a hash table address controller to hash the destination address from the packet for comparison with the addresses stored in at least one of said plurality of hash table locations; and

a transfer manager, wherein, if an address stored in one of said plurality of hash table locations matches the destination address as compared by said hash table address controller, said data transfer manager sends the data from said source port to said destination port,

wherein, if an address stored in the one of said plurality of hash table locations does not match the destination address, said hash data address controller changes the addresses stored in the one of said plurality of hash table locations by a predetermined amount.

10. A network controller according to claim 9, wherein the predetermined amount is a prime number.

11. A network controller according to claim 9, further comprising a memory having a plurality of buffers, wherein each of said plurality of ports corresponds to a respective one of said plurality of buffers.

12. A network controller, comprising:

a plurality of ports including (i) at least a source port capable of communicating with a source device, and (ii) at least a destination port capable of communicating with a destination device, the source device having a source address and the destination device having a destination address, wherein the source device transmits at least one packet to the destination device, the packet comprising at least one of the destination address and a combination of the destination address and data;

a hash table comprising a plurality of hash table locations to store destination addresses;

a hash table address controller to hash the destination address from the packet for comparison with the addresses stored in at least two of said plurality of hash table locations; and

a transfer manager, wherein, if an address stored in one of said plurality of hash table locations matches the destination address as compared by said hash table address controller, said data transfer manager sends the data from said source port to said destination port.

13. A network controller according to claim 12, wherein the hash table controller compares the destination address from the packet with the addresses stored in at least two of said plurality of hash table locations by continuing to fetch additional addresses stored in the hash table locations, up to a predetermined amount.

14. A network controller, comprising:

a plurality of port means for communicating information, including (i) at least a source port means for communicating with a source device, and (ii) a destination port means for communicating with a destination device, the source device having a source address and the destination device having a destination address, wherein the source device transmits at least one packet to the destination device, the packet comprising at least one of the destination address and a combination of the destination address and data;

a plurality of hash table location means for storing destination addresses; and

hash table address controller means for hashing the destination address from the packet for comparison with the addresses stored in at least one of said plurality of hash table location means,

wherein if an address stored in one of said plurality of hash table location means matches the destination address, said hash table address controller means provides information that causes data to be transmitted from said source port means to said destination port means, and

wherein if an address stored in the one of said plurality of hash table location means does not match the destination address, said hash table address controller means changes the address stored in the one of said plurality of hash table location means by a predetermined amount.

15. A network controller according to claim 14, wherein the predetermined amount is a prime number.

16. A network controller according to claim 14, comprising a plurality of buffer means for storing information, wherein each of said plurality of port means corresponds to a respective one of said buffer means.

17. A network controller according to claim 14, further comprising data transfer manager means for directing the data in said source port means to said destination port means in accordance with said hash table address controller means.

18. A network controller according to claim 14, wherein said hash table address controller means compares the destination address from the packet with the addresses stored in at least two of said plurality of hash table location means.

19. A network controller according to claim 18, wherein said hash table address controller means compares the destination address from the packet with the addresses stored in at least two of said plurality of hash table location means by continuing to fetch additional addresses stored in the hash table location means, up to a predetermined amount.

20. A network controller, comprising:

a plurality of port means for communicating information, including (i) at least a source port means for communicating with a source device, and (ii) a destination port means for communicating with a destination device, the source device having a source address and the destination device having a destination address, wherein the source device transmits at least one packet to the destination device, the packet comprising at least one of the destination address and a combination of the destination address and data;

a plurality of hash table location means for storing destination addresses;

hash table address controller means for hashing the destination address from the packet for comparison with the addresses stored in at least one of said plurality of hash table location means;

a multiplicity of single bit buffer means for determining one of an empty state and a full state of an associated contiguous buffer means for storing information;

packet storage manager means for associating a state of a bit of a single bit buffer means with one of the empty state and the full state of an associated contiguous buffer means, and for generating the address of a contiguous buffer means through a simple function of one of an address and a number of its associated single bit buffer means; and

transfer manager means for sending the data from said source port means to said destination port means, when an address stored in one of said plurality of hash table location means matches the destination address as compared by said hash table address controller means.

21. A network controller according to claim 20, wherein if an address stored in the one of said plurality of hash table location means does not match the destination address, said hash table address controller means changes the address stored in the one of said plurality of hash table location means by a predetermined amount.

22. A network controller according to claim 21, wherein the predetermined amount is a prime number.

24. A network controller according to claim 20, wherein said hash table address controller means compares the destination address from the packet with the addresses stored in at least two of said plurality of hash table location means.

25. A network controller according to claim 24, wherein said hash table address controller means compares the destination address from the packet with the addresses stored in at least two of said plurality of hash table location means by continuing to fetch additional addresses stored in the hash table location means, up to a predetermined amount.

26. A method of controlling communication among a plurality of ports comprising (i) a source port in communication with a source device and (ii) a destination port in communication with a destination device, the source device having a source address and the destination device having a destination address, wherein the source device transmits at least one packet to the destination device, the packet comprising at least one of the destination address and a combination of the destination address and data, the method comprising the steps of:

a. storing destination addresses in one of a plurality of hash table locations;

b. hashing the destination address from the at least one packet;

c. comparing the hashed destination address from step b with the addresses stored in at least one of the plurality of hash table locations;

d. transmitting the data from the source port to the destination port if an address stored in one of the plurality of hash table locations matches the destination address compared in step c, or changing an address stored in the one of the plurality of hash table locations by a predetermined amount if an address stored in the one of the plurality of hash table locations does not match the destination address compared in step c.

23. A network controller according to claim 28, wherein each of said plurality of port means corresponds to a respective one of said contiguous buffer means.

27. A method according to claim 26, further comprising the step of repeating step c while there is an absence of a match between an address stored in the one of the plurality of hash table locations and the destination address compared to step c.

28. A method according to claim 26, wherein the predetermined amount is a prime number.

29. A method according to claim 26, further comprising the step of buffering the data received by the source port from the source device.

30. A method according to claim 26, further comprising the step of directing the data from the source port to the destination port in accordance with step d.

31. A method according to claim 26, wherein step d compares the destination address from the packet with the addresses stored in at least two of the plurality of hash table locations.

32. A method according to claim 31, wherein step d compares the destination address from the packet with the addresses stored in at least two of the plurality of hash table locations by continuing to fetch additional addresses stored in the hash table locations, up to a predetermined amount.

33. A method of controlling communication among a plurality of ports comprising (i) at least a source port in communication with a source device and (ii) a destination port in communication with a destination device, the source device having a source address and the destination device having a destination address, wherein the source device transmits at least one packet to the destination device, the packet comprising at least one of the destination address and a combination of the destination address and data, the method comprising the steps of:

a. storing destination addresses in one of a plurality of hash table locations;

b. hashing the destination address from the packet;

c. comparing the hashed destination address from step b with the addresses stored in at least one of the plurality of hash table locations, and changing an address stored in the one of the plurality of hash table locations by a predetermined amount if the address stored in the one of the plurality of hash table locations does not match the hashed destination address;

d. directing the data from the source port for transmission to the destination port if an address stored in one of the plurality of hash table locations matches the destination address as compared in step c.

34. A method according to claim 33, further comprising the step of repeating step c while there is an absence of a match between an address stored in the one of the plurality of hash table locations and the destination address compared in step c.

35. A method according to claim 33, wherein the predetermined amount is a prime number.

36. A method according to claim 33, further comprising the step of buffering the data received by the source port from the source device.

37. A method of controlling communication among a plurality of ports comprising (i) at least a source port in communication with a source device and (ii) a destination port in communication with a destination device, the source device having a source address and the destination device having a destination address, wherein the source device transmits at least one packet to the destination device, the packet comprising at least one of the destination address and a combination of the destination address and data, the method comprising the steps of:

a. storing destination addresses in one of a plurality of hash table locations;

b. hashing the destination address from the packet;

c. comparing the hashed destination address from step b with the addresses stored in at least two of the plurality of hash table locations;

d. directing the data from the source port for transmission to the destination port if an address stored in one of the plurality of hash table locations matches the destination address as compared in step c.

38. A method according to claim 37, wherein step c further comprises the step of comparing the destination address from the packet with the addresses stored in at least two of the plurality of hash table locations by continuing to fetch additional addresses stored in the hash table locations, up to a predetermined amount.