JPS6348462B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a method for resolving packet collisions that occur when multiple nodes transmit on the local network almost simultaneously based on the contention method. .

In conventional packet collision resolution methods, after a collision occurs,
Each node that caused a collision generates an independent random number, stops transmitting for a certain period of time according to the random number, and
Probabilistic collision avoidance is performed by transmitting again after that. (For example, R. Metcalfe and D.
Boggs “Ethernet; Distributed Packet
Switching for Local Computer Network”
Communications of the ACM, July1976
vol 19, No. 7 p 395/404) This resulted in disadvantages such as long transmission waiting times, reduced throughput due to collisions caused by retransmissions during high loads, and no guarantee that communication could be completed within a finite amount of time.

In order to solve these drawbacks, the present invention solves the conflict by sequentially transferring the transmission right from one end of the conflicting node to the other end after the conflict occurs, and will be described in detail below with reference to the drawings.

FIG. 1 shows an embodiment of the present invention, in which 1 is a transmission line using optical fiber, 2-1 to 2-3 are coupling devices, and 3-1 to 3-3 are a processor, terminal equipment, etc. The nodes 4-1 and 4-2 are terminal devices. FIG. 2 is a conceptual diagram showing the flow of optical signals in the coupling device. 1 is a transmission line, 2 is a branch concentrator, 5-1 is a waveguide for receiving signals transmitted from the left, 5-2 is a waveguide for receiving signals from the right, and 6-1 is a waveguide for receiving signals from the right. Waveguide for signal transmission, 6
-2 is a waveguide for signal transmission to the left. Waveguides 6-1, 6-2 for signal transmission and signal reception,
By connecting an optical transmitter and an optical receiver to each of nodes 5-1 and 5-2, each node (3 in FIG.
-1 to 3-3) is the direction identification of the received signal (identification of which direction the above received signal was received from, that is, the originating node is on either side of the own node)
When transmitting, it is possible to transmit in only one direction or in both directions.

Communication between nodes is carried out through two phases: (i) competition phase and (ii) resolution phase. Each node constantly monitors the signal on the transmission line 1 and operates according to the current phase. The operation for each phase will be explained below. Note that the initial state is the competition phase.

(i) Operation in contention phase A node that wants to transmit a packet monitors the signal on transmission path 1, and transmits the packet when no other node is communicating (when there is no signal on transmission path 1). If another node is transmitting, the packet is transmitted after waiting until the transmission is completed. Packets are sent in both directions. While the own node is transmitting packets, it receives signals on the transmission path and monitors the occurrence of collisions. In the coupling device having the configuration shown in FIG. 2, since the node itself does not receive the packet it is transmitting, it can be determined that a collision has occurred if the packet is received during transmission. Note that if the shortest packet length is chosen to allow a node to continue transmitting packets for a longer time than the time required for the optical signal to travel back and forth between the nodes at both ends, collisions will always be detected during packet transmission. . If a collision is detected during transmission, the packet being transmitted is discarded as an abnormal packet, and other nodes take measures such as making the packet length shorter than the shortest packet length, sending an incorrect CRC code, etc. After taking the following steps, the solution phase begins. Other nodes also enter the resolution phase after receiving the above invalid collision packet.

(ii) Operations during the resolution phase Figure 3 shows the operations of the node that caused the conflict during the resolution phase. For simplicity, nodes that did not cause a collision are omitted from the diagram. 1 is a transmission line, 2-1 to 2-
3 is a coupling device, and 3-1 to 3-3 are nodes that have caused a collision. 7 is a packet sent by node 3-1 and is sent in both directions. 8 is a reservation signal sent by the node 3-2 and is sent only to the right. 9 is a reservation signal sent from node 3-3 and is sent only to the right. 10 is a packet transmitted by node 3-2, which is transmitted in both directions. 11 is a reservation signal sent from node 3-3 and is sent only to the right. 12
is a packet sent by node 3-3 and is sent in both directions.

The operation is as follows. When a collision occurs, node 3-1 receives collision packets from nodes 3-2 and 3-3 from the right side, but does not receive anything from the left side. Node 3-3 is node 3- from the left.
Collision packets 1 and 3-2 are received, but nothing is received from the right side. Therefore, it is determined that the node 3-1 is located at the left end of the collision node sequence, and the node 3-3 is located at the right end of the collision node sequence. The leftmost node 3-1 waits until the transmission line 1 becomes a no-signal state, and then sends the packet 7 on the transmission line in both directions. After transmission, it enters the reception state and does not transmit until the end of the resolution phase. Remaining node 3
After receiving the packet from node 3-1, nodes -2 and 3-3 transmit short reservation signals 8 and 9, respectively, only to the right side. Immediately upon receiving the reservation signal 8 sent by the node 3-2, the node 3-3 stops sending the reservation signal 9 and waits for the colliding node located to the left of itself to complete its packet transmission. Since no reservation signal comes to node 3-2 from the left side of its own node, after transmitting its own reservation signal 8, it subsequently transmits packets 10 in both directions.
After receiving the packet 10 transmitted by the node 3-2, the node 3-3 transmits a reservation signal 11 to the right side. This time, the reservation signal of other nodes is not coming from the left, so after sending reservation signal 11,
Send packet 12 in both directions. Node 3-
After the transmission of the packet No. 3 is completed, there is no collision node waiting for transmission, so the transmission path 1 becomes silent. When all nodes connected to transmission line 1 detect a sufficiently long no-signal period (the time for the optical signal to travel back and forth between the nodes at both ends + the time for sending out the reservation signal), they determine that the resolution phase is over and return to the contention phase. . During the resolution phase, nodes other than the colliding node suppress transmission.

In the above example, transmission was performed in order from the leftmost node 3-1, but it is also possible to transmit in reverse order from the rightmost node 3-3, in which case the above-mentioned left and right sides are reversed.

The end of the packet transmitted from each node may be indicated by adding a special code string to the end of the packet, or may be detected by the no-signal time after the end of transmission. In the above example, the end of the resolution phase was determined by the length of the no-signal time, but it is known that the last node to transmit is the last from its position (right end), and a special signal or code string is used. It is also possible to notify all nodes of the termination. The leftmost node 3-1, which transmits at the beginning of the solution phase, directly sends out a packet without a reservation signal, but since it can also send a reservation signal, it is possible for all nodes to perform the same operation. Further, although the reservation signal is supposed to be transmitted only in the right direction, it is also possible to transmit it in both directions. However, in this case,
In order to avoid interference between reservation signals and packets transmitted by other nodes, the sum of the transmission time of the reservation signal and the time from the transmission of the reservation signal to the transmission of the packet is equal to the time for the optical signal to travel back and forth between the nodes at both ends, and the This needs to be longer than the sum of the times from the reception of the reservation signal until the own node stops transmitting the reservation signal, which reduces the efficiency of using the transmission path.

Fig. 4 shows an embodiment of a coupling device in which the transmission paths are independent in the right direction and the left direction, where 1-1 is the right transmission path, 1-2 is the left transmission path, and 5-1 is the transmission path to the left.
is a waveguide for receiving signals from the left direction, 5-2 is a waveguide for receiving signals from the direction, 6-1 is a waveguide for transmitting signals from the right direction, and 6-2 is for transmitting signals from the left direction. It is a waveguide. 13 is a branch concentrator. In this case as well, it is possible to identify the receiving direction of the signal, transmit only in one direction, and transmit in both directions, and the same operation as in the above example is possible.

FIG. 5 shows a specific embodiment of the coupling device shown in FIG. 4 using a polymer optical waveguide. 1-1,1-
2 is a transmission line using optical fiber, 5-1, 5-
2, 6-2, 14-1 to 14-4, 15-1,
15-2 is a polymer optical waveguide, 16-1, 16-
2 is an optical receiver that uses a photo diode. 17-1 and 17-2 are optical transmitting devices that use laser diodes or light emitting diodes.
18 is a coupling device housing. 19-1 to 19-
Reference numeral 4 denotes a connection portion between the coupling device and a connection cable from the node, and 20-1 and 20-2 are connection devices between the coupling device and the transmission line. Signals sent from a node to other nodes are sent as electrical signals via cable 21-
Optical transmitter 17-1, 1 by 2, 21-3
7-2, the optical signal is transmitted to the optical waveguide 6-1,
6-2. The output optical signals are output to transmission lines 1-1 and 1-2 via optical waveguides 14-3 and 14-2, respectively. That is, the optical transmitter 17-1 transmits to the right, and the optical transmitter 17-2 transmits to the left. On the other hand, receiving devices 16-1, 16-
2 are optical waveguides 5- through optical waveguides 14-1 and 14-4 from transmission lines 1-1 and 1-2, respectively.
1 and 5-2 are detected and sent as electrical signals to connection cables 21-1 and 21-4. Therefore, by separately controlling the electrical signals on the four connection cables, each node can realize the functions of identifying the receiving direction of the signal, transmitting only in one direction, and transmitting in both directions, and the operation of the above embodiment is achieved. It is possible to do this.

When using a signal such as an optical signal whose directionality is easy to realize, a photomolecular optical circuit as shown in FIG. This can be achieved by combining a T-coupler using a mirror.
When using a transmission line such as a coaxial cable or twisted pair wire, it is necessary to devise ways to realize the directionality of the signal. FIG. 6 shows an example in which the coupling device shown in FIG. 2 for use in a transmission line such as a coaxial cable or twisted pair wire is realized using a directional coupling device and a hybrid circuit. 22-1, 22-2 are transmission lines, 23-1, 23-2 are hybrid circuits,
24-1, 24-2 are directional coupling devices, 25-
1, 25-2 are branching devices, 26-1, 26-2
are transmission signal lines, 27-1, 27-2 are reception signal lines, 28-1, 28-2, 29-1, 29-
2, 30-1, and 30-2 are signal lines. The signal from the left propagates from the hybrid circuit 23-1 through signal lines 30-1, 29-1, and 28-1,
Transmission line 2 via hybrid circuit 23-2
It is transmitted to 2-2, but the signal lines 30-2, 29-
2, it is not transmitted to 28-2. Similarly, signals from the right side are signal lines 28-2, 29-2, 30-2.
propagate. The directional coupling device 24-1 transmits the signal from the left (via the signal line 29-1) and the transmission signal (via the transmission signal line 26-1) to the right.
The signal is transmitted from the transmission signal line 26-1 to the signal line 29-1
It will not be transmitted to. Therefore, branching device 25-1
The only signal received from the left side is the signal from the left side. The same applies to the signal from the right side, and as a result, the same operation as in FIG. 2 is performed. In this case, rather than using one transmission line in both directions, a system using separate transmission lines for each direction, as shown in FIG. 5, is easier to implement as it eliminates the need for a hybrid circuit.

FIG. 7 shows a specific configuration example of a transmission control device that performs conflict resolution using the present invention. It is connected to the processor, terminal equipment, etc. in the node by an interface circuit through a transmitting/receiving packet buffer. 31 is a coupling device, 32-1 is a receiving circuit to the left, 32-2 is a transmitting circuit to the right, 33-1 is a transmitting circuit from the left, 33
-2 is a receiving circuit from the right direction. 34 is a packet transmitting circuit, and 35 is a packet receiving circuit which processes a preamble and an error detection code. 3
6 is a parallel-to-serial conversion circuit, 37 is a serial-to-parallel conversion circuit, 38 is a buffer for transmitting packets, and 39 is a buffer for receiving packets, in which packets are stored as parallel data. 40 is a collision detection circuit, and 41 is a node position identification circuit at the time of collision, which outputs three types of information: right edge, left edge, and intermediate information. 42 is a reservation signal sending circuit, 43-1,
43-2 is a transmission line. When a packet collision occurs, the collision detection circuit 40 detects the collision and stops sending the packet. The position identification circuit 41 detects the position of its own node when the collision occurs,
If it is at the left end, the packet is immediately retransmitted. In other cases, after the packet receiving circuit 35 receives one packet, the reservation signal sending circuit 42 is activated.
The reservation signal sending circuit 42 sends out the reservation signal to the right, and when the sending is finished, retransmits the packet.
If a reservation signal from another node is received from the left while the reservation signal is being sent, the own node stops sending the reservation signal and waits for the other node to finish transmitting one packet. In response to the reception end signal from the packet receiving circuit 35, the reservation signal sending circuit 42 repeats the above operation. After a collision occurs, it is confirmed that all nodes that caused the collision have finished sending packets (as determined by the packet receiving circuit 35 based on the length of the no-signal time).
Until now, the packet transmitting circuit 34 does not transmit packets except when activated by the reservation signal transmitting circuit 42 and the position identifying circuit 41.

As explained above, the node that caused the collision can reliably transmit from the end according to its position in the next resolution phase, so the transmission waiting time can be reduced, and the usage efficiency does not decrease even under high load. There are advantages such as being able to always send the data within the specified time.

[Brief explanation of the drawing]

Fig. 1 is a block diagram of an embodiment of the present invention, Fig. 2 is a diagram showing the signal flow in the coupling device, Fig. 3 is a diagram of the operation during conflict resolution, and Fig. 4 shows how the transmission path is separated for each direction. Fig. 5 shows a specific example of a coupling device using a polymer optical circuit, and Fig. 6 shows a coupling device using coaxial cables and twisted pair wires as the transmission path. Specific Example: FIG. 7 shows a specific configuration example of a transmission control device that performs conflict resolution using the present invention. 1, 1-1, 1-2...optical fiber transmission line, 2
-1 to 2-3... Coupling device, 3-1 to 3-3...
Node, 4-1, 4-2...Terminal device, 2...Branch concentrator, 5-1, 5-2...Signal reception waveguide, 6-1, 6-2...Signal transmission waveguide ,7...
...Transmission packet of node 3-1, 8...Node 3
-2 reservation signal, 9...Reservation signal (interruption) of node 3-3, 10...Transmission packet of node 3-2,
11... Reservation signal of node 3-3, 12... Transmission packet of node 3-3, 13... Branch concentrator, 14-1 to 14-4... Waveguide for connection with transmission line, 15-1 , 15-2... Waveguide for branching and concentrating, 16-1, 16-2... Optical receiver, 17
-1, 17-2... Optical transmitting device, 18... Coupling device housing, 19-1 to 19-4... Connection device for connection cable and coupling section, 20-1, 20-2... Transmission line and Connection device with the coupling part, 21-1 to 21-4...
...Cable for connection with node, 22-1, 22-
2... Transmission line, 23-1, 23-2... Hybrid circuit, 24-1, 24-2... Directional coupling device, 25-1, 25-2... Branching device, 26-
1, 26-2... Transmission signal line, 27-1, 27-
2... Reception signal line, 28-1, 28-2, 29-
1, 29-2, 30-1, 30-2...signal line,
31-coupling device, 32-1...transmission circuit to the left, 32-2...transmission circuit to the right, 33-1
...Reception circuit from the left direction, 33-2...Reception circuit from the right direction, 34...Packet transmission circuit, 3
5... Packet receiving circuit, 36... Parallel-serial conversion circuit, 37... Serial-parallel conversion circuit, 38... Buffer for transmitting packets, 39... Buffer for receiving packets, 40... Collision detection circuit, 41... Position Identification circuit, 42... Reservation signal sending circuit, 43-1,
43-2...Transmission line.

Claims (1)

[Claims] 1. Occurs when a plurality of nodes, such as processors or end devices, send packets almost simultaneously on a bus-type local network based on a contention method to which a plurality of nodes are connected. In the method for resolving packet collisions, the node includes means for controlling packet transmission in the right direction, left direction, or both directions simultaneously on the transmission path;
and a coupling device for connecting the node and the transmission path, the node having means for identifying the direction of packet reception;
The means for identifying the packet reception direction determines whether the own node is located at the right end, the left end, or inside the colliding node string that caused the collision from the receiving direction of the colliding packet among the plurality of nodes. The means for controlling the packet transmission temporarily suppresses the transmission based on the contention method, and the node at one end of the colliding node string starts transmitting unconditionally. After completing packet reception, a node other than the end node sends a short reservation signal from itself to the other end node, and while the reservation signal is being sent, another reservation signal is sent from the one end node to the other end node. If it receives this, it determines that there is a collision node that has not yet finished transmitting from its own node to the node at one end, and stops transmitting the reservation signal from its own node, and terminates the transmission. If the other reservation signal is not received, packets are transmitted sequentially in accordance with the position of each node by transmitting a packet following the reservation signal of the own node. A method for resolving packet collisions in a local network, which is characterized by: