Справедливая очередь
-
Основы справедливой очереди
- Справедливая очередь обеспечивает равномерное распределение ресурсов между потоками.
- Используется в маршрутизаторах и коммутаторах для передачи пакетов из буфера.
- Скорость передачи данных зависит от количества активных потоков и пропускной способности канала.
-
Справедливость в сетевом планировании
- Справедливость имеет разные определения, включая циклическое планирование и взвешенную справедливую организацию очередей.
- Существуют формальные понятия оценки справедливости, включая минимальную и максимальную справедливость.
-
Алгоритм взвешенной справедливой очереди
- Алгоритм имитирует справедливое распределение ресурсов, учитывая размер пакетов.
- Выбирает порядок передачи пакетов, моделируя время их завершения.
- Сложность алгоритма составляет O(log(n)), где n — количество очередей/потоков.
-
Детали алгоритма
- Используется виртуальное время для упрощения вычислений и поддержания порядка передачи пакетов.
- Виртуальное время не точно моделирует реальное время, но обеспечивает порядок передачи.
-
Псевдокод алгоритма
- Представлен псевдокод для функций receive() и send(), которые выполняются при получении и выборе пакета для отправки.
-
Рекомендации
- Статья ссылается на RFC 970 и другие источники для получения дополнительной информации.
Полный текст статьи: