Overlay networks of in situ instruments for probabilistic guarantees on message delays in wide-area networks

Messages transported over wide-area networks are subject to various delays at the hosts and intermediate nodes. In addition to bandwidth limits, the delays have an apparent "random" component due to the complicated dynamics of the network traffic. We consider that the messages sent over the network are subjected to three types of delays: 1) propagation delays along the links; 2) delays due to bandwidth of the links; and 3) "other delays" at the hosts and intermediate nodes which are randomly distributed according to unknown distributions. We propose an overlay network of in situ instruments on such a network to collect delay measurements, compute paths and route messages. We propose regression methods to compute a path whose message delay is close to the optimal expected delay with a high probability, based entirely on measurements. The delay distributions are arbitrary and this guarantee is the best kind possible for this network. We then present a simple multiple path method for achieving low end-to-end delays. This overlay network is implemented over the Internet using user-level daemons that realize paths among themselves without explicit support from the underlying network routers. The Internet measurements show that this method achieves significantly higher aggregated bandwidths compared with the default paths.