Perl語言遍歷樹形結(jié)構(gòu)的算法設(shè)計(jì)——利用cisco鄰居發(fā)現(xiàn)協(xié)議遍歷全網(wǎng)絡(luò)的思路

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

最近幾個月，perl的learning和program終于看完了，準(zhǔn)備上手寫代碼。第一個試手的腳本是讀取excel表格，第二個腳本是利用perl讀取核心交換機(jī)的cisco鄰居協(xié)議信息，之后提取協(xié)議文本中的IP地址，遍歷網(wǎng)絡(luò)中所有交換機(jī)并讀取其cdp信息，直至形成網(wǎng)絡(luò)拓?fù)鋱D信息。

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

但是當(dāng)設(shè)計(jì)遍歷全公司網(wǎng)絡(luò)時，碰了釘子。

剛開始考慮將交換機(jī)名稱作為hash的key，IP地址作為value。通過簡單的for循環(huán)遍歷key，來實(shí)現(xiàn)全網(wǎng)絡(luò)的發(fā)現(xiàn)和遍歷（后面有詳細(xì)介紹）。但是因?yàn)閔ash本身的特性，總是會在某一分支的幾臺交換機(jī)間發(fā)生重復(fù)訪問的情況。后來加入數(shù)組變量還是同樣情況?？嗨稼は肓艘惶彀霑r間，在稿紙上反復(fù)的演練設(shè)計(jì)，最后找到了合適的算法（雖然可能運(yùn)行效率不是最高的，但方法是正確的，如大神有更好的方法歡迎推薦?。?。下面進(jìn)入正題：

先來看下網(wǎng)絡(luò)結(jié)構(gòu)：

思科園區(qū)網(wǎng)絡(luò)的推薦網(wǎng)絡(luò)模型，主要分核心層、匯聚層、接入層。而在實(shí)際應(yīng)用中，規(guī)模龐大的園區(qū)網(wǎng)絡(luò)，因?yàn)榉N種條件（資金、環(huán)境等等）制約，存在次級匯聚層、接入層與接入層串聯(lián)等結(jié)構(gòu)出現(xiàn)。

因此，像筆者公司的網(wǎng)絡(luò)，屬于復(fù)雜的樹形結(jié)構(gòu)。

第二，簡單介紹一下算法設(shè)計(jì)過程：

筆者剛開始對于網(wǎng)絡(luò)結(jié)構(gòu)的遍歷算法，想的比較簡單了，

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

后來發(fā)現(xiàn)該方法中單純的使用Hash，總是會訪問到最后一層結(jié)構(gòu)后，會卡在幾個鄰居交換機(jī)之間循環(huán)訪問，無法跳到上一層結(jié)構(gòu)。出現(xiàn)此問題，首先是因?yàn)镠ash本身遍歷key是無序的，加上筆者思路有誤，最終失敗了。還有，筆者在Hash賦值過程中簡單的使用了“=”，后經(jīng)測試驗(yàn)證“=”僅僅將內(nèi)存地址進(jìn)行了相互賦值，實(shí)際上三個Hash是同一個Hash。最后，筆者編制了一個方法，將三個Hash間由相互賦值變?yōu)榱恕皬?fù)制”；

（2）改進(jìn)后，引入了數(shù)組機(jī)制，也就是將readHash簡單替換為了數(shù)組，但是效果不佳；

（3）再次改進(jìn)，將cmpHash也替換為數(shù)組，但是效果不佳；

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

循環(huán)部分的具體代碼放出如下：

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;}
}

算法中，判斷條件后進(jìn)行循環(huán)，采用了LABLE循環(huán)控制。

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

時間限制，后期再補(bǔ)充。