Расширение карт маршрутизации и интенсивность потоков данных
Рассмотрим очень важное свойство матриц вида (4.4.2) для корректных СРКМ. Зафиксируем узел-получатель
Рассмотрим обычные РТМ и РКМ. Расширим РТМ и РКМ согласно (4.4.1) в следующем виде:
Назовем Рассмотрим узлы
Заметим, что отношение доминирования не транзитивно, т.е. из соотношений
не следует, что
Пусть эти таблицы заданы следующим образом:
Из (4.5.7) видно, что
Однако при этом
Будем говорить, что узел ak транзитивно доминирует над узлом ai по отношению к узлу aj (в контексте карты маршрутизации T), если существует последовательность узлов вида
такая, что
Обозначим такой тип доминирования следующим образом:
Рассмотрим несколько свойств, связанных с отношениями доминирования и транзитивного доминирования узлов ТКС. Лемма 4.5.1: Пусть задан орграф G(A,W,R), соответствующий некоторой ТКС, и на нем определена корректная РКМ T и её расширение если Докажем утверждение Леммы 4.5.1. Пусть доминирование узла ak над узлом ai проявляется при интенсивности потока xk в ak и xi в ai (будем рассматривать только этот один поток, направленный от ak к aj и проходящий через ai, для которого xi ≤ xk. Тогда такое доминирование будет проявляться при любой интенсивности 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.1. доказана. Из неё вытекает следующее следствие.
Следствие 4.5.1: В условиях леммы 4.5.1 для любого узла
Лемма 4.5.2: Пусть выполнены условия леммы 4.5.1, задан узел-получатель
Рассмотрим потоки, направленные к узлу-получателю 1) xi ≤ xk., (4.5.17) 2) Докажем, что из первого утверждения следует второе. Из леммы 4.5.1 следует, что
Запустим от узла ai поток к узлу-получателю aj, который будет протекать через ak с интенсивностью xi или, если xi =0, с любой интенсивностью меньшей, чем xk (далее под xi будем подразумевать эту интенсивность). Из узла ak запустим поток к aj с интенсивностью (xk – xi). Тогда интенсивность суммарного потока, протекающего через узел ak, будет равна xk, и этот поток будет проходить через am, минуя ai и не возвращаясь в ak, так как
Таким образом, справедливо второе утверждение леммы 4.5.2. Следствие первого утверждения из второго очевидно. Лемма 4.5.2. доказана. Лемма 4.5.3: В условиях леммы 4.5.1 справедливо следующее утверждение: любой узел
Докажем эту лемму методом от противного. Пусть существует такой узел
В соответствии со следствием 4.5.1 из леммы 4.5.2 без потери общности можно считать, что элементы этой последовательности обладают следующим свойством:
Рассмотрим три подряд идущих узла данной последовательности
Таким образом, справедлива следующая цепочка соотношений:
откуда следует, что Следствие 4.5.2: В условиях леммы 4.5.1 при фиксированном узле-получателе
Иными словами, согласно следствию 4.5.2 для любого узла-получателя
Доказательство этого следствия поведем методом от противного. Предположим, что такого узла нет. Тогда существует узел-получатель
Тогда можно построить последовательность вида (4.5.22) со свойством (4.5.23). Но из леммы 4.5.3 следует, что такой последовательности не существует. Поэтому сделанное предположение неверно, что доказывает справедливость следствия 4.5.2. Следствие 4.5.3: В условиях леммы 4.5.1 при фиксированном узле-получателе
Утверждение следствия 4.5.3 очевидно, так как в противном случае узел ak транзитивно доминировал бы над самим собой, что противоречит утверждению леммы 4.5.3. Зафиксируем узел-получатель
Тогда матрица доминирования будет выглядеть следующим образом:
Рассмотрим связь матрицы доминирования с отношениями доминирования узлов ТКС в форме импликации вида:
Из соотношения (4.5.31) следует эквивалентность следующих соотношений
Критерий корректности для РКМ можно сформулировать в виде следующей теоремы.
Теорема 4.5.5: Распределяющая карта маршрутизации T корректна тогда и только тогда, когда для любого узла-получателя
Докажем сначала необходимость. Пусть РКМ корректна. Зафиксируем узел-получатель
Тогда из (4.5.34) следует, что
а это противоречит утверждению леммы 4.5.3. Теперь докажем достаточность. Рассмотрим РКМ. Так как все прокладываемые этой картой маршруты будут заканчиваться в узле-получателе aj, то нам остается доказать, что все определяемые РКМ маршруты будут конечнозвенными. Предположим, что РКМ некорректна. Тогда будут существовать бесконечные маршруты, т.е., маршруты, содержащие циклы. В этом случае будут существовать узлы, транзитивно доминирующие сами над собой. Но из (4.5.33) в силу (4.5.32) следует, что для любой узел
Полученное противоречие доказывает корректность РКМ и справедливость теоремы 4.5.5.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|