Network Discovery and Verification
By Zuzana Beerliova, Felix Eberhard, Thomas Wilhelm Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák, L. Shankar Ram. IEEE Journal on Selected Areas in Communications, 2005
350 citations recorded by the source corpus.
Due to its fast, dynamic, and distributed growth process, it is hard to obtain an accurate map of the Internet. In many cases, such a map-representing the structure of the Internet as a graph with nodes and links-is a prerequisite when investigating properties of the Internet. A common way to obtain such maps is to make certain local measurements at a small subset of the nodes, and then to combine these in order to "discover" (an approximation of) the actual graph. Each of these measurements is potentially quite costly. It is thus a natural objective to minimize the number of measurements which still discover the whole graph. We formalize this problem as a combinatorial optimization problem and consider it for two different models characterized by different types of measurements. We give several upper and lower bounds on the competitive ratio (for the online network discovery problem) and the approximation ratio (for the offline network verification problem) in both models. Furthermore, for one of the two models, we compare four simple greedy strategies in an experimental analysis
View Paper: https://www.semanticscholar.org/paper/cc8a03daf394b4a2831907457b34e340f52e2d44
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- M. Azeem
- Muhammad Faisal Nadeem
- N. Prasad
- C. Hernando
- J. Cáceres
- Ramjee Prasad
- C. Seara
- P. Mahalle
Citations in the corpus
- On the metric dimension of a zero-divisor graph (2017, methodology): “The metric dimension has been discovered or invented in di erent forms and has appeared in di erent applications including combinatorial optimization [22], strategies for themastermind game [9], network discovery and veri cation [8], robot navigation, [15] and so on.”
- Metric-based resolvability of polycyclic aromatic hydrocarbons (2021, methodology): “Partition dimension also has many applications in various real-world applications, such as strategies, coding, and decoding of mastermind games [9], the popular Djokovic–Winkler relation [4], and the procedure of verifying and discovering a network [3].”
- Proposed Security Model and Threat Taxonomy for the Internet of Things (IoT) (2010, methodology): “The new architecture must support methods for the registering of a new sensor system in the broader network [3].”
- On the Metric Dimension of Cartesian Products of Graphs (2005, background): “Resolving sets have since been widely investigated [4, 8, 9, 10, 11, 12, 14, 17, 18, 27, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 48] and arise in many diverse areas, including network discovery and verification [2], robot navigation [27, 41], connected joins in graphs [40], and strategies for th”