T E L KO M NI K A ,  V o l. 1 4 ,  N o. 3 S ept em ber   20 1 6 ,  pp.   11 42 ~ 114 9   I S S N :  1 693 - 6 930 ac c r edi t ed  A   b D IK T I,  D e c r e e  N o 58/ D I K T I / K ep/ 2013   D O I :   10. 12928/ T E LK O M N I K A . v 1 4 i 3 . 3648      11 42       R ec ei v ed   M ar c h   2 9 ,  201 6 ;  R ev i s ed  May  1 7 ,  2 01 6 ;  A c c ept e J une   5 ,  201 6   F lo w  F air  S am p lin g  Ba sed   o n  M u lt is t ag Blo o m  F ilt er       L i u  Y u a n z h e n * H u a n g  S h u r o n g L i u  J i a n z h a o   Y anc heng  I ns t i t ut e of  T ec hno l ogy Y a nc heng   2 240 51, J i a ng s u, C hi n a     * C or r es po ndi ng a ut hor ,   e - ma i l l i uy uanz h en_2 004 @ 1 26. c om       A b st r act   N et w or k  t r a f f i c  di s t r i but i on i s   heav y - t a i l e d.  M os t  of  ne t w or k  f l ow s   ar e s hor t   and  c ar r y  v e r y  f e w   pac k et s ,   and  t he  num b er   of   l a r ge  f l ow s   i s   s m al l .   T r adi t i on al   r andom   s am pl i ng  t end s   t s a m pl m or l ar g e   f l ow s   t h an  s h or t   one s .   H ow e v er ,   m any   app l i c at i ons   d epe nd  on  per - f l ow   t r af f i c   ot h er   t han  j u s t   l ar g f l ow s .   A   f l ow   f ai r   s am p l i n bas ed  on  m ul t i s t ag B l oom   f i l t er s   i s   pr opo s ed.   T h t ot al   m ea s ur em en t   i n t er v a l   i s   di v i d e d   i nt c h i l t i m i nt er v a l s .   I e ac c hi l t i m i nt er v al ,   em pl o y   m ul t i s t age  B l oom   f i l t er s   t q u er y   t h i n c om i n g   pac k et s  f l ow  w het her  ex i s t s  i n f l ow  i nf or m at i o n t abl e or  not .  I f  ex i s t s ,  s am pl e t he p ac k et  w i t h s t a t i c   s am pl i ng  r at w h i c i s   i nv er s el y   pr opor t i o nal   t t he  e s t i m at i o f l ow   t r af f i c   u t t he  pr ev i o us   t i m e   i n t er v al ;   if   not ,   t hat     i s   i t s   new   f l ow s   f i r s t   pa c k e t ,   c r eat t he  f l ow   i n f or m at i on ,   i ns er t   i t   i n t t he  m ul t i s t ag B l oom   f i l t er s   an s am pl t he  pac k et   w i t 100 pr ob abi l i t y .   T he  r es ul t s   s how   t h at   t he  pr opo s ed  al g or i t hm   i s   ac c ur at e es pec i al l y   f or  s hor t  f l ow s  an d ea s y  t o e x t e nd.       Ke y w o rd s n e tw o r k  tr a ff i c , s h o r fl o w ,   m ul t i s t ag e b l oom   fi l te r s ,   f l ow  f ai r  s am pl i ng       C o p y r i g h t   ©   20 16 U n i ver si t a s A h mad  D ah l an .  A l l  r i g h t s r eser ved .       1 .  I n tr o d u c ti o n   T r a f f i c   m eas ur e m ent   i s   es s ent i al   f or   net w or k   m anage m ent ,   m oni t or i ng  a nd  s c he dul i ng ,   and m an y  s t ud i es  ar e c ar r i ed ou t  f or  di f f er ent  appl i c at i ons  [ 1 - 2 ].  F or  h i g h s pee d n et w or k ,  r out er s   c annot  m anage t o gen er at e c om pl et e dat a f or  ev er y  pac k et .   T he y   ha v e t o em pl o y  r es t r i c t ed   s a m pl i n g w hi c h i s  ef f ec t i v e  t o r educ e dat a an d r es ou r c e c ons u m pt i on.  I n t he f i e l d of  net w or k   t r af f i c   m eas ur e m ent ,   ac c or di ng   t o   t he   s am pl i ng   s t r at eg y ,   t her e   ar m ai n l y   t hr ee  k i nds   of   s a m pl i n m et hods :  s y s t e m at i c   s a m pl i ng,  s t r at i f i e d r andom  s a m pl i ng and r an dom   s a m pl i ng.   E ar l y  t r af f i c  s a m pl i ng m ai n l y  c onc e nt r at e d on  pac k et  s am pl i ng,  a nd  l at er  on f l o w   s a m pl i n g.  F l o w   i s  a c ol l ec t i on of  pac k et s  w i t h t he s am e pr oper t i es  w i t hi n a t i m e per i od.  T her e ar m an y   m et hods   t di s t i ngu i s f l o w .   T he  c om m on  us ed  i s   t he   f i v t up l m et hod.   T he  f i v t up l r ef er s   t o s our c e/ des t i nat i on I P  ad dr es s ,  s our c e/ des t i n at i on p or t  and pr ot oc o l  t y p e.  I f   any   pac k et  of  a   f l ow   i s  s am pl ed,  t hen  t he f l o w  i s  s am pl ed.   N et w or k   t r af f i c   i s   s el f - s i m i l ar   and  t he  d i s t r i b ut i on  i s   h eav y - ta i l ed.   M os t   of   net w or k   f l ow s   ar s hor t   a nd  c ar r y   v er y   f e w   pac k et s ,   and  t he  num ber   of   l ar ge  f l o w s   t hat   c ar r y   l a r ge  am ount   of   pac k et s   i s   s m al l .   A   s t ud y   s ho w s   9%   of   t h t ot a l   f l o w s   oc c up y   a bou t   9 0%   of   t he   t r af f i c   [ 3 ].  T h e   t r adi t i on al  s am pl i ng m et ho ds  t end  t o s am pl e m or e l ar ge f l o w s  t han  s hor t   one s .  A nd  s om e   al g or i t hm s   f oc us i ng  on  l ar g f l ow   s am pl i ng  [ 4 - 5 ]   ar p r opos ed  t s ol v pr o bl em s   i w hi c om i t   l ar ge  f l o w   w i l l  br i ng  gr eat  l os s ,  s uc h  as  t r af f i c  ac c ount i ng .  H o w e v er   t her e  ar e m an y  o t her   app l i c at i ons   w hi c h  de p en d  on p er - f l o w  i nf or m at i on r at her  t han  l ar ge f l o w s ,  s u c h as  at t ac k s   det ec t i on   [6 - 8] .   T he  pur pos of   t r af f i c   m eas ur e m ent   det er m i nes   w ha t   k i nd  of   s a m pl i ng  m et hod   t o be  ad opt e d   [ 9 ].   N m at t er  w h at  k i nd of   s am pl i ng,  as  l ong as  i t  em pl o y s  1 i N   pac k et s  s t r at eg y ,  t he  s a m pl i n g r es ul t s  t e nd t s a m pl e m or e pac k et s  o f  l ar ge f l o w s  an d om i t  l ot s   of  s hor t  ones .   S am pl i ng  t ha t  s am pl es  m or e pac k et s  f r o m   s hor t  f l ow s  at  ex p ens e of  l o w  s am pl i n g r at of  l ar ge   f l ow s ,   i s   c al l ed  f ai r   s am pl i n g.   I t he  f i el of   f a i r   s a m pl i ng,   s ev er al   r es ear c hes   h av been   c ar r i ed  out   [ 10 - 12 ].   A  s k et c h gui de  s a m pl i n g a l gor i t hm  i s  pr opo s ed   [ 13 ],  m ak e t he pr oba bi l i t y   w i t w hi c h   an  i nc om i ng p ac k et  i s  s am pl e d a  dec r e as i ng  s am pl i ng  f unc t i on  of  t h e s i z e  of  t he  f l o w  t h pac k et   bel ongs  t o , b ut  t h e s hor t  f l o w  es t i m at i on  er r or   i s   gr e at and  t he  s pac e  ef f i c i enc y   i s   l o w .  Z ha ng J ,   et   al . ,   [ 14 ]   pr o pos s p ac ef f i c i ent   pac k et   f ai r   s am pl i ng,   t r af f i c   i s   as s u m ed  t f ol l o w   Z i pf   di s t r i b ut i on  w i t h par am et er   z ,   and  d es i gns  t he  m ul t i  r es ol ut i o n s am pl i n g s t at i s t i c s ,   but  c om put i n c o m pl ex i t y  i s   hi g her .     Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NI K A     I S S N :  1 693 - 6 930       F l ow  F a i r  S am pl i ng  B as e on  Mul t i s t ag e B l o om F i l t er s   ( Li u Y u an z he n )   1143   I n or d er  t o  m eet  t he  nee ds   of  t hos e a pp l i c at i ons   t ha t  n eed  per - f l o w   i nf or m at i on,   a   nov el   f l ow  f ai r  s am pl i ng m et hod bas ed on m ul t i s t a ge B l oom  f i l t er s   ( MB F )  i s  pr opo s ed t o c apt ur e m or e   i nf or m at i on es pec i al l y  f r om   s hor t  f l o w s .  T he  w h ol e m eas ur em ent  i nt er v al  i s   di v i ded  i nt o n um ber s   of  c hi l t i m e i nt er v a l s .  D ur i ng a c hi l i nt er v a l ,  s am pl i n g r at e f or  o ne f l o w   r em ai ns   unc han ged .   F or   an   i nc om i ng p ac k et ,   m ul t i s t age  B l oom  f i l t er s  ar em pl o y ed  t o f i n d t he c or r e s pond i ng  f l o w   i nf or m at i on  t abl e,   an s am pl t h pac k et   bel o ngs   t t he  f l o w   w i t c er t ai s am pl i ng  r at e .   T he   s a m pl i n g r at e  i s   i n v er s el y   p r opor t i ona l  t o t h e es t i m at i on t r af f i c  of  t he f l o w  u p t o t h e pr e v i ous  c hi l d   in t e r v a l.   F or  ne w   ar r i v al  f l o w ,  t her e i s  n o f l o w  i nf or m at i on,  s o a f ul l  s am pl i n g r at e i s  t ak en,  t hat  i s   s a m pl i n t h pac k et   w i t h   1 00%   pr oba bi l i t y .   T he  a l gor i t hm   i s   s i m pl t i m pl em ent ,   t i m i n t er v al   s et t i n g i s  f l ex i bl e ,  an d t h e r es ul t s  s ho w  t ha t  i t  i s  ac c ur a t e es pe c i al l y  f or  s hor t  f l o w s .         T he r es t  o f  t hi s  paper  i s  or gan i z ed as  f ol l o w s .   S ec t i on  2   pr o v i des  a br i ef  s ur v e y   of   B lo o m  f ilt e r   an d m ul t i s t a g e B l o om  f i l t er s .  S ec t i on   3   pr es ent s  a  det ai l ed  des c r i pt i on  of  t he  pr opos e d f l ow  f ai r  s am pl i ng.   S ec t i on  4   g i v es  t he or et i c a l  ana l y s i s  and s ec t i on  5   gi v es   ex per i m ent al   ana l y s i s .   W c onc l ud e i n S ec t i o 6 .       2 . B lo o m  F ilt e r   a n d  M u l ti s ta g e  B l o o m  F i l te r s   A   B l o om  f i l t er  i s   a s pac e - ef f i c i ent   dat a  s t r uc t ur and  i s  us ed  t o  t es t   w het her   an  el em ent   i s  a m e m ber  of  a s et .  I t  s uppor t s   m e m ber  quer i es ,  r andom  s t or age an d has  c ons t ant  h as l ook up t i m e.  Y ou c an a d d an el em ent  and qu er y   f or  an el em ent  w i t h B l oo m   f i l t er .  S i nc pr opos e b y   B l o om   B ur t on  i 197 0   [1 5 ] ,   i t   has   bee us ed  i d at ab as ap pl i c at i ons ,   and  s om e   i m pr ov ed  a l gor i t hm s   ar pr opos ed  [ 1 6 - 1 7 ] .   I r ec e nt   y ear s ,   i t   has   b een  w i d el y   c o nc er ned  i t h e   f i el d of  ne t w or k  [ 1 8 - 19 ].           A em pt y   B l oom  f i l t er  i s  a  bi t  ar r a y  of   m   b i t s ,  a l l  s et  t o  0.  T her e m us t  al s o be  k   di f f er ent   has h f unc t i ons  def i n ed,   w i t h a uni f or m   r andom  di s t r i but i on .  E a c h of  has h f unc t i on s  has hes  s o m e   s et  el em ent  t one  of  t he  m   ar r a y   pos i t i o ns ,  an d t h e  c or r es pond i ng  pos i t i o ns  a r e s et  t 1,  as   s ho w n i F i gur e 1.         F ig ur e   1 . S t an dar B l oom  f i l t er           I f   an  el em ent   bel o ngs   t s et ,   t hen  t he  c or r es pon di ng   has pos i t i o ns   m us t   be  s et   t 1.   F al s n egat i v m at c hes   ar i m pos s i bl e.   H o w e v er ,   du t t h s am pos i t i on  m a y   be  s et   t o   f or   m an y   t i m es ,   ot her   e l em ent s   has hi ng  s et t i ng  m a y   l ea t s om el em ent   does   n ot   be l on t t h s et   and  i t s   c or r es pon di n h as pos i t i ons   ar s et   t 1,   t hus   t he  el em ent   i s   er r oneo us l y   as s um ed   t o bel ong t o t he s et .  T he pr obab i l i t y   i s  c al l ed f al s e pos i t i v e er r or ,  or  i n s hor t  f al s e pos i t i v e.  F al s pos i t i v e m at c hes  ar e pos s i bl e.  T he pr oba bi l i t y   of  f al s e pos i t i v w i l l  be  an al y z e be l o w .   A s s um e t hat  a has h f unc t i on s el ec t s  eac h ar r a y  p os i t i o n w i t h e qua l  pr ob abi l i t y .   Let   n   be  t he  num ber   of   t he  s et   el e m ent s ,   m   be  t he  num ber   of   bi t s   i t he  ar r a y ,   and  k   b t he  num ber   o f   has f unc t i ons .   T he  pr ob a bi l i t y   t hat   c er t ai b i t   i s   s et   t o   1   b y   c er t a i n   has h   f unc t i o i s 1/ m .   T he pr obab i l i t y  t h at  i s   not  s et  t 1 i s :     1 1 m        F or  t her e ar k   has h f unc t i ons ,  s o t he pr ob abi l i t y  t hat   t he bi t  i s  not  s et  t o 1 b y   an y   of  t he  k   f unc t i ons  dur i ng  one  i ns er t i on  i s :     1 1 k m      Evaluation Warning : The document was created with Spire.PDF for Python.
                             I SSN :  1 6 9 3 - 6 930   T E L KO M NI K A     V o l.   1 4 ,  N o 3 S ept em ber   201 6   :   11 42     1 149   1144     A f t er  i ns er t   n   e l em ent s ,  t h e pr ob ab i l i t y  ( den ot e d as 0 p   )  t hat  c er t a i n  pos i t i o n s t i l l  i s   s et   t o 0  i s :       0 1 1 kn m p  =       T he f al s e pos i t i v e ( den ot e d  as   er r p )  is :       ( ) 0 1 1 11 k kn k er r p m p   = = −−           ( ) / 1 k kn m e ≈−   ( ) / ln 1 kn m k e e =                      W h ile ( ) / ln 2 k mn =   , th a i s   0 1/ 2 p = ,   er r p t ak es  t he m i ni m u m  v al ue :     / ln 2 / mi n 11 1 0.6185 22 k mn mn er r p  = −= =       Mul t i s t ag e B l oom   f i l t er s  i s   par al l el  s t r uc t ur e of  s ev er a l  B l oom   f i l t er s ,  as  s ho w n i F i gur 2.   E ac B l oom   f i l t er   em pl o y s   d i f f er ent   has f u nc t i on   c l us t er s .   T ad a el em ent ,   e v er y   B l o om  f i l t er  s houl d m a k e an ad d op er at i on.  T o t es t   an  el em ent ,  o nl y  e v er y  B l o om  f i l t er  i ndi c a t es   t he e l e m ent  i s  i n t h e s et .    A l t hou gh t he  i nh er ent  f al s e  pos i t i v e er r or  of  B l oom  f i l t er  ex i s t s ,  t he   di f f er ent  has h f unc t i o n c l us t er s  c an gr eat l y  r e duc e t he  er r or .  Let   p   i s  t he f al s pos i t i v e er r or  of  a  s i ngl B l oom  f i l t er ,   n   i s  t he   num ber  of  s t ages ,  as s um e eac B l o om  f i l t er  has  e qua l  f al s e pos i t i v er r or ,  t hen  t he  f al s e p os i t i v e er r or  of  a m ul t i s t ag e B l o o m   f i l t er s  w i t h   n   s t ag es  i s n p .       F i gur e 2.    Mul t i s t a ge B l oom   f i l t er s       3 .  F l o w  F a i r  S a m p l i n g  M e t h o d   Let   ( ) 1 , 2... = k fk    be t he f l ow  dur i ng  t he m eas ur e m ent  i nt er v al .  D i v i de t he  w h ol m eas ur e m ent  i nt er v al  i nt n   c hi l t i m e i nt er v a l s .   w e  c a r r y   out  f l o w  s am pl i n v i a p a c k et  s am pl i ng,   t hat   i s   i f   a n y   pac k et   of   f l o w   i s   s am pl ed,   t h en  t he  f l o w   i s   s am pl ed ,   an s t at i s t i c s   ar b as ed   on   f l ow s   not   p ac k et s .   C ol l ec t   s a m pl ed pac k et s  ev er y   c hi l t i m e i nt er v al  an s am pl i ng  r at f or  t he  f l ow   i s   unc h ang ed  dur i ng  t he  c hi l t i m i nt er v a l .     W em pl o y   f l o w   i nf or m at i on  t a bl t m ai nt a i n     s a m pl ed  f l o w     i nf or m at i on.   Mul t i s t ag B l oom   f i l t er s   ar us ed   t add  or   qu er y   f or   c or r es pondi ng  f l ow  r ec or d i n t h e f l o w   i nf or m at i on t ab l e.     F or   ne w   ar r i v a l   pac k et ,   l oo k   f or   i t   i t he  m ul t i s t ag B l o om   f i l t er s ,   i f   an y   of   t he  b i t s   at   t he   has h pos i t i o ns  i s  0,   w hi c h m eans   t he c or r es pondi n g f l o w   r ec or d d oes  not  ex i s t ,   t he a dd   t h pac k et   i nt m ul t i s t age   B l oo m   f i l t er s   and  c r ea t t he  f l o w   i nf or m at i on  r ec or d.   T add   a e l em ent ,   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NI K A     I S S N :  1 693 - 6 930       F l ow  F a i r  S am pl i ng  B as e on  Mul t i s t ag e B l o om F i l t er s   ( Li u Y u an z he n )   1145   a ll  B lo o m  f ilt e r s  c or r es pon di n g pos i t i ons  s hou l be s e t  t o 1.   I f  t he r ec or d ex i s t s ,   t hat  i s   al l  B l oom   f ilt e r s   in d ic a t e   t h c or r es po ndi ng  pos i t i o ns   ar s et   t 1,   s am pl t he  pac k et s   bel o ng  t t he  f l o w   w i t h s t at i c  s am pl e r at e   t k p   and  upd at e t he f l o w  i nf or m at i on ,  as  s ho w n i F i gur e 3         F i gur 3.  s am pl i n g pr oc es s  w i t h  m ul t i s t age  B l oom  f i l t er s       T he s a m pl i ng  r at e t k p   i s   unc hang ed  d ur i n g   t h c hi l t i m i nt er v al I t   i s   i nv er s el y   pr opor t i on al  t o t he es t i m at e  t r af f i c   1 t k N   up t o t h e pr e v i o us  c hi l d t i m e i nt er v al .  I f  t he f l ow  i s   t   t i m i nt er v a l  ne w  ar r i v a l  f l o w ,  t h en t he 1 t k N    equa l s  t o 0,   t hen    s am pl i ng r at t k p   equal s  t o   1.   A s  t i m goes   b y ,   t h c ur r ent   es t i m at t r af f i c   1 t k N   gr o w s ,   i f   f l o w   i s   not   ov er ,   t he  s am pl i n r a t f or   t he   f l ow  dec r eas es  w i t h t i m as   a s t ep f unc t i on.  S am pl i ng r at t k p    i s a s f o l l o w s:                                              ( 1)       W he r e ε   i s   a c ons t ant .   Let   i k N   be t h num ber  of  pac k et s   s a m pl ed  f r om   f l ow   k f   dur i n g c hi l t i m e i nt er v al   t ,  a nd t hen  t he  es t i m at e t r af f i c  of   f l ow k f   af t er  t i m e i nt er v al   t   is :              1 / = = t t i t k kk i N Np                                    (2 )                 F l o w  f ai r  s am pl i n g pr oc es s   as  f ol l o w s :     di v i d e t h e m eas ur em ent  i nt n   c h ild  t im e  in t e r v a ls ;   in i t ia li z e    0 k N   t o  0   / /  i n it ia li z e  t r a f f ic  is  0   in i t ia li z e  a l l 1 k p    t o 1    / / s am pl i n g r at e f or  a  ne w  f l o w  dur i ng  a t i m e i nt er v a l   i s  1     w hi l e ( t i m e i nt er v al   t )     / / d u r i ng t he c h i l d t i m e i nt er v a l   t 1... = tn     x = ar r i v al  pac k et ;          i f ( B l oom  f i l t er  s t age _i ( ( ) ( ) ( ) 12 , , ..., k h x h x h x ==1 )     // th a t  i s   x   ex i s t s  i n f l o w   i nf o  t ab l                              s am pl e t he  p ac k et  w i t h s t at i c  r at e   t k p   upda t e f l o w   i nf or m at i on      el s               s et  B l o om   f i l t er  s t ag e _i ( ( ) ( ) ( ) 12 , , ..., k h x h x h x = 1 / / i ns er t  t he e l em ent  i n t o M B F   1 2 1 1 1 2 ε = + t k t k p N Evaluation Warning : The document was created with Spire.PDF for Python.
                             I SSN :  1 6 9 3 - 6 930   T E L KO M NI K A     V o l.   1 4 ,  N o 3 S ept em ber   201 6   :   11 42     1 149   1146   s a m pl e t h e p ac k et     c r eat e f l o w  r ec or d       if  t im e  in t e r v a l t  is  o u t       c o m put e    1 + t k p       / / ac c or di n g t o  equ at i on( 1)   c o m put e    t k N       / / ac c or di n g t o  equ at i on( 2)     if  it ’s  t im e  t o  c le a r  M u lt is t a g e  B lo o m   f ilt e r s            c l ear  M ul t i s t a ge  B l o o m   f i l t er s ,  al l  bi t s  s et  t 0  / / e v er y   t hr es h ol d  t i m T        / /  t hr es h ol d   = T kt ,  w h er k   i s  an i nt e ger ,   t   i s  t he  dur a t i o n of  c hi l d t i m e i nt er v al         F or  t he d ur at i on  t i m e of  s hor t  f l o w   i s  s hor t  an d l ar g e f l o w  i s   l on g,  s o s am pl i n g ne w   ar r i v a l  f l o w  f ul l y  c a n get  m or e s hor t  f l ow s  i nf or m at i on.   A s  t he num ber  of  l ar ge f l ow s  i s  s m al l ,  t he   c ons um ed r es our c es  ar e l i m i t ed dur i ng c hi l d t i m e i nt er v a l .  I n or der  t o   r educ e t he pr es s ur e o f   r es our c es   c aus ed  b y   s am pl i n g,   w c an  d i v i d t h m eas ur em ent   i nt er v al   i n t s ho r t er   c hi l d   t i m e   i nt er v a l s .   T hen  t he  r es our c es   c ons u m pt i on  f or   l ar ge  f l o w s   dur i ng  t he  f i r s t   ar r i v al   t i m i nt er v a l   i s   r educ ed,   an d dur i ng  ot h er  t i m e i nt er v a l s  s am pl e l ar g e f l o w s   w i t h c er t a i n s am pl i n g r at e.     A t  t h e e nd  of  t he t i m e i nt er v a l ,  t he f l o w  r ec or ds   w h i c h ha v e no t  b een  up dat e d ar e   as s u m ed i n ac t i v e  f l o w s  an d  r em ov ed f r om  t he f l o w  i nf or m at i on t ab l e.  C l ear  u p m ul t i s t ag B l o om   f i l t er s  ev er y  t hr es ho l d t i m e   T    t o r educ e  c onf l i c t  of  h as h c ol l i s i on,  a nd  at  t h e s am e t i m i t   w i l l   br eak  t he f l ow   i nf or m at i on and br i ng er r or  es pec i a l l y  f or  l ar ge f l ow s   w h os e dur at i o n t i m e go    ac r os s  s ev er a l  t i m e i nt er v al s .  T hr es hol T   i s  c ons t ant  t i m es  of   dur at i on   t   of  c hi l d t i m e   in t e r v a l:       = T kt                                     ( 3)     W h er i s  an i n t eg er .       4.  T h eo r et i cal   A n al ysi s   4 . 1.   V al u e E st i m at i o n      T he ent i r e m eas ur em ent  t i m e i s  di v i ded  i nt o   n   c h i l d t i m e i nt er v al s .  Let i k N   b e t he  pac k et s  nu m ber  and i k X   be by t es  num ber  s am pl ed f r o m   f l ow k f   dur i ng c hi l d t i m e i nt er v al   t T hen t he t ot a l  pac k et s  num ber  es t i m at i on  v al u e   k N is :         1 / = = n i t k kk i N Np                                 ( 4)     T he t ot al   b y t es  num ber  es t i m at i on v a l u k X   is :           1 / = = n i t k kk i X Xp                                 ( 5)     4 . 2 .   S p a c e  C o n s u m p ti o n     T he s pac e c ons um pt i on  of  t he pr opos e d a l gor i t hm   m ai nl y  c om es  f r o m  t w par t s ,   one  i s   t he m ul t i s t ag e B l o om   f i l t er s  t ak i ng up s pac e ,  an d t he s ec o nd  i s  f l o w  i nf or m at i on t ab l e   m ai nt enanc e.   A   B l oom   f i l t e r   i s   s pac e - ef f i c i ent   has dat s t r uc t ur an get s   i t s   s pac ef f i c ac y   at   t he  c os t   of   f al s pos i t i v e   er r or .   T he  s t ages   of   m ul t i s t age  B l oom   f i l t er s   c an  be  det er m i ned  b y   t he ba l anc e of  r es our c es  and f al s e pos i t i v e er r or .   F or  f l ow  i nf or m at i on t ab l e m ai nt en anc e,  t he  w or s t   c as i s  t hat  t he s pa c e c ons um pt i on  i s  c ons t a n t   t i m es   of   t he num ber   of   f l o w s   dur i n t h t ot a l  m eas ur e m ent  t i m e.  H o w e v er ,  f or  t he  num ber  of  s hor t  f l o w s  i s   l ar ge  an d t h dur at i on t i m e i s   s hor t ,   at   t he  end  of   t he  c h i l t i m i nt er v al ,   t h f l o w s   h av not   b een  u pda t ed  ar r em ov ed  f r o m   f l ow   i nf or m at i on t a bl e t d o f ur t her  an al y s i s ,  t hus  r el eas e m uc h s pac e,  s o t h s pac e ne ede t ur ns  t o c ons t ant  t i m es  of   f l o w s  dur i ng c h i l d t i m e i nt er v al .   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NI K A     I S S N :  1 693 - 6 930       F l ow  F a i r  S am pl i ng  B as e on  Mul t i s t ag e B l o om F i l t er s   ( Li u Y u an z he n )   1147   4. 3 .   Er r o r  A n a l y s i s   T he  er r or   i s   c o m pos ed  of   s am pl i ng  er r or ,   f al s pos i t i v er r or   of   m ul t i s t age  B l oom   f i l t er s   and  er r or   c aus e b y   r egu l a r l y   c l e ar   up  m ul t i s t a ge  B l o o m   f i l t er s .   T he  f al s pos i t i v e   o f   m ul t i s t age  B l o om   f i l t er s   i s   ex p one nt i al l y   dec r eas ed   r ef er   t s i ng l B l oom   f i l t er .   C l e ar   up  m ul t i s t a ge  B l oom   f i l t er s   r egul ar l y   i s   t r ed uc has c ol l i s i o and  br i ngs   er r or   es pec i al l y   f or   f l ow s   w hos dur at i o t i m go  ac r os s   t he  t i m i nt er v a l s .   T he  t hr es ho l t i m i s   i nt eger   t i m es   of   t he  t i m e   i nt er v a l ,     a nd   bet t er  l o ng er  t h an s h or t  f l o w   dur at i on  t i m e,  w h i c h c an  r ed uc er r or  t o  s hor t  f l o w s .   C om par at i v e l y ,  t he m ai er r or  i s  s am pl i ng  er r or .   S am pl i ng  i s  an  ef f ec t i v e m et ho d f or  dat r educ t i o n,   ho w ev er ,  s am pl i ng  i t s el f  c a n n ot  av oi d   i n h er ent   s t at i s t i c al   er r or .  I n   our  a l gor i t hm ,   s a m pl i n g er r or  i s   m or e f or  l ar ge f l o w s  w hos e s am pl i ng  r at e i s   i n v er s el y  pr o por t i on al   to  i ts  tr a f f i c ,   and  ha v e ac c ur at e i nf or m at i on  es t i m at i on f or  s hor t  f l o w s .       5 .  E xp er i m en t al   A n al ysi   In  th i s  s ec t i o n,   w e us e t he  ac t ual  dat a of  t h e I nt er net  t o c ar r y  o ut  ex p er i m ent al   an al y s i s .   D at a c om es   f r o m  t he U . S .  N at i o na l  Lab or at or y  f or  A pp l i c at i o n N et w or k  R es e ar c h ( N LA N R )   p u b lic l y  a v a il a b le  T R A C E .     F l o w  f ai r  s am pl i ng r a t e c hang es   w i t h t i m e i nt er v a l .  F i gur e 4  s ho w s  s am pl i n g r at e   c o m par i s on  of   our   f l o w   f ai r   s a m pl i ng  and  r a ndom   s am pl i ng  w i t s am pl i ng  r at equa l s   t 0. f or   t he  s am f l o w ,   and   t h t i m i nt er v al   i s   m ill is e c o n d   ( m s ) .   S am pl i ng  r a t of   our   f l o w   s am pl i ng  m et hod dec r eas es  as  a s t e p f unc t i on  ev er y  c hi l d t i m e i nt er v al .   W hi l e 1 out   N   r and om  s a m pl i ng’ s   s a m pl i n g r at i s  s et  ar t i f i c i a l  or  ac c or d i ng  t o a  c er t ai n r ul and  r em ai ns  s t at i c .         F i gur e 4.   S am pl i ng  r at e c o m par i s on       U nder   t he  s am e pac k et  s am pl i ng r at e ,  o ur  f l o w  f ai r   s am pl i ng m et hod  t ur ns   t o s am pl e   m or e  f l ow .  F i gur e 5 s how s   under  t h e s am e  pac k et  s a m pl i ng r at e,  f l o w  f ai r  s a m pl i ng and r an dom   s a m pl i n g’ s  f l ow  r at i s am pl ed.   R an dom   s a m pl i ng  s a m pl es  1  pac k et   f r o m   N ,   f or   net w or k  t r af f i c   di s t r i b ut i on i s  h ea v y - t ai l ed ,   m aj or i t y  of  pac k et s  s a m pl ed ar e   f r om  l ar ge f l ow s .   W hi l e s a m pl i ng  r at e i s  c l os e t 1,  a l l  f l o w   i nf or m at i on c an b e ob t ai ne d i n t he or y .          T he  f al s pos i t i v er r or   of   m ul t i s t age  B l oom   f i l t er s   dec r eas es   as   t he  nu m ber   of   s t ages   i nc r eas e.  F i gur e 6 s ho w s  t he r el at i o n of  t he s t ages  num ber  o f   m ul t i s t age B l oom  f i l t er s  ( MB F )   and  m ax i m u m   o f   f al s pos i t i v er r or .   W hi l s t a ges   n u m ber   equal s   t 1,   m ul t i s t ag B l oom   f i l t er s   t ur ns  t o a s i ngl e s t ag e B l oom   f i l t er .  T he  f al s e pos i t i v e r at e dec r eas es  ex pone nt i a l l y   w i t h t he   i nc r eas of  t he s t ag es .     0 1 2 3 4 5 6 7 8 9 10 0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 0. 7 0. 8 0. 9 1 t im e m s s am pl i ng r at e     f l ow  f ai r  s am pl i ng r andom  s am pl i ng w i t h s am pl i ng r at e= 0. 3 Evaluation Warning : The document was created with Spire.PDF for Python.
                             I SSN :  1 6 9 3 - 6 930   T E L KO M NI K A     V o l.   1 4 ,  N o 3 S ept em ber   201 6   :   11 42     1 149   1148         F i gur e 5.   F l o w  r at i o s am pl e d c om par i s on   F i gur e 6.   R el a t i o n b et w e en  s t ages  of   m ul t i s t age  B l o om  f i l t er s  ( MB F )   and   m ax i m u m   of  f al s e pos i t i v e  er r or       6 .  C o n c l u s i o n   T hi s   paper   pr opos es   a f ai r   f l ow   s am pl i ng   al gor i t hm   bas ed o n m ul t i s t ag B l oom   f i l t er s .   T he t ot a l  m eas ur em ent  i nt er v a l  i s   di v i ded  i nt o n  c hi l d t i m e i nt er v a l s .  D ur i ng  t h e s am e t i m e   i nt er v a l ,  t he s am pl i n g r at e f or  c er t ai n f l o w  k eep  s t at i c .  T he s am pl i ng  r at e  i s  i nv er s el y   pr opor t i on al  t o t h e f l ow s  es t i m at e t r af f i c  up t o t he  pr ev i ous  c hi l d t i m e i nt er v a l .   I t ’s  s im p le  t o   ev a l u at e t he t o t al   t r af f i c  a c c or di ng t o s am pl ed  pac k et s .  T he num ber  of  s t ages  of   m ul t i s t age   B l o om   f i l t er s   i s   adj us t abl ac c or di ng  t t he  r es our c es   and  t he  f al s pos i t i v er r o r   de m and.   T he   r es ul t s   s ho w   t hat   t h pr op os ed  al gor i t hm   c an  s a m pl m or s hor t   f l ow s .   A n t he   al gor i t hm   c an   be a ppl i e d i n m an y  ap pl i c at i ons  s uc as  at t ac k s  det ec t i on,  t r af f i c  engi ne er i ng .           R ef er en ces   [1   Z hao Y ,  X i X ,  J i ang M .  H i er ar c h i c al  R eal - t i m e N et w or k  T r af f i c  C l as s i f i c at i on B a s ed  on E C O C .   T EL KO M N I KA   I ndone s i a J ou r nal  o f  E l e c t r i c al  E ngi neer i ng .   2014 ;   12( 2) :   15 51 - 15 60.   [2   Z hou  D ,   Li W ,   Z h ou  W ,   et   a l .   R es ear c on  T r af f i c   I dent i f i c at i on  B a s e o M ul t i   Lay er   P er c ep t r on .   T el k om ni k a .   20 14 ;   12( 1) :   201 - 208.   [3   F ang  W ,  P et er s on L .   In te r - AS T ra f f i c  Pa t t e rn s  a n d   T h e i I m p li c at i o ns .  P r oc e edi ng s  of  I E E E   G L O B E C O M R io ,   Bra z i l .   199 9 185 9 - 18 68.   [4   Z hang  Z ,   W a n B ,   Lan  J .   I d e nt i f y i ng  e l eph ant   f l ow s   i i nt er net   bac k bo ne  t r af f i c   w i t bl oo m   f i l t er s   an d   L RU.   C om put er  C om m uni c at i o ns .   2 015 61:   70 - 78 .   [5   Z hou  A P ,   C he ng  G ,   G uo  X J ,   et   al .   P ar al l el   de t ec t i o al g or i t h m   on  l ong  d ur at i on  d at a   s t r ea m i n g .   J our n al  o f  C om m uni c at i o ns 2 015;   3 6( 11) :   1 56 - 166 .   [6   P ont a r e l l i  S ,  R ev i r i ego P ,  M aes t r J A .  E f f i c i ent   F l ow  S am p l i n W i t h B a c k - A n not at ed C u c k o o H as h i ng .   I E E E  C om m uni c at i on s  Le t t er s .   2014;  18( 10) :   1 695 - 1698 .   [7   B ar t os  K ,  R e hak  M .  I F S :  I n t el l i gent   f l ow  s am pl i n g f or  n et w or k  s ec ur i t y an  ada pt i v e   appr oa c h .   I nt er na t i o nal  J our nal  of   N et w o r k   M anagem ent .   2 015 ;  25( 5) :   26 3 - 282 .   [8   J os eph N .   U s i n g S ub - o pt i m al  K al m an   F i l t er i ng f or  A n om al y  D et ec t i on i n N et w or k s .  P r o c eed i ng o f   I nt er na t i o nal  C onf e r en c on E l ec t r i c al  E ng i ne er i n g,  C o m pu t e r  S c i en c e a nd  I nf or m at i c s  ( E E C S I  201 4) .   Y ogy ak ar t a,  I n done s i a.  20 14;   1:   408 - 414 .   [9   Z hou A P ,  C heng G ,  G uo X J .   H i gh - S pe ed net w or k  t r af f i c  m ea s ur em e nt  m et hod.   J our n al  of   S of t w ar e 2014;   25( 1) :   1 35 - 153 .   [1 0   W a n Y X ,   C hen  S Q ,   Z h ang  Z .   A   f a i r   s am pl i ng  a l gor i t hm   of   net w or k   f l ow   bas ed  o d y n am i c   c ou n t   fi l te r .  I E E E  4t h  I nt er nat i ona l   C onf er en c on S of t w ar e E ngi neer i n g  a n d  Se rv i c e  Sc i e n c e  (I C SESS) .   2013:  811 - 815.   [1 1   Yi   P ,   Q i a n   K,   H ua ng   W W .   A dapt i v f l ow   s am pl i ng  a l gor i t h m   ba s ed   on  s a m pl e p ac k et s   and  f or c e   s am pl i ng t hr e s h ol d S  t ow ar ds  anom al y  det e c t i on.   J our n al  of  E l ec t r o ni c s  &  I nf or m at i o n T e c hanol og y 2015;   37( 7) :   16 06 - 16 11.   [1 2   D u ffi e l d  N F ai r  S am pl i ng  A c r os s  N et w or k  F l ow  M eas ur em ent s .  SI G M ET R I C S’ 1 2 .   Lond o n,  E ngl a nd ,   U K.  AC M .   2012:  367 - 3 78.   [1 3   Ku m a r A,  X u  J .   S k et c h g ui d ed s am pl i ng - U s i ng on - l i ne e s t i m at e s  of  f l ow  s i z e f or  adapt i v e da t a   c ol l ec t i on .  I n  Pr o c .   o f  I EEE  I nf oc o m   20 06.   W a s h i ng t on .   2 0 06:  1 - 11.   0 0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 0. 7 0. 8 0. 9 1 0 0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 0. 7 0. 8 0. 9 1 pac k et  s am pl i ng r at e f l ow s  r at i o s am pl ed     f l ow  f ai r  s am pl i ng r andom  s am pl i ng 1 2 3 4 5 6 7 8 9 0 0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 0. 7 s t ages  of   M B F m ax i m um  of  f al s e pos i t i v e er r or Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NI K A     I S S N :  1 693 - 6 930       F l ow  F a i r  S am pl i ng  B as e on  Mul t i s t ag e B l o om F i l t er s   ( Li u Y u an z he n )   1149   [1 4   Z hang  J W u   J X , N i u  X N . S p a c e - E f f i c i ent  f ai r  p ac k et  s am p l i ng al gor i t hm .   J o ur nal  of   s of t w ar e .   2 01 0;   21( 10) :   264 2 - 26 55.   [1 5   B ur t on  B .   S pac e/ t i m t r ade of f s   i has c odi ng  w i t al l ow abl er r or s .   C om m uni c at i on s   A C M .   1970 ;   13( 7) :   422 - 4 26.   [1 6   P ont a r e lli  S ,   R e v ir ie g o   P ,   M ae s t r J A .   I m pr ov i n c ou nt i n B l oom   f i l t er   per f or m anc w i t f i nger pr i nt s .   I nf or m at i on P r o c e s s i ng L et t er s .   2015 ;  11 6( 4) :   304 - 3 09.   [1 7   J   A gui l ar - Sa b o ri t ,   P   T r anc os o,   V   M unt es - M ul er o.   D y nam i c   C ount   F i l t er s .   A CM   S I G M O Re c o r d 2006;   35( 1) :   26 - 32.   [1 8   Bro d e A,   M i t z e n m ac h er   M .   N et w or k   A ppl i c at i ons   of   B l o o m   F i l t er s :   A   S ur v ey .   I nt er net  M at h 2003 ;   (4 ):   4 85 - 509 .   [1 9   Li W ,   Q W ,   G o ng  J ,   et   al .   D et ec t i on  of   S u per p oi nt s   U s i ng  V ec t or   B l o om   F i l t er .   I E E E  T r a n s ac t ions   on I nf or m at i o n F or e ns i c s  &  S e c ur i t y .   2 015;  11( 3) :  51 4 - 52 7.             Evaluation Warning : The document was created with Spire.PDF for Python.