A passive approach for detecting shared bottlenecks

There is a growing interest in discovering Internet path characteristics using end-to-end measurements. However, the current mechanisms for performing this task either send probe traffic, or require the sender to cooperate by time stamping the packets or sending them back-to-back. Furthermore, most of these techniques require the packets to carry sequence numbers to detect losses, and a few of them assume the existence of multicast. This paper introduces a completely passive approach for learning Internet path characteristics. In particular, we show that by noting the time difference between consecutive packets, a passive observer can cluster the flows into groups, such that all the flows in one group share the same bottleneck. Our approach relies on the observation that the correct clustering minimizes the entropy of the inter-packet spacing seen by the observer. It does not inject any probe traffic into the network, does not require any cooperation from the senders, and works with any type of traffic whether it is TCP, UDP, or even multicast.

I. INTRODUCTION

The Internet literature contains a large body of research that addresses the problem of learning Internet path characteristics using end-to-end measurements. The vast majority of this research requires the end system conducting the measurements to send probe traffic along the path whose characteristics it wants to learn [3], [4], [10], [19], [21]. The few previous mechanisms that do not generate probe traffic are not completely passive because they require the sender to cooperate by time stamping the packets [10], [22] or sending them back-to-back [12], [23]. Furthermore, most of the proposals for inferring path characteristics from end-to-end measurements are not applicable to standard UDP traffic because they assume a packet loss is detectable [12], [19], [22], [23], and some of them work only with multicast traffic [19].