Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-10-27
2002-04-23
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S229000, C370S230000, C370S231000, C370S235000, C370S236000, C370S395430, C370S464000, C370S466000, C370S468000, C370S471000, C370S232000, C370S389000, C370S395100
Reexamination Certificate
active
06377550
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
This invention is in the field of telecommunications, and is more specifically directed to flow control in asynchronous transfer mode (ATM) communications.
In the field of digital communications, whether applied to voice, video, or data communication, various techniques have been developed for routing messages among nodes connected in a network. One such approach is referred to as packet-based data communications, in which certain network nodes operate as concentrators to receive portions of messages, referred to as packets, from the sending units. These packets may be stored at the concentrator, and are then routed to a destination concentrator to which the receiving unit indicated by the packet address is coupled. The size of the packet refers to the maximum upper limit of information that can be communicated between concentrators (i.e., between the store and forward nodes), and is typically a portion of a message or file. Each packet includes header information relating to the source network address and destination network address, which permits proper routing of the message packet. Packet switching with short length packets ensures that routing paths are not unduly dominated by long individual messages, and thus reduces transmission delay in the store-and-forward nodes. Packet-based data communications technology has enabled communications to be carried out at high date rates, up to and exceeding hundreds of megabits per second.
A well-known example of a fast packet switching protocol, which combines the efficiency of packet switching with the predictability of circuit switching, is Asynchronous Transfer Mode (generally referred to as “ATM”), in which packet lengths and organization are fixed, regardless of message length or data type (i.e., voice, data, or video). The fixed packets according to the ATM protocol are referred to as “cells”, and each ATM cell is composed of fifty-three bytes, five of which are dedicated to the header and the remaining forty-eight of which serve as the payload. According to this protocol, larger packets are made up of a number of fixed-length ATM cells. The fixed-size cell format enables ATM cell switching to be implemented in hardware, as opposed to software, resulting in transmission speeds in the gigabits-per-second range. In addition, the switching of cells rather than packets permits scalable user access to the network, from a few Mbps to several Gbps, as appropriate to the application. The asynchronous nature of the transmission permits ATM cells to be used in transmitting delay-tolerant data traffic intermixed with time-sensitive traffic like voice and video over the same backbone facility. To more efficiently utilize the bandwidth for these various applications, traffic management techniques are now employed which give priority to time-sensitive traffic relative to delay-tolerant traffic.
Closed loop traffic management involves the use of feedback signals between two network nodes to govern the data rates of channels, with a goal of improving the efficiency of bandwidth utilization. This efficiency improvement is particularly necessary when communication of compressed voice and video information is involved, because compression tends to make the bit rate variable, in which case the feedback signals enable the network to communicate either the availability of bandwidth or the presence of congestion.
Current traffic management schemes utilize various transmission categories to assign bandwidth in ATM communications. One high priority category is Constant Bit Rate (CBR), in which the transmission is carried out at a constant rate. Two categories of Variable Bit Rate (VBR) transmission are also provided, one for real-time information and another for non-real-time information. A low priority category is Unspecified Bit Rate (UBR), in which data are transmitted by the source with no guarantee of transmission speed. In the recently-developed Available Bit Rate (ABR) service class, feedback from the network nodes, via Resource Management (RM) cells or by way of explicit congestion indications in data cells, is used by the source network node to dynamically control channel transmission rate in response to current network conditions, and within certain transmission parameters that are specified upon opening of the transmission channel (i.e., in the traffic “contract”).
For the ABR class of service, the source and destination nodes agree, in the traffic contract, upon a Peak Cell Rate (PCR) and a Minimum Cell Rate (MCR), thus setting the upper and lower bounds of transmission for an ABR communication. Once these bounds are established, a flow control algorithm is executed, typically both at the source network node and at ATM switches in the network, to define the current transmission rate of each channel. As is known in the art, thousands of connections may be simultaneously open between a given pair of network nodes. As such, traffic management can be a relatively complex operation, especially in controlling ABR category communications.
The setting of upper and lower bounds for ABR traffic is only one issue in ATM flow control. Another issue addressed by ATM flow control schemes, referred to in the art as “fairness”, is the allocation of available bandwidth among the multiple ABR channels that are to be carried by a given link, especially in the case where the available bandwidth is less than the PCR of each of the channels. A proper fairness scheme requires that ABR channels with the highest PCR (or MCR) do not dominate the available bandwidth, and also that the channels with the lowest PCR (or MCR) are not disproportionately served relative to the high data rate channels.
Several fairness criteria are known in the field of ATM flow control. One fairness criterion, referred to as the “Max-Min” scheme, is popular as it leads to the maximization of total throughput. This approach is based upon an iterative procedure of computing the cell rate allocation among ABR channels. In a first iteration (l=1) of the procedure, a set variable u
1
defines the set of links making up the network, and a set variable v
1
defines the set of ABR flows traversing the network. Variable b
j
is initialized to the bandwidth available to a link L
j
in the network, and variable n
j
is initialized to the number of ABR flows sharing link L
j
. During each iteration l, a ratio r, is determined as the smallest ratio b
j
j
for all links L
j
&egr;u
l
. A set of links W
l
={L
j
}≅u
l
is then defined as those links for which the ratio b
j
j
equals r
j
, as is a set of flows S
l
={F
i
}≅v
l
where each flow F
i
in the set S
l
travels over one of the links in W
l
. The set W
l
establishes the level l bottleneck links, and the set S
l
establishes the level l bottleneck flows. The data rate r
l
is the bottleneck rate of the links in set W
l
and is the constraint rate of the flows in set S
l
. A reduced network U
l+1
is then constructed by subtracting the bottleneck set W
l
from the set U
l
set v
l+1
is then derived, by subtracting set S
l
from v
l
, and defines the set of flows for which constraint rates remain to be determined. Considering m as the number of flows that are both in S
l
and which also travel over any link L
j
≅U
l+1
, the construction of the reduced network is completed by subtracting the value mr
l
from b
j
, and the number m from n
j
for each link L
j
&egr; U
l+1
. If the set u
l+1
is null, the bottleneck rate of each link and the constraint rate of each flow has been found.
While this approach readily defines the bottleneck and constraint rates, this procedure cannot be directly implemented into ATM network switches because global knowledge of the entire network is required; rather, a practical ATM switch algorithm must permit the links in the network to determine their bottleneck rates in a distributed fashion. A know distributed approach for a
Brady III W. James
Kizou Hassan
Logsden Joe
Moore J. Dennis
Telecky , Jr. Frederick J.
LandOfFree
Nested measurement period switch algorithm for flow control... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Nested measurement period switch algorithm for flow control..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nested measurement period switch algorithm for flow control... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2922269