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

网络层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章 网络层本章目的: r理解网络层服务依赖的原理:m选路 (路径选择)m处理扩展性m路由器工作原理m先进主题: IPv6, NATr因特网中的实例和实现网络层3第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层4网络层r从发送主机到接收主机传输段r在发送侧将段封装进数据报r在接收侧，向运输层交付段r网络层协议在每台主机、路由器中r当IP数据报通过路由器时，路由器检查所有数据报首部字段networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路层物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical网络层5关键的网络层功能r转发: 将分组从路由器的输入移动到适当的路由器输出r选路: 决定分组从源到目的地所采用的路由m选路算法类比:r选路: 规划从源到目的地路径的过程r转发: 通过单个立交桥的过程网络层61230111到达分组首部的值选路算法本地转发表首部值输出链路01000101011110013221选路和转发相互影响网络层7连接建立r在某些网络体系结构中第三重要的功能:mATM, 帧中继, X.25r在数据报流动之前，两台主机和其间的路由器创建虚拟连接m需要路由器参与r网络层和运输层的连接服务:m网络层: 在两台主机之间m运输层: 在两个进程之间网络层8网络服务模型问题：对从发送方到接收方“隧道”化传输数据报，其服务模型 是什么?对单个数据报的例子服务:r确保交付r以少于40 msec时延确保交付对数据报流的例子服务:r按序数据报交付r对流确保最小带宽r对分组间间隔变化的限制网络层9网络层服务模型:网络体系结构服务模型带宽保证无丢失保证排序定时拥塞指示因特网尽力而为无无任何可能的顺序不维持无ATMCBR保证恒定速率是有序维持拥塞不出现ATMABR保证最小速率无有序不维持提供拥塞指示网络层10第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层11网络层连接和无连接服务r数据报网络提供网络层无连接服务r虚电路网络提供网络层连接服务r与运输层服务的类比:m服务: 主机到主机m无选择: 网络提供一个或其他m实现: 在网络内部网络层12虚电路r在数据流动之前，建立呼叫；然后拆除r每个分组携带VC标识符r在源到目的地路径上的每台路由器为每条经过的连接维护维护状态r链路、路由器资源(带宽、缓存)可能分配给VC“源到目的地路径与电话电路行为非常相似”m性能明确m沿着源到目的地路径的网络动作网络层13VC实现一条VC由下列组成:1.从源到目的地的路径2.VC号是标识沿路径每条链路的号码3.沿路径路由器中转发表中的项r属于VC的分组携带一个VC号r每条链路的VC号必须改变m新的VC号来自转发表网络层14转发表122232132VC号接口号 入接口 入VC # 出接口 出VC #1 12 2 222 63 1 18 3 7 2 171 97 3 87 西北路由器中的转发表 :路由器维护连接状态信息!网络层15虚电路: 信令协议r用于建立、维护和拆除VCr用于ATM、帧中继、X.25中r没有用于今天的因特网中应用运输网络数据链路物理应用运输网络数据链路物理1. 发起呼叫2. 入呼叫3. 接受呼叫4. 呼叫已连接5. 数据流开始6. 接收数据网络层16数据报网络r在网络层无呼叫建立r路由器：没有端到端连接的状态m无网络级“连接”的概念r分组使用目的主机地址转发m在相同源和目的对可能采用不同的路径应用运输网络数据链路物理应用运输网络数据链路物理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 11001000 00010111 00011111 11111111 其他 340亿可能的项网络层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?因特网r在计算机间交换数据m“弹性”服务，无严格的定时要求r“智能” 端系统 (计算机)m能够适应，执行控制，差错控制m网络内部简单，“边缘”复杂r许多链路类型 m不同的特点m难以提供统一服务ATMr从电话技术演化来r人类交谈：m严格定时，可靠性要求m对确保服务的需求r“哑” 端系统m电话m网络内部复杂网络层20第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层21路由器体系结构概述路由器的两个关键功能: r运行选路算法/协议(RIP, OSPF, BGP)r从入链路到出链路转发 数据报网络层22输入端口功能分散式交换分散式交换: r给定数据报目的地址, 在输入端口内存中使用转发表查找输出端口r目的: 以“线速”完成输入端口处理r排队：如果数据报到达比交换结构 的转发速率快物理层:比特级接收数据链路层:如以太网参见第5章网络层23三种类型的交换结构内存总线纵横制网络层24经内存交换第一代路由器:r 具有交换功能的传统计算机，在CPU的直接控制下r分组拷贝到系统的内存r速率受内存带宽限制(每数据报跨越两次总线)输入端口输出端口内存系统总线网络层25经总线交换r数据报从输入端口到输出端口内存经一个共享的总线r总线竞争: 交换速率受总线带宽限制r1 Gbps总线, Cisco 1900: 用于接入和企业(非区域或主干)路由器的充足速率总线网络层26经互联网络的交换r克服了总线带宽限制rBanyan网络, 其他互联网络最初研制以连接多处理器中的处理器r先进的设计：数据报分段为固定长度的信元，通过交换结构搅和信元r Cisco 12000: 通过互联网络交换Gbps网络层27rBatcher-Banyan交换机Line card(转发 buffering)Line card(转发 buffering)Line card(转发 buffering)Line card(转发 buffering)选路CPUBuffermemory选路 softwarew/ router OSr高速路由器网络层28输出端口r当数据报来自交换结构比传输速率更快时，需要缓存r调度安排 为了传输在排队数据报之间选择交换结构排队：缓存管理数据链路处理(协议、拆封)线路端接网络层29输出端口排队r当到达速率经交换机超过输出链路速率时缓存r因为输出缓存溢出，出现排队(时延)和丢包!交换结构交换结构在时间t输出端口竞争一个分组时间以后网络层30输入端口排队r交换结构比组合的输入端口慢- 排队可能出现在输入队列r线头(HOL)阻塞: 排队的数据报在队列的前面阻碍队列中的其他数据报转发r由于输入缓存溢出，出现排队时延和丢包!在时间t输出端口竞争，仅一个红色分组能被传输 绿色分组经历了HOL阻塞交换结构网络层31第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层32The Internet 网络层转发表主机，路由器网络层功能:选路协议路径选择RIP, OSPF, BGPIP 协议编址规则数据报格式分组处理规则ICMP 协议差错报告路由器“信令”运输层: TCP, UDP链路层物理层网络层网络层33IP:无连接交付系统r互联网服务被定义成分组交付系统。m服务是不可靠的，因为分组可能丢失、重复、延迟或不按序交付等，但服务不检测这些情况，也不提醒发送方和接收方。m服务是尽力而为的，互联网并不随意地丢弃分组；只有当资源用完或底层网络出现故障时才可能出现不可靠性。m服务是无连接的，因为每个分组都是独立对待的。分组序列可能经过不同的传输路径或者有的丢失有的到达。网络层34IP 数据报格式ver长度32 bits数据(变长,通常是一个TCP或UDP段)16-bit标识符互联网检查和寿命32 bit源IP地址IP协议版本号首部长度 (字节)剩余跳的最大数(在每台路由器减1)对分段/重装总数据报长度(字节)较高层协议交付的负载首部长度服务类型数据的“类型”标志段偏移高层32 bit目的IP地址选项 (如果有的话)例如，时间戳，记录所经路径，定义访问的路由器列表TCP的开销多大?r20 字节 TCPr20 字节 IPr= 40字节+ 应用层开销网络层35IP分片和重新组装r网络链路有MTU (最大传输长度) 最大可能的链路级帧m不同的链路类型，不同的r在网络中，大IP 数据报被分割(“分段”)m一个数据报 变为几个数据报m“重新装配”仅在最后目的地mIP首部比特用于标识、排序相关段分段: 输入: 一个大的数据报输出: 3个小的数据报reassembly网络层36IP分片和重新组装ID=x偏移=0段标识=0长度=4000ID=x偏移=0段标识=1长度=1500ID=x偏移=185段标识=1长度=1500ID=x偏移=370段标识=0长度=1040一个大数据报 变为几个较小的数据报例子r4000字节数据报rMTU = 1500字节在数据字段1480 字节偏移 =1480/8 网络层37第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层38IP编址:概述rIP地址: 对主机、路由器接口的32-bit 标识符 r接口: 在主机/路由器和物理链路之间的连接m路由器通常具有多个接口m主机可能具有多个接口mIP编址与每个接口相联系223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.1.1 = 11011111 00000001 00000001 00000001223111网络层39子网rIP地址: m子网部分(高阶比特)m主机部分(低阶比特) r什么是子网 ?m具有IP地址相同的子网部分的设备接口m能够物理上互相到达而没有中间路由器223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27网络由3个子网组成LAN网络层40子网223.1.1.0/24223.1.2.0/24223.1.3.0/24判断方法r为了决定子网，从其主机或路由器分离每个接口，生成孤立网络的岛。每个孤立的网络被称为一个子网子网掩码: /24网络层41子网多少个子网?223.1.1.1223.1.1.3223.1.1.4223.1.2.2223.1.2.1223.1.2.6223.1.3.2223.1.3.1223.1.3.27223.1.1.2223.1.7.0223.1.7.1223.1.8.0223.1.8.1223.1.9.1223.1.9.2网络层42IP编址: CIDR无类型域间选路(Classless InterDomain Routing,CIDR)m任意长的地址的子网部分m地址格式: a.b.c.d/x, 其中x是地址子网部分的比特长度11001000 00010111 00010000 00000000子网部分主机部分200.23.16.0/23网络层43IP编址: 如何得到一个地址?问题：主机怎样得到IP地址?r由系统管理员在文件中的硬编码mWintel: 控制面板-网络-配置-TCP/IP-性质mUNIX: /etc/rc.configr动态主机配置协议(Dynamic Host Configuration Protocol DHCP): 动态地从服务器得到地址m“即插即用” (详情参见下章)网络层44IP编址:如何得到一个地址?问题：网络怎样得到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.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的任何分组”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISP组织 0组织 7因特网组织 1ISPs-R-Us“向我发送地址始于199.31.0.0/16的任何分组”200.23.20.0/23组织 2.等级编址允许有效的通告选路信息:网络层46等级编址: 更为特定的路由ISPs-R-Us具有更为特定的路由到组织 1“向我发送地址始于200.23.16.0/20的任何分组”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISP组织 0组织 7因特网组织 1ISPs-R-Us“向我发送地址始于199.31.0.0/16或200.23.18.0/23的任何分组”200.23.20.0/23组织 2.网络层47IP编址: 其他问题问题：ISP怎样得到地址块?回答:因特网名字与号码分配团体( Internet Corporation for Assigned Names and Numbers,ICANN )m分配地址m管理DNSm分配域名，调解争议网络层48第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层49NAT: 网络地址转换10.0.0.110.0.0.210.0.0.310.0.0.4138.76.29.7本地网络(如归属网络)10.0.0/24因特网其他部分具有该网源或目的的数据报都有10.0.0/24的地址(照常)所有数据报本地离开本地网络具有相同的单一源NAT IP地址: 138.76.29.7,不同的源端口号网络层50NAT: 网络地址转换r动机: 外部关注本地网络只使用的一个IP地址 :m对ISP无需分配地址范围：对所有设备只用一个IP地址m能够改变本地网络中的设备地址，而不必通知外部m本地网络中的设备不显式地可寻址、由外部所见(增强安全性)网络层51NAT: 网络地址转换实现: NAT 路由器必须:m出数据报: 每个外出的数据报用(NAT IP地址, 新port #) 代替(源IP地址, port #). . . 远程的客户机/路由器的响应，将用(NAT IP地址, new port #)作为目的地址 m记住(在NAT转换表中)每个 (源IP地址, port #)到(NAT IP地址, 新port #) 转换对m入数据报: 对每个入数据报的地址字段用存储在NAT表中的(源IP地址, port #)替代对应的 (NAT IP地址, 新port #) 网络层52NAT: 网络地址转换10.0.0.110.0.0.210.0.0.3S: 10.0.0.1, 3345D: 128.119.40.186, 80110.0.0.4138.76.29.71: 主机10.0.0.1 发送数据报到128.119.40, 80NAT 转换表WAN 侧地址 LAN 侧地址138.76.29.7, 5001 10.0.0.1, 3345 S: 128.119.40.186, 80 D: 10.0.0.1, 33454S: 138.76.29.7, 5001D: 128.119.40.186, 8022: NAT路由器改变数据报源地址从10.0.0.1, 3345 到138.76.29.7, 5001,更新表S: 128.119.40.186, 80 D: 138.76.29.7, 500133: 回答到达的目的地址: 138.76.29.7, 50014: NAT 路由器改变数据报目的地址从138.76.29.7, 5001到10.0.0.1, 3345 网络层53NAT: 网络地址转换r16-bit 端口号字段: m用一个LAN侧地址支持60,000 并行连接!rNAT 引起争议:m路由器的处理上升为第三层m违反了端到端原则 应用设计者必须要考虑 NAT可能性，如 P2P应用程序m地址短缺应当由IPv6来解决网络层54第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层55ICMP: 互联网控制报文协议r由主机和路由器用于网络级信息的通信m差错报告：不可达主机，网络，端口, 协议m回声请求/回答 (由 ping使用)r网络层 “上面的” IP:mIP 数据报中携带ICMP 报文rICMP报文: 类型、编码以及引起差错的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首部网络层56Traceroute和ICMPr源向目的地发送一系列UDP段m第一个 TTL =1m第二个 TTL=2, 等m不可能的端口号r当第n个数据报 到达第n和路由器:m路由器丢弃数据报m并向源发送一个ICMP报文 (类型 11, 编码0)m报文包括路由器的名字和IP地址r当ICMP报文到达，源计算 RTTrTraceroute执行上述过程3次停止规则rUDP段最终到达目的地主机r目的地返回ICMP “主机不可达”分组 (类型3, 编码3)r当源得到该ICMP, 停止网络层57第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层58IPv6r初始动机: 32-bit地址空间很快将会被完全分配完r附加的动机:m首部格式帮助速率处理/转发m首部变化以促进QoS IPv6 数据报格式: m固定长度 40 字节首部m不允许分段网络层59IPv6首部(续)优先级 : 标识特殊流的分组优先权流标签: 标识在相同“流”中的i数据报(流的概念没有很好定义)下一个首部: 标识数据的上层协议网络层60与IPv4相比的其他变化r检查和: 完全去除以减小每跳的处理时间r选项: 允许，但在首部之外，由“下一个首部”字段指示rICMPv6: 新版本的 ICMPm附加的报文类型，如 “分组太大”m多播组管理功能网络层61从 IPv4到IPv6的迁移r并非所有的路由器能被同时更新m无“标志日 ”mIPv4和IPv6路由器混合将如何运行? r隧道: 在IPv路由器之间IPv6数据报作为IPv4数据报的负载网络层62隧道ABEFIPv6IPv6IPv6IPv6隧道逻辑视图:物理视图:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4流: X源: A目的: F数据流: X源: A目的: F数据流: X源: A目的: F数据源:B目的: E流: X源: A目的: F数据源:B目的: EA-to-B:IPv6E-to-F:IPv6B-to-C:IPv6 在IPv4中B-to-C:IPv6 在IPv4中网络层63第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层64直接和间接交付r直接交付直接交付m是指在一个物理网络上，数据报从一台机器上直接传送到另一台机器上，这是所有互联网通信的基础。只有当两台机器同时连到同一底层物理传输系统时(例如一个以太网)，才能进行直接交付r间接交付间接交付m当目的地不在一个直接连接的网络上时，发送方必须把数据报发给一个路由器才能交付它r互联网中数据报交付的最后一步是直接交付，直接交付是间接交付的一个特例Q10.0.0.520.0.0.5R20.0.0.630.0.0.6S40.0.0.7网络10.0.0.0网络20.0.0.0网络30.0.0.0网络40.0.0.0网络层65Internet早期体系结构rARPANET 采用手工方式，设置指向其他网址的选路表r后期体系结构Core system网络层66默认路由：十分低效r默认路由虽能做到路由一致性，但却可能十分低效网络层67核心系统采用最优路由r为提高效率，所有核心路由器交换选路信息使得每个路由器都具有到所有目的站的最优路由的全部信息r如果在核心路由器的路由表上查不到某个数据报的目的站，它就发出 ICMP “目的站不可达”报文并抛弃这个数据报r就本质而言，网络层68核心系统不能分为若干部分r核心系统不能划分成若干保存部分信息的子集，否则可能无效r若主干分成路由器两个子集，每个子集保存部分信息并使用默认路由。这样的体系结构使得具有非法目的站的数据报形成了选路环路网络层69对等主干网结构rARPANET 与 NSFNET 之间建立了多个连接，增加了路由选择结构的复杂性。这两个网络称为对等主干网络，或简称为对等网(peers)网络层70对等主干网中 IP 选路的多样性r对等主干网配置，一对地理位置接近的主机之间的流量应该选择最短的路径m从主机 3 到主机 1 的通信量通过R1r主机 3 到主机 2 的路由有多条m如果这些主干分属不同ISP，是否有问题？网络层71体系结构复杂性的限制r除非互联网范围很小，否则不能让所有路由器直接参与选路更新协议m即使与互联网连接站点仅有一个本地网络，核心体系结构也不能满足任意数量的需要，否则选路流量太大m每个网点不能容纳多个路由器和网络，因为只有与主干网直接相连的路由器才能直接通信m在大型互联网中，网络和路由器并非由一个实体管理，也没有使用最短路 网络层72核心系统的重要启示r限制参与同一个选路协议的路由器数量，表明某些路由器将被排除在该组外，它需要有一些默认路由m在早期Internet中，非核心路由器把数据报交给核心系统来交付r重要启示网络层73需要建立获得路由信息的机制r选路信息必须在两个方向流动：m从一组参与路由器到一个非参与路由器m非参与路由器必须将隐藏网络的信息传给该组网络层74自治系统的概念r从选路的角度来说，处于一个管理机构控制之下的网络和路由器群组称为一个自治系统(autonomous system，AS)rAS可能有复杂结构，该独立机构要负责保证其内部的路由信息的一致性和可用性r在AS内的路由器，可以自由地选择寻找路由、广播路由、确认路由以及检测路由的一致性的机制m可安排R3通告网络2、3和4(R1知道网络1)r核心路由器自己也构成一个自治系统网络层75从一个核心网到独立的自治系统r为了使在AS中的隐藏网络能到达 Internet ，每个AS必须向其他AS通告自己的网络r在AS中使用IGP，在AS之间使用EGPEGPIGPIGP网络层76第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层77选路选路算法的图论抽象:r图中的节点是路由器r图中的边是物理链路m链路代价: 时延，费用或拥塞等级目的：决定从源到目的地通过网络的“好的路径”(路由器序列)选路 协议AEDCBF2213112535r“好的”路径:m通常意味着最小费用的路径m其他定义也是可能的网络层78选路算法分类全局的或分散的信息?r分散的: 路由器知道物理相连的邻居，到邻居的链路费用计算的迭代过程，与邻居交换信息“距离矢量” 算法r全局的:所有路由器具有完全的拓扑、链路费用信息“链路状态”算法s静态的或动态的?r静态: 路由随时间缓慢变化r动态: 路由更快地变化m周期的更新m适应链路费用变化网络层79A Link-State 选路算法Dijkstra算法r所有节点知道网络拓扑、链路费用m经“链路状态广播”完成m所有节点具有相同信息r从一个节点(源)到所有其他节点计算最低费用路径m给出对这些节点的转发表r迭代: k次迭代后，得知到k个目的地的最低费用路径概念:rc(x,y): 从节点x到y的链路费用; = 如果不是直接邻居rD(v):从源到目的地v路径费用的当前值rp(v): 从源到v沿路径的前任节点rN: 已知在最小费用路径中的节点集合网络层80Dijsktra算法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中中 网络层81Dijkstra 算法: 例子步骤012345NuuxuxyuxyvuxyvwuxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,uD(y),p(y)2,xD(z),p(z) 4,y4,y4,yyxwvz2213112535网络层82Dijkstra算法, 讨论算法复杂性: n个节点r每次迭代: 需要检查所有节点w, 不在N中rn(n+1)/2 对比: O(n2)r更有效的实现是可能的: O(nlogn)可能振荡:r如链路费用 = 承载流量的量wzyx11+ee0e1100wzyx2+e0001+e 1wzyx02+e1+e10 0wzyx2+e0e01+e 1最初 重计算选路 重计算重计算e11e11e11网络层83第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层84距离矢量算法(1)Bellman-Ford方程 (动态规划)定义dx(y) := 从x到y最低费用路径的费用则dx(y) = min c(x,v) + dv(y) 其中min对x的所有邻居网络层85Bellman-Ford 例子 (2)yxwvz2213112535Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3du(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取最小的节点是在最短路中的下一跳 转发表B-F equation says:网络层86距离矢量算法(3)基本思想: r每个节点周期性的发送它自己的距离矢量以估计到其邻居r当节点x接收到来自邻居的新DV估计，它使用B-F方程更新其自己的DV :Dx(y) minvc(x,v) + Dv(y) for each node y Nr在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用 dx(y) 网络层87距离矢量算法(4)迭代、异步: 每次本地迭代由下列引起: r本地链路费用改变rDV从邻居更新报文分布式:r每个节点仅当其DV改变时通知邻居m如果必要，邻居则通知它们的邻居等待 (来自邻居本地费用报文的变化)重新计算 估计值如果到任何目的地的DV已经变化, 通知 邻居 每个节点:网络层88距离矢量: 链路费用变化链路费用变化:r好消息传播得快r坏消息传播得慢“计数到无穷”问题!r在算法稳定前，迭代44 次: 参见课文毒性逆转: r如果Z路由通过Y得到 X :mZ告诉Y它(Zs)到X的距离是无穷 (因此Y将不能经Z路由到X)r这将完全解决计数到无穷问题? xz1450y60网络层89LS和DV算法的比较报文复杂性rLS: 对n个节点，E条链路, 发送O(nE) 报文 rDV: 仅在邻居之间交换m收敛时间变化收敛速度rLS: O(n2) 算法要求 O(nE)报文m可能具有振荡rDV: 收敛时间变化m可能有选路环路m计数到无穷问题健壮性: 如果路由器异常，将发生什么现象?LS: m节点可能通告不正确的链路费用m每个节点仅计算它自己的表DV:mDV节点通告不正确的路径费用m每个节点表能由其他人使用 差错通过网络传播网络层90第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层91等级选路规模: 具有2亿个目的地:r在选路表中不能存储所有的目的地!r选路表交换将堵塞链路! 管理自治r互联网 = 网络的网络r每个网络管理员可能要控制他自己网络中的选路我们的选路研究至此是理想的r所有路由器是等同的r网络“扁平” 实践中并不真实网络层92等级选路r将某区域的路由器聚合成为 “自治系统” (AS)r在相同AS中的路由器运行相同的选路协议m“intra-AS” 选路协议m在不同的AS中的路由器能够运行不同的intra-AS 选路协议网关路由器r直接链路到在另一个AS中的路由器网络层933b1d3a1c2aAS3AS1AS21a2c2b1bAS内部选路 算法AS之间选路 算法转发表3c互联的ASr转发表由AS内部和AS之间的选路算法所配置mAS内部设置内部目的地表项mAS之间和AS内部对外部目的地设置表项网络层943b1d3a1c2aAS3AS1AS21a2c2b1b3cAS间的任务r假定在AS1中的路由器接收目的地是AS1外部的数据报m路由器应当将分组朝着网关路由器转发，但哪个呢？AS1需要:1.知道通过AS2可到达哪些目的地，通过AS3到达哪些2.传播这些可达信息到AS1中所有路由器AS间选路的工作!网络层95例子: 设置路由器1d的转发表r假定AS1从AS间协议得知子网 x 从AS3(网关1c)可达，而不是从rAS间协议传播可达性信息到所有内部路由器r路由器1d从AS内部信息决定，它的接口I正处于到1c的最低费用路径上r在转发表中放入表项(x,I).网络层96从AS间协议得知，子网x经多个网关可达使用来自AS内部协议选路信息，以决定到每个网关的最低费用路径热土豆选路:选择具有最小费用的网关从转发表决定接口I 通向最低费用网关。表项Enter (x,I) 在转发表中例子: 在多个AS之间选择r现在假定AS 1从AS间协议得知，子网x 从AS3和从AS2可达r为了配置转发表, 路由器1d必须决定对目的地x ，它应当将分组转发向哪个网关r这也是AS间选路协议的工作!r热土豆选路: 发送分组朝着两个路由器中最近的那个网络层97第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层98RIP ( 选路信息协议)r距离矢量算法r包括在1982中的 BSD-UNIX Distributionr距离度量: 跳的数量(最大 = 15跳)DCBAuvwxyz 距离 跳 u 1 v 2 w 2 x 3 y 3 z 2 网络层99RIP通告r距离矢量: 每30秒在邻居之间经响应报文(又称为通告)交换r每个通告：在AS中包括多达2