Nonblocking and fair queuing switching method and shared memory packet switch

[0002] The present invention relates to all cell or frame based shared memory switches that control routing-of discrete packets between an input port and an output port.

[0003] Two basic forms of communications are circuit switched and packet switched communications. Circuit switched communications open a dedicated path of communication between a source and a destination. This forecloses access to the path by other sources and/or destinations even if only a small portion of the bandwidth of the path is being utilized. In the packet switched method, data is broken into packets when transmitted from a source and reassembled at the destination. This allows multiple sources and destinations to divide up and utilize the bandwidth of any given path, but presents a more complex problem because conflicting communications will contend for limited communication path resources.

[0004] Such switches require an amount of memory because packets will often have to wait a number of cycles before being transferred due to contention. Multi-port switches are generally classified by the manner in which their memory is allocated, as either input buffered, output buffered or shared memory architectures.

[0005] Input buffered switches are those in which packets are stored in an input queue. The recognized problem of these switches is termed head-of-line-blocking (HOL), where a packet at the head of the queue prevents others from being transmitted until the destination port transmits that packet. An algorithm is applied to the packet at the head of the queue to determine its destination. This packet remains at the head of the queue until the destination port processes or transmits the packet. Additional received packets are blocked by the packet at the head of the line. As an example, consider a system having one input port A and two output ports B and C. A situation may occur where output port B has become congested and packets arriving from input port A can not be transmitted to output port B as fast as they are arriving. Packets buffered for output port C will be transmitted. After a time, the buffers will be filled with packets destined for output port B which can not be transmitted. At this point, all packets arriving from input port A for output B and for output port C will be discarded. Even though output capacity for output port C is available, congestion at output port B will cause output port C's packets to be dropped. This head of line blocking is an undesirable effect because congestion on one network path interferes with traffic on other uncongested paths.

[0006] Output buffered switches solve these input buffered switch blocking problems by queuing packets at the output ports. This prevents one stream of traffic from a given input port from blocking other streams of traffic destined for a different output port. These switches suffer from a fairness problem though, because there is the potential that where traffic is inbound on two ports and destined for a single output port, one stream will completely consume all available buffers associated with the single port, leaving no buffers for the second stream. The problem is acute in environments with large bursts of traffic. Outbound packets are dissociated from their input port, any input port can therefore consume all the available buffers, leaving very few or no buffers for other input ports.

[0007] Shared memory switch architectures alleviate some of problems of both input buffered and output buffered switches, but potentially suffer the same problems of each to a lesser degree. In a shared memory switch, there is a pool of available buffers. These buffers may be allocated as either input or output buffers as needed. Once a buffer is released, it is returned to the pool of available buffers for use again as either an input or output buffer. There is a reduced potential for head-of-line-blocking and unfairness in allocation of the buffers, but each is still possible.

[0008] Accordingly, there is need for a shared memory switching method which solves head-of-line-blocking problems and provides improved fairness in allocation of output buffers among input ports. It is an object of the invention to provide such an improved shared memory switching method and switch.

[0009] The present invention provides an improved shared memory switching method and switch in which a guaranteed minimum number of buffers per output port is reserved for each input port. This precludes one input port from blocking the packet traffic of another input port at any of the output ports of the switch. The invention also provides a burst handling capability through optional preferred features in which the shared memory of the switch is divided into reserved and unreserved buffers, with the guaranteed minimum number of buffers being provided from the reserved buffers. The unreserved buffers are available to any port and will handle burst communications that exceed a given input port's allocation of reserved buffers. So that bursts are also handled fairly among input ports, additional optional preferred features of the present invention involve limiting the number of unreserved buffers that may be consumed by a single input port. For fairness among output ports, method also preferably fairly allocates unreserved buffers among the output ports.

[0010] Other features, objects and advantages of the present invention will be apparent to those skilled in the art through reference to the attached drawings, of which:

[0011] FIG. 1 is a logical diagram of a shared memory switch of the present invention;

[0012] FIG. 2 is a logical diagram illustrating burst handling features of the switch of the present invention; and

[0013] FIG. 3 is a logical diagram illustrating additional burst handling features of the present invention.

[0014] Broadly stated, the present invention concerns a shared memory packet switching method and switch which allocates the shared memory among input ports of the switch for output ports of the switch to prevent blocking by any particular input port of the switch. No single input port can exhaust reserved buffers from the shared memory and block access by another input port to any given output port. Burst conditions are handled by additional optional features of the invention, which permit use of unreserved buffers for burst conditions. Fairness may be provided in burst conditions through limiting the number of unreserved buffers that can be simultaneously used by a single output port for packets from a single input port. Limiting parameters and counters are preferred methods for tracking buffer quantities to achieve each of the various buffer allocation features provided by the invention.

[0015] For simplicity of illustration, the following description assumes a buffer size that is equal to one packet, reflecting the case of implementations where the buffer size is as large as the largest packet. Accordingly, each packet is stored in one buffer. Artisans will appreciate, however, that the invention is not limited to that case and is equally applicable to other implementations where a smaller buffer is used. For example, a buffer size of 256 bytes might be used and the largest packet size might be 1522 bytes. In that case, each packet would be stored in 1 to 6 buffers depending on its size. In the latter case, counters described herein would simply be incremented or decremented by the number of buffers in which the packet is stored rather than by one as in the illustrated embodiment.

[0016] Referring now to FIG. 1, shown is a logical representation of a switch constructed and managed in accordance with the invention to divide a shared free pool of buffers 10 among a plurality of X output ports 12 to allow shared and nonblocking access by a plurality of Y input ports 14. When a packet arrives at the switch, an input port 14 grabs an available buffer, e.g., buffer 1 of T total free buffers in the buffer pool 10. Once a switching decision is made in conventional fashion for the given packet which has been buffered, for example, at an input port 14(2), the given packet is added to the transmit queue of the appropriate destination output port designated by the given packet by transferring the buffer holding the packet to the output port, which in the example of FIG. 1 is the first output port 12(1). Additional buffers are then grabbed as needed by the input port 14(2) for receiving an additional packet. A single packet may use one or more buffers depending upon the particular switching implementation. Once the given packet is transmitted from the output port 12(1), the buffer (or buffers) which held it is released back into the free buffer pool, completing the general cycle of passing a packet through the switch.

[0017] In accordance with the invention, the available resources of the free buffer pool are allocated among output port 12(1)-12(X) and input port 14(1)-14(Y) pairs to avoid the case where a single port can monopolize available buffers causing blocking conditions at other ports. The pool 10 is divided into a reserved number of buffers, designated as Total Free Buffers (T). The following steps will allocate the T available buffers among ports of the switch.

[0018] Let there be P_Onumber of output ports on the switch and P_Inumber of input ports. A parameter G, which can be set globally or individually for each output port, indicates the number of buffers that are reserved or dedicated for each input port to a given output port. A preferred embodiment equally divides the T reserved buffers among ports of the switch. In that case, the parameter G is set to T/(P_O*(P_I−1)). P_I-1 accounts for the fact that a packet received on an input port is not forwarded on the same port and hence is not buffered to that port. Thus, each output port will have G buffers reserved for each input port.

[0019] For the buffer management, there are a plurality of individual counters 16 on each output port counting buffers that are used by each input port for each output port. Each counter has the label, CO_XI_Y, where X is the output port number and Y is the input port number which received the packet. Accordingly, CO₁I₂is the counter at output port 12(1) that counts the number of packets queued from input port 14(2). At power up/reset, all CO_XI_Ycounters are set to zero. An input port of the switch retrieves a buffer from the free buffer pool. The input port uses this free buffer to receive a given packet, as represented by arrow 1 of FIG. 1.

[0020] The packet forwarding decision is made on the received packet. There are two possible forwarding decisions. In the case of a unicast, the packet is forwarded to a unique output port. In the case of broadcast or multicast, the packet is forwarded to a group of output ports.

[0021] In a unicast, the packet is added to the transmit queue of an output port if the output port counter CO_XI_Yis less than G (indicating that the output port has reserved buffers for this input port), as indicated by arrow 2 of FIG. 1. After a packet is queued to the output port, the corresponding counter CO_XI_Yis incremented. The packet is discarded if the output counter CO_XI_Yhas reached G. Hence, discard if (CO_XI_Y=G). Once the packet has been transmitted, the CO_XI_Ycounter is decremented and the buffer is released to the free buffer pool, as indicated by arrow 3 in FIG. 1.

[0022] A multicast occurs when the given packet is intended for multiple destinations. In such case, a packet may be added to several output ports which satisfy the same conditions as a unicast packet on any output port. If the conditions are not met on an output port, the packet is not queued to that port, but is queued to any other output port having available buffer capacity reserved to it for the input port receiving the packet. If the packet is queued, the corresponding counter CO_XI_Yis incremented. When an output port transmits the packet, it decrements the counter CO_XY. When the last port has transmitted the packet, the buffer is released to the free pool of buffers.

[0023] This allocation of reserved buffers ensures that each port gets its fair share of the free buffers. It gives absolute fairness to all ports. However, burst events may result in packet loss since a port is only allocated its reserved buffers. The invention therefore optionally provides additional preferred features to accommodate burst events, which will be useful in implementations where such events are likely. This is accomplished by having a quantity of unreserved buffers in the pool of buffers. The available buffers in the pool 10 are divided into reserved and unreserved buffers. The reserved buffers provide guaranteed availability, in the manner described above. The remaining number of buffers are unreserved and can be used by any input port to absorb the bursts.

[0024] The burst capability of the invention preferably uses an additional counter C_uto track unreserved buffers. Since G represents the guaranteed buffers available at a given output port for each input port, the system must reserve this number of buffers from the pool 10. Therefore, in a system with P_Iinput ports the guaranteed buffers to be reserved, at one output, for all input ports is GBR=(P_I−1)*G, where P_I−1 accounts for the fact that a packet received on an input port is not forwarded on the same port and hence is not buffered to that port.

[0025] If the same amount is to be guaranteed for each output port, then the required total number of guaranteed buffers needed to be reserved from the pool 10 is N=[(P_I1)*G]*P_O. If different numbers of buffers are allocated at each output port, then N will be a summation of the buffers reserved separately at the output ports. Input ports will require P_Inumber of buffers to receive next incoming packets. Therefore, free available unreserved buffers is defined as F=T−N−P_I. The value of F and G are inter-related and are implementation dependent.

[0026] Management of the reserved buffers is as described above, with the CO_XI_Ycounters ensuring that reserved buffers are fairly allocated at each output port for each input port. For the management of unreserved buffers, the additional unreserved buffer counter C_ukeeps the total count of available unreserved buffers. At power up/reset, CO_XI_Ycounters are set to zero and counter C_uis set to F. An input port of the device retrieves a buffer from the free buffer pool and it uses this free buffer to receive a packet.

[0027] In the unicast case, if the output port counter CO_XI_Yis less than G (indicating that the input port has a reserved buffer for this output port) the packet is added to the transmit queue of the output port and counter CO_XI_Yis incremented. Where CO_XI_Yequals G, such as during a burst event or a backup at an output queue, available unreserved buffers may be used. This is the case if the value of C_uis greater than or equal to I (indicating that at least one unreserved buffer is available). Where an unreserved buffer is used, the packet is added to the transmit queue of the output port, C_uis decremented and the packet buffer is marked as allocated to unreserved (this marking will become important when the packet is transmitted). If C_uis zero, no unreserved buffers are available and the packet is dropped. Hence, the packet is enqueued if either CO_XY<G or C_u>=1.

[0028] Once the packet has been transmitted, it must be determined whether the packet occupied a reserved or unreserved buffer. If the packet occupied an unreserved buffer (based on marking), C_ushould be incremented. Hence, after transmission, the buffer is released to free buffer pool and CO_XI_Yis decremented if buffer was marked reserved. Otherwise, C_uis incremented if the buffer is marked unreserved.

[0029] Where unreserved and reserved buffers are used, the preferred method of conducting a multicast uses available unreserved buffers for the multicast to avoid complications in releasing reserved buffers used in a multicast. In such a multicast, if C_u>=1 the packet is marked as using unreserved buffer and then added to each output queue specified in the multicast and the counter C_uis decremented. If no unreserved buffer is available, i.e., C_u=0, then the packet is dropped. The same buffer is queued to each output port queue specified in the multicast decision and C_uis decremented once since one buffer is used. When the last output port specified in the multicast has transmitted the packet, the buffer is released to the free buffer pool and counter “C_u” is incremented.

[0030] In both methods above, i.e., the use of reserved buffers where only reserved buffers are available and the use of unreserved buffers where both reserved and unreserved buffers are available, some inefficiency is caused by the need to handle multicast packets. In one case, a multicast packet consumes only one buffer, but buffer space is reserved for it by each packet for which it is queued. In the other case, there will be times when CO_XI_Yhas dropped below G but buffers for that output port are still used from C_u. In many cases, this is an acceptable trade-off for the simplification of the method it allows. In many cases, the inefficiency caused by the first is small because multicast packets are often a very small percentage of traffic. In the second case, since bursts are transient conditions, the buffers in C_uwill soon be released having accomplished their purpose of accommodating the burst.

[0031] However, there is an alternative which can be used where greater efficiency is desirable. This alternative is to treat multicast traffic as a separate output port for buffer utilization considerations. In this case, guaranteed buffers are allocated for multicast packets with a plurality of counters CO_MYwith one counter for each input port. M=G*P_Ibuffers are reserved for multicast packets. Buffers for output ports and unreserved buffers are allocated as above. The unreserved buffers will be F=T−N−M−P_I.

[0032] At power up/reset, CO_XI_Ycounters and counters CO_MYare set to zero and counter C_uis set to F. An input port of the device retrieves a buffer from the free buffer pool and it uses this free buffer to receive a packet,

[0033] In the unicast case, if the output port counter CO_XI_Yis less than G (indicating that the input port has a reserved buffer for this output port) the packet is added to the transmit queue of the output port and counter CO_XI_Yis incremented. Where CO_XI_Yis greater than or equal to G, such as during a burst event or a backup at an output queue, available unreserved buffers may be used. This is the case if the value of C_uis greater than or equal to 1 (indicating that at least one unreserved buffer is available), and then the packet is added to the transmit queue of the output port, C_uis decremented and CO_XI_Yis incremented. In this method, there is no need to mark the buffer as coming from the unreserved pool. If C_uis zero, no unreserved buffers are available and the packet is dropped. Hence, the packet is enqueued if either CO_MY<G or C_u>=1.

[0034] Once a unicast packet has been transmitted, it must be determined whether the output-input port pair was using any unreserved buffers. If CO_XI_Yis greater than G, it was and C_uis incremented. In either case, CO_XI_Yis decremented. With this method, an unreserved buffer will be released as soon as any packet is transmitted from an output-input port pair that had used more than its reserved allocation rather than on transmission of the specific packet that on reception caused the allocation to be exceeded. Availability of unreserved buffers is maximized.

[0035] When a multicast packet is received, the behavior is the same except that the counter CO_MI_Yis used in place of CO_XI_Y. When the last output port specified in the multicast has transmitted the packet, the buffer is released to the free buffer pool and counter CO_MI_Yis decremented. If CO_MI_Yis greater than G, C_uis incremented. In !this method, no CO_XI_Ycounter is ever incremented or decremented for a :Multicast packet. The following optional features may also alternately use this CO_MI_Yto achieve multicast as alternatives to the specific described uses of unreserved buffers.

[0036] It is possible that a burst, a slow communication channel, or other event may cause a single input port to dominate use of the unreserved buffers. Additional optional preferred features build upon the unreserved buffer concept and introduce a new parameter; MAI, and a new counter CI_y, to achieve fairness during such events and avoid such domination. These features are logically represented in FIG. 2, where each input port 14 has a CI_Ycounter and an associated MAI parameter. The maximum available buffers per input port, MAI, determines the maximum number of buffers that an input port is allowed to use from the unreserved buffers at any one time. The MAI can be set between 0 and F. The term F represents the case where all the free available buffers may be allocated to a single port allowing that port to dominate use of the unreserved buffers. The MAI can be globally set or it can be unique for each input port and is implementation dependent. The following implementation assumes a globally set MAI for illustrative purposes, but unique MAI_Y, where Y= a corresponding input port may easily be implemented in similar fashion.

[0037] The CI_Ycounter is also set to zero at reset or power up. Thus, at power up/reset, CO_XI_Ycounters are set to zero, CI_Yis set to zero, C_uis set to F.

[0038] In the unicast case, if CO_xI_y<G a packet received at an input port is added to the output queue determined by a forwarding decision based on the packet and the corresponding CO_XI_Ycounter is incremented (arrow 2 of FIG. 2). Where a burst or other event results in CO_XI_Ybeing equal to G, the packet may still be added to the appropriate output queue only if CI_Y<MAI and C_u>= 1. In the latter case, CI_Yof the input port is incremented, the packet is marked as occupying unreserved buffer, and C_uis decremented. If either CI_Y=MAI or C_u<1, the packet is dropped. Where CI_Y=MAI, the packet is dropped even though some unreserved buffers might be available. This preserves fairness in the allocation of the unreserved buffers.

[0039] When the output port transmits the packet, it decrements the associated CO_XI_Yif the buffer holding the packet was reserved and releases the buffer to the free buffer pool (arrow 3 of FIG. 2). If the packet had been marked as unreserved then counter C_uis incremented and CI_Yis decremented.

[0040] In the multicast case, if for an output port CI_Y<MAI and C_u>=1 or the packet has been marked as unreserved buffer (indicating that a buffer has already been allocated for the multicast) then the packet is added to the output queue specifed in the multicast decision. If the packet is unmarked, then the packet is marked as occupying an unreserved buffer, the counter C_uis decremented and CI_Yof the input port which queued the given packet is incremented. Otherwise, the packet is dropped. When the last port has transmitted the packet, the buffer is released to the free buffer pool 10, counter C_uis incremented and CI_Yis decremented.

[0041] Additional optional preferred features embody fair allocation of unreserved buffers, for a given input port, among output ports. This is represented logically in FIG. 3. To achieve fairness in allocating unreserved buffers among output ports, an additional parameter M is used to restrict each output port's use of unreserved buffers. Like MAI, M may be unique to individual output ports or may be globally set to be equal for each output port. In the latter case, M₁=M₂=M₃=M_pin FIG. 3, and the globally set value is simply referred to as M.

[0042] In addition to the previously discussed counters, there are individual counters UO_XI_Yon each output port counting unreserved buffers that are used by each input port for each output port. Each counter has the label UO_XI_Ywhere x is the output port number and y is the input port number which received the packet. At power up/reset, the CO_XI_Y, UO_XI_Y, and CI_Ycounters are set to zero and counter C_uis set to F.

[0043] After input queuing of a given packet and a forwarding decision based on a destination specified by the given packet, either a unicast or multicast is implemented. In the case of a unicast, if CO_XI_Y<G the packet is added to the output queue designated through the forwarding decision and its CO_XI_Ycounter is incremented. Where CI_Y<G, the packet is still queued using an unreserved buffer only if CI_Y<MAI and C_u>=1 and UO_XI_Y<M. In the latter case, three associated operations are conducted: increment UO_XI_Y; increment CI_Yof the input port, mark packet as occupying unreserved buffer, and decrement counter C_u. As a result, the packet may be dropped even though unreserved buffers are available if either the particular input port or output port has exhausted its allotment of unreserved buffers. If any of the conditions for queuing the packet using the unreserved buffer are not met, the packet is dropped.

[0044] When the output port transmits the packet, it decrements the counter CO_XI_Yif the buffer holding the packet was reserved, and releases the buffer to the free buffer pool. If the packet had been marked unreserved then counter C_uis incremented, and UO_XI_Yand CI_Yare decremented.

[0045] In the multicast case, if CI_Y<MAI, UO_XI_Y<M, and C_u>=1 or the packet is marked as unreserved buffer, indicating an unreserved buffer has already been allocated when the packet was queued at another output queue, then the packet is added to an output queue specified in the multicast. If the packet is unmarked, then it is marked as occupying unreserved buffer, UO_XI_Yis incremented, C_uis decremented, and CI_Yof the input port which queued the given packet is incremented. The test and resulting actions are repeated for each output port specified in the multicast. If the conditions are not met for any output port (that is, the packet is not queued to any output port), the packet is dropped. When the packet is transmitted on a port, UO_XI_Yfor that port is decremented. When the last port has transmitted the packet, the buffer is released to the free buffer pool 10, counter C_uis incremented and CI_Yis decremented.

[0046] This final optional feature provides fairness by accounting for uneven data rates, uneven traffic loads and collisions on shared media among the output ports. For each of these conditions, an output port will not capture all the buffers if the packets are being forwarded to one congested port.

[0047] In varying result, the invention therefore provides for the fair use of shared memory resources in an packet switch. Reserved buffers are allocated among ports to prevent a single port from dominating the memory causing a blocking condition. Unreserved buffers may also be provided in the shared memory pool to accommodate bursts of traffic and other events which can lead to an unfair buffer allocation. Additional levels of fairness are provided to accommodate burst and similar conditions when unreserved buffers are allocated among input ports and allocated among output ports. Individual allocating may be varied for any of the features of the invention thereby permitting tailoring of allocations to suit individual implementations based upon determined traffic conditions, and the parameters may change over time through software or firmware code with or without human intervention as monitored traffic conditions change.

[0048] While various embodiments of the present invention have been shown and described, it should be understood that other modifications, substitutions and alternatives are apparent to one of ordinary skill in the art. Such modifications, substitutions and alternatives can be made without departing from the spirit and scope of the invention, which should be determined from the appended claims.

[0049] Various features of the invention are set forth in the appended claims.