15-441: Computer NetworkingOverviewMulticast IssuesLoss RecoveryImplosionRetransmissionExposureIdeal Recovery ModelAside: Using the RoutersSlide 10Scalable Reliable Multicast (SRM)SRM Request SuppressionRequest DampingSRM Star TopologySRM (Summary)What’s Missing?Local RecoveryReliable Multicast Transport Protocol (RMTP)RMTP: Fixed HierarchyRMTP: CommentsPragmatic General MulticastPragmatic General MulticastLight-weight Multicast Service (LMS)LMS: DefinitionsLMS with Replier LinksSlide 26Slide 27Multicast Congestion ControlVideo Adaptation: RLMLayered Media StreamsDrop Policies for Layered MulticastRLM IntuitionSlide 33Receiver-Driven Layered MulticastRLM Join ExperimentJoin ExperimentsSlide 37MotivationContent Distribution NetworksHow Akamai WorksSlide 41Slide 42Slide 43Akamai – Subsequent RequestsConsistent HashConsistent Hash – ExampleSlide 47Peer-to-peer networksExample: NapsterExample: GnutellaExample: FreenetFreenet QueryFreenet FeaturesFreenet SummaryConclusions15-441: Computer NetworkingLecture 25: Multicast Challenges, CDN and P2P systems01/14/192Overview•Multicast Challenges•Content Distribution Networks•Peer-to-Peer Networks01/14/193Multicast Issues•Reliable transfer•ACK/NACK Implosion•Exposure•Reliable Multicast Protocols•Scalable Reliable Multicast •Reliable Multicast Transport Protocol•Pragmatic General Multicast•Lightweight Multicast Service•Congestion control01/14/194Loss Recovery•Sender-reliable•Wait for ACKs from all receivers. Re-send on timeout or selective ACK•Per receiver state in sender not scalable•ACK implosion•Receiver-reliable•Receiver NACKs (resend request) lost packet•Does not provide 100% reliability•NACK implosion01/14/195ImplosionR1SR3 R4R221Packet 1 is lostAll 4 receivers request a resendR1SR3 R4R2Resend request01/14/196Retransmission•Re-transmitter•Options: sender, other receivers•How to retransmit•Unicast, multicast, scoped multicast, retransmission group, …•Problem: Exposure01/14/197ExposurePacket 1 does not reach R1;Receiver 1 requests a resendPacket 1 resent to all 4 receiversR1SR3 R4R2211Resend requestR1SR3 R4R21Resent packet01/14/198Ideal Recovery ModelPacket 1 reaches R1 but is lost before reaching other ReceiversOnly one receiver sends NACK to the nearest S or R with packetSR3 R4R2211R1SR3 R4R2Resend request1Resent packetRepair sent only to those that need packetR101/14/199R1Aside: Using the RoutersSR3 R4R2•Routers do transport level processing:•Buffer packets•Combine ACKs•Send retransmissions•Model solves implosion and exposure, but not scalable•Violates end-to-end argumentNACKRTXRouter01/14/1910Multicast Issues•Reliable transfer•ACK/NACK Implosion•Exposure•Reliable Multicast Protocols•Scalable Reliable Multicast •Reliable Multicast Transport Protocol•Pragmatic General Multicast•Lightweight Multicast Service•Congestion control01/14/1911Scalable Reliable Multicast (SRM)•Originally designed for wb•Receiver-reliable•NACK-based•Every member may multicast NACK or retransmission01/14/1912SRM Request SuppressionPacket 1 is lost; R1 requests resend to Source and ReceiversPacket 1 is resent; R2 and R3 no longer have to request a resendR1SR3R221Delay varies by distanceXResend requestR1SR3R21XXResent packet01/14/1913Request Damping•Deterministic Suppression•Receivers start timers with delay = C1 x ds,r•Stochastic Suppression•Start timers with delay = U[0,D2] x ds,r01/14/1914SRM Star TopologyPacket 1 is lost; All Receivers request resendsPacket 1 is resent to all ReceiversSR221R3XR4Delay is same lengthResend requestSR21R3 R4Resent packet01/14/1915SRM (Summary)•NACK/Retransmission suppression•Delay before sending•Delay based on RTT estimation•Deterministic + Stochastic components•Periodic session messages•Full reliability•Estimation of distance matrix among members01/14/1916What’s Missing?•Losses at link (A,C) causes retransmission to the whole group•Only retransmit to those members who lost the packet•[Only request from the nearest responder]SenderReceiverABE FSC D0.990 000 001/14/1917Local Recovery•Application-level hierarchy•Fixed v.s. dynamic•TTL scoped multicast•Router supported01/14/1918Reliable Multicast Transport Protocol (RMTP)•Reliable Multicast Transport Protocol by Purdue and AT&T Research Labs•Designed for file dissemination (single-sender)•Deployed in AT&T’s billing network01/14/1919RMTP: Fixed Hierarchy•Rcvr unicasts periodic ACK to its Designated Receiver (DR)•DR unicasts its own ACK to its parent•Rcvr chooses closest statically configured (DR)•Mcast or unicast retransmission•Based on percentage of requests•Scoped mcast for local recoveryDR2SR3R4R1R R R RDDDRRReceiver R*RouterDR5R R01/14/1920RMTP: Comments: Heterogeneity •Lossy link or slow receiver will only affect a local region: Position of DR critical•Static hierarchy cannot adapt local recovery zone to loss points01/14/1921Pragmatic General Multicast•Cisco’s reliable multicast protocol•NACK-based, with suppression•Repair only forwarded to the NACKers01/14/1922Pragmatic General Multicast Packet 1 reaches only R1; R2, R3, R4 request resendsPacket 1 resent to R2, R3, R4; Not resent to R1R1SR3 R4R211 11Resent packetR1SR3 R4R2211XRouters remember resend requestsResend request01/14/1923Light-weight Multicast Service (LMS)•Enhance multicast routing with selective forwarding•LMS extends router forwarding - what routers are meant to do in the first place•No packet storing or processing at routers•Strictly IP: no peeking into higher layers01/14/1924LMS: Definitions•Replier•Receiver volunteered to answer requests•Turning point•Where requests start to move downstream•Directed mcast•Mcast to a subtreeR1SR3 R6R2Replier linkR4 R5ReplierTurning point1X01/14/1925LMS with Replier LinksPacket 1 reaches only R1; R2 requests resendResend requests from each receiver follow replier linksR1SR3 R6R2211XResend requestReplier linkR4 R5Turning pointR1SR3 R6R2Resend requestReplier linkR4 R501/14/1926LMS with Replier LinksRequest from replier links go up towards the SourcePacket 1 is resent to all ReceiversR1SR3 R6R21Resent packetReplier linkR4 R5R1SR3 R6R2Resend requestReplier linkR4 R5Turning point01/14/1927Multicast Issues•Reliable transfer•ACK/NACK Implosion•Exposure•Reliable Multicast Protocols•Scalable Reliable Multicast •Reliable Multicast Transport Protocol•Pragmatic General
View Full Document
Unlocking...