Statistical Multiplexing; Layered Network ArchitecturePowerPoint PresentationAdmin.Slide 4Recap: Circuit Switching vs. Packet SwitchingRecap: Queueing TheoryExample: Analysis of Circuit-Switching Blocking (Busy) Time: State DiagramEquilibrium = Time ReversibilityAnalysis of Circuit-Switching Blocking (Busy) Time: SketchRecap: Packet Switching DelayAnalysis of Queueing Delay: SketchExampleAnalysis of Delay (cont’)Slide 14Slide 15A Key Question: To Partition or not to Partition Resources?Partition or NotStatistical MultiplexingSlide 19Slide 20Slide 21Datagram Packet SwitchingSlide 23Timing Diagram of Datagram SwitchingVirtual-Circuit Packet SwitchingSlide 26Slide 27Timing Diagram of Virtual-Circuit SwitchingDiscussion: Datagram Switching vs. Virtual Circuit SwitchingSlide 30Slide 31Slide 32Slide 33Slide 34An Example: No LayeringAn Example: Benefit of LayeringSlide 37An Example of LayeringSlide 39Layering -> Logical CommunicationSlide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Summary: End-to-End ArgumentsSlide 52Slide 53ChallengesBackup SlidesThe Design Philosophy of the DARPA InternetGoalsSurvivability in the Face of Failure: QuestionsSlide 59Support Multiple Types of Service: QuestionsSupport Multiple Types of ServiceSupport a Variety of Networks: QuestionsSupport a Variety of NetworksOther GoalsStatistical Multiplexing;Layered Network ArchitectureY. Richard Yang1/17/20122OutlineAdmin. and recapA taxonomy of communication networksLayered network architecture3Admin.Readings from the textbook and additional suggested readings (highly recommended)Assignment one is linked on the schedule pagedue Jan. 24, 2012, in classif you type it in, you can email to our TA Harry.4circuit switching: dedicated circuit per call/session: e.g., telephone, GSM High-Speed Circuit-Switched Data (HSCSD)packet switching: data sent thru network in discrete “chunks”e.g., Internet, General Packet Radio Service (GPRS)Recap: A Taxonomy of Switched Networkscommunication networksswitchednetworksbroadcastnetworkscircuit-switchednetworks(e.g. telephone, GSM)packet-switched networks(e.g. Internet)Recap: Circuit Switching vs. Packet Switching5circuit switchingpacket switchingresource usage use a single partition bandwidthuse whole link bandwidthreservation/setup need reservation (setup delay)no reservationresource contentionbusy signal (session loss)congestion (long delay and packet losses)charging time packetheader no header per packet headerfast path processingfast per packet processingRecap: Queueing TheoryWe are not interested in extremely precise modeling, but want quantitative intuitionStrategy: model system state if we know the fraction of time the system spends at each state, we can get answers to some basic questions: how long does a new request need to wait before being served? System state changes upon events:introduce state transition diagramfocus on equilibrium: state trend neither growing nor shrinking6Example: Analysis of Circuit-Switching Blocking (Busy) Time: State Diagram70 1 k Nsystem state: # of busy linesp0 p1pkk+1pk+1 pN(k+1)Consider a simple arrival pattern- client requests arrive at a rate of  (lambda/second)- each request takes 1/mu secondsAssume memory less- During a small interval t, the number of new arrival is: t- During a small interval t, the chance that a current request finishes is: tEquilibrium = Time ReversibilityCannot distinguish 8timestatekk+1kkkkff 11# ,#kkkkbb 11# ,#Analysis of Circuit-Switching Blocking (Busy) Time: Sketch90 1 k Nsystem state: # of busy lines)1(1kppkkat equilibrium (time reversibility) in one unit time: #(transitions k  k+1) = #(transitions k+1  k)p0 p1pkk+1pk+1(k+1) 01)!1(1111pppkkkkk   NNp!12!21!110...11pN10Recap: Packet Switching Delay Four types of delay at each hop nodal processing delay: check errors & routing queueing: time waiting for its turn at output link transmission delay: time to pump packet onto a link at link speed  propagation delay: router to router propagation The focus is on queueing and transmission delayAnalysis of Queueing Delay: Sketch110 1 kNsystem state: #packets in queue1kkppat equilibrium (time reversibility) in one unit time: #(transitions k  k+1) = #(transitions k+1  k)p0 p1pkk+1pk+1 01011ppppkkkk10pExampleAssume requests come in at a rate of one request per 30 secondsEach request takes on average 20 secondsWhat is the fraction of time that a packet newly arrived needs to wait for 3 early packets?12Analysis of Delay (cont’)Average queueing delay:Transmission delay:Queueing + transmission: 130 1 kk+11)1( k)1( 14Delay1 :delay queueing averageRLwAssume:R = link bandwidth (bps)L = packet length (bits)a = average packet arrival rate (pkt/sec)111 RLRLRLtransqueueingRLaLRanutilizatio / :Link utilization (also called traffic intensity)111 tran squeueingFor a demo of M/M/1, see: http://www.dcs.ed.ac.uk/home/jeh/Simjava/queueing/mm1_q/mm1_q.html15Queueing Delay as A Function of Utilization ~ 0: average queueing delay small -> 1: delay becomes large > 1: more “work” arriving than can be serviced, average delay infinite !Assume:R = link bandwidth (bps)L = packet length (bits)a = average packet arrival rate (pkt/sec)RLaLRanutilizatio / :1RLw16A Key Question: To Partition or not to Partition Resources?Case 1 (not reserve): all arrivals into a single queue serving with rate RAssume:R = link bandwidth (bps)L = packet length (bits)a = average packet arrival rate (pkt/sec)Case 2 (reserve): the arrivals are divided into n links with rate R/n eachSetup: n streams; each stream has an arrival rate of a/nComparison: each stream reserves 1/n bandwidth or notPartition or Not1710M5M5M4pkt/sec2pk/sec2pk/sec18Statistical Multiplexingno reservation: all arrivals into the single link, the queueing delay + transmission delay:reservation: each flow uses its own reserved (sub)link with rate R/n, the queueing delay + transmission delay:A simple model to compare bandwidth efficiency of - reservation/dedication (aka