Иерархические сети и сети с неоднородной средой

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

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

Правила маршрутизации в таких сетях зависят от того, каким образом используется спутниковая система. Это, в свою очередь, зависит от того, какое требование является определяющим - большая производительность или малая задержка при передаче. Например, в спутниковой системе типа ALOHA может использоваться методика типа MASTER, согласно которой повторная передача пакетов после их столкновения в спутниковом канале всегда осуществляется через наземную сеть. Эта методика хорошо работает при больших нагрузках в сети, но при малых нагрузках она недостаточно широко использует наземную сеть, и поэтому все пакеты передаются с достаточно большой задержкой, характерной для спутниковых каналов. Если в сети действуют правила маршрутизации, ориентированные на минимальную задержку в сети, при малой нагрузке основную роль в передаче будет играть наземная сеть, а спутниковая система возьмет на себя избыточный поток, когда возрастут задержки в наземной сети.

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

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

Для случаев, когда расположение терминалов не позволяет объединить их в группы естественным образом, были предложены специальные эвристические методы. Их суть состоит в том, что на первом шаге в группы объединяются ближайшие терминалы, а затем каждая группа представляется своим центром масс и числом входящих в него терминалов. Начав с объединения отдельных терминалов, алгоритм затем переходит к объединению ближайших образований независимо от того, являются они отдельными терминалами или группами, до тех пор, пока группы не достигнут заранее заданной предельной величины и дальнейшее их объединение станет невозможным. При этом может понадобиться какое-то правило, запрещающее объединить группы, расположенные слишком далеко друг от друга; иначе остающимся группам, не достигшим максимальной величины, придется охватить слишком большие пространства. Расположение узла внутри группы связано с установкой концентратора при одном из терминалов. Поскольку положение центра тяжести всей группы известно, достаточно исследовать варианты расположения концентратора при терминалах, наименее удаленных от центра тяжести, и выбрать вариант с минимальной стоимостью.

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