פתרון הודעות ונתיבי רשת

פתרון התרגיל הראשון

נחזיק את המספר הגבוה ביותר שראינו ואת bitmap של 32 המספרים האחרונים. בקבלת מספר גבוה יותר נזיז את החלון; בהפרש גדול או שווה ל32 נמחק את כל הbitmap במקום לבצע shift ברוחב לא חוקי. מספר בתוך החלון נבדק לפי הbit שלו, ומספר מחוצה לו מסווג כישן בלי לטעון שראינו אותו בעבר.

הקוד הבא הוא בדיקה מלאה של המודל ללא גלישת מספרי רצף. כדי לתמוך בגלישה צריך להגדיר חשבון סידורי וחלון שאינו יוצר עמימות בין קדימה לאחורה.

#include <cassert>
#include <cstdint>

enum class verdict { fresh, duplicate, old, invalid };
struct window {
    std::uint32_t highest = 0;
    std::uint32_t bits = 0;
    verdict accept(std::uint32_t sequence) {
        if (sequence == 0) return verdict::invalid;
        if (sequence > highest) {
            auto distance = sequence - highest;
            bits = distance >= 32 ? 0 : bits << distance;
            highest = sequence;
            bits |= 1;
            return verdict::fresh;
        }
        auto distance = highest - sequence;
        if (distance >= 32) return verdict::old;
        auto mask = std::uint32_t{1} << distance;
        if (bits & mask) return verdict::duplicate;
        bits |= mask;
        return verdict::fresh;
    }
};
int main() {
    window history;
    assert(history.accept(2) == verdict::fresh);
    assert(history.accept(1) == verdict::fresh);
    assert(history.accept(1) == verdict::duplicate);
    assert(history.accept(4) == verdict::fresh);
    assert(history.accept(3) == verdict::fresh);
    assert(history.accept(40) == verdict::fresh);
    assert(history.accept(2) == verdict::old);
}

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

פתרון התרגיל השני

אפשר לשלוח datagram ריק באמצעות sendto עם אורך אפס וpointer תקין. בקבלה נקבל אפס bytes כאשר ההודעה הגיעה, ולא סימון FIN. הparser שלנו ידחה את האורך כי הוא דורש שנים עשר bytes לפחות במבנה המעבדה הקבוע.

const char unused = 0;
if (sendto(sender.value, &unused, 0, 0,
           reinterpret_cast<sockaddr*>(&destination), sizeof(destination)) == SOCKET_ERROR)
    fail("send empty datagram");

נגדיל את מספר איטרציות הקבלה לחמש, אבל עדיין נטפל בtimeout משום שהפרוטוקול אינו מבטיח הגעה. נפריד בדוח בין תוצאת הAPI לבין החלטת parser, כדי לא לייחס לUDP את כלל האורך שאנחנו המצאנו.

פתרון התרגיל השלישי

אפשר להתחיל במועמד הראשון, ולהפעיל את השני לאחר השהיה קצרה שנבחרה במדיניות אם הראשון עוד לא הצליח. שני הניסיונות חולקים deadline כולל; השני אינו מקבל שתי שניות חדשות בלי קשר לזמן שכבר חלף. בתרחיש הנתון הוא יכול לנצח לפני שהראשון הגיע לtimeout.

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

נשמור בתוצאה את הכתובת שנבחרה לצורכי אבחון ואת שם היעד המקורי לצורך זהות. אם נבחרה כתובת אחרת בעקבות fallback, לא נחליף את השם המצופה בתעודה בשם שבחר הצד המרוחק.