Distance Vector Routing Algorithm

• Algoritma vektor Jarak bersifat iteratif, asinkron, dan terdistribusi.
  • Terdistribusi: Didistribusikan dimana setiap node menerima informasi dari satu atau lebih tetangganya yang terhubung langsung, melakukan perhitungan dan kemudian mendistribusikan hasilnya kembali ke tetangganya.
  • Iteratif: Ini berulang karena prosesnya berlanjut hingga tidak ada lagi informasi yang tersedia untuk dipertukarkan antar tetangga.
  • Asynchronous: Tidak mengharuskan semua nodenya beroperasi dalam langkah kunci satu sama lain.
• Algoritma distance vector merupakan algoritma yang dinamis.
• Hal ini terutama digunakan di ARPANET, dan RIP.
• Setiap router memelihara tabel jarak yang dikenal sebagai Vector .

Tiga Kunci untuk memahami cara kerja Algoritma Routing Vektor Jarak:

• Pengetahuan tentang seluruh jaringan: Setiap router membagikan pengetahuannya ke seluruh jaringan. Router mengirimkan pengetahuan yang dikumpulkannya tentang jaringan ke tetangganya.
• Routing hanya ke tetangga: Router mengirimkan pengetahuannya tentang jaringan hanya ke router yang memiliki link langsung. Router mengirimkan apa pun yang dimilikinya tentang jaringan melalui port. Informasi tersebut diterima oleh router dan menggunakan informasi tersebut untuk memperbarui tabel routingnya sendiri.
• Berbagi informasi secara berkala: Dalam waktu 30 detik, router mengirimkan informasi ke router tetangga.

Algoritma Perutean Vektor Jarak

Misalkan dx ₍ y) adalah biaya jalur berbiaya terkecil dari node x ke node y. Biaya terkecil dihubungkan dengan persamaan Bellman-Ford,

d _x (y) = menit _v {c(x,v) + d _v (y)}

Dimana minv adalah persamaan yang diambil untuk semua x tetangga. Setelah menempuh perjalanan dari x ke v, jika kita mempertimbangkan jalur berbiaya terkecil dari v ke y, biaya jalurnya adalah c(x,v)+d _v (y). Biaya terkecil dari x ke y adalah biaya minimum c(x,v)+d _v (y) yang diambil alih semua tetangga.

Dengan algoritma Distance Vector Routing, node x berisi informasi routing berikut:

• Untuk setiap tetangga v, biaya c(x,v) adalah biaya jalur dari x ke tetangga langsung, v.
• Vektor jarak x, yaitu D _x = [ D _x (y) : y dalam N ], yang memuat biayanya ke semua tujuan, y, dalam N.
• Vektor jarak masing-masing tetangganya, yaitu D _v = [ D _v (y) : y in N ] untuk setiap tetangga v dari x.

Perutean vektor jarak adalah algoritma asinkron di mana node x mengirimkan salinan vektor jaraknya ke semua tetangganya. Ketika simpul x menerima vektor jarak baru dari salah satu vektor tetangganya, v, ia menyimpan vektor jarak dari v dan menggunakan persamaan Bellman-Ford untuk memperbarui vektor jaraknya sendiri. Persamaannya diberikan di bawah ini:

d _x (y) = min _v { c(x,v) + d _v (y)} untuk setiap simpul y di N

Node x telah memperbarui tabel vektor jaraknya sendiri dengan menggunakan persamaan di atas dan mengirimkan tabel yang telah diperbarui tersebut ke semua tetangganya sehingga mereka dapat memperbarui vektor jaraknya sendiri.

Algoritma

Pada setiap simpul x, Inisialisasi untuk semua tujuan y di N: D _x (y) = c(x,y) // Jika y bukan tetangga maka c(x,y) = ∞ untuk setiap tetangga w D _w (y) = ? untuk semua tujuan y di N. untuk setiap tetangga w kirim vektor jarak D _x = [ D _x (y): y di N ] ke w loop tunggu (sampai saya menerima vektor jarak apa pun dari beberapa tetangga w) untuk setiap y di N: D _x (y) = minv{c(x,v)+D _v (y)} Jika D _x (y) diubah untuk sembarang tujuan y Kirim vektor jarak D _x = [ D _x (y) : y di N ] kepada semua tetangga selamanya

Mari kita pahami melalui contoh:

Berbagi informasi

• Pada gambar di atas, setiap cloud mewakili jaringan, dan angka di dalam cloud mewakili ID jaringan.
• Semua LAN dihubungkan oleh router, dan semuanya direpresentasikan dalam kotak berlabel A, B, C, D, E, F.
• Algoritma routing distance vector menyederhanakan proses routing dengan mengasumsikan biaya setiap link adalah satu unit. Oleh karena itu, efisiensi penularan dapat diukur dari jumlah jalur untuk mencapai tujuan.
• Dalam perutean vektor jarak, biaya didasarkan pada jumlah hop.

Pada gambar di atas, kita mengamati bahwa router mengirimkan pengetahuan ke tetangga terdekat. Tetangga menambahkan pengetahuan ini ke pengetahuan mereka sendiri dan mengirimkan tabel yang diperbarui ke tetangga mereka. Dengan cara ini, router mendapatkan informasinya sendiri ditambah informasi baru tentang tetangganya.

Tabel Perutean

Dua proses terjadi:

• Membuat Tabel
• Memperbarui Tabel

Membuat Tabel

Awalnya, tabel routing dibuat untuk setiap router yang berisi setidaknya tiga jenis informasi seperti ID Jaringan, biaya dan hop berikutnya.

• NET ID: ID Jaringan menentukan tujuan akhir paket.
• Biaya: Biaya adalah jumlah hop yang harus ditempuh paket untuk sampai ke sana.
• Hop berikutnya: Ini adalah router tujuan pengiriman paket.

• Pada gambar di atas, tabel routing asli ditampilkan dari semua router. Dalam tabel routing, kolom pertama mewakili ID jaringan, kolom kedua mewakili biaya link, dan kolom ketiga kosong.
• Tabel perutean ini dikirim ke semua tetangga.

Misalnya:

1. A mengirimkan tabel routingnya ke B, F & E.  
2. B mengirimkan tabel routingnya ke A & C.  
3. C mengirimkan tabel routingnya ke B&D.  
4. D mengirimkan tabel routingnya ke E & C.  
5. E mengirimkan tabel routingnya ke A & D.  
6. F mengirimkan tabel routingnya ke A.  

Memperbarui Tabel

• Ketika A menerima tabel routing dari B, maka A menggunakan informasi tersebut untuk memperbarui tabel.
• Tabel routing B menunjukkan bagaimana paket dapat berpindah ke jaringan 1 dan 4.
• B adalah tetangga dari router A, paket dari A ke B dapat dijangkau dalam satu hop. Jadi, 1 ditambahkan ke semua biaya yang diberikan dalam tabel B dan jumlah tersebut akan menjadi biaya untuk mencapai jaringan tertentu.

Setelah penyesuaian, A kemudian menggabungkan tabel ini dengan tabelnya sendiri untuk membuat tabel gabungan.

Tabel gabungan mungkin berisi beberapa data duplikat. Pada gambar di atas, tabel gabungan router A berisi data duplikat, sehingga hanya menyimpan data yang memiliki biaya terendah. Misalnya, A dapat mengirim data ke jaringan 1 dengan dua cara. Yang pertama, yang tidak menggunakan router berikutnya, jadi biayanya satu hop. Yang kedua memerlukan dua lompatan (A ke B, lalu B ke Jaringan 1). Opsi pertama memiliki biaya paling rendah, oleh karena itu opsi ini dipertahankan dan opsi kedua dihilangkan.

• Proses pembuatan tabel routing berlanjut untuk semua router. Setiap router menerima informasi dari tetangganya, dan memperbarui tabel routing.

Tabel routing akhir dari semua router diberikan di bawah ini:

AGR//

Referensi : [1]