ორმაგი დიფუზური განახლება ალგორითმი

ამ სტატიის წაკითხვის დაწყებამდე ჩვენ გირჩევთ, გაეცნოთ მასალას ბელმან-ფორდ ალგორითმის მიხედვით გზების გაანგარიშების შესახებ.

დიფუზური განახლების ალგორითმი (დიფუზური განახლების ალგორითმი - არის ერთ-ერთი ორი ალგორითმა, რომელიც განიხილება აქ თავდაპირველად განკუთვნილი დისტრიბუციის ქსელში განხორციელების მიზნით. ეს არის უნიკალური, რომ იგი ასევე შლის ინფორმაციას მიღწეულია და ტოპოლოგიის შესახებ, რომელიც შეიცავს ალგორითმის საბოლოო ავტომატებში. აქ განხილული სხვა ალგორითმები აქვეყნებს ინფორმაციის მოშორებას პროტოკოლის განხორციელების შეხედულებისამებრ და არ განიხილავენ ალგორითმის ფარგლებში ალგორითმის მუშაობის ამ ასპექტს.

1993 წლისთვის, Bellman-Ford და Dijkstra განხორციელდა, როგორც გავრცელდა ალგორითმები რამდენიმე მარშრუტიზაციის ოქმში. ამ ადრეული განხორციელების შედეგად მიღებული გამოცდილებისა და განლაგების შედეგად მიღებული გამოცდილება, რომელიც ჩატარდა კვლევის "მეორე ტალღის" კვლევისა და ქსელის გადართვის ქსელებში მარშრუტის პრობლემებზე, რამაც გამოიწვია გზა ვექტორული და ორმაგი.

მას შემდეგ, რაც ორმაგი განკუთვნილია, როგორც გავრცელებული ალგორითმი, უმჯობესია აღწერო მისი მუშაობა ქსელში. ამ მიზნით, მე -8 და მე -9 მოღვაწეები გამოიყენება. ორმაგი ასახსნელად, ეს მაგალითი სამი მიმართულებით აღინიშნება და შემდეგ ცვლილებები იმავე დანიშნულების ნივთების ხელმისაწვდომობას. პირველ რიგში, საქმე განიხილება, როდესაც ალტერნატიული გზაა, მაგრამ მეზობელი არ არის, მეორე კი განიხილავს იმას, როდესაც არსებობს ალტერნატიული გზა და მეზობელი.

ფიგურაში 8, შესწავლა D თვალსაზრისით:

1. გაიგებს ორი გზა D:

1. არ აღიარებს გზას B- ის მეშვეობით, რადგან B იყენებს როგორც მისი მემკვიდრე:
2. ადარებს ხელმისაწვდომი ბილიკები და ირჩევს უმოკლეს გზას მარყუჟების გარეშე:
3. ამოწმებს დარჩენილი ბილიკები, რათა დადგინდეს, თუ არსებობს რომელიმე მათგანი მეზობლებისგან:

ამის შესახებ იცის, რადგან C აცხადებს მარშრუტს, რათა მისი ადგილობრივი მეტრული ტოლია.

ინარჩუნებს ადგილობრივ მეტრულ მ- ს თავის ტოპოლოგიის მაგიდასთან.

აქედან გამომდინარე, A იცის ადგილობრივი ღირებულება C და ადგილობრივი ღირებულება ა.

1. 3 (C) = 3 (ღირებულება A), ასე რომ, ეს მარშრუტი შეიძლება იყოს მარყუჟის, ამიტომ, C არ აკმაყოფილებს მიზანშეწონილობის მდგომარეობას. C არ არის შეაფასა, როგორც მეზობლები.

Downstream მეზობლები ორმაგი ეწოდება შესაძლო მემკვიდრეებს. დავუშვათ, რომ არხი [A, H] არ მუშაობს. ორმაგი არ არის დამოკიდებული პერიოდული განახლებები, ასე რომ არ შეიძლება მხოლოდ დაველოდოთ სხვა განახლებას საიმედო ინფორმაცია. პირიქით, აქტიურად უნდა დაიცვას ალტერნატიული გზა. ამდენად, ეს არის ალტერნატიული გზების დიფუზური გამოვლენის პროცესი. თუ არხი [A, H] არ მუშაობს, მხოლოდ D:

1. ამოწმებს თქვენს ადგილობრივ მაგიდას შესაძლო მემკვიდრეებს (მეზობლები).
2. არ არსებობს შესაძლო მემკვიდრეები, ამიტომ უნდა მოიძებნოს ალტერნატიული გზა მარყუჟების გარეშე D (თუ ეს არსებობს).
3. აგზავნის თხოვნას თითოეულ მეზობელს, რათა დადგინდეს, თუ არსებობს ალტერნატიული გზა D.
4. C:
5. B:
6. იღებს პასუხებს:

ფიგურა 9-ში, დანიშნულება (D) პუნქტი H- თან გადაადგილდებოდა მეორე მაგალითზე.

ამ მაგალითში არსებობს შესაძლო მემკვიდრე (მეზობელი).

სწავლა D თვალსაზრისით A:

1. გაიგებს ორი გზა D:
2. არ აღიარებს რაიმე გზას B:
3. ადარებს ხელმისაწვდომი ბილიკები და ირჩევს უმოკლეს გზას მარყუჟების გარეშე:
4. ამოწმებს დარჩენილი ბილიკები, რათა დადგინდეს, თუ არსებობს რომელიმე მათგანი მეზობლებისგან:

თუ არხი [A, C] არ მუშაობს, უბრალოდ გათვალისწინებით:

1. ამოწმებს თავის მაგიდასთან ადგილობრივი ტოპოლოგიის შესაძლო მემკვიდრე.
2. შესაძლო მემკვიდრე არსებობს H.
3. ცვლის ადგილობრივ მაგიდას, როგორც საუკეთესო გზა.
4. აგზავნის განახლებას მეზობლებთან, აღნიშნა, რომ მიღწევის ღირებულება D შეიცვალა 3-დან 4-მდე.

როგორც ხედავთ, გადამუშავება, როდესაც არსებობს შესაძლო მემკვიდრე, უფრო სწრაფად და უფრო ადვილია, ვიდრე მის გარეშე. ქსელებში, სადაც მარშრუტიზაციის ოქმი განლაგებული იყო ორმაგი (კერძოდ, EIGRP) გამოყენებით, ერთ-ერთი მთავარი დიზაინის ამოცანა შეზღუდოს შესაძლო მემკვიდრის არარსებობისას წარმოქმნილი ნებისმიერი მოთხოვნის მოცულობას. მოთხოვნის არეალი არის ძირითადი განმსაზღვრელი ფაქტორი, თუ როგორ ორმაგი ალგორითმი სწრაფად დასრულდა და, შესაბამისად, რამდენად სწრაფად ხდება ქსელის კონვერტაცია.

ფიგურა 10 გვიჩვენებს ძირითადი დასრულებული ორმაგი მანქანა.

მარშრუტში შეტანილი რამ უარესია (მარშრუტის დეგრადაცია) შეიძლება იყოს:

• დაკავშირებული არხი ან მეზობელი
• განახლების განახლება მარშრუტისთვის უმაღლესი მეტრულით
• მიღების შეკითხვის მიმდინარე მემკვიდრე
• მეზობელიდან ახალი მარშრუტის მიღება
• ახალი მეზობელი იპოვეს, ისევე როგორც მარშრუტები, რომლითაც მას შეუძლია
• მიღების ყველა მოთხოვნა გაგზავნილი მეზობლები, როდესაც მარშრუტი გაუარესდება