Analisa Probabilistik Algoritma Routing pada Jaringan Hypercube Zuherman Rustam Jurusan Matematika Universitas Indonesia Depok 16424. E-mail :
[email protected]
Abstrak Algoritma routing pada suatu jaringan interkoneksi adalah suatu mekanisme untuk menentukan rute yang harus dilalui oleh suatu packet yang berasal dari suatu node sumber ke node destinasi pada jaringan tersebut.Tujuan utama dari algoritma routing adalah memilih rute , yang yang menghubungkan node origin dengan node destination, dengan total delay setiap packet minimal. Makalah ini membahas hasil analisa probabilistic tentang dua buah algoritma routing yaitu Algoritma Deterministik Bit Fixing dan Algoritma Randomized Routing. Dengan menggunakan teorema Chernoff dapat diketahui probabilitas suatu packet mencapai node tujuan.
1.
Pendahuluan
Komputer paralel terdiri dari sejumlah proses yang saling berinteraksi. Komunikasi antara prossesor dilakukan melalui interconnection network, sedangkan informasi yang dikirimkan antar prosessor dapat berupa sekumpulan data binary , yang dinamakan dengan packet. Untuk merepresentasikan interaksi antar prosessor digunakan suatu graph atau topology. Node dari graph tersebut menunjukkan prosessor sedangkan edge yang menghubungkan sepasang node menunjukkan adanya jalur komunikasi antara kedua prosessor.Topologi atau Graph yang biasa digunakan antara lain : Linear Array , Hypercube , Mesh dan Fat Tree. Topologi Linear Array merupakan topologi yang sederhana dan banyak digunakan untuk komputer paralel dengan jumlah prosesor yang sedikit. Generasi pertama komputer paralel ( Intel iPSC dan CM2 ) menggunakan topologi hypercube. Generasi berikutnya seperti Intel Paragon dan iWrap menggunakan topologi mesh.[ Bertsekas ,1989] Jaringan Linear Array , Hypercube , Mesh dan Fat Tree digolongkan kedalam static interconnextion networks , hal ini disebabkan karena prosessor dihubungkan satu sama lain dengan menggunakan fixed connection. Algoritma Routing untuk suatu Jaringan Interkoneksi adalah suatu mekanisme untuk menentukan rute / lintasan yang harus dilalui oleh suatu packet dari suatu node sumber ke node destinasi. Tujuan utama algoritma routing adalah memilih rute pada jaringan sedemikian sehingga total delay untuk setiap paket minimum. Dalam makalah ini akan dibahas dua algoritma routing yaitu Bit-Fixing Routing dan Randomized Routing pada jaringan Hypercube. Sistimatika makalah ini sebagai berikut : bagian kedua membahas definisi dan teorema dasar yang berkaitan dengan Topologi Hypercube , bagian ketiga membahas tentang algoritma Bit-Fixing , bagian terakhir dari makalah ini membahas algoritma Randomized Routing.
2.
Topologi Hypercube
Suatu jaringan hypercube berdemensi n ( disebut juga dengan n cube ), terdiri dari N = 2 node. Setiap node ber-degree n , dengan perkataan lain setiap node terhubung dengan n buah node lainnya. . Setiap node mempunyai n bit address . Address dari node ke i dinyatakan dalam bentuk (i 1 , i 2 ,..., i n ) ¸{0,1} n . Edge e menghubungkan sepasang node i dan j jika jarak Hamming antara (i 1 , i 2 ,..., i n ) dan ( j 1 , j 2 ,..., j n ) bernilai 1 . Topologi hypercube ditinjau berdasarkan komputasi lebih baik dibandingkan dengan mesh, hal ini ditandai dengan fakta bahwa komputasi yang dikerjakan dengan satu langkah di mesh dapat dikerjakan dengan satu langkah pada hypercube , sedangkan kebalikannya tidak berlaku. n
A-105
Proceedings Komputer dan sistem Intelejen(KOMMIT2002) Auditorium Universitas Gunadarma, Jakarta, 21 – 22 Agustus 2002
A-106
Definisi 1 : Misalkan diberikan suatu jaringan dengan N node , dimana setiap node memuat suatu packet yang harus dikirimkan ke suatu node destinasi , jika node destinasi membentuk suatu permutasi π : N ¨ N , dari N node maka masalah routing dinamakan masalah Permutasi Routing. Algoritma yang digunakan untuk menyelesaikan masalah ini dinamakan algortima Permutasi Routing. Definisi 2 : Setiap algoritma routing , dimana rute setiap packet ditentukan berdasarkan hanya pada address dari node destinasi , dinamakan algoritma oblivious-routing. Algoritma ini menggunakan rute tetap untuk setiap pasang node sumber dan destinasi. Pada node antara , keputusan yang harus dilakukan adalah memilih rute yang harus dilalui suatu packet, berdasarkan address node destinasi. Teorema 3 : [Motwani et all ,1997] Kompleksitas algortima Permutasi Routing pada jaringan dengan N node , berdegree n , adalah Ω(
3.
N ). n
Algoritma Bit-Fixing Routing
Algoritma Bit-Fixing merupakan algoritma oblivious-routing deterministik. Pada node intermediate , keputusan routing untuk suatu packet , hanya didasarkan pada adrress dari node destinasi.Misalkan suatu packet akan dikirimkan dari node sumber ber-address π(i ) ke node destinasi ber-address η(i ) melalui node intermediate ber-address σ(i ) . Pertama sekali harus dibandingkan address π(i ) dengan σ(i ) ,dimulai dari kiri ke kanan, dan ditentukan di posisi mana kedua address tersebut berbeda. Selanjutnya packet dikirimkan ke node beraddress η(i ) dimana η(i ) dengan σ(i ) hanya berbeda pada posisi tersebut. Misalkan diberikan jaringan Hypercube berdimensi n , terdiri dari N = 2 n
node dan
n dan operator setiap node berdegree n ( genap). Misalkan i dan j bit-string dengan panjang 2
•
merupakan operator konkatenasi. Dan dimisalkan setiap node di hypercube tersebut dinyatakan dalam bentuk (i • j ) dan setiap node merupakan elemen berbeda dari matriks A , berukuran n 22
n ×22
. Berdasarkan data-data tersebut maka menghitung transpose dari matriks A sama artinya dengan proses routing setiap element ke node destinasi yang berbeda sedemikian sehinggga element yang disimpan di node (i • j ) di kirimkan ke node ( j • i ) . Karena node destinasi membentuk suatu permutasi maka masalah ini dinamakan masalah permutasi routing , atau transpose permutasi. Permutasi diatas diperlukan untuk membahas kompleksitas dari algoritma bit-fixing algorithm untuk Hypercube . Dengan menggunakan teorema 3 akan menghasilkan corollary berikut ini : Corallary 4 : Kompleksitas dari algortima Bit-Fixing-routing pada jaringan hypercube dengan N node berdegree n adalah Ω(
N ). n
Bukti : n
Íi , j
¸{0,1,...,2 2
1} permutasi transpose memerlukan routing elememt yang disimpan pada node
Analisa Probabilistik Algoritma Routing pada Jaringan Hypercube
A-107
sumber (i • j ) ke node destinasi ( j • i ) . Misalkan untuk j = 0 , ( terdapat j =0 ) ,
Íi
n ¸{0,1,...,2 2
n 22
buah node dengan
1} dilakukan routing untuk element yang disimpan pada node sumber
(i • 0) ke node destinasi (0 • i ) dengan menggunakan algoritma Bit-Fixing. Setiap element harus
melalui node (0 • 0) . Jika i merupakan bilangan ganjil terdapat
n 22
2
n
node dari 2 2 node yang n
22 memiliki address (1 • 0) . Sehingga berdasarkan transpose permutasi terdapat 2
element yang
akan melintasi edge , yang menghubungkan node (1 • 0) dan (0 • 0) . Karena hanya ada sebuah elemen pada saat yang bersamaan yang dapat menggunakan edge yang n
22 sama , maka hal ini memrlukan 2
langkah . Sehingga permutasi transpose memerlukan
Ω( 2 n ) langkah.
4.
Algoritma Randomized-Routing
Untuk menylesaikan masalah permutasi routing pada hypercube , Les Valiant membentuk algoritma randomized routing , untuk mengirimkan suatu packet . Algoritma Valiant tersebut terdiri dari dua phase yaitu:[ Valliant ,1982] 1. Pada setiap dipilih secara random , node intermediate σ(i ) dari {1,2,..., N } dan kirimkan packet v i dari i ke σ(i ) dengan menggunakan Bit-Fixing Routing 2. Jika packet telah sampai di node antara σ(i ) , kirimkan packet tersebut dari node intermediate σ(i ) ke node destinasi π(i ) dengan menggunakan Bit-Fixing Routing Lemma 5 : Jika algoritma Bit-Fixing digunakan untuk mengirimkan packet v i dari i ke σ(i ) dan mengirimkan packet v j dari j ke σ( j ) maka rute keduanya tidak akan melintasi rute yang sama jika akan keduanya sudah berpisah. Bukti : Misalkan k dan l masing-masing menunjukkan node dimana kedua path berpisah dan bergabung . Karena rute pada bitfixing untuk masing-masing packet v i dan packet v j tergantung hanya pada address dari node k dan node l maka kedua packet tersbut harus melaui rute yang sama . Selanjutnya akan dibahas tentang kompleksitas algoritma Randomized-Routing.Misalkan p i = (e 1 , e 2 ,..., e k } lintasan yang dilalui oleh packet v i dan didefinisikan himpunan S sebgai berikut : S = {v j i ‚j , v j melintasi paling sedikit sebuah edge di p i = (e 1 , e 2 ,..., e k } }. Untuk suatu packet v , keterlambatan (lag) dari packet v relatif terhadap p i dinyatakan sebagai t - j . Keterlambatan terjadi jika pada saat t , packet tersebut sudah siap untuk melintasi edge e j . Lemma 6: Batas atas keterlambatan packet v i adalah S Bukti :
Proceedings Komputer dan sistem Intelejen(KOMMIT2002) Auditorium Universitas Gunadarma, Jakarta, 21 – 22 Agustus 2002
A-108
Setiap packet yang meninggalkan lintasan p i = (e 1 , e 2 ,..., e k } dengan lag sebesar l , akan lag dari packet tersebut akan dikenakan penalti sebesar satu satuan , sehingga lag dari packet tersebut menjadi l + 1 . Misalkan t / saat terakhir suatu packet berada di himpunan S dengan keterlambatan sebesar l . Karena jumlah langkah hingga maka ada packet yang akan menggunakan / / e j / pada saat t / sedemikain sehingga t − j = l . Karena packet v akan menggunakan edge e j / dan pada saat yang bersamaan suatu packet w sedang berada di edge e j / , maka dua terdapat dua pilihan untuk packet w yaitu harus meninggalkan p i pada saat t / atau w menunggu untuk melintasi edge e j / +1 pada saat t / + 1 . Hal ini akan mengakibatkan beberapa packet harus melintasi e j / +1 pada saat t / + 1 .Hal ini bertentangan dengan maksimalitas dari l . Berdasarkan lemma 5 , w
tidak akan pernah kembali ke lintasan p i . Sehingga setiap packet yang berada di S paling sedikit mengalami penalti paling sedikit satu kali. Selanjutnya akan dibahas ekspekati waktu untuk mentransfer seluruh packet pada jaringan Hypercube.
⎧1 , jika e ∈ pi ∩ p j , ⎩0 , jika tidak demikian
Misalkan didefinisikan variabel random H ij = ⎨ dan
d i menunjukkan total delay yang dialami oleh packet
berlaku d i ≤
n
∑H j =1
, dan E[d i ] ≤ E[
ij
n
∑H j =1
v i . Berdasarkan lemma 6, akan
n
ij
] = ∑ E[ H ij ] . j =1
Misalkan T (e ) variabel random yang menunjukkan banyaknya rute yang melintasi edge e n
. Jika p i = (e 1 , e 2 ,..., e k } maka
∑H j =1
k
ij
≤ ∑ T (ei ) . Karena setiap rute harus melalui paling i =1
sedikit sebuah edge di p i = (e 1 , e 2 ,..., e k } , misalkan edge tersebut adalah e l .Karena edge e l adalah edge yang dilintasi oleh setiap rute tersebut untuk membawa suatu packet anggota S maka n
k
k
j =1
i =1
i =1
E[∑ H ij ] ≤ E[∑ T (ei )] =∑ T (ei )] Karena edge pada Hypercube adalah simetris
, maka untuk e l
(1)
dan
em
berlaku
E[T (el )] = E[T (em )] . Jumlah edge pada digraph adalah Nn maka ekspektasi panjang suatu rute adalah Íe
n 1 Nn dan ekspektasi panjang total rute adalah . Dengan perkataan lain E [T (e )] = , 2 2 2
¸E . Dengan menggunakan persamaan (1) , maka akan berlaku : n
E[∑ H ij ] ≤ j =1
k n ≤ 2 2
(2)
Karena rute untuk suatu packet dipilih bebas secara random.Untuk suatu nilai i , i ‚j , H ij merupakan percobaan Poison sehingga untuk menghitung batas-batas probabilistik dari H ij dapat digunankan Teorema Chernoff , yaitu Teorema Chernoff : Jika X = maka
∑X i
i
dimana X i suatu menunjukkan outcome dari percobaan bebas Poisson,
⎛ eδ berlaku Pr[ X > (1 + δ ) μ ) < ⎜⎜ 1+ δ ⎝ (1 + δ )
⎞ ⎟⎟ ⎠
μ
, dimana δ
konstanta
dan
Analisa Probabilistik Algoritma Routing pada Jaringan Hypercube
A-109
μ = E[ X ] = ∑i p i .
Selanjutnya,jika δ > 2e − 1 maka akan berlaku :
⎛ e1+δ Pr[ X > (1 + δ ) μ ) ≤ ⎜⎜ 1+δ ⎝ (1 + δ )
μ
⎞ ⎛ e1+δ ⎟⎟ ≤ ⎜⎜ 1+δ ⎠ ⎝ (1 + δ )
Dengan menetapkan (1 + δ ) μ = 6 n maka Pr[
n
∑H j =1
ij
⎞ ⎟⎟ ⎠
μ (1+δ )
1 ≤ ( ) μ (1+δ ) 2
> 6n ) ≤ 2 − 6 n .
Karena total banyaknya packet adalah 2 n maka probabilitas , bahwa suatu delay yang terjadi lebih besar 6n , adalah lebih kecil dari 2n × 2 6n . Berdasarkan analisa diatas maka akan dihasilkan proposisi berikut ini : Proposisi 7 : Dengan probabilitas kurang dari 1 − 2 −5 n , suatu packet v i dalam 7n langkah atau kurang dari itu.
akan mencapai node σ(i )
Phase kedua pada algoritma Randomized-Routing Valliant identik dengan phase pertama jika node sumber dan node destinasi dipertukarkan. Sehingga analisa diatas juga berlaku untuk phase kedua. Dengan dilakukan pertukaran peran dari node source dan node destinasi maka dengan probabilitas
1 , suatu paket gagal untuk mencapai node destinasi pada salah satu phase N tersebut , kurang dari 2 −5 n +1 . Atau dapat dinyatakan dinyatakan dalam proposisi dibawah ini : lebih kecil dari 2 −n =
Proposisi 8: Dengan probabilitas lebih kecil dari 1 −
1 , suatu packet tidak akan mencapai destinasinya N
dalam 14n langkah atau kurang dari itu.
5. [1]. [2]. [3].
Daftar Pustaka D.P. Bertsekas and J.N. Tsitsiklis , Parallel and Distributed Computation , Prentice Hall Inc, 1989. R.J Motwani et all , Randomized Approximation Algorithms in Combinatorial Optimization , PWS , 1997 L.G. Valliant , A Scheme for Fast Parallel Communication , SIAM J. Computations , Vol 11:350-361,1982
