Multicast switching in a credit based unicast and multicast switching architecture

A system and method of switching packets and/or cells, which includes a switching apparatus having a plurality of input units that receive at least one packet to be transferred by the switching apparatus. A plurality of output units transfer the packet out of the switching apparatus. A switch unit transfers the packet from one of the input units to one of the output units. Each input unit includes at least one input queue that temporarily holds the packet to be transferred by the switching apparatus. Each input unit also includes a respective unicast credit count unit that allows the packet to be transferred out from the queue when a current unicast credit value determined by the unicast credit count unit is at least predetermined value. Each output unit includes at least one output queue that receives the packet as switched by the switch unit, and which is to be transferred out of the switching apparatus. Each output unit also includes a output port scheduler unit that generates credit tokens and that outputs credit messages based on the credit tokens generated. Multicast credit count units are provided for each QoS priority that a multicast packet can be set to, in which they maintain a current multicast credit value for the QoS priorities.

BACKGROUND OF THE INVENTION

A. Field of the Invention

The invention relates generally to scheduling of unicast and multicast packets and cells, and, more particularly, to a packet and cell switching apparatus where the output units schedule unicast and multicast traffic via a credit mechanism, and where the switch unit schedules multicast traffic at a fabric scheduling stage, and where unicast and multicast traffic is merged on a per output port basis via a credit mechanism.

B. Description of the Related Art

A generic packet switching apparatus can be partitioned into the following three units: the input unit, the switch unit, and the output unit. As a packet traverses the switching apparatus from an input port to an output port, it passes these units in the listed order of sequence.

The majority of the switching apparatus' buffer capacity is typically implemented at the input unit. The input buffering typically includes Virtual Output Queue (VoQ) structures. In addition to the buffering performed by the input unit, the switch unit may also implement buffering, and the output unit may also implement buffering, depending on the implementation.

Any scheduling process can be viewed as two stages of scheduling. One stage, called “traffic scheduling”, determines the order and sequence in which the incoming packets are transferred from the input to the output port of the switching apparatus. The second stage, called “fabric scheduling”, is the level of scheduling which performs the transfer of the packets from the input to output units. In conventional cell and/or packet switching systems, both the traffic scheduling and fabric scheduling are performed by the switch unit. There is a desire to have some of those scheduling processes decentralized from the switch unit, in order to lessen the burden on that component and to distribute it to other components of a switching apparatus that have resources available to perform those processes.

SUMMARY OF THE INVENTION

At least one aspect of the present invention performs multicast switching in a credit based unicast and multicast switching architecture.

According to one aspect of the invention, there is provided a switching apparatus, which includes a plurality of input units each configured to receive at least one packet to be transferred by the switching apparatus. The switching apparatus also includes a plurality of output units each configured to transfer the at least one packet out of the switching apparatus. The switching apparatus further includes a switch unit configured to transfer the at least one packet from a respective one of the input units to a respective one of the output units. Each of the input units includes at least one input queue configured to temporarily hold the at least one packet to be transferred by the switching apparatus. Each of the input units also includes at least one unicast credit count unit configured to allow the at least one packet to be transferred out from the at least one queue when a current unicast credit value determined by the unicast credit count unit is at least predetermined value, the at least one unicast credit count unit configured to receive a unicast credit value provided thereto, wherein there is one unicast credit count unit per input queue. Each of the output units includes at least one output queue configured to receive the at least one packet as switched by the switch unit, and which are to be transferred out of the switching apparatus. Each of the output units also includes an output port scheduler unit configured to generate credit tokens and to output the credit message based on the credit tokens generated. A plurality of multicast credit count units is provided for each of a plurality of QoS priorities that a multicast packet is capable of being set to, the plurality of multicast credit count units respectively configured to maintain a current multicast credit value for the plurality of QoS priorities, the plurality of multicast credit count units configured to allow the at least one packet to be transferred out from the respective one of the plurality of output queues when a current multicast credit value determined by the respective one of the plurality of multicast credit count units is at least a second predetermined value.

According to another aspect of the invention, there is provided a method for a switching apparatus that includes a plurality of input units each configured to receive packets to be transferred by the switching apparatus, a plurality of output units each configured to transfer the packets out of the switching apparatus, and a switch unit configured to transfer the packets from respective ones of the input units to respective ones of the output units. The method includes receiving, by an input queue of one of the input units, at least one packet to be transferred by the switching apparatus. The method also includes determining a current unicast credit value for the input queue. Based on the determined current unicast credit value, the method includes determining if the input queue is in a Hungry state. If the Hungry state has changed from a previous determination of the Hungry state, the method includes outputting a unicast queue status message from the one of the input units. The method further includes determining, by one of the output units, the queue status for the input queue of the one of the input units. Based on the unicast queue status message, the method further includes determining if the at least one packet currently stored in the input queue of the one of the input units is eligible for transfer from the input unit to the switch unit. If the at least one packet currently stored in the input queue of the one of the input units is determined to be eligible for transfer, the method includes outputting a credit message to the input queue of the one of the input units.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

Compared to conventional switching apparatus where unicast and multicast traffic are scheduled by a switch unit, the present invention provides a method and system where traffic scheduling of unicast traffic is de-centralized away from the switch unit by being partially distributed to the output units, and where the output unit merges and co-schedules unicast and multicast traffic on a per output port basis via a credit distribution mechanism.

Several conventional examples of switch unit implementations exist, whereby the switch unit implementations are outside the scope of the present invention. The present invention addresses a scalability problem which is in general associated with switch unit implementations, whereby the switch unit implementation becomes increasingly complex as the number of ports and QoS priorities provided by the switch unit increases. As a result, the switch unit becomes an implementation bottleneck for scaling the capacity of switching apparatus implementations. The present invention allows for scaling the number of output ports and QoS priorities provided per output unit without increasing the required complexity of the switch unit implementation.

In the present invention, the credit scheduling referred to below is scheduling that occurs at the “traffic scheduling” stage, whereby the fabric scheduling is beyond the scope of this invention, and may be performed by conventional methods. That is, once a unicast packet or cell has been qualified for transfer from an input to an output unit by way of the credit mechanism or credit scheme as discussed in detail below, that same packet or cell then undergoes fabric scheduling, whereby the fabric scheduling is typically performed by a switch unit. The traffic scheduling stage determines when a unicast packet or cell can be forwarded to the fabric scheduling (whereby the fabric scheduling is performed by DataTx units referred to in detail below). Thus, unless identified otherwise, the credit-based scheduling described below is performed at the traffic scheduling stage.

FIG. 1shows an N×M switching apparatus (N and M are integer values) incorporating a packet scheduling method and apparatus according to a first embodiment of the present invention. Each of the N input ports100receives packets, and buffers the received packets in their respective input units110. Each input unit110transmits packets to the switch unit140via the ingress data links120. The switch unit140transmits the packets to their destination output unit via the egress data links150. The packets exit the switching apparatus via the N output ports180associated with the output units170.

The input unit110performs a bi-directional exchange of internally generated control messages with the output units170. This message exchange is performed via the input unit's control link130and the output unit's control link160, across the switch unit140. In one possible implementation of the first embodiment, input unit L and output unit L (L being a positive integer greater than one) are integrated into a single physical device. This way, the L′th input unit110and the L′th output unit170can share the same bi-directional control link connecting to the switch unit140, which reduces the number of control links in half.

The switch unit140transmits unicast packets from the input unit110to the unicast packet's destination output unit170, and the switch unit140replicates and transmits a copy of a multicast packet from the input units110to each of the multicast packets destination output units170.

In the first embodiment, the switch unit140has the capability of prioritizing between packets accordingly to unicast and multicast QoS priorities. Depending on the implementation of the switch unit140, each individual multicast packet is transmitted one or multiple times from an input unit110to the switch unit140, until the switch unit140has transmitted a copy of the multicast packet to each of the multicast packets destination output units170.

The implementation of the switch unit140for performing fabric scheduling is outside the scope of this invention, whereby well known implementation approaches include scheduled crossbar switches, shared memory buffer switches, and buffered crosspoint switches, implemented in a single or multi-stage switch topologies. A typical switch unit implementation includes a single device unit in smaller switching apparatus implementations, while multiple device units are typically used in larger switching apparatus implementations.

FIG. 2shows the details of an input unit110that may be utilized in the first embodiment. Incoming unicast and multicast packets arrive at the input port200of the input unit110. If the arriving packet is a multicast packet, it is buffered in one of the Input Multicast Queue (IMQ)220, where each IMQ220represents a multicast QoS priority. It is the multicast packet's QoS priority which determines in which IMQ220the multicast packet is buffered.

The DataTx unit292interfaces between the IMQs220and the ingress data link294which connects the input unit110to the switch unit140. It is the DataTx unit292which controls when multicast packets are forwarded from the IMQs220to the switch unit140. The implementation of the switch unit140and the associated DataTx unit292in the input unit110for performing fabric scheduling is outside the scope of this invention, and may be performed by conventional fabric scheduling techniques. In a typical implementation, the forwarding of multicast packets is controlled by a multicast scheduling mechanism provided by the switch unit140, and/or by a multicast scheduling mechanism provided by the input unit110, and/or by a multicast flow control backpressure mechanism between the switch unit140and the input unit110.

If the incoming packet is a unicast packet, it is buffered in one of the Input Unicast Queues (IUQ)210, where each IUQ210represents a distinct <output port, unicast QoS priority> combination. It is the unicast packet's destination output port and unicast QoS priority which determines in which IUQ210the unicast packet is buffered.

The DataTx unit292interfaces between the IUQs210and the ingress data link294which connect the input unit110to the switch unit140, in a fabric scheduling stage. It is the DataTx unit292which controls when unicast packets are forwarded from the IUQs to the switch unit140. The implementation of the switch unit140and the associated DataTx unit292in the input unit110for performing fabric scheduling is outside the scope of this invention, and may be performed by conventional fabric switching techniques. In a typical implementation, the forwarding of unicast packets is controlled by a unicast scheduling mechanism provided by the switch unit140, and/or by a unicast scheduling mechanism provided by the input unit110, and/or by a unicast flow control backpressure mechanism between the switch unit140and the input unit110.

Before a unicast packet can be forwarded from the IUQ210to the DataTx unit292, it is qualified for forwarding as described in the following. A credit counter variable, UnicastCreditCnt290, is maintained per IUQ210. The counter maintains the IUQ's current number of credits, and the variable is defined the range given by:UnicastCreditCnt ε [−MTU to CreditMax]Where,MTU is the largest packet size supported by the switching apparatus (e.g., 128, 1500, 10000, or 16000 bytes)CreditMax is a threshold at which the UnicastCreditCnt counter saturates. A typical value of UnicastCreditCnt is MTU.The credit counter is updated such that,UnicastCreditCnt=UnicastCreditCnt+CreditMsg−PacketSize, and has a default reset value of zero.Where,CreditMsg is the credit value carried in an incoming unicast credit message270destined for the associated IUQ210. The addition of CreditMsg to UnicastCreditCnt is performed when the credit message arrives at the IUQ210via the incoming control link250.PacketSize is the size of a unicast packet which is moved from the IUQ210to the DataTx unit292. The subtraction of PacketSize from UnicastCreditCnt is performed by adder/subtractors when the packet is forwarded from the associated IUQ210to the DataTx unit292.

Before a unicast packet can be forwarded from an IUQ210to the DataTx unit292, it is qualified for forwarding as determined by the value of the UnicastCreditCnt variable associated with the IUQ210. The packets are qualified one-by-one for forwarding out of the IUQ210. The packet currently located in the front of the queue is qualified for forwarding when UnicastCreditCnt is equal to or greater than zero (UnicastCreditCnt≧0). When the UnicastCreditCnt holds a negative value, no packets can be qualified for forwarding from the IUQ210to the DataTx unit292.

A UnicastHungry status (Boolean) is associated with each IUQ210. The UnicastHungry status determines whether or not the IUQ210is requesting to be allocated and receive credits. When an IUQ's UnicastHungry status changes, information about the new status is forwarded as a unicast queue status message230, which is transmitted from the input unit110to the output unit170associated with the IUQ210, via the switch unit140. The UnicastHungry status is defined as:UnicastHungry=((NonEmpty) or (UnicastCreditCnt<0)) and (UnicastCreditCnt<CreditMax)Where,NonEmpty is a Boolean which is True (=“1”), when one or more packets are stored in the associated IUQ210.UnicastCreditCnt is the credit counter associated with the IUQ210(see definition above)CreditMax is defined above.

When the UnicastCreditCnt value is negative, the associated UnicastHungry status is True, which means that the IUQ210is eligible to receive credits. As credits arrive, the UnicastCreditCnt will eventually reach a value of zero or higher, which in turn will qualify the current packet in head-of-line position in the IUQ210to be forwarded, whenever the input unicast queue is non-empty.

In an alternative implementation of the first embodiment, the IUQ's head-of-line packet can be qualified for forwarding when UnicastCreditCnt is equal to or greater than the size of the head-of-line packet. In such an alternative implementation of the first embodiment, the UnicastCreditCnt variable holds a value of zero or higher.

The unicast queue status messages are generated based on the associated UnicastHungry status variables as described above, and it is the CtrlRxTx unit280which performs the transmission of the unicast queue status messages to the output unit via the outgoing control link240which connects the input unit110to the switch unit140.

Credit messages which have been generated by the output units170and transmitted to the input unit110, via the switch unit140, are received by the CtrlRxTx unit280via the incoming control link250. It is the CtrlRxTx unit280which performs the reception of credit messages, and directs the received credits to their destination IUQ210and associated UnicastCreditCnt variable.

The implementation of the switch unit140and the associated CtrlRxTx unit280in the input unit for performing fabric scheduling is outside the scope of this invention, and may be performed by conventional fabric scheduling techniques. In a typical implementation, the transmission and reception of the queue status and credit messages is controlled by a message scheduling mechanism provided by the switch unit140, and/or by a message scheduling mechanism provided by the input unit110, and/or by a message flow control backpressure mechanism between the switch unit140and the input unit110.

FIG. 3shows the details of an output unit170. Unicast queue status messages which have been generated by the input units110and transmitted to the output unit170, via the switch unit140, are received by the CtrlRxTx unit305via the incoming control link300. It is the CtrlRxTx unit305which performs the reception of unicast queue status messages, and forwards310the received queue status information to the output port scheduler unit320.

Through the received unicast queue status messages, the output port scheduler unit320maintains the UnicastHungry status for every IUQ210in the switching apparatus which corresponds to the particular <output port, unicast QoS priority> combination. The queue status is updated whenever a unicast queue status message arrives, according to the queue status carried in the incoming unicast queue status message.

The output port scheduler unit320generates a stream of credit tokens, where the value of the credit tokens corresponds to the output ports maximum transmission rate. The following steps determines if the credit token results in the generation of a credit message, and if so, to which IUQ210or OPQ360the credit message is to be transmitted.1. Wait for a credit token to become available for the output port.2. Filter out the output ports unicast QoS priorities, for which the UnicastHungry status is False for all IUQs210corresponding to the output port unicast QoS priority.3. Filter out the output ports multicast QoS priorities, for which the MulticastHungry status is False for the corresponding Output Port Queue (OPQ)360(see description of Output Port Queue (OPQ)360and associated MulticastHungry status below).4. Select a unicast or multicast QoS priority between the remaining non-filtered unicast and multicast QoS priorities. The selection is performed according to the priority order between unicast and multicast QoS priorities. If all QoS priorities have been filtered out, discard the credit token and go to step 1.5. If the selected QoS priority is a unicast QoS priority:a. Select round robin or weighted round robin between the input units, which have an IUQ210corresponding to the selected unicast QoS priority, for which the UnicastHungry status is True.b. Generate a unicast credit message, and forward it325to the CtrlRxTx unit305.c. Transmit the credit message to the selected input unit which implements the IUQ210for which the credit message is destined (via a control link332and the switch unit).d. Go to step 1)6. If the selected QoS priority is a multicast QoS priority:a. Generate a multicast credit message for the selected Multicast QoS priority.b. Forward the multicast credit message330to the MulticastCreditCnt variable370associated with the selected multicast QoS priority and corresponding Output Port Queue (see detailed description of Output Port Queue (OPQ)360and associated MulticastCreditCnt variable below).c. Go to step 1

The implementation of the CtrlRxTx unit305for performing fabric scheduling depends on the switch unit implementation which is outside the scope of this invention, and may be performed by conventional fabric scheduling techniques. In a typical implementation, the transmission and reception of the queue status and credit messages is controlled by a message scheduling mechanism provided by the switch unit140, and/or by a message scheduling mechanism provided by the input unit110, and/or by a message flow control backpressure mechanism between the switch unit140and the input unit110.

Incoming unicast and multicast packets arrive via the egress data link340from the switch unit140, and are received by the DataRx unit345via the incoming data link340. It is the DataRx unit345which performs the reception of packets, and directs the received packets to the OPQ360queue depending on the packet type (unicast or multicast) and unicast355or multicast350QoS priority. The implementation of the switch unit140and the associated DataRx unit345in the output unit170for performing fabric scheduling is outside the scope of this invention, and may be performed by conventional fabric scheduling techniques.

The output unit170implements an OPQ (output port queue) queue360for each unicast and multicast QoS priority defined for the output port. A credit counter variable, MulticastCreditCnt370, is maintained per OPQ360associated with a multicast QoS priority. This variable maintains the associated multicast OPQ's current number of credits, and the variable is defined the range given by:MulticastCreditCnt ε [−MTU to CreditMax]
Where,MTU is the largest packet size supported by the switching apparatusCreditMax is a threshold at which the UnicastCreditCnt counter saturates. A typical value of CreditMax is a value equal to MTU.The credit counter is updated such that,MulticastCreditCnt=MulticastCreditCnt+CreditMsg−PacketSize, and has a default reset value of zero.Where,CreditMsg is the credit value carried in a multicast credit message which has been received330from the output port scheduler320, and the addition to MulticastCreditCnt is performed when the multicast credit message is received from the egress port scheduler.PacketSize is the size of a multicast packet which is moved from the OPQ360to the Output Port Transmit (OPT) unit380. The subtraction from MulticastCreditCnt is performed by adder/subtractors when the packet is forwarded from the OPQ360to the OPT unit380.

A MulticastHungry status (Boolean) is associated with each OPQ360defined per multicast QoS priority for the output port. The MulticastHungry status determines whether or not the OPQ360is eligible to be allocated and receive credits from the output port scheduler unit320. The MulticastHungry status is made available to the output port scheduler unit320which is implemented in the same output unit. The MulticastHungry status is defined as:MulticastHungry=((NonEmpty) or (MulticastCreditCnt<0)) and (MulticastCreditCnt<CreditMax)Where,NonEmpty is a Boolean which is True (=“1”), when one or more packets are stored in the associated multicast OPQ360.MulticastCreditCnt is the credit counter associated with the OPQ360(see definition above)CreditMax is defined above.

The OPT unit380continuously performs a packet arbitration and transmission function algorithm, such as described in the following steps:1. Wait until one or more of the OPQs360buffer a packet, i.e., until one or more of the OPQs360can be considered as non-empty according to the following definition of non-empty OPQ queue state.a. An OPQ360which corresponds to a unicast QoS priority is non-empty when it holds one or more packets. If not, it is considered empty.b. An OPQ360which corresponds to a multicast QoS priority is considered non-empty when it holds one or more packets and the corresponding MulticastCreditCnt variable is greater than or equal to zero (MulticastCreditCnt20).2. Select between non-empty OPQ360in the following priority order: unicast QoS priority 1 OPQ, multicast QoS priority 2 OPQ, unicast QoS priority 3 OPQ, multicast QoS priority 4 OPQ.3. Forward a packet from the selected non-empty OPQ360and transmit the packet across the output port.4. Go to step 1

In the present invention, both the input units110and the output units170perform credit based scheduling, whereby the input units110are slaved to the output units170in the determination of which packets or cells are qualified for transfer across the switch unit140. The input units110are involved in the credit based scheduling by generating unicast queue status messages230, and counting received credits per input queue, and providing that information to the corresponding output unit170. In that way, the output units170provide the primary control for the credit based scheduling, whereby the input units110provide information to the output unit170for use in the credit based scheduling.

FIG. 4shows the unicast and multicast QoS priorities provided by the switch apparatus according to the first embodiment. The switch apparatus arbitrates between unicast and multicast traffic using a priority scheme, which is equivalent to the OPQ arbitration performed by the OPT unit380. In one possible implementation of a priority scheme, the 1stpriority is unicast QoS priority 1, the 2ndpriority is multicast QoS priority 2, the 3rdpriority is unicast QoS priority 3, and the 4thpriority is multicast QoS priority 4. The unicast and multicast packet priorities provided by the switch apparatus are therefore identical to the QoS priority arbitration performed between OPQs360by the OPT unit380.

Compared to unicast packets which receive the credits at the ingress queues, the multicast packets receive the credits at the OPQ360. Otherwise, the scheduling of unicast and multicast packets using a credit based procedure at the traffic scheduling stage is not much different from each other.

The methodology of a first embodiment of the present invention has now been described above. The following will describe different options and approaches for implementing the present invention.

The output unit implementation shown inFIG. 3shows a single output port per output unit170. An alternative implementation provides multiple output ports per output unit170. In such an implementation, the output port scheduler unit320schedules each of the output units output ports fully independently of each other, and the OPQs360and the OPT unit380are implemented per output port provided by the output unit170. In such an implementation where the output units170implement multiple output ports, the switch unit140still only needs to perform arbitration with input and output unit resolution. This allows for scaling the number of ports in the switching apparatus, without affecting the complexity of the switch unit implementation since the granularity of the switching arbitration provided by the switch unit140becomes independent of the number of output ports provided per output unit170.

The above-described implementation provides a total of four (4) QoS priorities per output port. An alternative implementation can implement any integer number N of QoS priorities per output port, and the priority order between unicast and multicast QoS priorities can be arbitrarily defined, as long as the QoS priority arbitration performed by the OPT unit380matches the unicast versus multicast packet arbitration performed by the switch apparatus. The number of QoS priorities and associated OPQs provided by the output unit170may be larger than the number of QoS priorities. This allows for scaling the number of QoS priorities per output port in the switching apparatus, without affecting the complexity of the switch apparatus implementation since the QoS prioritization granularity of the switching arbitration provided is independent of the number of QoS priorities provided per output unit.

FIG. 5shows an alternative implementation of the first embodiment, where the exchange of credit and unicast queue status messages between the input and output units is performed in-band with the switching of packets from input units110to output units across the switch unit140. In-band signifies that credit and unicast queue status messages are transmitted in an interleaved manner (e.g., at predetermined positions for data packets and control information per each link) on the same input and output links, so that the control and data links shown onFIG. 1can be merged into single combined data/control input500or output link510.

The input and output link shown inFIG. 1andFIG. 5can be implemented using one or multiple serial link transmission connections.

The description of the first embodiment has referred to packets, which is a variable size data unit. The present invention also applies to a subset of fixed size packets, which is referred to as a cell unit in the field of networking switching apparatus.

Thus, apparatuses and methods have been described according to the present invention. Many modifications and variations may be made to the techniques and structures described and illustrated herein without departing from the spirit and scope of the invention. Accordingly, it should be understood that the methods and apparatus described herein are illustrative only and are not limiting upon the scope of the invention. Further, one or more aspects as described can be combined in any given system or method. Still further, one or more embodiments may be implemented in hardware, e.g., by a schematic design or a hardware description language (HDL), and/or implemented in a programmable logic device (FPGA/CPLD) or an ASIC, and/or they can be implemented in hardware using discrete hardware devices.