Определение порядка выдачи пакетов из матрицы регистров

Важнейшей составляющей процесса коммутации пакетов является их дис­петчеризация, которая включает анализ способа размещения множества пакетов в МР и определение порядка выдачи пакетов из строк матрицы (этап 3 ПКП- метода).

Формализуем определение порядка выдачи пакетов из матрицы регистров.

Обозначим через F_kмножество пакетов, находящихся в матрице Bна k-м такте ретрансляции, k = 0,1,2,.... На множествеопределим функцию S_k, та­кую, что, если регистр B_jсодержит некоторый пакет c_qв k-м такте

ретрансляции,если регистр B_jсвободен. Таким образом:

36

На рис. 2.2 дана графическая иллюстрация определения функции S_k. Здесь квадратами показаны отдельные регистры (регистровые ячейки) МР, а вложенные

Рисунок 2.2. Определение функции S_kдля заданного распределения пакетов множества F_kв матрице регистров

На множестве пакетов F_kопределим отношение совместности

такое, что

37

Еслито пакеты c_qи c_rбудем считать совместными (такие пакеты

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

Введем в рассмотрение граф совместности. Вершины этого

графа соответствуют пакетам множества F_k, а ребра - отображают их совмест­ность. Взвесим вершины графа Γ _kнеотрицательными целыми числамиВес

τ_qвершины c_qбудем определять временем, которое пакет c_qпровел в матрице регистров, выраженным в числе тактов работы КУ. Сразу после записи пакета c_q в МР полагаем τ = 0.

q

На рис. 2.3 в качестве примера показан взвешенный граф совместности Γ_k для случая, представленного на рис. 2.2 (значения весов выбраны условно и ука­заны внутри вершин).

Выделим в графе Γ _kкликутакую, что:

Если клик, отвечающих условию (2.2) в графе Γ_kнесколько, то выберем любую из них равновероятным способом. По определению носителькликибудет включать только совместные вершины и будет максимальным по включению. Та­ким образом, пакеты, соответствующие вершинамбудут допускать парал­

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

Рисунок 2.3. Взвешенный граф совместности Γ_kдля случая рис. 2.2

Для графа Γ _k, изображенного на рис. 2.3, выделяется клика Γkс носителем (пунктирная линия на рис. 2.3). Для этой клики Сумма весов остальных трех клик, имеющихся в данном графе, равна

1, 1 и 0.

Учитывая введенное формализованное представление, один такт (цикл) ре­трансляции пакетов при использовании ПКП-метода можно описать приведенным ниже псевдокодом. Далее для удобства через c_lи B(μ(c_l)) условимся обозначать соответственно пакет, находящийся в голове очереди Q_l, и регистр матрицы B, выбранный для записи этого пакета согласно реализуемому алгоритму маршрути­зации.

НАЧАЛО ПРОЦЕДУРЫ «Цикл ретрансляции пакетов»

ПРИНЯТЬ k = 0

ВЫПОЛНЯТЬ ПОКА хотя бы одна очередь Q₁не пуста

СЧИТАТЬ пакеты из не пустых очередей [Q_l}

ОПРЕДЕЛИТЬ множество регистров {b (μ( c_l

ПЕРЕПИСАТЬ в матрицу Bвсе пакеты {c_r}, для которых

КОНЕЦ ВЫПОЛНЯТЬ ПОКА

КОНЕЦ ПРОЦЕДУРЫ «Цикл ретрансляции пакетов»

Рассматривая приведенный выше псевдокод с привязкой к структурной мо­дели КУ (см. рис. 2.1), уточним функции элементов данной модели. Передача в МР считанных из очередей пакетовобеспечивается коммутирующими эле­ментами R_x, R₂,..., R_n. Проверка условия /и блокировка передачи

пакетов в МР (HOL blocking) осуществляется коммутирующими элементами K_x,K₂,...,K_nи клапанами G_x,G₂,...,G_n. Формирование клики Γ'обеспечивается за счет матричной организации КУ, при которой совместные пакеты автоматиче­ски попадают в разные строки МР, а учет весов вершин с целью выбора множе­ства Fс максимальным суммарным весом вершин реализуется правилами φ_x,φ₂,...,φ_n, определяющими работу коммутирующих элементов L_x,L₂,.,L_n.

2.4.