|
|
עמוד:244
כמו-כן , אם הצומת המרכזי מפסיק לפעול , למשל עקב בעיית חומרה , עדכון טבלאות הניתוב יופסק , עד שצומתי הרשת יזהו את התקלה ויבחרו צומת אחר שישמש כצומת מרכזי . האפשרות השנייה נקראת ניתוב מבוזר ; כל צומת בונה לעצמו טבלת ניתוב . לשם כך צריך כל צומת לייצג את הרשת כולה ולקבל נתוני עומס מכל הרשת . מודדים את נתוני העומס בכל צומת בפרקי זמן קבועים , ומעבירים את תוצאות המדידה לכל הצמתים האחרים . היתרון של ניתוב מבוזר הוא שאין צורך לשדר טבלאות ניתוב ; כל צומת מחשב בעצמו את טבלת הניתוב שלו . בעיית התנודות באלגוריתמים דינמיים הבעיה של אלגוריתם ניתוב דינמי , המשתמש במידע עדכני על מידות העומס בצלעות הגרף , דומה במקצת לבעיה של כלב המנסה לתפוס את זנבו . האלגוריתם מנסה לצוד מטרה שנעה כל הזמן , ובנוסף , פעולת האלגוריתם עצמו משפיעה על תנועת המטרה . כדי להבהיר זאת נשתמש שוב בדוגמת רשת הכבישים . כאשר מנסים לכוון את התנועה בשעות עומס יכולה להתרחש שרשרת אירועים כדלקמן 1 * תחנת רדיו מודיעה על עומס בקטע מסוים . * נהגים רבים מנסים להימנע מהעומס על-ידי בחירת נתיב חלופי . * כתוצאה - הקטע שהיה עמוס מתפנה , והנתיב החלופי נעשה עמוס . * תחנת הרדיו מודיעה על העומס בנתיב החלופי . * הנהגים חוזרים לנתיב המקורי . תנודות כאלה יכולות להימשך , משום שכעת ייווצר שוב עומס בנתיב המקורי ושרשרת האירועים תחזור על עצמה . תופעה דומה עלולה לקרות גס באלגוריתמי ניתוב דינאמיים . האלגוריתם גורם לכך שמנות רבות ינותבו לנתיבים פנויים . כתוצאה מכך עלולים נתיבים אלה להפוך לעמוסים , ושוב ייווצרו פקקים ברשת . קיימות דרכים להקטין את התנודות ולהביא לניתוב יציב יותר אך במסגרת זו נסתפק בכך שהצגנו את הבעיה ונשאיר לתלמידים המתעניינים לחפש את הפתרונות לבעיה זו .
|
|