Network topologies

• US 6,584,073 B1
• Filed: 06/02/1999
• Issued: 06/24/2003
• Est. Priority Date: 06/02/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wade, Jon, Steele, Guy L. Jr., Heller, Steven K.
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US09/323,963
• Time in Patent Office: 1,483 Days
• Field of Search: 370/254, 370/255, 370/257, 370/258, 370/406, 370/407
• US Class Current: 370/254
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867

Abstract

In accordance with methods and systems consistent with the present invention, a number of improved network topologies are provided that have been selected to improve network performance based on various performance characteristics. The topologies are also selected to facilitate network reconfiguration, including adding nodes and removing, nodes. As a result, the network topologies in accordance with methods and systems consistent with the present invention do not follow a rigid, predefined pattern; rather, these topologies have been selected for network performance purposes as well as reconfiguration purposes.

Claims

1. A distributed system comprising at least seven nodes in a network that is not fully connected, the nodes including a node 0, a node 1, a node 2, a node 3, a node 4, a node 5, and a node 6, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 3, node 4, node 5, and node 6;

node 1 is communicatively linked to node 0, node 2, node 3, node 4, and node 5;

node 2 is communicatively linked to node 1, node 3, node 4, node 5, and node 6;

node 3 is communicatively linked to node 0, node 1, node 2, node 5, and node 6;

node 4 is communicatively linked to node 0, node 1, node 2, node 5, and node 6;

node 5 is communicatively linked to node 0, node 1, node 2, node 3, and node 4; and

node 6 is communicatively linked to node 0, node 2, node 3, and node 4.

2. The distributed system of claim 1 wherein each of the nodes has five ports.

3. The distributed system of claim 1 wherein node 0 and node 1 communicate via a bus.

4. The distributed system of claim 1 wherein node 2 and node 3 communicate via a bus.

5. The distributed system of claim 1 wherein node 4 and node 5 communicate via a bus.

6. A distributed system comprising at least eight nodes in a network that is not fully connected, the nodes including anode 0, a node 1, a node 2, a node 3, a node 4, a node 5, a node 6, and a node 7, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 3, node 4, node 5, and node 6;

node 1 is communicatively linked to node 0, node 2, node 4, node 5, and node 7;

node 2 is communicatively linked to node 1, node 3, node 4, node 6, and node 7;

node 3 is communicatively linked to node 0, node 2, node 5, node 6, and node 7;

node 4 is communicatively linked to node 0, node 1, node 2, node 5, and node 6;

node 5 is communicatively linked to node 0, node 2, node 3, node 4, and node 7;

node 6 is communicatively linked to node 0, node 2, node 3, node 4, and node 7; and

node 7 is communicatively linked to node 1, node 2, node 3, node 5, and node 6.

7. The distributed system of claim 6 wherein each of the nodes has five ports.

8. The distributed system of claim 6 wherein node 0 and node 1 communicate via a bus.

9. The distributed system of claim 6 wherein node 2 and node 3 communicate via a bus.

10. The distributed system of claim 6 wherein node 4 and node 5 communicate via a bus.

11. The distributed system of claim 6 wherein node 6 and node 7 communicate via a bus.

12. A distributed system comprising at least nine nodes in a network that is not fully connected, the nodes including a node 0, a node 1, a node 2, a node 3, a node 4, a node 5, a node 6, a node 7, and a node 8, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 3, node 4, node 6, and node 8;

node 1 is communicatively linked to node 0, node 2, node 4, node 5, and node 7;

node 2 is communicatively linked to node 1, node 3, node 4, node 6, and node 7;

node 3 is communicatively linked to node 0, node 2, node 5, node 7, and node 8;

node 4 is communicatively linked to node 0, node 1, node 2, node 5, and node 6;

node 5 is communicatively linked to node 1, node 3, node 4, node 7, and node 8;

node 6 is communicatively linked to node 0, node 2, node 4, node 7, and node 8;

node 7 is communicatively linked to node 1, node 2, node 3, node 5, and node 6;

node 8 is communicatively linked to node 0, node 3, node 5, and node 6.

13. The distributed system of claim 12 wherein each of the nodes has five ports.

14. The distributed system of claim 12 wherein node 0 and node 1 are partner nodes.

15. The distributed system of claim 12 wherein node 2 and node 3 are partner nodes.

16. The distributed system of claim 12 wherein node 4 and node 5 are partner nodes.

17. The distributed system of claim 12 wherein node 6 and node 7 are partner nodes.

18. A distributed system comprising at least ten nodes in a network that is not fully connected, the nodes including a node 0, a node 1, a node 2, a node 3, a node 4, a node 5, a node 6, a node 7, a node 8, and a node 9, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 3, node 4, node 6, and node 8;

node 1 is communicatively linked to node 0, node 2, node 5, node 7, and node 9;

node 2 is communicatively linked to node 1, node 3, node 4, node 6, and node 9;

node 3 is communicatively linked to node 0, node 2, node 5, node 7, and node 8;

node 4 is communicatively linked to node 0, node 2, node 5, node 6, and node 9;

node 5 is communicatively linked to node 1, node 3, node 4, node 7, and node 8;

node 6 is communicatively linked to node 0, node 2, node 4, node 7, and node 8;

node 7 is communicatively linked to node 1, node 3, node 5, node 6, and node 9;

node 8 is communicatively linked to node 0, node 3, node 5, node 6, and node 9; and

node 9 is communicatively linked to node 1, node 2, node 4, node 7, and node 8.

19. The distributed system of claim 18 wherein each of the nodes has five ports.

20. The distributed system of claim 18 wherein node 0 and node 1 are partner nodes.

21. The distributed system of claim 18 wherein node 2 and node 3 are partner nodes.

22. The distributed system of claim 18 wherein node 4 and node 5 are partner nodes.

23. The distributed system of claim 18 wherein node 6 and node 7 are partner nodes.

24. The distributed system of claim 18 wherein node 8 and node 9 are partner nodes.

25. A distributed system comprising at least eleven nodes, in a network that is not fully connected, the nodes including a node 0, a node, 1, a node 2, a node 3, a node 4, a node 5, a node 6, a node 7, a node 8, a node 9, and a node 10, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 3, node 4, node 6, and node 8;

node 1 is communicatively linked to node 0, node 5, node 7, node 9, and node 10;

node 2 is communicatively linked to node 3, node 4, node 6, node 9, and node 10;

node 3 is communicatively linked to node 0, node 2, node 5, node 7, and node 8;

node 4 is communicatively linked to node 0, node 2, node 5, node 7, and node 9;

node 5 is communicatively linked to node 1, node 3, node 4, node 8, and node 10;

node 6 is communicatively linked to node 0, node 2, node 7, node 8, and node 10;

node 7 is communicatively linked to node 1, node 3, node 4, node 6, and node 9;

node 8 is communicatively linked to node 0, node 3, node 5, node 6, and node 9;

node 9 is communicatively linked to node 1, node 2, node 4, node 7, and node 8; and

node 10 is communicatively linked to node 1, node 2, node 5, and node 6.

26. The distributed system of claim 25 wherein each of the nodes has five ports.

27. The distributed system of claim 25 wherein node 0 and node 1 communicate via a bus.

28. The distributed system of claim 25 wherein node 2 and node 3 communicate via a bus.

29. The distributed system of claim 25 wherein node 4 and node 5 communicate via a bus.

30. The distributed system of claim 25 wherein node 6 and node 7 communicate via a bus.

31. The distributed system of claim 25 wherein node 8 and node 9 communicate via a bus.

32. A distributed system comprising at least twelve nodes in a network that is not fully connected the nodes including a node 0, a node 1, a node 2, a node 3, a node 4, a node 5, a node 6, a node 7, a node 8, a node 9, a node 10, and a node 11, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 4, node 6, node 8, and node 11;

node 1 is communicatively linked to node 1, node 5, node 7, node 9, and node 10;

node 2 is communicatively linked to node 3, node 4, node 6, node 9, and node 10;

node 3 is communicatively linked to node 2, node 5, node 7, node 8, and node 11;

node 4 is communicatively linked to node 0, node 2, node 5, node 9, and node 11;

node 5 is communicatively linked to node 1, node 3, node 4, node 8, and node 10;

node 6 is communicatively linked to node 0, node 2, node 7, node 8, and node 10;

node 7 is communicatively linked to node 1, node 3, node 6, node 9, and node 11;

node 8 is communicatively linked to node 0, node 3, node 5, node 6, and node 9;

node 9 is communicatively linked to node 1, node 2, node 4, node 7, and node 8;

node 10 is communicatively linked to node 1, node 2, node 5, node 6, and node 11; and

node 11 is communicatively linked to node 0, node 3, node 4, node 7, and node 10.

33. The distributed system of claim 32 wherein each of the nodes has five ports.

34. The distributed system of claim 32 wherein node 0 and node 1 communicate via a bus.

35. The distributed system of claim 32 wherein node 2 and node 3 communicate via a bus.

36. The distributed system of claim 32 wherein node 4 and node 5 communicate via a bus.

37. The distributed system of claim 32 wherein node 6 and node 7 communicate via a bus.

38. The distributed system of claim 32 wherein node 8 and node 9 communicate via a bus.

39. The distributed system of claim 32 wherein node 10 and node 11 communicate via a bus.

40. A distributed system comprising at least thirteen nodes in a network that is not fully connected, the nodes including a node 0, a node 1, anode 2, a node 3, a node 4, a node 5, a node 6, a node 7, a node 8, a node 9, a node 10, a node 11, and a node 12, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 4, node 6, node 8, and node 11;

node 1 is communicatively linked to node 0, node 5, node 7, node 9, and node 10;

node 2 is communicatively linked to node 3, node 4, node 6, node 9, and node 10;

node 3 is communicatively linked to node 2, node 5, node 7, node 8, and node 11;

node 4 is communicatively linked to node 0, node 2, node 5, node 9, and node 12;

node 5 is communicatively linked to node 1, node 3, node 4, node 6, and node 8;

node 6 is communicatively linked to node 0, node 2, node 5, node 7, and node 10;

node 7 is communicatively linked to node 1, node 3, node 6, node 11, and node 12;

node 8 is communicatively linked to node 0, node 3, node 5, node 9, and node 12;

node 9 is communicatively linked to node 1, node 2, node 4, node 8, and node 11;

node 10 is communicatively linked to node 1, node 2, node 6, node 11, and node 12;

node 11 is communicatively linked to node 0, node 3, node 7, node 9, and node 10; and

node 12 is communicatively linked to node 4, node 7, node 8, and node 10.

41. The distributed system of claim 40 wherein each of the nodes has five ports.

42. The distributed system of claim 40 wherein node 0 and node 1 communicate via a bus.

43. The distributed system of claim 40 wherein node 2 and node 3 communicate via a bus.

44. The distributed system of claim 40 wherein node 4 and node 5 communicate via a bus.

45. The distributed system of claim 40 wherein node 6 and node 7 communicate via a bus.

46. The distributed system of claim 40 wherein node 8 and node 9 communicate via a bus.

47. The distributed system of claim 40 wherein node 10 and node 11 communicate via a bus.

48. A distributed system comprising at least fourteen nodes in a network that is not fully connected, the nodes including a node 0, a node 1, a node 2, a node 3, a node 4, a node 5, a node 6, a node 7, a node 8, a node 9, a node 10, a node 11, a node 12, and a node 13, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 4, node 6, node 8, and 11;

node 1 is communicatively linked to node 0, node 5, node 7, node 9, and node 10;

node 2 is communicatively linked to node 3, node 4, node 6, node 9, and node 10;

node 3 is communicatively linked to node 2, node 5, node 7, node 8, and node 11;

node 4 is communicatively linked to node 0, node 2, node 5, node 9, and node 12;

node 5 is communicatively linked to node 1, node 3, node 4, node 8, and node 13;

node 6 is communicatively linked to node 0, node 2, node 7, node 10, and node 13;

node 7 is communicatively linked to node 1, node 3, node 6, node 11, and node 12;

node 8 is communicatively linked to node 0, node 3, node 5, node 9, and node 12;

node 9 is communicatively linked to node 1, node 2, node 4, node 8, and node 13;

node 10 is communicatively linked to node 1, node 2, node 6, node 11, and node 12;

node 11 is communicatively linked to node 0, node 3, node 7, node 10, and node 13;

node 12 is communicatively linked to node 4, node 7, node 8, node 10, and node 13; and

node 13 is communicatively linked to node 5, node 6, node 9, node 11, and node 12.

49. The distributed system of claim 48 wherein each of the nodes has five ports.

50. The distributed system of claim 48 wherein node 0 and node 1 are partner nodes.

51. The distributed system of claim 48 wherein node 2 and node 3 are partner nodes.

52. The distributed system of claim 48 wherein node 4 and node 5 are partner nodes.

53. The distributed system of claim 48 wherein node 6 and node 7 ate partner nodes.

54. The distributed system of claim 48 wherein node 8 and node 9 are partner nodes.

55. The distributed system of claim 48 wherein node 10 and node 11 are partner nodes.

56. The distributed system of claim 48 wherein node 12 and node 13 are partner nodes.

57. A distributed system comprising at least fifteen nodes in a network that is not fully connected, the nodes including a node 0, a node 1, a node 2, a node 3, a node 4, a node 5, a node 6, a node 7, a node 8, a node 9, a node 10, a node 11, a node 12, a node 13, and a node 14, the nodes being communicatively linked as follows:

node 0 is communicatively linked to node 1, node 4, node 6, node 8, and node 11;

node 1 is communicatively linked to node 0, node 5, node 7, node 9, and node 10;

node 2 is communicatively linked to node 3, node 4, node 6, node 9, and node 10;

node 3 is communicatively linked to node 2, node 5, node 7, node 8, and node 11;

node 4 is communicatively linked to node 0, node 2, node 5, node 9, and node 12;

node 5 is communicatively linked to node 1, node 3, node 4, node 13, and node 14;

node 6 is communicatively linked to node 0, node 2, node 7, node 13, and node 14;

node 7 is communicatively linked to node 1, node 3, node 6, node 11, and node 12;

node 8 is communicatively linked to node 0, node 3, node 9, node 12, and node 14;

node 9 is communicatively linked to node 1, node 2, node 4, node 8, and node 13;

node 10 is communicatively linked to node 1, node 2, node 11, node 12, and node 14;

node 11 is communicatively linked to node 0, node 3, node 7, node 10, and node 13;

node 12 is communicatively linked to node 4, node 7, node 8, node 10, and node 13;

node 13 is communicatively linked to node 5, node 6, node 9, node 11, and node 12; and

node 14 is communicatively linked to node 5, node 6, node 8, and node 10.

58. The distributed system of claim 57 wherein each of the nodes has five ports.

59. The distributed system of claim 57 wherein node 0 and node 1 are partner nodes.

60. The distributed system of claim 57 wherein node 2 and node 3 are partner nodes.

61. The distributed system of claim 57 wherein node 4 and node 5 are partner nodes.

62. The distributed system of claim 57 wherein node 6 and node 7 are partner nodes.

63. The distributed system of claim 57 wherein node 8 and node 9 are partner nodes.

64. The distributed system of claim 57 wherein node 10 and node 11 are partner nodes.

65. The distributed system of claim 57 wherein node 12 and node 13 are partner nodes.

66. A method for distributed system configuration, comprising the steps of:

creating a set of network topologies, each associated with one group of nodes, each group having a different number of nodes, each network topology configured based on performance characteristics, wherein each of the set of network topologies does not fully connect the associated group of nodes;

selecting one of the set of network topologies for a network with network nodes based on a number of the network nodes in the network; and

configuring the network using the selected network topology.

67. The method of claim 66 wherein each of the set of network topologies is configured based on a diameter of the network topology.

68. The method of claim 66 wherein each of the set of network topologies is configured based on a bisection bandwidth of the network topology.

69. The method of claim 66 wherein each of the set of network topologies is configured based on whether the network topology is symmetric.

70. The method of claim 69 wherein each of the set of network topologies is configured based on whether the network topology is node symmetric.

71. The method of claim 69 wherein each of the set of network topologies is configured based on whether the network topology is edge symmetric.

72. The method of claim 66 wherein each of the set of network topologies is configured based on an average path length of the network topology.

73. The method of claim 66 wherein the number of nodes in each group form a sequence.

74. The method of claim 73 wherein the sequence begins at seven nodes and ends at sixteen nodes.

75. A method for distributed system configuration, comprising the steps of:

creating a set of network topologies, each associated with one group of nodes, each group having a different number of nodes, each network topology configured to facilitate reconfiguration of the associated group, wherein each of the set of network topologies does not fully connect the associated group of nodes;

selecting one of the set of network topologies for a network with network nodes based on a number of the network nodes in the network; and

configuring the network using the selected topology.

76. The method of claim 75 wherein each network topology is configured to facilitate upgrading the network.

77. The method of claim 75 wherein each network topology is configured to facilitate downgrading the network.

78. The method of claim 75 wherein the number of nodes in each group form a sequence.

79. The method of claim 78, wherein the sequence starts at seven nodes and ends at sixteen nodes.

80. A method for distributed system configuration, comprising the steps of:

creating a set of network topologies, each associated with one group of nodes, each group having a different number of nodes, each network topology configured based on performance characteristics, wherein each of the set of network topologies does not fully connect the associated group of nodes;

selecting one of the set of network topologies for a network with network nodes based on a number of the network nodes in the network; and

configuring the network using the selected network topology, wherein each of the set of network topologies is configured based on one of a diameter of the network topology, a bisection bandwidth of the network topology, an average path length of the network topology, and whether the network topology is symmetric.

81. A method for distributed system configuration, comprising the steps of:

creating a set of network topologies, each associated with one group of nodes, each group having a different number of nodes that form a sequence, each network topology configured based on performance characteristics, wherein each of the set of network topologies does not fully connect the associated group of nodes;

selecting one of the set of network topologies for a network with network nodes based on a number of the network nodes in the network; and

configuring the network using the selected network topology.

82. A method for distributed system configuration, comprising the steps of:

creating a set of network topologies, each associated with one group of nodes, each group having a different number of nodes that form a sequence, each network topology configured to facilitate reconfiguration of the associated group, wherein each of the set of network topologies does not fully connect the associated group of nodes;

selecting one of the set of network topologies for a network with network nodes based on a number of the network nodes in the network; and

configuring the network using the selected topology.