Определение порядка выдачи пакетов из матрицы регистров
Важнейшей составляющей процесса коммутации пакетов является их диспетчеризация, которая включает анализ способа размещения множества пакетов в МР и определение порядка выдачи пакетов из строк матрицы (этап 3 ПКП- метода).
Целью диспетчеризации является выбор подмножеств пакетов для выдачи в каждом такте работы КУ таким образом, чтобы сократить среднее время передачи одного пакета.Формализуем определение порядка выдачи пакетов из матрицы регистров.
Обозначим через Fkмножество пакетов, находящихся в матрице Bна k-м такте ретрансляции, k = 0,1,2,.... На множествеопределим функцию Sk, такую, что
, если регистр Bjсодержит некоторый пакет cqв k-м такте
ретрансляции,если регистр Bjсвободен. Таким образом:
36
На рис. 2.2 дана графическая иллюстрация определения функции Sk. Здесь квадратами показаны отдельные регистры (регистровые ячейки) МР, а вложенные
Рисунок 2.2. Определение функции Skдля заданного распределения пакетов множества Fkв матрице регистров
На множестве пакетов Fkопределим отношение совместности
такое, что
37
Еслито пакеты cqи crбудем считать совместными (такие пакеты
можно выдать из матрицы регистров одновременно, поскольку они находятся в разных строках).
Через отношение αkможно определить также отношение несовместности
Введем в рассмотрение граф совместности. Вершины этого
графа соответствуют пакетам множества Fk, а ребра - отображают их совместность. Взвесим вершины графа Γ kнеотрицательными целыми числамиВес
τqвершины cqбудем определять временем, которое пакет cqпровел в матрице регистров, выраженным в числе тактов работы КУ. Сразу после записи пакета cq в МР полагаем τ = 0.
q
На рис. 2.3 в качестве примера показан взвешенный граф совместности Γk для случая, представленного на рис. 2.2 (значения весов выбраны условно и указаны внутри вершин).
Выделим в графе Γ kкликутакую, что:
Если клик, отвечающих условию (2.2) в графе Γkнесколько, то выберем любую из них равновероятным способом. По определению носительклики
будет включать только совместные вершины и будет максимальным по включению. Таким образом, пакеты, соответствующие вершинам
будут допускать парал
лельную выдачу на выходы КУ, а их количество будет максимально возможным для данного распределения пакетов в МР.
Учет весов вершин при выделении клики Γkпозволяет реализовать относительный приоритет при выборе пакетов для выдачи, ограничивая время пребывания пакетов в матрице регистров и позволяя реализовать диспетчеризацию пакетов с учетом времени их обработки.
Рисунок 2.3. Взвешенный граф совместности Γkдля случая рис. 2.2
Для графа Γ k, изображенного на рис. 2.3, выделяется клика Γkс носителем (пунктирная линия на рис. 2.3). Для этой клики
Сумма весов остальных трех клик, имеющихся в данном графе, равна
1, 1 и 0.
Учитывая введенное формализованное представление, один такт (цикл) ретрансляции пакетов при использовании ПКП-метода можно описать приведенным ниже псевдокодом. Далее для удобства через clи B(μ(cl)) условимся обозначать соответственно пакет, находящийся в голове очереди Ql, и регистр матрицы B, выбранный для записи этого пакета согласно реализуемому алгоритму маршрутизации.
НАЧАЛО ПРОЦЕДУРЫ «Цикл ретрансляции пакетов»
ПРИНЯТЬ k = 0
ВЫПОЛНЯТЬ ПОКА хотя бы одна очередь Q1не пуста
СЧИТАТЬ пакеты из не пустых очередей [Ql}
ОПРЕДЕЛИТЬ множество регистров {b (μ( cl
ПЕРЕПИСАТЬ в матрицу Bвсе пакеты {cr}, для которых
КОНЕЦ ВЫПОЛНЯТЬ ПОКА
КОНЕЦ ПРОЦЕДУРЫ «Цикл ретрансляции пакетов»
Рассматривая приведенный выше псевдокод с привязкой к структурной модели КУ (см. рис. 2.1), уточним функции элементов данной модели. Передача в МР считанных из очередей пакетовобеспечивается коммутирующими элементами Rx, R2,..., Rn. Проверка условия /
и блокировка передачи
пакетов в МР (HOL blocking) осуществляется коммутирующими элементами Kx,K2,...,Knи клапанами Gx,G2,...,Gn. Формирование клики Γ'обеспечивается за счет матричной организации КУ, при которой совместные пакеты автоматически попадают в разные строки МР, а учет весов вершин с целью выбора множества Fс максимальным суммарным весом вершин реализуется правилами φx,φ2,...,φn, определяющими работу коммутирующих элементов Lx,L2,.,Ln.
2.4.
Еще по теме Определение порядка выдачи пакетов из матрицы регистров:
- Оценка эффективности использования матрицы регистров коммутационного устройства
- 3.7. Оценка средней загрузки матрицы регистров
- Общие особенности разработанного метода коммутации пакетов
- 4. Материальная ответственность в административном порядке и ее субъекты.
- Структурная модель устройства коммутации с параллельноконвейерной диспетчеризацией пакетов
- Тема: РАССМОТРЕНИЕ ДЕЛ В ПОРЯДКЕ УПРОЩЕННОГО ПРОИЗВОДСТВА. ПРИКАЗНОЕ ПРОИЗВОДСТВО В АРБИТРАЖНОМ ПРОЦЕССЕ
- МЕТОД И АЛГОРИТМ КОММУТАЦИИ С ПАРАЛЛЕЛЬНОКОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ. СТРУКТУРНАЯ МОДЕЛЬ КОММУТАЦИОННОГО УСТРОЙСТВА
- Оценка быстродействия коммутационного устройства при использовании параллельно-конвейерной диспетчеризации пакетов
- Алгоритм коммутации с параллельно-конвейерной диспетчеризацией пакетов
- ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК КОММУТАЦИОННОГО УСТРОЙСТВА С ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ
- Тема: ПРОИЗВОДСТВО ПО ПЕРЕСМОТРУ СУДЕБНЫХ АКТОВ В ПОРЯДКЕ НАДЗОРА. ПРОИЗВОДСТВО ПО ПЕРЕСМОТРУ СУДЕБНЫХ АКТОВ ПО НОВЫМ И ВНОВЬ ОТКРЫВШИМСЯ ОБСТОЯТЕЛЬСТВАМ
- Структура и формат передаваемых пакетов
- Оценка полного времени прохождения пакетов через коммутационное устройство
- МЕТОДЫ И УСТРОЙСТВА КОММУТАЦИИ ПАКЕТОВ В МАТРИЧНЫХ МУЛЬТИПРОЦЕССОРАХ
- Определение текучести
- Определение насыпной плотности
- СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ КОММУТАЦИОННОГО УСТРОЙСТВА С ПАРАЛЛЕЛЬНОКОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ
- Определение твердости
- Определение гранулометрического состава
- 2.3.5 Определение твердости