IEICE TRANS. ELECTRON., VOL.E87–C, NO.3 MARCH 2004

1

PAPER

Special Issue on Internet Technology Series IV

Compound Data Oriented Processing in USAGI IPv6
Stack
Hideaki YOSHIFUJI†a) , Student Member, Kazunori MIYAZAWA††b) ,Masahide NAKAMURA†††c) , Yuji SEKIYA†d) , Nonmembers, Hiroshi ESAKI†e) ,and Jun MURAI††††f) , Members

SUMMARY
IPv6 has been attracting much attention as a
drastic countermeasure for severe shortage of addresses on theInternet. Linux, one of operating systems, also supports IPv6.
However, the quality of the protocol stack was not so good. In
this study, we worked out an architectural design for this basic software in Linux. Specifically, we introduce compound data
oriented processing in network stack, which simplifies data object management and relationship between object. We show thequantitative research shows that the quality of protocol stack of
IPv6 has been greatly improved.
key words: IPv6, Linux, Compound Data Oriented Processing

1.

Introduction

The Internet Protocol Version 4 (IPv4)[10] has been
the fundamental protocol in the Internet for long time.
However, several grave issues have arisen for ten years
since it was developed. For instance, severe shortageof address space was expected. Internet Protocol Version 6 (IPv6)[1], so called as “Next Generation Internet
Protocol (IPng)”, was designed to solve the problemsof the traditional Internet Protocol, Version 4.
The speciﬁcation of IPv6 has almost ﬁxed at the
IETF[13]. After the IPv6 technology being put on its
experimental stage, a lot of network appliance and software vendors are now supporting it, and commercial
service by Internet Service Providers is also available.
Now, IPv6 is reaching practical stage with productquality.
Linux IPv6 protocol stack is not really new; it has
been available since early Linux 2.1.x days in 1996.
However, once it was integrated into the mainline kerManuscript received January 1, 2002.
Manuscript revised January 1, 2003.
Final manuscript received January 1, 2004.
†
The authors are with the University of Tokyo, Tokyo,
Japan.
††
The author is with Yokogawa Electric Corporation,
Tokyo, Japan.
†††
The author is with Hitachi Communication Technologies, Ltd., Tokyo, Japan.
††††
The author is with Keio University, Kanagawa, Japan.
a) E-mail: hideaki@yoshifuji.orgb) E-mail: kazunori@miyazawa.orgc) E-mail: nakam@linux-ipv6.orgd) E-mail: sekiya@wide.ad.jpe) E-mail: hiroshi@wide.ad.jpf) E-mail: jun@wide.ad.jp

nel, it was not so actively developed while situation andspeciﬁcation were changed.
In 2000, USAGI Project[15] was established by
WIDE Project[16] and several hackers, who had leadLinux IPv6 Users JP joined the Project. The Projectstudies and develops on subject from kernel to user
space to provide high quality and up-to-date implementation to the world.
According to the research by the Project, we foundissues in Linux IPv6 stack. the architecture is too complex to keep them all right.
In this paper, we describes the new architectures
to make Linux conform well to speciﬁcations by IETF.
Speciﬁcally, we introduce compound data oriented processing scheme. This scheme is with simple, selfmanaged data object and compound of them. We describe how our high quality protocol stack is realized inthis scheme.
2.

Neighbor Discovery

Neighbor Discovery (ND) is one of core elements of
IPv6 and known that it consists of Router and Preﬁx
Discovery, Address Resolution and Neighbor Unreachability Detection and Redirect [9], [14]. They are essential to keep stable communication, and requires accurate timer and state management by various events on
network. For example, Address Resolution and Neighbor Unreachability Detection use Neighbor Cache Entry (NCE) in its concept and it is required to keep
the timer accurate to manage reachability of neighbors
properly.
In the previous implementation, NCE was managed by periodic polling timer and timer inside the entry. The reachability was managed in the following two
ways (Figure 1).
Periodic timer
Periodic timer (30 seconds) invokes managementtask, which checks reachability of every node. It
also clean-up entries in the table.
Entry-internal timer
Dynamic timer inside the entry invokes management task for itself in semi-reachable states. The
timeout depends on the state.

IEICE TRANS. ELECTRON., VOL.E87–C, NO.3 MARCH 2004

2
Neighbor Table
fib6_node

Neighbor Entry

Timer 1 Timer

Neighbor Entry

Timer 2

metrics
rt6_info

Neighbor Entry

Timer 3Neighbor Entry

Timer 4

fib6_node

fib6_node
RTN_RTINFO

fe80::dead:beef:cafe:babe
fe80::cafe:babe:dead:beefFig. 1

Fig. 3

Linux NDP Table with complex timer

Linux Routing Table::/0

Neighbor Table

rt6_info
fib6_node

Neighbor Entry

Timer 1
RTN_RTINFO

Neighbor Entry

Timer 2Neighbor Entry

Timer 3Neighbor Entry

Timer 4fe80::dead:beef:cafe:babe
fib6_nodeFig. 4
Fig. 2=&ipv6_null_entry

fib6_nodeLinux IPv6 Routing Table Structure

USAGI NDP Table with Dynamic Timers

Table 1 TAHI Conformance Test Result of NCE Management(PASS Ratio)
Linux 2.4.18
39%

USAGI 2.4
89%

KAME/FreeBSD 498%linked list which stores actual routing information, suchas nexthop (Figure 3), which is actually represented as
NCE. The elements in the linked list are chained innumerical order of metric. Linux IPv6 routing tablesupports equal-cost multiple paths.
3.1 Default Routers Management. Protocol requires accuracy of few seconds for allstates, the former results in inaccurate state management. Furthermore, state management was split andresource management was complex.
Therefore, we redesigned NCE management. We
split the management task including timers and mutual exclusion (locks), for state management (Figure2). Each entry has it own dynamic timer and lock forstate transition and it is responsible for its own statetransition; in short, each NCE is self-managed. On theother hand, periodic timer is not used for state management, and it is only used for garbage collection.
In this architecture, the tasks under the global lockare simpliﬁed. Resource managements for neighbors
including mutual exclusion are also greatly simpliﬁed.
As the results of NCE management in Table 1 shows, it
becomes possible to exchange messages correspondent
to the status of each NDP entry as deﬁned in the NDP
speciﬁcations.
3.

Routing Table

Linux IPv6 routing table, as known as “Forwarding
Information Base,” is constructed by Radix Tree[12].
A Radix Tree is built with internal nodes and leaves,which are nodes marked with RTN RTINFO. Every node
represents a bit position to test. And each leaf has a

Neighbor Discovery for IP Version 6 (IPv6) [9] introduces conceptual data structure as known as “Default Router List,” which holds information of “default
routers” advertised via Router Advertisement messages.
Linux does not have separate “Default Router
List” structure. It holds the default routers as a kindof routes to ::/0, instead of holding the information in
separate list.
However, as shown in Figure 4, Linux IPv6 protocol stack has a radix tree with ﬁxed node informationon the top and it points to ipv6 null entry. Therefore, when default route is added, the information is attached at the next of the rt6 info{} structure whichcontains ipv6 null entry. This causes default routenot to be referred.
In USAGI implementation, we replace theipv6 null entry with the new entry when adding a
new routing entry on the top level root of the tree
(Figure 5). When the last route is being deleted
from the the top level root of the tree, we re-insert
ipv6 null entry. This means, we actually treat the“default routes” which hold information regarding “Default Routers” as normal routes. And now, we cannaturally insert and remove the “default route” entries
properly to/from the routing table as we can do forYOSHIFUJI et al.: COMPOUND DATA ORIENTED PROCESSING IN LINUX IPV6 STACK

3
::/0

::/0

metrics

rt6_info

rt6_info

fib6_node

fib6_node

RTN_RTINFO=&ipv6_null_entry

RTN_RTINFO

fe80::dead:beef:cafe:babe
fib6_nodesame metrics

fib6_nodeFig. 7

Fig. 5USAGI IPv6 Routing Table Structure

metrics::/0
rt6_info
fib6_node
RTN_RTINFO

rt6_dflt_ptr

Fig. 6

Default Routers in Linuxother normal routes.
3.2 Router Precedence Management
As mentioned before, the default routers are stored
on the top level root node of the routing tree (Figure 6). It is called “Default Router Selection” topick one default router from the default router list.
In Default Router Selection, it does round-robin thedefault router list when it becomes unreachable. To
achieve this in Linux, the default router was pointed
by rt6 dflt pointer, which is guarded by the global
lock named rt6 dflt lock, and updated when routeris unreachable(Figure 6).
In this implementation, there were several issues.
Unfairness
rt6 dflt pointer is reset when routing is modiﬁed; this happens very often and routers are notequally selected.
Lack of Generic route selection
rt6 dflt pointer was only for the default routes;
The logic could not apply to generic route selections; we need to have generic way to select one
from multiple routes to support improved routerselection strategy such as “Default Router Preferences, More-Speciﬁc Routes, and Load Sharing” [2].
Metrics
Linux treated metrics in other way than normalroutes. Now we treat default routes like normalroutes, it is the time to eliminate special handlingof metrics of default routes.
To solve these issues, we introduced a new genericround-robin code for the routes with same metrics. We
do round-robin for routes with same metrics when a

New Method for Route Round-robinroute in that set is used (Figure 7). When a routeis looked up, use the ﬁrst entry which is in “probably
reachable” state in conjunction with NCE in the nexthop entry and relink it at the tail of the entries withsame metrics. In this way, the rt6 dflt pointer andrt6 dflt lock are eliminated. This logic can apply
to not only the default routes but also other genericroutes.
The “Router Selection” draft [2] also introduces
the concept of “preference” of routes. The routersadvertise 2-bit preferences of routes with Router Advertisement message, and hosts select more preferredrouters.
To implement this, we stores preference (2 bit) ofroutes into the ﬂags of the routing informations insteadof reﬂecting it to the metrics. This is to separate this
attribute from metrics to simplify other logic, for example to avoid ﬁxing up routing table when receiving
RA.
Finally, when a route is looked up, use the ﬁrst
entry with highest preference is in “probably reachable”
state in conjunction with NCE in the nexthop entry andrelink it at the tail of the entries with same metrics.
This is the way how we improved routing operation including default routes and router selections using
compound data structure oriented scheme in conjunction with NCE; objects are self-managed and data compound represents data relationship.
4.

IP Packet Transformer

The role of IP is to transfer datagrams from source
to destination. In traditional manner, it is enough tocarry it in as-is way. Today, however, keeping security
becomes important.
In order to support these requirements with minimum impact against users, IP layers are required to
be changed. Now, they not only transfer datagramsfrom one to another, but also ﬂexibly “transforms” itsformat. For example, IP layer will encrypt / decrypt
packets to keep security. It also appends authentication (or integrity check) data etc. These are all kindsof “transformations.”
4.1 Stackable Destination and XFRM
A new framework for IP packet processing has been
introduced into linux-2.5.x to implement IPsec, e.g.

IEICE TRANS. ELECTRON., VOL.E87–C, NO.3 MARCH 2004

4

Authentication Header[6] and Encapsulating Security
Payload[7]. It is called XFRM and “Stackable Destination.”
XFRM stands for transformer. Its fundamental
data structures are xfrm policy{} and xfrm state{}.
Each represents IPsec Policy (SP) and Security Association (SA) respectively. Thus, Security Policy
Database (SPD) consists of xfrm policy{}. Similarly,
Security Association Database (SAD) is consists ofxfrm state{}. An xfrm state{} is associated with
xfrm policy{} via xfrm tmpl{}, which represents template for packet transformation.
Stackable destination is the infrastructure forpacket transformation in the output path. It looks likea kind of linked list of dst{}, the protocol independent destination cache. This list is created temporalily
and cached according to the policy. dst{} has its own
output method output and it transforms the packet in
conjunction with xfrm state{}, which represents stateof transformer.
The netlink[11] infrastructure is used as fundamental user interface to maintain SAD and SPD. In addition to this native interface, the standardized PF KEY[8]interface, which is for SAD, is supported, and for SPD,PF KEY KAME [5] extension is supported.
4.2 AF Independent XFRM Infrastructure
Since core functionality of the XFRM engine is common
among address families (e.g. IPv6 or IPv4). AF independent XFRM infrastructure has been introduced.
Instance of AF speciﬁc XFRM engine is instantiated by registering AF speciﬁc information tables, e.g.
xfrm policy afinfo{} and xfrm state afinfo{}. tothe core XFRM engine. e.g. xfrm policy afinfo{}and xfrm state afinfo{}. Common variables are also
passed via the tables.
4.3 Packet Processing Details
In this section, we describe details of packet processing.
4.3.1 Output Path
The output process of IPsec fully uses this architecture.
The sequence of calling functions are xfrm lookup(),
xfrm tmpl resolve(), xfrm bundle create() anddst output().
First, xfrm lookup() looks up xfrm policy{} inSPD after routing resolution. At the moment the parameter dst{} in the stack points original dst{} structure. xfrm tmpl resolve() is called in xfrm lookup()
to resolve xfrm tmpl{} in xfrm policy{} which represents how the packet is processed and ﬁnds set of
xfrm state{} for it. This process corresponds to looking up IPsec SA or IPsec SA bundle matched with IPsec
policy.

Output Packet Processing

Lookup Routing Table

ip6_route_output

sk_buff

original_dst

Find xfrm_policy as IPsec policy

xfrm_lookup

xfrm_policy

xfrm_tmpl
xfrm_tmpl
xfrm_tmpl

Look up xfrm_state with comparing
with xfrm_tmpl in the policy

xfrm_tmpl_resolv

xfrm_tmpl
xfrm_tmpl
xfrm_state
Connect xfrm_state with the dst andcreate stackable destination

xfrm_bunele_create

sk_buff

dst

XXX_output
dst

XXX_output
original dst

Fig. 8

XXX_output

IPsec output process

Then, xfrm bundle create() creates the stackable destination. This corresponds to creating IPsec
SA (or SA bundle if multiple SA are needed).
Finally, dst output() is called after building up
the packet. Each output routine speciﬁed by the function pointer in the dst{} is called along with the chainof dst{} by popping up the dst{}. This pointer points
esp6 output() etc. The output function is able to use
xfrm state{} from dst{} pointer in sk buff{}. Andat last, the origial dst{}’s output function is called.
4.4 Input Path
The input process for IPsec is more simple than output.
As all extension header handlers and protocol handlers are registered with inet6 protos[] at its initialization phase, processing routines for AH and ESP are
also registered to inet6 protos[] at initiation.
When a packet is reached input hander, The kernel
parse it from the head, and call the hander according
to the registration table.
Each handler of IPsec protocol looks up xfrm state{}and processes it. If it succeeds, used xfrm state{}pointer is kept in sec path{} in sk buff{} which contains the packet.
Finally, xfrm policy check() is called at theentrance of upper layer process.
it compares
xfrm tmpl{} in xfrm policy{} and xfrm state{} kept
in sec path{} to determine if it is allowed to be delivered.
4.5 Test Results
On 24th April, 2003, Tom Lendacky reported to netdev
mailing list that Test results of Linux-2.5 IPsec are very
excellent(Table 2).

YOSHIFUJI et al.: COMPOUND DATA ORIENTED PROCESSING IN LINUX IPV6 STACK

5
Output Packet Processing

Input Packet Processing
Comparing xfrm_tmpl in xfrm_policy
and xfrm_state stored in sec_path[]

xfrm6_policy_check

Lookup Routing Table

ip6_route_output

sk_buff

xfrm_policy

xfrm_tmpl
xfrm_tmpl
xfrm_tmpl

sk_buffIP

AH

Find xfrm_policy as IPsec policy
Find xfrm_policy as MIP binding

xfrm_lookup

xfrm_tmpl
xfrm_tmpl
xfrm_state

sec_path

xfrm_policy

xfrm_tmpl
xfrm_tmpl
xfrm_tmpl

xfrm_policy

xfrm_tmpl
xfrm_tmpl
xfrm_tmpl

ESP

Look up xfrm_states with comparing
with xfrm_tmpls in the policies

xfrm_tmpl_resolv

xfrm_tmpl
xfrm_tmpl
xfrm_state

look up xfrm_state{} and process packet.
If succeeded, link it to skb->sec_path[]list.

xfrm6_rcv

xfrm_tmpl
xfrm_tmpl
xfrm_state
Connect xfrm_state with the dst andcreate stackable destination

xfrm_bunele_create

ip6_input_finish

original_dst

CompareCall protocol processing
functions by protocol number
sk_buff

IP Layer Process

Fig. 9dst

XXX_output
dst

XXX_output
dst

IPsec input process

XXX_output

dst

XXX_output

dst

We have tried to ﬁx the bugs in IPv6 IPsec fragmentation, and they should be ﬁxed for now.
Table 2%)

original dst

Fig. 10
SchemeXXX_output
XXX_output

Mobile IP using XFRM / Stackable Destination

Summary of TAHI Conformance Test (linux-2.5.58,
Test Series
ipsec
ipsec4
ipsec4-udp

Pass
95
98
96

Warn
2
2
4

• ESP, which ecrypts the packet after the destination
header for Home-Address option.
• AH, which generates authentication data forpacket and insert it after the destination header.
• Mobile-IP Dest2, which swaps Care-of Address andHome Address in the packet.

Fail
3
0
0

4.6 Future Evolution
The XFRM infrastructure and the Stackable Destination are the promising schemes. For example, Mobile
IPv6[4] is feasible.
Figure 10 shows the prototype diagram for Mobility support using XFRM / Stackable Destination infrastructure.
In this prototype, we introduce another set of policy for Mobile IP. This policy controlled by mobility
daemon in user space based on Binding Update. It
describes the type of transformation (e.g. appending
Home Address Option in the destination option headeretc.) and its corresponding binding data (i.e. Care-of
Address and Home Address).
The xfrm bundle create() compiles multiple
templates into the single stackable destination, taking account of the ﬂow of the process. Assuming
co-existence of AH, ESP and Mobile IP, AH requires
full packet. However, source address in the packet
should be home address. Thus, the Stakable Destination should be constructed as follows.
• Mobile-IP Dest1, which inserts Care-of Address
into the packet.
• Mobile-IP Rthdr, which inserts routing header(type 2) into the packet.

In this way, complex packet will be constructed in theseschemes.
5.

Conclusion

In this paper, we describes the architecture of USAGI
IPv6 networking stack. While USAGI software wasdeveloped based upon original Linux, we introduced
new compound data oriented architecture to various
area. This idea is to make some object simple andself-managed, and the compound of the object represents complexed processing. NCE in Neighbor Discovery manges itself. In routing area, Routing Entryis corresponded with the NCE, and the reachability is
managed by NCE itself. Preference of router is organized itself within the compound of the routing objects.
On the other hand, each IP packet transformer is represented by a object, and the chain of object called“stackable destinaiton” enables us ﬂexible transformation. This idea totally enables us to achieve naturaland high quality protocol stack.
Our product is widely and freely available underopen source license, and which can be used with various
kinds of Linux systems.
Finally, we list future items.
• Policy routing, which realizes routing not only by

IEICE TRANS. ELECTRON., VOL.E87–C, NO.3 MARCH 2004

6

destination address but also by the source address,
traﬃc class, etc. This also aﬀects the source address selection [3] algorithm.
• New security architecture for real end-to-end communication.
• More contribution to mainline kernel based onwide knowledge, as one of co-maintainer of Linuxkernel networking stuﬀ.
We will continue studying on architecture from basic to application. We continue providing high quality
implementation widely to deploy IPv6, and contributing IETF standardization process.

Kazunori MIYAZAWA
He joined
Yokogawa Electric Corporation.
Hejoined USAGI Project since 2000.

Masahide NAKAMURA
He joined
Hitachi Corporation. He joined USAGI
Project since 2002.

References[1] S. Deering and R. Hinden. Internet Protocol, Version 6(IPv6) Specification. RFC2460, Devember 1998.
[2] R. Drave and R. Hinden. Default router preferences, morespecific routes, and load sharing. Work in Progress, June
2002.
[3] R. Draves. Default Address Selection for Internet Protocol
version 6 (IPv6). RFC3484, February 2003.
[4] D. Johnson, C. Perkins, and J. Arkko. Mobility Support in
IPv6. Work in Progress, June 2003.
[5] KAME Project. KAME Project Web Page. http://www.
kame.net.
[6] S. Kent and R. Atkinson. IP Authentication Header.
RFC2402, November 1998.
[7] S. Kent and R. Atkinson. IP Encapsulating Security Payload (ESP). RFC2406, November 1998.
[8] D. McDonald, C. Metz, and B. Phan. PF KEY Key Management API, Version 2. RFC2367, July 1998.
[9] T. Narten, E. Nordmark, and W. Simpson. Neighbor Discovery for IP Version 6 (IPv6). RFC2461, December 1998.
[10] J. Postel. Internet Protocol. STD0005, September 1981.
[11] J. H. Salim, H. Khosravim, A. Kleen, and A. Kuznetsov.
Netlink as an IP Services Protocol, December 2002.
[12] Keith Sklower. A tree-based packet routing table for berkeley unix. In USENIX Winter, pages 93–104, 1991.
[13] The Internet Society. Internet Engineering Task Force.
http://www.ietf.org.
[14] S. Thomson and T. Narten. IPv6 Stateless Address Autoconfiguration. RFC2462, December 1998.
[15] USAGI Project. USAGI Project Web Page. http://www.linuxipv6.org.
[16] WIDE Project. WIDE Project Web Page. http://www.wide.
ad.jp.

Hideaki YOSHIFUJI
was born inTokyo, Japan. He received the B.Eng.,
and M. of Information Sciences from Tohoku University, Sendai, Japan, in 1999
and 2001, respectively. He works for USAGI Project as core member since its establishment in 2000. Now he is aiming forPh.D. in the University of Tokyo. He is
one of Linux co-maintainers of networking
area, since 2003.

Yuji SEKIYA
received B. from Kyoto University, received M. from Keio
University. The University of Tokyo. Heworks for USAGI Project as core member
since its establishment.

Hiroshi ESAKIHe received the B.E.
and M.E. degrees from Kyushu University, Fukuoka, Japan, in 1985 and 1987,
respectively. And, he received Ph.D from
University of Tokyo, Japan, in 1998. In
1987, he joined Research and Development Center, Toshiba Corporation, where
he engaged in the research of ATM systems. From 1998, he works for Universityof Tokyo as an associate professor, andworks for WIDE project as a board member. He has been at Bellcore in New Jersey (USA) as a residential
researcher from 1990 to 1991, and has engaged in the researchon high-speed computer communications. From 1994 to 1996, hehas been at CTR (Center for Telecommunications Research) of
Columbia University in New York (USA) as a visiting scholar.
He is currently interested in a high-speed Internet architecture,including MPLS technology, a mobile computing, and IPv6.

Jun MURAI
Born in March 1955
in Tokyo. Graduated Keio University in
1979, Department of Mathematics, Faculty of Science and Technology, MS for
Computer Science from Keio University
in 1981, Received Ph.D in Computer Science from Keio University in 1987.
Associate Professor, Faculty of Environmental Information, Keio
University; Adjunct Professor at Institute of Advanced Stud-YOSHIFUJI et al.: COMPOUND DATA ORIENTED PROCESSING IN LINUX IPV6 STACK

7

ies, United Nations University; Instructor at Tokyo Universityof Art and Music; President of Japan Network Information Centre (JPNIC). General chair person of WIDE Project, a Internet
research consortium in Japan. Vice chair person of Internet Society, Japanese chapter; Vice president of Internet Association,
Japan.