Decoupling congestion management state and connection management state in high performance computing

Abstract

A first network endpoint establishes a connection with a second network endpoint by transmitting a control packet including a first identifier associated with the connection and the first network endpoint. The first network endpoint stores, in a first data structure based on the first identifier, a first connection state associated with the connection and stores, in a second data structure based on the first connection state, a first congestion state associated with the connection. The first network endpoint identifies, for a data flow associated with the first identifier, a congestion state corresponding to the data flow, by: obtaining the first connection state by searching the first data structure based on the first identifier; and identifying the first congestion state by searching the second data structure based on the obtained first connection state.

What is claimed is: 
     
         1 . A computer-implemented method, comprising:
 establishing, by a first network endpoint, a connection with a second network endpoint by transmitting a control packet including a first identifier associated with the connection and the first network endpoint;   storing, by the first network endpoint in a first data structure based on the first identifier, a first connection state associated with the connection;   storing, by the first network endpoint in a second data structure based on the first connection state, a first congestion state associated with the connection; and   identifying, for a data flow associated with the first identifier, a congestion state corresponding to the data flow, identifying the corresponding congestion state comprising:
 obtaining the first connection state by searching the first data structure based on the first identifier; and 
 identifying the first congestion state by searching the second data structure based on the obtained first connection state. 
   
     
     
         2 . The method of  claim 1 , further comprising:
 identifying a data packet to be scheduled, the data packet associated with the first identifier; and   determining whether to schedule the data packet based on at least one of:
 a status of the identified first congestion state; 
 a status of the obtained first connection state; or 
 one or more statuses of connections associated with the identified first congestion state. 
   
     
     
         3 . The method of  claim 1 , further comprising:
 storing the first connection state in a first entry in the first data structure, the first data structure comprising connection states associated with connections between the first network endpoint and at least the second network endpoint; and   storing the first congestion state in a second entry in the second data structure, the second data structure comprising congestion states associated with the connections between the first network endpoint and at least the second network endpoint.   
     
     
         4 . The method of  claim 3 ,
 the first entry indicating at least the first identifier associated with the connection, one or more data packets pending to be transmitted, a first status associated with the connection, and a congestion index associated with the first congestion state stored in the second data structure, and   the method further comprising identifying the first congestion state by searching the second data structure further based on the congestion index indicated in the first entry.   
     
     
         5 . The method of  claim 4 ,
 the second entry in the second data structure indicating at least a second status associated with the first congestion state, one or more connection indices corresponding to elements in the first data structure, and one or more of a congestion window size and a congestion rate, and   the connection indices including at least the first identifier for the connection and corresponding to connections associated with the first congestion state.   
     
     
         6 . The method of  claim 3 ,
 the first entry in the first data structure indicating at least the first identifier associated with the connection, one or more data packets pending to be transmitted, and a first status associated with the connection,   the second entry in the second data structure indicating at least a second status associated with the first congestion state and one or more of a congestion window size and a congestion rate, and   the method further comprising identifying the first congestion state by searching the second data structure further based on an encoding associated with the first identifier.   
     
     
         7 . The method of  claim 6 ,
 the second entry in the second data structure further indicating an array comprising connection state entries from the first data structure, the second entry comprising the first congestion state, and   the method further comprising:
 including the connection states associated with the connection as a sub-element of the congestion state; 
 identifying the first congestion state by searching the second data structure further based on a first encoding associated with the first identifier; and 
 obtaining the first connection state by searching the array based on a second encoding associated with the first identifier. 
   
     
     
         8 . The method of  claim 7 , further comprising encoding the first identifier based on at least one of:
 obtaining a first index for the second data structure by shifting one or more bits of the first identifier, the first identifier and the first index comprising fully overlapping bits;   obtaining a second index for the second data structure by shifting one or more bits of the first identifier, the first identifier and the second index comprising no overlapping bits; or   obtaining the first index or the second index by masking the first identifier prior to shifting the one or more bits.   
     
     
         9 . The method of  claim 7 , further comprising:
 determining that the data flow comprises at least:
 first data transmitted from the first network endpoint to the second network endpoint; and 
 second data transmitted from the first network endpoint to the second network endpoint in response to a request from the second network endpoint; 
   storing, by the first network endpoint, the first connection state in the first data structure using a portion of the first identifier in response to the data flow comprising the first data, the first data structure further comprising connection states associated with the first network endpoint as a transmitting entity;   storing, by the first network endpoint, the first connection state in a third data structure using the same portion of the first identifier in response to the data flow comprising the second data, the third data structure comprising connection states associated with the first network endpoint as a receiving entity; and   storing, by the first network endpoint, the first congestion state in the second data structure using a remainder of the first identifier.   
     
     
         10 . A computer system, comprising:
 a processing resource; and   a non-transitory machine-readable storage device storing instructions executable by the processing resource to:
 transmit, by a first network endpoint, a control packet including a first identifier associated with the first network endpoint and a connection to be established with a second network endpoint; 
 store, by the first network endpoint based on the first identifier, a first connection state associated with the connection; 
 store, by the first network endpoint based on the first connection state, a first congestion state associated with the connection; and 
 identify, for a data flow associated with the first identifier, a congestion state corresponding to the data flow, by performing:
 a first search, using the first identifier, in a first structure which stores connection states associated with connections, the first search returning the first connection state; and 
 a second search, using the returned first connection state, in a second data structure which stores congestion states associated with connection states, the second search identifying the first congestion state. 
 
   
     
     
         11 . The computer system of  claim 10 , the instructions executable by the processing resource further to:
 determine whether to schedule a data packet associated with the first identifier based on at least one of:
 a status of the identified first congestion state; 
 a status of the returned first connection state; or 
 one or more statuses of connections associated with the identified first congestion state. 
   
     
     
         12 . The computer system of  claim 10 , the instructions executable by the processing resource further to:
 store the first connection state in a first entry in the first data structure, the first data structure comprising connection states associated with connections between the first network endpoint and at least the second network endpoint; and   store the first congestion state in a second entry in the second data structure, the second data structure comprising congestion states associated with the connections between the first network endpoint and at least the second network endpoint.   
     
     
         13 . The computer system of  claim 12 , the instructions executable by the processing resource further to:
 indicate, in the first entry in the first data structure, at least the first identifier associated with the connection, one or more data packets pending to be transmitted, a first status associated with the connection, and a congestion index associated with the first congestion state stored in the second data structure; and   perform the second search based on the congestion index indicated in the first entry.   
     
     
         14 . The computer system of  claim 13 , the instructions executable by the processing resource further to:
 indicate, in the second entry in the second data structure, at least a second status associated with the first congestion state, one or more connection indices corresponding to elements in the first data structure, and one or more of a congestion window size and a congestion rate; and   include in the connection indices at least the first identifier for the connection, the connection indices corresponding to connections associated with the first congestion state.   
     
     
         15 . The computer system of  claim 12 , the instructions executable by the processing resource further to:
 indicate, in the first entry in the first data structure, at least the first identifier associated with the connection, one or more data packets pending to be transmitted, and a first status associated with the connection;   indicate, in the second entry in the second data structure, at least a second status associated with the first congestion state and one or more of a congestion window size and a congestion rate; and   perform the second search based on an encoding associated with the first identifier.   
     
     
         16 . The computer system of  claim 15 , the instructions executable by the processing resource further to:
 indicate, in the second entry in the second data structure, an array comprising connection state entries from the first data structure, the second entry comprising the first congestion state;   include the connection states associated with the connection as a sub-element of the congestion state;   identify the first congestion state by searching the second data structure based on a first encoding associated with the first identifier; and   obtaining the first connection state by searching the array based on a second encoding associated with the first identifier.   
     
     
         17 . The computer system of  claim 16 , the instructions executable by the processing resource further to encode the first identifier by at least one of:
 obtaining a first index for the second data structure by shifting one or more bits of the first identifier, the first identifier and the first index comprising fully overlapping bits;   obtaining a second index for the second data structure by shifting one or more bits of the first identifier, the first identifier and the second index comprising no overlapping bits; or   obtaining the first index or the second index by masking the first identifier prior to shifting the one or more bits.   
     
     
         18 . A non-transitory computer-readable storage medium comprising instructions executable by a processing resource to:
 establish a connection between a first network endpoint and a second network endpoint by transmitting a control packet including a first identifier associated with the connection and the first network endpoint;   store, in a first entry in a first data structure based on the first identifier, a first connection state associated with the connection;   store, in a second entry in a second data structure based on the first connection state, a first congestion state associated with the connection;   identify, for a data flow associated with the first identifier, a congestion state corresponding to the data flow, by:
 obtaining the first connection state by searching the first data structure based on the first identifier; and 
 identifying the first congestion state by searching the second data structure based on the obtained first connection state; and 
   determine whether to schedule a data packet associated with the first identifier based on a status of the identified first congestion state or the returned first connection state.   
     
     
         19 . The non-transitory computer-readable storage medium of  claim 18 ,
 the first entry indicating at least the first identifier associated with the connection, one or more data packets pending to be transmitted, a first status associated with the connection, and a congestion index associated with the first congestion state stored in the second data structure, and   the instructions executable by the processing resource further to identify the first congestion state by searching the second data structure further based on the congestion index indicated in the first entry.   
     
     
         20 . The non-transitory computer-readable storage medium of  claim 18 ,
 the first entry in the first data structure indicating at least the first identifier associated with the connection, one or more data packets pending to be transmitted, and a first status associated with the connection,   the second entry in the second data structure indicating at least a second status associated with the first congestion state and one or more of a congestion window size and a congestion rate, and   the instructions executable by the processing resource further to:
 identify the first congestion state by searching the second data structure further based on an encoding associated with the first identifier; and 
 schedule the data packet further based on the first status and the second status.