|
|
עמוד:231
אפשרות אחרת היא להתייחס לקצב השידור המרבי האפשרי בערוץ . כזכור , לקצב השידור המרבי בערוץ ( הנמדד בסל '' ש ) נהוג לקרוא גם קיבולת ( capacity ) הערוץ . קיבולת הערוץ קובעת כמה זמן דרוש להעברת מנה באורך נתון בערוץ . למשל ; אם אורך המנה הוא 1000 סיביות וקצב השידור בערוץ הוא 1 M סל"ש , אזי זמן שידור המנה יהיה מילישנייה . קיבולת הערוץ מקבילה לאיכותו של קטע כביש ברשת כבישים . כולנו יודעים שקטעי כבישים נבדלים זה מזה לא רק באורכם אלא גם באיכותם . למשל , בדרך הררית מפותלת קשה לנסוע מהר ואילו בכביש ישר ורחב ( רב-נתיבים ) אפשר לנוע במהירות רבה . אולם , האורך והקיבולת של הערוץ אינם הגורמים היחידים הקובעים את מהירות המעבר בו . כל מי שנסע בכביש מהיר , כמו נתיבי אילון בשעות הבוקר , יודע שיש גורם חשוב נוסף שקובע את מהירות המעבר בכביש . גורם זה הוא העומס בכביש . גם כביש מהיר , באיכות גבוהה , יהפוך לאיטי מאוד כאשר העומס בו גבוה . עומס ברשת תקשורת יגרום לתורים בצמתים ; כאשר מנה מגיעה לצומת עמוס , היא נאלצת להמתין לתורה . לכן יש להוסיף לזמן השידור גם את זמן ההמתנה בתור . משום כך , אלגוריתמים רבים לניתוב מתייחסים לזמן שנמשכת העברת מנה מצומת לצומת , במקום להתייחס לקצב השידור המרבי בערוץ . צומת יכול לקבוע את זמן המעבר לצומת שכן , על-ידי משלוח מנת בדיקה מיוחדת מדי פעם . כאשר הצומת השכן מחזיר מנה זו , הצומת השולח קובע את המרחק אל הצומת השכן לפי הזמן שנדרש למנת הבדיקה להגיע אליו בחזרה ( זמן זה כולל המתנות בתורים של הצמתים . ( לפי אמת מידה זו , המסלול הקצר ביותר הוא גם המהיר ביותר . ללא קשר לאמת המידה שבה משתמשים , יש למצוא דרך לייצג מרחקים בגרף . כאשר האורך של כל צלע מיוצג בגרף , הוא נקרא גרף משוקלל . לכל צלע e בגרף משוקלל , מוצמד מספר חיובי , ( le ) המייצג את האורך ( או המשקל ) של הצלע . באיור 4 . 17 מוצגת דוגמה לגרף משוקלל המתאר רשת מסוימת . המספרים שליד הצלעות מייצגים את משקל הערוץ המתאים ; נהוג להשתמש גם במונח מחיר של צלע ואז מטרת האלגוריתם היא למצוא נתיב זול ביותר . היחידות שבהן אנו מודדים את מחירי הצלעות אינן חשובות כרגע . ברשת המתוארת באיור על-ידי גרף , יש נתיבים אחדים שאפשר לנוע
|
|