Method and apparatus for random packet marking for differentiated services

• US 7,277,388 B1
• Filed: 03/31/2000
• Issued: 10/02/2007
• Est. Priority Date: 03/31/2000
• Status: Expired due to Fees

• Current Assignee: Nokia Internet Communications (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Koodli, Rajeev
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Jagannathan; Melanie
• Application Number:
  US09/540,361
• Time in Patent Office: 2,741 Days
• Field of Search: 370229-235, 370/395.21, 370/258, 370/253, 370/465, 370/468, 370/414, 370/416, 370/429
• US Class Current: 370/230.1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A method is disclosed for a router to provide random assignments of three priorities, each signifying a drop precedence, to packets on a per customer basis. The router determines a sending rate estimate. Then the router marks a packet a priority level based on the sending rate estimate.

Claims

1. A method, comprising:

determining a sending rate estimate, s;

determining any credits or debits for a packet stream including a plurality of data packets from a customer domain, a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from the customer domain.

2. A method, comprising:

determining a sending rate estimate, s;

determining any credits or debits for a packet stream including a plurality of data packets from a customer domain, a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, marking comprises determining if the sending rate estimate is less than a first rate threshold and in response to a determination that the sending rate estimate is less than the first rate threshold, setting a probability of marking at least one data packet with a first selected priority level is one of a plurality of priority levels, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from the customer domain.

3. The method of claim 2, further comprising

in response to a determination that the s is less than the first rate threshold, incrementing a burst size.

4. A method, comprising:

determining a sending rate estimate, s;

determining any credits or debits for a packet stream including a plurality of data packets from a customer domain, a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, marking comprises determining if the sending rate estimate is between a first rate threshold and a second rate threshold and in response to a determination that the sending rate estimate is between a first rate threshold and a second rate threshold, setting a probability of marking a data packet with a subordinate priority level based on s, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from the customer domain.

5. A method, comprising:

determining a sending rate estimate, s;

determining any credits or debits for a packet stream including a plurality of data packets from a source; and

probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, marking comprises determining if the sending rate estimate is between a first rate threshold and a second rate threshold and in response to a determination that the sending rate estimate is between a first rate threshold and a second rate threshold, marking a data packet such that a rate of packets marked a subordinate policy level is no greater than 1−

first rate threshold/s.

6. A method, comprising:

determining a sending rate estimate, s;

determining any credits or debits for a packet stream including a plurality of data packets from a source; and

probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, marking comprises determining if the sending rate estimate is above a second rate threshold and in response to a determination that the sending rate estimate is above the second rate threshold, marking the packet such that a rate of packets marked the second priority level is at least (second rate threshold-first rate threshold)/s.

7. The method of claim 6, further comprising in response to a determination that the sending rate is above the second rate threshold, marking the packet such that a rate of packets marked a lowest priority level is at least (s−

second rate threshold)/s.

8. A method, comprising:

determining a sending rate estimate, s;

determining any credits or debits for a packet stream including a plurality of data packets from a source; and

probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s;

determining if the sending rate estimate is greater than a rate threshold;

in response to a determination that the sending rate estimate is greater than the rate threshold, determining if a burst size is greater than a minimum burst; and

in response to a determination that the burst size is greater than the minimum burst, marking the packet a first priority level.

9. The method of claim 8, further comprising in response to a determination that the burst size is greater than the minimum burst, decrementing the burst size.

10. A method, comprising:

determining a sending rate estimate, s;

determining any credits or debits for a packet stream including a plurality of data packets from a source; and

probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s;

determining if the sending rate estimate is greater than the super rate threshold, determining if a burst size is greater than a minimum burst; and

in response to a determination that the burst size is greater than a minimum burst, marking the packet a priority level based on a count of packets marked a highest priority level during a period.

11. The method of claim 10, further comprising in response to a determination that the burst size is greater than the minimum burst, decrementing the burst size.

12. An apparatus, comprising:

a first determining unit configured to determine a sending rate estimate, s; and

a second determining unit configured to determine any credits or debits for the packet stream, wherein a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

a marking unit configured to probabilistically mark the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from a customer domain.

13. The apparatus of claim 12, wherein the mark unit comprises a determining unit configured to determine if the sending rate estimate is between a first rate threshold and a second rate threshold and another marking unit configured to mark a data packet such that a rate of packets marked a subordinate priority level is no greater than 1−

(first rate threshold/s) in response to a determination that the sending rate estimate is between a first rate threshold and a second rate threshold.

14. An apparatus, comprising:

a first determining unit configured to determine a sending rate estimate, s; and

a second determining unit configured to determine any credits or debits for the packet stream, wherein a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

a marking unit configured to probabilistically mark the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from a customer domain, the marking unit comprising

a third determining unit configured to determine if the sending rate estimate is less than a first rate threshold; and

a setting unit configured to set a probability of marking at least one data packet with a first selected priority level to a first value, responsive to a determination that the sending rate estimate is less than the first rate threshold, wherein said first selected priority level is one of a plurality of priority levels.

15. The apparatus of claim 14, further comprising a unit configured to increment a burst size, in response to a determination that the s is less than the first rate threshold.

16. An apparatus, comprising:

a first determining unit configured to determine a sending rate estimate, s; and

a second determining unit configured to determine any credits or debits for the packet stream, wherein a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

a marking unit configured to probabilistically mark the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from a customer domain, the marking unit comprising a third determining unit configured to determine if the sending rate estimate is between a first rate threshold and a second rate threshold; and

a setting unit configured to set a probability of marking a data packet with a subordinate priority level based on s, responsive to a determination that the sending rate estimate is between a first rate threshold and a second rate threshold.

17. An apparatus, comprising:

a first determining unit configured to determine a sending rate estimate, s; and

a second determining unit configured to determine any credits or debits for a packet stream including a plurality of data packets from a source, a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

a marking unit configured to probabilistically mark packet stream to one of a plurality of priority levels based on the sending rate estimate, s, the marking unit comprising a third determining unit configured to determine if the sending rate estimate is above a second rate threshold; and

a marking unit configured to mark the packet such that a rate of packets marked the second priority level is at least (second rate threshold−

first rate threshold)/s, in response to a determination that the sending rate estimate is above the second rate threshold.

18. The apparatus of claim 17, further comprising another marking unit configured to mark the packet such that a rate of packets marked a lowest priority level is a least (s−

second rate threshold)/s, in response to a determination that the sending rate is above the second rate threshold.

19. An apparatus, comprising:

a first determining unit configured to determine a sending rate estimate, s; and

a second determining unit configured to determine any credits or debits for a packet stream including a plurality of data packets from a source, wherein a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met;

a marking unit configured to probabilistically mark the packet stream to one of a plurality of priority levels based on the sending rate estimate, s;

a third determining unit configured to determine if the sending rate estimate is greater than a rate threshold;

a fourth determining unit configured to determine if a burst size is greater than a minimum burst, in response to a determination that the sending rate estimate is greater than the rate threshold; and

another marking unit configured to mark the packet a first priority level, in response to a determination that the burst size is greater than a minimum burst.

20. The apparatus of claim 19, further comprising a decrementing unit configured to decrement the burst size, in response to a determination that the burst size is greater than the minimum burst.

21. An apparatus, comprising:

a first determining unit configured to determine a sending rate estimate, s; and

a second determining unit configured to determine any credits or debits for a packet stream including a plurality of data packets from a source, a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met;

a marking unit configured to probabilistically mark the packet stream to one of a plurality of priority levels based on the sending rate estimate, s;

a third determining unit configured to determine if the sending rate estimate is greater than a super rate threshold;

a fourth determining unit configured to determine if a burst size is greater than a minimum burst, in response to a determination that the sending rate estimate is greater than the super rate threshold; and

another marking unit configured to mark the packet a priority level based on a count of packets marked a highest priority level during a period, in response to a determination that the burst size is grater than a minimum burst.

22. The apparatus of claim 21, further comprising a decrementing unit configured to decrement the burst size, in response to a determination that the burst size is greater than the minimum burst.

23. A method, comprising:

determining a first probability by using a first algorithm;

determining at least one second probability by using a second algorithm, the first algorithm being different from the second algorithm; and

weighting each probability so that each probability contributes to a net probability, wherein the weighting comprises determining any credits or debits for a packet stream including a plurality of data packets from a source, wherein a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from a customer domain.

24. A computer program embodied within a computer readable medium, when executed the computer program includes means for marking a packet stream including a plurality of data packets from a source by performing:

determining a sending rate estimate, s; and

determining any credits or debits for the packet stream, wherein a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from a customer domain.

25. A system for marking a packet stream including a plurality of data packets from a source, comprising:

a metering tool for determining a sending rate estimate, s; and

a determining means for determining any credits or debits for the packet stream, wherein a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

a router for probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from a customer domain.

26. An apparatus for marking a packet stream including a plurality of data packets from a source comprising:

a metering tool for determining a sending rate estimate, s; and

a determining component for determining any credits or debits for the packet stream, wherein a probability marking of the packet stream is improved while there is a sufficiently accumulated credit and when a first criterion is met; and

a marking component for probabilistically marking the packet stream to one of a plurality of priority levels based on the sending rate estimate, s, wherein the packet marking is on a flow-aggregate or aggregate basis for the packet stream including a plurality of data packets from a customer domain.