Efficient resource placement in generalized de Bruijn networks

The de Bruijn network is generally considered to be a promising substitute for the hypercube, because it has a small node degree and is versatile, fault tolerant, and easily extensible. In this paper, we focus on efficient resource allocation in undirected, binary, generalized de Bruijn networks. We consider the problem of placing the minimum number of resource copies in a network, such that each node either has a copy of the resource or is able to reach exactly one copy of the resource within a given number of hops, lay, d hops. The solution to this problem is referred to as a perfect d-hop placement. We show that there exists a perfect 1-hop placement for all networks such that n = 5(2i+1), or 10(2i+1), where i is any non-negative integer ad n is the number of nodes in the network. We also demonstrate that it is impossible for a perfect 1-hop placement to exist on a de Bruijn network when n = 10i+1, where i≥1 and i mod 3≠2. Through a software simulation, we also illustrate that perfect 1-hop placements exist, in the range 2≤n≤30, only for networks where n = 2, 3, 4, 5, 6, 10, 15, 25, and 30. Finally, we examine the issue of whether a perfect resource placement on a de Bruijn network must be symmetric.