ABSTRACT

Through the analysis of network topology discovery algorithm used ICMP protocol and FDB address, a novel layer topology discovery and link layer topology discovery algorithm which is suitable for campus network environment is proposed based on SNMP protocol. This algorithm can rapidly and accurately calculate the second and third floors topology of the whole pipe network.

Keywords:

Simple Network Management Protocol, Topology Discovery, Network Management

1. Introduction

Network topology is a method which is used for expression of the network logical connection relation and the physical connection relation [1] [2] [3]. Through the network topology, the network administrator can intuitively understand the operation situation of the current network, and pinpoint the network fault for isolation. Moreover, the network administrator can accurately analyze the bottleneck existed in the whole network in order to specifically reinvent the network and improve the overall performance of the network. Network topology auto-discovery technology becomes the key to build network topology. In this study, we constitute Ethernet network environment based on the campus network of many kinds of equipment in order to implement a rapid network topology discovery algorithm on the basis of the neighbor relations of routing protocol and IEEE802.1D spanning tree protocol.

2. Common Topology Discovery Methods

2.1. Using the ICMP Protocol Three Layer Topology Structure

TCP IP agreement, when the router receives the TTL field is reduced to 0 when an IP packet, the router from the proximal end to detect the source address returns the ICMP message overtime [4]. Trace route application according to the principle of link state routing between the testing point to point, and obtain from the detection source address to the destination address all through the routing between sequences. Using trace route technology, the address space of the whole network can be path detection, in order to calculate the whole network of network layer topology relationship. More successful example is the university of southern California SCAN Mercator research project development tool, the tool use trace route and ping technology, by adopting the method of heuristic conjecture construction destination address space, and use a hop count limit of UDP packets to actively probe the destination address. Because each trace route on a detection, in fact have to send three UDP packets on a network, structure of the whole network topology relations will produce a lot of network overhead.

2.2. Using FDB Address Published Structure Topology on the Second Floor

Turn FDB address published is a network link layer device (Bridges, switches, etc.) in order to rapidly and accurately forward data frames and maintenance, it shows that a MAC address is on the switch which was found on the port [5]. To the equipment of different manufacturers r & d, the format of the different item FDB address table, but contain “MAC address, port” the tuples. Through the FDB table, can’t directly find the switch the connection between the relationship, need to determine through other logical relation. Bell LAB’S Yuri Breitbart put forward by the link layer topology discovery algorithm based on FDB table, they put forward the following lemma is used to determine the connection relationship; Turn down the address of A port is published for the Fa, port B address published for Fb; Connected directly to A and B < - > FaUFb = N, And Fa∩Fb = NULL. However, using the lemma to calculate layer topology relationship needs to complete FDB table, this requires additional traffic to the network. As FDB table is updated dynamically, this requirement is difficult to implement in the actual network environment, or can only be approximate.

3. The Topology Discovery Algorithm Based on SNMP

The current network connection device is essentially belongs to can be tube type, that is, they all support the SNMP simple network management protocol [6]. Network topology information can be obtained from the MIB variables, so it can be used to compute the second and third floors of network topology relationship.

3.1. The Network Layer Topology Discovery

Gateway device of routing table ipRouteTable defines the routing information of the device, the list items related to the network layer topology discovery are: ipRouteDeSt, ipRouteIfIndex, ipRouteNextHop, ipRouteType, ipRouteDeSt record as a starting point to the device To get to the destination address range, IpRouteIfIndex record ipRouteDeSt index number of interfaces, IpRouteNextHop record interface that corresponds to the next-hop gateway address or the directly connected subnet gateway address, IpRouteType record ipRouteNextHop represented address connection relationship with the device; when ipRouteType 4, said both routers and road by the device directly connected; when it is 3, said corresponding interface connection is a subnet. According to this feature, select an activity network management workstation interfaces are subnet gateway address as seed node, adopt the undirected graph breadth-first traversal methods to detect all routing equipment, analysis of routing information network layer topology relationship can be calculated.

1) The main data structure: In the process of network layer topology discovery using two-dimensional chain table structure to store the routing data collected information. Involves the main data structure is as follows:

a) Struct IPAddrEntrInfo//Device address information

{char ipAdEntAddr[16];//On the interface definition ofIPv4 addresses

char ipAdEntNetMaSk[16]; //The interface with the corresponding subnet mask value

};

b) Struct IPRouteEntrInfo//Equipment routing information

{char ipRouteDeSt[16];//The purpose of the device to the address

char ipRouteNextHop[16];//To a specific destination address required after the next-hoprouter address or the connected subnet gateway address

int ipRouteType;//Connection type: 3-connected subnet, 4 to connect the router

};

c) Struct RouterNode//Routing nodes

{char router IdentifyAddreSS[16];//A mark of router address

IPAddrEntrInfo *info_ipAd;//Address information

IPRouteEntrInfo *info_ipRo;//Routing information

};

2) Algorithm implementation:

Algorithm defined: OutBoundAddreSSSetS representation and export the router directly connected to the next-hop router address collection, using it to limit the scope of the network layer topology discovery, in order to avoid because of the next-hop router with the tube field equipment passwords in the same communication program to expand on the network; CommunitySnmp ReadLiSt said read password capacity table objects; The router address queue nexthopQueue said to be found; router SeedRouter said seeds; Gather-Router- InfoAll function is used to collect the data, routers which returns RouterNode types of nodes; SnmpPing function using SNMP Get operation primitives, implement test specified passwords, equipment of some combination of communication protocol version can response. The network layer topology discovery algorithm implementation process is as follows:

a) Reads the topology discovery configuration information from a configuration file, initialize the object as follows: OutBoundAddreSSSetS, SeedRouter, community SnmpReadLiSt, adding SeedRouter into an empty queue nexthopQueue.

b) If nexthopQueue to empty the queue, then the turn (g); Otherwise remove nexthopQueue squadron head node, using community SnmpReadLiSt chain table as input, call SnmpPing passwords and test out the response of communication protocol version number.

c) If (b) passwords, hasn’t been able to find out the response in the communication process in two different conditions:the tested device address for SeedRouter, turn (i); Be tested device address for SeedRouter, turn (b).

d) Using (b) test the passwords, and successful communication protocol version as input parameters and device address, call GatherRouterInfoAll collect information about the address of the router info_ipAd info_ipRo and routing table information, and returns the node as a two-dimensional chain table of longitudinal node concatenated; at the same time to the address information such as linked lists as a horizontal nodes are concatenated.

e) Analysis (d) of the data collected by the node’s routing table. If ipRouteType = 4, record the router and the corresponding ipRouteNextHop value represented by the equipment directly connected, at the same time to test whether the value exists in the collection OutBoundAddreSSSetS (to avoid application expand network) and lateral address information list info_ipAd (solve the problem of different address can represent the same router, avoid duplication of access equipment); If doesn’t exist, then add it to nexthopQueue queue. If IpRouteType = 3, record the router is connected to a subnet directly.

f) Repeat (b)-(e) operation.

g) Analysis lateral address information list info_ipAd, run after the OSPF routing protocol such as due to choose the shortest path may not be recorded in the MIB connection relationships: if two interfaces with the corresponding IP address mask do equals the network address after operation income, is a direct link between them is or is connected between the same subnet.

h) According to the transverse address information list info_ipAd calculate the whole pipe network in all possible set of host addresses, preparing for the link layer topology discovery.

i) End of the algorithm.

Different router devices may support different public MIB. The currently supported MIB group besides ipRouteTable, as well as ipCidrRouteTable and ipForWardTable, so collect routing information needs to be the first test which a set of the equipment support MIB variables.

3.2. The Link Layer Topology Discovery

Spanning tree protocol is a network of the link layer protocol, which is used to ensure that the network interconnection between equipment. There is no physical loop running the Spanning tree protocol bridge equipment by regularly sends bpdus in bridge protocol data unit message to dynamic maintenance of acyclic tree topology.

According to IEEE802.1D-2004, in the tree topology, the root is called the root bridge, and the one and only one root Bridges. The root bridge has the highest priority, it forward data frames on all of its ports. The root bridge is determined, the rest of the bridge each port for its record received total root path cost, with a minimum cumulative root path cost port for the root of the bridge port. The specified port number on the bridge is refers to the port; it can be sent from the root bridge direction Data frame is forwarded to the connected network segment, and the ability to connect the network segment of forward data frames to the root bridge. The port specified bridge refers to from the connection to the same network segment of the bridge in the choice of a forward data frames to the root bridge. The root bridge, it all ports designated bridge for the bridge itself; Other bridge root port specified bridge, is directly connected with the port Bridges the specified port specified bridge is the bridge itself. According to the definition of the specified bridge Known, if two bridge has a direct relationship between a pair of port, so the two ports designated bridge the same; If the at least one of the two ports for the blocking state, so the connection between the two ports is the backup link. According to the rules, which can calculate the link layer topology relationship.

1) The main data structure: In the link layer topology discovery, in addition to using part of the data structure of network layer topology discovery, also defines the following data structure, is also the use of two-dimensional chain table data structure to store the nodes.

a) Struct Dot1dStpPortEntrInfo//Spanning tree information

{int dot1dStpPortState;//Port state

char deSignaBridge [24];//Port specified bridge

};

b) Struct Dot1dTpFdbEntrInfo//Turn address published

{char dot1dTpFdbAddreSS[18];// The MAC address

int dot1dTpFdbPort;//Corresponding index of port

int dot1dTpFdbStatuS;//State of the MAC address

};

c) Struct IEEE8021D//The bridge node

{int dot1dStpRootCOSt;//The cumulative root cost

int dot1dStpRootPOrt;//The root port

Dot1dStpPortEntrInfo *info_Stp;//Spanning tree information

Dot1dTpFdbEntrInfo *info_fdb;//Address published information

};

2) Algorithm implementation:

In order to describe the link layer topology discovery algorithm, first of all objects are defined as follows: dot1dCompatibleAgentS queue said compatibility of the spanning tree protocol layer equipment collection; ipSetS said webmaster to address space provided by the link layer topology discovery collection; SnmpPingPoSix functions and SnmpPing function are similar, the difference is that the Snmp-PingPoSix using the specified OID (1. 3. 6. 1. 2. 1. 17. 2. 1. 0) and test equipment in a multithreaded way will be able to SNMP operation response; GatherBridgeInfoAll function is used to collect the bridge data, the function returns IEEE8021D types of nodes. Link layer topology discovery algorithm process is as follows:

a) Initialize dot1dCompatibleAgentS queue and ip-SetS collection is empty; Read from the configuration file link layer topology discovery address space, and assign a value to ipSetS.

b) Will set ipSetS and set hoStSetS intersection operation, as a result, save to ipSetS.

c) If ipSetS is empty, the turn (h); Otherwise using Snmp-PingPoSix function, the object of the ipSetS response test,and the response is to save the address to dot1dCompatibleAgentS queue.

d) Ifdot1dCompatibleAgentS is empty, the turn (f); Otherwise remove dot1dCompatibleAgentS QA team head, use GatherBridgeInfoAll functions collect QA Info_Stp spanning tree information and address info_fdb published information, and returns the node as a two-dimensional vertical node concatenated list, at the same time Info_Stp concatenated list as lateral node, etc.

e) Repeat (d) operation.

f) Spanning tree information list and address forwarding chain table to calculate the connection relationship. Two choices from the spanning tree list node, and should meet the following conditions: belong to different equipment; specify the bridge; ports enabled and in the forwarding state; the two nodes respectively belong to the specified port and not the root bridge port; node connection flag bit is 0. Remember A root port node represents the root bridge, on behalf of another node B, query interface information list, calculate the definition of A IP address the MAC address of the interface. In B address forwarding bracelet query the MAC address appears in the table on which port; If you can find the corresponding port, record under “equipment.Port-equipment.Port” precise connection relations; Accurate port number, otherwise can’t record the B to negative number to represent the connection relationship. Connect A and B of two nodes logo position is 1.

g) The spanning tree information linked list of nodes connection reset, spanning tree information list again, take out two nodes conform to the following conditions: belong to different equipment; specify the bridge; the two nodes at least one in the blocking state; node connection flag bit is 0. The record as the backup link, between the two nodes and node connection flag bit to 1.

h) End of the algorithm.

3.3. The Topology Discovery Results

Using this algorithm, to drag and drop the primitive topology adjustment operation, mapped the network layer in University of Science and Technology LiaoNing campus network topology and part of the link layer topology as shown in the following two figure: network layer topology can be found that the ring connection (Figure 1), the link layer topology can find backup link (Figure 2).

4. Conclusion

Network topology discovery is the basis of the visualization of network management; this algorithm uses the SNMP protocol to realize the rapid discovery of network layer and link layer topology structure. The topology calculated by this algorithm is accurate and efficient, which has been checked with success on the experimental results.

Cite this paper

Zhang, X.L. (2018) An Optimization Algorithm of Network Topology Discovery Based on SNMP Protocol. Journal of Computer and Communications, 6, 104-111. https://doi.org/10.4236/jcc.2018.61011

References