Bagaimana Cara Menggunakan Tabel Routing Pastry?

Saya mencoba menerapkan Tabel Hash Terdistribusi Kue, tetapi beberapa hal lolos dari pemahaman saya. Saya berharap seseorang dapat mengklarifikasi.

Penafian : Saya bukan mahasiswa ilmu komputer. Saya telah mengikuti dua kursus sains komputer dalam hidup saya, dan tidak ada yang berurusan dengan sesuatu yang jauh kompleks. Saya telah bekerja dengan perangkat lunak selama bertahun-tahun, jadi saya merasa saya siap dengan tugas implementasi, jika saya bisa membungkus pikiran saya dengan ide-ide. Jadi saya mungkin kehilangan sesuatu yang jelas.

Saya telah membaca makalah yang penulis terbitkan [1], dan saya telah membuat beberapa kemajuan yang baik, tetapi saya terus terpaku pada satu titik khusus ini dalam cara tabel routing bekerja:

Koran itu mengklaim itu

Tabel routing node, $R$ , disusun dalam $\lceil \log_{2^b} N\rceil$ baris dengan masing-masing entri $2^b - 1$ . The $2^b - 1$ entri pada baris $n$ dari tabel routing yang masing-masing mengacu pada simpul yang sahamnya nodeId node hadir ini nodeId di fi rst n digit, tapi yang $n + 1$ digit th memiliki salah satu dari $2^b - 1$ kemungkinan nilai selain yang $n + 1$ digit th di id node hadir ini.

The singkatan variabel aplikasi-spesifik, biasanya 4 . Mari kita gunakan b = 4 , demi kesederhanaan. Jadi yang di atas$b$$4$$b=4$

Tabel routing node, , diatur ke dalam ⌈ log 16 N ⌉ baris dengan 15 entri masing-masing. Ke 15 entri pada baris n dari tabel routing masing-masing merujuk ke sebuah node yang nodeId berbagi nodeId node saat ini dalam digit n pertama, tetapi yang n + 1 digit memiliki salah satu dari 2 b - 1 nilai yang mungkin selain n + Digit ke- 1 dalam id node saat ini.$R$$\lceil \log_{16} N\rceil$$15$$15$$n$$n + 1$$2^b - 1$$n + 1$

Saya sangat mengerti. Selanjutnya, adalah jumlah server dalam gugus. Saya mengerti juga.$N$

Pertanyaan saya adalah, jika baris suatu entri ditempatkan bergantung pada panjang kunci yang dibagikan, mengapa batas acak pada jumlah baris? Setiap nodeId memiliki 32 digit, ketika (128 bit nodeId dibagi menjadi digit b bit). Jadi apa yang terjadi ketika N menjadi cukup tinggi sehingga ⌈ log 16 N ⌉ > 32 ? Saya menyadari bahwa akan dibutuhkan 340.282.366.920.938.463.463.374.607.431.768.211.457 (jika matematika saya benar) server untuk mencapai skenario ini, tetapi sepertinya inklusi aneh, dan korelasinya tidak pernah dijelaskan.$b=4$$N$$\lceil\log_{16} N\rceil > 32$

Selanjutnya, apa yang terjadi jika Anda memiliki sejumlah kecil server? Jika saya memiliki kurang dari 16 server, saya hanya memiliki satu baris di tabel. Selanjutnya, dalam keadaan apa pun setiap entri di baris tidak memiliki server yang sesuai. Haruskah entri dibiarkan kosong? Saya menyadari bahwa saya dapat menemukan server di leaf set tidak peduli apa pun, mengingat beberapa server, tetapi kesulitan yang sama muncul untuk baris kedua - bagaimana jika saya tidak memiliki server yang memiliki nodeId sedemikian rupa sehingga saya dapat mengisi setiap permutasi yang mungkin dari digit ke-n? Akhirnya, jika saya memiliki, katakanlah, empat server, dan saya memiliki dua node yang berbagi, katakanlah, 20 dari 32 digit mereka, dengan beberapa kebetulan acak ... haruskah saya mengisi 20 baris tabel untuk node itu, meskipun itu adalah jauh lebih banyak baris daripada yang bisa saya isi?

Inilah yang saya hasilkan, mencoba menjelaskan jalan saya melalui ini:

1. Entri harus disetel ke nilai nol jika tidak ada simpul yang cocok dengan awalan itu secara tepat.
2. Baris kosong harus ditambahkan sampai cukup baris ada untuk mencocokkan panjang bersama dari nodeIds.
3. Jika, dan hanya jika, tidak ada entri yang cocok dengan ID pesan yang diinginkan, kembalilah pada pencarian tabel routing untuk nodeId yang panjangnya dibagi lebih dari atau sama dengan nodeId saat ini dan yang entri secara matematis lebih dekat daripada saat ini nodeId ke ID yang diinginkan.
4. Jika tidak ada simpul yang cocok dapat ditemukan di # 3, anggap ini adalah tujuan dan mengirimkan pesan.

Apakah keempat asumsi ini berlaku? Apakah ada tempat lain saya harus mencari informasi tentang ini?

1. Pastry: Lokasi objek dan rute yang dapat diskalakan dan didesentralisasi untuk sistem peer-to-peer skala besar oleh A. Rowstrong dan P. Druschel (2001) - unduh di sini

Ide tabel routing dalam Pastry (dan semua jaringan P2P terstruktur) adalah untuk meminimalkan ukurannya, sambil menjamin routing yang lebih cepat.

Algoritma perutean Pastry berjalan sebagai berikut:

Langkah A. Sebuah simpul u mencari objek A dengan terlebih dahulu mencarinya di set daunnya. Langkah B. Jika tidak tersedia, maka kueri diteruskan ke simpul yang dikenal yang berbagi "sejumlah awalan dengan yang setidaknya lebih besar dari simpul yang Anda bagikan dengan A". Langkah C. Jika catatan tersebut tidak ditemukan, maka query diteruskan ke node di set daun yang numerik paling dekat dengan A .$A$$A$

Inilah sebabnya mengapa simpul menyimpan alamat node mengatur tabelnya sebagai berikut:$u$

1.Setiap catatan pada baris dari tabel routing simpul u adalah pengidentifikasi simpul yang berbagi bit awalan i dengan pengidentifikasi u .$i$$u$$i$$u$

2. sedikit catatan berturut-turut saya adalah unik dan diambil dari set { 0 , ... , 2 b - 1 } .$(i + 1)^{th}$$i$$\{0, …, 2^{b} – 1\}$

Contoh dalam skenario tipikal: jika alamat u adalah 1111 dan objek memiliki pengidentifikasi 4324: maka inilah yang akan terjadi: (kita asumsikan bahwa itu adalah basis 4. (yaitu alamat dari [1-4] [1- 4] [1-4] [1-4]).$A$

Node saham 0 awalan dengan objek A . Oleh karena itu, terlihat di baris 0. Menurut aturan 2 di atas, simpul u menyimpan alamat node 1XXX, 2XXX, 3XXX, 4XXX, di mana X adalah nilai "jangan peduli". Yang paling dekat di antara simpul-simpul ini ke A adalah 4XXX. - Mari mengatakan 4xxx ini sebenarnya 4013. Kemudian u ke depan untuk u 1 dengan alamat 4013. Sekarang Anda akan mengulangi hal yang sama lagi di simpul u 1 dengan alamat 4013.$u$$A$$u$$A$$u$$u _1$$u _1$

$u _1$$A$

$log_{2^b}$$b$$2^b$$b$

Skenario praktis biasanya tidak tipikal seperti itu. Mungkin ada situasi di mana tidak banyak node dalam jaringan. ini sebabnya kami mengikuti langkah C di atas. - Namun, apa yang Anda harus jamin untuk membuat algoritma ini benar adalah bahwa setiap node terhubung ke dua node terdekat dengan itu (dalam hal pengidentifikasi). Ini akan membentuk cincin simpul yang dipesan [misalnya 1-> 3-> 4-> 9-> 10-> 11-> 1]