DOC PREVIEW
Berkeley ELENG 228A - Loss networks and Markov random fields

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Loss networks and Markov random fieldsStan Zachary Ilze ZiedinsDept. of Actuarial Mathematics Dept. of Statisticsand Statistics University of AucklandHeriot-Watt University Private Bag 92019Edinburgh EH14 4AS AucklandScotland, U.K. New ZealandAbstractThis paper examines the connection between loss networks without controls andMarkov random field theory. The approach taken yields insight into the structureand computation of network equilibrium distributions, and into the nature of spatialdependence in networks. In addition, it provides further insight into some commonlyused approximations, enables the development of more refined approximations, andpermits the derivation of some asymptotically exact results.1 IntroductionLoss networks have been widely studied, primarily as models for telecommunication sys-tems, although other applications have also been discussed. One of the major aims inmodelling such networks is to obtain good estimates of performance measures such asblocking probabilities. In this paper we consider simple loss networks without controls(for example on routing or admissions) and examine the connection between such net-works and Markov random field theory. The benefits of this approach are several. It givesinsight into the structure and computation of network equilibrium distributions, and intothe nature of spatial dependence in networks. In addition, it provides further insight intothe reduced load approximation (see below) commonly employed when exact computationof equilibrium distributions is impossible, and enables the development of more refinedapproximations. Finally, for some highly symmetric networks this approach yields asymp-totically exact results. For excellent introductions to loss networks see Kelly [12], and alsoRoss [14].A general loss network without controls can be described as follows. Denote by J thefinite collection of resources in the network and let C = {Cj,j∈ J} where Cjis thecapacity of resource j.LetR denote the finite set of possible call (or customer) typesin the network. Calls of each type r ∈ R arrive as a Poisson process with rate νrandhave identically distributed holding (or service) times, which we assume, without loss ofgenerality, to have mean 1 (see Burman et al. [3]). Each call of type r requires (integer)capacity Ajrfrom resource j ∈ J for the duration of its holding time. If one or more ofthese resources does not have sufficient free capacity to carry the call then it is blocked andconsidered lost. Otherwise the call is accepted. All arrival processes and holding timesare independent of one another. The traditional example is that of a circuit-switchednetwork, in which resources correspond to links in the network, each of a given capacity.In this case a call of any type is assumed to require a single unit of capacity from eachlink on the route over which it travels, so that call types may effectively be identified withroutes. However, there are many other examples and applications, such as cellular radio1networks and modern ATM networks. In the latter, capacity (or bandwidth) requirementsfor different call types (for example, voice and video) may vary very greatly, even over thesame routes in the network.Let nrbe the number of calls of type r in progress, and for any R⊆ R,letnR=(nr,r∈ R). Let SR= {nR:r∈RAjrnr≤ Cjfor all j ∈ J}. Then, under theconditions outlined above, it is now very well-known that the stationary distribution π ofnRis given byπ(nR)=G(C)−1r∈Rνnrrnr!, nR∈ SR, (1)where G(C)−1is a normalising constant; that is, π has a truncated product form. Unfor-tunately, for networks of realistic size, this expression is of little help in the calculation of,for example, the stationary blocking probability that a call of any given type is rejected.This is due to the difficulties of calculating the normalising constant. However, a numberof relatively fast and efficient methods have been suggested which do permit exact calcula-tions to be made in certain circumstances. Dziong and Roberts [7] (see also Zachary [19])give an exact recurrence based on consideration of the reduced state space which recordsonly the total occupancy of each resource. Refinements of Buzen’s convolution algorithm[4] for closed queueing networks have also been applied to loss networks. Of particu-lar interest are Choudhury et al. [5], who invert the generating function of the partitionfunction, and Bean and Stewart [1], who apply refined dimension reduction techniques toBuzen’s algorithm, and thus obtain considerable efficiency gains.Due to the difficulties of calculating the normalising constant, various approximationsto quantities of interest, such as blocking probabilities, have been developed. In particularthe (multiservice) reduced load approximation (Dziong and Roberts [7], see also Ross [14])may be described briefly as follows. For each j ∈ J,letLjrbe the (stationary) probabilitythat resource j has fewer than the Ajrunits of free capacity needed to accommodate acall of type r at that resource (with Ljr= 0 whenever Ajr=0). EachLjris calculated byreference to an easily analysed model of resource j in isolation. In this, calls of each type rare assumed to arrive at resource j as a Poisson process with rate νr k =j(1 − Lkr). Thecapacity of the resource and call holding times are unchanged. The assumption underlyingthis approximation is that resources block “as if” independently of each other. We are thusled to a set of fixed point equations in the probabilities Ljr, for which the existence—butnot always the uniqueness, see Chung and Ross [6]—of a solution is guaranteed. In thesame spirit, the probability Brthat a call of type r is blocked is then taken to be given by1 − Br=j∈J(1 − Ljr). (2)The reduced load approximation is of course exact in the case of a single-resource network.The well-known Erlang fixed point approximation (EFPA) differs from the multiservicereduced load approximation by assuming a simplified model of each resource j in which,in particular,1 − Ljr=(1− Lj)Ajr(3)where Ljis the probability that the resource j has no free capacity. The approximation (3)reduces the number of variables in the fixed point equations referred to above. However,these may again have multiple solutions, see, for example, Ziedins and Kelly [20]. Blockingprobabilities are calculated using (2) as before. In general the EFPA is not exact for asingle-resource


View Full Document

Berkeley ELENG 228A - Loss networks and Markov random fields

Documents in this Course
FAST TCP

FAST TCP

57 pages

Load more
Download Loss networks and Markov random fields
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Loss networks and Markov random fields and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Loss networks and Markov random fields 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?