HK1047507B - Pipelined scheduling method and scheduler - Google Patents

Description

Pipeline scheduling method and scheduling device

Technical Field

The present invention relates to a packet switching system, and more particularly, to a pipeline scheduling method and scheduling apparatus implemented in a packet switching system.

Description of the Prior Art

With the rapid increase in internet usage, the use of the internet as a communication infrastructure is increasingly demanded. In order for the internet to function as a communication infrastructure, a router as a server node is required to increase the data transfer speed and enhance the function thereof. The existing high-speed router adopts the IP address search realized by hardware and the high-speed data transmission processing process by using the self-routing high-speed switch system structure.

To accommodate this growing demand for high-speed switching, Virtual Output Queue (VOQ) crosspoint switch systems having N input ports and N output ports are widely used, where each input port has N logical queues each corresponding to N output ports. Methods of scheduling such crosspoint switch systems have been proposed.

5,299,190 discloses a two-dimensional round robin scheduling mechanism. This mechanism employs a request matrix with each row representing an input and each column representing an output. Thus, a bit in a given row and column in the matrix represents a request issued by a corresponding input port to connect to a corresponding output port. The diagonal traffic patterns are used to overlay the request matrix to determine which request is to be serviced. The sequence diagonal traffic pattern for each of the K slots is used to provide guaranteed traffic fairly.

Us patent 5,734,649 discloses a similar scheduling method used in data packet routers. In this data packet router, a matrix of crosspoint switch system cells connects a data source to a selected destination during each of a series of intervals. The assignment of the switching system cells to the required connections can be achieved by a procedure which provides a data array with the same number of data cells as the number of switching system cells. During each interval, a data source is assigned to each data unit according to a first current pseudorandom shuffle (shuffle) pattern, and a respective destination is assigned to each data unit according to a second current pseudorandom shuffle pattern. During each interval, a new shuffle pattern set is generated. The diagonal grouping process, which is performed successively through the regions of the array of sources and destinations, is examined to search for previously unspecified matches and each match is assigned to the switching system unit according to the respective data unit.

However, these conventional scheduling methods have a drawback in that the amount of data processing performed per slot rises by the square of the number of ports. Therefore, since the number of input/output ports is increasing, it is difficult to increase the scheduling speed.

As a scheduling protocol that is expected to overcome the above-mentioned drawbacks, the applicant proposed a round-robin greedy scheduling (RRGS) algorithm in japanese patent application No. 11-172584 (unexamined publication No. P2000-174817). The RRGS algorithm can be implemented in an nxn packet switch, where N scheduling modules S are provided for N inputs, respectively₁To S_N. Scheduling Module S₁To S_NEach scheduling module performs scheduling of a predetermined future time slot and transmits the reserved output port information to the adjacent scheduling module. In this way, the reservation of output ports at the predetermined future time slot is completed during the N time slots before the predetermined future time slot. This scheduling process is performed at each time slot through a pipeline processing process to realize a future time slot nxn scheduling process, thereby realizing a high-speed packet forwarding process.

The present applicant proposed a framing RRGS algorithm in japanese patent application No. 2000-55103 (unexamined publication No. 2001-7822). In this framed RRGS, a sequence of frames is set, each frame of which comprises a plurality of time slots. Incoming packets are scheduled at the current frame such that the next frame after the current frame is forwarded to an appropriate output port. More specifically, scheduling can be performed in each frame by synchronously starting the scheduling discrimination process of the N input port scheduling modules at the start of the frame, synchronously performing the scheduling discrimination process by using a pipeline method in the frame, and synchronously completing the scheduling discrimination process at the end of the frame.

Although the RRGS algorithm and framing RRGS algorithm described above can provide high-speed, efficient data forwarding, the output port arbitration throughput is gradually increasing as the number of input ports and output ports is increasing.

Summary of the invention

An object of the present invention is to provide a pipeline scheduling method and scheduling apparatus that can perform high-speed scheduling according to the number of input ports and output ports.

Another object of the present invention is to provide a pipeline scheduling method and scheduling apparatus which can perform high-speed scheduling and also suppress unfairness between inputs.

According to one aspect of the invention, in a crosspoint switch system, scheduling means for scheduling a packet-forwarding connection from N input ports to a selected one of N output ports at each time slot, where N is a positive integer, the scheduling means comprises: an M matrix of scheduling modules, each scheduling module scheduling packet forwarding connections from a respective input group of input ports to an output group selected from a respective output group of output ports at each time slot according to reservation information indicating a reserved combination of the respective input ports and output ports, wherein N input ports are equally divided into M input groups and N output ports are equally divided into M output groups; and a selector for selecting sequential module patterns from different module patterns comprising an M x M matrix of scheduling modules, wherein each different module pattern determines a set comprising M scheduling modules to avoid collision with each other and determines a sequence of transfer reservation information, wherein the scheduling module determined by the selected module pattern reserves the packet forwarding connection based on current reservation information indicating a reserved combination of the corresponding input port and output port, and transfers updated reservation information based on the sequence determined by the selected module pattern.

According to another aspect of the present invention, a pipeline scheduling method for an nxn crosspoint switch system, connecting N input ports to respective output ports selected from among N output ports at respective time slots, includes the steps of: a) storing N logical queues for each of N input ports corresponding to each of N output ports, wherein N input ports are equally divided into M input groups and N output ports are equally divided into M output groups; b) storing packet forwarding requests in an M x M matrix of modules, each module of which stores packet forwarding requests for each output group selected from a corresponding input group of input ports to a corresponding output group of output ports; c) selecting M module graphics covering an M module matrix, wherein each module graphic determines a different set comprising M modules to avoid collision with each other; and d) in each time slot, performing the following steps d.1) to d.3) in each of the M modules determined by each of the selected M module graphics to implement a pipeline scheduling process: d.1) reserving a combination of the respective input port and output port at a predetermined future time slot in accordance with the respective packet forwarding request based on the input port reservation information and the output port reservation information received from the first two-stage modules in the row direction and the column direction of the M × M matrix; d.2) updating the input port reservation information and the output port reservation information depending on which combination is reserved; and d.3) transferring the updated input port reservation information and output port reservation information to subsequent two-stage modules in the row direction and column direction of the M x M matrix.

Step d) may be performed simultaneously in M scheduling processes for different future time slots, wherein each scheduling process of the M scheduling processes starts with a different module pattern of the selected M module patterns. Each selected M module patterns may be diagonal service patterns within a predetermined set of diagonal module patterns.

According to the present invention, a method for scheduling packet forwarding connections providing a combination of N input ports and N output ports of a crosspoint switch system, comprises the steps of: dividing possible combinations of N input ports and N output ports into M multiplied by M groups, wherein the N input ports are equally divided into M groups, and the N output ports are equally divided into M groups; assigning a packet forwarding request sent from an input port to an output port to a corresponding one of the M x M groups; sequentially selecting predetermined M diagonal service pattern sets from the M multiplied by M groups; and scheduling packet forwarding connections in a pipelined manner according to the sequentially selected diagonal traffic patterns.

As described above, different module graphics including an M × M scheduling module matrix are prepared to avoid collision with each other. Therefore, the M × M scheduling module matrix can perform pipeline scheduling in the row direction and the column direction of the matrix, thereby improving the efficiency of packet forwarding and thus realizing high-speed scheduling. Further, since the input ports and the output ports are divided into M × M packets, high-speed scheduling can be performed according to the number of input ports and output ports.

The M scheduling processes for different future time slots may be performed simultaneously in a pipelined manner, and each of the M scheduling processes begins with a different one of the selected M module graphics. Thus, an equal reservation opportunity is provided for the M × M scheduling module matrix.

Brief description of the drawings

Fig. 1 shows a block diagram of a packet switching system employing a switching system scheduling apparatus according to the present invention;

FIG. 2 is a schematic diagram illustrating the correspondence between sets of input lines and sets of output lines;

FIG. 3 shows a block diagram of a switching system scheduling apparatus according to an embodiment of the present invention;

fig. 4 shows a schematic diagram of the packet storage state of the VOQ in an embodiment;

FIG. 5A is a block diagram of an example of a switching system scheduling apparatus for illustrating a two-dimensional pipeline scheduling method according to an embodiment of the present invention;

FIG. 5B is a schematic diagram illustrating an example of a matrix stored in one of the scheduling modules of the switching system scheduling apparatus shown in FIG. 5A;

FIG. 6 is a timing diagram of a first slot frame during two-dimensional pipeline scheduling performed by the switching system scheduler shown in FIG. 5A;

FIG. 7 is a timing diagram illustrating a second slot frame during two-dimensional pipeline scheduling performed by the switching system scheduler shown in FIG. 5A;

FIG. 8 is a timing diagram showing a third slot frame in the two-dimensional pipeline scheduling process performed by the switching system scheduler shown in FIG. 5A;

FIG. 9 is a schematic diagram showing a first example of a selected diagonal module set and a diagonal module join sequence in a two-dimensional pipeline scheduling process performed by the switching system scheduler shown in FIG. 5A;

FIG. 10 is a schematic diagram showing a second example of a selected set of diagonal modules and a connection sequence of diagonal modules in a two-dimensional pipeline scheduling process performed by the switching system scheduler shown in FIG. 5A;

FIG. 11 is a schematic diagram showing a third example of a selected diagonal module set and a diagonal module join sequence in the two-dimensional pipeline scheduling process performed by the switching system scheduler shown in FIG. 5A;

FIG. 12 is a schematic diagram showing a fourth example of a selected set of diagonal modules and a connection sequence of diagonal modules in a two-dimensional pipeline scheduling process performed by the switching system scheduling apparatus shown in FIG. 5A;

FIG. 13 is a schematic diagram showing a fifth example of a selected diagonal module set and a diagonal module join sequence in the two-dimensional pipeline scheduling process performed by the switching system scheduler shown in FIG. 5A; and

fig. 14 is a diagram showing a sixth example of a selected diagonal module set and a diagonal module connection sequence in the two-dimensional pipeline scheduling process performed by the switching system scheduling apparatus shown in fig. 5A.

Description of The Preferred Embodiment

Switching system

Referring to fig. 1, a packet switching system according to an embodiment of the present invention includes a switching system portion 201 including an N × N crosspoint switch system 202 and a switching system scheduling device 203. The cross-point switch system 202 has N input ports corresponding to N input lines 204_1 to 204_ N, respectively, and N output ports corresponding to N output lines 205_1 to 205_ N, respectively, where N is an integer greater than 1. The N input ports of the crosspoint switch system 202 are connected to N input lines 204_1 to 204_ N, respectively, through N input interfaces each comprising N VOQs (virtual output queues) 206_1 to 206_ N, respectively. The N input interfaces each include both a VOQ and a destination resolution engine and a packet assembly/disassembly Portion (PAD), not shown in fig. 1. Here, the crosspoint switch system 202 switches fixed length packets (cells). The PAD assembles packets of cells received from the crosspoint switch system 202 and breaks packets received from the corresponding input lines into cells for forwarding to the crosspoint switch system 202.

From a functional point of view, the N input lines 204_1 to 204_ N are equally divided into M Input Groups (IG)211, where M is a divisor of N. Thus, each input set 211 accommodates N/M input lines and a corresponding VOQ. Likewise, the N output lines 205_1 to 205_ N are equally divided into M Output Groups (OG) 212. Thus, each output group 212 accommodates N/M output lines. Each of the VOQs 206_1 to 206_ N transmits a packet transfer Request (RQ) to the switching system scheduler 203 and receives a packet transfer permission (OK) from the switching system scheduler 203.

Referring to fig. 2, as described above, the N input lines 204_1 to 204_ N are equally divided into M input groups IG _1 to IG _ M, and the N output lines 205_1 to 205_ N are equally divided into M output groups OG _1 to OG _ M. Thus, there are M × M different combinations of M input groups and M output groups. In this embodiment, M × M scheduling modules S (1, 1) to S (M, M) are set according to each M × M different combinations.

VOQs 206_1 to 206_ N have the same structure. As shown in fig. 4, for example, assuming that VOQ 206_1 corresponds to input line 204_1, VOQ 206_1 stores N logical queues (buffers) 242_1 to 242_ N corresponding to N output lines 205_1 to 205_ N, respectively. From a functional point of view, the N logical queues 242_1 to 242_ N are equally divided into M groups 244_1 to 244_ M corresponding to the M output groups OG _1 to OG _ M, respectively. When a fixed length packet arrives at VOQ 206_1 through the input interface of input line 204_1, the input packet is sent to and stored in one of N logical queues 242_1 through 242_ N, depending on the destination address of the input packet. As shown by the diagonal hatching in fig. 4, the number of packets stored in one queue may differ from one queue to another.

Switching system scheduling device

As shown in fig. 3, the switching system scheduler 203 has M × M scheduling modules S (1, 1) to S (M, M) corresponding to each of M × M different combinations. Here, the scheduling module S (i, j) corresponds to the ith input group IG _ i and the jth output group OG _ j, where i is 1, 2. Since the input group IG _ i and the output group OG _ j accommodate N/M input lines and N/M output lines, respectively, the scheduling module S (i, j) performs N/mxn/M different schedules in view of future time slots, according to packet forwarding requests issued by the corresponding N/M VOQs. Upon completion of this scheduling, the scheduling module S (i, j) transmits the reserved input port information 231_ j, or the input port reservation status updated by the scheduling module S (i, j), to the neighboring scheduling module S (i-1, j), where if i-1 is 0, M is substituted. At the same time, the scheduling module S (i, j) transmits the reserved output port information 232_ i or the output port reservation status updated by the scheduling module S (i, j) to the adjacent scheduling module S (i, j +1), where if j +1 is M +1, 1 is substituted.

In this embodiment, the packet to be forwarded has a fixed length, and one slot is defined as the time period required to forward the packet from one input port to one output port. When receiving the reserved input port information 231_ j and the reserved output port information 232_ i from the previous scheduling modules S (i +1, j) and S (i, j-1), the scheduling module S (i, j) performs two-dimensional reservation of the input port and the output port to avoid collision with other scheduling modules according to the packet forwarding request issued by the corresponding VOQ and the reserved input port information 231_ j and the reserved output port information 232_ i.

In fig. 3, the reserved input port information 231_ j sequentially accesses the schedule module columns S (1, j) to S (M, j) in a round robin manner, and the reserved output port information 232_ i sequentially accesses the schedule module rows S (i, 1) to S (i, M) in a round robin manner. In other words, the scheduling modules S (1, 1) to S (M, M) are connected in the row and column directions to patrol the reservation information. However, such a scheduling module connection sequence is not limited to the case shown in fig. 3. The scheduling module connection sequence may be determined according to which diagonal module group is selected among different diagonal module groups (refer to fig. 9 to 14).

Two-dimensional pipeline scheduling process

As shown in fig. 5A, a scheduling module S is provided in the switching system scheduling apparatus₁To S₁₆For the sake of simplicity, assume that in fig. 3, N-16 and M-4. In this case, the switching system section 201 has a 16 × 16 cross-point switch system 202 having 16 input ports and 16 output ports. The 16 input lines are equally divided into 4 input groups and the 16 output lines are equally divided into 4 output groups. Thus, there are 16 different combinations of 4 input groups and 4 output groups, corresponding to each scheduling module S₁To S₁₆。

Referring to FIG. 5B, a scheduling module S_i(i ═ 1, 2,.. or 16) stores a 4 × 4 matrix corresponding to input ports (represented by numerals 1 to 4 located on the left side of the matrix in the vertical direction) and output ports (represented by numerals 1 to 4 located on the upper side of the matrix in the horizontal direction). More particularly, toIn other words, each matrix element of the 4 × 4 matrix uses a logical value "1" or "0" to indicate whether there is a packet forwarding request sent by the corresponding input port to the corresponding output port. Taking the scheduling module S1 as an example, since the (1, 1) matrix element is 0, it indicates that no packet forwarding request sent from the input port 204_1 to the output port 205_1 is received. Since the (1, 2) matrix element is "1", it indicates that a packet forwarding request sent from the input port 204_1 to the output port 205_2 is received.

In FIG. 5A, a scheduling module S₁A 4 × 4 matrix of input ports 204_1 to 204_4 (indicated by port numbers 1 to 4 in the vertical direction on the left side of the matrix) and output ports 205_1 to 205_4 (indicated by port numbers 1 to 4 in the horizontal direction on the upper side of the matrix) is stored. Likewise, a scheduling module S₂A 4 × 4 matrix of input ports 204_1 to 204_4 (indicated by port numbers 1 to 4 in the vertical direction on the left side of the matrix) and output ports 205_5 to 205_8 (indicated by port numbers 5 to 8 in the horizontal direction on the upper side of the matrix) is stored. Subsequent scheduling module S₃To S₁₆And so on.

For example, when a packet received at the input port 204_2 is to be forwarded to the output port 205_3, the corresponding VOQ sends a packet forwarding request to the output port 205_3 to the switching system scheduler 203. In this case, the packet forwarding request enters the scheduling module S₁Thus, the (2, 3) matrix element of the matrix changes from "0" to "1". Likewise, when a packet received at the input port 204_7 is to be forwarded to the output port 205_11, the corresponding VOQ 206_7 sends a packet forwarding request to the output port 205_11 to the switching system scheduler 203. In this case, the packet forwarding request enters the scheduling module S₇And the (3, 3) matrix elements in the matrix thus change from "0" to "1".

As shown in FIG. 5A, in this example, four scheduling modules S are in the selected set of diagonal modules₁、S₆、S₁₁And S₁₆Diagonal business figures are provided. As can be appreciated from FIG. 5A, four scheduling modules S₁、S₆、S₁₁And S₁₆In combination, conflicts with other scheduling modules can be avoided. For example, the scheduling module S₁The input ports 204_1 to 204_4 are not connected to other scheduling modules S₆、S₁₁And S₁₆Conflict with other input ports 204_5 to 204_ 16. Likewise, a scheduling module S₁Does not interact with other scheduling modules S₆、S₁₁And S₁₆Output ports 205_5 to 205_16 collide.

There are also three diagonal service patterns in the selected set of diagonal modules: (S)₂、S₇、S₁₂、S₁₃)；(S₃、S₈、S₉、S₁₄) (ii) a And (S)₄、S₅、S₁₀、S₁₅). The four diagonal service patterns respectively and simultaneously carry out scheduling processes on different future time slots by using the same time slot, thereby improving the scheduling efficiency.

When each scheduling module completes its scheduling process within the time slot, the scheduling module sends the reserved input port information to the neighboring scheduling module located in the direction of the horizontal arrow shown in fig. 5A. At the same time, the scheduling module also transfers the reserved output port information to an adjacent scheduling module located in the direction of the vertical arrow shown in fig. 5A. For example, the scheduling module S₁Updating the reserved input port information 265 and transferring the updated input port information 265 to the neighboring scheduling module S₂. At the same time, the scheduling module S₁Updates the reserved output port information 261 and transfers the updated output port information 261 to the adjacent scheduling module S₁₃. Each scheduling module performs a 4 x 4 scheduling process of a predetermined future time slot based on a packet forwarding request received from a corresponding VOQ and input port information and output port information received from a previous scheduling module. The scheduler module updates the reserved input port information and output port information and transfers them to the next scheduler module.

Thus, with 4 slots, the reserved input port information and output port information walks through the scheduling moduleBlock S₁To S₁₆And simultaneously, each scheduling module carries out respective scheduling processing process, thereby realizing the scheduling process of the scheduled future time slot.

There are two requirements to perform the scheduling process described above. First, the 4 × 4 scheduling process of the scheduling module including the transmission process of the reserved input port information and output port information must be completed in one slot. Second, equal reservation opportunities must be provided for the four input VOQs of each group. In other words, any scheduling algorithm may be employed if the requirements of one slot completion and fairness are met. For example, the scheduling algorithms disclosed in U.S. patent No. 5,299,190 and U.S. patent No. 5,734,649 may be used.

Referring to fig. 6, in this example, a scheduling module S providing a diagonal service pattern in a selected diagonal module group₁、S₆、S₁₁And S₁₆Having rights first in time slot T₁Starting for future time slot T_sThe input and output combinations of (a) and (b) are reserved.

When there are packet forwarding requests sent from the input ports 204_1 to 204_4 to the output ports 205_1 to 205_4 and some of them collide, the scheduling module S₁Packet forwarding requests are arbitrated. For example, if all VOQs 206_1 to 206_4 request the same output port 205_1, the scheduling module S₁These requests are arbitrated to respond to only one request. Likewise, the scheduling module S when there are packet forwarding requests sent from the input ports 204_5 to 204_8 to the output ports 205_5 to 205_8 and some of them collide₆These packet forwarding requests are arbitrated. When there are packet forwarding requests from the input ports 204_9 to 204_12 to the output ports 205_9 to 205_12 and some of them collide, the scheduling module S₁₁These packet forwarding requests are arbitrated. When there are packet forwarding requests sent from the input ports 204_13 to 204_16 to the output ports 205_13 to 205_16 and some of them collide, the scheduling module S₁₆These packet forwarding requests are arbitrated. Thus, in the time slotT₁Scheduling Module S₁、S₆、S₁₁And S₁₆The scheduling process of the scheduling process group 281 is performed.

After the scheduling process is completed, the scheduling module S₁、S₆、S₁₁And S₁₆The reservation state information is updated and transmitted. More specifically, the scheduling module S₁Updates the reserved input port information 265 and the reserved output port information 261, and then transfers the updated input port information 265 and the updated output port information 261 to the adjacent scheduling modules S, respectively₂And adjacent scheduling module S₁₃. Scheduling Module S₆Updates the reserved input port information 266 and the reserved output port information 262, and then transfers the updated input port information 266 and the updated output port information 262 to the neighboring scheduling module S, respectively₇And adjacent scheduling module S₂. Scheduling Module S₁₁Updates the reserved input port information 267 and the reserved output port information 263, and then transfers the updated input port information 267 and the updated output port information 263 to the neighboring scheduler module S, respectively₁₂And adjacent scheduling module S₇. Scheduling Module S₁₆Updates the reserved input port information 268 and the reserved output port information 264, and then transfers the updated input port information 268 and the updated output port information 264 to the adjacent scheduling modules S, respectively₁₃And adjacent scheduling module S₁₂。

In the next time slot T₂According to the received packet forwarding request and respectively from the preceding scheduling module S₁、S₆、S₁₁And S₁₆Received input port information and output port information, a scheduling module S₂、S₇、S₁₂And S₁₃Making future time slots T₃The next scheduling of the group 281 of scheduling processes. As described above, the time slot T is in the current scheduling stage₂The combination of the input port and the output port previously received cannot be retained. After the scheduling process is completed, the scheduling module S₂、S₇、S₁₂And S₁₃As described aboveUpdates the retained state information and transmits them.

In the next time slot T₃According to the received packet forwarding request and respectively from the preceding scheduling module S₂、S₇、S₁₂And S₁₃Received input port information and output port information, a scheduling module S₃、S₈、S₉And S₁₄Proceed to the future time slot T₅The next stage scheduling of the set 281 of scheduling processes. After the scheduling process is completed, the scheduling module S₃、S₈、S₉And S₁₄The retained state information is updated and transmitted as described above.

In the next time slot T₄According to the received packet forwarding request and respectively from the preceding scheduling module S₃、S₈、S₉And S₁₄Received input port information and output port information, a scheduling module S₄、S₅、S₁₀And S₁₅Making future time slots T₅The next stage scheduling of the set 281 of scheduling processes.

Also, T at 4 slots₁To T₄The future time slot T is completed during the time period₅Group 281 of scheduling processes. In other words, the future time slot T is completed₅From the input ports 204_1 to 204_16 to the correct ones of the output ports 205_1 to 205_ 16.

However, as described above, during the scheduling process group 281, such as the scheduling module set S₁、S₆、S₁₁And S₁₆Only one slot is scheduled for one diagonal traffic pattern. Thus, the other three scheduling process groups 282 through 284 for other different time slots may be performed in parallel with the scheduling process group 281, as shown in fig. 6. In addition, to guarantee the scheduling module S₁To S₁₆The fairness between them can be implemented by using four diagonal traffic patterns to start with different sets of diagonal modules to perform the scheduling processes 281 to 284 respectively. This will be explained in detail below。

As shown in fig. 6, in time slot T₁Scheduling module S for providing another diagonal service pattern in selected diagonal module group₂、S₇、S₁₂And S₁₃Making future time slots T₆The scheduling process of the scheduling process group 282. After the scheduling process is completed, the scheduling module S₂、S₇、S₁₂And S₁₃The reservation state information is updated and transmitted.

In the next time slot T₂According to the received packet forwarding request and respectively from the preceding scheduling module S₂、S₇、S₁₂And S₁₃Received input port information and output port information, a scheduling module S₃、S₈、S₉And S₁₄Making future time slots T₆The next stage scheduling process of the scheduling process group 282. After the scheduling process is completed, the scheduling module S₃、S₈、S₉And S₁₄The retained state information is updated and transmitted as described above.

In the next time slot T₃According to the received packet forwarding request and respectively from the preceding scheduling module S₃、S₈、S₉And S₁₄Received input port information and output port information, a scheduling module S₄、S₅、S₁₀And S₁₅Making future time slots T₆The next stage scheduling process of the scheduling process group 282. After this scheduling procedure is completed, the scheduling module S₄、S₅、S₁₀And S₁₅The retained state information is updated and transmitted as described above.

In the next time slot T₄According to the received packet forwarding request and respectively from the preceding scheduling module S₄、S₅、S₁₀And S₁₅Received input port information and output port information, a scheduling module S₁、S₆、S₁₁And S₁₆Making future time slots T₆The next stage scheduling process of the scheduling process group 282.

Thus, in four time slots T₁To T₄In parallel with the above-mentioned scheduling process group 281, the future time slot T is completed₆Group 282. Likewise, four time slots T can be used₁To T₄In parallel with the above-described scheduling process groups 281 and 282, the future time slot T is completed₇And T₈283 and 284.

As shown in fig. 7 and 8, the same processing is performed for the scheduling processing procedure groups 285 to 289. Each scheduling processing group running in parallel starts with a different diagonal service graph, so that the scheduling module S can be used₁To S₁₆Providing the same opportunity for reservation.

Diagonal module group

In fig. 9 to 14, various diagonal module groups each having a different module connection order are shown. In a scheduling module S as shown in FIG. 5A₁To S₁₆Four black dots form a diagonal traffic pattern in each 4 x 4 matrix of the array of (a). The diagonal module group includes four diagonal service patterns connected together in series by three horizontal arrows.

In fig. 9 to 14, the upper parentheses of the matrices shown in the upper left corners of fig. 9 to 14, which include sets of 4 numbers separated by commas, respectively, represent the transfer sequence of reserved input port information that is generally used in each of the matrices shown in fig. 9 to 14. The four numbers arranged vertically on the left side of the leftmost matrix in each diagonal module group represent the transfer sequence of the input port information that is retained. The numbers in parentheses at the bottom of each matrix represent the sequence numbers of the diagonal traffic patterns. In fig. 9 to 14, the same sequence numbers indicate the same diagonal traffic patterns.

In this embodiment explained with reference to fig. 5A, 6, and 7, four diagonal traffic patterns represented by the sequence numbers (1), (2), (3), and (4) shown in fig. 9 are used as the diagonal module group.

More specifically, in the sequence T₁A scheduling module S for forming a first diagonal service pattern (1)₁、S₆、S₁₁And S₁₆The scheduling process of the scheduling process group 281 is performed. After the scheduling process is completed, the scheduling module S numbered 1₁Communicating the updated reserved input port information 265 to the adjacent scheduling module S numbered 2₂. At the same time, the scheduling module S numbered 1₁Passing the updated reserved output port information 261 to the adjacent scheduling module S numbered 4₁₃. Also, as shown by the horizontal and vertical arrows in fig. 5A, the reserved input port information 265 and the reserved output port information 261 may be sequentially transferred to the adjacent scheduling modules. Thus, in the selected diagonal module group, four numbers separated by commas within parentheses, respectively, are represented in the following order: 1. 2, 3, 4, and the four numbers arranged vertically on the left side of the matrix are represented in the following order from top to bottom: 1. 4, 3 and 2.

As described above, such a scheduling module connection order is not limited to the case shown in fig. 5A. The scheduling module connection order may be determined according to which diagonal module group is selected from different diagonal module groups, as shown in fig. 9 to 14.

It is clear that the invention is not limited to 4 x 4 switching systems, but it can be applied to matrices of any size.

Claims (6)

1. A pipeline scheduling method for an nxn crosspoint switch system that connects N input ports to respective output ports selected from among N output ports at respective time slots, the method comprising the steps of:

(a) storing N logical queues for each of N input ports corresponding to each of N output ports, wherein the N input ports are equally divided into M input groups and the N output ports are equally divided into M output groups, wherein M is a divisor of N and is not equal to 1;

(b) storing packet forwarding requests in an M x M matrix of modules, each module of which stores packet forwarding requests for each output group selected from a corresponding input group of input ports to a corresponding output group of output ports;

(c) selecting M module graphics covering M x M matrix modules, wherein each module graphic determines a different set comprising M modules to avoid collision with each other; and

(d) in each time slot, performing the following steps d.1) to d.3) in each module of the M modules determined by each selected M module graphics to realize a pipeline scheduling process;

d.1) reserving a combination of the respective input port and output port at a predetermined future time slot in accordance with the respective packet forwarding request based on the input port reservation information and the output port reservation information received from the first two-stage modules in the row direction and the column direction of the M × M matrix;

d.2) updating the input port reservation information and the output port reservation information depending on which combination is reserved; and

d.3) transferring the updated input port reservation information and the updated output port reservation information to the subsequent two-stage module in the row direction and the column direction of the M × M matrix.

2. The pipeline scheduling method of claim 1, wherein step d) can be performed simultaneously in M scheduling processes for different future time slots, wherein each scheduling process of the M scheduling processes starts with a different module graphic of the selected M module graphics.

3. The pipeline scheduling method of claim 1, wherein each selected M module patterns may be diagonal service patterns within a predetermined set of diagonal module patterns.

4. A scheduler for an nxn crosspoint switch system that connects N input ports to respective output ports selected from among N output ports at respective time slots, the scheduler comprising:

n logical queues for each of N input ports corresponding to each of N output ports, wherein the N input ports are evenly divided into M input groups and the N output ports are evenly divided into M output groups, wherein M is a divisor of N and is not equal to 1;

an M x M matrix of scheduling modules, each scheduling module storing packet forwarding requests from a corresponding input group of input ports to each output group selected from a corresponding output group of output ports, according to corresponding packet forwarding requests, input port reservation information, and output port reservation information;

a selector for selecting M module patterns covering the M scheduling module matrix, wherein each module pattern of the M module patterns determines a different set of M scheduling modules to avoid collision with each other,

wherein at each time slot, each of the M scheduling modules defined by each of the selected M module graphics reserves a corresponding packet forwarding request for a predetermined future time slot, updates the input port reservation information and the output port reservation information according to the reservation contents, and transmits the updated input port reservation information and the updated output port reservation information to two subsequent-stage modules in the row direction and the column direction of the M x M matrix.

5. The scheduler of claim 4 wherein each of the M module patterns is a diagonal traffic pattern in a predetermined set of diagonal modules.

6. The scheduling apparatus of claim 4 wherein the selected M scheduling patterns identify scheduling modules that are concurrently performing M scheduling processes for different future time slots, wherein each of the M scheduling processes begins with a different one of the selected M module patterns.