中文模板

Transcription

1 ISSN , CODEN RUXUEW Journal of Software, Vol7, No2, December 2006, pp DOI: 0360/jos72565 Tel/Fax: by Journal of Software All rights reserved +,, (,00080) A Method of Topology Discovery for Switched Ethernet Based on Address Forwarding Tables SUN Yan-Tao +, WU Zhi-Mei, SHI Zhi-Qiang (Multimedia Communication & Network Engineering Research Center, Institute of Software, The Chinese Academy of Sciences, Beijing 00080, China) + Corresponding author: Phn: , Fax: , yantao02@ioscn Sun YT, Wu ZM, Shi ZQ A method of topology discovery for switched Ethernet based on address forwarding tables Journal of Software, 2006,7(2): Abstract: In this paper, the connections reasoning technique (CRT) based on the predication logic is proposed to infer the connections between network nodes This technique interprets the address forwarding tables (AFTs) as a set of predicate formulas and translates the topology discovery into a mathematic problem of logic reasoning, so that the topology discovery can be studied by resorting to mathematic tools An algorithm for topology discovery based on CRT is proposed in this paper Compared with current discovery algorithms, this method excels in: ) Applying the redundancies in AFTs more effectively, so that the whole topology can be built up by just small part of AFTs; 2) Naturally resolving the problem of topology discovery for multi-subnet switched domain without any extensions Furthermore, a method with little cost is proposed to discover the dynamic topology in this paper This algorithm is successfully applied to the network management system for CBISN (Community Broadband Integrated Services Network) Key words: network management; topology discovery; switched Ethernets; address forwarding table; topology : inference (connections reasoning technique),,, :(), ;(2), : ; ; ; Supported by the National Natural Science Foundation of China under Grant Nos , ( ); the Project of the Beijing Committee of Science and Technology of China under Grant NoH ( ) Received ; Accepted

2 2566 Journal of Software Vol7, No2, December 2006 : TP393 : A (switched Ethernet) 5, (Ethernet switch),, hub,,,, 2 ( ), ( ) [2,3] 3, 3 IETF 2000 MIB(management information base) [4], MIB, 2 ( ) Myung-Hee Son [2] STP (spanning tree protocol),, ;,, [0], Richard Black [3],,,, (, ),, ;, Breitbart AFT(address forwarding table, AFT) [5,6] :,, [9], [9], [5],2003,Bejerano, [] (skeleton path), (path constraint),,,,,,, Breitbart [5,6] ; [9] Ping, SNMP UDP,,,,,

3 : 2567 Lowekamp SIGCOMM 200 [7] : () ( ):, ( ) S i x, x [7] (MKR ),MKR 3,,,,, :(), ;(2), 2 2, :,,, MAC :(port,mac),,mac p, p p MAC,, [], :, 3 :,, SNMP ;,, ; (hub), MAC,,, :,,,,,, :, (administrative domain),, STP(spanning tree protocol) [],, IP IP IP 22, :() (3 ), ;(2) 2 3, (2) G=(D,E) D ( ) E,S,H,D=S+HPort(D,p) D p, Dp E={ Ax,By A,B D Ax By }

4 2568 Journal of Software Vol7, No2, December 2006 A (p,d) (A,p,D) (A,p,D) AFT(A,p) Port(A,p) Link(A,x,B,y) A x B y, AxBy, A, B, x, y, (A,p,D) A p D x, Link(A,p,D,x) FS (formulas set) A 2 B C 2 D (a) (a) Topology AFT (A, ) = {B, D} AFT (B, 2) = {D} AFT (A, 2) = {C} AFT (C, ) = {A, B, D} AFT (B, ) = {A, C} AFT (D, ) = {A, B, C} (b) AFT FS = {ABx, ADx, A2Cx, BAx, BCx, B2Dx, CAx, CBx, CDx, DAx, DBx, DCx} (c) Formulas Set set Fig AFTs and formulas set,, CRT(connections reasoning technique), CRT BRR(basic reasoning rule) () (symmetry rule):link(a,i,b,j) Link(B,j,A,i) Port(A,i)Port(B,j) Port(B,j) Port(A,i) (2) I (transition rule I):Link(A,i,C,u) Link(C,v,B,j) (u v) Link(A,i,B,j) :Link(A,i,C,u),A C P :Ai,,CuLink(C,v,B,j),C B P 2 :Cv,,Bju v, P P 2,A B :Ai,,Cu,Cv,,Bj, Link(A,i,B,j) (3) II (transition rule II):Link(A,i,C,u) Link(C,v,B,j) xlink(a,i,b,x) ylink(a,y,b,j),u v 2 4 ( ) u C v u C u C D p q i A B j j B x i A i A y j B u i j C A B : (a) (b) (c) (d) Fig2 a) u v, I,Link(A,i,B,j) u=v, 3 : The 4 cases of transition rule II 2 II 4 b) A C B, Ai,,Bx,Bj,,Cu,x j Link(A,i,B,x); c) B C A, Bj,,Ay,Ai,,Cu,y j Link(A,y,B,j); d) A C B, B C A, D, AiDp DqBj p q, I, Link(A,i,B,j)

5 : (4) (exclusion rule):link(a,i,b,j) ( x y(link(a,x,b,y) (x i y j))) :, : x y((x i y j) Link(A,x,B,y)), A,B Ax,,By Link(A,i,B,j), A,B Ai,,Bj x i y j,,,, (5) (inference of exclusion rule):link(a,i,b,x) Link(A,y,B,j) Link(A,i,B,j) ()~ (5) CRT (BRR) (hypothesis for the completeness of BRRs):BRR, FS,, FS, BRR [7] MKR(minimum knowledge requirement) ( )MKR : Au Bv, 3 : a) B AFT(A,u) and A AFT(B,v); b) B AFT(A,u) and k u: AFT(B,v) AFT(A,k) 0; c) i,j,i j:aft(a,u) AFT(B,i) 0 AFT(A,u) AFT(B,j) 0 k u: AFT(B,v) AFT(A,k) 0 BRR, : 3, Au Bv (x ): a) {AuBx,BvAx} AuBv; b) {AuBx,BvCx,AkCx} AuBv (u k); c) {AuCx,BiCx,AuDx,BjDx,BvEx,AkEx} AuBv (i j, u k) : a) b): BvCx AkCx AxBv AkBx ( II) AuBx AuBv ( ) c): AuCx BiCx AuBx AxBi ( II) AuDx BjDx AuBx AxBj ( II) AuBx ( ) BvEx AkEx BvAx BxAk ( II) AuBv ( ) I, MKR,, 3 [7]MKR MKR ( 2 ), {AuC,C2Bv} AuBv I, A,B C ( 3 ), A,B,,MKR, :() MKR BRR,BRR MKR ;(2) BRR BRR,

6 2570 Journal of Software Vol7, No2, December 2006 D A 2 3 B ADx A2Ex A3Bx BCx CDx C2Ex C E 2 Proof: ADx CDx ACx AxC A2Ex C2Ex A2Cx AxC2 AC2 A2C BCx ABx A2Bx AxB A3Bx A3B 23 Fig3 Infering a connection based on multiple nodes AFT 3 BRR () AFTable :AFTable[M][N],M,N AFTable[i][j]=k(k>0) (i,k,j)aftable[i][j]=0 i j AFTable[i][i]=,i=,,M AFTable,AFTable 0 Table The AFTable of a topology AFTable A B C D E F A 2 B C 2 D E F Connection :,Connection(A,B)={AiBj} Connection(C,D)={CiDx CxDj} UndeterminedList( ): Connection, Connection (2), AFTable;,, 4, AxBy : (i) :{AuCx,CyBv} R,{AuDx,DyBv} R2,, {AuJx,JyBv} Rn; (ii) :AxBy R R2 Rn Connection(A,B) (iii) Connection(A,B) AxBy, Connection(A,B) AxBy Connection ( AxBy, Connection AxBy ), AxCy BxCy (iv) AxBy,Connection(A,B) Connection(A,B) Connection, 3, Connection(A,C) : (i) A,C :Connection(A,B) Connection(B,C) RConnection(B,C) UndeterminedList, AFTable ;

7 : 257 (ii) Connection(A,C):R Connection(A,C) R; (iii) AxCy, Connection(A,C) ; (iv) Connection(A,C), Connection(A,C) (3), AFTable, AFT[i][j]=0, i j, AFTable,,, ( 4, E F ) 24, [6] :,, [6] FindLeafConnections, :,,, : () ;,, A B, A B,B A, L= M N, O(L) : BuildTree(S) /* S */ S ( dev), () dev, dev S (2) dev A,A S dev S A, dev S (3) BuildTree(dev);, hub, 25, hub VLAN, [6], 25 [5],, ( ), [6], 4,,, 4, A,D E N,B,C F N 2 AFT(A,2) AFT(D,) =, AFT(A,2) AFT(D,)=N,,A D Bejerano, [],,

8 2572 Journal of Software Vol7, No2, December 2006 A 2 B 2 C 2 D 3 E F AFT (A, ) ={E} AFT (A, 2) ={D} AFT (B, ) ={A, E} AFT (B, 2) ={C, D} AFT (B, 3) ={F} AFT (C, ) ={A, B, E, F} AFT (C, 2) ={D} AFT (D, ) ={A, E} AFT (E, ) ={A, D} AFT (F, ) ={B, C} 252 Fig4 Multi-Subnet switched domain 4, :() ;(2) ;(3) ;(4) 4 ( ), Ping SNMP Trap LinkUp LinkDown [4] MIB ifadminstatus ifoperstatus [5],,,,,F A,B A B D, R, F R,D D R p p S, F S,D S D D :,, :,,,, A i B j (A B ),F A,B =(k,b), B, A k# B, : B A, A,,, B ; B A, A C B F C,B,,, X,B X, X, B,, CRT, :(), ;(2),,,

9 : Table 2 Comparisons of algorithms 2 Completeness of AFTs Multi-Subnet topology Dynamic topology CRT No requirement Support Support Direct connection [6] Requirement No support No support MKR [7] No requirement Partly support Partly support Skeleton path [] Requirement Support No support 3 NS2, 3 :, (DCOUNT) (2 ) (5 ) (7 ), 5s, On/OFF (EXPOO_Traffic) [8] UDP 20%,, 20s,80s 300s Pentium IV 24GHz 256M, XP 3 4,DCOUNT/SCOUNT ;Aging Time ; Item Losts/Ratio ; Node Losts ; Before CR After CR Discovery Time, (CR time) (DC time)4 Aging Time=300s DCOUNT/SCOUNT 500/42 000/ /67 Table 3 The statistic of simulations 3 Aging time (s) Item losts/ratio (%) Node losts Discovery time Before CR After CR Before CR After CR CR time (s) DC time (s) /762 54/ /702 4/ < /608 0/ < / / /87 84/ < /746 0/ /92 336/ / / /84 0/ Table 4 Comparison of simulated results 4 DCOUNT/ MKR (after CR) CRT (after CR) Before CR item losts/ratio (%) SCOUNT Item losts CR time (s) Item losts CR time (s) 200/7 27/ < 500/ / < 000/ / , : (),, 60% (2) MKR, 4 :, 3 Before CR After CR :,, CRT

10 * 8 # * 8 # 2574 Journal of Software Vol7, No2, December 2006 (3) Aging Time=300s, 60%~80%, 32 (CBISNMS), (CBISN) IP SW200/200/00 /, 00, 500, IP, CBISN 5 CBISNMS CBISN WAN fibre Satellite Video DB VoD server Video channel server 000M/00M 000M Live video server SW200 aa Accounting server Network management server 000M/00M 000M Satellite receiving server Antenna Support multicast, QoS, IGMP, SNMP 0/00M 00M SW200 00M 00M SW200 00M SW00 SW00 SW00 SW00 Home gateway 0/00M Home gateway Home gateway Home gateway IP phone PC D-TV Analog TV Fig5 D-TV Analog TV PC IP phone The logical topology of CBISN 5 CBISN CBISNMS /, 6 Linux, NM-Services Fig6 ODBC NM- Database RPC ODBC GUI The architecture of CBISNMS 6 CBISNMS (NM-services) (NM-database), PostgreSQL73 (GUI) Windows, VC++ 60 :() (NodeSearcher):, ;(2) MIB (MIBCollector): ;(3) (TopoCalculator): (TopoViewer) CBISNMS,, ( hub), 7, :92689 ;VirtualHUB406 hub ;

11 : 2575, ( hub) , ( ) CBISN,7 8 CBISNMS VirtualHUB Fig7 Bridge-Connection view Fig8 Bridge-Port view 8 4,,,,,,,

12 2576 Journal of Software Vol7, No2, December 2006, VLAN, hub, References: [] Tanenbaum AS Computer Networks 3rd ed, Beijing: Tsinghua University Press, (in Chinese) [2] Donnet B, Raoult P, Friedman T, Crovella M Efficient algorithms for large-scale topology discovery In: Eager DL, Williamson CL, Borst SC, Lui JCS, eds Proc of the ACM SIGMETRICS 2005 New York: ACM Press, [3] Govindan R, Tangmunarunkit H Heuristics for Internet map discovery In: Sidi M, Sengupta B, eds Proc of the IEEE INFOCOM 2000 New York: IEEE Press, [4] Bierman A, Jones K Physical topology MIB Internet RFC-2922, 2000 [5] Breitbart Y, Garofalakis M, Martin C, Rastogi R, Seshadri S, Silberschatz A Topology discovery in heterogeneous IP networks In: Sidi M, Sengupta B, eds Proc of the INFOCOM 2000 New York: IEEE Press, [6] Breitbart Y, Garofalakis M, Jai B, Martin C, Rastogi R, Silberschatz A Topology discovery in heterogeneous IP networks: The NetInventory system IEEE/ACM Trans on Networking, 2004,2(3):40 44 [7] Lowekamp B, O Hallaron DR, Gross TR Topology discovery for large Ethernet networks In: Govindan R, ed Proc of the ACM SIGCOMM 200 New York: ACM Press, [8] Fall K, Varadhan K The ns manual [9] Zheng H, Zhang GQ An algorithm for physical network topology discovery Journal of Computer Research and Development, 2002,39(3): (in Chinese with English abstract) [0] Li T, Shi ZQ, Wu ZM Discovering layer-2 topology in bridged local area networks Computer Science, 2003,30(2):6 8,5 (in Chinese with English abstract) [] Bejerano Y, Breitbart Y, Garofalakis M, Rastogi R Physical topology discovery for large multi-subnet networks In: Bauer F, Roberts J, Shroff N, eds Proc of the IEEE INFOCOM 2003 New York: IEEE Press, [2] Son MH, Joo BS, Kim BC, Lee JY, Physical topology discovery for metro ethernet networks ETRI Journal, 2005,27(4): [3] Black R, Donnelly A, Fournet C Ethernet topology discovery without network assistance In: La Porta T, Ramjee R, Koenig H, Effelsberg W, eds Proc of the 2th IEEE Int l Conf on Network Protocols (ICNP 2004) Los Alamitos: IEEE Computer Society, [4] Case J, Fedor M, Schoffstall M, Davin J A simple network management protocol (SNMP) Internet RFC-57, 990 [5] Case J, McCloghrie K, Rose M, Waldbusser S SNMPv2 Internet RFC-905, 996 : [] Tanenbaum AS 3, :, [9],,2002,39(3): [0],, 2,2003,30(2):6 8,5 (975),,,,,, (970),,,CCF,,,, (942 ),,,,CCF,,