上海交通大学_计算机网络_翁惠玉_课件_5讲述.ppt

计算机网络讲义 第5章 网络层 网络层主要解决的问题 路由选择 网络互连 拥塞控制 为上层提供服务 第5章 网络层 网络层设计的相关问题 路由算法 拥塞控制 服务质量 网络互联 因特网中的网络层 网络层的设计 存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较 存储转发的数据包交换 数据包 Packet 存储转发 Store and Forward 路由器 Router 交换 Switching 通信子网 Communication Subnet 资源子网 Resource Subnet 网络层协议环境 网络层的设计 存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较 为传输层提供的服务 服务应与路由器技术无关 路由器的数量、类型和拓扑结构对于传输层来说应是不可见的 传输层所能获得的网络地址应采用统一的编址方式，并允许跨越多个LAN和WAN 网络层提供的服务类型 面向无连接服务：网络是不可靠的，网络服务不应面向连接，分组的排序和流控制应不属于网络层，每个分组都单独寻径，所以必须携带完整的目的地址 如Internet 面向连接的服务：网络应该提供可靠的、面向连接的服务，否则服务质量将无从谈起，尤其对于多媒体应用 如 ATM 网络层的设计 存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较 面向无连接服务的实现（数据报子网） 路由器A按左边的路由表运行，后来发现如到E和F应该走B才更好，于是更新路由表 网络层的设计 存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较 面向连接服务的实现（虚电路子网） H1和H2已建立了1#连接 H3要和H2建立连接只能是2# 网络层的设计 存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较 虚电路子网和数据报子网的比较 虚电路子网/数据报子网的比较(续) 虚电路子网 通过路径选择后建立连接 分组按序传输 服务质量能得到保证 通信后撤销连接 适合于实时传输 数据报子网 每个分组分别选择最佳路径，健壮性较好 整个网络系统的信道利用率高，成本低 差错控制和排序工作由协议高层（主机）完成 适合于非实时传输 第5章 网络层 网络层设计的相关问题 路由算法 拥塞控制 服务质量 网络互联 因特网中的网络层 路由算法 路由算法是网络层软件的一个重要部分，它决定进入的分组应从哪一根输出线传输 如果是数据报子网，将在每一个分组到达时作此决定 如果是虚电路子网，是在虚电路建立时决定，该连接上所有分组都将沿此线路传输 路由与转发：路由是寻径，转发是当一个分组到达时发生的动作 路由算法（续） 路由算法设计必须考虑的问题 正确性 简单性 健壮性 稳定性 公平性 最优性 路由算法中的度量标准 路径长度 hop数 延迟时间 路由算法的分类 静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由 静态算法（static routing） 最短路径算法（Dijkstra） 扩散法（flooding） 最短路由选择（Dijkstra） Dijkstra算法（1959）：通过用边的权值作为距离的度量来计算最短路径，有最少边数的路径不一定是最短路径 采用的数据结构 集合S：尚未找到最短路径的节点 的集合 数组R：R[i]为从指定源点去节点i 的路径上，节点i的前一个 节点 数组D：D[i]为从指定源点到节点i 的最短距离 算法的初始化 初始化集合S为除源节点外的所有节点 初始化数组D：如果从源节点到节点v的边存在，则D(v)为该边的权值，否则为无穷大 初始化数组R：如果从源节点到节点v的边存在，则R(v)为源节点，否则为0 算法 WHILE（集合S非空） { 从S中选一节点u，使D[u]最小； 如果（D[u]为无穷大） {错误！无路径存在，退出} 把u从S中删去； 对(u,v)是边的每个节点v { 如果（v仍在S中） C=D[u]+weight(u,v); 如果 （CD[v]） /*v找到了一条更短的路径*/ {R[v]= u; /*替换v的最短路径及长度*/ D[v]=C; } } } 从5出发到各个节点的最短路径 静态算法（static routing） 最短路径算法（Dijkstra） 扩散法（flooding） 扩散法（flooding） 不计算路径，有路就走 扩散法（续） 解决