Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-08-05
2001-04-03
Chin, Wellington (Department: 2731)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S423000, C370S450000, C370S462000
Reexamination Certificate
active
06212194
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to a switch for routing data between buses, and in particular to a switch having a non-blocking arbitration system.
2. Description of Related Art
Networks route data transmissions between network stations. In some network system buses typically connect network stations to a central hub or switch. A network hub is simply a repeater receiving a data transmission (e.g. an Ethernet data packet or an ATM cell) arriving on any one input bus and rebroadcasting outward on all output buses. A header in the data packet or cell indicates the packet or cell destination. Each network station looks at the header to determine if it should accept or ignore the data transmission. One disadvantage to a hub repeater is that each bus carrying data transmissions to a network station not only must convey transmissions directed to that station but must carry packets directed to all other stations as well. That can put a heavy load on all hub output buses at times of high traffic and can reduce network throughput.
A network switch, on the other hand, routes an incoming data transmission outward only on the bus leading to its destination, thereby reducing the traffic load on network buses. A network switch typically includes input buffers for receiving and storing incoming transmissions from the network stations, output buffers for storing and then transmitting outgoing transmissions to the network stations and an intelligent routing system for selectively providing a data routing path for each incoming data transmission from an input buffer to the appropriate output buffer. Each input buffer typically stores each incoming transmission, determines the destination output buffer from the routing data included in the packet or cell header, and then requests the routing system to provide a data path between the input buffer and the destination output buffer. When the routing system establishes the data path, the input buffer sends the transmission to the output buffer via the data path.
Since input buffers may have competing routing requests, the routing system must include an arbitration system for determining which requests are granted. Such an arbitration system for an Ethernet network switch is described in U.S. Pat. No. 5,689,664 entitled “Network Switch With Arbitration System”, issued Nov. 18, 1997 to Chou et al, (incorporated herein by reference). When Chou's arbitration system grants a request it signals the input buffer that made the request that it may begin forwarding a data packet to the output buffer via the switching mechanism. When the arbitration system thereafter learns that the data packet has been sent to the output buffer and that the output buffer is ready to receive another data packet, the arbitration system allows all input buffers to once again compete for a data routing path to the output buffer.
In Chou's network switch, an input buffer stores all incoming data packets but requests a data routing path only to the output buffer that is to receive its longest-stored data packet. If that output buffer is busy, the requesting input buffer is not only blocked from forwarding its longest-stored data packet to the busy output buffer, it is also blocked from forwarding any later stored data packet to other output buffers, even when they are idle.
What is needed is a network switch having an improved arbitration system wherein an input buffer storing a data transmission destined for a busy output buffer is not blocked from sending a subsequently stored data transmission to an idle output buffer.
SUMMARY OF THE INVENTION
A network switch in accordance with the present invention receives and stores each data transmission arriving at any of several input buses and then forwards the data transmission outward from the switch on an appropriate one of several output buses. The switch the includes a set of input buffers for receiving the transmissions, a set of output buffers for forwarding the transmissions and a routing system for selectively providing data paths for routing data transmissions from the input buffers to the output buffers. Each input buffer receives and stores each incoming data transmission arriving on a corresponding input bus and determines from routing information included in the data transmission which output port is to forward the data transmission outward from the switch. The input buffer then sends a routing request to the routing system requesting a data path to the appropriate output buffer. When the routing system establishes the data path, the input buffer sends the data transmission over that path to the output buffer. The output buffer stores the data transmission and then forwards it outward from the switch via a corresponding output bus.
In accordance the invention, the routing system sends STATUS data to each input buffer indicating whether each output buffer is busy receiving a data transmission from an input buffer or is idle and ready to receive a data transmission. When an input buffer is ready to forward a data transmission to an output buffer, it sends a routing request to the routing system requesting a data routing path to the destination output buffer for its longest-stored data transmission, provided that data transmission is to be forwarded to an idle output buffer, as indicated by the STATUS data. If the output buffer to receive an input buffer's longest-stored data transmission is busy, but an output buffer to receive a subsequently stored data transmission is idle, the input will request a data path to the idle output buffer and forward the later stored transmission when the routing system grants the request. Thus even though its longest-stored data transmission is destined to a busy output buffer, an input buffer is not prevented from forwarding subsequently received data transmissions to idle output buffers.
Accordingly, it is an object of the present invention to provide a network switch that allows an input buffer to forward data transmissions to idle output buffers even though the destination output buffer of its longest-stored data transmission is busy.
The concluding portion of this specification particularly points out and distinctly claims the subject matter of the present invention. However those skilled in the art will best understand both the organization and method of operation of the invention, together with further advantages and objects thereof, by reading the remaining portions of the specification in view of the accompanying drawing(s) wherein like reference characters refer to like elements.
REFERENCES:
patent: 5689644 (1997-11-01), Chou et al.
Bedell Daniel J.
Chin Wellington
I-Cube, Inc.
Smith-Hill and Bedell
Yao Kwang B.
LandOfFree
Network routing switch with non-blocking arbitration system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network routing switch with non-blocking arbitration system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network routing switch with non-blocking arbitration system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2490585