computer
communications
www.elsevier.com/locate/comcom
Lambda GLSP setup with QoS requirements in optical Internet
SuKyoung Leea*, David Griffith*1, Joo-Seok Songb
^National Institute of Standards and Technology, 100 Bureau Drive, Stop 8920, Gaithersburg, MD 20899, USA hDepartment of Computer Science, Yonsei University, Seoul, South Korea
Received 17 July 2001; revised 27 May 2002; accepted 18 June 2002
Abstract
GMPLS is currently being specified as the control plane for next generation optical networks. While one merit of GMPLS is that network operators are able to control the traffic of Internet Protocol (IP) and thus offer performance superior to that of traditional Internet Gateway Protocols (IGP), it has been a challenge to develop an efficient Traffic Engineering (TE) technique to satisfy the different traffic requirements of end-users in GMPLS domain. Several TE techniques have been thought of by creating a set of Generalized Label Switched Paths (GLSPs) in the optical network.
In this paper we present a technique for establishing GLSP in optical Internet, that supports Quality of Service (QoS) considering the traffic flows with delay QoS requirements. This approach accounts for the processing delay at the network layer that may be encountered in optical nodes that terminate lightpaths and perform some types of traffic grooming. Additionally, we extend the QoS routing framework by defining additional extensions that can be used in conjunction with Shared Risk Group (SRG) identifiers to reserve backup paths that do not share network resources with the working paths that they are protecting. We provide some simulation results to demonstrate the effectiveness of our routing algorithms.
© 2002 Elsevier Science B.V. All rights reserved. Keywords: GLSP; Optical Internet; TE; Backup path
1. Introduction
Recent years have seen a growing need to support applications that require a high Quality of Service (QoS) on networks that use the Internet Protocol (IP), voice traffic being a classic example. The response to this need has been the development of a range of tools, such as Integrated Services (IntServ) and Differentiated Services (DiffServ), to support various levels of QoS. In addition, it is now possible to implement Traffic Engineering (TE) in IP networks using tools such as Multi-Protocol Label Switching (MPLS) [1]. Using TE extensions to OSPF in combination with MPLS, it is possible to route connections across the network in order to optimize network utilization, avoid islands of stranded bandwidth, and balance load. The rapid growth in data traffic currently being experienced is fueled by the Internet, posing new challenges for transport network providers. To meet the bandwidth demand of the Internet, it is natural to use optical technologies with Wavelength Division Multiplexing (WDM) to offer the capability of building very large
* Corresponding author. E-mail address: sukyoung@antd.nist.gov (S.K. Lee).

ELSEVIER Computer Communications 26 (2003) 603-610
wide area networks with throughput of the order of terabits per second.
Recently, with the advent of new traffic engineering protocols like MPLS, there has been considerable activity in several standards groups to integrate MPLS and WDM networking technologies into a unified structure for optical Internet [2]. This extended version of MPLS that is so-called GMPLS will allow many carriers to deploy optical Internets where lambdas (wavelengths) are treated as very low-level point-to-point links for the transmission of packets between high performance routers. In this optical Internet, optical switches translate label assignments into corresponding wavelength assignments and setup GLSP using local control interfaces to switch devices. Subsequent to GLSP setup, no explicit label lookup/processing operations are performed by Optical Labeling Switched Routers (O-LSRs).
One of the benefits of GMPLS is that it supports TE by allowing the node at the network ingress to specify the route that a GLSP will take by using Explicit Routing (ER). An explicit route is specified by the ingress as a sequence of hops that must be used to reach the egress, which is different from the hop-by-hop routing, that is usually associated with packet-switch capable networks. ER features can also be used to facilitate QoS support for multiple class of services in GMPLS networks (e.g. DiffServ). There have been several efforts directed towards using QoS information to make routing decisions, but their focus is different from ours. A method for supporting QoS using the IETF's Open Shortest Path First (OSPF) routing protocol can be found in Ref. [4]. This approach advertises available bandwidth and delay metrics in OSPF Link State Advertisements (LSAs), but does not use the delay metric in computing paths. Some centralized routing schemes have been proposed, notably that in Ref. [4], which seek to find the transiting path whose delay is less than a prescribed limit and whose bandwidth is greater than a specified lower bound. That approach uses Dijkstra's algorithm to find a suitable path but does not specifically account for delays at layer 3 or for relative throughput, as our algorithm does.
Routing to support QoS requirements could be also applied to optical networks [5]. QoS routing selects a path offline for each flow or connection to satisfy diverse performance requirements and optimize resource usage. Even though network resource is still available, uneven distribution of traffic prevents from meeting QoS constraints, that is, leads to worse delay performance in terms of delay QoS. In this case, TE arranges traffic flows so that congestion caused by uneven network utilization can be avoided.
In this paper, we propose a mechanism to provide better delay performance and improve network utilization in the optical network. We do this by using a linear programming approach that seeks to minimize the total path delay, including delay introduced by packet processing at layers above optical. While other researchers, specifically [6], have introduced linear programs that account for the bottleneck effect at layer 3, their approach seeks to maximize total network throughput, while ours is focused on meeting QoS requirements.
The optimization routine that we are proposing will take path delay, including queueing delay at layer 3, into account. In optical Internet using lambda labeling, processing at layer 3 would constitute a significant bottleneck whose impact we wish to minimize. In transparent optical networks where it is possible to create lightpath connections between every pair of edge routers, this is not an issue. But in large networks with thousands of devices at the edge, creating a virtual topology that is a full mesh is impractical. Thus, we can expect that intermediate nodes with layer 3 functionality will exist in a lambda labeling network (most likely at the edges of optical subnetworks in the core). Thus it would be useful to account for the impact of layer 3 processing when the ingress computes the explicit route. The layer 3 processing overhead at intermediate nodes is accounted for in the proposed path set-up algorithm.
The rest of paper is structured as follows. In Section 2 we introduce the background. We describe our algorithm in Section 3 where an integer linear program (ILP) based solution is used. In Section 4 we present simulation results, and finally in Section 5 conclusion is drawn.
2. Background
Core optical network consists of the Optical Cross-Connects (OXCs) and fiber links interconnecting OXCs. Each OXC can route an input wavelength to an output wavelength. These OXCs, in most of the cases, can preclude the electronic processing, and thus a optical connection can be established between edge nodes. In lambda labeling network, GMPLS control plane is attached onto OXC devices and treats them as GMPLS nodes, hereafter called as O-LSR nodes, allowing GMPLS signaling to compute and set up Generalized Label Switched Paths (GLSPs) between O-LSR nodes in a similar way as MPLS LSPs.
O-LSRs can be viewed as a combination of a router and an OXC. The router component is responsible for all the layer 3 functions such as addressing, routing, and global topology discovery. It is also responsible for optimizing network performance, which can be carried out via TE with QoS support, management of optical resources (i.e. wavelength assignment in coordination with the optical channel sublayer), and restoration. That is, the most important advantage of GMPLS turns out to be its ability to do TE of IP networks although it was originally devised with other goals such as faster forwarding of IP datagrams. Even if GMPLS is very useful as protocols for establishing traffic engineered paths through optical Internet, many researchers have recently begun working on the mechanisms of computing these paths [7]. Therefore, the objective of this paper is to formulate the TE problems in mathematical form to motivate more work towards the consideration of multiple QoS classes. As can be seen in

Fig. 1. Traffic engineering with QoS requirements.
Fig. 1, the wavelengths can be assigned to the GLSPs in accordance with QoS class [5]. GMPLS would be applicable to DiffServ based networks as the growing trend is to use DiffServ in the edge O-LSRs and lightpaths in the core. In this paper, ingress O-LSRs determine the GLSPs that IP traffic flows will be routed through, in terms of the QoS requirements such as the maximum acceptable delay. Additionally, this path computation based on delay requirement can be also applied to establishing a backup path with reservations every time a primary path is established across the network. Seeing the objective of TE in terms of priorities, although we consider only a single level of priority for delay QoS in this paper, the proposed approach naturally can extend to multiple priority levels. As a consequence, the performance of the QoS service classes is oblivious to the presence of the delay-sensitive traffic.
Reliable network operation is another important aspect of TE. Failure recovery scenarios must be designed to ensure continuity of service following network impairments. Therefore, the operational capability must exist to reroute traffic through the remnant capacity when failures occur. While this rerouting procedure should make more effective use of the residual post-failure capacity, it should establish a backup GLSP to still satisfy the QoS requirement even after the traffic is recovered onto the backup path.
As a signaling protocol to support the QoS, there are two methods in GMPLS. One uses TE extensions to the Resource Reservation Protocol (RSVP-TE) [8,9] and the other one utilizes extensions to the Label Distribution
Protocol (LDP) called Constraint-based Routing LDP (CR-
LDP) [8,10]. IETF have been developing both signaling protocols. Either RSVP-TE or CR-LDP can be used allowing a GLSP to be explicitly specified across the optical core (Fig. 1) since both signaling protocols were also recently extended to support GMPLS.
3. GLSP set-up algorithm
The main problem of the proposed algorithm is to establish a GLSP that meets the delay requirement (We call
this GLSP as CR-GLSP: Constraint-based Routed GLSP).
The algorithm routes the GLSPs over the topology, and assigns wavelengths optimally to the various lightpaths. This assignment problem very likely belongs to the class of NP-hard problems [11], since its sub-problem, the static lightpath establishment has been shown to be NP-hard in Ref. [12]. Therefore, it is righteous to formulate the problem as an ILP.
We consider a connected network with N OXCs and L directed links such as fibers. Each fiber carries a certain number of wavelengths. A subset of these nodes is assumed to be edge O-LSRs between which lightpaths can be set up. We are given all the information on the virtual topology and status through a link state protocol.
That is, Interior Gateway Protocol (IGP), such as OSPF with extensions for optical and TE attributes will allow nodes to exchange information about optical network topology, resource availability, and even policy information.
Let G = (N,L) describe the given network with node set N = n1,n2,n\Ni and link set L = l1,12, where iNl and iLl denote the cardinalities of the node set and the link set, respectively. A link will be referred to by the ordered node pair it connects, (n1, n2). Let D = {Dj} be the distance matrix from node i to node j that means a propagation delay from node i to node j(i — j). Let K = k1,k2,k\K\ be the set of traffic demands belonging to a specific service class between a pair of edge O-LSRs. Typically there are several QoS service classes, each having characteristic specifications, such as delay. Here, we assume that the service class belongs to delay-sensitive class, since the algorithm focuses on delay QoS. Each traffic demand k [ K is defined by the ordered triple (Ik, Ek, ek), where Ik is the ingress OXC, Ek is the egress OXC, and sk is the maximum edge-to-edge delay that is allowed for request k. For traffic flow, We define \'kEk to be the average flow associated with the kth traffic demand belonging to the delay-sensitive class requesting CR-GLSP set-up. These demands are assumed to arrive one at a time. Like \'kEk, denotes the traffic from ingress I to egress E that flows over an intermediate virtual link (i,j).
The unknown variables that need to be determined based on optimizing a certain objective function and satisfying a set of constraints are the following. These binary valued variables indicate a set of virtual connectivities:
f 1 if the virtual topology has a direct fiber link (i, j),
Vij = j (1)
0 otherwise
where i,j = 1,2,iNl, i — j. If the TE function performs CR-GLSP setup online when a new CR-GLSP request arrives after a virtual topology is determined initially, these variables would assume the role of constants via virtual topology matrix. On the other hand, in case that the virtual topology is being formally modeled over the physical topology offline, the TE tool should compute the variables to overlay the virtual GLSPs. Thus, the online TE tool could be used to solve, in real time, problems such as the QoS based routing and rerouting of GLSPs.
When the network manager gets a request for a new CR-GLSP with a certain QoS requirement, it should determine whether this CR-GLSP can be routed to meet the QoS. The decision variables assume a binary value and denote which virtual link the GLSP select in the network. In mathematical form,
( 1   if the CR-GLSP has a lightpath on link (i, j)
eij = 1 (2)
0   otherwise
where i, j = 1,2,iNl and i — j. That is, ej indicates whether the CR-GLSP is routed over the virtual link from node i to node j as in Ref. [13].
xi indicates the layer 3 routing capability of the node as follows:
f 0   if node i has no layer 3 processing xi = J (3)
1   otherwise
The set of variables has to satisfy the following constraints.
Xvj# Ti,  £ vj# Rj      for all i,j. (4)
j i
where Ti and R, are the number of transmitters and receivers, respectively, at node i and j (i, j G N).
Xij = (vjX Af) + ej'A/lEl      for all i, j. (5)
' \'lEl,       i = Ik
I Afk - I AFk = " ~l'kEk, i = Ek (6)
jj
0, otherwise.
lij # WyC, (7)
where C is the capacity of each wavelength on a fiber and Wij denotes the number of wavelengths per link in the virtual topology between the nodes i and j for all i and j.
Xf1 = eijXhEk. (8)
Constraint (4) ensures that we can set up only single lightpath per port at each node. Constraints (5) and (6) are related to the traffic flow on virtual link for all i and j. When the new traffic demand is routed, the definition of the total traffic over link (i, j), Xj is expressed in constraint (5). Constraint (6) assures that the flow of traffic is conserved at each node. Although splitting is used for load balancing purposes by routing demands over multiple GLSPs at the ingress point, it is not permissible for the routing algorithm to always split traffic in an arbitrary manner since the traffic being routed may be inherently unsplittable. In this paper, the traffic flow XIkEk will not bifurcate either at any point in the network from the fact that the proposed TE algorithm is trying to route a CR-GLSP request explicitly to meet the QoS. Thus, constraint (6) is brought in so the traffic flowing into an OXC to be tantamount to that flowing out of the OXC for any OXC other than the ingress and egress O-LSRs. In terms of the constraints, the link capacity should not be exceeded with the addition of the new CR-GLSP along its path through the network that is presented in constraint (7). Constraint (8) specifies that if the link (i, j) does not exist on the CR-GLSP, no traffic can be routed on that link. Finally, constraint (9) keeps the new CR-GLSP from being set up between two nodes if there is no virtual link connecting them. Additionally, we can incorporate the layer 3 port throughput into constraint (7). When the traffic flowing through a link is going forward an intermediate O-LSR, the traffic demand should not be larger than the sum of the maximum throughput supported by IP router port:
Xj# WjC{1 + (a - 1)Qj},
(10)
where a # 1 denotes the maximum layer 3 port throughput, expressed as a fraction of the optical layer throughput.
A packet traversing the CR-GLSP experiences an end-to-end delay of £ijeijXIjEkDij + dnode, where dnode denotes the total waiting time at all nodes over the CR-GLSP. The dominant delay in light to moderately loaded high bandwidth optical networks is known as the propagation delay, which is uniquely determined by the length of the optical path over the physical WDM network. However, since wavelengths and fibers are finite, a lightpath is not always established between each source and destination IP routers. Moreover, if traffic grooming is available in some nodes, it is not always necessary to deploy a direct lightpath between two nodes to carry traffic between them. Instead, the traffic demand between two nodes may be carried by multiple lightpaths among some intermediate nodes without direct lightpath deployment between the two (end) nodes. Consequently, IP packets are forwarded to the destination by multi-hop IP routing. By this routing, layer 3 processing may still be a bottleneck of a network. Thus, dnode is defined to be the waiting and processing time at O-LSRs, since these nodes are the likely bottleneck points on any CR-GLSP. The delay increases with the number of hops and the expected processing delay at the intermediate nodes, since there can be an arbitrary number of intermediate O-LSRs on the GLSP.
we define to be the aggregate input rate to the mth (m = 1,2,M) O-LSR. Under the independence assumption on interarrivals we can model the delay experienced at layer 3 using an M/M/1 queueing model. Fig. 2 depicts the operation of such an optical Internet. Given that mm be the service rate in each intermediate node, we can get the average layer 3 processing delay

Fig. 2. Delay with layer 3 processing.
seen by the traffic flow as
t =y -Pm^^E, (11)
where = X^=mm is the utilization. Using the local connectivity and processing rate variables, the above Eq. (11) becomes
T= sr_eijQj_ Q2)
£ m _ (X^j + X'kEkY "  '
Thus, for the kth traffic flow belonging to DS class, the objective function for delay can be written as
f(eij) = (X eijX'kEkDj) + T, (13)
In Eq. (13), the second term t will be zero if there is no layer 3 processing at any point on the GLSP. The objective function, Eq. (13), should be minimized in order to support the delay QoS requirement of the kth flow belonging to the delay-sensitive class. If the minimum value of Eq. (13) does not satisfy the delay QoS requirement, the values computed from the minimization would not be applied to the variable eij.
On top of the constraints in Eqs. (4)-(9), an additional two constraints should be defined, that are related to QoS and layer 3 processing rate. One constraint for tolerable QoS can be defined as
0 # f(ej) # 8k. (14)
The other one for layer 3 processing rate can be expressed as
Jj $ vij2l Xij + ejQjX
for all I, E.
(15
It is generally known that the multicommodity network flow problem with integer constraints is NP-hard [11]. Thus the k disjoint route problem which is NP-hard in Ref. [11] can be dealt with the same as that the k distinct egress node pairs find k mutually link-disjoint routes.
Whenever a new traffic flow belonging to delay-sensitive class requests explicitly routed GLSP, the virtual lightpath will be configured and the network state will be updated. Unless it is possible to support the GLSP with the desired QoS, the request can be blocked or renegotiated and attempted again. Alternatively, the network manager can preempt the minimum number of lower priority flows that will allow the GLSP to be set up. The procedure for the kth request, which does not account for preemption, proceeds as follows:
Step 0: Obtain the parameters associated with the kth setup request
Step 1: if a transmitter or a receiver is not available at k
or Ek
then go to Step 3;
Step 2: ifthere is any GLSP to minimize Eq. (13) then go to Step 4; else ifthe request is negotiable then relax sk and go to Step 2; else go to Step 3; Step 3: Block this GLSP request and go to Step 5; Step 4: Provision resources for the GLSP and update network state; Step 5: End;
To satisfy the requirements of diverse routing, rerouting and restoration as well as TE, ER is necessary for constructing lightpaths. The route on which a new lightpath is to be established is specified by an object contained in the GLSP setup message. This route is typically be chosen by the ingress O-LSR, but it could be determined by a higher level network management system. The route may be specified either as a series of routers/OXCs, or in terms of the specific links used. Therefore, the above mechanism performs the calculation of primary and restoration light-path routes on-line as the individual requests arrive. These lightpaths could be computed all at once by doing an offline calculation that accounts for all the pending requests.
Because the network loading varies over time, the consideration of the optimal route selection could require the reconfiguration of established lightpath routes, as described in Ref. [3]. Although frequent lightpath reroutings may not be acceptable, a limited number of lightpath reroutings could improve the network state, supporting the requested QoS of the future traffic while maintaining the QoS of the traffic that the network is already supporting. In the initial configuration stage where there is no configured virtual topology, the appropriate virtual lightpath could be found by repeating the above procedure. This procedure is applied to the traffic that has the most stringent delay limit among all initial traffic demands of delay-sensitive service class at all egress O-LSRs being done so to the traffic with the next highest QoS requirement, in turn. Like setting up usual GLSP, the virtual topology would be configured for the traffic demand of delay-sensitive service class at each egress OXC by minimizing the objective function of delay. By finding the values of all the elements of the set {X^}, we can obtain a full set of routing assignments for all the traffic in the optical network.
Failure of LSPs due to link failures is detected via
GMPLS signaling protocol (e.g. CR-LDP or RSVP-TE)
information by the edge routers. They can request a rerouting of the LSPs after the link-state database has been updated by routing protocols or by other means. (An alternative, not studied in the paper, is to setup a disjoint path backup GLSP so that failures can be accommodated by changing the FEC to GLSP mapping at the ingress routers.)
Let S be the set of Shared Risk Link Groups (SRLGs)
associated with elements of the network. A single link or node may belong to more than one SRLG. Define Sj to be the set of SRLG identifiers associated with the link
(i, j) and define Sn to the set of all Shared Risk Group (SRG) identifiers associated with node n. Then the full set of SRG identifiers for the network is just the union of all these sets: S = ((JnEN Sn)U(U'EL S'). In order to set up a M:N protection group with QoS constraints that generally routes M backup paths that are node disjoint from N primary paths, we can proceed in the following way. Let K = {ki}|=1 be the set of requests for working paths in the protection group. For the first working path k1, we can use the algorithm that we have described above since there is no SRLG/SRG constraint. The SRLG/SRG identifiers associated with the working path are accumulated in the set S(k1). In order to compute a backup path for this working path, which will have the same source and destination nodes Ik1 and Ek1 and the same delay and bandwidth QoS requirements ek1 and Bk1, we can do several things. One possibility is to execute the Shortest Path First (SPF) algorithm described in Ref. [4], with some modifications. Like Eq. (11), let
tn  ft (1 - pnE)xnE
be the average layer 3 processing delay at node n due to all the existing traffic flows that are passing through the node. Whenever a flow is added, modified, or deleted, {tn }n[N should be updated. Recall that we defined Dj to be the propagation delay on the link from Node i to Node j. Define Bj to be the available bandwidth on the link from i to j.
Step 1: If Bij < Bk1, set Dij = 1.
Step 2: If Sij [ S(k1), set Dij = 1.
Step 3: (Backup path initialization.) Set P = {Ik1}, m = Iki.
Let f(P) = ti be the total delay on the backup path. Step 4: Determine the node n * with the lowest delay cost with respect to node m, which satisfies
minnEN,nEP[Dm,n + Tn\:
Step 5: Add n * to P. f (P)=f (P) + Dmn* + tn*.
Step 6: Iff (P) > 8k1, no backup path satisfying the desired
QoS requirements can be found.
If n  = Ek1, the algorithm has executed successfully. Step 7: Set m = n  and go to Step 4.
If it is not possible to find a backup path with the desired QoS characteristics, the algorithm could be run again with relaxed values for the maximum delay or minimum bandwidth, although this could result in a degradation of performance in the event of a failure on the primary path, even if the flow is successfully switched over to the backup path.
4. Performance evaluation from simulation
Some simulation experiments have been conducted in order to study the performance of the proposed CR-GLSP routing algorithm. In this section, we present the simulation

Fig. 3. Network model.
results of the proposed algorithm and compare it to the well-known SPF algorithm using a set of simulations. We have run our algorithm several times using GMPLS Lightwave Agile Switching Simulator (GLASS) which was developed by NIST to evaluate control algorithms in integrated MPLS/optical networks [14], and calculated average blocking probability and average end-to-end delay. That is, the performance is analyzed in terms of the number of rejected CR-GLSP requests and delay.
In the first place, we describe a simulation environment used to validate our algorithm in providing service requested by delay-sensitive class. The simulation tests were carried out on a model of the network shown in Fig. 3(a), which has also been used in Ref. [15]. In this topology model, a maximum of four wavelengths are available for use in each link and the capacity is 10 Gbps. The propagation delay Dij is assumed to be 0.05 ms for all links (i, j), and the maximum tolerable delay limit of every GLSP request from delay-sensitive traffic is 0.5 ms. For this topology, we consider in this paper two network models: one model where the values of the Xj are assumed to be 1 for all the edge nodes and the other one where the network layer processing overhead is placed on the nodes 5, 8, 9, 12 and 14. Every GLSP request arrives at all edge nodes, according to a Poisson process with mean arrival rate, Xr of 200, 1000, 1500, and 2000 in each experiment, respectively. Like in Ref. [16], the arrival rates of traffic for the different source and destination pair were chosen from a uniformly distributed random variable in the interval [1, XIE]. The value of X IE was selected as 2.5 Gbps in this simulation experiment. 10% of total traffic flows belongs to delay-sensitive service class. We assume that the time between GLSP set-up and teardown is exponentially distributed with a mean of 1 min. When a GLSP set-up request arrives at an ingress node, the destination is chosen randomly among all the edge nodes except the ingress with the set-up request. All the simulations were run till 5000 GLSP set-up requests were generated and each simulation was repeated 10 times to get the average blocking rate and the average delay measured during the simulation.
The average blocking performance versus the GLSP setup requests is shown in Fig. 4 where graph (a) and (b) is the performance of overall traffic and that of delay sensitive

Fig. 4. Blocking probability for model 1.
traffic, respectively. Fig. 5 also shows the average blocking performance from the other set of simulations where the location of intermediate O-LSRs is changed, i.e. the layer 3 processing is at nodes 5, 8, 9, 12 and 14. The average blocking rate increases at the increasing of the GLSP set-up requests. Moreover, the gain due to the consideration of network layer processing is evident from these graphs. Therefore, we find that the proposed CR-GLSP algorithm performed better with respect to the blocking rate, which means that the CR-GLSP algorithm utilizes network resources more efficiently. This improvement is realized due to the fact that although CR-GLSP algorithm would not be able to find the available bandwidth over the path with the minimum delay, it tries to utilize the path with the next minimum delay keeping the tolerable delay.
Without performance degradation in blocking rate, we obtain the better performance in terms of average end-to-end delay. The average delay associated with both algorithms is presented in Table 1 measured during the overall simulation time for the two topology models where model 1 performs layer 3 processing at all the edge nodes and the model 2 does so at only the 5 nodes listed above. From Table 1, it can be observed that the average delay increases at the increasing of the GLSP set-up requests since the more GLSPs are requested to be established, the more the traffic flows into the network. Despite the increasing of the average delay, the average delay of the CR-GLSP algorithm is still smaller than that of SPF algorithm. This is due to the fact that the CR-GLSP algorithm incorporates network layer processing delay into routing decision. It resulted from this incorporation that the CR-GLSP algorithm chose different path from that in SPF algorithm between source node 2 and destination node 9. As can be seen in Fig. 3(b), the SPF algorithm routed the GLSP over the route 2 — 1 — 4 — 9 while the CR-GLSP algorithm selected the route 2 — 3 — 7 — 9.
Therefore, it is known that our formulation in CR-GLSP is applicable to ER of backup GLSP as well as working GLSP in large IP over WDM networks with QoS constraints.

Fig. 5. Blocking probability for model 2.
Table 1
Delay performance (Unit: ms: 1/Xr; GLSP requests)
1/Xr	CR-GLSP algorithm	SPF algorithm	
Model 1			
200	0.266	0.424	
1000	0.292	0.477	
1500	0.321	0.499	
2000	0.343	0.521	
Model 2			
200	0.215	0.371	
1000	0.228	0.417	
1500	0.257	0.421	
2000	0.275	0.429	
5. Conclusion
The success of next generation IP over WDM networking depends on the ability to offer and support QoS to customers. It is clear that network layer processing cannot be neglected for designing TE algorithms as well as for this. In this paper, we formulated an optimization problem for constraint-based routing to support the QoS requested by delay-sensitive traffic in optical Internet. The CR-GLSP algorithm described in this paper is based on the idea that traffic flows encounter the delay resulting from layer 3 processing at subnetwork edge nodes. The algorithm uses the current state of the network to determine the delay associated with each possible path, and then chooses the path with the minimum total delay. The simulation results showed that the proposed algorithm improves the delay performance as well as the probability of successful GLSP establishment in comparison to SPF algorithm, which do not take the network layer processing into account. In the simulation test, GLASS tool was used as a simulation tool that was developed by NIST for optical Internet. The presented algorithm can also be used for establishing backup path with delay constraint and we described how to apply to protection.
The future study is network survivability which is also treated as an important issue recently. We are designing a several efficient restoration algorithms that ensure its survivability in optical Internet while we sustain the delay
QoS. At that time, it is worth noting multiple service categories whose level of restoration is different.
References
[1] E. Rosen, A. Viswanathan, R. Callon, Multiprotocol Label Switching Architecture, RFC 3031, January, 2001.
[2] A. Banerjee, J. Drakes, J.P. Lang, B. Turner, K. Kompella, Y. Rekhter, Generalized multiprotocol label switching: an overview of routing and management enhancements, IEEE Commun. Mag.
January (2001).
[3] G. Apostolopoulos, D. Williams, S. Kamat, R. Guerin, A. Orda, T. Przygienda, QoS Routing Mechanisms and OSPF Extensions, RFC
2676, August, 1999.
[4] Z. Wang, J. Crowcroft, "Quality-of-Service Routing for Supporting
Multimedia Applications", IEEE JSAC 14 (7) (1996). [5] N. Golmie, T.D. Ndousse, D. Su, A differentiated optical services
model for WDM networks, IEEE Commun. Mag. 38 (2) (2000).
[6] H. Harai, F. Kubota, H. Nakazato, Design of reconfigurable lightpaths in IP over WDM networks, IEICE Trans. Commun. E83-B (10)
(2000).
[7] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus, Requirements for Traffic Engineering over MPLS, RFC 2702,
September, 1999.
[8] Data Connection Computer Technology, MPLS Traffic Engineering: A Choice of Signaling Protocols, http://www.dataconnection.com/ download/crldprsvp.pdf.
[9] P. Ashwood, A. Banerjee, L. Berger, G. Bernstein, J. Drake, Y. Fan, K. Kompella, J.P. Lang, F. Liaw, E. Mannie, P. Pan, B. Rajagopalan, Y. Rekhter, D. Saha, V. Sharma, G. Swallow, Z.B. Tang, Generalized MPLS Signaling-RSVP-TE Extensions, Work on Progress, draft-ietf-mpls-generalized-rsvp-te-04.txt, July, 2001. [10] P. Ashwood, A. Banerjee, L. Berger, G. Bernstein, J. Drake, Y. Fan, D. Fedyk, K. Kompella, E. Mannie, J.P. Lang, B. Rajagopalan, Y.
Rekhter, V. Sharma, G. Swallow, Z.B. Tang, Generalized MPLS
Signaling-CR-LDP Extensions, Work on Progress, draft-ietf-mpls-generalized-cr-ldp-04.txt, July, 2001. [11] M. Garey, D. Johnson, Computers and Intractability, W.H. Freeman,
New York, 1979.
[12] I. Chlamtac, A. Ganz, G. Karmi, Lightpath communications: an approach to high bandwidth optical WANs, IEEE Trans. Commun. 40
(7) (1992).
[13] R. Ramaswami, K.N. Sivarajan, Optical Networks: a Practical
Perspective, Morgan Kaufmann, Los altos, CA, 1998. [14] NIST, http://www.antd.nist.gov/proj/asia/glass/. [15] K. Kar, M. Kodialam, T.V. Lakshman, Minimum interference routing
of bandwidth guaranteed tunnels with MPLS traffic engineering
applications, IEEE JSAC 18 (12) (2000). [16] I. Widjaja, A.I. Elwalid, Study of GMPLS Lightpath Setup over
Lambda-Router Networks, ICC'02, May, 2002.