Bandwidth allocation

In certain embodiments, a method for bandwidth allocation includes receiving at least a first traffic flow and a second traffic flow, each traffic flow including at least committed information rate (CIR) and excess information rate (EIR) parameters. The CIR parameter in each traffic flow is associated with a corresponding guaranteed pass-through rate. The first traffic flow and the second traffic flow are stored in first and second queues, respectively. The first queue is associated with a first provisioned weight, and the second queue is associated with a second provisioned weight. The method further includes scheduling downstream transmission of the first traffic flow and second traffic flow stored in the first and second queues according to at least first and second implementation weights that are determined based on a bandwidth of a downstream communication link, a CIR parameter of the first queue, a CIR parameter of the second queue, and each of the first and second provisioned weights.

TECHNICAL FIELD

The present invention relates generally to communication systems and more particularly to bandwidth allocation.

BACKGROUND

Communication networks may bottleneck at a point in the network that receives more traffic than it can pass. In other words, at that point in the network, there is not sufficient downstream bandwidth to pass all of the traffic at once. In such cases, a decision must be made as to the manner in which bandwidth will be allocated among various incoming traffic flows. Typical systems do not provide a robust bandwidth allocation solution for allocating bandwidth among the various incoming traffic flows.

SUMMARY

According to the present invention, disadvantages and problems associated with previous techniques for bandwidth allocation may be reduced or eliminated.

In certain embodiments, a method for bandwidth allocation includes receiving at least a first traffic flow and a second traffic flow, each traffic flow including at least committed information rate (CIR) and excess information rate (EIR) parameters. The CIR parameter in each traffic flow is associated with a corresponding guaranteed pass-through rate. The first traffic flow and the second traffic flow are stored in first and second queues, respectively. The first queue is associated with a first provisioned weight, and the second queue is associated with a second provisioned weight. The method further includes scheduling downstream transmission of the first traffic flow and second traffic flow stored in the first and second queues according to at least first and second implementation weights that are determined based on a bandwidth of a downstream communication link, a CIR parameter of the first queue, a CIR parameter of the second queue, and each of the first and second provisioned weights.

In certain embodiments, a method for allocating bandwidth includes accessing a corresponding CIR parameter for each of two or more weighted scheduling queues, the CIR parameter for a queue associated with a guaranteed pass-through rate. The method further includes accessing a corresponding EIR parameter for each of the two or more weighted scheduling queues, each weighted scheduling queue associated with a corresponding provisioned weight. The method further includes determining corresponding implementation weights for each of the two or more weighted scheduling queues. The implementation weights are for scheduling traffic stored in the two or more weighted scheduling queues for communication over a communication link and are determined according to a bandwidth of a communication link, each of the corresponding CIR parameters, and each of the corresponding provisioned weights.

Particular embodiments of the present invention may provide one or more technical advantages. Conventional techniques for scheduling traffic stored in weighted scheduling queues only address scheduling EIR traffic according to provisioned weights pre-assigned to the weighted scheduling queues. However, among other possible deficiencies, scheduling traffic stored in the weighted scheduling queues merely according to the provisioned weights may not allow CIRs to be guaranteed for the weighted scheduling queues. In certain embodiments, the present invention provides algorithms and mechanisms that can schedule multiple weighted scheduling queues with CIRs and EIRs, using determined implementation weights. In certain embodiments, scheduling traffic from queues according to the determined implementation weights may allow the CIRs of traffic flows to be satisfied, as well as the weighted throughput for the EIR traffic.

According to certain embodiments of the present invention, a network operator may be able to provide greater options for users communicating over its network. Typical systems do not offer users guaranteed throughput rates (i.e., CIRs). In certain embodiments, a network operator may offer users guaranteed throughput rates (CIRs), best effort traffic rates (EIRs), or a combination of both. In certain embodiments, guaranteed throughput rates (CIRs) provide minimum required throughputs while the excess rate (EIR) enhances performance. Subscribers may desire a certain amount of data throughput (guaranteed throughput, or CIR) and the ability to send additional traffic (excess rate, or EIR) when bandwidth is available. Service providers may be able to charge differently for the CIR and the EIR. In addition, particular embodiments offer improvements in how the provisioned weights associated with weighted scheduling queues translate into priorities for scheduling EIR traffic. Thus, operators may cater more closely to the bandwidth requirements of particular users. Particular embodiments may facilitate providing improved traffic management with differential Quality of Service (QoS).

Certain embodiments of the present invention may provide some, all, or none of the above advantages. Certain embodiments may provide one or more other technical advantages, one or more of which may be readily apparent to those skilled in the art from the figures, descriptions, and claims included herein.

DESCRIPTION OF EXAMPLE EMBODIMENTS

FIG. 1illustrates an example system10for allocating bandwidth. In the illustrated example, system10includes a number of queues12coupled to a scheduler14via one or more links16, a network18coupled to scheduler14via a link20, and a management module22. Although this particular implementation of system10is illustrated and primarily described, the present invention contemplates any suitable implementation of system10according to particular needs.

In general, scheduler14schedules at least portions of traffic flows stored in queues12for transmission to network18via link20, constrained by a limited bandwidth of link20. For example, scheduler14may schedule packets of traffic stored in queues12for downstream transmission to network18via link20, constrained by the limited bandwidth of link20. Thus, portions of system10, such as scheduler14and management module22may facilitate traffic management in a network or collection of networks. As examples only, traffic management may include one or more of network ingress traffic monitoring (e.g., local area network (LAN) ingress traffic policing), network-to-network queuing and scheduling (e.g., LAN-to-wireless area network (WAN) queuing and scheduling and/or WAN-to-LAN queuing and scheduling), congestion management, and admission control during flow provisioning.

Queues12may include any suitable type of storage medium and may be implemented in any suitable manner, according to particular needs. As just one example, queues12may be first-in, first-out queues. Although four queues12(i.e., queues12a,12b,12c, and12d) are illustrated and primarily described, the present invention contemplates system10including any suitable number of queues12.

In general, queues12store information associated with one or more received traffic flows24. Traffic flows24may originate from any suitable source. For example, traffic flows24may be received from one or more subscribers. A subscriber may include, for example purposes only, any suitable combination of communication devices, such as customer premises equipment, that use any appropriate communication techniques. Although particular types of subscribers are described, the present invention contemplates any suitable types of subscribers or other traffic flow sources at any suitable point in the network. Each traffic flow24may include any suitable type of information. For example, traffic flows24may include (in any suitable combination) one or more of voice traffic, data traffic, text traffic, multimedia traffic, or any other suitable type of information. Each traffic flow24may be associated with one or more subscribers or other clients.

Each traffic flow24may include one or more parameters. For example, traffic flows24may include one or more of a committed information rate (CIR) parameter, an excess information rate (EIR) parameter, and any other suitable parameters. In certain embodiments, certain of these parameters are negotiated by the subscribers associated with traffic flows24; however, the present invention contemplates these parameters being determined or assigned in any suitable manner. For example, a particular subscriber may negotiate a particular CIR for transmission of its traffic flows24, and traffic flows24for the particular subscriber may have a CIR parameter specifying the negotiated CIR. As another example, a particular subscriber may negotiate particular CIR and EIR for transmission of its traffic flows24, and traffic flows24for the particular subscriber may have CIR and EIR parameters specifying the negotiated CIR and EIR, respectively.

The CIR parameter of a traffic flow24specifies a corresponding guaranteed pass-through rate (CIR) for the traffic flow24. The CIR parameter may be bandwidth guarantee expressed in bits-per-second, for example. An EIR parameter of a traffic flow24refers to a transmission rate (EIR) that is in excess of the CIR to which transmission of traffic can burst when there is no congestion for transmission of traffic via link20. The EIR parameter may be bandwidth expressed in bits-per-second, for example. These parameters may be used, in part, for policing, admission control, traffic scheduling, and any other suitable purposes. In certain embodiments, acceptable CIR and EIR parameters are defined by the Metro Ethernet Forum.

Traffic flows24may be divided into portions, such as packets. Each portion of a traffic flow24may have its own associated parameters, which may or may not be the same (or have the same values) as other portions of the traffic flow24. For example, a traffic flow24may comprise a number of packets, some of which may include CIR traffic and some of which may include EIR traffic. These packets may be stored as packets in queues12and may vary in size.

Queues12may be coupled to scheduler14via one or more links16. Generally, links16provide for communication between scheduler14and queues12. Links16may be physical or logical links and may include memory access links or network communication links, according to particular needs.

Network18may include one or more local area networks (LANs), metropolitan area networks (MANs), wide area networks (WANs), radio access networks (RANs), a global computer network such as the Internet, or any other wireline, optical, wireless, or other links. Network18may communicate, for example, IP packets, Frame Relay frames, or Asynchronous Transfer Mode (ATM) cells to communicate voice, video, data, and other suitable information between network addresses.

Scheduler14may be coupled, either directly or indirectly, to network18via a link20. Link20may include any suitable type of communication link, such as any suitable type of wireline, optical, wireless, or other links. The present invention contemplates any suitable intervening devices or other communication equipment (e.g., routers, switches, etc.) between scheduler14and network18.

Link20may have a particular available bandwidth for communication of data. The bandwidth of link20may exceed the bandwidth that would be required to meet the CIRs and EIRs of each of traffic flows24. Thus, scheduler14may use one or more scheduling algorithms or values determined from one or more scheduling algorithms to schedule traffic flows24in a manner that satisfies the CIRs and EIRs for traffic flows24. Example scheduling algorithms are described in more detail below.

Queues12may be of various types. The type of a queue12may dictate the order in which scheduler14schedules traffic24stored in the queue12for transmission relative to traffic24in other queues12. For example, queues12may be priority queues26or weighted scheduling queues28. Priority queues26may store traffic24associated with CIR parameters only, and weighted scheduling queues28may store traffic24associated with one or more of CIR and EIR parameters. Thus, in certain embodiments, priority queues26store CIR traffic24, whereas weighted scheduling queues28store both CIR and EIR traffic24. Although particular numbers of priority queues26and weighted scheduling queues28are illustrated and primarily described, the present invention contemplates system10including any suitable numbers of priority queues26and weighted scheduling queues28. Typically, however, system10includes at least one priority queue26and two or more weighted scheduling queues28.

As described above, each traffic flow24may be assigned to one or more queues12. The present invention contemplates any suitable types of intervening components receiving traffic flows24and determining, based on one or more of the parameters of the traffic flow24for example, in which queue12to store the received traffic flows24. As just one example, one or more policers may receive traffic flows24and determine the appropriate queue12into which traffic flows24should be stored. The queue12in which to store a particular received traffic flow24may be determined in any suitable manner. For example, the policers may include one or more rules for determining that appropriate queue12in which to store portions (e.g., packets) of a traffic flow24according to one or more parameters (e.g., CIR parameter or EIR parameter) of the portions. The policer may determine on a packet-by-packet basis in which queue12a packet should be stored. Additionally or alternatively, the policer may determine that an entire traffic flow24(or a suitable sub-portion thereof) should be stored in a particular queue12.

Scheduler14may schedule traffic flows24from queues12for transmission via limited-bandwidth link20to network18. This scheduling may be determined, at least in part, according to the types of queues12. In certain embodiments, scheduler14may schedule traffic24stored in priority queues26(which store CIR-only traffic24) prior to scheduling traffic24stored in weighted scheduling queues28(which store both CIR and EIR traffic24). In embodiments in which system10includes multiple priority queues26, priority queues26may have a pre-assigned priority relative to one another, such that traffic24stored in a first priority queue26is scheduled prior to traffic24stored in a second priority queue26for example. Subsequent to scheduling traffic24stored in priority queues26(until priority queues26are empty, in certain embodiments), scheduler14may schedule traffic24stored in weighted scheduling queues28. Scheduler14may schedule traffic24stored in weighted scheduling queues28according to one or more implementation weights, described in more detail below.

In the illustrated embodiment, system10includes four queues12—queue12a(which may be referred to as a Class A queue), queue12b(which may be referred to as a Class B queue), queue12c(which may be referred to as a Class C queue), and queue12d(which may be referred to as a Class D queue). In this example, queues12aand12bare priority queues26, queue12abeing of higher priority than queue12b. Additionally, in this example, queues12cand12dare weighted scheduling queues28. In certain embodiments, weighted round robin scheduling (augmented by the implementation weights described below) may be used to schedule traffic24stored in queues12cand12d, each of queues12cand12dbeing assigned a provisioned weight. The provisioned weights for weighted scheduling queues28may total one hundred percent (or the number one). The provisioned weights may be divided among weighted scheduling queues28in any suitable manner, according to particular needs. For example, queue12c(which is a weighted scheduling queue28in the illustrated example) may be assigned a weight of 70%, while queue12d(which is a weighted scheduling queue28in the illustrated example) may be assigned a weight of 30%. As another example, the provisioned weights may be divided between weighted scheduling queues26such that weighted scheduling queues26have equal provisioned weights (e.g., 50% for queue12cand 50% for queue12d).

It is generally desirable when scheduling traffic24that the CIRs of traffic flows24be guaranteed and that the EIRs of traffic flows24be transmitted proportionally to the provisioned weights (of the weighted scheduling queues28in which EIR traffic24is stored). Thus, in the illustrated example, it may be desirable to satisfy the CIRs of queues12a,12b,12c, and12d, while scheduling the EIR traffic24of queues12cand12daccording to the provisioned weights assigned to queues12cand12d. Simply transmitting traffic24from queues12cand12daccording to the provisioned weights of queues12cand12dtypically will not meet these goals, as the CIR parameters of queues12cand12dwill generally not be met by simply scheduling traffic24stored in queues12cand12daccording to the provisioned weights of queues12cand12d.

In a particular example, suppose queues12cand12dhave provisioned weights of 70% and 30%, respectively. Suppose further that traffic flows24to be stored in queue12c(Class C traffic) has a CIR parameter of 18 megabits and an EIR parameter of 100 megabits. Suppose further that traffic flows24to be stored in queue12d(Class D traffic) have a CIR parameter of 20 megabits and an EIR parameter of 120 megabits. The total amount of traffic transmitted over link20at any given time is limited by the capacity (e.g., bandwidth) of link20. Thus, in the event that traffic24stored in data queues12exceeds the bandwidth of link20, scheduler14must selectively schedule traffic24from queues12.

In certain embodiments, scheduler14schedules traffic from weighted scheduling queues28(i.e., queues12cand12d) according to implementation weights determined from the weighted scheduling queues28. The implementation weights may be determined based on at least the bandwidth of communication link20, a CIR parameter of queue12c, a CIR parameter of queue12d, and each of the provisioned weights of queues12cand12d.

In certain embodiments, a queue12may store data associated with more than one traffic flow24. Each of those traffic flows24may be associated with a CIR parameter and an EIR parameter. The CIR parameters of the various traffic flows24may be the same or different, and the EIR parameters of the various traffic flows24may be the same or different. In certain embodiments, to account for the various CIRs and EIRs of the traffic flows24of a queue12, a total provisioned CIR parameter may be computed for each queue12, and a total provisioned EIR parameter may be computed for each queue12. The total provisioned CIR parameter for a particular queue12may be calculated by summing the values for the CIR parameters of each traffic flow24of the particular queue12. The total provisioned EIR parameter for a particular queue12may be calculated by summing the values for the EIR parameters of each traffic flow24of the particular queue12.

For example, each priority queue26(which stores CIR traffic24) may be associated with a total provisioned CIR parameter that is equivalent to the sum of the CIR parameters of the one or more traffic flows24stored in the priority queue26. As another example, each weighted scheduling queue28(which stores both CIR and EIR traffic24) may be associated with a total provisioned CIR parameter (equivalent to the sum of the CIR parameters of the one or more traffic flows24stored in the weighted scheduling queue28) and a total provisioned EIR parameter (equivalent to the sum of the EIR parameters of the one or more traffic flows24stored in the weighted scheduling queue28). The total provisioned CIRs and EIRs may be recalculated if a new traffic flow24is directed to a particular queue12(and the implementation weights may be recalculated as well, if appropriate).

A particular example technique for calculating the implementation weights for weighted scheduling queues28is described below. In certain embodiments, the variables of the formulas may be defined as follows.

Total provisioned Class A CIRs (i.e., for queue12a): ACIR;

Total provisioned Class B CIRs (i.e., for queue12b): BCIR;

Total provisioned Class C CIRs (i.e., for queue12c): CCIR;

Total provisioned Class C EIRs (i.e., for queue12c): CEIR;

Total provisioned Class D CIRs (i.e., for queue12d): DCIR;

Total provisioned Class D EIRs (i.e., for queue12d): DEIR;

Assume that the sum of the CIRs of queues12cand12dis less than X and that the sum of all of the CIRs and EIRs of queues12cand12dis greater than X. The provisioned weight for queue12c(the Class C queue) may be represented by the variable WC, while the provisioned weight for queue12d(the Class D queue) may be represented by the variable WD. It may be assumed that WD=1−WC. The throughput for Class C EIR traffic24(EIR traffic24of queue12c) may be represented by the variable REC, while the throughput for Class D EIR traffic24(EIR traffic24of queue12d) may be represented by the variable RED. Certain embodiments of the present invention calculate actual scheduling weights for Class C and Class D traffic (the implementation weights), which may be represented by the variables QCand QD, where QD=1−QC. In certain embodiments, use of the implementation weights by scheduler14to schedule traffic from the weighted scheduling queues12(queues12cand12dmay ensure that one or more of the following is true:CCIRand DCIRare substantially guaranteed; andREC/RED=WC/WDwhen CEIRand DEIRcompete for available X.

In certain embodiments, QCand QDmay be obtained by solving the following two equations:
QC*(X−ACIR−BCIR)=CCIR+REC
QD*(X−ACIR−BCIR)=DCIR+RED

The solutions to these two equations may be the following two formulas, such that implementation weights QCand QDfor queues12cand12dmay be computed according to the following formulas:
QC=WC+(WD*CCIR−WC*DCIR)/(X−ACIR−BCIR)
QD=WD+(WC*DCIR−WD*CCIR)/(X−ACIR−BCIR)=1−QC

Thus, in this particular example in which queues12cand12deach include both CIR and EIR traffic24, the QCand QDdetermined according to these formulas represent the implementation weights for each of queues12cand12d, respectively. In certain embodiments, the sum of the implementation weights may be the numeral 1.0 or one hundred percent, depending on the particular representation. In certain embodiments, the variable X, which represents the bandwidth of link20, may be replaced by the expression X/beta, where beta represents a WAN encapsulation overhead factor.

System10may include a management module22, which may be implemented in any suitable combination of hardware, firmware, and software. Management module22may include an application30that is operable to compute the implementation weights (e.g., QCand QD) for scheduling transmission of traffic24stored in queues12. Management module22may store values for the provisioned weights associated with weighted scheduling queues28(e.g., queues12cand12d). Management module22may include a suitable user interface with which a user may interact to specify one or more of the provisioned weights, bandwidth of link20, CIR and/or EIR parameters of queues12, or other suitable parameters. Additionally or alternatively, management module22may determine one or more of the provisioned weights, bandwidth of link20, CIR and/or EIR parameters of queues12, or other suitable parameters substantially without user interaction.

Management module22may provide the values for the implementation weights to scheduler14in any suitable manner. In certain embodiments, each time a traffic flow24is provisioned with a non-zero CIR parameter, each time the original CIR parameter for a traffic flow24is changed, or each time the provisioned weights of weighted scheduling queues28are changed, the implementation weights (e.g., Qc and Qd values) may change. This change may occur regardless of the scheduling class at issue. Application30may re-compute Qc and Qd according to the above-described equations and provide those implementation weights to scheduler14.

Queues12, scheduler14, and management module14may be implemented in any suitable combination of hardware, firmware, and software. The components that compose queues12, scheduler14, and management module14may be local to one another (on a single or multiple devices) or remote from one another, according to particular needs. In certain embodiments, queues12, scheduler14, and management module22may be implemented as part of a multi-service provisioning platform (MSPP).

Queues12, scheduler14, and management module14may be implemented using one or more processing units and one or more memory units. The one or more processing units may each include one or more microprocessors, controllers, or any other suitable computing devices or resources. The one or more processing units may work either alone or in combination with other components of system10to provide the functionality of system10. For example, operations performed by the one or more processing units may be performed collectively by the processing units and memory units. The one or more memory units may take the form of volatile or non-volatile memory including, without limitation, magnetic media, optical media, random access memory (RAM), read-only memory (ROM), removable media, or any other suitable memory component. The one or more memory units may be local to or remote from other components of system10.

In a first non-limiting embodiment of system10, scheduler14is operable to schedule traffic in an upstream direction, from a LAN to a WAN. In a second non-limiting embodiment of system10, scheduler14is operable to schedule traffic in a downstream direction, from a WAN to a LAN.

Although the present description focuses on an embodiment that includes four queues12(two of which are priority queues26and two of which are weighted scheduling queues28), those of ordinary skill in the art will understand that system10may include any suitable number of queues, any number of which may be priority queues26and weighted scheduling queues28). Those of ordinary skill in the art will understand that the above-described formulas may be extended for calculation of implementation weights for additional weighted scheduling queues12, if appropriate.

For example, the implementation weights for a generic number of weighted scheduling queues28may be determined based on at least the bandwidth of a communication link20(e.g., a downstream or upstream communication link), each of the CIR parameters of weighted scheduling queues28, and each of the provisioned weights of weighted scheduling queues28. A formula for determining such implementation weights for a generic number of weighted scheduling queues28may be expressed as follows:

In this example, Q represents the implementation weight being determined for a given queue i. The variable M represents the number of priority queues26, and the variable N represents the number of weighted scheduling queues28. The variable W represents the provisioned weight of a weighted scheduling queue28. Beta represents a WAN encapsulation overhead factor, although it should be noted that the present invention is not limited to scheduling transmission to a WAN.

Particular embodiments of the present invention may provide one or more technical advantages. Conventional techniques for scheduling traffic24stored in weighted scheduling queues28only address scheduling EIR traffic24according to provisioned weights pre-assigned to the weighted scheduling queues28. However, among other possible deficiencies, scheduling traffic24stored in weighted scheduling queues28merely according to the provisioned weights may not allow CIRs to be guaranteed for weighted scheduling queues28. In certain embodiments, the present invention provides algorithms and mechanisms that can schedule traffic24stored in multiple weighted scheduling queues28with CIRs and EIRs, using determined implementation weights. In certain embodiments, scheduling traffic24stored in weighted scheduling queues28according to the determined implementation weights may allow the CIRs of traffic flows24to be satisfied, as well as the weighted throughput for the EIR traffic24.

According to certain embodiments of the present invention, a network operator may be able to provide greater options for users communicating over its network. Typical systems do not offer users guaranteed throughput rates (i.e., CIRs). In certain embodiments, a network operator may offer users guaranteed throughput rates (CIRs), best effort traffic rates (EIRs), or a combination of both. In certain embodiments, guaranteed throughput rates (CIRs) provide minimum required throughputs while the excess rate (EIR) enhances performance. Subscribers may desire a certain amount of data throughput (guaranteed throughput, or CIR) and the ability to send additional traffic (excess rate, or EIR) when bandwidth is available. Service providers may be able to charge differently for the CIR and the EIR. In addition, particular embodiments offer improvements in how the provisioned weights associated with weighted scheduling queues28translate into priorities for scheduling EIR traffic24. Thus, operators may cater more closely to the bandwidth requirements of particular users. Particular embodiments may facilitate providing improved traffic management with differential QoS.

FIG. 2illustrates an example queue12caccording to certain embodiments of the present invention. Queue12cincludes a number of portions30. In certain embodiments, portions30may be packets and will be referred to as such throughout the remainder of this description. In this example, queue12cis a weighted scheduling queue28and includes packets of both CIR and EIR traffic. For example, a first subset of packets30may comprise CIR traffic24that is associated with a CIR parameter that specifies a guaranteed pass-through rate for packets30in the first subset. As another example, a second subset of packets30may comprise EIR traffic24that is associated with an excess pass-through rate for packets30in the second subset. Packets30within queue12cmay vary in size. Queue12cmay be any suitable size and may store any suitable number of packets30suitable for the size of queue12c.

FIG. 3illustrates an example method for bandwidth allocation according to certain embodiments of the present invention. The above example of four queues12athrough12dwill again be assumed for purposes of describing this example method. It will also be assumed again that queues12aand12bare priority queues26, with queue12abeing a higher priority queue than queue12b. It will also be assumed again that queues12cand12dare weighted scheduling queues28, with queue12cbeing assigned a provisioned weight of 70% and queue12dbeing assigned a provisioned weight of 30%.

It will also be assumed that one or more of queues12store traffic flows24. In certain embodiments, traffic flows24are stored in appropriate queues12by one or more policers. For example, a first traffic flow24amay be received, traffic flow24acomprising a CIR parameter. A policer may determine that traffic flow24ashould be stored in queue12a, a priority data queue26for CIR traffic only. The policer may facilitate storage of traffic flow24ain queue12a. As another example, a second traffic flow24bmay be received, traffic flow24bcomprising a CIR parameter. A policer may determine that traffic flow24bshould be stored in queue12b, a priority data queue26for CIR traffic only. The policer may facilitate storage of traffic flow24bin queue12b. As another example, a third traffic flow24cmay be received, traffic flow24ccomprising at least CIR and EIR parameters. A policer may determine that traffic flow24cshould be stored in queue12c, a weighted scheduling queue28for traffic that includes both CIR and EIR parameters. The policer may facilitate storage of traffic flow24cin queue12c. As another example, a fourth traffic flow24dmay be received, traffic flow24dcomprising at least CIR and EIR parameters. A policer may determine that traffic flow24dshould be stored in queue12d, a weighted scheduling queue28for traffic that includes both CIR and EIR parameters. The policer may facilitate storage of traffic flow24din queue12d. The receipt and storage of traffic flows24in appropriate queues12may be a substantially continuous process.

At step300, scheduler14determines whether any traffic24is stored in first priority queue12ato be scheduled for transmission. In certain embodiments, queue12acommunicates a status to scheduler14such that scheduler14is informed of whether queue12ais currently storing traffic24for scheduling and transmission. This status may be communicated automatically by queue12aor in response to a request from scheduler14. Additionally or alternatively, scheduler14may access queue12ato determine whether queue12ais currently storing traffic24for scheduling and transmission. If scheduler14determines at step300that traffic to be scheduled for transmission is stored in queue12a, then at step302scheduler14may schedule traffic24stored in queue12afor transmission. For example, scheduler14may schedule the next packet30stored in queue12afor transmission. Since queue12ais the highest priority queue12in this example, scheduler14may continue transmitting packets30from queue12auntil queue12ais empty.

If scheduler14determines at step300that no traffic24to be scheduled for transmission is stored in queue12a, then at step304, scheduler14may determine whether any traffic24is stored in second priority queue12bto be scheduled for transmission. In certain embodiments, queue12bcommunicates a status to scheduler14such that scheduler14is informed of whether queue12bis currently storing traffic24for scheduling and transmission. This status may be communicated automatically by queue12bor in response to a request from scheduler14. Additionally or alternatively, scheduler14may access queue12bto determine whether queue12bis currently storing traffic24for scheduling and transmission. If scheduler14determines at step304that traffic24to be scheduled for transmission is stored in queue12b, then at step306scheduler14may schedule traffic stored in queue12bfor transmission. For example, scheduler14may schedule the next packet30stored in queue12bfor transmission. Since queue12bis the second highest priority queue in this example, scheduler14may return to step300after communicating traffic24(e.g., a packet30) from queue12bto determine whether queue12a(which has a higher priority than queue12b) is now storing traffic24to be communicated.

If scheduler14determines at step304that no traffic24to be scheduled for transmission is stored in queue12b, then at step308, scheduler14may access the implementation weights determined for queues12cand12d(weighted scheduling queues28). In certain embodiments, the implementation weights were previously calculated by application30of management module22. Management module22may provide the determined implementation weights to scheduler14either spontaneously or in response to a request from scheduler14. In certain embodiments, the implementation weights may be calculated according to one or more of the formulas described above with respect toFIG. 1.

At step310, scheduler14may schedule traffic24stored in weighted scheduling queues12cand12daccording to the accessed implementation weights. The implementation weights may have been determined based on a bandwidth of a downstream communication link (e.g., link20), a CIR parameter of queue12c, a CIR parameter of queue12d, and each of the provisioned weights of queues12cand12d.If one of queues12cor12dis empty, scheduler14may simply schedule traffic24from the non-empty queue. In certain embodiments, traffic24stored in queues12cand12dis not scheduled for transmission unless both queues12aand queues12bare empty. Thus, after each transmission of a packet30from one of queues12cand12d(or at some other suitable interval) it may be appropriate to check queues12aand12bfor traffic24to be scheduled.

If all queues12are empty of traffic24to be scheduled for transmission, the method may end. However, in certain embodiments, scheduler may simply enter a “wait” state until one or more of queues12stores traffic to be scheduled. In such embodiments, the method may not end until scheduler14either fails or is otherwise shut down.

FIG. 4illustrates an example method for bandwidth allocation that includes particular example details for determining two or more implementation weights, according to certain embodiments of the present invention. In certain embodiments, at least certain steps of the method may be performed by management module22and/or scheduler14, either alone or in combination. In this example, it is assumed that system10includes two or more weighted scheduling queues28, each associated with a corresponding provisioned weight.

At step400, a corresponding CIR parameter for each of two or more weighted scheduling queues28may be accessed, the CIR parameter for a queue being associated with a guaranteed pass-through rate. At step402, a corresponding EIR parameter for each of the two or more weighted scheduling queues28may be accessed, the CIR parameter for a queue being associated with a guaranteed pass-through rate.

At step404, corresponding implementation weight may be determined for each of the two or more weighted scheduling queues28, the implementation weights for scheduling traffic24stored in the two or more weighted scheduling queues28for communication over a communication link20. The corresponding implementation weights may be determined according to a bandwidth of communication link20, each of the corresponding CIR parameters of the two or more weighted scheduling queues28, and each of the corresponding provisioned weights of weighted scheduling queues28.

At step406, scheduler14may schedule traffic24from the two or more weighted scheduling queues28for transmission over the communication link according to the determined implementation weights for the two or more weighted scheduling queues28. In certain embodiments, scheduler14may only schedule traffic24from the two or more weighted scheduling queues28if traffic24from all priority queues26has been scheduled.

Although particular methods have been described with reference toFIGS. 3-4, the present invention contemplates any suitable methods for bandwidth allocation in accordance with the present invention. Thus, certain of the steps described with reference toFIGS. 3 and 4may take place substantially simultaneously and/or in different orders than as shown and described. Moreover, components of system10may use methods with additional steps, fewer steps, and/or different steps, so long as the methods remain appropriate.

Although the present invention has been described with several embodiments, diverse changes, substitutions, variations, alterations, and modifications may be suggested to one skilled in the art, and it is intended that the invention encompass all such changes, substitutions, variations, alterations, and modifications as fall within the spirit and scope of the appended claims.