United States Patent [19]
`Wu
`
`[54] AUTOMATIC DISCOVERY OF NETWORK
`ELEMENTS
`[75] inventor:
`Jeff C. Wu, Ft. Collins, C010.
`[73] Assignee: Hewlett-Packard Company, Palo
`Alto, Calif.
`[21] App]. No.: 519,187
`[22] Filed:
`May 3, 1990
`
`[51] Int. Cl.5 ............................................ .. G06F 13/00
`[52] US. Cl. ........................... .. 395/200; 364/DIG. 1;
`364/284.4; 364/242.94; 364/2228!
`[58] Field of Search ................. .. 364/DIG. l; 370/54,
`370/851, 85.12, 85.13, 85.15, 94.1; 395/200,
`325, 800
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,644,496 2/1987 Andrews ....................... .. 395/800
`4,829,516 5/1989 Orimo ct a1.
`370/8512 X
`4.879.716 11/1989 McNally et a1.
`.... .. 364/D1G 1
`4,914,571 4/1990 Baratz et al.
`.... .. 364/D1G 1
`4,918,598 4/1990 Ashkin et al. .... ..
`364/DIG 1
`4,991,089 2/1991 Shorter
`364/D1G 1
`5,016,163 5/1991 Jesshope et al.
`364/D1G. 1
`5,051,987 9/1991 Conlon ............. ..
`370/94.1
`5,088,032 2/1992 Bosack ........................ .. 364/D1G.1
`Primary Examiner—Thomas M. Heckler
`[57]
`ABSTRACT
`Disclosed is a computer network node discovery sys
`
`illllllllllllllllllllllllllllllllllllIlllllllllllllllllllllllllllllllllllll
`5,185,860
`Feb. 9, 1993
`
`USO05185860A
`Patent Number:
`Date of Patent:
`
`[111
`[451
`
`tem that provides a general way of discovering network
`elements, or nodes, connected to a computer network,
`and a speci?c algorithm for discovering nodes con
`nected to a TCP/ IP network, using the SNMP protocol
`available within the TCP/IP network software. Some
`nodes on a network, called discovery agents, can con
`vey knowledge of the existence of other nodes on the
`network. The network discovery system queries these
`agents and obtains the information they have about
`other nodes on the network. It then queries each of the
`nodes obtained to determine if that node is also a discov
`ery agent. In this manner, most of the nodes on a net
`work can be discovered. The process of querying dis
`covery agents to obtain a list of nodes known to the
`discovery agents is repeated at timed intervals to obtain
`information about nodes that are not always active. In a
`TCP/IP network, discovery agents are nodes that re
`spond to queries for an address translation table which
`translates internet protocol (IP) addresses to physical
`addresses. The data from each node's address transla
`tion table is used to obtain both the IP and the physical
`address of other nodes on the network. These nodes are
`then queried to obtain additional information. After all
`the nodes on a network are discovered, the list of nodes
`is written to a database where it can be displayed by the
`network manager or other users of the network.
`
`16 Claims, 17 Drawing Sheets
`
`MAIN MEMORY #110
`
`DISCOVER sYsTEM
`
`PROCESSING H102 122,, OPERATING
`ELEMENT
`SYSTEM
`
`NETWORK
`SOFTWARE
`
`1
`(
`
`T
`
`#104
`
`b
`
`sYsTEM BUS
`
`‘-
`
`12o
`
`124
`
`4A
`)
`
`1
`
`116?
`
`
`
`
`
`
`
`
`
`
`
`1.7112 ,,10B DISPLAY INTERFACE NETwoRK "-
`
`
`
`, 114 o1s|<
`
`
`
`,5 PRINTER
`
`2 118
`
`
`
`{5106 KEYBOARD
`
`I
`
`5 ..............
`
`.............................................................................................. ..
`
`T
`
`7
`
`NETWORK
`
`If’;
`
`y)
`
`=
`
`Ericsson Exhibit 1016
`Page 1
`
`

`

`U.S. Patent
`
`Feb. 9, 1993
`
`Sheet 1 of 17
`
`5,185,860
`
`.............................................................................................. A VFEFMZ \ m:
`
`.
`
`
`
`~ u ‘ - Q o o o - u . ‘ - ¢ - - - - - u I ‘ . u - . . ~ ¢ . ~ Q ¢ 0 > 0 u ¢ - - , - - - - - u - n - | - - - - . . - u - I - - ‘ - - - l . n a . . . - ¢ - - u Q . . n ‘ ‘ v - . u - Q u u u u - u n - - - u - u u ~ . - - ~ - - q o ¢ .
`
`“OHM
`
`
`
`zmhw>w mw>ouw Ho
`
`3H ., 81
`
`£62.52 ozcéwmo N: ozHwwwuo?
`
`E1553 5.55 , , Ewzwd
`
`02k
`A. 25 5.53 v
`
`
`
`m L vZk ~3k 08k
`
`‘1 k QOHK <
`
`$52: $8 i252 2:20 23??
`
`
`
`
`
`HVEEEH
`
`
`8*
`
`r
`
`Ericsson Exhibit 1016
`Page 2
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 2 of 17
`
`5,185,860
`
`/ 202
`
`206
`
`NODE
`
`21s
`
`NODE
`
`11a
`’'
`
`REPEATER
`
`_
`
`214
`'J
`
`E
`
`\“212
`
`21a
`
`"ODE
`
`BRIDGE
`
`“20:!
`
`NETWORK
`PROBE
`
`\“224
`
`ROUTER!
`GATEWAY
`
`,220
`
`‘N’
`
`222
`[I
`
`IN’
`
`FIG. 2
`
`Ericsson Exhibit 1016
`Page 3
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 3 of 17
`
`5,185,860
`
`DISCOVER
`FIG. a
`
`#302
`
`#304
`SELF-SEED
`FIG. 7
`
`,306
`PROCESS-MODE
`FIG. a
`
`F308
`PROCESS-PING
`FIG. 9
`
`W310
`PROCESS-IFIP
`FIG. 10
`
`,312
`PROCESS-AT
`FIG. 15
`
`‘ FIG. 4|
`
`I FIG. 5|
`
`FIG. 3
`
`Ericsson Exhibit 1016
`Page 4
`
`

`

`U.S. Patent
`
`Feb. 9, 1993
`
`Sheet 4 of 17
`
`5,185,860
`
`402
`1“
`STORE-IF
`FIG. 11
`
`404
`/“
`STORE-IF
`FIG. 12
`
`406
`I’
`INVALIDNODE
`FIG. 13
`
`408
`1"
`FINDNODE
`FIG. 14
`
`410
`l"
`ADDNODE
`FIG. 15
`
`FIG . 4
`
`Ericsson Exhibit 1016
`Page 5
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 5 of 17
`
`5,185,860
`
`502
`V r’
`
`STORE-AT
`FIG. 17
`
`504
`r’
`INVALIDNODE
`HG, Ll
`
`,
`
`506
`r
`FINDNODE
`FIG. 14
`
`508
`J"
`ADDNODE
`FIG. 15
`
`FIG. 5
`
`Ericsson Exhibit 1016
`Page 6
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 6 of 17
`
`5,185,860
`
`@
`
`N602
`
`GET USER
`oPTIoNs
`‘P
`INIT DATABASE
`AND LOAD
`NODE LIST
`Jr
`INIT DOMAIN #606
`{I
`SELF SEED
`FIG. 7
`
`"604
`
`{4608
`
`POINT T0
`FIRST NODE
`LIST ENTRY
`
`#610
`
`612
`
`MORE
`ENTRIES
`?
`
`[1614
`
`1 WAIT
`
`PROCESS NODE W616
`FIG. 8
`&
`POINT TO
`NEXT NODE
`LIST ENTRY
`
`#618
`
`FIG. 6
`
`Ericsson Exhibit 1016
`Page 7
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 7 of 17
`
`5,185,860
`
`@
`
`SEND SNMP
`BROADCAST
`REQUEST
`
`W702
`
`RECEIVE SNMP
`MESSAGES
`
`r706
`
`ADDNODE
`FIG. 15
`
`FIG. 7
`
`Ericsson Exhibit 1016
`Page 8
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 8 of 17
`
`5,185,860
`
`802
`
`NODE
`IN DOMAIN
`
`PROCESS PING
`FIG. 9
`806
`
`,, 804
`
`STATE
`CHANGE
`?
`
`808
`[I
`STORE NEW
`STATE IN
`DATABASE
`
`PROCESS IFIP
`FIG. 10
`
`NODE
`RESPOND TO
`SNMP
`
`NODE
`IN DATABASE
`
`STORE NODE IN
`DATABASE
`
`#816
`
`PROCESS AT
`P16. 16
`
`#318
`
`‘15% FIG. 6’
`
`Ericsson Exhibit 1016
`Page 9
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 9 of 17
`
`5,185,860
`
`PING
`INTERVAL
`ELAPSED
`
`SEND ICMP- W904
`ECHO MESSAGE
`
`906
`
`910
`l
`/“
`SET NODE
`FAILED TO
`RESPOND FLAG
`
`RESPONSE
`'1’
`Y
`SET NODE
`RESPONDED
`FLAG
`Tr
`SET NEW PING #912
`INTERVAL
`
`N908
`
`@
`‘FIG. 9
`
`Ericsson Exhibit 1016
`Page 10
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 10 of 17
`
`5,185,860
`
`IFIP
`INTERVAL
`ELAPSED
`
`SEND SNMP
`1004
`E MESSAGE TO
`REQUEST NEXT "’
`IP TABLE ENTRY
`{r
`STORE-1P
`FIG. 11
`
`1006
`
`007
`
`SET NEW IFIP #1008
`I
`
`FIG. 10
`
`SEND SNMP
`MESSAGE TO
`REQUEST NEXT
`IF TABLE ENTRY
`T
`STORE-IF
`FIG. 12
`
`1010 ‘
`
`V1012
`
`1014
`N
`
`MORE
`IF ENTRIES
`‘P
`
`Ericsson Exhibit 1016
`Page 11
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 11 of 17
`
`5,185,860
`
`@
`
`FINDNODE
`FIG. 14
`
`1102
`fl
`
`,Y
`
`NODE
`EXIST
`?
`
`N
`INVALIDNODE
`FIG. 13
`
`1104
`
`1106
`r!
`
`ADDNODE
`Fgeggs
`———-1
`@
`
`UPDATE
`NODE STATE
`
`1112
`
`FIG. 1]
`
`Ericsson Exhibit 1016
`Page 12
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 12 of 17
`
`5,185,860
`
`g
`FIND IPINDEX
`
`1202
`
`r’
`
`MATCHING
`IP RECORD
`
`#1206
`
`MOVE PHYSICAL
`ADDRESS TO
`NODE RECORD
`‘11
`UPDATE STATE
`INFORMATION #1208
`IN NODE RECORD
`
`@
`
`FIG. .72
`
`Ericsson Exhibit 1016
`Page 13
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 13 of 17
`
`5,185,860
`
`1302
`
`IP
`ADDRESS
`= LOOPBACK
`ADDRESS
`
`NODE
`IN DOMAIN
`
`r’
`RETURN 0K
`
`1308
`1"
`v
`RETURN ERROR
`
`@ J
`
`FIG. .73
`
`Ericsson Exhibit 1016
`Page 14
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 14 of 17
`
`5,185,860
`
`@
`
`GET FIRST NODE #1402
`LIST ENTRY
`
`1404
`
`Y
`
`IP
`ADDRESS
`MATCH
`?
`N
`GET NExT NODE #1406
`LIST ENTRY
`
`N
`
`END OF
`NODE LIST
`
`1410
`
`1412
`
`RETURN ERROR
`
`1408
`J r’ -
`RETURN 0K
`
`@ 1
`
`FIG. 14
`
`Ericsson Exhibit 1016
`Page 15
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 15 of 17
`
`5,185,860
`
`C?
`
`HASH IP ADDRESS
`TO OPERATE
`#1502
`TABLE POINTER
`
`I
`ALLOCATE
`MEMORY FOR
`NODE RECORD
`1
`
`#1504
`
`1506
`
`STORE NODE DATA
`AND
`STATE IN RECORD
`
`@
`
`FIG. .75
`
`Ericsson Exhibit 1016
`Page 16
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 16 of 17
`
`5,185,860
`
`AT
`INTERVAL
`EXPIRED
`
`SEND SNMP
`MESSAGE To
`REQUEST NEXT
`AT ENTRY
`Tl!
`STORE-AT
`FIG. 17
`
`1604
`
`1606
`
`1607
`
`MORE
`AT TABLE
`ENTRIES
`
`1608
`UPDATE NODE
`STATE INFO ”
`+
`SET NEW
`AT INTERVAL
`
`1610
`
`@
`FIG. .76
`
`Ericsson Exhibit 1016
`Page 17
`
`

`

`US. Patent
`
`Feb. 9, 1993
`
`Sheet 17 of 17
`
`5,185,860
`
`@
`
`FINDNODE
`FIG. 14
`
`1702
`
`1704
`
`MODE
`EXIST
`?
`N
`INVALIDNODE #1705
`FIG. 13
`
`NODE
`VALID
`?
`
`Y
`ADDNODE
`FIG. 15
`
`1708M
`
`#1710
`
`#1712
`
`UPDATE
`NODE STATE
`
`@
`
`FIG. 17
`
`Ericsson Exhibit 1016
`Page 18
`
`

`

`AUTOMATIC DISCOVERY OF NETWORK
`ELEMENTS
`
`FIELD OF THE INVENTION
`This invention relates to computer systems and more
`particularly to computer networks that interconnect
`computers. Even more particularly, the invention re
`lates to determining the nodes connected to a network.
`
`10
`
`BACKGROUND OF THE INVENTION
`Computer networks are collections of hardware and
`software that connect computers and allow them to
`send information from one computer to another elec
`tronically. A computer network is comprised of the
`physical hardware connections between the various
`computers, for example telephone lines or a coax cable,
`and the software used to send and receive data and to
`route the data to the selected computer on the network.
`A local area network (LAN) is a network connection
`between computers in close proximity, typically less
`than one mile, and usually connected by a single cable
`such as coax cable. A wide area network (WAN) is a
`network of computers located at longer distances, often
`connected by telephone lines or satellite links. Network
`software may sometimes be used with both types of
`networks. For example, a popular network is the De
`partment of Defense internetworking protocol suite,
`known as Transmission Control Protocol/Internet Pro
`tocol (TCP/IP). This system was originally developed
`by the Defense Advanced Research Projects Agency
`(DARPA) and has now been widely distributed to Uni
`versities and industry.
`When a network is fast growing, that is, network
`elements or nodes are being added frequently, a net
`work administrator may not know all of the nodes con
`nected to the network. Also, a network administrator
`new to his or her job may not be familiar with the nodes
`on the network. Determining the nodes manually is a
`difficult problem. The administrator may contact all the
`users of the network known to the administrator, how
`ever, infrequent users may be forgotten and not con
`tacted. Also, if a node is connected to the network, but
`not active because the computer is not powered up or is
`inoperative, that node may not be included in the list. In
`a very short local area network, a network administra
`tor may physically trace the cable of the network to
`determine which nodes are located on the network.
`However, since longer local area networks can extend
`as far as a mile, through many floors and offices within
`a building, physical tracing may be impossible. In a
`wide area network, physical tracing is almost always
`impossible.
`For some commonly used networks, special equip
`ment can be purchased that will determine the nodes
`located on the network and the distance between them.
`This equipment, called a probe, is often limited by the
`other components of the network, however. For exam
`ple, in a local area network, a repeater unit may be used
`to extend the effective distance of the local area net
`work to a distance greater than is capable with a single
`cable. A repeater unit ampli?es signals, and therefore
`will not allow a probe to determine the location of
`nodes beyond the repeater.
`Other units connected to the network may obscure
`nodes. For example a bridge unit connects two similar
`networks but only passes messages that are being sent
`from a node on one side of the bridge to a node on the
`
`35
`
`40
`
`45
`
`50
`
`60
`
`65
`
`1
`
`5,185,860
`
`2
`other side of the bridge. It will not pass messages be
`tween nodes on the same side, in order to reduce the
`traffic on the other side of the bridge. A bridge will
`prevent a probe from determining the nodes on the
`other side of the bridge. A gateway is a unit that con
`nects dissimilar networks to pass messages. Because a
`gateway may have to reformat a message to accommo
`date a different network protocol, it will prevent a
`probe from finding nodes beyond the gateway.
`There is need in the art then for a method of deter
`mining the nodes on a local area network. There is
`further need in the art for determining such nodes with
`out the use of special equipment. A still further need is
`for a method that will determine which nodes are lo
`cated beyond the repeater units, bridges, and gateways
`on a network.
`
`SUMMARY OF THE INVENTION
`It is an object of the present invention to provide a
`method of determining the elements or nodes connected
`to a network.
`It is another object of the invention to provide a
`method of discovering network nodes on a TCP/IP
`network.
`Another object of the invention is to determine
`which discovered nodes are discovery agents and can
`convey knowledge of the existence of other nodes on
`the network.
`Another object is to query all discovery agents and
`ask for other nodes on the network.
`A further object is to query all TCP/IP nodes to
`retrieve the address translation table from the TCP/IP
`node.
`The above and other objects of the invention are
`accomplished in a system which provides a general way
`of discovering network elements, or nodes, and a spe
`ci?c algorithm for discovering nodes within a TCP/IP
`network, using a standard Simple Network Manage
`ment Protocol (SNMP), which is available within the
`TCP/IP network.
`Some nodes on a network can convey knowledge of
`the existence of other nodes on a network, and are
`called discovery agents. When a network contains dis
`covery agents, these agents can be queried to obtain the
`information they have about other nodes on the net
`work. By obtaining a list of nodes from a single discov
`ery agent, and querying each of the nodes obtained to
`determine if it is also a discovery agent, most of the
`nodes on a network can be discovered.
`The process of querying discovery agents to obtain a
`list of nodes known to be discovery agents, must be
`repeated at timed intervals. At any given time on a
`network, one or more nodes may not be responding to
`the network, either because it is inoperative, or because
`it is not powered up. Therefore, if the discovery process
`is attempted during this time, these unavailable nodes
`will not be discovered. By repeating the discovery pro
`cess over time at regular intervals, additional nodes on
`a network can be discovered.
`In a TCP/IP network, discovery agents are nodes
`that respond to queries for an address translation table.
`Within TCP/IP network, every node will have an inter
`net protocol (IP) address. This address is a 32 bit num
`ber and is unique to all nodes within the TCP/IP net
`work. Although the IP address is probably unique to all
`nodes everywhere that use the TCP/IP protocol, the
`physical address of a node on a particular network will
`
`Ericsson Exhibit 1016
`Page 19
`
`

`

`3
`be different from the IP address. For example, some
`types of LANs use an 8 bit address, and can therefore
`use the low order 8 bits of the IP address, however,
`some other types of LANs use a 48 bit address and
`cannot use the internet address. Therefore, every node
`within a TCP/IP network must have an address transla
`tion table which translates the IP address to the physical
`address. The data from each node‘s address translation
`table can be used to obtain both the IP and the physical
`address of other nodes on the network. Again, as de
`scribed in the above general algorithm, the queries
`should be repeated at timed intervals to insure that
`recently activated nodes are discovered. Another rea
`son for repeating the discovery process over timed
`intervals in a TCP/IP network is that some of the infor
`mation within a node's address translation table may be
`purged if the node does not use the information after a
`period of time. This purge is used to reduce the table
`size requirements within a node. By repeating the
`queries at timed intervals, the greatest amount of trans
`lation table information may be obtained.
`
`0
`
`5
`
`45
`
`5,185,860
`4
`invention should be determined by referencing the ap
`pended claims.
`FIG. 1 shows a block diagram of the computer hard
`ware that contains the discovery system of the present
`invention. Referring now to FIG. 1, a computer system
`100 contains a processing element 102. The processing
`element 102 communicates to other elements within the
`computer system 100 over a system bus 104. A key
`board 106 is used to input information from a user of the
`system, and a display 108 is used to output information
`to the user. A network interface 112 is used to interface
`the system 100 to a network 118 to allow the computer
`system 100 to act as a node on a network. A disk 114 is
`used to store the software of the discovery system of the
`present invention, as well as to store the data base col
`lected by the discovery system. A printer 116 can be
`used to provide a hard copy output of the nodes of the
`network discovered by the discovery system. A main
`memory 110 within the system 100 contains the discov
`ery system 120 of the present invention. The discovery
`system 120 communicates with an operating system 122
`and network software 124 to discover the nodes on the
`network 118.
`FIG. 2 shows a diagram of a network. Referring now
`to FIG. 2, a network 202 contains a node 206. Node 206
`contains the processor 100 (FIG. 1) which contains the
`discovery system software of the present invention.
`Node 206 is attached to a ?rst network segment 118.
`The network segment 118 is connected to a repeater 212
`which is connected to a second network segment 214.
`This second network system 214 has nodes 216 and 218
`attached to it. A repeater, such as repeater 212, allows
`network segments to be connected to allow a network
`to be extended over a longer distance. An important
`characteristic of a repeater is that there is no translation
`of data passing through it. That is, every message that is
`transmitted on one network segment, will pass un
`changed through a repeater‘ to the other network seg
`ment. Therefore, any messages broadcast, for example,
`by node 206 will be received by node 216 and node 218
`after these messages pass through repeater 212.
`Network segment 118 is also attached to a bridge 208
`which connects it to a third network segment 210. A
`bridge will only pass messages that are being transmit
`ted from a node on one side of the bridge to a node on
`the other side of the bridge. It will block messages that
`are transmitted from a node on one side of the bridge to
`a node on that same side of the bridge. This characteris
`tic reduces network traffic on various segments of a
`network.
`Segment 118 is also attached to a router/ gateway 220
`which connects is to a fourth network segment 222.
`Routers are devices that connect network segments
`which have similar characteristics. Gateways are de
`vices which connect networks having different types of
`characteristics. For example, a gateway might connect
`a local area network to a wide area network.
`Because bridges, routers, and gateways. must process
`the messages sent over the network, they also must
`contain information about which nodes are on the net
`work. Therefore, bridges, routers, and gateways are
`authoritative sources of information for determining the
`nodes on the network. A protocol de?nes the format of
`messages that are sent across a network. One popular
`protocol is the Department of Defense Internetworking
`Protocol Suite, popularly known as TCP/IP. Because it
`was developed by the Department of Defense, this
`protocol is widely available and used extensively, par
`
`50
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The above and other objects, features, and advan
`tages of the invention will be better understood by read—
`ing the following more particular description of the
`invention, presented in conjunction with the following
`drawings, wherein:
`FIG. 1 shows a block diagram of the hardware of the
`node that runs the process of the present invention;
`FIG. 2 shows a diagram of a typical computer inter»
`connection network;
`FIGS. 3 through 5 show a hierarchy diagram of the
`modules of the discovery system of the present inven
`tlOn;
`FIG. 6 shows a ?owchart of the main module of the
`invention;
`FIG. 7 shows a ?owchart of the self'seed module of
`the invention;
`FIG. 8 shows a ?owchart ofthe process-node module
`of the invention;
`FIG. 9 shows a ?owchart of the process-ping module
`of the invention;
`FIG. 10 shows a ?owchart of the process-IFIP mod
`ule of the invention;
`FIG. 11 shows a ?owchart of the store-1P module of
`the invention;
`FIG. 12 shows a ?owchart of the store-IF module of
`the invention;
`FIG. 13 shows a ?owchart of the invalidnode module
`of the invention;
`FIG. 14 shows a ?owchart of the ?ndnode module of
`the invention;
`FIG. 15 shows a ?owchart of the addnode module of
`the invention;
`FIG. 16 shows a ?owchart of the process-AT module
`of the invention; and
`FIG. 17 shows a ?owchart of the store-AT module of
`the invention.
`
`55
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`The following description is of the best presently
`contemplated mode of carrying out the present inven
`tion. This description is not to be taken in a limiting
`sense but is made merely for the purpose of describing
`the general principles of the invention. The scope of the
`
`65
`
`Ericsson Exhibit 1016
`Page 20
`
`

`

`5,185,860
`
`5
`ticularly in a university environment. Also, this suite of
`protocols is very popular on the UNIX operating sys-
`tem and has seen wide distribution there. The internet
`protocol (IP) uses a single thirty-two bit address for all
`nodes that can be connected to the internet at any loca—
`tion. Physical addresses within a particular type of net-
`work, are normally different from an IP address. If a
`network address is very small, perhaps eight bits, it may
`be the same as the low order eight bits of the IP address.
`If a network address is large. for example, some LANs
`use forty-eight bit addresses, it is impossible for these
`addresses to correspond directly to IP addresses. There-
`fore, both an IP address and a physical address exist for
`each node on a network. Devices such as routers, gate-
`ways, and bridges, which can send messages from one
`network to another must be able to translate between IP
`addresses and physical addresses. Therefore, these de-
`vices have translation tables which allow them to trans~
`late between these two types of addresses. By accessing
`these translation tables, one of the nodes on a network
`can obtain information about the other nodes on the
`network. The existence of these translation tables allow
`the method of the present invention to perform its func-
`tion.
`
`A network probe 224 is also attached to the network
`118. A network probe 224 is a device that assists in
`locating defective nodes and assists in repairing those
`nodes. Since it is a testing device, it may or may not be
`attached to a network at any given time. When a probe
`is attached to a network, the discovery system of the
`present invention can query the probe and use informa-
`tion obtained from the probe to assist in discovering
`other nodes on the network.
`
`FIGS. 3 through 5 show a hierarchy diagram of the
`modules of the software of the present invention. Refer-
`ring now to FIGS. 3 through 5, discovery module 302
`is the main module of the system. Discovery calls self-
`seed block 304 to start the process of building a database
`about the network, and it calls process-node block 306
`to process information about each node that it obtained
`from self-seed. Process-node block 306 calls process-
`ping block 308 to query a node on the network to deter-
`mine if that node is active. Process-node block 306 also
`calls process-IF]? block 310 for each IP address that it
`obtains. Process-IFIP block 310 calls store-1P block 402
`for each IP address, and store-1P block 402 calls invalid-
`node block 406, findnode block 408, and addnode block
`410, for each IP address. For each IF entry (physical
`address) received, process-IFIP block 310 calls store-IF
`block 404. For each address translation table entry,
`process-node block 306 calls process-AT block 312
`which in turn calls store-AT block 502. Store-AT block
`502 calls invalidnode at block 504, findnode block 506,
`and addnode block 508.
`
`FIG. 6 shows a flowchart of the discovery module
`block 302 (FIG. 3). Referring now to FIG. 6, after entry
`block 602 gets any options that the user wishes to enter.
`Block 604 then initializes the database used to perma-
`nently store the nodes, and loads node list from existing
`entries in the database. If a database for the network
`does not exist, the discovery system has the ability to
`create that database. If a database of the network al-
`ready exists, the discovery system will use the node
`information which is already available in that database
`to query other nodes within the system.
`Block 606 then initializes domains. A domain defines
`the limit beyond which the user of the discovery system
`does not wish to find nodes. That is, the domain limits
`
`6
`the range of the discovery process. This limitation is
`necessary on large networks, to keep the amount of
`processing to reasonable level. Furthermore, a user
`usually is only interested in the nodes on a particular
`network segment, or the network segment connected
`by repeaters and possibly bridges.
`Block 608 then calls FIG. 7 to self-seed the system. If
`no entries were available in the database, the discovery
`system can self-seed by sending a broadcast message
`and determine who responds to that message. After
`returning from self—seed, block 610 points to the first
`node list entry. As discussed earlier, the node list will
`contain a list of the nodes already known to the system.
`This list can be input from the database, or the list can
`be started from self-seed module. After pointing to the
`first entry, block 612 determines if there are more
`entries to process. If there are no more entries to pro-
`cess, block 612 transfers to block 614 which will wait a
`predetermined period of time before reprocessing the
`entire node list. Typically, block 614 will wait for ap-
`proximately thirty seconds. By reprocessing the node
`list periodically, additional nodes can be discovered.
`This is because a node may be inactive on the system at
`any given time and might not be discovered by a single
`pass through the network. By waiting and reprocessing
`the node list, nodes that were inactive may now be
`active and additional information can be obtained.
`If more entries in the node list exist, block 612 trans-
`fers to block 616 to process one of the nodes. After
`processing that node, block 616 transfers to block 618
`which points to the next node list entry and returns to
`block 612 to process the next node.
`FIG. 7 shows a flowchart for the self-seed block 304
`(FIG. 3) which obtains initial information about nodes
`on the network. Referring now to FIG. 7, after entry,
`block 702 sends an SNMP broadcast request to all nodes
`on the network. SNMP stands for Simple Network
`Management Protocol, and is a part of the TCP/IP
`network software. After sending the broadcast request.
`block 702 transfers to block 704 which receives SNMP
`
`I0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`messages from the nodes. If more SNMP messages are
`available, block 704 transfers to block 706 which adds a
`node to the node list for each message received. In this
`manner, all nodes that are currently active on the net-
`work can be queried to obtain initial information about
`the node. After all SNMP messages have been received,
`block 704 returns to the caller.
`
`Another way of self-seeding is to query the address
`translation table for the node that is executing the dis-
`covery system. This table will contain the addresses of
`other nodes on the network, and these addresses are
`then used to start the discovery process.
`FIG. 8 is a flowchart of the process-node block 306
`(FIG. 3). The process-node module of FIG. 8 is called
`from the discovery module of FIG. 6 once for each
`entry in the node list. Therefore, when FIG. 8 is called,
`the address of a single node is passed to it. Referring
`now to FIG. 8, after entry, block 802 determines
`whether the node is within a domain. As discussed
`earlier, the domain defines the limits beyond which the
`discovery program does not wish to discover new
`nodes. If the node is within the domain, block 802 trans-
`fers to block 804 which calls the process-ping module of
`FIG. 9 to determine whether the node is active. After
`returning from FIG. 9, block 804 transfers to block 806
`to determine whether the state of the node has changed
`since the last information was obtained. That is, when
`the process-ping module queries the node, it determines
`
`Ericsson Exhibit 1016
`
`Page 21
`
`Ericsson Exhibit 1016
`Page 21
`
`

`

`5,185,860
`
`10
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`45
`
`7
`the state of the node at the present time. This state is
`compared, in block 806, with the state of the node as it
`was known previously in the database. If that state has
`changed, block 806 transfers to block 808 to store the
`new state in the database. Control then returns to block
`810 which calls process-IFIP to retrieve the IF and IP
`tables from the node. After returning from FIG. 10,
`block 810 transfers to block 812 which determines
`whether the node responded to an SNMP request. If the
`node did respond to the SNMP request, block 812 trans—
`fers to block 814 which determines whether the node is
`currently in the database. If the node is not in the data-
`base, block 814 transfers to block 816 to add the node to
`the database. Control then continues at block 818 which
`calls FIG. 16 to retrieve the address translation table
`from the node. Control then returns to the caller.
`FIG. 9 shows a flowchart of the process-ping module
`block 308 (FIG. 3). This module is called to determine
`whether a node is active on the network. Referring now
`to FIG. 9, after entry block 902 determines whether the
`ping interval has elapsed. The ping interval is used to
`prevent a node from being queried too often. If the ping
`interval has not elapsed, block 902 returns to the caller.
`If the ping interval has elapsed, block 902 transfers to
`block 904 which sends an ICMP-echo message to the
`node. The ICMP’echo protocol is defined as a part of
`TCP/IP and is used to cause the node to return an
`acknowledgement to a message. Block 904 then trans-
`fers to block 906 which determines whether a response
`has been received from the other node. If a response has
`not been received within a predetermined amount of
`time, typically block 906 transfers to block 910 which
`sets a flag to indicates that the node failed to respond. If
`the node does respond, block 906 transfers to block 908
`which sets a flag to indicate that the node did respond
`and then block 912 sets a new ping interval which will
`prevent the node from being pinged for the period of
`the interval. The ping interval is typically five minutes.
`Block 912 then returns to the caller.
`FIG. 10 shows a flowchart of the process-IFIP mod-
`ule block 310 (FIG. 3). The IF and IP tables are avail-
`able in a node to define the translation of physical ad-
`dresses to IP addresses. The information is available as
`two different tables, with an index contained in the IF
`table to cross—reference to the IP table within the node.
`By obtaining these two tables, the discovery system can
`determine what the other interfaces to which a node is
`connected. and therefore determine other networks to
`which the node is connected. Referring now to FIG. 10.
`after entry. block 1002 determines whether the IFIP
`interval has elapsed. The IFIP interval is similar to the
`ping interval described with respect to FIG. 9. and is
`used to keep a node from being queried too often. If the
`IFIP interval has not elapsed, block 1002 returns to the
`caller. If the IFIP has elapsed, block 1002 transfers to
`block 1004 which sends an SNMP message to request
`the node to send its next I? table entry to the discovery
`node. When an entry is received, block 1006 calls store-
`IP module of FIG. 11 to store the node within the node
`list. Block 1007 then transfers back to block 1004 if
`more IP entries are available. After all the entries are all
`stored in the node list, block 1007 transfers to block
`1008 which sets a new IFIP interval of typically greater
`than l0 hours. Block 1010 then sends an SNMP message
`to request that the node send its next IF table entry to
`the discovery node. When an IF table entry is received,
`block 1012 calls the store-IF module of FIG. 12. Block
`1014 then transfers back to block 101 if more entri