Network switch with head of line input buffer queue clearing

• US 6,510,138 B1
• Filed: 02/25/1999
• Issued: 01/21/2003
• Est. Priority Date: 02/25/1999
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Fairchild Semiconductor Corporation (ON Semiconductor Corporation)
• Inventors: Pannell, Donald Robert
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US09/258,181
• Time in Patent Office: 1,426 Days
• Field of Search: 370/230, 370/231, 370/235, 370/236, 370/357, 370/360, 370/400, 370/410, 370/412, 370/415, 370/416, 370/428, 370/429, 340/2.1, 340/2.2, 340/2.28, 340/14.1, 709/232, 709/234, 709/235, 709/238
• US Class Current: 370/236
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/111 Switch interfaces, e.g. port details
• CPC Class Codes: H04L 49/112 Switch control, e.g. arbitration
• CPC Class Codes: H04L 49/1576 Crossbar or matrix
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance

Abstract

An improvement is provided to a network switch of the type including a set of input and output ports for receiving and forwarding data transmissions from and to network stations and a crosspoint switch for selectively routing data transmissions between the input and output ports. Each input port stores successive incoming data transmissions in an input buffer queue. When a data transmission reaches the head of the queue, the input port requests a route through the crosspoint switch to an output port that is to forward the transmission to a network station. When the output port is ready to receive the transmission the crosspoint switch establishes the route and the input port forwards the data transmission from its buffer queue to the output port. In the improved network switch, the input port discards the data transmission at the head of the buffer queue without forwarding it to an output port when necessary to make room in the buffer for incoming transmissions.

Claims

1. A network switch for routing data transmissions of varying size ranging up to a predetermined maximum size data transmission, between network stations, the network switch comprising:

a plurality of input ports, each input port including an input buffer comprising memory units for receiving and storing OaLa transmissions from at least one of said network stations;

a plurality of output ports, each for receiving and forwarding data transmissions to at least one of said network stations; and

routing means for providing a route for conveying a longest-stored data transmission in the input buffer of any one of said input ports to one of said output ports selected by said routing means, said routing means providing said route following receipt of a routing request from that one of said input ports requesting the route when the selected output port is ready to receive said longest-stored data transmission,

wherein each said input port removes and discards its longest-stored data transmission in its input buffer without forwarding it to one of said output ports when an amount of said input buffer memory not currently storing a received data transmission is below a threshold level sufficient to store a data transmission of the maximum size, before said routing means establishes a route to convey said longest-stored data transmission to one of said output ports, and

wherein each said input port otherwise forwards its longest-stored data transmission from its input buffer to a selected one said output ports after said routing means establishes a route thereto.

2. The network switch in accordance with claim 1 wherein said routing means comprises a crosspoint switch.

3. The network switch in accordance with claim 1 wherein each memory unit is of sufficient size to store only a fractional portion of a data transmission, and wherein each input port comprises:

counter means for maintaining a count of units its buffer memory not currently storing a portion of a data transmission, wherein said counter means increments said count said input port removes a data transmission from one of said units of buffer memory and decrements said count whenever said input port stores a data transmission in one of said units of buffer memory, the counter being incremented and decremented in proportion to a number of memory units occupied by the data transmissions removed from and stored in the buffer memory, and

means for signaling said input buffer to discard said longest-stored data transmission when said count falls below said threshold level.

4. The network switch in accordance with claim 3 wherein said routing means comprises a crosspoint switch.

5. In a network switch of the type having a plurality of input ports and a plurality of output ports, wherein each input port comprises an input butter having memory space for receiving and. storing data transmissions of variable size ranging up to a predetermined maximum size arriving at the input port and for forwarding a longest-stored data transmission from said buffer to an output port when the output port is ready to receive the data transmission, a method of operating said input buffer comprising the steps of:

continuously determining an amount of input buffer memory space not currently used for storing a data transmission; and

discarding said longest-stored data transmission from said input buffer without forwarding it to one of said output ports when an amount of unused input buffer memory space falls below a pre-determined threshold level sufficient to store a data transmission of said predetermined maximum size.

6. A network switch for routing data transmissions between network stations, the network switch comprising:

a plurality of input ports, each including a memory for receiving and storing incoming data transmissions from at least one of said network stations;

a plurality of output ports;

routing means for selectively providing a route for conveying data transmissions in the memory of any one of said input ports to any other of said output ports,

wherein whenever any data transmission stored in an input port'"'"'s memory becomes the longest-stored data transmission in that memory, that input port transmits a routing request to the routing means requesting a route for conveying that longest-stored data transmission to a selected one of the output ports,

wherein each input port removes and discards a longest-stored data transmission in its memory when its memory'"'"'s unused storage capacity fall below a predetermined threshold level before the routing means establishes a route for conveying the longest-stored data transmission to one of the output ports, each input port otherwise forwarding its longest-stored data transmission from its memory via the route established by the routing means, and

wherein said routing means stores each routing request received from each input port, discards a currently stored request from any input port when that input port subsequently transmits another routing request to the routing means before the routing means provides a route requested by the currently stored routing request, and otherwise discards a currently stored routing request from any input port only after providing the route requested thereby.

7. The network switch in accordance with claim 6 wherein said routing means comprises a crosspoint switch.