(i2) United States Patent
`Keshav et ah
`
`(54) DYNAMICALLY MODIFYING THE
`RESOURCES OF A VIRTUAL SERVER
`
`(75)
`
`Inventors: Srinivasan Keshav, Mountain View,
`CA (US), Rosen Sharnm, Mountmn
`View, CA (US); Shaw Chnang,
`Mountain View, ('.A (US)
`
`(73) Assignee. Ensim Corpnration, Sunnyvale, CA
`(US)
`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`USU06985937BI
`
`(10) Patent ]k[0.:
`(4s) Date of Patent:
`
`US 6&985&937 B1
`Jan. 10,2006
`
`5 636371 A
`5.692,047 A
`5,7&k&,t)9)7 A
`5.706,453 A
`5,7)hk774 A
`5,719,854 A
`5 727 2&)3 A
`5,7-18,614 A
`
`Yu ......... 39:i&5&)0
`McManis ................... 3804
`Schelling ct al ...... 358&296
`Chang et al.
`Hcden
`Choudhury et al....... 370,&231
`Hapnm et al
`SVa lime re r
`
`f&,'1')9?
`11 199?
`1,'1')98
`1 1998
`1,'1')98
`2 1998
`3,'1')98
`5 1998
`
`(Continued)
`I'ORL'IUN VAFLNF DO('UML'NTS
`
`( &
`
`) Notice.
`
`Sub)act to any disclaimer, the term of this
`patent is ex&ended or adjusted under 3S
`U S C IS4(b) by 0 clays
`
`.) V
`
`64-002141
`
`*
`
`1/1989
`
`(Continued)
`
`(21) Appl. No.. 09/569,371
`
`(22)
`
`Filed:
`
`May 11, 2000
`
`(Sl)
`
`Int. CI.
`(106F 15/173
`(200().01)
`(52) U.S. CI...................
`709/223, 709&?24; 709 226,
`709/238; 370/231; 370&23S; 718/I OS; 714/3S
`lrield of Classificatinn Search ........ 709,223—226,
`709&229, 238, 370?31, 232, 235 —236; 379,'Ill,
`714/3S; 718/I OS
`See application file for complete search history
`
`(58)
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`Plummer, D C, An Eriierner Address
`Re&&&iunr»i
`1'rr&r»c»/~ri~n»&o ernrig hieoi ork 1'rr&coco/ A dd ress e& ri&
`) si on on Erh eruct Hard-
`48 bi r Erher»ca Address for Transmi
`ware, Nov. 1982, [online], [rctricved on Jan. 17, 2000].
`Retneved lrom the Interne«. URL msg ne)A&adow,'an-
`swers/extras/rfcirfc826.txt&.
`
`(Continued)
`
`1'rimary Exammer Wensthi I.in
`I enwick a West I.I.V
`r&r iirni
`(74) An»met, Agenr,
`ABSTRACT
`
`(57)
`
`A system aml a method dynamically ad)usus the quality of
`service guarantees for virtual servers based upon the
`resource demands experienced by the virtual servers Virtual
`server resource denials are monitored to determine if a
`virtual scrvcr is ovcrloadcd based upon thc rcsourcc denials.
`arc modifie dynamically to
`scrvcr
`Virtual
`rcsourccs
`respond to thc changing rcsourcc rcquircmcnts of each
`virtual server. Occamonally, 6 physical host housing a virtual
`server mav not have ad&htional resources to anoca&e to a
`virtual server requiring increased resources In this instance,
`a virtual server busted by the overloaded physical host is
`transfcrrcd to another physical host &vith sufficicnt rcsourccs.
`
`4 CLaim(, 7 Drawing Sheets
`
`3,377,f&24 A
`4,1?7,510 A
`5,)89,667 A
`5,212,7')3 A
`5,226,16&) A
`5,249,2')0 A
`5,263,147 A
`5325,530 A
`5,437,&)32 A
`5528,753 A
`5,:172,68&) A
`558-1,023 A
`50&)3,&)2&) A
`5 r&23,492 A
`
`4&1968
`12&1979
`2/1993
`5&199)
`7/1993
`9»1993
`H /1993
`6&199)4
`7/1995
`&81996
`H /1996
`12&199f&
`2/1997
`4&199)7
`
`Nelson et al.
`Appall et al................ 364/200
`1'saki ct al.
`Donica et al.
`Waldron et al
`Heir«i
`I'rancisco ef af
`Mchrmann
`Wolf et al
`Fortin
`1kcda ct al.
`Hsu
`Hashimoto ct al....
`Teraslinna
`
`...
`
`3')5/425
`
`3')5/616
`
`Google Exhibit 1063
`Google v. VirtaMove
`
`

`

`US 6,985,937 Bl
`Page 2
`
`U S. VAI'L'N'I'O('.UML&N'I'S
`
`f&,57S,B»3 BI
`f&,580,72) Bi
`G,6-17,422 B2
`G,658,&71 Bl
`6.691,312 Bl
`6.725,45C& Bl
`f&,7f&0,773 B I
`6,820,1)7 Bi
`2003/00G1338 Al
`
`f&,'2003
`f&,'2003
`11 2003
`12 2003
`2 2004
`F2004
`7,'2004
`1 I,'20()4
`3 2003
`
`Hutchison ct al
`Beshai
`Suesinger et al.
`O'rien et al
`Sen e& al.
`Bruno e& al.
`Ancrousis ct al.
`.)ohnson
`SteB&ga
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`
`WO '&9 39261
`
`8/1 999
`
`OTHER PUBLICATIONS
`Huang, X W. et al, ''I'he LN'I'RAVH) Protocol Develop-
`'99, Mar.
`ment Environment," Proceedings oflEEE lnfoconi
`1999, mne pages.
`Du)iield, N.G., et al., "A Ficxibk Mode( for Rcsourcc
`Management &n Virtual Pnvate Networks,'vmpnier Com-
`mriniearivri Review Cvriference, Comparer Cvmmmiicanr&n,
`ACM SIGCOMM '99 Conference, Cambndge, MA, Aug.
`199&). pp 95-10S.
`30 1999-Sep 3
`Campbell, A. T, and Kcshav, S, "Quality of Scrvicc in
`Distributed Systems,'* Comparer Cvnmiumcanans 21, 1998,
`pp 291-293.
`Bach, M. J., The Design vf )he Un)a& Opera/ing Sysiem,
`Ncw Delhi, Prentice-Hail of India, 1989, ppv-x, 19-37.
`McDougaii, R., et ai., Resvuce Managemen), Upper Saddle
`lbver, NJ, Prentice HaH, 1999, pp iii-xix, 135-191.
`R&)singhani, A., RFC 1624, May 1994, [online], [retrieved
`I'eb 2, 2000]. retrieved from the internet &URI. faqs org/
`rfcu,'rfc1624.htmf&.
`Mallory, I'nd Kullberg, A., Rl ( 1141, .Ian. 1990 [online],
`[rctncvcd Fcb. 2, 2000]. rctricvcd from thc intcmct: &URL:
`faqs org/rfcs/rfc1141.html&.
`Egcvang, K. and Francis P., RFC 1631, May 1994 [online],
`[retneved Feb. 2, 2000]. retr&eved from the Internet. &URL.
`faqs org rfcs&rfcf (&31.htmf&.
`Keshav, S., An Lngi nearing Approach )v Cvmpuier
`Nenvvrking 8'I'M Nenvvrks, the Internet. and )he ?e)ep/ivne
`Nenvork, Reading, MA, Add&son-Wesley, 1997, pp vi&-x&,
`SS-115 20&)-3SS 39&-444
`Stcvcns, R. W., UNIX Neniork Programmirig io).
`I
`Nenvvrking 4 Pls" Siockers and X7'I, Upper Saddle River, N I,
`Prcnticc Hall, 199S, pp v-xiv, 29-53, 85-110, 727-760.
`Tanenbaum, A. S. and Woodhuii, A. S., Opera(ing Sys&ems.
`Design and lmplemenrarion, Upper Saddk R&vcr, NJ,
`Prenuce Hall, 1997, pp vu-xiv, 1-46, 401-454.
`l./NUX Device Driiers, Sebastopol, CA,
`Rubim, A.,
`O'Reiliy 8& Amoc&ates, Inc., 1998, pp v-x, 13-40.
`Goyal, V., et ai, "A Iiierarchical
`('VU Scheduler
`for
`Multimedia Opcratin Systems,"Pmceedings of rhe Second
`hiivnpvsinm vn ()peratmg 5/ysre&ns Demgn and lniplei ienra-
`rion* ]OSDI'96'), Scattk, WA, Oct. 1996, 13 pages.
`Laune, B. and Laurie, P., Apache The Defmi/iae Un/de,
`Sebastopol, CA, O'Reilly g& Associates, Inc, I'eh 1999, pp
`v-viii, 43-74.
`Aho,A. V, and Uiiman J. D.,Prmciples of Comp(ier Desigri,
`Reading, MA, 1977, pp vii-x, 359-362, 519-522.
`Jonsoon, J., "Expionn ~
`ihe Importance of Preprocessing
`Operations in Real-T&me Mull&processor ScheduhngT Pro«
`(lu IEL'E Rea/-Time Jys/em* Sympv&inm—Wvrki&i-
`v/
`/'rogi&ss .session, San I'rave(6&m, CA, Dec. 4, 1997, pp
`31-34.
`
`Hart
`Wahbe e& al............ 395/406 A
`Templin e& al.............. 370/401
`()osslcr c& al .....
`703/2(
`('oopcr ct al......
`7( i/133
`Weid et al.................. 395'800
`Ozkan
`Domenikos «i al.... 395/200.49
`Schnurer et al............. 3i)5 500
`Wendo&l't al............. 39&/72C&
`Germs&khi et al.
`I'owlow et al.
`Boebert et al.
`Hauser «& al.
`Adams
`Iwasaki e& al.
`Yang e& al
`G&een et al................. 39&/18C&
`
`M&skow&ec
`
`Bare
`
`Roved ......... 3')5/186
`................. 709'223
`()oodeium ct al.. 3')5,'200.55
`Vahalia ct al .....
`709)/225
`Mevers et al.......... 395'187.01
`Welsh ct al......
`3')5/186
`
`......
`
`709)/201
`
`713/200
`
`.....
`
`7(i/173
`
`Stockton
`Ho(I e& al.
`Y&n et al.
`Srinivasan
`Tomoike
`Yin et al.
`('unnnings
`.lain et al.
`('oilc ct al
`Bull et al.
`('hiussi ct al
`Bugnion et al........ 395/500.48
`Ran
`Adelman et al.
`Brooms ct al.
`Alden et al.
`Orcutt ct al
`Basak et al.
`Win e& al.
`..................... 713'200
`Touboul
`Moo&e e& al.
`Ault et al................... 709'101
`Chess ..........................
`717&5
`Rope&da et al............. 709'229
`Opalka et al.
`Mcl)evitt ct al.
`H ut et al.
`('hcssin ct al
`Yu ............................. 709/238
`I'is hler et al
`Pneto, Jr. et al.
`Primak ct al
`Massarani
`Hcrzog ct al.
`A&ken, J&. et al.
`Rocpclc, .)i.
`Chow et al.
`WU
`Blumenau et al.
`Rhee e& al.
`O&r et al.
`Zargham e& al.
`.)aisimha et al
`Collins et al.
`
`l)cianov ct al....
`0 ulet e& al.
`
`710/260
`
`AAA A A AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
`
`5&1998
`6&199S
`7&199S
`8/1998
`9/1998
`10,'1998
`11)1998
`11&199)8
`11)1998
`12&199)8
`12,'19&&8
`1&199)9
`1&1999
`»1999
`3/1999
`4&199&9
`5/1999
`6&19&)9
`6/1999
`&»'1999
`6/1999
`7&1999
`8/1999
`8&1999
`9/1999
`10&1999
`11&199)9
`11&1999
`11&199)9
`1&2000
`1,'200&)
`2/20i)0
`4&2000
`5/2000
`5&2000
`6/2000
`6,'200&)
`6/2000
`f»'2000
`7/20i)0
`8&2000
`8/2000
`9&2000
`12&2000
`12&2000
`2&2001
`Bl
`2&2001
`2&2001
`Bl '&2001
`7&2001
`7/20iu
`Bl
`Bl
`7&2001
`Bt
`10/2001
`Bl ','2002
`-I/2002
`Bl
`Bl
`4&2002
`5/2002
`Bl
`Bl
`5&2002
`7/2002
`Bl
`Bl
`8&2002
`8/2002
`Bl
`Bl
`8&2002
`8,'2002
`9&2002
`9&2002
`10,'2002
`10,'2002
`11/2002
`12,'2002
`3/2003
`4&2003
`
`Bl
`
`Bl
`Bl
`Bl
`Bl
`B 1 "
`B 1
`
`5 752 003
`5,761,477
`5,781,550
`5,799,173
`5,809 «27
`5,S28,893
`5.S38,f&86
`5,838,916
`5.S42,002
`5,84&,129
`S,S50,399
`5,860,004
`5,S6-1,f&83
`5,889,956
`5,859,99f&
`5,892,9C&8
`5,905,730
`5,913,024
`5,915,()85
`5 915,095
`s 918 018
`5.920,f&99
`5,933,603
`5 937,159
`5,956.481
`5 961,583
`5,9?S,373
`5,982,7-18
`5,9&) 1,812
`6,01f&,318
`6,01S,S27
`6,023.721
`6,047,325
`6,061 349
`6,065,118
`6,075,79 &
`6,0?&,938
`6,078,929
`6,078,957
`6,(hSC&,623
`r&,iBL543
`6,I(5,759
`6,122,f&73
`6,161,139
`6,167,520
`6,189,046
`6,192,389
`6,H)2,512
`6,230,203
`6,259,6')9
`6,266,678
`6,269,404
`6,298,479
`6,351,775
`6B70 «83
`6381.228
`6BS9,448
`63&)3.484
`6,425)X)3
`6,430,f&22
`6,434,742
`6,438,134
`6,442,164
`6,449,f&52
`6,457,008
`6 463,459
`6,4?0,3')8
`6,487,663
`6;190,670
`6,:129,985
`6,&42,167
`
`

`

`US 6,9]]5,937 Bl
`Page 3
`
`Rusling, D. A, Processes, [online], [retrieved on Dec 7,
`1999]. Rctricvcd from thc Internet: &URL: ccbaf.gov/-saw/
`linuxitlk-html nodc44 html&.
`Rusling, D A., Linux Processes, [onhne], [retrieved on Dec.
`1999]. Retneved from the
`Internet: &URL.cebaf.
`7,
`gov —saw,'linuxitlk-htmL'node4S.html&.
`Rusling, D. A, Identifiers, [online], [retrieved on Dec 7,
`1999]. Retrieved from the Internet &URI. cebaf.gov&-saw/
`linuxitlk-html nodc46 html&.
`Rusling, D. A., Scheduling, [online], [rctricvcd on Dcc. 7,
`1999]. Retneved from the Internet. &URL. cebaf.gov —saw&
`linux/tlk-html,'node47 html&.
`Rusling, D. A., Scheduhng in Multiprocessor Systems,
`[online], [retrieved on Dec 7, 19&fi)]. Retrieved from the
`&URI. cebaf gnv/-saw linux/tlk-html/node48
`Internet
`html&.
`Rusling, D. A., Files, [online], [rctricvcd on Dcc. 7, 1999].
`Retrieved from the Internet: &URL: cebaf gov,' saw,'linuxi
`tlk-htmL'node49.html&.
`Goyal, P. et al., "Start-time Fair Queuing: A Scheduhn ~
`Integrated Services Packet Sivitching
`Algorithm for
`Networks,'* Proceedings nf ACM SI(ICOMM *96, San
`Francisco, ('.A, Aug. 1996, 14 pages.
`Janosi, T., "Notes on 'A Hierarchical CPU Schedular for
`Mulnme&ha Operaung Syinems'y Pawan Goyal, Xin an ~
`Guo and Harnck Vin," [onhne], [re&waved on May 8, 2000].
`Retrieved from the Internet &URL. httpuhcs.cornell edu,i
`Info,'Courses/Spring-97/('S614/goy html&.
`Goyal, V, "Packet Scheduling, Algorithms for Integrated
`Scrviccs Networks," PhD Dissertation, University of Texas,
`Austin, TX, Aug. 1997.
`Pending United States patent application cntitlcd "Providin
`Quahty of Service Guarantees to Virtual Hosts," U.S. Appl.
`No. 09!452,286, iiling date Nov. 30, 1999.
`Vending United States patent application entitled "Selective
`Interception of System Calls,*'
`S Appl No. 09&499,098,
`filing date Fcb. 4, 2000.
`Pending United States patent application cntitlcd "Dynamic
`Scheduling of Task Streams in a Multiple-Rcsourcc System
`to Ensure Task Stream Quahiy of Service," U.S. Appl No.
`09 498,450, lihng date Feb. 4, 2000.
`entitled
`States
`Vending Umted
`patent
`application
`"Disambiguating I'ile Descriptors,*'.S. Appl No 09/5(t(L
`212, filing date Fcb. 8, 2000.
`Pending United States patent application cntitlcd "Rcstrict-
`in Communication Bctwccn Network Dcviccs on a (lom-
`mon Network,'* U.S. Appl No. 09,'502,155, lilin ~ date Feb.
`11, 2000.
`Vending United States patent applicatinn entitled "Restrict-
`ing Communication of Selected Processes to a Set of
`Specific Network Addrcsscs,'* U.S. Appl. No. 09/503,975,
`filing date Fcb. 14, 2000
`Pending United States patent application cntitlcd "Enabhn
`a Service Provider to Provide Intrans& Services,'.S. Appl.
`No. 09!526,980, iiling date Mar. IS, 2000.
`
`Boehm, B, "Managing Software Productivity and Reuse,'*
`IEEE Computer, voL 32, No. 9, Sep. 1999, 3 pages.
`Corbato, I'I et al. "An Lixperimental I'imesharing System,'*
`Procccdings of the American Fcdcration Of Information
`Processing Societies Spring Joint ('omputer ('onference,
`San Francisco, CA, May 1-3, 1962, pp 333-344.
`Deutsch, P. and Grant, C.A., "A Flexible Measurement Tool
`for Software Systems," Information Processing 71 (Proc. of
`the IFIP Congress), 1971, pp. 320-326.
`Edtlah, G., et al., "History-based Access Control for Mobile
`Code,*'ifth A('M ('onference on ('omputer and Com-
`munication Security, Nov S-S, 1998, (9 pages
`Erin saon, U. and Schncidcr, F. B., "SASI Enforccmcnt of
`Sccunty Policies; A Rctrospcctivc," Proc. Ncw Security
`Para&hgms Worl shop, Apr. 2, 1999, pp 1-17.
`Erhngsson, U. and Schnieder, F. B., IRM Enforcement of
`Java Stacl Inspection, [online], Feb. 19, 2000 [retrieved on
`Apr 2, 2002] Retrieved from the Internet: &URI. http pc&-
`tres.cornell.edu Dienst U12.0/Show
`Page/ncstrl cornell/
`TR2000-1786&.
`Evans, D. and Twyman, A., "Flexible Policy-Dircctcd Code
`Safety,'roc. of. 1999 IEEE Symposium on Security and
`Pnvacy, Oakland, ('A, May 9-12, 1999, pp. 1-14.
`Fraser, T. et al., "Hardening CUTS Software with Generic
`Software Wrappers,*'roc of 199') ILL'L'ymposium on
`Secunty and Privacy,
`f 999,
`I S pages.
`Goldberg, I. et al., "A Sccurc Environment For Untrustcd
`Hclpcr Applications (Confining the Wily Hacker)," Proc. of
`the Sixth USENIX UNIX Security Symposium, San Jose,
`Ca, Jul 1996, 14 pages.
`Goklberg, R. P., "Survey of Virtual Machine Research,"
`IL'L'L'omputer,.lun f974, pp 34-4S
`Vandey, R. and llashii, 0, "Providing I me-Gramed Access
`Control For Mobile Programs Through Binary
`Editing,'cchnicalRcport TR98 (6, University of California, Davis,
`
`CA, 1998, pp 1-22.
`Ritchie, D. M., "The Evolunon of the Unix Time-Sharing
`System," ATh'&T Bell Laboratories Technical Journal 63, No.
`I')84, (originally presented I')79), 11 pages
`(i, Vert 2, Oct
`Saltzer, J., H and Schroeder, M D, The Protection of
`Information in Computer Systems, [online], 1973, [rctricvcd
`on Apr. 2, 2002]. Retricvcd from thc Intcmct: &URL:
`cs.virginia.edu —evans!c&551/sa(tzer,'&.
`Wahbe, R., et ai, "Elbe&en& Software-Based Fault Isoalnon,'*
`Proc. of the Sympomum on Operating System Principles,
`1993, 14 pages.
`Goy al, Vawan et al, (ienera/ized (iaaranreed Ra!e 6/chedai-
`/ng A!got/rhmiz 4 Framework, IEEE&ACM Transactions,
`vol. 5, Issue: 4, Aug. 1997; pp. S61-571.
`Mitra, Debasis et aL, "Hierarchical Virtual Paruuonm
`Algorithms lor Virtual Private Networking,'ell Labs
`Technical Journal, Spnng, 1997, http:,'/cm.bell-labs.corn&
`cm/ms who/mitra,'papers,'globe.ps.
`" cited bv examiner
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jan. 10,2006
`Jan. 10, 2006
`
`Sheet 1 of 7
`Sheet 1 of 7
`
`US 6,985,937 B1
`US 6,985,937 B1
`
`roe es er aw ee es ee eee es
`
`
`UQHEIO|jESDUNOSEl%OZ
`
`UONBIO}/]EBiNOSadYOE
`
`UONESOI|eeouNOsal%OL
`
`UOHEIOIEsoINOSesOL
`
`UGNBIO}}EBUNOSBIYO}
`
`UONHBooESosnose!%O9
`
`UONEIOIJESONOS)%GL
`
`
`9291JBAIOSJENA
`
`
`VZ9LJaAlIasJENA
`
`
`acestJBAIBSJENA
`
`
`AZO:SOASJENA
`
`zgJanesJENUIA
`
`4279,0JOAJaSJENA
`
`AZJanes[ENA
`909}OY[IISA
`
`Gog}is0yjea1shud
`
`YO9LyOujes1shyg
`
`
`
`Jaijipowsasnose.JOPWUOWBDJINOSOJ
`
`
`
`JeNwIAoIUeUAGpeo]soyjeosAud
`
`
`
`J@AIOSJEMWIAJOAIOSJENA
`
`
`
`~“A=.GoTsinpowuaneinbgugsomnoseyameuag
`
`
`
`
`
`
`
`li
`
`OchOLL
`
`
`
`
`
`JOAOLUJAAIOSJaquejeq
`
`OrtOl
`
`Lainbig
`
`ene
`
`ofl
`
`wajshs
`
`OSt
`
`ce eee eee eee
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 10,2006
`
`Sheet 2 of 7
`
`US 6,985,937 B1
`
`Figure 2A
`
`

`

`U.S. Patent
`
`Jan. 1(),2006
`
`Sheet 3 of 7
`
`US 6,985,937 B1
`
`Monitor virtual server
`resource denials
`210
`
`Decrease virtual server
`resource allocation
`246
`
`No
`
`Is virtual
`server resource
`overloaded?
`220
`
`Yes
`
`Yes
`
`Select a new physical host
`to accomodate (increased)
`virtual server
`250
`
`Move (increased) virtual
`server to selected new
`physical host
`260
`
`Move virtual server users to
`new virtual server location
`270
`
`Figure 2B
`
`

`

`U.S. Patent
`
`Jan. 10l 2006
`
`Sheet 4 of 7
`
`US 6,985,937 B1
`
`Q C
`Ch0 «D C!
`ch QQ «D Itp
`ca0IL 'C
`O g0
`
`ap
`
`CI
`CD«I'
`
`0I
`
`h
`ID
`
`CD
`ID
`
`PC
`
`Ch
`ID
`
`Eat
`
`Q QO
`Qt0 'ch
`QCOO
`Q CI
`
`Z 0
`
`«p
`ID
`ID
`
`PC
`ID
`th
`ta
`
`CD'Cl
`
`'ClQOC Ct
`Ih Mal pp
`
`ID
`
`I c K
`— 0 co Cv
`
`mQ
`
`t
`
`'C
`0
`
`Rp
`
`hl
`Q C
`O CD
`Ch0Ih ap
`
`CD Q
`Ia
`
`Q0
`
`ch
`
`C
`
`0 CoCl
`I/I
`Q Pp
`
`ID
`ID
`Cl
`ICal
`th
`ta
`l
`
`Ea
`
`C
`
`0 «CC CI
`thQ
`
`cal
`al
`tp
`al
`Ih
`ftl
`
`EI
`
`D
`
`Z
`
`0
`
`0Z
`
`0Z
`
`Q
`CL EO ah
`
`ta
`D QC0Ct
`CLO
`
`EC
`
`ca/t Q I«!
`Q th hp
`ClE cC. '
`IL Q cOc QtSQ
`
`ca
`
`alC. c
`al '5
`C D O
`Q oah
`Q Cho pp
`
`Z
`
`QBO
`
`tD'al
`
`at
`o m
`mc ahO
`0 ca
`5 al
`'z
`
`Ch
`
`h«c c
`Q '5
`/E Q CD
`ID OCI
`ta hh
`g, o DP
`ERQ ah
`
`al
`
`I.:
`
`4 Q
`8 @CDth
`
`Ia
`
`ca
`
`Ca
`
`ID tD
`
`& C/P
`
`C
`Q. c«0
`ta
`
`I/I
`
`m I
`
`D tao «P
`Ih EO tc
`
`ID
`
`ta
`ID IDC
`«D Zt CD
`~ atA
`cho
`
`ap m/hCO Q
`
`C0
`I
`
`000 C
`
`D0
`0th
`a!
`
`I 2Q C
`
`D
`
`

`

`U.S. Patent
`
`Jan. 10,2006
`
`Sheet 5 of 7
`
`US 6,985,937 B1
`
`Figure 4
`
`

`

`U.S. Patent
`
`Jan. 10,2006
`
`Sheet 6 of 7
`
`US 6,985,937 B1
`
`Signal from Virtual
`Server Resource
`Modifier 120
`
`Signal to Dynamic
`Virtual Server
`Mover t40
`
`Periodic Physical Host
`Resource Check
`545
`
`Figure 5
`
`

`

`U.S. Patent
`
`Jan. 10,2006
`
`Sheet 7 of 7
`
`US 6,985,937 B1
`
`Signal received
`
`Dynamic Virtual
`Server Mover
`140
`
`Figure 6
`
`

`

`US 6,985
`
`,987 Bl
`
`1
`DYNAMICALLY MODIlrYING THL
`RFSOURCFS OF A VIRTUAl. SFRVFR
`
`CROSS RLI'L'RLNCL''0 RL'I.ATLD
`APPLICATIONS
`
`This applicanon is related to U.S. paleni Ser. No. Or) 4r)r),
`0r)g, entitled "Selective Inlercepnon oi. Syslem Calls,'y
`Horislav D. Deianov et al., filed I'eb 4, 2000, now U S Pat
`No (h54(hS4(i and commonly assigned with the present
`application 'I'he subject matter of this related application is
`incorporated by rcfi:rcncc hcrcin in its cntircty.
`
`33A('K('ROUND
`
`of resources, correspomhn ~ to either a lixed percentage of
`the capacity of a particular physical host (for example, the
`operating system may be instructed to allocate twenty per-
`cent of the central processin unit cycles to proces~ A anil
`two percent to process B) or a tixcd number of units (for
`cxamplc, thc operating system may bc instructed to allocate
`X cycles per seconil to process A and Y cycles per second lo
`process B). However, customers may be unable to anucipate
`the exact amount of resources they will require, and a static
`assignment of a particular resource allocation limit may not
`allow the virtual server system to adapt to changing cus-
`tomer tlccris.
`Instead of requirin customers to sclcct a static lcvcl of
`resources, a better resource allocation model is slruclured
`along the hnes of. elecnicily pncing—a customer receives
`what he needs, and he pays for ivhat he receives. Referring
`hack to a previous example, small customer 13 may initially
`request a very low level of resources I lowever, should his
`ncw home l&usincss suddenly expand, hc may quickly bump
`up against thc limit of thc scrvcr rcsourccs hc originally
`requested. In Ibis case, it would be preferable if customer
`B's virlual server resources were able to automatically,
`dynamically adjust to his increased resource needs
`I'hus it is desirable to provide a system and method for a
`virtual server capable of providing quality of service guar-
`antccs for a customer, which is also capable of ad)usting thc
`quality of scrvicc based upon changing customer demand. It
`is ilesirable Rir such a system lo dynamically ad)us) the
`physical host resources allocated to a virtual server.
`
`SUMMARY OF THE INVENTION
`
`The present invention dynamically ad)usus Ihe quahty of
`service guarantees for virtual servers based upon the
`resource demands experienced by the virtual servers Virtual
`servers having individual quality of service guarantees are
`lhstributed among a group of physical hosts. Each physical
`host's rcsourccs arc allocated among thc physical host's
`resiilenl virtual servers. The resources allocated lo a par-
`ncular virtual server may be dynamically ruljusted in
`response lo changing virtual server resource needs.
`Occasionallv, a physical host executing a virtual server
`may not have additional resources to allocate to a virtual
`scrvcr requiring incrcascd rcsourccs.
`In this instance, a
`virtual server hostcd by thc overloadcrl physical host
`is
`transfcrrcd to another physical host ivith sufficicnt rcsourccs.
`In one embodiment, a dynamic resource coniiguration
`moilule monitors resource denials received by virtual servers
`and determines if a virtual server is overloaded based upon
`the resource denials A resource demal may refer to any
`rcqucst by the virtual scrvcr that cannot bc immcdiatcly
`serviced, such as a denial of a rcqucst to crcatc a fil or a
`network packet delay. If thc rcsourcc denials rcccivcd by a
`parncular virtual server exceed a pre-speciiied limit,
`the
`virtual server is considered overloaded and a request is made
`for additional resources
`Thc resource usa c of the physical hosts within thc
`system ts monitored. A load-balancing iuncnon is peri ormed
`to sekcl the appropnale physical host when a virtual server
`transfer becomes necessary. A virtual server is transferred
`between physical hosts ivith minimal impact upon the opera-
`tion of the virtual server
`The features and advantages descnbed in the specilication
`are nol all-inclusive, anil parucularly, many addiuonal fea-
`tures anti advantages wdl be apparent to one oi ordinary skill
`in the art in view of the drawings, spemhcation, anil claims
`hereof Moreover, it should be noterl that the language userl
`
`is
`
`zn
`
`in
`
`an
`
`1. Field of Invention
`Thc prcscnt invention rclatcs generally to rcsourcc allo-
`cation for a virtual server, and more parhcularly, lo moni-
`toring and dynamically modifying lhe resource allocation
`for a virtual server based upon usage.
`2 Background of the Invention
`Netivorked computer resources are growing more popular
`as thc benefits of shanng computing rcsourccs become
`evident. Onc of thc fastest-grov ing sc ments of thc Inicrnct
`is the network market Network systems contain common
`elements, generally including a dedicated local server to
`mamtain the shared network data, and a communrcatrons
`system for providing data communication services between
`devices on the network Data communications services and
`scrvcrs arc not easy to configure, manage, and maintain.
`Thus, thcrc is an inccntivc for Intcrnct Scrvicc Providcrs
`(ISPs) to provide such network services and servers, thereby
`relieving corporanons of Ihe burden of providing these
`services directly
`is not economically feasible for an ISP to remotely ss
`It
`mana e servers located on a customer*s premises, and
`support many diifcrcnt customers in this fashion. Rather, an
`ISP would prcfcr to ofibr network scrviccs to multiple
`customers while keeping all of the server host computers
`within a central location of Ihe ISP for ease of management.
`Accorriingly, ISPs typically dedicate one or more physical
`host computers as each individual customer's server(s), and
`maintain each host computer in the centralired facihty 'I'his
`means thc ISP will have to own and maintain potentially
`large numbers of physical host computers, at least onc for 4-
`each customer's scrvcr or private network. Howcvcr, most
`customers will neither require nor be amenable to paying for
`the user of an enure host computer. Generally, only a
`fraction of
`storage, and other
`the processing power,
`resources of a host computer will be required to meet the sn
`needs of an individual customer.
`Diilerent customers have ihlferenl virtual server needs.
`For example, a company Aproviding large quantities of data
`and information to its employees anil customers will want to
`ensure that its virtual servers are always available to perform ss
`a large number of tasks. Company A may bc willing to pay
`a premium for a guarantccd high quality of scrvicc, with
`large amounts of processin ~
`high server availabihty anti
`power always on-call. By contrast, a small inihviilual B who
`merely uses his virtual server i or back-up lile storage space
`has very different quality of service requirements ('ustomer
`H needs (and wishes to pay for) only a limited amount of
`storage space to bc available on an intcrmittcnt basis
`VVhen servicing the needs of multiple cusuimers bavin ~
`dilferent needs, it is desirable lo provide a virtual server that
`is dynamic, not static,
`in its allocation of resources A
`customer's virtual server is typically assigned a fixed level
`
`ss
`
`

`

`US 6,985,937 Bl
`
`in the specilicauon has been pnncipally selected for read-
`ability and instructional purposes, anil may not have been
`selected to dehneate or circumscribe the inventive suliject
`matter, resort to the claims tieing necessary to determine
`such invcntivc subject matter.
`HRIEI'L'S('RIP'11ON Ol'l IL DRAWINGS
`
`10
`
`FIG. 1 is an illustration of a system for dynanucally
`modifying thc resources of a virtual scrvcr.
`flowchart of a process for dynamically
`FIG. 2A is a
`modifying the resources of a virtual server.
`FIG. ZB is 6 flowchart of another process for dynamically
`modifying the resources of a virtual server
`I'IG 3 is a block diagram of a prncess for determming 16
`whcthcr an indivirlual rcsourcc in a virtual scrvcr has
`rcachcd its limit.
`FIG. 4 is a flowchart of a process for determming when
`to increase or decrease a virtual server resource allocation.
`FIG. 5 is a block diagram of one process lor performin ~
`resource load balancing among physical hosts
`I'IG 6 is a flowchart of one process for transfernng a
`virtual scrvcr from onc physical host to another physical
`host.
`The figures depict a preferred embodiment of the present
`invention for purposes of illustration only. One skrfled in the
`art will readily recognize from Ihe lollowmg discussion that
`alternative embodiments of the structures and methods illus-
`trated herein may be employed without departing from the
`principles of the invention dcscribcd herein.
`
`10
`
`tc
`
`DL''AII.L'D DLS('RIV'11ON
`OI'1IL'RL'ILRRL'D LMBODIML'N'I'S
`Reference will now be made in detail Io several embodi- zs
`ments of the present
`invention, examples of which are
`illustrated in the accompanymg draivings Wherever practi-
`cable, the same reference numbers will lie used throughout
`the drawings to rcfcr to thc same or like parts. The term
`"virtual scrvcr" as used hcrcin refers to a virtual scrvcr 60
`capable of receiving a quality of service guarantcc from a
`physical host. Muluple virtual servers may reiude in a srngle
`physical host, and ihlferent virtual servers on the same
`physical host may receive different quality of service guar-
`antee
`FIG. I shoivs an cmborlimcnt of a system for dynamic
`servers. A ilynamic
`resource conligurauon in viruial
`resource conliguration module 1UU is coupled via a network
`to a group of physical host machines 160 (160A, 1600 and
`160('), or may be resident on any of these hosts 160 The 60
`physical host machines 160 may bc any kind of computer
`adapted to support virtual scrvcrs. Thc module 100 may be
`implcmcntcd in a software rlrivcr. It is to bc undcrstoorl that
`the dynamic resource conligurauon module 1UO wrll typi-
`cally support more than one physical host machme 160.
`in one embodiment, the dynamic resource txtn-
`Iloivever,
`figuration mndule 100 may support a single physical host
`160.
`The group of physical hosls 16U contains a group of
`virtual servers 162 Physical host 160A contains virtual
`servers 162A and 1620, physical host 1600 contains virtual
`servers 162(:, 162D anil 162L; and physical host
`
`e.
`
`160('ontainsvirtual scrvcrs 162F and 162G.
`
`In one embodiment, each individual virtual server 16Z has
`a dillerent quality of service guarantee. Dilferent quality of 66
`service guarantees are implemented by allocating different
`amounts of the resources nf each physical host machine 160
`
`to servicing each of the virtual servers 162. Physical host
`160 resources may be allocated as percentages of the
`resources of a particular physical host 160, or as a particular
`number of units within a physical host 160 (for example, the
`opcratin system may bc instructed to allocate X cycles pcr
`second to process A anti Y cycles pcr scconrl to process B).
`In Ihe embodiment shown in FIG 1, physical host 160
`resources are allocateil to inrhvidual virtual servers 162 as
`percentages of each physical host 160 'I'able I
`lists the
`resource allocations of each virtual server 162 as shown in
`I'IG I
`
`TABI.L'
`
`Vtt
`
`IS
`
`rit o
`
`Au
`
`iwut
`
`IrI(
`
`V rtual Se te
`
`Resource Allo si ou
`
`161A
`16" B
`I 6" I
`'6"Ii
`16" I
`16zp
`16ZO
`
`16; of phystcal host 160A
`6(!; of phystcal host 160A
`
`I ot phys cat hosi 160C
`(i
`!(i I of phys cat hosi 160C
`
`I'he virtual servers 162 each may consume a difFerent
`amount of thc rcsourccs of thc physical host machines 160.
`Thc rcsourccs of a physical host machine comprise the sct of
`luncnons and features Ihe physical host machine uses in
`implemennng tasks lor each virtual server. Examples of
`resources include disk space, memory, netivork capacity anil
`processing cycles ((:VU resources) As shown in I'IG I,
`virtual server 162A consumes IS% of the physical hnst
`IS% of physical host
`160A rcsourccs. This means that
`160A's disk space, memory, network banrlwidth, and GPU
`procesinng will be dedicated to servicing the needs of virtual
`server 162A. A variety of other types of physical host
`resources wdl be evident to one of skill in the art.
`A resource allocation for a virtual server is specilied as a
`"quality of service guarantee'* for that particular server. Lrach
`physical host stores quality of service guarantccs for thc
`virtual scrvcrs it hosts. As a physical host performs pro-
`cesses associated with a particular virtual server, the physi-
`cal host accesses Ihe stored quality ol service inl orms non to
`enabk the phvsical host to request the correct quality of
`system kernel of the physical
`service from the operatin
`host
`One implcmcntation for storing quahty of scrvicc guar-
`antcc information is a quality of scrvicc paramctcr table. A
`quality of service parameter table in each physical host 160
`associales each virtual server 162 resident in the parucular
`physical host 160 with quality of service parameters. These
`parameters are used to allocate physical host 160 resources
`for each resident virtual server 162 I or example, physical
`host 160A includes a quality of scrvicc parameter table,
`which lists rcsidcnt virtual servers 162A and 162B. Thc
`parameter table lisls whatever virtual servers are residenl in
`the physical host. As virtual server resource allocations are
`changed, aml as virtual servers are Iranslerred between
`physical hosts, the corresponding quahty of service param-
`eter tables are updated to reflect these changes and transfers
`In another cmbodimcnt, a single master quality of scrvicc
`paramctcr table can coordinate multiple slave tables asso-
`ciaterl with each physical host.
`Dynamic resource configurauon module 100 includes a
`virtual server resource monitor 110, a virtual server resource
`modiher 120, a physical host load balancer 130, a dynamic
`virtual server mover 140, and a file system 150 In one
`
`

`

`US 6,985,987 Bl
`
`these modules are poruons of the software
`embodiment,
`code implementing the dynamic resnurce conhguration
`module 100 The dynamic resnurce configuration module
`100 is further communicatively coupled to each physical
`host 160.
`Thc virtual scrvcr resource monitor 110 monitors the
`resource usage of the virtual servers 162 to date rmme
`if they
`are overloaded. The virtual server resource modifier 12U
`dynamically moihlies the resource allocauons of the virtual
`servers 162 on an as-needed basis 'I'he physical host load-
`balancer 130 periodically monitors the resource usage of the
`physical hosts 160, and uses thc dynamic virtual scrvcr
`mover 140 to transfer virtual scrvcrs 162 bctwccn physical
`hosts 160 as nccrlcd to balance thc loads of thc physical
`hosts 160. The lile system 150 is used for stonng state
`information associated with a parucular virtual server 162
`when transferring the particular virtual server 162 to a
`ditferent physical host 160 In another embodiment, the hie
`system 150 is not uscrl, and state information is copicrl
`directly from onc physical host to another physical host to in
`transfer a virtual scrvcr.
`FIG. ZA w a Ilowchart of an embodiment of the overall
`process lor dynamically modiiying the resources of a virtual
`server. Virtual server resource demals are momtoreil 210.
`Resource monitoring is performed using the selective inter-
`ceptinn of system calls One embodiment of selectively
`intcrccpting system calls is disclosed in thc rclatcrl applica-
`tion, thc sutilcct matter of which is incorporated hcrcin by
`reference. Each resource (e.g., dwl space, memory, network
`baiulwirith, or CPU cycles) used by a virtual server is
`monitoreil to determine the time at which the resource is
`the pnint at which a request for more
`fully used, that is,
`resources is either implicitly or explicitly denied Examples
`of rcsourcc denials include a memory allocation rcqucst
`denial and a network packet rlclay signal.
`A di,termination is made 220 as to ivhcthcr a particular
`virtual server resource is overloaded. The number of times
`a particular resource denial is received in a time window is
`avera ed using one of a number of well-I nown techniques
`If the average number of denials is beynnrl a pre-configured 30
`threshold, the virtual server is determined 220 to be over-
`loaded for the corresponding resource. If thc virtual scrvcr
`is not dctcrmincd to bc ovcrloadcd, thc mcthorl continues to
`monitor Z1U virtual server resource denials.
`If. Ihe virtual server is determined to be o