IEICE TRANS. COMMUN., VOL. E83-B, NO. 3 MARCH 2000
672

PAPER

New Self-Healing Scheme that Realizes DifferentiatedBandwidth Requirement on ATM Networks
Taishi YAHARA†, Ryutaro KAWAMURA†, and Satoru OHTA†, Members

SUMMARY
This paper proposes a new self-healing scheme thatdifferentiates the bandwidth requirement for each network service on
ATM networks. First, we show the necessity of our proposed scheme.
In the future network, we must satisfy two demands, rapid restorationfrom failure and differentiated bandwidth requirements. The conventional restoration scheme, called the self-healing scheme, realizes rapid
restoration, but does not support bandwidth differentiation; the new
self-healing scheme proposed herein does. We also show that the proposed scheme reduces the spare resources required for backup. The
scheme can be realized as a simple extension of the conventional selfhealing scheme. Finally, simulations show that the proposed scheme
requires fewer spare resources while offering comparable restoration
time to the conventional approach against any demand pattern.
key words: ATM, restoration, self-healing, differentiated bandwidth requirement

1. Introduction
Future networks must offer extremely high capacity. To thisend, backbone networks based on Asynchronous Transfer
Mode (ATM) networks are being established to provide sufficient network resources. In these networks, transmission
paths tend to be large, so one failure causes enormous data
loss. Furthermore, society will become highly dependent ondata communication. Mission critical network services include electric commerce and tele-medicine. Even one failure
will significantly damage the information society politicallyand economically, so rapid restoration from failure is required.
Self-healing schemes were developed to achieve this goal.
They realize rapid restoration by distributing the control
mechanism among network elements, and many variants havebeen proposed [1]-[18].
Other characteristic of future networks is that each network service will have a different bandwidth requirement according to the network service concept. Some high reliability services should be assured of a Peak Cell Rate (PCR) to
fully satisfy customer demands even if failure occurs. For
these services, sufficient spare resources must be reserved toensure restoration. On the other hand, the bandwidth of low
reliability services can be decreased to a predefined Minimum Cell Rate (MCR) for a short time to decrease cost. In
view of user cost and application, it is possible to define thefollowing service classes according to failure state.
(1) PCR guaranteed regardless of failure state
Manuscript received November 6, 1998.
Manuscript revised July 25, 1999.
† The authors are with NTT Network Innovation Laboratories,
Yokosuka-shi, 239-0847 Japan.

(2) Rate is allowed to fall to MCR only when failure happens(3) Rate is allowed to fall to MCR regardless of failure state
In ATM networks, the same network can carry these services. Given reasonable failure patterns, spare resources canbe reduced by forcing service classes (2) and (3) to MCR as
needed. This realizes cost effective network management withfewer spare resources needed for backup. However, no conventional self-healing scheme provides an adequate framework to achieve these states.
This paper proposes a new self-healing scheme that realizes differentiated bandwidth management. It is based on
the flexible bandwidth control permitted by the Virtual Path
(VP) layer in ATM networks. This paper also shows that thescheme realizes more cost effective network management thanthe conventional restoration scheme.
The remainder of the paper is organized as follows. In
the next section, we describe the conventional self-healing
scheme and its problems in realizing bandwidth differentiation. Section 3 describes how to realize the new self-healing
scheme. Section 4 quantitatively evaluates the proposed
scheme through simulations. Concluding remarks appear in
Sect. 5.
2. Conventional Self-Healing Scheme
2.1

Backup VP Scheme

Existing self-healing schemes are classified as the flooding
type [2], [8]-[12] and the backup VP type [3]-[7]. Flooding
type restoration looks for the backup route by broadcasting
messages after a failure is detected, so this scheme can detecta backup route flexibly regardless of the failure pattern. But,
it takes much restoration time. On the other hand, backup
restoration preassigns backup routes. This approach simplifies the restoration process. Backup restoration also suits ATM
networks (the advantages are described later). We have developed a scheme of this type called the Backup VP scheme
for ATM networks [3]-[5]. It is realized in the VP layer in
ATM networks. The control and flexibility possible with ATM
realizes effective restoration.
In this scheme, Backup VPs are preassigned with zero
bandwidth when established. This is feasible because ATM
networks allow route establishment to be independent of bandwidth setting [19]. The backup VPs accommodated in thatlink and are managed by the node connected to the link shares

YAHARA et al.: NEW SELF-HEALING SCHEME THAT REALIZES DIFFERENCIATED BANDWIDTH
673

the spare resources of a link. If a network failure occurs, theappropriate bandwidth is captured by distributed message
communication between nodes on the backup VP after the
failure is detected by a VP failure detection message, such as
VP-AIS[20]. After appropriate bandwidth is captured in all
links on the backup VP, the failed working VP is switched tothe backup VP.
The Backup VP scheme realizes rapid restoration by preassigning backup routes [3]. It also decreases cost by sharing
spare resources and switching at termination nodes unlike
restoration schemes that utilize dedicated spare resources andswitching at switching nodes [4], [21]-[24]. Furthermore, utilizing the Backup VP scheme allows us to estimate required
spare resources against foreseeable failure patterns (i.e. 1 link/
node failure). This simplifies network resource (bandwidth)
management. The maximum bandwidth required to counterall foreseeable failure patterns is established in all links [4].
2.2Problems of Conventional Self-Healing Scheme andits Solution

3.1

Establishment of Spare Resources

3.1.1

Estimation of Spare Resources

The proposed scheme is based on the Backup VP scheme, so
it is able to estimate the spare resources that fulfill all bandwidth requirements of each VP against all foreseeable failure
patterns [4]. In the same manner, we can estimate the spareresources for the 3 VP service classes. This means that sufficient spare resources are established in all links when H-VPs
capture PCR, and M-VPs and L-VPs capture MCR in all foreseeable failure patterns. Furthermore, the proposed scheme
utilizes the bandwidth of L-VPs to decrease the bandwidth
needed for restoration. These two technique decreases thespare resources required.
Spare resources required in link l (SRl) are given by equation (1). If SRl is below zero, spare resources are not requiredin this link. That is, all failed VPs are restored by the bandwidth released from L-VPs in foreseeable failure patterns.
l

In the conventional Backup VP scheme and other self-healing schemes, all network services are assumed to have thesame bandwidth requirement, so the spare resources are established to cope with the most stringent requirement of allservices carried. Thus conventional schemes require muchspare resources.
This paper extends the Backup VP scheme to solve thisproblem. We define the 3 VP service classes introduced inchapter 1.
- High reliability VP (H-VP): Guaranteed PCR regardless offailure- Middle reliability VP (M-VP): Decrease the bandwidth to
MCR in case of own failure- Low reliability VP (L-VP): Decrease the bandwidth to MCR
in case of own or other failure as necessary.
We extend the conventional self-healing scheme to support and utilize these VP services. The proposed scheme realizes cost-effective networks that require fewer spare resources by following below concepts.
- M-VPs and L-VPs captures MCR under own failure.
- Bandwidth released from L-VPs is utilized for restoration.
3. Proposed Scheme
This section details the proposed scheme. To provide a background to the proposed scheme, we first explain how to establish spare resources and node databases. We then explain
how to extend the Backup VP scheme.

SRl = Max (WRl,m ) – Σ(PCRl,vp – MCRl,vp )vp(1)

WRl,m : Total bandwidth required in link l to restore
all failed VPs when optional link m (≠l ) fails
PCRl,vp : PCR of low reliability VP in link l
MCRl,vp : MCR of low reliability VP in link l
3.1.2

Minimization of Spare Resources

Spare resources required in each link depend on the route ofeach working and Backup VP. To roughly minimize required
spare resources, we utilize the procedure in Fig. 1 to decide
the route of a working VP (VPa) and a backup VP (BVPa). It
presumes that VP a and BVPa are disjoint except termination
nodes.
In Seq3, condition (1) and (2) means that the link has
sufficient bandwidth (captured from L-VPs) such that all
backup VPs in the link can be restored against all foreseeable
failure patterns. If condition (1) and (2) are satisfied, it isuseless to increase spare resources. So, such a link will beselected as a candidate of backup VP first. If there are plural
candidates that satisfies two conditions or there are no candidates that fulfill the two conditions in Seq3, Subseq (in Fig.
1(b)) is executed. In Subseq, the link that increases spare resources least is selected, that means the link satisfies condition (3). When estimating spare resources after including VPa
and link i as elements of BVPa, some links may need morespare resources to guarantee the bandwidth requirements than
before including VPa, while other links may not due to thesharing of spare resources. To reduce total spare resources inwhole network, we prefer the link that does not need morespare resources.
One advantage of the proposed scheme is that it does
not affect the routes of existing working VPs and backup VPs.
To achieve complete optimization, we must change all routes
drastically, but this is not realistic because it would increase

IEICE TRANS. COMMUN., VOL. E83-B, NO. 3 MARCH 2000
674

node complexity and stop services. The proposed scheme does
not require route reestablishment, and so yields an approximately optimal solution.
3.2

Link and VP Information

To realize the proposed scheme in a distributed manner, allor some nodes must manage information about the bandwidth
utilization in the links, and VP characteristics accommodated
in the links. Thus, at least one node connected to each linkmust obtain the information described above. In this paper,
we define such nodes as “Management nodes.” A Management node obtains the Link information described in Table
1, and the VP information containing all data of working VPs
and backup VPs in the link. This information (see Table 2) isutilized by the proposed scheme.
3.3

Capture MCR Bandwidth in Failure State

When failure occurs, the trigger message for capturing bandwidth is sent. Management nodes on the backup VP capture
bandwidth from spare resources upon receiving the trigger
message by referring to Bandwidth in VP information. This
information is established based on the service requirementof the VP. That is, H-VP captures PCR and L-VP and M-VP
capture MCR in failure state (see Table 2).
3.4

Utilization of the Bandwidth Released from L-VPs

A bumping algorithm that releases all the bandwidth of some
VPs and utilizes the released bandwidth for restoration has
been proposed [25]. As an extension of the Bumping algorithm, we realize a restoration scheme that releases the bandwidth of L-VP to MCR and utilizes released bandwidth for
backup. Releasing the bandwidth is executed any time thespare resources are insufficient when failure occurs. Twomechanisms that release the bandwidth are described below.
(1) Release the needed bandwidth exactly.
(2) Force the bandwidth to MCR.
Requests to release bandwidth may come in groups, sincemechanism (1) would force each request to initiate bandwidth
Table 1 Link information.

(a)Table 2 VP information.
Contents

Data

VP classification Working VP / Backup VP
VP Identifier(VPI) Specific value for the VP in a link[3]Bandwidth

Working VP PCR and MCR of the VP (MCR is equal
to PCR in H-VP and M-VP)
Backup VP Bandwidth required when failure happens(H-VP : PCR, M-VP,L-VP : MCR)

VP reliability
value

A working VP in L-VP is set to 1, Other one is set to
an integral number over 1

Reserve
Condition

Null(Initial state) / Reserved*(Reserved
for release the bandwidth) / Executing*Working VP (Now executed bandwidth release) /Finish*(Finish the bandwidth release)
Backup VP

Null(Initial state)/Release(Reserve thebandwidth of L-VPs for restoration )Working VP

Null(Initial state)/VPI of a Backup VP
which reserves this VP and reserved
bandwidth **(Reserve condition ="Reserved")

Backup VP

Null(Initial state)/VPI of reserved Low
reliability VPs(Reserve condition="Release")

Reserve
Infomation(b)
Fig. 1 Procedure to establish virtual path network.

*, ** : these are for L-VPs

YAHARA et al.: NEW SELF-HEALING SCHEME THAT REALIZES DIFFERENCIATED BANDWIDTH675

the backup VP until that message reaches the Destination
node. If there are sufficient spare resources for backup, theManagement node captures spare resources and sends a
Capture_message to the next node. If not, the Management
node captures all spare resources first and selects some LVPs until adequate resources are captured for backup andreserves their bandwidth. The bandwidth is not released inthis phase to eliminate useless bandwidth release (e.g. restoration can not completed after some L-VPs were bumped).
In the Capture_message, The information Rel, which represents whether the bandwidth of L-VP is reserved or not in
all upstream nodes, is included. Rel is initialized to 0 at Start
node and updated when the bandwidth of L-VPs is reserved.
When updating, Rel is set to 1.
When Management nodes (node “A,” “B” and “C” inthis figure) receive a Capture_message, they execute the procedure in Fig. 3. Management nodes select one or more VPs
that have VP reliability value 1(e.g. L-VP(s)) that
ReserveCondition is “Null” or ReserveCondition is “Reserved” but all bandwidth are not reserved at this time.
ReserveInfomation includes information about reserved bandwidth in a L-VP, so it enables us to check whether all upstream links have already been reserved or not. To reserve
appropriate bandwidth, one or more L-VPs are reserved. Finally, if the appropriate bandwidth for restoration is successfully r eserv ed on all links on the backup VP, theCapture_message reaches the Destination node.
If a Management node does not capture or reserve theappropriate bandwidth, it sends a Cancel_message back torelease which increase restoration time [25] and complicate
the restoration algorithm. Restoration time is also importantfactor, so we adopt (2) because it minimizes the increase inrestoration time and simplify the restoration algorithm.
Figure 2 describes the algorithm for releasing the bandwidth of L-VPs and restoring failed VPs by utilizing the bandwidth so released. In Fig. 2, restoration starts using BVPm,
but the link “2” connecting node “B” and node “C” lacks
sufficient spare resources, so L-VPs (VPn) are released to provide enough free bandwidth. The termination node locateddownstream that detects the failure by VP alarm detection(ex. VP-AIS[20]) is defined as the Start node, while that located upstream is the Destination node. Node “A” manages
Link “1,” Node “B” manages Link “2” and Node “C” manages Link “3” about the VP and Link information in eachlink.
Phase 1: Bandwidth Capture Phase
The Start node sends a Capture_message to the next node on(a)Termination nodes
on a L-VP(VPn)

Backup VP (BVPm)
C

B

A

D

E

F

VP-Alarm(VP-AIS[20])Start
restoration- capturespare resources
Capturemessage(Rel =0)

Phase 1- capture spareresources andreserve L-VPs
Capturemessage(Rel =1)- capturespare resources
Capturemessage(Rel =1)
ReleasemessageReleasemessage- Executebandwidth release
Release_VP
messagePhase 2

- Release bandwidthof L-VP to MCR

Release_VP
message ack- Release bandwidthof L-VP to MCR

Release_VP
message ack
Releasemessage- Confirm acks
- Resume sequence- Switch VP

Phase 3

Switchmessage-Switch VP
Finishrestoration(b)
Fig. 2 Restoration sequence utilizing bandwidth releasing mechanism.

IEICE TRANS. COMMUN., VOL. E83-B, NO. 3 MARCH 2000
676

the Start node. Management nodes that receive theCancel_message initialize the updated Link information and
VP information. This procedure assumes unforeseeable failure patterns, such as multiple link/node failure or more.
Phase 2: Bandwidth Release Phase
If it is not necessary to release any L-VPs (e.g. Rel = 0), there
is no need to release the bandwidth, so the Destination nodeswitches the failed working VP to the backup VP and send a
Switch_message to the Start node as in the conventional
Backup VP scheme [4]. Upon receiving the Switch_message,
the Start node switches the failed working VP to the backup
VP that finishes the restoration sequence.
If it is necessary to release bandwidth (e.g. Rel = 1, in
Fig. 2), it sends a Release_message to the Start node via the
backup VP. Upon receiving the Release_message, the Management nodes execute the procedure in Fig. 4.
This procedure is needed to prevent cell overflow fromthe released L-VPs. If we simply release a VP and reassign
its bandwidth in one link, cells will continue to arrive at the
upstream node that may degrade the cell loss quality of otherworking VPs. To realize a safe sequence, we use ack for confirmation.

In this procedure, when one L-VP(VPb) is reserved bymultiple backup VPs, the Management node receiving
Release_message first switches the ReserveCondition of VPb
to “Executing.” When the Management node receives another
Release_message requesting bandwidth release of VPb, it does
not execute the sequence for bandwidth release. This is because the first disposal releases the bandwidth until MCR, so
all reserved bandwidth are released at one time. This method
decreases the total number of message communications torelease bandwidth and simplifies the restoration procedure.
After updating the ReserveCondition of all reserved LVPs to “Finish,” Management node sends Release_message
to the next node.
Phase 3: Switch Phase
Upon receiving Release_message, the Start node switches
the failed working VP to the backup VP using the captured
bandwidth and sends a Switch_message to the Destination
node. The Destination node then switches the failed VP to its
backup VP and restoration finishes.
4. Evaluation of Proposed Scheme
This section quantitatively evaluates the effectiveness of our
proposed scheme in terms of spare resources and restoration
time by simulation. Three schemes are compared, Backup
VP scheme, proposed scheme that establish the route of working and backup VP by the concept of shortest path (proposed1), and proposed scheme that establish routes by thesequence proposed in Sect. 3.1.2 (proposed2). The simulation conditions are described below.

Fig. 3 Procedure for bandwidth capture phase.

if (ReserveCondition of the Backup VP = Release ) then
- Send Release_VP_message to both termination nodesof reserved L-VPs whose condition are
ReserveCondition = "Reserved
ReserveInfo = "VPI of the Backup VP";
- Update VP information of above L-VPs
ReserveCondition = Executing ;- When confirming acks from a L-VP, update VP
information of this L-VP:
ReserveCondition = Finish ;- Send Release_message to the next node after
ReserveCondition of all reserved L-VPs become
Finish ;else- Send Release_message to the next nodeFig. 4 Procedure for bandwidth release phase.

-Network topology:
1. Metropolitan LATA network (15 nodes joined by 28 links(Fig. 5(a)))
2. Japan long haul network (56 nodes joined by 85 links(Fig. 5(b)))-Foreseeable failure: 1 link failure-PCR: all VPs have same PCR.
-VP routing:
Backup VP scheme, Proposed1 (using proposed scheme):
Working VPs occupy the shortest path. Backup VPs occupy the shortest path that is not common (except termination nodes) with working VP.
Proposed2: Working VPs and Backup VPs are establishedbased on the scheme described in Sect. 3.1.2 with theaim of minimizing spare resources.

(a) LATA(b) Japan long haul

Fig. 5 Network topology.

YAHARA et al.: NEW SELF-HEALING SCHEME THAT REALIZES DIFFERENCIATED BANDWIDTH
677

4.2

Evaluation of Restoration Time

When restoration involves the release of bandwidth, it tends
to increase the restoration time [25]. Restoration time is also
an important factor, so the increase must be as small as possible. Figure 10 shows evaluations of restoration time for each
network topology with variable MCR. Settings are the same

1
1

1

0.8
0.6
0.4
0.2

0

0
0

2

4

4

6

M-VP

8

10

8

2

0

0

2

6

4

6

M-VP

L-VP

8

10

8

4

6

2

0
0

L-VP

(b)Proposed2(a) Proposed1

Fig. 8 Evaluation of the spare resources with variable demand pattern in each service class. (Metropolitan LATA network, MCR / PCR =0.5, the total VP number of H-VP is set to 1)

1

Amount of Spare Resources(Relative value)

Figures 6 and 7 show a comparison of total spare resources
required versus MCR/PCR ratio. In Figs. 6 (a) and 7 (a), one
H-VP, M-VP and L-VP are established between all nodes
with the same bandwidth in proposed1 and proposed2. In(b), demand pattern in each node pair differs. The same numbers of 3 class VP (H-VP, M-VP and L-VP) are establishedin proportion to the total number of links in connecting eachnode pair. This demand pattern nearly reflects the real demand pattern. In Backup VP scheme, the same numbers of
VPs are established compared with proposed1 and proposed2.
All VPs must offer PCR. Spare resources are established tosatisfy all bandwidth requirements against any foreseeable
failure pattern, and the spare resources that satisfy this requirement are set to 1. The value in the graph is relative tothe total spare resources of the Backup VP scheme. From
both graphs, spare resources are proportionally decreased
depending on MCR. Furthermore, In Fig. 6 proposed2 requires 20% less spare resources than proposed1. However,proposed2 does not work well in the Japan long haul network. This is because there is no alternative backup VPs inthat network topology, so the results almost the same
Figures 8 and 9 shows evaluations of spare resources
required when the demand pattern in each class varies. The
number of M-VP and L-VP are proportionally variable in all

Amount of Spare Resources(Relative value)

Evaluation of Spare Resources

1

1

0

Amount of Spare Resources(Relative value)

4.1

node pairs one VP in all node pairs carries H-VP. MCR is set
to half of PCR. In both networks, the graph shows that thesame number of H-VP, regardless of M-VP, are required toachieve a 50% decrease in spare resources. Furthermore, quite
a lot less spare resources are needed when there are a lot of
L-VPs. Proposed 2 takes into account the releasing of L-VP,
so it realizes network with lower spare resource requirements.

Amount of Spare Resources(Relative value)-Message processing time: 10ms
-Failure detection delay: transmission delay (hop number fromthe point where failure occurs to termination node)-Alarm detection delay: 10ms (failure generation time is set
to 0)

0.8
0.6
0.4
0.2

0

0
2

4

4

6

M-VP

8

10

8

2

0

0

2

4

4

6

6

L-VP

(a) Proposed1

M-VP

8

10

8

2

6

0
0

L-VP

(b)Proposed2(a) Uniform demand pattern(b) Variable demand patternFig. 6 Evaluation of the spare resources with variable MCR. ( Metropolitan LATA network, H-VP : M-VP : L-VP = 1 : 1 : 1)

Fig. 9 Evaluation of the spare resources with variable demand pattern in each service class. (Japan long haul network, MCR / PCR = 0.5,
the total VP number of H-VP is set to 1)(a) Uniform demand pattern(b) Variable demand patternFig. 7 Evaluation of the spare resources with variable MCR. (Japan
long haul network, H-VP : M-VP : L-VP = 1 : 1 : 1)(a) Metropolitan LATA network(b) Japan long haul network
Fig. 10 Evaluation of the restoration time. (Uniform demand pattern,
H-VP : M-VP : L-VP = 1 : 1 : 1)

IEICE TRANS. COMMUN., VOL. E83-B, NO. 3 MARCH 2000
678

as in Figs 6 (a) and 7 (a) The values are relative to the average restoration time when utilizing the Backup VP scheme
against all foreseeable failure patterns. Average restoration
time using the Backup VP scheme is 429 msec in Fig. 10 (a),and 5,338 msec in Fig. 10(b).
The figures show that proposed schemes require moretime compared to the Backup VP scheme when using bandwidth release for restoration, but the increase is relatively
small. This is because the sequence for bandwidth release is
executed in a distributed manner, so the time spent is dispersed among the nodes involved. This result shows that the
proposed scheme decreases the spare resource requirements
without increasing the restoration time significantly. The restoration time of proposed2 is sometimes less than that of proposed1 even though proposed2 requires fewer spare resources.
This is because message processing does not concentrate at
specific nodes. It is a by-product of the routing scheme
adopted in proposed2.
5. Conclusion
We have proposed a new self-healing scheme that realizes
differentiated bandwidth requirement in each network service on ATM networks. The proposed scheme decreases the
bandwidth assigned to MCR for backing up M-VP and LVPs and utilizes bandwidth released from L-VPs to restore
failed VPs. We have also proposed ways to establish spareresources and node databases.
Simulation results show that the proposed scheme requires fewer resources than conventional restoration schemes
and that it increases the restoration time by a relatively small
degree for foreseeable failure in any demand pattern. These
results show that it is now feasible to construct effective networks that require fewer spare resources without degrading
restoration time significantly. This means that the proposed
scheme realizes networks that fulfill the rapidity and differentiated bandwidth requirement for the restoration requiredin future networks.
References[1] T.-H.Wu, Fiber Network Service Survivability, Artech House,
1992.
[2] W.D.Grover, “The selfhealing network,” Proc. IEEE Globecom,
pp.1090-1095, 1987.
[3] R.Kawamura and I.Tokizawa, “Self-healing virtual path architecture in ATM networks,” IEEE Commun. Mag., vol.33, no.9,
pp.72-79, Sept. 1995.
[4] R.Kawamura, K.Sato, and I.Tokizawa, “Self-healing ATM networks based on virtual path concept,” IEEE J-SAC, vol.12, no.1,
pp.120-127, Jan. 1994.
[5] R.Kawamura and S.Ohta, “SELF-HEALING ATM NETWORKARCHITECTURE; Implementation Results from NTT’s Nationwide Testbed ATM Network,” Proc. Networks, pp.717-722,
1996.
[6] P.Veitch and I.Hawker, “Administration of restorable virtual pathmesh networks,” IEEE Commun. Mag., vol.34, no.12, pp.96101, Dec. 1996.
[7] J.Carlier and D.Nace, “A new distributed restoration algorithm
for telecommunication networks,” Proc. Networks, pp.377-380,

1994.
[8] H.Komine, T.Chujo, T.Ogura, K.Miyazaki, and T.Soejima, “A
distributed restoration algorithm for multiple-link and node failures of transport networks,” Proc. IEEE Globecom, pp.459-463,
1990.
[9] K.Wipusitwarakun, H.Tode, and H.Ikeda, “Fast failure restoration algorithm with reduced messages based on flooding mechanism,” IEICE Trans. Commun., vol.E80-B, no.4, pp.564-572,
April 1997.
[10] H.G.Song, H.Lee, B.Moon, and S.J.Chung, “Dynamic rerouting for ATM virtual path restoration,” IEEE Globecom, 1997.
[11] H.Saito, M.M.Slominski, and M.Yoshida, “An improved guided
restoration algorithm for ATM crossconnect networks,” Proc.
NOMS, pp.225-234, 1996.
[12] E.Ayanoglu, “A fast topology update algorithm for restoration
under multiple failures in broadband networks,” Proc. IEEE ICC,
pp.1295-1299, 1993.
[13] J.Anderson, B.T.Doshi, S.Dravida, and P.Harshavardhana, “Fastrestoration of ATM networks,” IEEE J-SAC, vol.12, no.1,
pp.128-138, Jan. 1994.
[14] M.T.Busche, C.M.Lockhart, and C.Olszewski, “Dynamic Kshortest path (DKSP) facility restoration algorithm,” Proc. IEEE
Globecom, pp.536-542, 1994.
[15] K.Struyve and P.Demeester, “Escalation between recovery
schemes: Beyond ATM backup recovery,” Proc. IEEE Globecom, pp.755-761, 1996.
[16] K.W.Ko and K.W.Cheung, “A local map based (LMB) self-healing scheme for arbitrary topology networks,” IEEE Globecom,
1997.
[17] D.A.Dunn, W.D.Grover, and M.H.MacGregor, “Comparison of
k-shortest paths and maximum flow routing for network facility restoration,” IEEE J-SAC, vol.12, no.1, pp.88-99, Jan. 1994.
[18] P.Veitch and D.Johnson, “ATM network resilience, ” IEEE Network, pp.26-33, Sept./Oct. 1997.
[19] K.Sato and I.Tokizawa, “Flexible asynchronous transfer mode
networks utilizing virtual paths,” Proc. IEEE ICC, pp.831-838,
1990.
[20] ITU-T Recommendation I.610, B-ISDN operation and maintenance principles and functions, 1992.
[21] S.Ohta and K.Nunokawa, “Comparison of alternative service
protection mechanism for wide area ATM networks,” Proc.
Networks, 1996.
[22] D.Johnson, “Survivability strategies for broadband networks,”
IEEE Globecom, pp.452-456, 1996.
[23] M.Herzberg and A.Utano, “Optimal assignment of spare capacity to back-up VPs in survivable ATM networks,” Proc. Networks, pp.665-670, 1996.
[24] K.Murakami and H.S.Kim, “Comparative study on restoration
schemes of survivable ATM networks,” Proc. IEEE INFOCOM,
1997.
[25] T.Yahara and R.Kawamura, “Virtual path self-healing scheme
based on multi-reliability ATM network concept,” Proc. IEEE
Globecom, 1997.

YAHARA et al.: NEW SELF-HEALING SCHEME THAT REALIZES DIFFERENCIATED BANDWIDTH
679

Taishi Yahara received the B.E. and M.E.
degrees in Electric Engineering from Kobe
University, Kobe, Japan, in 1993 and1995,
respcetively. In 1995, he joined NTT Optical
Network Systems Laboratories, where heworked on network reliability techniques. He
is currently involved in research of futureinternet service system at NTT Network Innovation Laboratories. Mr. Yahara is a member of the IEEE Communication Society.

Ryutaro Kawamura
received the B.S.
and M.S. degrees in Precision Engineering and
Ph.D. degree in Electronics and Information
Engineering from Hokkaido University, Japan, in 1987, 1989 and 1996, respectively. In
1989, he joined Nippon Telegraph and Telephone Corporation’s (NTT) Optical Network
Systems Laboratories. He is engaged in research on network reliability techniques, Virtual Path control in ATM networks and highspeed computer networks. From 1998, he havebeen a visiting researcher at the CTR, Columbia University, New York,USA. Dr. Kawamura is a member of the IEEE Communications Society.

Satoru Ohta
received the B.E., M.E. and
Dr. E. degrees in Electronics Engineering from
Tokyo Institute of Technology, Tokyo, Japan,
in 1981, 1983, and 1996. Since 1983 he has
been with NTT, where he worked on researchand development of cross-connect systems,
transmission network synthesis, network management, and broadband ISDN. He is currently involved in research of optimization
techniques for transport networks at NTT
Network Innovation Laboratories. Dr. Ohta isa member of the IEEE. He received the Excellent Paper Award in 1991
from IEICE.