МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Распределенные алгоритмы

    { через очередь Qwv}

    begin получить от w;

    ndisu[w,v] := d ; Recompute (v)

    end

    Произошел отказ канала uw:

    begin получить < fail, w> ; Neighu := Neighu \ {w} ,

    forall v ( V do Recompute (v)

    end

    Произошло восстановление канала uw:

    begin получить < repair, w> , Neighu := Neighu ( {w} ;

    forall v ( V do

    begin ndisu[w, v] := N;

    послать < mydist, v, Du{[v]>

    to w

    end

    end

    Алгоритм 4.9 АЛГОРИТМ NETCHANGE (часть 2, для узла и).

    Реакция алгоритма на отказы и восстановления выглядит следующим образом.

    Когда канал между u и w отказывает, w удаляется из Neighu и наоборот.

    Оценка расстояния перевычисляется для каждого пункта назначения и,

    конечно, рассылается всем существующим соседям если оно изменилось. Это

    случай если лучший маршрут был через отказавший канал и нет другого соседа

    w' с ndisu[w', v]= ndisu[w, v]. Когда канал восстановлен(или добавлен

    новый канал) то w добавляется в Neighu, но u имеет теперь неоцененное

    расстояние d(w, v) (и наоборот). Новый сосед w немедленно информирует

    относительно Du[v] для всех пунктов назначения v (посылая

    сообщения ). До тех пор пока u получает подобное сообщения

    от w, u использует N как оценку для d(w,v), т.е., он устанавливает ndisu[w,

    v] в N.

    P(u, w, V)(

    up(u, w) ( w ( Neighu

    (1)

    ( up(u, w) ( Qwu содержит сообщение (

    последнее такое сообщение удовлетворят d = Du[v]

    (2)

    ( up(u, w) ( Qwu не содержит сообщение (

    ndisu[w, v] =Dw [v]

    (3)

    L(u, v) (

    u = v ( (Du[v] = 0 ( Nbu[v] = local) (4)

    ( (u ( v)( (w ( Neighu : ndisu[w, v] < N - 1)(

    ( Du[v] = 1 + min ndisu[w, v] = 1 + ndisu[Nbu[v], v])

    (5)

    w ( Neigh u

    ( (u ( v ( (w ( Neighu : ndisu[w, v]( N—1) (

    (Du[v] = N ( Nbu[v] = udef)

    (6)

    ХPфэЭ0х~йхых‹у9хс' |Др· Pп?єн‰юм?уък5з?йъЫcкЦ?мыХЁнeЪZмИвўй_оРисунок

    4.10 Инварианты P(u, w, v) и L(u, v).

    Инварианты алгоритма Netchange. Мы докажем что утверждения являются

    инвариантами; утверждения даны на Рисунке 4.10. Утверждение P(u, w, v)

    констатирует что если u закончил обработку сообщения от w

    то оценка u расстояния d(w,v) эквивалентна оценке w расстояния d(w, v).

    Пусть предикат up(u, w) истинен тогда и только тогда когда

    (двунаправленный) канал между u и w существует и действует. Утверждение

    L(u, v) констатирует что оценка u расстояния d(u, v) всегда согласована с

    локальными данными u, и Nbu[v] таким образом означен.

    Выполнение алгоритма заканчивается когда нет больше сообщений в любом

    канале. Эти конфигурации не терминальны для всей системы так как вычисления

    в системе могут продолжится позже, начавшись отказом или восстановлением

    канала (на которые алгоритм должен среагировать). Мы пошлем сообщение

    конфигурационной стабильности, и определим предикат stable как

    stable = (u, w : up(u, w) ( Qwu не содержит сообщений

    .

    Это предполагает что переменные Neighu корректно отражают существующие

    рабочие коммуникационные каналы, т.е., что (1) существует изначально. Для

    доказательства инвариантности утверждений мы должны рассмотреть три типа

    переходов.

    (1) Получение сообщения . Первое выполнение результирующего

    кодового фрагмента, как принято, выполняется автоматически и

    рассматривается отдельным переходом. Обратите внимание что в данном

    переходе принимается сообщение и возможно множество сообщений отправляется

    (2) Отказ канала и обработка сообщения < fail. . > узлами на обоих концах

    канала.

    (3) Восстановление канала и обработка сообщения двумя

    соединенными узлами.

    Лемма 4.14 Для всех uo, wo, и vo, P(uo, wo, vo) –– инвариант.

    Доказательство. Изначально, т.e., после выполнения инициализационной

    процедуры каждым узлом, (1) содержится предположением. Если изначально мы

    имеем (up(uo, wo), (2) и (3) тривиально содержатся. Если изначально мы

    имеем up(uo, wo), тогда ndisuo[wo, vo] = N. Если wo = vo то Dwo[wo] = 0 но

    сообщение < mydist, vo, 0> в Qw0u0, таким образом (2) и (3) истинны. Если

    wo ( vo то Dw0[vo]=N и нет сообщений в очереди, что также говорит что (2)

    и (3) содержаться. Мы рассмотрим три типа констатированных переходов

    упомянутых выше.

    Тип (1). Предположим что u получает сообщение от w.

    Следовательно нет топологических изменений и нет изменений в множестве

    Neigh , следовательно (1) остается истинно. Если v(vo то это сообщение не

    меняет ничего в P(uo, wo, vo). Если v = vo, u =uo, и w=wo значение

    ndisu,[wo, vo] может изменится. Однако, если сообщение < mydist, vo, .>

    остается в канале значение этого сообщения продолжает удовлетворять (2),

    так как (2) в сохранности то и (3) также потому что посылка ложна. Если

    полученное сообщение было последним этого типа в канале то d = Dw0[vo] по

    (2), которое подразумевает что заключение (3) становится истинным и (3) в

    сохранности. Посылка (2) становится ложной, таким образом (2) в

    сохранности. Если v = vo, u = wo (и uo сосед u) заключение (2) или (3)

    может быть ложно если значение Dw0[vo] изменилось в следствие выполнения

    Recompute(v) в wo. В этом случае, однако, сообщение < mydist, vo, . > с

    новым значением посылается к uo, которое подразумевает что посылка (3)

    нарушена, и заключение (2) становится истинным, таким образом (2) и (3)

    сохранены. Это происходит и в случае когда сообщение < mydist, vo, . >

    добавляется в Qw0u0, и это всегда удовлетворяет d = Dw0[vo]. Если v = vo и

    u(uo, wo ничего не изменяет в P(uo, wo, vo).

    Тип (2). Предположим что канал uw отказал. Если u = uo и w = wo этот отказ

    нарушил посылку (2) и (3) таким образом эти правила сохранены. (1) в

    безопасности потому что wo удалился из Neighu0 и обратно. Нечто произойдет

    если u = wo и w = uo. Если u = wo но w( uo заключение (2) или (3) может

    быть нарушено так как значение Dw0 [vo] изменилось. В этом случае пересылка

    сообщения < mydist, vo, . > узлом wo опять нарушит посылку (3) и сделает

    заключение (2) истинным, следовательно (2) и (3) в безопасности. Во всех

    других случаях нет изменений в P(uo, wo, vo).

    Тип (3). Предположим добавление канала uw. Если u = uo и w = wo то

    up(vo,wo) истинно, но добавлением wo в Neighu0 (и обратно) это защищает(1).

    Посылка < mydist, vo, Dw0 [vo]> узлом wo делает заключение (2) истинным и

    посылку (3) ложной, таким образом P(uo, wo, vo) обезопасен. Во всех других

    случаях нет изменений в P(uo, wo, vo).

    (

    Лемма 4.15 Для каждого uq и vo, L(uo, vo) –инвариант.

    Доказательство. Изначально Du0[uo] = 0 и Nbu[uo] = local. Для vo (uo ,

    изначально ndisu[w, vo] = N для всех w ( Neighu, и Du0[vo] = N и Nbu0[vo] =

    udef.

    Тип (1). Положим что u получил сообщение < mydist, v,d> от w. Если u( uo

    или v( vo нет переменных упомянутых изменениях L(uo, vo) . Если u = uo и v

    = vo значение ndisu[w, vo] меняется, но Du0 [vo] и Nbu0[vo]

    перевычисляется точно так как удовлетворяется L(vo, vo).

    Тип (2). Положим что канал uw отказал. Если u = uo или w = uo то Neighu0

    изменился, но опять Du0[vo] и Nbu0[vo] перевычисляются точно так как

    удовлетворяется L(uo, vo).

    Тип (3). Положим что добавлен канал uw . Если u = uo то изменилсяNeighu0

    добавлением w, но так как u устанавливает ndisu0[w, vo] в N это сохраняет

    L(uo, vo).

    4.3.2 Корректность алгоритма Netchange

    Должны быть доказаны два требования корректности.

    Теорема 4.16 Когда достигнута стабильная конфигурация, таблицы Nbu[v]

    удовлетворяют :

    (1) если u = v то Nbu[v] = local;

    (2) если путь от u до v( u существует то Nbu[v] = w, где w первый сосед

    u на кратчайшем пути от u до v;

    (3) если нет путь от u до v не существует то Nbu[v] = udef.

    Доказательство. Когда алгоритм прекращает работу, предикат stable

    добавляется к P(u,w,v) для всех u, v, и w, и это подразумевает что для

    всех u, v, и w

    up(u, w) ( ndisu[w, v] = Dw[v].

    (4.2)

    Применив также L(u, v) для всех u и v мы получим

    (0 если u ( v

    Du [v] = ( 1+ min Dw[v] если u( v ((w ( Neighu : Dw[v] < N -1

    (N w (Neigh u если u(v ((w ( Neighu :

    Dw[v]( N -1

    (4.3)

    которого достаточно для доказательства что Du[v] = d(u, v) если u и v в

    некотором связном компоненте сети, и Du[v] = N если u и v в различных

    связных компонентах.

    Во-первых покажем индукцией по d{u, v) что если u и v в некотором связном

    компоненте то Du[v]( d(u, v).

    Случай d(u, v) = 0: подразумевает u = v и следовательно Du[v] = 0.

    Случай d(u, v) = k +1: это подразумевает что существует узел w ( Neighu с

    d(w, v) = k. По индукции Du[v] ( k, которое по (4.3) подразумевает

    что Du[v] ( k + 1.

    Теперь покажем индуктивно по Du[v] что если Du[v] < N то существует путь

    между u и v и d(u, v) ( Du[v].

    Случай Du[v] = 0: Формула (4.3) подразумевает что Du[v] = 0 только для u =

    v, что дает пустой путь между u и v, и d(u, v) = 0.

    Случай Du[v] = k +1 < N : Формула (4.3) подразумевает что существует узел

    w ( Neighu с Dw[v] = k. По индукции существует путь между w и v и d(w, v)

    ( k, что подразумевает существование пути между u и v и d(u, v) < k+ 1.

    Следовательно что если u и v в некотором связном компоненте то Du[v] = d(u,

    v), иначе Du[v] = N. Это, Формула (4.2), и (u,v : L(u, v) и доказывает

    теорему о Nbu[v]. []

    Докажем что стабильная ситуация в конечном счете достигается если

    топологические изменения прекращаются, норм-функция в отношении stable

    определена. Определим, для конфигурации алгоритма (,

    ti = (число сообщений ) +

    (число упорядоченных пар u, v таких что Du[v] =

    i)

    и функцию f

    f(() = (to, t1,..., tN)

    f(() кортеж из (N + l) натуральных чисел, в некотором лексиграфическом

    порядке (обозначенном (l) . напомним что ((, (l) хорошо-обоснованное

    множество (Упражнение 2.5).

    Лемма 4.17 Обработка сообщения < mydist,.,. > уменьшает f.

    Доказательство. Пусть узел u с Du[v] = d1 получил сообщение < mydist, v,

    d2> , и после перевычислил новое значение Du[v] – d. Алгоритм

    подразумевает что d < di + 1.

    Случай d < d1: Пусть d = d1 + 1 что подразумевает что td2 уменьшилось на 1

    (и td1 следовательно), и только td с d > d1 увеличилось. Это подразумевает

    что значение f уменьшилось.

    Случай d = d1: Не новое сообщение < mydist, ., .> посланное u, и влияет

    только на f так что td2 уменьшилось на 1, т.о. значение f уменьшилось.

    Случай d > d1: Пусть td1 уменьшилось на 1 (и td2 следовательно), и только

    td с d > d1 увеличилось. Это подразумевает что значение f уменьшилось.

    []

    Теорема 4.18 Если топология сети остается неизменной после конечного

    числа топологических изменений, то алгоритм достигнет стабильной

    конфигурации за конечное число шагов.

    Доказательство. Если сетевая топология остается постоянной только

    обрабатывая сообщения которые имеют место, и, по предыдущей

    лемме, значение f уменьшается с каждым таким переходом. Это следует из

    хорошей обоснованности области f в которой может быть только конечное

    число таких переходов; следовательно алгоритм достигает стабильной

    конфигурации после конечного числа шагов. []

    4.3.3 Обсуждение алгоритма

    Формальные результаты правильности алгоритма, гарантирующие сходимость для

    исправления таблиц за конечное время после последнего топологического

    изменения, не очень хорошо показывают фактическое поведение алгоритма.

    Предикат stablе может быть ложным практически долгое время (а именно, если

    топологические изменения часты) и когда stablе ложен, ничто не известно о

    таблицы маршрутизации. Они могут содержать циклы или даже давать ошибочную

    информацию относительно достижимости узла назначения. Алгоритм поэтому

    может только применятся, где топологические изменения настолько редки, что

    время сходимости алгоритма является малым по сравнению с средним временем

    между топологических изменений. Тем более , потому что stablе -

    глобальное свойство, и устойчивые конфигурации алгоритма неразличимы от

    неустойчивых для узлов. Это означает, что узел никогда не знает, отражают

    ли таблицы маршрутизации правильно топологию сети, и не может отсрочить

    отправления пакетов данных , пока устойчивая конфигурация не достигнута.

    Асинхронная обработка уведомлений. Было этой части предположили что

    уведомления о топологических изменениях обрабатываются автоматически

    вместе с именением в единой транзакции. Обработка происходит на обоих

    сторонах удаленного или добавленного канал одновременно. Лампорт [Lam82]

    выполнил анализ мелких деталей и учел задержки в обработке этих

    уведомлений. Коммуникационный канал от w до u смоделирован объединением

    трех очередей.

    (1) OQwu , выходная очередь w,

    (2) TQwu , очередь сообщений (и пакетов данных) передаваемая

    (3) IQwu , входная очередь u.

    При нормальном функционировании канала, w посылает сообщение к u

    добавлением его в OQwu, сообщения двигаются от OQwu к TQwu и от TQwu к

    IQwu, и u получает их удаляя из IQwu. Когда канал отказывает сообщения в

    TQwu выбрасываются и сообщения в OQwu соответственно выбрасываются раньше

    чем добавились к TQwu. Сообщение < fail, w> становится в конец IQwu, и

    когда нормальное функционирование восстановилось сообщение

    также становится в конец IQwu. предикаты P(u, w, v) принимают слегка более

    сложную форму но алгоритм остается тот же самый.

    Маршрутизация по кротчайшему пути. Возможно означить вес каждого канала и

    модифицировать алгоритм так чтобы вычислять кратчайший путь вместо пути с

    минимальным количеством шагов. Процедура Recompute алгоритма Netchange

    использовать вес канала uw в вычислении оценки длины кратчайший путь

    через w если константу 1 заменить на wuw. Константа N в алгоритме должна

    быть заменена верхней границей диаметра сети.

    Довольно просто показать что когда модифицированный алгоритм достигнет

    стабильной конфигурации таблицы маршрутизации будут корректны и содержать

    оптимальный путь (все циклы в сети должны иметь положительный вес).

    Доказательство что алгоритм действительно достигает такого состояния

    требует более сложной нормфункции.

    Даже возможно расширить алгоритм для работы с изменяющимися весами каналов;

    реакция узла u на изменение веса канала – перевычисление Du[v] для v.

    Алгоритм был бы практическим, однако, только в ситуации когда среднее

    время изменений стоимостей каналов больше времени сходимости что не

    реально. В этих ситуациях должна алгоритм должен предпочесть гарантию

    свободы от циклов в течение сходимости, на пример алгоритм Мерлина-Сигалла.

    4.4 Маршрутизация с Компактными Таблицами маршрутизации

    Обсужденные алгоритмы маршрутизации требуют что бы каждый узел содержал

    таблицу маршрутизации с отдельной ссылкой для каждого возможного пункта

    назначения. Когда пакет передается через сеть эти таблицы используются

    каждом узле пути (исключая пункта назначения). В этой части рассматриваются

    некоторые организации таблиц маршрутизации которые хранение и поиск

    механизмов маршрутизации. Как эти таблицы маршрутизации могут быть

    вычислены распределенными алгоритмами здесь не рассматриваются. Для

    простоты представления положим что сеть связная.

    Стратегию уменьшения таблицы в каждом из трех механизмов маршрутизации,

    обсуждаемых в этой части, просто объяснить следующим образом. Если таблицы

    маршрутизации узла хранят выходящий канал для каждого пункта назначения

    отдельно, таблица маршрутизации имеет длину N; следовательно таблицы

    требуют ((N) бит, не важно как компактно выходящий канал закодирован для

    каждого пункта назначения. Теперь рассмотрим перестройку таблицы: таблица

    содержит для каждого канала узла ссылку говорящую какие пункты назначения

    должны быть смаршрутизированны через этот канал; смотри Рисунок 4.11.

    Таблица теперь имеет "длину" deg для узел с deg каналами; теперь

    компактность зависит от того как компактно множество пунктов назначения для

    каждого канала может быть представлено.

    [pic]

    Рисунок 4.11 Уменьшение размера таблицы маршрутизации.

    4.4.1 Схема разметки деревьев

    Первый метод компактной маршрутизации был предложен Санторо и Кхатибом

    [SK85]. Метод основан на пометке узлов целыми от 0 до N— I, таким образом

    чтобы множество пунктов назначения для каждого канала было интервалом.

    Пусть ZN обозначает множество {0, 1,..., N- 1}. В этой части все

    арифметические операции по модулю N, т.e., (N— 1) + 1( 0.

    Определение 4.19 Циклический интервал [a, b) в ZN – множество целых

    определенное как

    ( {a, a +1,..., b -1} если a lv то lw < Iu

    Доказательство. Во-первых, рассмотрим случай (uw ( lv. Узел w не сын u

    потому что в этом случае (uw = lw > lu > lv .Если uw ветвь то также lw =

    (uw < lv < lu. Если w отец u то lw < lu выполняется в любом случае. Во-

    вторых, рассмотрим случай когда (uw – наибольшая метка ребра в u, и нет

    метки (' ( lv (т.е., lv – нижняя граница нелинейного интервала). В этом

    случае ребро к отцу u не помечено 0, но имеет метку ku (потому что 0( lv, и

    нет метки (' ( lv). Метка ku – наибольшая метка в данном случае; ребро к

    сыну или ветви вниз w' имеет (uw’ = lw’ < ku, и ветвь к предком w' имеет

    (uw’ = lw’ < lu Таким образом w – отец u в данном случае, что подразумевает

    1w < lu. []

    Следующие две леммы относятся к случаю когда lu < lv. Мы выведем что

    каждый v ( T[u] или lv > ku, и в последнем случае ku < N имеет силу так

    что ребро к отцу u помечено ku.

    [pic]

    Рисунок 4.16 МАРШРУТИЗАЦИЯ ПАКЕТОВ ДЛЯ V В СХЕМЕ РАЗМЕТКИ ILS.

    Лемма 4.29 Если lu lu. Таким образом fv(w) < fv(u).

    Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.