# US 6,731,636 B1 · Scheduler using small sized shuffle pattern in ATM network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,731,636 B1
- Document ID: US6731636B1
- Status: Granted
- Kind: B1
- Application number: 09/676,815
- Filed: 2000-10-02
- Granted: 2004-05-04
- Earliest claimed: 1999-10-04
- Assignees: NEC Corporation
- Inventors: Ryuichi Ikematsu
- Web page: https://patentgrep.com/patent/US6731636B1

## CPC

- H04L 47/624: {Altering the ordering of packets in an individual queue}
- H04L 12/5601: {Transfer mode dependent, e.g. ATM}
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 47/50: Queue scheduling
- H04L 2012/5651: {Priority, marking, classes}
- H04L 2012/5679: {Arbitration or scheduling}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In a scheduler having m input interfaces and n output interfaces in an ATM switching apparatus, each of m and n is an integer equal to or more than 2. The scheduler is includes a storage unit, first and second rearranging unit, a control unit and a searching unit. The storage unit stores a plurality of shuffle patterns including first to fourth shuffle patterns. The first rearranging unit carries out a first shuffling operation in units of k data (k is an integer equal to or more than 2 and less than or equal to s which is one of n and m, the other being t) and a second shuffling operation in units of u groups (u is an integer equal to or more than 2 and corresponding to s/k) to (m×n) data supplied from the m input interfaces based on the first and second shuffle patterns to produce first rearranged data. The (m×n) data are grouped into (t×u) groups. The second rearranging unit carries out a third shuffling operation in units of p data (p is an integer equal to or more than 2 and less than or equal to (m×n)) and a fourth shuffling operation in units of groups to the first rearranged data based on the third and fourth shuffle patterns to produce second rearranged data. The first rearranged data are grouped into v groups (v is an integer equal to or more than 2 and corresponding to (m×n)/p).

## Claims

### Claim 1

A scheduler having m input interfaces and n output interfaces in an ATM switching apparatus, each of m and n being an integer equal to or more than 2, comprising:
a storage unit which stores a plurality of shuffle patterns including first to fourth shuffle patterns;
a first rearranging section which carries out a first shuffling operation in units of k data (k is an integer equal to or more than 2 and less than or equal to s which is one of n and m, the other being t) and a second shuffling operation in units of u groups (u is an integer equal to or more than 2 and corresponding to s/k) to (m×n) data supplied from said m input interfaces based on said first and second shuffle patterns to produce first rearranged data, said (m×n) data being grouped into (t×u) groups;
a second rearranging section which carries out a third shuffling operation in units of p data (p is an integer equal to or more than 2 and less than or equal to (m×n)) and a fourth shuffling operation in units of groups to said first rearranged data based on said third and fourth shuffle patterns to produce second rearranged data, said first rearranged data being grouped into v groups (v is an integer equal to or more than 2 and corresponding to (m×n)/p);
a control unit which reads out said first to fourth shuffle patterns to supply to said first and second rearranging sections;
a searching unit which outputs a permission signal for a relation between one input interface and one output interface based on said second rearranged data and a predetermined algorithm.

### Claim 2 (depends on 1)

The scheduler according to claim 1, wherein said storage unit includes a plurality of memories, which stores said plurality of shuffle patterns in units of sizes of said plurality of shuffle patterns.

### Claim 3 (depends on 1)

The scheduler according to claim 1, wherein said first rearranging section includes:
(t×u) rearranging sections, each of which carries out said first shuffling operation to corresponding ones of said (m×n) data based on said first shuffle pattern to produce third rearranged data; and
t third rearranging sections, each of which is provided for u of said (t×u) rearranging sections to carry out said second shuffling operation to corresponding u groups of said third rearranged data based on said second shuffle pattern to produce (said first rearranged data)/t.

### Claim 4 (depends on 1)

The scheduler according to claim 1, wherein said first rearranging section includes:
t third rearranging sections, each of which is provided to carry out said second shuffling operation to corresponding u groups of said (t×u) groups based on said second shuffle pattern to produce fourth rearranged data; and
(t×u) rearranging sections, each of which carries out said first shuffling operation to corresponding one of (said fourth rearranged data)/u based on said first shuffle pattern to produce (said first rearranged data)/(t×u).

### Claim 5 (depends on 1)

The scheduler according to claim 1, wherein said second rearranging section includes:
v fifth rearranging sections, each of which carries out said third shuffling operation to corresponding p data of said first rearranged data based on said third shuffle pattern to produce fifth rearranged data; and
a sixth rearranging section which carries out said fourth shuffling operation to said v fifth rearranged data based on said fourth shuffle pattern to produce said second rearranged data.

### Claim 6 (depends on 1)

The scheduler according to claim 1, wherein said first rearranging section includes:
a sixth rearranging section which carries out said fourth shuffling operation to said first rearranged data based on said fourth shuffle pattern to produce said sixth rearranged data; and
v fifth rearranging sections, each of which carries out said third shuffling operation to corresponding data of (said sixth rearranged data)/v based on said third shuffle pattern to produce (said second rearranged data)/v.

### Claim 7 (depends on 1)

The scheduler according to claim 1, wherein said control unit allocates ones selected in a same probability from among said plurality of shuffle patterns stored in said storage unit based on the number of data to be rearranged as said first to fourth shuffle patterns.

### Claim 8 (depends on 1)

The scheduler according to claim 1, wherein each of said plurality of shuffle patterns has a priority level, and
said control allocates ones selected in a specified probability from among said plurality of shuffle patterns based on the number of data to be rearranged as said first to fourth shuffle patterns.

### Claim 9 (depends on 1)

The scheduler according to claim 1, wherein said k is a common divisor of said m and n.

### Claim 10 (depends on 1)

A scheduler according to claim 1, wherein when s is not a common multiple of k, dummy data are added to at least one of said u groups such that the number of data in said one group is equal to k.

### Claim 11 (depends on 1)

The scheduler according to claim 1, wherein when said k is not a common divisor of said m and n, dummy data are added to at least one of said u groups such that said k is a common divisor of said m and n.

### Claim 12

A method of shuffling (m×n) in a scheduler having m input interfaces and n output interfaces, each of m and n being an integer equal to or more than 2, comprising:
(a) carrying out a first shuffling operation in units of k data (k is an integer equal to or more than 2 and less than or equal to s which is one of n and m, the other being t) and a second shuffling operation in units of u groups (u is an integer equal to or more than 2 and corresponding to s/k) to (m×n) data supplied from said m input interfaces based on said first and second shuffle patterns to produce first rearranged data, said (m×n) data being grouped into (t×u) groups;
(b) carrying out a third shuffling operation in units of p data (p is an integer equal to or more than 2 and less than or equal to (m×n)) and a fourth shuffling operation in units of groups to said first rearranged data based on said third and fourth shuffle patterns to produce second rearranged data, said first rearranged data being grouped into v groups (v is an integer equal to or more than 2 and corresponding to (m×n)/p); and
outputting a permission signal for a relation between one input interface and one output interface based on said second rearranged data and a predetermined algorithm.

### Claim 13 (depends on 12)

The method according to claim 12, wherein a plurality of shuffle patterns are stored in units of sizes of said plurality of shuffle patterns.

### Claim 14 (depends on 12)

The method according to claim 12, wherein said (a) carrying out includes:
(c) carrying out said first shuffling operation to said (m×n) data in units of k data based on said first shuffle pattern to produce a third rearranged data; and
(d) carrying out said second shuffling operation to said third rearranged data in units of u groups based on said second shuffle pattern to produce said first rearranged data.

### Claim 15 (depends on 12)

The method according to claim 12, wherein said (a) carrying out includes:
(e) carrying out said second shuffling operation to said (m×n) data in units of u groups based on said second shuffle pattern to produce said fourth rearranged data; and
(f) carrying out said first shuffling operation to said fourth rearranged data in units of k data based on said first shuffle pattern to produce said first rearranged data.

### Claim 16 (depends on 12)

The method according to claim 12, wherein said (b) carrying out includes:
(g) carrying out said third shuffling operation to said first rearranged data in units of p data based on said third shuffle pattern to produce fifth rearranged data; and
(h) carrying out said fourth shuffling operation to said fifth rearranged data based on said fourth shuffle pattern to produce said second rearranged data.

### Claim 17 (depends on 12)

The method according to claim 12, wherein said (b) carrying out includes:
(i) carrying out said fourth shuffling operation to said first rearranged data in units of groups based on said fourth shuffle pattern to produce sixth rearranged data; and
(j) carrying out said third shuffling operation to said sixth rearranged data in units of p data based on said third shuffle pattern to produce said second rearranged data.

### Claim 18 (depends on 12)

The method according to claim 12, wherein said first to fourth shuffle patterns are selected in a same probability from among said plurality of shuffle patterns based on the number of data to be rearranged.

### Claim 19 (depends on 12)

The method according to claim 12, wherein said first to fourth shuffle patterns are selected in a specified probability from among said plurality of shuffle patterns based on the number of data to be rearranged.

### Claim 20 (depends on 12)

The method according to claim 12, wherein said k is a common divisor of said m and n.

### Claim 21 (depends on 12)

The method according to claim 12, wherein when s is not a common multiple of k, dummy data are added to one of said u groups such that the number of data in said one group is equal to k.

### Claim 22 (depends on 12)

The method according to claim 12, wherein when said k is not a common divisor of said m and n, dummy data are added to at least one of said u groups such that said k is a common divisor of said m and n.
