KR100429907B1 - Router and routing method for combined unicast and multicast traffic - Google Patents

Abstract

The present invention relates to a router capable of performing a routing service at a high speed in a packet communication network, a routing method, and a packet input / output setting method of a router. In the router packet input / output setting method according to the present invention, (a) checking whether the switching target packet exists by checking whether it is a scheduling time point, and (b) minimum completion time for switching the switching target packet to the corresponding output terminal. (C) adjust the value of the packet state information message to perform the switching within the calculated minimum completion time, (d) determine the object to be switched preferentially, and (e) the priority of the determined switching. Determining the maximum amount of switching that is available for allocation to the connection object.

According to the present invention, it is possible to efficiently perform a service for a multicast packet, thereby remarkably improving the processing time problem of the existing router.

Description

Router and routing method for unicast packet and multicast packet service {Router and routing method for combined unicast and multicast traffic}

The present invention relates to a high-speed router structure used in a packet communication network and a routing method using the same. More specifically, the present invention relates to a structure of a switching fabric for smooth connection of an input / output terminal of a packet and the use of the same for all packets. The present invention relates to a packet connection method between input and output terminals capable of minimizing connection processing time, and a connection setting apparatus corresponding thereto.

A router is an input / output terminal that handles the input / output of a packet, a forwarding engine that distinguishes the output terminal number of the packet from the input terminal, and delivers it to the switching fabric, and outputs each packet transmitted from the forwarding engine It consists of a switching network that connects to.

High speed routers require a forwarding engine to quickly and accurately understand routing information. If the correct output stage is not known, broadcasting is performed to all output terminals, causing unnecessary load and connection delay between the input and output terminals.

In addition, the packet connection method between the input and output terminals of the router according to the prior art does not distinguish between unicast traffic and multicast traffic, so that the same packets are copied to each input terminal and transmitted to each input terminal for multicast traffic processing. It takes a packet-like service, which increases the load on unnecessary routers and delays processing time, resulting in output blocking, which prevents the connection establishment directly on all packets requiring a connection. .

In order to reduce such packet collisions and increase packet throughput, an input buffering scheme and a routing scheme have been proposed. The input buffering method is to temporarily store packets by buffering at the input stage, which is suitable for implementing a high-speed switch because the switching speed of the switching network and the reading and writing speed of the buffer memory operate at the speed of the transmission link. Only one packet can be sent in the network, and only one packet is accepted at one output.

As a result, problems such as an input-buffering collision and an output-buffering collision phenomenon occur. In this case, the output collision is a collision that occurs when several inputs are sent to a specific output at the same time, and the input collision is an output collision. This means that a connection cannot be made due to the limitation that only one packet can be processed at one input terminal.

The conventional routing method performs an I / O connection routing method for every packet connection, which causes a deterioration in transmission quality because of a delay in processing time to find routing for every packet.

An object of the present invention for solving the above problems of the prior art is a VOQ for separate multicast traffic in addition to a plurality of VOQ (Virtual Output Queue, VOQ) for unicast packet traffic at the input terminal It utilizes VOQ type packet standby memory structure with one structure, uses one cross-bar switch for unicast packet connection service, and uses multiple buses for multicast packet connection service. By developing a router structure to utilize, not only to provide an efficient multicast packet connection service, but also to reduce the overall packet connection service processing time by reducing the amount of unicast connection service processing.

In addition, we have developed a method of establishing a packet connection between the input and output terminals and a connection setting device for minimizing the total packet processing time in such a router to improve the utilization of the router and to provide fast service processing in the entire packet network. It is an object of the present invention to provide.

1 is a functional diagram of a high speed router according to an embodiment of the present invention.

2 is a block diagram of the input unit illustrated in FIG. 1.

3 is a functional diagram of a router for multicast packet processing according to an embodiment of the present invention.

4 is a configuration diagram of a port state information message used when determining packet connection priority.

5 is a flowchart illustrating a packet configuration method for a fast router according to the present invention.

6 is a functional diagram of a connection setting apparatus for performing a packet setting method of the present invention.

The present invention for achieving the above object includes the invention and the method invention as follows. In the method invention, first, in the method of setting a packet input / output of a router, a step of checking whether a packet to be switched exists and a step of calculating a minimum completion time for connecting all pending packets if a target packet exists. Adjusting a value of a packet state information message to be described later, determining a priority connection target of switching, and then determining a maximum possible amount of switching.

The routing method may include an input step of receiving and managing information to be delivered, a switching step of determining a priority of a connection and a switching order, and an output step of outputting a forwarded packet.

In addition to the above-described method invention, in the device invention, a router first includes an input unit for storing output stage information to which unicast and multicast packets are delivered, a switching unit for determining a packet connection priority and a switching order, and And an output unit for outputting the transmitted packet.

Hereinafter, a structure of a high speed router, a packet connection method between an input / output terminal, and a connection setting device will be described in detail with reference to the accompanying drawings.

1 is a functional diagram of a high speed router according to an embodiment of the present invention. As shown, the high-speed router is composed of a plurality of input unit 110, the switching unit 120, a plurality of output unit 130, the switching unit 120 is one connection setting unit 121, one uni It is composed of a cast packet switching unit 122 and a plurality of multicast packet switching unit 123.

The input unit 110 and the output unit 130 perform a connection function between a physical layer and a media access control (MAC) layer, and lookup and buffering for packet forwarding. Perform the function.

The switching unit 120 has a built-in one packet connection setting unit 121 according to the present invention, and when the connection with the output terminal is established, performs a switching function to determine the switching order, and performs the switching Intensive control management of switching network. In addition, according to the packet setting method, one of the packets waiting at each input terminal is selected and connected to the output terminal, respectively.

2 is a configuration diagram of the input unit 110, and as shown, the input unit 110 includes a forwarding function unit 210 and a plurality of standby memories 220. The forwarding function unit 210 distinguishes the output stage for each packet when the packets enter the input terminal. If the output stage for each packet cannot be distinguished, it waits in the multicast standby memory 222 which is one of the VOQs in the memory in the form of broadcasting. The packet identified as output i is waiting in standby memory 221 i, which is one of VOQs, waiting for a turn to be connected to output i.

The unicast packet switching unit 122 of FIG. 1 constituting the switching unit uses an N × N cross-bar switch to enable packet connection between N input and output terminals. The multicast packet switching unit 123 has the configuration as shown in FIG. 3, and has a structure in which Y buses 310 are connected to the multicast packet standby memory 222 provided for each input terminal. Packets waiting in the multicast packet standby memory i are delivered to the desired output terminal 130 through one of the Y buses 310 in the connection order determined by the packet connection establishment method of the present invention.

The output unit 130 has a structure in which an input terminal for a unicast packet and an input terminal for a multicast packet are connected to each other, so that a packet coming from an input terminal of a unicast packet is established as an output terminal as a connection request comes in. However, for packets coming from the multicast packet input end, it checks whether it is a packet to its output end, and if it is an output packet to itself, it connects to its output end, otherwise discards the packet.

In the present invention, since a connection request to a specific output terminal per one time slot has a connection setting unit 121 in which at least one packet of the unicast packet or the multicast packet is a connection request, the unicast packet and the multicast packet are the same time. The output port conflict does not occur due to the connection request to the same output.

Here, the message used in the connection setting unit 121 to determine the packet connection priority is as follows. 4 is a configuration diagram of a port state information message (PrtState) used when determining packet connection priority.

As shown in the figure, the port state information is for managing the state in which the packets identified by each output terminal are waiting in the VOQ of each input terminal through the forwarding engine, and the number of packets waiting for connection from each input terminal i to the output terminal j. The packet status information message NumPacket [i] [j] in the memory. FIG. 4 shows an embodiment of a 32X32 crossbar switch structure. The number of packets waiting in each VOQ is represented by one byte and used for establishing a packet connection.

5 is a flowchart illustrating a packet connection method between input and output terminals for a high speed router used in a packet switching network according to an embodiment of the present invention.

First, the high-speed router stays in a waiting state 510 waiting for a scheduling point or arrival of a new packet or output of a packet, and checks whether a new packet has been received or a waiting packet has been output (520). As a result, when a new packet is received at VOQ j of the input terminal i, the packet state information message of FIG. 4 is updated to NumPacket [i] [j] = NumPacket [i] [j] +1 (521), and one at VOQ. If the packet is outputted to the corresponding output terminal j, the packet status information message is updated to NumPacket [i] [j] = NumPacket [i] [j] -1 (521), and then waits again.

On the other hand, if the scheduling result is not the arrival of a new packet or the output of the packet, but a scheduling time, the packet connection scheduling using the packet status information message is performed. In other words, when scheduling every certain time T, scheduling is performed when T unit time elapses after the previous scheduling. If the value of the packet status information message NumPacket [i] [j] is not 0, the packet connection is set. Since the destination exists 540, packet connection scheduling is performed, but otherwise, the packet stays in the waiting state 510 again.

If there is a switching target, the minimum number of time slots required to output all waiting packets to the corresponding output terminal is calculated (541). The minimum time calculation (541) is Max { The smallest integer greater than NumPacket [i] [j] / N, The smallest integer greater than NumPacket [i] [N + 1] / Y, NumPacket [i] [j]} = B (B is the minimum time)

In order to complete the connection to the corresponding output terminal for all waiting packets within the calculated minimum completion time B, first, the NumPacket [i] [j] value, which is the currently waiting packet status information message, is set to SNPacket [i] [j] value. 542 performs packet connection establishment.

For the convenience of selecting packet allocation type that satisfies the constraint that only one packet should be allocated at each input / output terminal in each time slot. A dummy packet is added to the SNPacket [i] [j] value such that SNPacket [i] [j] = N × B. Since these virtual packets are just for convenience of packet connection establishment, they do not actually perform a connection service to the corresponding output terminal.

For example, given the value of SNPacket [i] [j] If, then, B = 22 by the minimum completion time calculation 541 and during the adjustment 542 of the SNPacket [i] [j] value. After adding the virtual packet, perform the following steps.

In order to prevent input collisions and output collisions, the packet connection configuration may allocate at most one waiting packet of VOQ at each input stage. The output stage for unicast packets can be accepted at most, but the output stage for multicast packets can output up to Y packets. A switching priority connection target that satisfies this constraint is determined (543).

For example, the value of the adjusted SNPacket [i] [j] about As shown in FIG. 1, an attempt may be made to first connect from an input terminal 1 to an output terminal 1, an input terminal 2 to a multicast output terminal 2, and an input terminal 3 to an output terminal 2. Here, 'O' indicates a connection target first, and 'X' indicates that it is not a target connection.

Next, the maximum amount that can be allocated is allocated to the determined switching priority connection target 543. In this process, only one packet can be handled in one time slot, so that the amount of connection processing to all connection targets is the same. The allocation is the maximum allocation and the remaining amount after allocation is calculated (544).

That is, the embodiment The maximum amount of the switching decision 544 possible for the switching priority connection target of the first priority is to connect the minimum of 10 packets among the priority packets. = {SNPacket [i] [j]}-{Priority Switching Packets} = Leave it as.

Lastly, to check whether the switching target packet exists (550), whether the current SNPacket [i] [j] values are all 0 or not, the SNPacket [i] [j] values are all If it is 0, the connection setup for all packets waiting in the VOQ is completed and thus stays in the waiting state 510 again.

However, if any one of the SNPacket [i] [j] values is not 0, there is a packet that has not been established yet. By performing the process to go to the standby state 510 to make an efficient packet connection for the high-speed router.

6 is a structural diagram of an input / output connection setting apparatus according to a packet input / output setting method of the present invention. In the drawing, first, there is a confirmation unit 610 that checks whether or not a packet to be switched at a scheduling time point exists. It examines the value of the value NumPacket [i] [j] of the packet state information message to determine whether it exists.

Next, there is a calculation unit 620 of the minimum completion time, which is responsible for calculating the minimum completion time of the connection for all waiting packets when there is a packet to be switched in the above step.

After that, the adjustment unit 630 sets the value of the current packet state information message to SNPacket [i] [j] in order to perform connection establishment within the minimum completion time, and then adds a virtual packet as described above to maximize the amount. It plays the role of preparing to carry out the switching decision.

Finally, there is a determining unit 640 of switching, which performs the function of determining the maximum possible amount of switching as described above.

So far I looked at the center of the preferred embodiment for the present invention. Those skilled in the art will appreciate that the present invention can be implemented in a modified form without departing from the essential features of the present invention. Therefore, the disclosed embodiments should be considered in descriptive sense only and not for purposes of limitation. The scope of the present invention is shown in the following claims rather than the foregoing description, and all differences within the scope will be construed as being included in the present invention.

As described above, according to the present invention, a multicast VOQ is provided at each input terminal and multicast is provided through a router having a structure in which a plurality of buses for these multicast packet connection services are placed in a switching fabric. The present invention is capable of efficiently servicing packets and significantly improving the processing load and processing time of existing routers by copying and processing all VOQs for unicast for multicast packet processing. Router structure can be effectively used for efficient packet connection service of high speed packet network.

In addition, the routing method, the packet setting method, and the connection setting device of the present invention are related to a packet connection scheme suitable for the router structure of the present invention, and are connected to all packets waiting for a connection from the VOQ to a corresponding output terminal at a time. By taking the setting method, the routing method is simplified because it does not need to process the packet connection at the beginning of every time slot, and only outputs to the corresponding output stage.

In addition, it provides a packet connection setting method that can complete the connection to the corresponding output terminal in minimum time by using information on all waiting packets together, thus increasing the number of packets processed per unit time. It is effective to let.

In addition, since the switching scheme according to the packet setting method of the present invention is connected to the maximum amount of packets possible with respect to the switching scheme determined once, the switching scheme between the input and output stages is performed in the form of using another switching scheme. This does not have to be changed every time slot, so the connection to the output stage can be handled quickly.

Claims (14)

(a) receiving a packet to be externally routed; (b) checking whether it is a scheduling time point, generating packet state information regarding the packet to be routed, and checking whether the packet to be routed exists; (c) calculating a minimum completion time required for routing when at least one packet to be routed exists; (d) adjusting a value of the packet state information so that all the packets to be routed can be routed within the minimum completion time; (e) determining a priority to be routed among all the packets to be routed; And, and (f) switching the packet to be routed so that a maximum number of packets can be simultaneously routed to the determined priority object to be routed. The method of claim 1, wherein step (c) Calculate the minimum completion time using the following equation, [Equation] B = Max { The smallest integer greater than NumPacket [i] [j] / N, The smallest integer greater than NumPacket [i] [N + 1] / Y, NumPacket [i] [j]} Here, B represents the minimum completion time, Max {a, b, c} means to select the largest number among a, b, c, NumPacket [i] [j] is the output j stage at the input i stage The packet information message, which is the number of packets waiting for connection establishment, is shown. N represents the number of input terminals and Y represents the number of buses. The method of claim 1, wherein step (d) A method of setting a packet input / output of a router, characterized by adding virtual packets so that the packet status information message is equal to the number of input terminals multiplied by the minimum completion time with respect to the total number of packets waiting to be connected. The method of claim 1, wherein step (e) Regarding the value of the adjusted packet state information message, a packet of a router characterized in that the connection object is first determined to have the largest value among the values of the adjusted packet state information message of a plurality of output terminals corresponding to each input terminal. How to set I / O. The method of claim 1, wherein step (f) The method of setting a packet input / output of a router, characterized in that the smallest value among the determined priority connection objects is determined as the maximum switching amount that can be allocated, and the maximum switching amount is assigned to the determined priority connection objects in common. The method of claim 1, After determining the maximum amount of switching that is available for allocation, examine whether there are any packets for which no switching connection has been determined, and if there are packets for which no connection has been determined, until no packets for which no connection has been determined exist. And repeating the steps (e) and (f). (a) receiving and managing output terminal information to which an input unicast packet is delivered and output terminal information to which a multicast packet is delivered; (b) determining a connection priority of a packet and determining a switching order when a connection with an output terminal is established; And, and (c) outputting a packet transferred from the input unit through the switching unit. The method of claim 7, wherein the step (a), Routing of a router characterized by checking whether a new packet has arrived or outputted a packet, and when a new packet has arrived or outputted a packet, updating a packet status information message indicating the number of packets waiting for a connection from an input terminal to an output terminal. Way. The method of claim 7, wherein step (b), (b1) checking whether a packet to be switched exists and calculating a minimum completion time for connection to all stages of all waiting packets, if any; (b2) adjusting a value of the packet status information message to perform a connection to a corresponding output terminal for all packets waiting in the calculated minimum completion time; And, (b3) determining the priority connection target of the switching, determining the maximum amount of switching available for allocation to the priority connection target of the determined switching, and removing the value of the adjusted packet state information message by the determined switching quantity. Router routing method characterized in that. At least one input unit configured to store output terminal information to which an input unicast packet is delivered and output terminal information to which a multicast packet is transmitted; A switching unit configured to perform a relay function of determining a connection priority of packets and determining a switching order when a connection with the output terminal is established; And, And at least one output unit for outputting a packet transmitted from the (additional) input unit through the (additional) switching unit. The method of claim 10, wherein the input unit, And a plurality of packet standby memories storing virtual output queues of unicast packets and multicast packets. The method of claim 10, wherein the switching unit The unicast packet includes a crossbar switch for connecting the packet from each input unit to an output unit; And The multicast packet router includes a switching network having a plurality of bus structures that receive a temporarily stored packet from the multicast packet standby memory of the input unit and provide a packet to the output unit. The method of claim 10, wherein the output unit And one output terminal for unicast packets and one output terminal for multicast packets. A computer-readable recording medium having recorded thereon a computer program capable of executing the method of any one of claims 1 to 9.