الگوریتم گره‌های بالا
الگوریتم گره‌های بالا (به انگلیسی: top-nodes algorithm، معروف به Rayrole's Algorithm) الگوریتمی برای مدیریت تقویم رزرو منابع است. این الگوریتم برای اولین بار در سال ۲۰۰۳ منتشر شد، و در سال ۲۰۰۹ بهبود یافته‌است. این الگوریتم هنگامی استفاده می‌شود که یک منبع بین کاربران زیادی به اشتراک گذاشته شده‌است (برای مثال پهنای باند در یک لینک ارتباط از راه دور یا ظرفیت دیسک در یک مرکز دادهٔ گسترده). هنگامی که احتیاجات یک منبع برنامه‌ریزی شوند، مدیر شبکه می‌تواند رزروهای صورت گرفته از منبع را بر روی یک تقویم پیاده‌سازی کند تا در در دسترس بودن شبکه را در هر لحظه در دست داشته باشد. این الگوریتم به کاربران اجازه می‌دهد کارهای زیر را انجام دهند:
تقویم به صورت یک درخت دودویی مرتب می‌شود که هر گره نشان دهندهٔ یک بازهٔ زمانی مشخص است. بازهٔ زمانی یک گره والد برابر اجتماع بازه‌های زمانی تمام فرزندانش است. ""
مدت زمان تحت پوشش یک رزرو توسط مجموعه ای از "گره‌های بالاً نشان داده می‌شود. این مجموعه، دقیقاً دورهٔ زمانی رزرو شده را پوشش می‌دهد و تعداد اعضای آن کمترین مقدار ممکن است. (مجموعه مینیمال است) یک گره مشخص از درخت دودویی زمانی «گره بالا» یک رزرو است که: مقدار زیر در هر گره ذخیره می‌شود:
q(node) = max(q(left child), q(right child)) + a
که در رابطه بالا a برابر تعداد نهایی منابع رزرو شده برای تمام رزروهایی است که این گره را به عنوان یک گره بالا دارند. (برای بهینه شدن کد، دو قسمت جمع بالا عموماً جداگانه ذخیره‌سازی می‌شوند)
این الگوریتم که در سال ۲۰۱۲ برای بهبود نسخه‌های پیشینِ ارائه شده منتشر شد، زمان مورد نیاز برای اجرای عملیات ابتدایی بر روی تقویم منابع رزرو شده را بهینه کرده و به حداقل رسانده‌است. از جمله عملیات‌هایی که از لحاظ زمانی بهبود بخشیده شده‌اند عبارت اند از: عملیات‌های حذف کردن یک رزرو یا اضافه کردن یک رزرو به درخت، محاسبهٔ مقدار منابع دردسترس و جلو بردن تقویم با گذشت زمان. مرتبه زمانی این عملیات‌ها مستقل از تعداد رزروها، طول بازه زمانی آنها و آنهاست. به منظور رسیدن به این مرتبه‌های زمانی بهینه، مدل Rayrole پیشنهاد می‌کند که یک درخت رزرو پویا ساخته شود و همین‌طور گره‌های حاوی رزروهای دائمی مدیریت شوند. با استفاده از همین دو اصل، Rayrole توانسته‌است مرتبه زمانی عملیات‌های ابتدایی درخت را به formula_1 برساند. به منظور رسیدن به این الگوریتم، موضوع مطالعهٔ او روشی برای به اشتراک گذاری منبعی به اندازهٔ formula_2 بین کاربران متعدد در یک شبکه ارتباط از راه دور یا یک سیستم محاسبه‌گر با شروع از یک تاریخ مشخص است.
درخت در این الگوریتم همچنان تعریف خود را حفظ کرده‌است (یعنی یک درخت دودویی است که هر گره آن نماینده یک بازه زمانی است) در این الگوریتم ادعاهای مختلفی به اثبات رسیده‌است که از جمله آنها داریم: ۱-به روزرسانی درخت:
این کار شامل چند مرحله است:
یک گره، زمانی گره مینیمم بازهٔ زمانی رزرو P است که:
۲- ایده ای که بر مبنای ایدهٔ ارائه شده در «۱» بیان شده‌است:
در این ایده هر گره از درخت شامل موارد زیر است:
formula_4 : ابتدا رزروهایی را که در میان گره‌های مینیمم خود، گره مورد نظر ما را دارند پیدا می‌کنیم. سپس حاصل جمع مقدار منبع تمام این رزروها را با نام formula_4 به عنوان یکی از مشخصه‌های گره ذخیره می‌کنیم.
formula_6: اگر گره انتخاب شده هیچ فرزندی نداشته باشد این مقدار را ۰ قرار می‌دهیم. در غیر این صورت، مقدار آن برابر ماکزیمم formula_7 در میان تمام فرزندان گره خواهد بود.
۳- ایده ای که بر مبنای ایده «۲» بیان شده‌است:
این ایده، ایده ای است که بیشتر شامل یکی از مراحل محاسبه مقدار formula_8 از منابع موجود در طول رزرو دوره P است، به این صورت که برای محاسبه آن داریم: اگر تاریخ شروع دوره P بعد از پایان یافتن دوره زمانی ای باشد که توسط ریشهٔ درخت نمایش داده می‌شود، داریم:
۴- این ایده بر مبنای ایدهٔ «۳» ارائه شده‌است:
در این ایده کمتر بودن مقدار formula_4 نسبت به مقدار formula_8 منجر به اضافه شدن تعدادی عملیات به مرحلهٔ اضافه کردن گره به درخت می‌شود:
اگر به گره موجود، گره فرزندی اضافه شود، مقدار formula_4 و formula_6 گره اضافه شده برابر صفر قرار گیرد.
درغیر این صورت، اگر گرهی اضافه شود و ریشه جدید باشد آنگاه:
اگر ریشهٔ قبلی چپ‌ترین فرزند ریشه جدید باشد: مقدار formula_4 گره جدید را برابر مقدار formula_14 قرار داده و از مقدار formula_4 ریشهٔ قبلی، مقدار formula_14 را می‌کاهیم.
اگر ریشهٔ قبلی شرایط حالت قبل را نداشته باشد: مقدار formula_4 ریشهٔ جدید را برابر صفر، مقدار formula_18 را به اندازه formula_14 افزایش داده، مقدار formula_14 را برابر ۰ و مجموع مقادیر formula_4 و formula_6 ریشه قدیمی را به عنوان formula_6 ریشه جدید قرار می‌دهیم.
مرحلهٔ بعدی اضافه کردن گره‌های برادر سمت راست ریشهٔ قدیمی می‌باشد، با این تغییرات که مقدار formula_4 در تمامی این گره‌های ذکر شده برابر مقدار formula_18 قرار گیرد و مقدار formula_6 همین گره‌ها صفر در نظر گرفته شود.
اگر دوره P یک دوره دائمی بدون تاریخ پایان باشد: اگر ریشه درخت یک گره مینیمم باشد، مقدار formula_14 به اندازه formula_28 افزایش داده شود، و در غیر این صورت مقدار formula_18 به اندازه formula_28 افزایش داده شود.
مقدار formula_28 به مولفه formula_4 همهٔ گره‌های مینیمم دوره P اضافه شود و مقدار formula_6 همهٔ گره‌های والد این گره‌های مینیمم به روز رسانی شود.
مزیت این الگوریتم این است که زمان ثبت یک رزرو منبع جدید فقط به اندازه تقویم بستگی دارد (و بستگی به تعداد رزروها ندارد). فرض می‌کنیم "n" تعداد دوره‌های اولیه تقویم باشد. حداکثر تعداد "گره‌های بالاً برای رزروی مشخص شده برابر formula_34 است.که در مرتبه زمانی بالا M برابر تعداد رزروهایی است که در طول دوره‌های زمانی تقویم موجود فعال هستند. (اگر رزرو منبع پس از پایان یافتن تقویم ممکن نباشد مقدار M برابر ۰ خواهد بود)