Traffic Shaping Algorithms

[mizu]

Traffic Shaping Algorithms

טוב אנטידוט.. ביקשת - קיבלת. הייתי שמח לשמוע התנסויות ודעות לגבי היעילות של אלגוריתמים שונים לביצוע Traffic Shaping ברמת ה-Network וברמת ה-Transport. כבר כמה שנים ישנן משפחות של אלגוריתמים כללים לביצוע פעילויות QoS בכלל ו-Traffic Shaping בפרט, אבל לא יצא לי בשנים האחרונות להתעדכן לגבי ההתקדמויות בתחום המעניין הזה, ומדי פעם אני נתקל במצבים שבהם יישום של אלגוריתם כנ"ל היה יכול לייעל עבודה. לדעתי הצנועה, כדי להשיג ביצועים אופטימליים אין מנוס מלנתח את המערכת ואת התעבורה, ולתכנן אלגוריתם ספציפי שיענה על הדרישות. עם זאת אני בטוח שמישהו כבר חשב על אלגוריתמים אדפטיביים / חצי-אדפטיביים, שמצליחים בנסיבות מסויימות להגיע לביצועים אופטימליים או קרובים לאופטימליים. אז מי שיצא לו לחקור טיפה את הנושא, להתעניין, או ליישם אלגוריתם Traffic Shaping לשימוש ביתי או מסחרי... מוזמן להאיר את עינינו בנושא... (במיוחד אלה מכם שעובדים בחברות שהמוצרים שלהן מתיימרים לספק פתרונות כאלה, או ספקיות שירות שמספקות ללקוחות אפשרויות דומות, מעל לרמה של להתקין ולקנפג כלי קנוי.. אלא ברמת התיאוריה והאלגוריתם). מיזו

 

[antidot]

ישר מפציץ, אה ?

 

[shed]

60 שניות על QoS כפי שמומש ב-802.16

אני אתייחס יותר ל-QoS ופחות ל-bandwidth shaping במובן הקלאסי של המונח. כדי להשיג ביצועים אופטימלים אין מנוס מלבצע ניתוח מערכת, אבל לדעתי אין צורך בתיכנון ומימוש אלגוריתם ספציפי, יש לא מעט אלגוריתמים והתקנים מספיק ג'נרים ועם חופש פעולה רחב למדי. לאחר אפיון מערכת יהיה צורך בקנפוג נכון של הכלים, אין צורך להמציא את הגלגל מחדש. אני אתייחס או אפרט איך מומש QoS בתקן 802.16 (a/d). דרישות התקן: תמיכה במספר סוגי שירות: 1. CBR - שירות קבוע ומובטח. ללא שום תלות בצריכת התקנים אחרים ברשת. 2. CIR - שירות עם מינימום מובטח. אפשרות ל-burstים של מידע (עם מקסימום מובטח) במידה ויש משאבים פנויים. 3. BE - Best Effort - שירות עם מקסימום מובטח, אין התחייבות על מינמום. בנוסף התקן מגדיר עוד סוג שירות (אופציונלי למימוש): CBR-AD: זהו שירות מסוג CBR אשר מופעל עליו מנגנון של Activity Detection. כאשר אין שימוש בשירות הנ"ל - המשאב הופך להיות זמין לאחרים. ברגע שיש זיהוי של שימוש במשאב הזה הוא הופך להיות מובטח בדיוק כמו cbr. היתרון הגדול הוא שלא "מבזבזים" את ההקצאה של CBR גם כאשר הלקוח סגר את המשרד ויצא לשבועיים בפריז. בהגדרות התייחסתי ל"שירות" ולא לרוחב פס. שירות כולל: 1. רוחב פס בערוץ העולה ובערוץ היורד - אין תעדוף לצד אחד על פני השני. 2. latency. 3. Jitter. 4. priority. ספק שירות מגדיר לעצמו "חבילה" של שירותים, או SLA. כל SLA שכזה מגדיר את כל הדברים המצויינים מעלה. עד כאן הגדרות, נעבור לסוג של מימוש (כפי שמוגדר על ידי התקן). ההתקן המנהל (base station) מחזיק אצלו את כל חבילות ה-SLA שקיימים במערכת. כאשר התקן קצה (ציוד לקוח) מתחבר לרשת מתבצע תהליך אותנתיקציה אשר בסופו כל אחד מהצדדים (יחידת הבסיס ויחידת הקצה) יודעים אחד על קיומו של השני, איזה שירותים מוקצים לציוד הקצה הנ"ל ועוד. בין שאר הדברים שהציודים "מסכימים" עליהם אפשר למצוא גם רשימה של CID, או Connection ID. כל Mac Packet מכיל שדות שמורים ל-CID הנ"ל. כלומר, כל Mac Packet שמשודר באוויר (ואשר יכול להכיל מספר רב של ethernet packets) מכיל header מסויים ובו מצויין ה-CID המתאים לו. כאשר מגיע פאקט אתרנתי הוא עובר קלאסיפיקציה ע"פ מדיע שנמצא בשכבות 2, 3 ו-4. (ניתן לבצע קלאסיפיקציה לפי IP, לפי vlan ועוד). בסוף התהליך הזה אנחנו יודעים איזה סוג שירות הפאקט הזה אמור לקבל. אם נעזוב מילים גדולות אפשר לתאר את המנגנון בצורה הבאה: לכל סוג שירות יש צבע משלו. לכל צבע יש "דלי" בצבע המתאים. כאשר מגיע פאקט יש תהליך שמחליט לאיזה צבע הוא שייך ובהתאם לכך זורקים אותו לדלי המתאים. לכל דלי יש "חור" בתחתית לפי הגדרות השירות. דלי של שירות טוב יותר יהיה עם "חור" גדול יותר בתחתית. וכך מגיעים פאקטים מצד אחד, ממלאים את הדליים בזמנם החופשי. הדליים מצידם מתרוקנים לפי הגדות ספק השירות. המנגנון שתיארתי דואג לטפל הרוחב פס שונה עבור sla שונים. אבל אינו מכיל בתוכו את מנגנוני העדיפויות ואת מנגנוני סוג השירות (cbr, cir, be ועוד). פרמטרים אלה ממושמים על ידי מנגנונים אחרים אשר תפקידם לדעת איך לבצע את המשיכה מהדליים. מכיוון ש-tcp/ip הינה תעבורה burstית מטבעה, יש צורך במנגנון/אלגוריתם נוסף אשר ידאג ל"השטיח" את הפיקים בתעבורה. אפשר לחשוב על זה כעל interleaver כזה או אחר.

 

[mizu]

תודה על המידע.

האלגוריתם שתארת הוא יישום של אחד משני האלגוריתמים הותיקים לעניין ה-QoS בפאקטות, שמכונה Leaky Bucket. מה שמעניין זה שלפי התיאור שלך, ה-IETF בחר באלגוריתם Leaky Bucket של ה-ATM Forum, ולא בחר באלגוריתם השני, Token Bucket שתוכנן ע"י IETF.. כנראה באמת הדרישות היו שונות. למיטב ידיעתי הדור השלישי בסלולר משתמש ב-Token Bucket. אגב, הרעיון של שני האלגוריתמים כמעט זהה, וההבדל ביניהם זה בדיוק מה שאמרת בסוף: Leaky Bucket נותן ביצועים ללא bursts, בעוד Token Bucket נותן bursts. יש כמה ואריאציות שמשלבות בינהם וכך זוכות (בעקרון) בטוב משני העולמות, אולי זה מה שעשו גם כאן? מיזו

 

[shed]

--->

אכן כן, כמו שציינתי בסוף ההודעה, מעבר לדליים, או יותר נכון, במקביל/בנוסף/כל הגדרה אחרת עובדים עוד מספר מנגנונים אשר אחראים ל: 1 . תעדוף לפי סוג שירות - הדליים דואגים לטפל ברוחב פס שונה עבור sla שונים, אבל לא לוקחים בחשבון את סוג השירות (cbr, cir, be). 2. מנגנון "ריקון" הדליים מכיל מנגנון שמטפל ב-latnecy ו-jitter (שוב, שני פרמטרים של QoS אשר הדליים לא מטפלים בהם). 3. מנגנון נוסף דואג ליישר burstים. במילים ממש מגעילות אפשר להגיד שעושים קונב' על פונ' הכניסה. 4. מנגנון נוסף דואג "לדפוק את כולם באופן שווה" - כלומר, אם המערכת נמצאת במצב של overbooking, כולם יידפקו בצורה שווה. מי שקנה מגה אולי לא יקבל את המגה שלו, אבל יקבל פי שניים ממי שקנה חצי מגה. כל הפרמטרים הנ"ל נמצאים ב-mac header ומוגדרים בסטנדרט. המימושים שונים בין יצרן ליצרן.

 

[ariev]

חוץ מ-leaky/token bucket ישנם

אלגוריתמים נוספים. אחד מאוד מעניין זה WRED, שמטפל יפה בתעבורת TCP. בגדול הרעיון הוא לזרוק פאקטים בצורה כזאת שלא נפגע יותר מידי ב-flow, אבל נבקר עליו מספיק לתת ביצועים בפי שרוצים...

 

[mizu]

יפה, WRED... תודה אריה

נו, אמרתי שבטח מישהו כבר פיתח משהו אדפטיבי. קראתי על זה עכשיו, נשמע מאוד מעניין. הרעיון של לזרוק פאקטות בצורה רנדומית מוטה לפי הסתברויות מעבר מרקוביות או התפלגויות פואסוניות... די מרשים, ואפילו מתבקש אם חושבים על זה. למה להתאמץ הרבה בלנתח ולבנות חוקים... התעבורה לא משקרת. ראיתי שיש מוצרים של סיסקו עם יישום WRED, מישהו התנסה? זה באמת "לומד" את הרשת כמו שזה מתיימר? מיזו

 

[antidot]

הםםם

אחרי שעברתי על המסמך הזה, התעוררו כמה סוגיות: 1) אני חייב ריענון דחוף בהסתברות (בזה אני בספק אם תוכלו לעזור לי...) 2) כמה שאני מבין, WRED עובד עם פרמטרים קבועים של thresholds ושל Max Dropping Probability. צויין בסוף המאמר שיש טעם לחקור התאמה דינמית של פרמטרים של WRED (מתבקש). אז אומנם כל class מתועדף לפי ההתפלגות שלו, את הפרמטרים של אותו class צריך להגדיר לבד. 3) לא מתיימר להבין יותר מדי בתחום, אבל נתקלתי בחיפושי אחרי WRED בלינק הבא, המציג פרוטוקול בשם WRT שמתיימר להרחיב את WRED ע"י כך שהפרוטוקול מבטיח לא לחנוק לגמרי את התעבורה המוגדרת כבעלת הסתברות הפלה גבוהה יותר.

 

[mizu]

המממ

בקשר להסתברות, זה לא מסובך מדי... אבל בטח שמחוץ לסקופ. אני הבנתי שהדרך שמוצעת לקנפג את WRED היא לעשות אנליזה לתעבורה באמצעים הסטטיסטים שתוארו (מרקוב) ולקבל מזה פרמטרים חד-משמעיים שיתאימו. זה טיפה שונה מאלגוריתם אדפטיבי עצמאי לחלוטין שעושה את זה תוך כדי הפעולה... אבל עדיין הרבה יותר טוב מכלום - ואולי לא הבנתי נכון? לכן שאלתי על יישומים. בקשר ל-WRT, למעשה WRED בעצמו מונע חנק באמצעות המנגנון ההתסברותי שלו, אבל מה ש-WRT עושה הוא "להעניש" תורים באופן שונה בהתאם לחסם, שמגיעים אליו רק בזמן עומס. כך בעצם הוא "מגן" בצורה אקטיבית על תעבורה חלשה ע"י להבטיח שלא מעיפים אותה מעבר לחסם. בנוסף עושה רושם ש-WRT מסתמך בלחלקו גם על ההנחה של Assured Forwarding, שזאת התנהגות מוגדרת שח ראוטרים שנותנת מינימום בטחון בהנחות מסויימות... אני לא יודע כמה ראוטרים תומכים בהתנהגות הזאת (שכוללת תיוג ושאר ירקות QoS). מיזו

 

[antidot]

המממם

אני הבנתי שאנליזה מסתבכת עבור תורים גדולים וההמלצה היא לבצע סימולציה עבור queues גדולים. לגבי WRT: כנראה לא התנסחתי נכון. הכוונה שלי הייתה למה שאמרת (ניסוח נכון אף פעם לא היה הצד החזק שלי). לגבי ההנחות, עוד לא הגעתי לזה.

 

[ariev]

WRED זהו עולם לא גמור

כלומר הדעות חלוקות ויש המון מחקרים שיוצאים כל הזמן על האפקטיביות שלו. לדעתי והבנתי הוא מאוד יעיל בסביבות שבהן יש כמות גדולה של TCP Flows, מאחר ושם ניתן להשפיע בצורה קלה יחסית על הביצועים הכוללים של קווים שמנים. אני יכול להגיד מניסיון מעשי שזה עובד יפה מאוד

 

[shed]

---> אדפטיביות ב-leak bucket

ב-802.16 יש מנגנון אפדטיבי אשר מקטין או מגדיל את "גודל החור" הכל דלי, על פי נתוני התעבורה בכל רגע נתון. (התקן מגדיר קבועי זמן של 2.5, 5, 10 ו-20 מילי שניה). אותה אדפטיביות מבטיחה שתמיד תהיה תעבורה ושלא יהיה מצב בו קונקשן נסגר לחלוטין.

 

[ariev]

יש חור בדלי... (לפי המנגינה)