Input queue packet switch architecture and queue service discipline

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.

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.    
   
   
       2 . The packet switching node claimed in  claim 1 , further comprising a queue inspection register tracking the number of times the input queue was inspected during a service cycle, the value of the queue inspection register being used to access the at least two head-of-line registers in sequence.  
   
   
       3 . The packet switching node claimed in  claim 2 , further comprising a queue service register specifying whether a packet queued in the input queue was matched with a corresponding destination output port during each service cycle, further inspection of the input queue for packets to match with idle ports being suppressed for the duration of the service cycle after the input queue has been serviced.  
   
   
       4 . The packet switching node claimed in  claim 1 , each input queue being one of: an input queue associated with a single input port; an input queue associated with a subgroup of the plurality of input ports; and one of a group of input queues, the group of input queues being associated with at least one input port.  
   
   
       5 . The packet switching node claimed in  claim 4 , wherein the packet switching node having the group of input queues are associated with the at least one input port, the packet switching node further comprising a packet classifier for classifying received packets in one of the group of input queues.  
   
   
       6 . The packet switching node claimed in  claim 5 , wherein each input queue in the group of input queues associated with the at least one input port corresponds to one of: a Class-of-Service level queue, a Type-of-Service level queue, a Quality-of-Service level queue, and a Virtual Local Area Network designation queue; the packet classifier classifying packets received at the packet switching node in accordance with one of: a Class-of-Service, a Type-of-Service, a Quality-of-Service, and a Virtual Local Area Network designation.  
   
   
       7 . The packet switching node claimed in  claim 1 , further comprising packet switching means and input queue service sequencing means, the inspection means being responsive to the packet switching means.  
   
   
       8 . The packet switching node claimed in  claim 1 , further comprising packet descriptors for tracking corresponding packets received at the packet switching node.  
   
   
       9 . The packet switching node claimed in  claim 8 , further comprising: 
 a. a memory storage for storing received packets; and    b. each packet descriptor further comprising a start storage memory address register for specifying the start memory storage address at which the corresponding packet is stored in the memory storage while pending processing.    
   
   
       10 . The packet switching node claimed in  claim 9 , further comprising: 
 a. a search engine for determining at least one output port for forwarding at least one received packet therethrough; and    b. each packet descriptor further comprising a destination output port register for specifying at least one output port for forwarding the corresponding packet therethrough.    
   
   
       11 . The packet switching node claimed in  claim 10 , wherein the destination output port register has a bit representation, wherein each bit corresponds to a destination output port selected from: a physical output port, a logical output port associated with a subgroup of the plurality of output ports, and a logical loopback port.  
   
   
       12 . The packet switching node claimed in  claim 10 , wherein each input queue is defined by a sequenced list of descriptors, each descriptor further comprising a next packet descriptor register specifying a packet descriptor reference, each head-of-line register specifying a reference to a corresponding head-of-line packet descriptor.  
   
   
       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.    
   
   
       14 . The method claimed in  claim 13 , wherein a packet descriptor is employed in referencing a corresponding packet pending processing at the packet switching node, the method comprising: 
 a. adding to the input queue a packet descriptor corresponding to each received packet;    b. inspecting a plurality of head-of-line registers in sequence to find a head-of-line register not referencing a valid packet descriptor; and    c. setting the value of the first found head-of-line register not referencing a valid packet descriptor to reference the packet descriptor added to the input queue.    
   
   
       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.    
   
   
       17 . The method claimed in  claim 16 , wherein each determination as to whether a destination output port is idle is performed responsive to a service request, the method further comprising: 
 a. tracking the number of service requests received during an input queue service cycle; and    b. selecting a head-of-line packet for matching with a corresponding destination output port based on the cumulative number of queue service requests received during each service cycle.    
   
   
       18 . The method claimed in  claim 16 , wherein head-of-line packets are accessed via a plurality of head-of-line registers referencing corresponding head-of-line packets queued in the input queue, the method further comprising updating references to head-of-line packets specified in head-of-line registers behind and including the head-of-line register corresponding to the head-of-line packet which was matched with a corresponding idle destination output port.