We will study the problem of exponential interconnection networks. Such a network is geometrically embedded with constant degree, and has links of different lengths such that number of nodes with a link of length x in a region of area A is proportional to A=2x. We begin our investigation by focusing on one example.
The Packed Exponential Connections (PEC) network is a grid-based network with connectivity and routing results that are competitive with hypercubic networks. The prior results are all empirical, since the structure of the network has only been understood through an indirect existence proof. In this research we will explore the first theoretical understanding of a PEC network. The preliminary work will be extended to incorporate the fundamental problems of routing and broadcasting; this will lead to broader question of the algorithmic utility of the PEC network, and exponential interconnection networks in general.
While the PEC network is deterministic an exponential interconnection networks can also be defined probabilistically. Such a network can and will be studied empirically and analytically; in any event, the PEC network gives a benchmark for comparisons.
The broader impact of this work can be seen both in the benefits of the research and the benefits for education. There is a need for a better understanding of networks in areas like ad hoc networks. In these areas the emphasis has been on simple issues like connectivity and hierarchical flow of information; we propose to study the properties of sparse networks that are better suited to algorithmic processing. The first step in this direction is the PEC networks. The educational benefits will be primarily in the involvement of students; a Ph.D. candidate is budgeted. This aspect of broader impact is particularly true for an SGER proposal, since it is always harder for a student to find support to work on high-risk subjects. It is important to train researchers to take risks. The desires of NSF to support underrepresented groups and undergraduate education will be kept in mind.
