موضوع مقاله: الگوریتم گره‌های بالا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم گره‌های بالا | مقدمه: این الگوریتم هنگامی استفاده می‌شود که یک منبع بین کاربران زیادی به اشتراک گذاشته شده‌است (برای مثال پهنای باند در یک لینک ارتباط از راه دور یا ظرفیت دیسک در یک مرکز دادهٔ گسترده). | ## بخش 1: الگوریتم گره‌های بالا | هنگامی که احتیاجات یک منبع برنامه‌ریزی شوند، مدیر شبکه می‌تواند رزروهای صورت گرفته از منبع را بر روی یک تقویم پیاده‌سازی کند تا در در دسترس بودن شبکه را در هر لحظه در دست داشته باشد. این الگوریتم به کاربران اجازه می‌دهد کارهای زیر را انجام دهند: بررسی کنند که آیا مقدار مشخصی از یک منبع در یک بازهٔ زمانی معین موجود است یا نه، مقداری از منبع را برای بازهٔ زمانی مشخصی رزرو کنند، رزرو قبلی را حذف کنند، تقویم را به جلو حرکت دهند (تقویم مدت زمان مشخصی را پوشش می‌دهد، و با گذشت زمان باید به جلو منتقل شود). پیاده‌سازی تقویم به صورت یک درخت دودویی مرتب می‌شود که هر گره نشان دهندهٔ یک بازهٔ زمانی مشخص است. وسط نمونه ای از تقویم ۷ ساعته (با دوره‌های زمانی اولیه یک ساعته) مدت زمان تحت پوشش یک رزرو توسط مجموعه ای از "گره‌های بالاً نشان داده می‌شود. این مجموعه، دقیقاً دورهٔ زمانی رزرو شده را پوشش می‌دهد و تعداد اعضای آن کمترین مقدار ممکن است. (مجموعه مینیمال است) یک گره مشخص از درخت دودویی زمانی «گره بالا» یک رزرو است که: همه فرزندان آن در بازه زمانی رزرو قرار بگیرند و این گره باید ریشه باشد زیرا در غیر این صورت حداقل یکی از فرزندان گره والد خارج از بازه زمانی رزرو شده قرار خواهد گرفت. مرتبه زمانی این عملیات‌ها مستقل از تعداد رزروها، طول بازه زمانی آنها و دانه‌بندی آنهاست. | ## بخش 2: الگوریتم گره‌های بالا | به منظور رسیدن به این مرتبه‌های زمانی بهینه، مدل Rayrole پیشنهاد می‌کند که یک درخت رزرو پویا ساخته شود و همین‌طور گره‌های حاوی رزروهای دائمی مدیریت شوند. با استفاده از همین دو اصل، Rayrole توانسته‌است مرتبه زمانی عملیات‌های ابتدایی درخت را به برساند. به منظور رسیدن به این الگوریتم، موضوع مطالعهٔ او روشی برای به اشتراک گذاری منبعی به اندازهٔ بین کاربران متعدد در یک شبکه ارتباط از راه دور یا یک سیستم محاسبه‌گر با شروع از یک تاریخ مشخص است. یک گره، زمانی گره مینیمم بازهٔ زمانی رزرو P است که: اگر بازهٔ زمانی رزرو P یک دورهٔ غیر دائمی با تاریخ پایان مشخص باشد، گره مینیمم نشان دهنده یک بازهٔ زمانی است که زمان خود گره کاملاً درون بازه P قرار دارد اما زمان پدر گره به‌طور کامل در P قرار نمی‌گیرد. همچنین اگر بازه زمانی رزرو P یک دوره دائمی بدون تاریخ پایان مشخص باشد، گره مینیمم نماینده یک بازه زمانی است که به‌طور کامل در بازهٔ F قرار می‌گیرد. (بازهٔ F بازه‌ای است که از زمان شروع بازه P شروع می‌شود و زمان پایان آن برابر با زمان پایانِ بازهٔ زمانیِ ریشه درخت است) ۲- ایده ای که بر مبنای ایدهٔ ارائه شده در «۱» بیان شده‌است: در این ایده هر گره از درخت شامل موارد زیر است: : ابتدا رزروهایی را که در میان گره‌های مینیمم خود، گره مورد نظر ما را دارند پیدا می‌کنیم. سپس حاصل جمع مقدار منبع تمام این رزروها را با نام به عنوان یکی از مشخصه‌های گره ذخیره می‌کنیم. | ## بخش 3: الگوریتم گره‌های بالا | درغیر این صورت، اگر گرهی اضافه شود و ریشه جدید باشد آنگاه: اگر ریشهٔ قبلی چپ‌ترین فرزند ریشه جدید باشد: مقدار گره جدید را برابر مقدار قرار داده و از مقدار ریشهٔ قبلی، مقدار را می‌کاهیم. اگر ریشهٔ قبلی شرایط حالت قبل را نداشته باشد: مقدار ریشهٔ جدید را برابر صفر، مقدار را به اندازه افزایش داده، مقدار را برابر ۰ و مجموع مقادیر و ریشه قدیمی را به عنوان ریشه جدید قرار می‌دهیم. مرحلهٔ بعدی اضافه کردن گره‌های برادر سمت راست ریشهٔ قدیمی می‌باشد، با این تغییرات که مقدار در تمامی این گره‌های ذکر شده برابر مقدار قرار گیرد و مقدار همین گره‌ها صفر در نظر گرفته شود. اگر دوره P یک دوره دائمی بدون تاریخ پایان باشد: اگر ریشه درخت یک گره مینیمم باشد، مقدار به اندازه افزایش داده شود، و در غیر این صورت مقدار به اندازه افزایش داده شود. مقدار به مولفه همهٔ گره‌های مینیمم دوره P اضافه شود و مقدار همهٔ گره‌های والد این گره‌های مینیمم به روز رسانی شود. کارایی مزیت این الگوریتم این است که زمان ثبت یک رزرو منبع جدید فقط به اندازه تقویم بستگی دارد (و بستگی به تعداد رزروها ندارد). | ## جمع‌بندی | برخی پرسش‌ها و مرتبه زمانی آنها برای بررسی اینکه آیا در طی یک دوره زمانی مشخص مقدار معلومی از منبع موجود است یا خیر : ذخیره مقدار مشخصی از یک منبع برای بازهٔ زمانی خاص : برای حذف رزرو قبلی : برای حرکت تقویم به جلو : که در مرتبه زمانی بالا M برابر تعداد رزروهایی است که در طول دوره‌های زمانی تقویم موجود فعال هستند.