Hose Bandwidth Allocation Method to Achieve a Minimum Throughput Assurance Service for Provider Provisioned VPNs

全文

(1)IPSJJournalSV'ol. 49 No,12 3967-3984(Dec. 2008) RegzLlar PopeT Hose Bandwidth Allocation Method to Achieve a Minimum Throughput for Provider Provisioned VPNs. Assurance. Service. MAsAyosm SHIMAMuRA,tl,*1 KATsuyosHl IIDA,t2 HIRoyuKI KoGA.t3 YouKI KADoBAyAsHIil and SuGuRu YAMAGucHiii We propose a hose bandwidth a}lecationmethod to achieve a minimum throllghputassurance (MTLA) servicefbr the hose model. Although the hose model, which has been proposed as a novel VPN servicernodelforproviderprovisionedvirtualprivat,enetworks (PPVPNs), has been proven t]obe effective fornetwork resourceeMciency and configurationcomplexity,therg has been no considerationof a rnechanism to assure qua}ityof service(QoS) in the hese model. The basic idea of our metihod is to gather availab}ebandwidth information from insidea network and use itto dividethe availab}ebandwidth into hose$ on each bottleneck link. We evaluate and clarifyour method through computer simulation runs. The simulationresultssbow that our metl}od can achieve an MTA servicein the bose model.. 1.. Introduction. Previderprovisioi}ed virtualprivatei}etworks(PPVPNs) are widely used by many enterprise organizations as privateinformatieni}etworks comiectingdistant sitesbecause a,providerhai}dlesthe VPN coi}figuratioi} and management for subscribers.Since VPN subscriberssha,ret}}ebai}dwidt}} representingliinited i}etworkresourcesan}eng allsubscribers, mecha,nismsforassuringthe qualityof service(QeS),especially tl}eminimuri}throughput,arestronglydesiredbecause TCP isnecessaryin the enterpriseapplica,tions and itcreatesburstyand elastic traMc. il. Graduate. t2. Global. i3. Department. *1. Pre$ently. 3967. Schoe} Scientific of with. of Intbrmation. Science,. Infbrmation Information Network. and and. Design. Nara. Computing Media Research. Institute Center,. Sciences, Center,. of Science Tokyo. University I〈yushu. a"d. Institute of. Technology of 'fechno}ogy. Kitakyushu. Institute. ot` Technology. For assuringtheini"ii}'}uii'} throug}}piit to subscribers, a providercoiivei}tioHally uses t}}ec・?Lstemeir-pipe modeZ in terms of bandwidth contract.In thismodel, a subscribercontractswith the providerfor a one-to-eneconnection,calledthe cllstomerpipe,te other sitesin t}}eVPN. Therefore,the previdier must assiire the ininin}uin throughput intonun}erousconRections, such as n(n ---1)/2,ifthe VPN has a fullmesh topology,where n isthe number of sitesin the VPN. To selvethisproblem,a hose modeli)has been proposedas a novelVPN service model in PPVPNs. The main target of the hose model is a customer haviilg multiple sites,and the model has been proposed and proven to be effectivefor network resource eMciei}cy and configuration complexit・yi)'2). Instead of using pipes between source ar}d destination sites,this model uses l'ioses, which are bui}dlesof pipes. By using heses, the hose model can reduce the number of connections t,onti. An illustratioi} about the customer-pipe a"d hose models is shown in Fig. 1. k} both models, there are two VPN subscribersA a,ndB, where each representsa cempany with three siteswhich required to be intercoimectedby a VPN. In the custoi'ller-・pipe model, t}}epi'ovidermust mai}age two customer pipes to sit,es A2 and A3 for siteAl and another two pipes to sitesB2 and B3 for siteB1, whereas in the hose m .odelonly one hose needs to be allocatedand manage(l for each siteAl and Bl. Here, the hose represei}ts the aggregation of allcllstomerpipes connected to the site. This aggregation eases tl}econfiguration con}plexityof large-sca,le VPNs. Furthermore, the network utilizationii}creases because network resources a,reshared admeng sites ef the same subscriber. In this way, the hose model '. provides high efflciencyin VPN services. In order to clearly describe the differencein how t,oalloca,t,e the bandwidth between the customer-pipe and hose mo(lels,in Table 1, we show a,simple exa,mple of the allocated ba,ndwidth based on Fig. 1. In thisexample, sitesA2, A3, B2, and B3 contract for the niinimum agreed throughput of 30, 30, 20, and srlThe deimitionof the ho$e model i$a bandwidth contractmodel in which a VPN provider offersthe throughput assurance for subscribershaving multipledestinationsit・es. In the mode}, the hose is definedas the aggregationot'customer pipes between source slteand other sitesin the subscriber.The providera}locatesthe bandwidth to t}}ehose,i.e., traffic toward alldestinationsltesin the subscriber.. @ 20(8 h)formation ProcessingSocietyof Japan.

(2) 3968. Hose. Bandwidth. Allecation. Method. to Achieve. a MTA. Service. for PPVPNs. ; Although the hose model has been preven te be effk)ctive fornetwork resource k--.-"rrVPN--p.f.o.ylTd.rg.r.ei.n.--e.dtw.-.e-{!.s rw .-..I.--l. u-.t-t ttt-t-ut. ・-P--perA."L2.-JJ. pt〈li'tic2!aj "L-'''〈iAl'r'o. Pipe A3. Edge router .sP.."lpa--B.--2.v. Ectge router r..,,.s(B. ii) --------(IB5)〉. B Pipe B3. Y. s.J..-. Customer-pipe. model. l lT i "-.),,et Y."R.N..-pre---yi.-q.vQ.mr.s."nlHn...e.rtweri〈.-..--.. ptrr.---]J-.tt l"""'-x .....L--". tttttttt; t......t.. '----- )-(LA2)1. ...rT-"..d"iP.".i.R{M.A-Z----"-----""" -]rr--Kt' 5〉. Pipa A3. Edge router. Edgff. Nsh-"f. router. .....". ".?..'ipe"B.-2"-"-.". f.t--x. ------pt〈B:l) '""(3i. Pipe B3 Hose model Fig.1. Table. 1. Illustration. Example. of customer-pipe. Site Bandwidth(Mb/$〉 Hose Subscriber Site. hose. The. A2. A3. 3e. 3e. B2 2e. models.. and ho$e models.. B3 2e. model B B2. 60. model. bandwidtFh. B3 40. On. the other ha.nd, subscribers A. agree(i throughput. contracted. .). '. A. 20, respectively, ii}the customer-pipe an(l B contract fer the minimum. model. A2lA3. Bandwidth(Mb/s). among. and. of ba・ndwidth allocation in customer-pipe Cu$tomer-pipe. in the l}ose model.. --------------・. of 60 and 40, respectively,. in the hose model. all the active sites belongii}g to the same. subscriber.. ca,n be shared For example,. if. site A3 becomes idle, its exeess bandwidth is redistributed to tl}e other sites A2, B2, a,nd B3 in tl}e customer-pipe ii}odel,while the excess bandwidth can be rea}located oRly to site A2 in the hose model.. IPSJJoumal. VoL. 49. No. 12. 3967-3984(Dec. 2eos.). el{ficiency, no mechanism forassuringthe minimum throughputinthe hose medel has been proposed becausethe n}ethodof allocating t}}ebaltdwidthof hosesto achieveQoS assurai}ce isnot clea,r. For QoS assuranceinthe hose model,we conrisiderthe fellewillg ininimum throughput assurance(A,Irll]A) service.A subscriber can obta,inn}uch rnoi'ethroughput tl}aii the "}iniinuin agreed throughputillits hose durii}ga periodwith no coi}gestion. During a periodef congestion,at least the n'}inii'num agreed throughput isprovidedas an averagein a certa,in period. Therefore,a,nptITA servicecan providegreaterthi'oughputpi'e(lictability tha,r} the best-effort VPN service. Ib achievean At{TA servicein the hose model, we nee(ltwo mechanisn}s.The first isa provisioniiig algoritlm'} thatdeterminesai}adequateamoui}tof alloca,ted bandwidth that n'}eets the ininin'}uin throug}}putreq{iireniei}ts forea,chhose. A provisioning algorithmforthe custon'}er-pipe model has b.een proposed3),and the basicideaof tl}is a}gorithmcan be appliedto the hose model with slightmodifications.In thispaper,we assume tl}atnetwork provisiening ferthe hose model has alreadybeen coii}pleted. The secend isan adaptivebandwidth a,lloca,tior} mechaHism that allocatesthe bandwidt}}to hosesaccoinmodatingthe available ban(lwidtl} ef a bottlei}eck lii}k in a network. IH thispaper, to acl}ieve an M"I7A servicein tl}ehose medel, we propese a servicemodel forthe hose model ai}da hose bandwi(lthallocation method as an implementatienof the servicemodel. Ollrbasicideaforthe servicemodel isthat the ayailable balldwidthii}each bottlenecklinki$distributed to hoses based oi} a ra,tio determinedby the previsioning algorithm.rll]b implen'}ent the hose inodel with an MTA service, we propose a hose ba,ndwidtha,llocatioR mechaRism that allocates the bandwidth at the subscriberaRd customer }evels. The difficulty of hose bandwidth allocatioi} isthatthe iilgress edge routersmust obtainoverallillformationabeut the available bandwidth insidethe networkand then allocate the bai)dwidthat two leve}sin a hierarchical ma,iiner. To obta,in such informatioi} at ingressrouters,eur methed usesa feedback-driven trafflc centrolmechanism. For our inet}}odbased oi}tl}eservicemodel, two requiremei}ts shouldbe coi}sidered: (1) fairnessand (2) high utiiization. @ 2008 InibrmationProces$ing Societyoi'Jap&n.

(3) 3969. Hose. Bandwidth. Allocation. Method. te Ach}eve. a MTA. Service. {'or PPVPNs. The fairnessrequirementisdivide(lintotwo levels, hose ai}dpipe,to prevent bandwidth starvatioi} in a ptpe4).Our method meets the requirementsby proportionalfairbandwidt}}allocationin two levelsbased on cellectedfeedback informatioRand traffic monitoringat iltgress routers. The restof the paper isorgai}ized as follows.Section2 reviewsrelatedwork and describesthe shortcomingsof an MTA servicein the hose model. Section3 describeseur hose bandwidth allocation methed and Sectien4 presentscornputer siinulatiolts thatdeinonstratetha. t our rnethodineetsthetl}ree requireinei}ts. Section5 concludesby briefiysllrr}ina. rizingthe inainpointsa.nd ll'}ei}tioniiig fiiture woi'k. 2.. Later,a provisionii}g algoritlm} foi' the hosemodel was proposed2).Thisalgoai}d. fectiveness Other A. a treestructiire. attempts of. using. a. research. preposed. fail.. to. It. optimize tree. backup. topology. the. total. structure. focused. restoration also. enable. Next,. minimizes. in oi}. faiilt. algorithm the. network. the. hose. network. we. fair. VPN This. sites study. of. proved. tl}e. in. select. tree-structure〈1. backup. resottrces. paths in. the. whei'i network. l}ose. inodel. primary topology. first. to. 3967-3984(Dec. 2e08). hose. hose. of. network. n. odel. to. Bandwidth. research. a,rea. of. be. the. hose. spa,re. the. do. not. studies. did. model.. allecation elllxa,nce. Tirodel,. of. Al-. they. Mechanisms. studies. hose. rea,llocation. proposed.. because. the. bai}(lwidth. two. been eMciency,. achieved for. the. first. in. have. resour¢e. Allocation. The. allocation dyi}arnic. model. mecha,nisins. studies.. quettiiig. achieve. that. set. flows. Sii}ce. while. mecl}ai}isn'}. the. the. bandwidth. queuing. third in. the. and med}o〈l. achieves. the. high. cus£omer-pipe. of. method. then. scriber,. a. different. amoRg. 5).. router,. if. the. they. have. authors. assume to. are. same. it. is. be. a. classified:. group.. not. lletwork. integrates of. 2-D. clear. requires. DRR. how a. for. different a. VPN. methods limit. s}}ertcoming. it. can. bandwidth. iHforma,tioR,. the. acl}ieve. degree (lyiiamic. outer level. in. and. a. their. to to. congestion reallocation. high. a. a. a, sul〉. levels que{ies,. logical. WFQ. bandwidth. allo-. evaluations.. ban{lwidtl}. traMc. of. Two outgoing. However,. fair. respect. leve}. of. reservation. proposed9),'e).. inciuded. incoming. with. and. and. sites. model. incoming. the. protocol. ainong. hose. beeR. inner. iiot. with. the. the in. the. was. dynamically. abeut. in. VPNs in. subscribers queuing. used. reservatioi}. resources. has. are. a. reserved. (RSVP-TE)8) (WFQ) te. informatioll. the. (2-D. prepese(l. considere〈l. sllperswitch. with. actual. n'iechanism. of. significant. congestion-related. usage. hoses. above caRnot. The. that. fair. service. different. was. levels.. ii} ai}. n'}echai}isin. enforee. que{iing. a WFQ. the. The be. robin. It. roiiter.. engineering. fair. cation. a. can. is conceptual,. DR.R. mallagement. traffic. providing. 2-D. flows.. fiow. superswitch. each. To. resource. weighted. routers. in. ii}troduce method.. protocol. t}}e. a,i}d links. assoeiated. and. 7).. their through. are. rouild. (DRR). pipes. and pass. group. Achievii}g. queuing. netwerk.. into. robin. for. that. deficit. round. nodes. destinatioi}. priHciple. two-dimeRsional. deficit. bandwidth. flows. same. implemented.. We. of. All. the. the. intermediate. bai}dwidth. allocatioi}. of. all. the. the. on. allecation. of. toward. is. ba.sed. inedel.. divides. be. method. is. fair. the. s?mperswitch. out. No. 12. t}}e. which. eg. by. on. previous. ai'}d. to. pa,ths. the. the. terms. model.. Even the. Work. bar}dwidtl}. service. subscribers. in. in. allocatien. explain. utilizatiei}. inodel.. pa,ths.. IPSJ Journal VoL 49. the. resources.. tolerance can. total. ceimected. service. three. for. effective. bandwidth. Related. review for. be. MTA. provide 2.2. algorithn}s. ca,n. an. not. DRR)6),. As explainedin the Introductioii, no inechanisu}forachievingAx'ITAserviceii} the hese medel has been proposedalthoughthe hose model iseffective fornetwork resourceeMcieitcyand coltfiguration complexity.In thissection, we reviewthree relat,ed studieson the l}osemodel ii}SectioH2.1 ai}dintroducethree related stdudies aRd tl}eir shortcomii}gs in terms of ArlTA servicesin the hose mo(lelin Sectiol} 2.2. 2.1 Related Work on Hose Model First,we describet}}eresearchareaofthe hese model. The rnodelwas proposed by Du{l}eld, et al.i)to improve the efliciency of network resourceutilization. It was defu}edas a 1)andwidthcontractmo(lel.The authorsdesigi}ed tl}ehosemodel to reducethe requiredRetwork resourcesby aggregatii}g cttstomerpipesbeca.use aggregatedpipes,calle(i a hose,ca,nachievea statistica. Imultiplexinggain.They showed the effectiveness ef the hose model by usingtrace-driven simulations. eonstructs. provisiening they. The. RelatedWork. rithm. Arlany though. allocation bottleneck. link. utilization inside of. networks. the. spare. is. in. the. in. t}}e. that. no. Withnet,werk. @ 2e08 InformatioiiProcessingSocietyoi`Japan.

(4) 3970. Hose. Bandwidth. Allocation Method. to Achieve a MTA. Service for PPVPNs B. l.,t.-". ..... ..r VPNprovideis' ngtyyorK.mrmm. s. rj ='IVj. ..-..... 〈-. K-. ---"----. '. .〈. --. ------・. -.,-l. tttttttttttt. lngressrouter. -・"---1.. Egress router. cannot. be. k=1 where. j' indicates. The. egress. No. 12. 3967-3984(Dec. 2008). are. from. responsible ingress. tion. described. in. control. packets.. the. a. source. for. "Thereas. site. periodically. toward. routers. sending. shape. 'Ih'aMc. a. traMc. shaping. destination. site.. coritrol to. rates. packets. reflect for. the. path. tc". informa-. j' are. given. by rj・ 〈= min. (ER(i..). explicit. rates.. Note. Core. (ER(i. routers. × ?"j). r... indicates. and. sites. measure. virtual. of. the. flows. one. the amount. "f is the exponential. virtual flow. Here,. rate. for. based. nvf =max ('rr¥ir ,1),. where. ,. available. for. one. preventirig. weight. sudden. subscribers. coiitains. on. path. increases path. (i, e) in. (・i.e). and. sendirig between. routers.. periodically of. IB. an. j' between. edge. nurnber. is. is a parameter. path. egress. the. ..)). (IB). that. and. culate. × ?t;)・.rj・ +. rate bound. ingress. a virtual. of traMc. weighted. amount. of. arriving. traMc,. and. they. cal-. on. arriving. moving. flow corresponds. in a given measurement. average. of the fair share. to the amount. of traMc. period rate of a treated. by. weight.. Note that n.f representsthe sum of each weight value correspondingto all traMc passingthrough a linkof each corerouter,and the valueof n.f isalways greaterthan 1. Let Ut denote the targetIinkutilization and C be the linkcapacity.We then calculatethe fairshare rateof a virtualflow (i.e., one weight)as cxq rf= T} vf . 'Ibreducethe instantaneouschangesin the valueofrf,we introduceitsmoving average:. "f. Vol. 49. routers. index. routers,. where. IPSJJournal. path. ingress. incremental. Next, we describeaiiavailablebandwidth allocatiori rr)ethodbased on feedbackdriven control.Iricontrastwith the above two queuing methods, the inherent shortcoming of thisrnethodis that itcannot be appliedto the hose model, although itachieveshigh utilization with the custonier-pipe model. 'Ibachievehigh utilization and fairallocation, the weighted proportionaJfair rate allocation(WPFRA) inethodii)has been proposed. Here, we explaina one-way versionof the WPFRA method i2),which isan extensionofthe original. The originalWPFRA rnethodusesround-tripfeedbackcontrol,whereas the oneway versionhas been introducedto improve the convergencespeed to the target bandwidth in transition states. A briefoverviewof theWPFRA method isgiveninFig. 2. Two kindsofrouters are used: edge and core routers.Outside traMc entersat ingressedge routers, goes through corerouters,and finally exitsat egressedge routers.In thismechar nism,ir)gress edge routersobtainiriformation about the available bandwidth fi'om egressedge routersaridthen allocatethe bandwidth fairlyamong sitesbased on a weight appliedto each site.The main featureof the WPFRA niethod isthe assigmnentof weightsto provideweightedproportionalfairnessamong allsites. Here, we explainthe calculationprocessfbrbandwidth allocation.Let B be the available bandwidth in a network,wj be the valueof a weight,and rj be the optimum bandwidth allocationgivenby. the. ward. Weighted proportionalfairrate allocation.. achieved.. ,. 2 ?vk. where. resources. n. '"il". [II.Il.1. Edgerouter- Dataflow II]corerouter-.qt--controifiow Fig. 2. ×. e a. (1 -. a). represents. × Ff. +a. × rf,. a parameter. in. the. range. of. (O. : 1] for. determining. the. re-. @ 2008 Information ProcessingSociety of Japan.

(5) 3971. Hose Bandwidth. Allocation Method. to Achieve a MTA. Service for PPVPNs. '. The bandwidth allocationcalculationprocess and the system variablesof the WPFRA method are shown in 'Iable 2. The weights for sites Xl, X2, and Yl are all 1. To confirm the convergence of system variables and the allocated bandwidth, we set ef to a suMciently high value. When new traMc appears at time O.1, 1.1, and 2.1, the values of systein variables are changed. Then,. sponslveness. Finally, in. the. when packet. ER(i..). a. core. accordirig. 〈= Mill. router. receives. a. control. packet,. it updates. the. ER. value. to. (ER(i,e),. rf). '. As a resultof theabove procedure,thesmallestvalueofrf aloi}gthe path between the irigress and egressroutersisselectedas the valueof ER, which isthe explicit ratefora singlevirtualflow. As describedabove, the WPFRA method achieveshigh link utilization by measuring the arrivingtrafiicand applying dynamic bandwidth reallocation. We show an example to confirm the capabilityof the WPFRA method forthe customer-pipemodel. The network topologyforthisexample isshown in Fig.3. SiteXO transmitsdata toward sitesXl and X2. Similarly, siteYO communicates with siteYl. The bandwidth of the bottlenecklinkis 100Mb/s, and that of otherlinksisinfinite. Aftertime O, 1,and 2, traMc toward sitesXl, Yl, and X2 isinjectedinto the network. Routers I, C, E representingressedge, core,and egressedge routers,respectively.. [[hble. 2. Comparison. of bandwidth. allocation. and. calculation. xo-m--B:.:::;::Xtaflo. Rb K-. SLt... I ...--.. C. ""'. E. -. X2 .''-'S. CYLt)N -----・. Controiflow. 〉(: !.). Boraenecked link:1OO Mb/s Otherlinks: coMb/s Fig.3 Example of bandwidthallocation and calculation process: Network topology.. process. for the WPFRA. and. our hose. bandwidth. allocation. method.. ,. WPFRA Time. Sending rx1. rate. (Mbls). rx2. rY1. method. our. Systemvariables nvf. rar・r. Sending. rf. Ff. ER. rx1. hose. bandwidth. rate. (Mbls). rx2. rY1. allocation. method. Systemvariables raT・Ti. nvf. rf. Ff. ER. 999.0. 1oo.O 100.0. '. o.o O.1. o.o 1oo.O. o.o. o.o. o.o. o.o. o.o. 100.0. O.5. 1oo.O. o.o. o.o. O.9 1.0. 1oo.O 100.0. o.o o.o. o.o o.o. 1.1. 1oo.O. o.o. 1oo.O. 1.5 1.9. 50.5. o.o. 50.0 50.0. o.o o.o. 50.5 50.0. 2.1. 50.0. 50.0. 50.0. 2.5. 33.5. 33.5. 33.5. 2.9 3.0. 33.3 33.3. 33.3 33.3. 33.3 33.3. 2.0. 50.0. 1.0 1.0. 100.0 100.0. 999.0 189.9. 100.0 100.0. o.o 100.0. o.o o.o. o.o o.o. o.o o.o. o.o o.o. 100.0 100.0. 1,O 1.0. 100.0 100.0. 100.0. 100.0. 1oo.O. 100.0. 100.0. 1oo.O. 100.0. 1.0. 100.0. 100.0. 100.0. o.o. 50.0. 55.0. 50.0. 100.0 100.0. o.o. o.o 100.0. 50.5 50.0. o.o o.o. 50.5 50.0. 200.0. 2.0. 101.0 100.0. 2.0 2.0. 50.0 50.0. 50.1 50.0. 50.0 50.0. 100.0. 2.0. 50.0. 50.0. 50.0. 150.0. 3.0. 33.3. 35.0. 50.0. 33.3. 100.5 100.0. 3.0 3.0. 33.3 33.3. 33.4 33.3. 33.3 33.3. 100.0. 3.0. 33.3. 33.3. 33.3. o.o. 25.0 25.0. 25.0 25.0. 25.0 25.0. 25.0 25.0. o.o 100.0. 1.0 1.0. 100.0 100.0. 100.0. 1.0. 100.0. 100.0. 1oo.O. 100.0. 1.0. 100.0. 100.0. 100.0. 100.0 200.0. 1.0 2.0. 100.0 50.0. 100.0 55.0. 100.0 50.0. 101.0. 2.0 2.0. 50.0 50.0. 50.1 50.0. 50.0. 100.0 100.0. 2.0. 50.0. 50.0. 100.0 100.0. 2.0 2.0. leo.o 1oo.O. 2.0 2.0. 50.0 50.0 50.0 50.0 50.0. 189.9. 50.0. 50.0. 50.0 50.0. 50.0 50.0. 50.0. 50.0'. 50.0 50.0 50.0 50.0 50.0 50.0. ,. Weights. fbr sites. in. the. WPFRA. method: Capacity. IPSJJournal. VoL49. No. 12. 3967-3984(Dec. 2oo8). Xl:×2:Yl=1:1:1 of single. bottleneck. Wbights link. =. 100(Mbls),. fbr subscribers. parameter. a. in. our. method:. X:Y=1:1. = O.9. @ 2oo8 InformationProcessing Societyof Japan.

(6) 3972 HoseBandwidthAllocation MethodtoAchievea MTA Service forPPVPNs the system variablesand the sending ratesforallthe sitesgraduallyconverge to certainvalues,and the availablebandwidth of each siteis determined after thisconvergence.At tiir}e 1,sinceother sitesare not active,siteXl can utilize 100% of the availablebandwidth (sendingrate rxi = 100A,Ib/s).At tiri)e 2, the availablebandwidth is divided into halffor each siteXl and Yl (rxi = ryi = 50Mb/s). At tirne3, the availablebandwidths of the sitesare equally redistributed (rxi = rx2 = ryi = 33.3Mb/s) because traMc of othersubscribers affectsthe bandwidth availableto each sitein the customer-pipemodel. It is concludedthat the WPFRA method acl}ieves high utilization and fairbandwidth allocationin the customer-pipemodel. 3. Hose Bandwidth. VbL 49. No. 12. 3967-3984(Dec. 2008). Bi in bottleneck. "xx.....L'X.L..N... link i. 7. !1. l. 1. A2. ..IllNlilllIR2・l,31ll A3 likiiY')41l・:A)/LZil A4 ,.iiiiiiiNIRIll.I,3I( 1 ./-. Jt.. 1'. -.. .---. Al. Ri(Ao. -N. .ie. '. --. '. JJ. Jtf. -. i-/'. u. '7/////7/////////i. n -N. Bl. Allocation Method. An MTA servicewillprovidebetterthroughput predictability in PPVPNs, as describedin Section 1. Since allthe relatedworks have substantialshortcomings,they cannot achievean pt'ITAservicein the hose model. 'Ibovercome these inevitableshortcomings,we propose a novel bandwidth allocationmethod for the hose model. In thissection,we firstconsiderhow to allocatethe available bandwidth to hoses and then describethe requirementsand detailsof our traf ficcontrolmechanism. Finally,we presentthe featuresof our method through coinparisonwith the previousrelatedmethods. 3.1 MTA Service in Hose Model In thissection,we designa servicemodel in the hose niodel.Our basicideafor the servicernodelis that we proportionallydistributethe availablebandwidth to hoses in each bottlenecklink.First,we determine the ratioof the allocated bandwidth among hosesby using a provisioningalgorithm,and we assurnethat the allocatedbandwidth alwaysexceedsthe minimum agreedthroughput in the MTA serviceeven during a period of congestion.Then, we assignthe bandwidth that exceeds the minimum agreed throughput to the hoses. Finally,we distribute the excessbandwidth to activehosesbased on the ratiodetermined by the provisioningalgorithm. An exarnpleofthe bandwidth allocation in our servicemodel isshown in Fig.4. Two customers A and B contractforhosesAl and Bl, which containthreea,nd two pipes,respectively. Allpipesexcept forthe pipe from Bl to B3 (pipeBl-B3). IPSJJournal. Available bandwidth. 11. iR. ". B2. 1. -v. i(BI). y777}7i/4ne/l2./?l/L・'Z B3 ]g ----L-s'. .r. Ri(si). Available :R i(si-s2) :Available. bandwidth. of hose. bandwidth. from. tt-. -. in site Si. site Si to S2. OActive(11111) idie Fig.4. MTA. service. in the hose. model.. are active.Ri(.,)representsthe ayailablebandwidth of the hose of sourcesite si in the bottlenecklinki;Ri(.,..,)representsthe availablebandwidth divided equallyinto activepipes froiri source sitesi to destinationsites2. Since pipe Bl-B3 isidle,pipe Bl-B2 can utilize100% of Ri(Bi).Therefore,activehoses always providelinkutilization ofnearly 100%. In thisexample,we dividetheavailable bottleneckbaiidwidthBi proportionally between hoses Al and Bl in the ratioa to (1 - a) duringperiodsof congestion. Ri(s,)isgivenby Ri(Ai)= aBi, Ri(Bi)= (1- a)Bi,(O s{a f{ 1). The. ratio a is detet'mined. by a bandwidth. allocation. by. a provisioning. method.. Then,. algorithm, Ri(.,-.,). and. Ri(.,) is calculated. is calculated. by. Rz(Ai.Ax) =illllli[AAiil・ Ri(Bi.Bx) =iilil[BBI))' @ 2008 Information Processing Societyof Japan.

(7) 3973 HoseBandwidthAllocation Method toAchievea MTA Service forPPVPNs where Aili(.,) represei}ts the mimber of activepipesin a hose of sourcesitesi. Our assumption isthat A4TA sei'vice can be achievedwhen the bandwi(-lth allocation method precise}y dividesthe bandwidth accerdingto the ratioa, wl}ich isdeterininedby the provisioi}ing algerithm.Based on our servicemodel in the hose il}odel, we considerthe mechanism ofoiirhose bandwidth allecatien k'iethod in the next section. 3.2 Mechanism To meet the requireinents forboth bandwidth allocatiolt ai}dhigh utilization, we integratea feedback-drivent,raffic centroland QoS schedulera,tan ingress router.k}gressi'outers can be aware of the congestionstatusof the network to obtainayailable ikformatio"from egressrouters.Based on the collgestion-related inforination, the maximuin a,mount of avai}ableban(lwidthcan be allocatedto activesubscribersand sites. k} our method, we {isea ene-way versioi} of the WPFRA rnethodi2)and classbased queueing (CBQ) '3)as a feedback-driventraffic contro}and traffic scheduier.Tl}eWPFRA med}od can completelyexploitthe ayailable bandwidt}},and CBQ can hierarchically shape the input tra{flc rateat the subscriberaltdsitelevels.Airloreover, we inaplemellt two i}'}echai}isins at ii}gress routersto simultaneously satisfythe a,bovetwo requirementsforfaimess.The firstistrafEic measurement foreach destinationsiteto determinewhether traffic ttothe destinedsiteisactive. Ingressroutersperiodically monitor t}}eamount of iRcomlng tra,fflc and classify allsites.We utilizea ll}easureinent algorithmthat isan expoiientially weighted movii}gaverageto adjustthe convergencespeed.Tke otherisdynamic eontrolof CBQ based on activeinformation.Mere specifically, the feedbackcontrolpackets from the Hetwork are used to determii}ethe amomit of ba,ndwidthto allocate, which issetin the CBQ parameters. To set these pa,rameters, the ingressrouterfii'st looks up the ideNtifier of a bottlenecklinkin a receivedcontrolpacket.The bottlenecklinkisspecified by core routerswhen the controlpacket passesthrough them. Thei},the ingress routercalculates the bandwidth assignmei}t to each subscribercorrespondingto the bottlenecklink,ai'id the assignedbandwidth is divide(levenly among the subscriber's activesites. The pseudocede ofthesealgorithmsisshown in Fig.5. First,the RecvCtrlPkt. IPSJ. Journal. VoL. 49. No.. 12. 3967-3984〈Dec.. 2008). /********************************************* variable. h:. Variable. for. hose. variable"hp: Vaxiable tor h; KumbeT of 6ubscyibers num-hp:. Number. of. h:. rndex. of. hose. p:. rndex. of. pipe. Total. number. 1:. pipe. of. hose. subscriber. of. Bettleneck. 1ink. Weight Active. flag. (binary〉. Available *********************************************1 #define. ZERO. O.Ol. RecvCtxlPkt. //. very. CtrlPkt. *p. small. value. 〉{. f********************************************* Look. up. network. infomnation. control. packet. ***************s*****************************1 ER. tt LookupER(p);. LeokupBottleneckLink(p);. l********************************************* Calculation. for. heGes. *********************************************1 /l. Calculate. tor. Eg.. h=Q;. h〈num-h[hj;. r)[1][h]. h++. ER. w-h[h];. /********************************************* Calculation for pmpe6 hoses *********************************************1 11. Calculate. for. the. httO; for. p=O;. !!. Calculate h"Q; for. Eq.. p++. [1] fu] [p] ;. Eg・. r-hp[i]. if. 5. h++. h〈nurnnvhp[h]. ){. [p] ; p-. ){. [xl [p]. [hi [p]. xnvhp[l]. rthhp[1]. Fig.. x-hp. h〈nummh[h];. xpthp [U. else. [p];. [h3 [p]. p:tte; if. of. h++. h〈num-hp[h]. s-hp[ll. ior. denominator. h〈nun"h[h];. [h] [p]. rnvh[1]. [h]. sMhp[1]. [hj [p];. [x] [p] ZERO;. Pselidocode. of calculation. of bandwidth. al}ocation. at ingress routers.. @ 2e08 Infom}EttionProcessingSocietyof'Japan.

(8) 3974 HoseBandwidthAllocation MethodtoAchievea MTA Service fbrPPVPNs functionis executed when ingressroutersreceivecontrolpackets. Then, the ingressroutersobtain the valueof ER and the locationof a bottlenecklinkby usingthe LookupER and LookupBottleneckLink functions, respectively. Finally, the ingressrouterscalculateand allocatethe bandwidth to subscribersand active sitesbased on the followingEqs.(1)and (2). Let ?vhbe the weight of subscriberh and 'ri(h) be the bandwidth allocatedto bottleneck. link. t given. rt(h) 〈= min. CA. Osl)ej (,b. by. (ER(i,.)×?vh,ri(h)+IBx?vh),. (1). B. 3.0ER. 1.5ER. 1.5ER. 2.0ER. 〈B. 2.0ER. wherepath(i,e) contains bottleneck linkl.Notethat,hereafter, we omitthe adjustment parameter ofIB;inotherwords,we setIB toa sufficiently highvalue. Then,letxi(hp) be a binaryflagthatindicates whethersitep ofsubscriber h. weightA:B=3:2 CH')Active. is active. ER: Available. in bottleneck. sites given. let ri(hp) be. the bandwidth. allocated. to active. by rl(hp) n. 'rl(h p). link l and. j'=1. o. Fig. 6. (2). - o), (:nt(hp). where 'nisan index identifying Note that sincetheseequationsareconceptual,we rnustallocatea very smallbut nor}zeroamount of bandwidth to idlesitesto preventthem discardingallof the incoming packets. The differencebetween the WPFRA method and our method is the impact of new traMc on the calculationprocessof system variablesand bandwidth allocation.In Table 2, new traflic of the same subscriber(i.e., X2 at times 2.0 and 2.1)does not affbctthe valuesof system variablesin our method, whereas the startof any traffic does affectthe system variablesin the WPFRA method. Therefbre,our method can dividethe availablebandwidth among subscribers, whileWFPRA dividesitamong sites. Next, we explainthe inherentdifficulty of bandwidth allocatioR where the multipleingressroutersexist.Ifallsubscribersare connectedto the same ingress router,itcan easilydistributethe available bandwidth to them. In other words,. IPSJJournal. Vol. 49. /"'-"'x.. foravirtuatflow L."? Idle (Xl(h.) == 1). 2 a:i(hJ・) =. N.L7. bandwidth. No. 12. 3967-3984(Dec. 2008). Bandwidth. allocation at ingress routers.. the ingr'essrouter does not need to be aware of inforrnationabout other subscribers.However, ifother subscribers connect to other ingi'essrouters,then all the ingressrouters must shape the arrivingtrafficbased on the information about allsubscribers. An example of bandwidth allocation with multiple ingress routers in our method isshown in Fig. 6. There are two subscribersA and B. SitesAl and Bl coMmunicate with A2 and A3 and with B2 and B3, respectively.Ingress router Il has CBQ class A and CBQ classesA2 a,nd A3 as childrenof the CBQ class A. Similarly,another ingress router I2 has CBQ classesB, B2, and B3. Here, ER is the bandwidth ava,ilable for a virtualflow. To explain the basic behavior of weighted proportional fairrate allocationamong subscribers,we assume that the weights for subscribers A and B are assigned as 3.0 and 2.0, respectively. There are three activesites:A2, A3, and B2. In thisexample, subscribers A and B are allocated 3.0ER ai}d 2.0ER based on their weights, respectively.At the sitelevel,sitesA2 and A3 can use 1.5ER because both sitesare active.3.0ER is evenly divided between two sites.On the other hand, siteB2 can use all of the. @ 2008 Infbrmation ProcessingSocietyof Japan.

(9) 3975. Hose. Bandwidth. Allocation "iethod to Achieve a MTA Tbble pt:Iethod. Service fbr PPVPN$ 3. Comparison. Information. Two-levelWFQ9),iO). Hose Hose. gathering N N. WPFRA11),12) Ourmethod. Pipe Hose. 2-DDRR6). Y Y. method ModifiedDRR. ModifiedWFQ Optional. CBQ(optional). bandwidth allocatedto subscriberB because siteB3 isidle. 3.3 Qualitative Comparisons The benefitof our inethod isthat itcan ineetthreesubstantialrequirements: proportionalfairbandwidth allocation among subscribers, fairbandwidth allocationamong activesitesin each subscriber, and high network utilization. 'Ilable 3 compares our method and thoseir}the relatedstudiesdescribedin Section2. 0ur method isthe only one that satisfies allof the above threerequirements. As describedin Referencei4),bandwidth allocation ainongflowshas significant complexitybecausesuch an algorithrn requirespacketclassification and per-flow statematiagement. In the context of VPNs and the hose model, fairallocation among subscribersand sitesis required,even though per-flowfairnessis unnecessary.Since per-fiowprocessingiscornplex,itshould be performed at the gateway of each site.The rnainreasonwe iisethe WPFRA method isbecause thismechanism does not processat the per-flowlevel,so it inherentlyachieves high utilization. 4. Evaluation In the previoussection,we describedhow to allocatethe ayailablebandwidth intohoses foran ":ITA servicein the hose model and presentedthe hose band-width allocationmethod. In thissection,we describecornputersimulationsperformed to quantitatively evaluateour hose bandwidth allocationmethod. We firstconfirm the basicbehaviorof our algorithmthrough comparisonswith the WPFRA method. As a perfornianceevaluationindex, we use the "allocation errorrate"as the ratioof the bandwidth in use to the previouslyallocatedbandwidth. Since the minimum throughput niay not be assuredifthere is a high. VoL49. No. 12. 3967-3984(Dec.. 2008). Fairness. Queuing. iThough. IPSJJournal. and ones in related work.. of features between our method. Model. subscribers. Highutilization. sites. flows. Yi. Y Y. Y N. N N. N Y. Y Y. N N. Y(bottlenecklink) Y(bottlenecklink). N. it has not been proved in their computer. I. 1oo. Mbls. i. 1oo. Mbls. i. 1oo. simulations.. l l. Mblsl. *.-!-・-!・!mp."-L,,.smms"-fi.""-"rm...i・.,.lp..mp........----. l G・yMbls 100 Mbls : 10 rns tt.tt.tt.....t*dttJIO rns. l 1co Mbls i : : 5 rns t"J-*tJt---L-t-t.]ttt-utti. .〈(M〉. dy. VPN as〉. providers' netwerk. /x〈AD-J"-]-". tstJ .〈IANII'). dy-×-. .@ 〈5Y7. 2. Ingressrouterc Fig. 7. XL. -h. tts. Core. .tH.----.-.---+J---'--t''. router. E: Egress. router. e=oj. Simulation topology.. allocation errorrate,the allocation errorratemust be reduced,so we investigate the impact of traflic parameterson the allocation errorrate.Finally, we analyze the stability forour method. On the basisof thesecomputer sirnulation ruris, we clarifythe characteristics of our method and indicatehow to decidethe system parametersforour method. 4.1 SimulationModel The computer simulatorwe used isthe ns-2.29simulatori5).Sincethe original ns-2does not containour hose bandwidth alloca,tion method, we add a module for itby extending the WPFRA module. The network topology used in the simulationisshown in Fig.7. To check whether our method has the designated hose behavior describedin Table 3 in Section3.3,we constructthe simplest topologyon the hose model where there are two subscriberseach of which is connected to two destinationsites.Il and I2 representingressrouters,Cl and C2 representcore routers,and El and E2 representegi'ess routers.These six routersform a VPN. Al, A2, and A3 are routersbelongingto subscriberA.. @ 2008 Information ProcessingSocietyof Japan.

(10) 3976. Ho$e Bandwidth AllocationMethod to Achieve a MTA Table 4. Servicefor PPVPNs Table. Output bufferlength ofeach router.. d. Router Rightdirect!on. Leftdirection. Al,Bl IlI2 ' Cl,C2 Others Others. IPSJJoumal. Vbl.49. No, l2. 3967--3984(Dec. 2ee8). Parameter$etting,. cr. IB Interva,}timeofingressrouters Intervaltimeofcorerouters Interva}timeot'egre$srouters. 600 400 oo oc. Similarly, Bl, B2, and B3 belollgto subscriberB. al, ..., aJ6a・ndbl, ...,b6 are TCP sendersof $ubscribersA and B, respectively. Ti'aflic from al, a2, aRd a3 and frem a4, a5, ai}da6 goes to A2 and A3, respectively. Similarly, traffic from bl, b2,and b3 and from b4,b5, and b6 goes to B2 an(lB3, respectively. All links are 100Mb/s, and the linkpropagatiei} delaysrange froin1 to 10ms, as shown in Fig.7. As describedin Section3,we treata topologywith a singiebottleneck liltk and multip}esubscribersconltectedt・odifferent, ingressrouters. Tb preventTCP oscillatien, we vary the propagationdelay ef accesslinksbetween that of the TCP sender hosts and Al or Bl: 1, 2, and 3ms. The TCP algorit}}mis TCP SACK, and the nuinber of TCP flowsis 10e foreach TCP sender,i.e., 300 fiowsforeach destinatioi} site.TCP data a.,ndcentrolpacketsize are 1500 and 10e bytes,respectively, includingthe headers.The buffersizesilt the routersaregivenin 'fable4. SiRceiitgress reutersshape iRput・trafiic in our metbod, the buffersizein a reuterinsidethe network shouldbe small.Therefore, we seta lovyTer valueforthe buffersizein core routers.Simllarly, we set a higher value forthe buffersizein routersoutsidethe netwerk to shape the eRormous amount of iRput traffic. "]rhe va,lues ofcoBtrolparametersused in our inethodare givenin ']Eable 5. [[b evaluatethe basicbehaviore{'our method, we mitigatethe effectef adjustment・ parameters;i.e., we setctand IB to sufi}ciently high values.'l]heiRtervaltimes of ingress,core,and egressroutersis500, 100,and 100ms, respectively. k} our method, the responsibility of ingressroutersissignificant because we implement two additionalmechanisms at ingressroutersas describedin Sectien3.2. We explaii}why the intervaltiineof ingressroutersislongerthan those of other routersin Section4.5.. 5. Parameter. Bufferlength 12oe. Va}ue e,g tTro. seoms lOOms 1eoms. ,. 4.2 Comparison with WPFRA Method In thissection,we compare the behaviorof the WPFRA metho(l and our method. Fbr thissiltaulatioll scenario,we deinoilstrate thatour algei'ithin caltallecatebandwidth foreach activesubscriberwhen traMc isinsertedand removed. To simplifythe i}etworktopology,we set5 and 7 to 100 Mb/s in Fig.7. Traffic toward A2, B2, A3, ai}dB3 startsa,t1, 10,3e, and 50s,respectively. The simulatioi} ends at 100s. We setweightsof 3 forsubscriberA and 2 forsubscriber B illour method. Sii'}ce the WPFRA method isunable te a,llocate bandwidth fora subscriber, we set 3 forsitesA2 an(lA3 and 2 forsitesB2 and B:3in the WPFRA method. The throughput (lynamicsofthe two methods are shown iHFig.8. 'l]he x-axes represei}t time iiiseconds,and they-axesindicatethe receive(l throughputat A2, B2, A3, and B3 with a measurement illterval of 1s. First,we focuson Fig.8(b)which concernsthe WPFRA naethod.Sincei)andwidth divisioll isperforH'}ed foreach customer pipe,not foreach sut)scriber a,ggregatioB,new startiRgtraMc at 3{)altd5es and ending tra,ffic at 70 and 90s atlectthe throughput of allothertra,Mc.When a sitebecomes active/idle, the throughputof allethersitesdecreases/increases. On theotl}erhalld,our method illustrated in Fig.8(a,) shows a di{ferent behavior.The sta,rting traffic toward A3 at 30s and B3 at 50s does not affectthe throughput ofothersubscribersB and A, respectively. Sixnilarly, the throughput of oRe subscriberisltotaffectedby ending traMc of the othersubscriberat 70 and 90s. In the bandwidth allocation among sitesbelongiiig to thesame subscriber, the ba,ndwidthavailable to sitesA2 aJndA3, and to B2 and B3 isdividedequallyat 30 a,nd50s. This confirmsthat our method cadnuse the l}osemedel because-our inethoddividesthe balldwi(lth a,tboth the subscriberat}dsitelevels.. @ 2008 Ini'ormationProcessingSociety ot'Japan.

(11) 3977. Hose. AllocationMethod to Achieve a AxlTA Service. Bandwidth. fbr PPVPNs. Wbight fbr subscribers:A : B = 3 : 2. kble. 1OO. Bandwidth. allocation. error rate and. utilization.. 1. :. Ourmethod. --e-".HX.".. --e---. 80. 6. Unit:Mbls. -+--. d. A2 B2 Utilization. 60.00(+O.OOU%,). WPFRAmethod. 59.96(-O.07U/o). 1oo.ooo/o. 100.000/,. 30.28〈+O.93U/o). 37.68(+O.48%). 4. c.e oo Y. A2 A3 B2 ,. e op fi. o. ac. o. op. oo. eo. 1OO. 11me (s) (a) Our method Weight for sites:A2:A3:B2:B3. =3:3:2:2. 1OO. 80 A. 60. g ` c,). s co f. ,isi ma. 20. o O. 20. 40. 60. 80. 100. 'fime 〈s) (b) WPFRA Fig.8. IPSJ. Comparison. Journal. of throughput. Vbl. 49. No.. 12. dynamics. method between. the WPFRA. 3967-3984 (Dec. 2008). method. and. our. method.. 30.28(+O.930/,) 37.68(+O.48a/o) 39.44(-1.400/o) 24,63(-1.480/o). Utilization. 100.oo%. A2 B2 B3 Utilization. 59.50(-O.830/,) 42.37(-1.140/o) 20.25(+1.25Q/o) 28.82(+O.870/,). -. 20. qn E. '. ,. =a o. '. 4o.oo(+o.ooo/,) 40.04(+O.100/,). 100.oo%. 20.25(+1.250/,). 28.82(+O.870/,). 1oo.oovyro. loo.oou/o. Next, we investigatethe bandwidth allocationerrorrate and utilization in certainscenarios.In allscenarios,tra,Mctoward A2, B2, B3, and A3 starts simultaneouslyat ls, and the simulationends at 100s. We investigate three simulationscenarios:traMc toward A2 and A3, traMc toward A2, A3, and B2, and traMc toward A2, B2, and B3. The ayeragethroughputat the receiverside and the utilization in each scenarioare givenin thble 6. All the resultsin the tableare ayeragesof a 50-secondmeasurement between 50 and 100s. Regarding the utilization, our method and the WPFRA method both achieved100%. As for the allocation errorrate,valuesinsidethe parenthesesinthe tableindicateerrors frornthe targetthroughput.These resultsshow thatour method achievesfairly low errorrates(i.e., below 1.5%) foreach site.Regarding the subscriberlevel, in every scenario,subscribersA and B attainapproximately60 and 40Mb/s, respectively. All allocation errorratesfor subscribersA and B are alsobelow !.5%. The resultsdemonstrate that our method can allocatebandwidth for subscribersbut not for sitesand that it can provide high linkutilization. Thus, from thesecomputer simulations, we concludethat the hose bandwidth allocationmethod describedin 'Ilable 3 in Section3.3can be achieved. 4.3 Impact of Multiple Bottleneck Links in a Hose In the previousscenario,the bottlenecklinkwas a singlelinkbetween core. @ 2008 InformationProcessing Societyof Japan.

(12) 3978. Hose. Bandwidth. Allocation 'I〉ible. 7. Method Results. to Achieve tbr mu}tiple. a MTA. Service. bottleneck. links.. O.5. Mbls. O.4. Unit:. fbr PPVPNs. "' ,. SubscriberAl. 17.98(-O.11U/,). C2-El C2.E2 Total Active:. 12.oo(+o.ooe/,) 29.98(-O.070/,) A2,. A3,. B2,. SubscriberBl. 12.02(+O.17U/o) 8.oo(+o.ooO/,) 20.02(+O.100/,). B3. T'. 30.00(+O.OOU/,) 12.14(+1.170/o) 42.14(+O.330/o). C2-E2 Total Active:. A2,. A3,. B3. o.oo〈+o.oou/o). 7.86(-1.750/o) 7.86(-1.750/o) Idle: B2. IPSJ Journal. Vol. 49. No. 12. 3967-3984(Dec.. 2008). 's,bgtl"ibo',A'. .tri'. ×. e,3. Eto-o.2 9E. .. )tw×pm. 〉2i(. Se. av -Iltl. .o..o.1 g. sumu/〉S(. × )pts〉Ose. O.1. ptil+iiltl lS-l+-fttT-kfLL+tti+Fi4{#+tltlki+ltIHt"f+-Y"{lliS"fTIH. .o.2. 〈 -O.3. routersCl and C2, although traMc toward sitesA2, A3, B2 and B3 passed through different paths Il to El, Il to E2, I2 to El, and I2 to E2, respectively. Next, we evaluateour method in a network topology with rnultiple bottleneck linksin a hose. In the hose model, each hose accommodates multiplepipes, so a hose can have multiplebottleneckIinksin different pipes. In contrast,in the customer-pipemodel, a customer pipe cannot haye rnultiple bottlenecklinks because itrepresentsa onetGone connection,not one-tomany connectionsIike the hose model. 'Ibconstructa network topologywith multiplebottlenecklinksin a hose,we set linkcapacities6 and 7 to 30 and 20 Mb/s in Fig.7, respectively. The first bottlenecklinkisthe linkbetween C2 and E1: the otherbottlenecklinkisthe link between C2 and E2. This simulationscenarioisthe same as that in Section4.2, except forthe linkcapacity. The sirnulation resultsare surninarizedin 'Table 7. 0ur method can divide the availablebandwidth intothe ratioof 3 to 2 in the congestedlinkand achieve high link utilization.Even when siteB2 is idle,our method can provide at leastapproximately8Mb/s to subscriberBl. In both simulationscenarios,the maximum allocationerrorrateis 1.75%. We concludethat ifno allocationerror occurs,the rninimum agreedthroughput ofat least12 and 8 Mb/s can be assured to subscribersAl and Bl, respectively, in thisscenario. 4.4 Scalability The above resultsshowed what our hose bandwidth allocation method iscapableofdoing.We now evaluateour method iriterinsofthe scalability and stability. '''. SubscriberB. .o. C2.El. 'T. .o.4. -O.5. o. 10. 20. .L.-...1.". ...L..."S .. .i 30 40 50 60 70. l 80. .L.....J 90 100. Ratio of number ot fiows (Subscriber BISubscriber A) Fig.. 9. Impact. of imbalance. ratio of TCP. flows on error rates.. which areimportantperformancemetrics.First,we focuson thescalability where parameters of two subscribersare uribala,nced becauseof the foIlowingreasons. In our method, the ratioof two traMc parameters- the number of TCP flows and number ofdestinationsites- among different subscribeismay impact performance, i.e., ifsome subscribers have more TCP flowsthan others,then they may obtaina largerbandwidth. Similarly, the imbalancein the number of destination sitesmay alsoimpact performance.In thissimulationscenario,we sirnplyset6 and 7 to 100 Mb/s in Fig.7. The impact of the imbalance ratioof the number of TCP flowsisshown in Fig. 9. In thissimulation,the number of TCP flowsfrom subscriberA isfixed at 60, whereas the number of TCP flowsfrom subscriberB variesin the range between 60 to 6000. This means that the imbalance ratioof the number flows of subscriberB to that of subscriberA is ranged from 1 to 100. The number of destinatiori sitesis 2 both forsubscribersA and B, and the weight value is 1 for both subscribersA aridB. The x-axisrepresentsthe imbalance ratioof the nuiiiberof TCP flows,and the y-axisisthe allocation errorrateof the total throughput foreach subscriber.. @ 2008 Information Processing Societyof Japan.

(13) 3979. Hose. Bandwidth. Allocation. Method. to Achieve. a A:ITA. Service. fbr PPVPNs. 15. 1. :. ¢. e.s. !. go -#-. .p-. g .o.s. l.:.U +l+lllltt. 2. +. th. wh. -1 -1.5. O. 10. 20. 30. pteag# 40. 50. 60. 70. 80. 90. 100. Ratio of number of destinationsites (Subscriber BISubscriber A) Fig. 10. Impact. of imbalance. ratio of destination sites on error rates.. If the amount of incoming traMc is not regulated,the throughput ratiois normally proportionalto the nurnber of TCP flows.Nevertheless, the errorin totalthroughput foreach subscriberisnearlyzeroeven when thenumber of flows increases.The maximum, ayerage,and minimum errorratesare O.30,O.23,and O.O09J6, respectively. This resultprovesthat our method achievesthe robustriess of the number of flows. In the next scenario,we examine the impact of increasingthe number of destinationsites, i.e., the scaleof the hose (Fig.10). The totalnumber ofdestination sitesconnected to egressroutersforsubscriberA isfixedat 2,whereas the number of destinatiori sitesofsubscriberB variesbetween 2 and 200. In otherwords, the range of the imbalance ratiofordestinationsitesof subscriberB to that of subscriberA is1 to 100. The number of TCP flows-is 600 forboth forsubscribers A and B, and the weightsare 1 foi'both subscribers.The x-axisin Fig.10 representsthe imbalance ratioof the nurnber of destinationsites,and the y-axis indicatesthe allocatiori errorratein the totalthroughput foreach subscriber. The errordoes not continueto increaseeven when the imbalance ratioof the destinationsitesincreases. The maximum, average,aridminimum errorare 1.09,. IPSJJournal. VoL 49. No. 12. 3967-3984(Dec. 2008). O.75,and 0.01%, respectively. Most resultsarebelow 1.009J6. As with the robustness againstthe nun')berof flows,thisresultshows that our inethod is robust with respectto the number of subscribers. The resultsof our simulationsclearlyshow thatingressrouterscan controlthe amount of incoming traMc even when the scaleof a VPN between subscribers A and B is imbalanced in the ratioof 100. Thus, we concludethat our hose bandwidth allocationmethod can keep the low allocatiori errorratein a largescaleVPN. 4.5 StabilityAnalysis The above simulationsshowed the effectiveness of our hose bandwidth allocationmethod. However, ifthe allocationerrorrate is significant, the MTA servicemay not be achieved.Therefore,we must analyze the factorsaffecting the aJlocation errorratein the firial simulationsceriarios. As describedin Section3.2,we implemented a traMc measurement mechanism iningressrouters.The ingressrouterisresponsible fordeterminingactivesitesby measuring the amount of incoming traMc forthe destination sites, and allocating theavailablebandwidth to activesites.The most importantaspectofour rnethod isthat inaccuratemeasurernentiriingressrouterscausesallocationerror.For example, ifn - k sitesare erroneouslyrneasuredin ingressrouterswhen n sites are active,then the allocatiori bandwidth for each siteis shiftedby a factor of n/(n - k). However, 'nsitesare actuallyactive,hence the throughput for each site fluctuates. ":Ioreover,the nuiiiberof destination sitesrepresents the number of queues in ingress routers. The total nurnber of flows divided by the number of destiriation sitesisthe number of flows that passes through each queue. Therefore, the possibilityof a queue instantaneously becoming empty increases as the number of destination sitesincreases.This characteristicmay cause the error in Ineasuring active sites. An example of an inaccurate nieasurement of the number of active sitesat an ingress router is shown in Fig.11. The rneasurernent intervaltirne for ingress routers i$ 50ms. The number of TCP flows of subscribers A and B is 600 for both, and the numbers of destination sites of subscribgrs A and B are 2 and 200, respectively. Iriother words, 300 and 3 flows pass through each queue, respectively.Here, we focus on siJbscriberB. The correct measured value for. @ 2008 InfbrmationProcessing Societyof Japan.

(14) 3980. Bandwidth. Hose. Allocation Method. Number Number. to Achieve a MTA. 6f destination sites of TCP flows. Service fbr PPVPNs Number Number. A : B = 2 : 2oo A:B= 600:600. of destination of TCP flows. sites. A :B A :B. = 2: 200 == 600:600. m. tntervaltime ot ingress routers:. ..o.m. 200. 9 -5' to v 9 -g. co -c} .di m .z5 150 co v 9 8 gE 1OO 'o"' tsn E5 sc z. 1'. 200. I f+t+. n'. t. +. 150. E E 8 E e 2 =o ¢ msi. 1oo. 50. 〈 9 D. Fig.. 11. lo. 2o. 3o. Error in number. 4o. so. 6o. 7o. Time {s) of active sites measured. so. ge. 1oo. at ingress routers.. subscriberB is200 becauseallsitesareinfactactive,but the measurement results are approximately40 and unstable.Consequently,each activesiteattempts to utilize a factorof 5 in the availablebandwidth, which causesthe fluctuations in throughput at each site. 'Ibclarifythe factorsaffecting the measurement error,we investigate the measurement intervaltime of ingressrouters.The x-axisin Fig. 12 shows the mea,sureinentintervaltiirie of ingressroutersin milliseconds, and the y-axisindicates the averagenuiiiberof activesitesmeasured during a 50-speriod.The rneasurement value convergeson 200 as the measurement intervaltime increases.The reasonfor thisis that fluctuatingtraMc passesthrough ingressroutersat each measurement intervaland ingressroutersmeasure the bursty traflic, i.e., TCP traMc. The irnpactsof the propagationdelay between core routersand the measurement intervaltime of ingressrouterson the allocatiori errorrate are shown in Fig.13. The linkdelabrsmight be another significant factorin the erroneous irieasurementin additionto the ineasurementintervaltime becauseour method. IPSJ. Journal. Vbl.. --i-----. o. o. 49. No. 12. 3967-3984(Dec. 2008). o Fig.. 12. so. 1oo. 1sc. 2oe. 2sc. 3oo. 3so. 4eo. 4se. soo. Intervel timeot ingressrouters(ms} Impact of measurement time interval at ingress routers on measurement. error.. is based on a feedback-driven control iiiechanisiii that issensitiveto delays. The values along the z-axis are the average allocationerror rates fbr subscribers A and B. The simulation resultsshow that the allocationerror rate converges to nearly zero as the measurernent tirneintervalof ingressrouters lengthens regardlessof the propagation delays. In other words, the rneasurement time interval can Iimit the iiripactof the propagation delays. It followsfrom these resultsthat the measureinent tin'}e intervalof ingr'essrouters is definitelyrelated to the alIocation error rate. It is one of the adjustable parameters, unlike in the case of the link delays. Therefore, we conclude that the measureir)enttime intervalof ingress routers should be long enough to stabilizeour method. The above three simulation resultsshow the impact of inaccurate measurement on short ineasurernent tirneintervals.rlbstabilizeour inethod and deterininethe measurement time interval,we analyze the requirod rninimum measurement tirne intervalin ingress routers. The impacts of linkdelays and subscriber imbalance ratioon the required minimum measurement time intervalare shown in Fig. 14. The x-axisrepresentsthe propagation delabrbetween core routers Cl and C2, and. @ 2008 InformationProcessing Societyof Japan.

(15) 3981. Hose Bandwidth AllocationMethod to Achieve a MTA. Number of destinationsites Number of TCP flows Average allocationerrorrateof A and B I]%] 1OO. Service fbrPPVPNs. A : B = 2 : 200 A:B=600:600. Number. of TCP. flows. A:B. =. 600:6oo. Required 300. 250. 200. 150. 1OO. 1OO. 40. o. Propagation delay. Mea$Ourement tiimOeOintervai 2oOf9ngress r3oeu9ers [ms]4oosoobetween ciand c2[msl Fig.. 13. Impact. of measurement. time. interval. in ingress. routers. on allocation. error rate.. the y-axisindicatesthe imbalance ratioof the numbers of sitesof subscribersB and A. The minimum valuessatisfying the preciseineasurernent of the number of activesites(i.e., exactly200) are plottedtoward the z-axis.As forthe propagationdelays,the requiredvaluedoes not change or slightly increasesdepending on the imbalance ratiofor subscribers.The imbalance ratioof the number of siteshad rnore impact on the measuremerittime ir)terval. The requiredvalue shows a linearincrease.Fr'omthisresult, we clarifythat the correlation between the stability of our method and the linkdelaysislow. Frornthe above sin'iulation runs,we clarified that the ineasureinent tiiiie intervalof ingressroutersisa significant factorforthe stability of our hose baridwidth allocationmethod. Therefore,to reduce the allocationerrorrate,we should set the long time iriterval for the ingressrouters.We note that itis necessaryto deterrnirie the optimal measurement tinieintervalforeach router.We consider that a controltheorymabr be applicableto our hose bandwidth allocation method. IPSJ Journal. VbL 49. No. 12. 3967-3984(Dec.. 2008). 1OO. 50. O 20 40 6o Propagation delay between Cl and C2 [msJ Fig. 14. Required minimum measurement.. so. lmbalance ratiofor loo. nuMberofsites(B/A). measurement time intervalin ingressroutersforprecise. such as theexplicit controlprotocol(XCP) i6).Although itisbeyond thescope of our research,thestability of such feedbacksystemsmight be achievedby plotting theiropen-looptransferfunctionon a Nyquist plot. 5. Conclusion In thispaper,we focused.on an MTA servicein the hose model and explairied the need fora bandwidth allocationmethod. On the assumption that network provisior}ing has alreadybeen completed,we desigried a hose bandwidth allocar tionmethod to achievethe MTA servicein the hosemodel. Our method provides at leastthe rninimuiii agreed throughput to activehoses even during a period of congestion.Our basicidea isthat our method gathersavailablebandwidth informationfroiii insidea network and dividesthe available bandwidth intohoses on each bottlenecklinkusingthe information.Our method was designedto meet the fo11owingtwo requirements:(1)fairness in terms of hosesand pipesand (2). @ 2008 Intbrmation Processing Societyof'Japan.

(16) 3982. Hose. Bandwidth. Allecation. Method. to Achieve. a MCrA. Service. fbr PPVPNs. high utilization of network resources. We ran computer simulationsto examine our method's a(lvantages alldt,oanalyzeitsscalability and stability. First,we determii'}ed the basicbeha・vior of our metho(lin throughputdynainics.Our met}}odeliniinated the impact of i}ewtrafi ficinsertion and existingtraMc removal on othertraffic. We theltinvestiga,ted its accuracyand effectixieness. Simulationresultsshowed that our method achieved a fair}ylow allocation errorrate.Regai'('ling the utiliza,tion, the linkutilization that itachievedwas as high as thatachievedwith the WPFRA method. IB the caseofa topologywith multiplebottlenecklinks,we found thatollrmethod could sa,tisfy tl}eininin'mn} agreed throughput by dividingtl}ea,vailable bai}dwidthusing the inforination insidethe lletwork.Ik the next sinmlation,to analyzethe scalability of our method, we exan}inedthe impact of the ratioof t・hescaleof subscriberson the allocatioi} errorrates.We proved that our method kept the alloca,tioi} errorra,telow even when the scaleof the VPN iHcyeased.Fina,11y, to clarifythe stability of our method, we analyzedthe factorsaffecting the a}locatioi}errorin tl}elastsiinulat,ion runs and c}arified that the n'ieasureii}ent tin}e intervalof ingressrouterswas definitely relatedto the allocation errorrate.On the otherhand, the linkdelaywas not a signifiea"t factorforthe stability ofour method. In suinmary, we sliowedthat eur n'}ethodsatisfied bot・hthe requiremei}ts for achievingan At`ITAservicein the hose model, clarified the scalability of our method, and indicatedhow to decide itssystem parameters.In future,we will apply our n'}etl}od to an ii}ter-VPNenvironmei}t. Acknowledgments We thank AssistantProfessorTakeshi Okuda, and.As-・ sistantProfessorShigeru Kashihara for theirir}sightful advice. This work is supperted in part by the 21st CeiituryCOE Program "UbiquitousNetworked Media Computing," Graduate School of InformatioRScience,Nara Ii-}stitute of Scienceand 'Ibchnology, Japan, and the Ministryof Edllcation,Sciei}ce, Sports a!idCulture,Japai},Grant-in--Aid forYbimg Sciei}tists, 18700054,2006.. virtual. priva,te. 2). I〈umar, virtual o.4,. 3). A.,. IEEE/71. Rastogi,. private pp.565-578. M.,. algorithm. 4). Iida,. for. programming, tions. R.,. CM. 7hans.. Networking,. A.. Yener,. in the. K.,. Conj12rence. llTEE. G.,. Uth. Sun,. Y.S.. model,. H.,. Vo}.10,. W.. and. neEE. No.5,. Jha,. A}gorithms. CM. Kadebayashi,. Y.. assurance. pp.679-692. for provisioning. [Ibean,s. Netwerking,. and. Yamagucl}i,. service. in. 71eleeomm'unication. pp.311--316. int'g. B.:. ILE]EE/.4. Attstralasian 2007),. Lau,. Proc.. and. threnghpllt. (ATNAC. Rosenbaum,. hose. Koga,. minimum. Proe.. Solutiems,. Silberschatz,. netwerks. (2002).. Shimalmura, ing. Vbl.10, N. S.: Provis,ion-. VPNs. us}ng. Networks. monlinear. and. Appliica-. (2007).. S.: Recent. Directions. Conflerence. on. in Virtual. Networks. Priyate. (ICON. 2009),. Network pp.217-223. (2003). 5). Liu,. Y.L.,. hose-model and 6). D.. 7). 8). M.. Berger,. L.,. RSVP. Byun,, for. Byun,. 11). Lee,. No.1,. C.L.,. 7"7,ans.. Packet 14). a. 15). The. M.:. Iida,. Fair. and. and. Design. Lee,. schemes. in. pp.521-528. Queueing. G.:. hose-. (2004).. Using. pp.375-385. Swailow,. 3209. Deficit. Round. (1996). RSVP--TE:. Extensioi}s. (2001).. M.:. pp.562-571. A. Resource. Management. Proc.. IEEE. Mechanism. lnt7. Co7derence. on. (2006).. Bandwidth. Sharing Network,. Chen,. allocation No.6,. No.3,. Provisioning,. Y.C.:. Services. K.,. Koga,. in. Hose. pp.57-59. Based. VPN,. Proc.. Ist. (20e6).. Weighted. Network,. JacobsoR,. Networks,. H.. Prepertional. IEICE. Fair. fZNbeans. Commun.,. No.12, V.:. to. S.. and. [Zlrtans. Net'work'ing, The. for. pp.3530-3540. Rate. Allo-. Vol.E85-B,. H.:. Vbl.11,. Network. Resource. alloca,tions. No.1,. Simulator. Adaptive. Band-. Netwerks,. Management. V61.3,. Core-stateless. ba,ndwidth. for. MPIjS. IEICE. (2007).. aRd Net'working,. Zhang, fair. S.: Propesal. Centrel. Link-sharing [b7ans.. a,pproximate. Project:. Yamagucl}i,. Feedback. LEEEYACM. I., Shenker,. and. One-Way. Vbl.E90-B,. and. VINT. V.. RFC and. Faii'. Vbl.4,. Generation. Using. Commun.,. Stoica,. 2006,. C.W.. AIIocation. architecture. restorable. Inter7?.et. (2e02). T.,. S.. provisioning. Generation. bandwidth. Efficient. QoS. Differentiated. pp.116-128. Floyd,. K.. VPN. Next. Chen,. in. G.:. IETF. Kim,. Lee, on. Ybkoyama, width. 13). and. Conference. cations. 12). H., based. for. Nent. Vbl.151,. 'lr., Srinivasan,. Network'ing H.. int7. L},. on. fair. Network`ing,. Tuune]s,. Woo,. Medel. Inforn}ation Ie). D.,. LSP. H.,. Hose. ilb7ans.. Ga,n,. for. engineering. Commztnicat]ions,. Varghese,. LEIrEE/ACM. T}'affic Cooferenee. Implementing. IEE. and. M.C.: int'l (2006).. N.:. Proc.. Shreedhar,. to 9). Ansari,. VPN,. Robin,. 2nd. pp.139-146. and. modelled. Chen,. Proc.. Engineering,. Wei,. and. VPNs,. LEEE/ACM. References. networks,. (2002).. pp.33--46 -- ms-2,. No.4,. Mode}s. pp.36t5-386. fair. queueilig:. in. high-$peed. for. (199t5). A. sca,Iable networks,. (2003). http://www.isi.edll/nsnan}/. ns/. 1) Duflield,N.G., Goyal,P.,Greenberg,A.G., Mishra, P.P.,Ramakrishnan, K.K. and vander Merwe, J.E.:Resource manageillentwith hoses:Point-to-cloud servicesfor. IPSJJeumal. VoL 49. No.l2. 3967-3984(Dec. 2008). 16). Katabi, delay. D., product. Handley, networks,. M.. and Proc.. Rehrs, ACM. C.: SIGCOMM. Conge$tion. co}}trol '02,. pp.89-102. for. high. bandwidth-. (2002).. (9 2008 Information Proces$ingSocietyof Japan.

(17) 3983. Hose. Bandwidth. Allocation Method. to Achieve a MTA. Service for PPVPNs. (ReceivedDecember 28, 2007) (AcceptedSeptember 10,2008) (Originalversionof thisarticlecan be found in the Journalof Inforn'iation Pro・cessingVbl.16,pp.201-218.). Hiroyuki Koga received the B.E., M.E. a,ndPh.D. degrees in coiiiputerscience and electronicsfrori)Kyushu Instituteof Technology, Japan, in 1998, 2000, and 2003, respectively.From 2003 to 2004 he was a postdoctoral researcher in the Graduate School of Information Science, Nara Instituteof Science and 'Ilechnology,. Masayoshi Shimamura receivedthe B.E. and M.E. degrees from the Facultyof Engineeringof Chiba InstituteofTechnology, Chiba, Japan, in 2003 and from the Graduate Schoolof Informar rv〈e ・" tionScienceof Nara Institute ofScienceand Technology (NAIST), -'t:tS;I7' `''lli$.. , Nara, Japan, in 2005, respectively. Ft'om April 2005 to March iS' 2007, he was an encouragement researcherin the 21st Century COE Program "UbiquitousNetworked Media Computing" in the Graduate School of Information Science, NAIST. Currently,he isa researcherat the Network Design Research Center of Kyushu Instituteof Technology (KIT). His research interests includeperforrnanceevaluationof networkingsystems.He. Japan. From August 2004 to 2006 he was a researcher in the Kitakyushu JGN2 Resea,rch Center, National Instituteof Infor-. is a member. of IEICE.. Katsuyoshi Iida receivedthe B.E. degree in computer science and systemsengineeringfi'omKyushu Institute ofTechnology (KIT),Iizuka,Japan, in 1996,the A,I.E. degreein informationscience fi'omthe Nara Institute of Scienceand rllechnology (NAIST), '7 Ikoma, Japan, in 1998,and the Ph.D. degreein computer science and systeii)s engineeringfrom KI'I"in 2001. From October 2000, he was an assistantprofessorin the Graduate Schoolof Informa-tion Science, NAIST. Since December 2004,he has been an associateprofessor in the Global Scientific Informationand Cornputing Center,'IbkyoInstituteof 'Ibk Technolog y, yo, Japan. His researchinterests includeperformance evaluation of networking systems,mobile networks,and Internettelephony.He is a member of the WIDE project,IEICE, and IEEE. In 2003, he receivedthe 18th TELECOM System Technology Award from the Tkelecomrnimications Advanceiiient Fbundation, Japan.. ". mation. and. an assistant. Technology, Japan. Since April 2e06, he has been in the Department of InforTnationand ]Nrledia Engineering,. Communications professor. faculty. of Environmental. research. interests. networks,. and. Engineering, University of Kitakyushu, Japa[ri.His include perforrnance evaluation of computer networks, mobile comrnunication protocols. He isa rnember ofthe IEEE and IEICE.. Youki Kadobayashi received the B.E., M.S., and Ph.D. degrees in computer science from Osaka University in 1992, 1994, and 1997, respectively.He is currently an Associate Professor in the Graduate School of Infbrmation Science,NAIST. His research -rgt tf.f,, lt.[ki interestsinclude overlacynetworks and network securityarchitecture.. E;a ,;Kh. IPSJ. Journal. VbL 49. No. 12. 3967-3984(Dec. 2008). @ 2008 Information ProcessingSocietyof Japan.

(18) 3984. Hose. Bandwidth. Allocation. Method. to Achieve. a MTA. Service. for PPVPNs. Suguru Yamaguchi receivedthe M.E. and D.E. degreesin computer sciencefrom Osaka Universityin 1988 and 1991, re spectively.From 1990 to 1992, he was a,nassistantprofessorin the Mucation Center forInformationProcessing,Osaka University.From 1992 to 1993,he was with the InformationTechnology Center,Nara Institute of Scienceand Tbchnology (NAIST), Nara, Japan, as an associateprofessor. From 1993 to 2000,he was with the Graduate School of InfbrmationScience,NAIST, Nara, Japan,as an associate professor.Currently, he isa professor at the Graduate School of Information Science, Nara Instituteof Science and Technology. He has also been a member of the WIDE Project since itsinception in 1988, where he has been conducting research on network security systems for wide area distributed computing environments. His research interestsinclude technologies for inforrnationsharing, inultiinedia communication over high-speed cornmunication channels, network security,and network inanagernent for the Internet.. IPSJ. Journal. Vbl. 49. No. 12. 3967-3984(Dec. 2008). @ 2008 Information ProcessingSocietyof Japan.

(19)

Illustration  of customer‑pipe  and  hose  models.

Illustration of

customer‑pipe and hose models. p.2
Fig.  5 Pselidocode  of  calculation  of bandwidth  al}ocation  at  ingress  routers.
Fig. 5 Pselidocode of calculation of bandwidth al}ocation at ingress routers. p.7
Fig.  13  Impact  of  measurement  time  interval  in ingress  routers  on  allocation  error  rate.
Fig. 13 Impact of measurement time interval in ingress routers on allocation error rate. p.15

参照

関連した話題 :