Обобщенная двухсерверная задача: различия между версиями

В обобщенной двухсерверной задаче имеются два сервера, один из которых перемещается в метрическом пространстве <math>\mathbb{X} \;</math>, а другой – в метрическом пространстве <math>\mathbb{Y} \;</math>. Они обслуживают запросы <math>r \in \mathbb{X} \times \mathbb{Y} \;</math>, которые поступают один за одним. Запрос r = (x, y) обслуживается посредством перемещения <math>\mathbb{X}</math>-сервера в точку x либо <math>\mathbb{Y}</math>-сервера в точку y. Решение, какой из двух серверов переместить при следующем запросе, не подлежит отменен и принимается в отсутствие каких-либо знаний о будущих запросах. Задача заключается в минимизации расстояния, пройденного обоими серверами.

'''Задача онлайн-маршрутизации'''

Обобщенная двухсерверная задача относится к классу задач маршрутизации под названием ''метрической системы сервисов'' [5, 10]. Подобную систему определяют метрическое пространство <math>\mathbb{M} \;</math> всех возможных конфигураций системы, начальная конфигурация <math>C_0 \;</math> и множество <math>\mathcal{R} \;</math> возможных запросов, в котором каждый запрос <math>r \in \mathcal{R} \;</math> является подмножеством <math>\mathbb{M} \;</math>. Пусть дана последовательность запросов <math>r_1, r_2, ..., r_n \;</math>. Допустимым решением является последовательность конфигураций <math>C_1, C_2, ..., C_n \;</math>, такая, что <math>C_i \in r_i \;</math> для всех <math>i \in \{ 1, ..., n \} \;</math>.

При моделировании обобщенной двухсерверной задачи метрической системой сервисов мы получаем <math>\mathbb{M} = \mathbb{X} \times \mathbb{Y}</math> и <math>\mathcal{R} = \{ \{ x \times \mathbb{Y} \} \cup \{ \mathbb{X} \times y \} | x \in \mathbb{X}, y \in \mathbb{Y} \}</math>. В классической двухсерверной задаче оба сервера перемещаются в одном и том же пространстве и получают одни и те же запросы, т.е. <math>\mathbb{M} = \mathbb{X} \times \mathbb{X}</math> и <math>\mathcal{R} = \{ \{ x \times \mathbb{X} \} \cup \{ \mathbb{X} \times x \} | x \in \mathbb{X} \}</math>.