Internet Data Transmission

Have you used the internet in the last day or week? (No one raised their hand)
How do you receive data from far away (e.g., YouTube, games)?
- Server sends data.
- Routers are involved.

Key Function: Transfer packets from one router to another.
How do routers know where to send packets?
- IP addresses: Routers send packets to destinations with specific IP addresses.
- Challenge: Multiple paths exist.

Analogy: Choosing a route from St. David's Station to campus.
Question: What algorithm do routers use to choose the best path?
- Dijkstra's Algorithm.
- A* (used in robotics, not typically in internet routing).
- Spanning Tree (data structure that can be used as an algorithm).
- OSPF (protocol that uses algorithms).

Survey: General public's understanding varies.
Definition: A huge, human-engineered system; arguably the largest.
- It works robustly due to robust algorithms.

User Level: Browser, chat, apps (e.g., TikTok).
Application Layer: Computing devices hosting apps and software (hardware).
Networking Devices: Routers and switches.
- Switches: Used in local networks to connect multiple devices.
  - Function: Distribute data packets to multiple users.
  - Routers vs. Switches: Router has policies, while switch does not. Nowadays, routers and switches are converging.
Physical Medium: Cables, Wi-Fi, LTE (4G, 5G).

Trade-offs: Wi-Fi (higher latency, bigger bandwidth), broadband, cable (minimal delay).
Algorithms aim to provide the best path based on parameters.
Example: Packet from America to the UK goes through several routers, choosing paths based on real-time parameters.

Network Core: Routers connected to each other.
- Focus: Network, data link, and physical layers.
- Excludes: Transport and application layers.
Edge Network: Edge router and other devices.

Routing: Determine the best path through the network.
Forwarding: Determine how to send a packet from the rest of the network to your devices.
Core routers primarily focus on routing.

Why different types? Because different networks have different characteristics (Wi-Fi, wired, dynamic).

Each node has its own IP address and MAC address.
Factors to consider when connecting Exeter and Nanden:
- Latency.
- Bandwidth.
- Topology of existing networks.
- Cost (e.g., using open-source tools).

Mathematical Tool: Graph.
Graph Representation: G = (V, E)
- V: Vertices (nodes) – e.g., a, b, c, d, e, f.
- E: Edges – connections between nodes; each may have a cost.

Initialization:
- Start from node A.
- Add connected nodes (A-D, A-B, A-C) to a table.
Choose the shortest edge.
- A-D (cost = 1).
Check neighbors of D (B, C, E).
- A to B:
  - Old cost: 2.
  - New cost (A-D-B): 1 + 2 = 3.
  - No change (old path is better).
- A to C:
  - Old cost: 5.
  - New cost (A-D-C): 1 + 3 = 4.
  - Update (new path is better).
  - Remember the previous hop (D).
- A to E:
  - Old cost: Infinity (A doesn't know E).
  - New cost (A-D-E): 1 + 1 = 2.
  - Update (new path is better): A-D-E.
Repeat:
- Choose the next shortest path (A-E).
- Continue until the termination condition is met (all nodes in the tree).

Initialization:
- Each router maintains a table.
- M’ stores nodes in the tree; algorithm terminates when all nodes are in M’.
- Columns: Distance to the source node and the previous node.
Main Algorithm:
- Checks the current shortest path.
- Updates neighbors if a better path is found.

Naive version: O(n^2)
- Outer loop: n times.
- Inner loop: Reduces searching space by one each iteration.
- Total complexity: 1 + 2 + … + (n - 1) = \frac{n(n-1)}{2}
Simplified with data structures (Fibonacci heaps, priority queues).

Millions of routers: 1,000,000^2 is computationally infeasible.
Links change dynamically.
Application: Top-tier networks (stable, costly to change, e.g., transatlantic cables).