beyond myself

0%

计算机网络复习-第五章

发表于 更新于 分类于 ，

《Computer Networking - A Top-Down Approach》第五章复习知识点总结

第五章主要介绍如何配置和管理网络，以及这其中使用到的各种协议如OSPF，BFP，ICMP，SNMP

5.1 介绍

转发和路由之间的桥梁就是转发表：

  • 转发功能使用转发表进行包的转发
  • 路由功能配置，更新，维护转发表以便转发使用

而路由功能可以通过两种方式来实现：

  1. 分布式的各路由器处理(Per-router control)
    1. 每个路由器上都有一个路由处理单元，他们通过和邻居路由器的路由处理单元的通信，计算出路由表
  2. 集中式的中央处理(Logically centralized control)
    1. 存在一个中央处理单元负责计算所有的路由器上的路由表并将其分发到各个路由器上
    2. 每个路由器上又一个Control Agent负责接收中央处理单元的命令，更新路由表

5.2 路由算法

对于一个网络，可以将其抽象为一个图，路由器和链路分别对应图中的节点和边。

路由算法的任务，就是找出图上点对之间的最小距离及最小距离对应的路径。

路由算法的分类：

  • 中心化的或去中心化的
    • 中心化的路由算法是基于对整个网络有着完整的认识基础上进行最短路径计算的
      • 中心化路由算法可以由中央处理单元进行，也可以在每个路由器上分别进行
      • 这需要在计算路由之前首先获得整个网络的链路信息
      • 中心化路由算法又被称为LS(link-state)算法
    • 去中心化的路由算法是仅基于各个路由器知道邻居路由器之间的链路和链路代价进行最短路径计算的
      • 去中心化的路由算法是分布式的，分散在各个路由器上进行计算
      • 去中心化的路由算法又被称为DV(distance-vector)算法
  • 动态路由算法或静态路由算法
    • 动态路由算法改变比较迅速，随着链路负载和网络拓扑结构的改变而改变路径
    • 静态路由算法相对来说改变比较少，一般需要认为改变链路代价才会改变路径
  • 负载敏感或负载不敏感
    • 负载敏感的路由算法随着链路拥塞情况的改变会改变路径
    • 负载不敏感的路由算法于链路拥塞情况无关
    • 负载敏感的路由算法实现起来困难重重，现实中使用的都是负载不敏感的算法

LS算法需要提前知道网络中的链路结构和链路代价，一般来讲，这是通过各个路由节点广播自身周围的链路与链路代价完成的。

而后所有的节点都会对整个网络有了了解，每个节点都可以运行LS算法，计算最短路径。

Dijkstra‘s Algorithm是一个常用于LS算法的图论最短路算法。在运行了Dijkstra‘s Algorithm后，路由器上就只需要存储<目的地，下一跳链路>对就可以了。

但是如果希望满足负载敏感的话，就会出现路由震荡的情况，解决的办法是让路由器在不同的时间点上进行路径计算，但是因特网路由器被发现是自同步的，也就是说即便一开始设置了不同的时间点，后来也会变成同一时间点计算，最后的办法就是随机时间发送路由控制包。

5.2.2 DV(Distance-Vector) 算法

在DV算法中，每个路由器接收来自邻居路由器的消息，计算路径，而后将结果再交给邻居路由器。常此往复，知道没有消息传递为止。

  • DV算法是去中心化的算法，不需要知道所有链路结构和代价
  • DV算法是异步算法，不需要同步，只需要接受消息并计算
  • DV算法是自终止算法，不需要特定的消息提醒终止，当链路上没有消息传递时，自动终止

Bellman-Ford等式是DV算法的重要基础：

$d(x,y)=\min_v{c(x,v) + d(v, y)}$

其中$v$是$x$的邻居，$d(x,y)$代表$x,y$之间的最短路径，$c(x,v)$代表$x,v$之间的路径代价。

这个等式对于$x$的取值揭示了从$x$到$y$所需要的下一跳目标$v$。而且所需要用到的信息只有$x$本身和邻居的信息。

所以路由器x上存储了：

  • x到周围邻居的链路代价
  • x的距离矢量，也即x到所有节点的最小路径长度
  • x的邻居的距离矢量

在DV算法中，每个路由器会将自己的距离矢量发送给邻居，邻居接收到后根据Bellman-Ford等式修改自己的距离矢量，如果修改成功，就将更新后的自己的距离矢量发送给邻居，最终距离矢量收敛到真正的最小距离。

count-to-infinity问题和poisoned reverse

count-to-infinity 是指由于链路代价的变化，使得某个节点x选择前往y的最短路下一跳时选择了z，但同时z前往y的最短路下一跳是x。这时在转发表中就形成了一个环。

解决这个问题的办法是，如果z前往y的最短路下一跳是x，那么在向x发送距离矢量的时候，告知z前往y的代价是无穷大，避免x选择前往y的下一跳时选择z，这就是poisoned reverse。

但是poisoned reverse也不能完全解决count-to-infinity问题。

LS 和 DV 算法比较

从消息复杂度，时间复杂度和鲁棒性来看，两个算法都不相上下。

其中LS需要$O(|V||E|)$的消息复杂度，$O(n^2)$的时间复杂度，由于计算是每个路由器独立计算，提供了一定的鲁棒性，但是一个路由器的错误消息也会被传递到所有路由器上进行计算。

DV的消息复杂度和时间复杂度都很难确定，鲁棒性上来看，一个错误的距离矢量也可能被传播到许多路由器上。

5.3 intra-AS Routing in the Internet: OSPF

在之前的讨论中，我们一直对路由网络做了简化，其中只有路由器和链路，但事实上，我们忽略了以下两个重要因素：

  • 规模。大规模的网络不可以向上述讨论一样简单使用普通的路由协议。因为即便只是存储下一跳的目标，都需要极大的内存。
  • 管理自治。不同的网络一般需要进行独立的管理，但是将所有的路由器纳入一个路由协议下，显然不能满足这个需求。

于是自治系统应运而生，也就是说，一个自治系统内，使用统一的路由协议进行管理，对外暴露网关进行通信，这样既能够通过控制自治系统的大小来控制路由协议作用的规模，也能实现自治系统内部的管理自治。

OSPF(Open Shortest Path First)

OSPF协议就是自治系统内部的路由协议。Open的意思是开源的，他的各种细则声明都可以在网上查到。

OSPF是一个LS算法的协议。所有的路由器首先以广播洪泛的方式将整个网络的链路结构和链路代价存储下来，而后使用Dijkstra‘s Algorithm进行最短路径和下一跳的计算。

同时OSPF并不涉及链路代价的配置，这个配置是有人为决定的。

所有的OSPF消息都由IP包携带，通过将IP包头中的上层协议域设置为89表明这是OSPF消息包。

OSPF支持以下的特性：

  • 安全。OSPF消息可以进行验证，验证方式有两种 — 简单验证和MD5验证。
    • 简单验证
      • 每个路由器上存放有明文密码
      • 传输消息时将明文密码放在消息里。
    • MD5验证
      • 每个路由器上存放有MD5密钥
      • 传输消息时将消息内容和MD5密钥结合算法产出一段哈希值，放在内容后面
      • 收到消息的路由器使用密钥再度哈希内容并和传来的哈希值比较，如果一致，验证就通过。
      • MD5验证时还会有序列号，防备replay攻击。
  • 多个同代价的路径。
    • 在选择最短路径时，可能会有多条路径，OSPF并不要求一定要选择一条，可以多条一起使用，降低负载压力。
  • 单播和多播的整合支持
  • 自治系统内部的再度结构化
    • 自治系统内部可以在被分成不同的区域
    • 有一个特殊区域为backbone area
    • 一个区域内部自由通信
    • 一个区域边界会有一个border router，用于和别的区域通信
    • 不同区域通信需要先经过border router，进入backbone area，再从border router出去到目标区域的border router，再进入区域，到达终点

5.4 Routing Around the ISPs: BGP

当我们需要在不同的自治系统之间进行通信时，OSPF就不能满足我们的需要了，同时，在不同的自治系统之间进行通信必须使用统一的协议，而实际上在因特网里就是全部使用的边际网关协议(Border Gateway Protocol)进行自治系统之间的通信。

对于一个自治系统内的主机，我们是使用IP地址进行的定位，但是对于一整个自治系统，我们是使用IP地址前缀进行定位。

5.4.1 The Role of BGP

对于一个自治系统间的通信协议，BGP需要提供一下两个基本的功能：

  1. 获取可到达的子网前缀。对于一个自治系统，他需要知道自己能够和哪些自治系统通信，以及这些自治系统的IP地址前缀是什么。
  2. 获取自治系统间的最好路径。

这两个功能是通过在路由器中存储<子网前缀，输出端口>的表来实现的

5.4.2 Advertising BGP Route Information

BGP协议是通过TCP连接来获取路由信息的：

  • 不同自治系统之间的BGP连接称为eBGP连接
  • 自治系统内部的BGP连接称为iBGP连接

注：BGP连接是逻辑连接，BGP连接的两端之间可能有多条链路

想要告知其他自治系统关于子网前缀的信息，就必须使用BGP消息：

  1. 源节点首先发出BGP消息
  2. 在路径上的自治系统网关通过eBGP连接收到消息
  3. 网关通过iBGP将消息广播到自治系统内的所有节点
  4. 网关继续通过eBGP将消息传递到其他的自治系统

5.4.3 Determining the Best Routes

当一个子网前缀通过BGP消息在自治系统间进行传输时，还会带上额外的属性：

  • AS-PATH，记录传播这个消息所经过的自治系统路径，同时可以作为环路检测–如果一个自治系统发现AS-PATH上有自己的名称，就说明出现环路，可以直接丢弃BGP消息
  • NEXT-HOP，AS-PATH的起始节点的IP地址

这两个属性是众多属性中对于选路最重要的两个属性。

也就是说，我们现在有的是多个(子网前缀，AS-PATH，NEXT-HOP)元组，这被称为一条路径，BGP需要决定最优路径

烫手山芋路由 (Hot Potato Routing)

烫手山芋路由的主要原则是：

尽量使得包在本自治系统内的时间短

所以烫手山芋路由采用的策略是：

选取从当前节点到NEXT-HOP最短的路径

我们可以看到，在这个过程中，起作用的最主要不是BGP，而是自治系统内部的路由协议(比如OSPF)，因为从当前自治系统的网关到达NEXT-HOP只有一条链路(这就是NEXT-HOP的定义)，剩余的代价是由当前节点到网关的代价决定的。

Route Selection Algorithm

实际上，BGP使用更加复杂的策略进行选路：

  1. 每条路径有一个本地偏好，选择本地偏好最优的。本地偏好由路由器自己设置或者由邻居路由学习而来，但是产生本地偏好的策略是由路由管理者人为设置的。
  2. 在剩余的路径中，选择AS-PATH最短的。
  3. 在剩余的路径中，采用烫手山芋路由策略。
  4. 如果还有多条路径，使用BGP identifier选路

5.4.4 IP任播

IP任播的意思是给出一组服务器，向其播送IP包，但是最终只能有一个服务器收到IP包。

IP任播可以用于DNS服务，因为所有的DNS服务最终返回的结果都是一样的(域名对应的IP地址)，但是需要选择一个最近的DNS服务器以便更快地获得结果。也就是要对一组DNS服务器发送请求，但是最终只需要一个DNS服务器回复就可以。

使用BGP实现IP任播的原理是：

  1. 给所有服务器赋予相同的IP地址(虽然说不同的主机需要唯一IP地址，但是由于这里的服务器提供的服务是一摸一样的，所以这么做没问题)
  2. 当使用BGP进行路由注册时，BGP自动使用选路策略完成了到当前最近的服务器的选路
  3. 接下来向该IP地址发送包，就已经是最近的服务器了

5.4.5 Routing Policy

对于选路，最终其实还是靠策略来决定选择的路径。

树上描述了一个情境，比如希望B不要选择通过X发包到C，避免这样的做法就是在策略中是的X不告知B从X可以发到C。

5.4.6 Putting the Pieces Together: Obtaining Internet Presence

假设你开了一家公司，架设了几台服务器，那么，想要全世界访问你的网站，需要如下操作：

  1. 获得物理连接，接到一个ISP上
  2. 获得IP地址分配，在这一步，获得了子网的IP地址前缀，并且通过BGP注册到了各个路由器上
  3. 将具体的IP地址分配给每一台主机
  4. 购买域名，提供你的DNS服务器IP地址，顶层域名上会注册你的域名和DNS服务器地址
  5. 用户访问，首先通过顶级域名DNS服务器获得你的DNS服务器地址，通过你的DNS服务器获得你的其他服务器地址，而后建立TCP连接

5.6 ICMP(Internet Control Message Protocol)

ICMP在结构上是传输层协议，ICMP消息通过IP包的负载传递。

但是在作用上，ICMP是用于传递IP协议的信息的，尤其是报错信息。

ICMP消息有三个部分，类型，消息码和产生ICMP消息的IP包的前8个字节。

ping命令原理：ping向目标服务器发送类型8消息码0的ICMP消息，服务器返回类型0消息码0的回应。

traceroute命令原理：

  • traceroute向目标服务器传递UDP消息
  • 但是将外层的IP协议包头的TTL设置为1，2，3，…一直下去
  • 每次当TTL到0，IP包被丢弃的时候，路由器都会发送特定的ICMP消息告知traceroute
  • 最终到达目标时，由于traceroute传出的UDP包端口号是无效的，目标服务器也会发ICMP消息告知traceroute
  • 此时的ICMP和之前的不同，所以traceroute也停止了UDP包的继续发送
  • 通过这些消息到达计时，traceroute算出每一跳的时间

5.7 Network Management and SNMP

网络管理其实类似于网络配置，使用一定的协议进行通讯并对网络中各个组件的参数进行监控和配置。

5.7.1 网络管理框架

网络管理有如下部分组成：

  1. 网络管理服务器，一般有人在服务器上进行操控
  2. 被管理设备，一个软硬都包含的设备，设备上有一个或者多个被管理对象
  3. 每个被管理对象都有一个MIB(Management Information Base)，用于存储对象相关的参数
  4. 每个被管理设备上都有一个管理用户程序，用于和网络管理服务器通信和修改MIB
  5. 网络管理协议

5.7.2 SNMP (Simple Network Manangement Protocol)

一个网络管理协议是用来在网络管理服务器和管理用户程序之间传递消息的，SNMP就是一个网络管理服务器，SNMP消息有如下类型：

  1. 服务器主动联系用户程序，发送消息，用户程序接收消息，采取行动，并返回结果消息
  2. 被管理设备出现意外状况，MIB改变，用户程序主动联系服务器。通知服务其MIB改变

SNMP的具体消息类型有如下几类：

  1. Get*Request用于获取被管理设备MIB的信息
  2. SetRequest用于设置被管理设备的MIB
  3. InformRequest用于通知别的管理服务器一些接收不到的MIB信息
  4. Response用于用户程序回复管理服务器
  5. Trap用于用户程序通知服务器特定的事件发生了