Statistical learning technique in a multi-port bridge for a...

Details Statistical learning technique in a multi-port bridge for a... Statistical learning technique in a multi-port bridge for a...

1999-03-19

2004-11-09

Nguyen, Chau (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S401000

Reexamination Certificate

active

06816490

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to a multi-port bridge for a local area network. More particularly, the invention relates to a technique for statistically reducing a number of learning operations required to be performed for updating a look-up table utilized for directing data packets through a multi-port bridge a local are network.
BACKGROUND OF THE INVENTION
Nodes of a local area network (LAN) are typically interconnected by a shared transmission medium. The amount of data traffic that the shared transmission medium can accommodate, however, is limited. For example, only one node at a time can successfully transmit data to another node over the shared transmission medium. If two or more nodes simultaneously attempt to transmit data, a data collision-occurs, which tends to corrupt the data being transmitted. Thus, nodes that share a transmission medium are considered to be in a same collision domain.
A multi-port bridge allows simultaneous communication between nodes of the LAN by segmenting the LAN into multiple collision domains (also referred to as network segments or LAN segments), each segment having a corresponding transmission medium.
FIG. 1
illustrates a conventional local area network including a multi-port bridge
10
.
The multi-port bridge
10
has eight ports A-H, though the number of ports can vary. Each port A-H is connected to a segment
11
-
18
of the LAN. Each segment
11
-
18
typically includes one or more nodes
19
-
34
, such as a workstation, a personal computer, a data terminal, a file server, a printer, a facsimile, a scanner or other conventional digital device. Each of the nodes
19
-
34
has an associated node address (also referred to as a medium access control (MAC) address) which uniquely identifies the node. The nodes
19
-
34
are configured to send data, one to another, in the form of discrete data packets.
When the LAN operates according to Ethernet standards, such as the Institute of Electrical and Electronics Engineers (IEEE) 802.3 standard, data is communicated in the form of discrete packets.
FIG. 2
illustrates a conventional IEEE 802.3 data packet
40
. The data packet
40
includes an eight byte long pre-amble
41
which is generally utilized for synchronizing a receiver to the data packet
40
. The pre-amble
41
includes seven bytes of pre-amble and one byte of start-of-frame. Following the pre-amble
41
, the data packet
40
includes a six-byte-long destination address
42
, which is the node address of a node which is an intended recipient for the data packet
40
. Next, the data packet
40
includes a six-byte-long source address
43
, which is the node address of a node which originated the data packet
40
. Following the source address
43
is a two-byte length field
44
. Following the length field
44
is a data field
45
. The data field
45
can be up to 1500 bytes long. Finally, the data packet
40
includes a two-byte frame check field
46
which allows a recipient of the data packet
40
to determine whether an error has occurred during transmission of the data packet
40
.
When a node (source node) sends data to another node (destination node) located on its same segment of the LAN (intra-segment communication), the data is communicated directly between the nodes without intervention by the multi-port bridge
10
and is known as an intra-segment packet. Therefore, when the multi-port bridge
10
receives an intra-segment packet, the multi-port bridge
10
does not bridge the packet (the packet is filtered). When a node (source node) sends a data packet to another node (destination node) located on a different segment (inter-segment communication), the multi-port bridge
10
appropriately forwards the data packet to the destination node.
More particularly, the multi-port bridge
10
(
FIG. 1
) receives each data packet
40
(FIG.
2
) and must determine whether the data packet
40
is for intra-segment communication or inter-segment communication, and if the data packet
40
is for inter-segment communication, the multi-port bridge
10
must determine to which port (destination port) the data packet
40
is to be directed based upon the destination address
42
contained in the data packet
40
. This can be accomplished by utilizing a look-up table which associates the destination address
42
included in the packet
40
to a port of the multi-port bridge
10
. Conventionally, the look-up table is constructed by executing a learning operation and a look-up operation for each received data packet
40
. Thus, the learning operation is placed in the critical path of the packet and must also be completed before the packet can be directed to the appropriate to destination port. During the learning operation, the source address
43
from the data packet
40
is stored in the table in association with the identification of the source port. During the look-up operation, the destination address
42
is utilized to look-up data stored during the learning operation for a prior packet so as to identify the appropriate destination port for the packet
40
.
Problems can arise, however, when the capabilities of the multi-port bridge
10
are exceeded by network demand. When data packets
40
are received by the multi-port bridge
10
at a rate that is higher than the rate at which the multi-port bridge
10
can appropriately perform a learning operation and a look-up operation for each packet
40
and, then, forward the packet, the multi-port bridge
10
becomes a source of network congestion. This problem is exacerbated as network users place increasing demands on the network.
Therefore, what is needed is improved technique for increasing the data packet handling capacity in a multi-port bridge for a local area network.
SUMMARY OF THE INVENTION
The invention is 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 utilized for identifying an appropriate destination port for the data packets by performing a look-up operation for each data packet. In accordance with the present invention, a learning operation is not performed for every packet received by the multi-port bridge. Rather, a learning operation is performed only in response to selected ones of the data packets. This 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.
A plurality of ports of the multi-port bridge are each coupled to a look-up bus. The look-up bus is coupled to the look-up table via a memory controller. Accordingly, look-up and learning operations for data packets received by a port of the multi-port bridge are performed via the look-up bus and the memory controller. The memory controller includes a look-up address queue and a learning address queue each of which are coupled to the look-up bus. In addition, a look-up controller is coupled to the look-up address queue, while a statistical learning controller is coupled to the learning address queue. A memory arbiter controls access to the look-up table.
When a data packet is received by a source port for the packet, the source port transfers the destination and source addresses for the packet via the look-up bus to the memory controller. The destination and source addresses for the packet are simultaneously stored in both the look-up address queue and in the learning address queue. When the look-up controller is available for performing a next look-up operation, the look-up controller requests permission to access the look-up table from the memory arbiter. Upon being granted permission, the look-up controller accesses the look-up table for determining whether the received packet is to be filtered, or if not filtered, to identify the appropriate destination port for the packet. The results of the look-up operation are then returned to the look-up bus where they are ava

Affiliated with

Also associated with

Rating

Statistical learning technique in a multi-port bridge for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Statistical learning technique in a multi-port bridge for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical learning technique in a multi-port bridge for a... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3339997