ให้ router แต่ละตัวรู้เฉพาะ link ที่ต่อถึงตน แลกเปลี่ยน distance vector กับเพื่อนบ้าน แล้วค้นพบเส้นทางสั้นที่สุดด้วยตนเอง กดดูทีละ synchronous round เพื่อตรวจ message, routing table ที่เปลี่ยน และการลู่เข้า
| ปลายทาง | Cost | Next hop |
|---|
| Round | Vectors sent | Entries changed | Routers updated | Max finite cost | Status |
|---|
Router x ไม่ได้รับ topology ทั้งกราฟ แต่เก็บ vector Dₓ และ cost ของ link ที่ติดกัน เริ่มแรกจึง route ได้เพียงตนเองและเพื่อนบ้าน โครงสร้างนี้ทำให้อัลกอริทึมทำงานแบบกระจายศูนย์ได้
D[x][x] = 0 D[x][neighbor] = linkCost D[x][other] = infinity
เมื่อถึงขอบรอบ router ส่ง vector รอบก่อนให้เพื่อนบ้าน Router x ทดลองไปทุกปลายทาง y ผ่านเพื่อนบ้าน v ทุกตัว การอัปเดตใช้ message จากรอบเดียวกันทั้งหมด จึงเห็น causality ชัดเจน
candidate = cost(x,v) + Dv[y]
if candidate < Dx[y]:
Dx[y] = candidate
nextHop[x][y] = vเมื่อครบหนึ่งรอบแล้วไม่มีช่องใดเปลี่ยน router ทั้งหมดลู่เข้าสำหรับ topology ปัจจุบัน การเพิ่ม link cost ทำให้ความรู้เดิมใช้ไม่ได้และเริ่มแลกเปลี่ยนใหม่ Lab นี้ตั้งต้นใหม่จาก direct links เพื่อให้ตรวจ reconvergence ได้โดยไม่ซ่อน stale route
repeat synchronousRound() until changedEntries == 0 message complexity per round: O(|E| · |V|)