Proposal Title
Design & Development of IP Network
Topology Discovery Algorithm based on Standard Network Protocols
Primary
Investigator(s):
Dr. Roger L. A. Cottrell
Assistant Director
Networks Group Leader
SLAC Computing Services
Stanford Linear
Email: cottrell@slac.stanford.edu
Hafiz Farooq Ahmad, PhD
Specialist Engineer
Communication Technlogies,
2-15-28 Omachi, Aoba Ku,
Email: farooq@comtec.co.jp
Descriptions of
Research and Goals
Figure 1 : Discovery of Multi-subnet Network & Boundary Aware Discovery
- Discovery of network routers, network switches (L2, L3), network printers, networks hosts and other managed networks devices. (These network devices could belong to any vendor).
- Interconnections between network devices. Router to router connections, switch to switch connections, router to switch connections, switch to host connections etc. (Figure-1)
- Multi-Subnet discovery. (Figure-1)
- Limiting the topology to a specific administrative domain. (Boundary aware topology discovery). (Figure-1)
- No user interaction. Few parameters required in the configuration file before discovering the network.
- Logically separate discovery and display procedure. This could enable us to support multiple display clients at a time.
- Topology-MIB development. This will provide a standard interface for other monitoring and management applications to access topology discovery information.
- IPv6 and IPv4 support.
- Visualization of Large Multi-subnet networks. (Figure-2)
Figure 2
: Sample Expected Output of Visualization
Network topology knowledge including the path between endpoints, can play an important role in analyzing, engineering, and visualizing networks. Network topology refers to the characterization of the physical connectivity relationships that exist among entities in a communication network. Network topology constantly changes as nodes and links join a network, personnel move offices, and network capacity is increased to deal with added traffic. It is sometimes impossible to identify the existence of multiple paths between hosts, switches, routers and printers, in such large and constantly evolving networks, it is difficult to determine how the network is actually laid out. Given the dynamic nature and the ever-increasing complexity of today's IP networks, keeping track of topology information manually is a daunting (if not impossible) task. This situation clearly mandates the development of effective, general-purpose algorithmic solutions for automatically discovering the up-to-date physical topology of an IP network. An additional challenge in the design of such algorithms is dealing with the lack of established, industry-wide standards on the topology information maintained locally by each network element, and the diversity of elements and protocols present in today's multi-vendor IP networks. The goals of our work research is to automatically discover network topology and visualization of the topology discovered.
Research on this project will consist of five major phases.
- Evaluation/analysis of the existing techniques
Our first aim will be to evaluate and analysis the existing approaches/software’s which are used to discover the network topology. Identify the limitations and develop a development plan for a new generic approach, keeping inconsideration the performance aspect.
- Development of new topology discovery algorithm
As our second aim we will develop a new topology discovery algorithm
which will not be any vendor protocol or vendor equipment dependent. We plan to
use standard Simple Network Management Protocol (SNMP), Internet Control
Message Protocol (ICMP), Address Forwarding Tables (AFT), Traceroute, etc. (Figure 3)
Figure 3 : Flow Diagram for Planned Single Subnet Discovery Algorithm
- Visualization algorithm
Our Third aim is to develop a visualization technique to display very large network in a way that the topology is easily understandable and useful for network diagnostics (no overlaps, all connections, different colors for different devices, zooming capability, locating capability using IP address, path locating etc). (Figure 2)
- IPv6 support
Our Fourth aim is to extend our topology discovery algorithm from IPv4 to IPv6 enabled devices.
- Testing in different network configurations
Our fifth and the final aim will be to thoroughly test our algorithm in different network configurations/environments and make some minor changes if needed.
Uses
- Network topology can be used in order to simulate real networks.
- Network topology information is useful in deciding whether to add new hosts, switches, routers, printers and to figure out whether current hardware is configured correctly.
- It also allows network managers to find bottlenecks and failures in the network.
- A network map helps users determine where they are in the network so they can decide where to site.
- Both network management and performance analysis benefit from network topology knowledge. Network managers with access to an automatically derived topology of their network, they are better able to react to and prevent problems. They can not only observe the exact location of a problem and trace it back to the source, but also analyze the use of the network under normal operations.
- For planning parallel applications, topology knowledge allows the effects of link-sharing on an application’s performance to be predicted in advance and nodes to be selected with appropriate network connections to match the application’s needs.
- While the bottlenecks on LANs are generally not as severe as those on WANs, reliance on commodity components and the emergence of grid-based computing has increased the need for topology discovery.
- Discovering the physical layout and interconnections of network elements is a prerequisite to many critical network management tasks, including reactive and proactive resource management, server setting, event correlation, and root-cause analysis.
Information to be extracted from Different
Network Devices
Routers
- ARP Cache (Once in one round of Topology Discovery[1])
- Routing Table (Once in one round of Topology
Discovery)
- Information (IP Address, Mask etc) about the router
interfaces. (Once in one round of Topology Discovery)
Switches L3
- ARP Cache (Once in one round of Topology Discovery)
- Routing Table (Once in one round of Topology
Discovery)
- Information about the interfaces. (Once in one round
of Topology Discovery)
- Address forwarding table. (Once in one round of
Topology Discovery)
Switches L2
- Address forwarding table. (Once in one round of
Topology Discovery)
ICMP Request
1. We need to send ICMP request (uni-cast) to every IP device
in the network to check its availability. (Once to every IP Device in one round
of Topology Discovery)
SNMP Request
1. Once using the ICMP request we know that the device is
on the network, and then we send it a SNMP request to check what type of device
it is. (Once to every IP Device in one round of Topology Discovery)
Amount of Data to be extracted from
Different Network Devices
- Address Resolution Protocol
(ARP) Cache
In the ARP cache we have IP address to MAC address mapping.
- Address Forwarding Table
(AFT)
In the ARP cache we have MAC address to port mapping.
- Routing Table
From the Routing we need to get the Mask and IP Address.
- Interface Information
From the interface information we need to Mask and IP Address.
Timeframes for Funding and Research
Completion
Any Required/Expected Research Cooperation
with CISCO
Support Requirements
Graduate Students Involved
Other Current or Anticipated Matching Funds
Short Biographic of the Researchers
Name of Cisco Account Manager
Names of CISCO Champion
Name and Address of the Relevant University Administrative Contact