1. Field of the Invention
The present invention relates generally to a packet switch. More particularly, the invention relates to a packet switch for scheduling between input and output in a packet switching system and realizing the scheduling.
2. Description of the Related Art
In the recent packet switching system, an input buffer type switch having N in number of inputs and N in number of outputs (N is natural number: the same shall be applied hereinafter) and, in which each input portion has N in number of virtual output queuing (VOQ), is typically employed.
FIG. 11 shows a construction of a typical input buffer type packet switch having N inputs and N outputs (N is natural number: the same shall be applied hereinafter). Referring to FIG. 11, a packet switch 40 has a plurality of input ports inputting data, a plurality of output ports outputting data, a data switching element 54 switching data input from the input port to transfer to the output port and a scheduler 50 controlling the switching element.
The input port has a construction of a virtual output queuing (VOQ) 52. As the switching element 54, a cross-bar switch is typically employed. The scheduler 50 employs a distributed scheduling construction, and is consisted of distributed scheduling modules 51-i (i=1 to N) per the input port.
The packet switch set forth above is assumed to perform transfer in the cross-bar switch with a fixed size packet. By this, an operation period of the switch system is quantized. A unit for quantization is referred to as time slot.
The scheduler receives a connection request information (REQ) per the output port from the input port per time slot to determine connection grant information (GRANT) between the input port and the output port on the basis of the connection request information. The scheduler generates a connection information (MSEL) between the input port and the output port on the basis of the connection grant information to notify to the switching element for setting connection of the input and output of the switching element.
On the other hand, the scheduler generates a transfer grant information (DSTMSG) indicative of the output port granted data transfer from each input port on the basis of the connection grant information to notify the transfer grant information for each input port. The input port outputs data to the switching element according to the transfer grant information to complete switching by reception of data to the output port.
A task of the scheduler is to generate the N×N connection grant information from the N×N connection request information. Upon generation of the connection grant information, each distributed scheduling modules 51-1 to 51-N determine permission and rejection of connection of the individual input port to the output port.
The output port granted connection by a certain distributed scheduling module 51-n (n is natural number 1≦n≦N) is a port “reserved” for other distributed scheduling module for another distributed scheduling module 51-m (m≠n) and becomes the port impossible to issue connection grant. Hereinafter, operation for determining connection grant to the output port by certain scheduling module is expressed as “reserve output port”.
As a distributed type scheduling algorithm of the packet switch, there is a round robin greedy scheduling (RRGS) algorithm reported in A. Smiljanic, R. Fan and G. Ramanurthy “RRGS* Round Robin Greedy Scheduling for Electric/Optical Terabit Switches” in Globecom, 1999.
In case of the scheduler employing the RRGS algorithm, the distributed scheduling module is connected in ring form for transferring message between adjacent distributed scheduling module. In the RRGS algorithm, reservation (connection grant determination) of time slot to be an object of the distributed scheduling module is performed to transfer the resultant information to the next distributed scheduling module. In order to ease message transfer speed demand condition, RRGS introduces a pipeline function. A reservation process of the time slot is completed upon completion of message transfer between respective distribution scheduling modules in one cycle. On the other hand, N in number of distributed scheduling module makes reservation for at least N slots ahead of the current slot. Furthermore, the RRGS algorithm progresses the reservation process for N time slots with shifting phase per one time slot.
On the other hand, as a modification of the RRGS algorithm, it can be considered an algorithm, in which reservation process for a plurality of time slots are started simultaneously from respectively different distributed scheduling modules to progress for completing simultaneously. Such algorithm is referred to as a framed RRGS.
FIG. 12 is a block diagram showing a construction of the packet switch with the distributed type scheduler employing the RRGS and framed RRGS. In FIG. 12, as an example, a system having four ports (N=4). In FIG. 12, the scheduler 1 is constructed with input modules (IM) 10-1 to 10-4 for performing distributed type scheduling. For each module 10-i (i=1 to 4), a frame pulse (FP) 21 indicative of the leading end of the frame and a super frame pulse (SuperFP) indicative of the leading end of a super frame. Each module 10-i operates in synchronism with the frame pulse 21 or the super frame pulse 22.
On the other hand, in each module 10-i, a physical number 23 is set for identification of the module. The connection request information 11 is input to the module 10-i from each input port for negotiation of the connection request. Each module 10-i outputs the connection grant information 12-1 to 12-4 representative of determined reservation (connection grant) resulting from negotiation.
In the RRGS and the framed RRGS, conflict of the connection demand for the output port is avoided by transferring “reserved output port information” as information degenerated input port information from the connection grant information (information generated with reference to the input port information) between adjacent distributed scheduling modules. For example, the module 10-3 receives the reserved output port information 14-2 from the preceding module 10-2 as reserved output port information 13-3 for use in negotiation for the connection request. After determination of the connection grant information, the reserved output port information 14-3 is notified to the module 10-4 in the next stage.
FIG. 13 is an illustration showing an example of general operation of the framed RRGS. Operation of the framed RRGS will be discussed hereinafter with reference to FIGS. 12 and 13.
Transfer direction of the reversed output port information in module number is #1→#2→#3→#4→#1→#2
Polarities of respective information are defined as follow. The connection request of each input port is 1 when the request is present and 0 when no request is present. The connection grant information (reserve information) is 1 when connection is granted (reserved) and 0 when connection is inhibited (non-reserved). The reserved output port information is 1 as reserved and 0 as not reserved.
In the shown example one frame consists of four time slots and the frame pulse 21 is input in four time slot periods. Also, the super frame pulse 2 is not used in the shown example.
In FIG. 13, when the frame pulse 21 is input to the modules 10-1 to 10-4 at a time slot TS1, the module 10-1 at first makes determination for the connection grant information of the input port 1 for the time slot TS1 of the next frame. Since this is the first determination, the reserved output port information of respective output ports are (0, 0, 0, 0) from the output port 1 to the output port 4 in sequential order. It is assumed that the connection request of the input port 1 is (0, 1, 0, 1) from the output port 1 to the output port 4 in sequential order. When the module 10-1 selects the output port 2, the module 10-1 stores the output port 2 as the connection grant information at the time slot TS1 for the next frame. Then, the reserved output port information (0, 1, 0, 0) is notified to the module 10-2.
Subsequently, at the time slot TS2, the module 10-2 determines the connection grant information of the input port 2 at the time slot TS1 for the next frame. Then, the module 10-2 receives the reserved output port information (0, 1, 0, 0). It is assumed that the connection request of the input port 2 is (0, 1, 1, 1) since the connection request cannot be assigned to the output port 2 since the output port 2 has already been reserved, the module 10-2 rejects connection request to the output port 2 for selecting the output port granting the connection request among the output ports 3 and 4. Here, it is assumed that the output port 3 is selected for granting the connection request. Then, the module 10-2 stores the output port 3 as the connection grant information at the time slot TS5 to notify the reserved output port information (0, 1, 1, 0) to the module 10-3.
Then, at time slot TS3, the module 10-3 and at time slot TS4, the module 10-4 determine the connection grant information at time slot TS1 for the next frame. At the timing where the time slot TS4 is completed, respective modules have the connection grant information at the time slot TS1 for the next frame, 4×4 connection grant information at the time slot TS1 for the next frame is fixed.
Furthermore, in the foregoing process procedure, at the time slot TS1, the module other than the module 10-1 starts “reservation” for respectively different time slots. For example, the module 10-2 starts reservation for time slot TS4 for the next frame, the module 10-3 starts reservation for time slot TS3 for the next frame and the module 10-4 starts reservation for the time slot TS2.
Respective modules performs process of respective reserved time slots at the relevant time slots, the reserved output information of the relevant reserved time slot is transferred to respective modules of next stages to perform scheduling process so that respective modules 10-1 to 10-4 will not have non-operation period. At a timing where the time slot TS4 is completed, respective modules have the connection grant information from the time slots TS1 to TS4 in the next frame, 4×4 connection grant information from the time slots TS1 to TS4 of the next frame is fixed.
FIG. 14 is an illustration showing the order of reservation (connection grant determination) of respective module. FIG. 14 shows the example of the case of 4×4 scheduler. Horizontal axis represents a time, in which one frame is consisted of four time slots. Vertical axis represent physical number of the modules. Transfer direction of the reserved output port information is #1→#2→#3→#4→#1→#2 . . . in physical number of the modules. Figures in the matrix represent number of the time slot in the next frame to reserve.
As shown in FIG. 14, the module having the physical number #1 is the leading module (time slot TS1) of the frame and starts from reservation of the time slot TS1 of the next frame. Similarly, the module of the physical number #2 starts reservation from the time slot TS4, the module of the physical number #3 starts reservation from the time slot TS3, and the module of the physical number #4 starts reservation from the time slot TS2.
When the foregoing conventional algorithm is employed, the following problems are encountered.
At first, when more than or equal to two and less than total number of ports input uniform traffic, ratio of obtaining of reservation (connection request process) between the ports becomes unfairness. In RRGS, since the scheduler having chance of making reservation at earlier timing on the pipeline has higher preference in reservation, probability of obtaining chance of connection becomes higher. Accordingly, the scheduler having earlier reservation chance is absolutely dominant in making reservation. This characteristics is caused by fixed connection topology of the modules. For this characteristics, unfairness is caused in obtaining chance of connection between adjacent ports.
In this respect, discussion will be given in terms of example of FIGS. 12 and 14. It is assumed that data to the output port 3 is accumulated in the input ports 1 and 2, and no other data is present. In this case, a connection request from the input port 1 to the output port 3 and a connection request from the input port 2 to the output port 3 are transmitted to every time slots. Considering fairness between the ports, two kinds of connection requests are to be process in 1:1 manner.
However, referring to FIG. 14, in the scheduler, the input port 2 may have a chance to obtain reservation for the output port 3 at earlier timing than the input port 1 at reservation in the time slot 4, and in other time slots, the input port 1 may have a chance to obtain reservation for the output port 3 at earlier timing than the input port 2. Accordingly, the process ratio becomes 75% at the input port 1 side and 25% at the input port 2 side. In general, considering the foregoing phenomenon in the adjacent two ports among N ports, obtaining ratio of port on upstream side and downstream side becomes N−1:1. Degree of unfairness is increased according to increasing of number of ports. This problem occur in adjacent two or more and N−1 or less ports. When number of adjacent ports is m, the obtaining ratio of the port between the most upstream side port and other port is N−m+1:1: . . . 1 (number of term is m).
Next, the second problem is occurrence of unfairness between the ports in terms of process delay (a period to connection grant response for the connection request) in the same frame. In the shown example, the starting order of the time slot to be reserved in the frame by respective modules is fixed. Therefore, in certain module, the time slot given the chance of reservation at the first timing is the leading time slot in the frame, and in other module, the time slot given the chance of reservation at the first timing becomes the last time slot in the frame.
As set forth above, in the conventional algorithm, the scheduler having earlier reservation chance at earlier timing on the pipeline has higher probability. Therefore, the scheduler having the earliest reservation chance is absolutely dominant in making reservation. When the transmission timing of the time slot having the first reservation chance in each module 10 is fixed, time differences to reservation for the connection request arriving at the same timing between the modules become unfair to cause unfairness in delay timing resulting in unfairness of the cell transmission.
In this point, an example of the case of FIGS. 12 and 14 set forth above will be discussed. Considering reservation of connection of respective modules 10-1 to 10-4 in the time slot TS1 as the leading time slot of the frame, the module 10-1 performs reservation of the time slot TS1 of the next frame at the leading end of the frame. The module 10-2 performs reservation of the time slot TS4 of the next frame at the leading end of the frame. The module 10-1 may make reservation of the slot at the earliest timing. On the other hand, the module 10-2 makes reservation of the time slot at the latest timing. For the connection request arriving at the same timing, the module 10-1 may make reservation of the time slot at earlier timing than other modules 10-2 to 10-4.