Network routing switch with non-blocking arbitration system

• US 6,212,194 B1
• Filed: 08/05/1998
• Issued: 04/03/2001
• Est. Priority Date: 08/05/1998
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: I-Cube, Inc. (ON Semiconductor Corporation)
• Inventors: Hsieh, Wen-Jai
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): YAO, KWANG BIN
• Application Number:
  US09/129,982
• Time in Patent Office: 972 Days
• Field of Search: 370/398, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/422, 370/423, 370/424, 370/428, 370/429, 370/438, 370/439, 370/450, 370/451, 370/459 , 370/461, 370/462, 370/447, 370/454
• US Class Current: 370/414
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes

Abstract

A local area network routing switch for routing data transmissions between buses includes a set of input buffers, each for receiving and storing successive data transmissions arriving via a corresponding one of the bus. The switch also includes a set of output buffers for forwarding data transmissions outward via a corresponding bus, and a routing system for selectively routing data transmissions from the input buffers to the output buffers in response to routing requests from the input buffers. The routing system sends STATUS data to each input buffer indicating which output buffers are busy receiving data transmissions and which output buffers are idle. An input buffer makes a routing request only when it stores a data transmission to be forwarded to an idle output port. If its longest-stored data transmission is destined for a busy output port, it may send a routing request for a more recently stored data transmission if that data transmission is to be forwarded to an idle output buffer. Thus a busy output buffer will not block data transmission by an input buffer even though its longest-stored data transmission is to be routed to that output buffer.

Claims

1. A routing switch for routing data transmissions between a plurality of buses, the routing switch comprising:

a plurality of input buffers;

a plurality of output buffers; and

routing means for granting a routing request made by any one of said input buffers by providing a data path for conveying a data transmission between the input buffer making the routing request and an output buffer identified by the routing request, and for sending STATUS data to each input buffer wherein said STATUS data concurrently indicates a status of every one of said output buffers,

wherein the status of an output buffer is idle if it is not currently linked to one of said input buffers by a data path provided by said routing means and the status of an output buffer is busy if it is currently linked to one of said input buffers by a data Path provided by said routing means,

wherein each input buffer corresponds to a separate one of said buses, receives and stores data transmissions arriving at said routing switch via its corresponding bus, sends a routing request to the routing means the routing request identifying an idle output buffer indicated by said STATUS data as being idle whenever the input buffer is not currently forwarding a data transmission to an output buffer and is currently storing a data transmission to be forwarded by the idle output buffer, and forwards the stored data transmission to the idle output buffer via a data path provided by said routing means when said routing means grants the routing request, and

wherein each output buffer corresponds to a separate one of said buses and forwards each data transmission received from any one of said input buffers outward from said routing switch via its corresponding bus.

2. The routing switch in accordance with claim 1 wherein upon granting a routing request from an input buffer said routing means sends a GRANTED response to that input buffer, and

wherein upon receiving the GRANTED response, the input buffer forwards a stored data transmission to an output port via a data path provided by said routing means.

3. The routing switch in accordance with claim 2 wherein upon granting a routing request from an input buffer, said routing means also sends a DENIED response to others of said input buffers, and

wherein when any of said input buffers receives a DENIED response when it is not busy forwarding a data transmission to an output buffer, the receiving input buffer sends a routing request to the routing system if it is currently storing a data transmission to be forwarded by an output buffer said STATUS data indicates is idle.

4. The routing switch in accordance with claim 3 wherein said routing means comprises:

switching means connected to said input and output buffers for providing routing paths therebetween in accordance with control data provided as input thereto; and

an arbitration system connected to said input buffers for receiving routing requests from each of said input buffers and providing said control data input to said switching means in response to said routing requests.

5. The routing switch in accordance with claim 1

wherein each of said output buffers includes memory for storing each data transmission it receives from an input buffer in an internal buffer memory until the output buffer can forward the data transmission via the corresponding bus,

wherein each of said output buffer asserts a STALL signal input to said routing means when the output buffer'"'"'s memory is full and de-asserts the STALL signal when the output buffer'"'"'s memory is no longer full,

wherein when a STALL signal from an output buffer is asserted, said routing means sends a “

FULL”

code to an input buffer forwarding a data transmission to said output buffer, and when the output buffer thereafter de-asserts the STALL signal, said routing means sends a “

READY”

code to said input buffer.

wherein upon receiving the FULL code, said input buffer suspends forwarding the data transmission to said output buffer, and

wherein upon receiving the READY code, said input buffer resumes forwarding the data transmission to said output buffer.

6. The routing switch in accordance with claim 5 wherein the routing request identifies the output buffer that is to receive a longest-stored data transmission to be received by an output buffer said STATUS data indicates is idle.

7. The routing switch in accordance with claim 5 wherein at least one of said input buffers comprises:

memory means for storing a plurality of data transmissions arriving at said routing switch via one of said buses,

means for determining an output buffer that is to receive each data transmission stored in said memory means, and

means for determining from said STATUS data whether any output buffer to which any of the data transmissions stored in said memory means is to be forwarded is idle, and for sending a routing request to said routing means when any one of the data transmissions stored in said memory means is to be forwarded by an idle output buffer, wherein said routing request identifies said idle output buffer.

8. The routing switch in accordance with claim 1 wherein at least one of said input buffers comprises:

memory means for storing a plurality of data transmissions arriving at said routing switch via one of said buses,

means for determining an output buffer that is to receive each data transmission stored in said memory means, and

means for determining from said STATUS data whether any output buffer to which any of the data transmissions stored in said memory means is to be forwarded is idle, and for sending a routing request to said routing means when any one of the data transmissions stored in said memory means is to be forwarded by an idle output buffer, wherein said routing request identifies said idle output buffer.

9. The routing switch in accordance with claim 8 wherein the routing request identifies the output buffer that is to receive a longest-stored data transmission to be received by an output buffer said STATUS data indicates is idle.

10. The routing switch in accordance with claim 1 wherein the routing request identifies the output buffer that is to receive a longest-stored data transmission to be received by an output buffer said STATUS data indicates is idle.