ЭКОНОМИЧЕСКИЕ АЛГОРИТМЫ УПРАВЛЕНИЯ ПОТОКАМИ В СЕТЯХ С ВИРТУАЛЬНЫМИ КАНАЛАМИ

Оглавление

1. Введение
2. Экономико-математическая модель компьютерной сети с виртуальными каналами
3. Спрос виртуального канала на коммуникационные ресурсы
4. Узлы компьютерной сети
5. Справедливость и оптимальность экономических алгоритмов управления потоками
6. Заключение
7. Литература

В работе представлен нестандартный подход, основанный на применении экономико-математических методов к распределению коммуникационных ресурсов компьютерной сети. Предлагаемые алгоритмы управления потоками в сетях с виртуальными каналами являются децентрализованными. Доказывается, что представленные экономические алгоритмы обеспечивают парето-оптимальность распределения сетевых ресурсов.

Рассмотрим компьютерную сеть как экономическую систему. В такой системе есть два типа экономических агентов: виртуальные каналы (virtual circuits) и узлы сети.

Каждый виртуальный канал характеризуется маршрутом в сети (совокупностью реальных каналов связи, составляющих данный виртуальный канал), требованиями пользователя к задержке (delay) и пропускной способности (throughput) виртуального соединения и величиной оставшихся виртуальных денег. Виртуальный канал наделяется некоторой суммой (виртуальных) денег, которые расходуются на приобретение коммуникационных ресурсов, т.е. пропускной способности реальных каналов связи.

Узел сети, как экономический агент, устанавливает цены на коммуникационные ресурсы. Цель узла - вычислить равновесную цену, при которой спрос на ресурсы равен их предложению.

Каждый новый виртуальный канал, зная свою цель относительно пропускной способности и задержки, использует ценовую информацию для определения возможности достижения этой цели. Если такая возможность отсутствует, то можно либо отложить формирование виртуального канала до тех пор, пока цены не понизятся, либо изменить цель. Таким образом, "экономика компьютерной сети" выполняет управление доступом (admission control).

Цены являются показателем редкости ресурсов. Поэтому использование рыночных механизмов в компьютерных сетях может способствовать повышению эффективности использования их ресурсов.

Моделью компьютерной сети может служить граф G=<V,E>, где V={1,2,...,K} - совокупность узлов, E={1,2,...,M} - совокупность ребер графа.

Каждое ребро i из E характеризуется двумя величинами:

• теоретическая пиковая пропускная способность C_i (измеряется в количестве данных, переданных в единицу времени);
• реальная пропускная способность S_i, причем S_i<C_i.

Величина S_i является верхней границей степени использования канала связи i . Как будет видно, она введена для того, чтобы ограничить задержку. При этом степень общности не уменьшается, т.к. S_i можно взять сколь угодно близким к C_i.

Цель управления потоками заключается в распределении пропускной способности между виртуальными каналами.

Пусть A={1,2,...,N} обозначает совокупность виртуальных каналов. Предположим, что A не меняется. Каждый виртуальный канал a из A определяется совокупностью реальных каналов, входящих в его состав, т.е. совокупностью ребер графа G:

L_a=i₁,i₂,...,i_m(a) , (1)

где i принадлежит E.

Виртуальные каналы, играя роль покупателей коммуникационных ресурсов, участвуют в их распределении. Часть ресурсов, доставшихся в результате распределения данному виртуальному каналу, описывается вектором X=(x₁,x₂,...,x_M), где все x_i>=0.

У каждого реального канала i из E есть свой продавец (узел сети), который взимает плату с виртуальных каналов за использование i.

Цены задаются вектором P=(p₁,p₂,...,p_M), где все p_i>=e>0. Предположение, что p_i>0 используется в пятой главе. Оно не уменьшает общность рассмотрения, ибо p_i может быть сколь угодно близким к нулю.

Для каждого виртуального канала a введем отношение предпочтения &_a на множестве распределений. Пусть вектор X предпочтительнее для a , чем Y, обозначим это следующим образом: X&_aY. Если X&_aY и Y&_aX, то для виртуального канала a вектора X и Y равноценны. Если X&_aY и X и Y не равноценны для a, тогда X строго предпочтительнее Y. Обозначим это X&^s_aY (s - от англ. strictly).

Пусть T(X) пропускная способность виртуального канала a, получившего в результате распределения ресурсы X, D(X) - средняя задержка a. Виртуальный канал a пытается максимизировать T(X) до тех пор, пока не достигнет цель g_a, заданную пользователем виртуального канала. Затем, a стремится минимизировать D(X).

Отношение предпочтения &_a определяется следующим образом:

1. если T(X)<=g_a, T(Y)<=g_a и T(Y)>=T(X), то Y&_aX;
2. если T(X)<g_a и T(Y)>=g_a, то Y&_aX;
3. если T(X)>=g_a, T(Y)>=g_a и D(X)>=D(Y), то Y&_aX.

Очевидно, что введенное таким образом отношение не охватывает все случаи, однако, является достаточным для наших целей.

Если приложение является критическим с точки зрения пропускной способности (например, передача файлов), g_a должно быть достаточно большим. Если приложение является критическим с точки зрения задержки (как, например, в случае, когда виртуальный канал соединяет рабочую станцию с базой данных), g_a - невелико (например, достаточно взять средний размер пакета в транзакции, деленный на "время размышления" (think time) пользователя).

Поскольку пропускная способность виртуального канала определяется скоростью самого медленного реального канала, входящего в его состав, то

T(X)=min{x_i| i принадлежит L_a} (2)

Рассматривая реальный канал связи i как систему массового обслуживания типа M/M/1, среднюю задержку на канале i в наихудшем случае (т.е. рассматривается верхняя граница для средней задержки) можно определить следующим образом [1]:

(3)

Средняя задержка на всем виртуальном канале:

(4)

Каждый виртуальный канал a наделяется некоторым бюджетом W_a>0, который соответствует приоритетности a . Бюджетную систему канала a можно записать в виде:

B_a(P)={X | P*X<=W_a} (5)

Спрос со стороны a на коммуникационные ресурсы:

Ф _a(P)={X | X принадлежит B_a(P), X&_aY, для всех Y из B_a(P)} (6)

Затраты на передачу единицы данных по реальному каналу i равны p_i . Следовательно, затраты на передачу единицы данных по всему виртуальному каналу a:

(7)

Поскольку виртуальный канал a стремится передавать данные со скоростью g_a , общие затраты составят: g_a*Q_a, причем должно выполняться условие: Q_a*g_a<=W_a.

Справедлива следующая лемма.

Если Q_a*g_a>=W_a при ценах P , то

1. Ф_a(P) - не пусто.
2. Ф_a(P) содержит единственный элемент ф.
3. ф_i = W_a/Q_a, если i принадлежит L_a.
4. ф_i=0, если i не принадлежит L_a.

Доказательство.

Поскольку

,

то ф является допустимым вектором (с т.зр. бюджетного ограничения) и B_a(P) - не пусто. Так как отношение предпочтения есть частичный порядок, существует максимальный (наиболее предпочтительный) элемент. Это значит, что Ф_a(P) - не пусто.

Допустим, что существует другой вектор ф', такой что ф'&_aф. Тогда имеем:

1. Если ф_i'>=0, то для всех i, не принадлежащих L_a, ф_i'>=ф_i.
2. Если T(ф')>=T(ф), то для всех i из L_a ф_i'>=(W_a/Q_a).

Если ф' равноценно ф для a, то T(ф')=T(ф)=(W_a/Q_a) и ф'=ф .

Если ф'&_a^sф, то T(ф')>T(ф)=(W_a/Q_a). Это означает, что ф_i'>(W_a/Q_a) и, следовательно, ф'*P>W_a. Поэтому, ф' не является допустимым, т.е. не удовлетворяет бюджетному ограничению. Лемма доказана .

Если виртуальный канал может достичь цель g_a, он покупает по ценам P пропускную способность, величиной в g_a, на каждом реальном канале, входящем в L_a. Оставшаяся сумма W_a-(Q_a*g_a) используется для минимизации средней задержки.

Введем обозначения:

u_i=x_i-g_a, K_i=C_i-S_i, U=(u₁, u₂, ...,u_m(a)).

Задачу минимизации средней задержки можно сформулировать следующим образом:

(8)

при условиях:

1. u_i>=0,
2. P*U<=W_a-Q_a*g_a.

Нетрудно доказать, что область допустимых значений U выпукла и компактна, а функция F(U) непрерывна и строго выпукла на этой области. Это означает, что существует единственное решение задачи.

Формулируя и упрощая условие Куна-Таккера для поставленной выше задачи, получим для всех i:

u_i=0, или

1/(p_i*(K_i+u_i)²)=v, (9)

где v - множитель Лагранжа .

Первое из этих условий означает, что в оптимуме x_i>=g_a. Второе условие говорит, что предельная задержка, приходящаяся на единицу цены, должна быть одинаковой у всех реальных каналов i, для которых x_i>g_a.

Заметим, что из (9) вытекает следующее равенство (для всех u_i>0):

(10)

Каждый виртуальный канал использует для вычисления v алгоритм бинарного поиска, представленный ниже:

1. v^d=0 (нижняя граница для v).
2. v^u=max{1/(p_i*(K_i)²), i из L_a} (верхняя граница для v , следует из (9)).
3. v=(v^u-v^d)/2
4. Для всех i из L_a:

a)

b) если u_i<0, то u_i=0.

5. Если P*U=W_a-Q_a*g_a, то U - оптимально (решение найдено).
6. Если P*U>W_a-Q_a*g_a, то v^d=v.
7. Если P*U<W_a-Q_a*g_a, то v^u=v.
8. Возврат в пункт 3 (вычисление нового значения v).

После вычисления U спрос виртуального канала a на коммуникационные ресурсы определяется однозначно:

ф_i^a=g_a+u_i, если i из L_a.

ф_i^a=0, если i не принадлежит L_a.

Общий спрос на ресурс i при ценах P равен сумме индивидуальных спросов каждого из виртуальных каналов:

(11)

Разницу между спросом и предложением будем называть функцией излишка (или просто излишком) и обозначать Z(P). Ясно, что Z(P) - вектор, его i-я компонента z_i(P)=d_i(P)- S_i.

Если z_i(P*)=0 для всех i, то экономика находится в состоянии конкурентного равновесия при равновесных ценах P*. Обычно, равновесие определяется как состояние, в котором: 1) нет неиспользованных ресурсов, 2) спрос каждого экономического агента (виртуального канала) полностью удовлетворен.

К "экономике компьютерной сети" это определение непригодно, т.к. возможна ситуация, когда S_i принимает значения строго большие, чем d_i(P), как бы низко цены не падали. Этот случай проиллюстрирован рисунком (рис.1).

Есть два виртуальных канала, W₁=W₂=1, и S_i=1 ( для всех i). В силу симметрии и леммы 1, виртуальные каналы поделят третий реальный канал пополам, виртуальный канал 1 получит (1/2,0,1/2), виртуальный канал 2 получит (0,1/2,1/2). Излишек составит: Z(P)=(-1/2,-1/2, 0).

Для того чтобы исключить подобные ситуации, введем новое определение равновесия. "Экономика компьютерной сети" находится в состоянии равновесия при ценах P* , если для всех i либо z_i(P*)=0, либо z_i(P*)<=0 и p_i=e.

Как следует из данного определения, излишек (в состоянии равновесия) допускается при минимальных ценах.

Узлы сети, являясь продавцами, устанавливают цены на коммуникационные ресурсы на основе соотношения спроса и предложения. Этот процесс выполняется по следующему алгоритму.

Алгоритм ценообразования.

1. Установка начальных цен P.
2. Вычисление для всех a из A спроса ф^a(P) (выполнение этого шага описано в предыдущей главе).
3. Если для всех i из E либо ( z_i(P)=0), либо (z_i(P)<=0 и p_i=e), то равновесие достигнуто (итерационный процесс останавливается).
4. Иначе, для всех i из E

p_i=max [p_i+r*p_i*(z_i(P)/S_i), e] (12)

5. Переход в пункт 2.

Комментарий. В качестве начальных цен можно брать p_i=e для всех i. На втором шаге все виртуальные каналы вычисляют спрос при текущих ценах параллельно. Для выполнения этих вычислений каждому виртуальному каналу a требуется информация о ценах на реальные каналы, входящие в L_a. Параметр r из (12) отражает важность обновления цен. На четвертом шаге продавцу реального канала i необходимо знать идентификаторы всех виртуальных каналов, в состав которых входит данный реальный, и их спрос на i , для вычисления z_i(P).

Сформулируем четыре критерия справедливости распределения ресурсов между виртуальными каналами.

(F1) Распределение {X¹, X², ..., X^N} справедливо, если для всех a из A выполняется неравенство T(X^a)>0.

Этот критерий утверждает, что не должно быть виртуальных каналов, которым досталась бы в результате распределения нулевая пропускная способность.

Будем называть реальный канал i из L_a заторным каналом (от слова затор, узкое место) виртуального канала a, если T(X^a)=x_i^a. Таким образом, заторный канал определяет пропускную способность виртуального канала.

(F2) Пусть i является заторным каналом виртуального канала a. Распределение {X¹, X², ..., X^N} справедливо, если x_i^a>=x_i^b для всех b из A.

Это условие иногда называют максиминным, поскольку оно определяется исходя из максимизации минимума пропускной способности. Данный критерий предполагает, что все виртуальные каналы стремятся максимизировать пропускную способность, но не учитывают задержку.

(F3) Распределение {X¹, X², ..., X^N} справедливо, если для всех a из A X^a&_aY для всех Y из B_a(P).

Это условие построено на основе понятия устойчивости по Нэшу (из теории игр). В отличие от F1 и F2, критерий F3 учитывает и пропускную способность, и задержку (в силу того, что он основывается на отношении предпочтения).

Прежде чем сформулировать четвертый критерий, введем несколько вспомогательных понятий.

Назовем коалицией S некоторую подсистему A. Коалиция S может улучшить распределение {X¹, X², ..., X^N}, если найдет другое распределение {Y¹, Y², ..., Y^N} такое, что:

1. Y^a=X^a, где a не принадлежит S (формирование коалиции не влияет на тех, кто в нее не входит);
2. Y^a&_aX^a, для a из S ( для всех членов коалиции новое распределение не хуже старого);
3. найдется такое a из S, для которого Y^a&^s_aX^a (хотя бы для одного члена коалиции новое распределение строго лучше старого).

Теперь определим четвертый критерий.

(F4) Распределение {X¹, X², ..., X^N} справедливо, если нет таких коалиций, которые могли бы улучшить распределение.

Условие F4 эквивалентно определению оптимальности по Парето .

Очевидно, что справедливы утверждения:

• Если F2, то F1;
• Если F4, то F3.

Следующая лемма показывает, что "экономика компьютерной сети" распределяет ресурсы справедливо с точки зрения критериев F1 и F3.

Пусть P - вектор цен, ф^a(P) - вектор спроса виртуального канала a при ценах P, X - вектор ресурсов, такой что X не равен ф^a(P). Тогда:

1. ф ^a(P)*P=W_a
2. Если X&_aф^a(P), то X*P>= ф^a(P)*P
3. Если X&^s_a ф^a(P), то X*P> ф^a(P)*P

В случае, если T(ф^a(P))<g_a, утверждения леммы очевидны. Пусть T(ф^a(P))>=g_a.

(1) Если ф^a(P)*P<W_a, у виртуального канала образуется остаток q=W_a-ф^a(P)*P, где q>0. Приобретение q/p_i полосы пропускания реального канала связи i из L_a позволяет уменьшить задержку, ибо она (задержка) является монотонно убывающей функцией от x_i, при x_i>=g_a. Это значит, что ф^a(P) - неоптимальный вектор. Полученное противоречие доказывает первое утверждение леммы.

(2,3) Допустим противоположное: если X&_a ф^a(P), то X*P< ф^a(P)*P.

Обозначим:

1. u_i= ф_i^a-g_a, если i из L_a.

u_i= ф_i^a, если i не принадлежит L_a.

2. h_i=x_i-g_a, при i из L_a.

h_i=x_i, если i не принадлежит L_a.

3. U=(u_1,u₂,...,u_m(a)), H=(h_1,h₂,...,h_m(a)).

Тогда, P*H<=W_a-Q_a*g_a и H -допустимо.

Если X равноценно ф^a(P) для a, то F(U)=F(H). Но это противоречит строгой выпуклости функции F.

Если X&_a^s ф^a(P), то F(H)<F(U). Приходим к противоречию с оптимальностью U(определением ф^a(P)). Это завершает доказательство леммы .

Согласно определению, цены P и бюджет W_a принимают только положительные значения. На основании этого и в силу утверждения части 1 леммы 2 распределение ф^a(P) является справедливым с т.зр. критерия F1. Справедливость с т.зр. критерия F3 вытекает из утверждений пунктов 2 и 3 леммы 2.

Воспользуемся леммой 2 для доказательства следующей теоремы, устанавливающей парето-оптимальность распределения в "экономике компьютерной сети" .

Пусть P - вектор равновесных цен. Тогда распределение {ф¹(P), ф²(P),..., ф^N(P)} является парето-оптимальным и единственным.

Единственность. В главе 3 было показано, что система спроса Ф^a(P) содержит один единственный элемент (для всех a из A). Следовательно и вектор {ф¹(P), ф²(P),..., ф^N(P)} - единственный.

Парето-оптимальность. Допустим, что коалиция S={1,2,...,s} сформировала новое распределение ф', такое что:

1. фⁱ'(P)&_i фⁱ(P), для всех i из S.
2. ф^j'(P)&^s_iф^j(P), хотя бы для одного j из S.

Следовательно, согласно лемме 2:

1. фⁱ'(P)*P>= фⁱ(P)*P, для всех i из S.
2. ф^j'(P)*P> ф^j(P)*P, хотя бы для одного j из S.

Значит,

(13)

Это свидетельствует о том, что коалиция не может улучшить распределение. В силу формулировки F4, распределение {ф¹(P), ф²(P),..., ф^N(P)} - оптимально по Парето. Теорема доказана .

В работе представлен нетрадиционный подход к управлению потоками в сетях с виртуальными соединениями.

Построена экономико-математическая модель компьютерной сети, учитывающая наличие индивидуальных конфликтных целей: максимизация пропускной способности и минимизация задержки. Во многих работах по управлению потоками в сетях либо предполагается, что все виртуальные каналы имеют одинаковые цели относительно пропускной способности и задержки, либо делаются попытки оптимизировать общесистемные (общесетевые) характеристики.

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

Далее, очень затруднительно определить общесистемные характеристики, которые бы адекватно отображали гетерогенность пользователей и приложений, их разную приоритетность. По-видимому, чем более крупномасштабной является система, тем менее пригодны общесистемные характеристики для управления ею. Вполне возможно, что более подходящими в таких случаях будут децентрализованные алгоритмы (т.е. алгоритмы, которые не базируются на общесистемных характеристиках).

Предложенная в работе алгоритмическая структура является децентрализованной .

В любых задачах распределения ресурсов принципиально важен вопрос о справедливости (распределения). В этой связи предлагаются различные метрики справедливости, одной из которых является парето-оптимальность. В работе доказано, что предлагаемые экономические алгоритмы управления потоками в компьютерных сетях - парето-оптимальны.

1. D.F.Ferguson, C.Nicolaou and Y.Yemini. "An Economy for Flow Control in Computer Networks", Proc. of the INFOCOM, 1990. (ps-file)
2. J.Sairamesh. "Economic Paradigms for Information Networks and Systems", PhD thesis, Columbia University, New York, 1996.
3. Economic Models for Allocating Resources in Computer Systems. D.Ferguson, C.Nicolaou, J.Sairamesh and Y.Yemini. Market based Control of Distributed Systems, Ed. Scott Clearwater. World Scientific Press, 1996.

Web master