What about the Network?End-to-End Arguments in System DesignWhere to Place Functionalities?Slide 4End-to-End Argument (E2EA)Typical ExamplesBenefits of E2EAExtension of E2EAIdentifying the EndsMoving Away from E2EAOther IssuesSummaryConsensus Routing: The Internet as a Distributed SystemMotivationMotivation – Routing loopMotivation – BlackholeConsensus RoutingStable ModeStable Mode – Update LogStable Mode – Distributed SnapshotStable Mode – AggregationStable Mode – ConsensusStable Mode – FloodSlide 24Router StateTriggersDistributed CoordinationView ChangeTransient ModeRoute DeflectionOther Transient SchemesEvaluationLink FailureEffect of Traffic EngineeringOverheadDiscussion PointsCAIDA ToolsCAIDASlide 39Internet Measurement InfrastructureScamperScamper DatasetsVisualization of IPv4 Internet TopologyRRDToolRRDTool (2)BelugaWalrusThanksWhat about the Network?CS 525 Spring 2009 Advanced Distributed SystemsEnd-to-End Arguments in System DesignJ.. Saltzer, D.P. Reed and D.D. ClarkM.I.T. Laboratory for Computer SciencePresented by: Abdullah Al-NayeemWhere to Place Functionalities?•Example: Reliable file transfer•Should reliability be implemented per-hop by the communication subsystem?•Or, end-to-end by host applications?34/14/2009 Department of Computer Science, UIUCWhere to Place Functionalities?•Possible failures in file transfer:–Disk access failure (hardware)–Packet drop or duplicated packet (communication)–File system error (software)•Communication subsystem cannot itself guarantee reliability.–Also increases network complexity–More overheads for applications that do not require reliability.•Application layer can provide full reliability, even without any support from lower layers of the network.–End-to-end checksum and retry44/14/2009 Department of Computer Science, UIUCEnd-to-End Argument (E2EA)•The lower layers of the network are not the right place to implement application-specific functions–Move functions “up and out”•“The function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system. Therefore, providing that questioned function as a feature of the communication system itself is not possible.”54/14/2009 Department of Computer Science, UIUCTypical Examples•Bit error recovery•Security using encryption•Duplicate message suppression•Recovery from system crashes•Delivery acknowledgement64/14/2009 Department of Computer Science, UIUCBenefits of E2EA•Core network can be simpler and faster•Less assumptions required on the networks•More flexibility in developing new network technologies and applications–Helped in proliferation of the Internet•Dumb networks, intelligent hosts74/14/2009 Department of Computer Science, UIUCExtension of E2EA•Lower layers may implement partial application-specific functions, but only for performance improvements.–Reducing retries in data transmissions•Should the level of reliability at the network be higher than the expected application reliability?•What are the possible tradeoffs?–Short-term performance vs. long-term flexibility–Performance vs. cost84/14/2009 Department of Computer Science, UIUCIdentifying the Ends•VoIP: Human user is the end-point•File Transfer: Application is the end-point•Only the end-points knows how to guarantee required reliability4/14/2009 Department of Computer Science, UIUC 9Voice over IPVoiceFilesFile TransferMoving Away from E2EA•Hosts are not always trustworthy–Security attacks, e.g. denial of service•E2EA does not guarantee congestion control–Unfriendly host•Communications are not always between two end-points–Multicast, broadcast•How does the network handle these circumstances?104/14/2009 Department of Computer Science, UIUCOther Issues•ISP control, filtering, network monitoring•Government interventions•More subtle end points–Anonymous users using third-party services–Cloud computing entities (SaaS user, SaaS provider, Cloud provider)•Do these factor imply the end of E2EA?114/14/2009 Department of Computer Science, UIUCSummary•End-to-End argument is not an absolute, but a design tool•End-to-End argument can help in organizing “layered” communication systems.124/14/2009 Department of Computer Science, UIUCConsensus Routing: The Internet as a Distributed SystemJohn P. John1, Ethan Katz-Bassett1, Arvind Krishnamurthy1, Thomas Anderson1,Arun Venkataramani21Dept. of Computer Science, Univ. of Washington, Seattle2University of Massachusetts Amherst5th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2008Presented by: Ahmed KhurshidMotivation•Internet routing protocols (both intra and inter domain) usually favors responsiveness over consistency–A new route is incorporated in the forwarding table before propagating the same to neighbors•Results in routing loops and blackholes•Usually there is no extra effort to ensure consensus–Solutions have been proposed for intra-domain routing144/14/2009 Department of Computer Science, UIUCMotivation – Routing loop15Link failure causing BGP loops at 2 and 3Policy change causing BGP loops at 2 and 3 when 4 withdraws a prefix from 2 and 3 but not 65: 1-5, 5: 4-55: 3-4-55: 4-55: 2-4-52 prefers the path through 3 2 and 3 each prefer the other over 64/14/2009 Department of Computer Science, UIUCMinimum Route Advertisement Interval (MRAI) TimerMotivation – Blackhole16iBGP link recovery causing blackholesAP is prefered over CDRecovered4/14/2009 Department of Computer Science, UIUCCDConsensus Routing•A consistency first approach that cleanly separates safety and liveness of routing–Safety: All the routers use a consistent route towards a destination (i.e. no loops)–Liveness: Quick reaction to failures and policy changes•Uses two simple ideas to ensure both consistent behavior and quick reaction1. Runs a distributed coordination algorithm to ensure globally consistent view of routing state2. Forwards packets using one of two logically distinct modes174/14/2009 Department of Computer Science, UIUCStable Mode•Unlike BGP, consensus routing does not immediately incorporate a newly learned route into the forwarding table•Periodically, all routers engage in a distributed coordination algorithm that determine the most recent set of complete updates•The coordination is based on classical distributed snapshot and consensus
View Full Document
Unlocking...