本文旨在对用一个连续的思路对网络知识做一个梳理。包含了：集线器、交换机、路由器等元器件出现的原因；环型、星型、多互联型、总线型、以及树型拓扑的适用场景；Dijstra算法、生成树协议、RIP、OSPF相关原理；二层选路、三层选路相关思考；二层组播和三层组播以及相关协议。

本文会用推演的方式，从两台主机直连开始，逐步引出并讨论以上内容，推演出生产可用的网络架构。因单篇博客的篇幅限制，本文会拆分成两篇博客进行讲解。

1 需要先了解的知识

在开始从简到繁讨论网络之前，我们需要先了解有哪些比较通用的数据包，各种数据包长什么样，以及二层到四层封装的层级。对各种数据链路层、网络层协议熟悉的，有相应基础的读者可以简要浏览后跳到下一章节；之前没有了解过这些的读者，可以仔细看一看这些数据包长什么样，留下一个大概的印象，但不必拘泥于了解每一个字段的意思。本章的内容主要参考了《TCP/IP详解 卷一》，有兴趣的读者可以点此链接在线阅读。

1.1 通用数据包格式

首先明确TCP/IP协议世界中的数据包(package)大概长什么，以及二层、三层、四层之间的关系。我们平时所说的二层，三层，四层源自OSI七层模型；二层，三层，四层分别对应OSI七层模型的数据链路层，网络层，传输层。发送应用数据的时候，这些层的信息会被逐层地加到发送数据上，形成一个洋葱式的嵌套结构，(在不考虑物理层也就是一层的情况下)，二层的信息会被加到应用数据的最外层，二层往内再是三层和四层。每一层协议的都会将更内层的内容看作本层的数据区，所以二层协议的的数据区会包含三层协议头部、四层协议头部和应用数据，三层协议的数据去会包含四层协议头部和应用数据。从二层到四层每层都会有多种协议，一般来说我们说的数据包都是指二层采用Ethernet(以太网)封装，三层采用ip封装，四层采用TCP/UDP封装的数据包。下图展示了数据包的通用格式，其中三层头部和四层头部都可以为无，CRC为校验和；二层的校验和一般在数据包尾部，三层和四层的校验和则放在对应头部里。

1.2 二层协议的数据格式

二层协议工作在数据链路层，经过二层封装的数据，才初步具有了传达到其他主机的能力。二层的协议按笔者理解主要分成两类：一类是用于一对多局域网；一类是单对单局域网络。

1.2.1 一对多局域网

一对多的主要指以太网，令牌环网这样的网络，其中的以太网，如果大学上过计算机网络课，应该会听过CSMA/CD，中文名是带冲突检测的载波侦听多路访问(十分绕口)，这个是10M以太网的基础之一，下面2.x节讨论的网络都是基于以太网。在此我们无许了解CSMA/CD的详细，只需要了解一对多网络是在一台主机发送数据，其他主机都能接收到数据，在这种情况下，如果需要知道从哪发的包，向哪儿发的包，就得有源地址和目的地址进行标记。所以在下面两种一对多局域网用的封装格式「以太网封装」和「802.3封装」中，都会有48位目的地址，48位源地址，也就是我们俗称的物理地址或mac地址。这两种封装中，以太网封装为主流，但802.3封装的包也可能被接收到。下图为二层的以太网协议封装和802.3协议封装格式，其中IP数据报为三层数据，PAD为填充(两种封装均要求整个数据包大小最为64-1518个字节)。

1.2.2 一对一局域网

如果两台主机只是用一条串行线路直接连接起来，那这条线路上除了这两台主机，就不会有其他主机发送消息了。这种情况下，源目地址就无用了，至于为何无用，打个比方，一对多的情况就好像写信送邮局投递，想要对方收到并回信，信上必须标注收件人和发件人；而单对单的情况则是我写完了信直接拿给对方，对方知道我是谁，也会直接把信回给我，此时写不写收件人和发件人便不重要了。所以用于单对单网络的封装方式中，都不会出现源目地址，所以这三种封装通常用于串口。其中「SLIP」是最简单的封装，「CSLIP」会对内部的IP/TCP头部进行压缩(主要思想就是利用两机直连通信IP/TCP头部有些字段不会发生变化，从而对头部进行精简，参考此链接)，「PPP」为SLIP的终极加强版(带冗余校验，支持CSLIP类似的IP/TCP头部压缩)。下图为二层的SLIP、CSLIP、PPP协议封装格式。

1.3 三层封装的数据格式

三层协议工作在网络层，经过三层封装的数据，才具有了传达到互联网所有其他主机的能力。三层协议的代表是ip协议，类似于二层的以太网协议，该协议的封装中也会有源目地址，这个一般我们称之为ip地址。理论上通过物理地址可以标识唯一的主机，那么通信的时候只要知道了源物理地址和目物理地址，实际上就可以标识到唯一的源主机和目主机，但为何有了物理地址还需要ip地址呢？主要是物理地址存在以下两种缺陷：

• 物理地址分布杂乱无章，难有逻辑上的连续关系。
• 物理地址一般都直接烧录在了硬件中，无法软件修改。

不连续地址映射到连续地址的思想

物理地址为何分布杂乱无章，可以自行去了解，至于ip地址如何解决了杂乱无章的问题，还请往下阅读。在局域网中，随着主机规模的增加，为了方便管理，我们更希望得到一片连续的地址或编号，用来标识主机，比如像1-1000，2000-3000，这要比ab-33-12-98-19-fa、ab-33-12-98-11-fa、cb-33-12-98-19-fa...这样散乱的物理地址要方便管理得多，更好编程也更好记忆。将不连续的的物理地址映射成虚拟的连续地址，学过linux的读者看到这里可能马上就会联想到页表机制，是的，这两者是同一种思想的产物，页表将不连续的内存物理地址映射成了虚拟的连续物理地址，同一片局域网下的不同物理地址自然也可以通过某个表(arp表)映射成连续的ip地址，从此，我们便可以在局域网中用ip地址指代某台设备。ip地址是一个32位int数，可以转换成易于人工读的点分十进制字符如"192.168.1.1"，两者的转换可以参考笔者之前的文章《防火墙自动化(一) 防火墙的配置解析》的2.1节

下图为三层常用的「IP」协议封装格式。其中数据部分可以为四层数据或工作在ip附属协议(ICMP/IGMP)的数据)。

1.4 四层封装的数据格式

四层协议工作在传输层，经过四层封装的数据，才具有了传达到互联网其他主机上某特定网络应用的能力。三层协议可以确保数据传输到对应的主机或主机组，四层协议则是定位到主机或主机组上的某个应用。我们常常听到套接字(Socket)这个概念，其定义是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象，实际上套接字就是一个struct/class/object的instance，里面最关键的信息是三层IP地址和四层端口，不同应用/进程在同一主机上使用的是不同端口，我们通过套接字定位到某台主机的某个网络应用，从而实现向特定网络应用发送数据的目的。

由于四层封装跟网络应用息息相关，谈到应用涉及到的内容会相当多，所以此处暂不展开，仅列出四层常用的两种协议TCP和UDP的封装格式。TCP的相关知识可以参考《TCP/IP详解 卷一》的第18-24章，UDP的相关知识可以参考《TCP/IP详解 卷一》的第11章。

1.5 其他常用协议数据包格式

1.5.1 VXLAN

2 关于网络的一次推演

此处为本文的主题，笔者将从各种拓扑开始，一直讨论到使用各种路由协议的网络。默认使用的网络为以太网。

2.1 两台主机互联

网络的魅力在于将不同的主机联系在一起，我们从最简单的两台主机的情况开始讨论。将两台主机当成两个城市，现在只有这两个城市，如果要互相运输物资，路该怎么修？答案是修一条直达的线路，比如广州到深圳之间修一条直通的高铁。如图，下面这两台主机，它们可以通过串口，RJ45网口(后面将这些口统一称为接口)直接进行连接，并在二层上使用SLIP/CSLIP/PPP/Ethernet/802.3，三层上使用IP，四层上使用TCP/IP进行通信，当然，三层和四层的协议都是可选的，例如我要发送arp请求，则不需要三层和四层协议部分。我们一般把下面这种网络拓扑称之为点对点(Point to Point)拓扑。

让我们来看看双机直连时一台主机时如何向另一台主机发送数据包的，下图中，左边为发送方，右边为接收方。一般情况下，左边发送的应用数据，需要经过四层封装、三层封装、和二层封装后，再发送给右边；右边在接收到整个包后，需要逐层解封，其中二层和三层的解封一般发生在网卡，网卡会丢弃不属于发送给自己的报文，四层的解封一般在操作系统的内核空间；最终右边将解封好的应用数据投递给对应的应用。

2.2 多台主机互联

"亚当"和"夏娃"毕竟只有两台主机，当网络中出现第三台，第四台，乃至第N台主机的时候，我们应该怎么去建立它们之间的连接？换句话说，现在有n个城市(或地点)，我们应该怎么“修路”让他们可以互相“运输物资”？让我们参考实际生活，试图从中获得答案。

2.2.1 总线型(bus)拓扑

首先，笔者在百度地图上随机找了一处地方，如下图所示。

上图中有一条主干道，和四条支线，属于最常见的修路方式。假如这四条支线末端各是一个地点，则地点之间互相运输物资则需要通过：本地点支线-主干道-目标地点支线。简单地，我们可以参考上面的形式搭建我们的主机之间的连接，从而得到总线型(bus)拓扑，如下图(引用自此链接)。

2.2.2 环型(ring)拓扑

然后，笔者找到广州大学城的一张地图截图，图中标出的路线为广州大学城的内环。

如上图所示，通过内环这样一个环状线路，我们可以从中山大学跑到广东外语外贸大学，也可以从广东中医药大学跑到广东省中医院。如果有游历广州大学城中所有高校的需求，实际上通过内环这一条线路便可到达各所高校。参考此思路，我们也可以用环来解决多主机相连的问题，只要将它们全部串起来形成一个环即可得到环型(ring)拓扑，如下图所示。

2.2.3 多互联(mesh)拓扑

最后，笔者找出来一张普通的航班线路图。如下图所示。

从图中可以看到，中国的一线城市之间，比如说北京、上海、广州、深圳，都有互相飞的航班，而部分二三线城市之间则可能无直达航班，需要先飞到主要城市再进行转机。参照这个航班路线图，我们把图中的每个城市看成一台主机，每条航线看成网络线路，则可以形成多互联(mesh)拓扑。特殊地，假如未来的某天，每个城市和其他城市都有直飞线路，则可称之为全互联拓扑(full-mesh)，对应数据结构中的完全图，非全互联则可对应数据结构中的非完全图。在全互联拓扑的情况下，假如有n台主机，则会有C(2 n)条直连线路，每台主机需要n-1个接口，共n(n-1)个接口，如下即为一个全互联拓扑的示例。

2.3 多主机互联最通用的星型(star)拓扑

关于星型拓扑是什么，以及为什么它是最通用的，笔者想将之分成下面三个问题解释

• 环型拓扑的优缺点，为什么多主机互联最通用的拓扑不是它？
• 多互联拓扑的优缺点，为什么多主机互联最通用的拓扑不是它？
• 什么是星型拓扑？它和总线型网络的关系是什么？
  最终会得出一个结论，多主机互联时最宜用星型拓扑。

2.3.1 环型拓扑的优缺点

缺点之前先说优点，优点是用到的连接线缆是最少的(相比总线型、多互联型)。假如有n台主机，则只需要n条线和2n个接口即可完成环状拓扑。缺点也是连接线缆最少带来的。比如说故障诊断困难，环上的任一节点出现故障都会引起全网的故障，所以对故障很难进行定位；然后调整网络比较困难，例如加节点或撤出节点都比较困难(需要断掉整个网络)。如下图，任意一条线发生中断，整个网络都会挂掉。另外，环状网络的传输会比较慢，参照一下上面的大学城内环吧，要到达一台地点可能要绕很多个地点，(加上还要避免数据传输冲突)速度相比总线型、互联型会较慢，目前环形拓扑的代表令牌环网最大的传输速率为100Mbps，属于已被取代的网络(21世纪比较少见)。

2.3.2 多互联拓扑的优缺点

互联拓扑和环形相反，需要的连接线缆是最多的(缺点)。假如有n台主机，如果采取全互联的方式，则需要n(n-1)/2条连接线缆，与此同时，还需要每台主机都有n-1个网口，假如现在有20台主机，则每台主机需要19个网口，这样每台主机上都会出现一排密密麻麻的接口，共需要19n个接口。这样一来我们的主机变成了“插座”，接口反倒取代其他元件成为了“大部队”。优缺同源，优点是线路多带来的冗余度高，可靠性高，任一线路中断影响都非常有限。如下图，任意一条线发生中断，只影响两台主机之间的通信，不会影响到其他通信。多互联拓扑在网络中有广泛的应用(在交换机之间使用)，但在主机互联时比较少用，一旦主机的规模稍大一点，所有主机就会面临上面的“插座”危机。

2.3.3 星型拓扑

接下来是引入星型拓扑。在讲星型拓扑之前我们先偏个题，讲讲总线型网络的理解。我们在理解总线型网络发送数据的时候，不宜将网络线路之看成普通的路，更宜将之看成“河道”，而发送数据更宜理解为“放水”。如下图，一台主机“放水”(发送数据)，其他主机都会收到“水”(接收到数据)。这是总线型网络的重要特点之一，总线型网络是10M以太网的载体，所以10M以太网也会拥有这种这种广播的特点(这点是我们后面解决的重点)。另外还请读者自行回忆计算机网络知识，如果同时有多台主机同时“放水”，水是不是就变混了？10M以太网是怎么去解决这个问题的？看到这里是否对以太网的CSMA/CD(带冲突检测的载波侦听多路访问)有了新的认识？

言归正传。星型网络是在总线网络上做了一点小的变动，用一台专门的主机作为中转，但本质上是总线网络的升级版。总线型解决多主机互联的思想是修一条“主干道”，其他主线通过“支线”接入“主干道”，而星型网络则是将“主干道”换成了一台新的主机，其他主机通过“支线”接入新的主机。想象一下，某个小区，修了一个广场，所有楼都有小路接入这个广场，小区内所有路都经过此广场；如果把广场当成“主干路”，便是我们说的总线型；如果把广场当成一个地点，便是我们说的星型。星型是将“主干道”浓缩成一台新主机的总线型，通过这台新主机，可以提供更多其他功能解决其他问题(后面会提到)。如下图所示，即为一个星型(star)拓扑。星型拓扑是多主机互联最常见的拓扑；采取星型拓扑，假如有n台主机，则需要n条连接线缆，连接线缆数量同环型一致的同时，其中某条线缆中断只会影响到某台主机和其他主机的通信。

让我们来看看使用了集线器的情况，发送的数据包是如何被处理的，下图中为Host C向Host A发送数据的完整流程。Host C上的数据，首先还是需要逐层进行封装，封装的过程同2.1，然后将数据发送出去；数据到达集线器后，集线器不会做解包处理，只会将数据从非接收接口外的其他全部接口发送出去(即广播，泛洪)；接收到的主机会逐层解包，看接收主机是否是自己，如果不是则会将包丢弃，如果是则会将数据复制到对应的内核空间；最终Host A接收到应用数据，Host B丢弃数据包。

2.5 多主机互联-使用交换机

集线器在发送数据包时只能使用广播，这无疑让非接收方的主机(如2.4节图中的Host B)处理(判断和丢弃)了太多无关数据包。最理想的方式应该是数据包只发到发送方指定的主机，指定的主机主机并非局限于某一台，可以是一台、多台或者全部主机，这里的关键在于发送方能否指定。 为了解决将数据包只发到发送方指定的主机这个问题，集线器的升级版本-交换机被开发出来。交换机在集线器的基础上，

• 增加了对二层地址(使用ethernet封装时，又叫做物理地址或mac地址)的缓存
• 增加了网络隔离功能。

此类设备一直沿用至今，集线器网络可以升级成下面的交换机网络。

2.5.1 二层地址缓存

二层地址的缓存，即交换机会对二层地址进行缓存，将之存放在一个叫做mac地址表的表中，一般将这个过程也称作mac地址学习。网络初始时mac地址表中是没有数据的，所以在转发前面的包时，还是得使用类似集线器这种广播的方式，数据包会从非接受接口的所有接口发出去；但由于交换机会自动记录哪个mac地址来自于哪个接口，将mac地址表(mac地址到接口的映射)填充起来，等mac地址表中有了对应的表项，就可以将数据只发送到目标主机了，这时候只会从特定的接口发出数据包。二层地址的缓存，提高了整体网络的运行效率以及减少了大量重复的数据包。下图展示了一个已有二层地址缓存的交换机是如何处理数据包的，Host C发向Host A的包到达交换机后，交换机会查询缓存的mac地址表，然后将包只转发给Host A。

2.5.2 网络隔离

网络隔离，(笔者认为)初始时解决的也是如何将数据包只发到发送方指定的主机的问题，但是解决思路和二层地址缓存有点区别，所以还有其他衍生用途。如果把交换机/集线器当成一个传信点，向外传递情报使用的是“飞鸽传书”，集线器就是收到一条情报往四面八方都“飞鸽”，交换机就是可以缩小范围往指定的方向“飞鸽”，但如何做到只往指定方向“飞鸽”呢？二层地址缓存的思路是记下“飞鸽”来的方向和情报的发件人比如小A，下次如果有给小A的情报，就从前面的方向发出去；网络隔离的思路则是分组，比如东边和西边是一组，南边和北边是一组，从东边收到的情报只往同组的西边发，南边收到的情报只往同组的北边发。二层地址缓存可以自行学习，网络隔离则依赖于人工的前期设置，当“飞鸽”的人变多时，二层地址缓存越来越好用，但网络隔离就很难支撑一对一的转发了，但其分组的思想还是保留了下来，用作划分局域网，隔离广播域。

而如何实现网络隔离？交换机提供了一种为VLAN（Virtual Local Area Network)的技术，这个技术基于802.1q协议(又称之为dot1q协议)，本质上是将数据包的二层头部拆出来，插入一个名为vlan tag的标记，用来标记不同的虚拟本地网络。以下为802.1q封装报文格式，其中vlan tag共有12位，能支持2^12=4096个vlan。

交换机和主机之间的接口一般会配置成所谓的access xxx(vlan号)模式，这个模式有以下意义：

• 这个接口进来的数据包都会被打上xxx(vlan号)的标签(vlan tag)；
• 不带xxx标签的数据包不会从此接口发出；
• 从这个接口出去的数据都会被拆除标签。
  access口一般用于连接host，host的网卡一般不能识别带vlan tag的包，所以要拆除vlan tag，保证下面的host可以识别。当然我们可以通过技术手段让host可以识别802.1q封装报文，从而发起网络攻击如vlan跳跃攻击。下面提供了Host C访问Host A时的处理流程，两者属于同一vlan(vlan 100)，可以互相访问。

2.6 两台交换机互联

一台交换机下面能连的主机数是有限的(现在通用的是48口交换机，以前还有24口交换机)，如果想要扩大网络规模，则免不了将交换机连接在一起，让我们先来讨论两台交换机连接在一起的情况。

2.6.1 两台交换机-使用vlan

当使用两台交换机直连时，如果使用的是48口的交换机，则最多可以承载48*2=96台主机。当网络中有96台主机时，如果有隔离的需求，我们可以使用1.5.2中提到的vlan，把这些主机划分到多个分组里。注意此处交换机和交换机之间的接口一般会配置成所谓的trunk模式(开启802.1Q中继功能)，这个模式的意义是：

• 允许任何携带vlan tag的包通过
• 从这个接口进出的包不会被拆除vlan tag
• 没有vlan tag的包经过时会被被自动插入native vlan tag(取决于交换机，有的不插入)

native vlan tag使用的vlan号是trunk口默认使用的vlan号，不同品牌的交换机可能存在差异。在trunk模式的支持下，不同交换机下面的主机可以被划入同一个虚拟局域网，只要vlan tag中的值相同，就会被识别同一个局域网(vlan)的数据。下图展示了两台交换机直连的情况下，交换机之间的接口被配置成Trunk模式，Host A是如何向Host D发送数据的。

还有一个笔者找到的更棒的例子，来自此链接。

2.6.1.1 vlan跳跃攻击(选读)

获取流量-主机和交换机之间通过DTP协商成Trunk

交换机接口上的Trunk模式可以被人工指定，两台交换机之间的接口配置trunk模式还是比较快捷的。但交换机数量比较多的时候，手动配置trunk比较麻烦。在这个基础上产生了DTP协议，只要交换机之间连接起来，开机之后交换机会发送trunk的协商包进行协商，从而动态的创建trunk，这给网络的配置提供了便利。DTP一共有4种模式：Dynamic desirable（主动希望成为trunk），Dynamic auto（成不成为trunk无所谓） Trunk/on(强制开启trunk)，Access/off（强制关闭trunk）。交换机的每个接口都可以被预配置成这4种模式之一，两台交换机之间的两个接口共有如下 $4*4=16$ 种情况，它们可以通过DTP协商消息协商模式。

DTP提供了接入的便利，但同时带来了隐患-VLAN跳跃攻击。在VLAN跳跃攻击中，黑客自行构造数据包，冒充成另一个交换机发送虚假的DTP协商消息，宣布它想成为中继(模拟为DTP Trunk/on模式的接口)；真实的交换机收到这个DTP消息后，以为它应当启用802.1Q中继功能，而一旦中继功能被启用，通过所有VLAN的信息流就会发送到黑客的计算机上。通过这种方式，黑客可以获得所有VLAN流量的“副本”，进而分析这些流量获得更多信息。

发送流量-封装多Tag数据包

802.1q封装会在二层头部和IP数据报之间插入一个Vlan tag，从而达到划分虚拟局域网的作用。如果在后面的IP数据报的最前面，再人工构造一个(或多个)12位的vlan tag，会发生什么？

首先要明确这是被802.1q协议允许的，后面的vlan tag会被交换机视作IP数据报的一部分，你可以利用这种特性发送恶意流量，也可以利用这种特性实现PPPOE、VXLAN类似的overlay功能。

然后，在使用双tag(或多tag)数据包进行非法数据的发送时，一般被称为双tag帧攻击。

最后，所谓的双tag帧攻击一般通过两个步骤完成(但大部分百度到的例子都称不上双tag帧攻击)：1)封装一个具有2个tag标签的数据帧，外层的tag id是Trunk链路的native vlan的pvid，内部的tag id是要攻击的主机所在的vlan id. 2)当具有双tag的帧从交换机trunk接口转发出去时,外层的tag id是Trunk链路的native vlan的 pvid，会剥离掉外层的一个tag,进而将具有攻击性的数据发送。如下图所示。

2.6.2 两台交换机-简化结构

让我们把主机隐去，简化结构方便后面的讨论。如下，各位读者仔细一看，是否和1.1中两主机直连(点对点拓扑)的情况有点像？是的，太阳底下没有新鲜事，两交换机直连又是另一个两个地点之间“修路”的故事。后面的推演将以此简化结构进行展开。

2.6.3 两台交换机-链路捆绑

当两台交换机直连时，如果下面都满载了主机，可能会出现交换机之间一台线路的带宽不够用的情况，如何去解决这个问题？最简单的思路是两台交换机之间加多一条线，但直接加一条线可能会出现环路，如下图所示，流量可能会在两台交换机之间“鬼打墙”，往复循环(防环是后面介绍的各种路由算法的重要组成部分)。

为了解决环路+带宽不够(单纯的环路可以通过stp，rstp协议来解决)，出现了链路捆绑技术，它可以将多条线路通过绑定的方式，形成逻辑上的一条线路，并且获得n(线路条数)倍的带宽(忽略链路捆绑协议消息发送带来的带宽损耗)。链路捆绑技术，又目前已被广泛地应用在一些网络连接中。通过将多条链路捆绑在一起提高了网络系统的带宽，并且为网络系统提供了高可用性，负载分担等功能。链路捆绑一般用下面的红圈表示。

2.7 多交换机互联

参考2.6.2的简化结构将所有主机隐去，以及2.2给出的三种多主机拓扑组织方式-总线型、环型、多互联型。我们可以得到多交换机的三种拓扑组织方式。

在这三种拓扑组织方式中，如果要挑选用于生产的组织方式，环型是最先出局的，原因同2.3.1，任一线路损坏整个网络都运行不了(令牌环网)且运行速度最慢；多互联会被保留下来，因为该组织方式的稳定性最好，冗余最多；总线型不会直接使用，但会在下文中升级成星型继续存在于网络。实际上，现有的交换机互联网络一般都是星型拓扑和多互联拓扑的结合。

2.8 多交换机互联-星型拓扑

仿照2.3.3，在一个三交换机的总线型网络中，我们增加一台交换机，将总线浓缩成一台新的交换机(一般称为汇聚交换机)，多交换机也可以采取2.3.3提供的星型拓扑的方式组网。如下图所示。

2.9 多交换机互联-转化成树型拓扑

从前面的内容我们可以导出结论，多交换机组网最常用的拓扑是多互联拓扑和星型拓扑。

多互联拓扑和星型拓扑的最大区别在于，星型拓扑不存在环路，但多互联一般存在环路。

而如果学习过数据结构/图论，应该有了解图(Graph)和树(Tree)分别是什么，以及它们之间的关系。(树和图之间更多的区别请参照此链接)

• 图是一种具有一种或多种方法来从任何点A到达任何其他点B的系统。
• 树是一种特殊的图，它永远不会有多路径，从A到B只有一种路径。并且树具有层级结构。
• 任意无向图可以通过去掉某些边的方式转化成树。图是可能出现环路的，而树是无环结构。

任意网络拓扑都可以算作无向连通图，上面多互联拓扑和星型拓扑都可以是无向连通图。任意无向连通图都可以通过最生成树算法删去不必要的边转化成树。通常的生成树算法有：最小生成树算[Prim算法(加点法)和Kruskal算法(加边法)，最短路径树算法Dijstra算法。

在2.8图的的基础上，为了方便我们的查阅理解，我们做一个简单的翻转，如下图所示，将星状网络上方的交换机全部翻转到下面，则上面的星状网络可以等价地画成下面两层树状结构形式。这就是我们所说的树型(Tree)拓扑。

但是否2.8图只能转化成以上的这种树状结构呢？答案是否定的。树是有不同层级结构的，我们以不同的交换机为树根(root)，得到的树是不一样的。如下，同样的星型拓扑可以转化成4种树型拓扑。

星型拓扑不存在环路，所以在转化成树状拓扑的时候不需要去掉多余的连线。如下图，选取TP-1为根，则左边的网络拓扑可以等价画成右边的网络拓扑。

多互联拓扑一般存在环路，需要去掉一些连线才能画成树型结构。如下图，左边为一个多互联拓扑，选取TP-1为根，生成右边的拓扑，右边的拓扑需要去掉红色的连线才能称之为树状结构。

在交换机中，我们会在每一台交换机上运行生成树协议(STP，Spanning Tree Protocal)或其变种(RSTP/MSTP)来去掉多互联拓扑中的环路，也就是上图中的红线。注意，真实去掉的线路由STP来决定，上图的红线代表的是去掉连线的一种情况，并不一定是实际去掉的线。

由于生成树协议使用的生成树算法(STA，Spanning Tree Algorithm)，类似于上面的Dijstra或Prim算法，其核心都是用“加点”的思想逐个将点加入到生成树。但不同于Dijstra算法，STP的STA不需要全局拓扑数据便能收敛出一棵树。所以接下来让我们先看Dijstra/Prim算法，再看生成树协议。

2.9.1 Dijstra/Prim算法

Dijstra算法的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个节点点作为源节点然后找到该顶点到图中所有其它节点点的最短路径，产生一个最短路径树。

Dijstra算法可以说是特殊条件下的Prim算法，两者的思想相同，均为确定树根后逐个加点的方式将所有点加入到树中，区别在每一步加哪个点，Prim算法选择连接到当前树的点中最小权重边的点，Djistra算法选择连接到当前树的点中到树根最小权重的点。对于同一个加权连通图，Prim算法和Djistra算法的结果可能会不一致。如下，

Prim算法(最小生成树)的工作流程

如下，在已有加权连通图的基础上，将点分为两个集合：红点集合R(已经加入树的节点)和黑点集合B(未加入树的节点)。第一步，选择一个点作为树根，如下图的0节点，加入到R中；第二步，从B中取出连接到R中节点的所有节点，如下图的1和2节点，比较对应边的权重，因5<8故选择2节点加入R，同时标记0-2这条边；循环第二步直到所有节点加入R。理解的重点在于将红点集合看成一个整体。

Dijstra算法(最短路径树)的工作流程

Dijstra算法的流程和Prim类似，主要是使用的权重不同，Dijstra算法使用的是累积的权重。如下图，图3到图4和上面存在差异，主要是因为0->1->3的累积权重8+11=19要小于0->2->4->3的累计权重5+10+7=22，所以图3到图4选择的是1-3这条边而非4-3这条边。

为方便理解两种算法，本处提供维基百科上Prim算法的一个更详细工作流程示例。在第二步的时候任意选定了顶点D作为树根，后面每个步骤都会往树里新增1个点和1条边，直到所有点都加入到树中，最终构建出该连通图对应的树。如需动态示例，还可参考此链接。

从上面我们可以得出，Dijstra和Prim的区别就在于权重和累计权重。而权重和累计权重怎么选择，这里可以预先给出一个结论，大部分路由/交换协议需要生成树状结构的时候使用的都是累计权重。比如OSPF使用的就是累计开销来计算本地的路由，RIP使用累计的跳数来计算路由，STP用累计的Cost来进行收敛。

Dijstra算法的输入为一个加权连通图G(V,E)和选定的树根，输出的结果为最短路径树T。G为Graph(图)，由Vertex(顶点)和Edge(边)的构成，T为Tree(树)。在任意星型或多互联型网络拓扑中，如果要转化成树状结构，可以使用Dijstra算法，但Dijstra算法需要的两个输入中，树根(根交换机)我们可以通过某种方式指定，加权连通图则不那么容易获取，需要明确一下下面两个问题。

交换机如何获取加权连通图？

首先，连通图在这说白了就是拓扑图，加权连通图只不过是在拓扑图的每条线路上加了权重；然后要明确，网络拓扑中的交换机并没有上帝视角，它们一开始是没有拓扑图的；想要它们有拓扑图，要么我人工将拓扑图存到交换机上，要么我设计一个沟通方法，让它们可以自己沟通后获取到拓扑图。最后，人工存拓扑图进交换机，实际上不太现实，只要网络拓扑发生变化，我就得重新导入；那么只剩下设计一个交换机之间的沟通方法(协议)，让它们自己去获取加权连通图。

是否一定需要获取加权连通图才能计算生成树？

答案是否定的，尽管很多协议会获取到加权连通图再计算最短路径树，比如OSPF，但存在某些方法，不获取加权连通图也能最终获得稳定的树状结构。OSPF(Open Shortest Path First)中的Shortest Path First实际上指的就是Dijstra's Shortest Path First algorithm，也就是Dijstra算法；OSPF会通过其设计的消息分组(LSA)来获取/通知完整的加权拓扑，从而直接利用Dijstra算法计算出从本节点到其他节点最短路径树从而得到最终的路由。这种做法可靠性很高(无环/收敛快)，但需要的消息分组占用带宽比较多，在早期带宽很有限的情况下，并没有直接被使用(但现在已经成为主流)。更多地是使用一些巧妙的方法可以以尽量小的消息分组分布式地达到类似的生成树状结构的效果，比如RIP计算路由，比如STP形成二层树状结构，两者的共同特点是占用带宽小和收敛速度慢，目前一般已不在生产环境使用，但两者的“升级版”还活跃在各种网络环境。

下面的STP便是一种带宽有限的情况下的巧妙的生成树状网络结构的沟通方法。

2.9.2 生成树协议(STP)

生成树协议的作用是将任意网络拓扑转化成树状拓扑。为了实现这个功能，我们需要 1）选出树根， 2）删去不必要的边，3）设计实现前两者的沟通机制。在2.9.1中，已经知道STP不需要全局拓扑也能计算出生成树，那它是如何生成树的，让我们带着下面的问题继续阅读，希望阅读完之后能有对应的答案。

• 哪个节点适合作为树根 (性能最好的节点/随机节点/任意人工指定的节点)？
• 使用几层的数据包来传递数据 (二层/三层/四层)？
• 如何实现路径的(累积)加权，如何计算权重？
• 如何删除不必要的边(down掉接口/实现其他特殊的接口状态)？
• 如何实现没有全局拓扑情况下形成树状结构？

在STP中，使用一种名为cost的值来标记两个节点之间线路的在整个网络拓扑中的权重。不同速率的线路的cost值是不同的，如下表所示，给出了旧版IEEE和修订版IEEE指定的不同速率下的线路cost值。

在STP中，使用一种名为BPDU(Bridge Protocol Data Unit)的数据包来进行数据的的交换，它是一种二层封装的包，共有两种不同的包格式Configuration BPDU和TCN BPDU，如下图所示。两种BPDU分别占用35个字节和4个字节，默认使用以太网(18字节封装)的情况下，完整的数据包分别占用53个字节和22个字节。那为什么不用三层/四层来封装BPDU呢？假设使用三层封装来封装BPDU的信息，则需要另外加上ip头部的20字节；对于一个2字节的TCN BPDU来说，共需要18(以太网)+20(IP)=38字节封装，数据才2字节，封装达到了38字节，未免显得太过于“头重脚轻”，所以工作在二层的包才符合早期带宽小的情况。

以下为open vswitch实现的STP协议对BPDU进行定义的部分，同上面的BPDU格式基本一致，供读者参考。

#define STP_PROTOCOL_ID 0x0000
#define STP_PROTOCOL_VERSION 0x00
#define STP_TYPE_CONFIG 0x00
#define STP_TYPE_TCN 0x80


struct stp_bpdu_header {
    ovs_be16 protocol_id;       /* STP_PROTOCOL_ID. */
    uint8_t protocol_version;   /* STP_PROTOCOL_VERSION. */
    uint8_t bpdu_type;          /* One of STP_TYPE_*. */
};

enum stp_config_bpdu_flags {
    STP_CONFIG_TOPOLOGY_CHANGE_ACK = 0x80,
    STP_CONFIG_TOPOLOGY_CHANGE = 0x01
};

/** Configuration BPDU **/
struct stp_config_bpdu {
    struct stp_bpdu_header header; /* Type STP_TYPE_CONFIG. */
    uint8_t flags;                 /* STP_CONFIG_* flags. */
    ovs_be64 root_id;              /* Bridge believed to be root. */
    ovs_be32 root_path_cost;       /* Cost of path to root. */
    ovs_be64 bridge_id;            /* ID of transmitting bridge. */
    ovs_be16 port_id;              /* Port transmitting the BPDU. */
    ovs_be16 message_age;          /* Age of BPDU at tx time. */
    ovs_be16 max_age;              /* Timeout for received data. */
    ovs_be16 hello_time;           /* Time between BPDU generation. */
    ovs_be16 forward_delay;        /* State progression delay. */
}

/** Topology Change Notification BPDU **/
struct stp_tcn_bpdu {
    struct stp_bpdu_header header; /* Type STP_TYPE_TCN. */
}

STP的两种BPDU，笔者用心想象了一下，实在没想象出来如何令一台交换机仅利用收到的BPDU就构建出完整的拓扑。里面有效的、能用于生成树计算的有：root_id（发送交换机认为的根交换机id），bridge_id（发送交换机的id），root_path_cost（发送交换机到根交换机的累计开销)，port_id（发送交换机发送这个BPDU的接口id）。如何利用这4个信息就计算出对应的生成树呢？我们以3台交换机互联来说明如何计算，假设这3台交换机的bridge_id分别为100，200，300，中间线路带宽分别为10Gbps，1Gbps，100Mbps。

1）网络中所有启用STP的交换机一开始都认为自己是树根root，发送Configuration BPDU(root_id=bridge_id,flag=0x01)给其所有邻居节点，如下图所示。

2）所有收到邻居BPDU的交换机，都会比较邻居节点发来的BPDU中的root_id和自己的root_id；如果自己的root_id更小，则回复Configuration BPDU(root_id=收到BPDU中最大的root_id,flag=0x80)，表示自己愿意以这个最大root_id为根，并且停止主动发送BPDU；如果自己的root_id更大，则回复Configuration BPDU(root_id=自己的root_id,flag=0x80)，表示希望邻居都以本交换机的root为root。(注:下面的cost=0请自行抓包确定是否实际为0，但这个一般不影响实现)

3）经过2过程后，确定了根是蓝色的交换机，但线路仍有环，需要删去一条边才能生成树，经过比较cost值后，非根的两台交换机阻塞(block)掉自己的接口，最终实现所有节点加入树，多余的边被删去，变成下面的树状网络。

上面的例子为了描述的时候的简单，假定了三台机器同时起STP，并且发送包也是同时发送同时到达。而实际网络中包的收发顺序往往是随机的，一台交换机可能在任意时刻启动STP，包也可能在随机时刻到达，这就导致了，不同情况下发包内容和顺序都有差异，但最终收敛出的结果是一致的。在通常的网络认证学习里，都喜欢把上面的过程概括成下面四个步骤。

这种概括方式将整个生成树收敛描述成了一个顺序的4步骤过程，但一般没有说明这4个步骤或者状态是可以同时存在于某个网络的。在同一时刻(生成树收敛时)，不同的交换机可以处于不同的步骤，而且这个步骤并不是一次性的，一般会有多次(网络震荡抖动)。

以4个步骤理解一台交换机是可以的，但以4个步骤理解整个交换机网络是不准确的。如果非要理解这个过程的话，不妨把它想象成东汉末年群雄并起，匡扶汉室一统天下。如下，为一块三国时期的地图。

如果玩过类似的三国类策略游戏，都会有“开局一块地，攻城略地打天下”这样的体验。假设此刻你是刘皇叔，手下的地盘为左下角那一片(蜀地)，首都在蜀，你要以蜀为基本盘，收复汉室大好河山。首先，假设你选择了从涪陵出兵(BPDU)宜都，宜都的首都在襄阳，也派出兵马(BPDU)与涪陵“碰一碰”；碰完之后发现蜀这个首都要比襄阳这个首都更值得奔赴(root_id更大)，于是宜都摇身一变，加入蜀国；从此绿色的国度少了宜都，蜀国多了宜都；接下来有个问题，宜都加入蜀国后要运战利品到蜀，战利品可以有多个路(巴东，巴，涪陵)传入蜀，但是走巴东，还是巴，还是涪陵(选择根接口)？答案是：一开始是涪陵，但后面巴和巴东的兵马(BPDU)也会进入宜都(可能有早有晚)，两路兵马会告诉宜都分别需要多少路到蜀地，宜都会比较会看那条路更快(到根开销更小)，最终可能变成选择走巴到蜀，自此宜都被攻下，宜都到首都的路径也被确定。

这种攻城略地的情况是否是一个一个来的呢？答案是否定的，这种情况实际会同时发生在每两个相邻的势力之间。各个势力都会广派兵马(BPDU)四处攻城略地，所以整个地图是动态的，同时存在多个势力的，可能涪陵和宜都大战时，吴也正在与广陵开战，长沙也在与豫章激烈斗争。随着地方割据势力的吞并。小势力逐渐消失，留下了几个大势力，最终大势力互相开战，直至天下一统，所有到首都的路径都被确定(生成树收敛完成)。

Dijstra是集中式的“加点法”，生成树式分布式的“加点法”。前者可以类比统一国家由政府计算如何从首都最快到各个城市，后者可以类比为各方势力群雄逐鹿顺便确定走那条路到首都更快。但实现的都是同一个东西，即任意加权连通图(拓扑)到树(树状拓扑)的转化。

2.9.3 生成树协议相关链接

生成树协议(STP)由IEEE 802.1d提出并指定，生成树协议的定时器，五种状态转化等详细内容，可以参考802.1d标准，交换机上的具体配置以及提供的增强特性可以参见对应Cisco、H3C等官网。

快速生成树协议(RSTP)由IEEE 802.1w提出并指定，其相较于STP对状态进行了删减，并加速了状态转化，还把厂商增强特性也纳入为协议的一部分，具体内容可以参考802.1w标准。

多实例生成树协议(MSTP)由IEEE 802.1s提出并指定，其相较于STP增加了对802.1q帧的区分，也就是针对每个vlan都可以建一棵生成树，实现不同vlan的生成树树根可以不同(可以负载到不同的主机上)，而非原来的一生成树所有vlan共用，具体内容可以参考802.1s标准。

2.10 多交换机互联-选路

多交换机互联时，从A交换机到B交换机，可能存在多条路径，这种情况下我们如何对二层数据包进行转发？为了方便说明，我们约定一个路径为(A，.... ,B)代表A到B的一条路径，省略号的部分为中间节点，比如(BR-2,MD-1,TP-1)为BR-2到TP-1一条路径，中间节点为MD-1，参照下图进行理解。

每一台交换机继续看作驿站，转发消息看作飞鸽传书，多交换机互联的情况便可以看成一个情报网，你现在是一个情报头子。假设每个驿站养了大量的鸽子可以用于传书，但驿站初建立时是不知道收到传书后应该飞鸽发往哪一个站点的。为了让这个情报网运作起来，我们必须通过一些通用的方法，让驿站能够传递情报。下面是一些可能的选项：

• 泛洪。每个驿站收到的飞鸽，都会将收到的信息抄录复制后，往除了发送情报点外所有相邻的情报点飞鸽。好处是肯定能到目标点，坏处是比较费鸽子并且可能鸽子走一圈又飞回来(环路)导致收到重复的信息。
• 静态规则。情报头子亲自/飞鸽传书到每一个驿站，跟驿站的负责人交待，发给谁的信息往哪个相邻的点飞鸽，除非情报头子再来修改，否则一直不变。这样也能发到目标，而且整个情报网很稳定，坏处是如果有新的信息，要修改或添加规则，比较费情报头子。
• 动态生成的规则。情报头子依靠自己用静态规则去运行整个情报网，如果情报网小还好，如果情报网稍微大一点，说实话这个情报头子很快就干不下去了。好的头子应该是让手下学习成长，执行更多的职责。在这种背景下，情报头子为了自己的生命健康，发明了一套沟通方法，并让驿站的手下学会这个方法，然后驿站可以根据这个沟通方法，互相飞鸽协商，然后动态生成如何传递每一条信息的规则。
• 在2的基础上再培养一个副情报头子。这个副的情报头子专门负责整理怎么走如何走，当驿站不知道消息该怎么飞鸽的时候，就通知这个副的情报头子，由副情报头子告诉驿站怎么传递信息。好处和坏处都是所有驿站又回到了根据下发的静态规则埋头飞鸽的时代，情报网管理职能中心化。

集线器和交换机就是第1种方案的的忠实执行者，集线器网络（本文2.4）便是选择泛洪这种方式，并且交换机对这种方式又进行了增强(本文2.5.1 )，增强的部分(二层地址缓存)减少了“飞鸽”的数量，使得没有那么“费鸽子”，但没有解决第一种方案可能带来的环路问题。关于环路如何产生，如何解决环路，让我们逐个回答下面的问题，最终得到二层通用的组网和选路。

• 数据包可不可以原路返回？
• 二层数据环路是如何产生的？
• 如何避免二层数据环路？
• 二层选路为什么不用静态规则？
• 二层选路为什么不用动态生成的规则？
• 二层选路为什么不用"再培养一个副情报头子"的方式？
• 存在多路径时，二层能不能多路径做负载？

2.10.1 数据包可不可以原路返回？

泛洪设定了只会往非发送点的其他点转发数据包，不允许返回，那么网络中能否原路返回呢？如上图左，现在我有一个数据包，需要从BR-2下的主机到BR-7下的主机，最短路径是(BR-2,MD-1,BR-1)，那么我可以不可以让这个数据包沿着(BR-2,MD-1,BR-2,MD-1,BR-1)这种路径走？从结果来说，(BR-2,MD-1,BR-1)和(BR-2,MD-1,BR-2,MD-1,BR-1)是等效的，都完成了BR-2到BR1的数据包发送，但后者转发一个数据包,BR-2和MD-1都参与转发了两次，相当于双倍负载，如果有千个万个数据包都这么转发，必定很快就耗尽交换机性能。所以，在二层交换机里，一般不允许原接口返回，但网络里有没有原接口返回的呢？答案是有，比如旁挂的防火墙，三层交换机跨vlan访问，都可以原接口返回，但在逻辑上会区分成不同的子接口收发，以不违背这个不可以原接口返回的规则。另，SDN(Software Definition Network)的白盒交换机可以自定义转发路径，你完全可以写一个原路返回的路径，然后让下面的交换机按照这个路径来转发，但是大部分时间无此必要罢了。

2.10.2 二层数据环路是如何产生的？

首先让我们看一个简化的例子，如下图，图中出现了一个物理环路(SW-1,SW-2,SW-3,SW-1)，此时A发送了1个目标为B的数据包，这时候会出现什么现象？让我们来分情况讨论。

首先是所有交换机都没有B地址缓存的情况，如下图所示。假定此时主机B只收不发(mac地址不会被学习到)，则会带来2个数据包的无限循环。当数据包到达SW-1时，因为没有B的缓存，交换机会将之泛洪出去，如下图左右的②过程；到达SW-2/SW-3时，由于没有二层地址缓存，也都会泛洪出去，如下图的③所示；最后又经过SW-3/SW-2，泛洪回到SW-1，完成了一个数据环路。虽然主机也会收到对应的数据包，但是有2个由SW-1复制的数据包陷入了无限循环中。

然后是上联交换机SW-2有B地址缓存的情况，如下图所示，SW-2上此时有B的二层地址缓存。当SW-1收到数据包的时候会泛洪给SW-2和SW-3，SW-3收到后会泛洪给SW-2，但到SW-2已经是终点了。因为SW-2上有记录，地址B应该往接口3发出，所以SW收到的2个数据包都会转发给主机B，不会有环路的情况，⑤便是这此发送数据包的最终步骤。但在这种情况下，出现了帧复制，也就是B收到了两个一样的数据包。

似乎只要上联交换机上有B地址缓存就不会产生环路，但真的是这样吗？我们在上图的基础上在加入一台交换机便知。如下图，主机B和SW-2之间增加了SW-4，此时SW-4上有B的mac地址缓存。当A发送数据包时，由于SW-2上没有mac地址缓存，所以不管是(SW-1,SW-2)还是(SW-1,SW-3,SW-2)，到达SW-2后都会泛洪。数据会像上面没有二层地址缓存一样在SW-1,SW-3,SW-2之间转圈，同时每次转到SW-2都会再发送一份副本给SW-4再到主机B，主机会收到大量的重复包。所以关键不在于上联交换机有无二层地址缓存，而是在于关键节点有没有对应的二层地址缓存，不然就会泛洪造成环路。那么关键节点是哪个节点呢？对于A、B之间最短路径的任意两个节点a、b，如果a，b之间存有多条路径，若此时数据包时A->B，则b就是一个关键节点，如下图，SW-2就是一个关键节点。

但大多数时候，是没办法保证这些关键节点上有对应的二层地址缓存的，所以一旦有物理环路，大概率会产生二层上的数据环路。而产生数据环路后，数据每次经过某个关键节点都会被复制成多份，如下图中的SW-2，如果没有对应的二层地址缓存，每当SW-1/SW-4下的主机访问SW-5/SW-3下的主机时，每次数据包都经过SW-2，都会复制成3份(交换机接入网络有n个口，则复制n-1份)，导致网络包数量迅速放大，形成所谓的广播风暴。

总而言之，二层数据环路的产生主要源于关键节点没有持久的、单向的、准确的转发规则。二层地址缓存(mac地址表项)存在过期时间，一个mac地址表项如果过期，从过期到重新学习到的这段时间里，如果有数据发送，则可能产生广播风暴。但即使有这个规则，也可能会面临帧复制这种浪费带宽的问题。

2.10.3 如何避免数据环路？

解决数据环路的思路有很多，但因为二层协议头中的字段有限，大部分都需要二层以上的协议进行支持，或者引入一个其他协议如STP。这里是笔者归纳整理的一些通用的防环思路，不局限于二层实现。

• 保证关键节点有持久的、单向的、准确的转发规则。由2.10.2可知，二层数据环路的产生主要是因为关键节点没有相应的转发规则，我们可以从这一点入手，通过配置静态规则(固定的)，来进行防环，但这种情况一般出现在三层，通过在关键节点合理配置静态路由和默认路由是可以防止环路的。
• 设定最大跳数。数据包里包含一个跳数，每经过一台设备这个值会减去1；即使发生环路，当跳数归零时数据包会被自动丢弃，避免一直在绕圈。这个功能一般可以用三层(ip)头部的TTL字段实现。
• 携带路径信息。数据包里包含一个路径信息，记录经过的节点，当数据包被发到已经经过的节点上时，会被丢弃，或者数据包一开始就不会被发往已经过的节点。这个功能以太网头部、IP头部、TCP/UDP头都没有字段支持，需要另外的协议定义字段去支持(比如BGP定义的数据分组中的AS-PATH字段)。
• 建立全局的树。本文2.9讨论了任意拓扑如何转化成树，以及图可能存在环但树是不存在环的。如果在整个网络拓扑中，选择某个特定的节点作为树根，再堵塞某些接口，形成树型拓扑，那么这棵树上的任意两点互访都是无环的。生成树协议的算法防环便是这种思路的实现。
• 建立以自己为树根的树。与全局树不同，这里的树是每个节点都以自己为树根计算出一棵树，而且一般是最短路径树。这棵树的数据会保留自身节点上，不会传递到其他节点。每个节点转发数据时，都会根据这棵树进行转发。OSPF协议的算法防环便是这种思路的实现。
• 以区域为单位建立树。上面建立的树是节点与节点之间，这里我们可以将多个节点看成一个整体/区域，再建立区域之间的树型拓扑，从而实现区域之间的无环化。OSPF的区域防环(area 0为树根/中心，其他area为分支)便是这种思路。
• 水平分割。二层的泛洪会让其他交换机都学习到某个mac地址，其实就可以看作传递mac地址表信息。mac地址表控制的是二层转发，路由表控制的是三层转发，都可以称作转发表。转发表的信息在传递时一般都不会从接收接口原路返回，这就是水平分割。

交换防环，主要用到了上面的建立全局的树和水平分割。假定我们使用的都是二层交换机，其他思路要么超出了二层以太网头部能实现的范畴比如设定最大跳数需要利用三层头部实现，要么跟下面的

“二层选路为什么不用静态规则？”一样，受限于二层地址分布的杂乱无章。

2.10.4 二层选路为什么不用静态规则？

因为二层如果用静态规则，需要的规则量太多了。本文1.3有讨论为什么有二层的mac地址后还会出现三层的IP地址，其中最主要的原因就是二层地址分布杂乱无章，无法有效汇总。举个例子，比如现在有个十字路口，往左边有个村子，里面住的是王大、王二、王三、王洛夫斯基，右边有个村子里面住的是大黄蜂，钢铁侠，葫芦娃；如果有人来寻人，你在路口为人指路，对于左边这个村子的人，你只要根据“前缀是王的往左走”这条规则指向左即可；对于右边这个村子的人你要根据“找钢铁侠往右走”、“找大黄蜂往右走”、“找葫芦娃往右走”这三条从上往下匹配后再指向右。二层地址的杂乱无章导致了一旦网络规模上升，静态规则是不可行的。但在三层中是可行的，因为三层连续地址一般可以汇总。三层静态规则一般被称为静态路由。

2.10.5 二层选路为什么不用动态生成的规则？

动态生成的规则和和静态规则一样，受限于mac地址无法有效汇总。所以三层出现了各种各样的动态路由(选路)协议，但二层没有这种协议。三层动态生成的规则一般被称为动态路由。

2.10.6 二层选路为何不"再培养一个情报头子"？

传统二、三层网络都是分布式的计算，每一个节点初始时都没有其他节点的信息，需要通过信息交换和本节点上的计算确定本节点对每个数据包采取的行为。而再培养一个情报头子是SDN(Software Definition Network)的思想，它是集中式计算。在SDN的概念里会有一个控制器，它会通过OpenFlow协议(南向接口)管理所有交换机，当交换机不知道怎么转发的时候，会请求控制器从而获得如何转发的指引(流表，Flow Table)，控制器经过拓扑计算后会下发流表指引如何转发。因为本文旨在厘清传统网络的概念思想，而最初的SDN网络并未被广泛使用(强调使用白盒交换机，相当于革设备厂商的命)，现在的SDN都是厂商和自家设备结合的产物，所以还是以传统网络的二层为主进行讲解，默认不采用这种方式。

2.10.7 存在多路径时，二层能不能多路径做负载？

首先要明确，只有二层封装的包是必须保证有序性的，这点跟二、三层都封装过的包不同，三层的IP首部里面包含了identifier(标识)和segment offset(片偏移)两个字段，可以用来确定先后顺序从而保证即使收到方乱序接收到也可以还原成原来的顺序，但二层封装的包(无论是以太网封装还是PPP封装)都做不到这一点，这也是三层出现的一个重要原因，因为不需要有序，三层可以轻松实现各种多路径负载。但因并非所有包里面都会含有三层头部，还有部分协议是工作在二层的，我们必须考虑到适配，所以要尽量保证二层帧的有序性。

然后，同源目的多路径，可能会造成数据帧的无序性。如下图，假如SW-2上有对应的二层地址缓存(暂时不会环路)，A往B顺序发送了两个以太网数据包1和2，结果到SW-1时，对这两个数据包做了负载，数据包1走了③，数据包2走了②，最终数据包2比数据包1先到了主机B(并非一定是这样，实际情况需考虑转发时延等因素)，这就造成A->B的数据帧顺序错乱。所以这种情况一般是不可取的。

最后，不同源目的多路径，一般不会造成数据帧的无序性。如下图，A顺序发送了两个以太网数据包1和2，但目的地址不一致，即使到了SW-1，对这两个数据包做了负载，数据包1走了③，数据包2走了②，也不一定会造成无序性，只要保证后续到C的一直走③，到B的一直走②就行。本文2.6.3的链路捆绑利用的就是这个原理，不同的目的mac地址的数据包会被哈希到不同的线路，并且一直固定是那条线路，从而实现了捆绑线路的负载，成为逻辑上的一条线。

所以可以得出结论，二层多路径是可以实现负载的。但因为二层防环目前主要是采用生成全局树和水平分割，所以多出来的路径会被阻塞，导致最终只有单路径，所以用链路捆绑这种方式将多条线作为逻辑上的一条线加入生成树计算，而链路捆绑，本身就是二层多路径负载的一种实现。

2.10.8 二层通用的组网和选路

经过上面的长篇大论，我们可以汇总一下，得到二层通用的组网和选路情况：

• 每个交换机算一个节点，普通互联线路算一条线，多条互联线路捆绑算一条线。
• 转发消息时，交换机有对应mac地址表项时单独从某个接口发出，没有对应mac的时候泛洪。
• 一般会用生成树协议解决多路径环路、潜在的数据帧无序性等问题。
• 星型拓扑可以不运行生成树，多互联型拓扑一般要运行生成树协议(或其衍生版本)。
• 判断有无环的的依据很简单，n个节点对应n-1条线则无环，多一条线都算有环。
• 因为运行了生成树协议，所以没得多余的路选，只有一条路可走，泛洪也等于只往一个接口发包。

还可以得到以下潜在的改进方向，这些都会在三层选路中进行改善：

• 生成树协议会阻塞某些线路，导致网络未被充分利用，可以想办法利用这些被阻塞的线。
• 二层地址缓存虽然改善了原有的泛洪“费鸽子”的情况，但解决的还不够彻底，可以多花点鸽子沟通，然后少泛洪。

2.11 接入、汇聚、核心三层网络架构

在本文2.8的两层树状结构的基础上，我们再嵌套一层树状结构，就会形成一个经典的接入、汇聚、核心三层网络架构。注意这里的三层并非指的三层协议，而是这个树的level是3。如下图，最下面的是相对低端的交换机，用于主机(服务器等设备)接入，我们称之为接入层；中间的是相对中端型号的交换机，用于对接入交换机做一层汇聚，我们称之为汇聚层；最上面只有一台(或一对)交换机，是整个网络的核心，我们称之为核心层。

这种三层架构可以类比成一个物流网络，比如最下面是广州集散点、深圳集散点、东莞集散点，中间是华南区集散点，最上面是中国区主集散点。mac地址的记录数量也会下面最少，中间次之，上面最多。但是否核心交换机就拥有下面所有的mac地址记录呢？答案是否定的，因为可能有些数据包在最下面的交换机就被转发掉了，根本没到过汇聚或核心交换机。所以如果要抓取所有的mac地址，需要将每一台接入上的mac信息抓取下来然后去重，或者将所有交换机的mac地址信息抓取下来然后去重(因为有些汇聚也会下接主机)。

上面这个三层架构是精简版的，真实的三层架构可能会考虑高可用，下层的交换机会使用多条线路上联，并且同时在网络中使用链路捆绑、堆叠、vrrp等技术，后面会举例说明生产上是如何在不同的网络架构上组合使用这些技术的，最终的目的是灵活组网。

3 小结

本篇仅讲解到二层网络，后面的内容虽已经列好思路和大纲，但需要一定时间整理和绘图才能发出。本篇绘制gif和普通图花了较多时间，以至于没有仔细校正内容，如有遗漏或理解偏差，望读者不吝指出。感谢诸位的阅读，我们将在下篇续上本篇的内容。