Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Расширение карт маршрутизации и интенсивность потоков данных




Рассмотрим очень важное свойство матриц вида (4.4.2) для корректных СРКМ.

Зафиксируем узел-получатель и запустим из каждого узла в aj поток с соответствующей интенсивностью xi. Из (4.3.3) и (4.4.4) следует, что для того, чтобы определить, с какой интенсивностью совокупность этих потоков проходит через узлы ТКС, достаточно рассмотреть соответствующие элементы следующего вектора “интенсивностей”:

. (4.5.1)

Рассмотрим обычные РТМ и РКМ. Расширим РТМ и РКМ согласно (4.4.1) в следующем виде:

, (4.5.2)

. (4.5.3)

Назовем расширением карты маршрутизации T. Заметим, что такое расширение РКМ не приведет к изменению в распределении информационных потоков в ТКС.

Рассмотрим узлы и зафиксируем узел-получатель . Будем говорить, что узел ak доминирует над узлом ai по отношению к узлу aj (в контексте карты маршрутизации T), если при управлении потоками данных, задаваемом РКМ T, существует такая совокупность потоков данных, при которой поток данных, направленный к узлу-получателю aj узлом ak, будет протекать через узел ai. Обозначим это отношение доминирования соотношением

. (4.5.4)

Заметим, что отношение доминирования не транзитивно, т.е. из соотношений

(4.5.5)

не следует, что

. (4.5.6)

В качестве примера рассмотрим граф, соответствующий некоторой ТКС, приведенный на рисунке 4.5.1. Пусть для него задана РКМ T. Рассмотрим таблицы маршрутизации из её расширения для узла-получателя a5=f

 

Пусть эти таблицы заданы следующим образом:

 

(4.5.7)

Из (4.5.7) видно, что

и . (4.5.8)

Однако при этом

. (4.5.9)

Будем говорить, что узел ak транзитивно доминирует над узлом ai по отношению к узлу aj (в контексте карты маршрутизации T), если существует последовательность узлов вида

, (4.5.10)

такая, что , , и для любых справедливо соотношение

. (4.5.11)

Обозначим такой тип доминирования следующим образом:

. (4.5.12)

Рассмотрим несколько свойств, связанных с отношениями доминирования и транзитивного доминирования узлов ТКС.

Лемма 4.5.1: Пусть задан орграф G(A,W,R), соответствующий некоторой ТКС, и на нем определена корректная РКМ T и её расширение . Тогда для любого узла-получателя и пары отличных от него узлов справедлива импликация вида:

если , то . (4.5.13)

Докажем утверждение Леммы 4.5.1. Пусть доминирование узла ak над узлом ai проявляется при интенсивности потока xk в ak и xi в ai (будем рассматривать только этот один поток, направленный от ak к aj и проходящий через ai, для которого xixk. Тогда такое доминирование будет проявляться при любой интенсивности x>xi. в узле ai Это происходит в силу того, что всегда можно создать поток данных, направленный от ai к aj. Заметим, что любой поток от узла ai к узлу-получателю aj с интенсивностью x≥xi не может проходить через узел ak, поскольку в этом случае появился бы циклический маршрут, что соответствовало бы существованию бесконечного маршрута и противоречило бы условию корректности РКМ.

Теперь докажем, что любой поток от узла ai к узлу aj с интенсивностью x<xi не будет проходить через узел ak. Действительно, если это не так, то такой поток с интенсивностью меньшей, чем xi, будет протекать через ak с интенсивностью, не превосходящей xi, и, следовательно, не превосходящей xk. Тогда можно создать новый поток от ak к aj с такой интенсивностью, чтобы суммарная интенсивность потоков на узле ak была равна xk. Оба эти потока будут проходить через ai, что приведет к появлению циклических, а, значит, бесконечных маршрутов, что противоречит условию корректности РКМ. Таким образом, поток любой интенсивности, направленный от узла ai к узлу aj через ak протекать не может, и, следовательно,

. (4.5.14)

Лемма 4.5.1. доказана. Из неё вытекает следующее следствие.

Следствие 4.5.1: В условиях леммы 4.5.1 для любого узла , отличного от узла-получателя, справедливо следующее соотношение:

. (4.5.15)

Лемма 4.5.2: Пусть выполнены условия леммы 4.5.1, задан узел-получатель и существуют три узла такие, что

, а (т.е., ). (4.5.16)

Рассмотрим потоки, направленные к узлу-получателю от узлов ai и ak. Пусть максимальная интенсивность таких потоков от ak, при которой они будут протекать через узел am, равна xk (если верхнего ограничения нет, то полагаем, что xk = ∞), а минимальная положительная интенсивность, с которой проходят через ak потоки от ai равна xi (если минимума нет, то в качестве значения xi принимаем инфимум положительных значений). Тогда, следующие утверждения равносильны:

1) xi xk., (4.5.17)

2) . (4.5.18)

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

и . (4.5.19)

Запустим от узла ai поток к узлу-получателю aj, который будет протекать через ak с интенсивностью xi или, если xi=0, с любой интенсивностью меньшей, чем xk (далее под xi будем подразумевать эту интенсивность). Из узла ak запустим поток к aj с интенсивностью (xk xi). Тогда интенсивность суммарного потока, протекающего через узел ak, будет равна xk, и этот поток будет проходить через am, минуя ai и не возвращаясь в ak, так как

и . (4.5.20)

Таким образом, справедливо второе утверждение леммы 4.5.2.

Следствие первого утверждения из второго очевидно.

Лемма 4.5.2. доказана.

Лемма 4.5.3: В условиях леммы 4.5.1 справедливо следующее утверждение: любой узел , выбранный при фиксированном узле-получателе , не может транзитивно доминировать сам над собой, т.е.

. (4.5.21)

Докажем эту лемму методом от противного. Пусть существует такой узел , для которого имеется циклическая последовательность узлов , доминирующих друг над другом, т.е.

. (4.5.22)

В соответствии со следствием 4.5.1 из леммы 4.5.2 без потери общности можно считать, что элементы этой последовательности обладают следующим свойством:

 

. (4.5.23)

Рассмотрим три подряд идущих узла данной последовательности . Пусть максимальная интенсивность потоков от узла к узлу-получателю, при которой он будет протекать через узел , равна (если верхнего ограничения нет, то полагаем, что ), а минимальная положительная интенсивность, с которой через узел проходят потоки от равна (если минимума нет, то в качестве значения принимаем инфимум положительных значений). Тогда из леммы 4.5.2 следует, что . В то же время, нетрудно убедиться, что .

Таким образом, справедлива следующая цепочка соотношений:

 

. (4.5.24)

откуда следует, что . Получили противоречие, из которого следует справедливость леммы 4.4.3.

Следствие 4.5.2: В условиях леммы 4.5.1 при фиксированном узле-получателе существует отличный от него узел такой, что для любого узла , отличного от aj и ai, справедливо сочетание

. (4.5.25)

Иными словами, согласно следствию 4.5.2 для любого узла-получателя существует отличный от него узел такой, что при любой интенсивности x>0 справедливо уравнение

. (4.5.26)

Доказательство этого следствия поведем методом от противного. Предположим, что такого узла нет. Тогда существует узел-получатель такой, что для любого отличного от него узла существует узел такой, что

. (4.5.27)

Тогда можно построить последовательность вида (4.5.22) со свойством (4.5.23). Но из леммы 4.5.3 следует, что такой последовательности не существует. Поэтому сделанное предположение неверно, что доказывает справедливость следствия 4.5.2.

Следствие 4.5.3: В условиях леммы 4.5.1 при фиксированном узле-получателе справедливо следующее утверждение: если узел транзитивно доминирует над узлом , то ai не может доминировать над ak, т.е.,

. (4.5.28)

 

Утверждение следствия 4.5.3 очевидно, так как в противном случае узел ak транзитивно доминировал бы над самим собой, что противоречит утверждению леммы 4.5.3.

Зафиксируем узел-получатель . Построим для него матрицу доминирования Q(j). Рассмотрим расширение РКМ T. Каждой расширенной РТМ сопоставим вектор с компонентами

(4.5.29)

Тогда матрица доминирования будет выглядеть следующим образом:

 

. (4.5.30)

 

Рассмотрим связь матрицы доминирования с отношениями доминирования узлов ТКС в форме импликации вида:

. (4.5.31)

Из соотношения (4.5.31) следует эквивалентность следующих соотношений

. (4.5.32)

Критерий корректности для РКМ можно сформулировать в виде следующей теоремы.

 

Теорема 4.5.5: Распределяющая карта маршрутизации T корректна тогда и только тогда, когда для любого узла-получателя верно, что его матрица доминирования Q(j) удовлетворяет следующему требованию:

(4.5.33)

Докажем сначала необходимость. Пусть РКМ корректна. Зафиксируем узел-получатель . Предположим, что существует число k такое, что

. (4.5.34)

Тогда из (4.5.34) следует, что

, (4.5.35)

а это противоречит утверждению леммы 4.5.3.

Теперь докажем достаточность. Рассмотрим РКМ. Так как все прокладываемые этой картой маршруты будут заканчиваться в узле-получателе aj, то нам остается доказать, что все определяемые РКМ маршруты будут конечнозвенными.

Предположим, что РКМ некорректна. Тогда будут существовать бесконечные маршруты, т.е., маршруты, содержащие циклы. В этом случае будут существовать узлы, транзитивно доминирующие сами над собой. Но из (4.5.33) в силу (4.5.32) следует, что для любой узел не может транзитивно доминировать сам над собой, т.е.

. (4.5.36)

Полученное противоречие доказывает корректность РКМ и справедливость теоремы 4.5.5.

 





Воспользуйтесь поиском по сайту:



©2015- 2022 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.