Part VII 广域网 (简称WAN), 路由, 和最短路径

前一课 跨越长距离提供数字通信的技术 通过本地回路给用户提供数字通信的技术 2019/4/28

本课 利用这些基础技术来构建分布在较大区域内的网络 动机 连接多台计算机：规模很大 跨越很长的地理长度 交互的公众道路 街道 建筑物 铁路 2019/4/28

WAN的基本构建单元 点到点的长距离连接 Packet switches：包交换机 2019/4/28

包交换机 是一种硬件设备 用于连接 其他包交换机 计算机 转发数据包 利用地址机制 2019/4/28

包交换机图示 是一个专用计算机，具有 中央处理器 存储器 I/O接口 固件 2019/4/28

组装一个广域网 在每个地点放置一台或多台包交换机 互连这些交换机 用LAN技术来处理 本地连接 用租用数字电路来进行长距离连接 2019/4/28

广域网的图示 互联的程度的取决于 通信量的估算 可靠性需求 2019/4/28

存储和转发 包交换机的基本模式 分组报文-packet 交换机-switch 从源计算机中发出 在交换机之间转发 抵达目的地 在存储器中存储分组报文 检查分组报文的目的地址 把分组报文发送到目的地 2019/4/28

广域网中的物理编址 基本要求 地址由两部分组成 每台计算机一个唯一的地址 高效转发 包交换机的编号 与之相连的计算机的编号 2019/4/28

对广域网寻址的图示 地址被编码成整形（由两部分组成） 高字节是交换机的序号 低字节是计算机的序号 2019/4/28

下一跳转发 由包交换机执行 使用路由表 路由表给出下一跳地址：注意！，只有一个，而非一串！ 2019/4/28

路由表缩写 多条表目指向同一个转向地址 路由表缩水 (缺省) 缩水后能提高查找的效率 2019/4/28

广域网中的路由选择 通过增加交换机可以扩大广域网的容量 路由表必须保证其有效性 内部交换机：不连接计算机 外部交换机：直接连接计算机 通用路由：必须包含到每个可能目的地的下一跳路由 最佳路由：到达指定目的地的下一跳必须指向到达目的地的最短路径。 2019/4/28

路由表信息的来源 手工 自动生成 人工生成路由表 在规模较小的网络中很有用 在路由不会改变的网络中也十分有用 由软件生成/更新路由表 这种方式在大型网络中是必需的 当发生错误时，它可改变路由 2019/4/28

路径选择和图论的关系 图 节点：交换机 边：连接 (由点对 (src, dst)表明 ) 2019/4/28

使用缺省路由 2019/4/28

最短路径的计算 来自图论中的算法 没有中心机构 (分布式计算) 每台交换机 必须了解到每一个目的地的路由 只可和与它直接连接的邻居进行通讯 2019/4/28

最小权路径的说明 图中边上的标记代表了节点间的距离 距离度量 图中由深色描绘的是从 4 到 5的最短路径 地理长度 经济价值 容量的倒数 2019/4/28

计算最短路径的算法 距离向量 (DV) 链路状态 这两种方法在实际应用中都有使用 交换机相互交换路由表中信息 交换机相互交换链路状态信息 2019/4/28

距离向量 相邻交换机周期的、双向交换信息 交换信息时, 交换机发送 接受方 点对列表 每一点对形如 (终点, 距离) 把列表中的信息和本地路由表中的相比较 如果存在更好的路径则改变列表中的信息 2019/4/28

距离向量算法 2019/4/28

距离向量法的直觉理解 Let 如果不存在到 V 的本地路径，或本地路径的代价高于C,就建立一条路径，其下一跳为 N，距离为 C D ：点对信息中的距离信息 C ： D ＋到发送点的距离 如果不存在到 V 的本地路径，或本地路径的代价高于C,就建立一条路径，其下一跳为 N，距离为 C 否则就ignore 2019/4/28

距离向量路径选择的举例 考虑 一条DV 信息的传递 节点 2 向 3, 5, 和 6发信 节点 6 建立到节点 2的路由，距离是 8 later, 3 发送信给 6 6 改变路径，把 3 作为它通向2 的下一个节点 2019/4/28

链路状态路径选择 克服了 DV 的不稳定性 一对交换机定期执行 交换机 测试它们之间的链路 传播链路状态信息 接受状态信息 计算新的路由 使用 Dijkstra’s 算法 2019/4/28

链路状态信息举例 假设节点 2 和3 测试它们之间的链路 传播信息 每个节点 接受信息 需要的话重新计算路由 2019/4/28

Dijkstra’s 最短路径算法 输入 输出 称为最短路径优先 (Shortest Path First ，SPF) 算法 边上标有权的图 节点, n 输出 从 n 到每个节点的最短路径 每条路径的权重 称为最短路径优先 (Shortest Path First ，SPF) 算法 2019/4/28

Dijkstra’s 算法 2019/4/28

算法的直观理解 从自身为源节点开始 向外扩散 在每一步 找到满足如下条件的节点 u 计算 没考虑过的 最靠近源节点 从 u 到每个相邻节点 v 的距离 如果距离较短, 则使从 u 开始的路径经过 v 2019/4/28

Dijkstra’s 算法的计算结果 举例： 从节点 6 开始的路径 到 3, 下一节点 = 3, 权值= 2 到 2, 下一节点 = 3, 权值= 5 到 5, 下一节点 = 3, 权值= 11 到 4, 下一节点 = 7, 权值= 8 2019/4/28

早期的广域网技术 ARPANET X.25 分组报文交换，曾在历史上占有很重要的地位 在发明时以高速著称, 以现在的标准来看则很慢 早期用于商业服务 仍然在使用 在欧洲比较流行 2019/4/28

现代的广域网技术 SMDS Frame Relay ATM 电话公司提供 没有Frame Relay流行 在商业服务中使用很广泛 2019/4/28

异步传输模式 ( ATM ) 电话公司提供设计 一个技术，同时处理 可用于局域网或广域网 目标: 取代因特网的地位 音频 视频 数据 2019/4/28

ATM 特性 端对端 (在应用程序到应用程序) 面向连接的接口: 性能有保证 使用cell 交换 建立 “连接” 发送数据 关闭连接 2019/4/28

ATM cell 定长分组包 (用于最高速的电子设备传送) 选择的长度是介于音频 (小) 和数据(大)之间的 头占5 个字节 负载占48个字节 注意: 这长度并不是对所有的应用都是最佳的 2019/4/28

ATM cell header 2019/4/28

ATM 交换机 ATM 网络的构件 由于连接 计算机 其他 ATM 交换机 接收和转发ATM cell 2019/4/28

cell的转发 由硬件直接执行 输入单元被送到一个输出接口 使用cell中的标记 动机: 高速 2019/4/28

标记转换 ATM连接用24位二进制定义 每台交换机上都重写VPI / VCI 著名的有虚拟路径标识 / 虚拟通道标识 (VPI / VCI) 一般统称为标记（label） 每台交换机上都重写VPI / VCI 2019/4/28

VPI/VCI重写举例 2019/4/28

ATM的服务质量 细粒度 (按连接) 连接建立后即定 由终结端指定 数据传输类型 吞吐量要求 分组报文分段的最大长度 能容许的最大时延 2019/4/28

数据传输类型 不变位速率 (CBR) 可变位速率 (VBR) 有效位速率 (ABR) 未定位速率 (UBR) 例如: 音频 可变位速率 (VBR) 例如: 自适应编码的视频 有效位速率 (ABR) 例如: 数据 未定位速率 (UBR) 各类都有详细的参数 (例如, 平均数, 最大数, 失败持续时间) 2019/4/28

在 ATM中传输数据 使用ATM 适应层 (AAL5) 接收和传递大量、可变长数据包 AAL5 分成小的cell来完成传递 叫做分段和重组 2019/4/28

ATM的评价 不尽人意 对局域网来说交换机太昂贵了 QoS 无法实现 2019/4/28

总结 广域网 (WANs) 广域网地址 跨越很长距离 连接很多计算机 在包交换机基础上确立 使用存储和转发机制 地址分成两部分 交换机/计算机 2019/4/28

总结(续) 路径选择 路由表的建立 路径选择的两种基本算法 每台交换机都包含有路由表 路由表给出通往终点的下一个节点 人工 自动 距离向量 链路状态 2019/4/28

总结(续) 广域网技术举例 ARPANET X.25 SMDS Frame Relay ATM 2019/4/28 Westmont College CS 140 总结(续) 广域网技术举例 ARPANET X.25 SMDS Frame Relay ATM 2019/4/28 Chapters 13-14