Link state routing — Dijkstra আর OSPF

১ · মূল ধারণা — প্রতিটি router-এর হাতে পুরো মানচিত্র

পর্ব ২২-এ দেখেছেন, routing-এর কাজ প্রতিটি router-এর routing table ভরা — কোন গন্তব্যের packet কোন next hop-এ যাবে। কাজটি স্বয়ংক্রিয়ভাবে করার দুটি বড় ঘরানা আছে। পর্ব ২৩-এর distance vector-এ প্রতিটি router শুধু প্রতিবেশীদের কাছ থেকে শোনে, “আমার হিসাবে অমুক জায়গা এত দূরে”. পুরো নেটওয়ার্ক কেমন, তা কেউ জানে না। এই পর্বের ঘরানাটি উল্টো: প্রতিটি router পুরো নেটওয়ার্কের মানচিত্র জানে, তারপর নিজে নিজে সবচেয়ে ছোট পথ হিসাব করে। এর নাম link state routing.

নেটওয়ার্ককে graph হিসেবে দেখা

Routing algorithm-এর চোখে নেটওয়ার্ক একটি graph: প্রতিটি router একটি node, প্রতিটি link একটি edge, আর প্রতিটি edge-এর একটি সংখ্যা — link cost. Cost কী দিয়ে ঠিক হবে, তা নেটওয়ার্ক প্রশাসকের সিদ্ধান্ত: গতি কম হলে বেশি cost, দামি বা দূরের link হলে বেশি cost, অথবা সব link-এর cost ১ (তখন “সবচেয়ে ছোট পথ” মানে সবচেয়ে কম hop). একটি পথের cost = পথের সব link-এর cost-এর যোগফল। Graph-এর মৌলিক ধারণা DSA কোর্সের Graph পর্বে আছে।

পুরো পর্বে আমরা এই ৬টি router-এর নেটওয়ার্ক ব্যবহার করব (পাঠ্যবইয়ে বহুল ব্যবহৃত একটি উদাহরণ; প্রতিটি সংখ্যা link-এর cost, আর link দুই দিকেই একই cost):

        ┌──────────── 5 ────────────┐
        │                           │
        │      v ─────── 3 ──────── w
        │     ╱ │                ╱  │ ╲
        │    2  │ 2           3     │ 1 ╲ 5
        │   ╱   │          ╱        │     ╲
        u       │       ╱           │       z
          ╲     │    ╱              │     ╱
           1    │ ╱                 │   2
             ╲  │╱                  │ ╱
                x ─────── 1 ─────── y

 Link: u-v 2, u-x 1, u-w 5, v-x 2, v-w 3, x-w 3, x-y 1, w-y 1, w-z 5, y-z 2

প্রশ্ন: u থেকে প্রতিটি router-এ যাওয়ার সবচেয়ে কম cost-এর পথ কোনটি, আর তাই u-এর forwarding table-এ কোন গন্তব্যের জন্য কোন link? Link state routing এই প্রশ্নের উত্তর দেয় দুই ভাগে — আগে মানচিত্র জোগাড় (অংশ ২), তারপর হিসাব (অংশ ৩)।

২ · মানচিত্র জোগাড়ের চার ধাপ — hello, cost, LSA আর flooding

প্রতিটি router-কে চারটি কাজ করতে হয়, তারপর পঞ্চম কাজ হিসাব:

পঞ্চম ধাপ: যখন সব LSA জমা হয়, প্রতিটি router-এর link-state database (LSDB)-তে পুরো graph থাকে। তখন প্রতিটি router নিজেকে উৎস ধরে Dijkstra চালায় (অংশ ৩)। লক্ষ করুন, একটি LSA-তে কী থাকে — router x-এর LSA দেখতে মোটামুটি এমন:

┌─────────────────────────────────────────────┐
│ Advertising router : x                      │
│ Sequence number    : 0x80000005             │
│ Age                : 0 s  (বাড়তে থাকবে)       │
├─────────────────────────────────────────────┤
│ Neighbour u  cost 1                         │
│ Neighbour v  cost 2                         │
│ Neighbour w  cost 3                         │
│ Neighbour y  cost 1                         │
└─────────────────────────────────────────────┘

৬টি router-এর ৬টি এমন LSA জোড়া দিলেই অংশ ১-এর পুরো ছবি। প্রতিটি link দুই প্রান্তের দুটি LSA-তেই আসে; বাস্তবে দুই দিকের ঘোষণা মিললে তবেই link-টি হিসাবে ধরা হয়।

Flooding-এর নিয়ম — sequence number কেন লাগে

Flooding শুনতে সরল: নতুন কিছু পেলে সবাইকে জানানো। কিন্তু জালের মতো নেটওয়ার্কে একই LSA অনেক পথে ঘুরে একই router-এ বারবার আসে। আবার পথে দেরি হওয়া একটি পুরোনো কপি নতুনটির পরে পৌঁছাতে পারে। Router কীভাবে জানবে কোনটি নতুন? উত্তর sequence number: প্রতিটি router নিজের প্রতিটি নতুন LSA-তে নম্বর এক বাড়ায়। গ্রাহক router-এর নিয়ম মাত্র তিনটি:

Reliable শব্দটির মানে: প্রতিটি LSA পাঠানোর পর প্রেরক ack-এর অপেক্ষা করে; নির্দিষ্ট সময়ে ack না এলে আবার পাঠায় (OSPF-এ এই সময় ডিফল্টে ৫ সেকেন্ড — vendor অনুযায়ী বদলানো যায়)। এটি পর্ব ১০-এর ARQ-র ধারণাই, শুধু প্রতিটি প্রতিবেশীর সাথে আলাদাভাবে।

Age কেন লাগে

প্রতিটি LSA-র একটি age (বয়স) থাকে, যা database-এ বসে থাকতে থাকতে বাড়ে। OSPF-এ সর্বোচ্চ বয়স (MaxAge) ৩,৬০০ সেকেন্ড, অর্থাৎ এক ঘণ্টা। এর দুটি কাজ: (১) কোনো router হঠাৎ বন্ধ হয়ে গেলে তার পুরোনো LSA চিরকাল database-এ থাকবে না — বয়স MaxAge-এ পৌঁছালে মুছে যায়। (২) তাই প্রতিটি router নিজের LSA নিয়মিত (OSPF-এ প্রতি ৩০ মিনিটে) নতুন sequence number দিয়ে আবার ছাড়ে, কিছু না বদলালেও। কোনো LSA ইচ্ছা করে তুলে নিতে চাইলে router তার বয়স MaxAge বসিয়ে flood করে — সবাই সেটি মুছে দেয়।

Sequence number-এর একটি ফাঁদ: রিবুটের পর router নিজের শেষ নম্বর ভুলে ছোট নম্বরে LSA পাঠাতে পারে। সমাধান তৃতীয় নিয়মেই — নিচের stepper-এর শেষ দুই ধাপ দেখুন।

Mesh: A–B, A–C, B–C, B–D, C–E, D–E. সবার কাছে A-র LSA-র sequence ৪. এবার A-র একটি link বদলাল।

একই তিন নিয়ম কোডে। Simulator বার্তাগুলো একটি সারিতে (queue) রাখে আর পাঠানোর ক্রমে একে একে পৌঁছায়, প্রতিটি পৌঁছানোয় router কী করল তা ছাপে:

// Reliable flooding of router A's LSA over a small mesh, using sequence numbers.
const nbr = { A: ["B","C"], B: ["A","C","D"], C: ["A","B","E"], D: ["B","E"], E: ["C","D"] };
const db = { A: 4, B: 4, C: 4, D: 4, E: 4 };   // seq of A's LSA each router holds now
let queue = [], sent = 0, nextSeq = 0;
const send = (from, to, seq) => { queue.push({ from, to, seq }); sent++; };
function receive({ from, to, seq }) {
  const mine = db[to];
  let what;
  if (to === "A" && seq > mine) {                 // my OWN LSA came back newer than mine
    nextSeq = seq + 1;
    what = `my own LSA is newer than mine -> must re-originate with seq ${nextSeq}`;
  } else if (seq > mine) {                        // newer: install, ack, pass it on
    db[to] = seq;
    const out = nbr[to].filter(n => n !== from);
    out.forEach(n => send(to, n, seq));
    what = `ACCEPT (had ${mine}), ack ${from}, forward to ${out.join(",") || "-"}`;
  } else if (seq === mine) what = "duplicate -> discard, ack only";
  else {                                          // older: discard, send newer copy back
    send(to, from, mine);
    what = `STALE (have ${mine}) -> discard, send seq ${mine} back to ${from}`;
  }
  console.log(`  ${from}->${to} seq ${seq}: ${what}`);
}
function flood(title, origin, seq) {
  console.log(title); queue = []; sent = 0;
  db[origin] = seq;
  nbr[origin].forEach(n => send(origin, n, seq));
  while (queue.length) receive(queue.shift());
  console.log(`  messages: ${sent}, databases: ${JSON.stringify(db)}\n`);
}
flood("1) A's link changed: A floods seq 5", "A", 5);
flood("2) A rebooted, forgot its counter, floods seq 1", "A", 1);
flood(`3) A jumps to seq ${nextSeq} and floods again`, "A", nextSeq);

1) A's link changed: A floods seq 5
  A->B seq 5: ACCEPT (had 4), ack A, forward to C,D
  A->C seq 5: ACCEPT (had 4), ack A, forward to B,E
  B->C seq 5: duplicate -> discard, ack only
  B->D seq 5: ACCEPT (had 4), ack B, forward to E
  C->B seq 5: duplicate -> discard, ack only
  C->E seq 5: ACCEPT (had 4), ack C, forward to D
  D->E seq 5: duplicate -> discard, ack only
  E->D seq 5: duplicate -> discard, ack only
  messages: 8, databases: {"A":5,"B":5,"C":5,"D":5,"E":5}

2) A rebooted, forgot its counter, floods seq 1
  A->B seq 1: STALE (have 5) -> discard, send seq 5 back to A
  A->C seq 1: STALE (have 5) -> discard, send seq 5 back to A
  B->A seq 5: my own LSA is newer than mine -> must re-originate with seq 6
  C->A seq 5: my own LSA is newer than mine -> must re-originate with seq 6
  messages: 4, databases: {"A":1,"B":5,"C":5,"D":5,"E":5}

3) A jumps to seq 6 and floods again
  A->B seq 6: ACCEPT (had 5), ack A, forward to C,D
  A->C seq 6: ACCEPT (had 5), ack A, forward to B,E
  B->C seq 6: duplicate -> discard, ack only
  B->D seq 6: ACCEPT (had 5), ack B, forward to E
  C->B seq 6: duplicate -> discard, ack only
  C->E seq 6: ACCEPT (had 5), ack C, forward to D
  D->E seq 6: duplicate -> discard, ack only
  E->D seq 6: duplicate -> discard, ack only
  messages: 8, databases: {"A":6,"B":6,"C":6,"D":6,"E":6}

৩ · Dijkstra — প্রতিটি router-এ একই হিসাব

Flooding শেষে সবার LSDB এক। এবার প্রতিটি router নিজেকে উৎস ধরে Dijkstra-র algorithm চালায় — ওলন্দাজ কম্পিউটার বিজ্ঞানী Edsger W. Dijkstra ১৯৫৬ সালে এটি ভাবেন আর ১৯৫৯ সালে প্রকাশ করেন। Routing-এর জগতে একে প্রায়ই SPF (Shortest Path First) বলা হয় — OSPF নামের “SPF” অংশ এখান থেকেই। Algorithm-টির সাধারণ রূপ, heap দিয়ে বাস্তবায়ন আর বিস্তারিত বিশ্লেষণ DSA কোর্সের Dijkstra পর্বে আছে; এখানে আমরা দেখব routing-এ এটি কীভাবে ব্যবহার হয়, আর পরীক্ষায় টেবিলটি কীভাবে লিখতে হয়।

চিহ্নগুলো

• c(x,y): x আর y-এর মাঝের link-এর cost; সরাসরি link না থাকলে ∞.
• D(v): এখন পর্যন্ত জানা উৎস থেকে v-এর সবচেয়ে কম cost.
• p(v): সেই পথে v-এর ঠিক আগের node (predecessor).
• N′: যেসব node-এর সবচেয়ে ছোট পথ নিশ্চিতভাবে জানা হয়ে গেছে।

প্রাথমিক অবস্থা:
  N' = {u}
  প্রতিটি node v-এর জন্য:
    v যদি u-র প্রতিবেশী হয়:  D(v) = c(u,v),  p(v) = u
    নইলে:                    D(v) = ∞
লুপ:
  N'-এর বাইরে যে w-এর D(w) সবচেয়ে ছোট, তাকে বাছাই
  w-কে N'-এ যোগ
  w-এর প্রতিটি প্রতিবেশী v, যা N'-এ নেই:
    D(w) + c(w,v) < D(v) হলে:  D(v) = D(w) + c(w,v),  p(v) = w
সব node N'-এ না আসা পর্যন্ত লুপ চলবে

দুটি নিয়ম আমরা আগে থেকে ঠিক করে রাখি, কারণ পরীক্ষায় এ নিয়ে দ্বিধা হয়: (১) দুটি node-এর D সমান হলে বর্ণক্রমে আগেরটি আগে বাছাই হবে; (২) নতুন পথের cost পুরোনোটির সমান হলে p(v) বদলাবে না — শুধু কঠোরভাবে ছোট হলে বদলায়। (কোনো বই অন্য নিয়ম নেয়; চূড়ান্ত cost একই থাকে। পরীক্ষায় নিজের নিয়মটি লিখে দেওয়া নিরাপদ।)

পরীক্ষার খাতায় একই হিসাব একটি টেবিলে লেখা হয় — প্রতি সারি একটি ধাপ, আর যে node N′-এ ঢুকে গেছে তার ঘর পরের সারি থেকে ফাঁকা। নিচের simulator হুবহু সেই টেবিল ছাপে, তারপর forwarding table. Graph বদলে (যেমন একটি link-এর cost) নিজের অনুশীলনের উত্তর মেলাতে পারবেন।

// Link-state database (identical in every router): 6 routers, 10 links, cost on each link.
const links = [["u","v",2],["u","x",1],["u","w",5],["v","x",2],["v","w",3],
               ["x","w",3],["x","y",1],["w","y",1],["w","z",5],["y","z",2]];
const nodes = ["u","v","w","x","y","z"], src = "u";
const cost = {};                       // cost[a][b] = link cost (both directions)
for (const n of nodes) cost[n] = {};
for (const [a, b, c] of links) { cost[a][b] = c; cost[b][a] = c; }
const D = {}, p = {}, Np = [src];      // D = distance, p = predecessor, Np = N'
for (const v of nodes) if (v !== src) { D[v] = cost[src][v] ?? Infinity; p[v] = src; }
const others = nodes.filter(v => v !== src);
const cell = v => Np.includes(v) ? "" : D[v] === Infinity ? "inf" : D[v] + "," + p[v];
const row = s => console.log(String(s).padEnd(5) + Np.join("").padEnd(8) +
  others.map(v => cell(v).padEnd(10)).join(""));
console.log("step N'      " + others.map(v => `D(${v}),p(${v})`.padEnd(10)).join(""));
row(0);
for (let step = 1; step < nodes.length; step++) {
  // pick w not in N' with the smallest D (tie -> alphabetical order)
  const w = others.filter(v => !Np.includes(v))
                  .sort((a, b) => D[a] - D[b] || a.localeCompare(b))[0];
  Np.push(w);
  for (const v in cost[w])             // relax every neighbour of w not yet in N'
    if (!Np.includes(v) && D[w] + cost[w][v] < D[v]) { D[v] = D[w] + cost[w][v]; p[v] = w; }
  row(step);
}
console.log("\nForwarding table of " + src + "\ndest  cost  path      next hop (link)");
for (const v of others) {
  const path = [v];
  while (path[0] !== src) path.unshift(p[path[0]]);
  console.log(`${v}     ${D[v]}     ${path.join("-").padEnd(9)} (${src},${path[1]})`);
}

step N'      D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0    u       2,u       5,u       1,u       inf       inf
1    ux      2,u       4,x                 2,x       inf
2    uxv               4,x                 2,x       inf
3    uxvy              3,y                           4,y
4    uxvyw                                           4,y
5    uxvywz

Forwarding table of u
dest  cost  path      next hop (link)
v     2     u-v       (u,v)
w     3     u-x-y-w   (u,x)
x     1     u-x       (u,x)
y     2     u-x-y     (u,x)
z     4     u-x-y-z   (u,x)

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

দাবি: কোনো node w যখন N′-এ যোগ হয়, তখন D(w) সত্যিই u থেকে w-এর সবচেয়ে ছোট cost. প্রমাণের ধারণা (বিপরীত ধরে নিয়ে):

1. ধরুন w-ই প্রথম node যার ক্ষেত্রে দাবিটি মিথ্যা — অর্থাৎ u থেকে w-এ একটি পথ P আছে যার cost D(w)-এর চেয়ে কম।
2. P শুরু হয় u-তে (N′-এর ভেতরে) আর শেষ হয় w-তে (তখনো বাইরে)। তাই পথে প্রথমবার N′ ছেড়ে বাইরে যাওয়ার একটি link আছে: a থেকে b, যেখানে a ∈ N′ আর b ∉ N′.
3. a আগেই N′-এ যোগ হয়েছে, সঠিক D(a) নিয়ে (w-ই প্রথম ভুল)। a যোগ হওয়ার সময় তার প্রতিবেশী b হালনাগাদ হয়েছিল, তাই D(b) ≤ D(a) + c(a,b) = P-এর u থেকে b পর্যন্ত অংশের cost.
4. সব cost অঋণাত্মক, তাই P-এর বাকি অংশ (b থেকে w) cost কমাতে পারে না: P-এর u থেকে b অংশ ≤ P-এর পুরো cost < D(w).
5. অর্থাৎ D(b) < D(w), অথচ algorithm বাইরের node-গুলোর মধ্যে সবচেয়ে ছোট D হিসেবে w-কে বেছেছে — বিরোধ। তাই দাবি সত্য। ∎

ধাপ ৪-এ “cost অঋণাত্মক” শর্তটি অপরিহার্য। ঋণাত্মক cost থাকলে Dijkstra ভুল উত্তর দিতে পারে — সেখানে লাগে Bellman-Ford (DSA কোর্সের Bellman-Ford পর্ব)। Routing-এ link cost সবসময় ধনাত্মক, তাই সমস্যা নেই।

৪ · খরচের হিসাব আর একটি বিপদ — জটিলতা ও oscillation

Dijkstra-র সময়

n টি node-এর নেটওয়ার্কে (উৎস বাদে n টি অন্য node ধরে) সাধারণ array দিয়ে বাস্তবায়নে প্রথম ধাপে n টি node দেখে সবচেয়ে ছোটটি খুঁজতে হয়, পরের ধাপে n − ১টি, এভাবে শেষ পর্যন্ত। মোট তুলনা n + (n − ১) + … + ১ = n(n + ১) ÷ ২ — অর্থাৎ O(n²). সবচেয়ে ছোট D খোঁজার কাজটি binary heap (priority queue) দিয়ে করলে প্রতিটি node তোলা আর প্রতিটি link-এর হালনাগাদ O(log V) সময় নেয়, তাই মোট O((E + V) log V), যেখানে V = node, E = link. Router-এর নেটওয়ার্কে প্রতিটি router-এর প্রতিবেশী অল্প (E অনেক ছোট V²-এর তুলনায়), তাই heap-এর রূপটি বাস্তবে দ্রুত।

Flooding-এর বার্তা

অংশ ২-এ দেখেছেন, একটি LSA-র flooding-এ E থেকে 2E বার্তা। প্রতিটি router একটি করে LSA ছাড়লে মোট O(V × E) বার্তা। হাজার হাজার router-এর একটি সমতল নেটওয়ার্কে প্রতিটি link-এর ওঠানামায় সবার কাছে flooding আর সবার Dijkstra চালানো বোঝা হয়ে দাঁড়ায়। এ কারণেই OSPF-এ area (অংশ ৭)।

Oscillation — যখন cost = বর্তমান ভিড়

ধরুন link cost ঠিক হয় বর্তমান ভিড় দেখে — যত বেশি traffic, তত বেশি cost. শুনতে বুদ্ধিমানের মতো: ভিড়ের রাস্তা এড়িয়ে চলা। কিন্তু একটি সরল উদাহরণ ভাবুন: একটি গন্তব্যে যাওয়ার দুটি পথ — ঘড়ির কাঁটার দিকে আর উল্টো দিকে। শুরুতে দুটিই ফাঁকা; সবাই একটি বেছে নিল (ধরুন ঘড়ির দিকে)। এখন সেই পথে সব traffic, তাই তার cost বেড়ে গেল। পরের হিসাবে সবাই একসাথে দেখল উল্টো দিক সস্তা — সবাই সেদিকে চলে গেল। তারপর সেটি ভারী, আবার সবাই ফিরে এল… পথ দোলনার মতো দুলতেই থাকে, আর প্রতিবার পথ বদলের সময় packet হারায় বা আগে-পরে পৌঁছায়।

সমাধানের দুটি পথ: (১) cost-কে ভিড়ের ওপর নির্ভর না করানো — OSPF আর IS-IS-এ cost স্থির, প্রশাসকের বসানো; (২) সব router যেন একসাথে হিসাব না করে, তাই LSA পাঠানো আর হিসাবের সময়ে এলোমেলো বিরতি। ইতিহাসে ARPANET-এর delay-নির্ভর metric-এ এমন অস্থিরতা দেখা গিয়েছিল, আর ১৯৮০-এর দশকের শেষে metric সংশোধন করে ওঠানামার সীমা বেঁধে দেওয়া হয়। ভিড় বুঝে traffic সরানোর কাজ আজ সাধারণত আলাদা ব্যবস্থায় হয় — MPLS traffic engineering বা SDN controller (পর্ব ৫৩)।

৫ · OSPF — বাস্তবের link state protocol

OSPF (Open Shortest Path First) একটি প্রতিষ্ঠানের ভেতরের নেটওয়ার্কে (একটি autonomous system-এর ভেতরে) সবচেয়ে বেশি ব্যবহৃত link state protocol — অর্থাৎ একটি IGP (পর্ব ২২)। প্রতিষ্ঠানের বাইরে, এক ISP থেকে আরেক ISP-তে, চলে BGP (পর্ব ২৫)। “Open” মানে খোলা মান — কোনো এক কোম্পানির মালিকানা নয়।

TCP বা UDP-তে না চলায় OSPF নিজেই নিজের নির্ভরযোগ্যতা সামলায় — অংশ ২-এর ack আর retransmission. বার্তা যায় multicast ঠিকানায়, আর IP header-এর TTL সাধারণত ১ — অর্থাৎ শুধু একই link-এর প্রতিবেশীর জন্য, router পেরিয়ে যায় না। OSPF-এর পাঁচ ধরনের packet:

Hello আর dead timer

প্রতিটি OSPF interface নিয়মিত hello পাঠায়। Ethernet-এর মতো broadcast নেটওয়ার্ক আর point-to-point link-এ সাধারণ ডিফল্ট: hello interval ১০ সেকেন্ড, dead interval ৪০ সেকেন্ড (hello-র চার গুণ) — RFC 2328-এর নমুনা মান আর বেশিরভাগ vendor-এর ডিফল্ট; কিছু পুরোনো ধরনের নেটওয়ার্কে (যেমন NBMA) ৩০ আর ১২০. ৪০ সেকেন্ড কোনো hello না এলে প্রতিবেশীকে মৃত ধরা হয়। দুই প্রতিবেশীর মধ্যে hello আর dead interval, area নম্বর, subnet mask (broadcast নেটওয়ার্কে), authentication আর কয়েকটি option মিলতে হয় — না মিললে তারা কখনো প্রতিবেশী হয় না। বাস্তবের ভুলের বড় অংশ এখানেই।

Neighbour state — Down থেকে Full

দুটি OSPF router পরিচিত হয়ে database মেলানো পর্যন্ত কয়েকটি অবস্থা পার হয়। Troubleshooting-এ “কোন state-এ আটকে আছে” দেখেই সমস্যা অনেকটা বোঝা যায়:

Cisco-ধাঁচের router-এ show ip ospf neighbor এই state দেখায়। একটি LAN-এর R1-এর দৃষ্টিতে (উদাহরণ আউটপুট, কাল্পনিক নেটওয়ার্ক):

R1# show ip ospf neighbor          ← উদাহরণ, Cisco IOS-ধাঁচ

Neighbor ID     Pri   State           Dead Time   Address         Interface
3.3.3.3         100   FULL/DR         00:00:36    10.0.0.3        GigabitEthernet0/0
10.0.0.5          1   FULL/BDR        00:00:33    10.0.0.5        GigabitEthernet0/0
2.2.2.2           1   2WAY/DROTHER    00:00:38    10.0.0.2        GigabitEthernet0/0
9.9.9.9           0   2WAY/DROTHER    00:00:31    10.0.0.4        GigabitEthernet0/0

R1 নিজে একটি DROther: DR (3.3.3.3) আর BDR (10.0.0.5)-এর সাথে FULL, অন্য দুই DROther-এর সাথে 2WAY. “Dead Time” ৪০ থেকে উল্টো গোনে, প্রতিটি hello এলে আবার ৪০ হয়। Linux-এ একই কাজ করে FRRouting-এর ospfd (কমান্ড vtysh -c "show ip ospf neighbor") বা BIRD — আউটপুটের ধরন একটু আলাদা।

৬ · DR/BDR নির্বাচন আর cost-এর হিসাব

LAN-এ DR কেন লাগে

একটি Ethernet switch-এ ৫টি OSPF router যুক্ত — সবাই সবার প্রতিবেশী। প্রত্যেকে প্রত্যেকের সাথে পূর্ণ adjacency করলে জোড়া হয় n(n − ১) ÷ ২ = ৫ × ৪ ÷ ২ = ১০টি; প্রতিটি নতুন LSA এই সব জোড়া দিয়ে বারবার flood হয়, আর প্রতিটি router LSDB-তে LAN-টিকে ১০টি আলাদা link হিসেবে দেখে। ২০টি router হলে ১৯০টি জোড়া। সমাধান: LAN-এর জন্য একজন প্রতিনিধি — Designated Router (DR), আর DR নষ্ট হলে সাথে সাথে দায়িত্ব নিতে একজন Backup DR (BDR). বাকিরা (DROther) পূর্ণ adjacency করে শুধু DR আর BDR-এর সাথে: প্রতিটি DROther-এর ২টি, আর DR–BDR নিজেদের ১টি — মোট (n − ২) × ২ + ১ = 2n − 3, অর্থাৎ মোটামুটি 2n. DR LAN-টির পক্ষে একটি Network LSA (type 2, অংশ ৭) বানায়, যাতে graph-এ LAN-টি একটি “ছদ্ম node” হয়ে যায়।

Flooding-ও বদলায়: DROther নতুন LSA পাঠায় 224.0.0.6-এ (শুধু DR আর BDR শোনে), আর DR তা পুরো LAN-এ 224.0.0.5-এ ছড়িয়ে দেয়। Point-to-point link-এ (দুটি router, মাঝে আর কেউ নেই) DR/BDR নির্বাচন হয় না — প্রয়োজনই নেই।

নির্বাচনের নিয়ম

1. প্রতিটি interface-এর একটি OSPF priority (০–২৫৫, ডিফল্ট ১)। Priority ০ মানে এই router কখনো DR বা BDR হবে না।
2. সবচেয়ে বড় priority জেতে; সমান হলে সবচেয়ে বড় router ID (৩২ bit সংখ্যা, IPv4 ঠিকানার মতো করে লেখা — সংখ্যা হিসেবে তুলনা হয়, লেখা হিসেবে নয়)।
3. নির্বাচন non-preemptive: একবার DR/BDR ঠিক হয়ে গেলে পরে বেশি priority-র router যোগ হলেও সে দখল নেয় না। DR নষ্ট হলে BDR DR হয়, আর নতুন BDR নির্বাচন হয়।

একটি LAN 10.0.0.0/24: R1 (priority ১, ID 1.1.1.1), R2 (১, 2.2.2.2), R3 (১০০, 3.3.3.3), R4 (০, 9.9.9.9), R5 (১, 10.0.0.5). পরে যোগ হবে R6 (২০০, 6.6.6.6).

Cost = reference bandwidth ÷ interface bandwidth

RFC 2328 শুধু বলে প্রতিটি interface-এর একটি cost থাকবে (১ থেকে ৬৫,৫৩৫); কীভাবে ঠিক হবে, তা বাস্তবায়নের ব্যাপার। প্রচলিত নিয়ম (Cisco-সহ অনেক vendor-এর ডিফল্ট):

অনেক vendor-এর ডিফল্ট reference bandwidth ১০০ Mbps — যখন এই নিয়ম চালু হয়, তখন ১০০ Mbps-ই ছিল দ্রুত link. আজ সমস্যা: ১০০ Mbps, ১ Gbps, ১০ Gbps, ১০০ Gbps — সবার cost ১! OSPF তখন একটি ১০০ Mbps link আর একটি ১০০ Gbps link-কে সমান ভাবে। তাই একটি নেটওয়ার্কের সব router-এ একই, বড় reference বসানো উচিত (যেমন ১০০ Gbps). নিচের calculator তা দেখায়, সাথে অংশ ৬-এর DR/BDR নির্বাচন আর adjacency-র হিসাব:

// (1) OSPF interface cost = reference bandwidth / interface bandwidth (integer, at least 1)
const ospfCost = (refMbps, bwMbps) => Math.max(1, Math.floor(refMbps / bwMbps));
const ifaces = [["T1 1.544M", 1.544], ["10M", 10], ["100M", 100], ["1G", 1000],
                ["10G", 10000], ["40G", 40000], ["100G", 100000]];
console.log("interface   ref=100M   ref=100G");
for (const [name, bw] of ifaces)
  console.log(name.padEnd(12) + String(ospfCost(100, bw)).padEnd(11) + ospfCost(100000, bw));

// (2) DR/BDR election on one Ethernet segment
const lan = [{ r: "R1", pri: 1, rid: "1.1.1.1" }, { r: "R2", pri: 1, rid: "2.2.2.2" },
             { r: "R3", pri: 100, rid: "3.3.3.3" }, { r: "R4", pri: 0, rid: "9.9.9.9" },
             { r: "R5", pri: 1, rid: "10.0.0.5" }];
const ridNum = s => s.split(".").reduce((a, o) => a * 256 + Number(o), 0); // compare as numbers
const ranked = lan.filter(x => x.pri > 0)            // priority 0 = never DR or BDR
  .sort((a, b) => b.pri - a.pri || ridNum(b.rid) - ridNum(a.rid));
console.log("\nrank  router  priority  router-id");
ranked.forEach((x, i) => console.log(`${i + 1}     ${x.r}      ${String(x.pri).padEnd(9)} ${x.rid}`));
console.log(`DR = ${ranked[0].r}, BDR = ${ranked[1].r}, ineligible: ` +
  lan.filter(x => x.pri === 0).map(x => x.r).join(","));
console.log(`string compare would say "2.2.2.2" > "10.0.0.5": ${"2.2.2.2" > "10.0.0.5"}`);

// (3) adjacencies on a LAN of n routers: full mesh vs. with DR + BDR
console.log("\n  n   full mesh n(n-1)/2   with DR/BDR 2n-3");
for (const n of [5, 10, 20, 50])
  console.log(String(n).padStart(3) + String(n * (n - 1) / 2).padStart(21) + String(2 * n - 3).padStart(19));

interface   ref=100M   ref=100G
T1 1.544M   64         64766
10M         10         10000
100M        1          1000
1G          1          100
10G         1          10
40G         1          2
100G        1          1

rank  router  priority  router-id
1     R3      100       3.3.3.3
2     R5      1         10.0.0.5
3     R2      1         2.2.2.2
4     R1      1         1.1.1.1
DR = R3, BDR = R5, ineligible: R4
string compare would say "2.2.2.2" > "10.0.0.5": true

  n   full mesh n(n-1)/2   with DR/BDR 2n-3
  5                   10                  7
 10                   45                 17
 20                  190                 37
 50                 1225                 97

বাস্তবে একটি Cisco IOS-ধাঁচের কনফিগারেশন দেখতে মোটামুটি এমন (উদাহরণ; vendor আর software-এর সংস্করণভেদে কমান্ড আলাদা):

! উদাহরণ — Cisco IOS-ধাঁচ
router ospf 1
 router-id 3.3.3.3
 auto-cost reference-bandwidth 100000      ! Mbps-এ, অর্থাৎ 100 Gbps
 passive-interface GigabitEthernet0/2      ! ব্যবহারকারীদের LAN: hello পাঠাবে না
 network 10.0.0.0 0.0.0.255 area 0
 network 192.168.20.0 0.0.0.255 area 0
!
interface GigabitEthernet0/0
 ip ospf priority 100
 ip ospf cost 10                           ! চাইলে হাতে cost বসানো যায়

passive-interface-এর মানে: ওই interface-এর নেটওয়ার্কটি OSPF-এ ঘোষণা হবে, কিন্তু সেখানে hello যাবে না, তাই কোনো প্রতিবেশী তৈরি হবে না। ব্যবহারকারীদের LAN-এ এটি নিরাপত্তার জন্য জরুরি (অংশ ৭)। হাতে বসানো ip ospf cost সূত্রের হিসাবকে ছাপিয়ে যায়।

৭ · বড় নেটওয়ার্কে OSPF — area, ABR, ASBR, LSA type আর নিরাপত্তা

অংশ ৪-এর সমস্যা মনে করুন: একটি সমতল নেটওয়ার্কে প্রতিটি link-এর ওঠানামা সবার কাছে flood হয়, সবাই Dijkstra চালায়, সবার LSDB পুরো নেটওয়ার্কের সমান বড়। OSPF-এর সমাধান দুই স্তরের hierarchical routing: নেটওয়ার্ককে কয়েকটি area-তে ভাগ।

              ┌─────────── Area 0 (backbone) ───────────┐
              │   R-core1 ─────────────── R-core2       │
              └─────┬──────────────────────────┬────────┘
                    │                          │
               ┌────┴────┐                ┌────┴────┐
               │  ABR-1  │                │  ABR-2  │        ASBR ── ISP
               └────┬────┘                └────┬────┘   (বাইরের route আনে)
         ┌──────────┴─────────┐     ┌──────────┴─────────┐
         │ Area 1 (ঢাকা অফিস) │     │ Area 2 (চট্টগ্রাম) │
         │  R11  R12  R13 …   │     │  R21  R22 …        │
         └────────────────────┘     └────────────────────┘

• Backbone area (area 0): কেন্দ্র। প্রতিটি অন্য area-কে area 0-এর সাথে যুক্ত থাকতে হয়; এক area থেকে আরেক area-র traffic area 0 হয়ে যায়। (ব্যতিক্রমী জোড়াতালি “virtual link” আছে, তবে তা নকশার দুর্বলতার লক্ষণ।)
• ABR (Area Border Router): যার interface area 0 আর অন্য কোনো area — দুটোতেই। প্রতিটি area-র আলাদা LSDB রাখে, আর এক area-র prefix-গুলো সারসংক্ষেপ করে অন্য area-তে জানায়।
• ASBR (AS Boundary Router): যে router OSPF-এর বাইরের route (static route, ISP-র default route, BGP থেকে শেখা route) OSPF-এ ঢোকায় — একে বলে redistribution.

LSA-র প্রধান ধরন

আরও কয়েকটি ধরন (যেমন type 7) এই পর্বের পরিসরের বাইরে। মূল কথা: area-র ভেতরে link state (type 1, 2 দিয়ে পুরো topology), কিন্তু area-র বাইরে শুধু “এই prefix, এত cost” (type 3) — যা অনেকটা distance vector-এর মতো আচরণ। এই কারণেই area 0-কে কেন্দ্র রাখার কঠোর নিয়ম: সব area-র সারসংক্ষেপ একটি কেন্দ্র দিয়ে গেলে distance vector-ধাঁচের loop তৈরি হতে পারে না।

ABR-এ route summarisation

Area 1-এ যদি 10.1.0.0/24, 10.1.1.0/24, 10.1.2.0/24, 10.1.3.0/24 — চারটি নেটওয়ার্ক থাকে, ABR-1 area 0-তে চারটি type 3 LSA না পাঠিয়ে একটি পাঠাতে পারে: 10.1.0.0/22 (পর্ব ১৭-এর route summarisation). লাভ দুটি: অন্য area-র টেবিল ছোট হয়, আর area 1-এর ভেতরে একটি /24 ওঠানামা করলেও বাইরের কেউ টের পায় না — সারসংক্ষেপ একই থাকে, তাই অন্য area-তে নতুন flooding বা হিসাব লাগে না। দাম: বাইরের router সবসময় সবচেয়ে ভালো পথ জানে না, আর ঠিকানা আগে থেকেই পরিকল্পিতভাবে ভাগ করতে হয়।

Authentication — ভুয়া প্রতিবেশী ঠেকানো

OSPF router সাধারণত যে কারও hello বিশ্বাস করে। কেউ নেটওয়ার্কে একটি যন্ত্র বসিয়ে OSPF চালালে ভুয়া LSA দিয়ে traffic নিজের দিকে টেনে নিতে বা নেটওয়ার্ক অচল করতে পারত। প্রতিরক্ষা:

• Authentication: OSPFv2-এ শুরু থেকে তিন ধরন — কোনোটি নয়, সাধারণ পাসওয়ার্ড (তারে খোলা অবস্থায় যায়, তাই প্রায় অর্থহীন), আর MD5-ভিত্তিক cryptographic যাচাই। পরে RFC 5709 HMAC-SHA যোগ করে, যা আজ পছন্দের। OSPFv3 প্রথমে IPsec-এর ওপর নির্ভর করত; পরে RFC 7166 নিজস্ব authentication trailer যোগ করে। সব প্রতিবেশীতে একই চাবি আর পদ্ধতি লাগে।
• Passive interface: ব্যবহারকারী বা সার্ভারের LAN-এ OSPF-এর hello বন্ধ (অংশ ৬)।

৮ · IS-IS, distance vector-এর সাথে তুলনা আর SDN

IS-IS — বড় ISP-র প্রিয় আরেকটি link state protocol

IS-IS (Intermediate System to Intermediate System) মূলত DEC কোম্পানির DECnet Phase V-এর জন্য নকশা করা, পরে ISO-র মান (ISO/IEC 10589). ১৯৯০ সালে RFC 1195 (“Integrated IS-IS”) একে IP route বহনের উপযোগী করে। মূল ধারণা OSPF-এর মতোই — LSP (OSPF-এর LSA-র সমতুল্য), flooding, Dijkstra. পার্থক্যগুলো:

• IP-র ওপর চলে না: IS-IS-এর বার্তা সরাসরি data link স্তরে (Ethernet frame-এ) যায়, IP packet হিসেবে নয়। তাই IP-র ঠিকানা-ব্যবস্থার গোলমাল IS-IS-এর নিজের যোগাযোগে প্রভাব ফেলে না, আর IP দিয়ে দূর থেকে একে আক্রমণ করাও কঠিন।
• Area-র বদলে level: Level 1 (area-র ভেতরে) আর Level 2 (area-গুলোর মাঝের backbone).
• সহজে বাড়ানো যায়: বার্তার তথ্য TLV (type-length-value) আকারে; নতুন ধরনের তথ্য (যেমন IPv6, RFC 5308) নতুন TLV যোগ করেই বহন করা যায়, protocol-এর নতুন সংস্করণ লাগে না।

এসব কারণে অনেক বড় ISP-র backbone-এ IS-IS ব্যবহারের চল আছে, আর প্রতিষ্ঠানের (enterprise) নেটওয়ার্কে OSPF বেশি দেখা যায় — যদিও এটি একটি সাধারণ প্রবণতা, কোনো নিয়ম নয়।

Link state বনাম distance vector

Count-to-infinity আর Bellman-Ford-এর বিস্তারিত পর্ব ২৩-এ (distance vector) — এখানে আর পুনরাবৃত্তি করছি না। Link state-এও পরিবর্তনের মুহূর্তে অল্প সময়ের loop (microloop) হতে পারে, কিন্তু flooding শেষ হলেই তা মিলিয়ে যায় (ভাবনার প্রশ্ন ২)।

SDN — কেন্দ্রীয় হিসাব, link state-এর আত্মীয়

Link state-এ প্রতিটি router একই হিসাব আলাদাভাবে করে। পুরো topology এক জায়গায় জমা করে একটি কেন্দ্রেই হিসাব করে সবাইকে টেবিল পাঠালে? এটিই SDN-এর কেন্দ্রীয় control plane-এর ধারণা (পর্ব ১৫-এ পরিচয়, বিস্তারিত পর্ব ৫৩)। পার্থক্য শুধু কোথায় হিসাব হয় — প্রতিটি যন্ত্রে নাকি এক কেন্দ্রে (ভাবনার প্রশ্ন ৫)।

৯ · AI-এর যুগে link state আর OSPF

AI দ্রুত OSPF কনফিগারেশন লেখে বা Dijkstra-র টেবিল বানায়, কিন্তু কিছু ভুল প্রায়ই করে, যা দেখতে নির্ভুল:

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

• Dijkstra-র প্রতিটি সারি হাতে বা simulator দিয়ে মিলিয়েছি, শুধু শেষ উত্তর নয়
• Timer, cost-এর সূত্র আর DR-এর নিয়মে কোনটি RFC-র আর কোনটি vendor-এর ডিফল্ট, আলাদা করেছি
• RFC নম্বরগুলো rfc-editor.org-এ খুলে শিরোনাম মিলিয়েছি
• কনফিগারেশন আগে ল্যাবে বা VM-এ (যেমন FRRouting দিয়ে) চালিয়ে neighbour state আর route দেখেছি
• Passive interface আর authentication আছে কি না দেখেছি, আর শুধু নিজের বা অনুমতিপ্রাপ্ত নেটওয়ার্কে পরীক্ষা করেছি