Transcript CMPT 371: Chapter 1 - Simon Fraser University

School of Computing Science
Simon Fraser University
CMPT 371: Data Communications and
Networking
Review
1-1
Course Objectives
 Understand principles of designing and
operating computer networks,
 Understand the structure and protocols of
the largest network of networks (Internet),
 Know how to implement network protocols
and networked applications, and …
 Have fun!
1-2
A snapshot of the Internet in 1999 showing major ISPs
1-3
Internet structure: packet journey
 a packet passes through many networks!
local
ISP
Tier 3
ISP
Tier-2 ISP
local
ISP
local
ISP
local
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
Tier-2 ISP
local
ISP
1-4
Layering of airline functionality
ticket (purchase)
ticket (complain)
ticket
baggage (check)
baggage (claim
baggage
gates (load)
gates (unload)
gate
runway (takeoff)
runway (land)
takeoff/landing
airplane routing
airplane routing
airplane routing
departure
airport
airplane routing
airplane routing
intermediate air-traffic
control centers
arrival
airport
Layers: each layer implements a service
 via its own internal-layer actions
 relying on services provided by layer below
1-5
Internet protocol stack
 application: supporting network
applications

FTP, SMTP, HTTP
 transport: host-host data transfer
 TCP, UDP
 network: routing of datagrams from
source to destination

IP, routing protocols
 link: data transfer between
neighboring network elements

application
transport
network
link
physical
PPP, Ethernet
 physical: bits “on the wire”
1-6
Encapsulation
source
message
segment Ht
datagram Hn Ht
frame
Hl Hn Ht
M
M
M
M
application
transport
network
link
physical
Hl Hn Ht
M
link
physical
Hl Hn Ht
M
switch
destination
M
Ht
M
Hn Ht
Hl Hn Ht
M
M
application
transport
network
link
physical
Hn Ht
Hl Hn Ht
M
M
network
link
physical
Hn Ht
Hl Hn Ht
M
M
router
1-7
What is a network app?
 Programs that



run on different end systems
and
communicate over a network.
e.g., Web: Web server
software communicates with
browser software
application
transport
network
data link
physical
 little software written for
devices in network core


network core devices do not
run user application code
application on end systems
allows for rapid app
development, propagation
application
transport
network
data link
physical
application
transport
network
data link
physical
1-8
How to create a network app?
 Design application architecture
 how to organize the app over end systems
 Choose network transport service(s)
 which service to use (TCP, UDP)
 depends on app requirements (delay, loss, bw, …)
 Design app protocol
 message types, format, actions, …
 Write code

implement the protocol
1-9
Socket Programming
 process sends/receives
messages to/from its
socket
 socket analogous to door


sending process shoves
message out door
sending process relies on
transport infrastructure
on other side of door which
brings message to socket
at receiving process
host or
server
host or
server
process
controlled by
app developer
process
socket
socket
TCP with
buffers,
variables
Internet
TCP with
buffers,
variables
controlled
by OS
 socket is the interface (API) between application and
transport layer
1-10
Sample app-level protocols
 Web and HTTP
 web caching
 FTP
 Domain Name System (DNS)
1-11
Transport layer
 provide
logical communication
between app processes
 transport protocols run in
end systems
 send side: breaks app
messages into segments,
passes to network layer
 rcv side: reassembles
segments into messages,
passes to app layer
 more than one transport
protocol available to apps
 Internet: TCP and UDP
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
1-12
Reliable data transfer: principles
rdt_send(): called from above,
(e.g., by app.). Passed data to
deliver to receiver upper layer
send
side
udt_send(): called by rdt,
to transfer packet over
unreliable channel to receiver
deliver_data(): called by
rdt to deliver data to upper
receive
side
rdt_rcv(): called when packet
arrives on rcv-side of channel
1-13
Reliable data transfer: Go-Back-N
Sender:
 k-bit seq # in pkt header
 “window” of up to N, consecutive unack’ed pkts allowed
 ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”
may receive duplicate ACKs (see receiver)
 timer for each in-flight pkt
 timeout(n): retransmit pkt n and all higher seq # pkts in window
 i.e., go back to n

1-14
Reliable data transfer: Selective repeat
1-15
TCP: Overview
 point-to-point:
 one sender, one receiver
 reliable, in-order byte
steam:

no “message boundaries”
 congestion controlled:
 will not overwhelm
network
 send & receive buffers
socket
door
application
writes data
application
reads data
TCP
send buffer
TCP
receive buffer
RFCs: 793, 1122, 1323, 2018, 2581
 full duplex data:
 bi-directional data flow
in same connection
 MSS: maximum segment
size
 connection-oriented:
 handshaking (exchange
of control msgs) init’s
sender, receiver state
before data exchange
 flow controlled:
 sender will not
socket
door
overwhelm receiver
segment
1-16
TCP Congestion Control: Summary
 Initially

Threshold is set to large value (65 Kbytes), has not effect

CongWin = 1 MSS
 Slow Start (SS): CongWin grows exponentially

till a loss event occurs (timeout or 3 dup ack) or reaches Threshold
 Congestion Avoidance (CA): CongWin grows linearly
 3 duplicate ACK occurs:

Threshold = CongWin/2; CongWin = Threshold; CA
 Timeout occurs:

Threshold = CongWin/2; CongWin = 1 MSS; SS till Threshold
1-17
Network layer
 transport segment from




sending to receiving host
on sending side
encapsulates segments
into datagrams
on receiving side, delivers
segments to transport
layer
network layer protocols
in every host, router
Router examines header
fields in all IP datagrams
passing through it
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
1-18
Network Taxonomy
Telecommunication
networks
Circuit-switched
networks
FDM
TDM
Packet-switched
networks
Networks
with VCs
Datagram
Networks
• Datagram network is neither connection-oriented
nor connectionless.
• Internet provides both connection-oriented (TCP) and
connectionless services (UDP) to apps.
1-19
Interplay between routing and forwarding
routing algorithm
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
0111
1
3 2
1-20
Router Architecture Overview
Two key router functions:
 run routing algorithms/protocol (RIP, OSPF, BGP)

forward datagrams from incoming to outgoing link
1-21
Addressing, Subnets
223.1.1.0/24
223.1.2.0/24
 Subnet is:
 a group of devices that can
reach each other without
intervening router
 identified by high order bits
of IP addresses
11011111 00000001 00000001 00000001
223.1.3.0/24
Subnet ID
Host ID
223.1.1.0/24
/24: # bits in subnet portion of address, subnet mask
1-22
Hierarchical addressing: route aggregation
Hierarchical addressing allows efficient advertisement of routing
information:
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
“Send me anything
with addresses
beginning
199.31.0.0/16”
1-23
Routing algorithms: Graph abstraction
•
 cost of link (x1, x2):
2
 Metric value, e.g., c(w,z) = 5
u
 could be
1
 1, or
 inversely related to bandwidth, or
 inversely related to congestion
5
v
2
x
3
w
3
1
5
z
1
y
2
 Cost of path (x1, x2, x3,…, xp) =
c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Routing algorithm: algorithm that finds least-cost path
1-24
Classification of Routing Algorithms
Global or local information?
Global:
 all routers have complete topology, link cost info
 “link state” algorithms
local:
 router knows physically-connected neighbors, link
costs to neighbors
 iterative process of computation, exchange of info
with neighbors
 “distance vector” algorithms
1-25
Hierarchical Routing
 aggregate routers into regions, “autonomous systems”
(AS)
 routers in same AS run same routing protocol
 “intra-AS” routing protocol
 routers in different AS can run different intra-AS routing
protocol
Gateway router
 Direct link to router in another AS
1-26
Hierarchical Routing
3c
3a
3b
AS3
1a
2a
1c
1d
1b
Intra-AS
Routing
algorithm
2c
AS2
AS1
Inter-AS
Routing
algorithm
Forwarding
table
2b
 Forwarding table is
configured by both
intra- and inter-AS
routing algorithm


Intra-AS sets entries
for internal dests
Inter-AS & Intra-As
sets entries for
external dests
1-27
BGP: reachability and policy routing
legend:
B
W
provider
network
X
A
customer
network:
C
Y
Figure 4.5-BGPnew: a simple BGP scenario
 A,B,C are provider networks
 X,W,Y are customer (of provider networks)
 X is dual-homed: attached to two provider networks
X does not want to route traffic from B via X to C
 .. so X will not advertise to B a route to C

1-28
Unicast, multicast, broadcast
 Unicast: one source, one destination
 E.g., web session
 Multicast: one source, multiple destinations
 Subset of all possible destinations
 E.g., streaming a hockey game to interested fans
 Broadcast: one source, all destinations
 E.g., broadcasting link state info to ALL routers in a
domain in OSPF protocol
 Anycast: multiple possible sources, one destination
 Sources have same (anycast) address
 Request is forwarded to appropriate source
 (Still in research phases)
1-29
Link Layer
Some terminology:
“link”
 hosts and routers are nodes
 communication channels that
connect adjacent nodes along
communication path are links



wired links
wireless links
LANs
 layer-2 packet is a frame,
encapsulates datagram
data-link layer has responsibility of
transferring datagram from one node
to adjacent node over a link
1-30
Adaptors Communicating
datagram
sending
node
frame
adapter
rcving
node
link layer protocol
frame
adapter
 link layer implemented in  receiving side
“adaptor” (aka NIC)
 looks for errors, rdt, flow
control, etc
 Ethernet card, PCMCI
 extracts datagram, passes
card, 802.11 card
to rcving node
 sending side:
 adapter is semi encapsulates datagram in
autonomous
a frame
 adds error checking bits,
 link & physical layers
rdt, flow control, etc.
1-31
CRC: basic idea
 Sender and receiver agree on a divisor
polynomial G(x) of degree r
 Sender: transmits T(x), which consists of
d+1 data bits AND r redundant bits such
that G(x)|T(x),

i.e., the remainder of dividing T(x) by G(x) is 0
 Receiver: gets T’(x) which may have
corrupted bits
• If G(x) | T’(x) then no errors occurred
d+1 bits
r bits
1-32
MAC Protocols: a taxonomy
Three broad classes:
 Channel Partitioning


divide channel into smaller “pieces” (time slots,
frequency, code)
allocate piece to node for exclusive use
 Random Access
 channel not divided, allow collisions
 “recover” from collisions
 “Taking turns”
 Nodes take turns, but nodes with more to send can take
longer turns
1-33
MAC and IP addresses
 Why do we have TWO addresses (IP,MAC)?
Do we have to have MAC addresses?
 Yes, we must have both



To allow different network-layer protocols over
same card (e.g., IP, Novell IPX, DECnet)
Enable flexibility, mobility of cards
Efficiency: imagine that nodes have only IP
addresses  ALL packets sent over LAN will be
forwarded by NIC to the IP layer  too many
useless interrupts
1-34
Ethernet CSMA/CD algorithm
1. Adaptor receives
4. If adapter detects
datagram from net layer &
another transmission while
creates frame
transmitting, aborts and
sends jam signal
2. If adapter senses channel
idle, it starts to transmit 5. After aborting, adapter
frame. If it senses
enters exponential
channel busy, waits until
backoff: after the mth
channel idle and then
collision, adapter chooses
transmits
a K at random from
{0,1,2,…,2m-1}. Adapter
3. If adapter transmits
waits K·512 bit times and
entire frame without
returns to Step 2
detecting another
transmission, the adapter
is done with frame !
1-35
Institutional network
to external
network
mail server
web server
router
switch
IP subnet
hub
hub
hub
1-36
Point to Point Data Link Control
 one sender, one receiver, one link: easier than
broadcast link:
 no Media Access Control
 no need for explicit MAC addressing
 e.g., dialup link, ISDN line
 popular point-to-point DLC protocols:
 PPP (point-to-point protocol)
 HDLC: High level data link control
1-37
The Internet: virtualizing networks
Internetwork layer (IP):
 addressing: internetwork
appears as a single, uniform
entity, despite underlying local
network heterogeneity
 network of networks
Gateway:
 “embed internetwork packets in
local packet format or extract
them”
 route (at internetwork level) to
next gateway
gateway
ARPAnet
satellite net
1-38
What is next?
 If you have passion for networking
 More networking:
 CMPT 471 (Systems)
 CMPT 408 (Theory)
 Some theory:
 Computer Simulation and Modelling: CMPT 305
 Probability and Statistics
 Algorithms and graph theory
 Some systems
 C/C++ coding and Unix
 OS: CMPT 300, CMPT 401
1-39
That is all!
Good luck on your final
1-40