Transcript PowerPoint version of Dr. Partridge`s presentation

Data Communications vs.
Distributed Computing
Dr. Craig Partridge
Chief Scientist, BBN Technologies
Chair, ACM SIGCOMM
A Quick History
 In the 1980s, the data comm community
largely stopped leading in network
application development
• Overwhelmed by lower layer research
problems
 Other communities stepped in:
• OS and distributed systems
• Supercomputing and physics
An unfortunate side effect
 The two fields most expert in networking
don’t talk as much as they should
 Indeed, I was invited to talk here because it
was considered nice to have a networking
perspective...
What’s new in networking
 So what have those networking guys been
up to for the past ten years or so???
 One person’s perspective
 I’ve tried to focus on fun topics
• So nothing on TCP performance
– Most problems are configurational
Self Similarity
 Trouble with queueing theory
• By late 1980s, clear that classic models didn’t
work for data traffic
• Off by factors of 10 or 100 in queue size
estimates
 Enter Leland, Taqqu, Willinger & Wilson
(‘93)
• Data traffic is self-similar (fractal)
Self Similarity Example
More Self Similarity
 Self-similarity means
traffic smooths very
slowly
• traffic at 100s sample
units very similar to
traffic at 0.01 second
samples
 High peak to mean
ratios
Self Similarity in practice
 Since 1993, we’ve been working to reduce
self similarity to practice
• Confirming it exists on various types of
networks
• Creating generator functions for modeling
• Understanding why it exists
Quality of Service
 A term whose definition is evolving
•
•
•
•
Bandwidth guarantee?
Loss guarantee?
Delay guarantee?
All three?
The QoS Challenge
 How to do QoS in a self-similar world?
• Old style Poisson aggregation doesn’t work
unless the network loads are very very large
 QoS Triumph
• Weighted Fair Queuing (Demers, Keshav,
Shenker)
• PGPS by Parekh
Weighted Fair Queuing
 A delightful insight
• Transform bit-wise sharing of links into
packetized sharing
• Work conserving!
 Nicely enough, all other work conserving
schemes have been shown to be variants of
WFQ
Fair Queuing Diagram
Bit by Bit
Fair Q’ing
WFQ Diagram
Bit by Bit
WFQ
PGPS
 Packetized General Processor Sharing
• Work by Parekh
 If traffic conforms to a (general) arrival
model, we can derive the upper bound on
queuing delay
• At high speeds, bound is nearly independent of
number of queues in the path
What Next for QoS?
 WFQ is expensive to implement
• Though good approximations exist
 General feeling that WFQ+PGPS is overkill
• Something simpler should be possible
• The community is working through various
statistical guarantees
High Performance
 Around 1991, the accepted wisdom was that
IP was dead because routers couldn’t go
fast
 Now, widely accepted that routers can
achieve petabit speeds
What Happened?
 Mostly, good engineering
• Router innards re-engineered for speed
 But also some new prefix lookup
algorithms
• Luleå algorithm
• WashU algorithm
Ad-Hoc Networks
 A new and exciting area
• Imagine thousand or millions of wireless
nodes in a room
• They’re moving
• They need to discover and federate (securely)
• Managing signal/noise ratio vital for
performance
More on Ad-Hoc Networks
 Odd desire to say we’re done
• Jini
• Existing ad-hoc routing protocols
 Yet the problems remain huge
• Device location hard (user interface harder)
• Density challenges existing protocols
• Clashes over spectrum
Robustness
 To keep the Internet robust we must
• Improve device reliability by factor of 10 every
two years; OR
• Improve our protocols to be more resilient
– Assuming something is always going up or down
– How to minimize impact
– In traffic
– In performance
 Can PODC community help here?
Lots of other initiatives
 Simulation
•
How do you simulate something 100 times bigger than anything ever built?
 Measurement
•
How much can you learn just from the edge of the network?
 Errors
•
Packets damaged frequently, what to do?
 Anycast
•
Nice idea, how do we make it real?
The Last Slide
 There’s lots of fun work in networking
• A lot has been happening
• A lot will happen
 Some of the problems are also of interest to
the PODC community
• I look forward to talking with you about them.