 | Name information |
| SNMP information |
| Name information |
| SNMP information (route table, etc.) |
| Net mask |
| List of hosts and routers within the subnet. |
Domain Topology Generation
Project Octopus
Basic tools
Several methods can be used to discover network topology within a domain. The simplest one is PING. Ping is a tool that allows to determine whether a machine is alive or not. It works by sending an ICMP packet to the machine, and if the machine responds, then that means it is alive. A variant of PING, broadcast PING works by sending the ICMP packet to a broadcast address. If a machine is part of that broadcast group, the machine will respond. Thus the host will get responses from all machines in the group. This is useful to determine the subnet of a host.
Another useful tool is the DNS (Domain Name Server) query. The DNS stores a large amount of information about nodes in the network. The service that all DNS servers supply is the name to address resolution. However, address to name and DNS ls by domain is not offered in every network for security reasons.
Another tool is traceroute. This tool allows you to figure out what routers a packet goes through when traveling to another machine. This helps in subnet guessing.
The most useful tool SNMP (Simple Network Management Protocol). SNMP is a protocol which allows you to query information about a machine's view of the network. For example, you can query a router what machines it is connected to. This is a very powerful tool, but unfortunately, it is not supported in many networks. Also, SNMP access is restricted in most networks that support it.
These are simple descriptions of the algorithms. For more detail, please email Rachit. All these algorithms output the topology in the same hierarchical format:
| List of hosts
| ||||
| List of routers
| ||||
| List of subnets
|
Ping Broadcast + DNS ls Algorithm
This algorithm relies on a DNS ls query to determine all the nodes in the network. Then routers are determined by a DNS query. If the host has more than one IP address, it is a router (Note: this is not necessarily true). Then the subnets of each host are determined by Rosen's Subnet Guessing algorithm.
SNMP Algorithm
This algorithm is the simplest. It finds the default router of the host the algorithm is running on first. From there it issues SNMP queries to determine routers and hosts the default router is connected to. The algorithm recursively goes through all the routers and hosts until it reaches a host that is outside the domain specified. This algorithm has the benefit of finding other network information such as packets dropped, link bandwidth, utilization, etc. However, the network must support SNMP.
Ping Broadcast + Subnet Hopping + Probing Algorithm
This algorithm determines routers and hosts by looking at the first few IP numbers of a subnet. It figures most adminisrators fill the subnet from the low IP numbers up, and the routers should be at the very first few nodes. If the algorithm finds a router, it hops to the other subnets the router is connected to and scans those.
Traceroute + DNS ls Algorithm
This algorithm is very similar to the first algorithm in that it relies on a DNS query to determine names of all the nodes in the network. Then what it does is runs traceroute on every node returned from the query. From the traceroute information, subnet information can be extracted.
Random Guess + Traceroute + Probing Algorithm
This algorithm is a hybrid of the previous two algorithms. It does away with the DNS ls requirement in that it uses random guessing to find IP addresses and then traceroutes them. Probing is used to find further IP addresses in the subnet. This way, you can get most of the routers and some hosts within an IP range.
Ping Broadcast Subnet Guessing Algorithm
This algorithm is a way to find out the subnet given a host within the subnet and ability to perform at least weak ping broadcast. We define strong ping broadcast support as if a ping broadcast is sent to a subnet, then all hosts within the subnet respond. In weak ping broadcast, only the router responds. The algorithm works by first assuming that the subnet mask length is 31 bits long. Then both broadcast addresses are broadcast and replies are recorded. If the intersection of both replies are not empty, then the broadcast was a valid broadcast and thus the subnet is correct (note: if only weak broadcast is supported, the two replies would be the ones of the same router). Otherwise, try guessing with a 30 bit net mask (and so on).
All of these algorithms are completed to as of March 1998. These algorithms have been run on the following networks:
| CUCS Network (Cornell Computer Science Department) |
| Cornell Network |
| Berkeley Network |
| Stanford Network |
The CUCS Network supported all of the algorithms above.
The Cornell Network did not support Ping Broadcast (only traceroute and SNMP algorithms worked).
The Stanford Network did not support strong broadcast nor DNS ls but allowed weak broadcast and traceroute.
This project was presented at BOOM (Bits on our Mind). Here are the Powerpoint slides.
This work is part of the new network management research in the CNRG Research Group with Professor S. Keshav.
This page is last modified 10/10/05 02:18:42 PM