酷应用

送书读书会丨网络拓扑的处理

百家作者：程序人生 2018-07-28 04:04:06

点击上方“程序人生”，选择“置顶公众号”

第一时间关注程序猿（媛）身边的故事

小贴士

文末有福利，有机会免费听分享、得赠书~

网络拓扑是网络工程师日常工作的基础。我们不论是在网络规划阶段、网络建设阶段还是在维护阶段都离不开网络拓扑。通常我们会使用一些画图工具来完成网络拓扑的绘制，比如用Microsoft Visio或Office PowerPoint来进行网络拓扑图的绘制。使用这样的工具可以画出非常漂亮的拓扑图，但是画出来的拓扑图并不方便转化为结构化的数据格式，我们也很难在这样的拓扑图上完成与拓扑相关的路径计算。

我们在本书的第2章中提到过DOT语言，这是一种用于描述网络拓扑的语言（拓扑数据结构的描述性语言）。本节将进一步的介绍DOT语言。另外，我们还将介绍一个Python的用于计算网络拓扑相关内容的模块。

12.4.1 描述一个网络拓扑

在数学的概念中，“图论”研究的是顶点和边所组成的图形。计算机网络拓扑是数学概念“图”的一个子集，因此计算机网络拓扑图也可以由节点（即顶点）和链路（即边）来进行定义和绘制。根据不同的划分维度，我们可以将网络拓扑图进行如下的划分。

1、无向图

在较为简单的场景中，我们通常用无向图来表示网络拓扑。在这样的拓扑图中，节点和节点之间的连接是没有方向的。这是因为在计算机网络中，通常链路都是双向并都能进行数据传递，此时我们并不太其实也无需关注链路的方向。这种图通常在物理连接拓扑图中最为常用。我们可以用DOT语言来这样表示：

graph site_a {
     core1 -- access1;
     core2 -- access2;
     core1 -- core2;
}

首先，我们使用关键字graph作为一个无向图的开始，后面site_a是这个无向图的名称。然后，使用大括号“{}”来描述所包含的节点。节点和节点之间的关系（边）使用 “--”双连字号来表示。每一行关系描述的末尾使用分号“;”。上面DOT语言描绘的拓扑图，我们可以用chrome浏览器加插件来查看，如图12-7所示。

12-7 无向图

2、有向图

计算机网络中流动的是数据流，而数据流其实是有很强的方向性。当需要在拓扑图中加入方向时我们就可以用有向图来进行表示。有向图定义的关键字为digraph，使用箭头来表示链路（节点与节点之间的互连关系）。代码如下：

digraph site_b {
     core1 [shape=box];
     core2 [shape=box];
     access1;
     access2;
     access1 -> core1 -> core2 -> access2;
}

我们可以在节点或边后面添加一些属性。上面的例子中定义了core1和core2的形状为方形。

同样，我们可以在chrome中查看这个代码对应的拓扑图，如图12-8所示。

12-8 有向图

3、多重图

多重边图（multi-grahp）也称为伪图（pseudograph），这是允许存在多重边的图，也就是两个节点之间存在多条边（链路）。

众所周知，计算机网络中节点与节点之间经常存在多条链路。有时，这些链路的属性还是不一样的，比如两个节点之间既存在10GE链路，又存在100GE链路。

这时，我们在DOT代码中只需要多次添加边就可以了。例如：

graph site_c {
      core1 -- core2 [label="10GE*8",color="red",fontsize=9.0];
      core1 -- core2 [label="100GE*2",color="blue",fontsize=9.0];
}

这里，我们在节点core1和core2之间添加了两条边，通过为边添加属性，我们可以知道第一条边代表8个10GE的链路，第二条边代表2个100GE链路。并且分别为这两条链路设置了不同的颜色。

现在，我们在浏览器中可以看到如下的拓扑，如图12-9所示。

12-9 多重图

更多关于DOT语言的描述请参考: https://graphviz.gitlab.io/documentation/。

在这一小节中介绍了如何用DOT语言来表示（绘制）一个网络拓扑。在接下来的两节中，我们将介绍如何用networkx这个模块对拓扑进行路径的计算。

12.4.2 最短路径的计算

在IP网络中，IGP最常用的有OSPF和ISIS两种协议，如何使用这两种协议对于网络工程师而言应该不会陌生。这两个协议一个重要的共同点就是：它们都是基于链路状态的路由协议。基于链路状态的路由协议在进行路由表计算时都是采用SPF（Shortest Path First，最短路径优先）算法。在日常的工作中，网络工程师通常不需要自己使用SPF算法来计算路由器上的路由表条目，因为网络设备都会准确无误的计算其自身的路由信息。但我们在做网络规划和网络运维时经常需要对网络进行路径分析，这就需要我们做大量的拓扑仿真计算，这些计算大部分都是基于SPF算法。

在Python的开源模块中，networkx是一个功能丰富用于拓扑计算的模块。现在的软件版本为2.0，后续的内容介绍将会基于这个版本。和其他模块的介绍一样我们还是从模块的安装开始。

对于Python模块我们还是推荐使用pip进行软件的安装。

$ pip install networkx
Collecting networkx
  Using cached networkx-2.0.zip
Collecting decorator>=4.1.0 (from networkx)
  Using cached decorator-4.1.2-py2.py3-none-any.whl
Installing collected packages: decorator, networkx
  Running setup.py install for networkx ... done
Successfully installed decorator-4.1.2 networkx-2.0

1、用networkx描述拓扑

为了计算网络的路径，我们需要先输入网络的拓扑关系，有了网络的拓扑关系才可以进行基于路径拓扑的计算。在网络拓扑的描述上，networkx和DOT语言非常类似，也分为三个部分：节点、边以及属性。在networkx中，节点被称为node，边是链路被称为edge。

#!/usr/bin/env python
#coding:utf-8
import networkx as nx

nodes = ["BJ", "SH", "GZ", "HZ","NJ","WH","XA"]
G = nx.Graph()
for node in nodes:
    G.add_node(node)

edges = [("BJ", "SH"),
         ("BJ", "GZ"),
         ("SH", "GZ"),
         ("HZ", "SH"),
         ("HZ", "GZ"),
         ("NJ", "SH"),
         ("NJ", "BJ"),
         ("WH", "SH"),
         ("WH", "BJ"),
         ("XA", "GZ"),
         ("XA", "BJ"),]
G.add_edges_from(edges)

上面的代码只是添加了一个拓扑。和DOT一样，networkx对拓扑也分为有向图和无向图，单重和多重图。在上面的例子中用nx.Graph()初始化了一个无向的单重图。如果要创建有向图需要使用nx.DiGraph()，多重图为nx.MultiGraph()，有向多重图为nx.MultiDiGraph()。

后续的代码就是使用了两个方法来添加节点（node）和边（edge）。

这个拓扑图可以参考12-10。

12-10 拓扑图示意图

4、最简单的路径计算

在OSPF和ISIS协议中，我们通常基于链路的cost来计算最短路径。在上面的例子中，我们可以假设所有链路的cost值都为1。我们先计算一下节点WH和HZ之间的最短路径是什么。这里我们需要用到networkx自带的一些算法来进行计算。这里我们使用shortest_path方法来计算两个节点之间的最短路径。

>>> nx.shortest_path(G,"WH","HZ")
['WH', 'SH', 'HZ']

注意：这里使用了Python的交互模式，这段代码的背景就是上一个例子中的代码内容。

5、给链路添加cost

在拓扑定义的时候可以添加cost，在networkx中默认使用weight作为cost属性。

#!/usr/bin/env python
#coding:utf-8
import networkx as nx

nodes = ["BJ", "SH", "GZ", "HZ","NJ","WH","XA"]
G = nx.Graph()
for node in nodes:
    G.add_node(node)

edges = [("BJ", "SH",1200),
         ("BJ", "GZ",2500),
         ("SH", "GZ",1300),
         ("HZ", "SH",280),
         ("HZ", "GZ",1000),
         ("NJ", "SH",300),
         ("NJ", "BJ",900),
         ("WH", "SH",800),
         ("WH", "BJ",850),
         ("XA", "GZ",2600),
         ("XA", "BJ",2000),]
G.add_weighted_edges_from(edges)

这个拓扑的链接关系和上一个例子是一样的，只是在连接关系上添加了cost值（其值是笔者基于距离的值，不过这个距离并不是严格依照地图的距离，而是做了一些简单修改后的值）。

现在我们再用刚才的算法计算一下“XA”到“HZ”之间的最短路径。

>>> nx.shortest_path(G,"XA","HZ")
['XA', 'GZ', 'HZ']

在默认情况下，方法shortest_path并不会考虑cost值的大小情况。还是基于跳数来计算。使用，我们可以看到XA到HZ是经过GZ节点的。

我们修改shortest_path的参数。

>>> nx.shortest_path(G,"XA","HZ",weight="weight")
['XA', 'BJ', 'SH', 'HZ']

修改参数后shortest_path使用了weight值作为cost进行计算，计算的最短路径是weight值的和总数最小的路径。

除了一开始设置的链路cost值之外，还可以单独修改某条链路的cost值。

比如现在假设“HZ”和“SH”之间的链路发生了故障，我们可以修改这条链路的cost为一个很大的值，假设为1000000。然后再计算一次“XA”到“HZ”之间的最短路径。

>>> G["HZ"]["SH"]["weight"]=1000000
>>> nx.shortest_path(G,"XA","HZ",weight="weight")
['XA', 'GZ', 'HZ']

经过修改后，XA到HZ的最短路径发生了变化，不再经过BJ和SH节点。

6、等价路径的计算

实际环境中，我们的网络中存在大量的等价路径，这时查找出所有的等价路径是很有必要的。在上面的这个拓扑中，如何查找出WH到GZ两节点之间的所有等价路径呢。

>>> list(nx.all_shortest_paths(G, "WH", "GZ",weight=None))
[['WH', 'BJ', 'GZ'], ['WH', 'SH', 'GZ']]

这里我们用了一个新的方法是all_shortest_paths，这个方法会返回一个生成器对象。我们可以用list()来遍历出所有的值。在上面的例子中，我们可以找到两条等价路径（并没有考虑链路cost值，只考虑了跳数）。

networkx中还提供了很多关于最短路径的方法，读者可以参考以下的链接：

https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html。

12.4.3 可用路径的计算

由于IP网络的IGP大多是基于最短路径的，因此在大部分情况下，我们只需要和IGP一样计算出最短路径就可以了。毕竟基于最短路径的流量模型是最为经济的，在大多数情况下，通过动态修改链路的cost值可以达到最优的流量分配。

当IP网络有了流量工程之类的工具，无论是通过RSVP-TE还是Segment Routing TE（SRTE）来部署流量的转发路径，在这之前通常都需要先获得流量的可用路径。而这些可用路径除了最短路径以外，还有那些全程路径cost值相对大一些的路径，我们可以称这些路径为次优路径或次次优路径。在networkx也有这样的算法可供大家使用。

1、获得可用路径

首先，可用路径是那些不存在节点重复的路径。假设我们有A、B、C三个节点，这三个节点形成了一个三角形的拓扑，见图12-11。在这个拓扑中，节点A和C之间的可用路径有两条：一条是A到C（我们这里记录为：A→C），另一条是A到B再到C(记录为：A→B→C )。这里不存在第三条可用路径，路径A→B→A→C或A→B→A→B→C这样的路径并不是我们这里所说的可用路径，因为在这两个路径中，对于同一个节点出现了重复。

12-11 三角形拓扑

现在我们还是基于12.4.2节中的拓扑（见图12-10）来获取XA和HZ之间的所有可用路径。

>>> for path in nx.all_simple_paths(G, "XA", "HZ"):
...     print(path)
...
['XA', 'BJ', 'NJ', 'SH', 'GZ', 'HZ']
['XA', 'BJ', 'NJ', 'SH', 'HZ']
['XA', 'BJ', 'WH', 'SH', 'GZ', 'HZ']
['XA', 'BJ', 'WH', 'SH', 'HZ']
['XA', 'BJ', 'GZ', 'HZ']
['XA', 'BJ', 'GZ', 'SH', 'HZ']
['XA', 'BJ', 'SH', 'GZ', 'HZ']
['XA', 'BJ', 'SH', 'HZ']
['XA', 'GZ', 'HZ']
['XA', 'GZ', 'BJ', 'NJ', 'SH', 'HZ']
['XA', 'GZ', 'BJ', 'WH', 'SH', 'HZ']
['XA', 'GZ', 'BJ', 'SH', 'HZ']
['XA', 'GZ', 'SH', 'HZ']

我们可以看到，从XA和HZ之间一共找到了13条可用路径。

2、获得部分可用路径

在刚才的例子中，我们的可用路径其实并不是很多，只有13条。但是当我们网络中的链路稍多一些时，可用路径就会变得非常的多。对于一个全互联的网络（即每两个节点之间都有直连的链路），任意两点之间的可用路径的数量值将为(n-2)!条。其值为节点数-2后的阶乘。如果是20个节点，那么其任意两点之间的可用路径数量将为18！（18的阶乘）= 6402 3737 0572 8000，这是一个非常庞大的数字。如果我们遍历这么多的可用路径，再快的计算机也许都无法在很短的时间内完成。

因此，我们希望获得的可用路径只是那些比最短路径稍微长一点的路径，这样我们就可以获得那些次优路径。我们可以修改上面例子中的代码为：

>>> for path in nx.all_simple_paths(G, "XA", "HZ", 3):
...     print(path)
...
['XA', 'BJ', 'GZ', 'HZ']
['XA', 'BJ', 'SH', 'HZ']
['XA', 'GZ', 'HZ']
['XA', 'GZ', 'SH', 'HZ']

这里代码的含义是，我们希望获得从XA到HZ且经过的节点数量最多为3（不包含起始节点）的所有路径。这次，我们获得的可用路径只有4条。

3、基于链路cost计算的可用路径

我们可以看到上面是基于网络节点的跳数来计算可用路径的，并不是基于链路的cost值来获取。大部分时候基于网络节点的跳数来计算可用路径是可以满足需要，但我们还是希望能基于链路的cost值来获取更为有效更为经济的可用路径。networkx也提供了相应的算法可供使用。我们先看一下如下的一段代码：

>>> def get_path_weight(G, path):
...     _weight = 0
...     for edge in nx.utils.pairwise(path):
...         _weight += G.edges[edge[0],edge[1]]["weight"]
...     return _weight
...
>>> for path in  nx.shortest_simple_paths(G, "XA", "HZ",weight="weight"):
...     print(path, get_path_weight(G, path))
...
['XA', 'BJ', 'SH', 'HZ'] 3480
['XA', 'BJ', 'NJ', 'SH', 'HZ'] 3480
['XA', 'GZ', 'HZ'] 3600
['XA', 'BJ', 'WH', 'SH', 'HZ'] 3930
['XA', 'GZ', 'SH', 'HZ'] 4180
['XA', 'BJ', 'GZ', 'HZ'] 5500
['XA', 'BJ', 'GZ', 'SH', 'HZ'] 6080
['XA', 'GZ', 'BJ', 'SH', 'HZ'] 6580
['XA', 'GZ', 'BJ', 'NJ', 'SH', 'HZ'] 6580
['XA', 'GZ', 'BJ', 'WH', 'SH', 'HZ'] 7030

我们在上面的代码中先定义了一个函数，这个函数是用来计算一条path路径的总cost（networkx中通常用weight参数进行表示）值。

方法shortest_simple_paths会从最小cost的路径开始依次给出可用路径。由于这个方法返回的是一个生成器，因此我们可以根据需求随时停止可用路径的查找。

假设，我们现在想获得4条可用路径。那么我们的代码可以这么来实现：

>>> from itertools import count
>>> counter = count(1)
>>> for c, path in zip(counter, nx.shortest_simple_paths(G, "XA", "HZ", weight="weight")):
...     if c > 4:
...         break
...     print(path, get_path_weight(G, path))
...
['XA', 'BJ', 'SH', 'HZ'] 3480
['XA', 'BJ', 'NJ', 'SH', 'HZ'] 3480
['XA', 'GZ', 'HZ'] 3600
['XA', 'BJ', 'WH', 'SH', 'HZ'] 3930