Advanced Computer Networks: Lecture 35 - 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 (489.49 KB, 16 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
1
Lecture No. 35
2
RouterBased
Congestion Control Solution
3
Congestion Control
• Basics: problem, terminology,
approaches, metrics
• Solutions
– Routerbased: queuing disciplines
– Hostbased: TCP congestion control
• Congestion avoidance
– DECbit
– RED gateways
• Quality of service
4
Router Solutions: Queuing
Disciplines
• Router defines policies on each outgoing
link
– Allocates buffer space:
Which packets are discarded?
– Allocates bandwidth:
Which packets are transmitted?
– Affects packet latency:
When are packets transmitted?
5
More Fairness Choices
• First In, First Out (FIFO)
– Fairness for latency
– Minimizes perpacket delay
– Bandwidth not considered (not good for
congestion)
• Fair queuing
– Fairness for bandwidth
– Provides equal bandwidths (possibly weighted)
– Delay not considered
6
Fair Queuing
• Logical roundrobin on bits
– Equallength packets: roundrobin on packets
– Variablelength packets ?
• Idea
– Let Si denote accumulated service for flow i
– Serve the flow with lowest accumulated service
– On serving a packet of length P from flow i,
update
Si = Si + P
7
Fair Queuing Example
15
10
10
10
20
A
10
B
15
20
10
15
20
10
C
20
15
SA 0
10
10
10
20
20
35
35
SB 0
0
20
20
20
20
20
30
SC 0
0
0
15
15
35
35
35
8
Fair Queuing Example
• Compare Si or Si + P ?
15
10
10
10
20
A
20
B
15
10
20
10
15
10
C
20
15
SA 0
10
10
20
20
20
35
35
SB 0
0
0
0
20
30
30
30
15 15 15 15 15 35
SC 0 0
Another detail: update counter at start or end of transmission ?
9
Fair Queuing
• Why is the suggested approach not
quite adequate?
– Flows can “save up” credit
– No transmission for long time (call it T)
– Burst uses all bandwidth for up to time
T x flow’s share of link
10
Fair Queuing
• How might we fix this problem?
– Don’t allow inactive flows to retain
service rates below that of any active flow
– i.e. after updating some flow’s Si
• For each flow j with no packets in its
queue
• Set Sj to the minimum Sk for all active
flows k
(or 0 if no flows are active)
11
Fair Queuing Example
10
10
20
A
10
B
20
20
15
10
C
20
15
SA 0
10
10
15
20
30
SB 0
0
20
20
20
30
SC 0
0
0
15
35
35
12
Weighted Fair Queuing
• Extend fair queuing
• Notion of importance for each flow
• Implement as weight Wi for flow i
• Update accumulated service with P/Wi
13
Weighted Fair Queuing Example
15
10
10
20
10
10
20
15
A (1)
20
B (2)
C (1) S 0
A
10
10
10
15
20
10
10
10
10
20
20
20
20
SB 0
0
10
10
10
15
20
20
SC 0
0
0
15
15
15
15
35
14
Weighted Fair Queuing
• What makes up a flow for fair queuing in the
Internet ?
• Too many resources to have separate
queues/variables for hosttohost flows
• Scale down number of flows
• Typically just based on inputs
• e.g. share outgoing STS12 between incoming
ISP’s
15
Fair Queuing in the Internet
10
10
10
10
10
10
10
10
10
A
10
B
10
10
10
10
STS12
C
D
ServiceLevel
Agreements
(SLAs) for
STS3
(155Mbps)
10
STS4
SA 0
10
10
10
20
20
20
SB 0
0
10
10
10
20
20
SC 0
0
0
10
10
10
20
SD 0
0
0
10
10
10
20
16
