## PENENTUAN PRIORITAS PADA JARINGAN BACKBONE PALAPA RING MENGGUNAKAN DERAJAT NODE DAN CUT VERTEX
S. I. Pella 1 , H. F. J. Lami 2
1,2 Jurusan Teknik Elektro, Universitas Nusa Cendana Jl. Adi Sucipto, Kupang, 85000, Indonesia Email:s.i.pella@staf.undana.ac.id Email: h.f.j.lami@staf.undana.ac.id

## ABSTRACT
Palapa Ring aims to connect provinces and cities in Indonesia via a high-data-speed telecommunication path. This research aims to identify the priority scale of each node in the Palapa Ring Backbone network by considering the degree of each node and the cut vertices of the network. The result shows that the existing infrastructure in Palapa Ring comprised 48 nodes and 117 links. The nodes with the highest degree in the network were PBR, PTK, BJM, JK, SB, and UP, with each of the nodes connected to four links. Cut vertices in the network consisted of 22 nodes. The nodes in the network are classified into four categories. Five nodes (PBR, PTK, BJM, SB, and UP) fell into the 1st priority group, two nodes (JK, MDN) fell into the 2nd priority group, 16 nodes fell into the 3rd priority group and the rest fell into the non-priority group.

## Keywords: Palapa Ring, Bottleneck, Node Priority, Cut Vertex, Node Degree

## ABSTRAK
Palapa Ring adalah proyek yang bertujuan untuk menghubungkan provinsi dan kota di Indonesia melalui jalur  telekomunikasi  berkecepatan  tinggi  data.  Tujuan  dari  penelitian  penelitian  ini  adalah  untuk mengidentifikasi  skala  prioritas  dari  setiap  node  di  jaringan  backbone  Palapa  Ring  dengan mempertimbangkan  derajat  setiap  node  dan  cut  vertex  pada  jaringan.  Hasilnya  menunjukkan  bahwa infrastruktur yang ada di Palapa Ring terdiri dari 48 node dan 117 link. Node dengan derajat tertinggi dalam jaringan adalah PBR, PTK, BJM, JK, SB dan UP, dengan masing-masing node terhubung ke empat link.  Cut  vertex  pada  jaringan  merupakan  himpunan  yang  terdiri  dari  22  node.  Node  dalam  jaringan diklasifikasikan ke dalam 4 kategori. Lima node (PBR, PTK, BJM, SB, dan UP) masuk ke dalam kelompok prioritas  pertama,  dua  node  (JK,  MDN)  masuk  ke  dalam  kelompok  prioritas  kedua,  16  node  masuk  ke dalam kelompok prioritas ketiga dan sisanya jatuh ke dalam kelompok non prioritas.
Kata Kunci:  Palapa Ring, Bottleneck, Prioritas Node, Cut Vertex, Derajat Node

## 1. PENDAHULUAN
Jaringan  Palapa  Ring  adalah  jaringan  data kecepatan tinggi  yang  direncanakan  untuk  menghubungkan   33 provinsi di Indonesia menggunakan kabel serat optik. Backbone  Palapa  Ring  direncanakan  mempunyai kapasitas  320  GBPS  [1].    Infrastruktur  direncanakan dibangun    dengan  kerja  sama  antara  pemerintah  dan
operator telekomunikasi, yaitu PT Telkom, PT Indosat dan PT Excelcomindo Pratama[2, 3].
Perencanaan  pembangunan  Palapa  Ring  per  tahun 2015  dapat  dilihat  pada  Gambar  1.  Jalur  yang berwarna  biru  adalah  jalur  serat  optik  yang  sudah terpasang  per  tahun  2015  .  Jalur  yang  berwarna lainnya adalah jalur yang direncanakan akan dibangun oleh  pihak  operator  telekomunikasi  (merah)  dan
pemerintah  (kuning  dan  oranye).  Penelitian  ini menggunakan  data  jalur  yang  sudah  terpasang  per tahun  2015.  Topologi  backbone  palapa  ring  yang sudah  terpasang  per  tahun  2015  dapat  dilihat  pada Gambar 2.
Gambar 1 Proyek Palapa Ring [3]
Gambar 2 Palapa Ring Per Tahun 2015[2]
Penentuan bottleneck pada sebuah jaringan diperlukan untuk  menentukan  skala  prioritas  node-node  dalam jaringan.  Salah  satu  cara  yang  umum  untuk mengidentifikasi  bottleneck  dalam  sebuah  jaringan adalah  dengan  menggunakan  cut  vertex  [4-6].  Cut vertex  adalah  kelompok  node  dalam  sebuah  graph, yang  apabila  dikeluarkan  dari  graph  tersebut  akan mengakibatkan terjadinya partisi[7]. Selain mempunyai  peran  yang  besar  dalam  menentukan konektivitas  dalam  jaringan,  dalam  sebuah  jaringan telekomunikasi  node-node  yang  termasuk  dalam kelompok  cut  vertex  juga  pada  umumnya  berperan besar  dalam  menyalurkan  trafik  dari  sebuah  partisi jaringan ke partisi yang lain.
Selain  menggunakan  metode  cut  vertex  sebagai penentu  bottleneck  dalam  sebuah  jaringan,  metode umum  dalam  menentukan  bottleneck  pada  sebuah
jaringan  adalah  menggunakan  derajat  node-node dalam  jaringan  tersebut  [8].  Sebuah  node  yang terhubung ke banyak link (derajat tinggi) menyalurkan lebih  banyak  trafik  dari  node  yang  terhubung  ke sedikit link (derajat rendah).
Penelitian  ini  bertujuan  untuk  menentukan  prioritas node-node  pada  jaringan  Palapa  Ring  dengan mempertimbangkan bottleneck dalam jaringan berdasarkan  derajat  sebuah  node  dan  apakah  node tersebut  merupakan  cut  vertex  dalam  jaringan. Berdasarkan  data  topologi  jaringan  Palapa  Ring, penelitian  ini  kemudian  akan  mengelompokan  node- node yang ada dalam empat kelompok prioritas.
Struktur  penulisan  paper  ini  sebagai  berikut.  Bagian pertama  mendiskusikan  latar  belakang  dan  tujuan dilakukannya  penelitian.  Bagian  kedua  membahas metode  penelitian  meliputi  blok  diagram  penelitian dan  kriteria  untuk  menentukan  kelompok  prioritas node  dalam  jaringan  Palapa  Ring.  Bagian  3 menyajikan  hasil  penelitian  dan  pembahasan,  diikuti oleh kesimpulan disajikan di bagian 4.

## 2. METODE PENELITIAN

## 2.1. Blok Diagram Penelitian
Secara  umum  langkah  kerja  dalam  penelitian  ini dibagi dalam 3 bagian seperti terlihat pada Gambar  3.
Pada  bagian  pertama,  peta  jaringan  backbone  palapa ring  direpresentasikan  dalam  bentuk  Graph  G(N,  L). N  adalah  himpunan  node  yang  ada  pada  graph merepresentasikan kota yang tergabung pada jaringan backbone  Palapa  Ring.  L  adalah  link  antar  node merepresentasikan  hubungan  serat  optic  yang menghubungkan  kota-kota  yang  tergabung  pada jaringan  backbone  Palapa  Ring.    Keterhubungan dalam Graph G(N,L) direpresentasikan dalam sebuah matriks  yang  dinamakan  matriks  Adjacency.  Tahap berikutnya adalah visualisasi Graph G(N,L)
Pada  bagian  kedua,  dilakukan  perhitungan  elemen- elemen  yang  menjadi  kriteria  penentuan  prioritas sebuah  node,  yaitu  derajat  dari  node  tersebut  dan apakah node tersebut merupakan cut vertex pada graph (N,L)
Pada  bagian  ketiga,  berdasarkan  hasil  pada  bagian kedua ditentukan prioritas setiap node dalam jaringan. Hasil klasifikasi node itu kemudian ditampilkan dalam bentuk visual dengan penggunaan warna yang berbeda untuk node dengan prioritas yang berbeda.

## Gambar Blok  Diagram Penelitian
Perangkat  lunak  yang  digunakan  dalam  penelitian adalah MATLAB R2011.

## 2.2. Kriteria Prioritas Node dalam Jaringan BackBone Palapa Ring.
Dalam  penelitian  ini  digunakan  2  kriteria  yang menentukan tingkat prioritas dari sebuah node sebagai berikut
● Derajat node , merupakan jumlah link yang terhubung  node  tersebut.  Semakin  banyak link  yang  terhubung  dengan  sebuah  node semakin tinggi Prioritas sebuah node
● Cut  Vertex, merupakan  node  yang  apabila dikeluarkan  dari  graph  akan  menciptakan partisi  dalam  graph.  Node  yang  merupakan cut  vertex  memiliki  prioritas  yang  lebih tinggi  dari  node  yang  bukan  merupakan  cut vertex.
Node  dalam  jaringan  akan  diklasifikasikan  dalam empat skala prioritas sebagai berikut
● Prioritas 1 adalah node-node dengan derajat yang tinggi dan merupakan cut vertex
● Prioritas 2 adalah node-node dengan derajat yang sedang dan merupakan cut vertex atau dengan  derajat  yang  tinggi  tetapi  bukan  cut vertex ● Prioritas 3 adalah node-node dengan derajat yang rendah tetapi merupakan cut vertex
● Non-Prioritas  adalah  node-node  dengan derajat  yang  rendah  dan  bukan  merupakan cut vertex.

## 3. HASIL DAN PEMBAHASAN
3.1. Konektivitas  Node  Jaringan  Backbone Palapa Ring.
Berdasarkan  Gambar  1,    backbone  jaringan  palapa ring  terdiri  dari  48  node  dan  117  link.  Tabel  1 menunjukan setiap node dan kota yang direpresentasikannya.
Tabel  1  Node  dan  Kota  pada  Jaringan  Backbone Palapa Ring Nod e Kota Nod e Kot a Nod e Kota 1  BNA 17  BJM 33  ML 2  SM 18  TGT 34  JR 3 MD N 19  BPP 35  BW 4  PD 20  SMP 36  DPR 5  PBR 21  TAR 37  MTR 6  DM 22  JK 38 BM A 7  BTM 23  CKP 39  PGU 8  JB 24  BDG 40 BW A 9  PG 25  CRB 41  KP 10  BTA 26 PW T 42  UP 11  BDL 27  PKL 43  KDI 12  IJN 28  SM 44  PRE 13  SBS 29  YK 45  PAL 14  PTK 30  SLO 46  PRG 15  KTP 31  MN 47  TMB 16  PLK 32  SB 48  MO
Matriks  keterhubungan  antar  node  dalam  adalah matriks dengan ukuran 48 x 48 dengan 117 dari 2304 elemennya bernilai 1 dan elemen lainnya bernilai 0.
Visualisasi graph dari jaringan backbone Palapa Ring dapat dilihat pada Gambar 4, Gambar 5 dan Gambar 6.
Gambar 4 Visualisasi Graph Node Sumatra
Gambar 4 menunjukan graph node-node yang berada di Sumatera (warna merah). Terdapat 12 node di Pulau Sumatera dengan 3 node yang menghubungkan Pulau Sumatera  dan  pulau-pulau  lainnya  yaitu  node  BTM (Batam), node IJN dan node BDL (Bandar Lampung).
Gambar  5  menunjukan  node-node  yang  berada  di Kalimantan  (warna  hijau  cerah)  dan node-node  yang berada di Jawa (warna ungu). Di  Kalimantan terdapat 9 node, dimana terdapat 2 node yang menghubungkan Kalimantan  dengan  pulau-pulau  lainnya  Node PTK(Pontianak) terhubung dengan node BTM(Batam) dan node IJN. Node BJM (Banjarmasin) terhubung  dengan  node  SB(Surabaya)  dan  node UP(Makasar).  Di  Jawa  terdapat  14  node  dengan  2 node  yang  terhubung  dengan  pulau-pulau  lainnya. Node  JK  (Jakarta)  terhubung  dengan  node  IJN  dan BDL.  Node  SB  (Surabaya)  terhubung  dengan  node BJM dan UP.
Gambar 5 Visualisasi Graph Node Kalimantan dan Jawa
Gambar  6  menunjukan  node-node  yang  berada  pada Bali  Nusra  (warna  hijau  toska)  dan  Sulawesi  (warna abu-abu). Di Bali-Nusra terdapat 6 node dengan node DPR(Denpasar)  yang  terhubung dengan  node  di  luar kawasan Bali-Nusra yaitu node BW(Banyuwangi). Di Sulawesi terdapat 8 node, dengan node UP(Makasar) terhubung dengan node-diluar wilayah Sulawesi yaitu node BJM dan node SB.

## Gambar 6 Visualisasi Graph Node Bali Nusra dan Sulawesi
Dengan melihat jumlah node dan link tampak bahwa konektivitas  pada  backbone  jaringan  Palapa  Ring bersifat sparse (topologi  mesh  membutuhkan  2304 link).  Topologi  jaringan  merupakan  kombinasi  dari topologi  ring  dan  topologi  chain,  sehingga  perlu diidentifikasi  node-node  yang  dapat  menyebabkan terjadi partisi jaringan.

## 3.2. Kriteria Prioritas Node

## 3.2.1 Derajat Node
Derajat node adalah jumlah link yang terhubung pada sebuah node.Gambar 7 adalah potongan kode Matlab untuk menghitung derajat node-node yang tergabung dalam jaringan backbone Palapa Ring.
Gambar 7 Kode Matlab untuk Menentukan Derajat Node.
Matriks conn pada Gambar 6 adalah matriks adjacency dan  matriks  konektivitas  jaringan  backbone  Palapa Ring berukuran (48 x 48).  Apabila node i terhubung dengan node j maka conn(i,j)=1 . Matriks noden adalah matriks yang menyimpan nama kota yang direpresentasikan  oleh  setiap  node.    Matriks  degree adalah matriks dengan ukuran 48x1 yang menyimpan derajat dari setiap node di jaringan Palapa Ring. Pada jaringan Palapa Ring terdapat 6 node dengan derajat 1, 31 node dengan derajat 2, 5 node dengan derajat 3 dan 6 node dengan  derajat 4. Data lengkap derajat setiap node dapat dilihat pada Tabel 2.
Tabel 2 Derajat Node dalam Jaringan Palapa Ring
Nod e De g Nod e Deg Nod e Deg BNA 1 BJM 4 ML 2 LSM 2 TGT 2 JR 2 MDN 3 BPP 2 BW 2 PD 2 SMP 2 DPR 2 PBR 4 TAR 1 MTR 2 DMI 2 JK 4 BMA 2 BTM 2 CKP 2 PGU 2 JB 2 BDG 3 BWA 2 PG 3 CRB 3 KP 1 BTA 2 PWT 2 UP 4 BDL 3 PKL 2 KDI 1 IJN 2 SM 2 PRE 2 SBS 1 YK 2 PAL 2 PTK 4 SLO 2 PRG 2 KTP 2 MN 2 TMB 2 PLK 2 SB 4 MO 1 3.3. Cut  Vertex  dalam  Jaringan  Palapa Ring
Cut vertex adalah himpunan node-node yang apabila dikeluarkan  dari  graph  G(N,L)  akan  mengakibatkan partisi dalam graph.
Gambar  8  merupakan  potongan  kode  matlab  untuk menentukan cut vertex pada jaringan backbone Palapa Ring.  Matriks cut  vertex adalah  matriks  berukuran 1x48 yang pada mulanya bernilai 0. Matriks A adalah copy  matriks  konektivitas conn .  Untuk  menentukan apakah  sebuah  node i adalah  cut  vertex,  node i dikeluarkan  dari  matriks A ,  kemudian  di  cek konektivitas  node-node  yang  tersisa  pada  matriks A . Apabila  terjadi  partisi  dalam  graph,  maka  node I adalah cut vertex dan cut vertex(i) = 1.
Gambar  9  merupakan  fungsi  untuk  memeriksa konektivitas dalam sebuah graph.
Gambar 8 Kode Matlab Menentukan Cut Vertex
Gambar 9 Fungsi Matlab Cek Konektivitas.
Pada  jaringan  backbone  Palapa  Ring  terdapat  22  cut vertex seperti yang terlihat pada Tabel 3. Node dengan kolom  CV  bernilai  1  adalah  cut  vertex,  sedangkan dengan  kolom  CV  bernilai  0  bukan  merupakan  cut vertex.
Tabel  3  Cut  Vertex  Pada  Jaringan  Backbone  Palapa Ring
Nod e CV Nod e Deg Nod e Deg BNA 0 BJM 1 ML 1 LSM 1 TGT 1 JR 1 MDN 1 BPP 1 BW 1 PD 0 SMP 1 DPR 1 PBR 1 TAR 0 MTR 1 DMI 0 JK 0 BMA 1 BTM 0 CKP 0 PGU 1 JB 0 BDG 0 BWA 1 PG 0 CRB 0 KP 0 BTA 0 PWT 0 UP 1 BDL 0 PKL 0 KDI 0 IJN 0 SM 0 PRE 1 SBS 0 YK 0 PAL 1 PTK 1 SLO 0 PRG 1 KTP 0 MN 0 TMB 1 PLK 0 SB 1 MO 0 3.4. Klasifikasi Prioritas Node pada Jaringan Palapa Ring. Klasifikasi prioritas node dilakukan menurut pengelompokan pada bagian 2. 2. Kode Matlab untuk klasifikasi node dapat dilihat pada Gambar 10. Matriks dtinggi adalah  matriks  berukuran  1x48  yang menandakan  node-node  dengan  derajat  tinggi.  Jika node i mempunyai derajat tinggi maka dtinggi(i)=1 . Matriks dsedang adalah matriks berukuran 1x48 yang menandakan  node-node  dengan  derajat  sedang.  Jika node i
mempunyai derajat sedang maka dsedang(i)=1 .    Matriks p1 , p2 , p3 dan NP adalah matriks yang menyimpan node-node dengan Prioritas 1,  Prioritas  2,  Prioritas  3  dan  non-Prioritas  menurut aturan pada bagian 2.2.

## Gambar 10 Code Matlab Klasifikasi Node
Hasil  pengelompokan  prioritas  node  dalam  jaringan Palapa Ring dapat dilihat pada Tabel 4.
Tabel 4 Prioritas Node pada Palapa Ring
Node Priorita s Nod e Priorita s Nod e Priorita s BNA NP BJM P1 ML P3 LSM P3 TGT P3 JR P3 MD N P2 BPP P3 BW P3 PD NP SMP P3 DPR P3 PBR P1 TAR NP MTR P3 DMI NP JK P2 BM A P3 BTM NP CKP NP PGU P3 JB NP BDG NP BW A P3 PG NP CRB NP KP NP BTA NP PWT NP UP P1 BDL NP PKL NP KDI NP IJN NP SM NP PRE P3 SBS NP YK NP PAL P3
PTK P1 SLO NP PRG P3 KTP NP MN NP TMB P3 PLK NP SB P1 MO NP
Visualisasi  graph  dengan node  prioritas  dapat dilihat pada Gambar 11, Gambar 12 dan Gambar 13.
Gambar 11 Visualisasi Prioritas Node Sumatera
Gambar 12 Visualisasi Prioritas Node di Kalimantan dan Jawa
Gambar 13 Visualisasi Prioritas Node di Bali Nusra dan Sulawesi
Node dengan Prioritas 1 ditandai dengan warna hijau terang, node dengan Prioritas 2 ditandai dengan warna merah, node dengan Prioritas 3ditandai dengan warna hijau  toska  dan  node  non  Prioritas  ditandai  dengan warna  biru.  Dari  visualisasi  dapat  dilihat  empat  dari node  Prioritas  1  berada  di  wilayah  Kalimantan  dan Jawa, 1 node Prioritas 1 berada di Sumatera dan 1 di Sulawesi. Node prioritas 3 (cut vertex dengan derajat kecil) sebagian besar berada pada wilayah Bali Nusra, dimana  topologi  jaringan  backbone  pada  wilayah tersebut berupa topologi rantai (chain). Pada wilayah Sumatera  dan  Jawa  tidak  terdapat  banyak  cut  vertex karena  topologi  jaringan  didominasi  oleh  topologi ring.    Ring  BJM,  SB,  UP  merupakan  topologi  ring yang anggotanya adalah node-node Prioritas 1.

## 4. KESIMPULAN
Jaringan  backbone  palapa  ring  yang  telah  terpasang per tahun 2015 terdiri dari 48 node yang dihubungkan oleh 117 link. Topologi jaringan merupakan gabungan dari  topologi  ring  dan  topologi  rantai.  Konektivitas
antar node bersifat sparse dengan 46% dari node pada jaringan Palapa Ring adalah cut vertex.
Berdasarkan  derajat  node  dan  cut  vertex  dalam jaringan, node pada jaringan Palapa Ring
dikelompokan  ke  dalam  empat  kelompok  prioritas. Terdapat lima node yang termasuk kelompok Prioritas 1,  yaitu  Pekanbaru  (PBR),  Pontianak  (PTK), Banjarmasin (BJM), Surabaya(SB) dan Makasar(UP).
Terdapat  2  node  dalam  kelompok  Prioritas  2,  yaitu Medan(MDN)  dan  Jakarta  (JK).  Pada  kelompok Prioritas 3 dan Non Prioritas masing-masing terdapat 16 dan 25 node.

## DAFTAR PUSTAKA
[1] B.  Y.  Iskandar,  "Indonesia’s  Initiative  to Deploy  NGN,"  in 7th  Global  Symposium Regulator  2007,  The  Road  to  Next- Generation Networks (NGN): Can Regulators  Promote  Investment  and  Open Access , 2007. [2] -,  "Indonesian  Domestic  Broadband,"  D.  K.
d. Informasi, Ed., ed, 2015.
[3] I.  K.  Rohman,  "Review  of  Indonesian broadband  development,"  Technical  report,
LIRNEasia2014.
[4] M.  Brazil,  C.  J.  Ras,  and  D.  A. Thomas,  "The  bottleneck  2- connected  k-Steiner  network p roblem  for  k≤  2," Discrete  Applied Mathematics, vol. 160, pp. 1028-1038, 2012.
[5] M.  Kim  and  K.  S.  Candan,  "SBV-Cut: Vertex-cut  based  graph  partitioning  using structural balance vertices," Data & Knowledge  Engineering, vol.  72,  pp.  285- 303, 2012.
[6] C.-P.  Schnorr,  "Bottlenecks  and  edge connectivity  in  unsymmetrical  networks," SIAM Journal on Computing, vol. 8, pp. 265- 274, 1979.
[7] D.  W.  Matula  and  F.  Shahrokhi,  "Sparsest cuts  and  bottlenecks  in  graphs," Discrete
Applied  Mathematics, vol.  27,  pp.  113-123,
1990. [8] A. Vespignani, "Modelling dynamical processes in complex socio-technical systems," Nature physics, vol. 8, p. 32, 2012.