System and method for recognizing application-specific flows and assigning them to queues

• US 7,225,271 B1
• Filed: 06/29/2001
• Issued: 05/29/2007
• Est. Priority Date: 06/29/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Oran, David R., Davie, Bruce S., DiBiasio, Michael V.
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): EL CHANTI, HUSSEIN A
• Application Number:
  US09/896,276
• Time in Patent Office: 2,160 Days
• Field of Search: 709223-225, 709231-233, 709/236, 709238-240
• US Class Current: 709/240
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2475 for supporting traffic characterised by the type of applications
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/801 Real time traffic

Abstract

A system assigns network traffic flows to appropriate queues and/or queue servicing algorithms based upon one or more flow parameters contained in reservation requests associated with the traffic flows. The system may be disposed at an intermediate network device within a computer network. The intermediate network device includes a reservation engine, a packet classification engine, an admission control entity, a traffic scheduler, and a flow analyzer. The flow analyzer includes or has access to a memory that is preprogrammed with one or more heuristic sets for use in evaluating the flow parameters of reservation requests. When a reservation request that includes one or more flow parameters characterizing the bandwidth and/or forwarding requirements of the anticipated traffic flow is received, the flow analyzer applies the heuristic sets. Depending on which set of heuristics, if any, the parameters satisfy, the flow analyzer selects the appropriate queue and/or queue servicing algorithm for the flow.

Claims

1. An intermediate network device for use in a computer network having a plurality of entities configured to issue requests to reserve network resources for use by traffic flows, the reservation requests specifying one or more flow parameters, the intermediate network device comprising:

a traffic scheduler having one or more network resources for use in forwarding network traffic received at the device at different rates;

a classification engine configured to identify network messages belonging to respective traffic flows based upon predefined criteria;

a resource reservation engine in communicating relationship with the traffic scheduler and the classification engine, the resource reservation engine including a flow analyzer that is configured to apply one or more sets of predefined heuristics that are accessible by the flow analyzer to the one or more flow parameters specified in the reservation requests to determine a type of traffic of the given traffic flow, the flow parameters including a token bucket rate, a token bucket size, and a peak data rate, the one or more sets of heuristics including heuristics configured to compare the token bucket rate, token bucket size, and a ratio of the peak data rate to the token bucket rate each with a different programmed constant descriptive of a particular type of traffic, to determine the type of traffic independent of any marking values in packets of the given traffic flow that identify traffic type, and the flow analyzer further configured to select a queue and/or a queue servicing algorithm for assignment to the traffic flow corresponding to the reservation request.

2. The intermediate network device of claim 1 wherein

the classification engine is directed to identify network messages belonging to the traffic flow, and

the traffic scheduler is directed to place network messages identified as belonging to the traffic flow in the selected queue.

3. The intermediate network device of claim 1 wherein

the selected queue is one of a priority queue (PQ) and a reserved queue, and

the PQ is drained before any other queues.

4. The intermediate network device of claim 3 wherein

a first set of heuristics is provided for determining whether the respective traffic flows carry real-time voice information, and

traffic flows that are determined to carry real-time voice information are assigned to the PQ.

5. The intermediate network device of claim 1 wherein a first set of predefined heuristics is given by the following equation:

6. The intermediate network device of claim 5 wherein r′

is approximately 12288 bytes/second, b′

is approximately 592 bytes/second and p_to_r′

is approximately 110 percent.

7. The intermediate network device of claim 4 wherein

a reserved queue is selected for each traffic flow that does not satisfy the first set of heuristics, and

a Weight Fair Queuing (WFQ) queue servicing algorithm is applied to the reserved queues.

8. The intermediate network device of claim 2 wherein the flow analyzer, in response to the application of the one or more sets of heuristics, associates a selected Per-Hop Behavior (PHB) with the traffic flow corresponding to the reservation request.

9. The intermediate network device of claim 1 wherein

the resource reservation engine utilizes the Resource reSerVation Protocol (RSVP) specification standard, and

the flow parameters are located in a RSVP Reservation (Resv) message received by the device.

10. In a computer network having a plurality of entities interconnected by a plurality of intermediate network devices having one or more resources for use in forwarding network traffic flows, a method for assigning queues and/or queue servicing algorithms to the traffic flows, the method comprising the steps of:

receiving, at the intermediate network device, a reservation request message specifying one or more flow parameters for a given traffic flow, the one or more flow parameters including a token bucket rate, a token bucket size, and a peak data rate;

applying, at the intermediate network device, one or more sets of heuristics to the flow parameters of the received reservation request message to determine a type of traffic of the given traffic flow, the one or more sets of heuristics including heuristics configured to compare the token bucket rate, token bucket size, and a ratio of the peak data rate to the token bucket rate each with a different programmed constant descriptive of a particular type of traffic, to determine the type of traffic independent of any marking values in packets of the given traffic flow that identify traffic type; and

selecting a queue and/or a queue servicing algorithm at the intermediate device for use with the given traffic flow, based on the application of the one or more sets of heuristics.

11. The method of claim 10 wherein a first set of heuristics is given by the following equation:

12. The method of claim 11 wherein r′

is approximately 12288 bytes/second, b′

is approximately 592 bytes/second and p_to_r′

is approximately 110 percent.

13. The method of claim 10 wherein

a first set of heuristics is provided for determining whether the respective traffic flows carry real-time voice information, and

a given traffic flow that is determined to carry real-time voice information, based on the first set of heuristics, is assigned to a priority queue (PQ) that is drained before all other queues.

14. The method of claim 10 wherein a traffic flow that is determined to carry other than real-time voice information is assigned to a selected reserved queue.

15. The method of claim 14 further comprising the step of applying a Weight Fair Queuing (WFQ) queue servicing algorithm to the reserved queues.

16. The method of claim 10 wherein the reservation request message corresponds to a Reservation (Resv) message as provided in the Resource reSerVation Protocol (RSVP) specification standard.

17. An intermediate network device for use in a computer network having a plurality of entities configured to issue requests to reserve network resources for use by traffic flows, the reservation requests specifying one or more flow parameters, the intermediate network device comprising:

means for receiving a reservation request message specifying one or more flow parameters for a given traffic flow, the one or more flow parameters including a token bucket rate, a token bucket size, and a peak data rate;

means for applying one or more sets of heuristics to the flow parameters of the received reservation request message to determine a type of traffic of the given traffic flow, the one or more sets of heuristics including heuristics configured to compare the token bucket rate, token bucket size, and a ratio of the peak data rate to the token bucket rate each with a different programmed constant descriptive of a particular type of traffic, to determine the type of traffic independent of any marking values in packets of the given traffic flow that identify traffic type; and

means for selecting a queue and/or a queue servicing algorithm for use with the given traffic flow based on the application of the one or more sets of heuristics.

18. The intermediate network device of claim 17, further comprising:

means for providing a set of heuristics to determine whether the respective traffic flows carry real-time voice information, and

means for assigning a traffic flow that is determined to carry real-time voice information, based on the set of heuristics, to a priority queue (PQ) that is drained before all other queues.

19. The intermediate network device of claim 18 wherein the flow parameters are selected from the group consisting of:

a token bucket rate for the given traffic flow;

a token bucket size for the given traffic flow; and

peak data rate for the given traffic flow.

20. A method for assigning appropriate queues in an intermediate network device to traffic flows that pass through the intermediate network device, the method comprising the steps of:

receiving, at the intermediate network device, a reservation request message specifying one or more flow parameters that describe a given traffic flow, the one or more flow parameters including a token bucket rate, a token bucket size, and a peak data rate;

comparing, at the intermediate network device, the token bucket rate with a programmed token bucket rate constant descriptive of a particular type of traffic, and

comparing, at the intermediate network device, the token bucket size with a programmed token bucket size constant descriptive of the particular type of traffic;

comparing, at the intermediate network device, the ratio of the peak data rate to the token bucket rate with a programmed peak data rate to token bucket rate constant descriptive of the particular type of traffic;

in response to the steps of comparing, determining, at the intermediate network device, a type of traffic for the given traffic flow independent of any marking values in packets of the given traffic flow that identify traffic type;

based on the determined type of traffic, directing the given traffic flow to a queue of the intermediate network device adapted for the determined type of traffic.

21. The method of claim 20 wherein the determined type of traffic is real-time voice traffic and the queue adapted for the determined type of traffic is a priority queue (PQ) that is serviced with preference over other queues.

22. The method of claim 20 wherein the marking values are differentiated services codepoint (DSCP) values.

23. The method of claim 20 further comprising the step of:

associating a selected Per Hop Behavior (PHB) with the given traffic flow in response to the step of comparing.

24. An intermediate network device configured to assign appropriate queues to traffic flows that pass through the intermediate network device, the intermediate network device comprising:

a communication facility configured to receive a reservation request message specifying one or more flow parameters that describe a given traffic flow, the one or more flow parameters including a token bucket rate, a token bucket size, and a peak data rate;

a flow analyzer configured to compare the token bucket rate with a programmed token bucket rate constant descriptive of a particular type of traffic, to compare the token bucket size with a programmed token bucket size constant descriptive of the particular type of traffic, and to compare the ratio of the peak data rate to the token bucket rate with a programmed peak data rate to token bucket rate constant descriptive of the particular type of traffic and to determine a type of traffic for the given traffic flow independent of any marking values in packets of the given traffic flow that identify traffic type; and

a traffic scheduler configured to direct the given traffic flow to a queue adapted for the determined type of traffic.

25. The intermediate network device of claim 24 wherein the determined type of traffic is real-time voice traffic and the queue adapted for the determined type of traffic is a priority queue (PQ) that is serviced with preference over other queues.

26. The intermediate network device of claim 24 wherein the marking values are differentiated services codepoint (DSCP) values.

27. The intermediate network device of claim 24 wherein the flow analyzer is further configured to associate a selected Per Hop Behavior (PHB) with the given traffic flow in response to the comparison.

28. A computer-readable storage media storing executable program instructions for assigning appropriate queues in an intermediate network device to traffic flows that pass through the intermediate network device, the executable program instructions when executed:

receive a reservation request message at the intermediate network device specifying one or more flow parameters that describe a given traffic flow, the one or more flow parameters including a token bucket rate, a token bucket size, and a peak data rate;

compare the token bucket rate with a programmed token bucket rate constant descriptive of a particular type of traffic;

compare the token bucket size with a programmed token bucket size constant descriptive of the particular type of traffic;

compare the ratio of the peak data rate to the token bucket rate with a programmed peak data rate to token bucket rate constant descriptive of the particular type of traffic;

determine, in response to the comparison, a type of traffic for the given traffic flow independent of any marking values in packets of the given traffic flow that identify traffic type; and

based on the determined type of traffic, direct the given traffic flow to a queue adapted for the determined type of traffic.