JPWO2004093395A1 - Routing device that transmits received packets according to sequence number - Google Patents

Abstract

A routing device (100) connectable to a network (52, 54, 56 and 58) sends a series of packets addressed to a predetermined receiver (60) from a predetermined transmitter (40) and having a sequence number. The received packet is temporarily stored in the queue (124) for each destination, and the stored packet is transmitted according to the sequence number regardless of the reception order of the packet for each stored destination.

Description

The present invention relates to a route control apparatus (router) in a network capable of transmitting a series of packets via a plurality of routes, and more particularly to routing according to a sequence number of received packets.
BACKGROUND OF THE INVENTION When a series of packets are transmitted through a plurality of paths in a network, the receiving order of packets sent from a transmitting end may be disturbed at the receiving end.
For example, when a series of packets are multicast-transmitted, the packets may be copied in a disordered reception order in a routing device in the middle of the network. As a result, the order of received packets is disturbed in all subsequent routing devices and receivers that receive a series of packets via the routing device.
Therefore, when the reception order of a series of packets is important, it is necessary for the transmitter to describe a sequence number in the transmission packet, and for the receiver to reconfigure the data by correcting omission and disorder of the sequence number.
On the other hand, research and development have been conducted to construct a network in which a series of packets are sequentially transmitted through only one path in the network and the reception order of the packets transmitted by the receiver is not disturbed.
However, in order to make maximum use of network resources, it is better to allow a series of packets to be transmitted via a plurality of paths.
Japanese Laid-Open Patent Publication No. 5-252186 (A) published on September 28, 1993 by Taisho describes a cell order matching method for ATM switches. This method adds a time stamp to the input cell in the ATM switch, and corrects the reversal of the cell order that occurs when distributed routing is performed in the switch according to the time stamp added in the buffer.
The inventors have recognized that it is efficient to reduce the processing load for correction on the receiver side by correcting the order of received packets in the routing device in the network. The inventors have also recognized that it is efficient to reduce the processing load for correcting jitter on the receiver side by correcting the transmission jitter of the received packet in the route control device in the network.
An object of the present invention is to correct the order of received packets in a route control device.
Another object of the present invention is to correct transmission jitter of a received packet in a path control device.
SUMMARY OF THE INVENTION According to one aspect of the present invention, a processor of a routing device connectable to a network receives a series of packets addressed to a predetermined receiver from a predetermined transmitter and having a sequence number. The packet is temporarily stored in the queue for each destination, and the stored packet is transmitted according to the sequence number regardless of the reception order of the packet for each stored destination.
The present invention further relates to a program for the above-described path control device.
According to the present invention, it is possible to correct the order of received packets in the routing device, thereby reducing the order correction load of the receiver and correcting transmission jitter of the received packets. .
In the drawings, the same elements have the same reference numerals.

FIG. 1 shows the configuration of a path control apparatus according to an embodiment of the present invention.
FIG. 2 shows a flowchart for processing a new received packet, which is executed by the packet analysis unit.
FIG. 3A shows the configuration of the packet management unit.
FIG. 3B shows a packet management queue in the packet management unit in FIG. 3A.
FIG. 3C shows a configuration of packet management data in the packet management queue in FIG. 3B.
FIG. 4 shows a flowchart for processing a new received packet, which is executed by the packet manager.
FIG. 5A shows an example of conditions for a received packet whose transmission order is corrected.
FIG. 5B is useful for explaining the identification and distribution of received packets by the packet manager.
6A and 6B show examples of packet management queues in the packet management unit.
FIG. 7 shows a flowchart for sending out a packet stored in the packet management queue, which is executed by the packet management unit.
8A and 8B show examples of packets in the packet management queue in the packet management unit.
9A and 9B automatically determine which of the routing devices in the network has the function of correcting the transmission order and which of the program receivers the packet transmission order is corrected according to a request from the program receiver. Various ways of making decisions are shown.
FIG. 10 is useful for explaining a method of correcting transmission jitter in a path control device.
Illustration of the preferred embodiment shows an embodiment configuration of a path control device 100 according to the present invention. The path control device 100 is connected to one or more networks 52 to 58. The route control device 102 may be connected to a transmitter 40 such as a program broadcast device for multicast. The transmitter 40 may have a reception function. The route control device 104 may be connected to a receiver 60 such as a multicast receiving device. The receiver 60 may have a transmission function. The route control devices 102 and 104 have the same configuration as the route control device 100.
The path control device 100 includes a packet order management unit 120 and network interfaces 132 to 142 connected to the networks 52 to 58 and the like, respectively. The route control device 100 may be connected to the transmitter 40 or the receiver 60. The packet order management unit 120 includes a packet analysis unit 122 and a packet management unit 124. The functions of the packet analysis unit 122 and the packet management unit 124 may be implemented (implemented) by the processor 126 according to a program stored in the program memory 128.
The network interfaces 132 to 142 supply the received packets to the packet order management unit 120. The packet analysis unit 122 of the packet order management unit 120 adds a reception time to the received packet, analyzes the packet, and determines whether the packet is a target of order correction.
FIG. 2 shows a flowchart executed by the packet analysis unit 122 for processing a new received packet.
In step 202, when receiving a new received packet, the packet analysis unit 122 determines attributes such as a destination address, a destination port, and a sequence number of the packet. In step 204, the packet analysis unit 12 determines whether or not the packet is an order correction target according to the attribute of the packet. When it is determined that the packet is not the target, in step 210, the packet analysis unit 12 transmits the packet to a corresponding network, for example, the network 58.
When it is determined that the packet is the target, in step 206, the packet analysis unit 122 analyzes the sequence number of the packet. In step 208, the packet analysis unit 122 extracts the time stamp and sequence number in the received packet and passes them to the packet management unit 124 together with the received packet. The packet management unit 124 transmits the packet to a corresponding network, for example, the network 58 in accordance with the sequence number in the form described below.
FIG. 3A shows the configuration of the packet management unit 124. FIG. 3B shows the configuration of the packet management queue 320 representing the packet management queues 302, 304, and 306 in the packet management unit 124 of FIG. 3A. FIG. 3C shows a configuration of packet management data 350 representing the packet management data 342 to 348 in the packet management queue 320 of FIG. 3B.
As shown in FIG. 3A, the packet management unit 124 dynamically generates and holds packet management queues 302 to 306 associated with the destination addresses A to C and the destination port.
As shown in FIG. 3B, the packet management queue 320 includes a packet management queue attribute 330 and a management data queue 340 area. The attribute 330 of the packet management queue includes the destination address 332 of the packet in the queue, the destination port 334 representing the reception port of the receiver 60, the sequence number 336 of the last outgoing packet in the queue, and the reception time of the oldest packet in the queue 338 fields are included. The destination address 332 may be an individual destination address or a destination address for multicast or broadcast (broadcast communication). The management data queue 340 includes the received untransmitted management data 342 to 348.
Referring to FIG. 3C, the packet management data 350 includes packet data 352, a reception time 354, and a packet sequence number 356. The packet data 352 includes a time stamp added by the transmitter 40.
FIG. 4 shows a flowchart for processing a new received packet, which is executed by the packet management unit 124.
In step 402, the packet management unit 124 determines whether there is a packet management queue 302 to 306 already generated for each destination address and destination port corresponding to the attribute of the new received packet. If it is determined that the corresponding queue does not exist, in step 404, the packet management unit 124 generates a corresponding packet management queue, and in step 406 stores the new packet in the generated queue.
When it is determined in step 402 that the corresponding queue exists, in step 414, the packet management unit 124 determines whether the sequence number of the new received packet is smaller than the last (previous) transmitted packet, that is, whether it is older. judge. If it is determined that the packet is older than the last transmitted packet, in step 430, the packet management unit 124 discards the new packet.
If it is determined that it is not older than the last transmitted packet, in step 416, the packet management unit 124 determines whether or not the corresponding packet management queue is empty. If it is determined that it is empty, in step 406, the packet management unit 124 stores the new packet in the management queue.
If it is determined that it is not empty, in step 418, the packet management unit 124 determines whether or not a received packet having the same sequence number as the new received packet exists in the corresponding packet management queue. If it is determined that there is a received packet with the same sequence number, the procedure proceeds to step 430.
If it is determined that there is no received packet with the same sequence number, in step 420, the packet management unit 124 stores the new received packet in an appropriate position in the corresponding packet management queue, and thereby the packet in the queue is stored. Correct the order.
FIG. 5A shows an example of the condition of a received packet that is a target of transmission order correction. In FIG. 5A, the example 51 of the condition of the packet whose transmission order is corrected is that the string value of the first 16 bits of the source IPv6 address corresponds to “fec0” and the communication protocol is TCP. Another example of the condition 52 is that the value of the first 16-bit string of the source IPv6 address corresponds to “3ffe”. Yet another example 53 of the condition is that the communication protocol is RTP. The analysis unit 122 determines whether or not the new received packet matches any of these conditions 51 to 53 (FIG. 2, steps 202 to 204). When it is determined that it matches any of the conditions, the analysis unit 122 passes the packet to the packet management unit 124 for transmission order correction.
FIG. 5B is useful for explaining the identification and distribution of received packets by the packet management unit 124. In FIG. 5B, when new received packets 501 to 505 are supplied to the analysis unit 122, the analysis unit 122 determines whether the packets 501 to 505 match the conditions 51 to 53 shown in FIG. 5A. The packet 501 has the leading 16-bit value “fec0” of the source address, the protocol is TCP, and therefore the packet matches the condition 51. The packet 502 has the first 16-bit value “fec0” of the source address, but its protocol is FTP, so the packet does not match any condition. The packet 503 has the leading 16-bit value “3ffe” of the source address, and therefore the packet matches condition 52. The packet 504 has the first 16-bit value “3ffe” of the source address, but its protocol is UDP and does not have a sequence number, so the packet does not match any condition. Packet 505 is RTP in its protocol, so the packet matches condition 53.
A packet that matches any of the conditions 51 to 53 is transferred to the packet management unit 124 together with the sequence number and reception time data for transmission order correction, and stored in the corresponding packet management queue. On the other hand, a packet that does not match any of the conditions 51 to 53 is transmitted to the corresponding networks 52 to 58.
6A and 6B show examples of packet management queues in the packet management unit 124. FIG. Packets passed to the packet management unit 124 by the packet analysis unit 122 are managed by the packet management unit 124 in the form of a queue. The packet management unit 124 generates and holds a packet management queue for each destination address and destination port.
Referring to FIG. 6A, it is assumed that the packet management unit 124 already has a packet management queue 101 for the destination address 102 and the destination port 103 and a packet management queue 201 for the destination address 202 and the destination port 203. . When the packet management unit 124 receives a new received packet 310 from the packet analysis unit 122, the packet management unit 124 checks whether a packet management queue corresponding to the destination address 302 and the destination port 303 of the packet exists. When there is no queue corresponding to the destination address 302 and the destination port 303 of the received packet 310 in the current packet management queues 101 and 201, the packet management unit 124 creates a new packet corresponding to the destination address 302 and the destination port 303. A management packet management queue 301 is created, and the received packet 310 is stored therein.
6B, the packet management unit 124 includes a packet management queue 101 for the destination address 102 and the destination port 103, a packet management queue 201 for the destination address 202 and the destination port 203, a destination address 302 and a destination port 303. It is assumed that the packet management queue 301 for use already exists. When receiving a new received packet 113 from the packet analysis unit 122, the packet management unit 124 checks whether there is a packet management queue corresponding to the destination address 102 and the destination port 103 of the packet. When the packet management queue 101 corresponding to the destination address 102 and the destination port 103 of the received packet 113 exists in the current queues 101, 201, and 301, the packet management unit 124 sets the destination address 102 and the destination port 103. The received packet 113 is stored in the corresponding packet management queue 101 according to the sequence number SN. For this purpose, the packet management unit 124 sequentially compares the sequence number of the packet 113 with the sequence numbers of the packets 110, 111, and 112 in the queue 101. Since this sequence number 1002 is larger than the sequence number 1001 of the packet 111 and smaller than the sequence number 1003 of the packet 112, the packet 113 is inserted between the packets 111 and 112 in the queue 101. When the new received packet 113 is smaller than the sequence number of a packet already sent to the network, the packet management unit 124 discards the received packet. In this example, the order of packets is corrected when a new received packet is stored, but the received packets may be stored in the order of reception without correcting the order, and the order of the packets may be corrected when transmitted.
FIG. 7 shows a flowchart for sending out the packet stored in the packet management queue 320 of FIG. 3B, which is executed by the packet management unit 124.
In step 702, the packet management unit 124 determines whether the sequence number of the packet at the head of the packet management queue 320 is the next number of the sequence number of the last (previous) transmitted packet. If it is determined that the sequence number is the next number of the sequence number of the last transmitted packet, in step 704, the packet management unit 124 transmits the packet at the head. Thereafter, the procedure returns to step 702. Accordingly, a series of packets having a series of sequence numbers following the sequence number of the last transmitted packet in the queue are sent out until the continuity of the sequence numbers breaks or the packet management queue is empty.
When it is determined that the sequence number is not the next number of the sequence number of the last transmitted packet, in step 714, the packet management unit 124 determines the packet with the oldest (earliest) reception time in the packet management queue. Calculate the difference between the reception time and the current time. In step 716, the packet manager 124 determines whether the difference is greater than a predetermined buffering time or waiting time in the packet management queue. When it is determined that the difference is larger than the predetermined buffering time in the packet management queue, in step 718, the packet management unit 124 determines that the packet with the smallest sequence number at the head regardless of the continuity of the sequence numbers of the packets. To the packet with the oldest reception time are sequentially transmitted. Thereafter, the procedure exits the routine of FIG. 7 when it is determined that the difference exiting the routine of FIG. 7 is not greater than the predetermined buffering time.
8A and 8B show examples of packets in the packet management queue in the packet management unit 124. FIG.
Referring to FIG. 8A, in the packet management queue, the sequence number of the last outgoing packet is 4000, the sequence number of the current first packet 401 is 4001, and the sequence numbers of the subsequent packets 402 and 403 are 4002 and Assume that it was 4004. Accordingly, the packet management unit 124 sequentially transmits the first and subsequent packets 401 and 402. The next packet 403 is not transmitted at this point because its sequence number 4004 is not continuous with the sequence number 4002 of the last packet 4002 transmitted.
Referring to FIG. 8B, it is assumed that the packets 410 to 414 are stored in the packet management queue 101 and the packet 409 has not been received yet. The reception time of the first packet 410 is 10: 00: 00: 500, and packets 411 to 414 are stored in ascending order of the sequence numbers following the packet 410. Assume that the predetermined buffering or waiting time in the packet management queue is 300 ms, and the time 10: 00: 600: 600 has elapsed. Therefore, the management unit 124 sequentially transmits packets from the first packet 410 to the oldest packet 413 according to the flowchart of FIG. The next packet 404 is not transmitted at this stage unless its sequence number is a number that is consecutive to the sequence number of the packet 413.
The routing device must forward the packet as soon as possible. That is, it is desirable that the time for holding the packet in the packet management queue is as short as possible. Therefore, instead of simply determining the buffering time of the packet based on the setting of the routing control device, the time for holding the packet in the buffer may be dynamically determined based on the actual reception state of the packet. In order to determine the holding time, the routing device receives the reception time between adjacent packets arranged according to the sequence number in the queue from the reception time and sequence number of each packet. The received packets are extracted at the maximum time interval in an order different from the order number. For example, in the example of the reception state as shown in FIG. 8B, the time interval between the packets 412 and 413 received in the maximum time interval in an order different from the order number is -240 ms. Such calculation is performed periodically, and the maximum time for holding the packet in the packet management queue is dynamically changed based on the maximum time interval. The holding time may be obtained by adding a certain time to the maximum time interval or by multiplying a certain coefficient in order to provide a margin.
Next, a description will be given of a method for determining which of the routing control devices in the network has the function of correcting the transmission order and which receiver is to correct the transmission order of packets addressed to the receiver. The simplest method is a method of directly setting the conditions of the received packet whose transmission order is corrected, such as the address, port, and protocol to be corrected, to all or selected routing control devices.
FIGS. 9A and 9B show which of the routing devices 912 to 920 in the network has a function of correcting the transmission order and the order of packets to which receiver 942 according to the request from the receiver 942. It shows how to automatically decide what to do. With reference to FIGS. 9A and 9B, an example in which a receiver requests and transmits a program to the transmitter will be described. However, what is requested to be transmitted is a program such as a video and audio program (program). Any content and information may be used without limitation.
In FIG. 9A, a receiver 942 requests and sends a series of packets representing a program to a transmitter 902 over a network according to a user request or a request of an application running on the receiver 942. A packet requesting to correct the order of is transmitted. This request packet includes an instruction that causes the first routing control device that has received the packet to set a function for correcting the order of the packets and a condition therefor. This request packet is transmitted to the transmitter 902 via the paths 954, 956, 958, and 960 and the path control devices 920, 918, 916, and 912, for example. In this case, the route control device 920 that first and directly receives the request packet from the receiver 942 is set to execute control for correcting the order of a series of packets of the program transmitted from the transmitter 902 to the receiver 942. Is done. The route control device 920 deletes the command in the request packet and transmits the request packet requesting program transmission without the command to the next route control device 916. When the routing control device 920 receives a packet addressed to the receiver 942 from the transmitter 902 and directly transmits the packet to the receiver 942, the routing control device 920 performs control for correcting the order of the packets.
In FIG. 9B, the receiver 942 requests the program transmitter 902 to transmit a series of packets representing a program over the network in accordance with a user request or a request of an application running on the receiver 942. Send a packet requesting to correct the packet order. The request packet is transmitted from the receiver 942 to the transmitter 902 in the form illustrated in FIG. 9A. In response to receiving the request packet, the transmitter 902 transmits a response or a reply packet to the receiver 942. The response packet is transmitted from the transmitter 902 to the receiver 942 via all possible paths 962, 964, 966, 968 and 970 in the network and the path controllers 912, 916, 918 and 920.
The response packet includes an instruction that causes the path control device that has received the same response packet a plurality of times or from a plurality of routes to set a function for correcting the order of the packets and a condition therefor. In this case, the route control device 918 that has received the same response packet a plurality of times or from a plurality of routes executes control to correct the order of a series of packets of the program transmitted from the program transmitter 902 to the program receiver 942. Is set. The route control device 918 discards the second response packet when the same response packet is received a plurality of times. Accordingly, it is possible to set so that the packet order is corrected only in a route control apparatus that may receive a packet from the transmitter 902 through a plurality of routes.
When the time stamp is added to the packet, the routing apparatus may correct the transmission jitter by adjusting the transmission interval based on the time stamp instead of simply correcting the transmission order. In this case, the management unit 124 needs to hold a time stamp as packet management data. For each packet management queue, the management unit 124 calculates at which time the next packet is transmitted from the difference between the reception time and the time stamp. At the time of the calculation, the management unit 124 determines whether the packet is corrected and inserted according to the sequence number between the received packets in the packet management queue, that is, the packet received later and the packet having the subsequent sequence number. Calculate the difference in reception time. The management unit 124 determines the transmission time of the packet in the packet management queue based on the inserted packet having the largest difference.
FIG. 10 is useful for explaining a method of correcting transmission jitter in a path control device. Assume that packets 501, 503, and 504 are sequentially received, and then packet 502 is received. Assume that the reception time of the packet 502 is received with a delay of 180 ms from the reception time of the packet 503 having the subsequent sequence number. The difference between the reception time of this packet 502 and the reception time of the subsequent packet 503 is the largest. Therefore, the transmission time of the packets 501 to 504 in the packet management queue is determined based on the packet 502. The reception time and time stamp of the packet 502 are 10020 and 10: 00: 00: 500, respectively, and the delay of 180 ms from the packet 503 has a margin of 20 ms with respect to the waiting time 200 ms of the packet management queue. . Therefore, for the packet of the time stamp 10020, 10: 00: 0: 520 obtained by adding the extra time 20 ms to the reception time is determined as the transmission time. The other packets 501, 503, and 504 determine their transmission times based on the difference between their respective time stamps and the time stamp of the reference packet 502. For example, since the time stamp of the packet 501 is 10000 and is 20 ms smaller than the time stamp 10020 of the reference packet 502, the packet 501 is set to 10: 00: 0: 500, which is 20 ms earlier than the transmission time 10: 00: 0: 520 of the packet 502. The transmission time is 501. In this way, by correcting the jitter of the packet by the path control device, the processing load for jitter correction in the receiver can be reduced.
The embodiments described above are merely given as typical examples, and variations and variations thereof will be apparent to those skilled in the art. Those skilled in the art will depart from the principles of the present invention and the scope of the invention described in the claims. Obviously, various modifications of the above-described embodiment can be made.

Claims (9)

A route control device connectable to a network,
Receives a series of packets addressed to a predetermined receiver from a predetermined transmitter and having a sequence number, temporarily stores them in a queue for each destination, and relates to the reception order of the packets for each stored destination And a routing device comprising a processor configured to transmit the stored packets according to the sequence number. The processor determines whether the received packet satisfies a predetermined condition for correcting the order of transmission of the packet with respect to the order of reception, and stores only the matching packet in a queue. The apparatus of claim 1. When a packet having the sequence number next to the sequence number of the last transmitted packet is not received and a predetermined time has elapsed from the reception time of the earliest received packet among the packets stored in the queue 2. The apparatus of claim 1, wherein the processor sends out the earliest received packet and packets in the queue having a lower sequence number. The apparatus according to claim 1, wherein the processor discards a packet having the smaller sequence number when receiving a packet having a sequence number smaller than the sequence number of the last transmitted packet. The apparatus of claim 1, wherein the processor transmits the stored packet according to the sequence number in accordance with a request in a packet addressed to the transmitter from the receiver. The apparatus according to claim 1, wherein the processor transmits the stored packet according to the sequence number according to a request in a response packet addressed to the receiver from the transmitter. 2. The processor according to claim 1, wherein the processor determines a maximum retention time of packets stored in the queue based on a difference in reception time between packets received in a different order with respect to a sequence number. Equipment. The apparatus according to claim 1, wherein the processor transmits the packet after correcting jitter of the packet according to a time stamp added to the packet. A program for a routing device connectable to a network,
Receiving a series of packets addressed to a predetermined receiver from a predetermined transmitter and having a sequence number, and temporarily storing them in a queue for each destination;
Transmitting the stored packet according to the sequence number regardless of the order of reception of the packet for each stored destination;
A program that can run to run.

Images