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

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

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

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

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

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

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

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

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

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

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

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

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

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

к.ф.-м.н., доцент

___________________ПоповВ.Б.

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

_________________________

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

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

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

Симферополь

2000 г.

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

3.3. Особенности создания броузеров в визуальных средах

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

Глава IÑ. Программная реализация

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

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

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

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

Заключение

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

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

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

Введение

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

В связи срасширением глобальной сети Internet возрастает необходимость внедрения новыхоптимизационных алгоритмов, связанных со скоростью обмена данных междукомпьютерами в единой сети. Компьютерные сети завоевывают мир. Системы измаленьких компьютеров превращаются в огромные хранилища данных, доступные всемумиру. Любая современная фирма, любой офис оснащен хотя бы простейшей сетью. Невыходя из дома, сотни тысяч людей работают на персональных компьютерах, приносяпользу всему миру. В основном для работы в Internet используются программы-броузеры. Эти программы позволяют легко обмениваться текстовой, графической извуковой информацией, используя популярную, простую в обращении мультемедийнуюслужбу ИНТЕРНЕТ WorldWide Web.

Цель

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

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

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

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

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

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

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

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

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

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

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

Определение.Множество Х=<img src="/cache/referats/9569/image002.gif" v:shapes="_x0000_i1025"> и набор U неупорядоченных пар объектов (<img src="/cache/referats/9569/image004.gif" v:shapes="_x0000_i1026">U – ребрамиграфа. Про ребра <img src="/cache/referats/9569/image006.gif" v:shapes="_x0000_i1027">будем говорить, что они соединяют вершины <img src="/cache/referats/9569/image008.gif" v:shapes="_x0000_i1028"><img src="/cache/referats/9569/image010.gif" v:shapes="_x0000_i1029"><img src="/cache/referats/9569/image012.gif" v:shapes="_x0000_i1030">U состоят из конечного числа объектов и пар, то граф Гназывается конечным.

Пусть <img src="/cache/referats/9569/image008.gif" v:shapes="_x0000_i1031"><img src="/cache/referats/9569/image010.gif" v:shapes="_x0000_i1032">

Определение.Система ребер графа Г <img src="/cache/referats/9569/image014.gif" v:shapes="_x0000_i1033">путем,соединяющим вершины <img src="/cache/referats/9569/image008.gif" v:shapes="_x0000_i1034"><img src="/cache/referats/9569/image010.gif" v:shapes="_x0000_i1035">

Определение.Путь <img src="/cache/referats/9569/image016.gif" v:shapes="_x0000_i1036">циклом, если <img src="/cache/referats/9569/image008.gif" v:shapes="_x0000_i1037"><img src="/cache/referats/9569/image010.gif" v:shapes="_x0000_i1038"><img src="/cache/referats/9569/image018.gif" v:shapes="_x0000_i1039">петлей.

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

вершин<img src="/cache/referats/9569/image008.gif" v:shapes="_x0000_i1040"><img src="/cache/referats/9569/image010.gif" v:shapes="_x0000_i1041">

<img src="/cache/referats/9569/image022.gif" v:shapes="_x0000_s1026"> <img src="/cache/referats/9569/image023.gif" v:shapes="_x0000_s1031"> <img src="/cache/referats/9569/image024.gif" v:shapes="_x0000_s1036">
Рис. 1

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

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

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

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

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

<img src="/cache/referats/9569/image026.gif" v:shapes="_x0000_s1059 _x0000_s1124">
Если в графе можновыделить более одного дерева, которые не связны между собой, то такой графназывают лесом.

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

Будем далее обозначать через Х – множествовершин и U – множество ребер графа, а сам граф,определяемый этой парой объектов, будем обозначать <X,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 в нее же.

Whilew=/=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. Если ребра нет, тосоответствующий элемент этого массива содержит достаточно большое число.

х – вершина-источник графа <X,U>.

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. Если ребра нет, то соответствующий элементэтого массива содержит достаточно большое число.

х – вершина-источник графа <X,U>.

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 doD[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).

<img src="/cache/referats/9569/image032.gif" v:shapes="_x0000_s1079"><img src="/cache/referats/9569/image033.gif" v:shapes="_x0000_s1078"><img src="/cache/referats/9569/image034.gif" v:shapes="_x0000_s1067"><img src="/cache/referats/9569/image034.gif" v:shapes="_x0000_s1066"> E+(x) E-(x)

<img src="/cache/referats/9569/image035.gif" v:shapes="_x0000_s1081"> <img src="/cache/referats/9569/image036.gif" v:shapes="_x0000_s1080">
<img src="/cache/referats/9569/image037.gif" v:shapes="_x0000_s1076"> <img src="/cache/referats/9569/image038.gif" v:shapes="_x0000_s1075">
y x y

S+(x) S-(x)

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

<img src="/cache/referats/9569/image040.gif" v:shapes="_x0000_s1086"><img src="/cache/referats/9569/image040.gif" v:shapes="_x0000_s1082">Граф Г называют транспортной сетью,если каждой дуге u соответствует целое число c(u)>=0 и найдутся x0 иz из Х такие, что Е+(х0)=

Е-(z)= . Вершина х0 называется истоком, z-стоком,c(u) – пропускной способностьюдуги. Потокомв транспортной сети называютцелочисленную функцию ф(u), удовлетворяющую следующим условиям :

1)0<=ф(u)<=с(u)

<img src="/cache/referats/9569/image042.jpg" v:shapes="_x0000_s1089">2) ф(u)- ф(u) = 0 для любой вершины x=/=x0, x=/=z.

uÎЕ+(х) uÎЕ-(х)

При этом поток не может «накапливаться» ни водной вершине транспортной сети, кроме истока х0 и стока z, поэтому

<img src="/cache/referats/9569/image042.jpg" v:shapes="_x0000_s1090"><img src="/cache/referats/9569/image042.jpg" v:shapes="_x0000_s1087"> ф(u) = ф(u) = Ф.

uÎЕ+(х) uÎЕ-(х)

ВеличинуФ называют потоком транспортной сети.Дуга u называетсянасыщенной, если ф(u)=c(u).Поток Ф называется полным, есликаждый путь из х0 в z содержит хотя бы одну насыщенную дугу.

Рассмотримразбиение R множествавершин сети Х = Х1UX2,

X1ÇX2, X1ÇX2=Æ, x0ÎX1, zÎX2, называемоеразрезом сети.

<img src="/cache/referats/9569/image042.jpg" v:shapes="_x0000_s1091">Сумма пропускных способностей множества {(xi,xj), xi из X1, Xj изХ2} определяет пропускную способность разреза R: r(R) = c(u),

uÎ{(xi,xj):xi ÎX1, xjÎX2}

Поскольку для любой дуги u выполняется неравенство ф(u)<=c(u),то Ф<=r(R).

Теорема Форда-Фалкерсона : максимальныйпоток в сети равен минимальной величине разрезов в этой сети.

Алгоритмнахождения максимального потока, предложенный Фордом и Фалкерсоном, состоит впостепенном увеличении допустимого потока Ф до максимальной величины Ф*.Начальное значение потоков полагается равным нулю. Процесс увеличения потокасостоит в поиске путей, на которых возможно увеличение потока, ссоответствующей разметкой вершин сети.

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

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

<img src="/cache/referats/9569/image044.jpg" v:shapes="_x0000_s1092">I. Увеличениепотока.

<img src="/cache/referats/9569/image044.jpg" v:shapes="_x0000_s1094">1. Присвоить истоку х0пометку (+х0, d(x0) = ). Это означает, что вход висток не ограничен; величина d всегда показывает, насколько может быть увеличен поток, входящий в помеченную вершину. Здесьсимвол обозначает достаточно большое число –начальное значение пометки.

2. Взять некоторую вершину xi спометкой, которая в общем случае имеет вид (+ или – xk, d(xi)), где xk – обозначение вершины, d(xi) – некотороечисло. Каждой непомеченной вершине xj из S-(xi), для которой ф(xi,xj)<с(xi,xj), присвоить пометку (+xi,min[d(xi),c(xi,xj)-ф(xi,xj)]). Это означает, что поток в дуге (xi,xj) можетбыть увеличен (знак плюс) на величину, определяемую минимумом. Каждойнепомеченной вершине xj из S+(xi), такой, что ф(xj,xi)>0 присвоить пометку (-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) называют устройство, служащее дляобъединения нескольких сегментов сети и не преобразующее передаваемуюинформацию. Сигналы от передающего компьютера поступают через концентратор ковсем остальным. Концентраторы бывают активные, пассивные и гибридные.

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

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

Сервер

Рис.5.Топология “Кольцо”.

Типы кабелей

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

— Коаксиальный (coaxial), подразделяющийся на толстый и тонкий;

— Витая пара (twisted pair), имеющая два типа: неэкранированная (10 Base-T) и экранированная.

— оптоволоконный (fiber optic).

Толстый кабель обеспечивает передачу сигналов на большиерасстояния, чем тонкий, -до 500 метров, и часто используется в качестве основного магистрального кабеля (backbone).

Для подключения к толстому коаксиальномукабелю применяют специальное устройство – трансивер(TRANSmitter/reCEIVER– передатчик.приемник), устройство,преобразующее поток параллельных данн

еще рефераты

Еще работы по компьютерным сетям

Реферат по компьютерным сетям

Защита информации в Интернете

29 Августа 2013

Реферат по компьютерным сетям

Информационная система (ІНФОРМАЦІЙНА СИСТЕМА ОБЛІКУ І АНАЛІЗУ РОЗРАХУНКІВ З ПОСТАЧАЛЬНИКАМИ І ПІДРЯДНИКАМИ)

29 Августа 2013

Реферат по компьютерным сетям

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

29 Августа 2013

Реферат по компьютерным сетям

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

29 Августа 2013