Родичев Ю.А. Компьютерные сети - архитектура, технологии, защита

Подождите немного. Документ загружается.

(20,1). Таким образом, по окончании 2-го шага узлы 1, 2 и 3 име-

ют постоянные метки, узлы 4 и 6 – временные метки, а узлы 5 и 7

никаких меток не имеют (рис. 2.27).

Рис. 2.27. Шаг 2

Рис. 2.28. Шаг 3

3-й шаг. Отбираются все узлы, которые соединены с узлом 2

одним ребром и не имеют постоянных меток. Это узлы 5 и 7.

Узел 5 получает метку (40,2). Узел 7 получает метку (60,2).

Маршрут 1-3-4, связывающий узлы 1 и 4, является кратчайшим

маршрутом от узла 1 к узлу 4 (любой другой маршрут от узла 1 к

узлу 4 длиннее); поэтому узлу 4 приписывается постоянная

мет-

ка (23,3). Таким образом, по окончании 3-го шага узлы 1, 2, 3 и 4

имеют постоянные метки, а узлы 5, 6 и 7 – временные метки

(рис. 2.28).

4-й шаг. Отбираются все узлы, которые соединены с узлом 4

одним ребром и не имеют постоянных меток. Это узел 6.

Сравнивая длины маршрутов 1-3-6 и 1-3-4-6, замечаем, что

длины первого (45) и третьего (45) больше длины

второго (43).

Поэтому временная метка (45,3) узла 6 меняется на метку (43,4).

Маршрут 1-2-5, связывающий узлы 1 и 5, является кратчайшим

маршрутом от узла 1 к узлу 5 (любой другой маршрут от узла 1 к

узлу 5 длиннее), и поэтому узлу 5 приписывается постоянная

метка (40,2). Таким образом, по окончании 4-го шага узлы 1, 2, 3,

4 и 5 имеют постоянные метки, а узлы 6 и 7 – временные метки

(

рис. 2.29).

Рис. 2.29. Шаг 4

Рис. 2.30. Шаг 5

Следующие два шага позволяют дать постоянные метки узлам

6 и 7 – (43,4) и (49,5) соответственно (рис. 2.30).

Замечание. На каждом шаге временная метка одного из узлов

меняется на постоянную по следующему правилу: рассматрива-

ются все узлы с временными метками и выбирается тот из них,

длина маршрута до которого от узла 1 является наименьшей.

Обратный ход алгоритма

Используя вторую компоненту метки, определяем последова-

тельность вершин в каждом кратчайшем маршруте. Например:

метка (49,5) узла 7 указывает на предшествующий узел 5,

метка (40,2) узла 5 указывает на предшествующий узел 2,

метка (20,1) узла 2 указывает на предшествующий узел 1.

В результате обратная последовательность узлов кратчайшего

маршрута от узла 1 к узлу 7 имеет вид 7→5→2→1.

Ответ:

Узел Маршрут Длина

2 1-2 20

3 1-3 15

4 1-3-4 23

5 1-2-5 40

6 1-3-4-6 43

7 1-2-5-7 49

Задания

1. Телефонная компания планирует соединить подземным ка-

белем шесть городов, расстояния между которыми заданы при

помощи таблицы:

А В С D Е F

А – 10 9 30 27 20

В 10 – 15 18 17 20

С 9 15 – 25 21 16

D 30 18 25 – 8 17

Е 27 17 21 8 – 13

F 20 20 16 17 13 –

Найдите минимальную длину кабеля, позволяющего жителям

любых двух городов связаться друг с другом по телефону.

2. Найдите кратчайшие маршруты, ведущие из узла A во все

другие узлы сети, представленной на рис. 2.31.

Рис. 2.31. Задача нахождения кратчайшего пути

ГЛАВА 3

ОСНОВЫ ПОСТРОЕНИЯ

КОМПЬЮТЕРНЫХ СЕТЕЙ

3.1. Основные понятия

Каждое из трех прошедших столетий ознаменовалось преоб-

ладанием одной господствующей технологии. Восемнадцатое

столетие было веком индустриальной революции и механизации.

В XIX веке наступила эпоха паровых двигателей. В течение ХХ

века главной технологией стали сбор, обработка и распростране-

ние информации. Среди прочих разработок следует отметить

создание глобальных телефонных сетей, изобретение радио и те

левидения, рождение и небывалый рост компьютерной индуст-

рии, запуск спутников связи.

Благодаря высокой скорости технологического прогресса эти

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

между сбором, транспортировкой, хранением и обработкой ин-

формации продолжают быстро исчезать. Организации с сотнями

офисов, разбросанных по всему миру, должны иметь возмож-

ность

получать информацию о текущем состоянии своего самого

удаленного офиса мгновенно, нажатием кнопки. По мере роста

нашего умения собирать, обрабатывать и распространять инфор-

мацию, потребности в средствах еще более сложной обработки

информации растут все быстрее,

Хотя компьютерная индустрия еще довольно молода по срав-

нению с другими производствами (например, автомобильной или

авиационной промышленностью

), прогресс в сфере производства

компьютеров был весьма впечатляющим. В первые два десятиле-

тия своего существования компьютерные системы были сильно

централизованными, как правило, в пределах одного помещения.

Часто эта комната оборудовалась стеклянными стенами, сквозь

которые посетители могли полюбоваться на великое электронное

чудо. Компания среднего размера или университет могли позво-

лить себе один-два компьютера, тогда как у крупных организа-

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

какие-нибудь 20 лет столь же мощные компьютеры

будут иметь

размеры меньше почтовой марки и производиться миллионами,

тогда казалась чистой фантастикой.

Объединение компьютеров и средств связи оказало глубокое

влияние на принцип организации компьютерных систем. Концеп-

ция «компьютерного центра» в виде комнаты, в которой помещал-

ся большой компьютер, и куда пользователи приносили свои про-

граммы, сегодня полностью устарела. Модель,

в которой один

компьютер выполнял всю необходимую работу по обработке дан-

ных, уступила место модели, представляющей собой большое ко-

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

кие системы называются компьютерными сетями.

Каждый компьютер в сети может иметь периферийные уст-

ройства, доступные другим компьютерам сети. Поэтому можно

привести еще одно, более

общее, определение компьютерной се-

ти. Компьютерной сетью называется совокупность узлов (ком-

пьютеров, терминалов, периферийных устройств), имеющих воз-

можность информационного взаимодействия друг с другом с по-

мощью коммуникационного оборудования и программного обес-

печения.

Два компьютера называются связанными между собой, если

они могут обмениваться информацией. Связь не обязательно

должна осуществляться при помощи

медного провода. Могут ис-

пользоваться самые разнообразные средства связи, включая воло-

конную оптику, радиоволны высокой частоты и спутники связи.

Компьютерные сети отнюдь не являются единственным видом

сетей, созданным человеческой цивилизацией. Даже водопроводы

Древнего Рима можно рассматривать как один из наиболее древ-

них примеров сетей, покрывающих большие территории и обслу-

живающих многочисленных

клиентов. Другой, менее экзотиче-

ский пример – электрические сети. В них легко можно найти все

компоненты любой территориальной сети: источники ресурсов –

электростанции, магистрали – высоковольтные линии электропе-

редач, сеть доступа – трансформаторные подстанции, клиентское

оборудование – осветительные и бытовые электроприборы.

Размеры сетей варьируются в широких пределах – от пары со-

единенных между собой компьютеров, стоящих на соседних сто-

лах, до миллионов компьютеров, разбросанных по всему миру

(часть из них может находиться и на космических объектах). По

широте охвата принято деление

сетей на несколько категорий.

Локальные вычислительные сети, ЛВС или LAN (Local Area

Network), позволяют объединять компьютеры, расположенные в

ограниченном пространстве. Для локальных сетей, как правило,

прокладывается специализированная кабельная система, и поло-

жение возможных точек подключения абонентов ограничено

этой кабельной системой. Иногда в локальных сетях используют

и беспроводную связь (wireless), но и при этом возможности

пе-

ремещения абонентов сильно ограничены.

Локальные сети можно объединять в более крупномасштаб-

ные образования – CAN (Campus Area Network – кампусная сеть,

объединяющая локальные сети близко расположенных зданий),

МАN (Metropolitan Area Network – сеть городского масштаба),

WAN (Wide Area Network – широкомасштабная сеть), GAN

(Global Area Network – глобальная сеть). Сетью сетей в наше

время называют глобальную сеть Интернет.

Для более крупных сетей также устанавливаются специаль-

ные

проводные или беспроводные линии связи или используется

инфраструктура существующих публичных средств связи, на-

пример, телефонные линии. В последнем случае абоненты ком-

пьютерной сети могут подключаться к сети в относительно про-

извольных точках, охваченных сетью телефонии, кабельного те-

левидения.

В сетях применяются различные сетевые технологии,

из которых в локальных сетях наиболее

распространены Ethernet,

Token Ring, 100VG-AnyLAN, ARCnet, FDDI. В глобальных сетях

применяются иные технологии. Каждой технологии соответст-

вуют свои типы оборудования.

Оборудование сетей подразделяется на активное – интер-

фейсные карты компьютеров, повторители, концентраторы и т.п.

и пассивное – кабели, соединительные разъемы, коммутаци-

онные панели и т. п. Кроме того, имеется вспомогательное обо-

рудование – устройства бесперебойного питания, кондициониро-

вания воздуха и аксессуары – монтажные стойки, шкафы, кабеле-

проводы различного вида. С точки зрения физики, активное обо-

рудование – это устройства, которым необходима подача энергии

для генерации сигналов, пассивное оборудование подачи энергии

не требует.

Оборудование компьютерных сетей подразделяется на конеч-

ные системы (устройства), являющиеся источниками и/или

по-

требителями информации, и промежуточные системы, обеспечи-

вающие прохождение информации по сети. К конечным систе-

мам, ES (End Systems), относятся компьютеры, терминалы, сете-

вые принтеры, факс-машины, кассовые аппараты, считыватели

штрих-кодов, средства голосовой и видеосвязи и любые другие

периферийные устройства, снабженные тем или иным сетевым

интерфейсом. К промежуточным системам, IS (Intermediate

Systems), относятся концентраторы

(повторители, мосты, комму-

таторы), маршрутизаторы, модемы и прочие телекоммуникаци-

онные устройства, а также соединяющая их кабельная и/или бес-

проводная инфраструктура.

Действием, «полезным» для пользователей, является обмен

информацией между конечными устройствами. Поток информа-

ции, передаваемый по сети, называют сетевым трафиком.

Трафик кроме полезной информации включает и служебную ее

часть – неизбежные

накладные расходы на организацию взаимо-

действия узлов сети. Пропускная способность линий свя-

зи, называемая также полосой пропускания, определяется

как количество информации, проходящей через линию за едини-

цу времени. Она измеряется в специальных единицах бит/с (bps –

bit per second), Кбит/с (kbps), Мбит/с (Mbps), Гбит/с (Gbps),

Тбит/с (Tbps)...

Для активного коммуникационного оборудования применимо

понятие производительность,

причем в двух различных ас-

пектах. Кроме «валового» количества неструктурированной ин-

формации, пропускаемого оборудованием за единицу времени

(бит/с), интересуются и скоростью обработки пакетов (pps –

packets per second), кадров (fps – frames per second) или ячеек (cps

– cells per second). Естественно, при этом оговаривается и размер

структур (пакетов, кадров, ячеек), для которых измеряется ско-

рость обработки. В идеале производительность коммуникацион-

ного оборудования должна быть столь высокой, чтобы обеспечи-

вать обработку информации, приходящей на все интерфейсы

(порты) на их полной скорости.

Для организации обмена информацией должен быть разрабо-

тан комплекс программных и аппаратных средств, распределен-

ных по разным устройствам сети. Поначалу разработчики и по-

ставщики

сетевых средств пытались идти каждый по своему пу-

ти, решая весь комплекс задач с помощью собственного набора

протоколов, программ и аппаратуры. Однако решения различных

поставщиков оказывались несовместимыми друг с другом, что

вызывало массу неудобств для пользователей, которых по раз-

ным причинам не удовлетворял набор возможностей, предостав-

ляемых только одним из поставщиков

. По мере развития техники

и расширения ассортимента предоставляемых сервисов назрела

необходимость декомпозиции сетевой задачи – разбивки ее на

несколько взаимосвязанных подзадач с определением правил

взаимодействия между ними. Разбивка задачи и стандартизация

протоколов позволяет принимать участие в ее решении большому

количеству сторон – разработчиков программных и аппаратных

средств, изготовителей коммуникационного и вспомогательного

(например

, тестового) оборудования и инсталляторов, доносящих

все эти плоды прогресса до конечных потребителей. Применение

открытых технологий и следование общепринятым стандартам

позволяет избегать эффекта вавилонского столпотворения. Ко-

нечно, в какой-то момент стандарт становится тормозом разви-

тия, но кто-то делает прорыв, и его новая фирменная технология

со временем выливается в новый

стандарт.

3.2. Применение компьютерных сетей

Современные организации обычно используют большое ко-

личество компьютеров, часто довольно удаленных друг от друга.

Например, компания, состоящая из нескольких офисов, может

иметь по компьютеру в каждом из офисов для обеспечения про-

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

работать изолированно друг от друга, однако в какой-то момент

администрация может принять решение соединить их, чтобы

иметь возможность быстрого доступа к информации по всей

компании.

Если посмотреть на эту проблему с более общих позиций, то

вопросом здесь является совместное использование ресурсов, а

целью – предоставление доступа к программам, оборудованию и

особенно данным для любого пользователя сети, независимо от

физического расположения ресурса

и пользователя. Другими

словами, то, что пользователь находится на расстоянии 1000 км

от данных, не должно помешать ему воспользоваться этими дан-

ными так же, как если бы они находились рядом. То есть целью

сетей является борьба с географическим разбросом.

Вторая цель заключается в обеспечении высокой надежности

при помощи альтернативных источников информации.

Напри-

мер, все файлы могут быть реплицированы на двух или трех ма-

шинах, так что, если одна из них недоступна (из-за отказа аппа-

ратуры), могут быть использованы другие копии. Кроме того, на-

личие нескольких процессоров означает, что если один из них

выйдет из строя, другие могут выполнить его работу, хотя

воз-

можно и с уменьшенной производительностью. Возможность

продолжать работу, несмотря на аппаратные проблемы, имеет

чрезвычайно большое значение для военных и банковских задач,

в управлении воздушным транспортом, безопасностью ядерных

реакторов, управлении непрерывными технологическими про-

цессами и т.п.

Еще одной целью является экономия средств. Небольшие

компьютеры обладают значительно лучшим соотношением про-

изводительности и цены, нежели большие. Универсальные вы-

числительные машины размером с комнату работают быстрее

персональных компьютеров примерно в десятки раз, однако их

стоимость больше в тысячу раз. Это несоответствие заставляет

многих разработчиков создавать системы, состоящие из персо-

нальных компьютеров, по одному на пользователя, с данными,

хранящимися на одном или нескольких совместно

используемых

файл-серверах. В такой модели пользователи называются кли-

ентами, а вся система – клиент-серверной моделью.

В клиент-серверной модели обмен информацией обычно при-

нимает форму запросов от клиента к серверу, при помощи кото-

100

рых клиент просит сервер выполнить какие-либо действия. Сер-

вер выполняет работу и отсылает обратно ответ. Обычно в сети

количество клиентов значительно больше числа используемых

ими серверов. На рисунке 3.1 представлена принципиальная схе-

ма клиент-серверной модели.

Запрос

Сеть

Ответ

Компьютер

клиента

Прикладной

процесс

клиента

Сервер

Данные

(серверный

процесс)

Рис. 3.1. Модель «клиент-сервер»

В системах, построенных по принципу клиент-сервер, выде-

ляются три логических уровня: уровень пользовательского ин-

терфейса, уровень обработки информации, уровень данных.

Двухзвенная архитектура предполагает наличие двух машин:

клиентской (рабочей станции) и сервера. Распределение логиче-

ских уровней может быть различным. Возможен вариант, когда

вся прикладная часть информационной

системы выполняется на

компьютерах пользователей системы (клиентов), а на стороне

серверов осуществляется только доступ к базе данных (Рис. 3.2,

а). В случаях, когда логика прикладной части системы достаточ-

но сложна, каждый пользовательский компьютер должен обла-

дать достаточным набором ресурсов, чтобы быть в состоянии

произвести обработку данных, поступающих от пользователя и

из базы

данных.

Противоположным является вариант, когда на клиентской ма-

шине реализован только пользовательский интерфейс, а вся обра-