JARINGAN KOMPUTER

ALGORITMA ROUTING

DAFTAR ISI

BAB I : PENDAHULUAN

o Latar Belakang Masalah

o Pengertian Algoritma dan Routing

o Bagaimana cara kerja Algoritma Routing

o Algoritma Routing Sulit atau tidak?

o Bagaimana cara menggunakan Algoritma Routing?

BAB II : PANDUAN ALGORITMA ROUTING

2.1. Routing

2.2. Static Routing dan Dinamic Routing

2.2.1 Static Routing

2.2.2 Dynamicc Routing

2.2.2.1 Algoritma Distance Vector

2.2.2.1.1 Routing Information Protocol

2.2.2.1.2 Interior Gateway Routing Protocol (IGRP)

2.2.2.2 Algoritma Link State

2.2.2.3 Algoritma Link State

BAB III : KARAKTERISTIK ALGORITMA ROUTING

3. Ciri-ciri dan Pembagian Algoritma Routing

3.1. Pembagian Algoritma Routing

3.2. Metode Algoritma Routing

3.3. Backtracking

3.3.1 Definisi

3.3.2 Prinsip Kerja

3.3.3 Analisis Penerapan Algoritma Backtracking

3.3.4 Penggunaan Backtracking

3.3.5 Kegunaan Backtracking

BAB IV : PENUTUP

o Kesimpulan

o Saran

o Pertanyaan dan Jawaban

BAB I

PENDAHULUAN

Latar Belakang Masalah

Algoritma routing adalah bagian algoritma dari perangkat lunak network layer yang bertanggung jawab untuk menentukan jalur mana yang menjadi jalur transmisi paket. Jika subnet tersebut menggunakan datagram secara internal, keputusan ini harus selalu dibuat setiap kali paket datang. Tetapi jika subnet tersebut menggunakan rangkaian virtual secara internal, keputusan routing ini hanya diambil pada waktu penetapan rangkaian virtual yang baru, sesudah itu paket data tinggal mengikuti rute yang telah ditetapkan sebelumnya. Setiap algoritma routing memiliki sifat-sifat seperti kebenaran, kesederhanaan, kekokohan, kestabilan, kewajaran dan keoptimalitas. Algoritma routing harus dapat menyesuaikan diri atau bertahan terhadap perubahan-perubahan dalam topologi dan lalu lintas data.

Algoritma routing bukanlah pelajaran yang terbilang baru dalam teknologi saat ini. Jangan kalian anggap remeh dengan pembelajaran yang satu ini. Berbicara mengenai Algoritma routing, topik ini sempat menjadi pro dan kontra. Mengapa ? bila diperhatikan cara kerjanya, Algoritma bekerja seperti logika matematika. Bila anda ingin mengerjakan tugas soal matematika dibuku tugas, kemudian kalian pasti mencari tugas yang sangat mudah dan langkah-langkah penyelesainnya dapat dikerjakan dengan secara logis dan sistematis serta terbatas jumlahnya. Begitulah konsep algoritma routing yang dimana Teknik penyusunan langkah-langkah penyelesaian masalah dalam kalimat dengan jumlah kata terbatas, tetapi tersusun secara logis dan sistematis yang mengirimkan paket serta mengarahkan dan menentukan jalur yang akan dilewati paket dari satu jaringan ke jaringan yang lain.

Pengertian Algoritma dan Routing

Algoritma merupakan suatu pondasi yang harus dikuasai oleh setiap mahasiswa yang ingin menyelesaikan suatu masalah secara berstruktur, efektif, dan efisiensi, teristimewa lagi bagi mahasiswa yang ingin menyusun program computer untuk menyelesaikan suatu persoalan.

Routing adalah inti dari semua kontrol jaringan, yaitu mekanisme yang digunakan untuk mengirimkan paket serta mengarahkan dan menentukan jalur yang akan dilewati paket dari satu jaringan ke jaringan yang lain.

Bagaimana cara kerja Algoritma Routing?

Algoritma routing digunakan untuk membangun dan mengatur table routing pada perangkat. Terdapat 2 cara untuk membangun table routing, yaitu :

· Static Routing : routing ini dibangun berdasarkan definisi dari adminstrator.

·       Dynamic Routing : algoritma ini dapat membuat perangkat router untuk dapat menentukan
     jalur routingnya secara otomatis, dengan cara menjelajah jaringan tersebut dan bertukar
     informari routing antar router. Terdapat 3 kategori tentang algoritma dinamik, yaitu :

oDistance Vector

oLink State

oHybrid

Algoritma Routing Sulit atau tidak?

Nah, mungkin ini pertanyaan yang paling luas bila dilihat dari berbagai sudut pandang. Algoritma Routing bisa bersifat sulitt atau tidak baik tergantung tujuan dari menggunakan Algoritma Routing. Tujuan yang baik, misalnya digunakan untuk membuat algoritma dari perangkat lunak network layer yang bertanggung jawab untuk menentukan jalur mana yang menjadi jalur transmisi paket. Jika subnet tersebut menggunakan datagram secara internal, keputusan ini harus selalu dibuat setiap kali paket datang. Tetapi jika subnet tersebut menggunakan rangkaian virtual secara internal, keputusan routing ini hanya diambil pada waktu penetapan rangkaian virtual yang baru, sesudah itu paket data tinggal mengikuti rute yang telah ditetapkan sebelumnya.

Bagaimana cara menggunakan Algoritma Routing?

Host mendengar pada alamat broadcast jika ada update routing dari gateway.

· Host akan memeriksa terlebih dahulu routing table lokal jika menerima update routing .

· Jika rute belum ada, informasi segera dimasukkan ke routing table .

· Jika rute sudah ada, metric yang terkecil akan diambil sebagai acuan.

· Rute melalui suatu gateway akan dihapus jika tidak ada update dari gateway tersebut dalam
waktu tertentu.

· Khusus untuk gateway, RIP akan mengirimkan update routing pada alamat broadcast di
setiap network yang terhubung.

. Algoritma yang digunakan adalah Algoritma Link State.

OSPF harus membentuk hubungan dulu dengan router tetangganya untuk dapat saling berkomunikasi seputar informasi routing. Untuk membentuk sebuah hubungan dengan router tetangganya, OSPF mengandalkan Hello protocol.

Namun uniknya cara kerja Hello protocol pada OSPF berbeda-beda pada setiap jenis media. Ada beberapa jenis media yang dapat meneruskan informasi OSPF, masing-masing memiliki karakteristik sendiri, sehingga OSPF pun bekerja mengikuti karakteristik mereka.

Media tersebut adalah sebagai berikut:

· Broadcast Multiaccess

Media jenis ini adalah media yang banyak terdapat dalam jaringan lokal atau LAN seperti misalnya ethernet, FDDI, dan token ring. Dalam kondisi media seperti ini, OSPF akan mengirimkan traffic multicast dalam pencarian router-router neighbour-nya.

· Point-to-Point

Teknologi Point-to-Point digunakan pada kondisi di mana hanya ada satu router lain yang terkoneksi langsung dengan sebuah perangkat router.

· Point-to-Multipoint

Media jenis ini adalah media yang memiliki satu interface yang menghubungkannya dengan banyak tujuan. Pada jaringan jenis ini, traffic OSPF juga dikirimkan menggunakan alamat IP multicast.

· Nonbroadcast Multiaccess (NBMA)

Media berjenis Nonbroadcast multi-access ini secara fisik merupakan sebuah serial line biasa yang sering ditemui pada media jenis Point-to-Point. Namun secara faktanya, media ini dapat menyediakan koneksi ke banyak tujuan, tidak hanya ke satu titik saja.

BAB II

PANDUAN ALGORITMA ROUTING

2.1. Routing

Routing merupakan proses dimana sesuatu dibawa dari satu lokasi ke lokasi lainnya. Contoh riil sesuatu yang membutuhkan perutean adalah surat, panggilan telepon, perjalanan kereta api, dan lain sebagainya. Pada suatu jaringan router adalah perangkat yang digunakan untuk merutekan trafik jaringan.

Untuk dapat melakukan perutean, suatu router, atau entitas apapun yang membangun routing, melakukan beberapa langkah berikut ini:

· Mengetahui Alamat tujuan – Ke tujuan (alamat) mana sesuatu yang dirutekan dikirim?

· Mengenali sumber-sumber informasi perutean – Dari sumber-sumber (router-router lain) mana saja suatu router dapat mempelajari jalur-jalur menuju tujuan?

· Menemukan rute-rute – Jalur-jalur atau rute-rute mana saja yang mungkin dapat dilalui untuk mencapai alamat tujuan?

· Memilih jalur atau rute – Memilih jalur atau rute terbaik untuk menuju alamat tujuan yang dimaksud.

· Memelihara dan memverifikasi informasi routing – Apakah jalur-jalur ke tujuan yang telah diketahui masih berlaku dan benar?

Pada suatu sistem jaringan komputer, router mempelajari informasi routing dari sumber-sumber routing-nya yang terletak di dalam tabel routing (routing table). Router akan berpedoman pada tabel ini untuk menyatakan port mana yang digunakan mem-forward paket-paket yang ditujukan kepadanya.

· Jika jaringan tujuan terhubung langsung dengan router, maka router sudah mengetahui port mana yang digunakan untuk mem-forward paket.

· Jika jaringan tujuan tidak terhubung langsung dengan router, maka router harus mempelajari rute terbaik untuk mem-forward paket ke tujuan.

2.2. Static Routing dan Dynamic Routing

Secara umum mekanisme koordinasi routing dapat dipelajari oleh router dalam dua metode, yaitu:

• Dimasukkan secara manual oleh administrator jaringan, disebut Static Routes.

• Dikumpulkan melalui proses-proses dinamis yang berjalan di jaringan, disebut sebagai Dynamic Routes.

2.2.1. Static Routing

Routing statik (static route) adalah pengaturan routing paling sederhana yang dapat dilakukan pada jaringan komputer. Static route adalah rute-rute ke host atau jaringan tujuan yang dimasukkan secara manual oleh administrator jaringan ke route table suatu router. Static route mendefinisikan alamat IP hop router berikutnya dan interface lokal yang digunakan untuk mem-forward paket ke tujuan tertentu (hop router berikutnya).

Static route memiliki keunggulan untuk menghemat bandwidth jaringan karena static route tidak membangkitkan trafik route update untuk memberikan informasi perubahan rute yang berlaku (sah) saat ini ke router-router lain. Penggunaan routing statik dalam sebuah jaringan yang kecil tentu bukanlah suatu masalah, hanya beberapa entri yang perlu diisikan
pada forwarding table di setiap router.

Namun tentu dapat dibayangkan bagaimana jika harus melengkapi forwarding table di setiap router yang jumlahnya tidak sedikit dalam jaringan yang besar. Apalagi jika untuk mengisi entri-entri di seluruh router di Internet yang jumlahnya banyak sekali dan terus bertambah setiap hari. Jadi penggunaan static route cenderung membutuhkan waktu ekstra ketika memanajemen jaringan. Hal ini disebabkan karena sistem administrator harus secara manual meng-update route table setiap terjadi perubahan konfigurasi jaringan.

kekurangan dan kelebihan static routing:

– dengan menggunakan next hop
(+) dapat mencegah trjadinya eror dalam meneruskan paket ke router tujuan apabila router yang akan meneruskan paket memiliki link yang terhubung dengan banyak router.itu disebabkan karena router telah mengetahui next hop, yaitu ip address router tujuan

(–) static routing yang menggunakan next hop akan mengalami multiple lookup atau lookup yg berulang. lookup yg pertama yang akan dilakukan adalah mencari network tujuan,setelah itu akan kembali melakukan proses lookup untuk mencari interface mana yang digunakan untuk menjangkau next hopnya.

– dengan menggunakan exit interface

(+) proses lookup hanya akan terjadi satu kali saja ( single lookup ) karena router akan langsung meneruskan paket ke network tujuan melalui interface yang sesuai pada routing tabel

(–) kemungkinan akan terjadi eror keteka meneruskan paket. jika link router terhubung dengan banyak router, maka router tidak bisa memutuskan router mana tujuanya karena tidak adanya next hop pada tabel routing. karena itulah, akan terjadi eror.

Routing static dengan menggunakan next hop cocok digunakan untuk jaringan multi access network atau point to multipoint sedangkan untuk jaringan point to point, cocok dengan menggunakan exit interface dalam mengkonfigurasi static route.

Recursive route lookup adalah proses yang terjadi pada routing tabel untuk menentukan exit interface mana yang akan digunakan ketika akan meneruskan paket ke tujuannya.

2.2.2. Dynamic Routing

Routing dinamik adalah cara yang digunakan untuk melepaskan kewajiban mengisi entri-entri forwarding table secara manual. Protokol routing mengatur router-router sehingga dapat berkomunikasi satu dengan yang lain dan saling memberikan informasi routing yang dapat mengubah isi forwarding table, tergantung keadaan jaringannya. Dengan cara ini, router-router mengetahui keadaan jaringan yang terakhir dan mampu meneruskan datagram ke arah yang benar.

Routing dinamik yang popular saat ini mengacu pada dua tipe algoritma yang dikenalkan oleh Bellman Ford dengan algoritma distance vectornya dan oleh Djikstra dengan algoritma link statenya. Cisco kemudian mengembangkan protocol untuk perangkat routernya yang merupakan gabungan dari kedua algoritma tersebut yang diberi nama protocol EIGRP.

Karakteristik pada dynamic routing:
§ informasi routingnya tidak lagi diberikan oleh orang (manual), melainkan diberikan oleh
   software.
§ apabila salah satu jalur yang ada mengalami gangguan atau kerusakan peralatan, maka
    router akan secara otomatis akan mencari ganti dari jaluryang tidak bisa dipakai lagi.
§ menangani jaringan yang lebih kompleks dan luas, atau jaringan yang konfigurasinya sering
    berubah-ubah (koneksi putus-nyambung)
§ jaringannya cerdas (sudah menggunakan komputasi)
§ memerlukan routing protokol untuk membuat table routing dan routing protokol ini bisa
    memakan sumber daya komputer.

2.2.2.1 Algoritma Distance Vector

Protokol distance vector bekerja dengan memberikan router-router kemampuan untuk mempublikasikan semua rute-rute yang diketahui (router bersangkutan) keluar ke seluruh interface yang dimilikinya.

Router yang secara fisik berada pada jaringan yang sama dinamakan neighbor. Jika router- router mempublikasikan rute-rute yang diketahuinya melalui seluruh interface-nya, dan seluruh neighbor menerima routing update, maka setiap router akan juga mengetahui rute-rute yang dapat dilalui ke seluruh subnet suatu jaringan.

Beberapa hal berikut ini akan lebih mempermudah memahami konsep dasar distance
vector:

· Router secara otomatis akan menambahkan subnet-subnet yang terhubung langsung ke
dalam routing table tanpa menggunakan protokol routing.

· Router mengirim routing update keluar ke seluruh interface-nya untuk memberitahu rute-
rute yang telah diketahuinya.

· Router “memperhatikan” routing update yang berasal dari neighbor-nya, sehingga router
bersangkutan dapat mempelajari rute-rute baru.

· Informasi routing berupa nomor subnet dan suatu metrik. Metrik mendefinisikan seberapa
baik rute bersangkutan. Semakin kecil nilai metrik,semakin baik rute tersebut.

·      Jika memungkinkan, router menggunakan broadcast dan multicast untuk mengirim routing
     update. Dengan menggunakan paket broadcast atau multicast, seluruh neighbor dalam
     suatu LAN dapat menerima informasi routing yang sama untuk sekali update.

· Jika suatu router mempelajari multirute untuk subnet yang sama, router akan memilih rute
terbaik berdasarkan nilai metriknya.

· Router mengirim update secara periodik dan menunggu menerima update secara periodik
dari router-router neighbor.

· Kegagalan menerima update dari neighbor pada jangka waktu tertentu akan menghasilkan
pencabutan router yang semula dipelajari dari neighbor.

· Router berasumsi bahwa rute yang diumumkan oleh suatu router X, router next-hop dari
rutenya adalah router X tersebut.

Beberapa fitur Protokol Distance Vector :

a) Route Poisoning

Routing loop dapat terjadi pada protokol distance vector routing ketika router-router memberitahukan bahwa suatu rute berubah dari kondisi valid ke tidak valid. Konvergensi yang lambat akan mengakibatkan router neighbor terlambat mendapat pemberitahuan kondisi tersebut, sehingga router neighbor tetap menganggap rute tersebut valid (dengan hop 1). Ketika router neighbor mengirimkan pemberitahuan keluar ke seluruh interfacenya, router pertama (yang memberitahukan kegagalan hubungan) akan mendapat informasi bahwa hubungan yang tidak valid tersebut dapat dicapai dari router neighbor dengan hop 2. Kedua router akan terus saling memberi
informasi rute yang salah tersebut disertai dengan menaikkan informasi hop-nya.

Dengan Route poisoning, router tidak akan memberitahukan status tidak valid pada suatu rute yang gagal. Tetapi akan tetap memberikan informasi keadaan rute yang gagal dengan status valid. Rute tersebut akan diberi metrik yang sangat besar, sehingga router lain akan menganggap rute tersebut sebagai rute yang tidak valid.

b) Split Horizon

Fitur Route poisoning tidak seluruhnya dapat mengatasi kondisi looping. Pada kasus di atas, ketika suatu router memberitahukan suatu rute yang gagal dengan metrik yang sangat besar, router neighbor kemungkinan tidak langsung mendapat pemberitahuan ini. Jika router neighbor kemudian memberitahu rute yang tidak valid tersebut ke router pertama (yang memberitahukan kegagalan hubungan) bahwa rute tersebut dapat dicapai dari dirinya dengan metrik yang jauh lebih baik, maka kondisi di atas dapat terjadi lagi.

Split horison mengatasi masalah ini dengan memberikan aturan bahwa suatu router yang mendapat pemberitahuan update informasi melalui interface x, tidak akan mengirimkan pemberitahuan yang sama ke interface x pula.

c) Split Horizon with Poison Reverse

Split horizon with poison reserve merupakan varian dari split horizon. Pada kondisi stabil, router bekerja dengan fitur split horizon. Tetapi ketika suatu rute gagal,router neighbor yang mendapat informasi ini akan mengabaikan aturan split horizon, dan kemudian mengirimkan kembali informasi tersebut ke router pertama dengan metrik yang sangat besar pula. Metode ini dapat memastikan bahwa seluruh router mendapat informasi yang benar mengenai kondisi rute tersebut.

d) Hold-Down Timer

Kondisi looping masih tetap terjadi pada jaringan redundant (jaringan dengan lebih dari satu jalur) walaupun fitur split horizon telah diaktifkan. Hal ini dimungkinkan karena suatu router dalam jaringan dapat memperoleh informasi mengenai rute yang sama melalui lebih dari satu jalur dan router. Oleh karenanya ketika suatu rute diinformasikan tidak valid oleh router bersangkutan, maka router neighbor pada saat yang sama juga mungkin mendapat informasi dari router lain dengan metrik yang masih dapat dijangkau. Informasi rute valid ini (poison) kemudian disampaikan ke router
pertama, sehingga kondisi looping akan terjadi.

Hold-Down Timer mengatasi masalah ini dengan memberikan aturan bahwa ketika suatu router yang mendapat pemberitahuan suatu rute tidak valid, router tersebut akan mengabaikan informasi rute-rute alternatif ke subnet bersangkutan pada suatu waktu tertentu (hold-down timer).

e) Triggered (Flash) Updates

Protokol distance vektor biasanya mengirimkan update secara regular berdasarkan interval waktu tertentu. Oleh karenanya banyak masalah looping terjadi sesaat setelah suatu rute tidak valid. Hal ini disebabkan karena beberapa router tidak segera mendapat informasi ini. Beberapa router mengatasi masalah ini dengan menggunakan fitur triggered update atau flash update, dimana router akan segera mengirim pemberitahuan update baru sesaat setelah suatu rute tidak valid. Dengan demikian informasi perubahan status rute dapat segera di-forward-kan secara lebih cepat, sehingga pengaktifan hold-down timer di sisi router neighbor juga lebih cepat.

2.2.2.1.1 Routing Information Protocol (RIP)

Routing protokol yang menggunakan algoritma distance vector, yaitu algortima Bellman-Ford. Pertama kali dikenalkan pada tahun 1969 dan merupakan algoritma routing yang pertama pada ARPANET. Versi awal dari routing protokol ini dibuat oleh Xerox Parc’s PARC Universal Packet Internetworking dengan nama Gateway Internet Protocol. Kemudian diganti nama menjadi Router Information Protocol (RIP) yang merupakan bagian Xerox network Services.

RIP yang merupakan routing protokol dengan algoritma distance vector, yang menghitung jumlah hop (count hop) sebagai routing metric. Jumlah maksimum dari hop yang diperbolehkan adalah 15 hop. Tiap RIP router saling tukar informasi routing tiap 30 detik, melalui UDP port 520. Untuk menghindari loop routing, digunakan teknik split horizon with poison reverse. RIP merupakan routing protocol yang paling mudah untuk di konfigurasi.

RIP memiliki 3 versi yaitu :

1. RIPv1

2. RIPv2

3. RIPng

Kelebihan

· Menggunakan metode Triggered Update

· RIP memiliki timer untuk mengetahui kapan router harus kembali memberikan
informasi routing.

·   Jika terjadi perubahan pada jaringan, sementara timer belum habis, router tetap harus
   mengirimkan informasi routing karena dipicu oleh perubahan tersebut (triggered
   update).

· Mengatur routing menggunakan RIP tidak rumit dan memberikan hasil yang cukup
dapat diterima, terlebih jika jarang terjadi kegagalan link jaringan

Kekurangan

· Jumlah host Terbatas

· RIP tidak memiliki informasi tentang subnet setiap route.

· RIP tidak mendukung Variable Length Subnet Masking (VLSM).

·   Ketika pertama kali dijalankan hanya mengetahui cara routing ke dirinya
   sendiri (informasi lokal) dan tidak mengetahui topologi jaringan tempatnya
   berada.

1. RIP Versi 1

· Dokumen –> RFC1058.

· RIP V1 routing vektor-jarak yang dimodifikasi dengan triggered update dan split
horizon dengan poisonous reverse untuk meningkatkan kinerjanya.

· RIP V1 diperlukan supaya host dan router dapat bertukar informasi
untukmenghitung rute dalam jaringan TCP/IP.

· Informasi yang dipertukarkan RIP berupa :

a. Host

b. Network

c. Subnet

d. Rutedefault

2. RIP Versi 2

· Enhancement dari RIP versi1 ditambah dengan beberapa kemampuan baru,

· Algoritma routing sama dengan RIP versi1,

· Bedanya terletak pada format dengan tambahan informasi yang dikirim,

· Kemampuan baru :

a. Tag –> untuk rute eksternal.

b. Subnet mask.

c. Alamat hop berikutnya.

d. Autentikasi.

2.2.2.1.2. Interior Gateway Routing Protocol (IGRP)

IGRP (Interior Gateway Routing Protocol) adalah juga protocol distance vector yang diciptakan oleh perusahaan Cisco untuk mengatasi kekurangan RIP. Jumlah hop maksimum menjadi 255 dan sebagai metric, IGRP menggunakan bandwidth, MTU, delay dan load. IGRP adalah protocol routing yang menggunakan Autonomous System (AS) yang dapat menentukan routing berdasarkan system, interior atau exterior. Administrative distance untuk IGRP adalah 100.

Kelebihan

· support = 255 hop count

Kekurangan

· Jumlah Host terbatas

RIP (Routing Information Protocol) dan IGRP (Interior Gateway RoutingProtocol) merupakan dua standar protokol routing berbasis distance vector routing protocol. RIP dan IGRP memiliki banyak kesamaan secara logik. Beberapa perbedaan penting dari kedua protokol routing ini diperlihatkan pada tabel berikut ini:

IGRP Metric memberikan penghitungan yang lebih baik mengenai seberapa baik rute-rute yang ada dibandingkan RIP metric. IGRP metric dihitung menggunakan pengukuran bandwidth dan delay pada interface dimana informasi update diterima. Hal ini akan memberikan arti yang lebih baik dibandingkan metric berdasarkan hop count.

RIP menggunakan penghitungan hop untuk besaran metriknya. Ketika informasi update diterima, metrik dari setiap subnet dalam informasi update merupakan jumlah router yang dilalui oleh informasi antara router penerima dengan setiap subnet. Hal ini dapat dilakukan karena sebelum mengirim informasi update, router akan menambah satu nilai metrinya untuk setiap subnet.

2.2.2.2 Algoritma Link State

Algoritma dasar kedua yang digunakan dalam proses routing adalah algoritma link-state. Algoritma routing link-state-based dikenal juga sebagai shortest path first (SPF). Algoritma ini mengelola suatu database kompleks dari informasi topologi. Jika algoritma distance vector tidak memiliki informasi spesifik mengenai jaringan-jaringan jauh dan tidak mengetahui router-router jauh, maka algoritma routing link-state mengelola secara penuh pengetahuan mengenai jarak router dan bagaimana mereka terhubung.

Routing link-state menggunakan link-state paket (LSP), suatu database topologi, algoritma SPF, yang menghasilkan SPF tree, dan pada akhirnya akan dihasilkan routing table dari jalur dan port untuk setiap jaringan. Routing link-state memiliki keunggulan pada jaringan besar karena beberapa alasan berikut:

· Protokol link-state hanya mengirim update dari topologi yang berubah saja.

· Periode update lebih jarang dibanding protokol distance vector.

· Routing link-state dapat disegmentasi ke dalam hirarki-hirarki area yang dapat membatasi
jangkauan perubahan-perubahan rute.

· Mendukung classless addressing.

· Routing link-state mengirim subnet mask bersama dengan update routing.

Protokol routing link-state mengurangi trafik broadcast karena protokol ini tidak secara periodik melakukan broadcast ataupun mengirimkan seluruh isi table routing-nya ketika melakukan broadcast. Protokol routing link-state melakukan pertukaran salinan lengkap tabel rutenya ketika inisialisasi berlangsung. Selajutnya pertukaran update rutenya dilakukan secara multicast dan hanya pada saat terjadi perubahan (dibangkitkan oleh perubahan topologi). Dengan demikian kondisi ini memungkinkan hanya perubahan saja yang dikirim ke router-router lain, bukan seluruh route table-nya.

Berbeda dengan protokol distance vector, protokol link-state harus menghitung informasi metrik rute yang diterimanya. Router akan menghitung seluruh cost yang berhubungan dengan link pada setiap rute untuk mendapatkan metrik rute-rute yang terhubung. Hal ini mengakibatkan router-router yang menggunakan protokol link-state bekerja lebih berat dan memerlukan lebih banyak memory serta siklus pemrosessan.

Open Shortest Path First (OSPF)

OSPF adalah protokol routing yang diperuntukkan bagi jaringan IP dengan Interior Gateway Protocol (IGP) oleh working group dari Internet Engineering Task Force (IETF). OSP memiliki dua karakteristk utama, yaitu open standard dan berbasis pada algoritma SPF yang kadangkala direferensikan dengan algoritma Dijkstra (seseorang yang memiliki kontribusi pembuatan algoritma SPF).

Proses dasar pembelajaran rute-rute OSPF untuk pertamakalinya umumnya:

· Setiap router menemukan neighbor melalui setiap interface-nya. Daftar setiap neighbor di simpan
dalam tabel neighbor.

· Setiap router menggunakan protokol tertentu untuk bertukar informasi topologi (LSA) dengan
neighbor-nya.

· Setiap router menyimpan informasi topologi yang dipelajarinya dalam database topologi.

· Setiap router menjalankan algoritma SPF pada database topologinya untuk menghitung rute-rute
terbaik dari setiap subnet di database.

· Setiap router menyimpan rute-rute terbaik ke setiap subnet ke dalam table routing-nya

OSPF memiliki 3 table di dalam router :

1. Routing table

Routing table biasa juga disebut sebagai Forwarding database. Database ini berisi the lowest cost untuk mencapai router-router/network-network lainnya. Setiap router mempunyai Routing table yang berbeda-beda.

2. Adjecency database

Database ini berisi semua router tetangganya. Setiap router mempunyai Adjecency database yang berbeda-beda.

3. Topological database

Database ini berisi seluruh informasi tentang router yang berada dalam satu networknya/areanya.

Kelebihan

· tidak menghasilkan routing loop

· mendukung penggunaan beberapa metrik sekaligus

· dapat menghasilkan banyak jalur ke sebuah tujuan

· membagi jaringan yang besar mejadi beberapa area.

· waktu yang diperlukan untuk konvergen lebih cepat

Kekurangan

· Membutuhkan basis data yang besar

· Lebih rumit

Beberapa fitur Protokol link state :

a. Steady-State Operation

Tidak seperti protokol distance vector, protokol link-state menjaga hubungan

dengan neighbor melalui pengiriman paket-paket kecil secara tak berkala dan jarang (kadang-kadang). OSPF menyebut paket kecil ini dengan Hello packets. Hello packet secara sederhana mengidentifikasi subnet dan keaktifan link serta router neighbor.

Ketika router gagal menerima paket Hellos dari neighbor pada suatu interval

tertentu (dinamakan dead interval), router akan mempercayai bahwa router bersangkutan mengalami kegagalan dan menandainya dengan “down” pada database topologi-nya. Kemudian router berhenti menerima paket Hello dan mulai menjalankan Dijkstra untuk menghitung kembali rute-rute baru.

b. Loop Avoidance

Algoritma SPF mencegah loop yang secara natural telah dilakukan bersamaan dengan pemrosessan database topologi, sehingga tidak diperlukan fitur loop-avoidance seperti split horizon, poison reserve, hold down timer, dan lain sebagainya.

c. Scalling OSPF Through Hierarchical Design

Pada jaringan besar dengan ratusan router, waktu konvergensi OSPF dapat melambat, dan membutuhkan banyak memory, serta pembebanan prosessor.

Masalah ini dapat diringkas sebagai berikut:

· Pada topologi database yang besar dibutuhkan lebih banyak memory dalam setiap router.

· Pemrosessan database topologi yang besar dengan algoritma SPF membutuhkan daya
pemrosesan yang bertambah secara eksponensial sebanding dengan ukuran database topologi.

· Satu perubahan status interface (up ke down atau down ke up) memaksa setiap router untuk
menjalankan SPF lagi.

Meskipun demikian, tidak ada definisi yang tepat untuk mendeskripsikan “jaringan besar”. Sebagai patokan (sangat umum, bergantung pada desain, model, router, dan lain-lain), untuk jaringan dengan paling sedikit 50 router dan 100 subnet, fitur OSPF scalability seharusnya digunakan untuk mengurangi problem di atas.

d. OSPF Area

Penggunaan OSPF area dapat memecahkan banyak (tidak semuanya) permasalahan mendasar ketika menjalankan OSPF pada jaringan besar. OSPF area memecah-mecah jaringan sehingga router dalam satu area lebih sedikit mengetahui informasi topologi mengenai subnet pada area lainnya. Dengan database topologi yang lebih kecil, router akan mengkonsumsi memory dan proses yang lebih sedikit.

OSPF menggunakan istilah Area Border Router (ABR) untuk mendeskripsikan suatu router yang berada diantara dua area (perbatasan). Suatu ABR memiliki database topologi untuk kedua area tersebut dan menjalankan SPF ketika status link berubah pada salah satu area. Penggunaan area tidak selamanya mengurangi kebutuhan memory dan sejumlah penghitungan SPF untuk router ABR.

e. Stub Area

OSPF mengijinkan pendefinisian suatu area sebagai stub area, sehingga dapat mengurangi ukuran database topologi. OSPF juga mengijinkan varian area lain yang dapat mengurangi ukuran database topologi, dimana juga akan mempercepat pemrosessan algoritma SPF. Tipe area terbaru saat ini adalah Totally Not-So-Stubby Area (TNSSA).

2.2.2.3. Balanced Hybrid Routing Protocol

Cisco menggunakan istilah balanced hybrid untuk mendeskripsikan protokol routing yang dipakai oleh EIGRP (enhanced IGRP). Hal ini dikarenakan EIGRP memiliki beberapa fitur seperti protokol distance vector dan protokol link-state.

Enchanced Interior Gatway Routing Protocil (EIGRP)

EIGRP (Enhanced Interior Gateway Routing Protocol) adalah routing protocol yang hanya di adopsi oleh router cisco atau sering disebut sebagai proprietary protocol pada cisco. Dimana EIGRP ini hanya bisa digunakan sesama router cisco saja. Bgmn bila router cisco digunakan dengan router lain spt Juniper, Hwawei, dll menggunakan EIGRP??? Seperti saya bilang diatas, EIGRP hanya bisa digunakan sesama router cisco saja. EIGRP ini sangat cocok digunakan utk midsize dan large company. Karena banyak sekali fasilitas2 yang diberikan pada protocol ini.

Kelebihan

· melakukan konvergensi secara tepat ketika menghindari loop.

· memerlukan lebih sedikit memori dan proses

· memerlukan fitur loopavoidance

Kekurangan

· Hanya untuk Router Cisco

EIGRP menggunakan formula berbasis bandwidth dan delay untuk menghitung metrik yang bersesuaian dengan suatu rute. Formula ini mirip dengan yang digunakan oleh IGRP, tetapi jumlahnya dikalikan dengan 256 untuk mengakomodasi perhitungan ketika nilai bandwidth yang digunakan sangat tinggi.

EIGRP melakukan konvergensi secara cepat ketika menghindari loop. EIGRP tidak melakukan perhitungan-perhitungan rute seperti yang dilakukan oleh protokol link-state. Hal ini menjadikan EIGRP tidak membutuhkan desain eksta, sehingga hanya memerlukan lebih sedikit memory dan proses dibandingkan protokol link-state.

Konvergensi EIGRP lebih cepat dibandingkan dengan protokol distance

vector. Hal ini terutama disebabkan karena EIGRP tidak memerlukan fitur loopavoidance yang pada kenyataannya menyebabkan konvergensi protokol distance vector melambat. Hanya dengan mengirim sebagian dari routing update (setelah seluruh informasi routing dipertukarkan), EIGRP mengurangi pembebanan di jaringan.

Salah satu kelemahan utama EIGRP adalah protokol ini Cisco-proprietary, sehingga jika diterapkan pada jaringan multivendor diperlukan suatu fungsi yang disebut route redistribution. Fungsi ini akan menangani proses pertukaran rute router diantara dua protokol link-state (OSPF dan EIGRP).

BAB III

KARAKTERISTIK ALGORITMA ROUTING

3. Ciri-ciri dan Pembagian Algoritma Routing

3.1. Pembagian Algoritma Routing

Algoritma nonadaptive tidak mendasarkan keputusan routing pada keadaan lalu lintas data dan topologi jaringan saat ini. Pemilihan jalur komunikasi yang digunakan antarmesin pada algoritma iniditentukan dari awal dan ditanamkan ke router pada saat jaringan diaktifkan. Algoritma routing ini disebut juga static routing.

Algoritma adaptive menentukan jalur komunikasi berdasar kondisi jaringan saat ini, seperti topologi yang digunakan dan juga kondisilalu lintas data. Algoritma adaptive (dynamic routing) memperoleh informasi untuk proses routing secara lokal, dari router terdekat atau dari semua router yang ada dijaringan.
Dua hal yang penting yang menguntungkan dari adaptive routing adalah:

1.Strategi routing adaptif dapat meningkatkan performance seperti apa yang keinginan user

2.Strategi adaptif dapat membantu kendali lalulintas. Akan tetapi, strategi ini dapat menimbul-kan
beberapa akibat, misalnya :

·Proses pengambilan keputusan untuk menetap-kan rute menjadi sangat rumit akibatnya beban pemrosesan pada jaringan meningkat.

·Pada kebanyakan kasus, strategi adaptif tergantung pada informasi status yang dikumpulkan pada satu tempat tetapi digunakan di tempat lain. Akibatnya beban lalu lintas meningkat.

· Strategi adaptif bisa memunculkan masalah seperti kemacetan apabila reaksi yang terjadi terlampau cepat, atau menjadi tidak relevan apabila reaksi sangat lambat.

Kategori Strategi Adaptif dapat dibagi menjadi :

- Isolated adaptive : informasi lokal, kendali ter-distribusi.

- Adaptive : informasi dari node yang berdekatan, kendali terdistribusi.

- Adaptive : informasi dari seluruh node, kendali terpusat.

3.2. Metode Algoritma Routing

o Forward Search Algrithm

Forward search algorithm dinyatakan sebagai menentukan jarak terpendek dari node awal yang ditentukan ke setiap node yang ada. Algoritma diungkapkan dalam stage. Dengan k buah stage, jalur terpendek node k terhadap node sumber ditentukan. Node-node ini ada dalam himpunan N. pada stage ke ( k+1 ), node yang tidak ada dalam M yang mempunyai jarak terpendek terhadap sumber ditambahkan ke M. sebagai sebuah node yang ditambahkan dalam M, maka jalur dari sumber menjadi terdefinisi

o Backward Search Algortihm

Menentukan biaya terkecil yang diberikan node tujuan dari semua node yang ada. Algoritma ini juga diproses tiap stage. Pada setiap stage, algoritma menunjuk masing-masing node. Definisi yang digunakan : N = himpunan node yang terdapat pada jaringan. D = node tujuan I ( i,j ) = seperti keterangan di atas. C2 ( n ) = biaya dari jalur biaya terkecil dari n ke D yang dihasilkan ketika algortma dikerjakan.

3.3. Backtracking

3.3.1 Definisi

Backtracking adalah algoritma yang berbasis pada algoritma DFS (Depth-First Search) yang dapat mencari solusi sebuah persoalan dengan lebih mangkus. Algoritma ini dapat menemukan solusi sebuah persoalan tanpa perlu memeriksa semua kemungkinan solusi dan hanya mempertimbangkan pencarian yang mengarah kesolusi. Algoritma Backtracking merupakan algoritma yang berbasiskan DFS (Depth First Search). Yang dilakukan oleh algoritma ini adalah mencari kemungkinan solusi dengan menelusuri hingga node terdalam. Kemudian dilakukan perjalanan kembali dengan melalui node-node calon solusi yang telah dikunjungi untuk menemukan jalur solusi lain yang lebih sesuai. Dengan kata lain, algoritma ini akan melakukan pencarian solusi secara berurutan dari jalur solusi satu ke jalur solusi lain. Namun akan berhenti bila solusi yang sesuai telah ditemukan.

3.3.2 Prinsip Kerja

Backtracking menggunakan prinsip DFS untuk mencari sebuah solusi persoalan. Ruang solusi diorganisasikan dalam struktur pohon dengan simpul pohon menyatakan status persoalan.Algoritma backtracking mencari solusi dengan menelusuri pohon dengan prinsip DFS. Di setiap simpul yang dikunjungi, algoritma akan mengecek apakah lintasan yang tercipta mengarah ke solusi (memenuhi fungsi pembatas). Jika lintasan tidak mengarah ke solusi,simpul tersebut akan ‘dibunuh’ dan menjadi simpul mati. Simpul mati ini tidak akan diperluas lagi. Jika pembentukan lintasan berakhir dengan simpul mati, proses pencarian akan membangkitkan simpul anak yang lain. Bila tidak ada lagi simpul anak yang dapat dibangkitkan,pencarian solusi dilanjutkan dengan melakukan runutbalik(backtrack) ke simpul hidup terdekat, yaitu orang tua. Simpul ini akan menjadi expand-node yang baru.Pencarian akan berhenti bila solusi sudah ditemukanatau tidak ada lagi simpul hidup untuk runut-balik. Algoritma backtracking secara signifikan memperbaiki kompleksitas algoritma yang dijumpai pada algoritma brute force. Jika jumlah simpul dalam pohon ruang status adalah 2n atau n!, maka pada kasus terburuk, backtrackingmemerlukan waktu O(p(n)2n) atau O(q(n)n!) dengan p(n)dan q(n) adalah polinom derajat n yang menyatakan waktu komputasi setiap simpul [3]. Sama seperti algoritma Brute-Force, prinsip dasar algoritma Backtracking adalah mencoba semua kemungkinan solusi yang ada. Perbedaan utamanya adalah pada konsep dasarnya, yaitu pada Backtracking semua solusi dibuat dalam bentuk pohon solusi (tree), dan kemudian pohon tersebut dan ditelusuri secara DFS (Depth First Search) sehingga ditemukan solusi terbaik yang diinginkan.

Contohnya :

Misalkan pohon di atas menggambarkan solusi dari suatu persoalan. Jika kita ingin mencari solusi dari A ke E, maka jalur yang harus ditempuh adalah (A-B-E). Demikian juga untuk solusi-solusi yang lain. Algoritma Backtracking akan memeriksa jalur secara DFS, yaitu dari solusi terdalam pertama yang ditemui yaitu solusi E. Jika ternyata E bukanlah solusi yang diharapkan, maka pencarian akan dilanjutkan ke F. Jalur yang harus dilalui untuk bisa mencapai E adalah (A-B-E) dan untuk mencapai F adalah (A-B-F). Kedua solusi tersebut memiliki jalur awal yang sama, yaitu (A-B). Jadi, daripada memeriksa ulang jalur dari A kemudian B, maka jalur (A-B) disimpan dulu dan langsung memeriksa solusi F. Untuk kasus pohon yang lebih rumit, cara ini dianggap lebih efisien daripada jika menggunakan algoritma Brute-Force.

3.3.3 Analisis Penerapan Algoritma Backtracking

Algoritma routing yang berdasar pada teknik pencarian graf telah terbukti memberikan fleksibilitas yang paling baik Jika digunakan metode exhaustive traversal, paket data dikirim melalui semua node yang dapat dikunjungisampai node tujuan ditemukan. Dengan metode ini, sebuah node pada jaringan dapat dikunjungi lebih darisatu kali, sehingga dapat menghasilkan beban yang tidakperlu bagi jaringan. Pendekatan yang dilakukan untuk mencegah redundansikunjungan paket data ke sebuah node adalah dengan menyimpan informasi status pada header pesan yang dikirim. Misalkan sebuah paket mempunyai struktur (R, TD,message). R adalah vektor n-bit yang berfungsi sebagairouting tag. Jika bit i pada R terdefinisi, maka paket data harus melalui dimensi i. Jika R = 0, maka paket data telahmencapai tujuan. TD adalah himpunan dimensi yang telahdilalui oleh paket data. Pada host sumber, TD diinisialisasi dengan nilai 0. Selama perjalanan, setiap melalui nodeantara sumber dan tujuan, nilai R dan TD diperbaharui. Proses routing pada titik-titik antara (intermediate node)melalui beberapa tahap. Tahap pertama adalahmentransmisikan paket data melalui jalur terpendek (shortest path) ke node tujuan. Jika jalur tertutup oleh komponen (node / host) yang cacat, maka himpunan dimensi yang pernah dilalui oleh paket data sampai saatini dapat digunakan untuk menghitung alamat semua nodeyang pernah dilalui oleh paket data ini.

Awalnya, paket data akan melalui dimensi 0 untukmencapai node 0011, kemudian melalui dimensi 1 untukmencapai node 0001. Kerusakan pada jalur komunikasi yang seharusnya dipilih, yaitu jalur dari 0001 ke 0101 dandari 0001 ke 1001 menyebabkan paket data terkirim kenode 0000. Di node 0000, kerusakan terdeteksi pada dua jalur komunikasi. Daftar dimensi yang telah dilalui olehpaket data tersimpan pada header paket. Daftar ini dapatdigunakan untuk menyusun ulang semua node yang telah dilalui paket data. Dari informasi ini, node 0000 dapatmenentukan bahwa node 0010 pernah dilalui oleh paketdata. Hal ini menyebabkan node 0000 untuk melalukan backtrack dengan mengirim ulang paket data ke node0001. Di node 0001, semua kemungkinan jalur telahdiperiksa sehingga menyebabkan paket data backtrack kenode 0011 dengan isi pesan (1110, [0, 1, 0, 0, 1],message). Algoritma routing pada node0011 akan memilih dimensi terkecil untuk melakukan pergerakanmenuju node tujuan, yaitu node 2, sehingga paket yangdikirim ke node 0111 berisi (1010, [0, 1, 0, 0, 1, 2],message). Node 0111 akan memilih dimensi 1 danmengirim pesan (1000, [0, 1, 0, 0, 1, 2,1], message) kenode 0101. Node 0101 kemudian mengirim paket data kenode 1101 yang merupakan node tujuan.

Setelah semua di tuliskan maka, akan mendapatkan suatu data yang telah dicarikan pada dimensi 0 yang mencapai node yang di cari . lalu setelah dapat hasil nya maka code pada program yang telah ditentukan ada di dalam program deklarasi Algoritma yang dimana seuai dengan kararekteristik yang di inginkan yang ada pada di bawah ini.

Contoh Deklarasi

j, n, h : integer

Algoritma:

if R = 0 then node tujuan sudah tercapai

for j := 0 to n – 1 and not b do begin

I if notVisited(getNode(rj)) then

kirim (R ⊕ ei, TD&j, message ) melalui dimensi j.

stop()

endif

endfor

if notFault(min(R)) and notVisited(getNode(min(R)))

then

begin

kirim (R ⊕ eh, TD&h, message ) melalui dimensi h.

stop()

endif

if node saat ini memperoleh paket dari node dengan

dimensi g then begin

kirim ulang (R ⊕ eg, TD&g, message ) ke node sebelumnya {backtrack ke node sebelumnya}

endif

3.3.4 Penggunaan Backtracking

Algoritma Backtracking digunakan untuk membuat Artificial Intelligence pada board games seperti catur, othello, dan checker. Dengan algoritma ini dapat dibuat pohon solusi sampai dengan kedalaman tertentu dari current status, dan dipilih solusi yang dapat membantu user menemukan langkah-langkah yang nantinya akan menghasilkan pohon solusi yang menguntungkan bagi user. Cara ini dipakai sebagai Artificial Intelligence yang digunakan untuk menyelesaikan dynamic problem. Beberapa contoh penggunaan dari algoritma Backtrack dari suatu masalah statik adalah untuk memecahkan masalah N-Queen problem dan Maze Solver.

N-Queen problem adalah permasalahan di mana user harus mencari cara bagaimana meletakkan bidak Queen catur sebanyak n buah pada papan catur atau pada papan berukuran nxn sedemikian rupa sehingga tidak ada satu bidakpun yang dapat memakan bidak lainnya hanya dengan 1 langkah (1 gerakan). Meskipun ada kemungkinan terdapat lebih dari satu cara untuk mendapatkan solusinya, tetapi tidak perlu dilakukan proses pencarian untuk mendapatkan semua solusinya. Untuk beberapa kasus tertentu perlu dilakukan pencarian terhadap semua solusi sehingga dapat dipilih satu solusi terbaik.

Maze solver adalah permasalahan di mana user harus mencari cara agar bisa keluar dari suatu maze (labirin). Pada maze sederhana di mana field yang dibentuk dapat direpresentasikan dalam bentuk biner dan pada setiap petak terdapat maksimal 4 kemungkinan : atas, kiri, bawah, dan kanan. Untuk masalah ini biasanya solusi pertama yang ditemukan bukanlah solusi optimal seperti yang diharapkan, sehingga harus dilakukan pencarian terhadap semua kemungkinan solusi agar didapatkan solusi terbaik.

3.3.5 Kegunaan Backtracking

v Algoritma Backtracking sangat berguna untuk mencari jumlah solusi jalur kombinasi yang diperlukan untuk mendapatkan solusi optimal.

v Algoritma Backtracking juga mudah diimplementasikan dengan bahasa pemrograman yang mendukung pemanggilan fungsi/prosedur rekursif.

v Untuk persoalan yang memiliki kemungkinan solusi yang kompleks seperti permainan catur, sebaiknya kedalaman pohon dibatasi sehingga tidak memakan waktu yang lama.

v Untuk alokasi memori yang akan dipakai untuk menyimpan langkah-langkah penyelesaian sebaiknya menggunakan dynamic array, karena sebagian besar program yang menggunakan algoritma ini menghasilkan solusi yang tidak dapat diprediksi.

BAB IV

PENUTUP

A. Kesimpulan

Jadi, kesimpulannya dari Algoritma Routinga adalah bahwa :

· Untuk jaringan berskala kecil algoritma routing yang sesuai adalah routing secara statik karena lebih menghemat bandwidth sedangkan untuk jaringan berskala besar lebih tepat menggunakan dynamic routing.

· Protokol RIP banyak digunakan karena kesederhanaan dalam mengimplementasikannya.

·Algoritma link state lebih baik dibandingkan algoritma distance vector dilihat dari sisi waktu konvergensi dan tidak adanya routing loop di dalam jaringan.

·Algoritma EIGRP yang dikembangkan Cisco sudah menggabungkan kelebihan dari algoritma link state dan algoritma distance vector, tetapi teknologi ini tidak banyak didukung oleh vendor router yang lain (Cisco proprietary).

B. Saran
Jika kita ingin membuat skala Algoritma Routing yang besar, maka kita harus memakai atau menggunakan dynamic routing yang berukuran skala besar yang dimana bisa menampung banyak nya yang dikelolah. Serta dalam Algoritma nya lebih baik kita menggunakan Algoritma Link State yang nilai lebih nya dalam sisi waktu yang konvergensi dan tidak adanya routing loop di dalam jaringan yang sedang berjalan.

C. Pertanyaan dan Jawaban

A. Pertanyaan

1. Apa yang dimaksud dengan Algoritma?

2. Apa yang dimaksud dengan Routing?

3. Bagaimana cara kerja Algoritma Routing ?

4. Apa yang dimaksud dengan Algoritma Routing?

5. Sebutkan langkah-langkah membangun routing?

6. Sebutkan kekurangan dan kelebihan static routing dengan menggunakan next hop?

7. Sebutkan kekurangan dan kelebihan static routing dengan menggunakan exit interface?

8. Sebutkan Karakteristik dynamic routing?

9. Sebutkan Kelebihan dan Kekurangan Routing Information Protocol (RIP) ?

10. Sebutkan Keunggulan Routing link-state?

B. Jawaban

1. Algoritma merupakan suatu pondasi yang harus dikuasai oleh setiap mahasiswa yang ingin menyelesaikan suatu masalah secara berstruktur, efektif, dan efisiensi, teristimewa lagi bagi mahasiswa yang ingin menyusun program computer untuk menyelesaikan suatu persoalan.

2. Routing adalah inti dari semua kontrol jaringan, yaitu mekanisme yang digunakan untuk mengirimkan paket serta mengarahkan dan menentukan jalur yang akan dilewati paket dari satu jaringan ke jaringan yang lain.

3. Algoritma routing digunakan untuk membangun dan mengatur table routing pada perangkat. Terdapat 2 cara untuk membangun table routing, yaitu :

Static Routing : routing ini dibangun berdasarkan definisi dari adminstrator.

   Dynamic Routing : algoritma ini dapat membuat perangkat router untuk dapat
   menentukan jalur routingnya secara otomatis, dengan cara menjelajah jaringan
   tersebut dan bertukar informari routing antar router. Terdapat 3 kategori tentang
   algoritma dinamik, yaitu : oDistance Vector

oLink State

oHybrid

4. Algoritma routing adalah bagian algoritma dari perangkat lunak network layer yang bertanggung jawab untuk menentukan jalur mana yang menjadi jalur transmisi paket.

5. Untuk dapat melakukan perutean, suatu router, atau entitas apapun yang membangun routing, melakukan beberapa langkah berikut ini:

· Mengetahui Alamat tujuan – Ke tujuan (alamat) mana sesuatu yang dirutekan dikirim?

· Mengenali sumber-sumber informasi perutean – Dari sumber-sumber (router-router lain) mana saja suatu router dapat mempelajari jalur-jalur menuju tujuan?

· Menemukan rute-rute – Jalur-jalur atau rute-rute mana saja yang mungkin dapat
dilalui untuk mencapai alamat tujuan?

· Memilih jalur atau rute – Memilih jalur atau rute terbaik untuk menuju alamat tujuan yang dimaksud.

· Memelihara dan memverifikasi informasi routing – Apakah jalur-jalur ke tujuan yang telah diketahui masih berlaku dan benar?

6. kekurangan dan kelebihan static routing:

– dengan menggunakan next hop

           (+) dapat mencegah trjadinya eror dalam meneruskan paket ke router tujuan apabila
     routeryang akan meneruskan paket memiliki link yang terhubung dengan banyak
     router.itu disebabkan karena router telah mengetahui next hop, yaitu ip address
    router tujuan

           (–) static routing yang menggunakan next hop akan mengalami multiple lookup atau
    lookup yg berulang. lookup yg pertama yang akan dilakukan adalah mencari
    network tujuan,setelah itu akan kembali melakukan proses lookup untuk mencari
    interface mana yang digunakan untuk menjangkau next hopnya.

7. kekurangan dan kelebihan static routing: – dengan menggunakan exit interface
(+ ) proses lookup hanya akan terjadi satu kali saja ( single lookup ) karena router akan langsung meneruskan paket ke network tujuan melalui interface yang sesuai pada routing table
(–) kemungkinan akan terjadi eror keteka meneruskan paket. jika link router terhubung dengan banyak router, maka router tidak bisa memutuskan router mana tujuanya karena tidak adany next hop pada tabel routing. karena itulah, akan terjadi eror.

8.      Karakteristik pada dynamic routing:
§ informasi routingnya tidak lagi diberikan oleh orang (manual), melainkan
    diberikan oleh software.
§ apabila salah satu jalur yang ada mengalami gangguan atau kerusakan
     peralatan, maka router akan secara otomatis akan mencari ganti dari jaluryang
    tidak bisa dipakai lagi.
§ menangani jaringan yang lebih kompleks dan luas, atau jaringan yang
    konfigurasinya sering berubah-ubah (koneksi putus-nyambung)
§ jaringannya cerdas (sudah menggunakan komputasi)
§ memerlukan routing protokol untuk membuat table routing dan routing
    protokol ini bisa memakan sumber daya komputer.

9. Kelebihan

· Menggunakan metode Triggered Update

· RIP memiliki timer untuk mengetahui kapan router harus kembali memberikan
informasi routing.

· Jika terjadi perubahan pada jaringan, sementara timer belum habis, router tetap
harus mengirimkan informasi routing karena dipicu oleh perubahan tersebut
(triggered update).

· Mengatur routing menggunakan RIP tidak rumit dan memberikan hasil yang
cukup dapat diterima, terlebih jika jarang terjadi kegagalan link jaringan

Kekurangan

· Jumlah host Terbatas

· RIP tidak memiliki informasi tentang subnet setiap route.

· RIP tidak mendukung Variable Length Subnet Masking (VLSM).

· Ketika pertama kali dijalankan hanya mengetahui cara routing ke dirinya
sendiri (informasi lokal) dan tidak mengetahui topologi jaringan tempatnya
berada.

10. Routing link-state memiliki keunggulan pada jaringan besar karena beberapa alasan berikut:

· Protokol link-state hanya mengirim update dari topologi yang berubah

saja.

· Periode update lebih jarang dibanding protokol distance vector.

· Routing link-state dapat disegmentasi ke dalam hirarki-hirarki area yang

dapat membatasi jangkauan perubahan-perubahan rute.

· Mendukung classless addressing.

· Routing link-state mengirim subnet mask bersama dengan update routing.

REFERENSI

Ketuta Gustini., Tipe IP Routing dan Algoritma IP Routing,

http://www.ketutagustini.com/index.php/daftar-isi/bab-8-protokol-routing/8-2-tipe-ip-routing-dan-algoritma-ip-routing

cara kerja algoritma Routing digunakan pada halaman 1-2