TELKOM NIKA , Vol.13, No .3, Septembe r 2015, pp. 8 44~850   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v13i3.1799    844      Re cei v ed Ma rch 2 3 , 2015;  Re vised J une  5, 2015; Accepted June 2 0 , 2015   A Congestion Control Algorithm Based on Queuing  Game for Space Information Network       Chao G uo*, Haita o  Xu, Guocai Jia, Zh iy ong Yao  Schoo l of Com puter an d Com m unic a tion En gin eeri ng,  Un iv ersit y  of Sci enc e and T e chno l o g y  Bei jin g,  Beiji ng, 10 00 8 3 , P. R. China   *Corres p o ndi n g  author, e-ma i l : guo9 9ch ao@ 163.com       A b st r a ct  In space infor m ati on n e tw ork, the long de lay an hig h  l i nk error rate  are the most differen t   character i stics  from th e traditi ona l gro u n d  n e t w o rk.  Based o n  the  que ui ng  ga me th eory, a  nove l  co ngesti o n   control is pro p o sed i n  this pa per. It assume s that  the users pay an ad mi ssion fee for e n terin g  the que ue,   and  then  cost  duri ng th e w a it ing ti me, at l a s t  they o b tain  a  be nefit fro m  t he  nod e w h e n   they ar e servic ed   compl e tely. T h i s  pap er not o n l y desi gns  a v a ria b le  ad miss i on fee  in or der  that  the pro p o s ed a l gor ith m  i s   mor e  su itab le  for the sp ace  envir on me nt, but als o  c onsi ders th e e ndi n g  profits  of th e ga me w h ic h  is   descri bed  by a  disco unt rate.  T he si mul a tio n  resu lt  show s the pro pos ed  alg o rith m i m p r ove the  netw o rk   perfor m a n ce.     Ke y w ords :  co ngesti on co ntrol; que ui ng ga me; sp ace  info rmati on n e tw ork; endin g  profit     Copy right  ©  2015 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion    The  sp ace in formation  net work is devel oped  an d fo rmed  on th basi s   of the   grou nd   netwo rk. It co nsi s ts of the  deep  spa c netwo rk,  the  satellite net work, the  aviation network a n d   the traditio nal  gro und  network [1]. Und e r the current  si tuation that e a ch  co unt ry b egin s  to  snat ch   the limited communi catio n s resou r ces over spa c e,  how to utili ze  spa c e inf o rmatio n net work  resou r ces effi ciently ha s be come a fo cu s [2]. Ther efore, whethe r a con g e s tion control sch e m e  is  good  o r  n o t i s  extremely  im portant.  Ho wever, d ue to  t he lo ng  delay  and  the  hig h   link  erro rate  of  the high l a ye r net work in cluding th e d eep  spa c n e twork  and t he satellite n e twork [3], the  traditional  co nge stion cont rol meth od of  the gro und  netwo rk i s  u n suitabl e for t he whole  spa c informatio n n e twork.    In order to solve the  congestion probl em  in the satellite network , there  were some  resea r chers  who  propo se d rea s ona ble  re so urce  all o catio n   sche mes a s  in  [4]. The  auth o rs  adju s ted the traffic spe ed  by changi ng the con g e s tio n  windo w si ze of the node in the network.   These sche m e s were all b a se d on the feedb ack  information of the node s [5, 6]. Although the s e   scheme s   we re able to  ref l ect the  current netwo rk  state, the to o long d e lay  cau s e d  by th e   prop agatio of the inqui ry and feed b a ck info rmati on led th netwo rk  re source wa ste.  Con s id erin g t he glo bal  situ ation of the  n e twork,  a u tho r s i n  [7] built  a ba rgai ning  model  ba sed  on  game the o ry. They ob serv ed and  analy z ed the  ch aracte ri stic  of the network reso urce fro m  the  perspe c tive o f  game theory, which offered a new  ide a  for dealing  with the network  con g e s tio n What’ s  mo re,  autho rs i n  [8 ] formulated   a co mp lex  m a thematical model based on  the sto c ha stic  differential  ga me theo ry. It de scribe d d y namic  ch an ges of n e two r re so urce at any time,  and   obtaine d an  optimal  strategy for  re sou r ce  all o cation throug h solving th e feedb ack  Na sh   equilib rium  of the mo del. It wa built a c cording  to th e re al n e two r k e n viron m en t and  co uld b e   solving, but some oth e model s whi c h were  built in the same way might not exist the   corre s p ondin g  feedba ck Nash e quilib riu m  solution.    In this p ape r, a cong esti on control al gorithm  ba se d on q ueui n g  gam e for  spa c e   informatio n n e twork (CCQ GS). Queui ng  game theo ry  was firstly prese n ted by Naor a s  sho w n  in  [9]. It modeled a que uin g  system  wh ich was b e lo nged to the  eco nomi c  field by combi n ing   queui ng a n d  game th eory. A consta n t  admissio n   f ee wa defined to  re stri ct the a c tion  of  cu stome r whether to j o in  the que ue. In  contra st, we  desi gn a dyn a mic a d mi ssi on fee in stea d of  the con s tant  admissio n  fe e to  ada pt th e real-t im chang es in  sp ace  info rmati on n e two r k.  The  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       A Conge stion  Control Alg o rithm  Based on Queui ng G a m e  for Space Inform ation… (Ch ao Gu o)  845 appli c ation  of  CCQGS  ma ke s the  n e twork  so cial  pro f it rea c he s th e maximu m.  Then  we g e the  optimal que u e  length to achieve the co n gesti o n  co ntrol in spa c e inf o rmatio n net work.   The rest of this  pa pe is  org ani zed a s   fo llo ws. In  se ction  2, the sy stem  model i s   descri bed. Th e desi gn of conge stion  co ntrol  algo rith m unde r the queui ng gam e model is gi ven  in Section  3. The  simulat i on an d com pari s on a r e  done i n  Se ction 5. At l a st, we  drew a  con c lu sio n  in S e ct ion 6.       2. Sy stem  Model  CCQGS is d e sig ned to b a lan c e the space  informa t ion netwo rk  load and  red u ce the   con g e s tion. It dete r mine s the  rule s fo u s ers to  e n ter the  qu eue s o f   the system  node s.  Sin c e   newly arrived  user n eed to wait for the servi c if there a r e oth e r users  in front of him, this  waiting time  cau s e s  an  extra income  when the  serv i c e en ds.  We  descri be it as a discou nt rate  [10] in the followin g  system  model.       i l l 1 2 R i   Figure 1. The  system mod e l of cong esti on co ntrol for  spa c e info rm ation network      In our p r o p o s ed mod e l a s   sho w n i n  Fig u re 1, a  user  ii N  who  wa nts  to enter th space i n form ation net work will obtain t he user’ s  benefit  R  from th e system if t he service is  compl e ted. Howeve r, the u s er  i  need s to  pay an a d mi ssi on fee  i  bef ore joi n ing th e que ue of   the  servi c e n ode. Users a rrive as  Poi s son  di stributi on  with the  a rrival  rate    and the  net wo rk  node se rvice time follo w expon ential  di strib u tion with  the servi c rate   [11]. Whe n  a  user  enters the  qu eue a nd b e fo re bei ng  se rviced, h e  mu st  wait for  a pe riod of time  whi c h forms t he  waiting cost p e r unit time  C The cu rrent numbe r of use r s in the que u e  called the q ueue len g th  are de noted  as  l .   The gai i Gl  of  use r   i  is the criteria fo r de ciding whethe r to join the q ueue o r  n o t. It  is comp uted  by the u s e r ’s  ben efit subtra cti ng th e admi s sion  fee an d th e waitin co st. If  0 i Gl , the use r  will  join the que ue. On the  contra ry, if  0 i Gl , the user will  balk because  there i s  n o  g a i ns eve n  lo sses fo r him.  Notice that th servi c nod anno un ce s th e gain    i Gl  to  the use r   i , it  utilizes the user’ s  benefit  R  which  sho u l d  be obtaine d after servi c e compl e ted.  Therefore, a  discou nt rate   is introdu ce d  in our propo sed syste m  model.   In traditio nal  queui ng  gam e mo del, the   admissio n  fe e is  set a s   con s tant. T h i s  d e fine  is  not suita b le u nder th e spa c e inform ation  netwo rk   environment. We redefine th e a d mission fe e i s   a variabl e asso ciated  with  the queu e length  l . As a result, the admission fe e  of our sy ste m   model is d e n o ted by   i l . Once the no de  can not se rvice the  use r s in the queu e timely, it will  increa se th admissio n  fe e in o r de r to  preve n t too  many u s ers t o  join th e q u eue, an d the n   reduce the possi bilit y of network  congesti on. The rel e vant  parameters in thi s   paper are shown  in  Table 1.   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 3, September 20 15 :  844 – 850   846 Table 1. Spe c ificatio ns of  the paramete r s of CCQGS   Parameters  Meaning    The user’s arrival rate      The node’s service rate     Utilization factor   =   l   The queu e lengt h of service node  R   The user’s benefi t  after service completed  C   The  w a iting cost of the user in the  sy stem p e r unit t i me    The discount rat e       3.  A Con g es tio n  Control Al gorithm Ba s e d on Queui ng Game   The system  welfare con s i s ts of  the   u s er’s  g a in  and  the n ode’ profit mai n ly  from the   admissio n  fe e. Due to the  determin ed  use r ’s  ben efit and the in creasi ng ad mission fee  with  the  increa sing q u eue length, the user’ s  gai n and the no de’s p r ofit are confli cting. Whe n  the qu eue  length g r ows,  the use r ’s g a in de cre a se s. On ce  it is less than  zero, the use r  b a lks the que ue.   Mean while, t he n ode’ profit increa se s. We  a s su me s that  a  user  joins the  que ue at  time  and   c o mplete the s e rvic e at time  1 t . In our  system m ode l, t he system  welfare of u s er  i  ca n be   cal c ulate d  as:     1 1 0 i i t t t i SE R e E C e d t        (1)     Whe r e t e  denot es en ding b e nefits.  After getting the each use r ’s  system  welfare,  the av erag e sy stem   welfare co ntribution  can b e  com p uted as:     1 1 0 0 i i t t t l l Sq E R e E C e d t            (2)     Whe r e l q  denot es the p r oba b ility of observing  l  use r s in t he que ue.   Acco rdi ng to  the  re stri ctio n conditio n   0 i Gl , CCQGS  jud ges a  user can joi n  the   queu e only if  he satisfie s th is conditio n . Our  co nge st i on control alg o rithm i s  an  i n itiative sche me,  so that users are able to  choi ce the fa vorable b eha vior. We turn  this rest rictio n to a thresh old   queu e le ngth  of no de. It is  ea sy for user’ s  di scrimination. T h e u s er’ s   gai n i Gl  can  be   cal c ulate d  as:       1 1 0 i i t t t ii Gl E R e C e d t l        (3)     Becau s e  that  the service  time of the n ode  in  spa c e  informatio netwo rk follo ws t he  expone ntial d i stributio n wit h  a pa ram e te . When a  ne w u s er arrive s to the n ode  and o b serve s   that there h a v e bee l  use r s already i n   the qu eue, th e servi c co mpleted  time   1 t  follows the  Erlang dist rib u tion  with pa rameters  and  1 l . Acco rdin g t o  these a s su mption  we o b t ains the   formulatio n a s   1 1 i t l Ee    (4)     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       A Conge stion  Control Alg o rithm  Based on Queui ng G a m e  for Space Inform ation… (Ch ao Gu o)  847 Whe r Comp uting th e expre ssi on  in (3), we ca n  obtains:       1 l ii CC Gl R E l            (5)     Whe n  the u s er’s  gain  sati sfies  0 i Gl , the re stri ctionexp r e ssi on can be  rewrite a s   follow:      1 0 l i CC RE l            (6)     If the user’ s  g a in not only satisfies  0 i Gl ,  but  also  sat i sf ie 10 i Gl  , this queu length is the t h re shol d den oted as  th l . The con d ition s  are given as:       1 2 0 10 l i l i CC RE l CC RE l                    (7)     Solving the a bove the i n e quality equ ations, th e thre shol d qu eue  l ength th l  is  cal c ulated  as:       1 lo g 2 l o g 1 it h i t h th CC El El l CC RR                 (8)     Whe r th lN The u s e r  firstly come s to  the  spa c e  informatio n n e twork, a nd t hen th servi c nod e   anno un ce s a n  admi s sion  fee to th e u s e r  with th con s ideratio n of th e current  nu mber of u s e r s in   the que ue. T he u s er  cal c u l ates hi s g a in  accord ing to  the re ceived  admissio n  fe e and th e wai t ing  co st. If the user’s  gain i s  n o  less than zero, he  joi n the queu e. Otherwi se h e  b a lks. Du ring t he  discu ssi on of the user’ s  g a in, a thresh old queu e le ngth is ded u c ted for the conge stion co ntrol  scheme fo r space inform ation network. The flow  cha r t of CCQGS i s  dra w  a s  Fig u re 2.   After the threshol d queu e length ha s b een ca l c ul ate d , we get the upper bo und  of the   queu e length.  This re stri cti on is u s ed fo r maximi zin g  the system welfare an d ba lanci ng the lo ad  of the netwo rk. To m a ke  our al gorith m  suit fo spa c e info rmatio n network, we introd uce the  endin g  profit to the gam e model. It descri b e s   th e inform ation  transmissio n  behavio rs  more   suitabl e with  the actu al  situation. Fo si ngle n ode, th e user  com e s an d de cid e s  whethe r to  join  the queue  or  not whic h only deponds  on  his  gain. On the  other word , if the length of the  queue  beyond th l , the user  will bal k. Ho wever,  due to the  ga ins of the join ed use r s are  non-neg ative ,   the system  welfare will stay in a opti m al leve l. At last, the conge stion co n t rol improve  the   perfo rman ce  of the network.    Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 3, September 20 15 :  844 – 850   848    1 1 0 i i t t t ii Gl ER e C e d t l       i     1 lo g 2 l o g 1 it h i t h th CC El El l CC RR                  0 i Gl    1 1 0 0 i i t t t l l Sq E R e E C e d t             Figure 2. The  flow cha r t of CCQGS       4.  Simulation and Comparis ons   In this se ctio n, we give so me simul a tio n s an d analy s is to prove  the co rrectn ess and the  effectivene ss of CCQGS. Firstly,  the influence of the discount ra te   to the thr e sh old que u e   length  th l  is experime n ted. Under t he rest riction conditio n  of  th l , Matlab  is used to cal c ulate the  interrelated  p a ram e ters a n d  sh ow the n u meri cal  re s u lt. It is  helpful for us  to  realiz e the extra  benefit of system from end ing profit of the game.  The n  we ob se rve  the relation ship between t h e   queu e le ngth  and  the  arri val rate.  Use r s in  spa c e  i n formatio n n e twork  co me  with  differe nt  probabilities, for  understanding the impact  to the sy stem, we do t he second ex perim ent. Since  our algo rithm  is ba sed  o n   queui ng  gam e theo ry  whi c is rarely u s ed in   cong est i on  cont rol, it  is  hard  to  com p are  with  othe similar al gorithm. We  ju st do  so me  nu meri cal  simul a tion to  analy s i s   and compa r the results wit h  different pa ramete rs.    On ba sis of the queuin g  game theo ry, we  built the system mod e l and simul a te the   netwo rk e n vironment. The  simulatio n  pa ramete rs a r sho w n in Ta b l e 2.      Table 2. The  value of the simulation pa rameters      R   C   40 60  100  10      In this  simula tion, we  defi ne the  admi s sion fe ll  to sho w n th chang es  of th e   system. Th discou nt rate  is a s sumed  as  0 . 0 1 , 0 .02 , 0.03 , 0 .04 , 0.0 5 , 0 .06 , 0.07 , 0 .08 , 0 . 08 , 0 .1 As sho w n in  Figure 3, with the  incre a se of the discount rate  the threshold q ueue len g th  th l   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       A Conge stion  Control Alg o rithm  Based on Queui ng G a m e  for Space Inform ation… (Ch ao Gu o)  849 decrea s e s . T he  rea s on  i s  that   expre s s the  en ding  profits. Th more  is , the  s m aller the  user’s gain becom e s. Once  the  user’ s  gain  drops,  the new arrival user  will  bal k the queue  with  the restri ctio  0 i Gl . Due to  th lN , we  roun d t he valu e in  the  simulatio n  and  get  the  threshold q u e ue length.         Figure 3. Thresh old qu eue  length for different        As sho w n in  Figure 4, we  can ob serve  the threshol d queue le ng th  th l  grows with the  increa se of the se rvice ra te  . When the servi c e rat e s are the same, the thresh old que u e   length is lo wer with the la rge r  discou nt rate. It means that after use r s joi n  in the queue of  the   node i n   spa c e inform ation  netwo rk, if the nod servi c es the  mo re  use r s pe r u n i t  time, the m o re  netwo rk t r affic can b e  p r o c e s sed in  ou r propo se d model.Th e   th reshold que u e   length den otes  the capa city  of nod e. Th e  high er  it is,  the m o re in formation  ca n be  h andle d  in  the  syst em.  Acco rdi ng to   the qu euin g   game  mod e l, we   can   get the  optim al system welfare  an d avoid  t h e   netwo rk con g e stion.         Figure 4. Thresh old qu eue  length for different          0. 01 0. 0 2 0. 03 0. 04 0. 05 0. 06 0. 07 0. 08 0. 09 0. 1 160 180 200 220 240 260 280 Thr e sh ol d l engt h of  t he queu e l   th     Be f o r e  <f l o o r > A f t e r  < f l oor > 40 45 50 55 60 65 70 75 80 10 0 15 0 20 0 25 0 30 0 35 0 40 0 Thr e shol l eng t h  of   t he queue l   th     =0 .0 1 =0 .0 3 =0 .0 5 =0 .0 7 =0 .0 9 Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 3, September 20 15 :  844 – 850   850 5. Conclu sion   Con s id erin g  the  sp eci a l sp ace inf o rmat io n e twork  enviro n ment, we desi gn a  con g e s tion  control al go rithm CCQ G S to achi eve  the re ason able di strib u tion of net work  resou r ces. O n  the ba sis  of the queui ng theo ry an d the gam e  theory, a system mod e l  is  formulate d  to  redu ce th e p r obability of th e co nge stion  occurrin g. We define  a variable a d missi o n   fee in stead  o f  a  con s tant  one  so  that t he m odel  ca n de scri be th e net wo rk sy stem m o re  real.  Beside s, a di scount rate is introdu ce d to the pr opo sed mod e l to  pre s ent the  e nding  profit o f  the  game. At last, better perfo rmance of the netwo rk i s  ob tained in the  simulatio n s.   In  the  future work, we will do some  rese aches on the  performance  compari s ion between  our alg o rithm  and othe rs a n d  solve the ro uti ng pro b lem  in spa c e info rmation n e twork.       Ackn o w l e dg ements   We  gratefully  ackno w le dg e ano nymou s  re viewers  who  re ad d r afts and  ma de ma ny  helpful su gge stion s Thi s  work  i s  sup port ed  by   the  Nat i onal S c ien c e  Fou ndatio Proje c t of P.  R.   Chin a (612 72 507),   China  Postdo ctoral Scien c e  Fou ndation  (201 3M530 526 ), t he F und ame n tal  Re sea r ch Fu nds for th e Central Universities (FRF-T P-09-015A ).      Referen ces   [1]  F i aschetti A, F i aschetti  M, Pietrab i ssa A,  Petrone M.  Con gestio n  pri c ing for dy na mic  ban dw idth   alloc a tio n  in s a tellit e netw o rks: A game-th eoretic a ppro a c h . Satellite Telec o mmun i cat i ons (EST EL),  201 2 IEEE First AESS Europe an Co nfere n ce . 2012: 1-6.   [2]  Hon g y in g L, Z h imin g Y, Z h i g ang  C. Ma x-Mi n Rate   Co ntrol  on T r affic in Br oad ba nd Mu lti beam S a tel lite  Communications S y stems.  C o mmunic a tio n s  Letters IEEE.   201 3; 17(7): 13 96-1 399.   [3]  Ganga dh ar S, Ngu y e n  T A N,  Umap athi G, Sterbenz JPG.  T C P W e stw ood(+ )  protocol i m p l e m e n tatio n   in ns-3 .  Proce edi ngs of the 6 t h Internatio nal  ICST  Confere n ce on Sim u lat i on T ools and  T e chniques.   Can nes, F r anc e: ICST  (Institute for  Comp ut er Sc i ences, S o cial-I nformatic s  an d T e lecom m unic a tion s   Engi neer in g). 2013: 16 7-1 75.   [4]  T a leb T ,  Kato  N, Nemot o  Y .  REF W A: An Effi cient a nd  F a ir Co ngesti o n  Co ntrol Sc h e me for  LEO  Satell ite Net w o r ks.  Networking, IEEE/ ACM Transactions . 20 06; 14(5): 1 031 -104 4.  [5]  T o rres R, Bord er J, C hoq uett e  G, Jun   X, Je -Hon g J.  C o n g e stion  contr o usin g RE D a n d T C P w i n dow   adj ustment.  MILIT A RY COMMUNICAT ION S CONF ER ENCE, 2012 - MIL C OM 2012. 20 12.   [6]  Utsumi S, Sa li m Z abir SM, S h iratori  N. T C P-C herr y : A  ne w  appr oac h for  T C P congestio n  contro l ov er   satellit e IP netw o rks.  Co mp uter Co mmu n icat ions.  20 08; 31( 10): 254 1-2 561 [7]  Petraki DK, Anastasopoulos  MP, Hsiao-H w a C, Co ttis PG. Distributed Resour ce Allocation for Delay - Sensitiv e Servi c es in Satell ite  Net w o r ks Usi ng Game T heor y .   Co mputati ona l Intelli ge n c e and AI in  Gam e s, IEEE Transactions . 200 9; 1(2): 134 -144.   [8]  Lon g Z ,  Xia n w e i Z .  Joi n t cro ss-la yer  optimi s ed ro utin g a n d  d y n a mic  po w e r a lloc a tio n   in d e e p  sp ace   informati on net w o rks un der pr edicta b le c onta c ts.  Commun ic ations, IET .  2013; 7(5): 41 7-4 29.   [9]  Naor P. T he Regu latio n  of Queue Siz e  b y   Le v y i ng T o lls.  Econo metric.  196 9; 37(1): 15-2 4 .   [10]  Che n  H, F r ank M. State D epe nde nt Pricin g w i t h  a Queu e.  IIE T r ansaction s.  2001; 33( 10) : 847-86 0.  [11]  Yi G, Hua L, Krishn amach a ri  B.  A packet dropp ing- bas ed i n centiv e mech anis m  for M/M/1 que ues w i th  selfish us ers . INFOCOM, 2011 Procee di ngs  IEEE. 2011: 26 87-2 695.       Evaluation Warning : The document was created with Spire.PDF for Python.