Description

A Hierarchical Path Computation Element (PCE)-Based
Routing Algorithm in Multi-Domain WDM Networks
Shengfeng Shang, Xiaoping Zheng, Heng Zhang, Nan Hua, Hanyi Zhang
State Key Laboratory on Integrated Optoelectronics
Tsinghua National Laboratory for Information Science and Technology,
Department of Electronic Engineering, Tsinghua University, Beijing, 100084, P. R. China
{shangsf04,zhangheng, huan03}@mails.tsinghua.edu.cn, {xpzheng, zhy-dee}@mail.tsinghua.edu.cn
Abstract: This paper proposes an

Categories

Published

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Similar Documents

Share

Transcript

A Hierarchical Path Computation Element (PCE)-Based Routing Algorithm in Multi-Domain WDM Networks
Shengfeng Shang, Xiaoping Zheng, Heng Zhang, Nan Hua, Hanyi Zhang
State Key Laboratory on Integrated Optoelectronics Tsinghua National Laboratory for Information Science and Technology, Department of Electronic Engineering, Tsinghua University, Beijing, 100084, P. R. China
{shangsf04,zhangheng, huan03}@mails.tsinghua.edu.cn, {xpzheng, zhy-dee}@mail.tsinghua.edu.cn
Abstract:
This paper proposes an inter-domain routing algorithm for multi-domain WDM networks based on hierarchical PCE architecture. The proposed algorithm presents a strategy of selecting k random paths in parent PCE. The simulation indicates that the proposed algorithm outperforms previous methods in term of blocking probability and resource utilization.
2010 Optical Society of America
OCIS codes:
(060.4250) Networks; (060.4256) Networks, network optimization
1. Introduction
Computing optimum routes for Label Switches Paths (LSPs) across domains in multi-domain networks presents a problem because of the constraints of confidentiality between domains. A solution can be achieved using the Path Computation Element (PCE) [1] architecture. If the domains are simply connected, the Per Domain Path Computation Technology is used. To overcome the limited visibility of traffic engineering (TE) information, Backward Recursive PCE-based computation (BRPC) [2] has been proposed for inter-domain path; however, the method can achieve the optimum path only when the sequence of traversing domain has been predetermined. The problem of how to determine the optimum sequence of domains has been studied in BGP-based networks [3]. In this scheme, the inter-domain information has been carried by PCEP messages to select the sequence of domain; however, the ignorance of intra domain resource information leads to high blocking probability, especially when the topology of intra domains is complex. In this study, we propose a novel path computation algorithm based on hierarchical PCE architecture [4]. In this algorithm, the parent PCE is responsible for computing the inter-domain path based on the global abstract topology, while the child PCEs are in charge of determined the intra-domain paths.
2. Proposed algorithm
In hierarchical PCE architecture, the database of the parent PCE (TED) includes both inter-domain and intra- domain information. In other words, the parent PCE is not only aware of the interconnection between
border nodes
(BN) from different domains, but also aware of the cost of virtual links between BNs from the same domain; the cost is advertised by each child PCE periodically. As the parent PCE has no visibility of
interior nodes
(IN), it cannot achieve the optimum path when the source node or destination node is IN. Especially when the topology of ingress or egress domain is complex, the result makes a large difference from the optimum result. The optimum path will undoubtedly pass by two BNs: one belongs to the ingress domain, and the other belongs to the egress domain. If we find the correct
Peer Node
(PN) from the ingress to the egress domain, we can achieve the global optimization result. Therefore, these PNs are important resources for computing the optimum path when the source and destination nodes are determined. Assumed that PN is predetermined, the optimum path can be computed using the PN information as follows:
( , ) ( , ) ( , ) ( , )
op n n op n n op n n op n n s d s bs bs bd bd d
Where
( , )
op n na b
represents the optimum path between
na
and
nb
,
,
n n s d
represent the source and destination node respectively, while
,
n nbs bd
represent the predetermined border nodes of the ingress and egress domains. If the ingress domain consists of
m
BNs and the egress domain
n
BNs, there exist
m n
PNs; each PN has the probability of
1/
m n
to achieve the global optimization path. When we compute optimum paths by selecting
k
random PNs and then choose the best result, the probability of global optimization can rise to
1 (1 1/ )
k
mn
. As
k
increases, the result approximates to the global optimization path. The paths selected by the parent PCE are named
k
random paths. Once a traffic connection request arrives at a node, this node requests the ingress PCE for a path. When the path is needed outside of the ingress domain, the ingress PCE sends a PCEP request to the parent PCE. With the knowledge of the egress domains location, the parent PCE computes
k
random candidate paths based on the
35
978-1-4244-7113-3/10/$26.00 ©2010 IEEE
selected PNs and the abstract topology of current domains. Each candidate inter-domain path includes the ingress and egress nodes of the traversing domains. Then the parent PCE sends computation requests to the child PCEs responsible for the domains which are traversed by any candidate domain path. The child PCEs reply the cost of each path which is carried in PCRep messages after computing the paths. The parent PCE computes the cost of each candidate path with the PCRep messages received from child PCEs and then selects the optimum one. At last, the parent PCE replies the optimum path to the ingress PCE, and then the process of path computation is accomplished.
3. Simulation results
A 9-domain, 61-node topology (Figure 1) is used for simulation. There are 36 border nodes, 19 inter-domain links in this topology; each intra-domain link accommodates 32 wavelengths while 64 wavelengths for inter-domain links. In our simulation experiment, the connection requests are considered to arrive at the network according to Poisson distribution, the s-d node pairs are chosen from different domains based on a uniform distribution, the traffic connection duration is negative exponentially distributed. Figure 1 shows the blocking probability (BP) under the influence of factor
k
. As
k
increases, the blocking probability decreases and converges to a specific curve. As shown in Figure 2, three different methods are implemented including the BGP-based PCEP resources advertisement (PCRA) scheme, the hierarchical PCE based algorithm (
k
=4) and the global optimization scheme. In addition, the results considering load balance are also performed in Figure 2. The results indicate that the proposed algorithm can significantly reduce blocking probability in multi-domain WDM networks. Considering load balance, it approximates to global optimization on blocking probability performance. In addition, the proposed algorithm achieved more efficient resource utilization than the conventional method (Figure 3).
Figure 1 topology and BP varies k Figure 2 BP achieved by three schemes Figure 3 Resource Utilization
4. Conclusions
This paper proposed a novel path computation algorithm based on hierarchical PCE architecture for multi-domain routing in WDM mesh networks. By utilizing
k
random paths in parent PCE the algorithm achieves an optimized result in great probability. The simulation results indicate that the blocking performance improves by introducing the factor
k
. As
k
increases, the proposed algorithm achieves lower blocking probability and more efficient resource utilization. When considering load balance, the result of the proposed algorithm approximates to global optimization.
4. Acknowledgement
This work is partly supported by projects under grant No. 2008AA01A327, 2008AA01A329, 2009AA01Z254, NSFC under grant No.60972020 and projects under grant No.2010CB328203, 2010CB328205.
References
[1] A. Farrel, J. P. Vasseur, 1. Ash, A Path Computation Element(PCE)Based Architecture, IETFRFC4655, Aug. 2006. [2] S. Dasgupta, 1. C. de Oliveira, 1. P. Vasseur, Path-Computation-Element-Based Architecture for Inter-domain MPLS/OMPLS Traffic Engineering: Overview and Performance, IEEE Network, Vol. 21, no.4, pp. 38-45(Jul-Aug. 2007). [3] F. Cugini, F. Paolucci, L. Valcarenghi, P. Castoldi, A. Weiin, PCE Communication Protocol for Resource Advertisement in Multi-domain BOP-based Networks, IEEE /OSA OFC, OWL3, Mar. 2009. [4] M. Chamania, A. Jukan, A Survey of Inter-domain Peering and Provisioning Solutions for the Next Generation Optical N Commun. Surveys & Tutorials, First Quarter 2009, vol. 11, Feb. 2009.
36

Search

Similar documents

Tags

Related Search

Shortest path with Ant Routing Algorithm in wContext-Based RoutingTrust Based Routing Protocol For ManetA map matching method for GPS based real timeScience/Research as a Spiritual PathTowards Online Shortest Path Computation PPTDepth-based routingRouting Protocols in WSNRouting algorithmRouting Protocol in VANET

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x