الگوریتم گره‌های بالا

الگوریتم گره‌های بالا (به انگلیسی: top-nodes algorithm، معروف به Rayrole's Algorithm) الگوریتمی برای مدیریت تقویم رزرو منابع است. این الگوریتم برای اولین بار در سال ۲۰۰۳ منتشر شد، و در سال ۲۰۰۹ بهبود یافته‌است. این الگوریتم هنگامی استفاده می‌شود که یک منبع بین کاربران زیادی به اشتراک گذاشته شده‌است (برای مثال پهنای باند در یک لینک ارتباط از راه دور یا ظرفیت دیسک در یک مرکز دادهٔ گسترده). هنگامی که احتیاجات یک منبع برنامه‌ریزی شوند، مدیر شبکه می‌تواند رزروهای صورت گرفته از منبع را بر روی یک تقویم پیاده‌سازی کند تا در در دسترس بودن شبکه را در هر لحظه در دست داشته باشد. این الگوریتم به کاربران اجازه می‌دهد کارهای زیر را انجام دهند:

• بررسی کنند که آیا مقدار مشخصی از یک منبع در یک بازهٔ زمانی معین موجود است یا نه،
• مقداری از منبع را برای بازهٔ زمانی مشخصی رزرو کنند،
• رزرو قبلی را حذف کنند،
• تقویم را به جلو حرکت دهند (تقویم مدت زمان مشخصی را پوشش می‌دهد، و با گذشت زمان باید به جلو منتقل شود).

پیاده‌سازی

تقویم به صورت یک درخت دودویی مرتب می‌شود که هر گره نشان دهندهٔ یک بازهٔ زمانی مشخص است. بازهٔ زمانی یک گره والد برابر اجتماع بازه‌های زمانی تمام فرزندانش است.

نمونه ای از تقویم ۷ ساعته (با دوره‌های زمانی اولیه یک ساعته)

مدت زمان تحت پوشش یک رزرو توسط مجموعه ای از "گره‌های بالاً نشان داده می‌شود. این مجموعه، دقیقاً دورهٔ زمانی رزرو شده را پوشش می‌دهد و تعداد اعضای آن کمترین مقدار ممکن است. (مجموعه مینیمال است) یک گره مشخص از درخت دودویی زمانی «گره بالا» یک رزرو است که:

• همه فرزندان آن در بازه زمانی رزرو قرار بگیرند و
• این گره باید ریشه باشد زیرا در غیر این صورت حداقل یکی از فرزندان گره والد خارج از بازه زمانی رزرو شده قرار خواهد گرفت.

گره‌های بالا برای رزروی از ساعت ۱ تا 5:59

مقدار زیر در هر گره ذخیره می‌شود:

q(node) = max(q(left child), q(right child)) + a

که در رابطه بالا a برابر تعداد نهایی منابع رزرو شده برای تمام رزروهایی است که این گره را به عنوان یک گره بالا دارند. (برای بهینه شدن کد، دو قسمت جمع بالا عموماً جداگانه ذخیره‌سازی می‌شوند)

الگوریتم Rayrole

این الگوریتم که در سال ۲۰۱۲ برای بهبود نسخه‌های پیشینِ ارائه شده منتشر شد، زمان مورد نیاز برای اجرای عملیات ابتدایی بر روی تقویم منابع رزرو شده را بهینه کرده و به حداقل رسانده‌است. از جمله عملیات‌هایی که از لحاظ زمانی بهبود بخشیده شده‌اند عبارت اند از: عملیات‌های حذف کردن یک رزرو یا اضافه کردن یک رزرو به درخت، محاسبهٔ مقدار منابع دردسترس و جلو بردن تقویم با گذشت زمان. مرتبه زمانی این عملیات‌ها مستقل از تعداد رزروها، طول بازه زمانی آنها و دانه‌بندی آنهاست. به منظور رسیدن به این مرتبه‌های زمانی بهینه، مدل Rayrole پیشنهاد می‌کند که یک درخت رزرو پویا ساخته شود و همین‌طور گره‌های حاوی رزروهای دائمی مدیریت شوند. با استفاده از همین دو اصل، Rayrole توانسته‌است مرتبه زمانی عملیات‌های ابتدایی درخت را به $O(log(n))$ برساند. به منظور رسیدن به این الگوریتم، موضوع مطالعهٔ او روشی برای به اشتراک گذاری منبعی به اندازهٔ $Q_{total}$ بین کاربران متعدد در یک شبکه ارتباط از راه دور یا یک سیستم محاسبه‌گر با شروع از یک تاریخ مشخص است.

ساخت درخت در الگوریتم Rayrole

درخت در این الگوریتم همچنان تعریف خود را حفظ کرده‌است (یعنی یک درخت دودویی است که هر گره آن نماینده یک بازه زمانی است) در این الگوریتم ادعاهای مختلفی به اثبات رسیده‌است که از جمله آنها داریم: ۱-به روزرسانی درخت:

این کار شامل چند مرحله است:

• یکی ضبط یک دوره زمانی برای رزرو P که شامل مقدار $Q_{r}$ از منابع می‌باشد که این کار توسط یک کاربر صورت می‌گیرد
• مرحله ای شامل اضافه کردن گره‌ها به درخت به صورتی که ریشهٔ درخت، تاریخ شروع بازهٔ P را دربر بگیرد و
• در روش Rayrole، مرحله اضافه کردن گره به درخت، شامل اضافه کردن تمام گره‌های مینیمم بازه زمانی رزرو P نیز می‌شود.

گره مینیمم چیست؟

یک گره، زمانی گره مینیمم بازهٔ زمانی رزرو P است که:

• اگر بازهٔ زمانی رزرو P یک دورهٔ غیر دائمی با تاریخ پایان مشخص باشد، گره مینیمم نشان دهنده یک بازهٔ زمانی است که زمان خود گره کاملاً درون بازه P قرار دارد اما زمان پدر گره به‌طور کامل در P قرار نمی‌گیرد. همچنین
• اگر بازه زمانی رزرو P یک دوره دائمی بدون تاریخ پایان مشخص باشد، گره مینیمم نماینده یک بازه زمانی است که به‌طور کامل در بازهٔ F قرار می‌گیرد. (بازهٔ F بازه‌ای است که از زمان شروع بازه P شروع می‌شود و زمان پایان آن برابر با زمان پایانِ بازهٔ زمانیِ ریشه درخت است)

۲- ایده ای که بر مبنای ایدهٔ ارائه شده در «۱» بیان شده‌است:

در این ایده هر گره از درخت شامل موارد زیر است:

$Q_{n}$ : ابتدا رزروهایی را که در میان گره‌های مینیمم خود، گره مورد نظر ما را دارند پیدا می‌کنیم. سپس حاصل جمع مقدار منبع تمام این رزروها را با نام $Q_{n}$ به عنوان یکی از مشخصه‌های گره ذخیره می‌کنیم.

$Q_{f}$: اگر گره انتخاب شده هیچ فرزندی نداشته باشد این مقدار را ۰ قرار می‌دهیم. در غیر این صورت، مقدار آن برابر ماکزیمم $Q_{n}+Q_{f}$ در میان تمام فرزندان گره خواهد بود.

۳- ایده ای که بر مبنای ایده «۲» بیان شده‌است:

این ایده، ایده ای است که بیشتر شامل یکی از مراحل محاسبه مقدار $Q_{d}$ از منابع موجود در طول رزرو دوره P است، به این صورت که برای محاسبه آن داریم: اگر تاریخ شروع دوره P بعد از پایان یافتن دوره زمانی ای باشد که توسط ریشهٔ درخت نمایش داده می‌شود، داریم:

$Q_{d}=Q_{total}-Q_{p0}-Q{p1}$

حال $Q_{p0}$ و $Q_{p1}$ را تعریف می‌کنیم:

$Q_{p0}$ : متغیری است که برابر مجموع مقادیر منابعی است که برای رزروهای دائمی ذخیره شده‌اند و ریشه درخت را به عنوان گره مینیمم در خود دارند.

$Q_{p1}$ : با حفظ شرایط $Q_{P0}$ تعریف می‌شود با این تفاوت که ریشه درخت اصلی جزو گره‌های مینیمم نمی‌باشد. در این صورت رابطه به شکل زیر تبدیل خواهد شد:

$Q_{total}-\max _{i\in \{minimum\,nodes\,of\,P\}}(Q_{n}(i)+Q_{f}(i)+\sum _{j\in \{parents\,of\,i\}}^{}Q_{n}(j))$

۴- این ایده بر مبنای ایدهٔ «۳» ارائه شده‌است:

در این ایده کمتر بودن مقدار $Q_{n}$ نسبت به مقدار $Q_{d}$ منجر به اضافه شدن تعدادی عملیات به مرحلهٔ اضافه کردن گره به درخت می‌شود:

اگر به گره موجود، گره فرزندی اضافه شود، مقدار $Q_{n}$ و $Q_{f}$ گره اضافه شده برابر صفر قرار گیرد.

درغیر این صورت، اگر گرهی اضافه شود و ریشه جدید باشد آنگاه:

اگر ریشهٔ قبلی چپ‌ترین فرزند ریشه جدید باشد: مقدار $Q_{n}$ گره جدید را برابر مقدار $Q_{p0}$ قرار داده و از مقدار $Q_{n}$ ریشهٔ قبلی، مقدار $Q_{p0}$ را می‌کاهیم.

اگر ریشهٔ قبلی شرایط حالت قبل را نداشته باشد: مقدار $Q_{n}$ ریشهٔ جدید را برابر صفر، مقدار $Q_{p1}$ را به اندازه $Q_{p0}$ افزایش داده، مقدار $Q_{p0}$ را برابر ۰ و مجموع مقادیر $Q_{n}$ و $Q_{f}$ ریشه قدیمی را به عنوان $Q_{f}$ ریشه جدید قرار می‌دهیم.

مرحلهٔ بعدی اضافه کردن گره‌های برادر سمت راست ریشهٔ قدیمی می‌باشد، با این تغییرات که مقدار $Q_{n}$ در تمامی این گره‌های ذکر شده برابر مقدار $Q_{p1}$ قرار گیرد و مقدار $Q_{f}$ همین گره‌ها صفر در نظر گرفته شود.

اگر دوره P یک دوره دائمی بدون تاریخ پایان باشد: اگر ریشه درخت یک گره مینیمم باشد، مقدار $Q_{p0}$ به اندازه $Q_{r}$ افزایش داده شود، و در غیر این صورت مقدار $Q_{p1}$ به اندازه $Q_{r}$ افزایش داده شود.

مقدار $Q_{r}$ به مولفه $Q_{n}$ همهٔ گره‌های مینیمم دوره P اضافه شود و مقدار $Q_{f}$ همهٔ گره‌های والد این گره‌های مینیمم به روز رسانی شود.

کارایی

مزیت این الگوریتم این است که زمان ثبت یک رزرو منبع جدید فقط به اندازه تقویم بستگی دارد (و بستگی به تعداد رزروها ندارد). فرض می‌کنیم "n" تعداد دوره‌های اولیه تقویم باشد. حداکثر تعداد "گره‌های بالاً برای رزروی مشخص شده برابر $2log(n)$ است.

برخی پرسش‌ها و مرتبه زمانی آنها

• برای بررسی اینکه آیا در طی یک دوره زمانی مشخص مقدار معلومی از منبع موجود است یا خیر : $O(log(n))$
• ذخیره مقدار مشخصی از یک منبع برای بازهٔ زمانی خاص : $O(log(n))$
• برای حذف رزرو قبلی : $O(log(n))$
• برای حرکت تقویم به جلو : $O(log(n)+M.log(n))$

که در مرتبه زمانی بالا M برابر تعداد رزروهایی است که در طول دوره‌های زمانی تقویم موجود فعال هستند. (اگر رزرو منبع پس از پایان یافتن تقویم ممکن نباشد مقدار M برابر ۰ خواهد بود)