Multiple access — ALOHA, CSMA/CD আর CSMA/CA

১ · একটি ঘর, অনেক বক্তা — ভাগ করা মাধ্যমের সমস্যা

কলেজের একটি ক্লাসরুম ভাবুন। স্যার বাইরে গেছেন, ৪০ জন শিক্ষার্থী। সবাই একসাথে কথা বললে কারও কথাই বোঝা যায় না — শব্দ মিশে যায়। কিন্তু চুপচাপ থাকলে ঘরটি অকারণে নষ্ট হয়। কোনো একটি নিয়ম দরকার: কে কখন বলবে।

নেটওয়ার্কেও ঠিক এই সমস্যা আছে। পর্ব ০৭ আর ০৮-এ দেখেছেন, bit যায় তামার তার, fiber বা বেতার তরঙ্গে। কিছু link হলো point-to-point — দুই প্রান্তে মাত্র দুটি যন্ত্র, যেমন আপনার কম্পিউটার থেকে switch-এর একটি port-এ যাওয়া একটি তার। কিন্তু অনেক link হলো broadcast channel: একজন পাঠালে সংযুক্ত সবাই শোনে। Wi-Fi-এর বাতাস, মোবাইল টাওয়ারের আশপাশের বেতার, পুরোনো দিনের এক লম্বা coaxial তারে যুক্ত অফিসের সব কম্পিউটার, বা একটি hub-এ জোড়া সব যন্ত্র — এরা সবাই একটি মাধ্যম ভাগ করে।

এমন মাধ্যমে দুই বা তার বেশি যন্ত্রের সংকেত একই সময়ে প্রাপকের কাছে পৌঁছালে তারা মিশে যায়। একে বলে collision. Collision-এ জড়িত সব frame সাধারণত নষ্ট হয়। প্রশ্নটি তাই দাঁড়ায়: অনেকগুলো যন্ত্র কীভাবে একটি চ্যানেল ভাগ করবে, যাতে collision কম হয় আর চ্যানেল যতটা সম্ভব কাজে লাগে? এই প্রশ্নের নাম multiple access সমস্যা, আর এর উত্তর যে নিয়ম, তাকে বলে MAC (medium access control) protocol.

একটি আদর্শ MAC protocol-এর কাছে আমরা কী চাই? R bit/s-এর একটি চ্যানেল আর M-টি যন্ত্র ধরে নিন:

• শুধু একজন পাঠাতে চাইলে সে পুরো R হারে পাঠাতে পারবে।
• M জন একসাথে পাঠাতে চাইলে প্রত্যেকে গড়ে R/M হার পাবে।
• পুরোপুরি বিকেন্দ্রীভূত — কোনো একটি “নিয়ন্ত্রক” যন্ত্র বা কেন্দ্রীয় ঘড়ির ওপর নির্ভর নয়, যা বিকল হলে সব বন্ধ।
• সরল আর সস্তা — প্রতিটি NIC-এ বসানো যায়।

কোনো একটি protocol চারটি শর্ত একসাথে নিখুঁতভাবে পূরণ করে না। প্রতিটি পরিবার কোনো একটিকে বিসর্জন দিয়ে অন্যটি পায় — এই পর্বের বাকি অংশ এই দাম-দরের গল্প।

২ · তিন পরিবার — ভাগ করে দেওয়া, এলোমেলো, পালা করে

(ক) চ্যানেল ভাগ করে দেওয়া — FDMA, TDMA, CDMA

পর্ব ০৮-এ multiplexing দেখেছেন — একটি link-এ অনেক প্রবাহ একসাথে বহন করা। একই কৌশল যখন অনেকগুলো আলাদা যন্ত্রের মধ্যে চ্যানেল ভাগ করতে ব্যবহার হয়, তখন নামের শেষে “multiple access” যোগ হয়:

• TDMA: সময়কে frame-এ, প্রতিটি frame-কে M-টি slot-এ ভাগ (পর্ব ০৮-এর TDM-এর মতো)। প্রতিটি যন্ত্র প্রতি frame-এ নিজের slot-এ পুরো হারে পাঠায়। কোনো collision নেই, সবাই ন্যায্য R/M পায়। কিন্তু একজনই পাঠাতে চাইলেও সে R/M-এর বেশি পায় না, আর অন্যদের খালি slot নষ্ট হয়। ২G মোবাইল নেটওয়ার্ক GSM-এ প্রতিটি carrier frequency ৮টি time slot-এ ভাগ করা হতো।
• FDMA: চ্যানেলের frequency পরিসর M-টি সরু ব্যান্ডে ভাগ (পর্ব ০৮-এর FDM). প্রত্যেকে সারাক্ষণ নিজের ব্যান্ডে পাঠায়, হার R/M. সমস্যা একই — অলস ব্যান্ড অন্য কেউ ব্যবহার করতে পারে না।
• CDMA: সবাই একই frequency-তে একই সময়ে পাঠায়, কিন্তু প্রত্যেকের data bit একটি নিজস্ব “code” দিয়ে গুণ করা। Code-গুলো এমনভাবে বাছা (পরস্পর orthogonal), যাতে প্রাপক নিজের code দিয়ে গুণ করে গড় নিলে শুধু কাঙ্ক্ষিত প্রেরকের bit ফিরে পায় আর বাকিদের অবদান প্রায় শূন্য হয়ে যায়। ৩G মোবাইলের (যেমন WCDMA) মূল ভিত্তি ছিল এটি; বিস্তারিত পর্ব ৫১-এ।

এই পরিবার ফোনকলের মতো স্থির ট্রাফিকে ভালো, কিন্তু দুর্বল bursty traffic: কম্পিউটারের ট্রাফিক হঠাৎ হঠাৎ আসে, বেশিরভাগ সময় চুপ। তখন নির্দিষ্ট ভাগ রাখা মানে অধিকাংশ slot বা ব্যান্ড নষ্ট — পর্ব ০৪-এ statistical multiplexing-এর যুক্তি মনে করুন।

(খ) Random access — যখন খুশি পাঠান, সংঘর্ষ হলে আবার

Random access protocol-এ কোনো ভাগ নেই। যার frame আছে, সে পুরো R হারে পাঠায়। Collision হলে জড়িত প্রত্যেকে একটি এলোমেলো সময় অপেক্ষা করে আবার পাঠায়। এলোমেলো কেন? সবাই যদি ঠিক ১ ms পরে আবার চেষ্টা করে, তারা আবার একসাথে ধাক্কা খাবে — চিরকাল। ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA — সবই এই পরিবারের।

(গ) Taking turns — পালা করে

তৃতীয় পরিবার দুই জগতের ভালোটা নিতে চায়: ভিড় কম হলে একজন প্রায় পুরো R পাবে, ভিড় বেশি হলে collision ছাড়াই সবাই পালা পাবে। কৌশল দুটি — একজন নিয়ন্ত্রক পালা করে ডাকে (polling), অথবা একটি অনুমতিপত্র (token) হাতে হাতে ঘোরে (token passing). অংশ ৯-এ বিস্তারিত।

৩ · ALOHA — হাওয়াইয়ের দ্বীপ থেকে প্রথম random access

ALOHA-র নিয়ম অবিশ্বাস্যরকম সরল:

1. Frame তৈরি হলেই পাঠিয়ে দিন — কিছু শোনার দরকার নেই।
2. কেন্দ্র frame ঠিকমতো পেলে একটি ACK (নিশ্চিতকরণ) পাঠায়।
3. নির্দিষ্ট সময়ে ACK না এলে ধরে নিন collision হয়েছে; একটি এলোমেলো সময় অপেক্ষা করে আবার পাঠান।

এই মূল রূপকে বলে pure ALOHA. ১৯৭২ সালে Larry Roberts একটি উন্নতি প্রস্তাব করেন: সময়কে সমান “slot”-এ ভাগ করুন, প্রতিটি slot ঠিক এক frame পাঠানোর সময়ের (T) সমান, আর সবাইকে বলুন frame পাঠানো শুরু করতে হবে শুধু slot-এর শুরুতে। এর নাম slotted ALOHA. এর জন্য সবার ঘড়ি মোটামুটি মিলিয়ে রাখতে হয় — কেন্দ্র নিয়মিত একটি সময়-সংকেত সম্প্রচার করলেই চলে। কিন্তু এই ছোট পরিবর্তনে throughput দ্বিগুণ হয়। কেন?

Vulnerable period — কোন সময়ে অন্য কেউ শুরু করলে আমার frame মরবে?

সব frame-এর দৈর্ঘ্য সমান ধরে নিন, পাঠাতে লাগে T সময়। আমাদের frame শুরু হলো t₀-এ, শেষ t₀ + T-তে। অন্য একটি frame যদি আমাদের frame-এর সাথে এক মুহূর্তের জন্যও মিলে যায়, দুটোই নষ্ট। যে সময়-জানালায় অন্য কারও শুরু করা আমাদের frame নষ্ট করে, তাকে বলে vulnerable period. নিচের ডায়াগ্রামে ধাপে ধাপে দেখুন।

৪ · Throughput-এর প্রমাণ — ১/(২e) আর ১/e কোথা থেকে আসে

বিশ্ববিদ্যালয় আর চাকরির লিখিত পরীক্ষায় এই প্রমাণটি খুব প্রিয়। প্রথমে দুটি সংজ্ঞা:

• S (throughput): প্রতি frame-সময় T-তে গড়ে কতগুলো frame সফলভাবে যায়। S = ১ মানে চ্যানেল একটুও নষ্ট না করে পুরো সময় কাজে লাগছে। S-কে “চ্যানেলের কত ভাগ কাজে লাগছে” হিসেবেও পড়া যায়।
• G (offered load): প্রতি T-তে গড়ে কতগুলো পাঠানোর চেষ্টা হয় — নতুন frame আর আবার পাঠানো frame মিলিয়ে। G > ১ হতেই পারে; তখন চ্যানেলে চাপ তার ক্ষমতার চেয়ে বেশি।

মডেলের অনুমান

অনেকগুলো (প্রায় অসীম) স্বাধীন যন্ত্র, প্রত্যেকে কালেভদ্রে পাঠায়। তাহলে মোট চেষ্টাগুলো সময়ের ওপর এলোমেলোভাবে ছড়ানো একটি Poisson প্রবাহ, গড় হার প্রতি T-তে G. এই মডেলে t সময়ে ঠিক k-টি চেষ্টা হওয়ার সম্ভাবনা:

এখান থেকে সবচেয়ে দরকারি ফল: t সময়ে একটিও চেষ্টা না হওয়ার সম্ভাবনা (k = ০) হলো e^−G·t/T. (আসলে retransmission আগের collision-এর ওপর নির্ভর করে, তাই এটি একটি সরল অনুমান।)

Pure ALOHA — S = G·e^−২G

1. একটি চেষ্টা সফল হয় যদি তার vulnerable period ২T-তে অন্য কোনো চেষ্টা শুরু না হয়। সেই সম্ভাবনা P_০ = e^−G·২T/T = e^−২G.
2. প্রতি T-তে G-টি চেষ্টা, প্রত্যেকটি e^−২G সম্ভাবনায় সফল। তাই S = G · e^−২G.
3. সর্বোচ্চ খুঁজতে অবকলন: dS/dG = e^−২G − ২G·e^−২G = e^−২G(১ − ২G). e^−২G কখনো শূন্য নয়, তাই dS/dG = ০ ⇔ G = ১/২.
4. G = ০.৫ বসালে S_max = ০.৫ · e^−১ = ১/(২e) ≈ ০.১৮৪. দ্বিতীয় অবকলন সেখানে ঋণাত্মক (বা সহজভাবে: G = ০-এ S = ০, আর G বড় হলে S → ০), তাই এটি সর্বোচ্চ।

Slotted ALOHA — S = G·e^−G

1. Vulnerable period T, তাই সফলের সম্ভাবনা e^−G, আর S = G·e^−G.
2. dS/dG = e^−G(১ − G) = ০ ⇔ G = ১.
3. S_max = ১ · e^−১ = ১/e ≈ ০.৩৬৮.

একটি বিকল্প প্রমাণও পরীক্ষায় আসে, যেখানে Poisson না ধরে সসীম N-টি যন্ত্র নেওয়া হয়। Slotted ALOHA-তে প্রতিটি যন্ত্র প্রতি slot-এ p সম্ভাবনায় পাঠায়। একটি slot সফল যদি ঠিক একজন পাঠায়: S(p) = N·p·(১ − p)^N−১ (এটি একটি binomial সম্ভাবনা)। অবকলন শূন্য করলে p = ১/N, আর S_max = (১ − ১/N)^N−১. N → ∞ হলে (১ − ১/N)^N → ১/e আর (১ − ১/N)^−১ → ১, তাই সীমা ১/e — একই উত্তর।

এবার সূত্র দুটি দিয়ে একটি টেবিল বানানো যাক, আর সর্বোচ্চ বিন্দু দুটি সংখ্যাগতভাবেও খুঁজে দেখা যাক (G-কে ০.০০১ ধাপে বাড়িয়ে)।

// Throughput S (good frames per frame-time) for offered load G (attempts per frame-time).
// Poisson model:  pure ALOHA S = G e^(-2G),  slotted ALOHA S = G e^(-G)
const pure = G => G * Math.exp(-2 * G);
const slotted = G => G * Math.exp(-G);
console.log("    G   pure S  slotted S  P(success) pure / slotted");
for (const G of [0.1, 0.25, 0.5, 0.75, 1, 1.5, 2, 3]) {
  console.log(G.toFixed(2).padStart(5) + pure(G).toFixed(4).padStart(9) +
    slotted(G).toFixed(4).padStart(11) +
    Math.exp(-2 * G).toFixed(3).padStart(14) + " / " + Math.exp(-G).toFixed(3));
}
// Find the maxima numerically (scan G in steps of 0.001) and compare with theory
let bp = [0, 0], bs = [0, 0];
for (let i = 1; i <= 3000; i++) {
  const G = i / 1000;
  if (pure(G) > bp[1]) bp = [G, pure(G)];
  if (slotted(G) > bs[1]) bs = [G, slotted(G)];
}
console.log("pure    max at G = " + bp[0] + ": S = " + bp[1].toFixed(4) +
  "   1/(2e) = " + (1 / (2 * Math.E)).toFixed(4));
console.log("slotted max at G = " + bs[0] + ": S = " + bs[1].toFixed(4) +
  "   1/e    = " + (1 / Math.E).toFixed(4));
const R = 10; // a 10 Mbps shared channel
console.log("useful data on " + R + " Mbps: pure " + (R * bp[1]).toFixed(2) +
  " Mbps, slotted " + (R * bs[1]).toFixed(2) + " Mbps");

    G   pure S  slotted S  P(success) pure / slotted
 0.10   0.0819     0.0905         0.819 / 0.905
 0.25   0.1516     0.1947         0.607 / 0.779
 0.50   0.1839     0.3033         0.368 / 0.607
 0.75   0.1673     0.3543         0.223 / 0.472
 1.00   0.1353     0.3679         0.135 / 0.368
 1.50   0.0747     0.3347         0.050 / 0.223
 2.00   0.0366     0.2707         0.018 / 0.135
 3.00   0.0074     0.1494         0.002 / 0.050
pure    max at G = 0.5: S = 0.1839   1/(2e) = 0.1839
slotted max at G = 1: S = 0.3679   1/e    = 0.3679
useful data on 10 Mbps: pure 1.84 Mbps, slotted 3.68 Mbps

তত্ত্ব কি বাস্তবে মেলে? — একটি Monte-Carlo পরীক্ষা

Poisson মডেলটি “অসীম যন্ত্র” ধরে। সসীম ৫০টি যন্ত্র নিয়ে slotted ALOHA সত্যি সত্যি চালালে কী হয়? নিচের simulator প্রতিটি slot-এ প্রতিটি যন্ত্রকে p = G/৫০ সম্ভাবনায় পাঠাতে দেয়, এক লাখ slot ধরে গোনে কোন slot সফল (ঠিক একজন), খালি (কেউ নয়) আর collision (দুই বা তার বেশি)। এলোমেলো সংখ্যা আসে একটি নির্দিষ্ট seed থেকে, তাই প্রতিবার একই ফল।

// Slotted ALOHA Monte-Carlo: N stations, each sends in a slot with probability p = G/N.
// Seeded PRNG -> the same numbers every run.
function rng(seed) {                         // mulberry32
  return () => {
    seed = (seed + 0x6D2B79F5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const N = 50, SLOTS = 100000;
console.log("   G  measured S  N-station Np(1-p)^(N-1)  Poisson Ge^-G  idle  collided");
for (const G of [0.25, 0.5, 1, 2, 3]) {
  const rand = rng(11), p = G / N;
  let ok = 0, idle = 0, coll = 0;
  for (let s = 0; s < SLOTS; s++) {
    let senders = 0;
    for (let k = 0; k < N; k++) if (rand() < p) senders++;
    if (senders === 1) ok++; else if (senders === 0) idle++; else coll++;
  }
  const exact = N * p * Math.pow(1 - p, N - 1);
  console.log(G.toFixed(2).padStart(4) + (ok / SLOTS).toFixed(4).padStart(12) +
    exact.toFixed(4).padStart(25) + (G * Math.exp(-G)).toFixed(4).padStart(15) +
    (100 * idle / SLOTS).toFixed(1).padStart(6) + "%" + (100 * coll / SLOTS).toFixed(1).padStart(9) + "%");
}

   G  measured S  N-station Np(1-p)^(N-1)  Poisson Ge^-G  idle  collided
0.25      0.1945                   0.1956         0.1947  77.8%      2.7%
0.50      0.3061                   0.3056         0.3033  60.5%      8.9%
1.00      0.3721                   0.3716         0.3679  36.1%     26.7%
2.00      0.2702                   0.2706         0.2707  12.8%     60.2%
3.00      0.1434                   0.1447         0.1494   4.5%     81.2%

৫ · CSMA — আগে শুনুন, তারপর বলুন

ALOHA-র সবচেয়ে বড় অপচয় হলো, কেউ পাঠাচ্ছে কি না তা না দেখেই পাঠানো। ভদ্র মানুষ কথা বলার আগে দেখে নেন অন্য কেউ বলছেন কি না। নেটওয়ার্কের ভাষায় এটাই carrier sense — চ্যানেলে কারও সংকেত (carrier) আছে কি না শোনা। এই নিয়ম যোগ করলে পাওয়া যায় CSMA (Carrier Sense Multiple Access). চ্যানেল ব্যস্ত পেলে কী করবে, তার তিনটি নীতি আছে (persistence):

শুনেও কেন collision? — propagation delay

CSMA যদি সব collision দূর করত, তাহলে আর কিছু লাগত না। কিন্তু পর্ব ০৫-এর propagation delay মনে করুন: সংকেত তারে চলে প্রায় ২ × ১০^৮ m/s-এ, তাৎক্ষণিক নয়। ধরুন A আর B একটি তারের দুই প্রান্তে, ২,০০০ m দূরে। A পাঠানো শুরু করল t = ০-তে। A-এর প্রথম bit B-তে পৌঁছাবে ২,০০০ ÷ (২ × ১০^৮) = ১০ µs পরে। এই ১০ µs-এর মধ্যে B চ্যানেল শুনলে নীরবতাই পাবে — আর সে-ও পাঠানো শুরু করতে পারে। CSMA-তে vulnerable period তাই মোটামুটি এক propagation delay: T_prop. Propagation delay frame-এর তুলনায় যত ছোট, CSMA তত ভালো কাজ করে — এই অনুপাতটিই অংশ ৭-এর efficiency সূত্রের “a”.

৬ · CSMA/CD — ক্লাসিক Ethernet-এর নিয়ম

সাধারণ CSMA-তে collision হলেও দুই প্রেরক পুরো frame পাঠিয়ে যায় — হয়তো ১,৫০০ byte, যার পুরোটাই নষ্ট। ক্লাসিক Ethernet-এর বুদ্ধি ছিল: পাঠানোর সময়ও তার শুনতে থাকা। তারের ওপর সংকেতের মাত্রা নিজের পাঠানো সংকেতের চেয়ে বেশি হলে বোঝা যায় অন্য কেউ-ও পাঠাচ্ছে — collision. ধরা পড়ামাত্র থেমে যাওয়া। এটাই CSMA/CD (Collision Detection). তারযুক্ত মাধ্যমে এটি সম্ভব, কারণ তারে নিজের সংকেত আর অন্যের সংকেত প্রায় সমান জোরে থাকে। পুরো নিয়মটি ধাপে ধাপে:

1. পাঠানোর frame তৈরি হলে চ্যানেল শুনুন (carrier sense).
2. চ্যানেল ব্যস্ত থাকলে খালি হওয়া পর্যন্ত অপেক্ষা (1-persistent), তারপর ৯৬ bit-সময়ের একটি ছোট ফাঁক (১০ Mbps-এ ৯.৬ µs, interframe gap).
3. পাঠানো শুরু করুন, আর পাঠানোর সময় শুনতে থাকুন।
4. পুরো frame collision ছাড়া গেলে কাজ শেষ।
5. Collision ধরা পড়লে সাথে সাথে frame থামিয়ে ৩২ bit-এর একটি jam signal পাঠান — যাতে তারের সবাই নিশ্চিতভাবে collision টের পায়।
6. তারপর binary exponential backoff: এটি যদি এই frame-এর n-তম collision হয়, তাহলে ০ থেকে ২^{min(n, ১০)} − ১ পর্যন্ত একটি পূর্ণসংখ্যা K এলোমেলোভাবে বেছে নিন, K × slot time অপেক্ষা করুন (১০ Mbps-এ slot time = ৫১২ bit-সময় = ৫১.২ µs), তারপর ধাপ ১-এ ফিরুন। ১৬ বার চেষ্টাতেও না হলে frame বাতিল।

এখন দুটি station-এর একটি সত্যিকারের collision সংখ্যা দিয়ে দেখি। ১০ Mbps-এর একটি তার, A আর B ২,০০০ m দূরে, s = ২ × ১০^৮ m/s — অর্থাৎ T_prop = ১০ µs, আর ১ µs-এ সংকেত যায় ২০০ m.

Binary exponential backoff — কেন “দ্বিগুণ”?

Collision হলে প্রত্যেকে জানে না আরও কতজন অপেক্ষায় আছে। দুজন হলে {০, ১} থেকে বাছাই যথেষ্ট — অর্ধেক সম্ভাবনায় আলাদা হয়ে যায়। বিশজন হলে {০, ১}-এ প্রায় নিশ্চিত আবার collision. পরিসর প্রতি collision-এ দ্বিগুণ করার যুক্তি: “বারবার ধাক্কা খাচ্ছি, নিশ্চয় অনেকে আছে।” কয়েকটি collision-এর মধ্যেই পরিসর প্রতিযোগীর সংখ্যার কাছাকাছি পৌঁছায়, আর load নিজে থেকে কমে — অংশ ৪-এর অস্থিরতার ওষুধ। ১০টি collision-এর পর পরিসর ০–১০২৩-এ আটকে থাকে, যাতে অপেক্ষা অসীম না হয়।

নিচের simulator তিনটি station (A, B, C) নিয়ে চলে; প্রত্যেকের একটি করে frame, সবাই slot ০-তে প্রস্তুত — তাই প্রথম slot-এ নিশ্চিত collision. সরল করার জন্য সময় slot-এ মাপা, আর carrier sense-এর বিস্তারিত বাদ: একটি slot-এ ঠিক একজন পাঠালে সফল, একাধিক হলে collision.

// Binary exponential backoff (classic Ethernet): 3 stations, one frame each,
// all ready at slot 0. After the n-th collision a station picks K in 0..2^min(n,10)-1
// and tries again K slots later. Slot = 51.2 us at 10 Mbps. Fixed seed.
function rng(seed) {                         // mulberry32
  return () => {
    seed = (seed + 0x6D2B79F5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const rand = rng(7);
const st = ["A", "B", "C"].map(name => ({ name, n: 0, next: 0, done: false }));
for (let slot = 0; st.some(s => !s.done) && slot < 100; slot++) {
  const tx = st.filter(s => !s.done && s.next === slot);
  if (tx.length === 0) continue;             // idle slot: print nothing
  if (tx.length === 1) {
    tx[0].done = true;
    console.log(`slot ${slot}: ${tx[0].name} sends alone -> SUCCESS ` +
      `(after ${tx[0].n} collision(s), t = ${(slot * 51.2).toFixed(1)} us)`);
    continue;
  }
  const picks = tx.map(s => {
    s.n++;                                   // n-th collision for this station
    const range = 2 ** Math.min(s.n, 10);    // K in 0..range-1
    const K = Math.floor(rand() * range);
    s.next = slot + 1 + K;                   // wait K whole slots, then retry
    return `${s.name}: n=${s.n} K=${K} of 0..${range - 1} -> slot ${s.next}`;
  });
  console.log(`slot ${slot}: ${tx.map(s => s.name).join("+")} COLLIDE | ` + picks.join(", "));
}

slot 0: A+B+C COLLIDE | A: n=1 K=0 of 0..1 -> slot 1, B: n=1 K=0 of 0..1 -> slot 1, C: n=1 K=1 of 0..1 -> slot 2
slot 1: A+B COLLIDE | A: n=2 K=2 of 0..3 -> slot 4, B: n=2 K=2 of 0..3 -> slot 4
slot 2: C sends alone -> SUCCESS (after 1 collision(s), t = 102.4 us)
slot 4: A+B COLLIDE | A: n=3 K=3 of 0..7 -> slot 8, B: n=3 K=3 of 0..7 -> slot 8
slot 8: A+B COLLIDE | A: n=4 K=3 of 0..15 -> slot 12, B: n=4 K=8 of 0..15 -> slot 17
slot 12: A sends alone -> SUCCESS (after 4 collision(s), t = 614.4 us)
slot 17: B sends alone -> SUCCESS (after 4 collision(s), t = 870.4 us)

৭ · Minimum frame size আর efficiency — খাতায় যেভাবে লিখবেন

কেন frame-কে অন্তত একটি round trip লম্বা হতে হবে

অংশ ৬-এর stepper-এ A collision-এর খবর পেয়েছে ১৮ µs-এ। কিন্তু A-এর frame যদি এর আগেই শেষ হয়ে যেত? তাহলে A পাঠানো শেষ করে ভাবত “সফল”, শোনা বন্ধ করত — অথচ frame পথে নষ্ট হয়েছে। CSMA/CD-র ভিত্তিই হলো: প্রেরককে frame শেষ করার আগেই collision জানতে হবে।

সবচেয়ে খারাপ অবস্থা ভাবুন। A আর B তারের দুই প্রান্তে, দূরত্বের propagation delay T_prop. A শুরু করল t = ০-তে। A-এর সংকেত B-তে পৌঁছানোর ঠিক আগমুহূর্তে (t = T_prop − ε) B শুরু করল। Collision B-এর কাছেই, আর B-এর সংকেত A-তে ফিরে আসতে আরও T_prop. অর্থাৎ A collision জানে প্রায় ২·T_prop সময়ে। তাই A-কে অন্তত ততক্ষণ পাঠাতে থাকতে হবে:

১০ Mbps Ethernet-এর ৬৪ byte — হিসাব

• শুধু তারের হিসাব: ক্লাসিক ১০ Mbps Ethernet-এ দুই প্রান্তের সর্বোচ্চ দূরত্ব প্রায় ২,৫০০ m (repeater দিয়ে জোড়া কয়েকটি segment মিলিয়ে)। T_prop = ২,৫০০ ÷ (২ × ১০^৮) = ১২.৫ µs, ২T_prop = ২৫ µs, তাই L_min = ১০^৭ × ২৫ × ১০^−৬ = ২৫০ bit ≈ ৩১.২৫ byte.
• বাস্তব বাজেট: কিন্তু পথে repeater, transceiver আর অন্য electronics-এর নিজের delay আছে, আর jam পাঠানোর সময়ও ধরতে হয়। IEEE 802.3 এসব মিলিয়ে সবচেয়ে খারাপ round trip-এর বাজেট ধরেছে ৫১২ bit-সময় = ৫১.২ µs — এটাই slot time. (অনেক পাঠ্যবই একে সরাসরি লেখে: ২T_p = ৫১.২ µs, অর্থাৎ যন্ত্রের delay সহ T_p = ২৫.৬ µs.)
• উত্তর: L_min = ১০^৭ bit/s × ৫১.২ × ১০^−৬ s = ৫১২ bit = ৬৪ byte. এজন্যই Ethernet frame (destination ঠিকানা থেকে FCS পর্যন্ত) কমপক্ষে ৬৪ byte; ডেটা কম হলে padding দিয়ে ভরানো হয় (frame-এর গঠন পর্ব ১২-এ)।

Efficiency — ১/(১ + ৫a)

CSMA/CD কতটা দক্ষ? ধরা যাক a = T_prop/T_trans, যেখানে T_prop দুই দূরতম station-এর মধ্যে propagation delay আর T_trans একটি সর্বোচ্চ-আকারের frame পাঠানোর সময়। অনেক station সবসময় পাঠাতে চাইলে দীর্ঘমেয়াদে চ্যানেলের যে ভাগ সফল frame-এ যায়, তার একটি প্রচলিত আসন্ন সূত্র (Kurose ও Ross-এর পাঠ্যবইয়ে দেওয়া, যার উৎস এর চেয়ে জটিল একটি বিশ্লেষণ):

এটি সঠিক মান নয়, মডেলের অনুমানে নির্ভর একটি সহজ নিয়ম — পরীক্ষায় লিখলে “আসন্ন” কথাটি লিখে দেবেন। সূত্রের বার্তা পরিষ্কার: a → ০ হলে (তার ছোট বা frame বড়) efficiency → ১; a বড় হলে efficiency ভেঙে পড়ে। নিচের calculator minimum frame আর efficiency দুটোই হিসাব করে।

// CSMA/CD rules of thumb: minimum frame (T_frame >= 2 x T_prop) and efficiency 1/(1+5a).
const s = 2e8;                               // signal speed in the cable, m/s
function minFrame(label, R, roundTrip_s) {
  const bits = R * roundTrip_s;              // bits sent while the round trip happens
  console.log(`${label.padEnd(34)} 2Tp = ${(roundTrip_s * 1e6).toFixed(2).padStart(6)} us` +
    ` -> min ${bits.toFixed(0).padStart(4)} bits = ${(bits / 8).toFixed(2)} bytes`);
}
minFrame("10 Mbps, 2500 m cable only", 10e6, 2 * 2500 / s);
minFrame("10 Mbps, IEEE round-trip budget", 10e6, 51.2e-6);
minFrame("100 Mbps, same 512-bit slot", 100e6, 5.12e-6);
console.log("100 Mbps: 5.12 us round trip covers at most " + (5.12e-6 / 2 * s).toFixed(0) +
  " m of cable (before any hub/repeater delay)");
console.log("");
console.log("efficiency = 1/(1+5a), a = Tprop/Ttrans");
function eff(label, R, d, frameBytes) {
  const tprop = d / s, ttrans = frameBytes * 8 / R, a = tprop / ttrans;
  console.log(`${label.padEnd(26)} a = ${a.toFixed(4).padStart(7)}  efficiency = ` +
    `${(100 / (1 + 5 * a)).toFixed(1)}%`);
}
eff("10 Mbps, 2500 m, 64 B", 10e6, 2500, 64);
eff("10 Mbps, 2500 m, 1518 B", 10e6, 2500, 1518);
eff("1 Gbps, 2500 m, 64 B", 1e9, 2500, 64);
eff("1 Gbps, 200 m, 1518 B", 1e9, 200, 1518);

10 Mbps, 2500 m cable only         2Tp =  25.00 us -> min  250 bits = 31.25 bytes
10 Mbps, IEEE round-trip budget    2Tp =  51.20 us -> min  512 bits = 64.00 bytes
100 Mbps, same 512-bit slot        2Tp =   5.12 us -> min  512 bits = 64.00 bytes
100 Mbps: 5.12 us round trip covers at most 512 m of cable (before any hub/repeater delay)

efficiency = 1/(1+5a), a = Tprop/Ttrans
10 Mbps, 2500 m, 64 B      a =  0.2441  efficiency = 45.0%
10 Mbps, 2500 m, 1518 B    a =  0.0103  efficiency = 95.1%
1 Gbps, 2500 m, 64 B       a = 24.4141  efficiency = 0.8%
1 Gbps, 200 m, 1518 B      a =  0.0823  efficiency = 70.8%

আজকের Ethernet-এ CSMA/CD কেন নেই

আজ অফিস বা বাসার প্রায় প্রতিটি Ethernet তার একটি কম্পিউটারকে সরাসরি একটি switch-এর port-এ জোড়ে। আধুনিক twisted-pair তারে পাঠানো আর গ্রহণের জন্য আলাদা জোড়া তার (বা gigabit-এ echo cancellation-এর মতো কৌশল) থাকে, আর switch-এর প্রতিটি port নিজেই একটি আলাদা collision domain. দুই প্রান্তের মাঝে আর কেউ নেই, আর দুজন একসাথে দুই দিকে পাঠাতে পারে — full-duplex. Collision-ই যখন হয় না, তখন carrier sense বা collision detection-এর দরকারই নেই। Full-duplex মোডে NIC CSMA/CD বন্ধ রাখে। ১০ Gbps আর তার চেয়ে দ্রুত Ethernet-এর standard-এ half-duplex মোডই রাখা হয়নি। তবু ৬৪ byte-এর নিয়ম আজও রয়ে গেছে, আর বেতারে এর আত্মীয় CSMA/CA প্রতিদিন কাজ করে। Switch কীভাবে frame পাঠায়, তা পর্ব ১২-এ।

৮ · বেতারে কেন আলাদা — CSMA/CA, hidden আর exposed terminal

Wi-Fi-ও ভাগ করা মাধ্যম, তবু CSMA/CD নয় — দুটি কারণে:

1. নিজের চিৎকারে অন্যের ফিসফিস শোনা যায় না। বেতারে প্রেরকের নিজের antenna-র সংকেত অনেক দূর থেকে আসা অন্যের সংকেতের চেয়ে বহু গুণ জোরালো — দূরত্বের সাথে সংকেতের শক্তি দ্রুত কমে। সাধারণ Wi-Fi radio এক সময়ে হয় পাঠায়, নয় শোনে।
2. Collision ঘটে প্রাপকের কাছে, প্রেরকের কাছে নয়। প্রেরক নিজের জায়গায় collision শুনতে পেলেও তাতে লাভ নেই, যদি প্রাপকের কাছে অন্য কারও সংকেত এসে মেশে — যেটা প্রেরক শুনতেই পায় না। এটাই বিখ্যাত hidden terminal problem.

তাই বেতারের দর্শন উল্টো: collision ধরা যায় না, তাই যতটা সম্ভব এড়ানো — CSMA/CA (Collision Avoidance). মূল ধারণাগুলো সংক্ষেপে (Wi-Fi-এর আসল সময়, সংখ্যা আর frame-এর বিস্তারিত পর্ব ১৪-এ):

• অপেক্ষার ফাঁক (IFS): পাঠানোর আগে চ্যানেলকে একটি নির্দিষ্ট সময় খালি দেখতে হয়। জরুরি উত্তরের (যেমন ACK) জন্য ফাঁক ছোট (SIFS), নতুন frame-এর জন্য বড় (DIFS) — ফলে ACK সবসময় আগে জায়গা পায়।
• আগেভাগে এলোমেলো backoff: চ্যানেল ব্যস্ত পেলে খালি হওয়ামাত্র লাফ দেওয়া নয় (1-persistent-এর বিপদ মনে করুন); একটি এলোমেলো সংখ্যক slot গোনা হয়, আর গোনার মাঝে চ্যানেল ব্যস্ত হলে গোনা থামিয়ে রাখা হয়, খালি হলে আবার চালু। শূন্যে পৌঁছালে পাঠানো। ব্যর্থ হলে পরের বার পরিসর বড় — Ethernet-এর মতোই exponential.
• প্রতিটি frame-এর ACK: collision ধরতে পারে না বলে প্রাপক প্রতিটি সফল frame-এর পর ACK পাঠায়; ACK না এলে প্রেরক ধরে নেয় হারিয়েছে, আবার পাঠায় — ALOHA-র পুরোনো বুদ্ধি।
• RTS/CTS (ঐচ্ছিক): বড় frame-এর আগে চ্যানেল “বুক” করা, যাতে hidden terminal চুপ থাকে — নিচের stepper-এ।

Exposed terminal — উল্টো সমস্যা

এবার চারটি যন্ত্র ভাবুন এক সারিতে: P ← B C → Q. B পাঠাচ্ছে বাঁ দিকের P-কে, আর C পাঠাতে চায় ডান দিকের Q-কে। B আর C কাছাকাছি, একে অপরকে শোনে; কিন্তু P অনেক দূরে বাঁয়ে, Q অনেক দূরে ডানে। C পাঠালে P-এর কাছে কোনো ক্ষতি হতো না (C-এর সংকেত P পর্যন্ত যায় না), আর Q-ও B-এর সংকেত পায় না। তবু C carrier sense করে B-এর সংকেত শোনে আর অকারণে চুপ থাকে। একে বলে exposed terminal problem — collision নয়, হারানো সুযোগ। সাধারণ CSMA/CA এটি পুরোপুরি সমাধান করে না; বরং নিরাপদ দিকে থাকে — অকারণে কিছুটা চুপ থাকা collision-এর চেয়ে ভালো।

৯ · পালা করে কথা — polling, token passing, DOCSIS আর মোবাইল

Polling — ক্যাপ্টেন ডাকেন

একটি নিয়ন্ত্রক (master) পালা করে প্রতিটি যন্ত্রকে জিজ্ঞেস করে: “পাঠানোর কিছু আছে?” যে যন্ত্রকে ডাকা হয়, সে নির্দিষ্ট পরিমাণ পর্যন্ত পাঠায়, তারপর পরের জনের পালা। Collision নেই, অলস slot নেই। কিন্তু দুটি দাম: (১) প্রতিটি ডাকের খরচ (polling delay) — একজনই পাঠাতে চাইলেও সবাইকে ডাকতে হয়; (২) নিয়ন্ত্রক বিকল হলে পুরো নেটওয়ার্ক বন্ধ। উদাহরণ: ক্লাসিক Bluetooth-এর piconet-এ central যন্ত্র পালা করে অন্যদের সুযোগ দেয়।

Token passing — হাতে হাতে চক

কোনো নিয়ন্ত্রক নেই। একটি ছোট বিশেষ frame — token — যন্ত্র থেকে যন্ত্রে নির্দিষ্ট ক্রমে ঘোরে। যার কাছে token, শুধু সে পাঠাতে পারে (নির্দিষ্ট সর্বোচ্চ সময় পর্যন্ত), তারপর token পরের জনকে দেয়। এতে collision নেই, আর সর্বোচ্চ কতক্ষণ পরে পালা আসবে তা নিশ্চিত — নির্ধারিত (deterministic) delay. দুর্বলতা: token হারালে বা বলয় ভাঙলে তা সামলানোর জটিল নিয়ম লাগে।

• IBM Token Ring (IEEE 802.5): ১৯৮০-এর দশকে অফিস LAN-এ Ethernet-এর প্রধান প্রতিদ্বন্দ্বী, ৪ আর পরে ১৬ Mbps. যন্ত্রগুলো যুক্ত থাকত একটি তারকা-আকৃতির hub-এর মতো যন্ত্রে (MAU), কিন্তু token ঘুরত যৌক্তিক বলয়ে।
• FDDI: ১০০ Mbps-এর fiber-ভিত্তিক token passing, দুটি উল্টো দিকে ঘোরা বলয় — একটি বলয় কাটা পড়লে অন্যটি দিয়ে চলে। ১৯৯০-এর দশকে বিশ্ববিদ্যালয় ক্যাম্পাস আর বড় প্রতিষ্ঠানের backbone-এ ব্যবহৃত হতো।

দুটিই আজ প্রায় বিলুপ্ত — সস্তা, সরল, দ্রুত বেড়ে চলা switched Ethernet-এর কাছে হেরে গেছে (ভাবনার প্রশ্ন ৪)।

আধুনিক মিশ্র রূপ — DOCSIS আর মোবাইল নেটওয়ার্ক

বাস্তবের বড় নেটওয়ার্ক প্রায়ই পরিবারগুলো মিশিয়ে ব্যবহার করে:

• কেবল ইন্টারনেট (DOCSIS): কেবল টিভির coaxial তারে অনেক বাড়ির modem একটি upstream চ্যানেল ভাগ করে। কেন্দ্রের যন্ত্র (CMTS) নিয়মিত একটি “map” পাঠায় — কোন ছোট slot (mini-slot) কার জন্য বরাদ্দ। কিছু mini-slot প্রতিযোগিতার জন্য: সেখানে modem ছোট request পাঠায় (random access, collision হলে backoff), আর CMTS তার জন্য collision-মুক্ত slot বরাদ্দ করে। ছোট request-এ এলোমেলো প্রতিযোগিতা, বড় ডেটায় নির্ধারিত বরাদ্দ — দুই জগতের ভালোটা।
• মোবাইল নেটওয়ার্ক (4G/5G): টাওয়ারের base station একটি কেন্দ্রীয় scheduler চালায় — প্রতি মিলিসেকেন্ডের মতো ছোট সময়ে ঠিক করে কোন ফোন কোন frequency-অংশে (resource block) পাঠাবে বা পাবে। কিন্তু ফোন প্রথমবার যোগাযোগ শুরু করতে যে “random access” প্রক্রিয়া চালায়, সেখানে অনেক ফোন একই সুযোগে ছোট সংকেত পাঠিয়ে প্রতিযোগিতা করে — slotted ALOHA-র মতো ধারণা, collision হলে আবার চেষ্টা (পর্ব ৫১)।

১০ · AI-এর যুগে MAC protocol-এর অঙ্ক আর ব্যাখ্যা

AI-এর কাছে ALOHA-র প্রমাণ চাইলে সাধারণত সুন্দর উত্তর আসে। কিন্তু এই বিষয়ে AI-এর ভুলগুলো খুব নির্দিষ্ট ধরনের, আর আত্মবিশ্বাসী ভাষার নিচে চাপা পড়ে।

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

• Vulnerable period (pure ২T, slotted T, CSMA প্রায় T_prop) ঠিক আছে কি না দেখেছি
• অবকলন নিজে করে বা উপরের টেবিলের কোড চালিয়ে সর্বোচ্চ বিন্দু (G = ০.৫ আর ১) মিলিয়েছি
• প্রতিটি ধাপে একক মিলিয়েছি: bit বনাম byte, µs বনাম ms, km বনাম m
• “Ethernet” বললে কোন রূপ — পুরোনো half-duplex bus না আধুনিক full-duplex switch — তা স্পষ্ট করেছি
• ইতিহাস, তারিখ আর standard-এর নম্বর মূল উৎসে যাচাই করেছি; duplex বা Wi-Fi সেটিং বদলানোর পরীক্ষা শুধু নিজের ল্যাব বা অনুমতি থাকা যন্ত্রে করেছি