Transcript ppt - Computer Science Division

Exploiting Packet Header Redundancy for
Zero Cost Dissemination of Dynamic
Resource Information
Peter A. Dinda
Prescience Lab
Department of Computer Science
Northwestern University
http://www.cs.northwestern.edu/~pdinda
Overview
• Piggyback information on outgoing packets
• Encode information into redundant or unused
TCP, IP, and Ethernet fields
• Result: Disseminate information with no
additional packets or increased packet size
• Identified: >=86 bits per packet
• Proof-of-concept: 17 bits per packet
2
Outline
•
•
•
•
•
•
•
Disseminating dynamic resource info
Theoretical redundancy
Mechanisms for exploiting redundancy
Prospects
Proof-of-concept
Using the mechanisms
Conclusion and future work
3
Disseminating Dynamic Resource Information
Consumer
Sensor
Network
Consumer
Consumer
4
Current Model
Sensor
App
App
Consumer
Transport
Network
Data Link
Transport
Network
Data Link
Physical
Physical
Sensor is just another application
5
Problems With Current Model
• Bandwidth consumption
– Can be reduced via adaptive techniques
– Different available BW to different consumers
• Additional packets injected into network
• Consumers must know to ask for data
But packets already flow through the network!
6
Proposed Model
Sensor
App
Transport
Network
App
Transport
Network
Header
Editing
Data
Extraction
Data Link
Physical
Data Link
Physical
Consumer
Sensor data piggybacked on application packets
7
Header Editing
Sensor Data
Ethernet
IP
TCP
Data
Padding
Overwrite unused or redundant fields with sensor data
How much redundancy is there and how do we exploit it?
8
Packet Traces
• NLANR Passive Measurement Network
• All packets at points of presence
• 28 90 second traces
– 4 sites (U. Buffalo, Columbia, Colorado
State, U. Memphis)
– Late September, 2001
– 68,000 to 3 million packets per trace
9
How Much Redundancy Is There?
• Headers as a sequence of 1 byte symbols
• Shannon entropy
– Number of bits needed per symbol
– Does not capture correlation
• Mutual information
– Bits per byte assuming one-step correlations
Evaluate the theoretical limits to redundancy
10
Redundancy in IP Headers
• Shannon entropy: 4.8 bits per byte
– 40 % redundant
– 8 extra bytes per header
• Mutual information: 1.2 bits per byte
– 85 % redundant
– 17 extra bytes per header
Considerable redundancy is available
How does this redundancy manifest in practical ways?
11
Practical Mechanisms: TCP Header
source port
destination port
sequence number
acknowledgement number
hlen reserved flags
window size
checksum
urgent pointer
options
Mechanism
Bits
Reserved bits
6
Ack field when ACK=0
32
Urgent field when URG=0
16
NOP option padding
varies
Total
>=54
12
Prospects: TCP Header
source port
destination port
sequence number
acknowledgement number
hlen reserved flags
window size
checksum
urgent pointer
options
Mechanism
Bits
Reserved bits
6
NOP option padding
Always Zero!
32
Untested
16
Untested
varies Options rare
Total
>=54
Ack field when ACK=0
Urgent field when URG=0
13
Practical Mechanisms: IP Header
vers hlen
TOS
length
flags fragment offset
identifier
TTL
protocol
checksum
source address
destination address
options
Mechanism
Bits
Reserved TOS bits
2
Reserved IP flag
1
Identifier when DF=1
16
Fragment offset when DF=1
13
NOP option padding
varies
Total
>=32
14
Prospects: IP Header
vers hlen
TOS
length
flags fragment offset
identifier
TTL
protocol
checksum
source address
destination address
options
Mechanism
Bits
Reserved TOS bits
2
NOP option padding
95% Zero
1
Always zero
16
90% DF=1
90% DF=1
13
varies Options rare
Total
>=32
Reserved IP flag
Identifier when DF=1
Fragment offset when DF=1
15
Practical Mechanisms: Ethernet Padding
Ethernet
IP
TCP
Data
Padding
Ethernet frame’s data must be at least 46 bytes long
TCP+IP+keystroke = 20+20+1 = 41 bytes
TCP ACK = 20+20 = 40 bytes
Prospects: Untested
16
Proof-of-concept
• Evaluate IP Header approaches
• Random bit source for data
• Minet user-level stack
– ~20 lines of header-editing/data extraction code
– ~200 lines of ancillary code (output)
• Study interaction with Linux stack (2.2
kernel) and Cisco router
17
Proof-of-concept results
Bits
Minet to
Linux
Minet to
Router
to Minet
Minet to
Router
to Linux
Demonstrated
bits
Reserved TOS bits
2
OK
FAILS
OK
0
Reserved IP flag
1
OK
OK
OK
1
Identifier when DF=1
16
OK
OK
OK
16
Fragment offset when DF=1
13
FAILS
FAILS
FAILS
0
NOP option padding
varies
untested
untested
untested
0
Total
>=32
Mechanism
17
IP Header can transport 17 extra bits 90% of the time
What should we use them for?
18
Using the Bits
• 1 sample per packet
– Host load: 1.4-15 bits per sample
– Network bandwidth / latency: ?
– Sample resolution can be varied
• Timestamps
– Easy for TCP packets – use RTT estimate
19
Using the Bits
• Using this channel to transport streams
• Unreliable like IP
• Also can’t choose where/when data is sent
– Only goes to “friendly” hosts
– Or have to wait until someone sends a packet
to the machine you are targeting
• What are appropriate coding approaches?
20
Diffusion
Sensor
Random
Drop
Header
Editing
App
Transport
Network
Consumer
Data
Extraction
Data Link
Physical
Information diffuses out from a sensor to “friendly” hosts
21
Conclusions and Future Work
• Introduced concept of exploiting packet
header redundancy for zero cost
information dissemination
– Intentionally extreme approach
• Identified mechanisms and prospects
• Demonstrated proof-of-concept
• Future work: Linux kernel implementation
22
For More
Information
• Peter Dinda
– http://www.cs.northwestern.edu/~pdinda
• Minet
– http://www.cs.northwestern.edu/~pdinda/minet/
• Prescience Lab
– http://www.cs.northwestern.edu/~plab
23