Input queue packet switch architecture and queue service discipline
First Claim
1. A packet switching node for switching packets received via a plurality of input ports to a plurality of output ports, the packet switching node comprising:
- a. a plurality of input queues for queuing packets received at the packet switching node;
b. at least two head-of-line registers per input queue, each head-of-line register referencing a corresponding head-of-line packet queued in the corresponding input queue; and
c. inspection means for inspecting the at least two head-of-line packets referenced by the at least two head-of-line registers in selecting a packet for transmission over a corresponding idle destination output port.
1 Assignment
0 Petitions
Accused Products
Abstract
A packet switching node architecture is described in accordance with which multiple packets queued in input queues are considered in selecting packets to be forwarded via idle output ports. Considering multiple queued packets reduces the probability that an output port remains idle and increases the probability that each input queue is serviced despite forwarding of packets being blocked by contention. Also described are processes for enqueuing packets into, and dequeuing packets from, input queues, each input queue having associated therewith a multitude of head-of-line registers pointing to a corresponding sequence of head-of-line queue entries. Enqueuing ensures that the correct head-of-line registers point, in sequence, to a sequence of head-of-line queue entries. Servicing each input queue removes queue entries from the sequence, and dequeuing ensures the resequencing of the head-of-line pointers. Advantages are derived from a reduced probability of an output port to remain idle, while the probability of servicing input queues is increased, thereby mitigating deleterious effects of contention and increasing the packet throughput.
-
Citations
18 Claims
-
1. A packet switching node for switching packets received via a plurality of input ports to a plurality of output ports, the packet switching node comprising:
-
a. a plurality of input queues for queuing packets received at the packet switching node;
b. at least two head-of-line registers per input queue, each head-of-line register referencing a corresponding head-of-line packet queued in the corresponding input queue; and
c. inspection means for inspecting the at least two head-of-line packets referenced by the at least two head-of-line registers in selecting a packet for transmission over a corresponding idle destination output port. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method of enqueuing packets received at a packet switching node, the method comprising:
-
a. adding a packet to an input queue;
b. inspecting a plurality of head-of-line registers in sequence to find a head-of-line register not referencing a packet; and
c. storing packet reference information in the first found head-of-line register not referencing a packet. - View Dependent Claims (14)
-
-
15. A method of forwarding packets queued in a plurality of input queues via a plurality of output ports of a packet switching node, the method comprising inspecting a plurality of head-of-line packets queued in each input queue in identifying a queued packet for which a corresponding destination output port is idle.
-
16. A method of dequeuing packets queued for processing in an input queue at a packet switching node, the method comprising:
-
a. determining whether a first destination output port via which a first head-of-line packet queued in the input queue is to be forwarded, is idle;
b. if the first destination output port via which the first head-of-line packet queued in the input queue is to be forwarded is idle, assigning the packet to the first destination output port for forwarding therethrough, and removing the packet from the input queue;
c. if the first destination output port via which the first head-of-line packet queued in the input queue is to be forwarded, is busy, determining whether a second destination output port via which a subsequent head-of-line packet queued in the input queue behind the first head-of-line packet is to be forwarded, is idle; and
d. if the second destination output port via which the subsequent head-of-line packet is to be forwarded is idle, assigning the subsequent packet to the second destination output port for forwarding therethrough, and removing the subsequent packet from the input queue. - View Dependent Claims (17, 18)
-
Specification