Rough notes from the time I was learning (self-taught) about Computer Networks.

Some common algorithms

RSA Algorithm
Named after the three MIT scholars (Rivest, Shamir, Adleman) who discovered it.
Steps:

• Select primes p and q.
  
• Calculate n = pq and Euler’s totient ϕ(n) = (p - 1)(q - 1).
  
• Find public exponent ‘e’ such that gcd(e, ϕ(n)) = 1.
  
• Encryption: Ciphertext is given by c = p^emod(n).
  
• Find private exponent ‘d’ such that ed = 1mod(ϕ(n)).
  
• Decryption: Plaintext is given by p = c^dmod(n).
  
• For details, check out my repository.
  

Carrier-sense multiple access with collision detection (CSMA/CD)
Steps:

• Following the fact that the station has frames to send, it initializes k to zero.
• Applies one persistent method (zero persistence/non-persistence/p-persistence or probability-based persistence)
• Transmission is done if the ‘Transmit and receive’ phase occurs.
• If found to be true upon checking, it follows the collision detection phase, else it’s a success (i.e., a collision is detected!)
• If true (i.e., if detected), it sends a jamming signal and increments k by one.
• If k > k_max = 15, then we halt.
• If false, then we choose a random number between 0 to 2^{(k - 1)}.
• Wait for T(b) time and then go to the second step (after k = 0) and repeat from there on.

Distance Vector Routing (DVR) Algorithm
Steps:

• Each router prepares its own routing table.
• Information about all routers in the network and the distance between each is known.
• Each router calculates its distance vector.
• Exchanges it with other routers.
• Repeats (n - 2) times for ‘n’ routers.
• After this, the routing tables converge and become stable.
• For example, say there are four routers: (a, b, c, d)
  => All distance vectors are calculated.
  => Say ‘a’ can be reached from b and d => new a or ‘A’ = min(b(A->B), d(A->B)).
  => (Minimum of cost of reaching router b from a via b) < (b from a via d), and so on.
  
• Suffers from the count to infinity problem.
• Uses UDP at the transport layer.
• Different from Link State Routing.

Flow Control Protocols

Check this branch for implementations of these protocols in code.

Stop and Wait:

• Sender sends the frame and the receiver sends the acknowledgment.
  
• Only works for perfect protocols.
  
• Main disadvantage: Only one frame is sent.
• Other Disadvantages: Slow, low throughput and efficiency, end-to-end delay, high packet loss probability.
  
• Not to mention, if the data is lost then it waits infinitely!
  

+Automatic Repeat Request (ARQ)
We repeat the request till acknowledgment comes within a stipulated or given time frame.

Go-back N-ARQ

• Sender window size, n = 2ⁿ - 1.
  
• Reciever window size = 1 (recieves one frame at a time, a drawback).
  
• No out of order frames are accepted.
  
• Receiver acknowledges each frame either independently or together.
  
• Sends NACK (negative acknowledgement) for corrupted frames.
  
• Re-transmits whole frame for even a single corruption. (Hence ‘Go-Back’ N-ARQ)
  
• Disadvantage: Receiver window size = 1 (acts as stop and wait if m = 1, i.e. when the sender window size is one).
  

Selective Repeat:

• Sender window size = Reciever window size = 2^{(n - 1)}.
  
• Reciever acknowledges each frame independently.
  
• Sends NACK for corrupted frames.
  
• Selectively sends the damaged frames. (and that’s why its called ‘selective repeat’)
  
• Sorts at the receiver’s end.
  
• Disadvantages: Needs sorting (link-list based??), acknowledgements are sent all the time.
  

Access Control

Channelization: Multiple access method where the bandwidth of a link is shared between other links.
FDMA

• Bandwidth might not be fully utilized here.
• Each user can independently and concurrently use it.
• Does not overlap frequencies.

TDMA

• Full bandwidth utilization.
• There are time slots for each user.
• Not independent and concurrent (does not overlap time).

CDMA

• Best of TDMA + FDMA.
• All users have their own code (independent).

Error Control

Cyclic Redundancy Check (CRC): Given binary (0/1) data, we can divide it with a smaller polynomial represented by 1/0 in order of the degrees of the polynomial variable (Eg: x² + 1 = 101) wherein we add zeroes equal to no. of bits in polynomial minus one, and then we divide our data via our binary encoded polynomial and attach the result in place of those zeroes. To cross-check or verify our correctness, we should obtain the division of our newly obtained result by our polynomial to be zero.
Checksum: Data unit divided into segments of n bits, added, 1’s complement taken -> if 0 then no error persists.
Parity Check: Check for odd or even no. of 1s in result, after adding 1/0 to the last bit of the original polynomial.

Basics

Casting

• Unicast - One host to another.
• Multicast - One to many.
• Broadcast - One to all.
  Limited Broadcast Address (LBA) = 255*4 for Ipv4, 4 octets of 1. (send to all others in the same network)
  Direct Broadcast Address (DBA) = NID.255*HID. (in other network)
  Eg : 20.1.3.5 => Class A => 20.255*3 (all of the last three octets have 1s)
  

Classless Inter-domain routing (CIDR)

• For a specific IP, or a set of IPs.
• Block size is a power of 2.
• First IP is divisible by the block length/size.
• Subnet mask (variable length) is NID, HID = 32 - NID.

Switching types

• Circuit
  
  • Dedicated communication path.
  • Needs an established circuit.
  • B/W wastage is there.
• Message
  
  • No physical connection.
  • Follows the store and forward technique.
  • B/W is used more efficiently.
  • There is no priority.
• Packet
  
  • No physical connection.
  • Internet uses this.
  • Priority is there.
  • No B/W wastage.

Quanitzation
Digitalization of an analog signal by rounding approximate values from analog points. With sampling done, it chooses a few points on the signal and rounds them off to a near-stabilized value.

• Advantages: Low noise (high SNR), Long distance, Data storage.
• Disadvantages: High B/W required, Attenuation.
• Applications: Telecom systems, Audio-recording, Special effects in videos.

PAM
An analog modulating signal scheme in which the amplitude of the pulse carrier varies proportionally to the instantaneous amplitude of the message signal. We can reconstruct it (natural pam; signal at Nyquist rate-noisy) by passing through a low pass filter at cut-off frequency.

Noise types

• Thermal noise (N = KTB formula applicable)
• Impulse noise
• Intermodulation
• Crosstalk (reduced by twisting of wires as done in twisted pair cables)

MAC address

• Identifies the physical address of a computer.
• Manufacturer of NIC (Network ID card) maintains it.
• Mac address is 6 bytes.

IP address

• Identifies connection of a computer on the internet.
• ISP/network administrator (local) assigns the address, which is a 32/128-bit (IPv4/IPv6) number. (taken as a string or character array in code)
  

ISO: International organization for standardization (org.)
OSI: Open systems Interconnection (model)
Piggybacking: Technique of temporarily delaying acknowledgement so it can be hooked to next outgoing frame.
Machester: RZ + NRZ - L | Differential Manchester: RZ + NRZ - I
Baud Rate: Number of signal units per second (bitrate/bps), emphasizes on data transmission.

Anirban

12/22/2019