Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 47
Текст из файла (страница 47)
Дляэтой цели в области памяти каждого узла заводятся специальные буферы. Таккак емкость буферов в каждом узле конечна, может случиться так, что ни одинпакет не может быть продвинут, потому что все буферы в следующем узле сетиуже заполнены. Эта ситуация изображена на рис. 5.1.
Каждый из четырех узловимеет B буферов, и в каждый буфер можно поместить ровно один пакет. Из узлаs в узел t были отправлены B пакетов, адресованных узлу v, а из узла v в узелu были отправлены B пакетов, адресованных узлу s. Все буферы в узлах u и vтеперь заполнены, и вследствие этого ни один пакет, хранящийся в узлах t и u,нельзя переправить по назначению.6s1B 6661PPP1P1PPPPPPPPPPPPPPPPPPPPB B BtuvПустой буферPP Заполненный буферРис.
5.1. Пример блокировки хранения-продвиженияСитуацию, когда группа пакетов ни за что не может достичь своего адресата,из-за того что каждый из них простаивает в ожидании пока освободиться буфер,занятый другим пакетом из той же группы, принято называть блокировкой илитупиком хранения-продвижения. (В конце этой главы мы бегло ознакомимсяс другими типами тупиковых ситуаций.) При проектировании сетей с коммутациейпакетов важно уметь справляться с блокировками хранения-продвижения. В этойглаве мы обсудим ряд методов (их обычно называют контроллерами), которыеможно использовать для того, чтобы не допустить возникновения тупиковых ситуаций, путем наложения определенных ограничений на порядок формирования ипродвижения пакетов. Методы предотвращения ситуаций блокировки хранения –продвижения реализуются на сетевом уровне эталонной модели взаимодействияоткрытых систем OSI (§ 1.2.2).171Мы рассмотрим две разновидности этих методов, основанных на структурированном и неструктурированном устройстве области буферной памяти.Методы, использующие структурированную буферную память (§ 5.5.2), выделяют в узле для каждого пакета особый буфер, который должен быть занят всякийраз, когда пакет сформирован или получен.
Если этот буфер уже занят, то принимать этот пакет нельзя. Методы, использующие неструктурированную буфернуюпамять (§ 5.5.3), имеют дело с равноправными буферами; в таком методе лишьпредписывается, можно или нельзя принимать пакет, но не указывается, в какой буфер следует его поместить. Необходимые определения и обозначения мывведем в § 5.5.1, а в заключение обсудим в § 5.4 ряд дальнейших вопросов.5.1. ВведениеКак обычно, сеть моделируется графом G = (V, E); расстояние между вершинами измеряется числом звеньев пути.
В каждом узле выделено B буферов длявременного хранения пакетов. Множество всех буферов обозначим символом B ,а отдельные буфера будем обозначать символами b, c, b u , и т. п.Обработка пакетов в узлах сети осуществляется при помощи действий следующих трех типов, которые могут выполняться в сети.1.
Формирование пакета. В узле u «создается» новый пакет p (в действительности прием этого пакетa происходит в протоколе более высокого уровня) ипомещается пустой буфер узла u. В этом случае узел u называется источникомпакета p.2. Продвижение пакета.
Пакет p перемещается из узла u в свободныйбуфер следующего узла w на маршруте его продвижения (выбор маршрута осуществляет используемый алгоритм маршрутизации). В результате этого действияопустошается буфер, ранее занятый пакетом p. И хотя контроллеры, которые мыдалее опишем, могут наложить запрет на это действие, предполагается, что в сетитакой шаг всегда допустим, т.
е. если контроллер не запрещает это действие, тоего можно осуществить.Легко видеть, что в системах с синхронным обменом сообщениями это действие выполняется за один переход согласно определению 2.7. В системах с асинхронным обменом сообщениями такое действие нельзя выполнить в рамках одного перехода, руководствуясь определением 2.6, но его можно реализовать, например, следующим образом. Узел u неоднократно пересылает пакет p в узел w,но не удаляет этого пакета из буфера, до тех пор пока не получит подтверждения.Когда пакет p поступает в узел w, то процесс w принимает решение о том, может ли этот пакет быть помещен в один из буферов.
Если это возможно, то пакетпомещается в нужный буфер и узлу u отправляется подтверждение; в противномслучае пакет просто игнорируется. Конечно, можно предложить и более эффективные способы реализации указанного действия. Например, можно потребовать,чтобы узел u не отправлял пакет p, до тех пор пока он не будет осведомлен о том,что узел w примет пакет p. Во всяком случае данное действие состоит из нескольких переходов того типа, который был введен в определении 2.6, но в этой главенам выгодно считать, что действие выполняется за один шаг.172Гл. 5.
Неблокируемая коммутация пакетов3. Поглощение пакета. Пакет p, занимающий некоторый буфер узла-адресата,удаляется из буфера. Считается, что в сети такое действие всегда разрешено.Обозначим символом P совокупность всех путей, по которым могут следоватьпакеты. Эта совокупность определяется конкретным алгоритмом маршрутизации(см. гл. 4); мы не будем касаться здесь вопроса о том, как образуется множествоP . Пусть k обозначает число звеньев самого протяженного пути из множестваP . Совсем не обязательно, чтобы число k было равно диаметру графа G; числоk может превосходить диаметр графа, если алгоритм маршрутизации не отдает предпочтение кратчайшим путям, но может быть также и меньше диаметра,если взаимосвязь в графе G осуществляется только между узлами, находящимисянедалеко друг от друга.Как видно из примера, приведенного в начале этой главы, тупиковые ситуации могут возникать, если разрешается неограниченное выполнение указанныхдействий (с учетом того, что в узле u должен быть пустой буфер, для того чтобысформировался пакет, и узел w должен иметь свободный буфер, чтобы принятьнаправленный в этот узел пакет).
Мы приведем определение контроллера — алгоритма, который разрешает или запрещает выполнение тех или иных действийв сети, подчиняясь при этом следующим требованиям.1. Всегда разрешено поглощение пакета, доставленного по назначению.2. Всегда разрешено формирование пакета в узле, все буферы которого свободны.3. Контроллер может использовать только локальную информацию; инымисловами, решение о том, может ли узел u принять тот или иной пакет, вырабатывается на основе той информации, которой располагает узел u или котораясодержится в самом пакете.Второе из приведенных требований исключает тривиальные решения задачи предотвращения блокировок (см.
определение 5.2) путем установления всеобъемлющегозапрета на прием какого-либо пакета в сети. Как и в гл. 2, мы будем использовать запись Zu для обозначения множества всех состояний процесса u, а записьM — для обозначения множества всех возможных сообщений (пакетов).Определение 5.1. Контроллером для сети G = (V, E) называется совокупность пар con = {Genu , Foru }u∈V , где Genu ⊆ Zu × M и Foru ⊆ Zu × M. Еслиcu ∈ Zu — это такое состояние процесса u, в котором все буферы узла u свободны,то для любого пакета p ∈ M имеет место включение (cu , p) ∈ Genu .Контроллер con разрешает формирование пакета p в узле u, который находится в состоянии cu , тогда и только тогда, когда (cu , p) ∈ Genu , и разрешаетпродвижение пакета p из узла u в узел w тогда и только тогда, когда (c w , p) ∈∈ Forw .
В формальном определении контроллера нет никаких условий, касающихся поглощения пакетов, потому что поглощение пакетов (в узле-адресате)всегда разрешено. Действиями сети под управлением контроллера con являютсявсе те и только те действия сети, которые разрешены контроллером con.Говорят, что пакет заблокирован в сети, если никакая последовательностьдействий сети не позволяет доставить этот пакет по назначению.5.2.
Структурированные решения173Определение 5.2. Для заданной сети G, контроллера con для G и конфигурации сети G пакет p (присутствующий в конфигурации ) называется заблокированным, если не существует никакой последовательности действий подуправлением контроллера con, применимой к конфигурации , в результате выполнения которых пакет p будет поглощен. Конфигурация называется тупиковой, если в ней присутствует заблокированный пакет.Как следует из примера, изображенного на рис.
5.1, тупиковые конфигурациисуществуют для любого контроллера. Задача контроллера состоит в том, чтобы непозволить сети попасть в такие конфигурации. Начальными конфигурациями сетиобъявляются такие конфигурации, в которых отсутствуют какие-либо пакеты.Определение 5.3. Контроллер называется беступиковым, если под управлением этого контроллера невозможно попасть из начальной конфигурации втупиковую.5.2. Структурированные решенияМы рассмотрим здесь класс контроллеров, в основу которых положены т. н.буферные графы, введенные Мерлином и Швейцером в работе [148] .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
