הקצאת משאבים ברשתות לקוח-שרת

Resource Allocation in Client-Server Networks

תיאור הפרויקט ותכולתו:

הפרוייקט יעסוק בבעיה של הקצאת משאבים במערכת שכוללת שרתים שמשרתים לקוחות. מערכת כזו כוללת קבוצת שרתים בעלי קיבול חסום וקבוצת לקוחות כאשר לכל לקוח יש דרישה למשאב, ורווח שהוא מוכן לשלם עם דרישתו תסופק במלואה. כמו כן, לכל לקוח נתונה תת קבוצה של שרתים שיכולים לשרת אותו (השייכות לקבוצה זו יכולה להיות קשורה, למשל, למיקום גיאוגרפי). פתרון הוא התאמה בין לקוחות למשאבי הספקים כך שמתקיים (1) לקוח מקבל משאבים רק משרתים שנמצאים בתת הקבוצה שלו, ו- (2) סך הדרישות שמשוייכות לשרת לא עולה על הקיבול שלו. המטרה היא למצוא פתרון שמביא למקסימום את הרווח הכולל של לקוחות שדרישותיהם מסופקות במלואן. הבעיה הנ"ל ממדלת הקצאת רוחב פס ברשתות סלולריות דור 4 ומיקום של גיבויים בענן.

במסגרת הפרוייקט הסטודנטים ילמדו על אלגוריתמי קירוב לפתרון הבעיה והכללות שלה, ויבחנו את ביצועיהם. בפרט, ביצועי האלגוריתמים יושוו לאלגורימים נאיביים ולביצועים שמובטחים מהניתוח התיאורטי שלהם.

תכולת הפרוייקט:
לימוד רקע תאורטי, לימוד האלגוריתמים לבעייה, מימוש האלגוריתמים, בניית כלי להשוואה בין ביצועי האלגוריתמים, בחירת משפחות קלטים שעליהן תבוצע ההשוואה, ניתוח ביצועי האלגוריתמים.

דרישות:

קדם: אלגוריתמים 1

מומלץ: תכנון וניתוח אלגוריתמים

מקורות:

D. Amzallag, R. Bar-Yehuda, D. Raz, G. Scalosub. Cell selection in 4G cellular networks. IEEE Transactions on Mobile Computing 12(7):1443-1455, 2013.

B. Patt-Shamir, D. Rawitz, G. Scalosub. Distributed approximation of cellular coverage. Journal of Parallel and Distributed Computing 72(3):402-408, 2012.

M. M. Halldórsson, S. Köhler, and D. Rawitz. Distributed approximation of k-service assignment. 19th International Conference On Principles Of DIstributed Systems (OPODIS), 2015.

email: dror.rawotz@biu.ac.il