Research On Last-hop And Subnet Discovery Technique In Network Topology Measurement

This paper mainly studies the technology of last-hop routers detection and subnet discovery in network topology measurement.The last-hop routers detection technology is designed to discover the last-hop router of the target with a small measurement load,and provide a basis for further efficient topology detection of the target network.The traditional traceroute method is not suitable for last-hop routers discovery because of the presence of more redundant measurements.This paper proposes and implements three methods for efficiently discovering last-hop routers by combining network distance prediction technology:based on a network detection packet to obation network distance,estimating network distance based on TTL fingerprint,a binary detection method based on a binary strategy.The three methods are used to detect the large-scale last-hop routers,and the discovery rate and the single target average amount of packets are evaluated.It is found that the accurate detection method can only be used for 20% of the target,while only sends two probe packets on average,the step detection method and the dichotomy method are applicable to all surviving targets.The average amount of dichotomy is 5,and the average amount of packets sent by the step method is 3.However,the performance of the stepped detection method depends on the distribution of the predicted distance deviation.Based on the above results,another contribution of this paper is to propose an adaptive last-hop routers discovery method.In the measurement process,according to the intermediate results and the performance of the three measurement methods,the optimal method is selected to obtain the highest discovery rate and detection efficiency.Experiments show that the average combination size of the optimal combination method does not exceed 5,and the effect is better than that of the three methods when used alone.Experiments show that the average amount of the combined method does not exceed 5,and the effect is better than that of the three methods when used alone.Traceroute measurement is the main means of discovering topology paths.However,when it is used for large-scale network topology measurement,measurement redundancy is generated.Especially when performing topology discovery on a subnet,a large number of repeated probes are generated at the core of the network.In this regard,this paper proposes three subnet discovery techniques by using external information such as subnet address division mechanism and the approximate tree structure of the target subnet topology.They are subnet branch growth detection technology,forward and reverse detection technology,and multi-type detection packet detection technology.The subnet branch growth technique uses the idea of depth-first search in the detection process,and continuously divides the target network segment into smaller subnets,and performs recursive detection on the starting and ending targets of different subnets;In the forward-reverse detection technology,when the measured IP is repeatedly encountered,the hop-by-hop detection process is stopped in advance according to the same assumption of the path to the same subnet,and the measurement redundancy is reduced;Multi-type probe packet detection technology replaces the probe packet type after timeout to increase the chance of reply.Combining these three technologies,this paper implements an efficient subnet discovery tool named fastrace based on NSE.The fastrace measurement experiment on 150 virtual dedicated servers,and compared with the results of the traceroute tool in terms of topology size and packet yield,found that fastrace can significantly reduce measurement redundancy without losing the discovery of topological integrity.