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

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

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

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

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

2.5 Сравнительный анализ

Разработка алгоритма динамической маршрутизации на базе протокола OSPF

При рассмотрении принципов MPLS обсуждалась необходимость заполнения в маршрутизаторах LSR таблиц меток, используемых при маршрутизации пакетов по сети MPLS. Для этого в каждом из узлов сети с использованием протокола маршрутизации создается база топологической информации о сетевых маршрутах. Наряду с рассматриваемыми протоколами BGP4 и IS-IS, для этой цели может быть применен протокол маршрутизации по состояниям каналов OSPF (Open Shortest Path First -- "первым выбирается кратчайший путь"). Поскольку OSPF используется наиболее часто, рассмотрение протоколов маршрутизации для MPLS в начинается именно с него.

Протокол OSPF относится к протоколам внутреннего шлюза IGP (Interior Gateway Protocol). К этой категории принадлежат протоколы маршрутизации, обеспечивающие обмен информацией в пределах автономной системы AS (Autonomous Systemпредставляет собой сеть, находящуюся под единым административным управлением).

Метрики OSPF

В OSPF используется принцип контроля состояния канала (link-state protocol), а метрика представляет собой оценку эффективности связи в этом канале: чем меньше метрика, тем эффективнее организация связи. В простейшем случае метрика маршрута может равняться его длине в пересылках (hops), как это происходит в протоколе RIP. Но в общем случае значения метрики могут определяться в гораздо более широком диапазоне.

Метрика, оценивающая пропускную способность канала, определяется, например, компанией CISCO, как количество секунд, нужное для передачи 100 Мбит. Имеется следующая формула для вычисления метрики доставки информации через каналы сети OSPF:метрика = 10⁸/скорость передачи в битах в секунду.

По этой формуле вычислены, например, следующие метрики:

· канал со скоростью 100 Мбит/с соответствует метрике 1;

· сеть Ethernet / 802.3 соответствует метрике 10;

· тракт Е1 2,048 Мбит/с соответствует метрике 48;

· тракт Т1 1,544 Мбит/с соответствует метрике 65;

· канал 64 Кбит/с соответствует метрике 1562;

· канал 56 Кбит/с соответствует метрике 1785;

· канал 19,2 Кбит/с соответствует метрике 5208;

· канал 9,6 Кбит/с соответствует метрике 10416.

Кроме того, протокол OSPF позволяет определить для любой сети значения метрики в зависимости от типа услуги ToS (Type ofService). Для каждой из метрик протокол OSPF строит отдельную таблицу маршрутизации. Чаще всего OSPF выбирает маршрут на основании полосы пропускания канала.

Архитектура сети MPLS

Технология Multiprotocol Label Switching (MPLS -- многопротокольная коммутация по меткам) -- это технология передачи данных от одного узла к другому, использующая метки для принятия решения о выборе маршрута. Технология MPLS подразделяется на две технологии: MPLS L2 VPN и MPLS L3 VPN. При использовании в сети технологии MPLS L2 VPN передача данных осуществляется на втором уровне модели OSI, используя такие технологии как Ethernet, Frame Relay и ATM. При использовании в сети технологии MPLS L3 VPN передача данных осуществляется на третьем уровне модели OSI, используя технологию IP [3]. MPLS сеть предоставляет широчайшие возможности передачи данных: возможность организовать множество соединений для одной организации, поддержка приложений реального времени (голос и видео). Маршруты в MPLS сети вычисляются посредством таких протоколов как BGP, OSPF, IS-IS и RIP [1].

Технологию MPLS L3 VPN можно использовать поверх магистральной MPLS сети, либо поверх магистральной IP сети, используя протоколы GRE, L2TPv3 и другие туннельные протоколы.

На рисунке 1 отображена простая магистральная MPLS сеть с применением технологии MPLS L3 VPN, которая обслуживает две организации, расположенные в разных городах (“City3”, “City5” и “City6”). Магистральная MPLS сеть состоит из следующих маршрутизаторов: «City1», “City2”, “City3_PE”, “City4”, “City5_PE” и “City6_PE”. Сети “Net1_A” и “Net1_B” относятся к одной организации, а сети “Net2_A” и “Net2_B” -- к другой.

Рисунок 2.5 Магистральная MPLS сеть

Обозначение «PE» в названии города означает, что в этом городе находится граничный маршрутизатор провайдера (Provider Edge). Обозначение «CE» в названии города означает, что в этом городе расположен граничный маршрутизатор клиента (Customer Edge) [2]. В городах, названия которых не содержат подобные обозначения, расположены промежуточные маршрутизаторы, повышающие надежность и отказоустойчивость MPLS сети. Такие маршрутизаторы провайдера могут стать граничными, если в соответствующем городе клиент захочет создать сеть своей организации.

В сетях, использующих технологию MPLS L3 VPN, можно выделить следующие преимущества (для пояснения будет использоваться сеть, изображенная на рисунке 1):

1. Независимость адресного пространства организаций -- сети разных организаций изолированы друг от друга.

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

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

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

5. Протокол MPLS используется совместно с другими протоколами: IP, IS-IS, OSPF, RIP и BGP [1].

6. В магистральных MPLS сетях можно гарантировать пропускную способность.

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

8. В магистральной MPLS сети можно организовать технологию VPLS (Virtual Private LAN Service -- технология организации виртуальной частной сети) -- создать виртуальный коммутатор, работающий на уровне L2 модели OSI, а в качестве граничного оборудования клиента использовать обычные коммутаторы. На рисунке 2 приведен пример реализации технологии VPLS для одной организации с офисами, расположенными в разных городах.

Рисунок 2.6 Технология VPLS

9. Технология MPLS L3 VPN позволяет создать много виртуальных маршрутизаторов и интерфейсов в магистральной MPLS сети, которые сконфигурированы отдельно для каждой организации. В качестве примера на рисунке 3 отображена одна организация, имеющая соединение между своими офисами, расположенными в разных городах, через виртуальный маршрутизатор.

Рисунок 2.7 Виртуальный маршрутизатор в MPLS сети

Недостатки:

1. Сложность реализации MPLS сети -- существует необходимость в инженерах, имеющих профессиональные навыки для построения таких сетей.

2. Дороговизна как оборудования и построения сети, так и обслуживания этой сети.

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

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

Алгоритм дырявого ведра

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

Рис 2.8 Дырявое ведро с водой (а); дырявое ведро с пакетами (б) Курс лекций по информатике

Та же самая идея применима к пакетам, как показано на рис. 5.28, б. Принцип таков: каждый хост соединяется с сетью через интерфейс, содержащий дырявое ведро, то есть конечную внутреннюю очередь. Если пакет появляется в очереди, когда очередь полная, пакет игнорируется. Другими словами, если несколько процессов хоста пытаются послать пакеты, когда в очереди уже стоит максимально допустимое число пакетов, новый пакет игнорируется. Такой интерфейс может быть реализован как аппаратно, так и программно операционной систе- мой хоста. Он был предложен Тернером (Turner, 1986) и называется алгоритмом дырявого ведра. По сути это не что иное, как однолинейная система массового обслуживания с постоянным временем обслуживания.

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

Когда размер всех пакетов одинаков (например, в ячейках ATM), этот алгоритм может применяться, как описано ранее. Однако при использовании пакетов переменного размера часто бывает лучше ограничивать количество байтов, переданных в сеть за такт, нежели передавать один пакет за такт. Так, если правилом установлена передача 1024 байт за тактовый интервал, то за этот период могут быть переданы в сеть либо один пакет размером 1024 байта, либо два пакета по 512 байт, либо четыре пакета по 256 байт и т. д. Если оставшееся количество байт меньше размера следующего пакета, следующий пакет должен ждать начала следующего такта.

Реализация исходного алгоритма дырявого ведра проста. Дырявое ведро состоит из конечной очереди. Когда прибывает пакет и в очереди есть место, пакет добавляется к очереди, в противном случае пакет игнорируется. Если очередь не пуста, то в течение каждого тактового интервала в сеть передается по одному пакету.

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

Заключение

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

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

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

Взвешанная справедливая очередь: Суть его состоит в том, что маршрутизаторы организуют отдельные очереди для каждой исходящей линии, по одной для каждого потока. Как только линия освобождается, маршрутизатор начинает циклически сканировать очереди, выбирая первый пакет следующей очереди. Таким образом, если за данную исходящую линию борются n хостов, то каждый из них имеет возможность отправить свой пакет, пропустив n - 1 чужих пакетов. Агрессивному хосту не поможет то, что в его очереди стоит больше пакетов, чем у остальных.

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

Список использованной литературы

1. Таненбаум Э. «Компьютерные сети», Питер, 2002г.

2. Советов Б.Я. «Моделирование систем», Москва, 2001г.

3. Нанс Бэрри «Компьютерные сети», Москва, 1996г.

4. «Microsoft Visual Basic-06», Питер, 2002г.

5. Интернет ресурсы.

маршрутизация алгоритм перегрузка трафик

Приложение

Листинг программы №1

Option Explicit

Public N As Integer

Dim m(5) As Integer

Private Sub Command1_Click()

Dim i As Integer

Dim kol As Integer

N = 0

kol = 0

For i = 1 To 5

m(i) = Text1(i - 1).Text

Text1(i - 1).Enabled = False

Text2(i - 1).Text = 0

kol = kol + m(i)

Next i

Do While kol > 0

For i = 1 To 5

If m(i) <> 0 Then

m(i) = m(i) - 1

N = N + 1

Text2(i - 1).Text = N

kol = kol - 1

End If

Next i

Loop

End Sub

Private Sub Command2_Click()

Dim i As Integer

For i = 0 To 4

Text2(i).Text = 0

Text1(i).Enabled = True

Next i

End Sub

Private Sub Command3_Click()

Меню.Show

Unload Me

End Sub

Private Sub Frame2_DragDrop(Source As Control, X As Single, Y As Single)

End Sub

№2

strat proc far

mov cs:request, bx

mov cs:request+2, es ret strat endp

intr proc far ; подпpогpамма пpеpывания

push ax

push bx

push cx

push dx

push di

push si

push bp

push ds

push es

pushf

push cs

pop ds

les di, dword ptr request

; в ES:DI

mov bl, es:[di+cmd_fld]

cmp bl, num_cmd

jle bc_ok ; ДА --> bc_ok

mov ax, 8003h

jmp short intr_end

bc_ok: shl bl, 1

xor bh, bh

call [fkt_tab+bx] les di, dword ptr request

; в ES:DI

intr_end:push cs

pop ds

les di, dword ptr request

or ax, 0100h

mov es:[di+status], ax

popf pop

pop ds

pop bp

pop si

pop di

pop dx

pop cx

pop bx

pop ax

ret ; возвpат в вызывающую подпpогpамму

intr endp

init proc near ; подпpогpамма инициализации

mov dx, 3f6h

xor al, al

out dx, al ;Turn off IRQ 14

call waithd ; sit back and relax…

mov dx, 1f6h ;SDH register

mov al, 0a0h ;Drive descriptor

out dx, al

mov dx, 1f2h ;Sector count

mov al, 1

out dx, al

mov dx, 1f3h ;Sector number

mov al, 1

out dx, al

mov dx, 1f4h ;low cyl

mov al, 0

out dx, al

mov dx, 1f5h ;high cyl

mov al, 0

out dx, al ;New generation choose zero cyl.

mov dx, 1f6h ;1^st head

mov al, 1

out dx, al

mov dx, 1f7h ;Status(Command) register

mov al, 20h ;Read Sector

out dx, al

gword: mov dx, 1f7h ; Wait for data

in al, dx

test al, 8 ; 8^th bit=1 - устр-во занято вып-м команды

jz gword

mov cx, 256

mov si, offset mbr

mov dx, 1f0h ;Get data

gloop: in ax, dx

mov [si], ax

add si,2

write proc near

mov bp, 30h

jmp short move

write endp

read proc near

mov bp, 20h

read endp

move proc near

mov bx, es:[di+num_rqst]

fild dword ptr es:[di+sector]

fld1

faddp st(1), st(0) ;sect+1

fistp fsec

les di, es:[di+b_adr]

move_1:

fild fsec ;load the number of the first sector to st(0)

fild n63 ;load count of the phisycal sectors to st(0)

fxch ;you understand what I mean, that's right?

Fprem ;st(0) mod st(1)

fxch

fcomp

fistp n ;save number of the phisycal sector

mov al, byte ptr n

mov sect, al

fild fsec ;вычисляем головку

fisub n

fidiv n63

fist temp

fild n255

fxch

fprem

fxch

fcomp

fistp n ;save number of head

mov al, byte ptr n

mov head, al

fild temp ; вычисляем цилиндр

fisub n

fidiv n255

fistp n

mov ax, word ptr n

dec ax

mov cyl, ax

h_ok: mov dx, 3f6h ; Turn off IRQ14

xor al, al

out dx, al

call waithd ; sit back and relax…

mov dx, 1f6h ;SDH Register

mov al, 0a0h

out dx, al

mov dx, 1f2h ;Sector count

mov al, 1

out dx, al

mov dx, 1f3h ;Sector number

mov al, sect;1

out dx, al

mov dx, 1f4h ;Cyl. low

mov al, byte ptr cyl;0

out dx, al

mov dx, 1f5h ;Cyl. high

mov al, byte ptr cyl+1;0

out dx, al

mov dx, 1f6h ;SDH register

mov al, head ;1

out dx, al

mov dx, 1f7h ;Status(command) register

mov ax, bp ;20h

out dx, al

mword: mov dx, 1f7h ;wait for data

in al, dx

test al, 8 ; 8^th bit=1 - устр-во занято вып-м команды

jz mword

mov cx, 256

mov dx, 1f0h

mloop: cmp bp, 20h ;Read or Write?

jne wr

in ax, dx

mov es:[di], ax

jmp short nx

wr: mov ax,es:[di]

out dx, ax

nx: add di, 2

loop mloop

call waithd ;ждем-с

mov dx, 3f6h ;Turn on IRQ14

mov al, 2

out dx, al

dec bx

cmp bx, 0

je move_e ;if equal, goto end

fild fsec

fld1

faddp st(1), st(0)

fistp fsec

jmp move_1

move_e: xor ax, ax ; все отлично

mov di, si

ret ; возвpат в вызывающую пpогpамму

move endp

waithd: mov dx, 1f7h

in al, dx

test al, 128 ;128=01000000b, it means that device is ready for R/W

jnz waithd

ret

diskdrv equ $

initm db "Your disk installed and ready to use"

im_ger db "?"

db ": $", 13, 10, 10

code ends

end

Листинг программы №3

Option Explicit

Dim vedro As Integer

Dim t, c As Integer

Private Sub Command1_Click()

Dim N, i, j As Integer

t = 0

Text2.Text = 0

Text3.Text = 0

Text4.Text = 0

vedro = 0

For j = 1 To Text5.Text

N = Int((Text6.Text - Text7.Text + 1) * Rnd() + Text7.Text)

For i = 1 To N

CountTime

Next i

Text2.Text = Text2.Text + 1

If vedro = Text8.Text Then

Text4.Text = Text4.Text + 1

End If

If vedro < Text8.Text Then

vedro = vedro + 1

End If

Next j

Text1.Text = t

End Sub

Public Sub CountTime()

Dim temp, i As Integer

t = t + 1

temp = t Mod Text9.Text

If temp = 0 Then

If vedro > 0 Then

vedro = vedro - 1

Text3.Text = Text3.Text + 1

End If

End If

End Sub

Private Sub Command2_Click()

Меню.Show

Unload Me

End Sub

Private Sub Command3_Click()

Меню.Show

Unload Me

End Sub

Private Sub Form_Load()

End Sub

Листинг программы №2

Option Explicit

Dim vedro As Integer

Dim t, c As Integer

Private Sub Command1_Click()

Dim N, i, j As Integer

t = 0

Text2.Text = 0

Text3.Text = 0

Text4.Text = 0

vedro = 0

For j = 1 To Text5.Text

N = Int((Text6.Text - Text7.Text + 1) * Rnd() + Text7.Text)

For i = 1 To N

CountTime

Next i

Text2.Text = Text2.Text + 1

If vedro = Text8.Text Then

Text4.Text = Text4.Text + 1

End If

If vedro < Text8.Text Then

vedro = vedro + 1

End If

Next j

Text1.Text = t

End Sub

Public Sub CountTime()

Dim temp, i As Integer

t = t + 1

temp = t Mod Text9.Text

If temp = 0 Then

If vedro > 0 Then

vedro = vedro - 1

Text3.Text = Text3.Text + 1

End If

End If

End Sub

Private Sub Command2_Click()

Меню.Show

Unload Me

End Sub

Private Sub Command3_Click()

Меню.Show

Unload Me

End Sub

Private Sub Form_Load()

End Sub

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