（基础数学专业论文）并行互联网络的若干分析.pdf

摘要 摘要 计算机技术的发展突飞猛进。为了不断提高单机的性能，单个处理器的制造 已经快要达到物理极限了。单个芯片电路的集成度，以及频率升高带来的功耗问 题，都已经成为增强处理器处理能力的瓶颈。 为了达到更好的处理能力，以解决不断提高的应用需求，越来越多的超级计 算机已经使用许多处理器协同工作而构成并行计算机系统。无论是芯片级制造， 还是系统级集成，并行计算系统已经成为如今计算技术发展的主流方向。 并行计算机系统中，为了让各个处理单元更好的协同工作，各种网络互联模 式应运而生。好的网络互联拓扑结构应该能够在最大程度上支持各个处理单元的 高效通信，以期达到加速计算的目的。另一方面，运行在并行计算系统中的各种 应用，则应当根据所处的网络连接环境，来不断变化自己使用计算资源的方式， 以便达到更好的执行效率。应用与系统结构的高度一致，是迅速解决问题与有效 利用资源达到平衡的关键。 因此，在以应用驱动的网络设计中，我们应当充分考虑应用需求的特点，设 计出的网络结构才会更合理有效。同样，如果我们的应用程序需要运行在特定的 网络结构上，那么经过对网络结构的细致分析，并对我们的应用程序运行方式作 出恰当的调整，我们就能够达到事半功倍的效果。 对网络结构的传统的分析方法，在面对快速发展的并行计算需求时，已显示 出了不足之处。新型的分析方法和分析工具呼之欲出。应用要发展，理论要先行。 只有从理论上为网络结构分析奠定了基础，才会有更长足的进步。 本文旨在提出几种对于分析并行网络环境和并行应用非常有用的方法，希望 能够间接帮助提高应用程序的运行效率。 本文在第一章首先简要回顾了并行计算机结构的发展趋势，应用程序在并行 计算机结构上的运行方式，以及衡量效率时应参考的依据。 第二章主要介绍了几种常用的互联网络结构模型，并简单总结了几种通常用 于网络拓扑结构度量的指标。 第三章主要研究了等周问题在分析并行网络结构中的应用。等周问题源于几 何，但是等周方法却应用于各种领域。我们通过建立的等周数指标，详细分析了 摘要 在一种网络拓扑结构上，如何确定目标子结构的方式。等周集的确定就是应用程 序在并行计算机系统结构上映射方式的确定。等周方法为应用程序的映射与结构 选择提供了一种新思路。 第四章主要引入了社会网络分析中的几个概念，可以作为分析并行互联网络 结构的参考指标。 第五章是对全文内容的总结，以及对今后继续研究的几点想法。 关键词并行计算互联网络映射等周数介数指标 a b s t r a e t a b s t r a c t t h e c o m p u t e rt e c h n o l o g i e sh a v e b e e nt h r o u g h ar a p i dd e v e l o p m e n t i no r d e rt oi n - c r e a s et h ep e r f o r m a n c eo fas i n g l ep r o c e s s o r , i th a sb e e np u s h i n gh a r d w a r et e c h n o l o g y t ot h ep h y s i c a ll i m i to fc h i pm a n u f a c t u r i n g f a s td e n s e c i r c u i t r ya n dt h eh e a to u t p u t , a r et w om a i nb o t t l e n e c k sl i m i t i n gt h ef u r t h e rg r o w t ho fa p r o c e s s o r i no r d e rt oi m p r o v et h ep e r f o r m a n c e ，a n dt om e e tt h ei n c r e a s i n gd e m a n d s ，m o r e a n dm o r es u p e r c o m p u t e r sb e c o m ep a r a l l e lc o m p u t e r sc o n s i s t i n go fm a n y c o o p e r a t i n g p r o c e s s o r s p a r a l l e lc o m p u t e r s ，i n c l u d i n gp a r a l l e l i s mo nc h i p sa n dm u l t i p r o c e s s o rs y s t e r n s ，h a v eb e c o m et h em a i n s t r e a mo ft h ec o m p u t i n gt e c h n o l o g y i no r d e rt og e tb e t t e rc o o p e r a t i o nb e t w e e np r o c e s s o r si np a r a l l e lc o m p u t e r s ，v a r - i o u si n t e r c o n n e c t i o nn e t w o r km o d e l sh a v eb e e np r o p o s e d t h eb e s tn e t w o r ks t r u c t u r e c o u l ds i g n i f i c a n t l yi m p r o v et h ec o m m u n i c a t i o np e r f o r m a n c ea m o n gp r o c e s s o r s ，a c c e l c r a t i n gt h ec o m p u t a t i o n i na n o t h e rw a y , t h ep a r a l l e la p p l i c a t i o nc a ng e tb e t t e rc x c c u t i o nr a t eb yd y n a m i c a l l ya d j u s t i n gt h em a p p i n gs c h e m a sa c c o r d i n gt ot h en e t w o r k c i r c u m s t a n c e s t h eb a l a n c eb e t w e e ne x e c u t i o nt i m ea n dh i g hu s a g eo fr e s o u r c e si s b a s e do nt h ec o n s i s t e n c yo fa p p l i c a t i o n sa n da r c h i t e c t u r e s t h e r e f o r e ，i nt h ea p p l i c a t i o n - d r i v e nd e s i g no fn e t w o r k s ，i ti sm o r ep r a c t i c a li fw e f u l l yc o n s i d e rt h ef e a t u r e so fa p p l i c a t i o n s o nt h eo t h e rh a n d ，i ft h en e t w o r ks t r u c t u r e i sf i x e d ，t h ea p p l i c a t i o nr e q u i r e sl e s st i m ei fa n do n l yi fi ti sa d j u s t e dt ot h es p e c i f i c n e t w o r ks t r u c t u r e ，b a s e do nr e a s o n a b l ea n a l y s i s t h ec l a s s i c a la n a l y s i sm e t h o d so nt h en e t w o r k sh a v eb e e no u t - o f - d a t ew h i l ec o n - s i d e r i n gp a r a l l e li n t e r c o n n e c t i o nn e t w o r k s n e wm e t h o d sa n dt o o l sa r er e q u i r e de m e r - g e n t l y t h ea n a l y s i so fn e t w o r k sb e g i n si nt h e o r e t i c a la r e aa n dt h e na p p l i e so nr e a l i s t i c p r o b l e m s t h i sp a p e ri n t e n d st oi n t r o d u c es o m ea n a l y s i sm e t h o d su s e di ni n t e r c o n n e c t i o n n e t w o r k sa n dp a r a l l e la p p l i c a t i o n s ，s ot h a tt h ep e r f o r m a n c eo fa p p l i c a t i o n sm a yb e i m p r o v e d i nc h a p t e r1 ，w es h a uf i r s tr e v i e wt h et r e n d si np a r a l l e la r c h i t e c t u r e s 。t h em a p p i n g a b s t r a c t s c h e m e so fp a r a l l e la p p l i c a t i o na n dt h ee f f i c i e n c yc o n s i d e r a t i o n s e v e r a lb a s i ci n t e r c o n n e c t i o nn e t w o r ks t r u c t u r e sa r er e v i s e di nc h a p t e r2 a n dt h e b a s i ci n d i c a t o r su s e dt om e a s u r en e t w o r k sa l ei n t r o d u c e d , t o o c h a p t e r3i sf o c u s e do nt h ei s o p e r i m e t r i ca n a l y s i so fi n t e r c o n n e c t i o nn e t w o r k s a n dp a r a l l e la p p l i c a t i o n s t h ei s o p e r i m e t r i cm e t h o di sf r o mg e o m e t r y , b u tn o wi s a p p l i e di nv a r i o u sf i e l d s w eg i v eac o m p r e h e n s i v ea n a l y s i so ft h ei s o p e r i m e t r i cp r o p - e r t i e so fk - d e g r e 宅c a y l e yg r a p h s ，a n dt h ew a yt of i n dt h ei s o - p e r i m e t r i cs e t s o n c e a ni s o - - p e r i m e t r i cs e ti sf o u n d , t h em a p p i n go fp a r a l l e la p p l i c a t i o n so n t ot h ei n t e r c o n - - n e c t i o nn e t w o r ki ns t r a i g h t - f o r w a r d t h ei s o - p e r i m e t r i cm e t h o dp r o v i d e san e ww a y c o n s i d e r i n gp a r a l l e lm a p p i n g sa n dt h el o c a ls t r u c t u r eo fn e t w o r k s s e v e r a li n d i c a t o r sp o r t e df r o ms o c i a ln e t w o r ka n a l y s i sa r ei n t r o d u c e di nc h a p t e r 4 t h e s ei n d i c a t o r sa r er e c o m m e n d e df o ra n a l y z i n gi n t e r c o n n e c t i o nn e t w o r k s c h a p t e r5c o n s i s t so fc o n c l u s i o n sa n dr e l a t e df u t u r ew o r k k e yw o r d sp a r a l l e lc o m p u t i n g i n t e r c o n n e c t i o nn e t w o r k p a r a l l e lm a p p i n g i s o p e r i m e t r i cn u m b e r b e t w e e n n e s sc e n t r a l i t yi n d i c a t o r s 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：童、乡胁 。2 椰年j ，月；口日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 名序 、。 q 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：季、劈 0 。8 年j 具；ae l c h a p t e r1 i n 仃o d u c f i o n c h a p t e r1 i n t r o d u c t i o n 1 1t r e n d si np a r a l l e la r c h i t e c t u r e c o m p u t e ra r c h i t e c t sh a v ea l w a y ss t r i v e dt oi n c r e a s et h ep e r f o r m a n c eo f t h e i rc o m - p u t e ra r c h i t e c t u r e s e n du s e r sa l w a y se x p e c tt h e i rp r o g r a m sr u n n i n gf a s t e r h i g hp e r f o r m a n c em a yc o m ef r o mf a s td e n s ec i r c u i t r y , p a c k a g i n gt e c h n o l o g y , a n d p a r a l l e l i s m 1 1 n o w a d a y s 。s e r i a l p r o c e s s o rc o m p u t e r sh a v ea c h i e v e du n h e a r d - o fs p e e d s t h es p e e do fas e r i a lc o m p u t e ri sd i r e c t l yd e p e n d e n tu p o nh o wf a s td a t ac a l lm o v e t h r o u g hh a r d w a r e a b s o l u t el i m i t sa r et h es p e e do fl i g h t ( 3 0 c m n a n o s e c o n d ) ，a n dt h e t r a n s m i s s i o nl i m i to fc o p p e rw i r e ( 9 c n g n a n o s e c o n d ) i n c r e a s i n gs p e e d sn e c e s s i t a t e i n c r e a s i n gp r o x i m i t yo fp r o c e s s i n ge l e m e n t s t h ef a m o u sm o o r e sl a w 【2 】h a sa p p r o x i m a t e l yp r e d i c t e dt h eg r o w t ho fc o m p l e x i t y i ni n t e g r a t e dc i r c u i t sf o rt h el a s tf o u rd e c a d e s h o w e v e r , i th a sb e e np u s h i n gh a r d w a r e t e c h n o l o g yt ot h ep h y s i c a ll i m i to fc h i pm a n u f a c t u r i n g s o o nt h i st r e n dw i l lc o m et oa l l e n d l 3 , 4 】i na d d i t i o n d o u b l i n gt h ef r e q u e n c yq u a d r u p l e st h eh e a to u t p u t 5 1 c o n s i d e r - i n gp o w e r p e r f o r m a n c ea n dc o s t p e r f o r m a n c ei m p r o v e m e n t ，p h y s i c a la n da r c h i t e c t u r a l b o u n d sl i m i tt h ec o m p u t a t i o n a lp o w e rt h a tc a nb ea c h i e v e dw i t has i n g l ep r o c e s s o r s y s t e m f r o mt o p 5 0 0s u p e r c o m p u t e rl i s t1w ec o u l ds e et h a ta l lt h ef a s t e s ts u p e r c o m p u t e r s i nt h ew o r l da r es o m ek i n do fp a r a l l e lc o m p u t i n gs y s t e m s p a r a l l e lc o m p u t i n gs y s t e mi sc o n s i s t i n go fm u l t i p l ep r o c e s s i n gu n i t sc o n n e c t e dv i a s o m ei n t e r c o n n e c t i o nn e t w o r kp l u st h es o f t w a r en e e d e dt om a k et h ep r o c e s s i n gu n i t s w o r kt o g e t h e r i n t e r c o n n e c t i o nm e c h a n i s m so fp r o c e s s i n ge l e m e n t si n c l u d es h a r e db u s f a b r i c s ，c r o s s b a r s t 6 ，s w i t c hb a r s ，e t h e m e t , e t c a c c o r d i n gt ot h eh a r d w a r ea r c h i t e c t u r e ， p a r a l l e lc o m p u t i n gs y s t e mc o u l db ec a t e g o r i z e di n t ot h ef o l l o w i n gl e v e l s m u l t i c o r e s m a n yp r o c e s s i n ge l e m e n t sa r ei n t e g r a t e di nas i n g l es i l i c o nc h i pa sa p r o c e s s o r i n s t r u c t i o n sa n dd a t af l o w sa m o n gp r o c e s s i n ge l e m e n t sm a yb ed i f f e r - l h t t p ：w w w t o p 5 0 0 o r g 1 m u l t i p r o c e s s o r sp r o c e s s o r sc o o p e r a t e b ys h a r e d m e m o r yo rs p e c i f i c i n t e r c o n n e c d o n s l i k e f p g a - b a s e ds w i t c h e r so r t o u t e r s ，e t c m u l t i s e i - v e l r sa l ls e l w e f sa mc o n n e c t e dt h r o u g hn e t w o r ki n t e r f a c e se t h e r n e ta n d m y r i n e ta t eo f t e nu s e d h y b d ds e v e r a l t e c h n o l o g i e sa b o v ea r eu s e d f o r m i n ga m o r ec o m p l i c a t e ds y s t e m 国国圄圄圄圄国国 目e 】b 口d e 口日口b 毋口s 口口霸口口 = = = = = = j i 日t = = = = = = p 二仁啬 i 匡曼罢 ( a ) c c l l be m ) r a p p o r t k c 2 5 6 燕翟 蠕 ( c ) s g ia l 恤q ) b l u c g e n e p 吐k a g i n g f i g u r ei 1s o m e m a i n s 吨a ms u p e r c o m p u t e ra r c h l t e e t u 忙s i nf i g u r el1 w el i s ts o m em a i n s t r e a ms u p e r c o m p u t e ra r c h i t e c t u r e st h ec e l l b r o a d b a n de n g i n ei n t e g r a t e s9p r o c e s s i n ge l e m e n t sa sap r o c e s s o r , w h i l er a p p o r t k c 2 5 6h a s2 5 6p r o c e s s i n ge l e m e n t si no n ec h i pi ns g ia l t i xs e r v e r s ，f p g a 。b a s e d 2 r e c o n f i g u r a b l ea p p l i c a t i o ns p e c i f i cc o m p u t i n gt e c h n o l o g y ( n u m a l i n k ) l e v e r a g e st h e p e r f o r m a n c eo ft h es y s t e m t h eb l u eg e n es u p e r c o m p u t e rm i g h tb et h em o s tp o w e r f u lc o m p u t i n gs y s t e mi n t h ew o r l dt o d a y i nt h el a t e s tt o p 5 0 0l i s tr e l e a s e di nn o v e m b e r2 0 0 7 ，t h e r ew e r e4b l u e g e n es y s t e m si nt h et o p1 0s u p e r c o m p u t e r s 嘶”秽州咛 9 ”5 p ”。”。”州“弼嚣 t o a n df r o m j ， m i d p l a n e t o a n d ，：。0 ， 孙绷 f r o m _ - 毒毒，f r o m 霉rk 雌。o 翻l 嚣 秘婚燃乞嘶翩l c 鼢 h g u r e1 2 i n t e r c o n n e c t i o nn e t w o r ko f b l u eg e n e a ss h o w ni nf i g u r e1 2 ，t h eb l u eg e n es y s t e mu s e st o m sa si t si n t e r c o n n e c t i o n n e t w o r k s e a c hn o d ec a r d ( o rr a n k ) i sf o r m e db y4 4 2t o m so fc o m p u t e ( o rn o d e ) c a r d s f i g u r e1 3 m a x i m u mn u m b e ro f p r o c e s s o r su s e di nt o p5 0 0s u p e r c o m p u t e r s a l o n gw i t ht h ee v o l u t i o n a r ya r c h i t e c t u r e s ，t h en u m b e ro fp r o c e s s o r su s e di ns u 一 3 c h a p t e r1 i n t r o d u c t i o n p e r c o m p u t e r sb e c o m el a r g e ra n dl a r g e r a sw ec a n s e ef r o mf i g u r e1 3 ，t h eb e t t e rp e r - f o r m a n c ew ew a n tt oa c h i e v e ，t h em o r ep r o c e s s o r sw en e e d o b v i o u s l y , t h es t r u c t u r e s a n di n t e r c o n n e c t i o nm e c h a n i s m sa r eg o i n gt ob em o r ea n dm o r ec o m p l i c a t e d ，w h i c h m a k e sc o m p r e h e n s i v ea n a l y s i so ni n t e r c o n n e c t i o nn e t w o r k sa ni m p o r t a n ta s p e c t 1 2 m a p p i n g a n de f f i c i e n c y u n l i k et h es e q u e n t i a lp r o g r a m sw em so n o u r p e r s o n a lc o m p u t e r s ，w h e nw ew a n t t os o l v eap r o b l e mo nap a r a l l e lc o m p u t e r , w en e e dt os p r i tt h ep r o b l e mi n t os e v e r a l s u b - p r o b l e m s t h e s es u b - p r o b l e m sm a ym u t u a l l yb ed e p e n d e n to nt h eo t h e r s m o s t p a r a l l e lp r o g r a m sc a nb ed e s c r i b e du s i n gag r a p hf o r m a l i s m ( s e ef i g u r e1 4 ) i nm o s t r e p r e s e n t a t i o n s ，e a c hv e r t e xr e p r e s e n t sat a s ka n de a c he d g eac o m m u n i c a t i o nl i n k i n t h ef o l l o w i n g ，w ew i l ld e n o t e ：t ，t h es e to ft a s k sa n d 扎t h e i rn u m b e r , p t h es e to f p r o c e s s o r sa n dm t h e i rn u m b e r w eh a v et oc o n s i d e rt h ec o m p u t a t i o nc o s t so ft h et a s k s ( e x e c u t i o nt i m e ) a n dt h e a m o u n to fi n f o r m a t i o nc o m m u n i c a t e do nt h el i n k s s o m e t i m e s ，w ec a nn o td e t e r m i n e t h ee x a c tv a l u e so ft h ep r o g r a mp a r a m e t e r sb u tc a no n l ya p p r o x i m a t et h e m g e n e r a l l y , c o m m u n i c a t i o nb e t w e e nt w op r o c e s s o r si sm u c hm o r et i m ec o n s u m i n gt h a nc o m m u n i c a t i o nb e t w e e nt w ot a s k sa l l o c a t e dt ot h es a n l ep r o c e s s o r , w h i c ha m o u n t st oal o c a l m e m o r ya c c e s s 1 2 s f i g u r e1 4 i n s t a n c e so f o fat a s kg r a p ha n dap r o c e s s o rn e t w o r k o b v i o u s l y , w en e e dt of i n dam a p p i n g 口：thp 。o nw h i c hw ew i l ls a t i s f yt h e 4 c h a p t e r1i n t r o d u c t i o n e x e c u t i o np e r f o r m a n c e w ec a nr o u g m yd i s t i n g u i s ht w oc l a s s e so fm e t h o d s ，n a m e l y , e x a c ta l g o r i t h m sa n dh e u r i s t i c s t t l m a n ys o l u t i o n sc a nb ef o u n di nt h el i t e r a t u r ef o r s o l v i n gt h em a p p i n gp r o b l e m t 8 - 1 1 b a s i c a l l y , w eh o p et h a tt h ee x e c u t i o nt i m ei sa ss h o r ta sp o s s i b l e s i n c ei n t e r - p r o c e s s o r sc o m m u n i c a t i o n i sm u c hm o r et i m e a s s u m i n gt h a ni n n e r - p r o c e s s o r sc o m m u n i c a t i o n a d d i t i o n a l l y , u n b a l a n c e dm a p p i n ga m o n gp r o c e s s o r sw o u l di n e v i t a b l yc a u s e t h a ts o m ep r o c e s s o r sa r e h i g h l yl o a d e da n do t h e r si d l e 。t h e r e f o r e ，t w oo p p o s i t ec r i t e r i a h a v et ob et a k e ni n t oa c c o u n t ：m i n i m i z a t i o no fi n t e r - p r o c e s s o r sc o m m u n i c a t i o n sa n d l o a d - b a l a n c i n go fc o m p u t a t i o n sb e t w e e np r o c e s s o r s w em i g h tf i n dt h a ti ti si m p o s s i b l et os p e e d - u pt h ee x e c u t i o n b yw h a t e v e rm a p p i n g m e t h o d s i nt h i se x t r e m ec a s e ，w em a yh a v et og ob a c kt ot h ep a r a l l e lf o r m a l i s mo ft h e p r o b l e mi nt h eb e g i n n i n g 。t of i n ds o m eu n r e a s o n a b l ei s s u e sw h i l es p l i t t i n gi t b yr e f o r m a l i z a t i o no ft h ep r o b l e mi nad i f f e r e n tw a y , a n o t h e rw o r l dc o u l db ei nt h ef r o n t i np r a c t i c e m o s to ft h ep r o b l e m sa n dm a p p i n gm e t h o d sa r et o p o l o g y a w a r e t l 2 1 3 1 t h e r e f o r e ，c a r e f u la n a l y s i so ft h ep r o b l e ma n dt h ei n t e r c o n n e c t i o nt o p o l o g yi sv i t a l b e f o r ep e r f o r m i n ga n yr e a l i s t i cc o m p u t a t i o n 1 3o v e r v i e wa n do u t l i n e a l o n gw i t ht h ed e v e l o p m e n to fp a r a l l e ls u p e r c o m p u t e r s ，t h ei n t e r c o n n e c t i o nn e t - w o r k sw i l lb e c o m em o r ec o m p l i c a t e d e x i s t i n ga n a l y t i c a lt o o l sw o u l dd e f i n i t e l yh a v e t o om a n yd i f f i c u l t i e st oc o p ew i t he v e r - c h a n g i n gi n t e r c o n n e c t i o nn e t w o r k s i th a sr e c e s s i t a t e dd e v e l o p i n gp r o p e rt o o l sf o r a n a l y z i n gi n t e r c o n n e c t i o nn e t w o r k st o w a r d sp a r - a l l e la p p l i c a t i o n s i nc h a p t e r2 ，w es h a l lr e v i e wt h eb a s i ct o p o l o g i e sf o r b u i l d i n gi n t e r c o n n e c t i o nn e t - w o r k s ，t h e i rd e r i v a t i v e s ，a n dt h ec o m m o ni n d i c a t o r sw h i c hh a v eb e e nu s e dt om e a s u r e t h es t r u c t u r a lp r o p e r t i e so fn e t w o r k s c h a p t e r3i sd e v o t e dt ot h ei s o p e r i m e t r i cp r o p e r t i e so fn e t w o r k s i s o - p e r i m e t r i c m e t h o d sa r ep o r t e df r o mg e o m e t r y , a n dn o wa p p l i e di nv a r i o u sf i e l d s w es h a nc o n c e n t r a t eo nt h ei s o - p e r i m e t r i ca n a l y s i so i lan e wi n t r o d u c e dn e t w o r k ，k - d e g r e ec a y l e y g r a p h ，b yc o m p r e h e n s i v ed i s c u s s i o n s ，w es h a l lp r e s e n tt h ep r o p e r t i e so nt h el o c a l s t r u c t u r eo fn e t w o r k s ，w h i c hp r o v i d e su sab e t t e rg u i d a n c et od oe f f i c i e n tm a p p i n g s 5 a n da l s o ，w eb r i n gi s o