Справедливая» очередь
«Справедливая очередь» нацелена на преодоление отмеченной выше ассиметрии распределения ресурсов коммутатора. Пусть каждый информационный поток обслуживается своей логической очередью. В идеальной системе (поток входных данных рассматривается как некая непрерывная и всегда существующая субстанция) пропускная способность выходной линии (С) может быть разделена поровну между всеми очередями посредством их циклического подключения к выходной линии на строго определенные и равные промежутки времени (см. слайд). При наличии n очередей, каждая из них получает возможность передавать свои пакеты в выходную линию со скоростью С/n бит/сек.
Эффективная скорость передачи может быть и выше, поскольку некоторые очереди становятся время от времени пустыми, и в это время другие из них могут передавать данные. Такая организация очереди предупреждает монополизацию ресурсов выходной линии «жадными» приложениями. Размер буфера для каждого потока может быть выбран таким, чтобы удовлетворялись специфические требования к уровню потерь пакетов конкретного потока.
Однако, рассматриваемая очередь является «справедливой» когда мы считаем входные потоки идеальными (непрерывными). В этом случае, пропускная способность передающей линии действительно равномерно распределяется между всеми непустыми очередями. Однако, в силу дискретной природы потока и различия размеров его пакетов, «справедливость» не обеспечивается.
Каждая из входных очередей циклически получает доступ к выходной линии на строго определенные и равные промежутки времени, и за этот интервал может быть передано строго определенное количество бит информации. Если длина пакета превосходит это значение, то он не будет передан; если она меньше – то часть времени доступа к линии этой очередью будет потрачена непроизводитеьно.
Для уменьшения таких непроизводительных потерь можно дефрагментировать приходящие пакеты на относительно короткие составляющие, что, очевидно, будет вести к усложнению процедуры коммутации.
Посмотрем на различия в обслуживании «идеального» потока и потока пакетов конечной длины в системе с двумя очередями.
Каждая из двух очередей содержит только по одному пакету размером L бит; при этом пропускная способность выходной линии составляет L бит/сек = 1 пакет/сек. В идеальной системе можно обеспечить для каждой очереди возможность передавать свои данные на скорости ½ пакета в секунду (рис. а).
Если обслуживание очередей организовано побитно (т.е. из каждой очереди равномерно передается по одному биту), то время цикла передачи составляет 2 секунды. Весь пакет из первой очереди будет передан за время 2-1/L секунд, а передача пакета из второй очереди завершится ровно через 2 секунды (уже видна некоторая «несправедливость» в обслуживании).
Если же обслуживание очередей организовано на «пакетном» принципе (рис. б), то пакет из первой очереди будет обслужен за 1 секунду, а из второй – через 2 секунды («несправедливость» стала еще большей). Естественно, усредненная «несправедливость» будет тем меньше, чем больше пакетов будет обслужено из каждой очереди.
Однако, в случае неравенства длин пакетов распределение пропускной способности выходной линиии не будет «справедливым». Например, если длины пакетов первой очереди вдвое больше длин пакетов второй очереди, то при достаточной длине очередей и обслуживании их на «попакетной» основе эффективная полоса пропускания на данном коммутаторе для первого потока будет вдвое больше, чем для второго. Поэтому, разумным решением является предоставление каждому потоку такой доли ресурса выходной линии, чтобы время завершения обработки пакетов каждого из них оказалось близким к значению, которое было бы получено в идеальной системе с непрерывным потоком входных данных. При попакетной дисциплине обслуживания единственной возможностью достижения этого остается выбор очередности обслуживания буферов.
Для этого каждый пакет, находящийся в очереди, следует снабдить меткой времени окончания его обслуживания, вычисленной исходя из модели непрерывного потока. Очередность же обслуживания входных буферов в каждом цикле определяется значениями этих меток по принципу «Пакет с меньшим значением метки обслуживается первым». Такую дисциплину обслуживания можно назвать «попакетная справедливая» очередь. Рассмотрим процедуру вычисления метки.
Пусть существуют n потоков, каждый из которых обслуживается отдельной очередью со скоростью 1 бит/сек (модель, максимально близкая к непрерывному потоку). Циклом обслуживания назовем период времени, в течении которого каждая очередь обслуживается по одному разу и R(t) – число циклов обслуживания n очередей, реализованных за время t. Будем считать, что k-й пакет i-го потока прибывает в пустой буфер своей очереди в момент 
и длина этого пакета равна P(i,k) бит. Этот пакет на побитовой основе будет обработан за P(i,k) циклов, т.е в момент t*, когда
.
Если пакет прибывает не в пустой буфер, то 
.
Величина F(i,k) и будет использована как финишная метка обслуживания пакета.
Величина F(i,k) не опреднляет действительное (реальное) время завершения обработки k-го пакета; она служит лишь признаком очередности, в которой будут обслуживаться буферы в пределах данного цикла.
Для примера рассмотрим систему из двух очередей, первая из которых имеет один пакет единичной длины, а вторая – один пакет удвоенной длины.
В идеальной системе обслуживание очередей производится со скоростью пакет в ½ сек в течении времени пока обе они имеют данные (т.е. на интервале от 0 до 2 единиц времени) и со скоростью пакет в 1 сек - на интервале от 2 до 3 единиц времени (рис. слева ).
В «попакетной справедливой» очереди значения финишних меток будут F(1,1)= R(0)+ 1=1 и F(2,1)= R(0)+ 2=2. Поскольку F(1,1)< F(2,1), то обслуживание начинается с первой очереди (рис. справа).
Таким образом, если в идеальной системе поток с короткими пакетами передавался с эффективной скоростью ½ сек-1., а поток с более длинным пакетом – со скоростью 2/3 сек-1, то обслучивание их в «справедливой» очереди реализовывалось с эффективными скоростями равными 1сек-1 и 2/3 сек-1 соответственно. Если бы обслуживание началось с очереди, имеющей более длинный пакет, то эти скорости имели бы значения 1сек-1 для «длинной» очереди и 1/3 сек-1 для короткой. Последние значения отличаются от идеальных в большей степени.