Distance vector routing — Bellman-Ford, RIP আর count-to-infinity

১ · ধারণা — প্রতিবেশীর মুখে শোনা পথ

পর্ব ১৫-এ দেখেছেন, routing হলো control plane-এর কাজ: পুরো নেটওয়ার্ক মিলিয়ে প্রতিটি router-এর routing table ভরা। পর্ব ২২-এ দেখেছেন টেবিলের গঠন, হাতে বসানো static route, আর routing protocol-এর দুই বড় ভাগ — একটি প্রতিষ্ঠানের ভেতরের IGP আর প্রতিষ্ঠানগুলোর মাঝের EGP. এবার প্রশ্ন: router-রা নিজেরা কীভাবে টেবিল বানায়? দুটি বড় পরিবার আছে। এই পর্বে প্রথমটি — distance vector; পরের পর্বে দ্বিতীয়টি, link state.

এই বিশ্বাসই distance vector-এর শক্তি আর দুর্বলতা। শক্তি: প্রতিটি router-এর কাজ খুব সরল, মেমরি কম লাগে, কোনো কেন্দ্র লাগে না। দুর্বলতা: প্রতিবেশী পুরোনো বা ভুল খবর দিলে সেই ভুলও ছড়ায়। তাই এর ডাকনাম “routing by rumour” — গুজবে চলা routing.

নামের মানে সোজা। প্রতিটি router-এর কাছে একটি তালিকা থাকে: প্রতিটি গন্তব্যের দূরত্ব (distance). সেই তালিকাকে গণিতের ভাষায় একটি vector ধরা হয় — তাই distance vector. দূরত্ব মাপা হয় একটি metric দিয়ে: কখনো শুধু কতগুলো hop, কখনো link-এর খরচ, delay বা bandwidth থেকে হিসাব করা একটি সংখ্যা।

 Router A-এর distance vector (গন্তব্য → দূরত্ব, পরের hop)
 ┌──────────┬────────┬──────────┐
 │ গন্তব্য   │ দূরত্ব  │ next hop │
 ├──────────┼────────┼──────────┤
 │ A        │ 0      │ —        │
 │ B        │ 1      │ B        │
 │ C        │ 3      │ B        │
 │ D        │ 6      │ B        │
 │ E        │ 7      │ B        │
 └──────────┴────────┴──────────┘
 প্রতিবেশীকে পাঠানো হয় শুধু প্রথম দুই কলাম: “আমার থেকে কে কত দূরে”

২ · Bellman-Ford সমীকরণ — একটি লাইনে পুরো যুক্তি

কিছু চিহ্ন ঠিক করি। নেটওয়ার্ককে একটি graph ধরুন: router হলো বিন্দু, link হলো রেখা। c(x,v) = router x থেকে প্রতিবেশী v-এর সরাসরি link-এর খরচ। d_x(y) = x থেকে y পর্যন্ত সবচেয়ে কম খরচের পথের মোট খরচ। তাহলে:

বাংলায়: “y পর্যন্ত আমার সবচেয়ে ছোট পথ = প্রতিটি প্রতিবেশী v-এর জন্য (v পর্যন্ত আমার link-এর খরচ + v থেকে y-এর সবচেয়ে ছোট দূরত্ব) — এদের মধ্যে সবচেয়ে ছোটটি।” যে v-তে সবচেয়ে ছোট মান আসে, সেই v-ই y-এর জন্য x-এর next hop.

কেন সমীকরণটি সঠিক — ছোট প্রমাণ

x থেকে y-এর যেকোনো পথ প্রথমে x-এর কোনো একটি প্রতিবেশী v-তে যায়। দুটি দিক দেখাতে হবে।

• বাঁ দিক ≤ ডান দিক: যেকোনো প্রতিবেশী v-এর জন্য “x থেকে v, তারপর v-এর সবচেয়ে ছোট পথে y” একটি বৈধ পথ, যার খরচ c(x,v) + d_v(y). সবচেয়ে ছোট পথ কোনো বৈধ পথের চেয়ে বেশি হতে পারে না।
• বাঁ দিক ≥ ডান দিক: ধরুন x থেকে y-এর সবচেয়ে ছোট পথের প্রথম hop v*. পথের বাকি অংশ v* থেকে y-এর একটি পথ, তাই তার খরচ অন্তত d_v*(y). অতএব d_x(y) ≥ c(x,v*) + d_v*(y) ≥ ডান দিকের minimum.

দুই দিক মিলে সমতা। এর পেছনের নীতিটি optimal substructure: সবচেয়ে ছোট পথের প্রতিটি অংশও সবচেয়ে ছোট। (ধরে নেওয়া হচ্ছে খরচ ঋণাত্মক নয়, যা নেটওয়ার্কে সবসময় সত্য।) Graph algorithm হিসেবে Bellman-Ford-এর পূর্ণ রূপ আর তার জটিলতা দেখতে পারেন DSA কোর্সের Bellman-Ford আর Floyd-Warshall পর্বে।

এবার সমীকরণটি একটি router-এ চালিয়ে দেখি। নিচের পাঁচ router-এর নেটওয়ার্ক পুরো পর্বে ব্যবহার হবে (সংখ্যাগুলো link-এর খরচ):

            A
         1 ╱ ╲ 4
          ╱   ╲
         B──2──C
         │    ╱ ╲
        7│  3╱   ╲6
         │  ╱     ╲
         D────1────E

 Link: A–B 1, A–C 4, B–C 2, B–D 7, C–D 3, C–E 6, D–E 1

শুরুতে (round ০) প্রতিটি router শুধু নিজের link-গুলো জানে। A-র vector: A = ০, B = ১, C = ৪, D = ∞, E = ∞ (∞ মানে “জানি না” বা “পৌঁছানো যায় না”). B আর C তাদের round ০-এর vector A-কে পাঠাল। A এখন সমীকরণটি প্রতিটি গন্তব্যে চালায়:

৩ · বিতরণকৃত, পুনরাবৃত্ত, asynchronous — algorithm-টি

Distance vector algorithm-কে তিনটি বিশেষণে বর্ণনা করা হয়, আর পরীক্ষায় এই তিনটিই প্রায়ই জিজ্ঞেস করা হয়:

• বিতরণকৃত (distributed): প্রতিটি router শুধু সরাসরি প্রতিবেশীর কাছ থেকে তথ্য পায়, হিসাব করে, আর ফল শুধু প্রতিবেশীকে জানায়। কোনো router পুরো topology জানে না।
• পুনরাবৃত্ত (iterative): বিনিময় আর হিসাব চলতেই থাকে, যতক্ষণ না কারও কাছে নতুন কিছু বলার থাকে। তারপর algorithm নিজে থেমে যায় — কেউ আলাদা করে থামার সংকেত দেয় না।
• Asynchronous: সব router একসাথে ঘড়ি মিলিয়ে কাজ করে না। যার কাছে যখন নতুন vector আসে, সে তখন হিসাব করে।

প্রতিটি router x তিনটি জিনিস রাখে: (১) প্রতিটি প্রতিবেশী v পর্যন্ত link-এর খরচ c(x,v); (২) নিজের distance vector D_x = [D_x(y) : প্রতিটি গন্তব্য y]; (৩) প্রতিটি প্রতিবেশীর সবশেষ পাওয়া vector D_v. পুরো algorithm:

প্রতিটি router x-এ:
  শুরু:  প্রতিটি গন্তব্য y-এর জন্য
           D_x(y) = c(x,y)  (y প্রতিবেশী হলে), নইলে ∞;  D_x(x) = 0
         নিজের vector সব প্রতিবেশীকে পাঠানো

  চিরকাল:
    অপেক্ষা — (ক) কোনো link-এর খরচ বদলাল, বা
              (খ) কোনো প্রতিবেশী নতুন vector পাঠাল, বা
              (গ) periodic timer বাজল
    প্রতিটি গন্তব্য y-এর জন্য:
        D_x(y) = min over v { c(x,v) + D_v(y) },  next_hop(y) = সেই v
    যদি কোনো D_x(y) বদলে থাকে  → সব প্রতিবেশীকে নতুন vector পাঠানো (triggered)
    timer বাজলে               → বদল না হলেও vector পাঠানো (periodic)

কখন পাঠাবে — periodic আর triggered update

কেন শেষ পর্যন্ত থামে — convergence-এর যুক্তি

সব router যদি একসাথে round ধরে কাজ করে (synchronous মডেল, পরীক্ষার হিসাবে এটিই ধরা হয়), তাহলে একটি সুন্দর সত্য প্রমাণ করা যায়: round k-এর পর প্রতিটি D_x(y) হলো সর্বোচ্চ k + ১টি link ব্যবহার করা পথগুলোর মধ্যে সবচেয়ে ছোটটির খরচ। Round ০-এ এটি সত্য (শুধু ১ link-এর পথ)। Round k-তে সত্য হলে round k + ১-এ x প্রতিবেশী v-এর “k + ১ link পর্যন্ত” মানের সাথে ১টি link যোগ করছে — ঠিক k + ২ link পর্যন্ত পথ। N টি router-এর নেটওয়ার্কে কোনো সবচেয়ে ছোট পথে N − ১-এর বেশি link থাকে না (থাকলে কোনো router দুবার আসত, অর্থাৎ একটি loop, যা বাদ দিলে খরচ কমে বা সমান থাকে)। তাই সর্বোচ্চ N − ২ round-এ সব ঠিক হয়ে যায়, আর পরের round-এ কিছুই বদলায় না — সেটিই থামার সংকেত। Router-রা asynchronous হলেও, খরচ স্থির থাকলে আর বার্তা শেষ পর্যন্ত পৌঁছালে algorithm একই উত্তরে পৌঁছায় — Bertsekas আর Gallager-এর “Data Networks” বইয়ে এর প্রমাণ আছে। এই স্থির অবস্থায় পৌঁছানোকে বলে convergence.

৪ · পূর্ণ উদাহরণ — round ধরে পাঁচটি টেবিল

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় সবচেয়ে প্রচলিত প্রশ্ন: “এই graph-এ distance vector চালান; প্রতিটি round-এর পর প্রতিটি router-এর টেবিল দেখান।” আগের পাঁচ router-এর নেটওয়ার্কে synchronous মডেলে হিসাব করি: প্রতি round-এ সবাই আগের round-এর vector পাঠায়, তারপর সবাই একসাথে নতুন করে হিসাব করে। প্রতিটি ঘরে লেখা “দূরত্ব (next hop)”; এই round-এ বদলানো ঘর মোটা অক্ষরে।

লক্ষ করুন A → E-এর মান: ∞ → ১০ → ৮ → ৭. প্রতিটি round-এ পথ একটি করে link লম্বা হওয়ার সুযোগ পায়, আর দূরত্ব শুধু কমে। এই হিসাব simulator-এ চালাই। কোডটি ঠিক উপরের নিয়ম মানে: প্রতি round-এ প্রত্যেকে আগের round-এর (old) vector দেখে নতুন হিসাব করে, আর কোনো মান না বদলালে থামে।

// Synchronous distance vector: once per round every router sends its vector
// to its neighbours, then every router recomputes with Bellman-Ford.
const links = [["A","B",1], ["A","C",4], ["B","C",2], ["B","D",7],
               ["C","D",3], ["C","E",6], ["D","E",1]];
const R = ["A", "B", "C", "D", "E"];
const cost = {};                         // cost[x][v] = cost of link x--v
R.forEach(x => cost[x] = {});
links.forEach(([u, v, c]) => { cost[u][v] = c; cost[v][u] = c; });
let D = {}; const hop = {};              // D[x][y] = distance, hop[x][y] = next hop
R.forEach(x => { D[x] = {}; hop[x] = {};
  R.forEach(y => { D[x][y] = x === y ? 0 : (cost[x][y] ?? Infinity);
                   hop[x][y] = cost[x][y] !== undefined ? y : "-"; }); });
const fmt = d => (d === Infinity ? "inf" : String(d)).padStart(5);
function show(r) {
  console.log("round " + r + "  to:" + R.map(y => y.padStart(5)).join(""));
  R.forEach(x => console.log("   " + x + " knows " + R.map(y => fmt(D[x][y])).join("")));
}
show(0);
for (let r = 1; ; r++) {
  const old = D; let changed = false; D = {};
  R.forEach(x => { D[x] = {};
    R.forEach(y => {
      if (x === y) { D[x][y] = 0; return; }
      let best = Infinity;               // d_x(y) = min over v of c(x,v) + d_v(y)
      for (const v in cost[x]) {
        const via = cost[x][v] + old[v][y];
        if (via < best) { best = via; hop[x][y] = v; }
      }
      D[x][y] = best; if (best !== old[x][y]) changed = true;
    }); });
  if (!changed) { console.log("round " + r + ": nothing changed -> converged"); break; }
  show(r);
}
R.forEach(x => console.log("next hops of " + x + ": " +
  R.filter(y => y !== x).map(y => y + "->" + hop[x][y]).join("  ")));

round 0  to:    A    B    C    D    E
   A knows     0    1    4  inf  inf
   B knows     1    0    2    7  inf
   C knows     4    2    0    3    6
   D knows   inf    7    3    0    1
   E knows   inf  inf    6    1    0
round 1  to:    A    B    C    D    E
   A knows     0    1    3    7   10
   B knows     1    0    2    5    8
   C knows     3    2    0    3    4
   D knows     7    5    3    0    1
   E knows    10    8    4    1    0
round 2  to:    A    B    C    D    E
   A knows     0    1    3    6    8
   B knows     1    0    2    5    6
   C knows     3    2    0    3    4
   D knows     6    5    3    0    1
   E knows     8    6    4    1    0
round 3  to:    A    B    C    D    E
   A knows     0    1    3    6    7
   B knows     1    0    2    5    6
   C knows     3    2    0    3    4
   D knows     6    5    3    0    1
   E knows     7    6    4    1    0
round 4: nothing changed -> converged
next hops of A: B->B  C->B  D->B  E->B
next hops of B: A->A  C->C  D->C  E->C
next hops of C: A->B  B->B  D->D  E->D
next hops of D: A->C  B->C  C->C  E->E
next hops of E: A->D  B->D  C->D  D->D

৫ · ভালো খবর দ্রুত, খারাপ খবর ধীরে — count-to-infinity

Convergence-এর প্রমাণ ধরে নিয়েছিল খরচ স্থির। বাস্তবে link-এর খরচ বদলায়, link নষ্টও হয়। তখন যা ঘটে, তা distance vector-এর সবচেয়ে বিখ্যাত দুর্বলতা।

ভালো খবর: খরচ কমলে

তিন router x, y, z: c(x,y) = ৪, c(y,z) = ১, c(x,z) = ৫০. গন্তব্য x. স্থির অবস্থায় y → x = ৪ (সরাসরি), z → x = ৫ (y হয়ে). এখন c(x,y) কমে ১ হলো। Round ১-এ y দেখে সরাসরি ১, জানিয়ে দেয়। Round ২-এ z হিসাব করে ১ + ১ = ২. Round ৩-এ কিছু বদলায় না। দুই round-এই সবাই জানল। ভালো খবর সবচেয়ে ছোট পথ ধরে এক round-এ এক hop করে ছড়ায়, কারণ কম মান সবসময় পুরোনো বেশি মানকে হারিয়ে দেয়।

খারাপ খবর: খরচ বাড়লে বা link নষ্ট হলে

একই নেটওয়ার্কে এবার c(x,y) বেড়ে ৬০ হলো। y দেখে: সরাসরি এখন ৬০, কিন্তু z তো বলেছিল “x আমার থেকে ৫”! y জানে না যে z-এর সেই ৫ আসলে y-এর নিজের ওপর দিয়েই। তাই y ধরে নেয় z হয়ে ১ + ৫ = ৬. z তখন y-এর নতুন ৬ শুনে নিজেকে ৭ করে, y তারপর ৮… দুজনে একে অপরের পুরোনো খবরে ভর করে প্রতি দুই round-এ ২ করে বাড়ায়। থামে তখনই, যখন z-এর হিসাবে y হয়ে খরচ সরাসরি link-এর ৫০ ছাড়িয়ে যায়। এই পর্বের synchronous মডেলে (round ১-এ y = ৬, শেষ বদল পর্যন্ত গুনে) বদল চলে ৪৭ round: round ৪৬-এ z সরাসরি ৫০-এ ফেরে, round ৪৭-এ y হয় ৫১ (z হয়ে), আর round ৪৮-এ কিছুই বদলায় না। Kurose ও Ross-এর পাঠ্যবইয়ে ঠিক এই উদাহরণের জন্য বলা আছে প্রায় ৪৪টি iteration (y আর z-এর বার্তা বিনিময়) — সেখানে গোনার ধরন আলাদা, তাই দুই সংখ্যা মেলানোর দরকার নেই। মূল কথা একই: দূরত্বের ফারাক যত বড়, তত বেশি round. আর এই পুরো সময় y আর z-এর মাঝে x-গামী packet একটি routing loop-এ ঘুরতে থাকে, যতক্ষণ না TTL শেষ হয় (পর্ব ২০)।

সবচেয়ে খারাপ অবস্থা: link পুরোপুরি নষ্ট আর কোনো বিকল্প পথই নেই। তখন থামার কোনো “৫০” নেই — দূরত্ব বাড়তেই থাকে অসীমের দিকে। একেই বলে count-to-infinity. সবচেয়ে সহজ উদাহরণ: তিনটি router একটি লাইনে, A — B — C, প্রতিটি link-এর খরচ ১ (hop count), গন্তব্য C.

কত round লাগে — ছোট হিসাব

Link-এর খরচ ১ আর অসীম = I ধরুন। ঘটনার পর round r-এ (r বিজোড় হলে B, জোড় হলে A) যার মান বদলায়, তার মান হয় r + ২: B-এর ৩, ৫, ৭…; A-র ৪, ৬, ৮… A-র মান I ছোঁয় যখন r + ২ = I, অর্থাৎ r = I − ২; পরের round-এ B. মোট I − ১ round — RIP-এ ১৫. সাধারণভাবে, loop-এর দুই প্রান্তের link-খরচ যত কম আর অসীম (বা বিকল্প পথের খরচ) যত বড়, তত বেশি round. তাই খারাপ খবরের ক্ষেত্রে convergence-এর সময়ের কোনো ভালো সীমা নেই, যেখানে ভালো খবর N − ২ round-এর মধ্যে পৌঁছায়।

নিচের simulator দুটি ঘটনা পাশাপাশি চালায়: সাধারণ distance vector, আর poison reverse (পরের অংশে বিস্তারিত) চালু করে। tell() ঠিক করে একজন প্রতিবেশীকে কী দূরত্ব বলা হবে।

// Line A --1-- B --1-- C, metric = hop count, destination C.
// At time 0 the link B--C fails. In every round each router recomputes from
// the distance its neighbour told it in the previous round.
const INF = 16;                                   // RIP: 16 means unreachable
function run(poison) {
  let A = { d: 2, via: "B" }, B = { d: 1, via: "C" };  // converged before failure
  // poison reverse: never tell a neighbour a real distance if you route via it
  const tell = (r, to) => (poison && r.via === to ? INF : r.d);
  let aHears = tell(B, "A"), bHears = tell(A, "B");
  const rows = [];
  for (let round = 1; round <= 20; round++) {
    const nb = Math.min(INF, 1 + bHears);         // B's only neighbour now: A
    const na = Math.min(INF, 1 + aHears);         // A's only neighbour: B
    const nA = { d: na, via: na < INF ? "B" : "-" };
    const nB = { d: nb, via: nb < INF ? "A" : "-" };
    if (nA.d === A.d && nB.d === B.d) break;      // nothing changed: stable
    A = nA; B = nB; rows.push([A, B]);
    aHears = tell(B, "A"); bHears = tell(A, "B");
  }
  return rows;
}
const show = r => r ? (r.d + "(" + r.via + ")").padEnd(7) : "".padEnd(7);
const plain = run(false), poisoned = run(true);
console.log("round | plain DV: A     B      | poison reverse: A     B");
plain.forEach((p, i) => {
  const q = poisoned[i] || [];
  console.log(String(i + 1).padStart(5) + " |           " + show(p[0]) + show(p[1]) +
    ("|                 " + show(q[0]) + show(q[1])).trimEnd());
});
console.log("plain DV needed " + plain.length + " rounds, poison reverse " +
  poisoned.length + " rounds to reach " + INF + " (unreachable)");

round | plain DV: A     B      | poison reverse: A     B
    1 |           2(B)   3(A)   |                 2(B)   16(-)
    2 |           4(B)   3(A)   |                 16(-)  16(-)
    3 |           4(B)   5(A)   |
    4 |           6(B)   5(A)   |
    5 |           6(B)   7(A)   |
    6 |           8(B)   7(A)   |
    7 |           8(B)   9(A)   |
    8 |           10(B)  9(A)   |
    9 |           10(B)  11(A)  |
   10 |           12(B)  11(A)  |
   11 |           12(B)  13(A)  |
   12 |           14(B)  13(A)  |
   13 |           14(B)  15(A)  |
   14 |           16(-)  15(A)  |
   15 |           16(-)  16(-)  |
plain DV needed 15 rounds, poison reverse 2 rounds to reach 16 (unreachable)

৬ · প্রতিকার — split horizon, poison reverse, অসীম ১৬, hold-down

সমস্যার মূল: A, B-কে এমন একটি পথের কথা বলছে যা B-এর ওপর দিয়েই যায়। কয়েকটি কৌশল মিলে এটি কমানো হয়।

দুটি শব্দ গুলিয়ে ফেলবেন না: route poisoning মানে যে router-এর route নষ্ট হলো, সে নিজেই সবাইকে metric ১৬ দিয়ে তা ঘোষণা করে; poison reverse মানে প্রতিবেশীকে তারই দিকের পথের জন্য ১৬ বলা। এবার poison reverse একই A — B — C লাইনে:

যেখানে poison reverse হার মানে — তিন router-এর loop

Poison reverse শুধু “যে আমাকে route দিয়েছে, তাকে ফেরত বলব না” — অর্থাৎ শুধু দুই router-এর loop ভাঙে। তিনটি router একটি ত্রিভুজে থাকলে গুজব ঘুরপথে ফেরে। নিচের নেটওয়ার্কে A, B, C একটি ত্রিভুজ, আর D যুক্ত শুধু C-এর সাথে; সব link-এর খরচ ১. A আর B দুজনেই D-তে যায় C হয়ে (দূরত্ব ২)। এবার C–D link নষ্ট:

      A ─── B
       ╲   ╱
        ╲ ╱
         C ──✂── D      গন্তব্য D · poison reverse সব জায়গায় চালু

// Triangle A-B-C with router D hanging off C; every link costs 1 (hops).
// Destination D. Split horizon with poison reverse is ON everywhere.
// At time 0 the link C--D fails.
const INF = 16;
const nbr = { A: ["B", "C"], B: ["A", "C"], C: ["A", "B"] };  // after failure
let st = { A: { d: 2, via: "C" }, B: { d: 2, via: "C" }, C: { d: 1, via: "D" } };
const advert = (from, to) => (st[from].via === to ? INF : st[from].d);
const heard = {};                    // heard[x][v] = distance v last told x
for (const x in nbr) { heard[x] = {}; nbr[x].forEach(v => heard[x][v] = advert(v, x)); }
const show = r => console.log(String(r).padStart(5) + "   " +
  ["A", "B", "C"].map(x => (st[x].d + " via " + st[x].via).padEnd(11)).join("").trimEnd());
console.log("round   A          B          C");
show(0);
for (let r = 1; r <= 25; r++) {
  const next = {};
  for (const x in nbr) {
    let best = { d: INF, via: "-" };
    nbr[x].forEach(v => {
      const c = Math.min(INF, 1 + heard[x][v]);
      if (c < best.d) best = { d: c, via: v };
    });
    next[x] = best;
  }
  const same = Object.keys(st).every(x => st[x].d === next[x].d && st[x].via === next[x].via);
  if (same) { console.log("round " + r + ": no change, all three say 16"); break; }
  st = next; show(r);
  for (const x in nbr) nbr[x].forEach(v => heard[x][v] = advert(v, x));
}

round   A          B          C
    0   2 via C    2 via C    1 via D
    1   2 via C    2 via C    16 via -
    2   3 via B    3 via A    16 via -
    3   16 via -   16 via -   4 via A
    4   16 via -   5 via C    16 via -
    5   6 via B    16 via -   16 via -
    6   16 via -   16 via -   7 via A
    7   16 via -   8 via C    16 via -
    8   9 via B    16 via -   16 via -
    9   16 via -   16 via -   10 via A
   10   16 via -   11 via C   16 via -
   11   12 via B   16 via -   16 via -
   12   16 via -   16 via -   13 via A
   13   16 via -   14 via C   16 via -
   14   15 via B   16 via -   16 via -
   15   16 via -   16 via -   16 via -
round 16: no change, all three say 16

৭ · RIP বাস্তবে — v1, v2, RIPng আর timer

RIP (Routing Information Protocol) distance vector-এর সবচেয়ে পরিচিত রূপ। এর শিকড় Xerox-এর XNS নেটওয়ার্কের একটি protocol-এ; আশির দশকে BSD Unix-এর routed প্রোগ্রামের মাধ্যমে এটি ব্যাপকভাবে ছড়ায়, আর ১৯৮৮ সালে RFC 1058-এ লিখিত মান পায়। Metric = hop count: প্রতিটি router পেরোলে ১; ১৬ মানে অসীম।

RIPv2-এর একটি বার্তা UDP-র ভেতরে এমন দেখায় (RFC 2453 অনুযায়ী; প্রতিটি সারি ৩২ bit):

 0               8               16                              31
┌───────────────┬───────────────┬───────────────────────────────┐
│ Command (1/2) │ Version (2)   │        must be zero           │ ← header, 4 byte
├───────────────┴───────────────┼───────────────────────────────┤
│ Address Family (2 = IPv4)     │        Route Tag              │ ┐
├───────────────────────────────┴───────────────────────────────┤ │
│                      IP Address (গন্তব্য)                      │ │ একটি route
├───────────────────────────────────────────────────────────────┤ │ = 20 byte;
│                      Subnet Mask                              │ │ এক বার্তায়
├───────────────────────────────────────────────────────────────┤ │ সর্বোচ্চ 25টি
│                      Next Hop                                 │ │
├───────────────────────────────────────────────────────────────┤ │
│                      Metric (1–16)                            │ ┘
└───────────────────────────────────────────────────────────────┘
 Command 1 = request ("আপনার টেবিল পাঠান"), 2 = response (vector)

Command ১ (request) পাঠায় সদ্য চালু হওয়া router — প্রতিবেশীর পুরো টেবিল চেয়ে; command ২ (response) হলো আসল vector. এক বার্তায় সর্বোচ্চ ২৫টি route, তাই সর্বোচ্চ ৪ + ২৫ × ২০ = ৫০৪ byte ডেটা; বড় টেবিল কয়েকটি বার্তায় যায়।

RIP-এর তিনটি timer

সংখ্যাগুলো RFC-র প্রস্তাবিত মান; বাস্তবায়নভেদে নাম আর মান আলাদা হতে পারে — যেমন Cisco-র ডকুমেন্টেশনে ডিফল্ট update ৩০, invalid ১৮০, hold-down ১৮০ আর flush ২৪০ সেকেন্ড। নিজের যন্ত্রের ডকুমেন্টেশন দেখে নেবেন। ৩০ সেকেন্ডের update “একটু এলোমেলো” করার কারণ আছে: সব router একসাথে update পাঠালে নেটওয়ার্কে একসাথে ঝাপটা আসে, আর পরস্পরের প্রভাবে router-গুলো নিজে থেকেই একই তালে চলে আসতে পারে — Sally Floyd আর Van Jacobson নব্বইয়ের দশকের শুরুতে periodic routing বার্তার এই synchronization নিয়ে একটি পরিচিত গবেষণা প্রকাশ করেন।

Hop count-এর দুর্বলতা

RIP-এর চোখে ১০ Gbps fiber আর ধীর পুরোনো লাইন দুটোই “১ hop”. দুই hop-এর ১০ Gbps পথ আর এক hop-এর ২ Mbps পথ থাকলে RIP বেছে নেবে ধীরটি। Offset বা কৃত্রিমভাবে metric বাড়িয়ে এটি কিছুটা সামলানো যায়, কিন্তু মূল সমস্যা থাকে। আর সর্বোচ্চ ১৫ hop — বড় নেটওয়ার্কে চলে না। এ কারণেই প্রতিষ্ঠানের ভেতরে OSPF বা IS-IS (পর্ব ২৪) বা EIGRP বেশি দেখা যায়।

Router-এ RIP চালু করা দেখতে এমন (উদাহরণ, Cisco IOS-ধাঁচের কনফিগারেশন; অন্য vendor-এর কমান্ড আলাদা):

! উদাহরণ — Cisco IOS-ধাঁচের কনফিগারেশন (ল্যাবে)
router rip
 version 2
 network 10.0.0.0
 no auto-summary
 passive-interface GigabitEthernet0/2

R1# show ip route rip
R     10.1.3.0/24 [120/2] via 10.1.12.2, 00:00:12, GigabitEthernet0/0
R     10.1.4.0/24 [120/1] via 10.1.14.4, 00:00:05, GigabitEthernet0/1

R মানে route-টি RIP থেকে শেখা। [120/2]-এর প্রথম সংখ্যা Cisco-তে RIP-এর administrative distance (একাধিক protocol একই prefix দিলে কাকে বিশ্বাস — পর্ব ২২), দ্বিতীয়টি metric (২ hop). 00:00:12 হলো শেষ update কতক্ষণ আগে এসেছে — ১৮০ সেকেন্ড পেরোলে route অচল। no auto-summary RIPv2-কে classful সংক্ষেপ করা থেকে থামায়; passive-interface সেই interface-এ update পাঠানো বন্ধ রাখে (যেমন ব্যবহারকারীদের LAN-এর দিকে) — নিরাপত্তার জন্যও ভালো অভ্যাস।

Linux-এ RIP চালাতে লাগে আলাদা routing daemon, যেমন FRRouting-এর ripd বা BIRD; kernel নিজে কোনো routing protocol চালায় না, শুধু টেবিল রাখে। এই পাতার কোড-চালানোর container-এ যাচাই করি — কোনো routing daemon চলছে কি, কেউ UDP 520-এ শুনছে কি:

echo "== routing daemons (RIP, OSPF, BGP...) in this container? =="
found=0
for p in /proc/[0-9]*; do
  name=$(cat "$p/comm" 2>/dev/null) || continue
  case "$name" in
    ripd|ripngd|routed|zebra|ospfd|bgpd|bird|bird6|watchfrr)
      echo "  found: $name (pid ${p#/proc/})"; found=1 ;;
  esac
done
if [ "$found" -eq 0 ]; then echo "  none: no ripd, routed, bird or frr process"; fi
echo "  processes visible: $(ls -d /proc/[0-9]* | wc -l)"
if command -v ps >/dev/null; then ps -eo pid,comm | head -n 6; else echo "  (ps not installed)"; fi
echo "== RIP's port in /etc/services =="
grep -wE '^(router|ripng)' /etc/services 2>/dev/null || echo "  (no entry or no /etc/services)"
echo "== any socket on UDP port 520 (hex 0208)? =="
if awk 'NR > 1 { split($2, a, ":"); if (a[2] == "0208") f = 1 } END { exit !f }' /proc/net/udp
then echo "  yes"; else echo "  no - nobody here listens for RIP"; fi
echo "== the kernel's table: /proc/net/route =="
cat /proc/net/route

== routing daemons (RIP, OSPF, BGP...) in this container? ==
  none: no ripd, routed, bird or frr process
  processes visible: 4
    PID COMMAND
      1 podman-init
      2 bash
     10 ps
     11 head
== RIP's port in /etc/services ==
  (no entry or no /etc/services)
== any socket on UDP port 520 (hex 0208)? ==
  no - nobody here listens for RIP
== the kernel's table: /proc/net/route ==
Iface	Destination	Gateway 	Flags	RefCnt	Use	Metric	Mask		MTU	Window	IRTT
tap0	00000000	0202000A	0003	0	0	0	00000000	0	0	0
tap0	0002000A	00000000	0001	0	0	0	00FFFFFF	0	0	0

RIP আজ কোথায়? সাধারণভাবে বলা যায়: ছোট নেটওয়ার্ক, ল্যাব আর প্রশিক্ষণ, কিছু পুরোনো বা সরল যন্ত্র, আর routing শেখার প্রথম ধাপ। বড় প্রতিষ্ঠান বা ISP-র ভেতরে এর জায়গা অনেক আগেই OSPF, IS-IS আর EIGRP নিয়েছে — তবে কোথায় ঠিক কতটা চলে, তার নির্ভরযোগ্য পরিসংখ্যান নেই। পরীক্ষা আর ইন্টারভিউতে অবশ্য RIP এখনো খুব প্রিয়, কারণ distance vector-এর সব ধারণা এতে স্পষ্ট দেখা যায়।

৮ · EIGRP-র DUAL আর distance vector বনাম link state

EIGRP — loop-মুক্ত distance vector

EIGRP (Enhanced Interior Gateway Routing Protocol) Cisco-র তৈরি, নব্বইয়ের দশকে আগের IGRP-র উত্তরসূরি হিসেবে আসে; দীর্ঘদিন শুধু Cisco-র যন্ত্রে চলত, পরে ২০১৬ সালে এর মূল অংশ একটি informational RFC (RFC 7868) হিসেবে প্রকাশ হয় — তবু অন্য vendor-এর সমর্থন সীমিত। ভেতরে এটি distance vector: প্রতিবেশীরা দূরত্ব জানায়, পুরো মানচিত্র নয়। কিন্তু এর কেন্দ্রে J.J. Garcia-Luna-Aceves-এর DUAL (Diffusing Update Algorithm), যার লক্ষ্য কোনো মুহূর্তেই loop না হতে দেওয়া। Metric-ও hop count নয় — ডিফল্টে মূলত পথের সবচেয়ে কম bandwidth আর মোট delay থেকে হিসাব। আর periodic নয়, শুধু বদল হলে আংশিক update.

DUAL-এর মূল কৌশল feasibility condition. দুটি শব্দ লাগবে: প্রতিবেশী v নিজে গন্তব্য পর্যন্ত যে দূরত্ব জানায়, তা reported distance (RD); আর আমার এখনকার সবচেয়ে ভালো মোট দূরত্ব feasible distance (FD). শর্ত: RD_v < FD হলে v-কে বিকল্প হিসেবে নিরাপদে নেওয়া যায়। যুক্তি: v-এর নিজের দূরত্ব আমার চেয়ে কম, তাই v-এর পথ আমার ওপর দিয়ে আসতে পারে না — এলে v-এর দূরত্ব আমার দূরত্বের চেয়ে বেশি হতো। এই শর্ত পূরণ করা বিকল্পকে বলে feasible successor; মূল পথ নষ্ট হলে router কাউকে জিজ্ঞেস না করেই সাথে সাথে তাতে চলে যায়। কোনো feasible successor না থাকলে router প্রতিবেশীদের “query” পাঠায় আর উত্তর না আসা পর্যন্ত route-টি “active” রাখে — অপেক্ষা করে, কিন্তু loop বানায় না।

আমাদের A — B — C লাইনে ভাবুন: A-র FD ২ (C পর্যন্ত)। B-এর জন্য A-র reported distance ২, আর B-এর FD ছিল ১. শর্ত ২ < ১ মিথ্যা — তাই A কখনো B-এর বিকল্প হতে পারে না। Count-to-infinity-র প্রথম ভুল পদক্ষেপটাই আটকে গেল। একই ধারণা পরে খোলা মানের Babel protocol-ও ব্যবহার করে (RFC 8966), যা mesh নেটওয়ার্কে দেখা যায়।

Distance vector বনাম link state — পাঠ্যবইয়ের তুলনা

Link state-এ (পর্ব ২৪) প্রতিটি router নিজের link-এর খবর পুরো নেটওয়ার্কে ছড়িয়ে দেয় (flooding), ফলে সবাই পুরো মানচিত্র পায় আর প্রত্যেকে নিজে Dijkstra চালায়। দুটির পার্থক্য (N = router-সংখ্যা, E = link-সংখ্যা):

তৃতীয় একটি পরিবারও আছে: path vector, যার প্রধান উদাহরণ BGP. এটি distance vector-এর মতোই প্রতিবেশীকে route জানায়, কিন্তু সাথে পুরো পথের তালিকা (কোন কোন autonomous system পেরিয়ে) পাঠায়। নিজের নাম পথের তালিকায় দেখলে router সেই route ফেলে দেয় — loop ধরার সবচেয়ে সরাসরি উপায়। বিস্তারিত পর্ব ২৫-এ।

৯ · AI-এর যুগে distance vector

“এই graph-এ distance vector-এর টেবিল বানিয়ে দিন” — AI এই কাজ দ্রুত করে, কিন্তু round গোনা আর tie-breaking-এ প্রায়ই ভুল করে, আর ভুলগুলো সুন্দর টেবিলে সাজানো থাকে বলে চোখে পড়ে না:

AI-এর উত্তর মানার আগে — চেকলিস্ট

• অন্তত দুটি ঘর নিজে Bellman-Ford সমীকরণে হিসাব করে মিলিয়েছি
• প্রতিটি round-এ শুধু আগের round-এর vector ব্যবহার হয়েছে কি না দেখেছি
• Port, multicast ঠিকানা, timer আর RFC নম্বর rfc-editor.org-এ খুলে মিলিয়েছি
• Vendor-এর কমান্ড (যেমন Cisco-র router rip) আর মানের নিয়ম আলাদা রেখেছি
• Routing কনফিগারেশন আগে ল্যাবে বা VM-এ চালিয়েছি, আর RIPv2-তে authentication আর passive-interface ভেবেছি