CN103733582B - Method and apparatus for the expansible packet scheduling of high-volume conversation - Google Patents

Abstract

A kind of equipment, comprising: multiple queue, it is for caching the multiple bags corresponding to multiple sessions；Scheduler, it is for dispatching out bag from different queue, forwards in the exit of each corresponding queue with the end time based on each bag；Outbound, it is couple to described scheduler, and the bag that scheduling is gone out by the bandwidth for being shared with all queues transfers from all queues, the wherein said end time is that dynamic calculation goes out based on the amount of bandwidth distributing to corresponding queue, and wherein said queue is assigned with the weights of correspondence to share total bandwidth.

Description

Method and apparatus for scalable packet scheduling of a large number of sessions

Cross References to Related Applications

Not applicable.

About Federal Sponsored

Statement of Research or Development

Not applicable.

Refer to Microfiche Addendum

Not applicable.

technical field

none

Background technique

Modern communication and data networks consist of nodes that transmit data throughout the network. These nodes may include routers, switches, bridges, or combinations thereof that transmit individual data packets or data frames in the network. Nodes can forward multiple packets corresponding to different sessions or flows in parallel. Packets for different sessions or flows may be received through multiple ingress ports and forwarded through multiple egress ports of the node. In addition, packets of different flows can be enqueued or buffered for a period of time in corresponding queues or buffers, and then the packets are sent out from the node. Packets in different queues can be forwarded over the same egress link, and they share the link's available or assigned bandwidth. The scheduler at the node is usually used to schedule and coordinate the forwarding of packets buffered in different queues on the same egress link, for example, the implementation method is to select from different queues at different time slots specified by the scheduler Bag.

Contents of the invention

In one embodiment, the invention includes an apparatus comprising: a plurality of queues for buffering a plurality of packets corresponding to a plurality of sessions; a scheduler for routing the packets from different queues scheduled to be forwarded at the egress of each corresponding queue based on the end time of each packet; and an egress link coupled to the scheduler and used to forward packets from all queues at a bandwidth shared by all queues The packets scheduled in , wherein the end time is dynamically calculated based on the amount of bandwidth allocated to the corresponding queue, and wherein the queue is assigned a corresponding weight to share the total bandwidth.

In another embodiment, the present invention includes a network component comprising: a receiver for receiving a plurality of packets corresponding to a plurality of sessions; one or more storage units for storing A plurality of queues acting to buffer packets of a corresponding session; a logical unit for calculating the end time of each detected packet at the head of the corresponding queue, and assigning the detected packets to a calendar time slots of the queue to forward the packets in ascending order of end time; and a transmitter for transmitting the plurality of packets assigned to the time slots in order of the time slots through the output link. In yet another embodiment, the present invention includes a network device implementing a method comprising: scanning multiple queues of multiple packet sessions to detect any backlogged packets in the queues; A packet is assigned to a plurality of time slots in a calendar table in ascending order of a plurality of end times calculated for the packet in terms of the bandwidth allocated to the packet session; the time slots in the calendar table are scanned sequentially slots to detect the assigned packets and sequentially forward the detected assigned packets on the shared egress link.

These and other features will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings and claims.

Description of drawings

For a more complete understanding of the present invention, reference is now made to the following brief description taken in conjunction with the drawings and detailed description, wherein like reference numerals refer to like parts.

Figure 1 is a schematic diagram of an embodiment of a scheduler architecture.

Figure 2 is a schematic diagram of one embodiment of a typical calendar queue.

FIG. 3 is a schematic diagram of another embodiment of a calendar queue with poor scalability.

Figure 4 is a schematic diagram of another embodiment of a calendar queue with improved scalability.

Figure 5 is a schematic diagram of an embodiment of a multi-level scheduler hierarchy.

Fig. 6 is a schematic diagram of an embodiment of a multi-level scheduling scheme.

Figure 7 is a diagram of one embodiment of a packet scheduling workload.

Figure 8 is a diagram of an embodiment of scheduling fairness.

Figure 9 is a diagram of one embodiment of slots scanned for sending packets.

Fig. 10 is a flowchart of an embodiment of a packet scheduling and forwarding method.

Figure 11 is a schematic diagram of an embodiment of a network element.

Figure 12 is a schematic diagram of one embodiment of a general purpose computer system.

detailed description

It should be understood at the outset that although an illustrative implementation of one or more embodiments is provided below, the disclosed systems and/or methods may be implemented using any number of techniques, whether currently known or in existence. The invention should in no way be limited to the illustrative implementations, drawings, and techniques described below, including the exemplary designs and implementations illustrated and described herein, but may be limited within the scope of the appended claims and their equivalents. Modified within the full range of effects.

Disclosed herein is a system and method for improved packet scheduling forwarding, eg, at network nodes. The scheduler can be used to efficiently schedule the forwarding of a plurality of packets corresponding to a plurality of sessions and buffered in a plurality of corresponding queues at a network node. Packet scheduling policies or algorithms can be implemented to deal with scalability issues caused by skipping idle queues, which exist, for example, when a large number of sessions are processed and a large fraction of the sessions are idle. The packet scheduling strategy or algorithm may be used to skip a bounded number of idle queues to serve or forward packets in the queues. The algorithm may have a time complexity of O(1) for all or multiple packet placements or conditions. Similar to other algorithms, such as the Weighted Fair Queuing (WFQ) algorithm, this algorithm can also have a fairness property to process packets of different sessions. The strategy or algorithm may be effectively implemented using software only, using software with limited hardware support, or using hardware.

Figure 1 illustrates one embodiment of a scheduler architecture 100 that may be used to schedule packets of different sessions or flows for forwarding. The scheduler architecture 100 may be implemented in a network component or node, such as a router, bridge, switch, or other component in a network for forwarding packets or frames. The packets may belong to different sessions or flows that may be received or generated at that network component. The scheduler architecture 100 may include a plurality of queues or buffers 110 , a scheduling unit or scheduler 120 coupled to all queues 110 , and an output or egress link 130 coupled to the scheduler 120 . Queue or buffer 110 may be used to buffer or temporarily store incoming or generated packets until the packet can be sent by scheduler 120 to egress link 130 for transmission. The scheduler 120 may select packets from different queues for transmission via the same shared egress link 130 in a certain order based on a scheduling algorithm, which may ensure fairness in the packet selection process as described below. Egress link 130 may be used to forward or transmit all packets of different sessions, and may have a fixed and assigned bandwidth, which may be shared among all sessions.

Generally, a scheduling algorithm can ensure fairness in the process of part allocation of the total bandwidth of the egress link 130, such as a WFQ scheduling algorithm. Based on WFQ, n sessions (n is an integer) can share an output link with bandwidth R, so each session i has a weight w _i . Each session can have a guaranteed ratio in WFQ can simulate a generalized process sharing (GPS) fluid model and define a virtual time where V(t)=0 when there is no packet backlog in the session. In other cases, Wherein B(t ₀ , t) is a set of backlog sessions in [t ₀ , t]. WFQ can also define a virtual start time for the kth packet on session i and the corresponding virtual end time in is the arrival time of the kth packet on session i, and where is the length of the kth packet on session i. The virtual end time is determined when the packet is queued, eg, when the packet is added to the queue. The packets in the queue are serviced in ascending order of the virtual end time of the backlog packets. Different schemes can also be used to reduce the complexity of WFQ, for example, using calendar queues or using self-clocked fair queuing (SCFQ). SCFQ can reduce the virtual time overhead of WFQ and use the virtual end time of the packet being delivered as the current virtual time.

FIG. 2 is an embodiment of a typical calendar queue 200, which can be used to reduce the computational complexity of the WFQ scheduling algorithm. A calendar queue may also be called a calendar table. Calendar queue 200 may include multiple time slots corresponding to multiple sessions or queues. The slots may be traversed in sequence to forward a corresponding assignment packet at each slot. The time slots may be processed in a recursive manner, and the specific operation is to restart from the first time slot (slot 0) after the last time slot (slot 9) has been processed. Although ten time slots (from 0 to 9) are shown in FIG. 2, calendar queue 200 may include a considerable number of time slots, for example, up to about 1,000,000 time slots or more. WFQ can be used to assign ordered backlog packets to the slots, and the backlog packets can then be forwarded according to the sequence of assigned slots.

One or more backlog packets (eg, P1, P2, P3, P4, etc.) may be assigned to each slot using WFQ. Backlog packets may be scheduled to be serviced (or forwarded) at entries or slots of the calendar queue 200 determined by corresponding quantized end times. The calendar queue 200 can be traversed iteratively, wherein packets assigned to time slots can be serviced if present. At each current time, one of the time slots may be scanned out for an assignment packet. If a packet is found, the packet may then be transmitted from its corresponding queue on the shared output link before moving to the next time slot in the calendar queue 200 . In other cases, the next slot may be scanned for dispatching packets. This process can be repeated in a circular sequence, wherein all time slots in the calendar queue 200 can be traversed multiple times in sequence. On-the-fly (eg, real-time) computational complexity of WFQ can be reduced using calendar queue 200 . However, the calendar queue 200 can be quite sparse, eg, it includes a large number of unassigned or empty time slots in an empty queue, which can still be scanned for assigned time slots. This can make scalability very poor and can reduce overall performance.

An embodiment of another calendar queue 300 that is less scalable is shown in FIG. 3 . Calendar queue 300 may include approximately 1,000,000 time slots (from 0 to 999,999), of which only the first time slot (slot 0) may be assigned a packet. Unassigned slots may correspond to empty queues that do not include backlog packets. This may be because not all sessions or flows are active all the time, and therefore some of the queues may be empty. Traversing this large number of unassigned or empty slots in calendar queue 300 may require considerable overhead, eg, when done in a software implementation. At this point, with only one packet assigned to a slot, only about one millionth of the total bandwidth may be used, and the rest of the bandwidth may be wasted, although the remaining empty slots are still being scanned .

To improve the scalability and performance of packet scheduling and forwarding across different sessions, an improvement to the scheduling algorithm is required such that the algorithm can assign a larger fraction of the time slots in the calendar queue, and thus obtain a denser calendar queue. This may result in better utilization of the overall bandwidth by roughly scanning the assigned slots in the calendar queue for non-empty packets, including backlog packets.

Specifically, if there is no packet backlog at the queue, then the new virtual time of the kth packet on session i can be defined as V _i ^k =0. ^{Otherwise, Vik} _is set equal to the end time of the packet being served. In the WFQ case, a packet's start time and end time can be calculated at the latest when the packet moves to the head of its queue or exits, rather than during the queuing time. This improved algorithm can define a virtual start time and the corresponding virtual end time where B is the set of all active sessions when the packet moves to the head of the queue. The remaining parameters are similar to the corresponding parameters described above.

According to the algorithm proposed above, only packets at the head of the corresponding queue are assigned to entries in the calendar queue or table determined by the end time. Thus, most slots in the calendar queue may have a packet assigned to them, and thus, the slots may be traversed more quickly to find packets to be serviced. Calendar queues may still include unassigned slots of empty queues in some cases, but the number of such slots can be greatly reduced, and thus the performance and scalability of packet scheduling and forwarding can be greatly improved on the improvement. This can also greatly improve bandwidth utilization, where most or a larger portion of the shared output link bandwidth can be used to transmit packets at different time slots.

As mentioned above, this improved algorithm can provide work-saving strategies.

Such a work-saving strategy may correspond to O(1) work-saving scheduling.

Furthermore, packets can be assigned to time slots of calendar queues or tables without the use of physical timers. The end time can also be calculated dynamically because the coefficient used to calculate the end time Can vary based on the amount of bandwidth allocated to the session instead of using a fixed value like in WFQ. Dynamic changes in the coefficients may reflect changes in sessions switching between active (including backlog packets) and idle (excluding backlog packets). This can make the calendar table denser regardless of the number of sessions considered. On average, or in general, about S time slots can be scanned to serve about S packets (S is an integer). The algorithm can also support Quality of Service (QoS) requirements, where different packet sessions may have different weights or priorities when sharing egress link bandwidth.

FIG. 4 shows another embodiment of a log queue 400 with improved scalability obtained based on the above-mentioned improved algorithm. Log queue 400 may include approximately 1,000,000 time slots (from 0 to 999,999), most or a large number of which may be assigned a packet at the head of the corresponding queue. Calendar queue 400 may include no unassigned slots, or a negligible number of unassigned slots, corresponding to an empty queue that does not include backlog packets. Calendar queue 400 is denser than calendar queue 300 obtained using WFQ, and thus can be processed with little computational overhead, eg, most of the time using software to do so. In other embodiments, hardware may also be used instead of software or both.

The above algorithm can also be implemented in a multi-level queuing hierarchy, where a queue at a certain level can be coupled to multiple queues at lower levels. As such, packets originating from lower-level queues can be forwarded to higher-level queues for scheduling using the above-described improved scheme. The schedulers at each stage can implement this improved scheduling algorithm to forward packets from different queues via shared output links. Figure 5 shows one embodiment of a multi-level scheduler hierarchy 500 in which an improved scheduling scheme can be implemented at each level. The multi-level scheduler hierarchy 500 may be implemented in network components or nodes, such as routers, bridges, switches, or other components used in a network to forward packets or frames. The packets may belong to different sessions or flows that may be received or generated at that network component. Alternatively, the multi-level scheduler hierarchy 500 may be implemented in multiple nodes, and the multiple nodes may be coupled in a multi-level hierarchical form, for example, in a tree topology. As such, packets may belong to different sessions or flows that may be forwarded along nodes at different levels.

The multi-level scheduler hierarchy 500 may include at least two levels of queues and corresponding schedulers, where each level may be based on the scheduler architecture 100 . As such, the first-level scheduler architecture 501 may include a plurality of first-level queues or buffers 510 (queues 4, 5, and 6), a first-level scheduling unit or scheduler 520 coupled to all first-level queues 510, and a first stage output or egress link 530 coupled to the first stage scheduler 520 . Additionally, a second stage scheduler architecture 502 is coupled to the first scheduler architecture 501, which may include a plurality of second stage queues or buffers 512 (queues 1, 2, and 3), coupled to all second stage A second level scheduling unit or scheduler 522 of the queue 512 and a second level output or egress link 532 coupled to the second level scheduler 522 . The second-level scheduler architecture 502 may be coupled to the first-level scheduler architecture 501 by coupling one of the second-level queues 512 (queue 3 ) to the first-level egress link 530 . Components of the first level scheduler architecture 501 and similar components in the second level scheduler architecture 502 may be similarly used for corresponding components of the scheduler architecture 100 .

The first-level scheduler architecture 501 and the second-level scheduler architecture 502 can be implemented in the same network node. Alternatively, the first level scheduler architecture 501 may be implemented in a first node of the tree, and the second level scheduler architecture 502 may be implemented in a second node at the next higher level in the tree, the second node being coupled to to the first node. First-level scheduler 520 may use first-level calendar queues 540 to implement the improved scheduling algorithm described above to efficiently schedule packets and send them from first-level queues 510 (queues 4, 5, and 6) via first-level egress Link 530 is forwarded to second level queue 512 (queue 3). Similarly, second-level scheduler 522 may use second-level calendar queues 542 to implement the improved scheduling algorithm described above to efficiently schedule packets and send them from second-level queues 512 (queues 1, 2, and 3) at forwarding on the secondary egress link 532. As such, first level calendar queue 540 and second level calendar queue 542 may be fairly dense, eg, similar to calendar queue 400 .

Figure 6 illustrates an embodiment of a multi-level scheduling scheme 600 at the multi-level scheduler hierarchy. The multi-level scheduler hierarchy may include three levels of queues and corresponding schedulers (not shown), wherein each level may be based on the scheduler architecture 100 . The three-level queues may include first-level queues including queues 4 to 12, which may have a plurality of corresponding weights (w _i ) as indicated in FIG. 6 . The third-level queue may also include a second-level queue and a third-level queue 0, the second-level queue includes queues 1, 2, and 3, and the queues may also have corresponding weights (w _i ). The first-level queue and the second-level queue can have corresponding first-level schedulers and second-level schedulers (not shown), and these two schedulers can implement the above-mentioned improved scheduling algorithm (using a corresponding calendar table) so that Forward packets on shared egress links (eg, to higher-level queues). Specifically, packets of queues 4, 5, and 6 can be scheduled and forwarded to queue 1 on the shared link, packets of queues 7, 8, and 9 can be scheduled and forwarded to queue 2 on the shared link, And packets for queues 10, 11 and 12 can be scheduled and forwarded to queue 3 on the shared link. Additionally, packets from queues 1, 2, and 3 can be scheduled to be forwarded to queue 0. Packets at queue zero can then be forwarded on the same output link.

One embodiment of a packet scheduling workload 700 corresponding to the multi-level scheduling scheme 600 is shown in FIG. 7 . The packet scheduling workload 700 is represented as a curve of multiple computed averages of instructions in the packet dequeue process versus multiple calendar queue slot sizes in bytes. The instructions used to dequeue packets (ie, remove packets from the head or exit of the queue) are implemented using the platform i686 processor. The graph shows that the number of instructions drops from about a 50 byte slot size all the way down to about a 500 byte slot size. This means that the average number of instructions in the dequeue process may be related to the slot size used in the calendar queue. However, for the same slot sizes examined, it was found that the average number of instructions (curve not shown) in the process of queuing a packet or adding a packet to a queue was a fixed value of about 32 instructions. This means that the average number of instructions during packet queuing or enqueuing (ie, adding a packet to the start or entry of a queue) may not be related to the slot size in the calendar queue.

An embodiment of scheduling fairness 800 for multi-level scheduling scheme 600 is shown in FIG. 8 . Scheduling fairness 800 is represented as multiple curves of multiple fairness ratio calculations - calendar queue slot size (in bytes) as used above. Specifically, the fairness ratio is calculated for queues 1 to 2 in the multi-level scheduling scheme 600 . Ideally, the fairness ratio should be equal to the ratio of the weight of queue 1 to the weight of queue 2, that is, 5/4=1.25. The two curves shown are for the following two cases: 250 packets are served in the queue 1 calendar table; 500 packets are served in the queue 2 calendar table. The curve shows that the larger the number of packets served, the closer the fairness ratio is to the ideal fairness ratio. Furthermore, it was found that there is an approximately equal fairness ratio between the different slot sizes in the case of serving 500 packets. Fairness in the case of serving 1,000 packets (not shown) can also be calculated in the same range of values for slot size, and is found to be roughly equal to the ideal fairness ratio of 1.25. This shows that as the number of packets increases, the fairness ratio of the improved scheduling algorithm is closer to the ideal or required fairness ratio between queues.

FIG. 9 illustrates one embodiment of a scan slot number 900 for sending packets in a multi-level scheduling scheme 600 . The number of scan slots 900 is represented as two curves of number of scan slots - calendar queue slot size in bytes as used above. Specifically, the number of scan slots shown is for servicing 1,000 packets in the calendar queue. These two curves correspond to the actual value of the number of slots scanned and the corresponding estimated value based on theoretical analysis. It was found that the two values are approximately equal, and therefore the two curves coincide. These curves indicate that the number of scan slots decreases as the calendar queue slot size increases, allowing more packets to be served per slot. Therefore, increasing the slot size increases the rate at which packets are dequeued from them, and improves bandwidth utilization and scalability.

FIG. 10 shows an embodiment of a packet scheduling and forwarding method 1000, which can be used to schedule and forward multiple packets of multiple sessions in parallel, ie, by sharing the same egress link bandwidth. The packet scheduling and forwarding method 1000 can be obtained based on the above-mentioned improved scheduling algorithm, and can be implemented by one network node or multiple network nodes in a multi-level queuing or scheduling scenario. The method can begin at block 1010, where a plurality of queues can be scanned to detect a backlog of packets in the queues. At block 1020, the plurality of packets detected at the head of the queue may be assigned to a plurality of time slots in a calendar table in ascending order of packet end times that are dynamic with respect to bandwidth allocated for the packets' sessions calculated, as described above. At block 1030, the time slots in the calendar queue may be scanned sequentially to detect assignment packets. At block 1040, the detected assignment packets may be forwarded in sequence on the same egress link or port. Blocks 1010 to 1040 may be repeated to continuously forward received/generated and enqueued packets in the network nodes.

FIG. 11 shows an embodiment of a network unit 1100 , which can be any device that transmits and processes data through a network, for example, the label switching system 100 . For example, the network unit 1100 may be located in any one of the above-mentioned network components, for example, in any one of RP, LC, edge node, forwarding node or server. The network unit 1100 may include one or more ingress ports or units 1110 coupled to a receiver (Rx) 1112 for receiving packets, objects or type length values (TLVs) from other network components. Network unit 1100 may include logic unit 1120 to determine which network components to send packets to. Logic unit 1120 may also implement or support dynamic configuration and forwarding method 1200 , and service reachability forwarding scheme 900 and/or 1000 . Logic unit 1120 may be implemented using hardware, software, or both. The network unit 1100 may also include one or more egress ports or units 1130 coupled to a transmitter (Tx) 1132 for transmitting packets or data to other network components. The components of network element 1100 may be arranged as shown in FIG. 11 .

The network components described above may be implemented on any general-purpose network component, such as a computer or network component with sufficient processing power, memory resources, and network throughput to handle the necessary workload experienced. Figure 12 illustrates a typical general-purpose network component 1200 suitable for implementing one or more embodiments of the components disclosed herein. Network component 1200 includes a processor 1202 (which may be referred to as a central processing unit or CPU) in communication with storage devices including: secondary memory 1204, read only memory (ROM) 1206, random access memory (RAM) ) 1208, input/output (I/O) device 1210, and network connection device 1212. Processor 1202 may be implemented as one or more CPU chips, or may be part of one or more application specific integrated circuits (ASICs).

Secondary storage 1204, typically consisting of one or more disk drives or tape drives, is used for non-volatile storage of data and is used as an overflow data storage device if RAM 1208 is not large enough to hold all working data. Secondary storage 1204 may be used to store programs that are loaded into RAM 1208 when those programs are selected for execution. ROM 1206 is used to store instructions and possibly data that are read during program execution. ROM 1206 is a non-volatile storage device that typically has a small storage capacity relative to the larger storage capacity of secondary storage 1204 . RAM 1208 is used to store volatile data and possibly also to store instructions. Access to both ROM 1206 and RAM 1208 is typically faster than access to secondary storage 1204 .

The present invention discloses at least one embodiment, and changes, combinations and/or modifications made by those skilled in the art to the embodiments and/or the features of the embodiments are within the scope of the present invention. Alternative embodiments resulting from combining, integrating, and/or omitting features of the described embodiments are also within the scope of the invention. Where a numerical range or limit is expressly stated, such expressed range or limit should be understood to encompass iterative ranges or limits of similar magnitude falling within the expressly stated range or limit (e.g., from about 1 to about 10 Including 2, 3, 4, etc.; greater than 0.10 includes 0.11, 0.12, 0.13, etc.). For example, so long as a numerical range having a lower limit _R1 and an upper limit _Ru is disclosed, any number falling within that range is also specifically disclosed. In particular, the following numbers within said range are specifically disclosed: R=R _l +k*(R _u -R _l ), where k is a variable ranging from 1% to 100% in increments of 1%, i.e., k 1%, 2%, 3%, 4%, 7%, ... 70%, 71%, 72%, ... 97%, 96%, 97%, 98%, 99% or 100%. Furthermore, any numerical range defined by two R numbers as defined above is also specifically disclosed. Use of the term "optionally" with respect to any element of a claim means that the element is either required or not required, both alternatives being within the scope of the claim. The use of the broader terms "comprising", "comprising" and "having" should be understood as supporting the broader terms "consisting of", "consisting essentially of" and "consisting substantially of" small term. Accordingly, the scope of protection is not limited by the description set out above but is defined by the claims that follow, that scope including all equivalents of the subject matter of the claims. Each and every claim is incorporated into the specification as further disclosure and the claims are embodiments of the invention. The discussion of a reference in the disclosure is not an admission that it is prior art, especially any reference that has a publication date after the priority date of this application's earlier application. The disclosures of all patents, patent applications, and publications cited in this application are hereby incorporated by reference herein as providing exemplary, procedural, or other details supplementary to this application.

While several embodiments have been provided herein, it should be understood that the disclosed systems and methods may be embodied in many other specific forms without departing from the spirit or scope of the invention. The examples of the invention are to be regarded as illustrative rather than restrictive, and the invention is not limited to the details given herein. For example, various elements or components may be combined or integrated in another system, or certain features may be omitted or not implemented.

In addition, techniques, systems, subsystems and methods described and illustrated in various embodiments as discrete or separate may be combined or integrated with other systems, modules, techniques or methods without departing from the scope of the present invention. Other items shown or discussed as coupled or directly coupled or communicating with each other may be indirectly coupled or communicating through some interface, device, or intermediate component whether electrically, mechanically, or otherwise. Other examples of changes, substitutions, and alterations can be ascertained by those skilled in the art, and can be made without departing from the spirit and scope disclosed herein.

Claims (21)

1. it is used for an equipment for the expansible packet scheduling of high-volume conversation, comprising:

Multiple queues, it is for caching the multiple bags corresponding to multiple sessions；

Scheduler, it is for dispatching out described bag from different queue, with the end time based on each bag in each corresponding team The exit of row forwards；And

Outbound, it is couple to described scheduler, and is used for scheduled bag at all described queues and with all institutes State the total bandwidth that queue shared to transfer,

The wherein said end time is that dynamic calculation goes out based on the amount of bandwidth distributing to corresponding queue, and

Wherein said queue is assigned with the weights of correspondence with shared total bandwidth；

The wherein said end time calculates only for the bag at described queue head, and is the most only pointed to described queue The bag of head is scheduling.

Equipment the most according to claim 1, the dynamic calculation of wherein said end time reflects session and is activating with empty The change of switching between spare time.

Equipment the most according to claim 1, is wherein assigned to the described weights service based on respective session of described queue Quality (QoS) requirement.

Equipment the most according to claim 1, it farther includes:

Multiple second queues, it is for caching the multiple bags corresponding to multiple sessions, and the plurality of second queue includes being couple to One the second queue of described outbound；

Second scheduler, it is for dispatching out described bag from the second different queues, with the end time based on each bag Forward in the exit of the second queue of each correspondence；And

Second outbound, it is couple to described second scheduler, and for by scheduled bag at all second queues and Transfer with the total bandwidth that all queues are shared.

Equipment the most according to claim 4, wherein queue, described scheduler, described outbound, described second queue, Described second scheduler and described second outbound are corresponding to consolidated network node.

Equipment the most according to claim 4, wherein queue, described scheduler, described outbound are corresponding to first network Node, and wherein said second queue, described second scheduler and described second outbound are higher corresponding to being positioned in tree Level and be couple to the second network node of described first network node.

Equipment the most according to claim 1, wherein scheduled is coated the multiple corresponding time slots being assigned in calendar watch, its Middle assigned bag forwards on described outbound according to the order of described time slot, and wherein said calendar watch is suitable Intensive and include that quantity is far fewer than the unassigned time slot assigning number of timeslots.

Equipment the most according to claim 1, the kth bag that formula is session i that the calculating of wherein said end time uses 'sWhereinFor the time started that kth bag is calculated, if i-th team Packet congestion is there is not, then V at row_i ^k=0, or V in the case of other_i ^kConfigured equal to obtaining at i-th queue servicing The end time of later bag, w_iFor session i weights in terms of the bandwidth of distribution, B is for moving to queue head when kth bag Time all activated session set, R is the total bandwidth of output link shared between all sessions,For kth bag on session i Length.

9. it is used for a networking component for the expansible packet scheduling of high-volume conversation, comprising:

Receptor, it is for receiving the multiple bags corresponding to multiple sessions；

One or more memory element, it is used for buffering multiple queues of the bag of described respective session for storage；

Logical block, it is for calculating end time, and the bag that will be detected for each bag detected at corresponding queue head It is assigned to the time slot of calendar queue so that according to the ascending order of end time to forward bag；And

Emitter, it is assigned to multiple bags of described time slot by output link for being sent according to the order of time slot.

Networking component the most according to claim 9, the calculating of the described end time wherein wrapped is based on certain coefficient, According to the amount of bandwidth of session distributing to described bag, occurrence dynamics changes described coefficient.

11. networking components according to claim 9, the kth that formula is session i that the calculating of wherein said end time uses Individual bagWhereinFor the time started that kth bag is calculated, if i-th Packet congestion is there is not, then V at individual queue_i ^k=0, or V in the case of other_i ^kConfigured serviced equal at i-th queue Last bag end time, w_iFor session i weights in terms of the bandwidth of distribution, B is for moving to queue when kth bag The set of all activated session during head, R is the total bandwidth of the output link shared between all sessions,For kth on session i The length of bag.

12. networking components according to claim 11, wherein assign bag to treat according to described end time F_i ^kForward this Process provides O (1) work and saves scheduling.

13. networking components according to claim 12, the most averagely have S time slot scan in described calendar queue with Serve S bag.

14. networking components according to claim 9, wherein number of timeslots is equal to 1,000,000 time slot or more.

15. 1 kinds of methods for the expansible packet scheduling of high-volume conversation, comprising:

Multiple queues are scanned to detect any overstocked bag in described queue for multiple bag sessions；

By the multiple bags detected at described queue head according to the ascending order of multiple end times be assigned in calendar watch multiple Time slot, the described end time is to distribute to the bandwidth aspect of described bag session calculate for described wrapping in；

Sequentially the described time slot in calendar watch described in column scan is to detect assigned bag；And

Shared outbound forwards appointment bag in order that detect.

16. methods according to claim 15, wherein said queue detects appointing in described queue through scanning continuously He Xin overstocks bag, and wherein said time slot has carried out recursive scanning, and its mode is first after scanning last time slot Restart at individual time slot.

17. methods according to claim 15, the bag the most only detected in the exit of described queue is according to them The ascending order of end time value of calculation is assigned to described time slot.

The size of 18. methods according to claim 15, the instruction number in wherein said bag dequeue process and described time slot Relevant, and wherein said to wrap into the average of instruction during team independent with the size of described time slot.

19. methods according to claim 15, wherein when bag number increases, belong to the described bag of different queue through forwarding more Close to the preferable fair ratio between described queue.

20. methods according to claim 15, the increase of the described time slot size of wherein said calendar queue reduces finger Send out the scanning timeslot number of bag to be forwarded.

21. methods according to claim 15, the kth that formula is session i that the calculating of wherein said end time uses BagWhereinFor the time started that kth bag is calculated, if i-th Packet congestion is there is not, then V at queue_i ^k=0, or V in the case of other_i ^kConfigured equal to obtaining service at i-th queue The end time of last bag, w_iFor session i weights in terms of the bandwidth of distribution, B is for moving to queue heads when kth bag The set of all activated session during portion, R is the total bandwidth of the output link shared between all sessions,For kth bag on session i Length.