Method and computer program product for scheduling network communication packets originating from different flows having unique service requirements

• US 6,247,061 B1
• Filed: 06/09/1998
• Issued: 06/12/2001
• Est. Priority Date: 06/09/1998
• Status: Expired due to Term

• Current Assignee: Dekko Technologies, Inc. (Graham Holdings Company), Intel Corporation, Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tai, Tsung-Yuan Charles, Bell, Carol Ann, Douceur, John R., Yavatkar, Rajendra S., Bernet, Yoram, Bar, Ofer
• Primary Examiner(s): Harrell, Robert B.
• Assistant Examiner(s): WILLETT, STEPHAN F
• Application Number:
  US09/094,045
• Time in Patent Office: 1,099 Days
• Field of Search: 709/226, 709/240, 709/232, 709/234, 709/235, 340/825.5, 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235
• US Class Current: 709/240
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/22 Traffic shaping
• 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/28 in relation to timing considerations
• 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/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/627 policing

Abstract

A method and computer program product for scheduling network communication packets in a multimedia environment where different packet streams have reservations of network bandwidth to form packet flows. The present invention divides the packet scheduling function into distinct components that may be implemented as separate drivers in a layered driver environment as exists, for example, in the Microsoft Windows NT operating system. One component is called a conformer and will generate and assign to each packet in the packet flow at least one conformance time that signifies the earliest a packet may be sent and still conform to the network resource requirements associated with the flow. Many different conformance algorithms can be supported so that the best algorithm is used for a particular packet flow and the service requirements that it represents. Should it be necessary to actually hold a packet until the conformance time is met, a shaper component is used to delay the packets. Finally, a sequencer component will send packets out as fast as possible over the network interface card. Each flow of packets processed by the sequencer component has at least two priorities, one for when the packets are conforming and one for when the packets are non-conforming. The sequencer component maintains priority lists of packet flow queues and will service the highest priority queue list followed by each successive priority list until no packets remain for transmission or the network interface card is unable to handle more packets. Each priority list will have a queue discipline associated therewith that will determine in what order the packets are taken off of the respective flow queues.

Claims

1. In a network communication system having a plurality of computer systems logically interconnected to one another and wherein data packets are communicated across the network between one or more of the computer systems, which data packets require transmission through the network in the form of packet flows that are defined as including streaming data having certain network resource requirements, such as bandwidth, that are required to meet quality of service standards for properly communicating the data packets, a method for improving flexibility of scheduling delivery of the data packets through the network by allowing different scheduling algorithms to be supported by distinct software components configured as drivers, comprising the steps for:

receiving a data packet that is scheduled for delivery by the network to one of the computer systems, said data packet being initially received by a conformer component configured as a first driver and that generates and assigns a conformance time for the data packet that signifies the earliest time at which the data packet may be sent while still conforming to the resource requirements necessary to meet quality of service standards for communicating the data packet over the network;

if necessary in order to meet a required conformance time, sending the data packet to a shaper component configured as a second driver which delays the data packet so that delivery of the data packet will occur at essentially the conformance time, thereby shaping network traffic as required by conformance time for each data packet;

if not necessary in order to meet a required conformance time, sending the data packet directly through the second driver without delay to a sequencer component configured as a third driver which has a plurality of priority queue lists, each packet flow being assigned to a priority queue list for data packets that are conforming and being assigned to a priority queue list for data packets that are not conforming with respect to the current time so that the priority queue list of a data packet can be updated when its conformance time becomes less than the current time;

assigning the data packet to the priority queue list associated with its packet flow based on whether the data packet is conforming or nonconforming with respect to the current time; and

transmitting the data packet onto the communications network in order of priority of the one or more priority queue lists.

3. A method as recited in claims 1 or 2 wherein at least one of the supported scheduling algorithms is a leaky bucket conformance algorithm.

4. A method as recited in claims 1 or 2 wherein at least one of the supported scheduling algorithms is a combination token bucket algorithm and leaky bucket algorithm.

5. A method as recited in claims 1 or 2 wherein at least one of the supported scheduling algorithms is a combination token bucket algorithm and leaky bucket algorithm along with traffic parameters to calculate the conformance time according to the following steps:

generating a preliminary conformance time using the token bucket algorithm to ensure meeting the sustained data rate;

discarding the packet if is nonconforming; and

generating the actual conformance time using the leaky bucket algorithm to ensure meeting the peak rate.

6. A method as recited in claims 1 or 2 wherein said transmitting step includes a step for taking a priority queue list of a higher priority and completely processing it before processing another priority queue list of a lower priority.

7. A method as recited in claim 6 wherein a round-robin queue discipline is used for taking packets from a priority queue list.

8. A method as recited in claim 6 wherein a deficit round-robin queue discipline is used for taking packets from a priority queue list.

9. A method as recited in claim 6 wherein a conformance time sequential queue discipline is used for taking packets from a priority queue list.

10. A method as recited in claim 6 wherein different queue disciplines are used for processing different priority queue lists.

2. In a network communication system having a plurality of computer systems logically interconnected to one another and wherein data packets are communicated across the network between one or more of the computer systems which data packets require transmission through the network in the form of packet flows that are defined as including streaming data having certain network resource requirements, such as bandwidth, that are required to meet quality of service standards for properly communicating the data packets, a computer-readable medium having computer-executable program code means embodied in said medium for implementing a method for improving flexibility of scheduling delivery of the data packets through the network by. allowing different scheduling algorithms to be supported by distinct software components configured as drivers, and wherein said method is comprised of the steps for:

receiving a data packet that is scheduled for delivery by the network to one of the computer systems, said data packet being initially received by a conformer component configured as a first driver and that generates and assigns a conformance time for the data packet that signifies the earliest time at which the data packet may be sent while still conforming to the resource requirements necessary to meet quality of service standards for communicating the data packet over the network;

if necessary in order to meet a required conformance time, sending the data packet to a shaper component configured as a second driver which delays the data packet so that delivery of the data packet will occur at essentially the conformance time, thereby shaping network traffic as required by conformance time for each data packet;

if not necessary in order to meet a required conformance time, sending the data packet directly through the second driver without delay to a sequencer component configured as a third driver which has a plurality of priority queue lists, each packet flow being assigned to a priority queue list for data packets that are conforming and being assigned to a priority queue list for data packets that are not conforming with respect to the current time so that the priority queue list of a data packet can be updated when its conformance time becomes less than the current time;

assigning the data packet to the priority queue list associated with its packet flow based on whether the data packet is conforming or nonconforming with respect to the current time; and

transmitting the data packet onto the communications network in order of priority of the one or more priority queue lists.

11. In a network communication system having a plurality of computer systems logically interconnected to one another and wherein data Packets are communicated across the network between one or more of the computer systems, which data Packets require transmission through the network in the form of packet flows that are defined as including streaming data having certain network resource requirements, such as bandwidth, that are required to meet quality of service standards for properly communicating the data packets, a method for comprising the steps for:

receiving a data packet that is scheduled for delivery by the network to one of the computer systems;

generating at a conformer component configured as a first driver a conformance time representing the latest time the data packet should be sent in order to conform to the resource requirements necessary to meet quality or service standards for communicating the data packet over the network;

associating the conformance time with the data packet;

if necessary in order to meet a required conformance time, sending the data packet to a shaper component configured as a second driver which delays the data packet so that delivery of the data packet will occur at essentially the conformance time, thereby shaping network traffic as required by conformance time for each data packet;

if not necessary in order to meet a required conformance time, passing the data packet to a sequencer component configured as a third driver for continued processing using the conformance time, the third driver comprising a plurality of queue lists so that each packet flow is assigned to a priority queue list for data packets that are conforming with respect to the current time and is assigned to the same or a different priority queue list for data packets that are not conforming with respect to the current time;

assigning the data packet to the priority queue list associated with its packet flow based on whether the data packet is confirming or nonconforming with respect to the current time; and

sending the data packet to a destination node over the communications network in order of priority of the one or more priority queue lists.

12. A method as recited in claim 11 wherein the step of generating a conformance time uses a conformance algorithm and traffic parameters associated with the packet flow.

13. A method as recited in claim 11 wherein the step of generating a conformance time uses a leaky bucket conformance algorithm and traffic parameters associated with the packet flow.

14. A method as recited in claim 11 wherein the step of generating a conformance time uses a combination token bucket algorithm and leaky bucket algorithm and traffic parameters associated with the packet flow.

15. A method as recited in claim 11 further comprising the step of discarding nonconforming packets and wherein the step of generating a conformance time uses a combination token bucket and leaky bucket conformance algorithm along with traffic parameters to calculate the conformance time according to the following steps:

generating a preliminary conformance time using the token bucket algorithm to ensure meeting the sustained data rate;

discarding the packet if is nonconforming; and

generating the actual conformance time using the leaky bucket algorithm to ensure meeting the peak rate.

16. In a network communication system having a plurality of computer systems logically interconnected to one another and wherein data packets are communicated across the network between one or more of the computer systems, which data packets require transmission through the network in the form of packet flows that are defined as including streaming data having certain network resource requirements, such as bandwidth, that are required to meet quality of service standards for properly communicating the data packets, a computer-readable medium having computer-executable program code means embodied in said medium for implementing a method for improving flexibility of scheduling delivery of the data packets through the network by allowing different scheduling algorithms to be supported by distinct software components, at least one of which is configured as a driver for a sequencer component, and wherein said method is comprised of the steps for:

receiving a data packet that is scheduled for delivery by the network to one of the computer systems, said data packet including a conformance time that signifies the earliest time at which the data packet may be sent while still conforming to the resource requirements necessary to meet quality of service standards for communicating the data packet over the network;

sending the data packet directly to a driver configured as a sequencer component which has a plurality of priority queue lists, each packet flow being assigned to a priority queue list for data packets that are conforming and being assigned to a priority queue list for data packets that are not conforming with respect to the current time so that the priority queue list of a data packet can be updated when its conformance time becomes less than the current time;

assigning the data packet to the priority queue list associated with its packet flow based on whether the data packet is conforming or nonconforming with respect to the current time; and

transmitting the data packet onto the communications network in order of priority of the one or more priority queue lists.

17. A computer-readable medium as recited in claim 16 wherein the priority list processing means processes each at least one priority list completely before processing another priority list and does so in priority order.

18. A computer-readable medium as recited in claim 16 wherein a round-robin queue discipline is used for processing one of the plurality of priority queue lists.

19. A computer-readable medium as recited in claim 16 wherein a deficit round-robin queue discipline is used for processing one of the plurality of priority queue lists.

20. A computer-readable medium as recited in claim 16 wherein a conformance time sequential queue discipline is used for processing one of the plurality of priority queue lists.

21. A computer-readable medium as recited in claim 16 wherein different queue disciplines are used for processing the plurality of priority queue lists.