CN103152281B - Two-level switch-based load balanced scheduling method - Google Patents

Abstract

A load balancing scheduling method based on two-level switching. The first-level input port buffers arriving cells in the VOQ queue according to the destination port. The scheduler switches the message to the second-level input port through the first-level switching network, and the VOQ queue The k cells from the same flow in the network are called a unit frame; each input port of the first stage executes the minimum length allocation according to the traffic distribution matrix, and in k consecutive external time slots, the same The unit frame of a flow is sent to the fixed mapping area of the flow; N second-level input ports are divided into N/k groups in turn, and each group contains k consecutive second-level input ports to form an area, each area according to the purpose The port buffers the cell in the OQ queue, and switches it to the destination output port through the second-level switching network. The invention has the advantages of simple dispatching process, no calculation or communication, easy hardware implementation, 100% throughput and guaranteed message order.

Description

Load Balance Scheduling Method Based on Two-Level Switching

technical field

The invention mainly relates to the field of message scheduling in a parallel switching structure, in particular to a message scheduling method for realizing load balancing and message order preservation in a parallel switching structure.

Background technique

Researchers have done a lot of research on packet out-of-sequence behavior by using active measurement and passive measurement methods. J.Bennet measured the out-of-sequence of packets at the switching center of MAE-East ISP, and found that in the measurement environment of heavy load and high parallelism of network equipment, the out-of-sequence of packets is very serious, and more than 90% of the connections have out-of-sequence . J.Bennett analyzed that the high out-of-sequence rate mainly comes from the local parallel processing mechanism inside the network, including parallel switching devices and parallel transmission links, and pointed out that packet out-of-order is not a pathological behavior of the network. Most high-performance parallel switching structures have out-of-order packets, such as load-balanced switch, parallel packet switch, multi-level switch, etc. Trouble with out-of-sequence problems. The deep parallel design brings load balancing and packet out-of-sequence problems to the switching fabric. Load balancing is the key to guaranteeing latency and throughput, but load balancing may cause out-of-order packets, which will damage the Internet network, because the TCP transmission protocol widely used on the Internet will mistakenly treat out-of-order packets as It is a sign of packet loss and congestion, which causes unnecessary retransmission and TCP timeout. These retransmissions and timeouts will reduce the TCP throughput and increase packet delay. Therefore, it is extremely necessary to ensure the sequence of packets while implementing load balancing of input traffic.

The methods to prevent out-of-sequence messages can be divided into two categories: 1) limit the number of out-of-order messages, and set a reordering buffer with limited capacity at the output end for reordering out-of-order messages; 2) ensure that messages follow the Arrival order leaves the output port, thereby avoiding out-of-order packets. Due to the limited capacity of the buffer, the first method can only handle out-of-order packets within a certain range. If the size of the reordering buffer is increased to O(N ² ), although the problem of out-of-order packets can be completely solved, it will Correspondingly, the packet delay is increased on a quadratic time scale, where N is the number of ports. Therefore, limiting the number of out-of-sequence packets cannot effectively solve the problem of out-of-sequence packets, and it is difficult to meet the requirements of high port density of routers. The Full Ordered Frame First (FOFF) algorithm proposed by Stanford University is a representative algorithm of the first method, which allows a certain number of out-of-order packets in the router, and sets an N×N buffer queue at the output end for for reordering out-of-sequence packets. It can be proved that in order to ensure that cells leave in sequence, the reordering buffer capacity of FOFF algorithm is at most N ² cells and can provide load balancing to obtain 100% throughput. In recent years, more researchers tend to adopt the second method to ensure the order of packets, which eliminates the reordering operation and buffer overhead at the output end, which is beneficial to improve the delay performance. The common feature of these scheduling methods is to obtain the state information of all arriving packets through a message passing mechanism, and perform centralized scheduling based on the global packet state information. For example, the mailbox switch (mailbox switch) method uses a symmetrical connection mode to create a feedback path for notifying the departure time of a message, and the scheduler schedules the message according to the message's departure time. This strategy can ensure that the packets of each flow leave the switching system in the order they arrive, but cannot provide load balancing to achieve 100% throughput. The alternate matching scheduling method adopts a centralized scheduling mode, assuming that the traffic characteristics are predictable and fixed, and adopts the method of matrix decomposition to solve the centralized scheduling problem offline, and realizes online scheduling and provides service guarantee in a distributed manner. However, when the traffic becomes unpredictable and changes dynamically, it is difficult to meet the centralized scheduling requirements under large switch sizes. The parallel matching scheduling method realizes message order preservation by transferring request-permission tokens between the first-level input line card and the second-level input line card, but in the specific hardware implementation, the frequent transfer of tokens between line cards will become a problem. Double the scheduling cycle.

Contents of the invention

The technical problem to be solved by the present invention is: aiming at the technical problems existing in the prior art, the present invention provides a scheduling process that is simple, does not require any calculation or communication, is easy to implement in hardware, achieves 100% throughput and can guarantee message A sequential load balancing scheduling method based on two-level switching.

In order to solve the problems of the technologies described above, the present invention adopts the following technical solutions:

A load balancing scheduling method based on two-level switching. The first-level input port buffers arriving cells in the VOQ queue according to the destination port. The scheduler switches the message to the second-level input port through the first-level switching network, and the VOQ queue The k cells from the same flow are called a unit frame, and the unit frame is the smallest scheduling unit; each input port of the first level performs the minimum length assignment according to the traffic distribution matrix, and in k consecutive external time slots, through The first-level switching network sends unit frames of the same flow to the fixed mapping area of the flow; N second-level input ports are sequentially divided into N/k groups, and each group consists of k consecutive second-level input ports In one area, each area buffers cells in the OQ queue according to the destination port. Since the mapping relationship between flow and area is fixed, k cells from the same unit frame will arrive at the head of the OQ queue in sequence, and are switched to the OQ queue through the second-level switching network. Destination output port.

As a further improvement of the present invention, a double-loop method is used to construct the mapping from flow to region:

(1.1) Construct the mapping from the N/k flow branches of the first-level input port to the N/k regions of the second-level input port in a cyclic manner, so as to ensure that each region can just cover all the flows;

(1.2) Further adjust the association between different input ports and N/k mapping methods in a cyclic manner to ensure that each area covers all flows according to the balanced distribution of input ports.

As a further improvement of the present invention, during input port scheduling, cells are assigned according to the mapping relationship between streams and regions to serve N/k stream branches in a round-robin manner, and the operation of the first-level input port at each external time slot The process is as follows:

(2.1) If the flow branch If there is a full frame in the VOQ queue, the full frame is scheduled first, and the N/k unit frames of the full frame are given the highest scheduling priority, the traffic distribution matrix L is searched, the first unit frame of the full frame is intercepted, and sent to the current L _{g, j is} the smallest region R _g , that is, execute steps (2.1.1)~(2.1.k), if there is no full frame, go to step (2.2);

(2.1.1) If the internal link from the input port i to the second-stage input port S _{g, 1} is idle, then the VOQ _{i, j} queue head cell is sent to the second-stage input port S _{g, 1} of the region R _g , Otherwise f=(f+1)modN/k, go to step (2.1);

(2.1.2) send VOQ _{i, j} queue head cell to area R _g second stage input port S _{g, 2} ;

(2.1.3) send VOQ _{i, j} queue head cell to area R _g second stage input port S _{g, 3} ;

And so on to (2.1.k) to send VOQ _{i, j} queue head cell to the second stage input port S _g of area R _{g, k} , g=(g+1)modN/k, go to step (2.1);

(2.2) If the flow branch VOQ queue, VOQ _{i, j} (kf≤j<kf+k) has the highest scheduling priority unit frame, then search the traffic distribution matrix L, and send the unit frame to the current region R _g with the smallest L _{g, j} , that is, execute Steps (2.1.1) ~ (2.1.k), otherwise go to step (2.3);

(2.3) If the flow branch If there are one or more unit frames in the VOQ queue, search the traffic distribution matrix L, select the unit frame of the VOQ queue with the smallest equalization coefficient according to the search result, and send it to the flow branch The fixed mapping region R _g , that is, execute steps (2.1.1)~(2.1.k), if there is only one unit frame, the search operation of the flow distribution matrix can be skipped, and the unique unit frame of the flow branch can be directly sent to its fixed map region R _g , otherwise flow branch Does not contain any unit frame, g=(g+1)modN/k, go to step (2.1).

Compared with the prior art, the present invention has the advantages of:

1. The dispatching method of the present invention can be distributed to each input port for independent execution, distributes cells according to the local VOQ queue information, does not require any communication overhead, and realizes 100% throughput with O(1) time complexity and can guarantee message Order.

2. The present invention realizes packet order preservation and load balancing without any communication overhead among the input port schedulers. By constructing a fixed mapping from flow to region, packet disorder is avoided and packet reordering overhead is eliminated; in order to avoid traffic concentration in regions, a dual-rotation method is used to construct flow-to-region mapping of different input ports Relationship, each input port maintains a traffic distribution matrix with a global unified view, and schedules unit frames according to the traffic distribution matrix. It can be proved that for any output port j, the queue lengths of OQ _j in the same area are the same and the queue lengths of OQ _j in different areas differ by at most 1, thus achieving 100% load balancing.

3. The present invention only needs to properly select the aggregation particle size k, and theoretically the lowest delay can be obtained. The delay performance of the scheduling method of the present invention under different aggregation granularity k is verified by simulation, and compared with the current mainstream load balancing scheduling algorithm. The simulation results show that when the aggregation granularity k=2, the present invention has the optimal delay performance among all current scheduling algorithms that can guarantee the order of messages, and under the burst traffic model, it exhibits and does not have the property of message order preservation algorithm with comparable performance.

4. The present invention schedules messages according to the fixed mapping relationship between streams and regions, the scheduling process is simple, no calculation or communication is required, and hardware implementation is easy.

Description of drawings

FIG. 1 is an example of a secondary switching architecture to which the scheduling method of the present invention is applied.

Fig. 2 is a schematic diagram of the flow-to-area mapping result obtained by using a double-loop mapping method when the number of ports N=32 and the aggregation granularity k=8 are constructed by the present invention in a specific application example.

Fig. 3 is a schematic flow chart of the method for executing load balancing scheduling in a specific application example of the present invention.

Fig. 4 is a schematic diagram of the distribution of cells in the OQ buffer of the second-level input port after the minimum length allocation of the present invention is adopted in the case of a traffic burst in a specific application example of the present invention.

Detailed ways

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

The present invention is based on the load balancing scheduling method of two-level switching. First, the first-level input port buffers the arriving cells in the VOQ queue according to the destination port, and the scheduler passes the first-level switching network (Mesh network as shown) to the message Switched to the second-level input port, k cells from the same flow in the VOQ queue are called a unit frame, and the unit frame is the minimum scheduling unit of the present invention. Each input port of the first stage independently executes the scheduling method of the present invention, executes the minimum length assignment according to the flow distribution matrix, and transfers the unit frames of the same flow through the first-stage switching network (Mesh network) in k consecutive external time slots Send to the fixed mapping area for this stream. N second-level input ports are divided into N/k groups in turn, and each group contains k consecutive second-level input ports to form an area; each area buffers cells in the OQ queue according to the destination port, because the flow to the area The mapping relationship is fixed, and k cells from the same unit frame will arrive at the head of the OQ queue in sequence, and will be switched to the destination output port through the second-level switching network (Mesh network as shown in the figure). In the above process, each input port independently executes the cell allocation algorithm based on flow mapping: the unit frame of the same flow is sent to the fixed mapping area of the flow through the first-level Mesh network; each area buffers the cells according to the destination port In the OQ queue, due to the fixed mapping relationship between flows and areas, k cells from the same unit frame will arrive at the head of the OQ queue in sequence, and will arrive at the output port in turn when the second-level Mesh network is idle. If the first-level buffer is implemented on the first-level line card, and the second-level buffer is implemented on the second-level line card, then the above-mentioned two-level switching structure becomes a typical load balancing switching structure, and the present invention is especially suitable for load balancing Router packet scheduling method. For the convenience of expression, the present invention uses a Mesh network to illustrate the content of the invention. The Mesh network can be understood as a technical approach to realize the exchange of messages to the second-level input port and the destination output port. It can be a Mesh network or other switching technologies.

It can be seen from the above that the core of the present invention is to divide k continuous input ports into one area, and the input end adopts a load distribution algorithm based on flow mapping to distribute k cells of the same flow to fixed the mapped area. It is proved by theory that this scheduling strategy can obtain 100% throughput rate and can guarantee the sequence of packets. Where k is the aggregation granularity, which determines the number of cells for scheduling the same flow each time. In order to avoid the concentration of flow areas, the present invention further adopts a dual-rotation method to construct the mapping relationship between flows and areas of different input ports. In order to realize the balanced distribution of loads at the second-level input ports, the present invention further maintains a traffic distribution matrix of a global unified view at each input port, and dispatches unit frames according to the traffic distribution matrix to achieve 100% load balance.

FIG. 1 is an example of a secondary switching architecture to which the scheduling method of the present invention is applied. In the figure, VOQ _{i, j} represent the virtual output queue j of the first-stage input port i; Indicates the output queue j of the second-level input port l; f(i, j) indicates the flow from the first-level input port i to the output port j; k is the aggregation granularity, indicating the number of consecutively scheduled cells of the same flow (k is a factor of the number of ports N); VOQ _{i, every k cells of the j} queue form a unit frame (unit frame), and the unit frames of N/k different VOQ queues at the first-level input port i (a total of N cells unit) to form an aggregate frame (aggregate frame), VOQ _{i, j} queue N cells form a full frame (full frame); the second-level input ports 1, 2, ..., N are divided into N in turn /k groups, each group contains k consecutive second-level input ports, and the k second-level input ports of the g-th group form a region, denoted as R _g , S _{r, z} represents the z-th of the region r Two-level input port; N streams of each input port are divided into N/k groups corresponding to N/k areas, each group contains k streams, and the k streams of the fth group of input port i form a stream branch ,Referred to as

In order to reduce the bandwidth requirements of the message buffer memory, the Mesh network usually operates at the rate R/N (internal link acceleration ratio is 1), thus the following definition is obtained:

Definition 1. The time it takes to send or receive a cell on a link with rate R is an external timeslot.

Definition 2. The time it takes to send or receive a unit frame on a link with a rate of R/N is a time slot (time slot), and the time slot is N times the external time slot.

Normally, in each time slot, that is, every N external time slots, the UFFS-k algorithm can aggregate N/k unit frames from N/k flow branches at the input end to form an aggregated frame and dispatch it to the second-level input port . The VOQ queue balance coefficient reflects the balance of flow distribution in the OQ queue of the second-level input port. The present invention schedules unit frames according to the length of the OQ queue in each region, and realizes the load balance between regions. Next, the working principle of the equalization coefficient of the present invention will be described in detail. By using the inductive proof of time slots, it can be proved theoretically that the above scheduling method based on flow mapping can guarantee that for any region R _g , 0≤j<N, k second-level input ports correspond to k The queue lengths are the same (neglecting the transmission delay of a unit frame), where l ∈ R _g . From this, the following definitions can be obtained:

Definition 3. Since for any region R _g , The queue lengths are the same (l∈R _g ), then the equalization coefficient of queue VOQ _{i, j} is equal to the length of the output queue j of its mapping area R _g , denoted as L _{g, j} .

Definition 4. If the queue VOQ _{i, j} has a unit frame and the equalization coefficient satisfies Then the VOQ _{i, j} queue unit frames are sent to the region R _g in consecutive k external time slots, which is the minimum length assignment.

It can be proved theoretically that adopting the minimum length allocation strategy can ensure that after the end of the time slot T, for any two regions R _g1 , R _g2 , the difference between the OQ queue length Lg _{1, j} and Lg _{2, j} is at most 1, so that it can realize 100% throughput and 100% load balancing. In order to achieve the minimum length assignment, the first-level input port scheduler needs to maintain the traffic distribution matrix L=[L _{g, j} ] of the global unified view. In order to ensure the consistency of the traffic distribution matrix in each input port view, each port must realize Mutual exclusion of write operations to the flow distribution matrix. The present invention adopts the lock mechanism to realize the mutually exclusive writing to the mutex L _{g, j} : if g, j satisfy And L _{g, j} are in the unlocked state, then the first-level input port i locks L _{g, j} and sends the VOQ _{i, j} queue unit frame to its mapping area R _g , L _{g, j} plus 1 is unlocked. The VOQ _{i, j queues whose equalization coefficients L g,} j are locked in the stream branch are directly skipped. It is not difficult to infer that only those input ports with the same mapping relationship between flows and areas schedule the same VOQ _{i, j} queue at the same destination port, which may cause write conflicts to the same L _{g, j} , and mutual exclusion of the equalization coefficient L _{g, j} Writing can prevent these input ports from sending multiple unit frames to the output queue j of the same area at the same time, resulting in unbalanced traffic distribution.

The message scheduling algorithm based on flow mapping dispatches cells according to the local VOQ queue information, and can be distributed to each input port of the first level and executed independently. Step 2 describes that each input port of the first level executes the load balancing scheduling method of the present invention. process.

In the present invention, the first step is to construct a flow-to-area mapping in a dual-rotation manner. The flow-to-area mapping method is related to the utilization of the second-level storage resources and the two-level Mesh network. In order to avoid throughput loss, the flow-to-area mapping algorithm should achieve a balanced distribution of input load in each area. The present invention proposes a dual-rotation mapping algorithm that takes into account both load balancing and message order preservation. When the buffer OQ queue lengths are different, cell disorder will occur, and the number of disordered cells increases with the increase of the difference in OQ queue length. If the k cells of the same flow are assigned to a preset mapping area (k consecutive second-level input ports) in a fine-grained manner, since the mapping relationship between the flow and the area is fixed, for any flow, its information The lengths of the OQ queues in the mapping areas where the cells are located are the same, so that the sequential sending of cells is realized.

1.1 Since for any given area, only k fixed streams of the same input port can be received, in order to achieve a balanced load distribution in each area, N/k stream branches of the first-level input port are constructed in a circular manner to the second Mapping of N/k areas of the input port of the stage, step 1.1 corresponds to the first layer of for loop described by the pseudo-code of the double-loop mapping algorithm, and step 1.1 ensures that each area can just cover all streams;

1.2 Further adjust the relationship between different input ports and N/k mapping methods in a cyclic manner. Step 1.2 corresponds to the second-layer for loop described in the pseudocode of the double-loop mapping algorithm. Step 1.2 ensures that each area is covered by a balanced distribution of input ports all streams.

The double-loop mapping algorithm establishes the mapping relationship between streams and regions through simple modulo operations, which is easy to implement in hardware. Its pseudocode is described as follows:

In the present invention, the second step is that the input port scheduling component distributes cells according to the mapping relationship between flows and regions, and serves N/k flow branches in a round-robin manner, with the unit frame as the minimum scheduling unit, In consecutive k external time slots, the unit frame of the fixed VOQ queue in the stream branch is sent. The operation flow of the first-level input port i scheduling component executing the scheduling method of the present invention in each external time slot is as follows:

2.1 If the flow branch (0≤f<N/k, f is initialized to 0), VOQ queue, VOQ _{i, j} (kf≤j<kf+k) has a full frame, then the full frame is scheduled first, and the full frame is given N/k units The highest scheduling priority of the frame, search the traffic distribution matrix L, intercept the first unit frame of the full frame, and send it to the area R _g with the smallest L _{g, j} at present, that is, perform steps 2.1.1~2.1.k, if there is no full frame Then turn to step 2.2,

2.1.1 If the internal link from the input port i to the second-level input port S _{g, 1} is idle, then send the VOQ _{i, j} queue head cell to the second-level input port S _{g, 1} of the area R _g , otherwise f =(f+1)modN/k, go to step 2.1;

2.1.2 Send the VOQ _{i, j} queue head cell to the second stage input port S _{g, 2} of the region R _g ;

2.1.3 Send the VOQ _{i, j} queue head cell to the second stage input port S _{g, 3} of the region R _g ;

 …

By analogy to 2.1.k, send VOQ _i,j queue head cells to the second-level input port S g _,k of region R _g , g=(g+1)modN/k, go to step 2.1.

2.2 If the flow branch VOQ queue, VOQ _{i, j} (kf≤j<kf+k) has the highest scheduling priority unit frame, then search the traffic distribution matrix L, and send the unit frame to the current region R _g with the smallest L _{g, j} , that is, execute Step 2.1.1～2.1.k, otherwise go to step 2.3.

2.3 If the flow branch If there are one or more unit frames in VOQ queue, VOQ _{i, j} (kf≤j<kf+k), search the traffic distribution matrix L, and select the minimum equalization coefficient VOQ queue, VOQ _{i, j} (kf≤j< kf+k), sending it to the stream branch The fixed mapping area R _g of the flow branch, that is, perform steps 2.1.1~2.1.k, if there is only one unit frame, the search operation of the flow distribution matrix can be skipped, and the unique unit frame of the flow branch is directly sent to its fixed mapping area R _g , otherwise the stream branches Without any unit frame, g=(g+1)modN/k, go to step 2.1.

The present invention adopts the degree of load balance to measure the degree of balance that the load is distributed in the second-level OQ buffer zone, and the degree of load balance can be defined as follows:

Definition 5. Load balancing degree: Assume that the l-th switching module forwards S _l [t _r , t _v ] cells within the time period [t _r , t _v ]. The load balance degree is the ratio of the minimum number of cells forwarded by different switching modules to the maximum number of cells within the time period, that is:

$\mathrm{E.}[t_r,t_v]=\frac{\underset{l=0,...K-1}{\min }{S}_l[t_r,t_v]}{\underset{l=0,...K-1}{\max }{S}_l[t_r,t_v]}$ (K is the number of second-level switching modules)

Obviously, the load balance degree E[t _r , t _v ]≤1, and E[t _r , t _v ] tends to 1, which means that the number of cells processed by each switching module is basically the same, and the load distribution among the switching modules is relatively balanced. The smaller the E[t _r , t _v ], the worse the load balance of the switch module, which proves that the scheduling method of the present invention can obtain 100% load balance.

As shown in Figure 2, in a specific application example, the flow-to-area mapping method designed in the first step of the present invention, when the number of ports N=32, and the aggregation granularity k=8, the flow-to-area obtained by using the double-loop mapping method (VOQ _ij represents the flow from input port i to output port j, → represents the mapping relationship). In order to facilitate the viewing of the mapping result from flow to area, the aggregation granularity flow k=8 with a larger value is selected. The flow-to-region mapping method is used to construct a fixed flow-to-region mapping relationship, which is related to the utilization of the second-level input storage resources and the two-level switching network (such as a Mesh network). In order to avoid the loss of throughput ) flow-to-area mapping algorithm should realize the balanced distribution of input load in each area.

The present invention adopts a dual-rotation mapping method to adjust the mapping of stream branches to regions. As shown in Figure 2, the input port i, (0≤i≤31) contains N/k=4 flow branches The input ports of the second stage are divided into N/k=4 regions {R ₀ , R ₁ , R ₂ , R ₃ }. In order to ensure the utilization of the first-level switching resources, the flow branches of the same input port should be mapped to different areas, thus four mapping methods are obtained. In order to ensure that each area can cover all the flows, the second-layer loop constructs the mapping from the flow branches of different input ports to the area in a round-robin manner, which theoretically ensures the feasibility of load balancing. According to the second-layer cyclic mapping operation, the input port i={0, 4, ..., 28} adopts the first mapping method, and the input port i={1, 5, ..., 29} adopts the second mapping method The input port i={2, 6, ..., 30} adopts the third mapping mode, and the input port i={3, 7, ..., 31} adopts the fourth mapping mode. The above-mentioned double-loop mapping method can take into account both load balancing and message order preservation. The present invention schedules unit frames according to the second-level input port flow distribution matrix, which further ensures the balance of each flow among regions.

As shown in FIG. 3 , it is a schematic flow chart of the method for implementing load balancing scheduling in a specific application example of the present invention, corresponding to the above-mentioned second step of the present invention.

As shown in Figure 4, for the present invention in the case of traffic burst, after adopting the minimum length distribution of the present invention, the distribution of cells in the OQ buffer zone of the second-level input port, the present invention realizes the message sequence while ensuring Balanced distribution of load. Since the mapping relationship between stream branches and regions is fixed, there are situations where buffer overflow occurs in some regions due to heavy load, while other regions are relatively idle. For example, the VOQ queue of a flow branch at the input end contains N cells, and the queue length is still increasing, while other flow branches have no unit frame to schedule. In this way, the internal link from the heavy-load flow branch to its mapping area will become a performance bottleneck. On the other hand, the heavy-load flow branch cannot use other idle links of the input line card, resulting in waste of internal bandwidth. In order to solve the above problems, the present invention allows heavy-load flow branches to seize link resources in the case of traffic bursts, and evenly distributes burst message flows in each area by giving the highest priority to full frames. In order to solve the cell out-of-sequence problem caused by scheduling full frames and follow the load balancing principle, the present invention assigns the N/k unit frames read from the VOQ _{i, j} queue, that is, a full frame _{, to the current L g with the smallest j.} Region R _g . The dispatch order obtained by adopting this strategy is: the first and second unit frames read from the VOQ _{i, j} queue are assigned in the area 2 and area 3 in turn, and the third unit frame and the fourth unit frame are assigned in the order of Area 1 or Area 4, these four unit frames will arrive at the output port j sequentially in the readout order. Since the length of the output queue j in different areas differs by at most 1, sending N/k unit frames in the full frame to the current L _{g in turn, the area with the smallest j} will not cause cell disorder. Essentially, both the scheduling unit frame and the scheduling full frame adopt the minimum length allocation strategy. The difference between the two is that the unit frame can only be fixedly allocated to its mapping area, while the full frame will be split into N/k unit frames for balanced distribution. in N/k regions.

The above are only preferred implementations of the present invention, and the protection scope of the present invention is not limited to the above-mentioned embodiments, and all technical solutions under the idea of the present invention belong to the protection scope of the present invention. It should be pointed out that for those skilled in the art, some improvements and modifications without departing from the principle of the present invention should be regarded as the protection scope of the present invention.

Claims (2)

1. the load equilibration scheduling method exchanging based on two-stage, is characterized in that:

First order input port is buffered in VOQ queue by arrival cell according to destination interface, scheduler by first order switching network by message switching to second level input port, k the cell from same stream in VOQ queue is referred to as a unit frame, and unit frame is minimum scheduling unit; Each input port of the first order is carried out minimum length assignment according to flow distribution matrix, at k continuous external time groove, by first order switching network, the unit frame of same stream is sent to this and flows fixing mapping area;

N second level input port is divided into N/k group successively, every group forms a region containing k continuous second level input port, each region according to destination interface by cell-buffering in OQ queue, owing to flowing to the mapping relations in region, fix, k the cell from same unit frame will arrive OQ queue heads position successively, by second level switching network, exchange to object output port;

In first order input port when scheduling, assigns cell according to the mapping relations that flow to region and serves N/k flow branching with polling mode, and described first order input port as follows in the operating process of each groove external time:

(2.1) if flow branching vOQ queue, VOQ _i,jthere is full frame, priority scheduling full frame, in 0≤f<N/k, f is initialized as 0, VOQ _i,jmiddle kf≤j<kf+k; Give this full frame N/k the highest dispatching priority of unit frame, search flow distribution matrix L, first unit frame of intercepting full frame, sends to current L _g,jminimum region R _g, perform step (2.1.1)～(2.1.k), if do not exist full frame to go to step (2.2); Queue VOQ _i,jequalizing coefficient equals its mapping area R _gthe length of output queue j, is denoted as L _g,j;

If (2.1.1) first order input port i is to second level input port S _{g, 1}inner link idle, by VOQ _i,jqueue heads cell sends to region R _gsecond level input port S _{g, 1}, otherwise f=(f+1) modN/k goes to step (2.1);

(2.1.2) send VOQ _i,jqueue heads cell is to region R _gsecond level input port S _{g, 2};

(2.1.3) send VOQ _i,jqueue heads cell is to region R _gsecond level input port S _{g, 3};

The rest may be inferred sends VOQ to (2.1.k) _i,jqueue heads cell is to region R _gsecond level input port S _g,k, g=(g+1) modN/k, goes to step (2.1);

(2.2) if flow branching vOQ queue, VOQ _i,j, there is the highest dispatching priority unit frame in kf≤j<kf+k wherein, searches flow distribution matrix L, and this unit frame is sent to current L _g,jminimum region R _g, perform step (2.1.1)～(2.1.k), otherwise go to step (2.3);

(2.3) if flow branching there are one or more unit frame in VOQ queue, searches flow distribution matrix L, selects the unit frame of minimum equalizing coefficient VOQ queue according to lookup result, sends it to flow branching fixedly mapping area R _g, perform step (2.1.1)～(2.1.k), if only can skip the search operation of flow distribution matrix containing a unit frame, directly the unique unit frame of flow branching is sent to its fixedly mapping area R _g, otherwise flow branching , containing any unit frame, g=(g+1) modN/k, does not go to step (2.1);

Wherein, VOQ _i,jthe VOQ j that represents first order input port i; the output queue j that represents second level input port l; F (i, j) represents the stream from first order input port i to output port j; K is polymerization granularity, represents the number of scheduling same stream cell continuously, and k is the factor of port number N; VOQ _i,jevery k cell of queue forms a unit frame, and the unit frame of the first order input port i N/k of place different VOQ queues forms an aggregate frame, amounts to N cell; VOQ _i,jthe N of a queue cell, forms a full frame; Second level input port 1,2 ...., N is divided into N/k group successively, and each group is containing k continuous second level input port, and k second level input port of g group forms a region, is denoted as R _g, S _r,zz the second level input port that represents region r; It is corresponding with N/k region that the N bar stream of each second level input port is divided into N/k group, and every group is flowed containing k bar, and the k bar stream of second level input port i f group forms a flow branching, is denoted as

Described external time groove in order to be R in speed, link sends or receives the time that cell is spent.

2. the load equilibration scheduling method based on two-stage exchange according to claim 1, is characterized in that, adopts two endless form to build the mapping that flows to region:

(1.1) build in a looping fashion N/k flow branching of first order input port to the mapping in an input port N/k region, the second level, to guarantee that each region be able to contain all stream;

(1.2) further adjust in a looping fashion the associated of different first order input ports and N/k kind mapping mode, to guarantee that each region contains all stream according to the equiblibrium mass distribution of second level input port.