(12) United States Patent
`Steele, Jr. et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,603,742 B1
`Aug. 5, 2003
`
`US006603742B1
`
`(54) NETWORK RECONFIGURATION
`
`(75) Inventors: Guy L. Steele, Jr., Lexington, MA
`(US); Steven K. Heller, Chelmsford,
`MA (US); Daniel Cassiday, Tops?eld,
`MA (US)_ Jon Wade Wellesley MA
`’
`’
`’
`
`(US)
`
`_
`_
`(73) Ass1gnee: SllIl MICI‘OSYSIZEIIIS, IIlC., Santa Clara,
`CA(US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/323,962
`_
`JllIl- 2, 1999
`(22) Flledi
`(51) Int. c1.7 .............................................. .. H04L 12/28
`
`U-S- Cl- ...................................... ..
`(58) Field of Search ............................... .. 370/351, 242,
`370/408, 402, 400, 254; 709/238, 293,
`242, 246, 258
`
`(56)
`
`References Cited
`
`6,005,860 A 12/1999 Anderson et 81.
`6,031,835 A
`2/2000 Abali et a1.
`6,055,618 A
`4/2000 Tllofson
`6,064,671 A
`5/2000 K4111“
`6,097,718 A
`8/2000 B10“
`6,137,781 A 10/2000 Goto et a1.
`6,230,252 B1
`5/2001 Passint et al.
`6,243,760 B1
`6/2001 Armbruster et a1.
`6,256,295 B1
`7/2001 Callon
`6,295,573 B1
`9/2001 Bailey et aL
`6,437,804 B1
`8/2002 Ibe et a1.
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`1/ 1998
`817097 A2
`OTHER PUBLICATIONS
`_
`_
`_
`Whay C. Lee, “Topology Aggregation for Hierarchical
`Routing in ATM Networks.” Apr. 1, 1995, pp. 82—92,
`Computer_c0mmunlcanon Revlew'
`
`Continued on next page)
`
`Primary Examiner—Wellington Chin
`Assistant Examiner—Brenda Pham
`(74) Attorney, Agent, or Firm—Finnegan, Henderson,
`Farabow, Garrett & Dunner, L.L.P.
`
`U.S. PATENT DOCUMENTS
`
`(57)
`
`ABSTRACT
`
`7/1992 Li
`57128932 A
`9/1995 Seth“ et a1‘
`5353978 A
`2/1997 Annapareddy et a1‘
`5’6O2’839 A
`5,680,116 A 10/1997 Hashimoto et 81.
`5,721,819 A
`2/1998 Galles et a1‘
`5,740,346 A
`4/1998 Wicki et aL
`5,751,710 A * 5/1998 Crowther et a1_ _________ __ 370/423
`5,751,967 A
`5/1998 Raab et 81.
`5,768,501 A
`6/1998 Lewis
`5,781,546 A
`7/1998 Sethll
`57812549 A
`9/ 1998 Seth“
`2
`lé‘f’?m et a1‘
`5,884,047 A
`3/1999 Aikawa et a1‘
`5,914,953 A
`6/1999 Krause et 81.
`5,970,232 A * 10/1999 Passint et a1. ....... .. 395/20068
`
`7
`
`7
`
`1 e
`
`RECONFIGURATTON
`
`TERMINATE
`COMMUNICATION
`RELATED PROCESSES
`
`N102
`
`RECONFTGURE
`NETWORK
`
`N104
`
`In accordance with methods and systems consistent with the
`present invention, an improved technique for recon?guring
`networks is provided By using this technique a network
`d .
`.
`' ?
`h .
`k h.1’ .
`.
`a mmrstrator can recon guret e1r networ w 1 e it'remams
`operational. As a result, users can contmue to utilize the
`network during recon?guration. Additionally, in accordance
`with methods and systems consistent with the present
`invention, a number of network topologies are provided that
`are designed to facilitate recon?guration. When using one of
`these topologies, the network can be recon?gured with a
`minimal amount of recabling, thus reducing the amount of
`time required for recon?guration.
`
`.
`
`.
`
`_
`
`86 Claims, 15 Drawing Sheets
`
`UPGRADE/
`DOWNGRADE
`
`UPDATE ROUTING
`TABLES
`
`I» 1502
`
`1
`
`REMOVE CABLES
`
`M1504
`
`l
`
`ADD/REMOVE
`NODE
`
`1
`
`ADD CABLES
`
`~1508
`
`1
`
`UPDATE ROUTING
`TABLES
`
`U PDATE
`ROUTI N G TABLES
`
`RESTART
`COMMUNTCATION
`RELATED PROCESSES
`
`T106
`
`N108
`
`@
`@
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 1 of 38
`
`

`
`US 6,603,742 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`IBM, “Clustering Algorithm for Computer Network Man
`agement Graphics”, Jun. 1988, pp. 71—79, IBM Technical
`Disclosure Bulletin, vol. 31, No. 1.
`Peercy, M. et al., “Distributed Algorithms for Shortest—Path,
`Deadlock—Free Routing and Broadcasting in Arbitrarily
`Faulty Hypercubes,” International Symposium on Fault Tol
`erant Computing Systems (FTCS), US, Los Alamitos, IEEE
`Comp. Soc. Press, vol. Symp. 20, Jun, 26, 1990, pp.
`218—225.
`
`Fleury, E. et al., “A General Theory for Deadlock Avoidance
`in Wormhole—Routed Networks,” IEEE Trans. on Parallel
`and Distributed Systems, IEEE Inc., NY, vol. 9, No. 7, Jul.
`1, 1998, pp. 626—638.
`Pifarre G. D. et al., “Adaptive Deadlock—and Livestock—
`Free Routing in the Hypercube NetWork,” IEEE Trans. on
`Parallel and Distributed Systems, IEEE Inc., NY, vol. 5, No.
`11, Nov. 1, 1994, pp. 1121—1138.
`
`* cited by examiner
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 2 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 1 0f 15
`
`US 6,603,742 B1
`
`C RECONFIGURATION )
`
`I
`
`TERMINATE
`COMMUNICATION
`RELATED PROCESSES
`
`f\/102
`
`V
`
`RECONFIGURE
`NETWORK
`
`“104
`
`UPDATE
`ROUTING TABLES
`
`“106
`
`TI
`
`RESTART
`COMMUNICATION-
`RELATED PROCESSES
`
`~108
`
`c
`
`)
`
`FIG. 1
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 3 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 2 0f 15
`
`US 6,603,742 B1
`
`200
`
`VIDEO DISPLAY
`
`~204
`
`CHASSIS
`
`~202
`
`KEYBOARD
`
`~206
`
`FIG. 2
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 4 of 38
`
`

`
`U.S. Patent
`
`Aug. 5, 2003
`
`Sheet 3 of 15
`
`US 6,603,742 B1
`
`|PR2016-00726
`
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex 1023, p 5 of 38
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 5 of 38
`
`

`
`mgm5
`
`Mm.5,
`
`m
`
`5
`
`S
`
`omm
`
`:o:>>m
`
`Umow
`
`mum
`
`4oz_Som
`MmE<>>Eow
`
`Ev
`
`oz_Som
`
`mzmfi
`
`U.S. Patent
`
`A
`
`©_\mj
`
`E
`
`EE
`
`me.
`
`>mosm__>_
`
`mom
`
`247,
`
`1
`
`Bmam
`
`/09«mm
`
`mmommmoomm
`
`VGE
`
`|PR2016-00726
`
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 6 of 38
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 6 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 5 0f 15
`
`US 6,603,742 B1
`
`A
`
`D
`
`B
`
`C
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 7 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 6 6f 15
`
`US 6,603,742 B1
`
`A
`
`D
`
`B
`
`C
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 8 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 7 0f 15
`
`US 6,603,742 B1
`
`A
`
`D
`
`B
`
`C
`
`E
`
`\‘LL
`
`\8/
`
`\3/
`
`E
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 9 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 8 0f 15
`
`US 6,603,742 B1
`
`FIG. 8
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 10 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 9 0f 15
`
`US 6,603,742 B1
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 11 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 10 0f 15
`
`US 6,603,742 B1
`
`E
`
`FIG. 10
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 12 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 11 0f 15
`
`US 6,603,742 B1
`
`FIG. 11
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 13 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 12 0f 15
`
`US 6,603,742 B1
`
`FIG. 12
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 14 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 13 0f 15
`
`US 6,603,742 B1
`
`FIG. 13
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 15 of 38
`
`

`
`U.S. Patent
`
`Aug. 5,2003
`
`Sheet 14 0f 15
`
`US 6,603,742 B1
`
`FIG. 14
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 16 of 38
`
`

`
`U.S. Patent
`
`Aug. 5, 2003
`
`Sheet 15 0f 15
`
`US 6,603,742 B1
`
`C UPGRADE/
`DOWNGRADE D
`
`UPDATE ROUTING
`TABLES
`
`M1502
`
`REMOVE CABLES
`
`~15o4
`
`ADDIGFgEDNéOVE
`
`“11506
`
`ADD CABLES
`
`~1508
`
`V
`
`UPDATE ROUTING
`TABLES
`
`“1510
`
`V
`
`END
`
`E
`
`FIG. 15
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 17 of 38
`
`

`
`US 6,603,742 B1
`
`1
`NETWORK RECONFIGURATION
`
`RELATED APPLICATIONS
`
`The following identi?ed US. patent applications are
`relied upon and are incorporated by reference in this appli
`cation.
`US. patent application Ser. No. 09/323,963, entitled
`“Improved Network Topologies,” ?led on even date
`herewith, assigned to a common assignee.
`US. patent application Ser. No. 09/323,696, entitled
`“Deadlock-Free Routing,” ?led on even date herewith,
`assigned to a common assignee.
`US. patent application Ser. No. 09/323,91, entitled
`“Dynamic Generation of Deadlock-Free Routings,”
`?led on even date herewith, assigned to a common
`assignee.
`US. patent application Ser. No. 09/323,965, entitled
`“Recursive Partitioning of Networks,” ?led on even
`date herewith, assigned to a common assignee.
`
`10
`
`15
`
`20
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to data processing
`systems and, more particularly, to network recon?guration.
`
`25
`
`BACKGROUND OF THE INVENTION
`
`35
`
`40
`
`45
`
`“con?guring a network” refers to changing the topology
`of the network (e.g., adding a node or removing a node). A
`30
`“network topology” refers to the structure that provides the
`communications interconnection among nodes of a network.
`As used herein, the term “node” refers to any device capable
`of communicating, such as a computer, router, switch,
`network processor, or symmetric multiprocessor. Thus, the
`topology of a network refers to the network’s particular
`con?guration of links and nodes.
`In conventional static-routing networks, recon?guring a
`network requires four steps as shown in FIG. 1. A static
`routing network uses statically-de?ned routing tables to
`perform routing. The routing is considered to be static
`because if the network is recon?gured, all of the routing
`tables need to be manually updated to account for the
`recon?guration. For eXample, if the recon?guration involves
`removing a node, the routing tables need to be updated to
`avoid routing through this node. And if the recon?guration
`involves adding a node, the routing tables need to be updated
`to route to the new node.
`When recon?guring a static-routing network, the network
`administrator ?rst terminates all processes communicating
`via the network (step 102). NeXt, the system administrator
`recon?gures the network by adding or removing a node and
`by performing the appropriate recabling (step 104). Then,
`the network administrator updates the routing tables in the
`network to account for the recon?guration (e.g., avoid the
`removed node) (step 106) and, ?nally, restarts the processes
`that were terminated (step 108). By recon?guring networks
`in this manner, the networks are rendered nonoperational for
`a signi?cant amount of time, such as a few hours. It is thus
`desirable to improve how networks are recon?gured.
`
`55
`
`60
`
`2
`the network during recon?guration. Additionally, in accor
`dance with methods and systems consistent with the present
`invention, a number of network topologies are provided that
`are designed to facilitate recon?guration. When using one of
`these topologies, the network can be recon?gured with a
`minimal amount of recabling, thus reducing the amount of
`time required for recon?guration.
`In accordance with methods consistent with the present
`invention, a method is provided in a distributed system
`containing a network with nodes, where each of the nodes
`has ports. This method con?gures the network to maXimiZe
`port usage, renders the network operational such that the
`nodes are capable of communicating via the network using
`static routing, and recon?gures the network while the net
`work remains operational.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The accompanying drawings, which are incorporated in
`and constitute a part of this speci?cation, illustrate an
`implementation of the invention and, together with the
`description, serve to eXplain the advantages and principles
`of the invention. In the drawings,
`FIG. 1 depicts a ?owchart of the steps performed by a
`conventional system during network recon?guration;
`FIG. 2 depicts a data processing system suitable for use
`with methods and systems consistent with the present inven
`tion;
`FIG. 3 depicts a more detailed diagram of the chassis of
`FIG. 2;
`FIG. 4 depicts a more detailed diagram of a routing card
`depicted in FIG. 3;
`FIG. 5 depicts a network topology for a network of 7
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 6 depicts a network topology for a network of 8
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 7 depicts a network topology for a network of 9
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 8 depicts a network topology for a network of 10
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 9 depicts a network topology for a network of 11
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 10 depicts a network topology for a network of 12
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 11 depicts a network topology for a network of 13
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 12 depicts a network topology for a network of 14
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 13 depicts a network topology for a network of 15
`nodes in accordance with methods and systems consistent
`with the present invention;
`FIG. 14 depicts a network topology for a network of 16
`nodes in accordance with methods and systems consistent
`with the present invention; and
`FIG. 15 depicts a ?owchart of the steps performed when
`recon?guring one of the networks depicted in FIGS. 5—14.
`
`SUMMARY OF THE INVENTION
`
`In accordance with methods and systems consistent with
`the present invention, an improved technique for recon?g
`uring networks is provided. By using this technique, a
`network administrator can recon?gure their network while it
`remains operational. As a result, users can continue to utiliZe
`
`65
`
`DETAILED DESCRIPTION
`In accordance with methods and systems consistent with
`the present invention, an improved technique for recon?g
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 18 of 38
`
`

`
`US 6,603,742 B1
`
`10
`
`15
`
`20
`
`3
`uring a network is provided that allows the network to
`continue operating during recon?guration. Also, various
`upgrade/downgrade sequences are provided for adding and
`removing one or more nodes which require only a minimal
`amount of recabling. Thus, by recon?guring a network in
`accordance with methods and systems consistent with the
`present invention, the network remains operational and a
`minimum amount of recabling is required.
`The upgrade/downgrade sequences occur in a family of
`network topologies which have been selected to facilitate
`recon?guration. These network topologies are discussed
`below, and they are also discussed in further detail in
`copending US. patent application Ser. No. 09/323,963,
`entitled “Improved Network Topologies,” which has previ
`ously been incorporated by reference. In addition to the
`network topologies, described below are exemplary routing
`tables for use in the network topologies as well as exemplary
`routing tables for use during network recon?guration. All of
`these routing tables provide routings that are deadlock free.
`Thus, using these routing tables ensures that a deadlock does
`not occur in the network. The term “deadlock” refers to an
`undesirable system state that occurs when a cycle of multi
`hop packets are each waiting on a busy node on the next hop.
`A “multi-hop” packet refers to a packet that is routed
`through at least one node before reaching its destination. A
`25
`deadlock may occur, for example, in a network of three
`nodes (node 1, node 2, and node 3), where node 1 is waiting
`to send a multi-hop packet to node 2 (which is not the
`packet’s destination), where node 2 is waiting to send a
`multi-hop packet to node 3 (which is not the packet’s
`destination), and where node 3 is waiting to send a multi-hop
`packet to node 1 (which is not the packet’s destination).
`Since each node is waiting on the other, a stalemate or
`deadlock occurs, and these nodes are rendered non
`operational. Deadlock-free routing is described in greater
`detail in copending US. patent application Ser. No. 09/325,
`696 entitled “Deadlock-free Routing,” which has previously
`been incorporated by reference.
`Implementation Details
`FIG. 2 depicts a data processing system 200 suitable for
`use with methods and systems consistent with the present
`invention. Data processing system 200 contains a chassis
`202 connected to a video display 204 and a keyboard 206.
`Data processing system 200 is suitable for use as one or
`more nodes in the network topologies described below.
`As shown in FIG. 3, chassis 202 contains up to seven
`cards 302—314 interconnected via bus 315. Of these cards,
`cards 308 and 314, known as routing cards, perform routing
`functionality with each having ?ve ports 316—324 and
`326—334 that connect to a communication link (e.g., a
`cable). The cards other than the routing cards (i.e., cards
`302—306, 310, and 312) typically contain multiple CPUs,
`memory, and secondary storage. In accordance with meth
`ods and systems consistent with the present invention, cards
`302—308 form a single node 336. Likewise, cards 310—314
`form a single node 338. Nodes 336 and 338 are referred to
`as partner nodes because they are both located in the same
`chassis 202. Since node 336 and node 338 are separate
`communications nodes, they may be interconnected via a
`communications link 340, known as a partner link. Apartner
`link is used to transfer control information between two
`partner nodes: the actual data is transferred via the bus 315
`for faster communications. One skilled in the art will appre
`ciate that data processing system 200 and chassis 202 may
`include additional or different components, including addi
`tional nodes.
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`4
`FIG. 4 depicts a more detailed diagram of routing card
`308, although routing card 314 is similarly con?gured.
`Routing card 308 contains a memory 402, a switch 404, and
`a processor 406 interconnected by an internal bus 407,
`which also connects to bus 315. Memory 402 contains
`routing software 408 that routes traf?c through the network
`using routing table 410. The switch coordinates the sending
`and receiving of information across the network via ports
`316—324 by using a send and receive buffer 412—430 for
`each port.
`
`Although aspects of the present invention are described as
`being stored in memory, one skilled in the art will appreciate
`that these aspects can also be stored on or read from other
`types of computer-readable media, such as secondary stor
`age devices, like hard disks, ?oppy disks, or CD-ROM; a
`carrier wave from a network, such as the Internet; or other
`forms of RAM or ROM either currently known or later
`developed. Sun, Sun Microsystems, the Sun logo, JavaTM,
`and JavaTM-based trademarks are trademarks or registered
`trademarks of Sun Microsystems, Inc. in the United States
`and other countries.
`
`Network Topologies
`
`In accordance with methods and systems consistent with
`the present invention, a number of network topologies are
`provided where the topologies have been selected based on
`both performance characteristics and the ease with which the
`network can be recon?gured. Network topologies for net
`works having seven to sixteen nodes are presented below
`with exemplary routing tables. The topologies for networks
`having less than seven nodes are not presented because they
`are fully connected. That is, since each routing card has ?ve
`ports, in networks of six or less nodes, each node can be
`connected to each other node. In such a situation, the
`network is referred to as being fully connected.
`
`FIG. 5 depicts a network topology for a network of seven
`nodes in accordance with methods and systems consistent
`with the present invention. Each node, node 0 through node
`6, has up to ?ve links to other nodes. Each link is depicted
`as either a solid line or a dashed line. A solid line indicates
`that the link is a nonpartner link; a dashed line indicates that
`the link is a partner link between partner nodes. Accordingly,
`the two partner nodes are contained in the same device. In
`FIG. 5, the letters (e.g., “A”) indicate a continuing connec
`tion to another like-lettered node. For example, node 0 is
`connected to node 6.
`
`As shown in FIG. 5, node 0 has a partner link with node
`1 and directly connects to nodes 3, 4, 5, and 6. Node 1 has
`a partner link with node 0 and directly connects to nodes 2,
`3, 4, and 5. Node 2 has a partner link with node 3 and
`directly connects to nodes 1, 4, 5, and 6. Node 3 has a partner
`link with node 2 and directly connects to nodes 0, 1, 5, and
`6. Node 4 has a partner link with node 5 and directly
`connects to nodes 0, 1, 2, and 6. Node 5 has a partner link
`with node 4 and directly connects to nodes 0, 1, 2, and 3, and
`node 6 directly connects to nodes 0, 2, 3, and 4. Below is a
`sample routing table for this network. The ?rst row of this
`table, for example, shows that data from node 0 may be sent
`directly to nodes 1, 3, 4, 5, and 6 and that data from node 0
`may be sent to node 2 via node 3.
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 19 of 38
`
`

`
`US 6,603,742 B1
`
`6
`
`-continued
`
`FROM\TO
`
`O
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`FROM\TO O
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`FIG. 6 depicts a network topology for a network of 8
`nodes in accordance With methods and systems consistent
`With the present invention. As shoWn in FIG. 6, node 0 has
`a partner link With node 1 and directly connects to nodes 3
`through 6. Node 1 has a partner link With node 0 and directly
`connects to nodes 2, 4, 5, and 7. Node 2 has a partner link
`With node 3 and directly connects to nodes 1, 4, 6, and 7.
`Node 3 has a partner link With node 2 and directly connects
`to node 0 and nodes 5 through 7. Node 4 has a partner link
`With node 5 and directly connects to nodes 0—2 and 6.
`Node 5 has a partner link With node 4 and directly
`connects to nodes 0, 1, 3, and 7. Node 6 has a partner link
`With node 7 and directly connects to nodes 0 and 2—4, and
`node 7 has a partner link With node 6 and directly connects
`to nodes 1—3 and 5. BeloW is an exemplary routing table for
`this network.
`
`10
`
`25
`
`FIG. 8 depicts a netWork topology for a netWork of 10
`nodes in accordance with methods and systems consistent
`With the present invention. As shoWn in FIG. 8, node 0 has
`a partner link With nodes 1 and directly connects to nodes 3,
`4, 6, and 8. Node 1 has a partner link With node 0 and
`directly connects to nodes 2, 5, 7, and 9. Node 2 has a partner
`link With node 3 and directly connects to nodes 1, 4, 6, and
`9. Node 3 has a partner link With node 2 and directly
`connects to nodes 0, 5, 7, and 8. Node 4 has a partner link
`With node 5 and directly connects to nodes 0,2, 6, and 9.
`Node 5 has a partner link With node 4 and directly connects
`to nodes 1, 3, 7, and 8. Node 6 has a partner link With node
`7 and directly connects to nodes 0, 2, 4, and 8. Node 7 has
`a partner link With node 6 and directly connects to nodes 1,
`3, 5, and 9. Node 8 has a partner link With node 9 and
`directly connects to node 0, 3, 5, and 6 node 9 has a partner
`link With node 8 and directly connects to nodes 1, 2, 4, and
`7. BeloW is an exemplary routing table for this network.
`
`30 FROM\TO 0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`s
`
`9
`
`FROM\TO
`
`0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`0
`
`1
`
`2
`
`3
`
`_ 3 _ _ — — 6
`
`_
`
`_ 2 _ — 7 —
`
`1 _
`
`_ _ 4 — — 35
`
`— 0 —
`
`5 — — —
`
`6
`
`0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`_ 3 _ _ 4 _ 6 _ s
`
`_ _ 2
`
`5 _ 7 _ 9 _
`
`1 _ _ _ 4 _ 6
`
`9 —
`
`_ 0 _
`
`5 _ 7 — — s
`
`_ 0 _ 2
`
`_ _ 6
`
`9 _
`
`1 _ 3 _ _
`
`7 _ _ s
`
`_ 0 _ 2 _
`
`— — s
`
`4
`
`5
`
`6
`
`7
`
`_ _ _ 2
`
`—
`
`_ _ 3 _ —
`
`7 —
`
`— 0 — — — 4
`
`—
`
`1 _ _
`
`5 — —
`
`7
`
`s
`
`9
`
`1 _ 3 _ 5
`
`—
`
`9 —
`
`_ 0
`
`3 _ 5 _ _ 6
`
`_
`
`1 _ _ 2 _ 4
`
`7 — —
`
`FIG. 7 depicts a netWork topology for a netWork of 9
`nodes in accordance with methods and systems consistent
`With the present invention. As shoWn in FIG. 7, node 0 has
`a partner link With node 1 and directly connects to nodes 3,
`4, 6, and 8. Node 1 has a partner link With node 0 and
`directly connects to nodes 2, 4, 5, and 7. Node 2 has a partner
`link With node 3 and directly connects to nodes 1, 4, 6, and
`7. Node 3 has a partner link With node 2 and directly
`connects to nodes 0, 5, 7 and 8. Node 4 has a partner link
`With node 5 and directly connects to nodes 0—2 and 6. Node
`has a partner link With node 4 and directly connects to nodes
`1, 3, 7, and 8. Node 6 has a partner link With node 7 and
`directly connects to nodes 0, 2,4, and 8. Node 7 has a partner
`link With node 6 and directly connects to nodes 1—3 and 5,
`and node 8 directly connects to nodes 0, 3, 5, and 6. BeloW
`is an exemplary routing table.
`
`FROM\TO 0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`s
`
`0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`_ 3 _ _ 4 _ 6 _
`
`_
`
`_ 2 _ _ 7 _ 5
`
`1 _
`
`_ _ 4 _ _ 6
`
`_ 0 _
`
`5 _ 7 _ _
`
`_ _ _ 2
`
`_ _ 6
`
`0
`
`1 _ 3 _ _
`
`7 _ _
`
`40
`
`45
`
`5
`
`60
`
`65
`
`FIG. 9 depicts a netWork topology for a netWork of 11
`nodes in accordance with methods and systems consistent
`With the present invention. As shoWn in FIG. 9, node 0 has
`a partner link With node 1 and directly connects to nodes 3,
`4, 6, and 8. Node 1 has a partner link With node 0 and
`directly connects to nodes 5, 7, 9, and 10. Node 2 has a
`partner link With node 3 and directly connects to nodes 4, 6,
`9, and 10. Node 3 has a partner link With node 2 and directly
`connects to nodes 0, 5, 7, and 8. Node 4 has a partner link
`With node 5 and directly connects to nodes 0, 2, 7, and 9.
`Node 5 has a partner link With node 4 and directly connects
`to nodes 1, 3, 8, and 10. Node 6 has a partner link With node
`7 and directly connects to nodes 0, 2, 8, and 10. Node 7 has
`a partner link With node 6 and directly connects to nodes 1,
`3, 4, and 9. Node 8 has a partner link With node 9 and
`directly connects to nodes 0, 3, 5, and 6. Node 9 has a partner
`link With node 8 and directly connects to nodes 1, 2, 4, and
`7, and node 10 directly connects to nodes 1, 2, 5, and 6. A
`sample routing table for this netWork is provided beloW.
`
`FROM\TO 0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`s
`
`9
`
`10
`
`0
`
`1
`
`_ 3 _ _ 4 _ 6 _ s
`
`6
`
`_
`
`9
`
`5
`
`5 _ 7 _ 9 _ _
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 20 of 38
`
`

`
`US 6,603,742 B1
`
`8
`connects to nodes 5, 7, 8, and 11. Node 4 has a partner link
`with node 5 and directly connects to nodes 0, 2, 9, and 12.
`Node 5 has a partner link with node 4 and directly connects
`to nodes 1, 3, 6, and 8. Node 6 has a partner link with node
`7 and directly connects to nodes 0, 2, 5, and 10. Node 7 has
`a partner link with node 6 and directly connects to nodes 1,
`3, 11, and 12. Node 8 has a partner link with node 9 and
`directly connects to nodes 0, 3, 5, and 12. Node 9 has a
`partner link with node 8 and directly connects to nodes 1, 2,
`4, and 11. Node 10 has a partner link with node 11 and
`directly connects to nodes 1, 2, 6, and 12. Node 11 has a
`partner link with node 10 and directly connects to nodes 0,
`3, 7, and 9, and node 12 directly connects to nodes 4, 7, 8,
`and 10. An exemplary routing table for this network is
`provided below.
`
`FROM\
`TO
`
`0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`— 4
`9
`
`0
`—
`1
`10
`6
`2
`7 —
`11
`3
`4 — 0 — 2
`5
`1 — 3 — —
`6
`— 0 — 2
`5 —
`7
`1 — 3 — 12
`3 —
`12
`8
`— 0
`3 — 5 — 0
`1 —
`9
`1 — — 2 — 4
`2
`2
`10
`1 — — 2
`2
`6 — 6
`12
`11
`— 0
`3 — 0
`3
`7 — 9 — —
`12
`8
`10
`4
`8 — 4
`7 — — 8 — 10
`
`11 — 4
`8 — 4 — 6 — 8
`5
`5 — 7 — 9 — — 10
`7
`— — 4 — 6
`9 — — 10
`10
`5 — 7 — — 8
`11 — 7
`— 0
`12
`9 — 12
`0 —
`— 6 — 8
`1
`3
`8
`— 0
`2 — 10
`10
`3
`11
`11 — —
`— 12
`0 —
`11 — 4
`— —
`7
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`>—t O
`
`>—tc\>~t||t\JU\|
`
`9
`
`||°°°°|°°|
`
`2
`
`8
`
`9 9 9
`
`6
`
`6
`
`7
`
`19116
`
`cxlcx
`
`7
`
`-continued
`
`4
`
`5
`4
`ml I
`
`|4>.|.z>.oo
`
`2 5 5
`
`3
`I
`
`l\Jl\J||l\J|N
`
`2
`
`3 33
`
`1
`
`0
`
`6 1 1 11
`
`FROM\TO
`l\3
`
`©\DO0\]C\LI\-J50-)
`
`>—t
`
`FIG. 10 depicts a network topology for a network of 12
`nodes in accordance with methods and systems consistent
`with the present invention. As shown in FIG. 10, node 0 has
`a partner link with node 1 and directly connects to nodes 4,
`6, 8, and 11. Node 1 has a partner link with node 0 and
`directly connects to nodes 5, 7, 9, and 10. Node 2 has a
`partner link with node 3 and directly connects to nodes 4, 6,
`9, and 10. Node 3 has a partner link with node 2 and directly
`connects to nodes 5, 7, 8, and 11. Node 4 has a partner link
`with node 5 and directly connects to nodes 0, 2, 9, and 11.
`Node 5 has a partner link with node 4 and directly connects
`to nodes 1, 3, 8, and 10. Node 6 has a partner link with node
`7 and directly connects to nodes 0, 2, 8, and 10. Node 7 has
`a partner link with node 6 directly connects to nodes 1, 3, 9,
`and 11. Node 8 has a partner link with node 9 and directly
`connects to nodes 0, 3, 5, and 6. Node 9 has a partner link
`with node 8 and directly connects to nodes 1, 2, 3, and 7.
`Node 10 has a partner link with node 11 and directly
`connects to nodes 1, 2, 5, and 6, and node 11 has a partner
`link with node 10 and directly connects to nodes 0, 3, 4, and
`7. An exemplary routing table is provided below.
`
`6
`
`7
`
`8
`
`9
`
`11
`
`FIG. 12 depicts a network topology for a network of 14
`nodes in accordance with methods and systems consistent
`with the present invention. As shown in FIG. 12, node 0 has
`a partner link with node 1 and directly connects to nodes 4,
`6, 8, and 11. Node 1 has a partner link with node 0 and
`directly connects to nodes 5, 7, 9, and 10. Node 2 has a
`partner link with node 3 and directly connects to nodes 4, 6,
`9, and 10. Node 3 has a partner link with node 2 and directly
`connects to nodes 5, 7, 8, and 11. Node 4 has a partner link
`with node 5 and directly connects to nodes 0, 2, 9, and 12.
`Node 5 has a partner link with node 4 and directly connects
`to nodes 1, 3, 8, and 13. Node 6 has a partner link with node
`7 and directly connects to nodes 0, 2, 10, and 13. Node 7 has
`a partner link with node 6 and directly connects to nodes 1,
`3, 11, and 12. Node 8 has a partner link with node 9 and
`directly connects to nodes 0, 3, 5, and 12. Node 9 has a
`partner link with node 8 and directly connects to nodes 1, 2,
`4, and 13. Node 10 has a partner link with node 11 and
`directly connects to nodes 1, 2, 6, and 12. Node 11 has a
`partner link with node 10 and directly connects to nodes 0,
`3, 7, and 13. Node 12 has a partner link with node 13 and
`directly connects to nodes 4, 7, 8, and 10, and node 13 has
`a partner link with node 12 and directly connects to nodes 5,
`6, 9, and 11. An exemplary routing table for this network is
`provided below.
`
`40
`
`45
`
`50
`
`55
`
`10
`10
`
`10
`10
`
`0
`7
`
`1
`
`2
`
`99 9 9
`
`|>—t\D|c\|c\
`
`6 6
`
`5
`— 3
`
`3
`
`4
`
`5
`
`|u\oo
`
`|l\Jl\J||l\J|l\J
`
`mlml
`|u\|u\xot\J|
`
`||4»|48
`4:-l-b-lung
`
`|\:|
`>—‘oo\1
`
`\:|\:||
`
`2
`
`49
`
`3 33 3
`
`FROM\TO
`
`0
`
`1
`
`6
`11
`
`1 1 11
`
`>—|©\DO0\]G\U\-BU-)l\J>—*©
`
`>—t>—t
`
`FIG. 11 depicts a network topology for a network of 13
`nodes in accordance with methods and systems consistent
`with the present invention. As shown in FIG. 11, node 0 has
`a partner link with node 1 and directly connects to nodes 4,
`6, 8, and 11. Node 1 has a partner link with node 0 and
`directly connects to nodes 5, 7, 9, and 10. Node 2 has a
`partner link with node 3 and directly connects to nodes 4, 6,
`9, and 10. Node 3 has a partner link with node 2 and directly
`
`FROM\TO
`
`0
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`— 4
`9
`
`10
`7 —
`
`11
`8 — 4 — 6 — 8
`5
`5 — 7 — 9 — — 10
`— — 4 — 6
`9 — — 10
`5 — 7 — — 8
`11 —
`
`6
`11
`
`U-)[\J>—*©
`
`12
`
`8
`7
`10
`7
`
`13
`
`6
`5
`6
`11
`
`|PR2016-00726
`
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 21 of 38
`
`IPR2016-00726
`ACTIVISION, EA, TAKE-TWO,
`2K, ROCKSTAR
`Ex. 1023, p. 21 of 38
`
`

`
`US 6,603,742 B1
`
`10
`
`9
`
`-continued
`
`with the present invention. As shown in this figure, node 0
`has a partner link with node 1 and directly connects to nodes
`4, 6, 8, and 11. Node 1 has a partner link with node 0 and
`directly connects to nodes 5, 7, 9, and 10. Node 2 has a
`partner link with node 3 and directly connects to nodes 4, 6,
`9, and 10. Node 3 has a partner link with node 2 and directly
`connects to nodes 5, 7, 8, and 11. Node 4 has a partner link
`with node 5 and directly connects to nodes 0, 2, 12, and 15.
`Node 5 has a partner link with node 4 and directly connects
`to nodes 1, 3, 13, and 14. Node 6 has a partner link with node
`7 and directly connects to nodes 0, 2, 13, and 14. Node 7 has
`a partner link with node 6 and directly connects to nodes 1,
`3, 12, and 15. Node 8 has a partner link with node 9 and
`directly connects to nodes 0, 3, 12, and 14. Node 9 has a
`partner link with node 8 and directly connects to nodes 1, 2,
`13, and 15. Node 10 has a partner link with node 11 and
`directly connects to nodes 1, 2, 12, and 14. Node 11 has a
`partner link with node 10 and directly connects to nodes 0,
`3, 13, and 15. Node 12 has a partner link with node 13 and
`directly connects to nodes 4, 7, 8, and 10. Node 13 has a
`partner link with node 12 a