Address look-up mechanism in a multi-port bridge for a local area network

• US 6,308,218 B1
• Filed: 06/09/1998
• Issued: 10/23/2001
• Est. Priority Date: 09/17/1997
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Vasa, Suresh
• Primary Examiner(s): Harrell, Robert B.
• Assistant Examiner(s): WILLETT, STEPHAN F
• Application Number:
  US09/094,237
• Time in Patent Office: 1,232 Days
• Field of Search: 709/238, 709/242, 709/244, 709/245, 711/200, 711/205, 711/206, 711/207, 711/216, 713/162
• US Class Current: 709/238
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/135 by jamming the transmission media
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/102 using shared medium, e.g. bus or ring
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9057 Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 49/9089 replacing packets in a storage arrangement, e.g. pushout

Abstract

An address look-up mechanism in a multi-port bridge for controlling use of a memory as a look-up table for appropriately filtering and directing packets. The look-up table includes learned look-up tables, permanent look-up tables and linked lists. As a data packet originating from a node (source node) is received by a corresponding one of the ports (source port) of the multi-port bridge, a look-up cycle and then a learning cycle are each performed. During the learning cycle, an identification of the source port for the packet is stored in the learned look-up tables in association with a hashed node address of the source node. Each existing entry is examined to ensure that the appropriate port identification is stored and to determine whether two or more nodes share a same hashed node address. If two nodes have the same hashed node address, then a linked entry in the linked lists is formed. During the look-up cycle, the packet is examined to determine whether it is intended for a VLAN group, if the packet is to be broadcast to all nodes of the LAN or if the packet is intended for a single destination node. If the packet is intended for a VLAN group, the source node address for the packet is utilized to access an appropriate entry in the permanent table. If the packet is intended to be broadcast to all the nodes of the LAN, the packet is directed to all the ports. If the packet is intended for a single destination node, information stored in the learned look-up tables during learning cycles for prior packets is utilized to identify an appropriate destination port for the packet.

Claims

1. A method of directing packets through a multi-port bridge for a local area network, the multi-port bridge for interconnecting a plurality of segments of a local area network, wherein each segment is associated with a corresponding port of the multi-port bridge and includes one or more nodes the method comprising steps of:

(a) receiving a destination node address, a source node address and a source port identification for a current packet;

(b) performing a learning cycle for the current packet wherein the learning cycle includes steps of;

(1) hashing the source node address to form a hashed source address;

(2) identifying a first storage location in a memory device based upon the hashed source address;

(3) determining if an entry has been made at the first storage location and, when no entry has been made at the first storage location, storing the source port identification at the first storage location;

(4) determining whether the entry made at the first storage location was made in response to a prior packet having a same hashed source address as the current packet and having a corresponding source node address that is dissimilar from the source node address of the current packet;

(5) forming a linked entry at a fourth storage location wherein the linked entry includes the source port identification for the current packet; and

(6) storing an address of the fourth storage location in the first storage location;

(c) performing a look-up cycle for the current packet wherein the look-up cycle includes steps of;

(1) determining whether the current packet is intended for multiple destination nodes or a single destination node;

(2) when the current packet is intended for multiple destination nodes, identifying a destination port for the current packet according to information obtained from a second storage location, wherein the second storage location is identified based upon the source node address; and

(3) when the current packet is intended for a single destination node, identifying the destination port for the packet according to information obtained from third storage location, wherein the third storage location is identified based upon the destination node address.

2. The method according to claim 1 wherein the step of performing the learning cycle further comprises a step of examining a link valid/not valid indicator in the first storage location, and when the link valid/not valid indicator does not indicate a valid link, performing steps of:

(1) forming a linked entry at a fourth storage location wherein the linked entry includes the source port identification for the current packet;

(2) storing an address of the fourth storage location in the first storage location further comprising a step of conditioning a link valid/not valid indicator in the first storage location to indicate a valid link; and

(3) conditioning the link valid/not valid indicator to indicate a valid link.

3. The method according to claim 1 wherein the step of performing the learning cycle and the step of performing the look-up cycle are both performed by a finite state machine.

4. The method according to claim 1 wherein the step of performing the learning cycle is performed while the current packet is still being received by the source port for the current packet.

5. The method according to claim 1 wherein the step of performing the look-up cycle is performed while the current packet is still being received by the source port for the current packet.

6. The method according to claim 1 wherein the step of performing the learning cycle and the step of performing the look-up cycle are both performed while the current packet is still being received by the source port for the current packet.

7. The method according to claim 6 wherein the step of performing the learning cycle is performed after the step of performing the look-up cycle is complete.

8. The method according to claim 1 wherein the step of performing the learning cycle is performed after the step of performing the look-up cycle is complete.

9. The method according to claim 1 wherein the information obtained from the second storage location includes a binary logic value for each port of the multi-port bridge wherein each binary logic value is indicative of whether the corresponding port is a destination port for the current packet.

10. The method according to claim 9 wherein the ports of the multi-port bridge are interconnected by a communication bus, the communication bus having a plurality of signal lines and wherein each port uniquely corresponds to one signal line of the communication bus and further wherein each binary logic value is applied to the corresponding signal line of the communication bus upon completion of the look-up cycle.

11. The method according to claim 10 wherein each binary logic value is representative of whether each destination port is associated with a node that is a member of a group to which the source node for the current packet belongs.

12. The method according to claim 1 wherein the information obtained from the third storage location includes an identification of the destination port for the current packet.

13. The method according to claim 12 wherein the identification of the destination port for the current packet is stored in the third storage location during a learning cycle performed for a prior packet.

14. A method of directing packets through a multi-port bridge for a local area network, the multi-port bridge for interconnecting a plurality of segments of a local area network, wherein each segment is associated with a corresponding port of the multi-port bridge and includes one or more nodes, the method comprising steps of:

a. receiving a destination node address, a source node address and a source port identification for a current packet;

b. performing a learning cycle for the current packet wherein the learning cycle includes steps of;

(1) hashing the source address thereby forming a hashed source address for the current packet;

(2) identifying a first storage location in a memory device based upon the hashed source node address;

(3) determining whether an entry has been made at the first storage location;

(4) when no entry has been made at the first storage location, storing the source port identification at the first storage location;

(5) when an entry has been made at the first storage location, determining whether the entry made at the first storage location was made in response to a prior packet having a same hashed source node address as the current packet and having a corresponding source node address that is dissimilar from the source address of the current packet; and

(6) when the entry made at the first storage location was made in response to a prior packet having a same hashed source node address as the current packet and having a corresponding source node address that is dissimilar from the source address of the current packet, performing steps of;

(a) forming a linked entry at a second storage location wherein the linked entry includes the source port identification for the current packet; and

(b) storing an address of the fourth storage location in the first storage location.

15. The method according to claim 14 wherein the step of determining whether an entry has been made at the first storage location includes a step of examining an entry valid/not valid indicator stored in the first storage location.

16. The method according to claim 15 wherein when no entry has been made at the first storage location, performing a step of conditioning the entry valid/not valid indicator to indicate that the entry is valid.

17. The method according to claim 14 wherein the step of performing the learning cycle is performed while the current packet is still being received by the source port for the current packet.

18. The method according to claim 14 wherein when the entry made at the first storage location was not made in response to a prior packet having a same hashed source node address as the current packet and having a corresponding source node address that is dissimilar from the source address of the current packet, performing steps of comparing a port identification stored at the first storage location to the port identification for the current packet, and when the comparison does not indicate a match, replacing the port identification stored at the first storage location with the port identification for the current packet.

19. The method according to claim 14 wherein the step of hashing the source node address includes a step of removing bits from the source node address and wherein the step of determining whether the entry made at the first storage location was made in response to a prior packet having a same hashed source node address as the current packet and having a corresponding source node address that is dissimilar from the source address of the current packet comprises a step of comparing the bits removed from the source address to a value stored at the first storage location and when the comparison does not indicate a match, performing the step of forming a linked entry.

20. An apparatus for directing packets through a multi-port bridge for a local area network, the multi-port bridge for interconnecting a plurality of segments of a local area network, wherein each segment is associated with a corresponding port of the multi-port bridge and includes one or more nodes, the apparatus comprising:

a. a communication bus coupled to each port of the multi-port bridge;

b. a memory device coupled to the communication bus wherein the memory device includes a look-up table including a plurality of table entries, each table entry associating a node address of one of the nodes of the local area network with a port identification of one of the ports of local area network;

c. a learning FSM for generating and updating the look-up table according to a hashed node address of the source address for each packet, a port identification of a port which receives the packet, a valid/not valid indicator, and an address of a linked table entry wherein the learning FSM accesses the look-up table via the communication bus;

d. a look-up FSM for utilizing the look-up table to identify an appropriate destination port for each packet received by the multi-port bridge according to a destination address for the packet wherein the look-up FSM accesses the look-up table via the communication bus; and

e. a plurality of registers coupled to the communication bus and accessible to the learning FSM and the look-up FSM wherein the plurality of registers includes a source address register for storing a source address for each packet, a destination address register for storing a destination address for the packet, a port identification register for storing the identification of a port that receives the packet, a memory address register for storing an address within the memory device for a location in look-up table, and one or more table entry registers for storing entries of the look-up table.

21. The apparatus according to claim 20 further comprising a comparator coupled to the source address register and to the one or more table entry registers for comparing a selected bits from the source address for a newly received packet stored by the source address register to selected bits from the source address for a prior packet stored in the one or more table entry registers.

22. The apparatus according to claim 20 further comprising a comparator coupled to the port identification register and to the one or more table entry registers for comparing a port identification for a newly received packet to a port identification for a prior packet.