Method and system for queuing traffic in a wireless communications network

• US 6,865,185 B1
• Filed: 02/25/2000
• Issued: 03/08/2005
• Est. Priority Date: 02/25/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Choksi, Ojas T., Patel, Pulin R., Patel, Achal R., Ali, Mohammad R.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Ferris, Derrick W
• Application Number:
  US09/513,912
• Time in Patent Office: 1,838 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/310, 370/332, 370/395.21, 370/395.72, 370/412
• US Class Current: 370/412
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04W 16/24 Cell structures
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 28/24 Negotiating SLA [Service Level Agreement]; Negotiating QoS [Quality of Service]
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation

Abstract

A method and system for queuing traffic in a wireless network includes receiving a stream of packets for transmission in the wireless network. Each packet includes a flow identifier and is assigned to one of the plurality of virtual groups based on the flow identifier. The virtual groups include discrete transmission resources. Each packet is queued in an assigned virtual group for transmission in the wireless network.

Claims

1. A method for queuing traffic in a wireless network, comprising:

receiving a stream of packets for transmission in a wireless network, each packet including a flow identifier uniquely identifying the flow;

determining for each packet based on the included flow identifier a location for a corresponding flow, the location comprising at least one of a sector in the wireless network, a latitude and a longitude of a mobile device associated with the flow, and a specific beam within a sector of the wireless network;

assigning each packet to one of a plurality of virtual groups based on the location for the corresponding flow, the virtual groups comprising discrete transmission resources; and

queuing each packet in an assigned virtual group for transmission in the wireless network.

2. The method of claim 1, further comprising:

determining for a packet based on the flow identifier a characteristic for the a corresponding flow, the characteristic comprising at least one of a wireless network parameter, a policy parameter for the flow, a flow parameter, and a power level for the flow; and

assigning the packet to a virtual group based on the location of the flow and the determined characteristic for the flow.

3. The method of claim 2, further comprising inserting a label indicating the virtual group.

4. The method of claim 1, further comprising:

determining for a packet based on the flow identifier a set of characteristics for a corresponding flow, the set of characteristics comprising the physical location of the flow, a wireless network parameter, a policy parameter for the flow and a flow parameter; and

assigning the packet to a virtual group based on the set of characteristics for the flow.

5. The method of claim 4, further comprising inserting a label indicating the virtual group.

6. The method of claim 4, the set of characteristics further comprising a power level for the flow.

7. The method of claim 1, further comprising inserting a label indicating the virtual group.

8. The method of claim 1, further comprising:

determining for a packet based on the flow identifier a wireless network parameter; and

assigning the packet to a virtual group based on the wireless network parameter.

9. The method of claim 8, further comprising inserting a label indicating the virtual group.

10. The method of claim 8, wherein the wireless network parameter comprises a sector layout.

11. The method of claim 8, wherein the wireless network parameter comprises a frequency plan in the wireless network.

12. The method of claim 8, wherein the wireless network parameter comprises a soft handoff percentage in the wireless network.

13. The method of claim 8, wherein the wireless network parameter comprises an interference estimate in the wireless network.

14. The method of claim 8, wherein the wireless network parameter comprises a sector power output in the wireless network.

15. The method of claim 8, wherein the wireless network parameter comprises a noise threshold in the wireless network.

16. The method of claim 1, further comprising:

determining for a packet based on the flow identifier a policy parameter for a corresponding flow; and

assigning the packet to a virtual group based on the policy parameter.

17. The method of claim 16, wherein the policy parameter comprises a service level agreement (SLA) for the flow.

18. The method of claim 16, wherein the policy parameter comprises a peak rate for the flow.

19. The method of claim 16, wherein the policy parameter comprises a subscribed rate for the flow.

20. The method of claim 16, wherein the policy parameter comprises a maximum burst rate for the flow.

21. The method of claim 16, wherein the policy parameter comprises a packet size for the flow.

22. The method of claim 16, wherein the policy parameter comprises a delay threshold for the flow.

23. The method of claim 16, further comprising:

determining for a packet based on the flow identifier a flow parameter for a corresponding flow; and

assigning the packet to a virtual group based on the flow parameter.

24. The method of claim 23, wherein the flow parameter comprises a type of the flow.

25. The method of claim 24, wherein the flow parameter comprises a data flow identifier.

26. The method of claim 23, wherein the flow parameter comprises a multi-slot/multi-code indicator for the flow.

27. The method of claim 23, wherein the flow parameter comprises a power level for the flow.

28. The method of claim 23, wherein the flow parameter comprises a multi-mode indicator for the flow.

29. The method of claim 1, further comprising modifying the existence of virtual groups based on a dynamic status of the wireless network.

30. The method of claim 1, further comprising defining the plurality of virtual groups to account for the impact of flows on the wireless network.

31. The method of claim 1, queuing the packets in the assigned virtual groups comprising queuing the packets in a common memory with a virtual group identifier for each packet.

32. The method of claim 1, the virtual groups including a plurality of class of service queues, further comprising:

determining a class of service for a packet; and

queuing the packet in a corresponding class of service queue in the assigned virtual group.

33. The method of claim 32, queuing the packets in the assigned virtual groups comprising queuing the packets in a common memory with a virtual group identifier and a class of service identifier.

34. The method of claim 32, wherein each class of service queue comprises a first in first out (FIFO) queue.

35. The method of claim 1, further comprising individually metering packets in a virtual group to demote packets in excess of corresponding flow policies.

36. The method of claim 1, further comprising dynamically controlling congestion in a virtual group based on available bandwidth for the virtual group in the wireless network.

37. The method of claim 1, further comprising:

receiving an indication of available bandwidth for a virtual group;

generating congestion control parameters for the virtual group based on the indication of available bandwidth; and

dropping packets from flows in the virtual group based on the congestion control parameters.

38. The method of claim 37, further comprising generating the indication of available bandwidth based on air-resource estimates.

39. The method of claim 37, further comprising generating the indication of available bandwidth based on pricing strategy information.

40. The method of claim 37, further comprising generating the indication of available bandwidth based on historical usage information.

41. The method of claim 1, at least one virtual group including a plurality of class of service queues, further comprising individually controlling congestion for each of the class of service queues in the virtual group based on a dynamic status of the wireless network.

42. The method of claim 1, further comprising:

assigning a packet for a corresponding flow in a first location to a first virtual group associated with the first location; and

in response to the flow device moving from the first location to a second location, assigning a subsequent packet for the flow to a second virtual group associated with the second location.

43. The method of claim 42, further comprising requeuing the packet in the first virtual group into the second virtual group based on an original queuing time for the packet.

44. A system for queuing traffic in a wireless network, comprising:

a dynamic flow manager operable to receive a stream of packets for transmission in a wireless network, each packet including a flow identifier uniquely identifying the flow, to determine for each packet based on the included flow identifier a location for a corresponding flow, wherein the location comprises at least one of a sector in the wireless network, a latitude and a longitude of a mobile device associated with the flow, and a specific beam within a sector of the wireless network, and to assign each packet to one of a plurality of virtual groups based on the location for the corresponding flow; and

the virtual groups comprising discrete transmission resources each operable to queue assigned packets for transmission in the wireless network.

45. The system of claim 44, the dynamic flow manager further operable to determine for a packet based on the flow identifier a characteristic for a the corresponding flow, the characteristic comprising at least one of a location of the flow, a wireless network parameter, a policy parameter for the flow, a flow parameter, and a power level for the flow, and to assign the packet to a virtual group based on the location of the flow and the determined characteristic for the flow.

46. The system of claim 45, the dynamic flow manager further operable to insert a label indicating the virtual group.

47. The system of claim 44, the dynamic flow manager further operable to determine for a packet based on a flow identifier a set of characteristics for a corresponding flow, the set of characteristics comprising the physical location of the flow, a wireless network parameter, a policy parameter for the flow, and a flow parameter, and to assign the packet to a virtual group based on the set of characteristics for the flow.

48. The system of claim 47, the dynamic flow manager further operable to insert a label indicating the virtual group.

49. The system of claim 47, the set of characteristics comprising a power level for the flow.

50. The system of claim 44, the dynamic flow manager further operable to insert a label indicating the virtual group.

51. The system of claim 44, further comprising software stored on a computer-readable medium, the software comprising the dynamic flow manager and operable to implement the virtual groups.

52. The system of claim 44, further comprising a preconfigured processor operable to implement the dynamic flow manager and the virtual groups.

53. The system of claim 44, the dynamic flow manager further operable to determine for a packet based on the flow identifier a wireless network parameter and to assign the packet to a virtual group based on the wireless network parameter.

54. The system of claim 53, the dynamic flow manager further operable to insert a label indicating the virtual group.

55. The system of claim 53, wherein the wireless network parameter comprises a sector layout.

56. The system of claim 53, wherein the wireless network parameter comprises one of a frequency plan and a frequency group in the wireless network.

57. The system of claim 53, wherein the wireless network parameter comprises one of a soft handoff percentage and a soft handoff region in the wireless network.

58. The system of claim 53, wherein the wireless network parameter comprises an interference estimate in the wireless network.

59. The system of claim 53, wherein the wireless network parameter comprises a sector power output in the wireless network.

60. The system of claim 53, wherein the wireless network parameter comprises a noise threshold in the wireless network.

61. The system of claim 44, the dynamic flow manager further operable to determine for a packet based on the flow identifier a policy parameter for a corresponding flow and to assign the packet to a virtual group based on the policy parameter.

62. The system of claim 61, wherein the policy parameter comprises a service level agreement (SLA) for the flow.

63. The system of claim 61, wherein the policy parameter comprises a peak rate for the flow.

64. The system of claim 61, wherein the policy parameter comprises a subscribed rate for the flow.

65. The system of claim 61, wherein the policy parameter comprises a maximum burst rate for the flow.

66. The system of claim 61, wherein the policy parameter comprises a packet size for the flow.

67. The system of claim 61, wherein the policy parameter comprises a delay threshold for the flow.

68. The system of claim 44, the dynamic flow manager further operable to determine for a packet based on the flow identifier a flow parameter for a corresponding flow and to assign the packet to a virtual group based on the flow parameter.

69. The system of claim 68, wherein the flow parameter comprises a type of the flow.

70. The system of claim 68, wherein the flow parameter comprises a data flow identifier.

71. The system of claim 68, wherein the flow parameter comprises a multi-slot/multi-mode for the flow.

72. The system of claim 68, wherein the flow parameter comprises a power level for the flow.

73. The system of claim 68, wherein the flow parameter comprises a multi-mode indicator for the flow.

74. The system of claim 44, the dynamic flow manager further operable to modify the existence of virtual groups based on a dynamic status of the wireless network.

75. The system of claim 44, the dynamic flow manager further operable to define the plurality of virtual groups to account for the impact of flows on the wireless network.

76. The system of claim 44, the virtual groups operable to queue the packets in assigned virtual groups by queuing the packets in a common memory with a virtual group identifier for each packet.

77. The system of claim 44, the virtual groups including a plurality of class of service queues, the virtual groups further operable to determine a class of service for a packet and to queue the packet in a corresponding class of service queue in the assigned virtual group.

78. The system of claim 77, the virtual groups further operable to queue the packets in the assigned virtual groups by queuing the packets in a common memory with a virtual group identifier and a class of service identifier.

79. The system of claim 77, wherein each class of service queue comprises a first in first out (FIFO) queue.

80. The system of claim 44, the virtual groups operable to individually meter packets and to demote packets in excess of corresponding flow policies.

81. The system of claim 44, each virtual group operable to dynamically control congestion in the virtual group based on available bandwidth for the virtual group in the wireless network.

82. The system of claim 44, each virtual group operable to receive an indication of available bandwidth for the virtual group, to generate congestion control parameters for the virtual group based on the indication of available bandwidth and to drop packets from flows in the virtual group based on the congestion control parameters.

83. The system of claim 82, further comprising a dynamic bandwidth estimator operable to generate the indication of available bandwidth based on air-resource estimates.

84. The system of claim 82, further comprising a dynamic bandwidth estimator operable to generate the indication of available bandwidth based on pricing strategy information.

85. The system of claim 82, further comprising a dynamic bandwidth estimator operable to generate the indication of available bandwidth based on historical usage information.

86. The system of claim 44, wherein at least one virtual group includes a plurality of class of service queues, each virtual group further operable to individually control congestion for each of the class of service queues in the virtual group based on a dynamic status of the wireless network.

87. The system of claim 44, the dynamic flow manager further operable to assign a packet for a corresponding flow in a first location to a first virtual group associated with the first location and in response to the flow moving from the first location to a second location to assign a subsequent packet for the flow to a second virtual group associated with the second location.

88. The system of claim 87, further comprising a mobility manager operable to requeue the packet in the first virtual group into the second virtual group based on original queuing time for the packet.

89. A peripheral card for a mobile gateway, comprising:

an external interface operable to receive a stream of packets for transmission in a wireless network, each packet including a flow identifier uniquely identifying the flow;

a dynamic flow manager operable to determine for each packet based on the included flow identifier a location for a corresponding flow, wherein the location comprises at least one of a sector in the wireless network, a latitude and a longitude of a mobile device associated with the flow, and a specific beam within a sector of the wireless network, to assign each packet to one of a plurality of virtual groups based on the location for the corresponding flow, the virtual groups comprising discreet transmission resources; and

an internal interface operable to forward the packets to the assigned virtual groups for queuing.

90. The peripheral card of claim 89, the dynamic flow manager further operable to add a virtual group label to each packet identifying the assigned virtual group.

91. The peripheral card of claim 89, further comprising a dynamic bandwidth estimator operable to generate an indication of available bandwidth for each of the virtual groups.