Примеры сетевых топологий

Смотрите http://www.opt-tut.ru масляные радиаторы оптом. |

Введение - часть 4


Для этого существует математические методы оценки сложности алгоритмов [А. 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 - набор узлов или вершин графа сети, а Е - набор неориентированных ребер или набор ориентированных дуг. Большинство исследований по сетевой надежности посвящены к-терминальным мерам. Пусть имеется набор из К узлов и узел sО K(k=|K|). Задана сеть G, и все дуги графа, описывающего сеть, имеют вероятность надежности р. Тогда к-терминальная мера надежности определяется как (Pr - вероятность):

Rel(G,s,K,p)=Pr[существует хотя бы один работающий путь от s до каждого узла из набора К]

То есть, надежность сети с графом G для набора узлов К и выбранного узла s при вероятности иметь надежную связь для всех ребер графа p равна вероятности того, что узел s имеет хотя бы один доступный путь до каждого из узлов К. Обычно эта величина соответствует определенному временному интервалу.

Существует два важных частных случая мер: 2-терминальная мера с |К|=2 и всетерминальная мера, где К=V. Эти меры принято обозначать Rel2(G,s,p) и RelА(G,s,p), соответственно (Rel - надежность).

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


Начало  Назад  Вперед