US00702741 lBl
`
`(12)
`
`United States Patent
`Pulsipher et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,027,411 B1
`Apr. 11, 2006
`
`(54) METHOD AND SYSTEM FOR IDENTIFYING
`AND PROCESSING CHANGES TO A
`NETWORK TOPOLOGY
`
`(75) Inventors: Eric A Pulsipher; Ft COIIIIIS, CO (US);
`Joseph R Hunt, Loveland, CO (US)
`
`(73) Assignee: Hewlett-Packard Development
`Company, L.P., Houston, TX (US)
`
`_
`( * ) Not1ce:
`
`_
`_
`_
`_
`Subject to any d1scla1mer, the term of this
`patent is extended or adjusted under 35
`U_S_C_ 154(1)) by 961 days,
`
`(21) Appl. N0.: 09/703,942
`
`(22) Filed:
`
`Oct. 31, 2000
`
`(51) Int CL
`(200601)
`H04L 12/28
`(52) us. Cl. .................... .. 370/254; 370/403; 370/402;
`370/351; 714/717; 709/223; 709 02 4
`(58) Field of Classi?cation Search .............. .. 370/229
`370/216 217 221 225 254 255 256 257’
`370/258’ 410’ 403’ 402’ 350’ 400’ 252’ 351?
`709/224 ’223 538 ’714/’717
`320/8555;
`’
`’
`’
`’
`’
`715/735’
`See application ?le for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,644,532 A *
`5,023,873 A 4
`5,727,157 A *
`5,729,685 A *
`5,732,086 A *
`5,740,346 A *
`5,886,643 A *
`6,l08,702 A
`
`2/1987 George et a1. ............ .. 370/255
`6/1991 Stevenson et a1‘
`3/1998 Orr et a1. .................. .. 709/224
`3/1998 Chatwani er a1,
`709/224
`3/1998 Liang et a1.
`370/410
`4/1998 WICkI et a1. ................ .. 714/22
`3/1999 Dlebboll et a1~
`8/2000 Wood ....................... .. 709/224
`
`6,160,796 A * 12/2000 Zou . . . . . . . . . . . .
`
`. . . .. 370/257
`
`707/203
`6,295,541 Bl* 9/2001 Bodnar et a1. ..
`6,347,336 B1 *
`2/2002 Song et a1. ............... .. 709/223
`
`6/2002 Wood ....................... .. 709/223
`6,405,248 B1 *
`6,636,981 B1 * 10/2003 Barnett et a1. ............ .. 714/4
`6,791,948 B1 *
`9/2004 Desnoyers et a1.
`370/254
`6,885,644 B1 *
`4/2005 Knop et a1. ............... .. 370/254
`FOREIGN PATENT DOCUMENTS
`
`EP
`JP
`W0
`
`830047 A2
`2000'76209
`WO98/44400
`
`3/1998
`3/2000
`10/1998
`
`* cited by examiner
`
`Primary Examineriwellington Chin
`Assistant Examiner4Chuong Ho
`
`(57)
`
`ABSTRACT
`
`_
`_
`A method and system are d1sclosed for mapp1ng the topol
`ogy of a network having interconnected nodes by identifying
`changes in the network and updating a stored network
`topology based on the Changes- The nodal Connections are
`represented by data tuples that store information such as a
`hos‘ identi?er’ a 901mm“ interface’ and a PO“ speci?eation
`for each connectlon. A topology database stores an ex1st1ng
`topology of a network. A topology converter accesses the
`topology database and converts the existing topology into a
`11st of current tuples. A connectlon calculator calculates
`tuples to represent connepnons 1n the new tOPOIPgy' he
`topology converter recelves the new tuples, 1dent1?es
`changes to the topology, and updates the topology database
`using the new tuples. The topology converter identi?es
`duplicate tuples that appear in both the new tuples and the
`existing tuples and marks the duplicate tuples to re?ect that
`_
`no change has occurred to these connectlons. The topology
`Converter attempts to resolve swapped POI~t COIIdIIIOIIS and
`searches for new singly-heard and multi-heard host link
`tuples in the list of existing tuples. The topology converter
`also Searches for new Con?ict
`tuples in the existing
`tuples. The topology converter updates the topology data
`base With the new topology~
`
`18 Claims, 26 Drawing Sheets
`
`PROTOCOLBASEDDATA
`GA'I‘HERINGTI-IROUGH
`POLLS
`
`35o
`
`TOPOLOOKUPS
`
`USER EDI‘TS
`
`ExTERNALAPPucAnoN
`INPUT
`
`("LOOK FOR‘
`REQUESTS?)
`
`.,
`("LOdK FOR;\\(
`READY?)
`CREATE’LOOKUP'AND
`UPDATE "NEIGHBOR ISIATA"
`8.061511%
`
`CREATE, rooxur. AND
`UPDATEREDUCEQ
`"NEIGHBORDATA
`
`340
`
`~~
`
`CONNECTION
`CALCULATOR
`
`TOPOLOGY
`CONVERTER
`
`320
`
`310
`
`NElGI-[BOR DATA
`(QUASl-PERMANEN'I‘)
`
`"NEIGHBOR DATA"
`LOOKUPS
`
`REDUCED TOPOLOGY
`RELATIONSHIPS
`USER ARBITRATION
`(TRANSIENT)
`REQUESTS
`
`LOOKUPS AT REDUCED
`RELATIONSHIPS
`
`ServiceNow, Inc's Exhibit 1001
`
`001
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 1 or 26
`
`US 7,027,411 B1
`
`ServiceNow, Inc's Exhibit 1001
`
`002
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 2 or 26
`
`US 7,027,411 B1
`
`(200
`
`ServiceNow, Inc's Exhibit 1001
`
`003
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 3 0f 26
`
`US 7,027,411 B1
`
`K301
`K121
`
`A110
`
`[131
`
`oocioco l
`
`I
`
`140
`
`FIG. 3
`
`ServiceNow, Inc's Exhibit 1001
`
`004
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 4 or 26
`
`US 7,027,411 B1
`
`K121
`//
`
`[301
`
`110
`r124
`_
`131
`//// ——7uu <?~>
`
`/123
`////
`
`:5: “4
`
`‘40
`
`133
`
`(It,
`
`FIG. 4
`
`ServiceNow, Inc's Exhibit 1001
`
`005
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 5 0f 26
`
`US 7,027,411 B1
`
`FIG. 5
`
`ServiceNow, Inc's Exhibit 1001
`
`006
`
`

`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 6 0f 26
`
`US 7,027,411 B1
`
`FIG. 6
`
`K151
`
`161
`
`171
`
`El
`
`162
`
`A 110
`
`163
`
`172
`
`060005
`
`12%
`
`121
`
`A110
`
`165
`
`173
`
`DODDDO
`
`166
`
`152
`
`ServiceNow, Inc's Exhibit 1001
`
`007
`
`

`
`S.U
`
`A
`
`:1
`
`1B1
`
`828m385882.8mm3.5;
`
`
`pm5:25.ozammss
`.O2<55amm<m-8uo§a
`
`
`
`mnsvaogM._§..5mo$§mz..
`
`zoabmzzouM%.Em>zoomoa::S<oasa»oo.§8
`
`
`
`2«xxx4/11:1:11xx.u§.$m,5ommWQ8good
`
`
`,.€E<mmmI:1.I1zI1/._.ZOn*
`amazmmzpommmmzgzouSE
`
`S,,:95~,§E2mz__E295
`
`ox__<e<amommQmz__9,2,5v_o3.E<mmu
`
`omwaammm+<m.5,,,
`
`
`Sm.=:mzo:<._mmE828eczemaUamopoma29308
`
`zo:$E$2MamaA1.5.wEMazamzébwamaomamam.:mmzoE./Emu
`
`
`<55mommofiz
`
`@zmz<2mm&m<:9
`
`em
`
`mbomamma
`
`
`
`zo:.<u:&<ézmmexm
`
`5%
`
`O08
`
`ServiceNow, Inc's Exhibit 1001
`
`ServiceNow, Inc's Exhibit 1001
`
`008
`
`
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 8 0f 26
`
`US 7,027,411 B1
`
`908
`906
`904
`902
`‘2
`T’
`I’
`I"
`DATA GATHERING ,_ TUPLE BUILDING+TUPLE REDUCTION, TOPOLOGY
`PHASE
`PHASE
`PHASE
`UPDATING PHASE
`
`FIG. 8
`
`910
`I)
`RECEIVE START
`SIGNAL
`912
`l
`K‘
`LOOK UP EXISTING
`DEVICES INTOPOLOGY
`DATABASE
`914
`l
`I’
`QUERY NODES
`
`922
`‘1
`FIRST WEEDING
`PHASE
`
`924
`I’
`‘i
`INFRASTRUCTURE
`BUILDING
`PHASE
`926
`,
`\’
`SECOND WEEDING
`PHASE
`
`1,
`
`91/16
`
`CREATE TUPLES
`
`v
`
`9228
`
`NOISE REDUCTION
`PHASE
`
`918
`l
`I)
`STORE TUPLESIN
`NEIGHBOR DATABASE
`
`920
`1
`I’
`AnDIgIlgIgfIFDATA
`AS REQUESTED
`FIG. 9
`
`930
`‘
`\’
`LOOK-FOR
`PHASE
`
`932
`l
`f‘
`CONSOLHJATION
`PHASE
`FIG. 10
`
`ServiceNow, Inc's Exhibit 1001
`
`009
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 9 0f 26
`
`US 7,027,411 B1
`
`402
`
`FIG. 1 1
`
`418
`6
`TUPLE 1s A CONN
`TO CONNLINK
`
`0
`CONN
`ONLY HEARS THIS N
`HOST ON GROUP 1
`
`HOsT HEARD
`SINGLY BY ANY
`UFHER
`CONN
`f)
`-
`
`410 A
`TUPLEISASINGLY-
`HEARD CONFLICT
`LINK
`
`412
`K
`TUPLE ISA SHHL
`
`416
`\’
`v
`TUPLEISAMHHL
`
`‘.54
`MOVE TUPLES FOR
`THIS HOST T0 EHL
`+
`
`‘
`
`‘
`
`ServiceNow, Inc's Exhibit 1001
`
`010
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 10 0f 26
`
`US 7,027,411 B1
`
`T0 BLOCK
`430 OF FIG.l2b
`
`FOR EACH
`SHI-[L TUPLE
`
`FOR
`EACH TUPLE
`IN EHL
`
`CONN TO CONN
`LINK TUPLE FOR
`EHL-CONN TO SIIHL
`
`COqNN
`
`428
`
`UPDATE TUPLE
`IF NOT COMPLETE
`
`CREATE EHL CONN TO SHHLCONN
`TUPLE IN CONN TO CONN LINK
`
`L
`
`FIG. 12a
`
`ServiceNow, Inc's Exhibit 1001
`
`011
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 11 or 26
`
`US 7,027,411 B1
`
`FROM BLOCK 420
`OF FIG. 12a
`
`FOR EACH
`CONNECTOR IN
`TU PLES
`(CONNl)
`
`DONE
`
`FIG. 1 2b
`
`TO BLOCK 444
`OF FIG. 12c
`
`FOR
`EACH OTHER
`CONNECTOR IN
`CONN-TO-CONN
`TUPLES
`(CONN2)
`
`‘ DONE
`
`YES
`
`CONNl TO
`CONN2
`EXISTS IN
`
`TUI;LES
`
`CONN2
`HEARS CONN3
`ON UNIQUE
`POVRT
`
`EACH CONN2 TO
`OTHER CONNECTO
`
`CREATE CONNl TO CONNZ
`TUPLE IN CONN ‘PO CONN
`LINKS
`
`I
`
`ServiceNow, Inc's Exhibit 1001
`
`012
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 12 or 26
`
`US 7,027,411 B1
`
`FROM BLOCK 430 OF FIG. 12b
`
`FOR EACH
`CONN TO CONN LINKS
`TUPLE
`
`DONE
`
`TO BLOCK 456
`OF FIG. 12d
`
`INCOMPLETE
`GROUP! PORT
`DATA FOR
`
`LOOK FOR DIFFERENT TUPLE
`INVOLVING CONNl IN
`EHL ON
`DIFFERENT GROUP/PORT
`
`FIG- 12C
`
`CONN2 ALSO
`HEARS
`HO7ST
`
`FILL IN MISSING
`GROUP/PORT FOR
`CONNZ
`
`ServiceNow, Inc's Exhibit 1001
`
`013
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 13 0f 26
`
`US 7,027,411 B1
`
`FROM BLOCK 444 OF FIG. 12c
`
`FIG. 12d
`
`DONE
`
`FOR EACH
`CONN TO CONN LINKS
`TUPLE
`
`CONSIDER CONNI
`AND CONN2
`OF THIS TUPLE
`
`NO
`
`TEST CONN
`HEARS CONNl AND
`CONN2 ON
`DIFFERENT
`- PORTS
`
`MOVE THIS TUPLE
`'DO EXTRA CONN
`LINKS
`
`ServiceNow, Inc's Exhibit 1001
`
`014
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 14 or 26
`
`US 7,027,411 B1
`
`FOR EACH
`SCL
`TUPLE (SEARCH TUPLE)
`
`)
`\
`CONSDER CONNl AND HOSTI 0F SEARCH TUPLE
`J
`
`470
`
`FOR EACH
`EHL
`TUPLE CONTAINING
`HOSTl
`
`DONE
`
`CONSIDER CONN2 OF TUPLE
`
`TUPLE IN CONN
`TO CONN LINKS FOR
`CONN2 AND CONNl
`
`FIG. 13
`
`CONN2 TO HOSTl
`TUPLE7IN EHL
`
`GROUP/PORT
`SAME FOR CONNZ HEARING
`CONNl <§c HOSTI
`
`480
`r
`MOVE SEARCH TUPLE TO SHHL
`I
`482
`/‘
`REMOVE OTHER TUPLES CONTAINING HOSTl FROM SCL
`
`V
`
`I
`
`ServiceNow, Inc's Exhibit 1001
`
`015
`
`

`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 15 0f 26
`
`US 7,027,411 B1
`
`DONE
`
`FOR EACH
`MHL
`TUPLE (SEARCH TUPLE
`
`)
`CONSIDER CONNl AND HOSTl
`
`DONE
`
`FOR EACH
`EHL
`TUPLE CONTAINING
`HOSTl
`
`)
`CONSIDER CONN2
`
`TUPLE IN CONN
`TO CONN LINKS FOR
`CONN2 AND CONNl
`
`FIG. 14
`
`CONN2 TO HOSTl
`TUPLE IN EHL?
`
`GROUP/PORT
`DIFFERENT FOR CONN2
`I ARING CO‘NNI & HOST
`
`MOVE SEARCH TUPLE TO EI~H,
`
`ServiceNow, Inc's Exhibit 1001
`
`016
`
`

`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 16 0f 26
`
`US 7,027,411 B1
`
`FIG. 15
`
`FOR EACH
`
`CONSIDER CONNl AND HOST]
`
`CONNl GROUP/
`PORT ALREADY IN
`ALREADYDIDLOOKFORS
`LIST?
`
`.
`
`508
`
`F '
`
`CREATE A LIST OF ALL CONNS IN CONN TO
`CONN LINKS TUPLES HEARD BY CONNl ON SAME
`GROUP/PORT AS HOSTl
`
`FOR EACH CONN
`(CONN2) IN LIST
`
`CONN2 TO HOSTl
`TUPLE rIN MHL
`
`INITIATE LOOKFOR FOR CONN2 TO HOSTl
`(VIA TUPLE MANAGER)
`1
`1
`ADD CONNl GROUP/PORT "TUPLE COMPONENT" (TUCO) ‘v 516
`TO ALREADYDIDLOOKFORS LIST
`|
`
`ServiceNow, Inc's Exhibit 1001
`
`017
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 17 0f 26
`
`US 7,027,411 B1
`
`FIG. 16a
`DONE TO BLOCK
`
`MORE CONNl
`GROUP/PORT TUPLES
`IN MHL?
`
`EXISTING
`N-ARY MIPIS TUPLE
`
`NO 526
`J
`
`528
`HOSTI ALREADY
`IN MHS TUPLE?
`
`DONE
`
`FOR REMAINING
`MHL TUPLE WITH
`RENCE TO HOSTI'?
`DO
`CONSIDER CONN2
`
`CONNl -TO-CONN2
`TUPLE IN CONN-TO-CONN LINKS TUPLE ON S ‘
`GROUP/PORT AS 7CONNLT0-HOST
`
`ADD AN MHL TUPLE FOR CONNZ-TO-I-IOSTI WITH SAME
`CONN2 GROUP/PORT AS CONNl-TO-CONN2 IN CURRENT MHS TUPLE
`W
`
`V
`
`ServiceNow, Inc's Exhibit 1001
`
`018
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 18 0f 26
`
`US 7,027,411 B1
`
`FIG. 16b
`
`FROM BLOCK 518
`
`FOR EACH
`SHL
`TUPLE
`
`EXISTING
`SHS TUPLE FOR
`COg‘IN
`
`CREATE SHS TUPLE
`
`ADD HOST TUCO TO SHS
`
`ServiceNow, Inc's Exhibit 1001
`
`019
`
`

`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 19 0f 26
`
`US 7,027,411 B1
`
`FIG. 17
`
`934
`1)
`CONVERT TOPOLOOY
`INTO TUPLE
`LISTS
`
`.
`
`936
`
`)
`
`COMPARE CURRENT LIST WITH
`NEW LIST AND DISCARD
`IN DENTICAL TUPLES
`
`938
`
`TAKE ACTION ON
`CHANGES TO TOPOLGY
`
`ServiceNow, Inc's Exhibit 1001
`
`020
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 20 of 26
`
`US 7,027,411 B1
`
`.
`
`C
`
`55”
`
`FIG 18a
`
`
`
`
`DONE
`
`D 0
`
`IS NODEA CONN?
`
`255
`
`
`4
`55
`R EAC
`F0
`
`ONNECTED INTERFACE (CONNIFACE) 0
`CONN (CONNI
`Do
`s C0\‘NIFAC
`c0NNEc1'ED161;sTAR SEGMENT
`
`ONE
`
`YES
`
`558
`
`_ TO BLOCK 5§x_)
`OF FIG. 18b
`
`
`
`FROM
`BLOCKS
`
`F10 18b
`
`NO
`
`N0
`
`YES
`
`FOR EACH T RINTERFA E
`IN(§EgEMENT
`C
`DO
`
`EXISTING SHS
`"TUPO TUPL " FOR
`SEGMENT ?
`NO
`
`CREATE A TOPO SHS TUPLE
`.—
`
`ADD TUCO FOR
`INTERFACES HOST T0 TOPO
`SHS
`
`
`
`'
`
`A
`
`5 66
`
`568
`
`N0
`
`YES
`
`commas
`CONNECFEDTOABUS SEGMENT?
`
`YES
`
`EXISTING MHS
`FOR comm 7
`
`NO T
`
`CREATE A TOPO M1-[S TUPLE
`
`ADD TUCO FOR HOST T0 MHS 'I'UPLE
`
`572
`
`CREATE CONN LINKS TUPLE FOR
`CONN1 & CONNZ
`
`
`
`O21
`
`ServiceNow, Inc's Exhibit 1001
`
`ServiceNow, Inc's Exhibit 1001
`
`021
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 21 of 26
`
`US 7,027,411 B1
`
`
`
`
`CREATE UNHEARD OF LINKS TUPLE
`
`DEFAULT SEGMENT?
`
`FIG. 18b
`
`NODE IN STAR SEGMENT?
`
`
`
`588
`
`CREATE SHS TUPLE
`
`
`
`590
`
`ADD TUCO FOR NODE TO SHS TUPLE
`
`TO
`BLOCK 55.0
`OF FIG. 18a
`
`O22
`
`ServiceNow, Inc's Exhibit 1001
`
`ServiceNow, Inc's Exhibit 1001
`
`022
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 22 of 26
`
`US 7,027,411 B1
`
`FIG. 19
`
`
`
`MARK NT AS "NO CHANGE"
`
`O23
`
`ServiceNow, Inc's Exhibit 1001
`
`FOR EACH TUPLE
`IN NEW
`TUPLES (NT)
`
`602
`
`LOOK FOR EXACT MATCH IN CURRENT TUPLES
`
`
`
`604
`
`EXACT MATCH FOUND?
`
`ServiceNow, Inc's Exhibit 1001
`
`023
`
`

`
`U.S. Patent
`
`Mw
`
`M.mB
`
`7SU
`
`1B114
`
`mine5%,mom
`
`m~..AEd?EmamzEmass55mom
`
`SN.05
`
`
`
`
`
`M..mosmzzoozosomopvfiowm%.mm:2°52EE2ofizamé
`
`7,__e:oz$___2Mmmda.ax:E32
`
`mobmzzouzo_.a:mz§__3E8eE§aEmmmdiQEEvasz
`
`024
`
`ServiceNow, Inc's Exhibit 1001
`
`ServiceNow, Inc's Exhibit 1001
`
`024
`
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 24 of 26
`
`US 7,027,411 B1
`
`OE.52.E52
`
`Emsamm55
`
`mobmzzoumo
`
`OE5%952
`
`EmzommEm
`
`mobmzzoumo
`
`ac:mac:
`
`305.2Ezopumzzou
`
`asE:
`
`zoaomzzou
`
`Emmamozéu
`
`son95:
`
`E305.Ezoaumzzou
`
`.5832:6
`
`zozomzzou
`
`m._bmE.F<
`
`EmEzasso:
`
`...EasE952
`
`N.E:~50
`
`0Z
`
`mam.05
`
`EmE2H55%
`
`E.E:asE9,58
`
`séaoqmOE.
`
`08GEmo
`
`as.ommo3E0015EOE
`
`5%mom
`
`EmQ
`
`mED._.
`
`EmE2"55%
`
`wEmEuEmzaom
`
`
`
`zzooUZEUHE2
`
`92Em52E003.
`
`N.
`
`EmN50
`
`
`
`zzooozEB<2
`
`9,2Em52E002.
`
`_..
`
`Em~59
`
`O25
`
`ServiceNow, Inc's Exhibit 1001
`
`ServiceNow, Inc's Exhibit 1001
`
`025
`
`

`
`U.S. Patent
`
`r._
`
`PA
`
`0m1,1
`
`1B1140}m
`
`
`
`7,63282952228mo53222,522.5
`
`
`
`S_,22oEm228222282252205222822.52228U5022222SE2822222:022202:02mozsa
`
`2.82$622
`
`22288228
`
`
`
`2220282982228
`
`6.222522o2.82
`
`.
`
`.m228o2EB<252ad.28m23228
`s22222220282
`
`6E22222
`
`29,22222.282288
`
`...
`
`2.
`
`22228E2228
`
`OZ
`
`2..
`
`.23E2.3282S20328
`
`20%.222:0
`
`com.05
`
`
`
`§2uo._mZONE
`
`28.222o
`
`2225222:22228
`
`5:22&27:523
`
`2..
`
`1E2E2,3.58
`
`Em28E2228
`
`228OzEo._.<E
`
`9,2152E27:82.
`
`O26
`
`ServiceNow, Inc's Exhibit 1001
`
`ServiceNow, Inc's Exhibit 1001
`
`026
`
`

`
`U.S. Patent
`
`Apr. 11,2006
`
`Sheet 26 of 26
`
`US 7,027,411 B1
`
`omvmzzzp5%mom
`
`SO:52ZHm,.EDH
`
`
`
`.oazo%_mz:vaaa
`
`zzouaomn:ma2.
`
`BEE5238%
`
`
`
`EmzcmmSsfima
`
`E8:~50E558.5Ez,3E85%
`
`Em~59E92:8.6E28E85%
`
`5:2asmo
`
`...5E5E958.53%no7285%
`
`5%m>o2
`
`Eo§2.Ezoaomzzou
`
`-.252Bass
`
`Emzoa22.8
`
`mzzouma
`
`027
`
`ServiceNow, Inc's Exhibit 1001
`
`68anmo.3860.520%
`
`NE
`
`mzoa98322:5%mom
`
`So52Emafibp.
`
`ServiceNow, Inc's Exhibit 1001
`
`027
`
`
`
`
`
`

`
`US 7,027,411 B1
`
`1
`METHOD AND SYSTEM FOR IDENTIFYING
`AND PROCESSING CHANGES TO A
`NETWORK TOPOLOGY
`
`FIELD OF INVENTION
`
`The present invention relates generally to computer net-
`works. More particularly, it relates to a method and system
`for identifying changes to a network topology and for acting
`upon the network based on the changes.
`
`BACKGROUND
`
`As communications networks, such as the Internet, carry
`more and more traffic, efficient use of the bandwidth avail-
`able in the network becomes more and more important.
`Switching technology was developed in order to reduce
`congestion and associated competition for the available
`bandwidth. Switching technology works by restricting traf-
`fic. Instead of broadcasting a given data packet to all parts
`of the network, switches are used to control data flow such
`that
`the data packet
`is sent only along those network
`segments necessary to deliver it to the target node. The
`smaller volume of traffic on any given segment results in few
`packet collisions on that segment and, thus, the smoother
`and faster delivery of data. A choice between alternative
`paths is usually possible and is typically made based upon
`current traffic patterns.
`The intelligent routing of data packets with resultant
`reduction in network congestion can only be effected if the
`network topology is known. The topology of a network is a
`description of the network which includes the location of
`and interconnections between nodes on the network. The
`
`word “topology” refers to either the physical or logical
`layout of the network, including devices, and their connec-
`tions in relationship to one another. Information necessary to
`create the topology layout can be derived from tables stored
`in network devices such as hubs, bridges, and switches. The
`information in these tables is in a constant state of flux as
`
`new entries are being added and old entries time out. Many
`times there simply is not enough information to determine
`where to place a particular device.
`Switches examine each data packet that they receive, read
`the source addresses, and log those addresses into tables
`along with the switch ports on which the packets were
`received. If a packet is received with a target address without
`an entry in the switches table,
`the switch receiving it
`broadcasts that packet to each of its ports. When the switch
`receives a reply, it will have identified where the new node
`lies.
`
`In a large network with multiple possible paths from the
`switch to the target node, this table can become quite large
`and may require a significant amount of the switch’s
`resources to develop and maintain. As an additional com-
`plication, the physical layout of devices and their connec-
`tions are typically in a state of constant change. Devices are
`continually being removed from, added to, and moved to
`new physical locations on the network. To be effectively
`managed, the topology of a network must be accurately and
`efficiently ascertained, as well as maintained.
`Existing mapping methods have limitations that prevent
`them from accurately mapping-topological relationships.
`Multiple connectivity problems are one sort of difficulty
`encountered by existing methods. For example, connectors
`such as routers, switches, and bridges may be interconnected
`devices in a network. Some existing methods assume that
`these devices have only a single connection between them.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`In newer devices, however, it is common for manufacturers
`to provide multiple connections between devices to improve
`network efficiency and to increase capacity of links between
`the devices. The multiple connectivity allows the devices to
`maintain connection in case one connection fails. Methods
`
`that do not consider multiple connectivity do not present a
`complete and accurate topological map of the network.
`Another limitation of existing topology methods is the use
`of a single reference to identify a device. Existing methods
`use a reference interface or a reference address in a set of
`devices to orient all other devices in the same area. These
`
`methods assumed that every working device would be able
`to identify, or “hear,” this reference and identify it with a
`particular port of the device. With newer devices, however,
`it is possible that the same address or reference may be heard
`out of multiple ports of the same device. It is also possible
`that the address or reference may not be heard from any
`ports, for example, if switching technology is used.
`Still another limitation of existing mapping systems is that
`they require a complete copy of the topological database to
`be stored in memory. In larger networks, the database is so
`large that this really is not feasible, because it requires the
`computer to be very large and expensive.
`Still another difficulty with existing systems is that they
`focus on the minutia without considering the larger mapping
`considerations. Whenever an individual change in the sys-
`tem is detected, existing methods immediately act on that
`change, rather than taking a broader view of the change in
`the context of other system changes. For example, a device
`may be removed from the network temporarily and replaced
`with its ports reversed. In existing systems, this swapped
`port scenario could require hundreds or thousands of
`changes because the reference addresses will have changed
`for all interconnected devices.
`
`Still another disadvantage of existing methods is that they
`use a continuous polling paradigm. These methods continu-
`ously poll network addresses throughout the day and make
`decisions based on those continuous polling results. This
`creates traffic on the network that slows other processes.
`Still another limitation of existing methods is the assump-
`tion that network parts of a particular layer would be
`physically separated from other parts. Network layer 1 may
`represent the physical cabling of the network, layer 2 may
`represent the device connectivity, and layer 3 may represent
`a higher level of abstraction, such as the groupings of
`devices into regions. Existing methods assume that all layer
`3 region groupings are self-contained, running on the same
`unique physical networking. However, in an intemet proto-
`col (IP) network, multiple IP domains may co-exist on the
`same lower layer networking infrastructure. It has become
`common for a network to employ a virtual
`local area
`network (LAN) to improve security or to simplify network
`maintenance, for example. Using virtual LANs, a system
`may have any number of different IP domains sharing the
`same physical connectivity. As a result, existing methods
`create confusion with respect
`to topological mapping
`because networks with multiple IP addresses in different
`subnets for the infrastructure devices cannot be properly
`represented because they assume the physical separation of
`connectivity for separate IP domains. Still another limitation
`of existing methods is that they do not allow topological
`loops, such as port aggregation or trunking, and switch
`meshing.
`
`028
`
`ServiceNow, Inc's Exhibit 1001
`
`ServiceNow, Inc's Exhibit 1001
`
`028
`
`

`
`3
`SUMMARY OF INVENTION
`
`4
`DETAILED DESCRIPTION
`
`US 7,027,411 B1
`
`A method and system are disclosed for mapping the
`topology of a network having interconnected nodes by
`identifying changes in the network and updating a stored
`network topology based on the changes. The nodal connec-
`tions are represented by data tuples that store information
`such as a host identifier, a connector interface, and a port
`specification for each connection. A topology database
`stores an existing topology of a network. A topology con-
`verter accesses the topology database and converts the
`existing topology into a list of current tuples. A connection
`calculator calculates tuples to represent connections in the
`new topology. The topology converter receives the new
`tuples, identifies changes to the topology, and updates the
`topology database using the new tuples. The topology con-
`verter identifies duplicate tuples that appear in both the new
`tuples and the existing tuples and marks the duplicate tuples
`to reflect that no change has occurred to these connections.
`The topology converter attempts to resolve swapped port
`conditions and searches for new singly-heard and multi-
`heard host link tuples in the list of existing tuples. The
`topology converter also searches for new conflict link tuples
`in the existing tuples. The topology converter updates the
`topology database with the new topology.
`
`SUMMARY OF DRAWINGS
`
`FIG. 1 is a drawing of a typical topological bus segment
`for representing the connectivity of nodes on a network.
`FIG. 2 is a drawing of a typical topological serial segment
`for representing the connectivity of nodes on a network.
`FIG. 3 is a drawing of a typical topological star segment
`for representing the connectivity of nodes on a network.
`FIG. 4 is a drawing of another typical topological star
`segment for representing the connectivity of nodes on a
`network.
`
`FIG. 5 is a drawing of the connectivity of an example
`network system.
`FIG. 6 is a drawing of the connectivity of another example
`network system.
`FIG. 7 is a block diagram of the system.
`FIG. 8 is a flow chart of the method of the system.
`FIG. 9 is a flow chart of the method used by the tuple
`manager.
`FIG. 10 is a flow chart of the method used by the
`connection calculator.
`
`FIG. 11 is a flow chart of the first weeding phase of the
`method used by the connection calculator.
`FIGS. 12a—d are flow charts of an infrastructure-building
`phase of the method used by the connection calculator.
`FIG. 13 is a flow chart of a second weeding phase of the
`method used by the connection calculator.
`FIG. 14 is a flow chart of the noise reduction phase of the
`method used by the connection calculator.
`FIG. 15 is a flow chart of the look-for phase of the method
`used by the connection calculator.
`FIGS. 16a—b are flow charts of the consolidation phase of
`the method used by the connection calculator.
`FIG. 17 is a flow chart of the method used by the topology
`converter.
`
`FIGS. 18a—b are flow charts of the morph topo phase of
`the method used by the topology converter.
`FIG. 19 is a flow chart of the duplication discard phase of
`the method used by the topology converter.
`FIGS. 20a—d are flow charts of the identify different
`tuples phase of the method used by the topology converter.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`The system provides an improved method for creating
`topological maps of communication networks based. Con-
`nectivity information is retrieved from the network nodes
`and stored as “tuples” to track specifically the desired
`information necessary to map the topology. These light
`weight data structures may store the host identifier, interface
`index, and a port. From this tuple information, the topology
`may be determined. A tuple may be a binary element insofar
`as it has two parts representing the two nodes on either end
`of a network link or segment. A “tuco” refers to a tuple
`component, such as half of a binary tuple.
`As used herein, a node is any electronic component, such
`as a connector or a host, or combination of electronic
`components with their interconnections. A connector is any
`network device other than a host,
`including a switching
`device. A switching device is one type of connector and
`refers to any device that controls the flow of messages on a
`network. Switching devices include, but are not limited to,
`any of the following devices:
`repeaters, hubs,
`routers,
`bridges, and switches.
`As used herein, the term “tuple” refers to any collection
`of assorted data. Tuples may be used to track information
`about network topology by storing data from network nodes.
`In one use, tuples may include a host identifier, interface
`information, and a port specification for each node. The port
`specification (also described as the group/port) may include
`a group number and a port number, or just a port number,
`depending upon the manufacturer’s specifications. A binary
`tuple may include this information about two nodes as a
`means of showing the connectivity between them, whether
`the nodes are connected directly or indirectly through other
`nodes. A “conn-to-conn” tuple refers to a tuple that has
`connectivity data about connector nodes. A “conn-to-host”
`tuple refers to a tuple that has connectivity data about a
`connector node and a host node. In one use, tuples may have
`data about more than two nodes; that is, they may be n-ary
`tuples, such as those used with respect to shared media
`connections described herein.
`
`A “singly-heard host” (shh) refers to a host, such as a
`workstation, PC, terminal, printer, other device, etc., that is
`connected directly to a connector, such as a switching
`device. A singly heard host link (shhl) refers to the link, also
`referred to as a segment, between a connector and an shh. A
`“multi-heard host” (mhh) refers to hosts that are heard by a
`connector on the same port that other hosts are heard. A
`multi-heard host link (mhhl) refers to the link between the
`connector and an mhh. A link generally refers to the con-
`nection between nodes. A segment is a link that may include
`a shared media connection.
`
`FIG. 1 is a drawing of a typical topological bus segment
`100 for representing the connectivity of nodes on a network
`110. In FIG. 1, first and second hosts 121, 122, as well as a
`first port 131 of a first connector 140 are interconnected via
`the network 110. The bus segment 100 comprises the first
`and second hosts 121, 122 connected to the first port 131 of
`the first connector 140.
`
`FIG. 2 is a drawing of a typical topological serial segment
`200 for representing the connectivity of nodes on the net-
`work 110. In FIG. 2, the first host 121 comprises a second
`port 132 on a second connector 145 which is connected via
`the network 110 to the first port 131 on the first connector
`140. The serial segment 200 comprises the second port 132
`on the second connector 145 connected to the first port 131
`on the first connector 140. FIG. 2 is an example of a
`connector-to-connector (“conn-to-conn”) relationship.
`
`029
`
`ServiceNow, Inc's Exhibit 1001
`
`ServiceNow, Inc's Exhibit 1001
`
`029
`
`

`
`US 7,027,411 B1
`
`5
`FIG. 3 is a drawing of a typical topological star segment
`301 for representing the connectivity of nodes on the net-
`work 110. In FIG. 3, the first host 121 is connected to the
`first port 131 of the first connector 140. The star segment 301
`comprises the first host 121 connected to the first port 131
`of the first connector 140. FIG. 3 is an example of a
`connector-to-host (“conn-to-host”) relationship.
`FIG. 4 is a drawing of another typical topological star
`segment 301 for representing the connectivity of nodes on
`the network 110. In addition to the connections described
`
`with respect to FIG. 3, a third host 123 is connected to a third
`port 133 of the first connector 140 and a fourth host 124 is
`connected to a fourth port 134 of the first connector 140. In
`FIG. 4, the star segment 301 comprises the first host 121
`connected to the first port 131 of the first connector 140, the
`third host 123 connected to the third port 133 of the first
`connector 140, and the fourth host 124 connected to the
`fourth port 134 of the first connector 140. Thus, the star
`segment 301 comprises, on a given connector, at least one
`port, wherein one and only one host is connected to that port,
`and that host. In the more general case, the star segment 301
`comprises, on a given connector, all ports having one and
`only one host connected to each port, and those connected
`hosts. Since the segments, or links, drawn using the topo-
`logical methods of FIG. 4 resemble a star, they are referred
`to as star segments.
`For illustrative purposes, nodes in the figures described
`above and in subsequent figures are shown as individual
`electronic devices or ports on connectors. Also, in the figures
`the nodes are represented as terminals. However, they could
`also be workstations, personal computers, printers, scanners,
`or any other electronic device that can be connected to
`networks 110.
`
`FIG. 5 is a drawing of the connectivity of an example
`network system. In FIG. 5, first, third, and fourth hosts 121,
`123, 124 are connected via the network 110 to first, third,
`and fourth ports 131, 133, 134 respectively, wherein the first,
`third, and fourth ports 131, 133, 134 are located on the first
`connector 140.
`
`The first, third and fourth hosts 121, 123, 124 are singly-
`heard hosts connected to separate ports 131, 133, 134 of a
`common connector 140—the first connector 140. The fifth
`
`and sixth hosts 125, 126 are singly-heard hosts connected to
`the third and fourth connectors 142, 143. The seventh and
`eighth hosts 127, 128 are multi-heard hosts connected to the
`same port 139 of the fifth connector 144. The multi-heard
`hosts 127, 128 illustrate a shared media segment 180, also
`referred to as a bus 180.
`
`The second, third, fourth, and fifth connectors 141, 142,
`143, 144 are interconnected and illustrate a switch mesh
`181. Each of the connectors in the switch mesh 181 is
`
`to
`connected to each other, either directly or indirectly,
`create a fully meshed connection. In the mesh, traffic may be
`dynamically routed to create an efficient flow.
`FIG. 5 also shows an example of a port aggregation 182,
`also referred to as trunking 182. The first connector 140 is
`connected via the network 110 to the second connector 141
`
`by two direct links, each of which is connected to different
`ports on the connectors. One link is connected to the sixth
`port 136 of the first connector 140 and to the seventh port of
`the second connector 137. The other link is connected to fifth
`
`port 135 of the first connector 140 and to the eighth port 138
`of the second connector 141. In this example, two connec-
`tors illustrate the multiple connectivity between nodes.
`Depending upon the device specifications, devices such as
`connectors may be connected via any number of connectors.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`As explained herein, the system resolves multiple connec-
`tivity problems by tracking port information for each con-
`nection.
`
`FIG. 6 is a drawing of the connectivity of a portion of a
`network having three connectors 171, 172, 173. A first host
`151 is connected directly to the first port 161 of the first
`connector 171 and the second host 152 is connected to a
`
`sixth port 166 of the third connector 173. The second port
`162 of the first connector 171 is connected directly to the
`third port 163 of the second, or intermediate, connector 172.
`The fourth port 164 of the intermediate connector 172 is
`connected directly to the fifth port 165 of the third connector
`173.
`
`FIG. 7 shows a block diagram of the system. FIG. 8 shows
`a flow chart of the method used by the system to retrieve and
`update the topology of the network. A tuple manager 300,
`also referred to as a data miner 300, gathers 902 data from
`network nodes and builds 904 tuples to update the current
`topology.