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.