NATIONAL BUREAU OF STANDARDS REPORT

9977

VALUATION OF TELECOMMUNICATIONS

Progress Report for FY 68

with Appendices

to

Defense Communications Agency

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
THE NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards1 provides measurement and technical information services

essential to the efficiency and effectiveness of the work of the Nation’s scientists and engineers. The

Bureau serves also as a focal point in the Federal Government for assuring maximum application of

the physical and engineering sciences to the advancement of technology in industry and commerce. To

accomplish this mission, the Bureau is organized into three institutes covering broad program areas of research and services: THE INSTITUTE FOR BASIC STANDARDS . .

. provides the central basis within the United

States for a complete and consistent system of physical measurements, coordinates that system with the 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. This

Institute comprises a series of divisions, each serving a classical subject matter area: —Applied Mathematics—Electricity—Metrology—Mechanics—Heat—Atomic Physics—Physical

Chemistry—Radiation Physics—Laboratory Astrophysics2—Radio Standards Laboratory, 2 which

includes Radio Standards Physics and Radio Standards Engineering—Office of Standard Refer- ence Data. THE INSTITUTE FOR MATERIALS RESEARCH . . . conducts materials research and provides

associated materials services including mainly reference materials and data on the properties of materials. Beyond its direct interest to the Nation’s scientists and engineers, this Institute yields services which are essential to the advancement of technology in industry and commerce. This Institute is or- ganized primarily by technical fields: —Analytical Chemistry—Metallurgy—Reactor Radiations—Polymers—Inorganic Materials—Cryogenics2—Office of Standard Reference Materials.

THE INSTITUTE FOR APPLIED TECHNOLOGY . .

. provides technical services to promote the use of available technology and to facilitate technological innovation in industry and government. The

principal elements of this Institute are: —Building Research—Electronic Instrumentation—Technical Analysis—Center for Computer Sci- ences and Technology—Textile and Apparel Technology Center—Office of Weights and Measures —Office of Engineering Standards Services—Office of Invention and Innovation—Office of Vehicle

Systems Research—Clearinghouse for Federal Scientific and Technical Information3 —Materials

Evaluation Laboratory—NBS/GSA Testing Laboratory.

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

2 Located at Boulder, Colorado, 80302.

3 Located at 5285 Port Royal Road, Springfield, Virginia 22151.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT

4556455

NBS REPORT

9977

VALUATION OF TELECOMMUNICATIONS

Progress Report for FY 68

by

S. C. Strom

Arthur M. Hobbs

to Defense Communications Agency

Systems Research and Development Division

Center for Computer Sciences and Technology

with Appendices

IMPORTANT NOTICE NATIONAL BUREAU OF STA

for use within the Government. B and review. For this reason, the whole or in part, is not authoriz Bureau of Standards, Washington

the Report has been specifically p

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

accounting documents intended

jbjectecf to additional evaluation

isting of this Report, either in Office of the Director, National

the Government agency for which

ties for its own use.

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
TABLE OF CONTENTS

Annual Progress Report for FY 1968 (S.C. Strom) ...

Appendix k, Comparison of Evaluation Techniques

(Arthur M. Hobbs)

1.0 Introduction

1.1 Definitions and Network Conditions

2.0 Evaluation Methods

2 .1 Cut Set Method

2.2 PATHFINDER-WORTH

2.3 Path Weighting

3.0 Test Cases

3.1 Cut Set Evaluation

3.2 PATHFINDER-WORTH Evaluation

3.3 Comparison Methods

U.O Validity of Passing from Small Networks to

Large Ones

5.0 Conclusions

6.0 Cut Set Lists

6.1 Four Switch Network I 6.2 Four Switch Network II

6.3 Five Switch Network

6.k Ordering Comparisons

Appendix B5 statement of a mathematical problem

(Arthur M. Hobbs)

Page

1

h

h

£

8

8

9

11

12

12

17

18

23

25

26

2 ?

30

#

65

References 66
Project

ANNUAL PROCESS REPORT

for FY 1968

PROJECT TITLE : Valuation of Telecommunications

OBJECTIVE ; a. To develop effective methods for calculating

the attack worth of the various elements .

b. To develop optimal offensive and defensive

strategies for destruction and/or preservation

of communication capabilities.

HISTORY : The project is a continuation of a previous effort

under contract with the Defense Communications Agency.

The contract has been in effect since July 1966.

National Bureau of Standards subcontracted The John

Hopkins University to conduct research in graph

theoretic methods for analysing large communications

networks

.

PROGRESS during FY 1968:

Research and development was concentrated in two general areas.

1. Determination of importance numbers for elements of a communications network.

2. Development of offensive and defensive strategies for

a telecommunications network serving a multi-command

multi- subordinate structure.

A pathfinding and counting method and a technique of assignment

of importance numbers to network elements were developed during

the previous period. Efficient computer programs capable of

handling real size networks had to be written and made operational.

These programs had to be provided with program interrupt and

restart routines. The difficulties caused by the size of the

network and the necessarily excessive running time were

satisfactorily resolved.

1
Considerable effort was devoted to finding an acceptable

method for determination of the worth value* or importance

number* of individual elements of the network.

Consultative services of Dr. M» J. Krakowski, of Tulane

University* New Orleans, were secured during summer 1967

The results of Dr. Krakowski' s investigation are contained

in a paper "Some Considerations in Valuation of a Telecommunications

Network" which is being published by NBS. Briefly summarized,

at the present state of art the problem has no satisfactory

numeric solution. Integer linear programming seems to be a promising tool for finding at least partial answers.

Our own efforts were concentrated on the study of the

relationship of path lengths to path counts and on the

relationship between the numbers of paths utilizing a network element and its relative importance value.

An acceptable method was developed to perform such relative

evaluation and to produce numbers which allow us to rank

network elements in an approximate order of importance.

The results obtained through this method were tested against

minimum cut sets (disconnecting sets) in the network and

a considerable degree of correlation was found. The study

is described in the paper "Comparison of Evaluation Techniques,"

included as Appendix A.

Tlie above work was accompanied by background theoretical

investigations in the related topics of graph theory. In

the course of these investigations several new theorems

on thickness-preserving compositions of graphs and on the

size of cut sets in t -minimal graphs were developed. Thus

abstract scientific research and its practical implementation

were successfully pursued.

During the course of our research, a new mathematical problem

was found whose solution would give directly the necessary

size and structure of an optimal military telecommunications

network which uses a civilian network. The most general

form of this problem asks what graphs can be embedded in

other graphs and includes several previously known and still

unsolved problems. However* the project requires only the

the solution of the special case whose exact statement

is given in Appendix B* and this version of the problem may

include sufficient restrictions to be solvable. The Johns

Hopkins University group has already made some progress toward

a solution.

2
Dr. Mandell Bellmore, of The Johns Hopkins University, with

a team of graduate students continued this efforts with

research concentrated in the area of multi-command problems.

Single- command attacker's and defender's problems had been

successfully solved previously. However, those methods

of solution could not be simply extended to the multi- command

situation; therefore, new approaches were sought and some progress was made. The problem of an attacker with

unlimited resources was solved and a computer program

implementing the solution was developed. The defender's

problem was theoretically solved; its translation into

a computer program remains to be done.

3
APPENDIX A

COMPARISON OF EVALUATION TECHNIQUES

by

Arthur M. Hobbs

1.0 INTRODUCTION

Every large communications system must be designed with considerable

care, taking into account a large number of factors, such as the

needed capacity and the failure rates of components. An important

factor in military communications networks is the survivability, or

the ability of the network to serve its purpose in the event of an enemy attack or a natural disaster

In the present study, we have concerned ourselves solely with the

survivability of large comrnunicat ions networks, containing I4O to 80

switches and 300 or more inter- switch links. We would like to

assign "importance numbers" to the elements (links and switches)

of the networks so that the more important to us that an element

survive in an attack, the larger the importance number assigned to it

In any reasonably complicated network there are numerous paths by

which each pair of subscribers might communicate, each path differing

from the others by one or more network elements. Therefore, it is

unlikely that the removal of any one, or even a small number, of

elements will adversely affect the existence of communication paths

between users of the network (although the effect of the removal on capacity or quality of communications may be serious indeed) . For

this reason it seems unlikely that we can find any absolute valuation

of the network elements, or any importance numbers whose values have

an absolute meaning.

We have written a pair of computer programs (PATHFINDER and WORTH,

referred to hereafter as PATHFINDER-WORTH) which assign numbers to

the network elements. Although we have referred to these numbers

in previous documents (for example, in reference C3J) as "importance

numbers", we hope merely that these numbers can properly be used

to place the network elements in rank order, so that elements highest

on the list are the most valuable to us and those lowest on the list

the least valuable. To test this hope, we have compared the ordering

obtained through PATHFINDER-WORTH with the ordering resulting from

arranging the elements randomly, and with a later described ordering

dependent upon cut sets . We believe that if the orderings given by

the two different methods, PATHFINDER -WORTH and cut sets, are similar

and differ markedly from the random ordering, then we have reason to

believe that the ordering given by PATHFINDER-WORTH is useful

The author wishes to thank James Owen for his help in performing

many of the calculations reported here and in preparing the graphs included.

l\
1.1 DEFINITIONS AND NETWORK CONDITIONS

A communications network is a collection of switching stations, or switches , interconnected by inter-switch communications links , each

containing one or more channels for communications . The switches are joined to subscribers , or users of the network, by access lines . The

network links and switches are called network elements We have assumed

for this study that no subscriber is also a switch; this assumption

is usually valid, there being presently at most one exception in the

networks we are examining. Such exceptions can usually be treated by

an artificial separation of the subscriber- switch into two parts,

one a switch joined to all other elements to which the subscriber-switch

is joined, and the other a subscriber joined to that switch by an ideal link.

In this study, we have assumed that a given pair of subscribers can communicate after an attack as long as there is a path still existing

between them which does not have too many links in tandem, regardless

of the remaining capacity of the network as a whole and regardless

of the number of other subscribers also attempting to use the network

at the same time. This assumption is reasonable in the special

conditions of military networks having priority levels for important

subscribers

.

We are interested in analyzing a large network which is shared by

many independent users, each with his own time-varying importance to

national defense. For the purposes of the remainder of this paper, we will call each pair of subscribers who are communicating through

our network a command- subordinate pair , whatever their real-life

functions. Further, we will assume that, at least for short periods

of time T, it is possible to assign a weight, or worth number, to each

pair, with increasing worth numbers corresponding to some increasing

importance values (e.g., national defense).

A collection of network elements is a cut set of the network if the

removal of these elements from the network results in the inability

of a set S of one or more command- subordinate pairs to communicate

and no subcollection of the elements separates all of the pairs S.

A cut set C may properly contain another cut set C' which separates

some, but not all, of the command- subordinate pairs separated by C.

For example, in Figure 1, the access links (Sll, l), (Sll, k), and

(S12, 3) are a cut set separating Cl from both Sll and S12. But

(Sll, 1) and (Sll, h) also form a cut set, properly contained in

the previous one, which cuts Cl from just Sll.

Our networks have one additional property which has not been much

considered in the past: for voice communications, there is a limited

number of links in tandem which may be used by a communication path.

5
(3 Switch

A Commend

A Subordinate

FIGURE 1. FOUR SWITCH NETWORK I

6
Quality of communications deteriorates very rapidly beyond this

number and it becomes impossible to talk over paths with more links.

This maximum number is much smaller than the total number of links

in the network, and thus only a small fraction of the total

theoretical number of paths in the network are usable for communications

.

This property has implications for cut sets* there will be many more

cut sets in the restricted path length network than in a network

without the restriction, since a set of elements whose removal does

not cut all paths may cut all short paths. On the other hand, the

property drastically reduces the number of paths requiring individual

analysis (if such is to be done).

Very few of the theoretical results which have been proven for

general networks hold true when we are restricted to just some of the

paths. For this reason, we have been forced into experimental

analysis of examples which we can investigate by hand. In each of

the examples used, we obtain weights for the elements of the

network and use the weights to give us an ordering of the elements

.

7
2.0 EVALUATION METHODS

Several methods of weighting the network elements have been

proposed. For example. Professor Martin Krakowski [2] has

proposed that the elements be weighted by the amount of

insurance which should be bought for them in an analogous

commercial system, with the amount of insurance being

obtained by means of a linear program. This method is

sufficiently documented in the report cited; we will not

repeat the description here.

Two additional methods for evaluating the network elements

have been proposed. Both of these methods make the

assumption that the command-subordinate worths for different

pairs are independent, and that the numbers obtained for an element of the network using different command-subordinate

pairs can be simply added to obtain an importance number for

the element. This second assumption has been thoroughly

discussed in the report by Professor Krakowski cited as reference [1]; suffice it to say here that the assumption

is a dangerous one. However, no adequate number-assigning

scheme has been proposed which, does net make this assumption,

other than the insurance scheme. Further, if the worths

assigned to different pairs are actually independent, the

additivity assumption need not be fatal to our weighting

schemes.

2.1 CUT SET METHOD

One method proposed for evaluating the network consists

of computing the following number for each of the network

elements (switches and links) et

where C ranges over all of the cut sets in the network

which include network element e;

v(C) is the mm of the worth numbers of the cormandsubordinate pairs which can no longer corammicat© after

the elements of the cut set C are removed from the network;

n(C) is the number of elements in the cut set C; and

N( e) is the number of cut sets in which e appears.

( 1 )

8
The rationale for this formula is as follows: We have no way of determining in advance what cut set might be used

by forces attacking the network. It is therefore plausible

that we should assign to each network element the average of

the values assigned to it by each of the possible attacks C

in which it appears.

If the removal of an element causes the total separation of

all communications, that el orient can appear in only one

cut set. But we would like the value of such an element to

be the total of the worths assigned to all command- subordinate

pairs. Since in this case N(e) would be 1, and n(C) would be 1,

the formula given would yield this result. It is not reasonable

to average over all cut sets for each element whether or not

it appears in the cut sets, simply because we have restricted

ourselves to cut sets rather than allowing all separating

sets of network elements to be used.

Further, an element which appears in a cut set with only a small number of other elorients in the set would intuitively

seem to deserve a value larger than an element which appears

in a cut set with the same value but which contains many other

network elements. After all, the element in the smaller cut

set is doing more of the work of separating the network. We

take this consideration into account by dividing each v(C) by

n(C), thus normalizing for the size of cut sets.

To apply this evaluation scheme to a communications network

requires that all proper cut sets for one or more of the

command-subordinate pairs be found and evaluated, and that

the indicated computation be performed. Unfortunately, there

is not yet any method by which the required searching and

computing can be carried out in any reasonable amount of time.

Most methods now require that numerous candidates for cut sets

be found, many rejected, and the rest evaluated. This process

is at best enormously time consuming. Thus, although this

cut set scheme for evaluating the network elements seams in

many ways to be a reasonable method, we have not tried to

implement it in the form of a computer program.

2.2 PATHFINDER-WORTH

A second evaluation scheme has been programmed for use on the networks we are concerned with. This method takes

advantage of the maximum path length for usable communications

in a real voice communications network to reduce computational

labor (in contrast to the cut set method above, which becomes even more laborious when this restriction is added) . The

method used here is to evaluate the following formula for

each network element e:

(c, s)

( 2 )

9
where the summation is carried out over all command- subordinate

pairs (c, s), and in which

w(c, s) is the command- subordinate worth for the pair (c, s)j

t(c, s) is the total number of usable paths joining command c with mibordinate s$ and

n(c, s, e) is the number of those paths which pass through

element e.

The concept used in obtaining this formula is that each

usable path through a network element contributes a value

to the element dependent solely on what that path connects

and how many other paths perform the same connecting function.

If only one path connects command c with subordinate s, that

path must be very important, and any network element on it

should be important as well. We therefore assign the path,

and thus every element on the path, the full command- subordinate

worth of the pair that the path joins. If, on the other hand,

the path is only one of many paths joining the command- subordinate

pair, cutting this one path will matter little to the pair.

Therefore, we should assign the path only a small value. We have

chosen to assign each path joining the command-subordinate pair

(c, s) simply the worth w(c, s) divided by the number of paths

t(c, s) joining the pair. We then multiply this value of one path by the total number of the paths joining the commandsubordinate pair and passing through a network element to find

the contribution of the conmi&nd-subordinate pair to the element.

Thus, if an element happens to be included in all or most of the paths between a command-subordinate pair, it will

receive all or most of the worth of that pair, since removing

the one element would destroy all or most of the paths joining

the pair. Finally, carrying out our assumption of additivity, we

simply add all of the values obtained for a network element

for the different command-subordinate pairs together, thus

obtaining a final value for each of the elements.

The above computation requires the finding and counting of

every usable path between every command-subordinate pair.

Although this requires a great deal of work, here the path

length limitation helps, rather than hinders, the counting

process. In addition, several techniques have been

developed [ 3l to render the counting process even faster.

It is for this reason, that we have chosen to implement this

method.

10
2.3 PATH WEIGHTING

Since none of the importance number assignment methods can be

shown to always yield perfect orderings of the elements of the

network, a relatively easy change was made in the pathfinding

computer program PATHFINDER which allowed each path as it was found to be weighted by a value based on the length of the path.

The path lengths and values to be assigned to paths of those

lengths are included in the data of the program, and can be

modified from run to run.

One reason we chose to do this was that a communicator will

usually prefer a short path over a longer one, given a choice.

His reasons include lower noise on shorter paths, lower

vulnerability on shorter paths (there being fewer network

elements to fail or be destroyed), and smaller strain placed

on the network's overall capacity by the use of a short path

instead of a long one. It therefore seems reasonable that a short path should be worth more than a long one

.

If we change t(c, s) to be the sum of the weights assigned to

the full set of paths between command c and subordinate s, and

n(c, s, e) to be the sum of the weights assigned to the set of

paths between command c and subordinate s which pass through

elanent e, then the above formula (2) gives a value of the

element e which depends strongly on whether most of the paths passing

through it are short or long.

Since n(c, s, e) and t(c, s) are both found in the pathfinding

program simply by adding a "1" to the appropriate numbers

whenever a new path is found, the substitution of weighted

paths can be made simply by adding the path weight instead

of the "1". This is precisely the change made in the program.

Of course, it is perfectly feasible to impose the weight "1" on every path, as well as any other weight, thus retaining the

original formulation of the formula (2) as a special case.

11
3.0 TEST GASES

Since only the pathfinding evaluation scheme has been programmed

on the computer, in order to compare its results with those of

the cut set scheme we were forced to limit ourselves to very

small networks. This limitation imposes a restriction on the

validity of our results for the very large networks in which we

are interested! we discuss the validity question in more detail

in Section b of this paper.

We chose one four switch network (shown in figures 1 and 2)

and one five switch network (figure 3) for our study. Each of

these networks was provided with two independent commands, one command with two subordinates and one with one subordinate.

We connected the commands and subordinates to the four switch

network in two different ways. Because of the enormous number

of cut sets ( 14. 2b) for even so smell a network as one with five

switches, we joined the commands and subordinates to the five

switch network in only one way. To free the results of any

bias introduced by making one command- subordinate pair

overwhelm the others, and to make the intuitive analysis of

the networks easier, we assigned a command-subordinate worth

of 10 to each of the pairs in each of the examples. We wanted

to Include the effect of a maximum usable path length which

was less than the length of the longest path in the networks.

Since the networks were so small, this desire forced us to use a path length of 3 switches, which is the shortest interesting

path length less than the longest path length (b) in the four

switch networks.

3.1 CUT SET EVALUATION

To evaluate the network elements using the cut set method,

it was first necessary for us to find all of the cut sets in

those networks . It should be remembered that a cut set is a set of network elements (links and switches) which separate

one or more of the command-subordinate pairs (c, s). Furthermore, no proper part of the cut set (a sub-set with fewer

elements) successfully separates the same command- subordinate

pairs (c, s) (although it might still separate some of them).

We have therefore class ifieouEe cut sets found by the list of

command- subordinate pairs which each separates. None of these

cut sets appears more than once. These lists appear in

Sections 6.1, 6.2, and 6.3, corresponding respectively to the

first and second four switch networks and the five switch

network.

12
S2-1

O Switch

Command

/\ Subordinate

FIGURE 2. FOUR SWITCH NETWORK XL

13
5

O

A

A

Switch

Command

Subordinate

RGURE 3. FIVE SWITCH NETWORK

1*1
The cut sets were used to evaluate the network elements in exact

accord with the formula shown in Section 2.1. Each cut set was

assigned the suira of the worths of the command- subordinate pairs

which it cut, and each element of that cut set was assigned the

value of the cut set divided by the number of elements in the

cut set. The values assigned to each element were added together

and divided by the number of cut sets in which that element appeared.

This process gave the importance number as indicated by the formula.

Using the method described above, the following importance numbers

were obtained for the elements of the three networks

:

FOUR SWITCH NETWORK I

ELEMENT SUM OF VALUES NUMBER OF CUTS v(©)

a 218.667 llO 5 . UU6

b 173. U05 32 5.1CL8

c 391.071; 69 5.667

d 233.072 52 U.U82

e 207.121 3h 6.091

f 161;. 167 33 h.97h

g 302.21LL 61 1;- 951;

h 182.002 29 6.275

i 187. 57U 31 6.050

j 192.073 38 5.051;

k 313.669 h9 6.1;01

m 207.121 3h 6.091

1 201;. 003 2JU 8.500

2 135.335 16 8.U58

3 85.000 7 12.1U2

h 201.50)3 33 6.106

15
FOUR SWITCH NETWORK II

ELEMENT SUM OF VALUES NUMBER OF CUTS v(e)

a 160.833 27 5.956

b 103. 15 6.866

c 193.83!? 28 6.922

d 336.670 62 5.130

© 173.33U 25 6.933

f 273.831 1*7 5.826

g 222.167 38 5.81*6

h 238 -33U 39 6.111

i 173.500 31* 5.102

j 205. 35 5.857

k 2I4

. 8 .168 38 6.530

m 173*331 25 6.933

1 122.501 12 10.208

2 187.002 25 7.1*80

3 225. 22 10.227

1 163.501 18 9.083

FIVE SWITCH NETWORK

ELEMENT SUM OF VALUES NUMBER OF CUTS Me)

a 55U.2U8 119 li.657

b 129. 5H 89 1.836

c 536.851 108 1.970

d 917.331 201 1*.713 e I4.3i.27i 85 5.073

f 165.977 108 1.3H

g 539.263 125 1.311

h 579.089 127 1.559

i 573. H8 121 1.739

j 561*278 132 1.252

k 508.279 9h 5.107

m 181.271 85 5.073

n 521.3IP. 118 1.118

0 718*125 161 1.615

p 563.3U5 120 I. 69I

1 1*21.231 75 5.616

2 316.996 38 8.312

3 308.831 53 5.827

1 351.332 51 6.506

5 255.661* 31 7.519

16
In all of the following lists, the element names given for the

networks are those shown in figures 1, 2, and 3. The letters

refer to links while the numbers are the names of switches.

The orders of network elements implied by the important numbers

given above are as follows, given in descending order:

FOUR SWITCH NETWORK I

3, 1, 2, k, h, h, e = m, i, c, a, b, j, f, g, d

FOUR SWITCH NETWORK II

3, 1, k, 2, e « m, c, b, k, h, a, j, g, f, d, i

FIVE SWITCH NETWORK

2, 5, b, 3, 1, k, e » m, c, b, i, d, p, a, o, h, n, f = g, j

3.2 PATHFINDER-WORTH EVALUATION

All three of these networks were tested using PATHFINDER-WORTH.

Since the networks are quite small, we were able to use several

different path weights with each of the networks and compare the

results of each of these runs with the ordering for the same network using cut sets. The weights used were as follows:

RUN 1 2 3 b 5 6 7

PATH LENGTH

1 1.0 1.0 1.0 .7 1.0 1.0 1.0

2 5.0 1.1 1.0 .6 .7 • b .1

3 10.0 1.3 1.0 •h .05 .05 .01

The orderings in ascending order of importance numbers for

the three networks in these seven runs follows:

FOUR SWITCH NETWORK I

RUN ORDER

1 b, a, e 3 m k* b. h. S3 d. 2, 1, 3

2 3, b. b. e m " k> a . h, S3 d. 2, 1, 3

3 f a

j , i s b) b. e 3 m = k, a , d a S

- h. 1, 2

b f, c. b, b. e ** m “ k> d> S3 a, b, 2, 3

5 U b, d. S, c, b. e 3 m 3 k, a. h, 1, 2, 3

6 h, d. S3 c, b. e “ m * *3 a. h. 1, 2 > 3

7 3, h, d. b. S3 c. e

3 m 3 k, h, a, 2, 1, 3

17
FOUR SWITCH NEIWORK II

RUN ORDER

1 c, d, if if b, 2, k s e a m, a, h, f » g3 b, 3, 1

2 c, is d. if b. k ffl e

3 m, a, h, f « if b, 3, 1

3 o 9 u if d, 2> b, k SS e 3 m, a, f - g

3 h, b, 3 , : h °i i. i. d, 2, b. k 23 e m, f 31 g, a, h, b, 3, l

$ if ©i i» 2, d. b, f a g5 k 3 e » m, h, a, 3, b. l

6 if if 2j d. b. f m gf k 35 e ® m, h, a, 3, b, i

7 if ©i if 2, d. b. f S3 g* k s e » m, h, a, 3, b, i

FIVE SWITCH NEIWORK

RUM ORDER

i c. d. g» o, n, h 3 Pi b. if e 3 m 3 k. a, 1 . u, 3j 2

2 £, c, gi d. i, n, o, h s Pi if b* e 3 m 3 k. a. 1 j H* 3f 2

3 C, g} d. U n, j, h =» 0 ”

Pj b. e

3 m 3 k,, a, if hj, 3 3 : h c, S, n. d9 if 3, h - Pi Of b. 1 , e

3 m 3 k, a j Uj 3, 2 £ n, g, it c. h 3

p, 1 , d. a. if e 3 m 3 k, hi b, o. 3i 2

6 f, n. gi c. h 3 p, 1 , d, if a. e

3 m 3 k, u. b, o, 3, 2

7 f, n. g

it c. h - P, 1, d, a. if e 3 m 3 k, hf bi o. 3, 2

It is clear that those orderings are not identical to, and in some cases not even very close to, the orderings obtained using cut sets.

However, since we are not sure the cut set orderings are optimal,

it is reasonable for us to carry on with the numerical comparison

of these results,

3.3 COMPARISON METHODS

There are three comparison methods which we have used to test

the above results against each other and against a random ordering

of the network elements.

Hie first method we used is the Rank Difference Method, found

on page 39h of reference [1$]. In this method, "given n corresponding

pairs of measured items (X^, Y ), (i 3 1, . n). Let (u^, v_^)

be the corresponding rank numbers. Here u. 3 1 for the largest

X^, 2 for the next largest X , etc., and similarly v^ = 1 for the

largest Y , 2 for the next largest Y_^, etc.

5

5

5

5

5

5

18
p = 1 - 6 I (rank difference) coefficient

i

(u

i ' \

Y

n (n - 1)

of correlation. In every case, - 1 ^ p ^ 1. Check 2_ (u- v. )= 0.”

i — i

Briefly, the larger the value of p, the closer the two lists are

to being identical.

In the second method, we simply counted the smallest number P of

interchanges of elements in one ordering necessary in order to

bring it into the other ordering. In this method, we first

arrange all elements with equal values into their correct relative

ordering in one of the two lists L and L' with respect to the

other list. We do this simply because no ordering of these

elements is preferred (we must remember this fact when considering

the quality of the ordering). Next, beginning with the lowest

element in list L, we count the number of elements with which

that element in list L' must be interchanged to bring it into

the lowest position in list L

1 . This number goes into the

value P. We delete this lowest element from list L' and perform

the same operation with the next element of list L. This

process will continue until all elements of list L' have been

deleted. At this time, P has the desired value. Note that

using this method, no interchange is counted for any element

after it is deleted fhom list L'

.

As an example, consider the two lists L and L' below:

D : a, b, c , d, e / \ L

T : b, e, c, a, H

To bring list L' into the same order as L, we note that a in L' must be interchanged with three elements in order to bring it

into its position in list L. Deleting a from L', we obtain

new L' : b, e, c, d

Now we notice that no interchanges are needed to bring b into

its correct position as the lowest in the remaining lis£ L'.

Therefore, P remains 3. Deleting b from L', we get

new L' : e, c, d.

Now c is the lowest among the remaining elements of L' in L.

Therefore, we add 1 to P, getting h, and delete c from L',

getting

new L‘ : e, d.

19
Only 1 interchanged more is needed to bring d and e into their

correct relative positions. Therefore, for ^e L and L' shown

in (3), P = 5-

The last method of comparing lists is simply a count of the

number of different orderings implied by the equalities present

in the ordering numbers generated by the evaluation techniques

We obtain this count in the following manner: For each set of

equal valued elements, find the factorial of the number of equal

valued elements. For one list, multiply together all factorials

found. The larger the result, the more equalities present, and

hence the less useful the ordering.

The following tables give the results of all three of these tests

for each of the seven runs of PATHFINDER, and for a random

ordering, compared against the order obtained using cut sets:

RUN

FOUR SWITCH NETWORK I

P P EN

1 .1*353 35 6

2 .10*71 37 6

3 .5088 36 72

1* .5530 32 6

5 .7260 21* 6

6 .7382 26 6

7 .7206 25 6

RANDOM • 3235 1*8 0

FOUR SWITCH NETWORK II

RUN P P EN

1 . 1*500 1*2 12

2 .1*291* 10* 12

3 .1*61*7 1*0 72

1* J*79l* 38 12

5 • 5853 30 12

6 .5853 31* 12

7 • 5853 31* 12

RANDOM • 261*7 50 0

20
FIVE ariTCH NETWORK

RUN P P EN

1 .7233 hO 12

2 .7609 36 12

3 .7865 32 Ihh

h .7775 35 12

5 . 77UU 36 12

6 .7 699 37 12

7 .77bh 36 12

RANDOM .1910 82 0

It will be noticed immediately that:

1) Both values P and P are much worse for the random ordering

than for any of the PATHFINDER-WORTH runs.

2) None of the runs produced an ordering identical to that

obtained using cut sets.

The ordering of the runs given by the two tests p and P are,

with the best fit with the cut set ordering first:

FOUR SWITCH NETWORK I

p 6, 5, 7, U, 3 } 2, 1 , RANDOM

P 5, 7, 6, h, 1, 3 , 2, RANDOM

FOUR SWITCH NETWORK II

P 5 - 6 » 7, U, 3, 1, 2, RANDOM

P 5

= 6 = 7, h, 3, 1, 2, RANDOM

FIVE SWITCH NETWORK

P 3, It, S - 7, 6, 2 , 1, RANDOM

P 3, 1*, 2 * 5 - 7, 6, 1, RANDOM

Using the equality count test, we notice that run 3 } where all

path weights were equal, has a much higher equality value than

any of the other runs for all three networks. This suggests

strongly that we should exclude run 3 from further consideration.

21
Among the other runs, runs U through 7 give the best fits with

the cut set ordering, although with varying orders among the runs. For both four switch networks, run £, with path weights

1., .7? and ,0£ for path lengths 1, 2, and 3 switches,

respectively, appears to be the best with respect to cut sets.

In the five switch network, this weighting scheme is bettered

only by run b } with weights .7, .6, and .b. It would appear,

then, that some reduction in value with increasing path length,

so long as the reduction is not extreme, improves the ordering

with respect to the cut set ordering.

In retrospect, this result is not surprising, since elements

in large cut sets are penalised by having the worth of the

cut set divided by the number of elements of the cut set.

We would expect a long path to contain elements of more

large cut sets than short paths, simply because long paths

have more elements. But since the greatest increase in

penalty to cut sets comes with the increase from one element

to two elements (element values change from the whole worth

of the cut set to the worth of the cut set), and falls off

more and more slowly after that, the reduction in weight for

longer path lengths in PATHFINDER should be mild.

Comparing the orderings of the PATHFINDER-WORTH runs with

a random ordering, we notice that even with an extremely

bad weighting scheme such as that of run 1 (l, 5, 10 with

increasing path length), PATHFINDER results are closer

to cut set results than the random ordering is. This lends

considerable weight to our belief that the PATHFINDER

ordering does give an approximation of the ideal "true”

ordering of the network elements. We conclude that elements

found to be high in the PATHFINDER ordering have a good chance

of being important, or worthy of further study, and those

low in the ordering may well be quite unimportant. Notice,

however, that there are elements, such as element b in FOUR SWITCH

NETWORK I, which are low in the PATHFINDER-WORTH ordering and

high in the cut set ordering, or vice versa . Such elements serve

as a warning that we cannot accept the PATHFINDER-WORTH

of the network elements as the final arbiter of network

element importance ; the ordering can only serve as a guide.

22
U.O VALIDITY OF PASSING FROM SMALL NETWORKS TO LARGE ONES

As mentioned previously, we were forced to carry out the

present study using very small networks simply because

of the large number of cut sets even in a five switch

network (h2k of all kinds). But our real concern is

with networks containing 1*0 to 75> switches and a proportionate

number of links. How valid are our conclusions for such

networks?

Of course, we cannot give a definitive answer to this

question without actually carrying out the study for such

networks, a presently impossible task. However, we can note

the effects of going from the four switch networks to the

five switch network and extrapolate from those effects.

First, the largest value of p for the five switch network

is noticably larger (the fit for that run is noticably

better) than the largest values for either of the two

four switch networks, and the smallest value of p (for

the random ordering) is noticably smaller than the

smallest value for either of the two four switch networks.

While the smallest value for P is found on one of the four

switch networks, this is caused partly by the fact that

there are fewer elements to permute on those two networks.

The largest value of P by far is that for the random ordering

on the five switch network.

Although the number of elements in the five switch network

is 2G as compared with 16 in each of the four switch networks,

the number of equalities generated in the five switch network

orderings is the same as the number in one of the four switch

networks and only one more than in the other network. On so small a sample it is dangerous to draw any conclusions, but

it seems possible that the equality number may actually decrease

or at least stay the same with increasing network size. Such

a result would seem reasonable since, with increasing complexity,

the chances of different numbers of different length paths passing

through different links ought to increase.

For the above reasons we can resonably hope that whatever

validity PATHFINDER-WORTH orderings have in small networks

will not be destroyed by increasing the size of the network,

other things being equal.

But what other things might not be equal? First the character

(density and other properties) of the larger network is almost

certainly different from that of the smaller networks. This

situation is unavoidable; however, we selected our examples

to have a density (number of links divided by total possible

number of links, without parallel links) as close to that of

the larger networks as possible. In addition, we attempted

to use proportionate numbers of commands, subordinates,

23
and connections of those elements to the switches. Finally,

we scaled down the maximum path length from 6 to 8 switches to

3 switches (the smallest number which would give values for

every link and switch of the networks),

A second problem is that the path weighting scheme in the

larger network cannot easily be inferred from the path weighting

schemes in the small networks. Fortunately, we need only

extend the weighting scheme from a maximum of 3 switches to 6 or 8 switches, not to 4.0 or 80, since the cut sets and paths

found and used both depend on the maximum path length chosen.

In addition, we notice one additional property of the values of

p and P in Chart II - the values of these measures are quite

close over wide ranges of choices of path weighting schemes.

Thus the orderings are rather insensitive to path weight

variations and we need merely specify a declining weight

with increasing path length, rather than a very specific

set of values for those path weights. Such a simple

specification should yield a usable ordering of the network

elements

24
5.0 CONCLUSIONS

At the very best, this study could add weight to the belief

that the PATHFINDER-WORTH values give an ordering of the network

elements which guides us to important elements (ones high on the list) and unimportant elements (ones low on the list).

In our opinion, the study is successful in this respect.

Our conclusions are as follows

:

1) A moderate amount of reduction in weight for increasing

path length with the PATHFINDER program appears to improve

the resulting ordering of the network elements when compared

to the ordering obtained using cut sets.

2) Network elements found to be high in the PATHFINDER-WORTH

ordering have a good chance of being important, or worthy

of receiving further analysis and possibly even a larger

proportion of our resources, while those low in the ordering

may well be quite unimportant and hence candidates for

deletion from the network.

NOTE: As demonstrated in Section 3.3* however, we cannot

accept the PATHFINDER-WORTH ordering of the network elements

as the final arbiter of network element importance; the ordering

can only serve as a guide for further analysis.

3) For reasons which include insensitivity to variations in

path length weights for PATHFINDER-WORTH values, we believe

the results described above will still hold true for large

networks (containing 1*0 to 80 switches).

25
6,0 CUT SET LISTS

We found the cut sets listed in Sections 6,1, 6*2, and 6.3

by a method involving the following fact? We know that

any cut set which separates more than one commandsubordinate pair must contain, for each of the pairs cut,

a cut set which separates that pair and which cannot be

reduced and still cut that pair. Therefore, for each

network we proceeded as follows? We found a list of

all cut sets for each command-subordinate pair (even in

the Tive switch network there were only 25> at most for a single pair). We then made all combinations of one cut set

from each of two such lists and one from each of the three

lists. The resulting collections of elements were classified

into classification groups by the command-subordinate pairs

they wereTmoTO

_ To^^iime (because of the lists from which

their elements were chosen). Within each classification group,

all sets of elements which properly contained another set of

elements in the same group were deleted, and all but one copy of

each remaining set was deleted. Finally, all cut sets which

appeared in the group classified as cutting all command-subordinate

pairs were deleted wherever they appeared in groups classified

as cutting just two pairs or just one command-subordinate pair,

and all cut sets which appeared in the groups classified as cutting two command-subordinate pairs were deleted from the

groups classified as cutting only one command-subordinate pair.

The resulting lists are those which are given in Sections 6.1,

6.2, and 6,3*

The process described in the previous paragraph could be

readily programmed for the computer, and in fact the portion

which involved combining cut sets was programmed. If the whole

process were computerized, it could be applied to large systems

j

however, the running tine for such applications would be

extremely large (many hours for even moderately large networks).

26
FOUR SWITCH NETWORK I

6 .

1

CUT SETS WHICH CUT ALL PAIRS

a, b, e a, b , m

a, d , h

c > a , 1 > c, f, g,

c 5 i j k

,

c, d, h,

a > a i ^ > c, f , j

,

C, g, h,

a >

*4 > a » a, d, g,

b, c s d

,

b, c, d,

c, d, f,

b, c, d,

b, c, d.

k

h

m

i , k

j , k

k , m

i, J g , ,1 , k

j , k , m

e, f, g

g> m

h, J , k

e » g, i, J g , i , J » m

1 , h 1 , 1, b, m 1,

1 , b , © 1 > 1 , j , k , m 1

,

1 j a j J > k 2 , 1, i, k, m 2,

1, e, i, k 3,

2, a

2, c, f, g

2, c, i, k

2 , c , f , j , k

2, c, g, i, j

3, a, b

3, a, d

3, c, f

3, c, i

4, c, k, m

A, b, c, d, g, m

4 , c , e , k

4, c, g, h

4, a, b, g, h

4 , c, d 3 h , k

4, b, c, d, e, g

4, a, d, e, g, k

4 , a , d, g , k , m

2

3

4, k,

4, e,

c, g

4, c, k

4, c

27

3
CUT SETS WHICH CUT OFF COMMAND 1 BUT LEAVE COMMAND 2 CONNECTED

a, b

c , i , k

c , f , ,1 , k

b, c, d , f, g

a , d , g , j , k

b, c 3 d, g, i, j

CUT SETS WHICH CUT OFF COMMAND

c j e s I

c, i , m

c» e, f, j c , f , j , m

c s d, h 3 i

a, d , g , j , m

a j d, e, g, j

c, d } fj h , ,j

CUT SETS WHICH CUT OFF COMMAND

e, k

k j m

d s h s k

f, g s h

g, h 9 j

b , d j e s f, g

b s d , e s g, j

b, d s f, g, m

b ^ d , g , j , m

, b 1, 4, k

» k

, J * k

, c, k

, a, d , g, k

, b, c s d, g

AND SUBORDINATE 1 OF COMMAND 1

3 e, j 1, 4, m

, j 3 m 1, 4, e

, i, m 2, 4, c

3 a 3 b

3 c 9 i

3 C, f, j

3 C , 6

3 c 3 m

3 a, d, g, m

s a , d } e, g

AND SUBORDINATE 2 OT? COMMAND 1

2, 4, g

3 k

3 f

3 g, J

* S, h

» b, d, e, g

3 b j d , gj m

3 c, d, h

1

11

4

4

4

2

1

1

1

1

2

2

4

4

4

4

2

3

2

2

2

4

44

4

28
CDT3

CUT SETS WHICH CUT COMMAND 1 FROM SUBORDINATE 1

c, i

c > f > J a, d, g, j

a, d, f, g, i

1,1 1 , 4

1, J 4, ca, d, g

CUT SETS WHICH CUT COMMAND 1 FROM SUBORDINATE 2

k 4 , b, d, g

b, d, f, g

b, d, g, j

CUT SETS WHICH CUT COMMAND 2 FROM HIS SUBORDINATE

m 2

, h

g, h

29
6.2 FOUR SWITCH NETWORK II

CUT SETS WHICH CUT ALL PAIRS

a, b , e a, b , m

a, g, h

a, b, f,

b, f, h,

c 5 d.3 ^3

C, d s k s e 3 f, S 3 f\ S 3 h,

f, S* J 3 a j Lj c

j

a, c s f,

b , c , f

,

c, d , f,

^ 3 d 3 g 3 C) 6 3 ^*3 C, f, g,

C 3 f s g 3 d s e s I,

d , i 3 J 3 a ? Qj 6 3 a, d s e

,

a, d, f,

a, d 3 g s a, d, h,

b , d , e , b, d j f,

d, f, h,

d, g s h 3

h

j

k

m

j

j

m

f , s

g 3 m

h, i

h , k

h , k

S 3 i

h, i

i , m

j * k

k , m

S, j, k

h, i, k

h, I j k

j 3 k , m

i , k, m

f, cl, k

j 3 k , m

i, j , k

i 3 J 3 k

1, b

1, S

1, c, d, k

1, d j i, k

2 * b, f, h

2 j d, e, k

2 , d , k , m

2, e, f, g

2 j f, g s h

2

f, gj m

2, d, f, h, k

2

d , g, h, k

3 s a, h

3 3 a , e

3, c s h

3 , c, m

3 3 e 3 J 3, h , j

3 , j , m

4 , a

^3 f, .1 4 S Cj d, k

^3 c, f, i

4 > d, i, j, k

1 , 2 , d, k

1, 3

1, ^ 2, 3, e 2, 3, h

2, 3, m

2 , 4, f

2 , 4, d, k

3, 4, c 3, 4, j

2, 3, 4

.30
CUT SETS WHICH CUT OFF COMMAND 1 BUT LEAVE COMMAND 2 CONNECTED

a. b

c, d, k

f. g, j a. c. f. g

c» f. g, i

d. i. ,1, k

a. d, g s J , k

a, d, b. i, k

b. d, f. J. k

CUT SETS WHICH CUT OFF COMMAND

c. d. e c, d. m

C, d, f. h

C, d, g. h

d. e. i, j

d. i. J , m

a, d, e. g> j a. d. e. h. i a s d, f. h. i a. d. g. J, m

a. d. h. i. m

b. d. a, j

b. d. f. J » m

d. f* b. i. j

d. g. h. i. j

CUT SETS WHICH CUT OFF COMMAND

e. k

k s m

f. h. k

g. h > k

a, e. f. g

a. f. g» m

b, f. h > i e. f. g. 1

f. g. b s i

f. K, i. m

2, d, k 2, 3

2, f, g

3, c 3, j

2 AND SUBORDINATE 1 OF COMMAND 1

1 , c , d 1 , 2 , d

1, d, i 2, 4, d

2, d, e

2 , d , m

2, d, f, h

2, d, g, h

4, d , d

d, i, .1

2 AND SUBORDINATE 2 OF COMMAND 1

1, k 3, 4 3, e

3 » h

3, m

4 > k

4, f, i

31
S

CUT SETS WHICH CUT COMMAND 1 FROM SUBORDINATE 1

c , d 2 , d

d, i, ,1 a » d j g j j

a, d, h, i

d, f, j

CUT SETS WHICH CUT COMMAND 1 FROM SUBORDINATE 2

k 3

a, f, g

f, g» i

CUT SETS WHICH CUT COMMAND 2 FROM HIS SUBORDINATE

e 1

> h

g, h

32
6.3 PIVfi SWITCH NETWORK

CUT SETS WHICH CUT ALL PAIRS

b. e c. h. k. n. 0

b

,

m c

,

h

,

i. k. n. o J, o

,

P c

,

f

,

h

,

1, n, 0

d. e

,

k c

,

g> h

,

k. n, 0

d. k

,

m b

,

c > .1, k, n. 0

I, o

,

P b. c

,

f

,

J, n, 0

b

,

h

,

n

,

0 f

,

g. h

,

k> o. p

b

,

h

,

0 » P a. c

,

e

,

g, h. k. 0

b

,

j. n s o a. c > g> h. m, 0

e

,

h

,

i. j a. d

,

o

,

**» h. J, k

h

,

j± , J, m a. d

,

f

,

h. J, k. m

h

,

k. o

,

P a. d. e

,

f. h. k. P

d

,

h. k s n

,

o a y d

,

f

,

h. m. p

d

,

v h. k

,

o. P a y d. e

,

i> J, k. n

d. .3 , k

,

n, o a. d

,

i

,

J, k. n. n

d. 'j * k

,

o. p a. d

,

i

,

j > k. n. 0

d

,

e

,

g» i. p e

,

d, g> i, .1

»

o. P

d

,

g> i. m. p b. c

,

d. e. g» J, P

d. e

,

f

,

i

b. G , d. g. J, m, P

d. f. g> i. m b

,

C , d. e » f. J, 0 c. d

,

e s h. i b

,

c

,

d

,

f. J'

,

m. o

c

,

X h

,

i. m b

,

c

,

d, e, f\ g> j c

,

*d

,

e

,

• g, i b

,

c

,

d

,

f. g» .1, m

G , d. g. i. m b. c

,

d

,

e. f. i. o

e > i. k, n. P b. c

,

d. *\ i. m. o i. k

,

m, n. P c

,

d

,

e > f. h. i. o

e

,

g. i. n. P c

,

d

,

f

,

h. i, m. 0

3> g, i. m, n } P d

,

i

,

J, k. a » o. p

e

,

' f

,

k j n. P d

,

0, i, J, n. 0, p

f

,

k

,

m

»

n. P d. f

,

J, k, n. O, p

h

,

i. j, n. o b. d

,

e » g. J, n. p

d s e

,

k

,

o s P b. d. g* J, m. a . p

d. k

,

m. o. P a. e

,

f

,

g> h. J, k

d. e i i. o. P a. f

,

g. h. J, k. m

d, i. m. o 3 P a. d

,

e

,

g» i> J, n

d } e

,

k. n. P a. d

,

g, i. J , m. n

d

,

k. m, n. P a, d

,

g> i> J, n. o d, e

,

h. i. P a. d

,

e > f. j. k. n

d

,

h

,

i. m. P a . d

,

f

,

j. k. r.. n

c

,

e

,

h s i. 0 a. d

,

f

,

J, k. n. 0

c

,

h

,

i. m. 0 a. c

,

e

,

g. h. J, k

c

,

h. i. n» 0 a. c

,

g. h. J, k. m

g. h. k. o. p c

,

d

,

f

,

g. i. j. n.

f , h. k. o. p a. f , g. h. J, k. n.

33
CUT SETS WITH SWITCHES WHICH CUT ALL PAIRS

1, d ? e 3 k 3 , c, d, f. m. 0

1, d 5 k. m 3 , c» d 3 e. s, P

1, h. i, 0 3 , C, d, S, m. P

1, b s J 3 0 3 , d. e. k 3 n, P

1, d, h, k

0 3 , d, k. m s n, P

1, d, J 3 k 3 0 3 , d. e 3 s, n, P

1, d. e. S3 i 3 3 d s s, m, n. P

1, d j S3 i. m 4 , c. d, e 1, a, b. h, 0 4 , c, d, m

1, S 3 h. k 3 0 4 , h. 0, P

1, b, b 3 k s 0 4 S d. e, n s P

1, d. S» i > J 3 O 4 3 d s m. n s P

1, a, d. e 3 h, i 4 , a. e. h, j

1, a s d. h 3 i

m 4 3 a s h. J , m

1, b

d. e s S3 ,1 4 * c. h, 11 3 0

1, b j d. S, J, m 4 , c. d, j, a. 0

1, b, d. e 3 13 0 4 , C, d. 3 , 0, P

1, b, d s i

m s 0 4 3 d. .1 3 n 3 0, p

1, a s e. S 3 h. .1, k 4 , a. b s J 3 n 3 0

1, a. R } b 3 .1, k, m 4 3 a. d, e, h, P

2, c s k 4 , a s d. h, m, D

2, a. b 4 3 a

C , e. h. O

2 > i > p

4 3 a 2 C, b. m, O

2, a j c s i 4 3 a. d, e. J, n

2 > c. f. i 4 3

cL ^ d s ,J 3 m, n

2, b. k. P 4 , a. d s j. n. 0

2, b, J 3 P 4 , b. d, e. 0, P

2, f*- 3 k. P 4 * b, d. m, 0, P

2, a. j 4 , b 3 c, .1 3 n 3 0

2 i b 3 c. f. j 5 , b

2, a 3 f. ,1 3 k 5 , h s i

3 , a. e 5 , C 9 d s k

3 j a. m 5 , c s d, S, i

3 , o. D 5 , C, S, h $ k

3 , a. n, 0 5 J d. f» h 3 k

3 s c> k. 11 3 0 5 , d 3 f\ k. n

3 9 C , f. n 3 0 5 , d. i. k 3 n

3 , C, d. e* f. E 5 , d. S> i s n

3 , c, d. f. S 3 m 5 , f. S» b s k

3 , C, d j e, f. 0

34
CUT SETS WITH SWITCHES WHICH CUT ALL PAIRS

1, 2, i

1, 2, k

1, 2, b, j

1, 3, o 1» 3, d, g, m

1> 3 , d , 6, g

1, 4, d, e

1 , 4 , d , m

1, 4, h s o

1 , ^ , d , j » o

1, 5, d, k

1, 5, d, g, i

1» 5, g, h, k

2, 3, a

2, 3 j P

2, 3, c, f

2, 4, c 2, 4, p

2, 4, a, j

2, 5, i

2 3 5, f, k

3, 4, c, n, o

3 } 5

5, h

4 s 5, d, n

4, 5, c, d

1, 2, 3

1, 2, 4 1,

^

5, d

2, 4, 5

35
CUT SETS WHICH CUT COMMAND 1 AND LEAVE COMMAND 2 CONNECTED

a. b , c. d s k

a j b. i » j c. d. g s i. P

c. d, f. g» i a. c, d, h. i

a, C, d. i

d. i» k. n, P

d. g» i. n > P

d, f. k. n, P

b s d, k s o s P

b 9 d. i, o 9 P

b, d > k. n » P a. d * h. i, P

a* c, b* 0

b, C, d

.1 5 P

b, C, d s f. J, o

b s C, d, f. J b, C, d, f, i. o

c. d, f. h. i j 0

b. d. S» J, n. p

a, f. h* j , k a. c. b. .1 * k

a j C, b * k. o a. d » f. h } j s k

a } d

f. b 3 k s P a. d, i> J , k s n a. d 9 i» J ? n

a, df. .1

k, n

b j c 9 b. k } n. o

d, k

i, d , 1, a, d,

1, b, d,

a, g,

3, a

3 » c, d

3> c, d,

3, c, d,

3, d, k s 3, d, g,

c, d

d , n,

a, h,

a, d,

^ a, c,

4, a , d,

b, d

1, b, d.

h, i

i, o h , j , k

£

f, o g» P

n, p

n, p

P

j

h, p

fr, Q

j , n

o, P

J

1, 3, d, g

1, 4, d

36
CUT SETS WHICH CUT COMMAND 2 AND SUBORDINATE 1 OF COMMAND 1

c , d , e

c , d, m

b s h, o,

c, d, h,

c, d, h,

c, d, j,

c 3 d , j , d j a , i , d, i, m,

d j e , f,

d, f, m,

b, d, e,

b , d, m,

b s d 9 e,

b , d , m,

c, g, h,

d, f, h,

b, c s h,

c, h, i

3

c, g, h,

d » c, j ) f*, g, h,

d, i, j,

d »

f* » J j a, e, f, a j f > F>> a j c 9 g 9 a, c, g,

a, a > 6 }

a, c, g,

a, d 9 e j a, d, f,

a, d, e,

a, d, f,

a, d, e 9 a, d, i,

a , d , i j a, d j e s a, d, f,

a 5 d, f,

a, f, g.

P

n, o o, p n 9 o o, p n * P

n, p

n, p

n 9 p

o, p

o, p

n s P

n, P

o, p

0, P

n, o n 9 o n, o n , o

o } p

n, o, p

n, o, p

g, h, j

h, j , m

g» h , J h s j , m

g, h, o h, m, o

f\ h, j

h, j , m

h, p

hj m, p

1, ,1 > n

j , m, n

j , n, o

f , j , n

j , m, n

j » n , o h, j , n, o

1 , d , e

1 , d , m

1, d, h, o 1» d, j , o

1, g, h, o

1, b, h, o

1, a, e, g » h, j

d» a , g 9 h , j 9 m

2, c 2 s b, p

2, f, P

2, a, f, j

3, c s n, o 3, d, e, n, p

3, d, m, n, p

5, c, d

5, c, g, h

5, d, f, h

5, d, f, n

5, d, 1, n

5, f, g, h

1, 2

1, 5, d

1» 5, g, h

2, 5, f

37
CUT SETS WHICH CUT COMMAND 2 AND SUBORDINATE 2 OP COMMAND 1

e. k 1, b 3 k, 0 1, 3, g.

k. m 1, 3 , k. 0 1, 3, e j h, k. n. 0 1, e. g» i 1, 4, J , h 9 k. o. P 1, g» i » m 2, 3, f

,1, n, 0 1, g. i. .1, 0 2, 4

J » k, o. D 1, b s e, g. j 3, n,

e i gi» P 1, b. g» .1 , m *», 5

g> i. m. P 1, b. e. i , o e, f. g. i 1, b. i, m, 0

f, s > i > m 2, k

a. e, h. i 2, a. i a. h. i> m 2, f. i a. e. g. i 2, b. f. j a. g. i. m 3 , k. a. 0

g, i. j > o. P 3, e. f. g

a. h. i

n > o 3, f. g. m

b. e. g. J , P 3, e. f. o b. g> J , m. P 3 , f. m. o b. e, i > 0, P 3, f. n. 0

b. i, m, o. P 3, e. g, P

b. e > f. J , o 3, g. m. P

b. f. •1 , 0 e b. 3 , n. 0 m

b. e. f. g» j b, n. o b, f. g. J » m J , o. P

b. e. f. i > o 5, k

b. f. i. m, 0 5

g> i e. f. h. i i 0 .1 » a. 0

f. h. i > m, 0

f. b i i. n t 0

f. g. i > J > n s o a. g. i» J > n. o

38
CUT SETS WHICH CUT ONLY SUBORDINATE 1 OF COMMAND 1

c , d

d, i, n, p

d , f j n , p

1, d

1, a, g, h, j

3, d, n, p

b, d, o, p

b, d, n, p

a, f, g, h, j

a, c, g, h, j

a, c, g, h, o a, d, f , h, '

j

a, d , f , h , p a , d , i , j , n

a j d , f, .]" y n

CUT SETS WHICH CUT ONLY SUBORDINATE 2 OF COMMAND 1

CUT SETS WHICH CUT ONLY THE SUBORDINATE OF COMMAND 2

1, g* i

1, b, g, j

1,-L , b,U , i,J. o

3, f, g

3, f, o

3, g, P

4 b , g 5 j , p

b, i, o, p

b , f , j , o b, f, g, j

b, f, i, o h. i. o

h , n, o h, o, p

j , n, o

j > o, p

em

1, h, o

X , j » o

2

3, n, o

5

39
6.h ORDERING COMPARISONS

For each of the networks and runs, the following graphs give the

comparison between the orderings obtained using the cut set

method and using PATHFINDER-WORTH. Rank positions are listed on the vertical axis of each graph. Along the horizontal axis is the

cut set ordering found for the given network, and a diagonal line

is drawn through the chart based on the ordering given. Note that

if two network elements were found to have equal values using

either the cut set method or PATHFINDER-WORTH, they are given

identical rank orderings, there being no way to distinguish between

the two elements

Below the cut set ordering list is the list of the network elements

in the order given by PATHFINDER-WORTH, using the adjustments

shown in the upper right-hand corner of the figure. This second

list is numbered from left to right to give the rank ordering, and,

for each element in this list, its proper location on the graph is

plotted with a large dot. Finally, the values of P and p for the graph

are given in the lower right-hand corner of each graph.

40


43

45
46
^7




52
53
54
b5

57

59


( 1 r «n 7 ?

!=iVj IfH -V1- WIJ — akmx- WW . % 4a]—

3fT[I,i _- i- l/: <5

| 'i f

.U.

v..

ti: L . 57^-t. 11. • i. ;!e

-ft Jti LL.rl Ids i-

_ FF

_ W

•• i

A

LI-ji

J

“1tv~

- L - J -

ir «--

-IF-- 4b —

-ft

1 H—

4> -4>— 4V t- —

<3 —1

« —

7— T

5

• 4 o

5

4)-- J —

f --< 5— --4-

_s

‘ ' r- «hA- — V

-t i 1 a

_

] •HI-

‘J | - - ii H T-r- 1Or-"cl (J b C“-W= r k „

- / , Jir- /.

&/

—

/

—fc f*-- r - } — Mr -A Sb —a : --le --fi

"* r

; -4)-

I l :;:

~ 5 u - 1 -t mi1 .* 5 * _1_L1 •i 1 i

02
b3

APPENDIX B

The solution for the following mathematical problem could be

directly applied to the problem of determining the optimal

number of and locations for the switches and inter-switch

links of a military communications network which uses

pre-existing civilian facilities with the purpose of

attaining the maximum connectivity permitted by those civilian

facilities:

Given a graph G, a positive integer k, and a subset S of the

set of all paths in G, find a graph H such that:

1) the vertices of H are vertices of G;

2) the edges of H are paths of G;

3) for every path s in S there is a path h in H such that

every edge of h is a subpath of s, the first vertex of

h is the first vertex of s, the last vertex of h is the

last vertex of s, and the number of edges of H in h is

less than k; and

li) H minimizes a function from the set of all graphs

satisfying conditions l), 2), and 3) to the set of

positive real numbers. (Typically, this function is a cost function.)

65
REFERENCES

1. Krakowski, M., Additivity and Non-Additivity in Communication

Networks, Working Paper, Project b556li5>5, 12 July 196?,

revised 8 August 1967, published as the first part of Some

Considerations in Assignment of Values to Elements of

Communications Network, by M* Krakowski, Working Paper,

Project September 1967

2. Krakowski, M., Linear Programming Approaches to Evaluation

of Elements of Communication Network, Working Paper, Project

b5$6k55>, 15> September 1967, published as the second part of

Some Considerations in Assignment of Values to Elements of

Communications Network, by M. Krakowski, Working Paper,

Project September 1967-

3. Hobbs, Arthur M., Programmers' Manual for the Pathfinding

Importance Number Generator, Report of Project

6 September 1968, continuation of same, 27 November 1968.

U. C.R.C. Standard Mathematical Tables, Twelfth Edition,

page 39h, Chemical Rubber Publishing Co., Cleveland, Ohio, 195>9 •

66