Алгоритмы наилучших ответов для эгоистичной маршрутизации: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) (→Модель) |
||
| Строка 6: | Строка 6: | ||
== Модель == | == Модель == | ||
''Игра о загруженности сети'' представляет собой кортеж <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math>, где N = {1, ..., n} – множество пользователей, где пользователь <math>i \;</math> контролирует <math>w_i \;</math> единиц спроса на трафик. В ''невзвешенных'' играх о загруженности <math>w_i = 1 \;</math> для i = 1, ..., n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а <math>d_e \;</math> – функция задержки, ассоциированная с ребром <math>e \in E \;</math>. Предполагается, что <math>d_e \;</math> являются неотрицательными и неубывающими функциями от загрузок ребра. Ребра называются ''идентичными'', если <math>d_e (x) = x \forall e \in E | ''Игра о загруженности сети'' представляет собой кортеж <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math>, где N = {1, ..., n} – множество пользователей, где пользователь <math>i \;</math> контролирует <math>w_i \;</math> единиц спроса на трафик. В ''невзвешенных'' играх о загруженности <math>w_i = 1 \;</math> для i = 1, ..., n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а <math>d_e \;</math> – функция задержки, ассоциированная с ребром <math>e \in E \;</math>. Предполагается, что <math>d_e \;</math> являются неотрицательными и неубывающими функциями от загрузок ребра. Ребра называются ''идентичными'', если <math>d_e (x) = x \; \forall e \in E</math>. Далее модель ограничивается играми о загруженности сети одного товара, в которых G имеет единственный источник s и приемник t, а множество пользовательских стратегий представляет собой множество путей s-t, обозначаемое как P. Без потери общности можно предположить, что граф G является связным и что каждая вершина G лежит на ориентированном пути s-t. | ||
Вектор P = ( | Вектор <math>P = (p_1, ..., p_n \;</math>), содержащий путь <math>p_i \;</math> модели s-t для каждого пользователя i, представляет собой ''профиль чистой стратегии''. Пусть <math>l_e(P) = \sum_{i: e \in p_i} w_i \;</math> обозначает загрузку ребра e в P. Определим стоимость <math>\lambda^i_p(P) \;</math> для пользователя i, направляющего свой спрос по пути p в профиле P, равной Х'р(Р) = X de(le(P))+ | ||
| Строка 18: | Строка 18: | ||
Наилучший ответ | '''Наилучший ответ''' | ||
Пусть pi – путь пользователя i, а Pi = (pi, ..., : : pi) – профиль чистых стратегий для пользователей 1, ..., : : i. Тогда наилучшим ответом пользователя i + 1 будет являться путь pi+1, такой, что pi+1 = | Пусть pi – путь пользователя i, а Pi = (pi, ..., : : pi) – профиль чистых стратегий для пользователей 1, ..., : : i. Тогда наилучшим ответом пользователя i + 1 будет являться путь pi+1, такой, что pi+1 = | ||