一種發送交叉命令的方法和裝置製造方法
2023-05-12 22:59:31 3
一種發送交叉命令的方法和裝置製造方法
【專利摘要】本發明公開了一種發送交叉命令的方法和裝置，涉及通信領域，能夠自動控制總的交叉命令發送時間，並使其達到時間最優。本發明提供的方法，應用於集中控制器中，網絡由p個節點構成，集中控制器通過該p個節點中的k個接入節點與網絡連接，p≥k≥2，k、p均為整數，該方法包括：基於網絡拓撲和k個接入節點獲取k個平衡單歸子樹；k個平衡單歸子樹由該p個節點構成，任意兩個平衡單歸子樹中的節點無交集，k個平衡單歸子樹中的節點數目平衡；按照每個平衡單歸子樹中的節點所在的層數從大到小的順序，向k個平衡單歸子樹中的節點並行發送交叉命令。
【專利說明】一種發送交叉命令的方法和裝置
【技術領域】
[0001]本發明涉及通信領域，尤其涉及一種發送交叉命令的方法和裝置。
【背景技術】
[0002]SDN (Software Defined Networking,軟體定義網絡)中的控制平面集中在網絡外部的一個獨立的控制器(集中控制器)上。SDN中重路由的過程為:LSP (Label SwitchedPath，標籤交換路徑)工作路徑上的某個鏈路兩端的節點檢測到該鏈路發生故障時，向集中控制器發送故障通告消息；集中控制器根據故障通告消息為該LSP計算恢復路徑(也可以稱為重路由路徑)，並向該恢復路徑上的所有節點發送交叉命令；當該恢復路徑上的所有節點均接收到交叉命令，並根據交叉命令建立本地交叉連接後，恢復路徑建立完成。
[0003]總的交叉命令發送時間(從集中控制器開始發送交叉命令的時刻到恢復路徑上的所有節點均接收到交叉命令的時刻所用的時間)與集中控制器發送交叉命令的順序有關。假設消息包在兩個節點之間的傳輸時延為I個單位時間，節點轉發消息包的轉發時延忽略不計，一般的，當恢復路徑的跳數是q時，總的交叉命令發送時間介於q+Ι個單位時間和2q+l個單位時間之間。
[0004]例如，參見圖1，LSP工作路徑為:節點1-節點6-節點7-節點5，節點6_節點7之間的鏈路發生故障時，得到的恢復路徑為:節點1-節點2-節點3-節點4-節點5 ;若按照「節點1、節點2、節點3、節點4、節點5」的順序發送交叉命令，則總的交叉命令發送時間為9個單位時間；若按照「節點5、節點4、節點3、節點2、節點I」的順序發送交叉命令，則總的交叉命令發送時間為5個單位時間。
[0005]目前，集中控制器一般按照隨機的順序發送交叉命令，隨機的順序導致總的交叉命令發送時間不可控，無法達到時間最優。
【發明內容】
[0006]本發明的實施例提供一種發送交叉命令的方法和裝置，可以自動控制總的交叉命令發送時間，並使其達到時間最優。
[0007]為達到上述目的，本發明的實施例採用如下技術方案:
[0008]一方面，提供一種發送交叉命令的方法，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的k個接入節點與所述網絡連接,P ^ k ^ 2, k>p均為整數，所述方法包括:
[0009]基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹；所述k個平衡單歸子樹由所述P個節點構成，任意兩個所述平衡單歸子樹中的節點無交集，k個所述平衡單歸子樹中的節點數目平衡；
[0010]按照每個所述平衡單歸子樹中的節點所在的層數從大到小的順序，向k個所述平衡單歸子樹中的節點並行發送交叉命令。
[0011]結合第一方面，在第一種可能的實現方式中，所述基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹，包括:
[0012]針對每個所述接入節點執行去除所述集中控制器與除該接入節點之外的k-Ι個接入節點之間的k-Ι個鏈路，得到k個不同的單歸網絡拓撲；
[0013]基於k個所述單歸網絡拓撲生成k個初始單歸子樹，所述k個初始單歸子樹為以所述集中控制器為根節點的k個最小生成樹；
[0014]確定k個所述初始單歸子樹中的P X (k-Ι)個可操作節點；
[0015]去除所述pX (k-Ι)個可操作節點，得到k個平衡單歸子樹。
[0016]結合第一方面的第一種可能的實現方式，在第二種可能的實現方式中，所述確定k個所述初始單歸子樹中的PX (k-Ι)個可操作節點，去除所述pX (k-Ι)個可操作節點，得到k個平衡單歸子樹，包括:
[0017]確定本次執行去除操作的執行對象，去除所述執行對象，所述執行對象為所述P X (k-Ι)個可操作節點中的一個；
[0018]所述確定本次執行去除操作的執行對象,包括:
[0019]在k個當前單歸子樹中，確定本次執行去除操作的子樹；所述當前單歸子樹是指當前網絡拓撲中的子樹，所述當前網絡拓撲是指上一次執行去除操作之後得到的網絡拓撲；所述本次執行去除操作的子樹中包含存在於其他k-Ι個當前單歸子樹中的節點；
[0020]將所述本次執行去除操作的子樹中的、存在於其他k-Ι個當前單歸子樹中的一個節點作為所述執行對象。
[0021]結合第一方面的第二種可能的實現方式，在第三種可能的實現方式中，所述在k個當前單歸子樹中，確定本次執行去除操`作的子樹，包括:
[0022]確定k個所述當前單歸子樹中的第一類子樹，所述第一類子樹為:包含其他k-Ι個當前單歸子樹中的節點的當前單歸子樹；
[0023]當所述第一類子樹中節點數量最多的當前單歸子樹有一個時，將所述第一類子樹中節點數量最多的當前單歸子樹作為本次執行去除操作的子樹，或者，
[0024]當所述第一類子樹中節點數量最多的當前單歸子樹有至少兩個時，將所述第一類子樹中節點數量最多、且層數最多的當前單歸子樹作為本次執行去除操作的子樹。
[0025]結合第一方面的第二種可能的實現方式或者第三種可能的實現方式，在第四種可能的實現方式中，所述將所述本次執行去除操作的子樹中的、存在於其他k-Ι個當前單歸子樹中的一個節點作為所述執行對象，包括:
[0026]當所述本次執行去除操作的子樹中的、存在於其他k-Ι個當前單歸子樹中的節點有至少兩個時，將所述至少兩個節點中所在層數最少的節點作為所述執行對象。
[0027]第二方面，提供一種發送交叉命令的方法，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的I個接入節點與所述網絡連接，P為大於等於I的整數，所述方法包括:
[0028]基於網絡拓撲和所述接入節點生成以所述集中控制器為根節點的最小生成樹；
[0029]按照所述最小生成樹中的節點所在的層數從大到小的順序向所述最小生成樹中的節點發送交叉命令。
[0030]第三方面，提供一種發送交叉命令的裝置，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的k個接入節點與所述網絡連接,P ^ k ^ 2,k>P均為整數，所述裝置包括:
[0031]獲取單元，用於基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹；所述k個平衡單歸子樹由所述P個節點構成，任意兩個所述平衡單歸子樹中的節點無交集，k個所述平衡單歸子樹中的節點數目平衡；
[0032]發送單元，用於按照每個所述平衡單歸子樹中的節點所在的層數從大到小的順序，向k個所述平衡單歸子樹中的節點並行發送交叉命令。
[0033]結合第三方面，在第一種可能的實現方式中，所述獲取單元包括:
[0034]獲取子單元，用於針對每個所述接入節點執行去除所述集中控制器與除該接入節點之外的k-Ι個接入節點之間的k-Ι個鏈路，得到k個不同的單歸網絡拓撲；
[0035]生成子單元，用於基於k個所述單歸網絡拓撲生成k個初始單歸子樹，所述k個初始單歸子樹為以所述集中控制器為根節點的k個最小生成樹；
[0036]確定子單元，用於確定k個所述初始單歸子樹中的pX (k-Ι)個可操作節點；
[0037]去除子單元，用於去除所述pX (k-Ι)個可操作節點，得到k個平衡單歸子樹。
[0038]結合第三方面的第一種可能的實現方式，在第二種可能的實現方式中，所述確定子單元具體用於，確定本次執行去除操作的執行對象，並通知所述去除子單元去除所述執行對象，所述執行對象為所述PX (k-l)個可操作節點中的一個；
[0039]其中，所述確 定子單元具體用於:
[0040]在k個當前單歸子樹中，確定本次執行去除操作的子樹；所述當前單歸子樹是指當前網絡拓撲中的子樹，所述本次執行去除操作的子樹中包含存在於其他k-l個當前單歸子樹中的節點；
[0041]將所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的一個節點作為所述執行對象。
[0042]結合第三方面的第二種可能的實現方式，在第三種可能的實現方式中，所述確定子單元具體用於，
[0043]確定k個所述當前單歸子樹中的第一類子樹，所述第一類子樹為:包含其他k-l個當前單歸子樹中的節點的當前單歸子樹；
[0044]當所述第一類子樹中節點數量最多的當前單歸子樹有一個時，將所述第一類子樹中節點數量最多的當前單歸子樹作為本次執行去除操作的子樹，或者，
[0045]當所述第一類子樹中節點數量最多的當前單歸子樹有至少兩個時，將所述第一類子樹中節點數量最多、且層數最多的當前單歸子樹作為本次執行去除操作的子樹。
[0046]結合第三方面的第二種可能的實現方式或者第三種可能的實現方式，在第四種可能的實現方式中，
[0047]所述確定子單元具體用於，當所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的節點有至少兩個時，將所述至少兩個節點中所在層數最少的節點作為所述執行對象。
[0048]第四方面，提供一種發送交叉命令的裝置，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的k個接入節點與所述網絡連接,P ^ k ^ 2,k>P均為整數，所述裝置包括:
[0049]處理器，用於基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹；所述k個平衡單歸子樹由所述P個節點構成，任意兩個所述平衡單歸子樹中的節點無交集，k個所述平衡單歸子樹中的節點數目平衡；
[0050]發送器，用於按照每個所述平衡單歸子樹中的節點所在的層數從大到小的順序，向k個所述平衡單歸子樹中的節點並行發送交叉命令。
[0051]結合第四方面，在第一種可能的實現方式中，所述處理器具體用於，
[0052]針對每個所述接入節點執行去除所述集中控制器與除該接入節點之外的k-l個接入節點之間的k-l個鏈路，得到k個不同的單歸網絡拓撲；
[0053]基於k個所述單歸網絡拓撲生成k個初始單歸子樹，所述k個初始單歸子樹為以所述集中控制器為根節點的k個最小生成樹；
[0054]確定k個所述初始單歸子樹中的P X (k-l)個可操作節點；
[0055]去除所述pX (k-l)個可操作節點，得到k個平衡單歸子樹。
[0056]結合第四方面的第一種可能的實現方式，在第二種可能的實現方式中，所述處理器具體用於，確定本次執行去除操作的執行對象，去除所述執行對象，所述執行對象為所述P X (k-l)個可操作節點中的一個；
[0057]其中，所述確定子單元具體用於:
[0058]在k個當前單歸子樹中，確定本次執行去除操作的子樹；所述當前單歸子樹是指當前網絡拓撲中的子樹，所述當前網絡拓撲是指上一次執行去除操作之後得到的網絡拓撲；所述本次執行去除操作的子樹中包含存在於其他k-l個當前單歸子樹中的節點；
[0059]將所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的一個節點作為所述執行對象。
[0060]結合第四方面的第二種可能的實現方式，在第三種可能的實現方式中，所述處理器具體用於，
[0061]確定k個所述當前單歸子樹中的第一類子樹，所述第一類子樹為:包含其他k-l個當前單歸子樹中的節點的當前單歸子樹；
[0062]當所述第一類子樹中節點數量最多的當前單歸子樹有一個時，將所述第一類子樹中節點數量最多的當前單歸子樹作為本次執行去除操作的子樹，或者，
[0063]當所述第一類子樹中節點數量最多的當前單歸子樹有至少兩個時，將所述第一類子樹中節點數量最多、且層數最多的當前單歸子樹作為本次執行去除操作的子樹。
[0064]結合第四方面的第二種可能的實現方式或者第三種可能的實現方式，在第四種可能的實現方式中，所述處理器具體用於，當所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的節點有至少兩個時，將所述至少兩個節點中所在層數最少的節點作為所述執行對象。
[0065]第五方面，提供一種發送交叉命令的裝置，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的I個接入節點與所述網絡連接，P為大於等於I的整數，所述裝置包括:
[0066]獲取單元，用於基於網絡拓撲和所述接入節點生成以所述集中控制器為根節點的最小生成樹；
[0067]發送單元，用於按照所述最小生成樹中的節點所在的層數從大到小的順序向所述最小生成樹中的節點發送交叉命令。[0068]第六方面，提供一種發送交叉命令的裝置，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的I個接入節點與所述網絡連接，P為大於等於I的整數，所述裝置包括:
[0069]處理器，用於基於網絡拓撲和所述接入節點生成以所述集中控制器為根節點的最小生成樹；
[0070]發送器，用於按照所述最小生成樹中的節點所在的層數從大到小的順序向所述最小生成樹中的節點發送交叉命令。
[0071]本發明實施例提供的發送交叉命令的方法和裝置，提供了發送交叉命令的固定順序，因此可以自動控制總的交叉命令發送時間；另外，本方案中集中控制器將網絡拆分成k個平衡單歸子樹、並行發送方式以及該固定順序的設置使得總的交叉命令發送時間達到最優；或者，基於網絡拓撲生成以集中控制器為根節點的最小生成樹以及該固定順序的設置使得總的交叉命令發送時間達到最優。解決了現有技術中，隨機順序導致的總的交叉命令發送時間不可控，無法達到時間最優的問題。
【專利附圖】
【附圖說明】
[0072]為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。
[0073]圖1為現有技術中的一種發送交叉命令的方法的示意圖；
[0074]圖2為實施例一提供的一種發送交叉命令的方法的流程圖；
[0075]圖3為實施例二提供的一種發送交叉命令的方法的流程圖；
[0076]圖4為實施例二提供的一種單歸接入場景的示意圖；
[0077]圖5為為基於圖4生成的以集中控制器為根節點的最小生成樹的示意圖；
[0078]圖6為實施例三提供的一種發送交叉命令的方法的流程圖；
[0079]圖7為實施例1提供的一種雙歸接入場景的示意圖；
[0080]圖8為基於圖7生成的初始單歸子樹的示意圖；
[0081]圖9 (a)為基於圖8生成平衡單歸子樹的過程的示意圖；
[0082]圖9 (b)為基於圖9 Ca)生成平衡單歸子樹的過程的示意圖；
[0083]圖9 (C)為基於圖9 (b)生成平衡單歸子樹的過程的示意圖；
[0084]圖9 Cd)為基於圖9 (C)生成的平衡單歸子樹的示意圖；
[0085]圖10為實施例2提供的一種多歸接入場景的示意圖；
[0086]圖11為基於圖10生成的初始單歸子樹的示意圖；
[0087]圖12為基於圖11生成的平衡單歸子樹的示意圖；
[0088]圖13為實施例四提供的一種發送交叉命令的裝置的結構圖；
[0089]圖14為實施例四提供的另一種發送交叉命令的裝置的結構圖；
[0090]圖15為實施例五提供的一種發送交叉命令的裝置的結構圖；
[0091]圖16為實施例六提供的一種發送交叉命令的裝置的結構圖；
[0092]圖17為實施例七提供的一種發送交叉命令的裝置的結構圖。【具體實施方式】
[0093]下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
[0094]實施例一
[0095]參見圖2，為本發明實施例提供的一種發送交叉命令的方法，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的k個接入節點與所述網絡連接，P≥k≥2，k、P均為整數，所述方法包括:
[0096]201:基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹；所述k個平衡單歸子樹由所述P個節點構成，任意兩個所述平衡單歸子樹中的節點無交集，k個所述平衡單歸子樹中的節點數目平衡。
[0097]其中，本方案可以應用於SDN中。
[0098]本實施例中k ^ 2，也就是說，集中控制器通過至少兩個(接入)節點與網絡連接。一般地，將集中控制器通過兩個(接入)節點與網絡連接的場景稱為雙歸接入場景，將集中控制器通過兩個以上的(接入)節點與網絡連接的場景稱為多歸接入場景。本方案的執行主體可以為集中控制器。
[0099]網絡拓撲由該網絡中的P節點以及該P個節點之間的連接關係構成。
[0100]任意兩個平衡單歸子樹中的節點無交集，說明:若P個節點中的某一節點在一平衡單歸子樹中，則該節點不會存在於除該平衡單歸子樹之外的其他k-l個平衡單歸子樹中。
[0101]k個平衡單歸子樹中的節點數目平衡是指，k個平衡單歸子樹中的任意兩個單歸子樹中的節點數目儘量相等，其中，任意兩個平衡單歸子樹中的節點數目之間的差值^k-10例如，若p=8，k=2，則k個平衡單歸子樹中每個平衡單歸子樹可以分別包含4個節點等；又如，若p=16，k=3，則k個平衡單歸子樹中可以分別包含6個節點、5個節點、5個節點，也可以分別包含6個節點、6個節點、4個節點等。
[0102]202:按照每個所述平衡單歸子樹中的節點所在的層數從大到小的順序，向k個所述平衡單歸子樹中的節點並行發送交叉命令。
[0103]示例性的，具體實現時，該步驟202可以為:使用k個進程向k個所述平衡單歸子樹中的節點發送交叉命令，每個進程對應I個所述平衡單歸子樹；在每個進程中按照該進程對應的平衡單歸子樹中的節點所在的層數從大到小的順序向該平衡單歸子樹中的節點發送交叉命令。其中，這裡的「進程」也可以稱為線程。
[0104]可選的，步驟201可以包括:
[0105]I)針對每個所述接入節點執行去除所述集中控制器與除該接入節點之外的k-l個接入節點之間的k-l個鏈路，得到k個不同的單歸網絡拓撲；
[0106]2)基於k個所述單歸網絡拓撲生成k個初始單歸子樹，所述k個初始單歸子樹為以所述集中控制器為根節點的k個最小生成樹；
[0107]3)確定k個所述初始單歸子樹中的P X (k-l)個可操作節點；[0108]4)去除所述pX (k-l)個可操作節點，得到k個平衡單歸子樹。
[0109]示例性的，在步驟I)中，集中控制器可以依次或者同時針對每個接入節點執行去除集中控制器與除該接入節點之外的k-l個接入節點之間的k-l個鏈路，從而得到k個不同的單歸網絡拓撲。
[0110]每個單歸網絡拓撲包含所述P個節點，k個初始單歸子樹共包含pXk個節點。
[0111]在步驟2)中，每個單歸網絡拓撲生成一個初始單歸子樹，且該過程中，節點的數量不變。也就是說，每個初始單歸子樹包含所述P個節點，k個初始單歸子樹共包含pXk個節點。
[0112]以集中控制器為根節點的最小生成樹的特徵是，集中控制器到樹中任意節點的跳數或者代價最小。其中，集中控制器可以利用現有技術中的任一種方法獲得以集中控制器為根節點的最小生成樹(即初始單歸子樹)。
[0113]在步驟4)中，由於k個初始單歸子樹共包含pXk個節點；且根據步驟201獲知k個平衡單歸子樹共包含P個節點。因此，k個初始單歸子樹中共包含P X (k-l)個可操作節點。
[0114]需要說明的是，具體實現時，集中控制器可以但不限於使用以下兩種方式實現步驟3)和步驟4):
[0115]方式1:先執行步驟3)再執行步驟4)，也就是說，先獲取到pX (k-l)個可操作節點，再去除該pX (k-l)個可操作節點。
[0116]方式2:執行pX (k-l)次循環過程，其中，在每個循環過程中，獲取I個可操作節點，並去除該可操作節點。
[0117]可選的，步驟3)和步驟4)可以包括:確定本次執行去除操作的執行對象，去除所述執行對象，所述執行對象為所述PX (k-l)個可操作節點中的一個。需要說明的是，該可選的方式為上述方式2中的循環過程。
[0118]其中，所述確定本次執行去除操作的執行對象，可以包括:
[0119]A)在k個當前單歸子樹中，確定本次執行去除操作的子樹；所述當前單歸子樹是指當前網絡拓撲中的子樹，所述當前網絡拓撲是指上一次執行去除操作之後得到的網絡拓撲；所述本次執行去除操作的子樹中包含存在於其他k-l個當前單歸子樹中的節點；
[0120]B)將所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的一個節點作為所述執行對象。
[0121]示例性的，本次執行去除操作可以包括--第1次執行去除操作至第pX (k-l)次執行去除操作中任意一次執行去除操作。其中，第1次執行去除操作時，k個當前單歸子樹為k個初始單歸子樹；第j次執行去除操作時，k個當前單歸子樹為第j-Ι次執行去除操作後的k個單歸子樹，其中I < j≤pX (k-l), j為整數。
[0122]進一步可選的，步驟A)可以包括:
[0123]確定k個所述當前單歸子樹中的第一類子樹，所述第一類子樹為:包含其他k-l個當前單歸子樹中的節點的當前單歸子樹；
[0124]當所述第一類子樹中節點數量最多的當前單歸子樹有一個時，將所述第一類子樹中節點數量最多的當前單歸子樹作為本次執行去除操作的子樹，或者，
[0125]當所述第一類子樹中節點數量最多的當前單歸子樹有至少兩個時，將所述第一類子樹中節點數量最多、且層數最多的當前單歸子樹作為本次執行去除操作的子樹。
[0126]示例性的，當第一類子樹中節點數量最多且層數最多的當前單歸子樹有至少兩個時，集中控制器可以選擇該至少兩個中的任意一個作為本次執行去除操作的子樹。
[0127]需要說明的是，本發明實施例對確定第一類子樹的具體方式不進行限定，例如，具體實現時，可以按照當前單歸子樹中包含的節點數量由大到小的順序，在k個當前單歸子樹中確定第一類子樹，具體可以參見實施例二。
[0128]進一步可選的，步驟B)可以包括:
[0129]當所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的節點有至少兩個時，將所述至少兩個節點中所在層數最少的節點作為所述執行對象。
[0130]示例性的，當該至少兩個節點中所在層數最少的節點有至少兩個時，集中控制器可以將其中任意一個作為執行對象。
[0131]需要說明的是，每個平衡單歸子樹對應一個樹發送時間，總的交叉命令發送時間為:k個平衡單歸子樹對應的k個樹發送時間中最大的樹發送時間。其中，樹發送時間是指，從集中控制器開始發送交叉命令的時刻到該(平衡單歸子)樹中的所有節點均接收到交叉命令的時刻所用的時間。
[0132]每層對應一個層發送時間，假設一個平衡單歸子樹包含m層，m≥1，m為整數，則該平衡單歸子樹對應的樹發送時間為:m層對應的m個層發送時間中最大的層發送時間。其中，層發送時間是指，從集中控制器開始發送交叉命令的時刻到該層中的所有節點均接收到交叉命令的時刻所用的時間。
[0133]本發明實施例提供的發送交叉命令的方法，基於網絡拓撲和k個接入節點獲取k個平衡單歸子樹，k ^ 2 ;並按照每個平衡單歸子樹中的節點所在的層數從大到小的順序，向k個平衡單歸子樹中的節點並行發送交叉命令。本方案提供了發送交叉命令的固定順序(在每個進程中按照該進程對應的平衡單歸子樹中的節點所在的層數從大到小的順序)，因此可以自動控制總的交叉命令發送時間；另外，本方案中集中控制器將網絡拆分成k個平衡單歸子樹、並行發送方式以及該固定順序的設置使得總的交叉命令發送時間達到最優。解決了現有技術中，隨機順序導致的總的交叉命令發送時間不可控，無法達到時間最優的問題。
[0134]實施例二
[0135]參見圖3，為本發明實施例提供的一種發送交叉命令的方法，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的I個接入節點與所述網絡連接，P為大於等於I的整數，所述方法包括:
[0136]301:基於網絡拓撲和所述接入節點生成以所述集中控制器為根節點的最小生成樹。
[0137]其中，本方案可以應用於SDN中，SDN架構可以包括:1個集中控制器和P個節點，P個節點構成一個網絡，集中控制器通過P個節點中的k個接入節點與該網絡連接。本實施例中k=l，也就是說，集中控制器僅通過一個(接入)節點與網絡連接，一般，將該場景稱為單歸接入場景。本方案的執行主體可以為集中控制器。
[0138]網絡拓撲由該網絡中的P節點以及該P個節點之間的連接關係構成。
[0139]以集中控制器為根節點的最小生成樹的特徵是，集中控制器到樹中任意節點的跳樹或者代價最小。集中控制器可以利用現有技術中的任一種方法獲得以集中控制器為根節點的最小生成樹。最小生成樹中包含該P個節點。
[0140]參見圖4，為一種單歸接入場景的示意圖，其中包括集中控制器和網絡拓撲。參見圖5，為基於圖4所示的網絡拓撲生成的以集中控制器為根節點的最小生成樹，該最小生成樹共包括m層。
[0141]302:按照所述最小生成樹中的節點所在的層數從大到小的順序向所述最小生成樹中的節點發送交叉命令。
[0142]需要說明的是，每層對應一個層發送時間，假設最小生成樹包含m層，m為大於等於I的整數，則總的交叉命令發送時間為:m層對應的m個層發送時間中最大的層發送時間。其中，層發送時間是指從集中控制器開始發送交叉命令的時刻到該層中的所有節點均接收到交叉命令的時刻所用的時間。
[0143]下面說明最小生成樹中每層對應的層發送時間:
[0144]假設消息包在兩個節點之間的傳輸時延為I個單位時間，節點轉發消息包的轉發時延忽略不計，並將最小生成樹的第i層包含的節點的數量表示為n(i)，將第m層節點的層發送時間表示為t(m)，總的交叉命令發送時間表示為t。n(l)=l。
[0145]按照步驟302中的順序發送交叉命令，則:
[0146]第m層節點的層發送時間為:t(m)=m+n(m) -1 ；
[0147]第m-1 層節點的層發送時間為:t(m-l)=t(m)+n(m-l)-l=m+n(m)+n(m-l) - 2 ；
[0148]第m-2 層節點的層發送時間為:t (m-2) =t (m-1) +n (m_2) -l=m_3+n (m) +n (m-1) +n (m_2)；
[0149]......[0150]第I層節點的層發送時間為:t⑴=n(m)+n(m-l)+…+η⑵+η⑴。
[0151]總的交叉命令發送時間:〖=祖乂(〖(1)3(2)^"3(!11))，其中祖乂函數表示求輸入參數中的最大值。本實施例中的總的交叉命令發送時間為樹發送時間。
[0152]由總的交叉命令發送時間的公式可知:
[0153]I)總的交叉命令發送時間隨著樹中的總節點數量的增大而增大；
[0154]2)總命令發送時間隨著樹的層數的增大而增大。
[0155]本發明實施例提供的發送交叉命令的方法，基於網絡拓撲，生成以集中控制器為根節點的最小生成樹；並按照該最小生成樹中的節點所在的層數從大到小的順序向該最小生成樹中的節點發送交叉命令。本方案提供了發送交叉命令的固定順序(按照該最小生成樹中的節點所在的層數從大到小的順序向該最小生成樹中的節點發送交叉命令)，因此可以自動控制總的交叉命令發送時間；另外，基於網絡拓撲生成以集中控制器為根節點的最小生成樹以及該固定順序的設置使得總的交叉命令發送時間達到最優。解決了現有技術中，隨機順序導致的總的交叉命令發送時間不可控，無法達到時間最優的問題。
[0156]實施例三
[0157]參見圖6，為本發明實施例提供的一種發送交叉命令的方法，應用於集中控制器中，網絡由P個節點構成，集中控制器通過P個節點中的k個接入節點接入網絡，p=8, k=2,該方法包括: [0158]601:集中控制器針對每個接入節點執行去除集中控制器與除該接入節點之外的k-l個接入節點之間的k-l個鏈路，得到k個不同的單歸網絡拓撲。
[0159]602:基於k個單歸網絡拓撲生成k個初始單歸子樹，k個初始單歸子樹為以集中控制器為根節點的k個最小生成樹。
[0160]以下步驟603-步驟613為由k個初始單歸子樹生成k個平衡單歸子樹的過程。其中，步驟603-步驟610為確定本次執行去除操作的子樹的過程，步驟601-步驟613為確定本次執行去除操作的執行對象的過程。
[0161]603:確定k個當前單歸子樹中節點數量為w的b個當前單歸子樹。
[0162]其中，w為k個當前單歸子樹中，節點數量最多的當前單歸子樹的節點數；b為節點數量為w的當前單歸子樹個數，b ^ I, b為整數。
[0163]第1次執行步驟603時，k個當前單歸子樹具體為k個初始單歸子樹。
[0164]604:判斷該b個當前單歸子樹中是否包含存在於其他k-l個單歸子樹中的節點的當前單歸子樹。
[0165]若是，則執行步驟605 ;若否，則執行步驟609。
[0166]示例性的，當b=l時，該步驟604具體可以為:判斷b個當前單歸子樹中是否包含存在於其他k-l個單歸子樹中的節點。例如，例如，k個當前單歸子樹為子樹1、子樹2、子樹3，且b個當前單歸子樹為子樹I時，判斷子樹I中是否包含存在於子樹2和子樹3中的節點。
[0167]當b > 2時，該步驟604具體可以為:分別判斷b個當前單歸子樹中是否包含存在於其他k-l個單歸子樹中的節點。例如，k個當前單歸子樹為子樹1、子樹2、子樹3，b個當前單歸子樹為子樹1、子樹2，則步驟604具體為:分別判斷子樹I中是否包含存在於子樹2和子樹3中的節點，子樹2中是否包含存在於子樹I和子樹3中的節點。該情況下，當該b個當前單歸子樹中的任意一個當前單歸子樹中包含存在於其他k-l個單歸子樹中的節點時，判斷結果為是。
[0168]需要說明的是，k個當前單歸子樹中的任意一個子樹中包含存在於其他k-l個單歸子樹中的節點的當前單歸子樹，則說明有可操作的節點(執行對象)。
[0169]605:確定該b個當前單歸子樹中包含的存在於其他k-l個單歸子樹中的節點的當前單歸子樹的個數C。
[0170]其中，c≥1，c為整數。
[0171]606:判斷c是否等於I。
[0172]若是，則執行步驟607 ;若否，則執行步驟608。
[0173]607:將節點數量為w的、包含存在於其他k-l個單歸子樹中的節點的當前單歸子樹作為本次執行去除操作的子樹。
[0174]在步驟607之後，執行步驟609。
[0175]608:確定該c個當前單歸子樹中層數最多的一個當前單歸子樹作為本次執行去除操作的子樹。
[0176] 示例性的，當該c個當前單歸子樹中層數最多的當前單歸子樹有至少兩個時，集中控制器可以選擇該至少兩個中的任意一個作為本次執行去除操作的子樹。
[0177]在步驟608之後，執行步驟609。
[0178]609:判斷本次執行去除操作的子樹中的層數最多的節點中，存在於其他k-l個當前單歸子樹的節點的個數r是否等於I。
[0179]若是，則執行步驟610 ;若否，則執行步驟611。
[0180]610:將本次執行去除操作的子樹中的層數最多的節點中，存在於其他k-l個當前單歸子樹的節點作為執行對象。
[0181]步驟610之後，執行步驟612。
[0182]611:將r個節點中，在其他k_l個子樹中層數最少的節點作為執行對象。
[0183]該r個節點為:本次執行去除操作的子樹中的層數最多的節點中，存在於其他k-l個當前單歸子樹的節點。
[0184]示例性的，若r個節點中，在其他k-l個子樹中層數最少的節點有至少兩個時，選擇其中任一個作為執行對象。
[0185]612:去除該執行對象。
[0186]步驟612之後，返回步驟603。
[0187]613:判斷k個當前單歸子樹的節點數之和是否等於P X k。
[0188]若是，則執行步驟615 ;若否，則執行步驟614。
[0189]示例性的，當判斷結果是時，說明不存在可操作的節點(執行對象)，即k個當前單歸子樹為k個平衡單歸子樹；反之，則說明存在可操作的節點(執行對象)，即k個當前單歸子樹不為k個平衡單歸子樹。
[0190]需要說明的是，步驟613還可以為確定k個當前單歸子樹中是否包含可操作節點的任一種方式。
[0191]614:將 w 減 I。
[0192]執行步驟614之後，返回步驟603。
[0193]615:使用k個進程向該k個平衡單歸子樹中的節點發送交叉命令，每個進程對應I個平衡單歸子樹；在每個進程中按照該進程對應的平衡單歸子樹中的節點所在的層數從大到小的順序向該平衡單歸子樹中的節點發送交叉命令。
[0194]本發明實施例提供的發送交叉命令的方法，基於網絡拓撲和k個接入節點獲取k個平衡單歸子樹，k ^ 2 ;並使用k個進程並行發送交叉命令，每個進程對應一個平衡單歸子樹，在每個進程中按照該進程對應的平衡單歸子樹中的節點所在的層數從大到小的順序向該平衡單歸子樹中的節點發送交叉命令。本方案提供了發送交叉命令的固定順序(在每個進程中按照該進程對應的平衡單歸子樹中的節點所在的層數從大到小的順序)，因此可以自動控制總的交叉命令發送時間；另外，本方案中集中控制器將網絡拆分成k個平衡單歸子樹、並行發送方式以及該固定順序的設置使得總的交叉命令發送時間達到最優。解決了現有技術中，隨機順序導致的總的交叉命令發送時間不可控，無法達到時間最優的問題。
[0195]下面通過以具體的例子對實施例三進行說明。
[0196]實施例1
[0197]參見圖7，為本發明實施例提供的一種雙歸接入場景的示意圖，該場景包括集中控制器、8個節點。8個節點分別表示為:節點1、節點2、節點3、…、節點8，集中控制器與節點I和節點8與網絡連接，也就是說，節點I和節點8為接入節點。
[0198]該情況下，步 驟601具體為:集中控制器去除集中控制器與節點8之間的鏈路，得到單歸網絡拓撲I ;去除集中控制器與節點2之間的鏈路，得到單歸網絡拓撲2。[0199]步驟602具體為:基於單歸網絡拓撲I和單歸網絡拓撲2生成2個最小生成樹，SP2個初始單歸子樹，分別標記為子樹I和子樹2,如圖8所不。
[0200]例舉第I次和第2次執行步驟603-613的具體過程:
[0201]第I次執行步驟603-613時，w=8,步驟603中確定的節點數量為8的b個當前單歸子樹為子樹I和子樹2 ;步驟604判斷的結果為:子樹I中包含存在於子樹2中的節點，子樹2中包含存在於子樹I中的節點；步驟605中確定的c=2 ;因此步驟606的判斷結果為否，需要通過步驟608確定本次執行去除操作的子樹。確定的本次執行去除操作的子樹為子樹2。
[0202]由於本次執行去除操作的子樹(子樹2)中的層數最多的節點中，存在於其他k-l個當前單歸子樹的節點的個數為3，分別為節點2、節點3、節點4，因此需要通過步驟613確定執行對象。具體的，由於在其他k-l個子樹中層數最少的節點的個數為3，分別為節點2、節點3、節點4，因此可以選擇該3個節點中的任意一個作為執行對象，本實施例中選擇節點2作為執行對象。
[0203]第2次執行步驟603-613時，w=8，步驟603中確定的節點數量為8的b個當前單歸子樹為子樹I ;步驟604判斷的結果為是，具體的判斷結果為:子樹I中包含存在於子樹2中的節點；步驟605中確定的c=l ;因此步驟606的判斷結果為是，需要通過步驟607確定本次執行去除操作的子樹。確定的本次執行去除操作的子樹為子樹I。
[0204]由於本次執行去除操作的子樹(子樹I)中的層數最多的節點中，存在於其他k-l個當前單歸子樹的節點的個數為1，為節點8，因此需要通過步驟612確定執行對象。確定的執行對象為節點8。
[0205]按照上述步驟，由2個初始單歸子樹生成2個平衡單歸子樹的過程可參見圖9(a)-圖9 (d)。具體的:
[0206]第1、2次執行步驟603-613:去除子樹2中的節點2、子樹I中的節點8，去除結果如圖9 Ca)所示；
[0207]第3、4次執行步驟603-613:去除子樹2中的節點3，子樹I中的節點7，去除結果如圖9 (b)所示；
[0208]第5、6次執行步驟603-613:去除子樹2中的節點4，子樹I中的節點6，去除結果如圖9 (c)所示；
[0209]第7、8次執行步驟603-613:去除子樹2中的節點I，去除子樹I中的節點5，去除結果如圖9 Cd)所示。
[0210]第9次執行步驟603-613的過程中，在執行步驟609之後，直接執行步驟615，說明:圖9 Cd)所示的去除結果為得到的2個平衡單歸子樹。
[0211]每個平衡單歸子樹的樹發送時間的計算方法可以參見實施例二，此處不再贅述。經計算可知，該2個平衡單歸子樹的樹發送時間均為4個單位時間，因此總的交叉命令的發送時間為4個單位時間。
[0212]實施例2
[0213]參見圖10，為本發明實施例提供的一種多歸接入場景的示意圖，該場景包括集中控制器、16個節點。16個節點分別表示為:節點1、節點2、節點3、...、節點16，集中控制器與節點1、節點2和節點4與網絡連接，也就是說，節點1、節點2和節點4為接入節點。[0214]參見圖11，為執行步驟601和602之後得到的3初始單歸子樹的示意圖，包括子樹
1、子樹2、子樹3。
[0215]由3個初始單歸子樹生成3個平衡單歸子樹的過程包括:依次去除子樹I中的節點16、子樹3中的節點13、子樹2中的節點16，子樹I中的節點12、子樹3中的節點9、子樹2中的節點12，子樹I中的節點15、子樹3中的節點14、子樹2中的節點13，子樹I中的節點8、子樹3中的節點5、子樹2中的節點15，子樹I中的節點14、子樹3中的節點10、子樹2中的節點8，子樹I中的節點11、子樹3中的節點9、子樹2中的節點1，子樹I中的節點4、子樹3中的節點11、子樹2中的節點6，子樹I中的節點10、子樹3中的節點2、子樹2中的節點4，子樹I中的節點7、子樹3中的節點5、子樹2中的節點7，子樹I中的節點6、子樹3中的節點1、子樹2中的節點3，子樹I中的節點3，子樹I中的節點2。最終得到的3個平衡單歸子樹如圖12所不的子樹1、子樹2和子樹3。 [0216]每個平衡單歸子樹的樹發送時間的計算方法可以參見實施例二，此處不再贅述。經計算可知，子樹I的樹發送時間為4個單位時間，子樹2的樹發送時間為6個單位時間，子樹3的樹發送時間為6個單位時間，因此，總的交叉命令的發送時間為6個單位時間。
[0217]實施例四
[0218]參見圖13，為本發明實施例提供的一種發送交叉命令的裝置，應用於集中控制器中，用以執行圖2所示的發送交叉命令的方法，網絡由P個節點構成，所述集中控制器通過所述P個節點中的k個接入節點與所述網絡連接，P≥k≥2, k、P均為整數,所述裝置包括:
[0219]獲取單元13A，用於基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹；所述k個平衡單歸子樹由所述P個節點構成，任意兩個所述平衡單歸子樹中的節點無交集，k個所述平衡單歸子樹中的節點數目平衡；
[0220]發送單元13B，用於按照每個所述平衡單歸子樹中的節點所在的層數從大到小的順序，向k個所述平衡單歸子樹中的節點並行發送交叉命令。
[0221]可選的，參見圖14，所述獲取單元13A包括:
[0222]獲取子單元13A1，用於針對每個所述接入節點執行去除所述集中控制器與除該接入節點之外的k-l個接入節點之間的k-l個鏈路，得到k個不同的單歸網絡拓撲；
[0223]生成子單元13A2，用於基於k個所述單歸網絡拓撲生成k個初始單歸子樹，所述k個初始單歸子樹為以所述集中控制器為根節點的k個最小生成樹；
[0224]確定子單元13A3，用於確定k個所述初始單歸子樹中的pX (k-l)個可操作節點；
[0225]去除子單元13A4，用於去除所述pX (k-l)個可操作節點，得到k個平衡單歸子樹。
[0226]可選的，所述確定子單元13A3具體用於，確定本次執行去除操作的執行對象，並通知所述去除子單元13A4去除所述執行對象，所述執行對象為所述pX (k-l)個可操作節點中的一個；
[0227]其中，所述確定子單元13A3具體用於:
[0228]在k個當前單歸子樹中，確定本次執行去除操作的子樹；所述當前單歸子樹是指當前網絡拓撲中的子樹，所述當前網絡拓撲是指上一次執行去除操作之後得到的網絡拓撲；所述本次執行去除操作的子樹中包含存在於其他k-l個當前單歸子樹中的節點；
[0229]將所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的一個節點作為所述執行對象。
[0230]可選的，所述確定子單元13A3具體用於，
[0231]確定k個所述當前單歸子樹中的第一類子樹，所述第一類子樹為:包含其他k-l個當前單歸子樹中的節點的當前單歸子樹；
[0232]當所述第一類子樹中節點數量最多的當前單歸子樹有一個時，將所述第一類子樹中節點數量最多的當前單歸子樹作為本次執行去除操作的子樹，或者，
[0233]當所述第一類子樹中節點數量最多的當前單歸子樹有至少兩個時，將所述第一類子樹中節點數量最多、且層數最多的當前單歸子樹作為本次執行去除操作的子樹。
[0234]可選的，所述確定子單元13A3具體用於，當所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的節點有至少兩個時，將所述至少兩個節點中所在層數最少的節點作為所述執行對象。
[0235]本發明實施例提供的發送交叉命令的裝置，基於網絡拓撲和k個接入節點獲取k個平衡單歸子樹，k ^ 2 ;並按照每個平衡單歸子樹中的節點所在的層數從大到小的順序，向k個平衡單歸子樹中的節點並行發送交叉命令。本方案提供了發送交叉命令的固定順序(在每個進程中按照該進程對應的平衡單歸子樹中的節點所在的層數從大到小的順序)，因此可以自動控制總的交叉命令發送時間；另外，本方案中集中控制器將網絡拆分成k個平衡單歸子樹、並行發送方式以及該固定順序的設置使得總的交叉命令發送時間達到最優。解決了現有技術中，隨機順序導致的總的交叉命令發送時間不可控，無法達到時間最優的問題。
[0236]實施例五
[0237]參見圖15，為本發明實施例提供的一種發送交叉命令的裝置，應用於集中控制器中，用以執行圖2所示的發送交叉命令的方法，網絡由P個節點構成，所述集中控制器通過所述P個節點中的k個接入節點與所述網絡連接，P≥k≥2, k、P均為整數,所述裝置包括:
[0238]處理器15A，用於基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹；所述k個平衡單歸子樹由所述P個節點構成，任意兩個所述平衡單歸子樹中的節點無交集，k個所述平衡單歸子樹中的節點數目平衡；
[0239]發送器15B，用於按照每個所述平衡單歸子樹中的節點所在的層數從大到小的順序，向k個所述平衡單歸子樹中的節點並行發送交叉命令。
[0240]可選的，所述處理器15A具體用於，
[0241]針對每個所述接入節點執行去除所述集中控制器與除該接入節點之外的k-l個接入節點之間的k-l個鏈路，得到k個不同的單歸網絡拓撲；
[0242]基於k個所述單歸網絡拓撲生成k個初始單歸子樹，所述k個初始單歸子樹為以所述集中控制器為根節點的k個最小生成樹；
[0243]確定k個所述初始單歸子樹中的pX (k-l)個可操作節點；
[0244]去除所述pX (k-l)個可操作節點，得到k個平衡單歸子樹。
[0245]可選的，所述處理器15A具體用於，確定本次執行去除操作的執行對象，去除所述執行對象，所述執行對象為所述PX (k-ι)個可操作節點中的一個；
[0246]所述處理器15A具體用於:[0247]在k個當前單歸子樹中，確定本次執行去除操作的子樹；所述當前單歸子樹是指當前網絡拓撲中的子樹，所述當前網絡拓撲是指上一次執行去除操作之後得到的網絡拓撲；所述本次執行去除操作的子樹中包含存在於其他k-l個當前單歸子樹中的節點；
[0248]將所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的一個節點作為所述執行對象。
[0249]可選的，所述處理器15A具體用於，
[0250]確定k個所述當前單歸子樹中的第一類子樹，所述第一類子樹為:包含其他k-l個當前單歸子樹中的節點的當前單歸子樹；
[0251]當所述第一類子樹中節點數量最多的當前單歸子樹有一個時，將所述第一類子樹中節點數量最多的當前單歸子樹作為本次執行去除操作的子樹，或者，
[0252]當所述第一類子樹中節點數量最多的當前單歸子樹有至少兩個時，將所述第一類子樹中節點數量最多、且層數最多的當前單歸子樹作為本次執行去除操作的子樹。
[0253]可選的，所述處理器15A具體用於，當所述本次執行去除操作的子樹中的、存在於其他k-l個當前單歸子樹中的節點有至少兩個時，將所述至少兩個節點中所在層數最少的節點作為所述執行對象。
[0254]本發明實施例提供的發送交叉命令的裝置，基於網絡拓撲和k個接入節點獲取k個平衡單歸子樹，k ^ 2 ;並按照每個平衡單歸子樹中的節點所在的層數從大到小的順序，向k個平衡單歸子樹中的節點並行發送交叉命令。本方案提供了發送交叉命令的固定順序(在每個進程中按照該 進程對應的平衡單歸子樹中的節點所在的層數從大到小的順序)，因此可以自動控制總的交叉命令發送時間；另外，本方案中集中控制器將網絡拆分成k個平衡單歸子樹、並行發送方式以及該固定順序的設置使得總的交叉命令發送時間達到最優。解決了現有技術中，隨機順序導致的總的交叉命令發送時間不可控，無法達到時間最優的問題。
[0255]實施例六
[0256]參見圖16，為本發明實施例提供的一種發送交叉命令的裝置，應用於集中控制器中，用以執行圖3所示的發送交叉命令的方法，網絡由P個節點構成，所述集中控制器通過所述P個節點中的I個接入節點與所述網絡連接，P為大於等於I的整數，所述裝置包括:
[0257]獲取單元16A，用於基於網絡拓撲和所述接入節點生成以所述集中控制器為根節點的最小生成樹；
[0258]發送單元16B，用於按照所述最小生成樹中的節點所在的層數從大到小的順序向所述最小生成樹中的節點發送交叉命令。
[0259]本發明實施例提供的發送交叉命令的裝置，基於網絡拓撲，生成以集中控制器為根節點的最小生成樹；並按照該最小生成樹中的節點所在的層數從大到小的順序向該最小生成樹中的節點發送交叉命令。本方案提供了發送交叉命令的固定順序(按照該最小生成樹中的節點所在的層數從大到小的順序向該最小生成樹中的節點發送交叉命令)，因此可以自動控制總的交叉命令發送時間；另外，基於網絡拓撲生成以集中控制器為根節點的最小生成樹以及該固定順序的設置使得總的交叉命令發送時間達到最優。解決了現有技術中，隨機順序導致的總的交叉命令發送時間不可控，無法達到時間最優的問題。
[0260]實施例七[0261]參見圖17，為本發明實施例提供的一種發送交叉命令的裝置，應用於集中控制器中，用以執行圖3所示的發送交叉命令的方法，網絡由P個節點構成，所述集中控制器通過所述P個節點中的I個接入節點與所述網絡連接，P為大於等於I的整數，所述裝置包括:
[0262]處理器17A，用於基於網絡拓撲和所述接入節點生成以所述集中控制器為根節點的最小生成樹；
[0263]發送器17B，用於按照所述最小生成樹中的節點所在的層數從大到小的順序向所述最小生成樹中的節點發送交叉命令。
[0264]本發明實施例提供的發送交叉命令的裝置，基於網絡拓撲，生成以集中控制器為根節點的最小生成樹；並按照該最小生成樹中的節點所在的層數從大到小的順序向該最小生成樹中的節點發送交叉命令。本方案提供了發送交叉命令的固定順序(按照該最小生成樹中的節點所在的層數從大到小的順序向該最小生成樹中的節點發送交叉命令)，因此可以自動控制總的交叉命令發送時間；另外，基於網絡拓撲生成以集中控制器為根節點的最小生成樹以及該固定順序的設置使得總的交叉命令發送時間達到最優。解決了現有技術中，隨機順序導致的總的交叉命令發送時間不可控，無法達到時間最優的問題。
[0265]所屬領域的技術人員可以清楚地了解到，為描述的方便和簡潔，上述描述的系統，裝置和單元的具體工作過程，可以參考前述方法實施例中的對應過程，在此不再贅述。
[0266]在本申請所提供的幾個實施例中，應該理解到，所揭露的系統，裝置和方法，可以通過其它的方式實現。例如，以上所描述的裝置實施例僅僅是示意性的，例如，所述單元的劃分，僅僅為一種邏輯功能劃分，實際實現時可以有另外的劃分方式，例如多個單元或組件可以結合或者可以集成到另一個系統，或一些特徵可以忽略，或不執行。另一點，所顯示或討論的相互之間的耦合或直接耦合或通信連接可以是通過一些接口，裝置或單元的間接耦合或通信連接，可以是電性，機械或其它的形式。
[0267]所述作為分離部件說明的單元可以是或者也可以不是物理上分開的，作為單元顯示的部件可以是或者也可以不是物理單元，即可以位於一個地方，或者也可以分布到多個網絡單元上。可以根據實際的需要選擇其中的部分或者全部單元來實現本實施例方案的目的。
[0268]另外，在本發明各個實施例中的各功能單元可以集成在一個處理單元中，也可以是各個單元單獨物理包括，也可以兩個或兩個以上單元集成在一個單元中。上述集成的單元既可以採用硬體的形式實現，也可以採用硬體加軟體功能單元的形式實現。
[0269]上述以軟體功能單元的形式實現的集成的單元，可以存儲在一個計算機可讀取存儲介質中。上述軟體功能單元存儲在一個存儲介質中，包括若干指令用以使得一臺計算機設備(可以是個人計算機，伺服器，或者網絡設備等)執行本發明各個實施例所述方法的部分步驟。而前述的存儲介質包括:U盤、移動硬碟、只讀存儲器(Read-Only Memory,簡稱ROM)、隨機存取存儲器(Random Access Memory,簡稱RAM)、磁碟或者光碟等各種可以存儲程序代碼的介質。
[0270]最後應說明的是:以上實施例僅用以說明本發明的技術方案，而非對其限制；儘管參照前述實施例對本發明進行了詳細的說明，本領域的普通技術人員應當理解:其依然可以對前述各實施例所記載的技術方案進行修改，或者對其中部分技術特徵進行等同替換；而這些修改或者替換，並不使相應技術方案的本質脫離本發明各實施例技術方案的精神和範圍。
【權利要求】
1.一種發送交叉命令的方法，其特徵在於，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的k個接入節點與所述網絡連接,P ^ k ^ 2, k>p均為整數，所述方法包括: 基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹；所述k個平衡單歸子樹由所述P個節點構成，任意兩個所述平衡單歸子樹中的節點無交集，k個所述平衡單歸子樹中的節點數目平衡； 按照每個所述平衡單歸子樹中的節點所在的層數從大到小的順序，向k個所述平衡單歸子樹中的節點並行發送交叉命令。
2.根據權利要求1所述的方法，其特徵在於，所述基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹,包括: 針對每個所述接入節點執行去除所述集中控制器與除該接入節點之外的k-Ι個接入節點之間的k-Ι個鏈路，得到k個不同的單歸網絡拓撲； 基於k個所述單歸網絡拓撲生成k個初始單歸子樹，所述k個初始單歸子樹為以所述集中控制器為根節點的k個最小生成樹； 確定k個所述初始單歸子樹中的P X (k-Ι)個可操作節點； 去除所述PX (k-Ι)個可操作節點，得到k個平衡單歸子樹。
3.根據權利要求2所述的方法，其特徵在於，所述確定k個所述初始單歸子樹中的pX(k-l)個可操作節點，去除所述pX(k-l)個可操作節點，得到k個平衡單歸子樹，包括: 確定本次執行去除操作的執行對象，去除所述執行對象，所述執行對象為所述P X (k-Ι)個可操作節點中的一個； 所述確定本次執行去除操作的執行對象，包括: 在k個當前單歸子樹中，確定本次執行去除操作的子樹；所述當前單歸子樹是指當前網絡拓撲中的子樹，所述當前網絡拓撲是指上一次執行去除操作之後得到的網絡拓撲；所述本次執行去除操作的子樹中包含存在於其他k-Ι個當前單歸子樹中的節點； 將所述本次執行去除操作的子樹中的、存在於其他k-Ι個當前單歸子樹中的一個節點作為所述執行對象。
4.根據權利要求3所述的方法，其特徵在於，所述在k個當前單歸子樹中，確定本次執行去除操作的子樹，包括: 確定k個所述當前單歸子樹中的第一類子樹，所述第一類子樹為:包含其他k-Ι個當前單歸子樹中的節點的當前單歸子樹； 當所述第一類子樹中節點數量最多的當前單歸子樹有一個時，將所述第一類子樹中節點數量最多的當前單歸子樹作為本次執行去除操作的子樹，或者， 當所述第一類子樹中節點數量最多的當前單歸子樹有至少兩個時，將所述第一類子樹中節點數量最多、且層數最多的當前單歸子樹作為本次執行去除操作的子樹。
5.根據權利要求3或4所述的方法，其特徵在於，所述將所述本次執行去除操作的子樹中的、存在於其他k-Ι個當前單歸子樹中的一個節點作為所述執行對象，包括: 當所述本次執行去除操作的子樹中的、存在於其他k-Ι個當前單歸子樹中的節點有至少兩個時，將所述至少兩個節點中所在層數最少的節點作為所述執行對象。
6.一種發送交叉命令的方法，其特徵在於，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的I個接入節點與所述網絡連接，P為大於等於I的整數，所述方法包括: 基於網絡拓撲和所述接入節點生成以所述集中控制器為根節點的最小生成樹； 按照所述最小生成樹中的節點所在的層數從大到小的順序向所述最小生成樹中的節點發送交叉命令。
7.—種發送交叉命令的裝置，其特徵在於，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的k個接入節點與所述網絡連接,P ≥ k ≥2, k>p均為整數，所述裝置包括: 獲取單元，用於基於網絡拓撲和所述k個接入節點獲取k個平衡單歸子樹；所述k個平衡單歸子樹由所述P個節點構成，任意兩個所述平衡單歸子樹中的節點無交集，k個所述平衡單歸子樹中的節點數目平衡； 發送單元，用於按照每個所述平衡單歸子樹中的節點所在的層數從大到小的順序，向k個所述平衡單歸子樹中的節點並行發送交叉命令。
8.根據權利要求7所述的裝置，其特徵在於，所述獲取單元包括: 獲取子單元，用於針對每個所述接入節點執行去除所述集中控制器與除該接入節點之外的k-Ι個接入節點之間的k-Ι個鏈路，得到k個不同的單歸網絡拓撲； 生成子單元，用於基於k個所述單歸網絡拓撲生成k個初始單歸子樹，所述k個初始單歸子樹為以所述集中控制器為根節點的k個最小生成樹； 確定子單元，用於確定k個所述初始單歸子樹中的pX (k-Ι)個可操作節點； 去除子單元，用於去除所述PX (k-Ι)個可操作節點，得到k個平衡單歸子樹。
9.根據權利要求8所述的裝置，其特徵在於， 所述確定子單元具體用於，確定本次執行去除操作的執行對象，並通知所述去除子單元去除所述執行對象，所述執行對象為所述PX (k-Ι)個可操作節點中的一個； 其中，所述確定子單元具體用於: 在k個當前單歸子樹中，確定本次執行去除操作的子樹；所述當前單歸子樹是指當前網絡拓撲中的子樹，所述當前網絡拓撲是指上一次執行去除操作之後得到的網絡拓撲；所述本次執行去除操作的子樹中包含存在於其他k-Ι個當前單歸子樹中的節點； 將所述本次執行去除操作的子樹中的、存在於其他k-Ι個當前單歸子樹中的一個節點作為所述執行對象。
10.根據權利要求9所述的裝置，其特徵在於，所述確定子單元具體用於， 確定k個所述當前單歸子樹中的第一類子樹，所述第一類子樹為:包含其他k-Ι個當前單歸子樹中的節點的當前單歸子樹； 當所述第一類子樹中節點數量最多的當前單歸子樹有一個時，將所述第一類子樹中節點數量最多的當前單歸子樹作為本次執行去除操作的子樹，或者， 當所述第一類子樹中節點數量最多的當前單歸子樹有至少兩個時，將所述第一類子樹中節點數量最多、且層數最多的當前單歸子樹作為本次執行去除操作的子樹。
11.根據權利要求9或10所述的裝置，其特徵在於， 所述確定子單元具體用於，當所述本次執行去除操作的子樹中的、存在於其他k-Ι個當前單歸子樹中的節點有至少兩個時，將所述至少兩個節點中所在層數最少的節點作為所述執行對象。
12.一種發送交叉命令的裝置，其特徵在於，應用於集中控制器中，網絡由P個節點構成，所述集中控制器通過所述P個節點中的I個接入節點與所述網絡連接，P為大於等於I的整數，所述裝置包括: 獲取單元，用於基於網絡拓撲和所述接入節點生成以所述集中控制器為根節點的最小生成樹； 發送單元，用於按照所述最小生成樹中的節點所在的層數從大到小的順序向所述最小生成樹中的 節點發送交叉命令。
【文檔編號】H04L12/753GK103733578SQ201380001322
【公開日】2014年4月16日 申請日期:2013年10月15日 優先權日:2013年10月15日
【發明者】孫俊 申請人:華為技術有限公司