Transcript csci4211-what-we-learned-last-time

What We Learned Last Time (Sept 9)
• What is a Computer Network/Internet?
• services
• components and their functions
Compare & Contrast:
Telephone Networks & Postal Service
• Packet Switching vs. Circuit Switching
• statistical multiplexing
• compare and contrast: TDM, FDM
• Fundamental Issues and Problems in Networking
• Layered Architecture and Protocol
CSci4211:
Weekly Summary
1
Summary of Introduction

What is a network? What is a computer/data network?
Compare w/ diff. networks (telephone, postal office,
transportation networks, …)


“bolts-&-nuts” view vs. service perspective
Packet switching vs. circuit switching:
packets, packet switching & statistical multiplexing

delay, losses and congestion vs. call blocking
Key functions: naming, addressing, routing & forwarding

Networks are distributed & complex systems!



Architecture: layering & hourglass



What may go wrong?


different technologies, “boxes” (routers, switches), & apps
Protocols and Interfaces (API)
bit errors, packet losses,, node failures, software bugs, app
crashes. ….. and Attacks !!!
What today’s Internet looks like? economics & policies
CSci4211:
Key Notes
2
Stuff We Didn’t Talk About or
Elaborated on

Various Physical Media


Access Networks



twisted pairs, co-axial cables, fiber optics, radio, satellite,
etc.
DSL, Cable Modem, Fiber to the Curb/Home, …
ISPs and Internet Backbones
Delay, Loss, and Throughput

various delays: transmission delay, propagation delay,
processing delay, queuing delay, ..
CSci4211:
Key Notes
3
A Simplified Illustration of Internet
CSci4211:
Key Notes
4
Announcements (Sep 23)
• Project #1: out today, and
Due Friday Oct 8 (11:59 pm).
Please start working on it as soon as possible!
• Written Homework Assignment #1 will be posted
by Sep 30, due Thu Oct 14 (6:30pm)
• P.S.:
Prof. Zhang will be on a oversea trip from Sep 25-Oct 12. No
office hours during this period (may still have intermittent
Internet access).
CSci4211:
Weekly Summary
5
What We Learned Last Time (Sept 16)
Applications and Application Layer Protocols
Basics of Building Applications: a networking perspective



application processes and inter-process communications
API: socket overview
“Addressing” processes (“whom is the other party is”)


What transport services to use?



client-server
peer-to-peer
- data centers, cloud services
download
“wireshark
”
software!
Examples of applications/application protocols



TCP and UDP
Application Structures


IP addresses and port numbers
world wide web and HTTP: transaction-oriented app protocol
email and SMTP (& POP, IMAP): session-based app protocol
Domain Name System (DNS)
CSci4211:
Key Notes
6
Highlight of Today’s Lecture (Sept 23)

Peer-to-Peer programming paradigm

•
•

Unstructured P2P Application Examples:





key problem in p2p programming paradigm?
how to find the other party? What’re the IP of and port #
used by the other party?
especially, if the other party is behind NAT
BitTorrent
Gaaza, Skype, …
Distributed Hashing Tables (DHT)
Java Socket Programming
Project #1 Overview
CSci4211:
Key Notes
7
Announcement (Sep 16)
• Please sign up to the class google group!
• Advanced Notice: Programming Project # 1 will be
posted next week!
• Please start reading about (Java) socket
programming in the textbook, and try the
examples!
CSci4211:
Weekly Summary
8
What We Learned Last Time (Sept 12)
• Application Layer
• application requirements & transport services
• application programming paradigms
• client-server vs. peer to peer
• Case Study 1: Web & HTTP
• web client vs. web server (TCP, port 80)
• HTTP: request & reply
• Case Study 2: Email
• SMTP: “interactive”
• Mail Access Protocols: POP, IMAP
• DNS: why do we need DNS?
• DNS server architecture & query process
CSci4211:
Weekly Summary
9
Web and HTTP Summary
Transaction-oriented (request/reply), use TCP, port 80
Client
Server
GET /index.html HTTP/1.0
CSci4211:
HTTP/1.0
200 Document follows
Content-type: text/html
Content-length: 2090
-- blank line -HTML text of the Web page
Weekly Summary
10
Email Summary
Alice
Message
user agent
(MUA)
client
Message
transfer
agent
(MTA)
SMTP
outgoing mail queue
SMTP
over TCP
(RFC 821)
Bob
POP3 (RFC 1225)/ IMAP (RFC 1064)
for accessing mail
Message
user agent
(MUA)
user mailbox
CSci4211:
Weekly Summary
port 25
server
Message
transfer
agent
(MTA)
11
root name server
DNS example
Root name server:
• may not know
authoritative name
server
• may know
intermediate name
server: who to
contact to find
authoritative name
server
6
2
7
3
local name server intermediate name server
dns.aol.com
1
8
dns.umn.edu.
4
5
authoritative name server
requesting host
dns.cs.umn.edu
homeboy.aol.com
afer.cs.umn.edu
CSci4211:
Weekly Summary
12
Announcement & Reminder (Oct 3)
• Homework Assignment #2: Due Oct 17
• check the class website
Reminder:
• Start working on your project #1, if you haven’t
yet!
CSci4211:
Weekly Summary
13
What We Learned Last Time
(Sept 19 & Sept 26)
• Transport Layer
• multiplexing and de-multiplexing
• UDP: connectionless transport service
• src/dst port no.’s, checksum
• TCP: connection-oriented, reliable service
• seq #, ack #, special “flags” (SYN, ACK, FIN, RST)
• simply reliable data transfer protocol
• connection set-up: 3-way handshake
• BSD Socket Programming
• create socket, bind socket, close socket
• connect, listen accept
• read/write, sendto/recvfrom, …
CSci4211:
Weekly Summary
14
Reminders (Oct 10)
• Homework Assignment #2: Due Oct 17
• Project #1: Due Oct 17
• Mid-Term: Oct 24 (in two weeks !!!)
• Start reviewing the material you have learned
so far:
•basic network concepts
•application layer
•transport layer
CSci4211:
Weekly Summary
15
What We Learned Last Time (Oct 3)
• TCP Connection Management
•Review TCP 3-way handshake connection setup
• Closing a connection: key issues and how TCP does it
• More efficient reliable data transfer protocols
• What’s the problem with Stop&Wait protocol?
• Go-Back-N and Selective Repeat
• concept of ”sliding window”
• sender algorithm:
•when to retransmit, when to send new packets? when to
move window forward?
• receiver algorithm:
•when/what to acknowledge? when to move window
forward? when to buffer packets, and when to pass to
upper layer?
•relationship between window size & seq. no. space
• round trip time estimation and TCP timeoutInterval
CSci4211:
Weekly Summary
16
TCP: Closing Connection
Remember TCP duplex connection!
Client wants to close connection:
Step 1: client end system sends
TCP FIN control segment to
server
client
client
closing
Step 2: server receives FIN,
replies with ACK. half closed
Step 3: client receives FIN.
half
closed
half closed, wait for server to close
server
half
closed
server
closing
Server finishes sending data,
also ready to close:
Step 4: server sends FIN.
CSci4211:
Weekly Summary
17
TCP: Closing Connection (revised)
client
Two Army Problem!
Step 5: client receives FIN,
replies with ACK.
– Enters “timed wait” - will
respond with ACK to received
FINs
server
client
closing
half
closed
half
closed
server
closing
ACK. connection fully
closed
Step 7: client, timer expires,
connection fully closed
timed wait
Step 6: server, receives
X
timeout
full
closed
full closed
CSci4211:
Weekly Summary
18
Go-Back-N: Basic Ideas
Sender:
• Packets transmitted continually (when available) without
waiting for ACK, up to N outstanding, unACK’ed packets
• A logically different timer associated with each “inflight” (i.e., unACK’ed) packet
• timeout(n): retransmit pkt n and all higher seq # pkts in window
Receiver:
• ACK packet if corrected received and in-order, pass to higher
layer, NACK or ignore corrupted or out-of-order packets
• “cumulative” ACK: if multiple packets received corrected and
in-order, send only one ACK with ack= next expected seq no.
CSci4211:
Weekly Summary
19
Selective Repeat
• As in Go-Back-N
– Packet sent when available up to window limit
• Unlike Go-Back-N
– Out-of-order (but otherwise correct) is ACKed
– Receiver: buffer out-of-order pkts, no “cumulative” ACKs
– Sender: on timeout of packet k, retransmit just pkt k
• Comments
– Can require more receiver buffering than Go-Back-N
– More complicated buffer management by both sides
– Save bandwidth
• no need to retransmit correctly received packets
CSci4211:
Weekly Summary
20
Go-Back-N: Sliding Windows
Sender:
•
•
“window” of up to N, consecutive unack’ed pkts allowed
send_base: first sent but unACKed pkt, move forward when ACK’ed
expected, not received yet
may be received
(and can be buffered,
but not ACK’ed)
rcv_base
Receiver:
• rcv_base: keep track of next expected seq no, move forward
when next in-order (i.e., w/ expected seq no) pkt received
CSci4211:
Weekly Summary
21
GBN in Action
CSci4211:
Weekly Summary
22
Selective Repeat: Sliding Windows
CSci4211:
Weekly Summary
23
Selective Repeat in Action
CSci4211:
Weekly Summary
24
Seqno Space and Window Size
• How big the sliding window can be?
– MAXSEQNO: number of available sequence
numbers
– Under Go-Back-N?
• MAXSEQNO will not work, why?
– What about Selective-Repeat?
CSci4211:
Weekly Summary
25
Selective Repeat:
Dilemma
Example:
• seq #’s: 0, 1, 2, 3
• window size=3
• receiver sees no
difference in two
scenarios!
• incorrectly passes
duplicate data as new
in (a)
Q: what relationship
between seq # size
and window size?
CSci4211:
Weekly Summary
26
Reminders (Oct 17)
• Homework Assignment #2: Due today midnight
• Project #1: Due today midnight
• Mid-Term: Oct 24 (7:30 – 9pm next Thursday !!!)
• 5 “big questions”
• cover the material up to Oct 10 (inclusive)
•basic network concepts
•application layer (exclude BSD/Java socket APL)
•transport layer
•network layer (IP addressing, VC vs. Datagram)
CSci4211:
Weekly Summary
27
What We Learned Last Time (Oct 10)
• Finishing up TCP and Transport Layer
• TCP Flow Control: avoid overwhelm receiver
•RecvWin: receiver advertises available buffer space
• Congestion Control: avoid overwhelm network routers
• two approaches:
• end-to-end implicit vs. router-assisted
• TCP congestion control: end-to-end implicit
• issue 1: how to determine network is congested
• issue 2: how to adjust sending rate to avoid congestion
• TCP congestion control mechanisms
• two parameters: ConWin, threshold
• slow start
• congestion avoidance: AIMD, duplicate ACKs, timeout
• fast retransmit/fast recovery
CSci4211:
Weekly Summary
28
TCP Flow Control: How It Works
• Rcvr advertises spare
room by including value
of RcvWindow in
segments
• Sender limits unACKed
data to RcvWindow
(Suppose TCP receiver
discards out-of-order
segments)
• spare room in buffer
– guarantees receive buffer
doesn’t overflow
= RcvWindow
= RcvBuffer-[LastByteRcvd LastByteRead]
CSci4211:
Weekly Summary
29
TCP Slowstart
Slowstart algorithm
Host A
RTT
initialize: Congwin = 1
for (each segment ACKed)
Congwin++
until (loss event OR
CongWin > threshold)
• exponential increase (per RTT) in
window size (not so slow!)
• loss event: timeout (Tahoe TCP)
and/or or three duplicate ACKs
(Reno TCP)
CSci4211:
Host B
Weekly Summary
time
30
TCP Congestion Avoidance
Congestion Avoidance
/* slowstart is over
*/
/* Congwin > threshold */
Until (loss event) {
every W segments ACKed:
Congwin++
}
Threshold: = Congwin/2
Congwin = 1
perform slowstart
CSci4211:
Weekly Summary
31
TCP Congestion Control: Recap
• end-end control (no network
assistance)
• sender limits transmission:
LastByteSent-LastByteAcked
 CongWin
• Roughly,
rate =
CongWin
Bytes/sec
RTT
• CongWin is dynamic, function of
perceived network congestion
CSci4211:
How does sender
perceive congestion?
• loss event = timeout or
3 duplicate ACKs
• TCP sender reduces
rate (CongWin) after
loss event
three mechanisms:
– AIMD
– slow start
– conservative after timeout
events
Weekly Summary
32
TCP Congestion Control: Recap (cont’d)
• When CongWin is below threshold, sender in
slow-start phase, window grows exponentially.
• When CongWin is above Threshold, sender is in
congestion-avoidance phase, window grows linearly.
• When a triple duplicate ACKs occurs, threshold
set to CongWin/2, and CongWin set to
threshold.
• When timeout occurs, threshold set to
CongWin/2, and CongWin is set to 1 MSS.
CSci4211:
Weekly Summary
33
What We Learned Last Time (Oct 10) …
•Network Layer
• basic functions: addressing, routing & forwarding
• IP addressing:
• 32 bits, dot notation
• two-level hierarchy: network part & host part
• how to determine network part?
• “classful” addressing scheme
• “classless” addressing scheme: CIDR
• Network Service Models
• Virtual Circuits: how it works?
• VC set-up & VCI translation table
• data forwarding
• Datagram: how it works?
CSci4211:
Weekly Summary
34
Routing & Forwarding:
Logical View of a Router
5
A
2
1
B
2
D
3
3
1
C
5
1
E
F
2
CSci4211:
Weekly Summary
35
IP Addressing: Network vs. Host
multi-access
LAN
223.1.1.2
• Two-level hierarchy
– network part (high order
bits)
– host part (low order bits)
• What’s a network ?
(from IP address perspective)
223.1.1.1
223.1.1.4
223.1.1.3
223.1.9.2
– device interfaces with
same network part of IP 223.1.9.1
address
223.1.8.1
– can physically reach each 223.1.2.6
other without intervening
router
223.1.2.1
223.1.2.2
CSci4211:
Weekly Summary
223.1.7.0
point-to-point
link
223.1.7.1
223.1.8.0
223.1.3.27
223.1.3.1
223.1.3.2
36
“Classful” IP Addressing
class
77
A
0 network
B
10
C
110
D
1110
15
23
31
host
network
128.0.0.0 to
191.255.255.255
host
network
1.0.0.0 to
127.255.255.255
host
multicast address
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
32 bits
• Disadvantage: inefficient use of address space, address
space exhaustion
• e.g., class B net allocated enough addresses for 65K
hosts, even if only 2K hosts in that network
CSci4211:
Weekly Summary
37
Classless Addressing: CIDR
CIDR: Classless InterDomain Routing
• Network portion of address is of arbitrary length
• Addresses allocated in contiguous blocks
– Number of addresses assigned always power of 2
• Address format: a.b.c.d/x
– x is number of bits in network portion of address
host
part
network
part
11001000 00010111 00010000 00000000
200.23.16.0/23
CSci4211:
Weekly Summary
38
Virtual Circuit vs. Datagram
• Objective of both: move packets through routers from source
to destination
• Datagram Model:
– Routing: determine next hop to each destination a priori
– Forwarding: destination address in packet header, used at
each hop to look up for next hop
• routes may change during “session”
– analogy: driving, asking directions at every gas station, or
based on the road signs at every turn
• Virtual Circuit Model:
– Routing: determine a path from source to each destination
– “Call” Set-up: fixed path (“virtual circuit”) set up at “call”
setup time, remains fixed thru “call”
– Data Forwarding: each packet carries “tag” or “label”
(virtual circuit id, VCI), which determines next hop
– routers maintain ”per-call” state
CSci4211:
Weekly Summary
39
Datagram Networks:
the Internet model
• no call setup at network layer
• routers: no state about end-to-end connections
– no network-level concept of “connection”
• packets forwarded using destination host address
– packets between same source-dest pair may take
different paths, when intermediate routes change!
application
transport
network
data link 1. Send data
physical
application
transport
2. Receive data network
data link
physical
CSci4211:
Weekly Summary
40
Virtual Circuit: Signaling Protocols
• used to setup, maintain teardown VC
• used in ATM, frame-relay, X.25
• used in part of today’s Internet: Multi-Protocol Label
Switching (MPLS) operated at “layer 2+1/2” (between data
link layer and network layer) for “traffic engineering” purpose
application
transport 5. Data flow begins
network 4. Call connected
data link 1. Initiate call
physical
CSci4211:
6. Receive data application
3. Accept call transport
2. incoming call network
data link
physical
Weekly Summary
41
green call
four “calls” going thru
the router, each entry
corresponding one call
purple call
blue call
orange call
VCI translation table (aka “forwarding table”), built at call set-up phase
1
2
3
2
1
1
1
2
During data packet forwarding phase, input VCI is used to look up the table,
and is “swapped” w/ output VCI (VCI translation, or “label swapping”)
CSci4211:
Weekly Summary
42
Virtual Circuit: Example
“call” from host A to host B along path:
host A router 1 router 2  router 3  host B
•each router along path
maintains an entry for
the call in its VCI
translation table
• the entries piece
together a “logical
connection” for the call
Router 4
0 Router 1
1
3
2 Router 2
2
5
3
1
11
0
Host A
• Exercise: write down
the VCI translation table
entry for the call at each
router
CSci4211:
7
0 Router 3
1
3
4
2
Weekly Summary
Host B
43
CSci4211:
Weekly Summary
44
Midterm & Other Tidbits (Oct 28)
• Midterm Exams:
• graded
• statistics:
• Max. 90, Median 87, Mean 73, Min. 40
• talk to us if you have questions, especially if you
didn’t do well
• Project 2 extended to Wed Nov 3, 11:59pm
• please check “Important Dates” for upcoming
deadlines!
CSci4211:
Weekly Summary
45
Pipelined Protocols
Pipelining: sender allows multiple, “in-flight”, yet-tobe-acknowledged data segments
– range of sequence numbers must be increased
– buffering at sender and/or receiver
• Two generic forms of pipelined protocols:
Go-Back-N and Selective Repeat
CSci4211:
Weekly Summary
46
Stop & Wait: Performance Analysis
Example:
1 Gbps connection, 15 ms end-end prop. delay,
data segment size: 1 KB = 8Kb
Ttransmit
U sender
L (packet length in bits)
8 kb

 9
R (transmiss ion rate, bps) 10 b/s
 8 10 6 s  0.008 ms
L/R
L
.008



 0.00027
RTT  L / R RTT * R  L 30.008
– U sender: utilization, i.e., fraction of time sender busy sending
– 1KB data segment every 30 msec (round trip time)
--> 0.027% x 1 Gbps = 33kB/sec throughput over 1 Gbps link
Moral of story:
network protocol limits use of physical resources!
CSci4211:
Weekly Summary
47
Pipelining: Increased Utilization
sender
receiver
first packet bit transmitted, t = 0
last bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
RTT
ACK arrives, send next
packet, t = RTT + L / R
Increase utilization
by a factor of 3!
U
sender
=
3*L/R
RTT + L / R
CSci4211:
=
.024
30.008
= 0.0008
Weekly Summary
microsecon
ds
48
Questions?
CSci4211:
Weekly Summary
49
Today’s Topics (Oct 28)
• IP Addressing and IP datagram service model:
• What’s an IP address?
• IP addressing scheme:
• class-based vs. classless (CIDR)
•How do you get one? Manually config., DHCP
• How does an ISP get their address blocks?
• IP datagram forwarding: host vs. routers
• longest prefix matching
• IP datagram format, IP fragmentation and reassembly; ICMP
• Router architecture: a quick overview
• If time permits, overview of routing
CSci4211:
Weekly Summary
50
CSci4211:
Weekly Summary
51
Announcement & Reminder (Nov 21)
• Hw #3 due today at midnight
• Hw #4 is posted on class website
• Project II “milestone” report (optional)
• email TA ([email protected]) what you have
done, and what still need to be done; issues &
problems you are facing, etc.
CSci4211:
Weekly Summary
52
What We Learned Last Time (Oct 17)
• Network Layer Routing
• basic issues
• Two Basic Routing Algorithms
• Link State vs. Distance Vector
• How does LS work?
•Today:
•DV
•Routing in Internet
•RIP, OSPF and BGP
CSci4211:
Weekly Summary
53
What We Learned Last Time (Nov 14)
• Data Link Layer
•Basic functions: framing, access control, etc.
• MAC addresses and ARP
• What is MAC address?
• How it differs from IP address
• Why do we need ARP
• How does ARP work?
• Media Access Control
•Shared media: issues and difficulties
•Taxonomy of MAC protocols
• Random access control:
•ALOHA and Slotted ALOHA
CSci4211:
Weekly Summary
54
Announcement & Reminder (Dec 5)
• Project II due mid-night today
•sign up for demo slots if haven’t done so
• Hw #4 due mid-night next Tuesday (Dec 10)
• Next Thursday’s class is last class of semester!
• We’ll finish up whatever leftover today
• Review material covered in entire course,
focusing on material after midterm
• Go over a sample final exam (will posted on web)
CSci4211:
Weekly Summary
55
What We Learned Last Time (Nov 21)
• Random Access Control:
•CSMA: nonpersistent vs. p-persistent
• CSMA/CD
•What are they? How do they work?
• Adaptive Controlled Access:
• token passing vs. polling
• Ethernet
•MAC: 1-persistent CSMA/CD, binary random backoff
• collision domain, bit-time and min. frame size
• 10BaseT, 100 BaseT (Fast Ethernet), Gigabit Ethernet
• Bridge: what does a bridge do?
• transparent (“plug & play”)
• bridge forwarding table: self-learning
CSci4211:
Weekly Summary
56