IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 1 of 17
`
`

`
`I t \
`
`J
`
`COMPUTER
`COMMUNICATION
`''
`( I I� l" ( C I '-£ <
`NETWORKS 1
`I {';
`. (',
`1\
`c
`
`. ,
`
`,_,
`
`. ·\
`
`edited by
`
`R. L. GRIMSDALE
`
`Professor of Electrical Engineering
`of Sussex, U.K. University
`
`
`and
`
`F. F. KUO
`of Hawaii
`
`Professor of Electrical Engineering
`
`
`University
`
`NOORDHOFF- LEYDEN- 1975
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 2 of 17
`
`

`
`Proceedings of the NATO Advanced Study Institute
`on Computer Communication Networks
`Sussex, United Kingdom
`,.
`September 9-15, 1973
`
`\·--:::!..1
`c -I
`MRY i 197b
`
`ISBN 90 286 0593 2
`@ 1975 Noordhoff International
`
`of A. W. Sljthoff International
`
`
`
`Publishing, a division
`
`Publishing Company B.V.
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval
`
`photocopying,
`
`
`system, or transmitted, In any form or by any means, electronic, mechanical,
`recording, or otherwise, without the prior permission of the copyright owner.
`
`Printed In The Netherlands.
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 3 of 17
`
`

`
`PREFACE
`
`v
`
`In 1968 the Advanced Research Projects Agency (ARPA) of the
`
`U.S. Department of Defense began implementation of a computer­
`
`communication network which permits the interconnection of heter­
`ogeneous computers at geographically distributed centres through­
`out the United States. This network has come to be known as the
`ARPANEI' and has grown !'rom the initial four node configura. tion in
`1969 to almost forty nodes (including satellite nodes in Hawaii,
`Norway, and London) in late 1973 .. The major goal oi' ARPANEI'
`is
`to achieve resource sharing among the network users. The resources
`to be shared include not only programs, but also unique facilities
`such as the powerful ILLIAC IV computer and large global weather
`
`data bases that are economically feasible when widely shared.
`
`The ARPANET employs a distributed store-and-forward packet­
`switching approach that is much better suited for compute:t'­
`communications networks than the more conventional circuit-switch­
`ing appro ach. Reasons favouring packet switching include lower
`cost, higher capacity, greater reliability and minimal delay. All
`of these factors are discussed in these Proceedings.
`
`Since the initial ARPA experiment and success, a number of
`packet-switched networks have been planned and designed and some
`a.re well on their way towards tu lly operational status. These
`networks include: COST-11 being developed by a multinational
`Eu ropean effort, which when completed in 1975, would link together
`major computer science centres in England, France, Switzerland,
`and Italy; CYCLAJ)ES, a French network linking centres in Paris,
`
`Rennes, Toulouse and Grenoble, planned for initial operation in
`early 1974; the Experimental Packet Sw:i:tching System (EPSS) of the
`British Post Office which has reached the advanced design stage,
`
`and which when completed will represent the first major packet­
`switched service offered by a common carrier; and SITA, a !'ully
`operational, special purpose network for European airlines, devel­
`oped and operated by Societe Internationale de Telecommun
`ications
`Aeronautique.
`
`With so m� diverse networks being designed, we, the organiz­
`
`ers of the Institute, felt that it was important to bring together
`most of the networks groups for the purpose of learning each other's
`te each other's
`design approaches and philosophies and to evalua
`methods to determine their advantages and drawbacks. Thus the pro­
`gramm e of the Institute focussed upon the major problem areas in
`the design and ope�ation of these networks. Topics included:
`Software and Hardware Design, Analytical Techniques, Network Design,
`Satellite Transmission, Economic Considerations, and Descriptions
`of Existing and Planned Networks.
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 4 of 17
`
`

`
`101
`
`Topological Design Considerations in Computer Communication
`
`Networks
`
`v. G. Cerf
`
`D. D. cowan
`
`R. c. Mullin
`
`Stanford
`University
`
`University of
`Waterloo
`
`Uni ver si ty of
`Waterloo
`
`and
`R. G. Stanton
`
`University of
`Manitoba
`
`I NTRODUCTI ON
`
`In designing a computer-communication network, a large
`number of constraints must be considered so as to produce a
`reasonable network topology. Time delays, throughputs, cost, and
`reliability are some of the major factors connected with
`producing an optimum design.
`Each of these factors encompasses
`a large amount of detailed analysis which must be completed in
`order to check a network design.
`
`Since network design is such a complex task, it is important
`to provide the designer with simple criteria for evaluation.
`Such criteria permit the network designer to develop an intuitive
`feeling for his designs, and to be aware of the effects of
`modifications on its parameters.
`
`This paper uses a linear graph model of computer­
`communications networks to establish a lower bound on delay and
`vulnerability! for such networks. The networks which are
`analyzed have the property that their graphs are regular. The
`lower bound on delay is characterized by measu.ring the average
`minimum path length in these regular graphs. The vulnerability
`of these same networks is shown to be equal to the valence of one
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 5 of 17
`
`

`
`102
`of the vertices for the trivalent graphs, and it is conjectured
`that this is true for higher valences.
`Both these criteria would appear to be useful in that
`designers may measure their network against these so..called
`"ideal" networks. This paper will only describe the bounds.
`Subsequent papers will provide algorithms for construction of
`graphs which satisfy these bounds and proofs of the vulnerability
`criteria.
`
`BACKGROUND
`Many factors can influence the design of computer­
`communication networks. Constraints such as acceptable upper
`bounds on cost and delay and lower bounds on throughput and
`In packet­
`reliability can strongly influence the final design.
`switched store-and-forward networks2,3, topology can play R major
`role in satisfying the delay and reliability constraints.
`Packets leaving a source node are routed to intermediate
`nodes until they finally arrive at their destination node. At
`each node, a packet undergoes several forms of delay. These
`include processing delay, queueing delay (if other packets are
`also routed over the same channel), transmission delay, and
`propagation delay on the channel. Typically, a packet carries a
`checksum with it; thus, a packet arriving at a node cannot be
`forwarded until the last bit of the packet has arrived and the
`checksum has been verified. It seems apparent that minimizing
`the average number of nodes and communication lines a packet has
`to pass through to reach its destination can reduce delay; of
`course, an alternative routing strategy which is sensitive to
`local congest�on may not always route the packet along the
`shortest path .
`Reliability of networks can be characterized in several
`different ways depending upon the degree of refinement one
`requires in an analysis. Once a network has been designed, there
`are a variety of computational approaches to analyzing reliability
`which are neatly summarized in Frank and Chou2. According to
`Frank and Chou, present analytical approaches are computationally
`intractable for large networks and a combination of analysis and
`simulation is required to obtain estimates of parameters which
`characterize the reliability of a network and its components.
`Very little is known, a priori, about the reliability of networks
`except that duplication of components and selected over-connection
`seem to improve it.
`There are several possible strategies for reducing delay and
`increasing reliability of a network, but in this paper we
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 6 of 17
`
`

`
`103
`concentrate on the effects of topology. Specifically, we examine
`the relationship between average path length and the number of
`nodes connected directly to a node (valence of the node}.
`
`This paper presents a study of networks which are represented
`as linear graphs, and it is assumed the reader is familiar with
`elementary notions of graph theory5. The analysis will be
`directed to packet-switching networks, but most of the work
`presented should be applicable to networks which use other
`mechanisms for routing and switching data. The nodes or vertices
`of the graph will be the packet-switching computers, and the
`edges or links will represent the transmission lines.
`
`It is possible for networks of arbitrary size to maintain a
`maximum and average path length of either one or two.
`If every
`node in an N-node network is connected to every other node, then
`we have a network where each node has valence N-1 and the shortest
`and average shortest path lengths are one.
`Figure 1 shows an
`example for N=6. The reliability of this network is very high,
`since every node is connected to every other node; however, the
`number of edges is N(N-1), and thus the cost of transmission lines
`2
`such a
`would increase with the square of the number of nodes.
`scheme is completely impractical for even moderate values of N.
`
`Fully connected 6 node graph
`Figure 1
`
`To keep th� maximal shortest path length constant at two, one
`can join all nodes through a central node as shown in the star
`network of Figure 2. Here transmission line costs increase
`linearly with N, but reliability and capacity of the central node
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 7 of 17
`
`

`
`104
`
`pose serious problems.
`
`9 Node star net
`Figure 2
`
`Such extreme cases are impractical, and hence intermediate
`schemes with average valence between 2 and N-1 are of prime
`interest. The next portion of this paper examines the relation­
`ship between valence, averag.e path length, and reliability. This
`relationship will allow an examination of the trade-off between
`average path length and number of transmission lines in the
`network; thus, we will develop a measure of the cost of a network
`as a function of its size under a suitable delay constraint. Some
`comments will also be made on the relationship of reliability and
`valence.
`
`AVERAGE PATH LENGTH IN A ClASS OF GRAPHS
`
`This section examines the network topology which produces
`minimum average path length, and presents an expression which is a
`lower bound on average path length under reasonable constraints.
`There is a short discussion of graphs which satisfy this lower
`bound, but the actual construction techniques are discussed in
`another paper6.
`
`The analysis is started by considering a tree with
`
`m-1
`1 + v I:
`j=O
`
`(v-l)j
`
`(1)
`
`nodes in which each node has either valence V or valence 1.
`
`A
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 8 of 17
`
`

`
`105
`
`tree with 10 nodes and V=3 is illustrated in Figure 3·
`One node
`is chosen as the root node and is labelled R in Figure 3· The
`root node R is considered to be at distance zero from itself in
`the tree, the V nodes adjacent to R are at distance one from R,
`the V(V-1) nodes adjacent to those at distance one are at distance
`2, etc. For ease of expression nodes at distance m from R will be
`referred to as "nodes at level m". The levels are shown on the
`1·igh t side of Figure 3. A tree such as the one just described is
`called a complete tree since new nodes can only be added by
`starting a new level. In order to find the average path length
`from R to all nodes in the tree, it is necessary to sum all paths
`and then divide by N-1. Since �here are V paths of length 1,
`v(v-1) paths of length 2, V(V-1)2 paths of length 3, etc., the
`average path length of a complete tree with m levels is
`
`N-1 [ m-1 ]
`
`1
`
`V i:
`j=O
`
`(V-l)j (.i+l)
`
`•
`
`R
`
`Complete 3-level Tree
`Figure 3
`
`(2)
`
`0
`
`2
`
`By removing monovalent nodes at the highest numbered level
`and their associated edges in the complete tree it is possible to
`arrive at a formula for average path length in a more general tree
`of th�s type. If the number of vertices in this tree is N, then
`the number of vertices removed is
`
`(V-1 )j - N.
`
`m-1
`1 + V i:
`j=O
`Then the average path length P( N, V) in this "pruned 11 tree is
`
`(3)
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 9 of 17
`
`

`
`106
`
`j
`P(N, V) = N-l V E (V-1) (j+l)
`j=O
`
`1 [ m-1
`-(1 + V n-;1 (V-l)j - N) m],
`
`j=O
`which can be written as
`
`One might note that
`m-1
`1 + V E (V-1 )j - N > 0.
`j=O
`and that m is the smallest integer which satisfies this inequality.
`Since
`
`(6)
`
`(V-l)m - 1
`V-2
`
`then
`
`(4)
`
`(5)
`
`(7)
`
`( 8)
`
`(9)
`
`1 + v�2 [<v-l)m - 1 J - N? o.
`Also, if we use (y) to denote the least integer? y, then
`m = � logV-1 N(V-�) + 2 �' for V > 2.
`
`If we substitute for m, it is possible to obtain a more explicit
`relation between the average path length P(N,v), the number of
`nodes N, and the valence v.
`It can easily be seen that
`V rr;l
`j=O
`
`2 [m(V-l)m+l
`V
`(V-l)j(j+l) =
`(V-2)
`- (m+l)(V-l)m + 1] (10)
`and, using (7) and (10), the average path length can be written as
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 10 of 17
`
`

`
`107
`
`( 11)
`
`+
`
`l
`
`P(N,V)
`N-1
`
`= _1_ [v(m{V-l)m+l-(m+1)(V-lt
`+ 1)
`(V-2)2
`_ mv ((v-l�=2 -') + (N-l)m]
`V [1 -(V-l)m + m(V-2)] + m
`(V-2 )2 ( N-1)
`= .3_[1-(V-l)m + m(V-2)]+ m
`N-1 (v-2)
`(9), as
`
`Expression (11) can be rewritten, using
`P( N, V) {logV-l N(V�2) + 2}
`V [l _ (V-l) jlogV-l N(V-2) + 2l
`V �
`2
`(N-l)(V-2)
`+ (V-2) 1logV-l N(V�2) + 2 � 1
`(12)
`
`
`
`This expression is dominated, for reasonably large N, by the
`
`
`
`
`leading logarithmic term. Therefore, the average path length
`
`from R to all nodes of the tree in Figure 3 is primarily
`
`logarithmic in N except for the case V=2 in which it is linear.
`Curves fox· P( N, V) for 2 < V < 6 and V+l < N < 1000 are shown in
`
`
`4, and these graphically illustrate the logarithmic nature
`Figure
`of
`of the average path length (and hence the delay) as a function
`
`the number of nodes in the network.
`
`Table I p1·esents a few values
`
`
`of average path length for different Nand V. The reader should
`
`
`
`note the drastic reduction in average path length between the
`cases V=2 and V:3· But an increase
`to v�6 for N=900 only reduces
`
`
`the average path length by a factor of approximately 21 while it
`
`increases the number of edges in the graph from 1350 for V=3 to
`2700 for V=6.
`
`
`
`
`This analysis presents a derivation of the average path
`
`length for trees similar to the tree of Figure 3· It is certainly
`
`
`the minimum for a tree joining N nodes, since any method of
`
`
`connecting the nodes would either produce the same configuration
`
`
`
`
`or would violate the valence constraint. An important related
`
`
`
`
`question is whether it is possible to construct a graph which has
`valence
`
`
`V and for which expression (12) is also the minimum average
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 11 of 17
`
`

`
`p
`
`0
`
`V=3
`
`V=4
`V=5
`
`=6
`
`Figure 4 Plot of P(N,v)
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 12 of 17
`
`

`
`109
`path length. Such a graph could possibly be constructed if the
`nodes of valence unity of a tree such as the one iri Figure 3 could
`be joined to make a V-valent graph such that, by choosing every
`node in turn as the root node, we could redraw the graph as a tree
`having a complete set of nodes at each of levels O,l,2, ... ,m-l.
`Since all distance sets would be identical for each root node, the
`minimum average path length from each node would be the same, and
`therefore the minimum average path length for the entire graph
`would be expression ( 12 ) . The maximum path length in such graphs
`is just m; so equation (9) shows that this quantity also grows
`logarithmically. Even if graphs with this property cannot be
`constructed for particular N and V, expression ( 12) still repre­
`sents a desirable lower bound on average path length, and thus
`presents information about the behaviour of average path length,
`and hence delay, as a :function of valence.
`
`N
`
`8
`20
`50
`100
`250
`500
`900
`
`2
`
`2.29
`5.26
`12.76
`25.25
`6 2.75
`125.25
`225.25
`
`v
`
`3
`1. 57
`2.37
`3.41
`4.27
`5·55
`6 .52
`7.32
`
`4
`
`1.43
`1.95
`2.59
`3· 27
`4.07
`4.57
`.5.20
`
`5
`1.29
`1. 74
`2.39
`2.70
`3·45
`3.88
`4.38
`
`6
`1 .14
`1. 68
`2.14
`2. 58
`3.08
`3.54
`3·75
`
`Table I
`Some Typical Values of P( N, v)
`
`Fortunately, we are able to construct graphs which attain
`this lower bound for many values of Nand V. The analysis of this
`problem in graph construction and the complete enumeration of many
`of the cases is discussed in another paper6. So far, graphs are
`known fol' V=3, and N=:l!, 6, U, 10, 12, ll.J., 16, 18, 20, 211, 26, 28,
`30, 34. It is also lmown that graphs do not exist for certain
`values of �. An example of such a minimllm average path length
`graph is shown in Figure 5. This is the graph for V==3 and N=lO,
`and is the well known Petersen graph.
`
`RELIABILITY OF NETIVORKS
`
`This section describes some preliminary results on the
`reliability of networks with minimum average path length. In
`particular, vulnerability of these networks is examined.
`
`A basic measure of vulnerability! is usually defined to be
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 13 of 17
`
`

`
`110
`the number of nodes and/or edges which must be removed from a
`network or connected graph in o;der to separate it into two
`
`disconnected components. An algorithm has been devised1 which
`
`will compute the vulnerability of a given network, but there are
`
`no known results to describe the behaviour of a class of networks.
`
`The availability of knowledge of the behaviour of such a class
`
`
`would provide the network designer with an intuitive feeling for
`what could be achieved.
`
`Figure 5
`A Minimum Average Path Length Graph
`for N = 10, V = 3, P(N,V) = 5/3
`
`The class of graphs with minimum average path length has
`
`
`many properties which make it amenable to vulnerability analysis.
`
`It has been shown7 that the class of cubic or trivalent
`graphs satisfying the minimum average path length constraint are
`3 -connected. This means that at least 3 nodes must be removed
`
`from the network before two disconnected components can be
`realized.
`
`K = K(G) as
`If we define connectivity or node-connectivity
`
`the minimum number of nodes in a graph G whose removal results in
`a trivial graph or a graph of two or more components, define line­
`A = t.(G) in an analogous fashion, and define 6 = a(a)
`connectivity
`as the minimum valence in a graph1 then these three quantities
`are re�ated by an inequality due to Whitney 5,8, namely,
`K(G) S f.(G) < 6(G).
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 14 of 17
`
`

`
`111
`This inequality implies that, if each node of a graph has uniform
`valence V and if K�v, then A=V also. For the case V=3, then A=3·
`
`We conjecture that graphs with minimum average path length
`and valence V are V-connected for V > 3· This conjecture seems
`reasonable, since graphs which satisfy the path length condition
`would have vertices "closely coupled" by edges.
`
`The question of separating a graph into components by
`removing a mixed set of points and lines has been studied5, 9. The
`separation of a graph G is characterized by a connectivity pair
`(a,b) which is an ordered pair of non-negative integers such that
`there is a set of a nodes and b edges whose removal disconnects
`the graph, and there is no set of a-1 nodes and b edges or a nodes
`and b-1 edges with this property.
`
`For graphs which are V-connected, it has been shown7 that
`there is a unique sequence of connectivity pairs which completely
`characterizes the vulnerability of the graph. The general
`expression for this sequence is
`
`( 2' v -2)' ( 1' v -1 ) ' ( 0' v) •
`(V=O), (V-1, 1 ), (V-2, 2)
`The sum of the two entries in each pair is a constant v, and this
`means that a combination of nodes and edges whose sum is V will
`completely disconnect the graph or reduce it to the trivial graph.
`
`CONCLUSIONS
`
`This paper has studied certain properties of linear graphs
`representing computer-communication networks. In particular, an
`expression has been derived which provides a lower bound on the
`average path length of a graph with N nodes and constant valence V
`for each node. Graphs which satisfy this lower bound have been
`constructed for many values of N with particular emphasis on the
`value V=3· These graphs with minimum average path length have
`other properties which make them useful models for networks.
`Since they have nodes of constant valence, they also provide a
`convenient model for reliability analysis,
`In particular, for
`V=3, it has been shown that the graphs are 3-connected and that
`their complete connectivity, and hence vulnerability, can be
`specified. It is conjectured that such graphs with higher valence
`V are V-connected, If this is the case, their vulnerability can
`also be completely specified.
`
`This analysis describes an achievable lower bound on both
`path length and vulnerability for constant valence graphs, and
`provides a convenient norm against which the network designer can
`compare his designs.
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 15 of 17
`
`

`
`112
`ACKNOWLEGEMENrS
`
`The authors would like to acknowledge the support of the
`Joint Services Electronics Program under contract number N-0014-
`67-A-0112-0044.
`
`REFERENCES
`1. Frisch, I. T., Analysis of the vulnerability of communication
`nets, Proceedings of the First Annual Princeton Conference on
`Systems Science, 1967, 188.
`2. Frank, H. and Chou, w., Topological optimization of computer
`net�orks, IEEE Proceedings, 60, Nov 1972.
`3· Gerla, M., The Design of Store-and-Forward (sjF) Networks for
`Computer Communications, School of Enginee1·ing and Applied
`Science, University of California, Los Angeles, 1973 (UCLA­
`ENG-7319 ).
`4. Fultz, G. L., Adaptive Routing Techniques for Message
`Switching Computer-Communication Networks, School of
`Engineering and Applied Science, University of California,
`Los Angeles, 1972, (UClA-ENG-7252).
`
`5. Harary, F., Graph Theory, Addison-Wesley Publishing Co., New
`York, 1969.
`
`6. Cerf, V. G., Cowan, D. D., Mullin, R. C. and Stanton, R. G.,
`The Generalized Moore Graph, to appear.
`7. Cowan, D. D., Some Results on the Connectivity of Trivalent
`Generalized Moore Graphs, Computer Communications Network
`Group, Department of Computer Science, University of Waterloo,
`Waterloo, 1973.
`8. Whitney, H., Congruent graphs and the connectivity of graphs,
`American Journal of Mathematics, 54, 150, 1932.
`9· Beineke, L. W. and Harary, F., The connectivity function of
`a graph, Mathematika, 14, 197, 1967.
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 16 of 17
`
`

`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1015 , p. 17 of 17