Transcript
CS433/533: Computer Networks
http://zoo.cs.yale.edu/classes/cs433/ 1/10/2012
Outline Administrative trivia’s What is a network protocol? A brief introduction to the Internet: past
and present Challenges of Internet network and app Summary
2
Personnel Instructor
Y. Richard Yang,
[email protected], AKW 308A • office hours – TTh 11:00-12:00 or by appointment – please feel free to stop by if you see I am in my office
Teaching assistant
Harry Liu
3
Textbook Textbook
Computer Networking: A TopDown Approach, 5/e by Kurose and Ross
Reference books
Computer Networks by A. Tanenbaum Computer Networks, A Systems Approach by L. Peterson and B. Davie TCP/IP Illustrated, Volume 1: The Protocols by W. Richard Stevens Java Network Programming, by Elliotte Harold on
Resources
http://zoo.cs.yale.edu/classes/cs433
4
What are the Goals of this Course? Learn design principles and techniques of: the Internet infrastructure large-scale Internet applications See how the principles and techniques apply
and adapt in real world:
real examples from the Internet
5
What Do You Need To Do? Please return the class background survey at the end
of the class
help us determine your background
help us determine the depth, topics, and assignments
suggest topics that you want to be covered (if you think of a topic later, please send me email)
Your workload homework assignments
• written assignments • programming assignments
two exams
6
Grading Exams
30%
Assignments
60%
Class Participation
10%
Subject to change after I know more about your background More important is what you realize/learn than the grades !! 7
Questions?
Outline Administrative trivia’s What is a network protocol?
9
What is a Network Protocol? A network protocol defines the format and
the order of messages exchanged between two or more communicating entities, as well as the actions taken on the transmission and/or receipt of a message or other events.
10
Example Protocol: Simple Mail Transfer Protocol (SMTP) Messages from a client to a mail server HELO MAIL FROM:
RCPT TO: DATA QUIT Messages from a mail server to a client status code
• The first digit of the response broadly indicates the success, failure, or progress of the previous command. – 1xx - Informative message – 2xx - Command ok – 3xx - Command ok so far, send the rest of it. – 4xx - Command was correct, but couldn't be performed for some reason. – 5xx - Command unimplemented, or incorrect, or a serious program error occurred.
content
Command: %telnet netra.cs.yale.edu smtp
user agent
mail server
SMTP
SMTP mail server
user agent
SMTP POP3, IMAP SMTP
outgoing message queue user mailbox
user agent mail server
user agent user agent
user agent 11
Example: TCP Reliability Host A
Host B
12
Protocol Standardization Most widely used protocols are defined in standards Why standard?
13
Internet Standardization Process All standards of the Internet are published as RFC
(Request for Comments)
e.g., the SMTP protocol is specified in RFC821 but not all RFCs are Internet Standards:
http://zoo.cs.yale.edu/classes/cs433/readings/interestingrfcs.html
A typical (but not the only) way of standardization: Internet draft RFC proposed standard draft standard (requires 2 working implementations) Internet standard (declared by Internet Architecture Board) David Clark, 1992: We reject: kings, presidents, and voting. We believe in: rough consensus and running code.
14
Outline Administrative trivia’s What is a network protocol? A brief introduction to the Internet past present
15
A Brief History of the Internet: Packet Switching and ARPANET 1957
USSR launched Sputnik; US DoD formed Advanced Research Projects Agency (ARPA)
1961
First paper by Len Kleinrock on packet switching theory
Paul Baran from RAND on design of packet switching networks
1964
1965-1968
ARPANET plan 3 independent implementation Bolt Beranek and Newman, Inc. (BBN), a small company, was awarded Packet Switch contract to build Interface Message Processors (IMPs)
16
Initial ARPANET 1969
ARPANET commissioned: 4 nodes, 50kbps
17
Initial Expansion of the ARPANET
Dec. 1969
July 1970
Apr. 1972
Mar. 1971
Sept. 1972
RFC 527: ARPAWOCKY; RFC 602: The Stockings Were Hung by the Chimney with Care
18
The Internet Becomes a Network of Networks 1970: ALOHAnet, the first packet radio network,
developed by Norman Abramson, Univ of Hawaii, becomes operational
1973: Bob Kahn poses the Internet problem---how to
connect ARPANET, packet radio network, and satellite network
1974: Vint Cerf, Bob Kahn publish initial design of TCP
(NCP) to connect multiple networks - 1978: TCP (NCP) split to TCP/IP - 1983: TCP (NCP) converted to TCP/IP (Jan. 1)
19
Growth of the Internet 1981: BITNET (Because It’s Time NETwork) between CUNY and Yale 1986: NSF builds NSFNET as backbone, links 6 supercomputer centers,
56 kbps; this allows an explosion of connections, especially from universities 1987: 10,000 hosts 1988: NSFNET backbone upgrades to 1.5Mbps 1989: 100,000 hosts RFC 1121: Act One – The Poem WELCOME by Leonard Kleinrock
We've gathered here for two days to examine and debate And reflect on data networks and as well to celebrate. To recognize the leaders and recount the path we took. We'll begin with how it happened; for it's time to take a look. Yes, the history is legend and the pioneers are here. Listen to the story - it's our job to make it clear. We'll tell you where we are now and where we'll likely go. So welcome to ACT ONE, folks. Sit back - enjoy the show!! 20
Web and Commercialization of the Internet 1990: ARPANET ceases to exist 1991: NSF lifts restrictions on the commercial use of the Net;
Berners-Lee of European Organization for Nuclear Research (CERN) released World Wide Web 1992: 1 million hosts (RFC 1300: Remembrances of Things Past) For a link of interesting RFCs, please see
http://zoo.cs.yale.edu/classes/cs433/readings/interestingrfcs.html
For more on Internet history, please see
http://www.zakon.org/robert/internet/timeline/
21
Growth of the Internet in Terms of Number of Hosts Number of Hosts on the Internet: Aug. 1981 213 Oct. 1984 1,024 Dec. 1987 28,174 Oct. 1990 313,000 Jul. 1993 1,776,000 Jul. 1996 19,540,000 Jul. 1999 56,218,000 Jul. 2004 285,139,000 Jul. 2007 489,774,000 Jul. 2011 849,869,781
CAIDA router level view
22
Outline Administrative trivia’s What is a network protocol? A brief introduction to the Internet past present
23
Internet Physical Infrastructure Residential access
Cable Fiber DSL Wireless
ISP
Backbone ISP
ISP
The Internet is a network Campus access, e.g.,
Ethernet Wireless
of networks Each individually administrated network is called an Autonomous System (AS)
24
Access: Fiber to the Premises (FTTP) Deployed by Verizon
(all locations) and AT&T (new build areas) One of the largest comm. construction projects
25
Access: Fiber to the Premises (FTTP) Highest theoretical capacity per user: 1 G bps up to 150Mbps downstream, 35 Mbps upstream Services analog and digital video video viewable with and without set-top converter voice interfaces with existing phone, data, video cabling
http://www22.verizon.com/about/community/tx/technology/fios_fact.html
26
FTTP Architecture
27
FTTP Architecture Optical Network Terminal (ONT) box outside dwelling or business Fiber Distribution Terminal (FDT) in poles or pedestals Fiber Distribution Hub (FDH) at street cabinet Optical Line Terminal (OLT) at central office
28
FTTP Architecture: To Home
29
FTTP Architecture: Fiber Distribution Terminal (FDT)
30
FTTP Architecture: Central to Fiber Distribution Hub (FDH) - Backbone fiber ring on primary arterial streets (brown) - Local distribution fiber plant (red) meets backbone at cabinet
FDH
31
Access: DSL Compared with FTTP, copper from cabinet
(DSLAM) to home
DSLAM
32
Access: Cable
Also called Hybrid Fiber-coaxial Cable (HFC)
Fiber node: 500 - 1K homes Distribution hub: 20K - 40 K homes Regional headend: 200 K - 400 K homes 33
Campus Network Internet
CE F2
F1 (Firewall)
S2
R1
S1
LB2 IPS2
IPS3
S6
LB1 (Load balancer)
IPS1(Intrusion prevention)
S4
S5
S3
tier-1
VLAN 200 VLAN 100 Tier-3
Tier-2
VLAN 300
VLAN Tier-1 400
Logger 34
Recall: Internet Physical Infrastructure Residential access
Cable Fiber DSL Wireless
ISP
Backbone ISP
ISP
The Internet is a network Campus access, e.g.,
Ethernet Wireless
of networks Each individually administrated network is called an Autonomous System (AS)
35
Yale Internet Connection cicada:~% traceroute www.cs.utexas.edu traceroute to net6.cs.utexas.edu (128.83.120.139), 64 hops max, 52 byte packets 1 arubacentral-vlan30-router.net.yale.internal (172.28.204.129) 1.540 ms 1.200 ms 1.344 ms 2 10.1.1.13 (10.1.1.13) 2.854 ms 1.072 ms 1.237 ms 3 qwest-asr.net.yale.internal (10.1.4.5) 1.139 ms 1.327 ms 1.281 ms 4 10.1.3.99 (10.1.3.99) 2.120 ms 1.343 ms 1.874 ms 5 cen-yale.net.yale.edu (130.132.251.74) 1.558 ms 1.634 ms 1.592 ms 6 nox300gw1-vl-706-nox-yale.nox.org (207.210.143.89) 5.570 ms 6.367 ms 5.208 ms 7 nox300gw1-vl-706-nox-yale.nox.org (207.210.143.89) 5.000 ms 5.008 ms 5.663 ms 8 nox1sumgw1-vl-803-nox.nox.org (192.5.89.237) 5.765 ms 5.909 ms 5.145 ms 9 nox1sumgw1-peer-nox-internet2-192-5-89-18.nox.org (192.5.89.18) 27.455 ms 27.232 ms 27.344 ms 10 64.57.28.36 (64.57.28.36) 38.111 ms 126.638 ms 37.985 ms 11 xe-1-1-0.0.rtr.hous.net.internet2.edu (64.57.28.57) 51.982 ms 106.096 ms 51.817 ms 12 rt1-hardy-hstn-xe-0-1-0-3018.tx-learn.net (74.200.187.6) 52.988 ms 52.937 ms 53.307 ms 13 tx-bb-i2-hstn.tx-learn.net (74.200.187.26) 53.444 ms 53.515 ms 53.288 ms 14 aust-utnoc-core-ge-5-0-0-706.tx-bb.net (192.88.12.50) 54.636 ms 54.703 ms 55.054 ms 15 192.88.12.26 (192.88.12.26) 55.056 ms 74.044 ms 54.926 ms 16 ser10-v702.gw.utexas.edu (128.83.10.1) 55.208 ms 54.803 ms 55.117 ms 17 cs-nocb10-v690.gw.utexas.edu (146.6.10.34) 55.013 ms 55.099 ms 55.045 ms 18 cs65k-cs45k-po1-p2p.aces.utexas.edu (128.83.37.66) 54.960 ms 55.005 ms 55.551 ms 19 net6.cs.utexas.edu (128.83.120.139) 55.015 ms 54.956 ms 54.847 ms 36
Internet2
\
http://www.internet2.edu/pubs/Internet2%20Planned%20100G%20Infrastructure%20Topology.pdf
37
Internet2
http://atlas.grnoc.iu.edu/atlas.cgi?map_name=Internet2%20IP%20Layer 38
http://www.qwest.com/largebusiness/enterprisesolutions/networkMaps/preloader.swf
Qwest Backbone Map
39
Level 3 Network
http://maps.level3.com/default/
40
Internet ISP Connectivity Roughly hierarchical
Divided into tiers Tier-1 ISPs are also called backbone providers, e.g., AT&T, Verizon, Sprint, Level 3, Qwest
An ISP runs (private)
Points of Presence (PoP) where its customers and other ISPs connect to it
ISPs also connect at
(public) Internet Exchange Point (IXP)
public peering
http://en.wikipedia.org/wiki/List_of_Internet_exchange_points_by_size
41
User Base of Large Internet Sites in U.S. (Oct. 2010)
42
Internet (Consumer) Traffic
43
Outline Administrative trivia’s What is a network protocol? A brief introduction to the Internet: past
and present Challenges of Internet network and app
44
Scale “Developers who have worked at the small scale might be asking themselves why we need to bother when we could just use some kind of out-of thebox solution. For small-scale applications, this can be a great idea. We save time and money up front and get a working and serviceable application. The problem comes at larger scales—there are no offthe-shelf kits that will allow you to build something like Amazon... There’s a good reason why the largest applications on the Internet are all bespoke creations: no other approach can create massively scalable applications within a reasonable budget.” http://www.evontech.com/symbian/55.html
45
Sharing a Shared Infrastructure question: how to allocate network
resources among users?
x1 1 x2
1 x3 46
Decentralized (“Selfish”) Users preferred
2
20 230
less 4 preferred
0 120 10
1
3 3
310 30
47
Decentralized (“Selfish”) Users preferred
2
230 20
less 4 preferred
0 120 10
1
3 3
310 30
48
Autonomous (“Selfish”) Users Assume each link has a latency function le(x):
latency of link e when x amount of traffic goes through e: l(x) = x total traffic
s
t l(x) = 1
Q: other examples of undesirable user behaviors? 49
Flexibility vs Performance
50
What Will We Cover? A tentative schedule will be posted at:
http://zoo.cs.yale.edu/classes/cs433/schedule.html
Network architecture and design principles Layered network arch; e2e principle Application architecture and design principles application paradigms; high performance network app. HTTP/Web, Email, DNS, Content distribution
Transport transport services reliability; distributed resource allocation; primal-dual transport protocols: TCP/UDP
51
What Will We Cover? Network network services distributed, asynchronous, autonomous routing algorithms; scalable router design IP/IPv6; mobile IP; cellular networks Link and physical multiple access; queueing analysis; capacity analysis Ethernet, 802.11, CDMA, bluetooth Multimedia networking principle of application adaptation; scheduling/QoS audio/video applications Network security security primitives; BAN logic, SSL 52
Summary Course administration A protocol defines the format and the order of messages exchanged
between two or more communicating entities, as well as the actions taken on the transmission and/or receipt of a message or other events. The past:
facts:
some implications of the past:
• The Internet started as ARPANET in late 1960s • The initial link bandwidth was 50 kbps • The number of hosts at the end of 1969 was 4
• ARPANET is sponsored by ARPA design should survive failures • The initial IMPs were very simple keep the network simple need a network to connect networks • Many networks
Current: The number of hosts connected to the Internet is > 800 millions The backbone speed of the current Internet is about 10/40 Gbps The Internet is roughly hierarchical where ISPs interconnect at PoP and IXP Needs to handle scale, decentralization
53
Preview We have only looked at the
topology/connectivity of the Internet
a communication network is a mesh of interconnected devices
A fundamental question: how is data
transferred through a network?
54
Backup Slides
Challenge of the Internet: Characterizing Internet Topology
56
Challenge of the Internet: Power Law? Some researchers
found that the outdegree Internet AS connectivity graph satisfies Power Law Does it really satisfy power law? If so, why?
Exponent = slope
R = -0.74
R
Dec’98
Rank: nodes in decreasing outdegree order Note that the plot is a line in log-log scale 57
An Example: Network News Transport Protocol (NNTP) Messages from a client to a news server
help list active group article next post
status code
content
Messages from a news server to a client • The first digit of the response broadly indicates the success, failure, or progress of the previous command. – 1xx - Informative message – 2xx - Command ok – 3xx - Command ok so far, send the rest of it. – 4xx - Command was correct, but couldn't be performed for some reason. – 5xx - Command unimplemented, or incorrect, or a serious program error occurred.
58
Local Access: ADSL
Asymmetrical Digital Subscriber Loop (ADSL) Telephone company’s solution to “last mile
problem”
59
Yale Internet Connectivity: Qwest cyndra.cs.yale.edu% /usr/sbin/traceroute www.synopsis.com traceroute to www.synopsis.com (198.182.60.11), 30 hops max, 38 byte packets
1 anger.net.yale.edu (128.36.229.1) 0.767 ms 1.740 ms 1.452 ms 2 bifrost.net.yale.edu (130.132.1.100) 0.680 ms 0.597 ms 0.567 ms 3 bos-edge-02.inet.qwest.net (63.145.0.13) 4.897 ms 5.257 ms 5.294 ms 4 bos-core-01.inet.qwest.net (205.171.28.13) 4.918 ms 5.405 ms 4.898 ms 5 ewr-core-02.inet.qwest.net (205.171.8.114) 11.998 ms 11.688 ms 11.647 ms 6 ewr-brdr-02.inet.qwest.net (205.171.17.130) 11.432 ms 12.036 ms 11.474 ms 7 205.171.1.98 (205.171.1.98) 7.547 ms 7.727 ms 7.632 ms 8 ae-1-56.bbr2.NewYork1.Level3.net (4.68.97.161) 7.513 ms 7.466 ms ae-154.bbr2.NewYork1.Level3.net (4.68.97.97) 7.585 ms 9 ge-0-1-0.bbr2.SanJose1.Level3.net (64.159.1.130) 75.468 ms so-0-00.bbr1.SanJose1.Level3.net (64.159.1.133) 75.630 ms ge-0-10.bbr2.SanJose1.Level3.net (64.159.1.130) 75.126 ms 10 ge-9-0.hsa1.SanJose1.Level3.net (4.68.123.40) 75.499 ms ge-80.hsa1.SanJose1.Level3.net (4.68.123.8) 76.429 ms 76.431 ms 11 h1.synopsysmv.bbnplanet.net (4.25.120.46) 86.414 ms 85.996 ms 85.896 ms 12 198.182.56.45 (198.182.56.45) 88.705 ms 92.585 ms 90.412 ms
Note: which link Yale will use depends on its current load balancing. It may not be qwest. 60
Yale Internet Connectivity: AT&T cicada.cs.yale.edu% /usr/sbin/traceroute www.amazon.com
1 anger.net.yale.edu (128.36.229.1) 0.906 ms 1.028 ms 0.784 ms 2 bifrost.net.yale.edu (130.132.1.100) 0.798 ms 0.722 ms 0.836 ms 3 12.175.96.1 (12.175.96.1) 0.861 ms 0.869 ms 0.804 ms 4 12.124.179.65 (12.124.179.65) 2.278 ms 2.276 ms 2.223 ms 5 gbr5-p80.n54ny.ip.att.net (12.123.1.202) 2.524 ms 2.314 ms 2.169 ms 6 tbr1-p013201.n54ny.ip.att.net (12.122.11.9) 3.212 ms 3.203 ms 3.560 ms 7 ggr2-p310.n54ny.ip.att.net (12.123.3.105) 3.045 ms 2.468 ms 2.419 ms 8 sl-bb20-nyc-12-0.sprintlink.net (144.232.8.49) 3.518 ms 2.748 ms 2.951 ms 9 sl-bb26-nyc-6-0.sprintlink.net (144.232.13.9) 4.690 ms 4.460 ms 49.531 ms 10 sl-bb23-pen-12-0.sprintlink.net (144.232.20.95) 7.191 ms 7.202 ms 7.033 ms 11 sl-bb22-pen-14-0.sprintlink.net (144.232.8.178) 7.131 ms 7.245 ms 7.096 ms 12 sl-bb21-pen-15-0.sprintlink.net (144.232.16.29) 7.100 ms 7.423 ms 8.049 ms 13 sl-bb23-rly-0-0.sprintlink.net (144.232.20.32) 10.777 ms 10.826 ms 11.049 ms 14 sl-st20-ash-11-0.sprintlink.net (144.232.20.150) 11.281 ms 10.948 ms 10.730 ms 15 sl-amazon-4-0.sprintlink.net (144.223.246.18) 10.562 ms 10.572 ms 11.381 ms
61
Network Access Point
62
Access: DSL Up to 25 Mbps per customer Currently a few Mbps downstream, and a
few Mbps upstream
63
Yale Internet Connection: Internet2 (2009) cicada:~% traceroute www.cs.utexas.edu traceroute to www.cs.utexas.edu (128.83.120.155), 30 hops max, 40 byte packets 1 anger.net.yale.edu (128.36.232.1) 0.386 ms 0.190 ms 0.266 ms 2 bifrost.net.yale.edu (130.132.1.100) 0.477 ms 0.437 ms 0.408 ms 3 nox230gw1-AT-8-1-540-NoX-YALE.nox.org (192.5.89.69) 5.367 ms 5.058 ms 5.686 ms 4 nox230gw1-PEER-NoX-NOX-192-5-89-10.nox.org (192.5.89.10) 10.432 ms 10.407 ms 10.411 ms 5 washng-nycmng.abilene.ucaid.edu (198.32.8.85) 14.673 ms 14.664 ms 15.164 ms 6 atlang-washng.abilene.ucaid.edu (198.32.8.65) 30.902 ms 30.546 ms 30.755 ms 7 hstnng-atlang.abilene.ucaid.edu (198.32.8.33) 58.883 ms 50.124 ms 50.133 ms 8 aus-core-so0-1-0-0.tx-bb.net (192.88.12.21) 53.591 ms 54.042 ms 53.812 ms 9 192.88.12.90 53.812 ms 53.685 ms 53.685 ms 10 ser9-v703.gw.utexas.edu (128.83.9.1) 54.058 ms 54.055 ms 54.305 ms 11 128.83.37.42 54.179 ms 54.054 ms 53.927 ms 12 net2.cs.utexas.edu (128.83.120.155) 53.927 ms 53.552 ms 54.423 ms
64
ATT Global Backbone IP Network
From http://www.business.att.com 65
AT&T USA Backbone Map
From AT&T web site.
66
How Much Data? Internet traffic 17 EB (2011) Google processes 20 PB a day (2008) Size of World’s digital content 500 EB
640K ought to be enough for anybody.
http://en.wikipedia.org/wiki/Exabyte
1 PB = 1000 TB 1EB = 1000 PB
Present Internet: Likely Web-based The Internet infrastructure has better
support for HTTP than other protocols A trend of software applications: From the desktop to the browser SaaS == Web-based applications Examples: Google Maps/Doc, Facebook
How do we deliver highly-interactive Web-
based applications?
AJAX (asynchronous JavaScript and XML) For better, or for worse…
Evolving Computing Models Do it yourself (build your own data centers) Utility computing Why buy machines when you can rent cycles? Examples: Amazon’s EC2, GoGrid, AppNexus Platform as a Service (PaaS) Give me nice API and take care of the implementation Example: Google App Engine Software as a Service (SaaS)
Just run it for me! Example: Gmail; MS Exchange; MS Office Online
Data centers http://www.youtube.com/watch?v=WBIl0cu
rTxU
Google http://www.youtube.com/watch?v=zRwPSF
pLX8I
70
Internet2
Source: http://www.internet2.edu/info/
71
