Slide 1

Managemen Antrianidi@ittelkom.ac.id1Jaringan AntrianAntrian tunggal (single queue) bisa merepresentasikan sal. transmisi, kanal, koneksi, sesi, dll.Umumnya jaringan (data) terdiri dari banyal sal. transmisi atau kanal

Perlu memodelkan jaringan sbg jaringan antrian yg berinteraksi, bukan sbg antrian tunggalJaringan Antrian: Contoh SederhanaJaringan sederhana dg 2 saluran transmisi (1 dan 2) dan 3 node (a, b dan c)Kedatangan bisa terjadi pd node a dan bKepergian bisa terjadi pd node b dan c

Jaringan Antrian: Contoh SederhanaModel antrianTiap link adalah sebuah antrian dlm jaringanPerlu mengetahui probabilitas routing, mis. berapa paket dari node a keluar dari sistem pd node b

Jaringan Antrian: Contoh LainKedatangan trafik pd tiap antrian (sal. Transmisi) dp mencakup:Trafik internal yg keluar dari satu atau lebih antrian lainTrafik eksternal yg memasuki jaringan

Open Queueing Networks(Jaringan Antrian Terbuka)Closed Queueing Networks(Jaringan Antrian Tertutup)

Jaringan Antrian TerbukaAnalisa Antrian TandemBurke Theorem:Memberikan hasil general untuk proses penyelesaian bukan hanya M/M/1 sajaUntuk antrian M/M/1, M/M/m atau M/M/ pd steady state dg laju kedatangan a) Proses kepergian/penyelesaian adalah Poisson dg laju b) Pd tiap waktu t, jumlah pelanggan dlm sistem independen dari urutan waktu kepergian sebelum t

Kesulitan-Kesulitan Analitis: Bagian 1Perhatikan dua sal. transmisi (antrian) tandem dg kapasitas (service rate) samaKedatangan-kedatangan ke sistem adalah PoissonPaket-paket memp. panjang yg sama, yaitu memp. waktu pelayanan tetap

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

Kesulitan-Kesulitana Analitis: Bagian 1Bagaimana dg antrian kedua?Waktu antar kedatangan n, bukan Poisson

Kesulitan-Kesulitan Analitis: Bagian 1Perhatikan antrian keduaWaktu antar kedatangan n, waktu antar kedatangan antara paket ke n dan n+1Waktu pelayanan, sn utk paket nCatatan 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 2Perhatikan versi yg lebih jelas dari antrian tandem -- kedatangan Poisson dan panjang paket (waktu pelayanan) terdistribusi eksponensialAntrian pertama adalah M/M/1Antrian kedua bukan M/M/1 krn waktu antar kedatangan pd antrian kedua berkorelasi dg waktu pelayanan paket

Kesulitan-Kesulitan Analitis: Bagian 2Pd 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+1Paket yg panjang yg tiba pd antrian kedua kemungkinan besar menemukan lebih sedikit pelanggan dlm antrian

Aplikasi Antrian Tandem Pada Jaringan DataAntrian kedua dapat dimodelkan sbg M/M/1 jika tidak ada korelasi antara waktu kedatangan dg waktu layanan Kleinrock Independence ApproximationGabungan bbrp aliran paket pada kanal transmisi mempunyai efek mengembalikan independensi antara waktu antar kedatangan paket dan panjang paketKrnnya, untuk feed-forward queue tanpa feedback spt pada virtual circuit jaringan paket dapat dimodelkan sebagai serie dari antrian tunggal M/M/1

Antrian Markovian TandemMisalkan state jaringan dg 2 antrian dinyatakan dg vektor (n1, n2)ni jumlah pelanggan dalam antrian atau service dalam antrian iJoint state probabilities:

P(n1, n2) = (1 - 1) 1n1(1- 2) 2n2

Joint probability merupakan product-form dari marginal probability

Jackson Queueing NetworksMemberikan solusi product-formJackson queueuing network adalah suatu jaringan dari M buah sistem antrain M/M/m dg:Hanya ada satu kelas pelanggan dlm jaringanPelanggan eksternal tiba ke node i sesuai dg proses Poisson dg laju i 0Waktu layanan pd tiap node i terdistribusi eksponensial dg mean i. Waktu layanan dari node lain independen dari proses kedatanganPelanggan setelah mendapatkan layanan pd node i akan melanjutkan ke node j dg probabilitas pij atau meninggalkan jaringan dg probabilitas:

Jackson Queueing Networks

Ukuran Performansi utk Jaringan Antrian TerbukaProses kedatangan pd tiap node umumnya tidak Poisson:

Total throughput dari jaringan

Rata-rata pelanggan mengunjungi node Vi

Rata-rata secara network-wide:

Ukuran Performansi utk Jaringan Antrian TerbukaMarginal Probabilitas dari node i:

Jumlah pelanggan pada antrian node i:

Jumlah pelanggan pada keseluruhan sistem:

Ukuran Performansi utk Jaringan Antrian TerbukaRata-rata waktu dalam jaringan:

Aplikasi Antrian Tandem Pada Jaringan DataModel untuk virtual circuit:

Aplikasi Antrian Tandem Pada Jaringan DataMisalkan jaringan mempunyai data sbb:Kapasitas semua link sama = 19200 bit/sec

Aplikasi Antrian Tandem Pada Jaringan DataKalkulasi delay end-to-end untuk:(i) paket-paket yg dikirim dari B ke F melalui VC2(ii) paket-paket yg dikirim dari A ke F melalui VC1(iii) paket-paket yg dikirim dari E ke F melalui VC1

In-Class ExerciseCari throughput rata-rata 1, 2 untuk tiap antrian pd jaringan antrian di bawah (sbg fungsi )

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?

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

Jaringan Antrian TertutupJaringan Antrian TertutupM = Jumlah antrianN = jumlah pelanggan dalam jaringan antrian tertutup

Model dari Jaringan Antrian TertutupJaringan antrian tertutup dp digunakan utk memodelkan tipe-tipe sistem berbedaDlm realitas sistem adalah terbukaJumlah pelanggan dlm sistem pd sembarang waktu adalah tetap berharga NAplikasiModel populasi terbatas (M/M/s/s/K)Tiap-tiap dari K user dp mempunyai paling banyak 1 panggilan aktif pd suatu saatMaksimum jumlah panggilan KSistem dengan heavy loadMulti-stage packet switches dg jumlah paket terbatas yg dibolehkan di dalam, dan paket baru selalu siap utk masuk jika satu meninggalkanWindow-based flow controlJumlah maksimum paket transit pada sembarang waktuTraffic EquationsPersamaan trafik utk jaringan tertutup

Spt, persamaan trafik utk jaringan terbuka, kecuali tidak ada term utk sumber (i)Tidak spt jaringan terbuka, ini tdk mempunyai solusi unik

Solusi Product Form Jaringan TertutupDari penurunan Global Balance Equations:

iiContoh Jaringan Tertutup (1)Sistem komputer memungkinkan dua job aktif pd setiap saatTiap 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 ExerciseMisalkan state sistem (n1, n2) mengindikasikan ada n1 job di CPU dan n2 job pd I/OEnumerasi state yg mungkinList persamaan trafik (dua persamaan)

Contoh Jaringan Tertutup (3)Solusi product form

Contoh Jaringan Tertutup (4)Faktor normalisasi

iContoh Jaringan Tertutup (5)Prob. steady state utk state (2,0)

11122In-Class ExerciseTentukan prob. steady state utk state (0,2) dan (1,1)

UtilisasiUtilisasi i adalah proporsi waktu server i sibuk Mis. i adalah laju kedatangan aktual ke antrian iUtilisasi dari antrian i adalah

Metoda lain tersediaSbg contoh, antrian i sibuk jika diduduki oleh ni > 0 jobs

iIn-Class ExerciseGunakan contoh jaringan yg sama, misalkan1 = 4 jobs/s2 = 1 job/sp = 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 antrianKomentar utk Faktor NormalisasiMetoda ini utk mencari konstanta normalisasi adalah tdk praktis utk sistem yg sangat besarAlgoritma utk komputasi numerik dp digunakan utk menentukan G(M,N)Sbg contoh algoritma convolution utk jaringan tertutupAlgoritma MVA

Example: Cyclic Network

In-Class Exercise

In-Class Exercise

In-Class ExerciseABCDE

In-Class ExercisePerhatikan jaringan paket switching di bawah. Terminal 1, 2 dan 3 membangkitkan trafik Poisson dengan laju masing-masing 1 = 0,5, 2 = 2 dan 3= 0,5 paket/det. Semua trafik ditujukan ke node 4, seperti diperlihatkan pada gambar. Semua link mempunyai kapasitas laju layanan = 6 paket/det dengan distribusi eksponensial. a. cari waktu delay rata-rata, T dari node 1 ke 4, jika paket melalui lintasan 1 2 4. b.Ulangi, soal (a) jika paket melalui lintasan 1 2 3 4. c. Paket sekarang dirutekan secara random melalui jaringan, dari node 1 ke node 4, dengan probabilitas routing berikut: q13 = 1/3, q23 = , q34 = 1, Cari delay rata-rata melalui jaringanPR Antrian Terbuka