Transparent Query Caching in Peer-to-Peer Overlay Networks

Transparent Query Caching in Peer-to-Peer Overlay Networks

Sunil Patro and Y. Charlie Hu

Purdue University

Penerjemah: Komarudin Tasdik (https://komarudintasdik.wordpress.com  )

Abstrak

Sistem peer-to-peer (p2p) seperti Gnutella dan Kazaa secara rutin digunakan oleh jutaan orang untuk berbagi musik dan banyak file melalui Internet, dan data itu menjadi bagian penting dalam Internet traffic. Internet traffic bisa dibagi ke dalam dua kategori: pesan protokol untuk pemeliharaan dan pencarian jaringan overlay p2p, dan pesan data untuk mendownload file-file data. Paper ini membahas dua kontribusi. Pertama, kami menyajikan kajian lokalitas dalam pesan-pesan protokol Gnutella query yang diinisiasi dan diforward servents di dalam organisasi yang sama. Kedua, kami mengusulkan skema query caching yang transparan untuk mereduksi bandwidth yang digunakan oleh p2p traffic yang berjalan di dalam dan di luar gateway sebuah organisasi.

Pengukuran lokalitas menampilkan bahwa terdapat lokalitas penting dalam query kolektif yang berjalan melalui gateway yang diforward oleh servents di belakang gateway, dan lokalitas itu bertambah dengan populasi servents. Skema caching transparan yang diusulkan kami memelihara pengalaman user, yaitu user terus menggunakan servent yang sama seperti sebelumnya, dan query akan berhasil dalam query yang mirip dengan atau tanpa menjalankan caching. Ukuran caching proxy transparan dalam experimental testbed delapan layanan Gnutella pasif dalam LAN yang menampilkan query cache dengan nilai mencapai 63%, reduksi query traffic mencapai 62%, dan downlink query dengan reduksi mencapai 12% pada gateway tersebut.

1 Pendahuluan

Pada enam tahun pertama ledakan Internet, satu jenis dominasi traffic melalui Internet telah mengalami HTTP traffic dari pengaksesan World Wide Web.     Sekitar tahun 2000, paradigma baru terhadap aplikasi-aplikasi Internet telah muncul dan berkembang pesat. Saat ini, sistem dan aplikasi yang disebut peer-to-peer (p2p) seperti Gnutella dan KaZaa secara rutin digunakan oleh jutaan orang untuk berbagi musik dan file-file lainnya di Internet, dan data itu termasuk bagian penting dari Internet traffic. Contohnya, ukuran network traffic berkelanjutan di University of Wisconsin (http://www.stats.net.wisc.edu) menampilkan bahwa peer-to peer traffic (KaZaa, Gnutella, dan eDonkey) terhitung 25-30% total campus traffic (di dalam dan di luar) pada Agustus 2002, sedangkan pada saat yang sama, web-related traffic terhitung sekitar 23% total traffic masuk dan 10% traffic keluar.

Untuk mereduksi penggunaan bandwidth dan latency dalam pengaksesan konten web, web caching telah dipelajari secara ekstensif. Saat ini, produk-produk web caching ditawarkan oleh sejumlah vendor dan tersebar luas di Internet, dan telah ditampilkan sangat efektif dalam mereduksi penggunaan network bandwidth dan latency akses. Berbeda dengan sedikit kemajuan yang telah dibuat menuju caching p2p network. Traffic itu dihasilkan oleh p2p network seperti Gnutella yang dibagi ke dalam dua kategori: pesan protokol untuk melakukan maintain pada overlay network dan untuk pencarian file-file data dalam overlay network, dan pesan data aktual untuk mendownload file. Sebelumnya, para peneliti telah menemukan bahwa pesan-pesan pencarian (query) dalam Gnutella network menampilkan lokalitas temporal, menyarankan bahwa caching harus terbukti menjadi teknik efektif dalam mereduksi network bandwidth yang digunakan oleh query-query ini dan latency dalam menemukan kembali balasan-balasan query. Beberapa skema query caching dikembangan dengan memodifikasi Gnutella servents, dan telah mengkonfirmasi keefektivan query caching. Maka, skema sebelumnya memiliki beberapa keterbatasan. Pertama dan sangat penting, skema-skema ini diusulkan dalam konteks memodifikasi Gnutella servents, dan mengandalkan pada adopsi besar dari servent yang dimodifikasi untuk memperoleh manfaat caching. Adopsi besar dari beberapa servent yang dimodifikasi berpotensi proses lambat. Satu alasan sederhana untuk ini adalah bahwa user digunakan untuk servent tertentu yang sedang mereka gunakan, karena kemampuan-kemampuan khususnya, GUIs, tergantung pada sistem operasi tertentu, dan sebagainya. Kedua, semua skema caching yang diusulkan sebelumnya diimplementasikan pada servent individu masing-masing, sehingga mereka tidak dapat mengeksploitasi lokalitas dalam query-query yang secara kolektif diforward atau diinisiasi oleh sekelompok servents, contohnya, di dalam organisasi yang sama.

Pada paper ini, kami mengeksplorasi skema query caching dalam p2p overlay network mengatasi keterbatasan yang disebutkan di atas. Pendekatan menyeluruh kami adalah untuk mengembangkan p2p caching proxy transparan yang akan dilampirkan ke gateway routers oganisasi atau ISP, yakni, seperti bagaimana web caching proxy tersebar secara khusus, dengan tujuan mereduksi p2p traffic di dalam dan di luar gateway. Gateway Cisco router (melebihi 80% router dalam Internet adalah Cisco router) yang menjalankan protokol WCCPv2 akan direduksi untuk mengalihkan arah TCP traffic ke port-port p2p yang sangat dikenal, contohnya, 6346 untuk Gnutella, untuk attached p2p caching proxy.

Kami fokus pada Gnutella network pada paper ini. Kontribusi khusus dari paper ini sebagai berikut:

  • Kami mengkaji lokalitas dalam query-qery yang diforward oleh servents di dalam sebuah gateway dan implikasi-implikasinya terhadap efektivitas caching pada gateway.
  • Kami mempresentasikan skema caching transparan yang memelihara pengalaman user p2p
  • Sejak Gnutella servents sering menggunakan port TCP yang sama untuk protokol dan data traffic, kami juga mempresentasikan skema untuk mengintegrasikan query caching proxy kami dengan beberapa HTTP caching proxy berkinerja tinggi off-the-shelf tanpa mengimplementasikan kembali satu ke yang lainnya, dan tanpa menggunakan biaya yang mahal.

Selanjutnya, paper ini diorganisir sebagai berikut. Bagian 2 memberikan gambaran umum tentang protokol Gnutella. Bagian 3 mempresentasikan ukuran yang diukur dalam pesan Gnutella query kolektif yang diobservasi pada gateway experimental testbed yang terdiri atas delapan Gnutella servents dalam sebuah LAN. Bagian 4 mempresentasikan dan mengevaluasi skema query caching kami. Bagian 5 mempresentasikan skema untuk mengintegrasikan skema query caching transparan kami dengan HTTP data caching untuk Gnutella network. Terakhir, Bagian 6 membahas karya terkait lainnya, dan Bagian 7 menyimpulkan paper ini.

2 Protokol Gnutella

Protokol Gnutella [1, 2] menetapkan operasi-operasi untuk melakukan maintain dan pencarian peer-to-peer overlay network yang berada di atas Internet. Gnutella peering nodes (disebut servents) berkoneksi dengan neighbor dekatnya menggunakan koneksi pont-to-point. Berikutnya, pertama mendeskripsikan bagaimana node baru berhubungan dengan Gnutella network yang ada, dan implikasi-implikasinya pada topologi yang dibentuk oleh servents di dalam sebuah organisasi. Kami kemudian secara singkat mendeskripsikan protokol untuk query request dan pesan respon, dan data file download.

Joining process dan implikasinya pada topologi

Kami mendeskripsikan joining process dari Gnutella servent khusus. Apapun host yang menjalankan servent dapat berkoneksi dengan Gnutella network. Ketika servent ingin berkoneksi, pertama melihat host cache-nya untuk menemukan address Gnutella servent agar bisa berkoneksi. Servent address dihapus dari host cache setelah dibaca. Jika host cache kosong, maka ia mencoba untuk berkoneksi ke Gnutella host cache server yang bagus (disebut juga PONG server) untuk menerima pesan-pesan PONG dalam merespon pesan PING-nya. Setelah menerima pesan-pesan PONG, servent mencoba untuk membangun koneksi dengan servent yang addressnya diperoleh dari pesan-pesan PONG.

Dalam Gnutella servent khusus, setelah pra penentuan jumlah koneksi Gnutella dibangun, servent mengirim pesan PING secara periodik untuk memonitor koneksi-koneksi itu dan dalam respon menerima sejumlah pesan PONG[1], yang ditambahkan pada ujung host cache. Tambahan pula, setelah koneksi dengan suatu servent yang ada dibagi-bagi, informasi alamat servent disimpan dan secepatnya ditambahkan ke host cache ketika servent meninggalkan Gnutella network.

Kesimpulannya, selama joining process Gnutella servent khusus, neighbor dipilih dari host cache yang kontennya acak wajar. Ini menyarankan bahwa ia tidak seperti servent dari organisasi sama akan menjadi neighbor masing-masing, bisa membuat kelompok sendiri, dan konsekuensinya, pesan-pesan query pasti akan melintasi gateway organisasi.

Query request and response. Untuk menempatkan file, servent mengirim query request ke semua direct neighbors-nya, yang pada gilirannya memforward query ke neighbors-nya, dan proses itu berulang. Ketika servent menerima query request, ia mencari file lokalnya untuk menyesuaikan ke query dan mengembalikan query response yang memuat semua kecocokan yang ia temukan. Query response mengikuti reverse path query request untuk menemukan servent yang diinisiasi query. Servent sepanjang path tidak melakukan cache pada query response.

Untuk menghindari query request dan response dari membanjiri network, tiap query mengandung bidang TTL (time to live), yang biasanya diinisiasi hingga 7 secara default. Ketika servent menerima query dengan TTL positif, ia mengurangi TTL sebelum memforward query ke neighbors-nya. Query diterima dengan TTL being 1 tidak diforwarded. Dengan kata lain, query dipropagasi dengan flooding terkontrol.

Mudah untuk melihat bahwa query yang sama dapat mengunjungi servent lebih dari sekali selama flooding terkontrol, yaitu, melalui neighbor yang berbeda dari servent. Untuk memastikan bahwa tiap node tidak melayani query sama lebih dari sekali, tiap query diidentifikasi dengan identifikasi unik yang disebut muid.

Ketika servent menerima query dengan muid yang telah bertemu di masa lalu, ia akan menghapus query secara sederhana. Sesungguhnya, copian yang diulang dari query yang sama tidak harus dihitung ketika mengukur lokalitas di antara sejumlah query.

Data file download. Setelah query masuk diterima oleh servent, user dapat memilih file untuk download. Permintaan download ini diselesaikan melalui pesan HTTP GET yang dikirim melalui koneksi TCP langsung antara merequest servent dan mereply servent.

3 Pengukuran Lokalitas

Pada bagian ini, kami mengkaji lokalitas dalam query yang diforward oleh sejumlah servent di samping gateway dan implikasinya terhadap efektivitas caching pada gateway.

3.1 Metodologi

Untuk memonitor traffic kolektif yang keluar dari sejumlah servents di balik router, kami telah mengimplementasikan tunneling probe yang berjalan pada FreeBSD machine yang dikonfigurasikan seperti pada Gambar 1. Pertama, probe machine diletakkan di depan gateway Cisco router yang menjalankan WCCPv2. Gateway router itu akan dikonfigurasikan untuk mengalihkan arah semua paket ke Gnutella port yang dikenali (contohnya, 6346) ke attached tunneling probe. Kedua, probe machine dikonfigurasikan untuk menggunakan IP selanjutnya untuk memindahkan arah semua TCP traffic ke tujuan lain dengan port 6346 ke port 6346 localhost, pada probe yang sedang melakukan listen. Ini memungkinkan probe untuk menghijack semua koneksi keluar dengan tujuan port 6346. Probe itu kemudian menginisiasi koneksi TCP ke tujuan asli, dan tunnel semua paket yang menuju ke dua arah, ke servent tujuan luar, probe machine muncul sebagai servent yang menginisiasi koneksi, sedangkan servent di dalam gateway yang menginisiasi koneksi TCP yang dianggap telah membangun koneksi TCP dengan tujuan servent. Dengan kata lain, menghijack koneksi TCP transparan ke servent di dalam gateway, tapi tidak ke servent di luar gateway.

Sedangkan melakukan tunneling Gnutella-traffic, probe mengumpulkan informasi tentang paket-paket yang ditunnel, seperti jenis pesan, ukuran, dan dengan istilah query, TTL, dan frekuensi. Kemudian informasi ini akan digunakan untuk menganalisis lokalitas dalam query request yang diforward atau diinisiasi oleh semua servent di dalam gateway seperti halnya data file download jika mereka menggunakan koneksi yang sama, yakni, dengan port 6346, ke servent tujuan.

Untuk memonitor Gnutella traffic yang berjalan melalui tiap Gnutella servent individu, kami telah membuat modifikasi untuk gtk-gnutella, unix-based open-source servent untuk Gnutella, untuk merekam semua pesan protokol dan data download di dalam dan luar servent.

Gambar 1. Tunneling probe yang berjalan pada PC dengan IP forwarding (disebut GW) menghijack koneksi keluar servent. Router bisa hilang jika servent dikonfigurasi untuk menggunakan GW sebagai default router-nya. Caching box yang dibahas dalam Bagian 4 menggantikan tunneling probe dengan query caching proxy.

Gambar 2. Konfigurasi measurement testbed. GW-2, GW-4, dan GW-8 menghijack koneksi keluar (dengan port tujuan 6346) dari Gnutella servent, dan tampil sebagai sumber koneksi ke luar servent.

Untuk menyederhanakan measurement setup, walaupun menggunakan real router, kami sudah mengkonfigurasikan masing-masing servent untuk menggunakan GW debagai default router (lihat Gambar 1). IP forwarding rules ditetapkan pada GW seperti paket-paket menuju port 6364 dari semua tujuan akan diforward ke port 6346 localhost, dan semua traffic lainnya diforward. Sehingga hanya koneksi Gnutella luar yang akan dihijack oleh tunneling probe.

3.2 Hasil Pengukuran

Kami mengukur lokalitas di antara delapan servent pasif yang berjalan pada cluster delapan PC selain router. Tiap servent dikonfigurasikan untuk memungkinkan empat koneksi masuk dan keluar. Tiap servent pasif, karena hanya memforward query dan query hits, tapi tidak menginisiasi query apapun. Lebih jauh, servent tidak menyimpan file apapun untuk sharing. Untuk mengukur lokalitas antar query dari sejumlah servent yang bermacam-macam, kami sudah mengkonfigurasikan tiga PC sebagai GW yang menjalankan tunneling probe, dan kami sudah mengkonfigurasikan semua testbed ke dalam sebuah hirarki seperti pada Gambar 2. GW-2, GW-4, dan GW-8 merupakan tiga GW, dan traffic pada koneksi keluar dari dua, empat, dan delapan servent semuanya berjalan melalui GW-2, GW-4, dan GW-8, secara respektif.

Gambar 3. Distribusi  persentase jenis yang berbeda dari pesan masuk dan keluar di GW-8 terletak pada koneksi keluar yang dihijack.

Kami memulai eksperimen dengan delapan servent pada 1:00 pagi EST tanggal 13 Januari 2003 (setelah 15 menit masa pemanasan), dan eksperimen ini berjalan selama satu jam. Tiap servent merekam semua pesan yang dikirim dan diterima, dan tunneling probe merekam semua paket Gnutella ke dalam dan luar GW pada koneksi keluar yang dihijack.

3.2.1 Traffic Breakdowns

Kami pertama kali melaporkan total Gnutella traffic yang berjalan melalui masing-masing servent dan GW serta perinciannya ke dalam jenis pesan yang berbeda. Gambar 3 menampilkan distribusi persentase jenis yang berbeda dari pesan keluar dan masuk pada koneksi keluar yang dihijack pada GW-8. Perincian sama pada servent individu, pada GW-2, dan pada GW-4 itu sangat mirip, sehingga tidak ditampilkan. Gambar 3 menampilkan bahwa antar traffic keluar, query traffic mendominasi query hits traffic. Distribusi ini menyarankan untuk Gnutella servent pasif, penyimpanan utama dari query caching tidak akan berasal dari pesan query hit yang direduksi, tapi dari pesan query request yang direduksi sendiri.

Gambar 3 juga menampilkan bahwa bagian penting dari traffic merupakan string query kosong. Sejak mereka tidak diarahkan ke query hit response apapun, dalam distribusi TTL dan pengukuran lokalitas di bawah, kami menghilangkan string query kosong.

3.2.2 Distribusi TTL

Gambar 4 dan 5 plot distribusi TTL dari query yang berjalan melalui masing-masing dari delapan servent sama halnya masing-masing dari tiga GW. Gambar 4 menampilkan bahwa jumlah query berkurang secara eksperensial dengan menambah TTL. Tindakan “eksponensial” ini bisa dijelaskan dengan skema flooding yang digunakan oleh protokol Gnutella: jika semua servent memiliki jumlah neighbor sama, jumlah servent query akan meningkat dengan menghapus TTL yang berkembang secara eksponensial.

Gambar 4. Distribusi TTL dari query yang berjalan ke dalam servent pada koneksi masuk dan keluarnya, tidak termasuk query kosong.

Gambar 5. Distribusi TTL dari query yang berjalan ke dalam gateway pada koneksi keluar yang dihijack, tidak termasuk query duplikasi dengan muid sama dan query-query kosong.

Sebaliknya, jika setiap servent menginisiasi jumlah query yang sama, jumlah query yang mencapai servent tertentu meningkat secara eksponensial dengan mengurangi TTL.

Catatan bahwa rata-rata antara 60% sampai 70% dari semua query yang mencapai tiap servent memiliki ttl = 1 (ttl = 0 setelah pengurangan), dan query-query ini tidak akan diforward lebih jauh.

Query-query yang mencapai servent dengan ttl > 0 setelah pengurangan akan diforward ke GW, direkam oleh tunneling probe. Tunneling probe kami tidak mengubah TTL, dan secara sederhana memforward query ke luar servent tujuan. Gambar 5 menampilkan distribusi TTL dari query yang berjalan keluar GW, yaitu pada koneksi keluar yang dihijack. Seperti yang diharapkan, distribusi persentase mirip dengan distribusi query dengan ttl > 0 direkam pada servent individu, dinormalisasi  setelah menghapus query-query dengan ttl = 0;

3.2.3 Lokalitas pada Masing-Masing Servent

Sebelum melihat pada lokalitas antar query yang berjalan melalui masing-masing GW, kami pertama melihat pada lokalitas di antara query yang berjalan melalui masing-masing servent, dan kami membagi ukuran lokalitas untuk query dengan ttl = 0 setelah berkurang, dari itu dengan ttl > 0 setelah berkurang, seperti kategori pendahulu tidak akan bermanfaat dari bentuk caching apapun, apakah caching dilakukan pada servent atau pada gateway. Gambar 6 menampilkan persentase query-query unik seperti sebuah fungsi frekuensi mereka disaksikan oleh masing-masing delapan servent, untuk ttl > 0 setelah pengurangan. Kami melihat bahwa jumlah query unik berkurang yang secara eksponensial sebagai sebuah fungsi frekuensinya yang terjadi, menampilkan pola popularitas mirip dengan distribusi Zipf-like.

Gambar 6. Gambar query pada servent individu  yang berjalan ke dalam servent pada koneksi masuk dan keluarnya untuk query dengan ttl > 0 setelah pengurangan, tidak mencakup query kosong; dan lokalitas query pada GW-8 untuk query dengan ttl > 0 yang berjalan ke dalam GW-8 pada koneksi keluar yang dihijack, tidak termasuk query kosong. Duplikasi dengan muid sama diabaikan.

Tabel 1 mendaftar lokalitas (yakni, bobot frekuensi rata-rata reoccurring) dari query dengan ttl > 0 yang berjalan ke dalam masing-masing servent dan tiga GW. Di masing-masing servent, lokalitas diukur dengan menghilangkan query dengan query string unik dan TTL sebagai query yang berbeda.

3.2.4 Lokalitas pada Gateway

Gambar 6 juga menampilkan persentase query unik sebagai fungsi frekuensi yang disaksikan oleh GW-8, router utama yang menghijack semua koneksi keluar sehingga menyaksikan semua query pada koneksi-koneksi itu. Kami melihat bahwa persentase query frekuensi tinggi yang secara signifikan lebih tinggi daripada counterparts-nya pada servents individu, menyarankan bahwa terdapat lokalitas penting antara query yang diforward oleh delapan servent.

Catat bahwa jika servent memiliki beberpa koneksi luar ke servent luar, ia akan memforward query melalui masing-masing koneksi. Lebih jauh, servent yang berbeda dapat memforward query yang sama (yakni, dengan muid yang identik) keluar karena mareka berbagi beberapa hops back pada servent yang sama selama tree propagasi query. Copian berulang seperti ini bagian dari query sama yang berjalan melalui gateway tidak harus dihitung seperti lokalitas, sejak respon berasal dari satu neighbor tidak akan digunakan untuk melayani permintaan ke neighbor lain. Untuk menghindari penghitungan seperti repeated query, tunneling probe kami merekam muid dari masing-masing query yang ia lihat, dan mengabaikan semua query yang muid-nya telah ditemukan sebelumnya.

Ringkasan lokalitas dalam query dengan ttl > 0 yang berjalan ke masing-masing servent pada koneksi masuk dan keluar, dan query yang berjalan ke dalam tiga GW pada koneksi keluar yang dihijack, tidak termasuk query kosong. Duplikasi dengan muid sama diabaikan.

Tabel 1 juga merinci lokalitas query dengan ttl > 0 yang berjalan ke dalam masing-masing tiga GW. Jumlah lokalitas pertama untuk GW dihitung dengan menghilangkan query dengan query string unik, TTL, dan neighbor sebagai query yang berbeda. Dengan demikian, mereka tidak mengandung lokalitas antar query dari servent yang berbeda. Ketika servent tidak berbagi neighbor apapun di luar gateway, seperti kasus dalam pengukuran kami, lokalitas pada GW mirip dengan lokalitas pada masing-masing servent. Jumlah lokalitas kedua untuk GW dihitung dengan menghilangkan query yang termasuk kategori query string unik dan TTL sebagai query yang berbeda. Sehingga jumlah ini mengandung lokalitas antar query dari servent yang berbeda. Tabel 1 menampilkan bahwa lokalitas bertambah dengan populasi servent. Kami mengira lokalitas antar query diforward oleh servent di dalam organisasi besar seperti sebuah universitas akan menjadi lebih tinggi.

4 Query Caching Transparan

Pengukuran lokalitas dalam bagian sebelumnya menyarankan bahwa caching pada gateway organisasi bisa jauh lebih efektif daripada caching pada servent individu di samping gateway karena ia dapat mengeksploitasi lokalitas teragregasi di antara semua query yang diforward dan diinisiasi oleh semua servent di dalam organisasi. Pada bagian ini, kami mempresentasikan skema query caching pada gateway organisasi. Untuk menyederhanakan pembahasan ini, kami mengabaikan caching HTTP download untuk sekarang, dan delay pembahasan mengintegrasikan query caching transparan dengan HTTP caching transparan pada gateway hingga bagian 5.

4.1 Gambaran Umum

Skema caching tranparan kami mirip dengan setup pengukuran lokalitas yang dibahas pada Bagian 3.1. Perbedaan hanya dalam caching setup; tunneling probe diganti dengan caching proxy yang mencache query respon (lihat     Gambar 1).

Semua pesan PING/PONG yang diinisiasi atau diforward oleh servent di dalam atau luar yang berjalan melalui gateway akan diforward oleh proxy servent. Caching proxy tidak akan mengubah TTL, sehingga daya tangkap pesan PING/PONG sama seperti sebelumnya. Sama halnya, pesan HTTP data download akan dilakukan tunnel.

Untuk query request yang berjalan keluar gateway, caching proxy mengecek query hits cache lokal. Jika ia melayani query response keluar cache-nya, ia tidak akan memforward query request keluar gateway. Jika ia tidak melayani query response keluar cache-nya, ia akan memforward query ke tujuan asli query, tanpa mengurangi TTL. Juga, daya tangkap query ini sama ketika proxy tidak ada.

4.2 Algoritma Caching

Seperti dibahas pada Bagian 3.2.4, proxy servent diattach ke gateway dapat berpotensi melihat repeated copies dari query yang sama, yakni, dengan muid identik. Gagasan rumit tentang cache misses dan cache hits ini berada pada skema caching transparan. Selanjutnya, kami membahas pilihan desain untuk algoritma caching dan mempresentasikan detil algoritma terpilih.

4.2.1 Pilihan Desain

Tiap Gnutella query request yang digali oleh caching proxy memiliki sekumpulan muid unik, query string, forwarder (di dalam gateway), neighbor (di luar gateway), TTL, dan nilai kecepatan minimum. Ini karena repeated queries dengan muid yang sama telah dihapus pada servent individu. Selanjutnya, kami membahas pilihan desain dengan istilah subset parameter ini agar digunakan untuk pengindeksan query hits. Sebenarnya, subset yang lebih kecil, lebih sering menggunakan kembali cached query hits, yakni, cache hit ratio yang lebih tinggi.

Di luar enam parameter itu, query string dan TTL merupakan caching parameters yang sangat penting. Parameter muid tidak harus sebuah parameter, karena sebaliknya, query dengan string sama dan parameter lainnya tapi muid yang berbeda tidak akan menghasilkan hit. Maka algoritma strictest caching adalah untuk mengindeks query hits dengan tuple (query string, forwarder, neighbor, ttl, minimum speed).

Gambar 7. Topologi contoh dari servent di dalam gateway

Algoritma caching kami lebih jauh menghilangkan dua parameter dari tuple lima di atas. Pertama, algoritma caching mengabaikan nilai forwarder, sejak query hits dari subtree (contohnya, berakar pada node A1 pada Gambar 7) berhubungan dengan query yang dikirimkan oleh  satu forwarder (contohnya servent A) dapat digunakan untuk membalas query berikutnya dengan query string sama tapi dari forwarder berbeda (servent C).

Kedua, algoritma caching menghapus kecepatan minimum cache yang mengindeks tuple seperti berikut ini. Ketika cache tidak terjadi, proxy menuliskan kembali kecepatan minimum sampai nol sebelum melanjutkannya ke luar gateway. Sebagai hasilnya, algoritma caching mengumpulkan query hit dengan semua kecepatan yang memungkinkan. Untuk query berikutnya yang mencocokkan semua parameter lainnya dengan cached query hit, tapi menentukan kebutuhan kecepatan minimum bukan nol, proxy selalu bisa mengekstrak subset dari cached query hit yang memenuhi kebutuhan kecepatan minimum tanpa memforward query keluar gateway lagi. Kami menyebut skema ini one-time bandwidth adjustment. Alternatifnya, proxy secara inkremental bisa memforward query dengan kebutuhan kecepatan minimum yang semakin rendah sehingga tidak dipenuhi dengan cached query hit sebelumnya. Pada kasus ini, proxy mereplace cached query hit dengan query hit yang baru saja diterima setiap waktu ia memforward query dengan kebutuhan kecepatan minimum yang lebih rendah. Kami menyebut skema ini incremental bandwidth adjustment. Sebenarnya, terdapat tradeoff di antara dua skema itu. Skema one-time bandwidth adjustment menghabiskan one-time cost untuk mendapatkan semua query hit yang memungkinkan, yang mungkin lebih tinggi daripada yang dibutuhkan, tapi dapat digunakan untuk membalas recurrence dari query sama yang selanjutnya. Skema incremental bandwidth adjustment memperoleh query hit on demand, tapi skema itu muncul dari repeated query hit ketika memforward query-query yang sama dengan kebutuhan kecepatan minimum yang semakin rendah. Secara eksperimen kami membandingkan dua skema ini pada Bagian 4.3.

Algoritma caching yang lebih agresif cenderung mengabaikan neighbor parameter dan caches query hit yang diindeks dengan (query string, ttl) saja. Skema caching ini dapat mengeksploitasi lokalitas dalam query kolektif dengan servent berbeda (lihat Tabel 1), sejak skema ini dapat menggunakan query hit dalam cache-nya yang dikumpulkan dari balasan node-node dalam subtree yang berakar pada satu neighbor di luar gateway (contohnya, servent A3 pada Gambar 7) untuk membalas query yang ditunjukkan untuk subtree yang berbeda di luar gateway (contohnya, berakar pada servent B3). Tetap tidak jelas ke tingkat apa skema ini memelihara user yang mencari pengalaman sebagai subtree berbeda yang mungkin menghasilkan himpunan query hits yang berbeda untuk query sama dengan TTL sama. Kami sedang mengkaji skema caching ini pada karya yang sedang kami lakukan ke depan.

Tabel 2. Tindakan algoritma caching untuk kasus-kasus yang berbeda

4.2.2 Algoritma yang Terpilih

Algoritma caching kami menyembunyikan query hits menurut tuple nilai (query string, neighbor, ttl) dari query. Algoritma ini menggunakan dua struktur data utama. Pertama, kapanpun proxy itu menggali query ke luar servent, proxy ini merekam muid, query string dan informasi TTL pada Cache Miss Table (CMT). Ketika query hit diterima dari luar, muid-nya dicek terhadap CMT untuk menemukan query string dan TTL yang sesuai, yang digunakan untuk mengindeks       ke dalam cache table. Cache table (CT) merupakan struktur data untuk menyimpan cached query hits. Untuk tiap CT entry CT (i), algoritma menambah field vector untuk mengingat muid dan forwarder menuju 10 query terbaru untuk query hit mana yang dibalas menggunakan cache entry itu.

Diasumsikan bahwa query hits untuk query tertentu sudah disembunyikan dalam ith entri cache, diindeks dengan (query string, neighbor, ttl). Kemudian, hasil pesan query hasil MSG-1 dalam cahce hit pada entri ini untuk pertama kali, balasan proxy dari cache dan menyimpan informasi (muid, forwarder) dari MSG dalam CT (i). Setiap saat ada cache hit dengan ith entry, (muid, forwarder) informasi pesan baru MSG-N dibandingkan dengan yang disimpan dalam CT (i) dan tindakan tepat menurut Tabel 2.

  • Kasus 1: (muid, forwarder) dari MSG-N mencocokkan salah satu dari pesan sebelumnya yang dibalas oleh proxy yang menggunakan cache entry sama. Ini tidak akan terjadi seperti forwarding servent harus sudah menghapusnya.
  • Kasus 2: muid dari MSG-N mencocokkan salah satu pesan sebelumnya yang dibahas oleh proxy menggunakan cache entry yang sama, tapi nilai forwarder-nya berbeda. Ini hanya terjadi ketika sebuah query diforward melalui forwarder yang berbeda terhadap neighbor yang sama. Pada kasus ini, proxy harus sudah membalas sekali ke sebuah query dengan (muid, forwarder) sama yang menggunakan cached query hits dari Gnutella subtree yang berakar pada cache entry’s neighbor, sehingga proxy itu harus menghapus MSG-N secara sederhana.
  • Kasus 3: muid dari MSG-2 tidak sesuai dengan muid dari semua query sebelumnya yang dibalas oleh proxy menggunakan cached query hits. Pada kasus ini, proxy sedang memperhatikan pesan query ini dengan muid ini untuk pertama kali. Karena itu, proxy membalas dari cache. Proxy juga menyimpan nilai-nilai (muid, forwarder) dari MSG-2 dalam cache entry yang sesuai.

Optimisisasi. Organisasi sederhana untuk algoritma caching kami adalah untuk mengecek CMT terhadap eksistensi entry dengan (muid, neighbor) yang sama dan menghapus query baru jika entry itu ditemukan. Alasannya adalah bahwa neighbor servent akan menghapus query apapun menurut Gnutella protocol. Optimisasi tambahan untuk proxy adalah untuk menghapus query-query kosong sejak query itu tidak menghasilkan query hits apapun. Ini mereduksi uplink traffic.

Caching delay. Komplikasi terhadap skema caching kami muncul ketika repeated query (yakni, dengan indeks cache yang sama) tiba pada proxy sebelum semua query hits dari luar gateaway untuk forwarded query pertama sudah diterima. Kami menyelesaikan masalah ini sebagai berikut. Sekali ada cache miss dan query itu diforward dengan proxy, proxy ini menciptakan entry yang tepat, merekam waktu, dan mendeklarasikannya sehingga tidak dapat digunakan hingga periode waktu tertentu yang telah berlalu, pada poin mana, cache entry ditandai sebagai usable. Pengukuran kami pada caching proxy telah menampilkan di atas 99% query yang diforward keluar gateway yang menerima semua query hits-nya dalam 15 detik. Jadi, kami menset periode yang sudah dilalui hingga 15 detik. Hit pada unusable cache entry dihilangkan karena kesemaannya seperti cache miss.

4.3 Hasil Caching

Kami sudah menjalankan dua set eksperimen selama satu jam secara teratur, satu dengan one-time bandwidth adjustment dan yang lainnya dengan incremental bandwidth adjustment. Hasil caching ditampilkan pada Tabel 3.

Tabel 3 menampilkan bahwa query kosong terhitung sekitar 40% pesan query dan sekitar 36-39% traffic pesan query. Satu pertanyaan tentang hasil caching apakah menghitung query-query yang terhapus berkaitan dengan optimisasi pada Bagian 4.2.2 dalam menghitung hit ratio. Sejak query yang terhapus berkontribusi untuk mereduksi uplink traffic, kami memandangnya sebagai cache hits.

Tabel 3. Hasil caching untuk skema one-time bandwidth adjustment dan skema incremental bandwidth adjustment

Untuk query-query yang tidak kosong, dua versi hasil algoritma caching dalam 38,15% dan 31,53% query message hit ratio (dengan query-query yang terhapus dianggap sebagai hits), 39.56% dan 33.07% byte hit ratio untuk pesan query (yakni, reduksi dalam uplink traffic), dan 12.41% dan 6.74% byte hit ratio untuk pesan-pesan query hit (yakni, reduksi dalam download traffic), secara respektif. Membandingkan dua algoritma caching, kami melihat bahwa cache hit ratio dalam menggunakan skema incremental bandwidth adjustment adalah sekitar 20% lebih kecil daripada menggunakan skema one-time bandwidth adjustment. Sejak sejumlah cache miss berkaitan dengan mismatch dalam kebutuhan kecepatan dengan menggunakan skema incremental bandwidth adjustment itu cukup tidak signifikan (766 keluar dari 1472218 miss), dan jumlah query dari kebutuhan kecepatan bukan nol dalam run yang menggunakan skema one-time bandwidth adjustment juga tidak signifikan (14669 keluar dari 1476160), kami menghubungkan perbedaan dalam hit ratio ke perbedaan dalam lokalitas dalam dua run; run menggunakan skema one-time bandwidth adjustment memiliki lokalitas lebih tinggi daripada run yang menggunakan skema incremental bandwidth adjustment. Dengan kata lain, dua algoritma caching kemungkinan besar berfungsi seperti query traffic sama yang ada.

Tabel 3 juga menampilkan bahwa hanya ada satu gap kecil di antara hit ratio terukur yang masuk ke dalam account caching delay yang dijelaskan pada Bagian 4.2.2 dan hit ratio teoritis yang dihitung berdasarkan lokalitas query yang mengasumsikan tidak ada caching delay. Ini memberi kesan bahwa repeated queries jarang terjadi ke query yang lainnya, dan caching delay memiliki dampak kecil pada efektivitas caching.

Secara keseluruhan, dua algoritma caching menghasilkan query message cache hit  ratio  62.50% dan 60.91% , query message byte hit ratio 61.53% dan 59.73%, dan query hit message byte hit ratio 12.41% dan 6.74%, secara respektif.

5 Mengintegrasikan Query Caching dengan HTTP Caching

Pada bagian ini, kami mempresentasikan skema untuk mengintegrasikan query caching proxy kami dengan off-the-shelf HTTP caching proxies yang banyak tersebar di Internet.

Faktanya bahwa Gnutella servent sering menggunakan TCP port yang sama untuk protokol dan data traffic yang memproses tantangan terhadap cache kedua jenis traffic secara transparan. Di satu sisi, kami tidak dapat secara sederhana mengkonfigurasi regular web cache untuk mendengarkan default Gnutella port (yakni, 6346), sebagaiman ia tidak dapat memahami pesan Gnutella protokol. Di sisi lain, off-the-shelf HTTP caching proxy berkinerja tinggi tersebar luas, sehingga ia tidak bisa dianggap mengimplementasikan kembali query caching dan HTTP caching di posisi atas yang lainnya.

Gambar 8. Mengintegrasikan query caching transparan dengan HTTP data caching

Gambar 8 mengilustrasikan skema kami untuk mengintegrasikan caching transparan dari Gnutella protocol dan data traffic pada gateway organisasi. Router yang menjalankan WCCPv2 dikonfigurasi untuk mengalihkan arah TCP traffic yang ditujukkan ke semua port khusus untuk attached caching proxy machines. Dua caching proxy diattach ke router: pertama adalah query caching proxy kami, mendengarkan port 6346 saja; kedua adalah off-the-shelf web caching proxy, mendengarkan port 9346, mengasumsikan 9346 adalah sebuah port yang tidak digunakan.[2] Konfigurasi default dari web caching proxy diubah sedikit demi sedikit: pada cache miss, selain membuat koneksi ke port 80 server asal, ia akan membuat koneksi ke port 6346 server asal. Catat bahwa dua proxy bisa berjalan pada mesin itu, selama router dikonfigurasi dengan benar. Langkah utama (dilabeli 1-6 Gambar 8) bahwa Gnutella traffic sedang dialihkan arahnya ke caching proxy dan dicache seperti berikut:

  • Router mengalihkan arah semua protocol traffic yang sedang menuju port 6346 ke proxy cache (Langkah 1), dan semua HTTP traffic menuju 9346 ke web caching proxy (Langkah 5). Router akan menjadi bersih di bawah semua Gnutella HTTP request dari dalam gateway tidak akan menuju port 6346.
  • Host menjalankan proxy cache menggunakan IP firewall untuk mengalihkan arah paket protokol yang diforward dari router ke port 6346localhost.
  • Proxy cache yang sedang melakukan listen port 6346 menerima pesan-pesan protokol, dan memprosesnya dengan tepat, sebagaimana dideskripsikan pada Bagian 4.2.2. Query miss akan diforward ke servent tujuan, dengan tujuan port 6346 (Langkah 2). Untuk tiap query hit yang sedang kembali dari servent luar (Langkah 3), jika ditentukan port 6346, query caching proxy akan memodifikasi port tersebut menjadi 9346 sebelum mengirimkan kembali ke servent di dalam gateway (Langkah 4). Perhatikan jika port yang sudah ditentukan bukan 6346, ia tidak akan dituliskan kembali.
  • Ketika servent di dalam organisasi mendownload file-file via HTTP, ia akan menentukan port       9346 (Langkah 5), sebagaimana yang diperintahkan oleh query hits yang ia sudah terima. Ini menjamin bahwa semua Gnutella HTTP request yang sedang menuju keluar gateway akan menggunakan port 9346.
  • Router mengalihkan arah HTTP request menuju port 9346 sampai web caching proxy.
  • Web caching proxy node menggunakan IP firewall untuk mengalihkan arah paket-paket HTTP ke port 9346 localhost.
  • Web caching proxy menerima HTTP request, dan berjalan seperti biasa. Pada sebuah hit, ia membalas servent keluar cache-nya (Langkah 6). Pada sebuah miss, ia selalu membuat koneksi ke server asal pada port 6346 (Langkah 7). Server asal dijamin sedang melakukan listen pada port 6346. Ini hanya karena ketika port itu ditetapkan dalam query hit 6346, query caching proxy akan menuliskannya kembali menjadi 9346, seperti dijelaskan di atas. Jika port yang sudah ditentukan bukan 6346, ia tidak akan dioverwrite, dan HTTP request tidak akan dialihkan arahnya oleh router. Dengan kata lain, mereka tidak akan dicache.

6 Karya Terkait

Walaupun caching peer-to-peer traffic merupakan topik yang relatif baru, sudah banyak kajian karakteristik Gnutella network dan traffic. Adar dan Huberman sudah mengkaji Gnutella traffic selama waktu 24 jam [3], dan ditemukan bahwa tepat 70% user tidak berbagi file, dan bahwa 50% dari semua respon telah dikembalikan hanya dengan 1% dari host. Dalam [7], Saroiu, dkk. juga sudah mengobservasi bahwa persentase kecil dari peer yang sudah muncul memiliki karakteristik “server-like”: peer ini sudah dihubungkan dengan baik dalam overlay network dan peer ini sudah melayani sejumlah banyak file. Dalam [6], Ripeanu, dkk. sudah mengkaji topologi  Gnutella network di atas waktu enam bulan, dan dilaporkan dua penemuan yang menarik: (1) Gnutella network menshare keunggulan dan kekurangan power-law structure, dan (2) Topologi Gnutella network benar-benar tidak sesuai dengan underlying Internet topology yang mengarah ke penggunaan network bandwidth yang tidak efisien.

Beberapa karya sebelumnya sudah mengkaji query caching dalam Gnutella network. Sripanidkulchai [9] sudah mengobservasi bahwa popularitas query string mengikuti distribusi Zip-like, dan sudah mengemukakan serta mengevaluasi skema query caching sederhana dengan memodifikasi Gnutella servent. Skema caching yang sudah dikemukakan adalah cukup sederhana; ia mencache query hit semata-mata berdasarkan pada query string-nya dan mengabaikan nilai-nilai TTL. Dalam [5], Markatos sudah mengkaji satu jam Gnutella traffic trace yang dikumpulkan pada tiga servent yang diletakkan di Greece, Norway, dan USA, secara respektif, dan ditemukan bahwa pada rata-rata tiap query dengan ttl > 1 disaksikan dengan masing-masing servent antara 2.57 sampai 2.98 kali (mengabaikan TTL), mengusulkan lokalitas penting antara query yang diforward oleh masing-masing servent. Markatos juga mengemukakan skema query caching dengan memodifikasi servent yang cache query hits-nya sesuai dengan query string, forwarder di mana query berasal, dan TTL. Kesimpulannya, semua skema caching sebelumnya untuk Gnutella network fokus pada servent individu, dan diimplementasikan dengan memodifikasi servent sehingga bergantung pada adopsi besar servent yang sudah dimodifikasi agar menjadi efektif. Perbedaannya, skema kami memandang semua servent di dalam organisasi sebagai kesatuan, mengeksploitasi lokalitas di antara query kolektif, tidak membutuhkan perubahan ke servent individu, sehingga dapat tersebar dengan mudah.

Beberapa karya saat ini sudah mengkaji p2p traffic lainnya. Leibpwitz, dkk. [4] sudah mengkaji satu bulan FastTrack-based [10] p2p traffic pada Israeli ISP utama dan ditemukan bahwa kebanyakan p2p files adalah file-file audio dan kebanyakan traffic berhubungan dengan video dan file-file aplikasi. Mereka juga melaporkan lokalitas penting dalam file-file data p2p yang sudah dikaji. Saroiu, dkk [8] sudah mengkaji laporan Internet traffic yang sedang terjadi melalui gateway organisasi besar ke dalam web, CDN, dan p2p (Gnutella dan KaZaa) traffic. Mereka fokus pada HTTP traffic, untuk teknik-teknik caching mana yang sangat terkenal. Perbedaannya, paper ini fokus pada p2p protocol traffic, dan mengemukakan skema caching transparan untuk query traffic sebagai skema untuk mengintegrasikan query caching transparan dengan HTTP caching transparan.

7 Kesimpulan

Kami sudah mengkaji lokalitas dalam query kolektif yang berjalan melalui gateway yang diforward oleh servent di samping gateway itu, dan ditemukan bahwa ada lokalitas signifikan dalam query kolektif, dan lokalitas bertambah dengan populasi servent-servent itu. Untuk mengeksploitasi lokalitas ini, kami sudah mengemukakan skema untuk caching query hit transparan pada gateway. Skema kami tidak membutuhkan modifikasi apapun untuk servent individu, dan dapat mengeksploitasi lokalitas dalam query kolektif yang berjalan menuju gateway. Kami sudah mengimplementasikan algoritma caching konservatif yang memelihara pengalaman user dengan membedakan query hit dari Gnutella subtrees yang berbeda di luar gateway; query akan berhasil dalam query hits serupa dengan atau tanpa menjalankan caching transparan. Jika servent di dalam gateway tidak menshare neighbor apapun di luar gateway, algoritma caching konservatif kami tidak memanfaatkan lokalitas dalam query kolektif, dan ia akan menghasilkan cache hit ratio serupa seperti cache pada servent individu (contohnya, di dalam gateway).

Pengukuruan caching proxy transparan kami dalam experimental testbed dari 8 Gnutella servents dalam sebuah LAN sudah menampilkan query cache hit ratio sampai 63%, dan reduksi uplink query traffic mencapai 62%, dan reduksi downlink query hit traffic mencapai 12% pada gateway.

Kami sedang mengejar beberapa tujuan dalam karya yang sedang kami lakukan. Pertama, kami sedang mengkaji efektivitas dan akurasi algoritma caching yang lebih agresif yang dibahas pada Bagian 4.2.1      yang mana tidak membedakan subtree di luar gateway dari mana query hit berasal. Kedua, tunneling probe dan caching proxy kami hanya menghijack keluar koneksi servent di dalam gateway. Secara prinsipil, koneksi masuk bisa dihijack dengan proxy servent pada gateway dalam mode yang serupa. Kami berencana untuk mengkaji reverse caching dari query-query pada gateway itu. Ketiga, untuk mengukur efektivitas skema cahing kami dalam dunia nyata yang menginginkan sejumlah besar servent aktif, kami berencana untuk menyebarkan tunneling probe kami dan caching proxy kami di Purdue Research and Development Network (RDN). RDN merupakan sebuah jaringan bayangan dari jaringan kampus yang dikembangkan untuk mengizinkan para peneliti, fakultas, dan mahasiswa mengakses konektivitas Gigabyte Network melalui kampus untuk penelitian, pengujian, dan pengembangan. Ia dapat dikonfigurasi untuk menyelesaikan jumlah yang dapat disesuaikan terkait network traffic dari jaringan kampus utama. Keempat, kami juga berencana untuk mengkaji p2p network traffic lainnya seperti KaZaa, dan memperluas skema caching yang sudah dikembangkan untuk Gnutella menuju jaringan p2p dan aplikasi-aplikasi lainnya.

Ucapan Terima Kasih

Kami mengucapkan terima kasih kepada para pemberi resensi yang tidak diketahui namanya yang telah memberikan komentar-komentar yang sangat bermanfaat. Tulisan ini didukung oleh Cisco Systems melalui University Research Program.

Referensi


[1] Pesan PONG dihasilkan oleh servent, baik pada kepentingannya sendiri atau kepentingan yang lain yang menggunakan PONG cache-nya seperti yang didukung dalam Gnutella versi 0.6.

[2] Kami mengasumsikan bahwa web caching proxy tambahan mendengarkan port 80 yang diattach ke router untuk menyembunyikan web traffic yang normal.

2 responses to “Transparent Query Caching in Peer-to-Peer Overlay Networks

  1. mas, mau nanya aku lagi skripsi S-1/penelitian tentang IPTV memakai overlay network. bisa dijelaskan tidak perbedaan antara overlay network dengan jaringan yang ada sekarang?

    terima kasih.😀

    • Maaf mas, saya juga baru baca-baca nih. Tapi secara sederhana Overlay network itu kedudukan node-nya sama sebagai client-server. Kalau ingin lebih jelas, dapat dibandingkan dengan Peer to Peer. Kalau ada info baru, insyaAllah saya share lagi. Semoga sukses skripsinya ya

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s