MULTI-HOUR DESIGN OF COMPUTER BACKBONE NETWORKS

This paper addresses the problem of designing wide area computer backb one networks that span many time zones. The problem of designing wide area computer backbone networks is commonly referred to as the Capacit y and Flow Assignment (CFA) problem. The CFA problem involves the rout ing of messages and the assignment of communication line capacities at minimum cost subject to performance constraints. In this paper, a ver sion of the CFA problem is addressed in which the assignment of commun ication line capacities is based on multi-hour traffic requirements. M ulti-hour traffic requirements are used since networks that span many time zones have changing traffic patterns that exhibit non-coincidence of traffic over the hours of the day. Thus, low cost network designs can be obtained by exploiting this non-coincidence. A heuristic proced ure is presented that takes advantage of this non-coincidence to provi de low cost solutions. This heuristic procedure is applied to a variet y of test problems and the solutions obtained are compared with lower bound solutions computed using a branch-and-bound procedure.