(12) United States Patent
`Steele, Jr. et al.
`
`US006603742B1
`US 6,603,742 B1
`Aug. 5,2003
`
`(io) Patent No.:
`(45) Date of Patent:
`
`(54) NETWORK RECONFIGURATION
`
`(75)
`
`Inventors: Guy L. Steele, Jr., Lexington, MA
`(US); Steven K. Heller, Chelmsford,
`MA (US); Daniel Cassiday, Topsfield,
`MA (US); Jon Wade, Wellesley, MA
`(US)
`
`(73) Assignee: Sun Microsystems, Inc., Santa Clara,
`CA (US)
`
`( * ) Notice:
`
`term this
`
`the
`Subject to any disclaimer,
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`EP
`
`6,005,860 A
`6,031,835 A
`6,055,618 A
`6,064,671 A
`6,097,718 A
`6,137,781 A
`6,230,252 B1
`6,243,760 B1
`6,256,295 B1
`6,295,573 B1
`6,437,804 B1
`
`12/1999 Anderson et al.
`2/2000 Abalietal.
`4/2000 Thorson
`5/2000 Killian
`8/2000 Bion
`10/2000 Goto et al.
`5/2001 Passint et al.
`6/2001 Armbraster et al.
`7/2001 Gallon
`9/2001 Bailey et al.
`8/2002 Ibe et al.
`
`of
`
`FOREIGN PATENT DOCUMENTS
`
`817097 A2
`
`1/1998
`
`OTHER PUBLICATIONS
`
`(21) Appl. No.: 09/323,962
`
`(22) Filed:
`
`Jun. 2, 1999
`
`11041. 12 2iS
`(51) Int. CI.7
`370/254; 370/400
`(52) U.S. CI
`(58) Field of Search
`370/351, 242,
`370/408, 402, 400, 254; 709/238, 293,
`242, 246, 258
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`Whay C. Lee, "Topology Aggregation for Hierarchical
`Routing in ATM Networks." Apr. 1, 1995, pp. 82-92,
`Review.
`Computer-Communication
`
`(List 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.
`ABSTRACT
`
`(57)
`
`5,128,932 A
`7/1992 Li
`5,453,978 A
`9/1995 Sethu et al.
`5,602,839 A
`2/1997 Annapareddy et al.
`5,680,116 A
`10/1997 Hashimoto et al.
`5,721,819 A
`2/1998 Galles et al.
`5,740,346 A
`4/1998 Wickietal.
`5,751,710 A *
`5/1998 Crowther et al
`5,751,967 A
`5/1998 Raab et al.
`5,768,501 A
`6/1998 Lewis
`5,781,546 A
`7/1998 Sethu
`5,812,549 A
`9/1998 Sethu
`5,859,981 A
`1/1999 Levin et al.
`5,874,964 A
`2/1999 Gille
`5,884,047 A
`3/1999 Aikawa et al.
`5,914,953 A
`6/1999 Krause et al.
`5,970,232 A * 10/1999 Passint et al.
`
`370/423
`
`systems
`and
`In accordance with methods
`present invention, an improved technique for reconfiguring
`networks is provided. By using this technique, a network
`reconfigure
`their
`
`network remains
`administrator can
`operational. As a result, users can continue to utilize the
`network during
`reconfiguration.
`Additionally,
`in
`with methods and systems consistent with the present
`invention, a number
`of network topologies
`are provided
`are designed
`to
`facilitate
`reconfiguration.
`
`When one of
`these topologies, the network can be reconfigured with a
`minimal amount of recabling, thus reducing the amount of
`time required for reconfiguration.
`
`consistent
`
`while
`
`accordance
`
`that
`using
`
`395/200.68
`
`86 Claims, 15 Drawing Sheets
`
`I
`
`UPGRADE/
`DOWNGRADE
`
`J
`
`UPD ATE ROUTI
`NG
`TABLES
`
`1502
`
`REMOVE CABLES
`
`•1504
`
`ADD/REM<
`OVE
`NODE
`
`1506
`
`ADD CABLES
`
`• 1508
`
`RECONFIGURATION
`
`TERMINATE
`iMMUNICATION
`CO
`PROCESSES
`RELA TED
`
`102
`
`RECONFIGURE
`NETWORK
`
`• 104
`
`UPDATE
`BLES
`ROUTING TAl
`
`•106
`
`RESTART
`COMMUNICATION-
`RELATED PROCESSES
`
`108
`
`END
`
`UPD ATE ROU
`TING
`TABLES
`
`1510
`
`END
`
`BUNGIE - EXHIBIT 1038
`
`

`

`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
`
`

`

`U.S. Patent
`
`Aug. 5, 2003
`
`Sheet 1 of 15
`
`US 6,603,742 B1
`
`102
`
`104
`
`106
`
`108
`
`RECONFIGURATION
`
`i r
`
`TERMINATE
`COMMUNICATION
`RELATED PROCESSES
`
`RECONFIGURE
`NETWORK
`
`UPDATE
`ROUTING TABLES
`
`RESTART
`COMMUNICATION-
`RELATED PROCESSES
`
`END
`
`FIG. 1
`
`

`

`U.S. Patent
`
`Aug. 5, 2003
`
`Sheet 2 of 15
`
`US 6,603,742 B1
`
`200
`r7
`
`VIDEO DISPLAY
`
`204
`
`CHASSIS
`
`202
`
`KEYBOARD
`
`206
`
`FIG. 2
`
`

`

`K) w
`o\ o u>
`o\
`cn
`d
`
`US 6,603,742 B1
`
`N« -J
`
`Ul
`o MS
`ui
`rD £
`!Z5 sr
`
`Sheet 3 0f 15
`
`o o OJ
`
`Ul
`CfQ
`=
`>
`
`Aug. 5, 2003
`
`O)
`d
`
`9
`ft
`
`US. Patent
`
`u
`
`,-338
`
`
`
`315
`
`T
`
`BUS
`
`334-
`
`332-
`
`330-
`
`<
`
`328-
`
`\
`
`326^
`314
`
`2L
`
`312
`
`2L
`
`220
`
`310
`
`340
`
`FIG. 3
`
`324-
`
`322- ^
`
`320-
`
`318.
`
`316^
`308
`
`306
`
`\
`
`304
`
`302
`
`336-,
`
`

`

`W
`K)
`
`o\ o
`ON
`cn
`d
`
`*"b
`o
`
`CZ3 sr
`
`fD
`fD
`
`o o
`
`OJ
`
`Ul
`CfQ
`
`> =
`
`9
`ft
`
`O)
`d
`
`324
`
`322
`
`320
`
`318
`
`316
`
`RCV |-
`
`SEND |—
`
`RCV |-
`
`SEND [—
`
`RCV H
`SENDJ-I
`
`RCV
`
`SEND
`
`RCV
`
`SEND |—
`
`430
`
`428
`
`426
`
`424
`
`422
`
`420
`
`418
`
`416
`
`414
`
`412
`
`BUS
`1—.—1^-315
`
`PROCESSOR
`
`J
`406
`
`TABLE
`ROUTING ^
`410
`
`408
`
`SOFTWARE
`ROUTING
`
`SWITCH
`
`407
`
`FIG. 4
`
`404
`
`MEMORY
`
`402
`
`308
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 5 of 15
`Sheet 5 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`D
`
`D
`
`B
`
`B
`
`C
`
`3
`
`A'
`
`A
`
`A
`
`0
`
`4
`
`\ '
`
`2
`
`JL
`
`C
`
`6
`
`5
`
`A
`
`D
`
`B
`
`FIG. 5
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 6 of 15
`Sheet 6 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`D
`
`B
`
`C
`
`
`
`V
`/ \
`
`c
`
`0
`
`4
`
`2
`
`6
`
`A
`
`\ /
`
`3
`
`7
`
`1
`
`5
`
`D
`
`B
`
`FIG. 6
`
`

`

`©
`
`A.
`
`7
`
`\ /
`A
`' \
`
`4
`
`Q
`
`V
`
`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 7 of 15
`Sheet 7 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`D
`
`B
`
`E
`
`8
`
`E
`
`
`
`6
`
`5
`
`A
`
`D
`
`B
`
`FIG. 7
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 8 of 15
`Sheet 8 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`D
`
`B
`
`O:
`
`4
`
`8
`
`•
`
`(!)
`
`7
`
`E
`E
`
`F
`F
`
`G
`G
`
`E
`E
`
`F
`F
`
`G
`
`o G
`
`V
`
`0
`
`0
`
`9
`
`6
`
`5
`
`A
`
`D
`
`B
`
`FIG. 8
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 9 of 15
`Sheet 9 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`D
`
`B
`
`E
`
`F
`
`G
`
`0
`
`4
`
`6
`
`
`
`E
`
`F
`
`G
`
`9
`
`8
`
`>
`
`10
`
`N X
`
`0
`
`7
`
`* v
`
`5
`
`A
`
`D
`
`B
`
`FIG. 9
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 10 of 15
`Sheet 10 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`D
`
`B
`
`8
`
`<!>
`
`—={11
`
`E
`
`E
`
`E
`
`E
`
`H
`H
`
`F
`F
`
`G
`G
`
`4
`
`(S1
`
`6
`
`G
`
`H
`H
`
`F
`
`G
`
`9
`
`/s.
`
`10
`
`>
`
`7
`
`4
`
`/
`v
`
`/ *
`
`©
`
`A
`
`D
`
`B
`
`FIG. 10
`
`FIG. 10
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 11 of 15
`Sheet 11 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`B
`
`0
`
`r H U
`
`E
`
`V
`
`,—i-
`
`F
`
`G
`
`9
`
`
`
`8
`
`•
`
`12
`
`10
`
`V.
`
`E
`
`F
`
`G
`
`<3>
`
`4
`
`v
`
`0
`
`6
`
`A
`
`v '
`
`' ^
`
`r-o
`
`5
`
`B
`
`FIG. 11
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 12 of 15
`Sheet 12 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`B
`
`D
`
`0
`
`11
`
`E
`
`E
`
`N. /
`
`8
`
`0-\
`
`E
`
`E
`
`F
`F
`
`G
`G
`
`H
`
`<3:
`
`4
`
`\ /
`
`/ \
`
`0
`
`6
`
`
`
`/ y
`
`o
`
`10
`
`7 / x
`
`F
`F
`
`G
`G
`
`H
`
`H
`
`9
`
`0
`
`A
`
`B
`
`D
`
`FIG. 12
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 13 of 15
`Sheet 13 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`B
`
`D
`
`0; 0 0
`
`^
`
`*
`
`N.
`
`E
`
`E
`
`F
`F
`
`G
`
`G
`
`H
`H
`
`11
`
`E
`
`E
`
`F
`F
`
`G
`
`G
`
`H
`
`9
`
`13
`
`
`
`4
`
`> '
`^ \
`
`\ /
`
`/
`
`0^A—0 i , ' 0
`
`7
`• \
`
`<6)^1 0 •"•••,0
`
`A
`
`B
`
`D
`
`FIG. 13
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 5, 2003
`Aug. 5, 2003
`
`Sheet 14 of 15
`Sheet 14 0f 15
`
`US 6,603,742 B1
`US 6,603,742 B1
`
`A
`
`B
`
`D
`
`0; 0 0 ^0
`
`E
`
`F
`
`\
`
`/
`
`
`
`E
`
`F
`
`G
`
`0—7^-0——^0
`
`v
`
`Tr
`
`\ '
`
`\ /
`
`\ /
`
`/ \
`
`x '
`K
`
`)'
`/ *
`
`^—®
`
`\ /
`
`(0—^—®
`
`G
`
`(§)•''''
`
`(H)
`
`($) —H(13)
`
`H
`
`A
`
`B
`
`D
`
`FIG. 14
`
`FIG. 14
`
`

`

`U.S. Patent
`
`Aug. 5, 2003
`
`Sheet 15 of 15
`
`US 6,603,742 B1
`
`UPGRADE/
`DOWNGRADE
`
`UPDATE ROUTING
`TABLES
`
`1502
`
`REMOVE CABLES
`
`1504
`
`ADD/REMOVE
`NODE
`
`1506
`
`ADD CABLES
`
`1508
`
`UPDATE ROUTING
`TABLES
`
`1510
`
`END
`
`FIG. 15
`
`

`

`US 6,603,742 B1
`
`1
`NETWORK RECONFIGURATION
`
`RELATED APPLICATIONS
`
`The following identified U.S. patent applications are 5
`relied upon and are incorporated by reference in this appli-
`cation.
`U.S. patent application Ser. No. 09/323,963, entitled
`"Improved Network Topologies," filed on even date
`herewith, assigned to a common assignee.
`U.S. patent application Ser. No. 09/323,696, entitled
`"Deadlock-Free Routing," filed on even date herewith,
`assigned to a common assignee.
`U.S. patent application Ser. No. 09/323,91, entitled
`"Dynamic Generation of Deadlock-Free Routings,"
`filed on even date herewith, assigned to a common
`assignee.
`U.S. patent application Ser. No. 09/323,965, entitled
`"Recursive Partitioning of Networks," filed on even
`date herewith, assigned to a common assignee.
`
`2
`the network during reconfiguration. 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 reconfiguration. When using one of
`these topologies, the network can be reconfigured with a
`minimal amount of recabling, thus reducing the amount of
`time required for reconfiguration.
`In accordance with methods consistent with the present
`invention, a method is provided in a distributed system
`10 containing a network with nodes, where each of the nodes
`has ports. This method configures 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 reconfigures 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 specification, illustrate an
`implementation of the invention and, together with the
`20 description, serve to explain the advantages and principles
`of the invention. In the drawings,
`FIG. 1 depicts a flowchart of the steps performed by a
`FIELD OF THE INVENTION
`conventional system during network reconfiguration;
`The present invention relates generally to data processing
`FIG. 2 depicts a data processing system suitable for use
`systems and, more particularly, to network reconfiguration. 25 with methods and systems consistent with the present inven­
`tion;
`BACKGROUND OF THE INVENTION
`FIG. 3 depicts a more detailed diagram of the chassis of
`FIG. 2;
`"configuring a network" refers to changing the topology
`FIG. 4 depicts a more detailed diagram of a routing card
`of the network (e.g., adding a node or removing a node). A
`"network topology" refers to the structure that provides the 30 depicted in FIG. 3;
`FIG. 5 depicts a network topology for a network of 7
`communications interconnection among nodes of a network.
`nodes in accordance with methods and systems consistent
`As used herein, the term "node" refers to any device capable
`with the present invention;
`of communicating, such as a computer, router, switch,
`network processor, or symmetric multiprocessor. Thus, the
`FIG. 6 depicts a network topology for a network of 8
`topology of a network refers to the network's particular 35 nodes in accordance with methods and systems consistent
`configuration of links and nodes.
`with the present invention;
`FIG. 7 depicts a network topology for a network of 9
`In conventional static-routing networks, reconfiguring a
`nodes in accordance with methods and systems consistent
`network requires four steps as shown in FIG. 1. A static-
`with the present invention;
`routing network uses statically-defined routing tables to
`perform routing. The routing is considered to be static
`FIG. 8 depicts a network topology for a network of 10
`because if the network is reconfigured, all of the routing
`nodes in accordance with methods and systems consistent
`tables need to be manually updated to account for the
`with the present invention;
`reconfiguration. For example, if the reconfiguration involves
`FIG. 9 depicts a network topology for a network of 11
`removing a node, the routing tables need to be updated to 45 nodes in accordance with methods and systems consistent
`avoid routing through this node. And if the reconfiguration
`with the present invention;
`involves adding a node, the routing tables need to be updated
`FIG. 10 depicts a network topology for a network of 12
`to route to the new node.
`nodes in accordance with methods and systems consistent
`When reconfiguring a static-routing network, the network
`with the present invention;
`administrator first terminates all processes communicating 5Q
`FIG. 11 depicts a network topology for a network of 13
`via the network (step 102). Next, the system administrator
`nodes in accordance with methods and systems consistent
`reconfigures the network by adding or removing a node and
`with the present invention;
`by performing the appropriate recabling (step 104). Then,
`FIG. 12 depicts a network topology for a network of 14
`the network administrator updates the routing tables in the
`nodes in accordance with methods and systems consistent
`network to account for the reconfiguration (e.g., avoid the
`55 with the present invention;
`removed node) (step 106) and, finally, restarts the processes
`FIG. 13 depicts a network topology for a network of 15
`that were terminated (step 108). By reconfiguring networks
`nodes in accordance with methods and systems consistent
`in this manner, the networks are rendered nonoperational for
`with the present invention;
`a significant amount of time, such as a few hours. It is thus
`FIG. 14 depicts a network topology for a network of 16
`desirable to improve how networks are reconfigured.
`60 nodes in accordance with methods and systems consistent
`with the present invention; and
`FIG. 15 depicts a flowchart of the steps performed when
`reconfiguring one of the networks depicted in FIGS. 5-14.
`DETAILED DESCRIPTION
`In accordance with methods and systems consistent with
`the present invention, an improved technique for reconfig-
`
`SUMMARY OF THE INVENTION
`In accordance with methods and systems consistent with
`the present invention, an improved technique for reconfig­
`uring networks is provided. By using this technique, a 65
`network administrator can reconfigure their network while it
`remains operational. As a result, users can continue to utilize
`
`

`

`US 6,603,742 B1
`
`Network Topologies
`
`4
`FIG. 4 depicts a more detailed diagram of routing card
`308, although routing card 314 is similarly configured.
`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 traffic 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.
`
`3
`uring a network is provided that allows the network to
`continue operating during reconfiguration. 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 reconfiguring a network in 5
`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 1°
`reconfiguration. These network topologies are discussed
`below, and they are also discussed in further detail in
`Although aspects of the present invention are described as
`copending U.S. patent application Ser. No. 09/323,963,
`being stored in memory, one skilled in the art will appreciate
`entitled "Improved Network Topologies," which has previ­
`that these aspects can also be stored on or read from other
`ously been incorporated by reference. In addition to the 15
`types of computer-readable media, such as secondary stor­
`network topologies, described below are exemplary routing
`age devices, like hard disks, floppy disks, or CD-ROM; a
`tables for use in the network topologies as well as exemplary
`carrier wave from a network, such as the Internet; or other
`routing tables for use during network reconfiguration. All of
`forms of RAM or ROM either currently known or later
`these routing tables provide routings that are deadlock free.
`Thus, using these routing tables ensures that a deadlock does 20 developed. Sun, Sun Microsystems, the Sun logo, Java™,
`not occur in the network. The term "deadlock" refers to an
`and Java™-based trademarks are trademarks or registered
`undesirable system state that occurs when a cycle of multi-
`trademarks of Sun Microsystems, Inc. in the United States
`hop packets are each waiting on a busy node on the next hop.
`and other countries.
`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
`In accordance with methods and systems consistent with
`to send a multi-hop packet to node 2 (which is not the
`the present invention, a number of network topologies are
`packet's destination), where node 2 is waiting to send a
`multi-hop packet to node 3 (which is not the packet's 30 provided where the topologies have been selected based on
`destination), and where node 3 is waiting to send a multi-hop
`both performance characteristics and the ease with which the
`packet to node 1 (which is not the packet's destination).
`network can be reconfigured. Network topologies for net­
`Since each node is waiting on the other, a stalemate or
`works having seven to sixteen nodes are presented below
`deadlock occurs, and these nodes are rendered non-
`with exemplary routing tables. The topologies for networks
`operational. Deadlock-free routing is described in greater 35
`having less than seven nodes are not presented because they
`detail in copending U.S. patent application Ser. No. 09/325,
`are fully connected. That is, since each routing card has five
`696 entitled "Deadlock-free Routing," which has previously
`ports, in networks of six or less nodes, each node can be
`been incorporated by reference.
`connected to each other node. In such a situation, the
`Implementation Details
`40 network is referred to as being fully connected.
`FIG. 2 depicts a data processing system 200 suitable for
`FIG. 5 depicts a network topology for a network of seven
`use with methods and systems consistent with the present
`nodes in accordance with methods and systems consistent
`invention. Data processing system 200 contains a chassis
`with the present invention. Each node, node 0 through node
`202 connected to a video display 204 and a keyboard 206.
`6, has up to five links to other nodes. Each link is depicted
`Data processing system 200 is suitable for use as one or 45
`as either a solid line or a dashed line. A solid line indicates
`more nodes in the network topologies described below.
`that the link is a nonpartner link; a dashed line indicates that
`As shown in FIG. 3, chassis 202 contains up to seven
`the link is a partner link between partner nodes. Accordingly,
`cards 302-314 interconnected via bus 315. Of these cards,
`the two partner nodes are contained in the same device. In
`cards 308 and 314, known as routing cards, perform routing
`5, the letters (e.g., A ) indicate a continuing connec­
`functionality with each having five ports 316-324 and 50
`tion to another like-lettered node. For example, node 0 is
`326-334 that connect to a communication link (e.g., a
`connected to node 6.
`cable). The cards other than the routing cards (i.e., cards
`302-306, 310, and 312) typically contain multiple CPUs,
`As shown in FIG. 5, node 0 has a partner link with node
`memory, and secondary storage. In accordance with meth­
`1 and directly connects to nodes 3, 4, 5, and 6. Node 1 has
`ods and systems consistent with the present invention, cards 55
`a partner link with node 0 and directly connects to nodes 2,
`302-308 form a single node 336. Likewise, cards 310-314
`3, 4, and 5. Node 2 has a partner link with node 3 and
`form a single node 338. Nodes 336 and 338 are referred to
`directly connects to nodes 1,4,5, and 6. Node 3 has a partner
`as partner nodes because they are both located in the same
`link with node 2 and directly connects to nodes 0, 1, 5, and
`chassis 202. Since node 336 and node 338 are separate
`6. Node 4 has a partner link with node 5 and directly
`communications nodes, they may be interconnected via a 60
`connects to nodes 0, 1, 2, and 6. Node 5 has a partner link
`communications link 340, known as a partner link. Apartner
`with node 4 and directly connects to nodes 0,1,2, and 3, and
`link is used to transfer control information between two
`node 6 directly connects to nodes 0, 2, 3, and 4. Below is a
`partner nodes: the actual data is transferred via the bus 315
`sample routing table for this network. The first row of this
`for faster communications. One skilled in the art will appre-
`ciate that data processing system 200 and chassis 202 may 65 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
`include additional or different components, including addi-
`may be sent to node 2 via node 3.
`tional nodes.
`
`

`

`US 6,603,742 B1
`
`6
`
`-continued
`
`5
`
`1
`
`2
`
`3
`
`0
`
`1
`
`3
`
`4
`
`5
`
`5
`
`2
`
`6
`
`4
`
`5
`
`FROMYTO
`
`0 12 3
`
`6
`7
`8
`
`1
`
`0
`
`0
`
`3
`
`2
`
`4
`
`5
`5
`
`6
`
`5
`
`4
`
`8
`
`3
`
`7
`
`6
`
`3
`
`J Q
`
`FROMYTO
`
`0
`1
`2
`3
`4
`5
`6
`
`0
`
`4
`
`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,
`FIG. 6 depicts a network topology for a network of 8
`4, 6, and 8. Node 1 has a partner link with node 0 and
`nodes in accordance with methods and systems consistent
`with the present invention. As shown in FIG. 6, node 0 has 15 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
`a partner link with node 1 and directly connects to nodes 3
`9. Node 3 has a partner link with node 2 and directly
`through 6. Node 1 has a partner link with node 0 and directly
`connects to nodes 0, 5, 7, and 8. Node 4 has a partner link
`connects to nodes 2, 4, 5, and 7. Node 2 has a partner link
`with node 5 and directly connects to nodes 0,2, 6, and 9.
`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 20 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
`to node 0 and nodes 5 through 7. Node 4 has a partner link
`7 and directly connects to nodes 0, 2, 4, and 8. Node 7 has
`with node 5 and directly connects to nodes 0-2 and 6.
`a partner link with node 6 and directly connects to nodes 1,
`Node 5 has a partner link with node 4 and directly
`3, 5, and 9. Node 8 has a partner link with node 9 and
`connects to nodes 0, 1, 3, and 7. Node 6 has a partner link
`directly connects to node 0, 3, 5, and 6 node 9 has a partner
`with node 7 and directly connects to nodes 0 and 2-4, and 25
`link with node 8 and directly connects to nodes 1, 2, 4, and
`node 7 has a partner link with node 6 and directly connects
`7. Below is an exemplary routing table for this network.
`to nodes 1-3 and 5. Below is an exemplary routing table for
`this network.
`
`FROMYTO
`
`0
`
`1
`
`4
`
`5
`
`2
`
`3
`
`3
`
`2
`
`7
`
`6
`
`6
`
`7
`
`1
`
`3
`
`2
`
`5
`
`5
`
`30
`
`FROMYTO
`
`0 12 3
`
`4
`
`5
`
`4
`
`4
`
`6
`
`7
`
`7
`
`7
`
`6
`
`6
`
`8
`
`9
`9
`
`9
`
`8
`
`8
`
`0
`1
`2
`3
`4
`5
`6
`7
`
`1
`
`1
`
`0
`
`0
`
`2
`
`3
`
`4
`
`4
`
`5
`
`5
`
`6
`
`7
`
`0
`1
`2
`3
`4
`5
`6
`7
`8
`9
`
`35
`
`40
`
`0
`0
`
`0
`
`0
`
`1
`
`1
`
`1
`
`3
`
`3
`3
`
`2
`
`2
`
`2
`
`5
`5
`
`4
`
`4
`
`7
`
`7
`
`9
`
`9
`
`8
`8
`
`6
`
`6
`
`piG. 9 depicts a network topology for a network of 11
`FIG. 7 depicts a network topology for a network of 9
`nodes in accordance with methods and systems consistent
`nodes in accordance with methods and systems consistent
`with the present invention. As shown in FIG. 9, node 0 has
`with the present invention. As shown in FIG. 7, node 0 has
`a partner link with node 1 and directly connects to nodes 3, 45 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
`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
`directly connects to nodes 5, 7, 9, and 10. Node 2 has a
`link with node 3 and directly connects to nodes 1, 4, 6, and
`partner link with node 3 and directly connects to nodes 4, 6,
`7. Node 3 has a partner link with node 2 and directly
`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 50 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
`with node 5 and directly connects to nodes 0, 2, 7, and 9.
`has a partner link with node 4 and directly connects to nodes
`Node 5 has a partner link with node 4 and directly connects
`1, 3, 7, and 8. Node 6 has a partner link with node 7 and
`to nodes 1, 3, 8, and 10. Node 6 has a partner link with node
`directly connects to nodes 0,2,4, and 8. Node 7 has a partner
`7 and directly connects to nodes 0, 2, 8, and 10. Node 7 has
`link with node 6 and directly connects to nodes 1-3 and 5, 55 a partner link with node 6 and directly connects to nodes 1,
`and node 8 directly connects to nodes 0, 3, 5, and 6. Below
`3, 4, and 9. Node 8 has a partner link with node 9 and
`is an exemplary routing table.
`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
`60 sample routing table for this network is provided below.
`
`FROM\TO
`
`0 12 3
`
`4
`
`5
`
`6
`
`7
`
`™
`
`0
`1
`2
`3
`4
`5
`
`3
`
`3
`
`0
`
`1
`
`1
`
`2
`
`2
`
`5
`
`4
`
`4
`
`7
`
`7
`
`7
`
`6
`
`6
`
`5
`6
`
`0
`
`FROMYTO 01234567 8
`
`65
`
`0
`1
`
`3
`9
`
`5
`
`5
`
`4
`
`6
`
`7
`
`9
`
`9
`
`8
`
`10
`
`6
`
`

`

`US 6,603,742 B1
`
`7
`
`-continued
`FROMVTO 01234567 8
`2
`4
`6
`9
`3
`4
`9
`5
`6
`7
`8
`9
`10
`
`7
`7
`8
`
`7
`
`8
`4
`4
`
`1
`
`6
`
`6
`
`9
`
`6
`
`6 10
`0
`0
`3
`0
`3
`0 3
`
`1
`1
`1
`1
`
`5
`
`2
`
`2
`
`2
`5
`2
`2 5
`
`9
`
`8
`8
`8
`
`2
`
`10
`
`5
`2
`
`1
`6
`1
`
`FROM\
`TO
`0
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`
`0
`
`1
`
`4
`3
`2
`4 8 —
`9
`5
`5
`5
`
`5 6
`4
`4
`
`7 8
`6
`7
`6
`7
`0 12
`6
`
`1 2
`4
`7
`9
`9
`10
`7
`8 11
`9 - 12
`0 —
`8 13 8
`10
`10
`2 —
`0
`3 11 11
`12
`11
`
`9 1 0 1 1
`
`
`
`8 11
`
`2
`8
`
`10
`10
`
`0
`
`10
`
`4
`7
`
`5
`12 3
`5 — 0 12
`4
`2 1
`6 12
`2 6 —
`0 3 7
`9
`- 4
`7
`
`2
`2
`
`6 10
`11
`7
`0
`1
`3
`0
`3
`1
`0 3
`1
`2
`1
`2
`- 0 3 —
`8 10 4 8
`
`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
`5 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,
`10 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
`FIG. 10 depicts a network topology for a network of 12
`nodes in accordance with methods and systems consistent 15 provided below,
`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, 20
`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 25
`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. 30
`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.
`
`FIG. 12 depicts a network topology for a network of 14
`35 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
`40 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
`45 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
`50 partner link with node 8 and directly connects to nodes 1,2,
`FIG. 11 depicts a network topology for a network of 13
`4, and 13. Node 10 has a partner link with node 11 and
`nodes in accordance with methods and systems consistent
`directly connects to nodes 1, 2, 6, and 12. Node 11 has a
`with the present invention. As shown in FIG. 11, node 0 has
`partner link with node 10 and directly connects to nodes 0,
`a partner link with node 1 and directly connects to nodes 4,
`3, 7, and 13. Node 12 has a partner link with node 13 and
`6, 8, and 11. Node 1 has a partner link with node 0 and 55 directly connects to nodes 4, 7, 8, and 10, and node 13 has
`directly connects to nodes 5, 7, 9, and 10. Node 2 has a
`a partner link with node 12 and directly connects to nodes 5,
`partner link with node 3 and directly connects to nodes 4, 6,
`6, 9, and 11. An exemplary routing table for this network is
`9, and 10. Node 3 has a partner link with node 2 and directly
`provided below.
`
`FROMVTO 0123456789 10
`0
`4
`8 —
`4
`6
`9
`5
`5
`9
`1
`9
`2
`4
`6
`5
`3
`9
`4
`9
`5
`1 —
`6
`7
`8
`9
`10
`11
`
`8
`
`11
`
`11
`11
`
`11
`5
`1
`
`8
`8
`8
`
`9
`
`6
`2
`5
`6
`— 37
`
`6 10
`11
`7
`0
`3
`1
`0
`3
`1
`0 3
`1
`1
`
`0 3
`
`7
`7
`0
`10
`
`2
`
`2 10
`2
`— 93
`5
`2
`4
`5
`2
`4
`
`7
`7
`
`11
`
`~
`10
`
`10
`__
`0
`7
`
`FROMYTO 0123456789 10
`0
`4 8 —
`4
`6
`1
`9
`5
`5
`2
`3
`
`9
`9
`
`6
`
`7
`
`7
`
`8
`
`11
`
`8
`
`11
`
`6 10
`11
`7
`
`4
`
`5
`
`11
`
`10
`10
`
`12
`8
`7
`10
`7
`
`13
`6
`5
`6
`11
`
`

`

`US 6,603,742 B1
`
`10
`
`9
`
`-continued
`
`FROMYTO
`
`0 1
`
`2
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9 10
`
`11
`
`12
`
`0
`
`0
`
`3
`
`3
`0 3
`
`1
`
`1
`
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`
`2 13
`2
`— 12
`3
`5
`- 0 12
`4 13 1
`1
`2
`1
`2
`6 12
`2 1 —
`2
`- 3 13
`0
`3
`7
`0 3 —
`—
`8 10
`4
`8 —
`4
`7
`8
`11
`9
`9
`5
`5
`
`3
`
`2
`
`13
`
`12
`
`12
`12
`
`12
`
`9
`0 12
`- 12
`0 —
`8 1 13
`13
`13 1 —
`10
`13
`2 —
`0
`3 1 11
`0 —
`12
`1 13
`13
`
`13
`
`10
`
`11
`
`6
`
`9
`
`15
`
`with the present invention. As shown in this figure, node 0
`FIG. 13 depicts a network topology for a network of 15
`has a partner link with node 1 and directly connects to nodes
`nodes in accordance with methods and systems consistent
`4, 6, 8, and 11. Node 1 has a partner link with node 0 and
`with the present invention. As shown in FIG. 13, node 0 has
`a partner link with node 1 and directly connects to nodes 4,
`directly connects to nodes 5, 7, 9, and 10. Node 2 has a
`6, 8, and 11. Node 1 has a part