Обмен пакетами при переключении между несколькими очередями: различия между версиями

Сетевой переключатель между несколькими очередями обслуживает m входящих очередей, обеспечивая пересылку пакетов данных, поступающих в m входных портов, через один выходной порт. На каждом временном отрезке на входные порты может поступить произвольное число пакетов, но только один пакет может пройти через общий выходной порт. Каждый пакет помечен значением, указывающим его приоритет в сети качества обслуживания (Quality of Service, QoS). Поскольку каждая очередь имеет ограниченную емкость B, а скорость поступления пакетов может быть намного выше скорости передачи, из-за недостаточного размера очереди часть пакетов может быть потеряна. Цель заключается в максимизации пропускной способности, которая определяется как суммарная стоимость переданных пакетов. Задача включает два взаимозависимых аспекта: управление буфером, а именно, какие пакеты следует пропускать в очереди, и планирование, т.е. какую очередь (по принципу FIFO) использовать для пересылки на каждом временном отрезке.

Задача 1 (задача с единичной стоимостью). Стоимость каждого пакета равна 1. Поскольку все пакеты в этом случае оказываются одинаково важны, это упрощает политику контроля допуска: все поступающие пакеты должны быть помещены в очередь; в случае переполнения буфера не имеет значения, какие пакеты сохраняются в очереди и какие отбрасываются.

Задача 2 (задача общего вида). Каждый пакет имеет индивидуальную стоимость, обычно принадлежащую к диапазону <math>[1, \alpha]</math>, заданному для всех пакетов. Специальный случай задачи имеет дело с двухточечной моделью, в которой стоимость пакетов принимает одно из значений <math> \{ 1, \alpha \}</math>.