1. Field of the Invention
The present invention relates to a method and apparatus for preventing access collisions for a plurality of nodes in a network, and more particularly, to a method and apparatus for avoiding access collisions for a plurality of nodes in a network in which a plurality of access types are present by using multiple paths.
2. Description of the Related Art
In a network that has a plurality of nodes, there may be two or more nodes trying to send messages to one or more other nodes on the same network at the same time. There are many examples of such a scenario, but perhaps the most well-known is the so-called "deadlock" condition, in which two or more processors try to change the contents of the same resource.
In such a situation, two nodes are trying to communicate but are unable to do so because they are sending messages simultaneously. This problem may be mitigated by introducing an arbiter, a node that examines messages as they arrive and sends an "acknowledgment" back to the source nodes, but in the case of nodes that may operate for extended periods of time without human intervention, such a measure is prohibitively expensive.
One method of solving this problem is to add an additional communication channel to the network. By using a separate channel, a sender can inform a receiver that it has begun sending a message, and the receiver can wait until it is finished before responding. If two or more nodes are trying to send messages simultaneously, they may still be able to do so because they are using different channels.
One method for increasing the likelihood that this solution will work is to assign different communication channels to different types of messages. For instance, in a multicast environment, two or more nodes will generally be sending messages, but the messages may be different types of messages: either one-to-many, or many-to-many. In such a case, an additional communication channel may be assigned to each different type of message. This results in the following: for example, if one type of message uses the first communication channel and another type uses the second, the chance that both types will be on the first channel at the same time is reduced to 1/2.
One drawback to this method is that the number of channels required increases as the number of message types increases. This can become unmanageable, especially in a large-scale network. For instance, if there are 1000 different types of messages to be sent between 100 nodes, there are 1000 different channels that must be set up.
One type of mechanism that has been developed in response to this problem is a multicast router. The function of a multicast router is to listen to a plurality of messages from a plurality of nodes, examine the types of messages and determine which communication channels will be required for each type of message. However, current methods for dealing with communication channel problems are insufficient for use in a large-scale distributed environment. The reason for this is that, in order to manage the communications of the nodes, the different nodes must be connected to the common network in such a way as to make it possible for each node to detect any node in the network with which it has communicated or will be communicating. As will be shown, in some circumstances it is impossible to do this.
As used herein, a "node" is a logical entity, a computer or processor or other device that is capable of executing software and acting as a source of data or control information. As will be shown, it is impossible for two nodes to discover all of the other nodes with which they have communicated or will be communicating.
A "network" is a distributed collection of nodes connected by physical or logical links. A "data packet" is any piece of data that may be transmitted through a network. When a data packet is transmitted, it will include the address of the source node and a destination node and some type of data. As used herein, the type of data that is being sent will be referred to as the "data packet payload".
"Broadcasting" refers to the process of sending a packet that is addressed to a number of nodes at the same time.
"Multicasting" refers to sending a packet that is addressed to a subset of nodes, where the subset comprises all nodes on a given communication channel. For instance, if a packet is addressed to any node on Channel 1, it will be transmitted to all nodes on Channel 1.
As will be shown, it is impossible for a node in the network to determine which nodes are on a given communication channel. Therefore, the multicast router must be able to determine from the source node which nodes are being addressed. This presents a problem when all the nodes that are to be addressed are on different communication channels.
One type of network architecture is the ring topology. A ring network consists of a sequence of nodes interconnected by communication links that form a closed loop. A complete set of nodes on such a network may be denoted as {0, 1, . . . , N-1}, where N is the number of nodes in the network. A node i on the ring network is connected to node i+1 and node i-1 by links. A ring network works very much like a circle or a one-dimensional line, and in general may be either synchronous or asynchronous. An example of a synchronous ring is the IEEE 802.5 Token Ring, and an example of an asynchronous ring is the IEEE 802.4 Carrier Sense Multiple Access/Collision Detection (CSMA/CD) Local Area Network (LAN) Standard.
In FIG. 1, there are seven nodes numbered 0-6. Note that the source and destination nodes (i.e., node 0, node 4, node 5 and node 6, node 2 and node 3) do not need to be on the same ring as other nodes.
FIG. 2 shows a more complex example. In this example there are four nodes numbered 0, 1, 2 and 3, with nodes 1, 2 and 3 on different communication channels (i.e., channels #0, #1 and #2 respectively). Nodes 0 and 4 are connected to node 1 on the same channel, and node 5 is connected to node 2 on the same channel. Nodes 3 and 6 are connected to node 2 on the same channel, and node 5 is connected to node 3 on the same channel.
In order to solve the problem of broadcasting and multicasting for node 5, it is necessary for it to determine whether node 0 is sending a packet to all nodes 1, 2 and 3 on the channel #0. This is impossible because nodes 1 and 2 are only connected to node 0 on channels #1 and #2, so node 0 will not be able to determine that there is a collision on channel #0.
An example of an application of this problem is the so-called "busy tone" problem. This involves a user in a telephone network that receives telephone service through the PSTN. The service provider may have many services available, such as a message waiting service, a call transfer service, a call hold service, etc. The user may wish to subscribe to all of these services, but cannot do so simultaneously. This is because the "network" of the user is the PSTN, and each of the above-listed services may require a separate channel on the PSTN.
When the service provider is ready to send a packet on a given channel, that channel is said to be "up". When a node attempts to send a packet on a given channel, that channel is said to be "up". A given channel can only be up if there are no other nodes attempting to send packets on that channel at the same time. To send a packet on a channel requires two conditions: (1) the node must determine that the channel is available, and (2) it must obtain permission to send the packet. To obtain permission, a node must send a message to a master node in the network. The master node allocates the communication channels among the nodes.
The above description is provided for the sake of clarity. However, as far as the present invention is concerned, the invention may be implemented on any type of channel, synchronous or asynchronous, point-to-point or multi-point. It is thus possible for the nodes to be connected by a bus or a ring. The only requirement is that the channel be point-to-point. The nodes may be arranged in any desired pattern, such as a ring or a line.
One possible solution to this problem would be to dedicate a channel for each type of packet, either on a per-node basis or on a per-communication-channel basis. This would require channels with the same physical address in different networks to be distinguished from each other. This is not possible with the current protocol. Thus, there is a need for a method of determining whether it is safe to transmit a packet on a given channel without relying on the physical addresses.
In order to solve this problem, the present invention provides a method and apparatus for sending and receiving messages by a plurality of nodes in a network in which a
