Networking Theory and Fundamentals - Lecture 1

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:75

Thêm vào BST

Báo xấu

77
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo giáo trình lý thuyết mạng căn bản bằng tiếng anh dành cho sinh viên chuyên ngành công nghệ thông tin

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Networking Theory and Fundamentals - Lecture 1

TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania Delay Models in the Network Layer It is important in data communication settings to be able to characterise the delay that individual packets are subjected to in their sojourn through the system. Delays can be traced to four main causes. • Processing delay : This is the time it takes to process a frame at each subnet node and prepare it for retransmission. These delays are deter- mined by the complexity of the protocol and the computational power available at each subnet node. • Propagation delay : This is the time it actually takes a frame to prop- agate through the communication link. These delays are dictated by the distance or length of the communication pathway. They can be signiﬁcant, for instance, in satellite links and in high-speed links when the propagation delay can be a signiﬁcant fraction of the overall delay. • Transmission delay : This is the time it takes to transmit an entire frame, from ﬁrst bit to last bit, into a communication link. These delays are dictated primarily by link speed, for example, a 9600 bps link occasions only half the delay of a 4800 bps link. • Queueing delay : This is the time a frame has to wait in a queue for ser- vice. These delays are occasioned by congestion at the subnet nodes. Propagation delays are determined by the physical channels and are inde- pendent of the actual traﬃc patterns in the link; likewise, processing delays are determined by the available hardware and again are not aﬀected by traf- ﬁc. We hence focus on the transmission and queueing delays endemic at any subnet node. The discussion ignores the possibility of retransmissions, which of course add to the overall delay. In practice, however, retransmis- sions are rare in many data networks so that this assumption may safely be 1
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania made.1 Queues are intrinsic to packet-switched networks. In a generic packet-switching network, Subnet node frames arrive asynchronously at Packets arrive Packets depart asynchronously asynchronously subnet nodes in the communica- tion subnet and are processed and released according to some ser- vice protocol, for instance, a ﬁrst- in, ﬁrst-out (FIFO) or ﬁrst-come, ﬁrst-served (FCFS) protocol. Typically, a subnet node cannot handle all the traﬃc entering it simultaneously so that frames arriving at the node are buﬀered to await their turn for transmis- sion. In queueing parlance, the frames are “customers” awaiting “service” from the subnet node which is hence the “server.” The overall queueing delay for a frame (customer) is determined generally by the congestion at the subnet node (server) which is governed by packet arrival statistics and the service discipline in force. Buffer Server Arriving Departing packets packets Single-server queue Multi-server queue More speciﬁcally, node congestion is inﬂuenced by the following factors: • Arrival statistics embodied in the distribution of customer interarrival times τ. (The arrival rate λ = 1/ E(τ) will play a critical rˆle in the o sequel.) • Buﬀer size m—for instance, ﬁnite buﬀer systems (m < ∞) in which customers are turned away if the queue is full, and inﬁnite buﬀer sys- tems (m = ∞) in which customers are always accepted into the system. 1 Multi-access networks are the exception which proves the rule: retransmissions are the rule rather than the exception in multi-access settings. 2
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania • Number of servers n—for instance, single-server systems (n = 1), multi-server systems (n ≥ 2), and inﬁnite-server systems (n = ∞). • Service statistics embodied in the distribution of customer service times X. (The mean service time E(X) = 1/µ, in particular, will prove to be a particularly useful concept in the sequel.) Together, these determine the delay faced by each customer. A succinct notation has evolved to describe the various factors that aﬀect the congestion and delays in a queueing environment. A generic queueing environment is described in the form A/B/c/d, where the ﬁrst two descriptors A and B connote the arrival and service statistics, respectively, and the second two descriptors c and d (if present) connote the number of servers and the system capacity (buﬀer size or maximal number of cus- tomers in the system), respectively. The descriptors A and B are speciﬁed by the arrival and service statistics of the queueing discipline and may be speciﬁed, for instance, as M (exponential or memoryless distribution), E (Er- langian distribution), H (hyperexponential distribution), D (deterministic), or G (general distribution), to mention a few possibilities. The descriptors c and d take on positive integer values, allowing inﬁnity as a possible value to admit limiting systems with an inﬁnite number of servers and/or inﬁnite storage capacity which are of theoretical interest. Little’s Theorem Consider a queueing environment which, after initial transients have died down, is operating in a stable steady state. Customer N customers in system Customer arrivals departures (rate λ) T time per customer (Closed) queueing environment in steady state The key parameters characterising the system are: • λ—the mean, steady state customer arrival rate. • N—the average number of customers in the system (both in the buﬀer and in-service). 3
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania • T —the mean time spent by each customer in the system (time spent in the queue together with the service time). It is tempting and intuitive to hazard the guess N = λT. This indeed is the content of Little’s theorem which holds very generally for a very wide range of service disciplines and arrival statistics. To motivate the result, consider a general, stable queueing envi- ronment which has customers arriving in accordance with some underlying arrival statistics and departing regulated by some given service discipline. Arrival, Departure Processes. At any instant of time t, let A(t) and D(t) denote the number of arrivals and departures, respectively, in the time in- terval [0, t]. The random processes A(t) and D(t), called the arrival and de- parture process, respectively, are governed by the probability distributions underlying customer arrivals and service provision, and provide a compre- hensive instantaneous description of the state of the system at any time t. The adjoining ﬁgure illus- trates sample functions of the ar- A(t) rival and departure processes. Ob- D(t) serve that the sample functions of Sample Function the processes A(t) and D(t) are -> Step Function Cadlag step functions with jumps of unit Contin ‘a droi ue limite ‘a gauch height. Indeed, both processes t are counting processes with the jump points indicating an arrival N(t) = A(t) - D(t) = # customers in system at time t or departure. Observe further that the sample functions of the depar- ture process lag the correspond- ing sample functions of the ar- N(t) rival process. The random process t N(t) = A(t) − D(t) then represents the instantaneous number of cus- tomers present in the queueing environment (both in-queue and in-service) at time t. Example 1 Transmission line. Consider a transmission line system with packets arriving every K seconds for transmission. Trans Departing miss Arriving ion line packets packets 4
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania Suppose that each packet requires a transmission time of aK seconds (a < 1) and that the propagation time for each packet is bK seconds. Viewing the transmission line as a server and packets as customers, customers arrive at a ﬁxed rate λ = 1/K packets/second. Each customer spends a ﬁxed amount of time in the system T = (a + b)K. The number of packets that enter the line before a given packet departs is hence N = T/K = a + b. This is the average number of packets in the line in the steady state. The arrival process A(t) is a ﬁxed time function which has regular unit jumps every K seconds; the departure process D(t) is also a ﬁxed time function with jump points regulated by the value a + b. Two cases, 0 < a + b < 1 and 1 < a + b < 2 are shown. A(t) A(t) D(t) D(t) 0ψ
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania via the ﬁgure that the area under the curve (up to t) of the instantaneous number of customers in the system is identically equal to the area between the arrival and departure sample functions which, in turn, is comprised of A(t) rectangular blocks of unit height and widths T1 , . . . , TA(t) . More formally, A(t) t t N(τ) dτ = A(τ) − D(τ) dτ = Ti . 0 0 i=1 Consequently, we obtain A(t) A(t) A(t) 1 1 ^ N(t) = Ti = Ti . t t A(t) i=1 i=1 The ﬁrst quantity on the right-hand side may be identiﬁed with the average arrival rate of customers up to time t: A(t) ^ λ(t) = . t Likewise, the second term on the right-hand side may be identiﬁed with the average time spent by the ﬁrst A(t) customers in the system: A(t) 1 ^ T (t) = Ti . A(t) i=1 Thus, we obtain ^ ^^ N(t) = λ(t)T (t). Now suppose that, as t → ∞, the various time averages tend to ﬁxed steady state values N(t) → N, ^ Queueing Environment ^(t) → λ, and T (t) → T . We then ^ λ obtain Little’s formula N = λT Arrivals Departures where we interpret N as the steady state, average number of customers in the system, λ as the steady state arrival rate of customers into the system, and T as the steady state, average time spent in the system by each customer. 6
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania It may be remarked that the formulation, while derived for a FIFO system, is actually very general and in fact applies to a very wide spectrum of queueing environments and service disciplines. Ensemble Averages. Little’s theorem extends quite naturally to situations where the arrival and departure processes, A(t) and D(t), are speciﬁed by some underlying probability law. Indeed, suppose that at time t the number of customers N(t) in the system has distribution πn (t). Then, the expected number of customers in the system at time t is given by ∞ ¯ N(t) = E N(t) = nπn (t). n=0 Now, for a large number of systems, the distribution of customers tends to a steady state or stationary distribution πn (t) → πn as t → ∞. Then, ∞ N(t) → N = (t → ∞). ¯ ¯ nπn n=0 Likewise, the mean time spent in the system by a customer tends to a limit- ing value Ti = E Ti → T (i → ∞), ¯ ¯ as does the instantaneous, mean customer arrival rate E A(t) →¯ (t → ∞). ¯(t) = λ λ t A fundamental result known as the ergodic theorem allows us to relate these steady state ensemble averages to the time averages obtained from individ- ual sample functions: for a very wide range of situations, including most situations encountered in practice, N = N, T = T , and λ = ¯ with probability ¯ ¯ λ one. Thus, we can heretofore apply Little’s theorem with conﬁdence to any closed queueing environment where we interpret the various quantities as steady state, long-term averages. Applications of Little’s Theorem The power of Little’s theorem is in its very wide applicability though care should be taken to make sure that it is applied in the context of a sta- ble, closed queueing environment where the mean arrival rate of customers matches the mean departure rate and the system is operating in the steady state. Some examples may serve to ﬁx the result. 7
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania Example 2 Transmission line, reprise. Suppose, as before, that packets arrive at regular intervals of K sec- onds to a transmission line. As before, the transmission time for each packet is aK (where 0 < a < 1) and the propagation delay is bK (for some positive b). Trans Departing miss Arriving ion line packets packets The queueing environment consists of a single server (the trans- mission line). Packets arrive at a rate λ = 1/K packets/second, with each packet staying in the system a total of T = aK + bK seconds. Little’s the- orem hence shows that the steady-state average number of packets in the system is N = λT = a + b. Recall that the actual number of packets in the system is a periodically varying, deterministic function so that the number of customers in the system never converges, even in the limit of very large time, to the constant N (cf. Example 1). The long-term average number of customers in the system, however, tends to N. Example 3 Access-controlled highway entry. If, in the previous transmission line example, we view the opera- tions of transmission and propagation in reverse order, we obtain a related service discipline. In this alternative setting, customers arrive peri- odically every K seconds, i.e., the customer ar- rival rate is λ = 1/K, wait in queue for bK sec- onds, and are serviced and released in aK sec- onds. We may identify this queueing environment with an (idealised) access-controlled highway en- Merging delay aK try system where traﬃc is permitted to enter a Metering delay bK highway access road at a ﬁxed rate of λ = 1/K cars per second. The cars wait in a queue of ﬁxed Arrival rate of cars size (ﬁxed buﬀer size) and are released periodi- to highway access λγ cally, one at a time, by a stop light metering sys- tem; the wait time in queue is bK seconds. Finally, on release, the car at the head of the queue moves at a ﬁxed rate over the access road to merge with traﬃc in the highway; the time taken to traverse this segment is aK seconds. Observe that Little’s theorem applied to the queueing segment alone shows that the average number of customers waiting in queue is bK/K = b, while Little’s theorem applied to the service segment yields the (fractional) average number of customers being serviced at any instant aK/K = a. Ap- plying Little’s theorem to the entire system consisting of queue and server 8
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania yields the average number of customers in the system N = (aK + bK)/K = a + b which is the sum of the number of customers in the two segments of the service discipline, as it should be. Observe that, while the physical details are rather diﬀerent, macro- scopically the two service disciplines are equivalent—at least in the average- sense, long term world view of Little’s theorem. Example 4 Airline counters. Consider a closed queueing environment in which customers enter- ing the system wait in a single queue for service from n service agents. The customer at the head of the queue proceeds for service to the ﬁrst available server who immediately begins service for the new customer as soon as the previous customer has departed. The average service time for a customer is X. Suppose that the the environment has a ﬁnite capacity and that, at any given (2) moment, there are no more than N cus- (1) tomers in the system. (For instance, we 1 may consider an idealised airport counter type of environment in a room with ﬁ- λγ nite capacity or a ﬁxed length serpentine n queue with a ﬁxed winding roped-oﬀ bor- der.) Suppose additionally that demand is such that any departing customer is instantly replaced by another customer. (All holiday airfares are advertised at half- price.) What is the average time a customer can expect to spend in the system once he enters it? Let λ denote the steady state mean arrival rate of customers into the system and T the average time spent in the system by each customer. Little’s theorem applied to the entire system (queueing environment A) yields N = λT , while an application of the theorem to the subsystem consisting only of the n servers (queueing environment B) yields n = λX. (Observe that, in steady state, the arrival rate to the system of servers must be exactly the same as the arrival rate into the system, else instability results.) It follows that the average time spent in the system by each customer is N (∗) T = N/λ = X. n Intuitive and satisfactory. Indeed, the form of the result is quite suggestive. Consider the following variation. Probabilistic airline counters. In a probabilistic variation, consider, as before, a ﬁnite capacity system which can accommodate at most N customers at a time with service being provided by n servers. The average service time per 9
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania ¯ customer is X. Suppose that there is constant demand so that the system is always full with each departing customer being promptly replaced by an arriving customer. In this version of the airport counter problem, each server has her own queue of customers. A customer entering the system joins a queue uniformly at random and awaits his turn for service. What is the average time spent in the system by a customer? Consider the ith subsystem con- sisting of the ith server with her associ- ated queue and let Ni , λi , and T i denote (2) (1) the mean number of customers in the ith 1 subsystem, the arrival rate into the sub- system, and the mean time spent in the λγ subsystem by a customer, respectively. n Then, Little’s theorem applied to the sub- system yields T i = Ni /λi . To determine the mean arrival rate into the ith subsys- tem, consider the queueing environment consisting of the ith server alone. In the steady state, suppose that the server is busy a fraction ρi of the time or, equivalently, is idle for a fraction 1 − ρi of the time. Little’s theorem then yields ρi = λi X. The quantity ρi connotes the mean utilisation factor for server i in the steady state. How then does one go about estimating the mean utilisation factor? The ergodic theorem tells us that, with probability one in the steady state, the fraction of time that a server is idle is iden- tically the instantaneous probability (at an arbitrary point in time in the steady state) that the server is idle, i.e., has no customers in service. Write π0 for the steady state instantaneous probability that the ith server is idle. It follows that ρi = 1 − π0 so that T i = Ni X ρi . Now note that T i = T for each i as all servers have the same average customer delay. Furthermore, Ni = N/n as, on average, each subsystem sees a fraction 1/n of the custom. Finally, observe that π0 is identically the probability that each of the N cur- rent customers in the room have selected a server other than i. It follows 1N that π0 = 1 − n . Consequently, 1N N (∗∗) T= X 1− 1− . n n The ratio of the mean delay in (∗) to that of (∗∗) is precisely 1 1 > 1. = 1N ρi 1− 1− n Thus, the congestion independent assignment of customers to queues lead- ing to (∗∗) results in an added cost in total delay corresponding precisely 10
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania to the mean time that a server is idle. Contrariwise, in the original system leading to (∗), all servers are constantly busy. The gentle reader should be able to make the correspondence between these two systems and statistical multiplexing (wherein system resources are maximally utilised) and time- or frequency-division multiplexing (wherein resources are allocated ahead of time). Example 5 Supermarket counters. Consider an n server system in which each server has a dedicated queue of customers to service. Suppose that the ith server sees a cus- tomer arrival rate of λi and that a typical (3) customer served by the ith server sees an average delay of Ti from the moment of (2) (1) ﬁrst arrival to the queue to the moment of 1 λ 1 completion of service. Let Ni denote the mean combined number of customers in the ith subsystem. Little’s theorem applied to the ith n λ n subsystem now yields Ni = λi Ti . Now, n n let N = i=1 Ni , λ = i=1 λi , and T de- note, respectively, the mean number of customers in the entire system, the total customer arrival rate into the system, and the average time spent by a cus- tomer in the system, respectively. Little’s theorem applied to the whole system hence yields n N λi T= Ti . = n λ j=1 λj i=1 Probabilistic interpretation. The expression for the average customer delay has an intuitive probabilistic interpretation. Suppose each customer ran- domly selects a server queue, picking the ith server queue with probability n pi = λi j=1 λj . Then the average customer waiting time at the counter before completion of service is n n λi T = E{pi } (T ) = pi T i = T i, n j=1 λj i=1 i=1 which is the same result obtained before. Example 6 Transmission line polling system. Consider a polling system in which m users time share a transmis- sion line. A switching mechanism is put into place whereby the line ﬁrst 11
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania transmits some packets from user 1, then proceeds to transmit some pack- ets from user 2, and continues likewise until it transmits some packets from user m. The line then returns to user 1 in round-robin fashion and repeats the process. (1) (m) λ1 (2) λm Round robin switching Suppose user i has packets arriving at a rate λi , each packet demanding an average transmission Packets from Overhead for (1) user m user m time Xi . In addition, suppose that when the line switches to user i, an av- erage negotiation or overhead period m Ai is required by the line to adjust to the new user before it can start trans- mitting packets from the user. What is the average round-robin cycle duration L before the line switches back to a given user? The problem is simpliﬁed by view- ing the overhead/negotiation periods as time occupied in sending virtual packets of indi- vidual virtual users. In this viewpoint, the transmission line serves 2m users in turn, Virtual user 1 A1 (1 , 1, 2 , 2, . . . , m , m), where i denotes the ith virtual user corresponding to the negotiation User 1 X1 period for user i, before returning to user 1 to begin a new cycle. We may hence model the transmission line as a single-server queueing system with varying average service times de- Virtual user m Am pending on the nature of the user: Ai for overhead packets of ith user, Xm User m X= Xi for real packets of ith user. Equivalently, service may be broken down into a system of 2m servers where servers take turns cyclically and sequentially with server i taking care of the overhead period for customer i (i.e., virtual customer i ) and server i taking care of customer i. Let Ni and Ni denote the steady- state average, instantaneous number of customers seen by servers i and i, 12
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania respectively. At any given moment, precisely one customer is in service and the remaining 2m − 1 servers are idle. It follows that i (Ni + Ni ) = 1. Thus, we can identify Ni and Ni as the fraction of the time that servers i and i, respectively, are busy. When server i is busy, the average service time (processing the overhead for user i) is Ai ; and as the overhead period for user i recurs, on average, every L seconds, it follows that the mean arrival rate of virtual user i is 1/L. Little’s theorem applied to server i alone hence yields Ni = Ai /L. Likewise, server i expends an average amount of time Xi in service of user i whose customers (packets) arrive at a rate λi . Little’s theorem again yields Ni = λi Xi . It follows that m m Ai 1= λi Xi , + L i=1 i=1 from which we readily obtain the expression m i=1 Ai L= m 1− i=1 λi Xi for the average cycle length. Example 7 Time-sharing computer. Consider a computing system where a central computer is accessed by N terminals (users) in a time-sharing fashion. Suppose that there is a sustained demand for computing time so that a vacating user’s place is promptly taken by a new user. In such a system, it would be useful, from a system administrator’s perspective, to obtain a realistic assessment of the throughput, i.e., the average number of users served per second. Suppose that each user, after a period of reﬂection lasting R seconds on average, submits a job to the computer which, again on average, requires P sec- 1 onds of cpu time. Suppose T is the av- erage time spent by each user at a termi- λγ CPU nal for a given job, and let λ denote the N throughput achieved. Then Little’s theo- rem applied to the queueing environment comprised of computer and N terminals yields N = λT (as the system always has N customers in it). Now, each client, on av- erage, will require at least R + P seconds (if his job is taken up immediately by the computer) and at most R + NP seconds (if he has to wait till all other jobs are processed). It follows that the average time spent by each customer 13
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania in the system may be bounded by2 R + P ≤ T ≤ R + NP. On the other hand, the throughput would be maximum if each client’s job was immediately taken up by the computer so that 1 λ≤ . P In combination with Little’s theorem we may now obtain the bounds N 1 N max{R + P, NP} ≤ T ≤ R + NP, ≤ λ ≤ min , . R + NP P R+P The achievable throughput and delay regions are readily seen as a function of the number of terminals N in the following ﬁgure. T T R + NP N / (R + P) NP 1/P R+P N / (R + NP) achievable throughput N N A Little Probability Theory Before we proceed to analyse the peccadilloes of individual queueing sys- tems, let us detour through a quick review of some of the probabilistic con- cepts that will be needed. Poisson and Exponential Statistics The Poisson and exponential distributions are closely related and are impor- tant in modelling arrivals and departures in many queueing environments in practice. A quick review of (some of) the important features of these distributions is therefore in order. a facetious note for the theoretical computer scientist: more evidence that P ≠ NP? 2 On 14
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania The Poisson Distribution. Suppose X is a discrete random variable taking values in the nonnegative integers {0, 1, 2, 3, . . . }. If, for some positive λ, the distribution of X is of the form λn P{X = n} = e−λ (n ≥ 0), n! we say that X is a Poisson random variable with parameter λ, and write simply X ∼ Po(λ). Poisson random variables occur in a wide variety of situa- tions in analysis and practice. Perhaps the best-known example of random events obeying the Poisson law is that of radioactive decay: the number of radioactive particles emitted by a radioactive substance and detected by a detector over a given interval of time t follows a Poisson law to a very good approximation. Other instances include: the number of chromosome inter- changes in organic cells under X-ray irradiation; the number of connections to a wrong number; the distribution of ﬂying bomb hits on London during World War II; and last, but not least, the arrival of customers in many queues in practice. It is easy to determine the moments of a Poisson random variable. To begin, observe that the Taylor series expansion for eλ readily yields the following identities: ∞ λk = eλ , k! k=0 ∞ ∞ λk λk−1 = λeλ , k =λ k! (k − 1)! k= 0 k= 1 ∞ ∞ λk λk−2 = λ2 = λ2 eλ . k(k − 1) k! (k − 2)! k=0 k= 2 It follows readily that if X is Poisson with parameter λ, then ∞ λk ke−λ E(X) = = λ, k! k= 0 and, likewise, ∞ ∞ ∞ λk λk λk E(X2 ) = k2 e−λ k(k − 1)e−λ ke−λ = λ2 + λ. = + k! k! k=0 k! k= 0 k= 0 It follows immediately that 2 Var(X) = E(X2 ) − E(X) =λ 15
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania as well. To summarise: if X ∼ Po(λ) then E(X) = Var(X) = λ. Higher order moments can be determined analogously. A key property of Poisson random variables is that sums of inde- pendent Poisson variables are also Poisson. Key Property Suppose { Xi , i ≥ 1 } is a sequence of independent Poisson k variables with Xi ∼ Po(λi ). Then, for every k, the partial sum Sk = i=1 Xi is k Poisson with parameter i=1 λi . Proof: The simplest proof is by induction. The base case for k = 1 is im- mediate. As induction hypothesis, suppose Sk−1 is Poisson with parameter k−1 i=1 λi . It is easy now to recursively specify the probability mass function of Sk : we have n n P {Sk = n } = P{Sk−1 = m, Xk = n − m} = P{Sk−1 = m} P{Xk = n − m} m=0 m=0 n λn−m (λ1 + · · · + λk−1 )m e−(λ1 +···+λk−1 ) k e−λk = m! (n − m)! m=0 n e−(λ1 +···+λk−1 +λk ) n (λ1 + · · · + λk−1 )m λn−m = k n! m m=0 + · · · + λk−1 + λk )n −(λ1 +···+λk−1 +λk ) (λ1 =e , n! the last step following via the binomial theorem. Thus, Sk is also Poisson k with parameter i=1 λi . This completes the induction. The Exponential Distribution. Suppose X is a nonnegative random vari- able. If, for some positive µ, the distribution function and probability den- sity function of X are of the form 1 − e−µx if x ≥ 0, FX (x) = P{X ≤ x} = 0 if x < 0, µe−µx if x ≥ 0, dFX (x) pX (x) = = dx 0 if x < 0, we say that X is an exponentially distributed random variable with parameter µ, and write simply X ∼ Exp(µ). The various moments of an exponentially 16
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania distributed random variable are easy to compute via successive integration by parts. In particular, if X ∼ Exp(µ), then ∞ ∞ 1 µxe−µx dx = E(X) = xpX (x) dx = . µ −∞ 0 Similarly, ∞ ∞ 2 E(X2 ) = x2 pX (x) dx = µx2 e−µx dx = , µ2 −∞ 0 so that 1 2 Var(X) = E(X2 ) − E(X) . = µ2 To summarise: if X ∼ Exp(µ), then 1 1 E(X) = , Var(X) = . µ2 µ Higher order moments can be determined analogously. The exponential distribution arises naturally in many contexts wher- ever a random quantity under consideration has a “memoryless” character. Formally, a random variable X is said to exhibit the memoryless property if, for every pair of positive real numbers r and s, P{X > r + s | X > r} = P{X > s}. (†) For instance, it is appropriate in many queueing settings to model customer service times as being memoryless in the sense that the additional time re- quired to ﬁnish servicing the customer is independent of the amount of service that he has already received. Another example where a memory- less property may be evidenced in a queueing setting is the times between customer arrivals; in many applications, these inter-arrival times may be modelled as memoryless in that the additional time that has to elapse be- fore the next arrival is independent of how much time has already elapsed since the previous arrival. Key Property A random variable X has the memoryless property if, and only if, it is exponentially distributed. Proof: Write G(r) = 1 − F(r) for the right tail of the distribution function of X. (For simplicity, we dispense with the subscript X as there is no danger of confusion here.) Then, by deﬁnition of conditional probability, P{X > r + s, X > r} P{X > r + s} G(r + s) P {X > r + s | X > r} = , = = P {X > r} P{X > r} G(r) 17
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania while, the right-hand side of (†) is just P{X > s} = G(s). Accordingly, X has the memoryless property if, and only if, it’s distribution satisﬁes (††) G(r + s) = G(r)G(s) for every r > 0 and s > 0. If X ∼ Exp(µ) then G(r) = 1 − F(r) = e−µr for every r > 0. Then G(r + s) = e−µ(r+s) = e−µr e−µs = G(r)G(s), for every r > 0 and s > 0. It follows that any exponentially distributed random variable has the memoryless property. More generally, it follows from a basic fact from analysis that the only distribution satisfying (†) is the exponential distribution.3 The exponential and Poisson distributions are intimately related, as we will see shortly. Poisson Random Processes. In order to be able to characterise the steady state of a queueing environment it is important to statistically characterise the time evolution of the total number of arrivals into the system A(t) and the total number of departures from the system D(t). These are both exam- ples of counting processes characterised by the occurrence of elementary events—arrivals in the case of the arrival process A(t) and departures in the case of the departure process D(t). Formally speaking, a counting pro- cess { X(t), t ≥ 0 } is a nonnegative, integer valued random process whose sample functions are nondecreasing and for which, for every pair of time instants s and t with s < t, X(t) − X(s) denotes the number of occurrences of an elementary event (arrivals or departures) in the time interval (s, t]. It is clear that the sample functions of a counting process have a step-like char- acter, increasing only at points of jump where the function value increases by an integral amount. In many cases in practice, arrivals or departures may be modelled as being independent over disjoint time intervals; furthermore, it is frequently possible to model the number of arrivals or departures that occur in an observation interval as being determined statistically only by the length of the interval and not on where the interval is positioned. The formalisation of these notions leads to the deﬁnition of independent and stationary increments, respectively. 3 The reader may wish to try her hand at proving the following generalisation: if G(r) is a solution of (††) deﬁned for r > 0 and bounded in some interval, then either G(r) = 0 for all r, or else G(r) = e−µr for some constant µ. 18
TCOM 501: Networking—Theory and Fundamentals Class Notes Santosh S. Venkatesh c 1997 University of Pennsylvania We say that a counting process X(t) has independent increments if the number of elementary events occurring in disjoint time intervals are independent. Formally, we require that for every positive integer k, and every collection of time instants s0 < s1 < s2 < · · · < sk , the random variables Xi = X(si ) − X(si−1 ) (1 ≤ i ≤ k) are independent. We say that a counting process X(t) has stationary increments if the distribution of the number of elementary events that occur in any observa- tion interval depends only on the length of the interval. Formally, we require that the probability mass function P{X(t + s) − X(s) = n} (n ≥ 0) depends only on the interval length t and not on s. The most important counting process for our purposes is the Pois- son process. A random process { X(t), t ≥ 0 } is said to be a Poisson process with rate λ > 0 if: X(0) = 0. X(t) has independent increments. The number of elementary events that occur in any interval of length t is Poisson distributed with parameter λt; i.e., e−λt [λt]n P X(t + s) − X(s) = n = (n = 0, 1, 2, . . . ) n! for every t and s. In other words, X(t + s) − X(s) ∼ Po(λt) for every t and s. It is not hard to demonstrate that a Poisson process satisﬁes the following properties: x Almost all sample functions of the process are monotone, nondecreas- ing, increasing only in isolated jumps of unit magnitude. Indeed, consider the number of elementary events that occur in any interval of duration δ. The points where these jumps occur may be identiﬁed with the times when some sort of random event occurs, such as, for instance, the arrival of a customer to a queue. The occurrence of an elementary event is called an arrival. With this interpretation then, X(t + s) − X(s) stands for the number of arrivals between the times s and t + s. Observe that λ can now be identiﬁed as simply the expected rate of arrivals. y The number of arrivals over disjoint time intervals are independent. More precisely, suppose { sk , k ≥ 0 } is a strictly increasing sequence of points in time and write Xk = X(sk ) − X(sk−1 ) for the number of arrivals 19
Class Notes TCOM 501: Networking—Theory and Fundamentals Santosh S. Venkatesh c 1997 University of Pennsylvania in the time interval (sk−1 , sk ]. Then { Xk , k ≥ 1 } is a sequence of indepen- dent, Poisson random variables, with Xk ∼ Po λ(sk − sk−1 ) (k ≥ 1). It is clear that the sample paths of a Poisson process are completely characterised by the arrival times of the elementary events that comprise the process. Accordingly, set t0 = 0 and, for each n ≥ 1, let tn denote the time of the nth arrival. The interarrival time τn = tn − tn−1 then denotes the time between the (n − 1)st and nth arrivals. The Poisson character of the process immediately implies that the interarrival times { τn , n ≥ 1 } form an independent, identically distributed sequence of random variables. The marginal distribution and density functions of the random variables τn are now readily determined: 0 if s < 0, Fτn (s) = P{τn ≤ s} = 1 − P{no arrival in duration s} = if s ≥ 0, 1 − e−λs 0 if s < 0, dFτn (s) pτn (s) = = if s ≥ 0. λe−λs ds It follows that the interarrival times τn are exponentially distributed with pa- rameter λ. In particular, Poisson interarrival times exhibit the memoryless property. The fundamental link between the Poisson and exponential distri- butions is manifested here: a Poisson process with rate λ has independent interarrival times sharing a common exponential distribution with parame- ter λ. Markov Chains Consider a sequence of random variables { Nk , k ≥ 0 } where each random variable takes on values only in the discrete set of points {0, 1, 2, . . . }. The random sequence {Nk } forms a Markov chain if, for every k, and every choice of nonnegative integers m0 , m1 , . . . , mk−1 , mk = m and mk+1 = n, P{Nk+1 = n | Nk = m, Nk−1 = mk−1 , . . . , N0 = m0 } = P{Nk+1 = n | Nk = m} = Pmn . In words: in a Markov chain, given a sequence of outcomes of random trials, the outcome of the next trial depends solely on the outcome of the immedi- ately preceding trial. Transition Probabilities. The set of values {0, 1, 2, . . . } that can be taken by the random variables Nk is called the set of possible states of the chain; 20