网络层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本地网络中的设备不显式地可寻址、由外部所见(增强安全性)网络层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后期体系结构mm由少量、集中的路由器来保存全部目的站的信息由少量、集中的路由器来保存全部目的站的信息mm其他大量的外部路由器仅包含部分信息其他大量的外部路由器仅包含部分信息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重要启示mm如果组外的一个路由器使用一些组作为默认如果组外的一个路由器使用一些组作为默认路由，选路将是次优的路由，选路将是次优的mm在不能满足大量路由器或一个广域网情况下，在不能满足大量路由器或一个广域网情况下，非参与路由器使用参与路由器交付非参与路由器使用参与路由器交付网络层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,yu uyxwvz2213112535网络层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)u uyxwvz2213112535Clearly, 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间选路的工作!网络层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中包括多达25个目的网络的列表网络层100RIP: 例子 目的网络目的网络 下一个路由器下一个路由器 到目的地的跳数到目的地的跳数 wA2yB2 zB7x-1.wxyzACDB在D中选路表网络层101RIP: 例子 目的网络目的网络 下一个路由器下一个路由器 到目的地的跳数到目的地的跳数 wA2yB2 zB A7 5x-1.选路 table in DwxyzACDB 目的地目的地 下一个下一个 跳跳 w - - x - - z C 4 . .从从A到到D通告通告网络层102RIP: 链路故障与恢复在180 sec后，如果无通告首部 - 邻居/链路宣告死亡m经使无效邻居的路由m新的通告发送给邻居m邻居依次发送出新的通告(如果表变化)m链路故障信息迅速地传播到整个网络m使用毒性逆转以防止ping-pong回路 (无限距离 = 16 跳)网络层103RIP表处理rRIP选路表由称为route-d (守护进程)的应用级进程管理r通告在UDP分组中发送，周期地重复物理层链路层网络层 转发表 (IP)运输层 (UDP)routed物理层链路层网络层 (IP)运输层 (UDP)routed转发表网络层104第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层105OSPF (开放最短路优先)r“开放”: 公共可用r使用链路状态算法 mLS分组分发m在每个节点拓扑图m使用 Dijkstra算法的路由计算rOSPF携带每个邻居路由器一个项r通告散布到整个AS(经洪泛)m携带在OSPF报文中直接封装在IP中(而不是TCP或UDP)网络层106OSPF “先进的”特色 (RIP所不具有的)r安全性: all OSPF messages authenticated (to prevent malicious intrusion) r运行多条费用相同的路径(在RIP中仅一条路径)r对每条链路，对不同的TOS(服务类型)，设置多种费用度量(如卫星链路费用置为用于尽力而服务为“低”，高为实时服务)r综合的单播和多播支持: m多播OSPF (MOSPF)使用与OSPF相同的拓扑数据库r在大域中层次的OSPF网络层107层次OSPF网络层108层次OSPFr两级层次: 本地, 主干m链路状态通告仅在本地m每个节点具有详细的区域拓扑；仅知道到其他区域网络的方向(最短路)r区域边界路由器区域边界路由器 : “摘要”到在自己区域网络的距离，向其他区域边界路由器通告r主干路由器主干路由器 : 运行OSPF 选路限制到主干r边界路由器边界路由器 : 连接到其他AS网络层109第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层110Internet inter-AS 选路: BGPrBGP (边界网关协议): 事实上的标准rBGP为每个AS提供了一种手段 :1.从相邻AS获得子网可达性信息2.向AS内部的所有路由器传播可达性信息3.基于可达性信息和策略，决定到子网的“好”路由r允许一个子网向因特网其余部分通告他的存在： “I am here”网络层111BGP基础r路由器的对(BGP对等方)交换选路信息通过半永久的TCP连接: BGP会话r注意到BGP会话不对应着物理链路(覆盖网络)r当AS2向AS1通告一个前缀, AS2则承诺它将转发任何指向该前缀的数据报mAS2能够在它的通告中聚合前缀3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP会话iBGP会话网络层112分发可达性信息r在3a和1c之间有eBGP 会话，AS3向AS1发送前缀可达性信息r1c则能使用iBGP来向AS1中的所有路由器分发这种新前缀可达信息 r1b则能经1b到2a的eBGP会话向AS2重新通告新的可达信息r当路由器知道了一个新前缀，它将在其转发表中未该前缀创建一个表项3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP会话iBGP会话网络层113路径属性 & BGP路径r当通告一个前缀，通告中包括了BGP属性mm前缀前缀 + + 属性属性 = = “ “路由路由” ”r两个重要的属性:mAS-PATH: 包含了对传递前缀的通告所经过的: AS 67 AS 17 m下一跳: 指示了到下一跳的特定内部AS路由器. (从当前AS到下一跳AS可能有多条链路.)r当网关路由器接收了路由通告，使用输入策略来接受/拒绝.网络层114BGP路径选择r路由器对某些前缀可能学到多于1条路由. 路由器必须选择路由.r消除规则 :1.本地偏好值属性 : 策略决定2.最短AS-PATH 3.选择下一跳路由器: 热土豆选路4.附加准则 网络层115BGP报文r使用TCP交换BGP 报文.rBGP报文:mOPEN: 对对等方和鉴别发送方打开TCP连接mUPDATE: 通告新的路径 (或撤销旧的)mKEEPALIVE 在没有UPDATES时，保持链路活跃;同时确认OPEN请求mNOTIFICATION:报告前面报文中的差错; 也用于关闭连接网络层116BGP选路策略rA,B,C 是提供商网络rX,W,Y是(提供商网络的)客户rX是双宿的: 连接到两个网络mX不希望路由从B经X到Cm. 因此X将不向B通告到C的路由网络层117BGP选路策略(2) A B C W X Y 图例：图例： 客户网络 提供商网络 rA向B通告路径AWrB向X通告路径 BAW rB应当向C通告路径BAW?m不! 因为W和C都不是B的客户，B不能从选路 CBAW 获得任何“收入”mB希望促使C向w经A选路mB希望仅向/到达它的客户选路!网络层118AS内选路和AS间选路有何不同? 策略: rAS间: 管理员希望控制它的流量选路的方式，谁能通过它的网络路由. rAS内: 单个管理员，因此不需要策略决定规模:r等级选路节省选路表长度，减小更新流量性能性能: rAS内: 能够关注性能rAS间: 策略将比性能更为重要网络层119第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路r4.8 广播和多播选路m多播优点m硬件多播m多播的特性mIGMPm广播 选路算法m多播选路算法网络层120多播是什么？单播广播多播任播向一台主机寻址向所有主机寻址向某些主机寻址向一台或多台主机的几个接口接口寻址网络层121单播vs.多播单播多播网络层122为何多播 ?r当向多个接收方发送相同的数据m更好的带宽利用率m较少的主机/路由器处理m更快的参与r应用m视频/音频广播 (电视，无线电类)m视频会议m实时新闻分发网络层123第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路r4.8 广播和多播选路m多播优点m硬件多播m多播的特性mIGMPm广播 选路算法m多播选路算法网络层124硬件广播r广播意味着网络向每一个目的地传递一个分组的拷贝。在总线技术中，广播交付可由传递单个分组完成r对多数硬件技术，通过向一个特定、保留的目的地址(称为广播地址)发送分组，实现广播m以太网用48 bit的全1地址表示广播地址r定义广播传递地址来指定广播交付。机器硬件识别本机硬件地址及广播地址，接收目的地址为这两者的分组r广播的主要缺点：每个广播都要消耗所有机器上的资源网络层125硬件多播r允许每台机器选择是否参与多播通信r保留了大量用于多播的地址。当一组机器要通信时，它们选择一个特殊的多播地址用于通信r配置好网络接口硬件以识别某多播地址后，组中所有机器就会收到送到该多播地址上每个分组的拷贝r单播和广播地址 vs. 多播地址m前者标识与一个物理网段相连的计算机，转发取决于网络拓扑；后者标识接收者的任意集合，须送往所有网段 网络层126以太网多播r保留以太网地址的一半用于多播r高阶八位组的低阶比特置 1标识明了多播地址，置 0标识单播地址mm多播地址：多播地址：01.00.00.00.00.0016r网络接口卡初始被配置成单播或广播地址mm单播地址：单播地址：00.00.00.00.00.0016r网卡驱动程序能重新配置该卡为允许识别一个或多个多播地址mm多播地址：多播地址：0 01 1.5E.00.00.00.0016网络层127IP 多播映射到以太网多播 要把 IP 多播地址映射成相应的以太网多播地址，只需将 IP 多播地址的低阶 23 比特放到指定的以太网多播地址 01.5E.00.00.00.0016 的低阶 23 比特上。m例：IP 多播地址 224.0.0.2 映射为以太网多播地址 01.5E.00.00.00.0216。r这种映射并不唯一，是折衷的结果网络层128第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路r4.8 广播和多播选路m多播优点m硬件多播m多播的特性mIGMPm广播 选路算法m多播选路算法网络层129IP 多播及特征rIP多播是硬件多播的互联网抽象r允许向主机的子集(被称为多播组)传输IP数据报，该子集能够跨越互联网上的任意网络rIP多播的特征mm组地址。组地址。每个多播组拥有唯一多播地址(D 类地址)。少数是永久的，其他是临时的；仅能用作目的地址mm组的数量。组的数量。228个多播组，限制是选路表mm动态组关系。动态组关系。主机能随时加入或离开组；能够是任意多组的成员网络层130IP多播特征(续)mm硬件的使用。硬件的使用。如网络硬件支持多播，则用硬件组播发送IP多播；如不支持，则用广播或单播传递mm网络间的转发。网络间的转发。组成员能与多个物理网相连，要有特殊的多播路由器转发IP多播mm传递语义。传递语义。IP 多播使用尽力而为的交付语义，多播数据报可能出现丢失、迟延、重复以及乱序到达的现象mm成员关系和传输。成员关系和传输。任意主机能向任何多播组发送数据报；组关系仅用于决定该主机是否能接收发往该组的数据报网络层131主机和多播传递rIP多播可用于单个物理网或Internetm对前者，将数据报放入帧中，用硬件多播能力m对Internet ，主机向多播路由器发送数据报，用多播路由器转发多播数据报r主机不用安装对多播路由器的路由或默认路由，仅用本地网络的硬件多播能力传输数据报r本地或非本地多播间的主要差异在于多播路由器，不在主机网络层132主机软件如何接收IP多播？rIP 软件须有接口，以允许应用程序加入或退出某个多播组m如多个应用程序加入同一个组，IP 软件必须为每个应用程序传送收到的送给该组数据报m如所有应用程序都已经退出该组，主机必须记住自己不要再参与相应的多播组的工作m主机必须允许协议把自己的组关系状态向本地多播路由器作通知r一个基本概念 主机加入特定网络上的特定主机加入特定网络上的特定 IP IP 多播组。多播组。r组成员关系与具体网络相关，软件为与该机器相连的每个网络独立地保留多播地址表网络层133第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路r4.8 广播和多播选路m多播优点m硬件多播m多播的特性mIGMPm广播 选路算法m多播选路算法网络层134Internet组管理协议：IGMPr在多个网络中多播的两个过程mIGMP：主机或多播路由器为参与多播，通知本地的多播路由器m多播树：本地多播路由器与其他多播路由器联系，传送组成员关系信息，建立多播路由rIGMP 类似于 ICMP(当前为IGMPv2)m使用IP数据报携带消息m提供由IP使用的服务 虽然虽然 IGMP IGMP 使用使用 IP IP 数据报来携带报文，我们认数据报来携带报文，我们认为为 IGMP IGMP 是是 IP IP 协议整体中的一部分，而不是协议整体中的一部分，而不是一个独立的协议。一个独立的协议。网络层135IGMP ：工作两阶段r主机加入一个新组时m发送一个 IGMP 报文给多播地址的全部主机，宣布该成员关系m本地多播路由器接收该报文后，向其他多播路由器传播该关系信息以建立必要的路由r本地多播路由器周期性地轮询本地网络上的主机m确定各组中有哪些主机m如果经过若干个轮询后，某组中始终没有成员，多播路由器就认为该组中不再有本网络中的主机，于是停止向其他多播路由器通告该组的成员关系信息网络层136第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路r4.8 广播和多播选路m多播优点m硬件多播m多播的特性mIGMPm广播 选路算法m多播选路算法网络层137R1R2R3R4(a)R1R2R3R4(b)duplicatecreation/transmissionduplicateduplicate广播选路算法r源复制vs.网络中复制r无控制洪泛 m广播风暴r受控洪泛m序列号控制的洪泛m反向路径转发 (RPF)网络层138ABGDEcF当路由器接收到广播分组时，仅当该分组到达的链路正好是位于它自己最短单播路径返回其源的路径上，它才向其所有出链路（除了它接收的那个）传输报文。否则，丢弃入分组。因为该路由器知道它或者将接收，或者已经接收在位于返回发送方自己最短路的链路上的该分组拷贝。 反向路径转发网络层139ABGDEcFABGDEcF(a) 从从A发起的广播发起的广播(b)从从D发起的广播发起的广播沿着生成树的广播网络层140ABGDEcF12345(a)逐步构造的生成树逐步构造的生成树E是中心ABGDEcF(b) 构造的生成树构造的生成树基于中心的生成树构造网络层141第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路r4.8 广播和多播选路m多播优点m硬件多播m多播的特性mIGMPm广播 选路算法m多播选路算法网络层142多播选路: 问题陈述r目的：目的：寻找一棵(或多棵)树，连接与有本地多播组成员的路由器相连m树: 连接所有使用的路由器的无环路径m基于源: 从每个发送方到所有接收方的不同的树m共享树: 所有组成员使用的相同树共享树基于源的树网络层143构建多播树的方法方法:r基于源的树: 每源一棵树m最短路树m反向路径转发r组共享树: 组使用一棵树m最小生成树 (Steiner) m基于中心的树我们先看基本的方法，然后学习采用这些方法的特定协议网络层144最短路树r多播转发树: 从源到所有接收方最短路径路由的树mDijkstra算法R1R2R3R4R5R6R7216345i有组成员联系的路由器没有组成员联系的路由器用于转发的链路, i 指示由算法所加的链路次序图例S: 源网络层145第4章 网络层r4.7 广播和多播选路m多播优点m硬件多播m多播的特性mIGMPm广播 选路算法m多播选路算法网络层146第4章 网络层r4.7 广播和多播选路m多播优点m硬件多播m多播的特性mIGMPm广播 选路算法m多播选路算法网络层147反向路径转发 if (在入链路上接收到的多播数据报位于返回到中心的最短路上) then 向所有出链路洪泛数据报 else 忽略数据报q依赖从路由器到发送方单播最短路的知识q每台路由器具有简单的转发行为:网络层148反向路径转发 : 例子结果是一棵特定源的反向SPT具有不对称链路可能是一种坏的选择R1R2R3R4R5R6R7有组成员联系的路由器没有组成员联系的路由器数据报将被转发图例S: 源数据报将不被转发网络层149反向路径转发 : pruningr转发树包含了五多播组成员的子树m无必要向这些子树转发数据报m“剪枝”报文由下游无组成员的路由器发送R1R2R3R4R5R6R7剪枝报文图例S: 源具有多播转发的链路PPP有组成员联系的路由器没有组成员联系的路由器网络层150共享树: Steiner树rSteiner树: 与具有联系组成员所有路由器连接的最小费用树r问题是NP完全的r存在好的启发式算法r实践中并未使用:m计算复杂性m需要整个网络的信息m整体的: 无论何时一台路由器加入/离开需要再运行网络层151基于中心的树r由所有共享的单一交付树r一台路由器标识为树的“中心”r加入:m边缘路由器向中心路由器发送单播join-msgmjoin-msg 由中间的路由器和“处理”并向中心转发mjoin-msg或者到达现有树的分支或到达该中心m由join-msg采用的路径成为对该路由器的树的新分支网络层152基于中心的树: 一个例子假定R6被选为中心 :R1R2R3R4R5R6R7生成的Join报文的路径次序图例2i31有组成员联系的路由器没有组成员联系的路由器网络层153因特网多播选路: DVMRPrDVMRP: 距离矢量多播选路 协议, RFC1075r洪泛与剪枝: 反向路径转发, 基于源的树m基于DVMRP自己的选路表的RPF 树，通过DVMRP路由器的通信构造m向多播组发起的数据报经RPF洪泛到各处 m无组成员的路由器：发送上游剪枝报文网络层154DVMRP: 续r软状态: DVMRP路由器周期性的 (1 分钟) “忘记”被剪枝的分支: m多播数据再次流向未剪枝的分支m下游路由器：再剪枝否则接收数据r路由器能够迅速嫁接到树上m遵循IGMP加入在叶节点r零碎的东西m通常在商业路由器中实现mMbone选路使用 DVMRP完成网络层155隧道问题：问题：怎样在单播路由器的“海洋”中连接多播路由器的“岛”呢？q多播数据报封装在“普通的”数据报中 (非多播编制的)q正常IP数据报经通用IP单播“隧道”发送到接收的多播路由器q接收多播路由器拆封，得到多播数据报物理拓扑逻辑拓扑网络层156PIM: 协议无关多播r不依赖任何特定基础单播选路算法 (与它们合作)r两种不同的多播分布情况:密集:q组成员分布密集，不彼此临近q带宽更为丰富稀疏:q具有组成员的网络数量与互联的网络数量相比小q组成员“广泛分布”q带宽不丰富网络层157稀疏-密集两种方法的后果: 密集r路由器假定有组成员，除非路由器显式剪枝r在多播树上的数据驱动结构 (如 RPF)r带宽和非组路由器处理消耗大稀疏:r除非路由器显式加入，否则认为无成员r在多播树上的接收方驱动结构 (如基于中心的)r带宽和非组路由器处理保守网络层159PIM - 稀疏模式r基于中心方法r路由器向集合点(RP)发送join 报文m中间路由器更新状态并转发joinr经RP加入后，路由器能够切换到特定源的树上m提升性能: 更少的集中, 较短的路径R1R2R3R4R5R6R7joinjoinjoin所有数据多播来自集合点集合点网络层160PIM - 稀疏模式发送方：r向RP单播数据, 这沿以RP为根树向下分发rRP能够向源上游扩展多播树 r如果没有联系的接收方，RP能够停止报文m“无人在听!”R1R2R3R4R5R6R7joinjoinjoin所有数据多播来自集合点集合点网络层161网络层: 小结下一站: 数据链路层!我们已经学习的内容:r网络层服务r选路原则: 链路状态和距离矢量r等级选路rIPr互联网选路协议RIP, OSPF, BGPr路由器构成rIPv6