网络层协议

null 第七章 网络层 第七章 网络层协议主要内容主要内容预备 IP地址计算 7.1 网络层概述 7.2 路由算法 7.2.1 最优化原则 7.2.2 最短路径路由算法 7.2.3 洪泛算法 7.2.4 基于流量的路由算法 7.2.5 距离向量路由算法 7.2.6 链路状态路由算法 7.2.7 分层路由 7.2.8 移动主机的路由 7.3 拥塞控制算法 7.3.1 拥塞控制的基本原理 7.3.2 拥塞控制算法 null7.4 网络互连 7.4.1 级联虚电路 7.4.2 无连接网络互连 7.4.3 隧道技术 7.4.4 互联网路由 7.4.5 分段 7.4.6 防火墙 7.5 INTERNET网络层协议 7.5.1 IP协议 7.5.2 Internet控制协议 7.5.3 内部网关路由协议：OSPF 7.5.4 外部网关路由协议：BGP 7.6 路由器体系结构和关键技术IP 地 址 的 分 类 及 规 划 IP 地 址 的 分 类 及 规 划 TCP/IP 地 址 概 述TCP/IP 地 址 概 述介 绍 TCP/IP 地 址 介 绍 TCP/IP 地 址 只允 许 具 有 唯 一 地 址 的 工 作 站 进 行 通 讯IP 地 址 IP 地 址 172 . 16 . 122 . 204IP 地 址 分 类 IP 地 址 分 类 Class A: Class B: Class C: Class D: for multicast Class E: for researchN = Network number assigned by NIC H = Host number assigned by network administratorIP 地 址 位IP 地 址 位识 别 IP地 址 分 类 (第 一 字 节 )识 别 IP地 址 分 类 (第 一 字 节 )High Order BitsOctet in DecimalAddress Class0 10 1101 -126 128 -191 192 -223A B C练 习 : IP 地 址 分 类 练 习 : IP 地 址 分 类 AddressClassNetworkHost10.2.1.1128.63.2.100201.222.5.64192.6.141.2130.113.64.16256.241.201.10A10.0.0.00.2.1.1B128.63.0.00.0.2.100C201.222.5.00.0.0.64C192.6.141.00.0.0.2B130.113.0.00.0.64.16NonexistentIP 地 址 规 划 IP 地 址 规 划 Host 地 址 Host 地 址 172.16.200.1172.16.3.10172.16.12.12IP: 172.16.2.110.1.1.110.250.8.1110.180.30.118IP: 10.6.24.2E0E1172.161212NetworkHost..地 址 没 有 进 行 子 网(SubNets)地 址 没 有 进 行 子 网(SubNets)Network 172.16.0.0172.16.0.0地 址 有 子 网 (SubNets)地 址 有 子 网 (SubNets)Network 172.16.0.0Subnet Mask (子 网 掩 码 )Subnet Mask (子 网 掩 码 )IP 地 址 NetworkHost十 进 制 与 位 的 等 值 十 进 制 与 位 的 等 值 子 网 掩 码 (Subnet Mask)没 有 子 网 (Subnets)子 网 掩 码 (Subnet Mask)没 有 子 网 (Subnets)不 用 子 网 (Subnets) ___ 缺 省 NetworkHost172.16.2.160255.255.0.01721600101011001111111110101100000100001111111100010000000000000000000010100000000000000000000000000010子 网 掩 码 (Subnet Mask)没 有 子 网 (Subnets子 网 掩 码 (Subnet Mask)没 有 子 网 (Subnets网 络 号 码 扩 展 8位 (bits)NetworkHost172.16.2.160255.255.255.01721620Subnet 111111111111111100000000111111111010110010101100000100000001000000000010101000000000000000000010练 习 : 子 网 掩 码 (Subnet Masks)练 习 : 子 网 掩 码 (Subnet Masks)AddressSubnet MaskClassSubnet172.16.2.1010.6.24.20172.30.36.12255.255.255.0255.255.0.0255.255.255.0B172.16.2.0A10.6.0.0B172.30.36.0子 网 规 划 子 网 规 划 B类 子 网 划 分 例 子 B类 子 网 划 分 例 子 子 网 (Subnet)地 址 = 172.16.2.0 主 机 (Host )地 址 = 172.16.2.1-72.16.2.254 广 播 (Broadcast) 地 址 = 172.16.2.255 八 位 子 网 IP Host Address: 172.16.2.120 Subnet Mask: 255.255.255.0NetworkSubnetHost1721620172.16.2.120:255.255.255.0 /8:1010110011111111Subnet:1010110000010000000100001111111100000010000000101111111101111001 0000000000000000C类 地 址 例 子 C类 地 址 例 子 子 网 (Subnet)地 址 = 201.222.5.120 主 机 (Host)地 址 = 201.222.5.121-01.222.5.126 广 播 (Broadcast) 地 址 = 201.222.5.127 5 位 子 网 IP Host Address: 201.222.5.121 Subnet Mask: 255.255.255.248NetworkSubnetHost2012225120201.222.5.121:1100100111111111Subnet:1100100111011110110111101111111100000101000001011111111101111 001 11111 00001111 000255.255.255.248 /5:广 播 (Broadcast)地 址 广 播 (Broadcast)地 址 练 习 : 广 播 (Broadcast)地 址 练 习 : 广 播 (Broadcast)地 址 地 址 类 子 网 广 播 201.222.10.60255.255.255.248子 网 掩 码 15.16.193.6255.255.248.0128.16.32.13255.255.255.252153.50.6.27255.255.255.128C201.222.10.56201.222.10.63A15.16.192.015.16.192.255B128.16.32.12128.16.32.15B153.50.6.0153.50.6.127子 网 (Subnetting)例 子 子 网 (Subnetting)例 子 Cisco ACisco BE0S0E0S0T0Cisco AE0: 172.16.2.1 S0: 172.16.1.1 S0: 172.16.1.2 E0: 172.31.4.1 T0: 172.31.16.1 Cisco BMask255.255.255.0/8Subnet172.16.2.0172.16.1.0172.16.1.0172.31.16.0172.31.4.0MaskSubnet255.255.255.0/8255.255.255.0/8255.255.255.0/8255.255.255.0/8公 有 地 址 :由 Internet Assigned Numbers Authority (IANA) 划 分 的 能 在 INTERNET上 用 得 地 址 公 有 地 址 :由 Internet Assigned Numbers Authority (IANA) 划 分 的 能 在 INTERNET上 用 得 地 址 公 有 地 址 与 私 有 地 址 私 有 地 址： 由 IANA 预 留 的 地 址： 10.0.0.0 - 10.255.255.255 172.16.0.0 - 172.31.255.255 192.168.0.0 - 192.168.255.255 7.1 网络层概述（1）7.1 网络层概述（1）ISO 定义 网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。 网络层是处理端到端传输的最低层。 网络层要解决的关键问题是了解通信子网的拓扑结构，选择路由。 网络层设计的有关问题 为传输层提供服务 面向连接服务 传统电信的观点：通信子网应该提供可靠的、面向连接的服务。7.1 网络层概述（2）7.1 网络层概述（2）无连接服务 Internet的观点：通信子网无论怎么设计都是不可靠的，因此网络层只需提供无连接服务。 IP/ATM，Fig. 5-1 网络层的内部组织 虚电路（virtual circuit） 数据报（datagram） 虚电路子网与数据报子网的比较 Fig. 5-2 路由器内存空间与带宽的权衡 虚电路方式，路由器需要维护虚电路的状态信息； 数据报方式，每个数据报都携带完整的目的/源地址，浪费带宽7.1 网络层概述（3）7.1 网络层概述（3）连接建立时间与地址查找时间的权衡 虚电路需要在建立连接时花费时间 数据报则在每次路由时过程复杂 虚电路方式很容易保证服务质量QoS（Quality of Service），但比较脆弱 虚电路方式很容易保证服务质量QoS(Quality of Service)，适用于实时操作，但比较脆弱。 数据报不太容易保证服务质量，但是对于通信线路的故障，适应性很强。 7.1 网络层概述（4）7.1 网络层概述（4）网络层为传输层提供的服务 面向连接服务：将复杂的功能放在网络层(通信子网)。 无连接服务：将复杂的功能放在传输层。 通信子网提供的服务（面向连接或无连接）与通信子网结构（虚电路或数据报）没有必然联系。 服务与子网结构的不同组合的例子 nullnull小结小结网络层的地位 通信子网的最高层； 位于数据链路层和传输层之间，使用数据链路层提供的服务，为传输层提供服务； 处理端到端传输的最低层。 网络层的作用 屏蔽各种不同类型网络之间的差异，实现互连 了解通信子网的拓扑结构，选择路由，实现报文的网络传输 网络层的两种实现方式 —— 数据报和虚电路 都属于分组交换，采用存储转发机制。 数据报(datagram)：每个分组被单独路由，分组带有全网唯一的地址 虚电路(virtual circuit)：先在源端和目的端之间建立一条虚电路，所有分组沿虚电路按次序存储转发，最后拆除虚电路。在虚电路中，每个分组无须进行路径选择。 网络层提供的服务 面向连接的服务和无连接的服务。7.2 路由算法（1）7.2 路由算法（1）路由算法是网络层软件的一部分 子网采用数据报方式，每个包都要做路由选择； 子网采用虚电路方式，只需在建立连接时做一次路由选择。 路由算法应具有的特性 正确性（correctness） 简单性（simplicity） 健壮性（robustness） 稳定性（stability） 公平性（fairness） 最优性（optimality） 路由算法分类 非自适应算法，静态路由算法 自适应算法，动态路由算法7.2 路由算法（2）7.2 路由算法（2）7.2.1 最优化原则 最优化原则（optimality principle） 如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J 到 K 的最优路由会落在同一路由上。 汇集树（sink tree） 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树； 路由算法的目的是找出并使用汇集树。 7.2 路由算法（3）7.2 路由算法（3）7.2.2 最短路径路由算法（Shortest Path Routing） 属于静态路由算法 基本思想 构建子网的拓扑图，图中的每个结点代一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。 测量路径长度的方法 结点数量 地理距离 传输延迟 距离、信道带宽等参数的加权数7.2 路由算法（4）7.2 路由算法（4）Dijkstra算法 每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注； 初始时，所有结点都为临时性标注，标注为无穷大； 将源结点标注为0，且为永久性标注，并令其为工作结点； 检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点； 在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点； 重复第四、五步，直到目的结点成为工作结点； 例，Fig. 5-6 算法实现，Fig. 5-7。程序与算法的区别是：从目的结点开始。nullnull7.2 路由算法（5）7.2 路由算法（5）7.2.3 洪泛算法（Flooding） 属于静态路由算法 基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。 主要问题 洪泛要产生大量重复包。 解决措施 每个包头包含站点计数器，每经过一站计数器减1，为0时则丢弃该包； 记录包经过的路径7.2 路由算法（6）7.2 路由算法（6）选择性洪泛算法（selective flooding） 洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。 应用情况 路由器和线路的资源过于浪费，实际很少直接采用； 具有极好的健壮性，可用于军事应用； 作为衡量标准评价其它路由算法。7.2 路由算法（7）7.2 路由算法（7）7.2.4 基于流量的路由算法（Flow-Based Routing） 属于静态路由算法 基本思想 既考虑拓扑结构，又兼顾网络负荷； 前提：每对结点间平均数据流是相对稳定和可预测的； 根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法。 提前离线（off-line）计算 需要预知的信息 网络拓扑结构； 通信量矩阵Fij； 线路带宽矩阵Cij； 路由算法（可能是临时的）。nullnull1/ = 800 bits 根据排队论，平均延迟 T = 1/ (C - )7.2 路由算法（8）7.2 路由算法（8）7.2.5 距离向量路由算法（Distance Vector Routing） 属于动态路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP协议采用。 基本思想 每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表； 以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离； 每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表； 邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X的距离为m，则路由器经过X到i的距离为Xi + m。根据不同邻居发来的信息，计算Xi + m，并取最小值，更新本路由器的路由表； 注意：本路由器中的老路由表在计算中不被使用。7.2 路由算法（9）7.2 路由算法（9）7.2 路由算法（10）7.2 路由算法（10）无限计算问题 算法的缺陷：对好消息反应迅速，对坏消息反应迟钝； 7.2 路由算法（11）7.2 路由算法（11）水平分裂算法 工作过程与距离向量算法相同，区别在于到X的距离不向真正通向X的邻居结点报告，使得坏消息传播的也快。 Fig. 5-11 虽然广泛使用，但有时候会失败。 7.2 路由算法（12）7.2 路由算法（12）7.2.6 链路状态路由算法（Link State Routing） 距离向量路由算法的主要问题 选择路由时，没有考虑线路带宽； 路由收敛速度慢。 链路状态路由算法 发现邻居结点，并学习它们的网络地址； 路由器启动后，通过发送HELLO包发现邻居结点； 两个或多个路由器连在一个LAN时，引入人工结点； Fig. 5-13 测量到每个邻居结点的延迟或开销； 一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。7.2 路由算法（13）7.2 路由算法（13）将所有学习到的内容封装成一个包； 包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表； 列表中对应每个邻居结点，都有发送方到它们的延迟或开销； Fig. 5-15 链路状态包定期创建或发生重大事件时创建。 将这个包发送给所有其它路由器； 基本思想：洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃； 改进 序号循环使用会混淆，解决办法：使用32位序号；7.2 路由算法（14）7.2 路由算法（14）路由器崩溃后，序号重置； 序号出错； 第二、三问题的解决办法：增加年龄（age）域，每秒钟年龄减1，为零则丢弃。 链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包； 链路状态包需要应答； Fig. 5-16 计算到每个其它路由器的最短路径。 根据Dijkstra算法计算最短路径； 实用协议 OSPF IS-ISnullnullnull从E发来的链路状态包有两个，一个经过EAB，另一个经过EFB； 从D发来的链路状态包有两个，一个经过DCB，另一个经过DFB；7.2 路由算法（15）7.2 路由算法（15）链路状态算法（LS）和距离向量算法（DV）的比较 路由信息的复杂性 LS 路由信息向全网发送 with n nodes, E links, O(nE) msgs sent each DV exchange between neighbors only 收敛（Convergence）速度 LS 使用最短路径优先算法，算法复杂度为O(n**2) n个结点（不包括源结点），需要n*(n+1)/2 次比较 使用更有效的实现方法，算法复杂度可以达到O(nlogn) 可能存在路由振荡（oscillations） DV convergence time varies may be routing loops count-to-infinity problem 7.2 路由算法（16）7.2 路由算法（16）健壮性: what happens if router malfunctions? LS node can advertise incorrect link cost each node computes only its own table DV DV node can advertise incorrect path cost each node’s table used by others error propagate thru network 7.2 路由算法（17）7.2 路由算法（17）Oscillations possible: e.g., link cost = amount of carried traffic 11+ee0e110002+e1+e100initially… recompute routing… recompute… recompute7.2 路由算法（18）7.2 路由算法（18）7.2.7 分层路由（Hierarchical Routing） 网络规模增长带来的问题 路由器中的路由表增大； 路由器为选择路由而占用的内存、CPU时间和网络带宽增大。 分层路由 分而治之的思想； 根据需要，将路由器分成区域（regions）、聚类（clusters）、区（zones）和组（groups）… Fig. 5-17，路由表由17项减为7项。 分层路由带来的问题 路由表中的路由不一定是最优路由。null7.2 路由算法（19）7.2 路由算法（19）7.2.8 移动主机的路由 需要解决的问题 为了能够将数据包转发给移动主机，网络必须首先要找到移动的主机。 网络结构示意图7.2 路由算法（20）7.2 路由算法（20）一些基本概念 移动用户（mobile users）：包括位置发生变化，通过固定方式或移动方式与网络连接的两类用户； 家乡位置（home location）：所有用户都有一个永久的家乡位置，用一个地址来标识； 外部代理（foreign agent）：每个区域（一个LAN或一个 wireless cell）有一个或多个外部代理，它们记录正在访问该区域的移动用户； 家乡代理（home agent）：每个区域有一个家乡代理，负责记录家乡在该区域，但是目前正在访问其它区域的用户。7.2 路由算法（21）7.2 路由算法（21）移动用户进入一个新区域时，必须首先向外部代理注册 外部代理定期广播声明自己的存在和地址的包，新到达的移动主机接收该信息；若移动用户未能收到该信息，则移动主机广播包，询问外部代理的地址； 移动主机向外部代理注册，告知其家乡地址、目前的数据链路层地址和一些安全信息； 外部代理与移动主机的家乡代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息； 家乡代理检查安全信息，通过，则给外部代理确认； 外部代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。 7.2 路由算法（22）7.2 路由算法（22）移动用户的路由转发过程 当一个包发给移动用户时，首先被转发到用户的家乡局域网； 该包到达用户的家乡局域网后，被家乡代理接收，家乡代理查询移动用户的新位置和与其对应的外部代理的地址； 家乡代理采用隧道技术，将收到的包作为净荷封装到一个新包中，发给外部代理； 家乡代理告诉发送方，发给移动用户的后续包作为净荷封装成包直接发给外部代理； 外部代理收到包后，将净荷作为数据链路帧发给移动用户； Fig. 5-19null小结小结最优化原则 路由算法的目的是找出并使用汇集树。 静态路由算法 最短路径路由算法 洪泛算法 基于流量的路由算法 动态路由算法 距离向量路由算法 将自己对全网拓扑结构的认识告诉给邻居 无穷计算问题，水平分裂算法 链路状态路由算法 将自己对邻居的认识洪泛给全网 分层路由 移动主机的路由 7.3 拥塞控制算法（1）7.3 拥塞控制算法（1）拥塞（congestion） 网络上有太多的包时，性能会下降，这种情况称为拥塞。 Fig. 5-22 拥塞产生的原因 多个输入对应一个输出； 慢速处理器； 低带宽线路。 解决办法 针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈； 需要全面考虑各个因素。7.3 拥塞控制算法（2）7.3 拥塞控制算法（2）拥塞控制与流量控制的差别 拥塞控制（congestion control）需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机、路由器等很多因素； 流量控制（flow control）与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。 null7.3 拥塞控制算法（3）7.3 拥塞控制算法（3）7.3.1 拥塞控制的基本原理 根据控制论，拥塞控制方法分为两类 开环控制 通过好的设计来解决问题，避免拥塞发生； 拥塞控制时，不考虑网络当前状态； 闭环控制 基于反馈机制； 工作过程 监控系统，发现何时何地发生拥塞； 把发生拥塞的消息传给能采取动作的站点； 调整系统操作，解决问题。7.3 拥塞控制算法（4）7.3 拥塞控制算法（4）衡量网络是否拥塞的参数 缺乏缓冲区造成的丢包率； 平均队列长度； 超时重传的包的数目； 平均包延迟； 包延迟变化（Jitter）。 反馈方法 向负载发生源发送一个告警包； 包结构中保留一个位或域用来表示发生拥塞，一旦发生拥塞，路由器将所有的输出包置位，向邻居告警； 主机或路由器主动地、周期性地发送探报（probe），查询是否发生拥塞。 7.3 拥塞控制算法（5）7.3 拥塞控制算法（5）7.3.2 拥塞控制算法 拥塞预防策略 开环控制 影响拥塞的网络设计策略 7.3 拥塞控制算法（6）7.3 拥塞控制算法（6）流量整形（Traffic Shaping） 开环控制 基本思想 造成拥塞的主要原因是网络流量通常是突发性的； 强迫包以一种可预测的速率发送； 在ATM网中广泛使用。 漏桶算法（The Leaky Bucket Algorithm） Fig. 5-24 将用户发出的不平滑的数据包流转变成网络中平滑的数据包流； 可用于固定包长的协议，如ATM；也可用于可变包长的协议，如IP，使用字节计数； 例，Fig. 5-25(a)(b)； 无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活。7.3 拥塞控制算法（7）7.3 拥塞控制算法（7）令牌桶算法（The Token Bucket Algorithm） 漏桶算法不够灵活，因此加入令牌机制； 基本思想：漏桶存放令牌，每T秒产生一个令牌，令牌累积到超过漏桶上界时就不再增加。包传输之前必须获得一个令牌，传输之后删除该令牌； Fig. 5-26 漏桶算法与令牌桶算法的区别 流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。 漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。nullnullnull7.3 拥塞控制算法（8）7.3 拥塞控制算法（8）流说明（Flow Specification） 一个数据流的发送方、接收方和通信子网三方认可的、描述发送数据流的模式和希望得到的服务质量的数据结构，称为流说明。 对发送方的流说明，子网和接收方可以做出三种答复：同意、拒绝、其它建议。7.3 拥塞控制算法（9）7.3 拥塞控制算法（9）虚电路子网中的拥塞控制 许可控制（admission control），基本思想：一旦发生拥塞，在问题解决之前，不允许建立新的虚电路； 另一种方法是发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区； 资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。 7.3 拥塞控制算法（10）7.3 拥塞控制算法（10）抑制包（Choke Packets） 基本思想 路由器监控输出线路及其它资源的利用情况，超过某个阈值，则此资源进入警戒状态； 每个新包到来，检查它的输出线路是否处于警戒状态； 若是，则向源主机发送抑制包，包中指出发生拥塞的目的地址。同时将原包打上标记（为了以后不再产生抑制包），正常转发； 源主机收到抑制包后，按一定比例减少发向特定目的地的流量，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、忽略抑制包；若在监听周期内没有收到抑制包，则增加负载； 通常采用的流量增减策略是：减少时，按一定比例减少，保证快速解除拥塞；增加时，以常量增加，防止很快导致拥塞。7.3 拥塞控制算法（11）7.3 拥塞控制算法（11）加权公平队列（Weighted Fair Queueing） 公平队列（Fair Queueing）算法 路由器的每个输出线路有多个队列； 路由器循环扫描各个队列，发送队头的包； 所有主机具有相同优先级； 一些ATM交换机、路由器使用这种算法； 一种改进：对于变长包，由逐包轮讯改为逐字节轮讯 Fig. 5-29 加权公平队列算法 给不同主机以不同的优先级； 优先级高的主机在一个轮讯周期内获得更多的时间片。 null7.3 拥塞控制算法（12）7.3 拥塞控制算法（12）逐跳抑制包（Hop-by-Hop Choke Packets） 在高速、长距离的网络中，由于源主机响应太慢，抑制包算法对拥塞控制的效果并不好，可采用逐跳抑制包算法； Fig. 5-30(a) 基本思想 抑制包对它经过的每个路由器都起作用； 能够迅速缓解发生拥塞处的拥塞； 上游路由器要求有更多的缓冲区； Fig. 5-30(b) null7.3 拥塞控制算法（13）7.3 拥塞控制算法（13）负载丢弃（Load Shedding） 上述算法都不能消除拥塞时，路由器只得将包丢弃； 针对不同服务，可采取不同丢弃策略 文件传输，优先丢弃新包，wine策略； 多媒体服务，优先丢弃旧包，milk策略； 早期丢弃包，会减少拥塞发生的概率，提高网络性能。7.4 网络互联（1）7.4 网络互联（1）互联网（internet）：两个或多个网络构成互联网。 多种不同网络（协议）存在的原因 历史原因：不同公司的网络产品大量使用； 价格原因：网络产品价格低，更多的人有权决定使用何种网络； 技术原因：不同网络采用不同技术、不同硬件、不同协议。7.4 网络互联（2）7.4 网络互联（2）网络互连设备 中继器（repeater） 物理层设备，在电缆段之间拷贝比特； 对弱信号进行放大或再生，以便延长传输距离。 网桥（bridge） 数据链路层设备，在局域网之间存储转发帧； 网桥可以改变帧格式。 多协议路由器（multiprotocol router） 网络层设备，在网络之间存储转发包； 必要时，做网络层协议转换。 传输网关（transport gateway） 传输层设备，在传输层转发字节流。 应用网关（application gateway） 应用层设备，在应用层实现互连； half-gateway（为了满足不同国家、组织的管理需要） Fig. 5-34null7.4 网络互联（3）7.4 网络互联（3）网络之间的区别 7.4 网络互联（4）7.4 网络互联（4）7.4.1 级联虚电路（Concatenated Virtual Circuits） 工作过程 级联虚电路工作过程与虚电路子网工作过程相似； 建立连接 当目的主机不在子网内时，则在子网内找一个离目的网络最近的路由器，与之建立一条虚电路； 该路由器与外部网关建立虚电路； 该网关与下一个子网中的一个路由器建立虚电路； 重复上述操作，直到到达目的主机。 传输数据 相同连接的包沿同一虚电路按序号传输； 网关根据需要转换包格式和虚电路号。 拆除连接null7.4 网络互联（5）7.4 网络互联（5）7.4.2 无连接网络互连（Connectionless Internetworking） 工作过程 无连接网络互连的工作过程与数据报子网的工作过程相似； 每个包单独路由，提高网络利用率，但不能保证包按顺序到达； 根据需要，连接不同子网的多协议路由器做协议转换，包括包格式转换和地址转换等。7.4 网络互联（6）7.4 网络互联（6）级联虚电路与无连接网络互连的比较 级联虚电路的优点 路由器预留缓冲区等资源，保证服务质量； 包按序号传输； 短包头。 级联虚电路的缺点 路由器需要大量内存，存储虚电路信息； 一旦发生拥塞，没有其它路由； 健壮性差； 如果网络中有一个不可靠的数据报子网，级连虚电路很难实现。7.4 网络互联（7）7.4 网络互联（7）无连接网络互连的优点 能够容忍拥塞，并能适应拥塞； 健壮性好； 可用于多种网络互连。 无连接网络互连的缺点 长包头； 包不能保证按序号到达； 不能保证服务质量。 7.4 网络互联（8）7.4 网络互联（8）7.4.3 隧道技术（Tunneling） 隧道技术 源和目的主机所在网络类型相同，连接它们的是一个不同类型的网络，这种情况下可以采用隧道技术。null7.4 网络互联（9）7.4 网络互联（9）工作过程（以Fig. 5-38为例） 主机1发送一个包，目的IP地址 = 主机2-IP，将包封装到局域网帧中，帧目的地址 = 路由器1-MAC； 局域网传输； 路由器1剥掉局域网帧头、帧尾，将得到的IP包封装到广域网网络层包中，包目的地址 = 路由器2地址； 广域网传输； 路由器2剥掉广域网包头，将得到的IP包封装到局域网帧中，包目的IP地址 = 主机2-IP，帧目的地址 = 主机2-MAC地址； 局域网传输； 主机2接收。 7.4 网络互联（10）7.4 网络互联（10）7.4.4 互联网路由（Internetwork Routing） 工作过程 互联网络的路由与单独子网的路由过程相似，只是复杂性增加； 两级路由算法 内部网关协议（IGP: Interior Gateway Protocol） RIP，OSPF 外部网关协议（EGP: Exterior Gateway Protocol） BGP 自治系统AS（Autonomous System）7.4 网络互联（11）7.4 网络互联（11）7.4.5 分段（Fragmentation） 每种网络都对最大包长有限制，有以下原因 硬件，例如 TDM 的时槽限制； 操作系统； 协议，例如包长度域的比特个数； 与标准的兼容性； 希望减少传输出错的概率； 希望避免一个包占用信道时间过长。 大包经过小包网络时，网关要将大包分成若干段（fragment），每段作为独立的包传输。7.4 网络互联（12）7.4 网络互联（12）段重组策略 分段重组过程对其它网络透明 网关将大包分段后，每段都要经过同一出口网关，并在那里重组； Fig. 5-41(a) 例，ATM网络； 带来的问题 出口网关需要知道何时所有分组都到齐； 所有分组必须从同一出口网关离开； 大包经过一系列小包网络时，需要反复地分段重组，开销大。7.4 网络互联（11）7.4 网络互联（11）分段重组过程对其它网络不透明 中间网关不做重组，而由目的主机做； Fig. 5-41(b) 带来的问题 对主机要求高，能够重组； 每个段都要有一个包头，网络开销增大； null7.4 网络互联（12）7.4 网络互联（12）标记段 树型标记法 例，包0分成三段，分别标记为0.0, 0.1, 0.2，段0.0构成的包被分成三段，分别标记为0.0.0, 0.0.1, 0.0.2； 存在的问题 段标记域要足够长 分段长度前后要一致 偏移量法 定义一个基本段长度，使得基本段能够通过所有网络； 包分段时，除最后一个段小于等于基本段长度外，所有段长度都等于基本段长度； 一个包可以包括几个段，包头中包括；原始包序号，包中第一个基本段的偏移量，最后段指示位； Fig. 5-42null7.4 网络互联（13）7.4 网络互联（13）7.4.6 防火墙（Firewalls） 什么情况下使用防火墙？ 为防止网络中的 信息泄露出去或不好的信息渗透进来，在网络边缘设置防火墙； Fig. 5-43 防火墙的一种常用配置 两个路由器，根据某种规则表，进行包过滤； 一个应用网关，审查应用层信息。 null小结小结互联网（internet）：两个或多个网络构成互联网 网络互连设备：中继器、网桥、路由器、传输网关、应用网关 虚电路网络互联 数据报网络互联 隧道技术 分段和重组 防火墙7.5 INTERNET网络层协议（1）7.5 INTERNET网络层协议（1）在网络层，Internet可以看成是自治系统的集合，是由网络组成的网络。 网络之间互连的纽带是IP（Internet Protocol）协议。7.5 INTERNET网络层协议（2）7.5 INTERNET网络层协议（2）7.5.1 IP协议 IP头格式 IP头包括20个字节的固定部分和变长（最长40字节）的可选部分，从左到右传输； 版本域（version）； IHL：IP包头长度，最小为5，最大为15，单位为32-bit word；7.5 INTERNET网络层协议（3）7.5 INTERNET网络层协议（3）服务类型域（Type of Service） 3个优先级位； 3个标志位：D（Delay）、T（Throughput）、 R（Reliability）； 2个保留位； 目前，很多路由器都忽略服务类型域。 总长度域（Total length） 标识域（Identification） DF：Don’t Fragment； 所有机器必须能够接收小于等于576字节的段。 MF：More Fragments 除最后一个段外的所有段都要置MF位。7.5 INTERNET网络层协议（4）7.5 INTERNET网络层协议（4）段偏移量（Fragment offset） 除最后一个段外的所有段的长度必须是8字节（基本段长）的倍数。One large datagram becomes several smaller datagrams7.5 INTERNET网络层协议（5）7.5 INTERNET网络层协议（5）生存期（Time to live） 实际实现中，IP包每经过一个路由器TTL减1，为0则丢弃，并给源主机发送一个告警包。 协议域（Protocol）：上层为哪种传输协议，TCP、UDP… 头校验和（Header checksum） 只对IP包头做校验； 算法：每16位求反，循环相加（进位加在末尾），和再求反。 源地址（Source address）和目的地址（Destination address） 7.5 INTERNET网络层协议（6）7.5 INTERNET网络层协议（6）选项（Options） 变长，长度为4字节的倍数，不够则填充，最长为40字节； 7.5 INTERNET网络层协议（7）7.5 INTERNET网络层协议（7）IP地址（IP Address） 地址组成：网络号 + 主机号； Fig. 5-47 地址表示采用用点分隔的十进制表示法，如166.111.68.3； 全0和全1有特殊含义 全0：表示本网络或本主机； 全1：表示广播地址； Fig. 5-48 子网（Subnets） 分而治之的思想：为了便于管理和使用，可以将网络分成若干供内部使用的部分，称为子网。对外界，该网络还是一个单独的网络。 Fig. 5-49 nullnullnull7.5 INTERNET网络层协议（6）7.5 INTERNET网络层协议（6）7.5.2 Internet控制协议 Internet控制报文协议ICMP（The Internet Control Message Protocol） 主要用来报告出错和测试； 报文类型 ICMP报文封装在IP包中。7.5 INTERNET网络层协议（7）7.5 INTERNET网络层协议（7）地址解析协议ARP（The Address Resolution Protocol） 解决网络层地址（IP地址）与数据链路层地址（MAC地址）的映射问题； Fig. 5-51 工作过程 建立一个ARP表，表中存放（IP地址，MAC地址）对； 若目的主机在同一子网内，用目的IP地址在ARP表中查找，否则用缺省网关的IP地址在ARP表中查找。若未找到，则发送广播包，目的主机收到后给出应答，ARP表增加一项； 每个主机启动时，广播它的（IP地址，MAC地址）映射； ARP表中的表项有生存期，超时则删除。null7.5 INTERNET网络层协议（8）7.5 INTERNET网络层协议（8）反向地址解析协议RARP（The Reverse Address Resolution Protocol） 解决数据链路层地址（MAC地址）与网络层地址（IP地址）的映射问题； 主要用于无盘工作站启动； 缺点：由于路由器不转发广播帧，RARP服务器必须与无盘工作站在同一子网内。一种替代协议BOOTP（使用UDP）。 7.5 INTERNET网络层协议（9）7.5 INTERNET网络层协议（9）7.5.3 RIP ( Routing Information Protocol) 内部网关协议IGP（interior gateway protocol）：自治系统AS内使用的路由算法，RIP、OSPF 外部网关协议EGP（exterior gateway protocol）：自治系统AS之间使用的路由算法，BGP RIP Distance vector algorithm Included in BSD-UNIX Distribution in 1982 RIPv1，RFC1058；RIPv2，RFC1723 Distance metric: # of hops (max = 15 hops) Distance vectors: exchanged every 30 sec via Response Message (also called advertisement)7.5 INTERNET网络层协议（10）7.5 INTERNET网络层协议（10）Destination Network Next Router Num. of hops to dest. w A 2 y B 2 z B 7 x -- 1 …. …. ....wxyzACDBRouting table in D7.5 INTERNET网络层协议（11）7.5 INTERNET网络层协议（11）RIP: Link Failure and Recovery If no advertisement heard after 180 sec --> neighbor/link declared dead routes via neighbor invalidated new advertisements sent to neighbors neighbors in turn send out new advertisements (if tables changed) link failure info quickly propagates to entire net poison reverse used to prevent ping-pong loops (infinite distance = 16 hops) 7.5 INTERNET网络层协议（12）7.5 INTERNET网络层协议（12）7.5.3 内部网关路由协议：OSPF 开放最短路径优先OSPF（Open Shortest Path First） 开放，公开发表； 支持多种距离衡量尺度，例如，物理距离、延迟等； 动态算法； 支持基于服务类型的路由； 负载平衡； 支持分层系统； 适量的安全措施； 支持隧道技术。7.5 INTERNET网络层协议（13）7.5 INTERNET网络层协议（13）构造有向拓扑图 根据实际的网络、路由器和线路构造有向图； 每个弧赋一个开销值； 两个路由器之间的线路用一对弧来表示，弧权可以不同； 多路访问（multiaccess）网络，网络用一个结点表示，每个路由器用一个结点表示，网络结点与路由器结点的弧权为0； Fig. 5-52null7.5 INTERNET网络层协议（14）7.5 INTERNET网络层协议（14）分层路由 自治系统AS可以划分区域（areas）； 每个AS有一个主干（backbone）区域，称为区域0，所有区域与主干区域相连； Fig. 5-53 一般情况下，有三种路由 区域内 区域间 从源路由器到主干区域； 穿越主干区域到达目的区域； 到达目的路由器。 自治系统间7.5 INTERNET网络层协议（15）7.5 INTERNET网络层协议（15）四类路由器，允许重叠 完全在一个区域内的内部路由器； 连接多个区域的区域边界路由器； 主干路由器； 自治系统边界路由器。 信息类型 null7.5 INTERNET网络层协议（16）7.5 INTERNET网络层协议（16）7.5.4 外部网关路由协议：BGP Why different Intra- and Inter-AS routing ? Policy Inter-AS: admin wants control over how its traffic routed, who routes through its net. Intra-AS: single admin, so no policy decisions needed Scale hierarchical routing saves table size, reduced update traffic Performance Intra-AS: can focus on performance Inter-AS: policy may dominate over performance7.5 INTERNET网络层协议（17）7.5 INTERNET网络层协议（17）边界网关协议BGP（Border Gateway Protocol） 通过TCP连接传送路由信息； 采用路径向量（path vector）算法，路由信息中记录路径的轨迹 similar to Distance Vector protocol each Border Gateway broadcast to neighbors (peers) entire path (I.e, sequence of ASs) to destination E.g., Gateway X may send its path to dest. Z: Path (X,Z) = X,Y1,Y2,Y3,…,Z Fig. 5-55 7.5 INTERNET网络层协议（18）7.5 INTERNET网络层协议（18）Suppose: gateway X send its path to peer gateway W W may or may not select path offered by X cost, policy (don’t route via competitors AS), loop prevention reasons. If W selects path advertised by X, then: Path (W,Z) = w, Path (X,Z) Note: X can control incoming traffic by controling it route advertisements to peers: e.g., don’t want to route traffic to Z -> don’t advertise