[计算机网络：自顶向下方方法](中文版ppt课件)第四章.ppt

《[计算机网络：自顶向下方方法](中文版ppt课件)第四章.ppt》由会员分享，可在线阅读，更多相关《[计算机网络：自顶向下方方法](中文版ppt课件)第四章.ppt（161页珍藏版）》请在三一办公上搜索。

1、网络层,1,第4章 网络层Network Layer,计算机网络：自顶向下方法 (原书第三版)陈鸣译，机械工业出版社，2005年Computer Networking: A Top Down Approach Featuring the Internet, 3rd edition. Jim Kurose, Keith RossAddison-Wesley, July 2004.,网络层,2,第4章 网络层,本章目的: 理解网络层服务依赖的原理:选路 (路径选择)处理扩展性路由器工作原理先进主题: IPv6, NAT因特网中的实例和实现,网络层,3,第4章 网络层,4. 1 概述4.2 虚电路和

2、数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,4,网络层,从发送主机到接收主机传输段在发送侧将段封装进数据报在接收侧，向运输层交付段网络层协议在每台主机、路由器中当IP数据报通过路由器时，路由器检查所有数据报首部字段,网络层,5,关键的网络层功能,转发: 将分组从路由器的输入移动到适当的路由器输出选路: 决定分组从源到目的地所采用的路由选路算法,类比:选路: 规划从源到目的地路径的过程转发: 通过单个立交桥的过程,

3、网络层,6,1,2,3,0111,到达分组首部的值,选路算法,选路和转发相互影响,网络层,7,连接建立,在某些网络体系结构中第三重要的功能:ATM, 帧中继, X.25在数据报流动之前，两台主机和其间的路由器创建虚拟连接需要路由器参与网络层和运输层的连接服务:网络层: 在两台主机之间运输层: 在两个进程之间,网络层,8,网络服务模型,问题：对从发送方到接收方“隧道”化传输数据报，其服务模型 是什么?,对单个数据报的例子服务:确保交付以少于40 msec时延确保交付,对数据报流的例子服务:按序数据报交付对流确保最小带宽对分组间间隔变化的限制,网络层,9,网络层服务模型:,网络层,10,第4章 网

4、络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,11,网络层连接和无连接服务,数据报网络提供网络层无连接服务虚电路网络提供网络层连接服务与运输层服务的类比:服务: 主机到主机无选择: 网络提供一个或其他实现: 在网络内部,网络层,12,虚电路,在数据流动之前，建立呼叫；然后拆除每个分组携带VC标识符在源到目的地路径上的每台路由器为每条经过的连接维护维护状态链路、路由器资源(带宽、缓

5、存)可能分配给VC,“源到目的地路径与电话电路行为非常相似”性能明确沿着源到目的地路径的网络动作,网络层,13,VC实现,一条VC由下列组成:从源到目的地的路径VC号是标识沿路径每条链路的号码沿路径路由器中转发表中的项属于VC的分组携带一个VC号每条链路的VC号必须改变新的VC号来自转发表,网络层,14,转发表,西北路由器中的转发表 :,路由器维护连接状态信息!,网络层,15,虚电路: 信令协议,用于建立、维护和拆除VC用于ATM、帧中继、X.25中没有用于今天的因特网中,1. 发起呼叫,2. 入呼叫,3. 接受呼叫,4. 呼叫已连接,5. 数据流开始,6. 接收数据,网络层,16,数据报网络

6、,在网络层无呼叫建立路由器：没有端到端连接的状态无网络级“连接”的概念分组使用目的主机地址转发在相同源和目的对可能采用不同的路径,1. 发送数据,2. 接收数据,网络层,17,转发表,目的地址范围 链路接口 11001000 00010111 00010000 00000000 到 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 到 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 1100

7、1000 00010111 00011111 11111111 其他 3,40亿可能的项,网络层,18,最长前缀匹配,前缀匹配 链路接口 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 otherwise 3,目的地址: 11001000 00010111 00011000 10101010,例子,目的地址: 11001000 00010111 00010110 10100001,哪个接口?,哪个接口?,网络层,19,数据报或虚电路网络: why?,因特网在计算机间交换数据“弹性”

8、服务，无严格的定时要求“智能” 端系统 (计算机)能够适应，执行控制，差错控制网络内部简单，“边缘”复杂许多链路类型 不同的特点难以提供统一服务,ATM从电话技术演化来人类交谈：严格定时，可靠性要求对确保服务的需求“哑” 端系统电话网络内部复杂,网络层,20,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,21,路由器体系结构概述,路由器的两个关键功能: 运行选路算法/协

9、议(RIP, OSPF, BGP)从入链路到出链路转发 数据报,网络层,22,输入端口功能,分散式交换: 给定数据报目的地址, 在输入端口内存中使用转发表查找输出端口目的: 以“线速”完成输入端口处理排队：如果数据报到达比交换结构 的转发速率快,物理层:比特级接收,数据链路层:如以太网参见第5章,网络层,23,三种类型的交换结构,内存,总线,纵横制,网络层,24,经内存交换,第一代路由器: 具有交换功能的传统计算机，在CPU的直接控制下分组拷贝到系统的内存速率受内存带宽限制(每数据报跨越两次总线),输入端口,输出端口,内存,系统总线,网络层,25,经总线交换,数据报从输入端口到输出端口内存经一

10、个共享的总线总线竞争: 交换速率受总线带宽限制1 Gbps总线, Cisco 1900: 用于接入和企业(非区域或主干)路由器的充足速率,总线,网络层,26,经互联网络的交换,克服了总线带宽限制Banyan网络, 其他互联网络最初研制以连接多处理器中的处理器先进的设计：数据报分段为固定长度的信元，通过交换结构搅和信元 Cisco 12000: 通过互联网络交换Gbps,网络层,27,Batcher-Banyan交换机,高速路由器,网络层,28,输出端口,当数据报来自交换结构比传输速率更快时，需要缓存调度安排 为了传输在排队数据报之间选择,交换结构,排队：缓存管理,数据链路处理(协议、拆封),线

11、路端接,网络层,29,输出端口排队,当到达速率经交换机超过输出链路速率时缓存因为输出缓存溢出，出现排队(时延)和丢包!,交换结构,交换结构,在时间t输出端口竞争,一个分组时间以后,网络层,30,输入端口排队,交换结构比组合的输入端口慢- 排队可能出现在输入队列线头(HOL)阻塞: 排队的数据报在队列的前面阻碍队列中的其他数据报转发由于输入缓存溢出，出现排队时延和丢包!,在时间t输出端口竞争，仅一个红色分组能被传输,绿色分组经历了HOL阻塞,交换结构,网络层,31,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATIC

12、MPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,32,The Internet 网络层,主机，路由器网络层功能:,运输层: TCP, UDP,链路层,物理层,网络层,网络层,33,IP:无连接交付系统,互联网服务被定义成不可靠的、尽力而为、无连接分组交付系统。服务是不可靠的，因为分组可能丢失、重复、延迟或不按序交付等，但服务不检测这些情况，也不提醒发送方和接收方。服务是尽力而为的，互联网并不随意地丢弃分组；只有当资源用完或底层网络出现故障时才可能出现不可靠性。服务是无连接的，因为每个分组都是独立对待的

13、。分组序列可能经过不同的传输路径或者有的丢失有的到达。,网络层,34,IP 数据报格式,ver,长度,32 bits,数据(变长,通常是一个TCP或UDP段),16-bit标识符,互联网检查和,寿命,32 bit源IP地址,IP协议版本号,首部长度 (字节),剩余跳的最大数(在每台路由器减1),对分段/重装,总数据报长度(字节),较高层协议交付的负载,首部长度,服务类型,数据的“类型”,标志,段偏移,高层,32 bit目的IP地址,选项 (如果有的话),例如，时间戳，记录所经路径，定义访问的路由器列表,TCP的开销多大?20 字节 TCP20 字节 IP= 40字节+ 应用层开销,网络层,35

14、,IP分片和重新组装,网络链路有MTU (最大传输长度) 最大可能的链路级帧不同的链路类型，不同的在网络中，大IP 数据报被分割(“分段”)一个数据报 变为几个数据报“重新装配”仅在最后目的地IP首部比特用于标识、排序相关段,分段: 输入: 一个大的数据报输出: 3个小的数据报,reassembly,网络层,36,IP分片和重新组装,例子4000字节数据报MTU = 1500字节,在数据字段1480 字节,偏移 =1480/8,网络层,37,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5

15、选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,38,IP编址:概述,IP地址: 对主机、路由器接口的32-bit 标识符 接口: 在主机/路由器和物理链路之间的连接路由器通常具有多个接口主机可能具有多个接口IP编址与每个接口相联系,223.1.1.1,223.1.1.3,223.1.1.4,223.1.2.9,223.1.1.1 = 11011111 00000001 00000001 00000001,223,1,1,1,网络层,39,子网,IP地址: 子网部分(高阶比特)主机部分(低阶比特) 什么是子网 ?具有IP地

16、址相同的子网部分的设备接口能够物理上互相到达而没有中间路由器,223.1.1.1,223.1.1.2,223.1.1.3,223.1.1.4,223.1.2.9,223.1.2.2,223.1.2.1,223.1.3.2,223.1.3.1,223.1.3.27,网络由3个子网组成,LAN,网络层,40,子网,判断方法为了决定子网，从其主机或路由器分离每个接口，生成孤立网络的岛。每个孤立的网络被称为一个子网,子网掩码: /24,网络层,41,子网,多少个子网?,223.1.1.1,223.1.1.3,223.1.1.4,223.1.2.2,223.1.2.1,223.1.2.6,223.1.3

17、.2,223.1.3.1,223.1.3.27,223.1.1.2,223.1.7.0,223.1.7.1,223.1.8.0,223.1.8.1,223.1.9.1,223.1.9.2,网络层,42,IP编址: CIDR,无类型域间选路(Classless InterDomain Routing,CIDR)任意长的地址的子网部分地址格式: a.b.c.d/x, 其中x是地址子网部分的比特长度,网络层,43,IP编址: 如何得到一个地址?,问题：主机怎样得到IP地址?由系统管理员在文件中的硬编码Wintel: 控制面板-网络-配置-TCP/IP-性质UNIX: /etc/rc.config动态

18、主机配置协议(Dynamic Host Configuration Protocol DHCP): 动态地从服务器得到地址“即插即用” (详情参见下章),网络层,44,IP编址:如何得到一个地址?,问题：网络怎样得到IP地址的子网部分?回答: 从它的ISP的地址空间得到分配的部分,ISP的块 1001000 00010111 00010000 00000000 200.23.16.0/20 组织 0 11001000 00010111 00010000 00000000 200.23.16.0/23 组织 1 11001000 00010111 00010010 00000000 200.23

19、.18.0/23 组织 2 11001000 00010111 00010100 00000000 200.23.20.0/23 . . . .组织 7 11001000 00010111 00011110 00000000 200.23.30.0/23,聚合,网络层,45,等级编址: 路由聚合,“向我发送地址始于200.23.16.0/20的任何分组”,Fly-By-Night-ISP,组织 0,组织 7,因特网,组织 1,ISPs-R-Us,“向我发送地址始于199.31.0.0/16的任何分组”,组织 2,等级编址允许有效的通告选路信息:,网络层,46,等级编址: 更为特定的路由,ISP

20、s-R-Us具有更为特定的路由到组织 1,“向我发送地址始于200.23.16.0/20的任何分组”,Fly-By-Night-ISP,组织 0,组织 7,因特网,组织 1,ISPs-R-Us,“向我发送地址始于199.31.0.0/16或200.23.18.0/23的任何分组”,组织 2,网络层,47,IP编址: 其他问题,问题：ISP怎样得到地址块?回答:因特网名字与号码分配团体( Internet Corporation for Assigned Names and Numbers,ICANN )分配地址管理DNS分配域名，调解争议,网络层,48,第4章 网络层,4. 1 概述4.2 虚

21、电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,49,NAT: 网络地址转换,10.0.0.1,10.0.0.2,10.0.0.3,10.0.0.4,138.76.29.7,本地网络(如归属网络)10.0.0/24,因特网其他部分,具有该网源或目的的数据报都有10.0.0/24的地址(照常),所有数据报本地离开本地网络具有相同的单一源NAT IP地址: 138.76.29.7,不同的源端口号,网络层,50,NA

22、T: 网络地址转换,动机: 外部关注本地网络只使用的一个IP地址 :对ISP无需分配地址范围：对所有设备只用一个IP地址能够改变本地网络中的设备地址，而不必通知外部本地网络中的设备不显式地可寻址、由外部所见(增强安全性),网络层,51,NAT: 网络地址转换,实现: NAT 路由器必须:出数据报: 每个外出的数据报用(NAT IP地址, 新port #) 代替(源IP地址, port #). . . 远程的客户机/路由器的响应，将用(NAT IP地址, new port #)作为目的地址 记住(在NAT转换表中)每个 (源IP地址, port #)到(NAT IP地址, 新port #) 转换

23、对入数据报: 对每个入数据报的地址字段用存储在NAT表中的(源IP地址, port #)替代对应的 (NAT IP地址, 新port #),网络层,52,NAT: 网络地址转换,10.0.0.1,10.0.0.2,10.0.0.3,10.0.0.4,138.76.29.7,NAT 转换表WAN 侧地址 LAN 侧地址,138.76.29.7, 5001 10.0.0.1, 3345 ,2: NAT路由器改变数据报源地址从10.0.0.1, 3345 到138.76.29.7, 5001,更新表,3: 回答到达的目的地址: 138.76.29.7, 5001,4: NAT 路由器改变数据报目的地

24、址从138.76.29.7, 5001到10.0.0.1, 3345,网络层,53,NAT: 网络地址转换,16-bit 端口号字段: 用一个LAN侧地址支持60,000 并行连接!NAT 引起争议:路由器的处理上升为第三层违反了端到端原则应用设计者必须要考虑 NAT可能性，如 P2P应用程序地址短缺应当由IPv6来解决,网络层,54,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选

25、路,网络层,55,ICMP: 互联网控制报文协议,由主机和路由器用于网络级信息的通信差错报告：不可达主机，网络，端口, 协议回声请求/回答 (由 ping使用)网络层 “上面的” IP:IP 数据报中携带ICMP 报文ICMP报文: 类型、编码以及引起差错的IP 数据报 的前面 8 字节,类型 编码 描述0 0 回声回答 (ping)3 0 目的网络不可达3 1 目的主机不可达3 2 目的协议不可达3 3 目的端口不可达3 6 目的网络未知3 7 目的主机未知4 0 源抑制(拥塞控制未使用）8 0 回声请求 (ping)9 0 路由通告10 0 路由器发现11 0 TTL过期12 0 坏的IP

26、首部,网络层,56,Traceroute和ICMP,源向目的地发送一系列UDP段第一个 TTL =1第二个 TTL=2, 等不可能的端口号当第n个数据报 到达第n和路由器:路由器丢弃数据报并向源发送一个ICMP报文 (类型 11, 编码0)报文包括路由器的名字和IP地址,当ICMP报文到达，源计算 RTTTraceroute执行上述过程3次停止规则UDP段最终到达目的地主机目的地返回ICMP “主机不可达”分组 (类型3, 编码3)当源得到该ICMP, 停止,网络层,57,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址

27、NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,58,IPv6,初始动机: 32-bit地址空间很快将会被完全分配完附加的动机:首部格式帮助速率处理/转发首部变化以促进QoS IPv6 数据报格式: 固定长度 40 字节首部不允许分段,网络层,59,IPv6首部(续),优先级 : 标识特殊流的分组优先权流标签: 标识在相同“流”中的i数据报(流的概念没有很好定义)下一个首部: 标识数据的上层协议,网络层,60,与IPv4相比的其他变化,检查和: 完全去除以减小每跳的处理时间选项: 允许，但在

28、首部之外，由“下一个首部”字段指示ICMPv6: 新版本的 ICMP附加的报文类型，如 “分组太大”多播组管理功能,网络层,61,从 IPv4到IPv6的迁移,并非所有的路由器能被同时更新无“标志日 ”IPv4和IPv6路由器混合将如何运行? 隧道: 在IPv路由器之间IPv6数据报作为IPv4数据报的负载,网络层,62,隧道,IPv6,IPv6,IPv6,IPv6,隧道,逻辑视图:,物理视图:,IPv6,IPv6,IPv6,IPv6,IPv4,IPv4,A-to-B:IPv6,E-to-F:IPv6,B-to-C:IPv6 在IPv4中,B-to-C:IPv6 在IPv4中,网络层,63,第

29、4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,64,直接和间接交付,直接交付是指在一个物理网络上，数据报从一台机器上直接传送到另一台机器上，这是所有互联网通信的基础。只有当两台机器同时连到同一底层物理传输系统时(例如一个以太网)，才能进行直接交付间接交付当目的地不在一个直接连接的网络上时，发送方必须把数据报发给一个路由器才能交付它互联网中数据报交付的最后一步是直接交付，直

30、接交付是间接交付的一个特例,网络层,65,Internet早期体系结构,ARPANET 采用手工方式，设置指向其他网址的选路表后期体系结构由少量、集中的路由器来保存全部目的站的信息其他大量的外部路由器仅包含部分信息,Core system,网络层,66,默认路由：十分低效,默认路由虽能做到路由一致性，但却可能十分低效,网络层,67,核心系统采用最优路由,为提高效率，所有核心路由器交换选路信息使得每个路由器都具有到所有目的站的最优路由的全部信息如果在核心路由器的路由表上查不到某个数据报的目的站，它就发出 ICMP “目的站不可达”报文并抛弃这个数据报就本质而言，核心系统的设计删除了默认路由，避免

31、了低效率的选路,网络层,68,核心系统不能分为若干部分,核心系统不能划分成若干保存部分信息的子集，否则可能无效若主干分成路由器两个子集，每个子集保存部分信息并使用默认路由。这样的体系结构使得具有非法目的站的数据报形成了选路环路,网络层,69,对等主干网结构,ARPANET 与 NSFNET 之间建立了多个连接，增加了路由选择结构的复杂性。这两个网络称为对等主干网络，或简称为对等网(peers),网络层,70,对等主干网中 IP 选路的多样性,对等主干网配置，一对地理位置接近的主机之间的流量应该选择最短的路径从主机 3 到主机 1 的通信量通过R1主机 3 到主机 2 的路由有多条如果这些主干分

32、属不同ISP，是否有问题？,网络层,71,体系结构复杂性的限制,除非互联网范围很小，否则不能让所有路由器直接参与选路更新协议即使与互联网连接站点仅有一个本地网络，核心体系结构也不能满足任意数量的需要，否则选路流量太大每个网点不能容纳多个路由器和网络，因为只有与主干网直接相连的路由器才能直接通信在大型互联网中，网络和路由器并非由一个实体管理，也没有使用最短路,尽管希望路由器交换选路信息，但任意大的互连网中的所有路由器参与到一个选路更新协议中是不切实际的。,网络层,72,核心系统的重要启示,限制参与同一个选路协议的路由器数量，表明某些路由器将被排除在该组外，它需要有一些默认路由在早期Interne

33、t中，非核心路由器把数据报交给核心系统来交付重要启示如果组外的一个路由器使用一些组作为默认路由，选路将是次优的在不能满足大量路由器或一个广域网情况下，非参与路由器使用参与路由器交付,网络层,73,需要建立获得路由信息的机制,由于单个组织能够具有由路由器互联的任意复杂的网络，该组织的路由器不可能与其他网络直接相连。需要一个机制，以使非参与路由器把隐藏的网络的情况通知给其他组。选路信息必须在两个方向流动：从一组参与路由器到一个非参与路由器非参与路由器必须将隐藏网络的信息传给该组,网络层,74,自治系统的概念,从选路的角度来说，处于一个管理机构控制之下的网络和路由器群组称为一个自治系统(autono

34、mous system，AS)AS可能有复杂结构，该独立机构要负责保证其内部的路由信息的一致性和可用性在AS内的路由器，可以自由地选择寻找路由、广播路由、确认路由以及检测路由的一致性的机制可安排R3通告网络2、3和4(R1知道网络1)核心路由器自己也构成一个自治系统,网络层,75,从一个核心网到独立的自治系统,为了使在AS中的隐藏网络能到达 Internet ，每个AS必须向其他AS通告自己的网络在AS中使用IGP，在AS之间使用EGP,EGP,IGP,IGP,网络层,76,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编

35、址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,77,选路,选路算法的图论抽象:图中的节点是路由器图中的边是物理链路链路代价: 时延，费用或拥塞等级,目的：决定从源到目的地通过网络的“好的路径”(路由器序列),2,2,1,3,1,1,2,5,3,5,“好的”路径:通常意味着最小费用的路径其他定义也是可能的,网络层,78,选路算法分类,全局的或分散的信息?分散的: 路由器知道物理相连的邻居，到邻居的链路费用计算的迭代过程，与邻居交换信息“距离矢量” 算法全局的:所有路由器具有完全的拓扑、链路

36、费用信息“链路状态”算法s,静态的或动态的?静态: 路由随时间缓慢变化动态: 路由更快地变化周期的更新适应链路费用变化,网络层,79,A Link-State 选路算法,Dijkstra算法所有节点知道网络拓扑、链路费用经“链路状态广播”完成所有节点具有相同信息从一个节点(源)到所有其他节点计算最低费用路径给出对这些节点的转发表迭代: k次迭代后，得知到k个目的地的最低费用路径,概念:c(x,y): 从节点x到y的链路费用; = 如果不是直接邻居D(v):从源到目的地v路径费用的当前值p(v): 从源到v沿路径的前任节点N: 已知在最小费用路径中的节点集合,网络层,80,Dijsktra算法,

37、1 初始化: 2 N = u 3 对所有节点v 4 if v 临近 u 5 then D(v) = c(u,v) 6 else D(v) = 7 8 Loop 9 找出w不在N中使得D(w)最小 10 将w加入N 11 对于所有v临近w并不在N中，更新D(v): 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* 到v的新费用或是到v的老费用或到w加上从w到v的已知最短路费用*/ 15 until 所有节点在 N中,网络层,81,Dijkstra 算法: 例子,步骤012345,Nuuxuxyuxyvuxyvwuxyvwz,D(v),p(v)2,u2,u2,u

38、,D(w),p(w)5,u4,x3,y3,y,D(x),p(x)1,u,D(y),p(y)2,x,D(z),p(z) 4,y4,y4,y,网络层,82,Dijkstra算法, 讨论,算法复杂性: n个节点每次迭代: 需要检查所有节点w, 不在N中n(n+1)/2 对比: O(n2)更有效的实现是可能的: O(nlogn)可能振荡:如链路费用 = 承载流量的量,e,1,1,e,1,1,e,1,1,网络层,83,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距

39、离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,84,距离矢量算法(1),Bellman-Ford方程 (动态规划)定义dx(y) := 从x到y最低费用路径的费用则dx(y) = min c(x,v) + dv(y) 其中min对x的所有邻居,网络层,85,Bellman-Ford 例子 (2),Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3,du(z) = min c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) = min 2 + 5, 1 + 3, 5 + 3 = 4,取

40、最小的节点是在最短路中的下一跳 转发表,B-F equation says:,网络层,86,距离矢量算法(3),基本思想: 每个节点周期性的发送它自己的距离矢量以估计到其邻居当节点x接收到来自邻居的新DV估计，它使用B-F方程更新其自己的DV :,Dx(y) minvc(x,v) + Dv(y) for each node y N,在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用 dx(y),网络层,87,距离矢量算法(4),迭代、异步: 每次本地迭代由下列引起: 本地链路费用改变DV从邻居更新报文分布式:每个节点仅当其DV改变时通知邻居如果必要，邻居则通知它们的邻居,每个节点:,

41、网络层,88,距离矢量: 链路费用变化,链路费用变化:好消息传播得快坏消息传播得慢“计数到无穷”问题!在算法稳定前，迭代44 次: 参见课文毒性逆转: 如果Z路由通过Y得到 X :Z告诉Y它(Zs)到X的距离是无穷 (因此Y将不能经Z路由到X)这将完全解决计数到无穷问题?,网络层,89,LS和DV算法的比较,报文复杂性LS: 对n个节点，E条链路, 发送O(nE) 报文 DV: 仅在邻居之间交换收敛时间变化收敛速度LS: O(n2) 算法要求 O(nE)报文可能具有振荡DV: 收敛时间变化可能有选路环路计数到无穷问题,健壮性: 如果路由器异常，将发生什么现象?LS: 节点可能通告不正确的链路费

42、用每个节点仅计算它自己的表DV:DV节点通告不正确的路径费用每个节点表能由其他人使用差错通过网络传播,网络层,90,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,91,等级选路,规模: 具有2亿个目的地:在选路表中不能存储所有的目的地!选路表交换将堵塞链路!,管理自治互联网 = 网络的网络每个网络管理员可能要控制他自己网络中的选路,我们的选路研究至此是理想的所有路由器是

43、等同的网络“扁平” 实践中并不真实,网络层,92,等级选路,将某区域的路由器聚合成为 “自治系统” (AS)在相同AS中的路由器运行相同的选路协议“intra-AS” 选路协议在不同的AS中的路由器能够运行不同的intra-AS 选路协议,网关路由器直接链路到在另一个AS中的路由器,网络层,93,互联的AS,转发表由AS内部和AS之间的选路算法所配置AS内部设置内部目的地表项AS之间和AS内部对外部目的地设置表项,网络层,94,AS间的任务,假定在AS1中的路由器接收目的地是AS1外部的数据报路由器应当将分组朝着网关路由器转发，但哪个呢？,AS1需要:知道通过AS2可到达哪些目的地，通过AS3

44、到达哪些传播这些可达信息到AS1中所有路由器AS间选路的工作!,网络层,95,例子: 设置路由器1d的转发表,假定AS1从AS间协议得知子网 x 从AS3(网关1c)可达，而不是从AS间协议传播可达性信息到所有内部路由器路由器1d从AS内部信息决定，它的接口I正处于到1c的最低费用路径上在转发表中放入表项(x,I).,网络层,96,从AS间协议得知，子网x经多个网关可达,使用来自AS内部协议选路信息，以决定到每个网关的最低费用路径,热土豆选路:选择具有最小费用的网关,从转发表决定接口I 通向最低费用网关。表项Enter (x,I) 在转发表中,例子: 在多个AS之间选择,现在假定AS 1从AS

45、间协议得知，子网x 从AS3和从AS2可达为了配置转发表, 路由器1d必须决定对目的地x ，它应当将分组转发向哪个网关这也是AS间选路协议的工作!热土豆选路: 发送分组朝着两个路由器中最近的那个,网络层,97,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,98,RIP ( 选路信息协议),距离矢量算法包括在1982中的 BSD-UNIX Distribution距离度量

46、: 跳的数量(最大 = 15跳),网络层,99,RIP通告,距离矢量: 每30秒在邻居之间经响应报文(又称为通告)交换每个通告：在AS中包括多达25个目的网络的列表,网络层,100,RIP: 例子,目的网络 下一个路由器 到目的地的跳数 wA2yB2 zB7x-1.,w,x,y,z,A,C,D,B,在D中选路表,网络层,101,RIP: 例子,目的网络 下一个路由器 到目的地的跳数 wA2yB2 zB A7 5x-1.,选路 table in D,目的地 下一个 跳 w - - x - - z C 4 . .,从A到D通告,网络层,102,RIP: 链路故障与恢复,在180 sec后，如果无通

47、告首部 - 邻居/链路宣告死亡经使无效邻居的路由新的通告发送给邻居邻居依次发送出新的通告(如果表变化)链路故障信息迅速地传播到整个网络使用毒性逆转以防止ping-pong回路 (无限距离 = 16 跳),网络层,103,RIP表处理,RIP选路表由称为route-d (守护进程)的应用级进程管理通告在UDP分组中发送，周期地重复,物理层,链路层,网络层 转发表 (IP),运输层 (UDP),物理层,链路层,网络层 (IP),运输层 (UDP),转发表,网络层,104,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NAT

48、ICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,105,OSPF (开放最短路优先),“开放”: 公共可用使用链路状态算法 LS分组分发在每个节点拓扑图使用 Dijkstra算法的路由计算OSPF携带每个邻居路由器一个项通告散布到整个AS(经洪泛)携带在OSPF报文中直接封装在IP中(而不是TCP或UDP),网络层,106,OSPF “先进的”特色 (RIP所不具有的),安全性: all OSPF messages authenticated (to prevent malicious intru

49、sion) 运行多条费用相同的路径(在RIP中仅一条路径)对每条链路，对不同的TOS(服务类型)，设置多种费用度量(如卫星链路费用置为用于尽力而服务为“低”，高为实时服务)综合的单播和多播支持: 多播OSPF (MOSPF)使用与OSPF相同的拓扑数据库在大域中层次的OSPF,网络层,107,层次OSPF,网络层,108,层次OSPF,两级层次: 本地, 主干链路状态通告仅在本地每个节点具有详细的区域拓扑；仅知道到其他区域网络的方向(最短路)区域边界路由器 : “摘要”到在自己区域网络的距离，向其他区域边界路由器通告主干路由器 : 运行OSPF 选路限制到主干边界路由器 : 连接到其他AS,网

50、络层,109,第4章 网络层,4. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议数据报格式IPv4编址NATICMPIPv6,4.5 选路概念4.6 选路算法链路状态距离矢量等级选路4.7 互联网中选路RIPOSPFBGP4.8 广播和多播选路,网络层,110,Internet inter-AS 选路: BGP,BGP (边界网关协议): 事实上的标准BGP为每个AS提供了一种手段 :从相邻AS获得子网可达性信息向AS内部的所有路由器传播可达性信息基于可达性信息和策略，决定到子网的“好”路由允许一个子网向因特网其余部分通告他的存在： “I am here”,网