teori antrian antrian m/m/1

61
Teori Antrian Antrian M/M/1 Hendrawan [email protected]

Upload: ezra

Post on 27-Jan-2016

320 views

Category:

Documents


13 download

DESCRIPTION

Teori Antrian Antrian M/M/1. Hendrawan [email protected]. Outline. Motivasi Introduksi sistem antrian Elemen sistem antrian Notasi sistem antrian Background Proses kedatangan dan keberangkatan Little’s law Antrian M/M/1 Penurunan dan Hasil Aplikasi utk analisa multiplexing. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Teori Antrian Antrian M/M/1

Teori AntrianAntrian M/M/1

[email protected]

Page 2: Teori Antrian Antrian M/M/1

Outline

• Motivasi• Introduksi sistem antrian

– Elemen sistem antrian– Notasi sistem antrian

• Background– Proses kedatangan dan keberangkatan

• Little’s law• Antrian M/M/1

– Penurunan dan Hasil– Aplikasi utk analisa multiplexing

Page 3: Teori Antrian Antrian M/M/1

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, ...

Page 4: Teori Antrian Antrian M/M/1

Dasar Antrian

• Single queue system biasa digunakan utk merepresentasikan shared resource networks

• Network of queues biasa digunakan utk merepresentasikan tipe jaringan yg lain– Process networks– Switching networks

Page 5: Teori Antrian Antrian M/M/1

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)

Page 6: Teori Antrian Antrian M/M/1

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)?

Page 7: Teori Antrian Antrian M/M/1

Process Networks

• Multi-stage switch• Distributed simulation system• Manufacturing process

Page 8: Teori Antrian Antrian M/M/1

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?

Page 9: Teori Antrian Antrian M/M/1

Switching Networks

• Jaringan telepon (telepon: circuit switches)• Jaringan signaling telepon (switches; STP)• Jaringan Paket X.25 (komputer: packet switches)• Internet (komputer: router)

Page 10: Teori Antrian Antrian M/M/1

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)?

Page 11: Teori Antrian Antrian M/M/1

Apa yang Bisa Dipelajari?

Faktor• Jumlah pelanggan• Pola penggunaan

(workload)• Karakteristik service• Jumlah resource

Performansi• Waktu tunggu• Blocking• Loss

Page 12: Teori Antrian Antrian M/M/1

Elemen-Elemen Antrian

Page 13: Teori Antrian Antrian M/M/1

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

Page 14: Teori Antrian Antrian M/M/1

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

Page 15: Teori Antrian Antrian M/M/1

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

Page 16: Teori Antrian Antrian M/M/1

Notasi Antrian

a/b/m/K• m = jumlah server• K = jumlah maksimum pelanggan yg

dibolehkan dlm sistem

Page 17: Teori Antrian Antrian M/M/1

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

Page 18: Teori Antrian Antrian M/M/1

Distribusi Kedatangan

• Pn(t) = P[Jumlah kedatangan sampai saat t = n]

Page 19: Teori Antrian Antrian M/M/1

Jumlah Kedatangan

• Mis. E[n] adalah mean dari jumlah kedatangan dlm perioda interval t

– Mean

– Variance

0

)(][n

n ttnPnE

tnEnEn 222 ][][

Page 20: Teori Antrian Antrian M/M/1

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

Page 21: Teori Antrian Antrian M/M/1

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

Page 22: Teori Antrian Antrian M/M/1

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

Page 23: Teori Antrian Antrian M/M/1

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

Page 24: Teori Antrian Antrian M/M/1

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

Page 25: Teori Antrian Antrian M/M/1

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

Page 26: Teori Antrian Antrian M/M/1

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

Page 27: Teori Antrian Antrian M/M/1

Markov Property

• Jika kita tahu sistem ada dlm state a pd saat tk, probabilitas transisi ke state lainnya pd saat tk+1 dp ditentukan – tidak perla tambahan informasi masa lalu

Page 28: Teori Antrian Antrian M/M/1

Little’s Law

• Jumlah pelanggan rata-rata dlm sistem (antrian) sama dg rate kedatangan dikalikan waktu rata-rata dlm sistem (antrian)

Page 29: Teori Antrian Antrian M/M/1

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]

Page 30: Teori Antrian Antrian M/M/1

Utilisasi

• Utilisasi dari sistem single server

• Utilisasi dari sistem c-server

Page 31: Teori Antrian Antrian M/M/1

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?

Page 32: Teori Antrian Antrian M/M/1

Saluran Transmisi

Page 33: Teori Antrian Antrian M/M/1

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

Page 34: Teori Antrian Antrian M/M/1

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

Page 35: Teori Antrian Antrian M/M/1

Network of Transmission Lines

Page 36: Teori Antrian Antrian M/M/1

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

Page 37: Teori Antrian Antrian M/M/1

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

Page 38: Teori Antrian Antrian M/M/1

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

Page 39: Teori Antrian Antrian M/M/1

Markov Chain

• Karena memoryless property dari r.v. eksponensial, jumlah pelanggan dlm sistem saat t, N(t), dp diekspresikan sbg continuous-time Markov chain

Page 40: Teori Antrian Antrian M/M/1

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

Page 41: Teori Antrian Antrian M/M/1

Global Balance

• Total rate transisi keluar dari state n sama dg total rate transisi ke state n– Dynamic equilibrium

Page 42: Teori Antrian Antrian M/M/1

Global Balance Equations

• Global balance equation utk antrian M/M/1

• Jika ada N state, ada N persamaan, termasuk relasi berikut

Page 43: Teori Antrian Antrian M/M/1

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

Page 44: Teori Antrian Antrian M/M/1

Local Balance Equations

• Persamaan local balance utk anrian M/M/1

Page 45: Teori Antrian Antrian M/M/1

Menyelesaikan Local Balance Equations

• Pers local balance menghasilkan n-1 rekursi berikut

Page 46: Teori Antrian Antrian M/M/1

Menyelesaikan Local Balance Equations

• Normalisasi dicapai melalui ‘conservation of probability’

Page 47: Teori Antrian Antrian M/M/1

Menyelesaikan Local Balance Equations

• Dg = / dan menggunakan identitas berikut

• Maka

Page 48: Teori Antrian Antrian M/M/1

Hasil

• Jika = / < 1 , kita dp

• Utilisasi

• Mean dari jumlah pelanggan, n

Page 49: Teori Antrian Antrian M/M/1

Hasil

• Dg Little’s law, dp dicari waktu rata-rata dlm sistem

• Dan waktu rata-rata dlm antrian

Page 50: Teori Antrian Antrian M/M/1

Hasil

• Dg Little’s Law lagi, jumlah rata-rata pelanggan dlm antrian

Page 51: Teori Antrian Antrian M/M/1

Hasil Grafik Antrian M/M/1

• Ekspektasi jumlah pelanggan dlm sistem

Jumlah pelanggan dlm sistem sbg fungsi utilisasi

Page 52: Teori Antrian Antrian M/M/1

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

Page 53: Teori Antrian Antrian M/M/1

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)

Page 54: Teori Antrian Antrian M/M/1

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

Page 55: Teori Antrian Antrian M/M/1

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

Page 56: Teori Antrian Antrian M/M/1

Time Division Multiplexing

Page 57: Teori Antrian Antrian M/M/1

Frequency-Division Multiplexing FDM

• Kanal bandwidth W dibagi kedlm m kanal dan masing-masing 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

Page 58: Teori Antrian Antrian M/M/1

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

Page 59: Teori Antrian Antrian M/M/1

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/

Page 60: Teori Antrian Antrian M/M/1

Performansi Multiplexing

• SM mengkombinasikan m aliran dari paket-paket dan mentransmisikannya dlm satu aliran tunggal

• TDM dan FDM menjaga aliran tetap terpisah

Page 61: Teori Antrian Antrian M/M/1

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