. search Abstract '
`
`Page 1 of2
`
`uses HOME l SEARCH user:
`
`I snow I was ACCOUNT l cormxcr IEEE
`V‘i'n'iV‘
`.
`. .... .
`
`St andgfina r"e'e;r s~'/5:1 abvs.
`
`
`
`E}1Le_rJ,t,b_e_i:sh.ip; ._Ru b l i c at-i o n s-I-S erv i c as "
`
`Welcome
`United States Patent and Trademark Offic
`
`Help
`
`FAQ Terms
`
`IEEE Peer Review
`
`|Quick Links
`
`IE5!
`
`” Search ‘“’5'
`
`
`
`A distributed restoration aigoirithm tor n'iuiitiplle=l|inll<< and
`.
`node ifailluires of transport networks
`
`Komine H. mug; ggu_ra;
`Fujitsu Lab. Ltd., Kawasaki, Japan ;
`This paper appears in: Global Telecommunications Conference, 1990, and
`Exhibition. ‘Communications: Connecting the Future‘, GILOBIECOM '90., IEEE
`
`Meeting Date: 12/02/1990 — 12/05/1990
`Publication Date: 2-5 Dec. 1990
`
`Location: San Diego, CA USA
`
`&Ma
`
`'
`
`0- Journals
`G megr:::s
`Pgoceedings
`Ostandards
`
`
`
`On page(s): 459 - 463 vo|.1
`Reference Cited: 6
`0- Join IEEE
`Inspec Accession Number: 3976310
`O"
`Abstract:
`
`O.Acc3s3th3
`IEEE Member
`Digltaltibrary
`
`Fast restoration of broadband optical fiber networks from multiple-link and node failu
`as well as single-link failures, is addressed. A distributed restoration algorithm b
`on message flooding is described. The algorithm is an extension of a previously prop
`algorithm for single-link failure. It restores the network from multiple-link and node
`failures, using multidestination flooding and path route monitoring. Computer simula
`of the algorithm verified that it can find alternate paths within 0.5 5, whenever the
`message processing delay at a node is 5 ms
`
`Index Terms:
`
`broadband networks optical links broadband optical fiber networks distributed restoration
`alg_g_ri_t_l_-m_1_ message flooding message processing delay multidestination flooding multiple-Ii
`failures node failures path route monitoring single-link failures
`transport networks
`
`Documents that cite this document
`Select link to view other documents in the database that cite this one.
`
`Search Results
`
`IPDF FULL-TEXT 364 KB
`
`PREV NEXT DOWNLOAD CITATION
`
`Home l Log-out | Journals | Conference Proceedings | S | Search by Author | Basic Search | Advanced Search | Join IEEE |Web Account | New this
`Lek | OPAC Linkin information | | Technical Su
`art | Email Alertin | No Robots Please | Release Notes | IEEE Online Publications | Help |
`FAQ| Terms | Back to Top
`
`lPR2 16-00726 -ACTIVISION EA, TAKE-1'\N
`81
`Ex.1
`2, p. 1§§§or144f éee
`8 C
`
`2K, 0 KST R,
`ch ‘6 %
`
`be
`
`C 3
`
`3660 f
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1238 of 1442
`
`

`
`_, seagclg Abstraicty
`
`'1
`
`Page 2 0f2
`
`Copyright © 2004 IEEE — All rights reserved
`
`IPR2 16-0072g- CT|V|S%0l\éE€.,
`Ex.1
`2, p.
`1
`of144
`
`ZKCIBOBKSTIER,
`
`be
`
`C e
`
`eeec f
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1239 of 1442
`
`

`
`Performance Analysis oft‘ Network Connective Probability of Multihop
`Network nndler (Correlated Breakage
`
`Shigeki Shiokawa and lwao Sasase
`
`Department of Electrical Engineering, Keio University
`
`3—l4—l Hiyoshi, Kohoku, Yokohama, 223 JAPAN
`
`Abstract—One of important properties of multihop network is the
`network connective probability which evaluate the connectivity of
`the network. The network connective probability is defined as the
`probability that when some nodes are broken, rest nodes connect
`each other. Multihop networks are classified to the regular net-
`work whose link assignment is regular and the random network
`whose link assignment is random. It has been shown that the net-
`work connective probability of regular network is larger than that
`of random network. However, all of these results is shown under
`independent node breakage. In this paper, we analyze the network
`connective probability of multihop networks under the correlated
`node breakage.
`It is shown that regular network has better per-
`formance of the network connective probability than random net-
`work under the independent breakage, on the other hand, random
`network has better performance than regular network under the
`correlated breakage.
`
`1
`
`Introduction
`
`In recent years, multi—hop networks have been widely studied
`[1]-[8]. These networks must pass messages between source and
`destination nodes via intermediate links and nodes. Examples of
`them include ting, shuffle network (SN) [l],[2] and chordal net-
`work (CN)[3]. One of the very important perfomtance measure
`of multi—hop network is the connectivity of the network. If some
`nodes are broken, it is needed for a network to guarantee the con-
`nection among non-broken nodes. Thus, the network connective
`probability defined as the probability that when some nodes are
`broken, rest links and nodes construct the connective network,
`should be a very important property to evaluate the connectivity
`of the network.
`
`Multi-hop networks are classified to regular network and ran-
`dom network according to the way of link assignment. In the regu-
`lar network, links are assigned regularly and examples of them in-
`clude shufflenet and manhattan street network. On the other hand,
`in random network, link assignment is not regular but somewhat
`random and examples of them include connective semi-random
`network (CSRN) [6]. The network connective probabilities of
`some multi—hop networks have been analyzed and it has been
`shown that the network connective probability of regular network
`is larger than that of random network. However, all of them is an-
`alyzed under the condition that locations of broken nodes are in-
`dependenteach other. In the real network. there are some case that
`the locations of broken nodes have correlation, for example. links
`and nodes are broken in the same area under the case of disaster.
`Thus, it is significant and great of interest to analyze the network
`connective probability under the condition when the locations of
`broken nodes have correlations each other.
`
`In this paper, we analyze the network connective probability
`of multi—hop network under the condition that locations of broken
`nodes have correlations each other, where we treat SN, CN and
`CSRN as the model for analysis. We realize the correlation as fol-
`lows. At first, we note one node and break it and call this node the
`center broken node. And next, we note nodes whose links con-
`nect to the center broken nodes and break them at some probabil-
`ity. We define this probability as the correlated broken probability.
`Very interesting result is shown that under independent breakage
`of node, regular network has better performance of the network
`connective probability than random network, on the other hand,
`under the correlated breakage of node, random network has better
`performance than regular network.
`In the section 2, we explain network model of SN, CN and
`CSRN which we analyze in the section 3. In the section 3, we ana-
`lyze the network connective probability under the condition when
`the location of broken nodes have correlation each other. And we
`compare each of network connective probability in the section 4.
`In the last, we conclude our study.
`
`2 Multihop network model
`
`In this section, we explain the multihop network models used
`for analysis of the network connective probability. We treat three
`networks such as SN. CN and CSRN which consists of N nodes
`and p unidirected outgoing links per node.
`Fig. I shows SN with 18 nodes and 2 outgoing links per node.
`To construct the SN, we arrange N = kph (k = l,2,---; p =
`1, 2, -
`- -) nodes in 1: columns ofp" nodes each. Moving from left
`to right, successive columns are connected by 12"“ outgoing links,
`arranged in a fixed shuffle pattern, with the last column connected
`to the first as if the entire graph were wrapped around a cylinder.
`Each of the pk nodes in a column has p outgoing links directed
`to p different nodes in the next column, Numbering the nodes in
`a column from 0 to pk — 1, nodes i has outgoing links directed
`to nodes j,j + l, ---, and j +p — 1 in the next column. where
`j =' (i mod p'°'1)p. In Fig. 1, p is equal to 2 and k is equal to 2.
`Since the link assigmnentof SN _is regular, SN is regular network.
`Fig. 2 shows CN with 16 nodes and 2 outgoing links per node.
`To construct CN, at first, we construct unidirected ring network
`with N nodes and N unidirected links. And p— 1 unidirected links
`are added from each node. Numbering nodes along ting network
`from 0 to N -— 1, nodei has outgoing links directed to nodes (i +
`l) mod N, (i + 1-,) mod N,---, and (i + 1',_,) mod N, where
`r,- (j = 1, 2,- - -_,p — 1) is defined as the chordal length. In Fig. 2,
`r 1 is equal to 3. Since r.- for everyi are independent each other, CN
`is not regular network. However, CN has much regular elements
`such a symmetrical pattern of network.
`
`0-7803-3250-4/96$5.00©1996 IEEE
`
`1581
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1240 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1240 of 1442
`
`

`
`ll
`
`O
`\
`
`.0-
`
`I
`
`.,
`
`Figure 2. Chordal network with N =‘l6. p = 2 and 1'1 = 3.
`
`Fig. 3 shows CSRN with 16 nodes and 2 outgoing links from a
`node. Similarly with CN, CSRN includes unidirected ring network
`with N nodes and N unidirected links. And we add p — 1 links
`from each node whose directed nodes are randomly selected. In
`CSRN. the number of incoming links per node is not constant, for
`example, in Fig. 3, the number of incoming links into node 1
`is
`1 and the one into node 3 is 3. The link assignment of CSRN is
`random except for the part of ring network, thus CSRN is random
`network.
`It has been shown that since the number of incoming
`links per node is not constant, the network connective probability
`of CSRN is smaller than those of SN and CN when locations of
`broken nodes are independent each other. And that of SN is the
`same as that of CN, because the network connective probability
`depends on the number of incoming links come into every nodes.
`
`3 Performance Analysis
`
`
`
`Figure 3. Connective serni-random network with N = 16 and
`p = 2.
`
`the connective network. Next, we consider the case that node 0 is
`broken. The node 0 has two outgoing links directed to nodes 1 and
`8, and if the node 0 is broken, we can not use them. Since node
`1 has only one incoming link from node 0, even if only node 0 is
`broken, rest nodes can not connect to node 1, that is, they can not
`construct the connective network. Here, we define the network
`connective probability as the probability that when some nodes
`and links are broken, the rest nodes and links can construct the
`connective network.
`Now, we explain the correlated node breakage using Fig. 3. At
`first, we note one node and break it. where this node is called as
`the center broken node. And then, we note nodes whose outgoing
`links come into the center broken node or whose incoming links
`go out of the center broken node, and break them at a probability
`defined as the correlated broken probability.
`In Fig 3, when we
`assume that the center broken node is the node 3, there are five
`nodes I , 2, 4. 9 and II which have possibility to become correlated
`broken node. And they become the broken nodes at the correlated
`broken probability. It is obvious that none of them is broken when
`the correlated broken probability is O and all of them is broken
`when the correlated broken probability is I.
`In our study, we analyze the network connective probability that
`only nodes are broken. And we assume that the number of center
`broken node is one in the analysis. We denote the correlated bro-
`ken probability by a and the network connective probability of SN,
`CN and CSRN by PSN, PCN and Peggy, respectively.
`3.1
`Shuffle Network
`
`Because the number of incoming links per node in SN is the
`constant p, when broken node is only center broken node, the rest
`nodes can construct the connective network. There are 2;: nodes
`have the possibility to become the correlated broken node. All ofp
`nodes which have outgoing link come into the center broken node
`have the outgoing links directed to the same nodes. For example,
`in Fig. I, if we assume that the node 9 is the center broken node.
`the nodes 0, 3 and 6 has outgoing links to node 9. And each of
`three nodes have two outgoing links directed to nodes 10 and ll.
`Therefore, only when all of them are broken, the rest nodes can
`not construct the connective network. On the other hand, all of
`outgoing links go out from 1; nodes which have incoming link from
`center broken node direct to different nodes. In Fig. 1, nodes 0, I
`and 2 have the incoming link from center broken node 9. And
`all of the outgoing links from their nodes direct to different nodes,
`thus even if all of them are broken, the rest nodes can construct the
`connective network. Thus, the network connective probability of
`SN is the probability that all of nodes whose outgoing links come
`
`Here, we analyze the network connective probability of SN, CN
`and CSRN under the condition that locations of broken nodes have
`correlation each other. Now, we explain the network connective
`probability in detail using Fig. 3. This figure shows the connective
`network which is defined as the network in which all nodes connect
`to every other nodes directly or indirectly. At first, we consider the
`case that the node 1 is broken. The node I has two outgoing links
`directed to nodes 2 and 3, and if the node 1 is broken, we can not
`use them. However. node 2 has two incoming links from nodes 1
`and 14, and node 3 has three incoming links from nodes 1, 2 and
`I1. Therefore. even if node I is broken, rest nodes can construct
`1582
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1241 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1241 of 1442
`
`

`
`into the center broken node are broken, and it is derived as
`
`P5-N=l—a".
`
`(1)
`
`3.2 Chordal Network
`
`The network connective probability of CN with p = 2 is differ-
`ent from that with p 2 3. At first, we consider the case withp = 2.
`When p is equal to 2, all of the outgoing links, from the nodes
`whose incoming links go out from the center broken node, direct
`to the same node. For example, in Fig. 2, when we assume that
`the center broken node is node 0, the outgoing links from it direct
`to nodes 1 and 4. And each of outgoing links from them directs to
`node 5. Therefore, only when all nodes whose incoming links go
`out from the center broken node are broken, the rest nodes can not
`construct the connective network. And we can obtain the network
`connective probability as
`
`PC,.,=1—a2
`
`forp=2.
`
`(2)
`
`And next, we consider the case that p 2 3. ln CN, when p is equal
`to or larger than three and each chordal length is selected properly,
`all of outgoing links from the nodes whose incoming links go out
`from the center broken node do not direct to the same nodes. And
`therefore, even if allof nodes which connect to the center broken
`nodes with incoming or outgoing links is broken, the rest nodes
`can construct the connective network, that is,
`
`PcN=]
`
`f0I'pZ3.
`
`3.3 Connective Semi-Random Network
`In CSRN, the number of the incoming links per node is not con-
`stant. Since the maximum number ofincoming links is N — 1 and
`one link come into a node at least, the probability that the number
`of the incoming links come into a node is i, denoted as A.-, is
`
`Ar‘: N‘2
`
`P
`
`(i_l)(N_2)
`
`0,
`i—1
`
`P
`
`(1 N_2)
`
`1v—1-t
`
`fort‘ :0
`-
`
`forz_>_1.
`
`the regular incoming link never overlap with the regular outgoing
`link, the probability to become the first case is (r — 1)/(N - 2)
`and one to become the second case is l —— (r - l)/(N — 2).
`in
`the first case, CM’, is the same as the probability that each of
`q -— 1 outgoing links among the p — l outgoing links except for
`the regular outgoing link overlap one of r — 1
`incoming links,
`denoted as C,’,_,‘q_1',_,. And in the second case, 0”’, is the
`same as the probability that each of q outgoing links among the
`p — 1 outgoing links except for the regular outgoing link overlap
`"L117"
`one ofr incoming links, denoted as C1’,
`Using C;._q,_,, given
`as follows,
`
`0,
`
`C;,:qI,.:=
`
`(pl) "I Pq):q:’z-.;;rlPyI_ql )
`
`for q’ < 0, r’ 3 0, q’ > p’,
`(p’ + r’ > N and
`ql<p'+r,—N)
`Otherwise.
`
`(5)
`
`we can derive C,,_,,_, as
`7- — 1
`_ 2)C,—l,q—l,r—l +
`
`CF17.’ =
`
`r — I
`_ N __ 2)C;la—l,q,v- '
`
`B,- can be derived as the sum of the probability that when the num-
`ber of incoming links is j — p + q, q ofp outgoing links overlap
`with one of incoming links. Therefore, we can obtain B,- as
`P
`
`B,~= Z
`=maz(0,p+l -j)
`
`A1’-p+q Cp.q.:‘ ~p+41 -
`
`(7)
`
`Here, we consider two nodes whose regular links connect to the
`center broken node. We call them regular node (R-node). And we
`define non-connective node (NC-node) as the node which have no
`incoming link. Even if a node has many incoming links, when all
`of source node of them are broken, it becomes NC-node. How-
`ever, when the number of incoming link is equal to or greater than
`2, the probability that all of source nodes of them are broken is
`very small compared with that when the number of incoming link
`is 1. Therefore, we assume the NC-node as the node which have
`only one incoming link and its source node is broken. That is,
`when the destination node of regular outgoing link of the broken
`node has only this regular incoming link and this node is not bro-
`ken, it becomes the NC-node. Fig. 4 shows the center broken node
`and R-node. (a) shows the case that none of R-node is broken, (b)
`shows the case that one of them is broken, and (c) shows the case
`that both of them are broken.
`It is found that there is only one
`node which have possibility to become the NC-node in all case.
`The probability that this node becomes the NC-node is A1. When
`the number of broken nodes is k, we can consider the three case
`with k = 1, k = 2 and k > 2. In I: = 1, this node is the center bro-
`ken node and it certainly becomes the case (a) and never becomes
`the case (b) and (c).
`in k = 2, the one node is the center broken
`node and the other is the correlated broken node and it becomes
`the cases (a) or (b). And the probability to become the case (a) is
`2/ I and to become the case (b) is l — 2/ I where I is the number of
`the nodes have possibility to become the conelated broken nodes.
`If k > 2, it becomes all the case. The number of broken nodes ex-
`cept for R-node in (a), (b) and (c) is k, k - l and k — 2, respectively.
`Furthermore, when the number of links connect to the center bro-
`ken node is 1, the probability that the number of correlated broken
`nodes is k, denoted as t”, is
`
`c,_,, = B,
`
`a'°(i — a)’-" .
`
`(8)
`
`(4)
`The nodes which have possibility to become the correlated bro-
`ken nodes are those which connect to the center broken node by
`outgoing link or incoming link. When the number of the incom-
`ing link come into the center broken node is 1', the sum of outgoing
`links and incoming links it have is p + 2'. However, the number of
`the nodes which have possibility to become the correlated broken
`nodes is not always p + 2‘, because the p outgoing links have the
`possibility to overlap with one of i incoming links. For example,
`in Fig. 3, when the center broken nodes is node 5, the outgoing link
`to node 12 overlap with the incoming link from node 12. There-
`fore, in spite of the node 5 has four outgoing and incoming links,
`the number of the nodes which have possibility to become the cor-
`related broken nodes when the node 5 is the center broken node is
`three.
`And now, we derive the probability that the number of nodes
`which have possibility to become the correlated broken nodes is j,
`denoted as B,-. Before derive B,-, we derive the probability that q
`ofp outgoing links which go out ofa node overlap with r incoming
`links come into it, denoted as GM,” Here, we define regular link
`as the link which construct the ring network and random link as
`other link. We consider the two case. The one is the case that one
`of the incoming links overlap with the regular outgoing link, and
`the other case is that none of incoming links overlap with it. Since
`1583
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1242 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1242 of 1442
`
`

`
`(a)
`
`/ regular node
`
`©74—%—©
`
`regular link
`
`(b)
`
`(c)
`
`
`
`
`
`. center broken node
`correlated broken node
`
`@ node which have posibility to
`become non-connective node
`
`Figure 4. The center broken node and regular nodes.
`
`And in this case, the probability to become the case of (a) is
`((3) 1_2Pk)/;Pk, to become the case of (b) is
`[_gPk_1V(Pk
`and to become the case of (c) is
`1_'_1P)¢_2)/(Pk. The network
`connective probability when the number of broken nodes is I, de-
`noted as E;, is derived in [8] as follows
`I-1
`
`N-N/11-3
`E(=H0 .
`Therefore, using (8) and (9). we can obtain the network connective
`probability as
`
`N—1
`
`Rcsrm = Z 31.00 - 11:)
`z=p
`
`‘
`2
`2
`N—1
`+ Ztz,n{7(1- A.>+<1— 7)(1- A.>L.}
`1:,
`
`N'-I N-I
`‘JP
`+2 2 ¢t,k{( ) 1P- k(1 --41)EIe
`k=2 l=maz(p,l:)
`I
`k
`
`‘
`I—2Plc—l
`A1)D1:—1
`(1
`[Pk
`1:
`(3) HP” ’(1 — A,)B,._.}
`11’):
`
`4 Results
`
`We show computer simulation and theoretical calculation re-
`sults of the network connective probability under the correlated
`breakage.
`Fig. 5 shows the network connective probability of SN, CN and
`CSRN with p = 2 versus the correlated broken probability. In this
`1 584
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1243 of 1442
`
`probabilityP
`networkconnective
`
`
`thoretical caluculation
`
`computer simulation
`
`SN
`0
`0 CN
`B CSRN
`
`‘0.0
`
`0.2
`
`0.4
`
`0.6
`
`0.8
`
`1.0
`
`correlated broken probability a
`
`Figure 5. The network connective probability with p = 2 versus
`correlated broken probability.
`
`1.0
`
`9-.
`>n
`.‘.:.'
`
`Z
`
`3 0.8
`N
`-DOI-
`a‘ 0.6
`0>
`'5Uu
`g
`8
`if
`fl
`§
`ea
`
`0.4
`
`0.2
`
`0
`SN
`0 CN
`0 CSRN
`
`thoretical caluculation
`
`computersimulation
`
`0.0
`
`0.2
`
`0.4
`
`0.6
`
`0.8
`
`1.0
`
`correlated broken probability a
`Figure 6. The network connective probability with p = 3 versus
`correlated broken probability.
`
`figure, the chordal length of CN, 1-, is 50. It is shown that the both
`the network connective probability of SN and CN is the same in
`p = 2. It is also shown that the network connective probability of
`CN or SN is larger than that of CSRN in small a,. however, in large
`a, the network connective probability of CN or SN is smaller than
`that of CSRN.
`Fig. 6 shows the network connective probability of SN, CN and
`CSRN with p = 3 versus the correlated broken probability.
`In
`this figure, r. is 50 and 1-3 is 120. The tendency of the network
`connective probability of SN and CSRN is the same as. the case
`with p = 2. However, the tendency of the network connective
`probability of CN is not different from that with p = 2.
`In CSRN, because the number of incoming links come into a
`node is not constant, even if p is large, there are some nodes whose
`number of incoming links is one. Therefore, the network connec-
`tive probability itself is small. However. the link assignment of
`CSRN is random, the condition of correlated breakage is not so
`different from that of independent breakage. On the other hand.
`in SN. because the number of incoming links come into a node is
`constant, the network connective probability under the indepen-
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1243 of 1442
`
`

`
`1.0
`
`in
`>x
`7;‘ 0.9
`.9at
`.9
`8 0.8
`D-
`9
`>
`
`'§ 0.7
`EO
`: 0'6
`‘5
`§ 0.5
`0.4
`
`Z
`
`l\'=384
`
`forCNandCSR
`
`N=3p"3 forSN
`
`thorclicalcaluculation
`
`computersimulatiou
`
`SN
`o
`o CN
`cl CSRN
`
`E"c
`
`:9co
`
`.°4:
`
`i'orCN and CSRN
`N=384
`N= 3 p"3 for SN
`thoretical calucularion
`
`"
`
`SN
`o
`o CN
`u CSRN
`
`computer simulation Network
`
`connectiveprobabilityP O6Euas
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`number of outgoing links p
`
`1
`
`6
`5
`4
`3
`2
`number of outgoing links p
`
`7
`
`‘igure 7. The network connective probability with a = 0.4 versus
`the number of outgoing links per node.
`
`Figure 8. The network connective probability with a = 0.8 versus
`the number of outgoing links per node.
`
`is random has good perforrrrarrce of one.
`
`Acknowledgement
`
`This work is partly supported by Ministry of Education, Kanagawa
`Academy of Science and Technology, KDD Engineering and Con-
`sulting lnc., NTT Data Communication System Co., Hitachi Ltd.
`and Mitsubishi Electric Co..
`
`References
`
`[1] M.G. Hluchyj, and MJ. Karol, “ShuffleNet: An application
`of generalized perfect shuffies to multihop lightwave net-
`works", INFOCOM '88, New Orleans,LA., Mar. 1988.
`
`[2] M.J. Karol and S. Shaikh, “A simple adaptive routing scheme
`for shufflenet multihop lightwave networks", GLOBECOM
`'88. Nov. 28, 1988—Dec. 1, 1988.
`
`[3] Bruce W. Arden and Hikyu Lee, “Analysis of Chordal Ring
`Network”, IEEE Trans. Comp.. vol. C-30, No. 4. pp. 291-
`296, Apr. 1981.
`
`[4] K. W. Doty, “New designs for dense processor interconnec-
`tion networks”, IEEE Trans. Comp.. vol. C-33, No. 5, pp.
`447-450, May. 1984.
`
`[5] H. J. Siegel, “Interconnection networks for SIMD ma-
`chines", Compur. pp. 57-65, June 1979.
`
`[6] Christopher Rose, “Mean lntemordal Distance in Regular
`and Random Multihop Networks", IEEE Trans. Commun..
`vol. 40, No.8. pp. 1310-1318, Oct. 1992.
`
`[7] J. M. Peha and F. A. Tobagi, “Analyzing the fault tolerance
`of double-loop networks”, IEEE Trans. Networking, vol. 2,
`No.4, pp. 363-373, Aug. 1994.
`
`[8] S. Shiokawa and I. Sasase, “Restricted Connective Semi-
`random Network,”, 1994 International Symposium on lnfor-
`mation Theory and its App1ications(1SITA '94), pp. 547-551,
`Sydney, Australia, November 20-711, 1994.
`
`ent breakage is large. However, because of regularity of the link
`ssignment, that under the correlated breakage is small.
`In CN,
`then 1: is two, the link assignment is regular, however, when p
`: larger than two, every chordal length is random and indepen-
`enteach other, and the link assignment is random. Moreover, the
`umber of incoming links per node of CN is the constant. There-
`)re, the network connective probability of CN is large under both
`re independent and correlated breakage.
`
`Figs. 7 and 8 show the network connective probability with
`= 0.4 and 0.8 versus p, respectively. It is shown that the larger
`is, the smaller difference of network connective probability be-
`veen SN and CSRN is, when a. is small. On the other hand, when
`is large, the larger p is, the larger difference of network con-
`ective probability between SN and CSRN is. The reason is as
`)l1ows. When a is small, the network connective probability of
`‘.SRN is small. However, the largerp is, the smaller the number of
`odes, whose number of incoming links is 1, is, and the closer to 1
`re network connectivity is. In SN and CN, even if p is small, the
`etwork connective probability is somewhat large when a is small.
`then p is large, the network connective probability of CSRN is
`[most the same with small p. On the other hand, in SN, the ten-
`ency network connectivity versus 12 is almost the same, however,
`re larger at is, the smaller the value is.
`
`As these results, CN has best performance of network connec-
`vity. However, it has been shown that CN has much poorer per-
`>rmance of intemodal distance than other network. Thus, it is
`tpecetd for the network to have good performance of both net-
`tork connective probability and intemodal distance.
`
`3 Conclusion
`
`We theoretically analyze the network connective probability
`f multihop network under the correlated damage of node. We
`‘eat shuflleNet, chordal network and connective semi-random
`etwork.
`It is found that in the independent node breakage. the
`etwork whose number of incoming links is the constant has good
`erformance of network connective probability, and found that in
`re correlated node breakage. the network whose link assignment
`
`1585
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1244 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1244 of 1442
`
`

`
`search Abstract
`
`‘
`
`I
`
`IEEE HOME I ssmcuu-:55 l snop I wee ACCOUNT I conmcrneee
`
`
`
`
`UEEE Xp/@ fi@
`
`
`
`
`
`
`
`
`
`Welcome
`United States Patent and Trademark Office
`
`Help
`
`FAQ Terms
`
`IEEE Peer Review
`
`Quick Links
`
`IV
`
`Page 1 0f2
`
`>> Search Absl
`
`Performance anaflysis of network cennective pirolbalbilliitty
`mufltihop network under coirirellaitedl breakage
`
`Shiokawa S. Sasase l.
`Dept. of Electr. Eng., Keio Univ., Yokohama, Japan;
`This paper appears in: Communications, 1996. ICC 96, Conference Record,
`Converging Technollogies for Tomorrow's Appllications. 1996 JIEIEIE llnternatio
`Conference on
`
`Meeting Date: 06/23/1996 - 06/27/1996
`Publication Date: 23-27 June 1996
`
`Location: Dallas, TX USA
`
`On page(s): 1581 - 1585 Vol.3
`Volume: 3
`Reference Cited: 8
`
`Number of Pages: 3 vol. xxxix+1848
`
`Inspec Accession Number: 5443424
`
`
`Abstract:
`One of important properties of a multihop network is the network connective probabi
`which evaluate the connectivity of the network. The network connective probability is
`defined as the probability that when some nodes are broken, the rest of the nodes
`connect each other. Multihop networks are classified as a regular network whose Ii
`assignment is regular and a random network whose link assignment is random. It ha
`been shown that the network connective probability of a regular network is larger the
`that of a random network. However, all of these results is shown under independent
`breakage. We analyze the network connective probability of multihop networks uncle
`correlated node breakage. It is shown that a regular network has a better performan
`the network connective probability than a random network under independent break.
`on the other hand, a random network has a better performance than a regular netwc
`under correlated breakage
`
`Indlex Terms:
`
`telecommunication
`random processes
`probability
`network t_qp_¢;I_ggy
`correlation methods
`network reliability
`correlated node breakage
`independent breakage
`link assignment multih
`network network connective probability
`r_\_q_de breakage
`performance
`performance anal)
`
`random network regular network
`
`Documents that cite this document
`
`
`
` O- Join IEEE
`
`O- Access the
`IEEE Member
`Diflitalllbfafl
`
`
`
`0- Journals
`&Magmnes
`O_conmm
`Proceedings
`O_standa,d6
`
`I§’,f_‘§ 1&fi§7&%g’,%%E,t£§’r£'i‘e5é:J{‘g'7E鑧’¥8Ia?s5§*c‘t1%%'§ rTa{‘c‘i:jsp?amumber=535183&k2dockey=535183@ieeecnfs&q...
`
`1/2/04
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1245 of 1442
`
`

`
`g search Abstract
`1..
`.
`Ii
`
`Page 2 of 2
`
`There are no citing documents available in lEEE Xplore at this time.
`
`
`
`Search Results LEQF FULL-TEXT 484 KB] PREV NEXT DOWNLOAD CITATION
`
`Home | Lgg_-out [Journals | Conference Proceedings | Standards | Search by Author | Basic Search | Advanceg_§e_a_r_ch | Join IEEE | Web Account | New this
`week | OPAC Linking Information | Your Feedback | Technical Suggort | Email Alerting | No Robots Please | Release Notes | IEEE Online Publications | Help |
`__FA0l ___Termsl&9|:__t.9_.I_o.rz
`
`Copyright © 2004 IEEE — All rights reserved
`
`I§’,f_‘§‘H&‘;‘?,§’/ 135$” 45?;;=?l'e5é*oTr"g7Eé‘£’¥éiifs'§c'il%B'§?é%‘%:jsp?amumbe1=535133&k2dockey=535183@ieeecnrs&q...
`
`1/2/04
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1246 of 1442
`
`

`
`On Four-Connecting a Triconnected Graphl
`(Extended Abstract)
`
`Tsan-sheng Hsu
`Department of Computer Sciences
`University of Texas at Austin
`Austin, Texas 78712-1188
`tshsu@cs.utezas. edu
`
`Abstract
`
`smallest augmentation problem.
`
`We consider the problem offinding a smallest set
`of edges whose addition four-connects a triconnected
`graph. This is a fundamental graph-theoretic problem
`that has applications in designing reliable networks.
`We present an O(noz(m, n) + 11:)
`time sequential
`algorithm for four-connecting an undirected graph G
`that is triconnected by adding the smallest number of
`edges, where n and m are the number of uertiees and
`edges in G,
`respectively, and a(m,n) is the inverse
`Aclcermann’s function.
`In deriving our algorithm, we present a new lower
`bound for the number of edges needed to four-connect
`a triconnected graph. The form of this lower bound is
`diferent from the form of the lower bound known for
`biconnectivity augmentation and triconnectiuity aug-
`mentation. Our new lower bound applies for arbitrary
`1:, and gives a tighter lower bound than the one known
`earlier for the number of edges needed to k-connect a
`(k — 1)-connected graph. For k = 4, we show that this
`lower bound is tight by giving an eflicient algorithm
`for finding a set of edges with the required size whose
`addition four-connects a triconnected graph.
`
`1
`
`Introduction
`
`The problem of augmenting a graph to reach a cer-
`tain connectivity requirement by adding edges has im-
`portant applications in network reliability [6, 14, 28]
`and fault-tolerant computing. One version of the aug-
`mentation problem is to augment the input graph to
`reach a given connectivity requirement by adding a
`smallest set of edges. We refer to this problem as the
`
`[This work was supported in part by NSF Grant CCR.-90-
`23059.
`
`Vertex-Connectivity Augmentations
`The following results are known for solving the small-
`est augmentation problem on an