Multiplex communications – Network configuration determination
Reexamination Certificate
1999-10-28
2004-02-24
Yao, Kwang Bin (Department: 2667)
Multiplex communications
Network configuration determination
Reexamination Certificate
active
06697338
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a technique for determining a topology of a communication network.
2. Discussion of the Known Art
Physical network topology refers to the physical connectivity represented by links such as, for example, twisted wire pairs, fiber optic or wireless links that exist among elements such as switches and routers in a communication network. This topology is part of a so-called physical layer or layer-1 of a known seven-layer ISO network model standard. Determining the physical interconnections of network elements is a prerequisite to certain critical network management tasks including, e.g., reactive and proactive resource management, server siting, event. correlation, and root-cause analysis.
For example, consider a fault monitoring and analysis application running on a central Internet Protocol (IP) network management platform. Typically, a single fault in the network causes multiple alarm signals from different interrelated network elements. Knowledge of the physical interconnections among the elements is essential to discriminate secondary alarm signals, and to correlate primary signals in order to isolate the actual failure site in the network. See, e.g., I. Katzela and M. Schwarz, Schemes for Fault Identification in Communication Networks, 3 IEEE/ACM Transactions on Networking, at 753-64 (Dec. 1995). Further, an accurate map of physical interconnections in a communication network enables a proactive analysis of the impact of element and link failures. Early identification of potential failure sites capable of disrupting a large number of network users, allows a network manager to enhance the survivability of the network, for example, by adding alternate routing paths before outages occur.
Certain systems, including Hewlett Packard's Open View Network Node Manager, and IBM's Tivoli for AIX, feature an IP mapping function for discovering routers and subnets, and for generating a network layer (i.e., ISO layer-3) topology showing router-to-router interconnections and router-to-subnet relationships. But a layer-3 topology tends to ignore complex physical interconnections of layer-1 network elements such as switches and bridges that comprise one or more subnets of the network. Thus, a network manager is not fully able to troubleshoot end-to-end connectivity, or to assess the potential impact of a link or device failure in a switched network based only on layer-3 topology information.
U.S. Pat. No. 5,727,157 (Mar. 10, 1998) relates to an apparatus and method for determining a computer network topology. According to the patent, a list of network addresses heard at each port of a data-relay device in a computer network is compiled for each device. Each device acquires a source address table listing addresses heard by each port of the device. The lists are compared to determine the existence of a direct or transitive connection between selected ports on different devices, to define interconnections between the devices in the network. The patented method does not, however, contemplate the existence of multiple subnets in the network. Thus, the method may not always generate an accurate topology of physical interconnections in networks that have more than one subnet.
U.S. Pat. No. 5,933,416 (Aug. 3, 1999) and U.S. Pat. No. 5,926,462 (Jul. 20, 1999) disclose a method of determining a network topology, involving monitoring traffic received by and emitted out of devices in the network. Traffic out of the devices is correlated with traffic into the devices, and a communication path between a pair of devices is indicated when the correlation of traffic out of one of the devices with traffic into another one of the devices, exceeds a predetermined threshold. The patented methods predict with a certain probability a physical connection between two nodes, but do not confirm the existence of such a connection between the nodes, however.
U.S. Pat. No. 5,850,397 (Dec. 15, 1998); U.S. Pat. No. 5,708,772 (Jan. 13, 1998); and U.S. Pat. No. 5,606,664 (Feb. 25, 1997) relate to apparatus and methods of determining a topology of a non-heterogeneous network, using proprietary information tables associated with the network elements.
U.S. Pat. No. 5,729,685 (Mar. 17, 1998) relates to apparatus for determining the topology of an asynchronous transfer mode (ATM) network, and U.S. Pat. No. 5,684,959 (Nov. 4, 1997) discloses a method of determining a topology of a fiber distributed data interface (FDDI) network. Neither of the two patents is expandable to arbitrary networks that include bridges, switches, hubs and the like.
U.S. Pat. No. 5,297,138 (Mar. 22, 1994) relates to determining a topology of a network consisting of repeaters, concentrators and bridges, and requires significant packet content monitoring. U.S. Pat. No. 5,684,796 (Nov. 4, 1997) discloses a method and apparatus for determining and maintaining agent topology information in a multi-segment, non-heterogeneous network, and U.S. Pat. No. 5,737,319 relates to a topology discovery method applicable only to static networks and not to data networks with rapidly changing topology. None of the foregoing patents presents a practical solution for discovering a physical or layer-1 topology in a heterogeneous (multi-vendor) IP network, in which more than one subnet may exist.
SUMMARY OF THE INVENTION
According to the invention, a method of discovering a physical topology of a network having elements each of which is assigned to one of a number of subnets within the network, wherein each element has one or more interfaces each of which is linked with an interface of another element, includes generating address sets for each interface of each network element, wherein members of a given address set correspond to network elements that can be reached from the interface for which the given address set was generated, and comparing members of first address sets generated for corresponding interfaces of a given network element with members of second address sets generated for corresponding interfaces of network elements other than the given element. A set of candidate connections between one or more interfaces of the given element and one or more interfaces of another network element are determined, such that, for each candidate connection, (a) none of the members of a first address set is also a member of a second address set, and (b) the members of the first address set and the members of the second address set together represent all network elements assigned to each subnet represented by the members of the first and the second address sets.
If only one candidate connection is determined between a first interface of the given network element and a second interface of another network element, the one candidate connection is identified as an actual connection between the elements. If more than one candidate connection is determined, those connections with other network elements that are in the same subnet as the given network element are eliminated from the set of the candidate connections.
REFERENCES:
patent: 5297138 (1994-03-01), Black
patent: 5432789 (1995-07-01), Armstrong
patent: 5465251 (1995-11-01), Judd et al.
patent: 5606664 (1997-02-01), Brown
patent: 5684796 (1997-11-01), Abidi
patent: 5684959 (1997-11-01), Bhat
patent: 5708772 (1998-01-01), Zeldin
patent: 5710885 (1998-01-01), Bondi
patent: 5727157 (1998-03-01), Orr
patent: 5729685 (1998-03-01), Chatwani
patent: 5732086 (1998-03-01), Liang
patent: 5734824 (1998-03-01), Choi
patent: 5737319 (1998-04-01), Croslin
patent: 5850397 (1998-12-01), Raab
patent: 5884036 (1999-03-01), Haley
patent: 5903559 (1999-05-01), Acharya
patent: 5926462 (1999-07-01), Schenkel
patent: 5933416 (1999-08-01), Schenkel
patent: 6075776 (2000-06-01), Tanimoto
patent: 6108702 (2000-08-01), Wood
patent: 6205122 (2001-03-01), Sharon et al.
patent: 6324168 (2001-11-01), Richardson
patent: 6331985 (2001-12-01), Coden
patent: 6469987 (2002-10-01), Rijhsinghani
Breitbart Yuri
Garofalakis Minos N.
Martin Clifford Eric
Rastogi Rajeev
Seshadri Srinivasan
Lucent Technologies - Inc.
Yao Kwang Bin
LandOfFree
Determination of physical topology of a communication network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Determination of physical topology of a communication network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determination of physical topology of a communication network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3340695