`

`THE MAGAZINE OF GLOBAL INFORMATION EXCHANGE
`SEPTEMBER/ OCTOBER 1996 VOL. 10 NO. 5
`• • • • • • • • • • • • • • • • • • • • • • • • • • • • •
`s
`T u
`E
`E
`R
`F
`A
`Resource Management with Virtual Paths in ATM
`Networks
`The authors present a survey article on resource man(cid:173)
`agemen t using virtual paths in an ATM network. Of
`interest are techniques tha t modify the VPC topology
`and capacity assignments in o rder to adapt to cha nging traffic
`conditions and possible network fa ilures.
`V. J. Friesen, J. J. Harms, and J. W. Wong
`
`10
`•••
`
`22
`•••
`
`28
`• • •
`
`40
`•••
`
`Voice over ATM: An Evaluation of Network
`Architecture Alternatives
`I This article describes eight application scenarios in
`I
`which there is a business case for voice over ATM. It
`then evaluates a lternative network architectures for
`implementing the required network functionality. The art icle
`incorporates much of the o ngoing work of the ATM Forum and
`the ITU , but does not restrict itself to standards a nd implemen(cid:173)
`tatio n agreements. In addition, it evaluates nonstandardized
`alte rnatives for A TM transport of voice traffic.
`David J. Wright
`
`Monitoring and Control of ATM Networks Using
`Special Cells
`The authors describe a framework for monitoring and
`controlling ATM netwo rks based o n the use of man(cid:173)
`agement cells. They explore various existing and new
`uses of management cells for performance monitoring, traffic
`control, fault management, and network adm inistration.
`Thomas M . Chen, Steve S. Liu, David Wang, Vijay K.
`Samalam, Michael J. Procanik, and Dinyar Kavouspour
`
`End-Station Performance under Leaky Bucket Traffic
`Shaping
`In this article, the autho rs study the contributio n of
`the leaky bucket plus cell spacer subsyste m to the
`delay and jitter in an end station. They also study the
`distribution of the size of the bursts of cells leaving the end sta(cid:173)
`tion a nd e ntering the network. Finally, they derive the theoreti(cid:173)
`cal upper bound for the size of bursts of cells.
`Baiju V. Patel and Chatschik C. Bisdikian, IBM Research
`Division
`
`• THIS ISSU E
`
`f ea tu r es d iscussions
`
`o n management and
`
`co ntrol of ATM net(cid:173)
`
`works.
`
`Cover i llus t rati on:
`
`I mage Ban k
`
`Icons explained
`
`[-1 The mortarboard indicates a tutorial
`
`that describes a unique idea or a new
`approach.
`
`~ article. a The light bulb indicates an article
`CJ The meshing gears indicate an article
`Lal that describes an implementation.
`ii The graph indicates an article that
`~ The sigma indicates an article that
`~ contains theory or analysis.
`~ Th, dock ;nd;ca,es a ,;mefy om£/e
`
`contains measurements from a real
`system.
`
`• • • • • • • • • • • • • • • • • • • • • • •
`DEPARTMENTS
`Editor's Note
`
`3
`
`New Books
`
`Dilbert® by Scott Adams
`
`Conference Calendar
`
`4
`
`6
`
`7
`
`2
`
`IEEE Network • September/October 1996
`
`

`

`New Sponsors for
`IEEE Network
`
`David C. Feldmeier
`
`am pleased to announce that in addition to the IEEE Communications
`Society, IEEE Network is now co-sponsored by the IEEE Computer Soci(cid:173)
`ety and the Internet Society. The co-spo nsorship begins in 1997, and shortly
`I will be adding members of the co-sponsoring societies to the editorial
`board of IEEE Network. My thanks to Tom Plevyak, the ComSoc Director of
`Publications, and Steve Weinstein for putting together the co-sponsorship
`agreement. My thanks as well to Ron Williams of the Computer Society, and
`Don Heath of the Internet Society.
`Throughout my tenure as Editor and Chief, I have worked to include more
`articles on data communication, network computing, and the Internet in IEEE
`Network . I have continued the shift in article coverage that started under Craig
`Partridge, the previous Editor in Chie f. I believe that the co-sponsorship of
`IEEE Network will make a good magazine even better. T he new sponsors of
`IEEE Network provide a new source of articles on some of today's hottest topics
`in communication, as well as a new source of readers. I look forward to these
`changes, which will allow IEEE Network to publish mo re articles of higher quali(cid:173)
`ty that are central to the interests of our readers.
`On another note, as some of you may already know, I recently left Bellcore
`to become Director of Strategic Plann ing at MUSIC Semiconducto rs. MUSIC
`sells hardware to accelerate protocol processing to many of the big data net(cid:173)
`working and telecommunication companies, and I'll be specifying new devices to
`expand the prod uct line. For me, the job is a chance to learn new skills and to
`commercialize some of my research. So far, the job has been fun, although
`MUSIC is two o rders of magnitude smaller than Bellcore, and it takes so me
`adjustment. I keep waiting for things to settle down, and I'm starting to realize
`that it's not going to happen. We're hiring new people rapidly, and the organi(cid:173)
`zation chart is mostly theoretical. As with any other small company, I usually
`end up doing a bunch of different things every week. I feel li ke I should have
`four o r five different business cards.
`
`•••••••••••••••••••••••••••••••••••••••••••
`
`IEEE NETWORK ISSN 0890-8044 is published bimonthly by the
`Institut e of Electrical and Electronics Engineers, Inc. Head(cid:173)
`quarters address: IEEE Publishing Seivices, 345 East 47th Street.
`cw York. NY 10017-2394, USA. Tel:+ I 212-705-7018;e-mail:
`iece.network@'iccc.org. Responsibility for the contents rests
`upon au thorS of signed articles and not the IEEE or its members.
`Unle:,5 otherwise spe.cified. the IEEE neither endorses nor sanc(cid:173)
`tion,;; any positions or actions espoused in / £££ Network.
`ANNUAL SUBSCRIPTION : $22 in addition to IEEE Com(cid:173)
`munications Society or any other IEEE Society member
`dues. Non-member prices: SI 15. Single copy price~: Mem(cid:173)
`ber. SIO; Non-member, $20.
`EDITORIAL CORRESPONDENCE: Address to: Dave Feldmeier.
`Editor-in-Chief./£££ Network. IEEE Communications
`Socie ty. 345 East 4 7th Street. ew Yurk. NY I 0017-2394.
`USA; e-mail: d.fcldmcicr@'iccc.org.
`COPYRIGHT AN D REPRINT PERMISSIONS: Abstracting is
`pcrmiucd with credit to lhc source. Libraries arc permitted to
`
`photocopy beyond the limits of U.S. Copyright law for private
`use of patrons: those articles tha t earl)' a code on the bottom of
`the first page provided the per copy fee indic~1ted in the code is
`paid through the Copyright Clearance Center. 222 Rosewood
`Drive, Danvers, MAO I 923, USA. For other copying, rcprin t,or
`republ ication permission, write to D irector, Publishing Services,
`at IEEE Headquarters. All rights reserved. Copyright © 1995
`by 1hc Institute of Electrical and Electronics Engineers, Inc.
`POSTMASTER: Send address changes to IEEE Nerwork.
`IEEE, 445 Hoes Lane, Piscataway. NJ 08855-1331 , USA.
`Printed in USA. Secund·class postage paid a t New Yo rk. NY
`and at additional mailing offices.
`SUBSCRIPTIONS, orders. address changes should be sent
`to IEEE ScrviceCentcr.445 Hoes 1-snc, Piscataway, NJ08855·
`1331, USA. Tel. + 1-908-98 1-0060. GST Reg# 125634188.
`ADVE RTISI N G: Advertising is accepted at the d iscretion of
`the publisher. Address correspondence to IEEE Network.
`345 East 47th Street, New York. NY !0017-2394, USA.
`
`l1 $J$Jzj
`I\EIWI I IC
`
`THE MAGAZINE OF GLOBAL INFORMATION EXCHANGE
`
`Director of Publicatio ns
`Thomas J . Plevyak, Bell Atlantic
`
`Ed itor-in-Chief
`David C. Feldmeier, Bcllcore
`
`Executive Dire ctor
`G. Allan Ledbetter, IEEE Communications Society
`
`IEEE Network Tec hnica l Ed itoria l Bo o rd
`J agan P. Agrawal, University of Missouri, USA
`Salah Aidarous, Bell N orthe rn Rese arch, Canada
`Steven M. Bellovin, AT&T Bell Laboratories, USA
`Ernst Biersack, Institut Eurccom, France
`Lillian M. Cassel, Villanova Univ., USA
`Jon Crowcroft. Un iversity College London, U K
`Steve Deering, Xerox PARC, USA
`Gary De lp, IBM Corporation, USA
`Julio Escobar, Bolt Beranek and Newman, Inc., USA
`David G reaves, University of Cambridge, UK
`Alden Jackson, Sandia National Laboratories, USA
`Anura Jayasumana, Colorado State U niversity, USA
`Frank Magee, AT&T Bell Laboratories, USA
`Allison Mankin, T he M ITRE Corporation, USA
`Gerald Neufeld, U n iv. of British Columbia, Canada
`Guy Omidyar, Computer Sciences Corporation, USA
`Pe ter O' Reilly, GTE Laboratories Inc., USA
`Gerard Parr, University of Ulster, Northern Ireland
`Guru Parulkar, Washington Univ., St. Louis, USA
`Kr,ysztof Pawlikowski, U. of Canterbury, New Zealand
`Thomas F. Piatkowski, Western M ichigan Univ., USA
`Stephen Pink, Swedish Inst. of Comp. Science, Sweden
`KK R amakrishnan, AT&T Bell Laboratories, USA
`Khosrow So hraby, University of Missouri, USA
`Mehmet Toy, AT&T Bell Laboratories, USA
`Gill Waters. University of Essex, U K
`Mart ina Zitterbart, TU Braunsehweig, Germany
`
`Fe a ture Editors
`John D. Spragins, "New Books and Multimedia"
`
`IEEE Produc tion Sta ff
`Joseph Milizzo, Publications Manager
`Catherine Kemelmacher, Production E ditor
`Eric Levine, Advertising Sales M anager
`Joanne O'R our ke, Staff Assistant
`Susa n Lange, Publications Assistant
`
`1996 IEEE C ommun ica tio ns Society Officers
`Stephen B. Weinstein, President
`Nim K. Cheung, VP-Technical Affairs
`Lin-shan Lee, VP-lntemationa/ Affairs
`R oberto B. de Marca, VP-Membership Affairs
`G . Allan Leadbetter, Secretary
`Ross C. Anderson, Treasurer
`Maurizio Decina, Past Presidem
`
`Boord of G ove rnors
`The e lected officers above plus Members-at-Large:
`Class of I 996
`Harvey A. Freeman - Lin-shan Lee
`Joseph L. LoCicero - Richard K. Snelting
`Class of 1997
`Magda EI-Zarki - Thomas J. P levyak
`Federico Tosco - Douglas N. Zuckerman
`Class of 1998
`Mark J. Karol -
`James F. Kurose
`David G. Leeper - Martina Z itterbart
`
`1996 IEEE O ffic e rs
`Wallace S. Rea d, President
`Charles K Alexander, President-Elect
`Tsuneo Nakaraha, Secretary
`Howard L. Wolfman, Treasurer
`J . Thomas Cain, Past Preside/It
`Daniel J. Senese, General Manager
`Celia L. Desmond, Director, Division Ill
`
`TEEE Network • September/October 1996
`
`3
`
`

`

`Resource Management with Virtual Paths in
`ATM Networks
`
`V. J. Friesen, J. J. Harms, and J. W. Wong
`
`Abstract
`In an ATM network, a virtu a l path con nection (VPC) is a labeled path wh ich can
`be used to transport a bundle of virtual channel connections (VCCs) and to man(cid:173)
`age the reso urces used by these connections. Using the virtua l path concept, the
`network is organized as a collecti on o f VPCs which form a VPC, or logical, over(cid:173)
`lay network . If the VPCs are permanent or semi-permanent a nd have reserved
`capacity, establishing new VCCs requires simple connection admission decisions at
`the VPC terminators of existing VPC s. This would enable faster connection estab(cid:173)
`lishment since transit nodes are not involved in the connection setup. The virtual
`path concept a lso allows the possib ility of segregating traffic types according to
`quality of service requ irements. However, the extent to w hich VPC provisioning is
`able to improve network efficiency is dependent on the resource management deci(cid:173)
`sions that determine the VPC topology and capacity allocations. This is a survey
`article on resource management using virtual paths in an ATM network. Of interest
`are techniques which mod ify the VPC topology and capacity assignments in order
`to adapt to chang ing traffic conditions and possible network fai lures . The resource
`management activities employed to facilitate such adaptation can be categorized
`by the timescale on which they operate. On the shortest timescale are strategies for
`dynamically making minor changes to the VPC topology or capacity assignments .
`On a somewhat longer timescale a re strategies for making more widespread modi(cid:173)
`fications to the VPC overlay network. This would be appropriate for traffic changes
`based on time of day and for recovering from network failures. Finally, on an even
`longer timescale, strategies may be employed to design a general VPC overlay net(cid:173)
`work, to be used at startup or after major network upgrades. Solutions to VPC
`resource management for each of these timescales are discussed .
`
`n asynch ronou s transfe r mod e (ATM) networks, mu lt i(cid:173)
`plexing a nd switching arc pe r formed on 53-byte ce ll s
`which are transported across the network o n virtual chan nel
`connect io ns (VCCs) [ I]. A virt ual path connection (YPC)
`/
`is a labe led pa th which can be used to tra nsport, process, and
`manage a b und le of YCCs. Two levels o f cell forwarding are
`d e fin ed: virt ual path (V P) a nd vi rtu a l cha nne l (VC), w h ich
`use the virtua l path identifier (VPI) a nd virtual chan ne l iden(cid:173)
`tifier (YC!) fie lds in the cell header, respectively [2].
`A VPC can be characterized by its two VPC terminators, a
`phys ica l ro ut e b e twee n th ese termin a to rs, a nd a po ssib le
`assigned ca pacity. A YCC, o n th e o the r hand, trave rses a set
`of co n ca te n a ted Y PCs. An exampl e o f this r e la t io ns hip
`be tween the Y PC and YCC is s ho wn in Fig. I. A t the origi(cid:173)
`nati ng YPC term ina to r (nocle A), a cell belonging to a give n
`YCC is ide ntified by a YC I (i.e., YC I 6). This YCI, as we ll as
`the ide ntifier o f the YPC used to carry this YCC (i.e., VPI 4),
`are the n writte n in the heade r of the cell. A t th e othe r end of
`the YPC (node D) , YC I ancl YP I tra nslatio n takes p lace fo r
`tra ns mission o n to th e nex t Y PC. A l t ra nsit nod es, o nly the
`YPI labe l need s to be recog nized, a nd the YC I fi e ld remains
`
`unchanged . T ransit nodes a rc the re fo re freed from perform(cid:173)
`ing YC I translatio n when routing cclls.1
`In ge ne ra l, a YCC is co nstructed from one or more YPCs
`(o r VC links). The numbe r of YPCs trave rsed by a YCC will
`be refe rred to as its VPC hop count. Likewise, a YPC is con(cid:173)
`stru cte d from one or mo re phys ica l lin ks (or VP links). T he
`number o f p hys ical links trave rsed by a YPC (or a YCC) will
`be re ferred to as its physical hop count. In Fig. I, the VCC has
`a V PC hop co unt o f two and a physical hop cou n t o f five,,
`wh ile YPC l an d VPC 2 lrnve phys ical hop co u nts of three
`and two, respectively.
`Using the virtual pat h concept, the ne twork is o rga nized as
`a collection of YPCs which fo rm a Y PC, or logical, overlay
`network (Fig. 2). In this logical network, links correspond to
`VPCs, whi le nodes correspond to YPC term inators. The logi-
`
`1 In fact, a VCC 11eed 1w1 be tra11sponed excfusii·ely withi11 a system of
`VPCs. There may be i11di1·idual VCC rowi11g prior to reaching the first
`VPC, after leal'ing the last VPC. or along the em ire rowe. For the pwposes
`of our disrnssion. we largely ignore these cases.
`
`10
`
`0890-8044/96/$05.00 © 1996 IEEE
`
`IEEE etwork • September/October I 996
`
`

`

`-VPI = 4 VCI = 6 -VPI = 15
`
`VCI = 6 -VPI = 8
`
`VCI = 6
`
`-VPI = 10
`VCI = 3 -VPI = 25
`
`VCI = 3
`
`Q v PC terminator
`
`Orransit node
`
`• Figure 1 . VCI and VP/ translation.
`
`Physical network
`
`A
`
`D rransit node - - Physical link
`O vPc terminator . ........ VPC
`
`• Figure 2. Sample VPC overlay network.
`
`VPC overlay network
`
`0 l ogical node
`
`Logical link
`
`ca l ne two rk can be modified (bo th the co nfigurati o n of the
`logical links and their capacities) according to resou rce provi(cid:173)
`s ion ing decis ions, whereby the network can adapt to changing
`conditio ns. In ge neral, the possible node types in th e physical
`network are:
`• VP transit nodes
`• VPC te rm inato rs
`• Composite nodes
`Composite nodes serve as VPC terminators for some V PCs
`a nd tr a ns it nodes for t he other VPCs. These
`three types arc a lso referred to as VP node, VC
`node, and V P-VC node, respectively [2].
`In t he ne twor k of Fig. 2, nodes A, E, and F
`a re VPC terminators, node C is a transit node,
`and nodes B and D a rc composite nodes. Con-
`s ider nodes A and F. Th ey arc co nn ec ted by a
`number of V PC routes. One of th e rou tes co n-
`s is ts of V PC 2, whic h takes the path A-8-C-F.
`This rou te is calle d a direct roure, s ince it has a
`VPC ho p count of one. In relatio n to nodes A
`and F, this is referred to as a direct VPC. Anoth-
`e r possible route betwee n nodes A and F can be
`constructed by co ncatenating VPC 1 (A- 8 ) with
`VPC 3 ( B-C -F). This is an indirect route which
`has a VPC hop count of two . Note that both of
`these rou tes have a physical hop count of three.
`The VPC hop count is therefore not a clea r indi(cid:173)
`cator of the physical hop count.
`We not e that several VPCs may traverse a given lin k, a nd
`severa l VCCs may be ro ut ed over each o f these V PCs, as
`illustrated in Fig. 3. Given th ese re lationsh ips, t he p rovisio n(cid:173)
`ing o f resou rces in a VP-based netwo rk ca n b e viewed on
`three separate tim escales, co rrespondi ng to the phys ical net(cid:173)
`work (lo ng- te rm), th e VPC ove rl ay netwo rk (medium-term),
`a nd t he indi vidual VCCs (s hort- te rm) [3]. W it h res pect to
`reso urce ma nagement act ivities, VCCs are provisio ned on a
`call-by-call basis by the control pla ne, which makes bot h con(cid:173)
`nection adm ission control (CAC) a nd route selection decisions
`[4]. On the timescale of V PC provisio ni ng, resource manage(cid:173)
`men t activities a rc more likely to be hand led by the manage(cid:173)
`me n t p lane and include VPC topology an d VPC capacity
`a/location decisions.
`V PCs, as d e fi ned in th e sta nd a rds [5], play a role in bo th
`traffic con tro l and network resource ma nagement. Some of
`the advantages wh ich ca n be realized th rough the use of the
`virtual path concept arc [5-7]:
`• Simplified connection admission (i nvolving only VPC termi(cid:173)
`nators)
`• Simpl ified routing at transi t nodes (i.e .. based on VP l only)
`• Adaptability to varying traffic and network failures through
`dyna mic resource management
`• Th e ab ility to implement p r io rity control by segrega ting
`traffic with different quality of service (QoS).2
`Wh ile the benefit offe red by th ese
`adva ntages. and therefore th e roles
`appropriate fo r VPCs, depend o n how
`control costs and transm iss ion cost
`are defined (see, e.g., [11, 12)), the
`most common view is that the primary
`
`role o f V PCs is to enha nce operating efficiency by the means
`stated above.
`T his is a survey a rticle on virtual path management in ATM
`ne two rks. T he key manageme nt tasks invo lve V PC topology
`and VPC capacity a llocation. These a re discu sed in the fol(cid:173)
`lowing section. Our survey is o rganized around four VP man(cid:173)
`agement activi ti es. In the th ird section. success ive VPC
`capacity reallocation is discussed. Successive reallocatio n is
`conce rned with changes in ca pacit ies alloca ted to specific
`VPCs. The next activity, discussed.in the fourth ection. i suc(cid:173)
`cessive topology reconfiguration. This involves a sl ight modifi(cid:173)
`cation to the VPC overlay network (e.g. , the addi tion of a new
`VPC to facilitate resource ma nagement). The fifth sect ion is
`co nce rn e d with scenarios where sign ificant changes to t he
`VPC topology, and co rresponding capacity a llocat io ns, a rc
`per formed. This may occur, fo r instance, in response to p re(cid:173)
`dicted changes in demand (e.g., time of day). In the sixth sec(cid:173)
`ti on, long-term VPC topology p la nnin g is di sc ussed.
`Long-term planning is a pplicable to VPC topological design at
`startup or afte r a physical network upgrade. F ina lly, th e last
`secti on provides some concluding remarks.
`
`The VPC Topology and Capacity Allocation
`Problems
`
`VPC
`
`VPC
`
`VPC
`
`Physical link
`
`-n,ie extent to which V PC provisioning
`/ is able to improve network efficiency
`is hig h ly depe nd e n t on its ability to
`provid e VCCs wi t h low se t up an d
`switch ing costs, while maintaining a low
`call blocking probability. This, in turn,
`is dependent on the VPC topology a nd
`capac ity allocations res ult in g from
`resource management decisions.
`In ge neral, the switching cost of a
`VCC increases with the physical ho p
`co u nt a nd the number of VPCs tra-
`
`VCCs
`
`1 We note that vinual 11etworks /8-10/ have
`also been proposed as a means of segregating
`traffic by sen•ice type. Using this concept, ro11t(cid:173)
`i11g ma11ageme111 could still be ha11dled by
`VPCs, while ba11dwidth manage111e111 may be
`ha11dled by a differem mecha11is111.
`
`• Fig ure 3. VCCs; VPCs, and the physical
`link.
`
`IEEE Network • September/October 1996
`
`11
`
`

`

`versed. As for the setup cost, a number of
`scenarios ma y arise when a VCC se tup
`re quest is made. If a VPC route is avail(cid:173)
`able with sufficient capacity to accept the
`new YCC, setup cost is re latively low,
`since decisions are made exclusively with(cid:173)
`in the control plane (i.e., by the CAC and
`routing algorithm). If a VPC route exists,
`but does not have adequate capacity to
`accom modate the new VCC, then the only
`way to avoid call blocking is to a llocate
`a dditional capacity to some set of YPCs.
`Fina lly, if no YPC ro ute is found from
`source to destination, then the o nly way
`to avoid call blocking is by setting up a
`new YPC or se t of VPCs. Th e las t two
`scena rios incur higher cost becau se the
`control plane algorithms cannot establish
`the connection on their own. It is also not
`guaranteed that the desired change to the
`VPC topology or capacity allocations can
`be made.
`A well-designed YPC overlay ne twork
`tries to maximize the probability of being
`able to acco mmodate new VCCs within
`the control plane, that is, without accom(cid:173)
`panying changes to the VPC topology or
`ca pacity assignme nts. Direct YPCs or
`routes wi th low YPC hop counts may be
`preferred.
`The VPC Topology Problem
`The cho ice o f VPC topology, o r layout,
`greatly impacts the connection setup and
`switching costs, as well as the network's resilie nce to unex(cid:173)
`pecte d traffic conditions a nd compone nt failures. T he latter
`implies the need for disjoint paths between source-destination
`pairs, and the ability to change topology when required.3
`T he VPC topology problem is affected by the configuration
`of the physical network; some example co nfigurations a re
`shown in Fig. 4. In Fig. 4a, transit nodes and VPC terminators
`a re always co llocated [1 5]. Figure 4b shows an a lternate
`approach, whe re transit nodes make up a backbone network,
`while YPC terminators are found only at the access points [7].
`A more generic form of this approach is to collocate VPC ter(cid:173)
`minators a t some of the t rans it nodes, whil e o ther tra nsit
`no des a re geogra phica lly distant from a ny termin ators, as
`shown in F ig. 4c [1 6]. The most general configuration is one
`in which any node in the network can serve as either a transit
`node or a YPC terminator [ I 7-20]. In this case, part of the
`VPC topology proble m is determining where VPCs will termi(cid:173)
`nate.
`T he YPC topology problem is a lso affected by va rious con(cid:173)
`strai nts. Some const rai nts, such as the maximum num ber of
`available YPi s, are rigidly defined. O ther constraints, such as
`a lower bound on the number of paths connecting a source(cid:173)
`destination pair [ 17], refl ect the objectives of the designer. lf
`there is a segregat io n of traffic in which each VPC carries
`
`(c)
`O Transit node
`O VPC terminator
`
`• Figure 4. Example physical network
`configurations.
`
`traffic of a specific class of service (CoS),
`o ne must essenti a lly design an overlay
`network (called a ClassRoute network in
`[4]) for each CoS. In general, segregation
`into CoSs ca n be based on a numbe r of
`attributes, such as transfer capability (as
`defined in [5]), QoS requirements, and/or
`ATM traffic pa ramete rs ( e.g., peak cell
`rate). Th e QoS is a specification of the
`e nd -to-end quality, or performance, the
`ne twork is expected to provide for a given
`YCC. The Q oS me trics of inte rest to the
`connection may include cell loss ra te,
`delay, and delay variation.
`
`The VPC Capacity Allocation
`Problem
`
`The te rms capacity allocation and band(cid:173)
`width allocation a r e often u sed inte r (cid:173)
`c hangeably, and can be a pplie d to two
`levels of resource allocation [21]:
`•
`At the individual VPC level, capac-
`ity allocation refers to the CAC a lgo(cid:173)
`rithm's task of determining how much
`capacity a give n YCC will require in
`ord e r t o meet its d esired QoS whil e
`maintai ning the QoS offered to other
`YCCs. Research into this problem has
`focused on calculating the effective
`bandwidth or equivalent capacity of a
`YCC [22-25]. We refer to this level as
`VCC capacity allocation .
`• At the network level, capacity allocation refers to the VPC
`management task of determining how network capacity is
`to be shared between VPCs. We refer to this level as VPC
`capacity allocation.
`Much research has been a imed at determining the capacity
`needed to support a specific mix of multiplexed YCCs [26-28].
`This type of calcula tion is clea rly needed by the CAC a lgo(cid:173)
`rithm in orde r to determine whether or not a given YCC can
`be accepted. It is also useful when dimensioning VPCs, if the
`approxima te traffic mix is known . Although this a rticle is
`mainly concerned with YPC topology and capacity allocation,
`o ne must keep in mind that these two proble ms are closely
`related to effective bandwidth, CAC, and routing.
`At the VP level, several fac tors have an influe nce o n the
`way in which capacity is a llocated, which in turn affects how
`much capacity is required by a given VCC or YPC. These fac(cid:173)
`tors are closely inte rre lated and include the following:
`
`De terministic vs. Statistic al Multiplexing - When deterministic
`multiplexing is used, each VPC is assigned its peak rate, which
`it is never a llowed to exceed, so tha t the sum of the assigned
`VPC capacit ies is never greater than the tota l link capacity.
`With statistical multiplexing, individual VP Cs are allowed to
`occasionally exceed their peak rates, as long as they conform
`to some statistically defined parameters.
`
`3 Th e idea of simplifying routing on a physical network by using predefined
`paths is not new to A TM. This has been studied in the context of building
`logical packet-switched networks on top of backbone networks { 13, 14].
`By setting digital cross-connects, logical paths (similar to virtual paths)
`can be created between sources and destinations. The problems of finding
`routes and bandwidth requirements for these logical paths are similar to
`the topology and capacity allocation problems of VPCs.
`
`Traffic Segregation Stra tegy - A traffic segregation stra tegy
`de term ines w hi c h typ es o f YCCs (or CoSs) a re gro upe d
`together for service on the same VPC. In general, segregation
`affects the traffic mix on a given VPC, which a ffects the multi(cid:173)
`plexing gain [29-31]. Segregation also affects efficie ncy, since
`all YCCs sharing a common YPC must receive the same QoS,
`determined by the most demanding YCC [5].
`
`12
`
`IEEE Network • September/October 1996
`
`

`

`constraints on
`algorithm
`
`complexity, since
`solutions need not
`be foun d quickly.
`
`In some net(cid:173)
`Resource ReseNofion Scheme -
`works, resources (e.g., ba nd width a nd
`buffers) can be partitio ned and dedicated to
`specific VPCs (i.e., reserved). For instance,
`in [30, 32- 34], each link has a d edica ted
`buffer for each VPC, and a cyclic queue ser(cid:173)
`vice d iscipline allows each VPC to be allo(cid:173)
`cated its own service ra te. If no partitioning
`mechanism is availa ble, the n no resources
`can be e xplicitly rese rved , and comple te
`buffe r sharing and firs t-in first-out (FIFO)
`scheduling are employed. Which resource
`reservation sche me is available has an impact
`on the effectiveness of traffic segregation.
`Seve ral o ptions are available for imple(cid:173)
`me nting VPC multiplexing and r esource
`reservation. One extreme is to use statistical
`multiplexing a nd comple te sh aring a t each
`link in the network, mixing all traffic types.
`This method should provide the best multi -
`plexing gain [27]. It also has the advantage that cha nges to
`YPC capacity assignments do not require modifications to
`buffer allocation and scheduling at the tra nsit nodes [7, 35,
`36]. H owever, Q oS guarantees may be difficult to provide,
`and the CAC algorithm may be co mplex because he te roge(cid:173)
`neous traffic sources are multiplexed together at the cell level
`[37]. The other extreme is to impleme nt de terministic multi(cid:173)
`plexing and resource reservation a t each link in the network
`with each YPC carrying only one CoS. This would simplify
`CAC and the provision of QoS guarantees, but efficiency may
`suffer due to peak rate allocation and resource reservation.
`Categorization of Resource Management Problems
`In this section, we provide a categorization of the YPC topol(cid:173)
`ogy and capacity allocation problems re ported in the litera(cid:173)
`ture. On the shortest timescale are strategies for dynamically
`making increme ntal changes to the top ology a nd capacity
`assignments. We refer to these as successive m odifications (as
`is done in [38]). Successive modifications a re seen as adapting
`to small va riations in ne twork traffi c a nd possibly also to
`minor failures. To ensure responsiveness it has been suggested
`that the algorithms used should obtain results quickly, even at
`the expense of optimality [39], and that the cha nges should be
`minor in order to speed up the impleme nta tion phase. Fur(cid:173)
`thermore, if modification decisions a re made in a distributed
`manne r, with local information and local objectives, changes
`can be made more quickly.
`On a somewhat longer timescale are strategies for ma king
`n etwork-wide ch anges to the topology a nd capaci ty assign(cid:173)
`ments. These strategies, referred to as global modifications,
`are seen as reacting to large fluctuations in network traffic
`(e.g., changes in forecasting in format ion and/or component
`failures). It is assumed tha t they occur much less frequently
`than successive modifications. Proble ms fo rmulated in terms
`of global modificatio ns typically a tte mpt to optimize some
`network-wide cont rol objective, thus involving a more com(cid:173)
`plex, time-consuming algorithm. Changes to the VPC overlay
`ne twork are also much more widespread, thus increasing the
`time required to imple ment the cha nges. Due to the longer
`timescale a nd a mount of informa tion req ui red for a global
`modification, centralized control is considered a mo re attrac(cid:173)
`tive option than distributed control.
`Fina lly, long-term planning strategies may be employed to
`design the VPC overlay ne twork on a long-term basis. T hese
`strategies are likely based on knowledge of the physical net(cid:173)
`work a nd possibly estimates of traffic patte rns. The nature of
`long-term planning imposes few constraints on algorithm com-
`
`The nature of
`
`long-term planning
`imposes few
`
`p le xity, since solut ions need not be fo und
`quickly.
`Given this broad classification of strate(cid:173)
`gies, we identify four distinct VPC manage(cid:173)
`me nt ac ti vit ies t ha t are disc ussed in the
`literature:
`• Successive capacity r eallocatio n redis(cid:173)
`tributes capacity on a fixed YPC topology.
`• Successive topology reconfiguration estab(cid:173)
`lishes and/or tears down VPCs with in an
`existing YPC topology.
`• Global reconfiguration consists of both
`global capacity reallocation and global wpol(cid:173)
`ogy reconfiguration. This activity pote ntially
`affects all VPCs in the network.
`• Long-term planning derives a static ( or
`general) set of YPCs and ini t ial or mini(cid:173)
`mum capacity assign ments for them.
`In the next sections, we discuss each of
`these activi ties in t urn. T he discuss ion is
`organized around three aspects of VP resou rce management:
`triggering mechanism, design algorithm, and implementation.
`A triggering mechanism is concerned wit h conditions under
`which ch anges a re to be made to the VPC to pology a nd/or
`capacity allocations. The design algorithm addresses the ques(cid:173)
`tion of what changes should be made. Finally, implementation
`is concerned with how the changes should be put into place.
`•
`Successive Capacity Reallocation
`Triggering Mechanism
`Successive capacity reallocation can be triggered:
`• On dema nd
`• When some threshold of spare capacity has been reached
`• When pe rformance monitoring indicates a need for reallo(cid:173)
`cation
`• Whe n failures require transfer of capacity
`Whe n t hresho ld s or monitoring infor matio