Data Communications and Networking

CSMA (Carrier-Sense Multiple Access)

Listens to the channel to see if its in use. If a collision is detected, wait a random amount of time and restart.

Primary Collision

Transmission is not seen due to propagation delay.

Secondary Collision

Stations waiting for transmission to end transmit at the same time.

Persistent CSMA

Listens until the channel is idle then immediately transmits, if there is a collision wait a random amount of time and restart.

Non-persistent CSMA

Listens to the channel, if it is in use wait a random amount of time then restart the protocol.

p-Persistent CSMA

Waits until the channel is free, transmits with probability p, otherwise waits until maximum propagation delay then restarts with p=1-p

CSMA/CA (Collision Avoidance)

(Wireless) Once a message is sent, wait for ACK. If it is not received, restart protocol.

CSMA/CD (Collision Detection)

(Wired) Listen to channel whilst transmitting, if interference is detected, stop transmitting and send jamming signal to tell other stations. Pick new time slot (2 x propagation delay)

Ethernet Standard Naming (e.g. 10BASE-T)

10 Mbit/s — baseband — twisted pair
Transfer rate — baseband — cable medium

Data Link Layer Parts

MAC (Media Access Control) and Logical Link Control

MIME Encoding

To transmit binary data through email systems expecting 7-bit ASCII:
Collect groups of 24 bits (8×3), split into groups of 6 bits (ASCII safe but also 24=6×4) and use values from 0 63

Character Stuffing

Add an escape character before any special characters, the receiver checks the character after the escape character.

Manchester Encoding

Bits are sent as High-low (1) or Low-high (0), giving a clear state transition in.

Parity Checking

Add a single bit to make the number of 1 bits even, this detects single-bit errors (or any odd number).

2D Parity Checking

Row and column parity, this allows for the CORRECTION of single bit errors.

Burst Error

Sequence of i bits where (at least) the first and last are errors, followed by another i bits with no errors.

Cyclic Redundancy Check (CRC)

Treat binary numbers as a polynomial (100 is 1x²+0x+0). Using a predefined generator, append n 0’s to the data (where n is the degree of the generator). Align the generator up with the leftmost 1 of the augmented data and XOR the values, repeat until XOR cannot be performed, the remaining value is the remainder. This is appended to the original data.

Propagation delay

Time taken for the signal to travel.

Random Early Detection (RED)

Running average queue length Q
Q < Min —> Accept
Min < Q < Max —> Accept/Reject at random
Max < Q —> Reject

Leaky Bucket Algorithm

Data can be added freely to the bucket but can only pass forward at one steady rate.

Token Bucket ALgorithm

Data can only be transmitted if tokens are available. Tokens are added at a steady rate, this allows for bursts of high rate transmissions.

POP Mail Protocol

Downloads mail from the server (deleting it from there).

IMAP Mail Protocol

Remotely accesses emails without downloading and deleting them.

Simple Network Management Protocol (SNMP)

Used to configure and control network devices.

Transport Layer Security (TLS)

Encrypts data in transit using a cryptographic hash.

UDP

Best-effort connectionless protocol used for real-time applications (video/audio streaming)

TCP (Transmission Control Protocol)

Connection-oriented protocol used for applications that require reliability.

IPv4 Checksum

One’s complement sum of other header fields.

Dynamic Host Configuration Protocol (DHCP)

Automation for network management that automatically assigns IP addresses, default gateways, etc.

Network Address Translation (NAT)

Allows multiple devices with private addresses to share a public address by rewriting the addresses.

Static Routing

Each router maintains a table of destinations and output links. Works well when configuration and traffic remains the same.

Backward Learning

Packets are timestamped leaving the source, this time is used to estimate time taken to send packet BACK to the source. Assumes reverse traffic encounters similar conditions and has no capability for delays to worsen.

Shortest Path Routing (General)

Assign costs to links and use total cost between routers. These costs can be static (hop count, bandwidth) or dynamic (link delay, etc).

Link State

Each router discovers the others by sending and receiving LSPs by flooding.

Distance Vector Routing

Each router only knows its neighbours but they iteratively share this information with their neighbours.

Split Horizon

A router should not advertise a route back out the interface from which it was learned.

Split Horizon with Poisoned Reverse

A router advertises the learned route back out the incoming interface BUT sets its metric to infinity (unreachable).

Open Shortest Path First (OSPF)

Networks are divided into a backbone and other areas. Each router is classified as a backbone, area border or internal router.

Routing Table vs Forwarding Table

Routing table is the routers record of other routers (neighbours for Distance Vector and all nodes for Link State). Forwarding table is derived from this and is the table of destination —> next hop.

Routing Fabric

Shared memory space in a router, each input and output port has shared access to it.

IPv4 Checksum

One’s complement OF the one’s complement sum of the 16-bit words of the header.
Add all words together (adding any carry bits back at the bottom), once this sum has been calculated, flip all of the bits to give the final value.