TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.4, April 201 4, pp. 2850 ~ 2 8 5 9   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i4.4731          2850     Re cei v ed Se ptem ber 5, 2013; Re vi sed  No vem ber 3,  2013; Accept ed No vem b e r  21, 2013   Performance Evaluation of Dynamic Load Balancing  Algorithms       Tianshu You ,  Wenhui Li, Zhiy i  Fang*,  Hongbin  Wa ng, Guanna n  Qu   Coll eg e of Co mputer Scie nc e and T e chno l o g y , Jili n Univ e r sit y , Cha ngc h un, Chi n a   *Corres p o ndi n g  author, e-ma i l : fangz y@j l u.e du.cn       A b st r a ct   Efficient task sched uli ng  mec han is m can b e tter  meet the  u s ers ’  Q o S req u ire m e n t, and  achi ev e   the loa d  ba la nc ing i n  physic a l  hosts, so the cl uster syst em w i th hig h  scal abi lity and re lia bil i t y can effective l y  improve the inform at ion utili z ation of  the system , thereby enhanc e the ov erall perfor mance of the Web  server cluster  system. In ord e r to buil d  a n e tw ork se rvice system w i th be tter scalabi lity and re lia bil i ty, thi s   paper describes the r ound-robin sc heduling algorithm  of  L VS cluster syst em ,  least-connection scheduling  alg o rith m, w e ighted l east-co nnecti on sch e duli ng a l g o rith m an d a pri o r propos ed ne w   w e ighted v a lu e   assig ned  sche duli ng  al gorith m , dy na mic  ad aptive fe ed bac k loa d  b a la nci ng strate gy. Meanw hi le, it ta k e s   simulati on ex p e ri ment for the roun d-rob i n  schedu lin g al gorith m  of LV S, least-conn e c tion sche dul i n g   alg o rith m, w e ighted  least-co nnecti on sch e duli ng  alg o rith m a nd the  n e w  w e ighted  valu e assi gne d   sched uli ng a l g o rith m, dyna mi c ada ptive fee dback l o a d  ba l anci ng strateg y  and take c o mp arativ e an al ysis   for the exper i m ental d a ta, thro ugh th e an alys is and  a ssess me nt, effectivel y point o u t the  advant ages  a nd  disa dvant ages  of the  existin g  lo ad  ba lanc i ng strate gy. It is co nduc ive  to better i m p r ove the  existi n g   equ ali z at io n al gorith m  p e rfor ma nce d e ficie n c ies  an d pro p o s e opti m u m  l o a d  bal anci ng str a tegy.      Ke y w ords : QoS, load ba la nci ng, LVS cluster  system,  perfor m a n ce a nalys i s , performance  evalu a tio n     Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  With the ra pi d developm e n t of network tec hnol ogy, the appli c atio n of the network  ha s   been  wi dely  popul ar. T h is tren d ma ke s high -spee d I n ternet  service be com e  ve ry po pula r  in   the  worl d of pu bli c  net work  services. Fo r ex ample: Ama z on, Da ngda n g , Jing dong  Mall and T a o bao  e-comme rce  system s, onli ne trai n ticket s b o o k i ng  system, online  p anic buying  system an d ot he r  netwo rk se rv ice s .  These netwo rk services  sometim e s e n co unt er in st ant and rapi d increa sed  visits,  c a us ing  th e en tir e   s y s t e m   s l ow  do wn  or e v e n   w e b s it e cra s h. T o  p r ovide  a la rge  numb e r of  cli ent  requ est s  a n d  better p e rfo r mance, op erators u s e  th e We b  serve r  cl uste r to  solve the  serv er  perfo rman ce  issue s . Expand the serve r ’s ba nd width  through the  load balan ci ng techn o log y ,  increa se the  throug hput of  the syste m , stren g t hen th e network da ta pro c e ssi ng  cap ability, an d   increa se net work flexibility and availabi lity.  Load  balan ci ng technolo g y  make  se rver loa d   a c hi eve a rel a tively balan ce,  thereby  reducing the response ti me of  client request s  ta sk, increasing the ut ilization of sy stem  resou r ces, so  that the performa n ce of the  syste m  ca n be improve d .  A good scheduli ng strategy  can effe ctively solve the probl em of n e twork  co n g e s tion, the ne are s t provid e d  whe n  se rvi c e  need ed to a c hieve l o cati on ind epen d ence; prov id es the  users with better acce ss  qua lity;  improve the  speed  of response f r om t he  server; im prove the  utilizat ion efficiency of  the  server  and othe r re source s; avoid  network’ s  ke y  parts havin g a singl e poi nt failure [1].  Efficient task sche dulin g  mech ani sm s  can  bette r  sa tisfy the u s e r ' s  Q o S  requi rements,  reali z ing the l oad bala n ce betwe en ea ch physical ho st, improving  the overall pe rforma nce of the   Web  serv e r  clu s t e r sy st e m .  Task  sc h edulin g is an  important p a rt of t he cluster  system , it  execute s  thro ugh map p ing  the task o r  tasks  subm itt ed by use r s t o  approp riate  resource s, a nd  its efficiency  will directly af fect  the performance  of the entire  Web  server cluster system  [2-4].  By  usin g load b a l anci ng techn o logy, it effectively im proves the resource ut ilization of  each se rver,  improve the  service avail a b ility of  the system [5].  The next ge neratio n of Internet  servi c e s   might ne ed more hig h -scal ability and hig h - availability system s on the  high-sp eed In ternet a s pe ct. In orde r to p r ovide a mo re  gene ral a nd  a   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Perform a n c e  Evaluatio n of Dynam ic Loa d Balanci ng  Algorithm s (T ianshu You )   2851 variety of ne xt-gene ration  Internet  se rv ice s , we n e e d  to d e velop  a hig h ly scal able  and  reli able   c l us ter s y s t em  [6].   In orde r to a nalyze  and e v aluate the d y namic  lo ad  balan cing  alg o rithm p e rfo r mance of  Web  serve r  clu s te r  syst em, we p e rf orm  seve ral  expe riment s and  me asu r e va riou s l oad   balan cing  al gorithm p e rf orma nce of the clu s te r  sy stem from lo ad bala n ci ng  indicato rs. We  comp ared th e laboratory  prop osed we ighted lea s t con n e c tion sche duling  alg o rithm with t h e   gene ral LVS  (Linux Vi rtual  Server)  clu s ters u s i ng th e  cycle, th e le ast conn ectio n  and  wei ght ed  least conn ecti on sche dulin g algorith m s.   The pa per i s  organi ze d a s  follows: Se ction two d e s cribe s  the d o mesti c  and  foreign  resea r chers’  work o n  the l oad bal an cin g  algo rith m p e rform a n c e a nalysi s ; Secti on thre e of this  pape r  will be  use d  fo r pe rforma nce a n a lysis  of  loa d  bala n ci ng  strategy; Se ction four takes  perfo rman ce  analysi s  for the algo rithm s  decri bed in   section three; Section five is the su mma ry.      2. Related Work  In the  appli c ation e n viron m ent of  We b  se rver   clust e r  system,  fo r the  cli ent's  requ est  task, it is  an  importa nt factor affe cting  t he overall  system’ s  pe rforman c e  on  how th e lo ad  balan ce r opti m um sche du les the load.  Among the  solutio n s of high-pe rf orm ance distri bu ted  load, some   ta ke hardware scheme,   othe rs  take software sche me. No  m a tter wh ich one   to  ta ke,  we have to consi der the fo llowing i s sue s  [1]:  (1) After takin g  the load ba lanci ng sche me, t he spee d of server to  receive a nd transmit   datagram an d the overall  detectio n  ca p ability of  load balan cing a r e  the primary  consi deration s .  (2) T he lo ad  balan cing  scheme  sho u ld  be able to  m eet the growi ng dem and  o f  network   traffic, bal an ce th e l oad   of differe nt o peratin g  syst ems an d h a rdwa re  platforms, a s   well   as  different load  flow.  (3)  Loa d bal anci ng e quip m ent sh ould  have go od  redu nda ncy  solutio n  whe n  failure   happ en s, ensure the availa bility, av oid th e system  suffer a hug e loss.  (4) A flexible , intuitive and safe man a gement  me a s ure is ea sy  to install, configure ,   maintain an d monitor, imp r ove work efficiency an d avoid errors.   At present,  a large n u m ber  of do mestic  an d  foreign  do cu ments  de scribe the   perfo rman ce   evaluation  an d an alysi s  of   load  bala n ci n g  st rategy. In  these  docum ents, they  take   perfo rman ce  analysi s  an d evaluation of  the load  bal a n cin g  algo rith ms and exi s ting algo rithm s ,  measure the  advanta g e s  and  di sadv antage s  of  the al gorith m  on  perfo rm ance, hel p p eople  desi gn better  algorith m  to meet the actu al appli c ation  requi rem ents.   Surde anu  M  and  othe r p e ople [7]  prop ose d   a   kind   of dist ribute d  Q/A sy stem,  usi n g   interqu e stio n parall e lism a nd dynami c  load bala n ci n g  to improve the system’ s  throug hput, a nd  redu ce the p e r so nal p r oble m s’ re sp on se  time.  Mode rn  para llel ad aptive  grid  co mputi ng  simulatio n  ha s va riou s  sizes, Iq ba l S and   Carey GF [8]  studie d  and  compa r ed the  cha r a c teri stics which pe rfo r med  by the d y namic  cha n g e   of the  pro c e s sors’  numb e r  wh en th e  four loa d -b alan cing  alg o rithm s  a r e   having  parall e l  comp utation.   In the docum ents of Koyama K, Shimizu K, Ashihara  H [9],  the authors u s e d  si mulation   method to  comp are an d evaluate  variou s a d a p tive load  balan cing  st rategy in  a c tual   environ ment,  the ada ptive load  bal a n c ing  strategy  has a b e tter loa d  bal an ce, an d bett e r to   improve  the  overall  pe rf orma nce of  the cl uste r  system, and   can  be  re ali z ed  in  pra c ti cal  appli c ation s .   Shan Z, Li n  C, Mari ne scu  DC’ s  docum ents [10] i n trodu ced th e l oad b a lan c in g strategy  about the web se rver cl uster a nd HTTP requ est  content an d prio rity proce s s sche d u ling   mech ani sm. This meth od  can e n sure th e quality of load bala n cin g   and net work  servi c e (QoS).    Yang  J, Ji n  D, Li Y ‘ s   do cume nts [1 1] ta ke  mod e li ng a nd  simul a tion for cl uster-b ased   real  we b serv er, buil d   syst em pe rforma nce  analy s is   model, fo r da ta se nt to server, ea ch  part of  the system  si mulate an d calcul ate the p a cket del ay. Introdu ce th e netwo rk  add ress tran slatio n,  ip  tunnel and  dire ct  ro uting three kin d s of  load bal an ci ng. Del a y as  part of the  in put mod e l of t h e   runni ng  syste m  and  the  sy stem m odel t o  mea s u r e  th e tran smi s sio n  data  pa cke t  in acco rd an ce  with the syste m  and the an alog sy stem perfo rm an ce.  Throu gh the  perfo rman ce  asse ssm ent and   the analy s is  of possibl e p e rform a n c e  b o ttlenecks to  adju s t the sol u tion to the  p r oble m , in o r der   to find the maximum pro c e ssi ng capa cit y  of the system.  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2850 – 2 859   2852 Teo YM, Ayani R’ s  do cuments [12]  use  16  PC and  a d r ive tra c k sim u lator two  experim ent platforms to take cl uster-based web serv er perform a nce and scalability experiment  analysi s . Th rough th e p e rforman c e  an alysis  and   e v aluation it  can be   seen that  rou nd-ro bin  sched uling  al gorithm i s  n o t as  good  a s  the othe r two  algorith m s, th e lea s t-con n e c tion al gorith m   is e a sy to  im plement, a nd  is  suitabl e for high  loa d  situation. Ho we ver,  wi th  the  decrea s e  of l oad,   the lea s t-con nectio n  sch e duling  algo rithm’s  waiting  time is m o re than 2 - 6 time s of the lea s t-l oad   sched uling al gorithm. The  performan ce  of least- loa d  sch eduli ng  algorith m  is the be st, but it  need s the time informatio n of each  requ e s t se rvice.   Dist ri but ed  s e rv er  cl ust e r  sy st e m  i s  a  co st -effective solution  to  provide  scal able  and   reliabl e Internet se rvice. In order  to a c hieve hig h -q u a lity servi c e,  it is ne ce ssary to adju s t the  system  config uration p a ra meters and u s e differe nt algorithm s to improve  syste m  perfo rman ce.       3. Load Bala ncing Stra te gies   After readi ng  and stu d ying  a large  num ber of p e rfo r mance an alysis  articl es, t h is a r ticle  elabo rated th e rou nd-ro bi n sched uling  algorithm, t he lea s t-con nectio n  sche duling al gorit hm,  weig hted le a s t-conn ectio n  sched uling  algorith m  an d a ne w la borato r y pro posed  weig h t ed   distrib u tion sche duling al g o rithm an d dynamic ad ap tive feedback load balan ci ng sche dulin g  algorith m  of  LVS cluste r system.    3.1. Scheduling Algorith m  of LVS Cluster Sy stem  (1)  Rou nd-ro bin sche dulin g algorit h m  (Rou nd-Ro bin  Scheduli ng, rr).   Rou nd-ro bin sched uling al gorithm   is  also known a s   1 : 1 sche duling  algo rithm, when the   load b a lan c e r  re ceives  a  service  re que st from the  cli e nt, it will sen d  the re que st to the ba ck-e nd   real  serve r  t o  pro c e s s in  accordan ce  with 1:1  p r op ortion. In the  reali z ation o f  algorithm,  we  con s id er the  state of the re al  back-end  server to en su re that  the task execute pro perly.  A ssu me t hat   a clu s t e r  sy st em ha s n  se rver nod es S 0 , S 1 , S 2 , …, Sn -1 , k mean s th e ID of  the last task assign ed to the se rvice n o de,  the algorit hm is de scrib ed as follo ws:  Input: the last sele ct task a ssi gne d se rver nod e and t he total serve r  data;   Output: sele ct the server to  be assign ed  task.   Rou nd_ Robi n _ Algorithm (n ode k, Serve r s n).   1. Settings an d initialize variable s  j=k ；   do ：   2. j= （） ； j+1 m od n   3. if （ S j   is alive ）   4. k=j ；   5. return S k ；   6. else nothi n g  to handle ；   7. while （！ ） j = k //if agree return to execute do, not re turn NULL   8. return  NU L L ；   Cod e  De s c rip t ion ：   Rou nd_ Robi n _ Algori h tm(n ode k, Serve r s n)  {        int j= k ;   do {                j= (j+ 1 )mod  n;              if(S j  is alive)                      {                   k = j;                   return S k ;                      }                       els e {                                 }           }while(j! = k )          return NULL;  }  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Perform a n c e  Evaluatio n of Dynam ic Loa d Balanci ng  Algorithm s (T ianshu You )   2853 Rou nd-ro bin  algorith m  is a  simple  sche d u ling  alg o rith m, load bal an cer  sel e ct a  server to  pro c e ss  cu st omers’ requ e s ts in tu rn, so that  only when the b a ck-end  se rv er configuration has   the sa me  co ndition a nd e a ch  user  req uest al most  h a s  t he sa me sy st em re sou r ce s co st ,   it   c an  provide the b e st load b a la ncin g efficien cy.  (2) L e a s t-Con nectio n  Sche duling Algo rithm (Le a st-Co nne ction Sch edulin g, lc).   Lea st-Conn e c tion Sch edu ling Algorith m  assess  th e real -time lo ad statu s  of back-end  serve r   n ode s throug h  the conne ction nu mber re co rde d  on the l oad  balan ce r, del ivering the  ne w  requ est to the  serve r  nod e whi c h ha s the   least numb e r of conne ctio ns to proce ss.  Assu me th at  a cl uste r  syst em ha s  n  se rver no de s S 0 , S 1 , S 2 , ... ... , S n-1 , C (S i ) m ean s  the   numbe r of co nne ction s  of the i se rver  node  now, S m  means th e  serve r  a s sig ned for th e n e w  requ est, and t he lea s t-conn ection  sched uling  algo rith m can be d e scrib ed a s  follows.  Input: the last sele ct task a ssi gne d se rver nod e and t he total serve r  data;   Output: sele ct the server to  be assign ed  task.   Lea st_Conn e c tion_Alg orith m   (nod e m, Servers n)  1. for (trav e r s e serv e r  cl ust e r);   2. Determi ne  wheth e r the  m serve r  wo rks p r op erly; if not, return to  step 1 and m o ve to   the next serv er, if so, conti nue to step 3;   3. for (traverse the se rver cl uster from th e m+1  serve r );  4. find the server with the least conn ecti ons;   5. find the correspon ding  server,  retu rn s S m ;  6. return s NULL if not fi nd the co rrespon ding serve r .  Cod e  De s c rip t ion ：   Lea st_Conn e c tion_Alg orith m (no de m, Servers n)    {       for(m= 0 ;m< n ;m+ + )     {          if(S m  is alive)        {             for(i= m + 1 ;i<n;i++ )                   {         if(C(S i )< C( S m ))            m= i;                      }              return S m ;           }         }      return NULL;  }  Lea st-Conn e c tion algo rith m is a simpl e  dynam ic lo ad balan cin g  algorithm, it can ta ke   con n e c tion  a s  u n it an d  dynamically tra n sfer the   loa d  requ est  wit h  different le ngths to th e  back- end serve r  for pro c e s sing,  when all the  serve r s’  p r o c e ssi ng pe rfo r man c e a r e  similar, it can  be  obtaine d goo d load bal an cing efficien cy.  (3)  Wei ghted  Least - Conn ection S c he duli ng Alg o ri thm (Weight ed Lea st-Co nne ction   Sched uling, wlc)  The  weig hted  least - conn ection sche duli ng al g o rithm   is the i m provement fo r th e lea s t- con n e c tion al gorithm, n o t only con s ide r  t he re al-time  n u mbe r  of co n nectio n s fo r e a ch  se rver, b u t  also  consi d e r  the  pro c e s s  cap a city o f  each se rve r , take  divisi on o peration  for  con n e c tion   numbe r of  ea ch  se rver  and  their p r o c e ssing pe rfor ma nce   which m ean s the l oad  of ea ch  se rver,  and thu s  to  determi ne th e real -time  status of ea ch  serve r , take  the lea s t rat i o of se rvers to   handl e the co nne ction re qu est se nt by clients.   Assu me th at  a cl uste r  syst em h a s n  server n ode s S 0 , S 1 , S 2 , ..... .,  S n-1 , W (S i ) m ean s the   weig ht value  of the i  serve r  no de,  C (S i ) mean s th e n u mbe r  of  con nectio n s  of th e i serve r  n o de  now,  Sm me ans the  serve r  assign ed for the new re qu est.  S m  server me ets the followi ng co ndition s:    (C (S m ) / CS UM) / W (S m )  = min {( C (S i )  / CSUM) / W  (S i )} (i =  0,1,  ...,  n-1)  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2850 – 2 859   2854 W h er e W ( S i ) i s  n o t zero,  be cau s e  in t h is  rou nd l o o k up  CS UM i s  a  con s tant,  so th e  judgme n t con d itions  can b e  simplified a s :  C (S m ) / W (S m ) = min {C  ( S i ) / W (S i )} (i  =  0,1, ..., n-1)    Whe r e W (S i ) is n o t zero, the jud g me nt  con d ition  can  be  cha nge d i nequ ality ope ration to   comp are.    C(S m ) / W ( S m ) > C ( S i ) / W( S i )    As divisi on  compa r ison o peratio n  con s ume   mo re CPU re so ur c e s  than m u ltiplication  comp ari s o n  o peratio n, and  the float point divisi on is  not allowed i n  the Linux kernel,  conn ection  numbe r an d  weighte d  di vision comp arison o per a t ion can  be  conve r ted to  the con n e c tion   numbe r  and   weig hted m u l t iplication  co mpari s o n  o p e ration   to co mpare,  serve r  weight s are   all  greate r  than  zero, so the j udgme n t con d ition ca n be  further o p timized a s  follo w:    C(S m ) × W(S i ) >  C ( S i )× W ( S m )    At the same time ensure that the server has  a weight of zero, the server will  not be  sched uled,  a nd the  weig hted le ast - co nne ction  sch edulin g al gorithm can  be  de scrib ed  as  follows :  Input: the last sele ct task a ssi gne d se rver nod e and t he total serve r  data;   Output: sele ct the server to  be assign ed  task.   Weig hted_ Le ast_ Con n e c tion_Algo r ithm (nod e m, Servers n ) .  1.  for (travers e server c l us ter);  2. determin e  wheth e r the  weig ht value of m  serve r  is above 0,in a nother  way whether it   works p r op erl y ; if not, return to st ep 1  and move to  the next se rver, if so,  cont inue to   step 3;   3. for (traverse the se rver cl uster from th e m+1  serve r );  4. find the server with the least ratio b e twee n co nne ction numbe r a nd wei ght value;  5. find the correspon ding  server, return s S m ;  6. return s NULL if not fi nd the co rrespon ding serve r ;  Cod e  De s c rip t ion:  Weig hted_ Le ast_ Con n e c tion_Algo r ithm (nod e m, Servers n )   {       for(m= 0 ;m< n ;m+ + )     {          if(W(S m )> 0)         {             for(i= m + 1 ;i<n;i++ )                   {          if(C(S m )* W( S i )> C(S i )*W(S m ))               m= i;                      }           return S m ;          }       }   return NULL;   }  Weig hted le a s t-conn ectio n  algo rithm i s  t he mo st effici ent algo rithm  on loa d  b a lan c ing  of  LVS clu s ter system, it not  only con s ide r  the n u mb e r   of real -time  conne ction  of  the serve r , b u t  also th e differen c e  between the  ba ck-e nd  se rv er pro c e s sing  perfo rman ce,  truly reali z e  a   dynamic lo ad  balan cing.     3.2.  A Ne w   Weigh t ed Va lue  Assign e d  Schedulin g Algorithm   In the new  weighted valu e  assigne d sch edulin g algo ri thm [13], we use the  CP U idle rate   and  me mory idle  rate of  b a ck-e nd sub - serve r  whi c h perio dically  a c qui red by  lo ad  bal an cing to   cal c ulate the  weig ht of the  back-end  sub - se rver. Th e weig hted  valu e function ex pre ssi on can be  expre s sed a s :    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Perform a n c e  Evaluatio n of Dynam ic Loa d Balanci ng  Algorithm s (T ianshu You )   2855 F(S i )= 0.6× ( 1 -C ( S i ))+ 0.4× M( S i )                                                                                             (1)    C(S i ), M ( S i ), W(S i )  den ote  the CPU uti lization, mem o ry idle rate  and the  se rver no de  weig ht of the each ba ck-e nd se rver, F(S i ) denote s  the new  weig ht of back-en d serve r  nod e.  After the ne w weig ht cal c ul ation we dete r mine  wh ethe r the n e w  wei ght sh ould  be  written to th e  IPVS schedul ing according to the following formul a:    () ()    () ; () ()    ( ) () . ii i ii i i WS F S B W S WS F S B W S F S                                                             (2)     B is a pre-giv en boun da ry value, the value of  B indicates the algo rithm effective assess  value after the improvem ent of weig h t ed least - con nectio n  sche duling al gorit hm. From th e  formula  abov e it is  not diffi cult to  se e th at the  sm alle r the value  of  B, the high er  freque ncy  of the  weight value to write to IPVS. If the B  value is  0, then every load inf o rmat ion result co llected can   satisfy the bo unda ry value con d ition. Th e load re su lts collecte d  will  also be written to the IPVS  sched uling. If  B =  1, then  the lo ad info rmation  re sult  colle cted  can not satisfy th e bo unda ry v a lue   condition, wit h  IPVS without any change, st ill maintain the original scheduling m ode.     3.3.  D y namic Adap tiv e  F eedba ck Loa d Balancing  Strateg y   A new wei ght ed distri butio n sched uling  algorith m  is p e riodi cally ma king a  requ est by the   load bal an ce r to colle ct the load info rmation of  ba ck-en d  sub-server n ode,  this app roa c h   increa se s the  commu nication overhea d  of the w hol e clu s ter  system, also in crea se s the lo ad  balan ce r’s bu rden.  F eed ba ck dynami c  adaptive  lo ad  balan cin g  st rategy [14] p e riodi cally a n d   adaptively col l ect their  own  load  by the  back-end  se rver nod e, an d se nd the lo ad informatio n to   the loa d  b a la nce r . Thi s   ap proa ch  redu ces th e  comm unication  ove r hea d of th e  wh ole  clu s te r   system, an d also  red u ce s  the burden of  the load bal a n ce r. In ord e r to avoid the instant ove r lo ad  of the l oad  b a lan c er an d  a si ngle  serv er  nod e,  al so  intro d u c e th e serve r   nod e loa d   red u n dan cy  value this pa rameter to furt her optimi z e t he perfo rma n ce of the clu s ter system.   About the  we ight cal c ul ation of the b a c k-en d sub - server,  we u s e se rver  perf o rma n ce  and dyna mic  load value th ese t w o imp o r tant pa ramet e rs  to ma ke more accu rat e   asse ssmen t   of  the cu rre nt lo ad ca pa city of the se rve r  n ode s, we a ssume that the  weig ht value i s  W, the  weig h t   W ab out the  serve r  pe rf orma nce and  dynamic l o ad value s  th ese t w o pa rameters  can  be   cal c ulate d  as  follows:    W(S i )= L( S i )/P ( S i )                                                                                                                                   (3)    P(S i ) is the   performance  indicator of t he se rver, decided by serv er’s CPU utilization,   available di sk sp ace and  memory spa c e. L(S i ) is the dynamic lo ad value of the se rver no de,  deci ded by CPU utilization, disk I/O  read and  wr ite spee d, memory utilization, net work  band width util ization a nd re que st respon se time.       4.  Performa nce An aly s is  and Ev aluation  In the web  se rver  clu s ter  system, it mai n ly us e  effect ive mea s ure i ndicators of  server to  analyze an d  evaluate  whether it i s  good  or  b ad the  clu s ter  system’ s  load b a lan c ing  perfo rman ce.  These effective measu r e  indicators  [1 ] mainly incl ude  CPU util ization, me m o ry  usa ge, ban d w idth utilizati on, disk IO throu ghp ut an d netwo rk IO  through put, the numbe r  o f   compl e ted service p e r u n it time, the numbe r  of con n e c ted cl ients pe r uni t time, and the  respon se tim e  to complete  a task reque st.  This arti cle  fo cu se s o n   a n e w  wei ghted   value a s sign ed  sched ulin g alg o rithm,   dynamic  adaptive  fee dba ck strat e gy  and roun d-robin sche du ling  algo rithm of LVS cluster sy stem , the  least-co nne ct ion sched ulin g algorithm a nd weig hted  least-co nne ct ion sched ulin g algorithm f o r   perfo rman ce analysi s   an d evaluation.  Compa r e  an d  analyze the a d vantage s an d disa dvanta ges  of existing a l gorithm s in  orde r to better im prove and optimi z e  the algorith m . In Choi E’s  pape r ， in  ord e r to  analy z e  the dynami cs of serve r  p e rforman c e  du e  to the  wo rklo ad, the  autho rs  perfo rm seve ral expe rime nts. With  so me kn owl edg e of ho w to  sele ct the p r oper  pe rform ance  cou n ters  and  their prope r  threshold  val ue, they   com pare  the  pe rforma nce  results of t he AL BM   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2850 – 2 859   2856 clu s ter with  the g ene ral  L VS clu s ter u s ing  RR,  LC a nd  WL C  sche duling  algo rit h ms. T he A L BM  clu s ter a c hie v es the better pe rform a n c e than the  LVS by balancin g the lo ads am ong t he  serve r s. It also has ve rified  and an alyze d  that  among  roun d-robi n sched uling al gorithm of LV S   clu s ter sy ste m , least-con n e ction  sched uling al go rith m and wei ght ed lea s t-conn ection  sched uling  algorith m , we ighted lea s t-conne ct ion  scheduli ng alg o r ithm ha s bet ter pe rform a n c e in the th re e  algorith m s [6] .   Here we ta ke simulatio n   experim ent for the ne w weighted valu e  assi gne d scheduli n g   algorith m  ,dynamic  ada ptive feedba ck  load b a la n c in g strate gy an d wei ghted l east-co nne cti on  sched uling al gorithm  on t he re que st resp on se  tim e , and ta ke  comp arative analysi s  for t he  experim ental  data. Labo ratory  expe ri ments we re done unde r  l o cal enviro n m ent,  use r   a c cess   client  uses WAS (Micro soft We b A ppli c a t ion Stre ss T ool) to  si mula te the u s e r  p r essure. Divid e d   to 7 expe rim ental g r ou ps,  set th e first  grou p a c ce ss numb e r  of u s ers to  10 0, the  se cond  g r oup  acce ss count  is 20 0, an d  set   30 0,400 ,500,600,7 0 0  re sp ectively  in  ord e r. E a ch  g r ou p ta ke  simulatio n  te sts  with wei g hted lea s t-co nne ction sch edulin g algo ri thm , a new  weig hted val u e   assign ed sch edulin g algo ri thm and dyna mic ada pt ive feedba ck loa d  balan cing  strategy [13].    0 100 200 300 400 500 60 0 700 0 1000 2000 3000 4000 5000 6000 TT FB  Av g( ms ) The  numb er o f co nnect ion  A n ovel  weig ht v alue  Dyn amic  adap tive  feed back  wlc   Figure 1. Re spon se Time  Comp ari s o n  of the Two Algorithm s    0 1 00 20 0 3 0 0 40 0 5 0 0 60 0 7 0 0 0 200 400 600 800 1000 1200 1400 1600 1800 2000 T TFB A vg(m s) t he  num ber  o f c onn ect ion  wl c  dy na mic  ad apt iv e f eed bac k   Figure 2. Re spon se Time  Comp ari s o n  of the Two Algorithm s      We can cle a rly see tha t  from Figure 1,  when the numb e r  of user requ est task  con n e c tion s is less than  230, the average  wait  re spo n se time of the impro v ed algorith m  is  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Perform a n c e  Evaluatio n of Dynam ic Loa d Balanci ng  Algorithm s (T ianshu You )   2857 slightly longe r than which o f  the wlc algo rithm.  The m a in rea s o n  for this phe nom enon i s  that the  improved algorithm  has  a new  weight  c a lc ulat ion and IPVS write proces s ,  that c o nsumes a  certai n  amou nt of time.  Whe n  the  n u m ber of ta sk co nne ction  i s  g r e a ter tha n  23 0,  with t h e   increa se n u m ber of the  re q u ire ta sk  co n nectio n ,  the a v erage  wait  resp on se time  of the improved   algorith m  sig n ificantly less than th at of wlc  al go rithm. No m a tter the  wlc  al gorithm, o r  the   improve d  alg o rithm, with the increa se  numbe r  of task  requ est  conne ction, when it rea c he s a   certai n number, the  whol e clus ter sy stem will reach the satu ration. Because the resource   utilization  of each server  cluster  system is al ready saturated.  When  this occurs,  we should  con s id er th e  clu s ter sy ste m  to b e  exp a nded,  addi ng   a ce rtain am ount  of ba ck-end real  serv ers  to  in c r ea se  ava ila b l e  se r v er  r e s o ur ce s .   From th e ave r age  wait re spon se  req u e s t time   comp arison  of u s e r  reque st in   Figure 2,  we  can  see t hat when th e  numbe r of  user  requ est s  i s  less tha n  2 4 0 , the ave r ag e wait re sp on se  time of the i m prove d  alg o rithm i s   slig htly l onge r th an  whi c h of  the wl c al go rithm. The m a in   rea s on fo r th is ph enom en on is th at the improv ed a l gorithm  ha s  weig ht value  cal c ulatio n  and  IPVS write process, this proces s consumes a  cert ain amount of  time. When t he user request  numbe r is g r eater tha n  24 0, with the in cre a se num b e r of the u s e r  req u e s ts, d y namic a dapt ive   feedba ck lo ad bal an cin g  strategy resp ond s fa ster than th e wei ghted  least - conne ction   sched uling  al gorithm, dyn a mic  adaptiv e feedb ack l oad b a lan c in g strategy is more  effecti v ely  enha nce the  throug hput  of the syste m , and bette r  bala n ce th e system lo a d , can effe ctively  improve the p e rform a n c e o f   the whole cl uster  system.   In the following we mai n ly take com pari s on a nal ysis for a n e w weighted  value   assignm ent sched uling   al gorithm, dyn a mic ada ptiv e feed ba ck  strategy  and  wei ghted  le ast- con n e c tion scheduli ng algo rithm from th e respon se ti me and sy ste m  throug hput  aspe cts.       Figure 3. Not e  Ho w the Ca pti on is Cente r ed in the Col u mn       As can b e  se en from Figu re 3, when the  numbe r of user’  requ est conne ction is  not big,  a  ne w weig hted  all o catio n  sched uling al gorithm  an d  dynamic ad a p tive feedb ack lo ad  balan cing  strategy hav e longe r re spon se time for user s’ re q uest than th e weig hted l east-co nne cti o n   sched uling al gorithm, the  main re ason  is the form e r   two algo rithm s  incre a se th e burden of the  load sch edul er when  cal c ulate the wei ghts val ue,  write and  rea d  the weig ht value s , and lo ad   balan cing  assign tasks,  cau s ing a ddition al comm uni cation overhea d, cost  some  resou r ces. Wi th  the increa sin g  numbe r of acce ss  requ e s ts conn ectio n s of the cu rrent use r s, th e new  weig hted   assign ed  sch edulin g algo rithm and dy namic  ada ptive feedba ck load bal an ci ng strategy  are  sup e rio r  to  th e weighte d  le ast-con n e c tio n  sch eduli ng  algorith m  o n   perfo rman ce.  In a ddition, i t   can  also be  seen from the  diagr am that  the dynami c   adaptive fe e d back lo ad b a l anci ng  strate gy  has lea s t  re spon se tim e , i t  mean s th at dynami c   ad aptive feed ba ck st rategy  i s  su pe rior to t he  new  weig hted  distributio n sche duling al g o rithm on p e rforman c e.   0 100 200 300 400 500 60 0 700 0 200 400 600 800 1000 1200 1400 1600 Byte s Recv Rate (Kb/s) th e  nu mb er  o f  co nn ec tio n  a  n ov el  w ei gh t  va lu e  d yn am ic  a da pt iv e  fe ed ba ck  w lc Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  2850 – 2 859   2858 0 100 200 300 400 500 600 7 0 0 0 200 400 600 800 1 000 1 200 1 400 1 600 Byt es  Recv  Rat e(Kb /s) th e n umb er  of  con ne cti on  a  nov el  wei gh t v alu e  dy nam ic  ada pt ive  fe edb ack  wl c   Figure 4. Not e  Ho w the Ca pti on is Cente r ed in the Col u mn       For dyna mic  page s, we  can se e from  t he above di agra m , whe n  the numbe r of use r   acce ss  req u e st conn ecti ons i s  le ss t han 2 00,  the  throug hput  of a ne w we ighted a s sig ned  sched uling al gorithm and dynamic  ada ptive feedba ck loa d  bal an cing poli c y is  slightly le ss t han  whi c h of the  weig hted le ast-con n e c tio n  sche du lin g  algorith m , mainly due  to the first two   algorith m s in cre a se the b u rde n  of the  load sch edul er in the p r o c e ss of  weig ht calculation ,  the  weig ht write,  weight  rea d  and the t a sk a ssi gnm ent of load  balan ce r, ca usin g additio nal   comm uni cati on overhea d ,  spent  som e  re sou r ce s.Whe n   u s er acce ss req u e st  conn ecti on   rea c he s abo ut 400, th e t h rou ghp ut of  the sy st em  reache s the   maximum. O v erall the  dy namic  adaptive feed back lo ad bal anci ng  strate gy has th e m a ximum thro u ghput. It mea n s the  dynam ic  adaptive fee dba ck  strate gy is su peri o r to  the n e w weighte d  sch eduli n g  algorithm  on  perfo rman ce.   In summ ary, throu gh the  compa r ative a nalysi s    of th e three  algo ri thms o n  pe rforma nce,  dynamic  ada ptive feedba ck lo ad b a la ncin g strateg y  has bette r perfo rman ce than the  new  weig hted a s sign ed sch e duling al gorit hm and rou nd-robi n sch edulin g algo rithm of the LVS  clu s ter  syste m , the lea s t-co nne ction  sched u ling a l gorithm  and  weig hted l east-co nne cti o n   sched uling al gorithm.       5. Conclusio n   This p ape r an alyzed the p e r forma n ce an alysis of the d o mesti c  and f o reig n do cum ent on  the clu s ter  sy stem loa d  bal anci ng alg o rit h m, its main  purp o se is to  resea r ch and  desi gn a b e tter  perfo rman ce  of the load balanci ng a l gorithm,  whi c h ma ke s the cluste r sy stem with hi gh  scalability an d reliability, and can effectively  impro v e the utilization and pe rforma nce of the  system  information. Th ro ugh th e d e scriptio n,  an al ysis  and  ev aluation  of a  ne w  weig hted   distrib u tion  sche duling  al gorithm, dyn a mic  adapt iv e feedb ack l oad b a lan c in g strategy a nd  roun d-robi n  sche duling  alg o rithm  of LV S clu s ter  syst em,  lea s t-con nectio n  sch e duling algo rit h m  and  weig hted  least - conn ection sche duli ng alg o rith m   on pe rforman c e. Fin a lly th e con c lusi on  is  that dynami c  ada ptive fee dba ck loa d  b a lan c in g  st rat egy ha s bett e r  perfo rma n c e. T h ro ugh  t h e   analysi s  a nd  evaluation  of the pe rf orma nce  of the loa d  bala n ci ng  st rategy of the  clu s ter  syste m ,  whi c h  can  effectively point  out the a d van t ages  and  di sadvantag es  o f  the existing  load b a lan c in g  strategy, is  condu cive to  better imp r ov e the def ici e ncie s of the  existing eq ua lization al gori t h m   and propo se  optimum pe rforma nc e load  balan cing  strategy.      Ackn o w l e dg ements   This research is  su pport ed by  China Jilin Province  Natural  Science  Funds under  prog ram of  parall e lization  and dynam ic sche du lin g model of CPU/GP U coope rative hi gh   perfo rman ce comp uting  cl uster (20 121 5189 ).  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Perform a n c e  Evaluatio n of Dynam ic Loa d Balanci ng  Algorithm s (T ianshu You )   2859 Referen ces   [1]  Xu  Lan. L oad  b a la ncin g techn o lo g y  r e searc h .  Agriculture&T e chn o lo gy.  200 9; 29: 155- 157.   [2]  Sun H, C h u n g uan g T .  Optimi zing M u lti-a g e n t  MicroGrid Re source Sc he du ling  b y  C o -Evol u tion ar y  w i t h   Preferenc e.  T E LKOMNIKA Indon esia n Jour nal  of Electric al  Engin eeri n g . 2 013; 11( 12): 72 22-7 229.   [3]  Jian g W ,  Z han g J, Li J, et al.  A Resourc e  S c hed uli ng Strat e g y  i n  Cl oud  Comp uting B a sed o n  Multi- age nt Genetic  Algorit hm.  T E LKOMNIKA Indones ian J our n a l of  El ectrical  Engi ne erin g . 201 3; 11( 11 ) :   656 3-65 69.   [4]  Quan B, L i  H,  Le Z .  D y nam ic  Routi ng a nd  R e sourc e  Assig n ment Al gorit h m  In sloted  opt ical N e t w orks.   T E LKOMNIKA Indon esi an Jou r nal of Electric al Eng i ne eri n g .  2013; 1 1 (4): 1 813- 182 1.   [5]  ZHU Jia y u,  XI AO, Dan, WANG Fei. Multi-di m ensi ona l Qo S constrai ne d  sched uli ng m e chan ism bas ed   on lo ad b a la nci ng for Clo ud co mputin g.  Co mp uter Engi ne erin g and Ap pl icati ons . 201 2.   [6]  Choi E. Perfor mance test an d ana l y sis for  an  ada ptive l oad b a l anci n g  mechan ism o n  distrib u te d   server cluster s y stems.  F u ture  Generatio n Co mp uter Syste m s . 2004; 20: 23 7-24 7.  [7]  Surdeanu M,  Moldovan DI,  Ha ra bag iu SM.  Performa nce  ana l y sis  of a  d i stribute d  q ues tion/ans w e ri n g   sy s t e m .  IEEE Transactions on Parallel and  Distribut ed Sys t em s . 20 02; 13 : 579-59 6.  [8]  Iqbal  S, Car e y  GF . Performan c e a nal ys is of   d y nam ic l oad   bal anci n g  al go rithms  w i th  vari abl e n u mb er   of processors.  Journ a l of par a llel a nd d i strib u t ed co mputi n g .  2005; 6 5 : 934- 948.    [9]  Koy a ma K, Shimizu K, As hihara H,  et al.   Per f orma nce  ev al uatio n  of ad apt ive l o a d   bal anc ing  po lici e s   in distributed s ystem s.  Proc e edi ngs of IEE E  Sing ap ore I n ter nati o n a l C onfere n ce  on.  IEEE. 1993; 2:   606- 611.   [10]  Shan Z ,  Li n C,  Marinesc u  D C . Mode lin g a nd p e rf ormanc e an al ysis  of QoS-a w ar e lo a d  ba lanc in g o f   w e b-server clusters.  Comp ute r  Netw orks . 2002; 40: 23 5-25 6.  [11]  Yang J, Ji n D,  Li Y. Mod e li ng  and s i mul a tio n  of performa nc e an al ysis for  a cluster- base d   w e b server .   Simulati on Mo dell i n g  Practice  and T heory . 2 006; 14: 1 88-2 00.   [12]  T eo YM, Ay a n i  R. Compar iso n  of loa d  b a la n c ing strate gies  on clust e r-bas ed  w e b serv ers.  Sim u lation .  200 1; 77: 185- 195.   [13]  W ang Ho ng bi n, F ang Z h i y i,   Qu Guanna n, Z hang  Xi Z h ang, Yu nchu n. A novel  w e ig ht distributi o n   sched uli ng a l g o rithm.  Journ a l  of Informatio n and C o mput ati ona l Scienc e . 201 1; 8: 1235- 124 4.  [14]  W ang H o n gbi n, F ang Z h i y i,  Cui S h u ang.  D y namic  ad ap tive feed back  of loa d  b a l anc ing strate g y .   Journ a l of Infor m ati on a nd C o mp utatio nal Sc ienc e . 201 1; 8: 1901- 19 08.   [15]  W ang Ho ng bi n. Rese arch o n  ad aptive  lo a d  bal anc ing s c hed uli ng strat e g y  in W e b s e rver cluste r   s y stem. Jili n U n iversit y . 20 13.       Evaluation Warning : The document was created with Spire.PDF for Python.