Multiplexing and congestion control

• US 9,866,441 B2
• Filed: 05/11/2012
• Issued: 01/09/2018
• 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.
• Primary Examiner(s): LEE, BRYAN Y
• Application Number:
  US13/469,131
• Publication Number:
  US 20120281535A1
• Time in Patent Office: 2,069 Days
• Field of Search: 709235
• 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:

obtaining parameters of the network at a network management server;

modeling traffic for a group of flows in the network based on the parameters to generate a model of the traffic including model flows, the modeling being performed by the network management server;

controlling an operational condition of the network to manage the traffic congestion in accordance with the model by generating traffic instructions at the network management server for combining selected flows of the group of flows based on the model flows, a probability of traffic, available bandwidth and a predicted bandwidth, and based on a congestion factor, wherein the congestion factor is a policy parameter for how close to full capacity a channel is to be loaded; and

adding priority information into the selected flows to indicate a priority of transmitting to be followed by network devices, wherein the priority information causes a network device to delay transmission of a first packet from a combined traffic flow and causes the network device to queue the first packet behind a second packet of the combined traffic flow.

2. The method of claim 1, comprising reducing packet processing overhead by reducing a number of packets having control information to be analyzed, wherein reducing of the packet processing overhead includes aggregating independent packets of the group of flows during the combining of the selected flows, wherein the modeling of the traffic is based on utilizing Fourier transforms.

3. The method of claim 2, wherein the control information includes address information and quality of service information.

4. The method of claim 1, comprising transmitting the traffic instructions from the network management servers to one or more network elements for adjusting routing to combine the selected flows, wherein the selected flows are limited to a same layer of the network.

5. The method of claim 1, further comprising estimating the model flows utilizing an estimation process selected from the group consisting of ad hoc determination, sampling, feedback controls, or combinations thereof.

6. The method of claim 1, wherein the modeling of the traffic is based on probability waves, wherein a height of each of the probability waves at time t is equal to the probability of traffic, P(t) at the time t, and wherein the selected flows are chosen based on the corresponding probability waves of the selected flows when combined approximating a square wave.

7. The method of claim 6, wherein the combining of the selected flows is based on using a formula B′

=Σ

BP_i(t)≦

B(1−

ε

), where ε

is the congestion factor, wherein a probability wave of flow i is P_i(t), wherein B is the available bandwidth, and wherein B′

is a predicted bandwidth.

8. The method of claim 1, further comprising:

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, wherein the probability of traffic can be greater than 1, corresponding to a defined overbooking level.

9. The method of claim 1, wherein the combining of the selected flows comprises selecting flows of the group of flows to avoid beat frequencies.

10. A server for managing traffic congestion in a network, the server comprising:

a memory storing computer instructions; and

a processor in communication with the memory, wherein the processor, responsive to executing the computer instructions performs operations comprising;

modeling traffic for a group of flows in the network based on parameters of the network to generate a model of the traffic including model flows;

generating traffic instructions to manage the traffic congestion in accordance with the model,

wherein the traffic instructions include combining selected flows of the group of flows based on the model flows, a probability of traffic, available bandwidth and a predicted bandwidth, and based on a congestion factor, wherein the congestion factor is a policy parameter for how close to full capacity a channel is to be loaded, and

wherein the traffic instructions include aggregating independent packets of the group of flows during the combining of the selected flows thereby reducing packet processing overhead by reducing a number of packets having control information to be analyzed; and

adding priority information into the selected flows to indicate a priority of transmitting to be followed by network devices, wherein the priority information causes a network device to delay transmission of a first packet from a combined traffic flow and causes the network device to queue the first packet behind a second packet of the combined traffic flow.

11. The server of claim 10, wherein the modeling of the traffic is based on utilizing Fourier transforms.

12. The server of claim 10, wherein the processor, responsive to executing the computer instructions performs operations comprising:

transmitting the traffic instructions to one or more network elements for the combining of the selected flows and for the aggregating of the independent packets.

13. The server of claim 10, wherein the combining of the selected flows comprises selecting flows of the group of flows having a same wavelength or harmonics of the same wavelength.

14. The server of claim 10, wherein the modeling of the traffic is based on probability waves, wherein a height of each of the probability waves at time t is equal to the probability of traffic, P(t) at the time t, and wherein the selected flows are chosen based on the corresponding probability waves of the selected flows when combined approximating a square wave.

15. The server of claim 14, wherein the combining of the selected flows is based on using a formula B′

=Σ

BP_i(t)≦

B(1−

ε

), where ε

is the congestion factor, wherein a probability wave of flow i is P_i(t), wherein B is the available bandwidth, and wherein B′

is a predicted bandwidth.

16. A non-transitory computer-readable storage medium comprising computer instructions, which, responsive to being executed by a processor of a network management server, cause the processor to perform operations comprising:

obtaining parameters of the network;

modeling traffic for a group of flows in the network based on the parameters to generate a model of the traffic including model flows;

controlling an operational condition of the network to manage the traffic congestion in accordance with the model by generating traffic instructions at the network management server for combining selected flows of the group of flows based on the model flows, a probability of traffic, available bandwidth and a predicted bandwidth, and based on a congestion factor, wherein the congestion factor is a policy parameter for how close to full capacity a channel is to be loaded; and

adding priority information into the selected flows to indicate a priority of transmitting to be followed by network devices, wherein the priority information causes a network device to delay transmission of a first packet from a combined traffic flow and causes the network device to queue the first packet behind a second packet of the combined traffic flow.

17. The non-transitory computer-readable storage medium of claim 16, wherein the generating of the model traffic flows is based on utilizing Fourier transforms.

18. The non-transitory computer-readable storage medium of claim 16, wherein the combining of the selected flows comprises at least one of:

selecting flows of the group of flows having a same wavelength or harmonics of the same wavelength, or selecting flows of the group of flows to avoid beat frequencies.