net queue 06

Jaringan Antrian

Hendrawanhend@telecom.ee.itb.ac.id

Outline

• Motivasi dan kesulitan-kesulitan analitis• Open vs Closed networks of queue• Solusi product-form

– Jackson’s theorem

• Closed networks of queue

Jaringan Antrian

• Antrian tunggal (single queue) bisa merepresentasikan sal. Transmisi, kanal, koneksi, sesi, dll.

• Jaringan data terdiri dari banyal sal. transmisi atau kanal

• Perlu memodelkan jaringan sbg jaringan antrian yg berinteraksi, bukan sbg antrian tunggal

Jaringan Antrian: Contoh Sederhana

• Jaringan sederhana dg 2 saluran transmisi (1 dan 2) dan 3 node (a, b dan c)– Kedatangan bisa terjadi pd node a dan b– Kepergian bisa terjadi pd node b dan c

Jaringan Antrian: Contoh Sederhana

• Model antrian– Tiap link adalah sebuah antrian dlm jaringan– Perlu mengetahui probabilitas routing, mis. berapa

paket dari node a keluar dari sistem pd node b

Jaringan Antrian: Contoh Lain

• Kedatangan trafik pd tiap antrian (sal. Transmisi) dp mencakup:– Trafik internal yg keluar dari satu atau lebih antrian

lain– Trafik eksternal yg memasuki jaringan

Kesulitan-Kesulitan Analitis: Bagian 1

• Perhatikan dua sal. transmisi (antrian) tandem dg kapasitas (service rate) sama– Kedatangan-kedatangan ke sistem adalah Poisson– Paket-paket memp. panjang yg sama, yaitu memp.

waktu pelayanan tetap

• Dg asumsi ini, antrian pertama adalah M/D/1– Formula P-K memberikan delay paket rata-rata

Kesulitan-Kesulitana Analitis: Bagian 1

• Bagaimana dg antrian kedua?– Waktu antar kedatangan n, bukan Poisson

Kesulitan-Kesulitan Analitis: Bagian 1

• Perhatikan antrian kedua– Waktu antar kedatangan n, waktu antar kedatangan

antara paket ke n dan n+1

– Waktu pelayanan, sn utk paket n

• Catatan bhw sn n , shg paket n+1 tdk pernah mengantri

– NQ = 0

– W = 0

• Antrian kedua jelas bukan M/D/1

Kesulitan-Kesulitan Analitis: Bagian 2

• Perhatikan versi yg lebih jelas dari antrian tandem -- kedatangan Poisson dan panjang paket (waktu pelayanan) terdistribusi eksponensial– Antrian pertama adalah M/M/1– Antrian kedua bukan M/M/1 krn waktu antar

kedatangan pd antrian kedua berkorelasi dg waktu pelayanan paket

Kesulitan-Kesulitan Analitis: Bagian 2

• Pd antrian kedua – Waktu antar kedatangan antara paket ke n dan n+1

lebih besar dari atau sama waktu transmsisi utk paket n+1, yaitu n sn+1

– Paket yg panjang yg tiba pd antrian kedua kemungkinan besar menemukan lebih sedikit pelanggan dlm antrian

Solusi Product Form

• Misalkan state jaringan dg M antrian dinyatakan dg vektor (n1, n2, …, nM)– ni jumlah “pelanggan” dalam antrian atau service dalam

antrian i

• Solusi product form– Joint state probabilities dinyatakan sbg perkalian

(product) dari probabilitas-probabilitas antrian individual yg sesuai

– P(n1, n2, …,nM) = P(n1)P(n2) … P(nM)

• Antrian berlaku seolah-olah mereka independen– Pelanggan pd tiap antrian adalah independen pd suatu

titik waktu tertentu

Tipe-Tipe Jaringan Antrian

• Jaringan antrian terbuka (open networks of queues)– Pelanggan-pelanggan tiba dan pergi dari jaringan– Contoh: paket-paket pada suatu jaringan

• Jaringan antrian tertutup (Closed networks of queues)– Pelanggan dlm jumlah yg tetap bersirkulasi dlm

jaringan– Contoh, pemrosesan pekerjaan (job) dlm suatu

sistem computing

Jaringan Antrian Tertutup

• Jumlah job tetap bersirkulasi diantara antrian– Job kembali ke CPU dg prob. p– Job memerlukan I/O dg prob. 1-p

• Kita akan diskusikan jaringan antrian tertutup nanti

Jaringan Antrian Terbuka

• Pelanggan masuk dan keluar sistem, mengambil nol atau lebih lintasan

• Fokus awal kita

Notasi

= total mean laju kedatangan ke jaringan i = mean laju pelayanan dari server ke-i

• rsj = prob. pelanggan tiba dari sumber akan di-

route-kan ke antrian j

• rjd = prob. pelanggan meninggalkan antrian j akan

di-route-kan ke tujuan (dan meninggalkan sistem)

• rjk = prob. pelanggan meninggalkan antrian j akan

di-routekan ke antrian k

Contoh Antrian Tandem

Contoh Multi-Stage Network

• rjk > 0 hanya antar tingkat (stage) yg berdekatan

Contoh: Topologi Umum

Deskripsi State dari Sistem

• State dari sistem dg M antrian dp didefinisikan sbg vektor M-elemen, dimana ni adalah jumlah pada sistem antrian ke-i (dlm antrian dan pelayanan)

• Tujuan kita adalah mencari pmf dari n

Throughput Rata-Rata

• Mis. i throuhput rata-rata melalui antrian i

• Berarti laju memasuki (meninggalkan) sistem antrian tertentu

• Persamaan trafik ...

In-Class Exercise

• Cari throughput rata-rata 1, 2 untuk tiap antrian pd jaringan antrian di bawah (sbg fungsi )

Global Balance Equations (1)

• Global balance equations …– Laju meninggalkan state n harus sama dg laju

memasuki state n

• Mis. (n) adalah prob. berada di state n• Berapa laju meninggalkan state n ?

Notasi: Unit Vektor ke-i

Global Balance Equations (2)

Global Balance Equations (3)

• Laju masuk harus sama laju keluar …

Local Balance Equations

• Local balance equations adalah generalisasi balance equations dari antrian M/M/1

• Local balance equations plus global balance equations dan traffic equations, memberikan solusi product form

Solusi Product Form

• Jaringan berlaku seolah-olah semua antrian independen secara statistik

In-Class Exercise

• Dlm jaringan antrian spt latihan sebelumnya, asumsikan kedatangan Poisson dg laju kedatangan 1000 paket/det dan rata-rata waktu pelayanan pd tiap antrian 0,2 ms. Berapa probabilitas tidak ada paket dlm sistem?

Marginal pmf

• Krn product form, marginal pmf dari ni pelanggan pd sistem antrian ke-i adalah …

• Ambil dari analisa antrian M/M/1 …

Pelanggan dan Delay dlm Jaringan

• Hasil utk jaringan penuh …

In-Class Exercise

• Utk jaringan dlm dua latihan sebelumnya, berapakah …(a) Jumlah rata-rata paket dlm jaringan?(b) Rata-rata delay melalui jaringan?

Jackson’s Theorem: Overview

• Jackson’s theorem adalah yg pertama memperlihatkan solusi product form utk jaringan antrian

• Jackson’s theorem mengidikasikan bhw rata-rata jumlah pelanggan dlm sistem dp diturunkan dg memperlakukan tiap antrian sbg antrian M/M/1– Korelasi antara waktu transmisi dan waktu antar

kedatangan dieliminasi– Randomisasi membagi trafik diantara route berbeda

Jackson’s Theorem: Asumsi (1)

• Kedatangan kedlm sistem Poisson dan waktu pelayanan exponensial– Cat. kedatangan ke antrian individual, akan secara

umum, tidak Poisson

• Independensi dari waktu antar kedatangan dan panjang paket

Jackson’s Theorem: Asumsi (2)

• Pemecahan aliran dirandomisasi menggunakan prob. rij yg diaplikasikan ke semua paket yg pergi dari antrian i– Aliran berbeda mungkin tdk mempunyai prob.

routing berbeda– Jackson’s theorem dp diperluas utk

memperhitungkan kelas pelanggan yg berbeda

Jackson’s Theorem (1)

• State dari sistem adalah sebuah vektor,

• Jackson’s theorem: asumsi j < 1, j = 1, 2, …, M maka utk semua n1, n2, …, nM

Jackson’s Theorem (2)

• Jackson’s theorem menyatakan:– Jumlah pelanggan di tiap antrian pd sistem

terdistribusi seolah-olah tiap antrian adalah M/M/1– Jumlah pelanggan di tiap antrian adalah independen

dari jumlah di antrian lain– Proses kedatangan total pd tiap antrian tidak perlu

Poisson

Jaringan Antrian Tertutup

Model dari Jaringan Antrian Tertutup

• Jaringan antrian tertutup dp digunakan utk memodelkan tipe-tipe sistem berbeda

• Dlm realitas sistem adalah terbuka• Jumlah pelanggan dlm sistem pd sembarang

waktu adalah tetap berharga N

Aplikasi

• Model populasi terbatas (M/M/s/s/K)– Tiap-tiap dari K user dp mempunyai paling banyak 1

panggilan aktif pd suatu saat– Maksimum jumlah panggilan K

• Sistem dengan heavy load– Multi-stage packet switches dg jumlah paket terbatas

yg dibolehkan di dalam, dan paket baru selalu siap utk masuk jika satu meninggalkan

• Window-based flow control– Jumlah maksimum paket transit pada sembarang

waktu

Traffic Equations

• Persamaan trafik utk jaringan tertutup …

• Spt, persamaan trafik utk jaringan terbuka, kecuali tidak ada term utk sumber (rsi)

• Tidak spt jaringan terbuka, ini tdk mempunyai solusi unik

Global Balance Equations

Solusi Product Form Jaringan Tertutup

Contoh Jaringan Tertutup (1)

• Sistem komputer memungkinkan dua job aktif pd setiap saat

• Tiap job memerlukan CPU dan I/O processing

Contoh Jaringan Tertutup (2)

• Jika job meninggalkan CPU, ada dua kemungkinan …– Job selesai dan segera digantikan oleh job lain (dg

prob. p)– Job memerlukan I/O, maka tambahan CPU dg prob 1

- p)

In-Class Exercise

• Misalkan state sistem (n1, n2) mengindikasikan ada n1 job di CPU dan n2 job pd I/O– Enumerasi state yg mungkin– List persamaan trafik (dua persamaan)

Contoh Jaringan Tertutup (3)

• Solusi product form …

Contoh Jaringan Tertutup (4)

• Faktor normalisasi …

Contoh Jaringan Tertutup (5)

• Prob. steady state utk state (2,0)

In-Class Exercise

• Tentukan prob. steady state utk state (0,2) dan (1,1)

Utilisasi

• Utilisasi i adalah proporsi waktu server i sibuk

• Mis. i adalah laju kedatangan aktual ke antrian i

• Utilisasi dari antrian i adalah …

• Metoda lain tersedia

• Sbg contoh, antrian i sibuk jika diduduki oleh ni > 0 jobs …

In-Class Exercise

• Gunakan contoh jaringan yg sama, misalkan1 = 4 jobs/s

2 = 1 job/s

p = 1/3a) Kalkulasi probabilitas state b) Kalkulasi utilisasi pd tiap antrianc) Kalkulasi jumlah rata-rata pelanggan pd tiap

sistem antriand) Kalkulasi rata-rata delay melalui tiap sistem

antrian

Komentar utk Faktor Normalisasi

• Metoda di atas utk mencari konstanta normalisasi adalah tdk praktis utk sistem yg sangat besar

• Algoritma utk komputasi numerik dp digunakan utk menentukan G(M,N)– Sbg contoh algoritma convolution utk jaringan

tertutup

TUGAS PELAJARI ALGORITMA/METODA UTK MENENTUKAN G(M,N): CONVOLUTION & MVA find in any Q Theory textbooks!