RANDOM LINEAR NETWORK CODING UNTUK PENGIRIMAN PAKET YANG HANDAL DI NETWORK Reza Zulfikar Ruslam

RANDOM LINEAR NETWORK CODING UNTUK PENGIRIMAN PAKET YANG HANDAL DI NETWORK Reza Zulfikar Ruslam – 2205100060 Email : [email protected] Bidang Studi Telekomunikasi Multimedia Jurusan Teknik Elektro-FTI, Institut Teknologi Sepuluh Nopember (ITS) Kampus ITS, Keputih – Sukolilo, Surabaya 60111 Abstrak – Dalam sebuah network, dibutuhkan node yang memiliki fungsi sebagai penghubung antara terminal satu dan terminal lain, node yang dimaksud bisa berupa computer, laptop, router, switch, dan hub. Saat hubungan point to multipoint terjadi, node tengah mendapat banyak masukan sehingga node akan membentuk paket masukan hasil kombinasi random linear di memori [1], pada strategi ini node tengah melakukan coding tambahan tapi tidak melakukan decoding, node harus menunggu paket injeksi sebelum mengirimkan paket. Sebuah skema random linear network coding untuk pengiriman paket yang handal di network, skema ini mempunyai teknik menyimpan paket di dalam memori dan setiap saat memiliki kesempatan untuk melakukan transmisi, paket-paket yang masuk ke dalam node membentuk paket tercoding dengan kombinasi random linear di memori. Paket yang telah terkombinasi ini yang akan dikirim ke node selanjutnya. Skema ini digunakan untuk permasalahan multicast terhadap network paket kabel lossless. Random linear network coding memiliki kemampuan menarik, saat menyebarkan atau mengirimkan informasi ke multicast grup tidak membutuhkan koordinasi antar node, dapat beroperasi tanpa rate, dan dapat dijalankan indefinitely hingga decoding berhasil. Kata kunci : Network coding, multicast, Random linear network coding, packet Networks I.

PENDAHULUAN Multicast adalah sebuah teknik di mana sebuah data dikirimkan melalui network ke banyak komputer yang tergabung dalam sebuah grup yang disebut multicast group. Multicasting merupakan sebuah cara pentrasmisian data secara connectionless (komunikasi dapat terjadi tanpa adanya negosiasi pembuatan koneksi). Multicast merupakan komunikasi one-to-many, point-to-multipoint. Konsep multicast adalah mengirimkan paket data ke banyak titik namun hanya titik-titik yang terdaftar saja, pengiriman ini lebih efisien jika dibandingkan dengan konsep broadcast, namun dapat diterima lebih banyak dibandingkan dengan konsep unicast. Analoginya adalah, pengiriman surat tagihan hutang oleh bank kepada nasabahnya, analogi ini menjelaskan bahwa paket dikirimkan ke alamat yang dikenal saja, mustahil jika suatu bank mengirimkan tagihan hutang ke nasabah bank lain. Beberapa algoritma multicast telah sering digunakan, diantaranya adalah Flooding, Spanning Trees, Reverse Path Broadcasting (RPB), Truncated Reverse Path Broadcasting (TRPB), Steiner Trees. Sebuah algoritma multicast baru dengan teknik sebagai berikut : node menyimpan paket yang diterima ke dalam

Proceeding Seminar Tugas Akhir Jurusan Teknik Elektro FTI-ITS

memori dan setiap saat mempunyai kesempatan transmisi, membentuk paket ter-coding dengan kombinasi random linear dari isi memori. logaritma ini disebut sebagai random linear network coding yang akan digunakan untuk permasalahan multicast terhadap network paket kabel lossless. Algoritma multicast Random linear network coding mencapai kapasitas paket level untuk hubungan single unicast maupun single multicast dan untuk model network baik kabel maupun nirkabel. II. TEORI PENUNJANG 2.1 Network Coding Network coding adalah sebuah skema baru di dalam network untuk memungkinkan node tengah menyimpan, dan menggabungkan data sebelum diteruskan ke sink. Network coding digunakan untuk mempercepat akses distribusi pada network komputer . Kinerja network coding dibandingkan network non network coding lebih cepat dan efesien karena data dikirim secara kombinasi dengan pengkodean dari beberapa source dengan satu kali pengiriman data. Dengan menggunakan network coding diharapkan masalah kecepatan download file, efisiensi dalam distribusi dapat diselesaikan, sehingga pengguna network lebih mudah dalam melakukan akses download file dalam jumlah besar dengan kata lain network coding akan meningkatkan performance sistem pada network. Network coding bekerja berdasarkan Butterfly network dimana pengiriman data dari suatu source atau server menuju ke node (PC) akan membutuhkan waktu yang lebih singkat dibanding kinerja network biasa. Dalam sistem network coding suatu routing multicast yang bekerja pada sistem akan di XOR sehingga membutuhkan jarak yang pendek dalam proses pengiriman data. Gambar 1 network tanpa mengunakan network coding. Pada node w terjadi injeksi paket dari node t dan node u yaitu dan . Paket yang diterima di node w akan dikirimkan duluan ke node x dan setelah terkirim, node w akan mengirim sehingga proses pengiriman akan berlangsung lebih lama. Gambar 2 menggunakan network coding. Pada node w injeksi paket dari node t dan node u akan dikirimkan pada saat yang bersamaan dengan syarat bahwa paket di node t dan paket di node u berbeda. Jika paket dari node t dan node u sama maka paket yang dikirim dari node w hanya 1 paket saja.

Gambar 1 Network tanpa Network Coding

untuk membuat sebuah simpul tidak terakses dari simpul yang lain. Hasilnya adalah, sesuai dengan teori max-flow min-cut. , adalah maximum flow dari suatu graf. Kita juga dapat menentukan sisi yang ingin dihilangkan, ambil setiap sisi dari awal sampai akhir yang terakses dari simpul awal sampai simpul akhir, kemudian hilangkan simpul yang memiliki nilai minimum.

Gambar 2 Network dengan Network Coding 2.2 Dijkstra Pada dasarnya, algoritma ini adalah salah satu bentuk algoritma greedy. Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi negatif dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini sering digunakan pada routing. Algoritma dijkstra mencari lintasan terpendek dalam sejumlah langkah. Untuk setiap simpul pada sumber (source) dalam graf, algoritma ini akan mencari jalur dengan cost minimum antara simpul tersebut dengan simpul lainnya [2]. 2.3 Max–Flow Min–Cut Max-flow min-cut adalah metode untuk mencari maximum flow dan minimum cut. Metode ini digunakan untuk menentukan besarnya kapasitas kanal untuk jalur transmisi data. Selain itu metode ini juga akan menghilangkan beberapa node yang nilai kapasitas kanalnya bernilai kecil dan tidak dipakai untuk melewatkan data [3]. Cut adalah membagi sebuah graf menjadi dua set yang berbeda, misalkan disebut A dan B, dimana A adalah source dan B adalah sink. Nilai Cut adalah nilai yang diperlukan untuk membagi graf tersebut menjadi dua.

Gambar 3 Cut Di Network Perhatikan bahwa total nilai untuk membagi graf tersebut adalah sama atau lebih kecil dari kapasitas setiap sisi. Hal ini menunjukkan bahwa flow maksimum adalah sama atau lebih kecil dari setiap cut dari setiap network. Dari sinilah asal mulai teorema max-flow min cut yang menyatakan bahwa nilai yang dibutuhkan untuk membagi suatu graf menjadi dua adalah sama dengan maximum flownya. Cara penyelesaiannya juga sama dengan cara mencari maksimum flow dari suatu graf. Diberikan sebuah graf terbobot, buang himpunan sisi dengan nilai minimum


Gambar 4 Minimum Cut Di Network 2.4 Extension Field GF(23) Tabel 1 Pemetaaan Elemen Fields Dalam Basis Elemen GF(23) Dengan F(X) = X3+ X+1 Elemen 0

0 0 0 1 0 1 1 1

0 0 1 0 1 1 1 0

0 1 0 0 1 0 1 1

Bin 000 001 010 100 011 110 111 101

Dec 0 1 2 4 3 6 7 5

Setiap elemen 2m dalam finite fields, GF (2m), dapat di Gambarkan sebagai suatu derajat polinom m – 1 atau kurang. Derajat polinom adalah nilai tertinggi orde eksponen. Dengan menunjukkan masing-masing dari unsur-unsur nol GF (2m) sebagai polinomial, ai (X), di mana setidaknya satu dari koefisien m ai (X) adalah nol. 2.5 Reed Solomon Code Sebuah kode Reed solomon (RS) dengan symbol kode nonbinary cyclic codes dengan simbol-simbol yang terdiri dari m-bit berurutan, dimana m adalah bilangan bulat positif yang memiliki nilai lebih besar dari 2. RS (n, k) kode pada m-bit simbol ada untuk semua n dan k dimana 0 < k < n < 2m + 2. Parameter-parameter sebgai berikut [4] :

dimana : adalah jumlah simbol data yang dikodekan : adalah jumlah total kode : adalah simbol kemampuan koreksi kesalahan : adalah jumlah parity symbol

2.5.1 Encoding Kode Reed-Solomon Pada dasarnya terdapat tiga tahap pada proses pegkodean RS secara sistematik, yaitu : Mengalikan data informasi dengan Menentukan pariti p(x) yang didapat melalui Operasi (1) dimana adalah generator polinomial untuk RS dengan simbol dari GF ( ) dengan panjang kode , yaitu

2.

Setelah nilai-nilai σ pada persamaan 6 sudah dapat ditentukan maka terbentuklah persamaan untuk σ(x). Lokasi error dapat diketahui dengan cara mensubstitusikan akar-akar generator polinomial ke dalam variabel x. Lokasi error (β) terjadi pada saat σ(x)=0. Nilai error Setelah lokasi error diketahui, maka nilai error dapat ditentukan dengan menggunakan persamaan

(2) (8) Menggabungkan hasil proses a dan b sehingga diperoleh codeword yang dapat ditulis sebagai (3) 2.5.2 Dekoder Reed-Solomon Pada RS dekoder, codeword yang diterima mempunyai persamaan: (4) di mana : = codeword yang diterima = codeword yang dikirimkan = error akan bernilai sama dengan pada saat codeword yang diterima tidak mengalami error ( . Langkah pertama yang dilakukan dekoder RS untuk mendekodekan data yang diterima, yaitu menghitung sindrom (S). Sindrom didapatkan dengan cara memasukkan akar-akar generator polinomialnya ke dalam codeword yang diterima. Penghitungan sindrom dapat dituliskan seperti pada persamaan 12 (5) Jika sindrom yang dihasilkan sama dengan nol maka codeword yang diterima tidak mengalami error, sedangkan apabila tidak sama dengan nol, maka dapat diartikan bahwa codeword yang diterima mengalami error, sehingga akan dilakukan langkah berikutnya, yaitu: 1. Mencari lokasi error mempunyai persamaan polynomial error locator pada persamaan (6) di mana v menunjukkan error yang terjadi sampai pada lokasi ke Nilai-nilai dari , , …, dapat dicari menggunakan matrik seperti yang terlihat pada persamaan 12, di mana syndrom pertama dilakukan untuk memprediksi syndrom berikutnya.

(7)


2.6 Random linear network coding Sebuah metode baru dalam network coding yaitu random linear network coding. Operasi pengkodean yang mempunyai kemampuan sederhana, node menyimpan paket yang diterima dan saat mempunyai kesempatan transmisi, maka node akan mengirimkan code paket yang dibentuk dari kombinasi random linear dari paket yang tersimpan. Pada strategi ini, node pertengahan melakukan coding tambahan namun tidak men-decode atau menunggu sebuah blok paket sebelum mengirim kode paket. Operasi coding dan decoding memiliki kerumitan polynomial. Pada metode ini node diasumsikan memiliki memori tidak terbatas. Metode ini dapat dimodifikasi sehingga paket yang disimpan ke dalam memori hanya jika global encoding vector mereka linearly independent dari paket-paket yang tersimpan. Modifikasi ini menjaga hasil kita tidak berubah sambil memastikan bahwa node tidak harus menyimpan banyak paket. Node membentuk paket dari kombinasi random linear network coding dari suatu paket didalam memori, Paket yang tersimpan di node membentuk, (9)

(10) (11)

Dimana dipilih berdasarkan distribusi merata pada elemen Finite field. Global encoding vector yang memenuhi,

(12) ditempatkan pada header. merupakan banyak paket yang tersimpan di dalam memori source node. III. PEMODELAN DAN SIMULASI SISTEM 3.1 Pemodelan Sistem Model sistem network coding yang digunakan pada simulasi Tugas Akhir ini dapat dilihat seperti Gambar 6. Simulasi pada tugas akhir ini dibuat untuk menganalisa

berdasarkan distribusi uniform dari element finite field, nilai elemen finite field [ ].

1

4 X1

8

2

3

e2

e1

3

2

Z1

e3

2

3

3

`

Z2

5

4

9

distorsi pada pengiriman media dengan memggunakan skema network coding pada sistem network komputer. Langkah–langkah yang dilakukan berdasarkan Gambar 3.1 adalah sebagai berikut: a. Memodelkan sistem network computer. b. Menentukan jumlah node yang akan digunakan,. Node berjumlah 6 buah, 1 source node, 3 node tengah, dan dengan 2 node penerima. c. Merepresentasikan dengan graf d. Memilih inputan e. Dalam network yang akan disimulasikan digunakan skema multicast, penentuan panjang lintasan sesuai dengan algoritma dijkstra untuk menentukan jalur terpendek. f. Algoritma max flow min cut untuk menentukan maximum flow dalam network. Algoritma ini digunakan untuk menentukan besar lintasan. g. Menentukan GF yang akan digunakan. h. Menkombinasi data dan mengkodekan menggunakan pengkodean Reed solomon untuk dikirim ke node tujuan. i. Pengiriman paket dengan menggunakan skema Random linear network coding. j. Data dikoreksi dan didekodekan pada penerima untuk mengetahui data asli.

6

Gambar 7 Random linear network coding Dari Gambar 7 dapat diperoleh persamaan :

Mulai

Sistem Network

dan merupakan global encoding vector yang ditandai dengan . Data yang ditaruh di header membentuk . Data yang diterima harus berupa bit 101, 010, 011, jika bit yang diterima berbeda maka terjadi error pada pengiriman.

Menentukan banyak node

Representasi dengan graf

Algoritma Dijkstra

Input

Algoritma Max Flow Min Cut

Menentukan panjang lintasan

Penentuan GF

Menentukan besar lintasan Selesai

Selesai

IV. ANALISA DATA DAN PEMBAHASAN 4.1 Analisa Hasil Simulasi Analisa hasil sistem perencanaan dengan menggunakan 6 node. Pengiriman data menggunakan sistem multicast dengan node 5 dan node 6 sebagai penerima atau sink dan node 1 sebagai source. Node 1 akan mengirim data menuju node 5 dan 6. Gambar 8 adalah adalah konfigurasi 6 node yang akan dikirimkan. Node 1

Elemen Finite field Random linier network coding

4

Pengkodean dengan RS Node 2

Data didekodekan 3 8

output

3

Node 3 2

2

Selesai Node 4

Node 5 9

Gambar 6 Diagram Alir Proses Simulasi 3.2 Skema Random linear network coding Pada skema Random linear network coding, data yang dikirimkan berupa bit 101, 010, 011. Galois field yang digunakan adalah GF(8) dengan A(7,3). Nilai dipilih


3

Node 6

Gambar 8 Konfigurasi Graf di Network

Berdasarkan Gambar 8 dapat dicari besarnya flow yang dapat dilewatkan kedalam network dengan memotong jalur yang tidak perlu untuk mendapatkan maksimal flow dan nilai minimum cut, sehingga didapatkan jalur pengiriman data data yang efesien data cepat. Selain menggunakan algoritma dijkstra juga digunakan max–flow min–cut untuk dibandingkan kinerja antara dua sistem tersebut. Pada simulasi yang dihasilkan didapatkan besarnya jarak maksimum flow adalah 2 dan 3.

2

1

4.3 Analisa Pengkodean Reed Solomon Setelah melakukan pencarian jarak lintasan terpendek menggunakan algoritma dijkstra dan nilai maksimum flow dan minimum cut maka data akan dikodekan untuk dikirim menggunakan kode Reed Solomon. Data yang dikirim menggunakan A(7,3) Reed Solomon code dengan menggunakan GF(8), Paket = 101,010,011.

8

2

2

2 3

` 5

4

6

Nilai

kita konversikan ke

berdasarkan Tabel 1

Gambar 9 Max Flow Min Cut dari source node ke node 5

3

1

Polinomial didapatkan dari persamaan 1

2

2

1

Nilai 2

3

dilihat dari persamaan 2

` 5

3 4

9

Kode yang dihasilkan dari persamaan 3 adalah 6

Gambar 10 Max Flow Min Cut dari source node ke node 6 4.2 Analisa Skema Random linear network coding Dari Gambar 7 akan dilakukan perhitungan dengan skema Random linear network coding. Persamaan dari gambar 7 adalah sebagai berikut :

(100)

(101) +(010) +(010)

+(010)

+(101)

+(100)

+

Diberikan error

Dari persamaan 4 dapat ditentukan kode paket yang diterima pada sink

Paket yang dikirim adalah 5,2,3 dengan bit 101,010,011. Untuk menemukan syndrome digunakan persamaan 5

Untuk mengetahui data yang dikirim dari node 1, kita ambil contoh paket yang diterima di yaitu


Membuat matrix dari syndrome sesuai dengan persamaan 7

Kita ambil matrix 2 x 2

Untuk mencari nilai

dan

kita gunakan persamaan 6

V. PENUTUP 5.1 Kesimpulan Berdasarkan hasil simulasi dan analisa, diperoleh beberapa kesimpulan sebagai berikut: 1) Penggunaan skema Random linear network coding untuk pengiriman paket 011,010,111 jika dibandingkan dengan skema multicast non network coding dengan pengkodean Reed Solomon dengan paket yang sama, maka probabilitas kesuksesan Random linear network coding lebih besar [5]. 2) Dari 2 hasil simulasi pengodean Reed Solomon dan skema Random linear network coding tidak jauh berbeda, namun perhitungan dalam Reed Solomon lebih banyak sehingga dapat menyebabkan error perhitungan. 5.2 Saran 1) Untuk penelitian lebih lanjut tentang Random linear network coding diharapkan menghitung, menganalisa proses penyimpanan paket di dalam memori sebelum dan sesudah di injeksikan paket. 2) Pemanfaatan Random linear network coding untuk sistem penyimpanan data yang terdistribusi. 3) Random linear network coding digunakan untuk pengiriman paket untuk akses yang cepat. 4) Random linear network coding dengan memori yang tidak terbatas dan random linear network coding dengan memori terbatas. DAFTAR PUSTAKA

Menghitung nilai error

[1] Desmond S. Lun, Muriel Médard, Ralf Koetter, and Michelle Effros, “On coding for reliable communication over packet networks”, Jan 2007. [2] Nur Fajriah Rachmah, “Aplikasi Algoritma Dijkstra dalam Pencarian Lintasan Terpendek Graf”, Institut Teknologi Bandung, Bandung, 2008. [3] Kevin Tanadi, “Analisis Kompleksitas Algoritma Untuk Menyelesaikan Permasalahan Maximum Flow”, Jurusan Teknik Informatika ITB, Bandung, Mar. 2008. [4] Bernard Sklar, “Digital Communications: Fundamentals and Applications, Second Edition”, Prentice-Hall, 2001, ISBN 0-13-084788-7. [5] T. Ho, M. Médard, R. Koetter, D.R. Karger, M. Effros, J. Shi, B. Leong, “A random linear network coding approach to multicast”, IEEE Transactions On Information Theory, vol. 52, NO. 10, October 2006. BIODATA PENULIS

Setelah decoding dengan RS didapatkan paket


Reza Zulfikar Ruslam, dilahirkan di Makassar 12 Juni 1987, merupakan anak pertama dari empat bersaudara pasangan Ruslam Dalton dan Nur Asmaida. Memulai pendidikan Sekolah Dasar di SDN Sawotratap III Sidoarjo, kemudian meneruskan pendidikan di SLTP Negeri 3 WaruSidoarjo dan SMA Negeri 15 Surabaya. Pendidikan terakhir di Teknik Elektro ITS bidang studi Telekomunikasi Multimedia. Sekarang sedang mengerjakan tugas akhir di Bidang Studi Telekomunikasi Multimedia, Jurusan Teknik Elektro ITS Surabaya. Email: [email protected]

RANDOM LINEAR NETWORK CODING UNTUK PENGIRIMAN PAKET YANG HANDAL DI NETWORK Reza Zulfikar Ruslam

Recommend Documents