Abstract: Multimedia applications present new challenges to the current networking technology. One of them is Quality of Service (QoS) requirement. Due to the increasing dynamics of traffic introduced by multimedia applications, dynamic and flexible QoS (Quality of Service) control is needed to ensure both QoS satisfaction and resource efficiency. Because integrated service networks are designed to support a wide range of traffic classes, which have different service requirements, developing metrics to evaluate them is complex. Optical networks provides Quality of Service (QoS), guarantees are also resilient to failures. Supporting QoS connections requires the existence of routing mechanisms that computes the QoS paths, where these paths satisfy the QoS constraints. Resilience to failures, on the other hand, is achieved by providing, each primary QoS path, a set of alternative QoS paths, upon a failure of either a link or a node. We aim at to minimize the total bandwidth reserved on the backup edges. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process. It turns out that the widely used approach of disjoint primary, restoration paths is not an optimal strategy. Hence, the proposed approximation provisioning algorithms (DCOPA) construct a topology, and this topology protects a portion of the primary QoS path. This approach guarantees to find a topology with optimal cost which satisfies the QoS constraints.
Keywords: optical network, provisioning, Schemes, Restoration Schemes, QoS Models, QoS Constraints, Shortest path, Primary path and Restoration Topology.
I. INTRODUCTION
OPTICAL networks are promising for serving as the backbone networks of the next-generation Internet due to their potential ability to meet the ever-increasing demands of high bandwidth. Internet applications can differ with respect to many characteristics, such as burst, high data transaction Bandwidth, multi-granularity of traffic flows, and high resilience. For example, data-intensive distributed applications may require moving different amounts of data from Kilobytes to Terabytes or even Petabytes among multiple sites. These applications may require different quality of service (QoS). Optical networking technologies offering enormous transmission bandwidth and advanced
capabilities are expected to play an important role in creating an efficient infrastructure for supporting internet applications. In current optical network, the capacity of each light path is usually restricted to the granularities such as STM-N, N=1, 4, 16, 64. For high data transport bandwidth requires, single light path couldn't satisfied the demand. So we need to setup multi-paths and split the traffic to these paths to implement data transport within the limited scope of time. It has been proved that a reasonable and efficient multi-path provisioning could increase the availability and decrease the rejection ratio of the whole network [2]. It is possible that the overall utilization efficiency of the network resource can be further improved through an appropriate traffic-distributing algorithm in multiple paths and an appropriate protected path provisioning [1].
This raises the research questions of how to decide the numbers of working paths and protection paths, how to design an adaptive algorithm to distribute the traffic onto the available multiple paths, and how to allocate the bandwidth resource to protection path to satisfy the QoS under a dynamic traffic requests.
A number of provisioning algorithms have been proposed in traditional networks [3] - [5]. However, all these algorithms addressed the problem of TCP packets for IP networks, they do not consider important issues involved in optical technologies, and therefore do not meet the requirements and exigencies of optical network. Reference [2] investigated the problem of reliable multi-path provisioning for high-capacity backbone optical networks. It proposed and investigated the characteristics of effective multi-path bandwidth as a metric to provision a connection to multiple paths while satisfying its availability requirements. It developed two efficient heuristics for solving the multi-path provisioning problem. The results showed that the heuristics perform significantly better (decreasing blocking probability) than conventional single-path provisioning approaches for high bandwidth connections.
This paper focus on optical network supporting application in which large and long-holding requests count more. And as a practical application, the protection and restoration will be taken into consideration. The objective of this paper is to develop a Dynamic Cost Optimized Provisioning and Restoration Algorithm for Optical Networks for splitting traffic and to configure the protection path to satisfy the users' availability requirements. More precisely, under a dynamic traffic model, we investigate the problem of distributing the traffic among the available k-paths and configuring the bandwidth of protection path in order to maximize the efficiency of network resources consumption or minimize the congestion on the network resources, while the users' availability requirements are satisfied. The remainder of the paper is structured as follows: Section II states the definitions and the objectives. Section III describes our algorithms of provision the bandwidth and configuring protection paths. Section IV proposes the results and comprises the performances between single-path routing and multi-path routing for optical multimedia application. Finally, the conclusion of this paper is given.
II. DEFINITIONS AND THE OBJECTIVES
In this paper, we develop dynamic algorithms for provisioning in optical networks. In order to take advantage of the multiplexing gain, we connect optical endpoints using a tree structure (instead of independent point-to-point paths between optical endpoints). An optical network tree has several benefits, as listed below.
1) Sharing of Bandwidth Reservation. A single bandwidth reservation on a link of the tree can be shared by the entire traffic between the two sets of optical endpoints connected by the link. Thus, the bandwidth reserved on the link only needs to accommodate the aggregate traffic between the two sets of optical endpoints.
2) Scalability. For a large number of optical endpoints, a tree structure scales better than point-to-point paths between all optical endpoint pairs.
3) Simplicity of Routing. The structural simplicity of trees ensures that if MPLS [3] is used for setting up paths between optical endpoints, then fewer labels are required and label stacks on packets are not as deep. With MPLS, between each pair of optical endpoints, label switched paths (LSPs) along links of the tree can be set up using the explicit routing capabilities of either RSVP-TE or CR-LDP[3].
4) Ease of Restoration. Trees also simplify restoration of paths in case of link failures, since all paths traversing a failed link can be restored as a single group, instead of each path being restored separately.
We develop algorithms for computing optimal optical trees, that is, trees for which the amount of total bandwidth reserved on edges of the tree is minimum. Initially, we assume that network links have infinite capacity, and show that even for this simple scenario, the general problem of computing the optimal optical tree is NP-hard. However, for the special case when the incoming and outgoing bandwidths for each optical endpoint are equal, we are able to devise a breadth-first search (BFS) algorithm for computing the optimal tree whose time complexity is, where and are the number of links and nodes in the network, respectively.
We present a dynamic integer programming formulation for the general optical tree computation problem (that is, when incoming and outgoing bandwidths for each optical endpoint are arbitrary)and develop an algorithm , we also extend our proposed algorithms for computing optical trees to the case when network links have capacity constraints. We show that in the presence of link capacity constraints, computing the optimal optical tree is NP-hard even when incoming and outgoing bandwidths of each endpoint are equal. Further, we also show that computing an approximate solution that is within a constant factor of the optimum is as difficult as computing the optimal optical tree itself However, our experimental results with synthetic network graphs indicate that the optical trees constructed by our proposed algorithms require dramatically less bandwidth to be reserved (in many instances, by more than a factor of 2) compared to breadth-first search. Further, among the two algorithms, the dynamic bandwidth reservation algorithm performs the best, reserving less bandwidth than either the BFS algorithms over a wide range of parameter values.
III. A DYNAMIC COST OPTIMIZED PROVISIONING ALGORITHM (DCOPA)
INPUT:A optical Network G=(N,L),optical network units OXC=(OXC1, OXC2,…., OXCp)Σ N, Residual Bandwidth constraints B on L and a VPN setup request Vr= (r1, r2,…, rp)
OUTPUT: A minimum cost optical tree OTMC for Vri on which all leaf nodes are optical network units OXCp with ri >0.
The optical network backbone is modeled by a graph G= (N, L), where N and L are the set of optical endpoints and the set of links, respectively. Let n and m denote the cardinality of N and L, respectively. Let B be the residual bandwidth of links on L and the amount of residual bandwidth on link l (lЄL) is denoted by B(l). A subset OXC=(OXC1, OXC2,…., OXCp)of N (Apï¡N) is the set of optical network units. Each endpoint ei of a optical gains access to optical service by connecting to a specific optical network unit OXCp in OXC. In other words, for each endpoint of a optical network, there is a corresponding optical network unit in OXC. The elliptic region in figure 1 is an example of optical network backbone G. The round regions (A to G) inside G are optical network units in N. The solid lines between two optical network units are links in L. The number beside each link is the amount of residual bandwidth on it (B (l) =5 for all lЄL in this figure). The round regions (1, 2 and 3) outside G are optical network units (e1, e2 and e3, respectively, in our notation) of an optical networks, which gain access to optical network service via optical network units in OXCp. The dotted lines labeled as path i, j is the transmission path for optical network traffic between ei and ej.
Fig.1. Optical Backbone Network
Optical Setup Request Modeling:
The demands for optical network service of customers are described by optical network setup requests. In this paper consider that the bandwidth requirement of each endpoint ej is symmetric. Let b(ej) denotes the bandwidth requirement of endpoint ej, and Maxr denote the maximum bandwidth guarantee provided by optical network unit. The ith setup request, denoted by vri .Each vri is represented by a p-tuple vector (r1, r2,…, rp), where p is the cardinality of optical network units(OXCs). The number of nonzero elements in vri represents the number of network unit contained in the corresponding optical networks. The value of jth element r1of vri represents the bandwidth requirement of endpoint ej.
Establishment Problem
The algorithm defined in this paper which mainly considers on-line establishment of bandwidth guaranteed point-to-point OXCs. The optical network setup requests of customers are sent to ORS (Optical Request Server).
In this paper consider the situation where (a) optical setup requests arrive one by one independently and (b) information about future optical setup requests is unknown. This information includes the number of future optical setup requests, the number of OXCs contained in each optical setup request, and the bandwidth requirement of each endpoint. The service provider must process each setup request in an on-line manner, the off-line model in not suitable. Upon receiving a setup request vri, the service provider triggers the provisioning algorithm to establish a corresponding connection. The provisioning algorithm performs this task by first choosing a path between each endpoint pair and then allocating bandwidth on each link on the paths. If there is not enough residual bandwidth on the link when the bandwidth is being allocated, vri will be rejected. In this paper the rejection ratio is taken as the performance metric to compare different optical network provisioning algorithms. The rejection ratio is defined as:
Number of requests rejected
Rejection ratio=
Total number of request received
The optimization goal of provisioning algorithms is to minimize the rejection ratio, which in turn will maximize the number of requests successfully established on the network backbone. Although the main performance metric here focus on rejection ratio.
Other important performance metrics (eg: link utilization and bandwidth allocation efficiency) are also investigated in the experimental simulations. The ORS also keeps the complete link state topology database and is responsible for finding an explicit path for each endpoint pair of a OXCs. Then the explicit paths can be setup using a signaling protocol such as RSVP. For computing the explicit paths, the ORS needs to know the current network topology and link residual bandwidth. We assume that there exists a link state routing protocol for information acquisition.
The Factors Influencing Rejection Ratio:
In this case, the links of the network backbone have a finite amount of bandwidth and the service provider needs to establish multiple connections on the network backbone on-line. The two most important factors influencing the rejection ratio achieved by provisioning algorithms are: (1) Bandwidth allocation efficiency (2) Load balance mechanism that considers the amount of residual bandwidth on links. Provisioning algorithms must take the residual bandwidth of links into account, and avoid using links that are thinly spread. This will balance the load on links of G and reduce rejection ratio.
A Dynamic Cost Optimized Provisioning Algorithm (DCOPA)
To address the problems described above we propose a new provisioning algorithm called the A Dynamic cost Optimized provisioning Algorithm. The cost function of the proposed algorithm optical tree selection is defined as following:
Rs (lx)
Cost (T) =
B (lx)
Where Rs(lx) and B(lx) represent the amount of bandwidth needed and the amount of residual bandwidth on link lx, respectively. The cost function is inspired by the cost function defined in the routing algorithms for route selection.
When processing a request, the proposed algorithm tries to find a optical tree that minimizes the cost function defined above.
It is clear that the additional cost for using a link lx in building a optical tree is proportional to the value of RS(lx) and is reciprocal to the value of B(lx). Therefore, the algorithm tries to finds a optical tree that has abundant residual bandwidth and only requires a small amount of bandwidth to be allocated to the tree links. As a result, algorithm can look after both bandwidth allocation efficiency and load balancing. The pseudo code of DCOPA is described below
Function Compute Rs(T, Vri)
Let lx be the xth link on T
Let Rs (lx) be the amount of bandwidth needed on lx with respect to the bandwidth requirement specified in Vri
Let Tax and Tbx be the two sub trees obtained by remove lx from T
For (each lx in T)
{
Initialize two variable BR_ Tax and BR_ Tbx to value 0;
For (each element rj ≠0 (1 ≤ j ≤ p) )
{
If(arj Є Tax ) then add rj to BR_ Tax
Else add rj to BR_ Tbx
}
Rs(lx) = min(BR_ Tax, BR_ Tbx )
}
Fig.2. Pseudo code to compute _Rs
Assume a network graph G consisting of n nodes. To process a setup request vri, the DCOPA iterates totally n times, once for each vЄN. In each iteration, DCOPA first finds a candidate optical tree PTv rooted at v for vri, and then computes the amount of bandwidth needed to be allocated to each link lx of PTv. Finally the cost value associated with PTv can be computed. After finding all PTv (vЄN), if there do not exist any PTv (vЄN) on which all links have enough residual bandwidth for allocation, DCOPA will reject vri. In the case of accepting vri, DCOPA will return the optical tree with the minimum cost value among all PTv (vЄN) for vri which is denoted by OTMC. In addition, DCOPA then allocates bandwidth to each link lx of OTMC by performing B(lx) = B(lx)-RS(lx). To find a candidate optical tree PTv rooted at v, DCOPA first find a BFS tree (breadth first search tree ) Tv rooted at v (by calling Function BFS_Tree). Tv contains all nodes in G and in addition, Tv may contain nodes which are not OXCs used in vri as leaf nodes. Therefore, DCOPA prunes Tv and obtained a candidate optical tree PTv, on which all leave nodes are OXCs used in vri (by calling Function Prune_Tree). DCOPA computes the amount of bandwidth needed for each link lx of a optical tree T according to the bandwidth requirement information in vri (by calling Function Compute_RS in figure 2). To compute the value of RS(lx) (lxЄT), we first remove lx from T and this will partition the optical tree into two sub trees BR_ Tax and BR_ Tbx. Let BR_ Txa and BR_Txb denote the accumulated bandwidth requirement of the OXCs (endpoints) on Tax and Tbx, respectively. Then RS(lx) is determined by the minimum value of BR_ Tax and BR_ Tbx. Given an optical tree T, in a normal case, the function Cost of DCOPA returns the cost value computed by the cost function defined previously. However, where T is null (Ø), or there are links on T which do not have enough bandwidth for allocation, the function cost will return α.
IV. COMPARIION AND ANALYSIS
We conducted an study to measure the performance of our DCOPA and BFS algorithms, and compared them with the approach to connect OXCs. The major findings of our study can be summarized as follows.
• The BFS generates optical trees with the smallest cost for a wide range of incoming and outgoing bandwidth ratios. It outperforms the DCOPA algorithms for medium-to-large bandwidth ratios.
• For low incoming and outgoing ratios, the BFS algorithms slightly outperform the DCOPA algorithm. In many cases, they construct optical trees that reserve half the bandwidth reserved by BFS.
Experimental Results
(Designed and developed DCOPA Vs BFS Tree Routing)
We compared the provisioning cost (that is, the total bandwidth reserved on links of the optical tree) and the running times of the algorithms for the symmetric as well as the asymmetric bandwidth models. In the study, we examined the effect of varying the following two parameters on provisioning cost: 1) network size 2) number of OXCs. Most of the plots in the following subsections were generated by running each experiment five times (with different random networks) and using the average of the cost/execution times for the five repetitions as the final result.
Cost
Fig. 3. Effect of Number of ONUs in performance of
Algorithm (Symmetric)
Number of ONUs
Simulation 1: (Network Size)
Figure.3 depicts the provisioning cost of the BFS and DCOPA algorithms as the number of network nodes is increased from 10 to 100. OXCs is assigned equal incoming and outgoing bandwidths and the number of OXCs set to 10% of the network size. The DCOPA algorithm is provably optimal for the symmetric case. Further, unlike the BFS algorithm which is oblivious to the bandwidths of endpoints, the BFS algorithm does take into account the bandwidth requirements for OXCs. As a result, it outperforms by almost a factor of 2 for a wide range of node values.
Number of OXCs
DCOPA-cost
BFS-cost
10
2050
3000
30
2500
4400
50
4500
7000
75
5500
9000
100
6500
10000
Table1 Parameter configuration of Simulation 1
Simulation 2: (Rejection Ratio)
We conduct 15 runs with various number of topology, in each of which, 100 requests are randomly generated. The rejection ratios achieved by the two provisioning algorithms are (see Figure 4). The x-axis represents the number of OXCs. and the y-axis represents the rejection ratio and average link utilization achieved by each provisioning algorithm in each run.
Number of ONUs
Rejection Value
Fig. 4. Effect of Rejection Ratio (symmetric)
Number of OXCs
DCOPA-Rejection Ratio
BFS-Rejection Ratio
10
2
6
30
1
5
50
1
5
75
1
4
100
0
4
Table1 Parameter configuration of Simulation 1
We can see that the rejection ratio achieved by DCOPA is much less than that achieved by BFS routing.
V. CONCLUSIONS
In this research work, the designed novel algorithms for provisioning optical network DCOPA connected OXC using a tree structure and attempted to optimize the total bandwidth reserved on edges of the optical tree. The algorithm showed that even for the simple scenario in which network links are assumed to have infinite capacity, the general problem of computing the optimal tree is NP-hard. However, for the special case when the incoming and outgoing bandwidths for each OXC are equal, DCOPA proposed a breadth-first search algorithm for computing the optimal tree. According the simulation results DCOPA can indeed reduce the rejection ratio effectively.
We can think of extending the project for using Alternative Cost Functions as the Performance Metric for Asymmetric case of bandwidth allocation in optical networks.
VI. REFERENCES
[1] Sudipta Sengupta and Ramu Ramamurthy, "From Network Design to Dynamic Provisioning and Restoration in
Optical Cross-Connect Mesh Networks: An Architectural and Algorithmic Overview", IEEE Network, July/August 2001.
[2] L. A. Cox, Jr., J. R. Sanchez, and L. Lu, "Cost Savings from Optimized Packing and Grooming of Optical Circuits: Mesh vs. Ring Comparisons," Opt.Networks, May-June 2001, pp. 72-90.
[3] R. Ramamurthy et al., "Capacity Performance of Dynamic Provisioning in Optical Networks," J. Lightwave Tech., vol. 19, no. 1, Jan. 2004, pp. 40-48.
[4] D. Awduche and Y. Rekhter, "Multiprotocol Lambda Switching: Combining MPLS Traffic Engineering Control with Optical Crossconnects," IEEE Commun.Mag., vol. 39, no. 3, Mar. 2003.
[5] Kefei Wang et at., "Multicast Routing in 40Gb/s Heterogeneous Optical Networks", 0-7803-8938-7/05/ IEEE, 2005.
[6] Jun Gu et at., "Routing algorithm for multicast under multi-tree model in optical networks", Elsevier Science Publishers Ltd, Volume 314, Issue 1 ,February 2004.
[7] Vladica Tintor and Jovan Radunović , "Distributed Dijkstra sparse placement routing algorithm for translucent optical networks", Photonic Network Communications Volume 18, Number 1, 55-64, 2008.
[8] Meeyoung Cha et al., "Integer Linear Programs for Routing and Protection Problems in Optical Networks", Photonic Network Communications , 2009.
[9] S. Ganguly., "Waveband Routing and Merging in Hybrid Optical Networks", IEEE Communications Society,2006.
[10] Ralf H¨ulsermann et al., "Dynamic Routing Algorithms in Transparent optical networks", IEEE Commun. Mag., 37:67-73, 2009.
