Mutiplexing and congestion control

• US 20090089449A1
• Filed: 03/05/2004
• Published: 04/02/2009
• Est. Priority Date: 03/07/2003
• Status: Active Grant

• Current Assignee: TRIA Network Systems, LLC
• Original Assignee: TRIA Network Systems, LLC
• Inventors: Day, John D.
• Granted Patent: US 8,180,918 B2
• Time in Patent Office: Days
• US Class Current: 709/235
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/5025 by proactively reacting to service quality change, e.g. by reconfiguration after service quality degradation or upgrade
• 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 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04L 61/5061 Pools of addresses
• CPC Class Codes: H04L 61/5084 Providing for device mobility network addressing or numbering for mobility support in wireless networks H04W8/26; mobile IP H04W80/04
• CPC Class Codes: H04L 65/1069 Session establishment or de-establishment
• CPC Class Codes: H04L 65/765 intermediate
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/565 : Conversion or adaptation of application format or content adding application control or application functional data H04L67/561
• CPC Class Codes: H04L 69/06 : Notations for structuring of protocol data, e.g. abstract syntax notation one [ASN.1]
• CPC Class Codes: H04L 69/08 : Protocols for interworking; Protocol conversion
• CPC Class Codes: H04L 69/24 : Negotiation of communication capabilities
• CPC Class Codes: H04L 69/32 : Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 69/325 : in the network layer [OSI layer 3], e.g. X.25 H04L69/16 takes precedence
• CPC Class Codes: H04L 69/329 : in the application layer [OSI layer 7]
• CPC Class Codes: H04Q 3/0054 : Service creation techniques
• CPC Class Codes: H04Q 3/0095 : Specification, development or application of network management software, e.g. software re-use
• CPC Class Codes: H04W 40/248 : Connectivity information update
• CPC Class Codes: H04W 8/087 : for preserving data network PoA address despite hand-offs
• CPC Class Codes: H04W 8/26 : Network addressing or numbering for mobility support
• CPC Class Codes: H04W 80/04 : Network layer protocols, e.g. mobile IP [Internet Protocol]
• CPC Class Codes: H05K 999/99 : dummy group

Abstract

Methods, systems and devices for network congestion control exploit the inherent burstiness of network traffic, using a wave-based characterization of network traffic and corresponding multiplexing methods and approaches.

Claims

1. A method for managing traffic congestion in a network, the method comprising:

modeling traffic on a given flow as a probability wave, wherein the height of the wave at time t is equal to the probability of traffic, P(t) at time t, and

controlling an operational condition of the network to manage traffic congestion in accordance with the probability wave.

2. The method of claim 1 further comprising estimating the probability wave in accordance with a selected estimation method.

3. The method of claim 2 wherein the estimation method is selected from a group comprising ad hoc determination, sampling, feedback controls, or other estimation method.

4. The method of claims 1-3 further comprising:

combining selected flows to control congestion, and

selecting the flows to be combined such that the resulting combination waveforms are characterized by a relation Pa(t)+Pb(t)=X, where Pa is the probability wave for flow a, Pb is the probability wave for flow b, and X is the probability of traffic.

5. The method of claim 4 wherein the probability of traffic can be greater than 1, corresponding to a defined overbooking level.

6. The method of claim 4-5 wherein the probability waves are combined to create an approximation of a square wave.

7. The method of claim 6 wherein the combining comprises phase shifting a selected wave to meet constraints imposed by the probability of traffic and to better approximate a square wave.

8. The method of claim 6 wherein the combining comprises selecting flows to be combined having the same wavelength or harmonics of the same wavelength.

9. The method of claim 6 wherein the combining comprises selecting flows to be combined so as to avoid beat frequencies.

10. The method of claim 7 wherein phase shifting a selected wave comprises phase shifting the wave within delay constraints for a QoS defined for the respective flow.

11. The method of claims 1-10 further comprising:

applying the combining to a plurality of flows in a given layer of a network.

12. The method of claim 11 wherein the combining comprises constructing a waveform that exploits differences in bandwidth between different layers.

13. The method of claims 11 or 12 further comprising the use of flow control feedback to establish the natural frequency of the waveform for a particular subnet or layer.

14. The method of claim 13 wherein the waveform arithmetically scales as a function of differences in bandwidth between different layers.

15. The method of claim 11 further comprising combining a plurality of flows having different waveforms, onto new flows at a lower layer of the network, each with pre-determined congestion characteristics, to create a set of combined flows for providing a variety of services in accordance with selected QoS parameters.

16. The method of any of claims 11-15 wherein the combining is executed such that the flows of lower layers in the network exhibit lower uncertainty in their probability functions.

17. The method of claim 16 wherein:

each instance can operate in accordance with a set of policies and parameters over a given range of bandwidth, and

flows managed thereby operate over given ranges of QoS parameters,

whereby the method can be applied recursively with different policies and parameters over an entire range of bandwidth and QoS.

18. The method of claim 17 wherein cooperating instances of identical rank form a layer of a specific scope operable to manage flows of a given bandwidth range, specific QoS or scope of management.

19. The method of claim 18 wherein:

instances at a higher rank generally manage lower bandwidth ranges and narrower QoS, and generally have greater scope, and

instances at lower ranks generally have higher bandwidth ranges and manage flows with broader QoS and less scope.

20. The method of claim 19 wherein within a range of QoS handled by a given layer, specific flows between senders and receivers further subdivide the range of QoS.

21. The method of claim 19 wherein QoS parameters may be expressed in terms of properties of the wave.

22. The method of claim 19 wherein QoS or other information needed to engineer a network may be derived directly from the wave.

23. A system for managing traffic congestion in a network, the system comprising:

means for modeling traffic on a given flow as a probability wave, wherein the height of the wave at time t is equal to the probability of traffic, P(t) at time t, and

means, responsive to the means for modeling traffic, for controlling an operational condition of the network to manage traffic congestion in accordance with the probability wave.