Listening to TCP flows

The general idea of Listen is to monitor TCP flows, and to draw conclusions about the state of a route from this information. The forward and reverse routing paths between two end-hosts can be different. Thus we may observe packets that flow in only one direction. We say that a TCP flow is complete if we observe a SYN packet followed by a DATA packet, and we say that it is incomplete if we observe only a SYN packet and no DATA packet over a period of 2 minutes (which is longer than the SYN timeout period).

Consider that a router receives a route announcement for a prefix $P$ and wishes to verify whether prefix $P$ is reachable via the advertised route. In the simplest case, a router concludes that the prefix $P$ is reachable if it observes at least one complete TCP flow. On the other hand, the router cannot blindly conclude that a route is unreachable if it does not observe any complete connection. Incomplete connections can arise due to reasons other than just reachability problems. These include: (a) non-live destination hosts; (b) route changes during the connection setup of a single flow i.e. SYN and DATA packets traverse different routes. (c) port scanners generating SYN packets.

Under the assumption that port scanners are not present, detecting reachability problems would be easy. To deal with non-live destinations, a router should notice multiple incomplete connections to $N$ different distinct destination addresses (for a reasonable choice of $N$). The problem of route changes can be avoided by observing flows over a minimum time period $T$. Hence, a router can conclude that a prefix is unreachable if during a period $t$ it does not observe a complete TCP flow where $t$ is defined as the maximum between: (a) the time taken to observe $N$ or more incomplete TCP flows with different destinations within prefix $P$; (b) a predefined time period $T$.

The basic probing mechanism described above suffers from two forms of classification errors: (a) false negatives; (b) false positives. A false negative arises when a router infers a reachable prefix as being unreachable due to incomplete connections. A false positive arises when an unreachable prefix is inferred as being reachable. A malicious end-host can create false positives by generating bogus TCP connections with SYN and DATA packets without receiving ACKs. In Section 6.2, we show how to choose the parameters $N$ and $T$ to reduce the chances of incomplete connections causing false negatives.