Transcript fdna03_Beck

An End-to-End Approach to Globally
Scalable Programmable Networking
Micah Beck, Assoc. Prof. & Director
Terry Moore, Assoc. Director
James S. Plank, Assoc. Prof & Director
Logistical Computing & Internetworking (LoCI) Lab
Computer Science Department
Future Directions in Net Architecture Workshop
Sept 27, 2003
What We Mean By That Title
» End-to-End: Rorschach for Networkers
• Generic functionality at intermediate nodes
• Push complex functionality to “endpoints”
» Scalability has many dimensions
• Number and distribution of nodes
• “Global” – like the Internet
» Programmable Networking
• Able to implement new functionality without
deploying new infrastructure
How to Build a Scalable Network Service
From Things You Have Around the House
» Weaken the Semantics
• Best Effort:
Availability, Correctness & Security
»Implement stronger guarantees
End-to-End
• Maximum Service Units in all dimensions
» Visible state must be generic
• Softness of state is a function of its use,
not its implementation
Review: Scalable Network Storage
» An End-to-End Approach to Globally Scalable
Network Storage, SIGCOMM 2002
Beck, M., Moore, T., and Plank, J.
» End-to-End means writer to reader
» Weak semantics: storage at server not necessarily
available, correct or secure!
• Tends to upset storage people
• Network people find it more natural
» Déjà vu: Are we reinventing file-based networks?
» “Everything I need to know I learned in Multics”
The Internet Backplane Protocol
» malloc-like allocation API; load/store/copy
» Maximum Service Units in all dimensions
• Maximum size of storage allocation
• Maximum duration of storage lease (renewable)
» Generic service: Minimal structure in stored state
• Names not semantically meaningful (long,
random)
• Servers are functionally interchangeable
» Warning: Denial of Service attacks!
» Scalable yes, but is it worth doing?
A Gratuitous Diagram
scalability
The limit of scalable functionality
Too good to be true
Not worth doing
Scalable services
functionality
Won’t scale
Scalable Programmable Networking
» Elements of Programmability
• Transforming data (computing)
• Making decisions (control)
» Computing is resource intensive
» Control is hard to scale
» Let’s start with computation
• Remote Procedure Call (client/server)
• Network services operating on flows
(send/receive)
» Warning: Denial of Service attacks!
Applying Our Methodology
» Weaken the Semantics
• Best Effort: Availability, Correctness & Security
» Implement these End-to-End
• Maximum Service Units in all dimensions
» Maximum size of input & output
» Maximum duration of computation
» Push state management to the endpoints
• Functional operations; no communication!
• IBP provides scalable state management
The Network Functional Unit (NFU)
» Exposed Service Model
• Buffer-to-buffer operations
• Must be composed with communication
» Remote Procedure Call
client
NFU operation
» Flow Service
sender
» IBP allocations can be RAM or mapped files
receiver
The NFU API (simplified)
» IBP_nfu_run(IBP_depot, NFU_op, IBP_arg_list[])
» Depot Address/port identifier
» NFU_op: numerical operation identifier
• Different implementations of same opcode must be
interchangable
» IBP_arg_list: list of allocations on called depot
• Each list element specifies
» call by reference (IBP capability) or value
» read-only or read/write
• Data types are not checked by NFU call mechanism
Dealing with State in the NFU
» Operands and results are IBP allocations
» State & side effects are possible
• But are they necessary? (use RAM buffers!)
» What operations are supported on a depot?
• Whatever application communities want
• Not necessarily homogeneous, but consistent
» How is the set of operations extended?
• Assigned names w/ fixed semantics
• Trust is required to install new operations
» Dynamic extension reduces scalability
End-to-End Guarantees: Availability
» A weak model is arbitrary outputs on failure
• Weaker still: arbitrary inputs on failure
• Stronger model: atomicity
» Transient unavailability: Retry
» Partition: redundancy in management of state
• Don’t overwrite inputs
• Checkpointing
• Transactions
Correctness: Now It Gets Difficult
»
»
»
»
»
Can computational elements be untrusted?
Generalize from Networking & Storage
These services “compute” the identity
Checksums verify the identify function
We need to verify other services
• Independent redundant computations
• Efficiently verifiable computations
» Verifiability may require redundancy in outputs
» Example: When computing a GCD, return all the
prime factors
Security is difficult, too!
» Current approaches to remote computation
require trust & authentication of the server
• Communication between client & server is
secure
• This is classical hop-by-hop security!
» This assures accountability
» End-to-end: compute without decrypting
» Is it possible? In some cases, perhaps.
» Is a dual strategy possible?
“Trust but verify”
Is This Anything? Is It Networking?
» “This no longer fits my intuition of what
networking is. This is remote access to storage or
distributed computation or something else.”
» What is networking? How did I get here?
» What do users what from the network?
• Synchronous communication
• Asynchronous communication
» Computation is sometimes required
» Implementing control is a performance issue
• Support for distributed applications
Multidimensional Networking
“… memory
locations … are
just wires turned
sideways in time”
Dan Hillis, 1982,
Why Computer
Science is No
Good
Illustrative Example: Merge Tree
M
L
Z
Y
X
K
Depot 2
Depot 1
copy
copy
K
K
L
M
X
Depot 3
merge
C
operations
in red are
initiated by
endpoint
B
X
Y stream state
Z
merge state
A
B stream state
C
A
network
endpoint
What About Performance?
» Obvious problems with client-to-depot latency
• Data & Control dependences enforced at edge
» Deep pipelining can mask latency
• Fill pipe with straight-line code
• We could even label and cache “instructions”
» When autonomy is delegated to processor, state at
depot increases
• Pseudo-processes can be created at the
discretion of the client
Related Work
» Ephemeral State Processing, Calvert, Griffioen and
Wen, SIGCOMM 2002
• 64-bit allocations; scalar operations
» Active Networking
» Agents & Mobile Code
» Distributed Operating Systems
• Remote Procedure Call
• Checkpointing & Process Migration
• State Machine Models
» Grid Computing; Peer-to-Peer
Conclusions
» Our architectural development follows a clear
architectural methodology, generalizing from IP
• The network is made up of limited-size,
unreliable, limited-duration resources
• Creation of unbounded, reliable, permanent
abstractions is difficult and costly
» Why is this so counter-intuitive?
• Networking starts from an analysis of scalability
• Computer Science usually starts from desired
functionality
» The proof of the pudding is in the tasting…