15-744: Computer NetworkingMotivationInternet MeasurementMeasurement MethodologiesTypes of DataOverviewActive MeasurementSample Question: TopologyHow Traceroute WorksProblems with TracerouteFamous Traceroute PitfallMore Caveats: Topology MeasurementLess Famous Traceroute PitfallDesigning for MeasurementSlide 15Two Main ApproachesPacket Capture: tcpdump/bpfTraffic Flow StatisticsWhat is a flow?Flow Record ContentsAggregating Packets into FlowsPacket SamplingProblems with Packet SamplingSlide 24Strategy: Examine the Zeroth-OrderStrategy: Cross-ValidationExample Sanity ChecksCross-Validation ExampleLongitudinal measurement hardAnonymizationPlanetLab for Network MeasurementSlide 32Traces CharacteristicsObservations – Routing PathologiesSlide 35Observations – Routing StabilityInter-Domain RelationshipsPolicies: Intra- and Inter-DomainRouting Faults, ErrorsISP TopologiesNetwork TopologyObservations – Re-orderingObservations – Packet OdditiesObservations – Loss RatesObservations – TCP BehaviorSlide 46Observations – Bottleneck BandwidthFlow PerformanceApplication Traffic AnalysisDNS AnalysisAlgorithms, HacksSecurity, Worms15-744: Computer NetworkingL-19 Measurement2Motivation•Answers many questions•How does the Internet really operate?•Is it working efficiently?•How will trends affect its operation?•How should future protocols be designed?•Aren’t simulation and analysis enough?•We really don’t know what to simulate or analyze•Need to understand how Internet is being used!•Too difficult to analyze or simulate parts we do understandInternet Measurement•Process of collecting data that measure certain phenomena about the network•Should be a science•Today: closer to an art form•Key goal: Reproducibility•“Bread and butter” of networking research•Deceptively complex•Probably one of the most difficult things to do correctly34Measurement Methodologies•Active tests – probe the network and see how it responds•Must be careful to ensure that your probes only measure desired information (and without bias)•Labovitz routing behavior – add and withdraw routes and see how BGP behaves•Paxson packet dynamics – perform transfers and record behavior•Bolot delay & loss – record behavior of UDP probes•Passive tests – measure existing behavior•Must be careful not to perturb network•Labovitz BGP anomalies – record all BGP exchanges•Paxson routing behavior – perform traceroute between hosts•Leland self-similarity – record Ethernet trafficTypes of DataActive•traceroute•ping•UDP probes•TCP probes•Application-level “probes”•Web downloads•DNS queriesPassive•Packet traces•Complete•Headers only•Specific protocols•Flow records•Specific data•Syslogs …•HTTP server traces•DHCP logs•Wireless association logs•DNSBL lookups•…•Routing data•BGP updates / tables, ISIS, etc.56Overview•Active measurement•Passive measurement•Strategies•Some interesting observationsActive Measurement•Common tools:•ping•traceroute•scriptroute•Pathchar/pathneck/… BW probing tools7Sample Question: Topology•What is the topology of the network?•At the IP router layer•Without “inside” knowledge or official network maps•Without SNMP or other privileged access•Why do we care?•Often need topologies for simulation and evaluation•Intrinsic interest in how the Internet behaves•“But we built it! We should understand it”•Emergent behavior; organic growth8How Traceroute Works•Send packets with increasing TTL values•Nodes along IP layer path decrement TTL•When TTL=0, nodes return “time exceeded” message9ICMP “time exceededTTL=1TTL=2TTL=3Problems with Traceroute•Can’t unambiguously identify one-way outages•Failure to reach host : failure of reverse path?•ICMP messages may be filtered or rate-limited•IP address of “time exceeded” packet may be the outgoing interface of the return packet10TTL=1TTL=2TTL=3Famous Traceroute Pitfall•Question: What ASes does traffic traverse?•Strawman approach•Run traceroute to destination•Collect IP addresses•Use “whois” to map IP addresses to AS numbers•Thought Questions•What IP address is used to send “time exceeded” messages from routers?•How are interfaces numbered?•How accurate is whois data?11More Caveats: Topology Measurement•Routers have multiple interfaces•Measured topology is a function of vantage points•Example: Node degree•Must “alias” all interfaces to a single node•Is topology a function of vantage point?•Each vantage point forms a tree12Less Famous Traceroute Pitfall•Host sends out a sequence of packets•Each has a different destination port•Load balancers send probes along different paths•Equal cost multi-path•Per flow load balancing•Why not just use same port numbers? 13Soule et al., “Avoiding Traceroute Anomalies with Paris Traceroute”, IMC 2006Designing for Measurement•What mechanisms should routers incorporate to make traceroutes more useful?•Source IP address to “loopback” interface•AS number in time-exceeded message•??•More general question: How should the network support measurement (and management)?1415Overview•Active measurement•Passive measurement•Strategies•Some interesting observationsTwo Main Approaches•Packet-level Monitoring•Keep packet-level statistics•Examine (and potentially, log) variety of packet-level statistics. Essentially, anything in the packet.•Timing•Flow-level Monitoring•Monitor packet-by-packet (though sometimes sampled)•Keep aggregate statistics on a flow16Packet Capture: tcpdump/bpf•Put interface in promiscuous mode•Use bpf to extract packets of interest•Packets may be dropped by filter•Failure of tcpdump to keep up with filter•Failure of filter to keep up with dump speeds•Question: How to recover lost information from packet drops?1718Traffic Flow Statistics•Flow monitoring (e.g., Cisco Netflow)•Statistics about groups of related packets (e.g., same IP/TCP headers and close in time)•Recording header information, counts, and time•More detail than SNMP, less overhead than packet capture•Typically implemented directly on line cardWhat is a flow?•Source IP address•Destination IP address•Source port•Destination port•Layer 3 protocol type•TOS byte (DSCP)•Input logical interface (ifIndex)19Flow Record ContentsBasic information about the flow…•Source and
View Full Document
Unlocking...