Policing method guaranteeing fair throughput and device realizing such a method

• US 5,566,163 A
• Filed: 06/01/1995
• Issued: 10/15/1996
• Est. Priority Date: 06/09/1994
• Status: Expired due to Fees

• Current Assignee: Alcatel NV (Nokia Corporation)
• Original Assignee: Alcatel NV (Nokia Corporation)
• Inventors: Petit, Guido H. M.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/458,027
• Time in Patent Office: 502 Days
• Field of Search: 370/13, 370/14, 370/17, 370/54, 370/60, 370/60.1, 370/61, 370/79, 370/84, 370/85.6, 370/94.1, 370/94.2, 340/825.06, 340/825.5, 340/825.51, 340/825.52
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The policing device verifies at a predetermined location of a communication system whether a cell stream transmitted over that communication system satisfies a negotiated cell interarrival time and a negotiated cell delay variation and takes adequate actions. The verification is performed according to an algorithm including the steps of comparing for each cell of the cell stream and at the predetermined location the current arrival time of the cell with a predicted arrival time and discarding the cell if that predicted arrival time is larger than the sum of the present arrival time and an additional time interval. When simultaneously the cell is discarded and the additional time interval is smaller than the negotiated cell interarrival time, the predicted arrival time is adapted and the additional time interval is increased to a value having an upper limit equal to the negotiated cell interarrival time, whereas when the predicted arrival time is smaller than or equal to the current arrival time, the additional time interval is decreased to a value having a lower limit equal to the negotiated cell delay variation.

Claims

1. Policing method for verifying at a predetermined location of a communication system whether a cell stream transmitted over said communication system satisfies a negotiated cell interarrival time (Tc) and a negotiated cell delay variation (t), and for taking actions according to the result of said verification, said method comprising the steps of:

comparing for each cell of said cell stream and at said predetermined location a current arrival time (Time) of said cell with a predicted arrival time (PredictedAT);

discarding said cell if said predicted arrival time (PredictedAT) is larger than a sum of said current arrival time (Time) and an additional time interval (t'"'"'), characterized in that when simultaneously said cell is discarded and said additional time interval (t'"'"') is smaller than said negotiated cell interarrival time (Tc), said predicted arrival time (PredictedAT) is adapted and said additional time interval (t'"'"') is increased to a value having an upper limit equal to said negotiated cell interarrival time (Tc), and further characterized in that when said step of comparing compares a predicted arrival time (PredictedAT) that is smaller than or equal to said current arrival time (Time), said additional time interval (t'"'"') is decreased to a value having a lower limit equal to said negotiated cell delay variation (t).

2. Policing method according to claim 1, characterized in that said method additionally includes the step of adapting said predicted arrival time (PredictedAT) when said predicted arrival time is smaller than or equal to said sum.

3. Policing method according to claim 2, characterized in that said predicted arrival time (PredictedAT) is adapted by making said predicted arrival time equal to the sum of said negotiated cell interarrival time (Tc) and either said current arrival time (Time) or said predicted arrival time (PredictedAT) depending on said predicted arrival time being smaller than or equal to said current arrival time (Time) or not respectively.

4. Policing method according to claim 1, characterized in that said additional time interval (t'"'"') is increase by making said additional time interval equal to said negotiated cell interarrival time (Tc).

5. Policing method according to claim 1, characterized in that said additional time interval (t'"'"') is decreased by making said additional time interval equal to said negotiated cell delay variation (t).

6. Policing method according to claim 1, characterized in that said predetermined location is an entry point of said communication system.

7. Policing device (PD) including processing means (PP1, PP2) able to apply respective ones of a plurality of police algorithm instances to respective ones of a plurality of cell streams and each of said instances having a conformance check part (C) able to derive a conformance signal (CS1, CS2) indicating whether or not a cell of said cell stream handled by said conformance check part (C) is satisfactory or not and an update part (U) able to update a value of a parameter used by said instance, said processing means (PP1, PP2) being able to produce for each said cell a plurality of said conformance signals (CS1, CS2) in parallel and to supply them to an arbitration module (AM) which is also included in said device (PD) and which derives from said conformance signals a discard signal (DS) indicating whether or not said cell is to be discarded as well as a plurality of feedback signals (FS1, FS2) indicating whether or not the value of said parameter needs to be updated in respective ones of said instances, characterized in that at least one of said first and second conformance check parts compares for each cell of said cell stream a current arrival time (Time) of said cell with a predicted arrival time (PredictedAT) to indicate by way of said first and second conformance signals, respectively, to discard said cell when said predicted arrival time is larger than a sum of said current arrival time and an additional time interval (t'"'"'), and wherein at least one of said first and second update parts respectively adapts said predicted arrival time and increases said additional time interval to a value having an upper limit equal to a negotiated cell arrival time (Tc) when simultaneously said cell is discarded and said additional time interval is smaller than said negotiated cell arrival time, whereas, when said predicted arrival time is smaller than or equal to said current arrival time, said additional time interval is decreased to a value having a lower limit equal to a negotiated cell delay variation (t).

8. Policing device, comprising:

a cell receiver circuit, responsive to an aggregate input cell stream having cells of different priorities, for providing said aggregate input cell stream and for providing a control signal;

a discard circuit, responsive to said aggregate input cell stream from said cell receiver circuit and to a discard signal, for providing a policed output cell stream with selected cells discarded; and

control circuitry, responsive to said control signal, for providing said discard signal, wherein said control circuitry comprises;

an enabling circuit, responsive to said control signal, for providing a first enabling signal and a second enabling signal;

a first police processor, responsive to said first enabling signal and to a first feedback signal, for providing a first conformance signal;

a second police processor, responsive to said second enabling signal and to a second feedback signal, for providing a second conformance signal; and

an arbitration module, responsive to said first and second conformance signal, for providing said first and second feedback signals and said discard signals;

wherein

said first and second police processors are for executing instances of a policing algorithm, and include first and second conformance check parts for respectively providing said first and second conformance signals indicating a satisfactory or unsatisfactory cell of said input cell stream and include first and second update parts respectively responsive to said first and second feedback signals for updating a parameter used in said instances, and wherein at least one of said first and second conformance check parts compares for each cell of said cell stream a current arrival time (Time) of said cell with a predicted arrival time (PredictedAT) to indicate by way of said first and second conformance signals, respectively, to discard said cell when said predicted arrival time is larger than a sum of said current arrival time and an additional time interval (t'"'"'), and wherein at least one of said first and second update parts respectively adapts said predicted arrival time and increases said additional time interval to a value having an upper limit equal to a negotiated cell arrival time (Tc) when simultaneously said cell is discarded and said additional time interval is smaller than said negotiated cell interarrival time, whereas, when said predicted arrival time is smaller than or equal to said current arrival time, said additional time interval is decreased to a value having a lower limit equal to a negotiated cell delay variation (t).