1. ALGORITMA
DIJKSTRA
1.1.
Pengertian Algoritma Dijkstra
Algoritma Dijkstra, dinamakan
sesuai dengan nama penemunya, seorang ilmuwan komputer berkebangsaan Belanda
yang bernama Edsger Dijkstra, adalah algoritma yang digunakan untuk
mencari lintasan terpendek pada sebuah graf berarah (directed graph)
dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.
Misalnya,
bila vertices dari sebuah graf melambangkan kota-kota dan
bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka
algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua
kota. Input algoritma ini
adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan
sebuah sumber vertex s dalam G dan V adalah
himpunan semua vertices dalam graph G.
1.2. Cara
Kerja Algoritma Dijkstra
Cara kerja
algoritma Dijkstra memakai stategi greedy, dimana pada setiap langkah
dipilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang
sudah terpilih dengan simpul lain yang belum terpilih.Misalkan, sebuah simpul
sumber s di sebuah jaringan, ingin memperoleh jarak yang tersingkat dan
termurah ke simpul lainnya yang ada dijaringan tersebut, misalnya ke simpul i.
Label jarak : d(l) menunjukkan jarak antara simpul s dan simpul i. Setiap langkah
dalam pencarian jalan tersebut ("antara'), simpul-simpul ini kelompokkan
kedalam dua jenis simpul, yaitu .. simpul dengan label jarak permanen dan
simpul dengan label jarak sementara. Label jarak permanen merupakan jarak
terdekat dari simpul s ke simpul i. Label jarak sementara merupakan batas atas
jarak s ke 1 pada 'alan denganjarak tersingkat. Selain itu ada inforrnasi
tentang sebuah simpul antara yang dilalui sebelumnya ("predecessor"). Langkah-langkah
pencarian jalan tersingkat dan termurah tersebut adalah sebagai berikut
Labelkan d(s) = 0
sebagai label jarak permanen, dan d(i) = x sebagai label jarak sementara, untuk
simpul lainnya selain simpul s. Setiap langkah iterasi : label jarak d(i)
merupakan jarak terdekat dari simpul s sepanjang jaln yang label-label nodenya
merupakan label jarak perrnanen. Algoritmanya . memilih simpul i dengan label
jarak sementara minimim dan membuatnya menjadi permanen, dan diteruskan dengan
memeriksa link-link yang kcluar dari i untuk memperbaharul label jarak dari
simpul yang berdekatan (terhubung ke simpul tersebut). Pemeriksaan jarak-jarak
tersebut dilakukan dengan: Bila d(j) > D(i) + Cij = B, maka dibuat d(j) = B
sebagai harga label yang baru dari d(J). 4). Langkah berhenti bila semua label
sudah merupakan label permanen. Dalam label dicantumkan simpul processor.
1.3. Kegunaan
Algoritma Dijkstra
Algoritma Dijkstra
dapat diterapkan pada ilmu jaringan komputer. Jaringan komputer dapat
dimodelkan sebagai sebuah graf, dengan setiap simpul menyatakan sebuah
komputer/router dan sisi didalam graf menyatakan saluran komunikasi(sering
disebut link). Setiap sisi mempunyai label nilai( yang disebut bobot). Bobot
tersebut dapat menyatakan jarak geografis(dalam km), kecepatan transfer data,
waktu pengiriman).
Mencari lintasan
terpendek dari router asal ke router tujuan dapat diartikan sebagai
menentukan lintasan terpendek dari simpul asal ke simpul tujuan di dalam graf
yang merepresentasikan jaringan komputer tersebut. Algoritma Dijkstra adalah
algoritma yang banyak digunakan untuk mencari lintasan terpendek.
2. REDISTRIBUTE
ROUTING PROTOKOL
2.1.
Pengertian Redistribute Routing Protokol
Redistribute adalah
cara untuk meredistribusikan kembali routing tabel yang dibentuk oleh suatu
routing protocol untuk diteruskan ke routing protocol lain. Dengan redistribute
kita bisa membentuk routing tabel yang lengkap dari suatu topologi walaupun
menggunakan routing protocol yang berbeda. Pada prinsipnya router yang menjadi
penghubung antara network dengan routing protocol yang berbeda akan menggunakan
routing protocol sesuai dengan routing protocol yang dipergunakan oleh kedua
network tersebut, misal interface F0/0 pada router tersebut berhubungan dengan
network yang menggunakan RIP maka router tersebut harus menggunakan RIP dan
pada F0/1 menggunakan OSPF maka router tersebut juga harus menggunakan OSPF
sesuai dengan network tempat interface tersebut terhubung. Untuk membuat agar
routing tabel yang dibentuk oleh RIP bisa diteruskan menuju ke OSPF maka
dipergunakan redistribute RIP, dan sebaliknya agar routing tabel yang terbentuk
pada OSPF bisa diteruskan menuju RIP maka dipergunakanlah redistribute OSPF.
Contoh dibawah ini adalah redistribute RIP
dan OSPF
Redistribute
terbagi menjadi redistribute EIGRP, Redistribute OSPF, Redistribute RIP,
Redistribute Connected, Redistribute Static. Berikut beberapa pengertian
redistribute
Redistribute
RIP adalah Suatu proses ketika routing sebuah router mengambil informasi yang
telah di temukan dalam satu routing protocol dan mendistribusikan ke protocol
routing yang berbeda dalam local dan wide area network dengan menggunakan
routing vector jarak algoritma.
Redistribute
OSPF adalah Suatu proses ketika routing sebuah router mengambil informasi dan
mendistribusikan ke protocol yang lain dimana jalur yang terbaik adalah jalur
yang mempunyai cumulative cost yang paling rendah.
Redistribute
EIGRP adalah Proses ketika routing sebuah router mengambil informasi dan
mendistribusikan ke protokolyang berbeda yang menggunakan dua tipe routing
protocol yang berbeda, yaitu distance vector dan linkstate.
2.2.
Cara Kerja
Cara kerjanya yaitu
router yang menjadi penghubung antara network dengan routing protocol yang
berbeda akan menggunakan routing protocol sesuai dengan routing protocol yang
dipergunakan oleh kedua network tersebut, misal interface F0/0 pada router
tersebut berhubungan dengan network yang menggunakan RIP maka router tersebut
harus menggunakan RIP dan pada F0/1 menggunakan OSPF maka router tersebut juga
harus menggunakan OSPF sesuai dengan network tempat interface tersebut
terhubung. Untuk membuat agar routing tabel yang dibentuk oleh RIP bisa diteruskan
menuju ke OSPF maka dipergunakan redistribute RIP, dan sebaliknya agar routing
tabel yang terbentuk pada OSPF bisa diteruskan menuju RIP maka dipergunakanlah
redistribute OSPF.
- Redistribute Rip adalah Suatu proses ketika routing sebuah router mengambil informasi yang telah di temukan dalam satu routing protocol dan mendistribusikan ke protocol routing yang berbeda dalam local dan wide area network dengan menggunakan routing vector jarak algoritma.
- Redistribute OSPF adalah Suatu proses ketika routing sebuah router mengambil informasi dan mendistribusikan ke protocol yang lain dimana jalur yang terbaik adalah jalur yang mempunyai cumulative cost yang paling rendah.
- Redistribute EIGRP adalah Proses ketika routing sebuah router mengambil informasi dan mendistribusikan ke protokolyang berbeda yang menggunakan dua tipe routing protocol yang berbeda, yaitu distance vector dan linkstate.
Tidak ada komentar:
Posting Komentar