Transcript Slide 1

ECE 526 – Network
Processing Systems Design
Network Processing Functions
Chapter 6&9: D. E. Comer
Packet Processing Functions
• Basic network system functionality
─
─
─
─
─
─
─
─
─
─
Address lookup
Packet forwarding
Fragmentation and re-assembly
Security
Error detection and correction
Queuing
Scheduling
Protocol de-multiplexing
Packet classification
Traffic measurement (Lab 2)
Ning Weng
ECE 526
2
Outline
•
•
•
•
Error detection and correction
Queueing
Scheduling
Packet classification
─ Inefficiency of packet de-multiplexing
─ Classification implementation schemes
• Summary
Ning Weng
ECE 526
3
Error Detection and Correction
• Bit errors can occur in packet
• Layer 2
─ Cyclic Redundancy Check (CRC)
• Layer 3
─ Header checksum
• Significant computation overhead
─ Layer 2 CRC done in hardware
─ Layer 3 checksum computed over packet header only
• Error correction not performed by network system
─ Even more overhead
─ Error correction handled by upper layers
Ning Weng
ECE 526
4
Queueing
• Referred to policies, data structure and algorithms
related to storing and selecting packets
• Packet processing- store and forward
─ Incoming packet placed in incoming queue
─ Outgoing packet placed in output queue
• When queue full, packets are discarded
• Recall: queuing is one source of packet delay
• Basic questions about queuing
─
─
─
─
What is the right size of each queue?
How many queue needed?
Where to place queues physically?
How to implement priority policy?
Ning Weng
ECE 526
5
Queueing Priority
• Multiple queues used to enforce priority
• Incoming packet
─ Assigned priority as function of packet content, size or security
─ Placed in appropriate priority queue
• Queueing discipline
─ Examining priority queues
─ Chooses which packet to send
─ Drop/discard policy: tail drop
Ning Weng
ECE 526
6
Queueing Disciplines
• Priority Queueing
─ Assign unique priority number to each queue
─ Choose packet from highest priority queue which is nonempty
─ Known as strict priority queueing -> starvation
• Weighted Round Robin (WRR)
─ Assign unique priority number to each queue
─ Process all queues round-robin
─ Compute N, max number of packets to select from a queue proportional to
priority
─ Take up to N packet for processing before moving to next queue
─ Does this work well?
• Weighed Fair Queueing (WFQ)
─ Use packet size rather than number of packets
─ Allocates priority to data amount of from a queue rather than number of
packets
Ning Weng
ECE 526
7
Scheduling
• Co-ordination of activities in network systems
• Two types
─ Link (queue) scheduling
─ Resource scheduling
• Resource allocation
─ Processing on multiple packets
─ Processing on multiple protocols
─ Multiple processors
• Scheduling attempts to achieve fairness
Ning Weng
ECE 526
8
source
message
segment Ht
datagram Hn Ht
frame
Hl Hn Ht
M
M
M
M
Encapsulation
application
transport
network
link
physical
Hl Hn Ht
M
link
physical
Hl Hn Ht
M
switch
destination
M
Ht
M
Hn Ht
Hl Hn Ht
M
M
Ning Weng
application
transport
network
link
physical
Hn Ht
Hl Hn Ht
M
M
network
link
physical
Hn Ht
Hl Hn Ht
M
M
router
ECE 526
9
Protocol Demultiplexing
• Used with layered protocols
• Protocols at each layer of stack are differentiated with
type information at lower layer
─ Example: layer 3 – IP, ARP based on Ethernet type
• Layered processing
─ On output side (sender), type field in each header specifies
encapsulation.
─ On input side (receiver), software in each layer chooses module
at next higher layer.
─ Layered processing is inefficient since we have to go through all
stacks sequentially
• Can we do better?
Ning Weng
ECE 526
10
Packet Classification
• Alternative to demultiplexing for higher speed
• Idea
─ All layer header information available (no dependency)
─ Can we process layer headers at different sequence (reorder!)
─ Can we consider all layer header at the same time (parallel!)
• Classification
─ Mapping packet into categories
─ Based on header information from mixed layer
• Rule based
─ Example:
• five-tuple flow classification
• Web traffic
Ning Weng
ECE 526
11
Classification: Software Version
• Compare values in header fields
• Conceptually a logic and of all fields comparisons
• Example: web traffic
─ three classification rules required
If ((frame type == 0x800) && (IP type ==6) && (TCP port ==80)
packet matched classification
else
packet does not match classification
• Can we do better?
Ning Weng
ECE 526
12
Classification: Software Optimization
Ning Weng
ECE 526
13
Classification: Hardware Version
• Specific hardware
• Extract required fields parallel
Ning Weng
ECE 526
14
Classification: Hybrid Version
• Hardware and software combination
─ Hardware for standard cases
─ Software for exceptions
Ning Weng
ECE 526
15
Summary
•
•
•
•
•
Finish overview of the major packet processing functions
Error detection and correction are expensive
Queuing and queuing disciplines
Scheduling and fairness
Difference between demultiplexing and classification
─ Sequential tour layers vs. parallel scan
Ning Weng
ECE 526
16
Network Measurements
• Why do we need measurements?
─
─
─
─
─
─
Debugging
Performance tuning
Discovery of network structure
Understanding of network behavior (reverse-engineering)
Discovery of security holes and attacks
Etc.
• How can we measure networks?
─ Inject packets and see what happens (active measurement)
─ Observe traffic (passive measurement)
• What are pros and cons of measurement?
Ning Weng
ECE 526
17
Active Measurement
• Metrics that can be measured
─
─
─
─
─
─
Connectivity
Round-trip time
Loss rate
Reordering
Available bandwidth
Bandwidth capacity
• Some metrics are available per-hop, others only end-toend
• Some tools need software on both sides of
measurement
Ning Weng
ECE 526
18
Passive Measurement
• Tcpdump is an example of passive network
measurement
• Passive measurement consists of several phases
─ Data collection
─ Data storage
─ Extraction and calculation of metrics
• Passive measurement metrics
─ Traffic volume (link utilization)
─ Traffic mix (e.g., by protocol type, by destination)
─ TCP flow behavior (packet retransmissions)
• Passive measurement challenges?
─ Data rates to process
─ Only partial view of network
─ Staleness of data
Ning Weng
ECE 526
19
Lab2: Network Traffic Monitoring &
Performance Measurement
• Goals
─ Learn basic network tools
─ Understand packet structure by watching real packets
─ Get real performance number
• Tools
─ Ping: a program verifying the existence of IP address
• Used for packet generator and delay measurement
─ Traceroute: a program tracing the route from sender to destination
• Used for delay measurement and route bottleneck identifier
─ Ethereal: network protocol analyzer
─ Iperf: a tool to measure the maximum throughput between client and
server
Ning Weng
ECE 526
20
Connectivity
• Simples case of active measurement
• Typically done with ICMP Echo Request
─ Recipient will reply with ICMP Echo Response
• Implemented in ping tool:
─ Sends ICMP echo requests to specified IP address
─ Prints responses
─ Reports TTL, round-trip time, loss rate (both ways)
• Useful parameters
─ -c or -n count
─ On Unix: -n numeric output (no IP address translation)
─ -f flood ping ☺
• Very common and useful tool
Ning Weng
ECE 526
21
Ping
• Sending ICMP “echo request” packets to the target host
and listening for ICMP “echo response” replies
• Using interval timing and response rate, ping estimates
the round-trip time and packet loss
Ning Weng
ECE 526
22
Ping Limitations
• What are the limitations of ping?
─
─
─
─
ICMP disabled
NAT boxes / firewalls
No information on route (other than TTL)
No information on performance (other than RTT)
• Other interesting observations
─ TTL in packets can reveal OS type (useful for hackers)
Ning Weng
ECE 526
23
Route
• How can route of packet be measured?
• Traceroute approach:
─
─
─
─
Send packets with limited TTL towards destination
Packets will “expire” and cause ICMP error message
Source of error message is intermediate hop
Repeat with increasing TTL
• Output:
─ Each router with RTT
Ning Weng
ECE 526
24
Traceroute
• To determine the route taken by packets across an IP
network.
• working by increasing the "time-to-live" value of each
successive batch of packets sent
• Host discards the packet and sends an ICMP time
exceeded packet when TTL = 0
• Using these returning packets to produce a list of hosts
that the packets have traversed en route to the
destination
• IP does not guarantee that all the packets take the same
route.
Ning Weng
ECE 526
25
Ning Weng
ECE 526
26
Traceroute Limitation
• Not all routers respond
• Processing, control and queue leads to wrong TTL
results
Ning Weng
ECE 526
27
tcpdump
• Passive network measurement tool: tcpdump
• Tcpdump collects packets from interface and displays headers
─
─
─
─
─
Only one interface can be observed at any point of time
All traffic on interface can bee seen (promiscuous mode)
Filter allows pre-filtering of output
Payload can be preserved (if necessary)
Timestamp of packet arrival and transmission
• Very useful to check network setup
• Useful options
─
─
─
─
-n no address translation
-r and -w to read and write files
-s determines length of preserved data
-vv very verbose output
• Results can be displayed nicely with ethereal
Ning Weng
ECE 526
28
Ethereal
Ning Weng
ECE 526
29
Bandwidth
• How to measure bandwidth?
─
─
─
─
TCP vs. UDP
Inject packets at high rates
Reporting of result?
Requires software on both sides
• Issues to consider
─
─
─
─
Measurement reports currently available bandwidth
Reports only bottleneck bandwidth
TCP behavior needs to be considered
Timing of UDP packet is critical
• Tool: iperf (and many others)
─ Client acts as sender
─ Server sinks traffic and reports statistics
Ning Weng
ECE 526
30
iperf
• Iperf report
• Iperf options
─
─
─
─
─
-s run as server
-c run as client
-u uses UDP instead of TCP
Man other options for packet size and rate (UDP)
-b binds output interface (very useful)
Ning Weng
ECE 526
31
Iperf
• > iperf -c 10.0.13.68
• results should look like this:
-----------------------------------------------------------Client connecting to 10.0.13.68, TCP port 5001
TCP window size: 8.00 KByte (default)
-----------------------------------------------------------[1924] local (your IP) port 1500 connected with
10.0.13.68 port 5001
[ ID] Interval Transfer Bandwidth
[1924] 0.0-10.0 sec 111 MBytes 92.9 Mbits/sec
• You're interested in the red numbers
Ning Weng
ECE 526
32
iperf Limitations
• What are the limitations of iperf?
─ Same as for any other bandwidth measurement tool
─ Control overhead
─ Many options -> possible misconfiguration
• Need tool to observe network traffic to verify correct
measurement setup
Ning Weng
ECE 526
33
Hyperion Project
• Distributed passive measurement platform
─ Multiple measurement node in network
─ Coordinated traffic collection and storage
• Performance challenge
─ Extraction, storage, and retrieval requires high performance
• Network processors can be used for extraction and preprocessing
Ning Weng
ECE 526
34
Hyperion Node Architecture
Ning Weng
ECE 526
35
Privacy Issues
• Passive measurements observe all traffic in network
─ Users have rights to privacy
─ Measurement data can reveal lots of personal information
• Examples of personal information
─
─
─
─
Web pages visited
Usernames and passwords (if not encrypted)
Emails, IM, etc.
Even encrypted traffic reveals information
• One possible solution: anonymization of traces
─ “Scramble” IP addresses
─ Prefix-preserving hashing is preferable over random hashing
─ Computationally expensive
Ning Weng
ECE 526
36