苏航韦莎小世界现象及其应用

小世界现象及其应用报告人：苏航、韦莎2009年10月14日上海交通大学图像通信研究所主要内容小世界网络的基本理论1基于小世界网络的应用层组播模型2基于小世界网络的疾病传播模型3总结与展望4上海交通大学图像通信研究所小世界网络的基本概念小世界现象：当你遇见一个陌生人，通过交谈，我们往往会惊奇地发现：“原来我们有共同的朋友！”或者说，仅通过几个熟识的人，我们就早已经相互联系在一起。六度分割假设：世界上的任意两个人，可以通过朋友关系联系起来，但朋友的个数是很小的，平均不超过6个。也就是说平均中间只需要5个人就可以将任意两个人联系起来。------StanleyMilgram，1967小世界现象在疾病传播、通信网络中也普遍存在，而且是“”网络结构中的一个基本属性。上海交通大学图像通信研究所小世界网络的基本概念四十年的沉寂期和十五年的飞速发展期ears,progresshas上海交通大学图像通信研究所规则网络：平移对称性晶格，任何一个格点的近邻数目都相同顶点的度：是单独顶点属性中重要的概念，顶点的度是与该顶点连接的其他顶点的数量随机网络：由N个格点构成的图中，可以存在条边，从中随机连接M条边所构成的网络就叫随机网络；若，则称随机网络中任意两点以概率p相连小世界网络2NC2NMpC上海交通大学图像通信研究所规则网络小世界网络随机网络小世界网络大部分的真实网络既不是完全规则的，也不是完全随机,小世界网络模型是从完全规则网络向完全随机网络的过渡模型断边重连机制:即在规则网络的基础上，对其每一个顶点所连接的边，以一定概率断开其中一个顶点，并重新进行连接，连接的新的端点从其他顶点中随机选取，但不能被重复选择，也不能与其自身进行连接，称其为“WS小世界模型”随机化加边机制:即在规则网络的基础上以概率随机选取两个顶点，加入一条边，任意两个不同的节点之间至多只能有一条边，并目每一个节点都不能有边与自身相连demo上海交通大学图像通信研究所小世界网络的性质聚类系数：量网络中节点之间连接紧密程度的一个重要度量，反映的是是网络的局部特征(())()()2iiiE连接节点的邻居节点之间的边的数量i节点的邻居节点之间理论上最多可能存在的边的数量论的数量。i1010.411上海交通大学图像通信研究所小世界网络的性质路径长度：在网络G中，任选两个节点和，连通这两个节点的最少的边数，定义为这两个节点的路径长度网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度特征路径长度是网络的全局特征，在朋友网络中，特征路径长度就是联系两个人的朋友的平均个数。ijijd上海交通大学图像通信研究所小世界网络的性质规则的最近邻网络具有高聚类性质，但网络特征路径长度较大;随机网络特征路径长度较小，但没有高聚类性质。实际的网络往往网络聚类系数较高，并且网络特征路径长度较小，小世界网络可以比较好的模拟这一特点。上海交通大学图像通信研究所小世界网络的集体动力学当，即网络为稀疏网络且保证连通的状态下：当时，且当时，且对于小p,每个捷径对L有一个高度非线性作用，不但缩小了它连结的一对点之间的距离，而且也缩小了它们所处的邻域之间的距离，以及邻域的邻域之间的距离等。相比之下，从一个集群邻域中移去一条边以建立一个捷径最多对C有线性作用；因此，即使L(p)急速下降，对于小P来说，C(p)仍然几乎不变。ln1nkn0p~/21Lnk~3/4C~ln()/ln()Lnk1p~/1Ckn上海交通大学图像通信研究所主要内容小世界网络的基本理论1基于小世界网络的应用层组播模型2基于小世界网络的疾病传播模型3总结与展望4上海交通大学图像通信研究所组播技术的基本概念组播(也称为多播)是指点到多点、多点到多点的通信方式，即多个信宿同时接收一个或多个信源发送的相同的信息。往往由信源发一个数据包沿着多播树进行转发，这棵多播树由通信子网的多播路由算法决定。1988年，Deering提出了将组播的功能机制增加到数据网IP层的组播实现体系结构，这种体系结构称为IP组播在IP组播中，不论组成员数量的多少，数据源只发送一次数据包，并且组播只向那些需要数据包的主机和网络发送包，任何一个数据包在组播树的链路上只出现一次，因此能够很好的控制流量，减轻主机和网络的负担，节省了宝贵的网络带宽。上海交通大学图像通信研究所IP组播的技术难题复杂度高：IP组播需要路由设备维护相应组播组的状态信息表和相关的地址信息，而组播地址很难实现聚合，增加了路由设备的负担和实现的复杂性，扩展性差。安全性问题:IP组播服务模型没有完善的组播组管理机制缺乏组创建的管理，由于路由器只检查目的地址，而不检查源地址，发送者可以随意的发送数据而不需要任何的身份验证和注册工作，主机也可以随意的加入和离开组播组发送者也不能阻止其他发送者使用相同的组播地址，从而无法避免组地址的冲突和恶意的攻击，可能造成网络拥塞。上海交通大学图像通信研究所IP组播的技术难题组播服务质量问题:IP组播是不可靠的网络层协议，在传输层，基于UDP协议，只是提供一种尽力而为的服务，不能使用TCP协议，难以支持可靠的网络传输，难以实现拥塞控制，因此服务商极少开放IP组播业务。地址分配机制:节点不能有效的发现一个立即可用的组播地址，而是随机选取一个来使用，这样随着组数目的增加，组播地址冲突的可能性也随之增大，面临着地址空间耗尽的问题。域间组播路由协议问题：域间组播路由协议对组播技术大规模实施具有重要的作用，但它需要ISP将他们的网络互连，同时隐藏各自的网络拓扑结构，目前IP组播还没有成熟有效的域间组播路由协议。上海交通大学图像通信研究所IP组播的商业问题设备问题：IP组播需要路由器支持组播功能，如果现有的路由器不支持组播，就需要更换设备，增加了商业的运营成本。跨域组播管理的问题:如果RP和其他组播源点不在同一个域内，难以进行流量控制和拥塞控制;ISP对其他域中的RP没有控制能力;当要进行跨域组播服务时，ISP之间必须进行协调，因此只有当应用组播所节省的带宽大大超过它的实施代价时才具有商业价值。IP组播还没有清晰的商业费用模型：网络运营商之间有不同的利益取向，由于组播分组在运营商网络内部需要复制，从而和根据流量对单播分组计费的模型相矛盾。上海交通大学图像通信研究所应用层组播协议应用层组播在思想上完全将复杂的组播功能交给应用层处理，从而避免了网络层相关条件的限制，降低了网络设备的性能要求。发送者不需要给每个接收者发送数据，只给部分接收者发送数据，接收者负责把接收到的数据转发给其他接收者，直至所有接收者都收到数据，等于把发送者的负担，分配到了多个其他成员身上。它将转发树构建在应用层上，两个主机实际的链路是底层的单播IP路径。从具体的过程来讲就是:组播源准备数据，查询组播路由表，获得子节点的单播IP地址，再分别打包、转发;这一过程重复进行，直到所有节点都收到数据包。上海交通大学图像通信研究所应用层组播技术对于IP组播：为IP组播，A为发送者，数据包从A到R1，再由R1转发给B和R2，R2再将收到的数据包转发给C和D应用层组播，A发送两份相同的数据包分别给B和C，再由C复制一份给D。应用层组播的效率比IP组播的效率要低，存在冗余的流量上海交通大学图像通信研究所应用层组播存在的问题可靠性问题：端系统不稳定，导致组播的可靠性不高拥塞问题：同一分组在同一条单播链路上重复分发，比一般的IP组播系统使用更多的网络资源，更有可能出现拥塞，导致组播性能的下降QOS性能问题：由于端系统不知道低层网络拓扑的结构，导致应用层组播性能有可能很差，端系统间建立的组播树一般不是最佳的，因此其时延较大。上海交通大学图像通信研究所基于小世界模型的应用层组播Internet网络的平均距离L是随网络大小N对数增长的,它明显具有小世界效应。从结构上看,Internet的实际结构介乎于规则网络和随机网络,表明其具有小世界效应。Internet具有集团化、聚类的特征，具有小世界网络的特性借鉴小世界网络的特点，进行组播上海交通大学图像通信研究所基于小世界网络的应用层组播构建骨干节点：按照组播组所要求特性的不同，应用分簇(cluster)方法将整个网络切割成多个小的区域，作为树状结构的第一个分支层，并确立这个类的中心点，可称为骨干节点。小世界网络建立：首先将所选出的骨干节点有序的连接成为一个规则网络。然后在大量的实验以及对网络状况初步了解的基础上，为这种转化设定一个概率P，初步建成了一个小世界骨干分发叠加网。建立簇内网络：各个簇内进行进一步的细分，构建较低层的骨干节点，或称为基层骨干节点，进一步构建簇内的细分网络。簇间偶然连接：据上层节点所提供的组播信息以及下层节点的特性，构建部分簇间连接。上海交通大学图像通信研究所小世界网络构建的叠加层拓扑图上海交通大学图像通信研究所小世界网络应用层组播的流量管理单速率算法中:发送端只用一种速率发送数据,整个组播组的吞吐量受瓶颈接收端的限制。多速率算法允许发送端使用多种发送速率，从而在接收端之间产生更灵活的带宽分配。分层组播:数据被分为多个层，分别使用不同的组播组进行发送。接收端选择订阅适当的层，订阅的层越多，数据质量越高。分区域组播：对于每一个骨干节点，视其为新的数据源，分别向其下层的骨干节点发送确认信息，下层骨干节点在接收到确认信息的同时向上层节点发送反馈。骨干节点根据反馈回来的延时将下层的节点分为高速中速低速等不同的区域。上海交通大学图像通信研究所小世界网络应用层组播的拥塞控制当网络负载较小时，吞吐量与网络负载基本保持线性关系当网络负载超过第1个关键转折点后，网络吞吐量增长变慢，网络延迟增长变快网络负载超过第2个关键点后，网络吞吐量急剧下降拥塞控制的目标就是使网络在关键转折点附近工作上海交通大学图像通信研究所常用的拥塞控制策略先进先出(FIFO)：提供基本的存储转发功能，也是目前Internet使用最广泛的一种方式，它在网络拥塞时存储分组，在拥塞解除时按分组到达顺序转发分组。优先级排队算法：在禁止其它流量的前提下，授权一种类型的流量通过，只有当高优先级队列空了以后，才能为低优先级服务定制排队：为允许具有不同最低带宽和延迟要求的应用程序共享网络而设计，为不同的协议分配不同的队列空间，并以循环方式处理队列加权公平排队：识别交互式应用的数据流，并将应用的数据流调度到队列前部，以减少响应时间。随机先期检测：如果网点拥塞增多，就随机丢弃一些分组;当源分布点检测到通信丢失，便降低传输速率。上海交通大学图像通信研究所基于小世界网络的组播机制数据源发送数据时，首先要探测第一层小世界骨干叠加网中的骨干节点，选取与该数据目标组播组相关性最强的骨干节点，然后以数据包的形式发送到该节点。这一骨干节点在收到数据后，首先选取一定数目的同层骨干节点，将信息复制发送。各骨干节点向下层的相关目标节点发送数据，在各层中同样的操作重复出现。分层分群，同层复制，多点传输的机制上海交通大学图像通信研究所小世界网络应用层组播性能分析实验条件：1个总的数据源，10个初层的骨干节点，每次的组播过程中，选用4个骨干节点作为主要的业务终端向客户端发送数据。路由器的转发能力限制为4Mb/s，缓冲队列的缓冲区大小为500包，最大和最小阈值分别为200和100。在实验中，假设该多媒体业务应用的丢包率低于10%效果良好，丢包率低于20%时用户能够接受，丢包率超过20%则用户无法忍受。在传输数据方面，采用的是多媒体业务数据流，流量为40帧/s，每一帧数据的大小按平均值为1000byte的指数分布，该业务的大约平均流量为1000*8*40=3.2*105b/s，背景流量按平均值为640kb/s的指数分布。上海交通大学图像通信研究所不同应用层组播方法的延时比较基于小世界网络的应用层组播模型同其他模型相比，延时特性具有明显优势NICE和ZIGZ