Brief Announcement: A Conjecture on Traceability, and a New Class of Traceable Networks

摘要

The problem of reconstructing the topology of a network, given a set of hop-by-hop traces of packet paths through it, is called 'network tracing'. Unfortunately, there are only a few known classes of networks (trees and odd rings) that are traceable, i.e. that have the property that a unique network topology can be reconstructed from a trace set. Here, we suggest a property that may be the reason such networks are traceable, and use it to identify a new class of traceable networks.