清华大学计算机网络net1

计算机网络原理——网络层网络层主要内容网络层概述网络层的地位网络层需要解决的问题数据报和虚电路网络层提供的服务路由算法最优化原则最短路径路由算法洪泛算法基于流量的路由算法距离向量路由算法链路状态路由算法分级路由拥塞控制算法拥塞控制的基本原理开环控制拥塞预防策略通信量整形(漏桶和令牌桶)流说明闭环控制虚电路网络中的拥塞控制抑制分组负载丢弃网络互联技术级联虚电路无连接网络互联隧道技术互联网路由分段防火墙Internet网络层协议支撑协议IP/ICMP协议ARP/RARP协议内部网关路由协议RIP，OSPF外部网关路由协议BGP计算机网络原理——网络层计算机网络原理——网络层网络层的位置当今流行的通信技术传统的电信网络：线路交换、x.25、帧中继、ATM。计算机网络：ARPANET、INTERNET等。有线电视网络。计算机网络中的网络层至关重要网络层是通信子网的最高层，关系着整个网络的运行控制。网络层需要解决的问题是确定分组从源地址到目的地址是如何路由的。网络层利用数据链路层提供的服务，为传输层提供服务。网络层处理端到端传输的最低层。在广播网络中，路由选择很简单，所以网络层也很薄，甚至不存在。而在大型网络中，分组不得不跨越若干个网络到达目的地址，这其中的种种问题就需要由网络层来解决。计算机网络原理——网络层网络层需要解决的问题网络层为了能够了解通信子网的拓扑结构，以便选择路由，需要解决以下问题：屏蔽各种不同类型网络之间的差异需要统一数据格式需要统一网络地址实现全网的数据传输建立跨越网络的虚电路网络之间实现分组的寻址和转发网络层的两种实现方式虚电路(virtualcircuit)：提供面向连接的服务。类似于电话，先建立连接，之后依次发送分组，最后关闭连接。避免对每个分组进行路由。数据报(datagram)：提供无连接的服务。类似于发送信件。对每个数据报(对于无连接中的独立分组称作数据报)分别进行路由。计算机网络原理——网络层通信交换技术计算机网络总是由资源子网和通信子网组成。通信交换技术是指数据信息如何在通信子网的各个结点之间进行传输的。通常存在三种交换技术：线路交换、报文交换和分组交换。还存在某几个技术的融合，即混合交换。线路交换(circuitswitching)在网络中利用可切换的物理通信线路直接连接通信双方。最常见的例子是电话系统。线路交换包括三种状态：线路建立、数据传送、线路拆除。线路交换方式中通道是专用的，利用效率低，并存在延迟。报文交换(messageswitching)是指信息以报文(逻辑上完整的信息段)为单位进行存储转发。计算机网络原理——网络层HHHAR5R2R3Router1R4HBMMMMM存储转发(StoreandForward)发送报文的主机在发送之前，要将报文的目的地址附加在报文前面。然后将报文发送到网络中的结点中。每个网络中的结点将完整地接收报文，暂存报文，然后将报文发送到下一个更接近目的主机的结点中。如此操作，直至将报文发送到目的主机为止。计算机网络原理——网络层分组交换(packetswitching)分组交换结合报文交换和线路交换的优点，采用存储转发机制，但是规定了传输数据的单位长度。过长的报文被分成较小的单位(分组packet)，依次发送。如何管理这些分组的正确传输：数据报和虚电路。数据报(datagram)：每个分组被单独处理。每个分组带有自己的目的地址和序号被发出，由通信子网中的结点进行路由选择。在所有分组到达了目的主机后，再将各个分组按照序号编排起来。虚电路(virtualcircuit)：在发送任何分组之前，首先在发送主机和目的主机之间建立一条逻辑连接，即在通信子网中确定一条用于本次传输数据用的结点序列。建立虚电路后，所有的分组都将按照循序依次被发送到目的主机。当所有的分组都发送之后，虚电路将被拆除。在虚电路方法中，每个分组无须进行路径选择。每个主机可以和另一个主机建立若干个虚电路，每个主机也可以同时和若干主机个建立虚电路。计算机网络原理——网络层虚电路与数据报的比较计算机网络原理——网络层虚电路与数据报之间的权衡路由器内存空间与带宽的权衡虚电路占用路由器中的表空间每个数据报都携带完整的目的/源地址，浪费带宽连接建立时间与地址查找时间的权衡虚电路需要在建立连接时花费时间数据报则在每次路由时过程复杂服务质量和健壮性的权衡虚电路方式很容易保证服务质量QoS(QualityofService)，适用于实时操作，但比较脆弱。通信线路的故障，对于虚电路而言有时是致命的。数据报不太容易保证服务质量，但是对于通信线路的故障，却很容易得到补偿。计算机网络原理——网络层MHHHAR5R2R1R3R4HBM1M3M2M1M2M3M1M2M3举例请判断是虚电路还是数据报？计算机网络原理——网络层网络层提供的服务网络层为传输层提供的服务面向连接服务：将复杂的功能放在网络层(通信子网)。建立连接传输数据拆除连接无连接服务：将复杂的功能放在传输层。只负责传输分组。通信子网提供的服务(面向连接或无连接)与通信子网结构(虚电路或数据报)无关。面向连接的服务用虚电路来实现(比较合理)面向连接的服务用数据报来实现面向无连接的服务用虚电路来实现面向无连接的服务用数据报来实现(比较合理)计算机网络原理——网络层通信子网结构及其提供的服务计算机网络原理——网络层小结—网络层概述网络层的地位确定分组从源地址到目的地址如何进行路由。网络层需要解决的问题屏蔽各种不同类型网络之间的差异实现全网的数据传输网络层的两种实现方式——数据报和虚电路都属于分组交换，采用存贮转发机制。数据报(datagram)：每个分组被单独处理，每个分组带有自己的目的地址和序号被发出。虚电路(virtualcircuit)：先在发送主机和目的主机之间建立一条逻辑连接，所有的分组按照循序依次被发送。最后虚电路将被拆除。在虚电路方法中，每个分组无须进行路径选择。网络层提供的服务面向连接的服务和无连接的服务。计算机网络原理——网络层计算机网络原理——网络层路由算法路由算法是网络层软件的一部分子网采用数据报方式，每个分组都要做路由选择。子网采用虚电路方式，只需在建立连接时做一次路由选择。路由算法应具有的特性正确性(correctness)、简单性(simplicity)、健壮性(robustness)、稳定性(stability)、公平性(fairness)、最优性(optimality)路由算法分类非自适应算法(静态路由算法)：按照预先计算好的(off-line)信息进行路由。自适应算法(动态路由算法)：根据网络拓扑结构，通信量等地变化来改变路由。计算机网络原理——网络层最优化原则最优化原则(optimalityprinciple)如果路由器J在路由器I到K的最优路由上，那么从J到K的最优路由会落在同一路由上。汇集树(sinktree)路由算法的目的是找出并使用汇集树。从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树。计算机网络原理——网络层几种常见的路由算法静态路由算法最短路径选择(ShortestPathRouting)洪泛算法(FloodingRouting)基于流量的路由算法(Flow-BasedRouting)动态路由算法距离向量路由算法(DistanceVectorRouting)链路状态路由算法(LinkStateRouting)分级路由(HierarchicalRouting)计算机网络原理——网络层最短路径路由算法基本思想构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。目的是构建两个路由器间的路由，算法是在子网拓扑图中找出最短路径。得到最短路径，有不同的测量路径长度的方法：计算结点数量计算地理距离计算传输延迟计算距离、信道带宽等参数的加权函数……Dijkstra算法是其中的一种计算最短路径的算法。计算机网络原理——网络层Dijkstra算法每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注。开始时，所有结点都为临时性标注，标注为无穷大。源结点标注为0，且为永久性标注，令其为工作结点。检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点。在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点。重复第三、四步，直到目的结点成为工作结点。Dijkstra算法的图例。Dijkstra算法的程序：与算法的区别是从目的结点开始。计算机网络原理——网络层Dijkstra算法图例计算机网络原理——网络层Dijkstra算法程序计算机网络原理——网络层洪泛算法基本思想把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。主要问题洪泛要产生大量重复分组。解决措施每个报头包含站点计数器，每经过一站计数器减1，为0时则丢弃该分组。记录下分组扩展的路径，防止它第二次扩散到已经扩散过的路径中。较实用的方法——选择性洪泛算法(selectiveflooding)洪泛法的一种改进：将进来的每个分组仅发送到与正确方向接近的线路上。计算机网络原理——网络层洪泛算法应用情况洪泛算法由于过于浪费路由器和线路的资源，在实际应用中很难被直接采用，但还是有一些用处的。在军事领域中，由于需要极好的健壮性，扩散法可以一展身手。在分布式数据库中，有时需要并行地更新所有数据库，这时洪泛算法也是最佳方案。因为洪泛算法总是能够选择最短的路径，可以产生一个最短的延迟。洪泛算法可以作为一种尺度衡量标准来评价其它路由算法。计算机网络原理——网络层基于流量的路由算法基本思想既考虑拓扑结构，又兼顾网络负荷。前提：每对结点间平均数据流是相对稳定和可预测的。根据网络带宽和平均流量，可得出平均分组延迟，因此路由算法就演变为寻找网络中连接两个路由器的线路上具有最小平均分组延迟的问题。需要预知的信息网络拓扑结构。通信量矩阵Fij，即线路ij之间的平均通信量。线路带宽矩阵Cij，即线路ij之间允许的最大通信量。临时的路由算法。图例。计算机网络原理——网络层基于流量的路由算法图例计算机网络原理——网络层根据队列原理，线路平均分组延迟的计算公式为：T=1/(C-)1/=800bit基于流量的路由算法图例计算机网络原理——网络层距离向量路由算法属于动态路由算法，最初用于ARPANET,DECnet等网络。基本思想：每个路由器维护一张表，表中列出了到每个目的地址的最佳距离和线路，并通过与邻居结点交换信息来更新表。表(路由表)的构成：以子网中其它路由器为表的索引，到达目的结点的最佳输出线路，和到达目的结点所需时间或距离。路由器需要知晓自己到邻居结点的“距离”。所用的度量标准可以为站点、估计的时间延迟等。如果为站点，本路由器到每个邻居结点的距离都为1。如果是延迟，本路由器就发送一个要对方立即响应的ECHO分组，用来回时间除以2即得到延迟时间，每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表。邻居结点X发来的表中，X到路由器i的距离为Xi。本路由器到X的距离为m，则本路由器经过X到i的距离为Xi+m。根据不同邻居发来的信息，计算Xi+m，取最小值，更新本路由器的表。注意：在计算中不使用本路由器中的老路由表。计算机网络原理——网络层距离向量路由算法图例路由器J计算到达路由器C的最新路由JAC=8+25=33msJIC=10+18=28msJHC=12+19=31msJ