第4章数据结构课件.ppt

本章目的: 理解网络层服务依赖的原理: 选路 (路径选择) 处理扩展性 路由器工作原理 先进主题: IPv6, NAT 因特网中的实例和实现 网络层是协议栈中最复杂的层次之一，是最具挑战性的部分； 运行在每台主机、路由器中； 在发送侧将段封装进数据报； 在接收侧，向运输层交付段； 在这个层次中我们将运行在网络层的分组称之为数据报； 网络层主要涉及的对象是路由器 转发: 将分组从路由器的输入移动到适当的路由器输出 选路: 决定分组从源到目的地所采用的路由 选路算法 类比: 选路: 从A地到B地选取合适的路径; 转发: 通过单个设施（“立交桥“）走哪条路才能向目的地前进; 在TCP中发送发流向接收方需要三次握手，以类似的方式，某些网络层体系结构(如ATM、帧中继)而非因特网，要求从源到目的地沿着所选的路径彼此握手，以便网络分组在流动之前，给定的源到目的地连接之间建立其状态------两台主机和其间的路由器创建虚拟连接； 网络层和运输层的连接服务: 网络层: 在两台主机之间 运输层: 在两个进程之间 对单个数据报的服务: 确保交付 确保分组将最终到达目的地 在特定的主机到主机时延上界内交付(100ms内) 对数据报流的服务: 按序数据报交付 对流确保最小带宽 对分组间间隔变化的限制 确保发送方发送的两个相继分组之间的时间量等于在目的地接收到它们的时间量 网络层服务模型: 第4章 网络层 4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器的构成 4.4 IP: 网际协议 数据报格式 IPv4编址 NAT ICMP IPv6 4.5 选路概念 4.6 选路算法 链路状态 距离矢量 等级选路 4.7 互联网中选路 RIP OSPF BGP 4.8 广播和多播选路 网络层连接和无连接服务 回想运输层能够给我们提供的两种服务：例如UDP和TCP； 网络层同样可以提供类似于运输层的两种服务； 主机到主机——进程到进程； 网络层提供连接服务的———虚电路(VC)网络，无连接服务的——数据报网络； 两种连接服务的本质不同，网络层的连接服务除端系统之外，还包括罗路由器； 源和目的主机之间的路径（即一系列链路和路由器）； VC号，沿着该路径的每段链路一个号码； 沿着该路径的每台路由器中的转发表项（在源到目的地路径上的每台路由器为每条经过的连接维护维护状态） “源到目的地路径与电话电路行为非常相似” 性能明确 沿着源到目的地路径的网络动作 属于一条VC的分组将在它的首部携带一个VC号； 因为一条VC在每条链路上可能具有不同的VC号，所以每台中间路由器必须用一个新的VC号代替每个传输分组的VC号。 新的VC号来自中间路由器的转发表； 用于建立 在建立阶段，发送运输层与网络层联系，指定接收方地址，通过选路算法获得分组要通过的一系列链路与路由器； 沿着该路径为每条链路确定VC号； 在该路径的每个路由器的转发表中增加一项； 数据传送，如下图； 虚电路拆除，即删除路由器转发表中的VC号 主要用于ATM、帧中继 没有用于今天的因特网中 在网络层无呼叫建立 路由器：没有端到端连接的状态 无网络级“连接”的概念 分组使用目的主机地址转发 在相同源和目的对可能采用不同的路径 转发表 最长前缀匹配 因特网 在计算机间交换数据 “弹性”服务，无严格的定时要求 “智能” 端系统 (计算机) 能够适应，执行控制，差错控制 网络内部简单，“边缘”复杂 许多链路类型 不同的特点 难以提供统一服务 ATM 从电话技术演化来 人类交谈： 严格定时，可靠性要求 对确保服务的需求 “哑” 端系统 电话 网络内部复杂 第4章 网络层 4. 1 概述 4.2 虚电路和数据报网络 4.3 路由器的构成 4.4 IP: 网际协议 数据报格式 IPv4编址 NAT ICMP IPv6 4.5 选路概念 4.6 选路算法 链路状态 距离矢量 等级选路 4.7 互联网中选路 RIP OSPF BGP 4.8 广播和多播选路 路由器的两个关键功能: 运行选路算法/协议(RIP, OSPF, BGP) 从入链路到出链路转发 数据报 路由器体系结构概述 输入端口功能 分散式交换: 给定数据报目的地址, 在输入端口内存中使用转发表查找输出端口 目的: 完成输入端口处理 排队：如果数据报到达比交换结构的转发速率快 输入端口功能 查找: 在一个庞大的转发表中进行线性有哪些信誉好的足球投注网站是不可能的（例如：按位匹配） 因此将转发表表项存放在一个树形数据结构中，树中的每一级可以认为是与目的地址的1比特相对应，若要查找，从树的根节点开始。 一旦通过查找确定了一个分组的输出端口，则该分组可转发进交换结构； 然而，一个分组可能会在进入交换结构时暂时阻塞（blocked），这是由于其他输入端口在占用交换结构。 交换结构 经