Ни один проект крупной сети со сложной топологией в настоящее время не обходится без исчерпывающего моделирования будущей сети. Программы, выполняющие эту задачу, достаточно сложны и дороги. Целью моделирования является определение оптимальной топологии, адекватный выбор сетевого оборудования, определение рабочих характеристик сети и возможных этапов будущего развития. Ведь сеть, слишком точно оптимизированная для решений задач текущего момента, может потребовать серьезных переделок в будущем. Моделирование используется для исследования характеристик новых модификаций протоколов, методы работы с очередями, для оптимизации параметров качества обслуживания.
На модели можно опробовать влияние всплесков загрузки, воздействие большого потока широковещательных запросов или реализовать режим коллапса (для Ethernet), что вряд ли кто-то может себе позволить в работающей сети. В процессе моделирования выясняются следующие параметры:
Перечисленные задачи предъявляют различные требования к программам. В одних случаях достаточно провести моделирование на физическом (MAC) уровне, в других нужен уже уровень транспортных протоколов (например, UDP и TCP), а для наиболее сложных задач нужно воспроизвести поведение прикладных программ. Все это должно приниматься во внимание при выборе или разработке моделирующей программы. Ведь нужно учесть, что ваша машина должна в той или иной мере воспроизвести действия всех машин в моделируемой сети. Таким образом, машина эта должна быть достаточно быстродействующей, и, несмотря на это, моделирование одной секунды работы сети может занять при определенных условиях не один час.
Задачи моделирования обработки очередей в виртуальном канале с целью оценки параметров качества облуживания требуют не столь значительных ресурсов. Но с учетом перебора возможных значений параметров конфигурации это также может занять много часов.
Результаты моделирования должны иметь точность 10-20%, этого достаточно для большинства целей и не требует слишком много машинного времени. Следует иметь в виду, что для моделирования поведения реальной сети надо знать все ее рабочие параметры: длины кабеля от концентратора до конкретной ЭВМ, задержки используемых кабелей, задержки концентраторов (этот параметр часто отсутствует в документации и его придется брать из документации на сетевой протокол, например, из IEEE 802.3). Параметры могут быть определены и прямым измерением. Чем точнее вы воспроизводите поведение сети, тем больше машинного времени это потребует. Кроме того, вам предстоит сделать некоторые предположения относительно распределения загрузки для конкретных ЭВМ и других сетевых элементов, задержек в переключателях, мостах, времени обработки запросов в серверах. Здесь нужно учитывать и характер решаемых на ЭВМ задач: www/ftp-сервер или обычная персональная рабочая станция создают различные сетевые трафики. Определенное влияние на результат могут оказывать и используемые ОС. В случае моделирования реальной сети можно произвести соответствующие измерения, что иногда тоже не слишком просто. Учитывая сложность моделирования на одной ординарной ЭВМ, следует ограничиваться моделированием не более чем одной минуты для каждого из наборов параметров (этого времени достаточно для копирования практически любого файла через локальную сеть). Исключение может составлять моделирование внешнего трафика, но в этом случае весь локальный трафик должен рассматриваться как фоновый.
Современные распределенные технологии дают новые возможности для решения задач моделирования.
Определение характеристик сети до того, как она будет введена в эксплуатацию, имеет первостепенное значение. Это позволяет отрегулировать характеристики локальной сети на стадии проектирования. Решение этой проблемы возможно путем аналитического или статистического моделирования. По существу, в данном разделе речь идет об описании сети в рамках теории массового обслуживания.
Аналитическая модель сети представляет собой совокупность математических соотношений, связывающих между собой входные и выходные характеристики сети. При выводе таких соотношений приходится пренебрегать какими-то малосущественными деталями или обстоятельствами.
Телекоммуникационная сеть при некотором упрощении может быть представлена в виде совокупности процессоров (узлов), соединенных каналами связи. Сообщение, пришедшее в узел, некоторое время пребывает в очереди до того, как оно будет обработано. Время передачи или полное время задержки сообщения $$D$$ равно:
$$D = T_p + S + W$$,
где $$T_p$$, $$S$$ и $$W$$ соответственно - время распространения, время обслуживания и время ожидания. Одной из задач аналитического моделирование является определение среднего значения $$D$$. При больших загрузках основной вклад дает ожидание обслуживания $$W$$. Для описания очередей в дальнейшем будет использована нотация Д. Дж. Кенделла:
$$A/B/C/K/m/z$$,
где $$А$$ - процесс прибытия: $$В$$ - процесс обслуживания; $$С$$ - число серверов (узлов); $$К$$ - максимальный размер очереди (по умолчанию - $$\infty$$ ); $$m$$ - число клиентов (по умолчанию - $$\infty$$ ); $$z$$ - схема работы буфера (по умолчанию FIFO). Буквы $$А$$ и $$В$$ представляют процессы прихода и обслуживания и обычно заменяются следующими буквами, которые характеризуют закон, соответствующий распределения событий:
Наиболее распространенными схемами работы буферов являются FIFO (First-In-First-Out), LIFO (Last-In-First-Out) и FIRO (First-In-Random-Out). Например, запись $$M/M/2$$ означает очередь, для которой времена прихода и обслуживания соответствует экспоненциальному распределению, имеется два сервера, длина очереди и число клиентов могут быть сколь угодно большими, а буфер работает по схеме FIFO. Среднее значение длины очереди $$Q$$ при заданной средней входной частоте сообщений $$\lambda$$ и среднем времени ожидания $$W$$ определяется на основе
$$\vec Q=\lambda \vec W$$
Для варианта очереди $$M/G/1$$ входной процесс характеризуется
$$p(k)=\frac{\left(\lambda t\right)^k}{k!}e^{-\lambda t}$$ , $$k=0,1,2,..$$.
Пусть $$N$$ - число клиентов в системе, $$Q$$ - число клиентов в очереди, и пусть вероятность того, что входящий клиент обнаружит $$j$$ других клиентов, равна:
$$П_j=P[n=j], j=0,1,2,... \sum_{j=0}^\infty П_j=1; П_0=1-\rho;\rho=\lambda\tau$$
Тогда среднее время ожидания $$w$$:
$$\overline{W}=\frac{\overline{Q}}{\lambda}=\frac{\rho\tau}{2(1-\rho)}(1+\frac{\sigma^2}{\tau^2})$$
(
$$\sigma$$ - среднеквадратичное отклонение для распределения времени обслуживания.
Для варианта очереди $$M/G/1 H(t) = P[X \le t] = 1 - e^{-\mu t}$$ ( $$H$$ - функция распределения времени обслуживания). Откуда следует $$\sigma^2 = \tau^2$$.
$$\overline{W}=\frac{\rho\tau}{(1-\rho)}$$
Для варианта очереди $$m/d/1$$ время обслуживания постоянно, а среднее время ожидания составляет:
$$\overline{W}=\frac{\rho\tau}{2(1-\rho)}$$
Аналитическая модель для сетей Ethernet (CSMA-CD) разработана Лэмом (S.S.Lam: "A Carrier Sense Multiple Access Protocol for Local Networks,"
$$\overline{D}=\frac{\lambda [S^2+(4e+2)\tau S+5\tau^2+4e(2e-1)\tau^2]}{2(1-\lambda [\overline{S}+\tau+2e\tau])}-\frac{(1-e^{-2\lambda\tau})(e+\lambda\tau-2\lambda\tau e)}{\lambda e[F(\lambda)e^{-(1+\lambda\tau)}+e^{-2\lambda\tau}-1]}+2\tau e+\overline{S}+\tau /3$$
где $$е$$ - основание натурального логарифма, $$\tau$$ - задержка распространения сигнала в сети. $$\vec S$$ и $$\vec S^2$$ - соответственно первый и второй моменты распределения передачи или обслуживания сообщения. $$f(\lambda)$$ преобразование Лапласа для распределения времени передачи сообщения. Следовательно,$$F(\lambda)=\int\limits_0^\infty f(t)e^{-\lambda t},dt$$ , а для сообщений постоянной длины $$f(\lambda)=e^{-\rho}, \vec S^2=\vec S^2$$, где $$\pi =\lambda \vec S$$. Для экспоненциального распределения длин сообщений:
$$F(\lambda)=\frac{1}{1+\rho}, \overline{S^2}=2\overline{S}^2$$
Рассмотрим вариант сети Ethernet на основе концентратора-переключателя с числом каналов $$N$$. При этом будет предполагаться, что сообщения на входе всех узлов имеют
$$\overline{W}=\hat{y}+\frac{\lambda\hat{y}^2}{2(1-\rho)},$$
где $$\hat{y}=[1+(N-2)\rho G]\overline{S}$$,
$$\hat{y}^2=2[1+(N-2)\rho G+(N-2)(N-3)\rho^2G^2]\overline{S^2}$$
$$\rho=\frac{\lambda S}{1-(N-2)G\lambda\overline{S}}$$ , $$\lambda=\lambda_i$$, а $$G=1/(N-1)$$ равно вероятности того, что сообщение отправителя $$i$$ направлено получателю $$j$$. Требование стабильности $$\rho \le 1$$ обязывает, чтобы $$\lambda \vec S \le (N-1)(2N-3)$$
Для больших $$n$$ это приводит к $$\lambda \vec S \le 1/2$$.
Среднее время распространения сообщения в сети равно $$\vec T_p = \tau,$$ где $$\tau$$ равно $$RTT$$.
$$\overline{D}=\hat{y}+\frac{\lambda\hat{y}^2}{2(1-\rho)}+\overline{S}+\tau$$
Особое место занимает моделирование систем работы с очередями. Эти задачи стали особенно актуальными в связи необходимостью получения гарантированных параметров качества обслуживания. Этот тип моделирования можно реализовать с помощью общедоступной программы и http://www-mash.cs.berkeley.edu/ns.)
Симуляционное (статистическое) моделирование служит для анализа системы с целью выявления критических элементов сети. Этот тип моделирования используется также для предсказания будущих характеристик системы. Такое моделирование может осуществляться с использованием специализированных языков симулирования и требует априорного знания относительно статистических свойств системы в целом и составляющих ее элементов. Процесс моделирования включат в себя формирование модели, отладку моделирующей программы и проверку корректности выбранной модели. Последний этап обычно состоит из сравнения расчетных результатов с экспериментальными данными, полученными для реальной сети.
При статистическом моделировании необходимо задать ряд временных характеристик, например: таблица 17.1.
| Системное время | Интервал от момента генерации сообщения до получения его адресатом, включая ожидание в очереди |
|---|---|
| Время ожидания | Промежуток времени от приема сообщения сетевым интерфейсом до обработки его процессором |
| Время распространения | Задержка передачи сообщения от одного сетевого интерфейса до другого |
Полный список таких временных характеристик включает в себя значительно больше величин. В процессе моделирования рассчитываются следующие параметры: таблица 17.2.
| Статистика очередей |
|---|
| Пиковая длина очереди |
| Среднеквадратичное отклонение длины очереди от среднего значения |
| Статистика времени ожидания |
| Среднее время ожидания |
| Максимальное время ожидания |
| Среднеквадратичное отклонение времени ожидания |
| Статистика системного времени |
| Среднее системное время |
| Максимальное системное время |
| Среднеквадратичное отклонение системного времени |
| Полное число сообщений в статистике системного времени |
| Пиковое значение числа системных сообщений |
| Среднеквадратичное отклонение числа системных сообщений |
| Статистика потерь сообщений |
| Полное число потерянных сообщений |
| Частота потери сообщений |
| Доля потерь из-за переполнения очереди |
| Доля потерь из-за таймаутов |
Разумеется, реальный перечень вычисляемых параметров может быть существенно шире и определяется конкретными целями расчетов. Рассмотрим частную задачу определения среднего числа связей между процессорами (узлами). Предполагается, что полное число узлов равно $$N$$, а схема соединения узлов соответствует изображенной на рис 17.1.
(рис 17.1) Среднее расстояние от произвольного узла до всех остальных узлов равно $$D(N+1)/3$$, где $$D$$ - расстояние между соседними узлами (предполагается константой).
Возможны разные подходы к моделированию. Классический подход заключается в воспроизведении событий в сети как можно точнее и поэтапном моделировании последствий этих событий. В реальной жизни события могут происходить одновременно в различных точках сети. По этой причине для моделирования идеально подошел бы многопроцессорный компьютер, где можно воспроизводить любое число процессов одновременно (современные распределенные вычислительные системы для решения таких задач подходят идеально). В любом случае необходимо выбрать некоторый постоянный временной интервал и считать, что события произошли одновременно, если расстояние между ними меньше этого интервала. Для сетей типа Ethernet таким временным интервалом может быть бит-такт (для 10-мегагбитного Ethernet это 100нс). Понятно, что это уже отступление от реальности (ведь задержки в сетевом кабеле не кратны этому времени), но не слишком значительное. Надо сказать, что такого рода предположений при моделировании приходится делать много. По этой причине крайне важно сравнивать результаты моделирования с данными, полученными для реальной сети. Если отличия лежат в пределах 10-20%, можно считать, что сделанные предположения не увели программу слишком далеко от жизни и ею можно пользоваться для расчетов. Рассмотренный выше подход пригоден для моделирования сетевого коллапса, так как скорость расчетов здесь зависит от числа узлов и почти не зависит от сетевой загрузки.
Другим подходом может стать метод, где для каждого логического сегмента (зоны столкновений) сначала моделируется очередь событий. При этом в каждой рабочей станции моделируется последовательность пакетов, ожидающих отправки. Эта очередь может время от времени модифицироваться, например, при получении ЭВМ пакета извне и необходимости послать на него отклик. После того как такая очередь для каждого сетевого объекта (сюда, помимо ЭВМ, входят мосты, переключатели и маршрутизаторы) построена, запускается программа отправки пакетов: выбирается самый первый по времени пакет (ожидающий дольше других) и проверяются для него условия начала передачи (отсутствие несущей на входе сетевого интерфейса в данный момент и в течение предыдущих 96 бит-тактов). Если условия отправки выполнены, пакет посылается в сеть. Вычисляются моменты достижения им всех узлов данного логического сегмента, проверяются условия его столкновения с другими пакетами. Следует заметить, что в этом подходе снимаются ограничения дискретности временной шкалы, использованной в предыдущем "классическом" подходе. Этот подход позволяет заметно ускорить расчеты при большом числе узлов, но малой загрузке сети. Проблемы реализации данной концепции моделирования связаны с обслуживанием довольно сложного списка, который описывает очередь пакетов, ожидающих отправки. В структуру этого списка включается и описание ситуации в сети на данный временной период. Дополнительные трудности сопряжены с поведением мостов, переключателей и маршрутизаторов, так как они могут вставлять в очередь дополнительные элементы, требующие немедленного обслуживания. Аналогичные вставки в очередь будут вызывать полученные станцией пакеты ICMP или TCP, требующие откликов. Причем такое вставление в очередь асинхронно по отношению к процедуре "отправки" пакетов. Очередь для всей локальной сети может быть единой, тогда пакеты разных логических сегментов должны быть помечены определенными флагами. При переходе из сегмента в сегмент флаг будет меняться. Возможно и построение независимых очередей для каждого из логических сетевых сегментов.
Данный метод был использован студентом ТСС МФТИ Алексеем Овчаровым в его магистрской диссертации (2000 год) для определения свойств фрагмента сети в условиях, близких к предельным (загрузка на уровне 70-100%). Такие режимы трудно реализовать на практике без нанесения серьезного ущерба клиентам сети. Результаты расчета представлены на рис 17.2.
Целью моделирования является определение зависимости пропускной способности сети и вероятности потери пакета от загрузки, числа узлов в сети, длины пакета и размера области столкновений.
Исходные данные о структуре и параметрах сети берутся из базы данных. Ряд параметров сети задаются конфигурационным файлом (профайлом). Сюда могут записываться емкость буфера интерфейса и драйвера, время задержки обработки запроса (хотя в общем случае эта величина может также иметь распределение) и т.д.. К таким параметрам относятся также: MTU,
Сеть разбивается на логические сегменты, в каждом из которых работает независимая синхронизация процессов (хотя эти процессы и влияют друг на друга через мосты, переключатели и маршрутизаторы).
(рис 17.2) Зависимость вероятности потери пакета в процентах от загрузки фрагмента сетиПолное моделирование сети с учетом рабочих приложений предполагает использование следующих распределений:
Последние два пункта существенным образом коррелированы с первым, так как используемые протоколы зависят от приложения, а активность узла может определяться, например, длиной пересылаемого файла. По этой причине при полномасштабном моделировании сначала определяется, что собирается делать рабочая станция или сервер (с учетом распределения по приложениям определяется характер задачи: FTP, MS explorer и т.д.). Затем разыгрываются параметры задания (длина файла, удаленность объекта и пр.), а уже на основе этого формируется фрагмент очереди пакетов.
Задача первого этапа: проверка пропускной способности при вариации загрузки и длин пакетов, подсчет числа столкновений (если они возможны), проверка влияния размера буфера сетевого интерфейса на пропускную способность (влияние размера буфера переключателей по пути до адресата).
Исходные данные для первого этапа:
Структура описания каждого из узлов включает в себя (формируется с учетом будущего расширения):
Формат описания топологии сети (список) Элемент списка:
Процесс посылки пакета включает в себя (в соответствии с требованиями документа IEEE 802.3):
Попытка начала передачи предполагает проверку:
Процесс приема предполагает:
Центральный менеджер осуществляет:
Равномерное распределение по времени
Для каждого узла устанавливается определенная средняя частота посылки пакетов. Время начала сессии предполагается случайным. Средняя частота может быть задана равной для всех узлов.
Минимальный средний период посылки пакетов определяется в бит-тактах и должен быть больше 512 бит-тактов. Понятно, что пока узел осуществляет передачу, он не может пытаться передать новый пакет. По этой причине частота посылки пакетов однозначно определяется паузой между концом предыдущего пакета и началом нового $$(\delta)$$. Среднее значение периода посылки пакетов равно $$Т_{пакета}+96(бит-тактов)+\delta$$ (значение $$\delta$$ величина в общем случае статистическая). Для каждого узла задается значение $$\delta$$ (сначала равное для всех узлов). Если предположить равномерное распределение вероятности, передача пакета может начаться в любой бит-такт с равной вероятностью.
При определении того, пытаться ли начинать передачу в данный бит-такт, будет произведена проверка условия:
$$rndm <1/\delta$$ (выполнение условия предполагает попытку начала передачи).
Если вероятность прихода $$n$$ пакетов на время $$t$$ распределена по закону Пуассона:
$$P=\frac{(Lt)^n e^{Lt}}{n!}$$, где $$L$$ - средняя частота следования событий, то реальное время между событиями может быть определено как $$\tau = -T ln(R)$$. $$R$$ - случайное число $$0 \le R \le 1$$, а $$T = 1/L$$.
Результатами моделирования могут являться (фиксируются отдельно для каждого набора входных параметров): таблица 17.3.
| 1. | Вероятность потери пакета для логического сегмента и каждой из рабочих станций |
|---|---|
| 2. | Пропускная способность серверов для каждого из логических сегментов (путь сервер -> логический сегмент) |
| 3. | Вероятность столкновения для каждого логического сегмента и каждой рабочей станции |
| 4. | Распределение потоков по логическим сегментам (и рабочим станциям) независимо для каждого направления (вход и выход) |
| 5. | Распределение потоков для всех входов/выходов переключателей мостов и маршрутизаторов |
| 6. | Доля вспомогательного трафика (ICMP, SNMP, отклики TCP, широковещательные запросы и т.д.) по отношению к информационному потоку для различных узлов сети (серверов, маршрутизаторов) |
| 7. | Уровень широковещательного трафика для каждого из логических сегментов |
Набор параметров, распределений и алгоритм моделирования сильно зависит от стоящей задачи.
Современный Интернет насчитывает десятки миллионов серверов и сотни миллионов рабочих станций. Данная технология стала широко использоваться в информационных системах и бизнесе, именно по этой причине проблема надежности сетей становится все более актуальной. Ведь совсем не безразлично, получит ли человек своевременно отклик от банкомата, произведет ли клиент покупку, будут ли корректно введены данные в систему навигации ракеты и т.д.
Но прежде чем поставить вопрос о надежности Интернет или даже локальной сети, нужно определить некоторые базовые понятия. Надежность всякой системы определяется надежностью составляющих ее элементов. А надежность элементов задается временем наработки на отказ или вероятностью отказа за оговоренный период времени. Надежности разных элементов могут отличаться существенно. В результате как усредненные значения надежности, так и распределения вероятности отказов разных сетевых устройств могут варьироваться в очень широких пределах. Во многих случаях надежность и распределения надежности определяются эмпирически.
И если требование надежности определить как работоспособность всех элементов, надежность Интернета окажется равной нулю, ведь всегда найдется неисправный или отключенный узел или рабочая станция. Если же определить надежность системы как возможность коммуникации между, скажем, 1000 каких-либо узлов или рабочих станций, то надежность Интернет окажется практически равной единице. Конечно, если ваша рабочая станция не попадет в число этих 1000 узлов, вы вряд ли согласитесь с утверждением абсолютной надежности. Понятно поэтому, что оба определения совершенно неприемлемы. Не нужно думать, что случай оценки надежности локальной сети, содержащей, например, 100 рабочих станций, много проще.
Здесь нужно будет определить, что такое отказ. Современная персональная ЭВМ - достаточно сложный прибор, содержащий несколько внешних устройств, один или более процессоров, оперативную память, сетевой интерфейс, ОС и т.д. Что следует считать отказом рабочей станции? Выход из строя источника питания, повисание ОС, разрушение системного диска, отказ сетевой карты и пр. или что-то еще, например, ошибка в прикладной программе или выдергивание уборщицей кабеля из розетки? Надо сразу сказать, что однозначного ответа на этот вопрос нет, все зависит от обстоятельств.
Прежде чем переходить к теоретической части, посмотрим, что можно сделать для улучшения надежности сети с практической точки зрения. Конечно, этому будет способствовать использование RAID-систем жестких дисков, катастрофоустойчивой системы дублирования резервных копий дисков в удаленных узлах, размещенных в разных зданиях, и т.д.. Но не следует снимать со счета дублирование базовых серверов: DNS, NTP (если они нужны), почтовых серверов, серверов баз данных и пр. Внутри локальной сети повышению надежности может способствовать применение протокола STP, который может автоматически обеспечить обход отказавшего участка LAN (если применение динамического протокола внутренней маршрутизации невозможно или нежелательно, например, по соображениям безопасности). Во многих случаях крайне важно задублировать шлюз сети, ведущий в Интернет, так как его отказ оставит всех пользователей сети без связи. Компания CISCO и многие другие фирмы разработали протоколы резервирования маршрутизаторов. В этих протоколах два или более устройств совместно используют виртуальные IP и МАС-адреса, которые указаны в сетевом сегменте для шлюза по умолчанию. Для реализации такой схемы существует три протокола:
Компания CISCO поддерживает только протокол
При рассмотрении
Выход из строя рабочей станции (терминальный узел) создает проблемы ее пользователю, остальные пользователи Интернет, скорее всего, этого не заметят, но отказ сервера скажется на работе всех его клиентов, в том числе и удаленных. Выход же из строя маршрутизатора (если это транзитный узел) может оказать влияние на работу целого региона. Отсюда видно, что отдельные узлы могут по-разному влиять на работу сети в целом. Даже в классе серверов можно выделить группы разного влияния на уровень надежности. Например, отказ сервера IN-ADDR.
Этим список факторов, влияющих на надежность, не исчерпывается. Если пользователь не может получить доступ к определенному сетевому ресурсу, это очень часто связано не с отказом оборудования или программы, а просто с перегрузкой одного из участков сети по дороге к указанному ресурсу (некомпетентность пользователя в данном анализе не рассматривается). Здесь имеется в виду не только ограничение пропускной способности, но и возможное увеличение задержки доставки, что достаточно критично в случае, например, IP-телефонии или видео-конференций. Таким образом, параметры надежности часто зависят от вектора загрузок (список значений загрузок каналов, влияющих на доступ и качество обслуживания). По этой причине, формулируя задачу оценки надежности, нужно определить, какие из параметров важны: связность, пропускная способность, время восстановления связности или минимизация задержек обслуживания.
Если мы рассмотрим в качестве примера полный граф с четырьмя узлами, размещенными в вершинах квадрата (6 ребер), то расчет связности такой сети будет включать комбинаторику перебора ребер и учет распределения вероятности обрыва каждой из связей. Нетрудно понять, что если попытаться проанализировать надежность структурированной локальной сети с сотней ЭВМ, задача окажется на много порядков сложней, я уже не говорю об Интернете в целом. Обычно множественность в таких задачах равна $$N$$! (где $$N$$ - число узлов в графе связей). В любом случае в качестве исходных данных должны использоваться значения надежности отдельных узлов и каналов, вычисленные или измеренные с учетом тех факторов, влияние которых вы хотите учесть. Во многих случаях бывает нужно сделать предположение относительно распределения
По этой причине, прежде чем писать и запускать программу расчета надежности сети надо научиться оценивать: а хватит ли имеющихся вычислительных ресурсов для решения поставленной задачи в текущем тысячелетии. Для этого существует математические методы оценки сложности алгоритмов [ А. V. AHO, J. D.Ullman, "Foundation of Computer Science", Computer Science Press, 1992, или V.V. Leeuwen, "Algorithms and Complexity", The MIT Cambridge, Massachusetts, Elsevier Science Publishers, 1990 ]. Из-за сложности прямых вычислений многие исследователи ограничиваются лишь оценкой возможных границ надежности. На практике, даже используя самые производительные вычислительные системы, можно оценить надежность сети с ограниченным числом узлов. Для больших сетей доступными являются лишь оценки нижней или верхней границы надежности.
За отправную точку примем сеть $$G =(V,E)$$, в которой $$V$$ - набор узлов или вершин графа сети, а $$Е$$ - набор неориентированных ребер или набор ориентированных дуг. Большинство исследований по
$$Rel(G,s,K,p)=Pr[существует~хотя~бы~один~работающий~путь~от~s~до~каждого~ узла~из~набора~К]$$
То есть, надежность сети с графом $$G$$ для набора узлов $$К$$ и выбранного узла $$s$$ при вероятности иметь надежную связь для всех ребер графа $$p$$ равна вероятности того, что узел $$s$$ имеет хотя бы один доступный путь до каждого из узлов $$К$$. Обычно эта величина соответствует определенному временному интервалу. Следует помнить, что для локальных сетей не может быть двух путей от $$s$$ до любого из узлов $$K$$.
Существует два важных частных случая мер: 2-терминальная мера с $$|К|=2$$ и всетерминальная мера, где $$К=V$$. Эти меры принято обозначать $$Rel_2(G,s,p)$$ и $$Rel_А(G,s,p)$$, соответственно ( $$Rel$$ - надежность).
Читателю, рассчитывающему найти какие-то формулы, подставив в которые число узлов,
В самых первых моделях ЭВМ память организовывалась из множества отдельно стоящих реле и вакуумных ламп. Компьютерные системы, которые отказывали при выходе из строя одного из их элементов, были крайне ненадежны, так как
Первые активные разработки в области систем повышенной надежности проводились для систем, чей отказ мог повлечь катастрофы и гибель людей. Примерами таких систем является авиа- и космические системы, управление ядерными реакторами, системы управления оборонными комплексами. В последнее время широко распространено мнение, что в ряде промышленных отраслей с экономической точки зрения выгодней применять системы повышенной надежности. Например, это экономически оправданно в телекоммуникационных сетях, банковских системах - сетях подтверждения кредитоспособности и в системах оформления заказов.
Основной целью исследований в области
В результате расчетов надежности упрощенной модели сети могут быть выработаны рекомендации и критерии по выбору топологии и структуры, которые помогут достичь более высокой надежности.
Первые сети с коммутацией пакетов были разработаны в 1960-х. Их создали с целью поделить высокоскоростные каналы между большим количеством пользователей. Трафик, порождаемый одним пользователем, имеет много всплесков и пауз. Трафик нескольких пользователей можно динамически разнести по времени и передавать по одному соединению. ARPANET была первой крупной сетью с коммутацией пакетов. Большая часть исследований в области
При сравнении ARPANET с коммерческими опорными сетями с коммутацией пакетов, используемыми в 1980-х годах, такими, как Telnet и Tymnet, ясно, что коммерческие сети много компактнее. Как следствие, вероятность нарушения связанности в коммерческих сетях много меньше, но, как правило, загрузка каналов там достаточно высока. Отсюда напрашивается вывод, что следует более детально вычислять параметры
Сегодня сеть ArpaNet может показаться топологически достаточно простой, но даже для такой сети расчет надежности отнюдь не простая задача даже при оценке простой связности.
Для того чтобы минимизировать перебор, можно использовать различные методы эквивалентного преобразования графа сети, минимизирующего число узлов или ребер при сохранении значения надежности.
На сегодняшний день крупнейшие телекоммуникационные сети являются
Особый случай сетей с коммутацией каналов возникает при проектировании связных сетей в параллельных вычислительных архитектурах для объединения параллельных процессоров и памяти. Модели, основанные на связанности сети, одинаково применимы и к отказам по причине перегрузок, и к отказам в работе сетевых узлов. Эквивалентом производительности системы считается среднее значение параметра связанности сети между ее входной и выходной точками.
Оптические кабели - одно из последних достижений современной технологии. Телекоммуникационные сети всего мира переводятся на использование этой техники (смотри, например, T. Flanagan, "Fiber Network Survivability" IEEE Communication Magazine 28 (1990) 46-53 ). Основным преимуществом оптической среды передачи по сравнению с передачей по медным кабелям является существенный рост пропускной способности и снижение уровня шумов. Именно по этой причине многие телефонные сети общего пользования осуществляют быстрый переход на оптику. Как, однако, оказалось, в проблематике надежности сетей существуют более важные проблемы, и именно их следует изучать. А именно: пропускная способность оптоволоконных сетей чрезвычайно высока, поэтому структура таких сетей, в отличие от обычных, имеет более распределенный характер.
Старые сети были более разветвленными и имели большое число связей, вопрос
К оптическим каналам добавляют каналы-дублеры с возможностью переключения между основным и дублирующим каналом. При этом желательно, чтобы трассы их прокладки не совпадали (по стране рыщут бульдозеры и экскаваторы, так и норовящие порвать любые кабели). В результате мы сможем применить к оптической сети уже имеющиеся методы оценки надежности.
Компьютерная система называется устойчивой к сбоям, если при отказе одного из ее компонентов она продолжает функционировать. В 1970-х годах такие компьютеры использовались в качестве переключателей в опорных телекоммуникационных сетях. И сегодня они широко применяются во многих приложениях. Позже были разработаны параллельные вычислительные архитектуры. С целью повышения производительности параллельные ЭВМ собирались из множества однотипных элементов. Однако параллельные архитектуры имеют также и повышенные характеристики надежности. Обычно такие отказоустойчивые и параллельные компьютерные системы при анализе надежности моделировались как сети. Поскольку большая часть исследований по оценке
Существует большое разнообразие сетевых моделей, часть из них применяется в других областях науки. Во всех анализируемых случаях сеть поддерживает работу многих пользователей, трафик каждого из них следует через сеть одним или несколькими маршрутами. Обычно подразумевается, что можно произвести более точную оценку надежности, если учесть в расчетах параметры маршрутизации. В завершение нужно отметить, что нужно учитывать величины пропускной способности. Одна из наиболее интересных областей применения - городские сети наземного транспорта. В этом контексте инциденты, такие, как аварии на автомагистралях, вызывают отказ сетевых узлов или дуг. Хотя нарушения связанности в сети городского транспорта происходят очень редко, все же вполне типично, когда отказ узла или связи вызывает ситуацию значительной перегрузки.
Наконец, применение многих средств оценки надежности сети, которые разработаны для мер, базирующихся на связности, распространяется на совершенно другие проблемы надежности, например, в сфере диспетчеризации и распределения ресурсов (в том числе операционных систем или сетей электроснабжения).
Механизмы потерь и причины их возникновения относительно хорошо изучены в классической теории надежности. Например, в электронных системах деградация узлов происходит, когда они подвергаются непрерывному тепловому воздействию. В результате такие узлы случайным образом выходят из строя. Анализ надежности для подобных систем обычно включает в себя изучение этих случайных процессов и параметры их распределений. При анализе
Из-за отсутствия приемлемой модели механизма потерь в сети и присущей сложности расчета
Рассмотрим некое обобщение этой модели. В частности, будем рассматривать модели, в которых каждый компонент может находиться в одном из нескольких состояний, или модели, в которых рабочее состояние характеризуется численным значением. Численные значения этих характеристик обычно приравниваются метрике расстояния или величине пропускной способности. Простая модель с двумя состояниями хорошо подходит для вычисления меры связанности. Когда возникает необходимость посчитать более сложную меру, например, производительность системы, применяют более сложные характеристики состояний компонентов.
Для модели с двумя состояниями вероятность работоспособности компонента или, проще, надежность, можно понимать по-разному. Наиболее распространенными являются формулировки:
Вообще в этом разделе договоримся применять термин надежность для обозначения вероятности того, что компонент или система работает. Здесь мы обсуждаем более частное определение. Доступность используется в контексте ремонтоспособных систем. Из сказанного следует, что компонент может находиться в одном из трех состояний: работает, не работает, в процессе восстановления. Доступность компонента определяется как вероятность его работы в случайный момент времени. Оценка величины доступности производится с учетом среднего времени восстановления в рабочее состояние и среднего времени в нерабочем состоянии. Надежность можно записать так:
$$\frac{среднее\ время\ до\ отказа}{среднее\ время\ до\ отказа + среднее\ время\ восстановления}$$
Определение надежности компонента не учитывает время восстановления. Специфицируется промежуток времени $$t$$, а надежность компонента определяется как вероятность того, что за это время $$t$$ компонент останется в рабочем состоянии. Допускаются также иные трактовки для вероятности того, что компонент работает. Конечно, интерпретация уровня надежности компонента определяет в свою очередь интерпретацию мер
За отправную точку примем сеть $$G=(V,E)$$, в которой $$V$$ - набор узлов или вершин, а $$Е$$ - набор неориентированных ребер или набор ориентированных дуг. При изучении моделей связанности для каждого $$е \in Е$$ мы определяем надежность $$е(р_е)$$ как $$Pr[e работает]$$. При изучении простых моделей потоков (кратчайших путей), мы ассоциируем пропускную способность $$с_е$$ (расстояние $$d_е$$ ) с каждым $$е \in Е$$. Мы интерпретируем $$р_е$$, как вероятность того, что $$е$$ работает и имеет пропускную способность $$с_е$$ (расстояние $$d_е$$ ), а $$1-р_е$$ - как вероятность того, что $$е$$ не работает и имеет пропускную способность $$0$$ (расстояние равно бесконечности). При изучении моделей потоков (кратчайших путей) с множеством состояний мы ассоциируем распределение пропускной способности $${c_{е,i}, p_{е,i}}$$ (распределение расстояний $${d_{е,i}, p_{е,i}})$$ для $$е \in Е$$. Здесь $$p_{е,i}$$ - вероятность того, что $$е$$ будет иметь пропускную способность $$c_{е,i}$$ (расстояние $$d_{е,i}$$ ).
Иногда, при изучении
$$\psi(S)=\left\{\begin{aligned}1, если, когда\ S\ работает, а\ T-S\ не\ работает, система\ функционирует.\\0, если, когда\ S\ работает, а\ T-S\ не\ работает, система\ не\ функционирует\\\end{aligned}$$
Функция SBS является когерентной, если $$\psi (Т)=1, \psi (0)=0$$ и выполняется условие $$\psi (S'') \ge \psi (S)$$ для $$S'' \sup S$$. Последнее свойство означает, что выход из строя любого из компонентов может только повредить работе системы. Представляет интерес задача вычисления выражения:
$$Rel(SBS,p)=Pr[\psi (S)=1]$$, где $$S$$ - набор работающих компонентов,
если известен вид распределения $$\psi ()$$. Иногда мы рассматриваем задачи надежности, где $$р_{е}=p$$ для всех $$е$$, в этих случаях мы заменяем $$p$$ на $$p$$ в представленной выше нотации. Для произвольной стохастической когерентной двоичной системы ( SCBS -
Во многих приложениях могут отказывать как дуги, так и узлы. Следовательно, приходится изучать модели, способные реагировать и на отказы узлов, и на обрывы дуг. К счастью, для случая ориентированных сетей с помощью преобразования, показанного на рисунке 17.3, задачу с ненадежными ребрами и узлами можно свести к задаче с абсолютно надежными узлами и ненадежными ребрами. В каждом случае дуга, которая замещает узлы, наследует характеристики соответствующих узлов.
(рис 17.3) Замена ненадежного узлаВыше представленное обсуждение указывает, что с практической точки зрения предпочтительнее коды для анализа надежности ориентированной сети по отношению к кодам для неориентированного случая. При условии тщательного подбора входных данных ориентированные сетевые коды можно применять для анализа ориентированных и неориентированных моделей сети и задач с отказом и без отказа узлов.
При вычислении надежности приходится учитывать не только топологию сети, но и потоки данных в ней. Следовательно, анализ их сложности включает соображения, которые связаны с механизмом, используемым при рассмотрении проблем распознавания и оптимизации, но отличаются от него.
Чтобы наиболее простым образом свести задачи анализа надежности к более знакомым комбинаторным проблемам, рассмотрим частный случай задачи анализа надежности, которая возникает, когда все индивидуальные компоненты надежности равны, т.е. $$p_{i}$$ для всех $$i$$. В этом случае $$Rel(SBS,p)$$ можно записать в виде полинома по степеням $$p$$:
$$Rel(SBS,p)=\sum_{i=0}^m F_ip^{m-i}(1-p)^i$$
Этот полином является полиномом надежности. Задача по его вычислению называется задачей анализа функциональной надежности, где в качестве входных данных используется представление SBS, а на выходе получается вектор $${F_{i}}$$.
Общий член в полиноме надежности $$F_{i}p^{m-i}(1-p)^i$$ представляет собой вероятность того, что работает ровно $$m-i$$ компонентов сети и функционирует система в целом.
Результатом задачи по распознавания гамильтоновых контуров может быть либо "Да", если в графе содержатся контуры, либо "Нет", а результатом задачи подсчета гамильтоновых контуров в графе является число таких контуров. NP и NP-полный являются классами задач распознавания. Классы, соответствующие задачам подсчета, обозначаются #P и #P-полный. Очевидно, что любая задача подсчета, по крайней мере, не проще, чем соответствующая ей задача распознавания. Например, если известно число гамильтоновых контуров в графе, то не составит труда ответить на вопрос: "Больше ли нуля число гамильтоновых контуров?". Получается, что любая разновидность задачи подсчета из NP-полного класса часто является #P-полной. С другой стороны, существуют примеры задач распознавания, у которых время решения является полиномиальным, а их счетные аналоги относятся к NP-полному классу. Например, задача поиска точного соответствия в
Многие практические приложения требуют использования моделей с разной надежностью компонентов. В таких моделях все вероятности являются рациональными числами. Мы формулируем проблему анализа рациональной надежности следующим образом. В качестве входной информации используется представление SBS и для каждого компонента $$i$$ пара целых чисел $$a_{i}$$, $$b_{i}$$. На выходе получается пара целых чисел $$a$$ и $$b$$ таких, что $$a/b = Rel(SBS,{a_{i}/b_{i}})$$.
Мы начинаем с установления того, что, если конкретный анализ функциональной надежности является NP-сложными, тогда соответствующий анализ рациональной надежности является NP-сложными.
Для любой задачи анализа рациональной надежности r-Rel и соответствующей ей задачи анализа функциональной надежности, f-Rel за полиномиальное время может быть сведена к r-Rel.
В f-Rel входит представление функции SBS. На выходе необходимо получить набор коэффициентов $${F_{i}}$$ полинома надежности. Чтобы преобразовать f-Rel в r-Rel, выберем $$m+1$$ рациональное значение вероятности $$0 < p_{0} < p_{1} < ... < p_{m} < 1$$. Для $$j= 0,1,…,m$$ обозначим решения соответствующей задачи анализа рациональной надежности как $$r_{j} = Rel(SBS,p_{j})$$, где все компоненты надежности установлены равными $$p_{j}$$. Теперь мы можем записать систему уравнений:
$$\sum_{i=0}^m F_ip_j^{m-i}(1-p)^i=r_j$$ для $$j = 0,1,...,m$$.
Решив $$m+1$$ задачу анализа рациональной надежности, найдем $$p_{j}$$ и $$r_{j}$$. Получим систему из $$m+1$$ линейного уравнения с $$m+1$$ неизвестными $$F_{i}$$. Коэффициенты матрицы имеют свойство матрицы Вандермонде и, следовательно, матрица является невырожденной, таким образом, можно вычислить значения $$F_{i}$$.
Исследуем более детально вид полинома надежности для функций SCBS. Если задана SCBS, мы определяем значения:
Заметим сразу, что коэффициенты полинома надежности обладают следующими свойствами:
$$0\le F_i\le{n\choose i}$$, для $$i =0,1,...,m$$
$$F_i={n\choose i},$$ для $$i<c$$,
$$F_i={n\choose i}-n_c,$$ для $$i=c$$,
$$F_{i}=n_{l}$$ для $$i=m-l$$,
$$F_{i}=0$$ для $$i>m-l$$
Эти свойства означают, что, вычисляя полином надежности, мы легко определяем важные свойства SCBS функции. Например, исследовав полином надежности, мы сможем определить размер набора разрезов с минимальной мощностью. Таким образом, если задача распознавания набора разрезов с минимальной мощностью имеет сложность NP, то задача вычисления полинома надежности тоже имеет сложность NP.
Приведем результаты, полученные для сложности анализа
Набор путей с минимальной мощностью для k-терминальной меры является деревом Штейнера с минимальной мощностью. Известно, что задача распознавания является NP сложной для ориентированных и неориентированных сетей. Анализ функциональной и рациональной надежности для задачи анализа имеют NP сложность. Валиант [L.G.Valiant, "The complexity the enumeration and reliability problems", SIAM, J. Computing, 8 (1979), 410-421] приводит альтернативное доказательство, заключающееся в демонстрации того, что вычисление
$$SN(K)=\Sigma F_i = |{S : S ~соответствует ~субграфу, ~который ~содержит ~путь ~до ~каждого ~узла ~в ~К}|$$, имеет сложность $$NP$$. Здесь $$K$$ является набором терминалов.
Задачи распознавания минимального набора путей и разрезов, сопряженные с 2-терминальной мерой, являются проблемами кратчайшего пути и
Для ориентированной всетерминальной меры проблемы с наборами путей и разрезов с минимальной мощностью являются задачами поиска минимального покрывающего дерева и минимального s-ориентированного разреза, соответственно.
Обе эти задачи решаются за полиномиальное время. Задача подсчета минимального s-ориентированных разрезов имеет сложность NP. А это, в свою очередь, означает, что связанная с ней задача надежности имеет сложность NP. Для случая неориентированной меры задачи по распознаванию и подсчету минимального набора путей и разрезов имеют полиномиальную сложность. Однако задача вычисления общего члена в полиноме надежности имеет сложность NP, потому что задачи анализа надежности для неориентированного случая имеют сложность NP.
В свете этих негативных результатов, большинство исследований имело целью анализ структурированных сети. Самый широкий
Результаты данного раздела указывают на то, что полиномиальные алгоритмы для
Решение задач оценки надежности опирается на простое, но важное соображение: существует такое преобразование графа, которое не меняет значений различных мер надежности, и это преобразование может быть использовано для упрощения топологии сети, для которой нужно вычислить точное значение надежности. Наша первая цель - преобразования графов, которые приводят к упрощению.
Ребро или дуга, которые не входят ни в один из минимальных наборов путей, называется нерелевантным: работоспособность таких нерелевантных ребер не влияет на работу или отказ сети. Самым простым способом упрощающим преобразования графа является удаление нерелевантных ребер. По определению, такое преобразование не меняет меру надежности. Чтобы преобразование имело практическое применение для сети, время его эффективной реализации должно быть полиномиальным. Для все-, k- и 2-терминальных мер надежности петли всегда являются нерелевантными. А для k- и 2- терминальных мер надежности нерелевантными являются также все оконечные ребра, не имеющие терминального окончания. Такие ребра легко находить и удалять. В случае ориентированных задач надежности поиск нерелевантных дуг отнюдь не простая задача. Было показано, что задача нахождения нерелевантных дуг в случае $$(s,t)$$ -связанности имеет сложность NP, в то время как общая неориентированная задача допускает эффективное решение.
Проблема
Читатели, знакомые с телекоммуникационными протоколами, могут заинтересоваться тем, как писать прикладные программы для работы с пакетами. В большинстве случаев вполне достаточно воспользоваться стандартной библиотекой для работы с сокетами. В особых случаях может возникнуть необходимость получения данных непосредственно от сетевого интерфейса. Прикладная программа взаимодействует с драйвером сетевого интерфейса. Ethernet-интерфейс, как и всякий другой, содержит несколько статусных управляющих регистров (
Следует иметь в виду, что разные интерфейсы могут иметь разное число
(рис 17.4) Структура CSR-регистра интерфейса (CSR0)
| Init | инициализация (initialize) |
|---|---|
| Strt | старт |
| Stop | стоп |
| Tdnd | запрос передачи (transmit demand) |
| Txon | включение передачи |
| Rxon | включение приема |
| Inea | разрешение прерываний ( |
| Intr | прерывание |
| Idon | инициализация выполнена (стирание записью 1) |
| Tint | прерывание при передаче (стирание записью 1) |
| Rint | прерывание при чтении (стирание записью 1) |
| Merr | ошибка при тайм-ауте на шине (стирание записью 1) |
| Miss | нет буфера для приема (стирание записью 1) |
| Cerr | ошибка из-за столкновения (стирание записью 1) |
| Babl | тайм-аут при передаче (стирание записью 1) |
| Err | ошибка типа Babl, Cerr, Miss, Merr (только для чтения) |
(рис 17.4b) CSR1
CSR2 (доступ разрешен при CSR0[stop] = 1)
(рис 17.4c) CSR2
| Bcon | 0 = <0:7> перестановка байтов адресов |
|---|---|
| Acon | 0 = |
| Bswp | 0 = /bm1, bm0, /hold; |
(рис 17.4d) Структура переменных init_mode (смещение = 0) имеет вид
(рис 17.5) Структура переменных init_mode| Drx | запрет приема |
|---|---|
| Dtx | запрет передачи |
| Loop | цикл |
| Dtcr | запрет передачи crc |
| Coll | столкновение |
| Drty | запрет повторов |
| Intl | внутренний цикл |
| Prom | режим приема всех пакетов (promiscuous mode) |
Приведенное выше описание регистров интерфейса не является единственно возможным. Структура драйверов варьируется для разных операционных систем. Для системных программистов полезно иметь возможность настраивать драйвер или непосредственно интерфейс на определенный режим, например, на прием всех пакетов, проходящих по кабельному сегменту. Последнее может представлять интерес в диагностических целях, так как вслед за пакетным драйвером загружается Etherdrv, Winsock или winpkt и т.д., блокирующие режим приема всех пакетов (mode=6).
Существует множество пакетных драйверов. Можно обнаружить несколько модификаций для одного и того же типа интерфейса. Эти драйверы могут быть ориентированы на работу в разных программных средах и иметь разные возможности. Драйвер может использовать минимум возможностей интерфейса (базовый уровень), реализовать более широкий набор функций (мультикастинг, сбор статистики и т.д.) или поддерживать практически все, на что способен данный интерфейс. В последнем случае он занимает больше места в памяти. При написании программы следует помнить, что порядок байтов в Ethernet противоположен тому, который используется в вашей машине.
Пакетные драйверы используют программные прерывания в интервале $$0x60 - 0x80$$. Следует сразу заметить, что не все прерывания из этого списка свободны, и при конфигурировании системы следует проявлять осмотрительность. Для того, чтобы избежать конфликтов с другими внешними устройствами, предусматривается возможность реконфигурации прерываний. Практически все драйверы могут работать с различными протоколами (TCP/IP, OSI и др.). Решить задачу мультиплексирования на связном уровне помогает процедура access_type, которая обеспечивает доступ для пакетов определенного типа.
Все функции реализуются с помощью обращения к драйверу с набором определенных параметров. Каждому типу используемого сетевого протокола, с которым работает интерфейс, ставится в соответствие целочисленный указатель (handle), получаемый с помощью процедуры access_type. Выполнимость драйвером тех или иных операций может быть выяснена с помощью запроса driver_info.
Следует помнить, что порядок байтов в PC и в некоторых сетях, включая Ethernet, не совпадает. Мультикастинг адресация реализуется на уровне L2, при этом список мультикаст-адресов подписки пользователей хранится в сетевом интерфейсе и может быть прочитан по запросу.
Современные сетевые интерфейсы производят подсчет принятых и переданных октетов, количество различного типа ошибок и пр. Получение статистических данных об ошибках и трафике через данный интерфейс осуществляется с помощью запроса get_statistics(handle). Статистические данные имеют вид целых 32-разрядных чисел.
Практически все интерфейсы допускают смену МАС-адреса, прошитого изготовителем интерфейса.
Ни один проект крупной сети со сложной топологией в настоящее время не обходится без исчерпывающего моделирования будущей сети. Программы, выполняющие эту задачу, достаточно сложны и дороги. Целью моделирования является определение оптимальной топологии, адекватный выбор сетевого оборудования, определение рабочих характеристик сети и возможных этапов будущего развития. Ведь сеть, слишком точно оптимизированная для решений задач текущего момента, может потребовать серьезных переделок в будущем. Моделирование используется для исследования характеристик новых модификаций протоколов, методы работы с очередями, для оптимизации параметров качества обслуживания.
На модели можно опробовать влияние всплесков загрузки, воздействие большого потока широковещательных запросов или реализовать режим коллапса (для Ethernet), что вряд ли кто-то может себе позволить в работающей сети. В процессе моделирования выясняются следующие параметры:
Перечисленные задачи предъявляют различные требования к программам. В одних случаях достаточно провести моделирование на физическом (MAC) уровне, в других нужен уже уровень транспортных протоколов (например, UDP и TCP), а для наиболее сложных задач нужно воспроизвести поведение прикладных программ. Все это должно приниматься во внимание при выборе или разработке моделирующей программы. Ведь нужно учесть, что ваша машина должна в той или иной мере воспроизвести действия всех машин в моделируемой сети. Таким образом, машина эта должна быть достаточно быстродействующей, и, несмотря на это, моделирование одной секунды работы сети может занять при определенных условиях не один час.
Задачи моделирования обработки очередей в виртуальном канале с целью оценки параметров качества облуживания требуют не столь значительных ресурсов. Но с учетом перебора возможных значений параметров конфигурации это также может занять много часов.
Результаты моделирования должны иметь точность 10-20%, этого достаточно для большинства целей и не требует слишком много машинного времени. Следует иметь в виду, что для моделирования поведения реальной сети надо знать все ее рабочие параметры: длины кабеля от концентратора до конкретной ЭВМ, задержки используемых кабелей, задержки концентраторов (этот параметр часто отсутствует в документации и его придется брать из документации на сетевой протокол, например, из IEEE 802.3). Параметры могут быть определены и прямым измерением. Чем точнее вы воспроизводите поведение сети, тем больше машинного времени это потребует. Кроме того, вам предстоит сделать некоторые предположения относительно распределения загрузки для конкретных ЭВМ и других сетевых элементов, задержек в переключателях, мостах, времени обработки запросов в серверах. Здесь нужно учитывать и характер решаемых на ЭВМ задач: www/ftp-сервер или обычная персональная рабочая станция создают различные сетевые трафики. Определенное влияние на результат могут оказывать и используемые ОС. В случае моделирования реальной сети можно произвести соответствующие измерения, что иногда тоже не слишком просто. Учитывая сложность моделирования на одной ординарной ЭВМ, следует ограничиваться моделированием не более чем одной минуты для каждого из наборов параметров (этого времени достаточно для копирования практически любого файла через локальную сеть). Исключение может составлять моделирование внешнего трафика, но в этом случае весь локальный трафик должен рассматриваться как фоновый.
Современные распределенные технологии дают новые возможности для решения задач моделирования.
Определение характеристик сети до того, как она будет введена в эксплуатацию, имеет первостепенное значение. Это позволяет отрегулировать характеристики локальной сети на стадии проектирования. Решение этой проблемы возможно путем аналитического или статистического моделирования. По существу, в данном разделе речь идет об описании сети в рамках теории массового обслуживания.
Аналитическая модель сети представляет собой совокупность математических соотношений, связывающих между собой входные и выходные характеристики сети. При выводе таких соотношений приходится пренебрегать какими-то малосущественными деталями или обстоятельствами.
Телекоммуникационная сеть при некотором упрощении может быть представлена в виде совокупности процессоров (узлов), соединенных каналами связи. Сообщение, пришедшее в узел, некоторое время пребывает в очереди до того, как оно будет обработано. Время передачи или полное время задержки сообщения $$D$$ равно:
$$D = T_p + S + W$$,
где $$T_p$$, $$S$$ и $$W$$ соответственно - время распространения, время обслуживания и время ожидания. Одной из задач аналитического моделирование является определение среднего значения $$D$$. При больших загрузках основной вклад дает ожидание обслуживания $$W$$. Для описания очередей в дальнейшем будет использована нотация Д. Дж. Кенделла:
$$A/B/C/K/m/z$$,
где $$А$$ - процесс прибытия: $$В$$ - процесс обслуживания; $$С$$ - число серверов (узлов); $$К$$ - максимальный размер очереди (по умолчанию - $$\infty$$ ); $$m$$ - число клиентов (по умолчанию - $$\infty$$ ); $$z$$ - схема работы буфера (по умолчанию FIFO). Буквы $$А$$ и $$В$$ представляют процессы прихода и обслуживания и обычно заменяются следующими буквами, которые характеризуют закон, соответствующий распределения событий:
Наиболее распространенными схемами работы буферов являются FIFO (First-In-First-Out), LIFO (Last-In-First-Out) и FIRO (First-In-Random-Out). Например, запись $$M/M/2$$ означает очередь, для которой времена прихода и обслуживания соответствует экспоненциальному распределению, имеется два сервера, длина очереди и число клиентов могут быть сколь угодно большими, а буфер работает по схеме FIFO. Среднее значение длины очереди $$Q$$ при заданной средней входной частоте сообщений $$\lambda$$ и среднем времени ожидания $$W$$ определяется на основе
$$\vec Q=\lambda \vec W$$
Для варианта очереди $$M/G/1$$ входной процесс характеризуется
$$p(k)=\frac{\left(\lambda t\right)^k}{k!}e^{-\lambda t}$$ , $$k=0,1,2,..$$.
Пусть $$N$$ - число клиентов в системе, $$Q$$ - число клиентов в очереди, и пусть вероятность того, что входящий клиент обнаружит $$j$$ других клиентов, равна:
$$П_j=P[n=j], j=0,1,2,... \sum_{j=0}^\infty П_j=1; П_0=1-\rho;\rho=\lambda\tau$$
Тогда среднее время ожидания $$w$$:
$$\overline{W}=\frac{\overline{Q}}{\lambda}=\frac{\rho\tau}{2(1-\rho)}(1+\frac{\sigma^2}{\tau^2})$$
(
$$\sigma$$ - среднеквадратичное отклонение для распределения времени обслуживания.
Для варианта очереди $$M/G/1 H(t) = P[X \le t] = 1 - e^{-\mu t}$$ ( $$H$$ - функция распределения времени обслуживания). Откуда следует $$\sigma^2 = \tau^2$$.
$$\overline{W}=\frac{\rho\tau}{(1-\rho)}$$
Для варианта очереди $$m/d/1$$ время обслуживания постоянно, а среднее время ожидания составляет:
$$\overline{W}=\frac{\rho\tau}{2(1-\rho)}$$
Аналитическая модель для сетей Ethernet (CSMA-CD) разработана Лэмом (S.S.Lam: "A Carrier Sense Multiple Access Protocol for Local Networks,"
$$\overline{D}=\frac{\lambda [S^2+(4e+2)\tau S+5\tau^2+4e(2e-1)\tau^2]}{2(1-\lambda [\overline{S}+\tau+2e\tau])}-\frac{(1-e^{-2\lambda\tau})(e+\lambda\tau-2\lambda\tau e)}{\lambda e[F(\lambda)e^{-(1+\lambda\tau)}+e^{-2\lambda\tau}-1]}+2\tau e+\overline{S}+\tau /3$$
где $$е$$ - основание натурального логарифма, $$\tau$$ - задержка распространения сигнала в сети. $$\vec S$$ и $$\vec S^2$$ - соответственно первый и второй моменты распределения передачи или обслуживания сообщения. $$f(\lambda)$$ преобразование Лапласа для распределения времени передачи сообщения. Следовательно,$$F(\lambda)=\int\limits_0^\infty f(t)e^{-\lambda t},dt$$ , а для сообщений постоянной длины $$f(\lambda)=e^{-\rho}, \vec S^2=\vec S^2$$, где $$\pi =\lambda \vec S$$. Для экспоненциального распределения длин сообщений:
$$F(\lambda)=\frac{1}{1+\rho}, \overline{S^2}=2\overline{S}^2$$
Рассмотрим вариант сети Ethernet на основе концентратора-переключателя с числом каналов $$N$$. При этом будет предполагаться, что сообщения на входе всех узлов имеют
$$\overline{W}=\hat{y}+\frac{\lambda\hat{y}^2}{2(1-\rho)},$$
где $$\hat{y}=[1+(N-2)\rho G]\overline{S}$$,
$$\hat{y}^2=2[1+(N-2)\rho G+(N-2)(N-3)\rho^2G^2]\overline{S^2}$$
$$\rho=\frac{\lambda S}{1-(N-2)G\lambda\overline{S}}$$ , $$\lambda=\lambda_i$$, а $$G=1/(N-1)$$ равно вероятности того, что сообщение отправителя $$i$$ направлено получателю $$j$$. Требование стабильности $$\rho \le 1$$ обязывает, чтобы $$\lambda \vec S \le (N-1)(2N-3)$$
Для больших $$n$$ это приводит к $$\lambda \vec S \le 1/2$$.
Среднее время распространения сообщения в сети равно $$\vec T_p = \tau,$$ где $$\tau$$ равно $$RTT$$.
$$\overline{D}=\hat{y}+\frac{\lambda\hat{y}^2}{2(1-\rho)}+\overline{S}+\tau$$
Особое место занимает моделирование систем работы с очередями. Эти задачи стали особенно актуальными в связи необходимостью получения гарантированных параметров качества обслуживания. Этот тип моделирования можно реализовать с помощью общедоступной программы и http://www-mash.cs.berkeley.edu/ns.)
Симуляционное (статистическое) моделирование служит для анализа системы с целью выявления критических элементов сети. Этот тип моделирования используется также для предсказания будущих характеристик системы. Такое моделирование может осуществляться с использованием специализированных языков симулирования и требует априорного знания относительно статистических свойств системы в целом и составляющих ее элементов. Процесс моделирования включат в себя формирование модели, отладку моделирующей программы и проверку корректности выбранной модели. Последний этап обычно состоит из сравнения расчетных результатов с экспериментальными данными, полученными для реальной сети.
При статистическом моделировании необходимо задать ряд временных характеристик, например: таблица 17.1.
| Системное время | Интервал от момента генерации сообщения до получения его адресатом, включая ожидание в очереди |
|---|---|
| Время ожидания | Промежуток времени от приема сообщения сетевым интерфейсом до обработки его процессором |
| Время распространения | Задержка передачи сообщения от одного сетевого интерфейса до другого |
Полный список таких временных характеристик включает в себя значительно больше величин. В процессе моделирования рассчитываются следующие параметры: таблица 17.2.
| Статистика очередей |
|---|
| Пиковая длина очереди |
| Среднеквадратичное отклонение длины очереди от среднего значения |
| Статистика времени ожидания |
| Среднее время ожидания |
| Максимальное время ожидания |
| Среднеквадратичное отклонение времени ожидания |
| Статистика системного времени |
| Среднее системное время |
| Максимальное системное время |
| Среднеквадратичное отклонение системного времени |
| Полное число сообщений в статистике системного времени |
| Пиковое значение числа системных сообщений |
| Среднеквадратичное отклонение числа системных сообщений |
| Статистика потерь сообщений |
| Полное число потерянных сообщений |
| Частота потери сообщений |
| Доля потерь из-за переполнения очереди |
| Доля потерь из-за таймаутов |
Разумеется, реальный перечень вычисляемых параметров может быть существенно шире и определяется конкретными целями расчетов. Рассмотрим частную задачу определения среднего числа связей между процессорами (узлами). Предполагается, что полное число узлов равно $$N$$, а схема соединения узлов соответствует изображенной на рис 17.1.
(рис 17.1) Среднее расстояние от произвольного узла до всех остальных узлов равно $$D(N+1)/3$$, где $$D$$ - расстояние между соседними узлами (предполагается константой).
Возможны разные подходы к моделированию. Классический подход заключается в воспроизведении событий в сети как можно точнее и поэтапном моделировании последствий этих событий. В реальной жизни события могут происходить одновременно в различных точках сети. По этой причине для моделирования идеально подошел бы многопроцессорный компьютер, где можно воспроизводить любое число процессов одновременно (современные распределенные вычислительные системы для решения таких задач подходят идеально). В любом случае необходимо выбрать некоторый постоянный временной интервал и считать, что события произошли одновременно, если расстояние между ними меньше этого интервала. Для сетей типа Ethernet таким временным интервалом может быть бит-такт (для 10-мегагбитного Ethernet это 100нс). Понятно, что это уже отступление от реальности (ведь задержки в сетевом кабеле не кратны этому времени), но не слишком значительное. Надо сказать, что такого рода предположений при моделировании приходится делать много. По этой причине крайне важно сравнивать результаты моделирования с данными, полученными для реальной сети. Если отличия лежат в пределах 10-20%, можно считать, что сделанные предположения не увели программу слишком далеко от жизни и ею можно пользоваться для расчетов. Рассмотренный выше подход пригоден для моделирования сетевого коллапса, так как скорость расчетов здесь зависит от числа узлов и почти не зависит от сетевой загрузки.
Другим подходом может стать метод, где для каждого логического сегмента (зоны столкновений) сначала моделируется очередь событий. При этом в каждой рабочей станции моделируется последовательность пакетов, ожидающих отправки. Эта очередь может время от времени модифицироваться, например, при получении ЭВМ пакета извне и необходимости послать на него отклик. После того как такая очередь для каждого сетевого объекта (сюда, помимо ЭВМ, входят мосты, переключатели и маршрутизаторы) построена, запускается программа отправки пакетов: выбирается самый первый по времени пакет (ожидающий дольше других) и проверяются для него условия начала передачи (отсутствие несущей на входе сетевого интерфейса в данный момент и в течение предыдущих 96 бит-тактов). Если условия отправки выполнены, пакет посылается в сеть. Вычисляются моменты достижения им всех узлов данного логического сегмента, проверяются условия его столкновения с другими пакетами. Следует заметить, что в этом подходе снимаются ограничения дискретности временной шкалы, использованной в предыдущем "классическом" подходе. Этот подход позволяет заметно ускорить расчеты при большом числе узлов, но малой загрузке сети. Проблемы реализации данной концепции моделирования связаны с обслуживанием довольно сложного списка, который описывает очередь пакетов, ожидающих отправки. В структуру этого списка включается и описание ситуации в сети на данный временной период. Дополнительные трудности сопряжены с поведением мостов, переключателей и маршрутизаторов, так как они могут вставлять в очередь дополнительные элементы, требующие немедленного обслуживания. Аналогичные вставки в очередь будут вызывать полученные станцией пакеты ICMP или TCP, требующие откликов. Причем такое вставление в очередь асинхронно по отношению к процедуре "отправки" пакетов. Очередь для всей локальной сети может быть единой, тогда пакеты разных логических сегментов должны быть помечены определенными флагами. При переходе из сегмента в сегмент флаг будет меняться. Возможно и построение независимых очередей для каждого из логических сетевых сегментов.
Данный метод был использован студентом ТСС МФТИ Алексеем Овчаровым в его магистрской диссертации (2000 год) для определения свойств фрагмента сети в условиях, близких к предельным (загрузка на уровне 70-100%). Такие режимы трудно реализовать на практике без нанесения серьезного ущерба клиентам сети. Результаты расчета представлены на рис 17.2.
Целью моделирования является определение зависимости пропускной способности сети и вероятности потери пакета от загрузки, числа узлов в сети, длины пакета и размера области столкновений.
Исходные данные о структуре и параметрах сети берутся из базы данных. Ряд параметров сети задаются конфигурационным файлом (профайлом). Сюда могут записываться емкость буфера интерфейса и драйвера, время задержки обработки запроса (хотя в общем случае эта величина может также иметь распределение) и т.д.. К таким параметрам относятся также: MTU,
Сеть разбивается на логические сегменты, в каждом из которых работает независимая синхронизация процессов (хотя эти процессы и влияют друг на друга через мосты, переключатели и маршрутизаторы).
(рис 17.2) Зависимость вероятности потери пакета в процентах от загрузки фрагмента сетиПолное моделирование сети с учетом рабочих приложений предполагает использование следующих распределений:
Последние два пункта существенным образом коррелированы с первым, так как используемые протоколы зависят от приложения, а активность узла может определяться, например, длиной пересылаемого файла. По этой причине при полномасштабном моделировании сначала определяется, что собирается делать рабочая станция или сервер (с учетом распределения по приложениям определяется характер задачи: FTP, MS explorer и т.д.). Затем разыгрываются параметры задания (длина файла, удаленность объекта и пр.), а уже на основе этого формируется фрагмент очереди пакетов.
Задача первого этапа: проверка пропускной способности при вариации загрузки и длин пакетов, подсчет числа столкновений (если они возможны), проверка влияния размера буфера сетевого интерфейса на пропускную способность (влияние размера буфера переключателей по пути до адресата).
Исходные данные для первого этапа:
Структура описания каждого из узлов включает в себя (формируется с учетом будущего расширения):
Формат описания топологии сети (список) Элемент списка:
Процесс посылки пакета включает в себя (в соответствии с требованиями документа IEEE 802.3):
Попытка начала передачи предполагает проверку:
Процесс приема предполагает:
Центральный менеджер осуществляет:
Равномерное распределение по времени
Для каждого узла устанавливается определенная средняя частота посылки пакетов. Время начала сессии предполагается случайным. Средняя частота может быть задана равной для всех узлов.
Минимальный средний период посылки пакетов определяется в бит-тактах и должен быть больше 512 бит-тактов. Понятно, что пока узел осуществляет передачу, он не может пытаться передать новый пакет. По этой причине частота посылки пакетов однозначно определяется паузой между концом предыдущего пакета и началом нового $$(\delta)$$. Среднее значение периода посылки пакетов равно $$Т_{пакета}+96(бит-тактов)+\delta$$ (значение $$\delta$$ величина в общем случае статистическая). Для каждого узла задается значение $$\delta$$ (сначала равное для всех узлов). Если предположить равномерное распределение вероятности, передача пакета может начаться в любой бит-такт с равной вероятностью.
При определении того, пытаться ли начинать передачу в данный бит-такт, будет произведена проверка условия:
$$rndm <1/\delta$$ (выполнение условия предполагает попытку начала передачи).
Если вероятность прихода $$n$$ пакетов на время $$t$$ распределена по закону Пуассона:
$$P=\frac{(Lt)^n e^{Lt}}{n!}$$, где $$L$$ - средняя частота следования событий, то реальное время между событиями может быть определено как $$\tau = -T ln(R)$$. $$R$$ - случайное число $$0 \le R \le 1$$, а $$T = 1/L$$.
Результатами моделирования могут являться (фиксируются отдельно для каждого набора входных параметров): таблица 17.3.
| 1. | Вероятность потери пакета для логического сегмента и каждой из рабочих станций |
|---|---|
| 2. | Пропускная способность серверов для каждого из логических сегментов (путь сервер -> логический сегмент) |
| 3. | Вероятность столкновения для каждого логического сегмента и каждой рабочей станции |
| 4. | Распределение потоков по логическим сегментам (и рабочим станциям) независимо для каждого направления (вход и выход) |
| 5. | Распределение потоков для всех входов/выходов переключателей мостов и маршрутизаторов |
| 6. | Доля вспомогательного трафика (ICMP, SNMP, отклики TCP, широковещательные запросы и т.д.) по отношению к информационному потоку для различных узлов сети (серверов, маршрутизаторов) |
| 7. | Уровень широковещательного трафика для каждого из логических сегментов |
Набор параметров, распределений и алгоритм моделирования сильно зависит от стоящей задачи.
Современный Интернет насчитывает десятки миллионов серверов и сотни миллионов рабочих станций. Данная технология стала широко использоваться в информационных системах и бизнесе, именно по этой причине проблема надежности сетей становится все более актуальной. Ведь совсем не безразлично, получит ли человек своевременно отклик от банкомата, произведет ли клиент покупку, будут ли корректно введены данные в систему навигации ракеты и т.д.
Но прежде чем поставить вопрос о надежности Интернет или даже локальной сети, нужно определить некоторые базовые понятия. Надежность всякой системы определяется надежностью составляющих ее элементов. А надежность элементов задается временем наработки на отказ или вероятностью отказа за оговоренный период времени. Надежности разных элементов могут отличаться существенно. В результате как усредненные значения надежности, так и распределения вероятности отказов разных сетевых устройств могут варьироваться в очень широких пределах. Во многих случаях надежность и распределения надежности определяются эмпирически.
И если требование надежности определить как работоспособность всех элементов, надежность Интернета окажется равной нулю, ведь всегда найдется неисправный или отключенный узел или рабочая станция. Если же определить надежность системы как возможность коммуникации между, скажем, 1000 каких-либо узлов или рабочих станций, то надежность Интернет окажется практически равной единице. Конечно, если ваша рабочая станция не попадет в число этих 1000 узлов, вы вряд ли согласитесь с утверждением абсолютной надежности. Понятно поэтому, что оба определения совершенно неприемлемы. Не нужно думать, что случай оценки надежности локальной сети, содержащей, например, 100 рабочих станций, много проще.
Здесь нужно будет определить, что такое отказ. Современная персональная ЭВМ - достаточно сложный прибор, содержащий несколько внешних устройств, один или более процессоров, оперативную память, сетевой интерфейс, ОС и т.д. Что следует считать отказом рабочей станции? Выход из строя источника питания, повисание ОС, разрушение системного диска, отказ сетевой карты и пр. или что-то еще, например, ошибка в прикладной программе или выдергивание уборщицей кабеля из розетки? Надо сразу сказать, что однозначного ответа на этот вопрос нет, все зависит от обстоятельств.
Прежде чем переходить к теоретической части, посмотрим, что можно сделать для улучшения надежности сети с практической точки зрения. Конечно, этому будет способствовать использование RAID-систем жестких дисков, катастрофоустойчивой системы дублирования резервных копий дисков в удаленных узлах, размещенных в разных зданиях, и т.д.. Но не следует снимать со счета дублирование базовых серверов: DNS, NTP (если они нужны), почтовых серверов, серверов баз данных и пр. Внутри локальной сети повышению надежности может способствовать применение протокола STP, который может автоматически обеспечить обход отказавшего участка LAN (если применение динамического протокола внутренней маршрутизации невозможно или нежелательно, например, по соображениям безопасности). Во многих случаях крайне важно задублировать шлюз сети, ведущий в Интернет, так как его отказ оставит всех пользователей сети без связи. Компания CISCO и многие другие фирмы разработали протоколы резервирования маршрутизаторов. В этих протоколах два или более устройств совместно используют виртуальные IP и МАС-адреса, которые указаны в сетевом сегменте для шлюза по умолчанию. Для реализации такой схемы существует три протокола:
Компания CISCO поддерживает только протокол
При рассмотрении
Выход из строя рабочей станции (терминальный узел) создает проблемы ее пользователю, остальные пользователи Интернет, скорее всего, этого не заметят, но отказ сервера скажется на работе всех его клиентов, в том числе и удаленных. Выход же из строя маршрутизатора (если это транзитный узел) может оказать влияние на работу целого региона. Отсюда видно, что отдельные узлы могут по-разному влиять на работу сети в целом. Даже в классе серверов можно выделить группы разного влияния на уровень надежности. Например, отказ сервера IN-ADDR.
Этим список факторов, влияющих на надежность, не исчерпывается. Если пользователь не может получить доступ к определенному сетевому ресурсу, это очень часто связано не с отказом оборудования или программы, а просто с перегрузкой одного из участков сети по дороге к указанному ресурсу (некомпетентность пользователя в данном анализе не рассматривается). Здесь имеется в виду не только ограничение пропускной способности, но и возможное увеличение задержки доставки, что достаточно критично в случае, например, IP-телефонии или видео-конференций. Таким образом, параметры надежности часто зависят от вектора загрузок (список значений загрузок каналов, влияющих на доступ и качество обслуживания). По этой причине, формулируя задачу оценки надежности, нужно определить, какие из параметров важны: связность, пропускная способность, время восстановления связности или минимизация задержек обслуживания.
Если мы рассмотрим в качестве примера полный граф с четырьмя узлами, размещенными в вершинах квадрата (6 ребер), то расчет связности такой сети будет включать комбинаторику перебора ребер и учет распределения вероятности обрыва каждой из связей. Нетрудно понять, что если попытаться проанализировать надежность структурированной локальной сети с сотней ЭВМ, задача окажется на много порядков сложней, я уже не говорю об Интернете в целом. Обычно множественность в таких задачах равна $$N$$! (где $$N$$ - число узлов в графе связей). В любом случае в качестве исходных данных должны использоваться значения надежности отдельных узлов и каналов, вычисленные или измеренные с учетом тех факторов, влияние которых вы хотите учесть. Во многих случаях бывает нужно сделать предположение относительно распределения
По этой причине, прежде чем писать и запускать программу расчета надежности сети надо научиться оценивать: а хватит ли имеющихся вычислительных ресурсов для решения поставленной задачи в текущем тысячелетии. Для этого существует математические методы оценки сложности алгоритмов [ А. V. AHO, J. D.Ullman, "Foundation of Computer Science", Computer Science Press, 1992, или V.V. Leeuwen, "Algorithms and Complexity", The MIT Cambridge, Massachusetts, Elsevier Science Publishers, 1990 ]. Из-за сложности прямых вычислений многие исследователи ограничиваются лишь оценкой возможных границ надежности. На практике, даже используя самые производительные вычислительные системы, можно оценить надежность сети с ограниченным числом узлов. Для больших сетей доступными являются лишь оценки нижней или верхней границы надежности.
За отправную точку примем сеть $$G =(V,E)$$, в которой $$V$$ - набор узлов или вершин графа сети, а $$Е$$ - набор неориентированных ребер или набор ориентированных дуг. Большинство исследований по
$$Rel(G,s,K,p)=Pr[существует~хотя~бы~один~работающий~путь~от~s~до~каждого~ узла~из~набора~К]$$
То есть, надежность сети с графом $$G$$ для набора узлов $$К$$ и выбранного узла $$s$$ при вероятности иметь надежную связь для всех ребер графа $$p$$ равна вероятности того, что узел $$s$$ имеет хотя бы один доступный путь до каждого из узлов $$К$$. Обычно эта величина соответствует определенному временному интервалу. Следует помнить, что для локальных сетей не может быть двух путей от $$s$$ до любого из узлов $$K$$.
Существует два важных частных случая мер: 2-терминальная мера с $$|К|=2$$ и всетерминальная мера, где $$К=V$$. Эти меры принято обозначать $$Rel_2(G,s,p)$$ и $$Rel_А(G,s,p)$$, соответственно ( $$Rel$$ - надежность).
Читателю, рассчитывающему найти какие-то формулы, подставив в которые число узлов,
В самых первых моделях ЭВМ память организовывалась из множества отдельно стоящих реле и вакуумных ламп. Компьютерные системы, которые отказывали при выходе из строя одного из их элементов, были крайне ненадежны, так как
Первые активные разработки в области систем повышенной надежности проводились для систем, чей отказ мог повлечь катастрофы и гибель людей. Примерами таких систем является авиа- и космические системы, управление ядерными реакторами, системы управления оборонными комплексами. В последнее время широко распространено мнение, что в ряде промышленных отраслей с экономической точки зрения выгодней применять системы повышенной надежности. Например, это экономически оправданно в телекоммуникационных сетях, банковских системах - сетях подтверждения кредитоспособности и в системах оформления заказов.
Основной целью исследований в области
В результате расчетов надежности упрощенной модели сети могут быть выработаны рекомендации и критерии по выбору топологии и структуры, которые помогут достичь более высокой надежности.
Первые сети с коммутацией пакетов были разработаны в 1960-х. Их создали с целью поделить высокоскоростные каналы между большим количеством пользователей. Трафик, порождаемый одним пользователем, имеет много всплесков и пауз. Трафик нескольких пользователей можно динамически разнести по времени и передавать по одному соединению. ARPANET была первой крупной сетью с коммутацией пакетов. Большая часть исследований в области
При сравнении ARPANET с коммерческими опорными сетями с коммутацией пакетов, используемыми в 1980-х годах, такими, как Telnet и Tymnet, ясно, что коммерческие сети много компактнее. Как следствие, вероятность нарушения связанности в коммерческих сетях много меньше, но, как правило, загрузка каналов там достаточно высока. Отсюда напрашивается вывод, что следует более детально вычислять параметры
Сегодня сеть ArpaNet может показаться топологически достаточно простой, но даже для такой сети расчет надежности отнюдь не простая задача даже при оценке простой связности.
Для того чтобы минимизировать перебор, можно использовать различные методы эквивалентного преобразования графа сети, минимизирующего число узлов или ребер при сохранении значения надежности.
На сегодняшний день крупнейшие телекоммуникационные сети являются
Особый случай сетей с коммутацией каналов возникает при проектировании связных сетей в параллельных вычислительных архитектурах для объединения параллельных процессоров и памяти. Модели, основанные на связанности сети, одинаково применимы и к отказам по причине перегрузок, и к отказам в работе сетевых узлов. Эквивалентом производительности системы считается среднее значение параметра связанности сети между ее входной и выходной точками.
Оптические кабели - одно из последних достижений современной технологии. Телекоммуникационные сети всего мира переводятся на использование этой техники (смотри, например, T. Flanagan, "Fiber Network Survivability" IEEE Communication Magazine 28 (1990) 46-53 ). Основным преимуществом оптической среды передачи по сравнению с передачей по медным кабелям является существенный рост пропускной способности и снижение уровня шумов. Именно по этой причине многие телефонные сети общего пользования осуществляют быстрый переход на оптику. Как, однако, оказалось, в проблематике надежности сетей существуют более важные проблемы, и именно их следует изучать. А именно: пропускная способность оптоволоконных сетей чрезвычайно высока, поэтому структура таких сетей, в отличие от обычных, имеет более распределенный характер.
Старые сети были более разветвленными и имели большое число связей, вопрос
К оптическим каналам добавляют каналы-дублеры с возможностью переключения между основным и дублирующим каналом. При этом желательно, чтобы трассы их прокладки не совпадали (по стране рыщут бульдозеры и экскаваторы, так и норовящие порвать любые кабели). В результате мы сможем применить к оптической сети уже имеющиеся методы оценки надежности.
Компьютерная система называется устойчивой к сбоям, если при отказе одного из ее компонентов она продолжает функционировать. В 1970-х годах такие компьютеры использовались в качестве переключателей в опорных телекоммуникационных сетях. И сегодня они широко применяются во многих приложениях. Позже были разработаны параллельные вычислительные архитектуры. С целью повышения производительности параллельные ЭВМ собирались из множества однотипных элементов. Однако параллельные архитектуры имеют также и повышенные характеристики надежности. Обычно такие отказоустойчивые и параллельные компьютерные системы при анализе надежности моделировались как сети. Поскольку большая часть исследований по оценке
Существует большое разнообразие сетевых моделей, часть из них применяется в других областях науки. Во всех анализируемых случаях сеть поддерживает работу многих пользователей, трафик каждого из них следует через сеть одним или несколькими маршрутами. Обычно подразумевается, что можно произвести более точную оценку надежности, если учесть в расчетах параметры маршрутизации. В завершение нужно отметить, что нужно учитывать величины пропускной способности. Одна из наиболее интересных областей применения - городские сети наземного транспорта. В этом контексте инциденты, такие, как аварии на автомагистралях, вызывают отказ сетевых узлов или дуг. Хотя нарушения связанности в сети городского транспорта происходят очень редко, все же вполне типично, когда отказ узла или связи вызывает ситуацию значительной перегрузки.
Наконец, применение многих средств оценки надежности сети, которые разработаны для мер, базирующихся на связности, распространяется на совершенно другие проблемы надежности, например, в сфере диспетчеризации и распределения ресурсов (в том числе операционных систем или сетей электроснабжения).
Механизмы потерь и причины их возникновения относительно хорошо изучены в классической теории надежности. Например, в электронных системах деградация узлов происходит, когда они подвергаются непрерывному тепловому воздействию. В результате такие узлы случайным образом выходят из строя. Анализ надежности для подобных систем обычно включает в себя изучение этих случайных процессов и параметры их распределений. При анализе
Из-за отсутствия приемлемой модели механизма потерь в сети и присущей сложности расчета
Рассмотрим некое обобщение этой модели. В частности, будем рассматривать модели, в которых каждый компонент может находиться в одном из нескольких состояний, или модели, в которых рабочее состояние характеризуется численным значением. Численные значения этих характеристик обычно приравниваются метрике расстояния или величине пропускной способности. Простая модель с двумя состояниями хорошо подходит для вычисления меры связанности. Когда возникает необходимость посчитать более сложную меру, например, производительность системы, применяют более сложные характеристики состояний компонентов.
Для модели с двумя состояниями вероятность работоспособности компонента или, проще, надежность, можно понимать по-разному. Наиболее распространенными являются формулировки:
Вообще в этом разделе договоримся применять термин надежность для обозначения вероятности того, что компонент или система работает. Здесь мы обсуждаем более частное определение. Доступность используется в контексте ремонтоспособных систем. Из сказанного следует, что компонент может находиться в одном из трех состояний: работает, не работает, в процессе восстановления. Доступность компонента определяется как вероятность его работы в случайный момент времени. Оценка величины доступности производится с учетом среднего времени восстановления в рабочее состояние и среднего времени в нерабочем состоянии. Надежность можно записать так:
$$\frac{среднее\ время\ до\ отказа}{среднее\ время\ до\ отказа + среднее\ время\ восстановления}$$
Определение надежности компонента не учитывает время восстановления. Специфицируется промежуток времени $$t$$, а надежность компонента определяется как вероятность того, что за это время $$t$$ компонент останется в рабочем состоянии. Допускаются также иные трактовки для вероятности того, что компонент работает. Конечно, интерпретация уровня надежности компонента определяет в свою очередь интерпретацию мер
За отправную точку примем сеть $$G=(V,E)$$, в которой $$V$$ - набор узлов или вершин, а $$Е$$ - набор неориентированных ребер или набор ориентированных дуг. При изучении моделей связанности для каждого $$е \in Е$$ мы определяем надежность $$е(р_е)$$ как $$Pr[e работает]$$. При изучении простых моделей потоков (кратчайших путей), мы ассоциируем пропускную способность $$с_е$$ (расстояние $$d_е$$ ) с каждым $$е \in Е$$. Мы интерпретируем $$р_е$$, как вероятность того, что $$е$$ работает и имеет пропускную способность $$с_е$$ (расстояние $$d_е$$ ), а $$1-р_е$$ - как вероятность того, что $$е$$ не работает и имеет пропускную способность $$0$$ (расстояние равно бесконечности). При изучении моделей потоков (кратчайших путей) с множеством состояний мы ассоциируем распределение пропускной способности $${c_{е,i}, p_{е,i}}$$ (распределение расстояний $${d_{е,i}, p_{е,i}})$$ для $$е \in Е$$. Здесь $$p_{е,i}$$ - вероятность того, что $$е$$ будет иметь пропускную способность $$c_{е,i}$$ (расстояние $$d_{е,i}$$ ).
Иногда, при изучении
$$\psi(S)=\left\{\begin{aligned}1, если, когда\ S\ работает, а\ T-S\ не\ работает, система\ функционирует.\\0, если, когда\ S\ работает, а\ T-S\ не\ работает, система\ не\ функционирует\\\end{aligned}$$
Функция SBS является когерентной, если $$\psi (Т)=1, \psi (0)=0$$ и выполняется условие $$\psi (S'') \ge \psi (S)$$ для $$S'' \sup S$$. Последнее свойство означает, что выход из строя любого из компонентов может только повредить работе системы. Представляет интерес задача вычисления выражения:
$$Rel(SBS,p)=Pr[\psi (S)=1]$$, где $$S$$ - набор работающих компонентов,
если известен вид распределения $$\psi ()$$. Иногда мы рассматриваем задачи надежности, где $$р_{е}=p$$ для всех $$е$$, в этих случаях мы заменяем $$p$$ на $$p$$ в представленной выше нотации. Для произвольной стохастической когерентной двоичной системы ( SCBS -
Во многих приложениях могут отказывать как дуги, так и узлы. Следовательно, приходится изучать модели, способные реагировать и на отказы узлов, и на обрывы дуг. К счастью, для случая ориентированных сетей с помощью преобразования, показанного на рисунке 17.3, задачу с ненадежными ребрами и узлами можно свести к задаче с абсолютно надежными узлами и ненадежными ребрами. В каждом случае дуга, которая замещает узлы, наследует характеристики соответствующих узлов.
(рис 17.3) Замена ненадежного узлаВыше представленное обсуждение указывает, что с практической точки зрения предпочтительнее коды для анализа надежности ориентированной сети по отношению к кодам для неориентированного случая. При условии тщательного подбора входных данных ориентированные сетевые коды можно применять для анализа ориентированных и неориентированных моделей сети и задач с отказом и без отказа узлов.
При вычислении надежности приходится учитывать не только топологию сети, но и потоки данных в ней. Следовательно, анализ их сложности включает соображения, которые связаны с механизмом, используемым при рассмотрении проблем распознавания и оптимизации, но отличаются от него.
Чтобы наиболее простым образом свести задачи анализа надежности к более знакомым комбинаторным проблемам, рассмотрим частный случай задачи анализа надежности, которая возникает, когда все индивидуальные компоненты надежности равны, т.е. $$p_{i}$$ для всех $$i$$. В этом случае $$Rel(SBS,p)$$ можно записать в виде полинома по степеням $$p$$:
$$Rel(SBS,p)=\sum_{i=0}^m F_ip^{m-i}(1-p)^i$$
Этот полином является полиномом надежности. Задача по его вычислению называется задачей анализа функциональной надежности, где в качестве входных данных используется представление SBS, а на выходе получается вектор $${F_{i}}$$.
Общий член в полиноме надежности $$F_{i}p^{m-i}(1-p)^i$$ представляет собой вероятность того, что работает ровно $$m-i$$ компонентов сети и функционирует система в целом.
Результатом задачи по распознавания гамильтоновых контуров может быть либо "Да", если в графе содержатся контуры, либо "Нет", а результатом задачи подсчета гамильтоновых контуров в графе является число таких контуров. NP и NP-полный являются классами задач распознавания. Классы, соответствующие задачам подсчета, обозначаются #P и #P-полный. Очевидно, что любая задача подсчета, по крайней мере, не проще, чем соответствующая ей задача распознавания. Например, если известно число гамильтоновых контуров в графе, то не составит труда ответить на вопрос: "Больше ли нуля число гамильтоновых контуров?". Получается, что любая разновидность задачи подсчета из NP-полного класса часто является #P-полной. С другой стороны, существуют примеры задач распознавания, у которых время решения является полиномиальным, а их счетные аналоги относятся к NP-полному классу. Например, задача поиска точного соответствия в
Многие практические приложения требуют использования моделей с разной надежностью компонентов. В таких моделях все вероятности являются рациональными числами. Мы формулируем проблему анализа рациональной надежности следующим образом. В качестве входной информации используется представление SBS и для каждого компонента $$i$$ пара целых чисел $$a_{i}$$, $$b_{i}$$. На выходе получается пара целых чисел $$a$$ и $$b$$ таких, что $$a/b = Rel(SBS,{a_{i}/b_{i}})$$.
Мы начинаем с установления того, что, если конкретный анализ функциональной надежности является NP-сложными, тогда соответствующий анализ рациональной надежности является NP-сложными.
Для любой задачи анализа рациональной надежности r-Rel и соответствующей ей задачи анализа функциональной надежности, f-Rel за полиномиальное время может быть сведена к r-Rel.
В f-Rel входит представление функции SBS. На выходе необходимо получить набор коэффициентов $${F_{i}}$$ полинома надежности. Чтобы преобразовать f-Rel в r-Rel, выберем $$m+1$$ рациональное значение вероятности $$0 < p_{0} < p_{1} < ... < p_{m} < 1$$. Для $$j= 0,1,…,m$$ обозначим решения соответствующей задачи анализа рациональной надежности как $$r_{j} = Rel(SBS,p_{j})$$, где все компоненты надежности установлены равными $$p_{j}$$. Теперь мы можем записать систему уравнений:
$$\sum_{i=0}^m F_ip_j^{m-i}(1-p)^i=r_j$$ для $$j = 0,1,...,m$$.
Решив $$m+1$$ задачу анализа рациональной надежности, найдем $$p_{j}$$ и $$r_{j}$$. Получим систему из $$m+1$$ линейного уравнения с $$m+1$$ неизвестными $$F_{i}$$. Коэффициенты матрицы имеют свойство матрицы Вандермонде и, следовательно, матрица является невырожденной, таким образом, можно вычислить значения $$F_{i}$$.
Исследуем более детально вид полинома надежности для функций SCBS. Если задана SCBS, мы определяем значения:
Заметим сразу, что коэффициенты полинома надежности обладают следующими свойствами:
$$0\le F_i\le{n\choose i}$$, для $$i =0,1,...,m$$
$$F_i={n\choose i},$$ для $$i<c$$,
$$F_i={n\choose i}-n_c,$$ для $$i=c$$,
$$F_{i}=n_{l}$$ для $$i=m-l$$,
$$F_{i}=0$$ для $$i>m-l$$
Эти свойства означают, что, вычисляя полином надежности, мы легко определяем важные свойства SCBS функции. Например, исследовав полином надежности, мы сможем определить размер набора разрезов с минимальной мощностью. Таким образом, если задача распознавания набора разрезов с минимальной мощностью имеет сложность NP, то задача вычисления полинома надежности тоже имеет сложность NP.
Приведем результаты, полученные для сложности анализа
Набор путей с минимальной мощностью для k-терминальной меры является деревом Штейнера с минимальной мощностью. Известно, что задача распознавания является NP сложной для ориентированных и неориентированных сетей. Анализ функциональной и рациональной надежности для задачи анализа имеют NP сложность. Валиант [L.G.Valiant, "The complexity the enumeration and reliability problems", SIAM, J. Computing, 8 (1979), 410-421] приводит альтернативное доказательство, заключающееся в демонстрации того, что вычисление
$$SN(K)=\Sigma F_i = |{S : S ~соответствует ~субграфу, ~который ~содержит ~путь ~до ~каждого ~узла ~в ~К}|$$, имеет сложность $$NP$$. Здесь $$K$$ является набором терминалов.
Задачи распознавания минимального набора путей и разрезов, сопряженные с 2-терминальной мерой, являются проблемами кратчайшего пути и
Для ориентированной всетерминальной меры проблемы с наборами путей и разрезов с минимальной мощностью являются задачами поиска минимального покрывающего дерева и минимального s-ориентированного разреза, соответственно.
Обе эти задачи решаются за полиномиальное время. Задача подсчета минимального s-ориентированных разрезов имеет сложность NP. А это, в свою очередь, означает, что связанная с ней задача надежности имеет сложность NP. Для случая неориентированной меры задачи по распознаванию и подсчету минимального набора путей и разрезов имеют полиномиальную сложность. Однако задача вычисления общего члена в полиноме надежности имеет сложность NP, потому что задачи анализа надежности для неориентированного случая имеют сложность NP.
В свете этих негативных результатов, большинство исследований имело целью анализ структурированных сети. Самый широкий
Результаты данного раздела указывают на то, что полиномиальные алгоритмы для
Решение задач оценки надежности опирается на простое, но важное соображение: существует такое преобразование графа, которое не меняет значений различных мер надежности, и это преобразование может быть использовано для упрощения топологии сети, для которой нужно вычислить точное значение надежности. Наша первая цель - преобразования графов, которые приводят к упрощению.
Ребро или дуга, которые не входят ни в один из минимальных наборов путей, называется нерелевантным: работоспособность таких нерелевантных ребер не влияет на работу или отказ сети. Самым простым способом упрощающим преобразования графа является удаление нерелевантных ребер. По определению, такое преобразование не меняет меру надежности. Чтобы преобразование имело практическое применение для сети, время его эффективной реализации должно быть полиномиальным. Для все-, k- и 2-терминальных мер надежности петли всегда являются нерелевантными. А для k- и 2- терминальных мер надежности нерелевантными являются также все оконечные ребра, не имеющие терминального окончания. Такие ребра легко находить и удалять. В случае ориентированных задач надежности поиск нерелевантных дуг отнюдь не простая задача. Было показано, что задача нахождения нерелевантных дуг в случае $$(s,t)$$ -связанности имеет сложность NP, в то время как общая неориентированная задача допускает эффективное решение.
Проблема
Читатели, знакомые с телекоммуникационными протоколами, могут заинтересоваться тем, как писать прикладные программы для работы с пакетами. В большинстве случаев вполне достаточно воспользоваться стандартной библиотекой для работы с сокетами. В особых случаях может возникнуть необходимость получения данных непосредственно от сетевого интерфейса. Прикладная программа взаимодействует с драйвером сетевого интерфейса. Ethernet-интерфейс, как и всякий другой, содержит несколько статусных управляющих регистров (
Следует иметь в виду, что разные интерфейсы могут иметь разное число
(рис 17.4) Структура CSR-регистра интерфейса (CSR0)
| Init | инициализация (initialize) |
|---|---|
| Strt | старт |
| Stop | стоп |
| Tdnd | запрос передачи (transmit demand) |
| Txon | включение передачи |
| Rxon | включение приема |
| Inea | разрешение прерываний ( |
| Intr | прерывание |
| Idon | инициализация выполнена (стирание записью 1) |
| Tint | прерывание при передаче (стирание записью 1) |
| Rint | прерывание при чтении (стирание записью 1) |
| Merr | ошибка при тайм-ауте на шине (стирание записью 1) |
| Miss | нет буфера для приема (стирание записью 1) |
| Cerr | ошибка из-за столкновения (стирание записью 1) |
| Babl | тайм-аут при передаче (стирание записью 1) |
| Err | ошибка типа Babl, Cerr, Miss, Merr (только для чтения) |
(рис 17.4b) CSR1
CSR2 (доступ разрешен при CSR0[stop] = 1)
(рис 17.4c) CSR2
| Bcon | 0 = <0:7> перестановка байтов адресов |
|---|---|
| Acon | 0 = |
| Bswp | 0 = /bm1, bm0, /hold; |
(рис 17.4d) Структура переменных init_mode (смещение = 0) имеет вид
(рис 17.5) Структура переменных init_mode| Drx | запрет приема |
|---|---|
| Dtx | запрет передачи |
| Loop | цикл |
| Dtcr | запрет передачи crc |
| Coll | столкновение |
| Drty | запрет повторов |
| Intl | внутренний цикл |
| Prom | режим приема всех пакетов (promiscuous mode) |
Приведенное выше описание регистров интерфейса не является единственно возможным. Структура драйверов варьируется для разных операционных систем. Для системных программистов полезно иметь возможность настраивать драйвер или непосредственно интерфейс на определенный режим, например, на прием всех пакетов, проходящих по кабельному сегменту. Последнее может представлять интерес в диагностических целях, так как вслед за пакетным драйвером загружается Etherdrv, Winsock или winpkt и т.д., блокирующие режим приема всех пакетов (mode=6).
Существует множество пакетных драйверов. Можно обнаружить несколько модификаций для одного и того же типа интерфейса. Эти драйверы могут быть ориентированы на работу в разных программных средах и иметь разные возможности. Драйвер может использовать минимум возможностей интерфейса (базовый уровень), реализовать более широкий набор функций (мультикастинг, сбор статистики и т.д.) или поддерживать практически все, на что способен данный интерфейс. В последнем случае он занимает больше места в памяти. При написании программы следует помнить, что порядок байтов в Ethernet противоположен тому, который используется в вашей машине.
Пакетные драйверы используют программные прерывания в интервале $$0x60 - 0x80$$. Следует сразу заметить, что не все прерывания из этого списка свободны, и при конфигурировании системы следует проявлять осмотрительность. Для того, чтобы избежать конфликтов с другими внешними устройствами, предусматривается возможность реконфигурации прерываний. Практически все драйверы могут работать с различными протоколами (TCP/IP, OSI и др.). Решить задачу мультиплексирования на связном уровне помогает процедура access_type, которая обеспечивает доступ для пакетов определенного типа.
Все функции реализуются с помощью обращения к драйверу с набором определенных параметров. Каждому типу используемого сетевого протокола, с которым работает интерфейс, ставится в соответствие целочисленный указатель (handle), получаемый с помощью процедуры access_type. Выполнимость драйвером тех или иных операций может быть выяснена с помощью запроса driver_info.
Следует помнить, что порядок байтов в PC и в некоторых сетях, включая Ethernet, не совпадает. Мультикастинг адресация реализуется на уровне L2, при этом список мультикаст-адресов подписки пользователей хранится в сетевом интерфейсе и может быть прочитан по запросу.
Современные сетевые интерфейсы производят подсчет принятых и переданных октетов, количество различного типа ошибок и пр. Получение статистических данных об ошибках и трафике через данный интерфейс осуществляется с помощью запроса get_statistics(handle). Статистические данные имеют вид целых 32-разрядных чисел.
Практически все интерфейсы допускают смену МАС-адреса, прошитого изготовителем интерфейса.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.