Method and a device for implicit differentiation of quality of service in a network

• US 7,646,715 B2
• Filed: 04/16/2004
• Issued: 01/12/2010
• Est. Priority Date: 04/24/2003
• Status: Expired due to Fees

• Current Assignee: Monarch Networking Solutions LLC (Acacia Research Corporation)
• Original Assignee: Orange S.A.
• Inventors: Roberts, James, Oueslati, Sara
• Primary Examiner(s): Sefcheck, Gregory B
• Application Number:
  US10/825,756
• Publication Number:
  US 20040213265A1
• Time in Patent Office: 2,097 Days
• Field of Search: None
• US Class Current: 370/234
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data

Abstract

Presented is a device for processing packets of flows on a network link. The device includes a scheduling module for scheduling packets in a queue in accordance with a fair queuing with priority algorithm.

Claims

1. A device for processing packets of flows on a network link, the device comprising:

scheduling means for scheduling packets of flows in a queue in accordance with a fair queuing with priority algorithm, the scheduling means being configured to schedule as priority packets any packets of flows in the queue that are not identified in a list of active flows and as non-priority packets any packets of flows that are already identified in the list of active flows;

means for writing flows in and erasing flows from the list of active flows as a function of the arrival and departure of packets of the flows, said means being configured to erase from the list of active flows a flow which has not had any packets in the queue for a certain time period, and thereby assigning priority to the packets of the flows for which a bit rate is below a dynamic threshold, the dynamic threshold being determined by traffic conditions; and

admission control means for controlling admission of said packets into the device in accordance with admission criteria;

wherein the scheduling means sends the admission control means admissibility condition data including a fair bit rate value that represents the bit rate achieved by a data flow that always has packets to send, and a priority load value which is a sum of the lengths of priority packets transmitted in a certain time period divided by the duration of that time period.

2. The device according to claim 1, wherein the admission control means comprise means for interrogating a list of protected flows for each incoming packet.

3. The device according to claim 2, further comprising means for erasing flows for which the time elapsed since the last packet was received exceeds a threshold value from the list of protected flows.

4. The device according to claim 2, wherein the admission control means comprise means for determining if the admission criteria are satisfied if a packet belongs to a flow that is not in the list of protected flows.

5. The device according to claim 2, comprising means for entering a new flow in the list of protected flows if the admission criteria are satisfied.

6. The device according to claim 1, wherein the scheduling means schedule the packets in a PIFO queue.

7. The device according to claim 6, wherein a pointer P identifies the last of the priority packets at the head of the queue.

8. The device according to claim 7, further configured to employ the list of active flows containing the identifiers of the active flows and wherein a time stamp is used for scheduling packets.

9. The device according to claim 8, further comprising means for measuring congestion.

10. The device according to claim 9, wherein congestion measurements are carried out as a function of a local time, a number of priority packet bytes transmitted during a current measurement period, and a number of bytes that a dummy flow could send in said current measuring period.

11. The device according to claim 6, comprising means for determining whether the PIFO queue is empty.

12. The device according to claim 1, further comprising discrimination means for distinguishing classes of service at admission control level.

13. The device according to claim 1, wherein the flows are identified by a hashing function applied to address attributes.

14. A method of treating packets of flows on a network link and ensuring a quality of service without explicitly distinguishing between real-time flows and data flows, the method comprising;

a scheduling step for scheduling packets of flows in a queue in accordance with a fair queuing with priority algorithm, the scheduling step scheduling as priority packets any packets in the queue that are not identified in a list of active flows and as non-priority packets any packets of flows that are already identified in the list of active flows;

writing flows in and erasing flows from the list of active flows as a function of the arrival and departure of packets of the flows, wherein a flow which has not has not had any packets in the queue for a certain time period erased from the list of active flows, and thereby assigning priority to the packets of the flows for which a bit rate is below a dynamic threshold, the dynamic threshold being determined by traffic conditions;

an admission control step for controlling the admission of said packets into a device for processing said packets in accordance with admission criteria; and

sending admissibility conditions data to a means for controlling admission of the data,

wherein the admissibility conditions data include;

a fair bit rate value that represents the bit rate achieved by a data flow that always has packets to send, and

a priority load value which is a sum of the lengths of priority packets transmitted in a certain time period divided by the duration of that time period.

15. The method according to claim 14, wherein the admission control step includes interrogating a list of protected flows for each incoming packet.

16. The method according to claim 15, wherein flows for which the time elapsed since the last packet was received exceeds a threshold value are erased from the list of protected flows.

17. The method according to claim 15, comprising a step for determining if the admission criteria are satisfied if a packet belongs to a flow that is not in the list of protected flows.

18. The method according to claim 15, comprising a step of entering a new flow in the list if the admission criteria are satisfied.

19. The method according to claim 14, wherein the scheduling means schedule packets in a PIFO queue.

20. The method according to claim 19, wherein a pointer P identifies the last of the priority packets at the head of the queue.

21. The method according to claim 20, further employing the list of active flows containing the identifiers of the flows and wherein a time stamp is used for scheduling packets.

22. The method according to claim 21, further comprising congestion measurement step for measuring congestion.

23. The method according to claim 22, wherein congestion measurements are carried out as a function of a local time, a number of priority packet bytes transmitted during a current measurement period, and a number of bytes that a dummy flow could send in said current measurement period.

24. The method according to claim 19, including a step for determining whether the PIFO queue is empty.

25. The method according to claim 14, wherein a signal relating to the loss of packets is sent to a user.

26. The method according to claim 14, further comprising discriminating classes of service at admission control level.

27. The method according to claim 14, wherein load sharing of flows over a plurality of links is effected with the aid of a function of address attributes including a free portion of a flow identifier.

28. A device for processing packets of flows on a network link, the device comprising:

scheduling means for scheduling packets in a queue as a function of a priority based on analyzing the incoming bit rate of the flows relative to a fair bit rate and in accordance with a fair queuing with priority algorithm; and

admission control means for controlling admission of said packets into the device in accordance with admission criteria,

wherein the admissibility condition data includes;

a fair bit rate value that represents the bit rate achieved by a data flow that always has packets to send, and

a priority load value, which is sum of the lengths of priority packets transmitted in a certain time period divided by the duration of that time period.

29. A method of treating packets of flows on a network link, the method comprising:

a scheduling step for scheduling packets in a queue as a function of a priority based on analyzing the incoming bit rate of the flows relative to a fair bit rate and in accordance with a fair queuing with priority algorithm;

an admission control step for controlling the admission of said packets into a device for processing said packets in accordance with admission criteria; and

a step of sending admissibility conditions to a means for controlling admission of the data;

wherein the admissibility conditions data include;

a fair bit rate value that represents the bit rate achieved by a data flow that always has packets to send, and

a priority load value, which is sum of the lengths of priority packets transmitted in a certain time period divided by the duration of that time period.