CS 268: 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 dounderstandInternet Measurement• Process of collecting data that measure certainphenomena 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 docorrectly34Measurement Methodologies• Active tests – probe the network and see how it responds• Must be careful to ensure that your probes only measure desiredinformation (and without bias)• Labovitz routing behavior – add and withdraw routes and see howBGP 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“timeexceededTTL=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 bethe 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 vantagepoints• 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 routersincorporate to make traceroutes moreuseful?• Source IP address to “loopback” interface• AS number in time-exceeded message• ??• More general question: How should thenetwork support measurement (andmanagement)?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 sometimessampled)• Keep aggregate statistics on a flow16Packet Capture: tcpdump/bpf• Put interface in promiscuousmode• Use bpf to extract packets ofinterest• Packets may be dropped byfilter• Failure of tcpdump to keep upwith filter• Failure of filter to keep up withdump speeds• Question: How to recoverlost information from packetdrops?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 thanpacket 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 Destination, IP address and port• Packet and byte counts• Start and end times• ToS, TCP flags…plus, information related to routing• Next-hop IP address• Source and destination AS• Source and destination prefix2021flow 1 flow 2 flow 3flow 4Aggregating Packets into Flows• Criteria 1: Set of packets that “belong together”• Source/destination IP addresses and port numbers• Same protocol, ToS bits, …• Same input/output interfaces at a router (if known)• Criteria 2: Packets that are “close” together in time• Maximum inter-packet spacing (e.g., 15 sec, 30 sec)• Example: flows 2 and 4 are different flows due to timePacket Sampling• Packet sampling before flow creation (Sampled Netflow)• 1-out-of-m sampling of individual packets (e.g., m=100)• Create of flow records over the sampled packets• Reducing overhead• Avoid per-packet overhead on (m-1)/m packets• Avoid creating records for a large number of small flows• Increasing overhead (in some cases)• May split some long transfers into
View Full Document
Unlocking...