Building a Reference Combinatorial Modelfor Dynamic Networks:Initial Results in Evolving Graphs

Wireless technologies and the deployment of mobile and nomadic services are driving the emergence of complex ad-hoc networks, that have a highly dynamic behavior. Modeling such dynamics, and creating a reference model on which results could be compared and reproduced was stated as a fundamental issue by a recent NSF workshop on networking. In this paper, we show how the modeling of time-changes unsettles old questions and allows for new insights into central problems in networking, like routing metrics, connectivity, and spanning trees. Such modeling is made possible through evolving graphs, a simple combinatorial model which helps capture the behavior of dynamic networks over time.