Ngaphambi kokuthi uqale ukufunda le ndatshana, sikucebisa ukuthi uzijwayeze ngokwezinto eziphathelene nokubalwa kwendlela ngokusho kweBellman - Ford algorithm.
I-algorithm yokuvuselela i-algorithm (ehlukile yokuvuselela i-algorithm -Daual) ingenye yama-algorithms amabili okuxoxwe lapha ekuqaleni ayehlose ukuqaliswa kwinethiwekhi esatshalaliswa. Ihlukile ngoba futhi isusa imininingwane ngempumelelo kanye ne-topology equkethwe ku-automata yokugcina ye-algorithm. Amanye ama-algorithms okuxoxwe lapha ashiya ukususwa kolwazi ngokubona kwe-protocol, futhi ungabheki lesi sici somsebenzi we-algorithm ngaphakathi kwe-algorithm uqobo.
Ngo-1993, kwasungulwa iBellman-Ford naseDijkstra njengama-algorithms asatshalaliswa ezinhlakeni eziningana zomzila. Isipiliyoni sitholwe ngenxa yalokhu kusetshenziswa kokuqala nokuhanjiswa kwaholela ku- "Wave Yesibili" yocwaningo kanye nokuboniswa ngenkinga yokuzithandela kumanethiwekhi okushintsha kwenethiwekhi, okuholele ekubonakaleni kwe-vector yenethiwekhi kanye nombaxaka.
Njengoba kudalwe kabili njenge-algorithm esatshalaliswa, kungcono ukuchaza umsebenzi wakhe kunethiwekhi. Ngale njongo, izibalo 8 no-9 ziyasetshenziswa. Ukuchaza okubili, lesi sibonelo kuzolandelwa ekusakazweni kwezindawo ezintathu, bese kuthi izinguquko zicutshungulwa endaweni yokutholakala kwazo zonke izinto ezifanayo. Esibonelweni sokuqala, leli cala lizocatshangelwa lapho kunendlela ehlukile, kepha alukho umakhelwane ophansi, owesibili uzocubungula icala lapho kukhona enye indlela nomakhelwane ophansi.
Kumfanekiso 8, ☆ndela d kusuka endaweni yokubuka a:
- A funda izindlela ezimbili ku-D:
- A ngeke aqaphele indlela nge-B, ngoba B isebenzisa i-ASPOROR yayo:
- I-a iqhathanisa izindlela ezitholakalayo bese ikhetha indlela emfushane kakhulu ngaphandle kwezingisi:
- Ihlola izindlela ezisele ukuthola ukuthi ngabe kukhona omunye womakhelwane ophansi:
Ukwazi lokhu ngoba u-C umemezela indlela eya e-D nge-metric yayo yendawo elingana no-3.
I-A igcina i-metric c etafuleni layo le-topology.
Ngenxa yalokho, kwazi inani lendawo ku-C kanye nenani lendawo ku-A.
- I-3 (kubiza ku-c) = 3 (izindleko ku-a), ngakho-ke le ndlela ingahle ibe yi-loop, ngakho-ke, c ayigculisi isimo sengozi. C ayibhalwa njengomakhelwane ophansi.
Omakhelwane ophansi ku-Dual babizwa ngokuthi abalandeli abangaba khona. Ake sithi isiteshi [a, H] asisebenzi. I-Dual ayithembeli ekuvuseleleni ngezikhathi ezithile, ngakho-ke angeke nje alinde esinye isibuyekezo ngolwazi oluthembekile. Esikhundleni salokho, kufanele alandele ngentshiseko enye indlela. Ngakho-ke, le yinqubo yokubona yokubona kwendlela ehlukile. Uma isiteshi [a, H] asisebenzi, sicabanga kuphela D:
- Isheke itafula lakho lendawo labalandela amathuba (omakhelwane abaphansi).
- Akunawo alande abaphumelelayo, ngakho-ke kumele bathole enye indlela ngaphandle kwama-loops kuye ku-D (uma ikhona).
- A ithumela isicelo kumakhelwane ngamunye ukuthola ukuthi ngabe kukhona enye indlela ngaphandle kwama-loops ku-D.
- Ku-C:
- Ku-B:
- Ukuthola lezi zimpendulo:
Kumfanekiso 9, into (D) ihanjiswe nge-H ku-E. Lokhu kuzosetshenziswa esifundweni sesibili.
Kulesi sibonelo, kukhona ophumelelayo (umakhelwane ophansi).
Study d kusuka endaweni yokubuka a:
- A funda izindlela ezimbili ku-D:
- A ngeke aqaphele nganoma iyiphi indlela nge-B:
- I-a iqhathanisa izindlela ezitholakalayo bese ikhetha indlela emfushane kakhulu ngaphandle kwezingisi:
- Ihlola izindlela ezisele ukuthola ukuthi ngabe kukhona omunye womakhelwane ophansi:
Uma isiteshi [a, c] asisebenzi, ukumane ucabangele:
- Isheke itafula layo le-topology yendawo ukuze alandele.
- I-Enakhendiki engenzeka ikhona ngoH.
- Ukushintsha itafula layo lendawo ku-H njengendlela engcono kakhulu.
- A ithumele isibuyekezo komakhelwane bawo, ibona ukuthi izindleko zayo zokufeza d zishintshe kusuka ku-3 kuye ku-4.
Njengoba ukwazi ukubona, ukucubungula lapho kunomphumela ongenzeka, ngokushesha okukhulu futhi kube lula kunakunganakho. Kumanethiwekhi lapho iphrothokholi ye-Roucting yathunyelwa kusetshenziswa okubili (ikakhulukazi, i-EIGRP), enye yezinhloso zokuklama okuyinhloko izokhawulela ivolumu yanoma yiziphi izicelo ezikhiqizwayo lapho kungenawo umlandeli. Indawo yesicelo iyinto enqumayo enqumayo ukuthi i-algorithm ephindwe kabili iphothulwa ngokushesha futhi, ngakho-ke, inethiwekhi yasheshisa ngokushesha kangakanani.
Umdwebo 10 ukhombisa umshini oyisisekelo osuqediwe.
Izinto ezifakiwe emzileni ziba zimbi kakhulu (ukucekelwa phansi kwendlela) kungaba:
- Ukwehluleka kwesiteshi esixhunyiwe noma umakhelwane
- Ukuthola isibuyekezo sendlela ephethe i-metric ephakeme
- Ukuthola umbuzo ovela kuMphumelele Wamanje
- Ukuthola indlela entsha evela kumakhelwane
- Kwatholakala umakhelwane omusha, kanye nemizila engathola ngayo
- Ukuthola zonke izicelo ezithunyelwe komakhelwane lapho umzila ebansakatha
