Formula Sheets: Networking Fundamentals & Physical Layer | Computer Networks - Computer Science Engineering (CSE) PDF Download

 Page 1


Net w orking F undamen tals & Ph ysical La y er F orm ula Sheet
Net w ork T op ologies
• Star T op ology : All no des connect to a cen tral h ub. Single p oin t of failure at h ub.
• Bus T op ology : All no des share a common comm unication medium. Collision probabilit y: P
collision
?
n um b er of no des.
• Ring T op ology : Eac h no de connects to exactly t w o others, forming a closed lo op. Data trans-
mission dela y: T
ring
=N·T
no de
, where N is the n um b er of no des, T
no de
is p er-no de dela y .
• Mesh T op ology :
– F ull Mesh: Num b er of links =
N(N-1)
2
, where N is the n um b er of no des.
– P artial Mesh: F ew er links, connectivit y dep ends on sp ecific links.
• T ree T op ology : Hierarc hical structure, ro ot-to-leaf dela y dep ends on tree heigh t h .
La y ering Mo dels
• OSI Mo del : 7 la y ers (Ph ysical, Data Link, Net w ork, T ransp ort, Session, Presen tation, Applica-
tion).
• TCP/IP Mo del : 4 la y ers (Link, In ternet, T ransp ort, Application).
• Encapsulation : Data at la y er n is encapsulated with a header at la y er n-1 .
Ph ysical La y er: T ransmission Media
• Guided Media :
– T wisted P air: A tten uation (dB/km) dep ends on frequency and cable qualit y .
– Coaxial Cable: Higher bandwidth, atten uation?
v
f , where f is frequency .
– Optical Fib er: A tten uation˜ 0.2-0.5 dB/km, bandwidth ˜ 10-100 Gbps.
• Unguided Media :
– F ree Space P ath Loss: L
FSPL
= 20log
10
(d)+20log
10
(f)+20log
10
(
4p
c
)
, where d is distance
(m), f is frequency (Hz), c is sp eed of ligh t (3×10
8
m/s).
T ransmission Mo des
• Simplex : One-w a y comm unication.
• Half-Duplex : T w o-w a y , one direction at a time. T urnaround tim e affects throughput.
• F ull-Duplex : T w o-w a y sim ultaneous. Effectiv e bandwidth = 2× single direction bandwidth.
Flo w Con trol (Link La y er)
• Stop-and-W ait :
– Throughput: S =
L
RTT+T trans
, where L is frame size, RTT is round-trip time, T
trans
=
L
R
, R
is data rate.
– E?iciency: ? =
1
1+2a
, where a =
T prop
T trans
, T
prop
is propagation dela y .
• Sliding Windo w :
– Windo w size: W = 2
n
-1 (for n -bit sequence n um b ers in Selectiv e Rep eat).
– E?iciency: ? = min
(
1,
W
1+2a
)
.
1
Page 2


Net w orking F undamen tals & Ph ysical La y er F orm ula Sheet
Net w ork T op ologies
• Star T op ology : All no des connect to a cen tral h ub. Single p oin t of failure at h ub.
• Bus T op ology : All no des share a common comm unication medium. Collision probabilit y: P
collision
?
n um b er of no des.
• Ring T op ology : Eac h no de connects to exactly t w o others, forming a closed lo op. Data trans-
mission dela y: T
ring
=N·T
no de
, where N is the n um b er of no des, T
no de
is p er-no de dela y .
• Mesh T op ology :
– F ull Mesh: Num b er of links =
N(N-1)
2
, where N is the n um b er of no des.
– P artial Mesh: F ew er links, connectivit y dep ends on sp ecific links.
• T ree T op ology : Hierarc hical structure, ro ot-to-leaf dela y dep ends on tree heigh t h .
La y ering Mo dels
• OSI Mo del : 7 la y ers (Ph ysical, Data Link, Net w ork, T ransp ort, Session, Presen tation, Applica-
tion).
• TCP/IP Mo del : 4 la y ers (Link, In ternet, T ransp ort, Application).
• Encapsulation : Data at la y er n is encapsulated with a header at la y er n-1 .
Ph ysical La y er: T ransmission Media
• Guided Media :
– T wisted P air: A tten uation (dB/km) dep ends on frequency and cable qualit y .
– Coaxial Cable: Higher bandwidth, atten uation?
v
f , where f is frequency .
– Optical Fib er: A tten uation˜ 0.2-0.5 dB/km, bandwidth ˜ 10-100 Gbps.
• Unguided Media :
– F ree Space P ath Loss: L
FSPL
= 20log
10
(d)+20log
10
(f)+20log
10
(
4p
c
)
, where d is distance
(m), f is frequency (Hz), c is sp eed of ligh t (3×10
8
m/s).
T ransmission Mo des
• Simplex : One-w a y comm unication.
• Half-Duplex : T w o-w a y , one direction at a time. T urnaround tim e affects throughput.
• F ull-Duplex : T w o-w a y sim ultaneous. Effectiv e bandwidth = 2× single direction bandwidth.
Flo w Con trol (Link La y er)
• Stop-and-W ait :
– Throughput: S =
L
RTT+T trans
, where L is frame size, RTT is round-trip time, T
trans
=
L
R
, R
is data rate.
– E?iciency: ? =
1
1+2a
, where a =
T prop
T trans
, T
prop
is propagation dela y .
• Sliding Windo w :
– Windo w size: W = 2
n
-1 (for n -bit sequence n um b ers in Selectiv e Rep eat).
– E?iciency: ? = min
(
1,
W
1+2a
)
.
1
Error Detection and Correction
• P arit y Chec k : Detects single-bit errors. Error detection probabilit y: P
detect
= 1 for o dd n um b er
of errors.
• Cyclic Redundancy Chec k (CR C) :
– Generator p olynomial degree k : Detects all burst errors of length =k .
– Error detection probabilit y: P
detect
= 1-
1
2
k
.
• Hamming Co de :
– Num b er of parit y bits: r , where 2
r
=m+r+1 , m is data bits.
– Hamming distance: d
min
= 3 (corrects 1-bit errors).
– Error correction capabilit y: t =?
d min-1
2
? .
Switc h ing T ec hniques
• Circuit Switc hing : Setup time T
setup
, dedicated bandwidth B .
• P ac k et Switc hing :
– Store-and-F orw ard Dela y: T
total
=
?
h
i=1
(
L
Ri
+T
prop
i
)
, where h is n um b er of hops, R
i
is link
rate, T
prop
i
is propagation dela y .
• Message Switc hing : Similar to pac k et switc hing but en tire message is transmitted as a unit.
Net w ork P erformance P arameters
• Bandwidth : Maxim um data rate (bps).
• Throughput : S =
data transferred
time
, t ypically S = Bandwidth.
• Latency : T
latency
=T
prop
+T
trans
+T
queue
+T
pro c
.
• Jitter : s
dela y
=
v
1
n
?
n
i=1
(d
i
-
¯
d)
2
, where d
i
is dela y of pac k et i ,
¯
d is mean dela y .
• Bit Error Rate (BER) : P
error
=
n um b er of err ored bits
total bits transmitted
.
F raming
• Fixed-Length F rames : F rame size = L bits.
• V ariable-Length F rames :
– Bit Stu?ing: Insert a 0 after fiv e consecutiv e 1s.
– Byte Stu?ing: Escap e c haracter (e.g., FLA G = 0x7E, ESC = 0x7D).
Net w ork Proto cols
• MA C Proto cols :
– CSMA/CD: Collision probabilit y P
coll
?
1
1+2a
.
– CSMA/CA: Uses R TS/CTS to reduce collisions.
• AR Q Proto cols :
– Stop-and-W ait AR Q: E?iciency ? =
1-P error
1+2a
.
– Go-Bac k-N AR Q: E?iciency ? =
1-P error
1+2a·P error
.
– Selectiv e Rep eat AR Q: E?iciency ?˜ 1-P
error
(for large windo w).
2