[發(fā)明專利]一種網(wǎng)絡(luò)驗證的方法、裝置、計算機存儲介質(zhì)及電子設(shè)備

有效

• 申請?zhí)枺?/td>: 202010783828.4
• 申請日: 2020-08-06
• 公開（公告）號: CN112054921B
• 公開（公告）日: 2021-09-03
• 發(fā)明（設(shè)計）人: 王之梁;葉方丹;尹霞;施新剛;翟恩南;劉洪強;吳鑫;王春生;馬效東;張銘;佘敦成;馬卿;程飆;郭天晨
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 北京安信方達知識產(chǎn)權(quán)代理有限公司 11262
• 代理人: 蔣冬梅;栗若木

本文公開一種網(wǎng)絡(luò)驗證的方法、裝置、計算機存儲介質(zhì)及電子設(shè)備，本發(fā)明實施例在計算待驗證網(wǎng)絡(luò)中每一個設(shè)備在K?failure場景下所有的路由后，確定每一個路由作為最優(yōu)路由的約束條件，根據(jù)確定出的約束條件對待驗證網(wǎng)絡(luò)進行網(wǎng)絡(luò)控制平面驗證，通過路由計算和約束條件的計算，快速的考慮了K?failure場景，實現(xiàn)了適用于大型網(wǎng)絡(luò)的驗證，為提升網(wǎng)絡(luò)運維效率提供了技術(shù)支持。

技術(shù)領(lǐng)域

本文涉及但不限于計算機網(wǎng)絡(luò)技術(shù)，尤指一種網(wǎng)絡(luò)驗證的方法、裝置、計算機存儲介質(zhì)及電子設(shè)備。

背景技術(shù)

隨著計算機網(wǎng)絡(luò)規(guī)模的不斷擴大，無論是設(shè)備的數(shù)量、所使用的協(xié)議類型，還是配置的復(fù)雜程度都在持續(xù)上升。對于大型網(wǎng)絡(luò)的維護人員而言，人工發(fā)現(xiàn)并定位當前網(wǎng)絡(luò)可能存在的問題，或在引入新設(shè)備、變更原有設(shè)備配置之后，保證網(wǎng)絡(luò)按照預(yù)期正確且穩(wěn)定地運行，均是比較困難的。

網(wǎng)絡(luò)控制平面驗證是一種幫助維護人員快速發(fā)現(xiàn)網(wǎng)絡(luò)配置問題的技術(shù)。配置網(wǎng)絡(luò)運行所需滿足的網(wǎng)絡(luò)屬性(如從設(shè)備A到設(shè)備B的流量可達)后，通過維護人員將網(wǎng)絡(luò)拓撲信息和設(shè)備配置信息輸入加載網(wǎng)絡(luò)控制平面驗證算法的工具，可以快速確定網(wǎng)絡(luò)屬性是否滿足預(yù)期，減少維護人員對網(wǎng)絡(luò)屬性的分析，從而縮短維護人員發(fā)現(xiàn)網(wǎng)絡(luò)故障的時間，提升網(wǎng)絡(luò)運維的效率。

以下就相關(guān)技術(shù)中的網(wǎng)絡(luò)控制平面驗證算法進行簡要介紹：

1、Batfish算法：通過控制平面模型生成數(shù)據(jù)平面模型；利用數(shù)據(jù)平面模型對網(wǎng)絡(luò)屬性進行驗證。當存在復(fù)數(shù)的網(wǎng)絡(luò)環(huán)境時，需要針對不同的網(wǎng)絡(luò)環(huán)境生成相應(yīng)的數(shù)據(jù)平面模型，然后確定網(wǎng)絡(luò)屬性在復(fù)數(shù)的網(wǎng)絡(luò)環(huán)境下是否滿足預(yù)期。簡言之，Batfish算法是仿真(Simulate)算法與已有數(shù)據(jù)平面驗證算法的結(jié)合。

2、ARC算法(網(wǎng)絡(luò)控制平面驗證的一種圖算法)：將網(wǎng)絡(luò)轉(zhuǎn)化為一張帶權(quán)的有向圖；將每個點拆分為入點和出點，然后根據(jù)協(xié)議的管理距離(AD)值，對每條邊賦權(quán)，以確定生成的有向圖在協(xié)議本身的優(yōu)先順序與原網(wǎng)絡(luò)一致；利用已有的圖算法確定可達性和K-failure(在網(wǎng)絡(luò)任意不超過K條鏈路故障的情況下，指定設(shè)備的可達性是否滿足)等屬性是否滿足預(yù)期。

3、Minesweeper算法：核心是對網(wǎng)絡(luò)進行編碼，包括：建立一套完整的符號體系；描述網(wǎng)絡(luò)各個階段的行為，利用符號體系描述網(wǎng)絡(luò)屬性成立所需要滿足的邏輯表達式；將邏輯表達式輸入約束求解器Z3中，求解邏輯表達式是否始終滿足，若不滿足將給出反例，反例標識網(wǎng)絡(luò)屬性無法滿足預(yù)期。

對大型網(wǎng)絡(luò)采用上述網(wǎng)絡(luò)控制平面驗證算法進行網(wǎng)絡(luò)屬性是否滿足預(yù)期的判斷，分別存在以下問題：如果存在復(fù)數(shù)環(huán)境，Batfish算法需要生成相同數(shù)量的數(shù)據(jù)平面模型，以進行數(shù)據(jù)平面驗證。當需要確定網(wǎng)絡(luò)有小于或等于k條鏈路發(fā)生故障時，判斷網(wǎng)絡(luò)屬性是否滿足預(yù)期的效率會急轉(zhuǎn)直下，也就是說，如果網(wǎng)絡(luò)中一共存在m條鏈路，那么小于或等于k條鏈路發(fā)生故障的情況有種，而在大型網(wǎng)絡(luò)中，鏈路數(shù)量成千上萬，判斷效率過低會導(dǎo)致Batfish算法無法使用。ARC算法的判斷效率基本滿足要求，但ARC算法將網(wǎng)絡(luò)簡化為加權(quán)有向圖，弱化了對網(wǎng)絡(luò)的描述能力，許多復(fù)雜的協(xié)議策略無法得到體現(xiàn)，降低了判斷結(jié)果的可靠性。Minesweeper算法的描述能力基本滿足要求，由于其編碼了邊故障的情況，因此驗證k-failure屬性時花費時間不會呈指數(shù)型增長；但通過選取一小部分網(wǎng)絡(luò)進行驗證可以發(fā)現(xiàn)，Minesweeper算法單次驗證時間特別長，一般需要耗費數(shù)小時的時間；另外，Minesweeper算法在網(wǎng)絡(luò)規(guī)模較大、配置較復(fù)雜時，因為Minesweeper將網(wǎng)絡(luò)所有的策略都編碼進了一個龐大的邏輯表達式，然后依靠約束求解器Z3去求解，其本身驗證效率就比較低。而可滿足性模理論(SMT，Satisfiability ModuloTheories)的求解本身是一個非決定性多項式時間完全(NPC，NP-Complete)問題，不論如何優(yōu)化，都無法避免其在理論上隨邏輯表達式的規(guī)模指數(shù)增長；即Minesweeper算法也很難在大型網(wǎng)絡(luò)中應(yīng)用。

綜上，相關(guān)技術(shù)中的網(wǎng)絡(luò)控制平面驗證算法，無法適用于大型網(wǎng)絡(luò)。

發(fā)明內(nèi)容