End-to-End Inference of Loss Nature in a Hybrid Wired/Wireless Environment

Jun Liu, Ibrahim Matta, Mark Crovella2002

TL;DR

This paper introduces a novel end-to-end method using Hidden Markov Models (HMMs) and "loss pairs" to distinguish between packet losses caused by network congestion and those due to wireless link errors. This distinction is crucial for TCP to avoid over-reacting to wireless-induced losses, thereby improving performance in hybrid wired/wireless networks.

What Problem Does This Paper Address?

The proliferation of wireless links in the internet has created a challenge for TCP's congestion control mechanisms. Traditionally, TCP interprets packet loss as a signal of network congestion. However, in hybrid wired/wireless environments, packet loss can also occur due to signal fading or interference on the wireless link, which is not indicative of congestion. When TCP incorrectly attributes wireless losses to congestion, it unnecessarily reduces its sending rate, leading to reduced throughput and unfairness. Existing methods for differentiating these loss types often require network-side support or struggle with accuracy. This paper aims to provide an effective, end-to-end solution that can accurately classify packet loss types without requiring any modifications to the network infrastructure.

Methods

The core of the proposed solution lies in leveraging the distinct characteristics of packet delays associated with different loss types. The authors hypothesize that congestion losses, stemming from buffer overflows, will exhibit different delay patterns compared to wireless losses, which are more erratic.

  1. Loss Pairs: This technique involves sending packets back-to-back. If one packet is lost and the other arrives, the arriving packet's round-trip time (RTT) provides a snapshot of the network conditions at the time of the loss. This is crucial for capturing the delay experienced just before a packet is lost.
  2. Hidden Markov Models (HMMs): HMMs are employed to model the observed sequence of RTTs from loss pairs. An HMM consists of a set of hidden states, each characterized by a probability distribution over observable events (in this case, RTTs). The authors train a 4-state HMM using Gaussian distributions for each state, where each state is intended to capture a specific network condition or loss type.
  3. Classification: Once the HMM is trained, the Viterbi algorithm is used to infer the most likely sequence of states for a given series of loss pair observations. The key innovation is the "labeling" of these states. Through a heuristic process involving bipartite partitioning of states and weight assignment based on RTT mean, standard deviation, and their ratio, states are assigned to either "congestion" or "wireless" loss types. A packet loss is then classified based on the state the HMM is in at that moment.

Datasets

The authors evaluate their technique using simulations with the ns-2 network simulator. They configure various network topologies and traffic patterns to generate datasets of packet losses. For each simulated loss pair, the true nature of the loss (congestion or wireless) is recorded, serving as the ground truth for evaluating the classification accuracy. No specific publicly available datasets are mentioned; the evaluation is based on simulated network scenarios.

Key Insights and Ideas

  • Delay as a Differentiator: The fundamental insight is that the delay patterns preceding congestion losses and wireless losses are measurably different, providing a basis for classification. Congestion losses tend to be associated with more predictable, higher delays due to buffer occupancy, while wireless losses are more variable.
  • HMMs for Temporal Patterns: HMMs are well-suited for capturing the temporal dependencies in network behavior, allowing them to learn and distinguish between these delay patterns over time.
  • Heuristic State Labeling: The development of a heuristic method to assign "congestion" or "wireless" labels to HMM states is a critical contribution. This process balances the need for high accuracy in classifying congestion losses (important for TCP fairness) with maintaining reasonable accuracy for wireless losses.
  • End-to-End Advantage: The proposed method operates entirely at the end-host, requiring no modifications to intermediate network devices, which is a significant practical advantage over many prior approaches.

Key Results

  • Superiority over Vegas Predictor: The proposed HMM-based technique consistently outperforms the Vegas predictor in classifying packet losses, achieving higher accuracy in distinguishing between congestion and wireless losses across various network configurations. For instance, in one comparison, the HMM achieved a P[CC] (probability of correctly classifying congestion loss) of 0.994 compared to the Vegas predictor's 0.932, while also maintaining a good P[WW] (probability of correctly classifying wireless loss) of 0.819.
  • Effectiveness Across Configurations: The technique demonstrates effectiveness in a wide range of network conditions, including varying bottleneck utilization, bandwidth-delay products, wireless link locations, and error models (uniform and Markovian-Gilbert).
  • Impact of Network Conditions: Classification accuracy generally deteriorates with increasing bottleneck utilization and can be affected by the burstiness of cross-traffic. Higher bandwidth-delay products tend to improve accuracy.
  • Wireless Link Error Model: Bursty wireless link errors (longer durations in the BAD state of a Markovian model) generally lead to more accurate classification.

Limitations and Future Work

  • Heuristic Labeling: The state labeling process is described as heuristic and subject to refinement for different application settings. While effective, it might not be universally optimal.
  • Trade-offs: The paper acknowledges a trade-off between accurately identifying congestion losses and wireless losses. Different applications might prioritize one over the other, requiring tuning of the labeling process.
  • Future Work: The authors plan to investigate trade-offs between classification accuracy and time/computation complexity, as well as the interaction between loss classification and recovery control mechanisms. They also suggest exploring other types of observations beyond RTTs, such as inter-arrival times between losses.

Summary updated

Abstract

In a hybrid wired/wireless environment, an effective classification technique that identifies the type of a packet loss, i.e., a loss due to wireless link errors or a loss due to congestion, is needed to help a TCP connection take congestion control actions only on congestion-induced losses. Our classification technique is developed based on the loss pairs measurement technique and Hidden Markov Models (HMMs). The intuition is that the delay distribution around wireless losses is different from the one around congestion losses. An HMM can be trained to capture the delays observed around each type of loss by different state(s) in the derived HMM. We develop an automated way to associate a loss type with a state based on the delay features it captures. Thus, classification of a loss can be determined by the loss type associated with the state in which the HMM is at that loss. Simulations confirm the effectiveness of our technique under most network conditions, and its superiority over the Vegas predictor. We identify conditions under which our technique does not perform well.
BibTeX
@misc{liu2002end,
  author = {Jun Liu and Ibrahim Matta and Mark Crovella},
  title = {{End-to-End Inference of Loss Nature in a Hybrid Wired/Wireless Environment}},
  year = {2002},
}
Figure