Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-10-02
2004-05-04
Patel, Ajit (Department: 2669)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S229000, C370S395200, C370S395400
Reexamination Certificate
active
06731636
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a scheduler, and more particularly to a scheduler for a switching apparatus in an ATM network.
2. Description of the Related Art
Generally, when data on N (N is a positive integer equal to or more than 2) input paths should be fairly allocated to M (M is a positive integer equal to or more than 2) output paths, a scheduler uses shuffle patterns.
FIG. 1
shows the overview of the structure of the scheduler proposed in a conventional example. A similar technique is disclosed in Japanese Laid Open Patent Application (JP-A-Heisei 9-326828). The scheduler
100
is used in a crossbar switch of a packet switching apparatus, and has N input interfaces and M output interfaces (both not shown). The scheduler
100
allocates request data
101
to
10
N for allocation request outputted from the first to N-th input interfaces M by M to the first to M-th output interfaces.
The scheduler
100
is composed of first to N-th output rearranging units
111
to
11
N, input rearranging unit
129
, a searching unit
139
, and a shuffle pattern storage unit
151
. The first to N-th output rearranging units
111
to
11
N input N sets of M request data
101
to
10
N outputted from the input interface units, respectively. The input rearranging unit
129
inputs N sets of M rearranged request data
121
to
12
N from the first to N-th output rearranging units
111
to
11
N. The N sets of M rearranged request data
131
to
13
N outputted from the input rearranging unit
129
are supplied to the searching unit
139
. The searching unit
139
outputs N permission signals
141
to
14
N. The shuffle pattern storage unit
151
is provided for the scheduler
100
to store shuffle patterns for rearrangement of the request data. One
152
of the shuffle patterns is outputted from the shuffle pattern storage unit
151
to the first to N-th output rearranging units
111
to
11
N, and is used for the rearrangement of the N sets of M request data
101
to
10
N. Also, the other shuffle pattern
153
is outputted from the shuffle pattern storage unit
151
to the input rearranging unit
129
, and is used for the rearrangement of the rearranged request data.
FIG. 2
shows a specific structure of the first output rearranging unit
111
in the conventional scheduler. The first to N-th output rearranging units
111
to
11
N have the same structure. Therefore, the structure of the first output rearranging unit
111
will be described. The first output rearranging unit
111
is composed of a single rearranging unit
161
which inputs M request data
1011
to
101
M. The Shuffle pattern
152
is supplied to the rearranging unit
161
from the shuffle pattern storage unit
151
shown in FIG.
1
. The rearrangement of the M request data
1011
to
101
M is carried out once in accordance with the shuffle pattern
152
. The M rearranged request data
1211
to
121
M are supplied to the input rearranging unit
129
shown in FIG.
1
.
FIG. 3
shows a specific structure of the input rearranging unit of the scheduler
100
shown in FIG.
1
. The input rearranging unit
129
is composed of a rearranging unit
176
, which inputs N sets of M rearranged request data
121
to
12
N. The shuffle pattern
153
is supplied from the shuffle pattern storage unit
151
shown in
FIG. 1
to the rearranging unit
176
. The rearrangement of the rearranged request data
121
to
12
N is carried out once in accordance with the shuffle pattern
153
. The rearranged request data
131
to
13
N are supplied to the searching unit
139
shown in FIG.
1
.
By the way, the rearrangement of the request data is carried out once in the rearranging units
161
and
176
shown in FIGS.
2
and
FIG. 3
, respectively. In such a conventional example, when the number of input paths is M which is different from the number of output paths N, the shuffle patterns need to be prepared individually. This will be described below.
FIG. 4
shows an example of the shuffle pattern used to rearrange twelve data. Only a part of such a shuffle pattern cannot be used for eight data which are less than twelve data. This will be further described. In the shuffle pattern for the twelve data shown in
FIG. 4
, values from “1” to “12” are randomly arranged in order of the access. At this time, it is supposed that eight shuffle data are fixedly taken out from the shuffle pattern shown in FIG.
4
. In this case, it is necessary to contain all the values from “1” to “8” in eight shuffle data. However, it is impossible for the taken data to contain all the values from “1” to “8”. Therefore, the shuffle patterns need to be independently prepared depending on the size of data.
Now, the case that the value M is “8” and the value N is “12” will be described as an example. When the scheduling operation of 8×12 is carried out, the number of shuffle patterns used to rearrange eight data is “40,320” as factorial of eight for all the patterns of arrangement, because the amount of information is 24 bits. Also, in case of twelve data, one set of shuffle patterns is 48 bits, and the number of shuffle patterns is “479,001,600” as factorial of twelve. Therefore, the memory with the memory capacity of 40,320 words×24 bits and the memory with the memory capacity of 479,001,600 word×48 bits need be prepared. Also, when access to the memories is carried out using a bus of eight bits, the memory access is carried out three times to read the shuffle pattern for eight data and six times to read the shuffle pattern for twelve data.
It could be considered that these two memories are accessed in parallel to reduce the access time. However, when such parallel access is carried out, it is necessary to prepare two sets of interface signals such as address signals and data control signal to access these two memories. Therefore, when the scheduler is realized as an integrated circuit such as LSI and FPGA, there would be a case that the number of terminals lacks.
In conjunction with the above description, the above Japanese Laid Open Patent Application (JP-A-Heisei 9-326828) corresponding to U.S. patent application Ser. No. 08/656,546 discloses a data packet router. In this reference, a data array having the number of data elements corresponding to the number of switch elements is provided in correspondence with a switch element matrix. First and second pseudo random shuffle patterns are generated to each of a series of intervals of connections of data sources and data destinations. The data sources are allocated to the data elements in accordance with the first current pseudo random shuffle pattern. The data destinations are allocated to the data elements in accordance with the second current pseudo random shuffle pattern. An increment test is carried out for the sources and the destinations over the data array to search a matching of a not-allocated source to the destination. The matching is allocated to the switch element corresponding to the data element. In this case, the first shuffle pattern is biased for the data source having the first priority level higher than a second priority level to be positioned near the start point of the increment test. After the whole data array is tested, the switch element is operated for the subsequent interval in accordance with the allocation for the current interval.
SUMMARY OF THE INVENTION
Therefore, an object of the present invention is to provide a scheduler in which the memory capacity of a memory for storing shuffle patterns can be reduced.
Another object of the present invention is to provide a scheduler in which a shuffling operation can be carried out when data with the number of input paths M is different from the number of output paths N.
Still another object of the present invention is to provide a scheduler in which a shuffling operation can be carried out for input paths or output paths with different priority levels.
In order to achieve an aspect of the present invention, in a scheduler having m input interfaces and n output interfaces in an ATM sw
NEC Corporation
Patel Ajit
Young & Thompson
LandOfFree
Scheduler using small sized shuffle pattern in ATM network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduler using small sized shuffle pattern in ATM network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduler using small sized shuffle pattern in ATM network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207570