Aplikasi Graf dalam Jaringan Komputer Penulis: Albert – NIM: 13506016 Program Studi Teknik Informatika, Institut Teknologi Bandung Jl. Ganesha 10, Bandung Email:
[email protected]
Abstrak - Makalah ini membahas tentang salah satu aplikasi graf dalam kehidupan, yaitu dalam jaringan komputer, termasuk di dalamnya, jaringan internet (world wide web). Matematika Diskrit, dalam kasus ini khususnya bidang graf, sangat berguna dalam kehidupan kita. Dalam kehidupan sehari-hari, terdapat banyak persoalan yang dapat diselesaikan dengan teori graf. Penggunaan teori graf sendiri tidak hanya mencakup bidang informatika saja, melainkan juga bidang ilmu lain, seperti elektro, kimia, dan bahkan sosial. Akan tetapi, dalam makalah ini, penulis akan memfokuskan pembahasan dalam bidang informatika, khususnya jaringan komputer. Dalam topik ini, kita akan menggambarkan jaringan komputer sebagai sebuah graf. Suatu komputer dalam sebuah jaringan akan dianggap sebagai suatu simpul, sedangkan kabel atau penghubung antar komputer dianggap sebagai sisi graf. Pada internet, terdapat pula pandangan yang berbeda dengan yang sudah disebutkan di atas. Halaman suatu situs dapat pula dianggap sebagai simpul, sedangkan hyperlink dianggap sebagai sis. Karena internet merupakan sebuah jaringan komputer raksasa, maka graf yang mereprentasikannya juga akan jauh lebih besar daripada jaringan komputer biasa. Tujuan pembuatan makalah ini adalah agar pembaca dapat mengerti dan mereprentasikan jaringan komputer dalam bentuk graf. Dengan demikian, pembaca dapat lebih mengerti menenai aliran data dan juga hubungan antara satu komputer dengan komputer lain yang terjadi dalam suatu jaringan.
Kata Kunci: graf, graf berarah, network graph, jaringan komputer, jaringan internet
1. PENDAHULUAN Pada masa sekarang ini, jaringan komputer sudah sangat umum digunakan dalam berbagai aspek kehidupan masyarakat. Hampir setiap perusahaan atau institusi pasti memiliki jaringan komputer
yang berfungsi untuk mendukung aliran data dan informasi yang berlangsung dalam perusahaan tersebut. Internet yang sudah sangat umum digunakan oleh masyarakat pada zaman sekarang ini juga merupakan sebuah jaringan komputer raksasa yang terbentang di seluruh dunia. Internet banyak digunakan oleh banyak orang karena internet menjanjikan penghematan waktu dan kemudahan dalam melakukan berbagai hal, seperti: pencarian informasi, transaksi perbankan dan belanja online, permainan dan segala hiburan lainnya yang bersifat online, dan masih banyak lagi keuntungan lain yang dapat diberikan oleh internet. Oleh karena itu, pertubmbuhan jaringan internet sendiri sangatlah cepat, dan jumlah pengguna internet di seluruh dunia juga berlipat ganda dengan pesat.
Studi mengenai jaringan komputer ini sendiri juga semakin banyak dipelajari dan menjadi suatu topik yang menarik untuk dipelajari. Akan tetapi, karena perubahannya yang sangat pesat, orang-orang yang berusaha untuk melakukan studi-studi tersebut haruslah lebih sering memeriksa perkembangan baru apa saja yang telah terjadi dan diaplikasikan dalam jaringan komputer dan internet yang digunakan di dunia ini.
2. LANDASAN TEORI 2.1. Graf Berarah Kebanyakan aplikasi teori graf membutuhkan sebuah definisi dari sebuah graf mengenai sisi mana yang dituju. Sehingga memungkinkan adanya sebuah sisi dari ke , akan tetapi tidak perlu dari ke . Berikut ini adalah definisi formalnya:
A directed graph (often called a digraph for brevity's sake) is a pair where is a set of elements called vertices and is a subset of the set of all ordered pairs , where
and
are vertices. (An
element of Example
is called an edge of
).
dengan sebuah bilangan, yang disebut sebagai bobot dari sisi tersebut. Bobot dapat bernilai positif maupun negatif.
Here is the formal definition of the weight of a walk: Given a weighted directed graph with a weight function , the weight of a walk
Figure 2: A directed graph with and
Equation 1
can be drawn as shown here.
is defined as the sum
2.2. Definisi Berikut adalah kumpulan definisi yang berkaitan dengan graf berarah.
Equation 2 The distance
Graf merupakan sesuatu yang sangat penting dalam jaringan, dimana objek utamanya adalah kumpulan simpul dengan hubungan satu atau dua arh di antara simpul-simpul tersebut. Many definitions from undirected graph theory have digraph-analogues: 1. The out-degree of a vertex is the number for all . of edges 2. The in-degree of a vertex is the number of edges for all . 3. Recall that in undirected graphs, a walk from vertex to a vertex is an alternating finite sequence of vertices and edges such that either or . 4. In directed graphs, a directed walk from vertex to a vertex is an alternating finite sequence of vertices and edges such that 5. A directed path is a directed walk which does not repeat any vertex. 6. A directed cycle is a directed walk which does not repeat any vertex except for the first and the last.
from
to
is defined by
Equation 3 if no directed walk from to to a directed walk from
exists
2.3.1. Algoritma Bellman-Ford Algoritma Bellman-Ford dapat menyelesaikan problem single-source shortest-path. Algoritma ini memperbolehkan sisi berbobot negatif, tapi tidak memperbolehkan graf berarah bersiklus yang mempunyai bobot negatif. Algoritma Bellman-Ford menghasilkan nilai false, yang menjawab bahwa tidak ada solusi yang memenuhi, yaitu jika menemukan cycle of negative weight yang bisa dicapai dari source. Sebaliknya algoritma Bellman-Ford mengembalikan true jika sudah menemukan semua jalur terpendek dari source. Algoritmanya: 1.
is the current estimate of the weight from vertex to vertex .
2.
is a predecessor of . In other words, the vertex through which the shortest distance from to was established.
for each vertex 2.3. Lintasan Terpendek Tahap selanjutnya dalam generalisasi teori sebuah graf adalah untuk mempertimbangkan graf berbobot, yang mana setiap sisi diasosiasikan
is
for for each edge
if
for each edge if return false; return true;
2.3.2. Algoritma Djikstra Algoritma Djikstra dapat menyelesaikan pencarian jarak terpendek dalam single-source problem pada graf berbobot (berarah atau tidak berarah), jika bobot dari sisi adalah positif. Algoritma Djikstra mempertahankan sejumlah verteks terpendek yang sudah dihitung sebelumnya, bersama complementary set of vertices yang bobot jalur terpendeknya belum ditetapkan. Algoritma ini secara berulang memilih verteks dengan bobot jalur terpendek minimal diantara verteks yang lain yang bobotnya belum ditentukan. Algoritma ini mengupdate bobot yang diperkirakan untuk semua verteks yang bertetangga (update ini umumnya disebut "relaxation" dari sisi diantara verteks ini). Kemudian verteks ini dijumlahkan dengan verteksverteks sebelumnya yang bobot jalur terpendeknya sudah dikalkulasi. Algoritma ini berlanjut sampai semua bobot jalur terpendek vertices sudah dikalkulasi (sampai set vertices yang bobot jalur terpendeknya belum ditentukan menjadi kosong). Algoritmanya: 1. 2.
is the set of vertices for which the has been computed. distance from to is the set of vertices for which the distance from to has not yet been computed.
3.
is the current estimate of the weight from vertex to vertex .
4.
is a predecessor of . In other words, the vertex through which was the shortest distance from to established.
while
{ Find
with the smallest for every
3.1. Pengertian Jaringan komputer adalah kumpulan komputer dan peralatan lainnya yang terhubung. Informasi dan data bergerak melalui kabel atau koneksi nirkabel lain, sehingga memungkinkan pengguna jaringan komputer untuk saling bertukar dokumen dan data, mencetak pada printer yang sama, atau bersama sama menggunakan suatu hardware/software yang terhubung dengan jaringan. Tiap komputer, printer, atau periferal yang terhubung dengan jaringan disebut node. Sebuah jaringan komputer dapat memiliki dua, puluhan, ribuan atau bahkan jutaan node. Sebuah jaringan terdiri dari 2 atau lebih komputer yang saling berhubungan diantara satu dengan yang lain, dan saling berbagi sumber daya seperti printer, pertukaran file, atau memungkinkan untuk saling berkomunikasi secara elektronik. Komputer yang terhubung tersebut, dimungkinkan berhubungan dengan media kabel, saluran telepon, gelombang radio, satelit, atau sinar infra merah. 3.2. Jenis-jenis Jaringan Komputer a. Local Area Network (LAN) / Jaringan Area Lokal. Sebuah LAN, adalah jaringan yang dibatasi oleh area yang relatif kecil, umumnya dibatasi oleh area lingkungan seperti sebuah perkantoran di sebuah gedung, atau sebuah sekolah, dan biasanya tidak lebih dari sekitar 1 km persegi. Beberapa model konfigurasi LAN, satu komputer biasanya di jadikan sebuah file server. Yang mana digunakan untuk menyimpan perangkat lunak (software) yang mengatur aktifitas jaringan, ataupun sebagai perangkat lunak yang dapat digunakan oleh komputerkomputer yang terhubung ke dalam network. Komputer-komputer yang terhubung ke dalam jaringan (network) itu biasanya disebut dengan workstation. Biasanya kemampuan workstation lebih di bawah dari file server dan mempunyai aplikasi lain di dalam harddisknya selain aplikasi untuk jaringan. Kebanyakan LAN menggunakan media kabel untuk menghubungkan antara satu komputer dengan komputer lainnya. b. Metropolitan Area Network (MAN) / Jaringan area Metropolitan Sebuah MAN, biasanya meliputi area yang lebih besar dari LAN, misalnya antar wilayah dalam satu propinsi. Dalam hal ini jaringan menghubungkan beberapa buah jaringan-jaringan kecil ke dalam lingkungan area yang lebih besar, sebagai contoh yaitu : jaringan Bank dimana beberapa kantor cabang sebuah Bank di dalam sebuah kota besar dihubungkan antara satu dengan lainnya. Misalnya Bank BNI yang ada di seluruh wilayah Ujung Pandang atau Surabaya.
if
3. JARINGAN KOMPUTER
c. Wide Area Network (WAN) / Jaringan area Skala Besar Wide Area Networks (WAN) adalah jaringan yang lingkupnya biasanya sudah menggunakan sarana Satelit ataupun kabel bawah
laut sebagai contoh keseluruhan jaringan BANK BNI yang ada di Indonesia ataupun yang ada di Negara-negara lain. Menggunakan sarana WAN, Sebuah Bank yang ada di Bandung bisa menghubungi kantor cabangnya yang ada di Hongkong, hanya dalam beberapa menit. Biasanya WAN agak rumit dan sangat kompleks, menggunakan banyak sarana untuk menghubungkan antara LAN dan WAN ke dalam Komunikasi Global seperti Internet. Tapi bagaimanapun juga antara LAN, MAN dan WAN tidak banyak berbeda dalam beberapa hal, hanya lingkup areanya saja yang berbeda satu diantara yang lainnya. 3.3. Topologi / Bentuk Jaringan Topologi suatu jaringan didasarkan pada cara penghubung sejumlah node atau sentral dalam membentuk suatu sistem jaringan. Topologi jaringan yang umum dipakai adalah: Mess, Bintang (Star), Bus, Tree, dan Cincin (Ring).
b. Topologi Jaringan Bintang (Star) Dalam topologi jaringan bintang, salah satu sentral dibuat sebagai sentral pusat. Bila dibandingkan dengan sistem mesh, sistem ini mempunyai tingkat kerumitan jaringan yang lebih sederhana sehingga sistem menjadi lebih ekonomis, tetapi beban yang dipikul sentral pusat cukup berat. Dengan demikian kemungkinan tingkat kerusakan atau gangguan dari sentral ini lebih besar. c. Topologi Jaringan Bus Pada topologi ini semua sentral dihubungkan secara langsung pada medium transmisi dengan konfigurasi yang disebut Bus. Transmisi sinyal dari suatu sentral tidak dialirkan secara bersamaan dalam dua arah. Hal ini berbeda sekali dengan yang terjadi pada topologi jaringan mesh atau bintang, yang pada kedua sistem tersebut dapat dilakukan komunikasi atau interkoneksi antar sentral secara bersamaan. Topologi jaringan bus tidak umum digunakan untuk interkoneksi antar sentral, tetapi biasanya digunakan pada sistem jaringan komputer. d. Topologi Jaringan Pohon (Tree) Topologi jaringan ini disebut juga sebagai topologi jaringan bertingkat. Topologi ini biasanya digunakan untuk interkoneksi antar sentral dengan hirarki yang berbeda. Untuk hirarki yang lebih rendah digambarkan pada lokasi yang rendah dan semakin keatas mempunyai hirarki semakin tinggi. Topologi jaringan jenis ini cocok digunakan pada sistem jaringan komputer .
Gambaran lain jenis-jenis topologi jaringan
a. Topologi Jaringan Mesh Topologi jaringan ini menerapkan hubungan antar sentral secara penuh. Jumlah saluran harus disediakan untuk membentuk jaringan Mesh adalah jumlah sentral dikurangi 1 (n-1, n = jumlah sentral). Tingkat kerumitan jaringan sebanding dengan meningkatnya jumlah sentral yang terpasang. Dengan demikian disamping kurang ekonomis juga relatif mahal dalam pengoperasiannya.
e. Topologi Jaringan Cincin (Ring) Untuk membentuk jaringan cincin, setiap sentral harus dihubungkan seri satu dengan yang lain dan hubungan ini akan membentuk loop tertutup. Dalam sistem ini setiap sentral harus dirancang agar dapat berinteraksi dengan sentral yang berdekatan maupun berjauhan. Dengan demikian kemampuan melakukan switching ke berbagai arah sentral. Keuntungan dari topologi jaringan ini antara lain : tingkat kerumitan jaringan rendah (sederhana), juga bila ada gangguan atau kerusakan pada suatu sentral maka aliran trafik dapat dilewatkan pada arah lain dalam sistem. Yang paling banyak digunakan dalam jaringan komputer adalah jaringan bertipe bus dan pohon (tree), hal ini karena alasan kerumitan, kemudahan instalasi dan pemeliharaan serta harga yang harus dibayar.
Tapi hanya jaringan bertipe pohon (tree) saja yang diakui kehandalannya karena putusnya salah satu kabel pada client, tidak akan mempengaruhi hubungan client yang lain. 3.4. Protokol Protokol adalah aturan-aturan main yang mengatur komunikasi diantara beberapa komputer di dalam sebuah jaringan, aturan itu termasuk di dalamnya petunjuk yang berlaku bagi cara-cara atau metode mengakses sebuah jaringan, topologi fisik, tipe-tipe kabel dan kecepatan transfer data. ProtokolProtokol yang dikenal adalah sebagai berikut: 1. Ethernet 2. Local Talk 3. Token Ring 4. FDDI 5. ATM Ethernet Protocol Ethernet sejauh ini adalah yang paling banyak digunakan, Ethernet menggunakan metode akses yang disebut CSMA/CD (Carrier Sense Multiple Access/Collision Detection). Sistem ini menjelaskan bahwa setiap komputer memperhatikan ke dalam kabel dari network sebelum mengirimkan sesuatu ke dalamnya. Jika dalam jaringan tidak ada aktifitas atau bersih computer akan mentransmisikan data, jika ada transmisi lain di dalam kabel, komputer akan menunggu dan akan mencoba kembali transmisi jika jaringan telah bersih. kadangkala dua buah komputer melakukan transmisi pada saat yang sama, ketika hal ini terjadi, masing-masing komputer akan mundur dan akan menunggu kesempatan secara acak untuk mentransmisikan data kembali. metode ini dikenal dengan koalisi, dan tidak akan berpengaruh pada kecepatan transmisi dari network. Protokol Ethernet dapat digunakan untuk pada model jaringan Garis lurus, Bintang, atau Pohon . Data dapat ditransmisikan melewati kabel twisted pair, koaksial, ataupun kabel fiber optic pada kecepatan10 Mbps.
LocalTalk LocalTalk adalah sebuh protokol network yang di kembangkan oleh Apple Computer, Inc. untuk mesin-mesin komputer Macintosh. Metode yang digunakan oleh LocalTalk adalah CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance). Hampir sama dengan CSMA/CD. Adapter LocalTalk dan cable twisted pair khusus dapat digunakan untuk menghubungkan beberapa computer melewati port serial. Sistem Operasi Macintosh memungkinkan koneksi secara jaringan peer-to-peer tanpa membutuhkan tambahan aplikasi khusus Protokol LocalTalk dapat digunakan untuk model jaringan Garis Lurus, Bintang, ataupun model Pohon dengan menggunakan kabel twisted pair. Kekurangan yang paling mencolok yaitu kecepatan transmisinya. Kecepatan transmisinya hanya 230 Kbps. Token Ring Protokol Token di kembangkan oleh IBM pada pertengahan tahun 1980. Metode Aksesnya melalui lewatnya sebuah token dalam sebuah lingkaran seperti Cincin . Dalam lingkaran token, komputerkomputer dihubungkan satu dengan yang lainnya seperti sebuah cincin. Sebuah Sinyal token bergerak berputar dalam sebuah lingkaran (cincin) dalam sebuah jaringan dan bergerak dari sebuah komputer-menuju ke komputer berikutnya, jika pada persinggahan di salah satu komputer ternyata ada data yang ingin ditransmisikan, token akan mengangkutnya ke tempat dimana data itu ingin ditujukan, token bergerak terus untuk saling mengkoneksikan diantara masing-masing komputer. Protokol Token Ring membutuhkan model jaringan Bintang dengan menggunakan kabel twisted pair atau kabel fiber optic. Dan dapat melakukan kecepatan transmisi 4 Mbps atau 16 Mbps. Sejalan dengan perkembangan Ethernet, penggunaan Token Ring makin berkurang sampai sekarang. FDDI Fiber Distributed Data Interface (FDDI) adalah sebuah Protokol jaringan yang menghubungkan antara dua atau lebih jaringan bahkan pada jarak yang jauh . Metode aksesnyayang digunakan oleh FDDI adalah model token. FDDI menggunakan dua
buah topologi ring secara fisik. Proses transmisi baiasanya menggunakan satu buah ring, namun jika ada masalah ditemukan akan secara otomatis menggunakan ring yang kedua. Sebuah keuntungan dari FDDI adalah kecepatan dengan menggunakan fiber optic cable pada kecepatan 100 Mbps.
4. JARINGAN INTERNET Keadaan sekeliling atau lingkungan dari Internet berbeda dengan jaringan computer biasa: 1. Links dan routers tidak dapat dipercaya. 2. Jalur alternatif sulit didapat. 3. Pola dari lalu lintas di internet berubah dengan tidak terprediksi dalam hitungan menit. Strategi routing pada lingkungan yang yang memiliki karakteristik seperti yang telah disebutkan di atas harus memiliki lebih banyak toleransi pada perubahan pada jaringan daripada strategi untuk jaringan telepon atau computer biasa. Dua dasar dari algoritma routing pada packet-switched network (Internet dan jaringan ATM) adalah: 1. Distance-Vector (berdasarkan pada BellmanFord Algorithm). 2. Link-State (berdasarkan pada Djikstra’s Algorithm). 4.1. Distance-Vector Routing Distance-vector routing menghasilkan asumsi sebagai berikut: “Each router knows the identity of every other router in the network.”
ATM ATM adalah singkatan dari Asynchronous Transfer Mode (ATM) yaitu sebuah protokol jaringan yang mentransmisikan pada kecepatan 155 Mbps atau lebih. ATM mentarnsmisikan data kedalam satu paket dimana pada protokol yang lain mentransfer pada besar-kecilnya paket. ATM mendukung variasi media seperti video, CD-audio, dan gambar. ATM bekerja pada model topologi Bintang, dengan menggunakan Kabel fiber optic ataupun kabel twisted pair. ATM pada umumnya digunakan untuk menghubungkan dua atau lebih LAN. dia juga banyak dipakai oleh Internet Service Providers (ISP) untuk meningkatkan kecepatanakses Internet untuk klien mereka.
Dalam usaha untuk menguatkan asumsi ini, setiap router akan mempertahankan sebuah distance vector, yang tersusun dari list of tuples: <destination, cost> untuk setiapsimpul pada jaringan. Dalam kasus ini, cost merupakan perkiraan akan jalur terpendek dari router tersebut ke tujuannya; perkiraan tersebut tidak pernah lebih kecil daripada panjang jalur sebenarnya. Algoritma Distance-Vector merupakan sebuah implementasi terdistribusi dari algoritma BellmanFord: 1. Setiap router secara periodik mengirim copy dari distance vector dirinya ke tetangganya. 2. Pada saat router menerima distance-vector dari tetangga, dia memutuskan apabila jarak untuk mencapai suatu destinasi akan menurun jika paket ke destinasi tersebut akan dikirim melalui tetangganya tersebut. 3. Jika menurun, router tersebut meng-update distance-vector dirinya sendiri.
4.2. Link-State Routing Pada distance-vector routing, informasi tentang topologi jaringan didistribusikan diantara routers, sehingga akan menghasilkan efisiensi tetapi juga mengakibatkan masalah. Sebuah pendekatan alternative, yang digunakan dalam link-state routing, adalah untuk memberi informasi lengkap mengenai graf dari jaringan tersebut kepada tiap router. Setelah itu, setiap router secara independen menghitung jalur yang optimal ke semua tujuan. Topology Dissemination Algoritma Link-state secara periodik akan mendistribusikan link-state packets (LSPs), yang dikembangkan pada setiap router yang berpartisipasi di sebuah jaringan. Isi dari sebuah LSP antara lain adalah: 1. ID Router tersebut. 2. ID salah satu tetangga dari sebuah router. 3. Panjang lintasan dari link ke tetangga tersebut. (Setiap router akan mengirim sejumlah LSP sesuai dengan jumlah tetangga yang dimiliki oleh router tersebut.)
Pada saat sebuah router menerima LSP, router itu akan mencoba untuk menyimpannya pada database LSP miliknya. Jika informasi tersebut berisi data yang sudah ada pada databasenya, tidak ada aksi yang akan dilakukan. Jika belum ada, router itu akan menyimpan data tersebut dalam databasenya dan meneruskan copy dari LSP yang baru dia terima ke setiap router tetangga (kecuali kepada router yang telah mengirim paket tersebut) Pada saat sebuah router dalam sebuah jaringan mempunyai LSP database yang konsisten, tiap router secara individual menghiutng jalur yang optimal ke semua simpul jaringan. Algoritma yang biasa digunakan untuk melakukan hal ini adalah algoritma Djikstra.
5. HASIL DAN PEMBAHASAN Melalui makalah ini, kita dapat mengetahui bahwa teori graf memang digunakan dalam jaringan komputer dan jaringan internet yang ada sekarang. Sebagai simulasi, akan ditampilkan sebuah gambar yang akan meremprntasikan peta jaringan internet. Gambarnya adalah sebagai berikut:
Karena gambar yang ditampilkan di dalam makalah ini tidak bisa terlalu besar, kemungkinan hasilnya kurang begitu jelas. Oleh karena itu, penulis telah mengupload gambar tersebut, dan soft copy dari gambar internet map tersebut bisa diperoleh di: http://img149.imageshack.us/img149/7039/internet map1024ej2.jpg
6. KESIMPULAN Dari semua uraian di atas, kita dapat menyimpulkan bahwa teori graf memang digunakan dan sangat penting dalam jaringan komputer serta jaringan internet. Bahkan mungkin penggunaan teori graf ini juga akan semakin meluas lagi seiring dengan teknologi manusia yang semakin berkembang. Perkembangan teknologi yang sangat pesat ini akan menyebabkan kemajuan dalam bidang jaringan komputer serta internet, sehingga mengakibatkan aplikasi teori graf yang akan digunakan menjadi semakin beragam dan mencakup masalah-masalah yang mungkin untuk saat ini bahkan belum terpikirkan. Dengan demikian, teori graf, dan bidang matematika diskrit pada umumnya, akan menjadi sebuah aspek yang penting bagi kemajuan ilmu pengetahuan dan teknologi.
DAFTAR REFERENSI http://www.hi-technews.net/articles/?c=Topic &id=6&pid=3 tanggal akses: 26 Desember 2007 http://www.ibiblio.org/links/devmodules/graph_net working/compat/page1.html tanggal akses: 26 Desember 2007 http://darto82.wordpress.com/2007/12/13/teknologi -jaringan-komputer/ tanggal akses: 26 Desember 2007 http://www.blogger.com/feeds/9970261253204196 34/posts/default tanggal akses: 26 Desember 2007
