Advanced Computer Networks: Lecture 34 - Dr. Amir Qayyum
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (281 KB, 21 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
1
Lecture No. 34
2
Where we are now …
• Understand how to
–
–
–
–
–
–
–
Build a network on one physical medium
Connect networks together (with switches)
Implement a reliable byte stream on Internet
Implement a UDP/TCP connection/channel
Address network heterogeneity
Address global scale
Endtoend issues and common protocols
• Today’s topic
– Congestion control
3
Congestion Control
Outline
– Queuing Discipline
– Reacting to Congestion
– Avoiding Congestion
4
Air Travel
• Planning a vacation for your semester break ?
• Try a trip to scenic Northern Areas
• Its a mere 3 hops from VUIslamabad
Islamabad
Airport
Flight
was
overbooked
Peshawer
Sakardu
VU
5
Congestion Control
• Reading: Peterson and Davie, Ch. 6
• Basics: problem, terminology, approaches,
metrics
• Solutions
– Routerbased: queuing disciplines
– Hostbased: TCP congestion control
• Congestion avoidance
– DECbit
– RED gateways
• Quality of service
6
Congestion Control Basics
• Problem
– Demand for network resources can grow
beyond the resources available
– Want to provide “fair” amount to each user
• Examples
– Bandwidth between Islamabad and Peshawer
– Bandwidth in a network link
– Buffers in a queue
7
Range of Solutions
• Congestion control: cure
congestion when it happens
• Congestion avoidance: stay away
from congestion
• Resource allocation: prevent
congestion from occurring
8
Model of Network
• Packetswitched internetwork (or
network)
• Connectionless flows (logical
channels/connections) between
hosts
9
State Maintained in Routers
• Hard state: state used to support routing
• Soft state:
– Information about flows
– Helps control congestion
– Not necessary for correct routing
10
Congestion Control Basics
• Router role
• Controls forwarding and dropping policies
• Can send feedback to source
• Host role
• Monitors network conditions
• Adjusts accordingly
• Routing vs congestion
• Effective adaptive routing schemes can
sometimes help congestion
• But not always
11
Finite Buffering Capacity per Output
Standard checkin lines
Customer
Service
x
a
angry mob eagerly awaiting
opportunity to address
underpaid customer service
representative
1x6 Switch
you are turned
away at door
12
Congestion Control Taxonomy
13
Congestion Control Taxonomy
• Why is explicit perflow congestion feedback
from routers rarely used in practice?
– Too many sources to track
• Millions of flows may fan in to one router
• Can’t send feedback to all of them
– Adds complexity to router
• Need to track more state
• Certainly can’t track state for all sources
14
Congestion Control Taxonomy
– Wastes bandwidth: network already
congested, not the time to generate more
traffic
– Can’t force the sources (hosts) to use
feedback
• Sol: use stochastic methods to select fairly
between flows, or classify flows into
categories at edge routers
15
Why Consider Rate Control ?
• Buffer space (window size) is an intrinsic
physical quantity
• Can provide rate control with window control
• Only need estimate of RTT
• Answer:
– Want rate control when granularity of averaging
must be smaller than RTT
16
Criticism of Resource Allocation
• Example: you have 10 Gbps total bandwidth
• Case 1: reserve whatever you want
– Users’ line of thought: On average, I don’t need much
bandwidth, but when my personal web crawler goes to
work, I need at least 100 Mbps, so I’ll reserve that much.
– Result: 100 users consume all bandwidth, all others get 0
• Case 2: fair/equitable reservations
– 35,000 students + 5,000 faculty and staff
– Each user gets 250 kbps, almost 5x a modem! (watch
that crawler crawl...)
17
Back to Air Travel Analogy
• Daily Islamabad to Peshawer flight, ~200 seats
• Case 1: reserve whatever you want
– 200 of us get seats. I’m Gold...are you ?
• Case 2: fair/equitable reservations
– 2,000 possible customers
– 0.099 seats per customer per flight
– Disclaimer: the passenger assumes all risks and
damages related to unsuccessful reassembly in
Peshawer !!!
18
Congestion Control Metrics
• How do we evaluate solutions ?
– Effectiveness (shown as power in the figure
below)
– fairness
19
Congestion Control Metrics:
What’s Fair ?
• Give flow A 1/3 of the link bandwidth ?
– Globally “fair”
– A uses 2 links at 1/3 bandwidth
– B and C use 1 link at 2/3 bandwidth
• Give flow A 1/2 of the link bandwidth ?
– Locally “fair” (fair on each link)
– Also globally “fair”: maximizes minimum flow
20
Power Measure for a Sliding
Window
• Bottleneck link with capacity C
• Roundtrip time RTT
21
