DOC PREVIEW
Berkeley ELENG 122 - Introduction to Computer Networks Midterm II Review

This preview shows page 1-2-3-4-25-26-27-51-52-53-54 out of 54 pages.

Save
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

EECS 122 Introduction to Computer Networks Midterm II Review Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Topics to be Covered Transport Protocols Congestion Control and Congestion Avoidance concepts TCP variants QoS Packet Scheduling and Congestion Control RED Mechanisms Fluid Model and Token Bucket method Essential DiffServ and IntServ Concepts P D Sections 5 1 5 2 6 1 6 3 6 4 2 6 5 1 6 5 3 Project 2 Specification Katz Stoica F04 2 Topics to be Covered Transport Protocols Congestion Control and Congestion Avoidance concepts TCP variants QoS Packet Scheduling and Congestion Control RED Mechanisms Fluid Model and Token Bucket method Essential DiffServ and IntServ Concepts Katz Stoica F04 3 Transport Layer Provide a way to decide which packets go to which applications multiplexing demultiplexing Can provide more reliability in order delivery at most once delivery Can support messages of arbitrary length Govern when hosts should send data can implement congestion and flow control Katz Stoica F04 4 UDP User Datagram Protocol Minimalist transport protocol Same best effort service model as IP Messages up to 64KB Provides multiplexing demultiplexing to IP Does not provide flow and congestion control Application examples video audio streaming Katz Stoica F04 5 TCP Transmission Control Protocol Reliable in order and at most once delivery Messages can be of arbitrary length Provides multiplexing demultiplexing to IP Provides congestion control and avoidance Application examples file transfer chat Katz Stoica F04 6 TCP Service 1 2 Open connection Reliable byte stream transfer from IPa TCP Port1 to IPb TCP Port2 3 Indication if connection fails Reset Close connection Katz Stoica F04 7 Flow Control vs Congestion Control Flow control regulates how much data can a sender send without overflowing the receiver Congestion control regulates how much data can a sender send without congesting the network Congestion dropping packets into the network due to buffer overflow at routers Katz Stoica F04 8 Congestion Window cwnd Limits how much data can be in transit i e how many unacknowledged bytes can the sender send AdvertisedWindow is used for flow control MaxWindow min cwnd AdvertisedWindow EffectiveWindow MaxWindow LastByteSent LastByteAcked LastByteAcked LastByteSent sequence number increases Katz Stoica F04 9 Topics to be Covered Transport Protocols Congestion Control and Congestion Avoidance concepts TCP variants QoS Packet Scheduling and Congestion Control RED Mechanisms Fluid Model and Token Bucket method Essential DiffServ and IntServ Concepts Katz Stoica F04 10 Why do You Care About Congestion Control Otherwise you get to congestion collapse How might this happen Assume network is congested a router drops packets You learn the receiver didn t get the packet Either by ACK or Timeout What do you do Retransmit packet Still receiver didn t get the packet because it is dropped again Retransmit again and so on And now assume that everyone is doing the same Network will become more and more congested And this with duplicate packets rather than new packets Katz Stoica F04 11 Solutions Increase buffer size Why not Slow down If you know that your packets are not delivered because network congestion slow down Questions How do you detect network congestion Use packet loss as indication By how much do you slow down Katz Stoica F04 12 TCP Slow Start Goal discover congestion quickly How Quickly increase cwnd until network congested get a rough estimate of the optimal size of cwnd Whenever starting traffic on a new connection or whenever increasing traffic after congestion was experienced Set cwnd 1 Each time a segment is acknowledged increment cwnd by one cwnd Katz Stoica F04 13 Slow Start Example The congestion window size grows very rapidly TCP slows down the increase of cwnd when cwnd ssthresh cwnd 1 cwnd 2 cwnd cwnd 3 4 segment 1 segment 2 segment 3 segment 4 segment 5 segment 6 segment 7 cwnd 8 Katz Stoica F04 14 Congestion Avoidance Additive increase starting from the rough estimate slowly increase cwnd to probe for additional available bandwidth Multiplicative decrease cut congestion window size aggressively if a timeout occurs If cwnd ssthresh then each time a segment is acknowledged increment cwnd by 1 cwnd cwnd 1 cwnd Katz Stoica F04 15 Slow Start Congestion Avoidance Example cwnd 1 Assume that ssthresh 8 cwnd 2 cwnd 4 Cwnd in segments cwnd 8 ssthresh cwnd 9 Roundtrip times cwnd 10 Katz Stoica F04 16 Putting Everything Together TCP Pseudocode Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 Katz Stoica F04 17 The big picture cwnd Timeout Congestion Avoidance Slow Start sstresh Time Katz Stoica F04 18 Packet Loss Detection Wait for Retransmission Time Out RTO What s the problem with this Because RTO is performance killer In the BSD TCP implementation RTO is usually more than 1 second The granularity of RTT estimate is 500 ms Retransmission timeout is at least two times RTT Solution Don t wait for RTO to expire Katz Stoica F04 19 Fast Retransmit Resend a segment after 3 duplicate ACKs Remember a duplicate ACK means that an outof sequence segment was received Notes segment 1 cwnd 1 ACK 2 cwnd 2 segment 2 segment 3 ACK 3 cwnd 4 ACK 4 ACK 4 ACK 4 segment 4 segment 5 segment 6 segment 7 3 duplicate ACKs Duplicate ACKs due packet reordering If window is small don t get duplicate ACKs Katz Stoica F04 20 Fast Recovery After a fast retransmit set cwnd to ssthresh 2 i e don t reset cwnd to 1 But when RTO expires still do cwnd 1 Fast Retransmit and Fast Recovery implemented by TCP Reno most widely used version of TCP today Katz Stoica F04 21 Fast Retransmit and Fast Recovery cwnd Slow Start Congestion Avoidance Fast retransmit Time Retransmit after 3 duplicated acks Prevent expensive timeouts No need to slow start again At steady state cwnd oscillates around the optimal cwnd size Katz Stoica F04 22 TCP Flavors TCP Tahoe cwnd 1 whenever drop is detected TCP Reno cwnd 1 on timeout cwnd cwnd 2 on dupack TCP newReno TCP Reno improved fast recovery TCP Vegas TCP SACK Katz Stoica F04 23 TCP Vegas Improved timeout mechanism Decrease cwnd only for losses sent at current rate Avoids reducing rate twice Congestion avoidance phase Compare Actual rate A to Expected rate


View Full Document

Berkeley ELENG 122 - Introduction to Computer Networks Midterm II Review

Documents in this Course
Lecture 6

Lecture 6

22 pages

Wireless

Wireless

16 pages

Links

Links

21 pages

Ethernet

Ethernet

10 pages

routing

routing

11 pages

Links

Links

7 pages

Switches

Switches

30 pages

Multicast

Multicast

36 pages

Switches

Switches

18 pages

Security

Security

16 pages

Switches

Switches

18 pages

Lecture 1

Lecture 1

56 pages

OPNET

OPNET

5 pages

Lecture 4

Lecture 4

16 pages

Ethernet

Ethernet

65 pages

Models

Models

30 pages

TCP

TCP

16 pages

Wireless

Wireless

48 pages

Load more
Download Introduction to Computer Networks Midterm II Review
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Computer Networks Midterm II Review and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Computer Networks Midterm II Review and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?