计算机网络(上交教授) Chap5

第5章 网络层,网络层主要解决的问题 路由选择 网络互连 拥塞控制 为上层提供服务,相当与路口的检查和服务，路口警察的任务,网络层的设计,存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,存储转发的数据包交换,数据包 Packet 存储转发 Store and Forward 路由器 Router 交换 Switching 通信子网 Communication Subnet 资源子网 Resource Subnet,网络层协议环境,Tnbm P344 Fig. 5-1 网络层协议环境,网络层的设计,存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,为传输层提供的服务,服务应与路由器技术无关 路由器的数量、类型和拓扑结构对于传输层来说应是不可见的 传输层所能获得的网络地址应采用统一的编址方式，并允许跨越多个LAN和WAN,网络层提供的服务类型,面向无连接服务：网络是不可靠的，网络服务不应面向连接，分组的排序和流控制应不属于网络层，每个分组都单独寻径，所以必须携带完整的目的地址 如Internet 面向连接的服务：网络应该提供可靠的、面向连接的服务，否则服务质量将无从谈起，尤其对于多媒体应用 如 ATM,对于网络层提供的服务有两种观点：,网络层的设计,存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,面向无连接服务的实现（数据报子网）,路由器A按左边的路由表运行，后来发现如到E和F应该走B才更好，于是更新路由表,A的路由表,E的路由表,C的路由表,Tnbm P346 Fig. 5-2 数据报子网中分组的寻径,用扩算法实现传输,网络层的设计,存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,面向连接服务的实现（虚电路子网）,H1和H2已建立了1#连接 H3要和H2建立连接只能是2#,A的路由表,Tnbm P348 Fig. 5-3 虚电路子网中分组的寻径,C的路由表,E的路由表,网络层的设计,存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,虚电路子网和数据报子网的比较,Tnbm P349 Fig. 5-4虚电路子网和数据报子网的比较,虚电路子网/数据报子网的比较(续),虚电路子网 通过路径选择后建立连接 分组按序传输 服务质量能得到保证 通信后撤销连接 适合于实时传输 数据报子网 每个分组分别选择最佳路径，健壮性较好 整个网络系统的信道利用率高，成本低 差错控制和排序工作由协议高层（主机）完成 适合于非实时传输,第5章 网络层,网络层设计的相关问题 路由算法 拥塞控制 服务质量 网络互联 因特网中的网络层,路由算法,路由算法是网络层软件的一个重要部分，它决定进入的分组应从哪一根输出线传输 如果是数据报子网，将在每一个分组到达时作此决定 如果是虚电路子网，是在虚电路建立时决定，该连接上所有分组都将沿此线路传输 路由与转发：路由是寻径，转发是当一个分组到达时发生的动作,路由算法（续）,路由算法设计必须考虑的问题 正确性 简单性 健壮性 稳定性 公平性 最优性 路由算法中的度量标准 路径长度 hop数(跳数少的） 延迟时间,路由算法的分类,静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由,静态算法（static routing）,最短路径算法（Dijkstra） 扩散法（flooding）,为路由器配置一张最优的路由表,最短路由选择（Dijkstra）,Dijkstra算法（1959）：通过用边的权值作为距离的度量来计算最短路径，有最少边数的路径不一定是最短路径,如下图： 5和4之间边数最少的路径是5234但最短路径是523674,采用的数据结构,集合S：尚未找到最短路径的节点 的集合 数组R：Ri为从指定源点去节点i 的路径上，节点i的前一个 节点 数组D：Di为从指定源点到节点i 的最短距离,算法的初始化,初始化集合S为除源节点外的所有节点 初始化数组D：如果从源节点到节点v的边存在，则D(v)为该边的权值，否则为无穷大 初始化数组R：如果从源节点到节点v的边存在，则R(v)为源节点，否则为0,算法,WHILE（集合S非空） 从S中选一节点u，使Du最小； 如果（Du为无穷大） 错误！无路径存在，退出 把u从S中删去； 对(u,v)是边的每个节点v 如果（v仍在S中） C=Du+weight(u,v); 如果 （CDv） /*v找到了一条更短的路径*/ Rv= u; /*替换v的最短路径及长度*/ Dv=C; ,从5出发到各个节点的最短路径,静态算法（static routing）,最短路径算法（Dijkstra） 扩散法（flooding）,为路由器配置一张最优的路由表,扩散法（flooding）,不计算路径，有路就走,如从5出发到4： 数据包从51,2；23,6；36,4；63,7；74,要解决的问题：数据包重复到达某一节点，如3，6,扩散法（续）,解决方法 在数据包头设一计数器初值，每经过一个节点自动减1，计数值为0 时，丢弃该数据包 在每个节点上建立登记表，则数据包再次经过时丢弃,缺点：重复数据包多，浪费带宽 优点：可靠性高，路径最短，常用于军事,路由算法的分类,静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由,自适应算法是动态的、分布式的算法 实现分布式算法的三要素： The measurement process（测量） The update protocol（更新协议） The calculation（计算）,自适应算法（adaptive algorithm）,自适应算法（adaptive algorithm）,距离矢量算法（D-V） 链路状态算法（L-S）,路由器动态建立和维护一张最优的路由表,D-V算法的工作原理,每个路由器用两个向量Di和Si来表示该点到网上所有节点的路径距离及其下一个节点 相邻路由器之间交换路径信息 各节点根据路径信息更新路由表,其中：,n 网络中的节点数 Di节点i的时延向量 dij节点i到j的最小时延的当前估计值 Si节点i的后继节点向量 sij从节点i到j的最小时延路径上的下一节点,路由表的更新,dij = min(dix + dxj) ( x A ) （从i到j的时延取途经每个节点时的时延的最小值） Sij = x（从i到j途经的下一个节点为x）,其中：,A 与i相邻的所有节点的集合 diji到j 的最短距离 dixi到x的最短距离 dxjx到j 的最短距离,注意：AI为21；IA为24 因为：往和返的信道流量不一定相同，节点A和I也并非在同一时刻测得，且线路状态是动态变化的,所谓节点即路由器当前节点为J,Tnbm P358 Fig. 5-9 D-V算法的路由表更新,D-V算法的缺点,交换的路径信息量大 路径信息不一致 收敛速度慢（坏消息） 不适合大型网络,无穷计算问题,好消息传播得快，坏消息传播得慢,A下网了,Tnbm P359 Fig. 5-10 无穷计算问题,克服收敛速度慢的方法,水平分裂 同距离矢量法，只是到X的距离并不是真正的距离，对下方点通知真正的距离，对上方点，给出无穷大 如上图中的C点，它向D通知到A的是真正距离，而向B通知到A的距离是无穷大 Holddown 当发现不通时，不重新选路径，而是把它设成无穷大 这些方法尚在研究之中,自适应算法（adaptive algorithm）,距离矢量算法（D-V） 链路状态算法（L-S）,路由器动态建立和维护一张最优的路由表,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,发现邻接节点,当一个路由器启动后，向每个点到点线路发送HELLO分组（携带自己的网络地址），另一端的路由器发送回来一个应答来说明它是谁，即通报其网络地址,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,测量线路开销,发送一个ECHO分组要求对方立即响应，通过测量一个来回时间再除以2，发送方就可以得到一个延迟估计值，想要更精确些，可以重复这一过程，取其平均值,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,构造分组,子网及其节点到其邻节点（路由器）的线路开销测量值（即延时，假设以ms计）,子网的链路、状态及分组情况：,节点A仅与节点B和E相邻 A B的时延为4ms A E的时延为5ms,Tnbm P363 Fig. 5-13 L-S算法的路由表更新,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,发布链路状态分组,用扩散法（向邻接的节点）发布链路状态分组 （以B为例，B的邻接点有A、C、F）,源节点E的链路状态分组经A和F到节点B，节点B必须再将E的状态分组转送到C，并向A和F发ACK,发送标志,ACK标志,Tnbm P365 Fig. 5-14 链路状态分组的转发和确认,存在的问题,状态分组的重复到达 如果序号循环使用，就会发生重复 如果一个路由器被重起，序号将从0开始重新计数，但这些分组会被当成过时分组 如果序号发生错误（如序号用32位表示，4被看成65540，第16位的0被误传成了1），则很多分组将被看成过时分组（此时565539均为过时分组，因为当前的分组序号是65540）,解决办法,使用一个32位序号，即使每秒钟发送一个分组，137年才会循环一次 在每个分组中加一年龄字段（如初值为60），每秒钟将年龄减1，为0后该分组将被丢弃 ，否则不会被认为是过时分组,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,计算新路由,用Dijkstra算法计算到每个节点的路由 得到该节点到每个节点的最短路径,L-S路由算法的优缺点,LSR的优点 路由信息的一致性好，坏消息也一样传播得快 状态分组的长度较短，仅包含到邻接点的距离、序号和年龄等，与网络规模关系不大，传输所耗用的网络带宽不大，此外，状态分组的扩散，由于年龄参数的设定，不会无限制扩散，所以可适用于大型网络 LSR的缺点 每个路由器需要有较大的存储空间，用以存储所收到的每一个节点的链路状态分组 计算工作量大，每次都必须计算最短路径,路由算法的分类,静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由,拓扑相关的路由算法,分层路由