用於有線或無線網絡的邊界掃描測試的系統和方法
2023-05-31 11:15:56
專利名稱：用於有線或無線網絡的邊界掃描測試的系統和方法
背景技術：
1.發明領域本發明一般涉及通信網絡中的數字數據傳輸，特別涉及在有線或無線網絡中執行邊界掃描或漫遊鏈路(roving link)測試的機制。
2.相關技術當前的網絡易於出錯並且難以配置，診斷和維護。當網絡出現故障時，找出故障點是困難且費力的。舉例來說，在使用路由表的系統中，當故障發生時，路由表中的信息將不再有效。網際網路控制消息協議(「ICMP」)或是相似類型的協議可用來報告錯誤，查找故障出處和監測網絡性能。然而，在自組有線或無線分組網絡中存在著明顯的缺陷，即無法測試到所有可能的可選路由，可選路由就是指當現存路由的信號發送不能令人滿意或是完全失敗時，當前沒有使用到而又可能是所需的路由。
支持邊界掃描的設備允許IEEE1149.1標準聯合測試行動組(「JTAG」)作為背板總線(backplanebus)使用，這就使實現背板互連測試和多分支結構成為可能，使得在系統集成和現場服務情況中能夠做到從背板到主板到晶片的診斷。舉個例子，IC晶片的所有存儲組件可在一個長移位寄存器中以最小化的開銷連接，接著使用片上的通用串行埠將任意測試向量移入和移出晶片。這些測試向量允許整個晶片得到演練，通過與工作晶片比較的結果來驗證準確性。當前，所有複雜的晶片都可以通過具有JTAG功能的接口來進行測試，這一技術也用在執行微處理器的硬體調試中。
此外，IEEE1532-2000系統內配置標準的發展平衡了IEEE1149.1結構，使得複雜可編程邏輯器件和現場可編程門陣列(FPGA)的編程可以現場進行。當前IEEE1149.4標準限於數字電子設備，並且僅覆蓋了具備JTAG功能的晶片。然而，在幾年後，混合信號測試總線標準IEEE1149.4將使得對模擬電路的測試成為可能。
圖論屬於處理實體(稱為節點)和節點間連接(稱為鏈路)的數學領域。一個重要的遍歷問題是在給定的曲線圖中找到一條線路，恰好能夠經過各邊一次而回到起始節點，這樣的線路稱為歐拉線路。只有當連接到每個節點的鏈路是偶數時，才有可能存在歐拉線路，這稱為具有偶度(even degree)。
由於不是所有的曲線圖都存在歐拉線路，共同的問題就是確定遍歷每條鏈路至少一次的最小長度線路。這個問題就是公知的郵遞員問題。利用稱為曲線圖歐拉化的方法把複製的鏈路添加到曲線圖中，這些複製的鏈路以這樣的方式添加，即，它們使得曲線圖中的每個節點都連接著偶數個鏈路。概括化的郵遞員問題，即熟知的鄉村郵遞員問題，就是確定曲線圖中特定鏈路子集的最短遍歷線路。間接或是直接曲線圖的鄉村郵遞員線路可在多項式時間中計算，而混合曲線(也就是含有間接和直接鏈路的曲線圖)的鄉村郵遞員線路就是NP-hard，一個簡單的方法是用表示遍歷損耗的邊來替換偶度的所有子曲線，然後在奇度的頂點上計算最小匹配。
近年來，產生了利用鄉村郵遞員線路算法的網絡協議一致性測試。在這項技術中，使用兩個確定性有限狀態機(deterministic finite statemachine)來分別模擬協議規範和協議執行。該測試由此與兩個狀態機的遍歷結果進行比較，並且重點放在最小化整個測試序列長度上。郵遞員線路技術也可類似用於根據網絡路由表來遍歷網絡中的所有鏈路。然而，網絡中隨時間變化的信號的發送和接收條件經常使統計建立的鄉村郵遞員線路無法實時完成。因此，本行業內缺少一種有效的方式來實時測試有線或是無線網絡的鏈路狀態，這就需要用一種方法來滿足此需求。
發明內容
因而，本文公開了應用於通信網絡的方法和算法，該通信網絡包含了多個網絡設備(這裡也稱為「網絡節點」，「節點」，或是「網絡站點」)，其每一個都具有在通信網絡中通信的裝置。掃描測試路由序列不依賴於用於網絡協議和路由通信的現有路由機制和協議而被構建。此舉是通過處在測試中的網絡的各個節點的廣播序列操作來完成的。作為一種選擇，掃描測試路由序列也可以通過連續運用鄉村郵遞員(「RPT」)線路算法來構建。連續的應用RPT算法可避免廣播操作對網絡的衝擊。在另一種配置中，掃描測試路由序列是通過在網絡中每個節點創建掃描鍊表，利用來自測試站點的深度優先搜索算法(「DFS」)探測網絡結構而得到在線計算的。
一旦建立了掃描測試路由序列，就會使用(deploy)漫遊測試代理來遍歷路由序列中的每條鏈路。漫遊測試代理是抽象的數據類型，它包含在一個或多個通信報文的數據有效載荷中而在網絡上傳輸。漫遊測試代理可包含源路由信息、待測屬性和中間結果。漫遊測試代理還可包括在每個或是被選網絡節點處可被調用的可執行代碼，用以執行或是修改已被代理執行的測試。測試的屬性可以是鏈路的連通性，節點路由配置，或是其它有用的屬性。
從下面的描述可以明顯的看出，本發明在現有方法之上提供了許多重要的有益效果。本發明提供了較低層的機制來自動解決有線或是無線網絡中出現的問題而無需依賴於網絡協議層或是相應的已建路由表。更進一步來說，通過繞開正常的路由系統，本發明有利地避免了對可能出現錯誤的路由表的循環依賴性。因而提供了能夠在網絡中迅速發現連通性問題的既健壯又簡化的方法。
附圖的簡要說明關於本發明的結構和操作的詳細說明，可以通過對附圖的學習而部分地了解，附圖中相同的參考標號表示了相同的部件，並且其中包括
圖1是根據本發明一個實施方案所述的示例性的有線、無線或是混合網絡拓撲的高層網絡圖；圖2是根據本發明一個實施方案所述的網絡圖，其示例性地顯示出了網絡中連接到不同節點的一組鏈路；
圖3是根據本發明一個實施方案所述的曲線圖，其示例性地顯示出了具有奇度的節點之間的一組鏈路；圖4是根據本發明一個實施方案所述的曲線圖，其示例性地顯示出了具有偶度的節點之間的一組歐拉化的鏈路；圖5是根據本發明一個實施方案所述的網絡圖，其示例性地顯示出了具有它們相應通信範圍和可能的通信鏈路的一組網絡設備；圖6是根據本發明一個實施方案所述的方框圖，其示例性地顯示出了廣播消息幀；圖7是根據本發明一個實施方案所述的方框圖，其示例性地顯示出了響應消息幀；圖8是根據本發明一個實施方案所述的方框圖，其示例性地顯示出了網絡線路消息幀；圖9A-9D是根據本發明一個實施方案所述的曲線圖，其示例性地顯示出了用於創建掃描測試路由序列的網絡線路技術；圖10是根據本發明一個實施方案所述的曲線圖，其示例性地顯示出了用於創建掃描測試路由序列的深度優先搜索技術；圖11是根據本發明一個實施方案所述的基於跳數的網絡地址表的例子；圖12示例性地顯示出了可與本文所述的各實施方案連接的無線網絡通信設備的方框圖；以及圖13示例性地顯示出了可與本文所述的各實施方案連接的計算機系統的方框圖。
詳細描述本文公開的實施方案提供了系統和方法，用以在有線或是無線網絡中實施邊界掃描測試。舉例來說，本文公開了一種方法，它允許網絡中的測試站點利用深度優先搜索技術來創建MAC層掃描測試路由序列，然後產生一個測試代理用以遍歷掃描測試路由序列中的鏈路，將有關掃描測試路由序列中各個鏈路的信息報告回測試站點。
在閱讀本說明書後，對本領域的技術人員來說，如何在各種實施方案和可選應用中實施本發明是顯而易見的。然而，儘管在這裡將描述本發明的各種可選實施方案，可以理解這些實施方案僅僅是示例性的，而不是限制性的。由此，各種可選實施方案的詳細描述不應解釋為限制所附權利要求書提出的本發明的範圍和外延。
圖1是根據本發明一個實施方案所述的示例性的有線、無線、或混合網絡50的高層網絡圖。在圖示的實施方案中，系統包括了與多個網絡設備10、20和30通信連接的網絡50。
網絡50可以是有線網絡、無線網絡、或是包括有線和無線的同類型的或是不同類型的網絡的組合。網絡50可以是個人區域網(「PAN」)，區域網(「LAN」)，廣域網(「WAN」)，或是集中包括了類似網際網路的全球通信網絡的分布式組合網絡。網絡50可以是自組織網絡(ad hoc)或是持續網絡並且可以是固定安裝的或是移動的，網絡50也可包括固定和移動組件的組合。另外，網絡50可傳送對應於單個網絡協議或多個網絡協議的通信。舉個例子，網絡50可攜帶802.3乙太網數據流和802.11無線數據流。
網絡設備優選地是能夠在類似網絡50的通信網絡中通信的設備。舉個例子，網絡設備10可以是個人電腦(「PC」)，膝上電腦，印表機，平板電腦，機頂盒，遊戲機，或是諸如個人數字助理(「PDA」)，蜂窩電話，尋呼機等無線通信設備和其他能夠和無線網絡進行數據通信的設備。諸如網絡設備10，20，30這樣不同的網絡設備通過網絡50通信連接。
在以下的詳細的說明中，類似網絡設備10的網絡設備可以稱為網絡設備、網絡節點、節點、無線通信設備、無線網絡設備和無線節點。儘管這裡使用了不同的名稱，網絡設備也可包括所有組件或是組件的最小子集和根據圖12和13描述的功能性能。
圖2是根據本發明一個實施方案的網絡圖，其中示例性地示出了網絡中連接到不同節點的一組鏈路；在所示的實施方案中，網絡設備10、20、30通過一系列的鏈路來連接通信。舉個例子，鏈路42連接節點10和節點20、鏈路44連接節點20和節點30、鏈路46連接節點30和節點10。順序經過鏈路42，44，和46就完成了網絡的遍歷，它在所示實施方案中是一個歐拉線路。
為了達到一致性和簡化說明的目的，這裡所指和詳細描述的不同鏈路將被描述為雙向和對稱的通信鏈路。因此，一個在特定的方向上(也就是從一個特定的源節點到特定的目的節點)的成功的鏈路測試表明從初始目的節點到初始源節點的相同鏈路的測試也是成功的。然而，本領域的技術人員可以理解，這裡的詳細說明所考慮的主要範圍包括了在定向和非對稱通信網絡中的所述技術的應用。
圖3是根據本發明一個實施方案例的曲線圖，示中示例性地示出了具有奇度的節點之間的一組鏈路。在所示的實施方案中，網絡54包括節點100、102、104、和106，通信鏈路A連接節點100和102。通信鏈路B連接節點100和104，通信鏈路C連接節點100和106。同樣的，通信鏈路D和F連接節點102和104，通信鏈路E和G連接節點104和106。圖中也示出了每個節點的度數，節點100，102和105是3度，而104是5度。
所示的網絡曲線圖不是歐拉形式，這意味著為了遍歷每條鏈路只一次，圖中的一些鏈路肯定會不止一次地被經過。舉個例子，按A，F，D，F，G，E，B，C，C的順序遍歷這些鏈路時，每條鏈路至少經過一次然後回到起始節點，而鏈路F和C經過了兩次。
圖4是根據本發明一個實施方案的曲線圖，其中示例性地示出了具有偶度的節點之間的一組歐拉化的鏈路；在所示的實施方案中，網絡54再次包括節點100、102、104和106。通信鏈路A連接了節點100和102，通信鏈路B連接了節點100和104，通信鏈路C和J連接了節點100和106。類似的，通信鏈路D，F和H連接了節點102和104，而通信鏈路E和G連接了節點104和106。圖中也示出了每個節點的度數，節點100、102和106是4度而節點104是六度。因為每個節點的度數是偶數，所以該網絡曲線圖是歐拉形式的。因此，按照A，F，D，H，G，E，B，C，J的順序遍歷鏈路，每條鏈路只單獨經過一次，最終回到第一個節點，也就是節點100。
圖5的網絡曲線圖分別示例性地示出了一組網絡設備210，220，230和240和它們相對應的通信區域211，221，231和241。此外，圖中還示出了所有可能的通信鏈路251，252，253，254，255和256。網絡200具有兩跳的最大半徑，因為由任意通信節點發出的通信報文廣播，最多兩跳就可以被網絡中的每個節點接收到。
在所示的實施方案中，可以使用連續的廣播方法來創建一個掃描測試路由序列。舉個例子，節點210最初發射只能由節點230接收的只有一跳的廣播消息。廣播消息可以是通信報文或是漫遊代理。在一個實施例中，通信報文的信息載荷中含有測試代理(test agent)。在接收後，節點230用確認信息來驗證鏈路251並記錄鏈路251的質量。在驗證鏈路和記錄鏈路質量後，節點230(和其他接收到初始廣播的節點)發送一個相應的一跳廣播消息而由節點210，節點220和節點240接收。
作為廣播消息的發起者，節點210抑制了由230發出的廣播消息。另一方面，節點220和240確認了廣播消息，因此分別驗證了鏈路253和鏈路252，也記錄了相應的鏈路質量。下一個重發廣播消息的節點(節點220或是節點240)將通過確認並記錄的鏈路質量來驗證鏈路254。此外，當節點220再次發送廣播消息，廣播消息到達節點210。因為節點210初始沒有得到來自節點220的確認，它會丟棄廣播消息，因此也就不再驗證鏈路255。另一種方法是，節點210通過節點230往節點220發送一個確認消息，因此也就驗證了鏈路255。有利的是，節點220通過來自經過節點230的確認消息確定鏈路255是間接鏈路。特別的是，潛在的鏈路256將根本無法驗證，因此這樣的鏈路根本不存在或是被認定為不可用。
有利的是，可用定向追溯(也就是反序)的方法把廣播消息的結果傳遞迴節點210。舉個例子，節點240將它從廣播消息中收集到的鏈路驗證和鏈路質量發送回節點230，節點230將從它的廣播消息中收集到的鏈路驗證和鏈路質量提供給節點210。類似的，節點220向節點230發送它的鏈路驗證和鏈路質量，節點230再次把信息傳遞給節點210。
圖6是根據本發明的一個實施方案示出的廣播消息幀300的方框圖。在所示的實施方案中，消息幀300包括了一系列的域。這些域包括了含有消息類型的類型域302，例如像前面根據圖5描述的那樣，它可以設置成表明消息類型是掃描測試路由序列廣播。域還包括發送地址域304，源節點地址域306，用來指示在報文丟棄前剩餘的跳數的存活時間(time-to-live)域308，代理識別域310，和優選地包含代理自身的代理域312。例如，代理域312可包含可執行指令。
圖7是根據本發明的一個實施方案，其中示出了反饋消息幀400的方框圖。在所示的實施方案中，消息幀400包含了一系列的域。這些域包括指示單播反饋消息的類型的類型域402，還包括接收地址域404，發送地址域406，目的地址域408，源節點地址域410，存活時間域412，代理識別域414，和優選地含有掃描測試廣播消息的結果的結果域416。在該實施方案中，結果域416設置成具有對應於掃描測試確定的屬性值的鏈路表。
圖8是根據本發明的一個實施方案，其中示出的網絡線路消息幀500的方框圖。在所示的實施方案中，消息幀包括一系列的域。這些域包括含有消息類型的類型域502，例如類型可表示為用以創建掃描測試路由序列的連續網絡線路消息。域還包括長度域504，源路由域506，其中域中起始地址和最終地址通常是網絡線路的出發點，存活時間域508，代理識別域510，代理域512，和結果域514。
在使用根據前面圖6-8所述的消息幀的實施方案中，在網絡中任意指定節點處開始創建掃描測試路由序列。發送廣播消息使得包含在廣播消息中的多種情況的漫遊鏈路測試代理可以遍歷整個網絡。舉個例子，廣播消息的報文格式可以是圖6所示的消息幀格式。有利的是，廣播消息幀在類型域指定了廣播操作，發送地址，起始源節點地址，報文存活時間，漫遊測試代理ID，和代理本身。代理本身通常指定了待執行的測試和待測的屬性，也包括了測試的可執行指令或是更改測試的可執行指令。
當來自起始節點(也可以稱為「指定節點」)的廣播消息(報文或是路由測試代理)被另一個節點接收時，兩個節點間的鏈路被驗證，鏈路質量被記錄。每個接收到初始廣播(層二節點)的節點將再次發送廣播消息(舉例來說，測試代理)並丟棄隨後接收到的相同的廣播消息。這就定義了一個廣播等級，起始節點在頂部，層二節點(也就是那些一跳遠的節點)是下一個，其餘的派生節點形成了層三，層四，等等直到網絡的邊界。
除了再次廣播測試代理，在層二或是更高層的每個接收節點將完成指定鏈路測試並對發送測試代理的親代節點提供單播反饋。前面根據圖7描述的這樣的反饋消息幀也包括了接收地址，發送地址，目的地址，源地址，代理ID和測試結果。測試結果通常是由測試確定的屬性值的鏈路表組成。有利的是，通過每個接收機確認廣播，接收機和廣播發送者之間的鏈路得到訓練，因此也得到了驗證。
測試結果中的屬性包括了鏈路的連通性，鏈路質量，相對信號強度指示器，節點路由配置或是其他有用的屬性。在一個實施方案中，測試結果以比特向量的形式表示。在這樣的設置中，一個具有5000個鏈路(比如，一個具有100個節點的全連通網絡)的網絡大致需要攜帶0.625K字節的數據。使用多於一個的通信報文可以將測試結果發送到指定的節點，例如在大型網絡的情況下。如果必需要確保穩定的傳輸，測試結果通信可以被確認和再次發送。一個每鏈路多比特方案也可以用來表明各種間隔等級的鏈路質量或是合併多個鏈路屬性。最後，網絡掃描測試可以使用小的數據報文，消除了由於無用數據而阻礙網絡的路由表。
在一個實施方案中，在每個接收端節點處記錄測試結果並通過確認報文發送回廣播節點。在這樣的實施方案中，希望中間節點(比如層二節點)能夠多次提供確認。舉個例子，在一個具有m跳網絡半徑的可執行前述的廣播操作的網絡中(也就是m-1層)，由初始節點發起廣播而由離指定節點一跳遠的節點做出的最大確認操作數，總共是m次確認。
這裡的網絡半徑定義成為了達到最遠端節點而必須由中間節點轉發的最小廣播操作數。為了減少中間節點處的確認數，可估計網絡廣播的半徑和每跳的往返時延，並在離指定節點n跳的每個廣播環路上計算所有節點的超時周期的適當值。通過這些超時參數，層二節點在向指定節點發送它的確認消息之前將等待累加多數或是所有來自它派生節點的確認消息。這樣的設置，具有簡化實施和減少存儲的優點。具體來說，中間節點僅僅只需知道如何向在廣播等級中它的中間媒體親代節點發送確認信息並等待它自己派生節點的反饋而無需在這些節點建立額外的路由表來幫助構建掃描測試路由序列。
一旦到達超時周期，所有在指定節點接收到的掃描測試序列結果將被用於構建鏈路圖，該圖顯示了測試中的網絡的連通性和每個鏈路的鏈路質量。這個鏈路圖是掃描測試路由序列。因此，在每個節點邊界掃描測試只需一次廣播操作。此外，在每個中間節點和葉節點處，網絡邊界掃描測試具有簡化實施、降低計算和存儲需求的優點。
圖9A-9D是根據本發明一個實施方案所述的用於創建掃描測試路由序列的網絡線路技術的曲線圖；在圖9A中示出了包括四個節點620，622，624和626的網絡，其中還示出了所有理論鏈路，包括鏈路630，632，634，636，638和640。在圖9B中，兩條額外的鏈路642和644添加到網絡圖中以使得該圖符合歐拉形式。在所示的實施方案中，每個節點620，622，624，和626都具有偶度。網絡線路(也就是郵遞員線路)可以構建成640，634，636，630，638，642，632和644。
這樣的網絡線路開始於節點620，遍歷網絡中的每條鏈路恰好一次，在節點620處結束。
在圖9C所示的實施方案中，節點620和624是不能通信的。舉個例子，它們可能是不在彼此範圍以內的無線通信設備。因此，鏈路640的初始遍歷(也就是測試)驗證失敗。掃描測試路由序列創建過程因此刪除鏈路640和類似644的任何等效鏈路。在做出這一改動後，圖9C示出了剩餘的鏈路，這就需要網絡線路構建成636，634，632，638，642和630。
該網路線路再次開始於節點620，遍歷網絡中的每條鏈路恰好一次，在節點620處結束。
在圖9D所示的實施方案中，當掃描測試路由序列程序沿新的網絡線路路由到達節點622時，將測試到鏈路638上的故障。在這一點上，掃描測試路由序列程序將刪除目前所有成功測試到的鏈路，為餘下圖中所剩節點構建新的網絡線路，也就是通過鏈路630連接的節點620和節點622。通過添加新的鏈路646將所剩的子圖轉化為歐拉形式。子圖的網絡線路現在可構建成630和646這裡，網絡線路開始於節點622，經過子集中的每條鏈路恰好一次，在節點622處結束。
一旦鏈路630和646得到驗證，累加測試結果並傳送回初始開始點，也就是節點620。返回結果的路徑是重構鏈路的逆序，也就是632，634和636。可選的是，掃描測試路由序列程序在遍歷(和驗證)鏈路630之後在620檢測它的到達返回，程序可能在此終止，而刪除鏈路646的冗餘遍歷和通過鏈路632，634和636的追蹤返回節點620是有益的。
在使用鄉村郵遞員線路的實施方案中，通過為每個可遍歷網絡子圖構建的一系列鄉村郵遞員線路來創建路由掃描測試序列。具體來說，測試中的網絡由間接曲線來表示。鄉村郵遞員線路因此可以構建並代表了通過網絡遍歷每個鏈路(「源路由」)的完整路由。一個漫遊測試代理根據源路由配置來遍歷曲線。當它遍歷整個網絡時，測試代理包括源路由的拷貝。對每個被遍歷的鏈路來說，執行指定的鏈路測試並記錄結果。測試結果可立即報告回指定節點或由漫遊測試代理攜帶以便晚些報告。
當一個鏈路順利測試出時，漫遊測試代理根據源路由前進到下一個節點。如果一個鏈路測試失敗時，也就是說，如果它出了故障或是不存在，當前線路就被中止。在這點上，構建新的子曲線圖，刪除已測的所有鏈路而不管成功與否，同時也刪除在鏈路刪除後不再連接到子圖的節點。這樣就構建了新的鄉村郵遞員線路，先前線路中止的節點就成為線路的起始點(舉例來說指定節點)。按照這種方式，漫遊測試將一直持續到鄉村郵遞員線路最終順利完成。漫遊測試代理接著沿所有成功的鏈路遍歷而回到線路的初始起始點。通過這種方式，網絡中所有鏈路將至少測試一次。
有利的是，隨後構建的鄉村郵遞員線路的子圖總是要比先前線路的圖或子圖更加簡單(也就是更少的鏈路和更少的節點)。這就確保了算法的收斂性。鄉村郵遞員線路的構建是計算性的多項式並且在網絡節點處可輕易提供，因為多數現代通信設備不受節點處理功率的限制。此外，連續鄉村郵遞員運算的使用避免了由於廣播消息的操作對網絡的不必要衝擊。複雜度(不包括出錯的發送數)是O(N2)，其中N代表了測試的網路中的全部節點數。
圖10是根據本發明的一個實施方案，其示出了用於創建掃描測試路由序列的深度優先搜索技術的曲線圖。在圖示的實施方案中示出了一系列網絡節點A-I連同在各個節點間存在的等級通信鏈路。也可出現其它的通信鏈路，舉個例子，在類似節點B，C和D的同一等級的節點之間的鏈路。
在所示的實施方案中，通過來自於測試站點的深度優先搜索程序探測網絡曲線圖中的節點，可在線計算掃描測試路由序列。如圖所示，節點A是測試站點。深度優先搜索分兩個階段進行。在第一個階段，主節點構建了一個掃描鍊表，它包括它所有相鄰節點的列表。這可以通過發送出一個廣播消息來實現。在第二個階段，主節點向它相鄰列表中的每個節點發送一個單播信息。單播信息是連續發送出去的，在收到第一次發送的單播信息已被接收的響應之前，將不會發送第二個單播信息。
因此，一系列的廣播和單播信息通過對遍歷整個網絡的深度優先搜索的控制來建立一個全面的掃描鍊表。在所示的實施例中，流程沿下面的路徑進行A，B，E，F，C，G，D，H，I在構建掃描鍊表時，測試站點A選擇了一個優選地沒有被用於啟動任何先前掃描鏈構建的測試向量標識符。此外，一個深度標識符變量被初始化為0，接著測試站點認定它本身是主節點，並發送一個廣播回應請求來收集離它最近鄰居的列表。廣播包含測試向量標識符來唯一標識這輪特定測試。此外，廣播還包括了深度標識符，它標示了到目前為止連接到掃描鏈上的節點數(比如跳數)。
當測試站點A收到了廣播回應時，記錄被創建，它包括測試向量標識符，深度標識符，鄰居指針(舉例來說，指向最近鄰居的指針)和所有最近鄰居的列表。測試站點A還包括一個標記，它用來指定當最後一個鄰居響應時掃描鏈的構建將終止。最後，測試站點A向它的最近鄰居發送單播信息來通知最近鄰居(比如節點B)成為主節點並繼續掃描鍊表的構建。
當最近的鄰居(比如節點B)接收到了來自測試站點的單播信息時，它要認定自己是主節點並發送出再次廣播的測試消息來識別它的最近鄰居。由節點B發送出的廣播消息包括了來自初始廣播的相同的測試向量識別符。當節點B接收到它的回聲響應時，它也創建了一個包括測試向量標識符，深度標識符，相鄰箭頭(舉例來說，最近鄰居的指針)和所有最近鄰居列表的記錄。在記錄中節點B也包括了一個標記來表明在完成後掃描鍊表應該返回到節點A，舉例來說，把節點A加入到最近鄰列表的末尾。最後，節點B向它最近的鄰居(比如，節點E)發送單播消息，通知該節點成為主節點並繼續掃描鍊表的構建。單播消息包括了來自初始消息的相同的測試矢量標識符，但是深度標識符將增加，以表明另一節點添加到鏈中。
在節點E和F處將繼續這一過程並當那部分子圖返回到測試站點A時，測試站點A跳到由它記錄標識的下一最近鄰居，通知節點C認定自己是主節點並繼續搜索鍊表的創建。有利的是，深度標識符從不重置，這樣當測試站點A向節點C發送單播消息時，深度標識符是7，反映了沿鏈從節點A到節點C的跳數(下和後)。
該過程將繼續，直到測試站點跳達它的鄰居列表中的最後一個節點，掃描鍊表在此刻也就完成。有利的是，可以通過邊界掃描鏈，利用掃描鍊表來發送探測消息。舉個例子，向掃描鏈上第n個節點發送消息，測試站點A發送具有三個域的廣播消息。廣播消息域包括(a)目的地節點n；(b)下一跳節點k(初始為1，但是當報文前進時每次增加)，以及；(c)測試向量標識符(用於查找記錄待用的合適的掃描鏈)。
無論何時發送具有目標節點n的廣播，每個節點查找測試向量標識符，並確定是否在轉發消息時使用k作為深度標識符。如果節點使用k時，它接收消息並再次廣播消息，下一跳標識符為k+1。如果主機接收到n＝k的消息，那麼它就是指定的接收者並由它處理消息。為對這樣的消息做出響應，產生了新的具有不定目標地址的消息。這將導致消息路由回測試站點A。在最壞情況下，用於鄉村郵遞員線路的貪婪在線算法在一個具有M個邊的圖中將遍歷2M個邊。根據圖10描述的深度優先搜索會產生這樣的性能限制，因此在所有可能的貪婪在線算法中存在著最佳算法。
有利的是，所述的用以創建掃描測試路由序列的深度優先搜索技術具有簡化實施，網絡節點計算量少的優點，並且通過在網絡圖的深度上擴展掃描測試消息來避免網絡擁塞。此外，此項技術可針對任何規模的網絡進行升級，從而獲得不依賴於現存路由表和網絡層通信協議的更加穩定的通信。
圖11是根據本發明實施方案的基於跳數(也就是掃描鏈位置)的網絡地址列表。在所示的網絡地址列表中，節點A因為是根節點，所以它的網絡地址值為0。節點B具有一的網絡地址，因為沿掃描測試路由序列，只需一跳就可以到達它。儘管在常規的路由中，C節點被認為是距離A節點一跳，根據掃描測試路由序列，節點C距離節點A七跳，因此它的網絡地址是七。類似的，節點D具有十一的網絡地址。相應的，節點E的網絡地址是2，節點F的網絡地址是4，節點G的網絡地址是8，節點H的網絡地址是12，節點I的網絡地址是14。
在一個實施方案中，節點A通過任意具有較低網絡地址的中間節點向特定的節點路由一個通信報文。因此，為了向節點I發送通信報文，節點A初始發送通過節點B，節點C，或是節點D的報文，並確保報文達到節點I。這是基於掃描測試路由序列的連續特性和接收節點按照該序列向下一節點轉發通信報文。
圖12示出了可與本文描述的各實施方案一同使用的無線通信設備700的方框圖。舉個例子，無線通信設備700可與手機或PDA網絡設備結合使用，或是作為無線網狀網中感應節點的一部分。然而，本領域的技術人員很清楚，也可以使用其他無線通信設備和(或)結構。
在所示的實施方案中，無線通信設備700包括了天線702，雙工器704，低噪聲放大器(「LNA」)，功率放大器(「PA」)708，調製電路710，基帶處理器712，揚聲器714，麥克風716，中央處理單元(「CPU」)718，和數據存儲區720。在無線通信設備700中，射頻信號(「RF」)由天線702發送和接收。雙工器704具有交換作用，在發送和接收信號的路徑間連接天線702。在接收路徑上，已接收射頻信號從雙工器704連接到了LNA706。LNA706放大接收到的RF信號，並將已放大信號連接到調製電路710的調製部分。
常規的調製電路710在一個集成電路(「IC」)上結合了解調器和調製器。解調器和調製器也可以是分離元件。解調器剝離了RF載波信號而留下了基帶接收音頻信號，然後將解調器的輸出發送到基帶處理器712。
如果基帶接收音頻信號包含了音頻信息，那麼基帶處理器712就對信號進行解碼並轉化為模擬信號。接著信號被放大並發送到揚聲器714。基帶處理器712也接收來自麥克風716的模擬音頻信號。這些模擬信號轉化成數位訊號並由基帶處理器712編碼。基帶處理器712也編碼數位訊號用於傳輸和產生發送到調製電路710的調製部分的基帶發送音頻信號。調製器將基帶發送音頻信號和RF載波信號混頻產生RF載波信號，發送到功率放大器708。功率放大器708放大RF發送信號並發送到雙工器704，在此處信號被交換到天線部分由天線702來發送。
基帶處理器712也與中央處理單元718連接通信。中央處理單元718可訪問數據存儲區720，中央處理器718被配置成易於執行存儲在數據存儲區720的指令(也就是電腦程式或是軟體)，電腦程式也可以由基帶處理器712來接收並存儲於數據存儲區720，或是接收時執行。這樣的電腦程式，當執行時，可使無線通信設備700執行本發明前述的各種功能。
在本說明書中，術語「計算機可讀媒體」是指用於為無線通信設備700提供可執行指令，而由中央處理單元718來執行的任何媒體。例如，這些媒體可包括數據存儲區720，麥克風716(通過基帶處理器712)和天線702(也通過基帶處理器712)，這些計算機可讀媒體是用以為無線通信設備700提供可執行代碼，編程指令，和軟體的設備。當由中央處理單元718來執行可執行代碼，編程指令和軟體時，將導致中央處理單元718執行這裡前述的創造性特徵和功能。
圖13是示出可與這裡描述的各種實施例連接的計算機系統750的方框圖。舉個例子，計算機系統750可用於連接網絡設備，網絡接入點，路由器，網橋，或是其他網絡基礎結構組件。然而，本領域的技術人員很清楚，也可以使用計算機系統和/或是架構。
計算機系統750優選地包括一個或多個處理器，例如處理器752。也可提供額外的處理器，例如管理輸入輸出的附助處理器，用於執行浮點數學運算的附助處理器，具有適於快速執行信號處理算法架構的專用微處理器(比如數位訊號處理器)，主處理器的下級從處理器(比如後端處理器)，用於雙向或是多處理系統的附加處理器。這類輔助處理器可以是分離的處理器，或是與處理器752集成在一起。
處理器752優選地連接於通信總線754。通信總線754可包括方便在存儲區和計算機系統750的其他並行元件之間進行信息傳送的數據通道。通信總線754進一步可提供用於與處理器752通信的一組信號，包括了數據總線，地址總線，和控制總線(沒有示出)。通信總線754可包括標準或是非標準的總線結構。例如，諸如兼容工業標準結構(「ISA」)的總線結構。擴展工業標準架構(「EISA」)，微通道結構(「MCA」)，並行元件互連(「PCI」)局部總線，或是由電子和電器工業協會發起的標準，包括IEEE488通用接口總線(「GPIB」)，IEEE696/S-100，等等。
計算機系統750優選地包括一個主存儲區756和可能包括一個次存儲區758。主存儲區756提供由處理器752執行的程序的指令和數據的存儲。主存儲區通常是基於半導體的存儲區，如動態隨機接入存儲區(「DRAM」)和/或靜態隨機接入存儲區(「SRAM」)。其他基於半導體的存儲類型，舉個例子，包括了同步動態隨機接入存儲(「SDRAM」)，隨機動態隨機接入存儲器(「RDRAM「)，鐵電(ferroelectric)隨機接入存儲器(」FRAM」)和類似的存儲器，包括只讀存儲器(「ROM」)。
輔助存儲器758可選的包括硬碟驅動器760和/或可移動存儲驅動器762，舉個例子，軟盤驅動器，磁帶驅動器，壓縮盤(「CD」)驅動器，數字通用盤(」DVD「)驅動器，等等。可移動存儲驅動器762以公知的方式讀寫移動存儲區媒體764。舉例來說，移動存儲媒體764也可包括軟盤，磁帶，CD，DVD等等。
可移動存儲媒體764通常是計算機可讀媒體，其上存儲了計算機可執行代碼(也就是軟體)或是數據。存儲於可移動存儲媒體764的計算機軟體或數據可作為電子通信信號778讀入到計算機系統750中。
在可選的實施方案中，輔助存儲器758可包括其他允許將電腦程式或是其他數據或指令加載到計算機系統750的類似設備。這類設備可包括，舉例來說，外部存儲媒體772和接口770。外部存儲媒體772可以是外部硬碟驅動器或外部光碟機動器，或是外部磁電光碟機動器。
輔助存儲器758的其它例子可以包括基於半導體的存儲器，例如可編程只讀存儲器(「PROM「)，可擦可編程只讀存儲器(」EPROM「)，電可擦只讀存儲器(」EEPROM「)，或是快閃記憶體(基於塊存儲，類似EEPROM)。也包括其他可讀存儲單元772和接口770，允許從可移動存儲單元772向計算機系統750發送軟體和數據。
計算機系統750可包括通信接口774，通信接口774允許在計算機系統750和外部設備(比如印表機)，網絡或信源之間傳送軟體和數據。舉例來說，經通信接口774，網絡伺服器可將計算機軟體或是可執行代碼發送到計算機系統750。通信接口774可以是數據機，網卡(「NIC」)，通信埠，PCMCIA插槽和卡，和紅外線接口，和IEEE1394火線(fire-wire)等等。
通信接口774優選地實施工業已頒布的協議標準，如乙太網IEEE802標準，光纖信道，數字用戶線(「DSL」)，異步數字用戶線(「ADSL」)，幀中繼，異步傳輸模式(「ATM」)，綜合數字業務網(「ISDN」)，個人通信業務(「PCS」)，傳輸控制協議/網際網路協議(「TCP/IP」)，串行線網際網路協議/點對點協議(」SLIP/PPP「)，等等，但也可實施定製的或是非標準的接口協議。
經通信接口774的軟體和數據通常是以電子通信信號778的形式傳輸的。這些信號778通常經通信信道776提供給通信接口774。通信信道776可通過使用包括有線或是電纜，光纖，常規的電話線，蜂窩電話鏈路，射頻(「RF」)鏈路，或是紅外線鏈路等各類通信設備來實現攜帶信號778。
計算機可執行代碼(也就是電腦程式或軟體)存儲在主存儲區756和/或次存儲區758中。電腦程式也可通過通信接口774來接收並存於主存儲器756和/或輔助存儲器758中。這類電腦程式，當執行時，使得計算機系統750可執行本發明前述得各種功能。
在本說明書中，術語「計算機可讀媒體」是指用於為計算機系統750提供計算機可執行代碼(比如軟體和電腦程式)的任何媒體。例如，這些媒體包括主存儲器756，輔助存儲器758(包括硬碟驅動器760，可移動存儲媒體764和外部存儲媒體772)，還有任何通信連接到通信接口774的並行設備(包括網絡信息伺服器或其他網絡設備)這些計算機可讀媒體是向計算機系統750提供可執行代碼，編程指令，和軟體的設備。
在使用軟體實現實施方案中，軟體可存儲在計算機可讀媒體上，通過移動存儲驅動器762，接口770，或是計算機接口774來裝到計算機系統750中。在這樣的實施例中，軟體是以電子通信信號778的形式裝入到計算機系統750中。由處理器752執行的軟體，使得計算機系統752可執行前述具有創造性的特徵和功能。
本發明的各種實施方案也可普遍應用於硬體使用，例如，類似特定用途集成電路(「ASIC」)或是現場可編程門陣列(「FPGA」)，對於本領域的技術人員來說，實施能夠執行這裡所述功能的硬體狀態機也是顯而易見的。各類實施例也可通過利用硬體和軟體的組合來實施。
儘管這裡所示和詳細描述的系統和方法是完全能夠獲得上述本發明的目標的，可以理解的是說明書和這裡所述的附圖代表了本發明的優選實施例，因此代表了本發明預期的發明主題。進一步可以理解，本發明的範圍包括了對本領域的技術人員來說是顯而易見的其他實施例，本發明的範圍除所附權利要求書以外，不受任何限制。
權利要求
1.一種用於測試與多個網絡設備通信連接的網絡中的鏈路的方法，包括建立包括通信網絡中每條鏈路的MAC層掃描測試路由序列；創建配置成能遍歷所述掃描測試路由序列中每條鏈路的測試代理；和在所述通信網絡上使用所述測試代理，其中所述測試代理檢查所述掃描測試路由序列中的鏈路以確定與該鏈路相關的信息。
2.根據權利要求1所述的方法，其中所述建立步驟包括從所述通信網絡中的多個網絡設備的每一個發送一系列的廣播信息。
3.根據權利要求1所述的方法，其中所述建立步驟包括網絡線路的連續應用。
4.根據權利要求3所述的方法，其中所述網絡線路是郵遞員線路。
5.根據權利要求1所述的方法，其中所述建立步驟包括執行通信網絡的深度優先搜索。
6.根據權利要求5所述的方法，其中所述執行步驟包括在通信網絡的每個網絡設備處構建掃描鍊表。
7.根據權利要求5所述的方法，其中所述執行步驟包括根據跳數產生規範的尋址方案。
8.根據權利要求1所述的方法，其中所述測試代理檢查所述掃描測試路由序列中的每條鏈路，從而確定與該通信網絡相關的信息。
9.根據權利要求1所述的方法，其中所述測試代理向測試站點報告鏈路信息。
10.根據權利要求1所述的方法，進一步包括創建多個測試代理；和在通信網絡上使用所述多個測試代理中的每一個。
11.根據權利要求10所述的方法，其中所述多個測試代理向單個測試站點報告鏈路信息。
12.根據權利要求1所述的方法，其中所述測試代理是配置成在一個或多個通信報文的數據載荷中傳輸的抽象數據類型。
13.根據權利要求12所述的方法，其中所述測試代理包括測試類型標識符，其用於識別待在鏈路上執行的測試的類型。
14.根據權利要求12所述的方法，其中所述測試代理包括源路由信息。
15.根據權利要求12所述的方法，其中所述測試代理包括中間鏈路信息結果。
16.根據權利要求12所述的方法，其中所述測試代理包括與鏈路的檢查有關的待分析的鏈路屬性。
17.根據權利要求16所述的方法，其中所述鏈路屬性為鏈路連通性狀態。
18.根據權利要求16所述的方法，其中所述鏈路屬性為網絡設備路由配置。
19.根據權利要求12所述的方法，其中所述測試代理包括與鏈路的檢查有關的待被運行的可執行指令。
20.根據權利要求19所述的方法，其中在檢查鏈路時所述可執行指令更改所述測試代理執行的測試。
21.根據權利要求19所述的方法，其中所述可執行指令是在所述多個網絡設備的子集處調用的。
22.一種用於測試與多個網絡設備通信連接的網絡中的鏈路的系統，包括具有網絡通信設備和存儲器的測試站點，所述測試站點通過網絡與多個網絡設備通信連接；包括所述網絡中的每條鏈路的掃描測試路由序列；測試代理，其被配置成檢查所述掃描測試路由序列中的鏈路，從而確定與該鏈路有關的信息。
23.根據權利要求22所述的系統，其中所述網絡通信設備是無線收發器。
24.根據權利要求22所述的系統，其中所述測試代理由所述測試站點創建。
25.根據權利要求22所述的系統，其中所述測試站點被進一步配置成向測試站點報告鏈路信息。
26.根據權利要求22所述的系統，其中所述測試代理被進一步配置成檢查所述掃描測試路由序列中的每條鏈路，從而確定與所述通信網絡有關的信息。
27.根據權利要求22所述的系統，其中所述測試代理是配置成在一個或多個通信報文的數據載荷中傳輸的抽象數據類型。
28.根據權利要求22所述的系統，其中所述測試代理包括測試類型標識符，其用於識別待在鏈路上執行的測試的類型。
29.根據權利要求22所述的系統，其中所述測試代理包括源路由信息。
30.根據權利要求22所述的系統，其中所述測試代理包括中間鏈路信息結果。
31.根據權利要求22所述的系統，其中所述測試代理包括與鏈路的檢查有關的待分析的鏈路屬性。
32.根據權利要求31所述的系統，其中所述鏈路屬性為鏈路連通性狀態。
33.根據權利要求31所述的系統，其中所述鏈路屬性為網絡設備路由配置。
34.根據權利要求22所述的系統，其中所述測試代理包括與鏈路的檢查有關的待被運行的可執行指令。
35.根據權利要求34所述的系統，其中在檢查鏈路時所述可執行指令更改所述測試代理執行的測試。
36.根據權利要求34所述的系統，其中所述可執行指令是在所述多個網絡設備的子集處調用的。
全文摘要
提供了用於為具有多個網絡節點的有線或是無線網絡提供邊界掃描測試的系統和方法。該系統包括了與網絡通信連接的測試站點。測試站點創建MAC層掃描測試路由序列，該序列包括網絡中的每跳鏈路並獨立於用於網絡的路由機制和協議。測試站點還創建了測試代理，其被配置成用以遍歷掃描測試路由序列中的每條鏈路。然後在網絡中使用測試代理，在測試代理檢查連接後，將連接信息報告回測試站點。掃描測試路由序列可以通過從網絡中的一個或多個節點發送出一系列的廣播消息來創建，從而利用網絡線路覆蓋整個網絡，或是在整個網絡中執行深度優先搜索。
文檔編號H04L12/24GK1788208SQ200380110362
公開日2006年6月14日 申請日期2003年10月31日 優先權日2003年5月13日
發明者唐納德·W·吉利斯, 汪衛林, 麥可·P·諾瓦 申請人:基永有限公司