Integrated packet latency aware QoS scheduling algorithm using proportional fairness and weighted fair queuing for wireless integrated multimedia packet services

• US 7,489,690 B2
• Filed: 11/16/2005
• Issued: 02/10/2009
• Est. Priority Date: 08/12/2005
• Status: Active Grant

• Current Assignee: Cellco Partnership, Inc. (Verizon Communications Inc.)
• Original Assignee: Cellco Partnership, Inc. (Verizon Communications Inc.)
• Inventors: Kakadia, Deepak Kumar
• Primary Examiner(s): Appiah; Charles N
• Assistant Examiner(s): AJIBADE AKONAI, OLUMIDE
• Application Number:
  US11/274,297
• Publication Number:
  US 20070041364A1
• Time in Patent Office: 1,182 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/232, 370/237, 370351-356, 370/395.21, 370/395.41, 370/412, 370413-417, 370/418, 370/419, 370/231, 370/238, 370/254, 370/255, 370/395.4, 370/395.5, 709/217, 709/218, 709/219, 709227-229, 709/230, 709/245, 709223-226
• US Class Current: 370/395.4
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Packet communication networks for transmission to wireless subscriber devices utilize both wireline and wireless packet routing components. The routing elements of these two different types often implement different packet scheduling algorithms, typically a form of Weighted Fair Queuing (WFQ) in the wireline portion of the network and Proportional Fairness (PF) queuing in the wireless domain. To improve resource allocation and thus end to end quality of service for time sensitive communications, such as integrated multimedia services, the present disclosure suggests adding the notion of slack time into either one or both of the packet scheduling algorithms. By modifying one or more of these algorithms, e.g. to reorder or shuffle packets based on slack times, global optimal resource allocations are possible, at least in certain cases.

Claims

1. A method of scheduling packet transmissions, for use in providing packet communication service to wireless subscriber client devices through a hybrid network having a wireline portion and a wireless portion, the method comprising:

determining a time budget for delivery of each respective packet through a combination of the wireline and wireless portions of the network to each of a plurality of the wireless subscriber client devices;

recording a respective time stamp indicating time of entry into the network for each packet;

routing the packets through the wireline portion of the network to the wireless portion of the network, using a first scheduling algorithm;

routing the packets through the wireless portion of the network using a second scheduling algorithm different from the first scheduling algorithm;

with respect to a point in the wireline network or a point in the wireless network before transmission of packets over wireless link to respective wireless subscriber client devices, subtracting a difference between time of arrival of each packet at the point before transmission over wireless link and the time of entry indicated by the respective time stamp, from the time budget for the packet, to compute a slack time representing a remaining amount of the time budget for delivery of each respective packet from said point through the network to one of the wireless subscriber client devices; and

at said point, reordering at least two of the packets intended for different wireless subscriber client devices for routing in accord with at least one of the scheduling algorithms, based on the computed slack times for said at least two packets in such a manner as will allow for delivery of the packets intended for different wireless subscriber client devices before expiration of respective timing budgets.

2. The method of claim 1, wherein:

the second scheduling algorithm is a Proportional Fairness (PF) algorithm; and

the reordering reorders said at least two packets for scheduling of transmission over the wireless link in accord with the PF algorithm.

3. The method of claim 1, wherein:

the first scheduling algorithm is a Weighted Fair Queuing (WFQ) algorithm; and

the reordering reorders said at least two packets for scheduling of transmission to the wireless portion of the network in accord the WFQ algorithm.

4. The method of claim 1, wherein:

the first scheduling algorithm is a Weighted Fair Queuing (WFQ) algorithm; and

the second scheduling algorithm is a Proportional Fairness (PF) algorithm.

5. The method of claim 4, wherein:

the reordering reorders said at least two packets for scheduling of transmission to the wireless portion of the network in accord the WFQ algorithm; and

the method further comprises reordering at least two packets intended for different wireless subscriber client devices for routing in accord with the PF algorithm, based on computed slack times.

6. The method of claim 1, further comprising discarding a packet having a slack time too short to allow delivery to an intended destination wireless subscriber client device, so as to advance transmission of another packet.

7. The method of claim 1, wherein the wireless portion of the network is a 3GPP2 1xEV-DO network.

8. The method of claim 1, wherein the determining of the time budget for each respective packet comprises:

determining a communication service or application for the respective packet from among a plurality of services or applications supported through the network; and

assigning a time budget associated with the determined service or application from among a plurality of possible time budgets associated with respective services or applications supported through the network.

9. A network for providing wireless service for wireless subscriber client devices, comprising:

a wireline portion, including at least one wireline packet routing element having an associated first packet transmission scheduler function for scheduling transmissions of packets from the wireline packet routing element, the first scheduler function utilizing a first scheduling algorithm;

a wireless portion for receiving packets from the wireline portion and transmitting received packets over one or more air links to the wireless subscriber client devices, the wireless portion including a wireless packet transmission element having an associated second packet scheduler function for scheduling the received packets for transmissions over the one or more air links, the second scheduler function utilizing a second scheduling algorithm different from the first scheduling algorithm; and

a packet monitor system for monitoring flows of packets through the network, wherein the packet monitor system;

records a respective time stamp indicating time of entry into the network for each packet;

determines a time budget for delivery of each respective packet through a combination of the wireline and wireless portions of the network to each of a plurality of the wireless subscriber client devices;

with respect to one of the transmission elements, determines a remaining slack time for delivery of each respective packet representing a remaining amount of the time budget for delivery of the packet, by subtracting a difference between time of arrival of each packet at the one transmission element and the time of entry indicated by the respective time stamp, from the time budget for the packet; and

instructs the scheduler function associated with the one transmission element to reorder at least two of the packets intended for routing through the one transmission element and delivery to different wireless subscriber client devices, to avoid an expiration of the slack time for delivery of one of the at least two packets, based on the computed slack times for said at least two packets.

10. The network of claim 9, wherein:

the second scheduling algorithm is a Proportional Fairness (PF) algorithm; and

the packet monitor instructs the second scheduler function to reorder packets to avoid an expiration of the slack time for delivery of one of the packets.

11. The network of claim 9, wherein:

the first scheduling algorithm is a Weighted Fair Queuing (WFQ) algorithm; and

the packet monitor instructs the first scheduler function to reorder packets to avoid an expiration of the slack time for delivery of one of the packets.

12. The network of claim 9, wherein:

the first scheduling algorithm is a Weighted Fair Queuing (WFQ) algorithm; and

the second scheduling algorithm is a Proportional Fairness (PF) algorithm.

13. The network of claim 9, wherein the wireless portion of the network comprises a 3GPP2 1xEV-DO network.

14. The network of claim 13, wherein:

the wireless portion comprises a Base Transmitter Station (BTS); and

the at least one packet transmission element comprises a Data Optimized Module (DOM) in the BTS.

15. The network of claim 14, wherein:

a radio network controller (RNC) interfaces the wireline portion to the wireless portion; and

the at least one packet routing element is implemented in or associated with the RNC.

16. The network of claim 9, wherein the packet monitor system comprises:

a first monitor appliance associated with the wireline packet routing element; and

a second monitor appliance associated with the wireless packet transmission element.

17. The network of claim 16, wherein:

the first monitor appliance generates the time stamp for each respective packet flowing through the wireline packet routing element, indicating time of entry into the network for the respective packet; and

the second monitor appliance computes the remaining slack time for each respective packet upon arrival of the respective packet at the wireless packet transmission element.

18. A method of scheduling packet transmissions, for use in providing packet communication service to wireless subscriber client devices through a hybrid network having a wireline portion and a wireless portion, the method comprising:

determining a time budget for delivery of each respective packet through a combination of the wireline and wireless portions of the network to each of a plurality of the wireless subscriber client devices, by;

determining a communication service or application for the respective packet from among a plurality of services or applications supported through the network; and

assigning a time budget associated with the determined service or application from among a plurality of possible time budgets associated with respective services or applications supported through the network as the time budget for delivery of the respective packet through network;

routing the packets through the wireline portion of the network to the wireless portion of the network, using a first scheduling algorithm;

routing the packets through the wireless portion of the network using a second scheduling algorithm different from the first scheduling algorithm; and

at a point in the wireline network or a point in the wireless network before transmission of packets over wireless link to respective wireless subscriber client devices;

computing a slack time representing a remaining amount of the time budget for delivery of each respective packet; and

reordering at least two of the packets intended for different wireless subscriber client devices for routing in accord with at least one of the scheduling algorithms, based on the computed slack times for said at least two packets in such a manner as will allow for delivery of the packets intended for different wireless subscriber client devices before expiration of respective timing budgets.