NBS TECHNICAL NOTE 787

Heuristic Cost Optimization of the

Federal Telpak Network
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards' was established by an act of Congress March 3, 1901. The Bureau's overall goal is to strengthen and advance the Nation's science and technology and facilitate their effective application for public benefit. To this end, the Bureau conducts

research and provides: (1) a basis for the Nation's physical measurement system, (2) scientific and technological services for industry and government, (3) a technical basis for equity in trade, and (4) technical services to promote public safety. The Bureau consists of the Institute for Basic Standards, the Institute for Materials Research, the Institute for Applied Technology,

the Institute for Computer Sciences and Technology, and the Office for Information Programs. THE INSTITUTE FOR BASIC STANDARDS provides the central basis within the United

States of a complete and consistent system of physical measurement; coordinates that system

with measurement systems of other nations; and furnishes essential services leading to accurate and uniform physical measurements throughout the Nation's scientific community, industry, and commerce. The Institute consists of a Center for Radiation Research, an Office of Measurement Services and the following divisions: Applied Mathematics — Electricity — Mechanics — Heat — Optical Physics — Nuclear

Sciences" — Applied Radiation - — Quantum Electronics 3 — Electromagnetics 3 — Time

and Frequency 3 — Laboratory Astrophysics 3 — Cryogenics n

. THE INSTITUTE FOR MATERIALS RESEARCH conducts materials research leading to improved methods of measurement, standards, and data on the properties of well-characterized

materials needed by industry, commerce, educational institutions, and Government; provides

advisory and research services to other Government agencies; and develops, produces, and

distributes standard reference materials. The Institute consists of the Office of Standard

Reference Materials and the following divisions: Analytical Chemistry — Polymers — Metallurgy — Inorganic Materials — Reactor

Radiation — Physical Chemistry.

THE INSTITUTE FOR APPLIED TECHNOLOGY provides technical services to promote

the use of available technology and to facilitate technological innovation in industry and

Government; cooperates witH public and private organizations leading to the development of

technological standards (including mandatory safety standards), codes and methods of test; and provides technical advice and services to Government agencies upon request. The Institute consists of a Center for Building Technology and the following divisions and offices: Engineering and Product Standards — Weights and Measures — Invention and Innovation — Product Evaluation Technology — Electronic Technology — Technical Analysis — Measurement Engineering — Structures, Materials, and Life Safety ' — Building Environment * — Technical Evaluation and Application 4 — Fire Technology.

THE INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY conducts research and provides technical services designed to aid Government agencies in improving cost effec- tiveness in the conduct of their programs through the selection, acquisition, and effective

utilization of automatic data processing equipment; and serves as the principal focus within

the executive branch for the development of Federal standards for automatic data processing equipment, techniques, and computer languages. The Center consists of the following offices and divisions: Information Processing Standards — Computer Information — Computer Services —

Systems Development — Information Processing Technology.

THE OFFICE FOR INFORMATION PROGRAMS promotes optimum dissemination and

accessibility of scientific information generated within NBS and other agencies of the Federal Government; promotes the development of the National Standard Reference Data System and

a system of information analysis centers dealing with the broader aspects of the National Measurement System: provides appropriate services to ensure that the NBS staff has optimum

accessibility to the scientific information of the world. The Office consists of the following

organizational units: Office of Standard Reference Data — Office of Technical Information and Publications —

Library — Office of International Relations.

1 Headquarters and Laboratories at Gaithersburg, Maryland, unless otherwise noted; mailing address Washington, D.C. 20234.

3 Part of the Center for Radiation Research.

a Located at Boulder. Colorado 80302.

* Part of the Center for Building Technology.
H* OLA-4—

'

a/oo Heuristic Cost Optimization of the

'*w Federal Telpak Network

1173

R.G.Saltman,

G.R. Bolotsky,

and

Z.G.Ruthberg

Systems Development Division

Institute for Computer Sciences and Technology

^'«/ National Bureau of Standards

Washington, D.C. 20234

""sav of

U.S. DEPARTMENT OF COMMERCE, Frederick B. Dent, Secretary

NATIONAL BUREAU OF STANDARDS, Richard W. Roberts, Director

Issued June 1973
National Bureau of Standards Technical Note lOl

Nat. Bur. Stand. (U.S.), Tech. Note 787, 52 pages (June 1973) CODEN: NBTNAE

For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C., 20402.

(Order by SD Catolog No. (13.46:7 87).

Price $0.80 domestic postpaid or $0.55 G.P.O. Bookstore.
CONTENTS

Page

ABSTRACT 1

1. INTRODUCTION 1

1 .

1

The Network Problem 1

1.

2

The Telpak Problem' s Value 2 1.3 The Solution Method 4

1 .

4

Problem Outputs 5 1 .

5

Summary of Results 5

2

.

THE KEY TABLES 6

2.1 The City Table (LOCTAB) 6 2.2 The Request Table (REQLST or WREQ) 7 2.3 The Link Table (LNKTAB) 7 2.4 The Route Table (ROUTAB) 8

3

.

THE ALGORITHMS 8

3 .

1

Choosing a Subproblem. (PREPRO) 9 3.2 The Linking Program (MAIN) 9 3.3 First Network and First Optimization (PASS1) 10

3.4 Configuring the Network for the Remaining

Requests (ADDREQ) 15

3 .

5

"Express" Links (BYPASS) 19

3.6 Rerouting Uneconomical Link Fills (PASS2 and PASS3) .. 23

4. THE COMPUTER RUNS 25

4 .

1

Programs , Subroutines , and Storage Requirements 25

4 .

2

Organization of the Runs 29

4 .

3

The Operating Environment 30

4.4 Input/Output 34

5. RESULTS 35

5.1 Costs 35

5 .

2

Connectivity 35

5 .

3

Computing Time 35
TABLES Page

1

Rate Structure for Txc and Telpak 3 2

Subproblem Selection by Circuit-Miles 9 3

Tracings of Shortest Spanning Tree 11

4 . 1 Size of Programs and Subprograms 27

4- . 2 Subprograms Employed 28

k . 3 Maximum Core Storage Required 28

5Developmental Subproblem Computer Runs 31

6Full Network Computer Runs 32

7

Storage of the Machines Used 33

8 .Summary of Results 36

8 .Summary of Network Parameters 36

9 . Computing Time Effectiveness 37

REFERENCES 38

APPENDIX A. PROPERTIES OF A SHORTEST SPANNING TREE A-l

APPENDIX B. NETWORK CHANCES PRODUCED BY DANGLING LINK ALGORITHM. B-l

APPENDIX C. REROUTING SEARCH SCHEME FOR UNECONOMICAL LINKS 0-1

APPENDIX D. SAMPLE COMPUTER OUTPUTS D-l

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. RutKberg

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 ser- vice 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, 7 7 3, 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 com- puter 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.

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 serv- ice 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. All

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

7 5 £ /mile/month in 1969, the Telpak rate in that year brought the single

circuit cost down to M- 7 £ /mile/month for complete C bundles of 60 circuits and 2 5 £ /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.
DECCO's current handling of the network involves the following

manually performed operations : keeping records on all request routings

;

reconfiguring the network in an evolutionary way by inserting configuration changes at frequent intervals. If a computerization and optimization of these procedures could be accomplished, then the following could

occur:

(1) there might be significant cost-savings to the Government, even if only a few percent of the total cost were saved;

( 2

)

re-optimizations , due to changes in tariffs , could be

carried out rapidly;

(3) the effects of proposed tariff changes could be analyzed

rapidly;

(4) the locations of inefficient sections or connections of the

network could be determined more systematically.

Table 1 Rate Structure for Ixc* and Telpak

a) Ixc Rates

Distance in Miles Cost/Mile/Month

first 25 (1-25) $3.00

next 75 (26-100) 2.10

next 150 (101-250) 1.50

next 250 (251-500) 1.05

over 500 (501- ) .75

Trunks

b) Telpak Rates

Maximum No. of Circuits

In Trunk

Trunk

Cost/Mile/Month

Circuit

Cost/Mile/Month

(filled trunk)

c

D

1

60

240

$28

$60

$0.47

$0.25
1.3 The Solution Method

Because of the nature of the Telpak tariff, direct terminal-toterminal connections could not minimize the cost of routing requests.

There are significant bulk savings when request routes or sections of

routes are combined into groups of 60 and 240. In addition, since cost

as a function of number of combined cirauits is not in a closed form

and, moreover, is non-linear, the optimization problem could not be

handled by presently available mathematical programming methods. Lastly,

the size of the network compounded the complexity of the problem. In

view of these factors , the following general decisions were made

a) Heuristic methods would be used throughout.

b) The resulting program would be tested on smaller subproblems

that could be more easily manipulated at reasonable computer

cost.

The specific method of solution used the following steps

1) Choose an initial subproblem composed of the 250 cities

(nodes) and 2394 requests that satisfy 87% of the required

circuit-miles (see 3.1 for definition) in the entire problem.

(PREPRO).

2) Find the shortest spanning tree" of this initial set of 250

cities and route the 2394 requests through it. (PASS1)

3) Decrease cost by decreasing the detour ratios*" of these re- quests via a heuristic link-adding re-routing algorithm.

(PASS1, cont.)

4) Configure, at minimum cost, the remaining 1383 cities and

3159 requests into this partially optimized network. (ADDREQ)

5) Decrease cost by introducing express trunks (long-distance,

filled or very nearly filled D trunks) via another heuristic

re-routing algorithm. (BYPASS)

6) Decrease cost by consolidating uneconomical links via still

another heuristic re-routing algorithm, done in two passes.

(PASS2, PASS3)

" See Appendix A for definitions and properties.

'• t> j. n j-- c r> no. of mi. in request rt. through network "" Detour Ratio of a Request = . _. . ,* , —E z airline distance of request
1.4 Problem Outputs

The main outputs containing the problem solution are as follows

(See Appendix D for sample printouts .

)

1. The network links, their respective circuit fills, and their

Telpak breakdown (C's, D's, Ixc's). A link is a unique direct connection between any two nodes and is assumed to travel in a straight line between the nodes.

2. The route of each request, listed by means of the links used.

Links are identified by their two nodal end points.

3

.

The total network cost (TOTCST) , calculated from the

individual link costs.

Additional useful constants of the solution are discussed in Section 4.

1 . 5 Summary of Results

The complete problem containing 1633 cities and 5552 requests was configured by a FORTRAN IV computer program developed and run on IBM

360/91 and /95 equipment. (Initial development runs were made on a

UNIVAC 1108.) The complete program took about 23 hours of CPU time ac- cumulated over 44 separate runs. A maximum of 1,234,040 bytes of core storage were required for any one run . ( See 5 . for complete results .

)

The number of required wire-miles configured were 9,345,396, and

cost of the configuration was $3,528,318 per month rental charge. This

yields a cost per required wire mile of $0.3775. The miles travelled

by the circuits in the configuration were 11,314,383 which yields a cost

per travelled wire-mile of $0.3118. The overall detour ratio (the travelled wire-miles divided by the required wire-miles) was 1.211. This means that the average circuit travelled a 21 percent greater distance

than the direct point-to-point distance.

Although the cost per required wire-mile is clearly the best indicator of the effectiveness of the algorithm, the data now collected

under the present manual system does not permit that number to be calculated for the manually-obtained results. The only computed data

available from the present manual system that is approximately equivalent are that 11,965,323 travelled circuit miles were configured at

cost per travelled wire-mile of $0.3153. This number is approximately

the same as that achieved by the computed configuration.

The cost of the approximately equivalent manual configuration was

$3,772,701.25 or somewhat more than the computed configuration. However, the manual configuration included a small number of multi-point

circuits (circuits with more than two terminations) which were not included in the computed configuration.
In addition, the total manual configuration includes an extra

7,308,729 travelled miles of GSA circuits not configured in the com- puter problem (and not included in the cost above) . The total configuration problem thus is about 60 percent larger than actually configured

by computer. It may be that the least economical circuits configured by

the computer program might have had the benefit of the use of bulk

trunks had the GSA portion of the network been included.

In summary, an heuristic optimization program has been success- fully run for a network of an extremely large size. A program for this

size network has rarely if ever been attempted before. The inclusion of

this program in the operational activities of DECCO is possible, but a

systems analysis of DECCO data flow and operations must be accomplished,

and a step-by-step conversion procedure designed, before installation

can be achieved.

2.0 THE KEY TABLES

In carrying out the solution method outlined in Section 1 . 3 and

generating the outputs of Section 1.4, four very important tables of

information are initiated and manipulated. The City and Request Tables

contain the bulk of the input data. During the course of the program

the Request, Link, and Route Tables collect the current network solution

information. The final values in these last three tables contain the

optimal route and link information. The final network cost is always

calculated from the final Link Table circuit fills and the rate structure. (See Table 1. ) These tables will now be described.

2.1 The City Table (LOCTAB)

The given information for each city (node) consists of a four

letter identification code (devised and used by DECCO) and a pair of

integer geographic coordinates expressed in miles. Each city record in

the table is five words long and contains:

1. City A - code name (given)

2. H. - horizontal coordinates in miles (given)

3. V. - vertical coordinates in miles (given)

4. Working word used during the program
2.2 The Request Table (REQLST or WREQ)

The given information for each request consists of the coded

names for the two terminal cities and the number of wires5 ' (sub-voice

grade circuits) required. Each request record is eight words long and

contains

1. Terminal City A - code name (given)

2. Terminal City B - code name (given)

3. Number of wires" required (given)

4. D. R

- Airline distance between Cities A and B, calculated by

the Pythagorean Theorem and rounded up twice according to the

procedure spelled out in the F.C.C. tariff regulations.

5. Detour Ratio (Calculated)

6. Working word used during the program

7. Number of links in the request route (from program)

8. Pointer to first word of request route in Route Table

(from program)

Note that REQLST is an integer array equivalenced to the real array WREQ

so that the proper mode (integer or real) could be used at various

points in the FORTRAN program. Also note that words 7 and 8 of a record

contain the final output information necessary for reading the Route

Table (See Figure 1 and Section 2.4).

2.3 The Link Table (LNKTAB)

The Link Table is one of the two key output tables of the problem. It always contains the current information on the links chosen for

the network routing configuration. The record for each link contains

the following seven words

1. End City A - code name

2. End City B - code name

3. Number of wires in use (fill)

4. Airline distance between end cities A and B

"In the final version of the program there are 12 wires per

voice-grade circuit. This constant Is stored in NWIRE.
5. Temporary added fill (for rerouting)

6. Working word used during program

n II !! I! t! I!

The Link Table is alphabetized on Cities A and B for purposes of program searches of this table.

2.4 The Route Table (ROUTAB)

The Route Table is the second of the two key outputs of the problem. It consists entirely of pointers to the links in the Link Table

that are in each route of a request. This indirect addressing scheme uses word 7 in the Request Table for the length of the request route

(in links) and word 8 of that table for a pointer to the first word of

that route in the Route Table (See Figure 1).

Request Table Route Table Link Table

Request

Record

1 A

2 B

3 . 4 . 5 . 6 . _. 7 3-^1

8 7

-""^

Figure 1 Indirect Addressing Scheme for Route of a Request

3.0 THE ALGORITHMS

The solution to this problem involves the sequential running of

six programs. The first one (PREPRO) is a program that selects from

the 1633 cities and 5552 requests a sub-problem of 250 cities. The

five remaining programs (PASS1, ADDREQ, BYPASS, PASS2, and PASS3) are

linked by a simple MAIN program. These five programs call upon an additional twenty-one subroutines to perform all the computations

needed. A run-time generated restart capability was added to
accommodate the long running time needed (22.8 hours of running time for

the entire problem on the 360/91,95). Whenever a restart was implemented, magnetic tapes were used to store the current key tables.

3.1 Choosing a Subproblem (PREPRO)

The programs PASS1, BYPASS, PASS2, and PASS3 were developed and

tested on subproblems of the large problem. In order to form meaningful

subproblems, the 1633 cities were ordered according to their required

number of circuit-miles. This number was determined for each city

(node) by calculating the circuit-miles (number of circuits x airline

distance) for each request and then summing the required circuit-miles

for all requests terminating at that city. Then for a problem with some number of chosen cities , only those requests were picked that had both

terminal cities chosen. Table 2 shows the percent of total circuitmiles considered in each subproblem. PREPRO accomplished Step 1 in the

solution method of Section 1.3.

As a measure of the fraction of the network contained in each

subproblem, the following quantity was calculated:

Circuit-Miles = # of Circuit-miles of Included Requests x 100

# of Circuit-miles of All Requests

It includes the circuit-miles of only those requests which can be routed

entirely within the subproblem network. It was decided to use a network

of 250 cities as a subproblem to start with in the final solution.

Table 2 Subproblem Selection by Circuit-Miles

No. of No. of % Circuit-Miles

Cities Requests

50 390 45

100 958 66

150 1520 76

200 2068 83 250 2394 87

1633 5552 100

3.2 The Linking Program (MAIN)

The MAIN program initializes the City and Request Tables by reading in the given city and request data. It also reads in four variable

constants required by the programs. These constants are: XMDR, NOKC,
XSIZE, and NWIRE. Their functions will be described later. The rest of

MAIN is used to sequentially invoke the programs PASS1, BYPASS, PASS2,

and PASS 3.

3.3 First Network and First Optimization (PASS1)

PASS1 contains three distinct segments to accomplish Steps 2 and

3 in the solution method of Section 1.3. These segments are:

1. Constructions of the shortest spanning tree.

2. Routing of requests over the spanning tree.

3. Addition of links by decreasing detour ratios of requests.

3.3.1 Construction of the Shortest Spanning Tree : The initial

network is established by linking the 250 city subproblem by a shortest

distance spanning tree* formed from the complete graph. The method used

is essentially the one outlined in reference [1], Construction B, and

uses the property that every node is connected to its closest neighbor

node. One starts the construction by marking an arbitrary city (the

first city in the City Table) 'in' the network and the rest of the cities

'out' of the network. At each iteration the closest 'out' city to the

set of 'in' cities is found and is connected to its closest 'in' city.

This newly established link is then sorted into the Link Table alphabetically and the ' out ' city marked ' in ' . This procedure terminates when

all the cities have achieved an 'in' status. Searching through the 'in'

cities was minimized by a judicious use of the minimum distance values

found in each iteration. See Figure 2 for a sample construction.

3.3.2 Routing Requests Over the Spanning Tree : This part of

PASS1 uses the shortest spanning tree properties that (a) there is only

one path between any pair of cities and that (b) every node is reachable from every other node. (See Appendix A) Requests are routed over

the entire tree by repeated tracings of chains"* in the tree, each such

tracing starting from a different root city. A sufficient number of

chains are considered to have been traced when all requests have been

given paths through the tree. The particular root city chosen for each

tracing is always the one with the largest number of unrouted requests

for which this city is an end point. This choice maximizes the possible

number of requests that can be routed via each tracing.

Starting at a root city, the program finds all chains in the

spanning tree originating from that root city. This procedure finds the

only route through the spanning tree between any two cities on a chain.

*See Appendix A for definition and properties.

*':The word 'chain' is used interchangeably with 'path' throughout

this paper. A chain may include a route or be included by a route.

10
Iteration

1

2

3

4

Figure 2 Shortest Spanning Tree Construction

"in"

Cities

A

A,E

A,E,C

A5 E,C,I

A,h ,L

,

B,D

"out"

Cities

B,C,D,E

B,C,D

B,D

D

Added

Link

AE

AC

BC

AD

Table 3 Tracings of Shortest Spanning Tree of Figure 2

Requests

1. A to B

2. A to C

3. B to C

4. D to E

Root City Tracing Requests Routed

A Chain 1. AC, CB A tc B, A to C, B to C Chain 2. AD none Chain 3. AE none D Chain 4. DA, AC, CB none Chain 5. DA, AE D to E

11
If any route so found is associated with a real request for service as defined by its terminal points, then the initial routing of the request

has been determined. The program goes to a different root city when all

chains from that root city have been traced. (See Table 3 for the tracings of Figure 2 ' s shortest spanning tree . ) Note that not only is the

Route Table initialized here, but the initial detour ratio for each re- quest and the initial accumulated circuit fill of each link is computed

and stored in the proper key tables.

3.3.3 Decreasing Detour Ratios of Requests : Before actually

proceeding with this phase of the program., the COST subroutine is called

in to establish the initial cost of this initial network. This is done

by breaking down the link fill values (found in the Link Table) into

Telpak units (Ixc, C, D) that minimize the cost per link. This calculation uses the Telpak rate structure (See Table 1). The sum of these

link costs is then considered the initial cost of the network and is the

quantity to be reduced by any optimization procedure.

The initial configuration of the network is extremely inefficient. Many requests have very high detour ratios, meaning that they

travel an extremely circuitous route from one end point to the other.

The purpose of this first cost reduction program is to reduce the detour

ratio by adding links that shorten the mileage travelled by requests.

In order to investigate only that part of the network in ±he vicinity of

the request being shortened (the primary request ) (See 3.3.3.1) an

ellipse is employed whose foci coincide with the end points of the primary request. Only those nodes of the network that fall on or within

the ellipse are considered for this subproblem. Initially, the ellipse"

is established with a relatively wide minor axis. If this results in

too many cities within the ellipse than can be easily handled by the

subproblem, the minor axis is reduced incrementally until an acceptable

number of cities is obtained. The acceptable number of cities is established by NOKC, which Is set at 20. In addition, the ellipse must be

small enough so that at least one city of the route of the primary re- quest falls outside the ellipse. This fact is necessary if the linkaddition program is to work properly.

3.3.3.1 Choosing Candidate Links . The primary request to be

re-routed is always one that has not yet been a candidate for rerouting,

and which has the largest detour ratio larger than XMDR = 1.15. This

value of XMDR was found by trial and error on the basis of network cost

saved versus computer time used.

For the cities contained within the ellipse initially, a

"The size of the ellipse used can be identified by its own detour

ratio . For an ellipse, the detour ratio is defined as the sum of the

distances from the foci to any point on the ellipse divided by the distance between the foci. For any ellipse, the sum of distances to any

point on the ellipse from the foci is constant regardless of the point

chosen.

12
completely connected network is formed. This means that fictitious

links are added temporarily to those already connecting the cities within the ellipse. A completely-connected network of 20 cities contains

190 links. A larger number of cities would begin to produce an unac- ceptably large number of links. Real links in this network are, for the

purposes of this subproblem, given a distance value of zero. Fictitious

links are assigned their real mileage. Then, using the algorithm of

Dantzig [2] for finding the shortest route through a network, the subroutine MINPA finds the shortest path in the subnetwork between the

terminals of the primary request. The method consists of tracing multiple paths from the starting terminal city of the request and extending

these paths at each step with a link or links that result in a minimum

cumulative length path (or paths). The first path to reach the second

terminal city of the request is the minimum length route sought.

The device of assigning real links a length zero provides

the answer in terms of the minimum extra real mileage that re-connects

the terminals of the primary request. This procedure takes advantage

of any links in the route of the primary request that fall within the

ellipse, as they have zero length for this problem. Thus, the links in

the minimum length path need not include the direct connection between

the foci cities. (See Figure 3a and 3b for illustration). The subnetwork's fictitious links that lie on the new shortest path for the primary request are then the candidate links being sought.

3.3.3.2 Testing Candidate Links . The shortest path between the terminal nodes in the primary request establishes the fictitious links on this path as candidate links for adding to the network.

The next step is to re-route the primary request and other secondary

requests passing through the ellipse, through the candidate links to

determine if a reduced network cost will result. The re-routing results, in most cases, in reduced detour ratios and therefore in reduced

cost. The basic subnetwork used for this test is the same as the subnetwork of 3.3.3.1 with the following two changes

:

1. All fictitious links that are not candidate links are removed

.

2. All primary request links that are not in the above

ellipse are added.

All requests having at least two links in this basic subnetwork are called secondary requests and are candidates for rerouting and reduction of their detour ratios. These requests include the primary request. Since true distances are now involved, all link lengths are restored to their true values.

For each secondary request a true shortest route is now

sought via subroutine MINPA. The subnetwork used consists of the basic

subnetwork plus any of the secondary request route links not in the

basic subnetwork. If this shortest route reduces the detour ratio of

13
Network A,B,C,D,E,F,G,H,I,

J,K,L

Primary Request (A,B) Route [A,B] = AC,CD,DB

Ellipse has foci A,B

and eccentricity e> 172

Figure 3a Network with Ellipse about nodes A,B

Real links: DB Fictitious links: AD,AB,AH,DH,BH

Shortest route for [A,B] : AD,DB

Figure 3b Subnetwork for Finding Shortest Route for Primary Request (A,B)

14
that secondary request, the new route is temporarily accepted (see Fig- ure 4a and 4b for illustration). After all secondary requests are tested (including the primary request) , and the appropriate new routes temporarily accepted, the final new network cost is compared to the old

one. If a net saving is achieved, the candidate links and their accom- panying secondary request route changes are accepted permanently.

After all requests with detour ratio greater than 1.15 (see

3.2.1) are put through this two-part process, PASSI ends. Note that no primary request is tried a second time after having once failed to

produce a saving, even though the network changes after each successful test of candidate links. The reason for this decision was to

shorten the execution of this time-consuming part of the program. In

most cases, each successful test of candidate links adds just one new

link to the network.

3.4 Configuring the Network for the Remaining Requests (ADDREQ)

Immediately after PASS1, the remaining 1383 cities and 3158 re- quests are read into the memory and configured into the partially optimized 250 city network, one request at a time. These requests, which

have at least one city not in the network, are taken in descending order

of their circuit-miles (see 3.1). Every such request is routed via a Minimum Cost Route Algorithm which, for each request, adds at least one new city and one new link with a minimal increase in the cost of the

network. If the resulting request route ends in a dangling link (a link

ending in a city with no other links connected at that city) , the route

is further optimized by a Deflection Link Algorithm that eliminates the

dangling link while reducing the network cost. It was decided to use ADDREQ after PASS1 because the Route Table, which is the largest of the

key tables, first reaches small enough size at this point.

3.4.1 Minimum Cost Route Algorithm : For each request to be

added to the network, an appropriate subnetwork is established. Each of

the two terminal cities of the request is linked to its five closest

cities in the current network. These cities (all real) and links (both

fictitious and real) form part of the subnetwork. Next, the direct link

between the request terminal cities is added to the subnetwork. Then an

ellipse, with a detour ratio XSIZE<1.25, is drawn using the two terminal

cities of the request as foci. (See Page 12) Requests lying in the

sparser northwest area of the network use a wider ellipse with

XSIZE<1.6. (These values were obtained by experimentation.) All additional cities in the network that are in or on this ellipse are added

to the subnetwork. Finally, all real links of the network that con- tain at least one city in this subnetwork are added to the subnetwork.

(See Figure 5a and 5b for illustration .

)

Using cost rather than length as the pertinent link characteristic, the program now finds a mirdmum cost path for the request in the

above subnetwork. This minimum path algorithm Is again based on the

15
Primary Request Links:

AC, CD, DB

Shortest Route Link:

AD

Figure 4a Basic Subnetwork Used for Rerouting Secondary Requests

•B

Original Route of (J,K)

[JD,DC,CA,AI,IH,HK]

New Route of (J,K)

[JD,DA,AI,IH,HK]

Figure 4b Subnetwork Used for Rerouting Secondary Request (J,K)

16
'OUT' city = I

'OUT' Recuest = R

ID

Fictitious Links = L

TJ , L,^, LTM, !*-._, L-.

Ellipse Foci = I and D

Figure 5a Network with ^ict-itious Links, 'Out' City I, and Subnetwork

Ellipse for Minimum Cost Route Algorithm

17
Minimum Cost

Route of R

ID ID ^C ICD^

Figure 5b Subnetwork Used For Finding a Minimum

Cost Route for Reauest from I to D

Added:

City I

Ldjik IC

Route [IC, CD]

Figure 5c Reconfigured Network with Request I to D

18
Dantzig algorithm E2] used in PASS1 (see 3.3.3.1) and is contained in

subroutine MENPA1. After finding the minimum cost route for the new

request, the four key tables are appropriately updated with the new

city, request, link, and route data. (See Figure 5c for illustration.)

The total network cost is also updated.

3.4.2 Deflection Link Algorithm : If the minimum cost route

subroutine makes either terminal city of the new request into a dangling (terminal) node of the network, a second optimization procedure

occurs before finalizing the route of the request. The subnetwork used

for this algorithm always consists of the dangling node A, the corres- ponding dangling link AB, the network interior node B, and a network

link BC out of B. (See Figure 6a.) An attempt is then made to convert

the dangling node into an interior node of the network by deflecting the

traffic in BC into a new link AC via a route consisting of BA, AC. (See

Figure 6b. ) The deflection link AC and the corresponding route changes

which produced the largest cost saving are then accepted into the network, as well as the final route of the new request (which may or may

not use that deflection link AC) . If no cost saving can be achieved by

this process, the original minimum cost route of the new request is

accepted and, in addition, the dangling node is connected to its two

closest network nodes by links with zero fill. This last step allows

future network changes to possibly make the dangling node into an interior node and thus achieve more economic bundling of circuits. (See

Appendix B for description of network changes accompanying the application of this algorithm.

)

3.5 "Express" Links (BYPASS)

Further reduction in the cost of the network is attained by substituting "express" links (direct links) for chains of links containing

the same number of D Telpak bundles. The cost reduction occurs because

the length of the express link is less than the length of the sequence

of links that it replaces. The object of BYPASS is to find a candidate

chain, to identify the routes that use the chain, and to test for a cost

reduction when bypassing the chain's traffic through a direct link.

Every successful bypass either introduces a new link with an appropriate

number of D Telpaks or adds that number of D Telpaks to an existing

express link.

3.5.1 Finding the First Candidate Chain : The program starts by

determining the number L, which equals the largest number of D Telpaks

in any one link of the entire network. If at least one C Telpak is also

present in any link having L 'D Telpaks' this value of L is increased by

1. The route of each request is then examined to find the longest

sequence of links with fills >_ 240L- Any request that has only one link

in its route is automatically eliminated from the search. The longest

sequence of links with fills •> 24 OL is the candidate chain being sought.

A table of chains that failed to produce a cost saving is developed in

FCHAIN and checked against a current chain being tested (via function

19
network link

network node

dangling link

network node

C

lo ) Before Deflection

removed network link

added deflection link

(b) After Deflection

Figure 6 Adding a Deflection Link

20
FTEST) so that no chain is found and run through this program more than

once.

3.5.2 Finding Routes that Contain a Candidate Chain : A search

is then made for all the request routes that completely contain the can- didate chain (via subroutine CNTAIN) . Each time such a request is

found, it is placed with its request fill, in a table FILTAB. This

table is arranged in descending order of fill requirements (in wires).

The required fills in this table are also accumulated and stored in a word SUMC.

3.5.3 Determining the Bypass Fill and Its Corresponding

Requests : If SUMC contains an integer multiple of 240 circuits, the

bypass link is given a fill of SUMC and all requests in FILTAB are

rerouted. If SUMC does not contain an integer multiple of 240 circuits, a choice must be made between the two integral multiples of 240 that

bound SUMC. The word MJSUM is set to 240 times the lower bound.

An additional requirement that must be satisfied in this process

is that all circuits of a request must be bypassed completely or not

bypassed at all. Requests cannot be split. The word CUMSUM accumulates the fill requirements of requests in FILTAB in descending order

of magnitude until the largest CUMSUM is obtained such that CUMSUM <_ NUSUM. Then CUMSUM and SUMC are examined to find the one closest to an integer multiple of 240 circuits. If CUMSUM is the closer one, the program attempts to bypass NUSUM of the D Telpaks and alters routes of

those requests in FILTAB that contributed to the value of CUMSUM. If

SUMC is the closer one, the program tries to bypass NUSUM+1 of the D

Telpaks and reroutes all requests in FILTAB. (See Figure 7)

3.5.4 Testing for Cost Savings : Using the end points of the

candidate chain as the terminals of the bypass link and the fill just

determined in 3.5.3, the cost of the network with the changed routes

of requests is compared to the old network cost. If a saving is

achieved, the bypass link is accepted and the route changes are made

permanent. If no saving is achieved in bypassing the candidate chain, a subset of that chain is chosen as a possible candidate chain and the

procedure just outlined is repeated.

3.5.5 Choosing a Chain Subset : The scheme for choosing subsets

of a candidate chain consists of removing links from the ends of a chain

in all possible ways so that the chain length is sequentially diminished by one each time. (See Figure 8 for details.) When a subset of a primary chain is bypassed, the largest of the unused chains on either

side of the subset is selected for the next trial chain and is treated

like the first candidate chain.

3.5.6 Finding Other Candidate Chains : After the first candidate

chain has been processed by the program, all other candidate chains with

fill >_ 240L are sought for and checked out. When no more chains are found for this value of L, L is reduced by 1 and the whole procedure

21
(N+l) x 240

SUMC

N x 240

(MJSUM)

CUMSUM

I < II -»- Bypass N 'D Telpaks'

II < I + Byoass (N+l) 'D Telpaks'

Figure 7 Bypass Pill Selection

iteration Length of Chain Beginning Link

N-3

N~3

N-3

Ending Link

1 NJ 1 N

2 N-l 1 N-l

3 N--1 2 N

u N-2 1 N-2

s

>T 9 N-l

6 1NJ -9 3 M

N-3

N-2

N-l

N

(M-1)(M) N-l

Figure 8 Scheme for Choosing Chain Segments

22
is repeated. The BYPASS program terminates when L = 1.

3.6 Rerouting Uneconomical Link Fills (PASS 2 and PASS 3)

The object of PASS2 and PASS3 is to reroute some link fills so that the maximum number of network links take advantage of the Telpak

bulk savings. In order to do this it is necessary to determine which

links have an uneconomical "overflow"" of circuits, to find and reroute

the requests that create the "overflow" , and to test the rerouting for

cost savings. The rerouting is done within a subnetwork via the mini- mum cost route subroutine (MENPA1) . The major difference between PASS2

and PASS3 is that PASS2 considers an overflow fill less than 30 circuits

(one half of a C trunk) to be uneconomical while PASS3 uses a value less

than 92 circuits (about one and one-half C trunks). PASS2 attempts to

eliminate Ixc's and uneconomical (half-filled) C trunks. PASS3 attempts

to eliminate full C trunks. Both attempt to fill more D trunks. A

minor difference between the two passes lies in the searching of the re- quests for choosing those that cause the overflow.

3.6.1 Choosing the Uneconomical Link and Its Overflow Fill

Value : The overflow value F of each link is computed (via subroutine

C0ST1) and stored in the last word of each link record. In PASS2 the F value for a link is the number of circuits remaining after removing all

full D and C Telpaks (0 < F < 30). ** PASS 3 uses an F value obtained by

removing all full D trunks and all but the last full C trunk (0 < F < 92). The untried link that has the largest F value is then tagged the

uneconomical one and its corresponding F value becomes the maximum

number of circuits to be rerouted (FMAX).

3.6.2 Choosing the Rerouting Subnetwork : Two intersecting circles are drawn whose centers are the uneconomical link's end nodes and

whose radii are the link's length (in miles) plus 500. The subnetwork

then consists of all nodes in or on these two circles and all links

which have at least one node in this node set. The current uneconomical

link is deliberately deleted from the subnetwork so that it will not be

used in the rerouting. If the subnetwork's allowable node table

(OKCTYS) or link table (OKLNKS) is exceeded (250 nodes, 2,600 links),

the circle radii are reduced by 20 miles and the procedure repeated until a satisfactory size network is achieved (see Figure 9).

3.6.3 Choosing Requests for Rerouting in PASS2 : In rerouting

requests that contribute to the overflow fill FMAX of the uneconomical

link, the largest number of circuits that is removed is FMAX+4. Therefore all requests containing the uneconomical link and requiring

*An 'overflow' fill is the number of circuits in a link, modulo 240. "'Note that C0ST1 assigns another C Telpak to any link having an overflow greater than 30 circuits.

23
p Lgure 3 Subnetwork .or perout me Unecomi cal Links

2"+
<FMAX+4 are stored in a 'try-table in descending order of number of circuits. The program attempts to reroute a single request from the trytable with an overflow fill, FIRY, ranging from MAX to FMAX+4. Once

an FTRY value fails to achieve a saving, no other request with that FTRY

value is tested. If none of these reroutings produces a saving, a com- bination of requests in the try-table, whose requirements have a com- bined fill <FMAX, is tested. (See Appendix C for scheme.) If a request

or a combination of requests produces a saving, the new route or routes

are accepted.

3.6.4 Testing for Cost Savings in PASS2 : To determine if a saving is achieved, the cost of the network with the new route of a re- quest is compared to its cost with the present route. This is done by

comparing the cost of adding the request with the new route (in CUMCST)

to the cost of adding the request with the present route (in RESAVE).

Whenever CUMCST is smaller than RESAVE, the new route of the request

is producing a saving, and is thus accepted permanently3.6.5 Choosing Requests for Rerouting and Testing for Cost

Savings in PASS

3

: In this last program of the Telpak problem, all re- quests whose routes contain the uneconomical link and whose requirement

is less than EMAX are stored in a try-table in descending order of fill

requirements. A set of requests is now sought in the try-table such

that the sum of their requirements is minimally greater than FMAX. If no such set exists, a single request minimally greater than FMAX is

used. This request set or the single request is then rerouted and

tested for cost savings just as in PASS2. (See 3.6.4.)

3.6.6 Terminating PASS 2 and PASS

3

: Every time a rerouting is

permanently accepted , new overflow values , F , are calculated for the

network links. If the new F value of a link Is greater than its old

value, and that link has already been tried, it is allowed to be tried

again by marking its record 'untried'. The program terminates when no more untried links have overflow fill values greater than zero.

4.0 THE COMPUTER RUNS

In order to understand the runs that were made for this problem,

it is necessary to discuss the computer programs and subprograms, the

organization of the runs, the operating; environments and the Input/

Output used. Whenever possible the pertinent information has been

placed in tables to summarize this information.

4 . 1 Programs , Subroutines , and Storage Requirements

The computer programs embodying the algorithms of Section 3 are

all written in Fortran IV for ease of transfer from one machine to another. The program PREPRO (see 3.1) ordered the 1633 cities and 5552

requests into nested subproblems of 50, 150, 200, and 250 cities. The

solution to the entire DECCO network configuration involves the six

programs MAIN, PASS1, ADDREQ, BYPASS, PASS2, and PASS3 described in

25
Section 3 , and twenty-one subprograms whose purpose will now be described very briefly. The number of statements and the storage requirements for these will be found in Table 4.1. The subprograms used in

each maj or program segment are shown in Table 4.2, and the core storage

requirements for each maj or program segment are shown in Table 4.3.

4.1.1 Subroutine CDISS : This routine calculates the distance,

in miles, between two cities. It uses the city's coordinate values for

the calculation.

4.1.2 Subroutine CLOCK : This routine is used at predetermined

restart points in the program. It obtains the remaining CPU time

allowed the program for the current run and decides whether to continue

running or to dump the vital information on tape and stop.

4.1.3 Subroutine CNTAIN : This routine is called by BYPASS to

examine a request route for containment of a candidate chain.

4.1.4 Function COST : This function finds the total cost of the

network at any given time.

4.1.5 Function C0ST1 : This function is similar to function COST

but has some different options.

4.1.6 Subroutine DEFLCT : This routine is called by ADDREQ to

attempt to convert an end city of a newly added request from a peripheral to an internal city of the network.

4.1.7 Function irTJiST : This function examines a variable length

table of failed chains for containment of a given chain. It is similar

subroutine CNTAIN.

4.1.8 Subroutine GAKBAG : This routine condenses the route table

whenever the program finds itself at the end of that table. Discarded

routes are marked by negative numbers and must be periodically cleared

out.

4.1.9 Function IXC : This function computes the cost of one circuit, using the Ixc cost structure (see Table 1).

4.1.10 Function LKCOST : This function computes the cost of one

link by using the Telpak rate structure of Table 1 and dividing the fill

among D's, C's, and Ixc's so as to minimize the cost.

4.1.11 Subroutine NTNLNK : This routine finds the closest 'out' city to a given 'in' city of a network. It is used in constructing the

minimum spanning tree.

4.1.12 Subroutine MTNPA : This routine finds the shortest path

length in miles between any too cities in a given network.

26
Table 4.1 Size of the Programs and Subprograms

Program or No. of Source Storage Required

No. Statements

Subprogram (Fortran IV) (Bytes)

1. MAIN 103 2,368

2. PASS1 732 30,168

3. ADDKEQ 421 8,172

4. BYPASS 359 5,792

5. PASS2 288 5,216

6. PASS3 323 7,060

1. CDISS 8 470

2. CLOCK 6 288

3. CNTAIN 30 684

4. COST 39 912

5. C0ST1 70 1,376

6. DEFLCT 382 27,300

7. PTEST 37 596

8. GARBAG 57 1,162

9. IXC 24 662

10. LKCOST 43 1,014

11. MINLNK 20 386

12. MINPA 89 1,234

13. MINPA1 101 1,164

14. NULINK 60 980

15. PROUT 103 3,728

16. PROUT3 77 3,008

17. SAVEIT 23 812

18. TEMPLK 24 350

19. TESTLK 46 816

20. TRY 75 1,366

21. TRY1

Total

65 1,246

3,605 108,330

27
4 . 2 Subprograms Employed

Run Type Programs Used" Subprograms Used" Storage (bytes)

PASS1 1, 2 I, 2, 4, 8, 9, 10,

II, 12, 14, 15, 17

44,184

ADDREQ 1, 3 1, 4, 6, 8, 9, 10

13, 14, 15, 16, 17

18, 19

52,918

BYPASS 1, 4 1, 2, 3, 4, 7, 8,

9, 10, 14, 16, 17

19,468

PASS 2 1, 5 1, 2, 4, 5, 8, 9,

10, 13, 15, 17, 20

20,538

PASS 3 1, 6 1, 2, 4, 5, 8, 9,

10, 13, 15, 17, 21

22,262

* The numbers refer to the programs and subprograms listed in

Table 4.1.

Table 4 . 3 Maximum Core Storage Required ( in bytes

)

PASS1 ADDREQ

BYPASS,

PASS2 OR PASS3

Program

System Routines

Common Blocks

Total

44,184

21,078

586,936

52,918

21,078

938,832

22,262

21,078

1,190,700

652,198 1,012,828 1,234,040

28
4.1.13 Subroutine MINPA1 : This routine finds the minimum cost

path in dollars, between any two cities in a given network. It is

similar to subroutine MINPA.

4.1.14 Subroutine NULINK : This routine finds the location of a new link in the alphabetized link table and, if desired, inserts the new link in the table at that position.

4.1.15 Subroutine PROUT : This routine is the general print-out

routine for all the programs and contains numerous options for printing

results of the computer runs.

4.1.16 Subroutine PROUT

3

: This routine is a print-out routine,

especially designed for the ADDREQ program.

4.1.17 Subroutine SAVEIT : This routine dumps the contents of the common blocks on magnetic tape when a check on the computer clock shows

that the allowable time for a run has almost expired.

4.1.18 Subroutine TEMPLK : This routine is called by ADDREQ to

link the five closest cities to an end city of a new request.

4.1.19 Subroutine TESTLK : This routine is called by ADDREQ. It either computes the cost of a subnetwork link with permanent fill and

places the fill requirement of the new request in a word of the link

record, or, if the link is not in the permanent table sets its cost to zero and places the link record in the temporary block of the link

table.

4.1.20 Subroutine TRY : This routine is used by PASS2 to find a

cheaper route for a request that is presently routed via an uneconomical link.

4.1.21 Subroutine TRY1 : This routine is used by PASS3 for a purpose similar to subroutine TRY.

4 . 2 Organization of the Runs

4.2.1 The Developmental Subproblems : The program was Initially

tested on small networks on the UNIVAC 1108 computer at the National

Bureau of Standards before any production runs were attempted. Then,

to eliminate further bugs and attain more confidence in the program's

operation, the nested subproblems of the DECCO network were run on various IBM 360 machines (see Section 4.3). At this point all the programs and subprograms except ADDREQ and its required subprograms DEFLCT.

PR0UT3, TEMPLK, and TESTLK were developed and debugged. The smaller

developmental subproblems (50 and 150 cities) were completed in one run

and used the entire program as developed to this point. The larger

developmental subproblems (200 and 250 cities) used the entire program
to this point but had to incorporate a restart feature in MAIN for the

completion of PASS1.

Table 5 shows various parameters associated with developmental

subproblem computer runs for 50, 150, 200, and 250 city problems. As

can be seen, a complete 250 city problem run took about 82 minutes of

computer time to complete. The 200 city problem was done with three

restarts of PASS1 while the 250 city problem used four restarts. A

restart in PASS1 always began at the point at which a new primary request was selected for re-routing.

4.2.2 Full Network : For the configuration of the entire DECCO

network, the result of the 250 city problem after the completion of

PASS1 was employed as a point of departure. The application of the

program ADDREQ and its necessary subprograms were completed with seven- teen restarts. (The number of restarts was determined by the availability of the computer.) An iteration here consists of the configuring

of a new request into the network. When a restart occurs, it is caused

to occur at the beginning of an iteration. BYPASS and its subprograms

required one run. An iteration here is defined as the selection of a

candidate chain and testing its segments for a bypass link substitution.

A restart capability was programmed but was not called in by this execution. The application of PASS2 and its subprograms was accomplished

with fourteen restarts while PASS3 used four restarts. PASS2 and PASS3

define an iteration as finding a link with overflow circuits and attempting to redistribute the overflow more economically. Note that the

MAIN program contains all the restart logic and it is the restart ver- stion of MAIN that is included in the program size data of Table 4. Table 6 shows the computer time required to complete the full 1633 city

configuration and optimization problem. Individual run times are given.

4 . 3 The Operating Environment

4.3.1 The Machines Used : The large core and time requirements

of the DECCO network and its larger subproblems required the use of a large machine. Three different IBM 360 's were used, depending on the

availability of the machines. Table 7 lists the storage capabilities

of the computers used while Table 5 includes a reference to the machine

used for each run.

30
Table 5 Developmental Subproblem Computer Runs

Size of Network

o Machine I^Lnimum Detour Run C.P.U. Time

Cities Requests Used Ratio (XMDR) No. Program (min.)

(Spanning Tree

/ PASS1 ( pluS Rout;illg

(Deer. Detour

.07

1

I ( Ratio 1.53

50 390 2 1.00 1 < BYPASS

PASS2

PASS3

0.05

0.03

0.03 Total 1.71

(Spanning Tree

| PASS1 ( pluS Routing 0.53

1 (Deer. Detour

1 ( Ratio 7.80

150 1520 2 1.20 1 ( BYPASS

PASS2

PASS3

0.38

0.25

2.90

Total 11.86

(Spanning Tree H PASS1 ( pluS ^^g

(Deer. Detour

( Ratio

2.62

9.72

2

tt 11.52

200 2028 2 1.15 34

•I

ti

tt BYPASS

PASS2

PASS3

12.23

10.00

1.18

1.40

3.40

Total 52.07

(Spanning Tree >( PASS1 ^ plus luting

(Deer. Detour

( Ratio

3.95

22.67

2

tt 12.25

250 2394 2 1.10 34

5H8 (

it

tt

tt BYPASS

PASS 2 PASS 3

7.10

11.38

12.28

1.75*

2.37

8.03-

Total 81.78

See Table 7 for code numbers for the machines used.

Charged time. CPU time unavailable.

31
Table 6 Full Network Computer Runs

Size of Network

Added Total I^chine Run. C.P.U. TijiB

Cities Requests Requests Used No. Program (min)

250 2394 2394 2 1-5 (See Table 5 for breakdown) Total 69.63

250+ 162 2556 3 1 ADDREQ 7.51

157 2713 2 7.50

134 2847 3 7.51

100 2947 4 4.35

i 199 3146 5 6.47

1 200 3346 6 7.12

200 3546 7 7.08

200 3746 8 7.29

200 3946 9 7.14

200 4146 10 7.60

200 4346 " 11 7.97

200 4546 1 12 8.69

200 4746 2 13 9.30

200 4946 14 9.70

200 5146 15 9.70

200 5346 16 10.10

200 5546 4 17 8.54

6 5552 ii 18 3.55

Total 137.12

1633 5552 Tl 19 BYPASS 8.06

2 2021

22

2324

25

26

2728

29

3031

32

3334

35

36

37

38

PASS2

ii

IT

It

It

1!

II

11

11

II

II

11

11

11

11 PASS 3

11

ff

T!

13.1

12.8

12.8

27.8

27.8

12.8

43.0

12.8

12.7

58.28

58.28

28.31

118.50

58.36

6.90

13.28

58.23

178.62

359.51

2 39 It 39.84*

Total 1161.77

Grand Total 1368.52 or

22.81 hrs.

° See Table 7 for code numbers for machines usee1 * Charged Time. CPU time unavailable.

32
Table 7 Storage of the Machines Used

No. Machine Location

Available

Core Memory

1.

2.

3.4.

UNTVAC 1108

IBM 360/95

IBM 360/91

IBM 360/91

NBS, Gaithersburg , Md.

NASA, Greenbelt, Md.

NASA, Greenbelt, Md.

Applied Physics Lab. , Columbia, Md.

5 OK words

4000K bytes

150 OK bytes

150 OK bytes

4.3.2 Execution Time and Storage : It should be noted that

throughout this report the core storage and C.P.U. time values are

approximate. This is due to differences between IBM 360 systems as well as variations in one system from run to run. The IBM 360/95 had

variations in both time and storage which sometimes were and sometimes were not attributable to its multiprogramming environment. In this

system the user has the option of calling for one of three FORTRAN

compilers, each differing in the level of optimization and the conse- quent program storage allocation. This system also has two types of

high speed memory, magnetic core and thin film core, which were assigned by the operating system. In one instance, for example, two identical runs had C.P.U. times of 2.37 minutes and 1.59 minutes, with the

shorter time undoubtedly due to thin film storage allocation. It should

be added, however, that thin film allocation was much less common.

There were also program factors contributing to the variation in

time and storage needs. Changes, from problem to problem, in the input

value of the minimum detour ratio (XMDR) were made in order to find an

optimal choice for this constant. The value of XMDR determined the

stopping point in PASS1 and thus influenced the running time. (The

smaller XMDR, the longer the running time.) Also, the array that con- tributed most to the core requirements of the common block was the

Route Table. A garbage collection routine was introduced to compact

this table as necessary. The larger the table, however, the less garbage collecting was required and the faster the execution time.

The C.P.U. times for the runs that were made are included in

Table 5 but, for the above reasons are considered only approximately

comparable. The storage requirements for the different program com- binations as well as the system and common block requirements are included in Table 4.2. Table 4 . 3 lists the maximum storage required for

the three phases of the DECCO network solution. Clearly, a computer

with about 1300K bytes available is necessary for solving the Telpak

problem.

33
4 . 4 Input/Output

4.4.1 Input Data : The input data for a subproblem consists of

the City Table (see 2.1), the Request Table (see 2.2), and the four

variable constants XMDR (minimum detoui1 ratio) , NOKC (the maximum num- ber of cities allowed in a subnetwork of PASS1) , XSIZE (the ellipse

detour ratio used to determine a subnetwork of PASS1) , and NWIRE (the

number of sub-voice telegraph/telephoto lines in a voice circuit) . The

input data is read in from cards, one card per city or request and one card for the constants. For the DECCO network the above input is used

for PASS1. ADDEEQ then reads the remaining requests from cards and

adds the corresponding city or cities as each request is configured.

After all requests have been configured, successive restarts of the

program use the contents of the previous run's arrays as input (via

magnetic tape )

.

4.4.2 Output of the Runs : As described in Section 1.4, the main

outputs of the runs consist of the Link Table, the Route Table, and the

final network cost (TOTCST) . The following five quantities are also

calculated and printed out. These are very important for the evaluation

of the network cost and configuration (see Section 5). See Appendix D

for sample outputs. See Table 8 for these values from the computer

runs.

4.4.2.1 Required Wire-JMiles (REQMI) . This number is obtained from the sum over all requests of the wire-miles (number of wires

required x airline distance) for each request. It is a measure of the

total network communication requirement in wire-miles.

4.4.2.2 Total Path (TQTPTH) . This number is the sum over

all requests of the product for each request of the wire-miles with its

detour ratio. It is a measure of the travelled wire-miles in the network.

4.4.2.3 Cost Per Required Wire-Mile (CPRWM) . This num- ber is the ratio of the total network cost (TOTCST) to the network's

required wire-miles (REQMI). It is a measure of the average cost for

each unit of communication requirement.

4.4.2.4 Cost Per Travelled Wire-Mile (CPTWM) . This num- ber is the ratio of the total network cost (TOTCST) to the total path

travelled in the network (TOTPTH) . It is a measure of the average cost

for each unit of communication utilization.

4.4.2.5 Average Detour Ratio (ADR) . This number is the

ratio of the total path (TOTPTH) to the required wire-miles (REQMI).

It is a weighted average of the detour ratios of all the network re- quests .

34
5.0 RESULTS

5 . 1 Costs

Table 8 . 1 includes a surrmary of the final cost results for the

full 1633 node network and its four subproblems. Several differences

are worth noting. The final problem introduces on the average, about one new city for every two requests added over the 250 city problem.

The effect of these many extra cities is that unit costs go up. The

cost per required wire-mile rises more than 12% over the result for the

250 city problem, although only 13% additional mileage has been configured. The average detour ratio also rises, as might be expected,

but not as much as the unit costs.

5 . 2 Connectivity

As shown in Table 8.2, the number of links per route is much

higher in the full network than in the smaller ones , and the connectivity is much lower. The connectivity is the ratio of the number of used

links in the configuration to the number of links in the minimum-distance spanning tree. In any n-node network, a completely connected

configuration has n(n-l)/2 links while the minimum spanning tree has

(n-1) links. Thus the maximum value of the connectivity is n/2. From

Table 8.2, it can be seen that all the networks are sparsely connected,

and the full network is the least dense.

5 . 3 Computing Time

Table 9 summarizes the time taken to compute different subprograms for different size problems. It can be seen, that, in general,

the dollar savings in the solution per minute of computing time de- creases as the problem size grows. The programs PASS2 and PASS3 were

relatively inefficient on the full size problem, although they still

saved in monthly rentals considerably more than the cost of their

computing time. However, it was not expected that PASS2 and PASS3 would

take as long as they did. If that had been known, a better strategy

would have been to re-run PASS1 on the largest problem following the

running of ADDREQ. This conceivably would have provided the input to

PASS2 with a more optimized configuration. Time and funding constraints

prevented further experimentation.

35
CD H9

Eh

P.3oP O ^ co cd (S

m

H

O-H P^ ld cd en o H ° # 9

rH rH rH CM OJ

rH rH rH rH rH ><

^,

Tj dl-0>

U CD rH

w

CD rH -H --^ CO CD CO OJ CO CXH S g rH (J) CO CD rH

CD 1 § CD CO CD

O

H

•P > CD P CM OJ OJ Ol CO

ffl l! fnfc O ^ • H ° O H 3 ^w

T3 CD ^ J OIOID Ol

CD rH S CO CO CD LO CO H S E

O) Lf) ID CD CD

CD 1 Eh

H

O MNJ > CD O ID OllD J H

ft) fc Eh CO CM CM r- CO £.H~ J- CO CD CD rH

rH

^-N

CD -CO- fn'Oriv-'

CD CD -H ^ CD Ol ID CD ID

j- r- cd ld r- •H I 3 oi co co co t— P 3 CD PC CO CO CO CO CO

CD U' P. P-i O (D'HU Uf^S^

co T3 CD CO CD Hf

O CD

CD rH ^ CD CD rH CD en p -H M o co cd en co •H S S 3 i cx CO CD zt CO LD

C71 0)

u

CD P E

CD rH CM CD J"

OJ

H l~~ o co

f£ -H v-' S J- r~- t-- co en

<"~s

p -co- co ^ O CO J;

O CO

O ^ ld o cd en rH O Eh H rH CM r^ CO

C/3

HO CD LD OJ en CO

tf Eh CD CD CD rH CM P O co J- co r- lo O \^

pn v-^ rH CM CM CM CO

CO -p

O

O CO Hr CM

co CD CM Ol CD LD

CD CO ID CD CO LD 3 rH CM OJ LD a1 ^ CD tJ E O5CD CD S a> CD O CD O CO •p ID LD O LD CO

-p i—I CM Ol CD •H <-{ O

co

Si •p

93o3 O >; P

a)p cd CD CM LD IT~- CM

O -H §

ID [^ CD ID CM

rH rH rH rH rH

U -P s

CD 6^s -p CO CO 00 rH CD • J co id cm en en

•p cm co co en O 4h rH

Eh

O

CD P en 3 O O • CC o -^ -J- ID CD C- LD S w rH >^< -HJ

CD -P CD

O CO J" Ol

CD cd oi oi en id

CD CO LD CD CO ID 3 rH CM CM LD O

CD «

y.

PjQ5CD CD S CD

O

OO CD CO •H ID ID CD LD CO

-P rH CM OJ CO •H r-\ O

36
CD

CD

CDqCD>

•H

-Pa

CD Un

MhWI

CD H9

EH

CDN

•H

00X

a)

CD LO CO LO rH

H z)- LO

HO

CO

(£1

en

CO

r-\ CO

ZfLO

CO

co

COo

CO

CO

IT- CO

en

CD

z± CD

co

J"LO

rco

rz)- CO

Zj"

CMHCO

CM

CO LO LO CO zt CM en

ro

coH

CO

CM

-CO- -CO- -CO- •CO

CDLO

-CO- CO

ztCD

•CO -CO

CD LO CO rH CM CD rH CO

•Ho

CO zt- CO CO

HH CO CO CO LO CO L~- H r- en zf

CO LO • r> r- *> ** CO ** *"* CD H CO r- CO CM co zf CO CD IT- CO

co co • co CM • en CO • CD o LO LO H CM CO

LO CO ** CM CM

-CO- -co- -CO- -co -co CO -CO- -coCO co CM r- H zj- CO co

•H

—

LO

zt- CM

CM CO

co

LO

CM

CD

CD

CO

CM

zl- o o

CO CMCO

zf co CO

H en LO Zf en CO Zj" CO LO o zt- CM CM • o r- • LO r-\ o co CD H rH H CO

CD zf "

CM CM

-CO- </> -co- -CO •CO- -co CO -COCO CD co r- LO o zf CO £

CO

zt COO

CO COCM

zt

CD CO

rH

LO

r- CO

CO •H CD CO ^ «* LO *> ** o " ** CO CD CD CO CO en CM CM CO CO CM z* LO LO . H zj- • CD CD • rH o [-» CO CM o CD H zj- CM

LO *^ H H

-CO- -CO- <o -CO- -co -co -CO- -co

CO CM o CD rH c~- CO r- £

enoCOO

CO

rCD

CO

CO

C~~ CD

CO

CO CD

CO

H CO *\ LO ri «* CO ** *^ CO *^ CJ LO CO LO CD CO LO CD co LO o en CM CO CO . CO CO CM • LO CO

CD rH Zt CM CD

H CD CO o co

LO

rH <-{

-C0- -co- -co- -co- CO CO -co -co-

^^ ^ ^

CD . CD . CD • CD .5 O

•H

H3 •5 iH 3 qH

C Pa

q•H

q s s g O

•H •5 5 O

•H

q o• H

q•H

-j-i *>~ P S P P

a) 8 CD

0j

O

CD

eg CJ 3

r<

CD

CD o

Su

CD

E-h $

CU En CD Cu 't-H CD Ph Eh CD Ph

cu p

CD CD CD CD CD CD CD

rH

bOq•H Pa

H

bOq

•H

-P rH

bO s&

bO 1 oo

rH > B

H > e rH £ i

t—{ CO

_

a

fd en 6o a

n3 00 oo oo oo o

CJ

a

T3SCD HIqo

•H

1d

S) •Hqoo

•HO

LO

CM

H

CO

CO

00s

CMCO00

oo

cu

37
REFERENCES

[1] Kruskal, J. B. , Jr. , On the Shortest Spanning Subtree of a

Graph and the Travelling Salesmen Problem, Proceedings of

the American Mathematical Society, Vol. 7, No. 1, (Feb. 1956)

pp. 48-50.

[2] Dantzig, G. B. , On the Shortest Route Through a Network,

Management Science, Vol. 6 (1960), pp. 187-190.

38
APPENDIX A

PROPERTIES OF A SHORTEST SPANNING TREE

The properties of a shortest spanning tree network for a finite

connected graph with a positive number (length)" associated with each

edge are summarized below:

1. Every node Is connected to its closest node.

2. Every node is reachable from every other node.

3. There is a unique path between any two given nodes.

4. The sum of the lengths of the edges is a minimum.

5. The tree is unique if the lengths of the edges are

distinct. 5'"v

6. The tree contains the minimum number of edges for connecting

all nodes . If n is the number of nodes , the number of edges

is (n-1).

7. The tree contains no loops.

* The positive number associated with an edge of a. graph can be

any characteristic possessed by all edges. In this problem, the cost

of an edge is used in this way.

** Since the lengths of the edges in the DECCO network are not

all distinct, the graph formed is not unique but is a shortest spanning

tree. A-l
APPEM)IX B

NETWORK CHANGES PRODUCED BY DANGLING LINK ALGORITHM

Each of the links in a path of two links can be thought of as having a fill composed of two disjoint sets. These are:

1. the fill of those requests whose routes contain both links.

2. the fill of those requests whose routes contain one link or the other.

Using the subnetwork of Figure 6 one can translate this fill information

into set theoretic relations.

If one denotes the fill of a link by FL, the fill of a set of re- quests by FR and then subscripts these quantities with letters denoting

the link or route, one can say, before deflection:

FL

AB

= ^ABC + ^AB (B.la)

^BC = FRABC

+ ^BC (B.lb)

The cost of link AB is then a known function of its fill (FL. R

) and its

length (D. R

) and similarly for link BC. Thus the total cost of the two

links is TJ, where

C = f(FL

AB' V + f(FLBC D

BC } (B - 2)

After deflection one has the relation:

i FL

AB

= ^C + ^AB (B.3a)

AC " "^BC ' ""ABC (B.3b)

, .„ = FR

BC

+ I

where the notation FL denotes the link fill after deflection. Combining equations (B.l) and (B.3) one then finds

t FL

AB

= FL

AB

+ FL

BC " 2FRABC (B.4a)

FL .„ = F^

i AC " ^C (B.4b)

3-1
Correspondingly the new cost , C , is a known function of the new fills

FL AR and FL .„, and the link lengths.

C ' = f(FL

'AB' V + f(FL

' AC V (B.5)

Figure B.l illustrates these set theoretic relations. Note that two

cases arise. One occurs when the deflected link BC is in the route

of the new request and the other occurs when BC is not in the route

of the new request.

B-2
Left Circle = FL

AB

Ripht Circle = FL

BC

a) Before Deflection

Left Circle = FL ; AB

Fdpht Circle = FL' AC

b) After Deflection

Figure B.l Set Theoretic Relations for Deflection Algorithm

B--3
APPENDIX C

REROUTING SEARCH SCHEME FOR UNECONOMICAL LINKS

The sequence for attempting reroutings of requests in PASS2 is

determined by establishing a value for the maximum number of circuits

to be rerouted (FMAX) and a try-table (TRYTAB) of requests in descending order of fill requirements. After unsuccessfully trying to find

a single request whose fill lies between FMAX and (FMAX + 4), the

region from (FMAX - 1) to 1 is tested for a set of requests. If a request is successful and the fill number I Is less than FMAX, a new

value of FMAX is computed from (FMAX - I). If this new FMAX is greater

than 1-4 the search for requests continues downwards. If this new FMAX

is less than (1-4) the direction of the search Is reversed and the range

is (FMAX + 4) to 1. This technique continuously offers the opportunity

for finding a request that will cover the remaining range.

C-l
APPENDIX D

SAMPLE COMPUTER OUTPUTS

The following three pages contain sample printouts from the TELPAK program for the 1633 city problem. The first printout (page D-2)

contains the beginning of the Link Table. In addition to the two

terminal city designations, the link distance and the link fill, the

TELPAK breakdown (D, C, Ixc) and the cost of the link appears. For this

particular printout, it was also found of value to list the requests

using this link. The second printout (page D-3) contains the beginning

of the Request Table. In addition to the city designations for the

request pair, the number of circuits required, the request airline

distance, and the detour ratio, the printout also has the route length

(in links) and the node (city) sequence of the route. The third printout (page D-M-) contains the end of the Request Table plus the vital

statistics resulting from this last run of the problem. These figures

appear in Table 8.1 for the 1633 city problem.

D-l
• — en co «n • r*» O

o — O « 0* o "O en

cm o* -o cm * —

— CM 3" Lfl en in

*0 lfl O

cm m o

— ifl CD — — m

N -»T rt rj (\( ji N N T T » N< nO — 3- -4> CN •« CM —• — — M fO T

— O -O CM -O

3" CM *0 CM CO am -o n

en o- o co T O 4 CO D CO lfl CM — cm j- inrv cm in o in co — CM

i/i •• n n -o — in N T T T -O (MO

*o o a- -o —• o —

—— cm m t

J1 N O - CO <n CM o CM o

r> in — -o r*. — cm n a-

( J) N O en —

cm o r*. in — i-»

r-v co cm cm cm o'

cm a- in en a-

<n cm o

o* m a- — CM

>0 rs co Ji o -o -o « i*i n co i/i t •

« o t ifl - no -- N IT

n) -o -e in <n cm o a- pv c ifi - n *

— cm en aT N N

-o in en — CM

cm -o cm co o in in O ffl 0- N Oiflin o rn m —* to o

O lfl 0> T CO

en cm — a- in

o- in o o « — cm en ar* o a- -o in i-* cm — in — CO —

r-. 3- o — o o

M i*> Jl en acm cm in 0 1/1-

•o ifl co n 4 in -o CM en CO a- D lfl —

a" o en ifl —• co co — — CM cm *n

a- cm •<> eo in —» cmj -o a- -o O ifl O* O — — — en ao* co o* r*. en t> CO O sO o o a- — en -o o O CO CM en lfl im a-

— a- o o o o cm O "*) CD T - lfl -

en o*- en in o co co — — CM CM en

O - M N >0 *n cm en m —

CO lfl O CO o

— — (M 3-

O CO O lfl CO O- O CD eo — in *n —* <n •« o

CO 3" t> C\j en 3"

4 N N enOOOiflen — —

Ol^-UlOifl

—• o -o cm o^cn^oeno— — pvo o — co in —

* en O CM IVOOifiONCO- CO N lfl lfl CO O — — r^ — — — cm en in co — «n t

fM en CM lfl — — in co co r^ COO 4 h O -43 — o — en *o o CO O

CM CM CM en a- <n cm aNTCOCOMMh-O

co— n n -o t> o co —^CcniflOa'COr^ — _ _ r\l en 3"

— 4} — CO en O

it co O is: co o — if) 2 — m 2 — CI CM t> — CM — CM en 3" cm a- in —

c*» o ifl en o-ojiifi-o-oaiai— cm en en o co v co co j cm ^cMencM«n>oooo ^oa-a-oo

z — m^ocn z— coeninoa-cof^ z in t in t co _ _ _ 3- — - - -. NM T — —• — CM en

3 COoD Nlfl

r^ en en r^

r- —

3 en in en

cm m o 3 3

lfl o in — o in -O O CM lfl Ifl - CM »- — en a- — m in 1—

Ifl in in in

UJ o UJ 1— UJ t- UJ X UJ X 3 tj ^ UJ 3 or 3 3

^ C7 lfl o X 3 X C3 z O

CD UJ in lfl U. uj in a- in o ^ UJ — a- co % UJ Iff UJ

tr r-. m or r*. *n — o

CO 3" O COor — in co

CM O CM

or or

Iff — 15 — <n a- iff — en lfl 13 is

icoenm DiflO-J1<*lMO'*)lfl 3 — ocoen

t «n ar *o — o— enencoor^ o-oa-coo

cnocM in — n o ifi o- nco -o meneniflenco

—• — a- l— — — — CM en 3" t— — — CM en VI in

in a

U UJ 3" Q: a-

"3 UJ OU

2 3 Z 3

in NNibJTN---oi/iNco)-ujninait>N

i n t- tc-coonTNcoifi or o — en o co

> n « CD --Onifl-OenN-O CMeniflenr- — — m Iff ---.NAT Iff — — CM en

(3" -J O CM

en _i m

o o o — 3: u. —

«neoN _jenr>o _i— _io MM Jl J T >0 lfl Jifl _JO or-en o o -oc\i on o <*i MTiiirk-niflZLIMZLMQ.

Iff Iff

-J en _l 3- — O

_J 3" _l — O en O O O — en Lfl

• u. *n I- U. — — i

lfl O — en

3- O lfl CM

-o en r*- en — c\j en aD-2
L_ 1— O

_i O u

bJ LO LA 2 -> U.

>- - >

tr ini >

«n 3 2 in

x > en i a j

INI L_ _J

_» *: x 3 «: x

_i •< _i

< 2 M

>0 l/> «X n o in

3- \D • O

li. >-Nl

£L > > ^

< i: C u

* Q_ "J I

O Q. J N

L-. > C b. S I- X <

UJ O Q K- _l X X X

isi u. ir> < _j 3

in *: u

*x >- x

> ^

b. 3

en <3

-J X

in v x

s 3 o

o O i£

* v < 3 3 X o o o

V tt *: v in: ^ it -it * 2 "5 X V * u *: v ^ if * ^ X ^ V

3 3 3 3 1 3 3 3 3 U. t- o 3 3 t- 3 3 3 3 3 3 »- 3 3

o o O O O o a o o -1 a: O Q M o a a n a o ~> Q Q < « «* -r L_ < < < < n o; •« < < y < «r « •< •< < X < <

D-3
ft

a

ai ro

fo in n n ~

-. o n <u

•# <t CJ u in ^

-* P* aj

-t Is- "1 n n in * • o a o ui < < > >

33

N s in „, * O 9 * J II q 3 a (\J N aj 111 u n -I O •t n * s

CD

u

n * en L£j UJ II o Z n m -• 3 a: a -> <u H - a * a <y T o J « -* d a <

jju cc

J 1 33 5

ii <*

a

a : 01 ul H ; * * </> i N N O

<y i- <

U> 3 h- ui a o z u

UJ 2 J u.

fc U. S. GOVERNMENT PRINTING OFFICE : 1973

—511-327/285

D-4
FORM NBS-114A (1-71) 2. Gov't Accession No.

U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO. NBS TN-7873. Recipient's Accession No.

4. TITLE AND SUBTITLE 5. Publication Date

Heuristic Cost Optimization of the Federal Telpak Network 6. Performing Organization Code

7. AUTHOR(S)

R. G. Saltman, G. R. Bolotsky, Z. G. Ruthberg

8. Performing Organization

10. Project/Task/ Work Unit No. fiUO-2456

9. PERFORMING ORGANIZATION NAME AND ADDRESS NATIONAL BUREAU OF STANDARDS DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

11. Contract/Grant No. 1-35859

12. Sponsoring Organization Name and Address Defense Communications Agency

8th Street S South Courthouse Road

Arlington, Virginia 22204

13. Type of Report & Period Covered Final , 14. Sponsoring Agency Code

15. SUPPLEMENTARY NOTES

16. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a significant bibliography or literature survey, mention it here.)

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

coiimunications service requests involving 1633 nodes. A FORTRAN IV program was developed to solve for actual needs of the Defense Communications Agency for leasedline service employing the Telpak tariff structure.

17. KEY WORDS (Alphabetical order, separated by semicolons) Communications network; computer program; heuristic; minimum cost; network configuration; optimization; Telpak rate structure.

18. AVAILABILITY STATEMENT

fxl UNLIMITED.

I I FOR OFFICIAL DISTRIBUTION. DO NOT RELEASE

TO NTIS.

19. SECURITY CLASS

(THIS REPORT)

UNCLASSIFIED

20. SECURITY CLASS

(THIS PAGE)

UNCLASSIFIED

21. NO. OF PAGES

52

22. Price

$.80 Domestic postpaid

$.55 G.P.0. Bookstore

USCOMM-DC S6244-P7
NBS TECHNICAL PUBLICATIONS

PERIODICALS JOURNAL OF RESEARCH reports National Bureau of Standards research and development in

physics, mathematics, and chemistry. Comprehensive

scientific papers give complete details of the work,

including laboratory data, experimental procedures, and theoretical and mathematical analyses. Illustrated with photographs, drawings, and charts. Includes

listings of other NBS papers as issued.

Published in two sections, available separately:

• Physics and Chemistry (Section A)

Papers of interest primarily to scientists working in these fields. This section covers a broad range of physical and chemical research, with major emphasis on standards of physical measurement, fundamental

constants, and properties of matter. Issued six times a year. Annual subscription: Domestic, $17.00; Foreign, $21.25.

• Mathematical Sciences (Section B)

Studies and compilations designed mainly for the mathematician and theoretical physicist. Topics in mathematical statistics, theory of experiment design, numerical analysis, theoretical physics and chemistry,

logical design and programming of computers and

computer systems. Short numerical tables. Issued quarterly. Annual subscription: Domestic, $9.00; Foreign,

$11.25.TECHNICAL NEWS BULLETIN

The best single source of information concerning the

i Bureau's measurement, research, developmental, cooperative, and publication activities, this monthly

publication is designed for the industry-oriented

individual whose daily work involves intimate contact with science and technology

for engineers, chemists,

physicists, research managers, product-development

managers, and company executives. Includes listing of

all NBS papers as issued. Annual subscription: Domestic, $6.50; Foreign, $8.25.

NONPERIODICALS Applied Mathematics Series. Mathematical tables, manuals, and studies. Building Science Series. Research results, test methods, and performance criteria of building materials, components, systems, and structures. Handbooks. Recommended codes of engineering and industrial practice (including safety codes) de- veloped in cooperation with interested industries, professional organizations, and regulatory bodies. Special Publications. Proceedings of NBS conferences, bibliographies, annual reports, wall charts, pamphlets, etc. Monographs. Major contributions to the technical

literature on various subjects related to the Bureau's

scientific and technical activities. National Standard Reference Data Series. NSRDS provides quantitative data on the physical and chemical properties of materials, compiled from

the world's literature and critically evaluated. Product Standards. Provide requirements for sizes, types, quality, and methods for testing various industrial products. r These standards are developed co- operatively with interested Government and industry groups and provide the basis for common understanding of product characteristics for both buyers and

sellers. Their use is voluntary. Technical Notes. This series consists of communications and reports (covering both other-agency and

NBS-sponsored work) of limited or transitory interest. Federal Information Processing Standards

Publications. This series is the official publication within the Federal Government for information «n

standards adopted and promulgated under the Public Law 89—306, and Bureau of the Budget Circular A—86

entitled, Standardization of Data Elements and Codes

in Data Systems. Consumer Information Series. Practical information, based on NBS research and experience, covering areas of interest to the consumer. Easily understandable language and illustrations provide useful background knowledge for shopping in today's tech- nological marketplace.

BIBLIOGRAPHIC SUBSCRIPTION SERVICES

The following current-awareness and literature-survey bibliographies are issued periodically by the Bureau:

Cryogenic Data Center Current Awareness Service (Publications and Reports of Interest in Cryogenics). A literature survey issued weekly. Annual subscription: Domestic, $20.00; foreign, $25.00.

Liquefied Natural Gas. A literature survey issued quarterly. Annual subscription: $20.00. Superconducting Devices and Materials. A literature survey issued quarterly. Annual subscription: $20.00. Send subscription orders and remittances for the preceding bibliographic services to the U.S. Department

of Commerce, National Technical Information Service, Springfield, Va. 22151. Electromagnetic Metrology Current Awareness Service (Abstracts of Selected Articles on Measurement

Techniques and Standards of Electromagnetic Quantities from D-C to Millimeter-Wave Frequencies). Issued monthly. Annual subscription: $100.00 (Special rates for multi-subscriptions). Send subscription order and

remittance to the Electromagnetic Metrology Information Center, Electromagnetics Division, National Bureau

of Standards, Boulder, Colo. 80302. Order NBS publications (except Bibliographic Subscription Services) from : Superintendent of Documents, Government Printing Office, Washington, D.C. 20402.
U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Washington. D.C. 20234

OFFICIAL BUSINESS

Penalty for Private Use. $300

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE COM—215