Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1998-07-10
2001-10-23
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
C370S235000, C370S470000
Reexamination Certificate
active
06307835
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of data communications and, more particularly, to the field of network data communications.
BACKGROUND OF THE INVENTION
In general network traffic on a data communications network has been described as bursty or fractal in nature. The volume of traffic if examined over time shows the self-similar characteristic of peaks and valleys at consistently diminishing time intervals (see, e.g.,
FIG. 1
where BW
MAX
is the maximum bandwidth). In other words, the network sustains periods of high traffic and low traffic. Additionally, even smaller intervals of time than those illustrated in
FIG. 1
can also be generally described as fractal or bursty as well. Modeling or designing hardware to handle the bandwidth requirements of this sort of bursty traffic has been fraught with difficulties. In general attempts to control the rate of frame transmission have had a depressing effect upon the overall channel bandwidth. An entire taxonomy of schemes exist to handle flow-control, from transmit windowing, and relatively recently, in-band communication of transmit delay timers, to creation of minimum frame sizes.
For example, a minimum frame spacing (“MFS”) scheme has a purpose or intent of delaying transmission by stuffing a fixed number of flag bytes between successive data frames or slots. A problem with implementing MFS with this type of traffic is that although it successfully dampens the transmit rate, this scheme does so indiscriminately. All frames are padded with flags whether or not they need to be padded (see, e.g.,
FIG. 2
wherein BW
MFS
is the bandwidth using the minimum frame spacing scheme and dBW
MFS
is the bandwidth difference or change between the maximum bandwidth). The net effect is to reduce the overall effectiveness of the device and waste bandwidth.
Another example can be seen in the Institute for Electrical and Electronic Engineers (“IEEE”) specification no. 802.3 which requires frames smaller than 64 bytes to be padded with sufficient bytes such that this minimum frame size is satisfied:
The number of extra bits shall be sufficient to ensure that the frame, from the destination address field through the FCS field inclusive, is at least minFrameSize bits. The content of the pad is unspecified. (IEEE 802.3, p. 21).
Additionally, the IEEE 802.3z committee recently introduced a concept called “Carrier Extension” as set forth below:
In half-duplex mode at operating speeds above 100 Mb/s . . . appending non-data symbols, referred to as extension bits, to frames which are less than minFrameSize+extendSize bits in length so that the resulting transmission is at least one slotTime in duration.
The IEEE implementations, however, are fixed on 64 bytes as a minimum frame size. The IEEE 802.3 specification requires that padding be inserted into the interior of the frame, that is, between the data and FCS fields. The IEEE 802.3z committee development is an attempt to avoid increasing the minimum Ethernet frame size by increasing the minimum slot-time for gigabit Ethernet to 4 k bit times which is again a hard constant.
SUMMARY OF THE INVENTION
In view of the foregoing background, the present invention advantageously provides a method and apparatus for more effectively controlling the data flow in data communication networks. The present invention also advantageously provides a method and apparatus which is dynamic, relatively simple, and has no absolute minimum frame size for data flow in a data communications network. The present invention additionally advantageously provides a method and apparatus which flexibly and effectively guarantee a maximum arrival rate for a downstream node in a data communications network. The present invention further provides a method and apparatus which reduces or prevents buffer overflow errors and lost frames due to sudden or even extended bursts of small frames in a data communications network.
More particularly, the present invention provides a variable frame padding (“VFP”) method and apparatus in which a host data communications terminal is free to change the minimum frame threshold at any time and thereby throttle up or down the transmit traffic. If the length of a frame is found to be under the minimum frame threshold or slot value then pad or flag bytes are inserted preferably after the frame's CRC field has been successfully transmitted. Sufficient flags are issued or inserted until the threshold or slot value has been reached. A downstream node of a data communications network advantageously receives the benefit of padding because it has the responsibility of keeping up with an upstream node of the data communications network. Because the rate of frame arrival is inversely proportional to frame size, the downstream node must work proportionately harder as the average arriving frame decreases proportionately in length.
If the transmitting node is forced to observe a minimum frame size such that all frames smaller than this value are extended in length, then a maximum arrival rate for the downstream node can be effectively guaranteed. In this way, the receiving node also can be insured against buffer overflow errors and lost frames due to sudden or even extended bursts of small frames. Because any frames exceeding this minimum frame threshold value are ignored, bandwidth utilization is only marginally affected. The method of the present invention is advantageously quite simple yet its effect can be powerful.
More particularly, a method of controlling data flow of data communications in a network is provided which preferably includes dynamically varying a minimum frame slot number and transmitting at least bytes of data from a frame of data of a slot. The method can also include determining the end of the frame of data, determining that the number of bytes of data within the frame is less than the current minimum frame slot number, and transmitting flag bytes within the slot until the combination of the number of bytes and flag bytes equals the current minimum frame slot number.
Another aspect of a method of controlling data flow of data communications in a network, more specifically, preferably includes: (a) transmitting at least one byte of data from a frame of data within a frame slot;(b) incrementing a byte counter from a current setting; (c) if an end of the frame of data does not occur, then repeat steps (a) and (b) for the frame; and (d) if an end of the frame of data occurs, then determining whether a number currently represented and stored in the byte counter is less than a predetermined minimum frame slot number. The method can also preferably include the steps of (e) if the number currently represented and stored in the byte counter is less than the predetermined minimum frame slot number, then transmitting a flag byte and incrementing a flag byte counter from a current setting;(f) if the number currently represented and stored in the byte counter is equal or greater than the minimum frame slot number, then resetting the byte and flag counters and repeating steps (a) through (e); (g) if the sum of the numbers currently represented and stored in the byte and flag counters does not equal the predetermined minimum frame slot number, then repeat steps (e) and (f); and (h) if the sum of the numbers currently represented and stored in the byte and flag counters equals the predetermined minimum frame slot number, then resetting the byte and flag counters to an initial setting and repeat steps (a) and (b) for another frame of data.
An apparatus for network data communications is also provided according to the present invention. The apparatus preferably includes transmitting means for transmitting at least bytes of frames of data of a data slot and counting means responsive to the transmitting means for counting the number of bytes and the number of flag bytes in a frame of a slot of transmitted data. The apparatus also preferably includes comparing means responsive to the counting means for comparing the number of bytes transmitted in each frame of data with a predeterm
Ho Duc
Hsu Alpus H.
Jorgenson Lisa K.
Regan Christopher F.
STMicroelectronics Inc.
LandOfFree
Method and apparatus for controlling data flow in data... 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 for controlling data flow in data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for controlling data flow in data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579051