National Bureau of Standards Technical Note 787 Nat. Bur. Stand. (U.S.), Tech. Note 787, 52 pages (June 1973) For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C., 20402. (Order by SD Catolog No. (13.46:787). Price $0.80 domestic postpaid or $0.55 G.P.O. Bookstore. Requests (ADDREQ) .. 3.3 First Network and First Optimization (PASS1) 3.5 "Express" Links (BYPASS) ... 3.6 Rerouting Uneconomical Link Fills (PASS2 and PASS3) .. 23 APPENDIX B. NETWORK CHANGES PRODUCED BY DANGLING LINK ALGORITHM. B-1 We would like to acknowledge the efforts of Mr. T. Zois for his work in obtaining and processing the initial network, and Mr. J. Grossmon for his programming contributions while a summer student employee at NBS in 1970. Disclaimer of endorsement: Use by the National Bureau of Standards of a particular manufacturer's computing equipment should not be construed to imply endorsement of that manufacturer's equipment by the National Bureau of Standards. HEURISTIC COST OPTIMIZATION OF THE FEDERAL TELPAK NETWORK* R. G. Saltman G. R. Bolotsky Z. G. Ruthberg A heuristic method of optimizing the design of a very large communications network is described. The procedure is employed to configure the routes of 5552 communications service requests involving 1633 nodes. A FORTRAN IV program was developed to solve for actual needs of the Defense Communications Agency for leased-line service employing the Telpak tariff structure. Key words: Communications network; computer program; heuristic; minimum cost; network configuration; optimization; Telpak rate structure. 1.0 INTRODUCTION 1.1 The Network Problem The Federal Government leases, on a monthly basis, a large number of interstate voice-grade circuits for its own use under the Telpak tariff. This tariff offers savings for bulk requirements, basing costs on *Sponsored by Defense Communications Agency, Reimbursable Order Nos. 70-19,71-36,72-78. per-mile of circuits leased rather than number of calls made. In 1969, leasing costs for these communications services, managed by the DOD Defense Commercial Communications Office (DECCO), were $3,773,000/month. In that same year, the Institute for Computer Sciences and Technology, National Bureau of Standards, was asked by the Defense Communications Agency, the parent organization of DECCO, to explore the use of a computer to automatically configure and optimize the DECCO DOD Telpak Network, which was being optimized manually by DECCO personnel. This report summarizes the results of this effort. All The DECCO DOD network consisted at that time, of 1633 ratecenters with sufficient circuit linkage to satisfy the needs of 552 "requests". A "request" is a requirement for continuous, leased service submitted by using agencies. It consists of two items: (1) a unique node pair which constitutes the end points (terminals) of the service and (2) the number of circuits desired to connect these end points. requirements submitted by different agencies for the same node pair are summed to determine the circuit requirements of a request. The routing of all requests for minimum cost is the essential substance of this problem. The outputs of the solution to the routing problem are (1) the sequence of nodes through which each request passes between its end points, (2) the listing and costing of the individual node-to-node links, and (3) the summarized cost of all links. The total requests for Telpak service which this R&D effort was to solve consisted of approximately 35,000 voice-grade lines. 1.2 The Telpak Problem's Value The advantage of the Telpak bulk rate structure can be seen from Table 1. Whereas the cheapest single circuit lease (Ixc)* rate was 75¢/mile/month in 1969, the Telpak rate in that year brought the single circuit cost down to 47¢/mile/month for complete C bundles of 60 circuits and 25¢/mile/month for complete D bundles of 240 circuits. At present all costs are proportionately higher. The essential fact about the C and D trunks is that once a trunk is leased for whatever number of circuits less than maximum, any empty space up to its maximum capacity can be filled at zero additional cost. *Ixc refers to the Interexchange tariff which is the mileage rate per single leased private line as opposed to Telpak bulk rates. |