Моделирование чистой выходной очереди

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

Но что, если взять коммутатор с очередями ввода/вывода и ускорить его работу, перемещая несколько сочетаний за шаг вместо одного? Возможно ли смоделиро- вать коммутатор, использующий чистую выходную очередь? Под этим термином здесь понимается, что последовательность отправок по выходным каналам (при которой коммутатор рассматривается как «черный ящик») должна быть одинако- вой для реализации поведения чистой выходной очереди и ускоренного алгоритма очередей ввода/вывода.

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

В этом разделе будет показано, что хватит гораздо более умеренного ускорения. Мы опишем поразительный результат, который получили Чуан, Гоэл, Маккеун и Прабхакар (Chuang, Goel, McKeown, Prabhakar, 1999), — он показывает, что коммутатор, использующий очереди ввода/вывода с ускорением 2, может моде- лировать коммутатор с чистой выходной очередью. На уровне здравого смысла этот результат использует тот факт, что внутреннее поведение коммутатора не обязано напоминать поведение чистой выходной очереди, если последовательность отправок пакетов с выходных каналов остается неизменной. (Следовательно, про- должая пример из предыдущего абзаца, не обязательно перемещать все n входных пакетов в общий выходной буфер за один шаг; для этого можно выделить больше времени, потому что их отправки по общему выходному каналу все равно будут распределены по более длинному периоду времени.)

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

Еще по теме Моделирование чистой выходной очереди:

  1. Выходные данные телевещателя
  2. 1.2.2.2. Выходные, праздничные и нерабочие дни
  3. Стремиться стать альтруистом «чистой воды» — принципиально неверно.
  4. Наряды вне очереди
  5. 2. Наследники иных (последующих) очередей
  6. 1. Наследники первой очереди
  7. Статья 1263. Третья очередь наследников по закону
  8. Статья 1264. Четвертая очередь наследников по закону
  9. Статья 1265. Пятая очередь наследников по закону
  10. Статья 1262. Вторая очередь наследников по закону
  11. Статья 1261. Первая очередь наследников по закону
  12. Мудрец, в первую очередь, – гармоничный человек
  13. Моделирование
  14. МОДЕЛИРОВАНИЕ
  15. Глава 4. Роль моделирования в социологии
  16. МОДЕЛИРОВАНИЕ ИЛИ ПОДРАЖАНИЕ?
  17. Тема 12. Иконологическое моделирование социальных процессов
  18. Уровни моделирования
  19. СОЦИАЛЬНОЕ МОДЕЛИРОВАНИЕ
  20. Тема 4. Роль моделирования в социологии