routing protocol

IGP ( Interior Gateway Protocol )

adalah protocol distance vector yang diciptakan oleh perusahaan Cisco untuk mengatasi kekurangan RIP. Jumlah hop maksimum menjadi 255 dan sebagai metric, IGP menggunakan Bandwidth, MTU, Delay Dan Load. IGP adalah protocol routing yang menggunakan Autonomous System ( AS ) yang dapat menentukan routing berdasarkan system, interior atau exterior. Administrative distance untuk IGP adalah 100.

IGP merupakan suatu penjaluran jarak antara vektor protokol, bahwa masing-masing penjaluran bertugas untuk mengirimkan semua atau sebagian dari isi table penjaluran dalam penjaluran pesan untuk memperbaharui pada waktu tertentu untuk masing-masing penjaluran.
Penjaluran memilih alur yang terbaik antara sumber dan tujuan. Untuk menyediakan fleksibilitas tambahan, IGP mengijinkan untuk melakukan penjaluran multipath. Bentuk garis equal bandwidth dapat menjalankan arus lalu lintas dalam round robin, dengan melakukan peralihan secara otomatis kepada garis kedua jika sampai garis kesatu turun.

Isi dari informasi routing adalah: 

• Identifikasi tujuan baru,
• Mempelajari apabila terjadi kegagalan. 

IGRP mengirimkan update routing setiap interval 90 detik. Update ini advertise semua jaringan dalam AS. Kunci desain jaringan IGP adalah:

• Secara otomatis dapat menangani topologi yang komplek
• Kemampuan ke segmen dengan bandwidth dan delay yang berbeda
• Skalabilitas, untuk fungsi jaringan yang besar

Secara default, IGP menggunakan bandwidth dan delay sebagai metric. Untuk konfigurasi tambahan, IGP dapat dikonfigurasi menggunakan kombinasi semua varibel atau yang disebut dengan Composite Metric. Variabel-variabel itu misalnya: bandwidth, delay, load, reliability 

Operasi IGP

Masing-masing penjaluran secara rutin mengirimkan masing-masing jaringan lokal kepada suatu pesan yang berisi salinan tabel penjaluran dari tabel lainnya. Pesan ini berisi tentang biaya-biaya dan jaringan yang akan dicapai untuk menjangkau masing-masing jaringan tersebut. Penerima pesan penjaluran dapat menjangkau semua jaringan didalam pesan sepanjang penjaluran yang bisa digunakan untuk mengirimkan pesan.

Tujuan dari IGP

• Penjaluran stabil dijaringan kompleks sangat besar dan tidaka ada pengulangan penjaluran.
• Overhead rendah, IGP sendiri tidak menggunakan bandwidth yang diperlukan untuk tugasnya.
• Pemisahan lalu lintas antar beberapa rute paralel.
• Kemampuan untuk menangani berbagai jenis layanan dengan informasi tunggal.
• Mempertimbangkan menghitung laju kesalahan dan tingkat lalu lintas pada alur yang berbeda.
• Penjaluran stabil dijaringan kompleks sangat besar dan tidaka ada pengulangan penjaluran
• Overhead rendah, IGP sendiri tidak menggunakan bandwidth yang diperlukan untuk tugasnya

Perubahan IGP

Kemudian setelah melalui proses pembaharuan IGP kemudian menjadi EIGP ( Enhanced IGP ), persamaannya adalah IGP dan EIGP sama-sama kompatibel dan antara router-router yang menjalankan EIGP dan IGP dengan autonomous system yang sama akan langsung otomatis terdistribusi. Selain itu EIGP juga akan memberikan tagging external route untuk setiap route yang berasal dari:

• Routing protocol non EIGP.
• Routing protocol IGP dengan AS number yang sama.

EGP ( Exterior Gateway Protocol )

adalah inti dari protocol routing internet. Protocol ini yang menjadi backbone dari jaringan Internet dunia. BGP adalah protokol routing inti dari Internet yg digunakan untuk melakukan pertukaran informasi routing antar jaringan. BGP dijelaskan dalam RFC 4271 RFC 4276 menjelaskan implementasi report pada BGP-4, RFC 4277 menjelaskan hasil ujicoba penggunaan BGP-4. Ia bekerja dengan cara memetakan sebuah tabel IP network yang menunjuk ke jaringan yg dapat dicapai antar Autonomous system (AS).

Hal ini digambarkan sebagai sebuah protokol path vector. EGP tidak menggunakan metrik IGP (Interior Gateway Protocol) tradisional, tapi membuat routing decision berdasarkan path, network policies, dan atau ruleset. BGP versi 4 masih digunakan hingga saat ini . EGP mendukung Class Inter-Domain Routing dan menggunakan route aggregation untuk mengurangi ukuran tabel routing. sejak tahun 1994, BGP-4 telah digunakan di Internet. semua versi dibawahnya sudah tidak digunakan. BGP diciptakan untuk menggantikan protokol routing EGP yang mengijinkan routing secara tersebar sehingga tidak harus mengacu pada satu jaringan backbone saja.

Interior Gateway Protocol (IGP)	Exterior Gateway Protocol (EGP)
Dalam sebuah single autonomous system (AS)	Antara autonomous system (AS) yang berbeda
Memiliki single network administration	Memiliki entitas administrasi yang independen
Pertukaran informasi routing dilakukan antar host dalam sebuah autonomous system atau sebuah routing domain	Pertukaran informasi routing bisa dilakukan antar host pada dua buah autonomous system (AS) yang berbeda
IGP dibagi menjadi dua kategori : Distance Vector Protocol Routing Information Protocol (RIP) Interior Gateway Routing Protocol (IGRP) LinkStateProtocol Open shortest-path first (OSPF) Intermediate System to Intermediate System (IS-IS)	Contoh protocol nya adalah BGP

jaringan komputer (SUBNETTING)

Penghitungan subneting

Subnetting adalah termasuk materi yang banyak keluar di ujian CCNA dengan berbagai variasi soal. Juga menjadi momok bagi student atau instruktur yang sedang menyelesaikan kurikulum CCNA 1 program CNAP (Cisco Networking Academy Program). Untuk menjelaskan tentang subnetting, Romi Satria Wahono biasanya menggunakan beberapa ilustrasi dan analogi yang sudah kita kenal di sekitar kita. Artikel ini sengaja dia tulis untuk rekan-rekan yang sedang belajar jaringan, yang mempersiapkan diri mengikuti ujian CCNA, dan yang sedang mengikuti pelatihan CCNA

Subneting adalah sebuah teknik yang mengizinkan para admistrator jaringan untuk memanfaatkan 32 bit IP address yang tersedia dengan lebih tepat.

IP address merupakan alat yang digunakan  agar paket data dapat mencapai tujuan.

Konsep penghitungan subneting bisa di lakukan dengan dua cara  yaitu dengan cara binary yang relatif lambat dan cara khusus yang lebih cepat.

Ada  empat masalah dalam  penghitungan subneting yaitu :

•  Jumlah subnet
•  Jumlah host per subnet
•  Blok subnet
• Alamat host-broadcast

Penghitunga IP addres umumnya adalah dengan 192.168.1.2  tapi ada kalanya  192.168.1.2/24 dengan subnet 255.255.255.0. sedangkan 24 adalah bid subnet mask diselubung dengan binary 1, atau dengan kata lain subnet masknya  ialah  11111111.11111111.11111111.00000000

(255.255.255.0) konsep seperti ini disebut CIDR (classless inter-domain  Rauting) yang diperkenalkan oleh IEFT pada tahun 1992.

Alamat yang unik terdiri dari 32 bit yang dibagi dalam 4

Okted (8 bit)

00000000 . 00000000 . 00000000 . 00000000

                                                o1           o2                 o3                    o4

IP address di bagi menjadi 2 yaitu network ID dan host ID, network ID digunakan untuk menentukan alamat dalam jaringan. Host ID menentukan alamat dari peralatan jaringan yang sifatnya unik untuk menentukan satu mesin dengan mesin yang lain.

IP Address di bagi menjadi kelas yaitu :

1. Kelas A (1-126)
2. Kelas B (128-192)
3. Keles C (192-223)
4.  Kelas D (224-239)
5. Kelas E (240-255)

Konsep subneting

Tujuan subneting :

• Menghemat penggunaan IP public.
• Mengurangi tingkat kemacatan (kongesti) komunikasi data dalam jaringan.
•  Mengatasi media fisik (hardwere) yang digunakan dalam sebuah network.
• Memecah broadcast domain.

Proses subneting adalah memindah atau menggesr garis pemisah antara bagian network dan host dari suatu IP Address.

Beberapa bit dari bagian host-ID di alokasikanmenjadi bit tambahan pada bagian network-ID.

Network Address pada satu jaringan tunggal di pecah menjadi beberapa subnetwork.

Proses subnetting dapat membuat sejumlah network tambahan dengan mengurangi jumlah maksimum host yang ada dalam tiap network tersebut.

Rujukan :

AL-ANWAR32.blogspot.com

cumpiitudong.blogspot.com

romisatriawahono.net

Pengertian dan Teori Algoritma Dijkstra

Pengertian dan Teori Algoritma Dijkstra

Algoritma Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk 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.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan darivertex u ke vertex v. Himpunan semua tepi disebut E.
Bobot (weights) dari semua sisi dihitung dengan fungs

w: E → [0, ∞)

Jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.
Ongkos (cost) dari sebuah sisi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.

Tujan Algoritma Dijkstra

Ø  Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya.

Ø  Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.

Ø  Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra.

Urutan Logika Algoritma Dijkstra

1.      Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).

2.      Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.

3.      Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.

4.      Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

5.      Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

Contoh :

Titik mengambarkan lokasi dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Pertama tentukan titik yang akan menjadi nomor kode (node) awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, lalu akan dilakukan pengembangan pencarian dari satu titik ke titik selanjutnya (tahap demi tahap).

1.    Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar node telah diberi nilai.

2.    Dijkstra melakukan kalkulasi terhadap node tetangga yang terhubung langsung dengan node keberangkatan (node 1), dan hasil yang didapat adalah node 2 karena bobot nilai node 2 paling kecil dibandingkan nilai pada node lain, nilai = 7 (0+7).

3.    Node 2 diset menjadi node keberangkatan dan ditandai sebagi node yang telah terdatangi. Dijkstra melakukan kalkulasi kembali terhadap node-node tetangga yang terhubung langsung dengan node yang telah terdatangi. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi terakhir, nilai 9 (0+9).

4.    Perhitungan berlanjut dengan node 3 ditandai menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11 (9+2).

5.    Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 (node tujuan ) telah tercapai lewat node 6. Jalur terpendeknya adalah 1-3-6-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai.

6.                 

Contoh soal : 

Mari kita pakai contoh jaringan yang sama dengan yang ada pada postingan Bellman-Ford yang lalu:

Misalnya kita akan menggunakan algoritma Dijkstra untuk mencari path terpendek dari node untuk mempermudah, buatlah tabel seperti berikut ini:

(Notasi dalam tabel algoritma Dijkstra memiliki format (s-j,D), dimana s-j menunjukkan rute dari node s menuju node j, sementara D menunjukkan jarak total antara kedua node tersebut)

Baris pertama masih berupa inisialisasi, yaitu Dj akan memiliki nilai jika tersambung langsung dan tidak memiliki nilai jika tidak tersambung langsung.

Karena node 1 kebetulan hanya memiliki 1 tetangga yaitu node 2, maka i = 2 dimasukkan pada himpunan N.

Node 2 sudah berperan sebagai "perpanjangan" node sumber (node 1), sehingga sekarang node-node yang terhubung dengan node 2 sudah bisa "dijangkau" oleh node 1 via node 2. Diketahui node 3 dan node 4 terhubung langsung dengan node 2, sehingga rutenya ditulis (1-2-3) dan (1-2-4).

Untuk langkah selanjutnya dipilih node i yang telah tersambung dengan node s namun belum masuk dalam himpunan N. Diketahui yaitu node 3 dan node 4. Node yang dipilih adalah yang memiliki jumlah jarak yang paling minimum, yaitu node 4. Sehingga didapat baris tabel berikutnya seperti berikut.

Seperti langkah yang sebelumnya, sekarang node 4 ikut berperan sebagai "perpanjangan" dari node 1 sehingga node 5 dan node 7 yang terhubung langsung dengan node 4 sudah bisa "dijangkau" oleh node 1 dengan rute yang tertampil.

Sebenarnya disini mulai terjadi perbandingan nilai jarak. Dengan dimasukkannya node 4 dalam himpunan N, maka node 4 berlaku sebagai "penembak sementara" (maafkan saya kalau istilahnya alay -_-). Maksudnya adalah node 4 dapat melakukan perhitungan minimum menuju node tertentu meskipun node tersebut telah diketahui rute dan jaraknya.

Dalam kasus ini dapat diambil node 3. Node 3 sudah diketahui rute dan jaraknya pada baris ke-2. Dengan masuknya node 4 pada himpunan N, maka node 4 akan menghitung jarak minimum antara entry D3 yang terdahulu dengan yang baru. (Perbandingan via node 2 dengan via node 4):

Via node 2 --> D2 + C23 = 2 + 3 = 5

Via node 4 --> D4 + C43 = 3 + 7 = 10

Maka entry yang dipertahankan adalah via node 2 dengan jarak 5.

Sebelumnya telah dipilih node 4 sebagai anggota N karena bertetangga dengan node 2. Sekarang dipilih tetangga node 2 yang lainya yaitu node 3.

Perbandingan yang terjadi:

Pada D4

Via node 2 --> D2 + C24 = 2 + 1 = 3

Via node 3 --> D3 + C34 = 5 + 7 = 12

Maka entry yang dipertahankan adalah via node 2 dengan jarak 3.

Pada D5

Via node 4 --> D4 + C45 = 3 + 4 = 7

Via node 3 --> D3 + C35 = 5 + 3 = 8

Maka entry yang dipertahankan adalah via node 4 dengan jarak 7.

Singkat cerita, tabel hasil akhirnya adalah sebagai berikut.

RELATED POSTS: