计算机网路复习笔记之网络层基础

网络层基础

网络层关注的是如何将源端数据送到另一方,为了将数据送到另一方,可能会经过很多跳中间路由器。网络层处理的是端到端的数据。
为了达到这样的目的,网络层必须知道网络的拓扑结构。并从中选取适当的路径传输;此外,网络层还得仔细选择路由器,避免线路拥塞和路由器负载过重,而其他路由器则很清闲。
当源端数据和接收端数据来自不同网络时,需要网络层来解决。

1.网络层的设计问题

5.1存储数据包与网络交换
如果一台主机需要发送一个数据包,它将数据包传递给就近的路由器,路由器可能在它自己所在的LLAN上,也可能在通往IPS的点到点的链路上;
在数据包到达路由器后,路由器的链路层对其进行校验和验证后,它首先会被存储在路由器上;接着沿路径被转发到下一个路由器,直至达到目标主机。
这是一种存储-转发数据报交换的模式。

2.无连接服务的实现

无连接的服务:所有数据包将会被独立的注入到网络中,并且每个包独立路由,不需要任何的提前设置。这里我们把数据包也称为数据报,对应的网络被称为数据报网络。
有连接的服务:在发送数据包之前,需要建立一条源路由器到目标路由器的路径,我们把这个连接称为虚电路。其类似于电话系统中建立的物理电路,该网路也被称为虚电路网络。

每个路由器将含有一个路由表,它指明了每一个可能的地址应该将数据包送到哪里去。每个表项由两部分组成,目标地址和通往目标地址所使用的出境线路。
每个路由表是可变的,管理这些路由表并作出路由选择的算法是路由算法。
IP协议是Internet的基础,它是无连接协议的范例。每个数据包携带一个IP地址,路由器根据IP地址来单独的转发每一个包。

3.有连接的服务

有连接的服务需要一个虚电路,为了避免数据包选择一条新的路径。需要使用路由表记录下来已经确认的路径,当连接被释放,虚电路消失。在面向连接的服务中,每个数据包都带有一个标识符,指明它属于哪一条虚电路。

这里的路由表是这样的,对于某个路由器而言,其包含了入境和出境两个逻辑列,每个列含有两行,分别指定了路由器和标识符。这里的出境标识符是可变的(为了解决某些冲突需要改变一下标识符)。这个改变出境标识符和的过程也被称为标签交换

4.简单的比较

使用虚电路需要有一个花费时间并且耗费资源的建立过程,之后处理数据包非常容易;在数据报网络中,不需要建立连接,但路由器需要一个更复杂的查找过程。对于数据报网络而言,需要使用更长的目标地址,因此如果在数据量很小的情况下,目标地址承担了巨大的开销,宽带资源被浪费。
在控制拥塞方面虚电路表现得更好,因为在建立连接时,资源可以提前预留。最后是事务处理和健壮性,虚电路网络并不能够表现得很好,因为其需要花费大量的时间用于建立和清除虚电路并且一旦发生宕机,虚电路终端,所有的数据都会受到影响。

路由算法(⭐️)

路由算法属于网络层软件的一部分:其负责确认一个入境数据包应该被发送到哪一条输出线路上。如果网路选择了数据报,那么路由器需要对每一个到达的数据包重新选择路径,因为自上次选择了过后,可能最优路径已经发生改变;对于使用虚电路时,只有在新建一条虚电路时,才需要路由决策,这种情形被称为回话路由

我们可以把一个路由器内部想象成为有两个进程,一个用于接收数据包,检查数据包并且转发,一个则用于更新路由表。

路由算法需要含有的特性:正确性,简单性,鲁棒性,稳定性,公平性和有效性。

路由算法分类:

  1. 非自适应算法:不会对当前进行测量,或者估算流量和拓扑结构来调整路由决策,相反所有路由都是在离线条件下计算好,并在网络启动时下载到路由器中,这个过程也被称为静态路由。该算法只适用于对路由选择已经很清楚的情况。

  2. 自适应算法:改变路由决策以便反应出拓扑结构的变化,通常也反映出流量的变化。
    这些动态路由算法在各个方面也有表现不同,获取信息的来源不同,改变路径时间的不同,对路由的优化度量不同等。

优化原则

最优路径的一般陈述:如果路由器J在路由器I到K的最优路径上,那么从J到K的最优路径仍然遵循同样的路由。

汇集树:作为最优化原则的一个直接结果,从所有的源到一个指定目标的最优路径的集合构成的一颗以目标节点为根的树。
汇集树不一定是唯一的。
汇集树不含有环,因此在指定的跳数内一定可以完成对数据包的传递。
每一个路由器都有一颗汇集树,根节点就是该路由节点。

具体的路由算法

最短路径算法

构建一张网络图,图中的每个节点代表一个路由器,每条边代表一段通信线路。为了选择一对给定路由器的路由,算法只需要在图中找到他们的最短路径。
采用Dijkstra算法(这里的思想完全一致)。

泛洪算法

路由器将数据包发送给到达线路之外的所有出境线路。
分析:这样的做法会导致大量的冗余数据包,并且如果不加限制的话,将产生无数个重复的包。
限制的做法有:

(1) 在每个包头加上一个跳计数器,每经过一个路由器,跳数减一,跳数为0时,丢弃掉该包。理想情况下,计数器的大小是源端到目的端跳长度;最坏的情况是整个网络的最长路径。

(2) 追踪已经泛洪过的数据包,避免第二次发送它们。每个源路由器在接收数据包时给数据包添加上一个序号,每个路由器为源路由器建立一个表,其中包含了这些已经泛洪过的数据包的序号,如果某个数据包的序号在这张表中,则不再泛洪该包。
(3)为了防止这张表无限膨胀,每个表使用一个计数器k作为参数。它表示直到k的所有序号都已经观察到了。当一个数据包入境时,很容易检测该包是否被泛洪过,只需要比较和k的大小,如果泛洪过,丢弃该包。

泛洪算法对于广播是一种有效的手段,但是对于其他用途而言不切实际。泛洪算法的鲁棒性非常好,如路由器损坏导致拓扑结构发生变化,仍然能够起比较好的作用。

距离矢量算法⭐️

每个路由器维护一张表,表中列出了当前已知到每个目标的最佳距离以及所使用的链路。这些表通过邻居之间相互交换信息而被不断更新,最终每个路由器都了解到达每个路由器的最佳链路。

路由器维护的表一共有两项,第一项是目的路由,第二项是到其的最优路径的跳数(也可以是一个综合计算的数值)。通过邻居分享的路由表可以计算出新的信息,如果有最佳路径,就更新该路由器的路由表。
注:感觉这里是绝对的重点,一定要掌握如何计算和更新路由表。

距离矢量算法会产生一个无穷计算的问题,关于什么是无穷计算,这里需要看书。
距离矢量算法的另一大缺点就是:当网络拓扑结构发生变化时,路由算法需要太长的时间才能收敛到稳定的状态(无穷计数问题引起)

链路状态路由算法⭐️

步骤:

  1. 发现其邻居节点,并掌握它们的网络地址
  2. 设置到每个邻居节点的长度值(或者说是成本度量值)
  3. 构造一个包,包含上述信息
  4. 将这个包发送给所有其他路由器,并且接受来自其他路由器的包
  5. 计算出到每个其它路由器的最佳路径

对于发现邻居,其实是很好理解的,每个路由器在启动过后都发送一个特殊的HELLO数据包,其邻居接到过后就会返回一个应答,包含了自己的网络地址等信息。

链路成本的计算:一种常用的选择是成本与链路带宽成反比。或者使用延迟估算来作为成本计算的方式。

构造链路状态包:
包含了以下内容:发送方的标志,序号,年龄(后面介绍),邻居和其成本的二元组。

构建链路状态包的时期为:周期性的构建或者当网络拓扑结构发生变化了进行构建。

对于发送包和接收包,这里使用的是泛洪算法,age字段的作用是防止数据包无限的生存下去,递减到0时则丢弃该包(这里不是到达一个路由器age-1)而是每过一个时间减一,比如说一秒。

计算新路由:使用的是Dijkstra算法计算。

链路状态路由算法相比距离矢量算法需要更多的内存和计算,对于一个具有n个路由器的网络,每个路由含有k个邻居,则用于存储输入数据的内存与kn成正比,并且计算时长的增长快过kn,在大型网络中运行这个算法仍然是个问题。不过在实际过程中,由于其并没有慢收敛的问题,因此工作的还不错。

层次路由

对于规模特别大的网络,可以把网络分成区域,对于区域内部仍然构建详细的路由,对于区域外部,只构建层次的路由表项,不关心内部。这样可以减小一个路由器维护的路由表的大小。

广播路由

使用泛洪算法,使用逆向路径转发的思想构建一颗汇集树。
生成树:网络的一个子集,包含所有路由器并且不含环路。汇集树属于生成树的一种。

组播路由

为了防止给不是该组成员发送,在采用广播的思想上,需要对生成的汇聚树进行剪枝。通过把不是改组成员去掉,可以构建组播树。

如果使用的是链路状态路由算法,每个路由器知道完整的拓扑结构,并且知道每个路由器是属于哪个组的情况下,可以使用最简单的组播算法。每个路由器针对组内每个发送者构建一颗它自己修剪后的组播树。具体的做法是首先构建一颗简单的汇聚树,然后再把不是该组的链路去掉即可。

拥塞控制算法⭐️

拥塞:网络中存在太多的数据包导致数据包被延迟和丢失,从而降低了传输性能。

拥塞控制和流量控制

拥塞控制的途径:简单来说需要增加资源和减小负载。在时间尺度上,要么事先避免拥塞,要么在发生拥塞过后迅速做出反应。

基本方法是建立一个与流量匹配的良好网络;
根据流量模式制定路由(改变最短路径权重等);
如果无法增加容量,那么可做的就是降低负载了。例如对于有连接的服务,如果此时负载很大,应该拒绝建立虚电路的请求,这样的控制也被称为准入控制。

流量感知路由

把链路权重设置成为一个带宽,延迟,负载,排队延迟的多方面函数,在其他条件都相同的情况下,最小权重的路径更青睐那些轻负载的路径。

早期的流量感知路由存在一个问题,把负载考虑进链路权重过后,如果某一条链路非常拥挤而另外一条很空闲,那么下一时刻负载将会转移到这条链路,但是下一时刻有回到原先的链路,从而导致网络抖动。解决办法是不考虑负载,只考虑带宽和传输延迟,这样的问题就不会发生。

准入控制

这是一种用于虚电路网络,防止出现拥塞的技术。其基本思想很简单:除非网络可以携带额外的流量而不会变得拥塞,否则不再建立新的虚电路。准入控制可以和流量感知路由结合,在建立虚电路的过程中,避开负载高的线路。

流量调节

必须要解决的两个问题:

(1)路由器必须确定何时快要接近拥塞(链路利用率,丢包数和排队包数),每个路由器连续监测它正在使用的资源

(2)路由器必须及时把信息反馈给造成拥塞的发送方

对于信息的反馈,这里有下面几种方法:

  1. 抑制包,路由器随机选择一个被拥塞的数据包,给数据包的源主机发送一个抑制包。同时打上标记,以防在发送的图中产生更多的抑制包。
  2. 显式拥塞通知,基本原理如下,路由器给每个转发的数据包打上标记,表明目前该链路正经历着拥塞,当包到达接收方时,接收方在回复应答包的时候会携带流量调节的信息,从而告诉发送方控制发送的速度。
  3. 逐跳后压,存在一种这样的情况,当发送方速率很快的时候,即使抑制包发送出去后,在到达发送方之前,仍然会注入大量的数据导致网络更加拥挤,所以这里可以这样:让抑制包抑制它经过的每一跳,这样的话,短时间内抑制效果将会生效,来达到快速缓解负载很大的链路段的压力。

负载脱落

当流量感知路由,准入控制和流量调节都没办法消除拥塞是,路由器可以使用负载脱落来消除拥塞。其思想很简单,当路由器快要被淹没时,直接丢弃掉这些数据包。
这里有一个问题,丢弃什么包呢?当然是丢弃掉不那么重要的包,这里的选择是这样的,发送方在发送包之前就给每一个包打上标签,表明这个包有多么重要,这样在丢包的时候可以参考这个标签,丢弃掉不那么重要的包。

随机早期检测算法(RED ⭐️):为了确定何时丢包,路由器要维护一个运行队列长度的平均值,在这个值超过某个阈值时,该链路就被认为即将拥塞,因此路由器丢弃一小部分的包(随机)来避免拥塞。
这里使用随机丢包的好处是可以更高概率的丢掉速率很快的发送方的包,因此发送方不得不重传这些被丢掉的包,而上层协议也会建议该发送方放慢速度,来达到避免拥塞的效果。

服务质量

有些应用对于网络的需求特别大,并不满足于网络的“尽力而为“,这个时候网络需要提供良好的服务质量来达到要求。

最简单的方式就是过度配置:建设有足够网络容量的网络,可以满足任何的流量需求。这不是可笑的想法,因为电话系统就是一个很好的例子。

确保服务质量必须解决下面的四个问题:

(1)应用程序需要网络什么样的质量?

(2)如何规范进入网络的流量?

(3)为了保障性能如何在路由器预留资源?

(4)网络能否安全的接受更多的流量?

应用需求

流:从源端发送到一个接收方的所有数据包被称为一个流。对于每个流的需求可以以下面四个参数来衡量:带宽,延迟,抖动,丢失。不同的应用这四个方面的要求不同。

流量整形

漏桶算法和令牌桶流量

想象一个漏桶,无论倒入水的速率有多大,只要漏桶还有水,其速率恒定;如果没有水,速率为0;如果超出漏桶容量,额外进入桶的水都会通过桶侧分流,最终流失掉。

概念上,每个主机连接到网络接口中含有一个漏桶,为了向网络层发送数据包,必须往网络中注入更多的水。如果漏桶满了来了一个数据包,该数据包必须排队等待漏桶空出来时再接纳,或者直接被丢弃。

令牌桶:把网络接口想象成为一个漏桶,正在往里灌水,速率为R,桶容量为B。现在,为了发送一个数据包,我们必须能够从桶内掏出水或者令牌。桶内只可以累积固定数量的令牌,如果桶是空的,那么必须等到累积到一定的令牌才能发送一个数据包。

包调度

定义:在同一个流之间以及在竞争流之间分配路由器资源的算法成为包调度算法。
不同的流可以预约潜在的资源有以下三种:带宽,缓冲区,CPU周期。
包调度算法负责分配带宽和其他路由器资源,具体的做法是确定下一次把缓冲区中的哪些数据发送到输出线路。最简单的方式是先进先出FIFO。
FIFO路由器在队列满时通常丢弃新到的数据包,由于新到的数据包会排在末尾,因此这种行为也被称作尾丢包
FIFO容易实现但是无法提供较好的性能。
公平队列:针对每一条输出线路,路由器为每个流设置单独的队列。当路线空闲时,路由器循环扫描各个队列,然后分别取一个进行发送。这样就保证了绝对的公平,但是也有不足(宽带需求小的往往占据了更多的带宽)。

其他的调度算法:
加权的公平队列
优先级调度
时间戳先后发送

网络互联

隧道技术

处理两个处于不同网络相互连接时的情况超级困难,然而却存在一种非常常见的情形,就是源主机和目的主机的网络类型是完全相同的。但是其中间却隔着一个不同的网络。解决这样问题的技术被称为隧道技术。
隧道技术广泛被用于那些因使用了其他网络而被隔离的的主机和网路。结果生成的网络就被称为覆盖网络,因为它有效的覆盖在了基础网络之上。
隧道的缺点就是无法到达位于隧道之下的网络的主机,因为数据包无法从隧道中逃生。

分享到 评论