Transcript Introduction to Computer Networks

Prof. James Won-Ki Hong
Dept. of Computer Science and Engineering
POSTECH, Korea
[email protected]
2015. 3. 5
POSTECH
CSED702Y: Software Defined Networking
1/70
Outline
 Overview








What’s a Protocol
Network Edge
Network Core
Protocol Layers, Service Models
Data Link Layer
Network Layer
Transport Layer
Application Layer
POSTECH
CSED702Y: Software Defined Networking
2/70
POSTECH
CSED702Y: Software Defined Networking
3/70
What’s a Protocol?
 Human Protocols
 “hello” – “hello”
 “How are you?”
… specific msgs sent
… specific actions taken
when msgs received or
other events
 Network Protocols
 For network devices
rather than humans
 All communication
activities in Internet
governed by protocols
 Protocols define message format, the order of messages
sent and received among network entities, and actions
taken on message transmission & receipt
POSTECH
CSED702Y: Software Defined Networking
4/70
What’s a Protocol?
Hello!
TCP connection
req.
Hello!
TCP connection
reply.
How are you?
Get http://www.postech.ac.kr
Fine, thank you!
<file>
time
POSTECH
CSED702Y: Software Defined Networking
5/70
Network Structure
 Network Core
 Core Routers/switches
 Network of networks
 Network Edge
 Edge routers/switches/terminals
 Applications and hosts
 Physical Media
 Communication links (e.g., fiber
optics, twisted pairs, radios)
 Access Networks
 2G/3G/4G Base stations
 WiFi APs
POSTECH
CSED702Y: Software Defined Networking
6/70
Network Edge
 End Systems (hosts)
 Run application programs
 e.g., WWW, email, kakaotalk
 At “edge of network”
 Client/Server Model
 Client host requests, receives
service from server
 e.g., WWW client/server;
email client/server
 Peer-to-Peer Model
 Host interaction symmetric
 E.g., teleconferencing, P2P
apps
POSTECH
CSED702Y: Software Defined Networking
7/70
Network Edge: Connection-Oriented Service
 Data transfer between end systems
 Handshaking: setup (prepare for) data transfer
ahead of time
 Transmission Control Protocol (TCP)
• Reliable, in-order byte stream data transfer
• Loss: acknowledgements and retransmissions
• Flow control
• Sender should NOT overwhelm receiver
• Congestion control
• Senders “slow down sending rate” when network congested
POSTECH
CSED702Y: Software Defined Networking
8/70
Network Edge: Connectionless Service
 Data transfer between end systems
 No handshaking
 User Datagram Protocol (UDP)
 Unreliable data transfer
 No flow control
 No congestion control
 Apps using TCP
 HTTP(WWW), FTP (file transfer), Telnet (remote login), SMTP
(email transmission)
 Apps using UDP
 Streaming media, Teleconferencing, Internet telephony (VoIP)
POSTECH
CSED702Y: Software Defined Networking
9/70
Network Core
 Definition
 Mesh of interconnected
routers
 Two Ways of Data
Transmission
 Circuit switching
• Dedicated circuit per call:
telephone network
 Packet switching
• Data sent through network in
discrete “chunks”
POSTECH
CSED702Y: Software Defined Networking
10/70
Network Core: Circuit Switching
 End-to-end Resources
Reserved for “call”
 Link bandwidth, switch capacity
 Dedicated resource: no sharing
 Circuit-like (guaranteed)
performance
 Call setup required
 Network Resources
Divided into “Pieces”
 Pieces allocated to calls
 Dividing link bandwidth into
“pieces”
• Frequency division (FDMA)
• Time division (TDMA)
• Code division (CDMA)
POSTECH
CSED702Y: Software Defined Networking
11/70
Network Core: Packet Switching
 Each End-to-End Data Stream Divided into Packets
 User A, B packets share network resources
 Each packet uses full link bandwidth
 Resources used as needed
10 Mbps
Ethernet
A
B
C
statistical multiplexing
1.5 Mbps
queue of packets
waiting for output
link
45 Mbps
D
POSTECH
CSED702Y: Software Defined Networking
E
12/70
Network Core: Packet Switching
 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
• Transmit over link
• Wait turn at next link
POSTECH
CSED702Y: Software Defined Networking
13/70
Circuit Switching vs. Packet Switching
Item
Circuit
Switched
Packet
Switched
Call setup
Required
No need
Dedicated physical path
Yes
No
Each packet follows the same route
Yes
No
Packets arrive in order
Yes
No
Bandwidth available
Fixed
Dynamic
Time of possible congestion
At setup time
On every packet
Potentially wasted bandwidth
Yes
No
Store-and-Forward transmission
No
Yes
Fault tolerant
No
Yes
Has delay
No
Yes
POSTECH
CSED702Y: Software Defined Networking
14/70
Delay in Packet-Switched Networks
3. transmission
A
4. propagation
B
1. nodal
processing
2. queueing
 Packets Experience Delays on End-to-End Path (4
sources of delay at each hop)
1. Nodal processing delay
• Check bit errors, determine output link
2. Queueing delay
• Time waiting at output link for transmission, depends on congestion level of router
3. Transmission delay
• R = link bandwidth (bps), L = packet length (bits), time to send bits into link = L/R
4. Propagation delay
• D = length of physical link, s = propagation speed in medium (~2x108 m/sec)
• Propagation delay = d/s
POSTECH
CSED702Y: Software Defined Networking
15/70
Protocol Layers
 Organization of Air Travel
 Layers: each layer implements a service
ticket (purchase)
ticket (complain)
baggage (check)
baggage (claim)
gates (load)
gates (unload)
runway takeoff
runway landing
airplane routing
airplane routing
arriving airport
Departing airport
• Via its own internal-layer actions
• Relying on services provided by layer below
airplane routing
POSTECH
CSED702Y: Software Defined Networking
16/70
Network Protocols
 Network Protocols
 Organized into layers to reduce complexity
 Each protocol belongs to a layer “n”
 Layer n protocol is distributed among end systems and packet
switches communicating by exchanging messages “n-PDU”
 Put together, the protocols of various layers are called “protocol stack”
HOST A
Layer nn
Layer
n-PDU
Layern-1
n
Layer
HOST B
n-PDU
Layer nn
Layer
n-PDU
(n-1)-PDU
Layern-1
n
 Layer n is said to rely on layer n-1 to deliver Layer
its n-PDUs
 Layer n-1 is said to offer “services” to layer n, e.g., guaranteeing a
timely delivery without errors, or with no assurances.
POSTECH
CSED702Y: Software Defined Networking
17/70
Example of a 4-Layer Protocol Stack
Original
message
M
M
3-PDU
H 3 M1
H2 H3 M1
H1 H2 H3 M1
H3 M2
H2 H3 M2
H1 H2 H3 M2
2-PDU
1-PDU
H3 M1
H2 H3 M1
H1 H2 H3 M1
destination
source
POSTECH
H3 M2
H 2 H 3 M2
H 1 H 2 H 3 M2
CSED702Y: Software Defined Networking
18/70
Internet Protocol Stack
 Five Layered Protocol
 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
• PPP, Ethernet
 Physical: bits “on the wire”
physical
 OSI Seven Layered Protocol
 Open Systems Interconnection model (OSI)
 Defines seven layers
• Presentation layer and session layer between application
layer and transport layer added
POSTECH
CSED702Y: Software Defined Networking
19/70
Layering: Physical Communication
 Roles of Peers and Entities
 Peers are distributed
 “Entities” implement layer
functions at each node
 Entities perform actions,
exchange messages with peers
 Transport
 Take data from app. layer
 Add address, reliability check
info to form “datagram”
 Send datagram to peer
 Wait for peer to ack. Receipt
 Analogy: post office
POSTECH
data
application
transport
network
link
physical
application
transport
network
link
physical
CSED702Y: Software Defined Networking
network
link
physical
application
transport
network
link
physical
data
application
transport
network
link
physical
20/70
Protocol Layering and Data
 Each Layer Takes Data From Above
 Adds header information to create new data unit
 Passes new data unit to layer below
M
Ht
M
Hn Ht
Hl Hn Ht
M
M
POSTECH
source
destination
application
transport
network
link
physical
application
transport
network
link
physical
M
message
Ht
M
segment
Hn Ht
Hl Hn Ht
M
M
datagram
CSED702Y: Software Defined Networking
frame
21/70
POSTECH
CSED702Y: Software Defined Networking
22/70
Link Layer Protocols
 Data Link Layer
 Provides a reliable link between two directly connected nodes, by
detecting and correcting errors that may occur in the physical layer
 Divided into two sub layers
• Media Access Control (MAC) layer
• Logical Link Control (LLC) layer
POSTECH
CSED702Y: Software Defined Networking
23/70
Medium Access Links and Protocols
 Two Types of Links
 Point-to-point (single wire)
 Broadcast (shared wire or medium)
 MAC Protocol
 Coordinates transmissions from different stations in order to
minimize/avoid collisions
 Classifications
• Channel Partitioning (TDM, FDM)
• Random Access
• Taking Turns
 Goal: efficient, fair, simple, decentralized
POSTECH
CSED702Y: Software Defined Networking
24/70
Random Access Protocols (1/2)
 Random Access Protocols
 A node transmits at random at full channel data rate R
 If two or more nodes “collide”, they retransmit at random
times
 The random access MAC protocol specifies how to detect
collisions and how to recover from them (via delayed
retransmissions)
 Examples of random access MAC protocols
• ALOHA
• SLOTTED ALOHA
• Carrier Sense Multiple Access (CSMA) and CSMA/Collision Detection (CD)
POSTECH
CSED702Y: Software Defined Networking
25/70
Random Access Protocols (2/2)
 Random Access Protocols
 CSMA
• Listen before transmit, if channel is sensed busy, defer transmission
 CSMA/CD
• Carrier sensing and deferral like CSMA, but collisions are detected within a
few bit times
• Transmission is then aborted, reducing the channel wastage considerably
• In wired LAN: collision detection is easy, can measure signal strength
• In wireless LAN: very difficult, the receiver should shut off while transmitting
• The most popular LAN technology, Ethernet, uses this protocol
POSTECH
CSED702Y: Software Defined Networking
26/70
LAN Technologies
 Local Area Network (LAN) Technologies
 LAN uses MAC protocols to control the access to the channel
 Token ring: IEEE 802.5, for computer room
 Ethernet
• Employ the CSMA/CD protocol, 10Mbps (IEEE 802.3), Fast E-net (100Mbps), Giga
E-net (1,000 Mbps)
• By far the most popular LAN technology
• Encapsulate an IP datagram (or other packet) in Ethernet Frame
 Ethernet Frame
• Preamble: 7 bytes with the pattern 10101010 followed by one byte with the pattern
10101011 (SFD - start frame delimiter)
• Address: 6 bytes, received by all adapters, but dropped if address does not match
• Type: indicates the higher layer protocol, mostly IP
• CRC: checked at receiver, if error is detected, the frame is simply dropped
POSTECH
S
Preamble F
D
DST.
Address
SRC.
Address
8 bytes
6 bytes
6 bytes 2 bytes
Type
Payload
n bytes
CSED702Y: Software Defined Networking
Frame
Check (CRC)
4 bytes
27/70
LAN Addresses and ARP
 IP Address
 Drives the packet to the destination network
 LAN (or MAC) Address
 Drives the packet to the destination node’s LAN interface card
 48-bit MAC address: burned in the adapter ROM
 Analogy
 MAC address: like Social Security Number
 IP address: like postal address
 Packet Delivery
 Delivery of a packet to a host requires two levels of addressing
• Logical  IP addresses
• Physical  MAC addresses
 We need a mapping between logical to its corresponding physical
address and vice versa
POSTECH
CSED702Y: Software Defined Networking
28/70
IP to MAC Address Mapping
 Static Mapping
 A table stored in each machine on the network that associates a
logical address with a physical address
 Dynamic Mapping
 Know one of the two addresses, uses a protocol to find the other one
 Address Resolution Protocol (ARP)
 Reverse Address Resolution Protocol (RARP)
 ARP
 Each IP node on the LAN has ARP module and table
• Table: <IP Address, MAC Address, TTL>
 An ARP message is encapsulated directly into a data link frame
POSTECH
CSED702Y: Software Defined Networking
29/70
ARP Operation
 Obtaining the Physical Address
 When the physical address of another host is required, an ARP
query packet is sent which includes
• IP address of sender and the receiver
 The intended recipient recognizes its IP address and sends back an
ARP response which contains the physical address
POSTECH
CSED702Y: Software Defined Networking
30/70
POSTECH
CSED702Y: Software Defined Networking
31/70
Network Layer
 Network Layer
 Provides the functional and procedural means of transferring
variable length data sequences (called datagrams)
Transport layer: TCP, UDP
Network
layer
IP protocol
• addressing conventions
• datagram format
• packet handling conventions
Routing protocols
• path selection
• RIP, OSPF, BGP
routing
table
ICMP protocol
• error reporting
• router “signaling”
Link layer
Physical layer
POSTECH
CSED702Y: Software Defined Networking
32/70
IP Addresses
 IP Address
 Serves two principal functions
• Host or network interface
identification
• Location addressing
 Defined as a 32-bit number
consisting of 4 octets
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
 Interface
 Connection between
223.1.3.1
223.1.3.2
host/router and physical link
 Routers typically have multiple
interfaces
 Hosts may have more than
2.1.1.1 = 00000010 00000001 00000001 00000001
one interface
 IP addresses associated with
2
1
1
1
interface, not host or router
POSTECH
CSED702Y: Software Defined Networking
33/70
IP Addresses
 IP Address Types
 Public IPs
• All ranges except private IPs, divided as four classes
 Private IPs
• 10.0.0.0/8: 10.0.0.0 – 10.255.255.255
• 172.16.0.0/12: 172.16.0.0 – 172.31.255.255
• 192.168.0.0/16: 192.168.0.0 – 192.168.255.255
class
A
0 network
B
10
C
110
D
1110
1.0.0.0 to
127.255.255.255
host
network
128.0.0.0 to
191.255.255.255
host
network
multicast address
host
192.0.0.0 to
239.255.255.255
240.0.0.0 to
247.255.255.255
32 bits
POSTECH
CSED702Y: Software Defined Networking
34/70
Classless Inter-Domain Routing (CIDR)
 Motivation
 Slow the growth of routing tables on routers across the Internet
 Introduced by Internet Engineering Task Force (IETF)
 Notation
 A syntax of specifying IP addresses and their associated routing prefix
 Standards of IPv4 + slash character (‘/’) + prefix size expressed as
decimal number which always counts from the MSB of the address
 Examples
• 192.168.2.0/24 == 192.168.2.0 (255.255.255.0)
• 192.168.0.0/16 == 192.168.0.0 (255.255.0.0)
 Number of address of a subnet = 2address size – prefix size
 CIDR and Mask
 A subnet mask is a bitmask that encodes the prefix length in quaddotted notation (e.g., 255.255.255.0)
 CIDR adopts Variable Length Subnet Mask (VLSM)
 Prefix bits can only specify contiguous bits!
POSTECH
CSED702Y: Software Defined Networking
35/70
Getting a Packet from Source to Destination
 Routing Example
header
data
fields 223.1.1.1 223.1.2.2
 Starting at A, dest. E:
• Look up network address of E
• Routing table: next hop router to E
is 223.1.1.4
• Link layer sends packet to router
223.1.1.4 inside link-layer frame
• Packet arrives at 223.1.1.4
 Arriving at 223.1.1.4, destined
for 223.1.2.2
• Look up network address of E
• Link layer sends packet to
223.1.2.2 via interface 223.1.2.9
• Packet arrives at 223.1.2.2
Dest.
next
network router Nhops interface
223.1.1
223.1.2
223.1.3
POSTECH
-
1
1
1
223.1.1.4
223.1.2.9
routing table in A
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
A
223.1.1.4
223.1.1.4
1
2
2
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.2.9
B
223.1.1.3
223.1.3.1
223.1.3.27
223.1.2.2
E
223.1.3.2
223.1.3.27
CSED702Y: Software Defined Networking
36/70
IP Fragmentation and Reassembly
 IP Fragmentation
 Max. Transfer Unit (MTU)
- largest possible linklevel frame
 Large IP packet divided
(“fragmented”) within net
• One packet becomes several
packets
• “Reassembled” only at final
destination
• IP header bits used to
identify, order related
fragments
length ID fragflag
=1500 =x
=1
offset
=0
length ID fragflag
=1500 =x
=1
offset
=1500
length ID fragflag offset
=1000 =x
=0
=3000
POSTECH
fragmentation:
in: one large packet
out: 3 smaller packets
reassembly
length ID fragflag
=4000 =x
=0
offset
=0
One large packet becomes
several smaller packets
CSED702Y: Software Defined Networking
37/70
ICMP: Internet Control Message Protocol
 Internet Control Message Protocol (ICMP), RFC792
 The purpose of ICMP messages is to provide feedback about
problems in the IP network environment
 Delivered in IP packets
 ICMP message format
• 4 bytes of ICMP header and optional message
 Functions
•
•
•
•
POSTECH
To announce network errors
To announce network congestion
To assist troubleshooting
To announce timeouts
CSED702Y: Software Defined Networking
38/70
Routing in the Internet
 The Global Internet
 A hierarchy of Autonomous Systems (ASs) (enterprise ASs
interconnected through ISP’s ASs)
 What is POSTECH’s AS #?
 Two level routing
• Intra-AS routing: each enterprise is responsible for its Internet routing policy
• Routing Information Protocol (RIP), Open Shortest Path First (OSPF)
• Inter-AS routing: uses the standard routing protocol
• Border Gateway Protocol (BGP)  the de facto standard
POSTECH
CSED702Y: Software Defined Networking
39/70
Classification of Routing Methods
 Two Routing Methods
 Distance vector routing
• A router informs its neighbors of topology changes periodically (e.g., 30s)
• Routers do not need to have knowledge of the entire path to a dest.
• Direction in which route or exit interface a packet should be forwarded
• Distance from its destination (distance can be cost, or real geographical distance)
• RIP relies on distance vector routing
 Link state routing
• Every node constructs a map of the connectivity to the network - a graph
• Each node independently calculates the next best logical path from it to
every possible destination in the network
• The collection of best paths will then form the node’s routing table
• OSPF relies on link state routing
POSTECH
CSED702Y: Software Defined Networking
40/70
Routing Information Protocol (RIP)
 Routing Information Protocol (RIP)
 Uses Distance Vector (DV) routing
• Basically routing table consists of dest., cost and next hop fields
• min (distance to sender + hop cost of dest. in sender’s table, cost)
• Update next field with sender’s name
To
Cost
Next
R1
∞
-
R2
10
-
R3
20
-
R4
0
-
R5
∞
-
R2
R4
10.1.0.4/32
10.1.0.2/32
10
To
Cost
Next
R1
10
-
R2
0
-
R3
∞
-
R4
10
-
R5
10
-
10
10.1.0.1/32
10
To
Cost
R1
∞
R2
POSTECH
10
Next
-
R3
20
-
R4
∞
-
R5
0
-
10.1.0.5/32
10
20
R1
10.1.0.3/32
R5
20
R3
To
Cost
R1
10
R2
∞
R3
0
Autonomous SystemR4(AS)20
CSED702Y: Software Defined Networking
R5
20
Next
-
To
Cost
Next
R1
0
-
R2
10
-
R3
10
-
R4
R4
∞
20
R2
R5
∞
20
R2
-
-
41/70
Open Shortest Path First (OSPF)
 Open Shortest Path First (OSPF)
 “open”: publicly available protocol (IETF)
 Uses the Link State (LS) routing
• Link State Advertisement (LSA) through packet dissemination
• Distributed, replicated database model, identical topology map at each node (LSDB)
• Route computation using the Dijkstra’s algorithm
R4
10.1.0.4/32
Originator
Neighbor
Cost
R2
R1
R2
10
10.1.0.2/32
R1
R3
10
R2
R1
10
R2
R4
10
R2
R5
10
R3
R1
10
R3
R4
20
R3
R5
20
R4
R2
10
R4
R3
20
R5
R2
10
R5
R3
20
10
10
10.1.0.1/32
10
10.1.0.5/32
10
20
R1
10.1.0.3/32
R5
20
R3
Autonomous System (AS)
POSTECH
CSED702Y: Software Defined Networking
42/70
OSPF
 Shortest Path Calculation
 Calculate the shortest path using Dijkstra’s algorithm by referring to
LSDB what we have obtained from LSA flooding
 Finally, construct a Routing Information Base (RIB) and install in
each router
Originator
Neighbor
Cost
R1
R2
10
R1
R3
10
R2
R1
10
R2
R4
10
R2
R5
10
R3
R1
10
R3
R4
20
R3
R5
20
R4
R2
10
R4
R3
20
R5
R2
10
R5
POSTECH
R3
20
R1
R1
R1
10
R2
10
R3
20
R4
10
R1
R1
20
R2
10
R4
R5
R1
CSED702Y: Software Defined Networking
10
R2
10
R5
43/70
Border Gateway Protocol (BGP)
 Border Gateway Protocol (BGP)
 An exterior gateway protocol
 Widely used for Internet backbone
 Each border gateway broadcasts to neighbors’ the entire path to dest.
AS 200
AS 100
170.10.0.0/16
180.10.0.0/16
180.10.0.0/16 300 200 100
170.10.0.0/16 300 200
AS 300
AS 400
150.10.0.0/16
AS 500
POSTECH
180.10.0.0/16 300 200 100
170.10.0.0/16 300 200
150.10.0.0/16 300 400
CSED702Y: Software Defined Networking
44/70
Intra-AS vs. Inter-AS Routing
Intra-AS
Inter-AS
Policy
Under same
administrative control, so,
policy based routing is
less important
Concerned with policies (e.g.,
which provider to select/avoid)
Scalability
Scalability is less of a
concern within an AS. A
large AS can be divided
into two AS, (e.g., “areas”
in OSPF)
Ability of routing alg. And table
to scale for routing among
large number of networks
Performance Focused on performance
metrics, needs to keep
costs low
Routing is policy-oriented,
quality of routes is secondary.
Also, it is difficult to propagate
performance metrics efficiently
(latency, privacy, etc.)
POSTECH
CSED702Y: Software Defined Networking
45/70
Multicast Routing
 Multicast
 Delivery of a packet to a group of receivers
 Multicast is becoming increasingly popular in the Internet (e.g., VoD,
IPTV, multi-player online game)
 Multiple unicast vs. multicast
POSTECH
Multiple Unicast
Multicast
Multiple data stream
Single data stream
CSED702Y: Software Defined Networking
46/70
Multicast Group Address
 Multicast (M-cast) Group Address
 M-cast group address “delivered” to all receivers in the group
 Internet uses CLASS D (240.0.0.0 to 247.255.255.255) from m-cast
 M-cast address distribution and other metrics are managed Internet
Group Management Protocol (IGMP)
…
10.0.3.0/24
M-cast group #1
240.0.0.2
M-cast group #2
240.0.0.3
10.0.1.0/24
10.0.2.0/24
10.0.3.0/24
10.0.4.0/24
…
10.0.1.0/24
…
…
10.0.2.0/24
10.0.4.0/24
POSTECH
CSED702Y: Software Defined Networking
47/70
POSTECH
CSED702Y: Software Defined Networking
48/70
Transport Services and Protocols
 Internet Transport Protocols
 Provide logical communication
between app’s processes running
on different hosts
 Transport protocols run in end
system (except L4~L7 switch)
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
 Internet Transport Services
 Reliable, in-order unicast delivery
(TCP)
• Congestion control
• Flow control
• Connection setup
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
 Unreliable (“best-effort”),
unordered unicast or multicast
delivery: UDP
POSTECH
CSED702Y: Software Defined Networking
49/70
Multiplexing / demultiplexing
 Multiplexing
 Gather data from multiple app processes, envelop data with header
 Demultiplexing
 Deliver received segments to correct app layer processes
 Segment: unit of data exchanged between transport layer entities
receiver
application-layer
data
segment
header
segment
P3
M
application
transport
network
P1
M
Ht M
H n segment
M
application
transport
network
32 bits
P4
source port #
M
P2
application
transport
network
dest port #
other header fields
application
data
(message)
TCP/UDP segment format
POSTECH
CSED702Y: Software Defined Networking
50/70
Multiplexing / demultiplexing: examples
 Port based Multiplexing/demultiplexing
 Well known ports: 0 – 1023
• E.g., telnet  23, ssh  22, FTP  21, HTTP  80/443
 Registered ports: 1024 - 49151
 Dynamic and/or private ports: 49152 – 65535
host A
source port: x
dest. port: 23
WWW client
host C
server B
Source IP: C
Dest IP: B
source port: y
dest. port: 80
source port:23
dest. port: x
Source IP: C
Dest IP: B
source port: x
dest. port: 80
port use: simple telnet app
WWW client
host A
Source IP: A
Dest IP: B
source port: x
dest. port: 80
WWW
server B
port use: WWW server
POSTECH
CSED702Y: Software Defined Networking
51/70
User Datagram Protocol (UDP) [RFC 768]
 UDP
 “No frills”, “bare bones” Internet transport protocol
 “Best effort” service, UDP segments may be:
• Lost, delivered out of order to app
 Connectionless
• No handshaking between UDP sender & receiver
• Each UDP segment handled independently of others
 Why we need a UDP?
•
•
•
•
No connection establishment which can add delay, require more resources
Simple: no connection state at sender & receiver
Small segment header
No congestion control: UDP can blast away as fast as desired
 Applications
• Often used for multimedia streaming apps
• Loss tolerant, rate sensitive
• Other UDP applications: DNS, SNMP
• Reliable transfer over UDP: add reliability at application layer
POSTECH
CSED702Y: Software Defined Networking
52/70
User Datagram Protocol (UDP) [RFC 768]
 UDP Checksum
 Goal: Detect “errors” (e.g., flipped bits) in transmitted segment
 Sender
• Treat segment contents as sequence of 16-bits integers
• Checksum: addition (1’s complement sum) of segment contents
• Sender puts checksum value into UDP checksum field
 Receiver
• Compute checksum of received segment
• Check if computed checksum equals checksum field value
• NO  error detected, YES  no error detected
32 bits
Length in
bytes of UDP
segment,
including
header
source port #
dest port #
length
checksum
Application
data
(message)
POSTECH
CSED702Y: Software Defined Networking
UDP segment format
53/70
TCP: Overview
ACK: ACK #
valid
 TCP Features
URG: urgent data
(generally not used)
 Point-to-point
PSH: push data now
(generally not used)
• One sender, one receiver
32 bits
 Reliable, in-order byte stream
source port #
• No “message boundaries”
dest port #
sequence number
 Pipelined
acknowledgement number
head not
U A P R S F rcvr window size
len used
• TCP congestion and flow control set
window size
 Full duplex data
• Bi-directional data flow in same
connection
 Connection-oriented
• Handshaking (exchange of control
messages) initializes sender,
receiver stat before data exchange
checksum
RST, SYN, FIN:
connection estab
(setup, teardown
commands)
ptr urgent data
Options (variable length)
application
data
(variable length)
Internet
checksum
(as in UDP)
 Flow controlled
• Sender will not overwhelm receiver
POSTECH
# bytes
rcvr willing
to accept
CSED702Y: Software Defined Networking
counting
by bytes
of data
(not segments!)
54/70
TCP Sequence #’s and ACKs
 Sequence Number
 Byte stream “number” of
first byte in segment’s data
 Acknowledgements
 Sequence # of next byte
expected from other side
 Cumulative ACK
 Out-out-order
Segments
 A: TCP spec doesn’t say,
up to the implementor
Host A
User
types
‘C’
Host B
host ACKs
receipt of
‘C’, echoes
back ‘C’
host ACKs
receipt
of echoed
‘C’
time
simple telnet scenario
POSTECH
CSED702Y: Software Defined Networking
55/70
TCP: Retransmission Scenarios
X
loss
time
POSTECH
Host A
Host B
Host B
Seq=100 timeout
Seq=92 timeout
timeout
Host A
lost ACK scenario
time
premature timeout,
cumulative ACKs
CSED702Y: Software Defined Networking
56/70
TCP Flow Control
 TCP Flow Control
 Sender will not overrun receiver’s buffers by transmitting too much, too
fast
 Receiver
• Explicitly informs sender of (dynamically changing) amount of free buffer space
 Sender
• Amount of transmitted, unACKed data less than most recently-receiver RcvWindow
size
receiver buffering
POSTECH
CSED702Y: Software Defined Networking
57/70
TCP Flow Control
 Window Management in TCP
 The receiver is returning two parameters to the sender
• AckNo (32 bits), Window Size (Win) (16 bits)
 Receiver can acknowledge data without opening the window
 Receiver can change the window size without acknowledging data
Receiver
Buffer
Sender
sends 2K
of data
0
4K
2K SeqNo=0
2K
Sender blocked
Sender
sends 2K
of data
Win=2048
AckNo=2048
2K SeqNo=2
048
4K
Win=0
AckNo=4096
3K
Win=1024
AckNo=4096
POSTECH
CSED702Y: Software Defined Networking
58/70
TCP Congestion Control
 TCP Congestion Control
 The sender has two additional parameters
• Congestion Window (cwnd)
• Slow-start threshold value (ssthresh)
 Many versions: TCP/Tahoe, TCP/Reno…
 Congestion control works in two modes
• Slow start (cwnd < ssthresh)  grows rapidly
cwnd = 1
cwnd = 2
cwnd = 4
cwnd = 8
• Based on Multiplicative Increase (MI)
• cwnd = cwnd + 1
• Congestion avoidance (cwnd >= ssthresh)
• Based on Additive Increase Multiplicative
Decrease (AIMD)
cwnd = 9
• No congestion: cwnd = cwnd + 1/cwnd
• Congestion: cwnd = cwnd / 2
 Timeout
• ssthresh = cwnd / 2
POSTECH
cwnd = 10
CSED702Y: Software Defined Networking
59/70
TCP Congestion Control
70
threshold
Congestion Window
60
congestion
window
timeouts
50
fast retransmission
40
30
20
additive increase
10
slow start period
0
0
10
20
30
40
50
60
Time
POSTECH
CSED702Y: Software Defined Networking
60/70
TCP Connection Management
 TCP Connection Management
 Initialize TCP variables
• Sequence number
• Buffer, flow control info (e.g., RcvWindow)
client
server
open
 Client: connection initiator
 Server: contacted by client
listen
 Open a Connection (3-way)
 Step1
• Client end system sends TCP SYN
control segment to server
 Step2
established
• Server end system receives SYN, relies
with SYN-ACK
established
 Step3
• Client rcvs SYN-ACK
• Connection is now set up
• Client starts the “real work”
POSTECH
CSED702Y: Software Defined Networking
61/70
TCP Connection Management
 Close a Connection
 Step 1
client
• Client end system sends TCP FIN
control segment to server
server
close
 Step 2
• Server receives FIN, replies with
ACK
• Closes connection, sends FIN
close
• Client receives FIN, replies with
ACK
• Enters “timed wait” – will respond
with ACK to received FINs
 Step 4
• Receives ACK
• Connection closed
POSTECH
timed wait
 Step 3
closed
closed
CSED702Y: Software Defined Networking
62/70
POSTECH
CSED702Y: Software Defined Networking
63/70
Application Layer Protocols
 Application-layer Protocols
 Define messages exchanged by
apps and actions taken
 Uses services provided by lower
layer protocols
application
transport
network
data link
physical
request
 Client-Server Model
 Client
• Initiates contact with server
• Typically requests service from server
 Server
• Provides requested service to client
• E.g., sends requested WWW page,
receives/stores received email
POSTECH
reply
application
transport
network
data link
physical
CSED702Y: Software Defined Networking
application
transport
network
data link
physical
64/70
Hyper Text Transfer Protocol (HTTP)
 TCP Transport Service
 Client initiates a TCP connection to server, port 80
 Server accepts TCP connection from client
 http messages (application-layer protocol messages) exchanged
between browser and WWW server
 TCP connection closed
 Stateless
 Server maintains no information about past client requests
 Stateful
 Post history (state) must be maintained
 If server/client crashes, their views of “state” may be inconsistent, must
be recovered
POSTECH
CSED702Y: Software Defined Networking
65/70
HTTP Message Format
 HTTP Message Types
 Request, response
 Request Format
request line
(GET, POST,
HEAD commands)
header
lines
Carriage return,
line feed
indicates end
of message
GET /somedir/page.html HTTP/1.1
Connection: close
User-agent: Mozilla/4.0
Accept: text/html, image/gif,image/jpeg
Accept-language:fr
(extra carriage return, line feed)
 Response
Format
status line
(protocol
status code
status phrase)
header
lines
data, e.g.,
requested
html file
POSTECH
HTTP/1.1 200 OK
Connection: close
Date: Fri, 12 May 2000 12:30:00 GMT
Server: Apache/1.3.0 (Unix)
Last-Modified: Mon, 22 Jun 1998 …...
Content-Length: 6821
Content-Type: text/html
data goes here ...
CSED702Y: Software Defined Networking
66/70
Domain Name System (DNS)
 Domain Name System
 Map between IP addresses and name
 Distributed database
• Implemented in hierarchy of many name servers
 Application-layer protocol
• Host, routers, name servers to communicate to resolve names
(address/name translation)
• Note: core Internet function implemented as application layer protocol
 Name servers
• Local name servers
• Each ISP, company has local (default) name server
• Host DNS query first goes to local name server
• Authoritative name server
• For a host: stores that host’s IP address, name
• Can perform name/address translation for that host’s name
POSTECH
CSED702Y: Software Defined Networking
67/70
DNS: Root Name Servers
 Root Name Servers
 Contacted by local name server that cannot resolve name
 Root name server
•
•
•
•
POSTECH
Contacts authoritative name server if name mapping not known
Get mapping
Returns mapping to local name server
13 root name servers worldwide
CSED702Y: Software Defined Networking
68/70
DNS Example: Recursive Query
root name server
 DNS Query Example
 Host cecom.yust.edu wants
IP address of
gunine.itce.postech.ac.kr
• Contacts its local DNS
server, dns.yust.edu
• dns.yust.edu contacts root
name server, if necessary
• Root name server may not
know authoritative name
server
• Root name server may now
intermediate name server
• Contact authoritative name
server through intermediate
server
• Authoritative name server
returns the IP address with
reply message
POSTECH
6
2
7
local name server
dns.yust.edu
1
8
3
intermediate name server
dns.postech.ac.kr
4
5
authoritative name server
dns.itce.postech.ac.kr
requesting host
cecom.yust.edu
CSED702Y: Software Defined Networking
gunine.itce.postech.ac.kr
69/70
DNS: Iterated Queries
 Recursive Query
 Puts burden of name
resolution on contacted
name server
 May induce heavy load
root name server
iterated query
2
3
4
 Iterated Query
7
 Contacted server relies with local name server
name of server to contact
dns.yust.edu
 Do not overwhelm the
1
8
contacted server
 More efficient than recursive
query
intermediate name server
dns.postech.ac.kr
5
6
authoritative name server
dns.itce.postech.ac.kr
requesting host
cecom.yust.edu
gunine.itce.postech.ac.kr
POSTECH
CSED702Y: Software Defined Networking
70/70
Q&A
POSTECH
CSED702Y: Software Defined Networking
71/70