Hypergraph theory started to take shape around 1960. It has been seen that the theory of hypergraphs is a powerful tool for the solution of integers optimization problems, such as scheduling problems, location problems, etc. when the incidence matrices of the corresponding graphs have some special properties. Combinatorial block designs, whose root can be traced much earlier than hypergraphs, are considered as special hypergraphs. They already found applications such as experiment designs, coding theory, etc. In this project, the investigator intends to extend the hypergraph and combinatorial design theories, motivated by a new class of applications, namely powerful interconnection structures in high-performance computing and communications based on multiconnect components. The new class of interconnection structures considered are called hypernetworks. A typical multiconnect component is an optical device connecting a set of nodes using TDM, WDM, CDM and SDM techniques. Additional examples of multiconnect component include a wireless LAN, a "cluster" of communicating mobile stations and a high-performance subnetwork in grid computing. A hypernetwork is represented by a hypergraph. In a point-to-point network, each connection, which connects a pair of nodes, has a fixed capacity dedicated to it. In a hypernetwork, the nodes connected by a multiconnect component or multipoint subnet are considered fully connected. Due to shared resources (channels, transceivers. etc.), hypernetworks have more balanced link loading, higher throughput and reduced time delay. Furthermore, hypernetworks support multipoint communications more efficiently. A hypernetwork, when abstracted as a hypergraph, is characterized by several parameters, such as vertex degree, hyperedge rank, diameter, bisection connectivity. regularity, uniformity, symmetry, etc. Since combinatorial block designs are special hypergraphs with many properties that are desirable in hypernetworks, it is quite natural to consider hypernetworks whose underlying theoretic models are block designs. The investigator propose to use hypergraph and combinatorial block design theories to guide the design of hypernetworks. Each design aspect has a spectrum of design choices. The design of a particular type of hypernetworks depend in application demands, technology feasibility, and cost-effectiveness. Since desirable hypernetwork features are interrelated and many of them have contradicting requirements, trade-offs must be considered. Thus, hypernetwork design problems are constrained optimization problems. The goal of this project is to investigate the potential and limit of hypernetworks by applying new combinatorial optimization techniques. The proposed research have implications in the construction of new computing and communication systems using emerging technologies. The proposed work is theoretical in nature, and it addresses fundamental issues in information processing and communication.
