search Abstract‘
`
`Page 1 Of 2
`
`uses HOME l SEARCH less
`
`I snow I was ACCOUNT I comncnese
`Geaeeooflélolbo
`
`
`
`if;
`
`Welcome
`United States Patent and Trademark Office
`
`» Search Absl
`
`
`
` whatcan
`O l Access?
`
`0- Log-out
`
`©n ifotuir-=coinimectiing an triconnected graph
`
`HS“ T
`Dept. of Comput. Sci., Texas Univ., Austin, TX , USA;
`This paper appears in: Foundations of Computer Science, 1992. lProceeclings.,
`Annual Symposium on
`
`Meeting Date: 10/24/1992 - 10/27/1992
`Publication Date: 24-27 Oct. 1992
`
`Location: Pittsburgh, PA USA
`
`On page(s): 70 - 79
`Reference Cited: 37
`
`Inspec Accession Number: 4488295
`
`Abstract:
`The author considers the problem of finding a smallest set of edges whose addition fu
`connects a triconnected graph. This is a fundamental graph-theoretic problem that h
`applications in designing reliable networks. He_presents an O(na(m,n)+.m) time
`sequential algorithm for four-connecting an undirected graph G that is triconnected t
`adding the smallest number of edges, where n and m are the number of vertices anc
`edges in G, respectively, and a(m, n) is the inverse Ackermann function. He presents
`new lower bound for the number of edges needed to four-connect a triconnected gra
`The form of this lower bound is different from the form of the lower bound known for
`biconnectivity augmentation and triconnectivity augmentation. The new lower bound
`applies for arbitrary k, and gives a tighter lower bound than the one known earlier fc
`number of edges needed to k-connect a (k-1)-connect graph. For k=4, he shows th
`this lower bound is tight by giving an efficient algorithm for finding a set edges with ‘
`required size whose addition four-connects a triconnected graph
`
`Index Terms:
`
`computational complexity computational geometry four-connecting_ graph theory graph-tpep
`problem inverseAckermann function
`reliable networks
`triconnected graph computational
`complexity computational geometry four-connecting graph theogy graph-theoretic problem
`inverse Ackermann function reliable networks
`triconnected graph
`
`Documents that cite this document
`
`There are no citing documents available in IEEE Xplore at this time.
`
`
`
`
`
`C)-Journa|s_
`sgivlagazlnes
`O‘ g°"‘3“:l'.‘°3
`“wee mgs
`O’ Slandafds
`
` 0 Join IEEE
`
`O- Establish IEEE
`WB13A000*1M
`O_ Accessthe
`IEEE Member
`Digit“ Library
`
`lPR2
`Ex. 1
`
`‘}£§‘,?_7/§“;+_‘;’,‘e‘§;}$, "°"".'i‘e¢'=§’t%:oT1’-‘g'§'§ze‘:?1’¥E’ri?§‘11c'?1‘%1°o'§Fé‘c'?:jsp?amumber=267s17&k2dockey=267s17@ieeecnfs&q...
`
`1/2/04
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1257 of 1442
`
`

`
`sea_rch Abstract
`
`In
`
`«
`
`Page 2 of 2
`
`
`
`
`
`PDF FULL-TEXT 776 KB]Search Results PREV NEXT DOWNLOAD CITATION
`
`flame | Log-out | Journals | Conference Proceedin s I Standards | Search b Author | I A_d;y_a__r_1g;_eg_§earg;_t1 | | | New this
`week | OPAC Linking Information | Your Feedback | Technical Suggort | Email Alerting | No Robots Please | Release Notes | IEEE Online Publications | Help |
`HQ! I«1n.1s_I B.a§.i:.i9.E9.
`
`Copyright © 2004 IEEE — All rights reserved
`
`:§’,f_‘fi 1 ‘fig’?/¥,gggglififrgé?i"e§é*oE’§'fEéaréi1fs'§=c‘f1%%'§?1T£Li:jsp?amumber=267817&k2dockey=267817@ieeecnfs&q...
`
`1/2/04
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1258 of 1442
`
`

`
`A Flexible Architecture for Multi-Hop Optical Networks‘
`
`A. Jaekel, S. Bandyopadhyay
`
`School of Computer Science,
`
`University of Windsor,
`
`Windsor, Ontario N9B 3P4, CANADA
`
`and
`
`A. Sengupta
`
`Department of Computer Science
`University of South Carolina
`Columbia, SC 29208
`
`Abstract
`It is desirable to have low diameter logical topologies
`for multihop
`lig/ttwave
`networks. Researchers have
`investigated regular topologies for such networks. Only a
`few of these (e.g., GEMNET 18]) are scalable to allow the
`addition of new nodes to an existing network. Adding new
`nodes to such networks requires a major change in routing
`scheme. For example, in a multistar implementation, a large
`number of retuning of transmitters and receiversland/or
`renumbering nodes are needed for [8]. In this paper, we
`present a scalable logical topology which is not regular but
`it has a low diameter. This topology is interesting since it
`allows the network to be expanded indefinitely and new
`nodes can be added with a relatively small change to the
`network. In this paper we have presented the new topology,
`an algorithm to add nodes to the network and two routing
`schemes.
`
`Keywords: Optical networks, multihop networks, scalable
`logical topology, low diameter networks.
`
`1. Introduction
`
`Optical networks [I] are interconnections of high-speed
`broadband fibers using lightpaths. Each lightpath provides
`traverses one or more fibers and uses one wavelength
`division multiplexed (WDM) channel per
`fiber.
`In a
`multihop network. each node has a small number of
`lightpaths to a few other nodes in the network. The physical
`topology of the network determines how the lightpaths get
`defined. For a multistar implementation of the physical
`topology, a lightpath u —> v
`is established when node u
`broadcasts to a passive optical coupler at a particular
`wavelength and the node v picks up the optical signal by
`tuning its receiver to the same wavelength. For a wavelength
`routed network, a lightpath u —) v might be established
`through one or several
`fibers interconnected by router
`nodes. The lightpath definition between the nodes in an
`optical network is usually represented by a directed graph
`(or digraph) G = (V, E) (where V is the set of nodes and E
`is the set ofthe edges) with each node of G representing a
`
`node of the network and each edge (denoted by u -9 v )
`representing a lightpath from u to v. G is usually called the
`logical topology of the network. When the lightpath u —-) v
`does not exist, the communication from a node 11 to a node v
`occurs by using a (graph-theoretic) path (denoted by
`u —->x, —>x2—>... —>xk_, —-)v)
`in G using k hops
`through the intermediate nodes
`x1, x2,
`xk_ ,
`. The
`information is buffered at intermediate nodes and, to reduce
`the communication delay, the number of hops should be
`small. If a shortest graph-theoretic path is used to establish a
`communication from u to v, the maximum hop distance is
`the diameter of G. Clearly, the lightpaths need to be defined
`such that G has a small diameter and low average hop
`distance. The indegree and outdegree of each node should be
`low to reduce the network cost. However, a reduction of the
`
`degree usually implies an increase in the diameter of the
`digraph, that is, larger communication delays. The design of
`the logical topology of a network turns out to be a difficult
`problem in view of
`these contradictory requirements.
`Several different logical topologies have been proposed in
`the literature. An excellent review of multihop networks is
`presented in [1].
`Both regular and irregular structures have been studied
`for multihop structures [2], [3], [4], [5], [6], [7]. All the
`proposed regular topologies(e.g., shuffle nets, de Bruijn
`graphs,
`t_9_ru_§_,__—jyp§_i;cQEs) enjoy the property of simple
`routing algorithms, thereby avoiding the need of complex
`routing tables. Since the diameter of a digraph with n nodes
`and maximum outdegree d is of 0(logd n), most of the
`topologies attempt to reduce the diameter to O(log,, n). One
`common property of these network topologies is the number
`of nodes in the network must be given by some well-defined
`fonnula involving network parameters. This makes the
`topology non-scalable. In short, addition of a node to an
`existing network is virtually impossible. In [8], the principle
`of shuffle interconnection between nodes in a shufflenet [4]
`is generalized (the generalized version can have any number
`of nodes in each column) to obtain a scalable network
`topology called GEMNET. A similar idea of generalizing
`
`0-8186-9014-3/98 $10.00 © 1998 IEEE
`
`472
`
`/
`
`/
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1259 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1259 of 1442
`
`

`
`the Kautz graph has been studied in [9] showing a better
`diameter and network throughput
`than GEMNET.' Both
`these scalable topologies are given by regular digraphs.
`Qne topology that has been studied for optical networks
`is the bidirectional ring network. In such networks. each
`node has
`two incoming lightpaths and two outgoing
`lightpaths. In tenns of the graph model. each node has one
`outgoing edge to and one incoming edge from the preceding
`and the following node in the network. Adding a new node
`to such a ring network involves redefining a fixed number of
`edges and can be repeated indefinitely.
`Our motivation was to develop a topology which has
`the advantages of a ring network with respect to scalability
`and the advantages of a regular topology with respect to low
`diameter. In other words. our topology has to satisfy the
`following characteristics:
`° The diameter should be small
`
`° The routing strategy should be simple
`°
`It should be possible to add new nodes to the net-
`work indefinitely with the least possible perturbation of
`the network.
`4
`' Each node in the network should have a predefined
`upper limit on the number ofincoming and outgoing
`edges.
`'
`In this paper we introduce a new scalable topology for
`multihop networks where the graph is not.
`in general.
`regular. Given integers n and d. our proposed topology can
`be defined for n nodes with a fixed number ofincoming and
`outgoing edges in the network The major advantage of our
`scheme is that, as a new node is added to the network. most
`of the existing edges of the logical topology are not changed.
`implying that
`the routing schemes between the existing
`nodes need little modification. The edges to and from the
`new added node can be implemented by defining new
`lightpaths which is small
`in number, namely. 0(d). For
`multistar
`implementation.
`for example.
`this
`can
`be
`accomplished by retuning 0(d) transmitters and receivers.
`The paper is organized as follows. In section 2. we
`describe the proposed topology and derive its pertinent
`properties. Section 3 presents two routing schemes for the
`proposed topology and establishes that
`the diameter is
`0(log,, n). Our experiments in section 4 show that. for a
`network with n nodes and having an indegree of at most d+ l .
`an outdegree of d and the average hop distance is
`approximately logd n. We have concluded with a critical
`summary in section 4.
`
`2. Scalable topology for multihop networks
`
`2.1 Proposed interconnection topology
`
`Given two integers n and d. dsn . we define the
`interconnection topology of the network as a digraph G in
`the following. As mentioned earlier.
`the digraph is not
`
`regular - the indegree and outdegree of a node vanes from I
`to d+l. We will assume that
`there is no k. such that
`
`rt = :1,‘ ;if It = dk for some k, our proposed topology is
`the same as given by [2]. Let k be the integer such that
`
`d‘
`
`n <dk+' . Let Z,‘ be the set of all (k+I)-digit strings
`
`choosing digits from Z = {Ql,2. ....d— l} and let any
`
`string of 2,‘ be denoted by
`
`xoxlmxk . We divide Zk
`
`into k+2 sets S0, S1.
`
`Sk+,
`
`such that all strings in Zk
`
`having xj as the left most occurrence of0 is included in S}.
`0SjSk and all strings with no occurrence of 0 (i.e.
`
`xi-$0. Osjsk )isincludedin Sk+|.Wenotethat
`k
`.
`_ .
`“d
`lst-+rl =(d") H
`ISJI =(""')j‘1k 1'
`0 S j S k
`. We define an ordering relation between every
`
`pair ofstrings in Zk .Each string in Si
`
`is smallerthan each
`
`string in Sj
`
`if i < j. For
`
`two strings 6,.63eS)-.
`
`0sj.<_k+I. if 6.: x0x,...xk
`
`and 62=)'0y|...)‘k
`
`andris the largest integersuch that xlatyl
`if x,<y, .
`
`then 0'l<0'2
`
`Definition: For any string 0, = x0x,...x‘-...xj...xk. the
`
`I
`string 62 = xoxl...x....x‘....xk obtained by interchanging
`
`the digits in the i"' and the fl‘ position in 0.. will be called
`
`the i-j-image of 6| .
`
`Clearly. if 0'2 is the i-j-image of 0, then 01 is the i-j-
`
`image of 0'2 and if xi = xi , O’. and 02 represent the
`same node.
`
`We will represent each node of the interconnection
`
`topology by a distinct string x0x|...xk of Zk. As
`
`. all suings of 2,‘ will not be used to
`d,‘ < n < :1“ I
`represent the nodes in G. We will use n smallest strings from
`Z,‘
`to represent the nodes of G. Suppose the largest string
`
`representing a node is in SM. We will use :1 node and its
`string representation interchangeably. We will use the term
`
`used string to denote a string of Z,‘ which has been already
`used to represent some node in G. All other strings of Zk
`will be called unused strings.
`Property 1: all strings of So are used strings.
`
`Property 2: if 0 e S’.
`
`is an used string. then all strings
`
`473
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex.1102, p. 1260 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1260 of 1442
`
`

`
`SJ-_1 are also used strings.
`of S0, S1,
`Property 3: If 6, = Ox, ...xk, 02 is the 0-l-image of
`
`o,_ and x,¢o .then 026 s',..
`
`Property 4: If 0'1 = 0xl...xk , x, #0 and oz.the0-
`
`1_-image of cl . is an unused string, then all strings of the
`
`form x,x2.._.xkj . 0 Sj Sd — I are unused strings.
`The proofs for Properties 1
`- 4 are trivial and are
`omitted.
`We now define the edge set of the digraph G. Let any
`
`node u in G be represented by xoxl ...xk . The outgoing
`edges from node u are defined as follows:
`
`- There is an edge xoxlxzmx,‘ —> xlxzmxkj when-
`
`ever xlx._,...xkj is an used string, for some je Z,
`
`0xlx2...xk—>xl0x2....r,‘
`- There is an edge
`whenever the following conditions hold:
`
`a) x1x2...xkj
`
`is an unused string for at least one
`
`je Z and
`
`b) .r-l0....\'k . the 0-l-image of u, is an used string
`
`- There is an edge Oxlx-_,...xk —) Ox2...xkj forall
`
`j e Z whenever the following conditions hold:
`
`a) x] #0 and
`
`b) x,0x3....tk, the 0-l-image of u.
`string
`
`is an unused
`
`We note that if use 5/. ,j > 0, node v = x|x3...x,‘j
`
`). As an
`always exists (from property 2, since v e SI-_l
`example. we show a network with 5 nodes for d: 2, k = 2 in
`figure 1. We have used a solid line for an edge of the type
`
`xoxlx2...xk —> x]x._,...xkj. alline of dots for and a line of
`the
`for
`an
`dashes
`and
`dots
`of
`edge
`type
`
`0x|x2...xk —> 0x3...xkj. We note that the edge from 010 to
`100 satisfies the condition for both an edge of the type
`
`xo.;lx2...xkg>.r|x2...xkj
`
`and an
`
`edge of
`
`the
`
`type
`
`0x.x2...xk —->x,0.r2...xk.
`
`
`
`Figure 1: Interconnection topology with d = 2, k:
`2 for n = 5 nodes.
`'
`
`2.2 Limits on Nodal Degree
`
`In this section, we derive the upper limits for the
`indegree and the outdegree of each node in the network. We
`will show that, by not enforcing the regularity, we can easily
`achieve scalability. As we add new nodes to the network.
`minor modifications of the edges in the logical topology
`suffice. in contrast to large number of changes in the edge-
`set as required by other proposed methods.
`Theorem 1: In the proposed topology. each node has an
`outdegree of up to d.
`
`Proof: Let u be a node ‘in the network given by
`
`xoxl ...xk e SJ. . We consider the following three cases:
`
`i) 0<jSk: For every v given by xlx2...xkr for all t.
`
`0SISd— 1 is an used string since ve Sj_ I. There-
`
`fore the edge u -) v exists in the network. If u e Sjflj
`> 0, these are the only edges from u. Hence. u has out-
`degree d.
`ii) j = 0: According to our topology defined above. u
`
`will have an edge to xlx2...xkj whenever xIx2...xkj
`
`is an used string for some je Z. We have three sub-
`casesto consider:
`'
`
`- If x,x2...xkj is an used stringfor allj, 0 Sj<d
`then it has outdegree d.
`
`- Otherwise. ifp of the strings xlxl-noxkj are used
`
`strings, for some j, 0 S j < d and the 0-l-image of u
`is also an used string, then it has edges to all the p
`
`nodes with used strings of the form xlxz ...x,‘j and
`to the 0-1-image of u. Hence u has outdegree p + 1.
`Here u has an outdegree of at least I and at most d.
`- Otherwise, if the 0-l-image of u is an unused string,
`
`then all strings of the fonn x.x2...xkj are unused’
`
`474
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1261 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1261 of 1442
`
`

`
`strings (Property 4) and u has d outgoing edges to
`
`nodes ofthe fomt Ox2x3...xkj . O Sj< (1. Hence u
`has outdegree (1.
`
`iii) j = k + I: If p of the strings .\'lX2...Xkj are used
`
`strings. for some j. 0 S j < d. then it has outdegree ofp.
`
`We note that xlx2...xk0 e S,‘ is an used string. There-
`
`fore l S p S d. and it has an outdegree of at least I and
`at most (1.
`
`Theorem 2: In the proposed topology. each node has an
`indegree of up to 11+ l.
`
`Proof: Let us consider the indegree of any node v given
`
`by yoyl ...yk e S). As described in 2.1, there may be three
`type of edges to node v as follows:
`
`- An edge !yo)'l...yk_ I ->y0y,...yk whenever
`
`ryoy, ...,vk_ , is an used string. for some t e Z .
`There may be at most d edges of this type to v.
`
`- If y, = 0. yoatfl there may be an edge
`
`0yo)'2..._vk —) y0y,..._vk
`
`- If yo = 0 and ryoy1...yk_l is an unused string for
`
`some
`
`re Z . there is an edge
`
`Otyl ...yk_l —> yoyl ...yk.There may be at most d
`edges of this type to v.
`
`0(d) retuning of transmitters and receivers, whereas for a
`wavelength routed network, this means redefinition of 0(d)
`lightpaths. In contrast. for other proposed topologies [8], [9]
`the number of edge modifications needed was 0(nd). As
`discussed in the previous section. the nodes are assigned the
`smallest strings defined earlier. Addition of a new node it
`implies that we will assign the smallest unused string to the
`
`newly added node. Let the string be xoxlmxk 6 SI.
`consider the following three cases:
`
`. We
`
`i)
`
`I <jSk : For every v given by x,x_,_...xkt,
`
`0StSd- I. ve Sj_l. Therefore v is an used string
`and we have to add a new edge
`u —> v
`to the net-
`
`work. The node given by wo = Oxoxl ....r‘. _ I
`
`is guar-
`
`anteed to be an used string. since woe S0 and we
`
`have to add a new edge wo —-3 u 4 to the network. If
`
`xi; = d‘ 1. we have to delete the edge from wo to its
`0-l-image at
`this
`time. For
`every‘ w given by
`weS-
`and is an
`J“
`lStSd—l.
`!x0xl...xk_|.
`unused string. Therefore we is the only predecessor of
`ll.
`
`ii) j = k+l :If v = xlx2...x,_,r. 0StSp—l is an
`
`used string, we add a new edge
`
`u -> v
`
`to the net-
`
`work. We note that xlx2...xk0 6 3k is an used string.
`Therefore,
`there is at least one v such that
`u —» v
`
`exists. Similarly, if w = rxox, ....rk_ I. OS I S p - l is
`
`We have to consider 3 cases,j = 0.} = l andj >l. Ifj >1,
`
`an used string. we add a new edge w —> u to the net-
`
`the only edges are of the type ty0yl...yk_l —-> y0y,...yk
`and there can be up to d such edges. lfj = l, in addition to
`
`work. We note that wo = 0x0xl....rk_ I re So is an
`used string. Therefore. there is at least one w such that
`
`the edges are ofthe type ty°yl...yk_ I —-) yoylmyk , there
`
`w -) u exists. If xk = d - l. we delete the edge from
`
`can be only one edge of the type Oyoyzmyk -> yoyl ...yk.
`Thus thetotal number of edges cannot exceed d + l. in this
`
`case. Ifj = 0. an edge ofthe type Otyl...yk_| —) yoyl ...yk
`exists
`if and only if the corresponding edge of type
`
`t_yoy]...yk_l -->_\'0y'...yk does not exist in the network.
`Therefore. there are always exactly (1 incoming edges to v in
`this case.
`
`2.3 Node Addition to an Existing Network
`
`In this section we consider the changes in the logical
`topology that should occur when a new node is added to the
`network. We show that at most 0(d) edge changes in G
`would sufficc when a new node is added to the network.
`When a multistar implementation is considered, this means
`
`we to its 0- 1-image at this time.
`
`iii)
`
`j = l
`
`: Let wt = 0x0x2...xk be the 0-1-image
`
`of u. Before insening u, the node
`
`0xox—_,...xk was
`
`connected to all nodes v = 0x2...x‘.!. 0StSd— l
`(case iii in our topology given in 2.l).We have to
`- delete the edge wt —-) v for each node
`
`v = 0x2...x,‘r in the network.
`
`- add an edge u—>v
`in the network.
`
`foreach node v = 0x2...xkt
`
`~ add a new edge
`network
`
`wo = 0xox,...xk_, —vu
`
`to the
`
`475
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1262 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1262 of 1442
`
`

`
`-
`
`lf wcstwo .add an edge wC -) u to the network.
`
`0’(S,D) denote the string x0x[...xkyly,+lyH_2...yk of
`
`' lfxk =
`
`d — 1 . and wo at 0xo000...0 delete the
`
`edge from we to its 0-l-image.
`
`
`
`Figure 2: Expanding a topology with d: 2, k: 2
`from (a) n = 5 to (b) n :6 nodes.
`
`Figure 2(a) shows again the network with 5 nodes given
`in Figure
`l. We choose the smallest unused string
`u = 101
`to represent the new node being inserted. The
`node u will have outgoing edges (shown by solid lines) to all
`nodes of the form Olj, to nodes 010 and 0| l. The 0-! image
`ofu is node 01 1. Hence all edges from OH to nodes 010 and
`011 are deleted an a new edge from l0l to 011 is inserted
`(shown by a dashed line). Also a new edge is inserted from
`node 0lO to 101. The final network is shown in Figure 2(b)
`
`3. Routing strategy
`
`In this section, we present two routing schemes in the
`proposed topology from any source node S to any
`destination node D. Let S be_given by the
`string
`
`length 2(k+ l)-I. Since 0(S. D) is oflength 2(k+ l) - I, it has
`(k+l)-[+1 substrings, each of length (k+l). Two of these
`substrings represent S and D. Since S and D are nodes in the
`network, these two substrings are used strings. If all the
`remaining k-I substrings of o'(S, D) having length k+l are
`also used strings. then a routing path from S to D of length
`k+ l-I exists as given by the sequence of nodes given in (l)
`below.
`
`5= xoxlmxk —->x1x2...xky,-)x2...x2k_IxkylyhI -->
`
`...—)xk_v,...yk_2yk_l—>y0yl...yk =D
`
`(1)
`
`In other words, if all thek - 1+ 2 substrings of o(S. D)
`are used strings. we can use 0'($. D) to represent the path
`from S toD in (1).
`
`Property 5: If all the k - I + 2 substrings of o(S. D) are
`used strings, o(S, D) represents the shortest path from S to
`D.
`
`However. if some of the substrings of o(S, D) are not
`used strings. then some of the corresponding nodes do not
`currently appear in the network and hence this path does not
`
`exist. We note that any two consecutive strings in o(S, D)
`
`is given by (113. where ct =
`
`Xt'xi+ l"'xIc)'l)'l+ 1 --->’t+iv
`
`osisk—1—I.and
`
`5‘ -‘:+ix.'+2---"t>'t>’1+|---3’1+t>’I+i+t- Le‘ Bbe ‘h°
`first unused string in (1). According to our topology. either
`
`oteso or aeS,H,.
`
`Property 6: If (1 e 50 and
`
`Y = X‘-+ .0.ri+2...xky,y,+l...y,+i, the 0-l-image of ct is
`an used string. then
`
`represents a path from S to 0! of length i.
`- 6(S, 0!)
`-
`there exists a path
`
`°‘“"Y”5= 0xi+2"'xkylyl+l"'y!+iyl+i+l
`
`- o(5, D)
`
`is a string of length k+2-I-i
`
`x°x,....rkeSj
`y0y,...yke S,
`
`and D be
`
`given
`
`by
`
`the
`
`string
`
`Property 7: If
`
`(1 e 30 and
`
`3.1 Routing scheme
`
`Let I be the length of the longest suffix of the string
`
`‘ox:----Vt
`
`that
`
`is also a prefix of _\'oyl..._v,‘
`
`and let
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1263 of 1442
`
`Y = X.-+ ‘Ox,-+2...xky,y,+l...y,H the O-I-image of a is
`
`an unused string. then
`
`represents a path from S to 0: of length i,
`- o(S. ot)
`-
`there exists a path
`
`476
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1263 of 1442
`
`

`
`°‘'‘’5 = °"i+2----"t—“I-"I+1--'Yi+i3’1+i+i
`
`- o(8, D)
`
`is a string of length k+2—l-i
`
`Properties 6 and 7‘ follow directly from our topology
`defined in 2.l.
`
`Property 8: lfa network contains all nodes in So. 5|,
`
`,5,‘
`
`then
`
`-
`
`there exists an edge S —-) ‘y = x,x2...xk0 and
`
`represents a path from (1 to D of length
`° 0(y, D)
`that cannot exceed k+l. 4
`
`Proof of Property 8: Since the network contains all
`
`for some j. jsk and must
`.Sk' Y e S].
`nodes in S0. 5,.
`exist. Our topology (section 2.1) ensures that
`the edge
`
`5 —-) 7 exists. The path given below consists only strings
`
`maximum of k+l edges.This represents the worst
`case since there may exist a shorter path by finding
`
`the longest suffix of xlx2...xk0 that matches the
`corresponding prefix of D. In this case the path
`cannot exceed k + 2.
`Case I can appear repeatedly. The worst situation is
`when we have to apply it to insert every digit of D. In other’
`words, the path in this case can be as long as 2(k+I).
`
`3.2 Example of routing
`
`Let us consider the network of Figure 2(b). Suppose, S
`= Oll and D = 001. Since the only outgoing edge from Oil
`is to its 0-I-image IOI.
`the first edge in the path is
`0ll ---> 101
`.From 101. we shiftin the successive digits of
`the
`destination.
`So,
`the
`final
`path
`is
`given
`by
`In
`S=0lI—->l0l—)0l0——)I00-—)00l =D.
`this
`
`particular example. there are no nodes belonging to group
`k+l. So, case 2 is not used.
`
`belonging to groups Si. Osisk and hence are used
`strings:
`
`4. Experiments to determine the average hop
`distance
`
`—>y0_vl ...yk.
`Y —> x2...xk0_\'0 —-> x3...xk0_\'0-—)
`number of edges in the path is k+ I. hence the proof.
`
`The
`
`Theorem 3:The diameter of a network using the
`proposed topology cannot exceed 2(k+ I ).
`Proof: We consider any source-destination pair (S, D).
`If all the k - l + 2 substrings of 6(S. D) are used strings,
`0(S,D) represents the shortest path from S to D and
`cannot exceed k+l. If B is the first unused string in (1), and
`a is the preceding string then we have to consider two
`cases:
`
`Case l)
`
`(16 So :
`
`In this situation we can apply
`
`is an used string.
`property 6 if O-l—image of ot
`Otherwise we can use property 7. If we can use
`propeny 6. it means we need two edges to insert the
`
`if we can use
`digit _v,H.H . Alternatively,
`propeny 7. it means we need one edge to insert the
`
`digit _\',H.+l.
`
`: In this situation we discard the
`ct e 5,”,
`Case 2)
`partial path from S to a. The first edge in our new
`be
`
`path
`‘will
`5 = x0x1...xk-—)x‘x2...xk0.
`Propeny 8 guarantees that once we have this
`situation. we can always start all over again
`
`ever
`without
`y0.y,.....yk
`digits
`inserting
`encountering an unused string and requires a
`
`477
`
`We carried out some experiments to determine the
`avera e ho distance In . In each of these ex
`riments, we
`8
`P
`P9
`have started with a given value of d. the minimum indegree
`(or outdegree) and a specified value of an integer k. The
`
`network with :1,‘ nodes is identical to that given in [8]. We
`
`have calculated the average hop distance 5 of this network
`from the hop distances of every source/destinations pairs
`using the routing scheme described in the previous section.
`Then we have added a node to the network and calculated 7:
`for the new network in the same way. We continued the
`
`process of adding nodes until the network contained dt + '
`nodes. The results of the experiments are shown in Table l
`and reveal the following:
`° The average hop distance is approximately k+l.
`° The average hop distance stans at approximately k
`and increases to approximately k+l as we start add-
`ing nodes to the network.
`We interpret these results as follows. Even though the
`diameter is 2(k+l). the number of lightpaths through paths
`involving 0-! images. which increase the number of hops. is
`relatively small. Our network is identical to that in [2] when
`.
`.
`I
`and. for
`the number of nodes in the network IS d* or J‘ +
`these values. it is known that the network has a diameter of
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1264 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1264 of 1442
`
`

`
`approach is the fact that we can very easily add new nodes
`to the network. This means that the perturbation of the
`network in terms of redefining edges in the network is very
`small in our architecture. The routing scheme in our network
`is very simple and avoids the use'of routing tables.
`
`Jaekel and S.
`Acknowledgments: The work of A.
`Bandyopadhyay has been supported by research grants from
`the Natural Science and Engineering Research Council of
`Canada. The work of A. Sengupta has been partially
`supported by Office of Naval Research grant # NO00l4-97-
`I-0806.
`
`[ll
`
`[2]
`
`[3]
`
`[4]
`
`[5]
`
`[6]
`
`[7]
`
`[8]
`
`[9]
`
`REFERENCES
`
`lightwave
`local
`"WDM—based
`B. Mukherjee,
`networks part II: Multihop systems." IEEE Network,
`vol. 6, pp. 20-32, July 1992.
`“Lightwave
`K. Sivarajan and R. Ramaswami,
`Networks Based on de Bmijn Graphs," IEEDACM
`Transactions on Networking, Vol. 2, No. I, pp. 70-
`79, Feb I994.
`“Multihop
`and R. Ramaswami,
`K. Sivarajan
`Networks Based on de Bruijn Graphs."
`IEEE
`INFOCOM ‘9l, pp. l0Ol-l0ll, Apr. 199].
`M. Hluchyj
`and M. Karol,
`“ShuffleNet: An
`application of generalized perfect
`shuffles
`to
`multihop lightwave networks." IEEE/OSA Jounial of
`Lightwave Technology, vol. 9, pp.l386-I397. Oct.
`1991.
`
`B. Li and A. Ganz, “Virtual topologies for WDM
`star LANSZ The regular structure approach." IEEE
`INFOCOM ‘92, pp.2134-2143, May I992.
`N. Maxemchuk, “Routing in the Manhattan street
`network." IEEE Trans. on Communications, vol. 35.
`pp. 503-512, May 1987.
`P. Dowd, “Wavelength division multiple access
`channel hypercube processor interconnection," IEEE
`Trans. on Computers. 1992.
`J. Innes. S. Banerjee and B. Mukherjee. “GEMNET :
`A generalized shuffle exchange based regular.
`scalable and modular multihop network based on
`WDM lightwave technology”,
`[EEE/ACM Trans.
`Networking,Vol 3, No 4, Aug I995.
`'
`A. Venkateswaran and A. Sengupta, “On a scalable
`topology for Lightwave networks", Proc IEEE
`INFOCOM’96, 1996.
`
`k and k+l respectively.
`
`Table 1: Variation of average hop distance with number of
`nodes
`
`.
`
`
`
`Nume7W T
`nodes
`
`k
`
`average ho
`I-I
`V
`
`
`
`ll
`..
`5 --
`
`1
`
`
`
`
`
`
`
`
`
`
`
`
`Ix.)
`
`Ix)
`
`I0
`. R
`
`
`
`5. Conclusions
`
`In this paper we have introduced a new graph as a
`logical network for multihop networks. We have shown that
`our network has an attractive average hop distance
`compared to existing networks. The main advantage of our
`
`478
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1265 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1265 of 1442
`
`

`
`.search. Abstract
`
`Page 1 0f2
`
`uses HOME l SEARCH use:
`
`I SHOP l was ACCOUNT I contact uses
`
`welcome
`United States Patent and Trademark Office
`
`E V}
`
`» Search Absl
`
`Search Results
`
`PDF FULL-TEXT 580 KB] NEXT DOWNLOAD CITATION
`
`
`
`
`
`
`
`A flexible architecture for multihop optical networks
`O-Journals
`
` 8‘ M"9a""°" Jaekel A. Bandyogadhyay, s. Sengugta, A.
`O‘ °°"Ier9'.‘°9
`Sch. of Comput. Sci., Windsor Univ., Ont., Canada;
`Pmceedmgs
`This paper appears in: Computer Communications and Networks, 1.998.
`O‘ Standams
`Proceedings. 7th International Conference on
`
`0- By Author
`G Basic
`O- Advanced
`
`
`
`0- Join IEEE
`0- Establish IEEE
`We” A°°°“m
`O_AGcess the
`IEEE Member
`mgitambm-y
`
`Meeting Date: 10/12/1998 - 10/15/1998
`Publication Date: 12-15 Oct. 1998
`
`Location: Lafayette, LA USA
`
`On page(s): 472 - 478
`Reference Cited: 9
`
`Number of Pages: xxii+929
`Inspec Accession Number: 6226042
`
`Abstract:
`It is desirable to have low diameter logical topologies for multihop Iightwave network
`Researchers have investigated regular topologies for such networks. Only a few of th
`(e.g., GEMNET) are scalable to allow the addition of new nodes to an existing netwo
`Adding new nodes to such networks requires a major change in routing scheme.
`example, in a multistar implementation a large number of retuning of transmitters an
`receivers anti/or renumbering nodes are needed for GEMNET. We present a scalable
`logical topology which is not regular but it has a low diameter. This topology is
`interesting since it allows the network to be expanded indefinitely and new nodes can
`added with a relatively small change to the network. We present the new topology, 5
`algorithm to add nodes to the network and two routing schemes
`
`Indlex Terms:
`
`telecommunice
`network topology optical fibre networks optical receivers optical transmitters
`network routing wavelength division multiplexing GEMNET WDM algorithm flexible
`architecture
`low diameter logical topologies multihoglightwave networks multihop optical
`
`receivers
`networks multistarimglementation network nodes
`routing scheme scalable logical topology transmitters
`
`regulartopologies
`
`retuning
`
`-
`Documents that cite this document
`There are no citing documents available in IEEE Xplore at this time.
`
`Search Results
`
`[PDF FULL-TEXT 580 KB] NEXT DOWNLOAD CITATION
`
`IPR2 16-0072 -ACTIVISION Eék, T%KEé'|'\Nq12Kt%OBKST%R,
`Ex.1
`2, p.
`1 §§or144§ e
`C
`
`be
`
`C e
`
`eeec f
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1266 of 1442
`
`

`
`.searc_h.Abstract
`-1)
`
`Page 2 of 2
`
`
`
`Home | Log-out | Journals | Conference Proceedings | Standards | Search by Author | Basic Search | Advanced Search | 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 |
`FAQ| Terms | Back to Top
`
`Copyright © 2004 IEEE — All rights reserved
`
`lPR2 16-00726 -ACTIVISION EA, TAKE-
`éee
`Ex.1
`2, p. 1‘E§?or144§
`g e
`
`2K 0 KST R,
`t:'B is
`Q:
`
`<31
`
`be
`
`C e
`
`3930 f
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO,