Perl語言遍歷樹形結構的算法設計——利用cisco鄰居發現協議遍歷全網絡的思路

先來點鋪墊，網絡工程師一枚，兩年前沒事就愛逛逛智聯招聘，發現招聘上總是有一條“會腳本語言中perl/php/python”一種。忘記當時怎么想的了，選的perl。因為現如今是python的天下了，很多人鼓吹python說perl已死，兩年期間也猶豫過。但是這兩天上手后，發現perl的魅力真是無窮無盡的，尤其是對于網工這行需要檢查狀態、處理大量文本信息，perl自帶的正則表達式功能強悍，十分合適。

最近幾個月，perl的learning和program終于看完了，準備上手寫代碼。第一個試手的腳本是讀取excel表格，第二個腳本是利用perl讀取核心交換機的cisco鄰居協議信息，之后提取協議文本中的IP地址，遍歷網絡中所有交換機并讀取其cdp信息，直至形成網絡拓撲圖信息。

在開發腳本期間，無論是Telnet::Cisco模塊還是后來干脆參照著CISCO模塊的處理方式直接用了其父類TELNET模塊（cisco模塊沒有寫可以用來判斷登錄是否順利的waitfor方法，為了使用Telnet模塊的waitfor方法猜交換機密碼，哈哈，懶是一種美德。），開發讀取show cdp neighbor detail信息方法都比較順利（這些方法以后寫博）。

但是當設計遍歷全公司網絡時，碰了釘子。

剛開始考慮將交換機名稱作為hash的key，IP地址作為value。通過簡單的for循環遍歷key，來實現全網絡的發現和遍歷（后面有詳細介紹）。但是因為hash本身的特性，總是會在某一分支的幾臺交換機間發生重復訪問的情況。后來加入數組變量還是同樣情況。苦思冥想了一天半時間，在稿紙上反復的演練設計，最后找到了合適的算法（雖然可能運行效率不是最高的，但方法是正確的，如大神有更好的方法歡迎推薦！）。下面進入正題：

先來看下網絡結構：

思科園區網絡的推薦網絡模型，主要分核心層、匯聚層、接入層。而在實際應用中，規模龐大的園區網絡，因為種種條件（資金、環境等等）制約，存在次級匯聚層、接入層與接入層串聯等結構出現。

因此，像筆者公司的網絡，屬于復雜的樹形結構。

第二，簡單介紹一下算法設計過程：

筆者剛開始對于網絡結構的遍歷算法，想的比較簡單了，

（1）最開始的方法，先聲明三個hash——dataHash，readHash，cmpHash，dataHash存入有cdp信息加工得到的交換機名與IP地址對，先將dataHash信息存入readHash，然后遍歷readHash的IP，讀取每臺交換機的cdp信息形成hash并賦值給dataHash。一輪遍歷完畢后，將readHash賦值給cmpHash。然后比較cmpHash和dataHash，選取cmpHash沒有的鍵值對，然后賦值給readHash再重復上述步驟，直到遍歷完整個網絡拓撲。

后來發現該方法中單純的使用Hash，總是會訪問到最后一層結構后，會卡在幾個鄰居交換機之間循環訪問，無法跳到上一層結構。出現此問題，首先是因為Hash本身遍歷key是無序的，加上筆者思路有誤，最終失敗了。還有，筆者在Hash賦值過程中簡單的使用了“=”，后經測試驗證“=”僅僅將內存地址進行了相互賦值，實際上三個Hash是同一個Hash。最后，筆者編制了一個方法，將三個Hash間由相互賦值變為了“復制”；

（2）改進后，引入了數組機制，也就是將readHash簡單替換為了數組，但是效果不佳；

（3）再次改進，將cmpHash也替換為數組，但是效果不佳；

（4）上述三次嘗試，花了一天一夜時間，無奈之下，筆者決定先用草稿紙將算法設計好再轉換為perl。在草稿紙反復演練，也讓筆者大腦有時間真正的進行考慮，筆者意識到針對復雜樹形結構，判斷條件也十分的復雜，不是一兩個循環+比較就能完成，同時也考慮到了Perl數組的特性，最終形成下面這個算法設計：

循環部分的具體代碼放出如下：

LABELA: while(1) {
    $find_cdp_ip = pop @{$switchlist{$uplinkip}};
    %data = ();
    eval {%data = cisco_top::cisco_cdp_hash(\$find_cdp_ip);};
    if ($@){ 
       die "Error using MethodName method. Error: $@\n"; 
    } 
    data_write(\%data);

    LABELB:foreach my $key2 (keys(%data)) {
    next LABELB if ($data{$key2}->{ip} =~ /$uplinkip/);
    push @{$switchlist{$find_cdp_ip}}, "$data{$key2}->{ip}";
    }

    push @old_array, $uplinkip;
    $uplinkip = $find_cdp_ip;

    LABELC: {if (exists $switchlist{$uplinkip}->[0]) {
        next LABELA;
    }
    $uplinkip = pop @old_array;

    if ( !exists $switchlist{$root_host}->[0] ) { 
         last LABELA; }
    redo LABELC;}
}

算法中，判斷條件后進行循環，采用了LABLE循環控制。

eval{...}if($@){...}涉及到筆者自制模塊中的錯誤捕獲。

時間限制，后期再補充。