Teori Antrian Antrian M/M/1 Rijal Fadilah
Dasar Antrian • Pelanggan (customer) tiba untuk pelayanan, dan jika semua pelayan (server) sibuk, pelanggan diantrikan dan dilayani kemudian • Parameter: Kecepatan kedatangan (arrival rate), kecepatan pelayanan (service rate), jumlah pelayan (server) • Pengukuran: waktu tunggu, waktu pelayanan, waktu di dalam sistem, utilisasi server, jumlah pelanggan dalam antrian, jumlah pelanggan dlm sistem, ...
Dasar Antrian • Single queue system biasa digunakan merepresentasikan shared resource networks
utk
• Network of queues biasa digunakan merepresentasikan tipe jaringan yg lain
utk
– Process networks – Switching networks
Resource Sharing Networks
• • • • •
Time-shared computers (Programs: CPU/DISK/IO) Statistical Multiplexer/Concentrator Packet-based (Packets: links) Channel-based (Calls: channels) Multiple-access & random access networks (Packets: shared medium)
Resource Sharing Networks • Ukuran performansi – Waktu tunggu – Probabilitas blocking
• Pertanyaan – Bagaimana relasi antara jumlah user, pola penggunaan, jumlah resource dan performansi? – Apakah resource dimanfaatkan secara adil (fair)?
Process Networks
• Multi-stage switch • Distributed simulation system • Manufacturing process
Process Networks • Ukuran performansi – Waktu penyelesaian (delay) – Throughput (penyelesaian persatuan waktu)
• Pertanyaan – Bagaimana performansi dipengaruhi oleh pola penggunaan berbeda? – Proses mana yg menjadi “bottlenecks” yg membatasi performansi? – Apakaha input berbeda diperlakukan secara adil dalam hal performansi?
Switching Networks
• • • •
Jaringan telepon (telepon: circuit switches) Jaringan signaling telepon (switches; STP) Jaringan Paket X.25 (komputer: packet switches) Internet (komputer: router)
Switching Networks • Ukuran performansi – – – – –
Delay (end point to end point) Throughput Utilization Blocking probability Loss
• Pertanyaan – Topologi jaringan yg terbaik? – Bagaimana me-routekan? – Bagaimana menjamin kualitas pelayanan (QOS)?
Apa yang Bisa Dipelajari?
Faktor • Jumlah pelanggan • Pola penggunaan (workload) • Karakteristik service • Jumlah resource
Performansi • Waktu tunggu • Blocking • Loss
Elemen-Elemen Antrian
Model Dasar • Pelanggan dari suatu populasi tiba pada sistem dg waktu kedatangan random • adalah rate kedatangan pelanggan • Sistem antrian mempunyai c server identik • Pelanggan ke-j meminta pelayanan dan akan memerlukan sj unit waktu pelayanan dari satu server • Jika semua server sibuk, pelanggan yg datang bergabung dlm antrian sampai tersedia server
Model Dasar • Disiplin pelayanan menspesifikasikan urutan dimana pelanggan dipilih dari antrian – Contoh: FIFO, LIFO, priority, random, …
• Waktu tunggu tQj adalah waktu diperlukan pelanggan ke-j antara memasuki sistem dan memasuki pelayanan • Total delay dari sistem j = tQj + sj • n = jumlah pelanggan dlm sistem – suatu random variable
• nq = jumlah pelanggan dlm antrian – suatu random variable
Notasi Antrian a/b/m/K • a = tipe proses kedatangan – M (Markov) menunjukan kedatangan Poisson, shg waktu antar kedatangan iid exponential random variables
• b = service time distribution – M (Markov) menunjukan distribusi eksponensial – D (Determistic) menunjukan service time konstan – G (General) menunjukan iid service times mengikuti suatu general distribution
Notasi Antrian a/b/m/K • m = jumlah server • K = jumlah maksimum pelanggan yg dibolehkan dlm sistem
Background: Proses Poisson
• Kedatangan terjadi dg rate • Probabilitas [secara eksak satu pelanggan tiba dlm interval [t, t+ t]] = t • Probabilitas [tidak ada kedatangan dlm interval [t, t+ t]] = 1 t • Dg membuat t mendekati nol, kita mendapatkan proses Poisson
Distribusi Kedatangan • Pn(t) = P[Jumlah kedatangan sampai saat t = n]
Jumlah Kedatangan • Mis. E[n] adalah mean dari jumlah kedatangan dlm perioda interval t – Mean
E[n]
nPn (t )
t
n 0
– Variance 2 n
E [ n 2 ] E[ n ] 2
t
Kelayakan Apakah proses Poisson cukup layak digunakan? • Secara umum proses Poisson adalah model yg baik jika terdapat sejumlah user yg besar (sumber paket) sehingga – Users serupa – Users independen
Kelayakan • Misalkan kita menggabungkan n proses Poisson • Tiap proses mempunyai rate /n, shg rate gabungan (aggregate) = • Waktu antar kedatangan , utk tiap proses mempunyai distribusi F(s) = P{ s} dan independen • Proses penggabungan mendekati proses Poisson dg rate dg n
Waktu Antar Kedatangan • Mis. T = waktu antar kedatangan dlm proses Poisson – T adalah random variables – Utk proses Poisson, waktu antar kedatangan adalah exponentially distributed random variables – Fungsi distribusi dan densitas utk distribusi eksponensial
Memoryless Property • Distribusi eksponensial adalah memoryless – Apa yg terjadi setelah waktu t adalah independen thd apa yg terjadi sebelum t – Pengetahuan masa lalu tidak membantu memprediksi masa depan
• Untuk waktu service
– Waktu tambahan yg diperlukan utk menyelesaikan service pelanggan yg sedang berlangsung independen thd kapan service dimulai
Memoryless Property • Utk waktu antar kedatangan
– Waktu utk kedatangan berikutnya independen thd kapan kedatangan terakhir terjadi
• Distribusi eksponensial adalah satu-satunya distribusi kontinyu mempunyai sifat memoryless • Distribusi diskrit yg mempunyai sifat memoryless adalah distribusi geometric
Markov Property • Memoryless property memungkinkan menggunakan Markov Chain untuk menganalisa antrian M/M/1 • Diberikan independensi dari waktu antara kedatangan dan waktu service, jumlah pelanggan dlm sistem kedepan hanya tergantung pd N(t), jumlah pelanggan dlm sistem pada saat t
Markov Property • Proses random adalah proses Markov jika masa depan proses diberikan saat ini independen thd masa lalu
• Markov chain adalah proses Markov dg discrete state space
Markov Property • Jika kita tahu sistem ada dlm state a pd saat tk, probabilitas transisi ke state lainnya pd saat tk+1 dpt ditentukan – tidak perlu tambahan informasi masa lalu
Little’s Law • Jumlah pelanggan rata-rata dlm sistem (antrian) sama dgn rate kedatangan dikalikan waktu rata-rata dlm sistem (antrian)
Little’s Law • Misalkan – Rate kedatangan ( ) – Jumlah dlm sistem, n(t), jumlah dlm antrian nQ(t), jumlah dlm pelayanan nS(t) – Waktu dlm sistem , waktu dlm antrian Q, waktu dlm pelayanan s
• Relasi parameter-parameter dg Little’s Law – Jumlah dlm sistem : E[n] = .E[ ] – Jumlah dlm antrian : E[nQ] = .E[ Q] – Jumlah dlm service : = E[nS] = .E[s]
Utilisasi • Utilisasi dari sistem single server
• Utilisasi dari sistem c-server
In-Class Exercise • Pelanggan memasuki toko dg rate rata-rata 32 pelanggan per jam. Rata-rata pelanggan menghabiskan waktu 12 menit di dlm toko. Berapa banyak pelanggan yg kita harapkan kita jumpai di dlm toko dlm sembarang waktu?
Saluran Transmisi
Saluran Transmisi • Parameter – adalah rate kedatangan – NQ adalah jumlah rata-rata paket menunggu dlm antrain (belum ditransmisikan) – W adalah rata-rata waktu tunggu dlm antrian (tidak termasuk waktu transmisi)
• Little’s law memberikan NQ = .W • Jika X adalah waktu transmisi rata-rata, Teorema Little memberikan utilisasi (rata-rata jumlah transmisi paket) = .X
Saluran Transmisi • Perhatikan kasus dimana
• 1/ adalah rata-rata waktu antar kedatangan • jika > 1, maka ekspektasi waktu service lebih besar drpd ekspetasi waktu antar kedatangan, yaitu pelanggan datang lebih cepat drpd yg dp dilayani – Antrian akan overflow atau meningkat sangat panjang – > 1, menghasilkan situasi yg tidak stabil
Network of Transmission Lines
Network of Transmission Lines • Paket tiba pada n node berbeda utk transmisi dg rate 1, 2, … , m • N adalah jumlah paket total dlm jaringan • Little’s law memberikan delay rata-rata per paket
Network of Transmission Lines • Perlu dicatat bahwa rata-rata delay per-paket adalah independen dari distribusi panjang paket dan metoda utk me-routing-kan paket • Juga utk node i, Ni = iTi
Antrian M/M/1 • Antrian tunggal (single queue) • Server tunggal (single server) • Pelanggan (paket) tiba sesuai dg proses Poisson dg rate per-detik • Distribusi waktu pelayanan adalah eksponensial dg mean 1/ detik • Buffer tak terbatas
Markov Chain • Karena memoryless property dari r.v. eksponensial, jumlah pelanggan dlm sistem saat t, N(t), dp diekspresikan sbg continuous-time Markov chain
Probabilty Flux • Probabilitas flux transisi adalah perkalian probabilitas state dimana transisi dimulai dan rate transisi – Indikasi rata-rata brp kali per-detik event sesuai dg korespondesni transisi terjadi
• Dlm kondisi steady-state, rata-rata brp kali/det suatu state dimasuki adalah sama dg rata-rata brp kali/det suatu state ditinggalkan – Menuju pd global balance equations
Global Balance • Total rate transisi keluar dari state n sama dg total rate transisi ke state n – Dynamic equilibrium
Global Balance Equations • Global balance equation utk antrian M/M/1
• Jika ada N state, ada N persamaan, termasuk relasi berikut
Local Balance • Utk Markov Chain, rate transisi dari state A ke state B sama dg rate transisi dari B ke A • Sbg contoh, rate transisi dari n-1 ke n sama dg rate transisi dari n ke n-1
Local Balance Equations • Persamaan local balance utk anrian M/M/1
Menyelesaikan Local Balance Equations • Pers local balance menghasilkan n-1 rekursi berikut
Menyelesaikan Local Balance Equations • Normalisasi
probability’
dicapai
melalui
‘conservation
of
Menyelesaikan Local Balance Equations • Dg = / dan menggunakan identitas berikut
• Maka
Hasil • Jika = / < 1 , kita dp
• Utilisasi
• Mean dari jumlah pelanggan, n
Hasil • Dg Little’s law, dp dicari waktu rata-rata dlm sistem
• Dan waktu rata-rata dlm antrian
Hasil • Dg Little’s Law lagi, jumlah rata-rata pelanggan dlm antrian
Hasil Grafik Antrian M/M/1 • Ekspektasi jumlah pelanggan dlm sistem
Jumlah pelanggan dlm sistem sbg fungsi utilisasi
In-Class Exercise • Suatu konsentrator menerima message dari satu grup terminal dan mentransmisikannya melalui suatu saluran transmisi tunggal. Misalkan message tiba sesuai proses Poisson dg rate satu message setiap 4 ms, dan waktu transmisi message mengikuti distribusi eksponensial dg mean 3 ms. (a) Cari rata-rata jumlah message dlm sistem dan total delay rata-rata (b) Berapa persentase peningkatan rate kedatangan shg menghasilkan dua kali total delay rata-rata
Traffic Multiplexing • Perhatikan suatu link komunikasi – Kapasitas transmisi tetap (C), rate dimana bit dp ditransmisikan (bit/sec) – Bbrp aliran trafik dp share capacity – Skim sharing dp mempengaruhi performansi
• Bentuk-Bentuk Multiplexing – Statistical multiplexing – Kanal terpisah • Time Division Multiplexing (TDM) • Frequency Division Multiplexing (FDM)
Statistical Multiplexing • Paket-paket dari semua aliran trafik digabungkan ke dlm satu antrian tunggal dan ditransmisikan secara FCFS • TSM = L/C diperlukan utk mentransmisikan L-bit paket
Time Division Multiplexing • Waktu dibagi dlm m slot, dan masing-masing dari m aliran trafik diberikan satu slot – Bangun m kanal, masing-masing dg kapasitas C/m – L-bit paket memerlukan TTDM = Lm/C sec utk transmit jika paket panjang dibandingkan dg panjang satu slot – L-bit paket memerlukan TTDM = L/C sec utk transmit jika slot sebesar panjang paket, tetapi harus menunggu (m-1) slot antar transmisi
Time Division Multiplexing
Frequency-Division Multiplexing FDM • Kanal bandwidth W dibagi kedlm m kanal dan masingmasing dari m aliran trafik diberikan satu kanal – Bangun m kanal, masing-masing dg bandwidth W/m, atau kapasitas C/m (abaikan ‘guard band’ antar kanal) – L-bit paket memrlukan TFDM = Lm/C sec utk transmit
Performansi Multiplexing • Stat Mux mempunyai delay rata-rata lebih kecil drpd TDM atau FDM – Kapasitas kanal terbuang dg TDM (wasted time slots) dan FDM (wasted bandwidth) jika aliran trafik idle – Waktu transmisi lebih besar utk TDM dan FDM
• Keuntungan TDM dari FDM – Stat mux mempunyai delay rata-rata lebih kecil tetapi variasi delay lebih besar – TDM dan FDM mengeleminasi keperluan utk mengidentifikasi aliran trafik asosiasi dg tiap paket
Performansi Multiplexing • Kita dp menggunakan hasil antrian M/M/1 utk menganalisa Statistical Multiplexing (SM) vs Time Division Multiplexing (TDM) atau Frquency Division Multiplexing (FDM) • Asumsi: – m aliran paket Poisson, masing-masing dg rate kedatangan /m, ditransmisikan melalui kanal komunikasi tunggal – Panjang paket utk semua aliran memp distribusi eksponensial dg waktu transmisi rata-rata 1/
Performansi Multiplexing • SM mengkombinasikan m aliran dari paket-paket dan mentransmisikannya dlm satu aliran tunggal • TDM dan FDM menjaga aliran tetap terpisah
Performansi Multiplexing • Utk SM
• Utk TDM (atau FDM)
• Rata-rata paket menghabiskan m kali lebih lama dalam antrian dan service dg TDM atau FDM dibandingkan dg SM – Namun kita tidak mempertimbangkan variansi
