摘 要 本文分析了現(xiàn)有的以太網(wǎng)鏈路層拓?fù)浒l(fā)現(xiàn)算法，在此基礎(chǔ)上提出了虛擬交換機拓?fù)浒l(fā)現(xiàn)改進算法，給出了算法的具體實現(xiàn)方法和實現(xiàn)。使得原有算法的應(yīng)用范圍更廣，適應(yīng)性更強。改進后的算法可以發(fā)現(xiàn)網(wǎng)絡(luò)中原算法無法發(fā)現(xiàn)的設(shè)備。

　　1、引言

　　隨著計算機性能的提高及通信量的巨增，傳統(tǒng)局域網(wǎng)已經(jīng)愈來愈超出了自身的負(fù)荷，交換式以太網(wǎng)技術(shù)應(yīng)運而生，大大提高了局域網(wǎng)的性能。與過去基于網(wǎng)橋，集線器，路由器的共享媒體的局域網(wǎng)拓?fù)浣Y(jié)構(gòu)相比，網(wǎng)絡(luò)交換機能顯著的增加帶寬。交換技術(shù)的加入，就可以建立地理位置相對分散的網(wǎng)絡(luò)，使局域網(wǎng)交換機的每個端口可平行、安全、同時的互相傳輸信息，而且使局域網(wǎng)可以高度擴充。局域網(wǎng)交換機根據(jù)使用的網(wǎng)絡(luò)技術(shù)可分為：以太網(wǎng)交換機、令牌環(huán)交換機、FDDI 交換機、ATM 交換機、快速以太網(wǎng)交換機。由于以太網(wǎng)的簡單與易用性，所以目前大部分的LAN 均采用了以太網(wǎng)交換機與快速以太網(wǎng)交換機作為自己的網(wǎng)絡(luò)交換設(shè)備。本文中的鏈路層拓?fù)浒l(fā)現(xiàn)正是針對以太網(wǎng)中的二層設(shè)備。

　　目前很多算法都是針對純可管理得交換機網(wǎng)絡(luò)設(shè)計的，但在實際應(yīng)用中，經(jīng)常會出現(xiàn)交換機網(wǎng)絡(luò)中夾雜著HUB 或不可管理的啞交換機。這種類型設(shè)備的存在使網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的準(zhǔn)確性大打折扣，我們把這類型的設(shè)備定義為虛擬交換機。因此提出一種對虛擬交換機的拓?fù)浒l(fā)現(xiàn)算法能使得原有算法的應(yīng)用范圍更廣，適應(yīng)性更強。

　　2、現(xiàn)有鏈路層拓?fù)浒l(fā)現(xiàn)算法

　　從交換機工作原理上我們能夠發(fā)現(xiàn)，交換機并未提供一種有效、直接的方法確定其直接連接的設(shè)備。對于一個異構(gòu)的網(wǎng)絡(luò)我們可行的方法就是利用SNMP 中的MIBⅡ bridge組的信息（各個廠家都實現(xiàn)），得到交換機的地址轉(zhuǎn)發(fā)表，并分析其特性，利用提出得簡單連接關(guān)系確定直接連接關(guān)系，來確定物理網(wǎng)路的拓?fù)潢P(guān)系。

　　2．1 現(xiàn)有算法描述

　　以給定的子網(wǎng)號和掩碼地址作為輸入，以交換機對象鏈表, 網(wǎng)段對象鏈表，主機對象鏈表，打印機對象鏈表和2 層連接對象鏈表為算法的輸出。給定子網(wǎng)的拓?fù)湫畔⑷堪谏鲜龅逆湵碇小?/P>

　　1）算法的部分首先根據(jù)子網(wǎng)地址和子網(wǎng)掩碼計算出子網(wǎng)的范圍，然后掃描該范圍內(nèi)的所有IP 地址，并判斷設(shè)備的類型以及其它信息。該過程用偽代碼表示如下：

　　for （子網(wǎng)范圍內(nèi)的每一個地址 ipAddr）

　　｛

　　if（存在某個設(shè)備的IP 地址為ipAddr）

　?。?/P>

　　deviceType = getTypeofDevice（ipAddr）；

　　if （deviceType == switch）生成交換機對象，添加到交換機對象鏈表中；

　　else if （deviceType == printer）生成打印機對象，添加到打印機對象鏈表中；

　　else

　　生成主機對象，添加到主機對象鏈表中；

　　｝

　?。?/P>

　　2) 找到子網(wǎng)內(nèi)所有主機的MAC 地址。

　　3) 遍歷子網(wǎng)中所有的交換機，交換機的FDB 表。

　　4）基于每個交換機的FDB 表，利用[4]所描述的方法計算交換機之間的連接關(guān)系。

　　5）重新調(diào)整子網(wǎng)內(nèi)的所有網(wǎng)段。

　　6）把網(wǎng)段和交換機的連接關(guān)系構(gòu)造成對象，添加到2 層連接對象鏈表中。

　　在算法的第（2）步，之所以要找到物理地址是因為交換機FDB 中的地址是MAC 地址，在為主機劃分網(wǎng)段時，要用到這些MAC 地址。找到主機MAC 地址的方法有兩種。種是利用主機的MIBII 中的inferfaces 組中的ifPhysAddress 對象，另一種是利用與該子網(wǎng)相連的路由器中的ipNetToMediaTable 來找到該子網(wǎng)內(nèi)的所有主機的MAC 地址。

　　2．2 算法所存在的問題

　　算法的假設(shè)條件是整個網(wǎng)絡(luò)都是可管理的交換機，即可以通過 SNMP 協(xié)議取得相應(yīng)信息。并且所有交換機是連接在一棵樹上，當(dāng)網(wǎng)絡(luò)中存在HUB 和啞交換機時，因為它們沒有MIB 表或取不到MIB 信息，因此有許多設(shè)備就不能自動被發(fā)現(xiàn)，而只能通過手動方式添加。在中提到虛擬交換機的概念及簡單的解決方法，但并沒有給出具體的實現(xiàn)算法。

　　3、虛擬交換機拓?fù)浒l(fā)現(xiàn)算法描述

　　虛擬交換機拓?fù)浒l(fā)現(xiàn)算法主要目的就是要檢測哪些交換機是直接連接到虛擬交換設(shè)備以及哪些交換機又是這些設(shè)備的下連設(shè)備。為了實現(xiàn)這個目標(biāo)，根據(jù)中簡單連接原理，能得到每個設(shè)備和它們所有的根設(shè)備之間的連接關(guān)系集合。如果某一根設(shè)備跟它的集合中所有設(shè)備都沒有直接連接關(guān)系，則該設(shè)備下聯(lián)可能就是一個虛擬交換設(shè)備。這樣就確定了虛擬交換機的位置，下來是要找出與虛擬交換設(shè)備直接連接的下級設(shè)備。如果某一個或多個設(shè)備是其它所有設(shè)備到虛擬交換機所連接的根設(shè)備都必須經(jīng)過的節(jié)點（集合的交集），則這種設(shè)備一定是跟虛擬交換機直接連接的下級設(shè)備。

　　發(fā)現(xiàn)程序遍歷網(wǎng)絡(luò)中的每個交換機，交換機中的 FDB 表，然后構(gòu)造兩張表：間接連接表和直接連接表。其中，間接連接表是一張二維表，每個表項都是一個struct，如下所示：

　　typedef struct _SimpleConnectRecord{

　　SInterface *pSInterface;

　　struct _SimpleConnectRecord *portDown; //point to the next simple connect record

　　struct _SimpleConnectRecord *portRight; //point to the SInterface of switch simply connected

　　} SimpleConnectRecord

　　表的每一行以交換機的某一個接口 a 開始，在接口a 后面的同行的接口是以a 為根，與a 有簡單連接關(guān)系的所有接口。表的列包含了整個表中出現(xiàn)的所有的接口，并且兩兩互不相同，可以作為表的索引。

　　第二張表是直接連接表，直接連接表是一張一維鏈表。鏈表中的每個元素是下面的結(jié)構(gòu)體：

　　typedef struct _DirectConnectRecord{

　　SInterface *pSInterfaceSource;

　　SInterface *pSinterfaceDestin;

　　struct _DirectConnectRecord *pNext;

　　} DirectConnectRecord;

　　拓?fù)浒l(fā)現(xiàn)程序通過對間接連接表的計算得到直接連接表，在根據(jù)直接連接表生成鏈路層連接對象。存儲在數(shù)據(jù)庫中。

　　3．1 算法的實現(xiàn)

　　本算法采用 java 語言實現(xiàn)主要代碼如下：

　　Vector portRight[]=new Vector[1024];

　　Vector portDown[]=new Vector[1024];

　　Vector counter[]=new Vector[1024];

　　int index=0;

　　public void getDirectConnected(String host){

　　createSimpleConnected（String host）;//利用Vector 構(gòu)建一個可變大小的二維表

　　//對簡單連接表進行識別得到直接連接關(guān)系

　　ListIterator it = portDown[index].listIterator();

　　int i = 0; //表示簡單連接表的行元素個數(shù)

　　int n=0;

　　counter[index] = new Vector();

　　counter[index].addElement(new Integer(i));

　　while (it.hasNext()) {//遍歷簡單連接表

　　i = Integer.parseInt(counter[index].get(0).toString());

　　int portSize = ( (Vector) portDown[index].elementAt(i)).size();

　　String nextIP= ( (Vector) portDown[index].elementAt(i)).elementAt(0).toString();

　　if (portSize == 2) {//如果一個端口上僅僅連接一個設(shè)備，則與該設(shè)備是直接連接

　　┇

　　i++;

　　index++;

　　getDirectConnected(nextIP);//以該設(shè)備為根得到其下級設(shè)備的連接關(guān)系

　　index--;

　　break;

　　}

　　else if (portSize > 2) {//連接多個設(shè)備的話，則通過算法得到直接連接關(guān)系

　　┇

　　i++;

　　n++;

　　}

　　}

　　if (n == portSize) { //如果所有的簡單連接設(shè)備的上連端口與其他設(shè)備之間均沒有簡單連接關(guān)系，則所有設(shè)備連接在

　　HUB 上

　　//判斷哪些設(shè)備是與HUB 簡單連接的設(shè)備

　　getHUBConnected()；

　　//遍歷所有設(shè)備得到被各個設(shè)備包含的數(shù)

　　String tmp=getMax();

　　//包含數(shù)為的設(shè)備，該設(shè)備即是與HUB 直接連接的設(shè)備

　　index++;

　　getDirectConnected(nextIP);//以該設(shè)備為根得到其下級設(shè)備的連接關(guān)系

　　index--;

　　}

　　4、結(jié)束語

　　利用本文提出的虛擬交換機拓?fù)渌惴?，在實際運行中能發(fā)現(xiàn)啞交換設(shè)備和共享設(shè)備，使原有的拓?fù)浒l(fā)現(xiàn)算法準(zhǔn)確性更高，適應(yīng)性更強。