KR20060015051A - Method for setting of routing path in multi protocol label switch network - Google Patents

Abstract

The present invention discloses a method for establishing a quality of service guaranteed routing path in a multiprotocol label switching network.

The routing path establishment method of the present invention includes a first step of calculating a future traffic inflow to be introduced to any transmission label edge router (LER); A second step of calculating all possible routing paths between the arbitrary transmitting label edge routers and the receiving label edge routers based on the network shape and the future traffic inflow, and calculating the weight of each link in the calculated routing paths; A third step of calculating an order value of a router and a link in the routing path in consideration of a hop count and an end-to-end delay based on the calculated weight of the link; And a fourth step of calculating a routing path that satisfies the bandwidth and end-to-end delay requested by the user based on the order value, and based on the future traffic demand prediction result and the traffic volume in the current network configuration. By setting up the network, it provides the maximum path with the same network resources, thus maximizing the utilization of the network resources and thus generating the maximum profit from the same network resources.

Description

Method for setting of routing path in multi protocol label switch network}

1 is a configuration diagram illustrating a problem of calculating a routing path in a general MPLS network.

2 is a flowchart illustrating a routing path establishment method according to the present invention.

3 is a network diagram of a multiprotocol label switching network according to an embodiment of the present invention;

FIG. 4 is a table showing all possible routing paths between transmission / reception points and each link cost calculated based on the assumption that different traffics are introduced at three transmission points a, e, and g in the network configuration of FIG. drawing.

5 is a diagram illustrating the weight w of each link E _ij calculated in consideration of the inflow traffic amount in FIG. 4 in the form of E _ij (w). FIG.

6 is a diagram showing order values for routers and links calculated in consideration of hop count and end-to-end delay in accordance with the present invention.

FIG. 7 is a diagram for explaining a process of calculating an optimal routing path that satisfies user requirements. FIG.

The present invention relates to a method for calculating an optimal routing path that can satisfy a quality of service in a multi-protocol label switching (MPLS) network, and more particularly, between arbitrary transmission / reception points. When setting the label switching path, the path is set based on the result of forecasting traffic demand and the amount of traffic in the current network configuration to maximize the utilization of network resources by providing the maximum LSP with the same network resources. It is about how to set up a routing path that allows you to make the most profit from your resources.

MPLS is a standard technology developed to speed up network traffic and make management easier. It establishes a specific path for a given packet sequence. Each packet is attached with a label, and a Label Switched Router (LSR) includes a Forwarded Information Base (FIB) storing routing information for setting a routing path according to a label, and routing of the corresponding packet is performed. .

The LSR corresponding to each hop (HOP) allows the packet to be transmitted to the receiving side by changing the label of the packet and transmitting the packet when routing the corresponding packet.

Meanwhile, a Label Switched Path (LSP) formed through a plurality of LSRs is used by a network operator to ensure a specific performance level, avoid network bottlenecks, and create an IP tunnel for a network-based virtual private network. These LSPs do not differ from circuit switch paths in asynchronous transfer mode (ATM) or frame relay networks, except that they do not rely on specific Layer 2 technology.

Because LSPs can be configured for various Layer 2 transmissions, such as ATM, Frame Relay, or Ethernet, MPLS has end-to-end performance over any transmission medium, eliminating the need for network duplexing or Layer 2-specific control mechanisms. It has the advantage of being able to create (end-to-end) circuits.

According to the MPLS technology, it is possible to provide a quality assurance type internet service that has not been provided in the existing Internet network for data service provision. In other words, in the MPLS technology for providing quality assurance Internet service, an Internet service capable of quality assurance by transmitting an LSP having an arbitrary band between a transmitting Label Edge Router (LER) and a receiving Label Edge Router in advance and transmitting traffic It can be provided.

In MPLS network, a series of technologies that efficiently operate the network and always satisfy the quality of service desired by the network user is defined as traffic engineering (TE). Constraints-based shortest path first (CSPF) algorithms were impossible.                         

In the existing Internet network, congestion occurs by using the shortest path line algorithm, always selecting the shortest routing path between the same transmitting / receiving MPLS switching nodes regardless of the state of the network and always delivering MPLS traffic over the same routing path. It was. CSPF solves this problem and changes the routing path by adding constraints such as bandwidth and end-to-end delay to the shortest route line algorithm of the existing Internet network. Unlike the existing Internet network, the shortest path is selected. Select routing paths that satisfy the same constraints to avoid network congestion.

The network has a situation in which it is impossible to provide stable data transmission service due to congestion or failure of traffic.If an LSP is established between arbitrary transmission / reception points according to the network configuration, a path between multiple transmission / reception points There is a possibility that a situation that cannot be set may occur.

1 is a configuration diagram illustrating a problem of calculating a routing path in a general MPLS network.

In FIG. 1, the MPLS network is composed of LERs LER1 to LER6 and LSRs LSR1 to LSR3, and the LER and LSRs are connected by a link to form LSPs (LSP-1 to LSP-3). In this case, the LER is a router serving as a transmitting / receiving point, and the LSR serves to transfer MPLS packets between the LERs, which are transmitting and receiving point routers.

In FIG. 1, if the bandwidth of all links is assumed to be 10 Mbps, if an attempt is made to set an LSP having a bandwidth of 10 Mbps between LER1 and LER2, the LSP is an LSP- via the <LER1-LSR1-LSR2- LSR3-LER2> router. 1 is set and uses the link bandwidth between these routers. At this time, the link between LER1 and LSR1, the link between LSR1 and LSR2, the link between LSR2 and LSR3, and the link bandwidth 10Mbps between LSR3 and LER2 are all used to set LSP1.

Under this situation, if you attempt to set up an LSP-2 with a bandwidth of 10 Mbps between LER3 and LER5, the possible routing path could be <LER3-LSR1-LSR2-LER5>, but the link bandwidth between LSR1 and LSR2 is already LSP-. Since it is used to set 1, the LSP-2 cannot be set between LER3 and LER5. In addition, even when trying to set LSP-3 having a bandwidth of 10 Mbps between LER4 and LER6, the possible routing path may be <LER4-LSR2-LSR3-LER6>, but the link bandwidth between LSR2 and LSR3 is already LSP-1. Since it is used to set the LSP-3 between LER4 and LER6, the LSP-3 cannot be set.

In order to solve this problem, the present invention provides a routing method capable of accommodating a maximum LSP based on demand prediction data between all possible transmission / reception points based on a network shape when setting an LSP between arbitrary transmission / reception points. It is about.

Accordingly, an object of the present invention to solve the above-mentioned problem is to establish a label switching path between arbitrary transmitting / receiving points in an MPLS network based on the future traffic demand prediction result and the traffic volume in the current network configuration. By setting up the network, it is possible to maximize the utilization of network resources by providing the maximum LSP with the same network resources so that the maximum profit can be generated with the same network resources.

In order to achieve the above object, a method for establishing a quality of service routing path in a multiprotocol label switching network according to the present invention includes: a first step of calculating future traffic inflow to be introduced into an arbitrary transmission label edge router (LER); A second step of calculating all possible routing paths between the arbitrary transmitting label edge routers and the receiving label edge routers based on the network shape and the future traffic inflow, and calculating the weight of each link in the calculated routing paths; A third step of calculating an order value of a router and a link in the routing path in consideration of a hop count and an end-to-end delay based on the calculated weight of the link; And a fourth step of calculating a routing path that satisfies the bandwidth and end-to-end delay requested by the user based on the order value.

Hereinafter, with reference to the accompanying drawings will be described in detail a preferred embodiment of the present invention.

2 is a flowchart illustrating a routing path establishment method according to the present invention.

First, the routing path setting method of the present invention will be briefly described as follows.

First, the future traffic inflows for any transmission point (transmission LER) in a given MPLS network are calculated, and then all possible routing paths between the transmission / reception points requested by the user are calculated based on the network shape and the calculated traffic in advance. . Next, a weight for each link of the calculated routing path is calculated, and an order value of each router and link on the path is calculated based on the calculated link weight. The optimal routing path is calculated based on the calculated order value.

Each routing path establishment process in FIG. 2 is described in more detail with reference to FIGS. 3 to 7.

3 is a diagram illustrating a network configuration of a multiprotocol label switching network according to an exemplary embodiment of the present invention.

First, the future traffic inflow amount at any transmission point (transmission LER) in the MPLS network shape of FIG. 3 is calculated (step 210).

In FIG. 3, the amount of future traffic to be introduced into each transmitting LER (a, e, g) is represented by T _LOAD .

In this embodiment, under the MPLS network environment as shown in FIG. 3, 100 Mbps of MPLS traffic flows between the transmitting LER (a) and the receiving LER (d), and 5 Mbps between the transmitting LER (e) and the receiving LER (f). It is assumed that the MPLS traffic of SMP is introduced and 5 Mbps MPLS traffic flows between the transmitting LER (g) and the transmitting LER (m). In FIG. 3, E _{i, j} means a link between router i and router j.

Next, after calculating all possible routing paths between any transmission / reception points based on the shape of the MPLS network and the future traffic inflow, the weight of the link is calculated based on this (step 220).

Under the assumption that different MPLS traffic can be introduced between three transmitting / receiving points in the network environment as shown in FIG. 3, all possible routing path calculations and link weight calculations between arbitrary transmitting / receiving points are performed in the following manner. .

FIG. 4 is a table showing all possible routing paths between transmission / reception points and each link cost calculated based on the assumption that different traffics are introduced at three transmission points a, e, and g in the network configuration of FIG. will be.

At this time, the weight of the link is calculated using a link weight calculation algorithm (hereinafter referred to as LWCA: Link Weight Computation Algorithm).

In FIG. 4, E _ij (d) denotes a delay for a link between router i and router j, and a unit is ms. In this embodiment, the delay for each link is defined as in FIG. 4. .

E _ij (ava) denotes the available bandwidth on the link between router i and router j. The unit is Mbps. In this embodiment, the available bandwidth for all links is defined as 500 Mbps.

T _load (Si) (i = 1, 2, 3) indicates the amount of traffic to be flowed from each of the three transmission LERs (a, e, g) and is in Mbps, and in this embodiment, flows into transmission point S1. The amount of traffic to be defined is 100 Mbps, the amount of traffic to be sent to transmission point S2 is 5 Mbps, and the amount of traffic to be transmitted to transmission point S3 is 5 Mbps.

P _candiate (Si, Di) represents all possible routing paths between any transmitting LER Si and receiving LER Di, where the routing paths are represented by a set of links. For example, in FIG. 4, there is one possible routing path between S1 and D1. The routing path is via links E _ab , E _bc and E _cd . Therefore, P _candiate (S1, D1) = {(E _ab , E _bc , E _cd )}. On the other hand, between S2 and D2 there is a route via links E _bc , E _eb and E _cf and a route through links E _eh , E _hk and E _kl , so P _candiate (S2, D2) = {(E _bc , E _eb , E _cf ), (E _eh , E _hk , E _kl )}. In the same way, there is a route between S3 and D3 via links E _gh , E _hk , E _kl and E _lm , so P _candiate (S3, D3) = {(E _gh , E _hk , E _kl , E _lm ) } Becomes

E _ij (cc) indicates the number of links between router i and router j included in the routing path when calculating a routing path between any transmitting / receiving point. For example, the link E _bc is included in both P _candiate (S1, D1) and P _candidate (S2, D2), so that E _bc (cc) = 2.

E _ij (load) represents the sum of total bandwidths required for a link between router i and router j included in calculating a routing path between any transmission / reception points to accommodate all of the routing paths. For example, in FIG. 4, link E _hk is included in the routing path between S2 and D2 and the routing path between S3 and D3. Therefore, the amount of bandwidth required for the link E _hk is 10 Mbps which adds up to 5 Mbps of traffic volume for the routing path between S2 and D2 and 5 Mbps of traffic volume for the routing path between S3 and D3.

E _ij (w) represents the weight of the link calculated by the LWCA algorithm for the link between router i and router j. E _ij (w) is calculated by a formula for calculating a link cost such as Equation (1).

For example, assuming that link E _ab (w) in FIG. 3 is normal, E _ab (w) = ((100 / 1,024) x 1 + (2 x 1,000)) = 2000.098.

In Equation 1, the normal and abnormal determination of the link is determined to be "abnormal" when the link is failing or the link delay is severe and normal traffic cannot be transmitted or the remaining lease bandwidth is no longer remaining. "Is determined.

As described above, when the calculation of the weight of the link according to the traffic inflow at any transmission point is completed, the order value which is the link weight considering the hop count and the end-to-end delay is calculated based on this (step 230).

The reason for calculating the link weight considering the hop count and the end-to-end delay is that the number of routing paths with less hop count when calculating the routing path between arbitrary transmitting / receiving points uses less network resources. This is to increase the utilization of network resources by calculating the routing path with.

FIG. 5 illustrates a weight w of each link E _ij calculated in consideration of the inflow traffic amount in FIG. 4 in the form of E _ij (w). This link weight w is used as input data for order value calculation in consideration of hop count and end-to-end delay.

In the MPLS network form of FIG. 5, it is assumed that requirements for LSP setting requested by a user are as follows.

LSP _request = P (S, D, b, d) = P (e, f, 10Mbps, 8ms)

In this case, P denotes a routing path to be calculated according to the LSP _request , S denotes a transmission LER, D denotes a reception LER, b denotes a request bandwidth for generating an LSP, and d denotes an end-to-end delay in generating an LSP.

That is, in the present embodiment, the user's requirement is defined as calculating a routing path having a 10Mbps bandwidth and end-to-end delay of 8ms or less between the transmitting LER (e) and the receiving LER (f).

FIG. 6 is a view showing order values for routers and links calculated in consideration of hop count and end-to-end delay according to the present invention.

The order fields E _ij [], N [] are added to all routers and links so that the order values of the links and routers considering the hop count can be stored. In FIG. 6, the order value of the link E _ij considering the hop count for the link between router i and router j is expressed in the form E _ij [od], and the order value of router N considering the hop count of any router N is N in the form [od]. That is, "od" represents the order value.

In order to calculate the order values of routers and links based on hop counts and end-to-end delays, the present invention searches from the receiving LER (f) to the transmitting LER (e) direction.

First, the order value of the receiving LER (f) is initialized to 0, and the order values of all remaining links and routers are initialized to infinity (∞).

The order value of the link considering the hop count of the link connected to any router is calculated by Equation 2.

From here,

E _ij (o) is the order value considering the hop count for the link between router i and router j, N (o) is the order value considering the hop count for any router N, E _ij (w) is router i and router Represents a weight value considering the traffic inflow for the link between j.

Since the order value of the receiving LER (f) is initialized to 0, the order values of the links E _cf and E _lf connected to the receiving LER (f) are calculated as follows.

In this embodiment, the link weight considering the traffic volume of the link E _cf is 2000.005, and the link order value for the current link E _cf is initialized to ∞. Therefore, since the order value ∞ for the existing link E _cf is greater than 1,000,000, which is the sum of the order value 0 of router f to 1,000,000, the order value E _cf (o) considering the hop count for the current link E _cf is The weight of the link is 2000.005 plus 1,000,000, resulting in 1002000.005.

In the same way, the order value of the link E _lf is 1001000.005.

In _addition , the order value N _neigh (o) for the neighbor router N _neigh connected to an arbitrary router N by link is calculated by Equation 3.

Thus, the received LER (f) and the order value for the LSR (c) link to a E _cf router, the order value of the reception LER link E _cf is associated with (f) E _ij (o) is 1002000.005 by equation (2) And the order value N _neigh (o) of the LSR (c), which is the neighboring router connected to the link E _cf , is initialized to ∞, so the order value of the link E _cf is changed to 1002000.005.

In the same way, the order value for the LSR (l), which is a router connected to the receiving LER (f) and the link E _lf , is changed to the order value of the link E _lf to be 1001000.005.

In this way, the order values for all routers and links are calculated as shown in FIG.                     

As shown in FIG. 6, when an order value for a mode router and a link is calculated, an optimal routing path having a minimum hop count among routing paths satisfying a bandwidth and end-to-end delay requested by a user is calculated based on the calculated order value. Calculation (step 240).

FIG. 7 is a diagram for explaining a process of calculating an optimal routing path that satisfies a user's requirement (S, D, b, d) = (e, f, 10 Mbps, 8 ms).

First, one of the links associated with it in the transmitting LER (e) is selected as the optimal link. In selecting the link, Equation 4 is used to determine whether the link satisfies the bandwidth and end-to-end delay requested by the user. In addition, Equation 4 is used to calculate an optimal path in consideration of various traffics to be introduced through the future predictable transmission LER (e).

The transmitting LER (e) selects the link having the minimum value by applying Equation 4 to the two links E _eb and E _eh connected to it. If Equation 4 is applied to the links E _eb and E _eh to obtain the remaining values, E _eh has less than E _eb . Therefore, the transmission LER (e) selects the link E _eh .

If, as a result of applying Equation 4, there are two or more links having the same value, Equation 5 is applied to select the link having the smallest quotient.

The reason for applying Equation 5 is to minimize the network resource utilization rate by selecting a routing path having a minimum hop count when two or more routing paths are selected in consideration of traffic inflow.

If there are a plurality of routing paths having a minimum hop count by applying Equation 5, Equation 6 is applied to select a routing path having a minimum end-to-end delay.

If the link E _eh is selected in the transmission LER (e) through the above-described process, the next E L _hk is optimally optimized in the same manner in the neighboring router LSR (h) connected through the corresponding link E _eh . We choose by link of.

Repeating the optimal link selection in each router until reaching the receiving LER (f) in this way yields an optimal routing path as shown by the thick arrows in FIG.                     

Through the three-step filtering process as described above, a method for calculating a routing path that can consider traffic inflows between arbitrary transmission / reception points and minimizes hop count and end-to-end delay can be realized.

As described above, the routing path setting method of the present invention uses the same network by setting the path based on the future traffic demand prediction result and the traffic volume in the current network shape when setting the label switching path between arbitrary transmission / reception points. It is possible to maximize the utilization of network resources by providing the maximum LSP with resources, thus generating the maximum profit from the same network resources.

Claims (7)

A first step of calculating future traffic inflows to be introduced to any outgoing label edge router (LER); A second step of calculating all possible routing paths between the arbitrary transmitting label edge routers and the receiving label edge routers based on the network shape and the future traffic inflow, and calculating the weight of each link in the calculated routing paths; A third step of calculating an order value of a router and a link in the routing path in consideration of a hop count and an end-to-end delay based on the calculated weight of the link; And Comprising a fourth step of calculating a routing path that satisfies the bandwidth and end-to-end delay requested by the user based on the order value. The method of claim 1, wherein the weight of each link is A method for establishing a quality of service routing path in a multiprotocol label switching network, which is calculated by a link weight calculation algorithm (LWCA) as shown in the following equation.

here, E _ij (load) is the sum of total bandwidths required for the link between router i and router j included in the calculation of the routing path between the transmitting label edge router and the receiving label edge router to accommodate the routing path, and E _ij (cc) is the router. The number of links between i and router j included in the routing path when calculating a routing path between any transmitting / receiving point, E _ij (d) is the delay of the link between router i and router j. The method of claim 1 or 2, wherein the third step After initializing the order value of the received label edge router to 0, and initializing the order values of all remaining links and routers to infinity (∞), And calculating an order value of a router and a link included in the routing path from the receiving label edge router toward the transmitting label edge router. The method of claim 3, wherein the order value of the link connected to the received label edge router is A method for establishing a quality guaranteed routing path in a multiprotocol label switching network, which is calculated by the following equation.

here, E _ij (o) is the order value considering the hop count for the link between router i and router j, N (o) is the order value considering the hop count for any router N, E _ij (w) is router i and router The link weight between j. The method of claim 4, wherein the fourth step When each router on the routing path has a plurality of links connected to the router, the routing path is calculated by selecting a link having a minimum value by applying the order value of the corresponding link to the following equation. Of Quality of Service Routing Routing Paths in.

Where E _ij (o) is the order value of the link between router i and router j. The method of claim 5, When there are a plurality of links having the same minimum value, in order to select a routing path having a minimum hop count, a multiprotocol label is selected by applying the order value of the corresponding link to the following equation. A method of establishing a quality assurance routing path in a switching network.

The method of claim 6, When there are a plurality of routing paths with the smallest hop count, in order to select the routing path with the smallest end-to-end delay, the path value having the minimum value is selected by applying the order value of the corresponding link to the following equation. Protocol Labeling A method of establishing a quality of service routing path in a switching network.

Images