Statistical Multiplexing; Layered Network Architecture Y. Richard Yang 1/17/20122 Outline q Admin. and recap q A taxonomy of communication networks q Layered network architecture3 Admin. ❒ 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 Networks communication networks switched networks broadcast networks circuit-switched networks (e.g. telephone, GSM) packet-switched networks (e.g. Internet)Recap: Circuit Switching vs. Packet Switching 5 circuit switching packet switching resource usage use a single partition bandwidth use whole link bandwidth reservation/setup need reservation (setup delay) no reservation resource contention busy signal (session loss) congestion (long delay and packet losses) charging time packet header no header per packet header fast path processing fast 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 shrinking 6Example: Analysis of Circuit-Switching Blocking (Busy) Time: State Diagram 7 0 1 k N system state: # of busy lines p0 p1 pk k+1 pk+1 pN λ (k+1)µ Consider a simple arrival pattern - client requests arrive at a rate of λ (lambda/second) - each request takes 1/mu seconds Assume 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 8 time state k k+1 kkkkff→++→ 11# ,#kkkkbb→++→ 11# ,#Analysis of Circuit-Switching Blocking (Busy) Time: Sketch 9 0 1 k N system state: # of busy lines µλ)1(1+=+kppkkat equilibrium (time reversibility) in one unit time: #(transitions k → k+1) = #(transitions k+1 → k) p0 p1 pk k+1 pk+1 λ (k+1)µ ( )01)!1(1111pppkkkkk++++==µλµλ( ) ( )NNpµλµλµλ!12!21!110...11++++=pN10 Recap: Packet Switching Delay q 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: Sketch 11 0 1 k N system state: #packets in queue µλ1+=kkppat equilibrium (time reversibility) in one unit time: #(transitions k → k+1) = #(transitions k+1 → k) p0 p1 pk k+1 pk+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: 13 0 1 k k+1 µ λ ρ−1ρρ)1( −kρρ)1( −14 Delay ρρ−=1 :delay queueing averageRLwAssume: R = link bandwidth (bps) L = packet length (bits) a = average packet arrival rate (pkt/sec) ρρρ−=+−=+111 RLRLRLtra nsqueueingRLaLRanutilizatio ==/ :ρLink utilization (also called traffic intensity) µρρµ111+−=+ tra nsqueueingFor a demo of M/M/1, see: http://www.dcs.ed.ac.uk/home/jeh/Simjava/queueing/mm1_q/mm1_q.html15 Queueing 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 ==/ :ρρρ−=1RLw16 A Key Question: To Partition or not to Partition Resources? ❒ Case 1 (not reserve): all arrivals into a single queue serving with rate R Assume: 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 each Setup: n streams; each stream has an arrival rate of a/n Comparison: each stream reserves 1/n bandwidth or notPartition or Not 17 10M 5M 5M 4pkt/sec 2pk/sec 2pk/sec18 Statistical 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 circuit-switching) and - no reservation (aka packet switching) setup - a single bottleneck link - n flows; each flow has an arrival rate of a/n ρ−11RLρ−11RLnAssume: R = link bandwidth (bps) L = packet length (bits)19 Summary: Packet Switching vs. Circuit Switching ❒ Advantages of packet switching over circuit switching ❍ most important advantage of packet-switching over circuit switching is statistical multiplexing, and therefore more efficient bandwidth usage ❒ Disadvantages of packet switching ❍ potential congestion: packet delay and high loss • protocols needed for reliable data transfer, congestion control • it is possible to guarantee quality of service (QoS) in packet-switched networks and still gain statistical multiplexig, but it adds much complexity ❍ packet header overhead ❍ per packet processing overhead20 Outline q Admin. and recap Ø A taxonomy of communication networks ¦ circuit switched networks ¦ packet switched networks ¦ circuit switching vs. packet switching Ø datagram and virtual circuit packet switched networks21 A Taxonomy of Packet-Switched