Теоретические основы проектирования компьютерных сетей - Вишневский В.М.

Название: Теоретические основы проектирования компьютерных сетей.
Автор: Вишневский В.М.
2003.
   В монографии рассматриваются методы анализа и синтеза компьютерных сетей. Приводятся точные и приближенные математические методы исследования систем и сетей очередей, а также эффективные вычислительные алгоритмы расчета таких сете. С позиций теорий сетей очередей описываются различные аспекты проектирования компьютерных сетей. Рассматриваются стохастические сетевые модели анализа задержек, управления потоками и расчета узлов коммутации пакетов. Систематизируются и исследуются алгоритмы выбора оптимальных маршрутов в сетях пакетной коммутации и динамической маршрутизации в ATM сетях. Дается описание комбинаторного алгоритма синтеза топологической структуры корпоративных компьютерных сетей. Приводятся новые результаты в области проектирования и оценки производительности беспроводных компьютерных сетей под управлением протокола IEEE 802.11.
   Происходящие в мире процессы развития инфокоммуникаций стали объективным фактором движения мирового сообщества к созданию глобального информационного общества. Фактически речь идет о развертывании очередной промышленной революции, получившей название «информационной». Международная интеграция информационных ресурсов и развитой инфраструктуры компьютерных сетей позволяет осуществлять взаимодействие любых пользователей для получения любого вида информации в реальном масштабе времени вне зависимости от расстояния и используемых средств вычислительной техники.
Содержание
Предисловие
Введение
1 Математические методы теории очередей
1.1 Общие положения и определения
1.2 Входящий поток, время обслуживания
1.3 Марковские случайные процессы
1.3.1 Процессы гибели и размножения
1.3.2 Метод диаграмм интенсивностей переходов
1.3.3 Цепи Маркова с дискретным временем
1.4 Преобразования Лапласа и Лапласа - Стилтьеса. Производящая функция
1.5 Однолинейные марковские системы массового обслуживания
1.5.1 Система типа М|М|1
1.5.2 Система типа М|М|1|n
1.5.3 Система с конечным числом источников
1.6 Полумарковские однолинейные системы и методы их анализа
1.6.1 Метод вложенных цепей Маркова в приложении для системы M|G|1
1.6.2 Метод вложенных цепей Маркова в приложении для системы GI\M\1
1.6.3 Метод введения дополнительной переменной
1.6.4 Метод введения дополнительного события
1.7 Многолинейные системы массового обслуживания
1.7.1 Системы М\М\п и М|М|n|m
1.7.2 Многоканальные системы без буфера для ожидания
1.7.3 Система М\М
1.7.4 Система M|G|1 с дисциплиной равномерного рас пределения процессора и дисциплиной LIFO с прерыванием обслуживания
1.8 Приоритетные системы массового обслуживания
1.9 Многофазные системы
1.10 Перспективные направления исследований в теории очередей
1.10.1 Исследование систем матричными методами
1.10.2 СМО с повторными вызовами
1.10.3 Другие направления исследований
2 Аналитические методы теории сетей очередей
2.1 Основные понятия и определения
2.1.1 Маршрутная матрица и потоки в сетях
2.1.2 Другие определения
2.2 Однородные экспоненциальные сети
2.2.1 Уравнения глобального баланса для замкнутых цепей
2.2.2 Вид решения в мультипликативной форме
2.2.3 Сети, зависящие от нагрузки
2.2.4 Показатели качества функционирования однородных сетей
2.3 Сети массового обслуживания с несколькими классами сообщений
2.3.1 Описание смешанной сети
2.3.2 Теорема ВСМР
2.3.3 Открытые сети МО с несколькими классами
2.4 Итерационный метод анализа средних значений
2.4.1 Общее описание метода
2.4.2 Однородная замкнутая сеть МО, зависящая от нагрузки
2.5 Оптимизация замкнутых однородных сетей массового обслуживания
2.5.1 Некоторые свойства характеристик замкнутых однородных сетей МО
2.5.2 Постановка и решение задачи оптимизации
2.5.3 Пример расчета
3 Вычислительные алгоритмы (методы вычислений характеристик сетей очередей
3.1 Алгоритмы вычисления характеристик однородных замкнутых экспоненциальных сетей массового обслуживания
3.1.1 Метод Бузена
3.1.2 Вычисление характеристик сети
3.1.3 Аналитическое представление нормализующей константы
3.1.4 Пример расчета
3.2 Расчет сетей с несколькими классами сообщений
3.2.1 Вычисление нормализующей константы
3.2.2 Маргинальное распределение длины очереди и пропускная способность
3.2.3 Расчет среднего времени ожидания и средней длины очереди
3.2.4 Алгоритм расчета замкнутой сети МО, допускающей изменение класса сообщений
3.3 Вычислительные аспекты метода анализа средних значений
3.3.1 Основные соотношения
3.3.2 Оценка эффективности вычислительного алгоритма
3.3.3 Расширение метода
3.4 Практические аспекты реализации алгоритмов расчета сетей массового обслуживания большой размерности
3.4.1 Выбор масштаба (масштабирование)
3.4.2 Реконфигурация сети МО
3.4.3 Обобщенный алгоритм свертки в виде дерева для расчета сетей МО
4 Приближенные методы исследования сетей очередей
4.1 Область применения и краткий анализ приближенных методов
4.1.1 Аппроксимация функций распределения
4.1.2 Диффузионная и декомпозиционная аппроксимации
4.2 Декомпозиционные методы на основе теоремы Нортона
4.2.1 Теорема Нортона для анализа замкнутых и разомкнутых локально-сбалансированных сетей массового обслуживания
4.2.2 Приближенный декомпозиционный алгоритм
4.2.3 Пример расчета
4.3 Декомпозиция разомкнутых сетей массового обслуживания на уровне первых моментов
4.3.1 Уравнения баланса потоков и дисперсий
4.3.2 Диффузионная аппроксимация системы МО GI/G/1
4.4 Полиномиальная аппроксимация
4.4.1 Описание метода
4.4.2 Оценка вычислительной сложности метода
4.4.3 Пример расчета
5 Развитие теории мультипликативных сетей очередей
5.1 Основные направления развития теории мультипликативных сетей
5.2 Сети массового обслуживания с зависимым обслуживанием
5.2.1 Описание сети. Обозначения
5.2.2 Частные случаи
5.2.3 Марковский процесс, описывающий функционирование сети
5.2.4 Основная теорема о мультипликативности сети
5.2.5 Частные случаи
5.3 G-сеть с отрицательными заявками
5.3.1 G-сеть с отрицательными заявками и групповыми удалениями положительных заявок
5.3.2 G-сеть с отрицательными заявками и триггерами
5.4 Решение уравнений баланса для интенсивности потоков и устойчивости G-сетей
5.5 G-сеть со случайным временем активизации сигналов
5.5.1 Однолинейные узлы
5.5.2 Симметричная G-сеть
5.5.3 Обсуждение результатов
5.6 G-сети с несколькими классами положительных заявок и сигналов
5.7 Другие модели и методы анализа G-сетей
6 Стохастические модели компьютерных сетей
6.1 Структура и информационное обеспечение компьютерных сетей
6.1.1 Структура компьютерных сетей
6.1.2 Сетевые протоколы
6.1.3 Использование теории сетей МО для исследования компьютерных сетей
6.2 Методы расчета характеристик сети пакетной коммутации
6.2.1 Анализ межконцевых задержек
62.2 Оптимизация пропускной способности и выбор маршрутов
6.2.3 Модель сети с ограниченной буферной памятью в узлах коммутации пакетов
6.3 Управление потоками в сети пакетной коммутации
6.3.1 Методы управления потоками
6.3.2 Сетевая модель глобального управления
6.3.3 Локальное управление буферами
6.4 Анализ буферной памяти узла коммутаци
6.4.1 Процесс буферизации в узле коммутации и схемы организации буферной памяти
6.4.2 Анализ однородного пула равнодоступных буферов
6.4.3 Сетевая модель памяти секционной структуры
6.4.4 Анализ динамической памяти с цепочкой буферов
7 Математические модели исследования алгоритмов маршрутизации
7.1 Основные понятия и определения
7.2 Постановка задачи
7.3 Алгоритмы решения задачи выбора оптимальных потоков в сети
7.3.1 Альтернативная маршрутизация
7.3.2 Фиксированная (однопутевая) маршрутизация
7.3.3 К-путевая маршрутизация
7.4 Примеры анализа алгоритмов маршрутизации в сетях передачи данных
7.4.1 Анализ различных вариантов алгоритмов маршрутизации для СПД «Экспресс»
7.4.2 Анализ развития СПД «Сирена»
7.5 Динамическая маршрутизация в ATM сетях
7.5.1 Характерные особенности ATM сетей
7.5.2 Основные понятия маршрутизации для ATM сетей
7.5.3 Взаимосвязь с подсистемой установки соединения
7.5.4 Классификация алгоритмов маршрутизации
7.5.5 Требования к алгоритмам динамической маршрутизации
7.5.6 Входные параметры заявки
7.5.7 Параметры состояния сети
7.5.8 Показатели качества маршрутизации
7.5.9 Анализ подходов к реализации общих требований
7.5.10 Маршрутизация запасных соединений
7.5.11 Выбор оптимального алгоритма и значений его параметров
8 Оптимизация топологической структуры компьютерной сети
8.1 Принципы топологического проектирования сетей передачи информации
8.2 Описание задачи синтеза топологии; исходные данные
8.3 Комбинаторный алгоритм топологической оптимизации сети передачи информации
8.4 Оптимизация топологической структуры по критериям стоимости и надежности
8.5 Алгоритм генерации остовных двухсвязных подграфов заданного графа
8.С Характеристики некоторых экстремальных графов. Теорема о нижней границе числа ребер
8.7 Общая задача топологического синтеза компьютерной сети
9 Методы анализа беспроводных компьютерных сетей
9.1 Состояние и перспективы развития беспроводных радиосетей
9.2 Схема распределенного управления
9.3 Моделирование беспроводной локальной сети в условиях высокой нагрузки
9.3.1 Оценка пропускной способности
9.3.2 Оценка вероятности передачи
9.3.3 Случай фрагментации пакетов
9.4 Моделирование городской радиосети
9.4.1 Имитационное моделирование радиосоты
9.4.2 Аналитический метод оценки
9.4.3 Оценка при технологии FHSS
9.5 Численные результаты исследования городской радиосоты
9.6 Региональные беспроводные сети на базе ШПС-радиомодемов
9.7 Аэростатная беспроводная сеть
9.8 Оптоэлектронные атмосферные каналы передачи данных в компьютерных сетях
Литература