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 f
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. A method for generating a path for routing a packet in a multi-level interconnection network of devices, the method comprising: providing a packet to be sent from a source device to a destination device of the network;identifying a closest common ancestor cell of the source device and the destina
1. A method for generating a path for routing a packet in a multi-level interconnection network of devices, the method comprising: providing a packet to be sent from a source device to a destination device of the network;identifying a closest common ancestor cell of the source device and the destination device, the closest common ancestor cell being the lowest level cell that contains both the source device and the destination device;when the closest common ancestor cell is a basic cell, establishing the path as an inter-basic cell path between the source device and the destination device; andwhen the closest common ancestor cell is not a basic cell, identifying an inter-cell link between a source-side device of a child cell of the closest common ancestor cell that contains the source device and a destination-side device of the child cell of the closest common ancestor cell that contains the destination device;identifying a source-side path from the source device to the source-side device;identifying a destination-side path from the destination-side device to the destination device; andestablishing the path as a concatenation of the source-side path, the inter-cell link, and the destination-side path. 2. The method of claim 1 wherein each device of the network has a unique identifier and the closet common ancestor cell is identified from the unique identifier of the source device and the unique identifier of the destination device. 3. The method of claim 2 wherein each cell within a level of the network is provided with a unique index within that level and each basic cell within a first level cell is provided with a unique index within that first level cell, and the unique identifier of each device is derived from the unique index of the device and the unique indexes of each ancestor cell of the device. 4. The method of claim 3 wherein the unique identifier of each device is generated by adding the unique index of the device within its basic cell to a summation, for each other ancestor cell, of the unique index of that ancestor cell times the maximum number of devices in a cell of the next lower level. 5. The method of claim 1 wherein the identifying of the source-side path includes recursively generating a path from the source device to the source-side device. 6. The method of claim 1 wherein the identifying of the destination-side path includes recursively generating a path from the destination-side device to the destination device. 7. The method of claim 1 including routing the packet along the generated path from the source device to the destination device. 8. The method of claim 1 wherein the network comprises: a plurality of basic cells, each basic cell having a number of devices connected via a communication mechanism; anda first level for organizing the basic cells into a first level cell, the number of basic cells of the first level cell being a maximum of one more than the number of devices in each basic cell, each device of each basic cell of the first level cell being directly connected via a first level link to one device of each other basic cell of the first level cell. 9. A method for modifying a path to avoid a failed link in a multi-level interconnection network of the plurality of devices, the method comprising: establishing an initial path from a source device to a destination device, the path identifying links between some of the devices of the multi-level interconnection network, each link in the path connecting a source-side device to a destination-side device, the lowest level of the multi-level interconnection network aggregating each of the plurality of devices into lowest level cells, each level that is higher than the lowest level having an aggregation of the cells of the next lower level into cells of that level, such that each cell of a level has at most one link to each other cell of that level to form a cell of the next higher level with links of the next higher level connecting the cells of the next lower level, such that for each level, each device of a cell has at most one link connecting the device to another device of another cell of that level;when it is determined that a link along the path has failed, identifying the level of the failed link wherein the source-side device and the destination-side device of the failed link are in different cells of the next lower level;selecting a proxy source-side device of another cell of the next lower level;establishing a to-proxy path from the source-side device of the failed link to the proxy source-side device; andestablishing a from-proxy path from the proxy source-side device to the destination device,wherein the modified path includes a portion of the initial path from the source device to the source-side device of the failed link, the to-proxy path, and the from-proxy path. 10. The method of claim 9 wherein each device, for each ancestor cell of the device, broadcasts to other devices of that ancestor cell the state of the device and the state of its links for the level of the ancestor cell and each device using a link state routing establishes a path between devices within that ancestor cell. 11. The method of claim 10 wherein when a device first receives a message of a broadcast, it forwards through other links for the level of the ancestor cell. 12. The method of claim 10 wherein link state routing is used to determine the path within the cell of the level of the failed link. 13. The method of claim 9 wherein the initial path is established by: identifying a closest common ancestor cell of the source device and the destination device, the closest common ancestor cell being the lowest level cell that contains both the source device and the destination device;when the closest common ancestor cell is a basic cell, establishing the initial path as an intra-basic cell path between the source device and the destination device; andwhen the closest common ancestor cell is not a basic cell, identifying an inter-cell link between a source-side device of the child cell of the closest common ancestor cell that contains the source device and a destination-side device of the child cell of the closest common ancestor cell that contains the destination device;identifying a source-side path from the source device to the source-side device;identifying a destination-side path from the destination-side device to the destination device; andestablishing the initial path as a concatenation of the source-side path, the inter-cell link, and the destination-side path. 14. The method of claim 9 wherein the network comprises: a plurality of basic cells, each basic cell having a number of devices connected via a communication mechanism; anda first level for organizing the basic cells into a first level cell, the number of basic cells of the first level cell being a maximum of one more than the number of devices in a basic cell, each device of each basic cell of the first level cell being directly connected via a first level link to one device of each other basic cell of the first level cell. 15. The method of claim 9 wherein each cell within a level of the network is provided with a unique index within that level and each device within a basic cell is provided with a unique index within that basic cell, and the unique identifier of each device is derived from the unique indexes of the device and of each ancestor cell of the device. 16. A computer-readable storage device storing computer-executable instructions for controlling a computing device to generate a path for routing a packet in a multi-level interconnection network of devices, by a method comprising: providing a packet to be sent from a source device to a destination device of the network;identifying a closest common ancestor cell of the source device and the destination device, the closest common ancestor cell being the lowest level cell that contains both the source device and the destination device;when the closest common ancestor cell is a basic cell, establishing the path as an inter-basic cell path between the source device and the destination device; andwhen the closest common ancestor cell is not a basic cell, identifying an inter-cell link between a source-side device of a child cell of the closest common ancestor cell that contains the source device and a destination-side device of the child cell of the closest common ancestor cell that contains the destination device;identifying a source-side path from the source device to the source-side device;identifying a destination-side path from the destination-side device to the destination device; andestablishing the path as a concatenation of the source-side path, the inter-cell link, and the destination-side path. 17. The computer-readable storage device of claim 16 wherein each device of the network has a unique identifier and the closet common ancestor cell is identified from the unique identifier of the source device and the unique identifier of the destination device. 18. A computer-readable storage device storing computer-executable instructions for controlling a computing device to modify a path to avoid a failed link in a multi-level interconnection network of a plurality of devices, by a method comprising: establishing an initial path from a source device to a destination device, the path identifying links between some of the devices of the multi-level interconnection network, each link in the path connecting a source-side device to a destination-side device, the lowest level of the multi-level interconnection network aggregating the plurality of devices into lowest level cells, each level that is higher than the lowest level having an a aggregation of the cells of the next lower level into cells of that level, such that each cell of a level has one link to each other cell of that level to form a cell of the next higher level with links of the next higher level connecting the cells of the next lower level, such that for each level, each device of a cell has no more than one link connecting the device to a device of another cell of that level;when it is determined that a link along the path has failed, identifying the level of the failed link wherein the source-side device and the destination-side device of the failed link are in different cells of a next lower level;selecting a proxy source-side device of another cell of the next lower level;establishing a to-proxy path from the source-side device of the failed link to the proxy source-side device; andestablishing a from-proxy path from the proxy source-side device to the destination device,wherein the modified path includes a portion of the initial path from the source device to the source-side device of the failed link, the to-proxy path, and the from-proxy path. 19. The computer-readable storage device of claim 18 wherein each device, for each ancestor cell of the device, broadcasts to other devices of that ancestor cell the state of the device and the state of its links for the level of the ancestor cell and each device using a link state routing establishing a path between devices within that ancestor cell. 20. The computer-readable storage device of claim 18 wherein the initial path is established by: identifying a closest common ancestor cell of the source device and the destination device, the closest common ancestor cell being the lowest level cell that contains both the source device and the destination device;when the closest common ancestor cell is a basic cell, establishing the initial path as an intra-basic cell path between the source device and the destination device; andwhen the closest common ancestor cell is not a basic cell, identifying an inter-cell link between a source-side device of the child cell of the closest common ancestor cell that contains the source device and a destination-side device of the child cell of the closest common ancestor cell that contains the destination device;identifying a source-side path from the source device to the source-side device;identifying a destination-side path from the destination-side device to the destination device; andestablishing the initial path as a concatenation of the source-side path, the inter-cell link, and the destination-side path.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (11)
Chao, Hung-Hsiang Jonathan; Xi, Kang, Determining rerouting information for single-link failure recovery in an Internet protocol network.
Kazuaki Iwamura JP; Takeo Horiguchi JP; Shogo Yamaguchi JP; Takuya Kawamura JP; Shinzo Matsubara JP; Fumihiko Ikegami JP, Network construction method and communication system for communicating between different groups via representative device of each group.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.