Երկակի դիֆուզիոն թարմացման ալգորիթմ

Նախքան այս հոդվածը կարդալը, մենք ձեզ խորհուրդ ենք տալիս ծանոթանալ ուղու հաշվարկի վերաբերյալ նյութի մասին, ըստ Bellman - Ford ալգորիթմի:

Դիֆուզիոն թարմացման ալգորիթմը (Diffusing Update Algorithm-Dual) երկու ալգորիթմներից մեկն է, որն ի սկզբանե նախատեսված էր բաշխված ցանցում իրականացման համար: Դրանով եզակի է նաեւ տեղեկատվությունը ալգորիթմի վերջնական ավտոմատներում պարունակվող հնարավորության եւ տեղաբանության մասին: Այստեղ քննարկված այլ ալգորիթմներ թողնում են տեղեկատվության հեռացումը Արձանագրության իրականացման հայեցողությամբ եւ չեն համարում Ալգորիթմի աշխատանքի այս կողմը:

1993 թ.-ին Bellman-Ford- ը եւ Dijkstra- ն իրականացվել են որպես բաշխված ալգորիթմներ մի քանի երթուղղման արձանագրություններում: Այս վաղ կիրառությունների եւ տեղակայման արդյունքում ձեռք բերված փորձը հանգեցրեց հետազոտության «երկրորդ ալիքի», ցանցի անջատիչ ցանցերում երթուղղման խնդրին, ինչը հանգեցրեց ճանապարհի վեկտորի եւ երկակի տեսքի:

Քանի որ երկակի ձեւը նախատեսված է որպես բաշխված ալգորիթմ, ավելի լավ է նկարագրել ցանցի վրա նրա աշխատանքը: Այդ նպատակով օգտագործվում են 8 եւ 9 թվեր: Կրկնակի բացատրելու համար այս օրինակը կհետեւի երեք ուղղությունների հոսքի մեջ, իսկ հետո փոփոխություններ են մշակվում նույն նպատակակետային կետերում: Առաջին օրինակում գործը կդիտարկվի, երբ կա այլընտրանքային ուղի, բայց ներքեւում չկա ներքեւի հարեւան, երկրորդը կքննարկի գործը, երբ կա այլընտրանքային ուղի եւ ներքեւի հարեւան:

Նկար 8-ում, ուսումնասիրեք D տեսանկյունից.

1. D- ն սովորում է D:

1. A- ն չի ճանաչի ճանապարհը B- ի միջոցով, քանի որ B- ն օգտագործում է որպես իր իրավահաջորդ.
2. Համեմատեք առկա ուղիները եւ ընտրում է ամենակարճ ճանապարհը առանց հանգույցների.
3. Ստուգում է մնացած ուղիները `որոշելու, թե դրանցից որեւէ մեկը ներքեւում է հարեւաններին.

Դա գիտի դա, քանի որ C- ն հայտարարում է իր տեղական մետրով `իր տեղական մետրով հավասար 3-ով:

Տեղի է պահպանում տեղական մետրը իր տեղաբանության աղյուսակում:

Հետեւաբար, գիտի տեղական արժեքը C եւ տեղական արժեքը Ա.

1. 3 (արժեքը C) = 3 (արժեքը ա), այնպես որ այս երթուղին կարող է հանգույց լինել, հետեւաբար, գ չի բավարարում իրագործելիության պայմանը: C- ը պիտակավորված չէ որպես ներքեւի հարեւանների:

Doual- ի ներքեւում գտնվող հարեւանները կոչվում են հնարավոր իրավահաջորդներ: Ենթադրենք, որ ալիքը [A, H] չի գործում: Երկակի չի ապավինում պարբերական թարմացումներին, ուստի չի կարող պարզապես սպասել մեկ այլ թարմացման, հուսալի տեղեկատվությամբ: Փոխարենը, պետք է ակտիվորեն հետեւի այլընտրանքային ուղու: Այսպիսով, սա այլընտրանքային ուղու տարածման հայտնաբերման գործընթաց է: Եթե ​​[A, H] ալիքը չի գործում, հաշվի առնելով միայն D:

1. Ստուգում է ձեր տեղական աղյուսակը հնարավոր իրավահաջորդների համար (հարեւանների ներքեւում):
2. Հնարավոր իրավահաջորդներ չկան, ուստի պետք է գտնել այլընտրանքային ուղի առանց հանգույցների D (եթե այն գոյություն ունի):
3. A- ն խնդրանք է ուղարկում յուրաքանչյուր հարեւանին որոշելու, թե արդյոք կա այլընտրանքային ուղի, առանց հանգույցների D- ին:
4. C- ում.
5. Բ.
6. Այս պատասխանները ստանում են.

Գծապատկեր 9-ում նպատակակետային (դ) կետը տեղափոխվել է H- ով E. Սա կօգտագործվի երկրորդ օրինակով:

Այս օրինակում կա հնարավոր իրավահաջորդ (ներքեւում հարեւան):

Ուսումնասիրեք D տեսանկյունից.

1. D- ն սովորում է D:
2. Ա-ն որեւէ կերպ չի ճանաչի B- ի միջոցով.
3. Համեմատեք առկա ուղիները եւ ընտրում է ամենակարճ ճանապարհը առանց հանգույցների.
4. Ստուգում է մնացած ուղիները `որոշելու, թե դրանցից որեւէ մեկը ներքեւում է հարեւաններին.

Եթե ​​[A, C] ալիքը չի գործում, պարզապես հաշվի առնելով.

1. Հնարավոր իրավահաջորդի համար ստուգում է տեղական տեղաբանության աղյուսակը:
2. Հնարավոր իրավահաջորդը գոյություն ունի Հ.
3. A- ն անջատում է իր տեղական սեղանը H- ում, ինչպես լավագույն միջոցը:
4. A- ն թարմացում է ուղարկում հարեւաններին, նշելով, որ իր նվաճման արժեքը փոխվել է 3-ից 4-ը:

Ինչպես տեսնում եք, վերամշակում, երբ կա հնարավոր իրավահաջորդ, շատ ավելի արագ եւ հեշտ է, քան առանց դրա: Network անցերում, որտեղ երթուղղման արձանագրությունը տեղակայված էր երկակի (մասնավորապես, EIGRP) օգտագործելով, դիզայնի հիմնական նպատակներից մեկը կսահմանափակի հնարավոր իրավահաջորդի բացակայության մեջ ստեղծված ցանկացած պահանջի ծավալը: Հայցի տարածքը հիմնական որոշիչ գործոնն է, թե ինչպես է կրկնակի ալգորիթմը արագ ավարտվում եւ, հետեւաբար, որքան արագ է ցանցը համընկնում:

Գծապատկեր 10-ը ցույց է տալիս հիմնական պատրաստի երկակի մեքենան:

Երթուղու մեջ ներառված բաները դառնում են ավելի վատ (երթուղու դեգրադացիա) կարող են լինել.

• Միացված ալիքի կամ հարեւանի ձախողում
• Ավելի բարձր մետրով երթուղու համար թարմացում ստանալը
• Ներկայիս իրավահաջորդի հարցում ստանալը
• Հարեւանից նոր երթուղի ստանալը
• Հայտնաբերվել է նոր հարեւան, ինչպես նաեւ այն երթուղիները, որոնց միջոցով կարող է ձեռք բերել
• Ստանալով հարեւաններին ուղարկված բոլոր պահանջները, երբ երթուղին վատանում է