ABR policing method and apparatus

• US 6,175,568 B1
• Filed: 12/16/1997
• Issued: 01/16/2001
• Est. Priority Date: 12/16/1997
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Awdeh, Raʼed Yousif
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Pham, Brenda H.
• Application Number:
  US08/991,553
• Time in Patent Office: 1,127 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/229, 370/236, 370/395, 370/468
• US Class Current: 370/236.1
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/20 Traffic policing

Abstract

An apparatus and a computer readable storage medium having computer readable instructions for directing a processor to execute a method executable by the apparatus for adjusting policing cell rates at a switch interface, for cells received from a source in an allowed cell rate system. The method includes the steps of storing a current policing rate (PACR) in a current policing rate buffer, storing a plurality of policing rates and policing rate application times in respective policing rate and policing rate application time buffers and in response to the departure of a backward resource management cell to the source at time tb(j), setting the contents of the policing rate buffers and the policing rate application time buffers according to the relative magnitudes of the current policing rate and the contents of the policing rate buffers.

Claims

1. A method of adjusting policing cell rates at a switch interface, for cells received from a source in an allowed cell rate system, the method including the steps of:

a) storing a current policing rate (PACR) in a current policing rate buffer;

b) storing a plurality of policing rates and policing rate application times in respective policing rate and policing rate application time buffers;

c) in response to the departure of a backward resource management cell to the source at time tb(j), setting the contents of said policing rate buffers and said policing rate application time buffers according to the relative magnitudes of said current policing rate and the contents of said policing rate buffers.

2. A method as claimed in claim 1 further including the steps of

a) storing a current policing rate (PACR) in a current policing rate buffer;

b) storing a first policing rate (DER_first) and a first policing rate application time (t_first) in a first policing rate buffer and a first policing rate time buffer respectively;

c) storing a last policing rate (DER_last) and a last policing rate application time (t_last) in a last policing rate buffer and a last policing rate time buffer respectively.

3. A method as claimed in claim 2 further including the step of receiving a backward resource management cell and on receiving such cell, determining whether or not a current cell rate is greater than or equal to said first policing rate and if so copying said first policing rate into said current policing rate buffer, copying said last policing rate application time into said first policing rate application time buffer, copying said last policing rate into said first policing rate buffer and setting the contents of said last policing rate buffer and said last policing rate application time buffer to zero.

4. A method as claimed in claim 2 further including the step of determining whether or not said first policing rate application time is earlier than said last policing rate application time and if so copying said first policing rate into said current policing rate buffer, copying said last policing rate application time into said first policing rate application time buffer, copying said last policing rate into said first policing rate buffer and setting the contents of said last policing rate buffer and said last policing rate application time buffer to zero.

5. A method as claimed in claim 2 further including the step of receiving a cell from said source at a time ta(k) and determining whether or not the current policing rate should be updated.

6. A method as claimed in claim 5 wherein the step of determining whether or not the current policing rate should be updated includes the step of determining whether said current policing rate is equal to said first policing rate and whether said first policing rate application time is equal to said last policing rate application time and whether said first policing rate is equal to said last policing rate and whether said last policing rate application time is equal to zero and whether said last policing rate is equal to zero and if so, changing said current policing rate.

7. A method as claimed in claim 5 further including the step of determining whether or not said cell received from said source conforms to said policing rate.

8. A method as claimed in claim 7 wherein the step of determining whether or not said cell received from said source conforms to said policing rate includes the step of calculating a policing increment value.

9. A method as claimed in claim 8 wherein the step of calculating said policing increment value includes the step of determining the minimum value of the reciprocal of a current and immediately past policing increment values.

10. A method as claimed in claim 9 further including the step of determining whether or not the sum of a last virtual scheduling time (LVST) and said minimum value is less than or equal to the sum of the time ta(k) and a cell delay variation tolerance value.

11. A method as claimed in claim 2 further including the steps of:

If (ER(j)<

DER_first AND ER(j)>

=DER_last)

IF (PACR>

=DER_firstAND(PACR−

DER_first)(t_last−

t_first)<

(ER(j)−

DER_last)(tb(j)+τ

3−

t_last))

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_first=t_last;

DER_first=DER_last;

t_last=tb(j)+τ

3;

DER_last ER(j) ELSE DER_last=ER(j)

ELSE

IF (ER(j)<

DER_first AND ER(j)<

DER_last)

IF (PACR<

=DER_firstAND(PACR−

DER_first)(t_last−

t_first)<

(DER_first−

DER_last)(tb(j)+τ

2−

t_last))

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_first=t_last;

DER_first=DER_last;

t_last=tb(j)+τ

2;

DER_last=ER(j);

ELSE

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_last=tb(j)+τ

2;

DER_last=ER(j);

ELSE

IF (ER(j)>

=DER_firstANDER(j)>

=DER_last)

IF (PACR>

=DER_firstAND(PACR−

DER_first)(t_last−

t_first)<

(DER_first−

DER_last)(tb(j)+τ

3−

t_last))

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_first=t_last;

DER_first=DER_last;

t_last=tb(j)+τ

3;

DER_last=ER(j);

ELSE

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_last=tb(j)+τ

3;

DER_last=ER(j);

ELSE

IF (ER(j)>

=DER_firstANDER(j)>

=DER_last)

IF (PACR>

=DER_firstAND(PACR−

DER_first)(t_last−

t_first)<

(ER(j)−

DER_last)(tb(j)+τ

3−

t_last))

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_first=t_last;

DER_first=DER_last;

t_last=tb(j)+τ

3;

DER_last=ER(j);

ELSE

IF (t_last>

tb(j)+τ

3)

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_last=tb(j)+τ

3;

DER_last=ER(j)

ELSE

IF (ER(j)>

=DER_firstANDER(j)<

DER_last)

IF (PACR>

=DER_firstANDPACR<

DER_last)

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_first=t_last;

DER_first=DER_last;

t_last=tb(j)+τ

2;

DER_last=ER(j);

ELSE

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

DER_first=DER_last;

t_last=tb(j)+2;

DER_last=ER(j);

ELSE

IF (ER(j)<

DER_firstANDER(j)<

DER_last)

IF (PACR>

=DER_firstANDPACR<

DER_last)

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

t_first=t_last;

DER_first=DER_last;

t_last=tb(j)+τ

2;

DER_last=ER(j)

ELSE

assigning the contents of said first and second policing rate buffers and said first and second application time buffers as follows;

DER_first=DER_last;

t_last=tb(j)+τ

2;

DER_last=ER(j);

Where;

t_first is the contents of the first application time buffer

t_last is the contents of the second application time buffer

DER_first is the contents of the first policing rate buffer

DER_last is the contents of the second policing rate buffer

tb(j) is the time at which a backward resource management cell is transmitted to the source;

τ

2 is an upper limit on feedback delay;

τ

3 is a lower limit on feedback delay; and

ER(j) is a new rate as determined from a previous cell received from the source; and

PACR is the current policing rate.

12. A policer for policing cell rates at a switch interface, for cells received from a source in an allowed cell rate system, the method including the steps of:

a) storing a current policing rate (PACR) in a current policing rate buffer;

b) storing a plurality of policing rates and policing rate application times in respective policing rate and policing rate application time buffers;

c) in response to the departure of a backward resource management cell to the source at time tb(j), setting the contents of said policing rate buffers and said policing rate application time buffers according to the relative magnitudes of said current policing rate buffer and the contents of said policing rate buffers; and

d) determining whether or not said cell received from said source conforms to said policing rate and if not rejecting said cell received from said source.

13. An apparatus for adjusting policing cell rates at a switch interface, for cells received from a source in an allowed cell rate system, the apparatus comprising:

a) memory for storing a current policing rate (PACR) in a current policing rate buffer;

b) memory for storing a plurality of policing rates and policing rate application times in respective policing rate and policing rate application time buffers;

c) a BRM cell departure signal generator for generating a BRM cell departure signal when a BRM cell to transmitted to a source end system;

d) a processor for setting the contents of said policing rate buffers and said policing rate application time buffers according to the relative magnitudes of said current policing rate and the contents of said policing rate buffer, in response to the departure of a backward resource management cell to the source.

14. An apparatus as claimed in claim 13 further including a timer for providing an indication of a current time tb(j) at which said BRM cell is transmitted.

15. An apparatus as claimed in claim 13 further including:

a) a current policing rate buffer for storing a current policing rate (PACR);

b) a first policing rate buffer and a first policing rate time buffer for storing a first policing rate (DER_first) and a first policing rate application time (t_first) respectively; and

c) a last policing rate buffer and a last policing rate time buffer for storing a last policing rate (DER_last) and a last policing rate application time (t_last) in respectively.

16. An apparatus as claimed in claim 15 further including a receiver for receiving a backward resource management cell and processor-readable instructions for directing said processor to determine whether or not a current cell rate is greater than or equal to said first policing rate and if so, copying said first policing rate into said current policing rate buffer, copying said last policing rate application time into said first policing rate application time buffer, copying said last policing rate into said first policing rate buffer and setting the contents of said last policing rate buffer and said last policing rate application time buffer to zero.

17. An apparatus as claimed in claim 15 further including processor-readable instructions for directing said processor to determine whether or not said first policing rate application time is earlier than said last policing rate application time and if so, copying said first policing rate into said current policing rate buffer, copying said last policing rate application time into said first policing rate application time buffer, copying said last policing rate into said first policing rate buffer and setting the contents of said last policing rate buffer and said last policing rate application time buffer to zero.

18. An apparatus as claimed in claim 15 further including a receiver for receiving a cell from said source at a time ta(k) and processor-readable instructions for directing said processor to determine whether or not the current policing rate should be updated.

19. An apparatus as claimed in claim 18 further including processor-readable instructions for directing the processor to determine whether said current policing rate is equal to said first policing rate and for determining whether said first policing rate application time is equal to said last policing rate application time and for determining whether said first policing rate is equal to said last policing rate and for determining whether said last policing rate application time is equal to zero and for determining whether said last policing rate is equal to zero and if so, changing the contents of said current policing rate buffer.

20. An apparatus as claimed in claim 18 further including processor-readable instructions for directing said processor to determine whether or not said cell received from said source conforms to said policing rate.

21. An apparatus as claimed in claim 20 further including memory and processor-readable instructions for directing said processor to calculate and store a current policing increment value.

22. An apparatus as claimed in claim 21 further including memory for storing said current and immediately past policing increment values and processor-readable instructions for directing said processor to determine the minimum value of the reciprocal of said current and immediately past policing increment values.

23. An apparatus as claimed in claim 22 further including memory for storing a cell delay variation tolerance value and processor-readable instructions for directing said processor to determine whether or not the sum of a last virtual scheduling time (LVST) and said minimum value is less than or equal to the sum of the time ta(k) and said cell delay variation tolerance value.

24. An apparatus for adjusting policing cell rates at a switch interface, for cells received from a source in an allowed cell rate system, the apparatus comprising:

a) means for storing a current policing rate (PACR) in a current policing rate buffer;

b) means for storing a plurality of policing rates and policing rate application times in respective policing rate and policing rate application time buffers;

c) means for generating a BRM cell departure signal when a BRM cell to transmitted to a source end system;

d) means for setting the contents of said policing rate buffers and said policing rate application time buffers according to the relative magnitudes of said current policing rate and the contents of said policing rate buffer, in response to the departure of a backward resource management cell to the source.

25. An apparatus as claimed in claim 24 further including a timer for providing an indication of a current time tb(j) at which said BRM cell is transmitted.

26. An apparatus as claimed in claim 24 further including:

a) a current policing rate buffer for storing a current policing rate (PACR);

b) a first policing rate buffer and a first policing rate time buffer for storing a first policing rate (DER_first) and a first policing rate application time (t_first) respectively; and

c) a last policing rate buffer and a last policing rate time buffer for storing a last policing rate (DER_last) and a last policing rate application time (t_last) in respectively.

27. An apparatus as claimed in claim 26 further including a receiving means for receiving a backward resource management cell and means for directing said processor to determine whether or not a current cell rate is greater than or equal to said first policing rate and if so, copying said first policing rate into said current policing rate buffer, copying said last policing rate application time into said first policing rate application time buffer, copying said last policing rate into said first policing rate buffer and setting the contents of said last policing rate buffer and said last policing rate application time buffer to zero.

28. An apparatus as claimed in claim 26 further including means for determining whether or not said first policing rate application time is earlier than said last policing rate application time and if so, copying said first policing rate into said current policing rate buffer, copying said last policing rate application time into said first policing rate application time buffer, copying said last policing rate into said first policing rate buffer and setting the contents of said last policing rate buffer and said last policing rate application time buffer to zero.

29. An apparatus as claimed in claim 26 further including a means for receiving a cell from said source at a time ta(k) and means for determining whether or not the current policing rate should be updated.

30. An apparatus as claimed in claim 29 further including means for determining whether said current policing rate is equal to said first policing rate and for determining whether said first policing rate application time is equal to said last policing rate application time and for determining whether said first policing rate is equal to said last policing rate and for determining whether said last policing rate application time is equal to zero and for determining whether said last policing rate is equal to zero and if so, changing the contents of said current policing rate buffer.

31. An apparatus as claimed in claim 29 means for determining whether or not said cell received from said source conforms to said policing rate.

32. An apparatus as claimed in claim 31 further including memory and means for calculating and storing a current policing increment value.

33. An apparatus as claimed in claim 32 further including memory for storing said current and immediately past policing increment values and means for determining the minimum value of the reciprocal of said current and immediately past policing increment values.

34. An apparatus as claimed in claim 33 further including memory for storing a cell delay variation tolerance value and means for determining whether or not the sum of a last virtual scheduling time (LVST) and said minimum value is less than or equal to the sum of the time ta(k) and said cell delay variation tolerance value.

35. A computer-readable storage medium on which is stored a plurality of computer readable instruction for directing a processor to adjust policing cell rates at a switch interface, for cells received from a source in an allowed cell rate system, said instructions being operable to direct said processor to perform the steps of:

a) storing a current policing rate (PACR) in a current policing rate buffer;

b) storing a plurality of policing rates and policing rate application times in respective policing rate and policing rate application time buffers;

c) in response to the departure of a backward resource management cell to the source at time tb(j), setting the contents of said policing rate buffers and said policing rate application time buffers according to the relative magnitudes of said current policing rate and the contents of said policing rate buffers.

36. A computer-readable storage medium as claimed in claim 35 further including codes operable to direct the processor to perform the steps of

a) storing a current policing rate (PACR) in a current policing rate buffer;

b) storing a first policing rate (DER_first) and a first policing rate application time (t_first) in a first policing rate buffer and a first policing rate time buffer respectively;

c) storing a last policing rate (DER_last) and a last policing rate application time (t_last) in a last policing rate buffer and a last policing rate time buffer respectively.

37. A computer-readable storage medium as claimed in claim 36 further including codes operable to direct the processor to perform the step of receiving a backward resource management cell and on receiving such cell, determining whether or not a current cell rate is greater than or equal to said first policing rate and if so copying said first policing rate into said current policing rate buffer, copying said last policing rate application time into said first policing rate application time buffer, copying said last policing rate into said first policing rate buffer and setting the contents of said last policing rate buffer and said last policing rate application time buffer to zero.

38. A computer-readable storage medium as claimed in claim 36 further including codes operable to direct the processor to perform the step of determining whether or not said first policing rate application time is earlier than said last policing rate application time and if so copying said first policing rate into said current policing rate buffer, copying said last policing rate application time into said first policing rate application time buffer, copying said last policing rate into said first policing rate buffer and setting the contents of said last policing rate buffer and said last policing rate application time buffer to zero.

39. A computer-readable storage medium as claimed in claim 36 further including codes operable to direct the processor to perform the step of receiving a cell from said source at a time ta(k) and determining whether or not the current policing rate should be updated.

40. A computer-readable storage medium as claimed in claim 39 further including codes operable to direct the processor to perform the step of determining whether said current policing rate is equal to said first policing rate and whether said first policing rate application time is equal to said last policing rate application time and whether said first policing rate is equal to said last policing rate and whether said last policing rate application time is equal to zero and whether said last policing rate is equal to zero and if so, changing said current policing rate.

41. A computer-readable storage medium as claimed in claim 39 further including codes operable to direct the processor to perform the step of determining whether or not said cell received from said source conforms to said policing rate.

42. A computer-readable storage medium as claimed in claim 41 further including codes operable to direct the processor to perform the step of determining the minimum value of the reciprocal of a current and immediately past policing increment values.

43. A computer-readable storage medium as claimed in claim 42 further including codes operable to direct the processor to perform the step of determining whether or not the sum of a last virtual scheduling time (LVST) and said minimum value is less than or equal to the sum of the time ta(k) and a cell delay variation tolerance value.