计算机网络课件第6章网络层.ppt

1、1,第六章网络层,2,主要内容（1）,6.1 网络层概述 6.2 路由算法 6.2.1 最优化原则 6.2.2 最短路径路由算法 6.2.3 洪泛算法 6.2.4 距离向量路由算法 6.2.5 链路状态路由算法 6.2.6 分层路由 6.2.7 移动主机的路由,3,主要内容（2）,6.3 拥塞控制算法 6.3.1 拥塞控制的基本原理 6.3.2 拥塞控制算法 6.4 网络互连 6.4.1 级联虚电路 6.4.2 无连接网络互连 6.4.3 隧道技术 6.4.4 互联网路由 6.4.5 分段 6.4.6 防火墙,4,主要内容（3）,6.5 INTERNET网络层协议 6.6.1 IP协议 6.6

2、.2 Internet控制协议 6.6.3 内部网关路由协议：OSPF 6.6.4 外部网关路由协议：BGP,5,6.1 网络层概述（1）,ISO 定义 网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。 网络层是处理端到端传输的最低层。 网络层要解决的关键问题是了解通信子网的拓扑结构，选择路由。,6,6.1 网络层概述（2）,网络层设计的有关问题 为传输层提供服务 面向连接服务 传统电信的观点：通信子网应该提供可靠的、面向连接的服务。 无连接服务 Internet的观点：通信子网无论怎么设计都是不可靠的，因此网络层只需提供无

3、连接服务。 IP/ATM,7,8,6.1 网络层概述（3）,网络层的内部组织 虚电路（virtual circuit） 数据报（datagram） 虚电路子网与数据报子网的比较 路由器内存空间与带宽的权衡 虚电路方式，路由器需要维护虚电路的状态信息； 数据报方式，每个数据报都携带完整的目的/源地址，浪费带宽,9,6.1 网络层概述（4）,连接建立时间与地址查找时间的权衡 虚电路需要在建立连接时花费时间 数据报则在每次路由时过程复杂 服务质量与可靠性的权衡 虚电路方式很容易保证服务质量QoS(Quality of Service)，适用于实时操作，但比较脆弱。 数据报不太容易保证服务质量，但是对

4、于通信线路的故障，适应性很强。,10,6.1 网络层概述（5）,网络层为传输层提供的服务 面向连接服务：将复杂的功能放在网络层(通信子网)。 无连接服务：将复杂的功能放在传输层。 通信子网提供的服务（面向连接或无连接）与通信子网结构（虚电路或数据报）没有必然联系。 服务与子网结构的不同组合的例子,11,网络层设计要点,存储转发分组交换 向传输层提供的服务 无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,12,存储转发分组交换,存储转发是计算机网络的基本功能； 当网络出现拥塞时，将需要发送的分组存储起来，一旦网络出现空闲再发送出去。,13,向传输层提供的服务,在网络层/传输层

5、的接口面上，网络层向传输层提供服务。 在设计网络层服务时，需要考虑下列目标： （1）所提供的服务应该独立于路由器技术； （2）路由器的数量、类型和拓扑关系对于传输层来说应该是不可见的； （3）传输层可以使用的网络地址应该有一种统一的编址方案，甚至可以跨越多个LAN和WAN。 问题的焦点：网络层应该给传输层提供的服务有两种: （1）面向连接的服务； （2）面向无连接的服务。,14,无连接服务的实现,所谓无连接的服务：即在发送过程中，所有的分组都被独立地传送到子网中，不需要事先建立连接；这样的分组通常称为数据报（datagram）；这样的子网称为数据报子网（datagram subnet）。,将分

6、组数据分成4个部分，通过网络从H1发送到H2,每个路由器都有一个路由表，每个分组根据相关的路由表选择路径从源主机达到目的主机。,15,面向连接服务的实现,所谓面向连接是指：在发送数据分组之前，必须首先建立起一条从源路由器到目标路由器之间的路径。这个连接称为一个VC（Virtual Circuit，虚电路），这个子网称为虚电路子网（ Virtual Circuit subnet）。,在数据发送之前，首先建立连接，这个连接产生了一条虚电路。以后的数据分组都沿着这条虚电路发送。虚电路对网络线路是敏感的，即若线路发生故障会影响数据分组的传输。,16,虚电路子网和数据报子网的比较,17,18,小结（1）

7、,网络层的地位 位于数据链路层和传输层之间，使用数据链路层提供的服务，为传输层提供服务； 通信子网的最高层； 处理端到端传输的最低层。 网络层的作用 屏蔽各种不同类型网络之间的差异，实现互连 了解通信子网的拓扑结构，选择路由，实现报文的网络传输,19,小结（2）,网络层的两种实现方式 ： 数据报和虚电路 都属于分组交换，采用存储转发机制。 数据报(datagram)：每个分组被单独路由，分组带有全网唯一的地址 虚电路(virtual circuit)：先在源端和目的端之间建立一条虚电路，所有分组沿虚电路按次序存储转发，最后拆除虚电路。在虚电路中，每个分组无须进行路径选择。 网络层提供的服务 面

8、向连接的服务和无连接的服务。,20,6.2 路由算法（1）,路由算法：是网络层软件的一部分，它负责确定一个进来的分组应该被传送到哪一条输出线路上。 如果子网内部使用了数据报，那么路由器必须针对每一个到达的数据分组重新选择路径，因为从上一次选择路径之后，最佳的路径可能已经改变了。 如果子网内部使用了虚电路，那么只有当一个新的虚电路被建立起来的时候，才需要确定路由路径。 路由算法可以分成两大类： （1）非自适应的 （2）自适应的,这个算法不会根据当前测量或者估计的流量和拓扑结构来调整它们的路由决策，相反路由选择是预先在离线情况下计算好的，在网络启动的时候被下载到路由器中。这个过程有时也被称为静态路

9、由。,这个算法会根据当前测量或者估计的流量和拓扑结构来调整它们的路由决策。,21,（1） 路由选择时机： 网络路由选择算法是网络层软件的重要组成部分。 路由选择的频度取决于选择的时机。,面向连接VC服务：路由选择的频度低，既每次在呼叫建立连接时，需选择一次路径，后续的数据分组均沿已建立的VC路径传送（会话路径选择）； 无连接的DG服务：路由选择的频度高。,22,（2） 路由选择算法： 要求： 正确性 简单化 健壮性（Robustness） 稳定性 公平性（Fairness） 最优化,23,指网络中节点根据通信子网的运行状况（可用的数据链路、各条链路中的信息流量），按照一定的策略选择一可用的传送

10、路径，将信息发往目的地DTE。,A,B,C,D,E,F,G,H,路由选择（或路径控制）,24,6.2.1优化原则,最优化原则：如果路由器J是在从路由器I到路由器K的最优路径上，那么，从J到K的最优路径也必定沿着同样的路由路径。 最优化原则的一个直接结果是，从所有的源到一个指定目标的最优路径的集合构成了一棵以目标节点为根的树。这样的树称为汇集树。,(a)一个子网,(b)路由器B的汇集树,图中的距离度量是跳数；由于汇集树是一个树，它不包含任何环，所以每个分组将在有限跳数之内被递交给目标主机。,25,6.2.2 最短路径路由算法,属于静态路由算法 基本思想 构建子网的拓扑图，图中的每个结点代表一个路

11、由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。 测量路径长度的方法 结点数量 地理距离 传输延迟 距离、信道带宽等参数的加权函数,26,最短路径路由,采用跳数的方法来进行度量最短路径； 见下图，我们希望找到从A到D的最短路径。,开始，将A标记为永久的,选择B为最短路径,从B选择E为最短路径,修改其它节点的路径,从E选择F为最短路径,从F选择H为最短路径,从A到D的最短路径为ABEFHD,27,Dijkstra算法(1),Dijkstra算法 根据网络拓扑，了解所有节点的链路代价 通过链路状态广播知道网络情况 每个节点都有相同的信息 从源节点到所有其它节点计算

12、最短路径 对这些节点给出路由表 反复查询: 通过k参数叠代，使得K到目标地址的最短路径,28,注意: c(i,j): 从i到j的代价，如果没有直接连接，则代价为无穷大 D(v): 从源到目标地址V的现行代价 p(v): 从源到V的前一个节点 N: 所知道的所有最短路径的集,Dijkstra算法(2),29,Dijkstra算法: 实例,步骤 0 1 2 3 4 5,开始 节点 A AD ADE ADEB ADEBC ADEBCF,D(B),p(B) 2 , A 2, A 2, A,D(C),p(C) 5, A 4, D 3, E 3, E,D(D),p(D) 1, A,D(E),p(E) 无穷

13、大 2, D,D(F),p(F) 无穷大 无穷大 4, E 4, E 4, E,30,Dijsktras Algorithm,1 Initialization: 2 N = A 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infty 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) =

14、 min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N,31,6.2.3 扩散法（Flooding）（1）,属于静态路由算法 基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。 主要问题 扩散要产生大量重复包。 解决措施 每个包头包含站点计数器，每经过一站计数器减1，为0时则丢弃该包； 记录包经过的路径,32,扩散法图例

15、,时延小 分组数量多，易阻塞,全路（扩散式）: 洪泛法（Flooding）,33,6.2.3 扩散法（Flooding）（2）,选择性扩散法（selective flooding） 扩散法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。 应用情况 对路由器和线路的资源过于浪费，实际很少直接采用； 具有极好的健壮性，可用于军事应用； 作为衡量标准评价其它路由算法。,34,6.2.4 距离向量路由算法（1）,距离向量路由算法（Distance Vector Routing） 属于动态路由算法,也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，

16、被RIP协议采用。 基本思想 每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表； 以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离；,35,6.2.4 距离向量路由算法（2）,每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表； 邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X的距离为m，则路由器经过X到i的距离为Xi + m。根据不同邻居发来的信息，计算Xi + m，并取最小值，更新本路由器的路由表；,36,距离表数据结构

17、,例如：对于节点X, 目标节点Y，节点X到Y的距离是通过邻节点Z来计算的,37,距离表: 例子,loop!,loop!,38,距离表给出路由表,A B C D,A,1 D,5 D,4 D,4,Outgoing link to use, cost,destination,Distance table,Routing table,39,图6.9实例,一个子网,图中列出了J从邻居路由器接收到的延迟矢量。例如：A到B为12，A到C为25，A到D为40等。假定J到A，I，H，K的延迟分别为8，10，12，6。 则：J到B是通过A到B，即为81220；J到C是通过I到C，即为101828；等等。 对于所有

18、其它的目标也执行同样的计算过程，最后得到新的J路由表。,40,6.2.5 链路状态路由算法（1）,链接-状态( L-S：Link-Status ) 算法，又称最短路径优先（SPF ：Shortest Path First）算法。 该算法原理：各网关主动测试所有与其相邻网关之间的状态，即网关周期性地向相邻的网关发出简短的查询报文，根据相邻网关的响应判断链接的状态（链路的通或断，主机有否激活），这就是取名L-S的原因；随后各网关周期性地广播其L-S信息；网关收到L-S报文后，可刷新互连网拓扑，若L-S发生变更，立即采用最短路径（Dijkstra）算法，刷新本地路由表。,41,每一个路由器要求完成的

19、工作,（1）发现它的邻居节点，并知道其网络地址； （2）测量到各邻居节点的延迟或者开销； （3）构造一个分组，分组中包含所有它刚刚知道的信息； （4）将这个分组发送给所有其它的路由器； （5）计算出到每一个其它路由器的最短路径。,42,每个路由器创建三个单列的表， 一个跟踪直连的相邻路由器， 一个确定整个互连网的拓扑， 一个用于路由表。 L-S路由器比任何V-D路由协议获取更多互连网信息。 L-S的IP路由协议的例子是整个链路状态OSPF。,43,发现邻居节点,当一个路由器启动的时候，它的第一个任务是找出哪些路由器是它的邻居。 实现方法：在每一条点到点线路上发送一个特殊的HELLO分组。线路另

20、一端的路由器回送一个应答说明它是谁。 这些名字必须是全局唯一的，因为当一个远程路由器以后听到有三个路由器连接到F上的时候，它必须能够确定这三个路由器所提到的F是否是同一个路由器F。,为了发现邻居节点，需要对LAN进行建模，在网络拓扑中将LAN本身看作是一个节点。,44,测量线路开销,链路状态路由算法要求每一个路由器知道它到各个邻居节点之间的延迟，或者至少有一个合理的估计值。 为了决定这份延迟信息，最直接的办法是在这条线路上发送一个特殊的ECHO分组，另一端必须回送一个应答。通过计算出往返时间，再除以2，则发送方路由器就可以得到一个合理的延迟估计值。 如果要想得到更好的结果，则可以多次执行这样的

21、测试过程，然后取它们的平均值。 但实际中还存在着负载，即两个方向上的延迟是不对称的。,如果考虑负载的话，负载会发生变化，有时CF最短，有时EI最短。很难确定最佳路径。 为了避免在选择最佳路径过程中的震荡现象，利用先验知识负载合理地分布在多条线路上。,45,创建链路状态分组,一旦所需要的交换信息已经收集到了，每个路由器的下一步工作是建立一个包含所有这些数据的分组。 分组的内容：发送方标识序列号年龄邻居列表（包含这个邻居的延迟）,一个子网,创建链路状态分组有两种：定期创建、当某一个重要事情发生的时候创建。,46,发布链路状态分组,链路状态路由算法最技巧的部分是如何可靠地发布链路状态分组。 当分组被

22、发布出去并且被安装后，首先获得分组的路由器将改变它们的路由路径。 不同的路由器有可能使用不同版本的拓扑结构，从而导致了不一致性、环、不可达的机器，或者其它的问题。 发布链路状态分组的思路： （1）使用扩散法来发布链路状态分组； （2）为了控制扩散过程，每一个分组包含一个序列号（随着每个新的分组而递增）； （3）每个路由器记录它所有（源路由器、序列号）对； （4）当一个分组进来后，路由器检查这个新的分组； （5）如果是新的，就转发该分组； （6）如果它是一个重复分组，则将它丢弃； （7）如果分组的序列号小于当前最大序列号，则它将被当作过时分组而拒绝。,47,从E发来的链路状态包有两个，一个经过E

23、AB，另一个经过EFB； 从D发链路状态包有两个，一个经过DCB，另一个经过DFB；,1:有事件发生；0：没有事件发生,48,6.2.5 链路状态路由算法（2）,链路状态算法（LS）和距离向量算法（DV）的比较 路由信息的复杂性 LS 路由信息向全网发送 N节点，E个连接的情况下，每个节点发送O(nE)的报文 DV 仅在邻居节点之间交换,49,6.2.5 链路状态路由算法（3）,收敛（Convergence）速度 LS 使用最短路径优先算法，算法复杂度为O(n*2) n个结点（不包括源结点），需要n*(n+1)/2 次比较 使用更有效的实现方法，算法复杂度可以达到O(nlogn) 可能存在路由

24、振荡（oscillations）,50,6.2.5 链路状态路由算法（4）,DV 收敛时间不定 可能会出现路由循环 count-to-infinity（无穷大）问题,51,6.2.5 链路状态路由算法（5）,健壮性: 如果路由器不能正常工作会发生什么? LS 结点会广播错误的链路开销 每个结点只计算自己的路由表 DV 结点会广播错误的路径开销 每个结点的路由表被别的结点使用，错误会传播到全网,52,6.2.6 分层路由,分层路由（Hierarchical Routing） 网络规模增长带来的问题 路由器中的路由表增大； 路由器为选择路由而占用的内存、CPU时间和网络带宽增大。 分层路由 分而治

25、之的思想； 根据需要，将路由器分成区域（regions）、聚类（clusters）、区（zones）和组（groups） Fig. 5-17，路由表由17项减为7项。 分层路由带来的问题 路由表中的路由不一定是最优路由。,53,54,6.2.7 广播路由,在网络中如果给所有的目标发送同一个分组，这样的传输称为广播（broadcasting）。 广播的方法： （1）简单地给每个目标单独发送一个分组； （2）扩散法； （3）多目标路由； （4）以发起广播的路由器为根的汇集树，或者生成树； （5）逆向路径转发,一个子网 汇集树 树,55,6.2.8 多播路由,采用一种办法能够给一些有明确定义的组发送

26、消息，这些组的成员数量虽然很多，但是与整个网络规模相比却很小，这样一个组发送消息称为多播（multicasting），它的路由算法称为多播路由。 多播传输要求对组进行管理。首先需要有一种办法来创建和销毁组，并且允许进程加入或者离开组。 多播传输关心的是，当一个进程加入组的时候，它需要把这个事实告诉它的主机。 对于路由器来说，它们的哪些主机属于哪些组非常重要。 当主机与组之间的从属关系发生变化的时候，主机必须将这些变化告诉路由器，或者由路由器定期地询问它们的主机。 无论采用哪些一种方式，路由器必须知道它们的哪些主机属于哪些组。 路由器再告诉它们的邻居，所以，主机与组的从属信息再整个子网中传播开来

27、。,一个子网,路由器生成树,组1的多播树,组2的多播树,56,6.2.9 移动主机的路由（1）,移动主机分为两类： （1）迁移主机（migratory host）：基本上是固定的，但是经常会从一个固定的站点移动到另一个固定的站点，并且只有当它们物理上连接到网络的时候才使用网络。,（2）漫游主机（roaming host）：实际上是在移动过程中执行计算，它们希望在移动的时候还能够保持与网络的连接。 以上两类统称为移动主机（mobile host）:是指那些离开了原始站点还想继续连接网络的主机。,57,6.2.9 移动主机的路由（2）,移动主机路由算法的目标： 能够做到用移动主机的主地址给它们发送

28、分组，而且不管这些主机在哪里，这些分组都能够被递交给它们。 主要的问题：怎样才能找到这些主机？,查找主机的具体步骤： （1）注册：当一台新的主机进入一个区域，不管采用什么方式入网（连到LAN、漫游进入无线网），该主机必须在外部代理那里注册自己； （2）注销：当一台主机离开网络时，也应该宣布自己的离开请求，以便让外部代理注销自己，但往往主机采用关机（大部分软件都提供在关机后几分钟后自动注销）,58,小结（1）,最优化原则 路由算法的目的是找出并使用汇集树。 静态路由算法 最短路径路由算法 扩散算法,59,小结（2）,动态路由算法 距离向量路由算法 将自己（路由结点）对全网拓扑结构的认识告诉给邻居

29、 无穷计算问题，水平分裂算法 链路状态路由算法 将自己（路由结点）对邻居的认识洪泛给全网 分层路由 移动主机的路由,60,6.3 拥塞控制算法(1),什么叫拥塞：当一个子网或者子网的一部分中出现太多分组的时候，网络的性能开始下降。这种情况称为拥塞（congestion）。,当主机传送到子网中的分组数量在子网的内容范围内的时候，所有这些分组都可以递交（除了有些受到传输错误的影响以外），被递交的分组数量与发送的分组数量成正比。,随着流量的快速递增，路由器不再能够处理所有这些分组，于是它们开始丢失分组，在流量很高的时候，性能将严重恶化，几乎没有分组能够被递交。,拥塞发生的因素很多。例如：多条输入线路

30、对同样的输出；慢速的处理器也可能引起拥塞。,61,6.3 拥塞控制算法（2）,拥塞产生的原因 多个输入对应一个输出； 慢速处理器； 低带宽线路。 解决办法 针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈； 需要全面考虑各个因素。,62,拥塞控制和流控制的区别,拥塞控制的任务是确保子网能够承载所到达的流量。这是一个全局性的问题，涉及到各方面的行为，包括所有的主机、所有的路由器、路由器内部的存储转发处理过程，以及所有可能会削弱子网承载容量的其它因素。,流控制问题：例如有一个1000Gbps的光纤网络，一台超级计算机试图以1Gbps的速率给一台个人计算机

31、传送一个文件。尽管这里并没有拥塞（网络本身没有任何问题），但是流控制却是需要的。以便强迫超级计算机经常停下来，给个人计算机以喘息的机会。,拥塞控制问题：例如有一个存储转发网络，线路为1Mbps，它有1000台大型计算机，其中一半的机器正在试图给另一半机器以100Kbps的速率传送文件。这里的问题并不是快速的发送方会淹没慢速的接收方，而是总流量超过了网络的处理能力。,流控制只与特定的发送方和特定的接收方之间的点到点流量有关。它的任务是，确保一个快速的发送方不会持续地以超过接收方能力的速率传输数据。流控制通常涉及到的做法是，接收方向发送方提供某种直接的反馈，以便告诉另一端的情形到底怎么样。,63,

32、6.3.1 虚电路子网中的拥塞控制,准入技术（admission controa）:一种广泛应用的、防止已经拥塞的子网进一步恶化的技术是准入技术。 准入技术的原理：一旦出现拥塞的信号，则不再创建虚电路，直到问题排除为止。 在网络系统中，在出现拥塞的情况下，企图建立新的传输层连接将会失败。 在电话系统中，当一台交换机超过负载的时候，它也会采用准入控制的方法，不再送出拨号音。,另一种方法是：允许建立新的虚电路，但是要谨慎地选择路由器，使所有新的虚电路都绕开有问题的区域。,省略掉拥塞的路由器和它们所有的线路。避开了拥塞的路由器。,64,6.3.2 数据报子网中的拥塞控制,由于每个数据报都需要走各自的

33、路由，因此数据报子网与虚电路子的拥塞控制方法是不太一样的。 采用每台路由器监视它的输出线路和其它资源的使用情况，采用合理的方式，就可以控制它的拥塞。 给出公式：,U新aU旧（1-a） f,U新：这条线路最新的利用率，取值在0.0和1.0之间； U旧：这条线路过去的利用率，取值在0.0和1.0之间； f ：线路瞬时利用率； a：代表路由器忘记最新的历史情况的概率。,每当U超过了特定的阈值的时候，该输出线路进入到一种“警告”状态； 路由器对每个新到来的分组都要进行检查，看它的输出线路是否处于警告状态。 如果是的话，就需要采取某种措施。,65,6.3.3 负载丢弃,当网络上任何一种方法都不能消除拥塞

34、的时候，路由器可以进行负载脱落（load shedding）。 负载脱落是指当路由器因为来不及处理分组而被淹没的时候，只要将这些分组丢弃即可。例如：,某些视频压缩算法会定期地传输一个完整的帧，然后以帧差（与完整帧之间的差异）的形式传输后续的帧。在这种情况下，丢弃帧差中的分组显然比丢弃完整帧中的分组要好的多。 考虑传输一个既包含ASCII文本又包含图片的文档。很显然，丢弃某个图象中的一行象素比丢掉一行可读的文本带来的损失要小的多。,采用早期检测可以避免拥塞的发生。 由于路由器可能无法判断哪一个源是引起拥塞的罪魁，所以，路由器采用随机地从拥塞队列中选取分组。,66,6.3.4 抖动控制,对于象音频

35、流和视频流这样的应用，只要传输时间是恒定的，那么它就不会介意到底需要20ms还是30ms才将分组递交给目标主机。 分组到达的变化量（即标准偏差）被称为抖动（jitter）。,比如：在高抖动的情况下，有的分组需要20ms到达，而其它的分组需要30ms到达，这将使得声音或者电影质量很不稳定。,高抖动的情形,低抖动的情形,通过计算出沿途每一跳的期望传输时间，就可以对抖动加以控制。 对于多个正在竞争同一条输出线路的分组，路由器可以将预定时间提前到达的分组减慢，而落后的分组逐渐加速，就可以减缓抖动的程度。,67,6.4 服务质量,前面我们讨论的是减少拥塞和提高网络性能。 然而随着多媒体网络连接的需求增长

36、，通常仅仅依靠这些特殊的手段还不够。 除此之外还需要做更多的工作，以便通过网络和协议的设计来保证服务质量。,导致网络服务质量问题出现的原因大致有两类：,（1）与网络无关的因素 业务服务器过载； 人为因素。,（2）网络的原因 网络设备原因； 接入链路的容量； 不均衡的流量分布导致的拥塞。,68,6.4.1 需求,从一个源到目标的分组流称为一个流（flow）。 在面向连接的网络中，属于同一个流的所有分组将会走同样的路由路径； 面向无连接的网络中，它们可能会走不同的路径。 每个流需求特征为：可靠性、延迟、抖动和带宽。这四个特征合起来决定了一个流所要求的服务质量（Quality of Service,

37、QoS）,69,6.4.2 获得好的服务质量所使用的技术,从网络的角度看： （1）当整个网络发生拥塞时，设法尽量增加网络资源。 （2）根据网络拓扑、流量和流向等因素合理优化网络的规划和设计，引导流量流向，尽量提高网络资源的利用率。 从业务的角度看： （1）在IP网络资源一定的情况下，在IP网络上提供有别于“尽力而为”的其他类型的业务，即提供有区别的业务。 （2）在网络有可能发生拥塞时，对服务质量比较敏感的业务设置较高的优先级，使其能够尽量优先得到服务。 但无论是采用什么样的QoS模型，这些思路都以牺牲低优先级的业务为代价，来换取高优先业务的QoS保证。,70,提供充足的资源,提供充足的资源：路

38、由器的容量、缓冲区空间、带宽，以保证分组能够顺利的通过。 充足的网络资源是解决服务质量问题的关键。在网络没有拥塞时有无QoS机制都行，因为即使是“尽力而为”的IP包也能够得到很好的服务。 这种方案的代价太昂贵。,71,缓冲能力,在接收方，数据流在被递交之前先缓存起来。将数据流缓存起来并不会影响到可靠性和带宽，但会增加延迟，然而，这样可以消除抖动。对于音频和视频点播，抖动是主要的问题，所以这项技术非常有用。,分组离开源主机,分组到达缓冲区,分组从缓冲区中移除,开始播放,出现停顿,如果将增大缓冲区空间，使得分组在起始时间再多延迟一会儿，就可以解决这个问题。 许多音频或视频播放器在开始播放之前需要先

39、缓存10秒左右的流数据。例如：Windows Media Player、RealPlayer等,72,流量整形,流量整形（traffic shaping）是指调节数据传输的平均速率（以及突发性），在服务器端对流量进行平滑处理。 当一个连接被建立起来时，用户和子网对于他们之间的电路上应该遵循什么样的流量模式（即流量的形式）达成一致的协议。有时称为服务等级协议（service level argreement）。 流量整形技术可以减少拥塞，对于实时数据的传输非常重要，比如音频和视频连接等，它们有严格的服务质量要求。,73,漏桶算法（1）,漏桶算法（The Leaky Bucket Algorith

40、m） 将用户发出的不平滑的数据包流转变成网络中平滑的数据包流； 可用于固定包长的协议，如ATM；也可用于可变包长的协议，如IP，使用字节计数； 无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活。,74,漏桶算法（2）,请想象这样一个桶，它的底部有一个小洞如图所示。不管该桶进水的速率是多少，当桶中还有水的时候，水流出去的速率是一个常数；当桶中没有水的时候，出水速率当然为0。,水龙头,水桶,水以恒定的速率从孔中流出,水快速地从水龙头流出,而且，一旦该桶满了，则再往里流的水将会沿着桶沿溢出，自然流失了（就是说，不会到达底部洞口的输出水流中)。,75,漏桶算法（3）,同样的思想也可以应用到分

41、组上，如图所示。从概念上讲，在每个主机连接到网络的接口中都包含一个漏桶，也即一个有限长度的内部队列。如果当该队列满的时候，又有一个分组到来，那么该分组将被丢弃。,这种机制既可以被内置到硬件接口中，也可以由主机的操作系统来模拟实现。此算法称为漏桶算法(leaky bucket algorithm)，最早是由Turner(1986)提出来的。手机上，这个算法非常简单，它只不过是一个常数服务时间的单服务器排队系统。,76,漏桶算法（4）,举一个漏桶的例子，假设一台计算机可以按照每秒钟25兆字节(2OOMbps)的速率产生数据，并且网络也可以运行在同样的速度上。然而，路由器只能在较短的时间间隔内(基本

42、上而言，能坚持到它们的缓冲区被填满)以这样的速率接收数据。在长时间情况下，它们的最佳工作速率不超过每秒2兆字节。,进入漏桶的输入数据,队列长度,漏桶的输出,由于数据以1兆字节大小的突发方式到来，每秒钟来一次40ms的突发数据。,77,图示说明,进入漏桶的数据以25MB/sec,持续时间500ms，相当于数据以1MB/40ms进入漏桶,漏桶下面的小孔以2MB/sec输出数据，容量为1MB,结论：这意味着即使是高达lMB的突发数据，都可以被毫无丢失地处理完。不管这些突发数据进来的速度有多快，它们都被分布到500ms的时间段上。,78,令牌桶算法（1）,漏桶算法强迫输出模式保持严格的均匀速率，而不管

43、通信流量的突发性程度如何。 对于许多应用，更好的做法是，当大量的突发数据到来的时候，应该允许输出流适当地加快，因此我们需要一个更加灵活，并且最好不会丢失数据的算法。令牌桶算法(bucket algorithm)正是这样一个算法。,桶中只能装有三个令牌,每隔 T秒往桶中装入一个令牌,在桶的外面有5个分组等待传送，要使一个分组被传送出去，它必须要抓住一个令牌，同时要销毁一个令牌,对于计算机网络传输，目前有三个分组已经被传输出去，还有两个分组等待传输。,79,令牌桶算法（2）,令牌桶算法的实现方法：基本令牌桶算法的实现非常简单，它只不过是一个记录令牌个数的变量。每隔T秒，该计数器增一；当一个分组被发

44、送出去的时候，该计数器减一。当计数器减到0的时候，就不能够再发送分组。在按字节计数的变种算法中，每隔T秒，计数器增加k；当发送分组的时候，减去每一个发送的分组的长度。,计算“以最大速率发送突发数据的持续时间”：设突发时间为S秒，令牌桶容量为C字节，令牌到达的速率为字节/秒，最大的输出速率为M字节/秒，那么，一次突发性的输出将包含CS字节。同时知道，在长度为S秒的最大速度突发过程中，字节数量为MS，则：CSMS，SC/(M-),80,漏桶算法与令牌桶算法的区别,流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。 漏桶中存放的是数据包，桶

45、满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。,81,6.5 网络互联,一组相互连接的网络,82,6.6.1 网络的不同之处,83,6.6.2 网络如何连接起来,两个网络通过网桥或交换机互连，接收帧，通过MAC地址，将这些帧转发到另一个不同的网络中。在这个过程中，交换机有一点协议转换，例如：以太网到FDDI,两个网络通过路由器互连，接收分组，通过IP地址，将这些分组转发到另一个不同的网络中。在这个过程中，路由器要进行协议转换，例如：以太网到分组交换网。,84,6.6.3 级联虚电路（1）,级联虚电路（Concatenated Virtual Circuits） 工作过程

46、级联虚电路工作过程与虚电路子网工作过程相似； 建立连接 当目的主机不在子网内时，则在子网内找一个离目的网络最近的路由器，与之建立一条虚电路； 该路由器与外部网关建立虚电路； 该网关与下一个子网中的一个路由器建立虚电路； 重复上述操作，直到到达目的主机。 传输数据 相同连接的包沿同一虚电路按序号传输； 网关根据需要转换包格式和虚电路号。 拆除连接,85,6.6.3 级联虚电路（2）,使用级联虚电路实现网络互连,86,6.6.4 无连接网络互连,无连接网络互连（Connectionless Internetworking） 工作过程 无连接网络互连的工作过程与数据报子网的工作过程相似； 每个包单独

47、路由，提高网络利用率，但不能保证包按顺序到达； 根据需要，连接不同子网的多协议路由器做协议转换，包括包格式转换和地址转换等。,一个无连接的网络互连,87,6.6.5 隧道技术（Tunneling）(1),隧道技术 源和目的主机所在网络类型相同，连接它们的是一个不同类型的网络，这种情况下可以采用隧道技术。,88,89,6.6.5 隧道技术（Tunneling）(2),工作过程（以上图为例） 主机1发送一个包，目的IP地址 = 主机2-IP，将包封装到局域网帧中，帧目的地址 = 路由器1-MAC； 局域网传输； 路由器1剥掉局域网帧头、帧尾，将得到的IP包封装到广域网网络层包中，包目的地址 = 路

48、由器2地址； 广域网传输； 路由器2剥掉广域网包头，将得到的IP包封装到局域网帧中，包目的IP地址 = 主机2-IP，帧目的地址 = 主机2-MAC地址； 局域网传输； 主机2接收。,90,6.6.6 互联网路由,工作过程 互联网络的路由与单独子网的路由过程相似，只是复杂性增加； 两级路由算法 内部网关协议（IGP: Interior Gateway Protocol）RIP，OSPF 外部网关协议（EGP: Exterior Gateway Protocol）BGP 自治系统AS（Autonomous System）,91,6.6.7 分段（1）,每种网络都对最大包长有限制，有以下原因 硬件

49、，例如 TDM 的时槽限制； 操作系统； 协议，例如包长度域的比特个数； 与标准的兼容性； 希望减少传输出错的概率； 希望避免一个包占用信道时间过长。 大包经过小包网络时，网关要将大包分成若干段（fragment），每段作为独立的包传输。,92,6.6.7 分段（2）,段重组策略 分段重组过程对其它网络透明 网关将大包分段后，每段都要经过同一出口网关，并在那里重组； 例，ATM网络； 带来的问题 出口网关需要知道何时所有分组都到齐； 所有分组必须从同一出口网关离开； 大包经过一系列小包网络时，需要反复地分段重组，开销大。,93,6.6.7 分段（3）,分段重组过程对其它网络不透明 中间网关不做

50、重组，而由目的主机做； 带来的问题 对主机要求高，能够重组； 每个段都要有一个包头，网络开销增大；,94,95,6.6.7 分段（4）,举例：将一个大的分组分成小的分组,分组号,第一个基本分段的号,分组结束位；0表示分段，1表示不分段,分组头,当通过一个最大分组长度为“8个数据长度头部”的网络之后的分段,当通过一个最大分组长度为“5个数据长度头部”的网络之后的分段,96,6.6 网络互联（19）,6.4.6 防火墙（Firewalls） 什么情况下使用防火墙？ 为防止网络中的信息泄露出去或不好的信息渗透进来，在网络边缘设置防火墙； 防火墙的一种常用配置 两个路由器，根据某种规则表，进行包过滤；

51、 一个应用网关，审查应用层信息。,97,98,小结,互联网（internet）：两个或多个网络构成互联网 网络互连设备：中继器、网桥、路由器、传输网关、应用网关 虚电路网络互联 数据报网络互联 隧道技术 分段和重组 防火墙,99,6.7 INTERNET网络层协议,在网络层，Internet可以看成是自治系统的集合，是由网络组成的网络。 网络之间互连的纽带是IP（Internet Protocol）协议,100,6.6.1 IP协议(1),20字节,D：延迟、T：吞吐量、R：可靠性,总长度（Total Length）：包含头和数据，最大长度为65535字节,DF：不分段 MF：更多的段 Fra

52、gment offset: 分段偏移，除了一个数据报的最后一个分段以外，其它所有的分段必须是8字节的倍数。,240/8=30,TTL：最大为255秒,Protocol：指出传输层协议； Header checksum：头部校验和，只校验头部。,101,6.6.1 IP协议(2),102,6.6.2 IP地址(1),IP地址（IP Address） 地址组成：网络号 + 主机号； 地址表示采用用点分隔的十进制表示法，如166.111.68.3；,103,6.6.2 IP地址(2),全0和全1有特殊含义 全0：表示本网络或本主机； 全1：表示广播地址；,104,6.6.2 IP地址(3),子网（S

53、ubnets） 分而治之的思想：为了便于管理和使用，可以将网络分成若干供内部使用的部分，称为子网。对外界，该网络还是一个单独的网络。,105,IP地址实例 1,当你想将一个数据报从源地址发送到目的地址时，I P 协议要进行路由判断。请看下面的例子：,注意，它们在不同的网络中。尽管它们都是B 类地址，但它们的前1 6 位并不相同。由于它们的不同，则从I P 协议的观点来看，它们应该在不同的物理网络上。发送的数据报应先到达路由器，然后路由器再将这个数据报转发给目标设备。如果两个地址的网络号相同，则I P 协议仅关心子网划分情况。,106,IP地址实例 2,子网掩码有助于我们确定子网号。请看下面的例

54、子,在这个例子中，目标地址已经修改。同时我们还加入了一个子网掩码，用它来进行子网划分。由于使用的是B类地址，所以掩码中的前两个2 5 5 指向地址的网络部分，第三个2 5 5 用于定位子网域，它是本地可管理地址的一部分。 掩码中的1指向子网位。这两个设备是在同一个子网中吗？请看每个地址中第3个8 位位组中的每一位。源地址的二进制子网域中的内容是0 0 0 0 0 1 0 0 ；目标地址的二进制子网域中的内容是0 1 1 0 0 0 1 0 。因为这两个二进制数字不同，所以这两个设备不在同一个子网中。此时，源设备首先要将数据报发送给路由器，路由器再将数据报发送给在目标网络中的目标设备。,107,

55、IP地址实例4,问题：我们经常混淆地址和掩码，如何知道它们的不同？ 解答：掩码的第一个8 位位组是2 5 5 ，而地址中的第一个8 位位组永远不会是2 5 5 。 问题：如何确认为网络选择的掩码是正确的？ 解答：尽管你做了正确的调查研究，并且用当前信息建立了可能是最好的掩码，但当你的网络设计和网络管理发生变化时，如果你不得不要修改地址管理结构，这就说明你选择的掩码是不适当的。当你选择掩码并建立你的地址管理规划时，最好的建议是有足够的空间以满足未来子网的增加和每个子网中主机的增加。,108,IP地址实例5,给定的IP地址为192.56.12.120,子网掩码是:256.256.256.240。

56、问：1.子网络号？ 2.主机号？ 3.直接的广播地址？ 4.如果主机地址的头十位用于子网，那么184.231.138.239的子网掩码 是？ 6.如果子网掩码是256.256.192.0，那么下面那个主机必须通过路由器才能与主机129.23.144.16通信？ 1.A.0.0.0.112 B.0.0.0.120 C.0.0.12.120 D.0.0.12.0 2.A.0.0.0.120 B.0.0.12.8 C.0.0.0.8 D.0.0. 0.127 3.A.256.256.256.255 B.192.56.12.127 C.192.56.12.120 D.192.56.12.112 4.A

57、.256.256.192.0 B.256.256.224.0 C.256.256.256.224 D.256.256.256.192 6.A.129.23.191.21 B.129.23.126.222 C.129.23.130.33 D.129.23.148.127,109,IP地址实例5（续）,解答： 1、192.56.12.120是一个C类地址，240=11110000，120=01111000，则子网号为：01110000=112。 2、主机号为：00001000=8。 3、直接广播地址为主机号为1，则广播地址为192.56.12.127 。 4、184.231.138.239为B类地

58、址。主机地址占6位，则子网掩码为： 256.256.256.192。 5、129.23.144.16为B。主机地址占14位。则,110,IP地址的补充说明专用IP地址,TCP /IP协议需要IP地址支持，IP地址资源具有告急的趋势，使用IP地址的组织未必要求接入因特网。 解决方案：用于专用网的地址分配方案（RFC1918） 原理：定义两类IP地址， 全局IP地址用于因特网公共主机； 专用IP地址仅用于组织的专用网内部本地主机。 公共主机和本地主机可以共存于同一网络和进行互访； 本地主机必须经网络地址迁移服务器（NAT或代理服务器）才能访问因特网。 RFC1918定义的专用IP地址： 10.0.

59、0.0 10.256.256.255 1个A类地址； 172.16.0.0 172.31.256.255 16个连续的B类地址； 192.168.0.0 192.168.256.255 256个连续的C类地址。 业界支持：大多数路由器不转发携带本地IP地址的分组。,111,无类域间路由CIDR(1),无类域间路由CIDR （Classless InterDomain Routing） CIDR的提出 Internet指数增长，IP地址即将用完 IP is rapidly becoming a victim of its own popularity. 基于分类的IP地址空间的组织浪费了大量的地址 The real villain is the class B network. CIDR RFC 1519 基本思想：将剩余的C类地址分成大小可变的地址空间；,112,