פרוטוקול העץ הפורש

פרוטוקול העץ הפורש (באנגלית: (The Spanning Tree Protocol (STP) הוא פרוטוקול תקשורת שנועד למנוע לולאות ברשת מקומית המגושרת באמצעות גשרים או מתגים בחיבור ל-Ethernet. הפעולה הבסיסית של STP היא למנוע לולאות שעלולות לגרום ל-Broadcast ורב-נתיב. עץ פורש מאפשר לכלול קישורים עודפים (redundant links) כדי לספק גיבוי נתיבים במקרה ונתיב פעיל מושבת ללא סכנת לולאות וללא הצורך באפשור/ביטול קישורים בצורה ידנית.
פרוטוקול העץ הפורש מבוסס על אלגוריתם שנכתב על ידי רדיה פרלמן בזמן שעבדה בחברת דיגיטל. הוא תוקנן לראשונה בתקן IEEE 802.1D ובתקן 802.1d-1998 אך בתקן 802.1d-2004 נשמר רק לצורך תאימות לאחור והוחלף בפרוטוקול העץ הפורש המהיר (The Rapid Spanning Tree Protocol (RSTP.

הפרוטוקול מייצג את טופולוגיית הרשת של רשת מקומית באמצעות גרף בלתי מכוון שבו כל צומת מייצג גשר או מתג וכל קשת מייצגת קישור באמצעות מדיות תקשורת ולעיתים גם רכיבי תקשורת בשכבה הפיזית של מודל ה-OSI. המטרה של הפרוטוקול היא ליצור טופולוגיית רשת של עץ פורש באמצעות חישוב משותף (כלומר חישוב מבוזר) של הרכיבים בשכבת הקו של מודל ה-OSI ברשת המקומית.

פרוטוקול העץ הפורש (802.1D)
בפרוטוקול העץ הפורש כל אחד מהפורטים בטופולוגיה העודפת עובר בין חמשת המצבים הבאים:

לא-פעיל (Disabled)
האזנה (Listening)
למידה (Learning)
העברה (Forwarding)
חסימה (Blocking)

בסיום התהליך כל אחד מהפורטים במתגים בהם מופעל הפרוטוקול מקבל אחד משלושת התפקידים הבאים:

root port: בכל מתג נבחר פורט אחד שהעלות להגיע ממנו למתג השורש היא הנמוכה ביותר.
designated port: פורט שנבחר במשותף על ידי מתגים שיש להם פורטים באותו מתחם התנגשות ושהעלות להגיע ממנו אל השורש היא הנמוכה ביותר.
non-designated port או blocked port: כל פורט שלא נבחר כ-root port או designated port עובר למצב חסימה על מנת לחסום נתיבים עודפים ולהימנע מלולאות.

לשלב ההאזנה והלמידה מוקצה זמן שנגזר מפרמטרים כמו קוטר הרשת (כלומר המרחק המקסימלי בין שני צמתים בטופולוגיה) וזמן ההעברה של BPDU בין שני פורטים (BPDU transmission delay). באופן זה ניתן להבטיח שכל אחד מהפורטים יקבל מספיק נתונים על מנת להחליט אם הוא חלק מטופולוגיית העץ הפורש ואיזה כתובות MAC הוא מעביר או חוסם.

מצב האזנה

מצב זה הוא החשוב ביותר כיוון שבו נבנה העץ הפורש. תהליך בניית העץ מורכב משלושה תתי-שלבים:

בחירה של מתג השורש (root bridge election): בחירת מתג השורש מבוססת על התיעדוף שניתן לכל אחד מהמתגים (bridge priority) על ידי מנהל הרשת וכתובת ה-MAC שלו שנקבעת על ידי היצרן. המתג הנבחר הוא זה שערך ה-bridge priority שלו הוא הנמוך ביותר, ואם קיים יותר ממתג אחד עם ערך כזה נבחר המתג בעל כתובות ה-MAC הנמוכה ביותר. בפועל, כל אחד מהמתגים ברשת מקבל מזהה (bridge id) המורכב משרשור של ה-bridge priority וכתובת ה-MAC שלו, והמתג בעל המזהה הנמוך ביותר נבחר כמתג השורש. מכיוון שהפרוטוקול משתמש בחישוב מבוזר, תהליך הבחירה מתחיל בכך שכל אחד מהמתגים רואה את עצמו כמתג השורש ומפרסם את ה-bridge id שלו באמצעות חבילות BPDU. ברגע שמתג מקבל BPDU עם bridge id נמוך משלו הוא מפסיק לשלוח BPDUs. בסיום התהליך נשאר מתג אחד שמפיץ BPDUs עם ה-bridge id שלו, וזהו המתג בעל ה-bridge id הנמוך ביותר. במידה ומנהל הרשת לא מתעדף מתג כלשהו ברשת, הפרוטוקול נותן לו את ערך ברירת המחדל 32,768. מכאן שאם אף אחד מהמתגים ברשת לא הוגדר, מתג השורש שיבחר הוא זה שכתובת ה-MAC שלו היא הנמוכה ביותר. יותר מכך, אם כל המתגים ברשת שייכים לאותו היצרן המתג שיבחר הוא הישן ביותר מביניהם.
בחירת הנתיבים בעלי העלות הנמוכה ביותר (least cost path) למתג השורש: בשלב זה, מתג השורש מפיץ חבילות BPDU עם ערך 'root path cost' אפס, וכל מתג שמקבל חבילת BPDU מוסיף ל-'root path cost' את העלות של הקישור שדרכו התקבלה החבילה.כך יכול כל מתג לדעת מה העלות של שליחת חבילה לשורש דרך כל אחד מהפורטים הפעילים שלו. באמצעות המידע הזה, כל מתג בוחר את הפורט שהעלות שלו היא הנמוכה ביותר על המתג ונותן לו תפקיד של 'root port'.(זהו הפורט שדרכו המתג יעביר חבילות מידע למתגים אחרים ברשת.) מבין הפורטים הנותרים, נבחר בכל סגמנט פורט אחד שעלותו היא הנמוכה ביותר ולו ניתן תפקיד של 'designated port'. (זהו הפורט שדרכו יועברו חבילות מידע שנשלחו על ידי כל המתגים שה-'root port' שלהם שייך לאותו סגמנט.)
חסימת שאר הנתיבים ברשת המקומית: בשלב זה נחסמים נתיבים חלופיים על מנת ליצור טופולוגיה לוגית של עץ פורש שמהגדרתו אין בו לולאות.

מצב חסימה

במצב זה הפורט לא מקבל ולא שולח מידע. כמו כן, הוא לא שולח BPDUs אבל כן מאזין ל-BPDUs על מנת ללמוד על שינויים בטופולוגיה הפיזית שדורשים חישוב מחדש של הטופולוגיה הלוגית (כלומר, העץ הפורש).

קישורים חיצוניים

פרוטוקולי תקשורת
אתרנט