- 1 -
An Algorithm of Real-time Network Topology Discovery
for Network Situation Awareness
Abstract
For network situation awareness system, the importance of real-time network topology discovery lies in
providing a platform displaying real-time network situation. In this paper, an algorithm of real-time
network topology discovery based on SNMP and several techniques are proposed including confirmation
of network device’ activity, distinguish of network device’s type, storage and disposal of network
topology information and so on.. In the given experiment environment, the algorithm is validated to
prove that it is feasible and accurate.
Keywords: network situation awareness system；network topology；real-time discovery
1 Introduction
Network situation awareness is a relatively new concept. At present, the number of individuals and
institutions researching on it is very small. There is much expatiation on concept, research status and
key techniques about network situation awareness in the Reference [1]. According to the description of
Reference [1], network situation awareness means that in large network environment it is able to
acquire, understand and display all kinds of security factors that may change network situation and then
to forecast development trend of network situation. Situation visualization is an important part in
network situation awareness system. It can show some security messages to decision-makers clearly.
These security messages include situation evaluation results, threat evaluation results and so on. So,
situation visualization can help decision-makers understand current network situation more clearly on
the whole.
The research on situation visualization[2] usually includes log data visualization, flux data
visualization, security event visualization and so on. Though network topology discovery has been
studied for many years, it is still new at the situation visualization aspect. For situation visualization,
network topology is a situation display platform. It can not only display network link structure but also
show the integrated information of network situation. When network has a failure, it could help us
ascertain the original location of the failure. When network suffers virus infection or network attacks,
administrators can know the damage situation by the integrated information on the topology map and
find some suitable methods to control the situation.
Because network situation awareness system is required to be able to acquire real-time or nearly
real-time network situation information, this determines that the network topology must have real-time
detection capability. Only in this way, we can meet the requirement of real-time display of situation
visualization. The paper will mainly discuss the contents of this area.
2 Topology Discovery’s Related Work
Overseas, CAIDA (the Cooperative Association for Internet Data Analysis) has developed Skitter
system which is based on traceroute and integrate BGP table. The system can detect link relationship
between network nodes. Cornell University has developed Octopus system[3]. The system integrated
many topology discovery methods, such as SNMP, traceroute, Heuristic guess and so on. It is designed
for topology discovery in the region or backbone network. Institute of Information Science, College of
Engineering in University of Southern California has designed a topology discovery
prototype—Mercator[4]. The prototype makes use of hop-by-hop feedback provided by some tools like
traceroute to find IP addresses during the process of network topology and construct network topology
- 2 -
map. Although many new routers no longer respond to the traceroute packets, the method still achieves
gratifying results on the present Internet. In addition, Bell Labs are being engaged in the research on
backbone network topology discovery. HP, IBM, Cisco and other enterprises are being engaged in the
research on LAN network topology discovery and have developed OpenView, Tivoli, Cisco Works
2000 and other products.
At home, network topology discovery start late. The domestic network topology discovery is
mainly based on the SNMP protocol and limited on the LAN or a management region network. For
instance, D. H. Xu, professor of Shanghai Jiao Tong University, adopts a method of constructing
network topology map with MIB-II and proposes a new algorithm to make the complexity of the
algorithm decline to 2 powers of the accessed router number. Xu points out that it is the lowest possible
index for network topology discovery based on the MIB- [5]. Information Engineering University, Ⅱ
provided by 863 Program, proposes an improved method that makes use of SNMP protocol to acquire
large-scale IP heterogeneous network topology structure. In addition, they also find in the practical tests
that some routers don’t respond intermittently and some target addresses are subnet numbers. At last,
they put forward the corresponding solutions by analysis [6]. Xi'an Jiao Tong University describes a
network topology discovery method in the National 863 High-tech Research and Development
Program[7]. The method makes use of SNMP protocol and combines data sheet information of MIB- Ⅱ
with data sheet information of Bridge-MIB. On the aspect of Internet topology exploration, Harbin
Institute of Technology funded by the Ministry of Information Industry researches into network
topology discovery in the Internet router level. The system designed by them mainly makes use of
ICMP and UDP protocol supported by routers to actively explore the Internet. It can describe network
topology structure dynamically and analyse network performance according to the changes in flow.
Their research results provide a technique platform which could help strengthen network management
in the macro, improve network efficiency and prevent large-scale network attacks[8]. Beijing
University of Aeronautics and Astronautics put forward a practical method of IPv6 backbone network
topology discovery in the subject of national basic research planning project. The method refers the
IPv4 backbone network topology discovery algorithms and strategies.
According to the current research of network topology discovery, most people only study network
topology discovery algorithm. Few institutions or organizations have applied network topology
discovery into network management. And the majority of network topology discovery researches are
static and not real-time. Real-time network topology discovery will be a new research direction for
network situation awareness system. It will enrich the modes of situation visualization.
3 Network Model and Topology Discovery Principle
A typical Ethernet network structure is showed as Figure 1. In the chart, R is the exit router. A is
the management computer. S1 to S5 are switches. P1 to P8 are personal computers. Here, we will
regard routers, switches and personal computers as network devices.
Now, there are many network topology discovery methods. But the method based on the SNMP
protocol is the most widely used. Most network devices support the SNMP protocol. Agents in these
network devices manage MIB (Management Information Base) defined by RFC (Request For
Comments). We can obtain network topology discovery information by accessing MIB with the SNMP
protocol. Now, MIB related to network topology discovery are mainly MIB-2 and bridge-MIB and
bridge-MIB mainly exists in the switches.
For router R, we can access its routing table with the SNMP protocol to obtain some related
information of network topology discovery, such as interface index of device itself, IP address of each
interface, IP
- 3 -
Figure 1: Typical Ethernet Network Structure
address of next hop, subnet mask address of each interface and so on. Description on the network
by a single router is partial, not the whole. But we can figure out IP-level topology structure of some
particular network by combining and analysing routing tables of all the routers in the whole network.
Firstly, we can create router queues and subnet queues which will be traversed and take a certain router
in the target network as a starting point. Secondly, we will adopt BFS(Breadth-First-Search) strategy to
detect all the routers in the network. At last, we can figure out IP-level topology structure of the target
network.
For switch S1, we can access its ARP(Address Resolution Protocol) table and MAC address table
with the SNMP protocol to obtain IP addresses of network devices linked to the switch. The type of the
network devices is mainly PC, such as P1 and P2. Other network devices are routers or switches, such
as S2. Above all, we must ascertain the activity of these network devices. If these network devices are
running, we will go on to access them with the SNMP protocol and distinguish these network devices’
type. If network devices accessed are switches or routers, the above steps will be repeated. Accessing
will not stop until network devices accessed are PC. We can figure out physical topology structure of
the target network through the above steps.
4 Real-time Network Topology Discovery Algorithm and Techniques
Algorithm Description
The algorithm uses network topology discovery method based on SNMP and several topology
discovery techniques to carry out real-time topology discovery. These techniques include judgment of
network device’s activity, distinguish of network device’s type and storage and disposal of network
topology information. At present, the algorithm is mainly used in the real-time physical topology
discovery. The algorithm flow chart is showed as Figure 2.
Key Techniques
Judgment of Network Device’s Activity
Judgment of network device’s activity is an important step in real-time discovery. If network
device’s activity is not decided, real-time discovery can’t continue. Usual method of judgment is to
send ICMP request messages (ping). Now personal firewalls are installed in the majority of personal
computers and these firewalls don’t allow ICMP request message through them out of security. Then
manager can’t determine whether personal computers are active or not. Against the condition, a new
judgment method that sends ARP request packets is put forward.
- 4 -
Start
End
According to table ARP and table MAC,
get network devices’ IP address linked to a
switch
Whether target devices are in the
same subnet with the switch or not
ARP detection
Whether target devices
are active or not
Distinguish network devices’ type
Access active network devices for related
topology information, store them into
the database and dispose them
Whether topology discovery is
stopped or not
Another detection
Y
Y
N
Y
N
N
Figure 2: Algorithm Flow Chart
Every personal computer has an ARP cache that stores mapping between IP address and MAC
address. When computers communicate with each other, they need to know their MAC addresses by
querying ARP cache. If there are not results they want, they will send ARP request packets to target
computers. If target computers are active, they will respond to request packets and send ARP response
packets. According to theory, ARP request packets can be sent actively to target devices and ARP
response packets are captured to judge target devices’ activity.
5 Distinguish of Network Device’s Type
Judgment of network device’s activity tells inactive network devices from active network devices.
After that, distinguish of network device’s type is needed. Only knowing which devices are personal
computers and which devices are switches, other switches can be accessed for related topology
information to finish network topology discovery. Its working theory is to get several object values in
the MIB-2 of target network device through SNMP protocol and analyse these values to distinguish
device’s type.
For router, the way to judge is as follows: Get the value of the ipForwarding in the MIB-2. If the
ipForwarding value is 1[9], then get the value of the ifNumber in the MIB-2. If the ifNumber value is
not less than 2, it shows that target device is Router.
For switch, the way to judge is as follows: Get the value of the ipForwarding in the MIB-2. If the
ipForwarding value is two, it shows that target device is not Router. It may be switch or personal
computer. Then get the value of the sysServices in the MIB-2. If the sysServices value is 78, it shows
that target device is switch. 78 can be expressed as a binary value 1001110. Every bit corresponds to
every layer of OSI and the first bit from right corresponds to the first layer. The second bit from right is
1 and it shows that target device can work in the second layer of OSI. According to above, switch can
be distinguished.
For personal computer, the way to judge is as follows: Get the value of the ipForwarding in the
MIB-2. If the ipForwarding value is 2, then get further the value of sysServices in the MIB-2. If the
sysServices value is 76, it shows that target device is personal computer. The reason is target device
doesn’t work in the second layer of OSI. Because 76 can be expressed as a binary value 1001100 and
- 5 -
the second bit from right is 0.
6 Storage and Disposal of Topology Information
This is the key step in real-time network topology discovery. After finding network devices and
get related information, the information (such as IP address, device’ type, parent IP address and so on)
must be stored in the database to provide information source for network topology visualization. In
order to store network topology information, two tables are created in the database. Suppose one is
named temp which stores undisposed topology information and the other is named final which stores
disposed topology information.
As network topology discovery goes on, the topology information in the database needs to be
disposed to supply network topology visualization with exact and real-time topology information. The
disposal can be carried out with SQL. There will be much same information stored in the database
because network topology discovery is cyclic. The redundant information must be deleted from
database in case of confusion in the process of network topology visualization. When some network
devices are shut down, the information about the devices will not be stored in the database. The
information about the devices before that will be out of date and must be deleted from database in time.
So the inactive devices will not be displayed in the topology map and network topology can be
visualized in a real-time and correct way.
The flow chart of storage and disposal of topology information is showed as Figure 3.
Start
End
Delete redundant records in the table temp
Delete all the records in the table final and copy all the
records in the table temp into table final
Whether the process of the storage
and the disposal is stopped or not
Y
Store topology information into the database while the
disposal process waits n seconds (n depends on the scale of
some network)
Delete out of date records in the table temp
Store topology information into the database while the
disposal process waits n seconds (n depends on the scale of
some network)
N
Delete redundant records in the table temp
Delete all the records in the table final and copy all the
records in the table temp into table final
Figure 3: Storage and Disposal of Topology Information Flow Chart
7 Experiment and Result Analysis
To validate the feasibility of the algorithm, a small experimental network is constructed, showed
as Figure 4. In the Figure, S is a layer-2 switch that links to university network upwards and links to
some personal computers downwards. A is a managing personal computer and firewall is not installed
in one of some personal computers.
- 6 -
Figure 4: Experimental Network
The experimental result is showed as Table 1. All the network devices that switch S links to
downwards can be found with the algorithm in the paper, including the devices personal firewall are
installed in. In the Table 1, some devices’ type is unknown because these devices are not installed
SNMP agent in or SNMP service doesn’t start.
Table 1: Experimental Result Based on Arp Detection
TIME NAME IP ADDRESS TYPE
PARENT IP
ADDRESS
DESCRIPTION
2008-01-15
16:23:39
unknown unknown
please check
whether SNMP
agent is enabled
2008-01-15
16:23:43
WANGXIUF PC
Hardware: x86
Family 15 Model
4 Stepping
2008-01-15
16:23:44
unknown unknown
please check
whether SNMP
agent is enabled
2008-01-15
16:23:57
HYJ PC
Hardware: x86
Family 15 Model
4 Stepping
2008-01-15
16:23:58
unknown unknown
please check
whether SNMP
agent is enabled
2008-01-15
16:24:04
GC-D55C0A PC
Hardware: x86
Family 15 Model
4 Stepping
2008-01-15
16:23:06
unknown unknown
please check
whether SNMP
agent is enabled
2008-01-15
16:23:07
TY-RWDYP PC
Hardware: x86
Family 15 Model
4 Stepping
In order to reveal the precise of the algorithm in the paper, a usual way to judgment of network
device’s activity that is Ping is also used. The experimental result is showed as Table 2. Personal
firewall is not installed in the network device in the Table 2.
- 7 -
Table 2: Experimental Result Based on Ping Detection
TIME NAME IP ADDRESS TYPE
PARENT IP
ADDRESS
DESCRIPTION
2008-01-15
16:23:07
TY-RWDYP PC
Hardware: x86
Family 15 Model 4
Stepping
By comparing the former experiment with the latter one, not only the feasibility of the algorithm
proposed in the paper is validated, but also the algorithm is more accurate than usual.
8Conclusion
Real-time network topology discovery plays an important part in network situation awareness. It
could help decision-makers have a timely and accurate understanding about the current network
situation so that they can react immediately and deal with possible network security events in time. The
algorithm proposed in the paper can bypass personal firewall and judge the activity of network devices
effectively. It has solved the problem that the activity of network devices can’t be judged by Ping
detection because Ping can not pass personal firewall. The algorithm is not only very accurate, but also
real-time. So, it can update information of network topology discovery dynamically.
Nowadays, the scale of network is growing very huge, and the structure of network is becoming
more and more complicated. In practice some problems about network topology discovery are still not
solved very well. For instance, how can network topology be discovered accurately when hubs or dumb
switches exist in the network? And how can physical topology discovery be implemented in the
multi-subnet or VLAN? Our algorithm is only implemented in a single subnet at present, not applicable
to multi-subnet or VLAN. At the same time, efficiency of the algorithm is not very high. Therefore, our
future work is to implement physical topology discovery in the multi-subnet and VLAN, to improve
efficiency of the algorithm and to strength the algorithm’s universality. Use unnumbered third level
headings for the acknowledgments. All acknowledgments go at the end of the paper.
References
[1]H. Q. Wang, J. Lai, L. Zhu, Y. Liang, “Survey of Network Situation Awareness System,” Computer Science, vol.
33, 2006, pp. 5-10.
[2]Liang Zhu, H. Q. Wang, L. J. Zheng, “Research Comment of Network Security Situation Visualization,”
Sciencepaper Online
[3]R. Siamwalla, R. Sharma, S. Keshav, “Discovering Internet Topology,” in INFOCOM’99, 1999
[4]R. Govindan, H. Tangmunarunkit, “Heuristics for Internet Map Discovery,” in Proceedings of IEEE
INFOCOM’00, 2000
[5]D. H. Xu, X. Hu, Q. Wang, Y. T. Bai, “Algorithm of Network Topology Search,” Computer Application, vol. 19,
1999, pp. 4-6.
[6]Y. F. Qin, Y. J. Luo, X. R. Kou, “Research on the Technology of Getting Network Topology Information,”
Microcomputer Information, vol. 22, 2006, pp. 127-130.
[7]Y. P. Li, H. Z. Wang, H. Y. Tian, Q. P. Zhao, “Network Topology Discovery Based on SNMP and Java,”
Computer Engineering and Applications, vol. 5, 2004, pp. 152-154.
[8]Y. Jiang, M. Z. Hu, B. X. Fang, H. L. Zhang., “An Internet router level topology automatically discovering
system,” Journal on Communications, vol. 23, 2002, pp. 54-62.
[9]Yuan Guan, X. J. Wang, J. D. Lu, “An Improved SNMP-based Network Topology Discovery Algorithm,”
Microelectronics & Computer, vol. 23, 2006, pp. 172-175.
