JP3460080B2 - Distributed management communication method and apparatus - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to real-time communication (hard real-time communication) necessary for realizing various distributed real-time control of various robots, automobiles, plants, home automation, etc., as well as images and voices. The present invention relates to a communication method and system that enable real-time communication (soft real-time communication) necessary for smoothly transmitting multimedia data.

FIG. 1 shows an example of a distributed real-time control system for a humanoid robot. In this example, an information processing device for controlling each functional block (head, eyes, ears, mouth, joints, etc.) of the robot. The humanoid robot system is constructed by connecting the spaces with an appropriate topology using the real-time communication link using the present invention.

In this example, hard real-time communication that guarantees a delay time is required to control each motor and sensor, and a bandwidth is guaranteed to smoothly send and receive image and audio data. Soft real-time communication is required.

[0004]

2. Description of the Related Art In conventional real-time communication (isochronous transfer, etc.) such as USB and IEEE 1394, a communication bandwidth is reserved in advance in a main communication control management device that centrally manages the communication data bandwidth. The main unit manages the bandwidth in a unified manner. That is, the main communication control management device realizes real-time communication by centrally managing the bandwidth. It is difficult to construct a large-scale real-time communication system with such a centralized management method (up to 12
7 nodes, maximum 63 nodes in IEEE1394),
When the main communication control management device breaks down, all communication is stopped.

In the conventional method, there is no practical system for overtaking because the priority is added to the communication packet, and even in the method of overtaking the experimental communication packet,
Achieve overtaking of communication packets with a short delay time,
There is no need to control the real-time communication by making it unnecessary to retransmit the communication packet or accelerating / decelerating the communication packet by changing the priority for each communication node. JP 62-260452
In the gazette, a multistage interconnection network (MIN) is applied to give priority to communication packets to realize packet and circuit switching. This method is originally a technology for telephone lines, and it enables packets or circuit switching by giving priority to a call request for setting, a call setting request, an asynchronous data request, etc. on the telephone line. Voice packets for voice data are prioritized, soft real-time communication is realized for voice packets, and non-real-time data packet communication is performed with other excess bandwidth. However, in this method, since communication packets are input and output through a plurality of stages of sub-switches depending on the number of ports, increasing the number of ports can increase the bandwidth, but the number of stages of sub-switches will increase. It increases and the delay time increases. Furthermore, in order to communicate, it is necessary to open the line first, and the delay of the initial communication is large. In addition, there is a possibility that a packet with a low priority cannot be transmitted from the transmission source for a long time because the line is not opened. Therefore, it is suitable for soft real-time communication such as voice communication, but not suitable for hard real-time communication for control purposes.

[0006] In the conventional method, communication packets having the same network address are always transmitted from the transmission source to the reception destination at the same moment at a certain moment, and are communicated through a plurality of routes at the same time by providing a dedicated line or a detour. It is not possible.
In Japanese Patent Laid-Open No. 58-151747, a predetermined class can be set for each terminal connected to the packet switch and routing can be performed according to the class (corresponding to the priority) assigned to the terminal. The class is assigned to the terminal, and in the event of a failure, the packet from the terminal to which the priority class is given can pass through the detour by the statically set routing table in advance. A packet from a terminal to which a non-priority class has been given can be set to pass only the detour during normal times, and to be discarded when a failure occurs. However, since the class is added to the terminal and the routing is changed only when the state changes from normal to failure, it is not possible to dynamically change the routing in normal. Also, at a certain moment, only one route is routed from the source to the destination for communication, and it is not possible to route multiple routes for simultaneous communication.

[0007]

On the other hand, according to the present invention: 1. Communication packets are prioritized, and communication packets of high priority are transmitted with low priority and communication packets of low priority are short-delayed for each communication node. Real-time communication is controlled by overtaking communication packets without retransmitting them. 2. Communication packets with exactly the same network address (source address and destination address) are set to different routes according to priority, and multiple routes are set. By simultaneously routing and communicating at the same time, a dedicated line or detour is provided to control bandwidth and delay time while controlling real-time communication. 3. Priority of communication packet for each communication node Real-time communication is controlled by distributed management by distributed control of acceleration / deceleration and routing of replacement communication packets. By combining the method, to achieve a small real-time communication of large and quantum time using the distributed management.

[0008]

As shown in FIG. 2, a priority is added to the header portion of a communication packet in addition to the network address (source address, destination address, etc.). 0 is the lowest priority, and the higher the number, the higher the priority. In FIG. 3, a total of four communication nodes are star-coupled, and communication node 1 (source 1) and communication node 2
The case where (source 2) simultaneously transmits a communication packet to the communication node 4 via the communication node 3 is shown. Figure 3
In (A), the communication node 1 transmits a communication packet of priority 1 to the communication node 3, and the communication node 2 simultaneously transmits a communication packet of priority 0 to the communication node 3. In FIG. 3B, the communication node 3 receives the communication packets from the communication node 1 and the communication node 2, but the communication node 3 receives the communication packet from the communication node 1 having a higher priority of the communication packet. Communication packet from the communication node 2 having a low priority is kept waiting in the communication node 3.
FIG. 3C shows that the communication packet from the communication node 1 is transmitted to the communication node 4 and then the communication packet from the communication node 2 having a low priority is transmitted to the communication node 4.

In order to realize the above, the following control method is performed. Figure 4 shows the case of a network switch with 5 inputs and 5 outputs and 4 overtaking buffers per input part, but if the communication packet input from the input port does not collide with the communication node, it is output port as it is. Output to. In FIG. 4, when communication packets input from different input ports output to the same output port, communication packets with lower priority are buffered (temporary for transferring data) according to the priority added to the communication packets. Stored in a different storage location) and output is awaited, and communication packets with high priority are output first. After outputting the communication packet of high priority, the communication packet of low priority is output from the buffer to the output port, and the communication packet of the priority is overtaken.

In order to realize the above-mentioned passing of the communication packet, a plurality of buffers having the same size as the communication packet are provided on the input port side. Further, it is possible to provide a storage device (memory) for temporarily saving the contents of the buffer when the input continues to be input and the buffer is about to overflow while the output is kept waiting.

FIG. 5 shows the details of one input section of the network switch of FIG. 4, but the passing of communication packets is performed as follows. The communication packet input from the input port is written in an empty buffer which is not used among the buffers 0 to 3 pointed by the input pointer. All the header parts of the input packet are always received and written in the buffer, and the output port number and the priority are obtained by referring to the routing table (route control table) as shown in FIG. 6 based on the received header. The obtained output port number is the link strobe (L0
To L4), for example, if the L0 bit is valid, it indicates that the output destination of the input packet is output port 0.

In FIG. 5, if a plurality of bits from L0 to L4 are valid, it means multicast, and if all are valid, it means broadcast. On the output side of the input section, the link strobe of each buffer is independently referred to for each output port, and when the link strobe of its own output port is valid, the priority arbitration device on the output port side (see FIG.
Output) together with the priority. The priority arbitration device gives output permission immediately when there is an output request from only one input port, and gives output permission to the one with the highest priority when there are a plurality of output requests. When there are multiple requests with the highest priority, output permission is given by the round robin method.

If there is no collision of communication packets, or if there is a collision and the communication packet has the highest priority at that time, the output is started immediately after the delay time of receiving the header and referring to the routing table. On the output side of the input unit, when the packet transmission is completed, each output port independently invalidates only its own link strobe, and when all the link strobes are invalidated, it means that the buffer is empty. When packets are kept waiting in the buffer but the input packets are continuously input, at least one empty buffer is always prepared so as not to overflow the buffer. In FIG. 5, if the number of empty buffers is low (for example, the remaining buffer is 1), the next input packet is stored in the save storage device (for example, SD).
RAM etc.) When the output progresses and the number of remaining empty buffers becomes large (for example, two or more), the input packets saved in the save storage device are restored to the buffer in consideration of the priority, and the output is continued.

In FIG. 5, the SDRAM output pointer points to the SDRAM save address of the input packet to be saved, and the SDRAM input pointer points to the empty buffer where the data is restored. In real-time communication,
When retransmission is performed, the overhead that occurs is very large and the quantum time in real-time communication becomes large, but by not performing such retransmission, the quantum time in real-time communication can be made very small.

A dedicated line and a detour can be provided by enabling the routes of communication packets having exactly the same network address to be set to different routes that can be simultaneously communicated according to the priority. At this time, different routes can be set for transmission and reception. It is possible to simultaneously communicate between exactly the same transmission source and reception destination through a plurality of different routes for each priority, and it is possible to widen the bandwidth. These functions enable control of the bandwidth and delay time of communication packets.

Basically, a routing table is referred to by a set of a network address and a priority. If a combination (route) having the same network address but the same priority is not found in the routing table,
The route with the lowest priority 0 is the default route. In other words, 1. If both the network address and the priority match, the route has the first priority. 2. If the network addresses match but the priority does not match, the route has the priority 0. At this time, priority 0
Since the route of is the default route, it is recommended to register it in the routing table so that the route does not disappear in the middle.

FIG. 7 shows a state in which communication packets of different priorities are simultaneously transmitted from the same source to the destination. In FIG. 7, there is a communication node at the intersection of the two-dimensional lattice, and communication packets having four priorities of priority 0 to priority 3 are simultaneously communicated from the transmission source to the transmission destination through different routes. For example, a communication packet from another communication node is set to pass through the same route to the destination on the route of priority 0, and the route of priority 3 is set in FIG.
By setting so that only the communication packets of the transmission source and the transmission destination of priority 3 can be passed, it is completely different from other communication packets (communication packets between other nodes and communication packets of different priority from the own node). It is possible to realize a dedicated line with a high throughput and a short delay time without collision. In a normal network, a certain route is defined at a certain moment (time), and communication is performed through that route. However, if the priority is different in this way, it is possible to simultaneously communicate on different routes. To do. Further, with the above-mentioned setting, the bandwidth between the transmission source and the reception destination can be widened and the delay time can be reduced.

A distributed control system often adopts a tree structure as shown in FIG. In FIG. 8, all lines (solid line, dotted line, broken line) indicate physical communication paths. In the case of communicating from the communication node 0 to the communication node 7 in FIG. 8, a communication packet of low priority 0 with low real-time property is communicated via the communication nodes 1 and 3 on the way, The communication packet of priority 3 which requires time property is directly communicated from the communication node 0 to the communication node 7. At this time, if the route of the dotted line is set so that only communication packets of priority 3 pass, communication packets of other priorities pass through different routes, so that different packets of different priority among the same communication nodes It is possible to realize a dedicated line with high throughput with low delay time without being disturbed. In addition, FIG. 8 is also an explanatory diagram that it is possible to easily extend it later (add a dotted line route) when it is found that the communication delay time cannot be met or the bandwidth is insufficient after the system is manufactured. Also serves as. For example, when the system designer initially designed the system to perform distributed control with a tree-structured architecture (other than the dotted line portion in FIG. 8), when actually producing it, communication from node 0 to node 7 Suppose that it turns out that the delay time cannot be met in time. According to the present invention, it is easy to newly provide a communication path (dotted line part in FIG. 8) between the node 0 and the node 7 and perform routing according to the priority (priority 3 in this case). It is possible to extend it by adding it later, and solve problems related to delay time and bandwidth. In this way, even if the communication packets have the same source and destination, if the priority is different, it is possible to set another route and provide a dedicated line or a detour that enables simultaneous communication. It is possible to build a real-time communication system that requires less time.

By changing the priority of the communication packet for each communication node, the communication packet is accelerated / decelerated and the routing is changed, and real-time communication control in distributed management is realized. The priority is changed by using a routing table (route control table) as shown in FIG. In FIG. 6, the routing table is referenced based on the network address and the priority, and the output port number (s) may be determined. At that time, in the mode in which the priority is not changed (the priority change bit in FIG. 6 is invalid), the priority remains unchanged, but in the mode in which the priority is changed (the priority change bit in FIG. 6 is valid). In this case, when outputting from the output port, the priority of the communication packet is replaced with the new priority. That is, the priority of the communication packet at the current node is determined by the priority added to the header of the input packet, and passing or routing is determined according to the priority, but the priority of the communication packet at the next node is Can be controlled. Therefore, the acceleration / deceleration of the communication packet can be distributed and controlled for both overtaking and routing according to the priority. The routing table is set by software (distributed management by a distributed operating system), and the routing (route control) itself is done by hardware.

The present invention, which is configured as described above, realizes real-time communication by a method of overtaking communication packets according to priority for each communication node without resending. At the same time, the priority of the communication packet can be changed for each communication node, and accordingly, the acceleration / deceleration of the communication packet and the routing control can be performed, thereby realizing the distributed management type real-time communication control. Furthermore, with the function to set the routes of communication packets with the same network address to different routes that can communicate at the same time according to the priority, it is possible to provide a leased line or detour, and delay due to route control according to the priority. Realize real-time communication control in terms of both time and bandwidth. In addition, since it is a distributed management type, even if a communication path becomes inoperable due to a failure, communication of the path that is not affected is maintained, and the routing table can be dynamically rewritten by software to control the path. Since it is possible, it may be possible to set another route so as to avoid the defective node, and the robustness of communication is high.

[0021]

BEST MODE FOR CARRYING OUT THE INVENTION The present invention is used on a responsive link, which is a real-time communication standard of a responsive processor for parallel distributed real-time control, which has been researched and developed by the Institute of Electronics Technology, Ministry of International Trade and Industry. There is.

In the responsive link, as shown in FIG. 9, an event line for hard real-time communication that guarantees a low delay time for control use and a data line for soft real-time communication that guarantees a bandwidth for multimedia data transfer are provided. Separation (Japanese Patent Laid-Open No. 10-307803), and real-time communication is realized by utilizing the present invention. Responsive link has 5 inputs 5 as shown in Fig. 4.
It has an output configuration, link 0 is connected to its own CPU, and four links 1 to 4 are input / output to / from the outside.

As shown in FIG. 9, the input port and the output port are a set of connectors / cables, and differential input / output is performed to improve noise resistance. Event link and data link are simultaneously performed. You can send and receive. The packet format of the responsive link is as shown in Fig. 10, and the 32-bit network address (source address (16bit) and destination address, including priority, is included in the header of each event and data.
(16bit)) is embedded. Further, the most significant bits of each of the source address and the destination address are priority bits 1, 0, which has a total of 2 bits (4 types) of priority.

The routing table is as shown in FIG. 11, and the reference source of the routing table is the header portion itself of the input packet (source address and destination address in which priority is embedded). References are as follows: -EE (Even
t table Enable) ・ DE (Data t) indicating that the table is a data line
able enable) -The output port number (link strobe: L0 to L4) indicating which link the data is output to.-Priority assignment valid bit (PE) -New priority (P0, P1).

In FIG. 4, when a communication packet is input from an input port (inputs 0 to 4), the header portion is first referred to in the table of FIG. 11 to obtain the output port number, priority and priority reassignment valid bit. The priority is output to the priority arbitration device of the output port (output 0 to 4) obtained by the output port number, and the priority side arbitration device on the output side outputs the output immediately when there is only one input port. If it is permitted and there is input from a plurality of input ports (meaning a situation in which a communication packet has collided), output is permitted to the highest priority according to the priority. (Round-robin for same priority)

The communication packets whose output is awaited by the priority arbitration device are stored in the buffers (buffers 00 to 43) shown in FIG. 4, and are output after the output of the communication packets having a high priority is completed. If the communication packet to be output keeps waiting and the buffer is about to overflow (the remaining empty buffer is one), save it in the SDRAM (synchronous DRAM) in the subsequent stage,
When the communication packets stored in the buffer are output and an empty buffer is created, the communication packets are restored from the SDRAM to the buffer and output in consideration of the priority.

When outputting the communication packet to the output port, if the priority change effective bit (PE) of FIG. 11 is valid, the priority (Priority 0, Priority 1) is the new priority (P 1, P0), and when disabled, the priority is maintained. Further, by using the routing table of FIG. 11 according to the present invention, different routes can be set even if they have the same network address but different priorities. By using these different routes, communication packets having different priorities can be simultaneously communicated. The prioritization of these communication packets and the route control by priority are performed by hardware according to the routing table, but the management and control of the routing table is performed by software (real-time distributed operating system etc.) Real-time communication is realized.

[0028]

According to the present invention, a distributed management type real-time communication system, which has been impossible in the past, is provided with (1) overtaking by communication packet priority (2) route control by priority (3) each communication node It is realized by using three methods of changing the priority of. At the same time, by combining these methods, it is possible to realize real-time communication with extremely short quantum time.No retransmission is required.Communication can be performed on different routes at the same time between the same communication nodes.Easy to retrofit communication delay and bandwidth. Extensible ・ Comparable with centralized management type, it is possible to connect a large number of communication nodes ・ Even if a part of the communication path is broken, robust communication is possible.

[Brief description of drawings]

FIG. 1 illustrates a distributed control system using a humanoid robot as an example.

FIG. 2 illustrates a packet format in which priority is added to a header portion of a communication packet.

FIG. 3 illustrates overtaking of communication packets according to priority.

FIG. 4 illustrates a network switch having five inputs and five outputs, and four passing buffers per input unit.

5 shows the details of one input section of the network switch of FIG.

FIG. 6 illustrates a routing table (route control table) for obtaining an output port number and a priority based on a received header of an input packet.

FIG. 7 is a diagram showing a state in which communication packets of different priorities are simultaneously being communicated from exactly the same source to the destination.

FIG. 8 is a diagram for explaining route control according to a priority in a tree structure as adopted in a distributed control system.

FIG. 9 illustrates signals and connectors of a responsive link through which an event line and a data line can simultaneously transmit and receive.

FIG. 10 illustrates a responsive link packet format.

FIG. 11 illustrates a routing table for responsive links.

Continuation of the front page (56) Reference JP 62-260452 (JP, A) JP 8-242256 (JP, A) JP 6-224939 (JP, A) JP 11-8652 (JP , A) JP 8-191328 (JP, A) JP 1-303832 (JP, A) JP 58-151747 (JP, A) (58) Fields investigated (Int.Cl. ⁷ , DB) Name) H04L 12/56 H04L 12/28 H04L 29/06

Claims (4)

(57) [Claims] 1. In a communication method in which selected information processing apparatuses communicate with each other using communication packets on a network having a communication node provided with a plurality of information processing apparatuses corresponding to each other, priority is given to communication packets. In the communication node of each information processing device, a plurality of communication packet overtaking buffers for each input port of the communication node and evacuation for preventing the overtaking buffers from overflowing
A storage device is provided to enable buffering of communication packets that should be overtaken according to the priority when a communication packet collision occurs, and input communication packets are input from one input port side to one or more output port sides. It issues an output request with the attached priority, arranges a communication packet priority arbitration device for each output port and performs output arbitration from each input port side, and according to the output arbitration, input packets are sent. A distributed management type communication method comprising: outputting independently to each output port side, and controlling communication packets passing through a communication node so as to overtake those having high priority and those having low priority. 2. The distributed management type communication method according to claim 1 , wherein the priority of the communication packet is changed for each communication node, and acceleration / deceleration of the communication packet and routing are controlled. 3. In a communication device in which selected information processing devices communicate with each other using communication packets on a network having a communication node provided with a plurality of information processing devices corresponding to each other, priority is given to the communication packets. In the communication node of each information processing device, a plurality of communication packet overtaking buffers for each input port of the communication node and evacuation for preventing the overtaking buffers from overflowing
A storage device is provided to enable buffering of communication packets that should be overtaken according to the priority when a communication packet collision occurs, and input communication packets are input from one input port side to one or more output port sides. It issues an output request with the attached priority, arranges a communication packet priority arbitration device for each output port and performs output arbitration from each input port side, and according to the output arbitration, input packets are sent. Distributed management type communication consisting of independently outputting to each output port side, and performing distributed management control so that communication packets passing through the communication node with higher priority overtake those with lower priority. apparatus. 4. The distributed management type communication device according to claim 3 , wherein the priority of the communication packet is changed for each communication node, and acceleration / deceleration of the communication packet and routing are controlled.