Abstract:
A switch device includes a plurality of ports respectively including a queue and transmits a flow including packets; and a processor configured to detect congestion in one of the plurality of ports, based on an amount of packets stored in the queues, receive, from another switch device, congestion information relating to the another switch device, specify a port coupled to a link where the congestion is not occurred, the link being one of a plurality of links coupled to the another switch device, based on the congestion information received from the another switch device, extract a target flow to which no packet stored in a queue of the specified port, from among a plurality of flows scheduled to be transmitted from the port in which the congestion is detected, and transmit a plurality of packets included in the extracted target flow from the specified port to the another switch device.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2015-046413, filed on Mar. 9, 2015, the entire contents of which are incorporated herein by reference. 
       FIELD 
       [0002]    The embodiments discussed herein are related to a switch device, a control method, and a storage medium. 
       BACKGROUND 
       [0003]    In an information processing system constructed by connecting information processing devices by using switches, link aggregation (LAG) is used as a redundancy technology for a layer 2.  FIG. 24  is a diagram for explaining LAG. In  FIG. 24 , 4 information processing devices  2  indicated by S#0 to S#3 are connected by 2 switches  90  indicated by Switch#0 and Switch#1. 
         [0004]    While the 2 switches  90  are connected by 4 physical links  90   a , the 4 physical links  90   a  are regarded as one logical link in LAG. Since all paths between layer 2 switches (L2 switches) that support LAG are handled as active paths (paths capable of performing communication), the switches are able to effectively utilize paths. Furthermore, failover based on a detour path (backup) is available at the time of cable disconnection, and availability is improved. 
         [0005]    Since order reversal of packets occurs, a simple round-robin method (in units of packets) is not appropriate as an algorithm for selecting paths. Usually, a hash value is calculated based on information of packets, such as an internet protocol (IP) address or a media access control (MAC) address, thereby selecting, based on the hash value, a physical link serving as a delivery destination of packets. Since, from this, a traffic is distributed in units of flows, no order inversion occurs. However, it is known that path selection becomes easy to be influenced by unevenness of a traffic for each of flows as the number of physical lines increases. 
         [0006]    In LAG, there is a technology in which hash values and priorities of reception packets are held and output destinations of the reception packets are controlled based on the hash values, the priorities, and buffering states of the reception packets, thereby distributing the packets in units of flows without changing the order thereof (see, for example, Japanese Laid-open Patent Publication No. 2012-205048). 
         [0007]    There is a technology for extending a band control rate per LAG group to the total rate of physical bands of all links configuring LAG groups even in a case where the LAG groups are formed across line cards (see, for example, Japanese Laid-open Patent Publication No. 2009-200905). 
         [0008]    In LAG, there is a problem that if a path is changed in a case where unevenness of a traffic causes congestion to occur in the path, order reversal of packets occurs. The order reversal of packets causes performance deterioration of a transmission control protocol (TCP). Therefore, in a case where the congestion occur, it is desirable to avoid the order reversal of packets due to a detour and to be able to perform efficient detour control. 
       SUMMARY 
       [0009]    According to an aspect of the invention, a switch device includes a plurality of ports respectively including a queue and transmits a flow including packets; and a processor configured to detect congestion in one of the plurality of ports, based on an amount of packets stored in the queues, receive, from another switch device, congestion information relating to the another switch device, specify, from among the plurality of ports, a port coupled to a link where the congestion is not occurred, the link being one of a plurality of links coupled to the another switch device, based on the congestion information received from the another switch device, extract a target flow to which no packet stored in a queue of the specified port, from among a plurality of flows scheduled to be transmitted from the port in which the congestion is detected, and transmit a plurality of packets included in the extracted target flow from the specified port to the another switch device. 
         [0010]    The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
         [0011]    It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0012]      FIG. 1  is a diagram for explaining path changing based on a switch according to a first embodiment; 
           [0013]      FIG. 2  is a diagram illustrating a configuration of the switch according to the first embodiment; 
           [0014]      FIG. 3  is a diagram for explaining detection and notification of a congestion state, based on a congestion detection notification unit; 
           [0015]      FIG. 4  is a diagram for explaining a flow group counter; 
           [0016]      FIG. 5  is a diagram for explaining determination of whether or not a detour path is usable; 
           [0017]      FIG. 6  is a diagram for explaining selection of a flow to be detoured; 
           [0018]      FIG. 7  is a diagram for explaining recording of a flow to be detoured; 
           [0019]      FIG. 8  is a diagram for explaining detour cancellation determination at the time of releasing a congestion state; 
           [0020]      FIG. 9  is a flowchart illustrating a flow of processing in a case where a switch receives a packet; 
           [0021]      FIG. 10  is a flowchart illustrating a flow of processing for selection of a detour flow based on an LAG traffic control unit; 
           [0022]      FIG. 11  is a flowchart illustrating a flow of processing for flow detour cancellation based on the LAG traffic control unit; 
           [0023]      FIG. 12  is a diagram for explaining MLAG; 
           [0024]      FIG. 13  is a diagram for explaining path changing based on switches according to a second embodiment; 
           [0025]      FIG. 14  is a diagram illustrating configurations of switches according to the second embodiment; 
           [0026]      FIG. 15  is a diagram illustrating a control message between spines; 
           [0027]      FIG. 16  is a diagram for explaining determination of whether or not a detour path is usable; 
           [0028]      FIG. 17  is a diagram for explaining recording of a flow to be detoured; 
           [0029]      FIG. 18  is a flowchart illustrating a flow of transmission processing for a control message; 
           [0030]      FIG. 19  is a flowchart illustrating a flow of reception processing for a control message; 
           [0031]      FIG. 20  is a flowchart illustrating a flow of processing for selection of a detour flow based on an LAG traffic control unit according to the second embodiment; 
           [0032]      FIG. 21  is a diagram for explaining path changing based on a switch according to a third embodiment; 
           [0033]      FIG. 22A  is a first flowchart illustrating a flow of processing for selection of a detour flow based on an LAG traffic control unit according to the third embodiment; 
           [0034]      FIG. 22B  is a second flowchart illustrating a flow of processing for selection of a detour flow based on the LAG traffic control unit according to the third embodiment; 
           [0035]      FIG. 23  is a flowchart illustrating a flow of processing for flow detour cancellation based on the LAG traffic control unit according to the third embodiment; and 
           [0036]      FIG. 24  is a diagram for explaining LAG. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0037]    Hereinafter, embodiments of an information processing system, a switch device, and a control method for an information processing system, disclosed in the present application, will be described in detail, based on drawings. The embodiments do not limit the disclosed technology. 
       First Embodiment 
       [0038]    First, path changing based on a switch according to a first embodiment will be described.  FIG. 1  is a diagram for explaining the path changing based on the switch according to the first embodiment. As illustrated in  FIG. 1 , an information processing system  1  according to the first embodiment includes 4 information processing devices  2  indicated by S#0 to S#3 and 2 switches  10  indicated by Switch#0 and Switch#1. In addition, in the information processing system  1 , the 4 information processing devices  2  are connected by the 2 switches  10 . The information processing devices  2  are devices that each perform information processing. The switches  10  are devices that each relay communication between the information processing devices. 
         [0039]    The switches  10  each include 6 respective ports indicated by P#0 to P#5. P#0 and P#1 are connected to the respective information processing devices  2 . P#2 to P#5 are connected to the other switch  10 . The 2 switches  10  are connected by 4 physical links  10   a  by using P#2 to P#5. However, based on LAG, the 2 switches  10  are connected by one logical link. While, in  FIG. 1 , for convenience of explanation, the 4 physical links  10   a  configure one logical link, more physical links  10   a  may configure LAG. 
         [0040]    Upon detecting a congestion state, Switch#0 selects a candidate for a detour destination, based on, for example, usage rates of paths of other ports. In addition, Switch#0 confirms that the candidate for a detour destination is not congested, and Switch#0 selects, as the detour destination, the candidate for the detour destination. In addition, Switch#0 selects, based on queue information of a detour source, a flow whose path is to be changed, and Switch#0 changes a path of the selected flow from the detour source to the detour destination. If the congestion state of the detour source is released, Switch#0 confirms queue information of the detour destination and restores the path of the detoured flow to an original path. 
         [0041]    In  FIG. 1 , a congestion state is detected in P#5, and the path of a flow selected from among flows whose packets are transmitted from P#5 is changed to a detour destination. In addition, if the congestion state of P#5 is released, the path of the flow, changed to the detour destination, is restored to the path of P#5. 
         [0042]    Next, configurations of the switches  10  according to the first embodiment will be described.  FIG. 2  is a diagram illustrating the configurations of the switches according to the first embodiment. As illustrated in  FIG. 2 , the switches  10  each include a receiving port  11   a  represented by a receiving port inter switch link (ISL) and  32  receiving ports  11   b  represented by a receiving port #0 to a receiving port #31. The switches  10  each include a transmitting port  12   a  represented by a transmitting port ISL and 32 transmitting ports  12   b  represented by a transmitting port #0 to a transmitting port #31. The switches  10  each include a central processing unit (CPU)  13 , a memory  14 , and a switching module  20 . 
         [0043]    The receiving port  11   a  is a port that receives packets transmitted from another spine via ISL in a case where the corresponding switch  10  is used as a spine of multi-chassis LAG (MLAG). MLAG and the spine will be described in a second embodiment. Each of the receiving ports  11   b  is a port that receives packets transmitted by the connected information processing device  2  or switch  10 . 
         [0044]    The transmitting port  12   a  is a port that transmits packets to another spine in a case where the corresponding switch  10  is used as a spine of MLAG. Each of the transmitting ports  12   b  is a port that transmits packets to the connected information processing device  2  or the other switch  10 . The transmitting port  12   a  and the transmitting ports  12   b  each include an output queue  12   c . The output queue  12   c  is a queue that stores therein packets output by the corresponding switch  10 . 
         [0045]    The CPU  13  is a central processing unit that reads and executes a program from the memory  14 . By executing the program, the CPU  13  realizes a function of an LAG traffic control unit  31 . Based on congestion information of the transmitting ports  12   b  and storage states of the output queues  12   c , the LAG traffic control unit  31  controls paths of traffics. Details of the LAG traffic control unit  31  will be described later. The memory  14  is a random access memory (RAM) that stores therein the program, an intermediate result of program execution, and so forth. 
         [0046]    Based on destinations of packets received by the receiving port  11   a  and the receiving ports  11   b , the switching module  20  distributes the packets into the transmitting port  12   a  and the transmitting ports  12   b . The switching module  20  includes a packet reception unit  21 , a forwarding database (FDB) storage unit  22 , an FDB control unit  23 , a hash calculation unit  24 , and a packet distribution unit  25 . The switching module  20  further includes a congestion detection notification unit  26 , a local congestion vector  27 , a flow group counter  28 , and a local flow vector  29 . 
         [0047]    The packet reception unit  21  receives packets received by the receiving port  11   a  and the receiving ports  11   b . The FDB storage unit  22  stores therein a database for searching, from destinations of packets, for logical ports from which the packets are output. The FDB storage unit  22  stores therein correspondences between MAC addresses, VLAN numbers, and logical port numbers. The FDB control unit  23  searches FDB stored by the FDB storage unit  22  and acquires logical ports from which packets are output. In the following description, it is assumed that the 32 transmitting ports  12   b  correspond to one logical transmitting port based on LAG and are connected to the 32 respective receiving ports  11   b  of the other switch  10  by using the respective physical links  10   a.    
         [0048]    The hash calculation unit  24  calculated a hash value of a packet from 5 tuples. Here, the 5 tuples are a transmission source IP address, a transmission destination IP address, a transmission source port number, a destination port number, and a protocol. The packet distribution unit  25  maps, to the transmitting ports  12   b , a hash value calculated by the hash calculation unit  24 , thereby distributing a packet to be transmitted to one of the transmitting ports  12   b.    
         [0049]    The congestion detection notification unit  26  detects congestion states of the transmitting ports  12   b , notifies the LAG traffic control unit  31  thereof, and sets the local congestion vector  27 . The local congestion vector  27  stores therein a congestion state for each of the transmitting ports  12   b . If one of the transmitting ports  12   b  is put into a congestion state, a corresponding bit of the local congestion vector  27  is set to “1”. 
         [0050]      FIG. 3  is a diagram for explaining detection and notification of a congestion state, based on the congestion detection notification unit  26 . As illustrated in  FIG. 3 , the transmitting ports  12   b  each include a queue length counter  12   d  that counts the length of the output queue  12   c , in addition to the output queue  12   c . If a packet is input to the output queue  12   c , the queue length counter  12   d  is incremented. If a packet is output from the output queue  12   c , the queue length counter  12   d  is decremented. 
         [0051]    For each of the transmitting ports  12   b , the congestion detection notification unit  26  stores therein a congestion threshold value  26   a  indicating a threshold value of congestion detection and includes a comparison unit  26   b  that compares the value of the corresponding queue length counter  12   d  with the congestion threshold value  26   a . In addition, if the queue length of the corresponding output queue  12   c  exceeds, based on a comparison result of the comparison unit  26   b , the congestion threshold value  26   a , the congestion detection notification unit  26  sets a corresponding bit of the local congestion vector  27  to “1”. In a case where the queue length of the corresponding output queue  12   c  exceeds the congestion threshold value  26   a  and a TCP session request is received, the congestion detection notification unit  26  notifies the LAG traffic control unit  31  of congestion detection along with a port number and a hash value. 
         [0052]    If a congestion state is released, the congestion detection notification unit  26  notifies the LAG traffic control unit  31  of congestion release and sets a corresponding bit of the local congestion vector  27  to “0”. 
         [0053]    The flow group counter  28  is a counter that counts the number of packets that are included in the corresponding output queue  12   c  and that belong to a flow group (flow set) into which flows sharing a common hash value are grouped.  FIG. 4  is a diagram for explaining the flow group counter  28 . As illustrated in  FIG. 4 , the flow group counter  28  includes an entry for each of flow groups. In  FIG. 4 , the flow group counter  28  includes 256 entries of a group counter #0 to a group counter #255. 
         [0054]    Based on a lower 8 bits of a hash value calculated from the 5 tuples of a packet, a flow is grouped. In addition, if a packet is input to one of the output queues  12   c , the corresponding group counter #n (0≦n≦255) is incremented. If a packet is output from one of the output queues  12   c , the corresponding group counter #n is decremented. 
         [0055]    In  FIG. 4 , the number of the output queues  12   c  and the number of entries of the flow group counter  28  have a 1-to-256 relationship. However, the number of the output queues  12   c  and the number of entries of the flow group counter  28  may have an M-to-N relationship in which M and N are integers. While, in  FIG. 4 , the value of the counter is increased or decreased based on the number of packets, the value of the counter may be increased or decreased based on a packet length. As illustrated in  FIG. 7 , described later, the flow group counter  28  includes bits, which each indicate whether or not a flow group is detoured, and port numbers of detour destinations while associating the bits and the port numbers of detour destinations with respective entries. 
         [0056]    The local flow vector  29  is a vector of 256 bits indicating a state of the flow group counter  28 . A bit n of the local flow vector  29  is set to “0” in a case where a value of the group counter #n is “0”, and the bit n of the local flow vector  29  is set to “1” in a case where the value of the group counter #n is a value other than “0”. In other words, that the bit n of the local flow vector  29  is “0” indicates that no packet belonging to a corresponding flow group exists in the output queue  12   c.    
         [0057]    Next, details of the LAG traffic control unit  31  will be described. The LAG traffic control unit  31  performs determination of whether or not a detour path is usable, selection of a flow to be detoured, recording of a flow to be detoured, and detour cancellation determination at the time of releasing a congestion state. 
         [0058]      FIG. 5  is a diagram for explaining determination of whether or not a detour path is usable. The LAG traffic control unit  31  confirms a congestion state of a detour path by using the local congestion vector  27  and determines whether or not the detour path is usable. The LAG traffic control unit  31  generates a 32-bit CV mask vector indicating another transmitting port  12   b  to be used as a detour path. The LAG traffic control unit  31  obtains AND of the local congestion vector  27  and the mask vector and in a case of all “0s”, the LAG traffic control unit  31  determines that the detour path is usable. 
         [0059]      FIG. 6  is a diagram for explaining selection of a flow to be detoured. As illustrated in  FIG. 6 , by using the local flow vector  29 , the LAG traffic control unit  31  selects, as a flow to be detoured, a flow whose packet is not queued in the corresponding output queue  12   c.    
         [0060]    Specifically, for a TCP flow whose session is newly initiated, the LAG traffic control unit  31  generates an FV mask vector of 256 bits, based on the lower 8 bits of a hash value calculated from 5 tuples of a SYN packet. In addition, the LAG traffic control unit  31  obtains AND of the local flow vector  29  and the FV mask vector. As a result, in a case of all “0s”, the LAG traffic control unit  31  selects, as a flow to be detoured, a flow included in a flow group corresponding to the lower 8 bits of the hash value. 
         [0061]    By detouring in this way while targeting the TCP flow whose session is newly initiated, the LAG traffic control unit  31  is able to avoid reversal of the reception order of packets without increasing a load of the CPU. The LAG traffic control unit  31  does not detour a flow of a flow group already queued in the corresponding output queue  12   c  and detours a flow of a flow group not queued. Accordingly, the LAG traffic control unit  31  is able to inhibit reversal of the reception order of packets from occurring in a flow that belongs to a detoured flow group and that is excluded from the TCP flow whose session is newly initiated, and it is possible to perform efficient detour control. 
         [0062]      FIG. 7  is a diagram for explaining recording of a flow to be detoured. As illustrated in  FIG. 7 , upon selecting a flow group to be detoured, the LAG traffic control unit  31  records information for detouring in a corresponding entry of the flow group counter  28 . Specifically, the LAG traffic control unit  31  sets, to “1”, a bit indicating a detour and records the port number of a detour destination. In, for example,  FIG. 7 , a flow belonging to a flow group corresponding to the group counter #0 is detoured, and the detour destination is the transmitting port #2. After that, packets belonging to the flow included in the detoured flow group are detoured. 
         [0063]      FIG. 8  is a diagram for explaining detour cancellation determination at the time of releasing a congestion state. As illustrated in  FIG. 8 , after confirming, by using the local flow vector  29 , a free space of the output queue  12   c  in the transmitting port  12   b  serving as a detour destination, the LAG traffic control unit  31  cancels detouring for a detoured flow. Specifically, the LAG traffic control unit  31  generates an FV mask vector of 256 bits in which a bit corresponding to a detoured flow group is set to “1”. The LAG traffic control unit  31  obtains AND of the local flow vector  29  and the FV mask vector. In a case of all “0s”, the LAG traffic control unit  31  determines that it is possible to cancel detouring. 
         [0064]    Next, a flow of processing in a case where the switch  10  receives a packet will be described.  FIG. 9  is a flowchart illustrating the flow of the processing in a case where the switch  10  receives a packet. As illustrated in  FIG. 9 , the packet reception unit  21  determines whether or not a packet is received (S 1 ). In a case of determining that no packet is received, the packet reception unit  21  waits for a packet to be received. 
         [0065]    On the other hand, in a case of reception, the FDB control unit  23  searches FDB by using a destination MAC address and identifies a logical port to transmit packets (a logical port corresponding to LAG configured by one or more physical ports) (S 2 ). In addition, the hash calculation unit  24  performs hash calculation by using 5 tuples of a packet (S 3 ), and based on a hash value, the packet distribution unit  25  identifies one of the transmitting ports  12   b  (a physical port to transmit the packet) (S 4 ). 
         [0066]    In addition, the congestion detection notification unit  26  determines whether the transmitting port  12   b  is congested (S 5 ), and in a case of being determined as not congested, the congestion detection notification unit  26  shifts control to S 9 . On the other hand, in a case of being congested, the congestion detection notification unit  26  determines whether or not being an overlay network (S 6 ). In a case of being determined as the overlay network, an original TCP frame is encapsulated by an outer header of UDP. Therefore, since it is difficult to determine whether or not the packet is a TCP connection request, the congestion detection notification unit  26  shifts control to S 9 . 
         [0067]    On the other hand, in a case of being determined as not the overlay network, the congestion detection notification unit  26  determines whether or not the packet is the TCP connection request (S 7 ), and in a case of being determined as not the TCP connection request, the processing proceeds to S 9 . On the other hand, in a case of the TCP connection request, the congestion detection notification unit  26  sends a congestion detection notification (the number of the congested transmitting port  12   b  and the hash value of the packet) to the LAG traffic control unit  31  (S 8 ). 
         [0068]    In addition, the packet distribution unit  25  references detour information of the flow group counter  28 , which corresponds to the hash value, and determines whether or not being a flow to be detoured (S 9 ). In a case of being determined as a flow to be detoured, the packet distribution unit  25  changes a detour path to the transmitting port  12   b  (S 10 ), and in a case of being determined as not a flow to be detoured, the packet distribution unit  25  proceeds to S 11 . 
         [0069]    In addition, the packet distribution unit  25  increments a group counter in the flow group counter  28 , which corresponds to the transmitting port  12   b , (S 11 ) and puts the packet in the output queue  12   c  of the transmitting port  12   b  (S 12 ). In addition, the transmitting port  12   b  extracts a packet from the output queue  12   c  (S 13 ) and decrements the group counter in the flow group counter  28 , which corresponds to the transmitting port  12   b  (S 14 ). In addition, the transmitting port  12   b  transmits the packet from the transmitting port  12   b  (S 15 ). 
         [0070]    In this way, the congestion detection notification unit  26  transmits a congestion detection notification to the LAG traffic control unit  31  in a case where the packet is the TCP connection request. Accordingly, the switch  10  is able to detour a packet at a timing when a new flow is generated. 
         [0071]    Next, a flow of processing for selection of a detour flow based on the LAG traffic control unit  31  will be described.  FIG. 10  is a flowchart illustrating the flow of processing for selection of a detour flow based on the LAG traffic control unit  31 . As illustrated in  FIG. 10 , the LAG traffic control unit  31  determines whether or not a congestion detection notification is received from the congestion detection notification unit  26  (S 21 ). In a case of being determined as not received, the LAG traffic control unit  31  waits for a congestion detection notification to be received. 
         [0072]    On the other hand, in a case of being received, the LAG traffic control unit  31  determines whether or not there is another transmitting port  12   b  to serve as a candidate for a detour path (S 22 ). As an example of a case where there is no candidate for a detour path, there is, for example, a case where all the other transmitting ports  12   b  belonging to the same LAG are subjected to “link down”. In a case where it is determined that there is no other transmitting port  12   b  to serve as a candidate for a detour path, the LAG traffic control unit  31  returns to S 21  and waits for a subsequent congestion detection notification to be received. 
         [0073]    On the other hand, in a case where it is determined that there is the other transmitting port  12   b  to serve as a candidate for a detour path, the LAG traffic control unit  31  sets, to “1”, a bit that corresponds to the detour path and that is included in bits of the CV mask vector (S 23 ). In addition, the LAG traffic control unit  31  obtains bitwise AND of the CV mask vector and the local congestion vector  27  of the detour path (S 24 ) and determines whether or not an operation result is “All 0s” (S 25 ). In a case of being determined as not “All 0s”, the LAG traffic control unit  31  returns to S 21  and waits for a subsequent congestion detection notification to be received. 
         [0074]    On the other hand, in a case of being determined as “All 0s”, the LAG traffic control unit  31  sets, to “1”, a bit that is included in bits of the FV mask vector and that corresponds to a flow group to which a target flow to serve as a target of detouring belongs (S 26 ). In addition, the LAG traffic control unit  31  obtains bitwise AND of the FV mask vector and the local flow vector  29  of the detour source transmitting port  12   b  (S 27 ) and determines whether or not an operation result is “All 0s” (S 28 ). 
         [0075]    In a case of being determined as “All 0s”, the LAG traffic control unit  31  records, as a flow to be detoured, the target flow in a corresponding entry of the flow group counter  28  (S 29 ) and returns to S 21 . On the other hand, in a case where it is determined that the operation result is not “All 0s”, the LAG traffic control unit  31  waits for a predetermined time period (S 30 ) and determines whether or not the predetermined number of times is reached (S 31 ). 
         [0076]    In a case where it is determined that the predetermined number of times is not reached, the LAG traffic control unit  31  returns to S 27  and obtains bitwise AND of the FV mask vector and the local flow vector  29  of the detour source transmitting port  12   b  again. On the other hand, in a case where the predetermined number of times is reached, the LAG traffic control unit  31  returns to S 21 . 
         [0077]    By referencing the local flow vector  29  of the detour source transmitting port  12   b  in this way, the LAG traffic control unit  31  is able to detour a flow belonging to a flow group whose packet is not stored in the corresponding output queue  12   c.    
         [0078]    Next, a flow of processing for flow detour cancellation based on the LAG traffic control unit  31  will be described.  FIG. 11  is a flowchart illustrating the flow of processing for flow detour cancellation based on the LAG traffic control unit  31 . As illustrated in  FIG. 11 , the LAG traffic control unit  31  determines whether or not a congestion release notification is received from the congestion detection notification unit  26  (S 41 ). In a case of being determined as not received, the LAG traffic control unit  31  waits for the congestion release notification to be received. 
         [0079]    On the other hand, in a case of being received, the LAG traffic control unit  31  references the flow group counter  28  of the corresponding transmitting port  12   b , thereby searching for a detour flow, (S 42 ) and determines whether or not there is a detour flow (S 43 ). In a case where it is determined that there is no detour flow, the LAG traffic control unit  31  terminates the processing. 
         [0080]    On the other hand, in a case where it is determined that there is a detour flow, the LAG traffic control unit  31  sets a corresponding bit of the FV mask vector to “1” (S 44 ) and obtains bitwise AND of the FV mask vector and the local flow vector  29  of a detour destination (S 45 ). In addition, the LAG traffic control unit  31  determines whether or not an operation result is “All 0s” (S 46 ). 
         [0081]    In a case of being determined as not “All 0s”, the LAG traffic control unit  31  returns to S 45 , and in a case of being determined as “All 0s”, the LAG traffic control unit  31  records, as a flow not to be detoured, in a corresponding entry of the flow group counter  28  (S 47 ). 
         [0082]    By referencing the local flow vector  29  of a detour destination in this way, the LAG traffic control unit  31  cancels detouring in a case where no packet is stored in the corresponding output queue  12   c . Accordingly, the switch  10  is able to avoid reversal of the arrival order of packets, associated with cancellation of detouring. 
         [0083]    As described above, in the first embodiment, in a case of receiving the TCP session request in a congestion state, the congestion detection notification unit  26  notifies the LAG traffic control unit  31  of congestion detection. Accordingly, in a case where a new flow is generated, the LAG traffic control unit  31  is able to detour the flow and to inhibit the reception order of packets from being reversed in the other switch  10  without increasing a load of the CPU. 
         [0084]    In the first embodiment, the LAG traffic control unit  31  references the local flow vector  29 , thereby detouring a flow belonging to a flow group whose packet is not stored in the corresponding output queue  12   c . Accordingly, the switch  10  only detours a flow whose packets are already transmitted to the other switch  10 . Therefore, it is possible to inhibit the reception order of packets from being reversed in the other switch  10 . 
         [0085]    In the first embodiment, by referencing the local flow vector  29 , the LAG traffic control unit  31  cancels detouring in a case where no packet is stored in the corresponding output queue  12   c . Accordingly, the switch  10  cancels detouring only in a case where packets are already transmitted to the other switch  10 . Therefore, it is possible to inhibit the reception order of packets from being reversed in the other switch  10 . 
         [0086]    In the first embodiment, in a case where the value of the queue length counter  12   d  exceeds the congestion threshold value  26   a , the congestion detection notification unit  26  detects congestion and notifies the LAG traffic control unit  31  thereof. Accordingly, the switch  10  is able to reliably sense congestion. 
         [0087]    In the first embodiment, whether or not each of the group counters in the flow group counter  28  is “0” is reflected in the local flow vector  29 . Accordingly, using the local flow vector  29 , the switch  10  is able to confirm a state of the corresponding output queue  12   c.    
         [0088]    In the first embodiment, for each of the flow groups, it is confirmed whether a packet is stored in the output queue  12   c . By selecting a relationship between the number of the output queues  12   c  and the number of entries in the flow group counter  28 , it is possible to reduce the flow group counter to a desired hardware size. Accordingly, for each of the flow groups, the switch  10  is able to determine whether or not detouring is available, and compared with a case where, for each of the flows, it is determined whether or not detouring is available, it is possible to reduce a hardware amount of the switch  10 . 
       Second Embodiment 
       [0089]    While a case of LAG is described in the first embodiment, a case of MLAG will be described in a second embodiment. Here, the term “MLAG” means LAG realized by devices.  FIG. 12  is a diagram for explaining MLAG. As illustrated in  FIG. 12 , an information processing system  3  according to the second embodiment includes 8 information processing devices  2  indicated by S#0 to S#7 and 6 switches  40  indicated by Leaf#0 to Leaf#3, Spine#0, and Spine#1. Here, a leaf (Leaf) is one of the switches  40 , which is directly connected to the corresponding information processing devices  2 . A spine (Spine) is one of the switches  40  other than Leafs. The switches  40  are devices that each relay communication between information processing devices. 
         [0090]    Each of the leafs includes 2 ports UP#0 and UP#1 for being connected to respective spines. UP#0 is connected to Spine#0, and UP#1 is connected to Spine#1. Each of the spines includes 4 ports DP#0 to DP#3 for being connected to respective leafs. DP#0 is connected to Leaf#0, DP#1 is connected to Leaf#1, DP#2 is connected to Leaf#2, and DP#3 is connected to Leaf#3. 
         [0091]    Each of the leafs includes a path for communicating with other leafs via Spine#0 and a path for communicating with other leafs via Spine#1 and configures MLAG. For example, packets addressed to S#0 by S#6 are to be sent from one of UP#0 and UP#1 of Leaf#3. If a link between Spine#0 and Leaf#0 is down, the packets sent from UP#0 reach Leaf#0 via Spine#0→Spine#1→DP#0. In this way, Spine#0 and Spine#1 that realize MLAG in relation to leafs configure one domain. 
         [0092]    The band of communication performed between the spines by using ISL is narrower than the band of communication performed between spines and leafs. While, in  FIG. 12 , for convenience of explanation, a case where the 2 spines configure the domain is described, the domain may be configured by more spines. 
         [0093]    Next, path changing based on the switches  40  according to the second embodiment will be described.  FIG. 13  is a diagram for explaining the path changing based on the switches  40  according to the second embodiment. As illustrated in  FIG. 13 , in the information processing system  3  according to the second embodiment, congestion information is shared between Spine#0 and Spine#1 belonging to the same domain in addition to FDB. In addition, upon detecting a congestion state in one of paths leading to the leafs, Spine#0 confirms that a path of Spine#1 is not congested, and Spine#0 uses a detour path routed through ISL. Upon detecting a congestion state of, for example, DP#0, Spine#0 confirms that DP#0 of Spine#1 is not congested, thereby using DP#0 of Spine#1 as a detour path. 
         [0094]    Based on queue information of DP#0, Spine#0 selects a flow to use the detour path. In addition, Spine#0 detours the selected flow via Spine#1. After that, if the congestion state of DP#0 is released, Spine#0 confirms information of an output queue  12   c  of DP#0 of Spine#1. In addition, in a case where no packet of the detoured flow is stored in the output queue  12   c , Spine#0 restores the path of the detoured flow to an original path. 
         [0095]    In this way, Spine#0 shares the congestion information with Spine#1, confirms that a path of Spine#1 is not congested, and uses a detour path. Accordingly, Spine#0 is able to perform efficient path changing. 
         [0096]    Next, configurations of the switches  40  according to the second embodiment will be described.  FIG. 14  is a diagram illustrating the configurations of the switches  40  according to the second embodiment. Here, for convenience of explanation, a same symbol is assigned to a functional unit that fulfills the same role as that of one of individual units illustrated in  FIG. 2 , and the detailed description thereof will be omitted. 
         [0097]    As illustrated in  FIG. 14 , compared with  FIG. 2 , the switches  40  each include a switching module  50  in place of the switching module  20 . The switching module  50  includes a flow group counter  58  in place of the flow group counter  28 . Unlike the flow group counter  28 , the flow group counter  58  stores no detour destination. The reason is that while, in the second embodiment, being different in a spine, a detour source and a detour destination are equal in the number of the transmitting port  12   b.    
         [0098]    By executing a program, the CPU  13  realizes functions of a LAG traffic control unit  41  and a control message transmission and reception unit  42 . Using a control message, the control message transmission and reception unit  42  transmits and receives congestion information to and from another spine. The control message transmission and reception unit  42  stores, in the memory  14 , the received congestion information as a remote congestion vector  43  and a remote flow vector  44 . Here, the term “remote” indicates another switch  40 . In contrast, the term “local” indicates the switch  40  itself. 
         [0099]      FIG. 15  is a diagram illustrating a control message between spines. As illustrated in  FIG. 15 , the control message includes Dst MAC, Src MAC, a congestion vector (CV), and a flow vector (FV). Dst MAC is a reserved MAC address of a protocol data unit (PDU) and is 01:80:C2:00:00:0f. Src MAC is a MAC address of the switch  40  that transmits the control message. CV is the local congestion vector  27  of the 32 transmitting ports  12   b . FV is the local flow vector  29  of 256 bits of the 32 transmitting ports  12   b.    
         [0100]    Regarding an information amount used for sharing the congestion state, 1 bit (a congestion state)×32 (ports)=32 bits=4 bytes is satisfied for CV, and 1 bit (a free state)×256 (flow groups)×32 (ports)=8 Kbits=1 Kbytes is satisfied for FV. Accordingly, if a message interval is 100 μs, (1 Kbytes×8 bits/100 μs)/10 Gbps=0.008 is satisfied. Therefore, a band usage rate in a link of, for example, 10 G (giga) is just about 0.8%. 
         [0101]    The LAG traffic control unit  41  has the same function as that of the LAG traffic control unit  31 . However, in a case of determining whether or not a detour path is usable, the LAG traffic control unit  41  uses the remote congestion vector  43  in place of the local congestion vector  27 .  FIG. 16  is a diagram for explaining determination of whether or not a detour path is usable. Compared with  FIG. 5 , in  FIG. 16 , bitwise AND of the remote congestion vector  43  and the CV mask vector is obtained. 
         [0102]    The LAG traffic control unit  41  records no port number of a detour destination in the flow group counter  58 .  FIG. 17  is a diagram for explaining recording of a flow to be detoured. As illustrated in  FIG. 17 , upon selecting a flow group to be detoured, the LAG traffic control unit  41  sets, to “1”, a bit indicating a detour of a corresponding entry of the flow group counter  58  while recording no port number of a detour destination. 
         [0103]    In a case where a congestion state is released, the LAG traffic control unit  41  confirms a free space of the output queue  12   c  of a detour destination by using the remote flow vector  44  in place of the local flow vector  29 , and after that, the LAG traffic control unit  41  cancels detouring. 
         [0104]    Next, flows of control message transmission and reception processing operations based on the control message transmission and reception unit  42  will be described.  FIG. 18  is a flowchart illustrating a flow of transmission processing for a control message, and  FIG. 19  is a flowchart illustrating a flow of reception processing for a control message. 
         [0105]    As illustrated in  FIG. 18 , the control message transmission and reception unit  42  determines whether or not a predetermined time period has elapsed (S 101 ). In a case where it is determined that the predetermined time period has not elapsed, the control message transmission and reception unit  42  waits for the predetermined time period to elapse. On the other hand, in a case where it is determined that the predetermined time period has elapsed, the control message transmission and reception unit  42  acquires, as the congestion information, the values of the local congestion vector  27  and the local flow vector  29  (S 102  and S 103 ) and transmits a control message including the congestion information (S 104 ). 
         [0106]    As illustrated in  FIG. 19 , the control message transmission and reception unit  42  determines whether or not a control message including the congestion information is received (S 111 ). In a case where it is determined that the control message including the congestion information is not received, the control message transmission and reception unit  42  waits for the control message including the congestion information to be received. 
         [0107]    On the other hand, in a case where it is determined that the control message including the congestion information is received, the control message transmission and reception unit  42  stores, in the memory  14 , the values of the remote congestion vector  43  and the remote flow vector  44  (S 112  and S 113 ). 
         [0108]    In this way, the control message transmission and reception unit  42  transmits and receives the control messages each including the congestion information. Accordingly, a spine is able to share the congestion information with another spine. 
         [0109]    Next, a flow of processing for selection of a detour flow based on the LAG traffic control unit  41  according to the second embodiment will be described.  FIG. 20  is a flowchart illustrating the flow of processing for selection of a detour flow based on the LAG traffic control unit  41  according to the second embodiment. As illustrated in  FIG. 20 , the LAG traffic control unit  41  determines whether or not a congestion detection notification is received from the congestion detection notification unit  26  (S 141 ). In a case where it is determined that a congestion detection notification is not received, the LAG traffic control unit  41  waits the congestion detection notification to be received. 
         [0110]    On the other hand, in a case where it is determined that the congestion detection notification is received, the LAG traffic control unit  41  sets, to “1”, a bit that corresponds to a local congested port and that is included in bits of the CV mask vector (S 142 ). In addition, the LAG traffic control unit  41  obtains bitwise AND of the CV mask vector and the remote congestion vector  43  (S 143 ) and determines whether or not an operation result is “All 0s” (S 144 ). In a case where it is determined that the operation result is not “All 0s”, the LAG traffic control unit  41  returns to S 141  and waits for a subsequent congestion detection notification to be received. 
         [0111]    On the other hand, in a case where it is determined that the operation result is “All 0s”, the LAG traffic control unit  41  sets, to “1”, a bit that is included in bits of the FV mask vector and that corresponds to a flow group to which a target flow to serve as a target of detouring belongs (S 145 ). In addition, the LAG traffic control unit  41  obtains bitwise AND of the FV mask vector and the local flow vector  29  of the detour source transmitting port  12   b  (S 146 ) and determines whether or not an operation result is “All 0s” (S 147 ). 
         [0112]    In a case where it is determined that the operation result is “All 0s”, the LAG traffic control unit  41  records, as a flow to be detoured, the target flow in a corresponding entry of the flow group counter  58  (S 148 ) and returns to S 141 . On the other hand, in a case where it is determined that the operation result is not “All 0s”, the LAG traffic control unit  41  waits for a predetermined time period (S 149 ) and determines whether or not the predetermined number of times is reached (S 150 ). 
         [0113]    In a case where it is determined that the predetermined number of times is not reached, the LAG traffic control unit  41  returns to S 146  and obtains bitwise AND of the FV mask vector and the local flow vector  29  of the detour source transmitting port  12   b . On the other hand, in a case where it is determined that the predetermined number of times is reached, the LAG traffic control unit  41  returns to S 141 . 
         [0114]    By referencing the remote congestion vector  43  in this way, the LAG traffic control unit  41  is able to determine a congestion state of a detour destination. 
         [0115]    As described above, in the second embodiment, the control message transmission and reception unit  42  transmits and receives the control messages each including the congestion information and writes, as the remote congestion vector  43  and the remote flow vector  44 , the control messages in the memory  14 . Accordingly, the congestion information is shared between the spines. In addition, after confirming a congestion state of a detour destination by using the remote congestion vector  43 , the LAG traffic control unit  41  performs detouring. The LAG traffic control unit  41  references the local flow vector  29 , thereby selecting, as a flow to be detoured, a flow whose packet is not stored in the corresponding output queue  12   c . Accordingly, the switch  40  is able to avoid reversal of the arrival order of packets due to a detour and to efficiently perform detouring. In the second embodiment, in a case where a congestion state is released, a detour of a flow is cancelled in order not to use a detour path. Accordingly, the switch is able to perform efficient packet relay without using ISL whose band is narrow. 
       Third Embodiment 
       [0116]    While a case where the congestion information is shared between spines is described in the second embodiment, a case where a leaf shares congestion information of a spine will be described in a third embodiment.  FIG. 21  is a diagram for explaining path changing based on a switch according to the third embodiment. In  FIG. 21 , the switch according to the third embodiment is indicated as a switch  60 . 
         [0117]    As illustrated in  FIG. 21 , Spine#0 and Spine#1 share congestion information with Leaf#0 to Leaf#3. In addition, upon sensing a congestion state in a path of Spine#0, each of the leafs changes a path by confirming that neither another port of the relevant leaf nor a path of Spine#1 is congested. 
         [0118]    Upon sensing a congestion state in, for example, a path of Spine#0, Leaf#3 changes a path by confirming that neither UP#1 nor DP#0 of Spine#1 is congested. In addition, Leaf#3 selects, based on the queue information of Leaf#3 itself, a flow whose path is to be changed, and Leaf#3 detours the flow. After that, if the congestion state of Spine#0 is released, Leaf#3 confirms queue information of each of Leaf#3 itself and Spine#1, used in a detour path, and restores a path of the detoured flow to an original path. 
         [0119]      FIG. 22A  and  FIG. 22B  are flowcharts each illustrating a flow of processing for selection of a detour flow based on an LAG traffic control unit according to the third embodiment. Here, the LAG traffic control unit according to the third embodiment is an LAG traffic control unit included in each of the leafs. As illustrated in  FIG. 22A , the LAG traffic control unit determines whether or not a congestion detection notification is received (S 241 ). In a case of being determined as not received, the LAG traffic control unit waits the congestion detection notification to be received. 
         [0120]    On the other hand, in a case of being determined as received, the LAG traffic control unit determines whether or not there is another transmitting port  12   b  to serve as a candidate for a detour path (S 242 ). In a case where it is determined that there is no other transmitting port  12   b  to serve as a candidate for a detour path, the LAG traffic control unit returns to S 241  and waits for a subsequent congestion detection notification to be received. 
         [0121]    On the other hand, in a case where it is determined that there is the other transmitting port  12   b  to serve as a candidate for a detour path, the LAG traffic control unit sets, to “1”, a bit that corresponds to a congested port of a spine and that is included in bits of the CV mask vector (S 243 ). In addition, the LAG traffic control unit obtains bitwise AND of the CV mask vector and the remote congestion vector  43  of another spine (S 244 ) and determines whether or not an operation result is “All 0s” (S 245 ). In a case of being determined as not “All 0s”, the LAG traffic control unit returns to S 241  and waits for a subsequent congestion detection notification to be received. 
         [0122]    On the other hand, in a case of being determined as “All 0s”, the LAG traffic control unit sets, to “1”, a corresponding bit of the CV mask vector of the detour path (S 246 ). In addition, the LAG traffic control unit obtains bitwise AND of the CV mask vector and the local congestion vector  27  of the detour path (S 247 ) and determines whether or not an operation result is “All 0s” (S 248 ). 
         [0123]    In a case of being determined as not “All 0s”, the LAG traffic control unit waits for a predetermined time period (S 249 ) and determines whether or not the predetermined number of times is reached (S 250 ). In a case where it is determined that the predetermined number of times is not reached, the LAG traffic control unit returns to S 247  and obtains bitwise AND of the CV mask vector and the local congestion vector  27  of the detour path again. On the other hand, in a case where it is determined that the predetermined number of times is reached, the LAG traffic control unit returns to S 241 . 
         [0124]    On the other hand, it is determined, in S 248 , that the operation result is “All 0s”, as illustrated in  FIG. 22B , the LAG traffic control unit sets, to “1”, a bit that is included in bits of the FV mask vector and that corresponds to a flow group to which a target flow to serve as a target of detouring belongs (S 251 ). In addition, the LAG traffic control unit obtains bitwise AND of the FV mask vector and the local flow vector  29  of the detour source transmitting port  12   b  (S 252 ) and determines whether or not an operation result is “All 0s” (S 253 ). 
         [0125]    In a case of being determined as “All 0s”, the LAG traffic control unit records, as a flow to be detoured, the target flow in a corresponding entry of the flow group counter  58  (S 254 ) and returns to S 241 . On the other hand, in a case of being determined as not “All 0s”, the LAG traffic control unit waits for a predetermined time period (S 255 ) and determines whether or not the predetermined number of times is reached (S 256 ). 
         [0126]    In a case where it is determined that the predetermined number of times is not reached, the LAG traffic control unit returns to S 252  and obtains bitwise AND of the FV mask vector and the local flow vector  29  of the detour source transmitting port  12   b  again. On the other hand, in a case where it is determined that the predetermined number of times is reached, the LAG traffic control unit returns to S 241 . 
         [0127]      FIG. 23  is a flowchart illustrating a flow of processing for flow detour cancellation based on the LAG traffic control unit according to the third embodiment. As illustrated in  FIG. 23 , the LAG traffic control unit determines whether or not a congestion release notification is received (S 261 ). In a case of being determined as not received, the LAG traffic control unit waits for the congestion release notification to be received. 
         [0128]    On the other hand, in a case of being determined as received, the LAG traffic control unit references the flow group counter  58  of the transmitting port  12   b  corresponding to a port of a spine, in which congestion is released, and the LAG traffic control unit searches for a detour flow (S 262 ). In addition, the LAG traffic control unit determines whether or not there is a detour flow (S 263 ). In a case where it is determined that there is no detour flow, the LAG traffic control unit terminates the processing. 
         [0129]    On the other hand, in a case where it is determined that there is a detour flow, the LAG traffic control unit sets a corresponding bit of the FV mask vector to “1” (S 264 ) and obtains bitwise AND of the FV mask vector and the remote flow vector  44  of a detour destination of a spine (S 265 ). In addition, the LAG traffic control unit determines whether or not an operation result is “All 0s” (S 266 ). 
         [0130]    In a case of being determined as not “All 0s”, the LAG traffic control unit returns to S 265 , and in a case of being determined as “All 0s”, the LAG traffic control unit obtains bitwise AND of the FV mask vector and the local flow vector  29  of its own detour destination (S 267 ). In addition, the LAG traffic control unit determines whether or not an operation result is “All 0s” (S 268 ). 
         [0131]    In a case of being determined as not “All 0s”, the LAG traffic control unit returns to S 267 , and in a case of being determined as “All 0s”, the LAG traffic control unit records, as a flow not to be detoured, in a corresponding entry of the flow group counter  58  (S 269 ). 
         [0132]    As described above, in the third embodiment, leafs share the congestion information of a spine. Therefore, if congestion occurs in a spine, a leaf changes to a detour path. Accordingly, the switch  60  is able to perform efficient detouring without using ISL whose band is narrow. 
         [0133]    All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although the embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.