KR100405807B1 - LSTs determining method for multicasting in MPLS network - Google Patents

Abstract

The present invention relates to a traffic path determination method for multicasting in a Multi-Protocol Label Switching (MPLS) network, comprising two tree paths and a tree for a single point-to-multipoint connection. Allows you to determine an alternative tree path for the path, but allows you to determine the source-based tree path rather than the destination-based tree path, and to determine the MPLS tree path when traffic requiring multicast arrives ingress. It can be applied to on-line method, and it considers not only the current network status but also the traffic demand that needs to be transmitted. To minimize the use of the label switching edge router (LER) in the MPLS network. To be able.

Description

Multiple traffic path determination method for multicasting in multi-protocol label switching network {LSTs determining method for multicasting in MPLS network}

The present invention relates to a method for determining a plurality of traffic paths for multicasting in a Multi-Protocol Label Switching (MPLS) network, and more particularly, to the rapid growth of the current Internet Protocol (IP) based network. In addition, multicasting is required for various multimedia information such as VOD, AOD, video conferencing, and internet movies. Such multicasting multimedia information is characteristically sensitive to network failure due to its characteristics. Therefore, in addition to the basic tree path (that is, the traffic path for multicasting), an alternative tree path to be set up in case of multicasting should be set separately, but in order to set the alternative tree path, the same bandwidth as the base tree path is used. Since this is required, two main tree paths and one alternate tree path By suggesting a method to effectively reduce the use of network resources, MPLS with a repair node exists in the on-line multicast tree path, that is, as in the case of protection switching. Make it applicable to your network.

MPLS is a popular technology for traffic engineering to guarantee the quality of service (QoS) for traffic transmitted from an Internet protocol (IP) network and to efficiently use network resources.

MPLS traffic engineering determines label switched paths (LSPs) in a variety of ways to better accommodate the varying QoS requirements of users' IP packets. This LSP is a point-to-point path connecting a single egress from a single ingress.

Meanwhile, with the rapid growth of IP-based, demand for various multimedia services such as VoIP, VOD, AOD, Internet movies, and video conferencing is increasing. In many of these multimedia services, a point-to-multipoint type of service is required. Providing a point-to-multipoint type of multimedia service using an LSP connecting point-to-point is a method for network resources. Poor in terms of utilization and / or quality of service management. This is because it is unicast multicasting to provide a multicasting service using the LSP.

Currently, the Internet Engineering Task Force (IETF) has internet drafts for MPLS label distribution using the existing multicast IP protocols PIM-SM and PIM-DM. Standardization work is in progress for multicast.

However, since the tree path determination used in the existing multicasting protocol is a destination-based method, it is not easy to properly reflect the intention of the service provider or the user.

In addition, existing studies on how to determine the multicast tree path to prepare for network failures are insufficient. Due to the nature of multicast traffic, high quality service for the transmitted traffic will be required. Therefore, deciding multicast tree path to prepare for network failure is very important. Moreover, the research on how to decide and set up alternative tree paths to effectively use network resources in preparation for network failures is weaker.

In addition, the destination-based method, which is an existing method, does not efficiently use network resources. Inefficient use of these resources results in poor service quality. In addition, in the conventional tree path determination method, since it is a tree path decision considering only the current network state, it does not consider the flow rate for the traffic that is currently required to be transmitted, which causes a problem that the traffic load is not distributed evenly over the network. .

The present invention was created to solve the existing problems in the technical background as described above, and its object is to determine two tree paths and alternative tree paths for the tree paths for a single point-to-multipoint connection. However, the on-line method of determining the MPLS tree path when the multicast-required traffic arrives ingress can be determined by the source-based tree path rather than the destination-based tree path. Label switching of MPLS networks by balancing the traffic loads across the network in consideration of the current network conditions as well as the traffic demands required for transmission, and minimizing the transmission costs incurred. Multi-protocol label made available for use on a label switching edge router (LER) It is an object of the present invention to provide a plurality of traffic path determination methods for multicasting in a switching network.

That is, according to the present invention, a method for determining a plurality of traffic paths for multicasting in a multi-protocol label switching network is designed to effectively reduce network resource waste while increasing tree paths and to prepare for a network failure. Is to provide.

1 is a diagram illustrating an example of a data communication network to which the MPLS scheme is applied;

2 is a diagram illustrating an example of an MPLS network having two tree paths and one alternative tree path proposed by the present invention.

3 is a block diagram of an apparatus to which the method of the present invention is applied;

4 is a flowchart illustrating a method of determining a plurality of traffic paths for multicasting in a multi-protocol label switching network according to an embodiment of the present invention.

※ Explanation of code for main part of drawing

31 input / output interface 32: switching structure,

33: memory 34: control unit

100: Data communication network with multi-protocol label switching

110: Ingress Label Edge Router

120: egress label edge router

130,131,132,133: Label Switch Router

In order to achieve the above object, a plurality of traffic path determination methods for multicasting in a multi-protocol label switching network according to the present invention are multicast in a data communication network to which a multi-protocol label switching (MPLS) scheme is applied. In the source-based determination method of the point-to-multipoint tree path (LST) for the transmission of traffic, among the entire link between the nodes and the nodes of the communication network, the current capacity to transmit traffic is currently A first step of creating a first network from which links having less than the traffic demand to be transmitted are removed; A second step of calculating a first distance information value for each link of the first network based on the traffic flow amount currently used on the link and the information on the traffic demand amount; A third step of determining a first point-to-multipoint traffic path based on the calculated first distance information value; Creating, in the communication network, a second network in which the spare capacity is less than or equal to the traffic demand and all links passing through the first point-to-multipoint traffic path are removed; A fifth step of determining a second point-to-multipoint traffic path based on the distance information value of each link of the second network among the first distance information values; A sixth step of dividing each of the traffic demands by a predetermined ratio on the determined first point-to-multipoint traffic path and the second point-to-multipoint traffic path; A seventh step of creating, in the communication network, a third network which is equal to or less than the larger value of the divided ratio and in which all the links passing through the first and second point-to-multipoint traffic paths are removed; An eighth step of calculating a second distance information value for each link of the third network based on the traffic demand amount and the segmentation amount; And determining a first point-to-multipoint traffic path based on the calculated first distance information value and using the same as an alternative path for the first and second point-to-multipoint traffic paths. It consists of 9 steps.

Hereinafter, a traffic path determination method for multicasting in a multi-protocol label switching network according to a preferred embodiment of the present invention will be described in detail with reference to the accompanying drawings.

In the present invention, a path for multicast is a tree connecting point-to-multipoint, which will be replaced by the term treepath, and likewise referred to below. Or alternative tree path) means a path determined to transmit traffic in place of the tree path when a failure occurs in the tree path (or the main tree path). In other words, the tree path in the MPLS network refers to the connection path from a single ingress router to a plurality of egress routers, and defines and uses the new term label switched tree (LST). Shall be.

1 is a diagram illustrating an example of a data communication network to which the MPLS scheme is applied. The network 100 includes a plurality of routers, and serves as an inlet of the network 100 to any data traffic among the plurality of routers. The router is called an Ingress Label Edge Router (LER) 110, and the router serving as an exit is called an Egress Label Edge Router 120. One or more routers serving as nodes of an intermediate path between the ingress LER 110 and the egress LER 120 are referred to as a label switching router (LSR) 130 and the ingress LER 110 The traffic path determined from the LSR 130 to the egress LER 120 is referred to as a label switch path (LSP1, LSP2). The LSP is an ingress LER 110. Determined for incoming traffic , In the figure, for example LSP1 means a path determined by 110 → 132 → 133 → 120, LSP2 refers to a path determined by 110 → 131 → 120.

FIG. 2 is a diagram illustrating an example of an MPLS network having two tree paths and one alternative tree path proposed by the present invention. As shown in FIG. When multicast traffic requiring multicast to Egress1) and Egress2 arrives at the ingress as a source, two tree paths determined for transmission of the arrived multicast traffic at that ingress, i.e. A first Label Switched Tree (LST1), a second Label Switched Tree (LST2), and one Replacement Tree Path (BT) are shown.

That is, the path of 'Ingress → LSR1 → LSR4 → Igres 1,2' indicated by the thick solid line represents the first tree path LST1, and the path of 'Ingress → LSR1 → LSR6 → Egress 1,2' The second tree path LST1 is represented, and the paths of 'ingress → LSR2 → LSR5 → egress 1,2 shown in bold dotted lines indicate the alternative tree path BT. These two tree paths (LST1, LST2) and one alternate tree path (BT) are source-based paths determined by the ingress when there is a need for multicast traffic.

For example, suppose that 10 multicast traffic transmissions are required from ingress to egress1 and egress2. The LST1 and LST2 are set in the ingress to be used in a normal situation other than a network failure. At this time, if 4 and 6 bandwidths are allocated for LST1 and LST2, 6 of the bandwidths allocated to LST1 and LST2 is set as 6 of the alternative tree path BT, and this alternative tree path BT is networked. Used in case of failure. In FIG. 2, LST1, LST2 and BT are set to respective paths that are guaranteed to be non-duplicated links and / or nodes with respect to each other.

FIG. 3 is a schematic block diagram of an apparatus for determining LSP and / or LST in the LER 110 and 120 of FIG. 1 and / or the ingress of FIG. 2, and is an input / output function serving as a data communication interface with an external device. An interface 31, a physical switching structure 32, a memory 33 for storing a routing table, a routing table stored in the memory 33 are created and the switching structure 32 is controlled according to the created and stored routing table. Control unit 34 for controlling the input / output of the traffic via the input / output interface 31, and the routing table stored in the memory 33 under the control of the control unit 34. Such LSPs and / or LSTs are also determined at the time of writing. Accordingly, the present invention described below may be applied to the control unit 34, and may be implemented. In particular, the present invention may be applied to the ingress LER as shown in FIG.

4 is a flowchart illustrating a method of determining a plurality of traffic paths for multicasting in a multi-protocol label switching network according to an embodiment of the present invention. The following information is already known to an ingress LER of an MPLS network. Premise. Physical topology, cost function (e.g., delay) for the network, initial and spare capacity of the network link, and traffic demand for traffic that currently requires multicasting (i.e. traffic demand to be transmitted). Routers on an MPLS network (LSRs) also assume that they know the information known to the ingress LER and have a copy function for label and traffic.

In addition, the symbols and definitions used to describe the present invention are as follows.

Let G be the network at which you want to determine LSP or LST for new traffic, and G = (m, n), m is the number of links, n is the number of nodes, and yi is the link i for network traffic. Allocated flows (i = 1, ..., m), (S, MG) are point-to-multipoints for multicast traffic demand, where S is the source MG is a multicast group. d is the demand for multicast traffic between S and MG, fi (xi) is the cost incurred when link i flow is xi (i = 1, ..., m), and fi '(xi) is xi flow Is the incremental cost per unit flow, where the differential function of fi (xi) (i = 1, ..., m), dist (i) is the distance of link i (i = 1, ..., m), G1 (z) is a network that removes links with less than z capacity in network G, G2 (z) is a network that removes links with less than z capacity in network G1 (z) and a link through which LST1 passes, and G3 (z ) Denotes a network in which the free capacity of the link is less than z in the network G2 (z) and a link from which the LST2 passes.

In FIG. 4, first, all of the nodes constituting the network G to which the MPLS scheme is applied and all the links between the nodes, remove all the links whose surplus capacity of the currently transportable link (hereinafter referred to as Ci) is less than the traffic demand d to be transmitted at present. In step S401, a new network G1 (d) is configured.

Subsequently, the distance information value dist (i) is obtained based on the traffic flow amount yi currently used for each link i of the network satisfying the G1 (d) and the information on the traffic demand amount d, wherein the yi and d For example, when information is used as a variable of the delay function fi (xi) as a cost function for each link, the distance information value dist (i) is obtained by differentiating the delay function fi (yi + d) based on Equation 1 below. Since it is defined as a result value of the function fi '(yi + / d), the corresponding distance information value is obtained using Equation 1 and yi and d value information (S402).

In Equation 1, i denotes a corresponding link (i = 1, ..., m) (m = total number of links), dist (i) is a distance information value of the link i, tci is the initial of the link i The capacity, yi is the amount of traffic flow in use on link i, and ci is the current spare capacity of link i, and a relationship of "ci = tci-yi" is established. In addition, if the delay function representing the delay on each link i is fi (xi), a formula of “fi (xi) = xi / (tci-xi)” is established, where xi is the amount of traffic passing through link i. If the derivative function of the delay function fi (xi) is fi '(xi), the expression " fi' (xi) = ci / (tci-xi) 2 " is established. Therefore, Equation 1 shows a result of arranging the delay function fi (xi) by putting yi + d instead of the variable xi in the derivative function fi '(xi).

That is, fi (xi) is a function of occurrence cost when the flow rate of link i is xi. In this embodiment, a delay function is used as an example of the cost function as described above, and fi '(xi) is the flow rate of link i. Is the increase cost function per unit flow, where is the derivative of the delay function.

For reference, the cost function is an example of using a delay function in the present invention, but is not limited thereto. The cost function may be a function for obtaining distance information on a link based on information on yi and d.

Next, based on the distance information value calculated for each link i of the network G1 (d) as above, the first point-to-multipoint tree path in that network G1 (d), i.e., (S, MG If LST1 is found in plural numbers, one LST is determined based on the principle of determining the tree path of a link having a relatively small calculated distance information as a tree path. It is preferable to determine only one, but the present invention is not limited thereto and may be a method for obtaining a desired optimal tree path (S403).

Next, we make network G2 (d) which removes all the links passing by the determined tree path LST1 in the network G which is less than d, and only takes into account the principle of disjointing only the links. In order to be non-duplicated, the network G generates a network G2 (d) from which all nodes are removed along with the link through which the determined tree path LST1 passes (S404).

Subsequently, distance information value dist (i) is obtained based on the traffic flow amount yi currently used for each link i of the generated network G2 (d) and the information on the traffic demand amount d, wherein the network G2 ( Since d) is included in the network G1 (d), the distance information value of each link i corresponds to the distance information value of each link i obtained in step S402. The tree path LST2 for the second point-to-multipoint tree path, that is, (S, MG) is obtained from the network G2 (d). Here, the method for obtaining the tree path LST2 is the same as the step S403, and the tree path LST2 is one of the main paths to be used as the basic tree path together with the first obtained tree path LST1 (S405).

Subsequently, the traffic demand amount d to be transmitted is allocated to q1 and q2 on the determined LST1 and LST2, respectively. More specifically, q1 and 4 are based on Equation 2, Equation 3, and Equation 4 below. xi is calculated while varying the ratio of q2 to a predetermined ratio, and the obtained value of xi is substituted into Equation 5 below, and the ratio of q1 to q2 when the resultant value of Equation 5 is minimum is determined. The total amount of traffic d to be transmitted on the LST1 and the LST2 is divided and allocated respectively.

, i = 1, ..., P _km (k = 1or2)]

,

Here, Equation 2 indicates that the multicast traffic demand d is satisfied by two tree paths LST1 and LST2, and q1 and q2 are divided into LST1 and LST2 so that the minimum cost is guaranteed as the solution of Equation 6 above. The amount of traffic to be allocated, d is the total amount of traffic to be transmitted, δ _i ¹ is ^{1 if} the tree path LST1 crosses link i; otherwise 0, δ _i ² is 1 if the tree path LST2 crosses link i, otherwise 0, P _km and q _km are the number of links of the tree path LST1 (k = 1) or the tree path LST2 (k = 2), ci represents the current redundant capacity of the link i, and Equation 3 is Indicates the flow amount to be allocated.

In this way, the traffic demand amount d is divided into quotas q1 and q2 so as to ensure a minimum cost, and then allocated, and a larger value of the quotas q1 and q2 is set to q _b (S406).

Next, in the network G, the free capacity is q _b or less and all the links passing through the tree paths LST1 and LST2 are removed to generate the network G3 (q _b ), but if the node is non-duplicated, the tree in the network G A network G3 (q _b ) having all the nodes removed along with the link through the paths LST1 and LST2 is generated (S407).

Finally, the distance information value dist (i) is calculated based on Equation 1 based on the traffic flow rate yi currently used for each link i of the generated network G3 (q _b ) and the information on the q _b value. In the same manner as in the step S402, but obtained by substituting q _b in Equation 1 instead of d. And based on the obtained distance information of each link, an alternative tree path (BT) is obtained from the network G3 (q _b ), wherein the method of obtaining the alternative tree path BT is performed in steps S403 and S405. The same alternative tree path is a spare path in case an abnormality occurs in the LST1 or LST2 path. Where q _b is the bandwidth allocated to the alternate tree path BT.

As described in detail above, a plurality of traffic path determining methods for multicasting in a multi-protocol label switching network according to the present invention may be determined as source-based tree paths rather than destination-based tree paths. It can be applied to the on-line method of determining the MPLS tree path when the required traffic arrives ingress, and considers not only the current network state but also the traffic demand that needs to be transmitted. It creates a balanced distribution of traffic load and minimizes the transmission costs incurred.

Therefore, according to the present invention, an alternative tree path may be established from the service provider's point of view, and network resources may be efficiently utilized. In other words, it is possible to efficiently use network resources and provide high-quality services by balancing the traffic to be transmitted to the entire network while reducing the transmission cost incurred for the traffic. Also, from the user's point of view, the service for some traffic is maintained by using the alternate tree path even if the link or node that the basic tree path passes through fails.

Claims (5)

In a data communication network to which multi-protocol label switching (MPLS) is applied, a source-based determination method of a point-to-multipoint tree path (LST) for transmission of multicast traffic, A first step of creating a first network from which links of a node and nodes of the communication network are removed, wherein links whose current traffic transmission capacity is less than a traffic demand to be transmitted at present are removed; A second step of calculating a first distance information value for each link of the first network based on the traffic flow amount currently used on the link and the information on the traffic demand amount; A third step of determining a first point-to-multipoint traffic path based on the calculated first distance information value; Creating, in the communication network, a second network in which the spare capacity is less than or equal to the traffic demand and all links passing through the first point-to-multipoint traffic path are removed; A fifth step of determining a second point-to-multipoint traffic path based on the distance information value of each link of the second network among the first distance information values; A sixth step of dividing each of the traffic demands by a predetermined ratio on the determined first point-to-multipoint traffic path and the second point-to-multipoint traffic path; A seventh step of creating, in the communication network, a third network which is equal to or less than the larger value of the divided ratio and in which all the links passing through the first and second point-to-multipoint traffic paths are removed; An eighth step of calculating a second distance information value for each link of the third network based on the traffic demand amount and the segmentation amount; And A ninth point for determining a first point-to-multipoint traffic path based on the calculated first distance information value, and using this as an alternative path for the first and second point-to-multipoint traffic paths; And a plurality of traffic path determination methods for multicasting in a multi-protocol label switching network. The method of claim 1, The second network generates and removes nodes passing through the first point-to-multipoint traffic path along with the corresponding link, and the third network creates the first and second point-to-multipoint traffic path. And removing nodes along with the corresponding link to generate multiple traffic paths for multicasting in a multi-protocol label switching network. The method of claim 1, In the second step, a delay function of each corresponding link is obtained based on the traffic flow amount, the traffic demand amount, or the information about the split amount, and the derivative value of the delay function is used as the first or second distance information value. A method for determining a plurality of traffic paths for multicasting in a multi-protocol label switching network. The method of claim 3, wherein The distance information value is " ", Where i denotes the corresponding link (i = 1, ...., m) (m = the total number of links), and dist (i) is the distance information value of the link i, tci Is the initial capacity of link i, yi is the traffic flow currently in use on link i, ci is the current spare capacity of link i, and a relationship of "ci = tci-yi" is established, and d is the traffic demand to be transmitted now. The method for determining a plurality of traffic paths for multicasting in a multi-protocol label switching network, wherein the division amount is substituted instead of d when the second distance information value is obtained. The method of claim 1, In the sixth step, xi is calculated while varying the ratio of q1 and q2 to a predetermined ratio based on Equation (1), Equation (2) and Equation (3) below, and calculates the xi value of Equation (4). ) And on the first point-to-multipoint traffic path and the second point-to-multipoint traffic path, depending on the ratio of q1 to q2 when the result of equation (4) becomes the minimum. And each of the traffic demands to be transmitted is divided and allocated to each other, wherein q1 and q2 are traffic amounts to be allocated to the first and second point-to-multipoint traffic paths, respectively, and d is to be transmitted. The total traffic amount, δ _i ¹ is ^{1 if} the first point-to-multipoint traffic path crosses link i; otherwise 0, δ _i ² is the second point-to-multipoint traffic path past link i 1, otherwise 0, P _km is the first point-to-multipoint traffic channel (k = 1) or the second point-to-multipoint Traffic path can link (k = 2), ci is showing the current spare capacity of link i, multi-plurality of traffic route determining method for multicasting in the protocol label switching network. --- (One) , i = 1, ..., P _km (k = 1or2) --- (2) , --- (3) --- (4)