Transcript 投影片 1 - NTUT

Chen-Nien Tsai
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
1
 Introduction
 The Architecture of Switches

The Evolution in the Architecture of Switches
 Switch Architecture Classification

Buffering Strategies
 Output-Buffered Switches
 Input-Buffered Switches
 Scheduling Algorithms (arbitration schemes)

PIM, iRRM, iSLIP, DRRM
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
2
 A packet switch is a node used to build a
network which utilizes the packet switching
paradigm for data communication.
ATM switches
 IP routers

 The high-speed switching technologies are
common to both ATM switches and IP routers.

Use a simple term: “switch”.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
3
 Fixed-length data units are better
Time slots concept
 Higher throughput
 Simpler hardware design

 Variable-length packets are usually
segmented into fixed-length data units.

We call these data units “cell” (not necessarily 53
bytes like ATM cells).
Time slot
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
Time
4
 Introduction
 The Architecture of Switches

The Evolution in the Architecture of Switches
 Switch Architecture Classification

Buffering Strategies
 Output-Buffered Switches
 Input-Buffered Switches
 Scheduling Algorithms (arbitration schemes)

PIM, iRRM, iSLIP, DRRM
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
5
Control Functions
Datapath Functions
Input Ports
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
Output Ports
2008/10/16
6
 Datapath Functions
Operations that are performed on every datagram.
 Often implemented in special purpose hardware.

 Control Functions
Operations that are performed relatively infrequently.
 Implemented in software.
 System configuration, management, and exchange
of routing table information.

Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
7
 Bus-based switch with single processor
 Bus-based switch with multiple processors
 Switch-based switch with multiple processors
 Optics Inside a Switch
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
8
Typically <0.5Gb/s aggregate capacity
Routing
Table
CPU
Buffer
Memory
SharedBackplane
Backplane
Shared
Shared
bus
Line
Interface
Line
Interface
Line
Interface
MAC
MAC
MAC
Packet
arrival
 A shared central bus and a central CPU/memory
 Bottlenecks
1.
The central CPU must process every packets.
2.
Every packet has to traverse twice through the shared bus
9
Typically < 5Gb/s aggregate capacity
 Parallelism can
Cache
CPU
update
Routing
Table
Buffer
Memory
Shared
bus
Line
Card
Line
Card
Line
Card
Buffer
Memory
Buffer
Memory
Buffer
Memory
Fwding
Cache
Fwding
Cache
Fwding
Cache
MAC
MAC
MAC
Packet arrival
Local process
forwarding
increase the system
throughput.
 Each packet traverse
the bus once.
 The central CPU
maintain the Routing
tables.
 The shared bus is still a
bottleneck.
2008/10/16
10
Typically < 50Gb/s aggregate capacity
Switched Fabric
 Replacing shared bus
Line
Card
CPU
Card
Line
Card
Local
Buffer
Memory
Routing
Table
Local
Buffer
Memory
Fwding
Engine
Fwding
Engine
MAC
MAC
Packet
arrival
Packet
arrival
with a switched fabric.
 Multiple packets can be
transferred across the
fabric simultaneously.
Local process
forwarding
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
11
 A 16-port IP router, with each port operating
at 2.4 Gb/s.
 If all of the line cards wish to transfer
datagrams simultaneously, requiring a
backplane with an aggregate bandwidth of
16 x 2.4 Gb/s = 38.4 Gb/s
 It is impractical to build shared backplanes
operating at 38.4 Gb/s.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
12
Optical links
0.72 Tbps
OC 768
(39.81 Gbps)
Switch Core
Line cards
0.3 - 10Tb/s or higher routers in development
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
13
 Introduction
 The Architecture of Switches

The Evolution in the Architecture of Switches
 Switch Architecture Classification

Buffering Strategies
 Output-Buffered Switches
 Input-Buffered Switches
 Scheduling Algorithms

PIM, iRRM, iSLIP, DRRM
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
14
 Switches can be classified according to

Switching techniques
 Time-Division
Switching
 Space-Division Switching

Buffering strategies
 Input-Buffered Switches
 Output-Buffered Switches
 Virtual-Output-Queueing Switches
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
15
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
16
 A single internal communication structure
Shared by all cells traveling from input to output.
 Can be a bus, a ring, or a memory.

 Advantage

Can easily be extended to support
multicast/broadcast operations.
 Disadvantage

Capacity limitation of the internal communication
structure.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
17
 Multiple physical paths are provided
 These paths operate concurrently

Multiple cells can be transmitted simultaneously
 Advantage

High capacity
 Disadvantage

Internal link blocking may occur
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
18
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
19
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
20
 Advantages
1.
Internally nonblocking
A
path is always available to connect an idle input
port to an idle output port.
2.
3.
Simple in architecture
Modular
 Disadvantage
1.
Need N2 crosspoints
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
21
 Introduction
 The Architecture of Switches

The Evolution in the Architecture of Switches
 Switch Architecture Classification

Buffering Strategies
 Output-Buffered Switches
 Input-Buffered Switches
 Scheduling Algorithms

PIM, iRRM, iSLIP, DRRM
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
22
 Switches need buffers because
 Store and forward
 Internal link blocking
 Output port contention
 Buffers are required to be placed somewhere
in the switches

to delay packet for not to drop them.
Input 1
collision
collision
Input 2
delayed
delayed
Output 1
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
23
Switch Fabric
(nonblocking)
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
24
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
25
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
26
 Most early-date research has focused on this
architecture.

Initial demand of switch capacity is low.
A
few to 10-20 Gbit/s
100% throughput
 Easier to obtain delay bound.

 M/D/1
queue
 What if we need more capacity…
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
27
 Assume
A 24-port ATM switch, with each port operating at
2.4 Gb/s.
 The backplane is fast enough
 An ATM cell is 53 bytes-long
53  8
 Transmission time is about 177 ns
 177 ns
2.4G
 Memory access time is 10 ns

 If multiple cells are routed to the same
output …
Store multiple cells in the output buffer per 177 ns.
 The output buffer could not receive all cells.

Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
28
 To build larger-scale and higher-speed
switches.
 Two main problems:

Throughput limitation due to the head-of-line
(HOL) blocking.
 Only

58.6% throughput can be achieved.
The need of arbitrating cells due to output port
contention.
 More
difficult to obtain delay bound.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
29
 Packets destined for other output ports that
are free may be blocked.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
30
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
31
 An input may have cells granted access by
more than one output.
Each input can transfer only one cell a time.
 Other cells have to wait, and their corresponding
outputs will be idle.

Input
Output
Input
Output
Input
Output
1
1
1
1
1
1
2
2
2
2
2
2
3
3
Multiple
grants 3
3
3
3
4
4
4
4
4
4
Request
Grand
Idle
Can’t transfer since Transfer
no grant received
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
32
 The inefficiency of idle output can be
alleviated if the scheduling algorithm runs
iteratively.
Parallel Iterative Matching (PIM)
 Iterative Round-Robin Matching (iRRM)
 Iterative Round-Robin with SLIP (iSLIP)
 Dual Round-Robin Matching (DRRM)

 They are VOQ-based algorithms and assume
nonblocking switch is used (crossbar switch).
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
33
 Three Steps for each iteration
Request
1.

Each unmatched input sends a request to every
output for which it has a queued cell.
Grant
2.

If an unmatched output receives multiple requests,
it grants one by randomly selecting a request.
Accept
3.

If an input receives multiple grants, it accepts one
by randomly selecting an output.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
34
Input
Iteration 1
Output
Input
Output
Input
Output
1
1
1
1
1
1
2
2
2
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
Request
Input
Grand
Output
Input
Accept
Output
Input
Output
1
1
1
1
1
1
2
2
2
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
Iteration 2
Request
Grand
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
Accept
2008/10/16
35
1. It is difficult and expensive to implement
random function at high speed.
2. PIM could lead to unfairness between
connections.
3. PIM does not perform well for a single
iteration. (63% throughput)
Flow 1
λ1,1 = 1
λ1,2 = 1
λ2,1 = 1
2 grants
Flow 2
Flow 3
2 requests μ1,1 = 1/4
μ1,2 = 3/4
μ2,1 = 3/4
Both input 1 and output 1
select flow 1 with 1/2
probability, resulting in the
¼ departure rate.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
36
 Works similarly to PIM, but uses the round-
robin schedulers instead of random selection.
Simple to implement.
 Performs fairly.

 Two round-robin scheduler (pointers)
Accept pointer ai at input i.
 Grant pointer gj at output j.

Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
37
1. Request

Each unmatched input sends a request to every
output for which it has a queued cell.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
38
2. Grant

If an unmatched output receives multiple requests, it
chooses one that appears next in its round-robin
schedule. The pointer gj is incremented to one
location beyond the granted input.
Output 2
received two
requests
(Input 1 & 3)
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
39
3. Accept
If an input receives multiple grants, it accepts
one that appears next in its round-robin
schedule. The pointer ai is incremented to one
location beyond the accepted output.

Input 1 received
two grants
(output 1 & 2)
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
40
1. Does not perform well for a single iteration.
16 x 16 switch
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
41
 Works similarly to iRRM, but the difference is
that the grant pointers update their positions
only if their grants are accepted.
100% throughput with one iteration.
 Desynchronization effect.

Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
42
1. Request
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
43
2. Grant

If an unmatched output receives multiple
requests, it chooses one that appears next in its
round-robin schedule.
No grant
pointers are
updated
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
44
3. Accept

If an input receives multiple grants, it accepts
one that appears next in its round-robin
schedule. The pointer aj is incremented to one
location beyond the accepted output. The
accept pointers are updated only in the first
iteration.
4. Update Grant pointer

The grant pointer gi is is incremented to one
location beyond the granted input if and only if
the grant is accepted in step 3. The grant
pointers are updated only in the first iteration.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
45
Update grant
points after the
grant is accepted
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
46
iSLIP achieves 100%
throughput
• 16 x 16 switches
• One iteration
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
47
1
1
2
2
1
1
2
2
1
1
2
2
1
1
2
2
1
1
2
2
1
1
2
2
 Main concept

When a successful matched, output arbiter
moves its pointer to one position beyond the
granted input, it must be the only output that
moves it pointer to that position.
Both inputs request both
outputs. The grant arbiter of
output 1 will grant to input 1.
In the next time slots, outputs
no long contend.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
48
1. Each input arbiter performs request
selection.
2. Sends a request to the output arbiters. Input
arbiters update their pointer values.
3. Each output arbiter performs grant
arbitration. Output arbiters update their
pointer values.
4. The output arbiters send grant signals to
input arbiters.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
49
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
50
 Smaller arbitration time than iSLIP, while
achieving comparable performance.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
51
Smaller arbitration
time
Switch
Architecture
Not perform well
with one iteration
DRRM
Buffer
Strategies
100% throughput
and good memory
utilization
Difficult to
implement, unfair
iSLIP
iRRM
OutputBuffered
Switch
Scheduling
Algorithms
Capacity limitation
PIM
Arbitrating
InputBuffered
Switch
VOQ
HOL blocking
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
52
 Shared-Memory Switches
 Banyan-Based Switches
 Clos-Network Switches
 Optical Packet Switches
 IP Route Lookups
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
53
Scheduling Algorithm (arbitration schemes)

1.
2.
3.
4.
T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker, "Highspeed switch scheduling for local-area networks," ACM Trans.
Comput. Syst., vol. 11, no. 4, pp. 319-352, 1993. (PIM)
N. McKeown, P. Varaiya, and J. Walrand, "Scheduling cells in an
input-queued switch," IEEE Electronics Letters, vol. 29, no. 25,
pp. 2174-2175, 1993. (iRRM)
N. McKeown, "The iSLIP scheduling algorithm for input-queued
switches," IEEE/ACM Transactions on Networking, vol. 7, no. 2,
pp. 188-201, 1999. (iSLIP)
H. J. Chao and J. Park, "Centralized contention resolution
schemes for a large-capacity optical ATM switch," Proc. IEEE
ATM Workshop, pp. 11-16, 1998. (DRRM)
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
54
General Introduction

1.
2.
3.
4.
N. McKeown, "A Fast Switched Backplane for a Gigabit
Switched Router," Business Communication Review, vol. 27, no.
12, 1997.
H. J. Chao, C. H. Lam, and E. Oki, Broadband Packet Switching
Technologies – A Practical Guide to ATM Switches and IP Routers,
John Wiley & Sons Inc., 2001.
F. Chang, New Generation Backbone Router - A Longevous
Solution, available at
http://tp2rc.tanet.edu.tw/ppt/91sem/NGRouterSolution.ppt
Kai-Wei Ke, An Introduction to Switches and Routers, CCN
Lectures Notes.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
55
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
56
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
57
To prevent routers from being the bottleneck
100,000%
DWDM Link speed
x2/8 months
10,000%
Internet Traffic
x2/1 yr
Router capacity
x2.2/18 m
Moore’s law
x2/18 m
1,000%
DRAM access rate
x1.1/18 m
100%
1996
1998
2000
2002
and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
Source: SPEC95Int & David Wireless
Miller, Stanford.
2008/10/16
58
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
59
 Multiple CPUs
process packets
in parallel.
 Parallelism can
increase the
system
throughput.
Make
forwarding
decisions
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
60
 Placing a separate
CPU at each
interface.
 Each packet traverse
the bus once.
 The central CPU
maintain the
forwarding tables.
Make
forwarding
decisions
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
61
 Multiple packets can
be transferred
across the
backplane.
Make
forwarding
decisions
Switched fabric
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
62
 The Forwarding Decision
Destination address parsing
 Forwarding table lookup
 Modifying packet header (TTL, checksum, etc.)

 The Backplane (fabric)

Forward datagram to outgoing port.
 The Output-link Scheduler
The datagram waits for its turn to be transmitted on
the output link.
 FIFO queue or other advanced algorithm.

Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
63
 Main concept

When a successful matched, output arbiter moves
its pointer to one position beyond the granted
input, it must be the only output that moves it
pointer to that position.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
64
Access Time (ns)
Commercial
DRAM
x1.1/18 m
Moore’s law
x2/18 m
Source: Nick McKeown, Stanford.
DWDM Link speed
x2/8 months
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
Router capacity
x2.2/18 m
65
Input
Ports
Output
Ports
FIFO Buffer
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
66
 A time slot is divided into N mini-slots.
 During each mini-slot, a cell from an input is
broadcast to all output ports.
 Each address filter will decide if the cell
should be stored in the following FIFO.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
67
 Advantage
1.
Easy to support multicasting
 Disadvantages
1.
2.
3.
4.
The medium may be congested.
High speed shared medium is difficult to design.
Memory speed may limit the switch size.
Lack of memory sharing among FIFO buffers.
 To overcome the 4th disadvantage

Shared-Memory Switch
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
68
Input
Ports
Output
Ports
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
69
 Incoming cells are time-division multiplexed
into a single data stream and sequentially
written to the shared memory.
 The routing of cells is accomplished by
extracting stored cells to form a single output
data stream.
 The output data stream is demultiplexed into
several outgoing lines.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
70
 Advantage
1.
2.
Easy to support multicasting
Better memory utilization
 Disadvantages
1.
2.
3.
4.
The medium may be congested.
High speed shared medium is difficult to design.
Memory speed may limit the switch size.
The control in the switches is more complicated.
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
71
 Crossbar-based switches
 Fully interconnected switches
 Banyan-based switches
Crossbar-based
Fully
interconnected
Nonblocking
Yes
Yes
No
Self routing
Yes
No
Yes
Complexity
N2
N2
NlogN
Features
Banyan-based
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
72
Wireless and Broadband Network Laboratory (WBNLAB) Dept. of CSIE, NTUT
2008/10/16
73