EE 122 Network Performance Queueing Theory Evaluation Computer Science Division Department of Electrical Engineering and Computer Science University of California Berkeley Berkeley CA 94720 1776 September 7 2004 Katz Stoica F04 Overview Motivations Timing diagrams Queueing Theory Evaluation Techniques Katz Stoica F04 2 Motivations Understanding network behavior Improving protocols Verifying correctness of implementation Detecting faults Monitor service level agreements Choosing providers Billing Katz Stoica F04 3 Outline Motivations Timing diagrams Queueing Theory Evaluation techniques Katz Stoica F04 4 Definitions Link bandwidth capacity maximum rate in bps at which the sender can send data along the link Propagation delay time it takes the signal to travel from source to destination Packet transmission time time it takes the sender to transmit all bits of the packet Queuing delay time the packet need to wait before being transmitted because the queue was not empty when it arrived Processing Time time it takes a router switch to process the packet header manage memory etc Katz Stoica F04 5 Sending One Packet R bits per second bps Bandwidth R bps Propagation delay T sec T seconds P bits Transmission time P R T time Propagation delay T Length speed of light 1 speed 3 3 nsec in free space 4 nsec in copper 5 nsec in fiber Katz Stoica F04 6 Sending one Packet Examples P 1 Kbyte R 1 Gbps 100 Km fiber T 500 usec P R 8 usec T P R T P R time T P R T P 1 Kbyte R 100 Mbps 1 Km fiber T 5 usec P R 80 usec P R time Katz Stoica F04 7 Queueing The queue has Q bits when packet arrives packet has to wait for the queue to drain before being transmitted P bits Q bits Capacity R bps Propagation delay T sec Queueing delay Q R P R T time Katz Stoica F04 8 Queueing Example P bits Q bits P 1 Kbit R 1 Mbps P R 1 ms Packet arrival Time ms 0 0 5 1 7 7 5 Delay for for packet packet that that arrives arrives at at time time t t d t d t Q t R Q t R P R P R bits in queue Q t Delay 2 Kb 1 5 Kb 1 Kb 0 5 Kb Time packet 1 d 0 1ms packet 2 d 0 5 1 5ms packet 3 d 1 2ms Katz Stoica F04 9 Router Store and Forward A packet is stored enqueued before being forwarded sent 10 Mbps Sender 5 Mbps 100 Mbps 10 Mbps Receiver time Katz Stoica F04 10 Store and Forward Multiple Packet Example 10 Mbps Sender 5 Mbps 100 Mbps 10 Mbps Receiver time Katz Stoica F04 11 Cut Through A packet starts being forwarded sent as soon as its header is received R1 10 Mbps R2 10 Mbps Receiver Sender Header time What happens if R2 R1 Katz Stoica F04 12 Throughput Throughput of a connection or link total number of bits successfully transmitted during some period t t T divided by T Link utilization throughput of the link link rate Bit rate units 1Kbps 103bps 1Mbps 106bps 1Gbps 109bps For memory 1 Kbyte 210 bytes 1024 bytes Some rates are expressed in packets per second pps relevant for routers switches where the bottleneck is the header processing Katz Stoica F04 13 Delay Delay Latency of bit packet file from A to B The time required for bit packet file to go from A to B Jitter Variability in delay Round Trip Time RTT Two way delay from sender to receiver and back Bandwidth Delay product Product of bandwidth and delay storage capacity of network Katz Stoica F04 14 Bandwidth Delay Product Source Window based flow control Send W bits window size Wait for ACKs i e make sure packets reached destination Repeat Throughput W RTT W Throughput x RTT Numerical example W 64 Kbytes RTT 200 ms Throughput W T 2 6 Mbps RTT Destination W RTT RTT time Katz Stoica F04 15 Delay Illustration 1 1 Sender Latest bit seen by time t 2 Receiver at point 2 at point 1 Delay time Katz Stoica F04 16 Delay Illustration 2 1 Sender 2 Receiver Packet arrival times at 1 1 2 Delay Packet arrival times at 2 time Katz Stoica F04 17 Overview Motivations Timing diagrams Queueing Theory Little Theorem M M 1 Queue Evaluation Techniques Katz Stoica F04 18 Little s Theorem Assume a system at which packets arrive at rate t Let d i be the delay of packet i i e time packet i spends in the system What is the average number of packets in the system d i delay of packet i t arrival rate system Intuition Assume arrival rate is 1 packet per second and the delay of each packet is d 5 seconds What is the average number of packets N in the system Katz Stoica F04 19 Answer Answer N x d 5 packets 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 time Katz Stoica F04 20 Little s Theorem 1 Latest bit seen by time t d i delay of packet i B t number of bits in transit in the system at time t 2 Sender Receiver d i B t time T What is the system occupancy i e average number of packets in transit between 1 and 2 Katz Stoica F04 21 Little s Theorem 1 Latest bit seen by time t d i delay of packet i B t number of bits in transit in the system at time t 2 Sender Receiver d i B t A area time T Average occupancy A T Katz Stoica F04 22 Little s Theorem 1 Latest bit seen by time t d i delay of packet i x t number of packets in transit in the system at time t 2 Sender Receiver A m A m 1 P d m 1 B t A area time T A A 1 A 2 A m P d 1 d 2 d m Katz Stoica F04 23 Little s Theorem 1 Latest bit seen by time t d i delay of packet i B t number of bits in transit in the system at time t 2 Sender Receiver A m P A m 1 d m 1 B t A area time T Average A T P d 1 d 2 d m T occupancy P m T d 1 d 2 d m m Arrival rate Average delay Katz Stoica F04 24 Little s Theorem 1 Latest bit seen by time t d i delay of packet i x t number of packets in transit in the system at time t 2 Sender Receiver A m i A m 1 d m 1 B t A area time T Average occupancy arrival rate x average delay Katz Stoica F04 25 Overview Motivations Timing diagrams Queueing Theory Little Theorem M M 1 Queue Evaluation Techniques Katz Stoica F04 26 Problem How many clerks do you need to handle all these people Katz Stoica F04 27 1 of customers …
View Full Document
Unlocking...