METODE INTERKONEKSI DUA JARINGAN DAN LETAK KONSENTRATOR
Metode interkoneksi dua jaringan 2
Algoritma terkait interkoneksi antara dua jaringan akan membentuk tree yang berfungsi untuk menghubungkan dua jaringan telekomunikasi yang berbeda.
Metode interkoneksi dua jaringan 3
Dengan menggunakan beberapa parameter pendukung, diantaranya adalah : trafik
eksternal dari masing-masing node, jarak antar node, dan bobot masing-masing node.
Metode interkoneksi dua jaringan 4
langkah metode interkoneksi sebagai berikut : 1.
Buat matrik untuk dua jaringan
2.
matrik incoming matrik outgoing
hitung trafik masing-masing node,
dengan cara menjumlahkan trafik incoming dan trafik outgoing masing-masing node. Sehingga akan didapat bobot (weight) dari tiap-tiap node. nodes
Z (t )
Wi * dij j 1
Metode interkoneksi dua jaringan 5
Menentukan nilai dari Zt untuk masing-masing node dalam kedua jaringan, dimana :
3.
Dipilih nilai Zt terkecil dari masing-masing jaringan.
Node yang memiliki Zt terkecil akan menjadi gateway dari dua jaringan tersebut.
Contoh
Terdapat 2 jaringan “disjoint” G1 dan G2. Trafik antara simpulsimpul dari G1 ke simpul-simpul G2 dan sebaliknya diketahui :
G1
a
G2
b c
d
1 4
2 3
5
6
Contoh: 7
Matrik eksternal:
1
2
3
4
5
∑
a
3
1
5
2
4
15
b
6
2
1
5
3
17
c
2
7
4
4
2
19
d
3
2
2
5
8
∑
14
12
12
16
17
20
a
b
c
d
∑
1
2
5
1
7
15
2
4
3
9
2
18
3
1
5
6
4
16
4
3
1
1
4
9
5
2
2
5
3
12
∑
12
16
22
20
contoh 8
Trafik dari dan ke : afa=15+12=27 bfb=17+16=33 cfc=19+22=41 dfd=20+20=40 1f1=15+14=29 2f2=18+12=30 3f3=16+12=28 4f4=9+16=25 5f5=12+17=29
Langkah selanjutnya:
Buat matriks jarak dari kedua jaringan untuk G1 matriks jarak d = 0 1 2 2 1 0 1 1 2 1 0 2 2 1 2 0
untuk G2 matriks jaraknya d = ? Cari Zt min untuk tiap node di G1 dan G2 Untuk G1 : Za = (fa*daa)+(fa*dab)+ (fa*dac)+(fa*dad) Zb= ?; Zc=?; Zd=? Untuk G2: Z1= (f1*d11)+(f1*d12)+(f1*d13)+(f1*d14)+(f1*d15) Z2 =?; Z3=?; Z4=?; Z5=?; Cari untuk G1 dan G2 node yang memiliki nilai Z terendah. Hubungkan node pada G1 dengan node pada G2 yang memiliki Zt terendah
Soal: tentukan interkoneksi dua jaringan berikut :
Diketahui dua jaringan disjoint G1 dan G2
G1
e
a
1
G2
b
4
d
c
2 3
5
• Matriks eksternal sbb: 1
2
3
4
5
a
5
7
2
4
3
b
6
2
6
1
c
4
3
8
d
4
6
e
5
7
∑
∑
a
b
c
d
e
1
3
6
7
3
2
5
2
5
3
1
3
4
6
6
3
2
7
9
3
6
9
3
2
4
4
7
3
7
9
2
8
5
5
6
8
2
6
5
∑
10
∑
Penentuan Letak Konsentrator 11
Diketahui sejumlah lokasi terminal, dimana lokasi terminal konsentrator yang optimal ? Penentuan konsentrator tergantung : Jumlah terminal yang harus dihubungkan kepadanya Besarnya trafik yang ditimbulkan oleh terminal Kapasitas link dan konsentrator
Penentuan Letak Konsentrator 12
Beberapa algoritma yang digunakan untuk menentukan letak konsentrator adalah : Dysart
- Georganas, Chandy Russel dan Essau william
Algoritma Dysart dan Georganas 13
Idenya memilih terminal yang dekat dengan terminalterminal lainnya. Algoritmanya adalah sebagai berikut : 1.
buat daftar dari N terminal dalam jaringan dan sejumlah k terminal yang paling dekat
2.
tentukan frekuensi pemunculannya untuk tiap terminal dalam daftar (1) tersebut
Algoritma Dysart dan Georganas 14
3.
tiap terminal mempunyai salah satu dari frekuensi pemunculan p yang terletak antara: p=1,2,......,F. Dimana F merupakan frekuensi pemunculan maksimum. Kelompokkan semua simpul ke dalam daftar S(p), p=1,2,...F. dimana daftar S(p) adalah daftar simpul-simpul yang mempunyai frekuensi pemunculan p.
Algoritma Dysart dan Georganas 15
4.
cari harga rata-rata frekuensi pemunculan ditambah 1, KM sebagai berikut: F
KM p 1
p.x( p) N
1
F=frekuensi pemunculan maximum Dimana x(p) adalah jumlah terminal didalam daftar S(P) N= jumlah node
Algoritma Dysart dan Georganas 16
5.
penentuan lokasi konsentrator pertama kali di dapat dari daftar S(F). Dapat ditambahkan terminalterminal dalam daftar S(P). Dimana KM ≤p≤F.
contoh Matrik jarak antar terminal 33 2
4 8 5
6 11
9
7
10
0
5
7
8
6
5
9
11
13
12
5
0
1
3
2
5
7
7
10
10
7
1
0
1
4
5
6
6
9
10
8
3
1
0
3
4
6
5
8
8
6
2
4
3
0
2
6
6
10
10
5
5
5
4
2
0
4
5
9
9
9
7
6
6
6
4
0
4
5
4
11
7
6
5
6
5
4
0
6
6
13
10
9
8
10
9
5
6
0
2
12
10
10
8
10
9
4
6
2
0
17
contoh 1.
Langkah 1buat daftar dari N terminal dalam jaringan dan sejumlah k terminal yang paling dekat. Misalkan k=3, maka Terminal 1 2 3 4 5 6 7 8 9 10
Daftar terminal dan sejumlah k tetangga terdekatnya 1,2,5,6 2,3,4,5 3,2,4,5 4,3,2,5 5,2,4,6 6,5,4,7 7,6,8,10 8,7,4,6 9,8,7,10 10,7,8,9 18
contoh 2. tentukan frekuensi pemunculannya untuk tiap terminal dalam daftar (1) tersebut
Terminal 1 2 3 4 5 6 7 8 9 10
Frekuensi pemunculan 1 5 3 6 6 5 5 4 2 3 19
contoh 20
3.
tiap terminal mempunyai salah satu dari frekuensi pemunculan p yang terletak antara: p=1,2,......,F. Dimana F merupakan frekuensi pemunculan maksimum. Kelompokkan semua simpul ke dalam daftar S(p), p=1,2,...F. dimana daftar S(p) adalah daftar simpul-simpul yang mempunyai frekuensi pemunculan p.
contoh 21
S(i):
daftar (lokasi) terminal dengan urutan frekuensi pemunculan i. S(1)
= (1) S(2) = (9) S(3) = (3,10) S(4) = (8) S(5) = (2,6,7) S(6) = (4,5) --- ini pertama kali diambil sebagai pilihan
contoh 22
KM
1 2 6 4 15 12 1 5 10
Lokasi konsentrator dapat ditambah sebagai pilihan : (2,4,5,6,7)
soal 23
5
1
Diketahui matrik jarak beberapa terminal adalah sbb, tentukan letak dari konsentrator dengan algoritma dysart & georganas 2
3 4 6 7
8
1
2
3
4
5
6
7
8
1
0
4
2
5
1
7
8
8
2
4
0
3
2
5
8
8
6
3
2
3
0
4
4
4
5
7
4
5
2
4
0
6
7
6
5
5
1
5
4
6
0
7
8
9
6
7
8
4
7
7
0
2
9
7
8
8
5
6
8
2
0
8
8
8
6
7
5
9
9
8
0
soal 1.
24
Langkah 1buat daftar dari N terminal dalam jaringan dan sejumlah k terminal yang paling dekat Terminal
Daftar terminal dan sejumlah k tetangga terdekatnya
1 2 3 4 5 6 7 8
1,5,3 2,4,3
soal 2. tentukan frekuensi pemunculannya untuk tiap terminal dalam daftar (1) tersebut Terminal 1 2 3 4 5 6 7 8
25
Frekuensi pemunculan
contoh 3.
tiap terminal mempunyai salah satu dari frekuensi pemunculan p yang terletak antara: p=1,2,......,F. Dimana F merupakan frekuensi pemunculan maksimum. Kelompokkan semua simpul ke dalam daftar S(p), p=1,2,...F. dimana daftar S(p) adalah daftar simpul-simpul yang mempunyai frekuensi pemunculan p. –
S(i): daftar (lokasi) terminal dengan urutan frekuensi pemunculan i. • • • • • •
26
S(1) = S(2) = S(3) = S(4) = S(5) = S(6) =
contoh KM
?
Lokasi konsentrator dapat ditambah sebagai pilihan : ………….
27
Algoritma Chandy-Russel 28
Pertama dicari “spanning tree” yang minimum tanpa kendala. Bila hasil ini dengan kendala “feasible”, maka ini optimum dan algoritma berhenti. Bila tidak, diteruskan dengan membagi dalam subset.
Langkah Algoritma Chandy-Russel sebagai berikut : 29
1. bagi set semua solusi ke dalam 2 subset. Satu subset memasukkan semua link dari solusi tanpa kendala yang terhubungkan ke lokasi konsentrator dan subset yang lainnya tanpa hubungan ini dan tak usah dilihat lagi.
2. dalam proses pembagian ke i: subsetnya adalah Si(1),Si(2),.....Si(p) dan harga batas paling bawah dari biaya adalah Li(1),....,Li(p). Misalkan Li(j) adalah harga terendah dalam Li(k),k,....,p.
Langkah Algoritma Chandy-Russel sebagai berikut : 30
3.
cek subset Si(j) apakah solusinya “feasible”. Bila “feasible maka ini berarti solusi optimum pula karena ini merupakan batas terendah Li(j) dan algoritma berhenti. Bila tidak, diteruskan ke langkah (4).
4.
labelkan lagi set j ke set k. Bagi Si(k) ke dalam Si+1(k) dan Si+1(k+1).pembagian ini diperoleh dengan cara memasukkan satu link bebas kedalam si(k) sehingga menjadi subset si+1(k) dan tanpa link tersebut menjadi subset Si+1(k+1). Hitung batas bawah yang baru dalam solusi Li+1(k) dan Li+1(k+1) dan teruskan ke langkah (2).
contoh Matrik biaya C
M5=1 M4=2 M2=2
Simpul
1
2
3
4
5
1
-
3
3
5
10
2
3
-
6
4
8
3
3
6
-
3
5
4
5
4
3
-
7
5
10
8
5
7
-
5 4 M3=3
2 3 1 konsentrator
Kendala : Kapasitas link = 5 pesan (message) per satuan waktu. Dicari “spanning tree” minimum: 31
Penyelesaian contoh 32
M4=2
5 4
M5=1
2
M2=2 2
3
2 1
M3=3
6
konsentrator
Ternyata tidak “feasible”: link (1,3) terdapat 6 message/satuan waktu. Subset A = termasuk link 2-1 dan 3-1 Subset B = tidak termasuk paling sedikit satu dari dua link (2-1,3-1)
33
Karena Subset A memuat link yang menghubungkan terminal langsung ke konsentrator, maka subset A berisi solusi yang diinginkan subset B dapat dihilangkan. Algoritma diteruskan dengan berturut-turut memasukkan link yang masih bebas dan mempertimbangkan semua pilihan yang mungkin.
34
Link yang ditambahkan adalah link yang masih bebas, yaitu link yang belum belum dimasukkan atau “not allowed” dalam suatu subset. Maka algoritma diteruskan dengan, misalnya memasukkan link 4-3 kedalam satu subset dan tak boleh dimasukkan ke dalam subset yang lainnya. Maka subset yang baru:
AA = 2-1, 3-1,, 4-3 AB = 2-1,3-1, link terlarang 4-3
35
Dilihat AA:
Aliran trafik di link 3-1 berisi trafik dari terminal 4 dan 3, jadi sebesar 5 message. Oleh karena itu terminal 5 tak dapat dihubungkan ke terminal 4 ataupun 3 karena akan menaikkan trafik di link 3-1. dengan demikian dapat dipakai link 5-2 atau5-1. karena biaya link 5-2 lebih murah daripada link 5-1, maka yang dipilih adalah link 5-2.
[ biaya link 5-1 = 10 sedangkan link 5-2=8]
Maka biaya total = C(2,1)+C(4,3)+C(3,1)+C(5,2) = 17 satuan
SUBSET AB 36
Dengan
memakai matriks biaya yang mula-mula akan didapat biaya : C(1,2)
Jadi
+ C(3,1) + C(4,2) + C(5,3) = 15
subset AB ini lebih murah dari pada subset AA. Karena subset AB biaya paling rendah dan „feasible” langkah harus diteruskan dengan subset AB
37
5
5
4
4
2
2 3 1 Biaya total = 17 satuan
3 1 Biaya total = 15 satuan
Algoritma Esau-William 38
Algoritma Esau-William merupakan salah satu algoritma yang digunakan untuk penyelesaian masalah capacitaced minimum spanning tree (CMST). CMST merupakan masalah yang sangat penting dalam mendesain jaringan telekomunikasi. Dalam masalah ini, diperlihatkan bahwa sebuah sentral processor (konsentrator/root/source node) dan beberapa set remote terminal (node selain konsentrator) dengan permintaan trafik tertentu yang mengharuskan adanya aliran antara central processor dan terminal.
Algoritma Esau-William 39
Tujuannya adalah membuat jaringan dengan biaya minimal yang dapat memuat permintaan tersebut.
Algoritma Esau-William 40
algoritma Esau-William adalah algoritma yang digunakan untuk menentukan suatu konfigurasi yang dianggap cost paling minimum dengan memperhatikan kapasitas maximal tiap linknya.
Algoritma ini mula-mula menghubungkan semua terminal dengan konsentrator. Kemudian mencoba link antar terminal (dan link antar terminal dengan konsentrator dihilangkan ) yang memaksimumkan pengurangan biaya.
Algoritma Esau-William 41
Prosedure dari algoritma Esau-William ini yaitu : Hitung parameter “tradeoff” d(i,j)
= cost(i,j) – cost (i, center),
untuk semua i,j, dimana center adalah lokasi konsentrator/processor central.
Algoritma Esau-William 42
Jadi, algoritma mencari pertama-tama selisih biaya (jarak) hubungan antara tiap simpul i dengan simpul j (simpul lain) dan simpul i tersebut dengan konsentrator.
Algoritma Esau-William 43
Prosedure
dari algoritma Esau-William (cont)
Bila
d(i,j) > 0 maka tak dipertimbangkan, karena c(i,center) akan lebih murah dari c(i,j).
Bila
d(i,j) < 0, pilih d(i,j) berurutan mulai dari yang minimum dan diperiksa apakah aliran trafik memenuhi kendala (kapasitas trafik ) bila link (i,center) ditiadakan dan i dihubungkan ke j.
contoh 44
4m/d 5m/d
• Matrik biaya
3 4
2 1
5
3m/d
5m/d
1
2
3
4
5
1
-
6
3
4
5
2
6
-
3
5
7
3
3
3
-
3
5
4
4
5
3
-
3
5
5
7
5
3
-
Node 1 sebagai konsentrator Kapasitas maksimum tiap link = 10 message/dtk
contoh 45
Algoritma essau william ini mula-mula menghubungkan semua terminal dengan konsentrator.
4m/d 5m/d
3 4
2 1
5
3m/d
5m/d
contoh
Hitung parameter “tradeoff” d(i,j) = c(i,j) – c (i, 1), untuk semua i,j, dimana 1 adalah konsentrator.
mencari selisih biaya (jarak) hubungan antara tiap simpul i dengan simpul j (simpul lain) dan simpul i tersebut dengan konsentrator.
46
– – – – – – – – – – – –
d(2,3)=c(2,3)-c(2,1)=3-6=-3 d(3,2)=c(3,2)-c(3,1)=3-3=0 d(2,4)=c(2,4)-c(2,1)=5-6=-1 d(4,2)=c(4,2)-c(4,1)=5-4=1 d(2,5)=c(2,5)-c(2,1)=7-6=1 d(5,2)=c(5,2)-c(5,1)=7-5=2 d(3,4)=c(3,4)-c(3,1)=3-3=0 d(4,3)=c(4,3)-c(4,1)=3-4=-1 d(3,5)=c(3,5)-c(3,1)=5-3=2 d(5,3)=c(5,3)-c(5,1)=5-5=0 d(4,5)=c(4,5)-c(4,1)=3-4=-1 d(5,4)=c(5,4)-c(5,1)=3-5=-2
1
2
3
4
5
1
-
6
3
4
5
2
6
-
3
5
7
3
3
3
-
3
5
4
4
5
3
-
3
5
5
7
5
3
-
47
contoh 48
Bila d(i,j) > 0 maka tak dipertimbangkan, karena c(i,center) akan lebih murah dari c(i,j).
Bila d(i,j) < 0, pilih d(i,j) berurutan mulai dari yang minimum dan diperiksa apakah aliran trafik memenuhi kendala (kapasitas trafik ) bila link (i,center) ditiadakan dan i dihubungkan ke j.
– – – – – – – – – – – –
d(2,3)=c(2,3)-c(2,1)=3-6=-3 d(5,4)=c(5,4)-c(5,1)=3-5=-2 d(2,4)=c(2,4)-c(2,1)=5-6=-1 d(4,3)=c(4,3)-c(4,1)=3-4=-1 d(4,5)=c(4,5)-c(4,1)=3-4=-1 d(3,2)=c(3,2)-c(3,1)=3-3=0 d(3,4)=c(3,4)-c(3,1)=3-3=0 d(5,3)=c(5,3)-c(5,1)=5-5=0 d(4,2)=c(4,2)-c(4,1)=5-4=1 d(2,5)=c(2,5)-c(2,1)=7-6=1 d(5,2)=c(5,2)-c(5,1)=7-5=2 d(3,5)=c(3,5)-c(3,1)=5-3=2
contoh 49
Dari contoh di atas d(2,3)=-3 adalah minimum Hilangkan
link (2,1) dan adakan link (2,3) Cek aliran trafik Link(2,3)=5 Link(3,1)=5+4=9<10 jadi masih memenuhi kendala
Berikutnya
link (5,4)d(5,4)=-2
50
Cek aliran trafik link(5,4)=5 Link (4,1)=5+3=8<10 Jadi memenuhi kendala
Berikutnya link(4,3) dan(2,4), bila dicek tidak memenuhi kendala.
Jadi jumlah total biaya=c(3,1)+c(2,3)+c(1,4)+c(4,5)=3+3+4+3=13 satuan
contoh 51
4m/d 5m/d
3 4
2 1
5
3m/d
5m/d
• Node 1 sebagai konsentrator • Kapasitas maksimum tiap link = 10 message/dtk
soal 2m/d 3m/d
• Matrik biaya
4 1
5 3
2
1m/d
4m/d
1
2
3
4
5
1
-
9
5
8
7
2
9
-
5
7
11
3
5
5
-
5
7
4
8
7
5
-
6
5
7
11
7
6
-
• Konsentrator di node 3 • Kapasitas maksimum tiap link = 6 message/dtk 52
Penyelesaian soal
Hitung parameter “tradeoff” d(i,j) = c(i,j) – c (i, 3), untuk semua i,j, dimana 3 adalah konsentrator.
d(1,2)=c(1,2)-c(1,3)=5-7=-2 d(2,1)=c(2,1)-c(2,3)=5-5=0 d(1,4)=c(1,4)-c(1,3)=8-7=1 d(4,1)=c(4,1)-c(4,3)=8-5=3 d(1,5)=c(1,5)-c(1,3)=7-7=0 d(5,1)=c(5,1)-c(5,3)=7-7=0 d(2,4)=c(2,4)-c(2,3)=7-5=2 d(4,2)=c(4,2)-c(4,3)=7-5=2 d(2,5)=c(2,5)-c(2,3)=11-5=6 d(5,2)=c(5,2)-c(5,3)=11-7=4 d(4,5)=c(4,5)-c(4,3)=6-5=1 d(5,4)=c(5,4)-c(5,3)=6-7=-1
1
2
3
4
5
1
-
5
7
8
7
2
5
-
5
7
11
3
7
5
-
5
7
4
8
7
5
-
6
5
7
11
7
6
-
2m/d 3m/d
4
1
5 3
2 53
1m/d
4m/d
HAPPY LEARNING!
