Batas Baru Rasio Kompetitif Longest Queue Drop: 1,46929591 <= CR(LQD) <= 1,683652

Batas bawah dan batas atas yang diperbaiki untuk kebijakan manajemen buffer kanonik pada switch memori bersama

Alex Davydow; Sergey Nikolenko· 2026· DOI 10.48550/arXiv.2609.19157

Masalah inti

Longest Queue Drop (LQD) adalah kebijakan manajemen buffer kanonik untuk switch memori bersama, di mana switch memelihara satu buffer bersama untuk semua antrean keluaran. Rasio kompetitif (CR) LQD mengukur kinerja kasus terburuknya relatif terhadap kebijakan offline yang optimal. Sebelum penelitian ini, batas terbaik yang diketahui adalah CR(LQD) dalam [1,44546086, 1,6918]. Makalah ini memperbaiki kedua ujungnya: batas bawah dinaikkan menjadi CR (LQD) \geq 184815365566285/125784985866185 = 1, 46929591..., dan batas atas diturunkan menjadi CR (LQD) \leq 1, 683652 . Penulis juga mengidentifikasi dan memperbaiki celah dalam penurunan bukti yang dipublikasikan sebelumnya.

Hasil utamanya adalah: - Batas bawah: CR (LQD) \geq \frac{184815365566285}{125784985866185} = 1, 46929591... - Batas atas: CR (LQD) \leq 1, 683652 Hasil ini memperbaiki batas sebelumnya, yaitu 1,44546086 dan 1,6918. Batas bawah disertifikasi pada instans berhingga tertentu dan independen terhadap aturan tie. Batas atas dibuktikan melalui solusi bentuk tertutup dari relaksasi selubung kontinu dan berlaku untuk setiap aturan tie. Perbaikan pada langkah agregasi juga memulihkan batas yang dipublikasikan sebelumnya.

Longest Queue Drop (LQD) adalah kebijakan manajemen buffer kanonik untuk switch memori bersama, di mana switch memelihara satu buffer bersama untuk semua antrean keluaran. Rasio kompetitif (CR) LQD mengukur kinerja kasus terburuknya relatif terhadap kebijakan offline yang optimal. Sebelum penelitian ini, batas terbaik yang diketahui adalah CR(LQD) dalam [1,44546086, 1,6918]. Makalah ini memperbaiki kedua ujungnya: batas bawah dinaikkan menjadi CR (LQD) \geq 184815365566285/125784985866185 = 1, 46929591..., dan batas atas diturunkan menjadi CR (LQD) \leq 1, 683652 . Penulis juga mengidentifikasi dan memperbaiki celah dalam penurunan bukti yang dipublikasikan sebelumnya.

Untuk batas bawah, penulis memperkenalkan keluarga instans baru yang disebut *front-loaded family*. Mereka memberikan sertifikat bilangan bulat eksak pada instans berhingga tertentu, yang dievaluasi terhadap kebijakan offline yang benar-benar optimal. Batas tersebut terbukti independen terhadap aturan tie: sebuah coupling adaptif memindahkan nilai tersertifikasi ke setiap aturan tie deterministik non-clairvoyant dan ke setiap aturan tie teracak dalam pengertian adversary adaptif. Untuk batas atas, penulis mengganti relaksasi titik akhir per paket pada endgame Antoniadis dkk. (2024) dengan relaksasi selubung kontinu dari ekspresi pembayaran yang sama, yang mereka selesaikan secara eksak dalam bentuk tertutup. Batas atas ini berlaku untuk setiap aturan tie. Selain itu, mereka menemukan celah pada langkah agregasi (Lemma 18) dari bukti yang dipublikasikan dan memperbaikinya dengan satu lemma teramortisasi dan analisis finite-head yang eksak. Perbaikan tersebut memulihkan batas 1,6918 yang dipublikasikan dan jaminan konferensi yang lebih lemah 1,707 dari Antoniadis dkk. (ICALP 2021), serta mendukung peningkatan lebih lanjut.

Batas yang diperbaiki mempersempit celah pada rasio kompetitif LQD, sehingga batas bawah dan batas atas menjadi lebih dekat. Konstruksi batas bawah menggunakan keluarga instans baru dan argumen coupling adaptif yang menggeneralisasi batas tersebut ke seluruh aturan tie. Batas atas menggunakan relaksasi selubung kontinu, yang diselesaikan secara eksak, sehingga memberikan jaminan yang lebih ketat. Identifikasi dan perbaikan celah pada bukti yang dipublikasikan penting karena memvalidasi hasil sebelumnya dan memungkinkan peningkatan lebih lanjut. Penulis mencatat bahwa batas bawah bersifat eksak untuk instans dan aturan tie tertentu, tetapi coupling adaptif memastikan batas tersebut berlaku secara luas. Batas atas, karena independen terhadap aturan, merupakan jaminan yang kokoh. Penelitian selanjutnya dapat berfokus pada menutup celah yang tersisa antara 1,46929591 dan 1,683652.

Praktisi dan peneliti ilmu komputer

Membuka konten member…