Path Computation Algorithms for Dynamic Service

Provisioning in SDH Networks

R.Madanagopal∗ , N.Usha Rani† , Timothy A. Gonsalves∗
∗ Department of Computer Science and Engineering
Indian Institute of Technology Madras
Chennai, India
Email: {madan,tag}@lantana.tenet.res.in
† NMSWorks Software Pvt. Ltd.
Chennai, India
Email: usha@nmsworks.co.in

Abstract— Synchronous Digital Hierarchy (SDH) is a time divi- are provisioned manually by the service providers by logging
sion multiplexing technology widely used in transport networks to into management systems and doing provisioning related activ-
provide bandwidth services. Dynamic service provisioning refers ities using them. They have to take into account the requested
to the arrival of service requests one-by-one randomly with no
prior information on future requests. This requires the use of demand, required QoS, available network resources and the
on-line algorithms which automatically compute the path to be ability to accommodate future requests before starting the
taken to satisfy the given service request. This problem involves a work of provisioning a requested service. This implies manual
tradeoff between minimizing the number of requests that are re- path computation and maintenance of huge inventory details.
jected and minimizing the total bandwidth that is utilized. Many Then the configuration on the network elements involved has
earlier works have addressed path computation algorithms, but
they treat each link as having some integer units of bandwidth. to be done. These processes being manual, are tedious and
They do not take into account the multiplexing structure defined more error prone. It might not result in optimal usage of
by SDH which imposes restrictions on the allocation of bandwidth network resources. The time required to provision a service
and the fact that higher order trails (logical connections) have will be more. But minimizing service turn-on times is the
to be established to support any bandwidth requirement. In key to accommodate more service requests in less time which
this work, these factors are considered in the path computation
algorithms. The network is treated as a graph containing physical results in maximizing the revenue for service providers.
links and logical trails and weights are assigned to them before The solution to this problem is to have automatic provision-
computing a path with the least cost. Weights are assigned such ing systems. Operators should be able to give the end-points of
that the trails are given higher preference to physical links the service and the bandwidth required and the system should
so that existing trails are used wherever possible. This avoids be able to provision the bandwidth automatically by calcu-
unnecessary creation of new trails. The performance is evaluated
for different values of weights. An improvement in the form of lating the appropriate path such that the network resources
dynamically adjusting the weights of links and trails is done are optimally utilized. Network Management Systems (NMS)
and its performance is shown to be better than having constant or Provisioning Management Systems (PMS) which have the
weights. complete network topology and the inventory details should
be able to perform the provisioning operation. Firstly the
I. I NTRODUCTION
NMS/PMS should be able to get the inventory details from the
In the current environment of high speed communications, database or the Element Management Systems (EMS) or the
network operators and service providers are constantly flooded Network Elements (NE) directly and it should be able to issue
with bandwidth requirements. This has led to the development configuration commands to them to provision the requested
of different transport technologies like PDH, SONET/SDH, capacity in the network elements involved. The other task
WDM/DWDM, ATM, DSL etc. Also, the need for providing is to find the best path to be used to satisfy the requested
differentiated services with different Quality of Service (QoS) service taking into account the capacity that is already in
requirements is being seen as a good opportunity by service use, free capacity available such that more future requests
providers to increase their revenue[1]. In this scenario, it is can be accommodated and the network resources are utilized
envisaged that there will be a large number of service requests optimally. This second aspect is the focus of this work.
with different QoS requirements which implies there will be The remainder of this paper is organized as follows. Section
a constant change in configuration of the network. This is II gives details regarding related work. Section III describes the
compounded by the fact that the service providers will try to path computation problem in SDH networks by describing the
use the available network resources efficiently before investing unique aspects that need to be considered. Section IV describes
in further resources. the details of the various algorithms proposed in this paper and
Service providers require faster provisioning of services to their limitations if any. Also, it describes how the algorithms
satisfy more customer requests in less time. Typically, services can be extended for computing dedicated protection paths in

1-4244-0799-0/07/$25.00 ©2007 IEEE 206

addition to the computing a working path. The performance approach to dynamic survivable service routing. SBPP can
of the algorithms are analyzed in Section V. Finally, Section be thought of as arranging a set of diverse protection paths
VI concludes this paper. but keeping the spare links on the backup paths unconnected
and shared with other setups, with connection occurring as
II. R ELATED W ORK needed upon failure. The aim is to increase capacity efficiency
Various earlier works have addressed the path computation by allowing sharing of protection channels between primary
problem in different networks. One of them is the all-optical working paths that do not have any single-failure modalities
network lightpath provisioning problem. The issue here is in common. Technically, such primary paths are said to have
to provide routes to the lightpath requests and to assign no Shared Risk Link Groups (SRLG) in common. As a
wavelengths on each of the links along this route among result, fewer spare capacity is needed to protect more working
the possible choices so as to optimize a certain performance capacity with the assumption that not all the working paths fail
metric. This is the commonly known Routing and Wavelength at the same time.
Assignment (RWA) problem[2], [3], [4]. This has been con- The Protected Working Capacity Envelope (PWCE)[9] con-
sidered with both static and dynamic traffic demands. Also, cept involves adaptation of static design models to create
it has been studied with no wavelength conversion, partial not an exact solution for one single demand matrix, but
wavelength conversion and full wavelength conversion. In an envelope of protected working channels, well suited for
work to date, it has been formulated as a difficult integer a large family of random demand instances that may be
linear programming (ILP) problem that does not lend itself somehow related to a single representative demand pattern.
to efficient solution. Different heuristics have been proposed An important property is that actions of any type related
and the problem solved based on different assumptions[5]. to ensuring protection occur only on the time-scale of the
An integrated topology independent procedure to solve the statistical evolution of the network load pattern itself, not on
RWA problem to minimize the number of SONET ADMs is the time-scale of individual connections. Protection cycles (p-
proposed in [6]. cycles) with support for the protection of spans on the ring is
Distributed path computation and provisioning is another chosen for implementing PWCE.
area studied extensively. Many centralized schemes have been The problem of dynamically routing QoS guaranteed paths
proposed which take the entire network topology and compute with restoration in MPLS networks is studied in [10]. Restora-
paths for the requested bandwidth demands. Since centralized bility implies that to successfully route a path set-up request
schemes are not scalable for large network sizes, distributed both an active path and an alternate link (node) disjoint
route computation and provisioning has been proposed[7]. backup path have to be routed at the same time. The backup
While distributed control enhances scalability and flexibility, paths can be shared amongst certain active paths while still
it might result in suboptimal path computation as a result maintaining restorability. ILP formulation of this problem is
of summarization of resource information. Summarization is given and it is shown that a partial information scenario which
needed since each node cannot maintain the complete network uses only aggregated information instead of complete per-
topology and resource information. The tradeoff is between the path information for routing performs well and the number of
path computation efficiency and the amount of information to requests rejected is very close to the full information bound.
be disseminated. Two approaches for provisioning of survivable Data
In this regard, generalized MPLS (GMPLS) by IETF is over SONET/SDH (DoS) connections utilizing the inverse-
being introduced as the most suitable control plane solution for multiplexing capability of virtual concatenation have been
next-generation optical infrastructure. This provides a frame- proposed in [11]. Virtual concatenation is a technique which
work in which the well-known and proven MPLS paradigm is groups an arbitrary number of SONET/SDH containers, which
being extended to be a control plane not only for routers etc. may not be contiguous, to create a bigger container. A new
but also for optical and other transport network elements. This scheme for real-time bandwidth allocation and path restoration
is achieved by means of Traffic Engineering (TE) extensions in SONET mesh networks, in response to demand and load
to a suite of protocols like OSPF, IS-IS, RSVP, LDP etc. Apart dynamics is presented in [12]. Various options for routing in
from IETF, ITU has defined a set of distributed control plane SDH networks for ring and mesh topologies are described
specifications for the Automatic Switched Optical Network in [13]. A sequential algorithm and a parallel algorithm for
(ASON). OIF is also working on user-to-network interface computing disjoint paths for protection and QoS for next
(UNI) and network-to-network interface (NNI) for optical generation SONET networks have been proposed in [14]
networks. Path computation in SONET rings using GMPLS by where the shortest path is computed based on the delay
creating Label Switched Paths (LSP) by making small changes in the links and the bandwidth requested. A generic ap-
in OSPF-TE LSA processing rules and RSVP-TE signaling proach to service-differentiated connection accommodation in
mechanism is proposed in [8]. wavelength-routed networks is proposed in [15].
The problem of efficiently managing and configuring a
transport network to both route and protect services in the face III. PATH C OMPUTATION P ROBLEM IN SDH N ETWORKS
of traffic uncertainty in time and space has been framed within All these works have one thing in common. They consider a
what is called the Shared Backup Path Protection (SBPP)[9] graph of the network topology containing nodes representing

207
 Fig. 1. SDH Multiplexing Structure

the network elements present and links inter-connecting them cannot be assumed to have simply some integer units of
with integer units of capacity. This allows to them to formulate capacity and the free capacity cannot be obtained simply by
the problem mathematically and numerical solutions are thus subtracting the alloted capacity from the maximum capacity
possible. In some cases, weights are associated with the links and allocations cannot be made until the free capacity becomes
taking into account different constraints and traffic engineering zero. In SDH, higher order containers like VC-4 have to be
parameters. Those algorithms then attempt to compute paths used to create trails between the source and destination nodes
such that they take the shortest route or a route that minimizes before provisioning any bandwidth between two points. This
the network resources consumed. For protection paths, the aim means that even to have a E1 bandwidth which maps to VC-12
is to use the existing protection routes as much as possible by in SDH between two points, a single VC-4 trail or a sequence
sharing in such a way their corresponding working paths are of VC-4 trails have to be available already or have to be
not affected by a single failure. established newly.
But when it comes to provisioning in transport networks When a VC-12 (approximately 2 Mbps) is provisioned in a
particularly SONET/SDH networks, links cannot be simply newly created VC-4 trail, then that trail cannot support a future
considered to have certain integer units of capacity as the VC-4 request since the full capacity is not available any more.
multiplexing structure defined by those technologies has to Similarly, it can accommodate only two future VC-3 requests
be followed while provisioning the requested services. The since out of a maximum of 3 VC-3s that can be multiplexed
multiplexing structure defined by SDH[16] is shown in Fig. 1. to form a VC-4, the first one is broken to accommodate the
The common G.703[17] signals such as E1, E4, DS1, DS3 requested VC-12 service. If 3 VC-12s are provisioned in the 3
etc. are mapped into their corresponding virtual containers VC- different VC-3s, then that VC-4 trail cannot accommodate any
12, VC-4, VC-11, VC-3. The lower order virtual containers further VC-3 requests even though only 3 * 2 = 6 Mbps out of
like VC-11, VC-12, VC-2 are pointed to by their tributary unit the potential 140 Mbps for a VC-4 is currently alloted since
(TU) pointers. These are then multiplexed into tributary unit all VC-3s are broken. Similar restrictions apply for other rates
groups (TUG) which are then multiplexed into higher order like VC-2 and VC-11. Also in SDH, any arbitrary bandwidth
virtual containers like VC-3 and VC-4. They are pointed to by cannot be provisioned in a trail. Only those standard rates
their administrative unit (AU) pointers and then multiplexed defined in SDH are allowed. So the requests cannot be in
into administrative unit groups (AUG) which are in turn numerical units of bandwidth, but in one of those standard
multiplexed into one of the possible Synchronous Transport rates.
Modules (STM) which are the units of transmission in SDH. In summary, the existing path computation algorithms can-
Similar structure exists for SONET as well. not be used as such for SDH networks for the following two
Because of this multiplexing structure of SDH, each link reasons:

208
 1) In SDH systems, trails have to be present or created
newly before provisioning any service.
2) SDH defines a strict multiplexing structure which has
to be followed while provisioning a service. All service
requests must fit into one of the standard rates supported
by SDH.
This paper deals with path computation algorithms for SDH
taking into account the above two considerations.

IV. PATH C OMPUTATION A LGORITHMS

A path computation algorithm finds minimum cost path
between the source and destination nodes for a requested
service with some requested capacity. The algorithms have
to be dynamic since the requests come online and they have
to be satisfied as soon as possible. Since the algorithms have
to be dynamic they will have no idea on the future requests Fig. 2. A Sample Network
that are possible. The algorithms should have performed such
that they have used the network resources efficiently until
that instant. The algorithms presented in this paper are online When a service request comes and there exists a sequence
without taking into account the possibility of reconfiguration of trails, it makes sense to use those trails rather than create
of the services later for better network resource utilization. new trails. So, trails have to be given higher preference than
Service providers like to achieve the twin goals of maxi- physical links which in turn means that the weight of a trail
mizing the number of requests serviced and minimizing the has to be less than the sum of the weights of the links. This
total bandwidth consumed. Also, the number of trails created is achieved for a trail t as:
should be minimum so that the bandwidth is not fragmented.

Less fragmentation means more number of high bandwidth w(t) = α ∗ w(l) (1)
requests getting accepted in the future. This implies the l∈L
network resources have to be optimally utilized so that more
where w(t) is the weight associated with the trail t, w(l) is
number of future requests can be accommodated resulting in
the weight associated with the link l, L is set of links on
maximization of the revenue. Therefore, the path computation
the path through which the trail is established, α is some
algorithms should be able to function such that the following
value between 0 and 1 and * denotes multiplication. Thus
three goals are met in the best possible way:
this equation assigns the weight for a trail as a fraction of
1) Minimizing the number of requests rejected. the sum of the weights of the links traversed by that trail.
2) Minimizing the total amount of bandwidth consumed to As a result, the weight of the trail will be less than or equal
satisfy the requested services. to the sum of the weights of the links traversed. So this trail
3) Minimizing the number of trails created. will be chosen instead of establishing new trail(s) along that
The topology of the network is represented as a graph path. Lower weights are given higher preference since the
G(V, E), where V is the set of network elements or nodes path chosen will be shorter if those links or trails are used
present in the network and E is the set of edges in the network. during path computation. The weight of the physical link can
The set of edges include both the set of the links and the be thought of as the cost of creating a new trail on that link.
set of trails present in the network. Since the services can When a new trail needs to be created, it can be created as
be provisioned only over VC-4 trails because of the SDH an end-to-end trail between the source and destination nodes
multiplexing structure, the set E includes both the physical or individual trails can be created on the links that are part
links connecting the network elements and the logical trails of the path that is found. The latter option is used in all the
created between them for satisfying service requests. Each algorithms since the creation of an end-to-end trail may not
physical link is associated with a weight which can be chosen result in efficient network resource utilization as it can be used
based on any criteria such as distance etc. If there is no need only by those requests that need to go through both the nodes
to distinguish the physical links based on any criteria then all between which the trail was created. In Fig. 2, the trail aed
their weights can be made equal. is an example of an end-to-end trail. Though this trail passes
A sample network is shown in Fig. 2. The solid lines through e, it can carry traffic only between a and d as the
represent physical links and the dashed lines represent trails VC-4 used is only cross-connected and not terminated at e.
which are logical links. If the capacity of the link is STM-N, To have better resource utilization of network resources, it
then N trails can use that link. A path is a sequence of links makes sense to create two separate trails, one between a and
and trails. If the path contains links, then trails have to be e and the other between e and d so that there is flexibility to
created on those links for carrying traffic. carry traffic between any two of those three nodes.

209
 The algorithms described use the weights as calculated • If no path can be found in the graph containing only trails,
above in finding the paths. Dijkstra’s shortest path algorithm it finds a path in the graph containing only links without
is used to find the weighted shortest path in the graph of taking account all the trails that are already present
the network. Shortest path here refers to the path such that
Algorithm 2
the sum of the weights of the links and trails constituting
it is the minimum. A simple algorithm is described initially. The main reason for the limitations of Algorithm 1 is that
Then two more algorithms which address the limitations of it performs the same sequences of steps twice once on the
the earlier algorithms are described to get better results. The graph containing only trails and again on the graph containing
path computation algorithms described below find a working only links. This can be overcome by a forming a single graph
path for the requested service. Extension to these algorithms containing both the trails and links that are present. There
to find dedicated protection paths is provided finally. must be differentiation between trails and links so that trails
are preferred to links wherever possible. This is achieved by
Algorithm 1 assigning weights for trails as described earlier as a fraction
1) Find the shortest path in the graph containing only of the sum of the weights of the links traversed by it. The
logical trails modified algorithm is given below:
2) If no path exists, go to Step 4 1) Find the shortest path in the graph containing both links
3) If capacity is available in all the trails along the path and trails
found 2) If no path exists, then report failure and stop
then 3) If capacity is available in all the links and trails along
provision the requested capacity and adjust free the path
capacity in the trails along the path found then
stop create trails wherever required or use existing
else trails and provision the requested capacity in
eliminate those trails where capacity is not them and adjust free capacity
available and go to Step 1 else
4) Find the shortest path in the graph containing only eliminate those links and trails where capacity
physical links is not available and go to Step 1
5) If no path exists, then report failure and stop The shortest path computed by this algorithm will have a
6) If capacity is available in all the links along the path combination of both trails and links. New trails will be created
found whenever links are found and the trails will be used as such
then whenever they are found. This will result in an optimal path
create trails wherever required or use existing containing already created trails that can be used and new trails
trails and provision the requested capacity in that are created when they need to be done so. The value of α
them and adjust free capacity will affect the behavior of the algorithm in terms of the number
else of requests accepted and the total bandwidth consumed.
eliminate those links and trails where capacity Limitations of Algorithm 2
is not available and go to Step 4 • When more than one shortest path exists between two
This algorithm follows a greedy approach. It tries to find the nodes, one of them is chosen for this request and all the
shortest path in the graph containing only trails so that no new future requests which require those nodes in the path. In
trails need to be created. If no path exists in that graph, then this way, it overloads one path instead of distributing the
it finds the shortest path in the graph containing only physical load
links. If there are trails present along the links constituting • It does not take into account the free capacity available
that path, then they are used else new trails are created. The in the links
requested capacity is provisioned on the trails found or created • It does not give weightage to a trail where a low rate like
and the free capacity is adjusted accordingly. If capacity is VC-12 can be accommodated as such when compared to
not available in any of the trails or links found, then they a trail in which a VC-3 or a VC-2 needs to be broken
are eliminated and the process is repeated until either a path to accommodate the requested rate. This may result in
that can accommodate the requested capacity is found or no creation of new trails later when VC-3 or VC-2 requests
more paths can be found in which case the service request is come in the future. In other words, this might result in
rejected. fragmentation of the capacity in the trails present
Limitations of Algorithm 1 Algorithm 3
• It tries to find a path in the graph containing only trails The main reason for the limitations of Algorithm 2 is that
even though it may be circuitous thus consuming more the weights are constant for the links and trails. In other
bandwidth words, the weights once assigned are not changed. As a

210
result, the algorithm is not adaptive to the changing network • If a VC-3 has to be broken, then β is set to 1 since all
characteristics. The weights have to be dynamically changed possible containers have to be broken
for the algorithm to be truly reflective of the current state of • If a VC-3 need not be broken, then this is the most
the network. This will lead to better results in terms of the desirable case and β is set to a value less than 1 (referred
optimal utilization of the network resources. as β3 )
For links, the dynamic weight adjustment has to be based For a VC-3 to be created it must be multiplexed into a VC-
on the free capacity available in a link. Link weight has to 4. So a VC-4 always have to be broken to service a VC-3
be increased and not decreased so that it doesn’t become less request. So β is always set to 1 in this case. But the use of
than the weight of a trail created on that link. One form of an existing trail and the creation of a trail for accommodating
dynamic weight adjustment for a link l is: this VC-3 request has to be differentiated. This is inherently
done since the weight of the trail will be used in the earlier
c(l)
w(l) = wi (l) + ∗ wi (l) (2) case which will be less than the weight of the link which will
cmax (l) be used in the latter case.
where wi (l) is the initial weight associated with the link For a VC-4 request, a new trail has to be created always
l, c(l) is the capacity used in the link l and cmax (l) is the whose cost will be covered as the weight of the links involved
maximum possible capacity of the link l. The weight of the in its creation.
link now reflects the capacity used and the capacity available
Provisioning of capacity in trails
in the link. The link weight increases whenever new trails are
created in that link. As a result, this link will not be chosen Once the path is computed then the requested capacity has
when another link with a lesser capacity utilization compared to be provisioned in the trails that belong to that path. To
to this is available. This will result in the balancing of the load achieve this, the next free slot for each rate in the trail is
across many links that are possible candidates for the shortest maintained. For VC-4 rate, the only value that is possible is
path. 1. For VC-3 it is from 1 to 3, for VC-2 it is from 1 to 21, for
However for trails, free capacity is not the most important VC-12 it is from 1 to 63 and for VC-11 it is from 1 to 84.
criteria for dynamically adjusting weights. Instead the weight Whenever a trail is created the free slot for all the rates are
of the trail can be reduced when there is no need for breaking set to 1. Subsequently, the slots are alloted sequentially. When
higher rate containers like VC-3 and VC-2. This will avoid high rate containers have to be broken to accommodate a low
fragmentation of the available bandwidth in trails and new rate request, then the free slot for those high rates according
trails need not be created whenever service requests for higher to the multiplexing structure are increased by 1. For example,
rates are made in the future. This is achieved for a trail t as: if a VC-12 request is made and a new trail created for it, then

the free slots for VC-3 and VC-2 are increased by 1. Then
w(t) = β ∗ α ∗ w(l) (3) the free slot for VC-12 is also increased by 1. Now if a VC-
l∈L 3 request needs to be accommodated in this trail, the second
VC-3 will be alloted to this request and the free VC-3 slot
where β is a number between 0 and 1 such that the weight
value is increased to 3. Now if successive VC-12 requests are
of the trail is reduced when there is no need to break high rate
made that have to be accommodated in this trail, they will be
containers. Since different rates of bandwidth follow different
alloted values from 2 to 21 which is the maximum value that
multiplexing route in SDH, maintaining a single weight for
is possible as a result of breaking the first VC-3. If another
all rates will not reflect the correct status on breaking for
VC-12 request is made, it will be alloted the slot 43 since the
each rate. So different dynamic weights for different rates are
second VC-3 is already alloted for a VC-3 request. Similar
maintained for each trail and the weight corresponding to the
mechanism is used when provisioning requests for other rates
requested rate is used in the path computation step.
are made.
According to the SDH multiplexing structure, for a VC-12
and VC-11 to be created it must be multiplexed into a VC-2, Provisioning of capacity in links
then into a VC-3 and finally into a VC-4. The dynamic weight
For links, provisioning involves creation of VC-4 trails
adjustment for VC-12 and VC-11 rates in a trail is:
along that link. In SDH, the standard transport rates defined are
• If both VC-3 and VC-2 have to be broken, then β is set STM-1, STM-4, STM-16, STM-64 and STM-256. The number
to 1 since all possible containers have to be broken after STM indicates the number of VC-4 trails that can be
• If VC-3 need not be broken but a VC-2 has to be broken, created on that link. Whenever new trails are created on the
then β is set to a value less than 1 (referred as β2 ) link, the free capacity is reduced accordingly. New trails can
• If both VC-3 and VC-2 need not be broken, then this is be created until the free capacity becomes 0.
the most desirable case and β is set to a value less than
that chosen in the previous case (referred as β1 ) Extension to support dedicated protection paths
For a VC-2 to be created it must be multiplexed into a VC- The algorithms described above compute a path for the
3 and then into a VC-4. The dynamic weight adjustment for given service request between two nodes for the requested
VC-2 rate in a trail is: capacity. This is typically the working path for the given

211
service request. But customers typically want high availability treated equally. For example, a VC4 is equivalent to 63 VC12s.
for the services they take from the service providers. This is So, an execution that rejects a VC4 request due to lack of
achieved by protecting the service through some other route capacity and accepts less than 63 future VC12 requests will
so that even when the working path fails, the service can show better performance when compared to an execution that
be continued in a protection path. There are two types of accepts the VC4 request and rejects the future VC12 requests.
protection: dedicated and shared. A dedicated protection path To overcome this problem, the requests that are accepted have
is exclusively reserved for one working path and protects only to be weighted according to the relative bandwidth to get
that path. This is commonly referred to as 1+1 protection. a better indication of the performance. This is achieved by
Shared protection refers to the case where one protection keeping VC12 as the base and multiplying each VC4 request
path is shared among many working paths such that any one by 63, VC3 request by 21 and VC2 request by 3.
working path failure is overcome by this protection path. But In each experiment the following parameters are considered:
this can protect only one working path at the maximum. This 1) Weighted number of service requests accepted.
is commonly referred to as 1+N protection. This is employed 2) Number of service requests rejected.
when network resources are not at a premium and when it 3) Number of trails created.
can be assumed that not all working paths will fail at the 4) Percentage of the total bandwidth consumed to satisfy
same time. the accepted requests.
To find a dedicated protection path for a given service The experiments are run with the above configuration for
request in addition to finding a working path, the above evaluating Algorithm 1. For evaluating Algorithm 2, the value
algorithms can be used as follows: of α in (1) is varied from 0.1 to 1.0 with increments of 0.1. For
1) Use one of the algorithms to find a working path. evaluating Algorithm 3, the values for β1 , β2 and β3 are varied
2) Eliminate the edges which are part of the working path from 0.3 to 0.7, 0.4 to 0.8 and 0.5 to 0.9 respectively. The
(if the protection path has to be edge disjoint) and experiments are run for the three networks 10 times each with
the nodes which are path of the working path (if the different sets of random service requests. The results obtained
protection path has to be node disjoint) from the graph. in one of the 10 iterations for the four parameters mentioned
3) Use the same algorithm used earlier to get a path which above are shown in Figs. 3-6 for Network 1, Figs. 7-10 for
can be used as the protection path. Network 2 and Figs. 11-14 for Network 3. Similar results were
The above algorithm is similar to the sequential algorithm obtained in the other 9 iterations as well.
used in [14]. From the results obtained, it is found that the Algorithm
2 gives better results by minimizing the number of requests
V. P ERFORMANCE R ESULTS rejected, trails created and total bandwidth utilized than Al-
The performance of the described algorithms are evaluated gorithm 1 for almost all the values of α between 0.1 and
and the results obtained are provided in this section. The 1.0. This shows that the greedy approach of Algorithm 1 is
experiments were performed on the three following networks: not able to perform as well when compared to Algorithm 2
where the problem is solved by considering a single graph
• Network 1: 70 nodes, 103 links
containing both trails and links and the best path as a whole
• Network 2: 14 nodes, 21 links (National Science Foun-
is found. Further, the Algorithm 3 with dynamic adjustment of
dation (NSF) network)
weights is able to perform better when compared to Algorithm
• Network 3: 47 nodes, 82 links (a national service provider
2 which uses constant weights. This is due to the balancing
(VSNL) network)
of load achieved by means of dynamic adjustment of weights
The service requests are randomly generated and the per- which results in the optimal usage of network resources. But,
formance of the algorithms are evaluated by running 10 in certain cases it can be observed that Algorithm 1 is giving
iterations, each with different sets of service requests for all the better results when compared to Algorithm 2 and Algorithm
three networks, which are simulated. In each iteration, service 3 for lower values of α. So very low values for α are not
requests are generated as follows: desirable.
1) Per iteration some number of requests are generated such Also it is found that the values of 0.6 to 0.9 for α results
that a small fraction of them are rejected. in the minimum number of requests being rejected while the
2) Source node and destination node are chosen randomly weighted number of requests accepted is maximum. At the
for each service request. same time, the number of trails created is also lesser for these
3) The bandwidth requirement is generated in the following values of α. For some values of α other than 0.6 to 0.9, the
proportion: VC4 - 4%, VC3 - 10%, VC2 - 6%, VC12 number of trails created is less when compared with those for
- 80%. This is roughly the distribution of bandwidth α between 0.6 and 0.9. In these cases, the number of requests
requirements for services received by a well-known accepted is less and so the number of trails created is also
national service provider (VSNL). less. But when the number of trails created proportional to the
The number of requests rejected is an important parameter number of requests accepted is considered, the values of α
that has to be evaluated. However, since different service between 0.6 and 0.9 is better when compared to other values
requests are for different bandwidth rates, they cannot be of α. The same holds for the percentage of total bandwidth

212
 Algorithm 1 Algorithm 1
7800 Algorithm 2 66 Algorithm 2
WEIGHTED NUMBER OF REQUESTS ACCEPTED

PERCENTAGE OF TOTAL BANDWIDTH UTILIZED

Alg. 3 - 0.3,0.4,0.5 Alg. 3 - 0.3,0.4,0.5
Alg. 3 - 0.4,0.5,0.6 Alg. 3 - 0.4,0.5,0.6
Alg. 3 - 0.5,0.6,0.7 Alg. 3 - 0.5,0.6,0.7
7700 Alg. 3 - 0.6,0.7,0.8 64 Alg. 3 - 0.6,0.7,0.8
Alg. 3 - 0.7,0.8,0.9 Alg. 3 - 0.7,0.8,0.9

62
7600

60
7500

58
7400

56
7300

54
7200
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
ALPHA ALPHA

Fig. 3. Weighted number of requests accepted in Network 1 Fig. 6. Bandwidth utilized in Network 1

1800
Algorithm 1 Algorithm 1
120 Algorithm 2 Algorithm 2
NUMBER OF REQUESTS REJECTED (out of 1500)

WEIGHTED NUMBER OF REQUESTS ACCEPTED

Alg. 3 - 0.3,0.4,0.5 Alg. 3 - 0.3,0.4,0.5
Alg. 3 - 0.4,0.5,0.6 1750 Alg. 3 - 0.4,0.5,0.6
Alg. 3 - 0.5,0.6,0.7 Alg. 3 - 0.5,0.6,0.7
Alg. 3 - 0.6,0.7,0.8 Alg. 3 - 0.6,0.7,0.8
100 Alg. 3 - 0.7,0.8,0.9 Alg. 3 - 0.7,0.8,0.9
1700

80 1650

60 1600

1550
40

1500
20

1450
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
ALPHA ALPHA

Fig. 4. Number of requests rejected in Network 1 Fig. 7. Weighted number of requests accepted in Network 2

860 70
Algorithm 1 Algorithm 1
Algorithm 2 Algorithm 2
NUMBER OF REQUESTS REJECTED (out of 400)

Alg. 3 - 0.3,0.4,0.5 Alg. 3 - 0.3,0.4,0.5

840 Alg. 3 - 0.4,0.5,0.6 60 Alg. 3 - 0.4,0.5,0.6
Alg. 3 - 0.5,0.6,0.7 Alg. 3 - 0.5,0.6,0.7
Alg. 3 - 0.6,0.7,0.8 Alg. 3 - 0.6,0.7,0.8
NUMBER OF TRAILS CREATED

Alg. 3 - 0.7,0.8,0.9 Alg. 3 - 0.7,0.8,0.9

820 50

800 40

30
780

20
760

10
740

0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
ALPHA ALPHA

Fig. 5. Number of trails created in Network 1 Fig. 8. Number of requests rejected in Network 2

213
 80 90
Algorithm 1 Algorithm 1
Algorithm 2 Algorithm 2

NUMBER OF REQUESTS REJECTED (out of 900)

Alg. 3 - 0.3,0.4,0.5 Alg. 3 - 0.3,0.4,0.5
Alg. 3 - 0.4,0.5,0.6 Alg. 3 - 0.4,0.5,0.6
Alg. 3 - 0.5,0.6,0.7 Alg. 3 - 0.5,0.6,0.7
Alg. 3 - 0.6,0.7,0.8 80 Alg. 3 - 0.6,0.7,0.8
NUMBER OF TRAILS CREATED

75 Alg. 3 - 0.7,0.8,0.9 Alg. 3 - 0.7,0.8,0.9

70

70

60

65
50

60 40
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
ALPHA ALPHA

Fig. 9. Number of trails created in Network 2 Fig. 12. Number of requests rejected in Network 3

85 300
Algorithm 1 Algorithm 1
Algorithm 2 Algorithm 2
PERCENTAGE OF TOTAL BANDWIDTH UTILIZED

Alg. 3 - 0.3,0.4,0.5 Alg. 3 - 0.3,0.4,0.5

Alg. 3 - 0.4,0.5,0.6 295 Alg. 3 - 0.4,0.5,0.6
Alg. 3 - 0.5,0.6,0.7 Alg. 3 - 0.5,0.6,0.7
80 Alg. 3 - 0.6,0.7,0.8 Alg. 3 - 0.6,0.7,0.8
NUMBER OF TRAILS CREATED

Alg. 3 - 0.7,0.8,0.9 Alg. 3 - 0.7,0.8,0.9

290

75
285

280
70

275

65
270

60 265
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
ALPHA ALPHA

Fig. 10. Bandwidth utilized in Network 2 Fig. 13. Number of trails created in Network 3

4260
Algorithm 1 Algorithm 1
Algorithm 2 Algorithm 2
WEIGHTED NUMBER OF REQUESTS ACCEPTED

PERCENTAGE OF TOTAL BANDWIDTH UTILIZED

Alg. 3 - 0.3,0.4,0.5 54 Alg. 3 - 0.3,0.4,0.5

Alg. 3 - 0.4,0.5,0.6 Alg. 3 - 0.4,0.5,0.6
4240 Alg. 3 - 0.5,0.6,0.7 Alg. 3 - 0.5,0.6,0.7
Alg. 3 - 0.6,0.7,0.8 Alg. 3 - 0.6,0.7,0.8
Alg. 3 - 0.7,0.8,0.9 Alg. 3 - 0.7,0.8,0.9
52
4220

4200 50

4180
48

4160
46

4140
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
ALPHA ALPHA

Fig. 11. Weighted number of requests accepted in Network 3 Fig. 14. Bandwidth utilized in Network 3

214
used. This is consistent for both Algorithm 2 and Algorithm The algorithms are evaluated for different sets of weights
3. Though, there is a trend showing better performance for and their performance is presented. It is found that when
increasing values of α, it is not uniform. We observed that the weights are dynamically varied according the state of the
this is a random behavior which depends on the network used network and the resources available, the performance is better.
and the service requests given in those cases. Then a simple extension is proposed for finding dedicated
Among the different combination of values for β1 , β2 and protection paths for those working paths which need to be
β3 in Algorithm 3, the combinations 0.5, 0.6, 0.7 and 0.6, protected. But not every working path will require a dedicated
0.7, 0.8 and 0.7, 0.8, 0.9 are found to give better results for protection path. Sharing of protection paths will result in the
the four parameters mentioned above when compared to the optimal usage of network resources.
other two combinations. But the difference among the different The extension of these algorithms for supporting shared
combinations is not very prominent. protection paths will be studied as a future extension. It
From these results, it can be inferred that links and trails should be able to take into account the inherent protection
must be differentiated. Trails must be given higher preference capabilities provided in SDH protection mechanisms like
than links so that already created trails are used as much Multiplex Section Protection (MSP)[18], Multiplex Section
as possible. This is achieved by means of assigning lesser - Shared Protection Ring (MS-SPRing)[18] and Subnetwork
weights to trails when compared to links. If the fraction α is Connection Protection (SNCP)[18].
too less, then it tries to use the existing trails always and this
R EFERENCES
results in consuming more bandwidth and congesting some
of the links. If the fraction α is very large, then new trails [1] W. Fawaz et al., “Service Level Agreement and Provisioning in Optical
Networks,” IEEE Communications Magazine, Jan. 2004, pp. 36-43
are created very frequently and this results in fragmentation [2] A. E. Ozdaglar and D. P. Bertsekas, “Routing and Wavelength Assign-
of bandwidth. The values of 0.6 to 0.9 for α are found to ment in Optical Networks,” IEEE/ACM Trans. Networking, vol. 11, pp.
give the optimal results for all the three networks. For the 259- 272, Apr. 2003.
[3] H. Zang, C. Ou and B. Mukherjee, “Path-Protection Routing and
algorithms to be more reactive to the service requests made and Wavelength Assignment (RWA) in WDM Mesh Networks Under Duct-
the bandwidth available, the weights have to be dynamically Layer Constraints,” IEEE/ACM Trans. Networking, vol. 11, pp. 248-258,
varied. For trails, the criteria used is the necessity for breaking Apr. 2003.
[4] X. Chu, B. Li and Z. Zhang, “A Dynamic RWA Algorithm in a
higher capacity containers in the SDH multiplexing structure. Wavelength-Routed All-Optical Network with Wavelength Converters,”
For links, the criteria used is the number of trails created in the Proc. IEEE INFOCOM, 2003, pp. 1795-1804.
links involved. Dynamically changing weights in this manner [5] M. Alanyali and E. Ayanoglu, “Provisioning Algorithms for WDM
Optical Networks,” IEEE/ACM Trans. Networking, vol. 7, pp. 767-778,
results in better usage of network resources and also more Oct. 1999.
requests are accepted. The values of 0.6 to 0.9 for β1 , β2 and [6] S. Janardhanan et al., “A Routing and Wavelength Assignment (RWA)
β3 are found to give better results when compared to other Technique to Minimize the Number of SONET ADMs in WDM Rings,”
Proc. HICSS, vol. 2, pp. 1-10, Jan. 2006.
values. This is again due to the fact that lesser values result [7] H. Liu et al., “Distributed Route Computation and Provisioning in
in more bandwidth utilization whereas very large values result Shared Mesh Optical Networks,” IEEE Journal on Selected Areas in
in fragmentation of bandwidth. Communications, vol. 22, pp. 1626-1639, Nov. 2004.
[8] S. Das, “Topology Discovery and Path Provisioning in SONET Rings
Since these algorithms are centralized, the issue of scalabil- Using GMPLS,” Proc. WOCN, 2006.
ity is a critical one. The time taken to compute a path in the [9] G. Shen and W. D. Grover, “Performance of Protected Working Capacity
70 nodes, 103 edges network is always less than 1 second on Envelopes based on p-cycles: Fast, Simple, and Scalable Dynamic
Service Provisioning of Survivable Services,” Proc. SPIE, vol. 5626,
a Pentium 4 (3 GHz) PC. Since this network is fairly large pp. 519-533, Nov. 2004.
and time taken is very low, these algorithms can be used in [10] M. Kodialam and T. V. Lakshman, “Dynamic Routing of Bandwidth
provisioning systems. The shortest path computation is done Guaranteed Tunnels with Restoration,” Proc. IEEE INFOCOM, 2000,
pp. 902-911.
using Dijkstra’s shortest path algorithm whose running time is [11] C. Ou et al., “Survivable Virtual Concatenation for Data Over
O((E+V ) log V ) when implemented using binary heap. Since SONET/SDH in Optical Transport Networks,” IEEE/ACM Trans. Net-
it does not increase exponentially with increasing network size, working, vol. 14, pp. 218-231, Feb. 2006.
[12] A. Gersht, S. Kheradpir and A. Shulman, “Dynamic Bandwidth-
these algorithms will be able to compute a shortest path for Allocation and Path-Restoration in SONET Self-Healing Networks,”
much larger networks in acceptable times. IEEE Trans. Reliability, vol. 45, pp. 321-331, Jun. 1996.
[13] H. Katz, G. F. Sawyers and J. L. Ginger, “SDH Management Network:
VI. C ONCLUSION Architecture, Routing and Addressing,” Proc. IEEE GLOBECOM, 1993,
pp. 223-228.
In this paper, new path computation algorithms are pre- [14] N. Ansari et al., “QoS Provision with Path Protection for Next Gener-
sented for service provisioning in SDH networks. These ation SONET,” Proc. IEEE ICC, 2002, pp. 2152-2156.
[15] A. Jukan and H. R. van As, “Service-Specific Resource Allocation in
algorithms differ from the conventional path computation WDM Networks with Quality Constraints,” IEEE Journal on Selected
algorithms in that they take into account the multiplexing Areas in Communications, vol. 18, pp. 2051-2061, Oct. 2000.
structure defined by SDH which imposes restrictions on the [16] ITU-T Recommendation G.707, Network node interface for the syn-
chronous digital hierarchy (SDH), G.707.
allocation of bandwidth and the fact that higher order trails [17] ITU-T Recommendation G.703, Physical/electrical characteristics of
(logical connections) have to be established to support any hierarchical digital interfaces, G.703.
bandwidth requirement. The assignment of weights to links [18] ITU-T Recommendation G.841, Types and characteristics of SDH
network protection architectures, G.841.
and trails to find an optimal path is described.

215