11The importance of the network• From a distributed systems standpoint, the physical network provides the backbone for overlays.– Distributed systems developers take for granted that a node can talk (reliably, if need be) to any other node in the same physically connected component via some identifier (say, IP address)• Tools, such as network coordinates, can help developersOverlay ViewPhysical Network View2End-to-End Arguments in System DesignJ.H. SaltzerD.P. ReedD.D. ClarkCS525: What about the network?3Overview1. The end-to-end argument2. Examples/applications of the argument3. Discussion4Function placement• Should functions that end users/applications perform be implemented at lower or higher levels?– If we want to transfer a file reliably, what should be the job of each computer subsystem?– How about encryption? Delivery Acknowledgement? Duplicate message suppression?5End-to-end argumentThe 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. (Sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.)6Careful file transferComputer AComputer B27Careful file transferComputer AComputer BF1) File transfer program on A asks file system to read F from disk8Careful file transferComputer AComputer B1) File transfer program on A asks file system to read F from disk2) File transfer program on A asks communication system to send fileF9Careful file transferComputer AComputer B1) File transfer program on A asks file system to read F from disk2) File transfer program on A asks communication system to send file3) Communication system transmits packets10Careful file transferComputer AComputer B1) File transfer program on A asks file system to read F from disk2) File transfer program on A asks communication system to send file3) Communication system transmits packets4) Communication system gives F to file transfer program on BF11Careful file transferComputer AComputer B1) File transfer program on A asks file system to read F from disk2) File transfer program on A asks communication system to send file3) Communication system transmits packets4) Communication system gives F to file transfer program on B5) File transfer program on B asks file system to write F to diskF12What can go wrong?Computer AComputer BA AA) Reading to and writing from file system313What can go wrong?Computer AComputer BA AA) Reading to and writing from file systemB) Breaking up file / reassembling fileBB14What can go wrong?Computer AComputer BA AA) Reading to and writing from file systemB) Breaking up file / reassembling fileC) Transmitting file over communication systemBCB15Possible solution #1• Ensure each step by some form of error checking: duplicate copies, redundancy, timeout and retry, etc.– Packet error checking at each hop– Send every packet three times– Acknowledge packet reception at each hop16Problems with this solution1. Not complete; still requires application level checking2. May not be economicalComputer AComputer BA ABB17Possible solution #2• “End-to-end check and retry”– Application commits or retries based on checksum value.– If errors along the way are rare, this will most likely finish on first try. 18Performance• Lower levels can be reliable as a performance booster– Transferring large files– Regardless of data communication, end-to-end check must be done• Tradeoff based on performance, not correctness– Is the amount of effort put into the reliability worth the performance gain?419Delivery guarantee• ARPANET returns RFNM to acknowledge successful message delivery– Is this really useful to end application?Computer A Computer B Computer A Computer Bmessage messageRFNMgot it20Data encryption1. Communication system needs keys2. Cleartext at host, before application3. Authenticity check must be performedComputer AComputer B21Data encryption1. Keys are maintained by end application2. Ciphertext before application3. Authenticity by default (assuming both keys are private)Computer AComputer B22Identifying the ends• Low level bit checking is bad for real-time voice transfer: high level error checking is better.• However, low level reliability measures may be fine is voice is being stored.23Discussion: Layering model• TCP (usually) runs only at end hosts• Does TCP violate end-to-end by being below application?• Is giving the application the option of TCP or UDP the way to go?ApplicationTransportNetworkData LinkPhysicalApplicationTransportNetworkData LinkPhysicalNetworkData LinkPhysicalComputer A Computer BRouter24Discussion: TCP splitting• Performance much better in wired section• Intermediate node acts as end host• What else can we do?Computer BComputer A525Discussion: Spam• The end user for email is generally considered to be a human.• By the end-to-end argument, the network should deliver all mail to the user.• Are spam control mechanisms therefore in violation of the end-to-end argument?– If so, is it an appropriate violation?26Discussion: End-to-end today• Is the end-to-end argument still valid today?– Is hardware good enough that we don’t have to worry about end checks?– Applications are becoming more and more complex.• Do P2P systems, such as Chord, violate end-to-end?• Does in-network aggregation, such as in sensor networks, violate end-to-end?27Stable and Accurate Network CoordinatesJ. Ledlie et al. (Harvard University)In International Conference onDistributed Computing Systems (ICDCS’06)Some slides taken from the author’s presentation28Outline Background Two Practical Problems1. Latencies are not static2. Changing coordinates is expensive Proposed Solutions1. Latency Filter2. Update Filter Conclusion29Outline Background Two Practical Problems1. Latencies are not static2. Changing coordinates is expensive Proposed Solutions1. Latency Filter2. Update Filter Conclusion30Motivation of Network CoordinatesA BDCGIEF(0,8)(20,20)(-15,20)(25,8)(-40,20)(-25,-17)(20,-15)H(9,-20)(-39,7)Pick server with lowest mean latency for all players.RTTABDirect measurement is not scalable!PlayerGame ServerUse centroid of network coordinates! – Server APredict latency by coordinates631Benefits of NCs
View Full Document