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