Panagiotis Georgopoulos

Ben Mccarthy
email: b.mccarthy@comp.lancs.ac.uk

Christopher Edwards

A Collaborative AAA Architecture to Enable Secure Real-World Network Mobility

Keywords: Network Mobility, NEMO BS, AAA, RADIUS, Security

Mobile Networks are emerging in the real world in various scenarios, from networks in public transportation to personal networks in consumer electronics. The NEMO BS protocol provides constant network connectivity and reachability for the nodes of these Mobile Networks in a seamless manner despite their roaming. However, NEMO BS has yet to show its advantages in real world deployment because it lacks troublefree and secure network access for the whole network, and secure data transmission for the nodes it provides connectivity for. On the other hand, Access Networks provide connectivity for Mobile Networks, but currently lack a robust AAA service which would enable network mobility support in a fast, trouble-free, but also secure and authenticated manner. Our paper describes a collaborative Unified Architecture that satisfies the requirements of both Mobile Networks and Access Networks, and our evaluation proves its efficiency and applicability for real world deployment in today's Internet infrastructure.

Introduction

Mobile IP (both Version 4 [START_REF] Perkins | IP Mobility Support[END_REF] and Version 6 [START_REF] Johnson | Mobility Support for IPv6[END_REF]) is designed to support the mobility of individual mobile nodes, such as laptops, netbooks or smartphones that are roaming from one network to another, maintaining session continuity for their applications. However, there is a strong requirement nowadays to support the mobility of an entire group of devices (termed a Mobile Network (MN)) that usually moves as a whole, whereas its individual devices (termed as Mobile Network Nodes (MNNs)) remain relatively immobile in relation to one another. For example, networks in public transportation, such as in trains, buses, coaches and airplanes that offer connectivity to passengers' devices as they move can be considered as MNs, whilst the end-devices are MNNs. Another example of a MN is a PAN in a consumer electronics scenario, where connectivity for all the different devices a user may carry as he moves, is maintained by a lightweight personal mobile router. For example, a mountain rescuer may have such a PAN that could consist of a wireless IP camera, a PDA with a live mapping application, IP sensor devices on his body to monitor his health condition and a VoIP application for communication with fellow rescuers during a rescue mission.

The NEMO BS protocol [START_REF] Devarapalli | NEMO Basic Support Protocol[END_REF] is responsible for offering constant connectivity and seamless session continuity to the MNNs of a MN without them having to be aware of their mobility, even though the MN might change it point of attachment from one Access Network (AN) to another. However, for real-world deployment, in order for the MR to run NEMO BS and support the mobility of the network, it has to be able to obtain secure and authenticated access from an AN in a fast and trouble-free manner. In addition, in such wireless mobile scenarios secure transmission of data is paramount, both in the range of the wireless hotspot the MR offers, but also as packets travel beyond the MN to the Internet via the AN. Furthermore, the AN has to have an efficient and scalable AAA infrastructure in order to authenticate, authorize and account the MN's connectivity.

Building on our previous work [START_REF] Georgopoulos | Towards a Secure and Seamless Host Mobility for the real world[END_REF], this paper describes a Unified Architecture (UA) that combines the strengths of Network Mobility and AAA services to satisfy in a secure manner the requirements of both MNs and ANs. The rest of the paper is organized as follows. Section 2 discusses the motivation behind our research and Section 3 gives some background information on its cornerstones. Section 4 provides the design of our UA and Section 5 evaluates our approach qualitatively and quantitatively. Finally, Section 6 concludes this body of work and highlights its benefits.

Motivation

In order to describe the motivation behind this work, let us discuss a reallife example that reveals the current problems and explains the reasoning and motivation behind our research. Let us consider a scenario where a bus company decides to offer Internet connectivity to passengers that board its buses every day. In this scenario, as the bus does its every-day route through town, its MR is responsible to obtain Internet connectivity from various publically available AN's Access Points (APs) being sporadically located around town, and share it to the passengers' devices by projecting a wireless hotspot in the bus.

During this real-life scenario, the MN of the bus requires : 1. Seamless mobility and uninterrupted connectivity for all its MNNs, despite the fact that the MR has to change its IP address whilst roaming from one AN to another, thus causing the MNNs' applications sessions to break. 2. Quick, effortless and secure network access to each AN it connects to. The MR should avoid requiring to be configured with the different type of authentication credentials and protocols each AN it encounters require. 3. Dynamic trust establishment with the AP it roams to, to avoid being connected to available but deceitful APs that would try to sniff its authentication credentials and hack into the MNNs' transmitted packets. 4. Avoid revealing its identity to each AN it roams to for privacy purposes. 5. Secure data transmission both locally, in the vicinity of the hotspot it provides to its MNNS, but also globally, as its MNNs' data are transmitted from the MN to the Internet via the AN.

At the same time, AN providers have their own requirements to satisfy in order to provide connectivity for MNs. To be specific, ANs require :

1. Financial benefit for setting up and administering wireless networks possible scattered around a large area, for the MNs to connect to. 2. A robust and well configured service to Authenticate, Authorize and Account the MNs' connectivity in a practical and scalable manner. It is unrealistic to expect that each AN should know in advance each MR requesting network access on behalf of a MN. 3. Avoid compromising their security policies and disallow unauthorized access to their networks.

Background

This section introduces the cornerstones of this research work; NEMO BS, IPsec, Radius, TLS based authentication methods and wireless security protocols.

NEMO BS Protocol

The NEMO BS protocol [START_REF] Devarapalli | NEMO Basic Support Protocol[END_REF] grants session continuity to the nodes of a MN that is roaming across different ANs, changing its point of attachment to the Internet. NEMO BS takes advantage of the large IPv6 address pool that guarantees global reachability of every MNN and also, manages to keep the mobility of the network transparent to its MNNs, by removing completely the need for the MNNs to run any extra protocols themselves to support their mobility. According to NEMO BS, when a MR moves away from its Home Network (HN) and finds an AN to connect to, it sends a Binding Update (BU) to its Home Agent (HA) containing its new topologically correct IPv6 Care-of-Address (CoA), optionally along with one or more Mobile Network Prefixes (MNPs). These MNPs represent the networks that the MR serves and advertises to its MNNs in Router Advertisements, so that each MNN can configure an IPv6 address itself and be globally reachable. When the HA receives a valid BU from a MR, it updates its binding cache for that MR and its MNPs, and then acknowledges it with a Binding Acknowledgment (BA). From this moment a bidirectional tunnel between the HA and the MR is instantiated and the HA intercepts packets destined for all the MNPs that the MR has registered, and forwards them to the MR's CoA to ensure reception of packets by the MNNs.

IPsec

IPsec [START_REF] Kent | Security Architecture for the Internet Protocol[END_REF] is a protocol suite for establishing secure IP communications between peers (hosts or gateways) over an insecure network. IPsec uses a combination of protocols to provide mutual authentication, data confidentiality, data integrity, non-repudiation and anti-replay protection on a per packet basis without any regard to the communication path between parties. IPsec mainly uses three cryptographic protocols; IKE, AH and ESP. IKE is used to exchange cryptographic keys among peers, establish the Security Associations (SA) among them for inbound and outbound traffic per peer and negotiate all the cryptographic algorithms of the secure communication channel that IPsec will operate upon. AH and ESP are used in two different modes based on the requirements of the application scenario; transport mode, where protection is provided from the Transport layer and higher, and tunnel mode, where protection is provided for the whole packet. Use of IPsec is mandatory in mobility scenarios [START_REF] Arkko | Using IPsec to Protect Mobile IPv6 Signaling Between Mobile Nodes and Home Agents[END_REF], [START_REF] Devarapalli | NEMO Basic Support Protocol[END_REF] to avoid attacks such as man-in-the middle, passive wiretapping or impersonation. Our UA complies with the aforementioned references and uses ESP in transport mode to protect control traffic between the MR and the HA in both directions, and ESP in tunnel mode to protect all the application traffic the MNNs generate.

RADIUS AAA Protocol

The RADIUS AAA protocol [START_REF] Rigney | Remote Authentication Dial In User Service (RADIUS)[END_REF] is the most well known and widely deployed AAA protocol worldwide. Its functionality is built on the generic AAA framework defined in [START_REF] De Laat | Generic AAA architecture[END_REF] and mainly involves three entities; the supplicant (enddevice), the Network Access Server (NAS) and the AAA server.

The process of performing a AAA service for a wireless device using RADIUS is as follows. When a device requests network access it uses a Layer 2 protocol (such as PPP or EAP) to communicate with the NAS and, among other information, send to it its authentication credentials. The chosen authentication method (e.g. EAP-TLS, PEAP etc.) will define the number of packets that should be exchanged for the authentication of the client, in addition to the type and format of the authentication credentials (e.g. a hashed password, a certificate etc.). Since the NAS has no appropriate means to authenticate the supplicant itself, it will initially collect all the information the supplicant sends, then use its AAA client implementation to encapsulate it in appropriate AAA packets, and then encrypt those with a strong key it shares with the AAA server before finally sending them to the server. When the AAA server receives these packets, it authenticates the supplicant usually with the aid of other resources, such as local databases or a PKI. If authentication is successful, the RADIUS server tries to authorize the user by checking its authorization policies which are, usually, ISP specific. When the AAA server reaches a decision whether the user should be granted or denied access to the network, it replies using AAA packets to the NAS, which is then responsible for relaying the reply to the supplicant over Layer 2 frames. When this phase is completed, the user is granted (or denied) access with a defined authorization level and the AAA server starts collecting accounting information for the supplicant's network usage from the NAS using specific accounting messages, that update the AAA server at regular intervals.

TLS based Authentication methods

There are more than 40 EAP based authentication methods that can be used in conjunction with a AAA protocol, which will encapsulate the data found in EAP frames into appropriate AAA messages and transfer them from the NAS to the AAA server. However, EAP authentication methods that are based on a Transport Layer Security Tunnel, such as EAP-TLS, EAP-TTLS, PEAP or EAP-FAST and others, appeal more to our research not only because they are more secure, but also because they bring significant advantages to roaming users. During Phase 1 of such an authentication method, the AAA server is authenticated to the supplicant, and then a secure TLS tunnel is created between them, which is then used from the client to submit its own authentication credentials. This process allows the supplicant to maintain its privacy as it does not disclose its authentication credentials to an intermediate AP or AN, but ensures that these are only transmitted to the AAA server over the tunnel they have established. Of particular importance for our research are EAP-TLS [START_REF] Simon | The EAP-TLS Authentication Protocol[END_REF] and EAP-TTLS [START_REF] Funk | Extensible Authentication Protocol Tunneled Transport Layer Security (EAP-TTLSv0)[END_REF]. During Phase 2, where the AAA server authenticates the client, EAP-TLS uses a client's certificate, whereas EAP-TTLS uses a password in a hashed format, usually dictated by another authentication mechanism such as CHAP. One important advantage that EAP-TLS and EAP-TTLS offer to roaming users, is the ability to skip Phase 2 of the authentication process if the user has been authenticated with the AAA server before. This feature is called Session Resumption (SR) and when enabled, allows the AAA server to keep a unique cache entry for a client that gets successfully authenticated once. Therefore, when the client roams to another AP requesting the same authentication procedure to occur, after completion of Phase 1, the AAA server realizes that it has a cached entry for it from its previous authentication, and thus skips Phase 2, even in scenarios where the client has not been connected to that AP before.

Wireless Security

The need for securing wireless communication is much higher for publicly available APs. The WiFi Alliance has designed WPA and WPA2 protocols to secure wireless networks by offering packet encryption, message integrity, protection against replay attacks and authorized network access with the use of cryptographic algorithms. WPA and WPA2 protocols support two authentication modes; Personal mode and Enterprise mode. When Personal mode is used, wireless clients can connect to an AP using a preshared key (PSK), whereas when Enterprise mode is used authentication is performed with the aid of a AAA backend server. One of the big advantages of the Enterprise mode of WPA2, is that after successful authentication, the wireless client and the AAA server are the only owners of a Master Key, which they then use to derive a Pairwise Master Key (PMK). The PMK is then sent from the AAA server to the AP in a secure AAA message, and is being used as a symmetric key, bound to the session of the AP and the client. With the knowledge of the PMK, a subsequent 4-way handshake is performed between the AP and the wireless node, that derives, binds and verifies additional operational keys that are used in the future communication of the node with the AP. This significant feature of WPA2 in Enterprise mode means that session keys are being securely derived and negotiated in a way that security is enhanced and preconfiguration is avoided. One additional advantage that the aforementioned key derivation procedure brings to mobile users, is that when a roaming node connects to a WPA2 AP, it firstly checks if it has a collection of keys, called PMK Security Association (PMKSA), that can be used with this AP. If this information has been cached from a previous association, then there is no need for a full authentication procedure with a AAA server, but only the 4-way handshake has to be performed locally between the AP and wireless client. PMKSA caching significantly speeds up the authentication procedure of the roaming client without compromising the security of the network.

We devised a Unified Architecture (UA) with the goal of bridging the gap between Network Mobility and AAA services in a secure manner and satisfying the requirements of all the parties involved. Fig 1 illustrates our design where we overlay the AAA model in its extended form for roaming scenarios [START_REF] De Laat | Generic AAA architecture[END_REF] over NEMO BS's architecture and integrate these services in a unified way. According to our design, the MN's HN now consists of a HA and a AAA Home Server (AAAHS) that are responsible for providing the Mobility and AAA services for the MN respectively, whilst it is away from its HN. Conceptually, in our bus scenario the HN could be represented by servers located at the IT department of the company or provided by an ISP offering these services. The AN depicted in Fig. 1 represents any network that can provide Internet connectivity via wireless hotspots in the area the MN roams. The AN (also known as Foreign Network) consists of its own AAA Foreign Server (AAAFS) and many APs that act as NASs and are able to exchange packets with its AAAFS. Conceptually the AN could be a wireless ISP's town network or a municipal network, offering publicly available WiFi connectivity to MNs. It is important to emphasize that our UA does neither augment nor alter the design of the AN itself, making it ready to be used in the current Internet infrastructure. What our UA requires though, is that the AN has a Service Level Agreement (SLA) with the HN of a MN, through which, the AAAFS has the ability to relay the authentication process to the MN's AAAHS. The AAAHS has evidently more appropriate information to authenticat the MR, and permit it to offer connectivity to its MNNs. This collaborative design provides important benefits to all parties involved, as the AN does not require to know the MR in advance, neither has to have any preconfigured information about it or its MNNs. In addition, if a TLS based authentication method is being used the MR avoids revealing its identity and credentials to the AN itself, as its authentication data are forwarded securely to its HN over a tunnel, after the initial authentication of the AAAHS to the MR (as described in Subsection 3.4). If the authentication procedure of the MR is successful, this means that the AAAFS has a secure partnership with the AAAHS dictated by the SLA and confirmed from the knowledge of the shared secret they use to secure the AAA packets they exchange, thus, the MR can trust the AN's AP. ANs have financial incentives to get SLAs with HNs because these would allow them to serve MNs and in turn bill their HNs appropriately for the provided service. HNs are also interested in getting SLAs with as many ANs as possible, because the latter will serve their MNs when they are away from "home", inducing financial benefits to both network providers and bigger connectivity coverage for the end users. Our UA does not oblige the establishment of SLAs between all small-scale networks, on the contrary, it can easily facilitate a hierarchical model where only big ISPs have SLAs between each other and through them accommodate the smaller networks they provide connectivity for. This model is simply fitted into our UA by introducing a chain of intermediate AAA servers of the involved ISPs in the path between the AAAFS of the AN and the AAAHS of the HN. According to this model, each AAAFS will play the role of the proxy AAA server and forward packets to the next AAA server in the chain until data reaches an ISP that has a partnership with the MN's HN and is able to finally route these packets to the MN's AAAHS, leading to a model that scales for the real world.

Following the principle of NEMO BS, where the MR is responsible to provide the mobility service for all its MNNs without them having to run any mobility protocols themselves, our UA dictates that the MR should carry out the AAA service on behalf of the whole network as well in a similar fashion. Therefore, when the MR connects to an AN it is responsible to authenticate itself and the entire network to its AAAHS, and include the MNP of the network it is serving in its BU. This important process ensures that only MNNs of a certain IPv6 address pool are authenticated and authorized for Internet connectivity. However, since the MR is carrying the authentication procedure on behalf of the whole network, it should also perform local authentication of the MNNs connected to it, using for example WPA2/PSK or WPA2/EAP-TLS. In our bus scenario this can easily be facilitated if, for example, regular commuters subscribe to the Internet-onthe-bus service and obtain a username and password to authenticate to the bus' MR, or if non-regular commuters could get a WPA2/PSK scratch card when they purchase their ticket. The two distinct authentication procedures that our UA defines (MNNs authenticated to the MR and the MR authenticated to its AAAHS) provide important advantages in roaming scenarios. Although the MR might be changing its point of attachment from one AN to another roaming, the MNNs will experience only a slight connectivity disruption whilst the roaming take place, but none of them would have to reauthenticate after this roaming. In addition, the MNNs could join or leave the MN whenever they want, without having to "inform" a distant server about it, reducing significantly the number of packets that have to travel from the MN to the Internet (and vice versa) saving bandwidth and minimizing processing delays.

Let us now consider the phases a MR has to go through to provide Mobility, Security and AAA for all its locally authenticated MNNs, from the time it starts roaming to a new AN until it obtains full Internet connectivity. According to our design, in order for the MR to become fully operational it has to perform its Layer 2 handover, its AAA communication as required by RADIUS and the chosen TLS based authentication method, its mobility tasks as required by NEMO BS and its security related configuration, as required by the local AP it connects to and the use of IPsec for the traffic generated by or destined to its MNNs. These occur sequentially in the following three distinct phases :

• Phase 1 -Layer 2 Association : The MR performs the Layer 2 association with the AP of the AN it roams to.

• Phase 2 -Layer 2 & 3 AAA Communication and WiFi Security Configuration : During this phase the MR will request network access to the AN and will perform the AAA authentication with its HN using the RADIUS protocol (described in Subsection 3.3). Since the MR does not have an IP address yet, its communication with the AP occurs using EAP frames that carry all the required information using Layer 2 (MAC) addresses. The AAA client implementation of the AP, encapsulates the data from the EAP frames to IP AAA packets and sends them to its AAAFS. However, since we are using a TLS based EAP authentication method in our UA, the initial packets that are sent from the MN should eventually reach its AAAHS server in order to establish a TLS tunnel. In order to accomplish this, in these initial packets the MR presents its "identity" to the AP, essentially revealing only its domain name in the form of "anonymous@homenetwork.com" by complying to the standardized Network Access Identifier (NAI) (defined in [START_REF] Aboba | The Network Access Identifier[END_REF]), and thus enabling the local AAAFS to identify where it should forward all the AAA packets to. When the AAAFS relays the initial authentication data to the MN's AAAHS, the latter forms a tunnel with the MR and carries out the full authentication process by exchanging packets back and forth according to the chosen authentication method. When the authentication process finishes, the AAAHS replies to the AAAFS of the AN, and then the later according to the authentication reply either grants network access to the MN or denies it. Authorization usually occurs after authentication and is related to the actual policies the AN and HN have in place for roaming networks. When authentication and authorization finish, and if the MN has been granted access, the MN derives secure session keys for its communication with the AP as described in Subsection 3.5, and the AAAFS starts the accounting procedure for the MN and updates the AAAHS with billing records.

• Phase 3 -Layer 3 Mobility & IPsec configuration: If the MR succesfully finishes Phase 2 and is granted access, it obtains a topologically correct IPv6 address either by contacting a DHCPv6 server or using IPv6 autoconfiguration. When the MR has an IPv6 address, its first task is to perform its mobility binding with its HA and at the same time to configure its security associations and apply its IPsec policies. According to [START_REF] Devarapalli | NEMO Basic Support Protocol[END_REF] and [START_REF] Arkko | Using IPsec to Protect Mobile IPv6 Signaling Between Mobile Nodes and Home Agents[END_REF], at this moment, the MR ensures that its control traffic to and from its HA will be secured by ESP in transport mode and all the subsequent traffic to and from its MNNs will be secured by ESP in tunnel mode. Therefore, to successfully finish Phase 3 the MR sends its secured BU with its MNPs to the HA and waits for the matching BA that denotes a successful binding and a fully operational MN.

Evaluation

This section describes a qualitative and quantitative evaluation of our UA.

Qualitative

Our UA brings significant benefits to both the roaming MN and the AN that serves it. Section 2 discussed the motivation behind our research. Here we revisit the presented motivation and detail it in requirements that are satisfied with our approach. Our UA satisfies the following requirements of the MN :

1. Secure, unobtrusive and trouble-free network access : a) The MR does not need to be configured with different types of credentials each visiting AN requires, since the actual AAA procedure is performed with the MN's AAAHS and this configuration is known to the MR in advance.

b) The MR does not reveal its identity to each AN it is visiting, thus keeping its privacy whilst roaming. c) The MR is able to establish trust dynamically with the AN it roams to, by relaying this task to its HN during its authentication. If its AAAHS does not trust the AAAFS when the latter forwards packets to the former, the AAA process fails and thus the MR should not trust the AN's AP. 2. Secure transmission of data locally, in the range of the AP using WPA/WPA2, and globally, as data leave the AN and travel to the Internet using IPsec. 3. Constant and reliable connectivity is provided with the use of NEMO BS, which in conjunction with the trouble-free network access that is provided using the AAA service, leads to seamless and quick roaming for the MN.

Our UA satisfies the following requirements of the AN: 1. Authentication of the MR without requiring to have information about it in advance. The AN relays the authentication procedure to the MN's HN that has more appropriate information to authenticate the MR. 2. Authorization of the MR according to its local policies. 3. Accounting of the MR for its MNNs' network use in order to bill its HN for the provided service appropriately. 4. All the previous transactions are performed without compromising the security policies of the AN and by bringing financial benefits to it.

Quantitative

In order to evaluate the true applicability and efficiency of our approach, we carried out a series of performance Tests on our experimental testbed. In this Section we describe the hardware and software setup of our testbed, the tests that we carried out and finally, we analyze and discuss the results observed.

Hardware and Software Testbed Setup : To evaluate the capabilities and performance of our UA we configured the testbed illustrated in Fig. 2. Our testbed consists of three Access Networks (AN1, AN2 and AN3), a MN, and the HN the MN originates from. All PCs on our testbed have a P4 2.8GHz CPU, 2GB RAM and a 80 GB hard drive and run Ubuntu 10.04 LTS. Each AN consists of two PCs, one of them acting as an AP by projecting a 802.11g wireless hotspot using the ath5k driver and the hostapd deamon (version 0.7.3), and the other acting as the AN's AAAFS. The AP in AN1 is being configured in WPA1-Enterprise mode, whereas the APs in AN2 and AN3 are being configured in WPA2-Enterprise mode, allowing us to experiment with different wireless AP configurations. The HN consists also two PCs, one of them acting as a HA by running the NEMO BS protocol stack from [7] in HA configuration, and the other acting as a AAAHS. All the AAA Servers on our testbed run the FreeRadius AAA Server (version 2.1.10) and have a certificate which we issued by creating a Certificate Authority. Furthermore, each AAAFS has a shared secret with the AAAHS in order to communicate with it securely. All the equipment on our testbed is IPv6 enabled. AN1 and AN2 are connected with the HN over Ethernet using native IPv6 addresses, whereas AN3 is connected to the HN over the Internet using an IPv6 Tunneling service from HE Tunnel Broker [START_REF]Hurricane Eectric IPv6 Tunnel Broker[END_REF]. This IPv6 tunneling approach introduces approximately a 315 ms delay (630ms roundtrip) and routes all the packets from AN3 to HN and vice versa via the Internet, using global IPv6 addresses. This technique ensures that our tests are being carried out not only on a local basis, but also over a long distance route over the Internet that presents real-time traffic characteristics in the communication.

The MR used in our tests runs the NEMO BS stack from [7] being configured in MR mode, with the appropriate MNPs and IPsec configuration that matches the one at its HA. Finally, the MR runs WPA supplicant (version 0.7.3) to allow it to connect to the ANs' APs, and also runs the hostapd deamon to create a wireless hotspot for three MNNs (two laptops and an HTC Touch 2 PDA) and use its internal RADIUS functionality to authenticate the MNNs. In our first Testing Regime we use three different MNNs (two laptops and a PDA) and record how long it takes them to connect to the MR's AP (Layer 2 association), to authenticate to it, and finally, to obtain an IPv6 address and become fully operational (Table 1). The PDA and one laptop are using WPA2-PSK for authentication, whereas the other laptop is using EAP-TTLS. Our second Testing Regime, includes four different Tests where the MR authenticates to the ANs using EAP-TLS without SR (Test 1, Table 3), EAP-TLS with SR (Test 2, Table 4), EAP-TTLS without SR (Test 3, Table 5) and EAP-TTLS with SR (Test 4, Table 4) respectively. Each Test includes six roaming movements (Stages) of the MR from one AP to another which are presented in Fig. 2 in blue arrows, associating the MR with AP1, AP2, AP3, AP2, AP1 and finally AP3. We decided to perform the aforementioned roaming movements because they demonstrate realistic scenarios, where a MR might connect repeatedly to the same AP, or swap from one AP to another repeatedly.

Results : Table 1 details the results from our first Testing Regime where our three MNNs connected to the MR's AP, authenticated to it using WPA2-PSK or WPA2-EAP-TTLS and obtained an IPv6 address from the MNP the MR advertised. Although the results from this Testing Regime seem very reasonable, we could note the significant difference on the average time it takes for the PDA to do its WPA2-PSK authentication (3.690 sec.) compared to the laptop's average time (0.05 seconds), which is attributed to the big difference on the resources the two devices have. All three MNNs remained connected constantly to the MR and were transmitting packets while we were performing the roaming Tests of the second Testing Regime that follow. For our second Testing Regime we performed four different Tests where we roamed the MR of the MN, and essentially the whole MN from one AP to another in Six Stages using four different authentication methods and configuration. Before focusing on the results of the different authentication methods (noted as Phase 2 on Tables 3, 4, 5 and 6), we could note that Phase 1 results (Layer 2 Association) were similar in all Tests, varying from 0.883 seconds to 1.499 seconds. Similarly, Phase 3 results in all Tests, where the MR configures an IPv6 CoA, performs its binding registration with its HA and applies its IPsec policies for all the traffic the MNNs might send, did not present notable differences, varying from 1.372 seconds to 2.574 seconds.

Focusing on the results of the different authentication methods and the route they take place via, we concentrate on Phase 2 of each Test of the second Testing Regime. During Test 1 of our second Testing Regime, the MR used EAP-TLS without SR and roamed from one AN to another as presented in Fig. 2. As Table 3 illustrates, in Stage 1 the MR connected to AP1 and carried out its EAP-TLS authentication in approximately 0.780 seconds, which is remarkably low, since this phase requires 21 packets to be exchanged in total. As Table 2 presents, 7 out of the 21 packets are transmitted locally between the MR and the AP, and 14 are transmitted "globally", following a 3 hop route from the MR to the AN's AP, then to the AAAFS and finally, to the MR's AAAHS. In Stage 2 of Test 1, the MR roamed to the WPA2 AP2, and did its EAP-TLS authentication faster and transmitted two less local packets. Stage 3 consists of the MR being connected to AP3, where all the Phase 2 packets are routed to the AAAHS over the IPv6 tunnel to Hong Kong. The tunnel overhead increased Phase 2 timing to an average of 4.549 seconds, almost 10 times more compared to the previous Stages. This is an expected delay as 14 packets have now to travel over the IPv6 tunnel which adds significant delay. To further evaluate our UA we repeated Tests 1 and 2 using a different authentication method, namely EAP-TTLS, that uses a username/password pair to authenticate the MR instead of a certificate. As Table 5 shows Phase 2 timings in this Test, are in similar levels with Test 1 although the number of "global" packets now required for EAP-TTLS are now 16, compared to 14 in EAP-TLS (Table 2). During Stage 3 we observed an expected increase of the timing of Phase 2, as now more packets have to travel over the IPv6 Tunnel and thus the additional delay is reflected in the results. However, once again, Phase 2 timings of Stage 4 and Stage 6 are remarkably low, thanks to PMKSA caching which prohibits the need for any "global" packets exchange. Generally, the overall timings of this Test remain at the same level compared to Test 1, with slight differences due to the difference of the authentication method being used.

Finally, Test 4 repeats Test 3 with SR being enabled at the AAAHS. All the overall timings of this Test (Table 6) are decreased compared to those of Test 3 (Table 5), as both Session Resumption and PMKSA caching are triggered where applicable. In particular, Phase 2 timings for Stages 2, 3 and 5 are remarkably low (0.055 seconds, 1.888 seconds and 0.080 seconds respectively), because SR reduces the number of "global" packets that needed to be exchanged from 16 down to 6 (Table 2). Phase 2 of Stages 4 and 6 of this Test, required only 4 local packets to be exchanged, compared to 21 in total for a full EAP-TTLS authentication with a WPA2 AP, because again PMKSA caching was enabled and ensured that only the 4-way handshake was performed.

Conclusion

In this paper we presented a UA that combines the strengths of NEMO BS and AAA services in a secure way and satisfies the requirements of both MNs and ANs. Our UA enables roaming MNs to experience constant Internet connectivity with trouble-free but secure network access, and secure transmission of their data despite their frequent roaming. Using our UA, ANs are able to provide efficient and secure AAA services in a profitable fashion. Our qualitative evaluation discussed the merits of our approach and how it satisfies the requirements of all the parties involved. The results from our thorough quantitative evaluation with different authentication methods and configuration, demonstrated the performance and applicability of our approach for a real world deployment.

Fig. 1 .

 1 Fig. 1. The devised Unified Architecture

Fig. 2 .

 2 Fig. 2. Experimental TestbedTesting Sets : The aforementioned testbed setup allows testing to take place via APs that have different configuration and over different routes, mimicking how communication would take place in an actual deployment scenario where MNNs are connected to a MR, and the MR roams from one AN to another. Following the design of our UA, we perform two separate Testing Regimes, one to test the performance of local authentication of the MNNs to the MR, and another one to evaluate the roaming of the MR from one AN to another. We repeat each Test of each Testing Regime 50 times, with the focus on how quickly the MNNs or the MR become fully operational using different authentication methods and configuration over our UA.In our first Testing Regime we use three different MNNs (two laptops and a PDA) and record how long it takes them to connect to the MR's AP (Layer

Table 1 .

 1 Authenticating MNNs to the MR

		WPA2-PSK WPA2-PSK WPA2-EAP-TTLS
		PDA	LAPTOP	LAPTOP
	Layer 2 Assoc. (sec.)	2.585		2.300	3.670
	Layer 3 Auth. (sec.)	3.690		0.050	0.320
	Layer 3 IP (sec.)	3.167		2.390	1.905
	Total (sec.) :	9.442		4.740	5.895
	# of Packets TEST 1 TEST 2 TEST 3 TEST 4
	Stage 1	7/14	7/16	7/16	7/16
	Stage 2	5/14	5/6	5/16	5/6
	Stage 3	5/14	5/6	5/16	5/6
	Stage 4	4/0	4/0	4/0	4/0
	Stage 5	7/14	7/6	7/16	7/6
	Stage 6	4/0	4/0	4/0	4/0

Table 2 .

 2 Local/Global number of Packets for Phase 2

Table 3 .

 3 EAP-TLS Results without Session Resumption

	X Phases X X X Phase 1 (sec.) X X X Stages ST.1 ST.2 ST.3 ST.4 ST.5 ST.6 X X 1.208 1.045 1.084 0.959 0.969 1.016
	Phase 2 (sec.)	0.780 0.208 4.549 0.014 0.690 0.009
	Phase 3 (sec.)	1.630 1.585 2.310 1.833 2.123 2.433
	Total (sec.) :	3.618 2.838 7.943 2.806 3.782 3.458
	X Phases X X X Phase 1 (sec.) X X X Stages ST.1 ST.2 ST.3 ST.4 ST.5 ST.6 X X 1.110 0.985 0.883 1.068 0.887 1.081
	Phase 2 (sec.)	0.345 0.090 1.906 0.038 0.126 0.045
	Phase 3 (sec.)	1.770 1.372 1.754 1.686 2.487 2.290
	Total (sec.) :	3.225 2.447 4.543 2.792 3.500 3.416

Table 4 .

 4 EAP-TLS Results with Session Resumption

Table 5 .

 5 The results from Stage 4, where MR roams to AP2 where it has been connected before in Stage 2, illustrate the benefits of PMKSA caching of WPA2, as the MR does not perform a full EAP-TLS authentication, but just a 4-way handshake. With PMKSA caching Phase 2 of Stage 4 completes in just 0.014 seconds, almost 15 times less compared to Phase 2 of Stage 2, when the MR connected to AP2 for the first time. Stage 5 is where the MR connects to AP1, where, although it has been connected to before, as it is a WPA1 AP, it does not support PMKSA caching and thus records similar timings with Stage 1. Stage 6 further affirms the advantages of PMKSA caching, as Phase 2 completes only in 0.009 seconds despite the tunnel setup to Hong Kong, since only the local 4-way handshake is required. Due to PMKSA caching, 15 packets less are now being exchanged in Stage 6 compared to Stage 3, which also leads to a reduction of approximately 4.5 seconds of the total time it takes for Stage 6 to complete. Test 2 of the second Testing Regime, repeats Test 1 but with the SR feature enabled at the AAAH Server. During Phase 2 of Stage 2 of this Test, the AAAHS realized that the MR had performed a successful authentication with it some seconds ago (during Stage 1) and thus skips the second part of the EAP-TLS procedure. As Table 2 presents, only 6 packets compared to 14 are now exchanged in Phase 2, which completes in only 0.090 seconds (Table 4), more than twice as fast compared to Test 1 when SR was disabled. Further demonstration of the benefit of SR is illustrated in Stage 3, where again only 6 packets are transmitted over the tunnel, reducing the time of this Phase to just 1.906 seconds compared to 4.549 seconds of Test 1. Stages 4 and 6 present similar results with Test 1, as PMKSA caching takes effect. During Stage 5, SR affirms its advantages again, with a significant reduction of Phase 2 timing down to 0.126 seconds compared to 0.690 seconds of Stage 5 of Test 1, since PMKSA caching is not applicable as AP1 is in WPA configuration. Overall, it has to be noted that the SR feature, where applicable (Stages 2, 3 and 5) has demonstrated significant advantages and reduction in Phase 2 timings compared to Test 1 and further improved the overall timings of the Stages where PMKSA caching was not applicable. Phases Stages ST.1 ST.2 ST.3 ST.4 ST.5 ST.6 Phase 1 (sec.) 1.299 1.207 0.932 0.961 1.491 1.090 Phase 2 (sec.) 0.335 0.242 5.124 0.010 0.335 0.015 Phase 3 (sec.) 1.876 2.269 2.574 2.320 1.763 2.340 Total (sec.) : 3.510 3.718 8.630 3.291 3.589 3.445 EAP-TTLS Results without Session Resumption

	X	X	X X	X	X X	X X
	X Phases X X X Phase 1 (sec.) X X X Stages ST.1 ST.2 ST.3 ST.4 ST.5 ST.6 X X 1.603 2.086 0.977 0.981 0.845 1.090
	Phase 2 (sec.)	0.291 0.055 1.888 0.022 0.080 0.032
	Phase 3 (sec.)	1.554 1.544 2.660 2.222 2.620 2.220
	Total (sec.) :	3.448 3.685 5.525 3.225 3.545 3.342

Table 6 .

 6 EAP-TTLS Results with Session Resumption


Michel Hanna
email: mhanna@cs.pitt.edu

Sangyeun Cho
email: cho@cs.pitt.edu

Rami Melhem
email: melhem@cs.pitt.edu

A Novel Scalable IPv6 Lookup Scheme Using Compressed Pipelined Tries

Keywords: IPv6, Tries Compression, Next Generation Internet

An IP router has to match each incoming packet's IP destination address against all stored prefixes in its forwarding table. This task is increasingly more challenging as the routers have to: not only keep up with the ultra-high link speeds, but also be ready to switch to the 128-bit IPv6 address space while the number of prefixes grows quickly. Commercially, many routers employ Ternary Content Addressable Memory (TCAM) to facilitate fast IP lookup. However, TCAMs are power-eager, expensive, and not scalable. We advocate in this paper to keep the forwarding table in trie data structures that are accessed in a pipeline manner. Especially, we propose a new scalable IPv6 forwarding engine based on a multibit trie architecture that can achieve a throughput of 3.1 Tera bits per second.

Introduction

In the IP lookup (or forwarding) problem, the router has to match the destination address of every incoming packet against its forwarding table to determine the packet's next hop on its way to the final destination [START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. An entry in the forwarding table, or an IP prefix, is a binary string of a certain length followed by wild card (don't care) bits and an output port. The actual matching requires finding the LPM or the Longest Prefix Matching [START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF]. Recently the problem is getting more significance given the anticipated switch from the 32-bit IPv4 to the 128-bit IPv6 [START_REF] Arano | IPv4 Address Report[END_REF].

The main research streams that deal with the packet forwarding problem are algorithm-based and hardware-based. The most well-known algorithm-based solutions use the binary trie data structures [START_REF] Degermark | Small forwarding tables for fast routing lookups[END_REF][START_REF] Nilsson | IP-Address Lookup Using LC-Tries[END_REF][START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF][START_REF] Srinivasan | Fast Address Lookups Using Controlled Prefix Expansion[END_REF]. A trie is: "a tree-like data structure allowing the organization of prefixes on a digital basis by using the bits of prefixes to direct the branching" [START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF]. Figure 1(a) shows and example of an 8-bit address IP forwarding table, where a, b, • • • , m are symbols given to the prefixes for identification. In Figure 1(b) we show the equivalent binary trie of the IP forwarding table given in Figure 1(a). The main advantages of a triebased solution are that they provide simple time and space bounds. However, with the 128-bit IPv6 prefixes, both trie height and enumeration become an issue when the prefixes are stored inside the nodes.

Hardware-based packet forwarding engines are divided into many classes. The first class uses the Ternary Content Addressable Memory (TCAM), which has been the de facto standard for the packet forwarding application [START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF][START_REF] Shah | Fast Updating Algorithms for TCAMs[END_REF]. A TCAM is a fully-associative memory that can store 0, 1 and don't care bits. In a single clock cycle, a TCAM chip finds the longest prefix that matches the address of the incoming packet by searching all stored prefixes in parallel. Nevertheless, TCAM has serious deficiencies: high power consumption, poor scalability to long IPv6 prefixes and lower operating frequency compared to other memory technologies [START_REF] Baboescu | A Tree Based Router Search Engine Architecture with Single Port Memories[END_REF].

The class of hash-based hardware packet forwarding engines has become popular recently [START_REF] Hanna | CHAP: Enabling Efficient Hardware-based Multiple Hash Schemes for IP Lookup[END_REF][START_REF] Hanna | Progressive Hashing for Packet Processing Using Set Associative Memory[END_REF][START_REF] Hanna | Advanced Hashing Schemes for Packet Forwarding Using Set-Associative Memory Architectures[END_REF]. The hash-based engines are promising because they offer constant search time. However, inefficiency rises when two or more keys are mapped to the same bucket, which is called "collision". One way to handle collisions is by chaining, which makes each bucket of the the hash table a linked list. The most obvious downside of chaining is the unbounded memory access time [START_REF] Cormen | Introduction to Algorithms[END_REF].

The last class of hardware solutions is based on the multibit trie representation of the forwarding table. In a multibit trie, one or more bits are scanned in a fixed or variable strides to direct the branching of the children [START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF][START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. level one for branching. Each node in the multibit trie is either empty or stores a prefix. Multibit trie-based solutions have the following features: (1) they are easily mapped into a hardware pipeline [START_REF] Baboescu | A Tree Based Router Search Engine Architecture with Single Port Memories[END_REF], (2) they reduce the lookup time greatly compared to binary trie [START_REF] Kim | Efficient Construction of Pipelined Multibit-Trie Router-Tables[END_REF], and (3) they have low power consumption [START_REF] Kim | Efficient Construction of Pipelined Multibit-Trie Router-Tables[END_REF].

A multibit trie reduces the memory lookup time of a unibit trie by decreasing its height [START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF][START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. The prefixes in a multibit trie have to be expanded into a set of allowed lengths, through a process called "Controlled Prefix Expansion" (CPE) [START_REF] Srinivasan | Fast Address Lookups Using Controlled Prefix Expansion[END_REF]. Gupta et al. [START_REF] Gupta | Routing Lookups in Hardware at Memory Access Speeds[END_REF] propose a two-level hardware multibit trie, of 24 and 8 bits strides, for IPv4 packet forwarding. The scheme's lookup time is 2 memory cycles at the memory cost of at least 33MB. In general, the strides of a k-level multibit trie will be denoted by s = {s 1 , • • • , s k }, where s l is the number of bits used at level l.

Prefixes can be represented as address ranges that in some cases overlap [START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF]. The prefixes that do not overlap are "disjoint" prefixes [START_REF] Srinivasan | Fast Address Lookups Using Controlled Prefix Expansion[END_REF][START_REF] Wang | TCAM-Based Forwarding Engine with Minimum Independent Prefix Set (MIPS) for Fast Updating[END_REF]. If all prefixes in the forwarding table are disjoint, then we call them "independent" [START_REF] Wang | TCAM-Based Forwarding Engine with Minimum Independent Prefix Set (MIPS) for Fast Updating[END_REF]. The independent prefix sets are important because there is only one prefix that matches any incoming packet, thus avoiding the LPM calculation. Any prefix set is transformed into an independent set using a technique called leaf pushing [START_REF] Srinivasan | Fast Address Lookups Using Controlled Prefix Expansion[END_REF][START_REF] Wang | TCAM-Based Forwarding Engine with Minimum Independent Prefix Set (MIPS) for Fast Updating[END_REF]. Figure 2(b) shows the leaf-pushed multibit trie for Figure 1(a), where we copy (or push) the prefixes from the intermediate nodes to the leaves. For example, prefix 'a' in Figure 2 In this paper we propose a novel IP forwarding scheme based on the compressed multibit trie framework. The main goal is to avoid any prefix matching during the IP lookup process while achieving scalability to the 128-bit IPv6 and relaxing the memory requirement. We reduce the memory footprint by introducing a new two-phase inter-node compression algorithm. Unlike existing compression algorithms [START_REF] Degermark | Small forwarding tables for fast routing lookups[END_REF][START_REF] Nilsson | IP-Address Lookup Using LC-Tries[END_REF], we do not use any encoding or bitmaps that have adverse effects on the run time and usually complicate the incremental update process. By using an SRAM pipelined architecture, we estimate that our scheme can process 4.9 Giga packets per second and at the same time use less than 1.0 MB of memory for real IPv6 tables with 10.4K prefixes on average.

The rest of this paper is organized as follows: In Section 2 we describe our new IP forwarding scheme.The experimental results and evaluation are given in Section 3. Before we conclude and discuss the future work in Section 5, we talk about prior art in Section 4.

Our New Forwarding Scheme

An interesting observation is that the outcome of any IP lookup operation is an interface (or output port) number [START_REF] Chao | High Performance Switches and Routers[END_REF][START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. Real-life backbone routers contain a relatively small number of output ports (usually a few tens). Note that there is a difference between the next hop information, which is an IP address of a router, and the output port which is just a physical port. The routers assign many next hop addresses to one output port [START_REF] Chao | High Performance Switches and Routers[END_REF][START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. This means that the number of unique next hop information is greater than the number of output ports. Throughout this work we use both terms "next hop information" and "output port" interchangeably.

Furthermore, we find that the distribution of the prefixes among the output ports exhibits a certain skewness. Figure 3 plots the distribution of the prefixes against the output ports of tables "Eugene1" and "Equix2", chosen as representatives from the IPv6 tables listed in Table 1 (Section 3). We find that 94% of the prefixes share port 0 as for Eugene1, while 68% prefixes share port 0 for Equix2. Hence, if we replace the prefixes in a trie representation of the forwarding table with their associated port numbers, we have a great opportunity to reduce the total number of nodes in this trie using inter-node compression. However, before we describe our inter-node compression algorithm, we build a leaf-pushed, port-based multibit trie which is trimmed to remove redundant leaves.

Constructing The Uncompressed Multibit Trie

Figure 4 depicts our trie before applying our inter-node compression technique for the forwarding table in Figure 1(a). We call this trie "Trimmed, leaf-pushed, port-based multibit trie", since it is a leaf-pushed multibit trie in which we replace the prefixes with their output port numbers. If there is a subtrie that has the same port number for all of its leaves, then we trim it keeping in its place only one leaf with that port number. Herein, we will refer to this trie as "uncompressed" trie since our final trie is compressed (Section 2.2).

Each node at level l of a k-level multibit trie with strides s = {s 1 , • • • , s k } is a data structure of type "UTN", uncompressed trie node, which consists of a single dimension array, T [ ] of size 2 s l , plus a back pointer, bp, to the node that points to the current node. For example, the trie in Figure 4 has k = 3 levels and a set of strides s = {3, 2, 2}. Each row in T [ ] contains three variables: P L, a list of prefixes to keep the prefixes that are mapped to this row, port, to store the port of this row if all of its P L prefixes have the same port, and ptr to store a forward pointer to a next level U T N node (if any). The port field is set to -1 if the row is empty and to -2 if the row has a pointer to the next level. Note that the first column in each trie node in Figure 4 is almost identical to the leaf-pushed trie of Figure 2(b) after replacing the prefixes with their ports.

The idea is simple: construct a leaf-pushed multibit trie, then replace each prefix with a port number. During this process, sometimes the prefixes that are mapped to a certain row have identical port numbers. As an example, consider

(r = 1; r ≤ 2 s l ; r++){ /*each row*/ if (N.T [r].P L is empty), then { N.T [r].port = -1 } /*empty row*/ else { if (∀(p, q) ∈ N.T [r].P L, p.port == q.port), then { N.T [r].port = p.port } else { Let pL be the longest prefix in N.T [r].P L if (|pL| ≤ S l ), then{ N.T [r].port = pL.port } else { N.T [r].port = -2 /*mark as pointer*/ N.T [r].ptr = BuildNode(N.T [r].P L, l + 1, N.T [r]) } } } } return N }
row number 4 at level 1 of Figure 4 where both prefixes h and i map to port '0'. Thus, we do not need to expand the trie to the second level as shown in Figure 2(b); instead we just stop at level 1 for this row. Thus, we remove the second level leaf that originally stemmed from row 4 of level 1 and replace it with one port, 0, at this row. Hence, the number of nodes in the leaf-pushed trie in Figure 2(b) is reduced. The dotted arrows in Figure 4 represent back pointers, while the solid ones represent regular next level, forward, pointers. The back pointers are essential for our inter-node compression Algorithm 2 (Section 2.2).

Algorithm 1 has one function, BuildNode(), which takes three arguments: a list of prefixes SP , an integer l = level number, and a U T N current pointer, cp. We start by passing a prefix list SP = all the forwarding table prefixes, l = 1 and a N U LL pointer from the main() function to BuildN ode(), which returns a pointer, Root, to a Uncompressed trie. BuildN ode() begins by allocating a new U T N pointer, N , as a new node, records its back pointer and allocates its T [ ] as an array of size 2 s l . It expands any prefix from SP that has a length less than S l , a cumulative stride 1 , and adds only the unique prefixes to the original 1 A cumulative stride, S l = P l i=1 (si), is the number of bits that are used till trie level l.

prefix set SP . In other words, if any of the expanded prefixes already exist in SP , we delete the expanded prefix since it inherits its original prefix's length. Each prefix is mapped to a row r, where r = 1, • • • , 2 s l , in the N.T [ ] array and is stored in its associated prefix list, N.T [r].P L.

If no prefix is mapped to a certain row, r, we set N.T [r].port to -1 (indicating an empty row). When a packet is matched at this row we apply the default route [START_REF] Chao | High Performance Switches and Routers[END_REF]. If all the prefixes that are stored in r have the same output port number, we simply set N.T [r].port to that port. In case all the prefixes that are mapped to r have lengths less than or equal to S l , we choose the longest prefix, say p L , and set N.T [r].port to p L .port. Note that we define |p| to be the length of prefix p and |SP | to be the size of the set of prefixes SP . The recursion in Algorithm 1 occurs when there is at least one prefix that is mapped to r and has a length longer than S l . In this case, we set N.T

Inter-Node Compression

In Algorithm 2 we construct a compressed trie from our uncompressed trie generated by Algorithm 1. Our algorithm aims at removing redundancy in trie nodes by checking if there exist two or more nodes at the same level that have identical contents. Since our compression algorithm combines different nodes at the same level, we call it "inter-node" compression and the resulting compressed trie is called Inter-Node Compressed Trie (INCT).

We start with a copy of our uncompressed trie at level l = k and scan each pair of tables at this level to see if there exists identical tables. If we find two identical nodes, we delete one of them and use its back pointer to update the forward pointer of its parent node. We keep doing this at each level in a backward fashion till we stop at the root. Figure 5(a) represents the three-level trie of Figure 1(a), while Figures 5(b) and (c) depict how we perform compression on this trie level by level. We do not show the back pointers in Figures 5(b) and (c) as they are not needed after the compression. We define the "compression ratio" as the percentage of the total number of trie rows after the compression divided by the total number of trie rows before the compression. The compression ratio in this example is 28 48 = 58.3%. The main idea of Algorithm 2 is to make a copy, CRoot, from the uncompressed trie, Root, then compress it and move the compressed trie without the back pointers and the P L fields to the forwarding plane. For this purpose we need to define noP trs[ ] as a global array of counters of size k to keep track of how many nodes we have per trie level. In addition, we define an array of U T N pointers, P [ ][ ], that stores the pointers to all the nodes for each trie level, which is used only during the compression and is deleted afterwards.

Function CompressTrie() of Algorithm 2 does the actual compression. It starts from the uncompressed trie copy, CRoot, then builds the The function then sequentially scans the trie levels starting from the leaves to the root to see if there are two identical nodes, which is done by calling IdenticalNodes(). IdenticalN odes() is a function that takes two U T N node pointers as arguments and returns true if and only if the two nodes have exactly the same contents, otherwise, it returns f alse. If we find two identical nodes P [l][i] and P [l][j], we use the back pointer of P [l][j] to adjust its forward pointer to point to P [l][i] and delete P [l][j].

P [ ][ ] arrays. -2 -2 -1 -2 0 0 -2 -2 0 0 -2 -2 0 0 -1 2 0 0 -2 2 0 0 -2 -2 0 0 1 1 0 0 0 2 0 0 1 1 0 0 0 2 0 0 1 1 0 0 -1 2 CRoot -2 -2 -1 -2 0 0 -2 -2 0 0 -2 -2 0 0 -1 2 0 0 -2 2 0 0 -2 -2 0 0 0 2 0 0 1 1 0 0 -1 2

INCT Packet Lookup

In this section we show how to search for a port number in our INCT trie-based IP forwarding scheme. The great advantage is that we do not have to match the incoming packet address against any prefix. During a packet lookup, we split the destination address into k chunks and use each chunk as a row index, r l ,

Experimental Evaluation

To evaluate our proposed ideas we built a simulation environment written in C++ and employed 10 real IPv6 files dated June 2010 from the routing information service (RIS) project [START_REF]Routing Information Service[END_REF]. Table 1 lists the tables, along with their sizes and their number of unique next hops.

The memory requirement at each row of either uncompressed trie or INCT trie is encoded in 3 bytes, where we use 2 bytes for a pointer and one byte for a port number. An empty row is encrypted by resetting all 3 bytes to zeros. Two bytes per pointer gives us the ability to address 2 16 = 65.5K nodes per level.

INCT Evaluation

Selecting the Strides. A common practice in pipelined trie forwarding engines is to use a large initial stride [START_REF] Jiang | Multi-Terabit IP Lookup Using Parallel Bidirectional Pipelines[END_REF]. This is due to the fact that most prefixes in Internet IPv6 forwarding tables are of length 24 bits or longer [START_REF] Chao | High Performance Switches and Routers[END_REF][START_REF] Li | Comparative Studies of Address Lookup Algorithms for IPv6[END_REF][START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. In this work we follow this common practice. We aim to have a small number of trie levels to limit the delay incurred by any incoming packet.

First, we select the number of strides for two representative IPv6 forwarding tables to find the best number of strides. Figure 6 shows the result of varying the number of strides from 5 to 9 for the two files Linx1 and Eugene2. We find that the same trend that having a larger number of strides leads to lower memory utilization. However, since we want to reduce the packet's delay, we choose k = 7 as a tradeoff between memory utilization and delay. To select the actual strides' values, we use a simple brute-force heuristic to reduce the total memory requirements of our INCT trie as we mentioned before. In the following subsections we will use the notation "Xyz(m)" to distinguish different 7) vs. Uncompressed( 7) trie for tables given in Table 1.

trie schemes, where Xyz is the trie scheme name and m is the number of trie levels (i.e., height). For example, Uncompressed [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF], means our uncompressed trie with a height of 7.

INCT Performance. Figure 7 shows the memory requirements of both INCT [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF] and Uncompressed(7) trie for the IPv6 tables given in Table 1. The average total memory for INCT( 7) is 466KB, while Uncompressed(7) trie has an average of 1.0MB. This means that we achieve on average a compression ratio of 44.7% or an average space saving of 55.3%. The maximum memory requirement belongs to table Linx1, 857KB for INCT(7) and 2.0MB for Uncompressed(7) trie. The smallest space savings is 27% for table Equix2, while the largest space savings is 71% for table Wide1. The actual compression ratio varies from file to file due to the distribution of the output ports among the prefixes.

INCT vs. Other Compression Schemes for IPv6. Figure 8 shows the memory utilization of MIPS(57), binary INCT(57), Lulea(6) (which is almost like the Tree Bitmap scheme [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF]) and INCT [START_REF] Degermark | Small forwarding tables for fast routing lookups[END_REF]. Since IPv6 is currently using only 64 bits out of its 128 bits for actual address prefixes while the other 64 bits are to identify MAC address [START_REF] Li | Comparative Studies of Address Lookup Algorithms for IPv6[END_REF][START_REF] Li | Tree, Segment Table, and Route Bucket: A Multistage Algorithm for IPv6 Routing Table Lookup[END_REF], we assumed that Lulea IPv6 version would have 6 strides: {16, 16, 8, 8, 8, 8}. In addition, we assumed that MIPS's stride set would start by an initial stride of 8 bits then scans the rest of the 64 bits, 56 bits, one bit at a time. Note that INCT(6) is using the same strides as Lulea(6), while binary INCT(57) is using the same strides of MIPS(57). 1.

MIPS [START_REF] Wang | TCAM-Based Forwarding Engine with Minimum Independent Prefix Set (MIPS) for Fast Updating[END_REF] is the first technique that utilized the limited number of ports in Internet routers to lower the number of prefixes in a forwarding table. The main goal of MIPS is to store the prefix set inside a TCAM chip in any order. MIPS builds a leaf-pushed binary trie to obtain an independent set of prefixes, replacing prefixes by their next hops which are then replaced with their corresponding port numbers. As a secondary effect MIPS reduces the number of prefixes needed to be stored. Our trie construction algorithm, Algorithm 1, can be considered as a generalization of the MIPS trie construction algorithm for the multibit trie case. MIPS also keeps its trie in the control plane for update handling, while it retains a copy of the trie prefixes in the TCAM lookup engine. Our scheme does not store the prefixes in the fast forwarding data plane.

The performance is measured as the total memory used by each scheme. In general, MIPS(57)'s average total memory is 339KB, while Lulea(6)'s is 5.3MB. Binary INCT(57) is smaller by 88% than MIPS(57) on average and INCT( 6) is smaller by 67% than Lulea(6).

INCT Forwarding Engine Performance Estimation

In this section we estimate the actual processing rate of our INCT packet forwarding engine using the standard CACTI memory version 5.3 simulator [START_REF] Thoziyoor | CACTI 5.1: An Integrated Cache Timing, Power, and Area Model[END_REF]. We use the high performance 32nm SRAM technology with one read port and one write port.

The CACTI results of the pipelined architectures are shown in Figure 9. For each IPv6 table we choose the maximum size of each trie level to be simulated. This is why the total size of each trie is larger than its previously reported average size. The IPv6 INCT [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF] saves 60.6% of area and 41.5% of total read dynamic energy over the Uncompressed [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF]. The stage frequency equals the minimum of the maximum operating frequency among the trie levels, which is 4.9GHz. In other words, the pipelined architecture's estimated throughput is 4.9Giga packets per second, which means a loss of 8% comparing to Uncompressed [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF]. For minimum packet size of 80 bytes, the INCT(7) throughput is 4.9 × 80 × 8 = 3.1Tbps (Tera bit per second). The total delay incurred by a packet, which is the summation of the access time of each pipeline stage, is 2.9ns for INCT [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF].

Prior Art and Related Work

Many optimizations are suggested to reduce the binary trie lookup time like the path-compressed trie which benefits from the fact that a binary trie may have long sequences of single-child nodes, then skip scanning some bits to reduce average lookup time [START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF]. Crescenzi et al. [START_REF] Ruiz-Snchez | Survey and Taxonomy of IP Address Lookup Algorithms[END_REF] use full prefixes expansion to 32 bits, then construct two-level multibit tries of 16 bits each. Their compression technique is based on repetitions elimination of the LPM of each subtrie at the second level only. They use 1.2MB to store a lookup table of 40K prefixes. The Lulea algorithm [START_REF] Degermark | Small forwarding tables for fast routing lookups[END_REF] uses bitmap compression to eliminate data redundancy in three levels, leaf-pushed tries with fixed strides of s = {16, 8, 8} [START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. The scheme has two data structures per node: bitmap and an array that contains the compressed data. For each row of a trie, Lulea stores '1' in the bitmap if the current and previous row values are not equal while pushing the current value to the compressed data vector, otherwise it stores '0'. Though the Lulea scheme is reported to store 32K prefixes in 160KB memory, it has a lookup time between 4 and 12 memory cycles and suffers from very high update time [START_REF] Degermark | Small forwarding tables for fast routing lookups[END_REF][START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. Eatherton et al. [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF] modify the Lulea scheme to facilitate incremental updates while keeping the compression ratio as low as that of Lulea's. The authors propose two bitmaps per trie node, one for all internally stored prefixes and one for external pointers, which allow them to reduce the update time through avoiding leaf pushing [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF][START_REF] Varghese | Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices[END_REF]. They store a table of 41K prefixes in 450KB.

Note that all these schemes are "intra-node" compression schemes, while our scheme is an "inter-node" compression scheme. Though these preceding algorithms are devised mainly to handle the 32-bit IPv4, they could be utilized also for the 128-bit IPv6 address [START_REF] Li | Comparative Studies of Address Lookup Algorithms for IPv6[END_REF]. In fact, very few trie-based solutions are explicitly proposed to handle IPv6 [START_REF] Bando | Flashtrie: Hash-based Prefix-Compressed Trie for IP Route Lookup Beyond 100Gbps[END_REF][START_REF] Li | Tree, Segment Table, and Route Bucket: A Multistage Algorithm for IPv6 Routing Table Lookup[END_REF]. In [START_REF] Li | Tree, Segment Table, and Route Bucket: A Multistage Algorithm for IPv6 Routing Table Lookup[END_REF], the authors propose a hybrid data structure that combines binary tree (trie), a segment table and a route bucket (hash table) to store an average of 645 real IPv6 prefixes in 390KB with a worst case access latency of six memory cycles. The authors in [START_REF] Bando | Flashtrie: Hash-based Prefix-Compressed Trie for IP Route Lookup Beyond 100Gbps[END_REF] propose an architecture similar to [START_REF] Li | Tree, Segment Table, and Route Bucket: A Multistage Algorithm for IPv6 Routing Table Lookup[END_REF] in the sense that they use a hybrid data structure comprised of: direct lookup table, hash table and multibit trie that uses a new Tree bitmap compression. They achieve a throughput of 160Gbps utilizing on-chip SRAM and off-chip DRAM memory of 4.9MB for synthetic IPv6 tables.

Recently, many researchers are proposing trie-based advanced pipeline architectures [START_REF] Baboescu | A Tree Based Router Search Engine Architecture with Single Port Memories[END_REF][START_REF] Jiang | Multi-Terabit IP Lookup Using Parallel Bidirectional Pipelines[END_REF][START_REF] Kim | Efficient Construction of Pipelined Multibit-Trie Router-Tables[END_REF]. Their architecture optimizations are based on the minimization of the stage maximum memory, the minimization of the total memory, or the maximization of the throughput. Most of these solutions use dynamic programming algorithms to map trie nodes from to pipeline stages. The work in [START_REF] Kim | Efficient Construction of Pipelined Multibit-Trie Router-Tables[END_REF] constructs a pipelined architecture from fixed stride tries since variable stride tries are hard to implement and maintain. The authors provide dynamic programming algorithms to find the optimal multibit trie for a given table. The optimization in [START_REF] Kim | Efficient Construction of Pipelined Multibit-Trie Router-Tables[END_REF] is based on minimizing the maximum memory required for a single stage. The pipeline depth is between 2 and 8 stages and each stage uses between 60KB and 80KB for an IPv4 forwarding table of 100K prefixes.

Jiang and Prasanna [START_REF] Jiang | Multi-Terabit IP Lookup Using Parallel Bidirectional Pipelines[END_REF] addressed the same problem with a different strategy. Their architecture consists of multiple pipelines that have between 20 and 25 stages, each with 18KB of RAM. The main idea is to have more stages than the actual number of the trie levels for flexibility. They report an overall a throughput of 3.2Tbps, which is boosted by using an intelligent caching technique that allows processing 8 packets in parallel. The aforementioned schemes are orthogonal to our proposed scheme and can be used to balance memory distribution among stages before applying our compression.

Conclusions and Future Work

In this paper we introduced a novel packet forwarding scheme that uses multibit trie inter-node compression to reduce the total memory. We showed that our scheme has a better compression ratio than MIPS, Lulea and Tree bitmap compression schemes. In addition, most previously proposed schemes store their prefixes (or a pointer to them) in the forwarding trie, which we do not. On average, our pipelined INCT architecture, INCT [START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF], consumes 466KB and can achieve a throughput of 3.1Tbps.

We believe that this work could be applied to other packet processing domains such as packet classification and deep packet inspection. Also, we need to consider systematic methods to select the trie strides rather than just reducing the memory. Since our INCT utilizes an inter-node compression technique, we can apply other intra-node compression techniques (e.g., Lulea [START_REF] Degermark | Small forwarding tables for fast routing lookups[END_REF]) in addition to achieve more compression ratio. Furthermore, we can increase the throughput by using smart caching techniques that take into account the traffic characteristics as well as the trie shape.

Fig. 1 .

 1 Fig. 1. (a) An example of an 8-bit address space forwarding table. (b) Its binary trie representation.

Fig. 2 .

 2 Fig. 2. (a) Multibit trie for Figure 1(a) with strides {3, 2, 2}. (b) Its leaf-pushed trie.

  (a) is copied two times at level 2 and four times at level 3 in Figure 2(b).

Fig. 3 .

 3 Fig. 3. Prefixes distribution of Eugene1 and Eqix2 vs. output ports numbers.

Fig. 4 .

 4 Fig. 4. Uncompressed multibit trie for Figure 1(a).

Algorithm 1

 1 Uncompressed Multibit Trie Construction Algorithm. U T N * BuildNode(Prefixes List SP , int l, U T N * cp) { Define N = new U T N node with N.T [ ] = new array of size 2 s l and N.bp = cp /*record back pointer*/ for (each p ∈ SP ) do { if (|p| < S l ), then { Expand p to length S l , add the expanded prefixes to SP and remove any redundancy } } for (each p ∈ SP ) do { r = row index specified by bits S l-1 to S l of p N.T [r].P L = N.T [r].P L ∪ {p} } for

  [r].port to -2 (indicating that this row has a pointer to the next level) then we set N.T [r].ptr to a new instance of the BuildN ode() by passing the set of prefixes that are mapped to this row, N.T [r].P L, the next level number, l + 1, and the current table row pointer, N.T [r].

  Uncompressed trie of Figure 1(a). (b) Compressing the leaves. (c) Our compressed (INCT) trie.

Fig. 5 .

 5 Fig. 5. Compressed trie construction from its corresponding uncompressed trie.Algorithm 2The Inter-Node Compression Algorithm.CompressTrie(U T N *CRoot) { Construct the arrays noP trs[ ], P [ ][ ] for(l = k; l > 1; l --) { for(i = 1; i < (noP trs[l] -1); i + +) { for(j = i + 1; j < noP trs[l]; j + +) { if (IdenticalNodes(P [l][i], P [l][j]))then{ /*use P[l][j]'s back pointer to point to P [l][i]*/ * (P [l][j].bp).ptr = P [l][i] Delete node P [l][j] } } } } }

Fig. 6 .Fig. 7 .

 67 Fig. 6. Number of INCT trie levels vs. total memory (KB) for Linx2 and Eugene1.

Fig. 8 .

 8 Fig. 8. Memory (MB) of Lulea(6)/Tree Bitmap, INCT(6), MIPS(57) and Binary INCT(57) for tables in Table1.

Fig. 9 .

 9 Fig.9. The CACTI simulations for INCT[START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF] vs. Uncompressed[START_REF] Eatherton | Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates[END_REF].

Table 1 .

 1 Statistics of IPv6 tables on June 2010. H is the number of output ports. where l = 1, • • • , k, to a certain table. We start from the CRoot, and for each row r l ∈ CRoot.T [ ], if Root.T [r l ].port ≥ 0, we direct the packet to this port and we stop scanning the trie. However, if CRoot.T [r l ].port equals -1, then we apply the default route. Finally, if CRoot.T [r l ] .port equals -2, then we use CRoot.T [r l ].ptr to move to the next next level and recursively repeat the process until either find a port or an empty row.

	Table	Size H Table	Size H
	Equix1 3,180 9	Linx2 37,282 13
	Equix2 3,215 9 Quagga1 3,464 7
	Eugene1 3,211 16 Quagga2 3,299 4
	Eugene2 3,233 15 Wide1 5,412 2
	Linx1 36,366 13 Wide2 5,470 2

Acknowledgment

This work was supported in part by a NSF grant (CCF-0952273).