用於在互連網絡之間傳輸預測的網絡行為的方法和系統的製作方法

2023-05-16 08:24:36

專利名稱：用於在互連網絡之間傳輸預測的網絡行為的方法和系統的製作方法
技術領域：
本發明一般地涉及網絡數據通信技術領域，並且在一個示例實施例中 涉及用來在互連網絡之間傳輸預測的網絡行為的方法和系統。
背景枝術
例如電信網絡這樣的網絡在網絡中將數據或流量從源遞送到目的地。 這些網絡可以由將網絡用於其自己的專用通信的公司來運營。它們也可以 由服務提供商來運營，所述服務提供商使別人可以將網絡用於其自有數據 的通信。
對於兩個或更多的網絡運營商而言，允許流量在其相應網絡之間傳播 以擴展對網絡使用者可用的通信範圍常常是有益的。網際網路是互連網絡的 最大這類集合。網絡運營商A可以向網絡運營商B付款以允許源自或去往 網絡A之用戶的流量通過網絡B傳輸。該協議被稱為網絡A從網絡B購 買轉接(transit)。還可以存在一種網絡A與B之間的互惠協議，其中網 絡A和B都允許源自或去往其相應網絡的用戶的流量免費通過兩方中的另 —個網絡傳輸。該協議是通常所說的對等(peering)。 一個網絡可以參加 與其他網絡的多個轉接和對等協議。


圖l是表示總的路由選擇交換系統的框圖。
圖2表示由網絡A的運營商所使用的網絡A的一個示例模型。 圖3表示由網絡B的運營商所使用的網絡B的一個示例模型。 圖4表示兩個數據結構，這兩個數據結構被圖1的系統用來存儲在創
建和使用故障轉移矩陣結構時使用的數據。
圖5表示故障結構，該故障結構被圖1的系統用來描述在構造和使片J
故障轉移矩陣時感興趣的故障場景。
圖6示出了圖2中的網絡A在特定故障狀態下的一個示例。
圖7示出了故障轉移矩陣結構的一個示例。
圖8示出了圖3中的網絡B在特定故障狀態下的一個示例。
圖9是一個示例需求路由選擇結構。
圖IO是描述圖1的系統所執行的一個示例方法的流程圖。
圖ll是對計算對等連結的一個示例方法進行描述的流程圖。
圖12是對計算故障轉移矩陣的一個示例方法進行描述的流程圖。
圖13是對模擬網絡的一個示例方法進行描述的流程圖。
圖14示出了一個示例圖形用戶界面。
圖15示出了以計算機系統的示例形式呈現的機器的圖形表示。 具體實灘方式
本發明中描述了某些用來幫助實現這些對等和轉接協議的機制。在整 個兩個網絡的具體實例A和B中都將提到交換流量。為了方便，A和B將 被稱為互相對等，儘管合同協議可以與上述對等的定義不同。雖然僅提到 了兩個網絡，但是多個網絡可以同時與其他網絡交換流量。所描述的機制 可以被擴展以幫助實現多個網絡之間的對等。
如果網絡B希望與另一個網絡A對等，則需要考慮以下兩個問題-
1. 每個網絡可能希望知道儘可能多的關於另一個網絡的信息，以 幫助對網絡之間所可能交換的流量的性質進行預測和規劃。
2. 然而，每個網絡可能希望儘可能地限制其他網絡所具有的對它為了防止其他 網絡從該知識得到任何商業優勢，如果這些網絡屬於競爭商業 實體的話。
網絡B所希望知道的關於網絡A的信息類型可以包括但不限於將流
經網絡B的源自或去往網絡A的流量的數量；網絡B中的入口點和出「:l
點，流量在此進入和離開網絡A;以及該流量在網絡B中經過的路徑。網
絡B還希望知道關於流量的這些屬性的將來可能的改變的信息，所述改變
是由下述事件等引起的網絡A中的組件的故障；網絡A中的組件的規劃
中斷(planned outage);以及網絡A中的路由選擇策略或拓撲的改變。在 本說明中，所有這些事件被描述為網絡A中的改變或故障，同時認識到除 實際網絡元件故障之外的原因可以是引起流量偏移的事件的原因。
該信息因以下原因等將會對網絡B有用對來自和去往網絡A的流量 和其網絡中的其他流量所將採用的路徑進行規劃，以使網絡中的過載或擁 塞的可能性最小化；幫助為網絡設計的未來改變進行規劃，這些改變包括 容量和拓撲改變；知道現在和未來其能夠向其自己的客戶端提供何種水平 的服務。
在本說明中，提議了一種示例機制，其使得兩個對等網絡A和B能夠 平衡上述的l和2要求。該機制中包括特殊的數據結構，其可以被在兩個 網絡之間交換。例如，被從網絡A提供到網絡B的數據結構對在兩個網絡 之間交換的流量的當前行為和可能的未來行為進行了足夠的揭示，以致有 助於網絡B的規劃目的。同時，該結構提供了與網絡A本身的內部設計有 關的最小信息，並且因此向網絡A提供了保密性。網絡B作為回報可以向 網絡A提供類似的數據結構。當然，網絡B也可以其它方式例如通過為信 息支付報酬來為提供該信息而補償網絡A。
這裡利用第一和第二網絡來說明本方法，在特定實施例中，第一網絡 網絡A將該信息提供給第二網絡網絡B以幫助網絡B預測下述流量的行 為，所述流量從網絡A流到網絡B並且所述流量進入網絡B的入口點是 由網絡A控制的。例如，這可以是當網絡A與網絡B處於對等配置時的 情況。本方法可以被容易地擴展為如下情況，其中，網絡A將信息提供給網絡B以預測下述流量的行為，所述流量從網絡B流到網絡A但足所述 流量進入網絡A的入口點是由網絡A控制的。該情況例如在網絡A是網 絡B的客戶並且因此為了規定流量從網絡B進入網絡A的入口點的能力 而向網絡B付款時發生。
網絡A和B的建模利用了網絡流量傳輸需求的概念。這些需求規定r 來自網絡中的特定源(或者在該源處進入網絡)的某一數量的流量去往該 網絡或另一個網絡中的特定目的地。然後利用由相應網絡實現的網絡路由 選擇協議通過一個或多個網絡來路由該需求的流量。網際網路中所使用的路 由選擇協議是IP (網際網路協議)。網絡中的不同故障狀態可以導致釆用不 同的路由。在IP中，網絡對其流量的路由選擇保持一定程度的控制。所 以，在上面的示例中，網絡A能夠控制流量從網絡A進入網絡B的入口
點o
2004年9月9日提交的名為"METHODS AND SYSTEMS TO PERFROM TRAFFIC ENGINEERING IN A METRIC-ROUTED NETWORK"的序列號為10/937,988的美國專利申請中描述了估計網絡^ 求的方法和將網絡模擬信息用於對網絡中的未來路由選擇路徑的進行規劃 和修改的方法，上述申請的全部內容通過引用而結合於此。
圖1是表示總的路由選擇交換系統的框圖。其由根據一個示例性實施 例的兩個子系統100和150組成。子系統100受網絡A的運營商的控制。 子系統150受網絡B的運營商的控制。
子系統IOO可以生成並使用三組表示網絡A和其到網絡B的連接的數 據結構。
1. 在示例實施例中，拓撲結構102描述了網絡A的拓撲。該拓撲 結構102中包括連接網絡A和網絡B的鏈路的表示。
2. 在示例實施例中，需求結構103描述了一組源自網絡A中並月. 目的地在網絡B中的端到端流量需求。這些需求表示網絡八試 圖從網絡A中的各種點發送到網絡B的網絡流量的數量。
3. 在示例實施例中，故障結構101描述了網絡A中的元件的一系 列改變場景。改變可以是故障場景或維護場景。網絡A希望將與這一系列場景下的從網絡A進入網絡B的流量的行為有關的 信息提供給網絡B。 圖4和圖5中提供了這些結構的細節。
在示例實施例中，這些結構是由形成子系統100的一部分的模塊(未 示出)生成的，所述模塊即網絡拓撲模塊、流量需求模塊和流量路由選擇 改變模塊。
對等鏈路使用情況計算器110使用數據結構101、 102和103來計算對 等鏈路使用情況結構120。在圖11中對計算器進行進一步描述，並且在圖 7中對得到的結構進行進一步描述。對等鏈路使用情況結構描述在故障結 構101中的每個故障場景下通過從網絡A到網絡B的每個對等鏈路路由多 少流量。
故障轉移矩陣構造器130使用對等鏈路使用情況結構120來計算被從 子系統IOO發送到子系統150的故障轉移矩陣結構140形式的改變數據。 故障轉移矩陣結構140描述流量在故障結構101中所列出的故障轉移場鼓 下如何從一個對等鏈路移動到另一個對等鏈路。圖7中提供了故障轉移矩 陣結構的進一步細節，並且圖12中提供了故障轉移矩陣構造器的進--步 的細節。
子系統150使用三組與101、 102和103形式相同的數據結構來描述網 絡B:
1. 在示例實施例中，故障結構151描述了網絡B中的元件的一系 列故障場景。這些可能包括網絡B希望包括在其對網絡B的行 為的模擬中以及包括在其對網絡B的未來修改和優化的規劃中 的場景。
2. 在示例實施例中，拓撲結構152描述了網絡B的拓撲。該結構 中包括將網絡B連接到網絡A的鏈路的表示。
3. 在示例實施例中，需求結構153包含可被通過網絡B路由並且 因此可以影響網絡B的流量使用和管理的流量需求(例如所冇 的流量需求)。具體而言，這包括源在網絡A中並且目的地在 網絡B中的需求、源和目的地都在網絡B中的需求，以及源在網絡B中並且目的地在網絡A中的需求。 在一個示例實施例中，這些結構是由形成子系統150的一部分的模塊 (未示出)生成的，這些模塊即網絡拓撲模塊、流量需求模塊和改變模 塊。
網絡模擬器160利用151、 152、 153中所包含的信息和已經由接收模 塊(未示出)從子系統100接收到的故障轉移矩陣結構140來執行對網絡 B的行為的模擬。具體而言，網絡模擬器160產生需求路由選擇結構 165，其描述了在151中所描述的每個故障場景下通過網絡B的153中的 每個需求的路由選擇。如果這些故障場景中的任何一個包含從網絡A到網 絡B的對等鏈路中的一個或多個對等鏈路的故障，則網絡模擬器160可以 參考故障轉移矩陣結構140，以確定在這些對等鏈路上通過網絡A進入網 絡B的需求的行為。圖13中提供了網絡模擬器160的細節。
可以利用網絡B的控制器在GUI 170中顯示需求路由選擇結構165， 以使故障場景下的網絡行為可視化。圖14中提供了一些GUI元素的細 節。需求路由選擇結構165還可以被用作網絡規劃工具180的輸入，網絡 規劃工具180可以建議網絡設計或路由選擇策略的修改或優化以減輕所述 故障(如果它們發生的話)的影響。
圖2表示由網絡A的運營商所使用的網絡A的一個示例模型，其將被 用來說明圖1中的系統所使用的數據結構。該示例中的網絡A (200)山 一組六個節點或者說路由器Nl (201)至N6組成。這些節點是通過雙向 鏈路連接的。例如，202將N1連接到N4。因為網絡A的運營商不知道網 絡B的拓撲，所以圖中用單個節點215來表示網絡B。網絡A與網絡B之 間的對等鏈路(Pl、 P2和P3， 220-222)將網絡A中的節點連接到網絡 B。
圖2中表示三個被路由的需求。DA1、 DA2和DA3 (230-232)是對 分別從Nl、 N2和N3到NB的流量的需求。通過網絡A的鏈路和通過對 等鏈路的這些需求的示例路由選擇被示出。這些是正常操作下的路由選 擇，正常操作例如是當網絡A的元素未曾發生故障時。需求DA1、 DA2 和DA3分別傳送50、 100和100 Mb/s (百萬比特每秒)的流量。注意到DA3具有分割的路由選擇，這是IGP最短路徑優先路由選擇協議所允許 的。該需求中的一半流量採用到目的地的一個路由，並且一半採用另一個 路由。
圖3表示由網絡B的運營商所使用的網絡B的一個示例模型，其將被 用來說明圖l中的系統所使用的數據結構。該示例中的網絡B (300)由一 組六個節點或者說路由器N7 (301)至N12組成。這些節點是通過雙向鏈 路連接的。因為網絡B的運營商不知道網絡A的拓撲，所以圖中用單個節 點310來表示網絡A。網絡A與網絡B之間的對等鏈路(Pl、 P2和P3， 320-322)是圖2中的鏈路220-222。
圖3中表示三個被路由的需求。DB1、 DB2和DB3 (330-332)是對 從NA分別到NIO、 N11和N12的流量的需求。通過對等鏈路和網絡B的 鏈路的這些需求的示例路由選擇被示出。這些是與圖2中的需求路由選擇 類似的正常操作下的路由選擇。
圖4表示被圖1中的子系統IOO和子系統150用來存儲故障轉移矩陣 結構140的創建和使用中所使用的數據的數據結構中的兩個。在圖4中， 為了說明而用表示圖2中的示例網絡A的數據來填充這些結構。
作為一個示例實施例的拓撲結構400包含這樣的表，該表中的每行表 示拓撲中的一個鏈路。表中的列可以如下所述
1. 鏈路ID:標識鏈路的字符串。
2. 來自鏈路所連接到的將數據發送到鏈路上的節點。
3. 來自節點/AS:如果來自節點是物理節點則是節點，或者如果來 自節點是另一個網絡的概括表示則是AS (Autonomous System,自治系統)
4. 去往鏈路所連接到的從鏈路接收數據的節點。
5. 去往節點/AS:類似於來自節點/AS，但是描述去往節點。 需求結構410包含這樣表，該表中的每行表示拓撲中的需求。表中的
列可以如下所述
1. 需求ID:表示需求的字符串。
2. 源發起通過網絡的流量傳輸的源節點或源AS。3. 目的地最終接收通過網絡的流量傳輸的目的地節點或目的地AS。
4. 流量(Mb/s):按照Mb/s (百萬比特每秒)或者其他流量數設
度量的將被發送的流量的數量。
圖5表示根據示例實施例的故障結構500，圖1中的子系統100和150 都使用故障結構500來描述結構中感興趣的故障場景和故障轉移矩陣結構 140的使用。
故障結構500作為示例說明包含圖2中的示例網絡A的三個故障場貴 的描述。故障結構500可以是這樣表，其中表的每行表示一個特定的故障 場景。表的每列表示網絡中的一個鏈路。表中的每個條目不是空白就是被 標以X。特定行和列中的X規定該行所表示的故障場景包括(至少)該列 所表示的鏈路。500中的三個故障場景表示圖2中的三個對等鏈路220-222 的故障。
注意一個故障場景可以包含多個鏈路故障。例如，故障結構510包含 對圖3中的網絡B中的故障的描述。所表示出的故障是網絡中的節點的故 障，其被描述為連接到該節點的所有鏈路的故障。因此，在表中，鏈路 P2、 N8-N7和N8-N10 (除別的以外)被標以X。
圖6表示特定故障狀態下的圖2中的示例網絡A。該圖將充當圖7中
的對等鏈路使用情況結構和故障轉移矩陣結構的構造時的一個示例。
網絡A (600)是與圖2中相同的網絡。在該圖中，由交叉610表示的 對等鏈路之一 P2已經發生故障。這是圖5中的結構500中的表的第二行 中所表示的故障場彔。三個需求DA1、 DA2和DA3 (601-603)已經被重 新路由以避開發生故障的對等鏈路。在該故障場景下，它們僅使用對等鏈 路Pl和P3來達到它們公共的目的地NB即網絡B。
圖7表示通過圖1中的子系統100計算出的對等鏈路使用情況結構 700和故障轉移矩陣結構710。在該附圖中，這些結構是利用圖2中的示 例網絡A和圖5中的故障結構500中的示例故障場景來填充的。
對等鏈路使用情況結構700由這樣表組成，表中的每行表示從故障結 構500複製的故障場景。另外，第一行表示"無故障"場景，其中網絡中對等鏈路。在該實例中有三個對等鏈路P1、 P2 和P3。
特定行和列的條目是該故障場景下的該對等鏈路的使用情況(以Mb/s 為單位)。如果該對等鏈路在該故障場景下發生故障，則不輸入數目。例 如，考慮圖6中和表700的第三行中所表示的故障場景P2。在該故障場設 下，網絡A通過對等鏈路P1來重新路由需求DA2，使得P1的總體使用惜 況是50Mb/s來自DA1，並且100Mb/s來自DA2。因此使用總數150Mb/s 被輸入表700的第三行第二列。
一旦對等鏈路使用情況結構700已經被計算出，圖1中的子系統100 的故障轉移矩陣構造器就計算故障轉移矩陣結構140。故障轉移矩陣結構 140包含與對等鏈路使用情況結構700相對應的數據。
故障轉移矩陣結構140可以被實現為這樣的表，其中每行表示故障場 景，並且每列表示對等電路。 一個示例實施例中的特定行和列的條目可以 是
1. 空白，如果對應的故障場景使對應的對等鏈路發生故障的話，
或
2. 等於來自該行中的所有故障鏈路的被傳送到對等鏈路的流量的 百分比。例如，從結構700可見在故障場景P2下，通常通過P2 傳送的150Mb/s的流量被重新路由。在故障場景P2下，Pl的使 用增加100Mb/s，其是150Mb/s的67%。因此，710中與故障場 景P2相對應的行和與對等電路Pl相對應的列中的條冃是 67%。
圖8表示特定故障狀態下的圖3中的示例網絡B。該附圖將充當圖9 的需求路由選擇結構的構造時的一個示例。
網絡B (800)是與圖2中相同的網絡。在該附圖中，由通過節點的交 叉表示的網絡中的節點之一N8 (820)已經發生故障。這是圖5中的結構 510中的表中所表示的故障場景。源自網絡A的三個需求DB1、 DB2和 DB3 (801-803)已經被重新路由以避開發生故障的節點。
圖9表示圖1中的網絡模擬器160利用故障轉移矩陣結構140、網絡B中的故障結構、拓撲結構和需求結構151-153來計算的需求路由選擇結 構900。
需求路由選擇結構900對於故障場景結構151中的每個故障場景都可 以包含一個表，並且對於其中沒有元件發生故障的網絡的正常操作包含--個表。在圖中，表示了這些表中的兩個正常操作表910，以及與節點N8 的故障相對應的表920，節點N8的故障是圖5的故障結構510中所表示的 單個故障場景。
900中的每個表對於網絡中的每個需求都有一行，並且對於網絡中的 每個鏈路都有一列。表中與特定需求和鏈路相對應的條目是來自通過該鏈 路傳送的該需求的流量的數量。
圖10是描述由圖1中的系統執行的根據一個示例實施例的過程的流 程圖。流程在1000處開始。在1010中，網絡A的拓撲、需求和故障結構 被對等鏈路使用情況計算器110用來構造對等鏈路使用情況結構120。該 過程在圖ll中被進一步描述。
在1020中，對等鏈路使用情況結構120被故障轉移矩陣構造器130用 來計算故障轉移矩陣結構l鄰。該過程在圖12中被進一步描述。
在1030中，網絡A將故障轉移矩陣結構140發送到網絡B。
在1040中，網絡B接收到來自網絡A的故障轉移矩陣結構140。
在1050中，網絡模擬器160利用網絡B的拓撲、需求和故障結構連 同故障轉移矩陣結構來模擬網絡B中的需求的路由選擇，從而構造需求路 由選擇結構165。該過程在圖13中被進一步描述。
在1060中，需求路由選擇結構165被用來通過GUI査看網絡模擬， 並且被用來根據這些路由選擇所描述的網絡行為來建議和實現對網絡布 局、路由選擇和未來規劃的優化。圖14具體參照對來自對等網絡的需求 的模擬來說明可被用來顯示網絡模擬的一些GUI元素。
過程在1070處結束。
圖11是描述根據示例實施例的利用圖1中的對等鏈路使用情況計算 器110來計算對等鏈路使用情況結構120的方法的流程圖。過程在1100處 開始。在1110中，對等鏈路使用情況結構120被定義為矩陣U(ij)，其中I 索引故障場景並且j索引對等鏈路。i-0是為正常的"無故障"場景保斷 的。最初，對於每個j， U(0j)被設為由在"無故障"場景下對需求進行路 由選擇而得到的鏈路使用情況。需求是利用網絡A所使用的任何路由選擇 協議(例如IP路由選擇協議)來路由的。對於iX)，每個U(ij)被設為零。 索引i被設為1。
在1120中，對於給定的故障場景i，對等鏈路U(iJ)被設為產生故障 場景i下的需求路由選擇的使用情況，從而再次模擬網絡A所使用的路由 選擇協議的行為，具體而言，當遇到故障場景所描述的故障時該協議的行 為。如果任何對等鏈路j在故障場景i下發生故障，則將U(iJ)設為"-"， 從而指示該鏈路未被使用。
在1130中，進行檢查，以了解i是否是網絡A的故障結構中的最後- 個故障場景。如果是，則過程在1140處結束，同時獲得所需的對等鏈路 使用情況表U(ij)。如果不是，則i在1150中被遞增並且控制返回1120。
圖12是描述根據一個示例實施例的利用圖1中的故障轉移矩陣構造 器130來計算故障轉移矩陣結構140的方法的流程圖。
過程在1200處開始。對等鏈路使用情況結構U(ij)被給出，其中i=0 表示"無故障"情況。
在1210中，對於所有的故障場景i和對等鏈路j， F(ij)被設為0，並 且i被初始化為1。 F(ij)將被用故障轉移矩陣結構140填充。
在1220中，.T(i)被設為對於使用情況U(OJ)， U(ij)等於"-"的所冇 使用情況U(OJ)的總量。就是說，T(i)是在場景i下必須從發生故障的對等 鏈路移動到其他鏈路的流量的總數量。對等鏈路計數器j被初始化為
1 ，,
在1230中，根據U(ij)是否等於"-"來進行分支。如果是，則在1260 中F(ij)也被設為"-"。如果不是，則在1240中F(ij)被設為鏈路i中的流 量在該故障場景下較之在無故障場景下的增加作為總的轉移流量T(i)的百 分比。就是說，F(iJ)被設為(U(ij)-U(Oj))/T(i)，其被表示作為百分比。
在1250中，根據是否已經到達最後一個對等鏈路j來進行分支。如果是，則控制移動到1270。如果不是，則j在1280中被遞增並且控制移動 回1230。
在1270中，根據是否已經到達最後一個故障場景i來進行分支。如果 是，則控制移動到1295。如果不是，則i在1290中被遞增並且控制移動 回1220。
圖13是描述根據示例實施例的用於在圖1的160中模擬網絡B的方 法的流程圖。
過程在1300處開始。由網絡A提供給網絡B的故障轉移矩陣F (i'J')被給出。這裡i'索引網絡A的故障場景，並且j'索引對等鏈路。
需求路由選擇結構165由三維數組D(i山k)表示。這裡I索引網絡B屮 的故障場景，i-0是"無故障"場景；j索引網絡B中的鏈路，並且k索引 網絡B中的需求。
在1310中，對於每個鏈路j和需求k， D(Oj，k)被設為網絡B中的JK常 操作下的鏈路j中的需求k的使用情況。對於i>0，每個D(ij，k)被設為0。 需求索引k被初始化為l。
在1320中，故障場景索引i被初始化為1。
在1330中，根據故障場景i中需求k是否將被重新路由以繞開已經發 生故障的對等鏈路來進行分支。如果不是，則在1350中對於該i， D(ij,k) 被設為在該故障場景下被路由的需求k的使用情況，從而模擬網絡B中的 路由選擇需求中所使用的常見協議。如果是，則在考慮使對等鏈路故障與 網絡B中的故障場景i相匹配的情況下，在1340中查閱故障轉移矩陣 F(i'j')以查找表示網絡A中的故障場景i'的行i'。
在1360中，在網絡B中的所有鏈路j上，對於在場景i下未發生故障 的每個對等鏈路j，，假定需求通過該鏈路j'進入網絡B，並且利用網絡B 中用於路由選擇的常見協議，來為需求k計算路由選擇r(j'J')。對於每個 j， D(i丄k)被增加r(j，J) x F(i，j，)。就是說，D(ij,k)被以下述比例同時路由通 過所有無故障的鏈路，所述比例是故障轉移矩陣結構140規定的流量從故 障對等鏈路故障轉移到其他對等鏈路的比例。
在1370中，根據是否已經到達最後一個故障場景i來進行分支。如果是，則控制移動到1380。如果不是，則i在1375中被遞增並且控制移動 回1330。
在1380中，根據是否已經到達最後一個需求k來進行分支。如果 是，則控制移動到13卯。如果不是，則k在1385中被遞增並且控制移動 回1320。
流程在13卯處結束，其中需求路由選擇結構D(ij，k)是完成的。
圖14是根據一個示例實施例的可被用來查看由圖1的160執行的網絡 模擬的結果的用戶圖形界面(GUI)的示意性表示。圖3的網絡B被表示 作為一個示例。因為網絡B的拓撲對該網絡的運營商是完全已知的，故其 可以被充分地表示，如框1410中一樣，諸如1460這樣的所有節點或路由 器都被顯示，並且諸如1420這樣的所有電路都被顯示。這些雙向電路被 用並排的兩個方向的鏈路示出，箭頭示出組成鏈路的方向。每個鏈路中的 空間可以用不同顏色來填充，以例如表示該鏈路在特定故障場景下的總體 使用情況，或者表示在特定故障,景下是否有需求通過該鏈路。GUI可以 被用來通過將故障元件示出為劃掉來査看不同的故障場景。例如，圖6中 所表示的故障場景在這裡是用交叉1440通過節點N8來表示的，節點N8 在該故障場景下是故障的。
網絡A的拓撲對網絡B是未知的。只有將網絡A連接到網絡B的對 等電路是已知的。所以網絡A可以如1400中一樣被表示為壓縮成單個節 點。對等電路如1450中一樣被表示為連接到節點1400的電路。
通常，網絡可以通過對等連接連接到許多對等網絡。在這種情況下， 如例如在網絡B內部的電路中實現的那樣將所有的對等電路表示為雙向鏈 路(例如1420)會導致屏幕或網絡的印出表示上的大量混亂。所以對等電 路可以如1450中一樣被表示為短電路，並且其所連接到的網絡B中的節 點是通過如1430中一樣從線路1450的尖端繪製一條單線到節點來示出 的。該線可被完全除去以進一步除去混亂。
圖15示出了以計算機系統1500的示例形式呈現的機器的圖形表示， 在該機器中可以執行用於使該機器執行這裡所討論的方法中的任何一個或 多個方法的一組指令。在替代實施例中，機器如獨立設備一樣工作或者可以連接(例如聯網)到其他機器。在聯網的部署中，機器可以作為伺服器-客戶端網絡環境下的伺服器或客戶機來工作，或者如端到端(或者分布
式)網絡環境下的對等機器一樣工作。機器可以是個人計算機(PC)、平 板PC、機頂盒(STB)、個人數字助理(PDA)、蜂窩式電話、網絡設 備、網絡路由器、交換機或網橋，或者任何能夠執行一組規定該機器所要 採用的動作的指令(順序的或相反)的機器。另外，雖然只有單個機器被 圖示，但是術語"機器"還應當被理解為包括獨立地或者共同地執行一組 (或多組)指令以執行這裡所討論的方法中的任何一個或多個方法的機器 的任意集合。
示例計算機系統1500包括經由總線1508互相通信的處理器1502 (例 如中央處理器(CPU)、圖形處理器(GPU)或者兩者兼有)、主存儲器 1504以及靜態存儲器1506。計算機系統1500還可以包括視頻顯示單元 1510 (例如液晶顯示器(LCD)或陰極射線管(CRT))。計算機系統 1500還包括字母數字輸入設備1512 (例如鍵盤)、用戶界面(UI)導航 設備1514 (例如滑鼠)、磁碟驅動單元1516、信號生成設備1518 (例如 揚聲器)和網絡接口設備1520。
磁碟驅動單元1516包括其上存儲有一組或多組指令和數據結構(例 如軟體1524)的機器可讀介質1522，這些指令和數據結構實現了這裡所 描述的方法或功能中的任何一個或多個或者被這裡所描述的方法或功能中 的任何一個或多個利用。軟體1524在其被計算機系統1500執行期間還可 以完全或者至少部分地駐留在主存1504中和/或處理器1502中，主存 1504和處理器1502也組成機器可讀介質。
還可以利用許多眾所周知的傳輸協議(例如HTTP)中的任何一個經 由網絡接口設備1520在網絡1526上發送或接收軟體1524。
雖然機器可讀介質1522在一個示例實施例中被示出為單個介質，但 是術語"機器可讀介質"應當被理解為存儲一組或多組指令的單個介質或 多個介質(例如，集中式或分布式資料庫，和/或與之相關聯的高速緩衝存 儲器或伺服器)。術語"機器可讀介質"還應當被理解為包括任何能夠對 供機器執行的一組指令進行存儲、編碼和傳送以及使機器執行本發明的方法中的任何一個或多個或者能夠對與這樣一組指令相關聯或被這樣-組指 令利用的數據結構進行存儲、編碼或傳送的介質。術語"機器可讀介質" 應當相應地被理解為包括但不限於固態存儲器、光學和磁性介質和載波信 號。
權利要求
1.一種傳輸預測的網絡行為的方法，所述方法包括生成網絡拓撲結構數據，該網絡拓撲結構數據描述第一網絡的拓撲的至少一部分；生成需求結構數據，該需求結構數據描述與所述第一網絡中的源和第二網絡中的目的地有關的至少一些流量需求，其中所述第一網絡與所述第二網絡之間有多個網絡鏈路；生成流量路由選擇改變數據，該流量路由選擇改變數據描述將需要流量路由的改變的至少一個改變場景；利用所述網絡拓撲結構數據、所述需求結構數據和所述流量路由選擇改變數據來針對所述至少一個改變場景計算通過所述第一網絡與所述第二網絡之間的所述多個網絡鏈路中的每一個網絡鏈路的流量的路由選擇；以及將改變數據發送到所述第二網絡，所述改變數據描述在所述至少一個改變場景中通過所述多個網絡鏈路的網絡流量移動。
2. 如權利要求1所述的方法，其中，所述改變場景是其中所述網絡鏈 路中的至少一個將被維護或發生故障的維護場景和故障場景中的至少--個。
3. 如權利要求1所述的方法，其中，針對多個改變場景計算通過所述 第一網絡與所述第二網絡之間的所述多個網絡鏈路的流量的路由選擇。
4. 如權利要求1所述的方法，其中，所述改變數據描述足夠的信息以 使得所述第二網絡的運營商能夠針對可能的改變場景作規劃同時不向所述 第二網絡運營商洩露關於所述第一網絡的其他信息。
5. 如權利要求1所述的方法，其中，所述需求結構數據為所述流量需 求中的每一個描述所述需求的源、所述需求的目的地和所述需求的大小。
6. 如權利要求1所述的方法，其中，所述網絡拓撲結構數據包括描述 所述第一網絡與所述第二網絡之間的所述多個網絡鏈路的數據。
7. 如權利要求1所述的方法，其中，針對所述改變場景中的每一個計算流量的路由選擇包括計算如果所述網絡鏈路中的一個或多個被改變的話 多少流量將被路由通過其他網絡鏈路中的每一個。
8. 如權利要求7所述的方法，其中，所述改變數據是根據針對所述至 少一個改變場景對所述第一網絡與所述第二網絡之間的所述多個網絡鏈路 中的每一個網絡鏈路的流量的路由選擇的計算確定的。
9. 如權利要求8所述的方法，其中，對於所述改變場景中的每一個， 所述改變數據包括如果所述網絡鏈路中的一個或多個被改變的話將被路由 通過所述其他網絡鏈路中的每一個網絡鏈路的流量的百分比增加。
10. 如權利要求9所述的方法，其中，所述百分比增加是如果改變場 景發生的話將被重新路由的流量的百分比。
11. 一種用於傳輸預測的網絡行為的系統，所述系統包括 網絡拓撲模塊，該網絡拓撲模塊用來生成網絡拓撲結構數據並且將所述網絡拓撲結構數據存儲在存儲設備中，所述網絡拓撲結構數據描述第一 網絡的拓撲的至少一部分；流量需求模塊，該流量需求模塊用來生成需求結構數據並且將所述需 求結構數據存儲在所述存儲設備中，所述需求結構數據描述與所述第一網 絡中的源和第二網絡中的目的地有關的至少一些流量需求，其中所述第一 網絡與所述第二網絡之間有多個網絡鏈路；流量路由選擇改變模塊，該流量路由選擇改變模塊用來生成流量路由 選擇改變數據並且將所述流量路由選擇改變數據存儲在存儲設備中，所述 流量路由選擇改變數據描述至少一個改變場景；計算器，該計算器利用所述網絡拓撲結構數據、所述需求結構數據和 所述流量路由選擇改變數據來針對所述至少一個改變場景計算通過所述第 一網絡與所述第二網絡之間的多個鏈路中的每一個鏈路的流量的路由選 擇；以及發送模塊，該發送模塊將改變數據發送到所述第二網絡，所述改變數 據描述在所述至少一個改變場景中通過所述多個網絡鏈路的網絡流量移 動。
12. 如權利要求11所述的系統，其中，網絡改變場景是其中所述網絡鏈路中的至少一個將被維護或發生故障的維護場景和故障場景屮的至少一 個。
13. 如權利要求ll所述的系統，其中，第二網絡改變場景是其屮所述 第二網絡中的至少一個節點將被維護或發生故障的維護場景和故障場雖屮 的至少一個。
14. 如權利要求11所述的系統，其中，所述計算器針對多個改變場^: 計算通過所述第一網絡與所述第二網絡之間的所述多個網絡鏈路的流貴的 路由選擇。
15. 如權利要求11所述的系統，其中，所述發送模塊發送下述改變數 據，所述改變數據描述足夠的信息以使得所述第二網絡的運營商能夠針對 可能的改變場景作規劃同時不向所述第二網絡運營商洩露關於所述第-網 絡的其他信息。
16. 如權利要求11所述的系統，其中，所述流量需求模塊為所述流梨: 需求中的每一個生成需求結構數據，所述需求結構數據描述所述需求的 源、所述需求的目的地和所述需求的大小。
17. 如權利要求11所述的系統，其中，所述網絡拓撲模塊生成網絡拓 撲結構數據，所述網絡拓撲結構數據包括描述所述第一網絡與所述第—二網 絡之間的所述多個網絡鏈路的數據。
18. 如權利要求11所述的系統，其中，所述計算器針對所述改變場景 中的每一個對流量的路由選擇進行的計算包括計算如果所述網絡鏈路中的 一個或多個被改變的話多少流量將被路由通過其他網絡鏈路中的每一個。
19. 如權利要求18所述的系統，其中，所述計算器根據針對所述至少 一個改變場景對通過所述第一網絡與所述第二網絡之間的所述多個網絡鏈 路中的每一個網絡鏈路的流量的路由選擇的計算確定所述改變數據。
20. 如權利要求19所述的系統，其中，所述計算器確定所述改變數據 對於所述改變場景中的每一個包括如果所述網絡鏈路中的一個或多個被改 變的話將被路由通過所述其他網絡鏈路中的每一個網絡鏈路的流量的EJ'分 比增加。
21. 如權利要求20所述的系統，其中，所述百分比增加是如果改變場景發生的話將被重新路由的流量的百分比。
22. —種傳輸預測的網絡行為的方法，所述方法包括 在第二網絡處接收來自第一網絡的第一網絡改變數據，所述第一網絡改變數據描述在至少一個網絡鏈路改變場景中通過所述第一網絡與所述第 二網絡之間的多個鏈路的網絡流量移動，其中，在所述網絡鏈路改變場景中，所述多個鏈路中的至少一個己經改變；生成網絡拓撲結構數據，該網絡拓撲結構數據描述所述第二網絡的沐' 撲的至少一部分；生成需求結構數據，該需求結構數據描述與所述第一網絡中的源和所 述第二網絡中的目的地有關的至少一些流量需求；生成第二網絡改變數據，該第二網絡改變數據描述所述第二網絡中的 至少一個改變場景；利用所述網絡拓撲結構數據、所述需求結構數據、所述第一網絡改變 數據和所述第二網絡改變數據來針對所述第二網絡中的至少一個改變場雖 計算通過所述第二網絡的流量的路由選擇。
23. 如權利要求22所述的方法，其中，所述網絡鏈路改變場景是其中 所述網絡鏈路中的至少一個將被維護或發生故障的維護場景和故障場景屮 的至少一個。
24. 如權利要求22所述的方法，其中，所述第二網絡改變場景是其屮 所述第二網絡中的至少一個節點將被維護或發生故障的維護場景和故障場 景中的至少一個。
25. 如權利要求21所述的方法，其中，所述網絡鏈路改變數據描述足 夠的信息以使得所述第二網絡的運營商能夠針對可能的網絡鏈路改變場景 作規劃同時不向所述第二網絡運營商洩露關於所述第一網絡的其他信息。
26. 如權利要求21所述的方法，其中，所述需求結構數據為所述流量 需求中的每一個描述所述需求的源、所述需求的目的地和所述需求的大 小。
27. 如權利要求21所述的方法，其中，所述網絡拓撲結構數據包括描 述所述第二網絡中的多個節點的數據。
28. 如權利要求21所述的方法，其中，針對所述第二網絡改變場鼓中 的每一個對流量的路由選擇進行的計算包括計算如果所述第二網絡節點屮 的一個或多個被改變的話多少流量將被路由通過其他第二網絡節點中的每 —個。
29. 如權利要求28所述的方法，其中，所述第二網絡改變數據是根據 針對所述至少一個第二網絡改變場景對通過所述多個第二網絡節點中的每 一個節點的流量的路由選擇進行的計算來確定的。
30. 如權利要求29所述的方法，其中，對於所述第二網絡改變場景屮 的每一個，所述第二網絡改變數據包括如果所述第二網絡節點中的一個或 多個被改變的話將被路由通過其他第二網絡節點中的每一個節點的流貴的 百分比增加。
31. 如權利要求30所述的方法，其中，所述百分比增加是如果第二網 絡改變場景發生的話將被重新路由的流量的百分比。
32. 如權利要求22所述的方法，還包括利用所述拓撲結構數據、所述 需求結構數據、所述第一網絡改變數據和所述第二網絡改變數據來向所述 第二網絡的運營商顯示圖形用戶界面，其中，所述圖形用戶界面示出了所 述第二網絡中的所有節點以及所述第二網絡與所述第一網絡之間的多個鏈路，但是其中所述圖形用戶界面不示出對所述第二網絡的運營商未知的第 一網絡的細節。
33. 如權利要求32所述的方法，其中，所述第二網絡中的節點之間的 鏈路被顯示為雙向鏈路。
34. 如權利要求32所述的方法，其中，所述第一網絡被顯示為壓縮節 點，並且所述第一網絡與所述第二網絡之間的鏈路被顯示為單線。
35. —種用於傳輸預測的網絡行為的系統，所述系統包括 接收模塊，該接收模塊用來在第二網絡處接收來自第一網絡的第一網絡改變數據，所述第一網絡改變數據描述在至少一個網絡鏈路改變場鼓中 通過所述第一網絡與所述第二網絡之間的多個鏈路的網絡流量移動，其中 在所述網絡鏈路改變場景中，所述多個鏈路中的至少一個己經改變；網絡拓撲模塊，該網絡拓撲模塊用來生成網絡拓撲結構數據並且將所述網絡拓撲結構數據存儲在存儲設備中，所述網絡拓撲結構數據描述所述第二網絡的拓撲的至少一部分；流量需求模塊，該流量需求模塊用來生成需求結構數據並且將所述;f求結構數據存儲在所述存儲設備中，所述需求結構數據描述與所述第一網絡中的源和所述第二網絡中的目的地有關的至少一些流量需求；改變模塊，該改變模塊用來生成第二網絡改變數據並且將所述第二網絡改變數據存儲在所述存儲設備中，所述第二網絡改變數據描述所述第二網絡中的至少一個第二網絡改變場景；以及網絡模擬器，該網絡模擬器利用所述網絡拓撲結構數據、所述需求結構數據、所述第一網絡改變數據和所述第二網絡改變數據來針對所述笫二網絡中的至少一個第二網絡改變場景計算通過所述第二網絡的流量的路山選擇。
36. 如權利要求35所述的系統，其中，所述網絡鏈路改變場景是其中 所述網絡鏈路中的至少一個將被維護或發生故障的維護場景和故障場景屮 的至少一個。
37. 如權利要求35所述的系統，其中，所述第二網絡改變場景是其屮 所述第二網絡中的至少一個節點將被維護或發生故障的維護場景和故障場 景中的至少一個。
38. 如權利要求35所述的系統，其中，所述網絡模擬器針對所述至少 一個第二網絡改變場景模擬通過所述第二網絡的多個節點中的每一個節點的流量的路由選擇。
39. 如權利要求35所述的系統，其中，所述流量需求模塊為所述流雖' 需求中的每一個生成需求結構數據，所述需求結構數據描述所述需求的 源、所述需求的目的地和所述需求的大小。
40. 如權利要求35所述的系統，其中，所述網絡拓撲模塊生成網絡拓 撲結構數據，所述網絡拓撲結構數據包括描述所述第二網絡中的多個節點 的數據。
41. 如權利要求40所述的系統，其中，所述網絡模擬器針對所述笫二 網絡改變場景中的每一個對流量進行的路由選擇包括計算如果所述至少一個第二網絡改變場景發生的話多少流量將被路由通過所述第二網絡節點中 的每一個。
42. 如權利要求41所述的系統，其中，所述網絡模擬器根據針對所述 至少一個改變場景對通過所述第二網絡中的多個節點中的每一個節點的流 量的路由選擇的計算確定所述第二網絡改變數據。
43. 如權利要求41所述的系統，其中，所述網絡模擬器確定所述第二 網絡改變數據包括對於所述第二網絡改變場景中的每一個，如果所述第 二網絡節點中的一個或多個被改變的話將被路由通過其他第二網絡節點中 的每一個節點的流量的百分比增加。
44. 如權利要求43所述的系統，其中，所述百分比增加是如果改變場 景發生的話將被重新路由的流量的百分比。
45. 如權利要求35所述的系統，還包括圖形用戶界面模塊，所述閣形 用戶界面模塊利用所述拓撲結構數據、所述需求結構數據、所述第一網絡 改變數據和所述第二網絡改變數據來向所述第二網絡的運營商顯示圖形用 戶界面，其中，所述圖形用戶界面示出了所述第二網絡中的所有節點以及所述第二網絡與所述第一網絡之間的多個鏈路，但是其中所述圖形用戶界 面不示出對所述第二網絡的運營商未知的第一網絡的細節。
46. 如權利要求45所述的系統，其中，所述圖形用戶界面將所述第二 網絡中的節點之間的鏈路顯示為雙向鏈路。
47. 如權利要求46所述的方法，其中，所述圖形用戶界面將所述第一 網絡顯示為壓縮節點並且將所述第一網絡與所述第二網絡之間的鏈路顯示 為單線。
48. —種用於網絡運營商的圖形用戶界面，所述圖形用戶界面包括 與節點之間的雙向鏈路一起顯示的第一網絡的多個節點；以及 被顯示為單個壓縮節點的至少一個第二網絡，並且單線將該壓縮節點連接到所述第一網絡。
49. 一種方法，包括將改變數據從第一網絡傳輸到第二網絡，所述改變數據描述對於至少 一個改變場景通過所述第一網絡與所述第二網絡之間的多個網絡鏈路的網絡流量移動，其中所述至少一個改變場景是其中所述網絡鏈路中的至少一 個將被維護或發生故障的維護場景和故障場景中的至少一個，所述改變數 據描述足夠的信息以使得所述第二網絡的運營商能夠針對可能的改變場貴作規劃同時不向所述第二網絡運營商洩露關於所述第一網絡的其他信息； 以及接收來自所述第二網絡的對所述改變數據的補償。
50. 如權利要求49所述的方法，其中，所述補償是財政補償。
51. 如權利要求49所述的方法，其中，所述補償是接收來自所述第二 網絡的改變數據。
全文摘要
一種傳輸預測的網絡行為的方法，該方法包括生成網絡拓撲結構數據，該網絡拓撲結構數據描述第一網絡(圖1，網絡A)的拓撲中的至少一部分。需求結構(圖1，項103)數據被生成，該需求結構數據描述與第一網絡(圖1，網絡A)中的源和第二網絡(圖1，網絡B)中的目的地有關的至少一些流量需求，其中第一網絡(網絡A)與第二網絡(網絡B)之間有多個網絡鏈路(圖2，項220、221和222)。流量路由選擇改變數據被生成，該流量路由選擇改變數據描述將需要流量路由選擇的改變的至少一個改變場景。該數據然後被用來計算改變數據，該改變數據描述通過第一網絡(網絡A)與第二網絡(網絡B)之間的多個網絡鏈路中的每一個網絡鏈路的流量的路由選擇。改變數據被發送到第二網絡(網絡B)。
文檔編號G06F15/16GK101542456SQ200680003495
公開日2009年9月23日 申請日期2006年1月27日 優先權日2005年1月28日
發明者安德烈·亨茨, 艾倫·古斯, 阿爾曼·麥格柏萊, 阿拉士·阿弗萊克特 申請人:卡裡德恩科技有限公司