METHOD AND APPARATUS FOR HIERARCHICAL ROUTING IN MULTIPROCESSOR MESH-BASED SYSTEMS
First Claim
1. A method comprising:
- splitting a mesh network of nodes into a plurality of partitions, each partition including at least one node;
dividing a first partition into a plurality of rectangular regions;
determining a partition route from a source region to a destination region of the plurality of rectangular regions;
providing a region route from a region source node within one of the plurality of rectangular regions to a region destination node within the same rectangular region; and
routing a packet from a source node within the source region to a destination node within the destination region using the partition route and the region route.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for hierarchical routing in mesh systems. The method may include splitting 420 a mesh network of nodes into a plurality of partitions, each partition including at least one node, dividing 430 a first partition into a plurality of rectangular regions, determining 440 a partition route from a source region to a destination region of the plurality of rectangular regions, and providing 450 a region route from a source node within one of the plurality of rectangular regions to a destination node within the same rectangular region. The method may also include routing 460 a packet from a source node within the source region to a destination node within the destination region using the partition route and the region route.
-
Citations
20 Claims
-
1. A method comprising:
-
splitting a mesh network of nodes into a plurality of partitions, each partition including at least one node; dividing a first partition into a plurality of rectangular regions; determining a partition route from a source region to a destination region of the plurality of rectangular regions; providing a region route from a region source node within one of the plurality of rectangular regions to a region destination node within the same rectangular region; and routing a packet from a source node within the source region to a destination node within the destination region using the partition route and the region route. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. An apparatus comprising:
-
a mesh network including a plurality of nodes; and a controller coupled to the mesh network, the controller including a routing initialization module configured to split the mesh network into a plurality of partitions, each partition including at least one node, divide a first partition into a plurality of rectangular regions; and at least one local routing module coupled to a node of the plurality of nodes, the at least one local routing module configured to determine a partition route from a source region to a destination region of the plurality of rectangular regions, provide a region route from a region source node within one of the plurality of rectangular regions to a region destination node within the one of the plurality of rectangular regions, and route a packet from a source node within the source region to a destination node within the destination region using the partition route and the region route. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. A method comprising:
-
splitting a mesh network of nodes into a plurality of partitions, each partition including at least one node, at least one partition providing performance isolation from at least one other partition of the plurality of partitions; dividing a first partition into a plurality of rectangular regions; determining a partition route from a source region to a destination region of the plurality of rectangular regions; providing a region route from a region source node within the destination region to a region destination node within the destination region; examining a packet destination region identifier and a packet destination node intra-region identifier; comparing the packet destination region identifier with a node region identifier to determine if the packet has reached the destination region; and comparing, if the packet has reached the destination region, the packet destination node intra-region identifier with a node intra-identifier to determine if the packet has reached the destination node. - View Dependent Claims (20)
-
Specification