Mpls Gmpls

DE OLIVEIRA LAYOUT

7/3/07

11:46 AM

Page 38

Path-Computation-Element-Based Architecture for Interdomain MPLS/GMPLS Traffic Engineering: Overview and Performance Sukrit Dasgupta and Jaudelice C. de Oliveira, Drexel University Jean-Philippe Vasseur, Cisco Systems Abstract The Path Computation Element Working Group at the Internet Engineering Task Force is chartered to specify a PCE-based architecture for the path computation of interdomain MPLS- and GMPLS-based traffic engineered label switched paths. In this architecture, path computation does not occur at the head-end LSR, but on another path computation entity that may not be physically located on the headend LSR. This method is greatly different from the traditional “per-domain” approach to path computation. This article presents analysis and results that compare performance of the PCE architecture with the current state-of-the-art approach. Detailed simulations are undertaken on varied and realistic scenarios where preliminary results show several performance benefits from the deployment of PCE. To provide a complete overview of significant development taking place in this area, milestones and progress at the IETF PCE WG are also discussed.

W

ith ever increasing requirements posed by significant advances in networking, service providers may use traffic engineering (TE) techniques to efficiently manage resources and provide consistent quality of service (QoS). Traffic engineering in multiprotocol label switching (MPLS) and generalized MPLS (GMPLS) networks are fundamentally based on constraint-based path computation. Briefly, constraint-based path computation involves the pruning of links that do not satisfy constraints and subsequently using the shortest path algorithm on the resulting subgraph [1]. This process is simple and efficient when the path involves only one domain, but can potentially become severely resource heavy, complex, and inefficient when multiple domains are involved. To address this problem, the Path Computation Element (PCE) Working Group (WG) of the Internet Engineering Task Force (IETF) has been developing an architecture that will allow multidomain path computation to be simple and efficient. The PCE architecture introduces a special computational entity that will cooperate with similar entities to compute the best possible path through multiple domains. A PCE is a node that has special path computation ability and receives path computation requests from entities known as path computation clients (PCCs). The PCE holds limited routing information from other domains, allowing it to possibly compute better and shorter interdomain paths than those obtained using the traditional per-domain approach. Among other purposes, PCEs are also being advocated for CPU-intensive computations, minimal-cost- based TE-LSP placement, backup path computations, and bandwidth protection. Along with the process

38

0890-8044/07/$20.00 © 2007 IEEE

of identifying the requirements and development of the architecture accordingly, a plethora of work is underway at the PCE WG on the new communication protocols that will make this architecture work. This includes the development of new interPCE communication protocols and introducing extensions to existing underlying routing protocols. Request for Comments (RFC) 4655 [2] specifies a PCE-based architecture. RFC 4657 [3] covers PCE communication protocol generic requirements, and RFC 4674 [4] discusses the requirements for PCE discovery. Several WG IETF drafts are currently underway to define PCE communication protocol in different scenarios, PCE-based interlayer TE, protocol extensions for Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (ISIS) for PCE discovery, PCC-PCE communication, and policyenabled path computation. As is evident, a thorough performance study to justify and quantify the motivation for this new architecture is required. As the architecture is in its infancy, a detailed analysis comparing existing approaches to a PCE-based approach has never been undertaken. This article has been written with two goals in mind. First, it presents a brief review of the significant developments that have taken place in the PCE WG since it was conceived in the IETF. Second, it identifies the most significant performance metrics, and then presents detailed simulation results and accompanying analysis to contrast the performance of the existing approach with that of the PCE. The rest of the article is organized as follows. Several scenarios that motivate the use of a PCE-based architecture are highlighted. The PCE architecture is described. The two path computation approaches to be compared, PCE-based and per

IEEE Network • July/August 2007

DE OLIVEIRA LAYOUT

7/3/07

11:46 AM

Page 39

domain, are discussed. Performance metrics for comparison are identified, while the complete simulation scenario is described and the results are analyzed. Finally, we conclude the article.

Motivation for PCE The development of the PCE architecture has been motivated by numerous path computation requirements and scenarios arising in present-day provider networks. This section presents some scenarios that are aided by the presence of PCE. Several other scenarios are discussed in [2], as well as these: • Limited visibility: There are several situations where the node responsible for path computation has limited visibility of the network topology to the destination. In such cases, it is not possible to guarantee that the optimal (shortest) path will be computed, or even that a viable path will be discovered except, possibly, through repeated trial and error using crankback [5] or other signaling extensions. • Processing overhead: There are many situations where the computation of a path may be highly CPU-intensive (computation of Steiner trees, multicriteria path computation, etc.). In these situations, it may not be possible or desirable for some routers to perform path computation because of the constraints on their CPUs. • Limited routing capability: It is common in legacy optical networks for the network elements not to have a control plane or routing capability. Such network elements only have a data plane and a management plane, and all crossconnections are made from the management plane. It is desirable in this case to run the path computation on the PCE, and to send the cross-connection commands to each node on the computed path. • Multilayer networks: A server-layer network of one switching capability may support multiple networks of another (more granular) switching capability. The different clientand server-layer networks may be considered distinct path computation regions within a PCE domain, so the PCE architecture is useful to allow path computation from one client-layer network region, across the server-layer network, to another client-layer network region.

PCE Architecture Depending on the requirements of a provider, the PCE architecture can be deployed based on a single composite-node external and dedicated entity, or a cooperative set of multiple entities. On a PCE, a traffic engineering database (TED) is maintained and updated by the underlying routing protocol. The TED is then used to compute paths based on requests received by a PCC. When the PCE exists as a composite PCE node, the path computation and path setup request take place on the same physical network element. In contrast, a PCE that is external to the entity requesting a path setup uses the TED present on it for path computation, eventually returning the computed path as a response. Multiple PCEs can be involved in path computation in different scenarios. Depending on how PCEs across different domains are configured, several PCEs may be involved in path computation. A partial path returned by one PCE may require another partial path computation by another PCE to complete the path. Inter-PCE communication can also result in the computation of a single path in a cooperative manner. Based on the architecture, a provider can deploy a centralized or distributed computation model. The centralized model involves a single PCE for all path computation requirements in its domain. The distributed model may involve several PCEs that cooperate and share the path computation requests.

IEEE Network • July/August 2007

Path Computation and Setup This section gives a brief overview of the two path computation methodologies, the per-domain and the PCE-based approach respectively. Related issues that arise during path setup are also highlighted. Both approaches use the Constrained Shortest Path First (CSPF) algorithm [1]. CSPF first prunes all the links in the topology that do not satisfy the constraint (available bandwidth, delay, etc.) and then runs Dijkstra’s Shortest Path algorithm on the resulting subgraph. The metric used for this computation is the weight assigned to the links. In the analysis undertaken for this article, size of the TE-label switched path (LSP) (bandwidth to be reserved on every link of the path) is the only constraint considered. It should be noted that the path computed by CSPF always depends on the current load conditions of the network. Rerouting of TE-LSPs due to link failures and setup of other TE-LSPs prior to the current setup request are some factors that can result in the computation of different paths for the same request. Under any circumstance, though, CSPF will always return the shortest path satisfying the constraint corresponding to the current loading in the network. Working of the two path computation techniques is explained in Figs. 1b and 1c, respectively, and using the simple network in Fig. 1a.

Backward Recursive PCE-Based Computation Path computation across domains is particularly difficult as the visibility of a head-end router is restricted only to the domain it lies in. Backward Recursive PCE-Based Computation (BRPC) utilizes multiple PCEs to compute the shortest interdomain constrained path along a determined sequence of domains. Inherent in the PCE architecture, this technique also preserves confidentiality across domains, an important requirement when domains are managed by different service providers [6]. The BRPC procedure is backward, as the path is computed in a reverse fashion from the destination area to the source area. It is recursive since the same basic sequence of steps is repeated for every intermediate domain lying between the source and destination. Every domain has certain “entry” boundary nodes (BNs) into the domain and “exit” BNs out of the domain (into other domains). The following notation is defined for a clear explanation of the BRPC procedure. The entry BN of domain i joins domains i – 1 and i. Let the source and destination domains be denoted 0 and n, respectively, and n – 1 intermediate domains 1, ⋅ ⋅ ⋅, n – 1. For k (i), and the kth exit domain i, the kth entry BN is denoted BNen k (i). BRPC uses the concept of a virtual BN is denoted BN ex shortest path tree (VSPT). VSPT(i) denotes the multipoint-topoint (MP2P) tree formed by the set of constrained shortest paths from the entry BNs of domain i to the destination router. Each link of tree VSPT(i) represents a shortest path. The BRPC procedure is as follows. For the destination domain n, VSPT(n) is computed from the list of shortest paths to all the entry BNs from the destination node. This is illustrated in Fig. 1b. VSPT(n) is then sent to the PCEs in the previous domain (domain n – 1 in this case) where it is concatenated to their TEDs (as links). This TED is then used by the PCEs in domain n – 1 to compute VSPT(n – 1). This sequence is repeated until the source domain and subsequently the headend router of the TE-LSP areiou reached, as shown in Fig. 1b.

Per-Domain Path Computation In contrast to the BRPC procedure, the per-domain path computation technique involves the computation of individual path segments in every intermediate domain without the sharing of any path information from other domains. The complete path for a TE-LSP is obtained by concatenating the path

39

DE OLIVEIRA LAYOUT

7/3/07

11:46 AM

Page 40

segments that are computed for every domain i. Figure 1c illustrates a simple scenario of per-domain path computation. The head-end router computes the first path segment by finding the shortest path to the nearest exit BN. The second path segment is then computed for the second domain by this BN to the next nearest exit BN. This method does not necessarily always yield the shortest path across domains. Several setup issues arise after a path has been computed and the headend router of the tunnel tries to setup reservation along the route using the Resource Reservation Protocol with Traffic Engineering extensions (RSVP-TE) [7]. They result from outdated TEDs on any or all of the routers involved in the path computation process. The TED is maintained on every TE enabled router and holds information about several attributes of the links in its domain of existence. Path computation based on CSPF uses the TED and results in a path that satisfies the constraints put on one or a combination of these attributes. If the TED on the router computing the path is outdated, a call admission control (CAC) failure occurs at the entry point router of the link corresponding to the outdated information. In such a situation, if the underlying routing protocol is OSPF with TE extensions (OSPF-TE), a link state advertisement (LSA) is flooded, or if it is IS-IS, a link state packet (LSP) is flooded. This flooding updates the TEDs of all the routers with the most updated information with respect to the concerned link and is restricted only to the domain in which the CAC failure occurred. The per-domain and PCE approaches proceed differently in this situation. Details of LSA flooding and their mechanisms are explained in great detail in [1].

capacity or highly utilized links. The maximum and average path costs are observed for each TE-LSP. The distributions for the maximum and average path costs are analyzed.

PCE-Based Approach — The BRPC method [6] is used to k (i) and the destination. compute the VSPT between BN en When a CAC failure occurs, a new VSPT for that domain is computed, and path setup is retried in the domain. The number of CAC failures that take place with the PCE approach is at most equal to that with the per-domain approach.

TE-LSPs/Bandwidth Setup Capacity — Due to the different path computation techniques, there is a significant difference in the amount of TE-LSPs/bandwidth that can be set up. This metric captures the difference in the number of TE-LSPs and corresponding bandwidth that can be set up using the two techniques. The traffic matrix is continuously scaled and stopped when the first TE-LSP cannot be set up for both methods. The difference in the scaling factor gives the extra bandwidth that can be set up using the corresponding path computation technique.

Per-Domain Approach — Here, a crankback [5] is used to report a setup failure to the router that is trying to set up the path. For example, without any loss of generality, let the CAC k (i) was setting up a failure take place in domain i when BNen j path to BN ex(i). Upon receiving the failure information, k (i) tries to find a new shortest path to the next closest BN en (j+1) BNex (i). This process continues until no path can be found k (i) to any BN (i). In this situation, the setup failure from BNen ex k (i) is sent upstream to BN k (i – 1) in information from BN en en k (i – 1) then selects the domain i – 1 using a crankback. BNen (j+1) next BNex (i – 1) to enter domain i. Information about setup failures can propagate using the crankback to the source domain containing the headend router. This cycle repeats until a path can be set up or no path is found after exhausting all possibilities. It should be noted that crankback signaling is associated only with the per-domain approach to path computation. Several issues related to CAC and crankback signaling may arise, and can be found in [8, references therein].

Performance Metrics This section discusses the metrics used to capture and compare the performance of the two approaches. Path Cost — As the two path computation techniques differ significantly, paths and their corresponding costs can be very different. In our analysis, path cost is the sum of link metric/weight assigned to the links that constitute the path. A higher path cost is undesired since it could be representative of a total higher delay or may signify the traversal of low-

40

CAC Failures — As discussed in the previous section, CAC failures occur due to two reasons: a midpoint router having an outdated TED, or when an entry BN to a domain does not have a path in the domain. Although the former situation is common to both the per-domain and PCE-based approaches, the latter occurs only in the per-domain approach. This metric captures the total number of CAC failures that occur during initial setup and reroute (on link failure) of a TE-LSP. The distribution across all TE-LSPs is analyzed. Crankback Signaling — When an entry BN fails to find a route in the corresponding domain, crankback signaling takes place in the case of per-domain path computation. As discussed in the previous section, a crankback signaling message propagates to the entry BN of the previous domain, and a new entry BN to the next domain is chosen, after which path computation takes place to find a path segment to the new entry BN of the next domain. This causes a significant delay in setup time. This metric captures the distribution of the number of crankbacks and the corresponding delay in setup time for a TE-LSP when using the per-domain path computation technique. The total delay arising from the crankback signaling is proportional to the costs of the links over which the signal travels (i.e., the path which is setup from the entry BN of a domain to its exit BN). Similar to above, the distribution across TE-LSPs is analyzed.

Failed TE-LSPs/Bandwidth on Link Failure — Link failures are induced in the network during the course of the simulations conducted. This metric captures the number of TE-LSPs and the corresponding bandwidth that failed to find a route when one or more links lying its path failed.

Results and Analysis Simulation Setup A very detailed simulator has been developed to replicate a real-life network scenario accurately. Following is the set of entities used in the simulation with a brief description of their behavior. Topology Description — To obtain meaningful results applicable to present-day provider topologies, simulations have been run on two realistic topologies representative of current service provider deployments. They consists of a large backbone area to which four smaller areas are connected. For the first topology, named MESH-CORE, a highly connected backbone was obtained from RocketFuel [9]. The second topology has a symmetrical backbone and is called SYM-CORE. The four connected smaller areas are obtained from [10]. Details of the topologies are shown in Table 1 along with their layout in Fig. 2. All TE-LSPs set up on this network have their sources and destinations in different areas, and all of them need to traverse the backbone network. Table 1 also

IEEE Network • July/August 2007

DE OLIVEIRA LAYOUT

7/3/07

11:46 AM

Page 41

Domain (0) 1

Domain (1) 1

1

Domain (2)

1

1

1

1 5

1

1

S

D

3 BN0ex(i)

1

1

1

1

BN1en(i)

1

1

(a)

9 S

6

6 D

D

D

1

4 Domain (0)

1

Domain (1)

Domain (2)

VSPT(1)

VSPT(2)

Direction of path computation c

Represents a cost of c units (b)

4

3

2

S

D

Domain (0)

Domain (1)

Domain (2)

Direction of path computation c

Represents a cost of c units (c)

■ Figure 1. Interdomain path computation: a) example network with associated link costs; b) VSPTs formed by the BRPC procedure and their costs; c) per-domain path computation and costs of the path segments. shows the number of TE-LSPs that have their sources in the corresponding areas along with their size distribution. Node Behavior — Every node in the topology represents a router that maintains state for all the TE-LSPs passing through it. Each node is a source for TE-LSPs to all the other nodes in the other areas. As in a real-life scenario, where routers boot up at random points in time, the nodes in the topologies also start sending traffic on the TE-LSPs originating from them at a random start time (to take into account the different boot-up times). All nodes are up within an hour of the start of simulation. All nodes maintain a TED, which is updated using LSA updates as outlined in [1]. The LSA updates are restricted only to the domain in which they originate. The nodes have a path computation engine that operates on the routing information in the TED. In the per-domain approach, routing information is

IEEE Network • July/August 2007

limited only to the domain of existence. In the PCE approach, routing information is passed on to the domains according to the methodology outlined in the BRPC procedure [6]. TE-LSP Setup —When a node boots up, it tries to set up all the TE-LSPs that originate from it in descending order of size. The network is dimensioned such that all TE-LSPs can find a path. Once set up, all TE-LSPs stay in the network for the complete duration of the simulation. The traffic matrix represents a full mesh where there is a TE-LSP between every pair of nodes that lie in different areas.

Inducing Failures For thorough performance analysis and comparison, link failures are induced in all the areas. Each link in a domain can fail independently with a mean failure time of 24 h and be

41

DE OLIVEIRA LAYOUT

7/3/07

11:46 AM

Page 42

1d

2d

6b 1b4b 12b 67 26 9b 7b 11b 38 5b 3b 31 10b 14 29 22 2b 8b 16 1512 53 76 ABR-80-BB 32 ABR-81-BB 40 5234 68 19 37 55 45 60 54 39 28 30 47 27 20 ABR-A1-BB 3626 49 24 51 43 41 27 13 6a ABR-A0-BB 75 9a 57 33 58 83 ABR-D1-BB 81 3a 48 66 7d 6d 80 60 1a ABR-A2-BB 46 8a ABR-D0-BB 6 70 2a 7a 9 2 54 1d 2d ABR-C0-BB 14a 10a 73 4d 6c 3d 74 ABR-C2-BB 13a 10c 71 61 11a 12a 18 17 72 ABR-C1-BB 3c 1c 9c 78 11 14c 11c 13c 2c 17c 23 8c 4c 16c 7c 12c 15c

9a

5a

2a

6d 7d

4a

6a

3d 4d

ABR-D0-BB 9

11

12

12c 8c 16c 13c 14c 17c

10a

11a

1

16 17 6

2a

ABR-A0-BB 13

5

4

2

ABR-B0-BB

3

ABR-B1BB 7b 5b 3b 1b

ABR-C2BB 4c ABR-C1BB ABR-C0BB 5c 1c 7c 11c 6c 15c 3c 10c 9c 2c

(a)

1a 14a

14 15

18 8

12a

3a

ABR-A1-BB 10

7

8a 13a

ABR-A2-BB

5d ABR-D1-BB

2b

8b 10b

6b

11b

9b 4b 12b

(b)

■ Figure 2. Topologies used for the simulations: a) MESH-CORE; b) SYM-CORE. restored with a mean restore time of 15 min. Both interfailure and interrestore times are uniformly distributed. When a link fails, an LSA is flooded by the adjacent routers of the link, and all the TEDs of the routers lying in the same domain of existence are updated. When a link on the path of a TE-LSP fails, reservation is removed along the path, and the head-end router tries to set up the TE-LSP around the failure. No attempt to re-optimize the path of a TE-LSP is made when a link is restored. The links that join two domains never fail. This step has been taken to concentrate only on how link failures within domains affect performance.

and results were collected after the expiry of a transient period. Figures 3 and 4 illustrate the behavior of the metrics for topologies MESH-CORE and SYM-CORE, respectively.

Path Cost — Figures 3a and 4a show the distribution of the average path cost of the TE-LSPs for MESH-CORE and SYM-CORE, respectively. During initial setup, roughly 40 percent of TE-LSPs for MESH-CORE and 70 percent of TELSPs for SYM-CORE have path costs greater with the perdomain approach (PD-Setup) than with the PCE approach (PCE-Setup). This is due to the ability of the BRPC procedure to select the shortest available paths that satisfy the conResults and Analysis straints. Since the per-domain approach to path computation is undertaken in stages where every entry BN to a domain Simulations were carried out on the two topologies previously computes the path in the corresponding domain, the most described. The results are presented and discussed in this secoptimal route is not always found. When failures start to take tion. In the figures, PD-Setup and PCE-Setup represent results place in the network, TE-LSPs are rerouted over different corresponding to the initial setting up of TE-LSPs on an empty paths resulting in path costs that are different from the initial network using the per-domain and PCE approach, respectively. costs. PD-Failure and PCE-Failure in Figs. 3a and 4a show Similarly, PD-Failure and PCE-Failure denote the results under the distribution of the average path costs that the TE-LSPs the link failure scenario. A period of one week was simulated have over the duration of the simulation with link failures occurring. Similarly, the average path Domain description TE-LSP size costs with the per-domain approach are much higher than with the PCE approach when link # of # of OC-48 OC-192 [0,20) [20,100] failures occur. Figures 3b and 4b show similar Domain name nodes links links links Mb/s Mb/s trends and present the maximum path costs for a TE-LSP for the two topologies. It can be seen D1 17 24 18 6 125 368 that with per-domain path computation, the maximum path costs are larger for 30 percent and 100 percent of the TE-LSPs for MESH-CORE D2 14 17 12 5 76 186 and SYM-CORE, respectively. D3

19

26

20

6

14

20

D4

9

12

9

3

7

18

MESH backbone

83

167

132

35

0

0

SYM backbone

29

37

26

11

0

0

■ Table 1. Details of all the areas used to create the two topologies.

42

Crankbacks/Setup Delay — Due to crankbacks that take place in the per-domain approach to path computation, TE-LSP setup time is significantly increased. This could lead to QoS requirements not being met, especially during failures when rerouting needs to be quick in order to keep traffic disruption to a minimum. Since crankbacks do not take place during path computation with a PCE, setup delays are significantly reduced. Fig-

IEEE Network • July/August 2007

DE OLIVEIRA LAYOUT

7/3/07

11:46 AM

Page 43

45

110 PD setup PCE setup PD failure PCE failure

PD setup PCE setup PD failure PCE failure

100 90 Maximum path cost

Average path cost

40 35 30 25

80 70 60 50 40

20 15

30

0

40 60 Percentage of TE-LSPs

20

20 0

100

80

0

20

40 60 Percentage of TE-LSPs

(a)

(b)

16

Crankbacks

12

300 PD setup PCE setup PD failure PCE failure

250 Crankback delay

14

100

80

10 8 6

PD setup PCE setup PD failure PCE failure

200 150 100

4 50

2 0 60

65

70

75 80 85 Percentage of TE-LSPs

90

95

0 60

100

65

70

75 80 85 Percentage of TE-LSPs

(c)

16

PD failure PCE failure

400

1600

PD setup PCE setup PD failure PCE failure

8 6

1200 1000 800 600

4

250 200 150 100

400 2

50

200 65

70

75 80 85 Percentage of TE-LSPs (e)

90

95

100

PD failure PCE failure

300 Number of TE-LSPs

10

0 60

100

350

1400 Bandwidth (Mb/s)

CAC failures

12

95

(d)

1800

14

90

0

0 Simulation runs

Simulation runs (f)

■ Figure 3. Results for MESH-CORE path cost: a) distribution of average path costs across TELSPs; b) distribution of maximum path costs across TE-LSPs; c) distribution of number of crankbacks across TE-LSPs; d) distribution of proportional setup delay due to crankback across TE-LSPs; e) distribution of CAC failures across TE-LSPs; f) TE-LSPs and corresponding bandwidth that failed to find a route.

IEEE Network • July/August 2007

43

DE OLIVEIRA LAYOUT

7/3/07

11:46 AM

Page 44

ures 3c and 4c show the distributions of the number of crankbacks that took place during the setup of the corresponding TE-LSPs for MESH-CORE and SYM-CORE, respectively. It can be seen that all crankbacks occurred when failures were taking place in the networks. Information regarding failures never propagate across domains since the corresponding LSAs are restricted only to the domain in which they originate. As a result, BNs of one domain do not have information on a failure in the next domain, leading to a crankback when a route cannot be found in the next domain. Figures 3d and 4d illustrate the proportional setup delays experienced by the TE-LSPs due to crankbacks for the two topologies. It can be observed that for a large proportion of the TE-LSPs, the setup delays arising out of crankbacks are very large, possibly proving to be very detrimental to QoS requirements. The large delays arise out of the crankback signaling that needs to propagate back and forth from the exit BN of a domain to its entry BN. More crankbacks occur for SYM-CORE than for MESH-CORE as it is a very restricted and constrained network in terms of connectivity. This causes a lack of routes, and often several cycles of crankback signaling are required to find a route. CAC Failures — As discussed in the previous sections, CAC failures occur either due to an outdated TED or when a route cannot be found from the selected entry BN. Figures 3e and 4e show the distribution of the total number of CAC failures experienced by the TE-LSPs during setup. About 38 percent and 55 percent of TE-LSPs for MESH-CORE and SYMCORE, respectively, experience CAC failures with perdomain path computation when link failures take place in the network. In contrast, only about 3 percent of the TE-LSPs experience CAC failures with the PCE method. It should be noted that the CAC failures experienced with the PCE correspond only to the TEDs being out of date. This is because with a PCE deployment, a BN that does not have a route to the destination is never selected by the BRPC procedure. Failed TE-LSPs/Bandwidth on Link Failures — Figures 4f and 3f show the number of TE-LSPs and the associated required bandwidth that fail to find a route when link failures are taking place in the topologies. For MESH-CORE, with the per-domain approach, 395 TE-LSPs failed to find a path corresponding to 1612 Mb/s of bandwidth. For PCE, this number is lower at 374 corresponding to 1546 Mb/s of bandwidth. For SYM-CORE, with the per-domain approach, 434 TE-LSPs fail to find a route corresponding to 1893 Mb/s of bandwidth. With the PCE approach, only 192 TE-LSPs fail to find a route, corresponding to 895 Mb/s of bandwidth. It is clearly visible that the PCE allows more TE-LSPs to find a route, thus leading to better performance during link failures. This improvement in performance arises due to the difference in path computation procedures too. BRPC always includes all links that satisfy the constraint in the VSPT and builds the shortest path from the destination. Since the per-domain approach does not have all information about links in other domains, after several TE-LSPs are set up, available bandwidth is left over in fragments insufficient to route all requests, thereby resulting in several setup failures. TE-LSP/Bandwidth Setup Capacity — Since PCE and perdomain path computation differ in how path computation takes place, more bandwidth can be set up with PCE. This is primarily due to the way in which BRPC functions. To observe the extra bandwidth that can fit into the network, the traffic matrix was scaled. Scaling was stopped when the first TE-LSP failed to set up with PCE. This metric, like all the others discussed above, is topology-dependent (hence the choice of two topologies for this study). This metric highlights the ability of

44

PCE to fit more bandwidth in the network. For MESHCORE, on scaling, 1556 Mb/s more could be set up with PCE. In comparison, for SYM-CORE this value is 986 Mb/s. The amount of extra bandwidth that can be set up on SYM-CORE is less due to its restricted nature and limited capacity.

Conclusion and Future Directions In this article a performance comparison with respect to several critical metrics between a PCE-based and a per-domain path computation deployment was presented. The PCE-based approach showed better results than the per-domain path computation approach with the selected performance metrics. Keeping in mind that all evaluation metrics are topology- and traffic-dependent, this study used two significantly different but representative topologies where the difference in performance improvement was also illustrated. Although many more nuances are left to be uncovered and analyzed in future work, novel preliminary analysis and insight into factors governing interdomain path computation are brought to light. An overview of the current status of the IETF PCE Working Group was also given. The WG is currently refining drafts, as well as awaiting deployment experiences. This should bring even further insights on the benefits of the PCE architecture for current network systems.

References [1] E. Osborne and A. Simha, Traffic Engineering with MPLS, Cisco Press, 2002. [2] A. Farrel, J.-P. Vasseur, and J. Ash, “A Path Computation Element (PCE) Based Architecture,” IETF RFC 4655, Aug. 2006. [3] J. Ash and J. L. Le Roux, “A Path Computation Element (PCE) Communication Protocol Generic Requirements,” IETF RFC 4657, Sept. 2006. [4] J. L. Le Roux, “Requirements for Path Computation Element (PCE) Discovery,” IETF RFC 4674, Oct. 2006. [5] A. Farrel et al., “Crankback Signaling Extensions for MPLS and GMPLS RSVP-TE,” Internet draft, v. 05, Nov. 2005, work in progress. [6] J.-P. Vasseur et al., “A Backward Recursive PCE-Based Computation (BRPC) Procedure to Compute Shortest Interdomain Traffic Engineering Label Switched Paths,” Internet draft, v. 01, Dec. 2006, work in progress. [7] D. Awduche et al., “RSVP-TE: Extensions to RSVP for LSP Tunnels,” IETF RFC 3209, Dec. 2001 [8] D. Medhi, “Quality of Service Routing Computation with Path Caching: A Framework and Network Performance,” IEEE Commun. Mag., vol. 40, no. 12, June 2002. [9] N. Spring, R. Mahajan, and D. Wetherall, “Measuring ISP Topologies with Rocketfuel,” Proc. ACM SIGCOMM, 2002. [10] J. Guichard, F. Le Faucheur, and J.-P. Vasseur, Definitive MPLS Network Designs, Cisco Press, 2005.

Biographies SUKRIT DASGUPTA ([email protected]) is currently a Ph.D. candidate at Drexel University. He received his B.Tech. in computer engineering from Sikkim Manipal Institute of Technology, India, in 2003 and M.S. in computer engineering from Drexel University in 2006. His interests lie in several areas of traffic engineering including resource allocation, path computation, signaling, and protocol analysis. JAUDELICE CAVALCANTE DE OLIVEIRA ([email protected]) received her B.S.E.E. degree from Universidade Federal do Ceara, Ceara, Brazil, in December 1995. She received her M.S.E.E. degree from Universidade Estadual de Campinas, Sao Paulo, Brazil, in February 1998, and her Ph.D. degree in electrical and computer engineering from the Georgia Institute of Technology in May 2003. She joined Drexel University in July of 2003 as an assistant professor. Her research interests include the development of new protocols and policies to support finegrained quality of service provisioning in the future Internet, researching and developing traffic engineering strategies, and the design of solutions for efficient routing in ad hoc and sensor networks. JEAN-PHILIPPE VASSEUR ([email protected]) is a system architect at Cisco Systems where he works on IP/MPLS architecture sepcifications, focusing on IP, TE, and network recovery. He holds an engineering degree from France and an M.S. from Stevens Institute of Technology, New Jersey. Before joining Cisco, he worked for several service providers in large multiprotocol environments. He is an active member of the IETF, co-chair of the IETF PCE Working Group, and has co-authored several IETF specifications. He is a regular speaker at various international conference and is involved in various research projects in the area of IP and MPLS. He has also filed several patents in the areas of IP and MPLS, and is the co-author of Network Recovery.

IEEE Network • July/August 2007

DE OLIVEIRA LAYOUT

7/3/07

11:46 AM

Page 45

50

60 PD setup PCE setup PD failure PCE failure

PD setup PCE setup PD failure PCE failure

55 50

40 Max path cost

Average path cost

45

35 30 25

45 40 35 30 25

20 15

20 0

20

40 60 Percentage of TE-LSPs

80

15

100

0

20

40 60 Percentage of TE-LSPs

(a)

(b)

140

8

Crankbacks

6

PD setup PCE setup PD failure PCE failure

120

Crankback delay

7

5 4 3

PD setup PCE setup PD failure PCE failure

100 80 60 40

2

20

1 0 40

50

60 70 80 Percentage of TE-LSPs

90

0 40

100

50

60 70 80 Percentage of TE-LSPs

(c)

PD setup PCE setup PD failure PCE failure

100

4 3

350

1400

Number of TE-LSPs

5

PD failure PCE failure

400

1600 Bandwidth (Mb/s)

CAC failures

450

PD failure PCE failure

1800

8

6

90

(d)

2000

7

100

80

1200 1000 800

300 250 200

600

150

400

100

200

50

2 1 0 40

50

60 70 80 Percentage of TE-LSPs (e)

90

100

0

0 Simulation runs

Simulation runs (f)

■ Figure 4. Results for SYM-CORE: a) distribution of average path costs across TELSPs; b) distribution of maximum path costs across TE-LSPs; c) distribution of number of crankbacks across TE-LSPs; d) distribution of proportional setup delay due to crankback across TE-LSPs; e) distribution of CAC failures across TE-LSPs; f) TE-LSPs and corresponding bandwidth that failed to find a route.

IEEE Network • July/August 2007

45