Сравнительный анализ производительности методов "асинхронная Алоха" и CSMA/CD

Размещено на http://www.allbest.ru/

3

Размещено на http://www.allbest.ru/

Государственное образовательное учреждениевысшего профессионального образования

Кубанский государственный технологический университет

(КубГТУ)

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

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

на тему

Сравнительный анализ производительности методов «асинхронная Алоха» и CSMA/CD

Краснодар

2009

Реферат

СЛУЧАЙНЫЙ ДОСТУП К СЕТИ, КОЛЛИЗИИ, ЧИСТАЯ АЛОХА, СООБЩЕНИЕ, СХЕМА МНОГОСТАНЦИОННОГО ДОСТУПА С ПРОВЕРКОЙ НЕСУЩЕЙ (МДПН), ОБНАРУЖЕНИЕ СТОЛКНОВЕНИЯ (ОС).

Объектом исследования являются метод «асинхронной Алохи» и CSMA/CD.

Цель работы состоит в создании программы на основе методов «асинхронной Алохи» и CSMA/CD и сравнении их производительности.

К полученным результатам относится созданная программа методов случайного доступа к сети типа «асинхронная Алоха» и CSMA/CD, а также сравнение производительности этих методов.

Содержание

программа сеть доступ случайный

Введение

1. Теоретическая часть

1.1 Постановка задачи

1.2 Описание метода «асинхронная Алоха»

1.3 Описание метода CSMA/CD

1.4 Блок-схема

2.Практическая часть

2.1 Описание кода программы

2.2 Анализ результатов выполнения программы

Заключение

Список использованных источников

Введение

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

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

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

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

В данном курсовом проекте рассматриваются два метода случайного доступа к сети: метод «асинхронной Алохи» (ее также называют Чистая Алоха) и метод CSMA/CD. Сначала методы случайного доступа были предложены для случаев, когда многие пользователи пытаются довольно редко передать пачки сообщений или когда друг с другом связываются небольшое число ЭВМ. Но применительно к производственным процессам, которые требуют строгого управления задержкой доступа, более предпочтителен управляемый доступ.

Целью исследования является закрепление основ и углубление знаний в области случайного доступа к сети, детальное изучение методов «асинхронной Алохи» и CSMA/CD, создание программного продукта для сравнения производительности данных методов.

Исследование проводится с использованием среды разработки программного обеспечения Borland Delphi 7.0.

Конечным результатом должна быть готовая и отлаженная программа для сравнительного анализа производительности методов «асинхронная Алоха» и CSMA/CD.

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

программа сеть доступ случайный

1. Теоретическая часть

1.1 Постановка задачи

Построить программу на основе методов «асинхронная Алоха» и CSMA/CD для нахождения производительности.

Для метода «асинхронная Алоха» найти:

· Нормированную порпущенную нагрузку

· Нормированную производительность

Для метода CSMA/CD найти:

· Виртуальное время передачи

· Производительность

Затем на основе результатов провести сравнительный анализ производительности, выявить, какой метод является более эффективным.

1.2 Описание метода «асинхронная Алоха»

Эта схема сначала была применена для доступа к общему каналу сотрудниками Гавайского университета в начале 1970-х годов. По этой схеме пользователь, желающий передать сообщение, делает это когда угодно. В результате могут наложится во времени два или несколько сообщений, вызвав столкновение (коллизию).

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

Стратегия доступа типа Чистая Алоха позволяет добиться производительности самое большее 1/2e 0,18 пропускной способности канала. Введем сначала некоторые определения. За доступ к каналу состязаются N станций. Станция передает, в среднем, пакетов в секунду (интенсивность обращений к сети). Величина 1/m представляет собой пропускную способность канала (1/) в передаваемых пакетах в секунду. Рассмотрим частный случай, при котором все передаваемые сообщения (пакеты) имеют среднюю длину, соответствующую m единицам времени передачи. Будем считать, что интенсивность нагрузки S (эквивалентно - нормированной по нагрузке) характеризует использование канала вновь поступающими пакетами.

(1)

Величина 1/m, которая обозначается , представляет собой пропускную способность канала в передаваемых пакетах в секунду. Таким образом, N/ Nm - относительное использование канала, или производительность, нормированная относительно . Общая интенсивность пакетов, передаваемых в канал, включая вновь генерируемые и передаваемые повторно, имеет некоторое значение ' > (из-за коллизий от каждого компьютера будет передаваться больше сообщений из-за необxодимости возобновлять поток). Тогда фактическая интенсивность нагрузки, или использование канала, является параметром G.

(2)

Рассмотрим типичное сообщение длительностью m (рис. 1).

Рисунок 1-Столкновение двух сообщений

Оно подвергается столкновению с другим сообщением, если эти два сообщения будут наложены одно на другое в любой точке. Легко заметить, передвигая пунктирное сообщение во времени, что столкновение может произойти в промежутке времени продолжительностью 2m с. Вероятность того, что в промежутке 2m с не произойдет столкновения, равна e^-2N'^m=e^-2G.

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

(3)

где S - нормированная производительность (средняя скорость поступления пакетов, деленная на максимальную производительность 1/m),

G - нормированная пропущенная нагрузка.

1.2 Описание метода CSMA/CD

Основная концепция протокола МДПН/ОС очень проста. Все станции прослушивают передачу по линии. Станция, желающая передать сообщение, выходит на связь только после обнаружения свободного состояния канала. Эта процедура называется проверкой несущей, а стратегия, основанная на такой проверке, схемой многостанционного доступа с проверкой несущей (МДПН). Очевидно, столкновения все же могут возникнуть, поскольку станции физически разнесены одна от другой и две или несколько станций могут обнаружить свободное состояние канала и начать передачу, что и вызовет столкновение. Если станции обнаруживают столкновение (обнаружение столкновения - ОС), они передают всем остальным станциям специальный сигнал о помехе и отменяют свои передачи. Возможность проверки несущей позволяет увеличить производительность канала по сравнению с чистой Алохой, а обнаружение столкновения с прекращением передачи вместо его завершения дает еще большее повышение производительности.

Был предложен и проанализирован ряд методов МДПН. Они различаются тем, как происходит управление передачей, если канал оказался занятым. Например, в схеме с p-настойчивостью станция, обнаружившая занятый канал, осуществляет передачу после того, как канал станет свободным, с вероятностью p. С вероятностью (1-p) передача откладывается на промежуток времени распространения сигнала. При схеме с 1- настойчивостью станция осуществляет попытку передачи, как только канал окажется свободным. При ненастойчивой схеме станция переносит передачу на другое время в соответствии с предписанным распределением задержек передачи, проверяет несущую в это время и продолжает процесс.

Протокол МДПН/ОС, работающий по правилу 1-настойчивости с добавлением возможности обнаружения столкновений в целях дальнейшего улучшения характеристик принят в качестве протокола в схеме Ethernet. Если обнаруживается столкновение и передача прекращается, попытка повторной передачи принимается через случайный промежуток времени, как и в схемах Алоха. Этот случайный промежуток времени удваивается каждый раз после обнаружения нового столкновения до некоторой максимальной величины, при которой станция выходит из строя и извещают вышестоящие уровни о нарушении связи. Удвоение промежутка называется процедурой двоичного замедления и может улучшить характеристику системы.

Проведем анализ системы с дискретным временем, чтобы выявить характеристики задержек протокола МДПН/ОС.

Рассмотрим шинную структуру.

Рисунок 2-Модель МДПН/ОС

Станции подключаются через пассивные ответвления к двусторонней шине. Сосредоточим внимание на двух наиболее удаленных станциях (А и В). Рассчитаем среднее время, требуемое для успешного запуска сообщения в шину. Обратная величина такого времени и будет максимальной производительностью. Назовем время до успешного завершения передачи сообщения виртуальным временем передачи t_v. Это время имеет три составляющие (см. рисунок 3). Оно включает время m, требуемое для передачи сообщения, время , требуемое для проверки завершения передачи, и время, кратное 2 единицам, для разрешения столкновений, если они обнаруживаются.

Пусть возникло столкновение между сигналами, передаваемыми станциями А и В. В худшем случае обнаружение столкновения займет на станциях А и В время в 2 с, после чего передача будет немедленно выключена. Это показано на рисунке 3: станция А начинает передачу в некоторый момент времени. Перед тем как сообщение станции А поступит на станцию В, последняя решает начать передачу. Станция В проверяет канал, находит его свободным и начинает собственную передачу. Это очевидное столкновение, которое обнаружится только через c.

Рисунок 3- Расчет виртуального времени передачи МДПН/ОС

Общее время до обнаружения столкновения составит 2 единиц времени, что и показано на рисунке.

Если произошло столкновение, предположим, что для его разрешения потребуется 2J единиц времени. J представляет собой среднее число повторных передач после того, как произошло столкновение. Оно сравнимо с параметром E=G/S-1, который был введен при изучении системы Алоха. Тогда виртуальное время передачи имеет вид:

t_v = m + + 2J = m [1+a(1+2J)], a /m. (4)

Далее найдем величину J. Она зависит от стратегии повторной передачи.

Рисунок 4-Наихудший случай обнаружения столкновения

Предположим, что длительность интервала столкновения (рисунок 3) описывается геометрическим распределением единиц 2 с параметром . В частности, интервал равен одной единице (2) с вероятностью , двум единицам с вероятностью *(1-) и т.д. Таким образом, является вероятностью успеха в конце интервала, а (1-) - вероятностью столкновения. Среднее число повторных передач J=1/, а именно

(5)

Это рассуждение переносит тяжесть нахождения J на .

Найдем вероятность .

Пусть в возможных передачах участвуют n станций (n >> 1). Пусть вероятность того, что одна станция намеревается передавать в промежутке времени 2 c, равна p. Тогда вероятность того, что передает одна станция, (а эта передача успешна)

= n p (1-p)^n-1 (6)

Используя величину p=1/n и учитывая, как предполагалось, что n >> 1, в пределе получим, что

_max = (1-1/n)^n-1 e ^-1, n (7)

Таким образом, величина , которую нужно подставить в (5), равна e ^-1. И равенство (4) принимает вид:

t_v = m [1+a(1+2e)], a / m. (4 а)

Максимальная производительность _max в числе сообщений за единицу времени равна 1/t. Обозначая через среднее число сообщений, передаваемых по каналу за единицу времени от всех пользователей, и нормируя его относительно пропускной способности 1/m (в сообщениях за единицу времени), из (4 а) находим

а / m. (8)

Пусть в качестве примера а=0,1. Это значит, что длительность сообщений в десять раз больше времени распространения сигнала из конца в конец. Для этого значения а имеем <0,6.

1.3 Блок-схема алгоритма сравнения производительности методов «асинхронная Алоха» и CSMA/CD

2. Практическая часть

2.1 Описание кода программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class(TForm)

GroupBox1: TGroupBox;

Label1: TLabel;

Edit1: TEdit;

Label2: TLabel;

Edit2: TEdit;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Button1: TButton;

Button2: TButton;

GroupBox2: TGroupBox;

Label7: TLabel;

Edit3: TEdit;

Label8: TLabel;

Edit4: TEdit;

Label9: TLabel;

Label10: TLabel;

Label11: TLabel;

Label12: TLabel;

Button3: TButton;

Button4: TButton;

Edit5: TEdit;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

S,P:real;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject); var

{процедура нахождения производительности метода Алоха}

N,M:integer; (количество станций и длительность сообщения)

L,G:real;{интенсивность обращений к сети и нормированная пропущенная нагрузка}

begin

L:=0.0039;

N:=StrToInt(Edit1.Text);

M:=StrToInt(Edit2.Text);

G:=L*N*M; {находим нормированную пропущенную нагрузку}

S:=G*exp((-2)*G); {находим нормированную производительность}

Label4.Caption:=FloatToStr(G);

Label6.Caption:=FloatToStr(S);

end;

procedure TForm1.Button2Click(Sender: TObject);

{процедура выхода из программы}

begin

close();

end;

procedure TForm1.Button3Click(Sender: TObject);

{процедура нахождения производительности метода CSMA/CD}

var

Tv,a:real;

M1,T1:integer;

begin

T1:=StrToInt(Edit4.Text);{время, требуемое для проверки завершения передачи}

M1:=StrToInt(Edit3.Text);{время, требуемое для передачи сообщения}

a:=T1/M1;

Label14.Caption:=FloatToStr(a);

Tv:=M1*(1+a*6.44); {находим виртуальное время}

P:=1/(1+a*6.44); {находим производительность}

Label10.Caption:=FloatToStr(Tv);

Label12.Caption:=FloatToStr(P);

end;

procedure TForm1.Button4Click(Sender: TObject);

begin

if S>P then Edit5.Text:='Алоха эффективнее'

else Edit5.Text:='CSMA/CD эффективнее';

{сравниваем производительности методов}

end;

end.

2.2 Анализ результатов выполнения программы

При запуске программы открывается окно «Сравнительный анализ производительности методов «Асинхронная Алоха» и CSMA/CD». Пользователю нужно ввести необходимые значения. После чего при нажатии кнопки «Посчитать» информации о производительности методов появится автоматически. При нажатии кнопки «Сравнить» автоматически появится информация о том, какой метод является более эффективным.

Рисунок 5- Сравнительный анализ производительности методов «асинхронная Алоха» и CSMA/CD (вариант 1)

В данном случае метод «асинхронной Алохи» оказался эффективнее, чем метод CSMA/CD. Заметим, что стратегия типа «асинхронная Алоха» позволяет добиться производительности самое большее S ? 0,18 пропускной способности канала при G=0,5.

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

Рисунок 6- Сравнительный анализ производительности методов «асинхронная Алоха» и CSMA/CD (вариант 2)

За счет увеличения длительности сообщения и уменьшения времени для проверки завершения передачи метода CSMA/CD, мы получаем, что метод CSMA оказался более эффективным. Если значение а уменьшить еще больше (путем сокращения длины кабеля или уменьшения пропускной способности в бит/с в целях увеличения m), соответственно увеличится _max, приближаясь к максимально возможному значению, равному 1.

Заключение

Целью исследования является закрепление основ и углубление знаний в области случайного доступа к сети, детальное изучение методов «асинхронной Алохи» и CSMA/CD, создание программного продукта для сравнения производительности данных методов.

В ходе выполнения исследования был создан программный продукт в среде Borland Delphi 6.0 для сравнительного анализа производительности методов «асинхронная Алоха» и CSMA/CD.

Были углублены знания и получены навыки анализа алгоритмов. Сравнивая производительности соответствующих методов, стало очевидным, что метод CSMA/CD существенно эффективней, чем «асинхронная Алоха». Максимальное значение производительности чистой Алохи составляет 0,18, а производительность метода CSMA/CD равно 1.

Протокол МДПН/ОС основан на методе чистой Алохи и позволяет улучшить ее характеристики. Метод МДПН/ОС входит в протокол сети Ethernet и принят, как один из стандартных методов в локальных сетях. Реализация локальных сетей по образцу сети Ethernet распространена весьма широко.

Список использованных источников

1. Блэк Ю. Сети ЭВМ. Протоколы, стандарты, интерфейсы. - М.: Мир, 1990.

2. Лойко В.И., Лаптев В.Н., Луценко Е.В., Постный В.А. Вычислительные системы, сети и телекоммуникации: Методические указания по подготовке курсовых работ (для студентов специальностей 351400 - Прикладная информатика в экономике). - Краснодар: КубГТУ, 2003. - 46с.

3. Шварц М. "Сети связи: протоколы, моделирование, анализ: в 2-х ч.Ч. 2" - М.: Наука- 1992.-272с.

4. Кравченко П.П., Чефранов А.Г. Методы управления ресурсами вычислительных систем: Учебное пособие. - Таганрог: Таганрогский ГРТИ, 1991.

5. Фаронов В.В. «Delphi 6» - М.: Издатель Молгачева С.В., 2001. - 672 с.

6. http://algolist.manual.ru/ - Алгоритмы, методы, исходники.

7. Семенов М.И, Лойко В.И., Барановская Т.П. Компьютерные системы и сети: Учебное пособие для студентов специальности 0719 - "Информационные системы в экономике" и других экономических специальностей вузов. - Краснодар: КубГАУ, 2000. - 215с.

Размещено на Allbest