Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Decentralized controlling
Reexamination Certificate
2000-01-13
2003-11-18
Wiley, David (Department: 2143)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Decentralized controlling
C709S230000, C709S238000
Reexamination Certificate
active
06651106
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to communication methods and topologies. More specifically the invention relates to a circuit and protocol useful in propagating information through a mesh topology in a reliable manner for real-time applications.
2. Description of the Related Art
In order to communicate electronic information from one point to another, that information must be passed from the transmitting point to the receiving point along some connecting medium. In a telegraph, for example, an electric circuit is opened and closed in a predictable and understandable manner so that signals generated on one end of the line are received and understood at the other. This works extremely well when there is only one transmitting point and one receiving point. Problems begin to occur if both points are capable of transmitting along the same wire. If both points happen to generate signals at both ends of the wire, indiscernible noise is produced and neither side can understand the other's message. Consequently, a probability problem exists in that the system will work fine when only one end is transmitting and will collapse when both sides happen to transmit at the same time.
To increase the usefulness of the system, it is helpful to have multiple stations along an interconnected single line, spanning some great distance. In this configuration, there would be many stations having access to the communication network. Despite the obvious benefit of multiple stations accessing the network, the probability of any two stations transmitting at the same time is greatly increased. As discussed above, this creates the risk of any particular message not being received.
While telegraphs certainly are not relied on to communicate information today, many modern electronic devices suffer from the same problems as described above. For instance, different components in a personal computer must communicate with each other as well as a CPU. On a larger scale, a plurality of computers may wish to communicate with each other on an intranet or even the Internet. The problem is the same in each instance; how can interconnected electronic components communicate over a shared medium?
Many types of solutions have been used in the past to solve this communication problem.
FIG. 2
illustrates one previous solution well known as a “bus” topography. Each Node N in network
100
is connected to the bus
10
. When any Node N sends a message, its is rapidly received by all of the other nodes N by traveling along bus
10
. Whichever Node N the message was intended for will likewise receive the message and process the information. There are three distinct problems with this type of topology. First, as in the telegraph example, multiple nodes N may wish to transmit at the same time. Second, if the link between any pair of nodes N is severed, the entire system is at least severely impaired and possibly totally disabled. Third, in real world applications the configuration of the nodes N is not likely to be positioned linearly as schematically illustrated.
To deal with the first problem, a media access control (MAC) protocol is needed which allows only one node to be transmit and at given time. One such protocol is known as Table Driven Proportional Access (TDPA), as shown in FIG.
11
. With this protocol, each Node N has an identical table
20
. The tables
20
will designate which particular Node N will be able to transmit at any given time. In the example presented, there are four nodes, numbered
1
-
4
. Each Node N has a node indication pointer
30
which steps through the table sequentially and indicates to all of the nodes N concurrently, which Node N is designated to transmit. In
FIG. 11
, the pointer
30
indicates that node
3
is able to transmit. At this point, all other nodes N will “listen” for a message which may or may not be transmitted by node
3
. After the message has been transmitted or after the time that would have been taken to transmit a message if no message is transmitted, the pointer
30
advances to the next index identifier which happens to indicate that node
1
will be free to transmit. The pointer advances through the table, and when the end is reached, it is reset to the beginning. In this manner, each Node N knows when to “speak” and when to “listen”, thus avoiding the problem of two nodes N simultaneously attempting to transmit at the same time.
TDPA is a commercially accepted and known protocol, however there are a wide variety of other protocols which may be used with a standard bus. In some of those protocols, such as CSMA, multiple nodes N could transmit at the same time. When this occurs, the two signals will “crash” into one another. The system will then recognize this collision and each Node N will attempt to resend its respective message. To avoid colliding again, the two nodes independently select random delay times (which are highly likely to be different from one another) and wait for that period of time before resending. Probability suggests that the two messages will most likely eventually each be sent, though subsequent collisions are possible (thus causing each node to again select a random delay time and restart the process). There is a finite probability, however, that repeated collisions could continue to occur, prohibiting the transmission of the data. When using this protocol, the collision could occur at any given point along the bus. Thus, one or more nodes N may have received one of the messages prior to the collision and would therefore not recognize that there was a collision. Ultimately, when the message is resent, those nodes N would interpret the message as a new one, not a repeat of the old. To avoid this and to prevent collision “debris” from being misinterpreted as a valid message, when a collision occurs, each node detecting the collision immediately transmits a jam signal to the remaining nodes to ensure they detect that a collision has occurred. This protocol has a probability (but not certainty) that it will eventually get information to its proper destination, but it is inherently slow and easy to bog down.
The second major problem with the use of a data bus occurs when a link
150
between a pair of nodes N is severed or a particular node malfunctions (emitting spurious information). In this condition, the entire system is impaired. This malfunction could occur in either the connection between Node N and the bus or along the bus between the individual nodes N.
FIG. 5
shows a bus
10
having four nodes N
1
-N
4
. As illustrated by the X through the bus
10
, the link between N
3
and N
4
has been severed. This could completely shut down the system. Signal reflections from the severed ends can cause even the intact connections between nodes to not function correctly.
To prevent a catastrophic failure caused by the severing of a connection, redundant bus line
10
′ may be added. In summary, 100% of the existing bus line is duplicated to achieve one level of redundancy (can survive one detected failure).
FIG. 8
shows how three buses may be used to achieve two levels of redundancy. Obviously, this method of protection requires an excessive amount of cabling, thus increasing the cost and complexity of the system.
Returning to
FIG. 5
, a second potential problem is depicted in which there is a problem with the node itself (see N
2
crossed out). The node may be generating random or spurious signals thus producing noise on both the bus
10
and
10
′. Such a malfunctioning node can also cause a change in the impedance of the connective media. When this occurs, the node is known as a babbling node. Thus, no matter the level of redundancy achieved, a single babbling node could shut down the entire system.
The third major problem with the use of a data bus is the physical parameters of the interconnecting cable. As shown in
FIG. 13
, the various nodes N are seldom linearly located, hence interconnecting cables, or links
150
, of different lengths must be utilized. Due to th
Avellino Joseph E
Wiley David
LandOfFree
Flooding communication using an access table to establish... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flooding communication using an access table to establish..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flooding communication using an access table to establish... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3152792