Multi-level interconnection network

Abstract

A method and system for providing a multi-level interconnection network is provided. A multi-level interconnection network comprises basic cells that are aggregated into higher level cells at each level of the network. At the first level, the basic cells are aggregated into first level cells. Each first level cell is an aggregation of a number of basic cells that is one more than the number of devices in a basic cell. The basic cells of a first level cell are fully connected; that is, each basic cell has a first level link or connection to each other basic cell. In a first level cell, each device of a basic cell has a first level link to each other basic cell. The multi-level interconnection network has higher level cells that are aggregations of lower level cells in a similar manner.

1 - 16 . (canceled) 
     
     
         17 . A method of incrementally deploying a multi-level interconnection network, the method comprising:
 establishing a minimum cell representing a unit of addition to the network, the minimum cell having a minimum cell level and having a number of devices indicated by its server number;   establishing a maximum level for the network; and   for each level from the maximum level down to the level next higher than the minimum level, starting with the selection of the cell of the maximum level,
 when the number of child cells of the selected cell that have been assigned only one minimum cell is less than one more than the server number, selecting a next child cell that has not been assigned a minimum cell; and 
 when the number of child cells of the selected cell that have been assigned at least one minimum cell is not less than one more than the server number, selecting a next child cell such that the child cells with at least one minimum cell and that are not full are selected before selecting a child cell without any minimum cell. 
   
     
     
         18 . The method of  claim 17  wherein the identifier of the next minimum cell to add is determined from the index of the selected child cell at each of the levels. 
     
     
         19 . The method of  claim 17  wherein a minimum cell is a collection of one or more basic cells, each basic cell having a number of interconnected devices. 
     
     
         20 . The method of  claim 19  wherein the devices of the basic cell are connected via a switch. 
     
     
         21 . The method of  claim 17  wherein the lowest level of the interconnection network comprises basic cells with each basic cell having a number of devices that are connected to each other, each basic cell having the same number of devices. 
     
     
         22 . The method of  claim 21  wherein the second lowest level of the interconnection network comprises first level cells with each first level cell having a number of basic cells, the number of basic cells of a first level cell being a maximum of one more than the number of devices of a basic cell, each pair of basic cells of a first level cell being directly connected to each other basic cell via only one first level link, each first level link directly connecting a device of one basic cell of a pair to a device of the other basic cell of the pair such that no device is connected to more than one first level link. 
     
     
         23 . The method of  claim 22  wherein the third lowest level of the interconnection network comprises second level cells with each second level cell having a number of first level cells of the second level cell that is a maximum of one more than the number of devices within each first level cell, each pair of first level cells of a second level cell being directly connected to each other first level cell via only one second level link, each second level link directly connecting a device of one first level cell of a pair to a device of the other first level cell of the pair such that no device is connected to more than one second level link. 
     
     
         24 . A computer-readable storage medium containing computer-executable instructions for incrementally deploying a multi-level interconnection network, by a method comprising:
 establishing a minimum cell representing a unit of addition to the network, the minimum cell having a minimum cell level and having a number of devices indicated by its device number;   establishing a current maximum level for the network; and   for each minimum cell to be added to the interconnection network,
 for each level from the current maximum level down to the level next higher than the minimum level, starting with selecting the cell of the current maximum level,
 when the number of child cells of the selected cell that have been assigned only one minimum cell is less than one more than the device number, selecting a next child cell that has not been assigned a minimum cell; and 
 when the number of child cells of the selected cell that have been assigned at least one minimum cell is not less than one more than the device number, selecting a next child cell such that the child cells with at least one minimum cell and that are not full are selected before selecting a child cell without any minimum cell; and 
 
 assigning the minimum cell to the cells selected from the currently maximum level down to the level next higher than the minimum level. 
   
     
     
         25 . The computer-readable storage medium of  claim 24  wherein the network interconnect includes three levels with the minimum cell level being lowest level. 
     
     
         26 . The computer-readable storage medium of  claim 24  wherein the network interconnect includes four levels with the minimum cell level being the second lowest level or the lowest level. 
     
     
         27 . The computer-readable storage medium of  claim 24  wherein the network interconnect includes five levels with the minimum cell level being the third lowest level, the second lowest level, or the lowest level. 
     
     
         28 . The computer-readable storage medium of  claim 24  wherein the lowest level of the interconnection network comprises basic cells with each basic cell having a number of devices that are connected to each other, each basic cell having the same number of devices. 
     
     
         29 . The computer-readable storage medium of  claim 28  wherein the second lowest level of the interconnection network comprises first level cells with each first level cell having a number of basic cells, the number of basic cells of a first level cell being a maximum of one more than the number of devices of a basic cell, each pair of basic cells of a first level cell being directly connected to each other basic cell via only one first level link, each first level link directly connecting a device of one basic cell of a pair to a device of the other basic cell of the pair such that no device is connected to more than one first level link. 
     
     
         30 . The computer-readable storage medium of  claim 29  wherein the third lowest level of the interconnection network comprises second level cells with each second level cell having a number of first level cells of the second level cell that is a maximum of one more than the number of devices within each first level cell, each pair of first level cells of a second level cell being directly connected to each other first level cell via only one second level link, each second level link directly connecting a device of one first level cell of a pair to a device of the other first level cell of the pair such that no device is connected to more than one second level link. 
     
     
         31 . A method of deploying a multi-level interconnection network, by a method comprising:
 establishing a minimum cell representing a unit of addition to the network, the minimum cell having a minimum cell level and having a minimum cell number of devices; and   when a minimum cell is to be added to the interconnection network, adding the minimum cell to a cell of each level of the interconnection network that is higher than the minimum level so that at each level above the minimum level one minimum cell is added to each child cell up to one more than the minimum cell number of devices so that the child cells with one minimum cell can be fully connected with links of that level before additional minimum cells are added to that level.   
     
     
         32 . The method of  claim 31  wherein the lowest level of the interconnection network comprises basic cells with each basic cell having a number of devices that are connected to each other, each basic cell having the same number of devices. 
     
     
         33 . The method of  claim 32  wherein the second lowest level of the interconnection network comprises first level cells with each first level cell having a number of basic cells, the number of basic cells of a first level cell being a maximum of one more than the number of devices of a basic cell, each pair of basic cells of a first level cell being directly connected to each other basic cell via only one first level link, each first level link directly connecting a device of one basic cell of a pair to a device of the other basic cell of the pair such that no device is connected to more than one first level link. 
     
     
         34 . The method of  claim 33  wherein the third lowest level of the interconnection network comprises second level cells with each second level cell having a number of first level cells of the second level cell that is a maximum of one more than the number of devices within each first level cell, each pair of first level cells of a second level cell being directly connected to each other first level cell via only one second level link, each second level link directly connecting a device of one first level cell of a pair to a device of the other first level cell of the pair such that no device is connected to more than one second level link. 
     
     
         35 . The method of  claim 31  wherein the devices are servers. 
     
     
         36 . The method of  claim 35  wherein the devices of a basic cell are connected via a switch.