На скорость передачи данных в сети, на надежность обслуживания запросов клиентов, на устойчивость сети к отказам оборудования, на стоимость создания и эксплуатации сети значительное влияние оказывает ее топология.
Под топологией компьютерной сети понимается способ соединения ее отдельных компонентов (компьютеров, серверов, принтеров и т.д.). Различают следующие основные топологии:
· топология типа звезда;
· топология типа кольцо;
· топология типа общая шина;
· древовидная топология;
· полносвязная сеть.
Рассмотрим данные топологии сетей.
Топология типа звезда . При использовании топологии типа звезда информация между клиентами сети передается через единый центральный узел (Рис. 11). В качестве центрального узла может выступать сервер или специальное устройство – концентратор (Hub).
Рис. 11. Топология типа звезда
В топологии звезда могут использоваться активные и пассивные концентраторы. Активные концентраторы принимают и усиливают передаваемые сигналы. Пассивные концентраторы пропускают через себя сигналы, не усиливая их. Пассивные концентраторы не требуют подключения к источнику питания.
Преимущества топологии звезда состоят в следующем:
1. Высокое быстродействие сети, так как общая производительность сети зависит только от производительности центрального узла.
2. Отсутствие столкновения передаваемых данных, так как данные между рабочей станцией и сервером передаются по отдельному каналу, не затрагивая другие компьютеры.
Однако помимо достоинств у данной топологии есть и недостатки:
1. Низкая надежность, так как надежность всей сети определяется надежностью центрального узла. Если центральный узел (сервер или концентратор) выйдет из строя, то работа всей сети прекратится.
2. Высокие затраты на подключение компьютеров, так как к каждому новому абоненту необходимо ввести отдельную линию.
3. Отсутствие возможности выбора различных маршрутов для установления связи между абонентами.
Данная топология в настоящее время является самой распространенной.
Топология типа кольцо . При топологии кольцо все компьютеры подключаются к кабелю, замкнутому в кольцо. Сигналы передаются по кольцу в одном направлении и проходят через каждый компьютер (рис. 12).
Рис. 12. Топология типа кольцо
Передача информации в данной сети происходит следующим образом. Маркер (специальный сигнал) последовательно, от одного компьютера к другому, передается до тех пор, пока его не получит тот, который хочет передать данные. Получив маркер, компьютер создает так называемый пакет, который используется для передачи данных. В пакет помещается адрес получателя и данные, а затем он отправляется по кольцу. Пакет проходит через каждый компьютер, пока не окажется у того, чей адрес совпадает с адресом получателя. После этого принимающий компьютер посылает источнику информации подтверждение факта получения пакета. Получив подтверждение, передающий компьютер создает новый маркер и возвращает его в сеть.
Преимущества топологии типа кольцо состоят в следующем:
1. Пересылка сообщений является очень эффективной, т.к. можно отправлять несколько сообщений друг за другом по кольцу. Т.е. компьютер, отправив первое сообщение, может отправлять за ним следующее сообщение, не дожидаясь, когда первое достигнет адресата.
2. Протяженность сети может быть значительной. Т.е. компьютеры могут подключаться к друг к другу на значительных расстояниях, без использования специальных усилителей сигнала.
3. Отсутствие коллизий (см. тему №3, раздел 2) и столкновения данных, так как передачу в каждый момент времени ведет только один компьютер.
К недостаткам данной топологии относятся:
1. Низкая надежность сети, так как отказ любого компьютера влечет за собой отказ всей системы.
2. Для подключения нового клиента необходимо прервать работу в сети.
3. При большом количестве клиентов скорость работы в сети замедляется, так как вся информация проходит через каждый компьютер, а их возможности ограничены.
4. Общая производительность сети определяется производительностью самого медленного компьютера .
Данная топология выигрывает в том случае, если в организации создается система распределенных центров обработки информации, расположенных на значительном расстоянии друг от друга.
Топология типа общая шина . При шинной топологии все клиенты подключены к общему каналу передачи данных (рис. 13). При этом они могут непосредственно вступать в контакт с любым компьютером, имеющимся в сети.
Рис.13. Топология типа общая шина
Передача информациипроисходит следующим образом. Данные в виде электрических сигналов передаются всем компьютерам сети. Однако информацию принимает только тот, адрес которого соответствует адресу получателя. Причем в каждый момент времени только один компьютер может вести передачу.
Преимущества топологии общая шина:
1. Вся информация находится в сети и доступна каждому компьютеру. Т.е. с любого персонального компьютера можно получить доступ к информации, которая храниться на любом другом компьютере.
2. Рабочие станции можно подключать независимо друг от друга. Т.е. при подключении нового абонента нет необходимости останавливать передачу информации в сети.
3. Построение сетей на основе топологии общая шина обходится дешевле, так как отсутствуют затраты на прокладку дополнительных линий при подключении нового клиента.
4. Сеть обладает высокой надежностью, т.к. работоспособность сети не зависит от работоспособности отдельных компьютеров.
Последнее преимущество определяется тем, что шина является пассивной топологией. Т.е. компьютеры только принимают передаваемые данные, но не перемещают их от отправителя к получателю. Поэтому, если один из компьютеров выйдет из строя, это не скажется на работе остальных.
К недостаткам топологии типа общая шина относятся:
1. Низкая скорость передачи данных, так как вся информация циркулирует по одному каналу (шине).
2. Быстродействие сети зависит от числа подключенных компьютеров. Чем больше компьютеров подключено к сети, тем больше загружена шина и тем медленнее идет передача информации от одного компьютера к другому.
3. Для сетей, построенных на основе данной топологии, характерна низкая безопасность, так как информация на каждом компьютере может быть доступна с любого другого компьютера.
Древовидная топология . В сетях с древовидной топологией компьютеры непосредственно связаны с центральными узлами сети – серверами (Рис. 14).
Рис.14. Древовидная топология
Древовидная топология представляет собой комбинацию топологии типа звезда и топологии типа общая шина. Поэтому ей в основном присущи те же преимущества и недостатки, которые были указаны для данных топологий.
Полносвязная вычислительная сеть . В полносвязной сети каждый компьютер соединен со всеми другими компьютерами отдельными линиями (рис. 15).
Рис.15. Полносвязная вычислительная сеть
Преимущества полносвязной сети:
1. Высокая надежность, так как при отказе любого канала связи будет найден обходной путь для передачи информации.
2. Высокое быстродействие, так как информация между компьютерами передается по отдельным линиям.
Недостатки данной топологии:
1. Данная топология требует большого числа соединительных линий, т.е. стоимость создания подобной сети очень высокая.
2. Трудность построения сети при большом количестве компьютеров, так как от каждого компьютера к остальным необходимо прокладывать отдельные линии.
Топология полносвязной сети обычно применяется для малых сетей с небольшим количеством компьютеров, которые работают с полной загрузкой каналов связи.
Для крупных вычислительных сетей (глобальных или региональных) обычно применяется комбинация различных топологией для разных участков.
Модели ЛВС
Существует две модели локальных вычислительных сетей:
· одноранговая сеть;
· сеть типа клиент-сервер.
В одноранговой сети все компьютеры равноправны между собой. При этом вся информация в системе распределена между отдельными компьютерами. Любой пользователь может разрешить или запретить доступ к своим данным. В таких сетях на всех компьютерах устанавливаются однотипные операционные системы (ОС), которые предоставляет всем компьютерам в сети потенциально равные возможности.
Достоинстваданной модели:
1. Простота реализации. Для реализации данной сети достаточно наличия в компьютерах сетевых адаптеров и кабеля, которых их соединит.
2. Низкая стоимость создания сети. Так как отсутствуют затраты, связанные с покупкой дорогостоящего сервера, дорогой сетевой операционной системы и т.д.
Недостатки модели:
1. Низкое быстродействие при сетевых запросах. Рабочая станция всегда обрабатывает сетевые запросы медленнее, чем специализированный компьютер – сервер. Помимо этого на рабочей станции всегда выполняются различные задачи (набор текста, создание рисунков, математические расчеты и др.), которые замедляют ответы на сетевые запросы.
2. Отсутствие единой информационной базы, так как вся информация распределена по отдельным компьютерам. При этом приходиться обращаться к нескольким компьютерам для получения необходимой информации.
3. Отсутствие единой системы безопасности информации. Каждый персональный компьютер защищает свою информацию посредством операционной системы. Однако операционные системы персональных компьютеров, как правило, обладают меньшей защищенностью, чем сетевые операционные системы для серверов. Поэтому "взломать" такую сеть значительно проще.
4. Зависимость наличия в системе информации от состояния компьютера. Если какой-то компьютер будет выключен, то информация, хранимая на нем, будет недоступна другим пользователям.
В сети типа клиент-сервер имеется один или несколько главных компьютеров - серверов. В таких системах всей основной информацией управляют серверы.
Сеть типа клиент-сервер является функционально не симметричной: в ней используются два типа компьютеров - одни ориентированны на выполнение серверных функций и работают под управлением специализированных серверных ОС, а другие - выполняют клиентские функции и работают под управлением обычных ОС. Функциональная несимметричность вызывает и несимметричность аппаратуры - для выделенных серверов используются более мощные компьютеры с большими объемами оперативной и внешней памяти.
Достоинствами данной модели являются:
1. Высокое быстродействие сети, так как сервер быстро обрабатывает сетевые запросы и не загружен другими задачами.
2. Наличие единой информационной базы и системы безопасности. Взломать сервер можно, но это значительно сложнее, чем рабочую станцию.
3. Простота управления все сетью. Так как управление сетью заключается в основном в управлении только сервера.
Недостаткимодели:
1. Высокая стоимость реализации, так как требуется покупать дорогостоящий сервер и сетевую операционную систему для сервера.
2. Зависимость быстродействия сети от сервера. Если сервер будет не достаточно мощным, то работа в сети может сильно замедляться.
3. Для правильной работы сети требуется наличие дополнительного обслуживающего персонала, т.е. в организации должна быть введена должность администратор сети.
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ВВЕДЕНИЕ
Первичные сети связи представляют собой совокупность сетевых узлов, станций и линий передачи (точнее, линейных трактов), которые соединяют их между собой и образуют сеть типовых каналов и трактов. Разветвленный и многоуровневый характер этой сети заставляет все работы, связанные с проектированием, монтажом, настройкой, вводом в эксплуатацию, реконструкцией, модернизацией и т. п., выполнять по отдельным участкам первичной сети. Применительно к междугородной (зоновой или магистральной) первичной сети такие участки называют магистралями. В состав магистрали входят два или более сетевых узлов (станции), на которых размещается оконечное и/или транзитное оборудование нескольких систем передачи (СП), а также одна или несколько физических линий связи, на которых организованы линейные тракты этих СП. В свою очередь, линейные тракты содержат обслуживаемые или необслуживаемые усилительные (или регенерационные) пункты, пункты коррекции, ответвления и т.п. Таким образом, магистраль представляет собой достаточно сложное и дорогое устройство, имеющее важное народнохозяйственное значение для сравнительно большого региона страны.
Целью курсового проекта является оптимизация топологии сети по критерию минимальной протяженности методом ветвей и границ.
1 СРАВНИТЕЛЬНЫЙ АНАЛИЗ ТОПОЛОГИЙ СЕТЕЙ ТЕЛЕКОММУНИКАЦИЙ
1.1 Этапы развития сетей
телекоммуникационный сеть протяженность топология
Различные виды электросвязи длительный период времени развивались независимо друг от друга. Каждый вид электросвязи ориентировался на создание своих каналов, систем передачи (СП) и сетей. Структура сети выбиралась в соответствии с особенностями распределения потоков сообщений, характерных для конкретного виды электросвязи. Некоторые отрасли промышленности и транспорта стали создавать свои сети, предназначенные для удовлетворения потребностей отрасли в передаче сообщений. Разобщенность технических средств не только не позволяла повысить эффективность совокупности сетей в масштабах страны, но и тормозила развитие обособленных сетей. Поэтому уже в начале 1960-х гг. стало ясно, что перспективным направлением развития сетей должно было стать объединение сетей. Было принято решение о создании ЕАСС (Единая автоматизированная сеть связи). ЕАСС базировалась на объединении разрозненных и многочисленных мелких сетей в общегосударственные сети каждого вида электросвязи, а затем в единую сеть с целью совместного использования определенных технических средств, и, в первую очередь, систем передачи и систем коммутации.
При создании ЕАСС было учтено, что определенные технические средства участвуют в процессе передачи независимо от вида сообщений, т. е. являются общими. В связи с этим вся сеть страны стала подразделяться на две взаимосвязанные составляющие:
1) первичную сеть - совокупность сетевых станций, сетевых узлов (дать определение в приложении) и соединяющих их линий передачи, которая позволяет организовывать сеть каналов передачи и групповых трактов.
Структура первичной сети учитывает административное разделение территории страны. Вся территория поделена на зоны, совпадающие, как правило, с территорией областей, краев. В соответствии с этим первичная сеть также состоит из следующих частей:
* местные первичные сети - часть сети, ограниченная территорией города или сельского района;
* зоновые первичные сети - часть сети, охватывающая территорию зоны (область, край, республика), обеспечивающая соединение между собой каналов разных местных сетей внутри одной зоны;
* магистральная первичная сеть - часть сети, соединяющая между собой каналы разных зоновых сетей на всей территории страны.
Структура первичной сети показана на рисунке 1.1.
Рисунок 1.1 - Структура первичной сети
2) вторичная сеть - совокупность технических средств, обеспечивающих передачу сообщений определенного вида, в состав которой входят: оконечные устройства, абонентские и соединительные линии, коммутационные станции, а также каналы, выделенные из первичной сети для образования вторичной.
Вторичные сети подразделяются на следующие виды:
* телефонные;
* телеграфные;
* передачи данных;
* факсимильные;
* телевизионного вещания;
* звукового вещания.
1.2 Основные способы построения телекоммуникационных сетей связи
Одним из основных требований, предъявляемых к сетям передачи индивидуальных сообщений (телефонные, телеграфные, факсимильные, передачи данных), является то, что сеть должна обеспечить каждому пользователю возможность связаться с другим пользователем. Для выполнения этого требования сеть связи строится по определенному принципу в зависимости от условий функционирования. Следовательно, сети связи могут иметь различную структуру, т. е. отличаться числом и расположением узловых и оконечных пунктов (станций), а также характером их взаимосвязи. На рисунке 1.2 показаны способы построения сетей связи.
При полносвязанном способе построения (принцип «каждый с каждым») между узлами существует непосредственная связь. Используется при небольшом количестве узлов на сети (рисунок 1.2 а).
При радиальном способе построения сети связь между узлами осуществляется через центральный узел (рисунок 1.2 б). Используется при построении сети на сравнительно небольшой территории.
На большой территории сеть связи строится по радиально-узловому способу (рисунок 1.2 в).
Кольцевой способ построения сети предусматривает возможность осуществления связи как по часовой, так и против часовой стрелки (рис. 1.2 г). В этом случае при повреждении на определенном участке сеть сохраняет свою работоспособность.
При комбинированном способе построения сети узлы на верхнем иерархическом уровне связываются по полносвязанной схеме рисунок 1.2 д). В этом случае выход одного из узлов не нарушает работу всей сети.
Рисунок 1.2 - Способы построения сетей связи
2 ПОСТРОЕНИЕ МОДЕЛИ ТОПОЛОГИИ РАЗРАБАТЫВАЕМОЙ СЕТИ ТЕЛЕКОММУНИКАЦИЙ
Данные представляем в виде таблицы 2.1
Таблица 2.1- Расстояния между узлами проектируемой сети
|
Сморгонь |
|||||||||||||||||
|
Островец |
|||||||||||||||||
|
Плещеницы |
|||||||||||||||||
|
Глубокое |
|||||||||||||||||
|
Шарковщина |
|||||||||||||||||
|
Молодечно |
|||||||||||||||||
|
Радошковичи |
|||||||||||||||||
|
Заславль |
Задача коммивояжера .
Возьмем в качестве произвольного маршрута:
X 0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,8);(8,9);(9,10);(10,11);(11,12); (12,13); (13,14); (14,15); (15,1);
Тогда F(X 0) = 56 + 31 + 32 + 80 + 27 + 77 + 80 + 29 + 155 + 87 + 66 + 21 + 43 + 17=801
3 РАЗРАБОТКА ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ ОПТИМИЗАЦИИ ТОПОЛОГИИ РАЗРАБАТЫВАЕМОЙ СЕТИ
Суть метода динамического программирования заключается в подходе к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающих различные этапы, обеспечивает получение допустимого оптимального решения задачи в целом при достижении последнего этапа.
|
Сморгонь |
|||||||||||||||||
|
Островец |
|||||||||||||||||
|
Плещеницы |
|||||||||||||||||
|
Глубокое |
|||||||||||||||||
|
Шарковщина |
|||||||||||||||||
|
Молодечно |
|||||||||||||||||
|
Радошковичи |
|||||||||||||||||
|
Заславль |
При решении задачи нахождения оптимального пути происходит разделение задачи на процессы (по количеству узлов), в данном случае на 15. Процесс начинается из узла № 1. Фактически не важно, откуда его начинать, все равно маршрут круговой и охватывает все узлы.
На первом этапе вычислительной процедурой будет расстояние от узла № 1 до каждого из оставшихся узлов.
|
№ процесса |
Значение |
|
На следующем этапе значение вычислительной процедуры принимает значение минимального расстояния в следующий (любой узел).
|
№ процесса |
Значение 1 этапа |
Значение 2 этапа |
|
Выбирается минимум функции и осуществляется переход к следующему этапу. Следует обратить внимание, что из значений функций можно сразу убирать заведомо неправильные значения. Так же не следует учитывать значения ведущие в «обратную сторону».
4 РАЗРАБОТКА БЛОК-СХЕМЫ ПРОГРАММЫ-ОБОЛОЧКИ И БЛОК-СХЕМ ОСНОВНЫХ ПРОГРАММ-ПРОЦЕДУР ДЛЯ ОПТИМИЗАЦИИ ТОПОЛОГИИ СЕТИ
Ввиду того, что основные процедуры представляют собой рекуррентное выражение, было нецелесообразным выводить их в отдельные процедуры с составлением алгоритмов.
5 РАЗРАБОТКА И ОТЛАДКА ПРОГРАММЫ ОПТИМИЗАЦИИ ТОПОЛОГИИ СЕТИ ТЕЛЕКОММУНИКАЦИЙ ПО КРИТЕРИЮ МИНИМУМА ЕЕ ПРОТЯЖЕННОСТИ
Программа разработана на языке программирования Java. Java -- объектно-ориентированный язык программирования, разрабатываемый компанией Sun Microsystems с 1991 года и официально выпущенный 23 мая 1995 года. Изначально новый язык программирования назывался Oak (James Gosling) и разрабатывался для бытовой электроники, но впоследствии был переименован в Java и стал использоваться для написания апплетов, приложений и серверного программного обеспечения
Отличительной особенностью Java в сравнении с другими языками программирования общего назначения является обеспечение высокой продуктивности программирования, нежели производительность работы приложения или эффективность использования им памяти.
В Java используются практически идентичные соглашения для объявления переменных, передачи параметров, операторов и для управления потоком выполнением кода. В Java добавлены все хорошие черты C++.
Три ключевых элемента объединились в технологии языка Java
Java предоставляет для широкого использования свои апплеты (applets) -- небольшие, надежные, динамичные, не зависящие от платформы активные сетевые приложения, встраиваемые в страницы Web. Апплеты Java могут настраиваться и распространяться потребителям с такой же легкостью, как любые документы HTML
Java высвобождает мощь объектно-ориентированной разработки приложений, сочетая простой и знакомый синтаксис с надежной и удобной в работе средой разработки. Это позволяет широкому кругу программистов быстро создавать новые программы и новые апплеты
Java предоставляет программисту богатый набор классов объектов для ясного абстрагирования многих системных функций, используемых при работе с окнами, сетью и для ввода-вывода. Ключевая черта этих классов заключается в том, что они обеспечивают создание независимых от используемой платформы абстракций для широкого спектра системных интерфейсов
Огромное преимущество Java заключается в том, что на этом языке можно создавать приложения, способные работать на различных платформах. К сети Internet подключены компьютеры самых разных типов - Pentium PC, Macintosh, рабочие станции Sun и так далее. Даже в рамках компьютеров, созданных на базе процессоров Intel, существует несколько платформ, например, Microsoft Windows версии 3.1, Windows 95, Windows NT, OS/2, Solaris, различные разновидности операционной системы UNIX с графической оболочкой XWindows. Между тем, создавая сервер Web в сети Internet, хотелось бы, чтобы им могло пользоваться как можно большее число людей. В этом случае выручат приложения Java, предназначенные для работы на различных платформах и не зависящие от конкретного типа процессора и операционной системы.
Исходные данные программа берет из текстового файла, представляющего собой таблицу. Путь к файлу прописан в теле программы. ПО умолчанию значение равно «D:\\cites.txt». Имеет значение количества городов, в случае изменения их количества, необходимо изменить значение переменной n.
Для удобства вывода результатов в программе указано наименование городов, для их изменения также необходимо менять код программы. При не изменении названий, программа корректно работает и за основу можно взять номера городов.
Вывод результатов оптимизации производится на экран, с указанием общей протяженности маршрута.
6 РАСЧЕТ ОПТИМАЛЬНОЙ ТОПОЛОГИИ РАЗРАБАТЫВАЕМОЙ СЕТИ ТЕЛЕКОММУНИКАЦИЙ И АНАЛИЗ МОДЕЛИ ТОПОЛОГИИ СЕТИ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЮ ПАРАМЕТРОВ
Результат работы программы представлены на рисунке 5.2. При этом результат проверен в других алгоритмах.
Схема маршрута с привязкой к карте РБ представлена на рисунке 6.1.
ЗАКЛЮЧЕНИЕ
В результате проделанной курсовой работы были получены неоценимые навыки в проектировании и оптимизации телекоммуникационных сетей. Был разработан алгоритм для программы оптимизации, реализована программа и проведена процедура оптимизации для заданной конфигурации сети. Результаты были проверены ручным вычислением. В качестве метода оптимизации структуры сети по критерию минимальной протяженности применялся метод ветвей и границ.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
1. Таха Х. Введение в исследование операций / пер. с англ. -М.: Вильямс, 2005.
2. Банди Б. Методы оптимизации. Вводный курс. -М.: Радио и связь, 1988.
3. Васильев Ф.В. Численные методы решения экстремальных задач. -М.: Наука, 1980.
ПРИЛОЖЕНИЕ А
ТЕКСТ ПРОГРАММЫ
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class ShortestPathDynamicMethods {
public static int readDistancesFromFile() throws FileNotFoundException {
File f1 = new File("D:\\Cities2.txt");
BufferedReader input = new BufferedReader(new FileReader(f1));
BufferedReader input1 = new BufferedReader(new FileReader(f1));
int NUMBER_CITIES = 0;
String line = null;
while ((line = input1.readLine()) != null) {
NUMBER_CITIES++;
} catch (IOException e) {
e.printStackTrace();
int array = new int;
String line = null;
while ((line = input.readLine()) != null) {
StringTokenizer st = new StringTokenizer(line);
while (st.hasMoreTokens()) {
String tkn = st.nextToken();
//System.out.println(tkn);
array[i][j] = Integer.parseInt(tkn);
} catch (IOException e) {
e.printStackTrace();
public static int getShortestDistance(int dist) {
List
cityList.add("Ивье");
cityList.add("Ошмяны");
cityList.add("Сморгонь");
cityList.add("Островец");
cityList.add("Поставы");
cityList.add("Мядель");
cityList.add("Плещеницы");
cityList.add("Глубокое");
cityList.add("Шарковщина");
cityList.add("Воложин");
cityList.add("Логойск");
cityList.add("Молодечно");
cityList.add("Вилейка");
cityList.add("Радошковичи");
cityList.add("Заславль");
int n = dist.length;
int dp = new int[n];
for (int d: dp)
Arrays.fill(d, Integer.MAX_VALUE / 2);
for (int mask = 1; mask < 1 << n; mask += 2) {
for (int i = 1; i < n; i++) {
if ((mask & 1 << i) != 0) {
for (int j = 0; j < n; j++) {
if ((mask & 1 << j) != 0) {
dp[i] = Math.min(dp[i], dp[j] + dist[j][i]);
int res = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
res = Math.min(res, dp[(1 << n) - 1][i] + dist[i]);
int cur = (1 << n) - 1;
int order = new int[n];
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j < n; j++) {
if ((cur & 1 << j) != 0 && (bj == -1 || dp + dist > dp[j] + dist[j])) {
cur ^= 1 << bj;
System.out.println("Порядок обхода городов: ");
for (int i = 0; i < order.length; i++)
System.out.println((i + 1) + " " + cityList.get(order[i]));
public static void main(String args) {
System.out.println("Минимальное расстояние: " + getShortestDistance(ShortestPathDynamicMethods.readDistancesFromFile()));
} catch (Exception e) {
e.printStackTrace();
Размещено на Allbest.ru
Роль и общие принципы построения компьютерных сетей. Топологии: шинная, ячеистая, комбинированная. Основные системы построения сетей "Token Ring" на персональных компьютерах. Протоколы передачи информации. Программное обеспечение, технология монтажа сети.
курсовая работа , добавлен 11.10.2013
Расчет сетей с минимальной протяженностью ветвей. Модель структуры сети соединении станций по принципу "каждая с каждой". Определение числа каналов между пунктами сети. Распределение каналов по ветвям сети, обеспечивающее минимальную протяженность связей.
курсовая работа , добавлен 19.12.2013
Изучение состава и структуры междугородной телефонной сети, плана распределения каналов вторичной сети. Анализ схемы разговорного тракта между телефонными аппаратами разных местных сетей. Расчет путей, сечений и надежности коммутируемой телефонной сети.
курсовая работа , добавлен 19.03.2012
Топология сети: общее понятие и разновидности. Активные и пассивные топологии, их главные особенности. Методы расширения сети. Расширение сети с топологией "звезда", обзор основных способов. Попарное соединение устройств при организации локальной сети.
презентация , добавлен 25.10.2013
Роль компьютерных сетей, принципы построения. Протоколы передачи информации в сети ArcNet, используемые топологии и средства связи. Программное обеспечение, технология развёртки. Операционные системы компьютерных сетей. Инструкция по технике безопасности.
курсовая работа , добавлен 11.10.2013
Изучение топологии NGN сети - сети связи следующего поколения, обеспечивающей передачу всех видов медиатрафика с различными требованиями к качеству обслуживания и их поддержкой. Перспективы применения технологии NGN для построения мультисервисной сети.
курсовая работа , добавлен 25.08.2010
Современные технологии доступа в сети Интернет. Беспроводные системы доступа. Оптико-волоконные и волоконно-коаксиальные системы. Существующие топологии сетей. Выбор топологии, оптического кабеля и трассы прокладки. Экономическое обоснование проекта.
дипломная работа , добавлен 17.04.2014
Анализ способов построения телефонных сетей общего пользования. Расчет интенсивности телефонной нагрузки на сети, емкости пучков соединительных линий. Выбор структуры первичной сети. Выбор типа транспортных модулей SDH и типа оптического кабеля.
курсовая работа , добавлен 22.02.2014
Сфера применения локальных вычислительных сетей как способа соединения компьютеров. Основные топологии, применяемые при построении компьютерных сетей. Одноранговые и иерархические локальные сети. Сущность кабельных и оптоволоконных способов связи.
реферат , добавлен 12.05.2014
Основные типовые топологии вычислительных сетей, их изучение, анализ, оценка. Вывод о работе сетей с различной топологией (цепочечной, полносвязной, ячеистой, комбинированной). Преимущества и недостатки топологий, влияющих на производительность сети.
Введение
1. Понятие топологии сети
2. Базовые топологии сети
2.3 Базовая топология сети типа "кольцо" (ring)
3. Другие возможные сетевые топологии
3.1 Топология сети типа "дерево" (tree)
3.2 Комбинированные топологии сети
3.3 "Сеточная" топология сети
4. Многозначность понятия топологии
Заключение
Список используемой литературы
На сегодняшний день невозможно представить деятельность человека без использования им компьютерных сетей.
Компьютерная сеть - представляет собой систему распределенной обработки информации, состоящую как минимум из двух компьютеров, взаимодействующих между собой с помощью специальных средств связи.
В зависимости от удалённости компьютеров и масштабов, сети условно разделяют на локальные и глобальные.
Локальные сети - сети, имеющие замкнутую инфраструктуру до выхода на поставщиков услуг. Термин "LAN" может описывать и маленькую офисную сеть, и сеть уровня большого завода, занимающего несколько сотен гектаров. Локальные сети развёртываются обычно в рамках некоторой организации, поэтому их называют также корпоративными сетями.
Иногда выделяют сети промежуточного класса - городская или региональная сеть, т.е. сеть в пределах города, области и т.п.
Глобальная сеть покрывает большие географические регионы, включающие в себя как локальные сети, так и прочие телекоммуникационные сети и устройства. Глобальные сети практически имеют те же возможности, что и локальные. Но они расширяют область их действия. Польза от применения глобальных сетей ограничена в первую очередь скоростью работы: глобальные сети работают с меньшей скоростью, чем локальные.
Из выше перечисленных компьютерных сетей, обратим свое внимание на локальные сети, для того чтобы лучше понять архитектуру сетей, способы передачи данных. А для этого надо знать такое понятие, как топология сети.
Топология - это физическая конфигурация сети в совокупности с ее логическими характеристиками. Топология - это стандартный термин, который используется при описании основной компоновки сети. Если понять, как используются различные топологии, то можно будет определить, какими возможностями обладают различные типы сетей.
Существует два основных типа топологий:
физическая
логическая
Логическая топология описывает правила взаимодействия сетевых станций при передаче данных.
Физическая топология определяет способ соединения носителей данных.
Термин "топология сети" характеризует физическое расположение компьютеров, кабелей и других компонентов сети. Топология сети обуславливает ее характеристики.
Выбор той или иной топологии влияет на:
состав необходимого сетевого оборудования
характеристики сетевого оборудования
возможности расширения сети
способ управления сетью
Конфигурация сети может быть или децентрализованной (когда кабель "обегает" каждую станцию в сети), или централизованной (когда каждая станция физически подключается к некоторому центральному устройству, распределяющему фреймы и пакеты между станциями). Примером централизованной конфигурации является звезда с рабочими станциями, располагающимися на концах ее лучей. Децентрализованная конфигурация похожа на цепочку альпинистов, где каждый имеет свое положение в связке, а все вместе соединены одной веревкой. Логические характеристики топологии сети определяют маршрут, проходимый пакетом при передаче по сети.
При выборке топологии нужно учитывать, чтобы она обеспечивала надежную и эффективную работу сети, удобное управление потоками сетевых данных. Желательно также, чтобы сеть по стоимости создания и сопровождения получилась недорогой, но в то же время оставались возможности для ее дальнейшего расширения и, желательно, для перехода к более высокоскоростным технологиям связи. Это непростая задача! Чтобы ее решить, необходимо знать, какие бывают сетевые топологии.
Существует три базовые топологии, на основе которых строится большинство сетей.
звезда (star)
кольцо (ring)
Если компьютеры подключены вдоль одного кабеля, топология называется "шиной". В том случае, когда компьютеры подключены к сегментам кабеля, исходящим из одной точки, или концентратора, топология называется звездой. Если кабель, к которому подключены компьютеры, замкнут в кольцо, такая топология носит название кольца.
Хотя сами по себе базовые топологии несложны, в реальности часто встречаются довольно сложные комбинации, объединяющие свойства нескольких топологий.
В этой топологии все компьютеры соединяются друг с другом одним кабелем (рисунок 1).
Рисунок 1 - Схема топологии сети тип "шина"
В сети с топологией "шина" компьютеры адресуют данные конкретному компьютеру, передавая их по кабелю в виде электрических сигналов - аппаратных MAC-адресов . Чтобы понять процесс взаимодействия компьютеров по шине, нужно уяснить следующие понятия:
передача сигнала
отражение сигнала
терминатор
1. Передача сигнала
Данные в виде электрических сигналов, передаются всем компьютерам сети; однако информацию принимает только тот, адрес которого соответствует адресу получателя, зашифрованному в этих сигналах. Причем в каждый момент времени только один компьютер может вести передачу. Так как данные в сеть передаются лишь одним компьютером, ее производительность зависит от количества компьютеров, подключенных к шине. Чем их больше, т.е. чем больше компьютеров, ожидающих передачи данных, тем медленнее сеть. Однако вывести прямую зависимость между пропускной способностью сети и количеством компьютеров в ней нельзя. Ибо, кроме числа компьютеров, на быстродействие сети влияет множество факторов, в том числе:
характеристики аппаратного обеспечения компьютеров в сети
частота, с которой компьютеры передают данные
тип работающих сетевых приложений
тип сетевого кабеля
расстояние между компьютерами в сети
Шина - пассивная топология. Это значит, что компьютеры только "слушают" передаваемые по сети данные, но не перемещают их от отправителя к получателю. Поэтому, если один из компьютеров выйдет из строя, это не скажется на работе остальных. В активных топологиях компьютеры регенерируют сигналы и передают их по сети.
2. Отражение сигнала
Данные, или электрические сигналы, распространяются по всей сети - от одного конца кабеля к другому. Если не предпринимать никаких специальных действий, сигнал, достигая конца кабеля, будет отражаться и не позволит другим компьютерам осуществлять передачу. Поэтому, после того как данные достигнут адресата, электрические сигналы необходимо погасить.
3. Терминатор
Чтобы предотвратить отражение электрических сигналов, на каждом конце кабеля устанавливают заглушки (терминаторы, terminators), поглощающие эти сигналы (Рисунок 2). Все концы сетевого кабеля должны быть к чему-нибудь подключены, например к компьютеру или к баррел-коннектору - для увеличения длины кабеля. К любому свободному - неподключенному - концу кабеля должен быть подсоединен терминатор, чтобы предотвратить отражение электрических сигналов.
Рисунок 2 - Установка терминатора
Нарушение целостности сети может произойти, если разрыв сетевого кабеля происходит при его физическом разрыве или отсоединении одного из его концов. Возможна также ситуация, когда на одном или нескольких концах кабеля отсутствуют терминаторы, что приводит к отражению электрических сигналов в кабеле и прекращению функционирования сети. Сеть "падает". Сами по себе компьютеры в сети остаются полностью работоспособными, но до тех пор, пока сегмент разорван, они не могут взаимодействовать друг с другом.
У такой топологии сети есть достоинства и недостатки. К достоинствам можно отнести:
небольшое время установки сети
дешевизна (требуется меньше кабеля и сетевых устройств)
простота настройки
выход из строя рабочей станции не отражается на работе сети
Недостатки такой топологии следующие.
такие сети трудно расширять (увеличивать число компьютеров в сети и количество сегментов - отдельных отрезков кабеля, их соединяющих).
поскольку шина используется совместно, в каждый момент времени передачу может вести только один из компьютеров.
"шина" является пассивной топологией - компьютеры только "слушают" кабель и не могут восстанавливать затухающие при передаче по сети сигналы.
надежность сети с топологией "шина" невысока. Когда электрический сигнал достигает конца кабеля, он (если не приняты специальные меры) отражается, нарушая работу всего сегмента сети.
Проблемы, характерные для топологии "шина", привели к тому, что эти сети, столь популярные еще десять лет назад, сейчас уже практически не используются.
Топология сети типа "шина" известна как логическая топология Ethernet 10 Мбит/с.
При топологии "звезда" все компьютеры с помощью сегментов кабеля подключаются к центральному компоненту, именуемому концентратором (hub) (рисунок 3).
Сигналы от передающего компьютера поступают через концентратор ко всем остальным.
Эта топология возникла на заре вычислительной техники, когда компьютеры были подключены к центральному, главному, компьютеру.
Обновлено — 2017-02-16
Типы топологии сетей локальных сетей. Кому-то этот вопрос может показаться не интересным и скучным, но для общего развития, хотя бы вкратце – не помешает. Может, даже где-то вы сможете блеснуть своими познаниями локальной сети, и на вас начнут смотреть с уважением. А может, ваша жизнь повернет так, что вам даже придется столкнуться с этим вопросом вплотную.
У меня именно так и произошло – чего я больше всего боялась, с тем мне и пришлось работать. И оказалось, что все мои страхи были только от не знания, а сейчас мне даже очень нравиться заниматься локальными сетями, и самой обжимать кабеля. Я буду писать коротко и ясно, чтобы не утомить вас подробностями, которые действительно могут вам и не пригодиться.
В чем преимущества локальных сетей вы можете почитать в этих статьях:
Схема физического соединения компьютеров называется топологией сети .
Существует три основных типа топологии сетей . Типы топологии сети — что это такое? Какой тип сети выбрать , чтобы и дешево было и надежно.
Преимуществом такой сети является её достаточно высокая надёжность. Чем больше компьютеров находится в кольце, тем дольше сеть реагирует на запросы. Но самый большой недостаток в том, что при выходе из строя хотя бы одного устройства отказывалась функционировать вся сеть. Да и стоимость такой сети высокая за счёт расходов на кабели сетевые адаптеры и другое оборудование.
2. Линейная топология сети или общая шина
. При линейной топологии все элементы сети подключаются друг за другом с помощью одного кабеля.
Концы сегментов должны быть затерминированы специальными сопротивлениями, которые называются терминаторами .
При создании такой сети не используется дополнительное оборудование – только кабель. Все подключенные устройства в такой сети «слушают» и принимают только те пакеты информации, которые предназначены только для них, а остальные игнорируются.
Преимущества такой сети – простота организации и дешевизна. Но существенным недостатком является низкая устойчивость к повреждениям. Любое повреждение кабеля влечет за собой выход из строя всей сети. Причем поиск неисправности очень сложен.
3. Звездообразная топология является доминирующей в современных локальных сетях. Она наиболее функциональная и стабильная. Каждый компьютер сети подключается к особому устройству, называемому концентратором (hub) или коммутатором (switch). При создании этой топологии каждое устройство получает доступ к сети независимо друг от друга и при обрыве одного соединяющего кабеля перестает работать только один из элементов сети, что существенно упрощает поиск неисправности.
Одним из важнейших различий между разными типами сетей является их топология.
Под топологией обычно понимают взаимное расположение друг относительно друга узлов сети. К узлам сети в данном случае относятся компьютеры, концентраторы, свитчи, маршрутизаторы, точки доступа и т.п.
Топология – это конфигурация физических связей между узлами сети. Характеристики сети зависят от типа устанавливаемой топологии. В частности, выбор той или иной топологии влияет:
Различают следующие основные виды топологий: щит, кольцо, звезда, ячеистая топология и решетка. Остальные являются комбинациями основных топологий и называются смешанными или гибридными.
Шина . Сети с шинной топологией используют линейный моноканал (коаксиальный кабель) передачи данных, на концах которого устанавливаются специальные заглушки – терминаторы (terminator). Они необходимы для того,
Рис. 6.1.
чтобы погасить сигнал после прохождения по шине. К недостаткам шинной топологии следует отнести следующее:
Кольцо – это топология, в которой каждый компьютер соединен линиями связи с двумя другими: от одного он получает информацию, а другому передаст и подразумевает следующий механизм передачи данных: данные передаются последовательно от одного компьютера к другому, пока не достигнут компьютера-получателя. Недостатки топологии "кольцо" те же, что и у топологии "шина":
Звезда – это единственная топология сети с явно выделенным центром, называемым сетевым концентратором или "хабом" (hub), к которому подключаются все остальные абоненты. Функциональность сети зависит от состояния этого концентратора. В топологии "звезда" прямые соединения двух компьютеров в сети отсутствуют. Благодаря этому имеется возможность решения проблемы общедоступности данных, а также повышается устойчивость к повреждениям кабельной системы.
Рис. 6.2.
Рис. 6.3. Топология типа "звезда"
– это топология компьютерной сети, в которой каждая рабочая станция сети соединяется с несколькими рабочими станциями этой же сети. Характеризуется высокой отказоустойчивостью, сложностью настройки и переизбыточным расходом кабеля. Каждый компьютер имеет множество возможных путей соединения с другими компьютерами. Обрыв кабеля не приведет к потере соединения между двумя компьютерами.
Рис. 6.4.
Решетка – это топология, в которой узлы образуют регулярную многомерную решетку. При этом каждое ребро решетки параллельно ее оси и соединяет два смежных узла вдоль этой оси. Одномерная решетка – это цепь, соединяющая два внешних узла (имеющие лишь одного соседа) через некоторое количество внутренних (у которых по два соседа – слева и справа). При соединении обоих внешних узлов получается топология "кольцо". Двух- и трехмерные решетки используются в архитектуре суперкомпьютеров.
Сети, основанные па FDDI, используют топологию "двойное кольцо", достигая тем самым высокой надежности и производительности. Многомерная решетка, соединенная циклически в более чем одном измерении, называется "тор".
(рис. 6.5) – топология, преобладающая в крупных сетях с произвольными связями между компьютерами. В таких сетях можно выделить отдельные произвольно связанные фрагменты (подсети ), имеющие типовою топологию, поэтому их называют сетями со смешанной топологией.
Для подключения большого числа узлов сети применяют сетевые усилители и (или) коммутаторы. Также применяются активные концентраторы – коммутаторы, одновременно обладающие и функциями усилителя. На практике используют два вида активных концентраторов, обеспечивающих подключение 8 или 16 линий.
Рис. 6.5.
Другой тип коммутационного устройства – пассивный концентратор, который позволяет организовать разветвление сети для трех рабочих станций. Малое число присоединяемых узлов означает, что пассивный концентратор не нуждается в усилителе. Такие концентраторы применяются в тех случаях, когда расстояние до рабочей станции не превышает нескольких десятков метров.
По сравнению с шинной или кольцевой смешанная топология обладает большей надежностью. Выход из строя одного из компонентов сети в большинстве случаев не оказывает влияния на общую работоспособность сети.
Рассмотренные выше топологии локальных сетей являются основными, т. е. базовыми. Реальные вычислительные сети строят, основываясь на задачах, которые призвана решить данная локальная сеть, и па структуре ее информационных потоков. Таким образом, на практике топология вычислительных сетей представляет собой синтез традиционных типов топологий.
Качество работы сети характеризуют следующие свойства: производительность, надежность, совместимость, управляемость, защищенность, расширяемость и масштабируемость.
К основным характеристикам производительности сети относятся:
Для оценки надежности сетей используются различные характеристики, в том числе:
Расширяемость означает возможность сравнительно легкого добавления отдельных элементов сети (пользователей, компьютеров, приложений, сервисов), наращивания длины сегментов сети и замены существующей аппаратуры более мощной.
Масштабируемость означает, что сеть позволяет наращивать количество узлов и протяженность связей в очень широких пределах, при этом производительность сети не ухудшается.
Прозрачность – свойство сети скрывать от пользователя детали своего внутреннего устройства, упрощая тем самым его работу в сети.
Управляемость сети подразумевает возможность централизованно контролировать состояние основных элементов сети, выявлять и разрешать проблемы, возникающие при работе сети, выполнять анализ производительности и планировать развитие сети.
Совместимость означает, что сеть способна включать в себя самое разнообразное программное и аппаратное обеспечение.
