US6920146B1 — Switching device with multistage queuing scheme

Claim 1

Independent Claim 141 words

In a switching device, apparatus for communicating data packets from sending ports to destination ports, comprising: a first stage queue comprising a plurality of first queues for storing packet-related data from a sending port, wherein the packet-related data is stored in the plurality of first queues based on a characteristic of the data packets; a second stage queue associated with each of a set of destination ports, the second stage queue comprising a plurality of second queues, each of the plurality of second queues for storing the packet-related data from each of the plurality of first queues of the first stage queue based on a characteristic of the data packets; and a switch fabric coupled to the second stage queue, the switch fabric using the packet-related data in the second stage queue for transmitting the data packets to a destination port.

Claim 2

Dependent Claim 141 words

In a switching device, apparatus for communicating data packets from sending ports to destination ports, comprising: a first stage queue comprising a plurality of first queues for storing packet-related data from a sending port, wherein the packet-related data is stored in the plurality of first queues based on a characteristic of the data packets; a second stage queue associated with each of a set of destination ports, the second stage queue comprising a plurality of second queues, each of the plurality of second queues for storing the packet-related data from each of the plurality of first queues of the first stage queue based on a characteristic of the data packets; and a switch fabric coupled to the second stage queue, the switch fabric using the packet-related data in the second stage queue for transmitting the data packets to a destination port.

Claim 3

Dependent Claim 27 words

The apparatus of claim 1 including means for determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue.

Claim 4

Dependent Claim 22 words

The apparatus of claim 1 including address resolution logic sending the packet-related data from the sending port to the first stage queue.

Claim 5

Dependent Claim 31 words

The apparatus of claim 1 wherein each second stage queue includes multiple second queues, the packet-related data stored in a specific second queue based on the characteristic of the data packets.

Claim 6

Dependent Claim 25 words

The apparatus of claim 1 wherein the switch fabric is a shared memory switch fabric for communicating data packets from sending ports to destination ports.

Claim 7

Dependent Claim 23 words

The apparatus of claim 1 wherein the switch fabric is a crossbar matrix for communicating data packets from sending ports to destination ports.

Claim 8

Dependent Claim 105 words

In a switching device, a method for communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue a pointer to memory storing a data packet and a list of destination ports; identifying a destination port stored in the first stage queue; retrieving the pointer to memory stored in the first stage queue; storing in a second stage queue associated with the identified destination port the retrieved pointer to memory; and using the pointer to memory in the second stage queue to complete the communication of the data packet from the sending port to the identified destination port.

Claim 9

Dependent Claim 105 words

In a switching device, a method for communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue a pointer to memory storing a data packet and a list of destination ports; identifying a destination port stored in the first stage queue; retrieving the pointer to memory stored in the first stage queue; storing in a second stage queue associated with the identified destination port the retrieved pointer to memory; and using the pointer to memory in the second stage queue to complete the communication of the data packet from the sending port to the identified destination port.

Claim 10

Dependent Claim 45 words

The method of claim 7 , wherein the first stage queue includes multiple first queues, and the step of storing the pointer to memory in the first stage queue comprises storing the pointer in a specific first queue based on a characteristic of the packet.

Claim 11

Dependent Claim 47 words

The method of claim 7 , wherein the second stage queue includes multiple second queues, and the step of storing the retrieved pointer to memory in the second stage queue comprises storing the retrieved pointer in a specific second queue based on a characteristic of the packet.

Claim 12

Dependent Claim 140 words

In a switching device, a method of communicating data packets from one or more sending ports to destination ports, the method comprising: storing, in a first stage queue comprising a plurality of first queues, packet-related data associated with the data packets from the one or more sending ports, wherein the packet-related data are stored in one of the plurality of first queues based on a characteristic of the data packets; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue; and transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 13

Dependent Claim 140 words

In a switching device, a method of communicating data packets from one or more sending ports to destination ports, the method comprising: storing, in a first stage queue comprising a plurality of first queues, packet-related data associated with the data packets from the one or more sending ports, wherein the packet-related data are stored in one of the plurality of first queues based on a characteristic of the data packets; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue; and transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 14

Dependent Claim 42 words

The method of claim 10 wherein the switch fabric is a shared-memory switch fabric, and the transmitting comprises using the packet-related data to obtain a copy of the data packets from the shared-memory switch fabric to complete communication of the data packet.

Claim 15

Dependent Claim 49 words

The method of claim 10 wherein the switch fabric is a crossbar matrix, and the transmitting comprises using the packet-related data to form connections in the matrix so as to communicate simultaneously a copy of the data packets from the sending port to each of the determined destination ports.

Claim 16

Dependent Claim 106 words

In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue packet-related data from a sending port; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue based on network protocol type; and transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 17

Dependent Claim 106 words

In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue packet-related data from a sending port; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue based on network protocol type; and transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 18

Dependent Claim 113 words

In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue packet-related data from a sending port; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue based on whether the data packets are unicast packets or multicast packets; and transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 19

Dependent Claim 113 words

In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue packet-related data from a sending port; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue based on whether the data packets are unicast packets or multicast packets; and transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 20

Dependent Claim 110 words

In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue the data packets from a sending port; determining from the data packets which destination ports are to receive the data packets in the first stage queue; storing in a second stage queue associated with each determined destination port the data packets from the first stage queue based on a characteristic of the data packets; and transmitting the data packets in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 21

Dependent Claim 110 words

In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue the data packets from a sending port; determining from the data packets which destination ports are to receive the data packets in the first stage queue; storing in a second stage queue associated with each determined destination port the data packets from the first stage queue based on a characteristic of the data packets; and transmitting the data packets in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 22

Dependent Claim 95 words

A multistage queuing apparatus for transmitting data packets from one or more sending ports to a plurality of destination ports, comprising: a first queue structure, operatively coupled to the one or more sending ports, comprising a plurality of first queues for storing packet-related data associated with the data packets based on a first characteristic of the data packets; and a second queue structure, operatively coupled to the first queue structure and plurality of destination ports, comprising a plurality of second queues for storing the packet-related data based on the first characteristic and a second characteristic.

Claim 23

Dependent Claim 95 words

A multistage queuing apparatus for transmitting data packets from one or more sending ports to a plurality of destination ports, comprising: a first queue structure, operatively coupled to the one or more sending ports, comprising a plurality of first queues for storing packet-related data associated with the data packets based on a first characteristic of the data packets; and a second queue structure, operatively coupled to the first queue structure and plurality of destination ports, comprising a plurality of second queues for storing the packet-related data based on the first characteristic and a second characteristic.

Claim 24

Dependent Claim 14 words

The multistage queuing apparatus of claim 16 , wherein the first characteristic is priority.

Claim 25

Dependent Claim 16 words

The multistage queuing apparatus of claim 16 , wherein the first characteristic is network protocol type.

Claim 26

Dependent Claim 16 words

The multistage queuing apparatus of claim 16 , wherein the first characteristic is type of service.

Claim 27

Dependent Claim 24 words

The multistage queuing apparatus of claim 16 , wherein the second characteristic is a destination port number associated with the plurality of destination ports.

Claim 28

Dependent Claim 120 words

A multistage queuing apparatus for transmitting data packets from one or more sending ports to a plurality of destination ports, comprising: a first queue structure, operatively coupled to the one or more sending ports, comprising a first array of two or more first queues for storing the packet-related data associated with the data packets in accordance with a first characteristic of the data packets; and a second queue structure comprising a plurality of second arrays, each of the second arrays comprising two or more second queues operatively coupled to one of the plurality of destination ports, wherein each of the second arrays is adapted to store the packet-related data from the first queue structure in accordance with the first characteristic.

Claim 29

Dependent Claim 120 words

A multistage queuing apparatus for transmitting data packets from one or more sending ports to a plurality of destination ports, comprising: a first queue structure, operatively coupled to the one or more sending ports, comprising a first array of two or more first queues for storing the packet-related data associated with the data packets in accordance with a first characteristic of the data packets; and a second queue structure comprising a plurality of second arrays, each of the second arrays comprising two or more second queues operatively coupled to one of the plurality of destination ports, wherein each of the second arrays is adapted to store the packet-related data from the first queue structure in accordance with the first characteristic.

Claim 30

Dependent Claim 29 words

The multistage queuing apparatus of claim 21 , wherein the dimension of the first array is the same as the dimension of each of the plurality of second arrays.

Claim 31

Dependent Claim 41 words

The multistage queuing apparatus of claim 21 , wherein the apparatus further includes port determination logic interposed between the first queue structure and second queue structure to determine to which of the plurality of destination ports to transmit the packet-related data.

Claim 32

Dependent Claim 109 words

In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue packet-related data from a sending port based on a characteristic of the data packets; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue; and transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 33

Dependent Claim 109 words

In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising: storing in a first stage queue packet-related data from a sending port based on a characteristic of the data packets; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue; and transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

Claim 34

Dependent Claim 14 words

The method of claim 24 wherein the packet-related data comprises a pointer to memory.

Claim 35

Dependent Claim 13 words

The method of claim 24 wherein the packet-related data is a data packet.

Claim 36

Dependent Claim 52 words

The method of claim 24 wherein the first stage queue comprises a plurality of first queues, and the step of storing the packet-related data in the first stage queue comprises storing the packet-related data in one of the plurality of first queues based on the characteristic of each of the data packets.

Claim 37

Dependent Claim 11 words

The method of claim 24 wherein the packet characteristic is priority.

Claim 38

Dependent Claim 13 words

The method of claim 24 wherein the packet characteristic is network protocol type.

Claim 39

Dependent Claim 13 words

The method of claim 24 wherein the packet characteristic is type of service.

Claim 40

Dependent Claim 19 words

The method of claim 24 wherein the packet characteristic is packet type comprising a unicast type and multicast type.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2008-07-18	2009-01-17	2009-07-19	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2012-07-18	2013-01-17	2013-07-19	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2016-07-18	2017-01-17	2017-07-19	$7700.00	Window Closed / Lapsed

Switching device with multistage queuing scheme

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag