|
|
עמוד:235
סיווג של אלגוריתמים של ניתוב קיימים שני סוגים עיקריים של אלגוריתמי ניתוב ? אלגוריתמים ריכוזיים או גלובליים ( global routing algorithms ) שמשתמשים במידע מלא וגלובלי על כל הצמתים של הרשת כדי למצוא נתיבים קצרים ביותר . זה מחייב שהאלגוריתם יקבל בדרך כלשהי , מידע על הרשת , לפני ביצועו . החישוב עצמו יכול להתבצע במקום כלשהו או בכמה מקומות . נהוג לקרוא לאלגוריתמים מסוג זה גם בשם link state algorithms משום שהאלגוריתם צריך לדעת את המחיר של כל ערוץ ( link ) ברשת . אלגוריתמים לא-ריכוזיים Draw ( decentralized routing algorithms ) חישוב הנתיב הקצר ביותר נעשה באופן מחזורי ומבוזר . לאף אחד מהצמתים אין מידע מלא על כל הערוצים ברשת . במקום זאת , כל צומת מתחיל מכך שהוא יודע רק את המשקל של כל הערוצים היוצאים ממנו אל הצמתים השכנים . ואז , תוך תהליך מחזורי של חישוב והחלפת מידע עם הצמתים השכנים , הצומת מחשב בהדרגה את הנתיב הקצר ביותר ליעדים נתונים . האלגוריתמים מהסוג השני הם סבוכים יותר ולכן נתרכז בלימוד אלגוריתם גלובלי . אלגוריתם למציאת מסלול קצר בגרף ייצוג רשת התקשורת באמצעות גרף משוקלל מאפשר לפתור את בעיית הניתוב על-ידי מציאת מסלול קצר ביותר בגרף משוקלל . נעבור אפוא לדון באלגוריתם שהקלט שלו הוא ! גרף משוקלל ( לכל קשת נתון מחיר ) צומת מקור , S צומת יעד , T והפלט שלו הוא : מסלול קצר ביותר בין S ל-ד . לכאורה אפשר לאמץ את האלגוריתם הזה > מצא את השכן הקרוב ביותר אל צומת המקור , אחר-כך את השכן הקרוב ביותר אליו וכוי , עד שתגיע לצומת היעד . צומת נקרא בשם צומת פעיל כאשר בוחנים את השכנים שלו .
|
|