Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-01-21
2004-02-24
Olms, Douglas (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395400, C370S414000, C370S418000
Reexamination Certificate
active
06697328
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to a method for optimizing the use of connected sections in a system for transmitting data pockets.
In modern packet switching systems, information is transmitted in data packets. One example of this is ATM cells. These have a header part and an information part. The header part is used to store connection information, and the information part to store the wanted data to be transmitted. As a rule, the actual transmission takes place via connecting sections between the transmitter and receiver. In this case, there may be a requirement to utilize the connecting sections in such a manner that a plurality of transmitting devices transmit the cell streams originating from these devices via the same connecting section.
In order to allow the transmission of the respective cell streams to be carried out in accordance with the requirements of the individual cell streams, a so-called WEIGHTED FAIR QUEUING SCHEDULING method has become generally accepted in the prior art. The corresponding relationships are described, for example, in the document “Virtual Spacing for Flexible Traffic Control”, J. W. Roberts, International Journal of Communication Systems, Vol. 7, 307-318 (1994). In this case, the individual cell streams are assigned different weighting factors, which are used to control the actual transmission process on the individual connecting sections. Reference should be made to
FIG. 3
to assist understanding.
By way of example, this shows cell streams
1
. . . n. The n cell streams are passed from a transmitting device DEMUX in the direction of one or more receivers. In practice, only one common connecting section is used in this case. The n cell streams are furthermore assigned weighting factors r
1
. . . r
n
. To assist understanding, it is assumed that it is intended to pass only two cell streams, namely the cell streams
1
,
2
, via a connecting section. The connecting section is furthermore intended to have a maximum transmission capacity of 150 Mbit/s. The two cell streams
1
and
2
are assigned weightings r
1
=2 and r
2
=1. This results in the cell stream
1
being transmitted at a transmission rate of 100 Mbit/s, and the cell stream
2
at only 50 Mbit/s, if cells for both cell streams are present for transmission. If only one of the two cell streams has cells to transmit, this cell stream is assigned the total transmission capacity of 150 Mbit/s.
FIG. 2
shows how the theoretical considerations addressed above are implemented in practice in the prior art. This shows how data packets, or ATM cells, are dealt with using the weighted fair queuing scheduling algorithm. In this case, incoming cells are supplied to the input device EE, are passed on to the demultiplexing device DEMUX and are stored there with the aid of a demultiplexing function, which is implemented here, and with the assistance of a queue identifier QID in a logic queue. The queue identifier QID is in this case contained in the cell header of each cell.
At the same time, control data which are determined in the input device EE are for this purpose supplied to a scheduler device S. A scheduling algorithm which is known per se is executed in this device. This may be, for example, the weighted fair queuing scheduling algorithm or any other algorithm. This algorithm determines, for example, the sequence in which or the time at which it is intended to read the cells which are stored in the buffer stores P
1
. . . Pn (initial planning). The result of the assessment of the control data by this algorithm is supplied to the output device AE. The cells stored in the buffer stores P
1
. . . Pn are now read, on the basis of the result of the assessment, by the algorithm which is being executed in the scheduling device S. Furthermore, an acknowledgment signal is fed; back to the input device EE. After this and when a new cell with a queue identifier QID arrives in the input device EE and when an acknowledgment ‘selected QID’ is present, the input device EE uses the buffer filling level for QID=I as well as the scheduling method to decide whether the message “SCHEDULE QID” is generated. This message indicates to the scheduler device S that it should carry out initial planning for the next transmission time for this queue identifier QID, in some way.
A problematic feature of such a procedure is that, although the weighted fair queuing scheduling algorithm guarantees minimum cell rates, a maximum cell rate limiting cannot be carried out here. However, this is a major factor since, in practice, both minimum and maximum cell rates often have to be complied with—for example in the case of ABR (available bit rate) traffic.
European Patent Application EP 0 705 007 A2 describes a method for guaranteeing maximum and minimum cell rates. In this case, the scheduling of the cells is carried out on a cell basis, one scheduler being used first to ensure the minimum cell rate, and a scheduler then being used to limit the peak cell rate.
SUMMARY OF THE INVENTION
The invention is based on the object of providing a weighted fair queuing scheduling algorithm that is modifiable such that optimized transmission is ensured.
In general terms the present invention is a method for optimization of the utilization of connecting sections in systems in which information is transmitted in data packets. A scheduling method runs on a scheduler device by which connection parameters, which are representative of lower transmission rates of the data packets, are guaranteed during the transmission process. A queue identifier is stored in the packet header. Based on the queue identifier, the scheduling method running on the scheduler device may possibly be preceded by a further scheduling method running on a further scheduler device, by which the connection parameters which are representative of upper transmission rates of data packets are limited during the transmission process. There may be more than one scheduler device while there is only one further scheduler device.
An advantageous feature of the invention is that, based on a queue identifier contained in the packet header, the scheduling method running on a scheduler device may possibly be preceded by a further scheduling method running on a further scheduler device, by means of which the connection parameters which are representative of upper transmission rates of data packets are limited during the transmission process, in which case there may be more than one scheduler device, while there is only one further scheduler device. In this case, the result from the first stage is used as the input signal for the second stage. This results in both an upper and a lower cell-rate limit being controllable, that is to say the cells are not transmitted at higher cell rates during the transmission process. In particular, this method is not limited to the use of a specific algorithm. Furthermore, it should be also be mentioned that two scheduler devices are provided, there being only one of the first of these scheduler devices, while there may advantageously be more than one of the remaining one of the scheduler devices.
Advantageous developments of the present invention are as follows.
The scheduling method is a weighted fair queuing scheduling algorithm. This is linked to the advantage that a proven method can be used. A further advantage of this is that this algorithm guarantees lower limiting of the cell rate.
An input device containing a table which contains the current filling levels of the buffer stores. This is linked to the advantage that a current map of these filling levels is stored here at all times.
Depending on control data obtained from the scheduler device, the output device takes cells from at least one of the buffer stores and acknowledges this process to the input device. As a result of the feedback, the reading process has a direct influence on the first stage of the two-stage method. The two stages of the two-stage scheduling method thus do not operate independently of one another. The way in which the first stage o
Fish & Richardson
Olms Douglas
Phunkulh Bob A.
Siemens Aktiengesellschaft
LandOfFree
Process for optimizing load distribution between connection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process for optimizing load distribution between connection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for optimizing load distribution between connection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289904