We introduce a new type of network routing problem, the subnet generation problem (SGP) which is a special case of the traffic placement problem (TPP). In the TPP, given (1) a network which consists of routers and links, and (2) a set of point-to-point traffic demands to be placed including finding feasible routes, the objective is to minimize the sum of costs of the unplaced demands subject to the Quality-of-Service routing constraints.
The SGP is a TPP with an extra set of constraints that restricts the combinations of demands to be placed. In our SGP, each router has a fixed amount of
that is to be transmitted to every other router in the
. A subnet is defined as any subset of the routers in the network. This means that every router in the subnet will have exactly the same total information-gain. The objective is to find a subnet that maximizes the total information-gain: there must be a demand with a valid path between every pair of routers in the subnet. The reason for creating demands among the routers arises from the fact that every node in a selected group of routers is required to be a client and a server. The figure below shows an example of a subnet and a path solution.