Statistical learning technique in a multi-port bridge for a local area network

• US 6,816,490 B1
• Filed: 03/19/1999
• Issued: 11/09/2004
• 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: Chung, David
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US09/272,959
• Time in Patent Office: 2,062 Days
• Field of Search: 370/389-394, 370/400, 370/401, 370/475, 370/471
• US Class Current: 370/392
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/40013 Details regarding a bus controller
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 12/42 Loop networks
• 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/201 Multicast operation; Broadcast operation
• 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

A statistical learning technique in a multi-port bridge for a local area network (LAN). In response to data packets received by the multi-port bridge, learning operations are performed for updating a look-up table in the multi-port bridge. The look-up table is also utilized for identifying an appropriate destination port for each data packet by performing a look-up operation. A learning operation, however, is performed only in response to selected ones of the data packets. A statistical learning controller determines whether a received data packet is a broadcast or uni-cast packet. If the packet is a broadcast or multi-cast packet, the statistical learning controller forwards a request for a learning operation. Upon being granted, the look-up table is updated. It the packet is a uni-cast packet, the statistical learning controller forwards a request for a learning operation only if (m) uni-cast packets have been received since a prior learning operation was performed for a uni-cast packet. In the preferred embodiment, (m) is sixteen. Accordingly, the look-up table is preferably updated in response to every broadcast and multi-cast packet and in response to every sixteenth uni-cast data packet. The invention minimizes the need to preoccupy the look-up table for performing learning operations and, thus, increases the availability of the look-up table for performing look-up operations.

Claims

1. An apparatus for directing data packets through a multi-port bridge for a local area network (LAN), the apparatus comprising:

a. table means for storing addresses of nodes of the LAN in association with an identification of a port of the multi-port bridge corresponding to each stored address;

b. look-up means coupled to the table means for identifying destination ports for each of a plurality of at least (m) uni-cast packets received by the multi-port bridge; and

c. learning means coupled to the table means for updating the table means only in response to every (m)th uni-cast data packet of the plurality of at least (m) uni-cast data packets, wherein m is greater than one.

2. An apparatus for directing data packets through a multi-port bridge for a local area network (LAN), the apparatus comprising:

a. table means for storing addresses of nodes of the LAN in association with an identification of a port of the multi-port bridge corresponding to each stored address; and

b. learning means coupled to the table means for updating the table means once for every (m) uni-cast packets received by the multi-port bridge, wherein m is greater than one.

3. The apparatus according to claim 2 wherein the learning means also updates the table means once for each broadcast data packet received by the multi-port bridge.

4. The apparatus according to claim 2 wherein the learning means also updates the table means once for each multi-cast data packet received by the multi-port bridge.

5. A multi-port bridge for a local area network (LAN), the multi-port bridge comprising:

a. a look-up table wherein the look-up table stores addresses of nodes of the LAN in association with an identification of a port of the multi-port bridge corresponding to each stored address; and

b. a statistical learning controller coupled to the look-up table wherein the statistical learning controller selectively updates the look-up table in response to a data packet received by the multi-port bridge based upon a destination address included in the data packet and the statistical learning controller performs a learning operation based upon a first bit of the destination address included in the packet and further wherein the statistical learning apparatus performs the learning operation when the first bit of the destination address is a logic zero and a predetermined number of destination addresses having the logic zero for the first bit have been received without having performed the learning operation in response to the destination address having the logic zero for the first bit.

6. The multi-port bridge according to claim 5 wherein the statistical learning controller performs the learning operation when the first bit of the destination address is a logic one.

7. The multi-port bridge according to claim 5 wherein the statistical learning controller performs the learning operation when the destination address indicates that the data packet is a broadcast data packet.

8. The multi-port bridge according to claim 7 wherein the statistical learning controller performs the learning operation when the destination address indicates that the data packet is a multi-cast data packet.

9. A multi-port bridge for a local area network (LAN), the multi-port bridge comprising:

a. a look-up table wherein the look-up table stores addresses of nodes of the LAN in association with an identification of a port of the multi-port bridge corresponding to each stored address; and

b. a statistical learning controller coupled to the look-up table wherein the statistical learning controller selectively updates the look-up table in response to a data packet received by the multi-port bridge based upon a destination address included in the data packet, and further wherein the statistical learning controller performs a learning operation when the destination address indicates that the data packet is a uni-cast packet and a predetermined number of uni-cast packets have been received without having performed the learning operation in response to a uni-cast packet.

10. A method of statistically updating a look-up table in a multi-port bridge for a local area network (LAN), the method comprising:

a. receiving a data packet;

b. determining whether the data packet is a uni-cast data packet;

c. when the data packet is a uni-cast data packet, determining whether a predetermined number of uni-cast data packets have been received without having updated the look-up table in response; and

d. when the predetermined number of uni-cast data packets have been received without having updated the look-up table in response, updating the look-up table in response to the data packet.

11. The method according to claim 10 wherein when the data packet is not a uni-cast packet, updating the look-up table in response to the data packet.

12. The method according to claim 10 wherein when the predetermined number of data packets has not been received updating a counter for maintaining a count of data packets received without having updated the look-up table in response.

13. The method according to claim 10 wherein when the predetermined number of uni-cast data packets have been received without having updated the look-up table in response, initializing a count to the predetermined number.

14. The method according to claim 13 further comprising decrementing the count for each uni-cast packet received until the count reaches zero.

15. The method according to claim 14 wherein when the count reaches zero, upon receiving a next uni-cast data packet:

a. updating the look-up table in response to the next uni-cast data packet; and

b. re-initializing the count to the predetermined number.

16. A method of statistically updating a look-up table in a multi-port bridge for a local area network (LAN), the method comprising:

a. receiving a data packet; and

b. determining whether a predetermined period of time has elapsed since the multi-port bridge was last powered-on or reset, and when the predetermined period of time has not elapsed, updating the look-up table in response to the data packet, and when the predetermined period of time has elapsed;

a. determining whether the data packet is a uni-cast data packet;

b. when the data packet is a uni-cast data packet, determining whether a predetermined number of uni-cast data packets have been received without having updated the look-up table in response; and

c. when the predetermined number of uni-cast data packets have been received without having updated the look-up table in response, updating the look-up table in response to the data packet.

17. The method according to claim 16 wherein when the data packet is not a uni-cast packet, performing a step of updating the look-up table in response to the data packet.

18. A multi-port bridge for interconnecting a plurality of segments of a local area network (LAN), the multi-port bridge comprising:

a. a plurality of ports, each port for communicating with a corresponding segment of the LAN;

b. a communication bus coupled to each of the plurality of ports;

c. a look-up table coupled to the communication bus wherein the look-up table stores addresses of nodes of the LAN in association with an identification of a port of the multi-port bridge corresponding to each stored address;

d. a look-up controller coupled to the look-up table for identifying a destination port for each of a plurality of at least (m) uni-cast data packets received by the multi-port bridge; and

e. a statistical learning controller coupled to the look-up table wherein the statistical learning controller updates the look-up table in response to every (m)th uni-cast data packet received by the multi-port bridge and in response to every broadcast data packet received by the multi-port bridge, wherein m is greater than one.

19. The multi-port bridge according to claim 18 further comprising a data bus coupled to each of the plurality of ports for transferring data packets to their corresponding destination port.

20. The multi-port bridge according to claim 19 further comprising a data packet buffer coupled to the data bus for temporarily storing data packets undergoing transfer to their corresponding destination port.