KR100475783B1 - Hierarchical prioritized round robin(hprr) scheduling - Google Patents

Abstract

The HPRR method uses token bucket rate classifiers to indicate whether each individual packet meets the traffic specification for the flow (queues per flow 1, 2, 3, 4). Flows are considered to be in a single service class (classes A, B, and D). One such class is identified as the default "best" service class (D). Each service class is assigned a weighting corresponding to the portion of the bandwidth approved for the class when all classes are active. The HPRR method allows a packet from a flow to be forwarded in one of two ways, either as part of the allocated bandwidth of that class or as part of the best bandwidth. By always providing two paths to the flow to send the packets, the flow is always given two different classes, its primary or constituent class and its fair share of the best-in-class class.

Description

Hierarchical PRIORITIZED ROUND ROBIN (HPRR) SCHEDULING}

Cross Reference to Related Application

This application claims priority to US Provisional Application No. 60 / 156,123, entitled "hierarchical prioritization round robin (HPRR) scheduling", filed September 25, 1999 by Applicant.

Field of invention

FIELD OF THE INVENTION The present invention generally relates to computer networks and, more particularly, to scheduling data traffic over data transmission links.

One requirement for link sharing is to share bandwidth on a link between multiple organizations, where each organization wants to receive a guaranteed share of link bandwidth during congestion, but one organization Bandwidth that is not in use by the system must be available to other organizations sharing the link. A representative example is a number of relays sharing a trans Atlantic FAT pipe, each paying a fixed share of the costs for entities sharing a single ISDN circuit. Another example of link sharing is shared bandwidth on a link between different protocol families (eg, IP and SNA), where control of link sharing is needed because different protocol families have different responses to congestion. A third example of link sharing is sharing bandwidth on a link between different traffic types such as telnet, ftp or real time audio and video.

Control of network resources involves local decisions about usage, as well as consideration of per-connection end-to-end requirements. One function of the link sharing mechanism is to enable the gateway to control the distribution of bandwidth on local links in response to pure local requests.

The need to involve different traffic types, including real-time services on shared links, leads to the need for hierarchical link sharing with classes of traffic. Link sharing services and real time services involve isochronous sets of constraints to be satisfied at the gateway. There is also a need to prevent starvation of lower priority traffic while satisfying link sharing requirements while at the same time meeting the needs of higher priority traffic.

Current scheduling methods support differentiated quality of service (QOS) using a variant of Prioritized Class Based Queuing (CBQ) or Weighted Fair Queuing (WFQ). The prior art CBQ and WFQ methods have two important factors: 1) overlimit traffic, i.e. traffic from a flow that exceeds the guaranteed traffic rate specification of the flow, and 2) statistics that are not guaranteed guarantees of bandwidth and delay. Ignore deliberate overbooking of flows to provide scientific guarantees. Overbooking of flows means that when all flows are active at the same time, flows with the reserved minimum bandwidth requirements are allowed, even if the capacity is insufficient to provide that bandwidth.

The CBQ algorithm relies on a fixed set of flows that are always considered to be active, not an environment that changes the activation flows rapidly. The CBQ algorithm uses a slow-acting average rate per flow to classify it as an overlimit. The CBQ algorithm operates relatively slowly because it relies on the calculated class average rate to determine whether the class exceeds or falls below the traffic limit. It depends on the average rate per slow flow (or class) to indicate class overlimit, and on a relatively complex algorithm to determine what process bandwidth should be allocated for the overlimit class. In the end, this makes no countermeasure for overbooking the flow in the class. That is, if flows with guaranteed minimum service rates are deliberately over-licensed, statistically a small number of allowed flows will be backlogged at the same time. The CBQ algorithm does not consider class bandwidth emphasis in the presence of overbooking.

In the CBQ algorithm, each class can be limited to its allocated average bandwidth, but there is no protection against instantaneous bandwidth loss for underlimit classes. This is because the CBQ algorithm as described above relies on a relatively slow changing average rate to determine whether the class is overlimit or not.

The signal level WFQ method has the problem of overbooking because a set of overbooked flows can arbitrarily occupy a large portion of the bandwidth. Each flow consumes its fair share even if the number is too large. The problem of overbooking is mitigated by the concept of hierarchy in the WFQ scheduler. However, the WFQ algorithm assumes that each flow conforms to its traffic specification, and the algorithm described above has no countermeasures for individual flows that exceed the traffic specification limit. In the hierarchical WFQ method for flow in one class, there is no concept for sharing bandwidth in the best effort class. If a higher level flow is overlimit, it must contain itself in the bandwidth allocated to that class, and cannot complete other best-in-class flows in the default class. As an example, consider the case where there are five flows in the guaranteed class assigned 50% of the bandwidth, each with 10% of the bandwidth allocated, and only one flow in the default class assigned 50% of the bandwidth. . One default flow is constantly backlogged, thus acquiring 50% of the bandwidth. When one of the guaranteed flows suddenly needs as much bandwidth as possible, it will continue to receive only 10% of the link bandwidth, ie only one fifth of the 50% allocated to the guaranteed class using hierarchical WFQ.

In the WFQ scheduling algorithm, overbooked flows continue to use the weighted value of the bandwidth, and indeed can consume large portions of the bandwidth arbitrarily at significant overbooking conditions. The WFQ algorithm limits the class of flows to the ratio of bandwidths and does not provide any measure for enforcing that bandwidth in the presence of excess reservation. Overbooking is an important economic requirement for commercial bandwidth providers. WFQ algorithms provide better worst case delays than deficit round robin (DRR) algorithms, while also having a number of computational complexity. The main problems are the complexity of calculating the packet termination time and maintaining the queues arranged based on the termination time. These complexities are generally considered to be at the level of O (log N) for the N possible flows.

1 is a partial schematic flow diagram of hierarchical prioritized round robin (HPRR) scheduling in accordance with the principles of the present invention;

2 is a block diagram of data structures used by the system and HPRR method of FIG.

3 is a block diagram of one exemplary state of the data structure of FIG.

4 and 5 are flow charts of the operation of the process of receiving new packets in accordance with the method and system of FIG.

6, 7, 8, 9 and 10 are flowcharts of the scheduling of packets to be transmitted according to the method and system of FIG.

The problems of scheduling packets on a data transmission link are solved by the present invention of hierarchical prioritized round robin scheduling.

An important component for providing differentiated quality of service (QOS) in data networking devices is the scheduling method for packets routed to the outgoing transport interface. The present invention is a method for scheduling packets on a transport interface that provides bandwidth allocated to different classes of traffic, where each class consists of multiple flows. This provides effective and fair handling when overbooked flows, ie the sum of the traffic rates of allowed flows, exceed the allocated capacity for the classes of flows. The present invention maintains a DRR mechanism for limiting the bandwidth of each class to an allocated portion of capacity, while providing a dedicated round robin (DRR) to provide prioritized forwarding of packets with the concept of priority for each class. This includes enhancing the algorithm. A key feature of the present invention is to identify one class as the default class, where flows that exceed the traffic rate of that class can still forward packets within the allocated bandwidth of the default class.

In HPRR, the first example bursting assurance class flow will acquire a total of 35% of the bandwidth plus one half of the best bandwidth (25%) to that 10% guarantee. The HPRR method allocates a default or best effort bandwidth efficiently and easily for certain differentiated class flows that exceed its traffic specification limit.

The HPRR method immediately uses the correct token bucket rate classifier to mark each individual packet as compliant or inconsistent with the traffic specification for the flow. The essence of the invention is that the flow is considered part of two different classes, namely the assigned class of the flow and the default or best effort class. The HPRR method allows a packet from a flow to be forwarded in one of two ways, either as part of the allocated bandwidth of that class or as part of the best bandwidth. Unlike CBQ, the HPRR method does not mark the classes as overlimit or not, or attempt to determine whether the overlimit classes are allowed to block or forward the packets. There is no need to deal with any algorithm that tests for over or under limit of all peer classes. Instead, by always providing two paths in order to send the packets for one flow, one flow is always given its fair share of two different classes, that is, its primary or composed class and the best class. do.

The HPRR method is a simple and effective algorithm for handling overbooked classes. An overbooked class has its own flows compared to the insufficient bandwidth allocated to that class, but because each flow can use the best bandwidth, bandwidth that allows bandwidth guarantees for classes when other classes are inactive You can get a fair share of.

The HPRR method determines on a packet-by-packet basis whether the packet itself matches the traffic rate token bucket. Remaining packets that do not meet the flow specification token bucket of the flow are inadequate for forwarding via the flow's class bandwidth, but are still suitable for forwarding over the default class bandwidth. The HPRR method uses a new prioritized DRR method to avoid partitioning operations and O (log N) maintenance of the arranged queue at the expense of a higher worst case delay limit.

Justice

Generic scheduler: schedules packets from leaf classes that are not related to link sharing guidelines.

Link sharing scheduler: schedules packets from some leaf classes that exceed link sharing allocations during congestion.

Regulatory class: When packets from that class are scheduled by the link sharing scheduler at the gateway.

Unregulated Class: When traffic from that class is scheduled by the generic scheduler.

Overlimit, Underlimit, at-limit: If a class has been used more than its recently allocated link-sharing bandwidth (averaged over a certain time interval, bytes / sec), the class is referred to as overlimit. In other words, when used less than a certain portion of the link share bandwidth, it is called an under limit, otherwise it is called an edge limit.

The invention will be more clearly understood with the foregoing and other advantages from the following detailed description of the embodiments of the invention illustrated in the drawings.

1 is a partial schematic flow diagram of a hierarchical prioritized round robin scheduling method in accordance with the principles of the present invention. The present invention includes an apparatus and method for scheduling the transmission of packets on a data transmission link. Packets transmitted on the transmission link are given to a scheduler, which queues the packets and rearranges the packets if necessary to meet predetermined conditions.

The scheduling methods and apparatus described herein (called schedulers) include per-flow queuing, which limits both priority level based bandwidth division and maximum burst at each priority level. It involves a combination of prioritization services. The present invention combines the key features of both weighted process queuing (WFQ) and class-specific queuing (CBQ) packet scheduling methods. In addition, an improved depth round robin service method is included in the present scheduling method and apparatus. The improved depth round robin service method avoids the complexity of prioritization queues and the splitting of SFQ end time calculations.

Referring to Figure 1, the scheduler of the present invention processes packets at a number of stages within the scheduler.

1. Packets are first classified into flows. For the Internet Protocol (IP), the flow classification is suitably a function of the source and destination IP addresses of the packets, the IP protocol type and the User Datagram Protocol (UDP) or Transmission Control Protocol (TCP) port number in the packet. In the scheduler, packets are first put into a per-flow queue. Each flow preferably has a maximum number of buffers that can be queued thereon. As an example of flow classification, IP telephony (ie, encapsulated voice) is classified as flow number 1, and all other packets may be classified as flow number 4 (default flow class).

Each flow is considered to be a member of a single service class that describes the set of data forwarding services provided for the flow.

2. The packets must then pass through the maximum rate token bucket limiter, which limits the forwarding rate on a per flow basis. Once the packets have passed their maximum rate limiter, they are suitable for forwarding either of two classes, the flow's constituent class or the default class.

3. The packets must then pass through a traffic rate token bucket limiter to be suitable for forwarding to that logical class-specific queue. The traffic rate is the maximum rate at which the flow source agrees to inject traffic into the network. The service contract between the network and the traffic source is such that only packets transmitted at less than the traffic rate will receive differentiated service by the network. For a Committed Information Rate (CIR) service as provided in frame relay networks, the traffic rate corresponds to the CIR rate. Although the network receives packets faster than the traffic rate, it is appropriate that they will only forward at their best. In the scheduler of the preferred embodiment of the present invention, packets arriving faster than the traffic rate are prevented from being forwarded as part of the bandwidth allocated to that class of service and can only be forwarded as part of the bandwidth allocated to the default class.

4. At any time, a class can be instantaneously overbooked, which means that flows with an incoming traffic rate that exceed the configured capacity of the transport channel assigned to the class are allowed. In this state, the scheduler allows flows to forward packets using the default class bandwidth in addition to that class's bandwidth.

5. Packets passing through the traffic rate limiter are scheduled on a class-specific queue that holds packets for all flows within the same class.

Packets are only physically pushed onto the flow queue. The class-specific queue of FIG. 1 is a virtual queue used to describe the operation of the method of the present invention. In addition, all packets that meet the flow's maximum rate token bucket limiter are suitable for forwarding from both the class's bandwidth and the default class bandwidth.

Actual flow-specific queues conceptually provide class-specific queues for assigned service classes of flows. The manner in which packets from flows within the same class are forwarded to the class-specific queue is irrelevant to the present invention, however, however, it is appropriate in the form of a process queuing algorithm such as depth round robin scheduling.

Each flow is built using the maximum rate limiter in the scheduler, so it does not forward the packet if it exceeds the maximum rate established for the flow. Buffer management is performed flow by flow, not class.

Each flow also has a traffic rate limiter that prevents forwarding packets above the traffic rate of the flow onto its class of service queue. Each flow must be built using a traffic rate limiter that must be matched to receive the bandwidth allocated to that flow class. The flow is allowed to send data faster than the traffic rate, but it stays back on the per-flow queue and can only be forwarded as part of the bandwidth allocated to the default class.

The scheduler forwards packets from the flow queues to the virtual queue for the class of service. This is a virtual queue because there is no need to perform physical queuing (eg, linked lists) for per-class queuing. Instead, the scheduler only needs to maintain a pointer to the top flow queue on the class-specific list. When the top packet or packets from the virtual priority queue exit the queue, they are removed from the (real) flow queue and the next top of the class queue is determined by scanning the active flow queue in that class. The scheduler preferably does not forward packets in any given single queue that are not aligned.

Each service class is assigned a scheduling priority. Class-specific queues are serviced in order of priority, and are subject to bandwidth limitations. Advantageously, a depisit round robin (DRR) algorithm may be used to schedule packets from each class. The present invention includes improvements to the DRR algorithm to implement prioritized scheduling. The highest priority class queue is served until the quantum is exhausted, at which time the next higher priority class is scanned. When all classes have exhausted their quantum, a new DRR round begins.

The quantum of the class for that priority DRR algorithm is calculated by the scheduler based on the maximum allocated bandwidth (MAB) built for the class. The MAB is conveniently expressed in units of integer percentage points ranging from 1 to 100, although other methods may be used within the scope of the present invention.

The MABs assigned to a class determine that quantum for DRR purposes so that the ratio of quantums for each class is equal to the ratio of MABs for each class. One algorithm for computing the quantum from the MAB is described below. The class with the highest MAB is given the maximum quantum, which is the maximum packet size allowed in the system. For the IP routing protocol, the appropriate maximum is 1600 bytes in shape, which exceeds the IP Maximum Transmission Unit (MTU) for Ethernet local area networks (LANs). The other classes are assigned a quantum based on the ratio of that MAB to the highest MAB. As an example, assuming that the highest MAB is 50%, it is assigned a class quantum of 1600. A class with 10% MAB receives a quantum of 10/50 * 1600 or 320 bytes. Using this quantum allocation algorithm, the dynamic range of reserved rates is limited to 1500-1. Ideally, to limit the number of rounds needed to accumulate 1600 byte depths, the dynamic range should be limited to about 100-1.

An important concept of the scheduler of the present invention is that all non-zero priority flows are scanned twice, ie once by its priority queue scheduler and once by the best-of-breed (BE) priority level 0 DRR scheduler. The purpose of this is to guarantee bandwidth for prioritization flows even for the best bandwidth. As an example, consider five prioritized flows with a 10 kbps traffic rate and one best flow sharing a 500 kbps channel. Prioritization flows reserve only 50 kbps of available 500 kbps, but they require some mechanism to share the 450 kbps left for best practice. Scanning the flows twice as described above achieves this purpose.

The actual bandwidth of the received flow over the period of continuously backlogged flows is the sum of the two rates.

1. the published traffic rate of a flow transmitted at the priority level of the class of flow, and

2. Share of flow of residual best capacity.

In IP networking, most identified flows are bursted, and most flows are idle at any given moment. The service share of a given flow is not the quantum divided by the sum of the quantums of all assigned flows, but the quantum divided by the sum of the quantums of active flows. The term "assigned" refers to the flow assigned to a channel when spectrum management assigns a modem to a particular RF channel. A flow is considered to be active only when it has packets queued (i.e., it is in the state) on the queue per flow or actually has packets transmitted.

As an example, assume that there are 100 flows at the best or priority 0 level assigned to a channel. Each is given a flow quantum of 1500 bytes. Over a given congestion period (ie, when one or more packets were queued), only 10 of the modems sent certain data. Since only 10 modems are active, the sum of the active quantums is 15000, and each modem is given the opportunity to transmit 10% of the bandwidth available for 1500/15000 of bandwidth or priority 0 (lowest) traffic. .

The operation of the scheduler of the present invention in overbooking is important. Overbooking occurs when the traffic rate introduced on the transmission link exceeds the allocated capacity of the link assigned to the class of flows. Each class is scheduled independently, and no class is allowed to exceed its average rate (as determined by quantum assignment when DRR is used for the class-specific scheduling level). In an alternative embodiment of the invention, the per-class scheduling step may use WFQ, in which case each class is also blocked from using more than its allocated share of bandwidth.

The modified deficit round robin method of the present invention provides prioritized forwarding. The prioritized DRR method is suitably used in the final class-specific scheduling step of the scheduler of the present invention. Prior art DRRs rely on the concept of quantums assigned for each scheduled class and visit each class in a round robin fashion. In the present invention, each class is given priority. The prioritized DRR method of the present invention visits each class in order of priority, and there is no specific order for classes having the same priority. The highest priority class is serviced until all packets on that class-specific queue are forwarded or until the depth count is exhausted. At this point, the next highest priority class is serviced. When all classes have their class queues empty or their depths exhausted, a new DRR round begins, that is, the classes in all backlog states are given a new quantum. As in the DRR algorithm, the ratio of quantum assignments determines the long-term ratio of the transmission link bandwidth allocated to the class.

In a preferred embodiment of the invention, flows are introduced into the transport channel based on the established level of excess reservation. One approach is to build household rate active flows within a service class. As an example, if only 10% of the flows are expected to be activated at the same time, the build activity rate (CAP) build for this case is 10%.

Each flow has an identifying traffic specification that provides traffic rate and traffic burst parameters for the traffic rate token bucket. It is determined whether packets from the flow match the traffic specification or not. Each class has a minimum reserved bandwidth associated with it. This is similar to the regulatory information transmission rate of frame relay networks of minimum cell rate for ATM networks. The minimum reservation rate is used as the traffic specification for the traffic rate token bucket of the method of the present invention.

The excess reservation introduction control method then introduces flows such that the sum of the reservation rates of the introduced flow and the CAP percentage is less than the MAB percentage placed for the class on the channel. For example, when the CAP is set to 10%, the class is constructed to have a MAB of 50% of the 1 Mbps channel, the class has a reserved traffic rate of 100 Kbps, and the number of introduced flows is as follows.

Number of flows introduced

(MAB * capacity) / CAP * reserved bandwidth)

= 0.50 * 1,000,000 / (0.10 * 100, 000)

Introduced Flows

When flows are introduced in a reserved excess, more flows may actually be activated than the number of CAP expected active flows. The scheduling method of the present invention divides the construction capacity for the class evenly among all of the overbooked introductory flows so that each receives less than the “defined” rate of its bandwidth, and so that no other class is affected. do. All flows will use the best bandwidth, but if other best flows are disabled, it is still possible for the flows to receive the prescribed bandwidth. It is also desirable to report the number of packets arriving into the system to find an overbooked situation for that class, i.e., when the CAP establishment activity percentage of flows is delayed at the same time. It provides guidance on how to set the CAP parameters and can be used as the basis for service level agreements.

By changing the traffic specification and the introduction policy, most of the QOS service concept can be implemented using the present invention.

The guaranteed service can provide a class with the highest priority with a non-zero traffic bucket and zero overbooking (i.e. 100% of the CAP is active at the same time). This combination can guarantee minimum delays and maximum bandwidths.

The Regulatory Information Transmission Rate (CIR) service class may be implemented with a non-zero traffic rate, lower priority than the guaranteed class, and allowed overbooking. By allowing overbooking, the bursty traffic of conventional data communications can receive statistically guaranteed service while maintaining high link utilization.

Prioritized best service classes may be provided with an infinite traffic rate bucket and infinite overbooking (CAP = 0), and with a class priority lower than the CIR class but better than the default service class.

The default service class may have an unlimited traffic rate bucket and a lower priority than the unlimited overbooking and prioritization best class.

Bulk or low priority service classes have unlimited traffic rates and unlimited overbooking, and have a lower priority than the default class.

Figure 2 illustrates the key flow structures used in the above embodiment of the present invention. FLOW structure 100 contains all the information associated with a single flow of packets. Each flow includes a queue structure named PacketQ, which contains pointers to the start and end of the queue of packets to be transmitted.

QITEM structure 110 allows structures containing it to be linked to a dual linked list. The QUEUE structure 120 contains pointers to the head and tail QITEMs of a given list, along with a count of the items in that list.

The SLICONF structure 130 includes parameters that are considered to be built for operation of a particular service class (SCLASS 140) when operating on a particular interface Intf 150. This includes, for example, overparameter reservation, which indicates how many times the actual bandwidth can be overbooked by introduced flows for an interface with reservation rates exceeding capacity.

The DRRITEM structure 160 includes parameters required for scheduling flow (or class of service) using the Deficit Round Robin (DRR) algorithm. The DRR algorithm works by initially assigning a fixed quantum to each item. Flows are allocated bandwidth according to the relative ratio of their quantum assignments. Quantum assignment is fixed for each flow and is determined when the flow is created.

The quantum for the flow is stored in the U32 quantum field 162 of the DRRITEM. At any given point in time, the flow will send the amount of bytes stored in the depth count of that DRRITEM. At the beginning of each DRR round of the DRR queue, all DRRITEMs in that queue are incremented by their depth count by the amount of their quantum. When each DRRITEM is processed (by the NextBurst method described with respect to FIGS. 6-10), its depth value is compared against the number of bytes to be sent by the next packet for that flow. If the count of bytes in the deficit count is insufficient, the flow moves to the end of the DRR queue and waits for the next DRR round for the deficit to be incremented. If there are enough bytes in the deficit, the packet is transmitted and the deficit count is reduced by the number of bytes sent. Over a long run, the DRR algorithm provides a fair bandwidth to all flows in the DRR queue, based on the ratio of its quantum assignments. This is fairer than a typical single forward queue first-class forwarding (FCFS) service, because there are fewer flows with fewer and smaller packets and no need to backlog behind packets of flows with large packets.

The service level interface (SLI) structure 170 controls the scheduling and includes statistics of the operation of a single service class (SCLASS) operating on a single interface (Intf). The scheduling method of the present invention requires logically providing portions of the bandwidth of the interface for each SLI in accordance with the weighting established for the SLI. Within that allocated bandwidth, the embodiment provides equal weighted portions for all active flows within the same class of service.

SLIs are considered to be arranged with respect to the priority field of the service class (SCLASS 140). The p_classes field of INTF structure 150 leads a linked list of SLI structures 170 and is linked through a QITEM structure 110 named priority in SLI.

The present invention uses three separate DRR queues.

Flow Priority DRR Queue: Flow structure 100 includes a DRRITEM called pq that links all flows belonging to the same class of service (and thus at the same priority level). The head and tail of this queue is a QUEUE structure 120 named flow list within SLI structure 170.

Flow Best Practice DRR Queue: Flow structure 100 includes a DRRITEM 160 called bq that links all active flows on the interface. Interface structure Inft 150 includes a QUEUE structure 120 that provides the head and tail of a linked list of flows.

Class DRR Queue: A Service Level Interface (SLI) structure 170 that is active on an interface is considered to be part of the SRR's own DRR queue. The DRRITEM 160 for this class level of scheduling is stored in the cq object of the SLI 170.

The TOKBKT structure 180 is used to maintain a flow rate token bucket used to determine when flows are allowed to use its class of service bandwidth, and to keep flow packets on the flow queue when it arrives faster than the flow maximum allowed forwarding rate. Both maximum rate token buckets are described.

3 shows an exemplary state of the structures of FIG. 2. Only relevant fields of the above structures are shown. For a particular transport interface of a data communication device, a single Intf structure includes a QUEUE structure that leads linked lists of SLI in decreasing order of priority. By way of example, there are two service classes, namely gold, SCLASS = "gold" structure 200, and a default, SCLASS = "default" structure 210 for the default service class structure 260. There is always an SLI structure for the default service class.

1. Flow 1 220 is one of two active flows in the Gold SCLASS. As with all active flows, it has a QUEUE structure named PacketQ 222 that leads a linked list of packets 224, 226 to send on the flow. The scheduling method of the present invention always transmits packets from the same flow in order. In FIG. 3, only flow 1 is shown as having packets on that PacketQ, but in this embodiment all active flows have such packets. PacketQ and packets are not shown in other flows for simplicity.

Flow 1 220 is considered to be on two DRR queues. The flow priority queue is guided by a QUEUE structure named FlowList (FlowList) in SLI 230 for the Gold class on this interface. The DRRITEM, named pq in flow 1, contains a link to another flow on its SLI flowlist, flow 2 235. Flow 1 is also considered to be on the best-in-class DRR queue, which is guided by a QUEUE structure named beq in Intf interface structure 240. All flows on the best effort DRR queue are linked via a DRRITEM named "bq" in the flow structure. It should be noted that all the flows 220, 235, 245, 250 of FIG. 3 exist on the linked list led by Intf.beq 240 and are linked via their bq DRRITEM structures.

2. Flow 2 235 is another flow in the Gold Service Class that is activated with Flow 1. The term activation means having a packet waiting to be transmitted when applied to a flow or SLI.

3. Flow 3 245 is the best flow. Although they are not shown, this includes PacketQ with packets to transmit, and includes a sli pointer that indicates the back to SLI for the operation of the default class of service (not shown). 3 does not use its pq DRRITEM, which uses bq DRRITEM and is considered to exist only on the best-in-class DRR queue.

4. Flow 4 250 is similar to flow 3 245. This is the best-in-class flow, which is bandwidth scheduled only under the default class of service.

Each flow has a pointer named S255 that indicates the SCLASS structure in which they are classified. All flows are considered to be in one class. The default class contains unclassified flows.

Flows that are considered to belong to the default service class 210 (flows 3245 and 4250) are not linked via pq DRRITEM. Instead, when the default class SLI is provided bandwidth by the NextBurst procedure, the flows above it are obtained from the beq list off of the Inft structure 240 rather than the flow list QUEUE of the default class SLI 260.

In addition, all flows contain a pointer sli that points to an SLI structure that controls its operation on the interface. In FIG. 3, for simplicity, only the sli back pointer for flow 2 235 is shown.

4 and 5 illustrate the operation of a procedure for processing the arrival of a new packet for the scheduling method of the present invention. Although the steps of FIG. 4 are represented by declarations of the C computer language using the fields as described in FIG. 2, the invention is not limited to this computer language.

Referring to FIG. 4, when the data communication device processes the arrival of a packet to the scheduler of the interface, it calls processing PktArrival () at step 300.

Pkt is a transmission target packet including a pointer and a length of the packet.

F is a pointer to the FLOW structure in which the packet is classified.

I is a pointer to an INTF structure that is routed over to send the packet.

In step 305, the method checks whether the number of queued packets on packets of flow F exceeds the maximum number of buffers allowed for the service class of flow F. In such a case, it is incremented in step 310 and the packet is discarded in step 315.

Otherwise, at step 320, the newly arrived packet is queued on the PacketQ queue of flow F. The q_enq () function of the method takes a pointer to QITEM as its second independent variable. In the case of step 320, it is assumed that the Pkt structure has QITEM as its first element.

In step 325, the bActive boolean of the flow F is checked. If the flow is already marked active, no additional processing is required upon packet arrival, and processing skips to step 380 (FIG. 5). Otherwise, the flow needs to be made active and is introduced into a data structure similar to FIG. 3 at step 330.

Referring to FIG. 5, at step 335 it is checked whether the flow belongs to the default service class. Otherwise, the method proceeds to step 340, where the flow is queued on the flowlist QUEUE of that (non-default, prioritized) SLI. If the QITEM in pq DRRITEM of the flow is used to link the flows of the same SLI together, the prioritized SLI is also marked as active in step 345, and the count of active flows (nflow field of SLI structure 170) is incremented. .

Subsequent to step 345, in steps 350, 355, and 360, the method checks whether the newly activating flow is in the overbooked state of the service class. Each flow is associated with a normalized reservation rate (nrr) expressed in bits per second. This is the bandwidth reserved for the flow. The method allows the operator to build and introduce flows in a state where excess reservation, i.e., the sum of introduction flow reservation rates exceeds the capacity allocated to the class of service. The capacity is allocated by service class as a percentage. The bits per second allocated for a class of service are stored at the normalized maximum allocation rate or nmar in the field of the SLI. At any given point in time, the sum of the reservation rates of active flows is stored in the sumrev field of the SLI at step 350. When this exceeds the rate allocated for the class nmar in step 355, the SLI is indicated as being in an overbooked state in step 360. The operation is restarted at step 365.

Whether new activation of the flow is done on the pq DRR queue or not, processing proceeds to step 365, where the flow is queued on the best queue guided by the beq QUEUE structure of Intf I. QITEM in the bq DRRITEM of the flow is used to link the flows on the best effort flow list.

In step 370, the flow starts its occupancy within the current DRR round with its depth set equal to the flow to which the quantum is assigned. In this embodiment, all flows in bq (best queue) and all flows in pq (priority queue) are considered to have the same quantum. By way of example, a suitable quantum may be 512 bytes. The quantum should be chosen smaller than the maximum ethernet packet rate (1500 bytes), but not too small so that an excessive number of DRR rounds are not needed to increment the depth for the size of the packet. Note that the flow within prioritized SLIs is considered to be in two different DRR queues, namely, its own class prioritization queue (linked via pq) and the best-in-class DRR queue (linked via bq). shall. Depisit for both DR queues is initialized.

In step 375, the default SLI is marked as active because the flow was added to the best effort flow list. The count of active flows on the default SLI is incremented.

In step 380, it is checked whether the flow is in an overbooked state. When a flow is activated and there are other active flows in the flow service class that already have their reserved rates exceeding the link's allocated capacity for that service class, the flow is in an overbooked state. The method of the present invention is unique in that it maintains the overbooked state of these flows and counts the arrivals of packets in the overbooked state.

A packet that arrives to discover if service classes are in an overbooked state causes the count of "Overbooked packet arrivals" to be incremented in step 30.

Step 395 terminates packet arrival processing.

The flow in which the packet is classified is now inserted into the data structure illustrated in FIG.

6, 7, 8, 9 and 10 illustrate a method of scheduling NextBurst of packets or bytes to be transmitted. The NextBurst task is initiated when the transmission of one or more packets is complete and the data communication transmitter requests the scheduler to select the next packet or group of packets. The algorithm is expressed such that the caller of NextBurst can specify the maximum number of bytes to be transmitted (maxBurst) or the maximum number of packets to be transmitted (maxPkts). These two parameters form the parameters for NextBurst operation 400 with a pointer to the INTF interface to which the next burst will be sent.

The NextBurst routine has a number of local variables.

active_classes is a count of the number of SLIs that are active.

overlimit_classes is a count of the number of SLIs that are "overlimit". Overlimit SLI is that all flows are "overlimit". Overlimit flow is to have that traffic token bucket exceeded. The traffic token bucket measures whether the flow exceeds its reservation minimum rate.

nover is a count of the number of overlimit flows in a particular service class.

bReturn is a TRUE (ie set to 1) control flag when the method determines that the NextBurst routine should be returned.

P is a pointer to the current SLI structure that receives the bandwidth.

F is a pointer to the current flow (within P) that is provided with bandwidth.

Pkt is a pointer to the current packet of F being tested.

In step 405, the method initializes local variables, scans through all SLIs (via p_classes QUEUE in INTF), and sets the bOverlimit bit of the class to 0 (ie, FALSE).

Step 410 begins the next DRR round of the "Priority DRR Queue". This sets the local SLI pointer (P) to the head of the p_classes queue of INTF. Note that the "q_head (QUEUE)" operation returns a pointer to the head of the queue but does not remove it from the queue.

Step 415 checks whether all classes have been provided with bandwidth in the current priority class DRR round. In such a case, the P pointer becomes zero and the next class DRR round begins at step 420. In this step, step 425 is executed for each class in the interface (i.e. all SLIs linked via the P-classes QUEUE of the INTF structure with bExhausted == 1). This means that they run out of class DRR depths. The depth is incremented by the dedicated quantum at step 430, and the bExhausted flag is cleared to prepare the SLI for the next class DRR round.

Immediately completed round, the number of "overlimit" classes was accumulated in the local counter "overlimit_classes". These are classes that must wait until a later call to NextBurst to make certain of the flows suitable for forwarding the packet. In step 435, this overlimit_classes count is compared to the number of active classes, and if all classes are overlimit, NextBurst cannot forward any packets and returns to sent == 0 in step 445.

In step 440, if the last class DRR round has emptied all the queued packets such that there are no longer any active classes, NextBurst also returns to step 445. However, if there are still active classes, a new class DRR round begins by transitioning back to step 410.

Again in step 415, if the current class DRR round has not ended, processing proceeds to step 450. In step 450, if the current SLI is not marked as active, it means that it does not have an active flow, which means that it can be omitted. In this case, the method proceeds to step 455 to take the next lower priority SLI on the p_classes queue of the interface, and then to step 415.

If the current SLI (addressed to P) is active, the method proceeds to step 450, where the number of active_classes is incremented by one.

In a subsequent step 460, the SLI checks to see if the deficits in the current priority DRR round are exhausted. The P-> bExhaysted flag above is used for this purpose. In this case, this SLI cannot receive bandwidth in the current priority DRR round and the next SLI must be checked in step 455.

If not, the method continues to step 470, where the bOverlimit flag of the current SLI is checked. This flag is set when all flows in the SLI are overlimit. In this case, no bandwidth is given to the priority SLI, and the next SLI must be checked through step 455.

Otherwise, the method continues to steps 475, 480, and 485, where a local variable "FlowQP" is set depending on whether the current class is a "default" class or not. If the current CLI (P) is the default, then the relevant queue of flows for which bandwidth is to be provided is the I-> beq "best" queue of flows. If the current CLI (P) is a priority queue, then only the appropriate flows are those linked from the CLI's flowlist queue. FlowQP is set to a pointer to a dedicated QUEUE structure.

In either case, the method continues to step 490, where the number of overlimit flows in the current class is initialized to zero.

Step 495 indicates common processing points to provide bandwidth for the "Next Flow" of the current class of service. An off-sheet connector object "505" labeled "Next Flow" is referenced from FIG. In step 495, the local pointer F is set to the head of the FlowQP queue (but the flow is not queued).

Next, the method checks at step 500 that all flows of the current SLI have their packets emptied, ie F is null. Otherwise, the method continues to step 525 of FIG. 7.

In step 500, if all flows of a given service class are determined to be exhausted (ie, F == 0), the service class is marked as inactive in step 510, and the total number of active service classes is reduced. In step 515, the method checks the bReturn flag set in step 795 when the current attempt of the NextBurst method has sent a good maximum number of packets. If so, the NextBurst method ends at step 520. Otherwise, processing of the next service class continues at step 455.

In step 525, the method checks whether all flows in the current service class are overlimit. In such a case, the method proceeds to step 530, where the class itself is marked as overlimit, and the number of overlimit classes for the implementation of this attempt of the NextBurst method to step 455 to check the next service classes Is detected.

If the class itself is not overlimit, the method proceeds from step 525 to step 535. This starts processing the "Next Packet" of the next packet on the current flow. The local pointer Pkt is set to the head of the packet queue of the current flow, but the packet itself is not removed from the queue.

In a subsequent step 545, the Pkt pointer is checked. If this is NULL, all packets in the current flow are transmitted and the method proceeds to step 585. Step 585 updates the data structure and statistics of FIG. 2 for the case when the flow becomes inactive. The flow is removed from both the priority DRR queue (ie, SLI flowlist QUEUE) and the best-in-class DRR queue (from the "beq" QUEUE of INTF). Step 585 also decreases the sum of the sum of the reservation rates of all active flows in the class, i. In step 590, if P-> sumrev falls below the "normalized maximum allocation rate (P-> nmar)", the class is no longer considered to be in an overbooked state. In this case, the P-> Overbooked flag is cleared in step 595. In each case, after the check in step 590, the method continues to the next flow in the current SLI in step 495.

Again in step 545, if the current Pkt pointer is not pressed, the method proceeds to step 550. In this step, it is checked whether the bReturn flag is set by step 765, in which case the method returns to step 560. If the bReturn flag has not yet been set, processing continues to step 555.

Step 555 checks whether sending the packet causes the NextBurst routine to exceed the maximum number of bytes allowed in the NextBurst routine call. The total bytes sent currently being executed are kept in the "sent" local variable. In this case, NextBurst returns to step 560 without transmitting the current packet.

If step 555 does not detect that the maximum burst per routine call has not been exceeded, the method continues to step 565 where the priority DRR queue "depitst" is checked. If the packet length exceeds the depth count of the priority "class" DRR item (i.e., P-> cq. Depth), the current class is exhausted its allowed transmissions in this priority DRR round. In this case, the service class is displayed with the bExhausted flag set to 1 (true), and the method proceeds to step 455 to check the next service class.

However, if the service class DRR depth is not exhausted in step 565, the method begins again in step 575, where the maximum rate token bucket for the flow is updated. The process for updating the token bucket (tokbkt_update ()) adds the appropriate number of tokens to the token bucket count based on two of the CPU processor ticks that have elapsed from the last update. Each "token" in the token bucket grants the right to send one byte.

In step 580, the method compares the packet length with the number of tokens in the updated maximum rate token bucket (F-> maxBkt). If the tokens are insufficient, the method proceeds to step 600. Here, the method increments the count of such "overMaximum" packet scheduling attempts and increments the number of "overlimit" flows (local variable "nover") in the current service class. In step 605, a task "MoveFlowToEnd ()" is attempted to move the overlimit flow to the end of its current flow queue. The flow is not allowed to send packets until a subsequent call to NextBurst where enough time may elapse to add more tokens to its maximum rate token bucket. The method transitions from step 605 to step 495 to handle the next flow in the current class.

If the method passes the maximum rate token bucket limiter at step 580, this continues to step 610, which is the connector that leads to the NextBurst process of FIGS. 8 and 9.

Step 620 is a continuation of NextBurst processing from FIG.

625 checks whether the current class provided with the bandwidth is the default class. If not, step 630 updates the reservation rate "traffic" token bucket for the flow, and step 635 checks if the flow is currently below its reservation rate. Otherwise, the method indicates at step 640 that the packet has exceeded its traffic rate and moves the flow to the string of its priority DRR list at step 645, moving MoveToToEnd as described in steps 700 to 720. Try the sub () method. The flow is not allowed to transmit traffic in excess of its traffic rate token bucket within the bandwidth provided for its prioritized service class. This can only be transmitted when the bandwidth is provided to a default class of service. After moving the flow to the end of the flow list of the CLI, step 650 proceeds to step 495 to process the next flow in the current class.

If step 635 determines that the flow does not exceed its reserved traffic rate limit, it proceeds to step 655. This step checks whether the current packet for the flow exceeds the depth for the flow-specific DRR round, i.e., F-> pq.deficit. In such a case, the routine proceeds to step 660 because the flow must be backlogged until the next flow-specific DRR round. In step 660, the "pq" DRR item depth of the flow is increased by quantum. In step 665, the MoveFlowToEnd sub-method is attempted to move the flow from front to back of the flow list of the current class, and processing continues to the next flow in step 495.

In step 625, if the current class provided with bandwidth is the actual default class, then the method continues to step 675. Steps 675 to 690 are similar to the method used for non-default classes. Step 675 compares the length of the packet with the depth of the flow on the best-in-class DRR list (F-> bq.deficit). If the packet length is less than the depth of flow, the method continues to step 725. However, if the length of the next packet exceeds the best-in-class DRR depth, the method continues to step 680. In step 680, the best DRR depth of the flow is increased by the best DRR quantum of the flow (F-> bq.quantum). In step 685, the flow is moved to the end of the flow list of the class by attempting the MoveFlowToEnd method, as described in steps 700-720. After step 685, the method returns via “Next Flow” label 505 to process the next flow in step 495.

Step 700 is the beginning of the MoveFlowToEnd submethod attempted by steps 605, 645, 665 and 695 above. The MoveFlowToEnd method is tried for a specific flow F and for a specific DRR queue FlowPQ. Recall that a flow can be a member of two different DRR queues and likewise have two different DRRITEMs 160, F-> pq and F-> bq. The MoveFlowToEnd method simply selects the appropriate DRRITEM to be changed. In step 705, the DRR queue pointer FlowPQ is checked to see if it is the best queue. In that case, the method proceeds to step 715, where the flow is first dequeued from the beginning of the best-in-class DRR queue (q_remove (FlowPQ, & P-> bq)) and then queued to the tail of that DRR queue. State (q_enq (FlowPQ, & P-> bq)). The MoveFlowToEnd sub method then terminates at step 720. If step 705 determines that the priority DRR queue has changed instead of the best-in-class DRR queue, the method proceeds to step 710, where the flow is first removed from the head of the priority DRR queue and then queued back to the tail. Becomes

Referring now to FIG. 10 of the MextBurst method, if step 655 or 675 determines that the flow has sufficient depth in the current flow DRR round to transmit the current packet, then control is passed to step 725 (FIG. 9). To. The packet is actually dequeued from the head of the flow packet queue in step 725.

Step 730 actually attempts an operation "send ()" to send the packet over the transmission link. The local variable sent accumulates the number of bytes sent via the "send ()" operation.

Steps 735, 740, 745, and 750 update the dedicated flow DRR queue by determining the packet length sent directly from the "depitsit" count of the dedicated DRRITEM. For the default class, this is F-> bq (step 740), and for non-default classes this is F-pq. In either case, processing resumes at step 750, where the DRR depth (P-> cq) for the class level DRR queue is reduced by the packet length.

In step 755, the number of statistics is updated. The traffic rate and maximum rate token buckets of the flow have one removed token for each transmitted byte. The current statistics, plus the interval, are incremented for both flow-specific and class-specific statistics.

Step 760 increments the count (sentpkts) of packets transmitted in this attempt of NextBurst. If this is lower than the maximum number of packets requested for transmission (parameter maxPackets), the process resumes at the next packet in the current flow, which is indicated via the "NextPacket" connector for step 535. If the maxPackets count is reached, in step 765 the control flag "bReturn" is set to TRUE. Operation of the method then returns to step 540 to consider the next packet. The " bReturn " flag set in step 765 is tested for this case after the method properly updates the data structures of FIG. 2 when the packet just sent is the last packet of the active class of service.

It should be noted that the above-described embodiments are merely illustrative of the principles of the present invention. Those skilled in the art can implement various other changes and modifications within the scope and concept of the invention while embodying the principles of the invention.

Claims (21)

A method of scheduling transmission of packets over a data communication link, the method comprising: a) receiving a plurality of packets of a data flow, b) organizing the flow into a class of service; c) scheduling a transmission bandwidth of the service class to a selected limit; d) forwarding packets of the flow that meet the selected limit; e) identifying a default class having a default class bandwidth, f) forwarding packets using both the bandwidth assigned to the service class and the bandwidth assigned to the default class. A method of selecting a next packet for transmission on a network among a plurality of prioritized packet queues, the method comprising: a) assigning each queue in the plurality of prioritized packet queues a quantum of allocated bandwidths, b) assigning a deficit indicative of the amount of allowed data to be forwarded by the queue to each queue in the plurality of prioritized packet queues; c) selecting a next packet for transmission from a queue having a high priority and a depth value exceeding the size of the next packet; d) reducing the depth of the queue selected in step c) by the size of the next selected packet; e) where all backlogged queues in the plurality of prioritized packet queues have insufficient depth to forward the next packet, the depth of the quantum in the depth of each of the backlogged queues. Adding a value, whereby a new round of selection from among the set of prioritized packet queues is initiated. The method of claim 2, f) if all cues are empty, add the value of the depth to the value of the quantum in each empty queue, whereby a new round of selection from the set of prioritized packet queues begins. Further comprising, the selection method. The method of claim 1, Scheduling the received packets of the flow into a flow-by-flow queue. The method of claim 1, Prior to organizing the flow into a class of service, determining whether the data flow is below a maximum rate limiter and scheduling packets of the flow if the data flow is below a maximum rate limiter. The method of claim 5, wherein Discarding packets exceeding the maximum rate limiter. The method of claim 5, wherein Queuing packets exceeding the maximum rate limiter until the maximum rate limiter is no longer exceeded. The method of claim 1, And the step f) further includes forwarding only packets that exceed the selected limit on the bandwidth allocated to the default class. The method of claim 1, And the step f) further includes forwarding packets under an instantaneous overbooked condition on the bandwidth allocated to the default class. The method of claim 1, And d) further comprises scheduling the packets into a class-specific packet queue. The method of claim 10, Scheduling the packet to a class-specific queue further comprises using a process queuing algorithm. The method of claim 11, And the process queuing algorithm is a discrete round robin algorithm. The method of claim 11, And the process queuing algorithm is a first-in, first-out algorithm. The method of claim 1, wherein the d) step, d-iii) scheduling the packets into one of a plurality of class-specific packet queues; d-ii) scheduling bandwidth of the transmission link between the plurality of class-specific packet queues according to a second process queuing algorithm. The method of claim 14, And the second process queuing algorithm further comprises a weighted process queuing algorithm. The method of claim 1, And assigning a scheduling priority to each class. A method of scheduling transmission of packets over a data communication link, the method comprising: a) receiving a plurality of packets of a data flow, b) organizing the flow into a class of service; c) scheduling packets to the service class queue having a service class limit if the flow limit has not been exceeded; d) sending packets from the service class queue while the service class limit is not exceeded; e) defining a default class, g) sending packets on the queue for the default class that exceed the service class limit, Whereby packets of the flow are transmitted via both a service class queue and a default class queue. A scheduling apparatus for scheduling transmission of packets over a data communication link, comprising: a) means for scheduling received packets of the data flow into a per-flow queue, b) means for organizing the scheduling packets into a class of service; c) means for scheduling the transmission bandwidth of the class of service to a selected limit; d) means for forwarding packets of the flow that meet the selected limit; e) means for identifying a default class having a default class bandwidth; f) means for forwarding packets using both the bandwidth assigned to the class of service and the bandwidth assigned to the default class. The method of claim 18, g) means for determining if the data flow is below a maximum rate limiter, If the maximum rate limiter is not exceeded, the received packets are forwarded. The method of claim 19, And means for discarding packets exceeding the maximum rate limiter. The method of claim 19, And means for queuing packets exceeding the maximum rate limiter until the maximum rate limiter is no longer exceeded.