BAB 3 ANALISIS DAN PERANCANGAN Pada bab ini akan dijelaskan mengenai analisis dan perancangan IS-IS routing protokol dalam ATN. Dalam IS-IS protokol, jenis protokol routing yang digunakan adalah protokol link state sesuai spesifikasi yang diberikan oleh ISO 10589 yang merupakan panduan teknis pengimplementasian protokol IS-IS. Analisis yang dibahas mencakup spesifikasi fungsionalitas – fungsionalitas yang akan diimplementasikan untuk membuat IS-IS routing protocol namun difokuskan pada bagian penerapan algoritma shortest path first routing yang dijelaskan pada ISO 10589. Pada tugas akhir ini analisis dan perancangan dilakukan dengan merujuk kepada dokumen standar ISO yang berkaitan.
3.1 Analisis Kebutuhan Protokol Pada ATN, fungsi routing antara IS dengan IS diatur dalam IS-IS routing protocol (IS-IS) dan inter-domain routing protocol (IDRP). Spesifikasi dan deskripsi kebutuhan IS-IS dijelaskan didalam ISO 10589. Secara umum, kebutuhan fungsional untuk IS-IS dibagi menjadi dua kelompok besar, yakni Subnetwork Independent Functions (SIF) dan Subnetwork Dependent Functions (SDF). SDF berhubungan dengan kapabilitas untuk memberikan antarmuka dengan subnetwork dan melibatkan operasi-operasi seperti mendeteksi, membentuk dan mengelola routing adjacency untuk entitas network di dalam routing domain yang dihubungkan melalui berbagai tipe media jaringan. Selain itu SD juga bertugas untuk meneruskan paket data menuju node lain (baik itu ES maupun IS) dengan menggunakan informasi routing yang. Sementara SIF menyediakan kapabilitas untuk melakukan pertukaran dan pemrosesan informasi routing. SIF juga melakukan pertukaran informasi yang berhubungan dengan kontrol antara IS yang bertetangga (adjacent) sesuai hasil validasi dari SDF. Kebutuhan fungsionalitas dalam IS-IS dibagi kedalam dua kelompok: 1. Subnetwork Dependent Functions (SDF) SDF bertanggung jawab untuk memberikan antarmuka dengan berbagai subnetwork dan bertanggung jawab untuk menemukan (discover), membentuk (establish) dan mengelola (maintain) adjacency antar IS III-1
III-2 dalam satu routing domain. SDF bekerjasama dengan protokol ES-IS (ISO 9542) untuk menentukan alamat network layer untuk seluruh pasangan tetangga, baik itu ES ataupun IS. 2. Subnetwork Independent Functions (SIF) Fungsi-fungsi yang didefinisikan didalam SIF ini tidak bergantung kepada subnetwork atau layanan data link tertentu yang berada dibawahnya, kecuali dalam mengenali dua jenis subnetwork, yakni broadcast subnetwork dan general topology subnetwork. SIF menyediakan kemampuan untuk melakukan pertukaran dan pemrosesan informasi routing. SIF juga melakukan pertukaran informasi yang berhubungan dengan kontrol antara IS yang bertetangga (adjacent) sesuai hasil validasi dari SDF. Singkat kata, SIF merupakan routing engine dari IS. Proses pembentukkan adjacency yang dilakukan oleh SDF erat kaitannya dengan ISO 9542 mengenai Routing Exchange Protocol yang bertindak layaknya DHCP pada lingkungan IP1. Oleh karena itu, SDF tidak akan dibahas lebih lanjut pada tugas akhir ini karena sudah berada diluar batasan dari pengerjaan tugas akhir. Pada tugas akhir ini diasumsikan basis data adjacency telah tersedia. 3.1.1
Subnetwork Independent Functions
SIF di dekomposisi menjadi empat modul/proses, yakni: Decision, Update, Forward dan Receive yang ditunjukkan pada Gambar 3.1.
Gambar 3.1 Data Flow Diagram dalam Subnewtork Independent Functions
1
Studi mengenai Routeing Exchange Protocol telah diimplementasikan pada tugas akhir dengan judul
Studi dan Implementasi Routing Exchange Protocol antara End System dan Intermediate System pada Aeronautical Telecommunication Network oleh Iqbal Farabi.
III-3 3.1.1.1 Decision Proses inilah yang menghitung rute-rute ke setiap tujuan didalam routing domain. proses decision menciptakan basis data forwarding dengan menjalankan algoritma SPF yang memanfaatkan basis data link state. Basis data link state ini dikelola oleh proses Update. Sebuah IS menjalankan proses eksekusi SPF yang terpisah untuk Level 1 dan Level 2. Hasil dari proses Decision ini adalah penentuan pasangan adjacency yang disimpan dalam basis data forwarding yang nantinya digunakan oleh Proses Forward untuk meneruskan NPDU. Menurut ISO 10589, input yang dibutuhkan oleh proses decision adalah: a. Basis data link state, basis data ini merupakan kumpulan informasi dari seluruh LSP terbaru dari semua IS yang diketahui, basis data ini dikelola oleh proses Update. b. Notifikasi Event, ini merupakan sinyal yang diberikan oleh proses Update bahwa terjadi perubahan pada sebuah link didalam domain. Sedangkan output yang dihasilkan adalah: c. Basis data forwarding, basis data yang berisi informasi jalur terpendek ke hop berikutnya. Basis data ini dibuat satu untuk masing-masing routing metric dan satu untuk masing-masing level. Sehingga jika IS mengimplementasikan Level 1 dan 2 dengan tiga macam routing metric, maka akan ada enam basis data forwarding yang dihasilkan. Untuk menentukan nilai jarak antar node didalam proses routing, digunakan suatu ukruan yang dinamakan routing metric. Ada empat jenis routing metric yang didefinisikan didalam ATN. Routing metric ini berhubungan dengan empat kualitas service (QoS) yang diatur pada ISO 8473. Keempat routing metrik itu adalah: a. Default Metric: ini adalah jenis ukuran yang dimengerti oleh setiap IS dalam domain. Ukuran ini merepresentasikan kapasitas dari sirkuit untuk menangani lalu lintas data. Nilai yang lebih besar mengindikasikan kapasitas yang lebih rendah. b. Delay metric: ukuran ini merepresentasikan delay transit dari sirkuit terkait. Nilai yang lebih besar menunjukkan waktu delay yang lebih lama. Ukuran ini bersifat opsional.
III-4 c. Expense Metric: ukutan ini merepresentasikan monetary cost dari penggunaan sirkut yang terkait. Nilai yang lebih besar mengindikasikan monetary cost yang lebih besar. Ukuran ini bersifat opsional. d. Error Metric: ukuran ini merepresentasikan kemungkinan terjadinya residual error dalam sirkuit terkait. Semakin besar nilainya, semakin besar pula kemungkinan terjadi error. Ukuran ini bersifat opsional. 3.1.1.1.1
Algoritma
Algoritma yang digunakan dalam proses decision ini adalah algoritma shortest path first (SPF). Algoritma dieksekusi secara konkuren dan independent pada setiap IS di dalam routing domain. Proses routing sebuah PDU untuk intra-domain berjalan dengan basis hop-by-hop yang berarti algoritma hanya akan menentukan hop berikutnya yang menuju tujuan dari PDU, bukan keseluruhan jalur. Untuk menjamin agar proses ini berjalan dengan konsisten dan benar untuk seluruh IS dalam routing domain, ada beberapa syarat yang perlu dipenuhi yakni:
Setiap IS dalam routing domain memiliki informasi topologi yang identik.
Setiap IS menggunakan jumlah dan jenis routing metric yang sama.
Ada tiga jenis path yang mungkin dihasilkan dari eksekusi algoritma SPF. Ketiga jenis path tersebut adalah:
Minimum cost path, sebuah jalur dengan jumlah metric minimum.
Equal minimum cost path, beberapa jalur yang memiliki jumlah metric minimum yang sama.
Downstream path, kumpulan jalur yang akan membuat PDU lebih dekat ke tujuan (bukan jalur lengkap sampai ke tujuan).
IS akan mengeksekusi algoritma sebanyak jumlah tetangganya untuk setiap metric sehingga jika keempat metric diimplementasikan, akan terdapat 4 dikali jumlah tetangga eksekusi algoritma SPF. Selain itu, terdapat satu basis data forwarding untuk tiap metric. Algoritma juga akan melakukan pengecekan sebelum mempergunakan informasi adjacency/path melalui dua prinsip yang diatur dalam klausa 7.2.8 pada ISO 10589 yakni tidak boleh menggunakan path yang melalui IS yang mengindikasikan terjadi overload pada basis data LSP-nya dan tidak boleh menggunakan informasi adjacency kecuali kedua IS mencantumkan adjacency tersebut (two-way connectivity check).
III-5 Terdapat dua jenis basis data forwarding yang dihasilkan oleh proses decision, yakni level 1 dan level 2. Namun seperti telah disebutkan sebelumnya, pada tugas akhir ini hanya akan diimplementasikan routing level 1, dengan demikian basis data forwarding level 2 pun tidak akan diimplementasikan. 3.1.1.2 Update Proses Update meng-generate informasi link-state yang local berdasarkan basis data adjacency yang dibangun oleh SDF. Informasi link-state ini disebarkan keseluruh tetangganya dalam bentuk LSP. IS juga menerima informasi link-state yang serupa dari semua tetangganya, menyimpan salinan LSP yang diterima, dan menyebarkan kembali ke tetangga yang lain. IS dalam sebuah area mengelola basis data link state yang identik. Hal ini berarti bahwa sebuah IS dalam area yang sama akan memiliki cara pandang yang sama terhadap topologi areanya yang sangat penting untuk konsistensi routing didalam area tersebut. Karakteristik umum dari proses Update adalah:
LSP di-generate sebagai hasil dari perubahan topologi dan juga di-generate secara berkala.
Level 1 LSP disebarkan di dalam area tapi tidak disebarkan keluar area.
Level 2 LSP disebarkan keseluruh Level 2 IS didalam routing domain.
LSP tidak disebarkan keluar routing domain.
Input yang dibutuhkan oleh proses update adalah:
Basis data Adjacency, dikelola oleh SDF dan berisi pasangan-pasangan tetangga yang ada di area tersebut.
Notifikasi perubahan basis data Adjacency, notifikasi dari SDF bahwa telah terjadi suatu event dalam basis data adjacency (Circuit up, Circuit down, Adjacency Up, Adjacency Down, dan Cost change).
Link State PDU, dari proses Receive bersama dengan keterangan asal PDU.
Sequence Number PDU, diterima dari proses Receive bersama dengan keterangan asal PDU.
Output:
Basis data Link State, berisi informasi tentang informasi status dari suatu link dari semua IS yang diketahui, basis data ini dipakai oleh proses Decision.
III-6
Sinyal kepada Proses Decision karena terjadinya event tertentu. Event- event yang dimaksud adalah: penerimaan LSP dengan informasi yang berbeda dari yang disimpan atau penghapusan LSP dari basis data.
3.1.1.2.1
Pembentukan LSP
Seperti telah dijelaskan pada sub bab sebelumnya, proses Update bertanggung jawab untuk membuat LSP. Tujuan pembentukan LSP ini adalah untuk memberikan informasi kepada IS – IS lain dalam satu area, status adjacency dari IS tersebut dengan tetangga sekitarnya. Proses update akan melakukan pembentukan LSP secara periodik. Proses update membentuk LSP pada saat kadaluarsanya holding time, perubahan basis data adjacency, atau terdapat perubahan pada informasi di dalam LSP. Terdapat dua jenis LSP pada level 1 yakni LSP non-pseudonode dan LSP pseudonode. Perbedaannya hanya terdapat pada bagian option part (CLV) dimana option part dari LSP pseudonode tidak memuat area address. Ukuran buffer penerima LSP berbeda pada tiap IS. Oleh karena itu, pada kasus-kasus tertentu, bisa terjadi ukuran LSP yang dikirim melebih ukuran buffernya. Pada kasus seperti ini LSP dipecah menjadi beberapa fragmen LSP. Kasus seperti ini disebut sebagai multiple LSP atau fragmentasi LSP. Setiap LSP di-set dengan field sourceID yang sama namun memiliki nilai field LSP Number yang berbeda pada setiap LSP. 3.1.1.2.2
Penyebaran LSP
Proses update juga bertanggung jawab menyebarkan LSP ke seluruh entitas jaringan dalam area. Mekanisme dasar yang digunakan adalah flooding seperti yang telah dijelaskan di sub bab 2.2.2.2. flooding menggunakan Sequence Number sebagai mekanisme pengontrolan duplikasi LSP. Dalam proses penyebaran LSP, ada beberapa aturan sebagai berikut:
Level 1 LSP disebarkan ke dalam sirkuit yang minimal memiliki satu buah level 1 adjacency.
Level 2 LSP disebarkan ke dalam sirkuit yang minimal memiliki satu buah Level 2 adjacency
Ketika menyebarkan ke dalam subnetwork broadcast, PDU ditransmisikan ke alamat multi-destination AllL1IS (01-80-C2-00-00-14) untuk level 1 dan AllL2IS
(01-80-C2-00-00-15) untuk level 2.
III-7 Proses pengiriman dan penyebaran LSP dikontrol oleh sebuah flag bernama Send Routeing Message (SRM flag). Setiap LSP diasosiasikan dengan sebuah array SRM flag dengan sebuah index untuk setiap circuit. Jika flag di set maka artinya LSP harus ditransmisikan ke circuit yang sesuai di index.
Gambar 3.2 Ilustrasi Penggunaan SRM dan SSN Flag
Sementara itu, Send Sequence Number (SSN) flag digunakan dalam mekanisme yang lebih kurang sama, namun diperuntukkan bagi pengiriman PSNP ke circuit tertentu. Penggunaan kedua flag ini diilustrasikan pada gambar 3.2 yang menunjukkan bahwa LSP X akan dikirim ke Circuit A, C dan D dan informasi mengenai LSP Y akan dikirimkan ke circuit A dengan menggunakan PSNP. 3.1.1.2.3
Menentukan informasi terbaru
Proses update bertanggung jawab menentukan apakah suatu LSP yang diterima memuat informasi baru, lama atau informasi duplikasi dengan acuan data yang tersimpan di basis data LSP. Penentuan informasi terbaru ini mengacu kepada nilai field sequence number dalam LSP, semakin besar nilai didalam field ini berarti semakin baru info yang ada didalamnya. Contoh kasusnya, jika sebuah LSP yang dibuat oleh sistem sumber S memiliki nilai x pada field sequence number, dan sistem R yang berada didalam domain menyimpan LSP dari S dengan nilai yang lebih kecil dari x, maka R akan mengganti informasi didalam basis data link statenya dengan nilai baru yang diterima. Pada kasus lain dimana R memiliki LSP dari S dengan nilai sequence number lebih besar dari x (misal y) kemudian R menerima LSP lagi dari S dengan sequence number
III-8 x, maka R akan mengirimkan LSP milik S ke S dengan sequence number y. ketika sistem S menerima LSP miliknya dengan sequence number y (yang lebih besar dari yang ada didalam basis data miliknya), S akan meng-generate LSP baru dengan sequence number y+1 dan menyebarkannya. 3.1.1.2.4
Basisdata link state
Basis data ini berisi informasi LSP terbaru dari setiap level 1 IS dan pseudonode (jika ada) di area tersebut. Level 1 LSP berisi daftar link menuju ke IS tempat LSP digenerate. Pada kondisi tertentu, bisa terjadi overload didalam basis data link state sehingga IS tidak bisa menyimpan LSP yang diterima. Ketika hal ini terjadi, sebuah IS perlu melakukan beberapa langkah spesifik untuk memastikan bahwa jika basis data link statenya menjadi inkonsisten, IS lain tidak akan menggunakan dirinya sebagai jalur untuk melakukan forward. Ketika LSP tidak bisa disimpan, LSP diabaikan dan IS memasuki status “waiting” selama waitingTime. Kemudian LSP membuat LSP nya sendiri dengan LSP Number di set ke 0 dan LSP Database Overload Bit di set ke 1. Ini dilakukan untuk mencegah IS ini dijadikan jalur forwarding oleh IS lain. Ketika berada didalam status “waiting”: Jika LSP tidak bisa disimpan, maka PDU diabaikan dan waitingTime diulang dari awal. IS melanjutkan proses decision dan forward seperti pada kondisi normal. Ketika waitingTime kadaluarsa, maka IS melakukan
aksi-aksi
berikut:
Menginisiasi
event
lSPL1DatabaseOverlosad
(recovered), mengembalikan bit LSP Database Overload ke 0 dan menyebarkan LSP tersebut dengan nilai LSP Number 0. Setelah itu Set atribut l1State menjadi “On” kemudian lanjutkan operasi normal. 3.1.1.3 Forward Proses forward bertanggung jawab untuk mengirimkan PDU, baik yang berasal dari IS itu sendiri ataupun meneruskan PDU yang berasal dari entitas network lainnya. Input pada proses ini adalah:
PDU dari Proses Update,
PDU dari Receive Process, ini adalah data PDU
Basis data Forwarding, basis data yang berisi informasi jalur terpendek ke hop berikutnya. Basis data ini dibuat satu untuk masing-masing routing metric.
III-9 Sementara itu, output dari proses ini adalah proses pengiriman PDU itu sendiri. Dalam proses meneruskan PDU ke IS lain, terdapat panduan umum. Misal DEST adalah alamat tujuan dari PDU yang akan diteruskan, maka proses forwarding dilakukan dengan cara mengecek area address dari DEST didalam area address yang ada didalam IS. Jika ada yang cocok, maka cari tetangga yang menuju ke DEST di dalam Level 1 basisdata forwarding. Jika area address tidak ditemukan, maka cari adjacency yang menuju jalur ke IS Level 2 terdekat agar PDU tujuan PDU bisa dicari di area lain. 3.1.1.4 Receive Proses Receive merupakan proses yang menerima semua input ke dalam mesin routing dan meneruskan informasi-informasi tersebut sesuai tujuannya. Proses Receive meneruskan informasi dari sumber-sumber berikut: -
PDU dengan Network Layer Protocol Identifer diset ke IntraDomainRouteingPD.
-
Informasi konfigurasi dari mesin protocol ISO 9542.
-
Data PDU dari mesin protocol ISO 8473.
Proses Receive akan melakukan operasi berikut pada setiap penerimaan PDU: -
Jika LSP, teruskan ke proses Update.
-
Jika IIH PDU, teruskan ke SDF .
-
Jika NPDU data atau error report untuk IS lain, teruskan ke proses forward.
-
Selain itu, abaikan PDU.
3.2 Analisis Algoritma Routing Shortest Path First Seperti telah dijelaskan pada Bab 2, algoritma perutean Shortest Path First merupakan salah satu jenis protokol routing yang bersifat adaptif dan tersebar. Dalam proses komputasinya, algoritma ini menggunakan basisdata Link State sebagai input dan menghasilkan basisdata Forwarding seperti diilustrasikan dalam gambar 3.3.
Gambar 3.3 Ilustrasi Algoritma Shortest Path First
III-10
Komponen-komponen dari algoritma SPF adalah: PATHS: merepresentasikan graf berarah asiklik yang berisi jalur-jalur terpendek dari sistem yang melakukan proses komputasi (misalnya sistem S). Data dalam PATHS disimpan dalam bentuk triplet dengan bentuk
, dimana: N:
merupakan system ID dan memiliki panjang IDLength+1. Untuk N merupakan non-pseudonode, octet terakhir berisi 0 dan untuk N yang pseudonode, octet terakhir merupakan pseudonode ID.
d(N) :
merupakan jarak N dari S.
{Adj(N)}: merupakan himpunan dari adjacency yang valid dan bisa digunakan oleh S untuk melakukan forward ke N. Jika suatu system telah ditempatkan didalam PATHS, maka path yang tersedia didalam Adj(N) sudah terjamin sebagai jalur terpendek. TENT: sama dengan PATHS, berisi triplet namun jarak yang ada didalamnya belum tentu merupakan jalur yang terpendek. Misalnya terdapat triplet , triplet ini tidak akan dapat dimasukkan kedalam list PATHS kecuali sudah terbukti bahwa tidak ada jalur yang lebih pendek dari x menuju N. Algoritma memulai operasi dengan mengisi PATHS dengan tiplet dirinya sendiri karena tidak ada path yang lebih pendek untuk menuju S selain S itu sendiri. Kemudian TENT diisi dengan seluruh node dari basis data adjacency lokal. Karena sistem yang dimasukkan ke PATHS sudah dipastikan merupakan jalur terpendek, maka setiap suatu sistem misalnya N dimasukkan ke PATHS, setiap tetangga N (misal M) dihitung sebagai jalur baru menuju M. Jika <M,*,*> sudah terdapat didalam PATHS, maka jalur baru (jarak N + N ke M) sudah pasti lebih panjang sehingga diabaikan. Jika <M,*,*> berada didalam TENT dan jalur baru ini lebih pendek, maka jalur lama dihapus dan diganti dengan jalur yang baru. Jika jalur baru memiliki jarak yang sama maka himpunan kemungkinan {Adj(M)} ditambah dengan himpunan kemungkinan dari jalur baru tersebut. Jika M tidak ada didalam TENT, maka <M,*,*> ditambahkan ke TENT. Berikutnya, algoritma mencari triplet didalam TENT dengan x yang terkecil. Setelah ditemukan, kita tempatkan N ke dalam PATHS. Kita tahu bahwa tidak ada jalur yang lebih pendek untuk menuju N dari x karena seluruh jalur
III-11 menuju sistem yang ada di PATHS telah dihitung dan jalur menuju sistem di TENT akan lebih besar dari x karena x merupakan nilai minimum di TENT. Ketika TENT kosong, maka PATHS sudah lengkap. 3.2.1
Perancangan Struktur Data Shortest Path First
Rancangan struktur data yang digunakan untuk menjalankan algoritma SPF terdiri dari rancangan list Unknown, TENT dan PATHS terdapat pada kode 3.1. // Unknown List Element struct unknown{ struct nsap_address *source; struct nsap_address *dest; int cost; struct unknown *next; }; struct unknown_list{ struct unknown *head; struct unknown *curr; int num_rec; }; // TENT List Element struct tent{ struct nsap_address *source; struct nsap_address *dest; int cost; int cost_to_root; struct tent *next; }; struct tent_list{ struct tent *head; struct tent *curr; int num_rec; }; // PATH List Element struct paths { struct nsap_address *dest; struct nsap_address *next_hop; int cost_to_root; struct paths *next; }; struct path_list{ struct paths *head; struct paths *curr; int num_rec; }; Kode 3.1 Struktur List untuk Algoritma SPF
III-12
3.3 Analisis dan Perancangan Aplikasi Pada tugas akhir ini terdapat satu jenis aplikasi yang dibuat yakni aplikasi IS (router) yang digunakan untuk.melakukan pengujian hasil implementasi algoritma routing dan protokolnya. 3.3.1
Deskripsi Umum Aplikasi IS
Dalam tugas akhir ini, aplikasi IS yang diimplementasikan harus bisa menjalankan fungsi perutean untuk antar IS yang diatur didalam IS-IS untuk level 1. Berdasarkan deskripsi dari kebutuhan fungsional pada subbab 3.1.1 dan klausa 12 dari ISO 10589, aplikasi IS yang dibangun harus mampu untuk memenuhi fungsi-fungsi yang telah dijelaskan didalam subbab 3.1. Untuk melakukan perancangan aplikasi IS, terlebih dahulu didefinisikan Event, Predikat dan Aksi yang mungkin dilakukan oleh aplikasi IS tersebut berdasarkan prakiraan Event-event yang terjadi dalam IS sebenarnya. 3.3.2
Event
Event adalah kejadian yang dapat menjadi pemicu (trigger) untuk terjadinya perubahan state bagi sistem. Berikut adalah daftar dari event – event yang mungkin terjadi pada sistem yang mengimplementasikan IS-IS routing level 1.
Tabel 3.1 Event dalam IS-IS routing level 1
Nama
Deskripsi
WT-end
Waiting time telah kadaluarsa
LSP-end
LSP Interval telah kadaluarsa
LS:L1
Menerima Link State PDU Level 1
LS:L2
Menerima Link State PDU Level 2
CLNP PDU
Menerima CLNP Data PDU
AdjUp
Adjacency Up
AdjDown
Adjacency Down
CtUp
Circuit Up
CtDown
Circuit Down
CoCh
Circuit Cost Change
III-13 3.3.3
Predikat
Predikat merupakan ekspresi boolean dari sebuah state. Saat terjadi sebuah event, sistem kemudian memeriksa predikat – predikat yang terkait dengan event tersebut. Jika hasil evaluasi dari predikat terkait menghasilkan nilai true, set aksi tertentu yang sesuai untuk merespon event yang terjadi dieksekusi. Tabel 3.2 mendeskripsikan predikat – predikat yang ada pada IS-IS routing level 1:
Tabel 3.2 Predikat dalam IS-IS routing level 1
Nama
Deskripsi
Pl1
IS merupakan IS Level 1
Pl2
IS merupakan IS Level 2
Psnq
Nilai Sequence Number dari LSP baru sama
Prlq
Nilai Remaining lifetime dari LSP baru sama
Prlz
Nilai Remaining lifetime dari LSP baru adalah 0
Psng
Nilai Sequence Number dari LSP baru lebih besar
Pcv
Nilai Checksum Valid
Pidq
Nilai ID Length dari PDU yang diterima sama panjang
Pxaa
Maximum Area Address cocok
Psnx
Nilai Sequence Number mencapai nilai maksimum
Ppt
Mendukung Point to Point
Pbc
Mendukung Broadcast subnetwork
Pr
LSP bisa disimpan dalam basis data.
Plsi
LSP Interval berada dalam range waktu yang valid
Pssn
SSN flag di set
Psrm
SRM flag di set
Pdest
IS penerima Data PDU merupakan IS Tujuan
Pexist
LSP ada di basis data
3.3.4
Aksi
Aksi merupakan langkah - langkah yang dapat diambil oleh sebuah sistem. Tidak seluruh aksi bersifat wajib. Beberapa aksi bersifat opsional bergantung pada predikat yang dimiliki sistem saat terjadi sebuah event.
III-14
Tabel 3.3 Aksi yang terdapat dalam IS-IS routing level 1
Nama
Deskripsi
Discard
Membuang PDU
LS
Mengirim LS PDU
LS:Pt
Mengirim LS PDU dalam general topology subnetwork
LS:Bc
Mengirim LS PDU dalam Broadcast subnetwork
LS:Req
Meminta LS PDU
Record
Merekam entry basisdata yang baru
PSN:Req
Meminta PSN PDU
Forward-DT
Melakukan forward terhadap DT PDU
Forward-DT:ES
Melakukan forward terhadap DT PDU ke IS dalam area
Reset:MA
Reset MaxAge
Reset:ZL
Reset ZeroAgeLifeTime
Reset:LST
Reset LSP Interval
Reset:WT
Reset WaitingTime
Reset:SeqNum
Reset Sequence Number kembali menjadi nol
SRM:Clear
Kosongkan SRM flag
SRM:ClearAll
Kosongkan semua SRM flag kecuali yang berkorespondensi
SRM:Set
Set SRM flag
SRM:SetAll
Set Semua SRM flag kecuali yang berkorespondensi
SSN:Set
Set SSN flag
SSN:SetAll
Set Semua SSN flag kecuali yang berkorespondensi
SSN:Clear
Kosongkan SSN flag
SSN:ClearAll
Kosongkan semua SSN flag kecuali yang berkorespondensi
CorrLSP
Notifikasi bahwa LSP yang diterima rusak, tambah counter
MaxSN
IS butuh menaikkan nilai Sequence Number, tapi telah mencapai nilai maksimum, tambah counter.
OLSC
Mengirimkan notifikasi Overload State Change.
IS:On
IS memasuki state On
IS:Wait
IS memasuki state Waiting
III-15 3.3.5
Perancangan Aplikasi IS
Pada perancangan aplikasi IS hanya dibahas mengenai tabel state yang mungkin dimiliki oleh sistem dilengkapi dengan state chart diagram terkait. Adapun tabel state tersebut dapat dilihat pada tabel 3.4 berikut: Tabel 3.4 Tabel State untuk Aplikasi IS
Event
Predikat
Aksi
State Baru Ready
LS:L1
~Pcv
CorrLSP; Discard; LS:Req
~Plt1
Discard
Ready
Psnx
MaxSN; Reset:MA; Reset:ZL;
Ready
Reset:SeqNum Prlq ^ Psnq ^ Pcv
SRM:Clear; Discard
Ready
Prlq ^ Psnq ^ Pcv ^ ~Pbc
SRM:Clear; SSN:Set; Discard
Ready
~Prlq v ~Psnq v ~Pcv ^
Record; SRM:SetAll,
Ready
Psng
SRM:Clear;
~Prlq v ~Psnq v ~Pcv ^
Record; SRM:SetAll,
Psng ^ ~Pbc
SRM:Clear; SSN:Set;
Ready
SSN:ClearAll ~Prlq v ~Psnq v ~Pcv ^
SRM:Set; SSN:Clear
Ready
~Pr
OLSC; LS; IS:Wait
Waiting
LS:L2
~Plt2
Discard
WT-end
~Pr
Reset:WT: OLSC; LS:
Pr
OLCS; LS; IS:On
Ready
LSP-end
~Plsi
LS
Ready
CLNP
~Pdest
Forward-DT
Ready
Pdest
Forward-DT:ES
Ready
AdjUp
-
LS
Ready
AdjDown
-
LS
Ready
CtUp
-
LS
Ready
CtDown
-
LS
Ready
CoCh
-
LS
Ready
~Psng Ready Waiting
III-16 3.3.5.1 State Chart Diagram dari Aplikasi IS State chart yang dihasilkan dari perancangan aplikasi IS berdasarkan event, predikat dan aksi yang mungkin terjadi, terdapat pada gambar 3.4 berikut. Waiting Action Set [~Pr]
Reset:WT
WT-end [Pr]
Up
OLCS
Action Set OLCS
LS
IS:Wait
Ready [~Pdest]
Down
Forward-DT
CLNP PDU [Pdest]
Forward-DT:ES
LSP-end[~Plsi] CtUp AdjUp LS
CoCh AdjDown CtDown Discard
LS:L2[~Plt2]
[~Plt1]
Action Set [~Pcv]
Discard
CorrLSP
LS:Req
Action Set [Psnx] MaxSN
Reset:MA
Reset:ZL
Reset:SeqNum
Action Set [Prlq ^ Psnq ^ Pcv]
SRM:Clear
Discard
Action Set [Prlq ^ Psnq ^ Pcv ^ ~Pbc]
SRM:Clear
Discard
SSN:Set
Action Set [~Prlq v ~Psnq v ~Pcv ^ Psng]
Record
LS:L1
SRM:SetAll
SRM:Clear
Action Set [~Prlq v ~Psnq v ~Pcv ^ ~Psng]
SRM:Set
SSN:Clear
Action Set [~Prlq v ~Psnq v ~Pcv ^ Psng ^ ~Pbc]
Record
SRM:SetAll
SRM:Clear
SSN:Set
Action Set [~Pr]
OLCS
LS
IS:Wait
Gambar 3.4 State Chart Diagram untuk Aplikasi IS
SSN:ClearAll
LS
III-17 3.3.6
Perancangan PDU
Perancangan PDU meliputi perancangan jenis - jenis PDU dan juga perancangan komponen – komponen yang sama (common field) penyusun PDU. Jenis PDU yang dirancang terdapat 4 jenis, yakni: LSP, CSNP, PSNP dan Data PDU. 3.3.6.1 Perancangan Common Header Common Header dirancang sebagai sebuah struktur yang memiliki atribut – atribut yang diatur oleh ISO 10589. Sesuai namanya, field yang ada disini merupakan field yang terdapat pada seluruh PDU dalam IS - IS routing. struct common_header { __u8 nlpid; /* Network layer protocol id */ __u8 len; /* Length indicator */ __u8 pro_id; /* Version / protocl id extension */ __u8 id_len; /* ID Length */ __u8 pdu_type; /* Type */ __u8 ver; /* Version, nilai default 1 (0x01) */ __u8 reserved; /* Reserved part for future use */ __u8 max_aa; /* Maximum Area Address */ }; Kode 3.2 Perancangan Struktur Data Common Header
3.3.6.2 Perancangan Option Part Struktur data yang digunakan untuk options part berupa struct dengan tiga atribut yakni code
yang mengindikasikan kode opsi
yang dipilih, length
yang
mengindikasikan panjang dari options part dan value yang berisi nilai dari opsi yang dipilih. Daftar kode opsi yang mungkin terdapat pada tabel 2.2 sub bab 2.3.5.1 struct option_part { __u8 code; __u8 len; __u8 *value; }; Kode 3.3 Perancangan Struktur Data Option Part
3.3.6.3 Perancangan Link State PDU Struktur data yang digunakan untuk mengimplementasikan LSP dapat dilihat pada Kode 3.6. struct ls_pdu { struct common_header *header; __u8 pdu_len[2];
III-18 __u8 rem_life[2]; __u8 lsp_id[SYS_ID_LEN + 2]; __u8 seq_num[4]; __u8 checksum[2]; __u8 is_type; struct option_part *option; }; Kode 3.4 Struktur Data LS PDU
3.3.6.4 Perancangan ISO 8473 PDU (Data PDU) Terdapat tiga bagian dalam Data PDU yakni fixed part, address part dan data part. Pada bagian data part, dikarenakan bagian tersebut hanya akan digunakan sebagai pengujian proses routing, pada tugas akhir ini bagian ini hanya direpresentasikan sebagai sebuah octet/byte yang akan di isi oleh pesan pendek sebagai penanda. Ketiga bagian tersebut diimplementasikan dalam bentuk struktur data berikut. struct fixed_part { __u8 nlpid; /* Networ layer protocol id */ __u8 len; /* Length indicator */ __u8 pro_id; /* Version / protocl id extension */ __u8 reserved; /* Reserved part for future use */ __u8 type; /* Type */ __u8 holding_time[2]; /* Holding time */ __u8 checksum[2]; /* Checksum */ }; Kode 3.5 Struktur Data Fixed Part dalam Data PDU
struct source_address_part { __u8 sal; struct nsap_address *sa; };
/* Source Address Length */ /* Source Address */
struct destination_address_part { __u8 dal; /* Destination address length */ struct nsap_address *da; /* Destination address */ }; Kode 3.6 Struktur Data Address Part dalam Data PDU
// ISO 8473 Data PDU struct data_pdu{ struct fixed_part *fix; struct source_address_part *source; struct destination_address_part *dest; struct option_part *option; }; Kode 3.7 Struktur Data ISO 8473 PDU / Data PDU
III-19 3.3.7
Perancangan Basis data
Struktur data yang digunakan untuk options part berupa struct dengan tiga atribut yakni code
yang mengindikasikan kode opsi
yang dipilih, length
yang
mengindikasikan panjang dari options part dan value yang berisi nilai dari opsi yang dipilih. Daftar kode opsi yang mungkin terdapat pada tabel 2.2 sub bab 2.3.5.1 3.3.7.1 Adjacency Database Adjacency database atau basis data ketetanggaan merupakan basis data yang digunakan oleh proses update untuk menghasilkan LSP yang kemudian digunakan untuk membentuk link state database. Dalam setiap entri basis datanya, terdapat dua field yakni ID sistem dan waktu valid yang tersisa dalam koneksi dengan sistem tersebut. Adjacency database dibentuk oleh subnetwork dependent functions sehingga pada tugas akhir ini basis data ini diasumsikan telah tersedia. // Adjacency Table Element struct adj_rec { struct nsap_address nsap; __u8 snpa[6]; // system ID int hold_time; // holding time, struct adj_rec *next; int cost; // struct time_t timestamp; }; // Adjacency Table struct adj_db{ struct adj_rec *head; struct adj_rec *tail; struct adj_rec *curr; int num_rec; }; Kode 3.8 Struktur untuk entri dan tabel dalam Adjacency Database
3.3.7.2 Link State Database Basis data ini disimpan didalam IS level 1 dan IS level 2 dan berisi informasi LSP terbaru dari setiap level 1 IS atau pseudonode di area tersebut. Level 1 LSP berisi daftar link menuju ke IS tempat LSP di-generate. Berikut ini adalah pseudocode untuk record dalam link state database.
III-20 // Link State Table Element struct ls_rec { __u8 addr[6]; __u8 type; __u32 seq_num; __u16 lsp_age; int SSN[MAX_CIRCUIT]; int SRM[MAX_CIRCUIT]; struct ls_pdu *lsp; struct ls_rec *next; time_t timestamp; };
// ID of LSP originator // wether IS level 1 or 2 // Sequence Number // Remaining Lifetime // SSN Flag // SRM Flag // The received LSP
// Link State Table struct ls_db{ struct ls_rec *head; struct ls_rec *curr; int num_rec; }; Kode 3.9 Struktur untuk elemen dan tabel dalam link state database
3.3.7.3 Forwarding Database Basis data ini digunakan untuk menentukan kemana PDU akan diteruskan jika sistem tujuan ada didalam area ini. Level 1 IS membutuhkan satu informasi tambahan yakni informasi mengenai level 2 IS terdekat. Oleh karena itu, basis data ini juga menunjukkan bagaimana cara mencapai IS level 2 di dalam area jika tujuan tidak terdapat di area tersebut. Berikut adalah skema basisdata forwarding level 1. // Forward Table Element struct forward_rec{ __u8 adr[6]; // idLength octet ID of destination __u8 splits[MAX_PATH_SPLIT]; __u8 next_hop[MAX_PATH_SPLIT]; }; // Forward Table struct forward_db{ struct forward_rec *head; struct forward_rec *curr; int num_rec; }; Kode 3.10 Struktur untuk elemen dan tabel dalam forwarding database
Pada skema diatas, jumlah next_hop dibatasi sebanyak MAX_PATH_SPLIT, parameter ini digunakan untuk membatasi jumlah path ke hop berikutnya. Jika path menuju sistem A melebihi MAX_PATH_SPLIT maka beberapa path akan di buang hingga mencapai nilai MAX_PATH_SPLIT. Pengurangan path ini mengacu kepada beberapa nilai seperti jumlah jarak (metric sum), tipe adjacency (adjacency type), neighbor ID, dan circuit ID.
