Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1997-12-18
2001-02-20
Pham, Chi H. (Department: 2731)
Multiplex communications
Data flow congestion prevention or control
C370S282000, C370S296000, C370S417000
Reexamination Certificate
active
06192028
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to network switching and more particularly, to methods and systems controlling network data traffic on half-duplex media in switched networks.
2. Background Art
Switched local area networks use a network switch for supplying data frames between network stations, where each network station is connected to the network switch by a media. The switched local area network architecture uses a media access control (MAC) layer enabling a network interface card to access the media. The network switch passes data frames received from a transmitting station to a destination station based on the header information in the received data frame.
Network congestion occurs if a receiving network element, for example a receiving network station, is unable to receive data at a rate greater than or equal to the transmission rate of the transmitting element. For example, traffic in a client-server environment is dominated by client requests followed by a burst of frames from the server to the requesting client. Hence, only a limited number of client requests can be output to the server from the switched hub at the assigned switching port. If the number of client requests exceeds the capacity of the server's port, some of the data packets will be lost. In another example, a client having limited buffer space may be unable to keep up with the transmission rate of a transmitting station, resulting in lost packets. Finally, network congestion may occur if a transmitting station attempts to transmit data packets to a receiving station that is already receiving data packets from another transmitting station. Hence, a receiving station may be unable to keep up with reception of data packets from two separate transmitting stations.
Flow control has been proposed to reduce network congestion, where a sending station temporarily suspends transmission of data packets. A proposed flow control arrangement for a half-duplex environment, referred to as “back-pressure,” causes a receiving station to force a collision with the transmitting station when the receive buffer of the receive station reaches a “receive buffer unavailable” state.
The disclosed flow control proposals, however, assume that flow control should be initiated when a receive buffer is full, which still results in a loss of data. Moreover, the existing proposals do not describe how to determine the instance in which flow control should be initiated. The problem also become more complex in a switched environment, where a network switch must route data packets received from a plurality of transmitting stations to the appropriate destination stations. Moreover, if the flow control duration is too short, a receiving station may still lose portions of the transmitted data. If the duration is too long, the transmitting station remains idle, reducing network throughput.
SUMMARY OF THE INVENTION
In view of the foregoing, there is a need for an arrangement in a network switch for selectively outputting data frames from a transmitting station to a destination station that efficiently implements flow control in a manner that avoids dropped data packets and wasted network bandwidth.
There is also a need for an arrangement that selectively generates flow control signals to a transmitting station from a switched network element based on a buffer capacity of an output port serving a destination station, as well as the overall global buffer capacity of the switched element for all network stations.
There is also a need for an arrangement in a switched network element for selectively routing data packets to a destination station, where the destination station can be identified quickly enough to assert back pressure to the transmitting station to halt transmission of the data frame currently being transmitted.
These and other needs are attained by the present invention, where a network switch selectively transmits a flow control signal to a transmitting station during reception of a data frame based upon a number of free frame pointers stored in a queue relative to an adjustable queue, where the free frame pointers specify respective memory locations available for storing received data frames, and an adjustable queue threshold relative to the queue storing the free frame pointers.
According to one aspect of the present invention, a method in a network having network stations includes the steps of setting a first queue threshold level for a first queue configured for storing free frame pointers, the free frame pointers specifying respective memory locations available for storing received data frames, receiving a portion of a first data frame from a first of the networks stations, and selectively transmitting a signal to the first network station during reception of the first data frame based on the first queue threshold level and a number of the free frame pointers stored in the first queue, the signal causing a collision with the first network station during transmission of the first data frame. The transmission of the signal to the first network station during reception of the first data frame that causes the collision ensures that network throughput is maximized, since the transmitting station is immediately halted from continued transmission of the first data frame. Moreover, the decision to transmit the signal to the first network station to cause a collision is based upon a number of free frame pointers stored in the queue, where the free frame pointers specify respective memory locations in a global buffer pool available for storing received data frames. Hence, the present invention provides a particularly advantageous arrangement of managing global buffer capacity by providing a memory architecture where memory allocation is based on free frame pointers that specify memory locations available for storing received data frames.
Another particular feature of the above-described aspect includes the steps of setting a second queue threshold level for a port queue configured to store an assigned frame pointer, the assigned frame pointer specifying a storage memory location of a stored data frame to be transmitted to a second of the network stations, and identifying the port queue as a destination port for the first data frame based on the portion of the first data frame, wherein the selectively transmitting step comprises selectively generating the signal based on the number of free frame pointers relative to the first queue threshold level and a number of the assigned frame pointers relative to the second queue threshold level. Hence, the decision to selectively transmit a signal to cause a collision can be based upon either the number of free frame pointers for global use by the network switch relative to the first queue threshold, or the number of assigned frame pointers corresponding to an identified destination port relative to the second queue threshold level.
Another aspect of the present invention provides an apparatus for selectively outputting a data frame from a transmitting station to a destination station in a network, comprising a first port for receiving at least a portion of the data frame from the transmitting station, a first queue for storing free frame pointers, the free frame pointers specifying respective memory locations available for storing received data frames, a first programmable threshold register for storing a first threshold value, a second port for outputting data frames identified for transmission to the destination station, and a controller for selectively causing the first output port to induce a collision with the transmitting station during reception of the data frame from the transmitting station, based on a number of the free frame pointers stored in the first queue relative to the first threshold value. The use of free frame pointers provides a flexible memory architecture for the storage and transmission of data frames. Moreover, selective collisions based on the number of free frame pointers stored in the queue ensures that the possibility of
Crayford Ian
Erimli Bahadir
Kadambi Jayant
Kerstein Denise
Leung Eric Tsin-ho
Advanced Micro Devices , Inc.
Pham Chi H.
Tran Maikhanh
LandOfFree
Method and apparatus providing programmable thresholds for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus providing programmable thresholds for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus providing programmable thresholds for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2573122