про маршрутизацію в своїх таблицях. Раптово у нього зявляються необхідність в маршруті до вузла Н. Він розсилає широкомовним способом набори TTL на 1, 2, 3 и т. д. Скільки раундів потрібно на пошук шляху?
Рішення. Для визначення шляху до маршрутизатора H, маршрутизатору B потрібно 3 раунди. Це залежить від кількості проміжних маршрутизаторів.
В найпростішому варіанті алгоритму хорд при пошуку в рівно рангових мережах таблиці виказувачів не використовуються. Замість того проводиться лінійній пошук по кругу в обох напрямках. Чи може при цьому вузол передбачити в якому напрямку потрібно шукати? Відповідь аргументуйте.
КР.КС-94.00.00.000 ПЗ | Арк.
12
Зм. | Арк. | № докум | Підпис | Дата
Рішення. Вузол може порівняти свій номер в одноранговій мережі з шуканим. І якщо номер більший за свій то потрібно шукати (відсилати запити) за годинниковою стрілкою, тобто в сторону збільшення номерів. І навпаки якщо шуканий номер менше - потрібно проводити пошук проти годинникової стрілки, в сторону зменшення номерів вузлів.
Розгляньте круг, використаний в алгоритмі хорд і показаний на мал. 5.22. Припустимо, вузол 10 раптово підключається до мережі. Чи вплине це на таблицю виказувачів вузла 1, і якщо так, то як?
Рішення. Після входження вузла 10 в мережу він починає обмінюватися з сусідніми вузлами службовою інформацією, ті в свою чергу передають йому проміжні ключі діапазона між ними, а також передають пакети інформування нового вузла за годинниковою та проти годинникової стрілки. В одному з напрямів вузол 1 отримує службову інформацію і оновлює свою таблицю вказівників.
В якості можливого механізму боротьби з перегрузкою в підмережі, яка використовує віртуальні канали, маршрутизатор може утриматися від підтвердження отриманого пакету в наступних випадках:
1) він знає, що його остання передача по віртуальному каналу була одержана успішно; 2) у нього є вільний буфер. Для простоти припустимо, що маршрутизатори використовують протокол з очікуванням і що у кожного віртуального каналу є один буфер, виділений йому для кожного напряму трафіку.
Рішення. Передача пакету (даних або підтвердження) займає Т секунд. Шлях пакету проходить через п маршрутизаторів. З якою швидкістю пакети доставляються адресату? Передбачається, що помилки дуже рідкісні, а зв'язок між хостом і маршрутизатором майже не віднімає часу.
Передача пакета (даних або підтвердження) займає Т секунд. Шлях пакета проходить через п маршрутизаторів, отже виходить що швидкість буде рівна (пропускна здатність лінії звязку)/(n*T) і поділити на 2 так як для кожного пакету необхідне підтвердження про доставку.
КР.КС-94.00.00.000 ПЗ | Арк.
13
Зм. | Арк. | № докум | Підпис | Дата
Завдання 19. Напишіть програму, що моделює комп'ютерну мережу з дискретним часом. Перший пакет в черзі кожного маршрутизатора долає по
одній транзитній ділянці за інтервал часу. Число буферів кожного
маршрутизатора обмежено. Прибулий пакет, для якого немає вільного
місця, ігнорується і повторно не передається. Натомість використовується
крізний протокол з тайм-аутами і пакетами підтвердження, який, в кінці
кінців, викликає повторну передачу пакету маршрутизатором-джерелом.
Програма на мові С++
Код головного процесу.
//підключаємо бібліотеки
#include <vcl.h>
#pragma hdrstop
//підключаємо h – файли інших потоків
#include "Unit2.h"
#include "Unit3.h"
#include "Unit4.h"
#include "Unit1.h"
#pragma package(smart_init)
#pragma link "Excel_2K_SRVR"
#pragma resource "*.dfm"
//оголошуємо вказівники на 3 потоки, вони реалізують функції маршрутизаторів
P1 *potik1;
P2 *potik2;
P3 *potik3;
//оголошення форми проєкту
TForm1 *Form1;
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
КР.КС-94.00.00.000 ПЗ | Арк.
14
Зм. | Арк. | № докум | Підпис | Дата
//код кнопки запуску прогрими (роботи маршрутизаторів)
void __fastcall TForm1::Button1Click(TObject *Sender)
{
//виділяємо пам'ять для 3 потоків
//встановлюємо їм приорітет виконання
//та запускаємо їх на виконання
potik1 = new P1 (true);
potik1->Priority =3;
potik1->Resume();
potik2 = new P2 (true);
potik2->Priority =3;
potik2->Resume();
potik3 = new P3 (true);
potik3->Priority =3;
potik3->Resume();
}
//реалізовує елемент керування який дозволяє зупинити виконання процесів та здійснити вихід з програми
void __fastcall TForm1::Button2Click(TObject *Sender)
{
//зупиняємо процеси
potik1->Terminate();
potik2->Terminate();
potik3->Terminate();
//виходимо з програми та повертаємо код виходу 0 (нормальне завершення //програми)
exit(0);
}
КР.КС-94.00.00.000 ПЗ | Арк.
15
Зм. | Арк. | № докум | Підпис | Дата
Код маршрутизатора 1.
//підключаємо бібліотеки потрібні для роботи першого потоку
#include <vcl.h>
#pragma hdrstop
//підключаємо h – файли інших процесів
#include "Unit1.h"
#include "Unit2.h"
#pragma package(smart_init)
//оголошуємо змінні та прототипи функцій для роботи потоку
int owner=1,r;
int run();
// Important: Methods and properties of objects in VCL can only be
// used in a method called using Synchronize, for example:
//
Synchronize(UpdateCaption);
where UpdateCaption could look like:
void __fastcall P1::UpdateCaption()
{
Form1->Caption = "Updated in a thread";
}
__fastcall P1::P1(bool CreateSuspended)
: TThread(CreateSuspended)
{
}
void __fastcall P1::Execute()
{ n:
//викликаємо функцію randomize для випадкового вибору маршруту
randomize();
КР.КС-94.00.00.000 ПЗ | Арк.
16
Зм. | Арк. | № докум | Підпис | Дата
//викликаємо функцію яка визначає завантаженість маршрутизатора, для //наглядного відображення завантаженості
run();
//організовуємо цикл який керує роботою процесу, виконується до тих пір поки //користувач не призупинить роботу потоку.
while(!Form1->CheckBox1->Checked)
{
//вибираємо лінію для відправки
r=random(3);
//if(r==1){Form1->Label4->Caption=1; Form1->Label13->Caption=owner; }
//якщо маршрутизатор не занятий, вказуємо на завантаження пакету, інакше //очікуємо
if(r==2)
{x:
if(Form1->Label7->Caption==1)
{
Sleep(100);
if(Form1->Label4->Caption==1){goto v;}
else{goto x;}
}
else
{
Form1->Label7->Caption=1; Form1->Label16->Caption=owner;
}
}
if(r==3)
{ x1:
if(Form1->Label10->Caption==1)
КР.КС-94.00.00.000 ПЗ | Арк.
17
Зм. | Арк. | № докум | Підпис | Дата
{
Sleep(100);if(Form1->Label4->Caption==1){goto v;}
else{goto x1;}
}
else
{
Form1->Label10->Caption=1;Form1->Label19->Caption=owner;
}
}
//обробляємо буфер на локальному маршрутизаторі
v: if(Form1->Label4->Caption==1)
{ run();
if(Form1->Label5->Caption==1)
{ run();
if(Form1->Label6->Caption==1)
{ run();
Sleep(1000);Form1->Label6->Caption=0;/*robumo*/ run();
Sleep(1000);Form1->Label5->Caption=0; run();
Sleep(1000);Form1->Label4->Caption=0; run();
}
else{run();Form1->Label5->Caption=0;Form1->Label6->Caption=1;}
}
else{run();Form1->Label5->Caption=1;Form1->Label4->Caption=0;}//robumo peremi4ennje
}
}
//реалізовуємо керування потоком
while(Form1->CheckBox1->Checked)
{Sleep(100);}
goto n;
КР.КС-94.00.00.000 ПЗ | Арк.
18
Зм. | Арк. | № докум | Підпис | Дата
}
//визначаємо завантаженість маршрутизатора
run()
{int k=0;
if(Form1->Label4->Caption==1){k++;}
if(Form1->Label5->Caption==1){k++;}
if(Form1->Label6->Caption==1){k++;}
Form1->ProgressBar1->Position=k;//Sleep(300);
}
Код маршрутизатора 2.
//підключаємо бібліотеки потрібні для роботи другого потоку
#include <vcl.h>
#pragma hdrstop
//підключаємо h – файли інших процесів
#include "Unit1.h"
#include "Unit3.h"
#pragma package(smart_init)
//оголошуємо змінні та прототипи функцій для роботи потоку
int owner=2,r;
int run2();
// Important: Methods and properties of objects in VCL can only be
// used in a method called using Synchronize, for example:
Synchronize(UpdateCaption);
where UpdateCaption could look like:
void __fastcall P2::UpdateCaption()
{
Form1->Caption = "Updated in a thread";
}
КР.КС-94.00.00.000