Algoritma Routing dan Maksimum Flow

Algoritma Routing dan Maksimum Flow
Routing adalah proses pemilihan rute atau jalan pada suatu network pada saat pengiriman paket data. Proses ini terjadi pada setiap router di jaringan tersebut. Atau kalau dilihat pada router, routing adalah proses forwarding paket data dari interface input ke interface output suatu router dengan melihat alamat IP tujuan. Untuk melakukan forwarding tersebut maka router membentuk suatu tabel routing yang memetakan suatu alamat IP ke interface tertentu. Tabel routing umumnya berisi alamat IP dan next hop routing. Artinya untuk mencapai alamat IP tertentu maka paket data tersebut diforwarding ke IP atau interface next hop.
Proses pengisian tabel routing dilakukan dengan menggunakan algoritam routing. Prinsip umum dari routing adalah bagaimana paket dapat sampai di tujuan dengan melewati lintasan terpendek dan utilisasi rendah. Banyak jenis algoritma routing yang dikembangkan untuk berbagai jenis kebutuhan. Beberapa macam algoritma routing adalah distance vector algorithm, link state algorithm dan path vector protocol.

a. Distance Vector Algorithm adalah algoritma routing dengan menggunakan algoritma Bellman Ford untuk memilih rute terbaik. Pada algoritm ini setiap router memiliki distance table yang berisi alamat router berikutnya (next hop) dan cost dari link ke router tersebut. Proses pengisian tabel ini dilakukan melalui proses updating secara periodik oleh router tetangga. Pemilihan rute terbaik dilakukan dengan cara memilih next hop yang memiliki cost paling kecil. Kelemahan protokol ini adalah menjadi tidak stabil jika ditemukan lebih dari satu cost paling kecil.

b. Link State Algorithm adalah algoritma routing dengan menggunakan algoritma Djikstra untuk mencari rute terbaik. Pada algoritma ini masing-maing router membangun topologi network dalam bentuk map/graph berdasarkan informasi yang dikirim oleh node-node lain. Dengan menggunakan map tersebut suatu rute dipilih berdasarkan algoritma Djikstra untuk mendapatkan path paling pendek. Kelemahan protokol ini adalah menyebabkan trafik yang besar pada jaringan untuk kebutuhan update informasi routing.

c. Path Vector Protocol adalah protokol yang dipakai sebagai inter domain routing yaitu routing antar domain yang berbeda. Hal ini berbeda dengan protokol sebelumnya yang hanya bisa dipakai pada domain yang sama. Prinsip kerjanya mirip dengan distance vector hanya saja informasi routing dipertukarkan antar speaker node, yaitu node yang mewakili masing-masing domain. Informasi yang dipertukarkan adalah path yang ada di dalam masing-masing domain, bukan cost seperti pada distance vector.
Pola routing ini akan menentukan aliran trafik yang mengalir pada link-link transmisi. Jika pola routing tidak optimal maka akan menghasilkan utilisasi yang tidak seimbang pada link-link sehingga aliran yang mengalir menjadi tidak optimal. Salah satu algoritma yang banyak dipakai untuk menghasilkan maksimum flow adalah algoritma Ford-Fulkerson. Pada algortima ini proses dimulai dengan pencarian flow augemented path (FAP) untuk suatu pasangan sumber-tujuan. Pada masing-masing FAP tersebut dialirkan trafik sampai tercapai maksimum flow pada masing-masing FAP tersebut. Jumlah semua trafik yang mengalir ke tujuan adalah maksimum flow yang bisa dibawa oleh network tersebut.