1999.2.9
손장우
son@netmanias.com
www.netmanias.com
Netmanias Confidential
Content
.Generic packet switch 구조
.라우터구조의짂화
.G/T.Router architecture 분석
.G/T.Router의핵심기술
.New router architecture
Netmanias Confidential
Generic Packet Switch 구조
.Generic Packet Switch 구조
.Forwarding Function
.Switching Function
.Various packet switches
Netmanias Confidential
Generic Packet Switch 구조Packet switch(ATM switch, LAN switch, IP Router)
“도착(ATM cell/MAC frame/IP packet)을
어느outgoing interface(output port)로
포워딩할것인가?”
Forwarding decision후, 이cell/frame/packet을해당목적지outgoing interface(output port)로젂달해주는기능“어떤방법과구조로, 얼마나빨리?”
Routing, Control, Mgt : Routing protocol실행시켜route를계산하고
routing table을생성및관리. Admission control,… 시스템관리, 구성관리,...
FT생성: IP~ RIP/OSPF/BGP,   ATM~ UNI/PNNI/Q.293,  Ethernet~ STP
QoS/CoS 제공 =-CBQ, WFQ (delay) =-RED, WRED (loss)
Forwarding
& Classification
Function
Routing/Signaling/ mgt. Function
Input
port i
output
port j
Scheduling Function
Switching Function
(Fabric + Buffer)
Per-packet processing
Control
Data-path
Netmanias Confidential
Forwarding Function
Packet
IP Router
Packet
cell
ATM Switch
VPI/VCI table
{in port,VPI/VCI, out port,VPI/VCI}
cell
Packet
LAN Switch
MAC SAT table
{MAC addr.,port#,age}
Packet
IP routing table
{dst prefix, next hop, outgoing interface, MAC addr.…}
#2
#2
#2
Switching Function
Switching Function
Switching Function
lookup
Internal routing tag,rewrite
lookup
Internal routing tag,(new VPI/VCI)
lookup
Internal routing tag
Netmanias Confidential
Switching Function
Output Buffering
Shared Buffering
Input Buffering
2
2
2
2
2
2
Fabric
Buffer
Fabric
Buffer
Fabric: shared bus, shared memory, crossbar, Banyan, multistage interconnection network, ….
#2
Netmanias Confidential
Various switches
FT
VPI/VCI
ATM
SW H/W
PNNI
Q.293
FT
VPI/VCI
ATM SW H/W
IP
IFMP
FT
VPI/VCI
ATM
SW H/W’
IP
TDP
FT
VPI/VCI
ATM
SW H/W
IP
ATMARP/NHRP/MARS  
PNNI
Q.293
IP FT
{dst prefix,,,}
Shared Bus
IP
IP FT{dst prefix,,,}
SF
(SM, CXB)
IP
ATM switch
IP switch(Ipsilon)
Tag switch(Cisco)(MPLS)
MPOA
Legacy router
Gigabit router
(L3 switch)
Netmanias Confidential
Various switches
SAT
SF
(SM, CXB)
STP
IP RTSAT
SF
(SM, CXB)
IP
STP
L2 switch
L2/3 switch
(Multilayer switch)
Netmanias Confidential
라우터의고속화= Data path의H/W화
Forwarding
& Classification
Function
Routing/Signaling/ mgt. Function
Input
port i
output
port j
Scheduling Function
Switching Function
(Fabric + Buffer)
Control
Data-path
Control Function.Routing protocol(RIP, OSPF,BGP,..)
.Populates Routing Table
.System management
.상대적으로발생빈도가낮음
DataPath Function.모든IP packet에대해수행
.Forwarding decision, switching, output link scheduling
Netmanias Confidential
라우터구조의짂화
.Traditional Router architecture and forwarding scheme
.Forwarding scheme의변화
.Switching Fabric의변화
.대체적인Gigabit/Terabit Router의구조
Netmanias Confidential
Traditional Router Architecture
.General purpose microprocessor(CPU): Routing과forwarding기능을모두수행
.Packet forwarding: CPU + cache + Memory (full Routing Table)
.Centralized forwarding(모든패킷이RP를거친다.)
.Shared Bus: 533Mbps(Cisco 4000),  up to 2~3Gbps
.Multi-protocol(IP, IPx, Appletalk, DECnet,…)  지원
.다양한LAN technologies(Ethernet, Token Ring, FDDI,…)지원
.2 datapaths : Slow path(Processor switching), Fast path(cache switching)
Line
Interface
Card
Shared bus
Routing
protocol
(RIP, OSPF
,BGP,...)
System
mgt
Routingtable mgt.
Packet forwarding
(LPM)
Packet
filtering
(보앆, 분리)
….
Ethernet
FDDI
Route Processor (RP)
Backplane Bus
Route Processor (RP)
cache
RT
CPU
Shared
buffer
cache
CPU
Shared
buffer
Full RoutingTable
Line Interface Card (LIC)
Netmanias Confidential
Process switching (slow path) : First packet
RT
cache
CPU
Shared
buffer
Line
interface
Shared bus
L3
L2
.copy a packet to shared buffer
.lookup cache (EM) find entry =65.32.58.49 in cache
.lookup RT (LPM)    find entry = 65.32/6 in RT (긴시갂소요)
.initialize cache
.rewrite MAC frame header
.send to line interface
.calculate CRC and send to link.
L2
L3
L3
.
L3
.
.
L2
.
L2
L3
.
.
.
LPM
Routing processor(RP)
Dest IP =
65.32.58.49
Netmanias Confidential
Fast cache switching (fast path):Subsequent packets
RT
cache
CPU
Sharedbuffer
Line
interface
Shared bus
L3
L2
L3
L3
.
L2
L3
.
L2
.
.copy a packet to shared buffer
.lookup cache      find entry =65.32.58.49 in cache
.rewrite MAC header
.send to line interface
.calculate CRC and send to link.
L2
L3
.
.
EM
Routing processor(RP)
Dest IP =
65.32.58.49
Netmanias Confidential
Problems of traditional router ()Forwarding scheme
.Main CPU가packet forwarding도수행(routing fn,management fn,…)
.Centralized forwarding :
.하나의CPU가모든line I/f로부터들어오는모든패킷을포워딩(RT든cache든) .NP로트래픽집중~병목= NP로의access, CPU의Forwarding decision
.S/W-based forwarding : LPM ~ low forwarding rate
.Cache-based forwarding : Locality 문제
..Routing table에routes수가맋으면cache hit율이떨어짂다. Cache hit rate 00.50%, performace 90%저하
RT
cache
CPU
Line
interface
Shared bus
L2
L3
L2
L3
L2
L3
L3
L2
L3
Routing processor(RP)
Routingprotocol(RIP, OSPF,BGP,...)
System
mgt
Routing
table mgt.
Packet forwarding
(LPM)
Packet
filtering
(보안, 분리)
….
Shared
buffer
Netmanias Confidential
Problems of traditional router (2)Switching Fabric
.Shared bus: not scalable(bus capacitance limitation), < 2.5 Gbps
.2 HOP operation:
..congestion시에bus access를위한delay 증가.
..system throughput감소(한packet이버스를두번경유해야하므로shared bus용량이Gbps면실제스위칭용량은0.5Gbps)
RT
cache
CPU
Shared
buffer
Line
interface
Shared bus
L2
L3
L2
L3
L2
L3
L3
L2
L3
Routing processor(RP)
Netmanias Confidential
Router architecture의짂화과정
.Forwarding scheme의변화
.cache-based(): Distributed forwarding
.cache-based(2): RF과FF의분리
.cache-based(3): SF사용
.Full RT lookup(): RF과FF의분리
.Full RT lookup(2): FT을각Line I/f에분산
.Full RT lookup(3): SF사용
Netmanias Confidential
cache-based(): Distributed forwarding
CPU
CPU
Update
buffer
buffer
buffer
buffer
buffer
buffer
buffer
buffer
cache
cache
cache
cache
Shared
buffer
Sharedbuffer
RT
cache
RT
cache
.Distributed Forwarding: Routing cache를각line card로분산시킴
.Data Path
.) First packet .shared buffer .RT lookup (LPM) .outgoing line interface
.2) Route processor updates caches in each line interface
.3) Subsequent packets .lookup cache in line interface .outgoing line interface
.장점
.분산forwarding .NP로의트래픽집중해소, Main CPU는first packet포워딩
.# of Bus access가준다.system throughput증가
Netmanias Confidential
cache-based(2): RF과FF의분리cache-based(3): SF사용
CPU
0.264
buffer
buffer
buffer
buffer
buffer
buffer
buffer
buffer
Switch
Fabric
RT
cache
FE card
0.264
RT
cache
FE card
Shared
buffer
RT
cache
CPU
RT
cache
RP
FEC
FEC
첫번째
패킷
두번째패킷
.Routing 기능과Forwarding기능을분리: Forwarding기능맊젂담하는Forwarding engine card(FEC)를둠.
.FEC를복수개사용: (Central CPU로의트래픽병목을경감)
.FEC로의트래픽집중으로인한병목해소
.Forwarding engine의부하분담
.FEC : SW-based forwarding (.264+cache+memory, LPM)
.고성능processor사용으로포워딩율높임
.Switching Fabric사용: high throughput
.Data Path
.) packet도착: Header맊Forwarding Engine card로젂송(SF통해)
.2) FE card: sends {updated header + forwarding instruction} back to the line interface
.3) Line interface send the packet to outgoing interface.
Netmanias Confidential
Full RT lookup
CPU
Shared
buffer
FIB
CPU
Shared
buffer
Cache를사용하지않고
FIB에서LPM수행
LPM: ASIC or
dedicated processor
FIB
CPU
FIB
buffer
Update
buffer
FIB
buffer
buffer
FIB
buffer
buffer
FIB
buffer
buffer
FIB
CPU
FIB
buffer
Update
buffer
FIB
buffer
buffer
FIB
buffer
buffer
FIB
buffer
buffer
Switch
Fabric
RT
cache
RT
RT
RT
C7200
C8500C2000
C7500
Netmanias Confidential
Full RT lookup(): FT을두어RF과FF의분리
.Cache를사용하지않고모든패킷에대해Forwarding table을lookup해서Longest matching prefix를찾는다.
.Forwarding table: Routing table의mirror image (LPM에최적화시켜구성, RT의모든entries가다있음)
.Main CPU는route변화시forwarding table을update한다.
.DataPath: Topology-Driven forwarding, not traffic driven!
.LPM: ASIC or dedicated processor
.장점: cache기반방식의locality문제해결
C7200
CPU
Shared
buffer
Line
interface
Shared bus
L3
L2
L2
L3
L2
L3
L3
L2
L3
update
FT
SE
RT
Netmanias Confidential
Full RT lookup(2): FT을각Line i/f에분산
.Cache를사용하지않고모든패킷에대해Forwarding table을lookup해서
.Longest matching prefix를찾는다.
.Forwarding table: Routing table의mirror image (LPM에최적화시켜구성, RT의모든entries가다있음)
.Main CPU는route변화시forwarding table을update한다.
.DataPath: Topology-Driven forwarding, not traffic driven!
.LPM: ASIC or dedicated processor
.장점: cache기반방식의locality문제해결
C7500
CPU
Line
interface
Shared bus
update
FT
RT
FT
SE
buffer
FT
SE
buffer
FT
SE
buffer
FT
SE
buffer
Netmanias Confidential
Full RT lookup(3): SF사용
.Switching Fabric을Shared Meomory, Crossbar로대치
.2Gbps .5Gbps .40Gbps .60 Gbps
CPU
Lineinterface
update
FT
RT
FT
SE
buffer
FT
SE
buffer
FT
SE
buffer
FT
SE
buffer
Switch
Fabric
Netmanias Confidential
이렇게해서, Gigabit Router가나오게됨.
RT
FT
CPU
FT
buffer
Update
buffer
FT
buffer
buffer
FT
buffer
buffer
FT
buffer
buffer
Switch
Fabric
Cisco 8500Cisco GSR 2000Juniper M40
BBN MGR
0.264
buffer
buffer
buffer
buffer
buffer
buffer
buffer
buffer
Switch
Fabric
RT
cache
FE card
0.264
RT
cache
FE card
CPU
RT
cache
RP
FEC
FEC
update
Netmanias Confidential
일반적으로, 두구조
RT
FT
CPU
FE/FT
buffer
Update
buffer
FE/FT
buffer
buffer
FE/FT
buffer
buffer
FE/FT
buffer
buffer
Switch
Fabric
Routing Processor
update
buffer
buffer
buffer
buffer
buffer
buffer
buffer
buffer
FEC
FE/FT
FEC
FE/FT
RT
Update
update
FT
Fully-distributed Forwarding
Partially-distributed Forwarding
Switch
Fabric
SF = Crossbar or
Shared memory
FE = ASIC or
Dedicated processor
라우팅프로토콜
CPU
Routing Processor
라우팅
프로토콜
LIC
LIC
Cost & Performance
Trade-off
Netmanias Confidential
Conventional router vs. Gigabit Router
.Forwarding scheme
.Main CPU가packet forwarding 수행: forwarding기능이포함
.S/W-based forwarding : LPM ~ low forwarding rate
.Centralized forwarding : 하나의CPU가각line i/f로부터들어오는모든패킷을포워딩
.Cache-based forwarding : Locality 문제
.Switching Fabric
.Shared bus: not scalable, < few Gbps
.2 HOP operation: congestion시에bus access를위한delay 증가
Central CPU
Shared
buffer
RT
cache
RT
Central CPU
FE
buffer
Update
buffer
FE
buffer
buffer
FE
buffer
buffer
FE
buffer
buffer
Switch
Fabric
Routing
protocol
(RIP, OSPF
,BGP,...)
Systemmgt
Routing
table mgt.
Packetforwarding(LPM)
Packet
filtering
….
Routing
protocol
(RIP, OSPF
,BGP,...)
System
mgt
Routing
table mgt.
….
Distributed H/W based forwarding
Separation data path and control plane
Fast switching using switching fabric
Netmanias Confidential
Gigabit Router architecture 분석
3604
Cisco GSR
grf600
AscendGFR
aranea--28
Charlotte
Aranea-
v25k_image
NortelVersalar
prodtech
Nexabit
NX64000
m40
Juniper
M40
everest
Netcore
Everest
prodcat_oc_photo_5000
Packet engines
Power Rail
ip9520-back2
Torrent
IP9000
tsr_spot
Avici
TSR
pluris
PlurisTNR
?
Netmanias Confidential
현재, 출시된대부분의고속라우터가...
3604
aranea--28
v25k_image
grf600
Cisco GSR
Ascend
GFR
CharlotteAranea-
Nortel
Versalar
.분석하고자하는고속라우터제품
.Cisco GSR 2000 series  (40Gbps~60Gbps)
.BBN MGR (50Gbps)
.Ascend GFR 400/600 (4Gbps~6Gbps)
.Charlotte  Aranea- Terabit Router (80Gbps~.9Tbps)
.Nortel Networks Versalar 25000 (20Gbps~480Gbps)
.동일한포워딩& 스위칭파라다임을갖음.
.Distributed forwarding
.VOQ (Virtual Output Queueing)
.Crossbar switching fabric
.Fixed-size cell switching
.Segmentation & Reassembly
.Cisco GSR 2000 구조를주로분석(수치예)
Netmanias Confidential
Gigabit Router architecture
Backplane (dedicated) Bus
Switching Fabric Card
Line Interface Cards (LIC)s
Routing processor Card
Crossbar Scheduler
CrossbarSwitching Fabric(6.6)
Backplane (dedicated) Bus
Switching Fabric
Buffer memory
Scheduling
Engine
ForwardingEngine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Buffer memory
SchedulingEngine
ForwardingEngine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
ForwardingEngine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Backplane (dedicated) Bus
Switching Fabric
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
ForwardingEngine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
RoutingProcessor
Routing
Table
Netmanias Confidential
Data-path맊펴서보면,
이라우터의스위칭용량은
6 .2.5Gbps = 40Gbps
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Buffer memory
SchedulingEngine
ForwardingEngine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
ForwardingEngine
Layer2 i/f
(SONET/ATM)
Crossbar Scheduler
Crossbar
Switching Fabric
-6.6
Full-duplex
(각방향2.5Gbps)
LIC
LIC2
LIC6
...
OC-2
(622Mbps)
Switching path맊고려하고
평면그림으로그리면,
Backplane (dedicated) Bus
Switching Fabric
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
ForwardingEngine
Layer2 i/f(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Routing
Processor
Routing
Table
Routing
Processor
Routing
Table
Backplane Bus
(dedicated)
Line i/f card
Switching Fabric Card
Netmanias Confidential
Ingress and Egress functions
Egress
Buffer memory
SchedulingEngine
Layer2 i/f
(SONET/ATM)
Egress
Buffer memory
Scheduling
Engine
Layer2 i/f
(SONET/ATM)
Egress
Buffer memory
Scheduling
Engine
Layer2 i/f
(SONET/ATM)
LIC6
Ingress
Buffer memory
Forwarding
Engine
Layer2 i/f(SONET/ATM)
Crossbar Scheduler
Crossbar
Switching Fabric
-6.6
단방향(2.5Gbps)
LIC
...
Ingress
Buffer memory
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Ingress
Buffer memory
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
...
Ingress
Egress
LIC
LIC6
기능에따라ingress와
egress로구분하고,
단방향으로그리면
Netmanias Confidential
Logical architecture
Egress
Buffer memory
Scheduling
Engine
Layer2 i/f
(SONET/ATM)
Egress
Buffer memory
Scheduling
Engine
Layer2 i/f
(SONET/ATM)
EgressBuffer memory
Scheduling
Engine
Layer2 i/f
(SONET/ATM)
LIC6
Ingress
Buffer memory
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Crossbar Scheduler
Crossbar
Switching Fabric
-6.6
단방향(2.5Gbps)
LIC
...
Ingress
Buffer memory
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
IngressBuffer memory
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
...
Ingress
Egress
LIC
LIC6
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


IP forwarding, packet filer & segmentation


RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

in
out
어두운 정방향 사선
Forwarding table
& packet filters
Internal
routing tag
Crossbar
Netmanias Confidential
G/T-Router architecture
Mini-packet
IP packet


Internal routing tag
WSIFS: Wire-Speed IP forwarding and Segmentation
Crossbar
Scheduler
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


WSIFS


IQ(N,)
IQ(N,N)
...
어두운 정방향 사선

어두운 정방향 사선

어두운 정방향 사선
어두운 정방향 사선

어두운 정방향 사선

6.6
crossbar
switch
어두운 정방향 사선



어두운 정방향 사선

RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

RQ(N,N)
...
RQ(,N)
...
...
...
...
in
in N
out
어두운 정방향 사선
Output Queue
out
Forwarding table
& packet filters
Forwarding table
& packet filters
Internal
routing tag
IP packet
Mini-packet
Routing
Processor
Netmanias Confidential
라우터내Data(IP packet) 젂달경로
.IP address lookup: 입력단에도착하면패킷의헤더를검사하여next hop, outgoing interface을찾는다.
.Segmentation: 가변길이의IP 패킷을고정길이의mini-packet으로segmentation하여해당출력단의큐Q(i,j)에저장한다. 64바이트로가정한다. 이때, 각입력큐는Virtual Output Queueing 방식. 크로스바를통해스위칭되는entity는mini-packet이다.
.Crossbar scheduling: crossbar scheduler는N2개의FIFO queues에대해젂송경합을중재한다. Stanford의Tiny-Tera와Cisco의GSR 2000의경우, SLIP algorithm이적용되며, BBN의MGR의경우2DRR계열인GWFA algorithm으로경합중재를수행한다. Charlotte.
.backplane과crossbar switching fabric: mini-packet based switching fabric으로mini-packet 단위로동기식으로젂송, 슬럿화.
.Re-assembly: 해당output port로젂송된mini-packet은그패킷의마지막mini-packet이교홖되어올때까지기다리며, Re-assembler는도착하면reassembly되어IP packet을복원한다.
.Transmission link scheduling: IP packet은서비스등급에따라해당queue에저장되며QoS scheduler에의해젂송시갂을스케쥴링받아output link로젂송된다.
Netmanias Confidential
Gigabit Router의핵심기술
. Wire-speed packet forwarding (수~수십~수백Mpps)
#NAME?
#NAME?
2. Wire-speed packet classification
3. Wire-speed switching (수~수십~수백Gbps~수Terabit/sec)
#NAME?
#NAME?
4. Re-assembler
5. QoS scheduling(WFQ), WRED, CoS, Diff-serv
6. Policy-based forwarding/queueing/scheduling
7. Line interface
-POS (Packet-over-SONET)/ATM/GE
Netmanias Confidential
Wire-speed packet forwarding
.Packet forwarding: 도착패킷의destination prefix를이용해forwarding table에서이패킷의Next hop router를찾는과정
Crossbar
Scheduler
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


WSIFS


IQ(N,)
IQ(N,N)
...
어두운 정방향 사선

어두운 정방향 사선

어두운 정방향 사선
어두운 정방향 사선

어두운 정방향 사선

6.6crossbarswitch
어두운 정방향 사선



어두운 정방향 사선

RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

RQ(N,N)
...
RQ(,N)
...
...
...
...
in
in N
out
어두운 정방향 사선
Output Queue
out
Forwarding table
& packet filters
Forwarding table
& packet filters
Internalrouting tag
IP packet
Mini-packet
Routing
Processor
Netmanias Confidential
Wire-speed packet forwarding
.IF we could do FAST longest prefix matches, then we wouldn’t be here. (Nick McKeown, Stanford univ.)
.If you could get the whole IP forwarding table in fast memory(and update it invisibly) then who needs ATM?
.방법롞
.Distributed forwarding: Forwarding decision을Line card에서
.LPM: Binary tree algorithm .new and efficient LPM(Longest match를찾기위해소요되는memory access 횟수를줄일수있는알고리즘개발)
.General-purpose microprocessor .dedicated ASIC H/W (memory access속도를빠르게)
* RISC processor+cache+Conventional Patricia tree algorithm =
near wire-speed performance , but too expensive!
Netmanias Confidential
Longest Prefix Matching (LPM)
Routing table
{28.32..5/6, port}
...
{28.32.225.0/8, port3}
...
{28.0.0.0/8, port5}
28.32.95. =
0000000 0000000 0000 0000000
0000000 0000000 *
...
0000000 0000000 *
...
0000*
도착패킷의dest.IP address
Longest matchingprefix
.Class A(8bit), Class B(6bit), Class C(24bit) : exact match
.CIDR(Classless InterDomain Routing): 임의의길이network id 사용가능
.Destination address의prefix가variable length가됨
.LPM: IP address lookup시에도착패킷의dest IP address와가장길게매치되는prefix를찾음
Port 3으로젂송
Netmanias Confidential
Binary tree algorithm
P= 0*P2= *P3= 00*P4= *P5= 0*P6= 000*P7= 000*P8= 00000*P9= 0000*
Prefix {Pi}
Lookup Key .LPM
0000000*
000*
00000*
00*
0

0

0

0
0

0
0
0



P6
최악의경우prefix의길이맊큼memory access필요
IPv4의경우: 최대32번, 평균22번(current ave. prefix length)
No child
node to 0
Netmanias Confidential
Required forwarding rate
.IPv4의경우: 최대32번, 평균22번(current ave. prefix length)
.22번/packet*00nsec/번= 2.2.sec/packet=> 450000pps
.Packet length = 64B(control packet), 576B(data packet)
.Port speed = Gbps
.required forwarding rate = Gbps/(576B/packet) = 2.7 Mpps
or Gbps/(64B/packet) = 9.5 Mpps( nsec/packet ?)
Image40
Netmanias Confidential
Recent approaches
.Binary search on prefix length(Washington Univ.,997)
.Compressed multibit trie (Luea Univ., 997)
.Single-level prefix expansion(Stanford Univ., 998)
.Binary search on prefix rages(Washington Univ.,998)
.Controlled prefix expansion(Washington Univ.,998)
.상용lookup chip : MUSIC CAM L2/3/4 address lookup
.L2/4 : exact match
.L3 : longest prefix match (up to 20 Mpps)
.Vendor solution: not released, patented
.See https://www.netmanias.com/
Netmanias Confidential
Wire-speed switching
Crossbar
Scheduler
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


WSIFS


IQ(N,)
IQ(N,N)
...
어두운 정방향 사선

어두운 정방향 사선

어두운 정방향 사선
어두운 정방향 사선

어두운 정방향 사선

6.6
crossbar
switch
어두운 정방향 사선



어두운 정방향 사선

RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

RQ(N,N)
...
RQ(,N)
...
...
...
...
in
in N
out
어두운 정방향 사선
Output Queue
out
Forwarding table
& packet filters
Forwarding table& packet filters
Internal
routing tag
IP packet
Mini-packet
Routing
Processor
Forwarding& ClassificationFunction
Routing/Signaling/ mgt. Function
Input
port i
output
port j
Scheduling Function
Switching Function
(Fabric + Buffer)
Netmanias Confidential
Wire-speed switching
Output Buffering
Shared Buffering
Input Buffering
2
2
2
2
2
2
Fabric
Buffer
Fabric
Buffer
Fabric: shared bus, shared memory, crossbar, Banyan, multistage interconnection network, ….
#2
Netmanias Confidential
패킷스위치의분류
Windowing
Destination queueing(VOQ)
Output expansion
Input expansion
DQ-based Input expansion  
Switching
Fabric
Packet 스위치
Buffering
Scheme
Space-Division switch
Time-Division switch
Crossbar switch(GSR,MGR,VSR,A-)
Banyan switch
N2Disjoint path switch
Shared Medium switch
(Cubit, Fore, Cisco 4000)
Shared Memory switch
(Atlanta,Cisco 8500,JuniperM40)
Input bufferingOutput bufferingInput & Output bufferingShared buffering
Why input queueing ?
Netmanias Confidential
Buffer memory requirements(single port memory)
.장점: 최적의성능(수율과큐잉지연시갂)
.단점: N배스피드업필요
.장점: 최적의성능(수율, 큐잉지연시갂, 셀손실율)
.단점: 2N배스피드업필요
.장점: No speedup
Scalability
.단점: 수율한계
Output queueing
(N+)V
Shared queueing
2NV
Input queueing
2V
V
N Write
N Read
N Write
Read
Write
Read
Netmanias Confidential
Buffer memory requirements(single port memory)
Output queueing
(N+)V
Input queueing2V
Read
N Write
Read
Write
Netmanias Confidential
Ex) Design a 6.6@ 2.5Gbps switch
.Traditional shared bus SF (OQ): ~ few Gbps
.required shared bus BW = 6.2.5Gbps = 40 Gbps (impossible !)
.Shared memory SF (OQ): memory발젂이speed보다는size증가
.memory bus ~64bit, 0nsec DP-SRAM : 6.4Gbps
.required memory size: 32K~64K cells/packets (too expensive !)
.Multistage Interconnection network using shared memory SE
.possible, but traffic management become complex !(multiple queueing point)
.Nonblocking조건맊족위해, 4~6 times more switching elements required for 2X scale-up. (cost)
.Additional delay
.Crossbar SF (IQ)
.Crossbar switching speed & input buffer memory .2.5Gbps(스위치사이즈N=6,32,64,...에무관.탁월한확장성)
.HOL blocking: 해결가능(VOQ,…)
.Crossbar scheduler구현이난제
Netmanias Confidential
Multistage network: CLOS network

N=6
m.n
-
-2
n.m
-
-2
-3
-3
(k=N/n=4)

n
(k=N/n=4)
k.k
-
-2
-3
-4
-5
-6
(m=7)

n

N=6

n

n
Strict-sense non-blocking condition
2nd stage SE수= 2(n-)+=2n-
ststage
2ndstage
3rd
stage
Netmanias Confidential
Scalability of input queueing switch
N=64
2.5Gbps면
2.5.4=0Gbps
N=4
……………….
…………...….
2.5Gbps면
2.5.64=60Gbps
N=64
N=4
……………….
…………...….
2.5Gbps면
2.5Gbps
2.5Gbps면
2.5Gbps
Output queueing
Input queueing
Netmanias Confidential
Input-Buffering의문제: HOL blocking
2
2
Output conflict
Head-of-Line blocking
2

2
2
2

2
2
2
2
  2
2
2

2

Output queueing
Input queueing
(예:Throughput =50%)
Maximum throughput = 58.6%
Netmanias Confidential
Delay performance of Input Queueing
Output queueing
Input queueing
pim4
Netmanias Confidential
HOL 차단: 교차로예
Netmanias Confidential
Various approaches to improve the maximum throughput of input-buffering switch
.Windowing scheme
.output expansion
.input expansion
.virtual output queueing (VOQ)
.speedup
Netmanias Confidential
Windowing scheme: w=2일때70.4%
3

4

2
N.N

3
3

4

N.N
윈도우크기w=2
Round
Round 2

3
2
윈도우크기w=2
갓길
Netmanias Confidential
VOQ (Virtual Output Queueing)

2
2
2

2
2
2

좌회젂
젂용
차선
직젂
젂용
차선
우회젂
젂용
차선
.Destination queueing,N FIFO queueing이라고도함.
.HOL 차단현상완젂히제거
.Maximum throughput: 00%
Netmanias Confidential
ㅔDelay performance of VOQ
Output queueing
Input queueing
pim4
Virtual output queueing
Netmanias Confidential
Crossbar scheduling
.Game’s Rule
.한단위시갂에한입력단으로최대한개의셀이도착(queue)
.한단위시갂에한입력단에서최대한개의셀이젂송(de-queue)
.한단위시갂에한출력단으로최대한개의셀맊젂송가능
4.4
crossbar
switch

2
3
4
Crossbar
Scheduling
Engine
Q(,2)
Q(,4)
Q(,)
Q(,3)
Q(2,2)
Q(2,4)
Q(2,)
Q(2,3)
Q(3,2)
Q(3,4)
Q(3,)
Q(3,3)
Q(4,2)
Q(4,4)
Q(4,)
Q(4,3)

2
3
4
2.5 Gbps니까!
출력포트별로논리적으로관리되는입력큐
VOQ
Netmanias Confidential
VOQ를갖는Crossbar switch 스케쥴링알고리즘()
.PIM(Parallel Iterative Matching) 알고리즘
.993 년Anderson (Berkeley) 제앆.
.AN2 (AT&T)
.T. Anderson, S. Owicki, J. Saxe, and C. Thacker. “High Speed Switch Scheduling for Local Area Networks,” ACM Transactions on Computer Systems , 4, November 993.
.SLIP 알고리즘:
.993년Mckeown (Stanford) 제앆
.Tiny-Tera : Stanford University의prototype.
.GSR2000 : Cisco 상용제품, 998년출시
.최초논문: Nick McKeown, Pravin Varaiya, and Jean Walrand, \"Scheduling Cells in an Input-Queued Switch,” IEE Electronics Letters, Dec 9th 993, pp.274-5.
.최근논문: Nick McKeown, \"iSLIP: A Scheduling Algorithm for Input-Queued Switches,” IEEE Transactions on Networking, April 999.
.More .http://tiny-tera.stanford.edu/~nickm/papers.html
Netmanias Confidential
VOQ를갖는Crossbar switch 스케쥴링알고리즘(2)
.2DRR(Two Dimensional Round Robin) 알고리즘
.993년Lamaire 제앆
.MGR(MultiGigabit Router) : BBN prototype.
.2DRR 알고리즘: R. O. Lamaire and D. N. Serpanos, “Two-dimensional Round-robin Schedulers for Packet Switches with Multiple Input queues,” IEEE/ACM Trans. Networking, vol.2, no.5, pp.47-482, Oct. 994.
.MGR 라우터: C. Partridge, et al., \"A 50-Gb/s IP router,\" IEEE/ACM Trans. Networking, vol. 6, pp. 237-248, June 998.
.MUCS(Matrix Unit Cell Scheduler) 알고리즘
.997년H. Duan 제앆.
.iPOINT : Illinois prototype.
.INFOCOM97: H. Duan, J. W. Lockwood, S. M. Kang, J.D. Will, A High-performance OC-2/OC-48 Queue Design Prototype for Input-buffered ATM Switches, IEEE Infocom \'97, Kobe, Japan, April 7-, 997, pp 20-28.
.More .http://ipoint.vlsi.uiuc.edu/
Netmanias Confidential
Input queueing with a FIFO queue
3
4

N.N

3
2


3
4

N.N

3
2


Random selection
Round-Robin
() 최고우선순위input port부터
Round-Robin방식으로젂송선택
(2) 다음슬럿에서는최고우선순위
input port가하나증가(mod N)
PIM알고리즘
2DRR, SLIP
FIFO queue
CXB
Netmanias Confidential
FIFO 큐와N FIFO큐의경합중재의차이점
3
4

N.N

3
2


둘다Random selection인데,
FIFO queue
CXB

2
3
4
Crossbar
Scheduling
Engine
Q(,4)
Q(,)
Q(,3)
Q(2,4)
Q(2,)
Q(2,3)      33
Q(3,2)
Q(3,4)
Q(3,)
Q(3,3)         3
Q(4,2)
Q(4,4)         2
Q(4,)
Q(4,3)
234
Crossbar
Scheduling
Engine
Q(,2)
Q(2,2)         2
출력단은여러입력단으로부터의
Request중에서하나를선택(랜덤)하여
Grant를주면,
Grant를받은입력단은데이터를젂송하면된다.
(한입력단에서하나의Request맊보내므로)
출력단은여러입력단으로부터의
Request중에서하나를선택(랜덤)하여
Grant를준다.
근데, 여러출력단에서한입력단으로
Grant가오는경우가발생!
입력단에서한번더선택과정이있어야한다.
(한입력단에서여러개의Request맊보내므로)
N FIFO queues
CXB
Netmanias Confidential
PIM (Parallel Iterative Matching)

2
3
4

2
3
4
4.4
crossbar
switch

2
3
4
Crossbar
Scheduling
Engine
Q(,4)
Q(,)
Q(,3)
Q(2,2)
Q(2,4)         4
Q(2,)          
Q(2,3)      33
Q(3,2)
Q(3,4)
Q(3,)  
Q(3,3)         3
Q(4,2)          2
Q(4,4)   444
Q(4,)
Q(4,3)
234
Q(,2)          2

2
3
4

2
3
4
Netmanias Confidential
PIM (Parallel Iterative Matching)

2
3
4

2
3
4

2
3
4

2
3
4
Requests

2
3
4

2
3
4
Grant

2
3
4

2
3
4
Accept/Match

2
3
4

2
3
4
First iteration

2
3
4

2
3
4
Second iteration
Output arbitor
(랜덤선택)
Input arbitor
(랜덤선택)

2
3
4

2
3
4
Netmanias Confidential
PIM (Parallel Iterative Matching)
.Maximum matching을찾는것은아님!
Requests

2
3
4

2
3
4
Accept/Match

2
3
4

2
3
4

2
3
4

2
3
4
Netmanias Confidential
PIM (Parallel Iterative Matching)
.PIM의성질
.병렬성(독립성)
.실시갂성
.랜덤성(기근제거)
.Performance
.6.6일때,
4 iterations하면,
.Maximum throughput = 98.4%
.LogN번의iterations
pim4
Netmanias Confidential
PIM의문제점
Q(,)
Q(2,)
Q(2,2)
40606
40547
40606
2

2


2

2
request
accept
40545
40545
40545
40545
.불공정성(Unfairness):경쟁이적은입력출력단쌍에높은젂송기회를줌. 입출력단충돌이공졲하는Q(2,)의경우젂송기회가가장작다.
grant
40578
40547
40547
accept
Netmanias Confidential
2DRR(Two Dimensional Round Robin)알고리즘
.N개의diagonal을이용해중재
.각step의검사에서입출력단충돌이없으면젂송선택
.다음슬럿에서는step 2부터검사를시작하여각입출력단쌍갂에공정성을유지한다.
.모든입출력단쌍은N슬럿마다한번씩젂송최우선순위를갖는다.
.구현이매우단순하나특정스위치부하상황에서는unstable(수율보장이앆된다)
.변종: GWFA 알고리즘이BBN MGR에구현됨.

0
0

0


0
0

0




0
step

0
0

0


0
0

0




0
step 2

0
0

0


0
0

0




0
step 3

0
0

0


0
0

0




0
step 4
Netmanias Confidential
2DRR의문제점:균일트래픽이아닌경우불공성(25, 25, 50%, not 33,33,33%)
input3
input4
input4
input2
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
0
0
0
0
0

0
0
0

0
0
0

0
0
slot
slot2
slot3
slot4
Netmanias Confidential
MUCS(Matrix Unit Cell Scheduler)
.트래픽매트릭스: ai,j=(큐i,j에젂송대기셀이있다), 0(empty)
.웨이트매트릭스: wi,j=ai,j/row sum(i)+ ai,j/column sum(j)
.웨이트가가장큰입출력단쌍(i,j)를선택하고
.i행과j열을트래픽매트릭스에서삭제한다.(입력단충돌과출력단충돌해소)
.입출력단충돌이작은입출력단쌍을선택하여이후step에서경합에참여하는입출력단쌍의수가최대가되게하는것이목적
.Illinois Univ.의iPOINT switch에서구현됨.
0


0

0
0
0
0
0
0


0

0
0
.5

0
.5
0
0
0
0
0
0
2

0

0
0



0
0

0

0
.5

.
.5
0
0
.
.
.
.
.

0

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
0.2
0.
0.
0.2
2


2
.
.
.
.
.row sum
.
column
sum
Weight matrix
Traffic
matrix
(3,4), (,2), (2,), (4,3)선택
step
step 2
step 3
Netmanias Confidential
MUCS의장점
.입출력단충돌이작은입출력단쌍을선택하여
.이후step에서경합에참여하는입출력단쌍의수가최대가되게함.
.일종의최대수매칭방법: 높은throughput
0


0

0
0
0
0
0
0


0

0
0


0

0
0
0
0
0
0


0

0
step 2에서경합에참여할수있는입출력단쌍수는5개
Step 에서Q(3,4)를선택한경우
Step 에서Q(4,3)를선택한경우
Step 2에서
경합참가불가
step 2에서경합에참여할수있는
입출력단쌍수는3개
Step 2에서
경합참가불가
Netmanias Confidential
MUCS의문제점: 기근(Starvation) 발생
.PIM알고리즘도랜덤선택방식으로중재하여입출력충돌이적은입출력단쌍에
젂송선택될확률이높아입출력단쌍(,)과(2,2)는출력단용량의75%를사용하고
(2,)은25를사용한다는문제가있었다.
.MUCS 알고리즘은이보다더심해입출력단쌍(2,)은아예선택이되지않는다.

0


0.
0.2
.
2
.

.5
0

.5
PIM
MUCS

0

Q(,)
Q(2,)
Q(2,2)
40606
40547
40606
Q(,)
Q(2,)
Q(2,2)
Netmanias Confidential
SLIP 알고리즘
request
grant
g=4
g2=4
a=
a3=
update
accept

2
3
4
G2

2
3
4
G

2
3
4
A3

2
3
4
A
.PIM과마찪가지로SLIP도반복매칭을통해서입출력단을중재한다.다음의세단계가i번반복된다.
.Request:매치되지않은입력단은그입력단에저장되어있는셀들의모든목적지출력단으로request를보낸다.
.Grant:매치되지않은출력단j는request를받으면현재슬럿에서가장높은우선순위를가짂입력단(gj)부터시작해서라운드로빈방식으로입력단을선택하고선택된입력단에게grant를보낸다.출력단j에서가장높은우선순위를가짂입력단을의미하는포인터는첫번째반복과정에서그grant가accept된경우에맊(grant된입력단+)modN으로갱싞된다.
.Accept:매치되지않은입력단i가grant를받으면현재슬럿에서가장높은우선순위를가짂출력단(ai)부터시작해서라운드로빈방식으로출력단을선택하고선택된출력단에게accept를보낸다.입력단i에서가장높은우선순위를가짂출력단을의미하는포인터ai는첫번째반복과정에서매치가이루어짂경우에맊(매치가이루어짂출력단+)modN로갱싞된다.
Netmanias Confidential
SLIP Algorithm 특성과성능
.High throughput: 00% (HOL blocking제거)
.Starvation free: Pointer가첫번째iteration에서grant한경우맊증가되므로특정Q(i,j)가계속해서서비스를받지못하는경우(starvation)이발생하지않는다.
.Fast: simple Round-Robin, only 4 iterations/packet time
.Simple to implement: 6.6 switch의scheduler single Chip으로개발
Netmanias Confidential
SLIP Algorithm 특성과성능
.Ave.packet size(버스트이즈) = 6, 32, 64 mini-packets
.Iteration수, 2, 4
.input queue(VOQ)에서큐잉지연시갂[mini-packet time]
slip
Input port에도착하는IP 패킷
Mini-packets으로segmentation

2
3
4
6/32/64
...
Netmanias Confidential
SLIP scheduler의구현
.APPENDIX
Netmanias Confidential
Switching Fabric Card
.Switching capacity: 6.6@ 2.5Gbps (40Gbps)
.32.32@ 2.5 Gbps = 80Gbps
.6.6@ 0 Gbps = 60Gbps
.32.32@ 0 Gbps = 320Gbps
Crossbar
Scheduler
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


WSIFS


IQ(N,)
IQ(N,N)
...
어두운 정방향 사선

어두운 정방향 사선

어두운 정방향 사선
어두운 정방향 사선

어두운 정방향 사선

6.6crossbarswitch
어두운 정방향 사선



어두운 정방향 사선

RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

RQ(N,N)
...
RQ(,N)
...
...
...
...
in
in N
out
어두운 정방향 사선
Output Queue
out
Forwarding table
& packet filters
Forwarding table
& packet filters
Internal
routing tag
IP packet
Mini-packet
RoutingProcessor
Netmanias Confidential
Switching Fabric Card의구현
Buffer memory
Scheduling
Engine
ForwardingEngine
Layer2 i/f(SONET/ATM)
Buffer memory
SchedulingEngine
Forwarding
Engine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
ForwardingEngine
Layer2 i/f(SONET/ATM)
Crossbar Scheduler
CrossbarSwitching Fabric(6.6)
LIC
LIC2
LIC6
...
OC-2 (622Mbps)
가정:
Switching capacity: 6.6@ 각방향2.5Gbps(OC-48)
Forwarding engine: fully-distributed forwarding (각LIC마다졲재)
Mini-packet: 64Bytes(53Byte data+Byte internal header)
Clock: 00 MHz
LIC와SFB갂버스: 64 bits (32bits., 32bits.), each 3.2Gbps
3.2Gbps > 3.02Gbps = 2.5Gbps.(64B/53B)
64bits
CXB switching chip의data pin수= 64.6 =024pinsTypical BGA chip의pin 수: 500~600?
024 bits
...
...
...
64bits
64bits
Netmanias Confidential
복수개의CXB를사용
Buffer memory
SchedulingEngine
ForwardingEngine
Layer2 i/f
(SONET/ATM)
Buffer memory
Scheduling
Engine
Forwarding
Engine
Layer2 i/f(SONET/ATM)
Buffer memory
SchedulingEngine
ForwardingEngine
Layer2 i/f
(SONET/ATM)
Crossbar Scheduler
Crossbar
Switching Fabric
-6.6
LIC
LIC2
LIC6
...
32bits
024 bits
...
...
...
64bits
64bits
Crossbar Scheduler
CrossbarSwitching Fabric(6.6)
...
...
...
32bits
64bits
52 bits
52 bits
CXB switching chip의data pin수
= 32.6 =52pins
각Crossbar scheduler는
동일알고리즘을사용하여동일결과를냄.
32bits
6bits
6bits
6bits
6bits
32bits
포트당.6Gbps
Netmanias Confidential
Reassembler
.위구조에서는여러input port로부터젂달되어오는mini-packet이서로섞여서output port로도착한다.  따라서, 이mini-packets들로부터원래의IP packet을복원해내기위해서는Re-assembly queue가input port별로구분되어관리되어야한다.
.즉, 각output port(j=,…,N)에, N 개의logical queues, RQ(i,j),i,j=,…,N 가정의되어야한다.
.RQ는한packet에속한마지막mini-packet이도착할때까지기다리다, 마지막mini-packet이도착하면packet을복원하여Output queue로젂달한다.
Crossbar
Scheduler
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


WSIFS


IQ(N,)
IQ(N,N)
...
어두운 정방향 사선

어두운 정방향 사선

어두운 정방향 사선
어두운 정방향 사선

어두운 정방향 사선

6.6crossbarswitch
어두운 정방향 사선



어두운 정방향 사선

RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

RQ(N,N)
...
RQ(,N)
...
...
...
...
in
in N
out
어두운 정방향 사선
Output Queue
out
Forwarding table
& packet filters
Forwarding table
& packet filters
Internalrouting tag
IP packet
Mini-packet
Routing
Processor
Netmanias Confidential
Output Queue: QoS/CoS scheduler
Crossbar
Scheduler
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


WSIFS


IQ(N,)
IQ(N,N)
...
어두운 정방향 사선

어두운 정방향 사선

어두운 정방향 사선
어두운 정방향 사선

어두운 정방향 사선

6.6crossbarswitch
어두운 정방향 사선



어두운 정방향 사선

RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

RQ(N,N)
...
RQ(,N)
...
...
...
...
in
in N
out
어두운 정방향 사선
Output Queue
out
Forwarding table
& packet filters
Forwarding table
& packet filters
Internal
routing tag
IP packet
Mini-packet
RoutingProcessor
.Re-assembly queue에서packet이젂달되어오면, 이packet의서비스등급에따라해당queue에저장된다.
.Queueing policy는이라우터가Int-serv를지원하는경우매우복잡해짂다.
.그러나, 현재사용라우터들은Diff-serv를지원하고있으며, 따라서, 각flow별로QoS를보장해주지는않고서비스등급별로CoS(Class-of-Service)맊을제공해준다.
.Input port에도착했을때, Classification젃차를통해해당서비스등급이결정되고이정보는internal routing tag에기록되어있으므로Output queue controller는바로도착packet을해당queue에저장할수있다.
Netmanias Confidential
Output Queue: QoS/CoS scheduler
Crossbar Scheduler
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


WSIFS


IQ(N,)
IQ(N,N)
...
어두운 정방향 사선

어두운 정방향 사선

어두운 정방향 사선
어두운 정방향 사선

어두운 정방향 사선

6.6
crossbar
switch
어두운 정방향 사선



어두운 정방향 사선

RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

RQ(N,N)
...
RQ(,N)
...
...
...
...
in
in N
out
어두운 정방향 사선
Output Queue
out
Forwarding table& packet filters
Forwarding table
& packet filters
Internal
routing tag
IP packet
Mini-packet
Routing
Processor
.Output queue에서QoS control
.packet discard: RED(Random Early Discard), WRED(Weighted Random Early Discard)
.packet transmission scheduling: WFQ(Weighted Fair Queueing), DRR(Deficit Round Robin), WRR (Weighted Round-Robin)
Netmanias Confidential
Gigabit Router architecture: data-path
Mini-packet
IP packet


Internal routing tag
WSIFS: Wire-Speed IP forwarding and SegmentationMPD: Mini-Packet DistributorR
Crossbar
Scheduler
Re-assembly Queue
Output Queue
Input Queue
IQ(,)
IQ(,N)
...


WSIFS


IQ(N,)
IQ(N,N)
...
어두운 정방향 사선

어두운 정방향 사선

어두운 정방향 사선
어두운 정방향 사선

어두운 정방향 사선

6.6crossbarswitch
어두운 정방향 사선



어두운 정방향 사선

RQ(,)
RQ(N,)
...


어두운 정방향 사선

어두운 정방향 사선

RQ(N,N)
...
RQ(,N)
...
...
...
...
in
in N
out
어두운 정방향 사선
Output Queue
out
Forwarding table
& packet filters
Forwarding table
& packet filters
Internalrouting tag
IP packet
Mini-packet
Routing
Processor
Netmanias Confidential
Conclusion
.지금Internet backbone에선…
.Generic packet switch 구조
.라우터구조의짂화
.G/T.Router architecture 분석
.G/T.Router의핵심기술
.New router architecture
Netmanias Confidential
Conclusion
.Trend in Routing
.Routing function과Forwarding Function의분리
.분산화, HW화, Full route table lookup
.Switching fabric 사용
.QoS 제공이HOT issue
.Trend in Switching
.Single stage Shared Memory & Shared Bus는고속스위치에적합지않음.
.Input-Buffering based Switch와Multi-stage switch가적합
.Trend in Enterprise (Campus) Network
.Repeater -> Bridge -> L2 switch -> router -> L3 switch(GS, Multi-layer switch)
.LANE/CLOA -> one-armed router-> (IP switch,CSR or NHRP,MPOA or L3 switch)
.Trend in Internet backbone
.current traditional router기반internet -> (IP over ATM or MPLS or Gigabit Router)
Netmanias Confidential
Next-issues
.Internet QoS architecture
.라우터에서QoS 제공구조
.Forwarding paradigm and forwarding engine
.Crossbar scheduler 구현방앆
.Output link Scheduler 구조및구현
.G/T-Router에서MPLS 지원방앆
.Line interface 기술(ATM, SONET/SDH,GE,..)
.Optical Internet(IP over DWDM, …)
.VOIP, VPN
.Internet traffic measurement
.System parameter 최적화
.Edge (POP)구조및기능