Beranda > Routing TCP/IP Volume 1 > Protokol Routing Distance Vector

Protokol Routing Distance Vector

Dinamakan distance vector karena faktanya route-route di advertise sebagai sebuah vektor (jarak, arah) / (distance,direction), dimana jarak ditentukan oleh metric dan arah merupakan router next-hop. Misalnya, “Network A adalah network sejauh 5 hop dan dapat dicapai dari arah router X”. Setiap router mempelajari jalur-jalur dari sudut pandang router tetangganya dan kemudian meng-advertise jalur-jalur dari sudut pandangnya sendiri. Karena setiap router sangat tergantung pada informasi tetangganya, protokol routing distance vector sering disebut “routing by rumor“.

Beberapa protokol routing yang tergolong distance vector antara lain:

  • Routing Information Protocol (RIP) for IP
  • XNS RIP dari Xerox Networking System
  • IPX RIP dari Novell
  • Systems Internet Gateway Routing Protocol (IGRP) dan Enhanced Internet Gateway Routing Protocol (EIGRP) dari Cisco
  • DNA Phase IV dari DEC
  • Routing Table Maintenance Protocol (RTMP) dari AppleTalk

Ciri Khas Umum

Protokol routing distance vector biasanya menggunakan sebuah algoritma routing dimana setiap router secara periodik mengirimkan update routing kepada semua tetangga (neighbor) dengan cara mem-broadcast seluruh isi tabel routing.

Update Periodik

Update periodik berarti pada setiap rentang waktu tertentu, setiap router akan mengirimkan update routing. Rentang waktu ini berkisar antara 10 (RTMP dari AppleTalk) sampai 90 (IGRP dari Cisco) detik. Perlu diperhatikan disini, jika frekuensi update terlalu sering, traffik bisa jadi terlalu padat dan membebani CPU router, jika frekuensi terlalu jarang, convergence time jadi terlalu lama.

Neighbors

Tetangga (Neighbor) bagi sebuah router berarti router lain yang berada pada data link yang sama. Protokol routing distance vector mengirimkan updatenya kepada router-router neighbor-nya dan bergantung pada neighbor untuk mengirimkan informasi update kepada neighbor mereka yang lain. Karena alasan inilah, routing distance vector disebut menggunakan update hop-by-hop.

Update Broadcast

Ketika router pertama kali aktif dalam network, bagaimana cara router tersebut menemukan router-router yang lain dan memberitahukan keberadaan dirinya sendiri? Cara paling sederhana adalah dengan mengirimkan update dengan tujuan address broadcast (255.255.255.255). Router-router tetangga yang menggunakan protokol routing yang sama akan menerima paket broadcast ini dan dapat mulai bertukar informasi sebagai neighbor. Host-host dan mesin lain yang tidak berkepentingan akan mengabaikan paket tersebut.

Update Seluruh Tabel Routing

Kebanyakan protokol routing distance vector mengambil cara paling mudah untuk memberitahu neighbor semua yang diketahui dengan cara mem-broadcast keseluruhan isi tabel routing. Neighbor yang menerima update ini akan mengumpulkan informasi-informasi yang mereka butuhkan dan mengabaikan yang lainnya.

Routing by Rumor

Gambar berikut menunjukkan cara kerja algoritma distance vector. Dalam contoh ini, metric yang digunakan adalah hop count. Pada saat t0 Semua router baru saja aktif. Dengan melihat tabel routing pada baris paling atas, pada saat t0 informasi yang dimiliki oleh keempat router hanyalah network-network yang terhubung langsung (directly connected). Pada tabel hal ini diindikasikan dengan entri yang tidak memiliki router next-hop dan hop count nya sama dengan 0. Setiap router akan mem-broadcast informasi ini pada setiap link yang terhubung pada masing-masing router.

1-dvp-action3

Pada saat t1, update pertama telah diterima dan diproses oleh semua router. Kita lihat pada tabel routing A, update dari router B pada A mengatakan bahwa Router B dapat mencapai network 10.1.2.0 dan 10.1.3.0, keduanya sejauh 0 hop. Jika network sejauh 0 hop dari B, berarti network tersebut sejauh 1 hop dari A. Router A menaikkan nilai hop sejauh 1 satuan dan memasukkan dalam tabel routing. Router A sudah mengetahui network 10.1.2.0 dengan hop count 0, jadi Router A mengabaikan informasi network 10.1.2.0 dengan hop count 1 (lebih besar dari hop count yang sudah diketahui Router A).

Tetapi, network 10.1.3.0 merupakan informasi yang baru bagi A, jadi informasi tersebut akan dimasukkan kedalam tabel routingnya. Address source dari paket update tersebut adalah interface router B (10.1.2.2), dengan begitu, informasi yang dimasukkan akan memiliki address next-hop 10.1.2.2 dengan hop count sebesar 1.

Router-router yang lain juga melakukan operasi yang sama pada saat yang sama (t1).

Pada saat t2, periode update telah habis dan update-update berikutnya akan di broadcast. Router B mengirimkan tabel routing terbarunya, Router A menaikkan hop count network yang di advertise oleh Router B sebesar 1 satuan dan membandingkannya dengan tabel routingnya sendiri. 10.1.3.0 termasuk informasi yang sudah diketahui, dan hop countnya juga tidak berubah, jadi informasi tersebut diabaikan. Sedangkan network 10.1.4.0 merupakan informasi baru dan akan dimasukkan ke dalam tabel routing.

Network berada dalam status convergence pada saat t3, setiap router telah mengetahui setiap network, address router next-hop untuk setiap network, dan jarak dalam satuan hop setiap network.

Route Invalidation Timers

Kini network pada gambar diatas telah convergence secara sempurna, bagaimana cara network berada pada convergence lagi (re-convergence) jika terjadi perubahan topologi dalam network? Jika network 10.1.5.0 down, maka jawabnya adalah mudah, Router D pada update yang dijadwalkan akan memberikan tanda unreachable (tidak dapat dicapai) pada network tersebut dan mengirimkan informasi tersebut pada update.

Tetapi, bagaimana jika router D yang mengalami kegagalan (down)? Router A,B,dan C masih memiliki entri informasi network 10.1.5.0 pada tabel routing mereka; padahal informasi tersebut tidak valid lagi, tetapi tidak ada router yang menginformasikan hal ini. Router-router lain akan tetap memforward paket pada network yang tidak dapat dicapai (inreachable) tanpa mengetahui fakta yang terjadi.

Problem ini dapat ditangani dengan cara menyetting route invalidation timer untuk setiap entri dalam tabel routing. Misalnya, ketika C pertama kali mengenali network 10.1.5.0 dan memasukkan informasi network tersebut kedalam tabel routing, router C akan memberikan timer (pengukur waktu) untuk entri route tersebut. Setiap update rutin yang diterima dari Router D, C akan mengabaikan informasi network 10.1.5.0 yang telah dikenali dan pada saat yang sama mereset timer pada entri route tersebut.

Saat router D mengalami kegagalan, C tidak lagi mendapatkan update mengenai network 10.1.5.0. Timer akan terus berjalan dan akan berakhir, C akan menandai route sebagai unreachable (tidak dapat dijangkau) dan mengirimkan informasi tersebut pada update berikutnya.

Biasanya periode timer route berkisar antara 3 sampai 6 kali periode update. Sebuah router tidak akan menganggap sebuah entri route sebagai route yang tidak valid hanya karena tidak terdapat update dalam satu periode, karena dapat menimbulkan paket lost, atau delay dalam nework. Pada saat yang sama, jika period timer terlalu lama, proses re-convergence menjadi terlalu lama.

Split Horizon

Sebuah update route yang diberikan kembali kepada router dimana paket informasi didapatkan disebut reverse route.  Split horizon adalah salah satu mekanisme untuk mencegah terjadi reverse route diantar 2 router.

Selain alasan agar tidak membuang-buang sumber daya, ada alasan lain yang lebih penting untuk tidak mengirimkan informasi kembali kepada router yang memberikan informasi tersebut. Fungsi terpenting dari protokol routing dinamik adalah untuk mendeteksi dan mengatasi problem perubahan pada topologi network jika jalur terbaik pada network tidak lagi dapat dijangkau, protokol harus mencari jalur terbaik berikutnya.

Kita lihat kembali pada network yang telah convergence pada gambar diatas, dan misalkan network 10.1.5.0 mengalami kegagalan atau down. Router D akan mendeteksi hal ini, dan menandai network sebagai unreachable (tidak dapat dijangkau), dan mengirimkan informasi tersebut kepada Router C pada interval update berikutnya. Akan tetapi, sebelum D mengirimkan update, update dari C tiba lebih dulu, dan meng-klaim bahwa router D dapat menjangkau network 10.1.5.0 sejauh 1 hop. Router C akan menaikkan hop count dan memasukkan informasi tersebut kedalam tabel routing yang mengindikasikan bahwa network 10.1.5.0 dapat dijangkau melalui interface Router C 10.1.4.1 sejauh 2 hop.

Kini paket yang ditujukan untuk address 10.1.5.3 tiba pada router C, yang kemudian akan memforward paket tersebut pada router D. Router D , dari informasi didalam tabel routing akan memforward paket tersebut ke Route C, C kembali ke D, dan begitu seterusnya. Terjadilah routing loop.

Dengan mengimplementasikan split horizon kemungkinan terjadinya routing loop dapat dicegah. Ada 2 kategori split horizon: simple split horizon dan split horizon with poisoned reverse.

Atura pada simple split horizon adalah pada saat mengirimkan update keluar melalui suatu interface, jangan pernah menyertakan informasi-informasi network yang didapatkan dari update pada interface tersebut.

Router-router pada gambar dibawah ini mengimplementasikan simple split horizon. Router C mengirimkan update kepada Router D untuk network 10.1.1.0, 10.1.2.0, dan 10.1.3.0. Network 10.1.4.0 dan 10.1.5.0 tidak disertakan dalam update karena informasi network-network tersebut didapatkan dari Router D. Seperti itu juga, update pada Router B berisi 10.1.4.0 dan 10.1.5.0 dan tidak menyertakan network 10.1.1.0, 10.1.2.0, dan 10.1.3.0.

2-split-horizon3

Split horizon with poisoned reverse adalah modifikasi dari simple split horizon yang menyediakan informasi yang lebih positif.

Aturan pada split horizon with poisoned reverse adalah, ketika mengirim keluar update melalui suatu interface, maka setiap informasi network yang didapatkan dari interface tersebut ditandai sebagai unreachable.

Pada skenario network diatas, Router C akan tetap meng-advertise network 10.1.4.0 dan 10.1.5.0 kepada Router D tetapi network-network tersebut akan ditandai sebagai unreachable. Gambar berikut menunjukkan tabel routing yang dikirimkan dari C ke D dan B akan nampak mirip. Perhatikan bahwa route ditandai sebagai unreachable dengan mengeset metric menjadi inf (infinity/tidak terbatas), dengan kata lain, network berada pada jarak sejauh tak terbatas.

3-poison

Split horizon with poisoned reverse dianggap lebih aman dan lebih baik dari pada simple split horizon. Digunakan pendekatan “berita yang buruk lebih baik daripada tidak ada berita sama sekali“. Misalnya, Router B menerima informasi yang salah yang menyebabkan router D  menganggap subnet 10.1.1.0 dapat dijangkau via Router C. Simple split horizon tidak akan melakukan apa-apa untuk membetulkan kesalahpahaman ini, sedangkan  update dengan metode split horizon with poisoned reverse akan langsung menghentikan kemungkinan terjadinya loop. Untuk alasan ini, implementasi distance vector yang modern menggunakan split horizon with poisoned reverse. Efek sampingnya adalah paket update jadi lebih besar yang mungkin dapat memperparah masalah kepadatan traffik pada link.

Counting to Infinity

Split horizon akan dapat mencegah loop yang terjadi antar neighbor, tetapi tidak dapat menghentikan loop yang terjadi dalam network seperti pada gambar dibawah ini. Misalkan network 10.1.5.0 down. Router D mengirimkan update yang sesuai pada semua neighbornya, Router C (dengan tanda panah putus-putus) dan Router B (dengan tanda panah biasa). Router B akan menandai jalur via D sebagai unreachable, tetapi Router A meng-advertise jalur terbaik berikutnya untuk mencapai 10.1.5.0 yang adalah sejauh 3 hop. B memasukkan informasi ini pada tabel routing.

4-counting-infinitB kini memberitahukan D bahwa B memiliki jalur alternatif untuk network 10.1.5.0. D memasukkan informasi ini dan mengupdate C dengan mengatakan bahwa D memiliki jalur sejauh 4 hop. C memberi tahu pada A jalur 10.1.5.0 sejauh 5 hop. A memberitahu pada B network tersebut sejauh 6 hop.

B mengganti nilai hop count menjadi 7 dan mengupdate D, dan berputar terus seperti itu. Situasi ini disebut masalah counting-to-infinity karena hop count menuju 10.1.5.0 akan terus bertambah tak terbatas. Semua router mengimplementasikan split horizon tetapi tidak dapat membantu mengatasi masalah ini.

Sebuah cara mengurangi akibat dari counting to infinity adalah dengan mendefinisikan infinity (ketidakterbatasan) itu sendiri. Umumnya, protokol distance vector mendefinisikan infinity sebesar 16 hop. Seiring dengan update yang terus berputar antar router pada gambar diatas, hop count pada network 10.1.5.0 pada semua router akhirnya akan mencapai nilai 16. Pada saat itu, network akan dianggap unreachable.

Triggered Updates

Triggered update, atau disebut juga flash update, sebenarnya sangat sederhana: jika terdapat perubahan metric lebih baik atau lebih buruk, router akan langsung mengirimkan update tanpa menunggu periode update yang telah dijadwalkan. Re-convergence akan lebih cepat terjadi daripada jika semua router harus menunggu untuk mengirimkan update pada waktu yang telah dijadwalkan seperti biasanya, masalah counting-to-infinity juga dapat dikurangi, walaupun tidak bisa dihilangkan secara sempurna. Update regular masih bisa terjadi bersama dengan triggered update. Karena itu setelah menerima update yang benar dari triggered update, router masih dapat menerima informasi route yang salah dari router yang belum re-convergence.

Perbaikan lebih lanjut adalah dengan menyertakan update hanya dari network-network yang memicu adanya update tersebut. Teknik ini mengurangi waktu proses dan efek pada bandwidth network.

Holddown Timers

Jika hop count dari suatu network bertambah, router akan mengeset holddown timer untuk route network tersebut. Sampai timer tersebut berakhir, router tidak akan mau menerima update baru untuk route tersebut.

Efek sampingnya, waktu untuk re-convergence jadi lebih lama. Tidak seperti timer yang lain, holddown timer harus di set secara hati-hati. Jika periode holddown timer terlalu pendek, akan jadi tidak effektif, jika terlalu lama, akan mempengaruhi proses routing normal.

Asynchronous Updates

Gambar dibawah menunjukkan sekumpulan router yang terhubung pada backbone ethernet. Router-router tidak seharusnya membroadcast update-update mereka pada saat bersamaan, karena dengan begitu, paket-paket update akan berbenturan (collide) satu sama lain. Tetapi situasi seperti ini dapat saja terjadi ketika beberapa router berada pada satu network broadcast. Sistem delay yang berhubungan dengan proses update dalam router cenderung menyebabkan update timer menjadi sinkron satu sama lain. Karena beberapa router telah sinkron, maka collision akan mulai terjadi, lebih lanjut akan menambah sistem delay, dan pada akhirnya router-router yang berada pada satu network broadcast menjadi sinkron semua.

5-trigger-update

Asynchronous update dapat dilakukan dengan salah satu dari 2 cara berikut:

  • Update timer setiap router tidak bergantung pada proses routing dan karena itu tidak dipengaruhi oleh beban proses pada router.
  • Waktu random yang kecil akan ditambahkan pada setiap periode update router sebagai sebuah offset.

Jika router mengimplementasikan metode pertama, maka semua router yang berada pada network broadcast harus dihidupkan dalam waktu yang random. Me-reboot semua router pada waktu yang bersamaan, seperti ketika terjadi pemadaman listrik dalam satu daerah, dapat menyebabkan update timer kembali berada pada waktu yang sama.

Pada metode ke-2, menambahkan waktu random pada periode update menjadi effektif jika variable cukup besar dibandingkan dengan jumlah router yang berada pada network broadcast. Sally Floyd dan Van Jacobson telah melakukan perhitungan bahwa jika perandoman yang terlalu kecil akan dapat dikalahkan oleh network dengan jumlah router yang cukup banyak, dan karena itu agar dapat menjadi effektif, maka update timer harus berkisar antara 50% dari median periode udpate.

About these ads
  1. Belum ada komentar.
  1. April 15, 2009 pukul 12:10 pm

Berikan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Ikuti

Get every new post delivered to your Inbox.

%d blogger menyukai ini: