Address look-up mechanism in a multi-port bridge for a local area network
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
22 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
(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. - View Dependent Claims (15, 16, 17, 18, 19)
-
-
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. - View Dependent Claims (21, 22)
-
Specification