CN1558615A - A physical network topology discovery system and method thereof - Google Patents

Abstract

The invention relates to a physical network topology finding system for computer network topology and general purpose MIB information and method thereof, which comprises, determining the IP address range of the administration domain, determining the active IP address aggregation in the network address range, determining subnet quantity, corresponding subnet number and subnet mask, mapping the IP address aggregation, obtaining the discovered address transferring table information belonging to the switchboard of the subnet, obtaining the connection between the ports of the switchboards. determining the connection between the host computer and the port of the switchboard. The system comprises: a determining device for the apparatus, an information gathering device, an information processing device, a topology display device. The invention is utilized to a variety of IP network( such as IPV4, IPV6, and IP telecommunication network).

Description

A physical network topology discovery system and method thereof

technical field

The invention relates to computer network topology discovery and general MIB (management information base) library information, in particular to a physical network topology discovery system and method thereof, physical topology discovery based on such information and general topology discovery technology.

Background technique

Switches have become key devices in modern computer networks. For network administrators, it is extremely important to be able to obtain network topology information at any time. It can help determine link continuity, perform error correlation analysis, and place servers in the most appropriate locations.

The traditional topology discovery technology only discovers the logical network connections of the three layers, that is, discovers the connections between routers and subnets. This technology is obviously not suitable for the environment of switches. Because the routing table of the router stores the information of the adjacent entity (referring to the router), the general address forwarding table of the switch cannot clearly provide the information of the adjacent entity (referring to the switch). Of course, some manufacturers provide specific protocols to support device discovery, such as CISCO's CDP protocol. But usually the devices in the LAN do not come from the same manufacturer. In such a heterogeneous network environment, new algorithms are needed to support the topology discovery of the heterogeneous network. The information basis of these algorithms must be supported by all manufacturers. common standards.

Contents of the invention

The purpose of the present invention is to provide a method for discovering physical network topology, which can accurately discover the layer-2 physical network topology structure based on the limited information provided by the heterogeneous network environment, including the connection between switch ports and switch ports, the connection between switches and The connection of the host, the connection of the switch and the HUB, the connection of the host and the HUB. At the same time, the algorithm can be applied to the VLAN environment.

A layer-2 network topology discovery method based on general MIB database information (in this document, a layer-2 network topology is equivalent to a physical network topology, and the two can be interchanged). The invention discovers the topological structure of the two-layer network through three stages of equipment determination, information collection and information calculation through self-designed algorithm. The present invention is characterized in that the number of ICMP messages that need to be sent before the general algorithm collects network information is reduced from O(n ² ) to O(n), which reduces the occupation of network bandwidth and improves the speed of system operation; At the same time, the invention can discover the HUB equipment transparent to the switch in the network, so as to give the exact physical connection instead of the logical connection. The invention can be implemented in various IP networks (IPV4, IPV6, IP telecommunication networks, etc.), and is applicable to environments without VLANs and environments configured with VLANs and each VLAN corresponds to a spanning tree.

The two-layer physical network topology discovery method based on the MIB information defined by the general RFC includes three stages of device discovery, information collection and topology calculation to achieve the goal. The algorithm we propose is based on the MIB information defined by the general RFC, and is suitable for heterogeneous Network, through calculation, the connection relationship between switch port and switch port, switch port and HUB, switch port and host, host and HUB can be given in the layer-2 network;

The algorithm we proposed, the preprocessing process of collecting information before the algorithm runs, the amount of ICMP information sent is O(n), and the theoretical basis of the algorithm is about the division of uplink ports and downlink ports.

Firstly, we introduce our proposed algorithm based on Layer 2 topology discovery

1 definition

Forwarding table: port j of switch S _i stores the source MAC received by the port during the switching process

Address set, denoted as F(S _i , j);

Complete forwarding table: The complete forwarding table of port j of switch S _i means that F(S _i , j) contains all

A collection of device MAC addresses that the port can see;

Leaf switch: In the case of a complete forwarding table, if a switch exists and only one

A port whose forwarding table contains the MAC addresses of other switches;

Flag node: When the host running the algorithm is a member of the subnet to be discovered, the host is called

Sign node; otherwise, the router connected to the subnet is called a sign node;

Leaf port of the switch: If the forwarding table F(S _i , j) of port j of switch S _i is in complete condition

In the case does not contain the MAC address of any other switches or marked nodes, then

is called the leaf port of the switch;

Uplink port: the port whose MAC address of the marked node appears in the forwarding table corresponding to the port;

Downlink port: the port corresponding to the port does not appear in the forwarding table that marks the MAC address of the node;

2 theorems

(n＝1，2….，N，N为交换机S_k的端口计数，且n不等于上行端口集合中端口的编号)，则S_i的端口j与S_k的上行端口1直接相连。例如，图2中S3的上行端口为1，下行端口为2，3，满足F(S2，2)＝F(S3，2)∪F(S3，3)∪{S3}，因此判定S2端口2与S3上行端口1相连。If the switches S _i and S _k satisfy:

(n=1, 2..., N, N is the port count of switch S _k , and n is not equal to the port number in the uplink port set), then port j of S _i is directly connected to uplink port 1 of S _k . For example, in Figure 2, the uplink port of S3 is 1, and the downlink port is 2, 3, which satisfies F(S2, 2) = F(S3, 2)∪F(S3, 3)∪{S3}, so it is determined that S2 port 2 Connect to uplink port 1 of S3.

We propose Algorithm 1, the theoretical calculation basis of the algorithm is: the condition that the downlink port of switch A is directly connected with the uplink port of switch B is that the downlink port forwarding table of switch A is exactly equal to the union of the non-uplink port forwarding table of switch B And on B itself. 3 Algorithm-1 (applicable to switches directly connected to switches instead of connected through HUB)

1) PING all switches in the subnet

Figure 3 shows the direction of the PING message flow;

2) Read the address forwarding table of each switch in turn;

3) Construct the uplink port and downlink port set of each switchboard from the address forwarding table of each switchboard, and put all switch nodes in the subnet into the queue to be detected simultaneously;

4) Push the leaf switch nodes into the queue to be generated in turn (this queue is a first-in-first-out queue), and remove the leaf switch from the queue to be detected at the same time;

5) Take out a node from the queue to be generated to make it a node to be detected;

6) Check whether the MAC address of the node to be detected is included in the address forwarding table of each port in the downstream port set of other nodes, if it occurs but the number of nodes in the table is greater than 1, then delete this entry, if only the detection node occurs, Then the port number of the port corresponding to this item is directly connected to the uplink port of the node to be detected, and this port is removed from the downlink port set of the current node at the same time;

7) Every time a node is traversed, if the downlink port set of this node is empty, the switch node is pushed into the node queue to be generated, and removed from the queue to be monitored;

8) If the queue to be generated is not empty, repeat 6 to 8. The Algorithm 2 we give can find the situation that multiple switches are connected through HUB, and the characteristic is that the downlink port forwarding table of a certain switch is equal to the union of the non-uplink port forwarding tables of several switches and then merged with these switches themselves . 4 Algorithm-2 (for the improvement of Algorithm-1, it can be applied to the situation where switches are connected through HUB, compatible with Algorithm 1, but the complexity is slightly larger)

1) Find out all switch sets;

2) PING all switches;

3) Obtain the forwarding tables of all switches, and judge the uplink port and downlink port;

4) All leaf switch nodes are pushed into the queue to be generated, and all non-leaf switches are pushed into the queue to be detected;

5) Take out a detection node in the queue to be detected, and detect its downlink ports one by one

CASE1: If a downlink port only contains a node in the queue to be generated but not a node in the queue to be detected, connect the downlink port directly to the uplink port of the node in the generation queue, and transfer the downlink port from If the node has no downlink ports after removal, push this node into the queue to be generated; remove the corresponding node in the generation queue connected to it;

CASE2: If its downlink port contains several nodes in the queue to be generated, but does not include nodes in the queue to be detected, then this downlink port is connected to the uplink ports of these queues to be generated through a HUB, and at the same time, the This downlink port is removed from the forwarding table. If there is no other downlink port after removal, push this node into the queue to be generated; remove the corresponding node in the generation queue connected to it;

CASE3: If its downlink port contains a node that is not a queue to be generated, then detect the next downlink port;

6) After detecting all downlink ports, if the node still has a downlink port, this node is re-pressed into the tail of the queue of the node to be detected;

7) Repeat steps 5 and 6 until the queue of nodes to be detected is empty (indicating completion),

Figure 4 shows a subnet environment including a HUB. The topology discovery process using this algorithm is as follows:

The forwarding table behavior of each downlink port

F(S1, 2) = {S2, S5, S6}

F(S1, 3) = {S3, S4, S7}

F(S2, 2) = {S5, S6}

F(S3, 2)={S7}

Remember that the queue to be generated is Q, and the queue to be detected is T, then the initial

Q={S5, S6, S7, S4}

T = {S1, S2, S3}

The first step is to take out S1, detect F(S1, 2), F(S1, 3), both are CASE3, then push S1 into the end of the T queue, at this time

Q={S5, S6, S7, S4}

T = {S2, S3, S1}

The second step is to take out S2, detect F(S2, 2), it is CASE2, then add a HUB between S2 port 2, S5 port 1 and S6 port 1, remove S5 and S6 from Q, and delete the port of S2 at the same time 2's downlink port forwarding table, after deletion, there is no downlink port forwarding table in S2, so S2 is pushed into Q, at this time

Q={S7, S4, S2}

T = {S3, S1}

The third step is to take out S3, detect F(S3, 2), it is CASE1, directly connect S3 port 2 to S7 port 1, remove S7 from Q at the same time, and delete the downlink port forwarding table of S3 port 2, after deletion, S3 There is no downlink port forwarding table, push S3 into Q, at this time

Q={S4, S2, S3}

T={S1}

The fourth step is to take out S1, detect F(S1, 2), it is CASE1, directly connect S1 port 2 to S2 port 1, remove S2 from Q, delete the downlink port forwarding table of S1 port 2, because S1 is still There is a downlink port, so continue to detect the next downlink port forwarding table of S1, at this time

Q = {S4, S3}

The fifth step is to detect F(S1, 3), which is CASE2, connect S1 port 3, S4 port 1, and S3 port 1 through HUB, remove S4 and S3 from Q, delete the downlink port forwarding table of S1 port 3, After deletion, there is no downlink port forwarding table in S1, and S1 is pushed into Q. At this time

Q={S1}

T = empty set

end of algorithm

In order to achieve the required purpose, this solution is based on the proposed algorithm, through three stages of device discovery, information collection and topology calculation to achieve the required purpose, specifically including the following steps: (as shown in Figure 5)

To determine the IP address range of the management domain, it can be given manually by the network administrator, or can be obtained automatically by querying the gateway router, and can be obtained by querying the ipRouteTable of the gateway router. At the same time, query the port number of the router to determine whether there is a one-armed route

2. Determine the set of active IP addresses in the network address range obtained in step 1, and realize by pinging all IP addresses;

3. Determine the number of subnets and the corresponding subnet number and subnet mask, and obtain them by accessing the ipAddrEntry of the router;

4. Map the active IP address set obtained in step 2 to a specific physical device, and instantiate the corresponding device;

Send an SNMP GET message to each active IP address. If the device corresponding to the IP address does not implement BRIDGE-MIB, the device corresponding to the IP address is a host; if the device corresponding to the IP address implements BRIDGE-MIB, and its ipForwarding is 0 , the device corresponding to the IP address is a switch; if the device corresponding to the IP address implements BRIDGE-MIB, and its ipForwarding is 1, the device corresponding to the IP address is a router; multiple IP addresses may correspond to the same physical device, you can Avoid mapping these IP addresses to different devices by looking at the IP address table for that device;

5. For a certain subnet, ping all the switch devices belonging to the subnet obtained in step 4 from the host running topology discovery;

6. Obtain the address forwarding table information of the switch belonging to the subnet found in step 4;

7. Analyze and calculate the information obtained in step 6 through the given algorithm to obtain the connection between the switch port and the switch port (there may be a switch-HUB-switch connection);

Eighth, according to the information in the switch address forwarding table, determine the connection between the host and the switch port, including the switch-HUB-host connection;

The present invention has the advantages of: using the MIB information defined by RFC supported by each manufacturer as the basis of the topology discovery algorithm, which can be applied to heterogeneous networks; abandoning the general two-layer topology discovery requirement for all forwarding tables to be complete, the algorithm The collected information can ensure that the algorithm can accurately discover the topology, greatly reducing the number of PING operations required to meet the complete requirements of the forwarding table; it can accurately locate the connection between ports, rather than the simple logical connection between devices ;Can discover HUB devices transparent to switches; at the same time, this algorithm can also be applied to the environment where VLANs are configured and each VLAN corresponds to a spanning tree;

Description of drawings

Figure 1 is a typical subnet environment diagram.

Figure 2 is an example diagram of the theorem.

Figure 3 is a flow chart of ICMP messages.

Fig. 4 is a subnet environment including a HUB, and a flow chart of using this algorithm for topology.

Fig. 5 is a flow chart of the method for discovering the topology of the physical network according to the present invention.

FIG. 6 is a diagram of the physical network topology discovery system of the present invention.

Figure 1 is an example of each term for a typical subnet environment

Among them, S1, S2, S3, S4, and S5 are switches, M is the management node, that is, the node where the algorithm runs, and M is also the symbol node of the subnet. The uplink port of S3 is port 1, and the downlink ports are port 2 and port 3. S2, S4, and S5 are leaf switches. Port 2 of S4 and port 2 of S2 are leaf ports of switch S4 and switch S2 respectively.

M is a management station, which is also a symbol node; S _k (k=1..5) is a switch, the number next to the switch represents the port number, and Host represents the host.

Figure 2 is an example of the theorem

In the figure, the uplink port of S3 is 1, and the downlink port is 2, 3, satisfying F(S2, 2) = F(S3, 2)∪F(S3, 3)∪{S3}, so it is determined that S2 port 2 and S3 Uplink port 1 is connected.

The forwarding tables of switches S2 and S3 are as follows

F(S2, 2) = {S3, S5, S6}

F(S3, 2)={S5}

F(S3,3)={S6} satisfies F(S2,2)=F(S3,2)∪F(S3,3)∪{S3}, so it is determined that S2 port 2 is connected to S3 uplink port 1.

Figure 3 is the flow of ICMP messages

Among them, the dotted arrow is the ICMP request message flow, and the solid line arrow is the ICMP response message flow

Figure 4 is an example of Algorithm 2 network environment

In the figure, there are a management station and a symbol node M, a switch S _k (k=1..7) and two HUBs connected to the switches.

Detailed ways

The prerequisites for the implementation of the program are

(1) Each switch is configured with an IP address, all of which are manageable, and all of them are implemented

BRIDGE-MIB defined by RFC1213-MIB and RFC1493;

(2) The host where the algorithm is running is installed with SNMP agent

(3) Both the active switch and the host respond to the PING message

The implementation system can be divided into four devices:

(1) Equipment determination device;

(2) Information collection device;

(3) information processing device;

(4) Topological information database;

(5) Topology display device;

Figure 6 shows the interrelationships of the five devices. The device determining means includes determining the IP address range of the management domain, determining the set of active IP addresses, collecting device information and instantiating each physical device. The MIB information to be queried includes ipRouteTable, ipAddrTable, sysDescr, ifTable, ipForwarding, dotldBaseType, etc. The final result of the device is to give a set of switches, a set of routers, and a set of hosts active within a specific IP address range, and instantiate corresponding devices.

The information collection device collects the information required by the algorithm through SNMP messages. Before collecting information, it is first necessary to send PING messages to all switches in a given subnet to fill the forwarding table of the corresponding switch. The MIB information to be queried for information collection is dotldTpFdbTable.

The information processing device includes an algorithm analysis calculation process and an information storage process device. The information processing process adopts the algorithm given by us to obtain the physical connection information between switch ports, switches and HUBs, and switches and hosts through the analysis of uplink ports, downlink ports and their forwarding tables. The premise of the information storage process is to design the database interface, and the designed database should enable the topology display device to obtain topology information simply and comprehensively. Through the database interface, the separation of information calculation and display is realized at the same time.

The information storage process is responsible for storing the results of the algorithm analysis into the database.

Topology information database; store topology information data;

The topology display device includes obtaining the topology information of the database, and performing topology display according to the topology information. The topology display can adopt different display styles according to the user's preference. But no matter which topology display method is used, the display is always independent of the calculation of topology information.

Wherein, the device determination device is connected to the information collection device, the information collection device is connected to the information processing device, the information processing device is connected to the topology information database, the topology information database is connected to the topology display device, and the topology display device is connected to the equipment determination device.

Claims (6)

1. A Layer 2 physical network topology discovery method based on MIB information defined by general RFC, including three stages of device discovery, information collection and topology calculation to achieve the goal. It is characterized in that the algorithm we propose is based on the MIB defined by general RFC Information, suitable for heterogeneous networks, can give the connection relationship between switch ports and switch ports, switch ports and HUBs, switch ports and hosts, and hosts and HUBs in a layer-2 network through calculation; 2. The method for discovering the topology of a physical network according to claim 1, characterized in that, in the preprocessing process of collecting information before the operation of the algorithm, the amount of ICMP information sent is O(n), and the theoretical basis on which the algorithm is based is about uplink port and downstream port division. 3. The method for discovering the topology of a physical network according to claim 1, the algorithm 1 proposed by us, is characterized in that the theoretical calculation basis of the algorithm is: the condition that the downlink port of switch A is directly connected to the uplink port of switch B is that switch A The downlink port forwarding table of switch B is exactly equal to the union of the non-uplink port forwarding tables of switch B and then merged with switch B itself. 4. According to the method for discovering the topology of a physical network according to claim 1, the algorithm 2 we provide can discover the situation that multiple switches are connected through HUBs, and it is characterized in that the downlink port forwarding table of a certain switch is equal to several switches The union of the non-uplink port forwarding tables is then merged on the switches themselves. 5. A method for discovering a physical network topology, the specific steps of which are as follows: 1. Determine the IP address range of the management domain, which can be given manually by the network administrator, or can be obtained automatically by querying the gateway router, by querying the ipRouteTable of the gateway router, and querying the port number of the router at the same time to determine whether there is a one-armed route; 2. Determine the set of active IP addresses in the network address range obtained in step 1, and realize by pinging all IP addresses; 3. Determine the number of subnets and the corresponding subnet number and subnet mask, and obtain them by accessing the ipAddrEntry of the router; 4. Map the set of active IP addresses obtained in step 2 to specific physical devices, instantiate the corresponding devices, and send SNMP GET messages to each active IP address. If the device corresponding to the IP address does not implement BRIDGE-MIB, the The device corresponding to the IP address is a host; if the device corresponding to the IP address implements BRIDGE-MIB, and its ipForwarding is 0, then the device corresponding to the IP address is a switch; if the device corresponding to the IP address implements BRIDGE-MIB, and its ipForwarding is 1, the device corresponding to the IP address is a router; 5. For a certain subnet, ping all the switch devices belonging to the subnet obtained in step 4 from the host running topology discovery; 6. Obtain the address forwarding table information of the switch belonging to the subnet found in step 4; Seventh, the information obtained in step six is analyzed and calculated by the given algorithm to obtain the connection between the switch port and the switch port; Eighth, according to the information in the switch address forwarding table, determine the connection between the host and the switch port, including the switch-HUB-host connection. 6. A physical network topology system, comprising: (1) device determining means, including determining the IP address range of the management domain, determining the set of active IP addresses, collecting device information and instantiating each physical device; (2) information collecting device, collects the required information of algorithm by SNMP message; (3) Information processing device, including algorithm analysis and calculation process and information storage process device; (4) topology information database; store topology information data; (5) Topology display device, including obtaining database topology information, and performing topology display according to the topology information; it is characterized in that the device determination device is connected to the information collection device, the information collection device is connected to the information processing device, and the information processing device is connected to the topology information database , the topology information database is connected to the topology display device, and the topology display device is connected to the device determination device.

Images