The research reported here offers a solution to the communications resource allocation problem. Unlike earlier approaches to this problem, we employ a time-sliced event model where messages are sent and received in a single time slice called an epoch. In addition, we also consider networks that contain relay nodes capable of only transferring messages. Consequently, network topologies can be considered where a given node is not directly connected to every other node and must use one or more relay nodes in order to get a message to some destination. The resulting architectures broaden the networks to be considered and enable the capability of constructing more realistic communication scenarios. In this paper we modify the standard MCNF model by turning our focus to feasibility instead of optimality in an effort to provide adequate and accurate decision support to communication network planners. Given a network configuration and message requirements, our goal is to determine if the proposed scenario is feasible in terms of the communication resources available. To meet this goal, three algorithms are presented that each solve the extended MCNF problem with varying degrees of accuracy and run-time requirements. Experimental results show that a large number of multi-variable interactions among input parameters play a key role in determining feasibility and predicting expected execution time. Several heuristics are presented that reduce run-time dramatically, in some cases by a factor of 37. Each algorithm is tested on a range of inputs and compared to the others. Preliminary results gathered indicate that the second algorithm of the three (APEA) offers the best balance of accuracy vs. execution time. In summary, the solutions presented here solve the resource allocation problem for message delivery in a way that enables evaluation of real world communication scenarios. / Master of Science

In this paper, we present solutions concerning communications resource allocation for tactical communication networking. Given a mission definition (which defines communication needs among participants) and participant capabilities (such as processing power and bandwidth), algorithms are presented to determine if the mission as presented is feasible. The mathematical foundation of the problem is presented, and a "static" model to determine feasibility is shown. Further evolution of the algorithm into a "dynamic" model and the reasons for the more demanding requirements are presented. Reasoning behind use of the Netflo algorithm in the dynamic model is also discussed. The inclusion of the algorithm in a stand-alone program is discussed, including overall program structure, graphical user interface components and alternative output (such as the generation of high level network policy). Finally, future work in this area is discussed. / Master of Science