6.计算机网络 网络层(1)

计算机网络第6章网络层16.1网络层概述通信子网最上面的一层完成任意端-端系统之间的数据透明传送点-点通信与端-端通信网络层连接从源端到目的端包含若干中间系统数据链路层仅将数据帧从物理线路一端到另一端主要解决如何使分组跨越通信子网从源站点发送到目的站点的问题2OSI参考模型应用层表示层会话层传输层网络层数据链路层物理层传输介质传输介质传输介质主机CCP网络层数据链路层物理层应用层表示层会话层传输层网络层数据链路层物理层主机CCP网络层数据链路层物理层3实际的网络结构4网络层的主要功能路由选择拥塞控制网络互联为传输层提供服务5网络层向上提供的服务面向无连接的服务认为通信子网总是不可靠的没有排序和流量控制功能每个包带有目的地址面向连接的服务认为子网提供可靠的服务交换数据前必须建立网络层的连接连接建立时双方可协商服务参数、质量等具有排序和流量控制功能6面向无连接的服务7数据报交换主机可随时发送数据报源端主机不知道网络是否有能力传送包以及目的端主机是否正常每个包被独立地处理，有可能路由到失效的链路和节点。路由表必须要更新每个包必须携带完整的目的地地址，包的开销高于面向连接的模式。8面向连接的服务9面向连接的服务10虚电路交换在发送第一个数据包之前要进行连接的建立，一般等待时间为RTT。连接请求包含完整的目的地址，但每个数据包只携带很小的VC标识，因此每个包的开销较小如果连接上的链路或交换机故障，连接将被中断，必须建立一个新的连接。连接建立为预留资源提供了支持。11121314156.2路由算法路由选择6.2路由算法路由选择算法给定一组路由器及连接路由器的链路，找出一条从源到目标的“好”路径。谁确定路由表？who用什么信息确定路由表项?what何时修改路由表项？when何地存放路由信息？where如何控制路由表大小？how为什么路由表能确定一条路径？why16路由选择算法非自适应算法静态路由不根据实测或估计的网络的当前通信量和拓扑结构来作路由选择自适应算法动态路由根据拓扑结构、通信量的变化来改变其路由选择。自适应路由的前提节点间交换网络状态信息17路由选择算法的特性正确性(correctness)简单性(simplicity)健状性(robustness)稳定性(stability)最优性(optimality)公平性(fairness)有效性(efficiency)18路由技术元素性能标准（“好”的路径）跳计数，成本，延迟，吞吐量网络信息源大多数路由决策要求根据网络拓扑、负载和链路成本等作出决定无，局部，邻接节点，全部节点信息更新时间连续，定期，负载变化，拓扑变化19路由技术元素决策时间数据报包到达时虚电路建立时决策形式每个节点（分布）每个节点都负责为到达的包选择一条输出链路中心节点（集中）由某些指定节点（网络控制中心）负责决策原始节点（源端）路由决策由源站点而非网络作出20静态路由算法不用测量也不需利用网络信息，按某种固定规则进行路由选择（1）泛射路由选择法（2）固定路由选择法（3）随机路由选择法21（1）泛射路由选择扩散法基本思想：将入境报文输出到所有输出线路（除入境线路外）特性尝试所有可能路由至少有一个包通过最小跳路由到达所有与源节点连接的节点都被访问优点健状性，建立虚电路，广播重要信息缺点包的拷贝呈指数增长（每个节点记下已发包的标识）2223（2）固定路由选择法路由是固定的用一个中心路由目录维护路由节点只需相邻节点的信息对于数据报或虚电路网络作同样路由优点简单对具有稳定负载的可靠网络效率较高缺点缺乏灵活性2425（3）随机路由选择法在所有与之相邻的节点中为分组随机选择出一个节点。方法虽然简单，但实际路由不是最佳路由，这会增加不必要的的负担，而且分组传输延迟也不可预测，故此法应用不广。26动态路由选择算法节点的路由选择要依靠网络当前的状态信息来决定的策略，称动态路由选择策略。（1）独立路由选择节点根据自己搜集到的有关信息做出路由选择的决定，与其它节点不交换路由选择信息。（2）集中路由选择（3）分布路由选择27（2）集中路由选择集中路由选择也像固定路由选择一样，在每个节点上存储一张路由表。集中路由选择算法中的节点路由表由路由控制中心RCC(RoutingControlCenter)定时根据网络状态计算、生成并分送到各相应节点。由于RCC利用了整个网络的信息，所以得到的路由选择是完美的，同时也减轻了各节点计算路由选择的负担。28（3）分布路由选择所有节点定期地与其每个相邻节点交换路由选择信息。每个节点均形成一张路由选择表。每个节点按照该路由选择决策路由296.2.1路由算法最短路径算法（Dijkstra)距离向量路由算法（DistanceVectorRouting，DV）链路状态（LinkStateRouting，LS）30最短路径算法（Dijkstra1959）31最短路径选择测量路径长度的方法（性能指标）最小跳计数最短距离信道带宽传输延迟平均通信量子网图节点代表路由器；弧线代表两个路由器之间的一条链路Dijkstra算法找出一个节点到所有其他节点的最短路径323334距离向量算法DV算法的特点分布的(distributed)每个节点接收来自与其直接邻接节点的信息执行路由计算；将计算结果回传给直接邻接节点迭代的(iterative)计算过程循环进行，直到相邻节点没有可交换的信息为止。异步的(asynchronous)并不要求所有节点相互锁步操作。3536373839404142434445464748349505152DV算法缺点交换路径的信息量大收敛速度慢不适合大型网络53链路状态路由算法基本思想：采用延迟作为性能标准每个节点为每条链路维护一个近似的延迟值节点每10秒计算每条出境链路的平均延迟如有重大变化，则采用扩散法通知其他节点每当接收到来自其他节点的信息时，用Dijkstra算法重新计算路由表54延迟计算方法（在每个节点）盖上入境包到达时间的时间戳；并记录其离开时间；收到肯定确认时，计算该包的延迟；收到否定确认时，更新离开时间，重发；Dijkstra算法计算从一个节点（源，假设为A）到网络中所有其他节点的最小成本路径迭代的经第k次迭代后，就能找到到k个目标节点的最小成本路径。555657585960分级路由广播路由多播路由移动主机路由61