H2
S2 S3S8
S1S4
S9 S10
S5S6 S7
S11
H1
H8
H3
H4
H9
H10
H5
H6
H7
H11
controller
collector Metric calculation
Route calculation
Rate calculation
Flow management
BAB 3
MODEL DAN PERANCANGAN SISTEM
Bab ini juga berisi rancangan sistem yang meliputi arsitektur jaringan dan ........ Bab ini
bertujuan untuk memaparkan model jaringan dan model antrian yang digunakan untuk
mekanisme multipath routing dan adaptasi laju data. Model ...... ini diselesaikan dengan
pemrograman linear dan solusinya dapat digunakan untuk membangun flow forwarding tabel
dalam protokol routing dan penentuan alokasi laju pengiriman.
3.1 Perancangan Aplikasi SDN
Rancangan sistem meliputi rancangan topologi jaringan pada data plane dan rancangan
aplikasi SDN. Rancangan sistem ini diimplementasikan dalam controller Ryu dan
disimulasikan dalam mininet yang memungkinkan pengguna menggunakan beberapa topologi.
Rancangan sistem terdiri dari beberapa bagian seperti pada gambar 3.1, terdiri dari beberapa
proses yaitu: pengumpulan data-data kondisi jaringan, perhitungan kondisi jaringan, pemilihan
rute dan alokasi data rate.
Gambar 3.1: Blok rancangan sistem
-
1
Untuk menjalankan beberapa proses pada gambar 3.1, maka diperlukan modul-modul
sebagai berikut:
- Kolektor: modul kolektor digunakan untuk mengumpulkan informasi tentang kondisi
jaringan global, dan bertanggung jawab untuk menyimpan semua informasi. Informasi
topologi jaringan, lalu lintas jaringan dan kondisi atau keadaan masing-masing perangkat
dll. controller meminta berbagai data kondisi jaringan dari switch dengan mengirimkan
pesan feature_request, dan switch mengirimkan pesan feature_reply berisi data yang
diminta. Mekanisme ini dijelaskan secara rinci dalam spesifikasi OpenFlow [17].
- Perhitungan metrik: modul perhitungan metrik digunakan untuk menentukan parameter
cost tiap link yang akan digunakan untuk menentukan routing dan laju data dan menyimpan
semua kemungkinan jalur masing-masing pasangan switch.
- Perhitungan Rute: modul perhitungan rute digunakan untuk menghitung jalur terpendek
dan jalur alternatif antara sumber dan tujuan. Perhitungan rute dilakukan ketika pesan
packet_in datang ke controller.
- Perhitungan laju data: modul perhitungan laju data digunakan untuk menghitung service
rate. Sebagaimana ditentukan dalam spesifikasi OpenFlow, setiap flow switch OpenFlow
berisi sekumpulan instruksi yang dijalankan ketika sebuah paket entri yang sesuai tiba.
Salah satu jenis instruksi adalah meter yang mengarahkankan paket ke meter tertentu. Setiap
meter memiliki satu atau lebih meter band.
- Manajemen flow: modul manajemen flow bertanggung jawab untuk menentukan jalur
setiap flow dan menginstal aturan/flow entry ke datapath atau switch. Fungsi ini
bertanggung jawab untuk mengatur flow yang efisien dengan mendistribusikan trafik.
3.2 Mekanisme routing dan alokasi rate terpusat
Prinsip dari routing dan alokasi rate terpusat seperti ditunjukkan pada gambar 3.2. Setiap
terdapat permintaan layanan dari sebuah flow maka controller SDN akan memeriksa sumber
daya yang tersedia. Jika terdapat sumber daya jaringan, maka flow akan diterima dan
Controller menghitung dan mengevaluasi besarnya sumber daya yang dapat diberikan ke flow
tersebut. kemudian controller menentukan sebuah path dari sumber sampai tujuan yang
diperuntukan untuk flow tersebut. pemilihan path didasarkan pada informasi kondisi jaringan
yang dikumpulkan oleh controller. Informasi ini secara reguler dikirimkan oleh switch ke
controller. Disamping melakukan pemilihan path, controller juga menghitung ketersediaan
2
tidak
tidak
flow baru
?
Trafik masukan
ya
Pencocokan paket dengan flow yang
ada
Kebijakan dari controller
Antrian untuk flow
Admission control
Ada
jaminan bandwidth
?
Fair queuing Fix rate
ya
Flow ditolak
Routing
sumber daya path tersebut dan menginformasikannya kepada switch. Informasi sumber daya
berupa agregat rate pada sebuah path yang juga merupakan kemampuan path untuk melayani
flow yang masuk. Berdasarkan agregat rate pada path maka dapat ditentukan besarnya rate
untuk sebuah flow.
Gambar 3.2: mekanisme routing dan alokasi rate terpusat
Pada mekanisme routing pada aplikasi ini, hasil pencarian routing disimpan di routing tabel
T. semua kemungkinan path dan informasi jaringan disimpan dalam modul (database) sehingga
kontroler tidak menjalankan algoritma routing online. Controller melakukan pengaturan routing
berdasarkan jalur yang sudah tersimpan. Penentuan routing hanya dilakukan di node ingress dan
node intermediate hanya melakukan fowarding. Controller tidak menghitung path untuk setiap
permintaan flow tetapi menggunakan informasi yang sudah tersedia
3. 2.1 Pemilihan routing
Pada bagian ini kami menyajikan skema pemilihan routing terdiri untuk menentukan
beberapa jalur. Algoritma untuk menemukan rute berdasarkan jalur routing terpendek dan
terdapat pra-pembentukan jalur atau dukungan untuk sumber rute. Rute yang ditemukan adalah
satu rute terpendek (terbaik) dan beberapa rute alternatif. Pada awalnya flow dilewatkan pada
path terbaiknya, ketika controller mendeteksi adanya kemacetan di sebuah link pada path
3
terbaik maka trafik akan didstribusikan ke path alternatif sesuai dengan utilitas path sehingga
dapat menghindari kemacetan jaringan. Controller menghitung utilitas setiap node s pada data
plane jaringan. Kemacetan terdeteksi pada link sebuah path jika utilitasnya melebihi ambang
kemacetan β , misalnya, β = 95%. Tujuan pembatasan ini untuk menjaga utilitas ke tingkat
yang masih bisa diterima oleh jaringan (tidak menyebabkan turunnya kinerja jaringan).
Prosedur untuk pemilihan routing dan distribusi trafik pada multipath routing digambarkan
pada gambar 3. ....dengan penjelasan sebagi berikut :
- Ketika ada flow baru datang ke jaringan, controller Mencari kemungkinan lintasan terbaik
dari sumber ke tujuan menggunakan algoritma DFS ( ) untuk pencarian jalur terbaik dan
jalur alternatif, dimana rute terbaik adalah :
Pi best=max {Rbw pi|Pi∈P od }
Ketika controller mendeteksi kemacetan di sebuah link pada sebuah path yang
menyebabkan utilitas path (l)> β, controller memindahkan trafik ke path alternatif yang
menghindari link ini. Path alternatif ditentukan dengan menggunakan Algoritma 1.
Controller mendistribusikan trafik melalui m path menurut rasio splitting φ, dimana ϕ
ditentukan pada persamaan :
Algoritma load balancing bertujuan untuk menghitung beban yang adil dari setiap path
yang sudah terpilih. Trafik yang dilewatkan ke tiap path proporsional dengan beban path
dengan algoritma sebagai berikut :
Rpi=
ρpi
∑j=1
n
ρp j
x Rtot
Controller akan terus membagi trafik ke beberapa jalur alternatif sesuai dengan utilitas
path selama masih dibawah threshold. Paket akan terus dikirimkan ke lintasan ini sampai
mencapai target utilisasi path alternatif (ε). Dimana 0 < ε < 1
Skema routing mengontrol utilitas dengan 3 parameter yang dapat diatur oleh controller:
α adalah sebuah parameter yang menunjukkan bahwa link atau path terjadi
kemacetan. Misalnya (α = %)
β Sebuah parameter yang menunjukkan apakah jalur alternatif dapat menerima trafik
atau tidak. Parameter ini untuk memastikan bahwa path alternatif dapat menyediakan
bandwidth
ϕ sebuah parameter yang menunjukan ekspektasi dari utilitas path.
4
Gambar 3.3 : Mekanisme pemilihan jalur
3.2.1 Deteksi kongesti
Untuk mendeteksi kongesti mekanisme routing mengunakan kondisi path. Kondisi
beban path menggambarkan seberapa macet path tersebut. jika beban path melebihi ambang
batas maka mengindikasikan kongesti. Parameter yang diamati sebagai informasi yang
diperlukan untuk deteksi kongesti adalah sebagai berikut :
jumlah paket yang ditransmisikan pada switch
ukuran paket
5
RTT (round trip time)
Jumlah hop
kapasitas link
Status kongesti : panjang antrian, packet loss, utilitas, delay
3.2.2 Komposisi cost metric
Metric routing terintegrasi dalam protokol routing untuk meningkatkan kualitas
komunikasi dalam hal bandwidth, kesalahan laju pengiriman, latency, keandalan, dan biaya.
Oleh karena itu desain metric routing merupakan hal yang sangat penting. Pada sistem ini
metric yang digunakan merupakan integrasi dari beberapa informasi yaitu beban trafik dan
delay dan diinginkan parameter tersebut mempunyai nilai seperti pada tabel 3.1 berikut :
Tabel 3.1. Parameter Cost Metric
parameter notasi tingkat
Utilitas link L rendah
Kapasitas link C tinggi
delay RTT rendah
Utilitas switch Q rendah
Dari pertimbangan nilai yang diinginkan diperoleh sebuah persamaan :
Cong(i , j)=α .L(i , j )+ β . RTT +γ . Q(i )
δ .C
3.2.3 Admission control
Pada SDN, kelebihan beban dapat terjadi pada data plane dan control plane. Oleh karena
itu perlu diperhatikan pembatasan flow yang masuk dari parameter control plane dan data plane.
Dari parameter control plane, kelebihan beban pada controller akan mengakibatkan waktu
pemrosesan yang lama. Hal ini dapat menyebabkan pengendalian jaringan akan terganggu, salah
satu contohnya adalah flow setup. Flow set up diperuntukan untuk untuk sebuah flow yang
baru datang ke sebuah jaringan SDN. Waktu yang diperlukan untuk flow set up dipengaruhi
oleh faktor-faktor antara lain: banyaknya trafik yang masuk ke switch, trafik yang masuk ke
controller, kapasitas controller dan algoritma yang digunakan untuk menentukan aturan sebuah
flow [ ]. Mekanisme admission control ditunjukan pada gambar 3.4.
6
Gambar 3.4 : mekanisme admission control
3.2.4 Alokasi rate
Mekanisme penyesuaian rate seperti ditunjukan pada gambar 3. 5. Secara umum
penyesuaian laju kedatangan flow dilakukan ketika terjadi kongesti di sebuah path. Ketika
controller mendeteksi adanya kemcetan pada sebuah path, maka controller akan memberikan
informasi kepada ingress switch untuk menyesuaikan laju pengiriman.
7
Gambar 3.5: alokasi rate
Mekanisme dasar untuk merancang skema pengendalian kemacetan PACEC, terdiri dari
fungsi keputusan, fungsi penyesuaian rate, dan frekuensi keputusan.
b. Fungsi keputusan
Fungsi keputusan membantu pengendali rate untuk menentukan penyesuaian agregat Rate
pada router ingress. Dalam PACEC ,controller memonitor available bandwidth. Pengendalian
kemacetan dipicu saat keterseidaan bandwith mencapai ambang batas tertentu. Setiap interval
waktu t, controller mengolah informasi global jaringan dan menginformasikan ketersediaan
bandwidth ini ke ingress router.
c. Fungsin penyesuaian rate
Pada router ingress , diterapkan algoritma penyesuaian rate yang berfungsi untuk
meningkatkan dan menurunkan agregat rate pengiriman sbb:
d. Frequency keputusan
Frekuensi keputusan menentukan seberapa sering untuk mengubah rate. Di skema PACEC,
ketika router ingress menerima informasi dari controller, maka sumber mengubah rate sesuai
dengan fungsi penyesuaian rate. frekuensi keputusan PACEC ditentukan oleh seberapa sering
8
controller
Ingress switch Egress switchcore switch
router ingress menerima informasi dari controller. frekuensi keputusan atau t pada PACEC
diatur ke RTT antara ingress dan egress routers dalam kasus tidak ada kemacetan.
3.3 Model
3. 3.1 Topologi jaringan
Pada desertasi ini, Kami mempertimbangkan topologi jaringan yang ditunjukan pada gambar
3.6 yang terdiri dari user, edge switch yang terdiri dari switch ingress dan egress dan core
network yang terdiri dari core switch. Edge switch terletak pada batas jaringan untuk
menyediakan dukungan klasifikasi trafik, pembatasan laju pengiriman dan core switch yang
berada di dalam jaringan untuk menyediakan fungsi forwarding. Semua switch terhubung ke
controller.
Gambar 3.6 : Topologi jaringan
3. 3.2 Model Jaringan sebagai graph
Jaringan dimodelkan sebagai graph G (S ,L ) seperti ditunjukan pada gambar 4.2, sebuah
node yang dikaitkan untuk setiap router atau switch dan edge berarah untuk setiap link berarah
yang secara fisik menghubungkan setiap node. Dengan demikian, S adalah satu set node dan L
adalah himpunan link berarah. S= {s i } adalah kumpulan dari node dan L= {li }, adalah kumpulan
9
p3
p2
p1
o d
5
4
1
6
3
2
dari link. Link li=( si , s j ) adalah sebuah pasangan node, dimana si adalah outgoing node dan sj
adalah incoming node.
Gambar 3.7 : Jaringan Data Plane Sebagai Graph Berarah G (S , L )
Asumsi terdapat N path antara sepasang sumber-tujuan. Jika o adalah node sumber dan d
adalah node tujuan, maka P (o , d ) adalah seluruh rute dari o ke d, P (o , d )= {P1 ,… .. , PN }. asumsi
bahwa path-k (k=1 , …. , N ) terdiri dari li intermediate node, maka :
Pk= {o , s i , s j ….. , d }
Pk= {li }
Diasumsikan setiap link li mempunyai kapasitas sebesar C i. Kapasitas dari sebuah path
adalah C p dan merupakan kapasitas minimum dari semua link yang menyusun sebuah path
dari sumber sampai tujuan. Jika kapasitas tiap link adalah C i, maka kapasitas sebuah path
adalah kapsitas minimum dari semua link yang membentuk path tersebut.
CP=min {Ci }
3. 3.3 Model Jaringan sebagai antrian
Pada desertasi ini model jaringan openflow seperti digambarkan pada Gambar 3.8 switch dan
controller dimodelkan sebagai node antrian untuk menghitung delay pada perangkat ini. Asumsi
proses kedatangan paket di jaringan mengikuti proses Poisson dan laju kedatangan rata-rata di
10
λf1
μc
Ingress node Egress nodeIntermediate node
SDN controller
Flow arrival
λtotμs1
λc
S1 μsk
Flow levelPacket level
Flow size = z packet
Packet size = x bit
μsk-n
Sk-n Sk
Packet in Packet in
Packet out
Packet out
Packet out
switch s adalah λs, dan bahwa kedatangan di switch yang berbeda adalah independen. Paket
yang datang dan tidak cocok dengan flow entry akan diteruskan ke controller melalui pesan
paket-in.
Paket yang datang dari sebuah flow ke switch diklasifikasikan menjadi dua kategori, pertama
adalah paket yang datang dari flow baru (fnew) dan paket dari flow telah mempunyai flow table
(fold). Keduanya tiba dengan proses Poisson dengan laju kedatangan rata-rata λnew dan λold. waktu
pelayanan switch diasumsikan untuk mengikuti distribusi general, dan waktu pelayanan yang
diharapkan di switch adalah 1/μs. Waktu pelayanan rata-rata pesan paket-in di controller
dilambangkan 1/μc. waktu pelayanan ini termasuk waktu transmisi dari switch ke controller.
Untuk menyederhanakan model ini, baik controller dan switch dianggap tidak ada batasan
kapasitas antrian. untuk layanan tunggal, semua paket tiba di sebuah switch dalam antrian
tunggal bukan antrian terpisah pada setiap port ingress dan semua paket diproses dalam urutan
waktu kedatangan (FIFO). Selain itu, kami beranggapan bahwa ketika paket pertama tiba di
switch, controller menginstal flow entri. Setelah itu, paket-paket yang tersisa tiba ke switch dan
diteruskan langsung. semua switch dalam model ini dianggap memiliki service rate yang sama,
dan pesan paket-in tiba di switch mengikuti proses Poisson.
Gambar 3.8: Model antrian jaringan SDN
a. Waktu menunggu di switch
11
Asumsi bahwa waktu pelayanan di switch terdistribusi general, dan kedatangan flow adalah
poisson, maka waktu menunggu di switch dimodelkan sebagai M/G/1. Jika laju kedatangan di
switch adalah λs dan laju pelayanan di switch adalah μs, dan
ρ s=λs
μs , maka waktu rata-rata menunggu di setiap switch dapat ditentukan dengan persamaan
berikut :
Mean dan varian dari waktu tunggu di switch adalah sebagai berikut :
(cek lagi )
mean
α s=ρ
2(1−ρ). E[P2]
E [P]
varian
σ s=√ [ ρs
2(1− ρs). E[P2]
E [P] ]2
+ρs
3 (1−ρ s)E[P3]E [P]
Dimana ρ adalah..... dan E[P] adalah ..., Jika cv adalah koefisien variasi, yaitu perbandingan
men dan varian
cv=αs
σ s
rata-rata waktu tunggu ( waktu antrian) untuk antrian M / G / 1 dapat dinyatakan sebagai :
W q=[1+cv2 ][ ρs
1−ρs ] t s
ρ=λ t s
Dimana : ts= 1/μs
Dari pengukuran empiris, Hasil kami menunjukkan bahwa model M / G / 1 dengan log-normal
Model campuran untuk memodelkan delay end-to-end di Jaringan OpenFlowenabled
lebih akurat
Ref :
[01x] Analytical Modeling of End-to-End Delay in OpenFlow Based Networks Azeem Iqbal, Uzzam Javed, Saad Saleh, JongWon Kim, Jalal S. Alowibdi, Muhammad Usman Ilyas, Senior Member, IEEE
12
Paket dari flow baru
controller
flow baru
Packet inPacket out
b. Model kedatangan paket di controller
Ketika sebuah switch menerima paket, switch menempatkan paket tersebut ke dalam antrian
paket di port masuk. Kemudian switch akan mengecek paket pertama dan mencocokan dengan
flow table. Jika hasil pencocokan gagal maka switch mengirimkan message paket-in yang
mengandung paket penuh ke controller SDN. controller akan menangani dan memberikan
keputusan paket tersebut dan akan mengirimkan ke switch dan ditambahkan ke flow table
switch yang bersesuaian. Karena pencarian flow table untuk semua paket adalah saling bebas
satu sama lain, maka waktu pemrosesan paket dapat dianggap sebagai variabel acak. Dengan
asumsi tersebut maka antrian di controller pada penelitian ini dimodelkan dengan M/G/1.
Jika flow datang pada sebuah switch dengan rata-rata laju kedatangan λtot flow per satuan
waktu. Sebagian flow yang datang adalah flow baru dan paket pertama dari flow baru yang
datang ke switch akan dikirimkan ke controller untuk meminta inisiasi flow. Jika rata-rata
kedatangan flow baru adalah λbaru= φ. λtot maka packet-in yang datang ke controller sama dengan
laju kedatangan flow baru. Flow datang pada sebuah switch mengikuti proses poisson oleh
karena itu packet in yang datang ke controller diasumsikan mengikuti pola kedatangan poisson
juga.
rata-rata laju kedatangan packet in dari ke controller sebuah switch adalah λc❑ dimana
λc❑=φ . λ totpacket per satuan waktu.
Gambar 3..9: proses inisiasi
Asumsi bahwa packet in yang ditimbulkan oleh flow baru setiap switch adalah λc❑ maka packet in yang
datang secara keseluruhan jika terdapat K switch adalah :
λc=∑i=0
k
λci
13
Dimana λc merupakan rata-rata laju kedatangan permintaan inisiasi flow dari semua switch
yang terhubung ke controller.
c. Waktu menunggu di controller
Lama waktu pelayanan diasumsikan mempunyai distribusi tertentu (umum) dengan rata-rata
waktu pelayanan di controller adalah t c dan laju pelayanan di controller sebesar μc .Waktu
menunggu di controller (W qc ¿ ....
ρc=λc
μc
α k=ρc
2(1− ρc). E [P2]
E[P]
σ k=√[ ρc
2(1−ρ c). E [P2]
E[P] ]2
+ρc
3(1−ρ)E[P3]E [P]
Secara umum, jika kita ingin waktu tunggu rata-rata menjadi tidak lebih dari t menit, maka
kita dapat menghitung laju kedatangan maksimum yang diijinkan (λ) sebagai berikut:
W qc=[ 1+cv2 ][ ρ c
1−ρc ]t c<t
Rata-rata respon time di controller dapat diestimasi dengan model antrial M/G/1 [ ]:
E [r ]=E [e ]+E [e ] ρ (1+cv2 )2 (1−ρc )
Dimana E [e ] adalah rata-rata waktu eksekusi, ρ intensitas beban cv koefisien variasi
(perbandingan standar deviasi dengan mean) dari waktu ekseskusi permintaan
d. End to end delay
14
Delay antrian pada path end-to-end diasumsikan bahwa semua independen satu sama lain.
Hal ini dapat dibenarkan oleh fakta bahwa agregat flow trafik terpecah pada setiap node dan
bercampur dengan trafik yang tiba dari sumber lainnya. Asumsi independensi telah divalidasi
dalam (Kruskal et al, 1984), (Lau et al, 1997) dan (Van Den Berg et al, 1995). Delay dari
sebuah link dapat dinyatakan sebagai penjumlahan dari delay propagasi (d p), delay forwarding
paket (d f ), dan delay antrian (dq), seperti yang ditunjukkan pada Persamaan. (1).
d=d¿+d f+dq
parameter kedua dan ketiga dalam Pers. (.... ) merupakan variabel tergantung pada bandwidth
dan kebijakan antrian di path p, sementara Dp adalah konstan tergantung pada sifat fisik dan
panjang path. asumsi bahwa kedatangan paket mengikuti proses Poisson dengan waktu
pelayanan eksponensial dan setiap antrian adalah dilengkapi buffer yang tak terbatas dan
disiplin pelayanan adalah FCFS , maka Dq dapat diturunkan dari analisis antrian M/G/1 .
Ketika sebuah koneksi flow dalam kelas f dirutekan sepanjang path Pi, maka berdasarkan model
jaringan M/G/1 tandem, mean dan varian delay setiap link DLi ditentukan menggunakan formula
[ ] :
Jika delay setiap link i adalah DLi, maka delay dalam sebuah path adalah :
D p=∑i=1
n
DL i
Menurut teorema limit pusat dan pengukuran data dari trafik internet, kita tahu bahwa end to
end path delay, yang terdiri dari sejumlah besar independen delay dalam antrian intermediate,
terdistribusi normal. Dari hasil di [02x] mean dan dan varians dari delay end-to-end dari path -
j adalah :
α s=Nρs
2(1− ρs). E[P2]
E [P]
σ s=√N √[ ρs
2(1−ρs). E [P2]
E[P] ]2
+ρs
3(1− ρs)E [P3]E[P]
15
3. 3.4 Model Routing
Masalah routing dalam jaringan adalah bagaimana mencari jalan atau beberapa jalur untuk
mengirimkan trafik melalui jaringan tanpa melebihi kapasitas link. Pada penelitian ini,
menggunakan proses seleksi jalur informasi tentang ketersediaan bandwidth. Dengan
mempertimbangkan topologi jaringan G (S ,L ), semua koneksi diasumsikan menggunakan
sumber o∈S dan tujuan d∈S yang sama dan mengalami delay sebesar Di untuk setiap link.
Setiap flow diasumsikan meminta bandwidth untuk memenuhi persyaratan QoS. Jika P (o , d )
adalah semua path yang memungkinkan untuk merutekan flow dari pasangan (o ,d ) maka
permasalahan routing dalam kasus ini adalah menemukan path yang mempunyai sisa kapasitas
AV P maksimum dalam sebuah jaringan.
= max (min AV i ) dengan C p>0
Dimana sisa kapasitas atau available bandwidth dari end to end path adalah kapasitas yang
tersisa yaitu jumlah trafik yang dapat dikirim ke sepanjang path tanpa terjadi kemacetan.
Available bandwidth pada sebuah link secara umum didapatkan sesuai persamaan ().
AV i=(1− ρi )∗C i
di mana AV i adalah bandwidth yang tersedia pada link i, ρi adalah utilitas pada link i , dan C i
adalah kapasitas link i. Selanjutnya, end-to-end bandwidth yang tersedia dari path yang berisi H
link jika terdapat paket yang dikirimkan pada rate r adalah:
AV P (r )= mini=1 … H
AV i (r )
jika asumsi terdapat m koneksi dari kelas flow f untuk path pk dan diasumsikan bahwa
setiap node sumber mengetahui informasi mengenai topologi jaringan (termasuk kapasitas
maksimum setiap link) dan beban trafik yang ditawarkan antara setiap pasangan sumber-tujuan.
Dengan pengetahuan global tentang topologi jaringan dan beban trafik yang ditawarkan, m
koneksi di setiap kelas f harus diarahkan melalui path pk antara o dan d dengan alokasi
bandwidth tertentu.
a. Rute tunggal
16
pada model single path, flow hanya diberikan pada path yang mempunyai available
bandwidth terbesar. Diasumsikan path terbaik pk best dari seluruh rute dari sumber dan tujuan
adalah path yang mempunyai sisa bandwith AV P terbesar.
pk best=max {AV P|pk∈ P(o ,d )}
Path dengan available bandwidth terbesar digunakan sebagai path primer. Selanjutnya path
dengan bandwidth yang lebih kecil disediakan sebagai path alternatif. Trafik dialihkan ke path
alternatif jika terjadi kegaglan pada path primer.
b. Rute jamak
Sebuah rute multipath adalah satu set path, dimana masing-masing memiliki node sumber
dan tujuan yang sama. Kami juga menganggap bahwa pada setiap path di rute multipath sebagai
jalur alternatif.Dalam multi-path routing, setiap router dapat menggunakan beberapa jalur yang
berbeda untuk mencapai tujuan. Penggunaan multipath routing bertujuan untuk meningkatkan
ketersediaan end-to-end. ketika salah satu jalur gagal, maka paket data masih bisa disampaikan
melalui jalur lainnya dan dengan demikian ketersediaan end-to-end dapat dipertahankan,
asalkan tidak semua jalur antara sumber dan tujuan gagal secara bersamaan. Asumsi terdapat n
buah path yang mungkin, maka pada multipath routing dipilih k buah path dimana k ≤ n
sehingga ∀ k berlaku AV P>0.
(catatan : masih akan dikembangkan lebih lanjut)
Untuk memodelkan multihop path, pada penelitian ini dipertimbangkan jaringan tandem
m/g/1 yang sudah dijelaskan pada sub bab ....
Asumsi path k ( k= 1,...N) terdiri dari Li intermediate node, maka path ke k dapat
dimodelkan sebagai jaringan antrian yang terkoneksi dalam tandem. Misalkan flow trafik
dengan rata-rata laju kedatangan poisson maka jika terdapat antara sumber dan tujuan diantara
N disjoint path dalam pararel adalah terdistribusi poisson juga yang dinotasikan sebagai
λ j ( j=1 … N )
Dimana
∑j=1
N
λ j=λ
17
λ
λ
λ
λf1
λ
c. Pembagian beban path
Beban jaringan dibagi dan kemudian didistribusikan secara proporsional sesuai dengan
Splitting rasio. Model kami menentukan spliting rasio dengan meminimalkan delay path
maksimal. Gambar 2 menunjukkan suatu set beberapa path yang terhubung antara sumber dan
tujuan.
P (o , d )= {pk }
P (o , d )= {p1, p2 ,…. , pk }
|P (o ,d )|=k
Dari sudut pandang pengguna, jalan p∈P(o , d) terhubung antara sumber dan tujuan dapat
dianggap link logis seperti yang diilustrasikan pada Gambar. 3.... Beban Jaringan akan
didistribusikan dan ditugaskan untuk setiap path sesuai dengan solusi optimal dari masalah
pembagian beban.
Jika Misalkan Bp,l mewakili bandwidth dan dp,l mewakili delay propagasi link l ∈ p.
Bandwidth dan delay di sepanjang jalan Dapat didekati di sini sebagai berikut
Ini masih m/m/1
Gambar 3.10 : splitting ratio
18
di mana λ adalah rata-rata laju kedatangan trafik dan adalah splitting ration untuk path p.
Dengan asumsi ini model pada gambar ..... ditransformasikan ke model antrian pada gambar ....
dan fungsi biaya dirumuskan dalam persamaan.
C p (ϕ p )=Dp+1
B p−λ ϕp (ini masih m/m/1)
Meminimalkan maxp∈P
C p (ϕ p )
Dengan kendala
∑p∈P
ϕ p=1
dan0 ≤ ϕ p≤ Bp
Splitting ratio ϕp untuk semua p ∈ Ρ, adalah dan proporsi trafik yang dialokasikan untuk
path p. Spliting ratio awal dihitung dari Persamaan a :
∀ p∈ P: ϕ p0=
Bp
∑p∈ P
Bp
Controller akan melakukan langkah-langkah sebagai berikut :
1. Hitung C p (ϕ p ) dengan menggunakan persamaan ... untuk setiap p
2. Pilih p∈P yang mempunyai utilitas path ρp < β
3. Tentukan trafik yang melewati path sebanding dengan split ratio
4. Tentukan perubahan splitting ratio
5. Perbaharui splitting ratio
19
3. 3.5 PACEC
Dalam Bab ini, kami mengusulkan eksplisit rate congestion control baru yang menyesuaikan
laju pengiriman flow sesuai dengan status jaringan (kapasitas yang tersedia di path jaringan).
Metode congestion control pada desertasi ini menggunakan router assited congestion control
yang bekerja secara edge to edge. Perbedaan utama dengan router assisted congestion control
yang sudah ada adalah, mekanisme congestion control yang kami usulkan menentukan laju
pengiriman dengan melibatkan seluruh switch di data plane yang dikoordinasi oleh controller.
Keputusan diambil secara global untuk menentukan laju pengiriman flow yang dapat
dialokasikan pada sebuah path dari sumber sampai tujuan.
a. Karakteristik umum
Pada jaringan traditional, metode router assisted control diterapkan pada setiap router
dimana router memberikan umpan balik ke end sistem mengenai keadaan jaringan, dan
memerintahkan pengirim mengirimkan paket pada rate tertentu. Secara umum router assisted
congestion control dimodelkan dengan teori antrian M/G/1-PS untuk menghitung agregat rate
pada setiap router (node). Dimana agregat rate pada setiap node mengikuti model sederhana
yang diberikan pada persamaan berikut:
R=C(1−ρ) (5)
Dimana :
R : sending rate untuk sebuah link, C : kapasitas link dan ρ : utilitas link.
Dari nilai R(t) yang didapatkan, maka dapat diperhitungkan sending rate untuk setiap flow.
Berikut adalah ringkasan persamaan yang digunakan oleh beberapa router asisted congestion
control di jaringan traditional.
Table : 3.1
Agregat sending rate Sending rate per flow Kenaikan dan penurunan rateXCP
Secara umum Kekurangan dari metode yang sekarang adalah rate dihitung secara lokal pada
tiap node sehingga menghasilkan optimal lokal belum tentu secara global juga optimal. Sebagai
ilustrasi sebagai berikut :
20
Informasi lokal
R1(t)= ? R2(t)= ?
Pandangan global
Controller :kebijakan pengendalian kemacetan
R(t)= ?
(tambahkan)
Oleh karena itu kami mengembangkan metode router assisted congestion control yang kami
sebut PACEC ( ) yang mempertimbangkan kondisi global jaringan sehingga diharapkan dapat
mencapai global optimal. Kami menggunakan pendekatan edge to edge congestion control,
dimana sending rate dihitung untuk sebuah path pasangan sumber dan tujuan. PACEC
merupakan algoritma congestion control yang menghitung laju pengiriman secara adil untuk
flow secara langsung dari sumber ke tujuan yang berasosiasi dengan sebuah path. Ide dasar dari
PACEC adalah untuk membangun sistem congestion control pada kerangka kerja SDN dengan
prinsip kolaborasi switch sepanjang path dari sumber sampai tujuan dalam jaringan.
router assisted congestion control di SDN
Gambar 3.11: PACEC di SDN
Secara umum, rate yang dapat dialokasikan pada sebuah path adalah :
Rp=Cp(1−ρp) (7)
Dimana : Rp : sending rate untuk sebuah path, C p : kapasitas path dan ρp : utilitas path
21
usul
Dengan tujuan untuk :
Ropt=maxi=i: k
Rpi=C pi
(1−ρi )
Perbedaan PACEC dengan pengendalian kemacetan yang dibantu jaringan lainnya yang
adalah :
pertama, tidak menggunakan pengukuran yang digunakan untuk umpan balik secara
langsung; laju pengiriman dihitung secara independen berdasarkan hasil dari
perhitungan controller. Perhitungan laju pengiriman dibatasi oleh waktu pelaporan
yang dibutuhkan oleh switch untuk melaporkan kondisi masing-masing switch ke
controler.
Kedua, tidak ada penyesuaian rate secara bertahap. Laju pengiriman dihitung secara
eksplisit berdasarkan kapasitas yang tersedia dan utilitas pada sebuah path. Dengan
demikian PACEC, menghindari penyesuaian laju pengiriman secara bertahap.
Perhitungan laju pengiriman ekspisit secara langsung membantu algoritma ini mencapai
konvergensi yang cepat.
PACEC merupakan sebuah cara untuk menerapkan congestion control melalui
pengalokasian laju pengiriman secara terpusat, dengan menggunakan prinsip-prinsip sebagai
berikut:
- Flow baru dimulai dengan laju pengiriman flow yang tinggi. Laju pengiriman ini
tergantung pada bandwidth yang tersedia pada sebuah path. Controller pada PACEC memutuskan agregat rate flow maksimum yang diijinkan melewati sebuah path.
- ingress switch menyesuaikan laju pengiriman untuk semua flow yang melewati path sesuai
dengan informasi controller.
- Ingress switch melakukan perubahan laju pengiriman flow jika terdapat perubahan
informasi dari controller. Laju pengiriman dihitung secara eksplisit berdasarkan flow
aktif dan ketersediaan kapasitas, sehingga menghindari penyesuaian bertahap seperti
yang dilakukan oleh algoritma reaktif.
Pada PACEC perhitungan laju pengiriman di controller hanya dibatasi oleh waktu yang
dibutuhkan jaringan untuk mendaftarkan perubaan flow dan kondisi jaringan atau secara singkat
kami sebut dengan periode update (Tupdate). Tupdate ini berhubungan langsung dengan frekuensi
22
Xppengirimm 1 penerimam 2 i N
Rp controller
keputusan yang menentukan seberapa sering ingress switch menerima keputusan dari controller untuk
mengubah laju pengiriman.
b. Model PACEC
Kami mempertimbangkan jaringan dengan satu set flow dan link seperti yang telah
ditunjukan pada gambar 3. ...., Untuk menyederhanakan model, diasumsikan dari sumber ke
tujuan sudah tersedia sebuah path P. Sebuah path dalam jaringan data plane terdiri dari
beberapa link l, l∈P. setiap link lmempunyai kapasitas C l ,maka kapasitas path, C p yang
memiliki H link berturut-turut adalah sesuai dengan adalah sebagai berikut :
C p= mini=1 … H
C i
Setiap node terhubung ke sebuah controller. controller menghitung AV p atau bandwidth
yang tersedia pada path P. AV p digunakan sebagai batas atas kapasitas path yang masih dapat
diberikan kepada flow yang melewati path tersebut.AV p juga digunakan untuk menentukan
agregat rate maksimum atau Rpyang melewati sebuah path. Berdasarkan Rp, ingress switch
menyesuaikan laju pengiriman sebesar X p yang mendekati nilai Rp .
Gambar 4... : mekanisme PACEC
Jika setiap path P memiliki satu set flow, F (P), yang melewatinya dan setiap flow a pada path
P dikirim pada laju pengiriman ra, berarti kita akan menentukan alokasi laju pengiriman untuk
flow a yang memenuhi batasan kapasitas path:
∑a∈ F (p )
ra ≤C p
23
c. Kondisi path
Kondisi path jaringan merupakan elemen kunci dari model ini. Kondisi path dapat
diketahui oleh controller dari informasi yang dilaporkan oleh setiap switch. Controller hanya
dapat membuat keputusan congestion control yang terbaik jika controller memiliki informasi
yang benar mengenai kondisi path jaringan data plane. kondisi path digunakan untuk
menentukan besarnya agregat flow yang dapat melewati sebuah path.
Kondisi path pada PACEC ditentukan dengan parameter utilitas path (ρpath). utilitas path
ditentukan dari besarnya utilitas link (ρlink) yang tergabung dalam path tersebut. Kondisi path
bernilai 0 sampai dengan 1. Jika ρp = 0 maka path tidak mengalami kemacetan, jika ρp = 1
menandakan path dalam keadaan macet total. Untuk mendapatkan nilai utilitas path, kami
meggunakan pendekatan pada [ ], dimana utilitas link pada antrian tunggal ρi secara umum
dinyatakan sebagai :
ρi=λi
μi
Ketika terdapat paket tambahan yang ditransmisikan pada rate r bps melintasi antrian ini, maka
utilitas efektif sebuah link ρi (r )adalah :
ρi (r )=min❑ (1 , ρi+
rC i )
Sebuah path jaringan yang terdiri dari urutan H link dimodelkan sebagai H antrian berturutan.
Dengan asumsi bahwa utilitas antrian berturut-turut tidak berkorelasi, maka utilitas end-to-end
dari sistem, ρP dapat dinyatakan sebagai
ρP=1− ∏1≤ i≤ H
(1−ρi )
Utilitas end-to-end dari sistem ketika diperikas pada rate r dapat dinyatakan sebagai ρP (r ),
yang dinyatakan dalam persamaan berikut :
ρP (r )=min❑ (1,1−∏
1 ≤i ≤ H (1−( ρi+r
C i )))
24
Available bandwidth dari end to end path adalah kapasitas yang tersisa yaitu jumlah trafik yang
dapat dikirim ke sepanjang path tanpa terjadi kemacetan. Pada paper ini Available bandwidth
pada sebuah link secara umum didapatkan sesuai persamaan ( ).
AV i=(1− ρi )∗C i
Maka bandwidth yang tersedia pada link i jika terdapat paket yang dikirimkan pada rate r adalah
:
AV i (r )=(1− ρi (r ))∗C i
di mana Ai adalah bandwidth yang tersedia pada link i, ρi adalah utilitas pada link i , dan C i
adalah kapasitas link i. Selanjutnya, end-to-end bandwidth yang tersedia dari path yang berisi H
link jika terdapat paket yang dikirimkan pada rate r adalah:
AV P (r )= mini=1 … H
AV i (r )
d. Rate path (Rp)
Rate path Rpmerupakan common rate yang diberitahukan controller ke edge router.Rp
ini merupakan rate maksimum yang diizinkan untuk flow yang akan melalui path ini selama
periode update T. Controller menghitung Rp secara berkala. Satu path hanya mempertahankan
satu nilai Rp. Secara prinsip Rpditentukan dengan pendekatan prosessor sharing pada
persamaan berikut :
Rp(t )=C p(1−ρ p( t))
e. Alokasi Resource
Setelah rate path Rp diperoleh, selanjutnya sumber daya Rp ini akan didistribusikan kepada N buah sumber trafik yang ada. Terdapat beberapa skema pengalokasian sumber daya ini, antara lain uniform share, fair share, dan constrained share. Permasalahan pembagian sumber daya ini dapat dituliskan secara matematis sebagai berikut. Misalkan terdapat N buah sumber yang memiliki volume data masing-masing adalah υ1 ,υ2 , … , υN . Misalkan bahwa masing-masing sumber mula-mula mengirimkan data dengan kecepatan masing-masing adalah κ1 , κ2 ,…, κN . Maka masing-masing sumber akan selesai mengirimkan data setelah waktu
τ i=υi/κ i (k1)
25
Mean dan standard deviasi dari waktu transmisi ini adalah
T m=∑i=i
N
τ i=∑i=i
N
υi/κ i (k2)
Sm=√ 1N∑i=i
N
(Tm−τ i)2
(k3)
Jika masing-masing sumber memiliki volume trafik yang sama dan laju transmisi mula-mula sama, maka Sm akan bernilai 0 dan sumber dikatakan memiliki laju yang uniform.
Dengan adanya tambahan resource Rp yang terdapat pada jaringan, maka resource ini dapat dibagikan ke setiap sumber sehingga setiap sumber mendapat tambahan rate sebesar ri . Dengan demikian, rate transmisi untuk setiap sumber menjadi
κ̄ i=κi+r i (k4)
Dengan demikian, waktu transmisi dari masing-masing sumber menjadi
τ i=υi/κ i=υi /(κi+ri )=τ i⋅κ i
κi+ri (k5)
Jika tidak semua tambahan resource Rp yang ada dialokasikan untuk penambahan rate dari setiap resource, maka persentase dari resource Rp yang dialokasikan untuk menambah rate transmisi dari masing-masing resource dapat dinotasikan dengan α . Parameter α bernilai antara 0 sampai 1 yang menunjukkan seberapa banyak resource dialokasikan untuk menambah rate dari sumber.
∑i=i
N
ri=α⋅R p (k6)
Dengan rate baru ini, maka mean dan standard deviasi dari waktu kirim sumber berturut-turut berubah menjadi
T m=∑i=i
N
τ i=∑i=i
N
τ i
κ i
κ i+r i (k7)
Dan
Sm=√ 1N∑i=i
N
(Tm−τ i )2=√ 1N∑i=i
N ((∑i=i
N
τ i
κ i
κi+ri)−τ i⋅
κ i
κ i+ri )2
. (k8)
Oleh karena τ i≤τ i maka berlaku T m≤T m . Sedangkan nilai dari standard deviasi yang baru Sm dapat bernilai lebih besar, lebih kecil, atau sama dengan Sm semula bergantung pada pemilihan ri.
26
Permasalahan pemilihan alokasi tambahan ri dengan demikian dapat diformulasikan sebagai upaya untuk meminimalkan parameter waktu transmisi rata-rata T m (rata-rata transmisi tercepat), atau meminimalkan standard deviasi Sm (keadilan waktu transmisi bagi setiap sumber), atau proporsional terhadap besar dari masing-masing volume data di setiap sumber.Permasalahan alokasi yang memimalkan waktu rata-rata transmisi dapat diformulasikan sebagai
Formulasi #1.
Diberikan: N sumber dengan kondisi awal volume trafik υ1 ,υ2 , … , υN dan rate transmisi awal κ1
, κ2 ,…, κN serta rate path sistem yang tersedia Rp dan persentase α .
Tentukan tambahan rater s= [r1 r2 … rN ]T
Sedemikian sehingga
∑i=i
N
ri=α⋅R p
dan
T m=∑i=i
N
τ i=∑i=i
N
τ i
κ i
κ i+r i minimum.
Permasalahan alokasi yang meminimalkan berbedaan waktu transmisi dapat diformulasikan sebagaiFormulasi #2.
Diberikan: N sumber dengan kondisi awal volume trafik υ1 ,υ2 , … , υN dan rate transmisi awal κ1
, κ2 ,…, κN serta rate path sistem yang tersedia Rp dan persentase α .
Tentukan tambahan rater s= [r1 r2 … rN ]T
Sedemikian sehingga
∑i=i
N
ri=α⋅R p
dan
Sm=√ 1N∑i=i
N ((∑i=i
N
τ i
κ i
κi+r i)−τ i⋅
κ i
κ i+ri )2
minimum.
Sedangkan formulasi untuk pengalokasian secara proporsional dapat dirumuskan sebagai.Formulasi #3.
Diberikan: N sumber dengan kondisi awal volume trafik υ1 ,υ2 , … , υN dan rate transmisi awal κ1
, κ2 ,…, κN serta rate path sistem yang tersedia Rp.Tentukan tambahan rate
27
r s= [r1 r2 … rN ]T
Sedemikian sehinggar s=k⋅κ i
dan
∑i=i
N
ri=α⋅R p.
Jika kita dapat membuktikan bahwa T m=∑
i=i
N
τ i=∑i=i
N
τ i
κ i
κ i+r i dan
Sm=√ 1N∑i=i
N ((∑i=i
N
τ i
κ i
κi+ri)−τ i⋅
κ i
κ i+ri )2
adalah fungsi konveks, maka Formulasi #1 dan #2 dapat diselesaikan menggunakan optimasi konveks (Boyd dan Vandenberge, Convex Optimization, Cambridge University Press, 2004). Sedangkan Formulasi (3) dapat diselesaikan dengan Pemrograman Linear (LP). ===========================================================Penyelesaian permasalahan pada Formulasi #1.
Ada beberapa cara untuk menyelesaikan Formulasi #1
Cara pertama adalah dengan cara analitis menggunakan metode Lagrange, cara kedua adalah dengan cara numeris dengan menggunakan metode Optimisasi Konveks.
Pada pembahasan ini, kita akan selesaikan permasalahan Formulasi #1 dengan menggunakan metode analitis yakni menggunakan metode Lagrange.
Untuk penyelesaian dengan metode Lagrange, kita tinjau dulu kasus dengan jumlah sumber sebanyak 2 buah.
Permasalahan formulasi #1 untuk kasus dua sumber ini dapat dinyatakan dengan
Diberikan 2 sumber dengan kondisi awal volume trafik υ1 danυ2 serta rate transmisi awal κ1 dan κ2 . Rate path sistem yang tersedia Rp dan persentase α .
Tentukan tambahan rater s= [r1 r2 ]
T
Sedemikian sehinggar1+r2=α⋅R p=X p
dan
T m=12∑i=i
2
τ i=12∑i=i
2
τ iκi
κ i+ri=1
2 ( υ1
κ1+r1+
υ1
κ2+r2)
minimum
Fungsi objektf yakni T m yang merupakan fungsi dari r1 dan r2 kita notasikan sebagai F(r1,r2), yaitu
F (r1 , r2 )=12 ( υ1
κ1+r1+
υ1
κ2+r2)
. (K9)
28
Sedangkan konstrain persamaan r1+r2=α⋅R p kita tulis ulang sebagai fungsi G(r1,r2), yaitu
G(r1 , r2 )=r1+r2−X p=0 (K10)
Gradien dari fungsi objektif F(r1,r2) adalah ∇ F(r1 ,r 2)=
∂F (r1 , r2 )r1
a⃗r 1+∂F (r1 , r2 )r2
a⃗r 2
=−υ1
2 (κ1+r1)2a⃗r 1−
υ2
2 (κ2+r2)2a⃗r2
(K11)
Sedangkan gradient dari fungsi konstrain adalah
∇G(r1 , r2)=∂G(r1 , r2 )r1
a⃗r 1+∂G(r1 , r2 )r 2
a⃗r2
=a⃗r 1+ a⃗r2 (K12)
Persamaan Lagrange ():L (r1 , r2 , λ )=∇ F (r1 , r2)−λ⋅∇G(r1 ,r 2)=0 , (K13)
Dengan λ adalah konstanta pengali Lagrange.
Dengan memasukkan nilai ∇ F(r1 ,r 2) dan ∇G(r1 , r2 ) ke dalam (K13) diperoleh
−υ1
2 (κ1+r1)2a⃗r 1−
υ2
2 (κ2+r2)2a⃗r 2− λ⋅( a⃗r1+ a⃗r2 )=0
(K14)
Atau
(− υ1
2 (κ1+r1 )2+λ) a⃗r1+(− υ2
2 (κ2+r 2)2+λ) a⃗r 2=0
(K15)
Agar persamaan (K15) terpenuhi, maka setiap komponen pada a⃗r 1 dan a⃗r 1 harus nol. Sehingga
(− υ1
2 (κ1+r1 )2+λ)=0
dan (− υ2
2 (κ2+r2 )2+λ)=0
.
Atau
( υ1
(κ1+r 1)2 )=(υ2
(κ2+r2 )2 ) (K16)
Atau
( (κ1+r 1)2
(κ2+r 2)2 )=( υ1
υ2 ) (K17)
Dengan asumsi k1+ r1 dan k2 + r2 positif, maka
29
κ1+r1
κ2+r2=√ υ1
υ2 (K18)
Oleh karena κ1 dan κ2 adalah rate transmisi awal dari sumber 1 dan 2, dan r1 dan r2 adalah
penambahan rate bagi kedua note tersebut, sedangkan υ1 dan υ1 adalah volume traffic mula-mula dari sumber 1 dan 2, maka persamaan (K18) memiliki arti fisis bahwa penambahan rate r1 dan r2 harus dilakukan agar rasio dari rate transmisi akhir adalah sebanding dengan akar dari rasio volume trafik sumber 1 terhadap sumber 2.
Tulis ulang (K18) sebagai persamaan linier dalam r1 dan r2, serta mengingat r1+r2=X p maka diperoleh sistem persamaan
r1−√ υ1
υ2⋅r 2=−k1+√ υ1
υ2⋅k2
(K19.A)
r1+r2=X p (K19.B)
Dalam matriks :
[1 −√ υ1
υ2
1 1 ]⋅[r1
r2 ]=[−k1+√ υ1
υ2⋅k2
X p]
(K20)
Dengan demikian solusi dari (K20) yang merupakan solusi permasalahan Formulasi #1 untuk jumlah sumber 2 adalah
[r1r2 ]=[1 −√ υ1
υ2
1 1 ]−1
[−k1+√ υ1
υ2⋅k2
X p]. (K21)
Untuk tiga sumber.
Penurunan dilakukan dengan cara yang sama dengan solusi dua sumber. Yaitu didefinisikan fungsi objektif:
F (r1 , r2 , r3 )=υ1
κ1+r1+
υ2
κ2+r2+
υ3
κ3+r3 (K22)
Dan fungsi konstrain
G(r1 , r2 ,r3 )=r1+r2+r3−X p=0 (K23)
Dengan menerapkan metode Lagrange seperti sebelumnya, maka kita peroleh set persamaan:κ1+r1
κ2+r2=√ υ1
υ2 (K24.A)
30
κ1+r1
κ3+r3=√ υ1
υ3 (K24.B)
Tulis ulang (K24.A) dan (K24.B), maka kita peroleh sistem persamaan linear
r1−√ υ1
υ2⋅r 2+0⋅r3=−k1+√ υ1
υ2⋅k2
(K25.A)
r1+0⋅r2−√ υ1
υ3⋅r3=−k1+√ υ1
υ3⋅k3
(K25.B)
r1+r2+r3=X p (K25.C)
Persamaan (K25.C) adalah dari fungsi konstrain.
Tulis ulang sistem persamaan (K25.A), (K25.B) dan (K25.C), maka kita peroleh persamaan dalam matriks:
[1 −√ υ1
υ20
1 0 −√ υ1
υ3
1 1 1]⋅[r1
r2
r3]=[−k1+√ υ1
υ2⋅k2
−k1+√ υ1
υ2⋅k3
X p
] (K26)
Sehingga solusi dari permasalahan Formulasi #1 untuk 3 variabel adalah
[r1
r2
r3]=[1 −√ υ1
υ20
1 0 −√ υ1
υ3
1 1 1]−1
⋅[−k 1+√ υ1
υ2⋅k 2
−k 1+√ υ1
υ2⋅k 3
X p
](K27)
Solusi general untuk N variable.
Solusi general dari N variable diperoleh dengan mengeneralisasi fungsi objektif F(r1, r2, ... , rN) dan G(r1, r2, …, rN) dan menerapkan metode Lagrange untuk kemudian menyusun persamaan yang diperoleh dalam sistem persamaan linier.
Dengan menerapkan langkah tersebut, maka sistem persamaan linier yang diperoleh adalah
r1−√ υ1
υ2⋅r 2+0⋅r3+⋯+0⋅r N=−k1+√ υ1
υ2⋅k2
(K28.A)
r1+0⋅r2−√ υ1
υ3⋅r3+⋯+0⋅r N=−k1+√ υ1
υ3⋅k3
(K25.B)
…
r1+r2+r3=X p (K25.C)
31
Dengan demikian persamaan matriksnya menjadi
[1 −√ υ1
υ20 ⋯ 0
1 0 −√ υ1
υ3⋯ 0
1 0 0 ⋯ 0⋮ ⋮ ⋮ ⋱ ⋮1 1 1 ⋯ 1
]⋅[ r1
r2
r 3
⋮rN]=[−k 1+√ υ1
υ2⋅k 2
−k1+√ υ1
υ3⋅k 3
−k1+√ υ1
υ4⋅k 4
⋮X p
](K26)
Untuk keringkasan, kita dapat tulis (K26) menjadi
P⋅r=c (K27)
Sehingga
r=P−1 c (K28)
Dengan
P=[1 −√ υ1
υ20 ⋯ 0
1 0 −√ υ1
υ3⋯ 0
1 0 0 ⋯ 0⋮ ⋮ ⋮ ⋱ ⋮1 1 1 ⋯ 1
](K29)
Dan
32
c=[−k1+√ υ1
υ2⋅k2
−k1+√ υ1
υ2⋅k3
−k1+√ υ1
υ2⋅k3
⋮X p
](K30)
==============================================================
BAGIAN CONTOH NUMERIK INI SUDAH DIVERIFIKASI (KRU, 21 June 2017)
Contoh Numerik.
Misalkan network memiliki 2 sumber dengan Volume Trafik υ1=100 satuan volume dan υ2=400
satuan volume. Mula-mula sumber tersebut mengirim dengan kecepatan yang sama yaitu κ1=4 dan κ2=4 . Jika Controller menginformasikan nilai Rp sebesar 10 dan dengan asumsi α=1 , maka akan dihitung penambahan rate r1 dan r2 agar rata-rata pengiriman menjadi minimum.
Solusi:
Untuk kasus ini, kita langsung saja ke persamaan matriks yakni
[1 −√ υ1
υ2
1 1 ]⋅[r1
r2 ]=[−k1+√ υ1
υ2⋅k2
X p]
Di sini
P=[1 −√ υ1
υ2
1 1 ]⋅[r1
r2 ] dan
c=[−k1+√ υ1
υ2⋅k2
X p].
Masukkan nilai υ1=100 , υ2=400 , κ1=4 dan κ2=4 serta Xp = 1x10 = 10
[1 −0 .51 1 ]⋅[r1
r2 ]=[−210 ]
Sehingga
[r1
r2 ]=[1 −0 .51 1 ]
−1
[−210 ]=[28 ]
Rate sekarang :
Sumber 1 : r1 + k1 = 4 + 2 = 6
Sumber 2 : r2 + k2 = 4 + 8 = 12
33
Perbandingan rate sumber 1 dan sumber 2 adalah 6 : 12 atau 1:2 yakni sama dengan perbandingan akar volume traffic sumber 1 terhadap sumber 2.
Waktu transmisi dari sumber 1 : t1 = v1 / (r1+k1) = 100 / 6 = 16,67.
Waktu transmisi dari sumber 2 : t2 = v2/(t2+k2) = 100 / 12 = 8,33.
Rata-rata waktu transmisi : (16.67 + 8.33) / 2 = 12.5
Sebelum penambahan rate, waktu transmisi adalah :
Sumber 1 : t1 = v1/k1 = 100/4 = 25
Sumber 2 : t2 = v2/k2 = 400/4 = 100
Sehingga waktu transmisi rata-rata adalah (25+100)/2 = 125/2 = 62.5
Apakah penambahan rate baru [2 8] tersebut paling minimum?
Ambil contoh penambahan rate masing-masing 5. Dengan demikian rate sumber 1 dan 2 menjadi 4 + 5 = 9.
Waktu transmisi sumber 1 : 100/9 = 11,11
Waktu transmisi sumber 2 : 400/9 = 44,44
Waktu transmisi rata-rata = (11,11 + 44,44) / 2 = 55,55 /2 = 27,775 (masih kalah dengan penambahan rate [2 8] tadi).
34
Ambil case yang lain, yakni [-2/5 52/5] (misalkan diijinkan r1 negatif). Dengan demikian,
Rate sumber 1 menjadi 18/5 dan rate sumber 2 menjadi 72/5.
Waktu transimisi sumber 1 menjadi : 100 / (18/5) = 27,78
Waktu transmisi sumber 2 menjadi : 400 / (72/5) = 27,78.
Waktu transmisi rata-rata adalah 27,78 (masih kalah disbanding dengan penambahan rate [2 8 ] tadi).
===================================================================
Solusi Formulasi #2.Kita akan selesaikan permasalahan Formulasi #2 dengan menggunakan metode metode Lagrange.
Seperti halnya dengan langkah terdahulu, kita tinjau dulu kasus dengan jumlah sumber sebanyak 2 buah. Permasalahan Formulasi #2 untuk kasus dua sumber ini dapat dinyatakan dengan
Diberikan 2 sumber dengan kondisi awal volume trafik υ1 danυ2 serta rate transmisi awal κ1 dan κ2 . Rate path sistem yang tersedia Rp dan persentase α .
Tentukan tambahan rater s= [r1 r2 ]
T
Sedemikian sehinggar1+r2=α⋅R p=X p
dan
35
Sm=√12∑i=i
2 ((12∑i=i
2 v i
κi+ri )−¿v i
κ i+ri )2
¿√12∑i=i
2 ((12 v1
k1+r1+
12
v2
k 2+r2 )−v i
κ i+ri )2
¿1√2 √((12 v1
k1+r1+1
2v2
k2+r2)−v1
κ1+r1 )2
+((12 v1
k1+r1+1
2v2
k2+r2)−v2
κ2+r2 )2
¿1√2 √(−1
2v1
k1+r1+1
2v2
k 2+r2)
2
+(12 v1
k1+r1−1
2v2
k2+r2)2
¿12√2 √(−v1
k1+r1+
v2
k 2+r2 )2
+(v1
k1+r1−
v2
k2+r 2 )2
¿12√2 √2⋅(v1
k1+r1−
v2
k2+r2)2
=12 √(v1
k1+r1−
v2
k2+r2)2
minimum
Karena tidak ada jaminan bahwa
v1
k1+r1≥
v2
k2+r2 , maka kita biarkan ekspresi terakhir tidak disederhanakan.
Oleh karena fungsi akar akan optimum jika fungsi di bawah tanda akarnya optimum, maka kita gunakan fungsi objektif yang lebih sederhana F(r1,r2)
F (r1 , r2 )=( v1
k 1+r1−
v2
k 2+r2)2
(K31)
Sedangkan konstrain persamaan masih sama seperti Formulasi (1) yaitu r1+r2=α⋅R p dan kita tulis ulang sebagai fungsi G(r1,r2), yaitu
G(r1 , r2 )=r1+r2−X p=0 (K32)
Gradien dari fungsi objektif F(r1,r2) adalah ∇ F(r1 ,r 2)=
∂F (r1 , r2 )r1
a⃗r 1+∂F (r1 , r2 )r2
a⃗r 2
=12 (υ1
κ1+r1−
υ2
(κ2+r2 ) )−υ1
(κ1+r1)2a⃗r 1+
12 (υ1
κ1+r1−
υ2
(κ2+r2 ) )υ2
(κ2+r2 )2a⃗r 2
(K33)
Sedangkan gradient dari fungsi konstrain adalah
36
∇G(r1 , r2)=∂G(r1 , r2 )r1
a⃗r 1+∂G(r1 , r2 )r 2
a⃗r2
=a⃗r 1+ a⃗r2 (K34)
Persamaan Lagrange ():L (r1 , r2 , λ )=∇ F (r1 , r2)−λ⋅∇G(r1 ,r 2)=0 , (K35)
Dengan λ adalah konstanta pengali Lagrange.
Dengan memasukkan nilai ∇ F(r1 ,r 2) dan ∇G(r1 , r2 ) ke dalam (K13) diperoleh
= 12 ( υ1
κ1+r1−
υ2
(κ2+r 2) )−υ1
(κ1+r1 )2a⃗r1+
12 ( υ1
κ1+r1−
υ2
(κ2+r2) )υ2
(κ2+r2)2a⃗r 2−λ⋅( a⃗r1+ a⃗r2 )=0
(K36)
Atau
(−( υ1
κ1+r1−
υ2
(κ2+r2) )υ1
2 (κ1+r1 )2+λ) a⃗r 1+(( υ1
κ1+r1−
υ2
(κ2+r 2) )υ2
2 (κ2+r2)2+λ) a⃗r 2=0
(K37)
Agar persamaan (K15) terpenuhi, maka setiap komponen pada a⃗r 1 dan a⃗r 1 harus nol. Sehingga
(−( υ1
κ1+r1−
υ2
(κ2+r2) )υ1
2 (κ1+r1 )2+λ)=0
dan ( υ1
κ1+r1−
υ2
(κ2+r2) )( υ2
2(κ2+r2 )2+λ)=0
.
Atau
( υ1
κ1+r1−
υ2
(κ2+r2) )−υ1
2 (κ1+r1 )2=( υ1
κ1+r1−
υ2
(κ2+r2) )υ2
2 (κ2+r2 )2 (K38)
Atau
( υ1
κ1+r1−
υ2
(κ2+r2) )( υ1
2 (κ1+r1)2+
υ2
2 (κ2+r2)2 )=0(K39)
Persamaan (K39) terpenuhi jika
( υ1
κ1+r1−
υ2
(κ2+r2) )=0 (K40A)
Atau
( υ1
2 (κ1+r1 )2+
υ2
2 (κ2+r2)2 )=0 (K40B)
37
Persamaan (K40B) hanya terpenuhi jika υ1 dan υ2 bernilai nol. Karena υ1 dan υ2 dapat bernilai sebarang bilangan positif, maka (K40B) tidak dapat dipenuhi. Sehingga (K40A) yang harus dipenuhi.
Persamaan (K40A) disederhanakan menjadi :κ1+r1
κ2+r2=
υ1
υ2 (K41)
Persamaan (K41) mengandung arti fisis bahwa untuk meminimalkan variansi dari waktu transmisi, maka penambahan rate r1 dan r2 dilakukan sehingga rasio rate transmisi sumber 1 terhadap sumber 2 setelah penambahan tersebut adalah sama dengan rasio dari volume trafik dari sumber 1 terhadap sumber 2. Hasil ini secara intuitif benar, karena dengan membuat rasio ini sama, maka waktu transmisi dari kedua sumber akan sama sehingga standard deviasi waktu transmisi menjadi nol yang merupakan nilai minimum standard deviasi yang mungkin.
Kita susun kembali persamaan (K41) tersebut serta dimasukkan fungsi konstrain, maka diperoleh system persamaan linier
r1−v1
v2⋅r 2=−k1+k 2
v1
v2 (K42A)
r1+r2=X p (K42B)
Dalam matriks, set persamaan (K42A) dan (K42B) dapat dituliskan sebagai
[1 −υ1
υ2
1 1 ]⋅[r1
r2 ]=[−k1+¿k2⋅υ1
υ2
X p]
(K43)
Dan solusi persamaan (K43) tersebut adalah
[r1
r2 ]=[1 −υ1
υ2
1 1 ]−1
⋅[−k 1+¿k2⋅υ1
υ2
X p]
(K44)
Seperti halnya pada penyelesaian Formulasi #1, kasus pada Formulasi #2 ini dapat digeneralisasi ke N sumber
Solusi general dari N variable diperoleh dengan mengeneralisasi fungsi objektif F(r1, r2, ... , rN) dan G(r1, r2, …, rN) dan menerapkan metode Lagrange untuk kemudian menyusun persamaan yang diperoleh dalam sistem persamaan linier.
Dengan menerapkan langkah tersebut, maka sistem persamaan linier yang diperoleh adalah
r1−υ1
υ2⋅r2+0⋅r3+⋯+0⋅r N=−k1+
υ1
υ2⋅k2
(K28.A)
38
r1+0⋅r2−υ1
υ3⋅r3+⋯+0⋅r N=−k1+
υ1
υ3⋅k3
(K25.B)
…
r1+r2+r3+⋯rN=X p (K25.C)
Dengan demikian persamaan matriksnya menjadi
[1 −υ1
υ20 ⋯ 0
1 0 −υ1
υ3⋯ 0
1 0 0 ⋯ 0⋮ ⋮ ⋮ ⋱ ⋮1 1 1 ⋯ 1
]⋅[ r1
r2
r3
⋮r N]=[−k1+
υ1
υ2⋅k2
−k1+υ1
υ3⋅k3
−k1+υ1
υ4⋅k 4
⋮X p
](K26)
Untuk keringkasan, kita dapat tulis (K26) menjadi
Q⋅r=c (K27)
Sehingga
r=Q−1 c (K28)
Dengan
Q=[1 −υ1
υ20 ⋯ 0
1 0 −υ1
υ3⋯ 0
1 0 0 ⋯ 0⋮ ⋮ ⋮ ⋱ ⋮1 1 1 ⋯ 1
](K29)
Dan
39
c=[−k1+υ1
υ2⋅k2
−k1+υ1
υ3⋅k3
−k1+υ1
υ4⋅k4
⋮X p
](K30)
==============================================================
Contoh Numerik.
Sama seperti contoh untuk Formulasi #1 sebelumnya. Misalkan network memiliki 2 sumber dengan Volume Trafik υ1=100 satuan volume dan υ2=400 satuan volume. Mula-mula sumber tersebut mengirim dengan kecepatan yang sama yaitu κ1=4 dan κ2=4 . Jika Controller menginformasikan nilai Rp sebesar 10 dan dengan asumsi α=1 , maka akan dihitung penambahan rate r1 dan r2 agar standard deviasi waktu pengiriman menjadi minimum.
Solusi:
Untuk kasus ini, kita langsung saja ke persamaan matriks yakni
[1 −υ1
υ2
1 1 ]⋅[r1
r2 ]=[−k1+υ1
υ2⋅k2
X p]
Di sini
P=[1 −υ1
υ2
1 1 ]⋅[r1
r 2 ] dan
c=[−k1+υ1
υ2⋅k 2
X p].
Masukkan nilai υ1=100 , υ2=400 , κ1=4 dan κ2=4 serta Xp = 1x10 = 10
[1 −0 .251 1 ]⋅[r1
r2 ]=[−310 ]
Sehingga
[r1
r2 ]=[1 −0 .251 1 ]
−1
[−310 ]=[−0,4
10 , 4 ]
Solusi ini menarik karena nilai r1 negatif, yang berarti rate untuk sumber 1 harus dikurangi.
Rate transmisi baru dengan demikian adalah :
Sumber 1 : 4 – 0,4 = 3,6
40
Sumber 2 : 4 + 10,4 = 14,4
Dengan demikian rasio sumber 1 : sumber 2 = 3,6 : 14,4 = 1 : 4 = v1 : v2.
Standar deviasi dengan rate baru ini adalah 0.
Contoh berikutnya : 3 sumber dengan volume data masing-masing sebesar v1 = 100, v2 = 200, dan v3 = 400.
Masing-masing memiliki rate mula-mula yang sama yakni : k1 = k2 = k3 = 5.
Network memberitahukan bahwa ada available bandwidth sebesar 10. Ingress switch memutuskan untuk memberikan semua bandwidth tersebut ke sumber. Akan dihitung berapa alokasi yang sebaiknya
diberikan ke setiap sumber.
Matriks Q
Q=[1 −v1
v20
1 0 −v1
v3
1 1 1]=[1 −0,5 0
1 0 −0 , 251 1 1 ]
Matriks c
c=[−k1+v1
v2k2
−k1+v1
v3k3
−k 1+v1
v4k 4]=[−5+ 1
25
−5+ 14
5
10]=[ −2,5−3 ,7510 ]
sehingga
41
[r 1r 2r3 ]=[
1 −0,5 01 0 −0 ,251 1 1 ]
−1
⋅[ −2,5−3 ,7510 ]=[−1 , 43
2 ,149 ,26 ]
TEST.
Rate sumber 1 sekarang = 5 - 1,43 = 3,57
Rate sumber 2 sekarang = 5 + 2,14 = 7,14
Rate sumber 3 sekarang = 5 + 9,26 = 14,26
Waktu transmisi
SUmber 1 = 100 / 3,57 = 28
Sumber 2 = 200 / 7,14 = 28
Sumber 3 = 400 / 9,26 = 28
Standard deviasi waktu kirim adalah 0. Seperti yang diharapkan.
===================================================================
e.1. Rate per flow (fair share rate)
Pada tahap ini sumber mengambil "langkah" untuk menyesuaikan rate berdasarkan informasi
dari ingress switch. Tahap ini digunakan untuk mengalokasikan rate untuk setiap flow sehingga
Rpdapat digunakan dengan optimal. Rate untuk setiap flow diperbaharui setiap kali sebuah flow
baru diterima di edge switch. Jika kapasitas path adalah adalah C p, diasumsikan rate
kedatangan setiap flow a adalah ra dan hasil perhitungan, rate yang bisa dialokasikan untuk
flow a adalah xa, maka setiap flow akan menerima layanan sebesar min (ra , xa ). Jika total laju
kedatangan flow adalah A, maka :
A=∑i=1
n
ra
Jika A>Cp, Maka
Cp=∑i=1
n
min ( ra , xa )
xa=? ? ?? ?
e.2. Proportional resource share
42
Flow kelas 2
λfm
λ2
λ1
C
b1
Flow kelas 1
b2
bm3
μs
control plane
Penjadwalan
kebijakan
classifierFlow kelas 3
e.3. Constrained resource share
3. 3.6 Interoperasi PACEC dengan multipath routing
Interoperasi PACEC dengan multipath routing ini dirancang untuk mengatasi keterbatasan
pengendalian kemacetan rate eksplisit saat ini dan protokol single path routing. Dalam shortest
pat routing , ketika link / jalur yang padat, pengirim hanya dapat menurunkan laju aliran.
arsitektur yang diusulkan memberikan solusi alternatif untuk masalah ini, di mana aliran baru
yang ditugaskan ke path yang terbaik di antara beberapa path dalam hal throughput dicapai.
Berlawanan dengan algoritma multipath lain yang diusulkan, algoritma multipath memberikan
tiap aliran ke diberikan path. Jalan terbaik ditentukan dengan mengumpulkan informasi dari rute
multipath dan kemudian menghitung rate berdasarkan informasi.
Sebuah rute multipath dikelola oleh router ingress untuk flow melintasi oleh rute
menggunakan algoritma ... yang dibahas dalam sub bab ...... Setiap kali flow baru tiba kerouter
ingress, router memberikan aliran ke jalur “terbaik”. Kami mendefinisikan jalur terbaik sebagai
path yang menyediakan laju pengiriman terbesar di antara rute multipath diatur untuk diberikan
tujuan. path terbaik ini ditentukan berdasarkan ......
3. 3.7 PACEC untuk heterogen trafik
43
Flow tipe f yang datang pada sebuah path menerima sebuah agregat laju pelayanan sebesar bf ∈ [0, Cp]. Dimana Cp >0 dan merupakan service rate maksimum yang dapat disediakan untuk
setiap tipe flow pada sebuah path. Total laju pelayanan bf dibagi untuk semua flow pada kelas
tersebut. waktu layanan flow dari kelas yang sama diasumsikan saling bebas satu sama lain
demikian juga waktu layanan untuk kelas yang berbeda diasumsikan diasumsikan saling bebas
satu sama lain, yaitu layanan yang diberikan kepada flow satu kelas tidak mempengaruhi
pelayanan yang diberikan kepada flow kelas yang lain.
Untuk menentukan sending rate tiap flow untuk layanan yang berbeda, maka mekanisme
congestion control terintegrasi dengan mekanisme manajeman jaringan lainnya. Dengan
mekanisme sebagai berikut :
a. Langkah 1
ingress node menerima permintaan dari layanan pelanggan UDP (VOIP atau video) atau
TCP untuk mengalokasikan kapasitas link. Pada langkah ini edge node
mengklasifikasikan permintaan ke dalam 1 dari kategori yang ada. Flow dibedakan ke
dalam 3 layanan. Untuk menentukan kelas pelayanan trafik heterogen di .... kita
mempertimbangkan tiga layanan :
GS (guaranted service) digunakan untuk flow data yang memiliki kendala yang kuat
baik dari segi delay dan kehandalan. Aplikasi yang ditargetkan oleh GS adalah layanan
yang tidak mentolerir variasi QoS;
AS : assured service digunakan untuk flow responsif yang tidak memiliki kendala
keterlambatan yang kuat, tetapi membutuhkan bandwidth rata-rata minimum.
BE: best effort digunakan untuk layanan yang tidak ada jaminan QoS.
Paket diklasifikasikan tergantung pada nilai DSCP dari header paket dan ditugaskan untuk
antrian yang berbeda (buffer) kelas forwarding seperti yang ditunjukkan pada Gambar 3.4.
44
Gambar 3. : klasifikasi paket
b. Langkah 2
ingress node melaporkan ke controller dan kemudian controller menetapkan path dengan
data rate QoS yang dipersyaratkan. Pada langkah ini termasuk di dalamnya terdapat
prosedur admission control. Pada langkah ini admission control diterapkan pada edge
router untuk memastikan sebuah permintaan akan diterima atau tidak. Admission control
hanya diberlakukan untuk flow real time. Sebuah permintaan akan diterima jika
- Bandwidth yang tersedia dapat melayani flow real timeRp ≥ bmin new
Dimana bmin new adalah bandwidth minimum yang diperlukan oleh sebuah flow baru
bmin adalah jamainan rate minimum. Dimana Rate minimum dari sebuah flow i masih
memungkinkan flow mendapatkan jaminan performansi
b i≥ bimin , ∀ i∈ f
bmin ditentukan berdasarkan karekteristik flow
- Flow setup controller tidak melebihi dari ambang batas
t setup=t t h resh old
Asumsi kapasitas total sebesar C dan kapasitas yang dialokasikan untuk tiap kelas adalah Ci
∑❑
❑
ci ≤ C
dsetup ≤d t h reshold
Dimana probabilitas delay untuk mendapatkan sebuah koneksi (flow setup)
P (dsetup ≥ d t hres hold )=1− ∫0
dt hres hold
f d setupdsetup
45
P (dsetup<d t hres h old )=1−Fd setup
P (dsetup<d t h res h old )= ∫0
d th resh old
f dsetupdsetup
c. Langkah 3
- Pemilihan path
Setelah dipastikan flow baru dapat diijinkan masuk jaringan, langkah selanjutnya adalah
diberikan rute sebuah path dari sumber sampai tujuan.
Dimana rute terbaik adalah :
Pi best=max {Rbw pi|Pi∈P od }
Path yang dipilih untuk aplikasi real time adalah path yang memenuhi syarat :
D p=D pt h reshold
Pengalihan rute untuk aplikasi real time dilakukan jika koefsien variansi dari delay path
≥ δ
- Bandwidth allocation
ai mewakili rate untuk flow i dan Rp adalah rate agregat untuk seluruh flow yang aktif
Untuk trafik heterogen alokasi rate untuk kelas yang berbeda sesuai dengan bobot
a i=w (c i)
∑j
❑
n j w (c j)Rp
Flow dari kelas yang sama mendapatkan proporsi yang sama dari Rp Dimana
46
Clinkclassifier WFQ
diffserv
Kelas 1
Kelas 2
Kelas 3
Setiap antrian i diberikan bobot φi sedemikian rupa sehingga rate pelayanan minimum
tertentu dijamin pada setiap antrian. Kapasitas yang dialokasikan untuk trafik kelas i
dinotasikan dengan ci diberikan
c i=ϕi
∑i
❑
ϕi
C link
Pengklasifikasi flow membaca kode pada header dan akan menempatkan masing-masing
kelas pada antrian. setiap antrian i diberi bobot sesuai dengan laju pelayanan minimum.
Kapasitas yang disediakan untuk masing-masing kelas adalah :
C k=ϕk
∑1
k
ϕi
.C
ρk=Bk
ϕk
∑i
k
ϕ i
.C
Bkmerupakan rata-rata agregat bit rate setiap kelas.
Sebuah path Pi untuk pasangan sumber dan tujuan mempunyai rata-rata laju kedatangan
sebesar λ dan rata-rata waktu pelayanan t. Terdapat m Qos kelas yang berbeda dalam jaringan,
misal Q= {1 , …, m }. Flow pada kelas yang sama diberikan alokasi bandwidth yang sama. Untuk
47
menentukan besarnya bandwidth setiap kelas maka perlu ditetapkan terlebih dahulu bandwidth
atau service rate pada sebuah path.
Setiap kelas mempunyai persyaratan QoS yang spesifik termasuk persyaratan bandwidth
minimal Bf dan kendala maksimal end-to-end delay Dpi. Jumlah total koneksi untuk setiap kelas
adalah Nf.
Pada sistem dengan heterogen flow dengan kelas layanan yang berbeda, service rate yang
dialokasikan berbeda untuk tipa jenis flow. flow dilayani oleh server tunggal dengan service
rate sebesar μ paket per detik. Dimana μ=Cσ , σ = rata-rata ukuran paket dan service rate untuk
setiap layanan adalah μc, μv , dan μe. Untuk menjaga kestabilan maka :
N c μc+N v μv+N e μe ≤ Nμ
Sehingga bit rate yang disediakan untuk setiap layanan adalah service rate dikalikan dengan
rata-rata ukuran paket setiap layanan. Jika untuk CBR ukuran paket rata-rata adalah E [ xc ], VBR
adalah E [ xv ] dan elastis adalah E [ xe ] paket per bit. maka bit rate untuk setiap layanan adalah
rc=E [ xc ] μc, r v=E [ xv ] μv dan r s=E [ xe ]μe . bit rate total untuk ketiga layanan adalah
N c rc+N v r v+N s rs<C
Ketika ada N flow yang ada dalam sistem yang terdiri dari Nc, Nv dan Ne, maka laju berakhirnya flow (service rate) adalah :
μ (N )=Rc (N c )E ( zc )
+Rv (N v )E ( zv )
+Re (N e)E(z s)
Beban yang diakibatkan oleh ketiga layanan adalah ρ=ρc+ ρv+ρe
Dimana ρc=λc
μc , ρ v=
λv
μv dan ρe=
λe
μe
Flow dengan CBR
Karena durasi dari layanan CBR tidak tergantung pada bandwidth yang tersedia maka bit rate untuk layanan ini adalah konstan sebesar rc. Ketika ada sejumlah Nc flow CBR maka bit rate total yang disediakan untuk layanan ini adalah
48
Rc (N c )=N c rc
- Flow dengan VBR
Layanan VBR bervariasi sesuai dengan ambang batas bawah dan ambang batas atas, maka bit rate untuk layanan ini adalah :
R v (Nv )=N v rv
r v=min (❑❑ ,❑❑) ( bergerak dari min threshold ke max threshold)
- Jumlah Flow - Jumlah flow untuk masing-masing layanan adalah : Jumlah flow streaming CBR
N c
Jumlah flow streaming VBR jika ada j flow CBR dan tidak ada flow elastik
N v (N c)=[C−N c rc
E[rv ] ]Jumlah maksimum flow elastik jika terdapat i flow streaming VBR dan j flow CBR adalah
N e (N c ,N e)=[C−N c rc−Nv rv
E [re] ]Beban trafik elastik jika ada i flow streaming VBR dan j flow CBR
ρe (i , j )=λe
μe (C−ir v− jr c )
- Flow elastis
Bit rate untuk layanan elastis tergantung pada ukuran flow dan bit rate yang dialokasikan untuk layanan ini adalah :
Re (N e)=N e r e
Initial sending rateSetiap flow yang dibangkitkan oleh sumber mengharapkan rate awal untuk mengirimkan
data. Rate awal yang dialokasikan untuk tiap flow sebesar ri tergantung pada jenis layanan.
49
Untuk layanan CBR jika permintaan rate sebuah flow adalah λfc, maka sending rate dari sebuah flow adalah :
rc= λfc
Untuk layanan VBR jika permintaan rate sebuah flow adalah λfv, maka sending rate dari sebuah flow adalah :
r v=¿
Untuk layanan elastis (best effort) jika permintaan rate sebuah flow adalah λfe, maka sending rate dari sebuah flow adalah :
re=¿
d. Langkah 4
Setiap periode waktu yang telah ditetapkan controller memperbaharui status kondisi
jaringan sesuai dengan kondisi yang dilaporkan tiap node. Pada langkah ini merupakan
proses update untuk laju pengiriman.
Rate adaptation
Jika ρ> β: ini menandakan kemacetan. rate tidak bisa dialokasikan secara penuh dan
penyesuaian harus dilakukan.
Penyesuaian dilakukan dengan menghitung kembali bandwidth yang tersedia pada
sebuah path. Update dari Rp dilakukan dengan menggunakan nilai ρp yang diamati dan
nilai Xp. Dengan mempertimbangkan rate ri yang diminta, menghitung nilai ρp baru
dengan rate yang sama dengan Rtot + ri.
e. Langkah 5
proses ini diulangi secara berkala.
50