Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-06-19
2002-09-03
Najjar, Saleh (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S239000, C709S240000, C709S241000, C709S242000, C359S199200, C370S230000, C370S229000, C370S256000
Reexamination Certificate
active
06446131
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to computer networks. More specifically, the present invention relates to bridges and other transparent layer-two devices for a local area network.
In a legacy local area network (“LAN”), each node of the LAN receives (or hears) all current on-going traffic. Each node looks at a destination address of each MAC frame placed on the LAN. A node accepts a MAC frame that is broadcasted or targeted directly to itself; otherwise the node discards the frame. This rather simplistic and trivial operation can provide adequate throughput and performance to small, low speed LANs, even though problems such as limited throughput could occur.
The LAN might be connected to other broadcast domains (e.g., another LAN) by a layer-three device such as a router. If a source node connected to the LAN sends frames to a destination node in a different broadcast domain, the frame would be forwarded to the different domain using layer-three mechanisms.
Such a LAN is typically segmented according to an 80/20 rule, in which inter-LAN traffic constitutes only 20% of the overall traffic. The throughput and the performance of this LAN architecture is limited because routing is usually done in software and is a rather expensive and slow operation.
As the number of nodes connected to the LAN is increased, it becomes increasingly difficult to follow the 80/20 rule. Increasing the number of broadcast domains while keeping constant the number of nodes in each broadcast domain could cause a substantial amount of inter-LAN traffic going through the routers and, hence, slow down the overall network performance. An alternative approach of increasing the number of nodes per broadcast domain would not be satisfactory because the number of collisions in each broadcast domain would be increased and the overall throughput would be reduced.
Bridges have been used to overcome this dilemma. Bridges are layer-two devices, which operate on frames and not packets. A bridge segments a LAN into multiple segments. Typically, a bridge is connected to two or more LAN segments. One function of the bridge is to forward or relay a frame from one segment to another segment at any given time instant. Broadcast messages are transmitted to all nodes on all segments connected to the bridge. However, unicast messages are sent only to the intended segments. Consequently, unicast messages intended for one segment are not heard by the other segments. Thus, by sending unicast messages to specific LAN segments, a bridge can reduce the overall number of collisions on a LAN.
If a bridge receives a unicast frame but does not know where to forward it (i.e. it does not know the specific LAN segment to which the destination node belongs), the bridge will broadcast the message to all of the LAN segments. It is therefore advantageous for a bridge to be aware of the overall topology of the LAN and know which node is connected to which segment.
Another function of bridges is to filter frames so that the destination node does not receive duplicate frames. To prevent the duplicate frames from being received, the bridges typically run an algorithm known as Spanning Tree algorithm. The Spanning Tree algorithm determines network connectivity such that there is at most one data route between any two nodes of the bridged LAN. The Spanning Tree algorithm starts with the bridged LAN's arbitrary topology and determines a single Spanning Tree. The Spanning Tree ensures that, at any moment, only one active physical path will be used between each pair of source and destination nodes of the network. For example,
FIG. 1
shows a network having two physical paths to a node. After running the spanning tree algorithm, one of those paths (crossed out with the large “X”) is made inactive (i.e., disabled).
Using the Spanning Tree algorithm, a bridged LAN can be dynamically reconfigured and new physical paths can be re-established. The Spanning Tree algorithm may be run whenever the network is booted up, whenever the network topology is changed (e.g., a new node is added, an existing node or a link fails), etc. It can take a relatively long time for the Spanning Tree algorithm to converge at a final Spanning Tree. It is not uncommon for thirty seconds to elapse before a final active Spanning Tree becomes stable. During this period while the Spanning Tree algorithm is being run, most of the frames are not forwarded to their intended destination and, therefore, are discarded.
The convergence speed of the Spanning Tree algorithm might be adequate for low speed networks. However it is usually too slow for high-speed LANs such as Fast Ethernet (100 BaseT) or Gigabit Ethernet. The slow speed can become a major drawback. Discarding thirty seconds worth of frames on a high speed network can amount to discarding a substantial amount of traffic.
Additionally, the Spanning Tree algorithm does not necessarily find an optimum path between any two nodes. For example, referring once again to
FIG. 1
, if a node connected to the third LAN sends a frame to a node connected to the second LAN, the frame will not be forwarded by the second bridge. Instead, the frame will be sent to the third bridge and then to the first bridge before arriving at the destination node.
There is a need to reduce the number of frames that are discarded while network connectivity is being determined. There is also a need to provide more optimal network connectivity.
SUMMARY OF THE INVENTION
The present invention meets these needs. According to one aspect of the invention, a transparent layer-two device of a local area network receives a MAC frame on an inbound port and handles the frame by determining whether the frame was previously received on a port other than the inbound port; discarding the frame if the frame was previously received; further filtering the frame if the frame was not discarded; and forwarding the frame if the frame was not filtered out.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.
REFERENCES:
patent: 4922503 (1990-05-01), Leone
patent: 5343471 (1994-08-01), Cassagnol
patent: 5396493 (1995-03-01), Sugiyama
patent: 6038600 (2000-03-01), Faulk, Jr. et al.
patent: 6128729 (2000-10-01), Kimball et al.
patent: 6169741 (2001-01-01), LeMaire et al.
patent: 6301256 (2001-10-01), Vasa
patent: 6308218 (2001-10-01), Vasa
Khansari Masoud
Lam Derek
LandOfFree
Bridges and other layer-two devices for forwarding MAC frames does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bridges and other layer-two devices for forwarding MAC frames, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bridges and other layer-two devices for forwarding MAC frames will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2868009