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

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

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

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

مدت زمان تحت پوشش یک رزرو توسط مجموعه ای از "گره‌های بالاً نشان داده می‌شود. این مجموعه، دقیقاً دورهٔ زمانی رزرو شده را پوشش می‌دهد و تعداد اعضای آن کمترین مقدار ممکن است. (مجموعه مینیمال است)
یک گره مشخص از درخت دودویی زمانی «گره بالا» یک رزرو است که:
* همه فرزندان آن در بازه زمانی رزرو قرار بگیرند و
* این گره باید ریشه باشد زیرا در غیر این صورت حداقل یکی از فرزندان گره والد خارج از بازه زمانی رزرو شده قرار خواهد گرفت.
وسط
*<small>گره‌های بالا برای رزروی از ساعت ۱ تا 5:59</small>*
مقدار زیر در هر گره ذخیره می‌شود:

```py
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_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 برابر ۰ خواهد بود)

## منابع

رده:الگوریتم‌های زمان‌بندی