Open Questions on Distributed Computing and Networking
Tremendous success of the Internet has enabled innovation in various applications, but the infrastructure has remained stagnant. Challenges in innovation include closed equipment, slow protocol standardization, and limited innovators in the field. Software Defined Networking (SDN) presents a new paradigm with a logically centralized controller and fast, hardware-based switches, aiming to address the limitations of traditional computer networks.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Some Open Questions on the Borderline of Distributed Computing and Networking Michael Schapira School of Computer Science and Engineering Hebrew University of Jerusalem
This Talk 1. New questions in Internet protocol design 2. Self-stabilizing Internet protocols 3. Incentive-compatible network protocols illustrated via Internet routing examples
The Internet Tremendous success from research experiment to global infrastructure Enables innovation in applications Web, P2P, VoIP, social networks, virtual worlds But, the Internet infrastructure fairly stagnant for decades
Why Cant We Innovate? Closed equipment software bundled with hardware vendor-specific interfaces Slow protocol standardization Few people can innovate equipment vendors write the code long delays to introduce new features
Traditional Computer Networks data plane: packet streaming Handle packets in real time : forward, filter, buffer, mark, rate-limit, measure,
Traditional Computer Networks control plane: distributed algorithms slower time scale: track topology changes, compute routes, install forwarding rules,
Software Defined Networking (SDN): a New Paradigm Controller: logically-centralized control, smart, slow, implemented in software, API to the data plane (e.g., OpenFlow) Switch: dumb, fast, implemented in hardware
Software Defined Networking (SDN): a New Paradigm Controller Application Network OS events from switches topology changes, traffic statistics, arriving packets, commands to switches (un)install rules, query statistics, 8
So Change is finally on the horizon But many challenges remain Realizing SDN (e.g., distribute the controller?) What are the right protocols (for routing, traffic engineering, etc.)? Distributed computing theory can play an important role here
Distributed Controller? for scalability and reliability Controller Application Controller Application partition and replicate state Network OS Network OS Elect a leader? Distribute the computation? How to ensure consistency (across controllers / switches)? Where to place the controller(s)? 10
Rethinking (Routing) Protocols Routing is a control plane operation slow (milliseconds seconds) Packet forwarding is a data plane operation fast (microseconds) Today s (intradomain) routing establishes connectivity optimizes routes (= shortest paths) failure re-convergence dropped packets!
Pushing Connectivity (Only!) to the Data Plane while retaining scalability implemented in hardware low overhead (end-to-end backup paths too costly ) static forwarding tables (no changes in packet rates) no change to packet header When packet to a node d arrives at node i, i s outgoing link is a function only of d i incoming link fid: Ei x P(Ei) -> Ei set of live outgoing edges
Resilient Forwarding A forwarding pattern {fid}i is t-resilient if for any (at most) t-edge-failures the existence of a path between a node i and the destination d implies loop-free forwarding from i to d. j x d i Perfect resilience t
Theoretical Perspective Thm[Feigenbaum-Godfrey-Panda-S-Shenker-Singla]: 1-resilient forwarding pattern always exists Thm[Feigenbaum-Godfrey-Panda-S-Shenker-Singla]: Perfect resilience is not achievable Big gap! does a 2-resilient forwarding pattern always exist? specific families of graphs? relax restrictions (randomness, dynamic forwarding tables, )?
Practical Perspective A perfectly-resilient mechanism for achieving connectivity in the data plane [ Data Driven Connectivity , Liu-Panda- Singla-Godfrey-S-Shenker, NSDI 2013] utilizes existing mechanisms small (few bits) changes to forwarding tables at packet rate
Directions for Future Research How to distribute the controller? Data-plane/control-plane perspective on other networking tasks (e.g., traffic engineering) Connectivity in the data plane
(Self-)Stabilizing Internet Routing
Border Gateway Protocol The Border Gateway Protocol (BGP) establishes routes between the (over 42,000) networks that make up the Internet AT&T Comcast Google Verizon
BGP Shortest-Path Routing! I want to avoid routes through Comcast if possible I won t carry traffic between AT&T and Verizon AT&T Comcast Google Verizon I want a cheap route I want short routes
Illustration: BGP Dynamics Prefer routes through 1 Prefer routes through 2 2 1 1, my route is 2d 2, I m available 1, I m available d A stable state is reached
Illustration: BGP Oscillation Prefer routes through 2 Prefer routes through 1 BGP might oscillate indefinitely between 2 1 1d, 2d and 12d, 21d 2, my route is 1d 1, my route is 2d 1, 2, I m the destination d Conjecture[Griffin-Wilfong, SIGCOMM 99]: 2+ stable states BGP can oscillate
Why are Oscillations Bad? Make the network unpredictable and hard to debug. Might lead to the flooding on the network with BGP update messages. Deteriorate performance! almost 50% of VoIP disruptions are due to BGP route fluctuations
Internet Protocols, Markets, and Beyond Often, in computational and economic environments 1. the prescribed behavior for each node (human, machine) is simple and natural 2. nodes interaction is not synchronized How can we reason about such environments? Internet protocols (BGP routing, TCP congestion control) large-scale markets social networks
Dynamics: Game Theory vs. Distributed Computing Game theory: establishes convergence to equilibrium for natural dynamics (best-/better-response, fictitious play, no- regret, ) but typically assumes synchronization. Distributed computing theory: analyzes system behavior in asynchronous environments but no general notions of natural behavior.
Simple Model n nodes1, ,n Node i has action space Ai A=A1 An A-i=A1 Ai-1 Ai+1 An Node i has reaction function fi:A-i Ai f=(f1, ,fn) fi can capture node i s best-responses
Simple Model (Cont.) Infinite sequence of discrete time steps t=1, A schedule :{1, } 2[n] maps each time step to the subset of nodes activated at that time step a fair schedule activates each node infinitely often An initial action-profile and schedule naturally induce a dynamics.
Simple Model (Cont.) Defn: An action-profile a*=(a1, ,an) is a stable state if fi(a*)=ai for all i. that is, a* is a fixed point of f abusing notation Defn: A system is convergent if for every choice of initial action-profile and fair schedule the induced dynamics converge to a stable state.
Towards a Characterization of Convergent Systems Thm [Jaggard-S-Wright]: If there exist multiple stable states, then the system is not convergent. valency argument! no failures, just dumb nodes! So, a unique stable state is a necessary condition for guaranteed convergence. Can be generalized to bounded-recall, non- stationary reaction functions.
Application: Internet Routing BGP establishes routes between the smaller networks that make up the Internet Sprint AT&T Comcast Qwest Question [Griffin-Shepherd-Wilfong, 2001]: Do multiple stable routing configurations imply the possibility of persistent route oscillations? Answer [Sami-S-Zohar, 2009]: Yes!
Other Applications Our two people in a corridor example Models of congestion control on the Internet Load balancing Diffusion of technologies in social networks Asynchronous circuits
Strengthening the Result: Convergence vs. Synchronism Defn: An r-fair schedule activates each node at least once in every r consecutive time steps Defn: A system is r-convergent if for all choices of initial action-profile and r-fair schedule the induced dynamics converges to a stable state. convergent r-convergent not r-convergence not convergent Thm [Erdmann-S]: If there exist multiple stable states, then the system is not (n-1)-convergent. tight! much more delicate valency argument
Complexity of Convergent Systems Thm [Jaggard-S-Wright]: Determining if a system with n nodes is convergent requires exponential communication (in n). Thm [Engelberg-Fabrikant-S-Wajc]: Determining if a succinctly described system is convergent is PSPACE-complete. Both results extend also to stochastic convergence .
Directions for Future Research Other protocols! Identify specific classes of (stochastically) convergent games and measure convergence rate (e.g.,in terms of asynchronous rounds). Characterize guaranteed convergence, and design algorithms for determining such convergence for other game dynamics (e.g., fictitious play, no-regret dynamics) other notions of equilibrium (e.g., mixed Nash, correlated) other notions of asynchrony
Incentive-Compatible Network Protocols
TCP Congestion Control is NOT Incentive Compatible queue link router link AIMD = Additive Increase Multiplicative Decrease
What About BGP? BGP was designed to guarantee connectivity between largely trusted and obedient parties. In today s commercial Internet ASes are owned by self-interested, often competing, entities might not follow the prescribed behaviour Simple examples show that BGP is, in fact, not incentive compatible a node can obtain a better route by lying
How Can We Fix This? Economic Mechanism Design: the reverse-engineering approach to game- theory . Goal: Incentivize players to follow the prescribed behaviour if others run the protocol so should I! without money! Thm [Levin-S-Zohar]: Secure variants of BGP are incentive compatible.
Conclusion An exciting time to be in networking Internet protocols motivate new research directions Distributed computing theory has much to contribute
