Xreferat.com » Рефераты по информатике и программированию » Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей

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

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

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

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


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

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


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


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

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

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


Выполнил студент 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. Основные понятия теории графов

Определение. Множество Х=Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей и набор U неупорядоченных пар объектов (Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей) из Х называется графом Г. Объекты множества Х называются вершинами графа, а наборы объекта U – ребрами графа. Про ребра Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделейбудем говорить, что они соединяют вершины Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделейи Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей.Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделейВ случае, если множество Х и набор U состоят из конечного числа объектов и пар, то граф Г называется конечным.

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

Определение. Система ребер графа Г Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделейназывается путем, соединяющим вершины Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделейи Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей.

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

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


вершин Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделейи Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделейграфа Г существует путь, соединяющий эти вершины.

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

Рис. 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 <=z; // Поместить в стек конечную вершину z.

w:=z; // Запомнить первую пройденную вершину.

D[z]:=0; // Обнуление длины пути из вершины z в нее же.

While w=/=x do // Пока не будет достигнута начальная вершина, выполнять

// перебор вершин графа

p:= вершина, для которой величина D[p] = d[p,w]+D[w] минимальна. Если таких вершин несколько и среди них имеется вершина x, то p:=x, если же среди них нет вершины x – взять любую из доставляющих минимум сумме.

Stack <=p; // Записать выбранную вершину в стек.

w:=p; // и взять ее для построения следующего шага.

End;

End.

Пусть число вершин графа |X|=n, а число ребер |U|=m. Оценим сложность этого алгоритма как число шагов выполнения алгоритмической схемы, считая одним шагом выполнение ровно одного выполнимого оператора, каковые представлены только строками 2,3,4,5,6,8,9. В худшем случае выбор вершины в строке 8 (по минимуму расстояния) произойдет в результате просмотра всех n вершин, а цикл с заголовком в строке 6 повторится для всех вершин, поэтому сложность алгоритма можно оценить как C*n^2, где С – некоторая константа, учитывающая реализацию алгоритма в произвольной вычислительной среде.


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

Алгоритм Форда-Беллмана

Идентификаторы : d[s,t] – массив длин ребер графа для каждой пары вершин s,t X. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число.

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

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. Окрестность вершины графа.

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: