Link framing, errors, medium access और bridging
लक्ष्य और assumptions
Bit stream में frames पहचानें, error-detection codes निकालें, shared medium पर access समझें और learning bridge trace करें। पूर्वज्ञान: XOR, binary polynomials और पाठ 02 के transmission/propagation delays। छोटे CRC हाथ से गणना के लिए हैं; इनका bit order और initial state सरल है, वास्तविक Ethernet FCS implementation नहीं। अन्य निर्देश न हों तो bridge में एक VLAN, active forwarding ports, कोई security filter और कोई stale entry नहीं है।
1. Frame boundaries पहचानना
Receiver को boundary तथा payload और control delimiter अलग करने का तरीका चाहिए। Length field count देती है, पर count खराब हो तो आगे की interpretation misalign हो सकती है। Delimiter scheme flag reserve करके payload में उसकी occurrence escape करती है। Byte stuffing में protocol के अनुसार reserved payload byte से पहले escape byte आता है या उसका रूप बदलता है। Receiver उल्टा नियम लागू करता है। Stuffing transparency है, compression या error correction नहीं।
HDLC-style bit-oriented उदाहरण में flag 01111110 है। Flags के बीच sender हर पाँच लगातार ones के बाद zero डालता है; receiver वह inserted zero हटाता है। Flags स्वयं stuffed नहीं होते। हल: payload 01111110, flags के बीच 011111010 बनता है: पहला 0, पाँच ones, inserted 0, बचा 1, अंतिम 0। दस लगातार payload ones से 111110111110 बनता है, यानी दो insertions। Byte boundary पर run counting reset नहीं करें। Stuffing transmitted length और transmission time बढ़ाती है।
2. Parity और checksum
Even-parity bit कुल ones की संख्या सम बनाती है। Data 1011001 में चार ones हैं, इसलिए parity 0 जोड़ें। विषम संख्या में bit flips parity बदलते हैं और detect होते हैं; सम संख्या के flips parity अपरिवर्तित रख सकते हैं। Detection से खराब bit की जगह या सुधार अपने आप नहीं मिलता।
Internet checksum में 16-bit words को one's-complement addition से जोड़कर परिणाम का bitwise complement लेते हैं। 16 bits से बाहर carry को low end में फिर जोड़ें; जरूरत हो तो दोहराएँ। उदाहरण: 0xF234+0x2345=0x11579; carry fold से 0x157A; complement=0xEA85। Data और checksum जोड़कर carry fold करने पर 0xFFFF आता है। Checksum pass होना केवल यह बताता है कि error detect नहीं हुआ, यह सही data का प्रमाण नहीं है। कुछ compensating changes एक-दूसरे को cancel कर देती हैं। यह additive checksum, XOR polynomial division से अलग है; दोनों sender authentication नहीं देते।
3. CRC की गणना और guarantees
Bits को GF(2) polynomial coefficients मानें। Addition/subtraction XOR हैं, carry नहीं। Degree-r generator G के leading और constant coefficients 1 लें। Data D के बाद r zeros लगाएँ; D×x^r को G से divide करके r-bit remainder R निकालें। भेजें T=D×x^r XOR R। सरल zero-initialized convention में T, G से पूरा divide होता है। Receiver उसी G से divide करता है; nonzero remainder error detect करता है।
हल: D=1101, G=1011, degree=3। शुरुआत 1101000 से करें। Aligned 1011000 XOR करने पर 0110000; फिर 0101100 XOR करने पर 0011100; फिर 0010110 XOR करने पर 0001010; अंत में 0001011 XOR करके remainder 001 मिलता है। Transmitted codeword=1101001, जो 1011 से divisible है। Generator में चार bits होने का अर्थ चार zeros जोड़ना नहीं; degree तीन है।
Error polynomial E हो तो error तभी छूटता है जब G, E को divide करे। Degree-r और constant term 1 वाला generator हर length≤r burst detect करता है। Burst length पहले बदले bit से आखिरी बदले bit तक है, बीच के अपरिवर्तित bits भी गिने जाते हैं। G में x+1 factor हो तो सभी odd-weight error patterns detect होते हैं। 1011 के लिए G(1)=1 modulo 2, इसलिए यह odd-weight guarantee नहीं देता। E=1011 स्वयं undetected three-bit error है। हर CRC हर error detect नहीं करता; zero remainder data सही होने का प्रमाण नहीं। Recovery के लिए retransmission या correction अलग चाहिए।
4. Medium access: कौन transmit करे?
Shared medium पर competing stations के लिए नियम चाहिए। Channel partitioning time/frequency बाँटती है; polling और token passing बारी तय करते हैं; random access में stations कोशिश करते और collisions से recover करते हैं। Reserved खाली turns capacity खो सकती हैं; contention में collisions काम बेकार कर सकती हैं। बेहतर विकल्प traffic और overhead पर निर्भर है।
Ideal Poisson attempts और समान frame length के model में pure ALOHA का vulnerable interval 2T और normalized throughput S=G exp(-2G) है। G=1/2 पर maximum 1/(2e) मिलता है। Slotted ALOHA starts synchronize करती है: vulnerable interval T, S=G exp(-G), maximum 1/e जब G=1। G प्रति frame time सभी attempts, retries सहित, गिनता है; S successful frames गिनता है। ये model के परिणाम हैं, Ethernet efficiency के universal formulas नहीं। G=0.5 पर slotted S≈0.3033 और pure S≈0.1839 है।
CSMA भेजने से पहले सुनती है, पर दूर का signal अभी नहीं पहुँचा हो सकता है; sensing collisions पूरी तरह नहीं हटाती। Classic half-duplex Ethernet में CSMA/CD transmission के दौरान collision detect करके attempt रोकता और binary exponential backoff के बाद retry करता है। Collision number n के बाद classic backoff integer 0 से 2^min(n,10)−1 तक uniformly चुनता है, delay उतने slot times होता है। तीसरी collision पर choices 0…7 और mean 3.5 slots हैं। चुना delay collision-free reservation की guarantee नहीं।
Ideal two-endpoint bound में worst-case collision वापस आने तक sender transmit करता रहना चाहिए: L/R≥2τ, यानी L≥2Rτ। R=10 Mb/s और one-way τ=20 microseconds हों तो L≥400 bits=50 bytes। यह केवल propagation वाला गणितीय bound है, Ethernet के standardized minimum frame size का विकल्प नहीं; असली timing allowances और भी हैं। सामान्य switched full-duplex Ethernet के point-to-point link में shared collision domain नहीं और CSMA/CD उपयोग नहीं होता। Wireless collision avoidance random backoff और acknowledgments जैसी coordination लेती है; इससे collisions असंभव नहीं हो जातीं।
5. Ethernet learning bridges
Transparent bridge accepted frame के source MAC और ingress port से सीखता है। Destination MAC lookup से action तय होता है। Known unicast दूसरे port पर हो तो केवल वहीं forward; destination ingress port पर हो तो filter; unknown unicast हो तो ingress छोड़कर eligible ports पर flood। Broadcast भी उसी broadcast domain में flood होता है। Source सीखना और destination ढूँढना अलग काम हैं। Entries age out होती हैं ताकि बदलाव relearn हो सकें।
खाली table वाला तीन-port bridge लें: A port 1, B port 2 और C port 3 पर। Port 1 पर A→B आने से A→1 सीखता है। B unknown है, इसलिए ports 2 और 3 पर copies भेजता है। Port 2 पर B→A से B→2 सीखता है; A known होने से केवल port 1 पर भेजता है। अगला A→B केवल port 2 उपयोग करता है। अगर D भी hub से port 1 साझा करे और D→1 पहले learned हो, तो A→D frame उसी segment पर वापस भेजने की बजाय filter होगा।
Bridges collision domains अलग करते हैं, पर VLAN/routing boundary न हो तो broadcast domain नहीं बाँटते। Redundant physical links loop बना सकते हैं: flooded frames घूमती रहें और MAC learning बदलती रहे। Ethernet frame में IP जैसा hop limit नहीं होता। Spanning-tree mechanisms कुछ redundant paths block करके loop-free active topology चुनते हैं; हर अतिरिक्त cable हटाना जरूरी नहीं। प्रश्न में forwarding/learning states दिए हों तो उन्हें लागू करें।
हल और जाँच
Overhead गिनने से पहले framing rule पहचानें। CRC में generator degree और XOR लें तथा final codeword का remainder जाँचें। Access formula के traffic/duplex assumptions स्पष्ट करें। Bridge trace में पहले source entry update करें, फिर forwarding, flooding और filtering अलग करें। Collision domain को broadcast domain न मानें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. हर पाँच लगातार payload ones के बाद zero डालने पर दस लगातार ones में कितने zeros जुड़ेंगे?
A. 0 B. 1 C. 2 D. 3
उत्तर: C
A: नियम दोनों runs पर लागू है।
B: पाँच के दो runs हैं, एक नहीं।
C: 111110111110 में दो inserted zeros हैं।
D: पाँच के केवल दो समूह हैं।
P02. Data 1101, generator 1011 तथा सरल zero-initialized CRC rule में कौन सा codeword भेजेंगे?
A. 1101000 B. 1101001 C. 1101101 D. 1101011
उत्तर: B
A: यह remainder लगाने की जगह zeros रखता है।
B: तीन-bit remainder 001 है; 1101 के बाद 001 जोड़ें।
C: 101 सही remainder नहीं।
D: Generator का tail जोड़ना polynomial division नहीं।
P03. एक even-parity check किस error pattern को हमेशा detect करता है?
A. कोई भी दो bit flips B. कोई भी nonzero संख्या में flips C. कोई भी चार bit flips D. कोई भी विषम संख्या में bit flips
उत्तर: D
A: दो flips parity बनाए रखते हैं।
B: Even-weight बदलाव छूट सकते हैं।
C: चार flips parity बनाए रखते हैं।
D: विषम flips parity बदलते हैं।
P04. Ideal collision-detection model में R=20 Mb/s और one-way propagation 10 microseconds है। L/R≥2τ से न्यूनतम length?
A. 200 bits B. 400 bytes C. 400 bits D. 20 bits
उत्तर: C
A: यह round trip की जगह one-way time है।
B: गणना bits देती है, bytes नहीं।
C: 2×20×10^6×10×10^-6=400 bits।
D: इसमें दी rate और round-trip factor छूटे।
P05. शुरू में खाली three-port bridge को port 1 पर A→B मिलता है। एक VLAN में सभी ports forwarding हैं। क्या करेगा?
A. A→1 सीखकर ports 2 और 3 पर flood B. B→1 सीखकर केवल port 2 पर forward C. A→1 सीखकर केवल port 1 पर वापस भेजे D. B unknown होने से drop
उत्तर: A
A: Source सीखकर unknown destination को ingress छोड़कर flood करता है।
B: Source A से सीखता है; B का port अभी ज्ञात नहीं।
C: Flooding ingress port छोड़ती है।
D: बताए सामान्य bridge model में unknown unicast flood होता है।
P06. Ideal slotted-ALOHA model S=G exp(-G) में maximum normalized throughput क्या है?
A. 1/(2e), जब G=1/2 B. 1/e, जब G=1 C. 1, जब G=1 D. G के साथ असीम बढ़ता है
उत्तर: B
A: यह pure ALOHA का maximum है।
B: Derivative exp(-G)(1-G), G=1 पर zero होकर maximum देता है।
C: Collisions से केवल exp(-1) successful frames प्रति frame time मिलते हैं।
D: बहुत attempts पर collisions throughput घटाते हैं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Computer Networks syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन