Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-02-25
2003-01-21
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S415000, C370S429000
Reexamination Certificate
active
06510138
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to a network switch for storing data transmissions from network station source in input buffer queues and then routing them to their network destination stations when a routing path is available, and in particular to a network switch that automatically clears a data transmission from the head of a buffer queue when the queue is full.
2. Description of Related Art
In a computer network, such as an Ethernet network, the various network stations may be linked to one another through a network switch, or through a matrix of interlinked network switches. Each network switch has several input and output ports for receiving and forwarding data transmission and each input port may be linked to a network station or to a port of another network switch. A typical network switch also includes a crosspoint switch or other routing device which selectively routes packets between the network switch's input and output ports. Each network station has a unique network address, and when a network station sends a data transmission to another network station it includes a header in the transmission containing the network address of the network station to receive the transmission. When an input port of a network switch receives an incoming transmission, it stores the transmission in an input buffer queue, reads the destination address from the header and determines where the packet is to be sent. The input port then sends a connection request to a switch arbiter requesting a connection through the crosspoint switch to the particular output port that can forward the packet to the addressed destination station. The arbiter grants the request by establishing a connection through the crosspoint switch and then signaling the input port to forward the data transmission to the output port. The output port stores the packet in an output buffer and then forwards the packet to the destination station.
An input port's buffer can receive data faster than it can forward it, at least until the buffer fills up. For example the packet at the head of an input port's buffer queue may be destined for a switch output port that is busy receiving transmissions from other ports. Thus the input port, which forwards transmissions from its queue in the order received is blocked from forwarding any transmissions until the busy output port is ready to receive the packet at the head of the input port's queue. In the meantime the input port has continue storing all incoming packets in its buffer queue. Eventually, if the output port is blocked for a long enough period of time, the input buffer queue will fill up and will have to discard incoming packets.
Conventional network flow control systems help to prevent loss of packet data by slowing the flow of data into the buffer. When a buffer in a network path is nearly full, the buffer may send flow control data back to network devices that send it data packets telling them to either halt or slow further packet transmissions. One difficulty with such a flow control system is that its takes time for the flow control data to reach the transmitting network stations and for the transmitting stations to reduce the flow of data packets into the overloaded buffer. Until the transmitting stations receive and process the flow control data, those network stations continue to transmit data at a rate which can overflow the receiving port's buffer. Also, when the rate at which data is sent to the buffer is too low, it takes time for the buffer to send flow control data to the transmitting stations telling them that they may speed up data transmissions. In the interim, system bandwidth can be under utilized.
SUMMARY OF THE INVENTION
The present invention relates to a network switch having a set of input ports for receiving data transmissions from network stations, a set of output ports forwarding data transmissions to network stations, a crosspoint switch for routing data transmissions from each input port to a selected output port, and a routing arbitrator for controlling the crosspoint switch. When an input port receives a data transmission it stores it in an input buffer queue that can store several data transmission in the order they are received. When the transmission reaches the head of the queue, the input port sends a request to the routing arbitrator requesting a connection through the crosspoint switch to a destination output port that is to forward the transmission to a network station. The routing arbitrator thereafter grants the connection request by commanding the crosspoint switch to establish a data path from the requesting input port to the requested output port and then signaling the input port to forward the data transmission from the head of its input buffer queue to the destination output port. When an output port is busy receiving data transmission from other ports, the input port's buffer queue can fill up with incoming data transmissions waiting to be forwarded.
In accordance with the invention, when an input port's buffer queue is nearly full, the buffer queue discards the data transmission at the head of the queue in order to make room for new incoming packets to be stored in the queue. Thus the longest-stored data packet, rather than incoming data packets, is discarded when an input buffer fills up.
This “head of line” buffer clearing approach has advantages over prior art systems that allow incoming data transmission to be lost when an input buffer queue fills up. First, a network station that does not receive an acknowledgment that a data packet has been received will typically retransmit the packet to the intended destination.
Thus the longest stored data transmission in an input queue is the transmission most likely to have a replacement data transmission already on route to the destination station.
Secondly by discarding the packet at the head of the input buffer queue we solve the flow control problem at its source and allow the buffer queue to resume forwarding packets to other switch output ports that are not blocked.
On the other hand, no matter how many packets arriving at the front of the queue are discarded, discarding such incoming packets in accordance with prior art flow control systems does nothing to solve the blockage problem at the front of the queue.
It is accordingly an object of the invention to provide an effective means for un-blocking data transmissions from a buffer queue of an input port of a network switch.
It is another object of the invent to prevent loss of the most recent packets to arrive at an input buffer queue of a network switch port when the queue is full such that all packets that can go out to uncongested ports can do so.
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: 5475680 (1995-12-01), Turner
patent: 5689644 (1997-11-01), Chou et al.
patent: 5784003 (1998-07-01), Dahlgren
patent: 5838684 (1998-11-01), Wicki et al.
patent: 6208644 (2001-03-01), Pannell et al.
patent: 6212194 (2001-04-01), Hsieh
patent: 6230229 (2001-05-01), Van Krevelen et al.
Bedell Daniel J.
Fairchild Semiconductor Corporation
Hsu Alpus H.
Smith-Hill and Bedell
LandOfFree
Network switch with head of line input buffer queue clearing 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 switch with head of line input buffer queue clearing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network switch with head of line input buffer queue clearing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065050