TUGAS AKHIR ANALISIS KINERJA JARINGAN SWITCHING CLOS TANPA BUFFER

TUGAS AKHIR ANALISIS KINERJA JARINGAN SWITCHING CLOS TANPA BUFFER

Diajukan untuk memenuhi salah satu persyaratan dalam menyelesaikan pendidikan sarjana (S-1) pada Departemen Teknik Elektro

O L E H

APRIANY PRIMA S. U. SIREGAR 050402037

DEPARTEMEN TEKNIK ELEKTRO FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA MEDAN 2009

Aprianty Prima S.U. Siregar : Analisis Kinerja Jaringan Switching Clos Tanpa Buffer, 2009.

ABSTRAK

Jaringan Clos adalah jaringan switching yang merepresentasikan suatu teori yang ideal dari sistem switching telepon banyak tingkat secara praktek. Tugas Akhir ini menganalisis kinerja jaringan switching Clos pada interkoneksi processor - memory. Kinerja yang dianalisis adalah probabilitas blocking. Untuk mengukur kinerja jaringan switching Clos harus terlebih dahulu mengetahui bagaimana cara membangun jaringan, bagaimana prinsip kerjanya, dan apa saja kinerja yang dapat diukur dari jaringan switching Clos tanpa buffer. Probabilitas blocking yang akan dihitung menggunakan metode Lee dan metode Jacobeus. Hasil yang diperoleh memperlihatkan perhitungan yang akurat dari jaringan switching Clos yaitu probabilitas blocking dengan metode Lee dan Jacobeus dengan parameter-parameter jumlah switch masukan n (dengan nilai 64, 120, dan 240), jumlah switch antara m (dengan nilai 64, 68, 72, 76, 128, dan 256) dan probabilitas yang diberikan oleh link masukan dan keluaran sibuk ρ (dengan nilai 0.6 sampai 0.95 dengan rentang 0.05), dimana dengan bertambahnya nilai switch antara maka nilai probabilitas blocking dengan metode Lee dan metode Jacobeus dari sistem switching tersebut menurun dengan selisih hasil yang diperoleh cukup kecil. Untuk nilai n=64, m=64, ρ=0.6 didapat nilai probabilitas blocking yang lebih kecil yaitu 7.97365x10-6 untuk nilai Pb metode Lee dan 7.15779x10-6 untuk nilai Pb metode Jacobeus dan untuk n=240, m=256, dan ρ=0.6 didapat nilai Pb yang lebih kecil yaitu 1.3263x10-25 untuk nilai Pb metode Jacobeus dan 1.24705x10-24 untuk nilai Pb metode Lee. Jika selisih jumlah switch masukan dan switch antara tidak terlalu besar, kedua metode (Lee dan Jacobeus) dapat dipilih karena memperlihatkan kinerja yang hampir sama, tetapi apabila perbedaan jumlah switch masukan dan antara semakin besar, metode Jacobeus menghasilkan kinerja yang lebih baik.


KATA PENGANTAR

Puji dan Syukur Penulis ucapkan kepada Tuhan yang Maha Esa, atas berkat dan kasihNya sehingga penulis diberikan kemampuan untuk dapat menyelesaikan Tugas Akhir ini dengan baik. Tugas Akhir ini berjudul: “Analisis Kinerja Jaringan Switching Clos Tanpa Buffer“. Tugas Akhir ini merupakan salah satu syarat untuk memperoleh gelar kesarjanaan pada Departemen Teknik Elektro Fakultas Teknik Universitas Sumatera Utara. Penulis menyampaikan rasa hormat, bangga, dan terima kasih yang sebesar-besarnya kepada kedua orangtua Penulis, Ayahanda Mitrael Siregar, SP dan Ibunda Dra. Tetty Landus Pangaribuan, yang telah membesarkan, mendidik dan selalu memberikan bantuan secara moral dan materil serta mendoakan Penulis. Dalam kesempatan ini juga Penulis menyampaikan rasa terimakasih yang sebesar-besarnya kepada : 1. Bapak Ir. M. Zulfin, MT, selaku Dosen Pembimbing Tugas Akhir, yang dengan ikhlas dan sabar memberikan masukan, dukungan, bimbingan dan motivasi dalam penulisan Tugas Akhir ini. 2. Bapak Ir. Rachman Hasibuan, selaku Dosen Wali selama Penulis mengikuti perkuliahan.


3. Bapak alm. Ir. Nasrul Abdi, MT, selaku mantan Ketua Departemen Teknik Elektro Fakultas Teknik Universitas Sumatera Utara dan Bapak Prof. Dr. Usman Baafai selaku Pelaksana Harian Ketua Departemen Teknik Elektro Fakultas Teknik Universitas Sumatera Utara. 4. Bapak Rahmad Fauzi, ST, MT, selaku Sekretaris Departemen Teknik Elektro Fakultas Teknik Universitas Sumatera Utara. 5. Seluruh staf pengajar di Departemen Teknik Elektro Fakultas Teknik Universitas Sumatera Utara, yang telah memberikan bekal ilmu kepada Penulis selama mengikuti perkuliahan. 6. Seluruh karyawan di Departemen Teknik Elektro Fakultas Teknik Elektro Universitas Sumatera Utara. 7. Terimakasih kepada sahabat Penulis yang telah memberikan dukungan dalam suka dan duka, teman-teman seperjuangan Angkatan 2005, Viona Nauvalisya, Kristina Sitompul, Icha, Diana, Christina, Once, Amy, Annisa, Muti, Taci, Dewi, Lemuel, Andry W., Daniel, Rainhard, Prindi, Harpen, Ricky H., Megi, Herman, Irpan, Dedi M., Dedi A., Bastana, Fery, Ardi, dan

Alex, dan semua teman-teman Elektro 2005 dan anggota

Hexacom 2004 yang tidak dapat Penulis sebutkan satu per satu, semoga hubungan kekerabatan kita terus terjaga. 8. Teman-teman UKM Fotografi USU yang telah sabar dengan hiatusnya Penulis. 9. Teman-teman mahasiswa dan semua pihak yang tidak dapat Penulis sebutkan satu persatu.


Penulis menyadari bahwa Tugas Akhir ini masih sangat jauh dari sempurna, baik dari segi materi maupun cara penyajiannya. Oleh karena itu, penulis siap menerima saran dan kritik dari pembaca yang sifatnya membangun demi kesempurnaan Tugas Akhir ini. Akhir kata, Penulis berharap agar Tugas Akhir ini dapat bermanfaat bagi pembaca dan Penulis. Medan,

Agustus 2009

Penulis

Apriany Prima S. U. Siregar


DAFTAR ISI

ABSTRAK................................................................................................ i KATA PENGANTAR .............................................................................. ii DAFTAR ISI ............................................................................................ v DAFTAR GAMBAR ................................................................................ viii DAFTAR TABEL .................................................................................... x I.

PENDAHULUAN 1.1 Latar Belakang Masalah ........................................................... 1 1.2 Rumusan Masalah .................................................................... 2 1.3 Tujuan Penulisan ...................................................................... 3 1.4 Batasan Masalah ....................................................................... 3 1.5 Metode Penulisan ..................................................................... 3 1.6 Sistematika Penulisan ............................................................... 4

II.

JARINGAN INTERKONEKSI BANYAK TINGKAT 2.1 Sejarah Jaringan Interkoneksi ................................................... 5 2.2 Switching ................................................................................. 10 2.3 Jaringan Interkoneksi ................................................................ 12 2.4 Karakteristik Jaringan Interkoneksi........................................... 13 2.4.1 Topologi .......................................................................... 13 2.4.2 Teknik Switching ............................................................. 15 2.4.3 Sinkronisasi ..................................................................... 17 2.4.4 Startegi Pengaturan .......................................................... 17 2.4.5 Algoritma Perutean .......................................................... 18 2.5

Klasifikasi Jaringan Interkoneksi .............................................. 18


2.5.1 Jaringan Interkoneksi Statis (Jaringan Langsung) ........... 19 2.5.2 Jaringan Interkoneksi Dinamis (Jaringan Tidak Langsung) ............................................. 19 a. Jaringan Interkoneksi Satu Tingkat ........................... 20 b. Jaringan Interkoneksi Banyak Tingkat ...................... 21 2.6 Klasifikasi Jaringan Interkoneksi Banyak Tingkat .................... 24 III.

JARINGAN SWITCHING CLOS TANPA BUFFER 3.1 Umum ...................................................................................... 27 3.2 Cara Membangun Sistem .......................................................... 27 3.3 Pemaketan Panggilan ................................................................ 32 3.4 Karakteristik Blocking dari Jaringan Clos ................................. 33 3.4.1 Jaringan Clos yang bersifat strict-sense non-blocking....... 33 3.4.2 Jaringan Clos yang bersifat rearrangeably non-blocking . 33 3.5 Jaringan Non-Blocking.............................................................. 34 3.6 Jaringan Clos yang Umum ........................................................ 39 3.7 Probabilitas Blocking Pada Jaringan Clos ................................. 41 3.7.1 Metode Lee ................................................................... 42 3.7.2 Metode Jacobeus ........................................................... 43 3.8 Jaringan Benes.......................................................................... 45 3.9 Keuntungan dan Kerugian Menggunakan Jaringan Switching Clos .......................................................................... 45

IV. ANALISIS KINERJA JARINGAN SWITCHING CLOS TANPA BUFFER 4.1 Umum ...................................................................................... 47


4.2 Perhitungan Analisis Kinerja Jaringan Switching Clos .............. 48 4.2.1 Analisis Kinerja dengan Metode Lee ............................. 48 4.2.2 Analisis Kinerja dengan Metode Jacobeus ..................... 49 V.

KESIMPULAN DAN SARAN 5.1

Kesimpulan .............................................................................. 57

5.2

Saran ........................................................................................ 58

DAFTAR PUSTAKA LAMPIRAN


DAFTAR GAMBAR

Gambar 2.1

Contoh Bentuk Jaringan Umum ............................................. 6

Gambar 2.2

Gambaran Fungsional dari Jaringan Interkoneksi ................... 8

Gambar 2.3

Tipe Elemen Switching .......................................................... 11

Gambar 2.4

Arsitektur Crossbar ............................................................... 13

Gambar 2.5

Pemecahan Data Menjadi Paket-Paket ................................... 16

Gambar 2.6

Klasifikasi Jaringan Interkoneksi ........................................... 19

Gambar 2.7

Skema Jaringan Satu Tingkat ................................................. 21

Gambar 2.8

Arsitektur Jaringan Interkoneksi Banyak Tingkat ................... 23

Gambar 3.1

Jaringan Switching Clos (3,3,4) .............................................. 28

Gambar 3.2

Jaringan Switching Clos (5,3,4) .............................................. 29

Gambar 3.3

Koneksi All-to-All Antar Tingkatan dari Jaringan Clos ........... 30

Gambar 3.4

Interkoneksi Penuh Jaringan Switching Tiga Tingkat ............. 32

Gambar 3.5

Elemen Switch Bertingkat Satu ............................................. 34

Gambar 3.6

Elemen Switch Bertingkat Dua............................................... 35

Gambar 3.7

Switching Clos Tiga Tingkat .................................................. 36

Gambar 3.8

Blocking pada Jaringan Tiga Tingkat ..................................... 38

Gambar 3.9

Contoh Sederhana Jaringan switching Clos ............................ 40

Gambar 4.1

Model interkoneksi antara prosesor dan memori .................... 47

Gambar 4.2

Perbandingan Antara Probabilitas Blocking Metode Lee dan Jacobeus dengan n=64 dan m=64 .................................... 52

Gambar 4.3

Perbandingan antara Probabilitas Blocking metode Lee dan Jacobeus dengan n=64 dan m=68 .................................... 53


Gambar 4.4


Gambar 4.5


Gambar 4.6

Perbandingan antara Probabilitas Blocking metode Lee dan Jacobeus dengan n=120 dan m=128 ................................ 55

Gambar 4.7

Perbandingan antara Probabilitas Blocking metode Lee dan Jacobeus dengan n=240 dan m=256 ................................ 56


DAFTAR TABEL

Tabel 4.1

Nilai Ρrobabilitas Blocking Metode Lee Untuk ρ = 0.6, 0.65, 0.7, 0.75 ........................................................ 49

Tabel 4.2

Nilai Ρrobabilitas Blocking Metode Lee Untuk ρ = 0.8, 0.85, 0.9, 0.95 ........................................................ 49

Tabel 4.3

Nilai Ρrobabilitas Blocking Metode Jacobeus Untuk ρ = 0.6, 0.65, 0.7, 0.75 ........................................................ 51

Tabel 4.4

Nilai Ρrobabilitas Blocking Metode Jacobeus Untuk ρ = 0.8, 0.85, 0.9, 0.95 ........................................................ 51

Tabel 4.5

Ρerbandingan Antara Ρrobabilitas Blocking Metode Lee dan Jacobeus dengan n=64 dan m=64 ................................. 51

Tabel 4.6


Tabel 4.7


Tabel 4.8


Tabel 4.9

Ρerbandingan Antara Ρrobabilitas Blocking Metode Lee dan Jacobeus dengan n=120 dan m=128 ............................. 55

Tabel 4.10

Ρerbandingan Antara Ρrobabilitas Blocking Metode Lee dan Jacobeus dengan n=240 dan m=256 ............................. 55


BAB I PENDAHULUAN

1.1

Latar Belakang Perkembangan teknologi informasi dan komunikasi yang sangat cepat

menjadi tantangan bagi orang-orang yang bergerak dalam dunia perangkat keras dan perangkat lunak untuk terus berupaya menciptakan inovasi-inovasi yang berguna bagi kemajuan teknologi informasi dan komunikasi. Perangkat-perangkat keras yang canggih mutlak diperlukan untuk mendukung kemajuan dan perkembangan teknologi informasi dan komunikasi terutama perangkat keras yang memiliki kinerja yang handal dengan biaya yang murah. Kinerja suatu jaringan telekomunikasi ditentukan oleh banyak faktor. Beberapa diantaranya adalah jenis jaringan switching yang diterapkan untuk membangun sebuah sistem interkoneksi, perangkat keras berteknologi tinggi yang digunakan untuk membangun sistem switching itu sendiri. Jaringan-jaringan komunikasi sekarang ini dibangun dengan teknologi switching yang sudah sangat canggih. Perangkat-perangkat switching yang banyak digunakan sekarang ini sudah menggunakan teknologi microprocessor dengan biaya murah dan Very Large Scale Integration (VLSI) dalam bentuk chip-chip yang memiliki bentuk yang kecil dengan kemampuan yang sangat handal. Berbeda dengan jaringan-jaringan komunikasi masa lalu yang membutuhkan ruang yang luas untuk meletakkan sebuah perangkat switching. Seperti pada jaringan switching crossbar yang memiliki ciri lambat dalam memproses panggilan karena menggunakan komponen-komponen elektromekanik pada


sistem kendalinya, juga membutuhkan biaya yang besar untuk membangunnya ataupun menambah kapasitas switching. Pengguna jasa komunikasi tentu mengharapkan teknologi komunikasi yang memiliki kinerja yang handal dengan biaya murah. Hal ini bisa diwujudkan dengan menggunakan teknologi microprocessor VLSI. Microprocessor VLSI ini menggunakan

teknologi

jaringan

switching

banyak

tingkat

(Multistage

Interconnection Networks). Salah satu teknologi jaringan switching yang dipakai pada beberapa microprocessor adalah jaringan switching Clos. Jaringan switching Clos ditujukan untuk interkoneksi antara modul memori dan modul prosesor seperti pada packet switching dalam jaringan komunikasi. Untuk itu diperlukan pengukuran kinerja dari jaringan switching Clos tanpa buffer ini agar dapat diketahui bagaimana probabilitas blocking-nya.

1.2

Rumusan Masalah Dari latar belakang di atas, dirumuskan beberapa permasalahan antara lain: 1. Bagaimana cara membangun jaringan switching Clos. 2. Bagaimana prinsip kerja jaringan switching Clos pada jaringan processor – memory. 3. Apa saja kinerja jaringan switching Clos. 4. Bagaimana cara menganalisis kinerja probabilitas blocking pada jaringan switching Clos dengan menggunakan metode Lee dan Jacobeus.


1.3

Tujuan Penulisan Tujuan penulisan Tugas Akhir ini adalah untuk menganalisis kinerja

jaringan switching Clos khususnya mengenai probabilitas blocking metode Lee dan Jacobeus pada jaringan switching Clos.

1.4

Batasan Masalah Agar masalah dalam Tugas Akhir ini tidak terlalu luas dan menyimpang dari topik yang ada, maka penulis perlu

membatasi permasalahan sebagai berikut :

a. Jaringan yang dibahas hanya jaringan switching Clos. b. Model yang dianalisis tidak menggunakan buffer. c. Kinerja yang dianalisis hanya mencakup probabilitas blocking tidak mencakup throughput dan delay. d. Nilai ρ yang dianalisis adalah 0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, dan 0.95. e. Tidak membahas komponen atau rangkaian elektronika yang mencakup operasi switching. f. Tidak menghitung kapasitas switching.

1.5

Metodologi Penulisan Metode penulisan yang digunakan dalam penulisan Tugas Akhir ini

adalah: 1. Studi literatur, berupa studi kepustakaan dan kajian dari jurnal-jurnal dan artikel pendukung. 2. Perhitungan kinerja jaringan switching Clos yang meliputi probabilitas blocking dengan metode Lee dan metode Jacobeus


1.6

Sistematika Penulisan Penulisan Tugas Akhir ini disajikan dengan sistematika penulisan sebagai

berikut: BAB I

PENDAHULUAN Bab ini merupakan pendahuluan yang berisikan tentang latar belakang masalah, tujuan penulisan, batasan masalah, metode penulisan, dan sistematika penulisan.

BAB II

JARINGAN

SWITCHING

BANYAK

TINGKAT

(MULTISTAGE INTERCONNECTION NETWORKS) Bab ini membahas tentang jenis-jenis jaringan switching banyak tingkat (multistage interconnection networks). BAB III

JARINGAN SWITCHING CLOS TANPA BUFFER Bab ini membahas tentang cara membangun, prinsip kerja, karakteristik, dan rumusan kinerja jaringan switching Clos tanpa buffer.

BAB IV

ANALISIS KINERJA JARINGAN SWITCHING CLOS TANPA BUFFER Bab ini menerangkan tentang analisis dari kinerja jaringan switching Clos, yaitu probabilitas blocking metode Lee dan Jacobeus.

BAB V

KESIMPULAN DAN SARAN Bab ini berisi kesimpulan dan saran dari hasil analisis data-data yang telah diperoleh.


BAB II JARINGAN INTERKONEKSI BANYAK TINGKAT

2.1

Sejarah Jaringan Interkoneksi Jaringan interkoneksi memiliki sejarah hebat yang telah berlangsung

selama bertahun-tahun. Jaringan berkembang seiring dengan minimal tiga rangkaian urutan yang menandainya yaitu jaringan switching telepon, komunikasi interprocessor, dan interkoneksi processor-memory. Switching telepon telah ada sejak munculnya telepon sebagai alat komunikasi. Jaringan awal telepon dibangun dari switch crossbar elektromekanis ataupun switch elektromekanis step-by-step. Pada akhir 1980, kebanyakan switch telepon lokal masih dibangun dari relay elektromekanis, meskipun switch-switch jarak jauh secara menyeluruh telah bersifat elektronik dan digital pada saat itu. Kunci perkembangannya terletak pada switching telepon termasuk jaringan nonblocking, jaringan Clos banyak tingkat pada tahun 1953 dan jaringan Benes pada tahun 1962. Banyak switch telepon yang dibangun saat ini merupakan perkembangan dari jaringan Clos ataupun jaringan yang mirip jaringan Clos. Jaringan interkoneksi inter-processor telah melalui rangkaian mode topologi yang telah berkembang selama bertahun-tahun, dimotivasi cukup besar oleh pemaketan dan batasan-batasan teknologi lainnya. Mesin awal, seperti Solomon, Illiac, dan MPP didasarkan pada mesh 2-D yang sederhana ataupun jaringan Torus karena regularitas fisik mereka. Mulai dari akhir 1970, jaringan ncube atau hypercube biner terkenal baik karena diameter mereka yang kecil. Banyak mesin yang dirancang di sekitar jaringan hypercube muncul, seperti


theAmetek S14, Cosmic Cube, komputer nCUBE, dan Intel rangkaian iPSC. Pada pertengahan 1980, ditunjukkan pemaketan realistis yang membatasi jaringan berdimensi rendah menggunakan hypercube dan kebanyakan mesin kembali pada mesh 2-D atau 3-D atau jaringan Torus. Kita Dapat melihat beberapa contoh jaringan umum pada Gambar 2.1a dan Gambar 2.1b.

1-D Mesh

1-D Torus (ring) 2-D Mesh

2-D Torus

Star Crossbar Bus

(a)


Binary Tree

1-Cube 4-Cube

0-Cube

2-Cube

3-Cube

(b) Gambar 2.1 Contoh Bentuk Jaringan Umum

Sebagai konsekuensinya, kebanyakan mesin yang dibangun di dekade akhir ini telah kembali pada jaringan-jaringan yang tersebut di atas, termasuk contoh kecilnya J-machine, Cray T3D, dan T3E, Intel DELTA, dan Alpha 21364. Sekarang ini, pin lebar pita tingkat tinggi dari router chips yang berhubungan dengan panjang pesan mendorong penggunaan jaringan dengan tingkatan node yang jauh lebih tinggi, seperi jaringan Butterfly dan jaringan Clos. Interkoneksi processor-memory muncul di akhir 1960 ketika sistem prosesor paralel menggabungkan jajaran jaringan untuk membolehkan prosesor manapun mengakses tumpukan memori tanpa membebankan prosesor lainnya.


Mesin terkecil memakai switch crossbar untuk tujuan ini, dimana mesin-mesin yang lebih besar menggunakan jaringan dengan topologi Butterfly (atau yang sepadan) pada susunan Dance-Hall. Variasi pada tema ini digunakan sejak 1980 untuk banyak prosessor yang terbagi secara paralel (shared memory parallel). Tiga urutan dari evolusi jaringan interkoneksi telah bergabung. Sejak awal 1990, telah ada sedikit perbedaan pada rancangan processor-memory dan jaringan interkoneksi inter-processor. Yang faktanya, router chips yang sama telah digunakan untuk keduanya. Variasi dari jaringan Clos dan jaringan Benes dari sistem telepon juga telah muncul pada jaringan multiprocessor sebagai bentuk dari topologi fat tree. Untuk mengerti tentang jaringan interkoneksi, perhatikan Gambar 2.2 berikut. 1

1

1

1

1

1

Jaringan Interkoneksi

Gambar 2.2 Gambaran fungsional dari jaringan interkoneksi. Seperti yang digambarkan pada Gambar 2.2, jaringan interkoneksi adalah sistem yang dapat diprogram untuk mengirimkan data antar terminal. Gambar tersebut menunjukkan enam terminal, T1 sampai T6 yang terhubung pada satu jaringan. Ketika terminal T3 ingin mengkomunikasikan beberapa data terhadap terminal T5, T3 mengirimkan suatu pesan yang mengandung data pada jaringan dan jaringan akan meneruskan pengiriman pesan pada T5. Jaringan yang dapat diprogram memiliki pengertian bahwa jaringan tersebut memiliki poin-poin yang berbeda setiap waktu. Jaringan yang digambarkan pada Gambar 2.2 dapat


mengirim pesan dari T3 ke T5 dalam satu putaran (satuan waktu) kemudian menggunakan sumber yang sama untuk mengirimkan pesan dari T3 ke T1 pada putaran berikutnya. Jaringan tersebut merupakan suatu sistem karena jaringan tersebut terdiri dari beberapa komponen, yaitu buffer, kanal, switch, dan kendali yang bekerja bersama-sama untuk mengirimkan data. Terminal-terminal (dilabelkan dengan T1 sampai T6) dihubungkan pada jaringan dengan menggunakan kanal. Arah panah pada masing-masing ujung kanal mengindikasikan bahwa jaringan tersebut bidireksional, yaitu merupakan hubungan timbal balik dari data yang masuk maupun yang keluar dari jaringan interkoneksi. Jaringan interkoneksi digunakan pada hampir semua sistem digital yang cukup besar yang memiliki dua komponen untuk berhubungan. Aplikasi paling umum dari jaringan interkoneksi berada pada sistem komputer dan switch-switch komunikasi. Pada sistem komputer, aplikasi jaringan interkoneksi tersebut menghubungkan

prosesor

ke

memori

dan

peralatan

masukan/keluaran

(input/output (I/O)) menuju pengendali keluaran/masukan. Jaringan interkoneksi tersebut menghubungkan port masukan menuju port keluaran pada switch-switch komunikasi

dan

router

jaringan.

Jaringan

interkoneksi

tersebut

juga

menghubungkan sensor dan actuator ke prosesor di sistem kendali. Dimana saja bit-bit tersebut diangkut antara dua komponen dari sistem, suatu jaringan interkoneksi kerap ditemukan.


2.2

Switching Komponen utama dari sistem switching atau sentral adalah seperangkat

sirkuit masukan dan keluaran yang disebut dengan inlet dan outlet. Fungsi utama dari sistem switching adalah membangun jalan listrik diantara sepasang inlet dan outlet tertentu, dimana perangkat yang digunakan untuk membangun koneksi seperti itu disebut matriks switching atau jaringan switching . Jaringan switching tidak membedakan antara inlet/outlet yang tersambung ke pelanggan maupun ke trunk. Sebuah sistem switching tersusun dari elemenelemen yang melakukan fungsi-fungsi switching, kontrol dan signaling. Perkembangan yang terjadi pada sistem transmisi dimana dengan ditemukannya sistem transmisi serat optik, menyebabkan peningkatan kecepatan transmisi dan menyebabkan adanya tuntutan akan suatu rancangan sistem switching yang sesuai dengan kebutuhan transmisi tersebut. Rancangan elemen switching yang dibutuhkan adalah rancangan yang dapat meneruskan paket data secara cepat, dapat dikembangkan dengan skala yang lebih besar dan dapat secara mudah untuk diimplementasikan. Suatu elemen switching dapat digambarkan sebagai suatu elemen jaringan yang menyalurkan paket data dari terminal masukan menuju terminal keluaran. Kata terminal dapat berarti sebagai suatu titik yang terdapat pada elemen switching. Dari pengertian di atas dapat disimpulkan bahwa switching adalah proses transfer data dari terminal masukan menuju terminal keluaran. Gambar 2.3 menggambarkan suatu tipe dari elemen switching dimana terlihat bahwa suatu switch yang terdiri dari tiga komponen dasar yaitu: modul masukan, switching fabric, dan modul keluaran.


Modul Keluaran

Modul Masukan Switching Fabric

Masukan Modul Masukan

Keluaran Modul Keluaran

Gambar 2.3 Tipe Elemen Switching

Ketiga komponen switch tersebut dijelaskan sebagai berikut : 1. Modul masukan Modul masukan akan menerima paket yang datang pada terminal masukan. Modul masukan akan menyaring paket yang datang tersebut berdasarkan alamat yang terdapat pada header dari paket tersebut. Alamat tersebut akan disesuaikan dengan daftar yang terdapat pada virtual circuit yang terdapat pada modul masukan. Fungsi ini juga dilakukan pada modul keluaran. Fungsi lain dilaksanakan pada modul masukan adalah sinkronisasi, pengelompokan paket menjadi beberapa kategori, pengecekan error dan beberapa fungsi lainnya sesuai dengan teknologi yang ada pada switching tersebut. 2. Switching fabric Switching fabric melakukan fungsi switching dalam arti sebenarnya yaitu merutekan paket dari terminal masukan menuju terminal keluaran. Switching fabric terdiri atas jaringan transmisi dan elemen switching. Jaringan transmisi ini bersifat pasif dalam arti bahwa hanya sebagai saluran saja. Pada sisi lain elemen switching melaksanakan fungsi seperti internal routing.


3. Modul keluaran Modul keluaran berfungsi untuk menghubungkan paket ke media transmisi dan ke berbagai jenis teknologi seperti kontrol error, data filtering, tergantung pada kemampuan yang terdapat pada modul keluaran tersebut.

2.3

Jaringan Interkoneksi Komunikasi diantara terminal-terminal yang berbeda harus dapat

dilakukan dengan suatu media tertentu. Interkoneksi yang efektif antara prosesor dan modul memori sangat penting dalam lingkungan komputer. Menggunakan arsitektur bertopologi bus bukan merupakan solusi yang praktis karena bus hanya sebuah pilihan yang baik ketika digunakan untuk menghubungkan komponenkomponen dengan jumlah yang sedikit. Jumlah komponen dalam sebuah modul IC bertambah seiring waktu. Oleh karena itu, topologi bus bukan topologi yang cocok untuk kebutuhan interkoneksi komponen-komponen di dalam modul IC. Selain itu juga tidak dapat diskalakan, diuji, dan kurang dapat disesuaikan, serta menghasilkan kinerja toleransi kesalahan yang kecil. Di sisi lain, sebuah crossbar yang ditunjukkan pada Gambar 2.4 menyediakan interkoneksi penuh diantara semua terminal dari suatu sistem tetapi dianggap sangat kompleks, mahal untuk membuatnya, dan sulit untuk dikendalikan. Untuk alasan ini jaringan interkoneksi merupakan solusi media komunikasi yang baik untuk sistem komputer dan telekomunikasi. Jaringan ini membatasi jalur-jalur diantara terminal komunikasi yang berbeda untuk mengurangi kerumitan dalam menyusun elemen switching. Perhatikan Gambar 2.4.


P1

P2

... Pn M1

...

M2

Mn

Gambar 2.4 Arsitektur Crossbar Fungsi jaringan interkoneksi dalam sistem komputer dan telekomunikasi adalah untuk mengirimkan informasi dari terminal sumber ke terminal tujuan [1].

2.4

Karakteristik Jaringan Interkoneksi Berikut

ini

akan

dipaparkan

karakteristik

jaringan

interkoneksi

berdasarkan topologi, teknik switching, sinkronisasi, strategi pengaturan, dan algoritma perutean.

2.4.1 Topologi Topologi jaringan merujuk pada pengaturan statis dari kanal dan node dalam suatu jaringan interkoneksi, yakni jalur yang dijalani oleh paket. Memilih topologi jaringan adalah langkah awal dalam perancangan suatu jaringan karena strategi routing dan metode kendali aliran tergantung pada topologi jaringan. Suatu peta jalan diinginkan sebelum jalur dapat dipilih dan melintasi dari rute terjadwal. Topologi tidak hanya menetapkan tipe jaringan tapi juga detil-detilnya seperti radix dari switch, jumlah tingkatan, lebar dan laju bit pada kanal. Memilih topologi yang baik merupakan suatu pekerjaan yang dengan secara besar mencocokkan jaringan yang dibutuhkan dengan teknologi


pengemasan yang tersedia. Pada satu sisi, rancangan dikendalikan oleh jumlah port dan lebar pita serta faktor kerja per port dan di sisi yang lainnya oleh pin per chip dan papan yang tersedia oleh kepadatan dan panjang kawat atau kabel serta laju sinyal yang tersedia. Topologi dipilih berdasarkan biaya dan kinerjanya. Biayanya ditentukan oleh jumlah dan kompleksitas dari chip-chip yang dibutuhkan untuk merealisasikan jaringan, kepadatan, panjang dari interkoneksi pada papan atau melalui kabel antara chip-chip ini. Kinerja dari topologi ini memiliki dua kompenen, yaitu lebar pita dan latency. Keduanya ditentukan oleh faktor selain topologi, contohnya kendali alarm, strategi routing, dan pola trafik. Untuk mengevaluasi topologinya saja, dikembangkan pengukuran seperti bisectional bandwidth, kanal beban, dan penundaan jalur yang merefleksikan pengaruh yang kuat dari topologi kinerjanya. Bahaya umum yang tidak diinginkan bagi perancang jaringan yaitu mencoba untuk mencocokkan topologi jaringan ke komunikasi data dari permasalahan yang dihadapi. Pada permukaannya, ini seperti ide yang bagus, sesudahnya jika suatu mesin bekerja menghasilkan suatu algoritma membagi-bagi dan menaklukkan (divide and conquer algorithm) dengan pola komunikasi berstruktur pohon, tidakkah seharusnya suatu jaringan pohon menjadi optimum untuk mengatasi jalur ini? Jawabannya biasanya tidak. Untuk keragaman alasan, tujuan

khusus

jaringan

biasanya

menjadi

ide

yang

buruk.

Karena

ketidakseimbangan beban yang dinamis atau ketidaksesuaian antara masalah ukuran dan mesin, beban pada jaringan tersebut biasanya memiliki keseimbangan yang buruk. Jika data dan urutan dialokasikan pada beban yang seimbang, kecocokan antara masalah dan jaringan hilang. Suatu masalah yang menyangkut


jaringan yang spesifik biasanya tidak dipetakan secara baik untuk menyediakan teknologi pengemasan, membutuhkan saluran yang panjang atau derajat node yang tinggi. Akhirnya, jaringan-jaringan seperti itu menjadi tidak fleksibel. Jika algoritma dapat dengan mudah berubah menggunakan pola komunikasi yang berbeda, jaringan tidak dapat berubah dengan mudah. Ini menyebabkan selalu lebih mudah menggunakan suatu jaringan bertujuan umum yang baik daripada merancang jaringan dengan topologi yang cocok ke masalah.

2.4.2 Teknik Switching Secara umum digunakan tiga teknik switching, yaitu circuit switching, packet switching, dan message switching. Tetapi yang sering digunakan adalah circuit switching dan packet switching. Pada circuit switching, jalur antara sumber dan tujuan harus telah disediakan sebelum komunikasi terjadi dan koneksi ini harus tetap dijaga sampai pesan mencapai tujuannya. Setiap koneksi yang dibangun melalui jaringan circuit switching mengakibatkan dibangunnya kanal komunikasi fisik diantara terminal sumber dengan terminal tujuan. Kanal komunikasi ini digunakan secara khusus selama terjadi koneksi. Jaringan circuit switching juga menyediakan kanal dengan laju yang tetap. Pada hubungan circuit switching, koneksi biasanya terjadi secara fisik bersifat point to point. Kerugian terbesar dari teknik ini adalah penggunaan jalur yang bertambah banyak untuk jumlah hubungan yang meningkat. Efek yang timbul adalah biaya yang akan semakin meningkat disamping pengaturan switching menjadi sangat komplek. Kelemahan yang lain adalah munculnya idle


time bagi jalur yang tidak digunakan. Hal ini tentu akan menambah inefisiensi. Circuit switching mentransmisikan data dengan kecepatan yang konstan sehingga untuk menggabungkannya dengan jaringan lain yang berbeda kecepatan tentu akan sulit. Pemecahan yang baik yang bisa digunakan untuk mengatasi persoalan di atas adalah dengan metode packet switching. Dengan pendekatan ini, pesan yang dikirim dipecah-pecah dengan besar tertentu dan pada tiap pecahan data ditambahkan informasi kendali. Informasi kendali ini, dalam bentuk yang paling minim, digunakan untuk membantu proses pencarian rute dalam suatu jaringan sehingga pesan dapat sampai ke alamat tujuan. Contoh pemecahan data menjadi paket-paket data ditunjukkan pada Gambar 2.5 berikut ini.

Data

Header paket

Paket

Gambar 2.5 Pemecahan Data Menjadi Paket-Paket

Penggunaan packet switching mempunyai keuntungan dibandingkan dengan penggunaan circuit switching antara lain[2] :


1. Efisiensi jalur lebih besar karena hubungan antar node dapat menggunakan jalur yang dipakai bersama secara dinamis tergantung banyaknya paket yang dikirim. 2. Bisa mengatasi permasalahan laju data yang berbeda antara dua jenis jaringan yang berbeda laju datanya. 3. Saat beban lalu lintas meningkat, pada model circuit switching, beberapa pesan yang akan ditransfer dikenai pemblokiran. Transmisi baru dapat dilakukan apabila beban lalu lintas mulai menurun. Sedangkan pada model packet switching, paket tetap bisa dikirimkan, tetapi akan lambat sampai ke tujuan (delivery delay meningkat). 4. Pengiriman dapat dilakukan berdasarkan prioritas data. Jadi dalam suatu antrian paket yang akan dikirim, sebuah paket dapat diberi prioritas lebih.

2.4.3 Sinkronisasi Dalam suatu jaringan interkoneksi sinkron, kegiatan pada elemen switching dan terminal masukan maupun terminal keluaran (I/O) dikendalikan oleh sebuah clock pusat sehingga semuanya bekerja secara sinkron. Sedangkan pada jaringan interkoneksi asinkron tidak.

2.4.4 Strategi Pengaturan Pengaturan sebuah jaringan dapat dilakukan dengan cara terpusat ataupun terdistribusi. Dalam strategi pengaturan terpusat, sebuah pengendali pusat harus memiliki semua informasi global dari sistem pada setiap waktu. Ini akan menghasilkan dan mengirimkan sinyal kontrol kepada terminal yang berbeda pada


jaringan tergantung dari informasi yang dikumpulkan. Kompleksitas sistem bertambah dengan cepat seiring bertambahnya jumlah terminal dan dampaknya mengakibatkan sistem dapat berhenti. Berbeda dengan jaringan terdistribusi, pesan-pesan yang dirutekan mengandung informasi perutean yang dibutuhkan. Informasi ini ditambahkan kepada pesan dan akan dibaca dan digunakan oleh elemen switching untuk merutekan pesan-pesan tersebut sampai ke tujuan.

2.4.5 Algoritma Perutean Algoritma perutean tergantung pada sumber dan tujuan dari suatu pesan, jalur interkoneksi yang digunakan ketika melalui jaringan. Perutean dapat disesuaikan ataupun ditentukan. Jalur yang telah ditentukan mekanisme peruteannya tidak dapat diubah sesuai dengan trafik yang terjadi pada jaringan, artinya tidak dapat dialihkan ke rute yang berbeda apabila terjadi kepadatan trafik [1].

2.5

Klasifikasi Jaringan Interkoneksi Jaringan interkoneksi dapat dibagi menjadi statis atau jaringan langsung

(direct network), dinamis atau jaringan tidak langsung (undirect network), dan hybrid. Jaringan hybrid adalah jaringan interkoneksi yang memiliki struktur yang rumit. Untuk selanjutnya akan dibahas lebih tentang jaringan statis dan dinamis dan dalam Tugas Akhir ini difokuskan pada jaringan interkoneksi dinamis yaitu jaringan switching Clos. Gambar 2.6 menunjukkan klasifikasi jaringan interkoneksi [1].


2-D Mesh Mesh 3-D Mesh 1-D Unidirectional Torus or Ring Torus (k-ary n-Cube

2-D Bidirectional Torus 3-D Bidirectional Torus

Strictly Orthogonal Topologies Direct Networks

Hypercube Other Topologies: Trees, Cube-connecter Cycles, de Brujin Network, Star Graphs,etc

Unidirectional MIN

Crossbar Regular Topologies Interconnection Network

Indirect Networks

Blocking Networks Bidirectional MIN

Multistage Interconnection Networks Irregular Topologies

Non Blocking Networks

Multiple Backplane Buses Hybrid Networks

Hierarchical Networks

Cluster-Based Networks

Other Hypergraph Topologies: Hypercubes, Hypermeshes, etc

Gambar 2.6 Klasifikasi Jaringan Interkoneksi

2.5.1 Jaringan Interkoneksi Statis (Jaringan Langsung) Dalam jaringan interkoneksi statis, jalur diantara terminal yang berbeda dari sistem bersifat pasif dan hanya jalur yang telah ditentukan oleh prosesor pengendali yang dapat digunakan untuk berkomunikasi. Masing-masing terminal dihubungkan secara langsung ke terminal lain dengan jalur interkoneksi tertentu. Beberapa hal yang penting dalam topologi ini: -

Derajat terminal (node), yaitu jumlah jalur yang dihubungkan ke terminal yang menghubungkan tetangganya.

-

Diameter, yaitu jarak maksimum antara dua terminal dalam jaringan.

-

Regularity, yaitu sebuah jaringan yang teratur jika semua terminalnya memiliki derajat yang sama.

-

Simetris, yaitu sebuah jaringan simetrik jika terlihat sama dari masingmasing perspektif terminal.


Dalam jaringan statis, jalur pentransmisian pesan dipilih dengan algoritma perutean. Mekanisme switching menentukan bagaimana masukan dihubungkan ke keluaran dalam sebuah terminal. Semua teknik switching dapat digunakan dalam jaringan langsung. Jaringan statis yang paling sederhana adalah jaringan bus [1].

2.5.2 Jaringan Interkoneksi Dinamis (Jaringan Tidak Langsung) Jika dibandingkan dengan jaringan statis, jalur interkoneksi antar terminal yang pasif, konfigurasi jalur dalam sebuah jaringan interkoneksi dinamis merupakan fungsi dari kondisi elemen switching. Jalur diantara terminal pada jaringan interkoneksi dinamis berubah sesuai dengan perubahan kondisi elemen switching. Jaringan dinamis dibangun menggunakan crossbar (khususnya yang berukuran 2x2) [1].

(a)

Jaringan Interkoneksi Satu Tingkat Jaringan interkoneksi satu tingkat adalah sebuah jaringan dinamis yang

dibangun dari satu tingkat penghubung dan dua tingkat elemen switching. Gambar 2.7 menunjukkan skema umum jaringan interkoneksi satu tingkat. Crossbar yang menyediakan koneksi penuh antara semua terminal dari sistem merupakan jaringan interkoneksi non-blocking satu tingkat. Tingkat penghubung dalam Gambar 2.7 adalah fungsi permutasi atau pertukaran keluaran elemen switching ke tingkat yang terjauh ke kiri masukan elemen switching yang lain. Lebih dari satu jalur yang dibutuhkan melalui jaringan untuk komunikasi yang efektif antara sumber dan tujuan [1].


Tingkat Penghubung

SE

SE

SE

...

...

SE

...

...

...

...

SE

...

...

...

...

SE

Modul memory

Input Tingkat dari elemen switching

Gambar 2.7 Skema Jaringan Satu Tingkat

(b)

Jaringan Interkoneksi Banyak Tingkat Jaringan merupakan suatu gambaran berarah dimana node-nodenya terdiri

dari tiga bagian berikut: -

terminal sumber, yang memiliki indegree 0

-

terminal tujuan, yang memiliki outdegree 1

-

elemen switching, yang memiliki indegree dan outdegree positif Jaringan banyak tingkat adalah jaringan dimana terminal-terminalnya

dapat diubah pada tingkat-tingkatnya, dimana semua terminal sumber pada tingkat 0, dan semua keluaran pada tingkat i dihubungkan ke masukan pada tingkat i+1. Jika semua terminal tujuan dari jaringan banyak tingkat dihubungkan ke tingkat n+1, maka disebut jaringan n-tingkat. Jaringan uniform adalah jaringan banyak tingkat dimana semua elemen switching pada suatu tingkat yang sama memiliki jumlah terminal masukan dan


terminal keluaran yang sama. Jaringan square dengan derajat k adalah jaringan banyak tingkat yang dibangun dari elemen switching k x k. Jaringan network/MIN)

interkoneksi adalah

banyak

jaringan

tingkat

(Multistage

interkoneksi

yang

interconnection

digunakan

untuk

menghubungkan sekelompok N masukan ke sekelompok M keluaran melalui sejumlah tingkat perantara menggunakan elemen switching yang berukuran kecil diikuti oleh interkoneksi tingkat-tingkat penghubung. Secara formal, jaringan interkoneksi banyak tingkat merupakan rangkaian tingkat-tingkat elemen switching dan jalur interkoneksi. Arsitektur elemen switching yang paling umum adalah jaringan interkoneksi antara elemen-elemen switching itu sendiri yang berukuran lebih kecil. Elemen switching yang paling sering digunakan adalah hyperbar dan lebih lebih khusus lagi adalah crossbar. Tingkat-tingkat penghubung merupakan fungsi interkoneksi, masingmasing fungsi adalah bijeksi dari alamat elemen switching tingkat-tingkat sebelumnya yang menghubungkan semua keluaran elemen switching dari tingkat yang diberikan ke masukan dari tingkat berikutnya. Dalam lingkungan multiprosesor, link tingkat pertama dihubungkan ke sumber (biasanya prosesor) dan link tingkat terakhir dihubungkan ke tujuan (modul memory). Jumlah tingkat minimum jaringan interkoneksi banyak tingkat harus menyediakan koneksi penuh (full connection) dari terminal masukan ke terminal keluaran. Jaringan interkoneksi banyak tingkat secara umum ditunjukkan pada Gambar 2.8. Elemen switching pada jaringan interkoneksi banyak tingkat boleh memiliki buffer masukan ataupun buffer keluaran. Buffer berfungsi sebagai penyimpanan sementara untuk pesan-pesan yang diblok ketika konflik terjadi.


Dalam kasus ini disebut jaringan interkoneksi banyak tingkat dengan buffer. Sedangkan jaringan interkoneksi banyak tingkat tanpa buffer merupakan jaringan interkoneksi banyak tingkat yang paling sederhana. Seperti yang ditunjukkan pada Gambar 2.8, jaringan interkoneksi banyak tingkat memiliki N masukan dan M keluaran. Jaringan interkoneksi banyak tingkat memiliki n tingkat, G0 sampai Gn-1. Masing-masing tingkat Gi memiliki Wi elemen switching yang berukuran ai,j x bi,j dimana 1≤j≤W i, dengan demikian tingkat Gi memiliki pi terminal masukan dan qi terminal keluaran sehingga [1]: Wi

p i = ∑ a i, j

Wi

dan

j=1

q i = ∑ b i , j ...................................(2.1) j=1

Tingkat-tingkat dari link/jalur interkoneksi

C0

C2

SE

SE

SE

SE

...

...

Cn

SE

SE

...

... G0

SE

G1

SE

...

...

... SE

Gn-1

Tingkat-tingkat dari elemen-elemen switching Ket: SE = Switching Element = Elemen Switching

Gambar 2.8 Arsitektur Jaringan Interkoneksi Banyak Tingkat


M terminal

...

...

...

...

... Prosesor

Cn-1

...

... N terminal

C1

Modul memory

Pola koneksi antara dua tingkat yang berbatasan atau berdekatan, Gi-1 dan Gi yang ditunjukkan Ci, menggambarkan pola koneksi untuk link pi = qi-1 dimana p0 = N dan qn-1 = M. Dengan demikian sebuah jaringan interkoneksi banyak tingkat dapat ditunjukkan sebagai [1]:

C0(N)G0(W0)C1(p1)G1(W1) . . . Gn-1(Wn-1)Cn(M) …………….(2.2)

Dimana C0 adalah pola koneksi dari sumber ke tingkat switching pertama dan Cn adalah pola koneksi dari tingkat switching terakhir ke tujuan. Pola koneksi Ci(pi) menggambarkan bagaimana link-link pi seharusnya dihubungkan ke keluaran qn-1 = pi dari tingkat Gi-1 dan masukan pi ke tingkat Gi. Pola koneksi yang berbeda memberikan perbedaan karakteristik dan topologi jaringan interkoneksi banyak tingkat. Link-link itu diberi label dari 0 sampai pi-1 pada Ci [1].

2.6

Klasifikasi Jaringan Interkoneksi Banyak Tingkat Penggolongan jaringan interkoneksi banyak tingkat berdasarkan defenisi-

defenisi yang telah diberikan ditunjukkan pada Gambar 2.8. Jaringan interkoneksi banyak tingkat telah digolongkan ke dalam tiga kelas menurut ketersediaan jalurjalur untuk membangun koneksi baru, yaitu [1]: 1. Blocking. Suatu koneksi antara pasangan masukan/keluaran yang bebas tidak selalu mungkin dikarenakan konflik dengan koneksi yang sudah ada. Pada umumnya, ada suatu jalur yang unik antara setiap pasangan masukan/keluaran, dengan memperkecil jumlah elemen switching dan


tingkat. Jaringan dengan satu jalur (unipath network) disebut juga sebagai jaringan switching banyan. Jaringan switching banyan digambarkan sebagai suatu kelas dari jaringan interkoneksi banyak tingkat dimana ada satu dan hanya satu jalur dari setiap terminal masukan ke setiap terminal keluaran. Dengan menyediakan jalur yang banyak (multiple path) dalam jaringan blocking (blocking network), konflik dapat dikurangi dan toleransi kesalahan dapat ditingkatkan. Jaringan-jaringan blocking ini juga dikenal sebagai jaringan banyak jalur (multipath network). 2. Non-blocking. Setiap masukan dapat dihubungkan ke terminal keluaran yang

bebas

tanpa

mempengaruhi

koneksi-koneksi

yang

ada.

Membutuhkan tingkat-tingkat tambahan dan memiliki jalur yang banyak antara setiap masukan dan keluaran. Contoh yang popular dari jaringan non-blocking adalah jaringan Clos. 3. Rearrangable. Setiap terminal masukan dapat dihubungkan ke setiap keluaran yang bebas. Bagaimanapun, koneksi-koneksi yang ada boleh menggunakan jalur-jalur yang dapat diubah-ubah. Jaringan-jaringan ini juga membutuhkan jalur yang banyak antara setiap masukan dan keluaran, tetapi jumlah jalur dan biaya lebih kecil daripada penggunaan jaringan non-blocking. Berdasarkan jenis saluran (channel) dan elemen switching, jaringan interkoneksi banyak tingkat dapat juga dibagi menjadi: 1. Jaringan interkoneksi banyak tingkat satu arah (unidirectional), kanalkanal dan elemen-elemen switchingnya satu arah.


2. Jaringan interkoneksi banyak tingkat dua arah (bidirectional), kanal-kanal dan elemen-elemen switchingnya dua arah. Ini menunjukkan bahwa informasi dapat dikirimkan secara simultan (bersamaan) dengan arah yang berlawanan antara elemen switching yang bersebelahan.


BAB III JARINGAN SWITCHING CLOS TANPA BUFFER

3.1

Umum Jaringan Clos dinamakan dari Charles Clos yang memperkenalkan

jaringan ini di paper yang berjudul “A Study of Non-Blocking Switching Networks,” yang diterbitkan oleh jurnal Bell System Technical pada Maret 1953[3]. Pada bidang komunikasi, jaringan Clos adalah jaringan switching banyak tingkat yang pertama kali dirumuskan oleh Charles Clos pada tahun 1953, yang merepresentasikan suatu teori yang ideal dari sistem switching telepon banyak tingkat secara praktek. Jaringan Clos dibutuhkan ketika secara fisik sirkuit switching akan memperbesar kapasitas dari switch crossbar tunggal yang tersedia. Salah satu keuntungan dari jaringan Clos adalah jumlah crosspoint (yang menyusun masing-masing switch crossbar) yang dibutuhkan dapat lebih sedikit dari pada keseluruhan sistem yang diimplementasikan dengan satu switch crossbar yang besar. Ketika jaringan Clos pertama kali ditemukan, jumlah crosspoint merupakan suatu indikasi yang layak atas keseluruhan biaya dari sistem switching.

3.2

Cara Membangun Sistem Jaringan Clos yaitu jaringan tiga tingkat yang setiap tingkatnya tersusun

dari suatu jumlah dari switch crossbar. Clos asimetris dikarakterisasi oleh (m, n, r) dimana m adalah jumlah dari switch antara, n adalah jumlah port masukan dari


masing-masing switch masukan (keluaran), dan r adalah jumlah dari switch masukan dan switch keluaran dari switch antara. Pada jaringan Clos, masingmasing switch antara memiliki satu masukan dari setiap switch masukan dan satu link keluaran dari untuk setiap switch keluaran. Dengan demikian, switch masukan r adalah crosbar n × m untuk menghubungkan port-port masukan n ke switchswitch antara m, switch-switch antara m adalah crossbar r × r untuk menghubungkan switch masukan r ke switch keluaran r, dan switch keluaran r adalah crossbar m × n untuk menghubungkan switch antara m ke port keluaran n. Sebagai contoh, suatu jaringan Clos (3,3,4) ditunjukkan oleh Gambar 3.1 dan jaringan Clos (5,3,4) ditunjukkan oleh Gambar 3.2[4].

Gambar 3.1 Jaringan Switching Clos (3,3,4)


Gambar 3.2 Jaringan Switching Clos (5,3,4)

Gambar 3.1 menunjukan suatu jaringan Clos simetris (m = 3, n = 3, r = 4) memiliki r = 4 n × m switch masukan, m = 3 r × r switch antara, dan r = 4 m × n switch keluaran. Semua switch yang ada merupakan switch crossbar. Jaringan Clos (5,3,4) adalah jaringan yang bersifat strictly non-blocking untuk trafik unicast. Seringnya berguna untuk memvisualisasikan koneksi all-to-all antara tingkatan dari jaringan Clos di tiga dimensi seperti yang ditunjukkan oleh Gambar 3.3. Switch-switch masukan dan keluaran dapat dianggap sebagai trafik yang bergerak horizontal menuju dan dari switch antara yang vertikal. Switch antara menggerakkan trafik secara vertikal dari switch masukan horizontal menuju switch

keluaran horizontal.

Susunan

persilangan

ini

juga


jalan

yang

berguna untuk memaketkan jaringan Clos yang kecil sebagaimana susunan tersebut menjaga semua koneksi antara tingkatan tetap pendek. Properti dari suatu jaringan Clos (m, n, r) dengan terminal N = r n mengikuti dari topologi. Jaringan Clos tersebut dapat dibagi dua baik itu secara horizontal maupun vertikal, seperti yang digambarkan pada Gambar 3.3, memberikan pembagian menjadi dua dari BC = mr untuk horizontal yang memotong melalui switch antara atau BC = 2nr = 2N untuk vertikal yang memotong melalui switch masukan dan switch keluaran.

Dalam

prakteknya,

kebanyakan

jaringan

dipaketkan

dengan

menempatkan switch masukan dan keluaran dan memotong semua kanal interswitch BC = 2N. Derajat dari switch masukan dan keluaran adalah δio=n+m dan dari switch antara δm = 2r.

Gambar 3.3 Koneksi All-to-All Antar Tingkatan Dari Jaringan Clos

Koneksi all-to-all antar tingkatan dari jaringan Clos lebih baik dimengerti dengan menggambar jaringan dalam tiga dimensi. Switch masukan menggerakkan trafik secara vertikal untuk memilih switch masukan, dan switch keluaran menggerakkan trafik secara horizontal untuk memilih port keluaran. Properti


paling menarik dari jaringan Clos dan satu dari properti non-blockingnya berasal yaitu perbedaan jalurnya. Untuk suatu jaringan Clos dengan m switch antara, ada rute |Rab| = m dari masukan a manapun ke keluaran b manapun, satu melalui masing-masing switch antara. Dalam routing pada sirkuit jaringan Clos, satu-satunya keputusan bebas terletak pada switch masukan dimana switch antara m mana yang dapat dipilih selama link yang menuju ke switch antara tersedia. Switch antara harus memilih link tunggal yang menuju ke switch keluaran (dan rute yang tidak mungkin jika link ini sibuk). Dengan cara yang sama, switch keluaran harus memilih port keluaran terpilih. Dengan demikian, permasalahan routing pada jaringan Clos akan berkurang dalam penempatan masing-masing sirkuit (paket) menuju switch antara.

3.3

Pemaketan Panggilan Pada prakteknya, blocking yang lebih sedikit diperoleh ketika link tidak

dialokasikan pada wilayah yang acak daripada ketika mereka dialokasikan pada wilayah yang acak. Kesempatan dari suatu panggilan terblok diperkecil jika jumlah kemungkinan jalur yang tersedia menuju ke sana dapat lebih besar. Jadi, jika masing-masing panggilan yang akan disusun dirutekan melalui bagian yang memiliki beban paling berat dari jaringan yang masih dapat melayaninya, panggilan berikutnya akan memiliki pilihan yang lebih besar dari jaringan daripada jika sebuah panggilan dirutekan melalui bagian dari jaringan yang memiliki beban yang lebih sedikit. Ini dikenal sebagai pemaketan panggilan (call packing)[5].


Pemaketan panggilan yang sederhana dapat diaplikasikan ke jaringan tiga tingkat seperti yang ditunjukkan pada Gambar 3.4 adalah untuk memilih jumlah terendah dari switch antara yang memiliki link bebas menuju switch masukan dan keluaran. Jadi, switch antara 2 hanya digunakan jika link A atau link B yang menuju switch 1 sedang sibuk, dan selanjutnya

Gambar 3.4 Interkoneksi Penuh Jaringan Switching Tiga Tingkat Ketika pemaketan panggilan digunakan, panggilan ditawarkan ke switchswitch dengan urutan yang telah ditetapkan sebelumnya. Pilihan yang salah di awal pengiriman dapat menyebabkan penurunan yang cukup serius dari pelayanan selama periode trafik rendah. Ini adalah kerusakan dari sistem Strowger yang terkenal. Untuk meniadakan hal ini, sistem pengendalian umum menggunakan switch-switch crosspoint biasanya menghasilkan fitur percobaan kedua. Ketika suatu percobaan untuk membangun koneksi gagal, penanda membuat percobaan kedua. Hal ini dilakukan untuk menghindari poin awal yang berbeda dari yang digunakan pada awal percobaan.


3.4

Karakteristik Blocking dari Jaringan Clos Hubungan antara nilai dari m dan n menegaskan karakteristik blocking dari

jaringan Clos. 3.4.1 Jaringan Clos yang bersifat strict-sense non-blocking Jika m ≥ 2n − 1 , jaringan Clos secara tepat non-blocking, yang berarti masukan yang tidak digunakan pada switch masukan dapat selalu dihubungkan pada keluaran yang tidak digunakan pada switch keluaran, tanpa perlu mengatur ulang panggilan yang ada. Ini adalah hasil yang dibentuk pada rumusan paper Clos klasik pada tahun 1953. Umpamakan ada terminal yang bebas pada masukan dari switch masukan dan hal ini harus disambungkan pada terminal bebas pada switch keluaran yang khusus. Pada kasus terburuk, n − 1 panggilan lain yang aktif pada switch masukan dipertanyakan, dan n − 1 panggilan lain yang aktif pada switch keluaran juga dipertanyakan. Umpamakan juga pada kasus terburuk, yaitu masing-masing panggilan ini lewat melalui switch antara yang berbeda. Karenanya, pada kasus terburuk dimana 2n − 2 dari switch antara, tidak dapat membawa panggilan baru. Maka itu, untuk meyakinkan strict-sense operasi nonblocking, switch antara yang lain dibutuhkan, membuat totalnya 2n − 1 . 3.4.2 Jaringan Clos yang bersifat rearrangebly non-blocking Jika m ≥ n , jaringan Clos merupakan jaringan non-blocking yang dapat disusun, yang berarti masukan yang tidak dipakai pada switch masukan dapat selalu dikoneksikan pada keluaran yang tidak digunakan pada switch keluaran, tapi agar hal ini mendapat tempat, panggilan yang ada boleh disusun ulang dengan menempatkan pangggilan yang ada tersebut pada switch antara jaringan Clos. Untuk membuktikannnya, cukup dengan mengumpamakan m=n, dengan


jaringan Clos yang sepenuhnya terpakai, yaitu panggilan r × n yang sedang dalam proses pemakaian.. Bukti menunjukkan bagaimana permutasi dari terminal masukan r × n pada terminal keluaran r × n dapat rusak/jatuh menjadi permutasi yang lebih kecil yang dapat diimplementasikan oleh switch crossbar individual pada jaringan Clos dengan m = n .

3.5

Jaringan Non-Blocking Jaringan non-blocking adalah jaringan yang memberikan keadaan bahwa

setiap saluran keluar yang bebas selalu dapat dicapai atau diduduki oleh setiap saluran masuk yang menginginkannya. Hal ini dapat diperoleh diantaranya dengan cara[6][7]: 1. Elemen switch bertingkat satu Pada Gambar 3.5 dapat terlihat elemen switch bertingkat satu.

Gambar 3.5 Elemen Switch Bertingkat Satu


Setiap saluran keluar yang bebas dapat dicapai (diduduki) oleh setiap saluran masuk yang mengingininya. Jumlah crosspoint = N2

2. Elemen switch bertingkat dua: Pada Gambar 3.6 dapat dilihat elemen switch tingkat 2.

Gambar 3.6 Elemen Switch Bertingkat Dua

Terdapat N saluran masuk (juga N saluran keluar) dan : Tingkat 1 : switch (A) Tingkat 2 : switch (B) Karena jumlah saluran masuk sama dengan jumlah saluran keluar, maka : N = kn = mp Misalkan : n < p, maka m < k


Bila jaringan tersebut adalah ”jaringan bebas rugi” berarti harus selalu dapat terjadi bahwa n saluran masuk switch (A) ke n saluran keluar dari suatu switch (B). Untuk ini haruslah : Setiap switch (A) terdapat n2 . m crosspoint Setiap switch (B) terdapat pnk crosspoint Jadi jumlah crosspoint total: k ⋅ n 2 m + m ⋅ pnk = N ⋅ nm + N 2 > N 2 .................................................. (3.1) Dari penjelasan tersebut didapat bahwa dalam lingkup jumlah crosspoint suatu jaringan switching dengan menggunakan dua tingkat tidak akan dapat lebih baik daripada 1 tingkat.

3. Elemen switch bertingkat tiga : Untuk jaringan tiga tingkat ini, Clos dapat menunjukkan bahwa jaringan bebas ruginya dapat dibuat dengan jumlah crosspoint yang lebih sedikit daripada jumlah crosspoint pada jaringan bebas rugi satu tingkat. Hal ini seperti ditunjukkan oleh Gambar 3.7. n  1− − n

A1

1

n  1− − n

1

. . .

1 1 1

. . .

1

. . .

2

. . .

. . .

k

. . .

. . .

. . .

m

C1

n  1− − n

. . .

. . .

n  1− − n

Ak

2

1

1

1

n  1− − n

A2

. . .

2

C2

n  1− − n

. . .

. . .

3

C3

(B) (A)

(C)

Gambar 3.7 Switching Clos Tiga Tingkat


Ada N saluran masuk (juga N saluran keluar) : N= kn Pada setiap switch (B) memiliki sejumlah k saluran masuk dan k saluran keluar.

Untuk jaringan bebas rugi, nilai switch antara harus lebih besar daripada switch masukan m > n, karena jika tidak demikian (misalnya m < n), maka akan selalu ada kemungkinan bahwa jika m saluran link dari salah satu berkas keluar switch A tertentu sibuk semua, maka (n - m) saluran masuk switch A tertentu yang bersangkutan, bila ingin keluar tidak akan mendapatkan saluran link lag, ini berarti terdapat blocking. Lain halnya jika m < n. Dalam hal ini setiap saluran masuk dari switch (A) tertentu akan selalu mendapatkan saluran link yang menuju ke salah satu switch (B). Tetapi dengan m > n tersebut belum menjamin tidak adanya blocking. Misalnya, satu saluran masuk switch A1 akan berhubungan dengan 1 saluran keluar switch C1. Ada kemungkinan seperti yang terlihat pada Gambar 3.8 bahwa (n - 1) saluran masuk dari switch A1 sudah berhubungan dengan (n - 1) saluran keluar yang bukan dari switch C1 dan (n - 1) saluran keluar switch C1 sudah berhubungan (dihubungi) dengan (dari) (n - 1) saluran masuk yang bukan dari switch A1 (dan saluran-saluran masuk ini memakai saluran link B yang berbeda), maka sejumlah (2n – 2) switch B sudah tak dapat dipakai lagi untuk hubungan satu saluran masuk switch A1 ke satu saluran keluar switch C1


sebelumnya. Dengan catatan dari switch B ke setiap switch A atau switch C hanya ada satu saluran link B.

Gambar 3.8 Blocking Pada Jaringan Tiga Tingkat Jadi jumlah minimum switch B untuk menjamin tidak adanya blocking adalah sebesar: m

= (2n - 2) + 1 = 2n – 1 ............................................................ (3.2)

Jadi jumlah crosspoint minimum : X3 (N, n) = 2 kn (2n - 1) + mk2 = (2n - 1) (2N + k2) = (2n - 1) N(2 + N/n2) , dimana N = kn .................................... (3.3) Untuk harga N tertentu, jumlah crosspoint tergantung dari jumlah saluran masuk per switch A = n. Untuk mencari minimumnya :


∂X 3 ( N , n) =0 ∂n

Jadi : 2n3 – Nn + N = 0

N=

2n 3 = 2n 2 , (untuk N besar) ...................................................... (3.4) n −1 1/2

N Diambil harga n =   , maka jumlah crosspoint total : 2

  N 1/2  X N,     2   

     N 1/2  N  = 2  − 1 × N 2 +    2     N     2  

  N 1/2  = 2  − 1 × {4 N}   2   = 4 × (2 ) × N 3/2 − 4N 1/2

{

= 2 × (2 × N )

3/2

}

− 2N

= 2 × (2N ) , pendekatan untuk N besar ...................... (3.5) 3/2

Jadi satu tingkat dapat lebih banyak jumlah crosspoint-nya dari pada tiga tingkat.

3.6

Jaringan Clos yang umum Lima tingkat jaringan bebas rugi dapat dibuat dengan mengganti setiap switch B dengan tiga tingkat jaringan yang bebas rugi seperti yang terlihat di Gambar 3.9.


(E)

(A)

1

1 . . .

1

n

(B C D)

. . . . . .

1

. . .

1

. . .

n

. . .

1

1 . . .

2

n

. . .

. . .

2

. . .

. . .

2

. . .

n

. . .

1 k

n

. . .

. . .

m

. . .

1 . . .

Gambar 3.9 Contoh sederhana jaringan switching Clos

Misalnya: Jumlah switch A = k Saluran masuk switch A = n Saluran keluar switch A = 2n – 1 Jumlah switch BCD = 2n -1 Saluran masuk switch BCD = k

Misalnya di dalam switch BCD : Jumlah switch B ada : k1 Saluran masuknya : n1 Saluran keluarnya : (2n1 - 1)


3

. . .

n

D-E simetris seperti B-A dan setiap switch C memiliki: Saluran masuk: k1 Saluran keluar: k1 Maka setiap switch B-C-D memiliki crosspoint sebesar: 

(2n 1 − 1)k 2 = 

k n12

  ............................................ (3.6) 

Jadi jumlah crosspoint total X 5 (N , n, n1 )

 k  = 2kn(2n − 1) + (2n − 1)(2n1 − 1)k ×  2 + 2  n1    k  = (2n − 1) + (2n − 1)(2n1 − 1)k ×  2 + 2  n1  

{

}

= 2n × k (2n − 1) + 2n1 k1 (2n1 − 1) + k12 (2n1 − 1) × (2n − 1)  k2  = 2kn (2n − 1) + (2n − 1)(2n1 − 1)k × 2 + (2n1 − 1) 2  n1    k = 2kn(2n − 1) + (2n − 1)(2n1 − 1)k  2 + 2 n1 

 N N = (2n − 1)2 N + (2n1 − 1)  2 + n n × n12  Terdapat :

3.7

  

  .................... (3.7) 

n  ∂x ∂x = =0  n1  ∂n ∂n1

Probabilitas Blocking Pada Jaringan Clos Probabilitas blocking dari jaringan switching adalah probabilitas suatu

pasangan masukan keluaran bebas yang tidak dapat disambungkan. Untuk menghitung probabilitas blocking, model sederhana dari jaringan Clos tiga tingkat


digunakan dua metode yang telah terbukti keakuratannya, yaitu metode Lee dan Jacobeus[8].

3.7.1 Metode Lee Pendekatan pertama diperkenalkan oleh C. Y. Lee. Dimana jika ρ adalah probabilitas yang diberikan oleh link masukan dan keluaran sibuk, probabilitas link yang diberikan sibuk antara switch masukan, keluaran dan antara adalah up/m. Dengan u adalah jumlah dari link potensial aktif pada switch masukan dan keluaran yang akan membawa panggilan baru yang memungkinkan (u = n - 1). Probabilitas dari jalur istimewa itu bebas antara switch masukan dan keluaran yang ditanyakan adalah (1-up/m)2. Karena ada jalur potensial m yang melalui jaringan Clos, probabilitas blockingnya kira-kira [1 - (1 - up/m) 2 ] m . Asumsi telah dibuat bahwa semua link dalam jaringan bersifat independen; jika suatu link tertentu dengan digunakan, tidak berpengaruh apakah link lainnya digunakan. Ini memberikan perkiraan tinggi dari probabilitas blocking.

Secara ringkasnya dapat dituliskan demikian:

ρ

= probabilitas yang diberikan oleh link masukan dan keluaran sibuk

u ρ /m = probabilitas link yang diberikan sibuk antara switch masukan, keluaran dan antara u

= n -1, jumlah dari link potensial aktif pada switch masukan dan keluaran

yang akan membawa panggilan baru yang memungkinkan. (1-u ρ /m)2

= Probabilitas dari jalur istimewa itu bebas antara switch masukan

dan keluaran yang ditanyakan


Jadi, probabilitas blockingnya adalah: Pb = [1 - (1 - uρ/m) 2 ] m ....................................... (3.8)

3.7.2 Metode Jacobeus Pada metode Jacobeus, asumsi link independen yang disebutkan di atas sedang tenang, sehingga trafik pada satu sisi jaringan hanya independen dari sisi lainnya. Seperti biasa, jumlah jalur yang dapat dipilih dari a diindikasikan oleh: a a! ................................................. (3.9)   =  b  b!(b − a )!

Pada awalnya, diasumsikan ada i panggilan masuk yang telah memasuki switch tingkat pertama sebagaimana masukan yang disambungkan,, dan ada j panggilan yang pergi meninggalkan jaringan Clos (panggilan keluar) melalui switch keluaran yang sama sebagaimana terminal keluaran bebas tersambung. Karena itu, 0 ≤ i ≤ u dan 0 ≤ j ≤ u . Lebih jauh, untuk tujuan perhitungan, diasumsikan

bahwa tugas manapun dari panggilan keluar menuju switch antara mungkin adanya, tapi tugas dari panggilan menuju switch antara telah ditentukan; hanya konfigurasi yang berhubungan dari switch masukan dan switch keluaran yang saling terkait. m Ada   cara untuk menetapkan panggilan keluar j menuju switch antara  j  i m;  m −

  i  dari hasil blocking, dimana  j m −

sejumlah (m − j ) switch

antara yang

  adalah jumlah cara dimana j 

tersisa dapat

bertepatan dengan

sejumlah (m − j ) dari panggilan ini. Probabilitas bahwa blocking muncul menjadi: Aprianty Prima S.U. Siregar : Analisis Kinerja Jaringan Switching Clos Tanpa Buffer, 2009.

β ij

 i  i!   m − j  (m − j )!(i + m − j ) i! j!( j − m)! × =  = = m! (m − j )!(i + m − j ) m! m   j!( j − m)!  j =

i! j! .................................................................................. (3.10) m!(1 + m − j )!

Perhitungan tersebut berlaku jika i + j ≥ m jika i + j < m , maka β ij = 0 . Hal ini secara implisit termasuk hasil Clos karena i ≤ u dan j ≤ u , jadi i + j tidak boleh lebih besar daripada 2u = 2n − 2 dan untukk jaringan Clos yang bersifat strict sense non-blocking, β ij selalu bernilai 0 (nol), dimana dapat dituliskan β ij = 0 .

Rumus probabilitas blocking yang dicetuskan oleh Jacobeus yaitu: u

u

PB = ∑∑ f i g j β ij .......................................... (3.11) i =0 j =0

dimana: u  u −i f i =   ρ i (1 − ρ ) i

.........................................

(3.12) u  u− j g j =   ρ j (1 − ρ ) ....................................... (3.13)  j Keterangan: fi adalah probabilitas bahwa telah ada i link aktif pada switch masukan. gi adalah probabilitas bahwa telah ada j link aktif pada switch keluaran.


Probabilitas blocking menjadi:

ρm (u!) 2 (2 − ρ ) ................................ (3.14) m!(2u − m)! 2u − m

PB =

Nilai-nilai yang cukup besar untuk difaktorialkan, tidak dapat dilakukan dengan perhitungan manual, maka akan dipakai program perhitungan dengan menggunakan software MATLAB 7.0.4. yang dapat dilihat pada Lampiran A. 3.8

Jaringan Benes Jaringan Benes adalah jaringan Clos yang bersifat rearrangebly non-

blocking dengan m = n = 2. Asumsikan bahwa N pada Gambar 8 adalah daya integral dari 2. Jika N = 4 , masing-masing switch antara adalah switch 2 × 2 . Jika N > 4 , masing-masing switch antara dapat digantikan dengan jaringan

Benes N / 2 × N / 2 . Dengan mengulangi substitusi ini, suatu jaringan Benes yang bersifat rearangebly non-blocking dari ukuran yang berubah-ubah dapat dibuat. Jaringan ini diatur dalam tingkat 2 log 2 N − 1 dari switch-switch N / 2 , dimana

log 2 N adalah suatu logaritma dengan basis 2. Contohnya, log 2 2 = 1 , log 2 4 = 2 , log 2 8 = 3 . Total angka dari switch yang dibutuhkan adalah N log 2 N − N / 2 , dapat ditunjukkan bahwa ini sangat dekat dengan teori lower bound untuk operasi non-blocking. Contoh-contoh jaringan switching Clos yang telah difabrikasi dapat dilihat pada Lampiran B.

3.9

Keuntungan dan Kerugian menggunakan jaringan switching Clos

Keuntungan: a) Menyediakan banyak jalur switch antara tiap pasang node.


b) Perbedaan jalur memungkinkan jaringan Clos untuk merutekan pola trafik yang berubah-ubah tanpa kehilangan throughput. Kerugian: a) Harga pembangunan tipe Clos ini mendekati dua kali biaya jaringan dengan tipe yang berbeda, seperti jaringan Butterfly dengan kapasitas yang sama. b) Redaman yang lebih besar daripada jaringan lainnya, misalnya jaringan Butterfly.


BAB IV ANALISIS KINERJA JARINGAN SWITCHING CLOS TANPA BUFFER

4.1

Umum Karakteristik dari sebuah sistem multiprocessor adalah kemampuan dari

setiap prosesornya untuk berbagi dengan sebuah memori tunggal. Kemampuan berbagi ini diwujudkan melalui sebuah jaringan interkoneksi antara prosesor dan modul memori. Model dari sistem ini dapat dilihat pada Gambar 4.1. Prosesor 1

Prosesor 2

Prosesor n

Memori 1

Switch Interconnection network

Memori 2

Memori n

Gambar 4.1 Model Interkoneksi Antara Prosesor dan Memori Fungsi dari sebuah switch interkoneksi adalah untuk membuat sebuah jalur yang tersedia antara tiap – tiap prosesor dan tiap – tiap modul memori. Pada Tugas Akhir ini jaringan interkoneksi yang ditawarkan sebagai penghubung antara prosesor dan modul memori tersebut adalah jaringan switching Clos. Tugas akhir ini bertujuan untuk menganalisis kinerja jaringan switching Clos. Kinerja yang diukur dalam tugas akhir ini adalah probabilitas blocking. Probabilitas blocking yang dihitung adalah probabilitas dengan metode Lee dan metode Jacobeus. Jaringan switching Clos yang dibahas ini merupakan jaringan tanpa buffer, yang berarti jika ada paket – paket yang membutuhkan keluaran yang sama, maka akan


dipilih salah satu paket secara acak yang akan diteruskan. Sedangkan sisa paket yang lain akan terblok atau terbuang.

4.2

Perhitungan

Analisis

Kinerja

Probabilitas

Blocking

Jaringan

Switching Clos Kinerja probabilitas blocking yang dihitung di sini adalah metode dari Lee dan Jacobeus yang telah dipaparkan di Bab III.

4.2.1 Analisis Kinerja dengan Metode Lee Pada analisis ini, akan dihitung besarnya probabilitas blocking (Pb) metode Lee yang dihasilkan oleh jaringan switching Clos dengan mengambil mengambil harga ρ =0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, dan 0.95 masing-masing untuk n=64, m=64; n=64, m=68; n=64, m=72; n=64, m=72; n=64, m=76; n=120, m=128; n=240, m=256. Probabilitas blocking metode Lee diperoleh dengan menggunakan persamaan (3.8).

Untuk ρ = 0.6 ; n = 64 ; u = n -1 = 63 ; m = 64 Pb = [1 - (1 -

63 × 0.6 2 64 ) ] = 7.97365 × 10-6 64

n = 64 ; u = n -1 = 63 ; m = 68 Pb = [1 - (1 -

63 × 0.6 2 68 ) ] = 3.24946 × 10-7 68

n = 64 ; u = n -1 = 63 ; m = 72 Pb = [1 - (1 -

63 × 0.6 2 72 ) ] = 1.0104 × 10-8 72


n = 64 ; u = n -1 = 63 ; m = 76 Pb = [1 - (1 -

63 × 0.6 2 76 ) ] = 2.44531 × 10-10 76

n = 120 ; u = n -1 = 119 ; m = 128 Pb = [1 - (1 -

119 × 0.6 2 128 ) ] = 8.04037 × 10-13 128

n = 240 ; u = n -1 = 239 ; m = 256 Pb = [1 - (1 -

239 × 0.6 2 256 ) ] = 1.24705 × 10-24 256

Dan seterusnya untuk p=0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95 dapat dilihat di Tabel 4.1 dan Tabel 4.2. Tabel 4.1 Nilai Probabilitas Blocking Metode Lee Untuk p = 0.6, 0.65, 0.7, 0.75 n

m

ρ=0.6

ρ=0.65

ρ=0.7

ρ=0.75

64

64

7.97365 × 10-6

64

68

0.000137536

0.001492102

0.010661083

3.24946 × 10

8.18084 × 10

0.000127663

0.001298852

72

1.0104 × 10

-7

64

3.68008 × 10

8.17361 × 10

0.000116929

64

76

2.44531 × 10

-08

1.2795 × 10

-7

4.01141 × 10

7.99058 × 10-6

120

128

8.04037 × 10-13

3.41629 × 10-10

5.89152 × 10-8

4.53449 × 10-6

240

256

1.24705 × 10-24

2.14205 × 10-19

6.04042 × 10-15

3.37993 × 10-11

-7

-8 -10

-6

-6

Tabel 4.2 Nilai Probabilitas Blocking Metode Lee Untuk p = 0.8, 0.85, 0.9, 0.95 n

m

ρ=0.8

ρ=0.85

ρ=0.9

ρ=0.95

64

64

0.051959842

0.17738246

0.432522804

0.763632291

64

68

0.008959429

0.043191378

0.148940434

0.373855794

64

72

0.001124554

0.007520035

0.035902633

0.124921249

64

76

0.00010592

0.000969279

0.006305317

0.029843898

120

128

0.000167645

0.003151492

0.031464537

0.172366454

240

256

4.34543 × 10

1.43758 × 10

0.001334423

0.037069835

-8

-5

4.2.1 Analisis Kinerja dengan Metode Jacobeus Pada analisis ini, akan dihitung besarnya probabilitas blocking (Pb) metode Jacobeus yang dihasilkan oleh jaringan switching Clos dengan mengambil mengambil


harga ρ =0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, dan 0.95 masing-masing untuk n=64, m=64; n=64, m=68; n=64, m=72; n=64, m=72; n=64, m=76; n=120, m=128; n=240, m=256. Probabilitas blocking metode Jacobeus diperoleh dengan menggunakan persamaan (3.14).

Untuk ρ = 0.6 ; n = 64 ; u = n -1 = 63 ; m = 64 Pb =

(63!)2 (2 − 0.6)2×63−64 0.6 64 64!×(2 × 63 − 64 )!

= 7.15779 × 10-6

n = 64 ; u = n -1 = 63 ; m = 68 Pb =

(63!)2 (2 − 0.6)2×63−64 0.6 68 68!×(2 × 63 − 68)!

= 1.65408 × 10-7

n = 64 ; u = n -1 = 63 ; m = 72 Pb =

(63!)2 (2 − 0.6)2×63−72 0.6 72 = 2.30125 × 10-9 72!×(2 × 63 − 72 )!

n = 64 ; u = n -1 = 63 ; m = 76 Pb =

(63!)2 (2 − 0.6)2×63−76 0.6 76 76!×(2 × 63 − 76 )!

= 1.91369 × 10-11

n = 120 ; u = n -1 = 119 ; m = 128 Pb =

(119!)2 (2 − 0.6)2×119−128 0.6128 = 2.41440 × 10-13 128!×(2 × 119 − 128)!

n = 240 ; u = n -1 = 239 ; m = 256 Pb =

(239!)2 (2 − 0.6)2×239−256 0.6 256 256!×(2 × 239 − 256 )!

= 1.3263e × 10-25

Dan seterusnya untuk p=0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95 dapat dilihat pada Tabel 4.3 dan Tabel 4.4.


Tabel 4.3 Nilai Probabilitas Blocking Metode Jacobeus Untuk ρ = 0.6, 0.65, 0.7, 0.75 ρ=0.6

ρ=0.65

ρ=0.7

n

m

64

64

7.15779 × 10

0.000125982

64

68

1.65408 × 10

64

72

64

-6

ρ=0.75

0.00139291

0.0101275

4.63779 × 10

-5

8.02094 × 10

0.000899065

2.30125 × 10-9

1.02789 × 10-7

2.78074 × 10-6

4.8052 × 10-5

76

1.91369 × 10-11

1.36169 × 10-9

5.76225 × 10-8

1.53508 × 10-6

120

128

2.41440 × 10-13

1.2445 × 10-10

2.5804 × 10-8

2.3621 × 10-6

240

256

1.3263e × 10-25

3.2766 × 10-24

1.3063 × 10-14

1.0121 × 10-11

-7

--6

Tabel 4.4 Nilai Probabilitas Blocking Metode Jacobeus Untuk ρ = 0.8, 0.85, 0.9, 0.95 n

m

ρ=0.8

ρ=0.85

ρ=0.9

Ρ=0.95

64

64

0.050136845

0.17347541

0.427590118

0.760690261

64

68

0.006783842

0.035465496

0.131253452

0.349163518

64

72

0.00055262

0.004365218

0.02425636

0.09648986

64

76

2.69076 × 10

0.000321147

0.002679407

0.015937956

120

128

2.3621 × 10

0.00223

0.02521

0.03016

240

256

1.7570 × 10

7.6150 × 10

-5

-6 -8

-6

8.9282 × 10

-4

0.0300

Data hasil perhitungan dengan n = 64 dan m = 64 dapat dilihat pada Tabel 4.5 dan Gambar 4.2.

Tabel 4.5 Perbandingan Antara Probabilitas Blocking Metode Lee dan Metode Jacobeus Dengan n=64 dan m=64 ρ

Pb Metode Lee

Pb Metode Jacobeus

0.6

0.00000797365

0.00000715779

0.65

0.000137536

0.000125982

0.7

0.001492102

0.00139291

0.75

0.010661083

0.0101275

0.8

0.051959842

0.050136845

0.85

0.17738246

0.17347541

0.9

0.432522804

0.427590118

0.95

0.763632291

0.760690261


n=64, m=64 0.9 0.8 0.7 0.6 Pb 0.5 0.4 0.3 0.2 0.1 0

Metode Lee Metode Jacobeus

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

ρ

Gambar 4.2 Perbandingan Antara Probabilitas Blocking metode Lee dan Jacobeus dengan n=64 dan m=64

Data hasil perhitungan dengan n = 64 dan m = 68 dapat dilihat pada Tabel 4.6 dan Gambar 4.3 berikut.

Tabel 4.6 Perbandingan antara probabilitas Blocking metode Lee dan metode Jacobeus dengan n=64 dan m=68 ρ Pb Metode Lee Pb Metode Jacobeus -7 3.25 × 10 1.65 × 10-7 0.6 8.18 × 10-6 4.64 × 10-6 0.65 0.000127663 0.0000802 0.7 0.001298852 0.000899065 0.75 0.008959429 0.006783842 0.8 0.043191378 0.035465496 0.85 0.148940434 0.131253452 0.9 0.3738557 0.349163518 0.95


n=64, m=68 4.00E-01 3.50E-01 3.00E-01 2.50E-01 Pb 2.00E-01 1.50E-01 1.00E-01 5.00E-02 0.00E+00

Metode Lee Metode Jacobeus

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

ρ Gambar 4.3 Perbandingan antara probabilitas Blocking metode Lee dan Jacobeus dengan n=64 dan m=68 Data hasil perhitungan dengan n = 64 dan m = 72 dapat dilihat pada Tabel 4.7 dan Gambar 4.4 berikut.

Tabel 4.7 Perbandingan Antara Probabilitas Blocking Metode Lee dan Jacobeus Dengan n=64 dan m=72 ρ Pb Metode Lee Pb Metode Jacobeus -8 0.6 1.01 × 10 2.30 × 10-9 0.65 3.68 × 10-7 1.03 × 10-7 0.7 8.17 × 10-6 2.78 × 10-6 0.75 0.000116929 0.0000481 0.8 0.001124554 0.00055262 0.85 0.007520035 0.004365218 0.9 0.035902633 0.02425636 0.95 0.124921249 0.09648986

1.40E-01 1.20E-01 1.00E-01 8.00E-02 6.00E-02 4.00E-02 2.00E-02 0.00E+00

Metode Lee

0. 9 0. 95

0. 8 0. 85

Metode Jacobeus

0. 7 0. 75

0. 6 0. 65

Pb

n=64, m=72

ρ

Gambar 4.4 Perbandingan Antara Probabilitas Blocking metode Lee dan Jacobeus Dengan n=64 dan m=72 Aprianty Prima S.U. Siregar : Analisis Kinerja Jaringan Switching Clos Tanpa Buffer, 2009.

Data hasil perhitungan dengan n = 64 dan m = 76 dapat dilihat pada Tabel 4.8 dan Gambar 4.5 berikut.

Tabel 4.8 Perbandingan Antara Probabilitas Blocking metode Lee dan Jacobeus dengan n=64 dan m=76 ρ Metode Lee Metode Jacobeus -10 2.45 × 10 1.91 × 10-11 0.6 1.28 × 10-8 1.36 × 10-9 0.65 4.01 × 10-7 5.76 × 10-8 0.7 7.99 × 10-6 1.54 × 10-6 0.75 0.00010592 0.0000269 0.8 0.000969279 0.000321147 0.85 0.006305317 0.002679407 0.9 0.029843898 0.015937956 0.95 n = 64, m=76 3.50E-02 3.00E-02

Pb

2.50E-02 2.00E-02

Metode Lee

1.50E-02

Metode Jacobeus

1.00E-02 5.00E-03 0.00E+00 0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

ρ

Gambar 4.5 Perbandingan Antara Probabilitas Blocking Metode Lee dan Jacobeus Dengan n=64 dan m=76



Tabel 4.9 Perbandingan Antara Probabilitas Blocking Metode Lee dan Metode Jacobeus dengan n=120 dan m=128 ρ 0.6

Metode Lee 8.04 × 10-13

Metode Jacobeus 2.41 × 10-13

0.65

3.42 × 10-10

1.24 × 1010

0.7

5.89 × 10-8

2.58 × 10-8

0.75

4.53 × 10-6

2.36 × 10-6

0.8

0.000167645

0.000002.36

0.85

0.003151492

0.00223

0.9

0.031464537

0.02521

0.95

0.172366454

0.03016

n=120, m=128 2.00E-01

Pb

1.50E-01 Metode Lee

1.00E-01

Metode Jacobeus

5.00E-02 0.00E+00 0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

ρ

Gambar 4.6 Perbandingan antara probabilitas Blocking metode Lee dan Jacobeus dengan n=120 dan m=128


Tabel 4.10 Perbandingan Antara Probabilitas Blocking Metode Lee dan Jacobeus Dengan n=240 dan m=256 ρ 0.6

Pb Metode Lee -24 1.25 × 10

Pb Metode Jacobeus 1.33 × 10-25

0.65

2.14 × 10-19

3.28 × 10-24

0.7

6.04 × 10-15

1.31 × 10-14

0.75

3.38 × 10-11

1.01 × 10-11

0.8

4.35 × 10-08

1.76 × 10-8

0.85

1.44 × 10-05

7.62 × 10-6

0.9

0.001334423

0.000893

0.95

0.037069835

0.03


n=240, m=256 4.00E-02 3.50E-02

Pb

3.00E-02 2.50E-02

Pb Metode Lee

2.00E-02 1.50E-02 1.00E-02

Pb Metode Jacobeus

5.00E-03 0.00E+00 0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

ρ

Gambar 4.7 Perbandingan Antara Probabilitas Blocking Metode Lee dan Jacobeus Dengan n=240 dan m=256

Dari tabel-tabel tersebut, didapatlah untuk pendekatan Lee dan Jacobeus, probabilitas blocking berkurang sebagaimana nilai m (jumlah switch antara) meningkat. Tabel tersebut juga menegaskan bahwa metode Lee menghasilkan nilai probabilitas Blocking yang lebih tinggi daripada hasil yang diperoleh dari metode Jacobeus. Juga untuk nilai switch masukan dan switch antara yang ditentukan, jika nilai ρ (probabilitas yang diberikan oleh link masukan dan keluaran sibuk) meningkat, maka nilai probabilitas blocking juga meningkat. Untuk selisih nilai switch masukan dan switch antara yang tidak terlalu besar, maka perbedaan nilai probabilitas blocking untuk metode Lee dan metode Jacobeus juga tidak terlalu besar, namun untuk selisih nilai switch masukan dan keluaran yang cukup besar, perbedaan antara nilai probabilitas blocking kedua metode tersebut juga menjadi cukup besar.


BAB V KESIMPULAN DAN SARAN

5.1

Kesimpulan Dari hasil analisis yang dilakukan, diperoleh kesimpulan sebagai berikut: 1. Untuk n = 64 dan m = 64 dengan p = 0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, nilai probabilitas blocking akan bertambah, baik itu dengan menggunakan metode Lee maupun dengan metode Jacobeus. Demikian juga halnya untuk n = 64 dan m = 68, n = 64 dan m = 72, n = 64 dan m = 76 , n = 120 dan m = 128, juga n = 240 dan m = 256. Ini membuktikan bahwa nilai probabilitas blocking meningkat ketika nilai p (probabilitas yang diberikan oleh link masukan dan keluaran sibuk) meningkat. 2. Dari tabel juga diperoleh, nilai probabilitas blocking semakin berkurang ketika jumlah switch antara-nya meningkat. 3. Selisih nilai probabilitas blocking antara metode Lee dan metode Jacobeus memiliki perbedaan hasil yang sangat kecil, 0.815 untuk n = m = 64 dan p = 0.6, dan memiliki selisih hasil 0.00294203 untuk p = 0.95 dan seterusnya untuk nilai-nilai yang telah dipaparkan pada BAB IV. 4. Jika selisih jumlah switch masukan dan switch antara tidak terlalu besar, kedua metode (Lee dan Jacobeus) dapat dipilih karena memperlihatkan kinerja yang hampir sama, tetapi apabila perbedaan


jumlah switch masukan dan antara semakin besar, metode Jacobeus menghasilkan kinerja yang lebih baik.

5.2

Saran Saran yang dapat Penulis berikan: 1. Analisis kinerja jaringan switching Clos dapat dibuat dengan metode simulasi dengan asumsi – asumsi yang realistik agar dapat diperoleh kinerja jaringan switching yang mendekati sebenarnya.


DAFTAR PUSTAKA

[1] Dally, William J. 2004. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers.

[2] Djajasugita, F. Ahmadi. 1990. Teknik Lalu Lintas: Diktat Kuliah. Bandung. hal 141-150.

[3] Douglass, Barry G., dan Oruq, A. Yavuz. “On Self-Routing in Clos Connection Networks”. IEEE Transactions on Communications Vol 41. Januari 1993. hlm. 121-124

[4] Flood, J. E. 1995. Telecommunications Switching, Traffic, and Networks, Edisi Pertama. Prentice Hall International (UK) Limited.

[5] Freeman, Roger L. 2005. Fundamentals of Telecommunications, Edisi Kedua. John Wiley & Sons Inc Publication.

[6] Imran Rafiq Quadri, Pierre Boulet, dan Jean Luc Dekeyser. Mei 2007 Modeling of Topologies of Interconnection Networks based on Multidimensional Multiplicity. Raport de Recherche, Institut National De Recherche En Informatique Et En Automatique..

[7] Jose Duato, Sudhakar Yalamanchili, dan Lionel Ni. 2003. Interconnection Networks. Morgan Kaufmann Publishers. USA. hal 23-31

[8]Schwartz, M.. 1987. Telecommunication Networks Protocols, Modeling and Analysis. Addison-Wesley Publishing Company, Inc, New York, USA,

[9] Viswanathan,Thiagarajan. 1992. Telecommunication Switching Systems and Networks, Edisi Pertama. Prentice-Hall of India Private Limited, New Delhi.


LAMPIRAN A

List program untuk menghitung nilai probabilitas Blocking metode Jacobeus untuk nilai faktorial pangkat tinggi. Khusus untuk kasus ini yang dapat dihitung adalah nilai dari n=240, m=256 dan p=0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, dan 0.95. Perhitungan ini dengan menggunakan program MATLAB 7.0.4.

%Maksimum nilai faktorial adalah 340 clear;clc; u=input('U = '); m=input('m = '); p=[0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95]; if u>170 u1=1:170; U1=prod(u1); u2=171:u; U2=prod(u2); else U=factorial(u); end if m>170 m1=1:170; M1=prod(m1); m2=171:m; M2=prod(m2); else M=factorial(m); end z=2*u-m; if z>170 z1=1:170; Z1=prod(z1); z2=171:z; Z2=prod(z2); else Z=factorial(z); Aprianty Prima S.U. Siregar : Analisis Kinerja Jaringan Switching Clos Tanpa Buffer, 2009.

end a=U1/M1;b=U2/M2;c=U1/Z1;d=U2/Z2; for i=1:length(p) e=((2-p(i))^(2*u-m))*p(i)^m; if u>170||m>170 Pb (i) = a*b*c*d*e; else Pb (i) = (U^2*e)/(M*Z); end disp(' '); disp(Pb(i)); end


LAMPIRAN B

Contoh jaringan switching Clos yang telah difabrikasi:

Contoh Jaringan Clos

Jaringan Clos Myrinet-2000 Untuk 128 Host Aprianty Prima S.U. Siregar : Analisis Kinerja Jaringan Switching Clos Tanpa Buffer, 2009.

TUGAS AKHIR ANALISIS KINERJA JARINGAN SWITCHING CLOS TANPA BUFFER

Recommend Documents