Network Coding

Network coding merupakan suatu bagian disiplin ilmu jaringan (networking) dan teori informasi (information theory), dimana ilmu ini mempelajari manipulasi data dalam suatu kerangka jaringan (network) guna (diantaranya) meningkatkan throughput dan sifat robust dari suatu data. Teori ini pertama kali diperkenalkan oleh Rudolf Ahlswede pada tahun 2000 dalam papernya untuk IEEE Transactions on Information Theory yang berjudul Network Information Flow, terinspirasi dari aplikasi jaringan komputer.

Dalam jaringan komputer, kita mengetahui bahwa paket data dari suatu node dapat dikirim multicast ke beberapa node dengan bantuan intermediate node (router) yang bertugas mereplika dan meneruskan paket data ke node yang dituju tanpa mengubah isi dari data tersebut. Namun, dalam komunikasi jaringan (network communication), akan kita dapati bahwa mereplika dan merutekan informasi tidaklah cukup. Sebagai contoh:

perhatikan struktur Butterfly Network di atas. Source S mengirim informasi bit \{ b_{1}, b_{2} \} untuk node D_1 dan D_2. Node 1, 2, 3, dan 4 berfungsi sebagai intermediate node. Kemudian tanpa menghilangkan generalisasi, S secara simetris mentransmit b_1 ke node 1 dan b_2 ke node 2. Gambar 1(a) mengilustrasikan bagaimana aliran bit yang terkirim dalam jaringan. Node 3 menerima b_1 dan b_2 masing-masing dari node 1 dan node 2. Dari dua informasi tersebut, dikarenakan output channel dari node 3 hanya ada 1, maka node 3 harus memilih salah satu diantara bit tersebut untuk diteruskan ke node 4. Pada kasus ini kita memilih b_1, sehingga node 4 mereplika dan kemudian mentransmit b_1 ke node D_1 dan D_2. Node D_2 mendapatkan semua informasi, sedangkan node D_1 hanya memperoleh informasi b_1 baik dari node 1 maupun dari node 4. Artinya metode ini tidak bisa digunakan untuk aliran informasi di dalam jaringan.

Node 3 bisa saja mengirimkan \{ b_{1}, b_2 \} ke node 4 dengan menaikkan kapasitas channel, seperti yang diilustrasikan pada Gambar 1(b). Artinya kita memperbesar power sinyal atau dengan menambah bandwidth. Tentunya ini sangat merugikan dan tidak elegan.

Network coding bisa mengatasi permasalahan ini dengan menggunakan operator “+” atau penjumlahan modulo 2 pada node 3, seperti yang diilustrasikan paga Gambar 1(c). Node 4 mereplika dan mengirim codeword tadi ke node tujuan: D_1 dan D_2. Node D_1 bisa dengan mudah mendapatkan informasi b_2 dengan cara menggunakan operasi penjumlahan: b_1 + ( b_1 + b_2 ) = (b_1 + b_1) + b_2 = 0 + b_2 = b_2 . Dengan cara yang sama, node 2 dapat memperoleh informasi b_1. Disini kita bisa menghemat bandwidth dan pada saat yang sama memperbesar throughput.

Struktur jaringan di atas, dengan sedikit modifikasi akan kita dapatkan topologi jaringan sebagai berikut:

Nc-2multicast

Bit b_1 dibangkitkan oleh node 1 dan b_2 dibangkitkan oleh node 2. Dua multicast dalam jaringan dengan tujuan yang sama yaitu D_1 dan D_2. Jika D_1 atau D_2 memiliki bit dari node 1 maka ia bisa memastikan bit data yang berasal dari node 2, dengan menggunakan operasi yang telah dijelaskan di atas. Begitu pula sebaliknya, jika D_1 atau D_2 memiliki bit dari node 2 maka ia bisa memastikan bit data yang berasal dari node 2 dengan menggunakan operasi yang sama.

Apabila kita gabungkan node 1 dengan D_1 menjadi t_{1}^{'} serta node 2 dengan D_2 menjadi t_{2}^{'} seperti gambar berikut:

Nc-2unicast

kita dapatkan struktur unicast, dimana node t_{1}^{'} dan t_{2}^{'} bertukar informasi dalam jaringan. Jika tidak ada network coding, pada saat node t_{1}^{'} dan t_{2}^{'} mengirimkan informasi bersamaan, maka dibutuhkan kapasitas channel yang besar untuk node 3 dan 4. Maka disinilah perlunya network coding dalam proses routing saat terjadi multiple unicast dalam jaringan.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s