第一原理的方法理解网络拓扑课件

以第一原理的方法来理解互联网的路由级拓扑结构小组成员：鲁泽茹 叶宣佐 孙彬彬A First-Principles Approachto Understanding the Internets Router-level TopologyLun Li David Alderson Walter Willinger John Doyle2004 ACM SIGCOMM内容提要背景及相关12345第一原理方法总结及前瞻拓扑结构的优化几种拓扑结构的对比评估协议的的性能保护网络进行资源配置方便理解大型网络为什么要进行拓扑？问题及挑战规模大真正的拓扑结构是不对外公开拓扑是时刻变化的1拓扑模型的趋势发展模型方法 远程连接十分昂贵网络是有层级 网络拓扑服从幂率(Faloutsos et al.,1999)随机图样模型（Waxman 1988）结构模型（GT-ITM Calvert/Zegura,1996）复制给定幂率度序列模型少数节点连接数目多少数节点连接数目多Rank R(d)DegreeSource:Faloutsos et al.(1999)幂率和网络拓扑路由层和自治域具有这种结构引起了基于度的网络模型的研究多数节点连接数目少多数节点连接数目少以度为基础的网络拓扑优先连接(Preferential Attachment)顺序增加一个节点来构建构建新的节点优先连接到有更多连接的节点例如:Inet,GPL,AB,BA,BRITE,CMU power-law generator基于度的拓扑模型期望 度序列基于随机图样模型来产生具有期望幂率的拓扑例如:幂率随机图样(PLRG),通用模型随机图样(GRG)优先连接(Preferential Attachment)顺序增加一个节点来构建构建新的节点优先连接到有更多连接的节点例如:Inet,GPL,AB,BA,BRITE,CMU power-law generator基于度的模型的特征度序列服从幂率高的度节点有许多连接，对系统很重要Achilles heel:对于随机的错误表现很稳定，但是对于特殊攻击十分脆弱（计算机疫情和病毒传播传播的原因）优先连接期望度序列What really matters when it comes to topology construction?技术限制经济问题2100101102Degree10-1100101102103Bandwidth(Gbps)15 x 10 GE15 x 3 x 1 GE 15 x 4 x OC12 15 x 8 FETechnology constraint带宽每个度的带宽路由器的技术限制Cisco 12416 GSR,circa 2002（最贵带宽最大）高带宽 度低度高 带宽低可低于有效边可低于有效边界，不可能超界，不可能超过这个边界过这个边界Rank(使用者数目)连接速度(Mbps)1e-11e-211e11e21e31e41e211e41e61e8Dial-up56KbpsBroadbandCable/DSL500KbpsEthernet10-100MbpsEthernet1-10Gbps大多数使用者是低大多数使用者是低速速少数使用者有高速少数使用者有高速高性能技术高性能技术学术或是企业学术或是企业住宅和小型企业住宅和小型企业经济考虑拓扑模型的趋势发展模型方法 远程连接十分昂贵网络是有层级 网络拓扑服从幂率(Faloutsos et al.,1999)随机图样模型（Waxman 1988）结构模型（GT-ITM Calvert/Zegura,1996）复制给定幂率度序列模型物理网络具有技术（经济）限制启发式拓扑优化启发式拓扑优化HostsHostsEdgesEdges核心核心网状高速核心，度低的路由器度高的节点在边缘SOXSFGP/AMPATHU.FloridaU.So.FloridaMiss StateGigaPoPWiscRENSURFNetRutgers U.MANLANNorthernCrossroadsMid-AtlanticCrossroadsDrexel U.U.DelawarePSCNCNI/MCNCMAGPIUMD NGIXDARPABossNetGEANTSeattleSunnyvaleLos AngelesHoustonDenverKansasCityIndian-apolisAtlantaWash D.C.ChicagoNew YorkOARNETNorthern LightsIndiana GigaPoPMeritU.LouisvilleNYSERNetU.MemphisGreat PlainsOneNetArizona St.U.ArizonaQwest LabsUNMOregonGigaPoPFront RangeGigaPoPTexas TechTulane U.North TexasGigaPoPTexasGigaPoPLaNetUT AustinCENICUniNetWIDEAMES NGIXPacificNorthwestGigaPoPU.HawaiiPacificWaveESnetTransPAC/APANIowa St.Florida A&MUT-SWMed Ctr.NCSAMRENSINetWPIStarLightIntermountainGigaPoPAbilene BackbonePhysical Connectivity(as of December 16,2003)0.1-0.5 Gbps0.5-1.0 Gbps1.0-5.0 Gbps5.0-10.0 Gbps网络性能指标网络性能指标在路由器技术限制的条件下，如何评估网络性能？Step 1:限制域限制域抽象的技术可行抽象的技术可行域域1101001000100001000001000000101001000degreeBandwidth(Mbps)Step 3:计算最大的流量计算最大的流量BiBjxijStep 2:计算需求计算需求并非再现真实的流量，而是要评估在合理的流量模式和技术的限制下选出的拓扑结构的原始的承载能力4似然相关指标似然相关指标对任何结构易于计算依赖于图样的结构而非产生机制定义指标：(di=degree of node i)L max和L min是L（g）之间用顶点集V所有简单的连接图g与同一个节点度序列的d的最大值和最小值。两种观点的对比基于度的观点对统计特性匹配建议有一个度高的核心第一原理方法的观点技术和经济考虑 性能建议一个度低的网状核心网络符合实际网络的物理设计如何协调两种观点？3相同的度分布优先连接（优先连接（PA）GRG（通用随机模型）（通用随机模型）相同的度分布HOT相同的度分布PAPLRG/GRGHOTAbilene-inspiredSub-optimal网络性能指标网络性能指标在路由器技术限制的条件下，如何评估网络性能？Step 1:限制域限制域抽象的技术可行抽象的技术可行域域1101001000100001000001000000101001000degreeBandwidth(Mbps)Step 3:计算最大的流量计算最大的流量BiBjxijStep 2:计算需求计算需求并非再现真实的流量，而是要评估在合理的流量模式和技术的限制下选出的拓扑结构的原始的承载能力4PAGRGHOT性能对比性能对比P(g)=1.19 x 1010P(g)=1.64 x 1010 P(g)=1.13 x 1012 似然相关指标似然相关指标对任何结构易于计算依赖于图样的结构而非产生机制Measures how“hub-like”the network core is定义指标：(di=degree of node i)L max的和L min是L（g）之间用顶点集V所有简单的连接图g与同一个节点度序列的d的最大值和最小值。Lmaxl(g)=1P(g)=1.08 x 1010 P(g)Perfomance(bps)PAGRGHOTAbilene-inspiredSub-optimal0 0.20.40.60.81 101010111012 l(g)=Relative Likelihood 需要强调的是：度分布相同可以有不同的核心结构 核心结构相同可以有不同的度分布100101102100101102Node DegreeNode Rank100101102100101102Node DegreeNode Rank100101102100101102Node RankNode Degree核心结构相同，度是均匀分布.核心结构相同，度是服从幂率分布 核心结构相同，度随便分布本文结论1.以度为基础的生成机制都可能产生的拓扑，具有性能差，并且非常难以产生真实的网络。2.路由器级拓扑模型应考虑网络设计的固有技术和经济的权衡，这是构建网络拓扑考虑的本质问题。3.真实的路由器级拓扑生成将需要额外的评估工作，将以其他主要功能（如地理，人口密度）为框架5工作前瞻依靠ISP来验证互联网的技术限制如何发现更好的网络拓扑构建一个想要的网络拓扑生成器当构建一个网络拓扑时，如何探测现有的网络拓扑符合当前拓扑To be continued我们学习有关度和拓扑有关的概念，以及如何构建一个性能优异的网络拓扑那么问题就来了？1：在我们定义对拓扑结构中的性能进行指标时，有一个叫吞吐量（throughput），它与带宽是什么关系？吞吐量和带宽是很容易搞混的一个词。当讨论通信链路的带宽时，一般是指链路上每秒所能传送的比特数，它取决于链路时钟速率和信道编码在计算机网络中又称为线速。可以说以太网的带宽是10Mbps。但是需要区分链路上的可用带宽（带宽）与实际链路中每秒所能传送的比特数（吞吐量）。通常更倾向于用“吞吐量”一词来表示一个系统的测试性能。这样，因为实现受各种低效率因素的影响，所以由一段带宽为10Mbps的链路连接的一对节点可能只达到2Mbps的吞吐量。这样就意味着，一个主机上的应用能够以2Mbps的速度向另外的一个主机发送数据。一句话：吞吐量没有带宽大2 网络的构建与拓扑，数学统计，物理因素有关，还和什么有关？从本文可以看出，除了和上述两种有关外，还和他的技术限制与经济因素有关。但是在真实构建网络的过程中，一些地理因素，环境因素和人文因素可能也是会对拓扑结构的产生构成影响。答案仅供参考答案仅供参考4 现在发展很是火热的物联网，与我们的拓扑有关，如果每个物体都联网了，那么可能出现什么样的拓扑，其度还是服从幂率么？本题为开放性问题，无标准答案。Thanks for your listening!