Wavelet-based Inference for Network Diagnosis

Wavelet-based Inference for Network Diagnosis

A Non-intrusive, Wavelet-based Approach To Detecting Network Performance Problems Polly Huang Anja Feldmann Walter Willinger ETH Zurich U. Saarbruecken AT&T Labs-Research

Road Map Motivation and rationale Mechanism details Conclusion and outlook Performance Problem Web Web

TCP TCP Network Link/Physical Web Internet

Network Link/Physical TCP Google.com Network Link/Physical proxy

congestion routing else server congestion routing else Current State Active probing

Ex: traceroute, ping Disturbing - injecting unnecessary traffic Biasing - distort metrics of interest Heisenberg effects Passive measurements Ex: Cisco NetFlow, IP Accounting, other packetlevel measurment give much information Do not infer problems inside the network What Would Be Cool

Passive Trigger alerts in real time For problems due to Server load Congestion Routing error Common Symptoms Delay and drop TCPs Closed-loop Control

Delays/drops reflected in RTT/RTO estimations RTT: round trip time RTO: retransmission timeout Quality of Network Path Values of RTT/RTO estimations Amounts of RTT/RTO samples Can be measured passively

Detailed Estimation Methodology A hash table of all data packets observed One RTT sample per data-ack pair One RTO sample per data-data pair Slow ~ #packets/observation period especially with high date rate connections (the likely trouble makers)

Objectives Passive measurement Non-intrusive Infer quality of network paths Detecting network performance problem Efficiently (so can be done in real time) Wavelet-based technique

Road Map Motivation and rationale Mechanism details Conclusion and outlook Wavelet-based Technique Theoretical ground Wavelet transform Energy plots (or scaling plots) Interpreting energy plots

WIND, the problem detection tool Features & examples Detection methodology Validation effort Theoretical Ground FFT Frequency decomposition fj, Fourier coefficient Amount of the signal in frequency j

WT: wavelet transform Frequency (scale) and time decomposition dj,k, wavelet coefficient Amount of the signal in frequency j, time k Wavelet Example 1 0 -1 00 00 00 00 11 11 11 11

s1 00002222 00000000 s2 0044 08 s3 8

00 8 0000 d1 d2 d3 Self-similarity

Energy function Ej = (dj,k)2/Nj Self-similar process Ej = 2j(2H-1) C <- the magic!! log2 Ej = (2H-1) j + log2C linear relationship between log2 Ej and j Self-similar Traffic

Effect of Periodicity self-similar Internet Traffic Adding Periodicity packets arrive periodically, 1 pkt/23 msec coefficients cancel out at scale 4 10 00 00 00 10 00 00 00

s1 10001000 10001000 s2 1010 11 s3

2 11 0 1010 d1 d2 d3

Simulation Traffic Single RTT Simulation Traffic Congestion Interpreting Energy Functions Abrupt knees at RTT time scale RTO time scale

Knee shifts RTT/RTO time changes Low energy level (after normalization) congestion low traffic volume WIND - The Detection Tool Wavelet-based Inference for

Network Detection Based on libpcap and tcpdump On-line mode (efficient) Per packet: compute dj,k Per observation period: output Ej On a subnet basis Off-line mode Detailed RTT/RTO estimation

Real Traffic By Subnets Real Traffic By Periods Real Traffic By Periods Detecting Methodology Reference function

Smoothed average Difference Area below the reference function Weighted sum by scale Flagged interesting Top 10% deviations Pick Out Interesting Ones 26, 30, 31

Validation By WIND off-line mode Detailed RTT/RTO estimations Volume Similar heuristics (area difference) CCDF of RTT/RTO Ratio of RTO/RTT Volume

Validate period 26, 30, 31 CCDF of RTT: CCDF of RTO: pick out period 29, 30, 31 pick out period 23, 26, 31 80-90% 80-90% are are validated validated interesting interesting

Road Map Motivation and rationale Mechanism details Conclusion and outlook Summary Detect problems using energy plots If self-similar, clean linear relationship If periodic, getting knees If problems, knee shifts or low energy level

WIND: the online/offline analysis tool Passive Efficient Outlook Full-fledged diagnosing tool More sophisticated heuristics Use of traceroute data Illustrative examples Using the tool (beta release)

Using the methodology Questions? http://www.tik.ee.ethz.ch/~huang

Recently Viewed Presentations

  • Comparison Comparisonof ofCosts CostsAssociated Associatedwith withthe thePreparation Preparationof

    Comparison Comparisonof ofCosts CostsAssociated Associatedwith withthe thePreparation Preparationof

    The author would like to thank Mr. Jason Woods, Mr. Dan Carl, Ms. Courtney Sherwood, Mr. William Beckman, Mr. John DenHerder and Mr. Paul Bui for their assistance in data collection. $39,420 DietGel R/E (without Petri dish) $45,260 DietGel R/E...
  • Traumatic Brain Injury and Use of Narcotic Pain

    Traumatic Brain Injury and Use of Narcotic Pain

    Definition of Chronic Pain(National Institutes of Health 2016) Occurs on at least half of the days over a 6 month period or longer . Chronic pain lasts after injuries heal, is poorly localized and may not have a identifiable physical...
  • Macbeth - Grade

    Macbeth - Grade

    Represents the path Macbeth chose NOT to take, the path in which ambition does not lead to betrayal and murder. Fearful of the witches' prophecy that Banquo's heirs will seize the throne, Macbeth hires a group of murderers to kill...
  • Presentation Title - CIT International

    Presentation Title - CIT International

    Disclosures. I have no personal financial relationships with commercial interests relevant to this presentation. The views expressed are my own, and do not necessarily represent those of the NIH, NIMH, or the Federal Government
  • The so-called &quot;Temple-State&quot; in Mesopotamia

    The so-called "Temple-State" in Mesopotamia

    The so-called "Temple-State" ... Statues of worshippers buried in the Abu Temple at Tell Asmar, c. 2600 B.C. Such statues were placed in the temple to serve as "substitutes" when the subject could not go to the temple to make...
  • Quaestio: How similar were the origins of Ancient India and ...

    Quaestio: How similar were the origins of Ancient India and ...

    THE BIG FOUR RIVER VALLEYS. Xia & Shang China: Yellow River (aka Huang He River) - Modern NE China . MORE THAN FOUR. There were other important early civilizations that developed in areas where fertile land could be cultivated to...
  • SIMS 213: User Interface Design & Development Marti

    SIMS 213: User Interface Design & Development Marti

    Harold and most of his group are familiar with calendaring systems such as Outlook or ICal, and use the CalAgenda calendaring system to schedule meetings. Harold's ultimate goal in relation to the campus calendar is to publicize as many events...
  • Rotary District 1130

    Rotary District 1130

    Community and Vocational Service. In line with Rotary international there has been a split of the C&V team in RIBI to separate teams. This was to boost Vocational Service as one of the main "Avenues of Service"