Framing আর ARQ — stop-and-wait, Go-Back-N আর Selective Repeat

১ · Data link স্তর — পাশের স্টেশন পর্যন্ত ঠিকঠাক পৌঁছানো

পর্ব ০৭ আর ০৮-এ দেখেছেন, physical layer শুধু bit পাঠায় — তারে ভোল্টেজ, fiber-এ আলো, বাতাসে তরঙ্গ। কোন bit কোন বার্তার অংশ, কোথায় শুরু কোথায় শেষ, পথে কোনো bit উল্টে গেল কি না — এসব নিয়ে physical layer মাথা ঘামায় না। এই দায়িত্ব তার ঠিক ওপরের স্তরের: data link layer.

Data link স্তর সাধারণত এই চারটি সেবা দেয়:

দুই উপস্তর — LLC আর MAC

LAN-এর মানদণ্ড তৈরি করতে গিয়ে IEEE-র 802 কমিটি data link স্তরকে দুই ভাগ করে। নিচের ভাগ MAC sublayer মাধ্যমের সাথে সরাসরি জড়িত: কে কখন পাঠাবে, frame-এ কোন MAC ঠিকানা বসবে, FCS কীভাবে হবে। এজন্য Ethernet (802.3) আর Wi-Fi (802.11)-এর MAC সম্পূর্ণ আলাদা। ওপরের ভাগ LLC (802.2) মাধ্যম-নিরপেক্ষ: network স্তরকে একই চেহারা দেখায় আর frame-এর ভেতরে কোন protocol-এর ডেটা তা চিহ্নিত করে। বাস্তবে আজকের Ethernet-এ IP বহনের সময় সাধারণত LLC header থাকেই না — frame-এর EtherType ঘর সেই কাজ করে দেয় (পর্ব ১২)। তবে ধারণাটি পরীক্ষায় প্রায়ই আসে।

তিন ধরনের সেবা

কোনটি বেছে নেওয়া হবে, তা নির্ভর করে link-এ ত্রুটি কত ঘন ঘন হয় তার ওপর। এই প্রশ্নে আমরা অংশ ৮-এ আবার ফিরব। তার আগে প্রথম সমস্যা: frame-এর সীমানা চেনা।

২ · Framing — bit-এর স্রোতে frame-এর শুরু আর শেষ

প্রাপকের কাছে আসে শুধু একটানা bit: 0110100101111110.... এর মধ্যে কোথায় একটি frame শেষ হয়ে পরেরটি শুরু হলো, তা বোঝানোর নিয়মকে বলে framing. চারটি পরিচিত পদ্ধতি আছে।

(ক) Character count — শুরুতে দৈর্ঘ্য লিখে দেওয়া

প্রতিটি frame-এর প্রথম ঘরে লেখা থাকে frame-এ কতগুলো byte. যেমন 5 A B C D মানে এই frame ৫ byte-এর (গোনার ঘরসহ), এরপর পরের frame. সরল, কিন্তু বিপজ্জনক: পথে শুধু গোনার ঘরটি নষ্ট হয়ে 5-এর জায়গায় 7 হলে প্রাপক পরের frame-এর দুটি byte-ও এই frame-এ টেনে নেবে। তারপর ভুল জায়গাকে পরের frame-এর গোনা ভেবে পড়বে, আর এভাবে পুরো স্রোতের সাথে তাল হারাবে। FCS বলতে পারবে frame নষ্ট, কিন্তু পরের frame কোথায় শুরু, তা বলতে পারবে না। এজন্য একা character count প্রায় কোথাও ব্যবহার হয় না; তবে অন্য পদ্ধতির সাথে দৈর্ঘ্যের ঘর রাখা খুবই প্রচলিত।

(খ) Flag byte আর byte stuffing

দ্বিতীয় বুদ্ধি: frame-এর শুরু আর শেষে একটি বিশেষ byte — FLAG. তাল হারালেও প্রাপক শুধু পরের FLAG খুঁজলেই আবার সঠিক জায়গায় ফিরে আসে। কিন্তু নতুন সমস্যা: ছবি বা zip ফাইলের মতো ডেটার ভেতরেও তো FLAG-এর মান থাকতে পারে! তখন প্রাপক সেটিকে frame-এর শেষ ভেবে বসবে।

সমাধান byte stuffing: ডেটার ভেতরে FLAG এলে তার আগে একটি escape byte (ESC) বসানো হয়। আর ডেটায় ESC নিজেই এলে? তার আগেও একটি ESC. প্রাপক নিয়ম জানে: ESC দেখলে সেটি ফেলে দিয়ে পরের byte-টি হুবহু ডেটা হিসেবে নেবে। C-তে স্ট্রিংয়ের ভেতর উদ্ধৃতিচিহ্ন লিখতে \" লেখার কথা ভাবুন — একই বুদ্ধি।

বাস্তবের PPP (RFC 1662) একটু ভিন্নভাবে করে: FLAG = 0x7E, ESC = 0x7D, আর escape করা byte-কে 0x20 দিয়ে XOR করে পাঠায়। অর্থাৎ 7E হয়ে যায় 7D 5E, আর 7D হয় 7D 5D. ফলে frame-এর ভেতরে কোথাও 7E থাকে না, আর প্রাপক যেকোনো 7E দেখেই নিশ্চিন্তে সীমানা ধরে। খরচ: খুব খারাপ ক্ষেত্রে (সব byte-ই 7E) frame প্রায় দ্বিগুণ লম্বা হয়ে যায়।

(গ) Bit stuffing — HDLC-র কৌশল

Byte stuffing ধরে নেয় ডেটা ৮ bit-এর byte-এ ভাগ করা। কিন্তু যেকোনো দৈর্ঘ্যের bit-স্রোতের জন্য একটি সাধারণ সমাধান আছে — bit stuffing, যা HDLC ব্যবহার করে। Flag হলো 01111110 — অর্থাৎ ছয়টি টানা 1. নিয়ম মাত্র দুটি:

• প্রেরক: ডেটায় টানা পাঁচটি 1 পাঠানোর পর পরের bit যা-ই হোক, একটি 0 বসিয়ে দেয়।
• প্রাপক: টানা পাঁচটি 1-এর পর 0 এলে সেটি মুছে দেয়। পাঁচটি 1-এর পর আবার 1 এলে বোঝে এটি flag (পরের bit 0 হলে) বা ত্রুটি/abort (সাতটি বা বেশি 1).

ফলে ডেটার ভেতরে কখনো ছয়টি টানা 1 যায় না, তাই flag শুধু সীমানাতেই দেখা দেয়। নিচের ডায়াগ্রামে ১৫ bit-এর একটি payload ধাপে ধাপে stuff হচ্ছে — এর ভেতরে flag-এর হুবহু নকশা 01111110-ও আছে।

(ঘ) Physical layer-এর coding violation

চতুর্থ পদ্ধতি physical স্তরের সাহায্য নেয়। অনেক line code-এ কিছু সংকেত-নকশা ডেটার জন্য কখনো ব্যবহার হয় না (পর্ব ০৭)। সেই “নিষিদ্ধ” নকশাকে ইচ্ছে করে frame-এর সীমানা হিসেবে পাঠানো যায় — একে বলে coding violation. যেমন 100BASE-TX (Fast Ethernet)-এর 4B/5B কোডে stream-এর শুরু আর শেষ বোঝাতে আলাদা কিছু control symbol আছে, যা কোনো ডেটা-nibble থেকে তৈরি হয় না; পুরোনো Token Ring-এ Manchester কোডের নিয়ম ভাঙা সংকেত দিয়ে সীমানা চিহ্নিত হতো। সুবিধা: stuffing লাগে না, ডেটা বাড়ে না।

নিচের প্রোগ্রাম দুই ধরনের stuffing-এরই encoder আর decoder — ওপরের stepper-এর payload আর PPP-র নিয়মে একটি byte-উদাহরণ:

// Bit stuffing (HDLC) and byte stuffing (PPP, RFC 1662) - encoder and decoder.
const FLAG = "01111110";
function bitStuff(bits) {                  // after five 1s in a row, insert a 0
  let out = "", ones = 0;
  for (const b of bits) {
    out += b; ones = b === "1" ? ones + 1 : 0;
    if (ones === 5) { out += "0"; ones = 0; }
  }
  return FLAG + out + FLAG;
}
function bitUnstuff(frame) {               // drop the 0 that follows five 1s
  const body = frame.slice(8, -8); let out = "", ones = 0, skip = false;
  for (const b of body) {
    if (skip) { skip = false; ones = 0; continue; }   // this is the stuffed 0
    out += b; ones = b === "1" ? ones + 1 : 0;
    if (ones === 5) skip = true;
  }
  return out;
}
const hex = a => a.map(x => x.toString(16).toUpperCase().padStart(2, "0")).join(" ");
function byteStuff(data) {                 // 7E -> 7D 5E, 7D -> 7D 5D
  const out = [0x7E];
  for (const x of data) x === 0x7E || x === 0x7D ? out.push(0x7D, x ^ 0x20) : out.push(x);
  return [...out, 0x7E];
}
function byteUnstuff(f) {
  const out = [];
  for (let i = 1; i < f.length - 1; i++) out.push(f[i] === 0x7D ? f[++i] ^ 0x20 : f[i]);
  return out;
}
const fr = bitStuff("011111101111101");
console.log("bits  in : 011111101111101\nframe    : " + fr + "\nback     : " + bitUnstuff(fr));
const data = [0x41, 0x7E, 0x42, 0x7D, 0x43];   // 'A' FLAG 'B' ESC 'C'
const bf = byteStuff(data);
console.log("bytes in : " + hex(data) + "\nframe    : " + hex(bf) + "\nback     : " + hex(byteUnstuff(bf)));

bits  in : 011111101111101
frame    : 011111100111110101111100101111110
back     : 011111101111101
bytes in : 41 7E 42 7D 43
frame    : 7E 41 7D 5E 42 7D 5D 43 7E
back     : 41 7E 42 7D 43

৩ · Flow control, error control আর ARQ — stop-and-wait

দুটি আলাদা সমস্যা প্রায়ই একসাথে সমাধান করা হয়, তাই গুলিয়ে যায়:

• Flow control — প্রাপকের buffer বা প্রসেসর ধীর হলে প্রেরককে থামানো। এখানে কোনো ত্রুটি নেই, শুধু গতির অমিল।
• Error control — frame নষ্ট বা হারিয়ে গেলে টের পাওয়া আর আবার পাঠানো।

দুটিরই সবচেয়ে প্রচলিত সমাধান ARQ (automatic repeat request) পরিবারের protocol. এর তিনটি উপকরণ:

1. ACK — প্রাপকের প্রাপ্তিস্বীকার। ACK না পাঠিয়ে প্রাপক প্রেরককে থামিয়েও রাখতে পারে — এটাই flow control.
2. Timer — প্রতিটি frame পাঠিয়ে প্রেরক একটি timer চালু করে। নির্দিষ্ট সময়ে ACK না এলে timeout হয়, আর frame আবার যায়। নষ্ট frame প্রাপক FCS দেখে ফেলে দেয় (পর্ব ০৯), কোনো উত্তর দেয় না — তাই নষ্ট আর হারানো, দুটিই timeout দিয়ে ধরা পড়ে।
3. Sequence number — frame-এ ক্রমিক নম্বর, যাতে প্রাপক একই frame দুবার পেলে বুঝতে পারে।

Stop-and-wait: একটি পাঠানো, তারপর ACK-এর অপেক্ষা

সবচেয়ে সরল ARQ হলো stop-and-wait: একটি frame পাঠিয়ে তার ACK না আসা পর্যন্ত প্রেরক আর কিছু পাঠায় না। মুদি দোকানের ছেলেটি একবারে একটি বস্তা ভ্যানে নিয়ে বাড়িতে পৌঁছে দেয়, আর মালিক “পেয়েছি” বললে তবেই পরের বস্তা আনতে যায় — ঠিক এমন।

Sequence number কেন লাগে, দুটি দুর্ঘটনা দিয়ে দেখুন:

প্রেরক                              প্রাপক
  │── F0 (seq 0) ─────────────────────►│  নিল, ওপরে দিল
  │◄──────────────────────── ACK 1 ────│  (“এবার 1 চাই”)
  │── F1 (seq 1) ───────── ✗ হারাল     │
  │   ... timer চলছে ...               │  কিছুই আসেনি
  │   timeout!                         │
  │── F1 (seq 1) আবার ───────────────►│  নিল, ওপরে দিল
  │◄──────────────────────── ACK 0 ────│

প্রেরক                              প্রাপক
  │── F1 (seq 1) ────────────────────►│  নিল, ওপরে দিল
  │       ✗ হারাল ◄──────── ACK 0 ────│
  │   timeout!                         │
  │── F1 (seq 1) আবার ───────────────►│  seq 1? আমি তো 0 চাই —
  │                                    │  নকল! ফেলে দিল
  │◄──────────────────────── ACK 0 ────│  তবু ACK আবার পাঠাল
  │── F2 (seq 0) ────────────────────►│  নিল

Stop-and-wait-এ একসাথে পথে থাকে মাত্র একটি frame, তাই পাশাপাশি দুটি frame-কে আলাদা করতে পারলেই যথেষ্ট: ১ bit-এর নম্বর — 0, 1, 0, 1 … এজন্য একে alternating bit protocol-ও বলে। এখানে ACK-এর নম্বর মানে “পরের যেটি চাই” — অনেক পাঠ্যবইয়ের রীতি; কোনো কোনো বই ACK-এ সদ্য পাওয়া frame-এর নম্বর লেখে। পরীক্ষায় কোন রীতি ধরছেন, তা লিখে দিন।

নিচের C প্রোগ্রাম আসল socket-এ stop-and-wait চালায়। socketpair দুটি জোড়া socket বানায় (OS-এর IPC, অপারেটিং সিস্টেম কোর্সে দেখেছেন), fork করে child হয় প্রাপক, parent প্রেরক। “Lossy” চ্যানেল বানাতে প্রেরক frame 2-এর প্রথম কপি ইচ্ছে করে পাঠায় না, আর প্রাপক frame 3-এর প্রথম ACK ইচ্ছে করে ফেলে দেয়। ACK-এর জন্য অপেক্ষা হয় poll দিয়ে, ২০০ ms timeout-সহ।

#include <stdio.h>
#include <unistd.h>
#include <poll.h>
#include <sys/socket.h>
#include <sys/wait.h>
int main(void) {                    /* stop-and-wait over a "lossy" socketpair */
    int sv[2], sent = 0, lostF = 0;
    if (socketpair(AF_UNIX, SOCK_SEQPACKET, 0, sv) < 0) { perror("socketpair"); return 1; }
    fflush(stdout); if (fork() == 0) {  /* receiver: prints nothing, only sends ACKs */
        char f[2], expect = 0; int accepted = 0, lostA = 0; close(sv[0]);
        while (read(sv[1], f, 2) == 2) {
            int dup = (f[0] != expect);
            if (!dup) { expect ^= 1; accepted++; }           /* new frame: deliver it */
            char ack = (char)(expect | (dup ? 2 : 0));       /* ACK = next expected seq */
            if (accepted == 4 && !lostA) { lostA = 1; continue; }  /* ACK of frame 3 lost */
            if (write(sv[1], &ack, 1) != 1) break;
        }
        _exit(0);
    }
    close(sv[1]); char seq = 0, ack;
    for (int i = 0; i < 5; i++, seq ^= 1)
        for (;;) {
            char f[2] = { seq, (char)('A' + i) };
            sent++;
            if (i == 2 && !lostF) { lostF = 1; printf("send frame %d seq=%d  (lost on the wire)\n", i, seq); }
            else { if (write(sv[0], f, 2) != 2) return 1; printf("send frame %d seq=%d\n", i, seq); }
            struct pollfd p = { sv[0], POLLIN, 0 };
            if (poll(&p, 1, 200) == 0) { printf("   timeout (200 ms) -> resend\n"); continue; }
            if (read(sv[0], &ack, 1) != 1) return 1;
            printf("   got ACK %d%s\n", ack & 1, (ack & 2) ? "  (receiver: duplicate, discarded)" : "");
            if ((ack & 1) == (seq ^ 1)) break;
        }
    close(sv[0]); wait(NULL); printf("5 frames delivered with %d transmissions\n", sent);
    return 0;
}

send frame 0 seq=0
   got ACK 1
send frame 1 seq=1
   got ACK 0
send frame 2 seq=0  (lost on the wire)
   timeout (200 ms) -> resend
send frame 2 seq=0
   got ACK 1
send frame 3 seq=1
   timeout (200 ms) -> resend
send frame 3 seq=1
   got ACK 0  (receiver: duplicate, discarded)
send frame 4 seq=0
   got ACK 1
5 frames delivered with 7 transmissions

৪ · Stop-and-wait-এর efficiency — U = 1/(1 + 2a)

Stop-and-wait নির্ভরযোগ্য, কিন্তু কতটা ধীর? পর্ব ০৫-এর দুটি delay (transmission আর propagation) দিয়েই হিসাবটি করা যায়। ধরা যাক:

• T_trans = L/R — একটি frame-এর সব bit তারে নামাতে সময়;
• T_prop = d/s — একটি bit-এর ওপারে পৌঁছাতে সময়;
• ACK খুব ছোট, তাই তার transmission time আর processing delay নগণ্য; কোনো ত্রুটি নেই।

প্রমাণ: সময় t = 0-তে প্রেরক প্রথম bit পাঠায়। T_trans-এ শেষ bit তারে নামে, T_trans + T_prop-এ সেটি প্রাপকের কাছে পৌঁছায়। প্রাপক সঙ্গে সঙ্গে ACK পাঠায়, যা আরও T_prop পরে প্রেরকের কাছে আসে। অর্থাৎ একটি frame-এর পুরো চক্র T_trans + 2T_prop, যার মধ্যে link কাজের ডেটা বহন করে শুধু T_trans সময়। তাই

এখানে U (link utilization বা efficiency) হলো মোট সময়ের কত ভাগ link নতুন ডেটা বহন করছে, আর throughput = U × R. সংখ্যা a-র একটি সুন্দর অর্থ আছে: link-এর ওপর একসাথে কতগুলো frame “ধরে” — R × T_prop হলো পথে থাকা bit (পর্ব ০৫-এর bandwidth-delay product-এর একমুখী রূপ), আর তাকে L দিয়ে ভাগ করলে a. a ছোট মানে link “খাটো” (frame তারের চেয়ে লম্বা), a বড় মানে link “লম্বা”।

সমাধান করা অঙ্ক

ত্রুটি থাকলে: U = (1 − p)/(1 + 2a)

এবার ধরুন প্রতিটি frame নষ্ট হওয়ার সম্ভাবনা p (ACK কখনো হারায় না), আর timeout ঠিক এক চক্রের সমান। প্রতিটি চেষ্টা স্বাধীনভাবে সফল হয় (1 − p) সম্ভাবনায়, তাই একটি frame পৌঁছাতে গড়ে কতবার পাঠাতে হয়, তা geometric distribution-এর গড়:

অঙ্ক ১-এ p = ০.০১ হলে U = ০.৯৯ ÷ ৩.৫ ≈ ২৮.৩%. এটি Stallings-এর পাঠ্যবইয়ের মডেল; বাস্তবে timeout এক চক্রের চেয়ে বড় রাখা হয়, ACK-ও হারাতে পারে, তাই আসল efficiency এর চেয়ে কিছুটা কম হয়। বিভিন্ন বই সামান্য আলাদা অনুমান করে (যেমন ACK-এর transmission time ধরা), তাই প্রশ্নে কোন অনুমান দেওয়া আছে তা মিলিয়ে নিন।

৫ · Sliding window আর Go-Back-N

উপগ্রহের উদাহরণে প্রেরক ৯৬% সময় বসে ছিল। সমাধান সহজ: ACK-এর অপেক্ষা না করে একসাথে কয়েকটি frame পাঠিয়ে দেওয়া — একে বলে pipelining (পর্ব ০৪-এর মতোই একসাথে অনেক টুকরো পথে রাখার বুদ্ধি)। কিন্তু সীমাহীন নয়: প্রেরক ACK ছাড়া সর্বোচ্চ W-টি frame পথে রাখতে পারে। এই W-টি নম্বরের জানালাকে বলে sliding window: সবচেয়ে পুরোনো frame-এর ACK এলে জানালা সামনে সরে (slide), আর নতুন একটি frame পাঠানোর অনুমতি মেলে।

Sequence number m bit-এর হলে নম্বর চলে 0 থেকে 2^m − 1, তারপর আবার 0 (modulo 2^m). কোনো frame হারালে কী হবে, তার দুটি নীতি — Go-Back-N আর Selective Repeat.

Go-Back-N-এর নিয়ম

• প্রাপক: window মাত্র ১ — শুধু ঠিক যে নম্বরটি আশা করছে সেটিই নেয়। ক্রমের বাইরের frame (আগেরটি হারানোয় পরে এসে গেছে) ঠিক থাকলেও ফেলে দেয়। প্রাপকের buffer-এর দরকার প্রায় নেই।
• ACK: cumulative ACK — “ACK k” মানে “k-এর আগের সব পেয়েছি, এবার k চাই”। ক্রমের বাইরের frame পেলে প্রাপক শেষ ACK-টিই আবার পাঠায়।
• প্রেরক: সবচেয়ে পুরোনো অস্বীকৃত frame-এর timeout হলে সেটি থেকে শুরু করে পরের সব পাঠানো frame আবার পাঠায় — “N ধাপ পিছিয়ে যাওয়া”।

নিচের Go-Back-N trace-এ W = ৪, ৮টি frame (0–7), আর frame 2-এর প্রথম কপি হারায়। সময়ের একক = একটি frame-এর transmission time; T_prop = ২, তাই t-তে পাঠানো frame পৌঁছায় t + ৩-এ, ACK ফেরে t + ৫-এ; timeout = পাঠানোর ৬ একক পর। (অংশ ৭-এর simulator ঠিক এই সংখ্যাগুলোই দেয়।)

কেন GBN-এ window ≤ 2^m − 1

ধরুন m = ২, নম্বর 0, 1, 2, 3, আর কেউ W = ৪ নিল। প্রেরক 0, 1, 2, 3 পাঠাল; প্রাপক চারটিই পেল, এখন আশা করছে পরের চক্রের 0. দুটি সম্ভাব্য ঘটনা:

• ঘটনা A: চারটি ACK-ই হারাল। প্রেরকের timeout, পুরোনো 0 আবার এলো।
• ঘটনা B: সব ACK পৌঁছেছে, প্রেরক নতুন চক্রের 0 পাঠাল।

দুই ক্ষেত্রেই প্রাপক দেখছে “seq 0” আর সে 0-ই চাইছে — পুরোনো আর নতুনকে আলাদা করার কোনো উপায় নেই। ঘটনা A-তে সে পুরোনো ডেটা নতুন ভেবে নেবে। W = ৩ হলে: প্রেরক 0, 1, 2 পাঠায়, প্রাপক আশা করে 3. ঘটনা A-তে পুরোনো 0 আসে (প্রাপক চায় 3 — বাতিল); ঘটনা B-তে নতুন 3 আসে। নম্বর আলাদা, তাই বিভ্রান্তি নেই। সাধারণভাবে: প্রাপক পরের যে নম্বর আশা করছে, তা প্রেরকের window-এর কোনো নম্বরের সাথে মিলে যাওয়া চলবে না। W-টি নম্বর আর পরের একটি — মোট W + 1টি আলাদা নম্বর লাগে, তাই W + 1 ≤ 2^m, অর্থাৎ W ≤ 2^m − 1.

৬ · Selective Repeat — শুধু যা হারিয়েছে

Go-Back-N-এর অপচয় চোখে পড়ার মতো: ঠিকঠাক পৌঁছানো 3, 4, 5 আবার পাঠাতে হলো। Link-এ ত্রুটি বেশি হলে বা window বড় হলে এই অপচয় অনেক বড়। Selective Repeat (SR) এর সমাধান:

• প্রাপক: নিজেরও W আকারের window রাখে। Window-এর ভেতরের যেকোনো ঠিক frame — ক্রমের বাইরে হলেও — buffer-এ রেখে দেয়। ফাঁক পূরণ হলে একসাথে ক্রম মেনে ওপরে দেয়।
• ACK: প্রতিটি frame-এর আলাদা ACK (ACK k = “frame k পেয়েছি”)। অনেক নকশায় প্রাপক ফাঁক দেখলে NAK পাঠিয়ে timeout-এর আগেই হারানো frame চেয়ে নেয়।
• প্রেরক: প্রতিটি frame-এর আলাদা timer; timeout হলে শুধু সেই frame আবার যায়।

একই পরিস্থিতি (W = ৪, frame 2 হারাল, NAK ছাড়া) এবার SR-এ:

কেন SR-এ window ≤ 2^m−1 — বিভ্রান্তির প্রমাণ

SR-এর প্রাপক একটি পুরো window গ্রহণ করে, তাই শর্তটি আরও কঠিন। আবার m = ২ (নম্বর 0–3), আর ধরুন W = ৩:

1. প্রেরক 0, 1, 2 পাঠাল। প্রাপক তিনটিই পেল, ACK দিল, আর তার window সরে গেল {3, 0, 1}-এ (পরের চক্রের নম্বর)।
2. তিনটি ACK-ই হারাল। প্রেরকের timeout — সে পুরোনো frame 0 আবার পাঠাল।
3. প্রাপকের window-এ 0 আছে! সে পুরোনো 0-কে পরের চক্রের নতুন 0 ভেবে গ্রহণ করল — ভুল ডেটা ওপরে যাবে।

W = ২ হলে: প্রেরক 0, 1; প্রাপকের নতুন window {2, 3}. পুরোনো 0 বা 1 আবার এলে তা window-এর বাইরে — প্রাপক চেনে এটি নকল, ফেলে দিয়ে ACK আবার পাঠায়। সাধারণ প্রমাণ: প্রাপক W-টি frame পেয়ে window সরালে তার নতুন window হয় [W, 2W − 1] (mod 2^m). প্রেরক তখনো পুরোনো [0, W − 1]-এর যেকোনোটি আবার পাঠাতে পারে। দুটি window-এর মোট 2W-টি নম্বর আলাদা না হলে বিভ্রান্তি — তাই 2W ≤ 2^m, অর্থাৎ W ≤ 2^m−1.

৭ · Sliding window-এর efficiency আর পরীক্ষার অঙ্ক

প্রমাণ: t = 0-তে প্রেরক টানা পাঠানো শুরু করে। প্রথম frame-এর ACK ফেরে T_trans + 2T_prop = (1 + 2a)T_trans সময়ে। এই সময়ের মধ্যে প্রেরক window-এর W-টি frame পাঠাতে পারে, যাতে লাগে W·T_trans.

• W ≥ 1 + 2a হলে প্রথম ACK আসার আগেই window ফুরায় না — ACK আসতেই থাকে, প্রেরক কখনো থামে না: U = 1.
• W < 1 + 2a হলে প্রতি (1 + 2a)T_trans চক্রে মাত্র W·T_trans সময় কাজ, বাকিটা অপেক্ষা: U = W/(1 + 2a).

ত্রুটি থাকলে (frame নষ্টের সম্ভাবনা p) Stallings-এর পাঠ্যবইয়ের মডেলে সূত্রগুলো এমন (ACK হারায় না ধরে, আর বই-ভেদে অনুমান সামান্য আলাদা হতে পারে):

SR-এর সূত্র সহজবোধ্য: প্রতিটি নষ্ট frame-এর জন্য শুধু একটি বাড়তি পাঠানো, তাই গড়ে ১/(১ − p) বার। GBN-এর হরে 2ap এসেছে কারণ প্রতিটি ত্রুটিতে প্রায় পুরো একটি round trip-এর frame (প্রায় 1 + 2a-টি) আবার পাঠাতে হয়। নিচের calculator সূত্রগুলো দিয়ে একটি টেবিল বানায়:

// Link utilization U (fraction of time the sender's link carries new, useful frames).
// a = Tprop / Ttrans, P = probability a frame is damaged (ACKs never lost) - Stallings' model.
const sw  = (a, P) => (1 - P) / (1 + 2 * a);
const sr  = (W, a, P) => W >= 2 * a + 1 ? 1 - P : W * (1 - P) / (2 * a + 1);
const gbn = (W, a, P) => W >= 2 * a + 1 ? (1 - P) / (1 + 2 * a * P)
                       : W * (1 - P) / ((2 * a + 1) * (1 - P + W * P));
const pct = u => ((100 * u).toFixed(1) + "%").padStart(8);
console.log("Error-free (P = 0):");
console.log("      a  1+2a |   S&W     W=7   W=127");
for (const a of [0.005, 0.1, 1.25, 12.5, 100])
  console.log(String(a).padStart(7) + String(1 + 2 * a).padStart(6) + " |" +
    pct(sw(a, 0)) + pct(sr(7, a, 0)) + pct(sr(127, a, 0)));
console.log("\nWith errors, P = 0.01 (1 frame in 100 damaged):");
console.log("      a |   S&W  GBN W=7  SR W=7 GBN W=127 SR W=127");
for (const a of [0.005, 1.25, 12.5, 100])
  console.log(String(a).padStart(7) + " |" + pct(sw(a, 0.01)) + pct(gbn(7, a, 0.01)) +
    pct(sr(7, a, 0.01)) + pct(gbn(127, a, 0.01)) + pct(sr(127, a, 0.01)));
// Example: 1000-byte frames, 1 Mbps, 2000 km of fiber (2e8 m/s)
const Tt = 8000 / 1e6, Tp = 2000e3 / 2e8, a = Tp / Tt;
console.log("\nTtrans=" + Tt * 1e3 + " ms  Tprop=" + Tp * 1e3 + " ms  a=" + a +
  "  S&W U=" + pct(sw(a, 0)).trim() + "  throughput=" + (sw(a, 0) * 1e3).toFixed(1) + " kbps");

Error-free (P = 0):
      a  1+2a |   S&W     W=7   W=127
  0.005  1.01 |   99.0%  100.0%  100.0%
    0.1   1.2 |   83.3%  100.0%  100.0%
   1.25   3.5 |   28.6%  100.0%  100.0%
   12.5    26 |    3.8%   26.9%  100.0%
    100   201 |    0.5%    3.5%   63.2%

With errors, P = 0.01 (1 frame in 100 damaged):
      a |   S&W  GBN W=7  SR W=7 GBN W=127 SR W=127
  0.005 |   98.0%   99.0%   99.0%   99.0%   99.0%
   1.25 |   28.3%   96.6%   99.0%   96.6%   99.0%
   12.5 |    3.8%   25.1%   26.7%   79.2%   99.0%
    100 |    0.5%    3.3%    3.4%   27.7%   62.6%

Ttrans=8 ms  Tprop=10 ms  a=1.25  S&W U=28.6%  throughput=285.7 kbps

পরীক্ষার ধাঁচের অঙ্ক — window আর sequence bit

এজন্যই HDLC-তে ৩ bit-এর সাধারণ নম্বরের পাশাপাশি ৭ bit-এর “extended” নম্বর (window ১২৭ পর্যন্ত) রাখা হয়েছিল — লম্বা উপগ্রহ link-এর জন্য।

Simulator — একই loss, তিন protocol

নিচের simulator অংশ ৫ আর ৬-এর সময়-হিসাব হুবহু চালায় (T_prop = ২ একক, timeout = ৬, ৮টি frame, ACK কখনো হারায় না), দুটি loss-এর নকশায়:

// Stop-and-wait vs Go-Back-N vs Selective Repeat on the same loss pattern. Time unit = one
// frame's transmission time. Tprop = 2: a frame sent at t arrives at t+3, its ACK is back at t+5.
const N = 8, P = 2, TO = 6;                          // frames, Tprop, timeout
function run(name, W, sr, lost) {
  const sentAt = [], acked = [], got = [], lossLeft = new Set(lost);
  let base = 0, next = 0, expect = 0, tx = 0, end = 0, log = [], ev = [], redo = [];
  for (let t = 0; base < N; t++) {
    for (const e of ev.filter(e => e.t === t)) {
      if (e.f !== undefined) {                       // a frame reaches the receiver
        if (sr || e.f === expect) got[e.f] = true;     // GBN keeps only the expected one
        while (got[expect]) expect++;
        ev.push({ t: t + P, a: sr ? e.f : expect });   // SR: ACK this frame; GBN: next expected
      } else if (sr) acked[e.a] = true;
      else for (let k = base; k < e.a; k++) acked[k] = true;
    }
    while (acked[base]) base++;
    if (base === N) { end = t; break; }
    for (let k = base; k < next; k++)                 // timeouts
      if (!acked[k] && sentAt[k] + TO === t) {
        log.push("t=" + t + " timeout " + k);
        if (sr) redo.push(k); else { next = k; break; }
      }
    const f = redo.length ? redo.shift() : (next < base + W && next < N ? next++ : -1);
    if (f < 0) continue; sentAt[f] = t; tx++;
    if (lossLeft.delete(f)) log.push("t=" + t + " send " + f + " LOST");
    else ev.push({ t: t + 1 + P, f });
  }
  console.log(name.padEnd(16) + "transmissions=" + tx + "  done at t=" + end + "  | " + log.join(", "));
}
for (const lost of [[2], [2, 6]]) {
  console.log("Lost first copy of frame(s): " + lost.join(", "));
  run("Stop-and-wait", 1, false, lost);
  run("Go-Back-N W=4", 4, false, lost);
  run("Sel. Repeat W=4", 4, true, lost);
}

Lost first copy of frame(s): 2
Stop-and-wait   transmissions=9  done at t=46  | t=10 send 2 LOST, t=16 timeout 2
Go-Back-N W=4   transmissions=12  done at t=19  | t=2 send 2 LOST, t=8 timeout 2
Sel. Repeat W=4 transmissions=9  done at t=19  | t=2 send 2 LOST, t=8 timeout 2
Lost first copy of frame(s): 2, 6
Stop-and-wait   transmissions=10  done at t=52  | t=10 send 2 LOST, t=16 timeout 2, t=36 send 6 LOST, t=42 timeout 6
Go-Back-N W=4   transmissions=14  done at t=25  | t=2 send 2 LOST, t=8 timeout 2, t=13 send 6 LOST, t=19 timeout 6
Sel. Repeat W=4 transmissions=10  done at t=24  | t=2 send 2 LOST, t=8 timeout 2, t=13 send 6 LOST, t=19 timeout 6

Piggybacking — ACK-কে ডেটার পিঠে চড়ানো

এতক্ষণ ডেটা চলেছে এক দিকে। বাস্তবে দুই দিকেই চলে (full-duplex). তখন প্রাপক আলাদা ছোট ACK frame না পাঠিয়ে তার নিজের ডেটা frame-এর header-এ একটি “ack” ঘর রেখে দেয় — একে বলে piggybacking. ঢাকা–রাজশাহী রুটের বাস ফেরার পথে খালি না গিয়ে ফিরতি মাল নিয়ে যায়, আর সাথে আগের চালানের রসিদও। লাভ: আলাদা ACK frame-এর header, FCS আর frame-এর মাঝের ফাঁক বাঁচে। ঝুঁকি: ফিরতি ডেটা না থাকলে ACK আটকে থাকবে — তাই একটি ছোট timer রাখা হয়; সময়মতো ডেটা না এলে আলাদা ACK চলে যায়। HDLC-র I-frame-এ পাঠানো আর গ্রহণ — দুটি নম্বরই থাকে, আর TCP-র প্রতিটি segment-এ ACK ঘর থাকে — দুটোই piggybacking-এর উদাহরণ।

৮ · বাস্তবের protocol — HDLC, PPP, Ethernet আর Wi-Fi

HDLC — পাঠ্যবইয়ের ধারণার বাস্তব রূপ

HDLC-র frame দেখতে এমন (ঘরের মাপ bit-এ; ঠিকানা আর control ঘর বাড়ানো যায়):

┌──────────┬─────────┬─────────┬──────────────────┬──────────┬──────────┐
│   Flag   │ Address │ Control │   Information    │   FCS    │   Flag   │
│ 01111110 │    8    │ 8 / 16  │     variable     │ 16 / 32  │ 01111110 │
└──────────┴─────────┴─────────┴──────────────────┴──────────┴──────────┘

• তিন ধরনের frame: I-frame (ডেটা, ভেতরে N(S) = নিজের নম্বর আর N(R) = piggyback করা ACK), S-frame (supervisory — RR “পাঠাতে থাকুন”, RNR “থামুন” অর্থাৎ flow control, REJ = Go-Back-N ধাঁচের আবার পাঠানোর অনুরোধ, SREJ = Selective Repeat ধাঁচের), আর U-frame (unnumbered — সংযোগ স্থাপন, বিচ্ছিন্ন করা ইত্যাদি)।
• নম্বর: সাধারণত ৩ bit (modulo ৮), extended রূপে ৭ bit (modulo ১২৮)।
• তিন mode: NRM (normal response — primary স্টেশন অনুমতি দিলে তবেই secondary পাঠায়, পুরোনো mainframe-terminal লাইনের মতো), ARM (asynchronous response — secondary নিজে থেকে পাঠাতে পারে, কিন্তু নিয়ন্ত্রণ primary-র; খুব কম ব্যবহৃত), আর ABM (asynchronous balanced — দুই প্রান্ত সমান, যে কেউ যেকোনো সময় পাঠায়; point-to-point link-এ সবচেয়ে প্রচলিত)।

PPP আর PPPoE

PPP (RFC 1661) দুই যন্ত্রের সরাসরি link-এর জন্য — একসময় dial-up modem, এখনো কিছু WAN link. এর framing HDLC-ধাঁচের (flag 0x7E, অংশ ২-এর byte stuffing), কিন্তু সাধারণ ব্যবহারে এটি numbered ARQ চালায় না: নষ্ট frame ফেলে দেয়, আবার পাঠানোর দায় ওপরের TCP-র। PPP-র আসল শক্তি অন্যখানে — LCP দিয়ে link-এর শর্ত ঠিক করা, PAP/CHAP দিয়ে ব্যবহারকারী যাচাই, আর NCP (যেমন IPCP) দিয়ে IP ঠিকানা দেওয়া।

এই সুবিধাগুলোর জন্যই PPPoE (RFC 2516) এসেছে: Ethernet-এর ওপর PPP session. বাংলাদেশসহ বহু দেশের অনেক broadband ISP বাড়ির router-এ PPPoE-র username আর password বসিয়ে সংযোগ দেয় — router-এর সেটিংসে “WAN type: PPPoE” দেখে থাকতে পারেন (সব ISP এভাবে করে না; কেউ সরাসরি DHCP বা static IP দেয়)। PPPoE-তে framing-এর কাজ Ethernet করে, তাই byte stuffing লাগে না; তবে PPPoE-র ৮ byte header-এর জন্য IP-র MTU সাধারণত ১,৪৯২ byte-এ নেমে আসে।

Ethernet আবার পাঠায় না — কেন?

তারের Ethernet ACK-ছাড়া সেবা দেয়: FCS না মিললে frame চুপচাপ ফেলে দেয়, প্রেরক জানতেও পারে না। কারণ দুটি। প্রথমত আধুনিক তামার তার আর fiber-এ bit-ত্রুটি অত্যন্ত বিরল — প্রতিটি frame-এ ACK, timer আর buffer-এর খরচ সেই বিরল ত্রুটির তুলনায় অনেক বেশি। দ্বিতীয়ত ওপরে TCP পুরো পথের জন্য নিজেই নির্ভরযোগ্যতা দেয় (পর্ব ৩০)। Link-এ আবার পাঠালে সেই কাজটি দুবার হতো। (পুরোনো half-duplex Ethernet সংঘর্ষ হলে frame আবার পাঠাত — কিন্তু সেটি সংঘর্ষ শনাক্ত করে, ACK দিয়ে নয়; পর্ব ১১।)

Wi-Fi আবার পাঠায় — কেন?

বেতার চ্যানেলে চিত্র উল্টো: দেয়াল, দূরত্ব, মাইক্রোওয়েভ ওভেন, পাশের ফ্ল্যাটের router — ত্রুটি আর সংঘর্ষ খুব সাধারণ। 802.11-এ প্রতিটি unicast ডেটা frame পৌঁছালে প্রাপক খুব ছোট একটি বিরতির (SIFS) পর ACK পাঠায়; ACK না এলে প্রেরক নির্দিষ্ট সীমা পর্যন্ত কয়েকবার আবার চেষ্টা করে — মূলত stop-and-wait. আধুনিক 802.11n/ac/ax-এ অনেক frame একসাথে জুড়ে পাঠিয়ে একটি “block ACK” দিয়ে কোনগুলো পৌঁছেছে জানানো হয় — selective repeat-এর ধাঁচ। কেন TCP-র ওপর ছেড়ে দেওয়া হয় না? কারণ TCP-র timeout অনেক লম্বা (পুরো পথের RTT), আর TCP প্রতিটি loss-কে নেটওয়ার্কের ভিড় ভেবে গতি কমিয়ে দেয় (পর্ব ৩২)। এক hop-এ মিলিসেকেন্ডের কম সময়ে আবার পাঠিয়ে Wi-Fi সেই ভুল সংকেত এড়ায় (পর্ব ১৪)।

৯ · AI-এর যুগে ARQ-এর অঙ্ক আর protocol-এর তথ্য

“Stop-and-wait efficiency, 2 km, 10 Mbps…” AI-কে দিলে চকচকে সমাধান আসবে। কিন্তু এই বিষয়ের অঙ্কে AI-এর ভুলগুলোর ধরন চেনা — বেশিরভাগই সূত্রের রীতি আর অনুমানে, যা আত্মবিশ্বাসী ভাষায় ঢাকা পড়ে।

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

• a-র সংজ্ঞা T_prop/T_trans কি না, আর সূত্রে ২-এর গুণ আছে কি না দেখেছি
• Window-এর সীমা protocol-ভেদে ঠিক আছে কি না মিলিয়েছি: GBN 2^m − 1, SR 2^m−1
• অন্তত একটি সংখ্যা উপরের calculator বা হাতের ক্যালকুলেটরে নিজে আবার হিসাব করেছি
• Stuffing বা trace-এর প্রশ্নে encoder/simulator চালিয়ে উত্তর মিলিয়েছি
• RFC নম্বর আর protocol-এর আচরণ (কোন link ACK দেয়, কোনটি দেয় না) মূল উৎসে যাচাই করেছি; পরীক্ষা নিজের ল্যাব বা VM-এ করেছি, অন্যের নেটওয়ার্কে নয়