ตารางเส้นทางเกิดขึ้นได้ยังไง

บทที่ 6 คำนวณเส้นทางโดยสมมติว่ามีข้อมูลลิงก์ทั้งเครือข่ายอยู่ในมือแล้ว บทนี้ถามว่าข้อมูลนั้นมาถึงได้ยังไง และมีสองสำนักคิดที่ตอบคนละแบบ

7.1 สำนักที่หนึ่ง: ทุกคนเห็นแผนที่ทั้งใบ (link-state)

แต่ละโหนดประกาศออกไปทั้งเครือข่ายว่า "ฉันมีเพื่อนบ้านชื่ออะไรบ้าง ลิงก์ละเท่าไหร่" ทุกคนเก็บประกาศของทุกคน แล้วต่างคนต่างมีแผนที่ทั้งใบเหมือนกัน จากนั้นรัน Dijkstra บนแผนที่นั้นเอง

ข้อดี: ทุกโหนดเห็นภาพเดียวกัน จึงตัดสินใจสอดคล้องกันและลู่เข้าเร็วเมื่อมีอะไรเปลี่ยน
ข้อเสีย: ค่าใช้จ่ายในการกระจายประกาศโตตามจำนวนโหนด และทุกครั้งที่ลิงก์ขยับก็ต้องประกาศใหม่

7.2 สำนักที่สอง: ทุกคนรู้แค่ที่เพื่อนบ้านบอก (distance-vector)

แต่ละโหนดไม่เก็บแผนที่เลย เก็บแค่ตารางว่า "ปลายทาง X ฉันไปถึงด้วยต้นทุนเท่าไหร่ และต้องส่งให้ใคร" แล้วบอกตารางนี้ให้เพื่อนบ้านฟังเป็นระยะ ใครได้ยินก็เอาไปบวกต้นทุนลิงก์ตัวเองแล้วอัปเดตตารางของตัว

ประหยัดกว่ามาก แต่แลกมาด้วยโรคประจำตัวที่ชื่อว่า count-to-infinity

7.3 พิสูจน์ด้วยตาเอง — เมื่อทุกคนเชื่อข่าวลือของกันและกัน

MAXH = 8                       # เพดานที่ประกาศว่า 'ไปไม่ถึง'
b_next, b_hops = "C", 3        # A เพิ่งตาย · B หันไปเชื่อข่าวจาก C แทน
c_next, c_hops = "B", 2

for rnd in range(1, 7):
    print(f"  รอบ {rnd}: B บอกว่าถึง A ใน {b_hops} hop (ผ่าน {b_next}) · C บอกว่า {c_hops} hop (ผ่าน {c_next})")
    if b_hops >= MAXH or c_hops >= MAXH:
        print(f"\n  ชนเพดาน {MAXH} -> ประกาศว่า A ไปไม่ถึง")
        break
    c_hops = b_hops + 1; c_next = "B"
    b_hops = c_hops + 1; b_next = "C"

ผลรันจริง

  รอบ 1: B บอกว่าถึง A ใน 3 hop (ผ่าน C) · C บอกว่า 2 hop (ผ่าน B)
  รอบ 2: B บอกว่าถึง A ใน 5 hop (ผ่าน C) · C บอกว่า 4 hop (ผ่าน B)
  รอบ 3: B บอกว่าถึง A ใน 7 hop (ผ่าน C) · C บอกว่า 6 hop (ผ่าน B)
  รอบ 4: B บอกว่าถึง A ใน 9 hop (ผ่าน C) · C บอกว่า 8 hop (ผ่าน B)

  ชนเพดาน 8 -> ประกาศว่า A ไปไม่ถึง

A ตายไปตั้งแต่ต้น แต่ B กับ C ใช้เวลาสี่รอบกว่าจะยอมรับ เพราะแต่ละฝ่ายเห็นอีกฝ่ายบอกว่า "ฉันไปถึงได้นะ" โดยไม่รู้ว่าเส้นทางที่อีกฝ่ายอ้างนั้นวิ่งผ่านตัวเองอยู่

💡 อุปมา — เหมือนสองคนยืนยันข่าวลือให้กันไปมา: "ได้ยินจากเขา" / "ก็ได้ยินจากคุณนั่นแหละ" · ไม่มีใครในวงรู้ว่าต้นทางของข่าวคือตัวเอง

การชนเพดานคือทางออกดิบ ๆ ที่ต้องมี — เป็นแนวคิดเดียวกับ TTL ในบทที่ 3 คือ ยอมรับว่าระบบจะเข้าใจผิด แล้ววางตัวหยุดไว้ ไม่ใช่พยายามทำให้ไม่ผิดเลย โปรโตคอลรุ่นใหม่ใช้วิธีที่ฉลาดกว่านั้น (แนบลำดับเวลา หรือแนบเส้นทางทั้งเส้นมาด้วย) แต่ทุกวิธีล้วนแก้ปัญหาเดียวกันนี้

อ่านแบบเต็มเล่ม