Новости
Научная статья. Аңдатпа
2 ноября 2017, 15:55

Автор статьи: специалист Ургенишбаев Камал Махамбетович

Алматинский университет энергетики и связи, г. Алматы, Казахстан

 

 

Бұл жұмыста маршрутизаторларда кеңінен қолданатын Дейкстр алгоритмінің қалай жұмыс жасайтын механизмі жариаланған. Осы жұмыс арқылы OSPF хаттамасының өнімділігі жарғарғы жолды қалай таңдай алатыны көрсетілген.

Дейкстр алгоритмін пайдаланып компьютерлік желідегі ең қысқа өнімділігі жоғарғы жолды есептеп табу

 

Үлкен глобальде желіде орналасқан компьютерлер бір-бірімен маршрутизаторлар арқылы қосылады. Ал маршрутизаторлар бір-бірімен әртүрлі түрлі жолдармен қосылуы мүмкін ол төменде мына суретте көрсетілген

 

1-    Сурет

 

Желідегі компьютерлдің бір-біріне ақпараттарды ең жоғарғы жылдамдықпен жібретін жолдарды табу үшін, біз компьютерлік желідегі өнімділігі жоғарғы метригін есептеп табуымыз қажет. Метрик деген сөзге анықтама берейін ол үшін граф сызып мынадай түсініктемелер еңгіземіз:

-       графтың төбелері болып маршрутизаторлар белгіленсін, олар суретте шеңбер түрінде көрсетілген, ал ішіндегі цифрлар олардың нөмірлері

-       маршрутизаторларды бір-бірімен қосатын жолдарды метрика деп атаймыз.

Жоғарғы суретті мысалы түрінде алып бірінші маршрутизатор мен алтыншы маршрутизатардың арасындағы өнімділігі жоғарғы жолды есептеп шығарайық. Оны шығару үшін біз алгоритм Дейкстрды  пайдаланамыз. Ол үшін бірінші маршрутизатор мен алтыншы маршрутизаторлар арасындағы метрикаларды қосып қосындысы минимальды жолды табуымыз қажет, сол жол ақпараттарды ең жоғарғы жылдамдықпен жеткізетін жол болып табылады. Дейкстр алгоритімін біздің есепте шығаруға беймдеу үшін келесі біріші кестені пайдаланымыз.

 

 

 

1-кесте. Жолдың өткізу қабілетін мен метрикаға сәйкестендіру

Метрика

Жолдың өткізу қабілеті

1

100 Мбит/с

2

50 Мбит/с

4

25 Мбит/с

8

12 Мбит/с

10

10 Мбит/с

20

5 Мбит/с

33

3 Мбит/с

25

4 Мбит/с

50

2 Мбит/с

100

1 Мбит/с

 

Дейкстр алгоритм жұмыс жасау қағидасы ол нақты алынған төбемен (түпдерек) басқа граф төбелер арасындағы тиімді жолдарды және олардың ең қысқа ұзындықты табу болады. Мысалы ретінде жоғарғы көрсетілген графты алайық. Графтың неше бір түрлері болады бір жаққа бағытталған, немесе екі жаққада бағыталған болып, оның себебі екі маршрутизатор арасындағы берілетін ақпарат бағытына байланысты. Біздің алған мысалда ақпараттар екі жаққада бағыталған сондықтан біз бағытталмаған графты аламыз.

Бұл графты біз матрица түрінде көрсетумізге болады

 

 

1

2

3

4

5

6

1

 

1

25

 

20

 

2

1

 

8

 

 

 

3

25

8

 

10

4

 

4

 

 

10

 

10

25

5

20

 

 

4

10

33

6

 

 

 

25

33

 

 

Түпдерек төбе ретінде екінші төбені алайық. Бұл дегеніміз 2 төбеден 1,3,4,5,6 төбелерге ең қысқа маршрутты табуымыз қажет деген сөз.

Бұл алгаритм қадамдап барлық төбелерді теріп оларға белгілерді тағайындайды, ол белгілер сол түпдерек төбеден нақты төбелерге дейінгі ең қысқа жол болып табылады.

Мысалы ретінде осы алгоритмды алайық.

2-ші төбеге 0 меткісін тағайындаймыз себебі ол төбе түпдерек болғандықтан. Қалған төбелерге шексіз белгісін тағайындаймыз.

 

 

Осы түпдерек төбеден басқа төбелерге делдалсыз баратын төбені таңдаймыз. Олар сурет бойынша 1 және 3 болып табылады. Оларың белгілері шексізден басқа белгілерге өзгереді. Оны былай есептейіз 0 қосылған сол төбелерге баратын метрика. Ол келесі суретте көрсетілген.

0+1=1

0+8=8

 

Әр бір қарастырылған төбелерге белгі цифр қойамыз олар меткі қосындыларының алдынағы меткі қосындыларынан кем болса мысалы олар  былай есептеледі.

2-ші төбемен 5-ші төбе

1-ші вариант 2-1-5  1+20=21

2-ші вариант 2-3-4   8+4=12

3-ші вариант 2-3-4-5 8+10+10=28

4- ші вариант 2-1-3-5 1+25+4=30

 

Осы 4 варианттың ең қосындысы азы ол 2-ші вариант Дейкстр алгоритмы бойынша осыны таңдап аламыз. Сіз ойлап қаларсыз көзге көрініп тұр ғой оның бәрін есептеп қажеті не деп, бірақ бұны процессор есептейді, маршрутизатордың ішінде тұрған оны бағдарлама тілінде түсіндіру қажет, Дейкстр алгоритімінің маңызы осында. Процессор көзді ашып жұмғанша секундтың мыңнан бір бөлігінде қуатына байланысты бәрін қосып соның ішіндегі қосындысы азды тауып береді.

2-ші төбемен 4-ші төбе

1-ші вариант 2-3-4        8+4=18

2-ші вариант 2-1-3-4     1+25+10=36

3-ші вариант 2-1-5-4     1+20+10=31

4-ші вариант 2-3-5-4     8+4+10=22

5- ші вариант 2-1-3-5-4 1+25+4+10=40

 

2-ші төбемен 6-ші төбе

1-ші вариант 2-3-5-6     8+4+33=45

2-ші вариант 2-1-5-6     1+20+33=54

3-ші вариант 2-3-4-6     8+10+25=43

 

Қалған вариантарды қарастырмайақ қойаын оны процессор есптеп жатар.

 

Есептелген төбелердің Дейкстр алгоритмы бойынша ең төменгі метрикасын алсақ онда ол былай болады:

2 төбе түпдерек теп алсақ шарт бойынша онда

2-1 төбе метрикасы 1 тең

2-3 төбе метрикасы 8 тең

2-5 төбе метрикасы 12 тең

2-4 төбе метрикасы 18 тең

2-6 төбе метрикасы 43 тең

 

Енді оны суретте көрсетейік

 

Енді екінші маршрутизатор мен алтыншы маршрутизатор арасындағы өткізу қабілетін есептеп шығарайық ол үшін біз метриканы кесте бойынша керісінше өктізу қабілетіне аударамыз.

2-ші мен 3-ші маршрутизатор метрика 8-ге тең өткізу қабілеті 12 Мбит/с

3-ші мен 4-ші маршрутизатор метрика 10-ға тең өткізу қабілеті 10 Мбит/с

4-ші мен 6-шы маршрутизатор метрика 25-ке тең өткізу қабілеті 4Мбит/с

Жалпы өткізу қабілетін шығару үшін екі әдісті пайдалануға болады бірінші әдіс ол орташа арифметикалық мәнді табу

С=(12+10+4)/3=8.6 Мбит/с

Былай жасауға болмайды себебі оны үйдегі қазақтелеком берген интернет сияқты есептесек қазақтелеком интернеті 2 Мбит/с оны төменгі суретте көрсетейін

Бізге берген интернетің жылдамығы (100+2)/2=51 Мбит/с тең емес, ол 2 Мбит/с болып қала береді сондықтан.

Дейкстр алгоритмі OSPF (Бірінші қысқа жолды табу) хаттамасында пайдаланылады. Біз жоғарыда статикалық түрдегі маршрутизатордың метрикасын алып есептеп шығардық. Практика жүзінде ол метрикалар минут сайын өзгеріп отырады.

Қортынды:

1.     Біз Дейкстр алгоритмі бойынша ең төменгі метриканы табамыз

2.     Дейкстра алгортимі арқылы формализация жасап кез келген бағдарлама тіліне аудара аламыз.

3.     Жалпы өткізу қабілетін тапқанда орташа арифметикалық мәнді табу әдісін қолдануға болмайды.

 

Пайдаланылған әдибеттер

 

1.     Компьютерные сети 2009г Олифер

2.     Компьютерные сети 2012г Таненбаум

 

 

 

ISSN 1560-1749 «Қазақстан жоғары мектебі» 3/2017ж 285 бетте жарияланған.