第一原理的方法理解网络拓扑.ppt

A First-Principles Approachto Understanding the Internet’s Router-level Topology Lun Li David Alderson Walter Willinger John Doyle 问题及挑战 拓扑模型的趋势 以度为基础的网络拓扑 优先连接(Preferential Attachment) 顺序增加一个节点来构建构建 新的节点优先连接到有更多连接的节点 例如: Inet, GPL, AB, BA, BRITE, CMU power-law generator 基于度的拓扑模型 期望 度序列 基于随机图样模型来产生具有期望幂率的拓扑 例如: 幂率随机图样 (PLRG), 通用模型随机图样 (GRG) 基于度的模型的特征 度序列服从幂率 高的度节点有许多连接，对系统很重要 Achilles’ heel: 对于随机的错误表现很稳定，但是对于特殊攻击十分脆弱（计算机疫情和病毒传播传播的原因） 路由器的技术限制 经济考虑 拓扑模型的趋势 网络性能指标 在路由器技术限制的条件下，如何评估网络性能？ 似然相关指标 两种观点的对比 基于度的观点 对统计特性匹配 建议有一个度高的核心 第一原理方法的观点 技术和经济考虑 性能 建议一个度低的网状核心网络 符合实际网络的物理设计 相同的度分布 相同的度分布 相同的度分布 网络性能指标 在路由器技术限制的条件下，如何评估网络性能？ 性能对比 似然相关指标 需要强调的是： 本文结论 以度为基础的生成机制都可能产生的拓扑，具有性能差，并且非常难以产生真实的网络。 路由器级拓扑模型应考虑网络设计的固有技术和经济的权衡，这是构建网络拓扑考虑的本质问题。 真实的路由器级拓扑生成将需要额外的评估工作，将以其他主要功能（如地理，人口密度）为框架 工作前瞻 依靠ISP来验证互联网的技术限制 如何发现更好的网络拓扑 构建一个想要的网络拓扑生成器 当构建一个网络拓扑时，如何探测现有的网络拓扑符合当前拓扑 我们学习有关度和拓扑有关的概念，以及如何构建一个性能优异的网络拓扑 1：在我们定义对拓扑结构中的性能进行指标时，有一个叫吞吐量（throughput），它与带宽是什么关系？ 2 网络的构建与拓扑，数学统计，物理因素有关，还和什么有关？ 4 现在发展很是火热的物联网，与我们的拓扑有关，如果每个物体都联网了，那么可能出现什么样的拓扑，其度还是服从幂率么？ PA GRG HOT P(g) = 1.19 x 1010 P(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的最大值和最小值。 Lmax l(g) = 1 P(g) = 1.08 x 1010 P(g) Perfomance (bps) PA GRG HOT Abilene-inspired Sub-optimal 0 0.2 0.4 0.6 0.8 1 10 10 10 11 10 12 l(g) = Relative Likelihood 度分布相同可以有不同的核心结构 核心结构相同可以有不同的度分布 10 0 10 1 10 2 10 0 10 1 10 2 Node Degree Node Rank 10 0 10 1 10 2 10 0 10 1 10 2 Node Degree Node Rank 10 0 10 1 10 2 10 0 10 1 10 2 Node Rank Node Degree 核心结构相同，度是均匀分布. 核心结构相同，度是服从幂率分布 核心结构相同，度随便分布 5 To be continued 那么问题就来了？ 吞吐量和带宽是很容易搞混的一个词。当讨论通信链路的带宽时，一般是指链路上每秒所能传送的比特数，它取决于链路时钟速率和信道编码在计算机网络中又称为线速。可以说以太网的带宽是10Mbps。但是需要区分链路上的可用带宽（带宽）与实际链路中每秒所能传送的比特数（吞吐量）。通常更倾向于用“吞吐量”一词来表示一个系统的测试性能。这样，因为实现受各种低效率因素的影响，所以由一段带宽为10Mbps的链路连接的一对节点可能只达到2Mbps的吞吐量。这样就意味着，一个主机上的应用能够以2Mbps的速度向另外的一个主机发送数据。一句