A System View of Networks

computer systems › 15-441 networks

Readings:

  • Software Engineering for Systems Hackers, David’s notes
  • TCP/IP Illustrated, Volume 1: The Protocols by W. Richard Stevens.
  • Unix Network Programming: Networking APIs: Sockets and XTI (Volume 1) by W. Richard Stevens.
  • Advanced Programming in the Unix Environment by W. Richard Stevens, Addison-Wesley, 1993
  • computer networks, a system approach
  1. basics: IP
  2. applications: Web, HTTP, CDN, Overlays (P2P and bitcoin), security
  3. modern n/w infrastructure: router, data center n/w

Chapter1: Foundation

Problem 1: build a network

  1. requirements from stakeholders: Stakeholders of a computer system may share different perspectives on it. We need to consider network designers, n/w operators, and application programmer in respect to computer networks.
    • designer: share n/w resource fairly
    • app programmer: networks provides (logical) channels for application processes to communicate
    • operator: Automation and avoidance of change make n/w more manageable. An operator can configure one router but not thousands of routers.
  2. Designing a n/w for performance should be aware of the performance metrics first.
  3. N/w designers have developed n/w architectures guiding the design and implementation of n/w which include Internet architecture and OSI model.

A recursive definition of a network: A network can consist of subnetworks, each composed of two or more nodes connected by physical links.

To build a network from the bottom up, we start by connecting two nodes with a physical link. We then scale the network by adding additional nodes or subnetworks.

The challenge then becomes providing network connectivity through addressing and routing mechanisms.

Terminology

  1. Direct links: a network can consist of two nodes. The physical medium that connects two nodes is called a link. A node can refer to a computer or a specialized piece of h/w. Direct links are composed of point-to-point and multiple-access ones.
  2. Point-to-point links: a pair of nodes share a single physical link whereas multiple-access is more than two nodes sharing one link.
  3. Indirect links: switched n/w among which the circuit switched type is for telephones and the packet switched type is for general n/w.
  4. Packet-switched n/w: the nodes send discrete blocks of data to each other. It uses store-and-forward approach to transfer data. Each node receives a complete packet over some link, stores it and then forwards to the next node.
  5. Circuit switched: This kind of n/w establishes a dedicated circuit across a sequence of links and then allows the src node to send data stream to a dest node.
  6. Internetwork (internet): a set of independent n/ws are interconnected to form an internetwork.
  7. Convention: a generic internet, the TCP Internet
  8. Router/Gateway: A node that is connected to two or more networks is commonly called a router or gateway
  9. Address: An address is a byte string that identifies a node. By specifying an address of a node, it can achieve host-to-host connectivity.
  10. Routing: The process of determining systematically how to forward messages toward the destination node based on its address is called routing.
  11. Source routing (or path addressing): the path to reach a given destination is explicitly specified by the source when it first injects a packet into the network.
  12. Cast: that the source node sends a message to a single node is called unicast (one-one). broadcast (one-all), multicast (one-many)
  13. Multiplexing, which means that a system resource is shared among multiple users. As in n/w context, data sent by users can be multiplexed over the direct links.
  14. STDM, synchronous time-division multiplexing. The idea is to divide time equally and, in a round-robin manner, each flow can send its data over the physical link.
  15. FDM, frequency-division multiplexing. The idea is to transmit each flow over the link at a different frequency.
  16. Packet, the limited-size block of data that the physical link allows for a data flow to transmit.
  17. FTP, file transfer protocol
  18. Burst error, several contiguous bits are corrupted.
  19. Bit error, a bit is flipped. It occurs because of outside forces. (1/(106~107) on a copper cable, 1/(1012-1014) on an optical cable)
  20. MAC, media access control address, 48 bits long, written in hex. It’s used as part of Ethernet protocol. e.g. 34:f3:e4:ae:66:44.
  21. Ethernet is a family of wired computer networking technologies
  22. Broadcast storm

Requirements

Why packet-switched networks are more efficient than circuit-switched ones?

The capability of transmitting data on a switch (bandwidth) is limited. When multiple hosts need to send data to their counterparts over a shared physical link, data flows are multiplexed onto the link and then demultiplexed at the receiving end. Common multiplexing methods, such as STDM and FDM, support only a fixed number of data flows, as it is difficult to allocate additional time slots or frequencies dynamically. Moreover, STDM can result in significant idle time if a host has no data to send during its allocated time slot.

Statistical multiplexing addresses these limitations by allocating transmission time to data flows on demand. By avoiding idle time, it gives packet-switched networks efficiency. To ensure fair access to the link and prevent a single large message from blocking other flows, statistical multiplexing imposes an upper limit on the amount of data each flow can send at a time—i.e., the packet size. Large messages are therefore fragmented into multiple packets for transmission and reassembled upon reception.

Each switch independently decides which packet to forward next, typically on a packet-by-packet basis. To maintain fairness, switches may use strategies such as First-In-First-Out (FIFO) or round-robin scheduling.

Switches also buffer incoming packets in memory in case packets arrive faster than the shared link can transmit them. If the buffer becomes full, some packets must be dropped—a condition known as congestion, which is the key challenges of statistical multiplexing.

App level of n/w: Many applications require common n/w services. It is the network designer’s responsibility to define an appropriate set of services that abstracts away the underlying network complexity from the application programmer. Such services are provided through (logical) channels. Each app can select the type of channel which meets its needs best.

A common communication pattern is to request and reply. To support such services, two types of channels are provided, request/reply channels and message stream channels.

Where the functionality of channels is implemented involves a trade-off between packet switches and the end hosts (devices).

N/w failures make it difficult to deliver a message reliably. There are three class of failures: at the bit level, bit errors or a burst error; at the packet level, packet lost or late; at the node and link level, a link is cut or flaky, or a node crashes.

Minimizing change simplifies network management, but it also underscores a fundamental trade-off between system stability and feature velocity. The deployment of new features within the network can impact thousands of dependent services and potentially result in significant periods of unavailability

Arch

The hourglass design of Internet protocols reflects the central philosophy of the architecture. IP defines how to exchange packets as the focal point of the arch. The narrow-waisted model makes n/w easy to embrace new technologies and user demands.

1
2
3
4
5
6
7
8
FTP HTTP DNS TFTP
  \/       \/
  TCP      UDP
       \/
       IP
  /  / /  \  \
 Ether ...  LTE WiFi
   (subnetwork)

Local area routing

Example of building a LAN:

  1. choose an addressing scheme: Use Ethernet. MAC shows the destination and source address.
  2. choose a routing algorithm to deliver packets to the destination
    • broadcast with learning switches algorithm: incurs loops, causing broadcast storm
    • broadcast with learning switches and spanning tree: solves loop issue
    • distance vector

MAC addresses: all MAC addressed are unique, assigned by the device’s manufacturer. Every device (wireless adapter, Ethernet port, bluetooth connector) has attached a MAC address.

Chapter3: Internetworking

In networking layer, Internet protocol provides inter-network connectivity to hosts, sending packets destined across networks. Sub-networks are connected via routers.

IP addressing

  1. hierarchical addressing: replace flat addresses (source routing) with hierarchical addresses which are easier to scale and forward
  2. class-based addressing: obsolete today. Traditional addressing tends to use network/host split and dotted-quad notation.
  3. subnet addressing: use network/subnet/host split. A single network number is shared among multiple networks called subnets. Subnets are close to each other, reachable by a single router. They are not visible outside.
  4. CIDR

Subnetting: All the nodes on each subnet are configured with a subnet mask and sharing the same subnet number. The subnet number is the bitwise AND of an IP address and a subnet mask of this subnet. By checking the bitwise AND between IP address of the destination host and the subnet mask of source host matching the subnet number of source host, it’s able to find out if these hosts are on the same subnet, thereby sending message via the subnet instead of a router.

Example:

IP address: 192.168.1.10 = 192.168.1.0 + 10

Subnet mask: 255.255.255.0. The ‘1’ marks the network part and the ‘0’ marks host part.

1
2
IP:         	 11000000.10101000.00000001.00001010
Subnet mask:     11111111.11111111.11111111.00000000

IP header design: the information of an IP header need is to parse packet, carry packet to the destination and deal the failures (loops, corruption, very large packet).

  • TTL, time-to-live filed (8 bits) prevents forwarding loops as it decrements at each loop and the packet will be discarded when it reaches 0.
  • A router can split a packet into multiple fragments when its size is larger than the link’s MTU

Tunneling forces a packet to go to specific point in the network. It doesn’t go through the regular path. A tunneling app is VPN.

A host has a host name, an IP address and a MAC address.

ARP helps to translate IP to MAC, an Ethernet address, by broadcast searching for IP address to all devices on the LAN. Each ARP response is cached as an ARP entry with a timeout on host’s ARP table. However, ARP broadcast takes O(N^2) for an N host network. Proxy ARP decreases the overhead of broadcast.

DNS is a directory service for hosts on the Internet which maps from host addresses to host names.

Terminology

  1. LAN: local area n/w,
  2. WAN: wide area n/w
  3. End host/host/computer/device, switch/bridge/router, number-port switch
  4. IP addresses (IPv4) uses a unique 32-bit number associated with a host. It’s partitioned into a prefix (network) and suffix (host) components. It’s represented with the dotted quad notation. e.g. 12.34.158.5.
  5. Class-based addressing, an early method of assigning IP addresses (specifically IPv4) by dividing the entire IP address space into fixed-size classes, based on the leading bits of the address.
  6. Subnet: the idea is to take a single IP network number and allocate the IP addresses with that network number to several physical networks which is referred to as subnets. A subnet can consist of multiple hosts.
  7. CIDR, classless interdomain routing. Flexible division between network and host addresses. Need to specify the boundary of network prefix by slash. e.g. 128.23.9/26 uses 26 bits as n/w prefix.
  8. Frame, a data unit for data link.
  9. Datagram (IP packet), a data unit for network layer.
  10. MTU, maximum transmission unit. Every link has a MTU which defines largest number of bits it can carry as one unit.
  11. ARP, address resolution protocol.
  12. DNS, domain name system.
  13. All FF address: FF:FF:FF:FF:FF:FF, an Ethernet destination means to broadcast to all devices on the LAN.