6.

829
Computer Networks
Lecture 1:
Introduction & Course Overview

Mohammad Alizadeh

Fall 2018

!1
 The Internet: An Exciting Time
One of the most influential inventions
– A research experiment that escaped from the lab
– … to be the global communications infrastructure

Ever wider reach

– Today: 3 billion users
– Tomorrow: more users, computers, sensors, “things”, …
40 billion devices by 2020

Constant innovation
– Apps: Web, P2P, social networks, virtual worlds …
– Links: Optics, WiFi, cellular, ...

◇ Slides 1-12 based on lectures by Nick McKeown (Stanford), Jennifer Rexford !2

(Princeton)
 Transforming Everything
The ways we do business
– E-commerce, advertising, cloud computing, ...

The way we have relationships

– E-mail, IM, Facebook, Instagram, virtual worlds

How we think about law

– Interstate commerce? National boundaries? Wikileaks?

The way we govern

– E-voting
– Censorship and wiretapping

The way we fight

– Cyber-attacks, nation-state attacks, fake news !3
But what is networking?

!4
A Plethora of Protocol Acronyms?
SNMP WAP
SIP IPX
PPP MAC
LLDP FTP
UDP
ICMP HIP
OSPF RTP IMAP IGMP
BGP IP
PIM ECN
RED ARP
RIP HTTP TCP
MPLS RTCP
SMTP
RTSP BFD CIDR
NNTP TLS NAT
SACK STUN
DNS SSH
DHCP
VLAN VTP
POP LISP TFTP LDP !5
A Heap of Header Formats?

!6
TCP/IP Header Formats in Lego

!7
 A Big Bunch of Boxes?
Label Load
Router Switch
Switched balancer
Router Scrubber
Repeater
Gateway
Intrusion Bridge Route
Deep Detection Reflector
Packet System
Inspection DHCP
server Packet
Firewall
NAT Hub shaper
Packet
DNS sniffer
WAN Base Proxy
accelerator server station !8
An Application Domain?

!9
 A place to apply theory?
• Algorithms and data structures
• Graph theory
• Control theory
• Queuing theory
• Optimization theory
• Game theory and mechanism design
• Machine learning & AI
• Cryptography
• Programming languages
• Formal methods
!10
 A place to build systems?
• Distributed systems
• Operating systems
• Computer architecture
• Software engineering
…

!11
 What Peers in Other Fields Say
“What are the top ten classic problems in networking? I would like to
solve one of them and submit a paper to SIGCOMM.”
After hearing that we don't have such a list: "Then how do you consider
networking a discipline?”

“So, these networking research people today aren't doing theory, and
yet they aren't the people who brought us the Internet. What exactly are
they doing?”

“Networking papers are strange. They have a lot of text.”

Is networking a problem domain or a scholarly discipline?

!12
Before you all leave …

!13
 So, Why is Networking Cool?
Relevant
– Can impact the real world
– Can measure/build things

Interdisciplinary
– Well-motivated problems + rigorous solution techniques
– Interplay with policy and economics

Widely-read papers
– Many of the most cited papers in CS are in networking
– Congestion control, distributed hash tables, resource
reservation, self-similar traffic, multimedia protocols
!14
 So, Why is Networking Cool?
Young, relatively immature field
– Tremendous intellectual progress is still needed
– You can help decide what networking really is

Defining the problem is a big part of the challenge

– Recognizing a need, formulating well-defined problem
– … is at least as important as solving the problem.

Lots of platforms for building your ideas

– Testbeds: Emulab, PlanetLab, Orbit, GENI
– Programmability: Click, Mininet, NetFPGA
– Measurements: traceroute, RouteViews, Internet2
!15
About this class

!16
 Goals

1. To understand a good slice of the state-of-the-art

in network architecture, protocols, and systems.

2. To learn how to conduct networking research and

develop innovative ideas.

!17
 Course Structure
Lectures & Readings

Three Problem Sets

One Quiz (Nov. 15, in class)

Final Project

!18
 Lecture & Readings
Lecture
– Each class we will discuss 1-2 papers
– You must read the papers before class
– Most of lecture will be spent discussing/debating the papers
– Come prepared to discuss the main ideas!

Questions about readings

– Questions will be posted on class webpage per lecture
– Submit answers online by midnight the night before lecture
(see class webpage)
– To pass the class, you must submit answers for at least 18
lectures
!19
 Syllabus Summary
Internet Architecture & Protocols (8 classes)
– Key principles & protocols: congestion control, routing, mobility,
measurement
– Classic research papers

“Underlay” Networks (8 classes)

– The infrastructure underlying the modern Internets
– Wireless & datacenter networks, optical networks, software-
defined networks, programmable routers

“Overlay” Networks (5 classes)

– Applications that run on top of the Internet
– Video, peer-to-peer, content distribution, blockchain

Miscellaneous (2-3 classes)

– Guest lectures, project presentations, … !20
 Logistics
Who will lead the discussions
– Hari Balakrishnan (hari@csail.mit.edu)
– Mohammad Alizadeh (alizadeh@csail.mit.edu)
– Guest experts (from Microsoft, Google, Fastly, Akamai, …)

TA
– Akshay Narayan (akshayn@mit.edu)

Class webpage
– http://web.mit.edu/6.829/www/currentsemester/

Piazza
– Sign up here: https://piazza.com/mit/fall2018/6829/home
– Quickest response; someone else probably has same question
– If private, please post a private Piazza post
!21
 Rest of Today
A sampler of class topics:

1. Internet Architecture & Protocols: Congestion

control; Routing

2. Underlay networks: Cellular, Datacenters, and

Programmable networks

3. Overlay networks: Streaming Video

!22
Internet Architecture
& Protocols

!23
 Internet Architecture
Architectural questions tend to dominate networking
research

Definition and placement of function

– What to do, and where to do it

The “division of labor”

– Across components (hosts, routers, and management
systems)
– Across multiple concurrent protocols and mechanisms

!24
Example: Reliable communication in the
Internet
Network
– Best-effort delivery between two end-point addresses
– Packets may be lost, corrupted, or come out-of-order

Host
– Everything else
– Retransmit lost/corrupt packets, put packets back in order,
…

host host

network
!25
 Why Best-Effort?
Never having to say you’re sorry…
– Don’t reserve bandwidth and memory
– Don’t do error detection & correction
– Don’t remember from one packet to next

Easier to survive failures

– Transient disruptions are okay during failover

End-to-end argument
– Reliability can only be guaranteed completely end-to-end

What are disadvantages of best-effort delivery?

!26
 Congestion Control

What rate to use for each flow?

- Prevent congestion collapse
- Allocate bandwidth “fairly”

Need to do this in a distributed way

!27
 TCP Congestion Control
Additive increase, multiplicative decrease
– Each RTT, increase window by one packet
– On packet loss, divide congestion window in half

Window
Loss

halved

t !28
 Some questions we’ll study…
What’s the “right” congestion signal?

How can routers help with congestion control?

What does it mean to be “fair”?

What if some hosts don’t follow the rules?

!29
 Inter-Domain Routing
How do routers find an end-to-end path?

AS 2 Backbone ISPs AS 3

AS 1

AS 5
AS Measurement
4
Border Gateway Protocol (BGP)
- How do ASes exchange
Regional ISPs information - How do we measure
- Policy-based routing congestion?
(e.g., path preferences based on - Where does it occur?
business relationships) !30
“Underlay” Networks

!31
 Most of the innovation is at the
Internet “Edge”

AS 2 AS 3

AS 1

Data Centers
AS 5 AS 4

Cellular Networks !32

 Cellular Networks

Key Challenges
- Limited wireless spectrum
- Interference
- Highly variable throughput
!33
 Data Centers
Microsoft

Microsoft

Google Facebook
!34
 These things are really big
10-100K servers
100 billion
100s searches
of Petabytes per month
of storage

100s of Terabits/s of Bw
(more than core of Internet)
1.15 billion users
10-100MW of power
(1-2 % of global energy
consumption)
120+ million users
100s of millions of dollars
◇ Slide by George Porter (UCSD) !35
!36
 Networking Inside Datacenters
1.
TLA
1 user request
Picasso Art is…
Deadline
2. Art is= a250ms
lie…
➔ 100s of Intra DC messages

…..
3.

Picasso

1. MLA ……… MLA 1. Art is a

lie…
Deadline = 50ms
2. The chief…
Tail latency matters
2.

…..
…..

• 99.9th percentile
3. 3.

“Everything
“It is
“Computers
“I'd your
“Art like
“Bad work
is to you
aenemy
lie
live in
artistscan
are
that
aslife imagine
useless.
that man
acopy.
makes
poor isis
is the
us
“The “Inspiration
Deadline = 10mschief does
of creativity
exist,
real.”
but They
itultimate
with
Good
must can
realize
lots
good only
seduction.“
artists
of
the
find give
money.“
steal.”
truth.
sense.“
you you
working.”
answers.”
Worker Nodes !37
 Datacenter Networking Challenges

- Very high speed links (10-100Gbps)

- Tiny round trip times (microseconds)
- Dense, multi-path topologies
- Cheap switches with small buffers
- Message latency is King

On the other hand…

- Single administrative domain
- No need to be compatible with outside world

!38
Network Programmability

!39
Software Defined Network (SDN)

Control Control Control

Program Program Program

Global Network Map

Control Plane

Software
Control
Packet
Forwarding Control
Hardware Packet
Forwarding
Control
Packet
Control Forwarding
Packet
Forwarding Control
Packet
Forwarding !40
Software Defined Network (SDN)

Control
Program
Control
Program
Replace distributed protocols
Control Control with
Program Program
“logically centralized” software
programs

Packet
Forwarding Packet
Forwarding

Packet
Packet Forwarding
Forwarding
Packet
Forwarding !41
 Programmable Data Plane

Can we program new data-plane algorithms?

– Congestion control
– Measurement Software
Control
– Load balancing Packet
Forwarding
– Packet scheduling Hardware

Today, these algorithms are hard-coded into router

hardware

!42
Software vs. Hardware routers
10000 3200

640
1000
240
80 100
100 32 35 40
Gbit/s

10 4

1
0.2
0.1 Software router
0.1 Hardware router

0
1999 2000 2002 2004 2007 2009 2010 2014
Year
10—100X gap between hardware and software
routers !43
 Programmable router hardware
Same performance as fixed-function chips,
Some programmability

Parser Ingress pipeline Queues Egress pipeline Deparser

match/ match/ match/ match/ match/

action action action action action

In Out

Stage 1 Stage 2 Stage 16 Stage 1 Stage 16

!44
“Overlay” Networks

!45
Video is the BIG thing on the Internet

Video is more than 50% of peak traffic in the US

Trend: Streaming over HTTP

– Content Distribution Networks (CDNs)
• Well-provisioned HTTP servers at the edge of the Internet
– Firewall friendliness

!46
 Dynamic Streaming over HTTP

Request:
next video chunk at bitrate
Outputr Input
1 sec/sec bitrate
Response:
video content 1 sec
video Video Server
Video
content
Client

How to pick video resolution (bitrate) based on network

conditions?
How does the transport (TCP) impact video quality?
How should the video codec and transport interact?

!47
Animation from Te-Yuan Huang (SIGCOMM ‘14) http://conferences.sigcomm.org/sigcomm/2014/doc/slides/38.pdf
Our first two papers…

!48
!49