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