25

BAB IV

LINK STATE

4.1 Pendahuluan

Protokol Link State pertama kali dikembangkan oleh Bolt Beranek dan

Newman pada jaringan ARPANET. Mereka, Bolt dan Newman, menamukan

bahwa protokol Link State memiliki kelebihan daripada protokol Distance Vector

dalam hal metrik, keandalan, bebas dari routing loop dan kecepatan

beradaptasi[9].

Umumnya protokol Link State menggunakan algoritma Dijkstra untuk

perhitungan route. Algoritma Dijkstra disebut juga shortest path first (SPF)

sehingga protokol Link State sering disebut protokol berbasis SPF.

Konsep Link State telah diimplementasikan pada sejumlah protokol

routing di berbagai tipe internetwork seperti protokol OSPF di TCP/IP, protokol

IS-IS di OSI, dan protokol NLSP di Novell’s Netware.

4.2 Algoritma Dijkstra

Algoritma Dijkstra dapat dinyatakan sebagai berikut: Menemukan path-

path terpendek dari suatu titik sumber tertentu ke semua titik yang lain pada

jaringan. Algoritma ini berproses melalui beberapa tahap. Pada tahap ke k, path-

path terpendek ke k titik yang terdekat (yang paling murah biayanya) ke titik

sumber sudah ditentukan. Titik-titik ini berada pada himpunan M. Pada tahap

(k+1), titik di luar himpunan yang merupakan path terdekat ke titik sumber

dimasukkan ke himpunan M. Ketika sebuah titik dimasukkan ke himpunan M,

sekaligus path dari titik tersebut ke titik sumber dapat didefinisikan.

Algoritma Dijkstra ini terdiri dari 3 langkah. Langkah 2 dan 3 terus

diulang sampai M=N. Langkah-langkah tersebut adalah sebgai berikut:

1. Inisialisasi

Pada tahap inisialisasi, himpunan titik-titik yang dimasukkan pada

algoritma hanya terdiri dari titik sumber.

26

Biaya-biaya path inisial ke titik-titik berdekatan (neighboring nodes)

merupakan biaya-biaya link.

2. Mendapatkan titik yang berdekatan di luar M yang memiliki path dari titik

dengan biaya termurah dan memasukkan titik tersebut ke himpunan M.

3. Memperbaharui path-path dengan biaya terkecil.

Berikut ini adalah flowchart algoritma Dijkstra:

start

Masukkan

data

topologi

jaringan

Bentuk tabel

routing awal

Tukarkan tabel

routing dengan

tabel routing milik

tetangganya

Bandingkan tiap entry

tabel tetangga dengan

entry tabel miliknya

Entry sudah ada

Bandingkan biaya

entry tersebut

dengan biaya

entry miliknya

Biaya entry

tersebut lebih kecilUpdate entry table

Proses

konvergen

end

yaya

ya

tidak

Masukkan entry

ke dalam tabel

routing miliknya

tidak

Gambar 4.1 Algoritma Dijkstra

27

4.3 Dasar-Dasar Routing Link State

4.3.1 Database Link State dan LSAs

Setiap protokol Link State memiliki database yang disebut database Link

State atau topological database. Dalam satu routing domain setiap router memiliki

database yang sama. Database ini berisikan informasi tentang topologi jaringan

dan bagaimana router-router dalam satu routing domain saling dihubungkan.

Database Link State merupakan komponen utama pada sebuah routing Link State.

Komponen utama lainnya adalah link-state advertisement atau LSAs. Setiap

router harus menghasilkan sebuah LSA yang menggambarkan kondisi link yang

dimiliki router tersebut. Kemudian LSA ini didistribusikan ke seluruh router pada

satu routing domain.

Secara umum sebuah LSA mengandung:

Identitas router

Kondisi link operasional dari router

Biaya setiap link operasional

Identitas segmen jaringan atar router yang terhubung ke setiap link

Sebuah indikasi untuk aplikasi yang ada pada router

Field-field lain yang biasanya ada di LSA antara lain:

Sequence number, ketika terdapat beberapa paket LSA pada satu routing domain

secara simultans maka sequence number digunakan untuk menentukan paket

mana yang paling up-to date.

Age of the LSA, field ini digunakan untuk menunjukkan kapan sebuah LSA yang

kadaluwarsa dihilangkan. Field ini juga digunakan untuk menunjukkan kapan

sebuah router harus mengirim kembali LSAnya untuk kepentingan kekokohan

(robustness).

Checksum of advertisement’s contents, field ini dapat digunakan untuk mencegah

dari kerusakan data, baik ketika flooding maupun ketika LSA yang disimpan di

database Link State.

28

4.3.2 Pertukaran Tabel Routing

Pertukaran tabel routing di protokol Link State sedikit lebih kompleks

daripada di protokol distance vector. Pertukaran tabel routing tersebut dapat

dijalaskan sebagai berikut:

1. Proses pendistribusian LSAs ke seluruh router pada routing domain. Proses

ini disebut juga flooding. Pada saat flooding, setiap router penerima LSA

pada satu interface akan mengirim LSA tersebut keluar dari semua interface

kecuali interface yang digunakan untuk menerima LSA tersebut. Pertukaran

LSAs ini dimulai dari router-router yang berdekatan.

2. Setiap router membangun database Link State yang terdiri dari LSAs yang

didapat dari router-router pada saat flooding.

3. Berdasarkan database Link State setiap router membangun topologi logik

sebagai sebuah pohon (tree) dengan dirinya sendiri sebagai akar (root).

Topologi logik ini mengandung seluruh path yang mungkin untuk mencapai

jaringan lain pada jaringan. Dengan menggunakan topologi logik ini sebagai

input, algoritma Dijkstra atau Shortest Path First (SPF) menentukan path

yang paling optimal sesuai dengan metrik yang digunakan.

4. Router mendaftarkan path-path yang paling optimal ke jaringan tujuan pada

tabel routing.

Ilustrasi keterangan di atas dapat dilihat pada gambar 4.1 berikut:

Gambar 4.2 Pertukaran Tabel Routing Link State

29

4.3.3 Propagasi Perubahan Topologi Jaringan

Pada protokol Link State, propagasi perubahan topologi jaringan dilakukan

oleh router yang pertama kali mengetahui perubahan topologi jaringan dengan

mengirimkan informasi update ke router-router lain atau designated router (router

yang didesain untuk menerima perubahan topologi jaringan). Perubahan topologi

jaringan dapat diketahui oleh semua router pada jaringan hampir pada waktu yang

bersamaan.

Untuk mendapatkan konvergensi, setiap router melakukan hal-hal di bawah:

Menyimpan informasi tentang router tetangga: nama router, apakah up

atau down, biaya link router tetangga.

Membuat sebuah paket LSA yang memuat informasi tentang nama router

tetangga dan biaya link, termasuk router tetangga yang baru, perubahan

pada biaya link dan link ke router tetangga yang down.

Mengirim keluar paket LSA ini sehingga semua router menerimanya.

LSA disimpan pada database kemudian dihitung route optimal yang baru

dengan menggunakan algoritma SPF dan diakhiri dengan dilakukan

update pada tabel routing.

4.4 Implementasi Protokol Link State

Protokol Link State telah dijadikan basis bagi beberapa protokol routing

lainnya di berbagai tipe internetwork seperti protokol OSPF di TCP/IP, protokol

IS-IS di OSI, dan protokol NLSP di Novell’s Netware. Pada tugas akhir ini akan

digunakan protokol OSPF untuk jaringan IPTV.

4.4.1 Open Shortest Path First

Open Shortest Path First (OSPF) adalah sebuah protokol terbuka yg telah

dimplementasikan oleh sejumlah vendor jaringan. Jika kita memiliki banyak

router, dan tidak semuanya adalah cisco, maka kita tidak dapat menggunakan

30

EIGRP, jadi pilihan kita tinggal RIP v1, RIP v2, atau OSPF. Jika itu adalah

jaringan besar, maka pilihan kita satu-satunya hanya OSPF atau sesuatu yg

disebut route redistribution-sebuah layanan penerjemah antar-routing protokol.

OSPF diturunkan dari beberapa periset seperti Bolt, Beranek, Newmans.

Dari namanya, protokol routing OSPF memiliki dua karakteristik utama. Pertama

adalah “open” dalam arti spesifikasi protokol routing ini dipublikasikan ke publik.

Spesifikasinya dapat dilihat pada RFC 1583 dan RFC 2538 untuk versi kedua

OSPF. Kedua adalah protokol routing ini menggunakan algoritma SPF atau

algoritma Dijkstra.

4.4.2 Tipe-Tipe Paket OSPF

OSPF menggunakan beberapa tipe paket yang berbeda dalam menjaga

tabel routing maupun database Link State. Keseluruhan tipe paket OSPF

berjumlah lima. Kelima tipe paket tersebut adalah sebagai berikut:

Paket Hello

Paket Database description

Paket Link State Request

Paket Link State Update

Paket Acknowledge

Paket-paket di atas menjamin setiap router OSPF memiliki informasi yang

lengkap tentang topologi jaringan di mana router tersebut berada. Paket berikut

merupakan header 24 byte yang ada pada semua tipe paket.

Version# Type Packet Length

Router

ID

Area

ID

Checksum

Au

Type Authentication Authentication

Gambar 4.3 Shared 24-byte header

31

Version : Versi OSPF yang digunakan

Type : Tipe paket yang digunakan

Packet Length : Total ukuran paket, termasuk panjang

header,dalam satuan byte

Router ID : IP address yang digunakan oleh router untuk

mengidentifikasikan dirinya sendiri

Area ID : Area di mana router berada

Au Type : Tipe autentifikasi

Aunthentication : Field ini berupa password untuk text

Di bawah ini akan dijelaskan field-field yang ada pada kelima paket.

Paket Hello

Version# Type Packet Length

Router

ID

Area

ID

Checksum

Au

Type Authentication Authentication

Network Mask HelloInterval Options

RTR

PRI

RouterDeadInterval DesignatedRouter BDR

Gambar 4.4 Paket Hello

Mask : Mask yang digunakan interface pengirim paket

hello

Hello Interval : Interval waktu antara satu paket Hello dengan

paket Hello berikutnya dari router yang sama

RTR PRI : Tingkat prioritas router pada jaringan

Designated Router : Menunjukkan router pengirim bersifat sebagai

designated router

BackUp Designated Router : Menunjukkan router pengirim bersifat

32

sebagai backup designated router

Neighbor : Optional field, ID router tetangga

Paket Database description

Version# Type Packet Length Router ID Area ID

Checksum

Au

Type Authentication Authentication

Interface MTU Options 0 0 0 0 0 0 1

M MS DD Sequence Number LSA Header

Gambar 4.5 Paket Database description

Interface MTU : Mask yang digunakan interface pengirim paket

Hello

Options : Kapabilitas tambahan yang dapat didukung oleh

router

I-bit : Jika diset On, menunjukkan bahwa paket tersebut

paket DD

M-bit : Jika diset On, menunjukkan bahwa terdapat paket

DD lain yang ikut serta

MS-bit : Jika diset On, menunjukkan bahwa router pengirim

menjadi master selama pertukaran database,

Jika diset Off, router tersebut menjadi slave

DD Sequence Number : Nomor pengurut paket DD

LSA Header : Header Link State Advertisement

Paket Link State Request

Version# Type Packet Length Router ID Area ID

Checksum

Au

Type Authentication Authentication

LS Type Link State ID Advertising Router

Gambar 4.6 Paket Link State Request

33

Field LS Type, Link State ID, dan Advertising Router menunjukkan LSA apa yang

dibutuhkan router.

Paket Link State Update

Version# Type Packet Length Router ID Area ID

Checksum

Au

Type Authentication Authentication

#LSA LSA's

Gambar 4.7 Paket Link State Update

#LSA : Nomor LSA

LSA’s : Link State Advertisements

Paket Acknowledge

Version# Type Packet Length Router ID Area ID

Checksum

Au

Type Authentication Authentication

LSA Headers

Gambar 4.8 Paket Acknowledge

LSA Headers : Menunjukkan LSAs yang di-acknowledge oleh

Router

4.4.3 Area

Di dalam OSPF terdapat beberapa istilah yang perlu dipahami, yaitu :

Area, yaitu letak dimana berada sebuah kumpulan network, router dan host

biasa. Area di sini bukan berarti area fisik.

Backbone, backbone adalah area yang khusus dimana area-area saling

terhubungkan. Seluruh area yang ada, harus terhubung ke backbone.

34

Stub Area, area dimana hanya terdapat satu buah gateway / router, tidak ada

alternatif lainnya.

Gambar 4.9. Area-area dalam OSPF

Sumber : www.h3c.com

Gambar 4.9 merupakan lustrasi dari area-area dalam OSPF. Area 0

merupakan backbone area, sedangkan area 1, area 2, area 3 dan area 4 merupakan

stub area.

4.4.4 Tipe-Tipe Router

Di dalam OSPF terdapat beberapa tipe router, yaitu:

Internal Router, merupakan router yang berada dalam satu area yang sama

dan tidak memiliki koneksi-koneksi dengan area lain. Fungsi dari internal

router adalah memberikan dan menerima informasi dari dan ke dalam suatu

area, serta me-maintain database topologi dan routing table untuk setiap

subnet.

Backbone Router, merupakan router yang berada dalam area backbone dan

memiliki semua informasi topologi dan routing yang ada dalam jaringan

OSPF tersebut.

35

Area Border Router, merupakan router yang bertindak sebagai penghubung

atau perbatasan dan bertugas untuk melakukan penyatuan antara area 0

dengan area-area lainnya. Selain itu, area border router juga bertugas

menyebarkan informasi setiap area yang terkoneksi ke masing-masing

areanya.

Autonomous System Boundary Router, merupakan sekelompok router yang

membentuk jaringan yang masih berada dalam satu hak administrasi, satu

kepemilikan, satu kepentingan, dan dikonfigurasi menggunakan policy yang

sama (dalam satu Autonomous System).

Gambar 4.10 Tipe Router dalam OSPF

Sumber : www.h3c.com

Gambar 4.10 di atas adalah ilustrasi untuk tipe-tipe router yang ada di dalam

OSPF.

36

4.4.5 Proses OSPF

Secara garis besar, proses yang dilakukan routing protokol OSPF mulai dari awal

hingga dapat saling bertukar informasi ada lima langkah. Berikut ini adalah

langkah-langkahnya:

a. Membentuk Adjacency Router

Adjacency router arti harafiahnya adalah router yang bersebelahan atau yang

terdekat. Jadi proses pertama dari router OSPF ini adalah menghubungkan diri

dan saling berkomunikasi dengan para router tetangganya. Untuk dapat

membuka komunikasi, hello protokol akan bekerja dengan mengirimkan hello

packet.

Pada sebuah jaringan broadcast multiaccess seperti ethernet, media broadcast

akan meneruskan paket-paket hello ke seluruh router yang ada dalam jaringan,

sehingga adjacency routernya tidak hanya satu. Proses pembentukan adjacency

akan terus berulang sampai semua router yang ada di dalam jaringan tersebut

menjadi adjacent router.

b. Memilih DR dan BDR (jika diperlukan)

Pada jaringan broadcast multiaccess, DR dan BDR sangatlah diperlukan. DR

dan BDR akan menjadi pusat komunikasi seputar informasi OSPF dalam

jaringan tersebut. Semua paket pesan yang ada dalam proses OSPF akan

disebarkan oleh DR dan BDR. Maka itu, pemilihan DR dan BDR menjadi

proses yang sangat kritikal. Sesuai dengan namanya, BDR merupakan

“shadow” dari DR. Artinya BDR tidak akan digunakan sampai masalah terjadi

pada router DR.

Proses pemilihan DR/BDR tidak lepas dari peran penting Hello packet. Di

dalam Hello packet ada sebuah field berisikan ID dan nilai Priority dari sebuah

router. Semua router yang ada dalam jaringan broadcast multi-access akan

menerima semua Hello dari semua router yang ada dalam jaringan tersebut

pada saat kali pertama OSPF berjalan. Router dengan nilai Priority tertinggi

akan menang dalam pemilihan dan langsung menjadi DR. Router dengan nilai

Priority di urutan kedua akan dipilih menjadi BDR. Status DR dan BDR ini

tidak akan berubah sampai salah satunya tidak dapat berfungsi baik, meskipun

37

ada router lain yang baru bergabung dalam jaringan dengan nilai Priority-nya

lebih tinggi.

Secara default, semua router OSPF akan memiliki nilai Priority 1. Range

Priority ini adalah mulai dari 0 hingga 255. Nilai 0 akan menjamin router

tersebut tidak akan menjadi DR atau BDR, sedangkan nilai 255 menjamin

sebuah router pasti akan menjadi DR. Router ID biasanya akan menjadi sebuah

“tie breaker” jika nilai Priority-nya sama. Jika dua buah router memiliki nilai

Priority yang sama, maka yang menjadi DR dan BDR adalah router dengan

nilai router ID tertinggi dalam jaringan.

Setelah DR dan BDR terpilih, langkah selanjutnya adalah mengumpulkan

seluruh informasi jalur dalam jaringan.

c. Mengumpulkan State-state dalam Jaringan

Setelah terbentuk hubungan antar router-router OSPF, kini saatnya untuk

bertukar informasi mengenai state-state dan jalur-jalur yang ada dalam

jaringan. Pada jaringan yang menggunakan media broadcast multiaccess, DR-

lah yang akan melayani setiap router yang ingin bertukar informasi OSPF

dengannya. DR akan memulai lebih dulu proses pengiriman ini.

Ada sebuah fase yang menangani siapa yang lebih dulu melakukan pengiriman.

Fase ini akan memilih siapa yang akan menjadi master dan siapa yang menjadi

slave dalam proses pengiriman.

Router yang menjadi master akan melakukan pengiriman lebih dahulu,

sedangkan router slave akan mendengarkan lebih dulu. Fase ini disebut dengan

istilah Exstart State. Router master dan slave dipilih berdasarkan router ID

tertinggi dari salah satu router. Ketika sebuah router mengirimkan Hello

packet, router ID masing-masing juga dikirimkan ke router neighbour.

Setelah membandingkan dengan miliknya dan ternyata lebih rendah, maka

router tersebut akan segera terpilih menjadi master dan melakukan pengiriman

lebih dulu ke router slave. Setelah fase Exstart lewat, maka router akan

memasuki fase Exchange. Pada fase ini kedua buah router akan saling

mengirimkan Database description Packet. Isi paket ini adalah ringkasan status

untuk seluruh media yang ada dalam jaringan. Jika router penerimanya belum

38

memiliki informasi yang ada dalam paket Database description, maka router

pengirim akan masuk dalam fase loading state. Fase loading state merupakan

fase di mana sebuah router mulai mengirimkan informasi state secara lengkap

ke router tetangganya.

Setelah loading state selesai, maka router-router yang tergabung dalam OSPF

akan memiliki informasi state yang lengkap dan penuh dalam database

statenya. Fase ini disebut dengan istilah Full state. Sampai fase ini proses awal

OSPF sudah selesai, namun database state tidak bisa digunakan untuk proses

forwarding data. Maka dari itu, router akan memasuki langkah selanjutnya,

yaitu memilih rute-rute terbaik menuju ke suatu lokasi yang ada dalam

database state tersebut.

d. Memilih Rute Terbaik untuk Digunakan

Setelah informasi seluruh jaringan beradadalam database, maka kini saatnya

untuk memilih rute terbaik untuk dimasukkan ke dalam routing table. Untuk

memilih rute-rute terbaik, parameter yang digunakan oleh OSPF adalah Cost.

Metrik Cost biasanya akan menggambarkan seberapa dekat dan cepatnya

sebuah rute.

Nilai Cost didapat dari perhitungan dengan rumus:

Cost of the link = 108 /Bandwidth

Router OSPF akan menghitung semua cost yang ada dan akan menjalankan

algoritma Shortest Path First untuk memilih rute terbaiknya. Setelah selesai,

maka rute tersebut langsung dimasukkan dalam routing table dan siap

digunakan untuk forwarding data.

e. Menjaga Informasi Routing Tetap Update

Ketika sebuah rute sudah masuk ke dalam routing table, router tersebut harus

juga me-maintain state database-nya. Hal ini bertujuan kalau ada sebuah rute

yang sudah tidak valid, maka router harus tahu dan tidak boleh lagi

menggunakannya. Ketika ada perubahan link-state dalam jaringan, OSPF

router akan melakukan flooding terhadap perubahan ini. Tujuannya adalah agar

seluruh router dalam jaringan mengetahui perubahan tersebut. Melihat proses

39

terjadinya pertukaran informasi di atas, dapat diprediksi bahwa OSPF

merupakan sebuah routing protokol yang kompleks dan rumit.

Namun di balik kerumitannya tersebut ada sebuah kehebatan yang luar biasa.

Seluruh informasi state yang ditampung dapat membuat rute terbaik pasti

terpilih dengan benar. Selain itu dengan konsep hirarki, dapat membatasi

ukuran link-state databasenya, sehingga tidak terlalu besar. Artinya proses

CPU juga menjadi lebih ringan.