Redes de Computadores
Célio Vinicius Neves de Albuquerque
Email: [email protected]
Url: http://www.ic.uff.br/~celio
2008/2
Livro-Texto:
REDES DE COMPUTADORES E A INTERNET
UMA ABORDAGEM TOP-DOWN
(www.aw.com/kurose_br)
James F. Kurose e Keith W. Ross
Copyright: 2006 - 3a. Edição
ISBN: 8588639181
http://www.pearson.com.br/
Referências Adicionais:
1.
Computer Networks, Andrew Tanenbaum Capítulos 1-6.
2.
An Engineering Approach to Computer
Networking, S. Keshav - Capítulos 1-16
2
Conteúdo Programático
1.
2.
3.
4.
5.
6.
7.
8.
9.
Redes de Computadores e a Internet
Camada de Aplicação
Camada de Transporte
Camada de Rede
Camada de Enlace e Redes Locais
Redes Sem Fio (Wireless) e Móveis
Multimídia em Redes
Segurança em Redes
Gerenciamentos de Redes
3
Página da Disciplina





Ementa
Contato
Referências
Calendário
Notas


2 Provas
1 Projeto Prático
4
Aplicações








Gerência de redes
Distribuição de Conteúdo (CDN), Redes P2P
Multicast em camadas
Multicast confiável
Transporte de alta velocidade
VoIP, TVoIP, VoD
Aplicações sem fio ad hoc, sensores, mesh
Aplicações móveis e sensíveis a contexto
5
Gerência de Redes
Ferramentas:
Pathchar
Nagios
Traceroute
Fping
Cacti
Source:
www.caida.org
6
Multicast
Varying Bandwidth Constraints
S
How can a single
video source
simultaneously satisfy
everyone?
10 Mbps
8 Mbps
6 Mbps
R1
8 Mbps
R2
1 Mbps
R3
7
Solution 1
Multi-Layered Video Encoding
Base Layer
…
Raw
Video
Multi-Layer
Encoder
Base layer (high priority)
Enhancement layers
(lower priorities)
Base + Enhancement
Layers
8
Problem 2
Time-Variation in Bandwidth Constraints
Time 1
S
10 Mbps
8 Mbps
Time 2
S
6 Mbps
4 Mbps
6 Mbps
R1
3 Mbps
R1
8 Mbps
R2
1 Mbps
R3
10 Mbps
R2
0.5 Mbps
R3
9
Solution 2
Feedback-based Source-adaptive Encoding

S


Video Packet
R
Monitor network status
Receivers indicate
congestion in feedback
packets
Feedback is returned to
source, which adapts the
video encoding rates and
the number of its layers
Feedback Packet
10
Problem 3
Feedback Implosion

S
Too many feedback
packets return to the
source
100
20
20
R1
10
5
R2
15
R3
2
R4
11
Solution 3
Feedback Packet Merging


S
Merge feedback information
Source receives backward
feedback packet and adjusts the
number and the rates of each
layer according to rates contained{5,20}
in feedback packet
{2,5,10,20}
{2,10}
Source will generate:
4 layers
Cumulative rates: 2, 5, 10, 20 {20}
R1
Layers received:
I, II, III, IV
{5}
R2
I, II
{10}
{2}
R3
R4
I, II, III
I
12
Feedback Merging Servers

Feedback mergers:




S
Standalone feedback merger
Router with feedback merger
Receiver with feedback merger
Source
R1
R2
R3
R4
Feedback path
13
Multicast

Topologia

D1
Video real

4 Mbps
r=6Mbps

10 Mbps
S
D2
10 Mbps
Sequências


2.5 Mbps

r=7.5Mbps
Wavelet Multilayer
Encoder
Return of Jedi
Flower Garden
Wallace and Grommit
1 Mbps
r=9Mbps
r: Tráfego de interferência Poisson
D3
14
Multicast
15
Multicast

Movie Sample: Wallace & Grommit
D1
43.14dB
4 Mbps
r=6Mbps
10 Mbps
S
D2
10 Mbps
37.8dB
2.5 Mbps
r=7.5Mbps
1 Mbps
r=9Mbps
D3
28.5dB
16
Controle de Congestionamento e
compartilhamento injusto de banda
Gargalo
R
Video
R
FTP
Vídeo não adaptativo
Aplicação TCP
Pacotes
perdidos
17
Congestionamento
18
Core-stateless networks
Domain 1
LAN
Domain 2
Edge
router
LAN
Edge
router
Core router
LAN
LAN
End Systems
End system
Edge (ingress/egress) router
Core router
19
Network Border Patrol (NBP)
6 Mbps
4.1
46 Mbps
Mbps
6 Mbps
4.1
46 Mbps
Mbps
4.1
446Mbps
Mbps
Mbps
64 Mbps
FLOW 1
FTP
NONADAPTIVE
VIDEO
S1
8 Mbps
8 Mbps
IR
8 Mbps
8 Mbps
CR
S2
R1
ER1
2 Mbps
ER2
R2
FLOW 2
62 Mbps
24 Mbps
2 Mbps
2 Mbps
2 Mbps
2 Mbps
20
Compartilhamento justo
21
Single shared link configuration
TCP Flow
S1
I1
10 Mbps
2 ms
R1
3 ms
10 Mbps
S2
1.5 Mbps
3 ms
E1
S3
E2
S4
10 Mbps
10 ms
R2
5 ms
128 kbps
I2
Unresponsive UDP Flow
22
Congestion collapse problem
Severe congestion
collapse using FIFO
only
Moderate congestion
collapse using WFQ
only
23
Congestion collapse problem
No congestion collapse using NBP with FIFO
24
Unfairness problem
Severe unfairness
using FIFO only
Moderate unfairness
using NBP with FIFO
25
General fairness configuration 2
D
E
E
R
20ms
50
Mbps
R
I
I
A B D
E EAB
E
F
E
10ms
E
5ms
R
100
Mbps
50
Mbps
I
A
H
F
R
H
AAA CCC GGGGG GGBBB
E
5ms
150
Mbps
R
E
5ms
150
Mbps
R
E
10ms
50
Mbps
I
I
I
B H H
C C C
GGGGGGG
R
26
Fairness results
NBP with WFQ
27
Fairness results
NBP with ECSFQ
28
Background
Weighted Fair Queueing (WFQ)
Output port of WFQ Router
Flow
Classifier



Per-flow
Queues
Round-robin
Scheduler
Flow classifier places packets in per-flow queues
Scheduler (e.g. deficit round robin) fairly serves the
per-flow queues
Packets from flows transmitting at lower rates experience lower
delays!
29
Background
Core-stateless Fair Queueing (CSFQ)
Output port of CSFQ Router
Single
Queue
Congested
Uncongested
FIFO
Scheduler
Drop
on
input





Packets are labeled by ingress routers with the flow input rate
Packets are placed in a single FIFO queue
If the queue occupancy is higher than a threshold, Drop-on-input
module probabilistically drops packets from flows transmitting at
a rate higher than their estimated fair share
If the queue occupancy is lower than a threshold, CSFQ is
ineffective
Packets from all flows experience the same delay!
30
Proposed Enhanced Core-stateless
Fair Queueing (ECSFQ)
Output port of ECSFQ Router
Drop
and
schedule
on
input

Congested
Uncongested
Scheduler
Extends CSFQ:


Single
Queue
ECSFQ places packets from flows transmitting at a rate
lower than their estimated fair share, ahead in the single
queue, a priority queue, independent of the queue
occupancy
Similar to WFQ, packets from flows transmitting at lower rates
experience lower delays!
31
Comparison of WFQ, CSFQ and
ECSFQ
Output port of WFQ Router
Flow
Classifier
Per-flow
Queues
Round-robin
Scheduler
Output port of CSFQ Router
Drop
on
input
Single
Queue
FIFO
Scheduler
Output port of ECSFQ Router
Drop
and
schedule
on
input
Single
Queue
Scheduler
32
Comparison
Requirement
of per-flow
state
Requirement
of per-flow
processing
Fair bandwidth
allocation
per-flow
Fair queueing
delay
per-flow
WFQ
High
High
Fair
Fair
CSFQ
None
None
Approximate Fair
Unfair
ECSFQ
None
None
Approximate Fair
Approximate Fair
33
Bandwidth Allocation
Scenario:
- Shared 1.5Mbps link with 3 competing flows
- 1 UDP at 1Mbps and 2 TCP flows
Existing CSFQ:
- Fair allocation for TCP Reno sources
- Unfair allocation for TCP Vegas sources
Proposed ECSFQ:
- Fair allocation for TCP Vegas sources
34
Comentários finais








Gerência de redes
Distribuição de Conteúdo (CDN), Redes P2P
Multicast em camadas
Multicast confiável
Transporte de alta velocidade
VoIP, TVoIP, VoD
Aplicações sem fio ad hoc, sensores, mesh
Aplicações móveis e sensíveis a contexto
35