Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-01-31
2003-10-14
Yao, Kwang Bin (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S428000, C370S414000
Reexamination Certificate
active
06633568
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a two-dimensional round-robin scheduling method. In particular, the present invention relates to a two-dimensional round-robin scheduling method with multiple selection of input and output buffered switch.
BACKGROUND OF THE INVENTION
Generally, the performance of input-buffered switches is not as good as that of output-buffered switches due to HOL (head of line) blocking phenomenon. However, the output-buffered switch is not appropriate for high-speed link since operating speed of switch memory fabric or output buffer should be faster than N times of link operating speed. On the contrary, input-buffered switches are appropriate for high-speed link because speed of switch memory fabric such as crossbar and Batcher-banyan is same as link operating speed.
There is an architecture for mitigating HOL blocking phenomenon and it is the multiple input buffer architecture in which each input port uses a number of buffers for an output port. In this architecture, there are N input ports and each input port is connected with N queues for output ports. Therefore, there are N
2
input queues in total. However, since N×N switches have N input links, only N queues are selected among the N
2
queues and it is called contention problem. There are several methods proposed to solve the contention problem and they are PIM (parallel iterative method), SLIP, 2DRR (two-dimensional round-robin) method, and TRM (time reservation method).
PIM method consists of request step, grant step, and accept step. At request step, N
2
input queues send requests to output ports. At grant step, output port randomly grants a request among received requests and notifies the result to each input port. Since an output port may receive a number of grants from an input port, only one grant is randomly selected and accepted among received grants.
Even though performance of PIM method is improved as request step, grant step, and accept step are repeated, it is fairly difficult to apply PIM method to high-speed applications because random operations are required for grant step and accept step.
SLIP method does not use probability functions. SLIP method was proposed at “Scheduling cells in an input-queued switch”, Electronics letters, Vol. 29, No. 25, December 1993, N. McKeown et al. and also at U.S. Pat. No. 5,500,858, N. McKeown. SLIP method utilizes round-robin scheme instead of random operations at grant step and accept step. That is, round robin pointer is used instead of the random operations. If current round-robin pointer value is i, first input port after ith input port is granted among requests received. The value of round-robin pointer is increased by one only if the grant is accepted by input port. In accept step of input port, round-robin pointer is used as well.
However, SLIP method is problematic in that synchronization problem is caused. That is, a number of output ports may grant an identical input port. In order to remove the synchronization problem, SLIP algorithm has to be repeated. In the worst case, the algorithm has to be repeated N times to converge in case that N×N switch is used. In addition, if a number of input and output ports increases, a number of requests and grants that needs to be searched at grant step and accept step increases as well. That is, if a number of input and output ports increases, it is difficult to apply SLIP method to high-speed applications.
2DRR method is proposed at “Two-dimensional round-robin schedulers for packet switches with multiple input queues”, IEEE/ACM transactions on networking, Vol. 2, No. 5, October 1994, R. O. LaMaire et al. and also at U.S. Pat. No. 5,299,190, R. O. LaMaire et al. In 2DRR method, N
2
requests are represented by N×N matrix. Only N search steps are required to determine a request to be transmitted. The service fairness of 2DRR method is equivalent to the service fairness that SLIP in iterated N times.
In the technical paper stated above, basic 2DRR algorithm searches request matrix in sequence defined by pattern sequence matix and determines a request to be transmitted. Enhanced 2DRR algorithm proposed by the technical paper shows performed improvement for specified traffic patterns. If a number of input and output ports increases, it is difficult to apply 2DRR method to high-speed applications because search steps of the algorithm are also increased.
TRM is proposed at “Input and Output queuing ATM switch architecture with spatial and temporal slot reservation control”, Electronics letters, Vol. 28, No. 1, January 1992, H. Obara et al. TRM utilizes input and output buffered switch that grouped input and output ports are used. Grouping input and output ports reduces number of queues for each input port and therefore number of requests used for contention is also decreased. A grouped input port selects a number of requests to prevent performance deterioration of switch. Overall performance of switch is improved by the statistical multiplexing gain due to the grouping.
In the paper proposing TRM, time information is used in contention control. When input buffer module sends requests to contention control module, contention control module sets transmission time and then notifies the time to input buffer module. Therefore, in case of large-scale switch, it is difficult to perform high-speed operation since the amount of time information is increased. Also, it is difficult to perform high-speed operation since number of input and output links is increased as number of input and output ports is increased.
C. Lund et. al disclosed a method at U.S. Pat. No. 5,517,495. The method is similar with the TRM and time information is used for contention control and service fairness is improved. In the invention, a request for a cell that waits for the longest time is transmitted to contention control module in consideration with priorities of output ports. Contention control module grants the longest waiting one among the received requests and notifies the result to input ports. Each input port is able to receive multiple grants from a number of output ports at the same time. Each input port accepts the longest waiting one among the received grants. Even though the method proposed by the invention U.S. Pat. No. 5,517,495 shows better performance than PIM method and SLIP method, it is difficult to apply the method to high-speed applications since time information should be sent in grant and accept steps and a minimum value is searched in the time information.
SUMMARY OF THE INVENTION
A two-dimensional round-robin scheduling method with multiple selection is provided. The two-dimensional round-robin scheduling method in accordance with an embodiment of the present invention employs input buffer modules, output buffer modules, a space division switching module and a contention control module. The input buffer module has input ports and queues. The output buffer module has output ports and queues. The space division switching module has switching planes. The space division switching module is connected with the input buffer modules through links and connected with the output buffer modules through links. The two-dimensional round-robin scheduling method in accordance with an embodiment of the present invention includes following steps. First step is for detecting whether a request signal is received from the input buffer module and building m×m request matrix r(i,j), i,j=1, . . . , m. Second step is for setting m×m search pattern matrix, d(i,j), i,j=1, . . . , m. The search pattern matrix describes search sequence, S=1, . . . , m. Third step is for initializing elements of m×m allocation matrix a(i,j), i,j=1, . . . , m. The allocation matrix contains information whether transmission request is accepted and which switching plane is used in the transmission. Fourth step is for examining a request matrix in accordance with the search sequence of search pattern matrix and finding r(i,j) that requests transmission. Fifth step is for setting a(i,j) for al
Han Man Soo
Jeong Gab Joong
Lee Bhum Cheol
Lee Jung Hee
Electronics and Telecommunications
Hoang Thai D
Seed IP Law Group PLLC
Yao Kwang Bin
LandOfFree
Two-dimensional round-robin scheduling method with multiple... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Two-dimensional round-robin scheduling method with multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-dimensional round-robin scheduling method with multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3152099