Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-09-13
2004-01-06
Ton, Dang (Department: 2666)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S238000
Reexamination Certificate
active
06674716
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
A method and an apparatus for deciding on the compliance of cells at an input port of a switch is used to determine whether cells arriving at a switching device have to be considered compliant or non-compliant which result is useable as a basis for the decision whether that cell shall be discarded or may be accepted.
2. Prior Art
In the field of transportation of information via fixed-length cells, switches are used which connect a plurality of incoming connection lines to a plurality of output connection lines in that they forward cells arriving on the incoming connection lines to the output connection line to which said cells are heading. Since such switches are limited in their capacity to handle cells without cell loss, each incoming line is assigned a maximum cell deliverance rate, also called allocated bandwidth. As long as all senders stay within the limit defined by the respective allocated bandwidth, the switch is designed to handle the cells without risk of loss of information. For correct function, a mechanism is used to determine for each connection the currently used bandwidth. If a sender exceeds its bandwidth limit, e.g. a control signal may be sent upstream to the sender to make him throttle his output cell speed. The correct determination of the currently used bandwidth is hence important for guaranteeing quality of service for all connections. Known mechanisms use a time counter which is used as basis for the determination of the arrival time of incoming cells. A theoretical arrival time is calculated for a next cell expected to arrive on the same connection line as a preceding cell. A generic cell rate algorithm, short GCRA, is then performed which compares the arrival time of this next cell with its theoretical arrival time, also called TAT. The GCRA generally performs two actions: Upon arrival of a cell it decides whether an arriving cell is considered compliant or non-compliant and it afterwards calculates the new theoretical arrival time TAT. The known principles of GCRAs are described in the ITU Recommendation I.3711 of the ITU Telecommunication Standardization Sector, March 1995. The GCRA is also known as the leaky-bucket algorithm which exists in various modifications. An overview over the leaky-bucket principle can be found on the Internet the address http://www-kr.cisco.com/univercd/data/doc/lightstr/r2
—
2/sys_over/traffic.htm.
In U.S. Pat. No. 5,418,777 a modified leaky-bucket method is disclosed for a message transmission system wherein a message cell stream is asynchronously transmitted and is carrying message cells for a plurality of virtual connections. The message cell rate for every virtual connection is being monitored, the shortest allowable timing between two message cells belonging to the same virtual connection being represented by the quotient of two numbers.
U.S. Pat. No. 5,224,092 describes a method for controlling a flow of data cells into a plurality of asynchronously time-divided transmission channels with a single admission switch for transmission in the channels with reference to the state of a plurality of count values. Therein the incrementation or decrementation of a number of variables is used, which variables are processed to produce a number of assessment signals which are then converted by further processing into a control signal that is used to accept or not accept data cells. Another thereto pertinent patent is U.S. Pat. No. 5,224,091 which is related to a method for monitoring a transmission system which comprises a plurality of virtual asynchronously time-shared transmission channels via which a data flow can be transmitted.
U.S. Pat. No. 5,509,001 describes an apparatus for controlling cells which are to be input to an ATM switch. The apparatus includes a periodic calculation circuit for periodically changing the number of cells for each of different calls and a control part for determining whether the cell stored in a buffer circuit should be output to the ATM switch or discarded.
An accounting system and method for an asynchronous transfer mode network is described in U.S. Pat. No. 5,623405.
A problem arises due to the fact that the counting range of such counters is in real hardware always limited. When reaching the highest possible reading, the counter therefore wraps to its lowest reading and starts counting again. Therefore, counter readings after a counter wrap are lower than some counter readings before. This leads to cell mishandling and mistreatment of senders. More precisely, the time counter wrap can lead to situations where cells are considered compliant although they are non-compliant and also to cells being considered non-compliant although they should be considered as compliant. With other words, if the time counter has a wrap either while waiting for a cell or before the next TAT, the GCRA result may be wrong.
It is an object of the invention to provide an apparatus and also to provide a method which avoids the above disadvantage in that it is designed to determine correctly the actually used bandwidth on connection lines on which cells are arriving. This is achieved in that the wraps of the time-counting means are monitored to determine whether a wrap occurred, the result of that determination being useful for deciding whether the theoretical arrival time has a valid value to be compared with the arrival time of an arriving cell.
In the dependent claims additional improvements and variations of the apparatus and of the method are contained therein.
A second comparison means for comparing the reading of the wrap-counting means at the first arrival time with the reading of the wrap-counting means at the second arrival time is a practical and simple solution for finding out the difference in the number of windows in which the first and the second cell arrived. This difference is an important variable for correctly determining the used bandwidth on that connection.
For easily finding out the number of the window in which the theoretical arrival time lies, the reading of the wrap-counting means at the theoretical arrival time can be used.
A practical solution for keeping the memory of the arrival times is to store the reading of the time-counting means at the second arrival time and at the first arrival time. When the storing places are arranged in form of a shift register, upon arrival of a new cell, the storage of the new arrival time will automatically effect the conversion of the arrival time of the previous cell which up to then has been the second arrival time, to the then valid first arrival time. This automatism is very simple and therefore needs not much dedicated logic.
State-determination means can be used to initiate on a timely regular basis with a predetermined repetition period a process which effects an artificial second arrival time for which the reading of the wrap-counting means is determined. This reading together with the reading of the wrap-counting means at the theoretical arrival time is usable for the determination whether a wrap occurred between the theoretical arrival time and the artificial second arrival time. This is a background process which even leads to correct cell-handling when the wrap-counting means has a wrap itself. The result of the background process can be used for setting a validity flag which indicates if the theoretical arrival time is valid for the next arriving cell or not.
For obtaining the maximum precision of the cell rate determination process, the repetition period should be chosen at maximum the time between two wraps of the time-counting means multiplied with the maximum reading of the wrap-counting means minus 2. Then it is guaranteed that, if the background process has been applied for one connection in the window where the previous cell arrived or in the window after that window, for the same connection the background process at latest is performed again before the wrap-counting means has reached one of the numbers of these windows again. Hence, every cell arrival constellation is treated fair.
If th
International Business Machines - Corporation
Scully Scott Murphy & Presser
Ton Dang
Tran Phuc
Zarick, Esq. Gail H.
LandOfFree
Cell compliance decision method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cell compliance decision method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cell compliance decision method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3191803