• End host must implement all layers
  • Network interface cards talk to the operating system talk to the applications
  • Datalink and physical should go into the network interface card.
  • Network should go into the operating system
  • Transport also goes into the operating system
  • Application implemented in the application
• How does the operating system know which application to send the packet to?
  • Answer: a port
  • There are physical ports and logical ports
• Sockets and ports
  • Socket: allows application to connect to the networking stack.
• Packet header must hold:
  • Destination host address
  • Destination port
• Application looks at data, NIC/Driver looks at packets, and the network stack is the intermediary in between them.
• Bits on wire (L1)…
• Switches vs Routers
  • Switches do what routers do but within a single network
  • In the modern day, the line is blurring.
• Layer encapsulation, multiple layers requre multiple headers.
• Why is the internet splitting of layers?
• End to end principle
  • Guides the debate about what functionality the network does or doesn’t implement.
• Reliable File Transfer
  • Make each step reliable (requires network to handle reliability)
• Allows steps to be unreliable, but do end-to-end check and try again if necessary (do not assume network is reliable)
• Neither will guarantee reliability, but solution 2 will allow you to avoid false positives.
• Clarks paper:
  • Network failures should not interfere with endpoint semantics
• Big idea: you are going to assume failures anyways, so no need to guarantee reliability.
• What is the controversy around the end to end principle?
  • Everyone believes it, but no one knows what it means…
  • Three interpretations of the end to end principle
    • “Only-if-Sufficient”: Don’t implement a function at the lower levels of the system unless it can be completely implemented at this level
    • “Only-if-Necessary”: Don’t implement anything in the network that can be implemented correctly by the hosts. Make network layer absolutely minimal.
    • “Only-if-useful”: If hosts can implement functionality correctly, implement it in a lower layer only as a performance enhancement.
• The E2E principle guides our discussion, performance and reliability
  • What does E2E ignore?
    • Control, what is in my power to change?
    • There are other stakeholders besides users, such as ISPs
    • “Middleboxes”
• “Dumb” network and “smart” end systems
• “Fate sharing”
  • “A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.”, fate sharing tries to prevent this.
  • When storing state in a distributed system, colocate it with entites that rely on that state.
• What is the value of Clark’s papers?
  • E2E principle becomes a pithy pillar that we can lean on.
• David Clark wrote a paper in 1988 that tried to capture why the Internet turned out as it did. What are the goals of the internet?
  • Connect existing networks
    • Pragmatic
    • Successful, narrow waist, IP
  • Robust in the face of failures
  • Support multiple types of delivery services
  • Accomodate a variety of networks
  • Allow distributed management of resources
  • Easy end host attachment
  • Cost effective
    • Hard to say
  • Allow resource accountability
    • Failure, ISPs can’t do this
• What priorities would a commercial design have?
  • Accountability/authentication as top goals
  • Probabily focus on high-revenue applciations
• What would the resulting design look like?
  • Much less flexible and general
• What goals are missing from the list?

Lecture 5: 2/4/2020

• Today is the birthday of Ken Thompson
• Endless number of possible solutions to routing
  • Constrain our discussion to “archetypal internet”
• Packet has:
  • Payload (the actual data)
  • Headers (metadata)
    • Must contain destination address
    • Implies that a host has an address!
    • Or more than one! Different addresses for different layers. Might be connected to multiple networks.
• What is a router?
  • Switch/router
  • A fully connected network doesn’t scale very well, but is extremely fault tolerant. You have low latency and high bandwidth to everyone.
  • All hosts share the same wire. Scales very well. Bad, not robust. Cutting the cable splits a lot. Everybody is sharing the same link. Very cheap.
• The challenge
  • “Good” may have many meanings. The basic challenge is the know how to send it next.
  • Random routing is wasteful
  • Don’t just send it to everyone, this is wasteful.
• Want to adapt to arbitrary topologies
  • Forwarding: when a packet arrives at R2, we are going to foward it.
    • Forwarding with a table.
• Forwarding: Looks up packet’s destination in table and sends packet to given neighbor. Local. Data plane
• Routing: The algorithm that populates tables for forwarding. Control plane.
• Getting a little theoretical
  • We can graph paths packets to a destination will take if they follow tables
  • Set of all paths create “directed delivery tree”. Must cover every node!
  • Oriented spanning tree rooted at destination
• Routing state validity
  • Local routing state is table in a single router
  • Global state is collection of tables in all routers
  • Goal of routing protocols: compute valid state
  • Need succincy correctness condition for routing…
• Global routing state is valid if and only if:
  • For each destination…
    • There are no dead ends
    • There are no loops
• Hosts generally do not participate in routing.
• Focus only on a single destination
  • Ignore all other hosts
  • Ignore all other routing state (why can we do this?)
• For each router, mark outgoing edge with arrow (point at next hop)…
• Bellman-Ford algorithm
• Networks are distributed, asychronous
• Promising algorithm to turn into a routing protocol!
• Distance-Vector Protocols

Lecture 6: 2/6/2020

• Jack Kilby invented the IC
• Rick Astley’s birthday

Kinds of Routing, Kinds of Networks

• The internet does not work by having a single giant routing protocol
• The internet is a network of networks
  • Best way to route on one may not be best way to route on the other
  • Networks differ!
    • Physical size, number of hosts
• Intradomain routing: within a single network
  • IGP: Interior Gateway Protocols
• Interdomain routing: routing between autonomous systems
  • EGP: Exterior Gateway Protocols
• Least Cost Routing
  • Routes that work, no dead ends, no loops
• Routes that minimize some cost
• Last time: tried to minimize the number of hops.
• What else might we want to minimize.
  • Price, propogation delay, distance, unreliability, others
  • But in this class, we can just abstract this away
• Where do these costs come from? Generally, local to router. Router know the costs of attached links.
• Least cost routes are destination based
• Shortest path = least cost path

Trivial and Static Routes

• A route to yourself, loopback routes.
• If you only have one neighbor, that is a default route
• Hosts with multiple neighbors usually have one anyway.
• Static routes are manually entered by the operator.
  • Route that wants to stay up for a long time
  • Censorship thing…?
  • Debugging
  • Operator wants to accomplish a specific goal.

Distance Vector Protocol

• Prototypical is RIP (Routing information protocol)
• Strong relationship to Bellman Ford
• Distance to destination as best path as far as you know.
• Which neighbor is along the best path
• When you changed your mind about distance
• Routing
  • Communicate with other routers to determine how to populating tables for forwarding
  • Figuring out best friends by sharing magic number with neighbors
• Forwarding
  • Physically handing the envelope to neighbors
• Serial Bellman-Ford Algorithm
• We don’t use Dijkstra’s because we need to know everything beforehand.
  • Bellman is parallel, distributed, and asynchronous.
• Distributed algorithms
  • Killer is not computational complexity, moreso the communication

Lecture 7: 2/11/2020

• B-F to D-V, Bellman-Ford to Distance-Vector.
• Can it handle failed links?
• Evidence of Absence of Routes (Poisoning)
• You are advertising poison routes. Dead routes get processes quickly, as opposed to waiting for timeouts.
• Besides expired routes, where did we not advertise something?
• Split horizon, we had a route but chose not to advertise. You can advertise a poison route, a reverse poison.
• Distance-Vector
  • Global computation (it’s distributed across all nodes)
  • …using local data (from just itself and its neighbors)
• Link-State
  • Local computation
  • …using global data (from all parts of the network)
  • What is this “global data”?
  • Information about the state of links
    • Is the link up?
    • What is the cost of this link
  • Gets the state of all links and the location of all destinations
  • Uses that global information to build full graph
  • Finds paths from itself to every destination on graph
  • Uses the second hop in those paths to populate its forwarding table
  • Each router has the complete topology; can basically do it however it wants!
    • For least-cost routes, this is called Single Source Shortest Path (SSSP)
  • Some obvious algorithm choices
    • BF Alg serial version
    • Dijkstra’s alg
    • BFS
    • Dynamic shortest path algorithms
    • Approsimate shortest path algorithms
    • Parallel SSP algorithms
  • Path that you choose will have to be compatible among routers.
  • Sharing Info Globally
  • Flooding: When local information changes, send to all neighbors. When you receive info packet from neighbor, send to all other neighbors. Really big problem. What happens when you add a loop to the topology?
  • Multiple loops, packets multiply exponentially.
  • Solution: Don’t send unless the information is new. Keep a sequence number of updates to tell when you have a new packet. Every router tracks largest sequence number seen from every other router.
  • How to make flooding reliable?
    • Periodically resend things.
  • Tell everyone else about any adjacent information.
  • Convergence delay
  • Using plain non-parallel Dijkstra’s algorithm, Dijkstra’s will never find a looping path.
  • Time to detect failure, time to flood link-state information (proportional to network diameter)
  • Timeline for Local Failure
• Learning switches
  • Tables filled in oppotunistically using data packets
  • No “seeding” with static entries required!
  • Very common for routing at the link layer (L2)
  • What happens when we hav ea loop?
  • If routers

Lecture 8

• Project 1: Distance-Vector, demos and topologies.
• Learning Switches, Spanning Tree protocol
  • L2 Routing, data packet opportunistically updates the tables
  • The big problem is cycles
  • The link state solution (sequence numbers) doesn’t work in this case.
  • Instead of routers sending things, hosts are sending the sequence numbers.
  • Data packets don’t necessarily have sequence numbers
  • The solution: Disable all links until there are no loops, in other words, a spanning tree.
• The solution
  • Find least cost paths from every switch to the root.
  • STP is basically D-V with a single table entry/destination
  • All switches begin by thinking they themselves are the root.
• Addressing
  • IGP vs. EGP
  • The magic of scaling is mostly about addressing
  • IP Addresses is what makes the internet scalable
  • Leads naturally to a two level hierarchy
  • Address: network.host
  • Interdomain routing protocol only deals with a few number of nodes.
  • Addresses aren’t assigned randomly
  • Border routers are running EGPs
  • Internal routers are routing IGPs
  • This was the early internet

Lecture 9 Interdomain Routing

• How are domains connected?
• Interdomain topology, AS graph
• What is a domain (Autonomous Systems)
  • Network under a single administrative control
  • Each AS is assigned a unique AS number (ASN)
• Common kinds of ASes
  • Stub: Merely sends/receives packets on behalf of its directly connected users. Universities, companies
  • Transit: Carries packets on behalf of other ASes.
• Interdomain topology is shaped by the business relationships bewteen ASes.
• Three basic kinds of relationships between ASes
  • X can by Y’s customer, provider, or peer
  • Customer pays provide, peers don’t pay each other
• Goals: valid routes, host addressing key to scaling!
• Multi-home networks break aggregation
• Aggregation and hierarchical addressing allow for scalability
  • you can do one without the other
  • multihoming breaks topology

Lecture 10: BGP

• Interdomain routing
• BGP extends Distance Vector

Lecture 11: Designing IP

• Designing the IP header and syntax.

Lecture 12: Designing IP and IP Routers

• Steve Deering focused on simplifying IP. Got rid of all fields that were not absolutely necessary.
  • Expanded addresses
  • Eliminated Checksum
  • Eliminated Fragmentation
  • New options mechanism, “next header”
  • Eliminated header length
  • Added flow label
• Attacks
  • Spoof source address, host cant filter because source address is always changing
  • Bother the spoofed host, the spoofed host is wrongly blamed.
• Security implications of TOS