Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 46
Текст из файла (страница 46)
4. Алгоритмы маршрутизацииДокажите, что ни один алгоритм маршрутизации не способен обеспечить доставку пакетов по адресу, если сеть испытывает непрерывные изменения топологии.4.6.2Упражнение 4.2. Студент предложил исключить из алгоритма 4.6 отправление сообщений (nys, w). Он привел следующий аргумент: узел и так узнаето том, что его сосед не является сыновней вершиной, если от этого соседа непоступает сообщений (ys, w).Можно ли таким образом модифицировать алгоритм? Какова будет сложностьтакого алгоритма?Упражнение 4.3. Докажите, что приведенная ниже формула задает инвариант алгоритма Чанди—Мисры вычисления путей, ведущих в вершину vq (алгоритм 4.7).Vm, w : (mydist, vq, d) e M wuA Vm: d(u, vo) ^ Du[v0].=^>d(w, vq) ^ dПриведите пример выполнения, в котором количество обменов сообщениями экспоненциально зависит от числа каналов в сети.4.6.3Упражнение 4.4.
Выясните, какие значения будут иметь все переменные взаключительной конфигурации алгоритма Netchange в том случае, когда этоталгоритм применяется к сети, имеющей следующую топологическую структуру:©<вПосле того как была достигнута заключительная конфигурация, в сети возникновый канал связи между узлами А и F. Какое сообщение узел F отправит узлу Апри обработке уведомления (repair, Л)? Какое послание узел А отправит узлу Fв ответ на это сообщение?4.6.4Упражнение 4.5. Приведите пример, свидетельствующий о том, что лемма 4.22 неверна для сетей с асимметричной характеристикой стоимости каналов.Упражнение 4.6.
Существует ли такая ILS, в которой для построения маршрутов используются не все каналы? Существует ли правильная схема, обладающая этим свойством? Существует ли оптимальная схема, обладающая этимсвойством?Упражнение 4.7. Приведите пример такого графа G и такого дерева поискав глубину Т для графа G, которые обладают следующими свойствами: граф G4.6. Упражнения к главе 4169имеет N = п2 вершин, диаметр графа G и глубина дерева Т являются величинами порядка 0(п ), и при этом существует такая пара узлов и и о, что схемаинтервальной разметки в глубину обеспечивает доставку пакета из вершины ив вершину v по маршруту, состоящему из jV —1 звеньев.(Граф можно выбрать таким, что G будет внешне планарным, и отсюда согласно теореме 4.37 следует, что G действительно имеет оптимальную ILS.)Упражнение 4.8. Постройте схему интервальной разметки в глубину длякольца, состоящего из N вершин.
Покажите, что существуют такие узлы и и и,что d(u, v) = 2 , а схема вынуждена построить маршрут, состоящий из jV - 2звеньев, для доставки пакета из вершины и в вершину v.4.6.5Упражнение 4.9. Докажите, что из минимальности дерева Т, используемогов доказательстве теоремы 4.48, следует, что это дерево имеет не более пг листьев. Докажите, что всякое дерево с m листьями имеет не более m —2 вершинразвилок.ГЛАВА5НЕБЛОКИРУЕМАЯ КОММУТАЦИЯ ПАКЕТОВСообщения (пакеты), перемещающиеся по коммуникационной сети с пакетнойкоммутацией, должны сохраняться в памяти каждого узла, перед тем как ониотправлены в следующий узел по пути их следования к вершине-адресату.
Дляэтой цели в области памяти каждого узла заводятся специальные буферы. Таккак емкость буферов в каждом узле конечна, может случиться так, что ни одинпакет не может быть продвинут, потому что все буферы в следующем узле сетиуже заполнены. Эта ситуация изображена на рис. 5.1. Каждый из четырех узловимеет В буферов, и в каждый буфер можно поместить ровно один пакет. Из узлаs в узел t были отправлены В пакетов, адресованных узлу и, а из узла v в узели были отправлены В пакетов, адресованных узлу s. Все буферы в узлах и и итеперь заполнены, и вследствие этого ни один пакет, хранящийся в узлах t и и,нельзя переправить по назначению.Г1I Пустой буферЕ х Л Заполненный буферВР и с .
5 . 1 . Пример блокировки хранения-продвиженияСитуацию, когда группа пакетов ни за что не может достичь своего адресата,из-за того что каждый из них простаивает в ожидании пока освободиться буфер,занятый другим пакетом из той же группы, принято называть блокировкой илитупиком хранения-продвижения. (В конце этой главы мы бегло ознакомимсяс другими типами тупиковых ситуаций.) При проектировании сетей с коммутациейпакетов важно уметь справляться с блокировками хранения-продвижения. В этойглаве мы обсудим ряд методов (их обычно называют контроллерами), которыеможно использовать для того, чтобы не допустить возникновения тупиковых ситуаций, путем наложения определенных ограничений на порядок формирования ипродвижения пакетов.
Методы предотвращения ситуаций блокировки храненияпродвижения реализуются на сетевом уровне эталонной модели взаимодействияоткрытых систем OSI (§ 1.2.2).5.1. Введение171Мы рассмотрим две разновидности этих методов, основанных на структурированном и неструктурированном устройстве области буферной памяти.Методы, использующие структурированную буферную память (§5.5.2), выделяют в узле для каждого пакета особый буфер, который должен быть занят всякийраз, когда пакет сформирован или получен. Если этот буфер уже занят, то принимать этот пакет нельзя.
Методы, использующие неструктурированную буфернуюпамять (§5.5.3), имеют дело с равноправными буферами; в таком методе лишьпредписывается, можно или нельзя принимать пакет, но не указывается, в какой буфер следует его поместить. Необходимые определения и обозначения мывведем в §5.5.1, а в заключение обсудим в §5.4 ряд дальнейших вопросов.5.1. ВведениеКак обычно, сеть моделируется графом G = (V, £); расстояние между вершинами измеряется числом звеньев пути.
В каждом узле выделено В буферов длявременного хранения пакетов. Множество всех буферов обозначим символом В,а отдельные буфера будем обозначать символами Ь, с, Ьи, и т. п.Обработка пакетов в узлах сети осуществляется при помощи действий следующих трех типов, которые могут выполняться в сети.1. Формирование пакета.
В узле и «создается» новый пакет р (в действительности прием этого пакета происходит в протоколе более высокого уровня) ипомещается пустой буфер узла и. В этом случае узел и называется источникомпакета р.2. Продвижение пакета. Пакет р перемещается из узла и в свободныйбуфер следующего узла w на маршруте его продвижения (выбор маршрута осуществляет используемый алгоритм маршрутизации). В результате этого действияопустошается буфер, ранее занятый пакетом р. И хотя контроллеры, которые мыдалее опишем, могут наложить запрет на это действие, предполагается, что в сетитакой шаг всегда допустим, т.
е. если контроллер не запрещает это действие, тоего можно осуществить.Легко видеть, что в системах с синхронным обменом сообщениями это действие выполняется за один переход согласно определению 2.7. В системах с асинхронным обменом сообщениями такое действие нельзя выполнить в рамках одного перехода, руководствуясь определением 2 .6 , но его можно реализовать, например, следующим образом. Узел и неоднократно пересылает пакет р в узел w,но не удаляет этого пакета из буфера, до тех пор пока не получит подтверждения.Когда пакет р поступает в узел w, то процесс w принимает решение о том, может ли этот пакет быть помещен в один из буферов. Если это возможно, то пакетпомещается в нужный буфер и узлу и отправляется подтверждение; в противномслучае пакет просто игнорируется. Конечно, можно предложить и более эффективные способы реализации указанного действия. Например, можно потребовать,чтобы узел и не отправлял пакет р, до тех пор пока он не будет осведомлен о том,что узел w примет пакет р.
Во всяком случае данное действие состоит из нескольких переходов того типа, который был введен в определении 2 .6 , но в этой главенам выгодно считать, что действие выполняется за один шаг.172Гл. 5. Неблокируемая коммутация пакетов3. Поглощение пакета. Пакет р, занимающий некоторый буфер узла-адресата,удаляется из буфера. Считается, что в сети такое действие всегда разрешено.Обозначим символом V совокупность всех путей, по которым могут следоватьпакеты.
Эта совокупность определяется конкретным алгоритмом маршрутизации(см. гл. 4); мы не будем касаться здесь вопроса о том, как образуется множествоV . Пусть k обозначает число звеньев самого протяженного пути из множестваV . Совсем не обязательно, чтобы число k было равно диаметру графа G; числоk может превосходить диаметр графа, если алгоритм маршрутизации не отдает предпочтение кратчайшим путям, но может быть также и меньше диаметра,если взаимосвязь в графе G осуществляется только между узлами, находящимисянедалеко друг от друга.Как видно из примера, приведенного в начале этой главы, тупиковые ситуации могут возникать, если разрешается неограниченное выполнение указанныхдействий (с учетом того, что в узле и должен быть пустой буфер, для того чтобысформировался пакет, и узел да должен иметь свободный буфер, чтобы принятьнаправленный в этот узел пакет).
Мы приведем определение контроллера — алгоритма, который разрешает или запрещает выполнение тех или иных действийв сети, подчиняясь при этом следующим требованиям.1. Всегда разрешено поглощение пакета, доставленного по назначению.2. Всегда разрешено формирование пакета в узле, все буферы которого свободны.3. Контроллер может использовать только локальную информацию; инымисловами, решение о том, может ли узел и принять тот или иной пакет, вырабатывается на основе той информации, которой располагает узел и или котораясодержится в самом пакете.Второе из приведенных требований исключает тривиальные решения задачи предотвращения блокировок (см. определение 5.2) путем установления всеобъемлющегозапрета на прием какого-либо пакета в сети. Как и в гл.
2, мы будем использовать запись Zu для обозначения множества всех состояний процесса и, а записьМ . — для обозначения множества всех возможных сообщений (пакетов).Определение 5.1. Контроллером для сети G = (К, Е) называется совокупность пар con = {Genu, Foru}uev , где Genu С Zu х М и Foru С Zu х М . Еслиси€ Zu — это такое состояние процесса и, в котором все буферы узла и свободны,то для любого пакета р е М имеет место включение (си, р) € Genu.Контроллер con разрешает формирование пакета р в узле и, который находится в состоянии си, тогда и только тогда, когда (си, р) € Genu, и разрешаетпродвижение пакета р из узла и в узел да тогда и только тогда, когда (cw, р) €€ Forw. В формальном определении контроллера нет никаких условий, касающихся поглощения пакетов, потому что поглощение пакетов (в узле-адресате)всегда разрешено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
