Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей

Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ТАВРИЧЕСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

им. В.И.Вернандского

МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА ИНФОРМАТИКИ

ДИПЛОМНАЯ РАБОТА

Проектирование и разработка

сетевых броузеров

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

Выполнил студент 5 курса

специальности «информатика»

_________________Поляков Т.И.

Научный руководитель,

к.ф.-

м.н., доцент

___________________Попов В.Б.

Решение о допуске к защите :

_________________________

Зав.кафедрой информатики

д.ф.-м.н., профессор

________________Донской В.И.

Симферополь

2000 г.

|Содержание | |

|Введение |2 |

| | |

|Глава I. Теоретико-графовые модели организации сетевых |3 |

|структур | |

| | |

| 1.1. Основные понятия теории графов |3 |

| | |

| 1.2. Графовые алгоритмы |5 |

|Глава II. Сетевые структуры на базе теоретико-графовых |11 |

|моделей | |

| 2.1. Методы построения сетевых структур |11 |

| 2.2. Классификация существующих методов |12 |

|организации сетей | |

| 2.3. Глобальная сеть Internet |16 |

| 2.4. Основы сетевой маршрутизации |20 |

| 2.5. Алгоритмы маршрутизации |24 |

|Глава III. Сетевые броузеры |33 |

| 3.1. Описание стандартного броузера |33 |

| 3.2. Характеристика существующих систем поиска |33 |

| 3.3. Особенности создания броузеров в |40 |

|визуальных средах | |

| | |

|программирования | |

| | |

|Глава ??. Программная реализация |44 |

| | |

|4.1. Архитектура системы “броузер” |44 |

| | |

|4.2. Основные процедуры броузера |45 |

| | |

|4.3. Архитектура имитационной модели глобальной сети |47 |

| | |

|4.4. Основные процедуры имитационной модели |48 |

| | |

|Заключение |50 |

| | |

|Список литературы |51 |

| | |

|Приложение 1 – исходный текст программы “броузер” |52 |

| | |

|Приложение 2 – исходный текст модели корпоративной сети |91 |

Введение

Актуальность

В связи с расширением глобальной сети Internet возрастает необходимость

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

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

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

доступные всему миру. Любая современная фирма, любой офис оснащен хотя бы

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

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

в Internet используются программы-броузеры. Эти программы позволяют легко

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

популярную, простую в обращении мультемедийную службу ИНТЕРНЕТ World Wide

Web.

Цель

Цель данной работы заключается в следующем :

- разработка математической модели сетевого броузера и корпоративной

среды;

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

сетях.

Для достижения данной цели были решены следующие задачи:

1.) Проведен анализ существующих броузеров;

2.) Рассмотрены основные топологии существующих корпоративных сетей;

3.) Разработан алгоритм определения оптимального маршрута передачи

информации по глобальной сети.

1.Теоретико – графовые модели

организации сетевых структур

1.1. Основные понятия теории графов

Определение. Множество Х=[pic] и набор U неупорядоченных пар объектов

([pic]) из Х называется графом Г. Объекты множества Х называются вершинами

графа, а наборы объекта U – ребрами графа. Про ребра [pic]будем говорить,

что они соединяют вершины [pic]и [pic].[pic]В случае, если множество Х и

набор U состоят из конечного числа объектов и пар, то граф Г называется

конечным.

Пусть [pic]и [pic]- произвольные вершины графа Г.

Определение. Система ребер графа Г [pic]называется путем, соединяющим

вершины [pic]и [pic].

Определение.Путь [pic], не проходящий дважды одно ребро, называется

циклом, если [pic]=[pic]. В частности, цикл [pic]будем называть петлей.

Определение. Граф Г называется связным, если для любых двух различных

вершин [pic]и [pic]графа Г существует путь, соединяющий эти вершины.

Рис. 1

Легко видеть, что граф из примера 1 является конечным, несвязным и

содержащим петли.

Определение. графы Г и Г` называются изоморфными, если существует

взаимно однозначное соответствие между их вершинами и ребрами такое, что

соответствующие ребра соединяют соответствующие вершины.

Определение. Граф Г` называется подграфом Г, если его вершины и ребра

принадлежат графу Г.

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

Определение. Деревом называется конечный связный граф с выделенной

вершиной, именуемой корнем, не содержащий циклов.

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

собой, то такой граф называют лесом.

Рис 2. Лес, имеющий две компоненты связности (2 дерева).

Будем далее обозначать через Х – множество вершин и U – множество ребер

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

;

x ?X, u ?U. Обозначим длину дуги u=(x,y) через d(u). Кратчайшую длину пути

из х в

z обозначим D(x,z).

Очевидно, если кратчайший путь из x в z существует и проходит через

промежуточную вершину w, то D(x,z) = D(x,w) + D(w,z). Эта формула

справедлива для любой промежуточной вершины w рассматриваемого пути, в том

числе и для последней, смежной с конечной вершиной w. Поэтому кратчайший

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

ближайшую смежную и запоминая цепочку построенных вершин (конечно, при

условии, что хотя бы один путь между вершинами x и z существует и граф не

содержит циклов. Эта идея и является в сущности принципом Р.Беллмана.

1.2. Графовые алгоритмы

Алгоритм Беллмана поиска кратчайшего пути между двумя вершинами связного

графа, не имеющего циклов с неотрицательными длинами ребер. Его описание

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

Идентификаторы :

D[w] – рабочий массив, при вычислениях интерпретируется как кратчайшая

длина из вершины w в вершину z.

w?X.

d[s,t] – массив длин ребер графа для каждой пары вершин s,t ?X. Если

некоторое ребро отсутствует, то в элементе этого массива полагается

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

ребер графа.

Stack – последовательность вершин, определяющая кратчайший путь из x в

z.

Begin

Stack:=’’; // Очистить Stack.

Stack .

n=|X| - число вершин графа.

u,w,k – рабочие переменные.

D[w] – массив, в котором к концу работы алгоритма будут содержаться

кратчайшие длины путей из х в w для всех вершин

w ?X.

Begin

D[x]:=0; // Длина пути из источника

x.

For w ?X do D[w]:=d[x,w]; // Инициализация матрицы расстояний

For k:=1 to n-2 do // Повторять n-2 раз

For w ?{X\{x}} do // Цикл по всем вершинам, кроме

источника.

For u ?X do D[w]:=min(D[w],D[u]+d[u,w]); // выбор

минимума.

End.

Этот алгоритм также основан на соотношении (принципе оптимальности)

Беллмана. Всякий раз, когда находится путь через транзитную вершину u,

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

путь. Это соотношение должно проверяться для любой возможной из n-2

транзитных вершин при оценке пути в каждую вершину, поэтому в алгоритме

имеется цикл, определенный в строке 4.

Алгоритм Дейкстры нахождения кратчайших расстояний от источника до всех

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

когда веса всех ребер неотрицательны.

Идентификаторы :

d[s,t] – массив длин ребер графа для каждой пары вершин

s,t ?X. Если ребра нет, то соответствующий элемент этого массива

содержит достаточно большое число.

х – вершина-источник графа .

n=|X| - число вершин графа.

u,w – рабочие переменные.

D[w] – массив, в котором к концу работы алгоритма будут содержаться

кратчайшие

длины путей из x в w для всех вершин w ?X.

BEGIN

D[x]:=0;

For w ?X do D[w]:=d[x,w];

T:={X\{x}};

While T=\= do

Begin

w:=вершина r из T такая, что D[r]=min{D[p]:p из T};

T:={T\{w}};

For u ?T do D[w]:=min[D[w],D[u]+d[u,w]];

End

END

Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.

Многие задачи исследования операций сводятся к анализу потоков,

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

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

элементов. Для математического представления таких процессов удобно их

задание в виде графов.

Рассмотрим конечный ориентированный граф Г=(X,u), в котором

Х={x1,...,xn}-множество вершин, U – множество дуг.

Пусть x ?X. Обозначим E+(x) – множество дуг графа, входящих в х, E-(x) –

выходящих из х.

Множества начальных вершин дуг из Е+(х) и множество конечных вершин дуг

из Е-(х) обозначим соответственно S+(x) и S-(x).

E+(x) E-(x)

y x

y

S+(x)

S-(x)

Рис. 3. Окрестность вершины графа.

Граф Г называют транспортной сетью, если каждой дуге u соответствует

целое число c(u)>=0 и найдутся x0 и z из Х такие, что Е+(х0)=

Е-(z)= . Вершина х0 называется истоком, z-стоком, c(u) – пропускной

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

функцию ф(u), удовлетворяющую следующим условиям :

1) 00 присвоить пометку

(-xi, min[d(xi), ф(xj,xi)]), что означает возможность уменьшения потока на

величину, определяемую минимумом.

3. Если сток не помечен и можно пометить какую-либо вершину, кроме

стока, то перейти к п.2.

4. Если оказался помеченным сток z, и в его пометку входит число d(z),

то между вершинами x0 и z найдется цепь, все вершины которой помечены

номерами предыдущих вершин. Для каждой помеченной вершины х в этой цепи

изменить величину потока : ф'(y,x)=ф(y,x)+d(z), если х имеет пометку

(+y,d(x)) или ф'(y,x)=ф(y,x)-d(z), если х имеет пометку (-y,d(x)). Пометка

вершины х стирается, назначенные потоки запоминаются. При достижении (в

процессе стирания пометок вершин цепи) истока х0 перейти к п.1; если же ни

одну вершину пометить не удается и сток z не помечен, то перейти к

построению разреза.

II.Построение разреза.

Искомый минимальный размер R определяется двумя множествами Х1 и Х2, где

Х1 – все помеченные вершины, Х2 – вершины, которые не удается пометить. При

этом полный поток Ф=Ф* должен быть равен величине полученного минимального

разреза.

2.Сетевые структуры на базе

теоретико-графовых моделей

2.1. Методы построения сетевых структур

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

компьютеры, предоставляющие ресурсы в сети (серверы), компьютеры,

обеспечивающие доступ к сетевым ресурса серверов (клиенты), среду (media),

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

принтеры, и другие элементы. В сетях реализуется принципиальная возможность

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

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

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

Различают сети с выделенными серверами и одноранговые сети. В настоящее

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

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

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

функционировать одновременно в качестве сервера, если этого требуют задачи.

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

(выделенный сервер) используется для установки всех разделяемых ресурсов.

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

сети и связано с рядом особенностей :

- сетевое администрирование проще за счет незначительного числа серверов

в сети и их узкой специализации;

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

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

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

использования в сервере производительного процессора;

- при нарушении работы сервера сеть становится практически

неработоспособной.

Если в одноранговой сети нет выделенного сервера, все компьютеры

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

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

Одноранговая сеть на основе сервера содержит выделенный сервер. Сеть

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

назначение :

- файл-серверы;

- принт-серверы;

- серверы приложений, на которых выполняются прикладные задачи;

- почтовые серверы;

- факс-серверы;

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

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

мэйнфреймами (большими ЭВМ) или удаленными пользователями через модемы и

телефонные линии;

- серверы служб каталогов, обеспечивающие поиск, хранение и защиту

информации в сети.

В комбинированных сетях совмещаются лучшие качества одноранговых сетей и

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

компоненты могут разрешать доступ к своим данным.

2.2. Классификация существующих методов организации сетей

Базовые топологии локальных сетей

Базовые топологии локальных сетей – это основные виды конфигураций

соединений элементов сетей при помощи кабеля.

Рассмотрим три базовых топологии : шина, звезда и кольцо.

Шина (или линейная шина) – это топология, представленная на рис. 4.

Рис. 4. Простейшая одноранговая сеть.

Передаваемый сигнал распространяется по кабелю – магистрали (сегменту) и

поглощается на концах терминаторами (заглушками). В любой момент времени

только один компьютер может вести передачу. Данные передаются всем

компьютерам сети, однако информацию принимает только тот, адрес которого

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

Говорят, что шина – пассивная топология. Компьютеры только “слушают”, но

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

баррел-коннекторов и репитеров.

Баррел-коннекторы – это специальные металлические соединительные

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

сигнал ощутимо затухает. Для решения проблемы сохранения физических

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

специальные устройства.

Репитер – это повторитель-формирователь, просто усиливающий сигнал.

Топология звезда предусматривает подключение всех компьютеров с помощью

сегментов кабеля к центральному элементу. Различают два подтипа этой

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

кабели соединены при помощи концентратора (hub), и активная звезда,

содержащая в центре компьютер, управляющий обменом информации в сети.

Концентратором (hub) называют устройство, служащее для объединения

нескольких сегментов сети и не преобразующее передаваемую информацию.

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9