1 Transport Overview 2/28/20122 Outline Ø Recap ❒ Overview of transport layer ❒ UDP ❒ Reliable data transfer, the stop-and-wait protocolRecap: the Lookup Problem ¦ Unstructured P2P design ¦ Napster (central query server) ¦ Gnutella (decentralized, flooding) ¦ Freenet (search by routing) • Kleinberg theorem ❒ Structured P2P design (search by routing) ❍ Chord (a ring) ❍ CAN (zones) 3Recap: the Scalability Problem ❒ Objective o Utilize resources of end hosts ❒ Requirements o Efficiency o Robustness o Incentive 4 servers C0 client 1 client 2 client 3 client n C1 C2 C3 CnRecap: BitTorrent ❒ If peer B has a piece that peer A needs, peer A sends interested to B ❒ unchoke: indicate that B allows A to request ❒ request: A requests a specific block from B ❒ piece: specific data 5 1.interested/ 3. request 2. unchoke/ 4. piece http://www.bittorrent.org/beps/bep_0003.htmlKey Design Points ❒ request: ❍ which data blocks to request? ❒ unchoke: ❍ which peers to serve? 1.interested/ 3. request 2. unchoke/ 4. pieceRequest: Block Availability ❒ Request (local) rarest first ❍ achieves the fastest replication of rare pieces ❍ obtain something of valueBlock Availability: Revisions ❒ When downloading starts (first 4 pieces): choose at random and request them from the peers ❍ get pieces as quickly as possible ❍ obtain something to offer to others ❒ Endgame mode ❍ defense against the “last-block problem”: cannot finish because missing a few last pieces ❍ send requests for missing pieces to all peers in our peer list ❍ send cancel messages upon receipt of a pieceBitTorrent: Unchoke q Periodically (typically every 10 seconds) calculate data-receiving rates from all peers q Upload to (unchoke) the fastest - constant number (4) of unchoking slots - partition upload bw equally among unchoked commonly referred to as “tit-for-tat” strategy 1.interested/ 3. request 2. unchoke/ 4. pieceOptimistic Unchoking ❒ Periodically select a peer at random and upload to it ❍ typically every 3 unchoking rounds (30 seconds) ❒ Multi-purpose mechanism ❍ allow bootstrapping of new clients ❍ continuously look for the fastest peers (exploitation vs exploration)BitTorrent Fluid Analysis ❒ Normalize file size to 1 ❒ x(t): number of downloaders (also known as leechers) who do not have all pieces ❒ y(t): number of seeds in the system at time t. ❒ λ: the arrival rate of new requests. ❒ µ: the uploading bandwidth of a given peer. ❒ c: the downloading bandwidth of a given peer, assume c ≥ µ. ❒ θ: the rate at which downloaders abort download. ❒ γ: the rate at which seeds leave the system. ❒ η: indicates the effectiveness of downloader sharing, η takes values in [0, 1]. 11System Evolution Solving steady state: Define 12System Evolution: Download Time T ❒ Look at system state, # of downloaders that will finish download and become seed: => 13BitTorrent: Summary ❒ Very widely used ❍ mainline: written in Python ❍ Azureus and µTorrent: the most popular ❍ Other popular clients: ABC, BitComet, BitLord, BitTornado, Opera browser ❒ Many explorations, e.g., ❍ BitThief ❍ BitTyrant ❒ Better understanding is needed requests/ interests requests/ interests requests/ interests requests/ interests requests/ interests 14Summary: P2P ❒ Many issues remaining, e.g., ❍ Streaming ❍ ISP/P2P integration ❍ … 1516 Outline ❒ Recap Ø Overview of transport layer ❒ UDP ❒ Reliable data transfer, the stop-and-go protocols17 Transport Layer vs. Network Layer ❒ Provide logical communication between app’ processes ❒ Transport protocols run in end systems ❍ send side: breaks app messages into segments, passes to network layer ❍ rcv side: reassembles segments into messages, passes to app layer ❒ Transport vs. network layer services: ❍ Network layer: data transfer between end systems ❍ Transport layer: data transfer between processes • relies on, enhances network layer services application transport network data link physical application transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical18 Transport Layer Services and Protocols ❒ Reliable, in-order delivery (TCP) ❍ multiplexing ❍ reliability and connection setup ❍ congestion control ❍ flow control ❒ Unreliable, unordered delivery: UDP ❍ multiplexing ❒ Services not available: ❍ delay guarantees ❍ bandwidth guarantees19 Transport Layer: Road Ahead ❒ Class 1: ❍ transport layer services ❍ connectionless transport: UDP ❍ sliding window reliability ❍ reliable data transfer using stop-and-wait ❒ Class 2: ❍ TCP reliability • overview of TCP • TCP RTT measurement • TCP connection management20 Outline ❒ Recap ❒ Overview of transport layer Ø UDP ❒ Reliable data transfer, the stop-and-go protocolsUDP: User Datagram Protocol [RFC 768] ❒ Often used for streaming multimedia apps ❍ loss tolerant ❍ rate sensitive ❒ Other UDP uses ❍ DNS ❍ SNMP source port # dest port # 32 bits Application data (message) UDP segment format length checksum Length, in bytes of UDP segment, including headerUDP Checksum Sender: ❒ treat segment contents as sequence of 16-bit integers ❒ checksum: addition of segment contents to be zero ❒ sender puts checksum value into UDP checksum field Receiver: ❒ compute checksum of received segment ❒ compute sum of segment and checksum; check if sum zero ❍ NO - error detected ❍ YES - no error detected. But maybe errors nonetheless? Goal: end-to-end detection of “errors” (e.g., flipped bits) in transmitted segmentOne’s Complement Arithmetic ❒ UDP checksum is based on one’s complement arithmetic ❍ one’s complement was a common representation of signed numbers in early computers ❒ One’s complement representation ❍ bit-wise NOT for negative numbers ❍ example: assume 8 bits • 00000000: 0 • 00000001: 1 • 01111111: 127 • 10000000: ? •