Xiuqiang He
email: hexiuqiang@huawei.com

Patrick P C Lee
email: pclee@cse.cuhk.edu.hk

Lujia Pan
email: panlujia@huawei.com

Cheng He
email: hecheng@huawei.com

John C S Lui

A Panoramic View of 3G Data/Control-Plane Traffic: Mobile Device Perspective

Keywords: mobile device traffic, data/control-plane, 3G networks, measurement

Users can access the Internet via 3G/4G cellular data networks using various types of user devices (e.g., smartphones, tablets, datacards). We conduct a detailed measurement study on the impact of different device types on the data/control-plane performance of a commercial, city-wide 3G cellular data network in China. We present a methodology that correlates different data/controlplane datasets collected at different points in the network core, and identify more than 60K devices of different types per day on average. For the devices we identify, we investigate how their commonly used Internet applications and internal heartbeat mechanisms lead to distinct data/control-plane behaviors. For example, we observe that datacard devices contribute a large volume of IP traffic in the data plane, while smartphones introduce significant resource overhead in the signaling control plane. Our measurement study provides insights for network operators to strategize pricing and resource allocation for the data/control planes of their cellular data networks with regard to the market penetrations of various device types.

Introduction

With the wide deployment of 3G/4G wide-area cellular data networks, we have witnessed the tremendous growth of mobile Internet access worldwide. There are many types of devices that enable mobile Internet access, such as smartphones, tablet computers, or datacards attached to laptops/PCs. There have been studies (e.g., [START_REF]Cisco. Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update[END_REF]) in forecasting the explosive growth of mobile data traffic from these devices. Compared to traditional wireline networks, cellular networks not only have relatively limited data-plane link capacity, but also have higher control-plane overhead that increases the loading of the network core [START_REF] Lee | On the detection of signaling DoS attacks on 3G/WiMax wireless networks[END_REF] and power consumption of mobile devices [START_REF] Qian | Characterizing Radio Resource Allocation for 3G Networks[END_REF]. From the perspectives of network operators, it is necessary to understand how the traffic patterns of different device types influence the performance of cellular data networks in both data and control planes. Understanding this influence can shed light on how to provision network resources, and if necessary, how to provide differentiated pricing or priority services across different device types or applications.

In this paper, we conduct an in-depth measurement study on the impact of different device types on the data/control-plane performance of a commercial 3G UMTS network deployed in a metropolitan city in China. We analyze several large-scale datasets, including IP packets with complete payload, UMTS-compliant signaling messages, and radio resource control (RRC) logs. We identify more than 60K devices of different types per day on average, as well as different IP applications. The extensive scales of our datasets allow us to conduct comprehensive analysis. In summary, the contributions of this paper are two-fold:

-We first present a methodology that correlates all these datasets, so that we can study the interactions of data and control traffic of each device type. We also characterize the IP applications commonly used by different device types. Note that the formats of our datasets follow the standard 3G specifications. Thus, our methodology is also applicable for general 3G networks, and will be useful for network operators of interest to carry out network planning by collecting the same datasets within their own managed networks. -We conduct an extensive measurement study mainly based on a 24-hour span of data/control-plane traces. We make the following observations. Even when there are only 7.5% of datacard devices, they contribute disproportionately about 46% of IP data traffic; for smartphone or tablet devices, they contribute less data traffic than datacard devices, but consume significantly high radio resource usage due to the frequent RRC connection setups/releases. Furthermore, we identify that iPhone/iPad devices have some internal heartbeat mechanisms that trigger a substantial number of RRC connection setups/releases, even though they generate minimal data traffic.

Our study shows the importance of how mobile devices interact with the control plane and what kind of behavior can be expected.

The remainder of the paper proceeds as follows. Section 2 reviews related work on 3G traffic measurement. Section 3 describes how we correlate different datasets collected at different points of a 3G network. Section 4 presents our findings from the datasets. Finally, Section 5 summarizes the lessons learned from our study.

Related Work

There have been measurement studies focusing on in-network data traffic collected inside 3G networks. Kilpi and Lassila [START_REF] Kilpi | Micro-and macroscopic analysis of RTT variability in GPRS and UMTS networks[END_REF] analyze the round-trip times of TCP flow data collected at a GPRS/UMTS network. Ridoux et al. [START_REF] Ridoux | Seeing the difference in IP traffic: wireless versus wireline[END_REF] collect data from a CDMA2000 network, and compare the similarities and differences with wireline data traffic. The DARWIN+ group [START_REF] Darwin | [END_REF] collects IP packets at a GPRS/UMTS network, and analyzes various issues such as TCP performance [START_REF] Ricciato | Bottleneck detection in UMTS via TCP passive monitoring: a real case[END_REF] and traffic anomalies [START_REF] D'alconzo | A Distribution-Based Approach to Anomaly Detection for 3G Mobile Networks[END_REF]. The above studies mainly analyze the data-plane performance of 3G networks.

Some recent studies analyze the control-plane performance of 3G networks. Lee et al. [START_REF] Lee | On the detection of signaling DoS attacks on 3G/WiMax wireless networks[END_REF] study the signaling overhead from the security perspective. They show that if an attacker generates data traffic following specific patterns, then a small amount of data traffic can sufficiently trigger heavy signaling overhead in the network core. On the other hand, they only analyze synthetic traces. Qian et al. [START_REF] Qian | Characterizing Radio Resource Allocation for 3G Networks[END_REF] infer and analyze the RRC state transitions of user sessions using data-plane traces, and mainly focus on power consumptions of mobiles. Paul et al. [START_REF] Paul | Understanding Traffic Dynamics in Cellular Data Networks[END_REF] collect data packet headers and various signaling messages in a national 3G network, and analyze their temporal and spatial variations. Our work differs from [START_REF] Paul | Understanding Traffic Dynamics in Cellular Data Networks[END_REF] in two aspects. First, our work focuses on distinguishing different device types and analyzing each of their data/control-plane performance. Also, our datasets contain full IP payload information that enables us to accurately identify more user applications and infer their impact to the network.

Several studies analyze the data traffic behavior of different types of handheld devices. Maier et al. [START_REF] Maier | A First Look at Mobile Hand-held Device Traffic[END_REF] analyze the mobile data traffic of handheld devices inside a residential DSL network, and Gember et al. [START_REF] Gember | A Comparative Study of Handheld and Non-Handheld Traffic in Campus WiFi Networks[END_REF] compare handheld and non-handheld devices in a campus WiFi network. In the context of 3G cellular data networks, Falaki et al. [START_REF] Falaki | A First Look at Traffic on Smartphones[END_REF][START_REF] Falaki | Diversity in Smartphone Usage[END_REF] study the smartphone traffic and identify the differences of user behavior based on the traces collected from a number of individual devices. Huang et al. [START_REF] Huang | Anatomizing Application Performance Differences on Smartphones[END_REF] propose a tool called 3GTest, which runs on thousands of smartphones over a wide geographic coverage. Each 3GTest-enabled device generates probe traffic to measure the network performance. Instead of collecting data from smartphone devices, Xu et al. [START_REF] Xu | Identifying Diverse Usage Behaviors of Smartphone Apps[END_REF] analyze the IP data traffic collected inside a tier-1 network core, and study the usage behavior of a variety of smartphone applications from the operator's perspective. Note that the above studies mainly focus on the data-plane performance. Our work complements the prior studies by also analyzing the control-plane performance. Specifically, we play the role of a network operator and look into the interactions of both data-plane and controlplane traffic traces collected within a 3G network.

Datasets and Preprocessing

We first describe several datasets that are used for our measurement study of a 3G UMTS network. We then explain how we correlate these datasets to obtain the information needed for our analysis. Finally, we address the limitations of our datasets.

Datasets

Data/control traffic. We capture traffic in both data and control planes from a commercial, city-wide 3G UMTS network in China. Fig. 1 shows the simplified topology of the 3G network we consider. The data path between a user equipment (UE) and the Internet traverses a base station (NodeB), a Radio Network Controller (RNC), and the core network (CN), all of which are defined in the 3GPP UMTS standard. Here, we focus on packet-switched domain of the CN, which comprises the Serving GPRS Support Node (SGSN) and the Gateway GPRS Support Node (GGSN). In a high level, the CN can be viewed as the central point that relays all UE-Internet data traffic as well as UE-UE data traffic. A 3G data network typically has a hierarchical architecture, i.e., multiple UEs communicate with a NodeB, multiple NodeBs communicate with an RNC, and multiple RNCs communicate with the CN.

We capture traffic in the integrated interface (a.k.a. Iu-PS) that connects 16 RNCs and the CN. We collect a 7-day span of traces from November 25, 2010 to December 1, 2010. The traces have a total size of around 13TB with about 27.6 billion packets and 383 million 5-tuple flows, including IP data packets with headers and full payloads and the Radio Access Network Application Part (RANAP) signaling messages. RANAP is the UMTS signaling protocol for the radio connection between a UE and the CN.

As shown in Section 4.1, we note that the data traffic patterns are very similar across each day over the 7-day span. Thus, in this paper, we focus on the 24-hour span of traces collected on November 28, 2010. The 24-hour traces have a total size of around 1.9TB with about 4.10 billion packets and 56.5 million 5-tuple flows. Given that our captured data packets contain full payloads, we apply a deep packet inspection (DPI) module to identify the application protocols. The DPI module has been available as part of a commercial product [START_REF] Huawei | MSCG hierarchical DPI solution[END_REF]. It maintains a database of signatures of hundreds of applications, and maps each 5-tuple flow to an IP application based on the pre-defined payload signatures. Table 1 summarizes the top application categories that we focus on in our analysis.

RRC connection record logs. A UE sends (receives) data to (from) the Internet via a

Radio Resource Control (RRC) connection. An RNC keeps the information for every RRC connection that we refer to as an RRC record. We collect the log files of the RRC records from all the 16 RNCs in the network (see Fig. 1). The log files span the same period as our data/control traffic trace, and account for a total of 168 million records with total size around 28GB from November 25, 2010 to December 1, 2010. From the RRC records, we then extract the useful fields including: (i) International Mobile Subscriber Identity (IMSI), the unique identification associated with each GSM-or UMTS-based UE, (ii) type allocation code (TAC), the code that uniquely identifies the UE device type and is composed of the initial 8-digit portion of the 15-digit International Mobile Equipment Identity (IMEI) code, (iii) RNC-ID, which uniquely identifies an RNC, and (iv) setup/release times of the RRC connection, which enable us to keep track of the connection duration.

Device type mappings.

For each TAC, we identify the corresponding device type, including the hardware model and operating system of a UE. We then establish the device type mappings. Such mappings can be obtained from different public sources such as [13,[START_REF]radiorraiders[END_REF]. Table 2 shows the device types considered in our analysis.

Correlating Datasets

We now describe how we correlate the datasets that cover both data-plane and controlplane information. Our correlation seeks to identify the control-plane behaviors of the Based on the above signaling message flow, we can identify four signaling messages that are important for our correlation: SCCP CC, Common ID, RAB Assignment Request, and RAB Assignment Response. Fig. 3 summarizes the fields of the signaling messages that we use for our correlation.

Correlating data/control traffic and RRC record logs. The goal of our correlation is to identify the data/control traffic for each RRC connection. One major challenge is that the data/control traffic and the record logs are obtained at different capture points that have loosely synchronized system clocks with around 60-150 second difference. Thus, we need to allow tolerance of such capture time differences in our correlation.

The basic idea of our correlation process is similar to the relational join operation by correlating the common fields in different datasets. We elaborate the details as follows:

1. We join the four signaling messages that have identical RNC-LR and SGSN-LR values and are seen within 15 seconds. RNC-LR and SGSN-LR are the local references of the RNC and SGSN associated with the RRC connection, respectively. 2. We join the output record in Step 1 with the RRC record that has the same IMSI field and is logged within 150 second difference. The time difference accommodates the imperfect synchronization among different captured points. 3. We then join the output record in Step 2 with the data packets. The correlation is based on the Tunnel Endpoint Identifier (TEID) field, which identifies the data communication tunnel. Each correlated data packet must have the same RNC IP, SGSN IP, and TEID fields as in the RRC record. Also, its timestamp must either be within the duration of the RRC connection, or differ from the setup/release times by no more than 150 seconds. If a data packet matches more than one RRC record, then we correlate it with the RRC record that has the closest setup/release time with the packet timestamp. 4. Finally, we obtain the device information of each packet with the device type mappings based on the TAC field.

The final output is that each data packet is associated with its corresponding RRC record and the device type. We then parse the data packets and perform the analysis. Implementation. Our correlation is implemented as a MapReduce [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF] program and run on a Hadoop [9] platform. This allows us to parallelize the correlation analysis. We utilize the repartitioned sort-merge join provided by Hadoop to realize the correlation. Our Hadoop platform consists of one namenode and seven datanodes that are connected by Gigabit switches. The platform has 112 CPU cores and 112GB memory in total, and it takes around 10 hours to complete the correlation process for one day of traces.

Limitations

One limitation of our work is that our datasets were collected in November 2010 (about a year ago from the time of this writing). Given the dramatic expansion of the smartphone market worldwide [START_REF]Worldwide Smartphone Market Expected to Grow 55% in 2011 and Approach Shipments of One Billion in 2015[END_REF], we expect that there is a dramatic growth of the volume of data/control-plane traffic in 3G networks as of today. Also, there have been continuing version upgrades for smartphone operating systems (e.g., in Android and iPhone/iPad), and such upgrades may change the underlying data transmission behaviors. Nevertheless, since our correlation methodology is based on the standard 3G specifications, it remains applicable for today's 3G networks in general, provided that the same datasets are available. One important future work is to validate the findings of our measurement study with the latest datasets.

Another limitation is that we cannot validate the accuracy of the DPI tool used in our flow-based application identification, given that the tool is part of a commercial product and is closed-source. Nevertheless, we expect that the identification process is sufficiently accurate for our analysis due to the commercial nature of the tool. Some of our findings (see Section 4) also conform to our intuition. Note that our flow-based application identification can also be substituted by other approaches, such as portbased analysis [START_REF] Falaki | A First Look at Traffic on Smartphones[END_REF] or dynamic protocol detection [START_REF] Dreger | Dynamic Application-Layer Protocol Analysis for Network Intrusion Detection[END_REF].

Measurement Results

Overview

We first give a general overview of our captured data traffic. After pre-processing, we identify more than 80% of traffic (out of ∼13TB) that can be successfully associated with the corresponding signaling traffic. Fig. 4 plots the IP traffic volume (per minute) over time in our 7-day traces, and Fig. 5 shows the number of devices identified on each day. We observe that the distributions of each day are fairly stable. In particular, the distributions do not indicate significant differences across weekdays and weekends.

In the following analysis, we only focus on the 1-day traces on November 28, 2010. Given the regularity of the traffic, we expect that our observations are consistent for other days of traffic. Fig. 6 illustrates the number of devices for different types listed in Table 2. There are 64,398 devices in total, in which iPhone leads all devices with a proportion of 32%. Mobile hand-held phones (including smartphones or low-end feature phones) dominate the majority of devices, while iPad and Datacard only account for 7.9% and 7.5% of devices, respectively. We point that over 99% of the devices can be successfully identified with the corresponding device types. Fig. 7 shows the total traffic volume for each traffic type. Datacard devices contribute 46% of the total traffic, although they only account for 7.5% of devices. We will explore possible reasons for this phenomenon later in Section 4.2.

We now evaluate the control-plane performance of different device types, based on our RRC record logs. Fig. 8 shows the average number of RRC connections per device for each device type. As shown, iPhone triggers the most RRC connections per device (237 times), followed by iPad (174 times). Even datacard devices dominate the largest portion of IP traffic, each datacard device triggers a relatively small number of RRC connections (68 times) compared to smartphones (e.g., Android, Windows Mobile). Note that each RRC connection setup/release triggers a number of signaling messages

0 0.5 1 1.5 2 2.5 x 10 4 IP H O N E S Y M B IA N F E A T U R E A N D R O ID IP A D D A T A C A R D W IN D O W S B L A C K B E R R Y U N K N O W N B A D A L IN U X Number of Devices
D A T A C A R D IP H O N E IP A D S Y M B IA N F E A T U R E A N D R O ID W IN D O W S U N K N O W N L IN U X B L A C K B E R R Y B A D A
Total Traffic Volume (GB) Fig. 7. Total traffic volume of each device type.

between a UE and an RNC, and such signaling messages consume radio resources of the cellular network [START_REF] Lee | On the detection of signaling DoS attacks on 3G/WiMax wireless networks[END_REF]. With the frequent RRC connection setups/releases, we can see that iPhone/iPad devices can bring large signaling overhead of an RNC and consume substantial radio resources of the whole cellular network. Fig. 9 shows the average RRC connection duration per device for each device type. Note that iPhone has the smallest duration among all (30 seconds). Since iPhone triggers more RRC connections and each RRC connection has a short duration, it implies that iPhone devices inject a high intensity of signaling workload into the network. In contrast, Datacard has the longest RRC connection duration, so we expect that Datacard devices tend to run long-lived data transfer applications that keep an RRC connection active for a long time.

We thus far observe that different device types have distinct data/control-plane performance. In the following subsections, we explore the possible reasons behind.

O N E IP A D A N D R O ID W IN D O W S S Y M B IA N B L A C K B E R R Y L IN U X D A T A C A R D F E A T U R E B A
D A T A C A R D IP A D F E A T U R E S Y M B IA N L IN U X B L A C K B E R R Y B A D A A N D R O ID W IN D O W S IP H O N E
Average RRC Duration (Sec.) per Device Fig. 9. Average RRC duration per device.

Application Characteristics

Let us examine the application usage patterns of different device types, and explore how the traffic compositions of the device types lead to the distinct data/control-plane behaviors that we observe. We first analyze the overall traffic distributions of different IP applications listed in Table 1. Fig. 10 shows the traffic volume distribution of different IP applications, where web browsing (38%), streaming (21%), P2P (10%) and file access (10%) are ranked the top four. IM and Email applications contribute 2% and 1% of the total traffic, respectively. The traffic that cannot be identified, i.e., labeled as "Unknown" in Fig. 10, only contributes 9% of the traffic. In other words, over 90% of total traffic can be successfully identified by our DPI tool. Fig. 11 shows the total number of RRC connections triggered by each application. In this work, we define that an application triggers an RRC connection if the first data packet transmitted in the RRC connection belongs to the application. We see that Tunneling triggers the most RRC connections among all applications. The reason is that a tunneling session is first established for providing a secure path for any other application protocols, or supporting the roaming service. IM triggers 21% of RRC connections, while generating only 2% of the total traffic (Fig. 10). On the other hand, P2P triggers only 0.1% of the total number of RRC connections, while contributing 11% of the total traffic. This is an important observation because it clearly shows that different applications have inherently different data/control-plane behaviors.

Let us investigate the application usage patterns of different device types. Fig. 12 illustrates the total traffic volume of applications for each device type, in which we only look at the top device types that contribute the most traffic. We make two key observations. First, datacard devices contribute 85% and 48% of all P2P and streaming traffic, respectively. Since most datacards are attached to static terminals such as PCs or laptops, these static terminals tend to run long-lived applications. Thus, they contribute a large volume of data-plane traffic even the population of datacard devices is small. Also, P2P and streaming applications trigger very few but long-lived RRC connections, and this validates our previous observations in Figs. 8 and9. Second, web browsing, streaming, and file access are the top three applications that account for the most traffic volume on smartphones (i.e., iPhone, Android, Symbian, Windows Mobile), and they altogether contribute over 80% of the smartphone traffic.

Active Devices

We now explore the behaviors of active devices and see their impact on the data/controlplane performance. We say that a device is active within time [t 1 , t 2 ] if it starts and releases an RRC connection at times t 1 and t 2 , respectively. Figs. 13 and 14 plot the distributions of the traffic volume and the number of active devices (per minute) for different device types over a 24-hour period (on Nov. 28), respectively. As expected, Fig. 13 shows that the traffic volume peak appears in day time, and the traffic trough appears at late night. While the number of active devices in Fig. 14 shows a similar pattern, the peak-trough difference is significantly different. We find that the traffic volume at the trough is 93% less than the peak traffic volume in Fig. 13, while the number of active devices at the trough is only 52% less than the peak value in Fig. 14.

After further investigation, we find that iPhone and iPad have a very similar pattern that is distinct from other device types, i.e., the numbers of active devices of iPhone and iPad remain quite stable during the 24-hour period. On the other hand, other device types exhibit obvious troughs and peaks in the number of active devices, with the troughs also appearing at late night.

We find that the internal heartbeat mechanism of iPhone/iPad keeps the devices active, even there is no data traffic initiated by user applications. To demonstrate, Fig. 15 shows the probability density of the inter-arrival times of RRC connection setups of iPhone. The inter-arrival times of RRC connections of iPhone occur more often at two values: 64 seconds (18.1%) and 589 seconds (4.9%). Similar observations are also made for iPad. We investigate and find that iPhone/iPad devices are "always-on" and generate heartbeat packets around every 60 seconds, and such packets are sent to Apple servers. Each heartbeat packet triggers an RRC connection, which will be released if there is no data traffic for an idle period that is less than 60 seconds. On the other hand, we do not observe any explicit heartbeat patterns in Android (not shown in the figure), possibly because there are many variants of Android devices and their heartbeat designs are different. In short, the heartbeat packets that we observe in the iPhone/iPad devices introduce many RRC connection setups/releases, which could lead to high signaling overhead in the network core.

Note that there are a few upgrades of iOS (Apple's mobile operating system) in 2011. In iOS 4.2 (which was launched in late November 2010), a technology that enables mobile devices and the network core to collaboratively minimize network congestion and mobile battery consumption [START_REF] Kingsley-Hughes | iOS 4.2 Supports Network Controlled Fast Dormancy[END_REF]. This may change the heartbeat behavior that we observe in our datasets. One future work is to validate such a heartbeat behavior with the latest datasets, based on the same correlation methodology as described in Section 3.2. 00:00 04:00 08:00 12:00 16:00 20:00 00:00 0 0.5

Summary, Implications, and Conclusions

We now summarize the key observations and potential challenges through the analysis of our massive data traces.

-In the data plane, datacard devices contribute almost 50% of the total traffic, while accounting for only 7% of the device population. Network operators may devise special resource allocation schemes for datacard users. Also, iPhone/iPad devices altogether account for around 40% of devices, and contribute nearly 40% of the total traffic due to their large market shares. -Our application-based analysis clearly shows that different user groups (distinguished by device types) have distinct user behaviors with specific preferences of choosing applications. For example, in all Apple devices (iPhone and iPad), the dominant applications are web browsing, streaming, and file access, and they altogether contribute more than 90% of iPhone/iPad traffic. From the network operators' perspectives, there are challenging issues of providing QoS guarantees and QoE improvement for different user groups. -In the signaling control plane, among all device types, iPhone has the highest average number of RRC connections per device. Meanwhile, iPhone/iPad devices have a very similar heartbeat behavior that triggers significantly more RRC connections than any other device types. Recall that each RRC connection setup/release involve a number of signaling messages exchanged between a UE and an RNC [START_REF] Lee | On the detection of signaling DoS attacks on 3G/WiMax wireless networks[END_REF]. These results reveal that specific device types can increase the signaling overhead to the network.

This paper analyzes the data/control-plane performance of different device types using massive traces collected from the core of a 3G UMTS city-wide network. We describe a correlation methodology that studies the interactions of different data/controlplane datasets, and make several key observations from our analysis that could be of interest to network operators and researchers. Our measurement study motivates the importance of characterizing the data/control-plane workloads of a 3G network and designing adequate strategies for network planning, resource allocation, and pricing. Since our measurement study is based on the datasets that are compliant with the 3G standard, our analysis methodology can be generalized for other 3G operational networks.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Total traffic volume (per minute) over one week.

Fig. 6 .

 6 Fig. 6. Number of devices for each device type.

Fig. 8 .

 8 Fig. 8. Average number of RRC connections per device.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Traffic volume of applications.

Fig. 12 .

 12 Fig. 12. Traffic volume distribution of applications for each device type (note that the y-axis scale is different for each device type for clear presentation).

Fig. 14 .Fig. 15 .

 1415 Fig. 14. Number of active devices (per minute).

Table 1 .

 1 Summary of categories of applications.

			RNC		CN
		...	...	Iu-PS	SGSN	GGSN	Internet
	UE		RNC
		NodeB	RRC connection	Data/control traffic
			record logs
		Fig. 1. A simplified architectural view of a 3G UMTS network.
	Category	Description
	Web browsing	HTTP-based web browsing activities
	IM	instant messaging applications such as Yahoo Messenger, MSN, Tencent QQ, etc.
	File access	audio/video files, software download/updates, FTP, etc.
	Streaming	online video services such as YouTube, PPLive, QQLive, Tudou, etc.
	Email	email services such as IMAP, POP3, SMTP, etc.
	P2P	file sharing via P2P software such as BitTorrent, Thunder, etc.
	Network Admin	network protocols such as DHCP, DNS, MDNS, NetBios, NTP, etc.
	Tunneling	tunneling protocols such as Socks4, Socks5, SSL
	Others	other successfully identified applications

Table 2 .

 2 Summary of device types. Common ID message, which contains the IMSI of the UE. The RNC associates the IMSI with the RRC connection for the UE and keeps this association throughout the RRC connection. Note that a single RRC connection may consist of one or multiple Radio Access Bearers (RABs) assigned for data communications. Each RAB assignment defines the actual radio resources for transmitting data traffic between the UE and the CN. The CN sends a RAB Assignment Request message to the RNC, which then executes the RAB setup protocol with the UE. Finally, the RNC replies a RAB Assignment Response message to the CN. From this onwards, the UE can send or receive data.

	UE	RNC	CN
	RRC connection setup	RANAP: Initial UE message
			SCCP: CC (Success/Failure)	SCCP CC	Timestamp	RNC-LR SGSN-LR
			RANAP: Common ID
				Common ID	Timestamp	RNC-LR IMSI
	RAB setup		RAB Assignment Request	RAB assignment request	Timestamp	RNC-LR SGSN IP SGSN TEID
			RAB Assignment Response	RAB assignment response	Timestamp SGSN-LR RNC IP	RNC TEID
	Fig. 2. Signaling message flow of the RRC con-	Fig. 3. Signaling message format (LR denotes
	nection setup.			local reference).

corresponding data-plane packets generated by different device types and different IP applications.

Extracting signaling messages. We first extract the RANAP signaling messages that are later used for correlation with RRC records. Fig.

2

depicts the signaling message flow of the RRC connection setup. When the UE wants to send or receive data, the RNC first makes a Signaling Connection Control Part (SCCP) connection request with the CN, which replies a SCCP Connection Confirm (SCCP CC) message. SCCP can be viewed as the transport protocol for RANAP. The CN also replies a

Acknowledgment

The work of Patrick P. C. Lee is supported in part by grant GRF CUHK413711 from the Research Grant Council of Hong Kong


D Saucez

J Kim
email: jkim@net.t-labs.tu-berlin.de

L Iannone

O Bonaventure
email: olivier.bonaventure@uclouvain.be

C Filsfils
email: cfilsfil@cisco.com

A Local Approach to Fast Failure Recovery of LISP Ingress Tunnel Routers

Keywords: Locator/ID Separation, Next Generation Internet, Addressing and Routing Architectures, Measurements, Emulations

LISP (Locator/ID Separation Protocol) has been proposed as a future Internet architecture in order to solve the scalability issues the current architecture is facing. LISP tunnels packets between border routers, which are the locators of the non-globally routable identifiers associated to end-hosts. In this context, the encapsulating routers, which are called Ingress Tunnel Routers (ITR) and learn dynamically identifierto-locators mappings needed for the encapsulation, can cause severe and long lasting traffic disruption upon failure. In this paper, thanks to real traffic traces, we first explore the impact of ITR failures on ongoing traffic. Our measurements confirm that the failure of an ITR can have severe impact on traffic. We then propose and evaluate an ITR synchronization mechanism to locally protect ITRs, achieving disruptionless traffic redirection. We finally explore how to minimize the number of ITRs to synchronize in large networks.

Introduction

It is widely recognized that the current Internet architecture is a victim of its own success and is facing unforeseen scalability issues, in terms of increasing routing tables, multi-homing, and inter-domain traffic engineering ( [START_REF]BGP Routing Table Analysis Report[END_REF], [START_REF] Quoitin | Evaluating the benefits of the locator/identifier separation[END_REF], [START_REF] Meyer | Report from the IAB Workshop on Routing and Addressing[END_REF]). Both academic researchers and industrial companies concur that the locator/ID separation paradigm, i.e., separating the semantic of end-systems' identifier and location (currently merged in the IP address), will provide the needed scalability improvement. Among the several recently proposed protocols leveraging on this principle, the Locator/ID Separation Protocol (LISP [START_REF] Farinacci | Locator/ID separation protocol (LISP)[END_REF]) has encountered the wider success and is being developed in the IETF (Internet Engineering Task Force [START_REF]Locator/ID Separation Protocol (LISP) Working Goup[END_REF]). LISP assigns Endpoint IDentifiers (EIDs) to end-hosts and Routing LOCators (RLOCs) to tunnel routers. In the core Internet only RLOCs are globally routable and used to tunnel packets between end-systems, which use EIDs that are globally unique but not globally routable (hence the use of tunnels).

Like the current Internet, LISP is affected by temporary link or node failures that may disrupt end-to-end reachability. More specifically, when an encapsulating router -the so called Ingress Tunnel Router (ITR) -fails, alternate/backup ITRs are not readily able to take over traffic encapsulation because they do not have the necessary identifier-to-locator mappings, resulting in prolonged packet drops and traffic disruption. Some aspects of the performance of LISP have been previously explored in other works, either focusing on the scalability of specific LISP elements, like the LISP cache ( [START_REF] Kim | A Deep Dive into the LISP Cache and What ISPs Should Know about It[END_REF], [START_REF] Chen | Evaluating the Performance on ID/Loc Mapping[END_REF], [START_REF] Iannone | On the cost of caching locator/id mappings[END_REF]) or on the mapping system used to distribute the mappings binding the locators with the identifiers ( [START_REF] Sriram | Enhanced Efficiency of Mapping Distribution Protocols in Scalable Routing and Addressing Architectures[END_REF], [START_REF] Choi | ID/LOC Separation Network Architecture for Mobility Support in Future Internet[END_REF], [START_REF] Jakab | LISP-TREE: A DNS Hierarchy to Support the LISP Mapping System[END_REF]). However, how LISP reacts to link and node failures has been largely neglected. The only document briefly discussing reachability issues is the draft by Meyer et al. [START_REF] Meyer | Architectural Implications of Locator/ID Separation[END_REF], which focuses on the general implications of having an Internet architecture based on the locator/ID separation paradigm. To the best of our knowledge, the present paper is the first analyzing failures in LISP, and, from a more general perspective, the failure of encapsulating routers in the context of a locator/ID separated architecture.

In this paper, we first provide all the relevant information for a complete understanding of the problem, overviewing LISP in Sec. 2. In Sec. 3 we formalize the failure problem, followed by our proposal (Sec. 4) and its evaluation (Sec. 5). Then in Sec. 6 we tackle the recovery problem, showing how it can be solved as well with our approach. Sec. 7 and Sec. 8 explore the synchronization issue in large networks. Finally, Sec. 9 concludes the paper.

LISP Basics

LISP is typically implemented on customer-edge border routers, whose upstream IP address (i.e., the one facing the Internet), which is a part of the Border Gateway Protocol (BGP) routing space, is the Routing LOCator (RLOC) used to locate end-systems of the local domain. The end-systems in the local domain use globally unique but not globally routable (hence not injected in the BGP routing infrastructure) IP addresses (or End-point IDentifiers -EID). Then, as shown in Fig. 1, LISP tunnels packets in the core Internet from one RLOC of the source EID to one RLOC of the destination EID. The Ingress Tunnel Router (ITR) prepends a LISP header to each packet using the ITR's RLOC as a source address and the Egress Tunnel Router's (ETR's) RLOC as a destination address, while the ETR strips this header and forwards the packet to its final destination.

The use of different addressing spaces, namely the EIDs and RLOCs, implies that there is the need of bindings between EIDs and RLOCs. These bindings specify which RLOC to use when encapsulating packets towards a given EID. These bindings are called mappings, hence the reason why LISP is called a mapand-encap approach. For scalability reasons mappings are obtained by ITRs ondemand and kept in a dedicated cache [START_REF] Iannone | On the cost of caching locator/id mappings[END_REF]. When, no suitable entry is present, a cache-miss is triggered, causing a query to a Map-Resolver (MR [START_REF] Fuller | LISP Map Server[END_REF]), which is the entry point of the Mapping System. The query consists in a Map-Request message to which eventually the MR (or directly the destination ETR) will return a Map-Reply message with the requested mapping. 5 Mapping retrieval is a key point performance wise since a cache-miss causes signaling traffic, increases communication setup latency, and decreases the throughput. Such an impact is due to the fact that current implementations drop packets causing a cache-miss. 6In a normal IP network, such as the enterprise network shown in the right part of Fig. 1, the Interior Gateway Protocol (IGP) handles link and node failures. Consider for example that ITR 1 and ITR 2 advertise a default route in the IGP, a very common deployment. In this case, if (the link attached to) ITR 1 fails, then the other local routers will detect the failure and update their routing tables to forward the packets to ITR 2 so that they can reach the Internet through it. During the last years, various techniques have been developed to enable routers to quickly react upon such failures [START_REF] Vasseur | Network Recovery: Protection and Restoration of Optical, SONET-SDH, IP, and MPLS[END_REF]. With LISP, the situation is different. If ITR 1 fails, the IGP will quickly redirect the packets to ITR 2 . However, ITR 2 will be able to forward these packets only if it already knows the corresponding mappings. Otherwise, ITR 2 will have to drop packets while querying the mapping system, an operation that can take tens of milliseconds or more per mapping [START_REF] Jakab | LISP-TREE: A DNS Hierarchy to Support the LISP Mapping System[END_REF].

The ITR Failure Problem

In order to estimate how important the ITRs' failure problem is, the first step is to evaluate the level of redundancy present in enterprise and campus networks. Indeed, in today's Internet, these networks often contain several redundant border routers to preserve connectivity in case of failures.

To evaluate such an aspect, we analyze Internet topology information from the Archipelago project [START_REF] Claffy | Internet mapping: From art to science[END_REF] and BGP tables of the Routeviews project [START_REF]Route views, University of Oregon Route Views project[END_REF]. We first extract the stub prefixes from the BGP table of Oregon-IX collected on August 12 th 2010 [START_REF]Route views, University of Oregon Route Views project[END_REF]. The BGP curve in Fig. 2 shows the number of neighbor ASes for each prefix. This is an approximation of the multi-homing degree. We obtain the traceroute curve in Fig. 2 by filtering an Archipelago trace captured July 24 th 2010 [START_REF] Claffy | Internet mapping: From art to science[END_REF]. Archipelago traces are a collection of traceroutes performed from several vantage points to any possible /24 prefix. We consider that the last router that does not belong to the stub BGP prefix is a border router for that prefix, providing an approximation of the number of active routers of the multi-homed stub prefixes. The curves in Fig. 2 show that when a stub prefix is multi-homed, most of the time it has only two border routers. Nevertheless, the long tail of the distribution indicates that for some prefixes, the number of ITRs can be potentially high. For this reason, to assess to what extent ITRs' failures are a problem, we can analyze the impact on traffic for the simple scenario of 2 ITRs, by using trace-driven emulations and the topology presented in Fig. 1. Our emulations use the software and the methodology used in previous works ( [START_REF] Kim | A Deep Dive into the LISP Cache and What ISPs Should Know about It[END_REF], [START_REF] Iannone | On the cost of caching locator/id mappings[END_REF]), assuming a mapping granularity equivalent to the current BGP table [START_REF] Iannone | On the cost of caching locator/id mappings[END_REF]. With this granularity, previous works ( [START_REF] Kim | A Deep Dive into the LISP Cache and What ISPs Should Know about It[END_REF], [START_REF] Iannone | On the cost of caching locator/id mappings[END_REF]), have shown that cache size is pretty small, allowing to neglect cache overflow problems, which are unlikely to happen.

We use two different 24h-long traces collected in 2010. A first trace, collected in September 1 st with a NetFlow collector without sampling, is from a middle sized Campus network (∼9,000 active users), connected via a 1 Gbps link to its ISP and 122.35 Mbps average traffic. The second trace has been collected within a large European ISP (∼20,000 active DSL customers). We split the network of the captured traces into two subnetworks (served by ITR 1 and ITR 2 ) in order to implement the multi-homing scenario as in Fig. 1. Since ISP's topology was unknown, we attach half of the address space to ITR 1 and the other half to ITR 2 . On the contrary, the Campus network has two border routers, which we assigned the role of ITR 1 and ITR 2 , hence attaching the traffic to the ITRs according to the real topology. From the traces, we selected the busiest hour (i.e., the worst case) and emulated the failure of one ITR in the middle of the selected hour. Fig. 3 shows the impact of the failure on the number of cache-misses on the alternate ITR, for the ISP and the Campus networks, which have a similar behavior. The figure shows the normal behavior without any failure (solid lines), as well as the two cases where one of the ITRs fails (dashed lines). During the first minute after the failure there are up to 5,000 additional cache-misses per minute (more than three times the normal rate) due to the traffic redirection on the alternate ITR. This failure can affect established TCP flows and cause packet drops for seconds or more. Fig. 3 shows as well that the transient state lasts around 5 minutes.

It has to be pointed out that we are underestimating the impact since we do not consider mapping delay, i.e., we assume that the mapping is retrieved immediately after the cache-miss. In reality, failure-induced cache-misses have much more severe impact because they affect established high traffic volume flows. While a normal cache-miss causes the loss of a few packets at flow setup time [START_REF] Ohmori | Analyses on first packet drops of lisp in end-to-end bidirectional communications[END_REF], a failure-induced cache-miss could cause more losses because disrupting high throughput flows on high bandwidth links. Moreover, the peak of cache-miss causes a load peak on the mapping system to retrieve the missing mappings.

Local ITR Failure Protection

To solve the problem presented in the previous section, we propose to synchronize the caches of a group of ITRs of the same site. The set of ITRs belonging to the same group is called the Synchronization Set. Replicating the LISP cache on the ITRs ensures that in case of failure and traffic re-routing, the packets of an existing flow will never be dropped because of a cache-miss, whatever the alternate ITR of the set is used.

There are two ways to synchronize ITR caches: either the mappings are pushed to the ITRs of the Synchronization Set, or the latter are notified that a new mapping has to be retrieved. We discuss both approaches in further details in Sec. 8. Here we just assume that the mapping requested by one ITR of a Synchronization Set is immediately replicated on all ITRs of the set. To ensure that mapping caches remain synchronized, the ITRs should keep it for the same amount of time. This implies that synchronized ITRs cannot anymore use a simple inactivity timeout [START_REF] Kim | A Deep Dive into the LISP Cache and What ISPs Should Know about It[END_REF] to purge unused entries from their cache. Indeed, doing so would lead to a loss of synchronization, since the same mapping can expire on one ITR, because it has not been used, while it is kept on the other ITR that forwarded packets towards this EID prefix.

To avoid such loss of synchronization, we propose to use a different policy, namely to keep each mapping in the cache during the TTL (Time-To-Live) that LISP associates to this mapping. When the mapping TTL expires the ITR must check the entry usage during the last minute. If the entry has not been used, it is purged. Otherwise, the mapping entry is renewed by sending a Map-Request. This last action triggers the synchronization mechanism, again replicating the mapping to all ITRs of the Synchronization Set. Such approach guarantees that, if no ITR has used the mapping during the last minute before TTL expiration, all replicas on the different ITRs will be purged. Otherwise, if at least one ITR used the mapping, the mapping will be replicated on all ITRs, renewing it for another TTL time. In both cases there is a consistent state on all ITRs of the Synchronization Set.

ITR Failure Protection Evaluation

To evaluate the cache synchronization technique we follow the same methodology and the same traces used in Sec. 3. On the one hand, we emulate the asynchronous cache strategy, i.e., where each ITR manages its own cache independently. On the other hand, we emulate the synchronous cache strategy, i.e., where ITR 1 and ITR 2 belong to the same Synchronization Set. In all of our simulations, we set the TTL to 5 minutes, which we consider as a reasonable worst case. Indeed, a lower value would generate too much overhead [START_REF] Kim | A Deep Dive into the LISP Cache and What ISPs Should Know about It[END_REF]. In practice, it is likely that the TTL will be longer than 5 minutes (the default in current LISP implementations being 24h), reducing the number of cache-misses, but increasing the number of entries that are stored in the cache [START_REF] Iannone | On the cost of caching locator/id mappings[END_REF]. However, it is worth noticing that the cost of slightly increasing the cache is very small compared to the cost of adding a redundant link. The figures in the remainder of this section show the cache behavior of ITRs in the normal case (i.e., without failures) using solid lines, while dashed lines correspond to scenarios with failures. In Fig. 3, the observed peak of cache-misses indicates that the traffic behind the two ITRs is not identical and not balanced; hence some mappings are in one ITR but not in the other. This is confirmed by Fig. 4, showing the evolution of the cache size for the ISP network (Campus network showing the same behavior), reinforcing the motivation for cache synchronization. Indeed, it can be observed that the ITRs have in general different cache sizes and when one of the ITRs fails the diverted traffic makes the size of the remaining ITR to grow. Fig. 5 and Fig. 6 show the evolution of both cache size and cache-misses when our synchronization approach is used. The curves labeled ITR1 and ITR2 show the evolution on the ITRs when they are not synchronized and none fails. The curve labeled MAX shows the maximum obtained when ITRs are synchronized but the content of their cache is assumed to be completely disjoint (i.e., the worst case). Finally, the curve labeled ITR1 (ITR2 failure) (resp. ITR2 (ITR1 failure)) corresponds to the actual values obtained with our synchronization approach if ITR 2 (resp. ITR 1 ) fails. Fig. 5 is interesting for two reasons. First, no peak is observed when the ITR fails, rather, the miss rate corresponds to the miss rate that would have been observed if the network only had one ITR. As one could expect, the miss rate measured in steady state after the failure is identical to the miss rate observed in Fig. 3 once the steady state has been reached. Second, comparing Fig. 3 and Fig. 5, it turns out that the miss rate when no failure occurs is lower when the ITRs are synchronized than when they are not. This difference can be explained by the fact that some form of locality occurs between the traffic of the two ITRs.

In summary, our emulations on the 2 ITRs scenario clearly show that ITRs' cache synchronization brings two main advantages: (i) it avoids a miss storm (hence induced packet drops) upon ITR failure; (ii) reduces the number of misses (hence packet drops) in the normal case. These benefits come at a small cost of increased cache size. Indeed, Fig. 6 confirms that the ITRs have naturally some entries in common, which makes the burden of synchronization acceptable.

ITR Recovery: Problem, Protection, and Evaluation

The cache-miss storm in case of failure, as investigated so far, can also be observed when an ITR boots (or comes back online after failure). Indeed, in this case, its cache is empty, hence the traffic attracted for encapsulation will cause misses and will be dropped. Our synchronization mechanism can be used also in this scenario. In case of synchronization, the time needed for an ITR to be synchronized with the other ITRs of the Synchronization Set is at most equal to the TTL. In this situation, when the ITR starts, it could begin the synchronization process and wait TTL time before announcing itself as an ITR able to encapsulate packets. With this approach the miss rate is not different than if the ITR had always encapsulated traffic.

This naive approach is very simple but has a major drawback. The TTL can be set to a high value, refraining the ITR from being used for a long period of time. To overcome this issue, we suggest allowing the ITR to receive a copy of the cache from another ITRs in the Synchronization Set. The transfer of the cache's information must be done reliably, e.g., using TCP. In this way the ITR can announce itself right after the cache transfer, shortening the start up time to a minimum, while preserving the benefits of the synchronization approach.

To better understand the impact on the traffic in the recovery case, we perform emulations in the two ITRs scenario, with ITR 2 recovering after ITR 1 runs alone for the last 30 minutes (using the ISP trace). Once back online, ITR 2 starts synchronizing with ITR 1 , i.e., it receives mapping information, but the traffic is still all routed toward ITR 1 . After 5 minutes (i.e., the TTL value we are using throughout all emulations), when the cache is synchronized with ITR 1 , the original setup is restored, sending traffic again to ITR 2 . Fig. 7 shows the miss rate observed at the ITRs for both the synchronized and the non-synchronized cases. The curve ITR1 (ITR2 failure) gives the miss rate observed on ITR 1 before the recovery of ITR 2 , while ITR1 (sync) (resp. ITR2 (sync)) shows the miss rate as observed on ITR 1 (resp. ITR 2 ) after ITR 2 has recovered when synchronization is used. For comparison, the curve ITR1 (async) (resp. ITR2 (async)) shows the miss rate when no synchronization is used, with a peak of 10,000 cache-misses confirming that waiting TTL instants to lazily synchronize the cache avoids cache-miss storm. For completeness, Fig. 8 shows the evolution of the cache size before and after recovery. In all cases, the cache smoothly moves towards its new steady state TTL time after the recovery. This smooth convergence motivates the use a fast cache synchronization method (i.e., explicit cache copy request) to speed-up the recovering of an ITR.

Synchronization Set in Large-Scale Networks

As shown in Sec. 3, in case of failure, when no synchronization is used, both the cache size and the cache-misses increase, as summarized in Tab. 1. While relatively similar increases can be observed comparing the results of the Campus and the ISP traces, the difference of the increases between ITR 1 and ITR 2 may be significant. Indeed, the average miss rate can be as low as 28% when ITR 1 fails, but as high as 96%, for the same trace, when ITR 2 fails. This result suggests that the Synchronization Set is a key point and should be carefully computed. The issue is exacerbated in large networks containing potentially many ITRs, which cannot all be synchronized.

For the above-mentioned reasons, it is important to have an idea of how large the Synchronization Set can be. To this end, we exhaustively calculated the Synchronization Set of 8 different real large-scale network topologies. Each of these topologies belong to one of the three following categories: (i) TIER1 grouping For the topologies where we had enough information, we considered the routers connected to another ISP as ITRs; the routers connected to the customers or to LANs with end-hosts are considered the EID routers; all the other routers are classified as backbone routers. For the topologies where no enough information was available, we classified the routers based on their connectivity degree. All the routers with a connectivity degree higher or equal to the 90 th percentile of the connectivity degree are considered ITRs. The routers with a connectivity degree lower or equal to the 80 th percentile of the connectivity degree are EID routers. All the other routers are classified as backbone routers. Applying this heuristic provides results similar to the topologies where information was available. To construct the Synchronization Set, we exhaustively enumerate the topology changes for any possible single failure (i.e., router or link).

Fig. 9 gives the quartiles (including min., max., and median) computed for the number of ITRs potentially used by each EID router. For this evaluation, we consider that only one EID router serves an EID prefix. This is a reasonable assumption since for the transit networks we evaluated (i.e., TIER1a, TIER1b, NREN, Internet2, and Géant) the EID prefixes belong to the customers, which have only one router toward their ISP (but are multi-homed with several ISPs). The figure shows that the number of ITRs potentially used by the EID routers is relatively independent of the type of topology and is between 1 and 2. Meaning that only a small portion of the ITRs are serving the same EIDs, due to the fact that large networks are segmented in relatively independent points of presence. This result clearly shows that synchronizing all the ITRs of a large network would be inefficient, while in our case the burden will be reasonable as an ITR will synchronize only with few other ITRs.

Fig. 10 goes the other way around, showing the number of routers that are potentially behind a single ITR, using again quartiles. The figure shows that in general an ITR has about half a dozen of routers behind it, going up to few tens for large networks. Therefore, the failure of an ITR can potentially impact on an important portion of traffic, which has to be shifted to the other ITRs. If the caches are not synchronized, the ITRs to which the traffic is diverted might experience a very important miss rate, with high packet drops. Synchronizing the ITRs' caches avoids such drops, as we demonstrate in Sec. 5.

In summary, protecting the ITRs is important as the failure of one of them can impact a large portion of the network. Fortunately, topologies of real networks seem to be segmented so to facilitate grouping the ITRs in small Synchronization Sets.

Synchronization Techniques

Even if, as discussed above, the Synchronization Set is in practice small also for large-scale networks, it is important to implement a mechanism to achieve such synchronization without introducing excessive overhead or management complexity. There are two possible ways to synchronize ITRs: either, the mappings are pushed to the ITRs, or the ITRs are notified of the presence of a new mapping and they retrieve the mapping on their own.

In both cases, the synchronization can be implemented either by leveraging on a routing protocol extension, by using a specific existing protocol (e.g., [START_REF] Luciani | Server Cache Synchronization Protocol (SCSP)[END_REF], [START_REF] Saito | Optimistic replication[END_REF], [START_REF] Obraczka | Evaluating the performance of flood-d: A tool for efficiently replicating internet information services[END_REF], [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF]), or by creating a brand new protocol. Extending a routing protocol to synchronize ITRs implies that they must be in the same routing protocol instance (e.g., the same IGP). However, this assumption is too restrictive as it might exist cases where the ITRs are in different networks (e.g., the ITRs are operated by the ISPs and the LISP site is multi-homed). Hence, we do not consider the extension of the routing protocol as an acceptable solution. Fortunately, LISP already proposes features that are handy to implement a synchronization mechanism. Indeed, LISP specifies the Included Map-Reply [START_REF] Farinacci | Locator/ID separation protocol (LISP)[END_REF] feature to push mappings in ITR caches. An included Map-Reply is a special Map-Request, which piggybacks a mapping. LISP also specifies the Solicit Map-Request (SMR) bit in Map-Requests to force ITRs to refresh their cache [START_REF] Farinacci | Locator/ID separation protocol (LISP)[END_REF]. When an ITR receives a Map-Request with the SMR bit set, it sends a Map-Request to retrieve a mapping for the EID indicated in the SMRed Map-Request.

Since both ITRs and MRs are involved in the mapping resolution, these are good candidates to trigger cache synchronization. However, ITRs are data-plane devices that need to forward packets at line rate. Therefore, imposing them to actively manage the synchronization protocol might cause excessive overhead with consequences on the data-plane performance. On the contrary, Map Resolvers are purely control-plane devices that are not intended to forward packet at line rate. Hence, MRs look like the best candidates to manage the synchronization protocol. To implement the cache synchronization based on notification messages, the MR only has to send an SMRed Map-Request to all the ITRs, when it receives a Map-Request. However, if the mappings are pushed to the caches, then the MR has to proxy the Map-Requests. The MR performs two operation when it receives a Map-Reply. First, it forwards the Map-Reply to the ITR that requested the mapping. Second, it sends the mapping to the other ITRs by using an included Map-Reply.

As discussed above, the Synchronization Set is in practice small and can be statically configured in the MR. However, for large or very dynamic networks, the configuration burden might still become cumbersome and a dynamic ITR discovery protocol coupled with an automatic Synchronization Set computation algorithm should be considered. It is out of the scope of this paper to propose any specific solution for these two mechanisms. Furthermore, there is still the open question of what is the best trade-off between tight synchronization and signaling overhead. Depending on the importance accorded by the operator to the accuracy of the cache synchronization, the mapping distribution between to the ITRs can be performed with a reliable protocol (i.e., TCP) or not. In addition, batching of synchronization messages can be used to reduce the number of exchanged synchronization messages. Moreover, when the network allows it, the mappings can be distributed by using IP multicast.

Conclusion and Further Work

In this paper, we propose a thorough study of failure protection and recovery in the context of the Locator/Identifier Separation Protocol (LISP) and propose a local failure protection mechanism for Ingress Tunnel Routers (ITRs). We first showed that ITR failures can indeed have large disruptive impact on ongoing traffic. Then, we explored how to minimize packet losses due to cache-misses caused by the redirected traffic on the alternate ITRs. Our proposal synchronizes the cache of set of ITRs in order to avoid such a phenomena. We thoroughly evaluate our proposal, showing that the load increase due to the synchronization is acceptable and suppresses the loss of packets upon ITRs failure/recovery.

Our ongoing work is aiming at extending the synchronization mechanism to ETRs and developing detailed specifications for implementation and experimentation in the lisp4.net testbed.

Fig. 1 :

 1 Fig. 1: LISP deployment example.

Fig. 2 :Fig. 3 :

 23 Fig. 2: Distribution of the number of border routers per BGP prefix.

Fig. 4 :Fig. 5 :Fig. 6 :

 456 Fig. 4: Cache size without synchronization (ISP).

Fig. 7 :Fig. 8 :

 78 Fig. 7: Cache-miss on ITR 2 after boot.

Fig. 9 :

 9 Fig. 9: Number of used ITRs per EID routers.

Table 1 :

 1 Increase of cache size and misses due to ITR failure.

		Failure Increase	Increase * Network
	Entries (avg.)	ITR1 55.54% ITR1 20.57% ITR2 68.54% ITR2 63.93%	46.59% Campus 20.30% ISP 56.98% Campus 56.54% ISP
	Misses (avg.)	ITR1 40.32% ITR1 17.02% ITR2 52.46% ITR2 67.14%	55.25% Campus 28.22% ISP 72.95% Campus 96.34% ISP
	* Increase without counting the 5 min.
	transient period right after failure

Table 2 :

 2 Topologies characteristics.

	Name Routers Links
	TIER1a 500 + 2,000 +
	TIER1b 200 + 800 +
	ISPa	50 +	200 +
	ISPb	20 +	60 +
	UCL	11	41
	NREN	30 +	70 +
	Internet2	11	30
	Géant	22	72

The proposed solution does not rely on any mapping system, hence their description is out of scope. Jakab et al.[START_REF] Jakab | LISP-TREE: A DNS Hierarchy to Support the LISP Mapping System[END_REF] propose a comparison of different mapping systems.

LISP does not specify any action for packets causing misses, which cannot be encapsulated due to the missing mappings. Current implementations, similarly to the case of missing MAC address in the ARP table, for scalability reasons drop the packet.

Acknowledgements. This work was partially supported by a Cisco URP grant. The research leading to these results has received funding from the French National Research Agency under grant agreement n • ANR-11-EITS-007-01. We would like to thank Simon van der Linden for his help.