Skip to content

Instantly share code, notes, and snippets.

@tttapa

tttapa/CN.md

Last active June 24, 2019 09:27
Show Gist options
  • Save tttapa/870436c6b266d3f81ff31f362c90c40f to your computer and use it in GitHub Desktop.
Save tttapa/870436c6b266d3f81ff31f362c90c40f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
CN.md

Computer Networks

1. Introduction

Slides: (61)

  • A Brief History of Networks
  • Computer Networks Today
  • Layering and Protocols

Reading:

  • 1.4: reference models (?p.)

2. Application I: Client-Server Systems

Slides: (68)

  • Network Programming
  • Telnet & SSH
  • HTTP
  • FTP
  • SMTP, POP, IMAP

Reading:

  • 7.2: Electronic mail (?p.)
  • 7.3.4: The Hyper Text Transfer Protocol (?p.)

3. Application II: DHCP & DNS

Slides: (60)

  • UDP Sockets in Java
  • Dynamic Host Configuration Protocol (DHCP)
  • The Domain Name System (DNS)

Reading:

  • ?.? DHCP
  • 7.1 DNS

4. Application III: P2P

Slides: (67)

  • Semi-centralized P2P
    • Napster
    • GIMPS, SETI@Home, BOINC
  • Unstructured P2P
    • Gnutella 0.4 → unstructured, decentralized overlay network
  • Super-node P2P
    • Gnutella 0.6
  • Structured P2P
    • Chord: Distributed Hash Table: map files onto nodes

5. Application IV: P2P

Slides: (32)

  • BitTorrent
  • TOR

Reading:

  • 7.5.4 Peer-to-Peer Networks (?p.)

6. Transport I

Slides: (79)

  • Transport Layer Services
  • Elements of Transport Layer Services
    • Addressing: Transport Service Access Points
      • Initial Connection Protocol: Process Server
      • Multiplexing
    • Connection Management
      • Bounded Packet Lifetime
      • Sequence numbers
    • Error Control
      • End-to-End Checksums
      • Acknowledgements
    • Flow Control
      • Sliding Windows
  • Sliding Window Protocols
    • Stop-and-Wait
    • Go-Back-N
    • Selective Repeat

Reading: (?p.)

  • 6.1.1 Services Provided to the Upper Layers

  • 6.1.2 Transport Service Primitives

  • 6.1.3 Berkely Sockets

  • 6.2.1 Addressing

  • 6.2.2 Connection Establishment

  • 6.2.3 Connection Release

  • 6.2.4 Error Control and Flow Control

  • 6.2.5 Multiplexing

7. Transport Layer II

Slides: (45)

  • Congestion Control
    • Kleinrock: power = load / delay
    • Min-Max Fairness: Bandwith to one flow cannot be increased without decreasing the bandwidth for another flow
    • Convergence
    • Small capacity receiver: dynamically resize flow control buffer (Transport)
    • Network congestion: lower send rate (Transport)
    • AIMD
  • Unreliable Datagram Protocol
  • Real Time Protocol and Real Time Control Protocol

8. Transport Layer III

Slides: (50)

  • TCP
    • TCP Header
    • 3-Way Handshake
    • TCP States

Reading:

  • 6.4.1 UDP
  • 6.4.3 RTP

9. Transport Layer IV

Slides: (62)

  • TCP Sliding Window
    • Tinygram Syndrome → Delayed Acknowledgements
    • Nagle's Algorithm
    • Silly Window Syndrome → Clarke's Algorithm
  • TCP Timer Management
    • Retransmission Time Out (Smoothed Round Trip Time)
    • Persistence Timer: when to send window probes, starts when Window size of 0 is reported
    • Keep Alive Timer
    • TIME_WAIT Timer: prior to connection closure, ensures that all segments associated with the connection have died
  • TCP Congestion Control
    • TCP: Packet loss → AIMD
    • ACK Clock
    • TCP Slow Start
    • TCP Tahoe
    • Fast Recovery
    • TCP Reno
      • Selective ACK
      • Explicit Congestion Notification

Reading:

  • 6.5.1 - 6.5.10: TCP (except "forbidden zone")

10. Network I

Slides: (90)

  • Network Layer Design Issues

    • Connectionless Services
      • IP
      • No setup phase required
      • Resilient to router crashes
    • Connection-oriented Services
      • MPLS (MultiProtocol Label Switching)
      • QoS, allocation of resources during setup
      • Congestion control (just allocate enough resources in advance for each VC)
      • Easier routing, smaller routing tables
      • Smaller circuit identifiers (not globally unique)

  • Routing Algorithms

    • Dijkstra
    • Bellman-Ford (Distance Vector Routing)
      • Dynamic
      • Each router has vector containing entry for each destination and the best link to get there
      • Vectors are exchanged with neighbors
      • Problem: Count to Infinity
    • Link State Routing
      1. Discover neighbors (addresses)
      2. Set distance to al neighbors
      3. Construct packet with all learned
      4. Send to all routers (Flooding with TTL and unique ID to eliminate duplicates, with age to recover from crashes)
      5. Compute shortest paths using Dijkstra (limit size of routing tables)
    • Hierarchical Routing
      • Reduces routing table size
      • Can increase path length

  • Delivery Models

    • Unicast
    • Broadcast
      • Naïve unicast
        • wasteful of bandwidth, intermediate routers see packets twice
        • sender has to know all addresses
      • Multi-destination
        • single message with list of all destinations
        • lot of work for routers
        • sender has to know all addresses
      • Flooding
      • Reverse Path
        • Exploits sink tree
        • Discard packets that arrive on links other than the link used to reach the sender
      • Spanning Tree
        • Subset of network that includes all routers and no loops
        • Each router knows if lines are in the spanning tree and forwards accordingly
        • Minimum possible number of packets
        • Only possible where routers have global knowledge (not possible with DVR)
    • Multicast

    Reading:

      1. Congestion Control
    • 5.1 Network Layer Design Issues

11 Network II

Slides: (69)

  • Internet Routing Protocols
    • OSPF
      • See: Link state routing
      • Equal Cost MultiPath (ECMP) Routing:
        • Remember sets of all equal length paths and split packets accross them → Load Balancing
      • Packtes (IP)
        • Hello → Discover neighbors
        • Link state update → Provides sender's costs to neighbors
        • Link state ack
        • Database description → Anounces which updates the sender has
        • Link state request → Requests information from the partner
    • BGP
      • See: Distance Vector Routing & Bellman-Ford
      • Peering & Transit
      • Operates on paths, not routers
        • Path = destination, first hop router, sequence of AS
      • iBGP
        • Boundary routers must learn routes of all other boundary routers
  • Dynamic Networks
    • Mobile Networks
      • Network-Layer Mobility
        • Home agent: single consistent address for mobile nodes
        • When host acquires new local address (care-of-address), report back to home agent
        • When home agent receives datagram: encapsulate and tunnel to care-of-address
        • Host de-encapsulates and responds directly
        • Subsequent datagrams may be tunneled directly between remote host and mobile host
    • Ad-Hoc Networks
      • Infrastructure-less networks: all nodes are both routers and hosts
      • Ad-Hoc On Demand Vector Routing (AODV): reactive, not proactive
  • Internet Control Protocols
    • ICMP
    • ARP

Reading:

  • 5.2.10 Mobile Hosts
  • 5.2.11 Ad-Hoc Networks
  • 5.6.4 Internet Control Protocols
  • 5.6.6 OSPF
  • 5.6.7 BGP

12. Network III

Slides: (84)

  • Congestion Control
    • Network provisioning
      • Improve infrastructure
    • Traffic Aware Routing
      • Include load in link costs
    • Admission Control
      • Do not allow new connections (virtual circuit only)
    • Throttling
      • Signal that the network is congested so that hosts can take action
    • Load Shedding
      • Drop packets
    • Traffic Aware Routing
      • Oscillations
        • Slowly adapting schemes do converge, but internet does not use traffic-aware routing
    • Circuit Admission Control
      • Describe average load and burstiness (leaky bucket)
      • Use historic patterns
    • Router Admission Control
      • Routers that are at capacity may remove themselves from remote routing tables (AODV)
    • Throttling
      • Occurs at Transport Layer
      • Mechanisms
        • Choke packets
        • Explicit Congestion Notification (ECN)
        • Random Early Detectionn (RED)
      • Estimatingn Load
        • Link utilization: rapid feedback but hard to account for bursty traffic
        • Packet loss: accounts for all traffic, but too late
        • Queuing delay: rapid feedback including burstiness
  • Quality of Service
    • Bandwidth - Delay - Jitter - Loss
    • Traffic Shaping: describe and police traffic
      • Traffic shape is encoded in service-level agreement
      • Leaky bucket
    • Packet Scheduling: reserve the resources necessary to assuer a QoS level along the whole route
      • FIFO
      • Fair Queuing (FQ): Round-robin
      • Weighted Fair Queuing (WFQ)
    • Admission Control: ensure that not too many flows are accepted
  • Internetworking and Heterogeneity
    • Connecting heterogeneous networks at scale
    • Approaches:
      • Translation
      • Indirection: higher level processes use a common layer that is mapped differently to different networks (IP)
        • Tunneling (multi-protocol routers)
    • Routing
      • Challenges
        • Different routing algorithms (DV, Link State)
        • Different shortest path metrics
        • Obfuscated internal paths (hierarchy)
        • Scale
      • Intradomain
      • Interdomain
        • Between Autonomous Systems
        • Border Gateway Protocol
    • Packet Fragmentation
      • Maximum Transmission Unit
        • Hardware limits
        • OS limits
        • Timing considerations
        • Protocol limits
      • Strategies
        • Transparent
          • Routers re-assemble packets after they traversed hops with small MTUs
          • Easier on the hosts
          • More work for routers
        • Nontransparent
          • Routers do not reassemble packets
          • Easier on the routers
          • More work for the hosts
      • Path MTU Discovery to avoid fragmentation
        • Router returns error message if packet is too big
        • Incompatible with fragmentation, so DNF must be set

Reading:

  • 5.2.7 - 5.2.9 Routing Algorithms
  • 5.3 Congestion Control
  • 5.4.1 - 5.4.4 Quality of Service

13. Network IV

Slides: (69)

  • IPv4 Overview
    • The IP Header
      • Differentiated Services
        • define set of traffic classes for charging and prioritization
        • Expedited Forwarding: regular or expedited (VoIP)
        • Assured Forwarding
          • Priority: gold, silver, bronze or normal
          • Discard: low, medium or high
  • IPv4 Addresses
    • Class-based Addressing
      • Class A: 16M
      • Class B: 64K
      • Class C: 256
      • → Wasteful
    • Classless Inter-Domain Routing (CIDR)
      • Edge routers: need an entry for each subnet or each of their hosts if final hop
      • All external traffic can be forwarded to their ISP
      • Core routers must know how to reach every network (default-free zone)
    • NAT
      • Problems:
        • Violates IP addressing principles: 1 address per interface
        • Breaks end-to-end model
        • Connection-oriented
        • Confuses layering
        • Only works with TCP and UDP
        • IP addresses in the body (FTP)
  • Introduction to IPv6

Reading:

  • 5.5 Internetworking
  • 5.6.1 IPv4
  • 5.6.2 IP Addresses

Data Link I

Slides: (69)

  • MAC Layer Principles
  • Case-study 1: CSMA and the Aloha Protocol
  • Case-study 2: LPL and the BMAC Protocol
  • Case-study 3: Time sync. and TSMP

Layer 5: Application Layer 4: Transport Layer 3: Network Layer 2: Data Link Layer 1: Phy

Transport layer: segment Network layer: datagram

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment