# US 6,731,645 B1 · Methods, switches, systems, and computer program products for fair transmission of data received at multiple inputs in the order received in a queued memory switch

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

- Number: US 6,731,645 B1
- Document ID: US6731645B1
- Status: Granted
- Kind: B1
- Application number: 09/515,829
- Filed: 2000-02-29
- Granted: 2004-05-04
- Earliest claimed: 2000-02-29
- Assignees: International Business Machines Corporation
- Inventors: Joseph Michael Abler
- Web page: https://patentgrep.com/patent/US6731645B1

## CPC

- H04L 12/5601: {Transfer mode dependent, e.g. ATM}
- H04L 49/108: {using shared central buffer}
- H04L 2012/5681: {Buffer or queue management}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A queued memory switch includes separate devices that switch received data to the outputs of the queued memory switch. Data is received by a first device (the master) and a second device (the slave) at a series of reception times. The slave sends information to the master indicating whether data directed to an output port was received by the slave at each of the reception times. The master stores the information from the slave with information indicating whether data directed to the same output port was received by the master at each of the reception times. The information indicates the order in which the master and slave received their respective data. The indication can be used to transmit the data from master and the slave in the order in which the data was received by the master and the slave. Related methods, systems, and computer program products are also disclosed.

## Claims

### Claim 1

A method of switching data from inputs of a queued memory switch to outputs of the queued memory switch, the method comprising the steps of:
receiving first data at a first input of a first device included in the queued memory switch directed to an output of the queued memory switch;
receiving second data at a second input of a second device included in the queued memory switch directed to the output;
determining an order of reception of the first and second data; and
transmitting the first and second data from the output of the queued memory switch in the determined order of reception, wherein the step of determining comprises the step of determining reception of the first and second data at a series of reception times, wherein the step of determining comprises the steps of:
indicating reception of the first data and non-reception of the second data if the first data is received and the second data is not received at the reception time;
indicating non-reception of the first data and reception of the second data if the second data is received and the first data is not received at the reception time;
indicating the reception of the first data and reception of the second data if the first and second data are received at the reception time; transmitting an indication of reception of the second data from the second device to the first device; and storing the indication in the first device.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of transmitting the first and second data from the output of the queued memory switch in the determined order of reception comprises the steps of:
determining that the output of the queued memory switch is available;
transmitting a grant from the first device to the second device at a time with respect to the transmission of the first data based on the order of reception of the first and second data; and
transmitting the second data from the second device on the output of the queued memory device responsive to the grant.

### Claim 3 (depends on 1)

The method of claim 1, wherein the step of determining further comprises the steps of:
storing a first indication of the reception of the first data at each reception time; and
storing a second indication of the reception of the second data at each reception time.

### Claim 4 (depends on 3)

The method of claim 3, wherein the first and second indications are associated.

### Claim 5 (depends on 1)

The method of claim 1, wherein the step of transmitting further comprises the steps of:
determining that the output of the queued memory switch is available;
transmitting a grant from the first device to the second device in response to an indication that the second data was received at a reception time and the first data was not received at the reception time, wherein the grant covers transmission of the second data prior to transmission of the first data; and
transmitting the second data from the second device on the output of the queued memory device responsive to the grant.

### Claim 6 (depends on 1)

The method of claim 1, wherein the first and second data comprise respective first and second frames that include the first and second data, wherein the step of determining further comprises the step of storing a count of cells included in the second frame.

### Claim 7 (depends on 6)

The method of claim 6, wherein step of transmitting comprises the steps of:
determining that the output of the queued memory switch is available;
transmitting a number of grants from the first device to the second device in response to an indication that the second frame was received at the reception time and the first frame was not received at the reception time, wherein the number of the grants corresponds to the count of cells included in the second frame, wherein the grant covers transmission of the second data prior to transmission of the first data; and
transmitting the data included in the second frame from the second device on the output of the queued memory switch responsive to the number of grants.

### Claim 8 (depends on 1)

The method of claim 1, wherein the first and second data comprise respective first and second cells that include data.

### Claim 9 (depends on 1)

The method of claim 1, wherein the first and second data comprise respective first and second frames that include data.

### Claim 10 (depends on 1)

The method of claim 1, wherein at least one of the first and second data is directed to the first and a second output of the queued memory switch.

### Claim 11 (depends on 1)

The method of claim 1, wherein the first and second data have respective associated first and second priorities, wherein the step of transmitting further comprises the step of transmitting the first and second data in the order of reception if the first and second priorities are equal.

### Claim 12

A system for switching data from inputs of a queued memory switch to outputs of the queued memory switch, the system comprising:
means for receiving first data at a first input of a first device included in the queued memory switch directed to an output of the queued memory switch;
means for receiving second data at a second input of a second device included in the queued memory switch directed to the output;
means for determining an order of reception of the first and second data; and
means for transmitting the first and second data from the output of the queued memory switch in the determined order of reception, wherein the means for determining comprises means for determining reception of the first and second data at a series of reception times, wherein the means for determining comprises:
means for indicating reception of the first data and non-reception of the second data if the first data is received and the second data is not received at the reception time;
means for indicating non-reception of the first data and reception of the second data if the second data is received and the first data is not received at the reception time; and
means for indicating the reception of the first data and reception of the second data if the first and second data are received at the reception time; means for transmitting an indication of reception of the second data from the second device to the first device; and means for storing the indication in the first device.

### Claim 13 (depends on 12)

The system of claim 12, wherein the means for transmitting the first and second data from the output of the queued memory switch in the determined order of reception further comprises:
means for determining that the output of the queued memory switch is available;
means for transmitting a grant from the first device to the second device, wherein the grant covers transmission of the second data prior to transmission of the first data; and
means for transmitting the second data from the second device on the output of the queued memory device responsive to the grant.

### Claim 14 (depends on 12)

The system of claim 12, wherein the means for determining further comprises:
a means for storing a first indication of the reception of the first data at each reception time; and
means for storing a second indication of the reception of the second data at each reception time.

### Claim 15 (depends on 14)

The system of claim 14, wherein the first and second indications are associated.

### Claim 16 (depends on 12)

The system of claim 12, wherein the means for transmitting further comprises:
means for determining that the output of the queued memory switch is available;
means for transmitting a grant from the first device to the second device in response to an indication that the second data was received at a reception time and the first data was not received at the reception time, wherein the grant covers transmission of the second data prior to transmission of the first data; and
means for transmitting the second data from the second device on the output of the queued memory device responsive to the grant.

### Claim 17 (depends on 12)

The system of claim 12, wherein the first and second data comprise respective first and second frames that include the first and second data, wherein the means for determining further comprises means for storing a count of cells included in the second frame.

### Claim 18 (depends on 17)

The system of claim 17, wherein means for transmitting further comprises:
means for determining that the output of the queued memory switch is available;
means for transmitting a number of grants from the first device to the second device in response to an indication that the second frame was received at the reception time and the first frame was not received at the reception time, wherein the number of the grants corresponds to the count of cells included in the second frame, wherein the grant covers transmission of the second data prior to transmission of the first data; and
means for transmitting the data included in the second frame from the second device on the output of the queued memory switch responsive to the number of grants.

### Claim 19

A computer program product for switching data from inputs of a queued memory switch to outputs of the queued memory switch, the computer program product comprising:
a computer readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising:
computer-readable program code means for receiving first data at a first input of a first device included in the queued memory switch directed to an output of the queued memory switch;
computer-readable program code means for receiving second data at a second input of a second device included in the queued memory switch directed to the output;
computer-readable program code means for determining an order of reception of the first and second data; and
computer-readable program code means for transmitting the first and second data from the output of the queued memory switch in the determined order of reception, wherein the computer-readable program code means for determining comprises computer-readable program code means for determining reception of the first and second data at a series of reception times, wherein the computer-readable program code means for determining comprises:
computer-readable program code means for indicating reception of the first data and non-reception of the second data if the first data is received and the second data is not received at the reception time;
computer-readable program code means for indicating non-reception of the first data and reception of the second data if the second data is received and the first data is not received at the reception time;
computer-readable program code means for indicating the reception of the first data and reception of the second data if the first and second data are received at the reception time; computer-readable program code means for transmitting an indication of reception of the second data from the second device to the first device; and computer-readable program code means for storing the indication in the first device.

### Claim 20 (depends on 19)

The computer program product of claim 19, wherein the computer-readable program code means for transmitting the first and second data from the output of the queued memory switch in the determined order of reception further comprises:
computer-readable program code means for determining that the output of the queued memory switch is available;
computer-readable program code means for transmitting a grant from the first device to the second device; and
computer-readable program code means for transmitting the second data from the second device on the output of the queued memory device responsive to the grant.

### Claim 21 (depends on 19)

The computer program product of claim 19, wherein the computer-readable program code means for determining further comprises:
computer-readable program code means for storing a first indication of the reception of the first data at each reception time; and
computer-readable program code means for storing a second indication of the reception of the second data at each reception time.

### Claim 22 (depends on 21)

The computer program product of claim 21, wherein the first and second indications are associated.

### Claim 23 (depends on 19)

The computer program product of claim 19, wherein the means for transmitting further comprises:
computer-readable program code means for determining that the output of the queued memory switch is available;
computer-readable program code means for transmitting a grant from the first device to the second device in response to an indication that the second data was received at a reception time and the first data was not received at the reception time; and
computer-readable program code means for transmitting the second data from the second device on the output of the queued memory device responsive to the grant.

### Claim 24 (depends on 19)

The computer program product of claim 19, wherein the first and second data comprise respective first and second frames that include the first and second data, wherein the computer-readable program code means for determining further comprises computer-readable program code means for storing a count of cells included in the second frame.

### Claim 25 (depends on 24)

The computer program product of claim 24, wherein means for transmitting further comprises:
computer-readable program code means for determining that the output of the queued memory switch is available;
computer-readable program code means for transmitting a number of grants from the first device to the second device in response to an indication that the second frame was received at the reception time and the first frame was not received at the reception time, wherein the number of the grants corresponds to the count of cells included in the second frame; and
computer-readable program code means for transmitting the data included in the second frame from the second device on the output of the queued memory switch responsive to the number of grants.
