Multicore Cncrt Programming
Multicore Cncrt Programming CS 6030
Popular in Course
verified elite notetaker
verified elite notetaker
ENVS 101 004
verified elite notetaker
54158, Introduction to Public and Community Health
verified elite notetaker
verified elite notetaker
Popular in ComputerScienence
This 78 page Class Notes was uploaded by Lisette Hodkiewicz on Wednesday September 30, 2015. The Class Notes belongs to CS 6030 at Western Michigan University taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/216891/cs-6030-western-michigan-university in ComputerScienence at Western Michigan University.
Reviews for Multicore Cncrt Programming
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/30/15
I Security Overview I Cryptography functions Secret key eg DES quot Public key eg RSA Message digest eg MD5 I Security services i f Privacy preventing unauthorized release of information 1 Authentication verifying identity of the remote participant Integrity making sure message has not been altered Security Cryptography Security algorithms services Secret Public Message Privacy Authentication Messagt key key digest integrity eg DES eg RSA eg MD5 y Secret Key DES Plaintext Plaintext Encrypt with Decrypt with secret key secret key Ciphertext 39 1 Public Key RSA Plaintext Plaintext Encrypt with Decrypt with public key private key I Encryption amp Decryption c memod n m cdmod n Ciphertext Message Digest I Cryptographic checksum just as a regular checksum protects the receiver from accidental changes to the message a cryptographic checksum protects the receiver from malicious changes to the message I Oneway function given a cryptographic checksum for a message it is virtually impossible to figure out what message produced that checksum it is not computationally feasible to find two messages that hash to the same cryptographic checksum I Relevance if you are given a checksum for a message and you are able to compute exactly the same checksum for that message then it is highly likely this message produced the checksum vou were given l I Public key authentication A B 50c P W93 X Key Distribution I Certificate 3 special type of digitally signed document certify that the public key in this document belongs to the entity named in this document signedX l39 the name ofthe entity being certified l l the public key of the entity 1 11 the name ofthe certified authority a digital signature I Certified Authority CA l l administrative entity that issues certificates useful only to someone that already holds the CA s public key Collajhof ative SignalProceamg Zille Huma Kamal w Miran mm Detection Classification and Trac ing 0 CSP in a detection classi cation an track39 ing application ciin win huuiym anymiknrnnmnw Need for CSP 0 Collaboration increases accuracy ofresults o Does not exhaust any single mote in the en 39ronmen o Towds Fault Tolerance o Energy conserved accuracy achieved and network life increased ciin win huuiym minimmom Focus on CSP o Tiaining phase o Testing phase o classi eaiion and Fusion phase I Data F Decision Fusion inn w may minimmum Fluw Chan nf CSP meESS Training Phase The training phase 7 where each mote is exposed to a number of sample signal readings belonging to each of the predetermined categories Based on this training every mote computes a mean and a covariance for each of the categories l r 5 Tull ii iill ii i V4 1m I11 mini li iumiquot mintmm flit mqu olimlm 39 cs 037 Whalers Semnriysthrm Testing Phase The testing phase 7 where each mote is exposed to a number of different test signa readings These signal readingare drawn fromk wn modalities of the categories Motes are then prompted to classify these test signals into one ofthe predetermined set ofcategories usingthe mean and covariance for each category in the trainingphase The frequency ofthe correctness ofthese decisions and erroneous decisions is maintained in a 2D table known as a confusion matrix 1 o Based on this confii ion matri piouahilit false alarm rate etc can be inferred cs 037 Whalers SemanyStErr Example Confusion Matrix 42 Probability ofdeteption for category 1 cs 037 Whalers Semnriysthrm Classification Bayes Rule can be transformed into a maximum a posterior rule formulated as 39 1 um M J v ltM w SJ Mf w MARS The resulting MAP matrix can be reduced by normalization formulated as rwherenz lyrepresentsthe xyelementnf i X the ddeAPmamx Tl ilan cs 603 7 Wireless Sensnrsystems Westem Michigan University References DS A D Costa A M Sayeed Colkzboraiive Signal Processigri for Distribute Classificaiiori iri Semor Networ Electrical and Computer Engineering University of WisconsinMadison LWHS D Li K D Wong Y H Hu A M Sayeed Detection Classi cation and Trac 39ng of Targets in Distributed Computer Engineering University of WisconsinMadison 603 r Wirelcss Sensnrsystems TCP Transmission Control Protocol a Simple Demultiplexor UDP I Unreliable and unordered datagram service I Adds multiplexing I No flow control I Endpoints identified by ports servers have wellknown ports T see etcservices on Unix 0 6 3 I Header format I Optional checksum 1 psuedo header UDP header data 1 TCP Overview I Connection oriented I Bytestream l app writes bytes TCP sends segments app reads bytes Application process l Write bytes TCP Send buffer I Full duplex I Flow control keep sender from overrunning receiver I Congestion control keep sender from overrunning network Application process I Read bytes TCP Transmit segments TCP Header 0 4 10 16 31 SrcPort DstPort SequenceNum Acknowledgment Heren 0 Flags AdvertisedVl ndow Checksum UrgPtr Options variable Flags SYN FIN RESET PUSH URG ACK Checksum lP pseudo header TCP header data 1 TOP Overview I When a client requests a connection it sends a SYN segment a special TCP segment to the server port I SYN stands for synchronize The SYN message includes the client s ISN I ISN is lnitial Sequence Number l 1 TOP Overview Contd l Every TCP segment includes a Sequence Numberthat refers to the first byte of data included in the segment I Every TCP segment includes Acknowledgement Number that indicates the byte number of the next data that is expected to be received 39 All bytes up through this number have already been received TCP Overview Contd I MSS Maximum segment size A TOP option I Window Every ACK includes a Window field that tells the sender how many bytes it can send before the receiver will have to toss it away due to fixed buffer size ThreeWay Handshake W Q Seq 35 ACK x 1 Send ACK ack yl11 Receive AfCK 36k If Receive SYN SEE 1 Send SYN Receive SYN seq 11 ACK 3 1 1 TOP Connection Establishment Step 1 Client Starts l A client starts by sending a SYN segment with the following information Client s ISN generated pseudorandomly Maximum Receive Window for client Optionally but usually MSS largest datagram accepted No payload Only TCP headers 39 1 TOP Connection Establishment Step 2 Sever Response I When a waiting server sees a new connection request the server sends back a SYN segment with Server s ISN generated pseudorandomly Request Number is Client ISN1 Maximum Receive Window for server Optionally but usually MSS No payload Only TCP headers I TCP Connection Establishment Step 3 I When the Server s SYN is received the client sends back an ACK with r i Request Number is Server s ISN1 TCP Data Transfer I Once the connection is established data can be sent I Each data segment includes a sequence number identifying the first byte in the segment I Each segment data or empty includes an acknowledgement Number indicating what data has been received Buffering I Keep in mind that TCP is part of the Operating System It takes care of all these details I The TCP layer doesn t know when the application will ask for any received data I TCP buffers incoming data so it s ready when we ask for it TCP Buffers l Both the client and server allocate buffers to hold incoming and outgoing data The TCP layer does this I Both the client and server announce how much buffer space remains the Window field in a TCP segment Send Buffers I The application gives the TCP layer some data to send I The data is put in a send buffer where it stays until the data is ACK d it has to stay as it might need to be sent again I The TCP layer won t accept data from the application unless or until there is buffer space ACKs I A receiver doesn t have to ACK every segment it can ACK many segments with a single ACK segment I Each ACK can also contain outgoing data piggybacking I If a sender doesn t get an ACK after some time limit MSL it resends the data TCP Segment Order I Most TCP implementations will accept outof order segments if there is room in the buffer I Once the missing segments arrive a single ACK can be sent for the whole thing I Remember lP delivers TCP segments and IP in not reliable IP datagrams can be lost or arrive out of order TCP Connection Termination l The TCP layer can send a RST segment that terminates a connection if something is wrong I Usually the application tells TCP to terminate the connection politely with a FIN segment FIN I Either end of the connection can initiate termination I A FIN is sent which means the application is done sending data I The FIN is ACK d I The other end must now send a FIN I That FIN must be ACK d App1 App2 FIN SNX ACKX1 I FIN SNY ACKY1 l I T State Transition Diagram Client Server Passive open LISTEN CLOSED ctive open SYN Active open ISYN Passive open Close LISTEN SYNSYN ACK SYNSYN ACK SendSYN SYNRCVD SYNSENT SYNRCVD SYNSENT SYN ACKACK SYN ACKACK CloseFIN CloseFIN FNWAT1 FNWAT1 ACK Timeout alter two segment lifetimes TIMEWAT ACK Timeout after segment lifetimes TMEWAT CLOSED IN TCP TIMEWAT I Once a TCP connection has been terminated the last ACK sent there is some unfinished business What if the ACK is lost The last FIN will be resent and it must be ACK d What if there are lost or duplicated segments that finally reach the destination after a long delay I TCP hangs out for a while 2 Max Segment Life to handle these s ua ons Checking TCP states with netstat netstat a n Active Connections Proto Local Address Foreign Address State TCP 000027 000020 LISTENING TCP 000029 000020 LISTENING TCP 0000213 000020 LISTENING TCP 0000217 000020 LISTENING TCP 0000219 000020 LISTENING TCP 0000221 000020 LISTENING TCP 0000223 000020 LISTENING TCP 0000225 000020 LISTENING TCP 0000280 000020 LISTENING TCP 00002135 000020 LISTENING TCP 00002443 000020 LISTENING TCP 00002445 000020 LISTENING TCP 12700121030 12700127161 ESTABLISHED TCP 12700121051 000020 LISTENING TCP 12700127161 000020 LISTENING TCP 12700127161 12700121030 ESTABLISHED TCP 141218143762139 000020 LISTENING TCP 1412181437621836 141218143432445 ESTABLISHED TCP 1412181437622003 662508431280 ESTABLISHED TCP 1412181437622136 141218143215222 ESTABLISHED TCP 1412181437623355 21615519316625050 ESTABLISHED TCP 1412181437623844 141218143102143 ESTABLISHED TCP 1412181437624635 14121814346280 ESTABLISHED TCP 1412181437624683 141218143102143 ESTABLISHED References I Cisco Networking Academy Program CCNA Cisco Press I CSCl5273 Computer Networks Dirk Grunwald University of ColoradoBoulder I CSCl4220 Network Programming Dave Hoinger Rensselaer Polytechnic Institute I TCPIP Illustrated Volume 1 Stevens I Java Network Programming and Distributed Computing Reilly amp Reilly I Computer Networks A Systems Approach Peterson amp Davie I httpwwwfirewallcx I httpwwwiavasoftcom Notes on Queueing Theory Dr Deep Medhi University of MissouriKansas City Chapter 2 Stochastic Processes BD Model and Queues In this section we provide brief overview of stochastic processes and then go into birthanddeath model and queueing analysis You may want to consult the book by Allen 1 used often in CS 394 for more material on stochastic processes etc 1 Stochastic Processes Let t be a parameter assuming values in a set T Let Al be a random or stochastic variable for every t E T The family All E T is called a stochastic process We think about stochastic events that occur over time ie l is in timespace In terms of measurement we can quantify time as either a continuous variable or a discrete variable for example the ALOHA protocol uses continuous time model while slotted ALOHA uses discrete time model Similarly the state space values for the stochastic process can also be continuous C or discrete D The possible combinations are Time state space C D to discuss C C eg brownian motion not covered D C Waiting time of n th arrival in a queue D D to discuss In discrete state space the stochastic process is called a chain with values denoted eg S 0 l m 2 Discretetime Markov chain A stochastic process Am 71 2 0 is called a Markov chain if for every Ti 6 S we have P744n iT IX39 il mail 40 10 P744n iT IX nil frail In this de nition we use time to be discrete What this means is that for a Markov chain the probability at time n depends only on the previous state and nothing before that This is known as the memoqless property of a Markov chain Now what is the probability of the process being in state j given that it was in state i in the preceding time This is the transition probability from state i to j It is written as pij Prlln jllnil Given you are at state i at time n 7 l the probabilities of moving to all states in the next time slot must add up to l ie 00 1 l for each i j0 A Markov chain is called temporally homogeneous if P744n jllnil P744nm jll39r vmil The transition probability is then denoted by pm For all possible values of i j one can denote he the transition probability as a matrix with elements pi339 The transition in nstep is given by pixn FHA jlg i Since a Markov chain has stationary transition probabilities we have 1min P7Amn jlm i for all m 2 0 and n gt 0 3 Continuoustime Markov Chain Let Xl0 g l lt co be a Markov process with countable state space S 0 12 over continuous timespace t For example X t can be the number of customers in the system at time t For continuous time discrete space Markov chains the transition probability is denoted by pig 2 Prrl u jru i lgt 0 ij E 5 Note ZPMU l for each i 1 Now we can consider all the possible cases for i j at time t giving us a matrix of information Thus in matrix notation Pl 2 piM0 2 transition probability matrix 4 ChapmanKolmogorov equation So far we have mentioned onestep transition probabilities ie probability of A given AHA CK equation provides a relation for multiple steps as follows 111501 m Zpikmwk m l k where n m 0 l 2 For continuous time this can be written as MC l ZPiklt5ijl 2 k where 5 2 0 In matrix notation Set the initial transition probability matrix as P I identity matrix ie 1100 2 l ifi j else 0 ifi a j De ne 4 MU Pom 4 MU 4 gm quot 111quot t zz t f0 r 1 qM 21imp M I M lim p771 H0 t H0 l Note that q s are instantaneous rate In matrix notation l 7 I Q lim H0 l where Q 915 Now recall the relation 2pm l 1 If we move 1 from RHS to LHS of this equation and then divide by l and let i a 0 we get PAWl WU 1l Pikll m 0 which implies an QM Qik 0 In short we have Z qqj q 0 lt3 1 Typically we denote qM iqi thus we have Z 91739 Qi 1 The matrix Q is known as the transition density matrix or in nitesimal generator or a rate matrix If the state space S is nite then 7 9390 Go 1 Go m 93910 Ql qlm Q39m gm 1 7 gm This is another way to write the CK equation in terms of rate P t if QP 1 1030 T PtQ or Now consider the vector 7rl 2 7m l W10 This is the probability vector of the state of the system at time t ie probability ofbeing at state 0 in time t is 7m l etc Now we move to the steadystate situation ie what is the system going to be like in steadystate as t a QC It is easy to see that 7rt 7r0Pt Also 1050 00 mam 0Q J If we denote the steadystate probability vector by 7r ie v I t 7 lt gt then from the relation 5 and lettingl a QC we get since derivative of a constant is zero 0 7ng with the requirement that probabilities sum up to l W1W2ml if is a column vector of the same dimension as 7r with each component being 1 we can write this in compact form as me 1 Note that 0 Q 7m 2 1 5 is a linear system of equation which has a unique solution under certain conditions To illustrate suppose that we have a system that takes three values 0 l 2 The probabilities are 7quot 7 0c7r1c7fz and 7rQ 0 is 90 901 902 Woe 7 1 7 2 Q10 41 412 0 0 0 920 921 92 and 7m 2 l is 7quot0 7f1 W2 1 Ifwe know q s then we can solve for 7r 5 BirthandDeath Process This is a special case of continuoustime Markov chain You can only transition to a neighbor one step away or stay where you are in an in nitesimal time period and the rate is statedependent one de ned for arrival and the other for departure Qii1 M i 0 12 qri71llic i1e2en qm3920 forja iliili Due to this situation and the requirement that the row sum to be zero from 3 we have qi qM A7 m for i not in boundary state Now what does the matrix Q look like We essentially get a band around the diagonal with one element on each side tridiagonal matrix all of the other elements are zero 7A0 A0 0 0 0 1 7A111 A1 0 0 Q 0 112 7A212 A2 0 Pictorially the statetransition diagram is as follows Now let s go back to CK equation For the birthanddeath process we can rewrite the CK equation from 4 as EN M 1 MU Mill mil llj1pij1l fofj 2 1 Iii05 AUIM39UU 11Pi1l 8 Suppose that M s and 111 s are nonzero Then the Markov chain is irreducible means every state can be reached from every other state by chaining it can be shown that in steadystate ng 7939 exists and are independent of the initial state i Revisiting CK equation above and using the fact that the derivative of a constant is zero we have 0 7Aj 11339 7g Aj717rj71 MHMH forj 2 l 9 0 AU KU 1117f1 These are also known as balance equations In fact the above is nothing but 7ng 0 specialized for the B D model The nice thing is that this linear system of equations is easily solvable analytically From 10 we have A0 in 1 71 For j 1 from 9 we have 0 91 117F1 Ao o 279 which implies using 10 llz z A17r1 117F1 AUWU Avri Thus Al AgAl 7Q in 7m 2 1112 Generalizing we get A A A jwm J Zl lt11 llillznllj Recall that all the probabilities must sum to l ie W0W17fzl which using the previous relation gives 701 Aolli AoAillillz 1 Thus as long as the sum is convergent we can calculate 7m and thus all the other probabilities 7939 due to 11 This is important since this probabilities help us determine something about the system behavior as we will see soon Aside for the system to converge we need the condition A A A v 2 1 9 1 lt x 1112 llj A nite note is that the balance equation can be easily written by looking at the steadystate equations since anything out of a state should some up to anything coming in ie the ow conservationquot idea 6 Special case MlVIl Queue An important special case of B D process is the case where transition rates are state independent and are xed one for birth another for death ie Aj A 11339 11 For this example due to Poisson property we will visit shortly the interarrival time is exponentially distributed with mean 1 A and the service time is exponentially distributed with mean 111 Also A known as the average arrival rate Remember we are still talking about Markov chains This is a special case and is identi ed as the MMl queue known as Kendall s notation where rst M is for the arrival the second M is for the service time and the third entry is to denote we have one server The statetransition diagram can be shown as below For this special case we get from 11 Now 7m 2 l is 7n l A A2 17 i m 1 1 For convergence in this case we need the condition 2A 11 lt co Since this is a geometric series convergence condition is satis ed by the requirement that A 1 lt 1 We thus have A 7fgl I j 7939 lig jl2 ll 1 If we write p A 11 which is known as utilization or traffic intensity then and hence W em The convergence condition also has a simple physical interpretation Since A 1 p lt 1 this means the average arrival rate should be less than the average service rate39 if it is other way around the system will over ow What has the MMl queue anything to do with network design and analysis We have mentioned earlier that to get a handle on network modeling and performance we have to have some idea about traf c The simplest network we can think of is just a network 1ink So here A would refer to the arrival rate to a network link while u will refer to the average service rate of the link with the link being one server Speci cally for data networks we can consider the arrival rate to be in packetssec Let Nl number of packets in the link at time i Q 7 What is the average number of packets in the link 00 7 39 4 7 39 p A A I gt7 EZltl j7fj 17p ix Thus using the steadystate probabilities we can obtain the result for N What about other measures such as average packet delay To obtain this we need the use the following result known as LittIe s Law avg number of packets in system in steady state N avg arrival rate avg packet delay in system in steady state T That is A7AT Rearranging we get 1 p IVA7A 7777 2777777 u 7 A M1 7 p Average waiting time in the queue W39 is W 2 Avg waiting time in System 7 Avg waiting time in Servrce p U 7 x7 39 Again by Little s Law which is also applicable in queues the average number of customers in queue is quzAVVI Thus we have shown above four performance measures that may be of interest for a network link which can be obtained once you know the average arrival rate and the average service rate Remark An important assumption about the MMl is that the input population is considered to be in nite In generic terms the term customer is used rather than packets since such models are applicable in other areas besides communication networks We have discussed so far delay results for the average value only How about 90th percentile value For MMl we have the following 90th percentile system delay T I 7110 90th percentile queueing delay may TI 7110p 0 Example 1 Suppose average arrival rate A is 100 pps and the service rate r1 is 200 pps then the average number ofpackets in the system is N Au 7 A IOU200 7 100 l The following is a table for average number in the system and the average delay in the system for different values of A and r1 Note the impact on delay when A and r1 are scaled A r1 N T 100 200 l 10 ms 150 200 3 20 ms 175 200 7 40 ms 1000 2000 l 1 ms 1500 2000 3 2 ms 1750 2000 7 4 ms 7 0n exponential distribution This is a good time to quickly go over a couple of things about exponential distribution The pdf of the exponential distribution with parameter A is given by y 2 Ae 1 gt0 The mean and the variance are given by 8 Poisson Process A purebirth homogeneous process ie M 0 Aj A is a Poisson process Another way A stochastic process Al l 2 0 taking nonnegative integer values is said to be a Poisson process with rate A if 1 is a counting process 2 The number of arrival that occur in disjoint time interval are independent 3 The number of arrivals in interval of length 739 is Poisson distributed with parameter AT P7Al 739 7 Al n crp7ATATquotn n 0 1 Note that camp is the exponential function crpr 2 ex where e is the Euler number 271 828 1828 Important properties of a Poisson process 1 Interarrival times are independent and exponentially distributed with parameter A Tn n1 in PM lt 5 1 7 crp7A5 1 7 e7 2 Sum of two independent Poisson processes is a Poisson process with rate being the sum of the two This holds for more than two also It is important to note that the Poisson arrival can also be described by a purebirth homogeneous pro 06S S 9 Revisiting a network link In the section on MMl we mentioned why the results are applicable for a data network link We need to reiterate that MMl results are applicable for Poisson arrival discussed above and exponentially distributed service time Packet arrivals characterized by Poisson arrival is a reasonable assumption although this is NOT always a good one However this helps us get started on getting a handle on doing some analysis Typically when we think of a network link we often have some idea about the rate such as 56 Kbps etc This is a deterministic rate Now how do we get exponentially distributed service time In a link model the other factor that comes into the picture is the size of the packet that has arrived Here is where we make another assumption the packet length is exponentially distributed with mean length l 1 bits Now if we denote the speed of a link by 7 bps then the average service rate of packets is u 10 which is exponentially distributed Thus we can use the MMl model for exponentially distributed packet size for studying a network link Example 2 If link speed is 15 Mbps ie a Tllink and the average packet size is l Kbits then the average service rate u is 15 Mbpsleits 1500 packets per sec pps 10 A View on Statistical Multiplexing The next thing to realize is that all the packets that arrive to a data network link is statistically multiplexed This is a key behavior of packetswitched networks This also results in queueing of packets if all the capacity of a link is used up at a certain time 7 this points to the average packet delay we discussed earlier Consider m statistically identical and independent Poisson packet streams each with an arrival rate of Am packets per sec transmitted over a communication link with exponentially distributed service time with mean service rate 11 In case of single pipe we have total Poisson arrival as mAm A due to one of properties of Poisson process mentioned earlier Using MMl model we get the avg delay to be 1 T a u 7 A If in the link is divided into m separate pipes partitioned then the service rate of each pipe is 117 ie lmth of the rate of the original pipe In this case the avg delay again using MMl on one partition 1 m T 7 b umiAm niA Thus splitting the line into m pipes increases the avg delay by m times This is an interesting phenomenon about statistical multiplexing as a rule of thumb it is better to have a fatter link than partition the link into lower speeds since it results in more delay on average What about the effect on average number of packets due to the scenarios discussed here 11 Inverse problem Find service rate for a given average delay We now pay attention to the simplest design problem when just a single network link is considered We know that the average delay for MMl model is given by l Tz Suppose you are given A the offered traf c in arrival rate based on forecasted data and the requirement that the average link delay should not be more than Tm To meet this delay Tm we need 1 m S Tmaa which implies 2 Tmaav Thus we get a bound on the minimum service rate required to meet the requirement Since service rate corresponds to the link speed this mean we can determine minimum link speed required if the average packet size is known Although this is a simple result it ties offered traffic and QoS requirement to the service rate to be provided Example 3 Suppose that the average arrival rate is 500 pps and we are given that the average packet size is 4Kbits If the system goal is to provide an average delay of 30 ms or less what should be the link speed Here 307 2 lu 7 A lu 7 500 This implies that the service rate u is 53333 pps or higher Since the average packet size is 4 Kbits the link speed needed is at least 213 Mbps or higher 12 Finite Buffer System lVIlVIlB So far we have talked about MMl Often in reality we do not have an in nite queue to hold all the packets for transfer due to nite buffer size Thus another model of interest is the nite buffer system How is the system behavior under nite buffer scenario Assume that the size of the nite buffer is B including server but customer population is still in nite That means you can queue only up to B 7 1 If there is an arrival when the buffer is full then that arrival is dropped lost this is packet dropping due to buffer over ow Again B D model can be used here by catering speci cally to this case Here the statetransition diagram is as follows 069 G and we have A if g j g B 7 1 ii 0 otherwise 11 if 1 S j S B 0 otherwise It can be derived from B D model or from the special case MMl that HA Aj v 7 7 lt 9 out 11 LB WM 0 3171 1 j Axl 1 7 p 1 7ltAugtB1 1 7 pm For p l the following is true and 2 o p Axl 1 l v 7 39lt B 79 3 1 J Note that the packet loss probability is given by B The mean number of packets in the system B B1 7 p ltBlp A JM fp W P7E1 and A7 132 ifp l The mean number of packets at the server E N5 is EHVS PTUV 0EZVSJV 0 PTUV gt 0E7517VS gt 0 7rggtlt0l77r0 x1 Thus the mean number of packets in the queue for p l 7 7 4 7 7 p 1 BPB A q 17 7E175 17 7 1770 lip 7pm while for p l we have Nq 132 7 BB 1 Effective arrival rate is given by The mean response time average delay is T NA 2 N M1 7 7 The mean waiting time is Wquot VIIAl 17Vq AM 7 73 13 MMm model m parallel servers Another model of interest in communication networks is m parallel servers This model comes up in the case of a communication link which is divided into m circuits or channels An arriving customer can take any of the circuits on arrival OR has to wait if all the servers circuits are busy In nite population assumption is made here this model is close to a telephone network link but not quite we ll see later where the difference is and This is again a B D model where M A jg ifl g j g m 2 my forj gt m The statetransition diagram is x 7 7 x cocoa ltgtC j u 211 311 11 mu W Note that for MMm model the utilization p is A 7 lt l p my Here we can show from B D model that j 1 in for 1 g j g m 7939 j mm forj gt m Further 71 mil 39 mm Given 7r s different performance measures can be derived T mmw 0 TilKl 7 AmuD 14 MMmm model m parallel servers loss system In this case the buffer size is m including for servers with m parallel servers Ie the buffer size is the same as the number of servers thus if all the servers are occupied then an arriving customer is rejected This is the case in the telephone network link model if all the circuits are busy an arriving call is rejected instead of being queued up if one of them become free later This is a very important system and is sometimes known as the loss system The statetransition diagram is 7 quotFULL mu A ifOSjgmil 0 otherwise jll if 1 S j S m 0 otherwise In this case 391 7U AHVFWU j l m Since sum of probabilities is l we can show that 3977 A l z w i0 J Speci cally the probability of an arriving call being blocked is the probability of being in state m 77 2 W This is the wellknown ErlangB Blockingloss formula and is usually denoted by E A 1 m Further we wrote I A 1 to denote the offered load in Erlang this is NOT utilization giving us L m E1m i0 W The average number in the system N is given by N 11 7 E1 m It is interesting to note that the ErlangB loss forrnual has the following recurrence relation 1E1 m 7 l E lta m m 1E1m7 l with the starting point B1 0 1 This can also be computed iteratively Write E1 m lI1 m Then 11 m md1 m 7 l1 1 Thus the iteration to compute blocking given offered load of l erlangs and the number of channel m procedure erlangb 1 m I 1 forj l m I j 10 l endfor I ld retumb Note that here the offered load traf c is given in l erlangs Recall our discussion at the end of chapter 1 We stated there that typically for telephone networks we provide offered traffic as Offered Load Number of call attempts hour average call holding time On close scrutiny this is A 11 where 11 average call holding time Again note that the assumption of arrival is Poisson Further we assume call holding time to be exponentially distributed Example 4 Suppose that the call arrival rate is on average 10 per hour and the average duration of calls is 6 minutes then the offered load in erlangs is l 10 0 X 5 lerl If now the link capacity is l m then the call blocking probability is El 1 11 105 If now the capacity is increased to 2 m then the call blocking probability reduces to E l 2 02 Note that ErlangB formula has nonlinear property For example if offered load is 2 erl and the capacity is 2 channels then the call blocking probability is E 2 2 04 which is smaller than when l erl load was offered to link capacity of 1 channels see above 20 Example 5 This example shows how increase in call holding time impacts blocking Suppose that the average call arrival rate is 100 callshour and the call holding time is 3 min then the offered load is 5 erl If the link capacity is 10 then call blocking probability is E 3 10 0018 Now suppose that the average call duration time increases somehow to 30 minutes then the offered load is 50 erl Thus the call blocking probability increases to E 30 10 08 Note that in this example the average call arrival rate did NOT increase at all This show that the change in the average call holding time can also impact on network call blocking performance a phenomenon observed with more users using the telephone for Internet dialup Now if we wanted to keep the call blocking at the initial value of 0018 then for 50 erl of load we will need at least 61 channels This is obtained using the Inverse ErlangB formula discussed later 15 MMoc model in nite servers This is the limiting case of MMm model with m 2 0c The balance equation reduces to ij71jll7rjc Thus 1 79 Avaro j 12 From the condition Zj 7g 2 l we obtain that 7n crp71 Thus jl Thus in steadystate the number in the system is Poisson distributed with parameter A 11 The average WjltAlljwc number in the system ie number of busy channels is A A7 7 11 However we know that this nothing but I for erlang offered load Thus this gives us another interpretation for the de nition of offered load in erlangs the average number of busy servers channels there were in nite number of servers available 21 16 MIVIl A39 model single server nite population In this case we have a nite population K The statetransition diagram is K 1 K701 192 27 A 0000 27 u u u u p In this case MK ej if g j 3 K Aj 0 otherwise 11 ifl S j S K 0 otherwise Steadystate probabilities are given by V K Aj 0ltltK 9 H 7 7m J c This model is often applicable for performance evaluation of a computer system where nite population where is a good assumption 17 Inverse Erlang B given a and blocking nd the number of channels This is another inverse design problem for a network link where the offered load is given in erlangs and the acceptable blocking level is also given and we are to nd the number of channels required in the link to meet the acceptable level of blocking known as gradeofservice The problem is to nd an integral minimum m for given I and acceptable blocking 1 mm m E1 m g b In this case the inverse is not easy to calculate as in the MMl case with delay Thus an algorithmic approach is needed We provide below a rough sketch Given offeredload and bgoal estimate number of trunks 22 assign tolerance estimatedtrunk int offeredload btest erlangbofferedload estimatedtrunk if btest gt bgoal then blow btest clow estimatedtrunk while btest gt bgoal do estimatedtrunk 20 btest erlangbofferedload estimatedtrunk bhigh btest chigh estimatedtrunk endwhile else bhigh btest chigh estimatedtrunk while btest lt bgoal do estimatedtrunk 20 btest erlangbofferedload estimatedtrunk blow btest clow estimatedtrunk endwhile endif diffb blow bgoal while absdiffb gt tolerance ampamp diffc ltgt 1 do cmid int clow chigh 20 btest erlangbofferedload cmid diffb btest bgoal diffc chigh clow if diffb gt 00 then clow cmid blow btest else chigh cmid bhigh btest endif endwhile if diffb lt 00 then notrunks cmid else notrunks cmidl endif 23 Jagerman 5 presents a much elegant method where the number of channels is assumed to take nonintegral values 18 MIG1 single nonexponential server in nite population So far we have considered exponential server case However the service distribution could be non exponential Thus results for nonexponential service time are also desirable There are several results for this one however the mathematical derivation is quite complex and beyond the scope of this course As such we list a couple of results for MG 1 system below W AXZ 2lt1 7 p where P is the second moment of the service time distribution Y A2 A p A2 1 7g T l WW 1 Another important special case of MGl besides MMl is MD l ie the service time is determin istic The deterministic service time is applicable for example in ATM Asynchronous Transfer Mode networks where cell size are xed and thus service rate is xed we will address at some point later whether Poisson arrival is a good assumption for ATM traf c or for other networks such as Internet Results for MD l are listed below p p Wquot 1V 2 214179 p 2179 2 p 92 211179 q 2179 19 GMl and GGl GMl refers to the case where the interarrival time is nonexponential while the service time is still exponential Finally GGl means both interarrival time and service time are nonexponential not necessarily the same distribution 24 20 An example of a nonexponential distribution hyperexponential The pdf for twostage hyperexponential distribution 12 is given by y 2 ylule mx yzilze wx 051 oz 2 0 and k1 dz 1 The mean is EX Ll 3 1 2 The variance is 2 2 0g 051 oz V X 2 7 7 7 7 lt gag 1 2 The distribution is considered to be balanced if 051 oz 1 2 The squared coef cient of variation 72 is given by note is the second moment How about generating hyperexponential distribution Given 72 and 11 a hyperexponential with bal anced mean can be generated as follows a l 17 7271 1 2 31 dz 1 7 k1 Calculate 051 and oz as follows and 1 and 2 as follows 1 2amp1 u 2 2 20am 25 21 Considering NINIl and MDl together In the gures below we plot N and T for different values of p for the systems MMl and MD 1 Notice the difference as p a 1 MIMI1 and MID1 Average number of customers in steady state 05 00 07 00 09 utilization p El N mm1 Nmd1 MIMI1 and MID1 Average Delay H 01 07 08 09 6 El Tmm1 ll Tmd1 05 utilization P 26 Introduction to Queueing Theory Based on the slides of Prof Himyuki Ohsaki Graduate School of Information Science amp Technology Osaka University Japan 1 Contents 9 Introduction to Queueing Theory o Little s Theorem 9 Standard Notation of Queueing Systems 9 Poisson Process and its Properties 9 MMJ Queueing System 9 MMm Queueing System 0 MMmm Queueing System 9 MGJ Queueing System Introduction to Queueing Theory What is Queueing Theory L o Primary methodological framework for aiglvrairsg 7 Cir L 1 i j if 9 Often 3inilpli39iiiiiig assuri itstiugris since realistic assumptions make meaningful analysis extremely difficult o Provide a basis for adequate agprroxii naticn HIgt Packet Delay 9 is the sum of delays on each subnet link traversed by the packet o Link delay consists of l Processing delay I rijjug39su dais unk delay lTransmission delay l Propagation delay packet delay Link Delay Components 1 o Pr easing l Delay between the time the packet is correctly received at the head node of the link and the time the packet is assigned to an outgoing link queue for transmission outgoing link queue HIgt HU head node tail node 6 Link Delay Components 2 o TJ39Jeueing iglelzrjj I Delay between the time the packet is assigned to a queue for transmission and the time it starts being transmitted ignezlceingg lt gt outgoing link queue HIgt Igt head node tail node 7 Link Delay Components 3 o l rviii39igi niggion delay I Delay between the times that the first and last bits of the packet are transmitted trigismissiol lelegtiy lt gt outgoing link queue HIgt HU head node tail node 8 Link Delay Components 4 o i rrgygiuaigii tigm delay I Delay between the time the last bit is transmitted at the head node of the link and the time the last bit is received at the tail node outgoing link queue HIgt Igt head node tail node 9 Queueing System 1 o packets arrive at random times to obtain service 9 time transmission delay is LC IL Packet length in bits I C Link transmission capacity in bitssec customer packet I service packet transmission HIgt Queueing System 2 o Assume that we already know quot to know quot nun if Cii 3l3t lquot1 Eli in the system 4 my per customer lt gt average delay customer arrival rate average of customers customer service rate 11 Little s Theorem Definition of Symbols 1 o pn Steadystate probability of having n customers in the system 9 rats inverse of average interarrival time o z rate inverse of average service 2quot jugatcjmere in the Definition of Symbols 2 o N0 Average number of customers waiting in queue o T Average customer time in the system o W Average customer waiting time in queue does not include service time o 5 Average service time of customer arrivalsdepa rtu res Little s Theorem o N Average number of customers 9 2 Arrival rate o T Average customer time 9 Hold for almost M rsirm that reaches a steady tate o Express the natural idea that crowded systems large IV are associated with long customer delays large 7 and reversely 139KgJ Illustration of Little s Theorem o Assumption lThe system is initially empty lCustomers depart from the system in the order they arrive 061 delay 7392 delay 739 Application of Little s Theorem 1 o No Average of customers waiting in queue o W Average customer waiting time in queue silg r 2L o X Average service time o p Average of packets under transmission V o 4 LI lvquot 9 p is called the utilization r the proportion of time that the line is busy transmitting a packet Application of Little s Theorem 2 o 2 Packet arrival rate at node i o N Average total of packets in the network 21 Little s Theorem Problem o Customers arrive at a fastfood restaurant as a Poisson process with an arrival rate of 5 per min 9 Customers wait at a cash register to receive their order for an average of 5 min o Customers eat in the restaurant with probability 05 and carry out their order without eating with probability 05 o A meal requires an average of 20 min 9 What is nun itier of in the restaurant Answer 75 19 Standard Notation of Queueing Systems Standard Notation of Queueing Systems 1 XYZK L iture if arr i if39cii prof IME i iemor Poisson process exponentially distributed interarrival times distribution of interarrival times n iinistir interarrival times XYZK o Yindicates quotthe iiiroitrabiiity Eigjstriimition of quottits Eii i iEr Tii distribution of service times distribution of service times ii iisti distribution of service times XYZK 9 Z indicates 9 K optional indicates iii iimit cn Titii f i of ririiltmear in the system 9 Examples lMMl MMm MMoo MMmm I MGl GGl lMDl MDlm Poisson Process and its Properties Poisson Process A stochastic process An tgt 0 Am gt0 is said to be F39C clSTT Ul i j lquot vcr2f1 witi39l r E lti if Am is a counting process that represents licijsziil rulinlaer of rail in 0 t The numbers of arrivals that occur in cili join t are incl The number of arrivals in any t t r is l39i39aji Eil l viiifzriji iboiled with parameter M 4 17 PAtr At n e 39 71 n 1311931 Gisttrihimzti i PTn S s 21 e o The ii iczan and variance of interarrival times 277 are LivyquotQt ancl 1M2 respectively Properties of Poisson Process 2 If two or more independent Poisson process A1 Akare it quotiir A A1 A2 Ak tl l p 1 with a rate equal to the sum of the rates of its components 11 merge A1 k 1 S A 21111 A 1 pr M5 Ak independent Poisson processes Properties of Poisson Process 3 o If a Poisson process A is into other 31 quot A1 and A2 by randomly assigning each arrival to A1 or A2 A LKL and split randomly With Pr0bability p 11 A1 Poisson process With PFOb lbiIi W 117 22 A MMJ Queueing System MMJ Queueing System o A single queue with a single at 9 Customers arrive according to 2 with rate 9 o The probability distribution of the service time is with mean 1 u single server Poisson arrival with arrival rate k Exponentially distributed service time infinite buffer with service rate u 30 MMJ Queueing System Results 1 o Utilization factor proportion of time the server is busy 0 u 9 Probability of n customers in the system pnpquot1 p in MMJ Queueing System Results 2 o Average customer time in the system N 1 7 H o Average number of customers in queue 2 NQ 1W p 1 p o Average waiting time in queue WT 1 p 1 MMJ Queueing System Problem o Customers arrive at a fastfood restaurant as a Poisson process with an arrival rate of 5 per min 9 Customers wait at a cash register to receive their order for an average of 5 minutes o Service times to customers are independent and exponentially distributed o What is the at the cash register Answer 52 o If the cash register serves 10 faster what is Cl iEi waitil lggf time of customers Answer 139min 33 MMm Queueing System MMm Queueing System o A single queue with 16i quot iiiquot3 9 Customers arrive according to Poi with rate 9 o The probability distribution of the service time is with mean lu m servers Poisson arrival G Bponentially with arrival rate k distributed service time with rate u infinite buffer 35 MMm Queueing System Results 1 o Ratio of arrival rate to maximal system service rate 1 a o Probability of n customers in the system mpquot mmm pozl M k m1 pJ l MMm Queueing System Results 2 quot3 that an arriving has viiiiii a m customers or more in the system Pg 2 pomp m 1 p o Average waiting time in queue of a customer N P W Q 390 Q 1 11 p o Average number of customers in queue oo pPQ N Z n mn Q 2110 p MMm Queueing System Results 3 o Average customer time in the system T i W i PQ my 1 o Average number of customers in the system Nx1Tmpp PQ l p MMm Queueing System Problem o A mailorder company receives calls at a Poisson rate of 1 per 2 min 0 The duration of the calls is exponentially distributed with mean 2 min o A caller who nds all telephone operators busy patiently waits until one becomes available o The number of operators is 2 on weekdays or 3 on weekend 9 What is waiting time of customers in queue Answer 067min and 009min 39 MMmm Queueing System MMmm Queueing System o A single queue with 16i quot iiiquot3 trtiff 9 Customers arrive according to Poi with rate 9 o The probability distribution of the service time is with mean lu m servers Poisson arrival G Bponentially with arrival rate k distributed service time with rate u buffer size m 41 MMmm Queueing System Results o Probability of m customers in the system p022 1 1 tot Z n iulaj m p 1 y m 20 1 y n MMmm Queueing System Problem o A telephone company establishes a direct connection between two cities expecting Poisson traf c with rate 05 callsmin o The durations of calls are independent and exponentially distributed with mean 2 min o Interarrival times are independent of call durations o 1115leCli il39itiltii should the company provide to ensure that an attempted call is blocked with probability less than 01 Answer 3 43 MGJ Queueing System MGJ Queueing System 9 A single queue with 1 single 9 Customers arrive according to Poi with rate 9 o The mean and S Ct l39if l rntmant of the service time are 1u and X2 single server Poisson arrival with arrival rate k Generally distributed service time Inflnlte bUffer with service rate u 45 MGJ Queueing System Results 1 o Utilization factor A 0 u o Mean residual service time RZMz 2 MGJ Queueing System Results 9 PollaczekKhinchin formula R M2 1 p21 p T2iW y ZzXz 21 p ZzXz 21 p NQZlW NxlTp Conclusion 9 Queueing models provide qualita ive insigl its on the performance of computer networks and wantitsgtive jreotlistim39is of average packet delay o To obtain tractable queueing models for computer networks it is frequently necessary to make 5ii i iili39fjii ig quiltions o A more accurate alternative is simulation which however can be i 1 ml lacking in Emil iht
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'