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($@){...}涉及到笔者自制模块中的错误捕获。

时间限制，后期再补充。