Flow-Based Symmetry Estimator (FSE): Estimating Routing Symmetry by Flow Measurements

Maurizio Dusi {mdusi (at) caida (dot) org}-Universita' degli studi di Brescia, Italy- and Wolfgang John {johnwolf (at) caida (dot) org}-Chalmers University of Technology, Sweden.
1. Overview
2. Prerequisites
3. FSE tool (download)

1. Overview

Knowledge of the fraction of symmetric flows on a link is especially important to traffic analysis and characterization tasks (e.g. traffic classification). Researchers and developers often embed the assumption of traffic symmetry in their traffic analysis tools. While such methods work fine on stub-networks with single access links (where traffic is 100% symmetric), they are unlikely to work on backbone networks, where routing asymmetry can impair or invalidate results of tools and models that assume symmetry. Consequently, it is crucial for passive network data analysis researchers to be aware of the symmetry properties of measured links in order to choose proper analysis methods.
We provide the Flow-based Symmetry Estimator (FSE), a simple quick method to estimate the level of routing symmetry on passively measured flow data. The FSE tool is designed to take unidirectional flow data as input. We chose CoralFlow (part CoralReef suite) as out-of-the-box tool to retrieve such information. First FSE filters out nonproductive TCP background radiation based on an effective heuristic. CoralFlow then applies interval based flow discrimination and defines flows as unidirectional stream of packets grouped by 5-tuples of source and destination IP, port numbers and protocol.

1.1 The FSE method:


After collecting a unique list of unidirectional flows for each direction of a link, 5-tuples are classified as symmetric if they appear within both lists. Packet- and byte-level symmetry is derived as the fraction of packets (bytes) sent between tuples classified as symmetric, so that the degree of symmetry can be quantified in three dimensions: flows (5-tuple), packets, and bytes.
    1. consider TCP packets carrying data
    2. Tf = set of tuples going forward
    3. Tb = set of tuples going backward
    4. intersection of Tf and Tb = set of symmetric tuples TS
    5. pkts (bytes) in TS=set of symmetric pkts (bytes)

1.2 The FSE traffic filter:

The presence of flows generating traffic that is inherently asymmetric, such as UDP and ICMP flows that do not always require packet recipients to reply, might mislead traffic symmetry assessement. Another cause of asymmetry over-estimation is TCP background radiation, such as network scanning and probing, which can be a substantial fraction of total flows on some links. To discard these kinds of traffic from symmetry estimates, FSE considers TCP data traffic only: in addition to filtering out ICMP and UDP traffic, we also filter out nonproductive TCP sessions consisting of only signaling packets, which are typically SYN/ACK/RST attacks, scans, etc. We use a simple heuristic to implement this filtering: consider only TCP packets without signaling flags (SYN/FIN/RST) but with the ACK bit set.

Find some results about the effect of this filter on the CAIDA webpage "Observing routing asymmetry in Internet traffic".

2. Prerequisites

3. FSE tool (CorlFlow based)

3.1 Download

Download the FSE script including some documentation here

3.2 Usage

  1. obtain the flow tables with crl_flow (one for each direction, dirA and dirB):
    crl_flow -Cipfilter='tcp[13]&1!=1 and tcp[13]&4!=4 and tcp[13]&2!=2 and tcp[13]&16==16' dag:[ trace.dirA|B.dag ] > trace.dirA|B.crlflows
  2. run fse.py on both the flow tables (dirA and dirB) to obtain the FSEs (Flow-based Symmetry Estimate) of symmetric traffic in terms of tuples, packets and bytes:
    python fse.py -a trace.dirA.crlflows -b trace.dirB.crlflows

last update: 2009-05-12 by Wolfgang John {wolfgang (dot) john (at) chalmers (dot) se}