Transcript Evolution of Data Networks

ELEN 602 Lecture 18
• Packet switches
• Traffic Management
1
Gateway
Organization
Servers
To internet or
wide area
network
s
s
Backbone
R
R
R
S
Departmental
Server
R
S
S
R
R
s
s
s
s
s
s
s
s
s
Campus Network
2
Intradomain and Interdomain levels
Interdomain level
Border routers
Internet service
provider
Autonomous system
or domain
Border routers
LAN level
Intradomain level
3
National service provider A
(a)
National service provider B
NAP
NAP
National service provider C
(b)
NAP
RA
Route
server
RB
LAN
RC
4
Components of Generic Switch/Router
Control
Line Card
…
…
N
Line Card
Line Card
1
2
Line Card
3
Line Card
…
3
Line Card
Line Card
…
Line Card
Interconnection
Fabric
1
2
N
5
Buffering
• Wherever contention is possible
– input port (contend for fabric)
– internal (contend for output port)
– output port (contend for link)
• Head-of-Line Blocking
– input buffering
2
1
2
Port 1
Switch
Port 2
6
Crossbar Switches
7
Workstation based Router
NIC Card
3
NIC Card
N
NIC Card
…
…
1
2
NIC Card
CPU
Main Memory
I/O
Bus
8
Workstation-Based
• Aggregate bandwidth
– 1/2 of the I/O bus bandwidth
– capacity shared among all hosts connected to switch
– example: 800Mbps bus can support 8 T3 ports
• Packets-per-second
– must be able to switch
small packets
– 100,000 packets-persecond is achievable
– e.g., 64-byte packets
implies 51.2Mbps
I/O bus
CPU
Interface 1
Interface 2
Interface 3
Main memory
9
Self-Routing Fabrics
• Banyan Network
– constructed from simple 2 x 2 switching elements
– self-routing header attached to each packet
– elements arranged to route based on this header
– no collisions if input packets sorted into ascending order
– complexity: n log2 n
001
011
001
110
111
011
110
111
10
High-Speed IP Router
• Switch (possibly ATM)
• Line Cards + Forwarding Engines
– link interface
– router lookup (input)
– common IP path (input)
– packet queue (output)
• Network Processor
– routing protocol(s)
– exceptional cases
11
Line card
(forwarding
buffering)
High-Speed Router
Routing
CPU
Buffer
memory
Line card
(forwarding
buffering)
Line card
(forwarding
buffering)
Line card
(forwarding
buffering)
Routing software
w/ router OS
12
Virtual-circuit Packet Switching
Packet
Packet
13
Delays in virtual-circuit switching
t
Connect
request
CC
CR
CC
CR
Connect
confirm
1
2
3
1
2
t
Release
3
t
1
2
3
t
14
Signaling for virtual-circuit setup
SW
1
Connect
request
Connect
confirm
SW
2
…
Connect
request
SW
n
Connect
request
Connect
confirm
15
Example virtual-circuit routing table
Entry for packets
with identifier 15
Identifier
Output
port
Next
identifier
12
13
44
15
15
23
27
13
16
58
7
34
16
FIFO Queuing:
(a)
Packet buffer
Arriving
packets
Transmission
link
Packet discard
when full
FIFO Queuing with discard priority
(b)
Packet buffer
Arriving
packets
Class 1
discard
when full
Transmission
link
Class 2
discard
when threshold
exceeded
17
HOL Priority queuing
Packet discard
when full
High-priority
packets
Transmission link
Low-priority
packets
When
high-priority
queue empty
Packet discard
when full
18
Sorting packets according to priority tag
Arriving
packets
Sorted packet buffer
Tagging
unit
Packet discard
when full
Transmission
link
19
Fair queuing
Packet flow 1
Packet flow 2
Approximated
bit-level
round robin
service
C bits/second
Transmission link
Packet flow n
20
Fluid-flow and packet-by-packet FQ
Queue 1
@ t=0
Fluid-flow system:
both packets served
at rate 1/2
1
Queue 2
@ t=0
t
0
1
Packet from
queue 2 waiting
Both packets
complete service
at t=2
2
Packet-by-packet system:
queue 1 served first at rate 1;
then queue 2 served at rate 1.
1
Packet from queue 2
being served
Packet from
queue 1 being
served
t
0
1
2
21
Computing finishing times
Rounds
Generalize so R(t) is continuous, not discrete
R(t) grows at rate inversely
proportional to nactive(t)
22
2
Queue 1
@ t=0
Fluid-flow system:
both packets served
at rate 1/2
1
Queue 2
@ t=0
Packet from queue
s served at rate 1
0
2
t
3
Packet-by-packet fair queueing:
queue 2 served at rate 1
Packet from
queue 2 waiting
1
Packet from
queue 1 being
served at rate 1
0
1
2
t
3
Fluid-flow and packet-by-packet FQ
23
Queue 1
@ t=0
Fluid-flow system:
packet from queue 1
served at rate 1/4;
Queue 2
@ t=0
1
Packet from queue 2
served at rate 3/4
Packet from queue 1
served at rate 1
t
0
1
Packet from
queue 1 waiting
2
Packet-by-packet weighted fair queueing:
queue 2 served first at rate 1;
then queue 1 served at rate 1.
1
Packet from queue 1
being served
Packet from
queue 2 being
served
t
0
1
Weighted Fair Queuing
2
24