./
`
`1‘
`
`-f ":2-IEWLETT-PACKARD COMPANY
`' Intellectual Property Administration
`P. 0. Bo 272400
`Fort C0|Ii(ns, Colorado 80527-2400
`
`J...» ” D
`
`PATENT APPUCAHON
`_
`ATTORNEY DOCKET N°- —
`
`.
`
`,
`
`IN THE U.S. PATENT AND TRADEMARK OFFICE
`Patent Application Transmittal Letter
`
`Illlllllllllllllllllllllllll
`00/12/01
`
`COMMISSIONER FOR PATENTS
`Il
`2
`if gllashington. D.C. 20231
`Sir:
`
`Transmitted herewith for filing under 37 CFR 1.53(b) is a(n):
`
`(X) Utility
`
`(
`
`I Design
`
`l)() original patent application,
`
`I
`
`I continuation-in—part application
`
` .S.3942
`825U09/"Ill II
`
`U 2
`
`INVENTORISII Eric A Pulsipher et al
`
`TITLE:
`
`Method And System For Identifying And Processing Changes To A Network Topology
`
`Enclosed are:
`
`(X) The Declaration and Power of Attorney.
`
`(x) signed
`
`(XI
`
`26
`
`sheets of drawings (one set)
`
`I
`
`(
`
`I Form PTO-1449
`
`I Priority documentlsl
`
`(
`
`)
`
`(
`
`)(0ther)
`
`I
`
`(
`
`) unsigned or partially signed
`
`I Associate Power of Attorney
`
`Information Disclosure Statement and Form PTO—1449
`
`(fee $
`
`I
`
`
`
`
`
` III
`
`(1)
`FOR
`
`TOTAL CLAIMS
`
`INDEPENDENT
`CLAIMS
`ANY MULTIPLE
`DEPENDENT CLAIMS
`
`CLAIMS AS FILED BY OTHER THAN A SMALL ENTITY
`
`(2)
`NUMBER FILED
`
`(3)
`NUMBER EXTRA
`
`(4)
`RATE
`
`(5)
`TOTALS
`
`3 ‘“
`
`3
`
`III
`
`BASIC FEE: Design ($320.00
`
`$270
`I; Utility ($710.00
`
`X$18
`
`$
`
`‘ID-
`
`$
`s
`
`)
`
`TOTAL FILING FEE
`
`OTHER FEES
`
`TOTAL CHARGES TO DEPOSIT ACCOUNT
`
`O0
`
`0
`710
`
`710
`
`710
`
`to Deposit Account 08-2025. At any time during the pendency of this application,
`710
`Charge $
`please charge any fees required or credit any over payment to Deposit Account 08-2025 pursuant to 37
`CFR 1.25. Additionally please charge any fees to Deposit Account 08-2025 under 37 CFR 1.16,
`1.17,1.19, 1.20 and 1.21. A duplicate copy of this sheet is enclosed.
`
`"Express Mail" label no. EL523338183us
`Date of Deposit oct, 31 2000
`I hereby certify that this is being deposited with the
`United States Postal Service "Express Mail Post
`Office to Addressee" service under 37 CFR 1.10 on
`the date indicated above and is addressed to:
`
`
`
`_
`Respectfully submitted.
`
`Enc A Pulsmher et al
`
`BY 9
`
`T. Grant Ritz
`
`Attorney/Agent for Applicantls)
`Reg- No-
`39.819
`
`Date: Oct. 31, 2000
`
`RSV 10/00 ITf3nSNeWl
`
`1
`— Attach as First Page to Transmitted Papers -
`
`Telephone N05 (970) 898-0697 Hp 2007
`SerViceN0w V. HP
`
`IPR20 1 5 -007 17
`
`

`
`
`
`.«
`
`Title
`
`Method and System for Identifying and Processing Changes to a Network Topology
`
`Field of Invention
`
`The present invention relates generally to computer networks. 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 available 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 traffic. 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 connections 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
`
`HP No. 100081024
`
`1
`
`

`
`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 complication, the physical layout of devices and their connections
`
`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. 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
`
`I 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.
`
`
`
`HP No 100081024
`
`2
`
`

`
`Still another difficulty with existing systems is that they focus on the minutia without
`
`I\)
`
`considering the larger mapping considerations. VVhenever an individual change in the system is
`
`CD\D0O\)O\U1-J>~U~>
`
`
`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 continuously 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 assumption 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 protocol (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 lP domains. Still another limitation of existing methods is that they do
`
`not allow topological loops, such as port aggregation or trunking, and switch meshing.
`
`Summary of Invention
`
`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
`
`HP No l0O08102~l
`
`3
`
`

`
`pnd
`
`based on the changes. The nodal connections 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 converter 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 converter 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
`
`Figure l is a drawing of a typical topological bus segment for representing the connectivity
`
`of nodes on a network.
`
`Figure 2 is a drawing of a typical topological serial segment for representing the connectivity
`
`of nodes on a network.
`
`Figure 3 is a drawing of a typical topological star segment for representing the connectivity
`
`of nodes on a network.
`
`Figure 4 is a drawing of another typical topological star segment for representing the
`
`connectivity of nodes on a network.
`
`2 3 4 5 6 7 8 9 O
`
`Figure 5 is a drawing of the connectivity of an example network system.
`
`Figure 6 is a drawing of the connectivity of another example network system.
`
`Figure 7 is a block diagram of the system.
`
`Figure 8 is a flow chart of the method of the system.
`
`Figure 9 is a flow chart of the method used by the tuple manager.
`
`Figure 10 is a flow chart of the method used by the connection calculator.
`
`HP No 100081024
`
`4
`
`

`
`Figure 11 is a flow chart of the first weeding phase of the method used by the connection
`
`calculator.
`
`Figures 12a—d are flow charts of an infrastructure—building phase of the method used by the
`
`connection calculator.
`
`Figure 13 is a flow chart of a second weeding phase of the method used by the connection
`
`calculator.
`
`Figure 14 is a flow chart of the noise reduction phase of the method used by the connection
`
`calculator.
`
`Figure 15 is a flow chart of the look-for phase of the method used by the connection
`
`calculator.
`
`Figures l6a—b are flow charts of the consolidation phase of the method used by the
`
`connection calculator.
`
`Figure 17 is a flow chart of the method used by the topology converter.
`Figures 18a-b are flow charts of the morph topo phase of the method used by the topology
`
`converter.
`
`Figure 19 is a flow chart of the duplication discard phase of the method used by the
`
`topology converter.
`Figures 20a—d are flow charts of the identify different tuples phase of the method used by
`
`the topology converter.
`
`Detailed Description
`
`The system provides an improved method for creating topological maps of communication
`
`networks based. Connectivity 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.
`
`HP No 100081024
`
`5
`
`

`
`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 ofmessages 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 rnhh. A link generally refers to the connection between nodes. A segment is a link that may
`
`include a shared media connection.
`
`Figure l is a drawing of a typical topological bus segment 100 for representing the
`connectivity of nodes on a network ll0. In Figure 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
`
`
`
`HP No 10008 l02-l
`
`6
`
`

`
`100 comprises the first and second hosts 121, 122 connected to the first port 131 of the first
`
`connector 140.
`
`Figure 2 is a drawing of a typical topological serial segment 200 for representing the
`
`connectivity of nodes on the network 110. In Figure 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. Figure 2 is an example of
`
`a c0nnector—to—connector (“conn~to—conn”) relationship.
`
`Figure 3 is a drawing of a typical topological star segment 301 for representing the
`
`connectivity of nodes on the network 110. In Figure 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. Figure 3 is an example of a connector—to~host
`
`(“conn—to—host”) relationship.
`
`Figure 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
`
`Figure 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 Figure 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 topological methods of Figure 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
`
`HP No lOOO8]02—!
`
`7
`
`1 U
`
`
`
`!.I>~LA)I\)
`
`6 7 8 9
`
`

`
`
`
`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.
`Figure 5 is a drawing of the connectivity of an example network system. In Figure 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 connected to each
`
`other, either directly or indirectly, to create a fully meshed connection. In the mesh, traffic may be
`
`dynamically routed to create an efficient flow.
`Figure 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 linkis 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 connectors illustrate the multiple
`
`connectivity between nodes. Depending upon the device specifications, devices such as connectors
`may be connected via any number of connectors. As explained herein, the system resolves multiple
`
`connectivity problems by tracking port information for each connection.
`
`Figure 6 is a drawing of the connectivity of a portion of a network having three connectors
`
`171, l_72, 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
`
`HP No 100081024
`
`8
`
`

`
`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.
`
`Figure 7 shows a block diagram of the system. Figure 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. The topology database “topod ” 350 stores the current topology for
`
`use by the system. The “neighbor data” database 310 stores new tuple data retrieved by the tuple
`
`manager 300. The connection calculator 320 processes the data in the neighbor data database 310
`
`to determine the new network topology. The connection calculator 320 reduces 906 the tuple data
`
`and sends it to the reduced topology relationships database 330. The topology converter 340 then
`
`updates 908 the topology database 350 based on the new tuples sent to the reduced topology
`
`relationships database 330 by the connection calculator 320.
`
`Figure 9 shows a flow chart of one operation of the tuple manager 300, as described
`
`generally by the data gathering 902 and tuple building 904 steps of the method shown in Figure 8.
`
`The tuple manager 300 receives 910 a signal to gather tuple data. The tuple manager 300 then
`
`retrieves 912 node information of the current topology stored in the topology database 350. This
`
`information tells the tuple manager 300 which devices or nodes are believed to exist in the system
`
`based on the nodes that were detected during a previous query. The tuple manager 300 then
`
`queries 914 the known nodes to gather the desired information. For example, the connectors may
`
`maintain forwarding tables that store connectivity data used to perform the connectors’ ordinary
`
`functions, such as switching. Other devices may allow the system to perform queries to gather
`
`information about the flow of network traffic. This data identifies the devices heard by a connector
`
`and the port on which the device was heard. The tuple manager 300 gathers this data by accessing
`
`forwarding tables and other information sources for the nodes to determine such information as their
`
`physical address, interface information, and the port from which they “hear” other devices. Based
`
`on this information, the tuple manager 300 builds 916 tuples and stores 918 them in the “neighbor
`
`data” database 310. Some nodes may have incomplete information. In this case, the partial
`
`H? No 100081024
`
`9
`
`10
`
`
`
`

`
`information is assembled into a tuple and may be used as a “hint” to determine its connectivity later,
`
`based on other connections. The tuple manager 300 may also gather 920 additional information
`
`about the network or about particular nodes as needed. For example, the connection calculator
`
`320 may require additional node information and may signal the tuple manager 300 to gather that
`
`information.
`
`After the data is gathered and the tuples are stored in the neighbor database 310, the
`
`connection calculator 320 processes the tuples to reduce them to relationships in the topology.
`Figure 10 shows a flow chart of the process of the connection calculator 320, as shown generally in
`the reduction step 906 of the method shown in Figure 8. The connection calculator 320 performs a
`
`first weeding phase 922 to identify singly-heard hosts to distinguish them from multi~heard hosts.
`
`Sirigly—heard hosts refer to host devices connected directly to a connector. The connection
`calculator 320 then performs an infrastructure—building phase 924 to remove redundant connector-
`
`to—connector links and to complete the details for partial tuples that are missing information. Then,
`
`the connection calculator 320 performs a second weeding phase 926 to resolve conflicting reports
`
`of singly—heard hosts. The connection calculator 320 then performs a noise reduction phase 928 to
`remove redundant neighbor information for connector—to—host links. If clarification of device
`
`connectivity is required, the connection calculator 320 performs a “look for” phase 930 to ask the
`tuple manager 300 to gather additional data. The tuple data is then consolidated 932 into segment
`and network containment relationships. The connection calculator 320 may also tag redundant
`
`tuples to indicate their relevance to actual connectivity. These redundant tuples may still provide
`hints to connectivity of other tuples. As part of the consolidation phase 932, the connection
`
`calculator 320 creates new n~ary tuples (tuples having references to three or more tucos) for shared
`
`media segments.
`
`Figure 11 is a flow chart of the connection calculator’s first weeding process 922 for
`distinguishing singly-heard hosts. The purpose of the first weeding process 922 is to identify the
`direct connections between connectors and hosts; that is, those tuples having a first tuco that is a
`
`connector and a second tuco that is a host. The connection calculator 320 looks through the tuple
`
`list in the neighbor database 310, and for each tuple 402, the connection calculator 320 determines
`
`HP No 100031024
`
`10
`
`ll
`
`

`
`404 whether the tuple is a connector-to-host (conn-to~host) link tuple. If it is not a conn—to—h0st
`
`fx)
`
`link, the connection calculator 320 concludes 418 that it is a conn-to~conn link and processes 402
`
`the next tuple. If the tuple is a conn—to-host link tuple, then the connection calculator 320
`
`determines 406 whether the connector hears only this particular host on the port identified in the
`
`tuple. If the connector hears other hosts on this port, then the tuple is classified 416 as a multi-
`
`heard host link (mhhl) tuple.
`
`If the connector hears only the one host on the port —— that is, if the host is a singly—heard
`
`host — then the connection calculator 320 determines 408 whether the host is heard singly by any
`
`other connectors. If no other connectors hear the host as a singly—heard host, then the tuple is
`
`classified as a singly—heard host link (shhl) tuple 412 and other tuples for this host are classified 414
`
`as extra host links (ehl). Another tuple for this host may be, for example, an intermediate connector
`
`connected indirectly to a host. For example, Figure 6 shows three connectors 171, 172, 173 the
`
`first connector is connected directly to the first host 151. This connection therefore forms an shhl
`
`tuple. The intermediate connector 172 is indirectly connected to the first host 151. The tuple data
`
`indicates that the intermediate connector 172 is indirectly connected to the host and hears the host
`
`from a particular port. An extra host links tuple is created so that this data may be used later in
`
`conjunction with other extra host links tuples from devices across the network, to verify connectivity
`
`by providing hints about connections.
`
`The first weeding process also attempts to identify conflicts. If other connectors hear the
`
`host as a singly—heard host, then a conflict arises and the tuple is classified 410 as a sirigly—heard
`
`conflict link (shcl) tuple to be resolved later. This conflict may arise, for example, if a host has been
`
`moved within the network, in which case the forwarding table data may no longer be valid. Certain
`
`connectors previously connected directly to the host may still indicate that the moved host is
`
`connected. When all tuples have been processed 402 to identify singly—heard host links, the first
`
`weeding phase 922 is complete.
`
`Figures 12a-d show a flow chart of the infrastructure building phase 924 of the connection
`
`calculator 320. The purpose of the infrastructure building phase 924 is to determine how the
`
`connectors are set up in the network. The first part of the infrastructure building phase 924
`
`3 4 5 6 7 8 9
`
`HP No |0O0S102«l
`
`1 1
`
`12
`
`

`
`manufactures tuples based on the list of singly-heard host link tuples identified in the first weeding
`
`phase 922. The purpose is to identify the relationship between the connectors in the extra host links
`
`tuples and the connectors directly connected to the singl}/«heard hosts. For each singly—heard host
`
`link 420, the connection calculator 320 processes 422 each extra host link that refers to the host.
`
`In the illustration of Figure 6, a c0nn—to-Conn link tuple would represent the connection between the
`
`first connector 171 and the intermediate connector 172. An extra host link tuple would represent
`
`the indirect connection between the intermediate connector 172 and the first host 151. The conn-
`
`to—conn link tuple between the first connector 17} and the intermediate connector 172 is an
`
`example of an ehlConn—to—shhlConn tiiple. If a conn-to-conn link tuple exists 424 for the extra host
`
`link connector to the sing1y—heard host link connector (eh1Conn—to—shhlConn), then the connection
`
`calculator 320 updates 428 the tuple if it is incomplete. It is possible that the tuple data may be
`
`incomplete and a conn«to-conn link may not exist. In that case, a conn~to—conn tuple does not exist
`
`for the eh1Conn—to—shhlConn, then such a tuple is created 426.
`
`After processing extra host links for singly—heard host links, the connection calculator 320
`
`considers 430 each connector (referred to as connl) in the tuples to determine the relationship
`
`between connectors. As illustrated in Figure 6, a single connector may be connected directly and
`
`indirectly to multiple other connectors. In Figure 6, the first connector 151 is connected to the
`
`intermediate connector 171 directly and also to the third connector 173 indirectly. The third
`
`connector 173 hears the first host 151 on the same part 165 that it hears the first connector 171 and
`
`the intermediate connector 172. The infrastructure building phase 924 tries to determine the
`
`relationship between other connectors heard on the same port of connl. In a series of
`
`interconnected connectors, the connector on one end may not hear a connector on another end, but
`
`it may hear intermediate connectors, that in turn hear their own intermediate connectors. Tuples are
`
`created to represent the interconnection of conn—to—conn relationships. Based on this data, the
`
`connection calculator 320 can make inferences regarding the overall connection between
`
`connectors.
`
`For every connl, the connection calculator 320 considers 432 every other connector
`
`(conn2) to determine whether a connl—to-conn2 tuple exists. If connl—to-conn2 does not exist,
`
`U1.5U9IN.)
`
`6 7 8 9
`
`H? No l0()08l02—l
`
`13
`
`

`
`then the connection calculator 320 considers 436 every other conn—to-conn tuple containing conn2.
`
`The other connector on this tuple may be referred to as conn3. If conn2 hears conn3 on a unique
`
`port 438 and if connl also hears conn3 440, then the connection calculator 320 creates 442 a tuple
`
`for conn1—to—corm2 in the connector—to-connector links tuple list.
`
`After processing all of the connl tuples, the connection calculator 320 processes 444 each
`
`connl—to~conn2 links tuple to ensure that they have complete port data. For each incomplete tuple
`
`446, the connection calculator 320 looks 448 for a different tuple involving connl in the extra host
`
`links tupleson a different port. If a different triple is found 450, then the connection calculator 320
`
`determines 452 whether conn2 also hears the host. If conn2 does hear the host, then the
`
`connection calculator 320 completes the missing port data for conn2. If conn2 does not also hear
`
`the host 452, then the connection calculator 320 continues looking 448 through different tuples
`
`involving connl in extra host links on different ports.
`
`After attempting to complete the missing data in each of the conn—to—conn links tuples, the
`
`connection calculator 320 processes 456 each conn-to~conn links tuple. The purpose of this sub~
`
`phase is to attempt to disprove invalid conn-to—conn links. The connection calculator 320 considers
`
`45 8 connl and conn2 of each conn—to-conn links tuple