Организация входных и выходных буферов
На концептуальном уровне каждый входной буфер представляет собой упо- рядоченный список; при этом сохраняется возможность вставки прибывающих пакетов в середину порядка, а также перемещения пакета в выходной буфер даже тогда, когда он еще не находится в начале очереди. Несмотря на это, линейное упорядочение буфера образует полезную метрику прогресса. С другой стороны, выходные буферы упорядочивать не нужно; когда приходит время отправки пакета, он просто покидает буфер.
Конфигурация напоминает терминал аэро- порта: входные буферы соответствуют стойкам регистрации, выходные — залам ожидания, а внутренняя реализация коммутатора — сильно загруженному кон- трольному пункту службы безопасности. Основное напряжение приходится на входные буферы: если не успеть к началу очереди до завершения регистрации, то вы можете опоздать на самолет; к счастью, служащие аэропорта могут извлечь вас из середины очереди и провести через контрольный пункт в ускоренном темпе. Напротив, в выходных буферах можно расслабиться: пассажиры спокойно сидят, пока не будет объявлена посадка на их рейс, после чего просто отправляются на самолет. Главное — преодолеть «затор» в середине, чтобы пассажиры успели к отлету.В частности, из этой аналогии следует, что нам не нужно беспокоиться о па- кетах, уже находящихся в выходных буферах; они отправятся в нужное время.
Соответственно мы будем называть пакет p необработанным, если он все еще на- ходится во входном буфере, и определим некоторые полезные метрики для таких пакетов. Входным окном IC(p) называется количество пакетов, находящихся перед пакетом p в его входном буфере. Выходным окном OC(p) называется количество пакетов, уже находящихся в выходном буфере p и имеющих более раннее время отправки. У необработанного пакетаp дела идут хорошо, если OC(p) намного боль- ше IC(p); в этом случае p находится ближе к началу очереди в его входном буфере, а в выходном буфере перед ним еще остается много пакетов. Для представления этой связи мы определим метрику Slack(p) = OC(p) - IC(p), заметив, что большие значения Slack(p) являются предпочтительными.Итак, наш план: паросочетания будут передаваться по коммутатору так, чтобы постоянно сохранялись следующие два свойства:
(i) Slack(p) > 0 для всех необработанных пакетов p;
(ii) На любом шаге, начинающемся с IC(p) = OC(p) = 0, пакет p будет переме- щаться в свой выходной буфер в первом паросочетании.
Сначала нужно убедиться в том, что сохранения этих двух свойств достаточно.
(E.1) Если свойства (i) и (ii) выполняются для всех необработанных пакетов во все моменты времени, то каждый пакет p будет отправлен в свое положенное время TL(p).
Доказательство. Если p находится в своем выходном буфере в начале шага TL(p), то, очевидно, он может быть отправлен; в противном случае он бы находился во входном буфере. В таком случае OC(p) = 0 в начале шага. Согласно свойству (i), имеем Slack(p) = OC(p) - IC(p) > 0, а следовательно, IC(p) = 0. Затем из свойства (ii) следует, что пакет p будет перемещен в выходной буфер в первом паросочетании этого шага, а следовательно, также будет отправлен в этом шаге. ■
Как выясняется, свойство (ii) гарантируется достаточно легко (и оно естествен- но выполняется в приведенном ниже решении), поэтому мы сосредоточимся на непростой задаче выбора паросочетаний для поддержания свойства (i).
Еще по теме Организация входных и выходных буферов:
- Выходные данные телевещателя
- 1.2.2.2. Выходные, праздничные и нерабочие дни
- 34. Социальная организация как вид социальной системы. Типы социальных организаций
- Статья 455. Использование передачи (программы) организации вещания
- ОРГАНИЗАЦИЯ
- ОРГАНИЗАЦИЯ ФОРМАЛЬНАЯ
- § 12.2. Гибкая организация
- ОРГАНИЗАЦИЯ ПРЕГЕНИТАЛЬНАЯ
- 35. Элементы организации
- § 3.2. Цели организации
- § 3.7. Персонал организации
- § 5.3. Бюрократия в организациях
- Функции управления в организации.
- Определение культуры организации.
- ГЛАВА 7. НЕКОММЕРЧЕСКИЕ ОРГАНИЗАЦИИ
- Работа с персоналом в организации.
- 1.3. Организация фокус-групп