Beranda > Routing TCP/IP Volume 1 > Protokol Routing Link State

Protokol Routing Link State

Protokol routing link state, kadang disebut juga sebagai protokol shortest path first atau protokol database, dibuat dengan algoritma jalur terpendek Dijkstra. Beberapa contoh protokol routing link state antara lain

  • Open Shortest Path First (OSPF) untuk IP
  • The ISO’s Intermediate System-to-Intermediate System (IS-IS) for CLNS and IP
  • DEC’s DNA Phase V
  • Novell’s NetWare Link Services Protocol (NLSP)

Meskipun protokol link-state dianggap lebih kompleks daripada protokol distance vector, tetapi sebenarnya dasar-dasar fungsinya tidak begitu kompleks:

  1. Setiap router menjalin relasi ketetanggaan (adjacency) dengan setiap neighbornya.
  2. Setiap router mengirimkan unit data yang disebut Link State Advertisement (LSA) kepada setiap neighbornya. LSA mendaftar setiap link yang dimiliki oleh router, dan untuk setiap link dicantumkan juga informasi link tersebut, status, metric dari interface router pada link, dan setiap neighbor yang terhubung pada link tersebut. Setiap neighbor yang menerima advertisement ini (LSA) akan memforward LSA tersebut kepada neighbor masing-masing.
  3. Setiap router menyimpan kopi dari semua LSA yang diterima dalam satu database. Jika semua berjalan dengan baik, seharusnya database pada semua router adalah identik satu sama lain.
  4. Database topologi yang lengkap, disebut juga link state database, digunakan oleh algoritma Dijkstra untuk menghasilkan graph (gambaran) network yang menunjukkan jalur terpendek menuju setiap router. Protokol link state dapat mengecek link state database untuk mencari subnet-subnet apa saja yang terhubung pada setiap router, dan memasukkan informasi ini kedalam tabel routing.

Neighbors

Pencarian router-router tetangga (neighbor discovery) adalah langkah pertama untuk mengoperasikan lingkungan link state. Untuk menjaga status hubungan dengan neighbor, digunakanlah protokol Hello. Protokol ini akan mendefinisikan format paket Hello dan prosedur untuk saling bertukar paket dan juga memproses informasi yang terdapat pada paket.

Minimal, paket hello akan berisi router ID (RID) dan address dari network yang akan dikirimi paket hello. Router ID adalah sesuatu yang digunakan untuk membedakan router dengan router-router lain, misalnya, IP address dari salah satu interface yang dimiliki. Field pada paket juga dapat berisi informasi subnet mask, Hello interval, periode maximum yang dibutuhkan sebuah router untuk menunggu paket hello dari neighbor sebelum menganggap neighbor tersebut mati, tipe circuit, dan tanda-tanda yang lain untuk membangun status adjacency (status bersebelahan).

Ketika 2 router telah menemukan satu sama lain sebagai sebuah neighbor, mereka akan mensinkronisasikan database mereka dimana mereka saling bertukar dan memverifikasi informasi database sampai database yang dimiliki masing-masing menjadi identik. Untuk melakukan hal ini, neighbor-neighbor harus bersebelahan (berstatus adjacent) dan harus bersepakat pada beberapa hal seperti parameter-parameter protokol misal timer dan lainnya. Dengan menggunakan paket Hello untuk menjalin adjacency, protokol link state dapat saling bertukar informasi dengan cara yang terkontrol. Bandingkan dengan distance vector yang hanya membroadcast update keluar pada setiap interface yang dikonfigurasi untuk protokol routing.

Selain untuk menjalin adjacency, paket hello juga berfungsi sebagai keepalive untuk memonitor adjacency. Jika paket hello tidak lagi terdengar dari adjacent neighbor dalam waktu yang telah ditentukan, maka neighbor dianggap unreachable dan status adjacency terputus. Biasanya interval periode paket hello adalah 10 detik, dan periode keepalive adalah 4 kalinya.

Link State Flooding

Setelah status adjacency terjalin, router-router akan mulai saling mengirimkan LSA masing-masing. Advertisement akan dikirimkan kepada semua neighbor (flooding). Dan pada gilirannya, setiap LSA yang diterima oleh router akan dikopi dan diforwardkan lagi kepada setiap neighbor masing-masing kecuali neighbor yang mengirimkan LSA tersebut. Proses ini adalah salah satu keuntungan protokol link state atas distance vector. LSA diforwardkan dengan segera, sedangkan protokol distance harus menjalankan algoritmanya, kemudian mengupdate tabel routing sebelum dapat memforwardkan update routing, walaupun itu triggered update. Hasilnya, protokol link state membutuhkan waktu convergence yang lebih singkat daripada distance vector.

2 prosedur yang sangat vital pada proses flooding ini adalah : sequencing dan aging.

Sequence Numbers

Kesulitan yang dialami pada proses flooding adalah ketika semua router telah menerima semua LSA, maka proses flooding harus dihentikan. Sebuah nilai time-to-live dalam paket dapat saja di andalkan untuk mengakhiri proses flooding, tetapi hal ini kurang effisien karena LSA akan terus bergentayangan dalam network sebelum time-to-live berakhir. Misalkan network dalam gambar berikut, subnet 172.22.4.0 pada router A mengalami kegagalan, dan A mem-flood sebuah LSA pada neighbor B dan D,  memberitahukan status link yang gagal. B dan D kemudian akan mem-flood hal tersebut pada semua neighbor mereka masing-masing, dan begitu seterusnya.

1-sequencenumber-lsa1

Mari kita lihat yang terjadi pada Router C. sebuah LSA diterima dari Router B pada sat t1, kemudian dimasukkan dalam database topologi C, dan kemudian diforwardkan ke Router F. Pada beberapa waktu kemudian t3, duplikasi yang lain dari LSA yang sama diterima Router C dari jalur yang lebih panjang A-D-E-F-C. Router C yang menerimanya mengetahui bahwa LSA yang barusan diterima sudah ada dalam database; pertanyaannya adalah, haruskah C memforward LSA yang baru diterima ke Router B? jawabannya adalah tidak, karena B telah menerima advertisement tersebut. Router C mengetahui hal ini karena LSA yang diterima dari Router  F memiliki nomor urut (sequence number) yang sama dengan LSA yang diterima lebih awal dari Router B.

Ketika Router A mengirim keluar LSA, Router A akan menyertakan sequence number yang identik untuk setiap duplikat yang dikirim. Sequence number ini akan disimpan dalam database topologi router bersamaan dengan LSA lainnya; saat router menerima LSA yang sudah berada dalam database dan ternyata memiliki sequence number yang sama, maka LSA tersebut akan diabaikan. Jika informasi LSA yang sama tersebut memiliki sequence number yang lebih besar, maka LSA yang baru beserta sequence number-nya akan dimasukkan kedalam database dan LSA akan di flood ke semua neighbor. Dengan cara ini, flooding akan berkurang saat semua router telah menerima duplikat dari LSA yang paling baru.

Karena sequence number diletakkan pada field dalam LSA, maka angka tersebut harus memiliki batas maksimum. Apa yang terjadi saat sequence number mencapai nilai maksimum?

Linear Sequence Number Spaces

Salah satu pendekatannya adalah dengan menggunakan linear sequence number space (spasi linear sequence number) yang cukup besar sehingga batas maksimum tidak akan pernah dicapai. Misalnya, jika menggunakan field 32-bit, maka akan ada spasi sebesar 232=4,294,967,296 sequence number yang tersedia mulai dari 0. Meskipun router membuat paket link state setiap 10 detik, akan membutuhkan waktu 1361 tahun untuk menghabiskan persediaan sequence number; beberapa router memang diharapkan agar beroperasi tanpa reboot dalam waktu yang sangat lama.

Sayangnya, pada dunia yang tidak sempurna ini, sering terjadi kegagalan fungsi. Jika proses routing link state kehabisan sequence number, maka router harus mematikan dirinya sendiri dan tetap dalam keadaan down yang cukup lama agar semua LSAnya expire dalam database untuk kemudian memulai lagi sequence number dari nilai terkecil.

Terdapat masalah lain saat router restart. Jika Router A restart, maka kemungkinan Router A tidak tahu sequence number terakhir yang ia gunakan dan harus memulai lagi, misal dari 0. Tetapi jika neighbornya masih memiliki sequence number Router A sebelumnya didalam database, maka sequence number yang lebih rendah akan dianggap sebagai sequence number yang telah usang dan akan diabaikan. Sekali lagi, proses routing harus tetap down sampai semua LSA expire dalam network. Dengan maximum age yang bisa saja selama 1 jam, maka solusi ini kurang effektif.

Solusi yang lebih baik adalah dengan menambahkan peraturan baru dalam proses flooding: jika sebuah router yang baru saja restart mengirimkan LSA pada neighbor dengan sequence number yang nampak lebih tua dari sequence number yang tersimpan dalam database, maka neighbor akan mengirimkan LSA yang sudah tersimpan beserta sequence numbernya kembali kepada router yang baru restart tersebut. Dengan begitu router yang baru restart akan mengetahui sequence number yang terakhir kali dia gunakan sebelum restart dan kemudian dapat menyesuaikan.

Akan tetapi perlu diperhatikan disini, bahwa sequence number yang terakhir kali dipakai bukanlah sequence number yang mendekati maximum, jika tidak, router yang barusan restart akan harus restart kembali. Sebuah peraturan harus digunakan untuk membatasi lompatan sequence number yang bisa digunakan oleh router, misalnya, sequence number tidak boleh meningkat lebih dari setengah dari total spasi sequence number.

IS-IS menggunakan spasi linear sequence number sebesar 32-bit.

Aging

Format LSA harus menyertakan field yang berisi umur (age) advertisement. Ketika LSA pertama dibuat, router memberikan nilai 1 pada field ini. Seiring dengan paket di flood kedalam network, setiap router akan menaikkan  nilai age advertisement ini.

Proses ini menambah lapisan lain kehandalan proses flooding. Protokol mendefinisikan nilai maximum age difference (MaxAgeDiff) untuk network. Sebuah router mungkin saja menerima lebih dari satu duplikat kopi dari LSA yang sama dengan sequence number yang sama tetapi memiliki nilai age yang berbeda. Jika perbedaan nilai age ini lebih kecil dari nilai MaxAgeDiff, maka diasumsikan bahwa perbedaan itu terjadi karena network latency yang normal; LSA yang sudah berada dalam database akan dipertahankan dan LSA yang baru datang dengan age yang lebih besar tidak akan di flood. Jika perbadaan nilai age ini lebih besar dari nilai MaxAgeDiff, maka diasumsikan telah terjadi anomali/keganjilan dalam network sehingga LSA dikirimkan tanpa dinaikkan nilai sequence numbernya. Dalam kasus ini, maka LSA yang baru akan disimpan, dan paket akan di flood. Biasanya nilai MaxAgeDiff ini adalah 25 menit (dipakai oleh OSPF).

Umur (age) sebuah LSA akan terus bertambah selama berada dalam link state database. Jika nilai age dari link state yang tersimpan terus bertambah sampai pada nilai maximum (MaxAge) yang didefinisikan oleh protokol routing, maka LSA akan di flood ke semua neighbor dan akan dihapus dari database.

Jika sebuah LSA akan dihapus dari database ketika mencapai MaxAge, maka harus ada mekanisme untuk memvalidasi LSA secara periodik dan me-reset timer sebelum mencapai nilai MaxAge. Sebuah timer Link State Refresh Time (LSRefreshTime) dibuat, jika timer ini berakhir, maka router akan mem-flood LSA yang baru pada semua neighbor yang kemudian akan mereset nilai age menjadi nilai age yang baru diterima. OSPF mendefinisikan nilai MaxAge sebesar 1 jam dan LSRefreshTime sebesar 30 menit.

Link State Database

Setelah neighbor discovery dan flooding LSA, tugas selanjutnya protokol routing link state adalah membangun link state database. Link state database atau database topology  menyimpan semua LSA dalam bentuk rangkaian rekaman. Walaupun sequence number, age dan informasi-informasi lain disertakan didalam LSA, variabel-variabel ini ada terutama untuk me-manage proses flooding. Informasi penting dalam proses penentuan jalur (path) terbaik adalah dengan meng-advertise router ID, network-network yang terhubung langsung (directly connected), dan cost yang berhubungan dengan network-network/ neighbor tersebut. LSA akan menyertakan 2 tipe informasi umum:

  • Informasi link router: mengadvertise neighbor-neighbor yang bersebelahan (adjacency) yang berupa triple (3 buah item Router ID, neighbor ID,dan Cost), dimana cost adalah cost dari link ke neighbor.
  • Informasi network stub: mengadvertise stub subnet (subnet yang tidak memiliki neighbor) yang terhubung langsung pada router yang berupa triple (3 buah item Router ID, Network ID, dan Cost).

Algoritma shortes path first (SPF) akan dijalankan sekali pada informasi link router untuk menetapkan jalur terpendek bagi setiap router, kemudian informasi network stub digunakan untuk menambahkan network-network tersebut pada router. Gambar berikut menunjukkan sebuah network dengan beberapa router dan link-link yang menghubungkan mereka; network stub tidak diperlihatkan agar lebih sederhana. Perhatikan bahwa beberapa link memiliki cost yang berbeda-beda pada setiap ujungnya. Cost berhubungan dengan arah keluar dari outgoing interface. Misalnya, link RB ke RC memiliki cost 1, sedangkan link yang sama memiliki cost sebesar 5 dari arah RC ke RB.

2-linkstatedatabase

Cost sebuah link dihitung dari arah keluar sebuah interface dan tidak harus sama pada semua interface dalam satu link.

Tabel berikut menunjukkan link state database generic untuk network pada gambar diatas, sebuah duplikat link state database ini akan disimpan dalam setiap router. Jika kita perhatikan database ini, maka kita dapat melihat bahwa database ini menggambarkan network secara komplit. Setelah ini barulah mungkin untuk mengkalkulasi sebuah tree (pohon) yang menggambarkan jalur terpendek menuju setiap router dengan menjalankan algoritma SPF.

3-linkstate-cost

Algoritma SPF

Sungguh sangat disayangkan algoritma Dijkstra dikenal pada dunia routing sebagai algoritma shortest path first. Meski begitu, tujuan dari setiap protokol routing adalah untuk mengkalkulasi jalur terpendek.

Berikut adalah sebuah versi dari algoritma Dijkstra yang telah diadaptasi untuk router:

  1. Sebuah router menginisialisasi pohon (tree) database dengan menjadikan dirinya sebagai akar (root). Entri ini menunjukkan router sebagai neighbornya sendiri dengan cost=0.
  2. Semua triple dalam link state database yang menggambarkan link pada neighbors dari router root tersebut akan ditambahkan dalam candidat database.
  3. Cost dari root menuju tiap link dalam candidate database akan dikalkulasi. Link dalam candidate database dengan cost paling rendah dipindahkan kedalam pohon (tree) database. Jika 2 atau lebih memiliki cost yang sama maka akan dipilih salah satu.
  4. Neighbor ID dari link yang baru saja ditambahkan dalam tree database diperiksa. Dengan pengecualian untuk setiap triple yang Neighbor ID nya telah ada pada tree database, triple-triple didalam link state database yang menggambarkan neighbor router tersebut akan ditambahkan dalam candidate database.
  5. Jika entri-entri tetap berada dalam candidate database, kembali ke langkah 3. Jika candidate database kosong, algoritma dihentikan. Saat selesai, satu buah Neighbor ID tunggal dalam tree database menggambarkan semua router dan shortest path tree telah lengkap.

Berikut adalah kemungkinan bentuk shortest parth tree yang dihasilkan dengan menjalankan algoritma pada network diatas.

4-spf-tree2

Area

Area adalah sebuah subset yang terdiri dari beberapa router yang membangun network. Memecah-mecah network menjadi beberapa area adalah solusi dari beberapa isu pada protokol link state berikut:

  • Database yang diperlukan membutuhkan memori yang lebih daripada prokolol distance vector.
  • Algoritma yang kompleks memberikan beban yang lebih pada CPU daripada yang diberikan oleh protokol distance vector.
  • Proses mem-flood paket link state yang kurang baik mempengaruhi bandwidth yang tersedia, terutama pada network yang tidak stabil.

Protokol link state modern dan router-router yang menjalankannya di desain untuk mengurangi effek-effek tersebut, tetapi tetap tidak dapat menghilangkannya. Bayangkan jika terdapat 8000 router dalam network, maka tentu saja hal ini akan sangat mempengaruhi memori, CPU, dan bandwidth.

Dampak seperti ini dapat dikurangi dengan mengimplementasikan konsep area, seperti pada gambar dibawah ini. Ketika sebuah network dibagi-bagi menjadi beberapa area, router-router yang berada dalam satu area hanya perlu mem-flood LSA dalam satu areanya saja dan dengan begitu hanya perlu memanage link state database untuk area tersebut. Semakin kecil database berarti semakin sedikit memori yang dibutuhkan bagi setiap router dan semakin sedikit beban CPU untuk menjalankan algoritma SPF diatas database tersebut. Jika terjadi perubahan topologi, maka flood yang disebabkan olehnya hanya terbatas pada satu area.

5-ospf-area

Router-router yang menghubungkan 2 area (Area Border Router, dalam istilah OSPF) termasuk pada kedua area dan harus memelihara 2 database topologi terpisah. Sebuah router pada 1 area yang ingin mengirimkan paket pada area lain hanya perlu mengetahui letak Area Border Router nya.

  1. Belum ada komentar.
  1. No trackbacks yet.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: