Network Discovery

We study network discovery as a combinatorial optimization problem in the following setting:

• Discover an unknown network modeled as a graph G=(V,E)
• Use minimum number of queries:
• A query is specified by a vertex v from V
• A query returns all shortest-paths from v.

Network Discovery is part of DELIS (Dynamically Evolving Large-scale Information Systems) -- an Integrated European Project founded by the "Complex Systems" Proactive Initiative within the Sixth Framework Programm.

There are several publications on this topic. The main results are summarized in the article "Network Discovery and Verification", published in the IEEE Jorunal on Selected Areas in Communications, December 2006:

• No deterministic algorithm can achieve competitive ratio better than 3.
• There is a randomized algorithm with competitive ration &radic(n log n)
• The offline version
  • is NP-complete
  • does not admit better than log(n) approximation

The long standing open problem is to find a good deterministic algorithm with provable performance, or good practical behaviour. Having both goals in mind we have performed experiments with several deterministic strategies (see the relevant papers for more details):

• The source code of the experiments is available.
• The data (collected from RouteView Project and from DIMES project) are available in the directory snapshots

Publications