Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Обозначим через f_k долю серверов, у которых ровно k заявок (заявка, которая находится на обслуживании в данный момент, тоже учитывается). Обозначим через u_k долю серверов, у которых заявок k или больше. Значения u_k можно легко получить через f_k и наоборот:

Понятно, что u₀ = 1.

Представим, что система находится в равновесии. Тогда у нас в среднем

серверов, на которых ровно k заданий. Все эти серверы обрабатывают задания со скоростью одно задание в единицу времени. Другими словами, количество серверов с k заявками или больше уменьшается на n(u_k − u_k+1) в единицу времени.

Теперь давайте посмотрим, на сколько количество серверов с k заявками или больше увеличивается в единицу времени. Чтобы увеличить число таких серверов, заявки должны поступать на серверы, у которых в данный момент k − 1 заявка. При методе выбора из двух вероятность того, что новое задание попадет на сервер с k или больше заявками, равна

потому что в этом случае оба случайно и независимо выбранных сервера должны иметь k или больше заявок, и для каждого из двух серверов эта вероятность и_k[26]. Значит, вероятность того, что новая заявка поступит на сервер, у которого ровно k − 1 заявка, равна

Поскольку заявок в единицу времени поступает λп, то получается, что число серверов с k или больше заявками в единицу времени в среднем увеличивается на

Так как система находится в равновесии, число серверов с k или больше заявками должно оставаться неизменным, то есть (П.9) равняется (П.11). Отсюда получаем уравнение баланса:

Результат, приведенный в работе{34}, говорит, что при определенных общепринятых предположениях о законе поступления заданий и времени их выполнения, в пределе для бесконечного количества серверов, уравнение (П.12) действительно описывает равновесное состояние системы. Это достаточно сложный технический результат. Нетрудно проверить или даже догадаться, что решение уравнения (П.12) задается формулами:

Это так называемый двойной экспоненциальный закон. Двойка в формуле, та самая двойка – вторая степень – из выражения (П.10). Точно так же мы могли бы выбирать не из двух, а из r серверов и получили бы

Интересно заметить, что при тех же предположениях, но случайном выборе одного сервера, изменятся выражения (П.10) и, соответственно, (П.11). Действительно, на этот раз заявка выбирает только один сервер и вероятность попасть на сервер с k или больше заявками равна просто и_k. Тогда вместо (П.12) получаем классическое уравнение баланса:

решение которого задается известной формулой Эрланга:

Очевидно, что и_k в формуле (П.13) убывает гораздо быстрее.

Именно эти формулы мы использовали в табл. 5.1. В нашем случае λ = 0,9, и в таблице мы привели значения f_k. В первой колонке – значения k, во второй – значения f_k, подсчитанные по формуле (П.14), в третьей – значения f_k, подсчитанные по формуле (П.13).

Назад к Главе 5

Приложения к главе 6

1. Схема Диффи – Хеллмана

Для начала введем обозначения. Пусть р – заданное простое число, g – заданное натуральное число, g < p. На самом деле g это так называемый первообразный корень числа р. Об этом мы расскажем ниже, в приложении 2 и приложении 3 к главе 6. Цель данного раздела – доказать, что в схеме Диффи – Хеллмана Алиса и Боб действительно получают один и тот же ключ.

Для любых натуральных чисел n и р мы воспользуемся стандартным обозначением для остатка от деления n на р:

n(modp) = [остаток от деленияnнаp].

(Читается «n по модулю p».)

Итак, Алиса задумала число х, а Боб число у. Схема Диффи – Хеллмана состоит из двух шагов.

Шаг 1. Алиса передает Бобу

a = (g^x) (modp).

Боб передает Алисе

b = (g^y) (modp).

Шаг 2. Алиса вычисляет ключ

K_A = (b^x) (modp).

Боб вычисляет ключ

K_B = (a^y) (modp).

Утверждение.Боб и Алиса получили один и тот же ключ K = K_A = K_B.

Доказательство. Нам нужно доказать, что K_A = K_B. Поскольку а и b – это остатки от деления на р, то существуют такие целые числа k и l, при которых

a =g^x −kp, b =g^y −lp.

Подставив эти выражения в формулы для ключей, получаем:

K_A = (g^y −lp)^x(modp),

K_B = (g^x −kp)^y(modp).

Заметим, что в выражении для K_A можно расписать (g^y − lp)^x следующим образом:

где А – это целое число, то есть рА делится на р. Таким образом получаем

K_A = ((g^y −lp)^x) (modp) = ((g^y)^x +pA) (modp) = (g^y)^x(modp).

Совершенно аналогично для какого-то целого числа B получаем

K_B = ((g^x −kp)^y) (modp) = ((g^x)^y +pB) (modp) = (g^x)^y(modp).

Результат теперь очевиден, поскольку

(g^y)^x =g^yx =g^xy = (g^x)^y.

2. Дискретное логарифмирование

Вспомним, что логарифм числа у по основанию g – это такое число х, для которого выполняется

g^x =y.