ГЛАВА 2
ПОСТАНОВКА ЗАДАЧИ ОРГАНИЗАЦИИ ДИНАМИЧЕСКОЙ СТРУКТУРЫ МОБИЛЬНОЙ СЕТИ БОЛЬШОЙ
РАЗМЕРНОСТИ
2.1. Метрики процесса передачи информации в мобильных компьютерных сетях
При решении задачи маршрутизации необходимо учитывать состояние каналов
передачи и время задержки в коммутационных узлах. Состояние канала
характеризуется несколькими параметрами, в первую очередь – полосой пропускания
канала, используемой алгоритмами маршрутизации для определения оптимального
пути к приемнику данных [31].
В качестве параметров могут быть использованы [16]:
Пропускная способность канала передачи данных (В – bandwidth), бит/сек.
Время задержки (D – delay), сек.
Загруженность канала (L – load), бит.
Надежность канала (R – reliability).
В большинстве случае используют составную метрику. В работе [31] представлены
уравнения для вычисления метрики:
Если больше нуля (0), то следует выполнить еще один шаг:
где – это константы.
Варьируя значения констант, можно давать различным переменным более высокий или
более низкий приоритет. По умолчанию , а . В этом случае .
Основываясь на приведенных выше метриках для каждого маршрута вычисляется
обобщенная метрика, по которой и определяется наилучший маршрут. При этом
используется формула:
где – константы;
– эффективная пропускная способность, которая определяется как произведение
полосы пропускания на загруженность канала;
– время задержки;
– надежность (процент информации, успешно переданной следующему узлу).
При выборе маршрута и анализе его эффективности в современных компьютерных
сетях используется концепция службы TоS (Type of Service), в связи с чем
определяется несколько типов служб в зависимости от параметра оптимизации
[46]:
TоS 0 – обычная служба, значение параметра назначается администратором;
TоS 2 – минимизация финансовой стоимости, назначается при известных стоимостных
параметрах сети;
TоS 4 – максимизация надежности, задается на основе истории неисправности;
TоS 8 – максимизация пропускной способности;
TоS 16 – минимизация задержки, мера времени пересылки, определяется
динамически.
Как правило, большинство стандартных протоколов маршрутизации минимизируют
задержку передачи информации. Для мобильных компьютерных сетей, в качестве
критерия оптимальности выбора маршрута, необходимо дополнительно рассматривать
время ремаршрутизации.
Для анализа процедуры ремаршрутизации будем использовать следующие параметры
[51]:
r – отношение среднего числа запросов на соединение к числу перемещения между
доменами маршрутизации. Назовем его отношение «активность - мобильность».
Тu – время обновления, отнесенное к одному перемещению между смежными доменами
маршрутизации.
Тs – время поиска нового месторасположения.
Т (x,y) – время посылки сообщения от одного домена x к домену y.
Тср – среднее время запроса/ответа между текущим доменом маршрутизации и
исходным доменом маршрутизации.
k – количество пройденных точек ветвления для вызывающей абонентской системы
необходимое для достижения искомой абонентской системы.
ТF – время установки точек ветвления между двумя серверами расположения. Это
время включает время пересылки сообщения между двумя серверами расположения.
Время передачи указателя перехода также включает время сообщения между двумя
серверами расположения.
a – относительная стоимость пройденных точек ветвления.
Метрикой производительности сети является общее время передачи (Тр), где:
Тр=kuЧТu +ksЧТs.
Коэффициенты ku и ks выбираются с учетом следующих условий:
Для абонентской системы с малым значением r (перемещения более частые чем
соединения) время обновления является преобладающим фактором в общем времени
передачи. В этом случае коэффициент поиска следует уменьшить, так как r зависит
от размера домена маршрутизации.
Для абонентской системы с высоким значением r (перемещения менее частые, чем
соединения) время поиска является преобладающим фактором в общем времени. В
этом случае коэффициент обновления следует уменьшить.
В работе [52] коэффициенты ku и ks выбираются равными: ku = 1/r и ks = r. Таким
образом, метрика производительности сети равняется:
Тр=1/r ЧТu + rЧТs.
Для мобильных компьютерных сетей в качестве критерия оптимальности
целесообразно рассматривать минимальное время ремаршрутизации, обеспечивающее
безразрывную передачу информации при перемещении абонентской системы [49]. В
этом случае длина пути переходит в разряд ограничений. Время ремаршрутизации
зависит от количества и времени возвратов по виртуальному дереву в результате
перемещения абонентской системы. Узел дерева, в котором осуществляется
изменение маршрута будем называть точкой ветвления маршрута. Время
ремаршрутизации Тс между двумя смежными листьями равно:
Тс = Тз + Тр,
где Тз - задержка в передаче по звену дерева, т.е. между соседними вершинами;
Тр – время коммутации в точке ветвления.
При наличии некоторого числа k промежуточных звеньев время маршрутизации
равно:
Тс = ТзЧ k + Тр.
При расположении точки ветвления на i –ом уровне Тi равно:
Тi = ТзЧ i + Тр.
При последовательном обходе всех листьев каждая точка ветвления обходится m-1,
где m - число нисходящих ветвей дерева. В этом случае суммарное время
ремаршрутизации при обходе всех листьев определяется величиной:
где L – число уровней дерева;
mi – количество нисходящих ветвей вершины i-го уровня.
На основании анализа полученного выражения можно сделать вывод, что с
сокращением числа уровней дерева сокращается время ремаршрутизации. Таким
образом, задачу сокращения времени ремаршрутизации можно свести к задаче
построения дерева с минимальным числом уровней. Минимальное число уровней
равное двум достигается при организации внутри
- Київ+380960830922