04/12/2012
Model Loss Sistem Anhar Prodi Teknik Elektro S1 UR
Topik Bahasan.. Bahasan.. Notasi Model Antrian (Kendall) Model Poisson (∞ customers, ∞ servers) Model Erlang (∞ customers, n < ∞ servers) Binomial model (k < ∞ customers, n = k servers) Engset model (k < ∞ customers, n < k servers)
2
1
04/12/2012
Notasi Model Antrian (Kendall)
A/B/n/p/k – A menyatakan proses kedatangan Interarrival time distribution: M= exponential (memoryless) D= deterministic G= general
– B menyatakan waktu pelayanan (service times) Service time distribution: M= exponential (memoryless) D= deterministic G= general
– n = jumlah server – p = jumlah tempat dalam sistem = jumlah server + tempat menunggu
3
Notasi Model Antrian (Kendall) (cont.) ◦ k = populasi pelanggan ◦ Nilai-nilai default (biasanya tidak dimunculkan) : p = ∞, k = ∞
◦ Contoh: M/M/1 M/D/1 M/G/1 G/G/1 M/M/n M/M/n/n+m M/M/∞ (Poisson model) M/M/n/n (Erlang model) M/M/k/k/k (Binomial model) M/M/n/n/k (Engset model, n < k)
4
2
04/12/2012
Model Poisson (M/M/∞) Model Poisson didefinisikan menggunakan model teletraffic berikut : – Kedatangan panggilan acak (random arrival/Pure Chance Traffic) dan independent satu sama lain – Selang waktu antar kedatangan terdistribusi eksponensial negatif – Jumlah sumber panggilan (customer) tak terhingga (k= ∞) – Laju rata-rata datangnya panggilan konstan (a=λ) Tak tergantung jumlah pendudukan yang sudah ada karena sumber panggilan tak terhingga
– Jumlah server yang melayani tak terhingga Setiap panggilan yang datang selalu dapat dilayani (lossless)
– Pola waktu pelayanan/pendudukan terdistribusi exponensial negatif dengan waktu pelayanan/pendudukan (service time) rata-rata = h = 1/µ – Harga rata-rata trafik sama dengan harga variansinya – Tidak ada buffer – Intensitas trafik = a = λ/µ
5
Diagram Transisi Kondisi Misalnya X(t) menyatakan jumlah customer di dalam sistem pada saat t Asumsikan bahwa X(t) = i pada suatu waktu t, dan kita lihat apa saja kemungkinan yang terjadi di dalam selang waktu yang sangat pendek (t, t+dt] : ◦ dengan peluang sebesar λdt + o(dt), bisa terdapat seorang pelanggan baru datang (transisi kondisi n → n+1) ◦ jika i > 0, dengan peluang sebesar iµdt + o(dt) bisa terdapat seorang pelanggan yang meninggalkan sistem (transisi kondisi n → n−1)
X(t) merupakan suatu proses Markov dengan diagram transisi kondisi sebagai berikut
0
1 6
3
04/12/2012
•
Persamaan kesetimbangan lokal
pn λ = pn +1 (n + 1) µ pn +1 = pi = •
λ ( n + 1) µ
pi =
a pi (n + 1)
n
a p0 , n = 0,1,2,3,... n!
Normalisasi
∞
∞
an pn = p0 ∑ = 1 ∑ n =0 n = 0 n! −1
∞ an p0 = ∑ = (e a ) −1 = e − a n =0 n! •
Maka distribusi dalam kondisi setimbang adalah Poisson
a n −a P{ X = i} = pi = e , n = 0,1,2,3,... n!
7
Sifat penting distribusi Poisson ◦ E [X] = a, D2[X] = a ◦ Seluruh trafik yang ditawarkan akan dapat diolah oleh server, artinya tidak ada trafik yang hilang (lossless) Oleh karena itu trafik yang ditawarkan akan sama dengan trafik yang dimuat atau A = Y
8
4
04/12/2012
Model Erlang (M/M/n/n) Model Erlang didefinisikan menggunakan model teletraffic berikut – Jumlah sumber panggilan tak terhingga (k=∞) – Selang waktu antar kedatangan terdistribusi eksponensial negatif dengan rata-rata 1/λ Pola kedatangan panggilan terdistribusi Poisson dengan laju rata-rata datangnya panggilan konstan (λ) Kedatangan panggilan acak (random arrival) dan independent satu sama lain Tak tergantung jumlah pendudukan yang sudah ada karena sumber panggilan tak terhingga
– Jumlah server terbatas (n < ∞) dan tidak ada buffer Tidak setiap panggilan yang datang selalu dapat dilayani; panggilan yang datang pada saat semua server sibuk akan tidak dapat dilayani panggilan-panggilan yang tidak dapat dilayani akan dihilangkan (lossy) : sistem rugi murni
– Pola waktu pelayanan/pendudukan terdistribusi exponensial negatif dengan waktu pelayanan/pendudukan rata-rata = h = 1/µ – Intensitas trafik = a = λ/µ
9
Rumus Rugi Erlang Dapat digunakan untuk menghitung prosentase panggilan yang hilang bila trafik yang ditawarkan dan jumlah server (ingat, server bisa berupa berkas saluran keluar, timeslot dsb.) diketahui Penurunan rumus menggunakan diagram transisi kondisi dan persamaan kesetimbangan – Koefisien kelahiran = λ (konstan) – Koefisien kematian = nµ – A = λ/µ
10
5
04/12/2012
λ
λ
0
λ
1
λ
2
µ
λ N
N-1
3µ
2µ
(N-1)µ
Nµ
λP(0) = 1µP(1) A.P(0) = 1.P(1) A.P(1) = 2.P(2) A.P(2) = 3.P(3) .. . A.P(n-1) = n.P(n) . . .
A.P(N-1) = N.P(N)
11
• Dari persamaan kesetimbangan tersebut bisa kita peroleh P(n) =
A n
P(n-1) =
• Jadi P(n) =
An
A2 n(n-1)
P(n-2)=
A3 n(n-1)(n-2)
P(n-3)= … =
An P(0) n!
P(0), dengan n = 0,1,2,…,N
n! • Mencari P(0) : N
– 1=
Σ P(n) = P(0) { 1+A+ A2!
2
n=0
– Jadi P(0) =
+
A3 3!
+…+
AN
}
N!
1 N
Σ
An
n=0 n!
12
6
04/12/2012
•
Sehingga An n! P(n) = 1+A+
• •
N A2 +…+ A 2! N!
Untuk n = 0,1,2,3,…, N P(N) = Probabilitas bahwa semua server sibuk; selama waktu ini semua panggilan yang datang ditolak (dihilangkan)
13
Simbol untuk menyatakan P(N) ◦ ◦ ◦ ◦ ◦ ◦ ◦
E1,N(A) EN(A) B (Blocking) Rumus Rugi Erlang Rumus Erlang-B B(N,A) Grade of Service (GOS) Dari segi nilai, GOS = Blocking Dari segi pengertian, GOS merupakan komplemen dari Blocking
14
7
04/12/2012
Jadi AN N! P(N) = E1,N(A) = EN(A) = B = 1+A+
N A2 + … +A 2! N!
Ditabelkan
15
Kongesti Waktu dan Kongesti Panggilan Probabilitas kondisi adalah lamanya waktu suatu kondisi berlangsung selama satu jam pengamatan (jam sibuk), maka P(N) dapat diartikan sebagai lamanya waktu dimana semua server (=N) sibuk berlangsung dalam jam jam sibuk sehingga P(N) disebut pula sebagai Kongesti Waktu (Time Congestion) Dapat pula dikatakan : P(N) adalah bagian waktu dimana N server sibuk
16
8
04/12/2012
• Pengertian Kongesti Panggilan = R(N) R(N) =
Jumlah panggilan yang ditolak Jumlah panggilan selama 1 jam
• Atau dengan kata lain : R(N) adalah bagian panggilan yang ditolak • Untuk kedatangan yang acak P(N) = R(N)
17
Efisiensi dan Kepekaan Efisiensi (= A/N) ◦ Untuk B tertentu, dengan bertambahnya A, akan diperlukan N yang lebih besar pula ◦ Makin besar A, makin besar (baik) efisiensinya B = 1% N
A
A/N
2
0,15
0,075
4
0,87
0,215
10
4,46
0,440
50
37,90
0,760 18
9
04/12/2012
Kepekaan ◦ Seberapa besar pengaruh perubahan A terhadap perubahan B untuk N tetap ◦ Makin besar A, makin besar kepekaaannya (perubahan Bnya)
B = 1% N
A
1,1A (A naik 1%)
Trafik 1,1A dan dengan N tetap; B berubah menjadi
2
0,15
0,165
0,012 (=1,2 %)
4
0,87
0,957
0,013 (=1,3 %)
10
4,46
4,906
0,015 (=1,5 %)
50
37,90
41,690
0,030 (=3,0 %) 19
Model Erlang dapat diterapkan pada trafik telepon di dalam suatu berkas saluran trunk dimana jumlah user yang menggunakannya sangat banyak ◦ customer = call − λ = call arrival rate (calls per time unit) ◦ h = 1/µ = average call holding time (time units) ◦ a = λ /µ = traffic intensity ◦ N = kapasitas link (jumlah saluran)
20
10
04/12/2012
• Harga rata-rata trafik yang dimuat oleh berkas saluran (pada rumus Erlang) – Merupakan jumlah saluran rata-rata yang diduduki (selama waktu 1 jam sibuk) – Y = trafik yang dimuat = N
N
Σ
n=0
n.P(n)=
Σ
n=0
An/(n-1)! N
Σ
Aj/j!
j=0
N
=A
Σ
n=0
An-1/(n-1)! =A N
Σ
j=0
– Y = A [ -B + 1]
Aj/j!
-
AN/N! N
Σ
Aj/j!
N
+
Σ
n=0
j=0
B
An/n! N
Σ A /j! j
j=0
1
21
Jadi : ◦ Y = A[1-B] atau ◦ A = Y + AB A = Trafik yang ditawarkan (rata-rata) Y = Trafik yang dimuat (rata-rata) AB = R = Trafik yang ditolak (hilang)
22
11
04/12/2012
Rumus Rekursif Erlang En+1(A)=
=
An+1/(n+1)! 2 n+1 1+A+ A +…+ A 2! (n+1)! [A/(n+1)] An/n! 2 n+1 1+A+ A +…+ A 2! (n+1)!
23
Rumus Rekursif Erlang (2) A
An/n! 2 1+A+ A +…+ 2!
En+1(A)=
An n!
An+1/(n+1)! (n+1) 1+
2 n+1 1+A+ A +…+ A 2! (n+1)!
24
12
04/12/2012
Rumus Rekursif Erlang (3) A.En(A)
En+1(A)= (n+1) 1+
An+1/(n+1)!
A
2 (n+1) 1+A+ A +…+ 2!
An n!
A.En(A)
=
(n+1) 1+
A (n+1)
En(A)
25
Rumus Rekursif Erlang (4) Jadi En+1(A)=
A.En(A) n + 1 + A.En(A)
atau
En (A)=
A.En-1(A) n + 1 + A.En-1(A)
26
13
04/12/2012
Rumus Rekursif Erlang (5) Misalkan akan dihitung blocking dari suatu sistem dengan A=15,7 Erlang dan N=10 saluran Perhitungannya dimulai dengan n=0 yaitu E0(15,7)=1 dan seterusnya sampai E10(15,7)
27
latihan Dua buah PABX akan dihubungkan satu sama lain. Trafik total yg ditawarkan dari PABX A ke PABX B adalah 25 erlang, demikian pula sebaliknya. Bila blocking pada berkas saluran penghubung diinginkan 1%, tentukan : ◦ Hitung jmlh saluran yg harus disediakan bila digunakan sirkuit one way. ◦ Hitung jmlh saluran yg harus disediakan bila digunakan sirkuit two way. 28
14
04/12/2012
Suatu berkas saluran terdiri dari 18 saluran. Ditawari trafik dng laju kedatangan panggilan 480 panggilan/jam dan rata-rata waktu pendudukan selama 105 detik. Bila kedatangan panggilan terdistribusi Poisson, hitung trafik yg ditawarkan, time congestion, call congestion dan jumlah panggilan yg ditolak rata-rata perjamnya. 29
Model Binomial (M/M/k/k/k) Model Binomial didefinisikan oleh model teletraffic berikut : – Jumlah sustomer terbatas tapi independen satu sama lain (k < ∞) on-off type customers (alternating between idleness and activity)
– Idle times terdistribusi eksponensial negatif dengan mean 1/υ – Jumlah server sama dengan jumlah customer (n = k) – Waktu pelayanan terdistribusi eksponensial negatif dengan mean 1/µ – Tidak ada buffer – Model Binomial bersifat lossless
30
15
04/12/2012
On--off tye customer On Misalkan Xj(t) menyatakan kondisi dari customer j ( j = 1,2,…,k ) pada waktu t State 0 = idle, state 1 = active = dalam pelayanan Kita lihat peristiwa yang terjadi selama selang waktu yang sangat singkat (t, t+h]: ◦ Jika Xj(t) = 0, customer menjadi aktif (terjadi transisi dari 0 ke 1) dengan peluang sebesar υh + o(h), ◦ Jika Xj(t) = 1, customer menjadi idle (terjadi transisi dari 1 ke 0) dengan peluang sebesar µh + o(h)
Proses Xj(t) merupakan proses Markov dengan diagram transisi kondisi sebagai berikut
31
Persamaan kesetimbangan lokal :
• Normalisasi :
• Dengan demikian distribusi pada kondisi setimbang dari seorang customer adalah distribusi Bernoulli dengan peluang sukses sebesar υ/(υ +µ) • offered traffic adalah υ/(υ +µ) • Dari sini kita bisa mengambil deduksi bahwa distribusi pada kondisi setimbang dari kondisi sistem secara keseluruhan (yaitu jumlah customer yang aktif) adalah distribusi binomial Bin(k, υ /(υ +µ)) 32
16
04/12/2012
Diagram Transisi Kondisi Misalnya X(t) menyatakan jumlah customer yang aktif ◦ Asumsikan bahwa X(t) = i pada saat t, dan kita perhatikan kejadian selama selang waktu yang sangat singkat (t, t+h]: Jika i < k, seorang customer yang idle menjadi aktif (terjadi transisi kondisi dari i ke i+1) dengan peluang sebesar (k−i)υh + o(h) Jika i > 0, seorang customer yang aktif menjadi idle (terjadi transisi kondisi dari i ke i-1) dengan peluang iµh + o(h), Proses X(t) adalah proses Markov dengan diagram transisi kondisi sebagai berikut
33
Persamaan kesetimbangan lokal
• Normalisasi
34
17
04/12/2012
Jadi distribusi dalam kondisi setimbang adalah binomial
35
Model Engset (M/M/n/n/k) Model Engset didefinisikan oleh model teletraffic berikut : – Jumlah pelanggan terbatas tetapi independen satu sama lain (k < ∞) on-off type customers (alternating between idleness and activity)
– Idle times terdistribusi eksponensial negatif dengan mean 1/υ – Jumlah server lebih kecil daripada jumlah customer (n < k) – Waktu pelayanan terdistribusi eksponensial negatif dengan mean 1/µ – Tidak ada buffer – Model Engset bersifat lossy 36
18
04/12/2012
Diagram Transisi Kondisi Misalnya X(t) menyatakan jumlah customer yang aktif ◦ Asumsikan X(t) = i pada saat t, dan kita perhatikan apa yang terjadi selama selang waktu yang sangat singkat (t, t+h]: Jika i < n, seorang customer yang idle menjadi aktif (terjadi transisi kondisi dari i ke i+1) dengan peluang sebesar (k−i)υh + o(h) Jika i > 0, seorang customer yang aktif menjadi idle (terjadi transisi kondisi dari i-1 ke i) dengan peluang iµh + o(h),
◦ Proses X(t) merupakan proses Markov dengan diagram transisi kondisi sebagai berikut
37
Persamaan kesetimbangan lokal
• Normalisasi
38
19
04/12/2012
Jadi distribusi pada kondisi setimbang adalah truncated binomial distribution:
• Offered traffic dinyatakan oleh kυ/(υ +µ)
39
Time Blocking
• Karena proses kedatangan tidak terdistribusi Poisson, maka pada model Engset, Time Blocking tidak sama dengan Call Blocking
40
20
