MODEL PROGRAM STOKASTIK DALAM RANCANGAN JARINGAN TELEKOMUNIKASI

MODEL PROGRAM STOKASTIK DALAM RANCANGAN JARINGAN TELEKOMUNIKASI

TESIS

Oleh

ANI MINARNI 067021001/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008

Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

MODEL PROGRAM STOKASTIK DALAM RANCANGAN JARINGAN TELEKOMUNIKASI

TESIS

Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

ANI MINARNI 067021001/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008


Judul Tesis

: MODEL PROGRAM STOKASTIK DALAM RANCANGAN JARINGAN TELEKOMUNIKASI Nama Mahasiswa : Ani Minarni Nomor Pokok : 067021001 Program Studi : Matematika

Menyetujui, Komisi Pembimbing

(Dr. Saib Suwilo, M.Sc) Ketua

(Dr. Sutarman, M.Sc) Anggota

Ketua Program Studi,

Direktur,

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 15 Juli 2008


Telah diuji pada Tanggal 15 Juli 2008

PANITIA PENGUJI TESIS

Ketua

: Dr. Saib Suwilo, M.Sc

Anggota

: 1. Dr. Sutarman, M.Sc 2. Dr. Tulus, M.Sc 3. Dra. Mardiningsih, M.Si


ABSTRAK Rancangan konvensional dan metoda optimisasi sedang mendapat tantangan dari cepatnya perkembangan jaringan telekomunikasi optik maupun elektronik. Menjadi penting untuk melibatkan keadan stokastik ke dalam model jaringan telekomunikasi karena permasalah yang muncul dalam jaringan ini umumnya bersifat random. Penelitian ini menelusuri metoda Program Stokastik (PS) untuk menandai track yang bersifat stokastik. Untuk masalah jaringan telekomunikasi di sini diusulkan model jaringan Multi-Komoditas ditinjau juga tiga tipe pendekatan PS, yaitu metode Here and Now, metoda Wait and See, dan metoda Skenario Tracking, melalui studi kasus suatu jaringan prototipe yang diintegrasikan ke dalam model Generik Flow Assignment (GFA). Diselidiki juga model dan bentuk sebaran/distribusi probabilitas untuk laju kedatangan (arrival rate) didasarkan pada sebaran waktu antar kedatangan (inter arrival rate). Implementasi model dilakukan dengan mengunakan software Program Stokastik. Kata Kunci : Optimisasi, Program Stokastik.

i Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

ABSTRACT Optimization methods and conventional designs nowadays are being challenged by the rapid development of either optic telecommunication or electronic networks. It is therefore important to engage stochastic condition into a model of telecommunication network since generally there arrised random problems. This research investigated Stochastic Programming (SP) method which used to indicate tracks with stochastic properties. Here, it was proposed to use a multi-commodity network model for telecommunication network problem. It also investigated three types of SP, i.e. Here and Now method, Wait and See method, and Scenario Tracking method through a case study on a prototype network integrated into the Generic Flow Assignment (GFA) model. A model and form of probability density/distribution for arrival rate based on the distribution of inter arrival rate. The implementation of the model was conducted by using the Stochastic Programming packet program. Keywords : Optimization, Stochastic Programming.

ii Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

KATA PENGANTAR

Pertama penulis panjatkan syukur kepada Allah yang Maha Pengasih Lagi Penyayang atas segala Rahmat dan karunia-Nya yang telah diberikan kepada penulis, sehingga penulis dapat menyelesaikan tesis sesuai dengan waktu yang telah dialokasikan. Tesis ini berjudul ”Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi”. Tesis ini merupakan persyaratan tugas akhir pada program studi matematika SPs Universitas Sumatera Utara. Pada kesempatan yang baik ini, penulis menyampaikan ucapan terima kasih dan penghargaan yang sebesar-besarnya kepada: Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.Ak selaku Rektor Universitas Sumatera Utara. Prof. Dr. Ir. T. Chairun Nisa B., M.Sc selaku Direktur Sekolah Pasca Sarjana yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pasca Sarjana Universitas Sumatera Utara Medan. Prof.

Dr.

Herman Mawengkang selaku ketua Program Studi Magister

Matematika SPs Universitas Sumatera Utara yang telah banyak membantu dalam penulisan tesis ini. Dr. Saib Suwilo, M.Sc selaku sekretaris Program Studi Magister Matematika di SPs Universitas Sumatera Utara dan juga sebagai ketua komisi pembimbing yang telah banyak membantu dalam penulisan tesis ini.

iii Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

Dr. Sutarman, M.Sc sebagai anggota komisi pembimbing yang telah banyak memberikan saran dan arahan dalam penulisan tesis ini. Dr. Tulus, M.Sc dan Dra. Mardiningsih, M.Si sebagai Dosen Penguji yang telah banyak memberikan saran dan arahan dalam penulisan tesis ini. Rektor Universitas Negeri Medan yang telah memberikan ijin belajar untuk studi lanjut di Program Magister Matematika USU. Dekan FMIPA Universitas Negeri Medan. Ketua jurusan Matematika FMIPA Universitas Negeri Medan. Seluruh Staf Pengajar pada Program Studi Magister Matematika SPs Universitas Sumatera Utara, yang telah memberikan ilmunya selama masa perkuliahan. Seluruh rekan-rekan mahasiswa angkatan ke-lima tahun 2006/2007 program studi Magister Matematika SPs Universitas Sumatera Utara atas kerjasama dan kebersamaan dalam mengatasi berbagai masalah yang dihadapi selama perkuliahan, Misiani S.Si selaku staf Administrasi program studi Matematika Universitas Sumatera Utara yang telah memberikan pelayanan yang baik kepada penulis. Secara khusus, terima kasih diperuntukkan kepada suami yang saya cintai Drs. E. Elvis Napitupulu, M.S. dan anak-anak yang saya cintai Rizal Afif, Fajrul Malik, dan Haura Azra, serta seluruh keluarga yang berkat dorongan dan perhatian serta doa mereka maka penulis dapat menyelesaikan pendidikan ini.

iv Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

Semoga tesis ini bermanfaat bagi pembaca dan berbagai pihak yang memerlukannya. Tentunya sebagai manusia tidak pernah luput dari kekurangan sehingga tulisan ini mungkin saja belum sempurna.

Medan,

Juni 2008

Penulis,

Ani Minarni

v Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

RIWAYAT HIDUP

Ani Minarni dilahirkan di Bandung pada tanggal 10 Oktober 1965 merupakan anak pertama dari 3 bersaudara dari Ayah Engkan Sukanda dan Ibu Susum Sumiati (Alm). Menamatkan Sekolah Dasar (SD) Negeri Pelesiran di Bandung pada tahun 1979, Sekolah Menengah Pertama (SMP) Negeri 2 di Bandung pada tahun 1982 dan Sekolah Menengah Atas (SMA) Negeri 3 di Bandung jurusan IPA pada tahun 1985. Tahun 1985 kuliah di jurusan Statistika Universitas Padjadjaran Bandung dan memperoleh gelar sarjana pada tahun 1991. Tahun 1992 menjadi staf pengajar di jurusan Matematika IKIP Medan hingga sekarang. Menikah dengan Drs. E. Elvis Napitupulu, M.S. pada tahun 1991 dan dikaruniai 2 orang putra (Rizal Afif Napitupulu dan Fajrul Malik Napitupulu) dan satu orang putri (Haura Azra Napitupulu). Tahun 2006 mengikuti pendidikan Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara.

vi Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .

x

DAFTAR SIMBOL . . . . . . . . . . . . . . . . . . . . . . . . . .

xi

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .

4

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

4

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

5

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .

5

BAB 2 KAJIAN PUSTAKA

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

7

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .

13

3.1 Konsep Komunikasi Data . . . . . . . . . . . . . . . . .

13

3.2 Metode Pendekatan Program Stokastik

. . . . . . . . . .

15

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

18

3.4 Pendekatan Wait and See . . . . . . . . . . . . . . . . .

19

3.5 Pendekatan skenario Tracking . . . . . . . . . . . . . . .

19

3.3 Metode Here and Now

vii Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

3.6 Fungsi Distribusi untuk Laju Kedatangan . . . . . . . . . BAB 4 PEMBAHASAN

20

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

23

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .

38

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

39

viii Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

DAFTAR TABEL

Nomor

Judul

Halaman

4.1

Hasil Optimisasi dari 64 Skenario untuk 11 Path . . . . . . . .

36

4.2

Hasil Optimisasi dari 1024 Skenario untuk 11 Path

37

ix Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

. . . . . .

DAFTAR GAMBAR

Nomor

Judul

Halaman

2.1

Hirarki link fisik antara subscriber dan Stasiun Pusat Kabel (WCS)

10

4.1

Pdf laju kedatangan p(u) . . . . . . . . . . . . . . . . . .

26

4.2

Cdf dari laju kedatangan C(u) . . . . . . . . . . . . . . . .

26

4.3

Jaringan prototype . . . . . . . . . . . . . . . . . . . . .

31

x Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

DAFTAR SIMBOL Symbol

Definition

ABR

Available Bit Rate

ATM

Asynchronous Tansfer Mode

B-ISDN

Broadband-Integrated Services Digital Network

CBR

Constant Bit Rate

CDV

Cell Delay Variation

CDVT cdf

CDV Tolerance cummulative distribution function

FTP

File Transfer Protocol

GFA

Generic Flow Assignment

O-D

Origin-Destination

OPNET pdf VBR STDM

Optimized Network Engineering Tool probability density function Variable Bit Rate Stochastic Time Division Multiplexing

xi Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar belakang Telekomunikasi adalah komunikasi jarak jauh. Masalah jaringan telekomunikasi berkaitan dengan masalah komunikasi data. Jaringan komunikasi biasanya diimplementasikan dalam layered protocol yang mendekomposisi suatu sistem yang rumit ke beberapa bagian yang dapat diatur yang disebut layer. Tiap layer memiliki interface yang terdefinisi dengan baik, ia menerima layanan yang disediakan oleh layer yang lebih rendah. Protokol adalah suatu persetujuan antara bagian-bagian yang berkomunikasi pada bagaimana komunikasi diproses (Yao, 2005). Banyak permasalahan yang muncul dalam jaringan telekomunikasi, antara lain ialah masalah shortest path, ATM, layanan ke pelanggan, kualitas suara, gambar, masalah jaringan akses, dan masalah call delay. Masalah lain yang dapat juga muncul dan menarik untuk dikaji ialah masalah arrival rate dan masalah inter arrival time. Masalah shortest path telah dibahas oleh Ji (2005) dalam masalah menentukan path terpendek untuk masalah jaringan 23 kota di China di mana beberapa kelompok edge yang menghubungkan antar kota memiliki distribusi yang berbeda-beda yaitu eksponensial, normal dan uniform. Di sini Ji memakai ratarata dalam membuat model. Sementara itu, masalah ATM telah diteliti oleh Yao (2005), masalah jaringan akses oleh Gloaguen (2006) dan masalah jaringan back-

1 Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

2 bone oleh Konak (2006). Kemudian Paxson (1994) telah meneliti masalah panjang session yang berkaitan dengan masalah arrival rate. Sangat jarang peneliti mengkhususkan diri meneliti masalah arrival rate yang merupakan salah satu masalah jaringan telekomunikasi yang sangat penting (Pitts J. Somans, 1996). Bahkan untuk inter arrival time yang berdistribusi Poisson majemuk belum ditemukan bagaimana solusi analitik untuk masalah arrival rate. Di sisi lain, dalam menyelesaikan masalah jaringan yang berkaitan dengan jaringan telekomunikasi, Suvrajet (1999) telah menyebutkan bahwa Program Linier deterministik tidak memadai digunakan untuk masalah jaringan telekomunikasi karena umumnya masalah ini bersifar stokastik yang jika dipaksakan akan mengakibatkan probability infeasibility. Maka Ji memakai Program Stokastik (PS) untuk menyelesaikan masalah shortest path jaringan telekomunikasi. Di bagian lain Azgomi dan Movaghar (2002) memakai PS bagi implementasi jaringan aktifitas stokastik pada pemodelan jaringan telekomunikasi. Kedua penulis mengkaji masalah konektivitas berbasis reliabilitas. Program stokastik tidak saja terpakai dalam masalah jaringan telekomunikasi tetapi telah memberi manfaat bagi penyelesaian masalah bidang-bidang lain seperti yang dilakukan oleh Prekopa (dalam Higle, 1978). Penulis ini bekerja dalam menentukan kapasitas reservoir untuk mengontrol banjir yang mungkin terjadi dimana volume aliran banjir bersifat stokastik. Kemudian Ferguson (dalam Higle, 1956) menerapkan model recourse sederhana yang merupakan bagian dari model program stokastik dalam mengatasi masalah management dalam industri penerbangan. Model recourse umum dipakai Sen (dalam Higle, 1994) dalam masalah jaringan khusus telekomunikasi.


3 Konak (2002) telah mendaftar sejumlah teknik pemodelan yang telah memainkan peranan penting, khususnya dalam analisis sistem dan jaringan telekomunikasi, diantaranya adalah model generik. Model ini dikaitkan dengan graph yang diperbesar (augmented graph). Variabel rancangan yang terlibat merupakan flow dan kapasitas. Melalui model ini dapat dirumuskan 3 model yang masing-masing berkaitan dengan masalah Capacity Assignment (CA), Flow Assignment (FA) dan Capacity and Flow Assignment (CFA) (Bazaraa, 2002) dimana masalah-masalah tersebut merupakan masalah graph. Dalam penelitian ini, Graph G = (V ; A) akan digunakan untuk menyatakan suatu jaringan telekomunikasi, dimana V menyatakan himpunan vertex dan A menyatakan himpunan arc atau edge. Dan jaringan paket telekomunikasi dapat dipandang sebagai suatu graph yang diperbesar dengan dua entitas: link flow λi dan kapasitas transmisi link Ci .Yang menjadi tujuan dari permasalahan optimisasi jaringan telekomunikasi adalah mengoptimumkan salah satu dari dua jenis indeks: operating index, yaitu banyaknya packet dalam system (delay of packets T ) dan capital index, yaitu biaya kapasitas d. Entitas yang harus digunakan diberi nama variabel rancangan terdiri dari flow dan kapasitas. Sementara itu, pendekatan-pendekatan yang telah digunakan untuk menyelesaikan masalah PS adalah metoda Here and Now (HN), metoda Wait and See (WS) dan Metoda Scenario Tracking (ST). Pendekatan HN mengintegrasikan distribusi data ke dalam program, dengan metoda ini keputusan dibuat sebelum semua skenario diobservasi. Metoda WS merupakan metoda penyelesaian PS secara langsung. Sedangkan metoda ST merupakan varian dari metoda WS.


4 Terkait dengan penjelasan di atas, penting untuk meneliti masalah arrival rate pada suatu jaringan telekomunikasi yang menggunakan model PS. Untuk itu, dalam penelitian ini dibangun suatu model PS bagi arrival rate untuk jaringan telekomunikasi melalui pendekatan metoda HN, metoda WS dan metoda ST yang diintegrasikan ke dalam model GFA. Implementasi model yang dihasilkan dilakukan oleh Software Program Stokastik

1.2 Perumusan Masalah Dari yang telah dipaparkan dalam bagian latar belakang di atas dapat ditarik suatu perumusan masalah dalam penelitian ini yaitu, bagaimanakah bentuk model untuk masalah jaringan telekomunikasi khususnya untuk masalah laju kedatangan (arrival rate) dimana parameter-parameter yang terlibat bersifat stokastik. Dengan kata lain bagaimanakah bentuk model program stokastik laju kedatangan dalam masalah rancangan jaringan telekomunikasi saat ini ditinjau melalui pendekatan metode HN, metode WS dan metode ST yang diintegrasikan ke dalam model GFA.

1.3 Tujuan Penelitian Penelitian ini bertujuan untuk menemukan model Program Stokastik untuk laju kedatangan (arrival rate) dikaitkan dengan waktu antar kedatangan (inter arrival time) yang bersifat stokastik yang merupakan masalah rancangan jaringan telekomunikasi dengan menggunakan pendekatan metoda HN, metoda WS dan metoda ST yang diintegrasikan ke dalam model GFA.


5

1.4 Kontribusi Penelitian Penelitian ini menyediakan model PS untuk laju kedatangan dalam rancangan jaringan telekomunikasi yang juga dapat dipertimbangkan untuk diimplementasikan sebagai alternatif model-model PS yang telah ada.

1.5 Metodologi Penelitian

1. Sebagai langkah awal, penelitian ini membahas konsep-konsep dasar jaringan telekomunikasi. 2. Mengkaji masalah-masalah yang ada dalam jaringan telekomunikasi. 3. Mengkaji masalah program stokastik. 4. Mengulas masalah pemodelan, mengkaji model-model program stokastik yang telah tersedia. 5. Membuat model program stokastik untuk rancangan jaringan telekomunikasi terutama untuk laju kedatangan (byte/detik). 6. Menentukan model program stokastik untuk rancangan jaringan telekomunikasi dengan memakai pendekatan metode Here and Now, metode Wait and See serta metode Scenario Tracking dimana parameter-parameter yang terlibat mengikuti distribusi Pareto, distribusi Log Ekstrim, dan distribusi Poisson Majemuk dan diintegrasikan ke dalam model GFA.


6 7. Mengimplementasikan model program stokastik yang diperoleh pada langkah 6 dengan menggunakan software Program Stokastik.


BAB 2 KAJIAN PUSTAKA

Dalam penelitian Konak (2002) disebutkan ada beberapa teknik berbeda untuk memodelkan dan menganalisis sistem telekomunikasi dan jaringan. Mengingat jaringan multiprotokol, jaringan multiservis, jaringan kapasitas dan jaringan kecepatan tinggi sangatlah vital bagi operasi ekonomi global, maka harus ditata mengarah ke standar pembakuan yang keras dan tegas baik demi kepentingan analisis maupun dari sisi fungsi. Untuk melakukan hal itu dituntut pemakaian teknik yang handal untuk menspesifikasi, mengevaluasi, implementasi, menguji serta memelihara jaringan. Semua metode untuk itu tergantung pada penggunaan teknik-teknik matematika maupun statistika, alat bantu komputer dan serangkaian metodologi. Berikut ini teknik-teknik pemodelan yang telah memainkan peranan penting dalam rancangan dan analisis sistem telekomunikasi dan jaringan.

1. Model probabilitas Model ini telah digunakan secara luas dalam sistem telekomunikasi. Ini merupakan model paling abstrak yang menghasilkan suatu solusi tertutup. 2. Model jaringan antrian Model ini, yang telah di gunakan untuk beragam aplikasi, juga dalam sistem telekomunikasi. 3. Model teori Rantai Markov Model ini telah memainkan peran utama dalam anlisis jaringan. Matriks 7 Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

8 geometri dan aljabar kronecker untuk solusi efisien Rantai Markov telah memperluas kapabilitas model ini. Akan tetapi, memakai model ini untuk memodelkan jaringan multimedia rumit masa kini, biasanya memerlukan Rantai Morkov sangat besar dan bagaimana memilih dan membangun Rantai Morkov skala besar merupakan kesulitan yang cukup berat. 4. Model Petrinets (PNS) Perluasan stokastik dari PNs yaitu SPNs bekerja membangun rantai markov skala besar secara otomatis. Model ini jarang digunakan untuk memodelkan dan menganalisis jaringan dan sistem telekomunikasi karena model ini lebih cenderung ke arah seni ketimbang sains yang menyebabkan sulit untuk diterapkan pada sistem yang kompleks dan berskala besar. 5. Model Fluida Model ini diperkenalkan untuk mengatur masalah ruang status berskala besar yang merupakan kesulitan utama untuk menganalisis MCs dan SPNs. Ide model fluida ini telah digabungkan dengan SPNs yang menghasilkan fluida stokastik petri nets (FSPNs). 6. Paket program dan simulasi jaringan 7. Model Generik Model ini dikaitkan dengan graph yang diperbesar (augmented graph). Variabel rancangan yang terlibat merupakan flow dan kapasitas. Melalui model ini dapat dirumuskan 3 model yang masing-masing berkaitan dengan masalah Capacity Assignment (CA), Flow Assignment (FA) dan Capacity and Flow Assignment (CFA), Bazaraa (2002).


9 Pendekatan metode HN, metoda WS dan metoda ST yang akan diintegrasikan ke dalam model GFA akan diuraikan dalam Bab 3. Disisi lain model stokastik spasial untuk jaringan telekomunikasi telah dikembangkan cukup luas akhir-akhir tahun ini sebagai suatu alternatif untuk pendekatan ekonomis yang bersifat tradisional berkaitan dengan perencanaan strategi dan pengukuran biaya. Model ini memungkinkan untuk menyatukan fitur geometrik dan stokastik yang diobservasi dalam jaringan telekomunikasi. Sebagai pertimbangan, dengan mengambil struktur geometri dari kerangka jaringan, model jaringan yang memakai alat geometri stokastik menawarkan sebuah gambaran yang lebih relevan ke lokasi dependen karakteristik jaringan daripada model jaringan konvensional. Unsur probabilistik mencerminkan variabilitas jaringan dalam ruang dan waktu. Contoh populer dari jaringan dimana model geometrik stokastik terpakai cukup intens adalah pada jaringan switching, jaringan multi-cast, dan sistem telekomunikasi bergerak (mobile telecommunication). Model-model tersebut melibatkan distribusi Poisson-Voronoi yang diagregasi. Ada juga yang melibatkan masalah spanning tree. Gloaguen (2006) memfokuskan diri pada jaringan akses telekomunikasi yang dapat dipandang sebagai bagian paling penting dalam pemodelan jaringan telekomunikasi karena secara kasar hampir 50% dari total investasi terpakai untuk jaringan akses. Dengan biaya se besar, itu dan kemungkinan populasi subscriber berubah, sangatlah penting mendapatkan model yang cocok untuk evaluasi biaya, analisis kinerja, dan perencanaan strategi dari jaringan akses.


10 Jaringan akses atau lup lokal adalah bagian dari jaringan yang menghubungkan suatu subscriber dengan WCS (Wire Center Station) yang bersesuaian. Hirarki link fisik dibuat melalui komponen-komponen jaringan seperti Network Interface Device (NID), secondary and primary cabinets (CS and CP) dan service Area Station (SAI) seperti ditunjukkan pada gambar 1. Zona pelayanan (serving zone) dikaitkan dengan tiap WCS; sub jaringan mengumpulkan semua link antara WCS dab subscriber yang terletak dalam zona servingnya biasa digambarkan dalam struktur tree

Gambar 2.1 : Hirarki link fisik antara subscriber dan Stasiun Pusat Kabel (WCS)

Fitur paling penting mengenai jaringan akses adalah dia merupakan tempat dimana jaringan telekomunikasi sesuai/cocok dalam perencanaan desa atau kota. Untuk jaringan kota yang dipertimbangkan di sini adalah kerangka dan sistem jalan raya. Penelitian penting dalam jaringan akses yang telah dilakukan pada tahuntahun terahir ini adalah mengenai Stochastic Subscriber Line Model (SLMM). Penelitian ini mengkaji mengenai model stokastik dan menawarkan alat untuk menjelaskan ketidakteraturan spasial beserta fitur geometrik jaringan akses, menganalisisnya dari sisi ekonometrika stokastik dalam hal biaya sambungan. Khusus-


11 nya, penelitian Gloaguen menyediakan rumus nilai rata-rata sederhana untuk evaluasi biaya, analisis kinerja dan perencanaan strategis. Kerangka pemodelan SSLM dibagi menjadi beberapa submodel sebagai berikut, Model Geometri Jaringan. Model Komponen Jaringan, dan Model Topologi Jaringan. Model Geometri Jaringan menggambarkan cable trench system, yang berlokasi di sepanjang sistem infrastruktur kota ataupun desa. Model Komponen Jaringan melokalisir komponen-komponen jaringan secara teknis pada lintasan atau bidang dengan menggunakan proses Poisson. Penelitian Gloaguen ini menggunakan pendekatan berdasarkan minimisasi ukuran jarak antara karakteristik-karakteristik data input dan nilai-nilai yang dihitung dari karakteristik-karakteristik tersebut memakai rumus teoritis yang sahih untuk model tessellation random. Data input dapat ditaksir dari data infrastruktur real maupun dari realisasi tessellation random. Realisasi tessellation random cukup penting untuk memverifikasi kebenaran prosedur penelitian model. Sementara itu penelitian Konak (2006) menyoroti pentingnya fungsi jaringan telekomunikasi backbone sehingga skenario kegagalan komponen harus dipertimbangkan dalam rancangan terutama untuk jaringan fiber optik yang luas. Karenanya, rancangan jaringan telekomunikasi yang memadukan survivabilitas dan reliabilitas telah menarik perhatian praktisi dan akademisi. Penelitian dalam bidang ini telah berkembang ke dua arah, yaitu rancangan jaringan survivabel dan rancangan jaringan reliable. Definisi reliabilitas jaringan tergantung pada asumsi tentang kegagalan komponen individual dan rata-rata servis dari jaringan. Jika diberikan riliabilitas komponen individual, maka reliabilitas suatu jaringan mengekspresikan kemam-


12 puannya menyediakan servis yang diinginkan end-user secara probabilitas. Menyelenggarakan konektivitas adalah servis terpenting dari jaringan ini. Konektivitas berbasis reliabilitas seperti reliabilitas semua terminal (peluang semua node telah terhubung) dan reliabilitas 2-terminal (peluang 2-terminal telah terhubung) telah sering dipakai dalam rancangan dan analisis reliabilitas jaringan. Situasi masalah reliabilitas berbasis konektivitas juga serupa dengan konektivitas berbasis reliabilitas. Penelitian lain yang melibatkan program stokastik dilaksanakan oleh Prekopa dalam Higle (1978), ia bekerja dalam menentukan kapasitas reservoir sebagai kontrol banjir yang mungkin terjadi dimana volume aliran banjir bersifat stokastik. Kemudian Ferguson dalam Higle (1956) menerapkan model recourse sederhana yang merupakan bagian dari model program stokastik dalam mengatasi masalah management dalam industri penerbangan. Model recourse umum dipakai Sen dalam Higle (1994) dalam masalah jaringan khusus telekomunikasi.


BAB 3 LANDASAN TEORI

Telekomunikasi adalah bagian dari komunikasi, maka berbicara mengenai telekomunikasi dapat dimulai dari konsep komunikasi. Dan penelitian tentang program stokastik dalam rancangan jaringan telekomunikasi melibatkan beberapa konsep komunikasi dan teknik pemodelan. Untuk itu berikut ini akan diuraikan mengenai kedua hal tersebut dilanjutkan dengan telaah pada beberapa penelitian yang telah dilakukan yang menunjang penelitian ini.

3.1 Konsep Komunikasi Data Jaringan komunikasi biasanya diterapkan dalam layered protocol yang mendekomposisi suatu sistem yang rumit ke beberapa bagian yang dapat diatur yang disebut layer. Tiap layer memiliki interface yang terdefinisi dengan baik, ia menerima layanan yang disediakan oleh layer yang lebih rendah. Protokol adalah suatu persetujuan antara bagian-bagian yang berkomunikasi pada bagaimana komunikasi diproses. Ia mendefinisikan sehimpunan aturan mencakup format dan arti dari kerangka, serta paket atau pesan yang dipertukarkan oleh pasangan entitas dalam suatu layer, Yao (2005). ATM dan B-ISDN : Asynchronous Transfer Mode (ATM) adalah suatu arsitektur jaringan. Ia dirancang untuk mendukung integrasi suara berkualitas tinggi, video dan lalu lintas data kecepatan tinggi. Untuk end user, ia menyediakan kemampuan untuk memindahkan sambungan berarah dan lalu lintas tak 13 Ani Minarni : Model Program Stokastik Dalam Rancangan Jaringan Telekomunikasi, 2008 USU Repository © 2008

14 terhubung pada bit rate yang bervariasi ataupun konstan. ATM juga memungkinkan alokasi bandwidth yang diminta dan menyediakan negosiasi QoS. Untuk provider jaringan, ATM memungkinkan transport beberapa tipe lalu lintas data yang berbeda yang melintasi jaringan yang sama.Jaringan ATM mentransmisikan informasi dengan memakai cell berukuran tetap yang terdiri dari 48-byte payload dan 5-byte header seperti terlihat pada Gambar 2.1. Quality of service (QoS) : Memungkinkan kontrak lalu lintas data konkrit, ATM mendefinisikan sejumlah parameter QoS yang nilai-nilainya dapat dinegosiasikan antara antara pelanggan dan penyedia. Tiga parameter yang biasanya jadi bahan negosiasi adalah Cell Loss Ratio (CLR), Cell Transfer Delay (CTD), dan Cell Delay Variation (CDV). Ketiga parameter itu menjelaskan karakteristik jaringan dan diukur di bagian receiver. CLR mengukur fraksi cell yang ditransmisi yang tidak dikirim sama sekali atau dikirim tapi terlambat sehingga tak berguna lagi. CTD adalah waktu transit dari sumber ke tujuan. CDV mengukur keberagaman cell yang dikirim. Ada juga beberapa parameter QoS yang tidak perlu dinegosiasikan. Network Congestion (jaringan macet) : Dapat diukur jika sejumlah besar lalu lintas sumber menjadi aktif secara bersamaan. Pada situasi macet seperti ini, terjadi antrian yang mengakibatkan cell loss dan meningkatkan delay. Salah satu penyebab kemacetan ini adalah kesibukan tingkat tinggi pada jaringan ATM. Masalah congestion merupakan isu yang penting dalam masalah jaringan. OPNET : Membantu mendukung secara menyeluruh proses pemodelan protocol, komunikasi dan distribusi sistem. Baik kinerja maupun jalannya sistem model dapat dianalisis dengan membuat simulasi kejadian diskrit. OPNET


15 adalah alat yang cukup perlu dilibatkan dalam fase studi simulasi, meliputi perancangan model, pengumpulan data dan analisis, Yao (2005).

3.2 Metode Pendekatan Program Stokastik Dalam paradigma telekomunikasi konvensional, statistik dari track yang ada dalam jaringan biasanya tak berubah dengan berubahnya waktu. Untuk alasan ini suatu model jaringan hanya perlu menandai kinerja jaringan yang berkaitan dengan nilai rata-rata seperti rata-rata delay dari semua paket data atas path. Akibatnya, parameter yang diperlukan dalam rumusan seperti ini juga terdapat dalam nilai-nilai seperti rata-rata laju kedatangan, rata-rata laju antar kedatangan atau rata-rata biaya. Pendekatan seperti ini bagaimanapun semakin mendapat tantangan seiring dengan pesatnya perkembangan paradigma baru telekomunikasi. Sebagai contoh perkembangan baru adalah tentang Asynchronous transfer mode (ATM). Suatu jaringan ATM dimaksudkan untuk mendukung aplikasi dengan rate bervariasi seperti CBR, VBR, ABR, dan UBR (unspecified bit rate). Perkembangan lainnya, beberapa aplikasi memerlukan bandwidth moderat, sekitar 2 kbps, sementara yang lain mungkin perlu hingga beberapa Mbps. Di sisi lain, pelanggan mungkin menuntut kualitas layanan (QoS) berbeda dari pelanggan lainnya. Lagipula suatu metric baru seperti CDTV (cell delay variation tolerance) harus dilibatkan dalam QoS. Sementara itu, untuk suatu metric konvesional seperti CTD (cell transrfer delay) atau CDV (cell delay variation), selera pelanggan dapat saja berbeda nyata. Fitur baru seperti pengendalian kemacetan (congestion-control) dan self-healing menambah kerumitan permasalahan telekomunikasi. Jadi, dalam jaringan telekomunikasi modern yang dihadapi saat ini,


16 track flow tidak saja bersifat dinamik tetapi juga bersifat stokastik. Dalam situasi demikian, pendekatan dimana yang menjadi tumpuan adalah nilai rata-rata parameter tidak lagi cukup valid. Faktanya, beragam masalah yang timbul alamiahnya selalu bersifat stokastik. Sebagai contoh, Min y = 2x1 + x2 Kendala ax1 + x2 ≥ 10 bx1 + x2 ≥ 8 dimana a dan b berturut-turut berdistribusi uniform [2;3] dan [1;2]. Dengan menggunakan nilai rata-rata a dan b, secara grafis solusi optimalnya adalah (x∗1 , x∗2) = (2, 5). Tapi, analisis lebih lanjut di bawah ini memperlihatkan bahwa peluang solusi yang didapat diatas jika disubstitusikan ke masalah awal, terlalu kecil, yaitu hanya 0.25 Prob [(a, b)|ax∗1 + x∗2 ≥ 10; bx∗1 + x∗2 ≥ 8] = Prob[(a, b)|2a + 5 ≥ 10; 2b + 5 ≥ 8] = Prob[(a, b)|a ≥ 2.5; b ≥ 2.5] = (0.5)(0.5) = 0.25 Contoh di atas menunjukkan fakta bahwa hanya memakai rata-rata parameter untuk menyelesaikan masalah optimisasi akan mengakibatkan probabilistic infeasibility untuk solusinya, Suvrajet (1999).


17 Semua model jaringan dapat diabstraksi sebagai suatu masalah program matematika (PM) sebagai berikut: Min f (x, a) Kendala g(x, b) ≥ 0 Dimana f : Rn → R1

(3.1)

g : Rn → Rm X : variable keputusan Daerah fisibel x merupakan daerah tertutup dengan g(x) secara analitik diekspresikan dalam suku-suku x dan himpunan parameter Ω = (a, b). Metode PM mengasumsikan bahwa semua parameter dalam Ω bersifat deterministik. Sedangkan metode Program Stokastik (PS) memungkinkan Ω terdiri dari parameter parameter yang bersifat stokastik /probabilistik, Dempster (1980) dan Tintner (1994). Sebagai contoh persamaan (1.1) dan persamaan (1.2), dalam PS menjadi persamaan (3.2) sebagai berikut: Min f (x, ad, au ) (3.2) Kendala g|(x, bd, bu ) ≥ 0 dimana subskrip d dan u adalah singkatan untuk deterministik dan tak tentu. Suatu skenario didefenisikan sebagai realiasi gabungan dari suatu parameter tak tentu. Ada dua jenis masalah dalam PS, yang pertama mengasumsikan bahwa pdf dan cdf dari data diketahui dan tertentu, sedangkan yang kedua pdf dan cdf tidak diketahui. Teori PS mula-mula dikembangkan untuk masalah jenis pertama.


18 3.3 Metode Here and Now Salah satu pendekatan representatif untuk menyelesaikan masalah PS adalah metode Here and Now atau HN, Dempster (1980). Dasar pemikiran dari metode ini adalah membuat keputusan sebelum semua skenario diobservasi. Disamping memakai momen seperti rata-rata dan varians, pendekatan HN mengintegrasikan distribusi ke dalam program. Sebagai contoh, rumusan (1.1) dan (1.2) untuk pendekatan HN menjadi P rob(ax1 + x2 ≥ 10) ≥ p1

(3.3)

P rob(bx1 + x2 ≥ 8) ≥ p2

(3.4)

Dimana p1 dan p2 merupakan probabilitas tertentu. Dengan menerapkan cdf uniform, diperoleh: (3 − P1 )X1 ≥ 10(2 − P2 )X2 ≥ 8

(3.5)

Dalam pendekatan HN, variabel rancangan xk adalah jejak lintasan bukan entitas ataupun momen dari entitas. Perlu dicatat bahwa metode HN melibatkan cdf. Tapi, secara matematis cdf hanyalah suatu hasil transformasi untuk mengubah satu rumus kerumus lainnya. Semua metode yang memakai cdf atau fungsi utilities dapat dipandang sebagai pendekatan tidak langsung karena dasarnya adalah transformasi. Ada juga transformasi yang tidak menyangkut pautkan cdf seperti pada Bertsekas (1941). Kemudian Powell (1964) membahas fungsifungsi yang tidak integrabel sehingga teknik transformasi tak bisa digunakan. Tapi dalam penelitian ini hanya fungsi-fungsi kontinu yang integrabel yang akan digunakan dan fungsi distribusi distkrit Poisson.


19 3.4 Pendekatan Wait and See Pendekatan lain yang disebut metode Wait and See (WS) merupakan metode untuk menyelesaikan PS secara langsung. Dalam pendekatan WS, variabel rancangan sk merupakan entitas random, ditentukan oleh parameter random a dan b. Pada persamaan (1.1) dan (1.2) daerah fisibel dabatasi oleh persamaan persamaan linier. Secara umum, persamaan-persamaan linier tersebut dapat diekspresikan sebagai berikut, A1x1 + a2xa = c1 (3.6) B1x1 + b2x2 = c2 Dan solusinya adalah X1 = (b2c1 − a2c2 )/(a1b2 − a2b1) (3.7) X2 = (a2c2 − b1 c1 )/(a1b2 − a2b1) Untuk situasi dimana daerah fisibel dibatasi oleh persamaan non linier, bentuk solusi akan seperti berikut, X1 = f1 (ak , bk , . . .) (3.8) X2 = f2 (ak , bk , . . .)

3.5 Pendekatan skenario Tracking Terdapat varian metode WS dan disebut skenario Tracking, Dembo (1991). Misal as dan bs adalah realisasi gabungan dari parameter tak tentu, berturutturut au dan bu . Untuk setiap skenario s ∈ S himpunan semua skenario, rumus SP yang diekspresikan oleh (2.2) meringkas suatu masalah deterministik seperti


20 di bawah ini yang akan disebut sebagai submasalah skenario. Min (X, ad , as ) (3.9) Kendala g(X, bd , bs ) ≥ 0 Untuk setiap skenario terdapat peluang ps . Dalam suatu lingkungan, suatu solusi Xr bagi suatu sistem stokastik nonlinier g(X, bd , bs ) ≥ 0 dikatakan norm fisibel jika dia meminimumkan min

X

ps [| |minimum[0, f (X, bd , bs )]||]

(3.10)

s

Berdasarkan hal tersebut suatu model dapat dibangun seperti berikut ini min

X

ps [||f(X, ad , as )|| = kminimum[0, g(X, bd , bs )]k]

(3.11)

s

Dimana ys adalah nilai optimal dari f (X, ad , as ), yang diperoleh dari penyelesaian submasalah skenario. Rumusan ini diberi nama model tracking alasannya adalah karena dia mendeteksi solusi skenario sedekat mungkin sambil tetap menjaga fisibilitas.

3.6 Fungsi Distribusi untuk Laju Kedatangan Untuk fungsi probabilitas variabel acak terdapat teorema fungsi distribusi berikut yang buktinya dapat diperoleh di berbagai buku teori probabilitas, misalnya dalam Ross (1989).


21 Teorema Fungsi Distribusi: Misalkan X adalah variabel acak dengan fungsi densitas probabilitas atau pdf f(x) sedemikian sehingga f (x) = 0 dalam interval [0,1]. Misal g(x) adalah fungsi real yang diferensiabel dimana-mana. Jika g 0(x) adalah fungsi real yang tak berubah tanda dalam [a, b], maka Y = g(x) adalah suatu variabel acak kontinu dengan pdf sebagai berikut,    f [h(y)].|h0(y)| α < y < β ϕ(y) =   0 untuk y lainnya

(3.12)

Dimana h(y) adalah fungsi invers dari g(x) dan α = min{g(a); g(b)}

(3.13)

β = max{g(a); g(b)}

(3.14)

Sebagai contoh, misalkan Y = g(x) = 1/x, untuk melihat proses yang menghubungkan waktu antar kedatangan dan laju kedatangan , hasilnya adalah x = h(y) = 1/y dan h(y) = −1/y 2. Untuk keadaan dimana waktu antar kedatangan menyebar/berdistribusi Eksponensial Negatif, yaitu F (x) = λe−λx ,

x>0

(3.15)

Maka menurut teori probabilitas di atas, pdf laju kedatangan adalah 1 1 1 1 ϕ(y) = f [h(y)] · |h0 (y)| = f ( ) · | − 2 | = 2 f ( ) y y y y λ 1 λ = 2 · λe−λ/y = 2 e− y , (y > 0) y y

(3.16)

Teorema fungsi distribusi ini berguna dalam bab 4 tesis ini untuk mendapatkan fungsi distribusi arrival rate apabila fungsi distribusi inter arrival time


22 dan panjang session data telekomunikasi diketahui. Fungsi distribusi kumulatif (cdf) diperoleh dengan mengintegralkan pdf untuk variabel acak kontinu. Untuk variabel acak diskrit, cdf merupakan jumlah kumulatif dari tiap satuan variabel diskrit tersebut.


BAB 4 PEMBAHASAN

Dalam praktek, kebanyakan masalah jaringan dianalisis dengan teknik simulasi dari pada dianalisis secara analitik. Akibatnya, pendekatan ST lebih fleksibel daripada metode HN karena HN memerlukan rumusan analitik suatu distribusi. Akan tetapi dalam situasi dimana parameter lintasan (track) berdistribusi konvensional, metode HN seringkali tidak memerlukan banyak perhitungan. Disini selanjutnya ditunjukkan prosedur dasar untuk kedua metode tersebut yang diterapkan pada masalah FA. Rumusan konvensional dari model generik yang disebutkan pada bagian pendahuluan didasarkan pada link-node yang incident. Akan tetapi dalam aplikasi B-ISDN terdapat bermacam-macam kelas lintasan (multiple classes of track) seperti CBR, VBR, UBR dan ABR yang akan ditransmisikan sepanjang path yang menghubungkan satu himpunan pasangan O-D. Karena itu diperlukan ekspresi link-flow λi melalui path flow xk yang berkaitan dengan track classes. Hal ini memungkinkan karena biasanya jumlah total dari xk lebih besar dari jumlah total λi . Berdasaran hal tersebut variabel rancangan menjadi xk dan model dibangun berdasarkan link-node yang insiden. Secara matematik masalah optimisasi jaringan dengan path-node yang insiden dapat dijelaskan oleh model Multikomoditas (MC), suatu paradigma representatif yang dikembangkan dalam teori jaringan. Untuk suatu paradigma B-ISDN, konsep dari kelas komoditas dikaitkan dengan kelas lintasan.


24 Model yang berdasarkan pada path-node yang insiden memiliki sifat penting yaitu asumsi Poisson tetap dapat digunakan. Ini karena path sejenis dengan suatu end-to-end connection dan beberapa tipe track dapat dijelaskan oleh pola Poisson pada connection layer. Untuk jaringan utama (backbone network), diperlukan fitur pemulih (restoration feature) ke dalam rumus FA. Dengan mempertimbangkan fitur-fitur tersebut maka dalam penelitian ini digunakan model generik FA (GFA) sebagai berikut, min y =

XX

dp xp

(4.1)

π∈Π p∈pπ

Kendala

X

xp ≥ γπ (1 − απ )

p∈pπ

X

xp ≤ Ci (1 + δ)

π∈Qi

(4.2)

Xp ≥ 0, ∀p ∈ Ppi , π ∈ Π dimana π : himpunan pasangan O-D Ppi : himpunan semua pasangan O-D terhubung dalam π Kemudian dp xp γπ Qj Ci Dan δ

= = = = = =

satuan biaya flow p flow dari path P / track requirement berkenaan dengan O-D koefisien nonsurvivabilitas (0 < απ < 1) himpunan semua path yang melintasi link-i kapasitas link-i fraksi kelebihan muatan (δ > 0)

Dalam model GFA terdapat metrik sederhana survivabilitas. Dimasa lalu, kajian ekstensif telah dilakukan dalam meningkatkan daya tahan jaringan paket (packet network survivability). Penelitian dalam masalah ini telah melibatkan area khusus. Secara umum, survivabilas jaringan dapat dimodelkan sebagai masalah


25 program integer. Secara khusus, studi tentang survivabilitas melulu hanya pada masalah path disjoint dan k-shortest path. Banyak model program integer canggih telah diusulkan dan sebagian darinya telah digunakan dalam praktek. Di sisi lain dalam model GFA tekanan utama terletak pada entitas primal seperti kapasitas link atau muatan lintasan (track-load). Untuk alasan ini, beberapa pendekatan sederhana pada survivabilitas lebih disukai, dan varians απ dan δ dalam model GFA dapat juga ditentukan sebagai model jaringan yang diusulkan. Dalam penelitian ini selanjutnya, integrasi PS ke dalam optimisasi jaringan diutamakan dengan asumsi bahwa γπ bersifat acak. Diskusi mengenai kapasitas link C dilibatkan dalam studi kasus di bawah ini. Suatu jaringan packet-switching adalah satu sistem multiple layer. Suatu karakteristik lintasan adalah layer dependen. Contohnya, pada TCP session connection layer, telah ditunjukkan beragam studi bahwa model Poisson merupakan pendekatan yang dapat diterima. Secara matematik, model Poisson meliputi tiga atribut, yaitu banyaknya pelanggan dalam waktu t, waktu antar-kedatangan (inter arrival time) dan laju kedatangan (arrival rate). Jika diberikan cdf waktu antar kedatangan T berdistribusi Eksponensial Negatif (NED), FT (t) = 1 − e−λt (t > 0) maka pdf dan cdf laju kedatangan U , berdasarkan teorema fungsi distribusi, lihat pers (3.16) berturut-turut diberikan oleh P (u) =

λ −λ/u e u2

(4.3)

dan C(u) = e−λ/u


(4.4)

26

Gambar 4.1 : Pdf laju kedatangan p(u)

Gambar 4.2 : Cdf dari laju kedatangan C(u)


27 Gambar 4.1 dan Gambar 4.2 merupakan representasi grafis dari p(u) dan C(u). Dalam model diatas entitas yang diperhatikan adalah connection session. Untuk mendapatkan rancangan kapasitas, kita perlu tahu distribusi panjang session dalam byte. Hal ini karena laju kedatangan R(byte/detik) ditentukan oleh perkalian waktu antar kedatangan U dengan panjang session X, yaitu R = XU . Dalam dekade terahir, penelitian-penelitian telah dilaksanakan untuk paradigma intenet. Telah dilaporkan bahwa panjang session X dapat dihampiri oleh distribusi Log Ekstrim dan Log Normal untuk paradigma TELNET dan FTP, Paxton (1994). Juga telah ditunjukkan bahwa FTPDATA burst length dapat dijelaskan oleh distribusi Pareto. Secara umum, track dapat dipandang sebagai superposisi dari track flow berdasarkan proses Poisson, sementara itu volume flow mengikuti distribusi berekor gemuk (heavy tailed). Berikut ini kita turunkan distribusi laju kedatangan untuk suatu paradigma telekomunikasi terpilih. Track TELNET : Berdasarkan pada [9] variable random Y berdistribusi Log Ekstrim jika cdfnya berbentuk seperti berikut ini, a−y FY (y) = exp − exp b

(4.5)

Berdasarkan pada analisis peluang, pdf variabel random R = XU = X/T diberikan oleh, Fx(x) = exp[−(2a/x)h ]

(4.6)

dan fx (x) =

h2ah exp(−2a /x)h x1+h


(4.7)

28 dimana h = 1/(b ln 2). Lebih lanjut pdf variable random R = XU = X/T adalah: FR(r) =

Z∞

fx (rt)fT (t)t dt

0

= λh2ah

Z∞

(4.8) z −(1+h) t−h exp[−2ah (zt)−h − λt]dt

0

Track FTPDATA : track FTP DATA terdiri dari aliran data yang membludak (a stream of bursts) yang panjangnya dapat digambarkan oleh distribusi Pareto yang merupakan suatu distribusi heavy-tailed. Secara matematik variabel random X dikatakan berdistribusi heavy-tailed jika memiliki sifat sebagai berikut: lim [1 − F (x)] =

x→∞

1 (a > 0) xa

(4.9)

Suatu distribusi dikatakan distribusi Pareto jika bentuk cdf dan pdfnya berturutturut seperti berikut ini:

a b Fx(X) = 1 − x

dan a fX (x) = b

a+1 b (x > b, a > 0) x

(4.10)

(4.11)

Berdasarkan analisa probabilitas, pdf untuk variabel random R = XU = X/T menjadi, FR(r) =

=

Z∞ b/r Z∞

fx (rt)fT (t)t dt a b

a+1 b λte−λt dt x

b/r

abaλ = a+1 r

Z∞

e−λt dt ta

b/r


(4.12)

29 Track Poisson Majemuk (CP) : Distribusi laju kedatangan bentuknya tidak tertutup jika panjang session berdistribusi Log Ekstrim atau Pareto. Tapi, bentuk tertutup dapat diperoleh jika panjang session berdistribusi Eksponensial. Model seperti ini disebut proses Poisson majemuk karena ia melibatkan dua distribusi Eksponensial yang independen untuk session antar kedatangan dan session length. Dalam praktek, model ini digunakan untuk menggambarkan paradigma ON-OFF ATM dimana sumber membangun track CBR dalam ON session dan panjang session ON-OFF mengikuti distribusi Geometrik, Pitts J. Somans (1996). Dalam literatur, model CP biasanya dibahas dalam analisis Markov tingkat lanjut karena merupakan kasus sistem antrian ukuran besar, Seperti model Poisson dasar, model CP memiliki 3 atribut, yaitu:

1. Banyaknya pelanggan dalam waktu t 2. Waktu antar kedatangan 3. Laju kedatangan

Umumnya penelitian orang ditekankan hanya pada atribut 1. Dalam analisis track jaringan, kita tertarik pada masalah laju kedatangan (ataribut 3). Untuk alasan ini, penelitian ini fokus pada laju kedatangan model CP dan menurunkan rumus-rumusnya. Prosedurnya langsung, tapi hasilnya belum ditemukan dimanapun. Misal pdf dari session waktu antar kedatangan T adalah fT (t) = λe−λt (t > 0)


30 dan panjang session X (byte) adalah, fx (X) = ae−at(x > 0)

(4.13)

Karena secara matematik, pdf laju kedatangan (byte/detik) R = X/T dapat diturunkan sebagai berikut, fR (r) =

Z∞

=

Z∞

fx (rt)fT (t)t dt

0

ae−artλe−λt t dt

(4.14)

0

=

c (r + c)2

Dimana c = λ/a maka cdfnya adalah, FR(r) =

Zr

fR (w)dw

(4.15)

0

Menarik untuk membandingkan persamaan (4.14) dengan persamaan (4.11). Persamaan (4.14) dapat disimpulkan berdistribusi shifted Pareto karena konstanta c berada pada posisi penyebut. Tidaklah praktis mengembangkan solusi bentuk tertutup untuk model GFA, karena sebenarnya dia adalah masalah program linier. Untuk LP deterministik, pendekatan terbaik adalah metode simpleks. Tapi, untuk analisis stokastik, disarankan untuk mencari solusi bentuk tertutup dari LP deterministik. Karena itu berikut ini diaplikasikan model GFA ke suatu jaringan utama yang ditunjukkan dalam Gambar 4.3.


31

Gambar 4.3 : Jaringan prototype

Dalam contoh ini yang diperhatikan hanya 3 subnet dan 2 pasangan O-D, (1,2), dan (2,3). Track yang diperlukan adalah R12 dan R34. Misalkan x1 , x2, x3, x4 adalah track flow traversing path (1-2), (2-3), (1-3-2), dan (2-1-3). Juga untuk link (i, j) terdapat kapasitas Cij . Dengan parameter-parameter tersebut GFA dapat diekspresikan sebagai berikut, min y =

4 X

dk xk

(4.16)

k=1

Kendala x1 + x3 = R12 x2 + x4 = R23 x1 + x4 ≤ c12

(4.17)

x2 + x3 ≤ c23 x3 + x4 ≤ c31 diberikan dk (k = 1, . . . , 4), dk adalah biaya flow ke-k. Solusi optimal dapat diperoleh secara grafik. Asumsikan d1 − d3 > d2 − d4 , maka x1 dan x2 optimal adalah x∗1 = R12 + (R23 − c23 − c31)/2 x∗2 = R23 + (R23 − c23 − c31)/2


(4.18)

32 Dan x1 , x2 optimal dapat diperoleh dari persamaan konstrain. Jika R12 = R23 = R dan C12 = C23 = C31 = C, maka solusi optimal dapat direduksi menjadi, x∗1 = 3R/2 − c x∗2 = R/2 x∗3

(4.19)

= C − R/2

x∗4 = R/2 Untuk metode WS, perlu diselidiki bentuk cdf ataupun pdf solusi optimal, pdfnya adalah komposisi (konvolusi) dari pdf R dan C karena xk optimal adalah jumlah aljabar dari R dan C. Dalam transmisi digital terdapat dua tipe kasus yakni C = konstanta untuk Time Division Multiplexing (TDM) dan C perubahan dinamik dari TDM secara statistik (STDM), yang tergantung pada metode penjadualan khusus sama seperti halnya jaringan track load. Contoh, metode Weighted Fair Queuing (WFQ) mengalokasikan link capacity secara signifikan berbeda dari Head-of-line queuing. Secara umum, paradigma STDM membawa kerumitan tambahan pada analisis jaringan dan bagaimana menaksir C masih dalam penelitian. Dalam penelitian ini hanya diselidiki STDM untuk model klasik M/M/1. Dalam kasus ini, pdfnya adalah, λ −λ/r e r2 λ fC (c) = 2 e−µ/c c

fR (r) =

(4.20)

Menurut teori probabilitas diketahui bahwa pdf dari x∗1 = 3R/2 − C sebagai berikut,


33

fx1 (z) =

Z∞

fR (v)fc

z

=

3λµ 2

Z∞

(4.21) −3λ/2v −µ/(v−z)

e

v 2(v

e − z)2

z

Nampaknya sulit, walaupun tak mustahil, memperoleh hasil analitik dari bentuk integral ini. Karenanya, harus digunakan teknik analisa numerik. Karena komputasi akan cukup banyak, pendekatan WS hanya terpakai untuk paradigma TDM dimana pdf dari x∗k diberikan oleh persamaan (4.19) karena C konstan. Kita lihat kembali metode HN. Karena model Poisson tetap berguna untuk track pada session connection layer, pada kerja berikut dia dipakai untuk pertama-tama menyederhanakan pendekatan HN, meskipun model GFA tidak perlu bersandar pada persyaratan Poisson. Dengan cdf pada persamaan (4.15) dari model CP, konstrain (4.17) ditransformasi ke, Prob(

X

xp ≥ Rπ ) = FR(

π∈Pπ

X

xp )

(4.22)

π∈Pπ

Atau X π∈Pπ

xp ≥

c −c 1 − qπ

(4.23)

dimana q adalah peluang yang diinginkan. Persamaan konstrain untuk R telah dikonversi ke pertidaksamaan. Secara umum, pertidaksamaan ini tak diperlukan untuk kasus deterministik, karena konsep awal berasal dari keseimbangan demandsupply dalam masalah transportasi. Dengan kata lain, pertidaksamaan harus dianggap sebagai pengaruh kumulatif dari banyak nilai dengan masing-masing peluangnya.


34 Untuk paradigm TELNET yang telah didiskusikan di bagian awal bab 3, konstrain (4.23) dapat juga ditransformasi ke bentuk berikut, Prob(

X

xp ≥ Rπ ) = FR (

π∈Pπ

X

x p ) ≥ qπ

(4.24)

π∈Pπ

melalui pdf (4.7). Tapi karena secara umum FR (·) bentuknya tak tertutup, perlu dilibatkan prosedur numerik untuk menghitung transformasi. Paradigma FTPDATA juga memiliki situasi serupa. Di atas juga telah dijelaskan konsep penting yang terdapat pada pendekatan HN. Variabel rancangan xk adalah merupakan jejak-jejak lintasan (threshholds). Untuk menjadi eksak, threshold demikian diperoleh di batas cdf dari variabel random yang diselidiki. Dalam paradigma TDM, kapasitas link diberikan sebagai konstanta, maka transformasi HN tak terpakai untuk konstrain (4.17) dalam model GFA, seperti telah ditunjukkan dalam contoh di atas. Disamping itu, dinamik dari kapasitas link dalam paradigma STDM secara langsung tergantung pada disiplin penjadualan yang dipakai pada lapisan paket rute (packet routing layer) dan hingga kini belum teridentifikasi bentuk distribusi yang representatif untuk itu. Prototipe jaringan yang ditunjukkan Gambar 4.3, kembali digunakan untuk menyederhanakan pendekatan HN melalui distribusi CP. Agar mudah, asumsikan bahwa R12 = R23 = R dan C12 = C23 = C, maka hasil transformasinya adalah,


35

X1 + X3 ≥ λq X2 + X2 ≥ λq X1 + X4 ≤ C

(4.25)

X2 + X3 ≤ C X3 + X4 ≤ C Dimana λq =

λ −λ 1 − ln(q)

(4.26)

Dan q adalah threshold khusus (antara 0 dan 1). Berdasarkan hal itu, solusi optimal adalah X1∗ = 3λq/2 − C X2∗ = λq/2 X3∗

(4.27)

= C − λq/2

X4∗ = λq/2 Berikut ini pengaruh metode Skenario Tracking diintegrasikan dengan paradigma FA dijelaskan melalui dua studi kasus dari prototype jaringan backbone dalam Gambar 4. Parameter-paramater berikut digunakan untuk membentuk rancangan optimisasi π : (1,2), (1,3), (2,4), (3,4), Ci : 7.0, 8.0, 8.5, 8.5 (untuk link (1,2), (1,3),(1,4),(2,3),(3,4) berturut-turut), dp : 2, 3, 6, 4, 9, 3, 2, 2, 7, 3,5. Semua path yang mungkin dipruntukkan bagi pasangan OD tertentu kecuali path 2-1-3-4 dan 2-3-1-4 untuk alasan sembarang. Karenanya ada 11 path. Studi kasus yang pertama tentang paradigma dimana perubahan track terjadi antara 0 dan 4 dengan 64 skenario. Untuk tiap skenario diberikan peluang


36 yang diinginkan. Sebagai suatu masalah MC, model GFA tak memiliki solusi analitik. Karenanya digunakan suatu software Program Stokastik untuk melakukan perhitungan. Beberapa teknik program linier dengan konstrain standar telah terintegrasi ke dalam software ini. Hasil kerja optimisasi ini ditampilkan dalam Tabel 4.1 dimana rata-rata dari solusi optimal juga disertakan untuk rujukan.

Tabel 4.1 : Hasil Optimisasi dari 64 Skenario untuk 11 Path Rata-rata Hasil ST

X−1 1.544 1.619

X−2 0.476 0.300

X−3 0.131 0.000

X−4 0.867 0.582

X−5 0.012 0.000

X−6 1.122 1.203

Rata-rata

X−7 1.095

X−8 0.797

X−9 0.286

X−10 1.978

X−11 0.077

Y 24.349

Dari tabel, terlihat bahwa rata-rata biaya optimal cukup dekat ke tracked hasil ST. Proses lebih lanjut, seperti estimasi parameter, pengujian hipotesis dan analisis varians dapat dilakukan dengan menggunakan hasil skenario sebagai input. Studi kasus kedua tentang suatu paradigma dimana track secara random berubah diantara 0 dan 4, dengan 1024 skenario. Probabilitas. Hasilnya bersamasama dengan rata-rata solusi optimal disajikan dalam Tabel 4.2.


37 Tabel 4.2 : Hasil Optimisasi dari 1024 Skenario untuk 11 Path Rata-rata Hasil ST

X−1 1.407 1.738

X−2 0.435 0.157

X−3 0.133 0.000

X−4 0.970 0.647

X−5 0.011 0.000

X−6 1.099 1.255

Rata-rata Hasil ST

X−7 1.208 0.826

X−8 0/837 1.171

X−9 0.267 0.919

X−10 1.643 0.827

X−11 0.047 0.000

Y 23.192 23.232

Eksperimen numerik ini dilakukan dengan memakai PC Dell yang memiliki spesifikasi (1) CPU-Intel Pentium 4: 1,7 GHz, (2) Sistem operasi Linux, versi 2.4-10. Dalam uji coba ini, waktu yang diperlukan software untuk menghitung 64 skenario sangat singkat sehingga dapat diabaikan sementara untuk yang 1024 skenario diperlukan waktu sekitar 3 detik, karenanya model program stokastik yang berbasis GFA ini memiliki run time yang cukup singkat sehingga dapat diterima.


BAB 5 KESIMPULAN

Metodoligi Program Stokastik (PS) berguna untuk optimisasi jaringan dimana parameter beafluktuasi secara random. Metode pendekatan yang diadaptasi oleh PS adalah metoda Here and Now (HN), metoda Wait and See (WS) dan metoda Scenario Tracking (ST). Dalam aplikasi jaringan, pengaruh stokastik dari track ditandai oleh satu himpunan peluang. Peluang ini dapat dievaluasi dari kontrak QoS untuk suatu jaringan baru atau diupdate dari rekaman statistik oleh network management services untuk jaringan yang tersedia. Jika distribusi taksiran cukup dekat ke rumus analitik, maka metode HN (metoda ini membuat keputusan sebelum semua skenario diobservasi) akan menjadi pilihan untuk digunakan, jika tidak maka lebih baik gunakan metode ST karena dasar dari metode ini berorientasi simulasi dimana keputusan dibuat setelah semua skenario diobservasi. Penelitian ini telah menghasilkan suatu model program stokastik untuk rancangan jaringan telekomunikasi (lihat persamaan 4.16), khususnya untuk masalah arrival rate, dengan menggunakan pendekatan metoda HN, metoda WS dan metoda ST yang diintegrasikan ke dalam model generik Flow Assignment, dimana inter arrival time mengikuti distribusi Eksponensial Negatif dan panjang session masing-masing berdistribusi Pareto, Log Ekstrim dan Poisson Campuran. Implementasi model dilakukan untuk 64 skenario dan 1024 skenario dengan menggunakan software Program Stokastik dan diperoleh run time dalam ukuran detik sehingga dapat diterima (cukup memadai).


DAFTAR PUSTAKA

Azgomi M.A. and Movaghar A. 2002. Application of Stochastic Activity Networks on Network Modelling, Proceeding of the 10th International Conference on Software, Telecommunication, and Computer Network, Dubrovnik. Bazaraa M., Jarvis J. 1997. Linear Programming and Network Flow, New York : Wiley. Bertsekas D. and Gallager R. 1941.The Pure Theory of Production Under Technological Risk and Uncertainty, Econometrica, 1941; 9:298-304. Dembo D.1991. Scenario Optimization, Annals of Operation Research; 30: 63-80. Dempster M. 1980. Stochastic Programming, New York, Academic Press. Gloagulen C., Fleischer F., Schmidt H., Schmidt V.2006. Fitting of Stochastic Telecommunication Network Models via Distance Measures and Monte Carlo Tests, Telecommunication Syst.; 31:353-377. Higle J.L. and Suvrajet S.1999. An Introduction Tutorial on Stochastic Linier Programming Models, Arizona. Ji Xiaoyu, 2005. Models and Algorithm for Stochastic Shortest Path Problem, Applied Mathematics and Computation; 170:503-514. Konak A. and Bartolacci. 2007. Designing Survivable Resilient Network : A Stochastic Hybrid Genetic Algorithm Approach, The International Journal of Management Science; 35: 645-658. Paxson V. 1994. Empirical Derived Analytic Models of Wide Area TCP Connection, IEEE/ACM Transaction on Networking; 2: 16-36. Paxson V., Floyd S.1995. Wide Area Track : The Failure Poisson Modelling, IEEE/ACM Transaction Networking; 3: 226-244. Pitts J., Schomans J.1996. Introduction to ATM Design and Performance, Chicester, Wiley. Powell M. 1964. An Eficient Method for Finding The Minimum of The Function of Several Variables without Calculating Derivatives, Computer Journal, 1964; 7: 155-162. Ross S. 1989. Introduction to Probability Model, 4 ed, San Diego, Academic Press, Tintner G.1994. The Pure Theory of Production under Technological Risk and Uncertainty, Econometrica,1994; 9: 298-304 Yao Z. 1997. ATM Network Model for Traffic Management, Dept. of Electrical and Computer Engineering, University of Manitoba, Winipeg.


MODEL PROGRAM STOKASTIK DALAM RANCANGAN JARINGAN TELEKOMUNIKASI

Recommend Documents