Design PrinciplesRandomizationSlide 3EthernetDeterministic algorithmsEthernet: uses CSMA/CDEthernet’s CSMA/CD (more)Ethernet’s use of randomizationEthernet commentsRandomization in Reliable MulticastScalability: Feedback ImplosionSender Oriented Reliable Mcast(simple) Rcvr Oriented Reliable McastReceiver- versus sender-oriented RM: observationsEvaluation of ApproachesAssumptions for AnalysisSlide 17Analysis of Sender Oriented ApproachAnalysis of Rcvr Oriented ApproachSender vs. Receiver (cont.)RM: Coping with Scale, HeterogeneityFeedback SuppressionFeedback Suppression: performance gainsLocal Recovery in SRMLocal Recovery: exampleReliable multicast (SRM)Randomization in Router Queue ManagementThe case against drop-tail queue managementIdea: early random packet dropRandom early detection (RED) packet dropSlide 31Slide 32We will revisit!RED: why probabilistic drop?1-1Design Principles Goals: identify, study common architectural components, protocol mechanismswhat approaches do we find in network architectures?synthesis: big picturedesign principles:separation of data, controlhard state versus soft staterandomizationindirectionnetwork virtualization: overlaysmultiplexingdesign for scale1-2Randomizationrandomization used in many protocolsExamples?1-3Randomizationwe’ll study:Ethernet multiple access protocolreliable multicastrouter (de)synchronization Router queue management1-4EthernetMetcalfe’s Ethernetsketchsingle shared broadcast channel 2+ simultaneous transmissions by nodes: interference only one node can send successfully at a time multiple access protocol: distributed algorithm that determines how nodes share channel, i.e., determine when node can transmit1-5Deterministic algorithmsTime Division Multiplexing? polling? virtual Ring?1-6Ethernet: uses CSMA/CDA: sense channel, if idle then { transmit and monitor the channel; If detect another transmission then { abort and send jam signal; update # collisions; delay as required by exponential backoff algorithm; goto A} else {done with the frame; set collisions to zero}}else {wait until ongoing transmission is over and goto A}1-7Ethernet’s CSMA/CD (more)Jam Signal: make sure all other transmitters are aware of collision; 48 bits; Exponential Backoff: first collision for given packet: choose K randomly from {0,1}; delay is K x 512 bit transmission timesafter second collision: choose K randomly from {0,1,2,3}…after next collision double K (and keep doubling on collisions until…..)after ten or more collisions, choose K randomly from {0,1,2,3,4,…,1023}1-8Ethernet’s use of randomizationresulting behavior: probability of retransmission attempt (equivalently length of randomization interval) adapted to current loadsimple, load-adaptive, multiple accessmorecollisionsheavierLoad (most likely), morenodes trying to sendrandomizeretransmissionsover longer time interval, to reduce collision probability1-9Ethernet commentsupper bounding at 1023 = k limits max sizecould remember last value of k when we were successful (analogy: TCP remembers last values of congestion window size)Q: why use binary backoff rather than something more sophisticated such as AIMD: simplicity (?)note: ethernet does multiplicative-increase-complete-decrease in backoff interval (why?)1-10Randomization in Reliable MulticastRM: how to transfer data “reliably” from source(s) to R receivers; R = 10 -- 100 -- 1000 -- 10000 -- 100000 conjecture: all current RM error and congestion control approaches have an analogy in human-human communication1-11Scalability: Feedback Implosion. . .ACKACKACKACKACKACKACKsenderrcvrs1-12Sender Oriented Reliable McastSender: mcasts all (re)transmissionsselective repeattimers for loss detectionACK tablepkt removed when ACKs are inRcvr: ACKs received pktsNote: group membership importantXsenderreceiversACKACKACKACKACK1-13(simple) Rcvr Oriented Reliable McastSender: mcasts (re)transmissionsselective repeatresponds to NAKswhen no longer buffer pkt?Rcvr: NAKs (unicast to sender) missing pktstimer to detect lost retransmissionNote: easy to allow joins/leavesXsenderreceiversNAK1-14Receiver- versus sender-oriented RM: observationsRcvr-oriented: shift recovery burden to rcvrsloss detection “responsibility”, timersscaling: protocol computational resources grow as R growsweaker notion of “group”receivers can transparently choose different reliability semanticsbut ……when does sender “release” data rcvd by all?heartbeat needed to detect lost last pkt1-15Evaluation of ApproachesExamine resource requirementsprocessing requirementsexpected time to process pkt•at sender: X, E[X]•at rcvr: Y, E[Y]mean value approachnetwork requirements1-16Assumptions for Analysisone sender, R receiversindependent errors, p per rcvrlossless signaling M - total number of transmissions per packet ,1,1][  mpmMPRm 1111][mRmpME1-171-18Analysis of Sender Oriented Approach Xp - pkt processing time Xa - ACK processing time Xt - timer processing time E[X] = E[M] E[Xp] /* packet send time */ + (E[M]-1)E[Xt] /* timer processing time */ + R E[M](1-p)E[Xa] /* ACK receive time */ E[Y] = E[M] (1-p)E[Xp] /* packet receive time */ + E[M](1-p)E[Xa] /* ACK send time */ thruput = min(1/E[X], 1/E[Y])1-19Analysis of Rcvr Oriented ApproachXXXE X E M E XE M E XE Y E M p E XE M E XE M E XE X E Ypntpnpnt     pkt proc time NAK proc. time timer proc timepkt send time * /NAK rcv time * /pkt rcv time * /NAK send time * /timeouts * /thruput =[ ] [ ] [ ] / *( [ ] ) [ ] / *[ ] [ ]( ) [ ] / *( [ ] ) [ ] / *[( ) ] [ ] / *min( / [ ], [ ])111211-20Sender vs. Receiver (cont.)Metric - rcvr oriented thruput/sender oriented thruputSignificant performance improvement shifting burden to receivers for 1-many; not as great for many-many0204060801001201401600 100 200 300 400 500 600 700 800 900 1000No. Receiversp=0.01p=0.05p=0.10p=0.25One-to-Many Comparison1.21.31.41.51.61.71.81.920 100 200 300 400 500 600 700 800 900 1000No. Receiversp=0.01p=0.05p=0.10p=0.25Many-to-Many ComparisonRM: Coping with Scale, HeterogeneityIssues:avoid feedback implosion in reverse pathavoid receiving unneeded data (retrans.)