網絡技術第二課內部技術培訓網絡技術第二課內部技術培訓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相關技術?，F在，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的可行的操作的總數?？梢钥吹贸觯瑢τ赟k-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最小的網橋將成為網絡中的根橋，它的所有端口都連接到下游橋，所以端口角色都成為指定端口。接下來，連接根橋的下游網橋將各自選擇一條“最粗壯