BAB III LANDASAN TEORI
3.1 Model Jaringan Komputer 3.1.1 Topologi dan Perangkat Jaringan A. Topologi LAN hub/switch/repeater
Tree
Termi
Star
Bus
Ring
Gambar 3.1 Topologi Jaringan LAN Sumber: Stallings (2004, p470) Yang dimaksudkan dengan topologi jaringan adalah bagaimana sistem akhir, atau komputer yang berada pada suatu jaringan saling terhubung. Sekarang ini, pada LAN lebih banyak digunakan teknologi Ethernet (star) dengan hub, switch atau repeater sebagai unit pusat jaringan.
B. Perangkat Jaringan Jaringan komputer menggunakan beberapa perangkat sebagai berikut. •
Kartu Jaringan Æ Untuk menghubungkan komputer dan saluran.
19
•
Repeater dan Hub Æ Alat ini berfungsi untuk memperkuat atau menghasilkan sinyal ulang, untuk memperpanjang jangkauan.
•
Switch Æ Switch menggunakan alamat kartu jaringan untuk menyaring data yang diterima dan untuk dikirimkan ke tujuan.
•
Router Æ Router digunakan untuk menghubungkan beberapa jaringan yang mungkin berbeda seperti Ethernet, serial WAN, dan sebagainya. Router dapat bekerja dengan alamat IP.
3.1.2 Local Area Network (LAN) Ethernet adalah standar yang dikeluarkan pada tahun 1982 oleh Digital Equipment, Intel dan Xerox. Keunggulan dari
Ethernet terletak pada
kemudahan implementasi, kecepatan yang tinggi dan integritas data yang dapat diandalkan. Ethernet menggunkaan teknologi CSMA/CD (Carrier Sense Multiple Access With Collision Detection) untuk menjalankan fungsi-fungsi di atas. Jenis protokol LAN lainnya adalah Token Ring dan FDDI. Sebuah paket jaringan yang dinamakan token akan dikirimkan dari suatu perangkat ke perangkat lainnya dalam jaringan. Ketika sebuah perangkat memiliki data untuk dikirimkan, perangkat tersebut harus menunggu hingga mendapatkan token, barulah mengirimkan data. Ketika selesai mengirim, token tersebut dilepaskan dan dikirimkan ke perangkat lainnya.
20
3.1.3 Wide Area Network (WAN) WAN adalah jaringan yang luas, biasanya terdiri dari beberapa LAN yang tersebar di lokasi yang berjauhan, dan dihubungkan dengan saluran jarak jauh Standar perangkat fisik yang terdapat pada WAN yaitu EIA/TIA-232 yang menyediakan kecepatan data hingga 64 Kbps, dan EIA/TIA-449/530 yaitu versi yang lebih cepat dari EIA/TIA-232 (hingga 2 Mbps). Standar lainnya adalah V.35. Standar Data Link Layer yang biasa digunakan adalah HighLevel Data Link Protocol (HDLC) dan Point-to-Point Protocol (PPP). Jenis saluran WAN adalah sebagai berikut. A. Point-to-Point Saluran point-to-point menyediakan jalur WAN tunggal terdedikasi dari suatu lokasi ke lokasi lainnya yang berjauhan. Biasanya saluran tersebut disewakan, dan digunakan secara pribadi (leased line). Biaya yang dikeluarkan bergantung pada kapasitas (bandwidth) dan juga jarak
B. Circuit-Switching Dengan konsep circuit-switching, komunikasi dilakukan melalui jalurjalur yang sudah tersedia. Jalur tersebut diaktifkan dan dihubungkan ketika komunikasi akan dimulai, lalu jalur tersebut akan dikuasai. Pada awalnya circuit-switching digunakan untuk mengirimkan suara namun sekarang juga digunakan untuk mengirimkan data. Jaringan Integrated Services Digital Network (ISDN) adalah salah satu contohnya.
21
C. Packet-Switching Saluran circuit-switching memiliki beberapa kekurangan, seperti rendahnya utilisasi jaringan dan kesulitan dalam menghubungkan perangkat-perangkat kecepatan yang berbeda. Packet switching digunakan dengan harapan sebagai berikut. •
Efisiensi atau utilisasi jaringan yang lebih baik, dapat digunakan oleh beberapa pihak
•
Komunikasi dengan kecepatan yang berbeda.
•
Sistem
antrian
paket
data
memungkinkan
terjadinya
penundaan, dan bukan penolakan. •
Dapat dilakukkan prioritasi terhadap paket-paket data tertentu.
Contoh teknologi WAN dengan packet-switching adalah X.25, Frame Relay, dan Asynchronous Transfer Mode (ATM). Terdapat pula teknologi dial-up yang menggunakan jaringan analog telepon sebagai pembawa data.
Peralatan jaringan yang biasa dipakai pada WAN adalah sebagai berikut. •
Switch WAN, pada infrastruktur jaringan pembawa ISP.
•
Server akses, untuk menampung koneksi yang menggunakan layanan dial-up (menggunakan modem).
•
Modem, adalah perangkat yang digunakan untuk mengubah sinyal analog menjadi digital, dan juga sebaliknya yang .
•
High Data Rate Digital Subscriber Line (HDSL), digunakan untuk menghubungkan router ke sirkuit digital seperti E1.
22
Untuk mendapatkan hubungan infrastruktur ISP, biasa diperlukan perangkat pada pengguna yang biasa disebut Customer Premises Equipment (CPE). Terdapat perangkat DTE (Data Terminal Equipment) pada pengguna (router), yang akan menggunakan DCE (Data Communications Equipment) untuk mengakses jaringan telekomunikasi WAN. Koneksi serial (point-topoint) adalah koneksi yang banyak dipakai untuk menghubungkan DTE dan DCE. Pada koneksi serial, kecepatan transfer data ditentukan oleh clock rate yang menyatakan jumlah bit per detik yang dapat dikirimkan. Sebagai contoh, clock rate 64000 akan memberikan kapasitas 64Kbps pada saluran. Clock rate ini hanya dapat ditentukan pada perangkat DCE . Tabel 3.1 Kapasitas Saluran WAN Sumber: (www.comptechdoc.org) Teknologi Dial Up Frame Relay E1 E3 SDH ATM
Kecepatan 56 Kbps 56 Kbps -.544 Mbps 1,544 Mbps 44,736 Mbps 51,8 Mbps (OC-1) 155 – 622 Mbps
Karakteristik Digunakan bersama-sama Besar paket berbeda-beda 24 kanal suara 672 kanal suara OC-1 - OC-48 (2488,32 Mbps) Paket dengan ukuran tetap
3.2 Protokol Jaringan Komputer Secara umum, protokol jaringan komputer memiliki fungsi-fungsi dan karakteristik sebagai berikut. •
Fungsi jaringan dibagi ke lapisan-lapisan protokol yang ada.
•
Enkapsulasi data, menjadi Protocol Data Unit (PDU).
•
Fragmentasi (pemotongan) data dan pengelompokan data kembali.
23
•
Kendali akan koneksi, secara connection-oriented atau tidak.
•
Data atau PDU dirangkai dengan urutan yang benar
•
Kendali kecepatan komunikasi
•
Kendali kesalahan dalam pengiriman data, deteksi dan perbaikan.
•
Pengalamatan pada berbagai level, seperti layer 3 dan layer 2.
•
Penggunaan saluran untuk beberapa komunikasi sekaligus.
•
Layanan transmisi dan transportasi.
3.2.1 Protokol Internet (IP) Protokol IP menawarkan koneksi yang bersifat connectionless di mana untuk berkomunikasi, tidak ditentukan jalur tertentu, melainkan secara packetswitched. Setiap paket data dikirimkan berdasarkan keputusan terbaik (routing decision), pada pengirim dan pada sistem perantara (router). Keputusan dipilih berdasarkan pertimbangan yang statis atau dinamis IP tidak menjamin bahwa paket data akan sampai dengan benar, atau dengan urutan yang benar pula, karena jalur pengiriman juga dapat berbeda. Karakteristik IP yang fleksibel ini membuat IP dapat digunakan pada berbagai macam aplikasi seperti Internet Control Message Protocol (ICMP), dan digunakan bersama protokol lain yang memiliki fungsi-fungsi yang tidak dimiliki IP (TCP atau UDP)
24
Gambar 3.2 Format Header Paket Data IP Versi 4 Sumber: Stallings (2004, p3593) Setiap paket data IP (versi 4) memiliki header seperti pada gambar 3.2 di atas. Informasi penting yang terdapat pada header tersebut adalah: •
Identification (16 bit) Æ nomor urut, sebagai identifikasi
•
Time to Live (8 bit) Æ jangka waktu paket berada di internet
•
Protocol (8 bit) Æ protokol satu level di atas yang akan menggunakan IP.
•
Source Address (32 bit) Æ alamat sumber
•
Destination Address (32 bit) Æ alamat tujuan
•
Data (bervariasi) Æ data dengan ukuran kelipatan 8 bit, dengan ukuran maksimal 65.535 oktet (data ditambah header).
Alamat IP yang dapat digunakan (32 bit, terdiri dari network id dan host id dengan jumlah bit yang bervariasi), terdiri dari alamat IP publik (yang dikenal di internet) dan alamat IP yang digunakan secara internal (privat).
3.2.2 Transmission Control Protocol (TCP) TCP menawarkan komunikasi secara connection-oriented, artinya dua aplikasi yang menggunakan TCP harus melakukan persiapan komunikasi
25
terlebih dahulu (dikenal sebagai three-way-handshake, dengan SYN dan ACK) sebelum memulai pertukaran data. TCP juga menyediakan kehandalan yang dapat digunakan bersamaan dengan IP, seperti: •
TCP memecah data pengguna menjadi potongan-potongan kecil dengan ukuran yang optimal (terbaik).
•
TCP memasang penanda waktu ketika mengirim data dan menunggu konfirmasi (acknowledge, ACK) dari pihak lain. Di sini ACK berfungsi sebagai penanda kemungkinan adanya paket yang hilang, dan juga penanda dalam mengatur kecepatan komunikasi.
•
TCP menyediakan deteksi kesalahan (checksum) pada header dan data, sedangkan pada IP hanya headernya saja.
•
TCP dapat mengurutkan kembali paket-paket data sesuai dengan urutannya (jika sampai di tujuan tidak secara berurutan).
•
TCP dapat mendeteksi adanya duplikasi paket.
•
TCP dapat mengatur kecepatan komunikasi.
Gambar 3.3 Enkapsulasi TCP Pada IP Sumber: Stevens (1994, p225)
26
Dalam penggunaannya
dengan IP, header dan data TCP akan
dienkapsulasikan pada paket data IP seperti pada gambar 3.3. TCP menambahkan pengalamatan aplikasi berupa alamat port aplikasi.
Gambar 3.4 Format Header TCP Sumber: Stallings (2004) Informasi penting pada header TCP adalah sebagai berikut. •
Source Port (16 bit) dan Destination Port (16 bit) Æ Alamat aplikasi
•
Sequence Number (32 bit) Æ Urutan urutan data sejak paket SYN yang pertama (dalam satuan oktet).
•
Akcnoledgment Number (32 bit) Æ Menyatakan sequence number dari oktet data berikutnya yang diharapkan untuk diterima.
•
Flags (6 bit) Æ Penanda, terdiri dari 1 bit, jika bernilai 1 , maka : 1. URG, menyatakan bahwa urgent pointer dipakai. 2. ACK, paket merupakan tanggapan. 3. PSH, menyatakan data akan langsung dikirimkan. 4. RST, mengulang koneksi. 5. SYN, menginisialisasikan nomor urut koneksi. 6. FIN, tidak ada data lagi yang akan dikirim.
27
•
Window (16 bit) Æ alokasi kredit untuk pengaturan kecepatan komunikasi.
•
Checksum (16 bit) Æ deteksi kesalahan header dan data
Berikut gambaran mengenai awal dan akhir dari transaksi TCP yang berorientasi pada koneksi. Awal transaksi diawali oleh pertukaran paket data yang disebut sebagai three-way-handhake. SYN SYN,ACK ACK Pertukaran Data FIN FIN,ACK ACK
Gambar 3.5 Transaksi Awal dan Akhir TCP Sumber: Stevens (1994, p232) A. Pertukaran Data Interaktif TCP menggunakan paket dengan tanda ACK untuk menandakan bahwa paket yang dikirim telah diterima. Bila ACK tidak diterima dalam waktu tertentu, maka terdapat kemungkinan bahwa paket tidak sampai ke tujuan atau tertunda terlalu lama hingga batas waktu timeout. Menurut Stevens (1994, p267), algoritma Nagle adalah algoritma yang menyatakan bahwa
28
sebuah ACK dapat menandakan bahwa beberapa paket sekaligus telah diterima. Untuk mengirimkan sejumlah data, TCP memiliki batasan jumlah yang dapat dikirim berupa window size (dari penerima). Implementasi slow start pada TCP menambahkan sebuah window baru yaitu congestion window (cwnd). Slow start digunakan untuk mengatur jumlah paket yang dapat dikirimkan pada awal komunikasi, dengan pertimbangan keadaan jaringan. Jumlah paket yang dapat dikirimkan adalah min(window,cwnd). Pada awal transaksi, cwnd ditetapkan pada nilai 1, dan bertambah 1 setiap ada ACK yang diterima.
B. Estimasi RTT (Round Trip Time) dan RTO (Retransmission Time Out) TCP menggunakan beberapa penghitung waktu (timer) yang digunakan untuk menandakan bahwa suatu paket telah hilang. Bila terjadi demikian, TCP akan berusaha untuk mengirimkan ulang paket tersebut. Besar waktu yang digunakan untuk menyatakan bahwa sebuah paket telah hilang disebut sebagai RTO. RTO dihitung berdasarkan perkiraan waktu yang digunakan untuk mengirimkan paket ke tujuan dan kembali (ACK) yang disebut sebagai RTT (Round Trip Time). Untuk setiap ACK yang diterima, dilakukan pemulusan terhadap estimasi RTT R = α R + (1 − α ) M , dengan α = 0,9 dan M adalah perhitungan RTT terbaru. Perhitungan RTO dilakukan menggunakan estimasi terhadap RTT. RTO = A + 2D , dengan A=0 dan D=3 untuk paket SYN awal. Untuk berikutnya
29
RTO = A + 4D Æ exponential backoff, dengan pengali 2, 4, 8...64 Algoritma Karn menyatakan bahwa jika suatu paket mengalami timeout dan dikirim ulang, maka RTT tidak diupdate ketika ACK diterima, karena masalah ambiguitas mengenai paket mana yang di-ACK. Ketika data berikut diterima, nilai A dan D akan diubah menggunakan pemulusan RTT dan pemulusan deviasi rata-rata. A = M + 0.5 , dengan M adalah penghitungan waktu terakhir. D = A/2 RTO = A + 4D. Pemulusan estimasi akan dilakukan ketika ACK berikut diterima Err = M – A A = A + g Err D = D + h ( |Err| - D ) RTO = A + 4D C. Algoritma Penghindaran Kongesti TCP (Congestion Avoidance) Pada batas tertentu, mungkin terjadi kongesti pada jalur, dan paket akan hilang. Stevens (1994, p291), menjelaskan bahwa kongesti dapat terjadi pada LAN yang dihubungkan ke WAN, atau pada router dengan jumlah aliran data masukan yang lebih besar dari keluaran. Terdapat 2 penanda bahwa paket hilang, yaitu terjadinya timeout dan diterimanya ACK duplikat (3 atau lebih). Untuk itu diperlukan algoritma penghindaran kongesti. Slow start dan congestion avoidance menggunakan dua variabel yaitu cwnd dan ssthresh. Operasi keduanya adalah sebagai berikut. 1. Inisialisasi cwnd = 1 dan ssthresh = 65535 2. Jumlah paket yang dapat dikirim adalah min (window, cwnd).
30
3. Ketika kongesti terjadi (ACK duplikat atau timeout), nilai sshtresh menjadi 1 2 dari min (cwnd, window). Jika kongesti
ditandai dengan timeout, maka cwnd menjadi bernilai 1. 4. Ketika data di ACK, cwnd akan ditambah sesuai dengan kondisi apakah menjalankan slow start atau congestion avoidance. Pada slow start, cwnd ditambah 1, pada congestion avoidance, cwnd ditambah 1/cwnd.
D. Algoritma Fast Retransmit dan Fast Recovery Jika terdapat ACK duplikat (3 atau lebih), ini dapat menandakan bahwa paket telah hilang. Karena ACK duplikat hanya dikirimkan ketika menerima data lain (yang tidak berurutan), maka ini menandakan bahwa aliran paket data tetap bekerja. Paket data yang hilang dikirimkan ulang tanpa menunggu timeout. Ini adalah algoritma fast retransmit. Berikutnya, congestion avoidance yang dijalankan, bukan slow start. Ini adalah
algoritma fast recovery. Kedua algoritma ini sering dioperasikan bersamasama sebagai berikut. 1. Ketika ACK duplikat ketiga diterima, nila ssthresh menjadi 1 2 dari cwnd. Kirim ulang paket yang hilang, dan nilai cwnd berikutnya adalah ssthresh ditambah 3 kali ukuran segmen. 2. Ketika ACK duplikat berikutnya diterima, tambah cwnd sebesar ukuran segmen, dan kirimkan paket berikutnya.
31
3. Ketika ACK yang mengkonfirmasi data diterima, ubah nilai cwnd menjadi ssthresh. ACK ini adalah ACK untuk paket yang
dikirim ulang pada langkah 1.
3.2.3 User Datagram Protocol (UDP) UDP menyediakan layanan yang bersifat connectionles., Keunggulan dari
komunikasi connection-oriented tampak pada bahasan TCP di atas, namun pada beberapa keperluan sebagai berikut, koneksi yang bersifat connectionless lebih cocok digunakan. •
Pengambilan data terus-menerus, seperti sensor.
•
Pengiriman data secara massal, dengan interval tertentu.
•
Komunikasi dengan interaksi yang singkat.
•
Aplikasi dan komunikasi real time
UDP beroperasi di atas IP, dengan menambahakan pengalamatan port
pada IP. Fasilitas deteksi kesalahan (checksum) pada UDP juga opsional, dan bila terjadi kesalahan pada pengiriman, tidak ada tindakan lanjut atas kesalahan atau kehilangan tersebut.
Gambar 3.6 Format Header UDP Sumber: Stallings (2004, p701)
32
3.2.4 Domain Name System (DNS) DNS adalah layanan database alamat terdistribusi yang berperan dalam
pemetaan hostname (nama suatu host atau komputer) menjadi alamat IP. Untuk berkomunikasi dengan komputer lain, dapat digunakan nama (selain alamat IP) yang lebih mudah diingat seperti www.cisco.com. Informasi pemetaan alamat DNS dibagi-bagi ke pihak-pihak yang berwenang untuk teritori terentu di internet. DNS dalam operasinya bekerja di atas UDP dan IP, dan untuk menggunakan layanan DNS, pihak yang ingin berkomunikasi harus menghubungin DNS server yang bersangkutan.
3.2.5 HyperText Transfer Protocol (HTTP) HTTP adalah protokol dasar pendukung WWW. HTTP adalah protokol
yang bersifat client/server, dengan client yang umum adalah web browser, dan server berupa web server. HTTP bekerja di atas TCP dan IP. HTTP menggunakan komunikasi yang bersifat stateless, di mana setiap
transaksi dilayani secara berbeda. Hal ini mendukung operasi yang dilakukan pada WWW, yang terdiri dari permintaan halaman web ke server (request), dan aksi atau tanggapan dari server (response), berupa informasi yang diminta dan status tanggapannya.
Gambar 3.7 Transaksi HTTP dengan perantara Sumber: Stallings (2004, p764)
33
Untuk setiap obyek pada halaman web, akan dibuka satu koneksi TCP ke server, dan server akan mengirimkan data tersebut melalui sesi terebut.
Operasi ini memiliki kekurangan yaitu banyaknya persiapan yang dilakukan oleh setiap koneksi TCP, untuk sesi komunikasi yang singkat. HTTP versi 1.1 memberikan opsi untuk menggunakan satu koneksi saja untuk mengambil beberapa obyek. (Persistent Connection) Berikut contoh transaksi HTTP Æ permintaan dari client
GET / HTTP1.1
HTTP/1.1 200 OK Æ balasan dari server, header dan body Date: Fri, 29 Dec 2006 10:30:15 GMT Server: Apache/2.0.54 (Unix) mod_ssl/2.0.54 OpenSSL/0.9.7d PHP/5.1.2 X-Powered-By: PHP/5.1.2 Content-Length: 4 Connection: close Content-Type: text/html Æ data berupa halaman web
…
3.2.6 Komponen Protokol VoIP
Berikut adalah protokol-protokol yang dapat dipakai dalam mendukung VoIP. •
Protokol
sinyal :
SIP/SDP
(Session
Description
Protocol)
(dikeluarkan oleh IETF, Internet Engineering Task Force) , H.323 (ITU-T), MGCP (Media Gateway Control Protocol, MEGACO (H.248), IAX, IAX2. •
Protokol media : RTP (milik IETF, diadopsi ITU-T)
34
•
Protokol transportasi : TCP, UDP, SCTP (Stream Control Transport Protocol).
•
Protokol pendukung seperti DNS.
3.2.7 Session Initiation Protocol (SIP) SIP
adalah
protokol
aplikasi
yang
bertugas
dalam
memulai,
mengendalikan dan mengakhiri percakapan multimedia. SIP dikembangkan oleh IETF pada tahun 1999. SIP sering digunakan bersamaan dengan RTP dan SDP. RTP digunakan untuk membawa data percakapan, dan SDP digunakan
untuk memberikan informasi mengenai kemampuan dari partisipan, agar dapat berpartisipasi
dalam
komunikasi
(seperti
negosiasi
codec,
protokol
transportasi, dan sebagainya). SIP dirancang untuk bekerja pada model internet, bekerja mirip dengan HTTP dan metode pengalamatan yang mirip dengan alamat e-mail. Pengguna SIP
diidentifikasikan
dengan
SIP
URI
dengan
format
berupa
sip:username@domain, yang terdiri dari nama pengguna (username) dan
nama domain.
3.2.8 Real-Time Transport Protocol (RTP) RTP distandarkan oleh IETF pada Januari 1996, mendukung pengiriman
data pada multimedia secara real time (audio dan video) melalui jaringan paket data (secara umum melalui UDP/IP). Protokol ini digunakan oleh SIP dan juga H.323. Protokol ini diharapkan dapat memberikan informasi seperti
35
pewaktuan (timing), aliran data codec, dan sebagainya. RTCP (Real-time Control Protocol) adalah protokol kontrol yang biasa dipakai bersamaan
dengan RTP. Pada sesi RTP, peserta komunikasi secara berkala mengirimkan paket RTCP untuk menerima atau memberikan informasi ke pengguna lainnya.
A. Analog menjadi Digital
Komunikasi real time selama ini lebih banyak menggunakan data dan sistem transmisi analog. Suara manusia dapat menghasilkan sebanyak 300 hingga 3300 Hz
perubahan sinyal elektrik. Nilai ini dipakai dalam
perhitungan penyediaan saluran transmisi (bandwidth 3000 Hz). Untuk sinyal video, bandwith yang dibutuhkan mendekati 4 MHz. Kekurangan yang dihadapi pada sistem transmisi analog adalah atenuasi (kekuatan menurun), distorsi waktu tunda, dan juga noise. Data dan transmisi dalam bentuk digital memiliki keuntungan seperti kurangnya pengaruh akan gangguan (noise). Pada sinyal suara, kebutuhan utama untuk mengubah dari analog menjadi digital adalah masalah kualitas. Untuk mengubah sinyal analog menjadi digital, dilakukan sampling untuk mengukur besaran sinyal sinusoidal tersebut, dan direpresentasikan dalam bentuk digital (Pulse Code Modulation, PCM). Sampling ini harus dilakukan sebanyak mungkin dalam unit waktu tertentu untuk mendapatkan gambaran yang memadai mengenai sinyal analog tersebut. Kualitas ini bergantung pada teknik sampling dari codec yang dipakai.
36
Tabel 3.2 Perbandingan Bandwith Codec Sumber: www.terracall.com/FAQs_white_1.aspx Codec
Bit Rate
Nominal Ethernet Bandwith (searah)
G.711 G.729 G.723.1 G.723.1 G.726 G.726 G.728 iLBC
64 Kbps 8 Kbps 6,4 Kbps 5,3 Kbps 32 Kbps 24 Kbps 16 Kbps 15 Kbps
87,2 31,2 21,9 20,8 55,2 47,2 31,5 27,7
Kbps Kbps Kbps Kbps Kbps Kbps Kbps Kbps
Codec G.711 (ITU) dengan kecepatan 64 Kbps, biasa digunakan pada
jaringan telepon digital. Codec ini menggunakan 8 bit encoding scheme PCM tanpa dikompres, dengan 8000 sampel per detik. Dengan G.711 VoIP akan memberikan kualitas suara terbaik, karena tidak ada kompresi.
Kekurangannya adalah bandwidth yang lebih besar, hingga 84,7 Kbps.
B. Transfer Data RTP
Paket data RTP akan dienkapsulasikan ke dalam paket UDP/IP. Bagian header berukuran 12 oktet, dapat ditambah hingga 4 sampai 60 oktet. Bagian PT atau Payload Type menandakan format data yang dibawa RTP. Tipe ini
merupakan pemetaan profil audio dan video, dari nomor tipe ke format data. SDP dapat digunakan untuk mengumumkan tipe apa yang dibawa ke aplikasi.
37
Gambar 3.8 Format Paket Data RTP Sumber: Perkins (2003)
3.3 Teori teletrafik 3.3.1 Konsep Trafik dan Unit Trafik
Menurut ITU-D (2006), teori teletrafik dapat didefinisikan sebagai aplikasi teori probabilitas dalam menyelesaikan permasalahan yang menyangkut perencanaan,
evaluasi
kinerja,
operasi
dan
perawatan
dari
sistem
telekomunikasi. Teori teletrafik adalah teori perencanaan yang menggunakan ilmu-ilmu yang dipakai pada riset operasi seperti proses stokastik, teori antrian dan simulasi numerik. Teletrafik mencakup trafik dari komunikasi data dan juga bentuk telekomunikasi lainnya (seperti telpon. Untuk menyatakan intensitas trafik, digunakan besaran trafik per unit waktu. Definisi dari intensitas trafik sumber layanan menurut ITU-D (2006) adalah jumlah perangkat atau layanan yang sibuk dalam satu unit waktu tertentu. Sumber layanan dapat berupa sejumlah server atau jalur telepon.
38
Gambar 3.9 Intensitas Trafik, Fungsi n(t) Terhadap Waktu Sumber: ITU-D (2006) Carried Traffic (Ac), adalah trafik yang dibawa pada sumber layanan
dalam interval T (gambar 3.9). Intensitas trafik biasa dihitung dengan menggunakan besaran erlang, sebagai penghormatan terhadap A.K Erlang (1878-1929), penemu teori trafik jaringan telepon. Carried Traffic tidak akan melebihi jumlah saluran (kanal), dengan nilai maksimum 1 erlang. Besaran lain yang banyak dipakai adalah CCS (Hundred Call Seconds), 1 CCS = 1 36 erlang. Offered Traffic A, adalah perhitungan yang digunakan pada model
teoritis, di mana trafik ini merupakan trafik layanan tanpa adanya penolakan atau kehilangan (karena jumlah server yang terbatas). Nilai Offered Traffic tidak dapat dihitung, namun dapati diestimasikan berdasarkan Carried Traffic. Rejected Traffic A l , adalah selisih antara Offered Traffic dan Carried Traffic. Nilai ini bisa dikurangi dengan memperbesar kapasitas sistem. Pada
pengukuran, besaran yang dapat diperoleh adalah Carried Traffic, yang didapat pada sistem yang berjalan sebenarnya.
39
Pada transmisi data, yang dibahas bukanlah durasi layanan, melainkan kebutuhan transmisi. Sebuah tugas dapat berupa pengiriman sejumlah s paket (bit atau byte). Jumlah trafik bervariasi sesuai dengan aktivitas pengguna. Trafik dapat berasal dari satu atau beberapa sumber yang independen satu sama lain. Penelitian trafik menunjukkan variasi trafik sebagian terdiri dari proses stokastik dan deterministik. Dalam perhitungan untuk membuat model trafik, pengukuran biasa dilakukan pada tenggang waktu yang memiliki jumlah trafik tertinggi (Busy Hour Traffic).
3.3.2 Grade of Service (GoS)
Pada penyediaan layanan jaringan, keputusan mengenai kualitas yang diberikan harus diperhatikan. QoS (Quality of Service), menurut ITU-T Recommendation E.800 didefinisikan sebagai kumpulan pengaruh atas
kualitas layanan, yang mempengaruhi derajat kepuasan yang diterima pengguna. QoS terdiri dari parameter kualitas layanan seperti dukungan layanan, operabilitas layanan, kemampuan layanan, dan keamanan layanan. Untuk memenuhi QoS tertentu, diperlukan penilaian GoS, yang didefinisikan oleh ITU-T Recommendation E.600 sebagai sejumlah variabel penelitian trafik yang menandakan ketersediaan sumber layanan pada kondisi tertentu. Kualitas ini dapat berupa penundaan waktu, peluang penolakan panggilan, peluang kehilangan paket data, dan sebagainya.
40
3.4 Teori Probabilitas dan Statistika 3.4.1 Peubah Acak dan Distribusi Peluang
Menurut Hillier dan Lieberman (2005, bab 24), pada saat melakukan percobaaan, kadang-kadang bukanlah keseluruhan hasil (ruang sampel) yang diperhatikan, namun fungsi-fungsi numerik yang diambil terhadap hasil percobaan tersebut (beserta distribusinya). Peubah acak adalah sebuah fungsi yang dinilai secara numerik dan ditentukan berdasarkan hasil percobaan. Hubungan antara peluang sebuah kejadian dan peluang mengenai peubah acak adalah topik yang penting.dalam teori probabilitas. Untuk setiap peubah acak, dikenal fungsi distribusi yang biasa disebut sebagai Cumulative Distribution Function (CDF) atau F(x). Fungsi distribusi merupakan peluang bahwa sebuah peubah acak X memiliki nilai yang lebih kecil atau sama dengan x. Fungsi probabilitas P(x), yang biasa disebut sebagai Probability Density Function (PDF) dan biasa disebut f(x), merupakan peluang bahwa sebuah
peubah acak X memiliki nilai x untuk ruang sampel diskrit P(X=x), dan peluang bahwa X berada dalam rentang nilai tertentu untuk ruang sampel kontinu P(a≤X≤b). Dengan demikian, F(x) memiliki hubungan dengan P(x) yaitu bahwa P(x) merupakan turunan dari F(x). F(x) = P (X ≤ x) =
∫
X X min
P( y )dy
X P(x) = F’(x) = [P ( x ')] X min = P(X) – P(Xmin)
Untuk probabilitas diskret, F(x) =
∑ P ( x)
X <x
41
3.4.2 Distribusi Binomial
Sebuah peubah acak X dikatakan memiliki distibusi binomial bila fungsi probabilitasnya dapat dikatakan sebagai: n! p k (1 − p ) n − k , dengan k !( n − k )!
P (X = k) = Px(k) =
n
∑ Px(k ) = 1 , k =0
di mana p berkisar antara 0 dan 1, n adalah bilangan bulat positif, dan k berkisar antara 0 ≤ k ≤ n. Distribusi ini memiliki 2 parameter, yaitu n (jumlah percobaan) dan p (peluang keberhasilan) pada setiap percobaan, dengan setiap percobaan hanya memiliki dua kemungkinan hasil. Bila n=1, distribusi binomial dapat diinterpretasikan sebagai P (X=0) = Px(0) = 1-p P (X=1) = Px(1) = p dan peubah acak demikian dikatakan memiliki distribusi Bernoulli.
3.4.3 Distribusi Poisson Sebuah peubah acak dikatakan memiliki distribusi Poisson bila memiliki fungsi probabilitas sebagai berikut. P(X=k) = Px(k ) =
λ k e−λ k!
,
dimana λ adalah konstanta positif (merupakan parameter distribusi), dan k bilangan bulat non negatif. Distribusi ini sering digunakan untuk situasi dimana sejumlah kejadian terjadi pada periode waktu tertentu, seperti kedatangan paket data dan dimana suatu kedatangan tidak berpengaruh pada kedatangan lainnya (secara acak).
42
3.4.4 Distribusi Normal Sebuah peubah acak dikatakan memiliki distribusi normal bila memiliki fungsi probabilitas sebagai berikut. ⎛ (k −μ ) ⎞ ⎟ 2σ 2 ⎠
⎜− 1 P( X = k ) = e⎝ σ 2π
Parameter dari distribusi ini adalah μ atau nilai rata-rata dan juga σ 2 (variansi). Distribusi normal dapat digunakan untuk pendekatan distribusi binomial dan juga Poisson.
3.4.5 Distribusi Geometrik Peubah acak X dikatakan memiliki distribusi geometerik bila fungsi probabilitasnya dapat dituliskan sebagai P(X=k) = Px(k ) = p (1 − p) k −1 , dimana parameter p adalah konstanta antara 0 dan 1, dan k > 0. Distribusi geometrik merupakan distribusi peubah acak berupa jumlah percobaan Bernoulli hingga peubah acak tersebut bernilai 1.
3.4.6 Distribusi Eksponensial Sebuah peubah acak (kontinu) dikatakan memiliki distribusi eksponensial bila fungsi probabilitasnya dapat dituliskan sebagai f ( x) = λ e − λ x , λ >0, t ≥ 0 F(x) = P(X≤x) =
∫
t
0
f (t )dt = 1 - e− λ x , 0 ≤ x ≤ ∞
43
1
rata-rata E[X}=
, variansi Var[X] =
λ
1
λ2
Parameter fungsi ini adalah θ , dengan λ merupakan
1
θ
.
Peubah acak ini banyak digunakan pada interval waktu seperti interval kedatangan, durasi komunikasi dan sebagainya.
3.4.7 Distribusi Gamma
Sebuah peubah acak (kontinu) dikatakan memiliki distribusi gamma bila fungsi probabilitasnya dapat dituliskan sebagai
f (x) =
λα λr x α −1e − α x = x r −1e − rx (bulat) , dengan Γ (α ) (r − 1)!
F ( x) =
1 Γ (α )
E[X] =
∫
λ x α −1 0
t
e − t (0 < x < ∞)
α α dan Var[X] = 2 λ λ
dengan Γ(α ) adalah fungsi gamma, dan
∫
λx
0
t α −1e− t dt adalah fungsi gamma
yang tidak lengkap (incomplete). Γ(1 2) = π , Γ(1) = 1 . Untuk bilangan bulat (selain negatif dan nol), Γ( z + 1) = zΓ( z ) = z !
3.4.8 Distribusi Erlang
Variabel acak X dikatakan memiliki distribusi Erlang jika fungsi probabilitasnya dapat dituliskan sebagai
44
f (x) =
λk ( k − 1) !
x k − 1 e − λ x , dengan
k −1
F ( x) = 1 − e−λ x ∑ i=0
= 1-
E[X] =
k
λ
(λ x )i (0 < x < ∞), i!
Γ(k , λ x) Γ(k )
dan Var[X] =
k
λ2
Distribusi Erlang memiliki kaitan yang erat dengan distribusi gamma, dimana α =k dan θ =
1
λ
. Pada kasus dimana k=1, maka distribusi Erlang
merupakan distribusi eksponensial. Untuk nilai k bulat positif, jumlah dari k bilangan acak eksponensial yang independen dan terdistribusi secara identik memiliki distribusi Erlang. Fungsi probabilitas Erlang biasa ditulis sebagai
f (x) =
(θ k ) k x k −1e − θ kx ( k − 1) !
dengan parameter θ dimana θ =
λ k
, dengan ekspresi ini, didapat
1 1 E[X]= , sama untuk setiap bentuk k, dan Var[X] = 2 kθ θ
3.4.9 Distribusi Chi-Square
Peubah acak Y dikatakan memiliki distribusi chi-square dengan n derajat bebas (n bilangan bulat positif), jika fungsi probabilitasnya dapat dituliskan sebagai
45
fY ( y ) =
1 −1 y ( n 2) e − y 2 , x>0 2 Γ ( n 2) n2
Simbol χ n2 akan lebih sering digunakan untuk menggantikan Y. Distribusi chi-square adalah distribusi gamma khusus dengan r =
1 n dan λ = . 2 2
3.4.10 Proses Stokastik
Menurut Hillier dan Lieberman (2005, p732), sebuah proses stokastik didefinisikan sebagai koleksi dari beberapa peubah acak (Xt) dimana indeks t berada pada himpunan T. Terkadang T diambil berupa himpunan bilangan bulat non negatif, dan Xt menyatakan sebuah karakteristik yang dicari dan dapat diukur pada waktu t. Pengamatan terhadap perilaku sebuah sistem yang beroperasi pada periode waktu tertentu sering menuju pada analisis dari sebuah proses stokastik dengan struktur demikian. Pada waktu tertentu yang ditandai dengan 0, 1, ..., sistem berada pada keadaan (state) yang ditandai dengan 0, 1..., M. Rentang antar waktu dapat sama atau berbeda-beda sesuai dengan perilaku sistem yang diamati. Keadaan (state) dari sebuah sistem dapat berarti secara kualitatif maupun kuantitatif, dan dapat digunakan untuk menyatakan jumlah keadaan yang ada pada suatu sistem. Representasi matematika dari sistem tersebut adalah sebuah proses stokastik (Xt), dimana peubah acak diukur pada waktu t=0, 1, 2, ... dan setiap peubah acak dapat berada pada keadaan 0, 1, ... M. Nilai ini merupakan karakterisasi dari (M+1) keadaan dari proses.
46
3.4.11 Rantai Markov
Asumsi mengenai distribusi bersama X0,X1,... penting untuk mendapatkan hasil analisis. Satu asumsi yang menuju pada kemudahan analisis adalah bahwa seubah proses stokastik adalah rantai Markov, yang memiliki ciri sebagai berikut: Sebuah proses stokastik dikatakan memiliki ciri Markov bila P( Xt+1=j | X0=k0, X1=k1, .... Xt-1=kt-1, Xt=i ) = P( Xt+1=j | Xt=i) untuk t=0,1,.... dan setiap urutan i, j, k0, k1,..., kt-1. Ciri Markov ini dapat ditunjukkan sama dengan menyatakan bahwa peluang kondisional pada waktu mendatang, diberikan kondisi lampau apa saja, dan kondisi sekarang Xt=i, adalah independen terhadap kejadian masa lampau dan hanya bergantung pada keadaan sekarang dari proses tersebut. Peluang kondisional P( Xt+1=j | Xt=i ) dinamakan peluang transisi. Untuk steiap i,j dan n, P( Xt+1=j | Xt=i ) = P (X1=j | X0=i), untuk semua t=0,1,...., maka peluang transisi (satu langkah) dikatakan tetap (stationary) dan biasa ditulis sebagai Pij. Dengan peluang transisi stationary, maka peluang transisi tidak berubah sepanjang waktu. Ini juga menyatakan bahwa P( Xt+n=j | Xt=i ) = P (Xn=j | X0=i), untuk t=0,1..... Peluang kondisional ini biasa disebut sebagai pij(n) dan dikatakan sebagai peluang transisi n-langkah, dan meyatakan peluang kondisional bahwa peubah acak X, dimulai pada keadaan i, akan berada pada keadaan j setelah n langkah M
(unit waktu).
∑ pij j =0
(n)
= 1 , untuk semua i dan n = 0, 1, 2,.....
47
Tabel 3.3 Matriks Transisi Rantai Markov satu langkah. Sumber: Hillier dan Lieberman (2005, p735) State 0 1 (n) P = ... M
0 p00(n) .... ..... pM0(n)
1 ..... .....
M p0M(n) .... .... pMM(n)
Sebuah proses stokastik (Xt) ( t = 0, 1 ,....) dikatakan sebagai rantai Markov finite-state jika memiliki : •
Sejumlah keadaan (state) yang pasti (finite)
•
Ciri Markov
•
Peluang transisi tetap
•
Satu set peluang inisial P( X0 = i ) untuk semua i.
Untuk menghitung peluang transisi n-langkah, dapat digunakan metode Chapman-Kolgomorov sebagai berikut: pij(n) =
M
∑p k =0
ik
(v)
pkj ( n −v ) , untuk semua i, j, n dan 0 ≤ v ≤ n
Elemen matriks transisi n-langkah dapat dilakukan dengan mengalikan matriks peluang satu langkah awal dengan dirinya sendiri sebanyak n kali. P(n) = P . P ... P = Pn = PPn-1 = Pn-1P
3.5 Teori Antrian 3.5.1 Pengertian antrian
Antrian adalah sebuah keadaan di mana permintaan atau kedatangan melebihi kapasitas untuk melayani permintaan tersebut. Diperlukan penelitian
48
dan pengukuran untuk menghasilkan keputusan yang memadai mengenai kualitas sistem atau layanan, seperti waktu menunggu dan biaya. Teori antrian tidak dapat menghasilkan solusi yang selalu tepat, namun dapat digunakan untuk menjelaskan dan memperkirakan karakteristik dari suatu sistem antrian tersebut (mungkin dalam rata-rata waktu antrian). Dalam penelitian kualitas layanan jaringan, diperlukan pengetahuan mengenai antrian trafik (permintaan) seperti distribusi interval waktu yang diekspresikan sebagai peubah acak non negatif. Interval waktu yang diperhatikan dapat berupa durasi layanan, durasi kongesti, waktu menunggu (tunda), waktu tunda panggilan, interval kedatangan permintaan, dan sebagainya. Interval waktu, dapat diekspresikan sebagai peubah acak T dengan fungsi distribusi F(t) : ⎧t ⎪ dF (u ), 0 ≤ t ≤ ∞ F(t) = ⎨0∫− ⎪ ,t ≤ 0 ⎩0 Peluang bahwa durasi interval waktu lebih kecil atau sama dengan sebuah unit waktu t t menjadi: p(T ≤ t) = F(t) Komplemen dari fungsi probabilitas tersebut adalah Fc(t) = 1 – F(t). Diasumsikan bahwa F(t) diferensiabel, dan fungsi berikut ada dF(t) = f(t) . dt = p{t < T ≤ t + dt} , t ≥ 0
49
3.5.2 Struktur Dasar Model Antrian
Menurut Hillier dan Lieberman (2005, p766), proses dasar dari kebanyakan model antrian adalah sebagai berikut. Pengguna yang memiliki kebutuhan atau permintaan akan datang pada waktu tertentu, dan berasal dari komponen yang disebut sebagai sumber permintaan. Pada waktu tertentu, anggota dari antrian akan dipilih untuk dilayani berdasarkan aturan yang disebut sebagai disiplin layanan. Layanan akan dilakukan sesuai dengan mekanisme layanan, dan pengguna akan meninggalkan sistem. Terdapat beberapa asumsi mengenai proses di atas. Sistem Antrian Sumber Permintaan
Antrian
Mekani se Layanan
Gambar 3.10 Proses Dasar Antrian Sumber: Hillier dan Lieberman (2005, p766) A. Sumber Antrian Sumber permintaan dapat diukur dengan jumlah total pengguna atau permintaan dari waktu ke waktu (termasuk pengguna potensial). Sumber permintaan dapat diasumsikan sebagai terbatas (finite, limited) dan tidak terbatas (infinite, unlimited). Analisis untuk sistem tidak terbatas lebih mudah, sehingga asumsi ini banyak digunakan pada model antrian. Untuk permintaan terbatas, analisis akan lebih sulit karena jumlah pengguna pada
50
sistem antrian akan mempengaruhi jumlah pengguna potensial di luar sistem pada setiap waktu. Pola statistikal dari kedatangan permintaan sepanjang waktu juga perlu diasumsikan. Asumsi yang biasa digunakan adalah bahwa kedatangan terjadi menurut proses Poisson (jumlah kedatangan hingga waktu tertentu memiliki distribusi Poisson), yaitu secara acak dengan rata-rata laju λ tertentu. Ekuivalen dengan pernyataan di atas, interval waktu kedatangan akan memiliki distribusi eksponensial seperti akan dijelaskan pada bagian 3.5.4. Asumsi mengenai perilaku pengguna juga diperlukan, apakah pengguna akan keluar bila antrian terlalu panjang.
B. Antrian Sebuah antrian memiliki karakteristik berupa jumlah permintaan maksimum yang dapat diterima. Antrian dapat dikatakan terbatas atau tidak terbatas. Asumsi antrian tidak terbatas lebih sering digunakan, meski terkadang ada batasan tertentu, namun akan menyulitkan dalam analisis. Untuk batasan yang cukup kecil, analisis secara terbatas diperlukan.
C. Disiplin Antrian Disiplin antrian berkaitan dengan urutan dimana permintaan pada antrian dipilih untuk dilayani. Terdapat beberapa asumsi seperti FCFS (First Come First Served), LCFS (Last Come First Served), RSS (Random
51
Selection for Service), PR (Priority), GD (General Discipline). FCFS biasa digunakan dan diasumsikan pada model-model antrian.
3.5.3 Pengukuran Sistem Secara Umum
Berikut beberapa istilah dan simbol yang banyak digunakan pada teori antrian: •
A/B/X/Y/Z = struktur model antrian, dimana A adalah distribusi kedatangan, B pola layanan yaitu distribusi peluang waktu layanan, X jumlah kanal paralel, Y batasan kapasistas sistem dan Z adalah disiplin antrian yang digunakan.
•
State (keadaan) dari sistem = jumlah pengguna dalam sistem.
•
N(t) = jumlah pengguna di sistem pada waktu t (t≥0)
•
Nq(t) = jumlah pengguna menunggu
•
Ns(t) = jumlah pengguna yang sedang dilayani
•
pn(t) = P( N(t) = n) peluang terdapat n pengguna pada waktu t
•
s atau c = jumlah pelayan atau server (secara paralel)
•
λn = rata-rata laju kedatangan pegguna (per unit waktu) ketika n pengguna berada dalam sistem.
•
μn = rata-rata laju layanan sistem keseluruhan (jumlah pengguna yang selesai dilayani per unit waktu) ketika n pengguna berada pada sistem.
•
λ , μ Æ λn = λ jika untuk setiap n nilainya konstan (stabil). Ketika laju layanan per server sibuk (ketika n≥1) adalah konstan, maka
52
disebut sebagai μ (untuk kasus μn = cμ , ketika c server sibuk melayani).
1 1 , adalah nilai harapan interval waktu kedatangan ,
λ μ
dan interval waktu layanan. •
ρ =
λ = faktor utilisasi layanan, yaitu nilai harapan bagian cμ
waktu ketika server sibuk melayani
Ketika sebuah sistem antrian baru beroperasi, keadaan sistem (jumlah pengguna di sistem) akan dipengaruhi oleh keadaan awal dan waktu yang telah berjalan. Sistem dikatakan berada pada kondisi transisi. Ketika sejumlah waktu telah berjalan, keadaan sistem akan menjadi independen terhadap keadan awal dan waktu yang telah berjalan, kecuali pada keadaan tertentu ketika ρ ≥ 1. Pada saat ini sistem dikatakan berada pada kondisi stabil (steady-state). Teori antrian lebih memfokuskan apda kondisi stabil ini, dikarenakan kesulitan analisis pada kondisi transisi. Berikut notasi keadaan sistem stabil. •
N = Nq + Ns jumlah pengguna pada sistem antrian
•
pn = P( N=n ) adalah peluang terdapat tepat n pengguna pada sistem
•
L = E[N] =
∞
∑ np
n
n =0
•
= nilai harapan jumlah pengguna pada sistem.
∞
Lq = E[Nq] =
∑ (n − c) p
n = c +1
n
nilai harapan panjang antrian
53
•
T = waktu menunggu pada sistem (termasuk waktu layanan) untuk
setiap pengguna. •
W = E(T )
•
S = waktu layanan.
•
Tq = waktu menunggu pada antrian (di luar waktu layanan) untuk
setiap pengguna. T = Tq + S •
Wq = E(Tq)
•
Wq(n) = waktu yang harus ditunggu oleh pelanggan ke n yang tiba.
•
r=
•
pb = peluang semua server sibuk
λ = nilai harapan jumlah pengguna pada sistem μ
Salah satu persamaan yang paling penting dalam teori antrian adalah formula Little (John D. C. Little tahun 1960), yang menyatakan rata-rata ukuran sistem dengan rata-rata waktu menunggu pengguna (keduanya pada sistem keadaan stabil). L = λ W dan Lq = λ Wq,
Dengan E[T] = E [Tq] + E[S] atau W = Wq +
L – L q = λ ( W – Wq ) = λ (
1
μ
)=
1
μ
, dapat diturunkan bahwa
λ =r μ
L – Lq = E[N] – E[Nq] = E[N-Nq] = E[Ns] ∞
= ∑ npn n =0
= 1 – p0
∞
∑ (n − 1) p n =1
n
=
∞
∑p n =1
n
54
Dengan demikian, dapat dihitung peluang bahwa semua server sibuk (pada sistem dengan banyak server pada keadaan stabil), dinotasikan pb. Nilai harapan jumlah pengguna pada sistem stabil adalah r, dan untuk sistem dengan c server, menjadi
r . Dapat ditunjukkan bahwa pb = ρ c
.
r = ρ = 0 . (1- pb) + 1. pb c Untuk antrian server tunggal (G/G/1), peluang bahwa sistem menganggur (N=0) merupakan peluang sebuah server menganggur. p0 = 1- pb dan p0 = 1 - ρ = 1 – r = 1 -
Nilai r =
1
μ
1
μ
adalah nilai yang biasa disebut sebagai Offered Load.
Untuk menghitung kualitas atau efektivitas dari sebuah sistem, terlebih dahulu harus dihitung jumlah pengguna pada waktu t tertentu, n(t), dan waktu yang harus ditunggu oleh pengguna ke n yang tiba, Wq(n). n(t) = {jumlah kedatangan pada interval (0,t] } – {jumlah yang telah dilayani dalam interval (0,t]} Terdapat tiga waktu tunggu yang harus diperhatikan, yaitu waktu menunggu layanan Wq(n), waktu yang dihabiskan pelanggan ke-n pada sistem Wn), dan waktu virtual yang mana sebuah kedatangan fiksi pada waktu t harus menunggu, V(t).
55
Wq
( n +1)
⎧⎪Wq ( n ) + S ( n ) + T ( n ) (Wq ( n ) + S ( n ) − T ( n ) > 0), =⎨ (Wq ( n ) + S ( n ) − T ( n ) ≤ 0) ⎪⎩0
dimana waktu di antrian hingga layanan dimulai adalah waktu menunggu di antara dua pengguna berurutan, Wq(n) dan Wq(n+1). S(n) adalah waktu layanan untuk pelanggan ke-n, dan T(n) adalah waktu kedatangan antara pelanggan ken dan pelanggan ke-n+1.
3.5.4 Proses Poisson dan Distribusi Eskponensial Menurut Gross dan Harris (1998, p16), model antrian stokastik yang paling banyak dipakai adalah model yang mengasumsikan waktu interval kedatangan dan waktu layanan mengikuti distribusi eksponensial, atau secara ekuivalen, laju kedatangan dan laju layanan yang mengikuti distribusi Poisson. Menurut Larsen dan Marx (2001, p255), proses Poisson menyatakan jumlah kejadian atau kedatangan pada unit waktu tertentu. Sebuah interval waktu T dibagi menjadi n buah subinterval, dengan panjang masing-masing T . Dengan asumsi sebagai berikut. n 1. Dengan interval yang begitu kecil, peluang bahwa 2 atau lebih kejadian dapat diabaikan (sama dengan 0) 2. Suatu kejadian tidak bergantung pada kejadian lainnya. 3. Peluang kejadian pada sebuah subinterval adalah konstan sepanjang interval dari 0 hingga T.
56
Subinterval sejumlah n, secara analogi sama dengan n percobaan dengan model binomial, dengan hasil 0 atau 1 dan peluang yang konstan sepanjang waktu. Dengan X sebagai peubah acak jumlah kejadian atau kedatangan, dan
λ menyatakan laju kedatangan, maka E(X) = λ T = npn pn =
λT n k
⎛ n ⎞ ⎛ λT ⎞ ⎛ λ T ⎞ px ( k ) = P ( X = k ) = ⎜ ⎟ ⎜ ⎟ ⎜1 − ⎟ n ⎠ ⎝ k ⎠⎝ n ⎠ ⎝
n−k
e − n ( λT / n ) [ n(λT / n)]
k
=
k! ∞
xn e = 1+ x + ∑ n =2 n ! x
(−αΔt )n e−λT (λT )k = n! k! n=2 ∞
P(T ≤ t + Δt | T > t ) = 1−1 + ∑
Peluang di atas merupakan fungsi probabilitas Poisson dengan rata-rata parameter λ t .
y2
y1
X=1
X=1
y3
X=2
y4
y5 y6
X=1
X=0
y7
X=3
Gambar 3.11 Hubungan Peubah Acak Poisson (X) dan Eksponensial (Y) Sumber: Larsen dan Marx (2001, p261)
57
Gambar 3.11 menunjukkan hubungan antara peubah acak X yaitu laju kedatangan pengguna pada unit waktu tertentu (distribusi Poisson), dan peubah acak Y yaitu waktu interval kedatangan (distribusi eksponensial). Tampak pula bahwa pdf (fungsi probabilitas) Y bergantung pada pdf X. Andai pada waktu a terjadi sebuah kejadian Poisson dengan laju λ per unit waktu, dan terdapat interval setelah a yaitu a + y. Peluang bahwa tidak terjadi kedatangan pada interval (a, a+y) adalah
e − λ y (λ y ) 0 = e − λ y . Pada interval (a, 0!
a+y), tidak akan ada suatu kedatangan atau kejadian bila dan hanya bila nilai peubah acak Y > y. P (Y > y ) = e− λ y P (Y ≤ y ) = 1 − P (Y > y ) = 1 − e − λ y dengan fY (y) adalah pdf dari Y (belum diketahui) y
P (Y ≤ y ) = ∫ fY (t )dt 0
turunan dari kedua persamaan P (Y ≤ y ) adalah d dy
∫
y
0
f Y (t ) dt =
d (1 − e − λ y ) , dan dy
f Y ( y ) = λ e − λ y , y > 0 (fungsi peluang eksponensial).
Menurut Hillier dan Lieberman (2005, p775), distribusi eksponensial adalah distribusi yang penting dalam teori antrian, dimana distribusi ini dinilai cukup realistis untuk menggambarkan sistem nyata, dan tetap sederhana untuk
58
dianalisis secara matematis. Distribusi ini banyak digunakan untuk menggambarkan interval waktu kedatangan dan juga waktu layanan. Jika T adalah peubah acak yang menggambarkan nilai di atas, maka lima karakteristik berikut akan menjelaskan implikasi dari penggunaan distribusi eksponensial pada teori antrian. 1.
fT (t )
adalah fungsi yang selalu menurun (t ≥0), maka
P (0 ≤ T ≤ Δt ) >P (t ≤ T ≤ t + Δt ) untuk setiap nilai Δt dan t. Jika T menyatakan waktu layanan, T dapat menggambarkan sistem dengan waktu layanan yang mendekati waktu harapan. Jika T menggambarkan waktu interval kedatangan, karakteristik ini menggambarkan bahwa calon pendatang cenderung menunda kedatangan bila melihat bahwa terdapat banyak pendatang di depannya. 2. Tidak mengingat masa lampau (memoryless). P (T > t + Δt | T > Δt ) =P(T > t ) untuk setiap t dan Δt Hal ini meyatakan bahwa fungsi peluang waktu yang tersisa hingga kejadian berikut (kedatangan atau selesai) selalu sama, tidak tergantung pada jumlah waktu yang telah lewat. Untuk interval waktu
kedatangan,
ini
menyatakan
bahwa
waktu
hingga
kedatangan berikutnya tidak terpengaruh pada kedatangan terakhir. Untuk waktu layanan yang berbeda-beda antara pengguna, karakteristik ini cukup dapat digunakan.
59
3. Nilai
minimum
dari
beberapa
peubah
acak
eksponensial
independen memiliki distribusi eksponensial. Jika T1, T2,…, Tn adalah peubah acak independen, dan U adalah peubah acak yang mengambil nilai minimum dari peubah Ti tersebut, maka U akan memiliki distribusi eksponensial juga. Untuk waktu kedatangan, ciri ini dapat berguna untuk digunakan untuk mendapatkan gambaran sistem yang tetap eksponensial, tidak tergantung pada perbedaan dan jumlah pendatang. Untuk waktu layanan dengan n buah server, dengan Ti waktu layanan yang tersisa untuk server i (eksponensial dengan α i = μ ), dapat digunakan U yang juga terdistribusi secara eksponensial dengan
α i = nμ . Dengan demikian, sistem dapat dianggap sebagai sistem dengan server tunggal dengan parameter nμ . 4. Hubungan dengan distribusi Poisson Dengan distribusi Poisson yang menyatakan jumlah kedatangan dengan parameter λ t, didapat nilai harapan kedatangan per unit waktu sebesar λ . Hal ini berguna untuk menyatakan jumlah layanan yang diselesaikan ketika waktu layanan memiliki distribusi eksponensial dengan λ = μ , dan λ = nμ untuk sistem n-server. Kedatangan pengguna juga dapat dikatakan acak, mengikuti proses Poisson. 5. Untuk setiap nilai t, P(T ≤ t + Δt | T > t ) ≈ Δt untuk Δt kecil.
60
Ciri 2 meyatakan P (T ≤ t + Δt | T > t ) =P(T ≤ t ) = 1 − e −αΔt untuk setiap t dan Δt . Karena ∞
ex = 1 + x + ∑ n=2
xn n!
maka (−αΔt ) n n! n=2 ∞
P (T ≤ t + Δt | T > t ) = 1 − 1 + ∑
≈ Δt untuk Δt kecil
Hal ini dapat digunakan untuk mendekati peluang insiden (kedatangan atau waktu layanan) pada rentang Δt kecil.
3.5.5 Model Antrian Birth-and-Death Markov
Menurut Hillier dan Lieberman (2005, p780), kebanyakan model antrian mengasumsikan proses birth-and-death. Proses ini menjelaskan peluang bagaimana N(t), jumlah pengguna pada sistem pada waktu t, berubah ketika t bertambah. Secara umum kedatangan dan kepergian terjadi secara acak, dimana lajunya bergantung hanya pada keadaan sistem sekarang. Proses ini mengasumsikan sebagai berikut. 1. Diberikan N(t) = n, fungsi peluang (pada saat ini) waktu yang tersisa hingga kedatangan berikut adalah eksponensial dengan parameter λn (n = 0, 1, 2 ,…).
61
2. Diberikan N(t) = n, fungsi peluang (pada saat ini) waktu yang tersisa hingga kepergian berikut adalah eksponensial dengan parameter μn (n = 1, 2 ,…). 3. Hanya terdapat satu kedatangan atau kepergian pada suatu waktu.
λn −1
λn
n-1
n
μn
n+1
μ n +1
Gambar 3.12 Diagram Laju Proses Birth-and-Death Sumber: Gross dan Harris (1998, p54) Proses ini memiliki laju kedatangan dan kepegian yang sama, di mana pada suatu state n (n = 0, 1, 2,…) pada sistem, laju kedatangan ke state ini sama dengan laju keluar dari state ini. Tabel 3.4 Persamaan Keseimbangan Proses Birth-and-Death Sumber : Hillier dan Lieberman (1980, p783) Keadaan (state) 0
Laju Kedatangan=Laju Kepergian μ1 P1 = λ0 P0
1
λ0 P0 + μ2 P2 = (λ1 + μ1 ) P1 λ1 P1 + μ3 P3 = (λ2 + μ2 ) P2
2 … n-1 n ….
... λn −2 Pn − 2 + μn Pn = (λn −1 + μn−1 ) Pn −1
λn −1 Pn −1 + μn +1 Pn +1 = (λn + μn ) Pn
Dari tabel di atas, di peroleh: Cn =
λn −1λn − 2 ...λ0 , untuk n = 1, 2, ... μn μn −1...μ1
…
62
Peluang kondisi steady-state adalah Pn = Cn P0 , untuk n = 1, 2, … ∞ ⎡ ⎤ P = 1 , maka 1 + ∑ n ⎢ ∑ Cn ⎥ P0 = 1 , sehingga n =0 ⎣ n =1 ⎦ ∞
Dengan syarat
P0 =
1 ∞
1 + ∑ Cn
.
n =1
∞
Dengan informasi bahwa L = ∑ nPn , dan juga bahwa jumlah server c juga n =0
adalah jumlah pengguna yang dapat dilayani (dan keluar dari antrian), maka ∞
Lq = ∑ (n = s ) Pn . Telah disebutkan bahwa W = n =c
L
λ
, Wq =
Lq
λ
, dengan
λ adalah rata-rata laju kedatangan pada keadaan lanjut (long-run). Dengan λn adalah rata-rata laju kedatangan pada sistem dengan state n (n = 0, 1, 2, ...), dan Pn adalah proporsi waktu bahwa sistem berada pada keadaan n, maka
λ =
∞
∑ λ n Pn . n=0
3.5.6 Model Dasar (Laju Kedatangan dan Laju Layanan Konstan)
Model ini mengasumsikan laju kedatanagan dan kepergian yang tetap yaitu λn = λ (n = 0,1 2, ...) dan μn = μ (n = 1,2,...).
A. Sistem dengan Server Tunggal. Faktor Cn untuk sistem dengan server tunggal menjadi
63
n
⎛λ⎞ Cn = ⎜ ⎟ , untuk n = 1,2,..., ⎝μ⎠ maka dari itu Pn = ρ n P0 untuk n = 1,2,..., dimana P0 =
1 ∞
1+ ∑ ρ n n =1
⎛ ⎞ = ⎜∑ ρn ⎟ ⎝ n=0 ⎠ ∞
⎛ 1 ⎞ =⎜ ⎟ ⎝ 1− ρ ⎠ = 1− ρ,
−1
oleh karena itu
Pn = (1 − ρ ) ρ n untuk n =0,1,2,..., sehingga ∞
L = ∑ n(1 − ρ ) ρ n n =0
∞
d (ρ n ) d ρ n =0
= (1 − ρ ) ρ ∑ = (1 − ρ ) ρ
d ⎛ ∞ n⎞ ∑ρ d ρ ⎜⎝ n =0 ⎟⎠
= (1 − ρ ) ρ
d ⎛ 1 ⎞ ⎜ ⎟ d ρ ⎝ 1− ρ ⎠
= (1 − ρ ) ρ
d ⎛ ∞ n⎞ ∑ρ d ρ ⎜⎝ n =0 ⎟⎠
=
ρ 1− ρ
=
λ μ −λ
secara demikian pula,
,
64
∞
Lq = ∑ (n − 1) Pn n =1
= L − 1(1 − P0 ) =
λ2 . μ (μ − λ )
Dengan asumsi λ < μ , dimungkinkan untuk menurukan peluang distribusi waktu menunggu pada sistem (termasuk pelayanan) T untuk kedatangan acak dan disiplin FCFS. Jika sebuah kedatangan pengguna menemukan n pengguna sudah berada di sistem, maka pengguna tersebut harus menunggu (n+1) waktu layanan eksponensial. S n +1 = T1 + T2 + ... + Tn +1 , untuk n = 0,1,2,..., dengan S n +1 adalah waktu menunggu kondisional di mana n pengguna telah berada di sistem. S n +1 memiliki distribusi gamma (pada teori antrian biasa digunakan distribusi Erlang). Karena peluang kedatangan acak akan menemukan n pengguna pada sistem adalah Pn,maka ∞
P (T > t ) = ∑ Pn P ( S n +1 > t ) , dan akan didapatkan bahwa n=0
P (T > t ) = e− μ (1− ρ ) t untuk t ≥ 0. T sendiri memiliki distribusi eksponensial dengan parameter μ (1 − ρ ). W = E[T ] =
1 1 = . μ (1 − ρ ) μ − λ
Terkadang waktu untuk menunggu baru dihitung setelah sebuah layanan dimulai. Waktu menunggu ini (di luar waktu layanan) adalah
65
Tq. Jika sebuah kedatangan menemukan tiada pengguna di sistem, maka layanan akan langsung dimulai P (Tq = 0) = P0 = 1 − ρ . Jika ditemukan n > 0 pada sistem, maka harus ditunggu n waktu eksponensial ∞
P (Tq < t ) = ∑ Pn P( S n > t ) n =1
∞
= ∑ (1 − ρ ) ρ n P ( S n > t ) n =1
∞
= ρ ∑ Pn P ( S n +1 > t ) n=0
= ρ P (T > T ) = ρ e − μ (1− ρ )t , untuk t ≥ 0. Dengan menurunkan rata-rata distribusi ini, didapatkan Wq = E (Tq ) =
λ μ (μ − λ )
B. Sistem dengan Server Jamak (c > 1) n λ μ) ( Cn =
n!
Cn =
untuk n =1,2,...,s, dan
c (λ μ ) ⎛ λ
c!
⎞ ⎜ ⎟ ⎝ cμ ⎠
n −c
=
c ( λ μ ) , untuk n =c,c+1,...
c !c n − c
Jika λ < s μ , maka ⎡ c −1 ( λ μ )n ( λ μ ) c ∞ ⎛ λ ⎞n −c ⎤ + P0 = 1 ⎢ ∑ ⎥ ∑ c ! n =c ⎜⎝ cμ ⎟⎠ ⎦⎥ ⎣⎢ n =0 n !
66
⎡ c −1 ( λ μ )n ( λ μ ) c ⎤ 1 = 1 ⎢∑ + ⎥, c ! 1 − (λ cμ ) ⎦⎥ ⎣⎢ n =0 n !
dan ⎧ ( λ μ )n P0 , jika 0 ≤ n ≤ c ⎪ ⎪ n! Pn = ⎨ n ⎪(λ μ ) ⎪⎩ c !c n −c P0 , jika n ≥ c.
Dengan notasi ρ = λ μ c , maka ∞
Lq = ∑ (n − s ) Pn = n=s
Tq =
Lq
λ
; W = Wq +
P0 (λ μ )c ρ ; c !(1 − ρ ) 2 1
μ
;
⎛ 1⎞ λ L = λ ⎜ Wq + ⎟ = Lq + . μ⎠ μ ⎝
P (T > t ) = e
− μt
⎡ P0 ( λ μ )c ⎛ 1 − e− μt ( s −1−λ μ ) ⎞ ⎤ ⎢1 + ⎜ ⎟ ⎥ , dan c !(1 − ρ ) ⎝ s − 1 − (λ μ ) ⎠ ⎥⎦ ⎢⎣
P (Tq > t ) = ⎡⎣1 − P(Tq = 0) ⎤⎦ e− cμ (1− ρ )t .
3.5.7 Rumus Erlang B (Loss Formula, M/M/c/c)
Menurut Gross dan Harris (1998, p80), untuk sistem antrian dengan banyak server, dan tidak terdapat garis antrian (batas sistem K = c, di mana pengguna yang tidak mendapat layanan Erlang B yang dapat dijelaskan berikut ini.
ditolak), dapat digunakan rumus
67
Peluang bahwa terdapat transisi dari state n ke n+1 adalah Pn (λ n)dt , dan peluang transisi dari arah sebaliknya adalah Pn +1 (n + 1)dt maka Pn +1 =
(λ μ ) Pn . n +1
Secara umum, Pn =
(λ μ ) n P0 , untuk (0 ≤ n ≤ c). n!
Dengan P1 + P2 + ... + Pn = 1 , maka ⎛ c (λ μ ) ⎞ P0 = 1 ⎜ ∑ ⎟, ⎝ i =0 i ! ⎠ (λ μ ) n E1,c = Pn = c n ! untuk (0 ≤ n ≤ c) (λ μ ) ∑ i! i =0
3.5.8 Rumus Erlang C (Penundaan)
Untuk keadaan kongesti, fasilitas untuk menunggu diperlukan, dan peluang penundaan inilah yang dijadikan penilaian untuk kinerja sistem. Ketika pengguna datang dan menemukan semua server sibuk, maka pengguna akan menunggu (ditunda) hingga terjadi kepergian dan dapat dilayani. Untuk n ≤ c, peluang bahwa sebuah pengguna pergi pada interval dt adalah ndt. Jika n > c, maka n-c pengguna menunggu, dengan peluang cdt. Peluang kedatangan adalah (λ μ ) dt. Persamaannya, menurut Bear (1980, p113) menjadi (λ μ ) + n = (λ μ ) Pn −1 + (n + 1) Pn +1 , untuk (0 ≤ n ≤ c, P−1 = 0 )
68
(λ μ ) + n = (λ μ ) Pn −1 + cPn +1 Pn =
(λ μ ) P
0
n!
⎛ (λ μ ) ⎞ (λ μ ) ⎛ (λ μ ) ⎞ Pn +1 = ⎜ P0 , Pn + 2 = ⎜ ⎟ ⎟ ⎝ n ⎠ ⎝ n ⎠ n! ⎡ c −1 ( λ μ )i ( λ μ )c P0 = 1 ⎢ ∑ + c! ⎢⎣ i =0 i !
⎛ (λ μ ) ⎞ ∑⎜ n ⎟ i =0 ⎝ ⎠ ∞
i
2
(λ μ ) P n!
0
⎤ ⎥ ⎥⎦
⎡ c −1 ( λ μ )i ( λ μ )c ⎛ ⎞⎤ c = + P0 1 ⎢ ∑ ⎜⎜ ⎟⎥ c ! ⎝ c − ( λ μ ) ⎟⎠ ⎥ ⎢⎣ i =0 i ! ⎦ Peluang kongesti (terjadinya penundaan) adalah ∞
E2,c ( λ μ ) = ∑ Pn n=c
⎧⎪ ( λ μ )n ⎛ ⎞ ⎫⎪ c =⎨ ⎜ ⎟⎬ ⎪⎩ n ! ⎝ c − ( λ μ ) ⎠ ⎪⎭
⎡ c −1 ( λ μ )i ( λ μ )c ⎛ ⎞⎤ c + ⎢∑ ⎜⎜ ⎟⎥ c ! ⎝ c − ( λ μ ) ⎟⎠ ⎥ ⎢⎣ i =0 i ! ⎦
Hubungan antara Erlang B dan Erlang C adalah E2,c ( λ μ ) =
cE1,c ( λ μ )
c − ( λ μ ) + λ μ E1,c ( λ μ )
3.5.9 Distribusi Waktu Menunggu
Jika semua server sibuk, peluang bahwa tidak ada kepergian dalam waktu
( )
t, adalah e−t
c
= e−tc . Jika sebuah pengguna datang ketika c server sibuk dan
j pengguna lainnya meunggu, pengguna tersebut akan menunggu lebih besar dari t bila dan hanya bila lebih sedikit dari j pengguna pergi dalam waktu t.
69
Kepergian ini dapat terjadi pada pengguna yang sedang mengantri ataupun sedang dilayani. Peluangnya adalah j
(ct )i − ct ∑ i! e i =0 Total peluang bahwa penundaan melebihi t untuk setiap nilai j adalah ∞
j
(ct )i − ct e i =0 i !
F (t ) = ∑ Pc + j ∑ j =0
− c −( λ μ ) )t = E2,c ( λ μ ) e (
Peluang di atas adalah non kondisional, peluang kondisional, di mana sebuah panggilan tertunda adalah sebagai berikut.
(λ μ ) F (t ) F (t ) − c − ( λ μ ) )t = =e ( = e− c (1−a )t , dimana a = c F (0) E2,c ( λ μ )
3.5.10 Model Kendali Kongesti TCP
Model kendali kongesti menurut Jitendra et.al merupakan model stokastik yang merupakan fungsi dari peluang kehilangan paket data dan nilai layanan berupa RTT . Pemodelan dilakukan dalam lingkup ronde yang dimulai dengan pengiriman sejumlah cwnd data dan diakhiri dengan diterimanya ACK. Sebuah ACK mungkin dikirimkan untuk mengkonfirmasi sejumlah b paket yang diterima (nilai 2 biasa digunakan). Ronde baru dimulai dengan nilai cwnd yang baru ( cwnd ' ). Jika terdapat cwnd paket yang dikirimkan, maka akan
70
terdapat cwnd b ACK. Nilai cwnd akan bertambah secara linear setiap RTT (cwnd’ = cwnd + 1/b). Kendali kongesti dimodelkan berdasarkan operasi berupa kehilangan paket yang ditandai dengan TD (3 ACK duplikat), juga yang ditandai dengan TD dan TO (timeout), dan pembatasan cwnd karena batasan window penerima (lebih jarang). Kehilangan paket pada sebuah ronde tidak bergantung pada kehilangan paket pada ronde lainnya. Jika pada sebuah ronde terdapat kehilangan paket, paket lain dalam ronde tersebut juga diasumsikan hilang. A. Indikasi Kehilangan Merupakan Tiga ACK Duplikat Transaksi dimulai pada t = 0 , dan untuk setiap waktu t > 0 , maka N t menyatakan jumlah paket yang dikirimkan dalam interval [0, t ) , dan Bt = N t t menyatakan laju pengiriman paket (throughput) baik diterima atau tidak. B adalah laju paket dalam kondisi steady-state jangka panjang B = lim Bt = lim t →∞
t →∞
Nt . t
Nilai p adalah peluang bahwa sebuah paket hilang (dan berarti paket lain di ronde tersebut dinyatakan hilang). Periode TD (TDP) adalah periode antara 2 indikasi TD. Untuk TDP ke i, Yi menyatakan jumlah paket yang dikirimkan pada periode tersebut, Ai menyatakan durasi periode tersebut, dan CWNDi menyatakan CWND pada akhir periode. Dengan mengasumsikan bahwa {cwndi }i adalah proses Markov dengan tambahan {Yi }i , maka dapat dituliskan B =
E[Y ] . E[ A]
71
Sebuah TDP dimulai setelah terjadi indikasi TD, dan nilai CWND adalah CWNDi −1 2 Pada setiap ronde, CWND ditambah dengan 1 b , dan jumlah paket yang dikirim per ronde bertambah 1 setiap b ronde. Variabel
α i menyatakan paket pertama yang hilang pada TDPi , dan X i menyatakan ronde terjadinya. Setelah paket α i , terdapat CWNDi − 1 paket yang dikirimkan sebelum ronde berakhir. Jadi terdapat Yi = α i + CWNDi − 1 paket
dikirimkan
dalam
Xi +1
ronde.
E[Y ] = E[α ] + E[CWND] − 1 . Untuk menurunkan
Dapat
dituliskan
E[α ] , diasumsikan
{α i }i adlaah peubah acak yang tersebar secara identik. P[α = k ] = (1 − p ) k −1 p, k = 1, 2,... ∞
E[α ] = ∑ (1 − p ) k −1 pk = k =1
E[Y ] =
1 . p
1− p + E[CWND] p
Dengan rij menyatakan durasi round-trip untuk ronde ke j pada TDPi , dapat dituliskan
E[ A] = ( E[ X ] + 1) E[r ] , dengan RTT= E[r ] . Untuk
menurunkan E[ X ] , digunakai cwnd i sebagai fungsi jumlah ronde. Pada TDPi , CWND bertambah antara CWNDi −1 2 dan CWNDi . CWNDi =
Yi =
X i b −1
∑ k =0
CWNDi −1 X i + , i = 1, 2... b 2
⎛ CWNDi −1 ⎞ + k ⎟ b + β i , β i = jumlah paket ronde sebelumnya. ⎜ 2 ⎝ ⎠
72
=
X iWi − 1 X i ⎛ X i ⎞ + − 1⎟ + β i 2 2 ⎜⎝ b ⎠
=
Xi 2
⎛ Wi −1 ⎞ ⎜ 2 + Wi − 1⎟ + β i ⎝ ⎠
Dengan mengasumsikan bahwa { X i } dan {CWNDi } adalah peubah acak identik dan independen, maka E[W ] =
2 E[ X ] dan b
E[ X ] ⎛ E[CWND] 1− p ⎞ + E[CWND] = + E[CWND] − 1⎟ + E[ β ] . ⎜ p 2 ⎝ 2 ⎠
βi diasumsikan terdistribusi secara seragam dari 1 hingga Wi , maka E[ β ] = E[W ] 2 . Selanjutnya didapatkan 2
E[W ] =
E[W ] =
2 + b 8(1 − p ) ⎛ 2 + b ⎞ +⎜ ⎟ , dan dapat diperhatikan bahwa 3b 3bp ⎝ 3b ⎠
(
8 +o 1 3bp
)
8 untuk nilai p yang 3bp
p , yaitu E[W ] ≈
kecil. Dari persamaan sebelumnya didapatkan bahwa
E[ X ] =
2 + b 2b(1 − p) ⎛ 2 + b ⎞ +⎜ ⎟ 6 3p ⎝ 6 ⎠
2
2 ⎛ 2 + b 2b(1 − p ) ⎞ ⎛ 2+b⎞ ⎟ E[ A] = RTT ⎜ 1 +⎜ + ⎟ ⎜ 6 ⎟ 3p 6 ⎠ ⎝ ⎝ ⎠
Perhatikan bahwa E[ X ] =
(
2b +o 1 3p
p
)
73
1− p + E[CWND] p B( p) = , dan dapat diekspresikan sebagai E[ A] B( p) =
1 RTT
(
2b +o 1 3p
p
)
B Indikasi Kehilangan Merupakan Tiga ACK Duplikat dan Timeout Pada model ini, ditambahkan kasus ketika pengirim TCP mengalami timeout. Paket atau ACK hilang, dan kurang dari tiga ACK duplikat diterima. Pengirim menunggu webanyak waktu T0 dan mengirim ulang paket yang belum di-ACK. Setelah timeout, cwnd dikurangi satu, dan sebuah paket dikirim ulang pada ronde pertama setelah timeout. Dengan ZiTO menyatakan durasi antara beberapa timeout, dan ZiTD menyatakan interval waktu antara dua timeout yang berurutan, dinyatakan Si = ZiTO + ZiTD . Bila Mi menyatakan jumlah paket yang dikirimkan dalam Si, maka {( Si , M i )}i adalah peubah acak yang tersebar secara identik, dan didapatkan B =
E[ M ] . Definisi TD diperluas menjadi periode setelah atau E[ S ]
berakhir pada indikasi terjadinya TO. ni adalah jumlah TDP pada interval ZiTD . Untuk TDP ke j pada interval ZiTD , didefinisikan Yij sebagai jumlah paket yang dikirimkan pada periode tersebut. Aij adalah durasi periode, X ij adalah jumlah ronde dalam periode tersebut, cwndij adalah ukuran
74
window pada akhir periode. Ri menyatakan jumlah paket yang dikirimkan pada ZiTO . Mi =
ni
∑Y j =1
ij
ni
+ Ri , S i = ∑ Aij + Zi TO , maka j =1
⎡ ni ⎤ ⎡ ni ⎤ E [ M ] = E ⎢ ∑ Yij ⎥ + E [ R ], E [ S ] = E ⎢ ∑ Aij ⎥ + E [ Z TO ] ⎣ j =1 ⎦ ⎣ j =1 ⎦ Jika {ni }i diasumsikan peubah acak yang tersebar secara identik, terbebas dari {Yij } dan { Aij } , maka ⎡⎛ ni ⎞ ⎤ ⎡⎛ ni ⎞⎤ E ⎢⎜ ∑ Yij ⎟ ⎥ = E[n]E[Y ] , E ⎢⎜ ∑ Aij ⎟ ⎥ = E[n]E[ A] ⎢⎣⎝ j =1 ⎠i ⎥⎦ ⎢⎣⎝ j =1 ⎠i ⎥⎦ Pada ZiTD , terdapat ni TDP, dimana terdapat sejumlah ni -1 yang berakhir dengan TD, dan 1 yang berakhir dengan TO. Dengan demikian, terdapat 1 TO dari ni indikasi. Bila Q adalah peluang sebuah indikasi yang mengakhiri TDP adalah TO, maka Q = 1 E[n] , dan juga B=
E[Y ] + Q * E[ R ] . E[ A] + Q * E[ Z TO ]
Bila cwnd adalah ukuran window kongesti, pada ronde dimana terdapat indikasi kehilangan (penultimate) akan dikirimkan
f1... f cwnd . Paket
f1... f k akan di-ACK, dan paket f k +1 adalah paket pertama yang hilang. Paket berikutnya pada ronde tersebut juga akan hilang. Karena terdapat sejumlah cwnd paket yang di-ACK, maka akan terdapat s1...sk paket yang dikirimkan pada ronde yang disebut ronde terakhir. Pada ronde ini terdapat kemungkinan kehilangan, sebut saja pada paket sm +1 . Untuk m paket yang
75
terkirim akan didapati m ACK yang mengkonfirmasi paket f k (ACK uplikat). Jika A(cwnd , k ) menyatakan peluang bahwa paket ke k dari cwnd paket, maka A(cwnd , k ) =
(1 − p ) k p , dan juga 1 − (1 − p )cwnd
C (n, m) adalah peluang bahwa m paket akan di-ACK dari n paket yang dikirim adalah
⎧⎪(1 − p) m p, m ≤ n − 1 C (n, m) = ⎨ , n ⎪⎩(1 − p) , m = n maka Qˆ (cwnd ) , peluang kehilangan pada window sebesar cwnd adalah sebuah TO adalah ⎧⎪1, cwnd ≤ 3 Qˆ (cwnd ) = ⎨ 2 cwnd 2 ⎪⎩∑ k =0 A(cwnd , k ) + ∑ k =3 A(cwnd , k )∑ m =0 C (k , m) Selanjutnya didapatkan
)(
(
(
⎛ 1 − (1 − p )3 1 + (1 − p )3 1 − (1 − p )cwnd −3 ⎜ Qˆ (cwnd ) = min(1, ⎜ cwnd 1 − (1 − p ) ⎜ ⎝ Dengan aturan L’Hopital, lim Qˆ (cwnd ) = p →0
)) ⎞⎟ ⎟ ⎟ ⎠
3 cwnd
Secara numerik, pendekatan yang baik terhadap Qˆ adalah 3 ⎞ ⎛ Qˆ (cwnd ) ≈ min ⎜ 1, ⎟ , dan Q (peluang kehilangan adalah TO), ⎝ cwnd ⎠ Q=
∞
∑
cwnd =1
Qˆ (cwnd ) P[CWND = cwnd ] = E[Qˆ ]
76
Dilakukan pendekatan Q ≈ Qˆ ( E[CWND]) Untuk menurunkan E[ R] dan E[ Z TO ] , diperlukan pelaung distribusi jumlah timeout dalam sejumlah urutan TO. Sejumlah k TO muncul ketika terdapat k – 1 kehilangan berturu-turut yang diikuti dengan satu paket yang terkirim dengan sukses. Jumlah TO dalam seurutan TO memiliki distribusi geometri, maka P[ R = k ] = p k −1 (1 − p ) , dan ∞
E[ R] = ∑ kP[ R = k ] = k =1
1 1− p
E[ Z TO ] merupakan rata-rata durasi urutan timeout diluar transmisi ulang. Enam timeout pertama akan memiliki durasi 2i −1T0 , i = 1, 2,..., 6 dengan timeout berikutnya sebesar 64T0 . Durasi urutan timeoutnya adalah ⎧⎪(2k −1 )T0 , k ≤ 6 Lk = ⎨ ⎪⎩(63 + 64(k − 6)T0 , k ≥ 7 ∞
E[ Z TO ] = ∑ Lk P[ R = k ] k =1
= T0
1 + p + 2 p 2 + 4 p 3 + 8 p 4 + 16 p 5 + 32 p 6 1− p
Dari penurunan di atas, didapatkan 1− p 1 + E[CWND] + Qˆ ( E[CWND]) p 1− p B( p) = , dengan f ( p) ˆ RTT ( E[ X ] + 1) + Q ( E[CWND]) T0 1− p
77
f ( p ) = 1 + p + 2 p 2 + 4 p 3 + 8 p 4 + 16 p 5 + 32 p 6 Pendekatan yang dapat diambil adalah
1
B( p) ≈ RTT
⎛ 2bp 3bp ⎞ 2 + T0 min ⎜ 1,3 ⎟ p 1 + 32 p 3 8 ⎝ ⎠
(
)