Algorithm CR

 

Algorithm CR (Constraint-based Routing)

 

The CR (Constraint-based Routing) algorithm is applied when opening the way or if it reopens path is dynamic.

In addition to the topology constraints used by conventional routing algorithms, the CR algorithm calculates routes based on throughput constraints or administrative strip. The paths calculated by the RC protocol are not necessarily shorter. Indeed, the shortest path may not meet the bandwidth capacity requested by the LSP. The LSP can thus take another route, slower but have the required bandwidth capacity. In this way, traffic is distributed more evenly on the network.

Designing a system for MPLS traffic engineering requires browsing the following steps:

1. Definition of the geographic extent of the MPLS system. Depends on the political administrative and network architecture.

2. Definition of member routers of MPLS system. This is to define the LSR entry, transit and exit of the MPLS system. For various reasons, it does not necessarily contain all network routers, especially if a router is not powerful enough or if it is not secure.

3. Definition of the hierarchy of the MPLS system. Two cases are possible: connect all MPLS LSR system and create a single level of hierarchy forming a largest MPLS or divide the network into several levels of hierarchy system. In the latter case, the LSR of first and second level of the hierarchy, which form the heart of the network are heavily meshed.

4. Definition of bandwidth requirements of LSP. The bandwidth requirements can be set by the end-to-end traffic matrix, which is not always available, or a statistical calculation based on the exploitation of LSP and regular updating of this information by constantly monitoring their traffic.

5. Definition of paths LSP. The roads are generally calculated dynamically by a CR real time. Where it proves difficult to achieve this real-time calculation, you can use a non-real-time CR algorithm.

6. Setting priorities LSP. Most can be assigned high priority to the LSP elapse before a large traffic. This will take the most routes short and to avoid overloading a large number of links in the network, while providing stability of routing and better utilization of resources.

7. Set the number of parallel paths between any two ends. You can configure multiple paths in parallel with roads physically different. This ensures load distribution more uniform traffic. The idea underlying LSP is set small for a better flexibility routing. This flexibility is the primary motivation parallel LSP.

8. Definition of the affinity of LSP and links. Colors can be assigned and links to the LSP according to administrative constraints. These colors are used determining the paths to choose from for the LSP.

9. Definition of adaptation and flexibility attributes. According developments network behavior, it is possible to find optimal paths for the LSP already calculated. The network administrator can accept or reject a new optimization LSP. It is not necessary that it be too frequent, because it could introduce instability routing. It should also include mechanisms to LSP rerouting in case of failure of an LSR.

The operation of an MPLS network follows the steps listed below:

1. Collection of statistical data using LSP at system startup. The purpose of this step is to calculate the traffic rate between each pair of routers. Existing statistical methods used to calculate the rate of traffic at the input and at the output of an interface but not up to a particular destination. The construction of the butt-end traffic matrix is ​​performed by estimation, which makes engineering difficult and inefficient traffic. Using LSP starting a MPLS system gives precisely the traffic rate between any two ends depending on the destination.

2. Operation of LSP with bandwidth constraints defined in step Previous. Step 1 above that allowed knowing the band needs bandwidth of each LSP; this information is used by the algorithm to recalculate the CR LSP with their real need for bandwidth.

3. Periodic updating LSP bandwidths. A periodic update the bandwidths of the LSP is required to ensure the development and adaptation of the network to changing traffic in the network.

4. Running the CR algorithm in real time. For efficient use of links, CR algorithm must be run on a dedicated server. Calculated on a server having all the topology information and attributes of all LSPs, this algorithm can achieve real time. The algorithm offers LSP with better performances compared to those of LSP already open. The CR algorithm must run in real time to reflect a failure of one LSP. The algorithm can then quickly determine a new LSP able to handle the traffic waiting.