jzhao.xyz

Search IconIcon to open search
     * _ 
*_#  \/
  \._/#
  //        

Internet Computing

Last updated May 1, 2022

Notes for CPSC 317 (see all notes)

The Internet is a network of networks. The main goals was to integrate a number of separately
administrated entities into a common entity

See also: peer-to-peer, security

# Changing an entrenched internet

Enabling a Permanent Revolution in Internet Architecture by McCauley, Harchol, Panda, Raghavan, and Shenker

The current Internet architecture is both inherently flawed (so we should explore radically different alternative designs) and deeply entrenched (so we should restrict ourselves to backwards-compatible and therefore incrementally deployable improvements).

For example, the decades-long migration effort from IPv4 to IPv6

TLDR;

  1. Internet architecture is, and will remain, difficult to change – clean-slate research and projects seem increasingly impossible
  2. Current focus is on backwards-compatible designs that have been tested in large-scale operational networks
  3. OSI model of the internet sees levels below them as ’logical pipes’ to get something from place A to B

# Communication

Necessary conditions

# Circuit Switching

Dedicated path between source and destination. Path taken is determined when connection is established. Single stream of info per path

Works well when

# Packet Switching

Data is divided in packets that are sent individually where each packet is self contained (contains source, destination, and data) and independently routed.

Works well when

# Multiplexing

Multiple input streams must share the medium. It must be possible to “demultiplex” at the destination

Types

  1. Time division multiplexing: each person gets a certain amount of time on the channel
  2. Frequency division multiplexing: each person gets a single frequency band on the channel
  3. Code division multiplexing: combines all messages using a specific code that can be decoded if code is known
  4. Orthogonal multiplexing: a combination of techniques

Network Protocol Stack (from most abstract to least)

Each layer takes data from above adds header information to create new data unit passes new data unit to layer below

  1. Application Layer ( HTTP)
  2. Transport Layer ( TCP, UDP)
  3. Network Layer ( IP Addresses) – this is the ’thinnest’ part of the network stack!
  4. Link Layer
  5. Physical Layer

# Hubs, Switches, and Routers

  1. Hub - broadcasting through cloning bits ( physical layer)
    1. Simplest and cheapest way to create a network
    2. Lots of unnecessary traffic
    3. Other people can see your traffic
  2. Switch - hub but it knows where other hosts are for direct addressing ( link layer)
    1. Keeps a switch table mapping interface number to MAC address
    2. If table is initially empty, will behave like a hub and broadcast
    3. Can start populating switch table based off of sender field from frames
    4. Quicker than a router for internal communication (though some routers have an Ethernet switch built in)
    5. If engineered right, can be full-duplex
  3. Router - glue that ties networks together ( network layer)
    1. Does NOT support broadcast
    2. Serves as a bridge between private home network and the network of the internet provider (which can reach the rest of the internet)
    3. Modern routers can also perform
      1. Network address translation ( NAT)
      2. Assigning IP addresses to hosts using DHCP
      3. Broadcast WiFi signal

# Error Correction

Methods for fault tolerance in data transmission

  1. Parity Bit
    1. Even parity is 1 if number of 1s is odd
    2. Can detect odd number of bit flips
  2. 2D Parity Bit
    1. Additional parity bits for each row
    2. Additional parity bits for each column
    3. One last additional bit in last row of parity bits
  3. Checksum
    1. Assume data is a sequence of 16-bit integers
    2. Addition, 1’s complement sum, carry out added back in
    3. Checksum is the 1’s complement of the computed value
    4. Compare with the received data (if same, it is ok)
      1. Alternatively, compute the same function over the data and checksum
  4. Cyclic Redundancy Check (CRC)
    1. Uses only XOR and shift
    2. Parameterized by constants G and r
    3. r + 1 is the length of G (some power of 2)
    4. G is the generator (arbitrary bit pattern)
    5. Sender wants to send D
      1. Chooses r CRC bits, R such that <D, R> is exactly divisible by G (mod 2)
    6. Receiver knows G, divides <D, R> by G. If the remainder is non-zero an error is detected!
    7. Can detect all burst errors less than $r+1$ bits, and burst errors greater than $r+1$ with probability $1-0.5^r$

# Access Control

  1. Half-duplex - both sides can transmit, but only one at a time
    1. Carrier Sense Multiple Access
      1. Listen before sending, only send if no one else is
    2. Collision Detection
      1. While sending, listen to see if what you are sending is garbled
      2. If so, give up
    3. “Try again later” uses binary exponential backoff
      1. Random backoff between 0 and power of 2 (n increases each time)
    4. Turn-based access control
      1. Controlled by centralized party - polls everyone
      2. Controlled in a decentralized manner - passes a token between senders
  2. Full-duplex - both sides can transmit at the same time without interference/ NAT

# Network Metrics / Peformance

Delay

Traffic Intensity

# Sliding Window

# Go-back-N

# Receiver

# Sender

Simulation Link

# Selective-Repeat Strategy

# Receiver

# Sender

Simulation Link

Congestion/Flow Control


Interactive Graph