Введение

Конец 20-го и начало 21-го веков ознаменовались бурным количественным и качественным ростом компьютерных сетей. Эта тенденция, которая очевидно сохранится в ближайшие десятилетия, хорошо иллюстрируется беспрецедентным ростом сети Интернет, охватившей все страны мира. Локальные компьютерные сети, являющиеся основой автоматизации деятельности отдельных предприятий и фирм, и распределенные сети, охватывающие города, регионы и континенты, проникли во все сферы человеческой деятельности, включая экономику, науку, культуру, образование, промышленность и т.д.

Современные компьютерные сети обеспечивают пользователям широкий набор услуг, включая электронную почту, передачу факсимильных и голосовых сообщений, работу с удаленными базами данных в реальном масштабе времени, службу новостей и другие услуги. На базе компьютерных сетей реализуются: дистанционное обучение, телемедицина, телеконференции, телебиржи и телемагазины и т.д.

Быстрый рост числа компьютерных сетей, успехи в развитии оптоволоконных и беспроводных средств связи, сопровождаются непрерывной сменой сетевых технологий, направленной на повышение быстродействия и надежности сетей, возможности интегрированной передачи данных, голоса и видеоинформации. Основным направлением развития технологий локальных сетей явилось создание семейства технологий Ethernet - Fast Ethernet - Gigabit Ethernet, обеспечивающее иерархию скоростей 10/100/1000 Мбит/с; в глобальных сетях осуществился переход от технологии Х25 к технологии Frame Relay, использованию стека протоколов TCP/IP, технологий ATM и Gigoethernet.

Смена технологий, непрерывный количественный и качественный рост компьютерных сетей выдвигают в ряд первоочередных задач развитие теоретических основ проектирования сетей на базе систематизации уже известных подходов и разработки новых методов анализа и синтеза компьютерных сетей. В настоящее время известны многочисленные публикации, в которых отражены технологии, логическая, физическая и программная структура современных компьютерных сетей [93,96,100,106,110].

Теоретические методы анализа и синтеза компьютерных сетей нашли отражение в многочисленных статьях и отдельных разделах монографий [2,12,74,78,95,119,120,172, 204,215,253,275], ориентированных в основном на специалистов - математиков. Сложность и многообразие подходов, отсутствие систематизации основных направлений анализа и синтеза компьютерных сетей создают значительные трудности для специалистов проектировщиков, желающих использовать теоретические подходы для решения практических задач. В то же время достаточная завершенность математических результатов и потребности разработчиков обусловили необходимость и своевременность систематизированного изложения теоретических основ проектирования компьютерных сетей.

Книга содержит девять глав, пять из которых посвящены методам анализа компьютерных сетей, основанным на теории систем и сетей массового обслуживания (теории очередей), четыре главы посвящены методам синтеза компьютерных сетей, а также последним результатам в области проектирования беспроводных компьютерных сетей.

Значительное внимание, уделяемое в первой части книги теории очередей, связано с тем, что стохастический характер поступления данных и недетерминированная обработка их в узлах коммутации и каналах связи предопределяет использование моделей теории очередей для анализа и проектирования компьютерных сетей.

Математические методы теории систем массового обслуживания обеспечивают возможность решения многочисленных задач расчета характеристик качества функционирования различных компонент компьютерных сетей, включая оценку вероятностно-временных характеристик узлов коммутации и маршрутизации; анализ производительности локальных сетей и сетей с множественным доступом; анализ буферной памяти узлов и методов локального и глобального управления потоками; расчет потерь и загрузку цифровых линий связи при передаче данных, голоса и видеоинформации при различных методах мультиплексирования и т.д.

В первой главе дано описание основных математических методов исследования марковских и полумарковских систем массового обслуживания. Исследуются однофазные и многофазные системы, а также системы с различными дисциплинами обслуживания входящих потоков сообщений.

Основное внимание в последующих двух главах уделяется аналитическим методам исследования локально-сбалансированных сетей очередей, стационарные вероятности состояний, которых имеют мультипликативную форму, и эффективным алгоритмам расчета характеристик таких сетей.

Рассмотренные во второй главе методы исследования локальносбалансированных сетей очередей позволяют получать решения в удобной мультипликативной форме. Однако прямое вычисление стационарных вероятностей состояний и других характеристик замкнутых сетей очередей требует значительных затрат машинного времени даже для сетей небольшой размерности. В связи с этим в третьей главе рассматриваются эффективные рекуррентные алгоритмы расчета сетей очередей. Наряду с описанием традиционных алгоритмов свертки и анализа средних значений дается изложение алгоритмов расчета сетей очередей большой размерности, базирующихся на использовании свойства разреженности матрицы маршрутов. Уделено внимание также практическим проблемам, возникающим при программной реализации вычислительных алгоритмов.

Следует отметить, что область применения аналитических моделей сетей очередей в значительной мере ограничивается из-за предположения об экспоненциальном характере обслуживания, так как в компьютерных сетях функции распределения времени обработки в узлах коммутации и передачи по каналам связи отличны от экспоненциальных. В этом случае, учитывая, что методы точного анализа моделей немарковских сетей очередей мало перспективны при исследовании реальных систем, используют приближенные подходы, рассмотренные в четвертой главе. Первый подход состоит в аппроксимации произвольной функции распределения последовательностью функций распределения, допускающих рациональное преобразование Лапласа, и отыскании точного решения для полученной сети очередей в мультипликативной форме. Ценой такой аппроксимации является значительное увеличение пространства состояний сети, что приводит даже при использовании высокоэффективных вычислительных алгоритмов к времени счета на ЭВМ, зачастую соизмеримому с имитационным моделированием.

Более перспективный подход связан с разработкой приближенных методов, которые позволяют исследовать немарковские сети очередей с блокировками, приоритетами и другими особенностями, характерными для компьютерных сетей. Большинство этих методов базируется на следующих подходах: либо постулируется независимость там, где случайные величины слабо зависимы, либо свойства мультипликативной формы представления сетей МО распространяются за пределы области их применения.

В пятой главе дано описание основных направлений развития теории сетей очередей; приведены новейшие результаты, полученные в этой области в последние годы. Особое внимание уделено исследованию сетей очередей с зависимым обслуживанием в центрах и решениям уравнения глобального баланса и устойчивости G-сетей.

В шестой главе методы расчета сетей очередей, описанные в предыдущих главах, используются для анализа сетевых моделей различных уровней протоколов, соответствующих «эталонной модели архитектуры открытых систем», и моделей отдельных компонентов компьютерных сетей. Основное внимание уделяется методам расчета интегральных характеристик, методам глобального и локального управления потоками, а также анализу процессов буферизации в узлах коммутации пакетов, являющихся основными компонентами компьютерной сети.

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

В седьмой главе систематизируются известные и приводятся новые алгоритмы выбора оптимальных маршрутов, включая исследование фиксированной, альтернативной и К-путевой маршрутизации. Приводятся примеры расчета для крупнейших в СНГ корпоративных компьютерных сетей «Сирена» и «Экспресс», в разработке и внедрении которых автор принимал непосредственное участие. Дается систематизированное изложение динамической маршрутизации в ATM сетях, которое до настоящего времени отсутствовало в отечественных и зарубежных изданиях.

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

Последняя девятая глава посвящена методам проектирования беспроводных сетей, получившим в последние годы широкое признание как эффективное средство решения проблемы «последней мили» и создания «домашних» и региональных компьютерных сетей. Дано описание новых аналитических моделей оценки производительности и других характеристик качества функционирования беспроводных сетей с использованием методов теории сетей очередей, описанных в главе 2.

Приведены примеры проектирования сети Radionet, обеспечивающей подключение организаций науки и образования города Москвы к сети Интернет, разработанной и внедренной под руководством и при участии автора книги. В последних двух разделах дано описание оригинального проекта беспроводной компьютерной сети с использованием привязных аэростатов, разработанного Институтом проблем передачи информации РАН и РНЦ «Курчатовский институт», а также применение оптоэлектронных атмосферных каналов передачи информации в компьютерных сетях.

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

Автор приносит благодарность сотрудникам отдела компьютерных сетей Института проблем передачи информации РАН, принимавших участие в подготовки книги. Особая признательность выражается академикам Е.П.Велихову и Н.А.Кузнецову за поддержку и ценные советы при написании книги.