Главная > Разное > Теоретические основы проектирования компьютерных сетей
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.2.3 Модель сети с ограниченной буферной памятью в узлах коммутации пакетов

Описанная в разделе 6.2.1 модель сети пакетной коммутации хотя и позволяет получать простые аналитические выражения для характеристик сети, но требует наличия ряда предположений и ограничений, таких как неограниченная буферная память в УК, отсутствие квитирования и повторной передачи не принятых в УК пакетов и т. д.

Рассмотрим подход, позволяющий более полно учитывать характерные особенности реальных сетей передачи данных и ослабить ряд указанных ограничений [75].

Рассмотрим модель сети коммутации, включающую W узлов и заданную топологию каналов связи между ними. Узел состоит из процессора, обслуживающего выходящие из УК канала передачи данных, и равнодоступных буферов каждый объемом на пакет. Это позволяет рассматривать многоэтапный процесс буферизации в УК на модели простейшей схемы памяти - однородного равнодоступного пула буферов. В качестве примера влияния сквозного квитирования на характеристики сети рассмотрим модель сети при дейтаграмном способе доставки пакетов. При этом будет исследоваться случай сквозного квитирования. Копии пакетов, ожидающие подтверждения об успешной передаче по сети, находятся в УК-источнике. Занятость буферной памяти в момент прихода в УК пакета приводит к сбросу последнего на сетевом уровне и последующему повторению его передачи из УК-источника, в отличие от повторения между соседними УК. Память, занимаемая принятым в УК пакетом, освобождается после получения положительного уведомления АСК 0 безошибочной передаче от соседнего узла.

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

Уравнения баланса потоков на входе и выходе узлов описанной сети имеют вид

где - стационарная вероятность наличия свободного буфера в УК сети. Эта вероятность для УК с простейшей схемой однородного равнодоступного пула буфера может быть записана (см. раздел 6.4) в виде

где - число буферов в - нормализующая константа модели замкнутой сети МО, описывающей функционирование УК. Для произвольного УК сети справедливы следующие утверждения.

Утверждение - монотонно убывающая функция А.

Доказательство. В рассматриваемом случае нормализующая константа может быть представлена в виде (см. раздел 3.1)

Из последнего выражения легко определяется

где - маргинальное распределение длины очереди в центре «Источник» рассматриваемого УК; - средняя длина очереди пакетов в центре «Источник».

Дифференцируя и подставляя значение получаем

Утверждение 1 следует из справедливости неравенства

Утверждение 2. Функция является монотонно возрастающей.

Доказательство непосредственно следует из производной

и очевидного неравенства

Система нелинейных уравнений (6.11) может быть записана в векторной форме

где - вектор-столбцы:

Рассмотрим решение системы (6.14) методом простых итераций. Обозначим результат итерации при Итерационный процесс определяется зависимостью

Обозначим если для если для . Справедливо следующее утверждение.

Утверждение 3. Последовательность сходится к единственному положительному решению системы (6.14). Доказательство. Рассмотрим норму

Воспользуемся достаточными условиями сходимости простых итераций, определяемыми в виде Производная

Отсюда

Очевидно, что имеет положительные компоненты для тех , у которых . Пусть тогда из (6.14)

В силу предположения индукции и утверждений 1 и что определяет неубывающую последовательность Отсюда и из предположения о неразложимости матрицы маршрутов что определяет

Среднее время задержки пакетов в рассматриваемой сети

где - среднее время записи пакета в память УК; - частота посещения - среднее время пребывания пакета в УК, определяемое интервалом от момента окончания приема пакета в буферную память УК до передачи пакета в выходящем из узла направлении: - среднее время цикла (см. раздел 6.4).

Рассмотрим другую модель сети пакетной коммутации, в которой квитирование пакетов осуществляется только между соседними УК. Неудачно переданный пакет повторяется из УК отправителя. Это требует сохранения копии пакета в буферной памяти передающего УК до момента получения от соседнего УК положительной квитанции АСК о приеме пакета. Отсутствие АСК в течение time-out классифицируется как потеря пакета, и передающий УК повторяет пакет по тому же самому или новому маршруту.

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

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

Как и раньше, предполагается, что потоки поступающие в УК, являются пуассоновскими.

Уравнение баланса потоков для узлов рассматриваемой сети имеет вид

где - стационарная вероятность наличия свободного буфера в УК сети.

Система (6.16) может быть записана в виде

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

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

При этом число повторений передачи по каналам сети можно считать распределенным по геометрическому закону со средним . Последнее эквивалентно увеличению относительной частоты посещения центров обслуживания модели замкнутой сети МО при (см. раздел 6.4). Таким образом, взаимовлияние УК при межузловом квитировании проявляется в функциональной зависимости

Указанная сеть исследовалась с помощью эквивалентной системы нелинейных уравнений относительно вероятностей занятости буферной памяти УК

Система (6.18) решается с помощью метода Ньютона, сходимость которого существенно зависит от выбора начального приближения. Среднее время задержки пакетов для рассмотренной сети определяется выражением (6.15), где

<< Предыдущий параграф Следующий параграф >>
Оглавление