Mengukur latensi jaringan satu arah

Ini adalah teka-teki tentang mengukur latensi jaringan yang saya buat. Saya percaya solusinya adalah tidak mungkin, tetapi teman tidak setuju. Saya mencari penjelasan yang meyakinkan. (Meskipun itu dianggap sebagai teka-teki, saya pikir cocok di situs web ini karena penerapannya pada desain dan pengalaman protokol komunikasi seperti di game online, belum lagi NTP.)

Misalkan dua robot berada di dua kamar, dihubungkan oleh jaringan dengan latensi satu arah yang berbeda seperti yang ditunjukkan pada grafik di bawah ini. Ketika robot A mengirim pesan ke robot B, dibutuhkan 3 detik untuk sampai, tetapi ketika robot B mengirimkan pesan ke robot A, dibutuhkan 1 detik untuk sampai. Latensi tidak pernah bervariasi.

Robot identik dan tidak memiliki jam bersama, meskipun mereka dapat mengukur berlalunya waktu (misalnya mereka memiliki jam tangan berhenti). Mereka tidak tahu yang mana dari mereka adalah robot A (yang pesannya ditunda 3s) dan yang mana robot B (yang pesannya ditunda 1s).

Protokol untuk mengetahui waktu pulang pergi adalah:

whenReceive(TICK).then(send TOCK)

// Wait for other other robot to wake up
send READY
await READY
send READY

// Measure RTT
t0 = startStopWatch()
send TICK
await TOCK
t1 = stopStopWatch()
rtt = t1 - t0  //ends up equalling 4 seconds

Apakah ada protokol untuk menentukan keterlambatan perjalanan satu arah? Bisakah robot menemukan yang memiliki penundaan pengiriman pesan lebih lama?

Diagram berikut, dari posting blog yang saya tulis , adalah bukti visual bahwa itu tidak mungkin:

Perhatikan bagaimana waktu kedatangan paket di setiap sisi tetap sama, bahkan ketika latensi satu arah berubah (dan bahkan menjadi negatif!). Paket pertama selalu mencapai server pada 1,5 detik pada jam server, yang kedua selalu mencapai klien pada 2 detik pada jam klien, dll. Isi paket dan waktu kedatangan lokal adalah satu - satunya hal yang bisa didasarkan pada protokol, tetapi konten dan waktu kedatangan dapat dipertahankan konstan karena asimetri bervariasi dengan memvariasikan kemiringan jam awal.

Pada dasarnya, asimetri dalam latensi satu arah terlihat persis seperti kemiringan jam. Karena masalahnya menyatakan bahwa kita tidak mulai mengetahui kemiringan jam awal atau asimetri latensi satu arah, dan yang satu bervariasi seperti memvariasikan yang lain sehingga efeknya tidak dapat dibedakan, kita tidak dapat memisahkan kontribusi mereka untuk menyelesaikannya. asimetri latensi satu arah. Tidak mungkin.

Secara lebih formal, Anda tidak bisa menyelesaikan panjang sisi bila hanya diberikan panjang siklus. Basis siklus memiliki derajat kebebasan, sesuai dengan skew clock tidak diketahui relatif terhadap salah satu peserta. Anda selalu dapat menyembunyikan latensi satu arah, bahkan ketika ada banyak peserta:n - $n-1$$n-1$

Jika Anda tidak memiliki kecenderungan visual, saya memiliki argumen intuitif lain. Bayangkan sebuah portal waktu hingga seratus tahun di masa depan. Ketika Anda mengobrol di seberang seseorang di sisi lain, Anda menyadari bahwa percakapan itu benar-benar normal meskipun ada seratus tahun asimetri dalam penundaan satu arah. Setiap efek yang dapat diamati akan jelas pada skala itu!

Saya pikir tidak mungkin untuk mengetahui latensi satu arah hanya dengan membandingkan stopwatch.

$A$$B$$C_{A1}$
$B$$C_{B1}=1$
$A$$C_{A2}=9$
$B$$C_{B2}=5$
$A$$B$

Mungkin jika Anda membuatnya menjadi pertanyaan karunia seseorang akan memecahkannya. Sampai saat itu, pujian.

Saya telah menemukan cara untuk KEDUA menemukan simpul mana yang (yaitu yang memiliki penundaan pesan lebih lama) DAN memperkirakan penundaan perjalanan satu arah. Sementara jawaban lain benar, mereka HANYA mempertimbangkan pengukuran jam langsung yang didekati yang tentu saja tidak dapat bekerja. Namun karena saya membuktikan di sini ini hanya bagian dari cerita karena di sini adalah algoritma kerja saya untuk yang di atas:

Asumsikan seperti dalam kehidupan nyata:

• Tautan bandwidth terbatas b

• Setiap node memiliki alamat unik (mis. A dan B)

• Ukuran paket p jauh lebih kecil dari produk latensi bandwidth *

• Node A dan B dapat mengisi saluran

• Node memiliki random () function

Setiap node mengisi saluran dengan paket-paketnya sendiri (masing-masing ditandai A atau B) ATAU meneruskan paket-paket yang diterimanya dari node lain sebagai berikut:

Always fill the channel with my own packets except:
if I receive a packet from another node then
   Randomly choose to 
          either forward that packet from the other node
          or discard that packet and forward my own packet

Penjelasan Intuitif Karena bandwidth A * produk latensi lebih tinggi (karena latensi lebih tinggi) A akan mengelola untuk menerima lebih banyak paket dari B, oleh karena itu setiap Node dapat mengetahui siapa mereka dalam diagram .

Lebih lanjut, dengan waktu konvergensi yang cukup untuk menjalankan algoritma di atas, rasio paket A ke B akan menunjukkan rasio aktual penundaan RTT dari A ke B dan karenanya OTT yang diinginkan .

PELACAKAN HASIL SIMULASI Berikut ini adalah simulasi yang membuktikan hal di atas dan menunjukkan bagaimana A berhasil melakukan konvergensi menuju keterlambatan 3 detik dan B konvergensi sekitar keterlambatan 1 detik:

Penjelasan Angka: Setiap saluran mewakili 1 detik waktu (ukuran paket dipilih untuk memiliki waktu transmisi 1 detik untuk kejelasan). Perhatikan bahwa setiap node dapat memulai algo kapan saja tanpa urutan atau waktu tertentu. Kolomnya adalah sebagai berikut:

• NODE A menerima: Apa yang dilihat simpul A di sisi penerimanya (ini juga P4 di bawah)

• NODE A menyuntikkan: Apa simpul A mengirimkan (perhatikan ini adalah A, atau secara acak A atau B)

• P1, P2, P3: Tiga paket yang sedang transit (berurutan) antara A dan B (transmisi 1 detik berarti 3 paket sedang transit dengan latensi 3)

• NODE B menerima: Apa yang dilihat B di sisi penerimanya (ini adalah P3)

• NODE B menyuntikkan: Apa yang B kirim keluar (perhatikan ini B, atau secara acak A atau B per algo)

• P4: Paket dalam perjalanan dari B ke A (lihat juga P1, P2, P3)

• A menghitung A: Apa yang diperhitungkan untuk paket A yang telah dilihatnya

• A counts B: Apa yang diperhitungkan A untuk paket B yang telah dilihatnya

• B counts A: Apa yang diperhitungkan B untuk paket-paket A yang telah dilihatnya

• B counts B: Apa yang diperhitungkan B untuk paket B yang telah dilihatnya

• A-> B: Latensi yang diperkirakan A terhadap B (rasio RTT 4 detik berdasarkan paket yang terlihat)

• B-> A: Latensi yang B perkirakan menuju A (rasio RTT 4 detik berdasarkan paket yang terlihat)

Seperti yang kita dapat melihat kedua node bertemu dan tetap di sekitar latensi sebenarnya (sebenarnya kita tidak melihat itu untuk A karena diperlukan lebih banyak detik untuk konvergen tetapi konvergensi perilaku yang sama seperti B)

Filter yang lebih baik dapat konvergen lebih cepat tetapi kita dapat dengan jelas melihat bagaimana keduanya menyatu di sekitar nilai yang benar untuk keterlambatan mereka, oleh karena itu mereka dapat mengetahui dengan pasti mengetahui keterlambatan mereka (meskipun saya menunjukkan estimasi mereka hanya untuk ilustrasi).

Juga, bahkan jika bandwidth antar tautan berbeda, metode di atas masih bisa bertahan (walaupun kita harus memikirkannya lebih untuk lebih yakin) dengan menggunakan pasangan paket untuk mengetahui perkiraan bandwidth dan kemudian hanya menerapkan persamaan proporsi di atas.

Kesimpulan Kami menyediakan algoritma untuk A dan B untuk mengetahui posisi mereka dalam jaringan dan mengetahui latensi mereka ke node lain untuk diagram di atas. Kami menggunakan metode estimasi pengukuran jaringan daripada pendekatan berbasis jam yang memang tidak dapat mengarah ke solusi karena masalah sinkronisasi jam rekursif.

Catatan Saya sekarang mengedit jawaban ini memberikan semua simulasi karena tidak ada yang akan percaya saya menyelesaikannya sejauh yang Anda lihat di komentar pertama. Semoga dengan hasil ini seseorang dapat lebih diyakinkan dan menyetujui untuk membantu semua orang setidaknya menemukan satu kesalahan atau kebenaran dalam puzzle pengukuran jaringan ini!

Ini adalah jawaban untuk @ user3134164 tetapi terlalu besar untuk dikomentari.

$P_x$$x$$R_x$$x$

• $R_1 = (1 - R_2) \times (1 - P_2)$$R_2 = (1 - R_1) \times (1 - P_1)$$1 - R_2$$1 - P_2$
• $R_1$$R_2$$\frac{R_1}{1 - R_1}$$\frac{R_2}{1 - R_2}$

Inilah sebabnya saya percaya ini tidak akan membawa Anda ke mana pun. Tolong tunjukkan kesalahan yang bisa saya lakukan selama alasan ini.