Major I cheat sheet

The instructor's own example: "definition, justification, advantage, disadvantage, like star topology". Answer in that order, every time:

1. Name it. One line: "A star topology is the best choice."
2. Define it. One sentence from the slides.
3. Justify it. Point at the words in the scenario that led you there ("the office wants one central device…").
4. Advantages that matter for this scenario.
5. Disadvantages — at least one, honestly stated, plus how to live with it.

1. Write the formula first, in words.
2. Convert units before substituting: km → m, bytes → bits (× 8), ms → s.
3. Substitute and show the arithmetic on one line.
4. Give the answer with a unit, then convert to the unit asked for (Kbps, ms, μs).
5. For parity, CRC and checksum: show the sender side and the receiver check, and state "accept" or "reject".

• Draw devices as labelled boxes or circles (A, B, C…) and links as straight lines.
• Write the link count under the drawing and check it against the formula.
• Mark the central device (hub/switch) clearly in a star, and the two terminators on a bus.
• For a hybrid, name it: "star backbone with bus networks".

The exchange of information between two devices through a transmission medium.

5 parts

Message, sender, receiver, transmission medium, protocol

Message

Text (Unicode bit patterns), numbers (binary), images (bit patterns), audio, video (images in rapid succession)

A set of devices (nodes) connected by communication links.

Node

A host (computer, printer, phone) or a networking device (router, switch, modem)

Link

The pathway that carries data between devices; wired or wireless

Point-to-point

A dedicated link between exactly two devices

Multipoint

One link shared by more than two devices

Performance

Measured by throughput and delay (transit and response time). Depends on number of users, medium, hardware and software. Throughput and delay contradict: more throughput means more data in the network, which raises delay.

Reliability

Frequency of failure and time to recover from a failure.

Security

Protecting data from unauthorized users and damage; policies to recover from breaches and data loss.

LAN

A room, building or campus (e.g. two buildings)

MAN

A town or city (e.g. STC across a city)

WAN

Long-distance transmission: countries, continents

internet

Any networks joined by connecting devices (routers)

Internet

The global collection of networks running the TCP/IP suite

To be on the Internet a host must run TCP/IP, have an Internet (IP) address, and be able to send IP packets to other machines.

Tier 1

International backbones, few, connected directly to each other (Sprint, AT&T, Lumen)

Tier 2

National/regional providers, connected to at least one tier-1 (STC, ITC, Mobily)

Tier 3

Local ISPs, buy service from national providers

Private peering

Direct connection, owned and operated by the ISPs themselves

IXP

Public peering point run by a third party; any ISP can connect (Saudi Arabian Internet Exchange)

Trend: international ISPs meet at private peering points; national ISPs interconnect through IXPs.

Protocol: a set of rules controlling the exchange of data between two entities. Its elements are syntax (format), semantics (meaning) and timing.

Why standards: early vendors (IBM, Digital) built networks only their own machines could join. Standards give interoperability between vendors, a large market for equipment and software, and guidelines for manufacturers, vendors and governments.

Organizations: ISO, ITU-T (UN agency), ANSI, IEEE (LAN/MAN standards), W3C.

Definition

Every node has a dedicated point-to-point link to every other node.

Links

N(N − 1)/2 — N = 5 gives 10

Ports

N − 1 NICs / I/O ports per device; cables = links

Definition

Each node has a dedicated point-to-point link to a central controller (hub/switch) only. Nodes are not linked to each other.

Links

N; each device needs one port

Definition

One long backbone cable; each node taps in with a drop line. Terminators close both ends.

Links

1 main cable + N drop lines (multipoint)

Definition

Each node has a dedicated point-to-point link with the two nodes on either side of it; the signal passes around the ring.

Links

N

A combination of topologies, e.g. a star backbone with three bus networks, star–bus, or star–ring. Use it when departments already have their own networks and need to be joined centrally.

Network architecture is too complex to handle as one piece, so functions are grouped into layers. Layer n − 1 provides a service to layer n through a well-defined interface.

PDU = data (payload) from the layer above + this layer's control information (header). The data link layer adds a header and a trailer.

Encapsulation: layer N − 1 carries the whole PDU of layer N in its data part without knowing its content. Each header is read only by the peer layer on the receiving node (peer-to-peer communication).

Ethernet | IP header | TCP header | DATA | trailer
 frame      packet      segment    message

OSI

7 layers, developed by ISO in the 1970s, a framework for standardization; dominated before 1990. An open system lets any two systems communicate regardless of architecture.

TCP/IP

5 layers, developed in the 1970s, named after TCP and IP. The lower four match OSI's lower four; OSI's session, presentation and application are one application layer.

Implementation

Application, presentation, session, transport: software. Network: hardware + software. Data link and physical: hardware in the NIC.

Light: 3 × 10⁸ m/s in vacuum, ≈ 2/3 of that in cable.

The number of bits that fill the link (the pipe's volume: width = bandwidth, length = delay).

Distance one cycle occupies; depends on frequency and medium.

Analog data

Continuous values (sound, light, temperature)

Digital data

Discrete values (text, integers)

Analog signal

Continuously varying wave, infinite values

Digital signal

Voltage pulses, limited values (1 = positive voltage, 0 = zero)

Periodic

Repeats over identical periods (cycles)

Aperiodic

No repeating pattern

Data communication commonly uses periodic analog and aperiodic digital signals. Data must become electromagnetic signals to be transmitted.

Simple signal: one frequency (a sine wave). Composite: several sine waves with different frequencies, amplitudes or phases.

Frequency is the rate of change with time: change in a short time = high frequency; over a long time = low frequency. Most digital signals are aperiodic, so frequency doesn't apply to them; use bit rate and bit interval.

• Low-cost technology
• Longer distances using repeaters
• Security and privacy (encryption)
• Noise is easily removed
• Cheaper, easier multiplexing (many sources on one link)
• Computer can process both analog (voice, video) and digital data

Two insulated copper wires twisted in a spiral to reduce interference from nearby pairs (more twists = better quality). Used in the telephone subscriber loop and LANs. Connector: RJ-45.

Straight-through: PC–switch/hub, router–switch/hub. Crossover: same-type devices: PC–PC, hub–hub, switch–switch, hub–switch, router–PC.

Core (thin glass/plastic fiber) + cladding (different optical properties) + jacket (protects against moisture and crushing). Carries light pulses.

Multiplexing: combining data from several sources onto one high-capacity link; a demultiplexer separates the streams at the other end.

Repeater: a physical-layer device that receives a weakened or distorted digital signal, regenerates it and sends a fresh copy, so the signal can travel farther.

• Framing / deframing: pack bits into frames with header and trailer
• Addressing: physical (MAC) addresses in the frame header
• Error control: detect and correct errors
• Flow control: sender must not send faster than the receiver can process
• Access control: who uses a shared link (part 2)

A flag (usually 01111110) marks the start and end of a frame. If it appears inside the data:

Byte stuffing

Character-oriented. Sender adds an ESC byte before every flag or ESC byte in the data; receiver removes the ESC and treats the next byte as data.

Bit stuffing

Bit-oriented. Sender adds a 0 after five consecutive 1s; receiver removes a 0 after five 1s; if the sixth bit is 1, it's the flag.

Single-bit

Only 1 bit of the data unit changes

Burst

2 or more bits change; not necessarily consecutive. Length = first corrupted bit to last corrupted bit.

To detect or correct, we must send redundant bits: codeword C(n, k), n = k + r.

1. Count the 1s in the dataword.
2. Parity bit = 0 if even, 1 if odd, so the total is even.
3. Receiver counts the 1s in the codeword: even → accept, odd → reject.

1. Write the datawords as rows.
2. Add a parity bit at the end of each row.
3. Add a parity row for each column, including the parity column (corner bit).
4. Receiver rechecks every row and column. A failing row + failing column cross at a single bad bit, which can be corrected.

1010 | 0
0111 | 1
1100 | 0
1001 | 0
-----+--
1000 | 1

Detects 1, 2 or 3 errors; not all 4-bit errors. Corrects a single-bit error.

1. Generator: write the polynomial as bits, e.g. x³ + x + 1 → 1011. r = generator length − 1.
2. Append r zeros to the dataword.
3. Divide with modulo-2 division: XOR, no borrows. When the leading bit is 0, XOR with 0000.
4. The r-bit remainder is the CRC; codeword = data + CRC.
5. Receiver divides the whole codeword by the same generator: remainder 0 → accept; otherwise reject.

101110000
1011
----
 0001
 0000
 ----
  0010
  0000
  ----
   0100
   0000
   ----
    1000
    1011
    ----
     0110
     0000
     ----
      110   ← CRC

Frame = 101110 110

1. Split the message into k-bit words (16 in the Internet).
2. Add the words. Any carry out of the left is wrapped around and added to the right.
3. Checksum = complement of the sum (flip every bit).
4. Receiver adds every word including the checksum, then complements. All 0s → accept; anything else → reject.

  10101001
+ 00111001
----------
  11100010   sum
  00011101   checksum (complement)

Receiver: 10101001 + 00111001 + 00011101
        = 11111111 → complement 00000000 → accept

  1100110011001100
+ 1010101010101010
------------------
 1 0111011101110110   carry out
 →0111011101110111   carry wrapped in
  1000100010001000   checksum

Retransmission is inefficient when:

• Wireless: the bit error rate is very high, so there would be a huge number of retransmissions.
• Real-time multimedia: waiting for a resend creates unacceptable delay.

Forward error correction (FEC) detects and corrects a limited number of errors without retransmission:

• Two-dimensional parity
• XOR: send R = C₁ ⊕ C₂ ⊕ … ⊕ Cₙ with the codewords; a corrupted block = XOR of R with all the other blocks
• Chunk interleaving for burst errors: mix chunks so a lost packet removes only one chunk from each packet, which multimedia can tolerate

LLC

Logical link control: error and flow control

MAC

Media access control: framing, MAC addressing, multiple access

Three families: random access (CSMA, CSMA/CD), controlled access (reservation, polling, token passing), channelization (FDMA, TDMA, CDMA).

No station is superior; each decides by itself. Carrier sense: listen to the medium before sending. This reduces collisions but cannot eliminate them, because of propagation delay.

Max propagation time: time for a bit to travel between the two most widely separated stations. The longer it is, the worse CSMA performs.

CSMA wastes the channel while colliding frames finish. With collision detection the sender keeps listening while it transmits. On a collision:

1. Abort the transmission.
2. Send a 48-bit jam signal so every station discards the frame.
3. Back off a random time.
4. Rerun the persistence method.

Used by Ethernet (IEEE 802.3) on a bus, or a star with a hub.

Ordered, fair access; no collisions; each node gets R/M.

Reservation

Each cycle starts with a reservation frame of N minislots (one per station). Stations that reserved send in order at full rate R.

Polling

Centralized: a primary station; select = primary wants to send to a secondary; poll = primary asks each secondary if it has data (data or NAK). Distributed: no primary; access passes down a known order (reservation and token passing are examples).

Token passing

A token circulates in a ring. A station waits for a free token, marks it busy with its data and destination; the destination takes the data and frees the token.

FDMA

Bandwidth split into M frequency bands; each station sends continuously on its band at R/M, even when alone

TDMA

One channel shared in time; a station waits for its slot, R/M even when alone

CDMA

One channel carries everyone at once; each station encodes with its own code, receivers decode with it

LLC (802.2)

Top: part of framing, error and flow control if needed; makes MAC transparent, so different LANs interconnect

MAC (802.3)

Bottom: part of framing, MAC addressing, media access (CSMA/CD for Ethernet, token passing for Token Ring); specific per LAN

6 bytes = 48 bits, flat, burned into the NIC ROM. First 3 bytes = vendor (Cisco 00-00-0C, Juniper 00-05-85); last 24 bits unique per card.

Traditional Ethernet is half duplex because of CSMA/CD. Full duplex sends and receives at once, so throughput doubles: 100 Mbps → 200 Mbps; 1 Gbps → 2 Gbps.

Requirements:

1. Full-duplex NICs
2. Two wire pairs: one host → switch, one switch → host
3. A switch, not a hub, as the central device
4. Point-to-point (dedicated) links to the switch

Each station is its own collision domain, so CSMA/CD is no longer needed.