CN100568847C - Combined Frame Scheduling and Buffer Management Algorithm in DiffServ Network - Google Patents

Abstract

Framework (100) is transmitted, abandoned to the frame that the invention discloses in a kind of differentiated services network environment.This framework (100) comprises that abandons a logical circuit (102), be used for abandoning a Frame of incoming frame stream (104) according to a kind of discard algorithm, if the congestion level in network environment reaches predetermined extent and the backlog of the formation that is associated with described Frame when reaching predetermined limits, just abandon this Frame.Also be provided with scheduling logic circuit (118), be used for the transmission of the one or more data queued frames of network environment inferior.

Description

Combined Frame Scheduling and Buffer Management Algorithm in DiffServ Network

This application claims benefit under Section 119(e) of Act 35, United States Congress, to Title 60/2000, "A Joint Frame Scheduling and Buffer Management Algorithm in DiffServ Networks," filed February 24, 2000. Priority of US Provisional Application No. 184,557.

technical field

The present invention relates to network exchange technology, more specifically, relates to the data frame forwarding technology adopted in network exchange.

Background technique

Differentiated Services (DiffServ) is a relatively new concept emerging in the Internet field, which is considered as a "soft" way to improve Quality of Service (QoS). Differentiated Services is a group of new technologies proposed by IETF (Internet Engineering Task Force), which allows Internet service providers and other IP-based network service providers to provide different levels of service for individual users who pay extra, and Send streams to these users. Under this system, the frame header of each data frame entering the network router contains a mark, which indicates what level of service the network router should give to the data frame during transmission. The network router then applies a corresponding level of different services to each data frame entering each port. Using the method of distinguishing services, the service provider can provide priority services to all data frame streams (traffic) of some specific users according to the appropriate frame tags contained in the frame header (but this is not strictly invariable) promise). The higher the priority of the service provided, the shorter the frame delay (that is, the frame waiting time). When frame congestion occurs, these data frames with priority marks will enjoy priority service.

As for the current differentiated forwarding mechanism, because in the worst case, the requirements of frame delay and bandwidth isolation cannot be guaranteed at the same time without seriously reducing the utilization rate of system resources, so the mechanism is not perfect. To satisfy frame delay guarantee and bandwidth guarantee at the same time, a frame forwarding scheduling mechanism is required, which combines buffer management technology and transmission scheduling technology.

Contents of the invention

One aspect of the present invention disclosed and claimed herein is to provide a frame scheduling, discarding architecture for use in a differentiated services network environment. The architecture includes a discarding logic circuit, which is used to discard a data frame from the input frame stream of the network environment according to a discarding algorithm, if the congestion level in the network environment reaches a predetermined level, and the data frame related The data frame is discarded when the queue backlog length reaches a predetermined limit. A scheduling logic circuit is also provided for scheduling the sending sequence of one or more queued data frames in the network environment.

Description of drawings

In order to have a more complete understanding of the present invention and its advantages, the following description is made in conjunction with the accompanying drawings, in the accompanying drawings:

FIG. 1 is an overall block diagram showing a frame forwarding system according to the disclosed embodiments;

The graph in Figure 2 represents the congestion surface formed by the system shown in Figure 1;

The block diagram in Figure 3 shows a sample frame forwarding system designed according to Table 1; and

The graph in Figure 4 shows the sub-congestion surface in a WRED-type application.

Detailed ways

The novel scheduling mechanism disclosed herein preferably combines measurable quality of service (QoS) criteria and buffer management into a joint method for performing frame forwarding in a differentiated service environment, where the quality of service criterion For example latency or bandwidth.

QoS is a very broad concept, and different people have different interpretations for it. Generally speaking, the method for improving QoS described in this paper is based on several assumptions: the type of service flow provided is unknown; the input flow service is irregular or unshaped (however, if the input flow is regular or shaped some other guarantees on switching performance); and the network manager is aware of the types of applications (or flow types) being carried out on the network and the relative importance of these applications, such as voice communications, file transfers, Or web browsing. The term "shaping" or "shaping" is defined as the control (i.e., traffic policing) of traffic flow, i.e. preventing overflow of downstream devices by limiting traffic flow to a level very close to the downstream device's input bandwidth capacity . Regularization is similar to shaping, but in the process of regularization, service flows exceeding the set flow are discarded instead of cached. On the premise of having these application knowledge, the network manager can divide various applications into several types, and set up a service level agreement for each type of application. Guaranteed to be composed.

One type can provide traffic exceeding the agreed bandwidth. The traffic flow provided by a compliance type does not exceed the agreed traffic. Conversely, a violation type can provide flow services that exceed contracted traffic. A violation type is composed of multiple violation micro-service flows. In order to achieve high link bandwidth utilization, a violation type is allowed to use any redundant bandwidth. However, the tolerance for violation types must be limited to not impairing the QoS of other compliance types.

Table 1 below shows an example table about six types of flows, each type of flow in the table has its own unique attributes and applications.

Table 1. Sample tables for six types of streams

Type C_n target Get guaranteed total bandwidth Low packet loss probability (low packet loss type) High packet loss probability (high packet loss type) Send C₃ with the highest priority 40Mbps Application: telephone service (VoIP), circuit emulation Waiting time: less than 1ms Packet loss: If C₃ is not overtransmitted, there is no packet loss Application: Video teaching Waiting time: less than 1ms Packet loss: If C₃ is not overtransmitted, there is no packet loss, otherwise, it will be discarded first Send C₂ with medium priority 35Mbps Application: interactive application, e-commerce Waiting time: less than 4ms Packet loss: If C₂ is not overtransmitted, there is no packet loss Application: Non-critical interactive application Waiting time: less than 4ms Packet loss: If C₂ is not overtransmitted, there is no packet loss, otherwise, it will be discarded first C₁ with low delivery priority 25Mbps Applications: Email, document backup Latency: Hope less than 16ms, but not critical Packet loss: If C₁ is not overtransmitted, no packet loss Application: Random web browsing Latency: Hope less than 16ms, but not critical Packet loss: If C₁ is not overtransmitted, no packet loss, otherwise, first throw away Total 100Mbps

As shown in Table 1, the various flow types (i.e. telephony, circuit emulation, video teaching, critical and non-critical interactive applications, e-commerce, e-mail, document backup, and random web browsing) are divided into three types ( C ₁ , C ₂ , C ₃ ), each type is assigned a certain bandwidth guarantee and delay limit. Type C ₃ is the transmission type with the highest priority, and all data frames need to be sent within less than 1 ms, and occupy 40 Mbps (40%) of the total port bandwidth of 100 Mbps. Type C ₂ is a medium priority type, which occupies 35Mbps (or 35%) of the total port bandwidth of 100Mbps, and requires that all data frames should be sent out within less than 4ms. Finally, the C ₁ type is the lowest priority type, which occupies 25Mbps (or 25%) of the total port bandwidth of 100Mbps, and requires that all data frames should be sent in less than 16ms before packet loss occurs go out.

Additionally, each transfer type (C ₁ , C ₂ and C ₃ ) has two subtypes: a high packet loss subtype and a low packet loss subtype. Consistent users should rarely experience dropped frames. However, violating users (ie, users sending data frames with too high a flow rate) will lose some data frames, and the first to be discarded will be those data frames that meet the high packet loss criterion. If this is not enough to relieve congestion, some data frames that meet the low packet loss criterion will also be discarded, and in the worst case, all data frames will be discarded.

It can be seen from Table 1 that types of applications, corresponding attributes, and delay and packet loss criteria can be matched in any desired manner. For example, random web browsing is classified as a high packet loss, high latency stream, while VoIP telephony is classified as a low packet loss, low latency stream.

In addition to the above three types (C ₁ , C ₂ and C ₃ ), more transmission types with other delay bounds and minimum bandwidth guarantees can also be divided. Also, in another variant, best-effort flows may constitute a lowest-priority class that only gets bandwidth if none of the other classes have any flows. It is also possible to add a type with higher transmission priority, which has absolute priority over the other three (or more) types; that is, if this type has only one data frame to transmit, then It needs to be sent first. But it should be noted that in this specific embodiment, each 10/100 Mbps port supports a total of three types (C ₁ , C ₂ and C ₃ ).

In a 1Gbps application environment, since the higher the line speed, the higher the required QoS guarantee, each port may support up to eight types (C ₈ -C ₁ ). For example, a default configuration might have six delay-bound queues Q ₈ -Q ₁ (corresponding to types C ₈ -C ₁ , respectively) and two best-effort queues Q ₂ and Q ₁ (corresponding to types C ₂ and C ₁ ). For the case of a 1Gbps port, the setting of the delay bound is, for example, 0.16ms for C ₈ and C ₇ , 0.32ms for C ₆ , 0.64ms for C ₅ , 1.28ms for C ₄ , and 2.56ms for C ₃ . Best-effort traffic is serviced only when there are no delay-bound flows requiring service. For the case of the 1Gbps port, there are two best-effort queues, and the higher the type, the greater the priority (that is, C ₂ has absolute priority to C ₁ ). Again, the above description is only an example situation. It should be noted that the above architecture is compatible with the IETF Type Classification proposed by the Internet Engineering Task Force.

In order to solve the uncertainty caused by the ignorance of the mixing of input streams, a delay guarantee algorithm is adopted to dynamically adjust the scheduling criterion and packet loss criterion according to the queue occupancy and the due time of the queue HOL frame. according to. The result: a guaranteed delay bound for all admitted data frames with high confidence - even in the presence of system-wide congestion. The delay guarantee algorithm can identify the type of violation, and intelligently discard some data frames, so as not to damage the type of compliance. The algorithm can also use a weighted RED (Random Early Detection) method (WRED) to distinguish high packet loss flows from low packet loss flows. The WRED method is used in internetworks to avoid frame congestion before it becomes a problem. The RED algorithm monitors the flow load at selected points along a network and randomly drops frames when congestion starts to increase. The transmission of data frames is slowed down in response to an upper layer operation that detects dropped data frames.

Referring now to FIG. 1, a block diagram is shown which is a high-level overview of the disclosed embodiments. The novel forwarding mechanism disclosed herein includes two aspects combined: buffer management and delivery scheduling, wherein buffer management works according to a discarding algorithm for deciding admission and discarding of incoming data frames; and The delivery schedule is used to determine the order in which data frames are sent out. The importance of the above combination can be summarized as follows: the interrelationship among bandwidth, delay, and cache is mathematically expressed as a relational expression of "shared bandwidth∝queue length/experienced delay". This combined mechanism, which utilizes scheduling techniques and buffer management techniques, controls the experienced delay and queue length. As a result of the above facts and mathematical relationships, the federation mechanism also adjusts the bandwidth enjoyed by each type.

Referring again to FIG. 1, a frame forwarding system 100 includes a drop logic circuit 102 that operates according to a drop algorithm that monitors an input bit stream 104. Referring to FIG. The output 106 of the drop logic circuit 102 flows into one or more queues 108, 110 and 112 (also referred to as queues Q ₁ , Q ₂ . . . , Q _n ), each of which corresponds to a respective flow type C ₁ , C _{2 .} . . , C _n . The queues 108, 110, 112 temporarily store these data frames according to the flow type specified by each data frame, and each queue outputs the data frames to a multiplexing logic circuit 114, so as to be finally input to an output queue 116 , the output queue has a total bandwidth capacity of K Mbps. For example, the category C ₁ with the lowest delivery priority is associated with a service level agreement S ₁ defined by a delay bound parameter (δ ₁ ) and a bandwidth parameter (r ₁ ). If the number of data frames queued in the queue 108 (also referred to as Q ₁ ) cannot be sent within the time specified by the delay bound parameter (δ ₁ ), then there is a need for certain data frames of that type A certain probability of dropping to prevent congestion. Similarly, the figure also shows the next highest delivery priority type C ₂ , which is associated with a service level agreement S ₁ which is defined by a delay bound parameter (δ ₂ ) and a bandwidth parameter (r ₂ )limited. If the number of data frames queued in queue 110 (also referred to as Q ₂ ) is too large to be sent within the time specified by the delay bound parameter (δ ₂ ), then there is a need for some frames of this type to A certain probability that data frames are dropped to prevent congestion.

In the embodiment shown there are multiple types, of which the highest priority C _n is associated with a service level agreement S _n defined by a delay bound parameter (δ _n ) and a bandwidth parameter (r _n ) of. If the number of data frames queued in queue 112 (also referred to as Q _n ) is too large to be sent within the time specified by the delay bound parameter (δ _n ), then there is a certain probability that a frame of that type will Some data frames are dropped to prevent congestion. The output queue 116 temporarily stores the data frames received from each type of queues 108, 110 and 112, and outputs each type C ₁ , C ₂ , . . . C _n to a port P (not shown in the figure). The multiplexer 114 is controlled by a scheduling logic 118 which determines the order in which frames of data depart from the queues 108, 110 and 112 of each type.

The following is a more generalized description of the new system. Assume that port P serves n stream traffic types, denoted C ₁ , C ₂ , . . . C _n . The network provider has negotiated a service level agreement S _i for each service type C _i , the agreement is the expression of δ _i and r _I , that is, S _i = (δ _i , r _i ), where δ _i is the type The longest experienced guaranteed delay allowed for any data frame in C _i , and r _i refers to the timeout minimum guaranteed bandwidth allocated for type C _i . The types are set such that the maximum guaranteed delay δ ₁ of type C ₁ is greater than or equal to the maximum guaranteed delay δ ₂ of type C ₂ and the maximum guaranteed delay δ ₂ of type C ₂ is greater than or equal to type C ₃ The maximum guaranteed delay δ _{3 of} , and so on (that is, δ ₁ ≥δ ₂ ≥...≥δ _n ). The advantage of the disclosed mechanism is that no matter what the stream type is, it can simultaneously satisfy the delay constraint condition and the bandwidth constraint condition of the service level agreement S _i (i is all values).

The following discussion of delay bounded scheduling is in the context of a 10/100 Mbps port with three delay bound types (C ₃ , C ₂ and C ₁ ). However, it is also possible to similarly construct application environments having more types. In the case of the 10/100Mbps port in Table 1, when the bounded delay is scheduled, the data queued into three scheduling queues Q ₁ -Q ₃ (belonging to types C ₁ , C ₂ and C ₃ respectively) Frames contain an arrival timestamp. When a data frame arrives at the head-of-line (HOL) position in the queue, scheduling decisions are made based on the timestamp of the HOL data frame in each queue. In the exemplary rules given below, latency is defined as the time difference between the job (or data frame) arrival timestamp and the current time. Obviously, if there are no data frames waiting to be transmitted for a particular type, then that type cannot be selected.

Referring now to FIG. 2, this figure represents the concept of a congestion surface 200 in accordance with the disclosed embodiments in Euclidean space. Set the queue backlog length (measured in total bytes) waiting for output port P forwarding in each service type C _i to be Q _i . Let λ _i =δ ₁ /δ _i , and let D=K·δ ₁ (measured in bytes). The congestion hyperplane 200 is bounded by the set of vectors {Q ₁ , Q ₂ , Q ₃ , . . . Q _n } and is defined by equation (1):

$\underset{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

The buffer manager 102 will discard an incoming data frame destined for port P and of type C _i under and only under the following conditions,

$\underset{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

as well as

Q _i >r _i ·δ ₁

(3)

The first condition (formula [2]) indicates that the system 100 is congested, that is to say, the system 100 has exceeded the congestion plane 200 . The second condition (Equation [3]) states that the backlog of type C _i is already large. Even if a data frame of type _Ci is admitted, nothing can be done about its compliance with the delay constraints that are a result of the existing backlog and minimum bandwidth guarantees for other types. Thus, the input data frame of type i is to be discarded.

The disclosed buffer management algorithm can be modified to incorporate WRED techniques, the benefits of which are well described in the literature. WRED technology uses a weighted queue length to determine when the system becomes so congested that one or more data frames need to be considered discarded. The drop rule must drop enough frames to keep the queue length below the congestion plane 200; otherwise, drop 100% of the frames to prevent congestion. Since the goal is to distinguish high packet loss flows from low packet loss flows, the system 100 cannot be allowed to reach the critical situation of the congested plane 200, where all data frames will be dropped, regardless of the order in which they are dropped order. Thus, in this particular embodiment, two sub-congestion planes (level 1 and level 2) are defined which are designed to enable early congestion prevention so that data frames rarely encounter Harsh conditions for 100% packet loss probability.

Referring now to FIG. 3, a block diagram in the figure shows an exemplary forwarding system according to Table 1. Referring to FIG. The frame forwarding system 300 (similar to system 100) has a bandwidth of 100 Mbps and employs drop logic 102 that operates according to the drop algorithm disclosed herein. The discard logic 102 monitors the input bitstream 302 and discards selected data frames 304 in the bitstream 302 to a trash bin 306 (shown for discussion purposes only) based on predetermined criteria . Those admitted data frames (307, 309, 311) are then enqueued into corresponding types of input queues (308, 310, and 312). For example, input queue 308 belongs to C ₁ type (the type with the lowest transmission priority), and the delay bound of this type requires that all data frames ₃₀₇ should be sent out within the time less than 16ms. When the traffic exceeds the agreed 25Mbps and becomes a violation type, there is a probability that some _C1 type data frames will be discarded to prevent congestion. Input queue 310 is the queue of a C ₂ type (transmission priority medium type), and the delay bound of this type requires that all data frames 309 should be sent out in the time less than 4ms, if this type C ₂ due to the provided When traffic exceeds the agreed 35Mbps and becomes a violation type, there is a probability that some _C2 type data frames will be dropped to prevent congestion. Finally, the input queue 312 is a queue of type C ₃ (the type with the highest transmission priority), and the delay bound of this type requires that all data frames 311 should be sent out within less than 1 ms. If this type C ₃ is due to When offered traffic exceeds the agreed 40Mbps and becomes a violation type, there is a probability that some _C3 type data frames will be dropped to prevent congestion.

Corresponding data frames (307, 309, and 311) enqueued into the respective queues (308, 310, and 312) pass through a multiplexer 314 (similar to the multiplexing logic 114 described above) for no more than The 100 Mbps traffic is multiplexed into an output bitstream 316 , where the 100 Mbps traffic value is the port output speed of the system 300 . However, there is a scheduling logic circuit 318 connected to the multiplexer 314 for scheduling the transmission of the corresponding type of data frame (307, 309 and 311) from each type of queue (308, 310 and 312) . As described above, each queued data frame (307, 309, and 311) is timestamped when it arrives at the corresponding queue (308, 310, and 312). When a certain type of data frame (307, 309 and 311) arrives at the queue head position (313, 315 and 317) of its corresponding queue (308, 310 and 312), according to the arrival time stamp of the queue head data frame in each queue Make scheduling decisions.

Referring to Fig. 4, the graph lines in the figure represent the congestion surface and the sub-congestion surface. It should be noted that any number of sub-congestion planes can be defined. The level 1 and level 2 sub-congestion planes (400 and 402, respectively) prevent congestion by randomly dropping a proportion of high-drop frames while retaining a large number of low-drop frames. This allows high-drop frames to fall victim to low-drop frames and start dropping early on. In this example, when the existing total queue backlog N is between 120 and 200KB, and the buffered data frame backlog of any one of the type queues Q ₁ -Q ₃ reaches or exceeds the corresponding queue limit A, B or C (in KB), there is a certain probability of discarding data frames. In the sub-congestion surface 400 of level 1, there is 16Q ₃ +4Q ₂ +Q ₁ ≥ 120KB, and the backlog of any one or more queues in queues Q ₁ -Q ₃ exceeds the corresponding limit (respectively A, B and C), the ranges of low packet loss and high packet loss are between 0 and 0-X%, respectively. Similarly, in the sub-congestion surface 402 of level 2, there are 16Q ₃ +4Q ₂ +Q ₁ ≥ 160KB, and the backlog of any one or more queues in queues Q ₁ -Q ₃ exceeds the corresponding limit (respectively For A, B and C), the ranges of low packet loss and high packet loss are respectively between 0-Y% and 0-Z%. Finally, for the congestion surface 200 of the third level, the congestion surface is defined by the relational expression of 16Q ₃ +4Q ₂ +Q ₁ ≥ 200KB, and both the high packet loss rule and the low packet loss rule require 100% Data frames are discarded.

Table 2 summarizes the packet loss rules using WRED. In this table, each sub-congestion plane is defined according to a 100Mbps port. In this specific example, the total maximum queue backlog N=200KB.

Table 2. Packet drop rules for improving QoS with three delay bound types on 10/100Mbps ports.

It should be noted that: in the specific embodiment with the delay limit in Table 1, when 16Q ₃ +4Q ₂ +Q ₁ ≥ N KB, only the above-mentioned discarding data frame (or packet loss) rule is applied, in this respect The content is discussed in detail below.

Table 3 gives an example that combines the above-mentioned discarding mechanism with the WRED technique.

Table 3. Sample drop method combined with WRED technology

Level 3 in Table 3 follows the rules presented above and assumes the delay-bound constraints of the system in Figure 1. For example, according to the above equations, if under such conditions (and only under such conditions): 16Q ₃ +4Q ₂ +Q ₁ ≥ 200KB, and the queue Q ₂ exceeds the predetermined backlog limit - that is, Q ₂ When ≥17.5KB, a data frame of type C ₂ will be discarded. Level 1 and Level 2 form the two sub-congestion surfaces discussed above (400 and 402, respectively). For example, if 120KB≤16Q ₃ +4Q ₂ +Q ₁ <200KB, and Q ₂ ≥17.5KB, packet loss is performed with a certain probability. It can be noticed that at each WRED level, whether the data frame belongs to the high packet loss category or the low packet loss category is identified, and different discard probabilities are assigned accordingly.

As shown in FIG. 2 , in this particular embodiment with three types C ₁ , C ₂ and C ₃ , each point on the congestion surface 200 forms a three-dimensional coordinate of a queue length (Q ₁ , Q ₂ , Q ₃ ), the coordinate point is tolerable, that is, if the respective queue lengths (Q ₁ , Q ₂ , Q ₃ ) remain stable at these values, then the corresponding delay bounds can be satisfied. For example, a set of tolerable steady-state queue lengths is expressed as (50, 17.5, 5) in KB. These values are derived as follows: Q ₃ =(r ₃ )(δ ₃ )=(40Mbps)(1ms)=5KB; Q ₂ =(r ₂ )(δ ₂ )=(40Mbps)(4ms)=17.5KB; Q ₁ =(r ₁ )(δ ₁ )=(25Mbps)(16ms)=50KB.

For delivery scheduling, define Δ(F) as the current latency of data frame F. Then, a data frame F of type i is defined as having slack Ψ _i (F), where Ψ _i (F) = δ _i - Δ(F). The advantage of this transmission scheduling method lies in a very simple relationship: the smaller the hysteresis (delay time), the higher the transmission priority. When the calculated sluggish times are equal for two or more types of queues, the scheduling process first transmits to the queue with higher priority (that is, the type with stricter delay requirements).

Although the preferred embodiment has been described in detail above, it should be understood that various changes, substitutions and alterations can be made without going beyond the protection scope and design concept of the present invention defined by the appended claims.

Claims (14)

1. method of in the differentiated services network environment, carrying out the data frame scheduling and abandoning, it comprises step:

Abandon logical circuit by one a Frame in the input data frame stream is abandoned, the logical circuit that abandons wherein is set to abandon under the following conditions Frame: if the congestion level in network environment reaches predetermined extent and the backlog of the formation that is associated with described Frame when reaching predetermined limits; And

Order of transmission is dispatched the order when order of transmission wherein is meant the one or more data queued frames in the network environment are sent by a scheduling logic circuit.

2. method of in the differentiated services network environment, carrying out the data frame scheduling and abandoning, it comprises step:

Abandon step:

If

Congestion level in network environment reaches predetermined extent, and

When the backlog of the formation relevant with certain Frame in the input data frame stream reaches predetermined limits,

Just abandon logical circuit and abandon this Frame by one;

The scheduling step:

By a scheduling logic circuit order of transmission is dispatched, order when order of transmission wherein is meant the one or more data queued frames in the network environment are sent makes Frame be delivered to output port from input rank before the time-delay gauge of this data frame type exceeds.

3. method according to claim 2 is characterized in that: in abandoning step, described Frame is associated uniquely with a data frame type, and this described unique data frame type also is associated with described formation in the network environment.

4. method according to claim 2 is characterized in that: in abandoning step, according to maximum delay limit and minimum bandwidth limit described formation is controlled.

5. method according to claim 2, it is characterized in that: comprise a plurality of formations in the network environment wherein, and according to the corresponding queues type these formations are classified, described a plurality of queue types prolong to transmitting the highest type of priority from transmitting the minimum type of priority.

6. method according to claim 5 is characterized in that: the maximum delay value of the minimum type of described transmission priority is greater than described maximum delay value with the highest transmission priority type.

7. method according to claim 2 is characterized in that: the scheduling step comprises a step of calculating lag time, in order to determine the order of transmission of described one or more data queued frames.

8. method according to claim 7 is characterized in that: described lag time is short more, and corresponding transmission priority is high more.

9. method according to claim 7, it is characterized in that: each described one or more data queued frame all is associated with a timestamp, and the difference of the time when the described lag time of certain selected data frame is defined as that the selected data frame is discharged in the formation described in described one or more data queued frame in described one or more data queued frame and the long delay time of described corresponding formation.

10. method according to claim 7, it is characterized in that: in described scheduling step, if first lag time of a lower priority formation equals second lag time of a higher priority queues, then at first described higher priority queues is carried out and transmitted scheduling.

11. method according to claim 2 is characterized in that: in described scheduling step, when a selected data frame in described one or more data queued frames arrives team position in its corresponding formation, then this Frame is carried out and transmitted scheduling.

12. method according to claim 2 is characterized in that: in abandoning step, abandon described Frame according to a plurality of predetermined congestion level.

13. method according to claim 12 is characterized in that: in reaching described a plurality of predetermined congestion level during high congestion level, all Frames relevant with reaching described predetermined described formation of overstocking limit all are dropped.

14. method according to claim 13, it is characterized in that: when reaching described predetermined congestion level, and when described predetermined congestion level was lower than described high congestion level, some Frames relevant with reaching described predetermined described formation of overstocking limit just were dropped.

Images