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

• US 20040213265A1
• Filed: 04/16/2004
• Published: 10/28/2004
• Est. Priority Date: 04/24/2003
• Status: Active Grant

• Current Assignee: Monarch Networking Solutions LLC (Acacia Research Corporation)
• Original Assignee: Orange S.A.
• Inventors: Oueslati, Sara, Roberts, James
• Granted Patent: US 7,646,715 B2
• Time in Patent Office: Days
• US Class Current: 370/395.42
• 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

The invention relates to a device for processing packets of flows on a network link, the device including scheduling means 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 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.

2. A device according to claim 1, further comprising admission control means for controlling admission of said packets into the device in accordance with admission criteria.

3. A device according to claim 2, wherein the scheduling means send the admission control means admissibility condition data.

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

5. A device according to claim 4, 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.

6. A device according to claim 4, 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.

7. A device according to claim 4, comprising means for entering a new flow in the list if the admission criteria are satisfied.

8. A device according to claim 2, 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.

9. A device according to claim 1, wherein the scheduling means schedule as priority packets any packets of flows in the queue that are not in a list of active flows and as non-priority packets any packets of flows that are already in said list.

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

11. A device according to claim 10, wherein a pointer P identifies the last of the priority packets at the head of the queue.

12. A device according to claim 11, further adapted to employ a list of active flows containing the identifiers of the active flows and wherein a time stamp is used for scheduling packets.

13. A device according to claim 11, further comprising 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.

14. A device according to claim 12, further comprising congestion measuring means.

15. A device according to claim 14, 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.

16. A device according to claim 10, comprising means for determining whether the PIFO queue is empty or not.

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

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

19. 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.

20. A method according to claim 19, further comprising an admission control step for controlling the admission of said packets into a device for processing said packets in accordance with admission criteria.

21. A method according to claim 20, further comprising a step of sending admissibility conditions to the means for controlling admission of the data.

22. A method according to claim 21, wherein the admission control step includes interrogating a list of protected flows for each incoming packet.

23. A method according to claim 22, 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.

24. A method according to claim 22, 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.

25. A method according to claim 22, comprising a step of entering a new flow in the list if the admission criteria are satisfied.

26. A method according to claim 21, 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.

27. A method according to claim 20, wherein the scheduling step schedules as priority packets any packets in the queue that are not in a list of active flows and as non-priority packets any packets of flows that are already in that list.

28. A method according to claim 20, wherein the scheduling means schedule packets in a PIFO queue.

29. A method according to claim 28, wherein a pointer P identifies the last of the priority packets at the head of the queue.

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

31. A method according to claim 30, further comprising steps of 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.

32. A method according to claim 30, further comprising congestion measurement.

33. A method according to claim 32, 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.

34. A method according to claim 28, including a step for determining whether the PIFO queue is empty or not.

35. A method according to claim 19, wherein a signal relating to the loss of packets is sent to a user.

36. A method according to claim 19, further comprising discriminating classes of service at admission control level.

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