Network switch having source port queuing and methods, systems and computer program products for flow level congestion control suitable for use with a network switch having source port queuing

[0002] The present invention relates to network communications and more particularly to congestion control in network communications.

[0003] In conventional networks, the rate of communications between network nodes, such as network switches, may be controlled so as to avoid congestion within the network which may reduce network throughput to unacceptable levels. Typically, congestion control mechanisms measure queue occupancy at a network node and utilize one or more occupancy thresholds which, if exceeded, can result in reducing the rate at which communications are received by a network node. Such congestion mechanisms have typically reduced data rates into the node experiencing congestion by pausing communications on a link into the node. When the incoming communications for a link have been paused, the outgoing communications may continue so as to reduce the queue occupancy at the node and, thereby, remove the congestion condition.

[0004] For example, if a network switch having N inputs and at least one output receives communications for the output from three of the N inputs, then, if a congestion condition is detected for the output, one or more of the three links would typically be paused to alleviate the congestion condition. In a link level congestion control system, the link associated with the input port which received the communication which resulted in the congestion condition would typically be paused for a predefined time period. One such link level congestion control system is provided by the Institute of Electrical and Electronics Engineers (IEEE) 802.3x specification which provides flow control through a pause message.

[0005] While link level flow control may avoid performance degrading congestion, such congestion control may also unnecessarily reduce throughput as pausing an entire link may overly restrict throughput. Accordingly, a need exists for improvements in network switches which may allow for improvements in congestion control in communications between network switches.

[0006] In light of the above discussion, the present invention may provide a network switch as well as methods, systems and computer program products for controlling congestion at a granularity of less than a link. Such finer granularity may be provided by pausing traffic at a source port level of a network switch. The network switch which transmitted a message which resulted in congestion being detected is notified of the congestion and pauses the communications from the source port of the message while maintaining communications over the link from other source ports. Such source port level congestion control may be provided by a network switch having a sub-queue of its output queues where each sub-queue corresponds to an input port. Source port level pausing of transmissions may then be provided by pausing the sub-queue associated with a source port.

[0007] In a particular embodiment of the present invention, flow control through a first network switch having a plurality of input ports and a plurality of output ports may be provided by receiving a message for transmission from an input port of the first network switch to an output port of the first network switch and determining if the received message results in an indication of congestion associated with transmitting the received message onto the output port. The transmission of messages received at a first input port on a second network switch which transmitted the message may then be paused while the second network switch continues to transmit messages received at input ports of the second network switch other than the first input port if the received message results in an indication of congestion.

[0008] In a further embodiment of the present invention, the transmission of messages received at a first input port on a second network switch may be paused by transmitting a pause message from the first network switch to the second network switch which specifies a source and/or destination address of the received message. The transmission of messages from the input port of the second network device associated with the source and/or destination address specified in the pause message may then be paused while continuing to transmit messages to the first network switch from input ports of the second network switch which are not associated with the source and/or destination address specified in the pause message.

[0009] In still another embodiment of the present invention, an output queue of the second network switch is associated with the output port over which the message received by the first network switch was transmitted. In such an embodiment, transmission of messages from the input port of the second network switch associated with the source and/or destination address specified in the pause message may be accomplished by dividing the output queue of the second network switch into a plurality of sub-queues, wherein each sub-queue corresponds to one of a plurality of input ports which receive messages for transmission on the output port of the second network switch. Messages received for transmission on the output port of the second network switch are stored in one of the plurality of sub-queues based on the input port from which the message was received. The sub-queue corresponding to the source and/or destination address specified in the pause message may then be determined so as to determine a paused sub-queue and transmission of messages in the paused sub-queue on the output port of the second network switch may be paused while continuing to transmit messages from sub-queues of the output port which are not paused.

[0010] In a still further embodiment of the present invention, the sub-queue corresponding to the source and/or destination address specified in the pause message may be determined by establishing a look-up table which relates source and/or destination addresses to source ports of the second network switch. The source and/or destination address associated with the input port of the second network switch to be paused may be extracted from the pause message and the input port to be paused identified utilizing the extracted source and/or destination address and the look-up table.

[0011] In specific embodiments of the present invention, the pause message specifies a duration during which messages from the input port of the second network device are paused.

[0012] Alternatively, the pause message may specify that messages from the input port of the second network device are paused until a resume message is received by the second network device. In such an embodiment, it may be determined if the congestion condition no longer exists. If so, a resume message may be sent from the first network switch to the second network switch so as to resume transmission of messages from the input port of the second network switch to the first network switch.

[0013] In a specific embodiment of the present invention, the pause message is an IEEE 802.3x link level flow control message. Furthermore, the link level flow control message may be a pause frame. In such an embodiment, the pad portion of the pause frame may include at least one of a source and a destination address.

[0014] A network switch according to the present invention includes a plurality of input ports and at least one output port. An output queue associated with the output port receives data from the plurality of input ports and provides data to the output port and a plurality of sub-queues of the output queue are also provided. Each of the plurality of sub-queues is associated with a respective one of the plurality of input ports so as to receive data from the associated respective one of the plurality of input ports.

[0015] The plurality of sub-queues may be configured so as to be separately paused so that one of sub-queues may be prevented from providing data to the output port irrespective of whether others of the plurality of sub-queues provide data to the output port. The plurality of sub-queues may also be configured so as to receive data from their respective input port irrespective of whether the sub-queue is paused. Furthermore, the output port may be configured so as to receive pause messages which specify an input port and further configured to pause a corresponding one of the sub-queues associated with an input port specified in a received pause message.

[0016] While the invention has been described above primarily with respect to the method aspects of the invention, both systems and/or computer program products are also provided.

[0017] FIG. 1 is a block diagram of a network switch according to one embodiment of the present invention;

[0018] FIG. 2 is a block diagram of a network configuration utilizing one embodiment of the present invention;

[0019] FIG. 3 is a diagram of a pause message suitable for use with the present invention;

[0020] FIG. 4 is a flowchart illustrating operations of a network switch according to an embodiment of the present invention when congestion is detected; and

[0021] FIG. 5 is a flowchart illustrating operations of a network switch upon receiving a pause message according to an embodiment of the present invention.

[0022] The present invention now will be described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art.

[0023] The present invention can be embodied as systems, methods, and/or a computer program products for congestion control in a network. As will be appreciated by those of skill in the art, the present invention can take the form of an entirely hardware embodiment, an entirely software (including firmware, resident software, micro-code, etc.) embodiment, or an embodiment containing both software and hardware aspects. Furthermore, the present invention can take the form of a computer program product on a computer-usable or computer-readable storage medium having computer-usable or computer-readable program code means embodied in the medium for use by or in connection with an instruction execution system. In the context of this document, a computer-usable or computer-readable medium can be any means that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

[0024] The computer-usable or computer-readable medium can be, for example, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. More specific examples (a nonexhaustive list) of computer-readable medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, and a portable compact disc read-only memory (CD-ROM). Note that the computer-usable or computer-readable medium could even be paper or another suitable medium upon which the program is printed, as the program can be electronically captured, via, for instance, optical scanning of the paper or other medium, then compiled, interpreted, or otherwise processed in a suitable manner if necessary, and then stored in a computer memory.

[0025] The present invention is described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to an embodiment of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart and/or block diagram block or blocks.

[0026] These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart and/or block diagram block or blocks.

[0027] The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart and/or block diagram block or blocks.

[0028] As is described in more detail below, the present invention provides for the control of communications between network switches so as to provide congestion control at a granularity of less than a link. Thus, the present invention may provide for pausing communications over a link to a network switch which originate from a particular source port of the network switch transmitting over the network link. Such source port level congestion control may be provided by providing sub-queues within an output queue of a network switch where the sub-queues are associated with a particular source port. Communications on the network link which originate from a particular source port may then be paused and queued in the corresponding sub-queue while other communications in the output queue are transmitted over the link. Thus, congestion control may be provided without necessitating that an entire link be paused. Such finer granularity may provide for improved throughput as a congestion control mechanism may fine tune the amount of communications which are paused to overcome a detected congestion condition.

[0029] FIG. 1 illustrates a network switch 10 according to an embodiment of the present invention. As seen in FIG. 1, the network switch includes a plurality of input ports A through Z (12athrough 12z). The input ports 12a-12zconnect to network links and receive communications to be routed to a plurality of output ports including the output ports 1 through N (14athrough 14n). Each of the output ports 1 through N, 14a-14n, has associated with it an output queue 16athrough 16n. The output queues 16a-16nreceive data from the input ports 12a-12zand supply data to the output ports 14a-14n.

[0030] As is seen in FIG. 1, data from any of the input ports 12a-12zmay be routed to any of the output ports 14a-14nand, therefore, each of the input ports may supply data to the output queues 16a-16n. However, as is further seen in FIG. 1, each of the output queues 16a-16nis subdivided into sub-queues 18a-18z, 20a-20zand 22a-22z. The number of sub-queues in an output queue 16a-16npreferably corresponds to the number of input ports 14a-14zin the network switch 10 such that each of the input ports 14a-14zprovides data to a corresponding one of the sub-queues 18a-18z, 20a-20zor 22a-22zof the output queues 16a-16n. However, groups of input ports may be represented by a single output queue and more than one output queue may represent a single output port.

[0031] As an example, data received on the input port A 12aand to be transmitted on the output port 114awould be queued in sub-queue 18aof output queue 16awhich corresponds to the input port A 12aas the source port of the data. Similarly, data received on the input port B 12band to be transmitted on the output port 114awould be queued in sub-queue 18bof output queue 16awhich corresponds to the input port B 12bas the source port of the data. Furthermore, data received on the input port Z 12zand to be transmitted on the output port 114awould be queued in sub-queue 18zof output queue 16awhich corresponds to the input port Z 12zas the source port of the data. Data received on the input port A 12aand to be transmitted on the output port 214bwould be queued in sub-queue 20aof output queue 16bwhich corresponds to the input port A 12aas the source port of the data. Data received on the input port B 12band to be transmitted on the output port 214bwould be queued in sub-queue 20bof output queue 16bwhich corresponds to the input port B 12bas the source port of the data. Furthermore, data received on the input port Z 12zand to be transmitted on the output port 214bwould be queued in sub-queue 20zof output queue 16bwhich corresponds to the input port Z 12zas the source port of the data.

[0032] In providing data from the sub-queues 18a-18z, 20a-20zand 22a-22zto the output ports 14a-14n, data may be taken from the sub-queues 18a-18z, 20a-20zand 22a-22zin a round-robin fashion such that data from each of the sub-queues 18a-18z, 20a-20zand 22a-22zof an output queue 16a-16nis transmitted on the corresponding output ports 14a-14nin a rotating manner. The precise mechanism of the rotation may vary from system to system and may, for example, take into account priority or bandwidth guarantees associated with data to be transmitted and thus, a weighted round-robin mechanism may be utilized. Furthermore, each of the sub-queues 18a-18z, 20a-20zand 22a-22zmay be paused by skipping a particular one of the sub-queues 18a-18z, 20a-20zand 22a-22zin the round-robin sequence. As will be appreciated by those of skill in the art, various conventional mechanisms for scheduling data from the sub-queues 18a-18z, 20a-20zand 22a-22zto be transmitted to the output ports 14a-14nmay be utilized while still benefitting from the teachings of the present invention. Thus, through the utilization of the queuing structure illustrated in FIG. 1, the sub-queues 18a-18z, 20a-20zand 22a-22zmay be individually paused.

[0033] Accordingly, the network switch 10 allows for the separate queuing of data in an output queue based on the input port (i.e. the source port) over which the data is received. As described below, such a separation of output queues 16a-16ninto the sub-queues 18a-18z, 20a-20zand 22a-22zmay allow for finer granularity in congestion control such that source port level congestion control may be utilized to reduce the amount of communication traffic flowing over a communication link without completely stopping the traffic flowing over the communication link.

[0034] FIG. 2 illustrates a network connection incorporating the network switch 10 to provide source port level flow control. Illustrated in FIG. 2 are two network switches 10 and 10′ connected by communication link 30. The network switches 10 and 10′ may be of the same or a different configuration, however, each should be capable of carrying out the operations described herein for congestion control. The network switches 10 and 10′ are illustrated in FIG. 2 as of the same configuration and, accordingly, corresponding aspects of network switch 10 are indicated in network switch 10′ by a prime indicator in the reference number.

[0035] Communication link 30 connects an output port 14aof the network switch 10 with an input port A 12a′ of the network switch 10′. As described above, data received from the input ports 12a-12zto be transmitted on the output port 14ais queued in the corresponding sub-queue 18a-18zbased on the input port 12a-12zfrom which the data was received. Data from the sub-queues 18a-18zis transmitted via output port 14aand communication link 30 to input port 12a′ of network switch 10′. Network switch 10′ may then queue the received data it its own output queue 16a′ and, preferably, a corresponding sub-queue 18a′ of output queue 16a′.

[0036] While the above operations of the network switches 10 and 10′ may be carried out during normal operations, in the event of the detection of congestion, the operations of FIGS. 4 and 5 may be carried out to pause data from a input port 12a-12zof the network switch 10 so as to alleviate a congestion condition at the network switch 10′. Preferably, if the network switch 10′ detects congestion associated with the output queue 16a′ as a result of data transmitted over communication link 30 and arriving at the input port A 12a′, then the network switch 10′ transmits a pause message over communication link 30 to the network switch 10. The pause message specifies a stream identifier associated with the data which resulted in the detection of the congestion condition. The network switch 10 receives the pause message and pauses the sub-queue of output queue 16awhich corresponds to the stream identifier specified in the pause message. In an IEEE 802.3x embodiment of the present invention, a pause message of the format illustrated in FIG. 3 may be utilized.

[0037] A seen in FIG. 3, an IEEE 802.3pause message may be modified according to the present invention by providing a stream indicator in the pad portion of the message. The stream indicator may act as a stream identifier from which the receiving network switch 10 may determine the sub-queue to pause. Thus, preferably, the stream indicator includes a source and/or destination media access controller (MAC) address of a message which resulted in the congestion condition. A source port associated with the source and/or destination address may be determined and the sub-queue associated with the source port identified by the stream identifier paused. A priority level could also be incorporated into the stream indicator so as to prioritize which sub-queues are paused in the event that multiple sub-queues are paused. For example, a further embodiment of the present invention might further partition traffic in sub-queues into sub-sub-queues of traffic of the same priority. Priority may be defined in terms of Internet Engineering Task Force (IETF) concepts in Differentiated Services or other priority mechanisms known to those of skill in the art.

[0038] Returning to FIG. 4, operations of switch 10′ will now be described. As seen in block 100, if the network switch 10′ detects congestion associated with the output port 14a′, the network switch 10′ determines the stream identifier of the data frame which resulted in the congestion condition (block 102). Suitable methods of determining if a congestion condition has occurred are known to those of skill in the art and, therefore, will not be described further herein. However, congestion tests may also be applied to the sub-queues of the present invention so as to prevent a sub-queue which is paused from resulting in a subsequent congestion problem at the network switch 10 which paused the sub-queue. However, if a congestion condition results at network switch 10, then the operations may be carried out as described below so that the amount of communications from the link associated with the queue or sub-queue which experiences a congestion condition may be reduced. Thus, the present invention may provide for reductions in traffic flow only through network switches which experience congestion conditions and these reductions may only propagate back to a point where a congestion condition no longer exists. Accordingly, the present invention may provide congestion control with limited impact on the overall network performance.

[0039] The determination of the stream identifier may be carried out by extracting the source and/or destination MAC address from the frame which resulted in the congestion condition. This stream identifier is then incorporated into a pause message and the pause message transmitted from the network switch 10′ which detected the congestion condition to the network switch 10 which sent the frame which resulted in the congestion condition (block 104). If no congestion condition occurs, then the network switch 10′ need not carry out the operations of blocks 102 and 104 (block 100).

[0040] FIG. 5 illustrates the operations of the network switch 10 upon receipt of the pause message from the network switch 10′. If a pause message is received (block 110), then the network switch 10 extracts the stream identifier from the pause message (block 112). As described above, this extraction may be carried out by evaluating a field in the pause message which specifies the source and/or destination MAC address of the frame which resulted in the congestion condition. The network switch 10 utilizes the extracted stream identifier to determine the sub-queue specified by the stream identifier (block 114). This determination may be made by maintaining a look-up table of unique source MAC addresses of all frames processed through each the output sub-queues 18a-18z. For example, a forwarding table which is maintained by each output port to direct traffic in the reverse-direction may be utilized. Utilizing the extracted address information, the output sub-queue associated with the address could be determined from the forwarding table to identify the sub-queue associated with the message which resulted in the congestion condition.

[0041] After determining the sub-queue specified by the stream identifier, the network switch 10 pauses that sub-queue (block 116). Thus, for example, if a frame from the input port A 12aof the network switch 10 resulted in congestion at the network switch 10′, then sub-queue 18awould be paused. A sub-queue may be paused for a predetermined duration, for a duration specified in the pause message or until a subsequent resume message is received to restart the paused sub-queue. If the congestion condition persists, then the same or a different sub-queue may be paused. Similarly, a resume message may be transmitted if it is determined that the congestion condition no longer exists.

[0042] In a further embodiment of the present invention, a receiving switch can direct a sending switch to pause transmission of data, possibly in the context of IEEE 802.3 flow control. The pause might be organized as a fraction of an interval among periodic intervals. Thus, there may be a fixed time interval, Dt, and some fraction, pi(t), of each interval Dt the sending switch must pause sending. Here pi(t) denotes the fraction of time (e.g. a fraction of Dt) to pause during the interval of time from time t to time t+Dt. The pause fraction may be calculated at the end of every time interval Dt and held constant for the subsequent time interval from time t to time t+Dt. In the event that a sub-queue is paused for a duration specified in the pause message, then the next value of the pause duration, namely pi(t+Dt) might be calculated as a function of sub-queue length, the sum of some or all sub-queue lengths, the present value pi(t) of the pause fraction, or other previous values of the pause fraction such as the previous value pi(t−Dt). For example, such a calculation of the next pause fraction pi(t+Dt) for sub-queue i might be:

[0043] pi(t+Dt)=0 if qi(t)<=T,

[0044] else

[0045] (1−k1)*pi(t)+k1*Fi(t)/Li

[0046] where qi(t) is a queue occupancy at time t, the threshold T is a queue occupancy level associated with congestion, k1 is a constant between 0 and , Li is the capacity of the link from the source port to the destination port and Fi(t) is the total offered flow over the link during the just completed time interval from t−Dt to t.

[0047] As a second example of pause fraction determination, another embodiment of the present invention may specify the pause fraction as:

[0048] pi(t+Dt)=0 if qi(t)<=T,

[0049] else

[0050] 2*pi(t)−pi(t−Dt)−k2{circumflex over ( )}2*(pi(t−Dt)−(1−Fi(t−Dt)/Li))−2*k2* (pi(t)−pi(t−Dt))

[0051] where pi(t), qi(t), T, t, t+Dt, and Li are as described above and where K2 is a constant between 0 an 1, pi(t−Dt) is the previous value of the pause fraction and Fi(t−Dt) is the previous value of the total offered flow over the link during the time interval from t−Dt to t. While two examples of the determination of a pause fraction, as will be appreciated by those of skill in the art, other determinations of the pause fraction may be utilized.

[0052] Simulations of the above-described source-port level congestion control and link level congestion control have been carried out for a 10 second time interval with an 85% traffic load and a 500 Kbyte congestion threshold for output port queues. Performance of the congestion control was measured in terms of control of buffer occupancy and link throughput. The maximum buffer occupancy results indicated that both link level and source port level congestion control managed to control buffer occupancy. Furthermore, the source port level congestion control achieved a 13% improvement in throughput over the link level congestion control.

[0053] While the present invention has been described with reference to network switches, as will be appreciated by those of skill in the art, the present invention may be applied to any network device have multiple input ports which are multiplexed onto an output port. Accordingly, as used herein, the term network switch refers to a network device which receives data at multiple input ports and provides that data to an output port for transmission over a communication link. Thus, the present invention may include in the term network switch, devices such as routers or the like.

[0054] In the drawings and specification, there have been disclosed typical preferred embodiments of the invention and, although specific terms are employed, they are used in a generic and descriptive sense only and not for purposes of limitation, the scope of the invention being set forth in the following claims.