网络技术培训课件

网络技术第二课内部技术培训网络技术第二课内部技术培训1第一课课后问题为什么本地arp表不会保存另外网段的目标地址：因为arp只负责在本网段内转换ip,和mac。对于其他网段的网络层填入目标地址，链路层填网关地址。网络设备校验出错如何处理？是否要求对端重新发送报文？网络设备校验出错直接丢弃报文，重新发送报文的功能交给TCP协议来实现。第一课课后问题为什么本地arp表不会保存另外网段的目标地址：2链路层相关技术802.1Q：vlan协议802.1是IEEE的一个工作组，负责制定iso7层模型中链路层的相关协议。常见的协议比如802.1q-vlan、802.1b-无线接入、802.1x-准入控制、802.1d-stp等链路层相关技术802.1Q：vlan协议3Vlan是做什么的vlan是virtuallan(虚拟局域网的简称)如果没有vlan协议会怎样：二层（链路层）报文会在二层设备的所有端口进行广播。导致只要在一个网络设备下的计算机都处在一个广播域下。Vlan的作用是将一台交换机的端口按照广播域进行隔离。Vlan是做什么的vlan是virtuallan(虚拟局域4举个例子举个例子5802.1q帧格式802.1q帧格式6802.1q帧格式说明802.1Q封装共4个字节，包含2个部分：TPID(Etype),TagControlInfo；

TPID:长度为2个字节，固定为0x8100,标识报文的封装类型为以太网的802.1Q封装；

TagControlInfo：包含三个部分：802.1P优先级、CFI、VLAN-ID；802.1PPriority：这3位指明帧的优先级。一共有8种优先级,取值范围为0~7,，主要用于当交换机出端口发生拥塞时,交换机通过识别该优先级,优先发送优先级高的数据包。CFI：以太网交换机中，规范格式指示器总被设置为0。由于兼容特性，CFI常用于以太网类网络和令牌环类网络之间，如果在以太网端口接收的帧具有CFI，那么设置为1，表示该帧不进行转发，这是因为以太网端口是一个无标签端口。VID：VLANID是对VLAN的识别字段，在标准802.1Q中常被使用。该字段为12位。支持4096（2^12）VLAN的识别。在4096可能的VID中，VID＝0用于识别帧优先级，4095（FFF）作为预留值，所以VLAN配置的最大可能值为4094。802.1q帧格式说明802.1Q封装共4个字节，包含2个部7802.1q帧与标准以太网帧相互转换明确交换机接收和发送的报文是带tag的还是不带tag的。VLAN成员的连接方式分为三种：Access,Trunk,Hybrid;

Access连接：报文不带tag标签,一般用于和tag-unaware(不支持802.1Q封装)设备相连，或者不需要区分不同VLAN成员时使用；

Trunk连接：在PVID所属的VLAN不带tag标签转发,其他VLAN中的报文都必须带tag标签，用于tag-aware(支持802.1Q封装)设备相连，一般用于交换机之间的互连；

Hybrid连接：可根据需要设置某些VLAN报文带tag,某些报文不带tag。与trunk连接最大的不同在于，trunk连接只有PVID所属的VLAN不带tag,其他VLAN都必须带tag,而Hybrid连接是可以设置多个VLAN不带tag；802.1q帧与标准以太网帧相互转换明确交换机接收和发送的报8不同类型的端口对tag处理方式

报文入方向：在入方向上，交换机的根本任务就是决定该报文是否允许进入该端口，根据入报文的tag/untag的属性以及端口属性，细分为如下情况：1)

报文为untag:允许报文进入该端口，并打上PVID的VLANtag,与端口属性无关；2)

报文为tag:在这种情况下，需要交换机来判断是否允许该报文进入端口；

Access端口：PVID和报文中tag标明的VLAN一致，接收并处理报文；否则丢弃。

Trunk/Hybrid端口：如果端口允许tag中标明的VLAN通过，则接收并处理报文；否则丢弃。不同类型的端口对tag处理方式

报文入方向：9不同类型的端口对于tag的处理报文出方向：在出方向上，交换机已经完成对报文的转发，其根本任务就是在转发出端口时，是否携带tag转发出去，根据出端口属性，细分为如下情况：1)

Access端口：将标签剥掉，不带tag转发；2)

Trunk端口：报文所在VLAN和PVID相同，则报文不带tag；否则带tag；3)

Hybrid端口：报文所在VLAN配置为tag，则报文带tag；否则不带tag；不同类型的端口对于tag的处理报文出方向：10一个vlan标记原理的例子通过标记的原理来理解vlan通讯的行为特征。一个vlan标记原理的例子通过标记的原理来理解vlan通讯的11STP生成树协议为什么要使用stp：如果二层网络一旦产生环路，由于二层帧没有ttl的概念，帧会无限转发。如果没有环路，那么一旦出现单点故障，就会造成网络中断。因此stp一方面解决二层环路的无限转发问题，另一方面解决了网络冗余问题。注意二三层协议对于环路处理的区别。STP生成树协议为什么要使用stp：12一些基本的图论知识什么是图？从几何角度上讲，平面图有三个要素，点、线和面。我们所考虑的图是由点和边构成的集合。有向图与无向图边要素：边的权值一些基本的图论知识什么是图？13图的一些基本性质点的要素：概念：点的度数：指的是点上面包含边的数量。定理：一张图中全部点的度数的和是边总和的两倍。记：∑

d(v)=2*∑

count(e)图的一些基本性质点的要素：14图的一些基本性质推论：对于不含自环的无向的完全图，边的总数和点的关系如下：假设点的数量为n，边的总数为n*(n-1)/2因为完全图，每个点都与其他点有一条边相连，因此每个点的度数都为n-1,所有点的度数总和为n*(n-1)。因此总边数为n*(n-1)/2图的一些基本性质推论：15图的一些基本性质概念：连通图一张图内任何一点都有至少一条路径与图中其他任意点可达概念：连通度一张图去掉n条边后由连通图变成非连通图的n的最小值图的一些基本性质概念：连通图16树的一些基本性质树是边数最少的连通图，一个点与另外一点只有一条路径可达。树中点数和边数的关系：设树中点的个数为n，边的总数为n-1因此，一张连通图中边的总数的范围是：n-1

<=

count(e)<=

n*(n-1)/2树的一些基本性质树是边数最少的连通图，一个点与另外一点只有一17连通图的生成树概念：生成树生成树包含图中全部的点，并且边是图的子集，这样的树叫做图的生成树。概念：生成树的初等变换删掉树中的一条边，添加一条生成树关于图的补集的边。这个操作叫做生成树的初等变换。定理：一个图的生成树可以由任意一个生成树经过有限次初等变换得到连通图的生成树概念：生成树18生成树的数量与最小生成树问题1：我有一个80设备的网络规模，需要拉成一个树状网络，怎么布线能保证所使用的网线总长度最短？或者保证所使用的网线长度能保证在一个范围？问题2：一共有多少种可能的布线方法？这个总数决定了采用一种随机方法能够达到满足目标的概率。生成树的数量与最小生成树19完全图的生成树数量一下具有n个节点的完全图的生成树数量。先分析一下这个问题,n个节点的完全图的边数是n(n-1)/2,生成树的边数是n-1。但是并不是所有的n-1条边的所有组合都能组合成生成树。因此生成树的数量要小于C(n(n-1)/2,n-1)我们考察一下完全图的全部生成树构成，我们假设其中一点为树根。那么生成树的总数是树根度数为i（1<=i<=n-1）的全部生成树的总和完全图的生成树数量一下具有n个节点的完全图的生成树数量。20完全图的生成树S(n)=ΣSi(n)

(1<=i<=n-1)

如图：完全图的生成树S(n)=ΣSi(n)(1<=i<=n-21完全图生成树个数从图中可以看到，Sn-1(n)的生成树只有一种。即Sn-1(n)=1。如果我们能计算出Sk(n)和Sk+1(n)之间的关系，就可以采用迭代的方式用Sn-1来表示Sk。从图里面可以看出，Sk和Sk-1是有关系的，我们假T(Sk-1，Sk）是把Sk-1通过减枝得到的Sk的可行的操作的总数。可以看得出，对于Sk-1（n）中的任意一个生成树，把Sk-1变成Sk的方式是把除了与树根相连的k-1个边不动，剩下的边选一个剪到树根。剩下的边的总数为n-1-(k-1)=n-k。因为生成树一共有Sk-1(n)种，因此T(Sk-1,Sk)=(n-k)Sk-1(n)完全图生成树个数从图中可以看到，Sn-1(n)的生成树只有一22完全图生成树个数需要注意的是T(Sk-1,Sk)不等于Sk(n)因为可能会出现如下情况

完全图生成树个数需要注意的是T(Sk-1,Sk)不等于Sk23完全图生成树个数但是，可以从图中看出，T(Sk-1,Sk)=T(Sk,Sk-1)。即把Sk-1变到Sk的方法的总数等于把Sk变成Sk-1方法的总数。我们再来看看如何把Sk变成Sk-1。把Sk变成Sk-1的方式是取一个与Sk相邻的点，把这点下面的整个子树插到除了根节点以外的其他节点下面。Sk一共有k个相邻节点。假设第i个节点下面拥有ni个子节点。那么把这第i个节点插到其他节点的方法一共有n-1-ni种。那么把任意一个Sk变到Sk-1的方法数为(n-1-n1)+(n-1-n2)+…+(n-1-nk)=k(n-1)-(n1+n2+…nk)=k(n-1)-(n-1)=(k-1)(n-1)。因此，T(Sk,Sk-1)=(k-1)(n-1)Sk(n)完全图生成树个数但是，可以从图中看出，T(Sk-1,Sk)=24完全图生成树个数这样，我们就得到了一个关于Sk-1(n)和Sk(n)的表达式(n-k)Sk-1(n)=(k-1)(n-1)Sk(n)=>

Sk-1(n)=[(k-1)(n-1)/(n-k)]Sk(n)=>Sk(n)=[k(n-1)/(n-k-1)]Sk+1(n)=[k(n-1)/(n-k-1)][(k+1)(n-1)/(n-k-2)]Sk+2(n)=[k(n-1)/(n-k-1)][(k+1)(n-1)/(n-k-2)]…[(n-1)(n-2)/1]Sn-1(n)完全图生成树个数这样，我们就得到了一个关于Sk-1(n)和S25完全图生成树个数Sk(n)=[(n-1)^(n-k-1)][(n-2)!/[(n-k-1)!(k-1)!]]=[(n-1)^(n-k-1)]C(n-2,k-1)Sn=

∑Sk(n)(1<=k<=n-1)因此Sn=

∑Sk(n)=

∑[(n-1)^(n-k-1)]C(n-2,k-1)

(1<=k<=n-1)我们假设k-1=r

(0<=r<=n-2)于是Sn=

∑[(n-1)^(n-r)]C(n-2,r)

=

∑[(n-1)^(n-r)](1^r)C(n-2,r)

(0<=r<=n-2)完全图生成树个数Sk(n)=[(n-1)^(n-k-1)][26完全图生成树个数二项式定理（牛顿）：（a+b）^n=

∑[a^(n-r)](b^r)C(n,r)因此Sn=（n-1+1）^(n-2)=n^(n-2)完全图生成树个数二项式定理（牛顿）：27完全图生成树个数我们得到结论，完全图生成树的个数与完全图中点的关系的表达式是S(n)=n^(n-2)变化规律:S(1)=1,S(2)=1,S(3)=3,S(4)=16,S(5)=125,S(6)=1296…举个S(4)的例子：完全图生成树个数我们得到结论，完全图生成树的个数与完全图中点28完全图生成树的个数对于我们之前假设的80个点的情况，可能的布线方案一共有80^78种Log(80^78,base=10)=78*log(80,base=10)=148.4因此全部方案总数的数量级在10的148次方。经过理论推算，整个宇宙的原子的数量的在10的80次方左右。因此，从这些方案中挑出某个特别的方案会比从宇宙中挑出某一个特别的原子要难10^68+倍,完全图生成树的个数对于我们之前假设的80个点的情况，可能的布29最小生成树从上面的结论可以看出，随机从全部的生成树中找出一种特别的生成树是很难的。但是从这些生成树中找到最小或者是最大的却远没这么复杂。这是因为最小生成树有一种特别的性质能够快速的减少组合的规模。这个特性是局部最优解与全局最优解拥有一致性，让我们可以使用贪心算法来求解问题最小生成树从上面的结论可以看出，随机从全部的生成树中找出一种30贪心方法举个找零钱的例子：假设有1，2，5，10，20面额的钞票，想要找33块钱，保证找的钞票数量最少。找钱的办法是先找20，再找张10块的，再找张2块，最后找一张1块。每次都选最接近剩余的钱，就可以保证找的钞票最少。最小生成树也是同样的类似的性质，一张图中的最小边一定属于最小生成树。假设最小生成树中不包含最小边，那么把该边加入生成树，会得到一个环，这个环去掉另一个边也能得到一颗树，这颗树会比原来的最小生成树还要小，与假设矛盾。贪心方法举个找零钱的例子：31Prim算法和kruskal算法Prim算法例子：Prim算法和kruskal算法Prim算法例子：32Prim算法和kruskal算法Kruskal算法例子：Prim算法和kruskal算法Kruskal算法例子：33STP协议网络设备中的生成树算法和上述的计算机内存里的模拟算法有个本质的区别，网络设备的生成树的计算是分布式的，可并行的。每个计算节点对应于图中的一个点，每个节点的目的就是选出有哪些边应该属于生成树，哪些边应该减掉。因此，STP协议算法的逻辑非常接近prim算法。目前使用的是STP协议的优化版本RSTP，而非传统STP。STP协议网络设备中的生成树算法和上述的计算机内存里的模拟34STP协议STP协议通过BPDU（bridge

protocoldataunit）报文，STPBPDU是一种二层报文，目的MAC是多播地址01-80-C2-00-00-00，所有支持STP的网桥都会接收并处理收到的BPDU报文。该报文的数据区里携带了用于生成树计算的所有有用信息。BPDU分为两种，一种是为了计算生成树，叫做配置BPDU,另一种是为了通知拓扑变化,叫做tcn。STP协议STP协议通过BPDU（bridgeproto35STP算法简要描述首先进行根桥的选举。选举的依据是网桥优先级和网桥MAC地址组合成的桥ID，桥ID最小的网桥将成为网络中的根桥，它的所有端口都连接到下游桥，所以端口角色都成为指定端口。接下来，连接根桥的下游网桥将各自选择一条“最粗壮”的树枝作为到根桥的路径，相应端口的角色就成为根端口。循环这个过程到网络的边缘，指定端口和根端口确定之后一棵树就生成了。生成树经过一段时间（默认值是30秒左右）稳定之后，指定端口和根端口进入转发状态，其他端口进入阻塞状态。STPBPDU会定时从各个网桥的指定端口发出，以维护链路的状态。如果网络拓扑发生变化，生成树就会重新计算，端口状态也会随之改变。STP算法简要描述首先进行根桥的选举。选举的依据是网桥优先36根桥自举过程概念：最初每个交换机都认为自己是根，并通过BPDU向相邻的交换机广播这个消息。如果收到其他交换机的BPDU不如自己的，那么丢弃这个报文，如果收到其他的BPDU比自己的好，就停止发送自己的BPDU报文，只转发那个比较好的BPDU报文。这样，最终网络里只剩下一个根桥在不断的发送BPDU报文，其他交换机只负责转发。RSTP对这个行为有个优化，就是非根桥也在发送缓存的BPDU报文，帮助BPDU能够尽快的到达网络边缘。根桥自举过程概念：37根端口、指定端口、阻塞端口的选择根端口与阻塞端口都是通往树根方向的端口。BPDU报文里面有一项是path

cost,用根的path

cost和自己的path

cost相加，哪一个小，哪一个就是根端口。阻塞端口和指定端口，是非根端口的端口哪一个加上port

cost小。小的为指定端口，大的为阻塞端口。阻塞端口不发送用户数据，但是会继续接收BPDU报文，监听网络变化。根端口：收发用户数据，但是并不发送BPDU报文。需要注意的是path

cost是由端口本身决定的，转发的时候要把自己的cost加在上面根端口、指定端口、阻塞端口的选择根端口与阻塞端口都是通往树根38端口状态类型以及状态迁移STP的端口有listening,learning,forwarding,disable,blocking五种状态。端口启动时候状态迁移的过程是listening->learning->(forwarding/blocking)。每个迁移过程默认时间forwarding

delay是15s，导致端口从启动到能转发数据的时间是30s。这段时间用来在网络里构造生成树。因此，stp的网络直径不能过大。RSTP对这个问题的优化是在很多情况下可以不用双倍的forwarding

delay能够快速的进入forwarding状态。同时可以把与非stp设备配置成边缘端口，启动直接就可以进入forwarding状态。另外，rstp中的blocking名字改成discarding。Discarding的端口变成了alternate端口用来给根端口做备份。状态能够快速迁移端口状态类型以及状态迁移STP的端口有listening,l39拓扑变化指定桥发现拓扑变化，比如原来的端口down掉，或者是有新的端口进入。就会由根端口向上发送tc报文。根桥收到tc报文后，会在下一个bpdu配置报文中添加拓扑变化的字段，指定桥收到后会强制刷新各个端口的mac缓存，用以快速切换链路。否则有可能只能等到缓存到期(300s)才能够转发数据。拓扑变化指定桥发现拓扑变化，比如原来的端口down掉，或者是40多实例生成树MSTP协议：不同vlan对应不同的生成树，对于不是单一vlan的情况，可以起到链路冗余和负载均衡的作用。多实例生成树MSTP协议：41新一代链路冗余技术传统生成树技术的缺点：1.过度复杂2.收敛速度慢，无法满足大规模二层网络的需要3.不能真正进行负载均衡。IETF从2004年就开始研究新一代透明交换（TRILL）技术来取代STP相关技术。现在，trill已经开始起步，相信不久的将来，STP就会成为历史。新一代链路冗余技术传统生成树技术的缺点：42演讲完毕，谢谢观看！演讲完毕，谢谢观看！43网络技术第二课内部技术培训网络技术第二课内部技术培训44第一课课后问题为什么本地arp表不会保存另外网段的目标地址：因为arp只负责在本网段内转换ip,和mac。对于其他网段的网络层填入目标地址，链路层填网关地址。网络设备校验出错如何处理？是否要求对端重新发送报文？网络设备校验出错直接丢弃报文，重新发送报文的功能交给TCP协议来实现。第一课课后问题为什么本地arp表不会保存另外网段的目标地址：45链路层相关技术802.1Q：vlan协议802.1是IEEE的一个工作组，负责制定iso7层模型中链路层的相关协议。常见的协议比如802.1q-vlan、802.1b-无线接入、802.1x-准入控制、802.1d-stp等链路层相关技术802.1Q：vlan协议46Vlan是做什么的vlan是virtuallan(虚拟局域网的简称)如果没有vlan协议会怎样：二层（链路层）报文会在二层设备的所有端口进行广播。导致只要在一个网络设备下的计算机都处在一个广播域下。Vlan的作用是将一台交换机的端口按照广播域进行隔离。Vlan是做什么的vlan是virtuallan(虚拟局域47举个例子举个例子48802.1q帧格式802.1q帧格式49802.1q帧格式说明802.1Q封装共4个字节，包含2个部分：TPID(Etype),TagControlInfo；

TPID:长度为2个字节，固定为0x8100,标识报文的封装类型为以太网的802.1Q封装；

TagControlInfo：包含三个部分：802.1P优先级、CFI、VLAN-ID；802.1PPriority：这3位指明帧的优先级。一共有8种优先级,取值范围为0~7,，主要用于当交换机出端口发生拥塞时,交换机通过识别该优先级,优先发送优先级高的数据包。CFI：以太网交换机中，规范格式指示器总被设置为0。由于兼容特性，CFI常用于以太网类网络和令牌环类网络之间，如果在以太网端口接收的帧具有CFI，那么设置为1，表示该帧不进行转发，这是因为以太网端口是一个无标签端口。VID：VLANID是对VLAN的识别字段，在标准802.1Q中常被使用。该字段为12位。支持4096（2^12）VLAN的识别。在4096可能的VID中，VID＝0用于识别帧优先级，4095（FFF）作为预留值，所以VLAN配置的最大可能值为4094。802.1q帧格式说明802.1Q封装共4个字节，包含2个部50802.1q帧与标准以太网帧相互转换明确交换机接收和发送的报文是带tag的还是不带tag的。VLAN成员的连接方式分为三种：Access,Trunk,Hybrid;

Access连接：报文不带tag标签,一般用于和tag-unaware(不支持802.1Q封装)设备相连，或者不需要区分不同VLAN成员时使用；

Trunk连接：在PVID所属的VLAN不带tag标签转发,其他VLAN中的报文都必须带tag标签，用于tag-aware(支持802.1Q封装)设备相连，一般用于交换机之间的互连；

Hybrid连接：可根据需要设置某些VLAN报文带tag,某些报文不带tag。与trunk连接最大的不同在于，trunk连接只有PVID所属的VLAN不带tag,其他VLAN都必须带tag,而Hybrid连接是可以设置多个VLAN不带tag；802.1q帧与标准以太网帧相互转换明确交换机接收和发送的报51不同类型的端口对tag处理方式

报文入方向：在入方向上，交换机的根本任务就是决定该报文是否允许进入该端口，根据入报文的tag/untag的属性以及端口属性，细分为如下情况：1)

报文为untag:允许报文进入该端口，并打上PVID的VLANtag,与端口属性无关；2)

报文为tag:在这种情况下，需要交换机来判断是否允许该报文进入端口；

Access端口：PVID和报文中tag标明的VLAN一致，接收并处理报文；否则丢弃。

Trunk/Hybrid端口：如果端口允许tag中标明的VLAN通过，则接收并处理报文；否则丢弃。不同类型的端口对tag处理方式

报文入方向：52不同类型的端口对于tag的处理报文出方向：在出方向上，交换机已经完成对报文的转发，其根本任务就是在转发出端口时，是否携带tag转发出去，根据出端口属性，细分为如下情况：1)

Access端口：将标签剥掉，不带tag转发；2)

Trunk端口：报文所在VLAN和PVID相同，则报文不带tag；否则带tag；3)

Hybrid端口：报文所在VLAN配置为tag，则报文带tag；否则不带tag；不同类型的端口对于tag的处理报文出方向：53一个vlan标记原理的例子通过标记的原理来理解vlan通讯的行为特征。一个vlan标记原理的例子通过标记的原理来理解vlan通讯的54STP生成树协议为什么要使用stp：如果二层网络一旦产生环路，由于二层帧没有ttl的概念，帧会无限转发。如果没有环路，那么一旦出现单点故障，就会造成网络中断。因此stp一方面解决二层环路的无限转发问题，另一方面解决了网络冗余问题。注意二三层协议对于环路处理的区别。STP生成树协议为什么要使用stp：55一些基本的图论知识什么是图？从几何角度上讲，平面图有三个要素，点、线和面。我们所考虑的图是由点和边构成的集合。有向图与无向图边要素：边的权值一些基本的图论知识什么是图？56图的一些基本性质点的要素：概念：点的度数：指的是点上面包含边的数量。定理：一张图中全部点的度数的和是边总和的两倍。记：∑

d(v)=2*∑

count(e)图的一些基本性质点的要素：57图的一些基本性质推论：对于不含自环的无向的完全图，边的总数和点的关系如下：假设点的数量为n，边的总数为n*(n-1)/2因为完全图，每个点都与其他点有一条边相连，因此每个点的度数都为n-1,所有点的度数总和为n*(n-1)。因此总边数为n*(n-1)/2图的一些基本性质推论：58图的一些基本性质概念：连通图一张图内任何一点都有至少一条路径与图中其他任意点可达概念：连通度一张图去掉n条边后由连通图变成非连通图的n的最小值图的一些基本性质概念：连通图59树的一些基本性质树是边数最少的连通图，一个点与另外一点只有一条路径可达。树中点数和边数的关系：设树中点的个数为n，边的总数为n-1因此，一张连通图中边的总数的范围是：n-1

<=

count(e)<=

n*(n-1)/2树的一些基本性质树是边数最少的连通图，一个点与另外一点只有一60连通图的生成树概念：生成树生成树包含图中全部的点，并且边是图的子集，这样的树叫做图的生成树。概念：生成树的初等变换删掉树中的一条边，添加一条生成树关于图的补集的边。这个操作叫做生成树的初等变换。定理：一个图的生成树可以由任意一个生成树经过有限次初等变换得到连通图的生成树概念：生成树61生成树的数量与最小生成树问题1：我有一个80设备的网络规模，需要拉成一个树状网络，怎么布线能保证所使用的网线总长度最短？或者保证所使用的网线长度能保证在一个范围？问题2：一共有多少种可能的布线方法？这个总数决定了采用一种随机方法能够达到满足目标的概率。生成树的数量与最小生成树62完全图的生成树数量一下具有n个节点的完全图的生成树数量。先分析一下这个问题,n个节点的完全图的边数是n(n-1)/2,生成树的边数是n-1。但是并不是所有的n-1条边的所有组合都能组合成生成树。因此生成树的数量要小于C(n(n-1)/2,n-1)我们考察一下完全图的全部生成树构成，我们假设其中一点为树根。那么生成树的总数是树根度数为i（1<=i<=n-1）的全部生成树的总和完全图的生成树数量一下具有n个节点的完全图的生成树数量。63完全图的生成树S(n)=ΣSi(n)

(1<=i<=n-1)

如图：完全图的生成树S(n)=ΣSi(n)(1<=i<=n-64完全图生成树个数从图中可以看到，Sn-1(n)的生成树只有一种。即Sn-1(n)=1。如果我们能计算出Sk(n)和Sk+1(n)之间的关系，就可以采用迭代的方式用Sn-1来表示Sk。从图里面可以看出，Sk和Sk-1是有关系的，我们假T(Sk-1，Sk）是把Sk-1通过减枝得到的Sk的可行的操作的总数。可以看得出，对于Sk-1（n）中的任意一个生成树，把Sk-1变成Sk的方式是把除了与树根相连的k-1个边不动，剩下的边选一个剪到树根。剩下的边的总数为n-1-(k-1)=n-k。因为生成树一共有Sk-1(n)种，因此T(Sk-1,Sk)=(n-k)Sk-1(n)完全图生成树个数从图中可以看到，Sn-1(n)的生成树只有一65完全图生成树个数需要注意的是T(Sk-1,Sk)不等于Sk(n)因为可能会出现如下情况

完全图生成树个数需要注意的是T(Sk-1,Sk)不等于Sk66完全图生成树个数但是，可以从图中看出，T(Sk-1,Sk)=T(Sk,Sk-1)。即把Sk-1变到Sk的方法的总数等于把Sk变成Sk-1方法的总数。我们再来看看如何把Sk变成Sk-1。把Sk变成Sk-1的方式是取一个与Sk相邻的点，把这点下面的整个子树插到除了根节点以外的其他节点下面。Sk一共有k个相邻节点。假设第i个节点下面拥有ni个子节点。那么把这第i个节点插到其他节点的方法一共有n-1-ni种。那么把任意一个Sk变到Sk-1的方法数为(n-1-n1)+(n-1-n2)+…+(n-1-nk)=k(n-1)-(n1+n2+…nk)=k(n-1)-(n-1)=(k-1)(n-1)。因此，T(Sk,Sk-1)=(k-1)(n-1)Sk(n)完全图生成树个数但是，可以从图中看出，T(Sk-1,Sk)=67完全图生成树个数这样，我们就得到了一个关于Sk-1(n)和Sk(n)的表达式(n-k)Sk-1(n)=(k-1)(n-1)Sk(n)=>

Sk-1(n)=[(k-1)(n-1)/(n-k)]Sk(n)=>Sk(n)=[k(n-1)/(n-k-1)]Sk+1(n)=[k(n-1)/(n-k-1)][(k+1)(n-1)/(n-k-2)]Sk+2(n)=[k(n-1)/(n-k-1)][(k+1)(n-1)/(n-k-2)]…[(n-1)(n-2)/1]Sn-1(n)完全图生成树个数这样，我们就得到了一个关于Sk-1(n)和S68完全图生成树个数Sk(n)=[(n-1)^(n-k-1)][(n-2)!/[(n-k-1)!(k-1)!]]=[(n-1)^(n-k-1)]C(n-2,k-1)Sn=

∑Sk(n)(1<=k<=n-1)因此Sn=

∑Sk(n)=

∑[(n-1)^(n-k-1)]C(n-2,k-1)

(1<=k<=n-1)我们假设k-1=r

(0<=r<=n-2)于是Sn=

∑[(n-1)^(n-r)]C(n-2,r)

=

∑[(n-1)^(n-r)](1^r)C(n-2,r)

(0<=r<=n-2)完全图生成树个数Sk(n)=[(n-1)^(n-k-1)][69完全图生成树个数二项式定理（牛顿）：（a+b）^n=

∑[a^(n-r)](b^r)C(n,r)因此Sn=（n-1+1）^(n-2)=n^(n-2)完全图生成树个数二项式定理（牛顿）：70完全图生成树个数我们得到结论，完全图生成树的个数与完全图中点的关系的表达式是S(n)=n^(n-2)变化规律:S(1)=1,S(2)=1,S(3)=3,S(4)=16,S(5)=125,S(6)=1296…举个S(4)的例子：完全图生成树个数我们得到结论，完全图生成树的个数与完全图中点71完全图生成树的个数对于我们之前假设的80个点的情况，可能的布线方案一共有80^78种Log(80^78,base=10)=78*log(80,base=10)=148.4因此全部方案总数的数量级在10的148次方。经过理论推算，整个宇宙的原子的数量的在10的80次方左右。因此，从这些方案中挑出某个特别的方案会比从宇宙中挑出某一个特别的原子要难10^68+倍,完全图生成树的个数对于我们之前假设的80个点的情况，可能的布72最小生成树从上面的结论可以看出，随机从全部的生成树中找出一种特别的生成树是很难的。但是从这些生成树中找到最小或者是最大的却远没这么复杂。这是因为最小生成树有一种特别的性质能够快速的减少组合的规模。这个特性是局部最优解与全局最优解拥有一致性，让我们可以使用贪心算法来求解问题最小生成树从上面的结论可以看出，随机从全部的生成树中找出一种73贪心方法举个找零钱的例子：假设有1，2，5，10，20面额的钞票，想要找33块钱，保证找的钞票数量最少。找钱的办法是先找20，再找张10块的，再找张2块，最后找一张1块。每次都选最接近剩余的钱，就可以保证找的钞票最少。最小生成树也是同样的类似的性质，一张图中的最小边一定属于最小生成树。假设最小生成树中不包含最小边，那么把该边加入生成树，会得到一个环，这个环去掉另一个边也能得到一颗树，这颗树会比原来的最小生成树还要小，与假设矛盾。贪心方法举个找零钱的例子：74Prim算法和kruskal算法Prim算法例子：Prim算法和kruskal算法Prim算法例子：75Prim算法和kruskal算法Kruskal算法例子：Prim算法和kruskal算法Kruskal算法例子：76STP协议网络设备中的生成树算法和上述的计算机内存里的模拟算法有个本质的区别，网络设备的生成树的计算是分布式的，可并行的。每个计算节点对应于图中的一个点，每个节点的目的就是选出有哪些边应该属于生成树，哪些边应该减掉。因此，STP协议算法的逻辑非常接近prim算法。目前使用的是STP协议的优化版本RSTP，而非传统STP。STP协议网络设备中的生成树算法和上述的计算机内存里的模拟77STP协议STP协议通过BPDU（bridge

protocoldataunit）报文，STPBPDU是一种二层报文，目的MAC是多播地址01-80-C2-00-00-00，所有支持STP的网桥都会接收并处理收到的BPDU报文。该报文的数据区里携带了用于生成树计算的所有有用信息。BPDU分为两种，一种是为了计算生成树，叫做配置BPDU,另一种是为了通知拓扑变化,叫做tcn。STP协议STP协议通过BPDU（bridgeproto78STP算法简要描述首先进行根桥的选举。选举的依据是网桥优先级和网桥MAC地址组合成的桥ID，桥ID最小的网桥将成为网络中的根桥，它的所有端口都连接到下游桥，所以端口角色都成为指定端口。接下来，连接根桥的下游网桥将各自选择一条“最粗壮