Resource placement in a class of hierarchical networks

The authors consider efficient resource placement in a class of hierarchical networks, which is a general type of cube-connected-cycles network and is referred to as GCCC. We consider the problem of placing the minimum number of resource copies in the network such that each node in the network either has a copy of the resource or is able to reach exactly one copy of the resource within a given number of hops, say, d hops. The solution to this problem is referred to as a perfect d-hop placement. We show that for any k-dimensional GCCC, a perfect 1-hop placement can be constructed if and only if k ≠ 2 or 5. We also discuss the general perfect d-hop placement in a k-dimensional GCCC, concluding that the necessary and sufficient condition for a perfect d-hop placement (d ≥ 2) to exist is that k be an integral multiple of (3×2 ^d-1-1). For those GCCC's in which a perfect placement does exist, our constructive proofs for these results also provide an algorithm for actually placing the resource copies in the GCCC. Finally, for those GCCC's in which a perfect placement does not exist, we consider approximate d-hop placements. We show that the number of resource copies needed in this case approaches the theoretical lower bound for perfect placement for large k.