Open Source Routing Experinces

at

Uppsala University

Robert Olsson

Hans Wassen

Emil Pedersen

Uppsala Universitet

2008-04-16

Agenda
Open Soure Routers (OSR)

Robert Olsson &

Hans Wassen &

Emil Pedersen OSR experiences at Uppsala University (40)

Tom Johans OSR experiences at SLU (15)

Coffee break

Dag Berge OSR project at KTH, (15)

Olof Hagsand/Bengt Görden.

IIS 10g bifrost router project (25)

Björn Pehrson Possible use of OSR (15)

Discussion

10 years in production

Three major installations

UU core routers towards SUNET

UU Student Network 30.000 students

ftp.sunet.se

Testing, Verification
Development & Research

Started out as simple testing.

Curiosity, Open Source, Collaboration

Relatively freedom, the idea to use in own infrastructure. No need for external funding.

OS was intended for desktops.

Testing, Verification
Development & Research

No need for test network. We could test in own infrastructure. (Or SLU)

Problem oriented vs Project oriented

We could work on complicated issues

NAPI 3years

pktgen 2years

fib_trie 1year

TRASH 1year

Tested

device

Flexible netlab at Uppsala University

* Raw packet performance

* TCP

* Timing

* Variants

sink

device

linux

El cheapo-- High customable -- We write code :-)

Ethernet

|

|

Test generator

linux

Ethernet

Lab

Core Problems

heavy net load: system congestion collapse

High Interupt rates

Livelock and Cache locality effects

Interupts are just simply expensive

CPU

interupt driven: takes too long to drop bad packet

Bus (PCI)

Packets still being DMAed when system overloaded

Memory bandwidth

Continous allocs and frees to fill DMA rings

Unfairness in case of a hogger netdev

Overall Effect

Inelegant handling of heavy net loads

System collapse

Scalabiity affected

System and number of NICS

A single hogger netdev can bring the system to its knees and deny service to others

March 15 report on lkml

Thread: "How to optimize routing perfomance"

reported by Marten.Wikstron@framsfab.se

- Linux 2.4 peaks at 27Kpps

- Pentium Pro 200, 64MB RAM

A high level view of new system

P

pkts

Interupt area

Polling area

P packets to deliver to the stack (on the RX ring)

Horizontal line shows different netdevs with different input rates

Area under curve shows how many packets before next interrupt

Quota enforces fair share

Quota

Some GIGE experiments/NAPI

Ping through a idle router

Ping through a router

under a DoS attack 890 kpps

Vae

Very well behaved just an increase a couple of 100 microsec !!

Kernel support

NAPI kernel part was included in:

2.5.7 and back ported to 2.4.20

Current driver support:

e1000 Intel GIGE NIC's

tg3 BroadCom GIGE NIC's

dl2k D-Link GIGE NIC's

tulip (pending) 100 Mbs

Cache effect/Performance

Cache effect/Performance

Cache line 32 – 128 bytes

Optimize struct for cache and multiprocessors

usage

PIO even worse then cache miss

PIO READ stalls CPU

PIO WRITE can be posted

DMA copies of data into RAM

Does prefetch solve problems?

NAPI production in use: uu.se

Stockholm

Stockholm

PIII 933MHz

2.4.10poll/SMP

Full Internet routing

via EBGP/IBGP

DMZ

AS 2834

UU- 1

UU- 2

Interneral

UU-Net

L- uu1

L- uu2

Intel NIC's

Not or were blessed...

Some GIGE experiments

Pktgen sending test w. 11 GIGE interfaces

skb clone = 10.0 Gbit/s

skb alloc = 7.4 Gbit/s

SeverWorks X5DL8-GG Intel e1000

R&D

I

O

A

P

I

C

Eth1

Eth0

CPU 0

CPU 0

CPU 1

CPU 1

Parallelization

Serialization

Eth1 holds skb's

from different CPU's

Clearing TX-buff

releases cache bouncing

For user apps new scheduler

does affinty

But for packet forwarding....

eth0->eth1 CPU0 (we can set affinity eth1 -> CPU0)

But it would be nice to other CPU for forwarding too. :-)

TX ring

Forwarding performance

Fills a GIGE pipe -- starting from256byte pkts

Bifrost concept

Linux kernel collaboration

NAPI for network stack.

Performance testing, development of tools and testing techniques

Hardware validation, support from big vendors

Detect and cure problems in lab not in the network infrastructure.

Test deploy (Often in own network)

IP-login installation
at Uppsala University

Approx 1000 outlets

Other activities
informal linux agenda

Ericsson is willing to open patent for Linux

Jamal have the contacs via Ericsson Montreal

DaveM has discussions with Washington university about who is willing to grant another patent for use with Linux

Discussed LC-trie with Alexey Kuznetsov.

LC-trie investigations. Got GPL from authors.

fib_trie performance comparison

Preroute pathes to disable route hash

32/64 bit || sizeof(sk_buff)

Gcc 3.4 x86_64 vs i686 on same HW

ipv6 performance

How rDoS work on sparse routing table?

Trash datastucture

Interesting novel approc. Trie-Hash --> Trash

When extending the LC-trie

Paper with Stefan Nilsson/KTH

Expoits that keylen does not affect tree deepth

We lengthen the so key it can be better compressed.

Implemented in Linux forwarding patch as a

replacement to the route hash.

Trash datastucture

Can do full key lookup. src/dst/sport/dport/proto/if

etc and later socket.

For even ip6 with littele performnace degradation

Could be a candidate for the grand unified lookup

Full flow lookup can understand connections.

Free flow logging etc

New garbage collection (GC) possible. Active GC stated

AGC in the paper. Listen to TCP SYN, FIN and RST

Show to be performance winner.

Trash datastucture
Uppsala Universitet core router

Trash datastucture
Very flat(fast) trees

118.1

expgw.data

ultrouter6

ultrouter7

ultGC-gw

Switch HVC

knutpunkt

193.10.131.0/24

SLU2

SLU1

ultgw-2

ultgw-1

ultKC-gw

KC

GC

127.7

HVC

127.2

HVC

127.1

DC

130.

242.

127.54

127.53

127.57

127.58

127.62

127.61

127.69

127.70

127.45

127.46

127.86

UU

DC

DC

127.6

193.10.131

127.82

127.81

96.2

96.61

98.2

98.61

GigaSUNET

skara-gw

127.101

127.102

..233.33/24

34 Mb

88.34/30

88.33/30

DC

HVC

127.21

127.22

88.50/30

88.49/30

80.74/32

80.73/32

ultrouter8

127.8

HVC

127.17

127.18

DMZ UU/ITS

ultrouter9

127.9

HVC

127.13

127.14

127.85

2

3

3

1

1

3

3

3

3

2

1

1

1

1

.5

.4

/24

/24

e1

e1

e5

e5

e4

e4

e3

e3

e6

e6

e2

e9

e7

e8

e0

e0

e0

e2

e3

e0

e9

e10

e0

e2

e3

e1

e0

e1

e0

e2

e3

e10

e1

e3

SLU's nät

(inte hela)

118.1

expgw.data

ultrouter6

ultrouter7

ultGC-gw

Switch HVC

knutpunkt

193.10.131.0/24

SLU2

SLU1

ultgw-2

ultgw-1

ultKC-gw

KC

GC

127.7

HVC

127.2

HVC

127.1

DC

130.

242.

127.54

127.53

127.57

127.58

127.62

127.61

127.69

127.70

127.45

127.46

127.86

UU

DC

DC

127.6

193.10.131

127.82

127.81

96.2

96.61

98.2

98.61

GigaSUNET

skara-gw

127.101

127.102

..233.33/24

34 Mb

88.34/30

88.33/30

DC

HVC

127.21

127.22

88.50/30

88.49/30

80.74/32

80.73/32

ultrouter8

127.8

HVC

127.17

127.18

DMZ UU/ITS

ultrouter9

127.9

HVC

127.13

127.14

127.85

2

3

3

1

1

3

3

3

3

2

1

1

1

1

.5

.4

/24

/24

e1

e1

e5

e5

e4

e4

e3

e3

e6

e6

e2

e9

e7

e8

e0

e0

e0

e2

e3

e0

e9

e10

e0

e2

e3

e1

e0

e1

e0

e2

e3

e10

e1

e3

BGP policy routing

ISP:er (SUNET)

och Knupunkt.

118.1

expgw.data

ultrouter6

ultrouter7

ultGC-gw

Switch HVC

knutpunkt

193.10.131.0/24

SLU2

SLU1

ultgw-2

ultgw-1

ultKC-gw

KC

GC

127.7

HVC

127.2

HVC

127.1

DC

130.

242.

127.54

127.53

127.57

127.58

127.62

127.61

127.69

127.70

127.45

127.46

127.86

UU

DC

DC

127.6

193.10.131

127.82

127.81

96.2

96.61

98.2

98.61

GigaSUNET

skara-gw

127.101

127.102

..233.33/24

34 Mb

88.34/30

88.33/30

DC

HVC

127.21

127.22

88.50/30

88.49/30

80.74/32

80.73/32

ultrouter8

127.8

HVC

127.17

127.18

DMZ UU/ITS

ultrouter9

127.9

HVC

127.13

127.14

127.85

2

3

3

1

1

3

3

3

3

2

1

1

1

1

.5

.4

/24

/24

e1

e1

e5

e5

e4

e4

e3

e3

e6

e6

e2

e9

e7

e8

e0

e0

e0

e2

e3

e0

e9

e10

e0

e2

e3

e1

e0

e1

e0

e2

e3

e10

e1

e3

Redundant

inre kärna

118.1

expgw.data

ultrouter6

ultrouter7

ultGC-gw

Switch HVC

knutpunkt

193.10.131.0/24

SLU2

SLU1

ultgw-2

ultgw-1

ultKC-gw

KC

GC

127.7

HVC

127.2

HVC

127.1

DC

130.

242.

127.54

127.53

127.57

127.58

127.62

127.61

127.69

127.70

127.45

127.46

127.86

UU

DC

DC

127.6

193.10.131

127.82

127.81

96.2

96.61

98.2

98.61

GigaSUNET

skara-gw

127.101

127.102

..233.33/24

34 Mb

88.34/30

88.33/30

DC

HVC

127.21

127.22

88.50/30

88.49/30

80.74/32

80.73/32

ultrouter8

127.8

HVC

127.17

127.18

DMZ UU/ITS

ultrouter9

127.9

HVC

127.13

127.14

127.85

2

3

3

1

1

3

3

3

3

2

1

1

1

1

.5

.4

/24

/24

e1

e1

e5

e5

e4

e4

e3

e3

e6

e6

e2

e9

e7

e8

e0

e0

e0

e2

e3

e0

e9

e10

e0

e2

e3

e1

e0

e1

e0

e2

e3

e10

e1

e3

Redundant ansluting

av tunga servernät

via router discovery

118.1

expgw.data

ultrouter6

ultrouter7

ultGC-gw

Switch HVC

knutpunkt

193.10.131.0/24

SLU2

SLU1

ultgw-2

ultgw-1

ultKC-gw

KC

GC

127.7

HVC

127.2

HVC

127.1

DC

130.

242.

127.54

127.53

127.57

127.58

127.62

127.61

127.69

127.70

127.45

127.46

127.86

UU

DC

DC

127.6

193.10.131

127.82

127.81

96.2

96.61

98.2

98.61

GigaSUNET

skara-gw

127.101

127.102

..233.33/24

34 Mb

88.34/30

88.33/30

DC

HVC

127.21

127.22

88.50/30

88.49/30

80.74/32

80.73/32

ultrouter8

127.8

HVC

127.17

127.18

DMZ UU/ITS

ultrouter9

127.9

HVC

127.13

127.14

127.85

2

3

3

1

1

3

3

3

3

2

1

1

1

1

.5

.4

/24

/24

e1

e1

e5

e5

e4

e4

e3

e3

e6

e6

e2

e9

e7

e8

e0

e0

e0

e2

e3

e0

e9

e10

e0

e2

e3

e1

e0

e1

e0

e2

e3

e10

e1

e3

Almost all...

OpenSource

bifrost

zebra/quagga

A new network symbol has been seen...

The Penguin Has Landed

Robert Olsson

2006-11-10T10:06:09

Robert Olsson