Abstract:
A method for monitoring data congestion in a computer network with multiple nodes and for controlling data transmission in the computer network. The method includes generating a congestion notification by the node which detects a data congestion and transmitting the congestion notification to the data source which is involved in the data congestion. The method also includes generating in the data source a congestion value which indicates how severe the data congestion is, and storing in a worst case array of the data source those congestion values which indicate the most severe data congestions.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]    This application claims priority under 35 U.S.C. §119 from European Patent Application No. 07121958.8 filed Nov. 30, 2007, the entire contents of which are incorporated herein by reference. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a method for monitoring data congestion in a computer network with multiple nodes, a method for controlling the data transmission in the computer network, and a computer network using the method for monitoring and controlling data congestion. 
         [0004]    2. Description of Related Art 
         [0005]    To be able to reap the benefits of the growth in computational power it is desired that the I/O subsystem of a computer is able to deliver the data requested by the processor subsystem at the rate at which it is desired. In recent years, it has become clear that the current shared bus-based architecture will become the bottleneck of the servers that host these powerful but demanding applications. InfiniBand™ is a solution to the corresponding limitation of the current I/O subsystem. The Infiniband specification defines the architecture of the interconnection that pulls together the I/O subsystems of the next generation of servers and will even move to the powerful desktop computers of the future. The architecture of the Infiniband is based on a serial, switched fabric and provides superior latency performance and products supporting 20 Gb/s node-to-node and 60 Gb/s switch-to-switch connections. Additionally, it resolves the scalability, expandability, and fault tolerance limitations of the shared bus architecture through the use of switches and routers in the construction of its fabric. Infiniband provides reliable end-to-end data connections and defines this capability to be implemented in hardware. In addition, Infiniband facilitates the deployment of virtualization solutions, which allow multiple applications to run on the same interconnect with dedicated application partitions. As a result, multiple applications run concurrently over stable connections, thereby minimizing downtime. Infiniband fabrics are typically constructed with multiple levels of redundancy in mind so if a link goes down, not only should the fault be limited to the link, but also an additional link can automatically be failed over to ensure that connectivity continues throughout the fabric. Creating multiple paths through the fabric results in intra-fabric redundancy and further contributes to the reliability of the fabric. Infiniband reference: http://www.infinibandta.org/home, Sep. 2, 2008. 
       SUMMARY OF THE INVENTION 
       [0006]    An object of the invention is to provide a method for monitoring data congestion in a computer network, a method for controlling the data transmission in the computer network, a computer network using the method for monitoring and/or controlling data congestion, and a computer readable article of manufacture tangibly embodying computer readable instructions for executing the method. 
         [0007]    According to one aspect of the invention, the object is achieved by a method for monitoring data congestion in a computer network with the features described. The method for monitoring data congestion in a computer network having multiple nodes and at least one data source includes the following steps: detecting the presence of a data congestion by a node; generating a congestion notification by the node which detects the data congestion in response to the detecting; transmitting the congestion notification to the data source; generating in the data source a congestion value for the data congestion where the value indicates the level of the data congestion; and storing at least one congestion value in a worst case array in a memory associated with the data source. 
         [0008]    The level of the data congestion may in particular indicate how severe the data congestion is. A predetermined subset of the congestion values may include in particular those congestion values which indicate the most severe data congestions. 
         [0009]    The method for controlling the data transmission in the computer network includes besides the above mentioned steps, the following step: the congestion value is used to enable the data transmission. 
         [0010]    In the computer network with multiple nodes using the method for monitoring data congestion the nodes are designed such that they are able to generate a congestion notification, when a data congestion occurs. 
         [0011]    Preferred embodiments of the invention arise from the characteristics indicated in the following. The method for monitoring data congestion in a computer network having multiple nodes includes the following steps: storing the congestion value in a first array in the memory when the data congestion has occurred in a data line; and storing the congestion value in a second array in the memory when the data congestion has occurred in a logical partition. 
         [0012]    Furthermore, the method according to the invention can include the following step: increasing the congestion value, if within a timeout period a further congestion notification arrives. 
         [0013]    Additionally, it can be provided in the method according to the invention that the congestion value is decreased, if within the timeout period no further congestion notification arrives. 
         [0014]    In another embodiment of the method according to the invention the timeout period is increased, if within the timeout period a further congestion notification arrives. 
         [0015]    In a further embodiment of the method according to the invention the timeout period is decreased, if within the timeout period no further congestion notification arrives. 
         [0016]    Furthermore, the method according to the invention can include the following step: replacing the smallest congestion value in the worst case array by a new congestion value if the new congestion value is higher than the smallest congestion value. 
         [0017]    In the method according to the invention a predetermined number of congestion values, for example, 16 congestion values, can be stored in the worst case array. 
         [0018]    Additionally, it can be provided in the method according to the invention that the data transmission is enabled, if the congestion value drops below a threshold. 
         [0019]    Advantageously, in the computer network the nodes have memory for storing the congestion values. Additionally, the nodes in the computer network can be provided with memory for storing timeout period values. Also, one or more nodes in the computer network can be a router. 
         [0020]    Further, the invention includes a computer readable article of manufacture tangibly embodying computer readable instructions for executing a computer implemented method for monitoring data congestion in a computer network with multiple nodes and at least one data source. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0021]    The invention and its embodiments will be more fully appreciated by reference to the following detailed description of presently preferred but nonetheless illustrative embodiments in accordance with the present invention when taken in conjunction with the accompanying drawings: 
           [0022]      FIG. 1  is a block diagram of an example of an Infiniband network; 
           [0023]      FIG. 2  is a block diagram of a network interface with a number of virtual network interfaces; 
           [0024]      FIG. 3  is a row array and a column array for storing congestion values and timeout values; 
           [0025]      FIG. 4  is a diagram with congestion notifications and congestion values and the storage of those congestion values in a worst case array, which represent the most serious congestions; 
           [0026]      FIG. 5  is a flow diagram, which shows what happens, when a congestion notification arrives at a network node; and 
           [0027]      FIG. 6  is a flow diagram showing what happens, when a data packet is transmitted. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0028]    The method according to the invention provides a computer or a virtual machine with information about how long it has to wait to get the permission for sending data via the network to a determined receiver. 
         [0029]      FIG. 1  shows a block diagram of an example of an Infiniband network. In order to be able to explain the function mode simply, a simple example was selected. The network comprises a first network interface NWI 1 , a second network interface NWI 2 , a third network interface NWI 3 , a fourth network interface NWI 4 , four routers R 1  to R 4  and communication lines L 1  to L 7 . In the following the communication lines are also called physical communication lines, data lines or in short lines. In the example according to  FIG. 1  only network interface NWI 3  is depicted with ports P 1  and P 2 , but in general, each of the network interfaces NWI 1  to NWI 4  may have two physical ports. With that network structure the redundancy and reliability can be increased. 
         [0030]    Each of the network interfaces NWI 1  to NWI 4  can communicate with each other via the routers R 1  to R 4  and the communication lines L 1  to L 7 . If for example, the network interface NWI 1  is required to transmit data packets to the network interface NWI 2 , the data packets are transmitted from network interface NWI 1  via communication line L 1 , router R 1 , communication line L 2 , router R 2  and communication line L 3  to the network interface NWI 2 . Also, if port P 1  of network interface NWI 3  is required to transmit data packets to the network interface NWI 2 , the data packets are transmitted from port P 1  of network interface NWI 3  via communication line L 4 , router R 3 , communication line L 6 , router R 2  and communication line L 3  to the network interface NWI 2 . In case both network interfaces NWI 1  and NWI 3  are required to transmit data packets at the same time to network interface NWI 2  with high data rates and the communication line L 3  is not designed to handle such a high data rate, a data congestion can appear at communication line L 3 . This congestion may lead to a data backlog on router R 2 , communication line L 2 , router R 1 , communication line L 1 , network interface NWI 1 , communication line L 6 , router R 3 , communication line L 4  and network interface NWI 3 . The data backlog in router R 3  can also lead to a congestion in a network interface which uses one of the components which are involved in the congestion. This can happen for example, if network interface NWI 4  is required to transmit data packets via router R 3 . 
         [0031]    A possibility for dissolving the data congestion on communication line L 3  is to restrict the data stream or the data streams respectively, which are scheduled to be transmitted via communication line L 3 , so much that communication line L 3  no longer forms the bottleneck for the data transfer. Therefore, router R 2  can advise the data sources, that the network interfaces NWI 1  and NWI 3  are to reduce their transmission rate. In the following, the feedback from the unit which detects the data congestion to the data source or sources which are involved in the congestion, is called backward explicit congestion notification (BECN), or for short, congestion notification (CN). 
         [0032]    Virtualization: 
         [0033]    Virtualization means that one physical computer can include, for example, 256 virtual machines, where on each of the virtual machines an independent application can run. With that, the workload of the physical computer can be increased. Furthermore, the staff can handle the system more easily, because there are fewer physical computers. The virtualization concerns also the network interfaces NW 1  to NW 4 . This means, that one physical or real network interface can comprise for example 256 virtual network interfaces. For example, network interface NWI 3  can comprise 256 virtual network interfaces VNWI 1  to VNWI 256  as it is depicted in the block diagram of  FIG. 2 . In the example of  FIG. 2 , the virtual network interfaces are also called logical network interfaces. Each of the virtual network interfaces is assigned a separate address and all virtual network interfaces are independent of another. This means, that the virtual machines are really independent from another. In the following, the virtual machines are also called virtual partitions or logical partitions LPAR. 
         [0034]    In the example of  FIG. 2 , the first  128  virtual network interfaces VNWI 1  to VNW 128  are connected to the first physical port P 1  and the second 128 virtual network interfaces VNWI 129  to VNW 256  are connected to the second physical port P 2 . 
         [0035]    Each of the physical communication lines L 1  to L 7  of the network comprises several virtual lanes VL. For example the physical communication line L 1  may comprise 16 virtual lanes VL 1  to VL 16 . Each virtual lane VL 1  to VL 16  in turn can transmit a separate data stream, wherein the data streams are independent from another. This has the advantage, that although if one of the virtual data lanes is fully engaged, data traffic can take place on the remaining virtual data lanes. 
         [0036]    As already mentioned, one network interface has 2 ports, and each port, i.e., each physical line, has 16 virtual lanes. This means that with 256 virtual machines, 2×16×256=8192 congestion management entries (CME) have to be handled. Each congestion management entry comprises a congestion memory with, for example, 40 bits storing a congestion value CV, which indicates the extent or level of the data congestion. In case a backward explicit congestion notification BECN occurs, the congestion value CV in the congestion memory is increased by one. After a certain timeout T the congestion value CV in the congestion memory is decreased by one, if no further backward explicit congestion notification BECN occurs within the timeout. 
         [0037]    In the above example the entire congestion memory has a total size of 8192×40 bits=320 kbit or 40 kByte. Because of the high data rate the congestion memory should be embedded on the network interface chip rather than on a separate chip. 
         [0038]    For downsizing the congestion memory, only the worst or most serious congestion is notified back to the data source or sources that are involved in the congestion by a backward explicit congestion notification BECN. 
         [0039]    Congestion Management: 
         [0040]    As depicted in  FIG. 3 , a column array CA is provided, in which for each logical partition LPAR the corresponding timeout value or timeout period T and congestion value CV is stored. In the example of  FIG. 3  it is stored in the column array CA that the logical partition LPAR  40  has a timeout T=20 and a congestion value CV=4. Whereas the logical partition LPAR  201  has a timeout T=120 and a congestion value CV=200. 
         [0041]    The column array CA has the following semantic: 
         [0042]    CA=[(LPAR 1 , T, CV), (LPAR 2 , T, CV), . . . (LPAR 256 , T, CV)] 
         [0043]    In the example of  FIG. 3  the column array CA has the following entries: 
         [0044]    CA=[ . . . (40, 20, 4) . . . (201, 120, 200)] 
         [0045]    Furthermore, as depicted in  FIG. 3 , a row array RA is provided, in which for each port P and each virtual lane VL the corresponding timeout T and congestion value CV is stored. In the example of  FIG. 3  it is stored in the row array RA that the virtual lane VL 16  of port P 1  has a timeout T=10 and a congestion value CV=8. The virtual lane VL 1  of port P 2  however has a timeout T=60 and a congestion value CV=1. 
         [0046]    The row array RA has the following semantic: 
         [0047]    RA=[(P 1 VL 1 , T, CV), (P 1 VL 2 , T, CV), . . . (P 1 VL 16 , T, CV), (P 2 VL 1 , T, CV), (P 2 VL 2 , T, CV), . . . (P 2 VL 16 , T, CV)] 
         [0048]    In the example of  FIG. 3  the row array RA has the following entries: 
         [0049]    RA=[ . . . (P 1 VL 16 , 10, 8) . . . (P 2 VL 1 , 60, 1) . . . ] 
         [0050]    From the column array CA and the row array RA the worst  16  congestion entries are transferred to a worst case array WCA. 
         [0051]    The worst 16 congestion values are depicted in the diagram of  FIG. 4 . 
         [0052]    In the example of  FIG. 4 , it is explained by the flow diagram shown in  FIG. 5  what happens if a new backward explicit congestion notification BECN arrives. If a new backward explicit congestion notification BECN arrives step S 1  (S 1 ), it is checked whether an entry already exists in the worst case array WCA step S 2  (S 2 ). If an entry exists in the worst case array WCA, this entry is updated in the worst case array WCA. If for example the entry CN 11  is concerned, the congestion value CV is updated which is indicated in  FIG. 4  by reference label B. Otherwise, it is checked in step S 4 , whether the update will promote a new entry into the worst case array WCA. If this is not the case, the entries (timeout T and congestion value CV) in the row array RA and the column array CA are updated in step S 5 . Otherwise, the entry in the worst case array WCA is updated in step S 6  and the entry is inserted into the worst case array S 7 . 
         [0053]    In the following it is described by means of three exemplary cases A, B and C what happens, if a new BECN arrives.  FIG. 4 , case A: A new backward explicit congestion notification BECN called congestion notification CN 32  arrives. In step S 2  it is checked, whether for the congestion notification CN 32  an entry already exists in the worst case array WCA (S 2 ). As there is no entry for the congestion notification CN 32  in the worst case array WCA, step S 4  is executed. Because the congestion value CV of the congestion notification CN 32  is smaller than 16 other congestion values CV, the congestion value CV of the congestion notification CN 32  will not be entered in the worst case array WCA. Therefore, step S 5  is processed. The entries (timeout T, congestion value CV) in the row array RA and the column array CA will be updated. 
         [0054]      FIG. 4 , case B: A new backward explicit congestion notification BECN called congestion notification CN 12  arrives. In step S 2  it is checked, whether for the congestion notification CN 12  an entry already exists in the worst case array WCA (S 2 ). As there already an entry for the congestion notification CN 12  in the worst case array WCA, step S 3  is executed. The entry (timeout T, congestion value CV) worst case array WCA will be updated. 
         [0055]      FIG. 4 , case C: A new backward explicit congestion notification BECN called congestion notification CN 40  arrives. In step S 2  it is checked, whether for the congestion notification CN 40  an entry already exists in the worst case array WCA (S 2 ). As there is no entry for the congestion notification CN 40  in the worst case array WCA, step S 4  is executed. Because the congestion value CV of the congestion notification CN 32  is higher than the smallest of the 16 highest congestion values CV, the congestion value CV of the congestion notification CN 32  will be entered in the worst case array WCA. Therefore, step S 6  is processed. The row and column for the best WCA entry will be updated, and in step S 7  the entry (timeout T, congestion value CV) is inserted into the worst case array WCA. 
         [0056]    In the following it is explained by means of the flow diagram shown in  FIG. 6  what happens if a data packet should be transmitted in the network step S 10 (S 10 ). First, it is checked in step S 11  whether there is an entry in the worst case array WCA. If this is not the case, the row and column entry is processed in step S 12 . Otherwise the entry in the worst case array WCA is processed in step S 13 . After performing steps S 12  and S 13  respectively, it is checked in step S 14 , whether the time delay is elapsed. If yes, the data packet is sent step S 15 (S 15 ). 
         [0057]    The method according to the invention can be used as a hypervisor, for instance, as a virtual machine monitor. 
         [0058]    While the present invention has been described with reference to what are presently considered to be the preferred embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. On the contrary, the invention is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims. The scope of the following claims is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structures and functions.