Routing-এর ভিত্তি — routing table, static route আর longest prefix match

১ · Routing একটি graph-এর সমস্যা — সবচেয়ে কম খরচের পথ

পর্ব ১৫-এ দেখেছেন, router-এর দুটি কাজ: forwarding (প্রতিটি packet-কে টেবিল দেখে সঠিক port-এ পাঠানো, data plane) আর routing (সেই টেবিল বানানো, control plane). এই মডিউলের পাঁচটি পর্ব দ্বিতীয় কাজটি নিয়ে। শুরু করি সবচেয়ে মৌলিক প্রশ্ন দিয়ে: “সবচেয়ে ভালো পথ” মানে আসলে কী?

আনুষ্ঠানিক ভাষায়, নেটওয়ার্ক একটি graph G = (N, E): N হলো router-এর সেট (node), E হলো link-এর সেট (edge). প্রতিটি link (x, y)-এর একটি cost c(x, y) — এটি হতে পারে delay, link-এর গতির উল্টো (ধীর link মানে বেশি cost), টাকার খরচ, অথবা সরল hop গোনা (প্রতিটি link-এর cost ১)। একটি পথের cost তার সব link-এর cost-এর যোগফল, আর routing-এর লক্ষ্য প্রতিটি উৎস-গন্তব্য জোড়ার least-cost path খোঁজা। Graph-এর ভিত্তি DSA কোর্সের Graph পর্বে, আর সবচেয়ে কম খরচের পথের algorithm Dijkstra ও Bellman-Ford পর্বে।

A ──────2────── B ──────4────── D
 ╲              │             ╱ │
  ╲ 5           │ 1       1 ╱   │ 3
   ╲            │         ╱     │
    ╲────────── C ──────╱       │
                └───────6────── E
link-এর cost: A–B 2, A–C 5, B–C 1, B–D 4, C–D 1, D–E 3, C–E 6

A থেকে E-তে যাওয়ার কয়েকটি পথ আর তাদের মোট cost:

লক্ষ করুন, “সবচেয়ে ভালো” নির্ভর করে কোন মাপকাঠি ধরছেন তার ওপর। Cost ধরলে জেতে চার hop-এর পথ (৭), hop গুনলে জেতে দুই hop-এর পথ (A → C → E). RIP-এর মতো পুরোনো protocol শুধু hop গোনে (পর্ব ২৩), OSPF সাধারণত link-এর গতি থেকে cost বানায় (পর্ব ২৪)। তাই একই নেটওয়ার্কে দুই protocol দুই পথ বাছতে পারে — অংশ ৪-এ দেখবেন এর ফল কী।

Optimality principle — কেন শুধু next hop রাখলেই চলে

A-র সবচেয়ে কম খরচের পথ A → B → C → D → E. এর যেকোনো অংশ, যেমন B → C → D, নিজেও B থেকে D-র সবচেয়ে কম খরচের পথ। প্রমাণ সহজ (“কেটে বসানো” যুক্তি): ধরুন B থেকে D-তে আরও সস্তা কোনো পথ Q আছে। তাহলে পুরো পথের B → C → D অংশ কেটে Q বসালে A থেকে E-র এমন একটি পথ পাওয়া যায় যার cost ৭-এর চেয়ে কম — কিন্তু ৭ তো সবচেয়ে কম ছিল। এই অসংগতি দেখায়, এমন Q থাকতে পারে না। (Q যদি মূল পথের কোনো node আবার ছুঁয়ে যায়, সেই চক্র বাদ দিলে cost আরও কমে বা সমান থাকে, কারণ cost ঋণাত্মক নয়।) একে বলে optimality principle (Bellman-এর নীতি)।

এর ফল গভীর: একটি গন্তব্যের দিকে সব router-এর সবচেয়ে কম খরচের পথ মিলে একটি গাছ (tree) তৈরি করে, যার শিকড় গন্তব্যে। তাই প্রতিটি router-কে পুরো পথ মনে রাখতে হয় না — শুধু “এই গন্তব্যের জন্য পরের hop কে”. A-র টেবিলে B, C, D, E — চারটি গন্তব্যেরই next hop B. A packet-কে B-র হাতে দেয়, B নিজের টেবিল দেখে C-কে দেয়, আর এভাবে hop-by-hop পুরো পথ তৈরি হয়। শর্ত একটাই: সব router-এর টেবিল যেন একই ছবি থেকে বানানো হয় — নইলে loop (অংশ ৭)।

২ · Routing table-এর একটি সারি — prefix, next hop, interface, metric আর উৎস

পর্ব ১৫-এ দেখেছেন, router-এর ভেতরে দুটি টেবিল: routing protocol-গুলো যা শেখে তা জমে RIB-এ, আর সেখান থেকে সেরাগুলো দ্রুত খোঁজার আকারে যায় FIB-এ (forwarding table). প্রচলিত ভাষায় দুটিকেই routing table বলা হয়। একটি সারিতে সাধারণত এই ঘরগুলো থাকে:

Route কোথা থেকে আসে — পাঁচ রকম

বাসার কম্পিউটারের default gateway (পর্ব ০৬) আসলে একটি default route-এর next hop. Cisco-র ভাষায় এর নাম gateway of last resort — “শেষ ভরসার দরজা”. যে router-এর default route নেই, সে অজানা গন্তব্যের packet ফেলে দিয়ে উৎসকে ICMP “Destination Unreachable” পাঠায় (পর্ব ২০)। ইন্টারনেটের কেন্দ্রের বড় router-এ ইচ্ছা করেই default থাকে না, টেবিলে থাকে পৃথিবীর সব prefix — এই এলাকার নাম “default-free zone”.

৩ · টেবিল পড়া — Cisco, Linux আর Windows

তিনটি জগতের টেবিল দেখতে আলাদা, কিন্তু ঘরগুলো একই। প্রথমে একটি Cisco IOS-ধাঁচের router-এর টেবিল (অন্য vendor-এর ধরন আলাদা)। এই router-কে পুরো পর্বে R1 বলব:

R1# show ip route
Codes: L - local, C - connected, S - static, R - RIP, O - OSPF, B - BGP
       * - candidate default
Gateway of last resort is 203.0.113.1 to network 0.0.0.0

S*    0.0.0.0/0 [1/0] via 203.0.113.1
      10.0.0.0/8 is variably subnetted, 5 subnets, 3 masks
C        10.0.1.0/24 is directly connected, GigabitEthernet0/1
L        10.0.1.1/32 is directly connected, GigabitEthernet0/1
S        10.20.0.0/16 [1/0] via 10.0.1.2
O        10.20.30.0/24 [110/30] via 10.0.1.3, 00:12:41, GigabitEthernet0/1
O        10.20.40.0/24 [110/20] via 10.0.1.3, 00:12:41, GigabitEthernet0/1
                       [110/20] via 10.0.1.5, 00:12:41, GigabitEthernet0/1
      203.0.113.0/24 is variably subnetted, 2 subnets, 2 masks
C        203.0.113.0/30 is directly connected, GigabitEthernet0/0
L        203.0.113.2/32 is directly connected, GigabitEthernet0/0

• প্রথম অক্ষর উৎস: C connected, L local, S static, O OSPF. * মানে default-এর প্রার্থী।
• [110/30] = [AD/metric]. OSPF-এর AD ১১০, এই পথের OSPF cost ৩০। Static route-এ [1/0].
• 10.20.40.0/24-এর দুটি লাইন — একই prefix, একই [110/20], দুটি next hop: এটাই ECMP (অংশ ৮)।
• যা নেই: R1 হয়তো RIP থেকেও 10.20.30.0/24 শুনেছে, কিন্তু টেবিলে আছে শুধু সেরাটি (OSPF) — অংশ ৪-এর stepper.

Linux-এ একই ধরনের তথ্য অন্যভাবে লেখা। একটি সাধারণ ল্যাপটপে (Wi-Fi আর একটি VPN চালু) ip route:

$ ip route
default via 192.168.0.1 dev wlan0 proto dhcp src 192.168.0.105 metric 600
10.8.0.0/24 dev tun0 proto kernel scope link src 10.8.0.2
192.168.0.0/24 dev wlan0 proto kernel scope link src 192.168.0.105 metric 600
blackhole 10.99.0.0/16 proto static

default via 192.168.0.1 — default route, next hop বাসার router. dev হলো outgoing interface. proto বলে route-টি কে যোগ করেছে: dhcp (DHCP থেকে পাওয়া gateway, পর্ব ১৮), kernel (ঠিকানা বসানোর সময় kernel নিজে — connected route), static (প্রশাসক)। scope link মানে গন্তব্য এই link-এই; src হলো পাঠানোর সময় উৎস ঠিকানা। metric 600 — Linux kernel-এ AD নেই; একই prefix-এর কয়েকটি route থাকলে কম metric জেতে (NetworkManager সাধারণত Wi-Fi-কে ৬০০ আর তারের Ethernet-কে ১০০ দেয়)। শেষ লাইনটি একটি blackhole route — অংশ ৬-এ।

Windows-এ route print (বা PowerShell-এ Get-NetRoute) mask আলাদা ঘরে দেখায়, আর একই subnet-এর জন্য লেখে “On-link”:

PS> route print -4
IPv4 Route Table
===========================================================================
Active Routes:
Network Destination        Netmask          Gateway       Interface  Metric
          0.0.0.0          0.0.0.0      192.168.1.1    192.168.1.50     25
        127.0.0.0        255.0.0.0         On-link         127.0.0.1    331
      192.168.1.0    255.255.255.0         On-link      192.168.1.50    281
     192.168.1.50  255.255.255.255         On-link      192.168.1.50    281
    192.168.1.255  255.255.255.255         On-link      192.168.1.50    281
===========================================================================
Persistent Routes:
  None

এখানে 0.0.0.0 / 0.0.0.0 = default route, Gateway ঘরে next hop, Interface ঘরে নিজের যে ঠিকানার interface দিয়ে বের হবে (নাম নয়, ঠিকানা)। 192.168.1.50 / 255.255.255.255 হলো নিজের ঠিকানার host route. Windows-এর metric = interface metric (link-এর গতি থেকে স্বয়ংক্রিয়) + route-এর metric, তাই সংখ্যাগুলো যন্ত্রভেদে আলাদা।

এবার এই পাতার কোড-চালানোর container-এ (rootless, বাইরের নেটওয়ার্ক নেই) আসল Linux টেবিল দেখি। ip route get kernel-কে জিজ্ঞেস করে “এই ঠিকানার জন্য কোন সারি জিতবে?” — কোনো packet না পাঠিয়েই। শেষে সাধারণ ব্যবহারকারী হিসেবে একটি route যোগ করার চেষ্টা:

if command -v ip >/dev/null; then
  echo "== ip route show =="
  ip route show
  echo "== ip route show default =="
  ip route show default
  echo "== ip route get: kernel's choice for each destination =="
  for d in 10.0.2.2 10.0.2.200 192.0.2.10 198.51.100.7 127.0.0.53; do
    ip route get "$d" | head -n 1
  done
  echo "== ip -6 route show =="
  ip -6 route show 2>&1 | head -n 8
  [ -z "$(ip -6 route show 2>/dev/null)" ] && echo "(no IPv6 routes here)"
  echo "== ip -6 route get 2001:db8::1 =="
  ip -6 route get 2001:db8::1 2>&1 | head -n 1
  echo "== try to add a static route as a normal user =="
  ip route add 198.51.100.0/24 via 10.0.2.2 2>&1 || echo "(exit code $?: root/CAP_NET_ADMIN needed)"
else
  echo "ip নেই — /proc/net/route আর /proc/net/ipv6_route দেখুন"
  cat /proc/net/route
  [ -r /proc/net/ipv6_route ] && head -n 5 /proc/net/ipv6_route
fi

== ip route show ==
default via 10.0.2.2 dev tap0
10.0.2.0/24 dev tap0 proto kernel scope link src 10.0.2.100
== ip route show default ==
default via 10.0.2.2 dev tap0
== ip route get: kernel's choice for each destination ==
10.0.2.2 dev tap0 src 10.0.2.100 uid 999
10.0.2.200 dev tap0 src 10.0.2.100 uid 999
192.0.2.10 via 10.0.2.2 dev tap0 src 10.0.2.100 uid 999
198.51.100.7 via 10.0.2.2 dev tap0 src 10.0.2.100 uid 999
local 127.0.0.53 dev lo src 127.0.0.1 uid 999
== ip -6 route show ==
fd00::/64 dev tap0 proto kernel metric 256 expires 86398sec pref medium
fe80::/64 dev tap0 proto kernel metric 256 pref medium
default via fe80::2 dev tap0 proto ra metric 1024 expires 1798sec hoplimit 64 pref medium
== ip -6 route get 2001:db8::1 ==
2001:db8::1 from :: via fe80::2 dev tap0 proto ra src fd00::a80a:54ff:fe04:b7fb metric 1024 hoplimit 64 pref medium
== try to add a static route as a normal user ==
RTNETLINK answers: Operation not permitted
(exit code 2: root/CAP_NET_ADMIN needed)

৪ · Longest prefix match গভীরে — তারপর AD, তারপর metric

পর্ব ১৫-এ longest prefix match-এর মূল নিয়ম আর একটি lookup simulator দেখেছেন: একাধিক সারি মিললে সবচেয়ে লম্বা prefix জেতে। বাস্তব router-এ প্রশ্নটি আরও জটিল, কারণ একই prefix কয়েকটি উৎস থেকে আসতে পারে — static থেকে, OSPF থেকে, RIP থেকে। তখন পুরো নিয়মটি তিন ধাপের:

1. সবচেয়ে লম্বা prefix — বেশি নির্দিষ্ট route সবসময় আগে। এটি অন্য কোনো কিছু দিয়ে উল্টানো যায় না।
2. একই prefix-এ সবচেয়ে কম AD — কোন উৎসকে বেশি বিশ্বাস। ভিন্ন protocol-এর metric তুলনা করা অর্থহীন (OSPF cost ৩০ আর RIP hop ২ — একক আলাদা), তাই আগে উৎস বাছা হয়।
3. একই উৎসে সবচেয়ে কম metric — একই protocol-এর ভেতরে কোন পথ সস্তা। Metric-ও সমান হলে কয়েকটি পথ একসাথে রাখা যায় — ECMP.

বাস্তবে ধাপ ২ আর ৩ ঘটে route শেখার সময় — RIB প্রতিটি prefix-এর জন্য সেরাটি বেছে FIB-এ বসায়। আর ধাপ ১ ঘটে প্রতিটি packet আসার মুহূর্তে, FIB-এ। ফল একই, তাই হিসাবের সুবিধার জন্য একসাথে ভাবা যায়। নিচে R1-এর কাছে গন্তব্য 10.20.30.40-এর জন্য তিনটি মেলা route (default-কে বাদ রেখে):

এবার পুরো নিয়মটি কোডে। নিচের engine-এ R1-এর RIB — connected, দুটি default (একটি AD ১, একটি AD ২৫০ backup), একটি static /16, একই /24-এর জন্য দুটি OSPF পথ আর একটি RIP পথ, আর 10.20.40.0/24-এর জন্য সমান খরচের দুটি OSPF পথ। প্রতিটি গন্তব্যের জন্য সব প্রার্থী (/len উৎস AD/metric) ছাপে, তারপর তিনটি ধাপে ছাঁকে, আর বন্ধনীতে লেখে কোন নিয়মে বাছাই হলো। শেষে ECMP-র জন্য flow-এর hash:

// Router R1's RIB: [prefix, source, AD, metric, next hop]. AD = vendor-style default.
const rib = [
  ["10.0.1.0/24", "connected", 0, 0, "eth1"],
  ["0.0.0.0/0", "static", 1, 0, "203.0.113.1"],
  ["0.0.0.0/0", "static", 250, 0, "198.51.100.1"],   // floating backup
  ["10.20.0.0/16", "static", 1, 0, "10.0.1.2"],
  ["10.20.30.0/24", "ospf", 110, 30, "10.0.1.3"],
  ["10.20.30.0/24", "ospf", 110, 50, "10.0.1.5"],
  ["10.20.30.0/24", "rip", 120, 2, "10.0.1.4"],
  ["10.20.40.0/24", "ospf", 110, 20, "10.0.1.3"],
  ["10.20.40.0/24", "ospf", 110, 20, "10.0.1.5"],
].map(([p, src, ad, m, nh]) => ({ p, src, ad, m, nh, len: +p.split("/")[1] }));
const ip = s => s.split(".").reduce((a, o) => a * 256 + +o, 0);
const hit = (r, d) => r.len === 0 || (d >>> (32 - r.len)) === (ip(r.p.split("/")[0]) >>> (32 - r.len));
function lookup(dst) {
  let c = rib.filter(r => hit(r, ip(dst))), why = [];
  console.log(dst + "  candidates: " + c.map(r => `/${r.len} ${r.src} ${r.ad}/${r.m}`).join(", "));
  for (const [k, f] of [["prefix /", Math.max], ["AD ", Math.min], ["metric ", Math.min]]) {
    const key = k[0] === "p" ? "len" : k[0] === "A" ? "ad" : "m";
    const best = f(...c.map(r => r[key]));
    if (c.some(r => r[key] !== best)) why.push(k + best);
    c = c.filter(r => r[key] === best);
  }
  const ecmp = c.length > 1 ? `, ECMP x${c.length}` : "";
  console.log(`   -> ${c[0].p} via ${c.map(r => r.nh).join(" + ")}  [${why.join(", ") || "only match"}${ecmp}]`);
  return c;
}
["10.20.30.40", "10.20.99.1", "10.0.1.77", "192.0.2.50"].forEach(lookup);
// ECMP: hash the 5-tuple (FNV-1a) so every packet of one flow takes the same path.
const fnv = s => [...s].reduce((h, ch) => Math.imul(h ^ ch.charCodeAt(0), 16777619) >>> 0, 2166136261);
const paths = lookup("10.20.40.7");
for (const sp of [50001, 50002, 50003, 50001, 50004, 50002]) {
  const flow = `tcp 10.0.1.9:${sp} -> 10.20.40.7:443`;
  console.log(`  ${flow}  hash ${fnv(flow) % paths.length} -> ${paths[fnv(flow) % paths.length].nh}`);
}

10.20.30.40  candidates: /0 static 1/0, /0 static 250/0, /16 static 1/0, /24 ospf 110/30, /24 ospf 110/50, /24 rip 120/2
   -> 10.20.30.0/24 via 10.0.1.3  [prefix /24, AD 110, metric 30]
10.20.99.1  candidates: /0 static 1/0, /0 static 250/0, /16 static 1/0
   -> 10.20.0.0/16 via 10.0.1.2  [prefix /16]
10.0.1.77  candidates: /24 connected 0/0, /0 static 1/0, /0 static 250/0
   -> 10.0.1.0/24 via eth1  [prefix /24]
192.0.2.50  candidates: /0 static 1/0, /0 static 250/0
   -> 0.0.0.0/0 via 203.0.113.1  [AD 1]
10.20.40.7  candidates: /0 static 1/0, /0 static 250/0, /16 static 1/0, /24 ospf 110/20, /24 ospf 110/20
   -> 10.20.40.0/24 via 10.0.1.3 + 10.0.1.5  [prefix /24, ECMP x2]
  tcp 10.0.1.9:50001 -> 10.20.40.7:443  hash 1 -> 10.0.1.5
  tcp 10.0.1.9:50002 -> 10.20.40.7:443  hash 0 -> 10.0.1.3
  tcp 10.0.1.9:50003 -> 10.20.40.7:443  hash 1 -> 10.0.1.5
  tcp 10.0.1.9:50001 -> 10.20.40.7:443  hash 1 -> 10.0.1.5
  tcp 10.0.1.9:50004 -> 10.20.40.7:443  hash 0 -> 10.0.1.3
  tcp 10.0.1.9:50002 -> 10.20.40.7:443  hash 0 -> 10.0.1.3

কেন longest prefix জেতে — একটি বাস্তব কারণ

ধরুন একটি ISP তার পুরো ব্লক 198.51.100.0/24 একটি route হিসেবে ঘোষণা করে (route aggregation — পর্ব ১৭)। এর ভেতরের একটি ছোট অংশ, 198.51.100.128/25, এমন একজন গ্রাহকের যিনি দুটি ISP-র সাথে যুক্ত। দ্বিতীয় ISP সেই /25 আলাদা করে ঘোষণা করে, আর longest prefix match-এর কারণে গ্রাহকের packet যায় /25 দিয়ে — aggregation-এর ভেতরে একটি ব্যতিক্রম। আবার এই শক্তিই বিপদও: কেউ ভুল করে বা ইচ্ছা করে কারও ঠিকানার আরও নির্দিষ্ট prefix ঘোষণা করলে সে traffic টেনে নেয় (BGP hijack — পর্ব ২৫)।

৫ · Lookup-এর ভেতরের কাঠামো — binary trie, Patricia trie আর TCAM

পর্ব ১৫-এর simulator টেবিলের প্রতিটি সারি একে একে দেখেছিল। দশ লক্ষ সারির টেবিলে প্রতিটি packet-এর জন্য তা অসম্ভব — সময় লাগবে সারির সংখ্যার সমানুপাতিক। সমাধান হলো এমন কাঠামো, যেখানে খোঁজার সময় নির্ভর করে ঠিকানার দৈর্ঘ্যের ওপর, সারির সংখ্যার ওপর নয়।

Binary trie — প্রতিটি bit একটি মোড়

Binary trie একটি গাছ, যার প্রতিটি node থেকে দুটি শাখা: bit ০ হলে বামে, ১ হলে ডানে। একটি prefix ঢোকাতে তার bit ধরে নিচে নামতে হয়, আর শেষ node-এ লিখে রাখতে হয় “এখানে একটি prefix শেষ হয়েছে, তার next hop এই”. খোঁজার সময় গন্তব্য ঠিকানার bit ধরে নিচে নামতে নামতে যত prefix-চিহ্নিত node পার হয়, শেষেরটিই সবচেয়ে লম্বা মিল। আর পথ শেষ হলে (পরের bit-এর শাখা নেই) থামা। এটি DSA-র Trie-রই রূপ — শব্দের অক্ষরের বদলে ঠিকানার bit.

নিচের কোড ছয়টি prefix trie-তে ঢোকায়, node গোনে, তারপর পাঁচটি ঠিকানা খোঁজে। প্রতিটি খোঁজে ছাপে কোন গভীরতায় (depth, অর্থাৎ কতটি bit পড়া হয়েছে) থামল, পথে কোন কোন prefix দেখা গেল, আর সবশেষে সেরা মিল:

// Binary trie for longest prefix match: one node per bit, left = 0, right = 1.
const ip = s => s.split(".").reduce((a, o) => a * 256 + +o, 0);
const bit = (x, i) => (x >>> (31 - i)) & 1;          // i-th bit from the left
const root = { kids: [null, null], hop: null };
let nodes = 1;
function insert(prefix, hop) {
  const [net, len] = prefix.split("/"), x = ip(net);
  let n = root;
  for (let i = 0; i < +len; i++) {
    const b = bit(x, i);
    if (!n.kids[b]) { n.kids[b] = { kids: [null, null], hop: null }; nodes++; }
    n = n.kids[b];
  }
  n.hop = `${prefix} -> ${hop}`;
}
[["0.0.0.0/0", "A"], ["10.0.0.0/8", "B"], ["10.1.0.0/16", "C"], ["10.1.2.0/24", "D"],
 ["10.1.2.128/25", "E"], ["203.0.113.0/24", "F"]].forEach(([p, h]) => insert(p, h));
console.log(`6 prefixes -> ${nodes} trie nodes`);
function lookup(dst) {
  const x = ip(dst);
  let n = root, depth = 0, best = null, walk = [];
  while (n) {
    if (n.hop) { best = n.hop; walk.push(`d${depth}:${n.hop.split(" ")[0]}`); }
    if (depth === 32) break;
    n = n.kids[bit(x, depth)];
    if (n) depth++;
  }
  console.log(`${dst.padEnd(12)} stopped at depth ${String(depth).padStart(2)} | ` +
    `seen ${walk.join(" ")} | best ${best}`);
}
["10.1.2.200", "10.1.2.7", "10.1.3.4", "10.200.0.1", "192.0.2.1"].forEach(lookup);

6 prefixes -> 50 trie nodes
10.1.2.200   stopped at depth 25 | seen d0:0.0.0.0/0 d8:10.0.0.0/8 d16:10.1.0.0/16 d24:10.1.2.0/24 d25:10.1.2.128/25 | best 10.1.2.128/25 -> E
10.1.2.7     stopped at depth 24 | seen d0:0.0.0.0/0 d8:10.0.0.0/8 d16:10.1.0.0/16 d24:10.1.2.0/24 | best 10.1.2.0/24 -> D
10.1.3.4     stopped at depth 23 | seen d0:0.0.0.0/0 d8:10.0.0.0/8 d16:10.1.0.0/16 | best 10.1.0.0/16 -> C
10.200.0.1   stopped at depth  8 | seen d0:0.0.0.0/0 d8:10.0.0.0/8 | best 10.0.0.0/8 -> B
192.0.2.1    stopped at depth  4 | seen d0:0.0.0.0/0 | best 0.0.0.0/0 -> A

Patricia trie আর TCAM

৬ · Static route — কখন, কীভাবে, আর তার কৌশলগুলো

Static route মানে প্রশাসক নিজে লিখে দিচ্ছেন “এই prefix-এর জন্য এই next hop”. কোনো protocol নেই, কোনো বার্তা বিনিময় নেই, CPU বা bandwidth খরচ নেই। কিন্তু নেটওয়ার্ক বদলালে টেবিল নিজে বদলাবে না।

একটি উদাহরণ নেটওয়ার্ক: R1 অফিসের মূল router. তার পেছনে LAN 10.0.1.0/24; সেখানে R2 (10.0.1.2) একটি শাখার দিকে, যেখানে 10.20.0.0/16. R1 ইন্টারনেটে যায় ISP-A দিয়ে (203.0.113.0/30 link, ISP-র router 203.0.113.1), আর backup হিসেবে আছে ISP-B (198.51.100.0/30 link, ISP-র router 198.51.100.1).

! ip route <prefix> <mask> <next hop বা interface> [AD]
ip route 10.20.0.0 255.255.0.0 10.0.1.2          ! শাখার নেটওয়ার্ক, R2 দিয়ে
ip route 0.0.0.0 0.0.0.0 203.0.113.1             ! default: ISP-A (AD 1)
ip route 0.0.0.0 0.0.0.0 198.51.100.1 250        ! floating default: ISP-B, শুধু ISP-A না থাকলে
ipv6 route ::/0 2001:db8:a::1                    ! IPv6 default (ঠিকানা documentation range থেকে)

$ sudo ip route add 10.20.0.0/16 via 10.0.1.2 dev eth1
$ sudo ip route add default via 203.0.113.1 metric 100
$ sudo ip route add default via 198.51.100.1 metric 200      # Linux-এ AD নেই — বেশি metric = backup
$ sudo ip -6 route add default via fe80::1 dev eth0          # IPv6-এ next hop প্রায়ই link-local
$ ip route get 10.20.5.9                                     # যাচাই: কোন সারি জিতবে

ip route add-এর route রিস্টার্টে মুছে যায়; স্থায়ী করতে netplan, NetworkManager বা systemd-networkd-এর কনফিগে লিখতে হয়। আর দূরের সার্ভারে default route বদলালে নিজের SSH সংযোগই কেটে যেতে পারে — আগে বর্তমান টেবিল সংরক্ষণ করুন।

Recursive lookup — next hop নিজেই দূরে থাকলে

Static route-এর next hop সরাসরি যুক্ত subnet-এ না-ও থাকতে পারে। ধরুন R1-এ লেখা আছে ip route 198.51.100.64 255.255.255.192 10.20.0.9. 10.20.0.9 কোনো connected subnet-এ নেই। তখন router দ্বিতীয়বার টেবিল খোঁজে — “10.20.0.9-এ কীভাবে যাব?” — পায় 10.20.0.0/16 via 10.0.1.2, আর 10.0.1.2 আছে connected 10.0.1.0/24-এ, eth1-এ। এই দুই-ধাপের খোঁজার নাম recursive lookup. BGP-তে এটি স্বাভাবিক (next hop প্রায়ই কয়েক hop দূরে); আধুনিক router FIB বানানোর সময়ই এই খোঁজা সেরে রাখে, তাই প্রতি packet-এ দুবার খুঁজতে হয় না।

Ethernet-এ next hop ছাড়া শুধু interface দিয়ে static route লিখলে router প্রতিটি গন্তব্যের জন্যই ARP করে, আর কাজ করে শুধু পাশের router proxy ARP দিলে (পর্ব ১৮)। তাই Ethernet-এ next hop লেখাই নিরাপদ; point-to-point link-এ শুধু interface দিলেও চলে।

Floating static route — backup যা ডুবে থাকে

Static route-এর AD ইচ্ছা করে বেশি দিলে (যেমন ২৫০), যতক্ষণ কম AD-র কোনো route একই prefix-এর জন্য থাকে, ততক্ষণ এটি টেবিলে বসে না — পানির নিচে ডুবে থাকে। মূল route চলে গেলে এটি “ভেসে ওঠে”. এজন্য নাম floating static. উপরের কনফিগে ISP-B-র default ঠিক এমন। বাস্তবে কী হয়, ধাপে ধাপে দেখি:

Linux-এ ধাপ ২-৩ একটু আলাদা: carrier চলে গেলে kernel route মুছে ফেলে না, শুধু linkdown চিহ্ন দেয়, আর ডিফল্টভাবে সেটি ব্যবহারও করতে পারে। net.ipv4.conf.all.ignore_routes_with_linkdown = 1 sysctl দিলে linkdown route এড়িয়ে পরের metric-এর route নেয়। এমন খুঁটিনাটি OS আর vendor-ভেদে আলাদা — তাই failover সবসময় পরীক্ষা করে দেখতে হয়, অনুমানে নয়।

Null route — summary-র ফাঁক বন্ধ করা

পর্ব ১৭-এ route summarisation দেখেছেন: শাখা router R2 তার চারটি LAN (10.20.0.0/24 থেকে 10.20.3.0/24) আলাদা না জানিয়ে একটি 10.20.0.0/22 হিসেবে জানায়। এতে মূল অফিসের টেবিলে চারটির বদলে একটি সারি — বড় নেটওয়ার্কে হাজার সারি থেকে কয়েকটিতে নামা যায়, lookup দ্রুত হয়, আর শাখার ভেতরের কোনো link ওঠানামা করলে বাকি নেটওয়ার্ককে জানাতে হয় না (route summarisation). কিন্তু ধরুন 10.20.2.0/24 এখনো ব্যবহার হয় না। 10.20.2.9-এর packet মূল অফিস summary দেখে R2-তে পাঠায়; R2-এর কাছে 10.20.2.0/24 নেই, মেলে শুধু তার default — যা মূল অফিসের দিকে। Packet ফিরে যায়, আবার আসে… ঠিক অংশ ৭-এর loop. সমাধান R2-তে একটি null route: Cisco-ধাঁচে ip route 10.20.0.0 255.255.252.0 Null0, Linux-এ ip route add blackhole 10.20.0.0/22. আসল LAN-গুলোর /24 route এর চেয়ে লম্বা, তাই সেগুলো আগের মতোই কাজ করে; শুধু summary-র অব্যবহৃত অংশ চুপচাপ ফেলে দেওয়া হয়। Linux-এ unreachable বা prohibit লিখলে ফেলে দেওয়ার সাথে উৎসকে ICMP-ও পাঠানো হয়।

৭ · ভুল static route-এ routing loop — TTL-এর রক্ষা

Dynamic protocol না থাকলে কেউ যাচাই করে না যে সব router-এর টেবিল মিলে একটি গাছ তৈরি করছে কি না। একটি টাইপো বা ভুলে যাওয়া route-ই যথেষ্ট: R2 বলে “এই গন্তব্য R3-এর দিকে”, আর R3 বলে “আমি জানি না, default ধরে R2-তে ফেরত”. Packet দুজনের মাঝে পিংপং বলের মতো ঘুরতে থাকে। এখানে বাঁচায় IP header-এর TTL: প্রতিটি router এক কমায়, আর যে router-এ পৌঁছে TTL আর কমানো যায় না (১ থাকে), সে packet ফেলে দিয়ে উৎসকে ICMP “Time Exceeded” পাঠায় (পর্ব ২০)। TTL না থাকলে loop-এর প্রতিটি packet চিরকাল ঘুরত, আর নতুন packet জমতে জমতে link পুরো ভরে যেত।

নিচের simulator চারটি router-কে একটি সারিতে রাখে: R1 – R2 – R3 – R4, আর LAN 10.4.0.0/24 আছে R4-এর পেছনে। প্রতিটি router নিজের static টেবিলে longest prefix match করে। Packet R1-এ আসে TTL ৮ নিয়ে (ছোট সংখ্যা যাতে আউটপুট ছোট থাকে; বাস্তবে সাধারণত ৬৪)। তিনটি পরীক্ষা: সঠিক কনফিগে LAN-এর একটি ঠিকানা, সঠিক কনফিগে অজানা একটি ঠিকানা, আর R3-এর একটি route হারিয়ে যাওয়ার পর।

// Static routes on 4 routers in a line: R1 - R2 - R3 - R4. LAN 10.4.0.0/24 sits behind R4.
const good = {
  R1: [["10.1.0.0/24", "connected"], ["0.0.0.0/0", "R2"]],
  R2: [["10.1.0.0/24", "R1"], ["10.4.0.0/24", "R3"]],          // no default route on R2
  R3: [["10.4.0.0/24", "R4"], ["0.0.0.0/0", "R2"]],
  R4: [["10.4.0.0/24", "connected"], ["0.0.0.0/0", "R3"]],
};
const ip = s => s.split(".").reduce((a, o) => a * 256 + +o, 0);
function lpm(table, dst) {
  let best = null;
  for (const [p, nh] of table) {
    const [net, len] = p.split("/");
    const ok = +len === 0 || (ip(dst) >>> (32 - len)) === (ip(net) >>> (32 - len));
    if (ok && (!best || +len > best.len)) best = { len: +len, nh, p };
  }
  return best;
}
function trace(name, routers, dst, ttl = 8) {
  let at = "R1", path = [];
  while (true) {
    const r = lpm(routers[at], dst);
    if (r && r.nh === "connected") { path.push(`${at}(deliver)`); console.log(`${name}: ${path.join(" > ")}  => DELIVERED`); return; }
    if (!r) { path.push(`${at}(no route)`); console.log(`${name}: ${path.join(" > ")}  => DROPPED, ICMP unreachable`); return; }
    if (ttl <= 1) { path.push(`${at}(TTL ${ttl})`); console.log(`${name}: ${path.join(" > ")}  => LOOP? TTL expired, ICMP time exceeded`); return; }
    path.push(`${at}(TTL ${ttl})`);
    ttl--; at = r.nh;
  }
}
trace("correct, 10.4.0.9 ", good, "10.4.0.9");
trace("correct, 10.9.9.9 ", good, "10.9.9.9");
const bad = { ...good, R3: [["0.0.0.0/0", "R2"]] };    // typo: R3 lost its route to R4
trace("broken R3, 10.4.0.9", bad, "10.4.0.9");

correct, 10.4.0.9 : R1(TTL 8) > R2(TTL 7) > R3(TTL 6) > R4(deliver)  => DELIVERED
correct, 10.9.9.9 : R1(TTL 8) > R2(no route)  => DROPPED, ICMP unreachable
broken R3, 10.4.0.9: R1(TTL 8) > R2(TTL 7) > R3(TTL 6) > R2(TTL 5) > R3(TTL 4) > R2(TTL 3) > R3(TTL 2) > R2(TTL 1)  => LOOP? TTL expired, ICMP time exceeded

৮ · ECMP আর policy-based routing

ECMP — সমান দুই পথ, দুটোই ব্যবহার

একই prefix, একই AD, একই metric-এর একাধিক পথ থাকলে router একটিকে বেছে বাকিগুলো অলস ফেলে রাখতে পারে — অথবা সবগুলো একসাথে ব্যবহার করতে পারে। দ্বিতীয়টির নাম ECMP (Equal-Cost Multi-Path). ঢাকা-চট্টগ্রাম যেতে মহাসড়ক আর রেল দুটোই সমান সময় নিলে সব যাত্রীকে এক পথে না পাঠিয়ে ভাগ করে দেওয়ার মতো — মোট বহন-ক্ষমতা দ্বিগুণ, আর এক পথ বন্ধ হলেও অন্যটি চলে।

কিন্তু ভাগ করবেন কীভাবে? প্রতিটি packet পালা করে আলাদা পথে পাঠালে (per-packet) একই TCP সংযোগের packet দুই পথে যায়; দুই পথের delay সামান্য আলাদা হলেই packet আগে-পরে পৌঁছায়। TCP তখন ভাবে packet হারিয়েছে, অপ্রয়োজনে আবার পাঠায় আর গতি কমায় (পর্ব ৩০, ৩২)। তাই প্রায় সব router করে per-flow hashing: packet-এর 5-tuple (উৎস ও গন্তব্য IP, উৎস ও গন্তব্য port, protocol) থেকে একটি hash হিসাব করে, পথের সংখ্যা দিয়ে ভাগশেষ নেয়, আর সেই নম্বরের পথে পাঠায়। একই flow-এর সব packet-এর 5-tuple একই, তাই hash-ও একই — অংশ ৪-এর আউটপুটে যেমন 50001 পোর্ট দুবারই 10.0.1.5-এ গেল।

সীমাবদ্ধতা: ভাগ হয় flow ধরে, byte ধরে নয় — একটি বিশাল ডাউনলোড আর একটি ছোট flow একই ওজন পায়। Data center-এর leaf-spine নেটওয়ার্ক পুরোপুরি ECMP-র ওপর দাঁড়িয়ে (পর্ব ৫২), আর স্তর ২-এর link aggregation (LACP, পর্ব ১২) একই ধরনের hash ব্যবহার করে।

Policy-based routing — গন্তব্য ছাড়া অন্য কিছু দেখে পথ

সাধারণ routing শুধু গন্তব্য ঠিকানা দেখে। কখনো চাওয়া হয় অন্য কিছু দেখে পথ বাছতে: “হিসাব বিভাগের (উৎস 10.0.1.0/25) সব traffic দামি কিন্তু নির্ভরযোগ্য ISP-A দিয়ে, বাকিরা সস্তা ISP-B দিয়ে”, বা “ভিডিও কনফারেন্সের port অন্য link দিয়ে”. একে বলে policy-based routing (PBR). Cisco-তে route-map দিয়ে মিলিয়ে set ip next-hop; Linux-এ একাধিক routing table আর ip rule — যেমন ip rule add from 10.0.1.0/25 table 100, আর table 100-এ আলাদা default. PBR সাধারণ ip route-এ দেখা যায় না, তাই সমস্যা খোঁজার সময় ip rule show-ও দেখুন।

৯ · Dynamic routing-এর শ্রেণিবিভাগ — IGP, EGP, AD আর convergence

Static route দিয়ে দশটি router চালানো যায়, দশ হাজার নয়। Dynamic routing algorithm-গুলো তিনটি প্রশ্নে ভাগ করা যায়:

দুই স্তরের routing — AS-এর ভেতরে আর মাঝে

পুরো ইন্টারনেট একটি বিশাল link-state নেটওয়ার্ক হলে প্রতিটি router-কে কোটি কোটি যন্ত্রের মানচিত্র রাখতে হতো, আর যেকোনো জায়গার link ওঠানামায় সবাইকে আবার হিসাব করতে হতো — অসম্ভব। তার ওপর ইন্টারনেট হাজার হাজার স্বাধীন প্রতিষ্ঠানের নেটওয়ার্ক — প্রত্যেকে নিজের নেটওয়ার্ক নিজের মতো চালাতে চায়। দুই সমস্যার সমাধান একসাথে: autonomous system (AS) — একটি প্রশাসনের অধীনের নেটওয়ার্ক, যার একটি AS নম্বর।

একটি AS-এর সীমানার router (gateway router) দুটোই চালায়: ভেতরের জন্য IGP, বাইরের জন্য BGP. বাইরের prefix-এর জন্য তার টেবিলে আসে “এই prefix BGP দিয়ে ওই gateway-এর মাধ্যমে”, আর সেই gateway-এ পৌঁছানোর পথ আসে IGP থেকে — অংশ ৬-এর recursive lookup ঠিক এখানে কাজে লাগে। বাংলাদেশের মতো দেশে দেশি ISP-গুলো নিজেদের মাঝে traffic বিনিময় করে দেশের ভেতরের exchange point-এ (BDIX-এর মতো IXP), আর বিদেশের traffic নেয় IIG-র মাধ্যমে — এর পুরোটাই AS আর BGP-র জগৎ (পর্ব ২৫)।

Administrative distance-এর টেবিল — vendor-এর পছন্দ

AD কোনো RFC-তে লেখা মান নয় — প্রতিটি vendor নিজে ঠিক করে, আর প্রশাসক বদলাতে পারেন। সবচেয়ে বেশি উদ্ধৃত হয় Cisco-র ডিফল্ট; Juniper একই ধারণাকে বলে “preference”, মান আলাদা; Linux kernel-এ AD নেই (FRR-এর মতো routing software Cisco-র কাছাকাছি মান ব্যবহার করে আর kernel-এ শুধু সেরাটি বসায়)। পরীক্ষায় “AD” প্রশ্ন এলে প্রায় সবসময় Cisco-র মান বোঝানো হয়:

এক vendor-এর ক্রম অন্য vendor-এ খাটবে, এমন ধরে নেওয়া চলে না — Juniper-এ OSPF (১০) static-এর (৫) পরেই, আর BGP অনেক নিচে।

Convergence — সবার একমত হতে কত সময়

একটি link নষ্ট হলো। পাশের router টের পায়, protocol বার্তা পাঠায়, অন্যরা শুনে নিজের হিসাব আবার করে, নতুন route FIB-এ বসায়। সব router নতুন, পরস্পর-সংগত টেবিলে পৌঁছাতে যে সময় লাগে, তা convergence time — এর মধ্যে ক্ষণস্থায়ী loop বা black hole হতে পারে। Link state সাধারণত কয়েক সেকেন্ডে converge করে (টাইমার টিউন করা আর BFD থাকলে এক সেকেন্ডেরও কম সময়ে), RIP-এর মতো distance vector কখনো মিনিট নেয় (পর্ব ২৩), আর BGP-তে কয়েক মিনিটও লাগতে পারে। Static route-এর convergence নেই — মানুষ না বদলানো পর্যন্ত টেবিল একই থাকে।

১০ · AI-এর যুগে routing table — উত্তর মিলিয়ে নেওয়া

“এই কনফিগে কী ভুল?” বা “আমার সার্ভারে দ্বিতীয় ISP-র backup route দিন” — AI এমন প্রশ্নে দ্রুত গোছানো কনফিগ লিখে দেয়। Routing-এর ভুল কিন্তু চুপচাপ থাকে: কনফিগ গ্রহণ করা হয়, কোনো error আসে না, আর সমস্যা ধরা পড়ে যেদিন মূল link নষ্ট হয়। AI-এর প্রচলিত ভুলগুলো চিনে রাখুন:

AI-এর routing পরামর্শ মানার আগে — চেকলিস্ট

• প্রতিটি গন্তব্যের সিদ্ধান্ত হাতে prefix → AD → metric ক্রমে মিলিয়েছি, আর ip route get দিয়ে নিশ্চিত হয়েছি
• AD বা metric-এর মান আমার vendor বা OS-এর ডকুমেন্টেশনে দেখেছি — অন্য vendor-এর মান ধরে নিইনি
• Summary থাকলে null route আছে, আর কোনো দুই প্রতিবেশী একে অপরকে default দেখাচ্ছে না
• Failover ল্যাবে বা VM-এ সত্যি link আর next hop বন্ধ করে পরীক্ষা করেছি
• বদলের আগে বর্তমান টেবিল আর কনফিগ সংরক্ষণ করেছি, আর শুধু নিজের বা অনুমতিপ্রাপ্ত নেটওয়ার্কে পরীক্ষা চালিয়েছি