（计算机应用技术专业论文）复杂网络中的计算迁移问题.pdf

东 北大学博士学位论文 摘要 复杂网络中的计算迁移问题 摘要 在过去的几年中，复杂网络的研究得到了迅速的发展，已经遍及各个学科 领域， 如生物学、 物理学， 甚至社会科学， 究其原因可以把它归结为以下两点: ( 1 ) 随着计算能力的提高， 使人们能够对包含数以千万计节点的各种现实网络 进行研究，这在以前是无法实现的;( 2 )人类迫切需要从整体上去认识各种复 杂网络内部各部分之间的相互关系，以揭示出具有某些指导意义的宏观规律。 经研究发现， 大量的实际网络都具有复杂网络的一些特征， i n t e r n e t 就是其中的 一个典型代表。 “ 计算”作为理论和实验二者之间的桥梁，已成为一种重要的科学研究方 式，在很多领域中己经成为一种重要的甚至是不可替代的解决问题的方法和工 具。但随着人们求解问题领域的不断拓展，所遇到的问题也越来越复杂，而且 规模也越来越大，解决这些问题所需要的计算能力也在大幅度提高。在这些新 问题的求解过程中，局部的计算资源已经无法满足这样的计算需求，因此打破 地域的限制来实现更大粒度和更大范围的资源共享就成为一种必然的需求。而 i n t e r n e t 作为一种集成了各种计算资源、 存储资源、 信息资源的超大规模的复杂 网络计算平台，无疑为解决以上需求提供了良好的计算环境支持，但同时还有 一些问题需要解决。 i n t e rn e t 作为迄今为止最复杂的人工系统， 在其杂乱无章的表象下却隐藏着 令人吃惊的大范围模式的秩序与结构。为此，本文通过分析研究 c a i d a 的 s k i t t e r 项目 提供的 i n t e r n e t 监测数据中蕴藏的某些复杂网络的特征和规律，来 研究复杂网络上的计算迁移问题。 提出了 “ 计算迁移”的思想。由于处在不同地域的用户对计算需求的不平 衡性，导致了 i n t e rn e t 上的资源呈现出不均匀分布，即在一些小生境中，资源 丰富，而在另外一些小生境中，却资源匾乏。另外，i n t e r n e t 上各种网络设备的 移动性和链路的多变性，使资源不再固定或稳定，而是动态变化的。在这种资 源动态变化以及分布不均匀的环境中，为了实现有限资源的最大化利用，当本 东北大学博士学 位论文摘要 地的资源有限，或剩余资源己不能满足用户计算任务的需求时，将计算任务迁 移到资源丰富，运行环境良 好的节点上继续运行，将能得到更好的性能表现。 即计算任务随资源的变化而进行迁移，实现 “ 资源在哪里，就到哪里计算，o 由于 i n t e rn e t 上资源分布的动态性，为了能有效利用其上的资源，资源发 现也是本文要解决的一个问题。针对 i n t e r n e t 网络拓扑结构中节点的度分布存 在 “ 幂律”分布，以及i n t e rne t 网络中存在 “ 小世界”的特征，引入 t c p / i p中 动态路由的思想，提出一种新的资源发现算法一连接度优先路由查找 ( c f r ) 算法。该算法能有效降低网络节点之间的通信开销和减少对每个查询进行处理 的节点数量，解决了传统的 “ 广播扩散”方式来搜索网络上共享资源而造成网 络流量急剧增加的问题。 基于c f r算法和“ 计算迁移” 思想， 提出了资源可用度计算迁移策略。 在 该策略中，将资源的可用度作为选择 “ 迁移目的地”的衡量标准，并借鉴旅行 计划的方法，实现了基于计算体的计算迁移过程，解决了由于资源的动态变化 以及分布的不均匀而导致的计算迁移问题。 仿真实验对c f r算法和资源可用度计算迁移策略的测试结果表明， 与传统 的资源查找算法相比， c f r算法能有效降低资源查找时的网络流量， 提高资源 查找速度。 在c f r算法的基础上， 资源可用度计算迁移策略能在更快的时间内 将计算任务迁移到满足资源需求的节点上， 从而实现了复杂网络上的计算迁移。 关键词复杂网络 计算迁移 资源发现 幂律 无尺度网络 c f r迁移策略 东 北大学博士学位论文 abs tract c o mp u t i n g m i g r a t i o n i n c o mp l e x ne t wo r k s abs t r act o v e r p as t f e w y e a r s , t h e r e s e a r c h o n c o m p l e x n e t w o r k h a s b e e n d e v e l o p e d r a p i d l y a n d e x t e n d e d m a n y s c i e n c e fi e l d s , s u c h a s b i o l o g y , p h y s i c s a n d s o c i a l s c i e n c e . i t b o i l s d o w n t o t w o r e a s o n s : ( 1 ) wit h t h e i m p r o v e m e n t o f c o m p u t i n g c a p a b i l i t y , p e o p le c a n r e s e a r c h v a r i o u s r e a l i s t i c n e t w o r k s i n c l u d i n g m u l t i m i l l i o n n o d e s . i t c o u l d n o t b e r e a l i z e d i n t h e p as t ; ( 2 ) p e o p l e n e e d t o r e c o g n i z e v a r i o u s n e t w o r k s u r g e n t l y t o f i n d o u t i n s t r u c t i o n a l m a c r o s c o p i c a l - r u l e s . t h e r e s e a r c h d i s c o v e r e d t h a t m a n y p r a c t i c a l n e t w o r k s h a v e s o m e c h a r a c t e r i s t i c s o f c o m p l e x n e t w o r k s , a n d i n t e rn e t i s a t y p i c a l o n e . c o m p u t i n g as a b r i d g e b e t w e e n t h e o ry a n d e x p e r i m e n t h as b e c o m e a n i m p o r t a n t s c i e n c e r e s e a r c h m e t h o d . i n m a n y f i e l d s c o m p u t i n g h as b e c o m e a n i m p o r t a n t t o o l w h i c h c a n n o e b e s u b s t i t u t e d . f o l l o w i n g t h e n e w p ro b l e m e m e r g e n c e , h o w e v e r , t h e p r o b l e m s a r e b e c o m i n g m o r e a n d m o r e c o m p l e x a n d t h e s c a l e s a r e m o re a n d m o r e b i g , as a r e s u l t , it i s n e c e s s a r y t o i m p r o v e m e n t t h e c a p a c i t y o f s o l v i n g t h e p r o b l e m . a m o n g t h e s e n e w p r o b l e m s b e s o l v e d , l o c a l c o m p u t i n g r e s o u r c e s h a d n t m e e t t h e n e e d , s o i t i s a k i n d o f r e q u i r e m e n t t o b re a k t h e l i m it e d o f z o n e a n d r e a l i z i n g b i g g e r g r a n u l a r i ty a n d b i g g e r s c a l e r e s o u r c e s - s h a r i n g . a s a s u p e r b i g s c a l e c o m p l e x n e t w o r k c o m p u t i n g p l a t f o r m i n t e g r a t i n g a l l k i n d s o f c o m p u t i n g r e s o u r c e s , s t o r a g e r e s o u r c e s , i n f o r m a t i o n r e s o u r c e s i n t e rne t i s a f a v o r a b l e c o m p u t i n g c i r c u m s t a n c e , b u t i t s t i l l h as s o m e p r o b l e m s t o r e s o l v e a s t h e m o s t c o m p l i c a t e d a r t i f i c i a l s y s t e m , i n t e rne t h i d e s o r d e r a n d s t r u c t u r e o f h u g e s c a l e m o d e , w h i c h i s s t a r t l i n g . s o t h e t h e s i s s t u d i e d t h e p r o b l e m o f c o m p u t i n g m i g r a t i o n o n c o m p l e x n e t w o r k b y a n a l y z i n g t h e d a t a o f i n t e rn e t , w h i c h w e re s u p p o r t e d b y s k i tt e r p r o j e c t o f c a i d a . t h e i d e a o f c o m p u t in g m i g r a t i o n i s p u t f o r w a r d . b e c a u s e o f t h e u n b a l a n c e r e q u i r e m e n t s o f c o m p u t i n g o f u s e r fr o m d i ff e r e n t z o n e , it l e a d s t o u n e q u a l d i s t r i b u t i n g , i n o t h e r w o r d s , r e s o u r c e s i s a b u n d a n t i n s o m e l i tt l e fi e l d w h i l e i t i s l a c k i n t h e o t h e r . o t h e r w i s e b e c a u s e o f m o b i l i ty o f v a r i o u s e q u i p m e n t s a n d v o l a t i l i t y o f l i n k o n i n t e rn e t , t h e r e s o u r c e i s u n s t a b l e a n d d y n a m i c . u n d e r t h i s d y n a m i c a n d u n e q u a l c o n d i t i o n , w e w 东北大学博士学位论文abs t ract m o v e d t h e c o m p u t i n g t as k t o t h e n o d e s t h a t h a v e a b u n d a n t r e s o u r c e s a n d f a v o r a b l e c i r c u m s t a n c e t h e n r e p r e s e n t t h e b e tt e r p e r f o r m a n c e i n o r d e r t o m a x u t i l i z e l i m i t e d r e s o u r c e s . t h e m o v i n g o f c o m p u t i n g t a s k i s f o l l o w i n g w i t h t h e c h a n g e o f r e s o u r c e s a n d a c h i e v e w h e r e r e s o u r c e s , w h e r e c o m p u t i n g . b a s e d o n t h e i d e a o f c o m p u t i n g m i g r a t i o n , i e l a b o r a t e t h e m i g r a t i o n s t r a t e g y b a s e d o n r e s o u r c e s a v a i l a b i l i ty i n t h i s s t r a t e g y , i r e g a r d t h e r e s o u r c e s a v a i l a b i l i ty a s a c r i t e r i o n t o s e l e c t m i g r a t i o n d e s t i n a t i o n , a c h i e v e t h e p r o c e s s o f c o m p u t i n g m i g r a t i o n b y c o n s u l t i n g t h e i d e a o f i t in e r a ry , a n d r e s o l v e t h e p r o b l e m a b o u t c o m p u t i n g m i g r a t i o n r e s u l t i n g f r o m d y n a m i c v a r i e t y a n d d i s t r i b u t i n g as y m m e t ry o f r e s o u r c e s c o n s i d e r i n g t o d y n a m i c o f r e s o u r c e s d i s t r i b u t i n g , r e s o u r c e s d i s c o v e r y i s a n o t h e r p r o b l e m t h a t t h e t h e s i s n e e d s t o r e s o l v e t o w e l l u t i l i z e re s o u r c e s . a i m a t t o p o l o g y o f i n t e r n e t , t h e n o d e s d e g r e e e x i s t p o w e r - l a w d i s t r i b u t in g a n d t h e r e i s s m a l l w o r l d i n i n t e rn e t , i i n t r o d u c e t h e i d e a o f d y n a m i c r o u t i n g i n t c p / i p , a n d p u t f o r w a r d a n e w r e s o u r c e f i n d i n g a l g o r i t h m -c o n n e c t i o n - d e g r e e f i r s t r o u t i n g ( c f r ) . t h e m e t h o d c a n e ff e c t i v e l y r e d u c e c o m m u n i c a t i o n o v e r h e a d a m o n g n o d e s , a n d s o l v e t h e p r o b l e m o f n e t w o r k fl o w d r a s t i c a l l y i n c r e a s e b e c a u s e o f u s in g t h e t r a d i t i o n a l b r o a d c a s t i n g m e t h o d t o s e a r c h s h a r e d r e s o u r c e s . t h e r e s u l t s o f s im u l a t i o n e x p e r i m e n t o n c f r a n d t h e m i g r a t i o n s t r a t e g y b as e d o n t h e r e s o u r c e s a v a i l a b i l i ty i n d i c a t e c f r c a n e ff e c t i v e l y r e d u c e n e t w o r k fl o w a n d im p r o v e t h e s p e e d o f r e s o u r c e s s e a r c h . o n t h e o t h e r h a n d , c o m p a r e t o r a n d o m m i g r a t i o n , t h e m i g r a t i o n s t r a t e g y b as e d o n t h e r e s o u r c e s a v a i l a b i l i ty c a n s p e n d s t h e l e s s t i m e t o m o v e c o m p u t i n g t as k s t o t h e e x p e c t e d n o d e a n d a c h i e v e c o m p u t i n g m i g r a t i o n i n c o mp l e x n e t w o r k s . k e y w o r d s c o m p l e x n e t w o r k , c o m p u t in g m i g r a t i o n , r e s o u r c e d i s c o v e ry , f r e e - s c a l e n e t w o r k , c f r , m i g r a t i o n s t r a t e g y - v- 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中 取 得的研究成果除加以标注和致谢的地方外， 不包含其他人己经发 表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示谢意。 学位论文作者签名: 吴 沫 日期: ,) o d 5_ ? 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用 学位论文的规定:即学校有权保留并向国家有关部门或机构送交论 文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可 以将学位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名;否则视为不同 意。 ) 学 位 论 文 作 者 签 名 : 美 沫 签字日期: z o o s. -3 . 6 导师签名 签字 日期 东 北大学博士学位论文 第一章 绪论 第一章 绪论 大量的实证研究发现， 现实中的许多真实网络都具有复杂网络的一些特征， 而i n t e r n e t 就是其中的一个典型代表。i n t e r n e t 作为迄今为止一个最复杂的人工 系统，涉及的问题和领域又极其繁多，日益庞大的网络规模及其异构性给网络 管理和互操作提出了新的问题:一方面 i n t e rne t 为用户提供了无比丰富的信息 资源和多种通讯手段，另一方面也使得用户处理、甚至定位感兴趣的信息变得 异常困难。尽管 i n t e r n e t 为我们提供了一个良 好的信息基础设施与灵活的网络 计算能力，但是，如何在如此复杂的 i n t e rn e t 上提供有效的手段来利用其上的 各种计算资源、网络存储资源、网络信息资源等却向我们提出了一系列新的挑 战。 1 . 1 复杂网络 近年来，学界关于复杂网络的研究正方兴未艾。特别是国际上有两项开创 性工作掀起了 一股不小的研究复杂网络的热潮。一是1 9 9 8 年w a tt s 和s t r o g a t z 在n a t u r e 杂志上发表文章，引 入了 小世界 ( s m a l l - w o r l d ) 网 络模型 o 1 ，以 描述从 完全规则网络到完全随机网络的转变。小世界网络既具有与规则网络类似的聚 类特性， 又具有与随机网络类似的较小的平均路径长度。 二是 1 9 9 9 年b a r a b a s i 和a l b e rt在 s c i e n c e 上发表文章指出，许多实际的复杂网络的连接度分布具有 幂律形式。由于幕律分布没有明显的特征长度，该类网络又被称为无尺度 ( s c a l e - f r e e ) 网 络2 1 。目 前， 己 经得到 研究的网 络在结 构上主要包括: 规则网 络、 随机网络、小世界网络和无尺度网络。 复杂网络研究所涉及的学科领域主要有:生命科学领域的各种网络 ( 如细 胞网络、蛋白质一蛋白 质作用网络、蛋白 质折叠网络、神经网络、生态网络) 、 社会网络 如: 流行性疾病的传播网络、 科学家合作网络、 语言学网络) 、 i n t e r n e t / w w w网络等等 3 4 5 1 。 对复杂网 络的研究之所以 能够取得迅速发展，可以 把 它归结为以下几条原因:首先，伴随着在各个领域中数据获取的计算机化，出 现了各种关于现实复杂网络拓扑结构的大型数据库:其次，计算能力的不断提 东 北大学博士学位论文 第一章 绪论 第一章 绪论 大量的实证研究发现， 现实中的许多真实网络都具有复杂网络的一些特征， 而i n t e r n e t 就是其中的一个典型代表。i n t e r n e t 作为迄今为止一个最复杂的人工 系统，涉及的问题和领域又极其繁多，日益庞大的网络规模及其异构性给网络 管理和互操作提出了新的问题:一方面 i n t e rne t 为用户提供了无比丰富的信息 资源和多种通讯手段，另一方面也使得用户处理、甚至定位感兴趣的信息变得 异常困难。尽管 i n t e r n e t 为我们提供了一个良 好的信息基础设施与灵活的网络 计算能力，但是，如何在如此复杂的 i n t e rn e t 上提供有效的手段来利用其上的 各种计算资源、网络存储资源、网络信息资源等却向我们提出了一系列新的挑 战。 1 . 1 复杂网络 近年来，学界关于复杂网络的研究正方兴未艾。特别是国际上有两项开创 性工作掀起了 一股不小的研究复杂网络的热潮。一是1 9 9 8 年w a tt s 和s t r o g a t z 在n a t u r e 杂志上发表文章，引 入了 小世界 ( s m a l l - w o r l d ) 网 络模型 o 1 ，以 描述从 完全规则网络到完全随机网络的转变。小世界网络既具有与规则网络类似的聚 类特性， 又具有与随机网络类似的较小的平均路径长度。 二是 1 9 9 9 年b a r a b a s i 和a l b e rt在 s c i e n c e 上发表文章指出，许多实际的复杂网络的连接度分布具有 幂律形式。由于幕律分布没有明显的特征长度，该类网络又被称为无尺度 ( s c a l e - f r e e ) 网 络2 1 。目 前， 己 经得到 研究的网 络在结 构上主要包括: 规则网 络、 随机网络、小世界网络和无尺度网络。 复杂网络研究所涉及的学科领域主要有:生命科学领域的各种网络 ( 如细 胞网络、蛋白质一蛋白 质作用网络、蛋白 质折叠网络、神经网络、生态网络) 、 社会网络 如: 流行性疾病的传播网络、 科学家合作网络、 语言学网络) 、 i n t e r n e t / w w w网络等等 3 4 5 1 。 对复杂网 络的研究之所以 能够取得迅速发展，可以 把 它归结为以下几条原因:首先，伴随着在各个领域中数据获取的计算机化，出 现了各种关于现实复杂网络拓扑结构的大型数据库:其次，计算能力的不断提 东 北大学 博士学 位论文第一章 绪论 高，使人们能够对包含数以千万计节点的网络进行研究，这在以前是无法实现 的;最后，人们迫切的需要从整体、宏观的角度去认识整个系统，因此对系统 各个部分之间的相互作用的拓扑性认识就显得尤为重要1 6 1 。研究这些复杂网络 所使用的主要方法是数学上的图论、物理学中的统计物理学方法和社会网络分 析方法. 在当前的复杂网络研究中，研究者提出的最主要概念就是 “ 网络” ( n e t w o r k s ) 。 抽象地说， 元素及其元素之间的 关系作为一个整体就是网络。 网络 可以用来描述人与人之间的社会关系，物种之间的捕食关系，词与词之间的语 义联系，计算机之间的网络联接，网页之间的超链接，科研文章之间的引用关 系，以及科学家之间的合作关系等。网络还可以作为现象的背景舞台，例如在 接触关系网络上传染病的传播，计算机病毒在 i n t e rne t网络或邮件网络上的传 播。网络与现象结合还可以用来讨论网络的稳定性等结构与功能关系，例如在 食物链网络上讨论个别或部分物种灭绝对整体生态系统的影响，在不同的网络 上讨论传染病传播的控制。此外，网络本身的演化过程也是一个有趣的问题， 例如 i n t e rne t 网络的形成被认为是无限定原则的，但是它却展现了一些重要而 普适的结构特征与稳定性1 7 1 复杂网络的研究，为我们提供了一种对复杂性研究的新视角、新方法。首 先，网络的现象涵盖极其广泛，因此，对网络的研究极具现实意义。上文提到 的现实世界中的各种网络都可构成某种复杂网络系统，因此，如果能发现一种 概括它们共同特性的观点和方法，则能够抓取这类网络的关键。而复杂网络研 究恰恰在这点上发现了它们同时都具有的三个主要特征:小世界特征、无尺度 性和高集聚度口 其次，在大量网络现象的基础上抽象出 两种复杂网络:小世界网络和无尺 度网络。这两种网络都同时具有两个基本特征:高平均集聚程度和小的最短路 径，而无尺度网络的度分布又具有幂律分布特征。高平均集聚程度反映了事物 在小世界的环境下自 发走向有序的态势;小的最短路径反映了系统演化速度快 的特征。系统低层次的因素之间的局部交互作用会更密集、更频繁，在系统层 次会涌现出更多的性质。 另外，复杂网络的基本测度性概念也反映了网络内某些个体与其它个体之 间的相互影响，这种双向的影响是网络分析的重点。例如，顶点的度的概念就 反映了与这个顶点相互作用的顶点数量的多少。 目前对复杂网络研究的内容主要包括: 网络的几何性质， 网络的形成机制， 东 北大学博士学位论文第一章 绪论 网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演 化动力学机制等问题。其中在自然科学领域，网络研究的基本测度包括:度 ( d e g r e e ) 及其分布特征， 度的相关性， 集聚程度及其分布特征， 最短距离及其分 布 特 征， 介 数 ( b e t w e e n n e s s ) 及 其 分 布 特 征， 连 通 集团 的 规 模 分 布 $ 1 9 1 1 0 1 1 1 1 。 通 过这些研究，三种概念在复杂网络的研究中占有重要地位。 第一，小世界的概念。它以简单的措辞描述了大多数网络尽管规模很大但 是任意两个节点间却有一条相当短的路径的事实。例如，在社会网络中，人与 人相互认识的关系很少，但是却可以找到很远的无关系的其他人。正如麦克卢 汉所说，地球变得越来越小，变成一个地球村，也就是说，变成一个小世界。 第二，集聚程度的概念。它是指网络集团化的程度，是一种网络的内聚倾 向。例如，社会网络中总是存在熟人圈或朋友圈，其中每个成员都认识其他成 员。另外，还可以通过连通集团来反映在一个大网络中各集聚的小网络分布和 相互联系的状况。例如，它可以反映这个朋友圈与另一个朋友圈的相互关系。 第三， 幂律的度分布概念。 度指的是网络中节点与节点间的关系( 用网络中 的边表达) 的数量;度的相关性是指顶点之间关系的联系紧密性。 对复杂网络研究的已有成果中，科学家发现绝大多数实际的复杂网络都具 有以 下几个基本特征 3 1 2 1 1 3 : ( 1 )网络行为的统计性:网络节点数可以 有成百上千万，甚至更多，从而 使得大规模性的网络行为具有统计性特征; ( 2 ) 节点动力学行为的复杂性:各个节点本身可以 是非线性系统，具有分 岔和混沌等非线性动力学行为; ( 3 )网络连接的稀疏性:一个n个节点的具有全局藕合结构的网络的连接 数目 为o (n 1) ， 而实际 大型网 络的 连接 数目 通常为。 (n ) 1 ( 4 ) 连接结构的复杂性:网络连接结构既非完全规则也非完全随机，而是 还存在一些其它结构特征: ( 5 )网络的时空演化复杂性:复杂网络具有空间和时间的演化复杂性，展 示出丰富的复杂行为，特别是网络节点之间的不同类型的同步化运动 ( 包括出 现周期、非周期混沌和阵发行为等运动) 。 以上五种特征，反映了实际网络的复杂性。一方面，它具有无序演化的特 征，另一方面，它也具有增加有序程度的演化特征。它不仅具有分形、混沌以 及自 组织演化的特征 1 4 1 5 1 6 1 7 1 ，而且还具有形成序参量的 特征。因 此，复杂 网络的研究可能会综合以往的各种自组织理论、非线性和复杂性理论研究的成 东北大学博士学位论文第一章 绪论 果 1 8 1 9 1 ，从而形成新的复杂性研究机制的理论。 如前所述，大量的实际网络都具有复杂网络的一些特征，而 i n t e r n e t 就是 其中的一个典型代表。实证表明，无论是在路由器级还是自治域级，i n t e r n e t 拓 扑 结 构 都 具 有 幂 规 律 和 小 世 界 网 络 特 性 2 0 2 1 2 2 1 i n t e r n e t 作为迄今为止最复杂的人工系统， 其中的一切几乎都是没有中央控 制的。无论是连接到i n t e rne t ，还是在www上冲浪，或是提供某种网络服务， 都由用户自己决定。 可以毫不夸张地说， i n t e r n e t 带来了前所未有的平等与自由。 我们的第一印象就是这样的一个 i n t e rne t 是杂乱无章的， 很难想到i n t e rne t 中蕴 藏着某种整体不变的规律。而美国施乐公司( x e r o x ) 的 p a l o a l t o研究中心的 i n t e rne t 生态研究小组的工作表明，与传统的人工系统相比，i n t e rne t 更象是一 个生态系统。 从整体上看， i n t e rn e t 从简单到复杂， 从低级到高级，正向着更优 的方向发展、演化，在其复杂的表象下，隐藏着令人吃惊的大范围模式的秩序 与结构。 这里所指的i n t e rne t 的大范围模式， 是i n t e rne t 中自 发地涌现出来的秩 序以 及产生 这种秩序的 机制2 3 1 作为一个庞大的结构松散的巨型复杂网络，i n t e r n e t 具有以下基本特征2 4 1 . ( 1 ) 分布性 i n t e rn e t 是一个真正的分布式系统， 该平台没有统一的控制， 所有网络资源 的链接都具有极强的开放性和动态性，网络实体的移动及其行为不可预测，这 种分布特性要求应用系统具有较强的网络适应性和动态调整能力。 ( 2 )多重的异构性 i n t e r n e t 上链接的主机和用户数目 相当巨大， 其异构性不言而喻， 更为复杂 的是 i n t e rn e t 上的软件服务无论是从体系结构、设计方法、实现语言、使用接 口还是功能都是千变万化，其异构特性非常复杂。建于其上的应用程序必须充 分考虑上述设备、人和软件的异构的屏蔽。 ( 3 )网络链接环境的多样性 依附于 i n t e r n e t 的网络链接也是复杂多样，包括各种局域网络、各种接入 设备、各种接入方式、各种接入协议和各种使用方式等等。 ( 4 )网络资源与服务的动态性 i n t e r n e t 是一个开放的网络， 没有全局管理. 新主机和通信链接的加入不会 事先通知。主机可以 移动或消失，然后重新( 以 新名字和新地址) 出现。不管是 在物理意义还是在逻辑意义上，各种服务和可用资源的拓扑结构都随着时间变 化而变化。 东北大学博士学位论文第一章 绪论 ( s ) 较弱的网络可用性 i n t e rne t 遍布世界各个角落，网络带宽一直是i n t e r n e t 面临的巨大问题，尤 其是 “ 最后一公里”往往还是依赖于各种低带宽链接，这使得网络的可持续链 接几乎不可能实现。在这种环境下的应用程序必须考虑网络可用性的限制和容 错处理。 ( 6 )潜在的不安全因素 随着网络深入到各行各业和各个角落，网络安全问题越来越突出，潜在的 恶意和无意的破坏行为如果得不到有效的控制和防范， i n t e r n e t 将成为一个危险 的 “ 雷区” ，其上的应用也将受到严重的影响。 显然，具有这些鲜明特色的 i n t e rne t 平台无疑和以往的单机平台、多处理 器平台是截然不同。而针对这些特性，寻找能适应这些特性的一种新的计算模 式，是充分发挥i n t e rne t 功效的重要一环。 1 .2 问题的提出 人类对计算的理解和追求始终是伴随着时代的变迁和科学技术的发展向前 演化的。自从第一台计算机问世以来，人类的计算能力得到了巨大的发展和提 高 ， 计 算 方 式 从 传 统 的 单 机 计 算 、 有 限 资 源 环 境 下 的 嵌 入 式 计 算 2 5 2 6 2 7 2 9 1 小 范围内 的 分布 式计 算， 以 及直到 近 年来提出 的 普 适计 算2 9 3 0 3 l 和全 球范围内 的网 格计算3 2 (3 3 ， 无不体现出 人类对计算的热衷和计算在各个领域内 的重要 性。 “ 计算”与理论和实验并列，己经成为第三种重要的科学研究方式，并且 计算将理论和实验连接起来，成为二者之间的桥梁。通过计算，可以完成许多 单纯依靠理论或者实验无法进行的科学研究。不仅在科学研究中，而且在越来 越多的社会与经济活动中， “ 计算” 也已经成为一种重要的甚至是不可替代的解 决问题的方法和工具。随着人们求解问题领域的不断拓展，所遇到的问题也越 来越复杂，而且规模也越来越大，解决这些问题所需要的计算能力也在大幅度 提高。例如，在天文学、医学、虚拟现实、基因组研究以 及与时间有关的三维 系统等的研究中，需要的都是超大规模的计算和数据分析能力。 在这些新问题的求解过程中，局部的计算资源已经无法满足这样的计算需 求，因此打破地域的限制来实现更大粒度和更大范围的资源共享就成为一种必 东北大学博士学位论文第一章 绪论 ( s ) 较弱的网络可用性 i n t e rne t 遍布世界各个角落，网络带宽一直是i n t e r n e t 面临的巨大问题，尤 其是 “ 最后一公里”往往还是依赖于各种低带宽链接，这使得网络的可持续链 接几乎不可能实现。在这种环境下的应用程序必须考虑网络可用性的限制和容 错处理。 ( 6 )潜在的不安全因素 随着网络深入到各行各业和各个角落，网络安全问题越来越突出，潜在的 恶意和无意的破坏行为如果得不到有效的控制和防范， i n t e r n e t 将成为一个危险 的 “ 雷区” ，其上的应用也将受到严重的影响。 显然，具有这些鲜明特色的 i n t e rne t 平台无疑和以往的单机平台、多处理 器平台是截然不同。而针对这些特性，寻找能适应这些特性的一种新的计算模 式，是充分发挥i n t e rne t 功效的重要一环。 1 .2 问题的提出 人类对计算的理解和追求始终是伴随着时代的变迁和科学技术的发展向前 演化的。自从第一台计算机问世以来，人类的计算能力得到了巨大的发展和提 高 ， 计 算 方 式 从 传 统 的 单 机 计 算 、 有 限 资 源 环 境 下 的 嵌 入 式 计 算 2 5 2 6 2 7 2 9 1 小 范围内 的 分布 式计 算， 以 及直到 近 年来提出 的 普 适计 算2 9 3 0 3 l 和全 球范围内 的网 格计算3 2 (3 3 ， 无不体现出 人类对计算的热衷和计算在各个领域内 的重要 性。 “ 计算”与理论和实验并列，己经成为第三种重要的科学研究方式，并且 计算将理论和实验连接起来，成为二者之间的桥梁。通过计算，可以完成许多 单纯依靠理论或者实验无法进行的科学研究。不仅在科学研究中，而且在越来 越多的社会与经济活动中， “ 计算” 也已经成为一种重要的甚至是不可替代的解 决问题的方法和工具。随着人们求解问题领域的不断拓展，所遇到的问题也越 来越复杂，而且规模也越来越大，解决这些问题所需要的计算能力也在大幅度 提高。例如，在天文学、医学、虚拟现实、基因组研究以 及与时间有关的三维 系统等的研究中，需要的都是超大规模的计算和数据分析能力。 在这些新问题的求解过程中，局部的计算资源已经无法满足这样的计算需 求，因此打破地域的限制来实现更大粒度和更大范围的资源共享就成为一种必 东 北大学博士学 位论文第一章 绪论 然的需求。而 i n t e rne t 作为一种集成了各种计算资源、存储资源、信息资源的 超大规模的网络计算平台，无疑为解决以上需求提供了良好的计算环境支持， 但同时还有一些问题巫待解决。 为此， 本文通过分析研究c a i d a的s k i tt e r 项目提供的i n t e rne t 监测数据中 蕴藏的某些复杂网络的特征和规律，来研究复杂网络上的计算迁移问题。主要 针对以下三个主要问题进行了研究，并提出了相应的解决方法。 ( 1 ) i n t e rn e t 作为一个开放的大规模复杂网络，其杂乱无章的表象后蕴藏的 某些宏观规律，能否对运行在其上的各种应用、服务或对某些问题的解决产生 某些影响或起到一定的指导作用。 ( 2 )由于处在不同地域的用户对计算需求的不平衡性， 导致了i n t e r n e t 上的 资源呈现出不均匀分布，即在一些小生境中，资源丰富，而在另外一些小生境 中，资源匾乏。另外， i n t e rne t 上各种网络设备的移动性和链路的多变性，使资 源不再固定或稳定，而是动态变化的。因此，如何在这种资源动态变化以及资 源分布不均匀的复杂网络中，实现对有限资源的最大化利用也是我们面临的问 题 。 ( 3 ) 随着i n t e rn e t 中网络节点数量的不断增多， 网 络规模的不断扩大， 利用 传统的 “ 广播扩散”方式来搜索网络上的共享资源将造成网络流量急剧增加， 从而导致网络中部分低带宽节点因网络资源过载而失效。因此，为了能有效利 用其上的各种资源， i n t e rn e t 网络环境中的资源发现方法也成为一个值得研究的 问题。 针 对以 上问 题， 本文 通过c a i d a ( c o o p e r a t i v e a s s o c i a t i o n f o r i n t e rn e t d a t a a n a l y s i s )的s k i t t e r 项目 提供的i n t e rn e t 监测数据， 借助统计的手段对i n t e r n e t 上的一些特征量进行了统计分析，并得出一些对本文工作具有指导意义的统计 规律。 提出了 “ 计算迁移”的思想。为了实现有限资源的最大利用化，当本地的 资源有限，剩余资源己 不能满足用户计算任务的需求时，将计算任务迁移到资 源丰富，运行环境良好的节点上继续运行，将得到更好的性能表现。即计算任 务随资源的动态变化而进行迁移，实现 “ 资源在哪里，就到哪里计算” 。 针对 i n t e rn e t 网络拓扑结构中，节点的连接度分布存在 “ 幂律”规律，以 及i n t e r n e t 中具有 “ 小世界”网络的特征，引入了t c p / i p中动态路由的思想， 提出一种新的资源发现算法一连接度优先路由查找算法 ( c f r ) ， 能有效降低网 络