Model-Based Identification of Dominant Congested Links

In this paper, we propose a model-based approach that uses periodic end-end probes to identify whether a “dominant congested link” exists along an end-end path. Informally, a dominant congested link refers to a link that incurs the most losses and significant queuing delays along the path. We begin by providing a formal yet intuitive definition of dominant congested link and present two simple hypothesis tests to identify whether such a link exists. We then present a novel model-based approach for dominant congested link identification that is based on interpreting probe loss as an unobserved (virtual) delay. We develop parameter inference algorithms for hidden Markov model (HMM) and Markov model with a hidden dimension (MMHD) to infer this virtual delay. Our validation using ns simulation and Internet experiments demonstrate that this approach can correctly identify a dominant congested link with only a small amount of probe data. We further provide an upper bound on the maximum queuing delay of the dominant congested link once we identify that such a link exists.