Transcript ReThinking-Internet-Arch - CSE Labs User Home Pages

Re-Thinking Internet Architecture
• Today’s Internet
– Original Design Goal, Philosophy and Principles
– End-to-End Principle and “Hourglass” Architecture of
Internet
– Pros and Cons; Challenging Issues
– What have changed? What may have yet to come?
• Overlay Networks
• Future Internet Architectures?
– What are key challenges/issues?
• E.g., mobility, security, “services-oriented” …
• Diversity of “end systems”: laptops, cell phones, sensors, …
1
Network Architecture
What is (Network) Architecture?
– not the implementation itself
– “design blueprint” on how to “organize” implementations
• what interfaces are supported
• where functionality is implemented
• Two Basic Architectural Principles
– Modularity (e.g., layering)
• how to break network functionality into modules
– End-to-End Argument
• where to implement functionality
2
Architectural Principles
(not unique to networks!)
Zhi-Li’s version (synthesized from various sources)
• End-to-end argument
– functionality placement
• Modularity
– Increase inter-operability and manage complexity
• vertical partition -> layered architecture
• horizontal partition?
• Keep it simple, stupid (KISS principle)
– Occam’s Razor: choose simplest among many solutions!
• complicated design increases system coupling (interdependence), amplifies errors, ..
• don’t over-optimize!
• Separating policies from mechanisms
– decouple control from data
– “semantics-free”
• Design for scale
– hierarchy, aggregation, …
3
Some Design/Implementation Principles
•
•
•
•
•
•
•
•
virtualization
indirection
soft state vs. hard state
fate sharing
randomization
expose faults, don’t suppress/ignore
caching
……
4
Original Internet Design Goals
[Clark’88]
In order of importance:
0
1.
2.
3.
4.
5.
6.
Connect existing networks
– initially ARPANET and ARPA packet radio network
Survivability
- ensure communication service even with network and router
failures
Support multiple types of services
Must accommodate a variety of networks
Allow distributed management
Allow host attachment with a low level of effort
Be cost effective
7. Allow resource accountability
5
Priorities
• The effects of the order of items in that list are
still felt today
– E.g., resource accounting is a hard, current research
topic
• Different ordering of priorities would make a
different architecture!
• How well has today’s Internet satisfied these
goals?
• Let’s look at them in detail
6
Summary: Internet
Architecture
• Packet-switched
datagram network
• IP is the “compatibility
layer”
– Hourglass architecture
– All hosts and routers run IP
• Stateless architecture
– No per flow state inside
network
TCP
UDP
IP
Satellite
Ethernet ATM
7
Summary: Minimalist Approach
• Dumb network
– IP provide minimal functionalities to support connectivity
• Addressing, forwarding, routing
• Smart end system
– Transport layer or application performs more
sophisticated functionalities
• Flow control, error control, congestion control
• Advantages
– Accommodate heterogeneous technologies (Ethernet,
modem, satellite, wireless)
– Support diverse applications (telnet, ftp, Web, X
windows)
– Decentralized network administration
• Beginning to show age
– Unclear what the solution will be  probably IPv6?
8
Questions
• What priority order would a commercial
design have?
• What would a commercially invented
Internet look like?
• What goals are missing from this list?
• Which goals led to the success of the
Internet?
9
Requirements for Today’s Internet
Some key requirements (“-ities”)
• Availability and reliability
– “Always on”, fault-tolerant, fast recovery from failures, …
• Quality-of-service (QoS) for applications
– fast response time, adequate quality for VoIP, IPTV, etc.
• Scalability
– millions or more of users, devices, …
• Mobility
– untethered access, mobile users, devices, …
• Security (and Privacy?)
– protect against malicious attacks, accountability of user actions?
• Manageability
– configure, operate and manage networks
– trouble-shooting network problems
• Flexibility, Extensibility, Evolvability, ……?
– ease of new service creation and deployment?
– evolvable to meet future needs?
10
End System Based Overlay/P2P
Services/Solutions
• General Concept of Overlays
• Some Examples
• End-System Multicast
– Rationale
– How to construct “self-organizing” overlay
– Performance in support conferencing applications
• Internet Indirection Infrastructure (i3)
– Motivation and Basic ideas
– Implementation Overview
– Applications
11
Overlay Networks
12
Overlay Networks
Focus at the application level
13
Overlay Networks
• A logical network built on top of a physical
network
– Overlay links are tunnels through the underlying network
• Many logical networks may coexist at once
– Over the same underlying network
– And providing its own particular service
• Nodes are often end hosts
– Acting as intermediate nodes that forward traffic
– Providing a service, such as access to files
• Who controls the nodes providing service?
– The party providing the service (e.g., Akamai)
– Distributed collection of end users (e.g., peer-to-peer)
14
Routing Overlays
• Alternative routing strategies
– No application-level processing at the overlay nodes
– Packet-delivery service with new routing strategies
• Incremental enhancements to IP
–
–
–
–
IPv6
Multicast
Mobility
Security
• Revisiting where a function belongs
– End-system multicast: multicast distribution by end
hosts
• Customized path selection
– Resilient Overlay Networks: robust packet delivery
15
IP Tunneling
• IP tunnel is a virtual point-to-point link
– Illusion of a direct link between two separated nodes
Logical view:
Physical view:
A
B
A
B
tunnel
E
F
E
F
• Encapsulation of the packet inside an IP
datagram
– Node B sends a packet to node E
– … containing another packet as the payload
16
6Bone: Deploying IPv6 over IP4
Logical view:
Physical view:
A
B
IPv6
IPv6
A
B
C
IPv6
IPv6
IPv4
Flow: X
Src: A
Dest: F
data
Src:B
Dest: E
Flow: X
Src: A
Dest: F
data
A-to-B:
IPv6
E
F
IPv6
IPv6
D
E
F
IPv4
IPv6
IPv6
tunnel
B-to-C:
IPv6 inside
IPv4
Src:B
Dest: E
Flow: X
Src: A
Dest: F
Flow: X
Src: A
Dest: F
data
data
B-to-C:
IPv6 inside
IPv4
E-to-F:
IPv6
17
MBone: IP Multicast
• Multicast
– Delivering the same data to many receivers
– Avoiding sending the same data many times
unicast
multicast
• IP multicast
– Special addressing, forwarding, and routing schemes
– Not widely deployed, so MBone tunneled between nodes
18
End-System Multicast
• IP multicast still is not widely deployed
– Technical and business challenges
– Should multicast be a network-layer service?
• Multicast tree of end hosts
– Allow end hosts to form their own multicast tree
– Hosts receiving the data help forward to others
19
RON: Resilient Overlay Networks
Premise: by building application overlay network, can
increase performance and reliability of routing
Princeton
Yale
application-layer
router
Two-hop (application-level)
Berkeley-to-Princeton route
Berkeley
20
RON Can Outperform IP Routing
• IP routing does not adapt to congestion
– But RON can reroute when the direct path is congested
• IP routing is sometimes slow to converge
– But RON can quickly direct traffic through intermediary
• IP routing depends on AS routing policies
– But RON may pick paths that circumvent policies
• Then again, RON has its own overheads
– Packets go in and out at intermediate nodes
• Performance degradation, load on hosts, and financial cost
– Probing overhead to monitor the virtual links
• Limits RON to deployments with a small number of nodes
21
Secure Communication Over Insecure
Links
• Encrypt packets at entry and decrypt at exit
• Eavesdropper cannot snoop the data
• … or determine the real source and destination
22
Communicating With Mobile Users
• A mobile user changes locations frequently
– So, the IP address of the machine changes often
• The user wants applications to continue
running
– So, the change in IP address needs to be hidden
• Solution: fixed gateway forwards packets
– Gateway has a fixed IP address
– … and keeps track of the mobile’s address changes
www.cnn.com
gateway
23
Unicast Emulation of Multicast
Stanford
Gatech
CMU
Berkeley
End Systems
Routers
24
IP Multicast
Gatech
Stanford
CMU
Berkeley
Routers with multicast support
•No duplicate packets
•Highly efficient bandwidth usage
Key Architectural Decision: Add support for multicast in IP layer
25
Key Concerns with IP Multicast
• Scalability with number of groups
– Routers maintain per-group state
– Analogous to per-flow state for QoS guarantees
– Aggregation of multicast addresses is complicated
• Supporting higher level functionality is difficult
– IP Multicast: best-effort multi-point delivery service
– End systems responsible for handling higher level functionality
– Reliability and congestion control for IP Multicast complicated
• Deployment is difficult and slow
– ISP’s reluctant to turn on IP Multicast
26
End System Multicast
CMU
Gatech
Stanford
Stan1
Stan2
Berk1
Berkeley
Overlay Tree
Gatech
Berk2
Stan
1
Stan2
CMU
Berk1
Berk2
27
Potential Benefits
• Scalability
– Routers do not maintain per-group state
– End systems do, but they participate in very few groups
• Easier to deploy
• Potentially simplifies support for higher level
functionality
– Leverage computation and storage of end systems
– For example, for buffering packets, transcoding, ACK aggregation
– Leverage solutions for unicast congestion control and reliability
28
Design Questions
• Is End System Multicast Feasible?
• Target applications with small and sparse
groups
• How to Build Efficient Application-Layer
Multicast “Tree” or Overlay Network?
– Narada: A distributed protocol for constructing efficient
overlay trees among end systems
– Simulation and Internet evaluation results to
demonstrate that Narada can achieve good performance
29
Performance Concerns
Gatech
Delay from CMU to
Berk1 increases
Stan1
Stan2
CMU
Berk1
Duplicate Packets:
Bandwidth Wastage
CMU
Gatech
Berk2
Stan1
Stan2
Berk1
Berk2
30
What is an efficient overlay tree?
• The delay between the source and receivers is small
• Ideally,
– The number of redundant packets on any physical link is low
Heuristic used:
– Every member in the tree has a small degree
– Degree chosen to reflect bandwidth of connection to Internet
CMU
Stan2
Stan1
Berk1
Berk2
High latency
Stan2
CMU
Stan2
Stan1
Gatech
Berk1
Berk2
CMU
Stan1
Gatech
High degree (unicast)
Berk1
Gatech
Berk2
“Efficient”
overlay
31
Why is self-organization hard?
• Dynamic changes in group membership
– Members may join and leave dynamically
– Members may die
• Limited knowledge of network conditions
– Members do not know delay to each other when they join
– Members probe each other to learn network related information
– Overlay must self-improve as more information available
• Dynamic changes in network conditions
– Delay between members may vary over time due to congestion
32
Performance Metrics
• Delay between members using Narada
• Stress, defined as the number of identical copies of a
packet that traverse a physical link
Gatech
Delay from CMU to
Berk1 increases
CMU
Stress = 2
CMU
Stan1
Stan2
Berk1
Gatech
Berk2
Stan1
Stan2
Berk
1
Berk2 33
ESM Conclusions
• Proposed in 1989, IP Multicast is not yet widely deployed
– Per-group state, control state complexity and scaling
concerns
– Difficult to support higher layer functionality
– Difficult to deploy, and get ISP’s to turn on IP Multicast
• Is IP the right layer for supporting multicast functionality?
• For small-sized groups, an end-system overlay approach
– is feasible
– has a low performance penalty compared to IP Multicast
– has the potential to simplify support for higher layer
functionality
– allows for application-specific customizations
34
Internet Indirection
Infrastructure (i3)
Motivations
• Today’s Internet is built around a unicast pointto-point communication abstraction:
– Send packet “p” from host “A” to host “B”
• This abstraction allows Internet to be highly
scalable and efficient, but…
• … not appropriate for applications that require
other communications primitives:
–
–
–
–
Multicast
Anycast
Mobility
…
35
Why?
• Point-to-point communication  implicitly
assumes there is one sender and one receiver,
and that they are placed at fixed and wellknown locations
– E.g., a host identified by the IP address 128.32.xxx.xxx is
located in Berkeley
36
IP Solutions
• Extend IP to support new communication
primitives, e.g.,
– Mobile IP
– IP multicast
– IP anycast
• Disadvantages:
– Difficult to implement while maintaining Internet’s scalability
(e.g., multicast)
– Require community wide consensus -- hard to achieve in
practice
37
Application Level Solutions
• Implement the required functionality at
the application level, e.g.,
– Application level multicast (e.g., Narada, Overcast,
Scattercast…)
– Application level mobility
• Disadvantages:
– Efficiency hard to achieve
– Redundancy: each application implements the same
functionality over and over again
– No synergy: each application implements usually only one
service; services hard to combine
38
Key Observation
• Virtually all previous proposals use
indirection, e.g.,
– Physical indirection point  mobile IP
– Logical indirection point  IP multicast
“Any problem in computer science can
be solved by adding a layer of indirection”
39
i3 Solution
Build an efficient indirection layer
on top of IP
• Use an overlay network to implement this layer
– Incrementally deployable; don’t need to change IP
Application
Indir.
TCP/UDP
layer
IP
40
Internet Indirection
Infrastructure (i3): Basic Ideas
• Each packet is associated an identifier id
• To receive a packet with identifier id, receiver R
maintains a trigger (id, R) into the overlay network
data id
Sender
Receiver (R)
data R
id R
trigger
41
Service Model
• API
– sendPacket(p);
– insertTrigger(t);
– removeTrigger(t) // optional
• Best-effort service model (like IP)
• Triggers periodically refreshed by endhosts
• ID length: 256 bits
42
Mobility
• Host just needs to update its trigger as it
moves from one subnet to another
Sender
id R2
R1
Receiver
(R1)
Receiver
(R2)
43
Multicast
• Receivers insert triggers with same identifier
• Can dynamically switch between multicast and
unicast
data id
Sender
data R1
id R1
Receiver (R1)
id R2
data R2
Receiver (R2)
44
Anycast
• Use longest prefix matching instead of exact
matching
– Prefix p: anycast group identifier
– Suffix si: encode application semantics, e.g., location
data p|a
Sender
data R1
p|s1 R1
p|s2 R2
Receiver (R1)
Receiver (R2)
p|s3 R3
Receiver (R3)
45
Service Composition: Sender
Initiated
• Use a stack of IDs to encode sequence of
operations to be performed on data path
• Advantages
– Don’t need to configure path
– Load balancing and robustness easy to achieve
Transcoder (T)
data idT,id
Sender
data id
data T,id
idT T
data R
id R
Receiver (R)
46
Service Composition: Receiver
Initiated
• Receiver can also specify the operations to be
performed on data
data id
Sender
Firewall (F)
data R
data F,R
idF F
Receiver (R)
data idF,R
id idF,R
47
Quick Implementation
Overview
• i3 is implemented on top of Chord
– But can easily use CAN, Pastry, Tapestry, etc
• Each trigger t = (id, R) is stored on the
node responsible for id
• Use Chord recursive routing to find best
matching trigger for packet p = (id, data)
48
Routing Example
• R inserts trigger t = (37, R); S sends packet p = (37, data)
• An end-host needs to know only one i3 node to use i3
– E.g., S knows node 3, R knows node 35
S
m-1
0
2
S
3
send(37, data)
20
[8..20]
7
7
[4..7]
3
[40..3]
Chord circle
37 R
[21..35]
41
41
20
37 R
35
[36..41]
trigger(37,R)
35
send(R, data)
R
R
49
Optimization #1: Path Length
• Sender/receiver caches i3 node mapping a
specific ID
• Subsequent packets are sent via one i3 node
[8..20]
[4..7]
data 37
[42..3]
Sender (S)
cache node
[21..35]
[36..41]
data R
37 R
Receiver (R)
50
Optimization #2: Triangular Routing
• Use well-known trigger for initial rendezvous
• Exchange a pair of (private) triggers well-located
• Use private triggers to send data traffic
[8..20]
[4..7]
37
data
[2] 30
2 S
Sender (S)
[42..3]
S
[30]
[21..35]
[36..41]
[2] R
37 R
data
R
2
[30]
30 R
Receiver (R)
51
Example 1: Heterogeneous Multicast
• Sender not aware of transformations
S_MPEG/JPEG
send(R1, data)
send(id, data)
id_MPEG/JPEG S_MPEG/JPEG
Sender
(MPEG)
Receiver R1
(JPEG)
send((id_MPEG/JPEG, R1), data)
id
(id_MPEG/JPEG, R1)
id
R2
send(R2, data)
Receiver R2
(MPEG)
52
Example 2: Scalable Multicast
• i3 doesn’t provide direct support for scalable multicast
– Triggers with same identifier are mapped onto the same i3 node
• Solution: have end-hosts build an hierarchy of trigger
of bounded degree
(g, data)
g
x
g g
R1 R2
R2
(x, data)
x
R3
R3
x
R4
R1
R4
53
Example 2: Scalable Multicast
(Discussion)
Unlike IP multicast, i3
1. Implement only small scale replication  allow
infrastructure to remain simple, robust, and
scalable
2. Gives end-hosts control on routing  enable
end-hosts to
–
–
Achieve scalability, and
Optimize tree construction to match their needs, e.g., delay,
bandwidth
54
Example 3: Load Balancing
• Servers insert triggers with IDs that have random
suffixes
• Clients send packets with IDs that have random suffixes
send(1010 0110,data)
S1
1010 0010 S1
A
S2
1010 0101 S2
1010 1010 S3
S3
send(1010 1110,data)
B
1010 1101 S4
S4
55
Example 4: Proximity
• Suffixes of trigger and packet IDs encode the
server and client locations
S2
S3
S1
send(1000 0011,data)
1000 0010
1000 1010 S2
1000 1101 S3
S1
56
Outline
• Implementation
• Examples
• Security
 Applications
 Protection against DoS attacks
– Routing as a service
– Service composition platform
57
Applications: Protecting Against DoS
• Problem scenario: attacker floods the
incoming link of the victim
• Solution: stop attacking traffic before it
arrives at the incoming link
– Today: call the ISP to stop the traffic, and hope for the
best!
• Our approach: give end-host control on what
packets to receive
– Enable end-hosts to stop the attacks in the network
58
Why End-Hosts (and not Network)?
• End-hosts can better react to an attack
– Aware of semantics of traffic they receive
– Know what traffic they want to protect
• End-hosts may be in a better position to
detect an attack
– Flash-crowd vs. DoS
59
Some Useful Defenses
1. White-listing: avoid receiving packets on
arbitrary ports
2. Traffic isolation:
–
–
Contain the traffic of an application under attack
Protect the traffic of established connections
3. Throttling new connections: control the rate
at which new connections are opened (per
sender)
60
1. White-listing
• Packets not addressed to open ports are dropped in
the network
– Create a public trigger for each port in the white list
– Allocate a private trigger for each new connection
IDR
[ID
data
P
S]ID
IDS S
Sender (S)
S [IDR]
[IDS] R
IDP R
IDP – public trigger
data R
IDS [IDR]
IDR R
Receiver (R)
IDS, IDR – private triggers
61
2. Traffic Isolation
• Drop triggers being flooded without affecting
other triggers
– Protect ongoing connections from new connection
requests
– Protect a service from an attack on another services
Transaction server
Legitimate client
(C)
ID1 V
ID2 V
Victim (V)
Web server
Attacker
(A)
62
2. Traffic Isolation (cont’d)
• Drop triggers being flooded without affecting
other triggers
– Protect ongoing connections from new connection
requests
– Protect a service from an attack on another services
Transaction server
Legitimate client
(C)
ID1 V
Victim (V)
Web server
Attacker
(A)
Traffic of transaction server
protected from attack on web server
63
3. Throttling New Connections
• Redirect new connection requests to a
gatekeeper
– Gatekeeper has more resources than victim
– Can be provided as a 3rd party service
Gatekeeper (A)
IDC C
Client (C)
X S
Server (S)
IDP A
64
Service Composition Platform
• Goal: allow third-parties and end-hosts to
easily insert new functionality on data path
– E.g., firewalls, NATs, caching, transcoding, spam filtering,
intrusion detection, etc..
• Why i3?
– Make middle-boxes part of the architecture
– Allow end-hosts/third-parties to explicitly route through
middle-boxes
65
Example
• Use Bro system to provide intrusion detection
for end-hosts that desire so
Bro (middle-box)
M
(idM:idBA, data)
(idBA, data)
idM M
client A
idAB A
(idAB, data)
i3
idBA B
server B
(idM:idAB, data)
66
Design Principles
1) Give hosts control on routing
–
–
–
A trigger is like an entry in a routing table!
Flexibility, customization
End-hosts can
•
•
•
•
•
Source route
Set-up acyclic communication graphs
Route packets through desired service points
Stop flows in infrastructure
…
2) Implement data forwarding in infrastructure
–
Efficiency, scalability
67
Design Principles (cont’d)
Host
Data plane
Internet &
Infrastructure overlays
p2p &
End-host overlays
i3
Infrastructure
Control plane
Data plane
Control plane
Control plane
Data plane
68
Conclusions
• Indirection – key technique to implement
basic communication abstractions
– Multicast, Anycast, Mobility, …
• I3
– Advocates for building an efficient Indirection Layer on top
of IP
– Explore the implications of changing the communication
abstraction; already done in other fields
• Direct addressable vs. associative memories
• Point-to-point communication vs. Tuple space (in Distributed
systems)
69
Requirements for Today/Tomorrow’s
Internet?
Some key requirements (“-ities”)
• Availability and reliability
– “Always on”, fault-tolerant, fast recovery from failures, …
• Quality-of-service (QoS) for applications
– fast response time, adequate quality for VoIP, IPTV, etc.
• Scalability
– millions or more of users, devices, …
• Mobility
– untethered access, mobile users, devices, …
• Security (and Privacy?)
– protect against malicious attacks, accountability of user actions?
• Manageability
– configure, operate and manage networks
– trouble-shooting network problems
• Flexibility, Extensibility, Evolvability, ……?
– ease of new service creation and deployment?
– evolvable to meet future needs?
70
Key Issues, Challenges, Solutions …
A More Network-Centric View
• New Naming/Addressing?
– Separating “identifiers” and “locators” to better support mobility
– “semantic-free” flat id space ?
– Data centric?
– Role of “search” on naming, etc.
• Scalable and Robust Routing
–
–
–
–
Better and more adaptive to failures, and other network events
Also better support for network management, security, …
how to perform routing on “flat id” space?
Or shall we decouple routing from “naming” or “addressing” ?
• Manageability
– “Centralized” approach
– …?
• Security (and Privacy?)
– More “accountable” networks, e.g., through “naming,” or id
management?
– …?
71
Key Issues, Challenges, Solutions …
Applications and Technology are Dual Drivers !
• More devices are connected, novel technologies, disruptive
new applications/services
– Google, and its impact of how we access Internet today
– social networking: Facebook, MySpace, …
– iPod/iTune, Skype, BitTorrent, P2P video streaming, YouTube,
Hulu.com, Kindle and Amazon, Ebay, …
– smart phones, etc., “third screen”
– “Cloud computing”, data centers, and “software as services”
–
• Flexibility, Evolvability, and Economic Viability of Network
Architectures!
– It’s “service”, stupid!
• But is network a (shared) “utility”, “commodity”, or
“service” ?
– “Networks” as services (e.g., VPNs), network security as services, …
– Network Virtualization and Virtualized Network Architectures
– User/application “customize-able” network services?
Ultimately, networks should be “invisible” !
72