Apa itu masalah hitung-hingga-tak-terhingga?

Ini adalah patologi vektor jarak di mana, setelah tautan gagal, router secara perlahan meningkatkan perkiraan jarak mereka ke tujuan yang tidak dapat dijangkau dengan bertukar informasi usang, secara keliru percaya bahwa jalur masih ada melalui satu sama lain. Mitigasi termasuk split horizon, poisoned reverse, dan membatasi jarak maksimum.

Mengapa status tautan dan vektor jarak keduanya digunakan?

Keduanya cocok untuk cakupan yang berbeda. Protokol status tautan seperti OSPF memberikan konvergensi yang cepat dan bebas loop dalam satu domain administratif di mana berbagi topologi penuh dapat diterima. Pendekatan vektor jarak dan vektor jalur berskala lebih baik dan mengungkapkan detail internal yang lebih sedikit di seluruh domain, itulah sebabnya BGP menggunakan desain vektor jalur antar jaringan.

Algoritma Perutean

Algoritma perutean menghitung jalur yang dilalui paket melalui jaringan, biasanya dengan menemukan rute berbiaya terendah melalui grafik router dan tautan menggunakan tampilan status tautan global atau komputasi vektor jarak terdistribusi, tetangga-per-tetangga.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Algoritma perutean adalah prosedur yang menentukan jalur berbiaya terendah (atau yang lebih disukai) melalui jaringan yang dimodelkan sebagai grafik berbobot, menghasilkan keputusan penerusan yang digunakan router untuk memindahkan paket menuju tujuannya.

Scope

Topik ini mencakup algoritma yang mengisi tabel penerusan: model grafik jaringan dengan biaya tautan; perutean status tautan menggunakan algoritma jalur terpendek Dijkstra dengan topologi yang dibagikan secara global; perutean vektor jarak menggunakan komputasi Bellman-Ford terdistribusi dengan pertukaran tetangga; perilaku konvergensi dan patologinya seperti masalah hitung-hingga-tak-terhingga; dan perutean hierarkis untuk skalabilitas. Ini memperlakukan algoritma secara abstrak, menyerahkan protokol konkret (OSPF, RIP, BGP) dan organisasi intra/antar-domainnya ke topik protokol perutean.

Core questions

Bagaimana jaringan dimodelkan sebagai grafik berbobot untuk perutean?
Bagaimana algoritma status tautan menghitung jalur terpendek dari tampilan topologi penuh?
Bagaimana algoritma vektor jarak berkonvergensi hanya dengan menggunakan pertukaran tetangga?
Apa saja masalah konvergensi dan stabilitas, seperti hitung-hingga-tak-terhingga, dan bagaimana cara mengatasinya?
Mengapa perutean dibuat hierarkis, dan bagaimana hal itu memengaruhi optimalitas jalur?

Key concepts

grafik jaringan berbobot
jalur berbiaya terendah
perutean status tautan
algoritma Dijkstra
perutean vektor jarak
persamaan Bellman-Ford
masalah hitung-hingga-tak-terhingga
split horizon dan poisoned reverse
perutean hierarkis

Key theories

Perutean status tautan (Dijkstra): Setiap router membanjiri biaya tautannya sehingga semua router berbagi topologi penuh, kemudian secara independen menjalankan algoritma Dijkstra untuk menghitung jalur terpendek; ini berkonvergensi dengan cepat dan dapat diprediksi tetapi memerlukan pertukaran informasi global.
Perutean vektor jarak (Bellman-Ford): Router bertukar perkiraan biaya terendah saat ini ke setiap tujuan dengan tetangga mereka dan memperbarui melalui persamaan Bellman-Ford; komputasi terdistribusi dan hanya menggunakan informasi lokal tetapi dapat berkonvergensi lambat dan menderita hitung-hingga-tak-terhingga.
Perutean hierarkis: Karena perutean datar tidak berskala ke seluruh Internet, router dikelompokkan ke dalam wilayah (sistem otonom) dengan perutean ditangani secara lokal di dalam setiap wilayah dan diringkas di antara mereka, menukar beberapa optimalitas jalur untuk skalabilitas dan otonomi administratif.

Clinical relevance

Algoritma perutean menentukan seberapa efisien dan andal aliran lalu lintas: algoritma status tautan mendasari protokol interior seperti OSPF yang berkonvergensi cepat setelah kegagalan, sementara ide-ide vektor jarak muncul di RIP dan dalam pendekatan vektor jalur BGP. Memahami perilaku konvergensi mereka sangat penting untuk merancang jaringan yang stabil dan mendiagnosis loop perutean serta pemulihan yang lambat setelah kegagalan tautan atau router.

History

Algoritma jalur terpendek yang menjadi inti perutean sudah ada sebelum jaringan komputer: karya Bellman dan Ford tentang masalah perutean pada akhir 1950-an dan algoritma jalur terpendek Dijkstra tahun 1959. Seiring berkembangnya jaringan paket, ini diadaptasi menjadi perutean vektor jarak dan status tautan, dan struktur hierarkis ke dalam sistem otonom membuat perutean berskala ke Internet global.

Debates

Perutean status tautan versus vektor jarak: Perutean status tautan berkonvergensi cepat dan menghindari hitung-hingga-tak-terhingga tetapi mengharuskan setiap router untuk menyimpan topologi penuh dan melakukan lebih banyak komputasi, sementara vektor jarak lebih sederhana dan lebih lokal tetapi dapat berkonvergensi lambat dan membentuk loop transien; jaringan nyata menggabungkan kedua ide pada skala yang berbeda.

Key figures

Edsger W. Dijkstra
Richard Bellman
Lester Ford

Seminal works

dijkstra1959
bellman1958
kurose2021

Frequently asked questions

Apa itu masalah hitung-hingga-tak-terhingga?: Ini adalah patologi vektor jarak di mana, setelah tautan gagal, router secara perlahan meningkatkan perkiraan jarak mereka ke tujuan yang tidak dapat dijangkau dengan bertukar informasi usang, secara keliru percaya bahwa jalur masih ada melalui satu sama lain. Mitigasi termasuk split horizon, poisoned reverse, dan membatasi jarak maksimum.
Mengapa status tautan dan vektor jarak keduanya digunakan?: Keduanya cocok untuk cakupan yang berbeda. Protokol status tautan seperti OSPF memberikan konvergensi yang cepat dan bebas loop dalam satu domain administratif di mana berbagi topologi penuh dapat diterima. Pendekatan vektor jarak dan vektor jalur berskala lebih baik dan mengungkapkan detail internal yang lebih sedikit di seluruh domain, itulah sebabnya BGP menggunakan desain vektor jalur antar jaringan.