Perf Analysis of Comptr Ntwrks
Perf Analysis of Comptr Ntwrks CS 756
Popular in Course
Popular in ComputerScienence
This 34 page Class Notes was uploaded by Leland Swift on Monday September 28, 2015. The Class Notes belongs to CS 756 at George Mason University taught by Staff in Fall. Since its upload, it has received 60 views. For similar materials see /class/215125/cs-756-george-mason-university in ComputerScienence at George Mason University.
Reviews for Perf Analysis of Comptr Ntwrks
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
Basic Queueing Theory MM Queues These slides are created by Dr Yih Huang of George Mason University Students registered in Dr Huang s courses at GMU can make a single machinereadable copy and print a single copy of each slide for their own reference so long as each slide contains the copyright statement and GMU facilities are not used to produce paper copies Permission for any other use either in machine readable or printed form must be obtained from the author in writing CS 756 Introduction El Queueing theory provides a mathematical basis for understanding and predicting the behavior of communication networks El Basic Model Arrivals gt Depa39tures Queue Sbrver CS 756 CS 756 El Maj or parameters interarrivaltime distribution servicetime distribution number of servers queueing discipline how customers are taken from the queue for example FCFS number of buffers which customers use to wait for service El A common notation ABm where m is the number of servers and A and B are chosen from M Markov exponential distribution D Deterministic G General arbitrary distribution CS 756 MMl Queueing Systems El Interarrival times are exponentially distributed with average arrival rate 9 El Service times are exponentially distributed with average service rate u El There is only one server CI The buffer is assumed to be in nite CI The queuing discipline is rstcome rst serve FCFS System State El Due to the memoryless property of the exponential distribution the entire state of the system as far as the concern of probabilistic analysis can be summarized by the number of customers in the system i the pasthistory how we get here does not matter El When a customer arrives or departs the system moves to an adjacent state either il or i l CS 756 State Transition Diagram 7 7b 7b 7b 7b 7b 000990015 H H H H H H El In equilibrium B Let P P system in state i El We have fLPi lupm The rate of movements in both directions should be equal CS 756 El Equations om the state transition diagram 1P0 P1 1P1 P2 1P2 P3 EISolve A 3 P1iP0pPO u P2 Plpltppogtpzpo Pkka0 EIWhat is p EISince gagfad we have 1 ape13130417 EIThatis Pk pkl p EINote that p must be less than 1 or else the system is unstable CS 756 Average Number of Customers Nikpkl pikpk k0 k0 CS 756 El Average delay per customer time in queue plus service time El Average waiting time in queue CS 756 CS 756 Applications El Consider 24 computer users each of which produces in average 48 packets per second El For every customer the interarrival times of his packets are exponentially distributed CI The lengths of packets are also exponentially distributed with mean 125 bytes CS 756 Scenario 1 El Users share a T1 line using the stande Tl timedivision multiplexing El Assume that each user is associated with an in nite buffer that is queue El In a T1 line it takes 18000 seconds to deliver or serve each byte El However due to their variable lengths the delivery or service times of packets are still exponentially distributed The average service rate it CI The system can be considered as 24 MMl queues De arts to W thepother end Arrlvals Q of the T1 line ueue Server 124th of the T1 line We have p2 275 64 075 1 075 T 1 i z 42msec 64 48 24 CS 756 13 Scenario 2 El Users share a 1544 Mbps line through an IP router Packets from 24 users 6 Q The entire T1 as the server CS 756 CI The aggregated arrival rate is 24x48 21152 CI The service rate is 24x64 2 1536 El We have p4864 75 1 1 z24msec 1536 1152 384 This system is 24 times faster than TDM CS 756 Discussion El Flaws in the analysis El Still such a drastic difference in results convincingly reveals the inefficiency of El This partly explains the momentum toward using the Internet as the universal information infrastructure El In general allowing customers to share a pool of resources is far more efficient than allocating a fixed portion to each customers CS 756 MMm Queueing Systems Arrivals Sewers All servers are identical with service rate u CS 756 State Transition Diagram x x x x x x 009 u u H mu mu m Balance equations i Pi foriSm 1Pi1 m Pi for zgtm CS 756 Solution fa 2390 for iSm Pl 1 i Pom p for igtm m 2 Where 02 mt Noticing that P 1 we have 71 P0mZ 1mpi mmm i0 i quotMl p CS 756 The probability that an arriving customer has to wait in queue m P0mpm w fem m 2p P0mpm quotMl P This is known as the Erlang C formula CS 756 Average number of waiting customers NQii mPiipim im i0 m p Pomp quot m m Pompm p 141 1 p2 P bf CS 756 CS 756 Average waiting time in queue W Z N Q 2 PP Q 1 11p Average time in the system 1 1 pPQ 2 1 PQ m m mill 1 Average number of customers in the system N T PQ m mlu T W u pPQ 1 p CS 756 MMlK Queueing Systems El Similar to MMl except that the queue has a nite capacity of K slots El That is there can be at most K customers in the system El If a customer arrives when the queue is full heshe is discarded leaves the system and will not return CS 756 Analysis x x A x a Notice its similarity to MMl except that there are no states greater than K We have Pipipo for OSiSK 0 for i gt K Noticing that ZZP 1 we have 1 P0 1 p CS 756 Poisson Process Let random variable N be a counter of the number of occurrences of a particular type of events Clearly the value of N increases over time Let N tbe the value of N at time I Moreover if N 0 0 N t is said to be a counting process The counting process N tis said to be a Poisson process having rate 7 if the number of events in any interval of length I is Poisson distributed with mean it That is for all st 2 0 n PNts Ns 2n 311 n 01 n CS 756 Discussion CI The interarrival times of a Poisson process with rate 1 is exponentially distributed with average 11 CI The reverse is also true if the interarrival times of events are exponentially distributed with average 1 1 then the event counting process is Poisson with rate xi El Thus the customer arrival processes of MM queueing systems are Poisson El A Poisson customer count and exponentially distributed customer interarrival times are the two sides of the coin CS 756 Sampling Poisson Arrivals El Consider a Poisson customer arrival process of with average rate 7 El Each customer can be classi ed as Type I or Type II with probability p and 11 respectively El Then the arrival process of Type 1 customers is also Poisson with average rate pl El Likewise the arrivals of Type 11 customers is Poisson with average rate I 19M CS 756 Application El We know that the customer arrivals at a barbershop form Poisson process with average rate of 10 customers per hour EIAmong the customers 40 are males and 60 are females El Then the interarrival times of male customers are exponentially distributed with an average rate of 4 per hour CI The interarrival times of female customers are exponentially distributed with an average rate of 6 per hour Per CS 756 Exercise El Consider the router configuration below 400 2000 Port 0 Packets Port 1 lepS SCC 2Mbps 60 311 PM CI The lengths of arriving packets are exponentially distributed with an average of 1000 bits CS 756 Questions El Argue that queues A and B are independent MMl systems El Compute the average length of queue A in bits El For a packet destined for port 2 compute its expected time at the router including transmission time El Compute the average time a packet spent at the router including transmission time El Compute the average number of packets at the routerincluding the ones in transmission CS 756 Merging Poisson Arrivals El Given two exponential variables X and X 2 with rates A and 12 the random variable X minX1X2 is also exponential with rate 21 22 El Consider two Poisson arrivals with average rates A and 12 CI The merged arrival process will also be a Poisson process with the average rate 1143912 CS 756 Application El Consider the router con guration below Packet arrival Packet 1 Router arrival CS 756 33 CI The lengths of arriving packets are exponentially distributed with an average of 1000 bits Why do we care about packet lengths El Packet arrivals at ports 1 and 2 are exponentially distributed with average rates of 2000 and 3000 packets per second respectively CI The transmission rate of port 0 is 10Mbps CI The whole system can be modeled as a single MMl queueing system with an arrival rate of 5000 and service rate of 10000 CS 756 34 Burke39s Theorem In its steady state an MMm queueing system with arrival rate 9 and perserver service rate u produces exponentially distributed interdeparture times with average rate Application Two cascaded independently operating MMm systems can be analyzed separately 1 4 4 Server 1 Server 2 Departs MM1 system 1 MM1 system 2 CS 756 CS 756 Pitfall El Consider the system below where the servers are transmission lines 500 Packets quot Per sec 1Mbps 2Mbps El Packets lengths are exponentially distributed with an average of 1000 bits El Can the two queues be analyzed separately Why Discussion In general any feedforward network of independentlyoperating MMm systems can be analyzed in this systembysystem decomposition CS 756 37 Question How about networks that do contain feedbacks Answer the interarIival times of some systems may not be exponentially distributed and thus cannot be analyzed as independent MMm queues CS 756 38 Jackson39s Theorem For an arbitrary network of k MMl queueing systems Pn1n2nk P11 11P21 12Pkl lka where P nj p 1 pf That is in terms of the number of customers in each system individual systems act as if they are independent MMl queues they may not CS 756 39 Application Consider the network below The arrival rate 2 and probabilities p and p are known We rst compute the arrival rates A and 12 lzllzp zngli 211210791 1221192091 CS 756 40 20 Quality of Service QOS Routing These slides are created by Dr Yih Huang of George Mason University Students registered in Dr Huang s courses at GMU can make a single machinereadable copy and print a single copy of each slide for their own reference so long as each slide contains the copyright statement and GMU facilities are not used to produce paper copies Permission for any other use either in machine readable or printed form must be obtained from the author in writing CS 756 A Quick Review of NPCompleteness El A problem is in Class P if it can be solved in polynomial time with a deterministic Turing machine Turing machine is a math modeling of stored instruction computers El A problem is in Class NP if it can be solved in polynomial time with a nondeterministic Turing machine A nondeterministic Turing machine can simultaneously pursue an in nite number of computational paths It is an unrealistic but useful math model CS 756 P and NP Problems CIA Class P problem can be solved in polynomial time on real machines and is considered tractable Sorting accounting shortest path problems spanning tree problems and many other problems you use computers to solve daily CIA Class NP problem can be solved in exponential time on real machines You may be able to solve it in polynomial time All Class P problems are also NP CS 756 CIA problem in NPP if exists cannot be solved in polynomial time on real machines and is considered intractable in practice CIA good way to nd a NPP problem is to consider problems that do not have known polynomial solutions algorithms map coloring problem traveling salesman problem automatic theorem proving and some QoS routing problems EIHowever no one can prove any of the above problems actually in NPP CS 756 PNP El This one of the most fundamental unsolved problem in computer science El Most people believe it is too good to be true It would imply that all problems solvable by a nondeterministic Turing machine can be solved in polynomial time in real world El Still we have not mathematically proven it wrong El However all most all computer scientists assume that NPP is not empty CS 756 NPComplete Problems El A problem X is NPComplete if the following statement is true If we can solve X in polynomial time then we can solve all NP problems in polynomial times El That is if you come up with a polynomialtime algorithm for any NP Complete problem then you have proven PNP El Since we don t believe PNP we solve NP Complete problems by devising workarounds or approximation algorithms heuristics CS 756 The Routing Problem El Traditional routing protocols RIP OSPF etc mainly use hop counts to select paths El This does not meet the requirements of many emerging communication applications El For example live multimedia applications must make sure that Packet delays are bounded Jitters changes in packet delays are well controlled CS 756 Shortest Path Algorithms El Given a graph GVE a shortest path algorithm nds a path with minimal distance according to the given link costs between a pair of source and destination El Shortest path algorithms are the foundation of network routing El Every realworld network routing protocol is either a centralized distributed or hybrid implementation of such algorithms CS 756 El Dijkstra Algorithm 0W2 where Vis the number of nodes in the graph or routers in the network Used by OSPF Works for nonnegative link costs El Belhnan Ford Algorithm 0EV where E is the number of links in the network Suitable for distributed implementations Used by RIP Works for arbitrary link cost values however negative costs cannot form cycles CS 756 QOS Routing El Find the path for a given source and destination that best satisfies a given set of criteria El Performance metrics include Hop count Delay Jitter the variance in consecutive packet separations at receivers Data loss rate Available residual bandwidth Queue length available buffer space CS 756 Taxonomy EIFor some metrics e g bandwidth buffer space the state of a path is determined by the state of its bottleneck link El Linkoptimization routing nds the path that optimizes the performance of its bottleneck link according to a given criteria Ex bandwidthoptimization routing nds the path with the largest bandwidth in the bottleneck link CS 756 El Linkconstrained routing nds a path whose bottleneck satis es a given criteria Ex bandwidthconstrained routing nds a path whose bottleneck supports the given bandwidth CS 756 CS 756 El For other QoS metrics such as delay and jitters the state of a path is determined by the combined state over all links of the path El Pathoptimization routing nds the path that optimizes the given metric Example delayoptimization routing finds a path with the minimum accumulated delay El Pathconstrained routing finds a path that satisfies the requirement of the given metric Example delayconstrained routing finds a path whose delay is bounded by the given value CS 756 Tractability El Optimization problems can be solved by the traditional type of shortest path algorithms Just use the given metric as the link cost El Constraint problems can be solved by their optimization counterparts To solve the delayconstrained routing problem simply run the delay optimization routing algorithm and see whether the best path meets the given delay bound However EIUsing one metric is not enough for QoS applications El Focusing on one metric could results in waste of network resources Consider an application that needs 5 Mbps We run a linkoptimization algorithm to nd a path CS 756 lOMbps 20Mbps Destination El Given the above network and link bandwidth the algorithm will select the red path whose bottleneck bandwidth is 20 rather than the blue path whose bottleneck bandwidth is 10 El However the red path uses 54 Mbps of bandwidth while the blue one uses only 52 Mbps El We need to consider a second metric hop count CS 756 Composite Routing Problems EIFinding a path between a source and destination using more than one performance metric El Such problems can be derived from the above four basic routing problems El For example the bandwidthconstrained leastdelay routing problem belongs to the linkconstrained pathoptimization problem class CS 756 Polynomial Routing Problems El Linkconstrained pathoptimization routing El Linkconstrained linkoptimization routing El Multilinkconstrained routing El Linkconstrained pathconstrained routing El Pathconstrained linkoptimization routing El In the following we will discuss important cases of the above problems and their solutions CS 756 BandwidthDelay Constrained Routing El This is a case of linkconstrained path constrained routing El It lends itself to multimedia applications that demand bandwidth availability and delay bound CS 756 El Algorithm lEliminate all links that do not meet the bandwidth requirements 2Run a traditional shortest path algorithm to nd the minimum delay path 3The path is accepted if it meets the delay constraint otherwise report failure CS 756 Discussion EIWe can always get rid of the link constrained part by eliminating unsatisfactory links CI The trick gives rise to the solutions for all the polynomial cases except the last one pathconstrained linkoptimization routing We will not cover the case in this talk You are encouraged to gure it out on your own CS 756 21 NPComplete Routing Problems El Pathconstrained pathoptimization PCPO routing Example delayconstrained minimum cost El Multipathconstrained routing MPC Example delay delay jitter constrained routing CS 756 22 El Notice There are two suf cient conditions for the NPcompleteness of PCPO and MPC The two metrics are independent and they both use real numbers or unbounded integers as values CS 756 23 A Precise Description of MPC El A metric d is said to be additive if given a path PL1L2 Ln dP dL1dL2 dLn The delay metric is additive El A metric d is said to be multiplicative if given a path PL1L2 Ln dP dL1dL2 dLn The transmission rate is multiplicative El Theorem Given any N additivemultiplicative metrics and their respective constraints the problem of finding a path satisfying the N constraints is NP complete CS 756 24 Shortest Path Bounded Delay Routing CI The hopcount metric where dLl for every link L in the network is additive CI The delay metric is also additive El Thus the problem is NPcomplete Elln general nding the shortest path in terms of hop counts that satis es an additivemultiplicative constraint is NP complete EI How depressing CS 756 25 Handling Delay and Jitter Constraints EIWe ve seen that delay and jitter constraints are dif cult to deal with They are however important to many multimedia applications El Fortunately in networks that do provide QoS guarantees additional help is available El Speci cally a network that guarantees QoS must use an advanced packet scheduling algorithm such as WFQ CS 756 26 EIWith many scheduling algorithms delays and jitters of a traffic ow are functions of its allocated bandwidth El In general the more bandwidth the shorter the delay and the lesser the jitter El To solve a routing problem involving delay and jitter constraints we first translate these constraints to a bandwidth requirement El We then face a bandwidth constrained problem which is easy to deal with CS 756 Discussion CI The delay derived from bandwidth refers to the queueing and transmission delay at a router El It does not include signal propagation delays El Thus some distortions are introduced in using bandwidth to guarantee delays El For many communication links this is ok El One important exception is satellite links which cause extraordinary propagation delays CIA practical solution is to simply exclude satellite links in delayconstrained routing CS 756
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'