! 1 1
Course Website: http://www.cs.sjtu.edu.cn /~jdyu/ teaching/cn/index.html About Myself: Jiadi Yu, Assistant Prof., Ph.D Office Room: 3-129, SEIEE E-Mail: jdyu@cs.sjtu.edu.cn 1 2
! Computer NetworksFourth Edition Andrew S. Tanenbaum Vrije Universiteit Amsterdam, The Netherlands ISBN 7-302-07815-7/TP.5697 2004-01 1 3
! A. S. Tenenbaum 2004-08 2001-07 William Stallings 2001-05 Douglas E. Comer 2000-08 TCP/IP 1993-12 2001-06 1 4
1! 1. 2. 3. 1 5
! Internet 1 6
! Client/Server 1 7
! 1 8
! Client/Server 1 9
Client/ServerC/S! 1 2 3 1 2 3 WS WS WS WS WS WS 1 10
! Internet 1 11
! 1 12
! 哪 么 1 13
! H 1 R 1 H 2 R 2 R i H 3 R j R k H m H n 1 14
! 1 15
! 1 16
! 1 17
! 1 18
What s the Internet millions of connected computing devices: hosts = end systems router server workstation mobile running network apps local ISP communication links fiber, copper, radio, satellite regional ISP transmission rate = bandwidth routers: forward packets (chunks of data) company network 1 19
Cool internet appliances IP picture frame http://www.ceiva.com/ Web-enabled toaster + weather forecaster World s smallest web server http://www-ccs.cs.umass.edu/~shri/ipic.html Internet phones 1 20
What s the Internet protocols control sending, receiving of msgs e.g., TCP, IP, HTTP, FTP, PPP Internet: network of networks router server local ISP workstation mobile loosely hierarchical public Internet versus private intranet regional ISP Internet standards RFC: Request for comments IETF: Internet Engineering Task Force company network 1 21
What s the Internet: a service view communication infrastructure enables distributed applications: Web, email, games, e- commerce, file sharing communication services provided to apps: Connectionless unreliable connection-oriented reliable 1 22
What s a protocol? human protocols: what s the time? I have a question introductions specific msgs sent specific actions taken when msgs received, or other events network protocols: machines rather than humans all communication activity in Internet governed by protocols protocols define format, order of msgs sent and received among network entities, and actions taken on msg transmission, receipt 1 23
What s a protocol? a human protocol and a computer network protocol: Hi Hi Got the time? 2:00 Q: Other human protocols? time TCP connection request TCP connection response Get http://www.awl.com/kurose-ross <file> 1 24
Network Structure 1 25
A closer look at network structure: network edge: applications and hosts network core: routers network of networks access networks, physical media: communication links 1 26
The network edge: end systems (hosts): run application programs e.g. Web, email at edge of network client/server model client host requests, receives service from always-on server e.g. Web browser/server; email client/server peer-peer model: minimal (or no) use of dedicated servers e.g. Gnutella, KaZaA, Skype 1 27
Network edge: connection-oriented service Goal: data transfer between end systems handshaking: setup (prepare for) data transfer ahead of time Hello, hello back human protocol set up state in two communicating hosts TCP - Transmission Control Protocol Internet s connectionoriented service TCP service [RFC 793] reliable, in-order bytestream data transfer loss: acknowledgements and retransmissions flow control: sender won t overwhelm receiver congestion control: senders slow down sending rate when network congested 1 28
Network edge: connectionless service Goal: data transfer between end systems same as before! UDP - User Datagram Protocol [RFC 768]: connectionless unreliable data transfer no flow control no congestion control App s using TCP: HTTP (Web), FTP (file transfer), Telnet (remote login), SMTP (email) App s using UDP: streaming media, teleconferencing, DNS, Internet telephony 1 29
The Network Core 1 30
The Network Core mesh of interconnected routers the fundamental question: how is data transferred through net? circuit switching: dedicated circuit per call: telephone net packet-switching: data sent thru net in discrete chunks The image cannot be displayed. Your computer may not have enough memory to open the image, or the image may have been corrupted. Restart your computer, and then open the file again. If the red x still appears, you may have to delete the image and then insert it again. 1 31
Network Core: Circuit Switching End-end resources reserved for call link bandwidth, switch capacity dedicated resources: no sharing circuit-like (guaranteed) performance call setup required 1 32
Network Core: Circuit network resources (e.g., bandwidth) divided into pieces pieces allocated to calls resource piece idle if not used by owning call (no sharing) Switching dividing link bandwidth into pieces frequency division time division 1 33
Circuit Switching: FDM and FDM TDM Example: 4 users frequency TDM time frequency time 1 34
Numerical example How long does it take to send a file of 640,000 bits from host A to host B over a circuit-switched network? All links are 1.536 Mbps Each link uses TDM with 24 slots/sec 500 msec to establish end-to-end circuit Let s work it out! 1 35
Another numerical example How long does it take to send a file of 640,000 bits from host A to host B over a circuit-switched network? All links are 1.536 Mbps Each link uses FDM with 24 channels/ frequencies 500 msec to establish end-to-end circuit Let s work it out! 1 36
Network Core: Packet Switching each end-end data stream divided into packets user A, B packets share network resources each packet uses full link bandwidth resources used as needed Bandwidth division into pieces Dedicated allocation Resource reservation resource contention: aggregate resource demand can exceed amount available congestion: packets queue, wait for link use store and forward: packets move one hop at a time Node receives complete packet before forwarding 1 37
A Packet Switching: Statistical 10 Mb/s Ethernet Multiplexing statistical multiplexing C B queue of packets waiting for output link 1.5 Mb/s D E Sequence of A & B packets does not have fixed pattern, shared on demand statistical multiplexing. TDM: each host gets same slot in revolving TDM frame. 1 38
Packet switching versus circuit switching Packet switching allows more users to use network! 1 Mb/s link each user: 100 kb/s when active active 10% of time circuit-switching: 10 users packet switching: with 35 users, probability > 10 active less than. 0004 N users 1 Mbps link Q: how did we get value 0.0004? 1 39
Packet switching versus circuit switching Is packet switching a slam dunk winner? Great for bursty data resource sharing simpler, no call setup Excessive congestion: packet delay and loss protocols needed for reliable data transfer, congestion control Q: How to provide circuit-like behavior? bandwidth guarantees needed for audio/video apps still an unsolved problem Q: human analogies of reserved resources (circuit switching) versus on-demand allocation (packet-switching)? 1 40
L Packet-switching: store-andforward R R R Takes L/R seconds to transmit (push out) packet of L bits on to link or R bps Entire packet must arrive at router before it can be transmitted on next link: store and forward delay = 3L/R (assuming zero propagation delay) Example: L = 7.5 Mbits R = 1.5 Mbps delay = 15 sec more on delay shortly 1 41
Packet-switched networks: forwarding Goal: move packets through routers from source to destination we ll study several path selection (i.e. routing) algorithms datagram network: destination address in packet determines next hop routes may change during session analogy: driving, asking directions virtual circuit network: each packet carries tag (virtual circuit ID), tag determines next hop fixed path determined at call setup time, remains fixed thru call routers maintain per-call state 1 42
Network Taxonomy Telecommunication networks Circuit-switched networks Packet-switched networks FDM TDM Networks with VCs Datagram Networks Datagram network is not either connection-oriented or connectionless. Internet provides both connection-oriented (TCP) and connectionless services (UDP) to apps. 1 43
! Internet 1 44
! 1 45
! 1 46
LAN Local Area Network IEEE 802.3CSMA/CD 10M IEEE 802.410M IEEE 802.5IBM4M 16M 1 47
MAN Metropolitan Area Network LAN 1 48
WAN Wide Area Network host end system communication subnet resource subnet 1 49
LAN! point-to-point - store-and-forward packet-switched 1 50
1! 1. 2. 3. 1 51
! ISO/OSI TCP/IP 1 52
! 1 53
7 6 5 4 3 2 1 A ISO/OSI! - - - Tnbm P39 Fig. 1-20 OSI B APDU PPDU SPDU TPDU 1 54
! 1 55
! 1 56
OSI/RM OSI OSI OSI OSI! OSI! OSI OSI! OSI 1 57
! OSI TCP/IP TCP/IP! 1 58
TCP/IP! TCP/IP OSI TCP/IP 1 59
! 5! 4! 3! 2! 1! (application layer) (transport layer) (network layer) (data link layer) (physical layer) 1 60
1 2! 1 AP 1 5 4 3 2 1! PDU 2 AP 2 5 4 3 2 1 1 61
1 2! 1 AP 1 5 4 3 2 1 PDU!! 2 AP 2 5 4 3 2 1 1 62
1 2! 1 AP 1 5 4 3 2 1! IP! 2 AP 2 5 4 3 2 1 1 63
1 2! 1 AP 1 5 4 3 2 1 IP!! 2 AP 2 5 4 3 2 1 1 64
1 2! 1 AP 1 5 4 3 2 1!! 2 AP 2 5 4 3 2 1 1 65
1 2! 1 AP 1 5 4 3 2 1!! 2 (application! layer) 5 4 3 2 1 AP 2 1 66
1 2! 1 AP 1 5 4 3 2 1! 2 AP 2 5 4 3 2 1 1 67
1 2! 1 AP 1 5 4 2 AP 2 5 4 3 2 1!! 3 2 1 1 68
1 2! 1 AP 1 5 4 3 2 1!! 2 AP 2 5 4 3 2 1 1 69
1 2! 1 AP 1 5 4 3 2 1!! 2 AP 2 5 4 3 2 1 1 70
1 2! 1 AP 1 5 4 3 2 1!! 2 AP 2 5 4 3 2 1 1 71
1 2! 1 AP 1 5 4 3 2 1 AP 1!! 2 AP 2 5 4 3 2 1 1 72
1 2! 1 AP 1 5 4 3!!!!!! H 3 H 4 H 5!! H 5! H 4 H 5!!! 2 AP 2 5 4 3 2 H 2 H 3 H 4 H 5! T 2 2 1 10100110100101 110101110101 1 1 73
1 2! 1 AP 1 5 4 3 2 1 2!! H 2 H 3 H 4 H 5! T 2 10100110100101 110101110101 2 AP 2 5 4 3 2 1 1 74
1 2! 1 AP 1 5 4 3 2 1!! H 3 H 4 H 5! H 2 H 3 H 4 H 5! T 2 2 AP 2 5 4 3 2 1 1 75
1 2! 1 AP 1 5 4 3 2 1!! H 4 H 5! H 3 H 4 H 5! 2 AP 2 5 4 3 2 1 1 76
1 2! 1 AP 1 5 4 3 2 1!! H 5! H 4 H 5! 2 AP 2 5 4 3 2 1 1 77
1 2! 1 AP 1 5 4 3 2 1! H 5! PDU!! 2 AP 2 5 4 3 2 1 1 78
1 2! 1 AP 1 5 4 3 2 1 AP 1!! 2 AP 2 5 4 3 2 1 1 79
! (entity) 1 80
! SAP (Service Access Point) 1 81
!!!! n + 1!!!! SAP SAP n!! 1 82
OSI TCP/IP! OSI! TCP/IP! TCP/IP! 7! 6! 5! 4!!!!!! (! TELNET, FTP, SMTP ) (TCP UDP)!!! () 3!! IP! 2!! 1!!! 1 83
Everything IP over Everything over IP TCP/IP! IP! IP!! HTTP SMTP DNS RTP! TCP UDP! IP! 1 2 3 1 84
!! 20 60 60 ARPA (Advanced Research Project Agency) (survivability) (circuit switching) 1 85
! 1 86
ARPANET! 1 87
!!!!!!! 1 88
! 1 89
! ARPANET ARPA 1983 TCP/IP ARPANET ARPANET! MILNET! 1983~1984 Internet 1990 ARPANET 1 90
! 1986 NSF NSFNET!!! 1991 1993 45 Mb/s T3 1 91
!!!!!!!!!!!! 1 92
!!!!!!!!!!! 1 93
! 1993 NSFNE T ISP 1994 4 NAP (Network Access Point) 4 NAP NAP NAP 1994 1 94
! ISP!! ISP! NAP! ISP!!! ISP! NAP! ISP ISP ISP! ISP!!!!! 1 95
! NAP ISP! ISP ISP PC! 1 96
1 97
1! 1. 2. 3. 1 98
! 1 99
! 20 1 = 80 1 2 3 4 5 6 713 3bit V = log 2 V 1 100
! 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 00 01 10 10 00 11 01 10 00 00 00 11 10 11 00 10 1 101
! 离 两 种 1 102
! 1 103
! 1 104
Nyquist! H Hz V! = 2Hlog 2 V b/s V01 2H 1 105
! (Baud)(bit)! 1 106
Shannon! H HzS/N!(b/s) = Hlog 2 (1+S/N) db db= 10log 10 S/N 30dBS/N=1000 1 107
! W S/N C 1 108
! 3500Hz 30dB (b/s) = Hlog 2 (1+S/N) = 3500log 2 (1+1000) 35000 (b/s) 35k bps 1 109
! 1 110
! 1 111
! 1) ASK(Amplitude Shift Keying) 2) FSK(Frequency Shift Keying) 3) PSK(Phase Shift Keying) QPSK(Quadrature Phase Shift Keying) 1 112
ASK (Amplitude Shift Keying) 0 1 0 1 ASK 1 113
FSK (Frequency Shift Keying) 1.5f f0 2f1 0 1 FSK 1 114
PSK (Phase Shift Keying) 00 π1 0 1 PSK 1 115
! 0 1 0 0 1 1 1 0 0 1 116
QPSK (Quadrature Phase Shift Keying) QPSK 2bit/ QAM-16 4bit/ QAM-64 6bit/ Tnbm P128 Fig. 2-25 (a) (b) (c) 1 117
! 1 118
! 01 4B/5B 1 119
NRZ (nonreturn-to zero) 10 bit 1 0 1 0 0 1 1 0 bit 1 120
Manchester encoding bit -0 bit -1 0 1 bit bit 1 121
differential Manchester encoding bit bitbit bit0 0 0 bit bitbit bit1 1 1 1 122
4B/5B! NRZ1nonreturn-to-zero change on one 4bit5 bit 5B1 1 123
164B/5B! 16 4bit 5bit 16 4bit 5bit 0 0000 11110 8 1000 10010 1 0001 01001 9 1001 10011 2 0010 10100 A 1010 10110 3 0011 10101 B 1011 10111 4 0100 01010 C 1100 11010 5 0101 01011 D 1101 11011 6 0110 01110 E 1110 11100 7 0111 01111 F 1111 11101 4bit5bit54 bit5b1 1 124
! bit bit bit 4B/5B 1.25 1 125
! 1 126
! PCM Pulse Code Modulation PCM f(t) 1 127
! 256 192 128 64 0 t A B C D E F G H A B C D E F G H 188 244 240 144 80 72 122 200 10111100 11110100 11110000 10010000 01010000 01001000 01111100 11001000 1 128
! 3500Hz 8000Hz 1 129
! 8 PCM 8 bit 8000 /64k b/s 1 130
! 01 50 Ω 185 M500 M 8100 M UTP cat 3/cat 5 1 131
! 750 MHz 100 km HFCHybrid Fiber Coax 54 ~ 550 MHz550-750 MHz! 1 132
! 1 133
! ASCII 1 1 1 1 134
! bit 1 135
! ASCII EBCDIC SYN BISYNC 1 136
bit! bit (01111110) bit HDLCSDLC CRC 1 137
bit! bit (01111110) 10 1 bitbit0bit 1 1 138
! 1 139
RS-232C RS-232-CModem DTEdata terminal equipment DCEdata circuit-terminating equipment 1 140
RS-232C! 25D 25 PIN 9 PIN DTEMale DCEFemale 0+12 V 1-12 V 15 m <20k b/s 1 141
RS-232-C! DTE 1 2 3 4 5 6 7 8 20 Frame Ground Transmit Data Receive Data Request To Send Clear To Send Data Set Ready Signal Ground Carrier Detect Data Terminal Ready 1 2 3 4 5 6 7 8 20 DCE 1 142
RS-232-C! DTE 1 2 3 4 5 6 7 8 20 Frame Ground Transmit Data Receive Data Request To Send Clear To Send Data Set Ready Signal Ground Carrier Detect Data Terminal Ready 1 2 3 4 5 6 7 8 20 DTE 1 143
! 25pin9pin 25pin 9pin 1 Frame Ground FG 2 3 Transmit Data TxD 3 2 Receive Data RxD 4 7 Request To Send RTS 5 8 Clear To Send CTS 6 6 Data Set Ready DSR 7 5 Signal Ground GND 8 1 Carrier Detect CD 20 4 Data Terminal Ready DTR 1 144
! Pin Pin 1 -STROBE 10 -ACK 2 DATA0 11 BUSY 3 DATA1 12 Paper Empty 4 DATA2 13 Select 5 DATA3 14 -Auto Feed 6 DATA4 15 -ERROR 7 DATA5 16 -INIT 8 DATA6 17 -SELECT IN 9 DATA7 18-25 GROUND 1 145
! Multiplexing FDM Frequency Division Multiplexing TDM Time division Multiplexing 1 146
FDM FDM 1 147
FDM! 1 148
FDM! 1 2 1 2 3 3 60 64 68 72 khz 300 3100Hz 60 64 68 72 khz Tnbm P138 Fig. 2-31 (a)(b)(c) 1 149
TDM 1 150
TDM! A A9 A8 A7 A6 A3 A2 A1 A0 B B9 B8 B7 B6 B3 B2 B1 B0 C C9 C8 C7 C6 D5 C5 B5 A5 D4 C4 B4 A4 t i+7 t i+6 t i+5 t i+4 t i+3 t i+2 t i+1 t i C3 C2 C1 C0 D D9 D8 D7 D6 D3 D2 D1 D0 1 151
TDM! TDM 1 152
TDM! A A4 A3 A2 A1 B C B2 B1 C3 C2 C1 A3 D2 C2 D1 A2 C1 B1 A1 A D C B A D C B A D C B A D D3 D2 D1 1 153
TDM! TDM TDMTDMSTDM 1 154
TDM! A A4 A3 A2 A1 B C D B2 B1 C3 C2 C1 D3 D2 D1 D3 A4 C3 B2 A3 D2 C2 D1 A2 C1 B1 A1 1 155
! 1 156
! 1 157
! 1 158
! 1 159
! -storeforward store-forward 1 160
! 1 161
! - store-forward 1 162
! t A B C D A B C D A B C D Tnbm P149 Fig. 2-39 1 163
! 适 1 164
! 适 1 165
! store-forward 1 166
! ATM 1 167
! 1 168
Thanks jdyu@cs.sjtu.edu.cn 1 169