Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/~ansobol/otarie/slides/vvedenskaya.pdf Дата изменения: Fri May 21 21:15:07 2010 Дата индексирования: Sat Jun 26 04:48:57 2010 Кодировка: Поисковые слова: р п р п р п р п р р п п р п п р р п р п п р п

Dynamic Routing; Configuration of Overloaded Interacting Servers N.D. Vvedenskaya, Moscow, I ITP We consider a symmetrical network with k servers and l Poisson input flows. The proto col uses dynamic routing: each flow is assigned to a subgroup of m servers, up on its arrival a message is directed to the least busy of these servers. Under the condition that at least m servers are overloaded the numb er of overloaded servers dep ends on the rate of input flows. For a circle of interacting servers this effect is describ ed in: N.D. Vvedenskaya, E.A. Pechersky, Circle of Interacting Servers: Sp ontanious Collective Fluctuations in case of large Fluctuation, Probl. Inform. Transmission, 2008, V. 44, No 4, P. 370-384.
1


Some history. Consider a system where the numb er of servers k . In case of dynamic routing where the shortest of m queues is selected the stationary distribution of queue lengths decreases sup erexp onentially:

Pr[q ueue leng th n] = For example, as m = 2 Pr[q ueue

nm -1 m-1

.

n2 -1 . leng th n] =

N.D. Vvedenskaya, R.L. Dobrushin, F.I. Karp elevich, A Queueing System with the Selection of the Shortest of Two Queues, Asymptotical Approach, Probl. Inform. Transmission, 1996, V. 32, No 1, 15-27. If k is finite the situation is quite different.
2


Consider a symmetrical system S = S (k, m) formed by k identical servers S = (s1, ..., sk ) k and l = m indep endent Poisson flows F = (fA1 , ..., fAl ), each of rate . Here Aj = (j1, ..., jm) are the numb ers of servers SAj = (sj1 , ..., sjm ) assigned to fAj . The servers have infinite buffers and op erate with equal rate 1. Up on its arrival with fAj a message is directed to a server from SAj that at the time of its arrival has the smallest workload.

3


The flows are describ ed by the sequences of indep endent pairs (n
(Aj )

, n

(Aj )

),

n = ..., -1, 0, 1, ...,

j = 1, ..., l,

(Aj ) n ­ the intervals b etween arrivals of two (A ) messages, Pr(n j > t) = e-t. (Aj ) n ­ the message lengths.

The distributions of n ( ) = E en
(Aj )

(Aj )

are identical,

< , < +, lim () = . +

All variables are iid.

4


The mean intensity of the sum of Poisson k (m) flows up on one server is = k . The system is in stationary state, (0) < 1, < = k l (0)
-1

.

If during some time p erio d the flow intensity is large the flow is said to b e overheated, if there is a lot of unserved messages in a buffer of a server the server is said to b e overloaded. Let w(t) = (w1(t), ..., wk (t) b e the load vector that indicates the load of buffers.

5


Virtual message arrive up on S at time moment t = 0 with flow fA1 , has zero length and is directed to the servers according to the dynamic routing proto col. The delay (waiting time) of virtual message is denoted by 1. The event {1 n} is denoted by 1(n) We are interested in probability of 1(n), that is exp onential: -1 ln Pr[1 nd]. n n lim Logarithm of needed probability can b e expressed via rate function


I=

0

sup {x(t) - [() - 1]}dt,
<+

For x(t) that is a trajectory of flow f we call x the flow sp eed.

6


One server. For "optimal"trajectory x(t) = a =const, limn -1 ln Pr [ > nd] = I d, n I = t sup<+ {a - [() - 1]} Optimization for a server of sp eed m gives I = m where m = [() - 1]. (() - 1)


2 1

2 > 1

7


System with k servers For any k, k 3 there exist (k), (k), 0 < (k) (k) < , that dep end on Aj distribution such that If < (k), then the event 1 is mainly defined by fA1 , only this flow is overheated limn -1 ln Pr [1(n)] = mmd, n where m is a p ositive ro ot to equation m = [() - 1]. If > (k), then all flows are overheated limn -1 ln Pr [1(n)] = kk d, n where k is a p ositive ro ot to equation
k k = m [() - 1].
8


The last statement is easy to explain formaly. Let mm = [() - 1], k kk = m [() - 1]. It easy to see that mm < kk if is sufficiently small, mm > kk if is sufficiently close to = k l (0) -1. (() - 1) 2 1


2 > 1

= [() - 1].

9


Consider an auxiliary system S (0) with similar k servers and l flows. The realization of flows in b oth systems are identical. At S (0) the routing is random: a message of flow fAj with given probability (j, r ) is directed to the server sr , sr SAj . The flows of S (0) up on the servers are indep endent and Poisson. Supp ose the flows F have the sp eeds aA1 , ..., aAl . We call these flows balanced with resp ect to servers S if for any j, r there exist such (j, r ) and such b > 0 that (j, r)aAj =
j l j =1 aAj

k

= b.

.

10


Now we compare the p erformance of systems S and system S (0). Let in b oth systems m , m m k server b e equally overloaded. In S 0 the flows up on m servers are balanced. For auxiliary system the difference |wi(t) - wj (t)| = o (t). It can b e shown that the comp onents of load vector in main system are even more concentrated in the neighb orho o d of bisectrix w1 = ... = wm than similar comp onents in the auxiliary system. Therefore the probability of events 1(n) in the systems are equal in case where k server are equally overloaded.

11


It can b e shown that if the event 1(n) takes place (and may b e some other servers are also overloaded) the probability of this event is not greater than the probability of similar event where several servers are equally overloaded and the overheated flows have equal sp eeds. Therefore it is sufficient to consider the equal overload of m , k m m servers caused by the equal overheat of several flows. The formulas for probability of 1(n) presented ab ove are the formulas for probability of equally overheated flows in auxiliary system

12


Comparison of large delay probability for different values of m brings the statement and formulas presented ab ove. Example The case of exp onentially distributed length, Pr[ x] = e-x:
(k) = (k - m) , (k) = k m -1

(k) = (k) as k increases.

13


Constant message length, circle system. Pr( = x) = . () = e , < 1. a) As 3 k 12 k = (k). For example k 0.311 as k = 3; k 0.667 as k = 5. b) As k > 12 : k 0.888; (k) 0.910 as k = 15

14