Embodiments relate to allocation of network capacity to a plurality of service flow types, and more particularly, to a multi-level allocation of the network capacity.

BACKGROUND

The need to transmit an amount of data that exceeds a network's capacity may require the data to be prioritized. Thus, some data may be transmitted within the available network capacity while other data may be buffered and/or otherwise delayed. Existing systems provide predefined limits on a subscriber's traffic. For example, attributes of a paid subscription plan may define what predefined limits are used when allocating network capacity. During periods of congestion, adaptive queue management may be used to discard packets until network load more closely matches a network's capacity.

However, these methods often result in a poor user experience. Therefore, improved methods of managing network congestion are required.

BRIEF SUMMARY

The systems, methods, and devices described herein each have several aspects, no single one of which is solely responsible for its desirable attributes. Without limiting the scope of the invention(s) as expressed by the claims which follow, some features will now be discussed briefly. After considering this discussion, and particularly after reading the section entitled “Detailed Description” one will understand how the disclosed examples provide advantages that include improved allocation of available network capacity across a plurality of service flows. In some aspects, the allocation of available network capacity may be performed in multiple cycles. For example, first, a minimum amount specific to each service flow type may be allocated to each service flow during a first allocation cycle. This ensures each service flow receives its minimum allocation during the allocation cycle. The minimum commitment to each service flow may vary across service flows. For example, high priority service flows may receive a larger minimum commitment than lower priority service flows.

After the minimum commitment to each service flow is satisfied, variable amounts of allocation may be provided to each service flow in multiple phases. During each progressive phase, a proportion allocated to each service flow may vary. For example, in a first progressive phase, a first service flow may receive a first amount of data and a second service flow may receive half the first amount of data. In a second progressive phase, the first service flow may receive a second amount of data, and the second service flow may receive a third of the second amount of data.

The disclosed methods and systems provide for network capacity allocations for service flow types that may preferentially slow down certain service flow types as congestion increases. For example, in some embodiments, video flows may be slowed before web-data flows. This policy is based on the realization that modern video streams use adaptive coding and can adapt the video quality to a wide range of data rates. As congestion increases, the policies can control the relative allocated data rates between different flows. e.g., web-data flows get 2× the rate of video flows, irrespective of the number of flows of each type.

The disclosed methods and systems provide for polices that provide a higher level of service to certain subscriber types and packages over other. These methods and systems also provide for policies that provide low level of service to certain subscriber types and packages during congestion, but high level of service when congestion abates.

In some aspects, meta-policies may automatically adapt policy parameters. For example, a subscriber traffic policy can be changed dynamically during congestion based on its recent usage—e.g., a high recent usage can be used to demote a subscriber's policy relative to others, thereby preferentially slowing down large file downloads. Similarly, long term usage can be used to demote a subscriber's policy, thereby improving experience for users that use the system within their usage limits.

In some implementations, separate queues are provided for each subscriber and for each subscriber traffic class. A single scheduler operates periodically (as opposed to continuously as may be done by traditional schedulers). The scheduler computes allocations across thousands of queues, each with its own set of traffic rate parameters (defining network capacity allocations within cycles of the scheduler) with the multi-level allocations of network capacity resulting in a multi-step allocation graph for each flow, an example of which is discussed below with respect toFIG.1.

The disclosed methods and systems are very flexible and can be used to create additional novel allocation policies. For example, groups of subscribers can be formed, with aggregate allocations to each group controlled by a set of policies similar to individual subscriber policies. The disclosed methods and systems are scalable to handle traffic with large number of subscribers and high aggregate data rates.

One aspect disclosed is a method of allocating network capacity over a communication channel of a network. The method includes determining a transmission profile for each of a plurality of service flow types, each transmission profile defining at least three different network capacity allocation parameters for a set of at least three different ordered network capacity allocation cycles. The method includes iteratively performing, for each of the at least three ordered network capacity allocation cycles: selecting, for each service flow type, the network capacity allocation parameters in each service flow type's transmission profile associated with a current network capacity allocation cycle of the at least three ordered network capacity allocation cycles; determining amounts of data to transmit for each of the plurality of service flow types based, at least in part, on the selected network capacity allocation parameters for the current network capacity allocation cycle; and transmitting over the communication channel, the determined amounts for each of the plurality of service flow types for the current network capacity allocation cycle.

In some aspects, the method also includes determining a total allocation for a particular allocation cycle based on a summation of network capacity allocation parameters corresponding to the particular allocation cycle for the plurality of service flow types, determining a remaining network capacity for the particular allocation cycle based on previous allocation cycles; and allocating the remaining network capacity based on the network capacity allocation parameters corresponding to the particular allocation cycle and network capacity allocation parameters corresponding to a previous allocation cycle in response to the remaining network capacity being less than the total allocation for the particular allocation cycle; and allocating the remaining network capacity based on the network capacity allocation parameters corresponding to the particular allocation cycle in response to the remaining network capacity being greater than or equal to the total allocation for the particular allocation cycle.

In some aspects, the method includes in response to the remaining network capacity being less than the total allocation for the particular allocation cycle, summing, for each service flow, the service flow's network capacity allocation parameters for the particular allocation cycle and network capacity allocation parameters corresponding to the previous allocation cycle; and allocating the remaining network capacity to each service flow in proportion to the sums for each service flow.

In some aspects, the method includes receiving data for transmission, determining a transmission data type of the received data based on one or more of: a source service access point, a destination service access point, and a classification of a payload of the data, and associating the received data with a service flow type based on the transmission data type.

In some aspects, the method includes classifying protocol headers to determine the classification of the transmission data type. In some aspects, the method also includes classifying the transmission data type into at least one of bursty, video, file download, and VoIP. In some aspects, the method also includes allocating network capacity during a first time period based on the set of network capacity allocation cycles; and allocating network capacity during a non-overlapping second time period based on a second set of network capacity allocation cycles. In some aspects, the method also includes iteratively performing, for each of the at least three ordered network capacity allocation cycles: allocating the determined amounts of data to transmit for each of the plurality of service flow type to a plurality of user terminals based on allocation parameters associated with each of the plurality of user terminals.

In some aspects, the method also includes determining a user terminal profile for each of the plurality of user terminals, each user terminal profile defining at least three different allocation parameters for user terminal data associated with a service flow type, the at least three different allocation parameters associated with at least three different ordered network capacity allocation cycles respectively; and iteratively performing, for each of the at least three ordered network capacity allocation cycles: allocating a portion of a determined amount for a service flow type to a user terminal based at least in part on the allocation parameter defined by the determined user terminal profile for the user terminal corresponding to the current network capacity allocation cycle, wherein the transmitting of the determined amounts for each of the plurality of service flow types for the current network capacity allocation cycle includes transmitting the allocated portion for the user terminal.

Another aspect disclosed is an apparatus for allocating network capacity over a communication channel of a network. The apparatus includes an electronic hardware processor, an electronic hardware memory, operably coupled to the electronic hardware processor, and storing instructions that when executed cause the electronic hardware processor to perform a method of allocating network capacity over a communication channel of a network. The electronic hardware processor is configured to determine a transmission profile for each of a plurality of service flow types, each transmission profile defining at least three different network capacity allocation parameters for a set of at least three different ordered network capacity allocation cycles, iteratively performing, for each of the at least three ordered network capacity allocation cycles: selecting, for each service flow type, the network capacity allocation parameters in each service flow type's transmission profile associated with a current network capacity allocation cycle of the at least three ordered network capacity allocation cycles, determining amounts of data to transmit for each of the plurality of service flow types based, at least in part, on the selected network capacity allocation parameters for the current network capacity allocation cycle, and transmitting over the communication channel, the determined amounts for each of the plurality of service flow types for the current network capacity allocation cycle.

In some aspects, the electronic hardware memory stores further instructions that when executed cause the electronic hardware processor to: determine a total allocation for a particular allocation cycle based on a summation of network capacity allocation parameters corresponding to the particular allocation cycle for the plurality of service flow types, determine a remaining network capacity for the particular allocation cycle based on previous allocation cycles, allocate the remaining network capacity based on the network capacity allocation parameters corresponding to the particular allocation cycle and network capacity allocation parameters corresponding to a previous allocation cycle in response to the remaining network capacity being less than the total allocation for the particular allocation cycle, and allocate the remaining network capacity based on the network capacity allocation parameters corresponding to the particular allocation cycle in response to the remaining network capacity being greater than or equal to the total allocation for the particular allocation cycle.

In some aspects of the apparatus, the electronic hardware memory stores further instructions that when executed cause the electronic hardware processor to in response to the remaining network capacity being less than the total allocation for the particular allocation cycle: summing, for each service flow, the service flow's network capacity allocation parameters for the particular allocation cycle and network capacity allocation parameters corresponding to the previous allocation cycle; and allocating the remaining network capacity to each service flow in proportion to the sums for each service flow.

In some aspects of the apparatus, the electronic hardware memory stores further instructions that when executed cause the electronic hardware processor to receive data for transmission, determine a transmission data type of the received data based on one or more of: a source service access point, a destination service access point, and a classification of a payload of the data; and associate the received data with a service flow type based on the transmission data type.

In some aspects of the apparatus, the electronic hardware memory stores further instructions that when executed cause the electronic hardware processor to classify protocol headers to determine the classification of the transmission data type. In some aspects, the electronic hardware memory stores further instructions that when executed cause the electronic hardware processor to classify the transmission data type into at least one of bursty, video, file download, and VoIP.

In some aspects, the electronic hardware memory stores further instructions that when executed cause the electronic hardware processor to allocate network capacity during a first time period based on the set of network capacity allocation cycles; and allocate network capacity during a non-overlapping second time period based on a second set of network capacity allocation cycles. In some aspects, the electronic hardware memory stores further instructions that when executed cause the electronic hardware processor to for each of the at least three ordered network capacity allocation cycles: allocate the determined amounts of data to transmit for each of the plurality of service flow type to a plurality of user terminals based on allocation parameters associated with each of the plurality of user terminals.

In some aspects of the apparatus, the electronic hardware memory stores further instructions that when executed cause the electronic hardware processor to determine a user terminal profile for each of the plurality of user terminals, each user terminal profile defining at least three different allocation parameters for user terminal data associated with a service flow type, the at least three different allocation parameters associated with at least three different ordered network capacity allocation cycles respectively, and iteratively perform, for each of the at least three ordered network capacity allocation cycles: allocate a portion of a determined amount for a service flow type to a user terminal based at least in part on the allocation parameter defined by the determined user terminal profile for the user terminal corresponding to the current network capacity allocation cycle. In these aspects, the transmitting of the determined amounts for each of the plurality of service flow types for the current network capacity allocation cycle includes transmitting the allocated portion for the user terminal.

Another aspect disclosed is an apparatus for allocating network capacity over a communication channel of a network. The apparatus includes means for allocating different proportions of available network capacity to a plurality of service flow types during each of at least three ordered network capacity allocation cycles; and means for transmitting data comprising the plurality of service flow types according to the allocations. In some aspects, the means for allocating different proportions of available network capacity is configured to determining a transmission profile for each of the plurality of service flow types, each transmission profile defining at least three different network capacity allocation parameters for the at least three different ordered network capacity allocation cycles, and allocate the different proportions in accordance with the determined transmission profiles. In some of these aspects, the means for allocating different proportions of available network capacity is further configured to select, for each service flow type, the network capacity allocation parameters in each service flow type's transmission profile associated with a current network capacity allocation cycle of the at least three ordered network capacity allocation cycles, and determine amounts of data to transmit for each of the plurality of service flow types based, at least in part, on the selected network capacity allocation parameters for the current network capacity allocation cycle. In some aspects of this apparatus, the means for allocating different proportions of available network capacity is further configured to transmit over the communication channel, the determined amounts for each of the plurality of service flow types for the current network capacity allocation cycle. In some of these aspects, the means for allocating different proportions of available network capacity is further configured to determine a total allocation for a particular allocation cycle based on a summation of network capacity allocation parameters corresponding to the particular allocation cycle for the plurality of service flow types, determine a remaining network capacity for the particular allocation cycle based on previous allocation cycles, allocate the remaining network capacity based on the network capacity allocation parameters corresponding to the particular allocation cycle and network capacity allocation parameters corresponding to a previous allocation cycle in response to the remaining network capacity being less than the total allocation for the particular allocation cycle, and allocate the remaining network capacity based on the network capacity allocation parameters corresponding to the particular allocation cycle in response to the remaining network capacity being greater than or equal to the total allocation for the particular allocation cycle.

In some aspects of the apparatus, the means for allocating different proportions of available network capacity is further configured to in response to the remaining network capacity being less than the total allocation for the particular allocation cycle: sum each service flow's network capacity allocation parameters for the particular allocation cycle and network capacity allocation parameters corresponding to the previous allocation cycle, and allocate the remaining network capacity to each service flow in proportion to the sums for each service flow. In some aspects of the apparatus, the means for allocating different proportions of available network capacity is further configured to receive data for transmission, determine a transmission data type of the received data based on one or more of: a source service access point, a destination service access point, and a classification of a payload of the data, and associate the received data with a service flow type based on the transmission data type.

In some aspects of the apparatus, the means for allocating different proportions of available network capacity is further configured to classify protocol headers to determine the transmission data type. In some aspects, the means for allocating different proportions of available network capacity is further configured to classify the transmission data type into at least one of bursty, video, file download, and VoIP. In some aspects, the means for allocating different proportions of available network capacity is further configured to: allocate different proportions of available network capacity during a first time period based on the at least three network capacity allocation cycles; and allocate network capacity during a non-overlapping second time period based on a second set of at least three network capacity allocation cycles.

Another aspect disclosed is a non-transitory computer readable medium comprising instructions that when executed cause a processor to perform a method of allocating network capacity over a communication channel of a network, the method comprising: determining a transmission profile for each of a plurality of service flow types, each transmission profile defining at least three different network capacity allocation parameters for a set of at least three different ordered network capacity allocation cycles; iteratively performing, for each of the at least three ordered network capacity allocation cycles: selecting, for each service flow type, the network capacity allocation parameters in each service flow type's transmission profile associated with a current network capacity allocation cycle of the at least three ordered network capacity allocation cycles, determining amounts of data to transmit for each of the plurality of service flow types based, at least in part, on the selected network capacity allocation parameters for the current network capacity allocation cycle, and transmitting over the communication channel, the determined amounts for each of the plurality of service flow types for the current network capacity allocation cycle.

