Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-05-21
2003-05-13
Hsu, Alpus H. (Department: 2738)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000
Reexamination Certificate
active
06563790
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer network interfacing and switching and, more particularly, to an apparatus and method controlling a network switch port operating in a half-duplex mode.
2. Background Art
Local area networks use a network cable or other media to link stations on a network. Each local area network architecture uses a media access control (MAC) enabling network interfaces at each station to share access to a medium.
The Ethernet protocol (IEEE/ANSI Std. 802.3) defines a half-duplex media access format that permits all stations to access the network media channel with equality. Traffic is not distinguished or prioritized over the media. Each station includes an Ethernet interface that uses carrier-sense multiple-access with collision detection (CSMA/CD) to listen for traffic on the media. Any station can attempt to contend for the channel by waiting a predetermined transmission delay interval after the deassertion of the carrier on the media, known as the interpacket gap (IPG) interval. If a plurality of stations have data to send on the network, each of the stations will attempt to transmit in response to the sensed deassertion of the carrier on the media and after the IPG interval, resulting in a collision. Hence, a transmitting station will monitor the media to determine if there has been a collision due to another station sending data at the same time. If a collision is detected, both stations stop, wait a respective random amount of time, and retry transmission.
Ethernet networks mediate collisions by using a truncated binary exponential backoff (TBEB) algorithm, that provides a controlled pseudo-random mechanism to enforce a collision backoff interval before retransmission is attempted. According to the truncated binary exponential backoff algorithm, a station counts the number of transmission attempts (k) during the transmission of a current frame using a counter, referred to as a “retry counter”. The station computes a collision backoff interval as a randomized integer multiple of a slot time interval, and attempts retransmission after the collision backoff interval. The station will attempt to transmit under the truncated binary exponential algorithm until a maximum retry limit (k
max
) has been reached. Under the Ethernet standard (IEEE/ANSI Std. 802.3), the maximum limit for retrying transmission of a data frame is sixteen (16) times. If the station unsuccessfully attempts transmission sixteen times, the data frame is discarded by the station.
The collision backoff interval is calculated by selecting a random number of time slots from the range of zero to 2
k
. For example, if the number of attempts is k=3, then the range of randomly selected integer multiples is (0,8); if the randomly-selected integer multiple is four, then the collision backoff interval will be equal to four slot time intervals. According to Ethernet protocol, the maximum range of randomly selected time slots is from zero to 2
10
.
The truncated binary exponential algorithm has the disadvantage that the range of randomly selected integer multiples (0, 2
k
) increases exponentially each time a specific station unsuccessfully attempts a retry transmission after collision (i.e., the count k is increased), resulting in a higher probability that during the next collision mediation the station will randomly select a larger integer multiple of time slots, thereby decreasing the probability that the station will gain access to the media on the next retry transmission. Thus, a new station that has data to transmit has a higher probability of winning a collision mediation than the station having a greater number of attempts. This effect is known as the “capture” effect, where a new station in the collision mediation effectively has a greater probability of capturing access to the media than the station attempting transmission prior to the new station.
Hence, collision mediation may reduce the network throughput and create unbounded packet access latencies. Consequently, the capture effect causes a large variance in the network access latency, and a corresponding large variance in end to end delays experienced by data packets.
Additionally, network stations generally do not have knowledge of the status of other stations on the network. If there is no collision, a transmitting station will transmit the data packet regardless of the state of the receiving station. If the receiving station is in a state of congestion, for example due to a lack of buffer space, the receiving station will discard the transmitted packet, resulting in a loss of data. If upper layer protocol requires the data to be resent, the sending station will resend the data packet at a later time, reducing the network throughput and efficiency.
Network congestion occurs if a receiving network element 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. Although the full duplex environment enables the server to transmit packets while receiving requests from other clients, 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 buffer, some of the data packets will be lost. Alternatively, a client having limited buffer space may be unable to keep up with the transmission rate of the server, resulting in lost packets.
Flow control has been proposed to reduce network congestion, where a receiving station causes a sending station to temporarily suspend transmission of data packets. A proposed flow control arrangement for a half duplex environment, referred to as “backpressure”, directs a receiving station to force a collision with the transmitting station by transmitting a jamming sequence of bits when the receive buffer of the receiving station reaches a “receive buffer unavailable” state.
FIG. 7
illustrates the use of backpressure by a port
202
within a network switch
200
operating in half-duplex mode according to the CSMA/CD protocol. Port
202
receives and transmits data packets in communication with a network station
204
via a network media
206
. If the port
202
is unsuccessful in transferring a data packet from its transmit buffer to the network station
204
over the media
206
due to collisions, the port
202
will backoff and wait a randomly selected period of time before retransmitting according to the CSMA/CD protocol. After each transmission attempt, the retry counter within the port is incremented. As discussed previously, as the number of retrys attempted by the transmitting port increases, the likelihood of that port gaining access to the media decreases.
Additionally, during the backoff interval, the receive buffers in port
202
may become active and start to receive a data packet
216
transmitted from network station
204
. Should the receive buffers in the port
202
become overloaded due to congestion of the network switch bus
208
or other network ports
212
, for example, the network switch engine
210
detects that the receive buffers of port
202
have become overloaded and directs the port to assert a backpressure jamming sequence
218
, causing network station
204
to backoff and wait a randomly selected period of time before attempting retransmission.
Under the CSMA/CD protocol, the collision forced by the jamming sequence causes the transmitting network station
204
to abort, jam and retransmit a data packet after the collision backoff interval. Thus, the asserted “backpressure” controls the input port congestion of station
202
by forcing the sending network station
204
to invoke the truncated binary exponential backoff (TBEB) algorithm under the CSMA/CD protocol. Consequently, the TBEB algorithm causes the sending station
204
to stop transmission and wait to retransm
Chow Peter
Erimli Bahadir
Fischer Jenny Liu
Yu Ching
Advanced Micro Devices , Inc.
Hsu Alpus H.
Tran Thien
LandOfFree
Apparatus and method for modifying a limit of a retry... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for modifying a limit of a retry..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for modifying a limit of a retry... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3086211