<<
>>

Организация входных и выходных буферов

Чтобы решить, какие два паросочетания коммутатор должен переместить на за- данном шаге, необходимо определить некоторые характеристики, определяющие текущее состояние коммутатора относительно чистой выходной очереди.
Для начала для пакета p определяется его время отправки TL(p), равное временному шагу, на котором он был бы отправлен по выходному каналу коммутатора при использовании чистой выходной очереди. Мы стремимся к тому, чтобы каждый пакет p отправлялся из коммутатора (с ускоренными очередями ввода/вывода) ровно на шаге TL(p).

На концептуальном уровне каждый входной буфер представляет собой упо- рядоченный список; при этом сохраняется возможность вставки прибывающих пакетов в середину порядка, а также перемещения пакета в выходной буфер даже тогда, когда он еще не находится в начале очереди. Несмотря на это, линейное упорядочение буфера образует полезную метрику прогресса. С другой стороны, выходные буферы упорядочивать не нужно; когда приходит время отправки пакета, он просто покидает буфер.

Конфигурация напоминает терминал аэро- порта: входные буферы соответствуют стойкам регистрации, выходные — залам ожидания, а внутренняя реализация коммутатора — сильно загруженному кон- трольному пункту службы безопасности. Основное напряжение приходится на входные буферы: если не успеть к началу очереди до завершения регистрации, то вы можете опоздать на самолет; к счастью, служащие аэропорта могут извлечь вас из середины очереди и провести через контрольный пункт в ускоренном темпе. Напротив, в выходных буферах можно расслабиться: пассажиры спокойно сидят, пока не будет объявлена посадка на их рейс, после чего просто отправляются на самолет. Главное — преодолеть «затор» в середине, чтобы пассажиры успели к отлету.

В частности, из этой аналогии следует, что нам не нужно беспокоиться о па- кетах, уже находящихся в выходных буферах; они отправятся в нужное время.

Соответственно мы будем называть пакет 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).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Организация входных и выходных буферов:

  1. Выходные данные телевещателя
  2. 1.2.2.2. Выходные, праздничные и нерабочие дни
  3. 34. Социальная организация как вид социальной системы. Типы социальных организаций
  4. Статья 455. Использование передачи (программы) организации вещания
  5. ОРГАНИЗАЦИЯ
  6. ОРГАНИЗАЦИЯ ФОРМАЛЬНАЯ
  7. § 12.2. Гибкая организация
  8. ОРГАНИЗАЦИЯ ПРЕГЕНИТАЛЬНАЯ
  9. 35. Элементы организации
  10. § 3.2. Цели организации
  11. § 3.7. Персонал организации
  12. § 5.3. Бюрократия в организациях
  13. Функции управления в организации.
  14. Определение культуры организации.
  15. ГЛАВА 7. НЕКОММЕРЧЕСКИЕ ОРГАНИЗАЦИИ
  16. Работа с персоналом в организации.
  17. 1.3. Организация фокус-групп