Method and apparatus for providing fair traffic scheduling among aggregated internet protocol flows

• US 6,084,855 A
• Filed: 02/18/1997
• Issued: 07/04/2000
• Est. Priority Date: 02/18/1997
• Status: Expired due to Term

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Telecommunications Oy (Nokia Corporation)
• Inventors: Markki, Outi, Soirinsuo, Timo
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US08/802,451
• Time in Patent Office: 1,232 Days
• Field of Search: 370/229-235, 370/252, 370/253, 370/390, 370/389, 370/391, 370/392, 370/351-356
• US Class Current: 370/235
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and apparatus is disclosed for providing fair traffic scheduling of L2 connections based on the number of IP flows and a priority coefficient for flow groups in the L2 connection. IP flows are scheduled according to a priority coefficient. The system identifies a number of IP flows for a plurality of connections, assigns a priority coefficient for each of the IP flows and schedules the IP flows according to the priority coefficient. The assignment of a priority coefficient results in a probability P_i that a data unit belonging to a flow carried over connection A_i will be selected for forwarding as defined by σ_i *x_i /Σ(x₁ . . . x_n), i={1,2, . . . n}, where x_i is the number of flows carried over connection A_i, σ_i is the priority and n is the number of connections. The relationship between the number of flows x_i and the priority σ_i is defined by Σ.sub.(e=1-n) (σ_i *x_i)/Σ.sub.(i=1-n) x_i =1.

Claims

1. A method of prioritizing the scheduling of Internet Protocol (IP) flows, comprising the steps of:

identifying a number of IP flows for each of a plurality of connections;

assigning a priority to each of the plurality of connections based on the identified number of IP flows; and

scheduling packet forwarding of the IP flows according to the assigned priority.

2. The method of claim 1 wherein the step of assigning a priority further comprises the step of defining a probability P_i that a data unit belonging to a flow carried over a connection A_i of n total connections, A_i, . . . A_n, is selected for forwarding according to:

##EQU3## where x_i represents a number of flows carried over the connection A_i, σ

_i represents a priority assigned to flows x_i and n represents a total number of connections.

3. The method of claim 2 wherein a relationship between the number of flows x_i and the priority σ

_i is defined by;

##EQU4##

4. The method of claim 1 wherein the step of identifying the number of IP flows further comprises the steps of:

monitoring packets carried over a connection;

extracting address information from the packets for a predetermined sample period;

storing the extracted address information;

counting the number of extractions stored; and

estimating the number of IP flows based upon the number of stored extractions counted.

5. The method of claim 4 wherein the step of extracting address information comprises the step of extracting full source address:

port and destination address;

port from the packets.

6. The method of claim 4 wherein the step of extracting address information comprises the step of extracting only a host or port part of an IP address from the packets.

7. The method of claim 4 wherein the step of storing the address information further comprises the step of compressing the extracted address information.

8. The method of claim 4 wherein the step of monitoring packets comprises the steps of:

replicating PDUS; and

directing the replicated PDUs to a processor for address extraction.

9. The method of claim 4 wherein the processor is outside the data path.

10. The method of claim 4 wherein the step of monitoring packets comprises the step of sampling the packets along the data path.

11. The method of claim 4 wherein the predetermined sample period comprises a selected time duration.

12. The method of claim 4 wherein the predetermined sample period comprises the time required to sample a predetermined number of packets.

13. The method of claim 1 wherein the step of assigning a priority further comprises the step of giving a higher priority to a connection having more users.

14. The method of claim 1 wherein the step of assigning a priority further comprises the step of differentiating a flow based on a management parameter.

15. The method of claim 14 wherein the management parameter represents operational and administrative considerations.

16. The method of claim 1 wherein the step of assigning a priority is based upon a compensation structure for different flow types.

17. An apparatus for scheduling Internet Protocol (IP) flows, comprising:

a monitor that identifies a number of IP flows for each of a plurality of connections;

a prioritizer, operatively coupled to the monitor, the prioritizer assigning a priority coefficient for each of the connections; and

a scheduler, operatively coupled to the monitor, the scheduler scheduling the IP flows according to the priority coefficient.

18. The apparatus of claim 17 wherein the priority coefficient assigned by the prioritizer results in a probability that a data unit belonging to a flow carried over connection A_i is selected for forwarding as defined by:

##EQU5## where x_i represents a number of flows carried over connection A_i, σ

_i represents a priority coefficient and n represents a number of connections.

19. The apparatus of claim 18 wherein a relationship between the number of flows x_i and the priority coefficient σ

_i is defined by;

##EQU6##20.

20. The apparatus of claim 17 wherein the monitor further comprises:

means for analyzing packets carried over a connection;

means for extracting address information from the packets for a predetermined sample period;

a memory for storing the extracted address information;

a counter for counting the number of extractions stored in the memory; and

a processor for estimating the number of IP flows based upon the number of extractions counted.

21. The apparatus of claim 20 wherein the means for extracting address information further comprises means for extracting full source address:

port and destination address;

port from the packets.

22. The apparatus of claim 20 wherein the means for extracting address information further comprises means for extracting only a host part of an IP address and port from the packets.

23. The apparatus of claim 20 wherein the processor further comprises data compression means for compressing the extracted address information.

24. The apparatus of claim 17 wherein the monitor further comprises:

means for replicating PDUs; and

means for directing the replicated PDUs to a processor for address extraction.

25. The apparatus of claim 20 wherein the processor is outside the data path.

26. The apparatus of claim 20 wherein the processor samples the packets along the data path.

27. The apparatus of claim 20 wherein the predetermined sample period comprises a selected time duration.

28. The apparatus of claim 20 wherein the predetermined sample period comprises a time required to sample a predetermined number of packets.

29. The apparatus of claim 17 wherein the priority coefficient represents a higher priority for a connection having more users.

30. The apparatus of claim 17 wherein the priority coefficient is used to differentiate a flow based on a management parameter.

31. The apparatus of claim 30 wherein the management parameter comprises operational and administrative considerations.

32. The apparatus of claim 17 wherein the priority coefficient is based upon a compensation structure for different flow types.