Содержание к диссертации
ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ 5
ВВЕДЕНИЕ 10
1 ПРОБЛЕМЫ ОРГАНИЗАЦИИ ЭФФЕКТИВНОГО ФУНК
ЦИОНИРОВАНИЯ СЕТИ ПАКЕТНОЙ КОММУТАЦИИ:
АНАЛИТИЧЕСКИЙ ОБЗОР И ВЫБОР НАПРАВЛЕНИЙ
РАБОТ 16
Логическая организация вычислительной сети ... 16
Операционные характеристики транспортной системы вычислительной сети 19
Система моделей функционирования сети передачи данных 20
Анализ моделей сетевых топологических структур . 25
Выводы о направлениях работ 33
2 ЗАМКНУТЫЕ МОДЕЛИ ЗВЕНА ПЕРЕДАЧИ ДАННЫХ 36
Структура линейного протокола 36
Анализ стартстопной управляющей процедуры ... 39
Модели нормальных процедур 41
Модели асинхронных процедур 44
Оптимизация сетевых параметров 59
Оценивание оптимальной длины кадра 60
Оценивание оптимальной ширины окна .... 74
Совместный выбор сетевых параметров .... 79
Управление шириной окна в условиях нестационарного характера искажений 83
2.6 Выводы 85
3 ОТКРЫТЫЕ МОДЕЛИ ЗВЕНА ПЕРЕДАЧИ ДАННЫХ
(ВЛИЯНИЕ БЛОКИРОВОК БУФЕРНОЙ ПАМЯТИ НА
ПРОИЗВОДИТЕЛЬНОСТЬ ЛИНЕЙНОГО ПРОТОКОЛА) 87
Дискретная модель фрагмента сети 88
Анализ операционных характеристик стартстопного протокола 91
Сравнение дискретной и непрерывной моделей старт-стопного протокола 95
Оптимизация длины кадра 101
Модели синхронного конвейерного протокола .... 103
Анализ управляющей процедуры в режиме группового отказа 106
Анализ управляющей процедуры в режиме селективного отказа 112
3.6 Выводы 119
ОТКРЫТЫЕ МОДЕЛИ МНОГОЗВЕННОГО ТРАКТА
ПЕРЕДАЧИ ДАННЫХ (ВЛИЯНИЕ БЛОКИРОВОК БУ
ФЕРНОЙ ПАМЯТИ НА ПРОИЗВОДИТЕЛЬНОСТЬ СКВОЗ
НОГО СОЕДИНЕНИЯ) 121
Модель тракта в виде открытой сети СМО 122
Анализ трехзвенного тракта 123
Анализ тракта длины D > 4 131
Декомпозиционный метод расчета пропускной способности тракта передачи данных 142
Выводы 147
ДЕТЕРМИНИРОВАННЫЕ КОНВЕЙЕРНЫЕ МОДЕЛИ МНОГОЗВЕННОГО ТРАКТА ПЕРЕДАЧИ ДАННЫХ 148
Структурные особенности транспортного уровня управления сетью 148
Оптимизация задержки абонентских сообщений в сети с низкой нагрузкой 151
Модель ненагруженного виртуального соединения 151
Оптимальное разбиение сообщения на пакеты 154
Выбор рационального размера кадра 161
Учет реальных свойств каналов связи 165
5.3 Совместная оптимизация сетевых параметров по
критерию системы и критерию пользователя .... 168
Проблемная ситуация 168
Метод выбора длины кадра и ширины окна . 169
Динамическое управление сетевыми параметрами 174
5.4 Анализ задержки в нагруженном виртуальном со
единении 177
Модели виртуального соединения с однородным трафиком 177
Модели виртуального соединения с неоднородным трафиком 188
5.5 Выводы 202
СТОХАСТИЧЕСКИЕ МОДЕЛИ КОНВЕЙЕРНЫХ МЕ
ХАНИЗМОВ ПРОЦЕССА ПЕРЕНОСА ДАННЫХ В ВИР
ТУАЛЬНОМ СОЕДИНЕНИИ (ВЛИЯНИЕ ДЛИТЕЛЬНО
СТИ СКВОЗНОГО ТАЙМ-АУТА НА ВЕРОЯТНОСТНО-
ВРЕМЕННЫЕ ХАРАКТЕРИСТИКИ МНОГОЗВЕННО
ГО ТРАКТА) 204
Вероятностно-конвейерная интерпретация многозвенного виртуального соединения 205
Аналитическая вычислимость сумм показательно-степенных функций 206
Анализ переноса данных при сквозном квитировании информационными пакетами 210
Функция вероятностей времени доставки пакета 210
Функция распределения времени доставки пакета 212
Среднее время доведения пакета до адресата . 213
Анализ сквозной задержки 214
6.4 Анализ переноса данных при сквозном квитировании
служебными пакетами 216
Характеристики передачи мультипакетного сообщения по однозвенному виртуальному каналу 218
Характеристики передачи одиночного пакета
по многозвенному виртуальному каналу .... 223
6.5 Анализ передачи мультипакетного сообщения по
многозвенному виртуальному каналу 228
Вероятностно-временные характеристики процесса доставки сообщения адресату 228
Анализ сквозных операционных показателей передачи сообщения 235
Выбор длительности тайм-аута ожидания сквозной квитанции 240
Выводы 242
7 МЕТОДИКА ИНЖЕНЕРНОГО РАСЧЕТА ПОКАЗАТЕЛЕЙ ПРОИЗВОДИТЕЛЬНОСТИ СЕТЕВЫХ СТРУКТУР И ОПТИМИЗАЦИИ ПРОТОКОЛЬНЫХ ПАРАМЕТРОВ 245
Введение 245
Условия предпочтения критериев оптимизации . . . 246
Выбор длины кадра и ширины окна по критерию пропускной способности 249
Выбор длины кадра по критерию средней задержки сообщений 255
Композиционный метод расчета сетевых параметров 259
Расчет длительности сквозного тайм-аута 261
Принципы построения трактов передачи данных и генерации сетевого трафика приложениями 263
Расчет операционных характеристик сетевых структур 265
Резюме 272
ЗАКЛЮЧЕНИЕ 274
ЛИТЕРАТУРА 278
ПРИЛОЖЕНИЕ. Акты внедрения и использования результа
тов работы 299
ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ
Ат — относительное время незанятости канала связи
звена передачи данных (Ат = Tm/t);
а — коэффициент увеличения длины кадра в
канале связи из — за бит(байт) — стаф финга
или применения асинхронной аппаратуры связи;
Б — средняя задержка сообщений в "узких"''' звеньях
виртуальных соединений неоднородной сети;
П — вероятность повторной передачи кадра;
В — размер абонентского сообщения;
Bj — средний размер сообщений
j — го инф ормационного потока;
В — средний размер сообщений, передаваемых по сети;
С — физическая скорость передачи по каналу связи;
Ccc(L,m) — пропускная способность управляющей процедуры
стартстопного протокола; Снс(Ь,ы,т) — пропускная способность нормальной процедуры
обмена в режиме селективного отказа; Снг(Ь,си,т) — пропускная способность нормальной процедуры
обмена в режиме группового отказа; Cac(L,co) — пропускная способность асинхронной процедуры
обмена в режиме селективного отказа;
CAr{L,uj) — пропускная способность асинхронной процедуры
обмена в режиме группового отказа;
D — длина виртуального соединения, выраженная в
количестве участков переприема;
D — средняя длина виртуальных соединий сети;
F — достоверность передачи данных в
инф ормационном канале;
объем пакетной и кадровой служебной инф ормации;
объем кадровой служебной инф ормации,
не хранящейся в буфере;
количество бит в буфере, необходимых для
организации очереди в виде связного списка буферов;
количество виртуальных соединений сети;
количество буферов узла коммутации, выделенных
для хранения очереди пакетов к каналу связи;
количество межузловых соединений сети;
количество пакетов в очереди к виртуальному
каналу;
число пакетов, адресованных в узел — получатель
j — го звена виртуального канала;
число пакетов і — го типа в очереди к
виртуальному каналу;
размер очереди на d— ом участке виртуального
канала;
число пакетов из очереди d— го звена, адресованных
в узел — получатель j — го звена виртуального
канала;
вектор параметров kj(d);
число пакетов г — го типа в очереди d— го звена
виртуального канала;
вектор параметров k^(d);
размер кадра;
количество типов пакетов;
количество фрагментов (пакетов) в
сообщении пользователя;
среднее время доведения N — пакетного сообщения
до адресата по тракту длины D при длительности
тайм — аута S;
функция распределения времени сквозной передачи
N — пакетного сообщения в тракте длины D;
функция вероятностей времени сквозной передачи
N — пакетного сообщения в тракте длины D;
вероятность блокировки узла — получателя
звена передачи данных;
Rn — вероятность искажения кадра в прямом канале
связи;
Rom — вероятность искажения кадра в обратном
канале связи;
гп — вероятность независимой битовой ошибки в
прямом канале связи;
г0 — вероятность независимой битовой ошибки в
обратном канале связи; S>N + 2D — 1 — размер тайм — аута, выраженный в
длительностях Т;
S(N,D,S) — среднее время ожидания сквозной квитанции
на N — пакетное сообщение в тракте длины D
при длительности тайм — аута S;
T = mt + Tm — длительность цикла передачи инф ормационного
кадра получателю и ожидания ответной
квитанции;
Тт — время незанятости канала связи;
T(D,N,k) — задержка N —пакетного сообщения в
виртуальном соединении длины D с общим
числом пакетов в очереди перед сообщением к; Td(K\, ... ,Kd-\) — задержка пакета в виртуальном соединении
длины D с ограниченными буф ерными
накопителями транзитных узлов;
Т(К) — средняя задержка кадра в звене передачи
данных;
T(N,D,S) — средняя сквозная задержка N — пакетного
сообщения в тракте длины D при
длительности тайм — аута S;
t = aL/C — время вывода инф ормационного кадра в линию
связи;
U — среднее время передачи бита данных по
виртуальным соединениям сети без "узких"
звеньев;
V — объем оперативной памяти узла коммутации,
выделенной под буферы для одного направления
передачи;
Z^r(u!,m) — коэф фициент использования инф ормационногс
канала, управляемого асинхронной процедурой
обмена в режиме группового отказа;
%Ас(ш,т) — коэффициент использования инф ормационного
канала, управляемого асинхронной процедурой
обмена в режиме селективного отказа;
Zffr(u,m) — коэф фициент использования инф ормационного
канала, управляемого нормальной процедурой
обмена в режиме группового отказа;
Zffc{uim) — коэф фициент использования инф ормационного
канала, управляемого нормальной процедурой
обмена в режиме селективного отказа; Zd(K\,...,Kd-\) — пропускная способность тракта длины D с
ограниченными накопителями в транзитных
узлах;
zr(u,K) — пропускная способность конвейерного
протокола в режиме группового отказа при
ограниченном буф ерном накопителе
узла — получателя;
zc(u,K) — пропускная способность конвейерного
протокола в режиме селективного отказа при
ограниченном буф ерном накопителе
узла — получателя;
a>j — доля общесетевого трафика, переносимая j — м
виртуальным соединением;
Pi — доля общесетевого трафика, проходящая по
г — му межузловому соединению;
Td — время полного цикла передачи пакета по d — му
звену виртуального соединения;
т^г> — время полного цикла передачи г — го пакета
по отдельному звену однородного
виртуального канала;
Td(n) — время полного цикла передачи п — го пакета
по d — му звену неоднородного
виртуального канала;
и — ширина окна.
Введение к работе
Интенсивный рост потребностей в распределенных прикладных вычислениях и информационном сервисе стимулировал широкое внедрение корпоративных и территориальных вычислительных сетей, основанных на принципах пакетной коммутации, в управленческую деятельность предприятий и отраслей народного хозяйства, в научные исследования, обучение, здравоохранение, межкорпоративные бизнес-процессы и т.д. [29, 39, 40, 62, 85, 118, 189, 192]. Повышение темпов деловой активности и необходимость снижения сроков документооборота выдвинуло в ряд важнейших задач информатизации общества формирование единого информационного пространства и стимулировало внедрение информационных сетей в традиционную почтовую связь, в результате чего появился новый вид связи - электронная почта [39, 62, 67, 85]. Устойчивой тенденцией становится интенсивное внедрение в управленческую деятельность организаций и фирм распределенных систем автоматизации деловых процессов, электронного документооборота, систем электронной комерче-ской деятельности, инструментальных средств интеграции информационной деятельности предприятий в информационное пространство сообщества Internet [40, 62, 67, 71].
Информационно-вычислительные сети, являясь основой современной индустрии обработки информации [29, 71, 87, 96, 118, 189, 192], предъявляют высокие требования к эффективному использованию средств связи и характеристикам обслуживания сетевых абонентов. В связи с этим одной из важнейших проблем, которую приходится решать при практическом воплощении сетевых проектов и их эксплуатационном сопровождении, является проблема адекватного описания процессов информационного переноса в сети и ее отдельных элементах в формальных моделях, используемых при администрировании и организации эффективной работы распределенных информационных систем в различных условиях функционирования. Возникающие здесь практические задачи стимулируют развитие методов описания процессов передачи данных разноуровневыми протоколами и мо-
делей информационно-вычислительных сетей.
Важнейшим показателем потенциальных возможностей связных ресурсов сети является пропускная способность межузловых соединений, управляемых различными реальными протоколами, а наиболее значимой характеристикой обслуживания абонентов - время доставки пользовательских данных удаленным сервисным службам по виртуальным соединениям и задержка ответных сообщений.
Применяемые в настоящее время модели процессов обмена в межузловых и виртуальных соединениях являются недостаточно адекватными. Кроме того, анализ существующих подходов к решению задачи оптимизации сетевых параметров показывает, что ряд существенных черт, факторов и механизмов, определяющих эффективность функционирования сети, необоснованно упрощается либо вообще игнорируется. Таким образом, возникает потребность в более совершенных моделях процессов информационного переноса и методах выбора параметров, разработка которых составляет основное содержание данной работы.
Диссертационнаая работа выполнялась в соответствии с тематическими планами нучно-исследовательских работ Томского государственного университета а также в рамках целевой комплексной научно-технической программы О.Ц.027(задание 05.31), утвержленной постановлением ГКНТ, Госплана СССР и АН СССР от 12.12.80 N 474/250/132 (N гос. регистрации 01812014091).
Целью настоящей работы является построение и исследование моделей процесса передачи протокольных блоков данных на различных уровнях сетевой архитектуры, разработка принципов построения сетевых трактов передачи данных и инженерных методов выбора протокольных параметров по критериям пропускной способности, средней сетевой задержки, их композиции и вероятностным показателям.
Методы исследования. При выполнении диссертационной работы использовались методы теории вероятностей, теории марковских цепей, теории массового обслуживания, теории расписаний.
Научная новизна.
В работе разработано два класса моделей процесса информационного переноса в сетевых структурах, отличающихся учетом существенно дискретного характера функционирования управляющих протоколов:
- потоковые, позволяющие исследовать предельные возможности магистралей передачи данных, управляемых протоколами канального и сетевого уровня, и оптимизировать сетевую структуру и протокольные пара-
метры по нагрузочному критерию;
- конвейерные, дающие возможность изучать влияние структурных неоднородностей передающей среды и потока данных на вероятностно-временные характеристики качества функционирования протокола транспортного уровня и синтезировать протокольные параметры по критерию, ориентированному на потребительские показатели.
Практическая ценность.
На основе проведенных исследований разработаны " Методические указания по инженерному расчету показателей производительности сетевых структур и оптимизации протокольных параметров" в различных эксплуатационных условиях. Самостоятельную практическую значимость имеют предложенные модели фрагментов сети с коммутацией пакетов, позволяющие проводить сопоставительный анализ управляющих протоколов и расчет операционных характеристик отдельных звеньев передачи данных, многозвенных виртуальных каналов и средние показатели эффективности функционирования всей сети.
Внедрение результатов работы.
"Методические указания по инженерному расчету показателей производительности сетевых структур и оптимизации протокольных параметров" внедрены в компьютерной фирме " Сибирские Цифровые Приборы", Куйбышевском авиационном институте - головной организации по комплексной научно-технической программе "Автоматизация научных исследований", Центре автоматизации и метрологии АН МССР. Инженерная методика передана также для использования на предприятие п/я А-3650.
Кроме того, материалы исследований используются в учебном процессе при чтении курсов лекций "Вычислительные системы и сети", "Принципы организации многопроцессорных комплексов" по специальности 22.04.00 "Программное обеспечение вычислительной техники и автоматизированных систем" в Томском государственном университете и при выполнении курсовых и дипломных работ студентов.
На защиту автором выносятся следующие положения.
Модели и методы расчета показателей производительности различных операционных режимов конвейерных протоколов управления межузловым соединением синхронного и асинхронного типа, учитывающие факторы искажений в прямом и обратном каналах связи звена передачи данных и фактор блокировок ограниченной буферной памяти узла-получателя.
Потоковые модели и результаты исследований операционных характеристик многозвенных трактов передачи данных с конечными обьемами
буферных накопителей в транзитных узлах, учитывающие существенно дискретный характер информационного переноса в виртуальном канале и описываемые открытыми сетями СМО с дискретным временем.
3. Детерминированные конвейерные модели и методы расчета показа
теля задержки мультипакетных сообщений в многозвенных неоднородных
виртуальных каналах с различной структурой сетевого трафика, учиты
вающие трубопроводный (конвейерный) эффект одновременного переноса
различных фрагментов сообщений на различных участках соединительно
го пути.
4. Стохастические конвейерные модели и результаты исследований
вероятностно-временных характеристик сквозного информационного пере
носа в многозвенном тракте, учитывающие влияние длительности сквоз
ного тайм-аута ожидания квитанции транспортного протокола и фактора
искажений в отдельных звеньях на показатели быстродействия виртуаль
ного соединения.
5. Методы и алгоритмы расчета сетевых и протокольных параметров
информационно-вычислительных сетей по критериям пропускной способ
ности межузловых и многозвенных соединений, сквозной задержки або
нентских сообщений, композиционному критерию оптимальности и веро
ятностным показателям эффективности функционирования сети.
Апробация работы и публикации.
Основные результаты диссертационной работы докладывались и обсуждались на следующих научно-технических форумах.
IV, V, VI Всесозных конференциях "Вычислительные сети коммутации пакетов" (Рига, 1985, 1987, 1989).
Международном семинаре "Территориальные информационные сети" (Рига, 1991).
XIII, XV, XVII Всесоюзных школах-семинарах по вычислительным сетям (Алма-Ата, 1988,1992; Винница, 1991).
II Всесоюзном семинаре "Перспективы развития вычислительных систем" (Рига, 1985).
I, II, IV, V, VII Белорусских школах-семинарах по теории массового обслуживания (Гродно, 1985,1988,1989,1991; Гомель, 1986).
Республиканской научно-технической школе-семинаре "Анализ и синтез систем массового обслуживания и сетей ЭВМ" (Одесса, 1990).
Республиканском научно-техническом семинаре "Совершенствование методов исследования потоков событий и систем массового обслуживания" (Киев, 1989).
II Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 1996).
IV,V Всероссийских семинарах "Нейроинформатика и ее приложения" (Красноярск, 1996,1997).
IX Международном симпозиуме по непараметрическим и робастным методам в кибернетике (Красноярск, 1997).
По результатам выполненных исследований опубликовано 34 печатные работы [134]-[167].
Структура диссертации.
Работа состоит из введения, семи глав, заключения, списка литературы и приложения, включающего документы о внедрении.
Проведенный в первой главе аналитический обзор результатов, достигнутых в моделировании сетевых структур, позволил установить основные направления исследований. Выявленные направления в теоретическом плане развиваются в пяти дальнейших главах.
Во второй главе предложены модели межузлового соединения, учитывающие влияние искажений потока протокольных блоков данных в прямом и обратном каналах связи на операционные характеристики звена передачи данных. В рамках предложенных моделей протоколов управления информационным каналом получены аналитические оценки оптимальных по критерию пропускной способности межузловых соединений значений длины кадра и ширины окна. Результаты этой главы опубликованы в работах автора [134, 138, 142, 143, 144, 145, 153].
В третьей главе построены модели двухзвенного сетевого фрагмента, позволяющие исследовать влияние фактора блокировок буферной памяти транзитного узла коммутации и протокольных параметров на производительность стартстопного и конвейерного протоколов управления звеном передачи данных. Материалы данной главы изложены в работах автора [137, 143, 144, 152, 162, 166].
Четвертая глава посвящена разработке моделей многозвенного тракта передачи данных, дающих возможность анализировать влияние качества каналов связи и емкости буферных накопителей транзитных узлов коммутации на операционные показатели протокола сетевого уровня. Полученные в этой главе результаты опубликованы в работах автора [137, 152, 159, 161, 162, 166].
В пятой главе исследуется процесс передачи потока мультипа-кетных сообщений по неоднородным многозвенным виртуальным соединениям на транспортном уровне управления сетью. На основе модели данного
процесса, отличающейся учетом конвейерного эффекта [65, 211], решается задача оптимальной фрагментации абонентских сообщений на пакеты данных. Здесь же развивается метод определения длины кадра и ширины окна линейного уровня неоднородной сети передачи данных, совместно учитывающий требования держателей средств связи к пропускной способности межузловых соединений и требования пользователей к задержке абонентских сообщений. Рассмотренные в этой главе вопросы нашли отражение в работах автора [135, 136, 139, 142, 146, 148, 150, 154, 155, 167].
Шестая глава посвящена разработке моделей информационного переноса в виде стохастического конвейера, позволяющих исследовать влияние длительности тайм-аута ожидания квитанции транспортного уровня на сквозную задержку сообщений в виртуальном канале. Предложена процедура синтеза длительности сквозного тайм-аута, обеспечивающей заданный уровень вероятности повторной передачи данных. Результаты, полученные в данной главе, изложены в работах автора [139, 140, 141, 147, 149, 151, 156, 157, 158, 159, 160, 161, 163, 164, 165].
В седьмой главе дается краткое описание основных положений инженерной методики расчета операционных характеристик, сетевых и протокольных параметров информационно-вычислительных сетей, составленной по результатам проведенных автором исследований. Методологические вопросы расчета показателей эффективности функционирования сети и параметрической оптимизации протоколов с различной степенью подробности затронуты в большинстве работ автора и отчете [92].
