Fault-tolerant communication channel structures

• US 7,020,076 B1
• Filed: 10/26/2000
• Issued: 03/28/2006
• Est. Priority Date: 10/26/1999
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Alkalai, Leon, Chau, Savio N., Tai, Ann T.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Sefcheck, Gregory
• Application Number:
  US09/698,514
• Time in Patent Office: 1,979 Days
• Field of Search: 370216-217, 370220-228, 714/43, 710/100, 710/305
• US Class Current: 370/217
• CPC Class Codes: H04L 1/22 using redundant apparatus to increase reliability

Abstract

Systems and techniques for implementing fault-tolerant communication channels and features in communication systems. Selected commercial-off-the-shelf devices can be integrated in such systems to reduce the cost.

Claims

1. A system, comprising:

a plurality of node devices, each operable to transmit or receive information; and

a first set of composite communication links to connect said node devices to form a communication network, each composite communication link having at least a communication channel of a first type and a communication channel of a different, second type, communication channels of said first type connected to said nodes to form a first network in a first topology and communication channels of said second type connected to said nodes to form a second network in a second, different topology,

wherein at least one of said first and said second networks is not partitioned when a single node failure occurs

wherein a node having a node position in said first network has a different node position in said second network,

wherein each of said first and said second topologies is a tree topology, and wherein a branch node in said first network is not a branch node in said second network.

2. The system as in claim 1, wherein communication channels of said first type include IEEE 1394 buses.

3. The system as in claim 1, wherein communication channels of said second type include I2C buses.

4. A system, comprising:

a plurality of digital electronic node devices which include at least one computer;

a first set of buses of a first type to connect each and every of said node devices to form a first network with a first topology;

a second set of buses of a different, second type to connect each and every of said node devices to form a second network with a second topology which is different from said first topology,

wherein said first and said second topologies are selected to be complementary to each other so that a single-point failure causing a partition in one of said first and said second network does not cause a partition in another of said first and said second network,

wherein said first topology includes a tree topology and said second topology includes a multi-drop serial topology, wherein each node device has three ports designated for connections to other node devices in said tree topology,

wherein said tree topology includes n branch nodes in which each of a first branch node 1 and a nth branch node n is connected to only two other nodes, and each branch node in said tree topology is connected to (1) at most three other nodes among which at most two nodes are branch nodes and (2) at least one leaf node; and

a plurality of backup buses of said first type which are connected to selected nodes in said tree topology and are not activated in absence of a failure, wherein a backup link is connected between said branch nodes 1 and n and a backup link is connected between any two leaf nodes i and j which satisfy |(i mod n)−

(j mod n)|=1.

5. A system, comprising:

a plurality of digital electronic node devices which include at least one computer;

a first set of buses of a first type to connect each and every of said node devices to form a first network with a first topology;

a second set of buses of a different, second type to connect each and every of said node devices to form a second network with a second topology which is different from said first topology, wherein said first and said second topologies are selected to be complementary to each other so that a single-point failure causing a partition in one of said first and said second network does not cause a partition in another of said first and said second network;

a third set of buses of said first type to connect each and every of said node devices to form a third network with a third topology; and

a fourth set of buses of said second type to connect each and every of said node devices to form a fourth network with a fourth topology which is different from said third topology,

wherein said third and fourth networks are operable to back up said first and said second networks, wherein each of said first and said third topologies is a tree topology, and where a branch node for one tree topology is not a branch node for another tree topology.

6. A method, comprising:

connecting node devices by a first set of communication links of a first type to form a first tree topology;

connecting said node devices by a second set of communication links of said first type to form a second tree topology, wherein a branch node in said first tree topology is not a branch node in said second tree topology;

connecting said node devices by a third set of communication links of a second type to form a first multi-drop serial topology;

connecting said node device by a fourth set of communication links of said second type to form a second multi-drop serial topology;

operating said first and said third sets of communication links to detect and bypass a failure location; and

operating said second and said fourth sets of communication links to back up said first and said third sets of communication links.

7. The method as in claim 6, wherein an IEEE 1394 bus is used for each communication link of said first type and an I2C bus is used for each communication link of said second type.