I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute E ng in ee ring   ( I J E CE )   Vo l.   8 ,   No .   5 Octo b e r   2 0 1 8 ,   p p .   3 3 6 8 ~ 3 3 7 3   I SS N:  2088 - 8708 DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 8 i 5 . pp 3 3 6 8 - 3373           3368       J o ur na ho m ep a g e h ttp : //ia e s co r e . co m/ jo u r n a ls /in d ex . p h p / I JE C E   Perf o r m a nce  Ana ly sis  of Mesh - ba s ed NoC’s  on Ro ut ing   Alg o rith m s       Ana la   M .   R . ,   Am it   N .   Su bra h m a ny a ,   Allbrig ht  D’ So uza   De p a rtme n o f   Co m p u ter S c ien c e   a n d   E n g in e e rin g ,   V   C o ll e g e   o f   En g in e e rin g ,   I n d ia       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   No v   30 ,   2 0 1 7   R ev i s ed   J an   19 ,   2 0 1 8   A cc ep ted   Feb   7 ,   2 0 1 8     T h e   a d v e n o S y ste m - on - Ch ip   ( S o Cs),  h a b ro u g h a b o u a   n e e d   to   in c re a se   th e   sc a le  o f   m u lt i - c o re   c h ip   n e tw o rk s.  Bu s   Ba se d   c o m m u n ica t io n h a v e   p ro v e d   to   b e   li m it e d   in   term o f   p e r f o r m a n c e   a n d   e a s e   o f   s c a la b il it y ,   th e   so lu ti o n   t o   b o th   b u   b a se d   a n d   P o in t - to - P o in ( P 2 P c o m m u n ica ti o n   s y ste m is  to   u se   a   c o m m u n ica t io n   in f ra stru c tu re   c a ll e d   Ne tw o rk - on - Ch i p   (No C).   P e rf o rm a n c e   o f   No d e p e n d o n   v a rio u f a c to rs  su c h   a n e tw o rk   to p o lo g y ,   ro u ti n g   stra teg y   a n d   sw it c h in g   tec h n iq u e   a n d   traf f ic   p a tt e rn s.  In   th is  p a p e r,   w e   h a v e   ta k e n   th e   in it iativ e   to   c o m p il e   to g e th e a   c o m p a ra ti v e   a n a ly sis  o d iff e r e n Ne t w o rk   o n   Ch i p   in f ra stru c tu re b a se d   o n   t h e   c las si f ica ti o n   o f   ro u ti n g   a lg o rit h m ,   s w it c h in g   tec h n iq u e ,   a n d   traf fic  p a tt e rn s.   T h e   g o a is  to   sh o w   h o w   v a ried   c o m b in a ti o n o f   th e   th re e   f a c to rs  p e rf o r m   d if fe re n tl y   b a se d   o n   th e   siz e   o f   t h e   m e sh   n e tw o rk ,   u sin g   NO X IM ,   a n   o p e n   so u rc e   S y ste m S i m u lat o o f   m e sh - b a se d   No C.   T h e   a n a ly sis  h a sh o w n   ten a b le ev id e n c e   h ig h li g h ti n g   t h e   n o v e lt y   o f   X Y ro u ti n g   a lg o rit h m .   K ey w o r d :   Net w o r k - on - c h ip   P er f o r m a n ce   R o u ti n g   alg o r it h m   S w itc h in g   tec h n iq u e   T r af f ic  p atter n   Co p y rig h ©   2 0 1 8   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   An ala  M .   R .   Dep ar te m en t o f   C o m p u ter   Sci en ce   an d   E n g i n ee r in g ,   R   C o lle g o f   E n g i n ee r in g ,   R   Vid y a n i k eth a n   P o s t,  M y s o r R o ad ,   B en g al u r u   -   5 6 0   0 5 9 ,   I n d ia .   E m ail:  a n ala m r 2 0 0 4 @ g m ai l.c o m       1.   I NT RO D UCT I O N     Net w o r k - on - C h ip   is   an   e s s e n t ial  co m m u n icatio n   s u b s y s te m   f o r   S y s te m - on - C h ip   ( So C )   ar ch itect u r es   as  it   h a s   t h ca p ab ilit y   to   m ee t   t h r eq u ir e m e n ts   o f   s ca lab ilit y ,   ea s o f   f ab r icatio n   a n d   ad v a n ci n g   tech n o lo g ies.   A   Mu l tip r o ce s s o r   S y s te m - on - C h ip   ( MP So C )   is   t h e   a g g lo m er atio n   o f   m icr o p r o ce s s o r s ,   m icr o co n tr o ller s ,   m e m o r y   b lo ck s ,   a n d   m o r s u ch   an a lo g   a n d   d ig ital  in ter f ac es,  co u n ter s ,   p o w er   m a n a g e m en t   cir cu its ,   etc.   T h s y s te m   is   b u ilt  to   m a k u s o f   lar g n u m b er   o f   I n tellect u al  P r o p er t y   ( I P )   co r es  f o r   h ig h   p r o ce s s in g   p o w er .   B u s es  a n d   p o in t - to - p o in ( P 2 P )   lin k s   w er u s ed   as  co m m u n icatio n   i n f r astru ct u r f o r   So C   at  its   i n ce p tio n ,   b u i f ai led   to   f u l f ill  f u t u r co m m u n icatio n   r eq u ir e m e n t s   s u ch   a s   h ig h e r   s ca lab ilit y ,   s tab le   p er f o r m a n ce   a n d   ac ce p tab le  p o w er   co n s u m p tio n   [ 1 ] ,   [ 1 0 ] .   Hen ce ,   th er w as  n ee d   t o   v ee r   a w a y   f r o m   co m p u tatio n   ce n tr ic  m o d els   to   co m m u n icatio n   ce n tr ic  m o d e ls   [ 3 ] .   T h ese  p r o b lem s   w er s o lv ed   Net w o r k - on - C h ip   ( No C )   m o d els.  C o u p led   w it h   m i n i m al  co m p lex i t y   a n d   h ig h   s ca lab ilit y ,   it  p r o v id es  h i g h   v er s at ilit y   alo n g   w it h   q u al it y   p er f o r m an ce .   T h p ith   o f   th No C   ap p r o a ch   is   to   u s m ac r o s co p ic  co n ce p s u ch   as  p ac k et - s w it ch in g   an d   in f r astru ct u r al   I P s   w h ich   allo w s   ac ce s s   to   i n d iv id u al  f u n ct io n al - I P   b lo ck .   T h e   m o s i m p o r tan f ea tu r e s   t h at   d is tin g u is h   No C   ar ch itect u r es   ar n et w o r k   to p o lo g y ,   r o u tin g ,   an d   p ac k et  p r io r ity .   Ho w e v er ,   p ar am eter s   s u c h   as  b u f f er   s ize,   p o w er   co n s u m p tio n ,   an d   ar ea   o v er h ea d   s h o u ld   also   b co n s id er ed   w h i le  d ea lin g   w i th   n et w o r k   p er f o r m a n ce .   T h No C   ar c h it ec tu r is   co m p r is ed   o f   th r ee   p ar ts   -   R eso u r ce s ,   R o u ter s   a n d   R eso u r ce   Ne t w o r k   I n ter f ac [ 2 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       P erfo r ma n ce   A n a lysi s   o f Mes h - b a s ed   N o C s   o n   R o u tin g   A lg o r ith ms   ( A n a la   M.  R . )   3369   a.   R eso u r ce s T h e y   ar t h p r o ce s s i n g   ele m en ts   th at   ar s e l ec ted   b ased   o n   f u n ct io n alit y ,   s ize  a n d   s p ee d   r eq u ir e m en ts   o f   a   n e t w o r k .   E . g .   Mic r o p r o ce s s o r s ,   Mic r o co n tr o ller s ,   A DC s ,   D AC s ,   FP G As,  Au d io   Vid eo   co n tr o ller s   o r   Me m o r y   B lo ck   co n tr o ller s .   b.   R eso u r ce   to   Net w o r k   in ter f ac e:  T h ey   p r o v id t h i n ter f ac f o r   th co m m u n icatio n   b et w e en   t h r eso u r c e   an d   th r o u ter s .   T h e y   ar in v o lv ed   w it h   th co n v er s io n   o f   p ac k ets  o f   d ata  i n to   s u itab le  f o r m   f o r   tr an s p o r tati o n   ( f l its   o r   p h its )   a n d   its   co n v er s io n   b ac k   to   th o r ig in a l p ac k et  o f   d ata.   c.   R o u ter I t   is   r esp o n s ib le  f o r   t h tr a n s f er   o f   d ata  f r o m   t h s o u r ce   I P   to   d esti n a tio n   I P   th r o u g h   r o u ter s   i n   ac co r d an ce   w it h   th r o u t in g   al g o r ith m .   T h t w o   m ain   r eso u r ce s   alo n g   w ith   t h I P   th at  ch ar ac ter izes  No C s   ar b u f f er s   an d   ch an n el s .   T o   in cr ea s t h r eso u r ce s   al lo ca tio n   f o r   ea c h   p ac k et,   a   p h y s ical   ch a n n el   is   m u ltip le x ed   i n to   a   n u m b er   o f   v ir tu a l   ch an n el s .   I is   v ia  t h ese  c h an n els  th a th p ac k ets  ar tr a n s f er r ed   f r o m   t h s o u r ce   I P   to   th d esti n atio n   I P   b y   d ef er r in g   to   th r o u ti n g   alg o r ith m   a s   p r escr ib ed .   E ac h   ch an n el  i s   co m p o s ed   o f   b u f f er s   th at  allo w   t h f r ee   m o v e m e n t o f   p ac k et s   in   m o r d is cr ete  f as h io n .   As  g i v e n   i n   t h liter at u r s u r v e y   b elo w ,   th r esear c h   s o   f ar   h as  b ee n   f o cu s e d   o n   g r ad in g   th e   p er f o r m a n ce   o f   r o u ti n g   alg o r it h m s   b ased   o n   laten c y   an d   p ac k et  in j ec tio n   r ate.   Ho w e v er ,   th er h as  b ee n   lac k   o f   f o c u s   o n   s ize  o f   th m e s h ,   w h ic h   cr ea tes  d r a m a tic  ch a n g in   t h p er f o r m an ce   o f   t h e   r o u tin g   al g o r ith m .   Hen ce ,   th is   e x p er i m e n is   f o c u s ed   o n   e m p h as izin g   t h ef f e ct  o f   s ize  o n   p er f o r m a n ce   t h r o u g h   t h s i m u latio n s   ca r r ied   o u t o n   NOXI M.     1 . 1 .   P er f o r m a nce  d epe nd encie s   As  p r ev io u s l y   m en tio n ed ,   an   N o C   is   d is tin g u is h ed   b ased   o n   v ar iab les  s u ch   as   n etwo r k   to p o lo g y ,   r o u tin g   alg o r ith m ,   s witc h in g - tech n iq u e ,   an d   tr af f ic  p atter n .   No C   s y n th etic  tr af f ic  p atter n s   ar ess en tial  to o ls   f o r   No C   p er f o r m an ce  ass ess m en an d   d ev is in g   n ew  ar ch itectu r es.   Per f o r m an ce  o f   th No C   with   r esp ect  to   th s ize  o f   t h n etwo r k   is   d r am aticall y   d ep en d en o n   t h ese  f acto r s ,   th e   m ain   m etr ics  u s ed   f o r   th e   ev alu atio n   o f   p er f o r m an ce  ar th r o u g h p u an d   av er ag e p ac k et  d ela y ,   b u o u r   f o cu s   in   t h is   p a p e r   is   o n   Gl o b al  A v er ag e Dela y   ( la ten c y ) .       1 . 1 . 1 .   T o po lo g y   Net w o r k   to p o lo g y   is   s p atia l   ar r an g e m e n o f   n o d es  co n n e cted   to   f o r m   n et w o r k .   d is tin g u i s h ed   ar r ay   o f   to p o lo g ies  s u c h   as   M esh ,   T o r u s ,   R i C o B it  an d   B FT   etc.   h as  b ee n   d esi g n ed   to   s u i d if f er en s y s te m s   an d   th eir   n ic h ap p licatio n s .   Ho w e v er ,   f o r   all  g e n er al  p u r p o s s i m u lat io n   a n d   m o s r ea l - w o r ld   ap p licatio n s ,   Me s h   to p o lo g y   i s   u s e d   d u to   its   s i m p licit y   in   co n s tr u ctio n   a n d   d esig n i n g   r o u ti n g   alg o r it h m s .   M esh   T o po lo g y :   I is   th ea s i est  to   f ab r icate   o f   all   th e   ar r an g e m e n t s   as   all  n o d es  ar ar r an g ed   in   th e   o r d er   o f   an   m   x   n   m atr i x .   T h m atr ix   f o r m   f ac to r   allo w s   th n et w o r k   to   b f lat  an d   v er y   t h i n .     1 . 1 . 2 .   Ro uting   R o u ti n g   al g o r ith m s   d eter m i n e   th e   p ath   s elec ted   b y   p ac k e to   r ea ch   its   d esti n atio n .   R o u ter s   h a v b ee n   d e - s i g n ed   s u ch   th at   at  ea ch   i n ter m ed iar y   r o u ter ,   d ec i s io n   i s   m ad to   tr an s f er   t h p ac k et  i n   p ar ticu lar   d ir ec tio n   i.e .   n o r th ,   s o u t h ,   e ast,  w est   o r   lo ca ( to   I P ) .   R o u ti n g   al g o r ith m s   h a v t wo   b asic  ap p r o ac h es    1 )   Dete r m in i s tic  a n d   2 )   A d ap tiv [ 2 ] [ 6 ] .   T h d eter m i n i s ti alg o r ith m   n ee d s   n o   in f o r m a tio n   o th er   t h an   th e   s o u r ce   ad d r ess   an d   th d esti n atio n   ad d r ess   to   d eter m i n p ar tic u lar   r o u te  f o r   th p ac k et.   T h ad ap tiv e   alg o r ith m   h as  n o   p r ed ef in ed   r o u te  an d   i s   d eter m i n ed   d y n a m icall y   at  ea c h   r o u ter   b ased   o n   th n et w o r k   lo ad   an d   tr af f ic  co n d itio n s .   T h d eter m i n is tic  al g o r ith m s   ar p r o v en   to   b d ea d lo ck   an d   liv elo ck   f r ee   s i n ce   ea ch   p ac k et  w ill  ev e n t u all y   r ea ch   its   d esti n atio n .   Ho w e v er ,   p ac k et  late n c y   i n   s u ch   a n   alg o r i th m   w ill  i n cr ea s d r asti ca ll y   i f   m u ltip le  p ac k e t s   n ee d   to   tr a v el  ac r o s s   t h s a m c h an n el  [ 6 ] .   On   t h o t h er   h an d ,   ad ap tiv alg o r ith m s   ar p r o n to   d ea d lo ck   an d   liv elo c k ,   b e - ca u s t h e y   ar d ep en d en o n   th tr a f f i d en s it y   a n d   m a k d ec is io n s   b ased   o n   its   a v aila b ilit y .   T o   av o id   d ea d lo ck s   an d   liv elo c k s   ca u s ed   b y   p ac k ets  c y cli n g   ar o u n d ,   ce r tain   t u r n s   n ee d   to   b eli m i n ated   [ 6 ] .   Du to   co m p u tatio n   d ep en d en c y ,   it  is   le s s   e f f ici en to   u s ad ap ti v e   r o u tin g   at  lo w er   p ac k et  in j ec ti o n   r ate.   T h m o s t c o m m o n   r o u ti n g   al g o r ith m s   ar as  f o llo ws:   a.   XY  r o u ti n g T h is   i s   d eter m i n is t ic  r o u ti n g   al g o r ith m   i n   w h ich   t h p ac k et  f ir s t   tr av er s e s   a cr o s s   th e   a x i s   u n t il  t h s o u r ce   a n d   d esti n at io n   ar ali g n e d   in   th e   s a m co lu m n ,   a n d   t h en   it  tr a v er s e s   i n   t h Y - a x i s   d ir ec tio n   till   t h d esti n a tio n   i s   r ea ch ed .   An   alter n ate  d esi g n   to   th i s   w o u ld   b th Y r o u ti n g ,   w h ic h   h a s   th p ac k et  m o v alo n g   t h Y - a x is   f ir s f o llo w ed   b y   th o s i n   t h X - a x i s .   b.   W est  f ir s t:  T h is   is   a n   ad ap tiv e   alg o r ith m   in   w h ic h   p ac k ets  m u s f ir s tr av el  i n   th w e s t war d   d ir ec tio n   an d   th en   m o v to w ar d s   t h d esti n a tio n   w it h o u m ak in g   an y   m o v e m en ts   w e s t [ 7 ] .   c.   No r th   last :   A n a lo g o u s   to   t h e   p r ev io u s ,   t h is   is   a n   ad ap tiv alg o r ith m   m a k es  ad ap ti v d ec is io n s   i n   t h e   b eg in n i n g   a n d   th e n   f in al l y   allo w s   th p ac k e t to   tr av el  n o r t h war d s   to   its   d esti n atio n   if   n ee d e d   [ 7 ] .   d.   Neg ati v Firs t:  I n   t h is   ad ap t iv al g o r ith m ,   th p ac k et  m u s ad ap tiv e l y   m a k all  n e g ativ d ir ec tio n a l   m o v e m e n in   t h b eg i n n i n g   an d   th en ,   all  t h p o s iti v m o v e m en ts .   Neg a tiv m o v e m e n ts   h er ar d ef in ed   as  w e s t a n d   s o u t h   w h i le  p o s iti v m o v e m e n t s   ar n o r th   a n d   ea s t [ 7 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  8 ,   No .   5 Octo b er   2 0 1 8   :   3 3 6 8     3 3 7 3   3370   e.   Od d - E v e n T h is   ad ap ti v r o u t in g   p r o h ib its   ea s to   n o r th   t u r n s   a n d   ea s t   to   s o u th   tu r n s   at   an y   n o d i n   an   ev en   co lu m n .   I a ls o   d is a llo ws  n o r th   to   w est   t u r n s   a n d   s o u t h   to   w est   tu r n s   at  a n y   n o d in   an   o d d   co lu m n   [ 8 ] .   f.   D y A D:  D y n a m icall y   s w i tch i n g   b et w ee n   A d ap tiv a n d   D eter m i n is tic  r o u tin g   i s   th c u l m i n atio n   o f   t h e   ad v an ta g es  o f   b o th   d eter m i n is t ic  an d   ad ap tiv al g o r ith m s .   I co u ld   b co m b i n at i o n   o f   a n y   t w o   alg o r ith m s ,   s u ch   th at   it  co n ti n u o u s - l y   m o n ito r s   it s   lo ca n et w o r k   lo ad   an d   m ak e s   d ec is io n s   b ased   o n   t h is   in f o r m atio n   [ 6 ] .     1 . 1 . 4 .   Sy nthet ic  t ra f f ic  pa t t er ns   T h ese  ar s p ec u lat iv e   m o d els   o f   tr a f f ic  to   d e m o n s tr ate  h o w   th e   s i m u latio n   w o u ld   p r o g r e s s .   T h e y   d if f er   f r o m   r ea lis tic   m o d el s   t h at  ar b ased   o n   ce r tai n   b en ch m ar k   p r o g r a m s .   T r af f ic   p at ter n s   p r ed ef i n t h e   d esti n atio n   n o d f o r   p ar ticu l ar   s o u r ce   n o d e.   I n   o u r   s i m u lati o n s ,   w u s ed   th f o llo w i n g   [ 3 ] :   a.   R an d o m   p atter n E ac h   s o u r c n o d d is p atch es  p ac k et  to   an o th er   r an d o m   n o d at  th s p ec if ied   p ac k e t   in j ec tio n   r ate.   b.   T r an s p o s 1 I is   m atr i x - t r an s p o s p atter n   in   w h ich   e ac h   P E   p r esen in   ch ip   at  lo ca tio n   ( I ,   J )   d is p atch es a   m ess a g to   th P E   at  ( n       I ,   n     1   J )   f o r   an   ( n   x   n )   s ize  N OC .     c.   T r an s p o s 2 T h P E   p r esen t a t c h ip   ( I ,   J )   co m m u n icate s   o n l y   w it h   th n o d ( J ,   I )   in   th n e t w o r k .     1 . 2 .   L it er a t ure  s urv ey   No C s   h a v b ec o m e   th e   m o s s o u g h t - a f ter   ar ch itect u r d u t o   its   o v er w h el m i n g   ad v a n ta g e s   o v er   t h e   p r im iti v So C   m o d el.   T h a b ilit y   to   p r o v id e   h i g h er   s ca la b ilit y   a n d   r e - u s ab ilit y   g iv e s   i an   ed g o v er   it s   co m p eti to r s .   E x ten s i v r esear ch   h as  b ee n   d o n i n   d ev elo p in g   n e w   to p o lo g ies  an d   r o u tin g   alg o r it h m s .   L e s s   co n v e n tio n al  to p o lo g ies  li k e   th R i C o B it  h a v b ee n   e x p lain ed   w ith   f le s h ed   o u in f o r m at io n   a n d   also   p er f o r m a n ce   e v al u atio n s   i n   m an y   p ap er s   [ 9 ] .   T h r atio   o f   a v er ag t h r o u g h p u a n d   av e r ag p ac k et  d ela y   is   co m p u ted   to   co m p ar d if f er e n s i m u latio n s .   I is   s h o w n   t h at  Od d - E v e n   r o u ti n g   is   s u p er io r   to   XY  r o u ti n g   w it h   r atio   o f   2 . 5 3 5 8   as  co m p ar ed   to   2 . 1 1 2 6   r esp ec tiv el y   [ 1 0 ] .   T h p er f o r m a n ce   o f   XY  r o u tin g   i s   p r ef er ab le  at  u n i f o r m   tr a f f ic  p atter n s .   Fo r   n o n - u n i f o r m   tr a f f ic,   th lo ad   at  th ce n ter   o f   t h n et w o r k   is   h i g h er   t h an   t h e   av er ag n et w o r k   lo ad   lead in g   to   t r af f ic  h o t s p o [ 1 1 ] .   A n o th er   d is ad v an tag e   is   t h at  if   n o d is   f au lt y ,   th a t   p ac k et  w il r e m ain   b lo ck ed   o n   t h at   p ath   [ 1 2 ] .   Ho w ev er ,   X r o u ti n g   is   s i m p le   an d   h as   v er y   lo w   h ar d - w ar o v er h ea d   as  co m p ar ed   to   ad ap tiv r o u ti n g   [ 1 3 ] .   Un d er   d is tr i b u ted   tr af f ic  p atter n s ,   XY  r o u t in g   a n d   Od d - E v e n   r o u tin g   w o r k   b etter .   Ho w ev er ,   in   d ir ec ted   tr af f ic  f o r   m o s p r ac tical  cir cu m s tan ce s ,   D y AD   r o u tin g   w o r k s   b et - ter   th an   m o s o f   t h o th er   r o u tin g   al g o r ith m s   [ 1 4 ] .   I n v es tig ati n g   th d esi g n   o f   No C   b y   ev al u ati n g   its   p er f o r m a n ce   r eq u ir es  t h e   av ai lab ilit y   o f   f a s a n d   ac c u r a te  s i m u latio n   to o ls .   No x i m   i s   S y s te m C   b a s ed   o p e n   s o u r ce ,   c y cle  ac c u r ate  p latf o r m   f o r   t h s i m u latio n   o f   b o th   co n v en t io n al  w ir e - b ased   N o C s   an d   e m er g i n g   W iNo C   ar ch itectu r es.  Se v er a d o cu m en t s   ar av ailab le  f o r   g ettin g   s tar ted   o n   th s i m u lato r .   T h r o u tin g   a lg o r ith m s   u s ed   i n   t h is   p ap er   h av e   b ee n   d e v elo p ed   w it h   ad eq u ate  d o cu m e n tat io n .   An   elab o r ate  ar ticle   d escr ib in g   t h g e n er al  s y s te m   s tr u ctu r o f   t h No C   i s   av ailab le  to   p r o v id th n ec es s ar y   k n o w led g f o r   f u r t h er   s t u d y   [ 1 ] .       2.   RE S E ARCH   M E T H O D     W ev alu ate   th e   p er f o r m a n ce   o f   m e s h   n et w o r k s   o f   s ize s   v ar y in g   ( f r o m   4 x 4   to   1 0 x 1 0 )   b ased   o n   th e   af o r e - m en tio n ed   d ep en d en cie s   s u c h   as  tr af f ic  p atter n s ,   r o u t - i n g   al g o r ith m s   a n d   s w itc h i n g   s ch e m e s .   T r af f ic  p atter n s   co n s id er ed   ar r an d o m ,   tr an s p o s 1   an d   tr a n s p o s 2   [ 3 ] .   T h r o u tin g   al g o r ith m s   co n s id er ed   ar XY,   w e s f ir s t,  n o r th   last ,   n e g ati v f ir s t,  o d d   ev e n   &   D y AD  [ 6 ] - [ 9 ] .   S w itc h i n g   s c h e m es  u s ed   ar n ei g h b o r s   o n   p at h   ( NOP )   an d   b u f f er   le v el  s tr ate g y .   A ll t h test s   w er co n d u cte d   o n   NOXI M,   an   o p en   s o u r ce   S y s te m C   Si m u lato r   o f   m es h - b ased   No C   [ 1 ] .   T h r esu l ts   h a v b ee n   o b tain ed   w it h   r e - s p ec to   g lo b al  a v er ag d ela y   at   d if f er en t   p ac k et  in j ec tio n   r ates ( P I R )   o r   th r o u g h p u t f o r   th f o llo w in g   T ab le  1   co n f ig u r atio n s :       T ab le  1 .   Sim u latio n   S etti n g s   S e t t i n g   V a l u e   B u f f e r   D e p t h   4   S i z e   o f   F l i t s( i n   b i t s)   32   D y a d   T h r e sh o l d   0 . 6   S i mu l a t i o n   T i me ( i n   c y c l e s )   1 0 0 0 0   P a c k e t   S i z e ( i n   f l i t s)   8   P a c k e t   I n j e c t i o n   R a t e   0 . 0 0 8   t o   0 . 0 2 0   S e l e c t i o n   S t r a t e g y   B u f f e r   L e v e l ,   N O P     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       P erfo r ma n ce   A n a lysi s   o f Mes h - b a s ed   N o C s   o n   R o u tin g   A lg o r ith ms   ( A n a la   M.  R . )   3371   3.   RE SU L T A ND  AN AL Y SI S   T h p er f o r m a n ce   o f   No C s   i s   e v alu a ted   b ased   o n   t w o   d if f er e n tr a f f ic   p atter n s   ( r a n d o m ,   tr a n s p o s 2 )   an d   s w itc h i n g   s ch e m e s   ( Neig h b o r s   o n   P ath ,   b u f f er   le v el)   h av b ee n   m ad ac r o s s   f o u r   d i f f er en I n j ec tio n   r ate,   g iv in g   r i s to   d escr ip ti v l is ti n g   o f   F ig u r e   1   a n d   Fi g u r 2   th at  i llu s tr ate  h o w   ea c h   r o u tin g   al g o r ith m   p er f o r m s .   I n t u iti v el y ,   w ca n   r elate   th s ize  o f   t h m es h   w i th   t h d ela y   a s   d ir ec tl y   p r o p o r tio n al,   s i n ce   lar g er   ti m w o u ld   b r eq u ir ed   to   tr an s f er   th e   p ac k ets   ac r o s s   lar g er   n et w o r k s .   B u t,  r o u t in g   al g o r ith m s   h a v b ee n   d esig n ed   d if f er e n tl y   to   h a n d le   lig h a n d   h ea v y   lo ad s .   Mo r o f ten   t h an   n o t,  T r af f ic  p atter n s   m a y   f a v o r   ce r tain   p ath s   m o r t h an   o th er s   d u t o   co m m o n   d esti n atio n   n o d es   th is   ca n   b b etter   s h o w n   b y   th f o llo w i n g   t w o   tr af f ic  p atter n s .               ( a)       ( b )     ( c )           ( d )       ( e )     ( f )         ( g )     ( h )     Fig u r 1 ( a)   P I R   0 . 0 0 8 ,   T r a f f ic  P atter n : Ra n d o m   o n   s w itc h in g   s c h e m es:  NOP ( b )   P I R   =   0 . 0 1 2 ,   T r af f ic  P atter n : Ran d o m   o n   s w itc h i n g   s ch e m es: N OP ( c)   P I R   0 . 0 1 6 ,   T r af f ic  P atter n : Ran d o m   o n   s w itc h i n g   s ch e m es:  NOP ( d )   P I R   0 . 0 2 ,   T r af f ic  P atter n : Ra n d o m   o n   s w itc h i n g   s c h e m e s : N OP ( e)   PIR =   0 . 0 0 8 ,   T r af f ic  P atter n : Ran d o m   o n   s w itc h i n g   s c h e m e s : B u f f er   L e v el ( f )   P I R   0 . 0 1 2 ,   T r af f ic  P atter n : Ra n d o m   o n   s w itc h in g   s c h e m es: B u f f er   L e v el ( g )   P I R   0 . 0 1 6 ,   T r af f ic  P atter n : Ra n d o m   o n   s w itc h i n g   s ch e m e s : B u f f er   L e v el ( h )   P I R   0 . 0 2 ,   T r af f ic  P atter n : Ran d o m   o n   s w itc h i n g   s ch e m es: B u f f er   L e v el       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  8 ,   No .   5 Octo b er   2 0 1 8   :   3 3 6 8     3 3 7 3   3372           ( a)     ( b )       ( c)           ( d )     ( e)     ( f )             ( g )     ( h )       Fig u r 2 .   ( a )   P I R   0 . 0 0 8 ,   T r a f f ic  P atter n : T r an s p o s o s w itc h i n g   s c h e m e s : N OP ( b )   PIR =   0 . 0 1 2 ,   T r af f ic  P atter n : T r an s p o s 2   o n   s w itc h in g   s c h e m es:  NOP ( c )   P I R   0 . 0 1 6 ,   T r af f ic  P atter n : T r an s p o s 2   o n   s w i tch i n g   sc h e m es:  NOP ( d )   P I R   0 . 0 2 ,   T r af f ic  P atter n : T r an s p o s o n   s w itc h i n g   s ch e m es : N OP ( e)   P I R   0 . 0 0 8 T r af f ic  P atter n : T r an s p o s 2   o n   s w itc h i n g   s c h e m e s : B u f f er   L ev el , ( f )   P I R   0 . 0 1 2 ,   T r af f ic  P atter n : T r an s p o s 2   o n   s w i tch i n g   s c h e m e s : B u f f er   L ev el , ( g )   P I R   =   0 . 0 1 6 ,   T r a f f ic  P atter n : T r an s p o s 2   o n   s w itc h i n g   s c h e m e s B u f f er   L e v el , ( h )   P I R   0 . 0 2 ,   T r af f ic  P atter n : T r an s p o s 2   o n   s w itc h i n g   s c h e m e s : B u f f er   L ev el       I n   T r af f ic   p atter n :   R a n d o m ,   w h ic h   tr a n s f er s   p ac k ets   h ap h az ar d ly   to   a n y   d esti n atio n   n o d e,   in   b o t h   b u f f er   lev el  an d   NOP   s elec ti n g   s ch e m e,   XY  r o u ti n g   i s   s ee n   to   o u tp er f o r m   t h r est.  As  th o v er all  d is tr ib u tio n   o f   r eq u es ts   is   co n s id er ed ,   n o   tr af f ic  h o ts p o ts   e x i s t.  T h is   m ak es   th e   tr af f ic   d is tr ib u tio n   s ee m   m o r u n i f o r m .   Du to   th is ,   XY  r o u t in g   d o es n ' s p e n d   th ti m tr y in g   to   d eter m i n an d   s elec f r ee   p ath s   lik t h ad ap tiv e   alg o r ith m s .   T h is   b eh a v io r   o f   XY  r o u tin g   h o ld s   g o o d   ev en   at  h ig h   P I R   an d   lar g m es h   s i ze s   as  illu s tr ated   in   Fig u r e   1 ( d ) ,   Fig u r 1 ( e) ,   Fi g u r 1 ( i)   an d   Fi g u r e   1 ( j ) .   Ma k in g   it   m o r e   r eliab le  t h a n   e v en   D y AD   w h ich   s h o w s   co n s is ten tl y   h i g h er   d ela y   t h an   XY  as  s h o w n   in   Fig u r e   1 ( a)   an d   Fig u r e   1 ( b ) .   Ho w e v er ,   XY  r o u ti n g   d em o n s tr ate s   b etter   d elay   t h a n   th o th er   ad ap tiv al g o r ith m s   as  s h o w n   in   Fi g u r e   1 ( c)   a n d   Fig u r e   1 d ) .   T h is   m a y   b ac co u n ted   d u to   th f ac th at  it  h a s   to   d eter m i n w h ich   ap p r o ac h   to   p r o ce ed   w it h   an d   its   co m p lex it y   o f   h ar d w ar e.   D y AD  al s o   b eh a v es  a s   e x p ec ted   it  h a s   h i g h er   d ela y   at  lo w   P I R   in   b o t h   t h s elec tio n   s tr ateg ie s .   Ho w e v er ,   its   laten c y   r ed u ce s   w it h   an   i n cr ea s i n   P I R   as  it  b ec o m e s   m o r s tab le.   I h as  v er y   h i g h   d ela y   in   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       P erfo r ma n ce   A n a lysi s   o f Mes h - b a s ed   N o C s   o n   R o u tin g   A lg o r ith ms   ( A n a la   M.  R . )   3373   co m p ar is o n   to   o th er   alg o r ith m s   as  s ee n   in   F ig u r e   1 ( a)   to   Fig u r e   1 ( e) .   T h is   p atter n   is   v is ib le  o n l y   i n   NOP .   Ho w e v er ,   it  s h o w s   i m p r o v e m en in   late n c y   w it h   an   i n cr ea s in   P I R   u n d er   B u f f er   L e v el.   T h r em ai n i n g   ad ap tiv alg o r ith m s   h a v d elay s   r an g i n g   f r o m   m ed iu m   to   h i g h   v al u es.   I n   T r af f ic  p atter n T r an s p o s 2 ,   XY  r o u tin g   h a s   h i g h er   d ela y   th a n   it s   ad ap tiv co u n ter p ar ts   at  lo w   P I R   s u ch   as  0 . 0 0 8   an d   0 . 0 1 2   as  s h o w n   i n   Fi g u r 2 ( a) ,   Fig u r e   2 ( b ) ,   Fig u r e   2 ( f ) ,   Fig u r e   2 ( g ) ,   b u w i th   a n   in cr ea s i n   P I R   at  s izes  lar g er   th an   8 x 8 ,   it  g en er all y   p er f o r m s   b etter   th a n   t h ad ap tiv e   co u n ter p ar ts   D y A a n d   odd - ev en   as  i n d icate d   in   Fig u r 2 ( c) .   C o m p ar ed   to   th r e m ai n in g   ad ap tiv alg o r it h m s ,   Neg ativ F ir s t,  as   s h o w n   in   Fig u r 2 ( g ) ,   Fig u r e   ( 2 h )   s h o w s   h ig h   p er f o r m a n c at  m ed iu m   to   h i g h er   P I R .   T h is   is   b ec au s it  i s   b etter   s u ited   f o r   s en d in g   p ac k ets  to   o p p o s ite  en d s   as  it  ad ap tiv el y   a llo w s   in itial  n e g ati v m o v e m e n ts   an d   t h en   ad ap tiv el y   p o s iti v m o v e m e n t s ,   m ak i n g   t h e   d ela y s   s h o r ter ,   th o u g h   it s   la ten c y   in cr ea s e s   at   s m aller   m e s h   d u e   to   ex tr ti m s p e n in   m a k in g   m o r ad ap tiv d ec is io n s .     No r th   l ast  s h o w s   lo w   to   m ed iu m   d ela y   ac r o s s   all   f i g u r es  a n d   th is   m a y   b b ec au s n o r th   last   is   ad ap tiv i n   th b eg in n in g   an d   d eter m i n is tic   in   th en d   w ith   it s   ap p r o ac h .   Sin ce   alo n g   t h p r i n cip al  d iag o n al  i s   w h er m o s tr af f ic  w i ll  b co n ce n tr ated ,   th ad ap tiv e   f ir s t   n atu r e   o f   n o r th   last   m a k e s   it  f aster   th a n   th e   r est  at   lo w   to   m ed iu m   P I R   an d   lo w   to   m ed iu m   s ize.   W est  f ir s i s   s h o w s   s i m i lar ,   if   n o s li g h t l y   w o r s p er f o r m a n ce   in   co m p ar is o n   to   No r th   L ast.  D y AD  is   m o r s tab le  at  lo w   P I R   v alu 0 . 0 0 8   as  s h o w n   i n   Fig u r 2 ( a)   an d   Fig u r 2 ( f ) .   I t s   p er f o r m a n ce   w o r s en s   w it h   a n   i n cr ea s i n   b o th   th P I R   an d   th m es h   s ize.       4.   CO NCLU SI O N     I n   th i s   p ap er ,   w h a v ai m ed   at  d er iv in g   an d   p o r tr ay in g   t h ef f ec o f   v ar io u s   f ac to r s   o n   p er f o r m an c e   w it h   r esp ec to   t h s ize  o f   a n   No C .   I ca n   b co r r o b o r ated   u s i n g   t h g r ap h s   t h at  t h d eter m i n is tic  r o u ti n g   alg o r ith m   -   XY  i s   n o t   s tab le  d u to   its   f lu ct u ati n g   b eh a v io r   f o r   d if f er en t   co m b i n atio n s   o f   tr af f ic  a n d   m es h   s izes  ( i.e .   at  lo w   P I R   an d   s m a ll  m es h   s ize) .   A d ap tiv al g o r i th m s   li k W est  Fir s t,  No r th   L ast,  Neg ati v Fir s an d   Od d - E v e n   s h o w   th a th e s alg o r ith m s   ar q u ite  r eliab le  in   d ea lin g   w it h   ce r tai n   tr af f ic   p atter n s   b u s u f f er   f r o m   lar g er   d ela y   ac r o s s   lar g e r ,   less   co n g e s ted   m es h   s tr u ct u r es  d u to   in cr ea s ed   p ac k et  lat en c y   ca u s ed   b y   it s   m o r co m p le x   h a r d w ar e.   Fo r   lar g No C s   at  h ig h er   P I R s ,   X is   u n d o u b ted l y   m o r attr a ctiv al g o r ith m   f o r   m o s tr a f f ic  p atter n s   d u to   i ts   lack   o f   d ep en d en ce   o n   n et w o r k   lo ad .   Si n ce   t h p ath   o f   tr an s ac tio n   n e v er   ch an g es,  i is   i n d ep en d en o f   t h p ath   ta k e n   b y   alie n   p ac k et s   as  lo n g   as  it s   o w n   p at h   is   f r ee .   A s   lar g er   m e s h es  lack   i n   t h n u m b er   o f   co m m o n   p ath s ,   XY  i s   d ef i n itel y   b et ter   ch o ice  f o r   r o u ti n g   alg o r it h m .   Mo r eo v er ,   XY   r o u tin g   h as  a   s i m p le  i m p le m en tatio n   t h u s   h av in g   s m all  o v er h ea d   d u r i n g   p ac k et  tr an s it.  A s   s ee n   b y   th e   o b s er v atio n s   t h u s   f ar ,   th e   r es u lts   o b s er v ed   g o   h a n d   i n   h a n d   w it h   t h i n tr o d u ctio n ,   s h o w ca s in g   t h o v er all   ef f ec tiv e n e s s   o f   XY  r o u tin g   al g o r ith m   o v er   th o t h er   alg o r it h m s .       RE F E R E NC E   [1 ]   V in c e n z o   Ca tan ia,   e a l . ,   Cy c l e - A c c u ra te  Ne t w o r k   o n   Ch ip   S im u l a ti o n   w it h   No x im ,   ACM   T ra n s.  M o d e l.   Co mp u t.   S imu l. 2 7 ,   1 ,   A rti c le 4 ,   p p 1 - 21 ,   A u g u st 2 0 1 4 .   [2 ]   S u d h a n sh u   C h o u d h a ry   a n d   S h a f Qu re sh i ,   P e rf o rm a n c e   Ev a lu a ti o n   o f   M e sh - b a se d   N o Cs:  Im p lem e n tatio n   o f   a   Ne w   A rc h it e c tu re   a n d   Ro u ti n g   A lg o rit h m ,   IJ AC ,   A u g u st 2 0 1 2 ,   p p 5 - 10 .   [3 ]   Ja y a n Ku m a S in g h ,   P e rf o rm a n c e   Ev a lu a ti o n   o f   d if f e re n Ro u ti n g   A lg o rit h m in   Ne t w o rk   o n   Ch ip ,   M a ste r’s  T h e sis Ju n e   2 0 1 4 .   [4 ]   Z.   S h a rif i,   e a l . ,   Co m p a riso n   o f   No Ro u ti n g   A lg o rit h m u sin g   F o r m a M e th o d s” ,   Ju ly   2 0 1 3 ,   p p .   1 - 15 .   [5 ]   Jin g c a o   Hu   Ra d u   M a rc u les c u ,   D y AD S m a rt  Ro u ti n g   f o Ne tw o rk s - o n - Ch i p ,   A p ril   2 5 ,   2 0 0 4 ,   p p : 1 - 10 .   [6 ]   M a k sa A tag o z i y e v ,   Ro u ti n g   A l g o rit h m s f o o n   Ch i p   Ne tw o rk s” ,   De c e m b e 2 0 0 7 ,   p .   79 .   [7 ]   Ch risto p h e r   J.  G las s   a n d   L io n e M .   NI. ,   T h e   T u rn   M o d e f o A d a p ti v e   R o u t in g ,   S e p tem b e 1 9 9 4 ,   p p : 1 - 10 .   [8 ]   W a n g   Zh a n g ,   e a l . Co m p a riso n   Re se a rc h   b e t w e e n   X a n d   Od d - Ev e n   Ro u ti n g   A l g o rit h m   o f   a   2 - Dim e n sio n   3 X 3   M e sh   T o p o lo g y   Ne two rk - on - Ch i p ,   W RI  Glo b a l   Co n g re ss   o n   In tell ig e n S y ste ms ,   GS IS 0 9 ,   M a y   2 0 0 9 ,   p p .   3 2 9 - 3 3 3 .     [9 ]   P a n   Ha o ,   e a l . ,   Co m p a riso n   o f   2 M ES Ro u ti n g   A lg o rit h m   in   NO C” ,   2 0 1 1   IEE 9 th   I n ter n a ti o n a C o n fer e n c e ,   p p .   7 9 1 - 795 .   [1 0 ]   M .   Nic k ra y ,   e a l . ,   A d a p ti v e   R o u ti n g   Us in g   Co n tex t - Aw a re   Ag e n ts  f o Ne t w o rk o n   Ch ip s” ,   De sig n   a n d   T e st   W o rk sh o p   ( IDT),   2 0 0 9   4 th   I n ter n a ti o n a l ,   pp 1 - 6 ,   2 0 0 9 .   [1 1 ]   R.   Ho lsm a rk ,   e a l . ,   De a d lo c k   F re e   Ro u ti n g   A lg o rit h m f o M e sh   T o p o lo g y   No S y ste m s   w it h   Re g io n s ,   DS D   2 0 0 6 .   9 t h   EUROM ICRO  Co n fer e n c e   o n ,   p p.   6 9 6 - 7 0 3 .   Evaluation Warning : The document was created with Spire.PDF for Python.