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.
`One 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. ln 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.
`° Each node in the network should have a predefined
`upper limit on the number of incoming 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 rt and :1. our proposed topology can
`be defined for rt nodes with a fixed number of incoming and
`outgoing edges in the network 'lhe major advantage of our
`scheme is that. as a new node is added to the network. most
`of the existing edges ofthe logical topology are not changed,
`implying that
`the routing schemes between the existing
`nodes need little modification. 'l11e 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(Iogd ll). 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 Iogd 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 varies from I
`to d+l. We will assume that
`there is no k. such that
`
`n = J,‘ ; if n = dk for some k, our proposed topology is
`the same as given by [2]. Let k be the integer such that
`
`J‘ < n <d“' . Let Zk be the set of all (k+l)-digit strings
`
`choosing digits from Z = [Q l, 2. ...,d— ll and let any
`
`string of 2,‘ be denoted by
`
`xoxlmxk . We divide Z,‘
`
`into k+2 sets 50, SI.
`
`Sku such that all strings in Z,‘
`
`having xj as the left most occurrence ol'0 is included in S/-,
`Osjsk and all strings with no occurrence of 0 (i.e.
`
`xj¢0,
`
`Osjs k
`
`) is included in Skgl . We note that
`
`is/t-+ti = (d")kH
`
`and
`
`[sit = (d— t)’a"",
`
`0 S j S k
`
`. We define an ordering relation between every
`
`pair ofstrings in Zk .Each stringin S‘.
`
`is smaller thaneach
`
`suing in S].
`
`if i < j. For two strings 6,.G,eSl. ,
`
`0Sjsk+l. if 0,: xoxlmxk
`
`and 6._,=_\'0yl..._)'k
`
`andiis the largest integersuch that x,=ey,
`if .r,<y,
`.
`
`then cl <02
`
`Definition: For any string 6, = x0xl...xl~...xi...xk . the
`
`string 02 = x0x|...x
`
`j...
`
`x,-...xk obtained by interchanging
`
`the digits in the i"‘ and the it“ position in 0" . will be called
`the i-j-image of GI ;
`
`Clearly. if 62 is the i-j-image of 0, then 01 is the i-j-
`
`image of G2 and if x‘. = xj . 0’, and 02 represent the
`same node.
`
`We will represent each node of the interconnection
`
`topology by a distinct
`
`string xoxlmxk of 2,‘. As
`
`dk<n<d“'. all strings of Z,‘ will not be used to
`represent the nodes in G. We will use It smallest strings from
`
`Z,‘
`
`to represent the nodes of G. Suppose the largest string
`
`representing a node is in SM. We will use a node and its
`string representation interchangeably. We will use the term
`
`used string to denote a string of 2,‘ which has been already
`used to represent some node in C. All other suings of Z,‘
`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 suings
`
`473
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1363 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1363 of 1442
`
`

`
`
`
`Figure 1: Interconnection topology with d = 2. k:
`2 for n = 5 nodes.
`
`2.2 Limits on Nodal Degree
`the
`In this section. we derive the upper limits for
`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 :1.
`
`Proof: Let u be a node in the network given by
`
`xoxl ...xk e SJ. . We consider the following three cases:
`
`i) 0 <j Sk: For every v given by .rlx2...xkt for all t.
`
`osrsd-1 is an used string since ve S/-_l. There-
`
`fore the edge u —) v exists in the network. If u e S}.,j
`> 0, these are the only edges from u. Hence, u has out-
`degree :1’.
`ii) j = 0: According to our topology defined above. u
`will have an edge to xlxzmxkj whenever .r.x2....r,‘j
`
`is an used string for some j e Z. We have three sub-
`cases to consider:
`
`- If xlx._,...xkj is an used string for allj. 0 Sj< d
`then it has outdegree d.
`i
`- Otherwise. ifp of the strings xlx2...x,‘j are used
`
`strings, for some j, 0 S j < d and the 0-l-image‘ of u
`is also an used string, then u has edges to all the p
`
`nodes with used strings of the fomt xlxzmxkj and
`to the 0-] -image of u. Hence :4 has outdegree p + I.
`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 form x,x_,_...xkj are unused
`
`Sj_l are also used strings.
`of So, SI.
`Property 3: lf cl = 0x,...xk. 02 is the 0-l-image of
`
`6, and XI #0 .then 626 5,.
`
`Propert_v4: lf cl = 0xl...xk , x1:=O and O3.the0-
`
`l-image of 0| .
`
`is an unused String, then all strings of the
`
`fonn xl.r2...xkj. 0 Sj .<.d— l 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 xoxlmxk . The outgoing
`edges from node at are defined as follows:
`
`- There is an edge x°xlx2...xk -—> xlxzmxkj when«
`
`ever xlx.,....rkj is an used string. for some je Z .
`
`- There is an edge Oxlxzmxk ——> xl0x2....rk
`whenever the following conditions hold:
`
`a) x,x,...xkj is an unused string for at least one
`
`je Z and
`
`b) .r~lO....rk , the 0- l~image of u, is an used string '
`
`- There is an edge Oxlxzwouxk —-> 0x2....xkj for all
`
`j e Z whenever the following conditions hold:
`
`a) x‘ #0 and
`
`b) xl0x3....rk,
`string
`
`the 0-l-image of u,
`
`is an unused
`
`We note that if u E Sj ,j > 0. node v = XIX2-nvxkj
`
`). As an
`always exists (from property 2. since ve SI-_,
`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
`
`xoxlxzmxk ——> xl.r2...xkj. a line of dots for and a line of
`dahes
`dots
`the
`type
`and
`for
`an
`edge
`of
`
`0x|x._,...xk —> 0x3...xkj. We note thatthe edge from 010 to
`I00 satisfies the condition for both an edge of the type
`I
`xox x2...x,‘-Lrlx-_,...xkj
`
`type
`
`and an edge of
`
`the
`
`0x'x2...xk -—>.r,0.r2...x,(.
`
`474
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1364 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1364 of 1442
`
`

`
`strings (Property 4) and u has d outgoing edges to
`
`nodes ofthe form 0x2x3...xkj. 0 S j < d. Hence u
`has outdegree :1.
`
`iii) 1' = k+ I: If p of the strings xlx2...xkj are used
`
`strings. for some j. 0 S j < d. then u has outdcgree of p.
`
`We note that x|.r2...xk0 e S,‘
`
`is an used string. There-
`
`fore l S p Sci. and it has an outdcgree of at least I and
`at most :1.
`Theorem 2: In the proposed topology. each node has an
`indegree of up to d+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 t)'0y|...yk_l —))-oyl ...yk whenever
`
`tyoy, ..._\-k_, is an used string. for some (6 Z .
`There may be at most d edges of this type to v.
`
`-
`
`If y, = 0, 3-0:0 there may be an edge
`
`0yoy2..._vk -) _\-0)-I ..._\'k
`
`e
`
`lf yo = Oand (yo)-I ...yk_ I is an unused suing for
`
`some 16 Z .there is an edge
`
`Oryl ...yk_ I —)y0yl...yk. There may be at ntostd
`edges of this type to v.
`
`We have to consider 3 cases,j = 0.j = l andj >l. lfj >1.
`
`the only edges are of the type ry0yl...y,‘_ I —) y°y,...yk
`and there can be up to d such edges. lfj = l, in addition to
`
`0(d) retuning of transmitters and receivers, whereas for a
`wavelength routed network, this means redefinition of O(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 :4
`implies that we will assign the smallest unused string to the
`
`newly added node. Let the string be x0xl....rk E S].
`consider the following three cases:
`‘
`
`. We
`
`i)
`
`l<jSk: For every v given by Xlx2....Yk!,
`
`0SlSd—l. ve Sj_|. Thereforev is an used string
`and we have to add a new edge
`u —» v
`to the net-
`
`work. ‘Hie node given by we = Oxoxl ....rk_ I
`
`is guar-
`
`anteed to be an used string, since woe S0 and we
`
`have to add a new edge wo —-> u to the network. If
`
`Xk = d ‘ i, we have to delete the edge from wo to its
`0-l-image at
`this
`time. For every w given by
`lstsd-l. we$.
`and is an
`J”.
`tx0xl...xk_I.
`unused string. Therefore wo is the only predecessor of
`U.
`
`ii) j = k+l :If v = xlx2...x,_.r, 0S.ISp—l is an
`
`used string. we add a new edge
`
`u -) v
`
`to the net-
`
`work. We note that x‘x-_,...xk0 e Sk is an used string.
`Therefore. there is at least one v such that
`u —> v
`
`exists. Similarly. if w = rxox,...x,‘_ I. OSIS p - l is
`
`an used string, we add a new edge w —> u to the net-
`
`work. We note that wo = 0x0xl....rk_| 6 So is an
`used string. Therefore. there is at least one w such that
`
`the edges are of the type ry0y....yk_| —>y0yl...yk , there
`
`w ——> u exists. If xk = d — l. we delete the edge from
`
`can be only. one edge of the type Oyoy-2...yk —) yoyl ...yk.
`Thus the total number of edges cannot exceed d + I. in this
`
`case. Ifj = 0. an edge ofthe type 01yl...yk_l -—> yoyl ...yk
`exists if and only if the corresponding edge of type
`
`Iyoyl ..._v,(_ 1 —>_\-oy,...y,‘ does not exist in the network.
`Therefore. there are always exactly d 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 C
`would suffice when a new node is added to the network.
`When a multistar implementation is considered. this means
`
`W0 to its 0- I-image at this time.
`
`iii)
`
`j = 1
`
`: Let wt = Oxoxzmxk be the 0-l-image
`
`of u. Before insening u. the node Oxox-l...xk was
`
`v = 0x2...xkI. Osrsd-I
`connected to all nodes
`(case iii in our topology given in 2.1).We have to
`- delete the edge we —) v for each node
`
`v = 0x2...xkr in the network.
`
`- add an edge u—)v foreach node v = Ox:,_...xk!
`in the network.
`
`- addanewedgc w0=0x0xl...xk_l—»u
`network
`
`to the
`
`475
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1365 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1365 of 1442
`
`

`
`-
`
`lf wcat wo
`
`.add an edge wc —> u to the network.
`
`0'(S.D) denote the string x0xl...xky,y,+ly,+2...yk of
`
`- If xk = d— I .and w0=0xoO00...0 delete the
`edge from wo to its 0- l-image.
`
`
`
`Expanding a topology with d = 2, k: 2
`Figure 2:
`from (a) n = 5 to (b) n :6 nodes.
`
`Figure 2(a) shows again the network with 5 nodes given
`in Figure
`1. We choose the
`smallest unused string
`:4 = 101
`to represent the new node being insened. The
`-node u will have outgoing edges (shown by solid lines) to all
`nodes ofthe fonn Olj. to nodes Ol0 and DI I. The 0-! image
`ofu is node 0| I. Hence all edges from 0| 1 to nodes 010 and
`OH are deleted an a new edge from l0l to 011 is insened
`(shown by a dashed line). Also a new edge is insened from
`node 0l0 to lol. 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 c(S. D) is oflength 2(k+l)- l. ithas
`(k+l)-I+l substrings. each of length (k+l). Two of these
`substrings represent S and D. Since S andD are nodes in the
`network, these two substrings are used suings. 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 -> xlx2...xky,->x2...x2k_ l).’k_)‘,)‘!+ I ——>
`
`...—)xky,...yk_2yk_l—>yoyl...)-k =D
`
`(i)
`
`In other words, if all the k - 1+ 2 substrings of o'(S. D)
`are used strings. we can use o(S. 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 G(S, D)
`
`is given by (18, where a = x,.x,H...xky,y,*|...y,+i,
`
`Osisk-l— l.and
`
`3: "i+lXi+Z"‘Xk)'(yI+l"'yl+iyI+i+il' Le‘ 31” “‘°
`first unused string in (l). According to our topology. either
`
`oteSo or ae.S'k+l.
`
`Property 6: If ot e So and
`
`7 = X”l0.ri+l...xky,y,+I...)-Hi, the0-I-image of Otis
`an used string, then
`
`represents a path from S to (1 oflcngth i,
`- o(S, ot)
`-
`there exists a path
`
`‘1“’Y""5 = °*‘t+2---‘kJ’1Yi+t--->'i+i3’i+;+t
`
`- o(5, D)
`
`is a string of length k+2-I-i
`
`xoxl....rkeSj
`_voyl..._yke S,
`
`.
`
`and D be
`
`given
`
`by
`
`the
`
`string
`
`Property 7: If ote S0 and
`
`Y = xi, lOxl.+2...xky,y,+ '...y,H. the 0-I-image of a is
`
`3.1 Routing scheme
`
`an unused string, then
`
`bet I be the length of the longest suffix of the suing
`Xoxt---It
`that
`is also a prefix of y°y,..._vk and let
`
`represents a path from S to u of length i.
`- 6(S. (.1)
`-
`there exists a path
`
`476
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1366 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1366 of 1442
`
`

`
`°""5 = °‘i+2-'--"L-."r."I+I--->'r+i3’r+i+r
`
`' c(5, D)
`
`is a string oflength /(+2-I-i
`
`Properties 6 and Tfollow directly from our topology
`defined in 2.1.
`
`Property 8: If a network contains all nodes in So. 5,.
`
`. S,
`
`then
`
`-
`
`there exists an edge 5 —-> y = x,.r,...xk0 and
`
`represents a path from or to D of length
`- o(y, D)
`that cannot exceed k+l.
`Proof of Property 8: Since the network contains all
`
`j.<_ /( and must
`for some j.
`. Sk_ Y E S).
`nodes in S0, 5,.
`exist. Our topology (section 2.l) 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 suffixof x.x2....rk0 thatmatehesthe
`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 longas 2(k+l).
`
`3.2 Example of routing
`Let us consider the network of Figure 2(b). Suppose. S
`= Oll and D = O0l. Since the only outgoing edge from OH
`is
`to its 0-I-image l0l.
`the first edge in the path is
`Ol l -9 l0]
`.From l0l. we shiftin the successivedigits of
`the
`destination.
`So,
`the
`final
`path
`is
`given
`by
`S=0ll-)l0i—)0i0—)l00-)00i=Dx
`In
`this
`
`particular example. there are no nodes belonging to group
`k+ I. So, case 2 is not used.
`
`belonging to groups S... Osisk and hence are used
`strings:
`
`4. Experiments to determine the average hop
`distance
`A
`
`—) }'0_\’l .._vk.
`y —-> .r2....rk0_\-0 —> .r3...xk0_\'o —->
`number of edges in the path is /:+ 1. 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).
`liall the k - 1+ 2 substrings of o(S. D) are used strings.
`c(S, D)
`represents the shortest path from S to D and
`cannot exceed k+l. If B is the first unused string in(l), and
`
`is the preceding string then we have to consider two
`or
`cases:
`
`Case I)
`
`(15 So:
`
`In this situation we can apply
`
`is an used string.
`property 6 if 0-1-image of ct
`Otherwise we can use property 7. If we can use
`property 6. it means we need two edges to insert the
`-"l+i+l ‘
`digit
`Alternatively,
`if we
`can use
`
`property 7. it means we need one edge to insert the
`
`digit _\-,,”-H.
`
`We carried out some experiments to determine the
`
`. In each of these experiments. we
`average hop distance I-1
`have started with a given value of d, the minimum indegree
`(or outdegree) and a specified value of an integer k. The
`
`network with all‘ nodes is identical to that given in [8]. We
`
`have calculated the average hop distance I-t 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 in
`for the new network in the same way. We continued the
`
`process of adding nodes until the network contained d“ I
`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 starts 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
`
`the number of nodes in the network is J,‘ cm!“ I and. for
`these values. it is known that the network has a diameter of
`
`or e S“. : ln this situation we discard the
`Case 2)
`panial path from S to or. The first edge in our new
`be
`
`path
`
`-will
`
`5 = xoxl...x,( —->xlx2...xk0.
`
`Property 8 guarantees that once we have this
`situation, we can always start all over again
`
`ever
`without
`)'o.y,.....yk
`digits
`inserting
`encountering an unused suing and requires a
`
`477
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1367 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1367 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 tenns 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.
`
`and S.
`Jaekel
`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 # N000l4«97-
`1-0806.
`
`[ll
`
`[2]
`
`I3]
`
`[4]
`
`[5]
`
`[6]
`
`[7]
`
`[3]
`
`[9]
`
`REFERENCES
`
`lightwave
`local
`"WDM-based
`8. Mukherjee,
`networks pan ll: Multihop systems." IEEE Network.
`vol. 6. pp. 20-32, July I992.
`"Lightwave
`K. Sivarajan and R. Ramaswami.
`Networks Based on de Bruijn Graphs," IEEHACM
`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 '9], pp. lO0l-l0l I, Apr. 199].
`M. Hluchyj
`and M. Karol.
`“ShuffleNet: An
`application of generalized
`perfect
`shuffles
`to
`multihop lightwave networks." IEEHOSA Jouma! of
`Lightwave Technology, vol. 9, pp.I386-I397, Oct.
`I991.
`
`topologies for WDM
`B. Li and A. Ganz. “Virtual
`star LA.Ns: The regular structure approach." IEEE
`INFOCOM '92, pp.2l34-2143. May I992.
`N. Maxemchuk, “Routing in the Manhattan street
`network." IEEE Trans. on Commurticatiarts, vol. 35.
`pp. 503-512. May I987.
`P. Dowd. "Wavelength division multiple access
`channel hypercube processorinterconnection." IEEE
`Trans. on Computers. I992.
`J. Innes. S. Banerjee and B. Mukherjee, “GEMNET :
`A generalized shuffie exchange based regular.
`scalable and modular multihop network based on
`WDM lightwave technology",
`IEEE/ACM Trans.
`Networking. Vol 3. No 4, Aug I995.
`’
`A. Venkateswaran and A. Sengupta, “On a ‘scalable
`topology for Lightwave networks". Ptoc IEEE
`lNFOCOM'96. 1996.
`
`k and k+l respectively.
`
`Table 1: Variation of average hop distance with number of
`nodes
`
`
`
`Number of
`nodes
`
`k
`
`average hop
`5
`
`Lu
`EC-
`2
`.
`
`
`
`
`
`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. 1368 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1368 of 1442
`
`

`
`s
`
`-. search. Abstract
`
`IEEE HOME l SEARCH IEEE
`
`I SHOP I WEB ACCOUNT I CONTACT IEEE
`
`Page 1 of 2
`
`erase
`
`Membership
`
`Publications/Services
`
`Standards
`
`Conferences Careers/Jobs
`
`lEEE.;XploreC*
`
`RELEASE 1.6
`
`welcome
`United States Patent and Trademark Office
`
`» Search Absl
`
`
`
`O- What can
`I Access?
`
`O- Log-out
`
`
`
`
`
`A flexible architecture for multihop optical networks
`
`Jaekel A. Bandyogadhyay, S. Sengupta, A.
`Sch. of Comput. Sci., Windsor Univ., Ont., Canada;
`This paper appears in: Computer Communications and Networks, 1998.
`Proceedings. 7th International Conference on
`
`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 lightwave networl<
`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 ai
`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, 2
`algorithm to add nodes to the network and two routing schemes
`
`Index Terms:
`
`.
`
`telecommunice
`network topology optical fibre networks optical receivers ogtical transmitters
`network routing wavelength division multiplexing GEMNET D -algorithm flexible
`architecture
`low diameter logical topologies multihoglightwave networks multihop optical
`networks multistarimglementation network nodes
`receivers
`regulartogologies
`retuning
`routing scheme scalable logical togology transmitters
`
`Documents that cite this document
`
`There are no citing documents available in IEEE Xplore at this time.
`
`Search Results
`
`IPDF FULL-TEXT 580 KB] NEXT DOWNLOAD CITATION
`
`Tables of Contents
`
`
`
`Journals
`0 & Magazines
`O- coiil'erei_1ce
`Proceedings
`
`O- Standards
`
`O- Advanced
`
`
`Member services
`
`
`
`0 Join IEEE
`0- Establish IEEE
`Web Account
`
`O- Access the
`IEEE Member
`
`Digital Library
`
`
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`
`Exh1102, peéé69 of 1é42eee eech chb
`
`c
`
`be
`
`cc
`
`eeecf
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1369 of 1442
`
`

`
`isearch-Abstract
`
`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 Suggon | Email Alerting | No Robots Please | Release Notes | IEEE Online Publications | Help |
`FAQ| Terms | Back to Tog
`
`Copyright © 2004 IEEE — All rights reserved
`
`|PR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`E
`1102,
`70
`’‘h
`P233
`
`°“é42eee
`
`9 e
`
`ch
`
`ch b
`
`c
`
`be
`
`c e
`
`eeec f
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1370 of 1442
`
`

`
`<95////~ 07/
`
`
`
`PTO/SB/21 (O2-04)
`Approved for use through O7f31l‘2006. OMB 0651-0031
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`Reduction Act of 1995. no ersons are r uired to res nd to a collection of information unless it disla s a walid OMB control number.
`09/629 570-Conf. #5411
`My 31- 2°°°
`“ed 9- “°'*
`FORM
`
`2153
`(Io be used for all correspondence after initial filing)
`
`3 E E°e""a"
`
`
`
`
`
`TRANSMITTAL
`
`
`
`
`
`
`
`Afler Allowance communication
`to Technology Center (TC)
`
`Appeal Communication to Board of
`Appeals and interferences
`
`Appeal Communication to TC
`(Appeal Notice. Brief. Reply Brief)
`
`El Proprietary information
`
`El Status Letter
`
`E] Dravving(s)
`
`El Licensing-related Papers
`
`D Petition
`Petition to Convert to a
`Provisional Application
`Power of Attorney, Revocation
`Change of Correspondence Address
`
`
`
`1:] Affidavlts/dec'ara“°n(s)
`
`
`
`
`
`El Information Disclosure Statement El CD. Number of CD(s)
`Certified Copy of Priority
`Document(s)
`
`
`
`
`
`Firm
`PERKINS COIE LLP
`
`
`.
`.
`°'
`Chun M. Ng - 36,878
`individual name
`
`D Response to Missing Partsl
`incomplete Application
`Response to Missing Parts
`under 37 CFR 1.52 or 1.53
`
`SIGNATURE OF APPLICANT, ATTORNEY, OR AGENT
`
`1 3
`
`
`
`Date
`
`/
`
`‘
`
`
`
`I hereby certify that this correspondence is being deposited with the U.S. Postal Service as Express Mail, Airbill No. EV336668894US. in
`an envelope addressed to: MS Amendment. Commissioner for Patents. P.O. Box 1450. Alexandria, VA 22313-1450, on the date shown
`below.
`
`
`
`Dated:
`
`|
`
`|
`
`Signature:
`
`I
`
`(Melody J.Almberg)
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1371 of 1442
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Other Enc|osure(s) (please
`Identify below):
`Return Postcard
`
`
`
`
`
`
`
`lj Extension of Time Request
`
`|:| Terminal Disclaimer
`
`'1 Express Abandonment Request D Request for Refund
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1371 of 1442
`
`

`
`Docket No.: O30048002US
`
`Client Ref No. 99-481A
`
`(PATENT)
`
`
`
`I hereby certify that this correspondence is being deposited with the U.S. Postal
`
`Service as Express Mail, Airbill No. EV336668894US. in an envelope addressed
`
`to: MS Amendment, Commissioner for Patents, PO. Box 1450, Alexandria, VA
`22313-1450, nlh daleshown below.
`
`
`
`I(Melody J. Almberu)
`Signature:
`: M’
`
`
`
`
` 1' re Patent Application of:
`Fred B. Holt et al.
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`Application No.: 09/629,570
`
`Confirmation No.: 5411
`
`Filed: July 31, 2000
`
`Art Unit: 2153
`
`For:
`
`JOINING A BROADCAST CHANNEL
`
`Examiner: B. E. Edelman
`
`INFORMATION DISCLOSURE STATEMENT (IDS)
`
`MS Amendment
`
`Commissioner for Patents
`P.O. Box 1450
`
`Alexandria, VA 22313-1450
`
`Sir:
`
`Pursuant to 37 CFR 1.56, 1.97 and 1.98, the attention of the Patent and Trademark
`Office is hereby directed to the references listed on the attached PTO/SBl08.
`It
`is
`
`respectfully requested that the information be expressly considered during the prosecution
`
`of this application, and that the references be made of record therein and appear among
`
`the “References Cited” on any patent to issue therefrom.
`
`This Information Disclosure Statement is filed more than three months after the U.S.
`
`filing date, OR more than three months after the date of entry of the national stage of a
`
`PCT application, AND after the mailing date of the first Office Action on the merits,
`
`whichever occurs first, but before the mailing date of a Final Office Action or Notice of
`
`Allowance (37 CFR 1.97(c)).
`
`Copies of the references have been provided.
`
`08/11/200k SSIINDIIRII 00000010 09539570
`01 FC 1806
`180.00 OP
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1372 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1372 of 1442
`
`

`
`Application No.: 09/629,570
`
`Docket No.: O30048002US
`
`Our check in the amount of $180.00 covering the fee set forth in 37 CFR 1.17(p) is
`
`enclosed. The Director is hereby authorized to charge any deficiency in the fees filed,
`
`asserted to be filed or which should have been filed herewith (or with any paper hereafter
`
`filed in this application by this firm) to our Deposit Account No. 50-0665, under Order No.
`
`030048002US.
`
`Dated:
`
`32
`
`02
`
`Respectfully submitted,
`ey
`
`Chun M. Ng
`Registration No.: 36,878
`PERKINS COIE LLP
`
`P.O. Box 1247
`
`Seattle, Washington 98111-1247
`(206) 359-8000
`(206) 359-7198 (Fax)
`Attorneys for Applicant
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1373 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1373 of 1442
`
`

`
`PTOISBI08alb (0803)
`Approved tor use through 07f31I2006. OMB 0651-0031
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Actot 1&5, no persons are requied I: respond to a collection at information unless I oontairs a valid 0MBcantrol number.
`
`
`
`
`Substitute for form 1449A/B/PTO
`
`INFORMATION DISCLOSURE
`
`STATEMENT BY APPLICANT
`
`(Use as many sheets as necessary)
`
`
`
`
`
`Aw"caf°n~um~er
`Fmneoate
`First Named Inventor
`Mun"
`Examiner~ame
`Attorney Docket Number O30048002US
`
`
`
`
`
`Cite
`No.‘
`
`Examiner
`Initials‘
`
`Document Number
`Number-Kind code’ (ifknown)
`
`
`
`U.S. PATENT DOCUMENTS
`
`Publication Date
`MM-DD-YYYY
`
`Name of Patentee or
`Applicant of Cited Document
`
`
`
`Pages, Columns, L‘nes, \Nhere
`Relevam passages of Relevam
`figures Appear
`
`
`
`US-2002-0027896
`
`03/2002
`
`Hughes et al.
`
`US-5,058,105
`
`10/1991
`
`Mansour et a1.
`
`US-5,079,767
`
`01/1992
`
`Perlman
`
`US-5, 345,558
`
`09-06-1994 Opher
`
`US-5,511,168
`
`04-23-1996 Perlman
`
`US—5,459,725
`
`10/1995
`
`Bodner et al.
`
`US-5,568,487
`
`10-22-1996 Sitbon
`
`US-5,644,714
`
`07/1997
`
`Kikinis
`
`US-5,757,795
`
`05-26-1998 Schnell
`
`US-5, 850,592
`
`12/1998
`
`Ramanathan
`
`US-5,925,097
`
`07/1999
`
`Gopinath et al.
`
`US-5,946,316
`
`08-31-1999 Chen et al.
`
`US-5,953,318
`
`09/1999
`
`Nattkemper et al.
`
`US-5,970,232
`
`10/1999
`
`Passint et al.
`
`US-6,073,177
`
`06-06-2000 Hebel et al.
`
`US-6,115,580
`
`09/2000
`
`Chuprun et al.
`
`US-6,151,633
`
`11-21-2000 Hurst
`
`US-6, 167,432
`
`12/2000
`
`Jiang
`
`US-6,173,314
`
`01/2001
`
`Kurashima et al.
`
`US-6, 195,366
`
`02-27-2001 Kayashima
`
`US-6,252,884
`
`06-26-2001 Hunter
`
`US-6,269,080
`
`07-31-2001 Kumar
`
`US-6,272,548
`
`08/2001
`
`Cotter et al.
`
`US-6,321,270
`
`11/2001
`
`Crawley
`
`Examiner
`Signature
`
`Date
`Considered
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1374 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1374 of 1442
`
`

`
`PTO/SBI08aIb (D8-03)
`Approved for use through 07B1I2(X)6. OMB 0651-0031
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`Undesthe Paperwortmeduaion Ado! 1995, no personsarerequied brespond to a collection otintormation unlesslcontainsa valid OMBcontrol number.
` Substitute for form 1449AlB/PTO
`
`
`
`
`
`
`INFORMATION DISCLOSURE
`
`STATEMENT BY APPLICANT
`
`(Ilse as many sheets as necessary)
`
`mum
`
`Examiner Name
`
`B. E. Edelman
`
`ADI->IiCaii0n Number
`
`09/629,570-Conf. #541 ‘I
`
`Filing Date
`First Named Inventor
`
`July 31, 2000
`Fred B, Holt
`
`Art Unit
`
`21 53
`
`
`
`
`
`2-BM —
`Rm" _
`Mm —
`E~ss"°meta'- —
`Weder _
`
`
`
`
`
`Cite
`No.‘
`
`Examiner
`Initials‘
`
`
`
`
`
`
`
`————
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`P”b"°3"°"
`Forei n Patent Document
`Date
`’
`Country Code’-Number‘-Idnd Code5 (ilknown) MM.DD.YYYY
`
`
`
`Name of Patentee or
`Applicam °f Cited Documem
`
`P395. C°IUm"-5. I-hes.
`where Rebvam passages
`or Relevant Figures Appear
`
`
`
`mg
`
`‘EXAMINER: Initial if reference considered, whether or not citation is in conformance with MPEP 609. Draw line through citation if not in conformance and not
`considered.
`Include copy of this form with next communication to applicant.
`' Applicants unique cimtion designation number (optional).
`2 See Kinds Codes of
`USPTO Patent Documents at www.usgto.gov or MPEP 901.04.
`3 Enter Office that issued the document, by the two-letter code (WIPO Standard ST,3).
`‘ For
`Japanese patent do