s2fieldsofstudy:
Computer Science
Business

text:
Analysis of IPv6 Transition Technologies

Currently IPv6 is extremely popular with companies, organizations and Internet service providers (ISP) due to the limitations of IPv4. In order to prevent an abrupt change from IPv4 to IPv6, three mechanisms will be used to provide a smooth transition from IPv4 to IPv6 with minimum effect on the network. These mechanisms are Dual-Stack, Tunnel and Translation. This research will shed the light on IPv4 and IPv6 and assess the automatic and manual transition strategies of the IPv6 by comparing their performances in order to show how the transition strategy affects network behaviour. The experiment will be executed using OPNET Modeler that simulates a network containing a Wide Area Network (WAN), a Local Area Network (LAN), hosts and servers. The results will be presented in graphs and tables, with further explanation. The experiment will use different measurements such as throughput, latency (delay), queuing delay, and TCP delay.

INTRODUCTION
The connection between computing nodes requires a protocol, number or a name, in order for each node to be recognized, and for the source and destination of each packet to be known. The Internet depends on protocol that is known as Internet Protocol version 4 (IPv4), which uses Classless Interdomain Routing (CIDR) and 32 bit: this protocol can cover 4.3 billion nodes around the world. Because the technology is developing, and many different services and devices use 3G and 4G, IPv4 is approaching its limit: there is not enough IPs available from internet service providers (ISP) to meet customer demand. Therefore, the new version of IP is critical in maintaining the pace of the Internet's development as shown in the picture below. IPv6, developed by IETF, is considered more efficient than IPv4 in relation to scalability, reliability, speed and security. Moreover, the size is larger than IPv4, as it uses 128 bit that will be able to encompass all of the nodes and any services that might require the IP, both now and in the future. Countries such as China, India and Japan have begun to use the next generation IP [1].
IPv6 can cover 340 trillion, trillion, trillion nodes whereas IPv4 is only capable of 4.3 billion nodes. This will contribute to building the necessary infrastructure for future development. IPv6 will not require NAT as IPv4 does, as security will be built in. IPv4 used NAT as security, but its function is not primarily for security. The flow control provides high priority for specific traffic to avoid congestion, and the connection with IPv6 will be as end to end. In addition, the IPv6 header is simpler than IPv4. It contains fewer fields which helps data to be processed faster, which will in turn be reflected in a higher performance. One of the fields which will not be included with IPv6 is the CRC, because the packet is already checked at a lower layer, and therefore is not required to be checked for errors in an upper layer. Consequently the process time will be decreased. The transition from IPv4 to IPv6 requires a smooth method without any disconnection or fault within the network. This requires an efficient management and upgrading of the nodes, devices and operation systems in order to be able to understand the new IP generation.

UNDERSTANDING IPV4 AND IPV6
The communication evaluation identifies IPv4 as being limited in not only the addresses available for customers but also in the services that consumers need to access the applications. The new version (IPv6) is found to have solved these issues of IPv4 by extending the size of the network in order to accommodate more customers; it is also easier to reconfigure addresses. IPv6 also provides a higher performance, particularly during real time traffic, which requires quality of service (QoS), and the overall processing time is reduced. Moreover, the new version is able to provide what is required for future development of an infrastructure. Security is also an important consideration, as the internet is used by many different applications to transfer data; security is implemented with the IPv6. In addition, mobility is supported.

IPv4
IPv4 is considered the core of internet addressing, as it allows transmission of data using TCP/IP. In previous years, this protocol proved its stability and reliability in working in the internet environment in order to provide a connection for millions of nodes. Figure 1 shows the five classes of IPv4 address. IPv4 was launched in the 1980s. After a small period of time, this protocol started to be exhausted; this led to the use of class inter domain routing (CIDR); however, this did not provide a long-term solution due to the rapidly increased use of the Internet. Some sources expected it to be exhausted in 2010 or 2012, which was a primary reason to develop a new version that was able to accommodate more consumers.
IPv4 contains 32 bits. It can cover 4.3 billion addresses. The address is represented as 192.168.2.1. Each colon can be from 0 to 255. In general, IPv4 contains five classes. Each class provides different limits to the address numbers for networks and hosts; the figure 2 shows the types of addresses and their range.

IPv6
IPv6 is also known as IP next generation: it is considered evolutionary from IPv4, as it does not make a radical change to IPv4 and the basic concept remains the same, but some features have been added, which help to improve performance and provide a good service for customers. In IPv6, the NAT was eliminated, which is considered an advantage. Moreover, the configuration is easier with IPv6 as it can be done stateless (auto configuration). The IP address is a combination of the MAC address for the interface and the prefix from the router; in general the DHCP is not used, but it can be used with DNS. The IPv6 size is 128 bits, comprised of Hexadecimal digits which are able to provide 3.8X10 38 addresses, which are enough to give a unique address to each device for today and the future. Each four digits are separated by a colon which provides eight parts; the zeroes can be omitted to make the address smaller as shown in figure 2 [2]. IPv6 makes the global routing simpler than IPv4. There is less effect on resources and memory, which helps to improve performance and be more efficient. The security is provided end to end by encryption, which is integrated within IPV6.
The traffic in IPv4 can be unicast, multicast or broadcast. With IPV6 the broadcast is no longer available because of its high consumption of resources. However, a broadcast can be sent from within a multicast.
1. Unicast Addressing: the unicast is to send the packet for a unique address (for one destination). 2. Multicast Addressing: the multicast addressing is to send the packet for a group of addresses. The IPv6 use the ff00::/8 as a prefix for multicast. The type of addressing use two protocols to know which IPs in the same group for multicast there are Multicast Listening Discovery protocol (MLD) and MLDv2. 3. Anycast Addressing: when there are many similar destinations in different areas the unicast use to send the packets to the closet destination from the sender [3].

Header
The IPV6 header is quite different from IPv4. Although IPv6 has abolished some fields it is still bigger than IPv4; however, it is more efficient than IPv4. The picture below shows the two headers and the differences between them. For example, the CRC is no longer necessary as the packet is already checked from a lower layer so there is no reason to check it again, which makes overheads on processing and loses time. Figures 3 and 4 show the differences header for IPv4 and IPv6. The IPv6 header is bigger than IPv4: IPv6 is 40 bytes while IPv4 is 20 bytes; this is how the IPv6 address is bigger than in IPv4. The version field detects which type of header it is: if it is 6 then the IP is IPv6, and if it is 4 that mean that it is IPv4. Traffic class determines the priority for traffic, which varies from 0 to 7: traffic class length is 8 bits and it is used to reduce traffic congestion as much as possible. The quality of service is provided by the flow label, which is 20 bits; when the traffic reaches the router this field provide a mechanism to process the traffic. Payload length, which is 16 bits, is used to detect the length of data and is able to transfer up to 64 Kbytes. The extension header will be used when the data exceeds 64 Kbytes, as it is 32 bits: the extension header therefore is capable of providing 4.3 million bytes. The type of extension header used is detected by the Next Header field. Hop limit is similar to TTL in IPv4: it is decreased after each hop until it reaches zero, and then it is discarded. The source and destination are each 16 bytes, which enables them to provide a long address [4].
Overall the IPv6 provides solutions for weakness in IPv4, such as address exhaustion: IPv6 provides addresses with 128 bit, there are no private addresses, and the transmission of data is end to end. IPv4 depends on manual or dynamic host configuration for addressing, whereas IPv6 uses auto configuration: the configuration is done automatically without the need to send a query and wait for a response from the DHCP server. The security with IPv4 is optional, so data transferred over the Internet could be hacked; IPv6, however, has IPsec in-built so that data is encrypted. IPv4 is limited in real time traffic despite using type of service (TOS) whereas IPv6 supports real time traffic by using Traffic Class and Flow Label. The routing table in IPv4 is large in comparison to IPv6. IPv6 uses the same home IP for excellent mobility, even when outside the home and it can use neighbour discovery and auto configuration when moving from one link to another [5].

TRANSITION STRATEGIES
Transition strategies are methods that provide a means of connection between IPv4 and IPv6, as these two protocols cannot understand each other. Therefore, in order to transfer data, a special method is needed. The three strategies are: • Dual-Stack: This method is used to understand simultaneously IPv4 and IPv6: regardless of which protocol is used, when the traffic is received the node is able to respond. • Tunnel: This strategy is employed when there are two networks that are using the same IP version but are separated by another network that has a different IP. The tunnel method establishes a virtual link through the networks by providing a connection in the middle of them. • Translation: This method is similar to NAT, as it changes the IP packet from IPv4 to IPv6 and vice versa, depending on the source and the destination [6].

Dual-Stack
The Dual Stack technique uses IPv4 and IPv6 within the same stack in parallel. The choice of protocol is decided by the administrator policies, along with what kind of service is required and which type of network is used. This technology does not make any change to the packet header and at the same time does not make encapsulation between IPv4 and IPv6. This technology is known as native dual stack or Dual IP layer [7]. According to [8], the Internet contains nodes and these nodes are able to support both protocols in parallel within the same infrastructure. Therefore, the node can provide the transmission of data for IPv4 and IPv6. This technique is not suitable for large networks like the Internet because it is difficult and expensive to cover all the nodes in such huge networks. On the other hand, it is suitable for small networks, which need less management and are easy to control. The dual stack is considered to be the basis for inventing the two other techniques for transition between IPv4 and IPv6

Tunneling
Tunneling could be either manual or automatic. The connection for the manual is a point to point mode which is assigned the source and the destination address of the tunnel by the operator while the automatic connection is a point to multipoint where the source address is assigned by the operator and the destination address is found automatically. The tunnel idea works as a bridge to transfer packets between two similar networks over incompatible network [7]. In other words, the IPv6 will be as a part of IPv4, and the IPv6 data will flow by using IPv4 infrastructure, which will send it to the destination (IPv6) for processing; the tunnel is a virtual link between the two points to transfer data [9].

Manual Tunnel
The manual tunnel provides a connection between the IPv6 networks over the IPv4 network as a static point-to-point tunnel. The IPv4 and IPv6 are manually assigned as the source and destination. This strategy provides a secure connection between two ends [10].

Automatic Tunnel
There are different types of automatic tunnels as follows.

Tunnel Broker
The dual stack is important for a tunnel broker, so that a tunnel for the hosts in the IPv4 network only can be built. The web server is required to build the tunnel because the user should be connected to a web server and apply certain authentication details (such as the IP address, operating system and IPv6 support software) and the replay will be a short script; now the IPv4 to IPv6 tunnel is ready to use. The tunnel broker is considered to be an automatic configuration service and it will configure the end point for the network side, the DNS server and the end user [11]. The tunnel broker contains different parts: the first is the tunnel broker (TB), which sends instructions between the server and DNS. Additionally, the TB works as a tunnel monitor, and if the tunnel is down it can use other tunnels which are already in existence in the tunnel group. The second is the tunnel server (TS), which should have at least three IPv6, an IPv4 unicast, and an anycast: these are used for routing, accessibility, and endpoint for the user respectively. Third is the tunnel server group (TSG), which uses the IPv4 anycast to divide the tunnel servers into tunnel server groups, all of which have the same IPv4 anycast address. This makes tunnel work more efficient as the user's request will be sent to the nearest tunnel, and if there is any issue with the connection another tunnel will take over and generate the connection. The fourth part is the DNS system (DNS), where each user has a domain name and the mappings are done by the DNS system. This requires the user to register to access the tunnel, and then the user will obtain an IPv6 address; at the end, the communication is carried out by a website such as http://gogo6.com/ by using HTTP protocol [12], figure 6 shows the tunnel broker mechanism.

6to4
6to4 is a technique that is able to connect IPv6 domains that are separated by an IPv4 network. The IPv4 network acts as a link between the IPv6 networks. 6to4 is an automatic tunnel. It uses the IPv4 infrastructure to transfer the IPv6 packet. Therefore, the IPv4 address is part of the IPv6 address during the transferring of the packets until they reach the other side of the tunnel [11]. The IPv6 networks are connected together using the 6to4 router with the prefix 2002: IPv4 address::/48. The IPv4 address (32 bit) is the 6to4 router address. The IPv6 destination will extract the encapsulation address. In addition to connecting the IPv6 network with the IPv6 Internet through the IPv4 network, the prefix is the same and the 6to4 router will encapsulate the IPv4 destination for the 6to4 relay router, as shown in figure 7, there are two IPv6 hosts isolated by the IPv4 network; the tunneling used by IPv6 to deliver data through IPv4 [9].

6over4
The 6over4 is an automatic technique for providing an approach to IPv6 nodes that exist within a pool of IPv4 networks. These IPv6 nodes are not directly connected to each other; so this technique will create a virtual link to provide a way for the IPv6 nodes to communicate [11]. The virtual link was created by IPv4 Multicast; it is represented by Ethernet with IPv6 and Multicast with IPv4. Therefore, the IPv4 infrastructure should be fully supported by IPv4 to provide the virtual link to all the IPv6 nodes. There are two important protocols to use with this technique, SLAAC and ND, the latter of which causes a security issue because the ND message might be attacked [8].

ISATAP (Intra-Site Automatic Tunnel Addressing Protocol)
ISATAP is another mechanism for enabling communication between IPv6 and IPv4 using the tunneling technique. It is used to link the local IPv6 address with the prefix fe80::5efe/96, which is followed by the IPv4 32 bit. ISATAP can build more than one gateway, which is used as a tunnel for IPv6 to access ISATAP hosts [8].
ISTAP is an automatic tunnel and it is point to point connection. The addressing is dependent on embedding strategy; the IPv6 address will be within an IPv4 address. The ISATAP tunnel is able to provide a connection between IPv6 and IPv4 routers: at the beginning of the connection the host within ISTAP will get an address called a local ISATAP address and will detect the next hop of the ISATAP router. The packets will then be sent by the tunnel after embedding the IPv6 address into an IPv4 address. At the destination the IPv4 header will be removed and the packet is sent to the IPv6 server; there the server sends the packets to the ISATAP network and finally the ISATAP router prepares the IPv6 packets into IPv4 and sends them to the ISATAP host, which will then remove the IPv4 header and extract the IPv6 packets [13]. Figure 8 shows the ISATAP mechanism.

Translation
The translation technology changes the header and the payload of the IP from version 4 to version 6 and vice versa. There are two ways for translation: stateless and stateful. The stateless translation, there is no reference for the pervious packet during the conversion while the stateful translation is related with the previous packets [7].

SIIT (Stateless IP/ICMP Translation)
The translation is executed with the header between IPv4 and IPv6. During the translation the information might be lost and NAT (network address translation) is required; therefore this technique is not recommended [14].The SIIT technique requires each IPv6 host to have an assigned IPv4 address. There are two types of addressing: one is known as IPv4-translated address for the IPv6 host, where the IPv6 address is generated by adding the prefix 0:ffff:0:0:0/96 before the IPv4 address; the second type is known as IPv4-mapped address for the IPv4 host, and the IPv6 is generated by adding ::ffff:0:0/96 before the IPv4 address. The translation operation is as follows: the IPv4 packet is translated to IPv6, the source will take the prefix ::ffff:0:0/96 and the destination will take the prefix 0:ffff:0:0:0/96 and remove it from the original. The DNS is vital in knowing the addresses; the local DNS server helps the IPv6 host to learn the IPv4 mapped address in order to get 'AAAA' record from 'A' record by using DNS64.
Moreover, the IPv4 record is registered within IPv6 hosts to answer the heterogeneous query and there is no security issue added for the network by the SIIT technique; also the DHCPv6 and the SLAA can be used to assign the IPv6 addresses for the host. This type is a stateless translation [8].

NAT-PT (Network Address Translation--Protocol Translation)
The communication between native IPv6 and native IPv4 could be obtained by using NAT-PT. This mechanism has a pool of global IPv4 and IPv6 prefix with length of 96 bits. The translation will be created by assigning the IPv6 with the IPv4 address pool through NAT-PT gateway [6]. This mechanism does not require extra Applications or depend on another mechanism, such as dual stack, but it requires interoperability with the core network for easy and fast management [11].
The prefix ::/96 will be used to generate a new address. To translate from IPv6 to IPv4, the IPv4 source will be created from the source of IPv6 and the port is found by looking it up in the NAT binding table; the destination IPv4 is created by removing the prefix. To translate from IPv4 to IPv6 the prefix will be added to the IPv4 source address to create an IPv6 source, and the destination address is generated by using the destination IPv4 address and the port looked up in the NAT binding table. To avoid the problems that are generated by building the binding map, the heterogeneous addressing will use the DNS ALG on the translator. This will assist in converting the A to AAAA query in two-way to generate a stateful binding between IPv6 and IPv4 addressing IPv4 by using the pool of addressing [8].

BIS (Bump in the stack) and BIA (Bump in the API)
Both BIA and BIS are stateful translations. These two mechanisms are used to solve a problem when an application in IPv4 wants to communicate with a remote IPv6 host through an IPv6 network; this strategy depends on tricking the application using IPv4 to assume that the remote host is IPv4 as well. This technique is built by software and inserted inside the host. The security is lax enough for a DOS attack on the DNS query: by exhausting the pool of IPv4 addresses, the binding table will be full [8]

Bump in the stack (BIS)
BIS uses the translation as per packet: the translation executes the operation by generating the source address from the host and the destination from the binding table with an IPv4 destination address. When the packet reaches the host, the translator translates the packet to IPv4 and the source address is taken from the binding table with the IPv6 source address and the destination from the host IPv4 address, as shown in figure 10 [8].
. Figure 10. BIS [8] The translation between IPv4 and IPv6 is done by injection BIS in the dual stack for the host and the IPv4 is detected to the IPv6 [15].

Bump in the API (BIA)
BIA is similar to BIS; with BIA the translator translates between IPv4 APIs and IPv6 APIs. The name resolver and address mapper are the same as in BIS, and the function mapper is responsible for the translation. The translation will be done without the IP header so that the security will not break down between end and end.

IPV6 DEPLOYMENT
To start using IPv6 over a network the equipment such as router, switches firewalls and servers should be supported by IPv6, and then the transition may begin. Generally, the migration will take time; however many countries today began to use IPv6 side by side with IPv4.

OPNET MODELER
The Optimized Network Engineering Tools (OPNET) Modeler is an efficient way to provide a complete study for the network analysis. The graphical user interface (GUI) is simple to use and the result is shown as graphical and static. Furthermore, it does not require a programing knowledge, and this can be easily used. The Opnet analyses the network as a real life network which gives a complete view before building the network in a real life and also contains a library of protocols and models which can be used as examples [18].
There are four simulation technologies supported by Opnet:

Discrete-event Simulation (DES):
The DES provides a simulation in the same way as a real network; it will assist the study by analyzing the performance and behavior of the protocols and packets.
Hybrid Simulation: Hybrid simulations supported by DES, the results depend on analysis and the DES to be accurate; by using the two, accurate results can be generated with reasonable runtimes.
Flow Analysis: Analytical techniques and algorithm are used with flow analysis. It uses detailed configuration information to recreate the routing table for the device to ensure high efficiency. Flow analysis is used to study and understand the routing and reachability throughout the network.

ACE Quickpredict:
The bandwidths, packet loss and latency impact time will be studied by ACE quick predict, which is supported within the OPNET Application Characterization Environment (ACE) [19]. Figure 11 shows the options for the Opnet simulation Figure 11. Opnet Simulation technology options

SIMULATION EXPERIMENT
This experiment will be conducted using the Opnet Modeler 17.5 for simulation. Opnet was chosen as it is considered as highly efficient simulation software and will be appropriate in reaching the goal of the experiment. It also includes most of the network technology such as routers and switches, as well as other equipment such as the filters, which help to analyses the traffic. The experiment consists of different stages: firstly, the network model is created; secondly, the most suitable statistical analysis is detected; thirdly, the simulation is run in order to obtain results; fourthly, the results are analyzed and compared to each other, and finally a report is written to discuss the results. .
The experiment will show the performance of two types of IPv6 transitions (6to4 and manual) and both of them will be compared with IPv4 and IPv6 traffic. The two transition technologies will provide the connection for two IPv6 sites that are isolated by an IPv4 network. The design includes a LAN, which contains 100 users that are connected by four switching devices using 100 base T cable. The Dual-Stack router (the router in the middle of the two networks) has two interfaces, one connected to the LAN by 100 Base T cable and the other to an IPv4 network by a PPPDS3 cable. The IPv4 network contains five routers connected with each other by 100 Base T links. The other side consists of the IPv6 network including a web server; the web server connection can be used for heavy browsing. This experiment will show how 6to4 and manual tunnel can be used to provide a connection for an IPv6 isolated by an IPv4. The routing protocol is RIP for IPv4 and RIPng for IPv6. The OSPFv3 is not compatible with the 6to4 tunnel. In addition, the experiment network topology is designed to be easy to understand and explains how the transition works. Moreover, the results will show the network behavior, which can be analyzed and compared with IPv4 and IPv6.

METHODS USED
The network is implemented by using different network materials such as switches, routers, LAN and servers as shown in figure 12. From the object palette one can choose the equipment and connect them together.
After the network implementation, start to configure the attributes for IPv6, IPv4, Dual-Stack, Manual and 6to4. The IPv4 and IPv6 they do not require any special configuration; just a normal configuration by assigning all interfaces IPv4 address for IPv4 network and IPv6 addresses for IPv6 network. The Dual-Stack as well is just required for each interface to add both IPs version 4 and version 6 together that is for servers and routers. The LAN setting can be configured by right clicking on the LAN icon and choosing "edit attributes." Extend "IP" and then "IP Host Parameters." IPv4 is assigned by putting its IP address in "Address" and then putting the mask in "subnet" mask. These steps should be followed again for each LAN. The router setting is edited by clicking on "IP Routing Parameter" and from there "Interface Information." There, IP addresses for 12 ports for IPv4 can be assigned, and IPv6 addresses may also be added by clicking on "IPv6 Parameter". The numbers of ports depend on the number of addresses. Change the "not active" to "Default EUI-64" and assign the IPv6 to the network. The switch does not require any configuration, and it is important to choose the right cable with the right equipment. All nodes are connected together by 100 base T cables and the edge routers connect to the IPv4 backbone by PPP_DS3 cable.
There are two important factors that should be configured to establish the traffic when designing the network. First "Application" is used to decide which application is required for the network, by choosing it from the "Object Palette" and right clicking to extend the "Application Definitions." From the "Number of Rows" choose the number of applications that will apply for the network; in this experiment it is one (web server). The service types are assigned in "Application Definitions," and this information is relayed back to the server. The server can then decide which services will be applied to the network. The "Description" field gives the choice as to what type of service and the value; for this experiment the choice is HTTP and the value is heavy browsing, which includes videos and images. "Profile" is used to detect the properties for each application: "Application" is binding with the server and "Profile" is binding with the host.
The Opnet Modeler provides many statistics which can be used to measure the network, which assists in understanding network behavior. The table 1 give examples of these measurements include: The required time to get an acknowledgement from the application. Throughput Represents the successful transmission of packets between two nodes. Traffic Receiver (byte/sec): Calculates the average bytes per second sent from client to server Traffic received (packet/sec): Calculates the number of packets by getting the average throughput of the packets sent from the client to the server. Traffic Sent (byte/sec): Is the average number of bytes assigned to the client by the server. Traffic Sent (packet/sec): Is the average number of packets assigned by the server to the client per second.

Ethernet Delay
Calculates the end-to-end delay between devices. Utilization Shows the percentage of consumption delay for packet forwarding and processing.

6to4 Tunneling
To create a 6to4 tunnel, the IPv4 address is embedded between the middle router and the IPv4 with the IPv6 6to4 prefix address (2002:ipv4 address-with the edge router::/48). The middle router should be a dual stack router to support both versions of IPs and is considered the transport gate to the other site. The tunnel configuration is done from the "IP Routing Parameters." Choose the "Tunnel Interface," and from "Tunnel Information" detect the source, which is the interface that connects to the IPv4 network (Tunnel Source). From "Tunnel Mode" detect the tunnel type: for this experiment the tunnel type is 6to4. To assign the tunnel address choose "Tunnel Interface" from "IPv6 Parameters", extend the row for however many tunnels there are, and then assign the IP address that is the IP address for the tunnel. For the other site it is the same configuration but with different IPs. Table 2 shows the configurations for 6to4 tunnel; The tunnel is now ready to transfer packets through the IPv4 network.

IPv6 Manual Tunnel
The manual tunnel is not too different from the 6to4; the idea is similar, but for the tunnel mode choose IPv6 (Manual). The source is the interface with central edge router that connects to the IPv4 network, and the destination is the interface for the IPv6 on the other side (across the IPv4 network). The configuration is similar on the other side but notice the difference for IPs: manual strategy uses 2001 instead of 2002 for 6to4. Also, manual requires the source and destination for the tunnel as it works point-to-point, unlike 6to4 which works as point-to-multipoint. Table 3 shows the configurations for the manual tunnel.

RESULTS AND DISCUSSION
The simulation ran for 5min (300 sec): this time is enough to gain an overview of the behavior of the network. Figure 13 shows the LAN TCP delay within the web server: 6to4 is represented by green, manual transition by red, blue for the IPv4, and purple for IPv6. Figure 13. TCP network delay

Delay
The TCP delay occurred in the transport layer; the transport layer could use UDP or TCP protocol, as the connection with the web server requires a TCP connection. The transport layer is responsible for the connection between end to end and for the flow packets, so when delay occurs it is found in this layer. As seen from the graph, IPv6 and IPv4 have shorter delays than the transition strategies. Moreover, the delay occurs because of the congestion in the network. This network includes a LAN of 100 hosts; at the same time as the transmission was underway, each host was browsing, including accessing large images and long videos, which generated a high numbers of packets travelling inside the network and it is this which caused the congestion to occur. As previously discussed, the simulation programmer creates traffic by sending the same request from the server to the 100 hosts at the same time. This traffic causes congestion and therefore the delay is appears; after the requests are sent, the windowing is decreased, which therefore decreases the traffic flow and therefore minimizes delay.
In addition, the transition technologies caused further delay, because when the packets reached the middle router (between the IPv4 network and the IPv6 network), the packets transferred through the tunnel. This required the IPv6 packet to be encapsulated into Ipv4 in order for them to transfer through the IPv4 infrastructure. When they reached the other side these packets were decapsulated and transferred to the destination server; the time between capsulation and decapsulation generated additional delays. Moreover, the transition technologies generated additional size to their packets (20 byte adds more than the original size). In addition, when the queue was full there was not enough space for the new packets; this generated drop packets and, as TCP is a reliable connection, when packets are dropped, TCP will retransmit the dropped packets. There are many factors that generate congestion, such as: • Queuing delay: The packets arriving at the switch or the router will wait in the queue for processing and the waiting time will create a delay. Figure 14 shows the point to point delay between the dual stack router (middle router between two networks) and the IPv6 switch site. The queue delay increases with time because as the packets begin to reach the queue router and await their turn for processing, more packets are arriving: when the queue is full this will affect the network's throughput as the number of packets that are successfully arriving at their destination is decreasing. The figure shows IPv4 has less queue delay because the packet size is smaller than other types. As seen in the figure, the IPv4 and IPv6 have the lowest delay, because the processing time for the router is faster than for manual and 6to4 strategies. In addition, IPv4 has lees queue than IPv6 because the packet size for IPv4 less than IPv6.
• CPU Utilizations: The router contains a CPU, and the usage becomes extremely high when there is a high level of traffic that needs to be processed quickly. The manual and 6to4 transitions generate more pressure on the CPU than IPv4, IPv6 and Dual-Stack because the 6to4 and manual required the encapsulation and De capsulation operations on each packet cross from IPv6 to Ipv4 and vice versa; figure 15 shows the effect of the five phases on the router. In general, the CPU utilization represents the percent of CPU time spent in processing traffic (Chen, Chang, Lin, 2004).  Figure 16 shows the responses times for each phase. The response times for IPv4, IPv6 and Dual-Stack are less than those of 6to4 and manual as they generated less overhead on the router and therefore the processing time is faster. The manual transition had a slower response time than 6to4, which is why the TCP delay is higher. Towards the end, congestion was generating the delay. For example, if there are 1000 packets that require 1 second to transmit in a normal situation with congestion the time needed can at least double, due to each packet needing to wait for a longer period of time, especially with TCP because of its reliability. The table 4 shows the difference in delays between IPv4, IPv6, manual and 6to4 tunneling. Table 4 shows the average network performances

Throughput
Throughput is the rate of transferring data through a network and is calculated using bits per second. The table shows the throughput between the LAN, which contains 100 users, and a FTP server. There are three data rates for this test: 1Mbps, 2 Mbps and 5 Mbps. The IPv6 had a higher throughput due to its larger packet size in comparison to the others; this enabled it to transfer more data. The second better throughput is for manual tunnel for 1 and 2 Mbps. With 5 Mbps the 6to4 got higher throughput than the others, except IPv6. Manual tunnel is point to point connection, which meant that the data travelled immediately from source to destination (which is also considered preferable for security reasons). In general, the throughput is increasing when the data rate is increased. Table 5 measure the throughput by using 1, 2 and 5 Mbps.

CONCLUSION
In the previous years IPv4 has proven its worth in providing sufficient addresses for the Internet. When the Internet continued to expand, it began to approach IPv4's limit in providing different services and applications. Therefore, a new version of IP (namely IPv6) was developed in order to cater to all users' requirements. In this paper, some networks were designed and simulated by using Opnet Modeler to study different translation schemes. The design contained different network devices in order to capture a real network environment. The network topology was configured in five phases as -IPv4, IPv6, Dual-Stack, 6to4, and manual tunnel. The statistical analysis was done to provide suitable results and to show that the network's performance varied across different mechanisms. For example, the CPU utilization for manual and 6to4 is higher than IPv6, IPv4 and Dual-Stack because the transition technology generates more effort to encapsulate and decapsulate. The Dual-Stack found less delay with TCP, but with 6to4 and manual the delay is higher because the packets are not transferred directly, as usual. The throughputs of the four network simulations were analyzed by using three different data rates: 1, 2 and 5 Mbps. The results show that IPv6 has higher throughput than the other four, and for manual it is higher than 6to4 till 5 Mbps. The 6to4 and manual strategies required manual configurations to detect the source, and the manual tunnel is required to have the destination detected in order to build the point to point mechanism.


extfieldsofstudy:
Computer Science
Physics

text:
Capturing collective conflict dynamics with sparse social circuits

We discuss a set of computational techniques, called Inductive Game Theory, for extracting strategic decision-making rules from time series data and constructing probabilistic social circuits. We construct these circuits by connecting component individuals and groups with strategies in a game and propose an inductive approach to reconstructing the edges. We demonstrate this approach with conflict behavior in a society of pigtailed macaques by identifying significant patterns in decision-making by individuals. With the constructed circuit, we then capture macroscopic features of the system that were not specified in the construction of the initial circuit, providing a mapping between individual level behaviors to collective behaviors over the scale of the group. We extend on previous work in Inductive Game Theory by more efficiently searching the space of possible strategies by grouping individuals into socially relevant sets to produce a more efficient, parsimonious specification of the underlying interactions between components. We discuss how we reduce the dimensionality of these circuits using coarse-graining or compression to build cognitive effective theories for collective behavior.

INTRODUCTION
A central problem in the study of collective behavior is how functionally significant macroscopic properties arise out of individual or microscopic interactions. The most common approach to studying the relationship between the micro and macro in biological systems is dynamical systems and pattern formation (for examples, see Sumpter, 2006;Ball, 2009;Couzin, 2009;Payne et al., 2013). A complementary approach is to treat the micro to macro mapping explicitly as a computation.
A macroscopic property can be said to be an output of a computation if it can take on values that have functional consequences at the group or component level, is the result of a distributed and coordinated sequence of component interactions under the operation of a strategy set, and is a stable output of input values that converges (terminates) in biologically relevant time  .
The input to the computation is the set of elements implementing the rules or strategies. The input plus the strategies constitute the system's microscopic behavior. My collaborators and I have developed novel computational techniques, called Inductive Game Theory ] Krakauer 2011][Lee et al. 2014], to extract strategic decision-making rules from correlations observed in the time series data and reconstruct the microscopic behavior.
In biological systems, there are typically multiple components interacting. Hence the computation of the macroscopic output is inherently collective, meaning we must examine how different configurations of strategies affect the macroscopic output ]. We describe the space of microscopic configurations using Markovian, probabilistic, "social" circuits ] Krakauer 2011][Lee et al. 2014].
Here, we briefly illustrate this approach using time series data collected on conflict dynamics from an animal society model system-a large, captive group of captive pigtailed macaques (Macaca nemestrina) (n = 47). We start with very simple time series data on which individuals were present in a conflict. This gives us a time series of binary fight participation vectors. Given this input of individual identities, our output is the distribution of fight sizes, which has been shown to have functional consequences for individuals in the study system ]. We ask whether individuals decide to join fights based on participation in the last fight (say between their allies and adversaries), what are their decision-making strategies, and how do these strategies collectively produce the distribution of fight sizes?

STRATEGY EXTRACTION AND CIRCUIT CONSTRUCTION
We begin by defining a space of strategies. Since we are interested in how individuals join fights and have limited a priori our input data to identity of fight participants, we can represent this space of strategies as c(n, m), where m-tuplet of individuals in the fight at time t is determined by the behavior of an n-tuplet of individuals in the fight at time t − 1 [DeDeo et al. 2010]. We restrict the C(n, m) 1:2 • ED Lee, BC Daniels, DC Krakauer and JC Flack space we explore to C(1, 1), C(2, 1), and C(1, 2) the simplest strategies in the space as cognitive and behavioral data indicate that the macaques are capable of using these strategies.
Choosing C(n, m) specifies the identity of the vertices between which can allow for strategic connections. The directed edges correspond to strategic information from m to n and we compute these as N (i) is the total number of events in which the n-tuplet i participated at all times t−1, and N (j t |i t−1 ) is the number of events in which the m-tuplet j participated at t given i in the previous event. N null is the average calculated over time permutations of the fights while maintaining the participation integrity of each event (e.g. we only shuffle the order of events; we do not shuffle participation).
The ∆P corresponds to a measurement of how often j follows i as a deviation from shuffle time series. Positive (negative) values indicate that j is more (less) likely to follow i than by chance. Since ∆P is normalized to −1 to 1, we interpret these values probabilistically where negative values correspond to a suggestion of strategic avoidance in the following fight.
We use the list of ∆P found for each C(n, m) strategy class to construct a social circuit for each strategy class. By modulating how we account for these causal relationships, we end up with multiple alternative circuits, or a family of circuits for each C(n, m) strategy class. Each circuit in the family is a model of the micro-macro relationship and so serves as a hypothesis for how strategies combine over nodes (inputs) to produce to the target output [Lee et al. 2014]. We test the circuits against each other in simulation to determine which can best recover the actual measured macroscopic behavior of our system and other fine grained statistics.
We find that (1) a variant of the C(2, 1) circuit, with the measured ∆P , captures some important features of the microscopic behavior of the system, (2) but that the distribution of fight sizes is degenerate over configurations of the C(2, 1) circuit parameter space. Although our analyses support the conclusion that the distribution of fight sizes results from the summed contributions of the ∆P in the C(2, 1) circuit, we note that the degeneracy of the distribution of fight sizes for C(2, 1) parameter space coupled to the observation that the C(2, 1) circuit is extremely complex with many precise, tiny parameters, suggests that the exact measured values of ∆P may not matter. A natural next step is to systematically reduce the dimensionality of the circuit. Our goal is two-fold: to find the a parsimonious description of the generative process that is also consistent with what we know about the information the monkeys use to make decisions-a cognitive effective theory.

SPARSE SOCIAL CIRCUIT CONSTRUCTION
Our approach is to compress the time series data to build a more compact circuit. Using a technique from neuroscience called sparse coding [Olshausen and Field 1997], we extract the individuals and subgroups that are regular and predictable conflict participants [Daniels et al. 2012]. We show an example from this process in Figure 3. Between these sparse groups, we search for ∆P strategies as specified in Eq 1, a space we denote as C(s i , s j ), where the sizes of groups 1 ≤ |s i |, |s i | ≤ 5. Consistent with previous results ], we find more significant C(2, 1) and less significant C(1, 1) strategies than would be expected from a null permutation of the data. On the other hand, we also find evidence for other strategy classes beyond the three explored in previous work.
Since we expect that important social groups in the data set constitute relevant features for strategy formation, we also allow for strategies of the form C(s i , 1), that is information that individuals use to form strategic decisions based on previous participation of a sparse group. Even with this addition, we have ∼12 sparse groups and so the number of strategic edges that can exist on this graph are several Capturing collective conflict dynamics with sparse social circuits • 1:3 orders smaller than the bipartite C(2, 1), a lesser cognitive burden on individuals who might use a similar model to predict conflict behavior.
Compared to other models that have been proposed for this system, the C(s i , s j &1) sparse circuit constitutes a comparatively reasonable fit despite being far more cognitively and computationally parsimonious in the number of possible strategies. Fig. 1. Example of sparse basis circuit obtained by sparse coding. Individuals in light blue circles are part of groups in dark blue. Individuals not in basis groups are green. For example, individual Vf is in a basis group alone. Eo and Ob appear in multiple different basis groups in this solution. We only show the top 15 largest ∆P significant with p ≤ 0.05; these are all positive. This circuit is simpler than the C(2, 1) network in so far as it has many fewer nodes and these nodes are composed of the regular and predictable individuals.

CONCLUSION
We have proposed an approach for reconstructing the microscopic, strategic behavior of components and individuals in social systems. This approach involves extracting component decision-making strategies from time series data on competitive interactions and constructing circuits that specify how these strategies combine to produce functionally important macroscopic properties that describe social structure.
With the exception of a few life history variables, it is not yet known what the important macroscopic properties are in biological and social systems. As we refine our understanding of the micro to macro mapping through construction of "full" circuits capturing the detailed microscopic behavior and prune these circuits to construct cognitive effective theories for the macroscopic output, we gain insight into the what properties of the time series data constitute the "right" input and hence the building blocks of our system. By investigating whether our most accurate, empirically justified circuits can also account for other potentially important macroscopic properties, we can begin to establish which macroscopic properties might be fundamental and what their relation is to one another, thereby moving towards a thermodynamics of biological collectives ].


Consistency of random forests

Random forests are a learning algorithm proposed by Breiman [Mach. Learn. 45 (2001) 5--32] that combines several randomized decision trees and aggregates their predictions by averaging. Despite its wide usage and outstanding practical performance, little is known about the mathematical properties of the procedure. This disparity between theory and practice originates in the difficulty to simultaneously analyze both the randomization process and the highly data-dependent tree structure. In the present paper, we take a step forward in forest exploration by proving a consistency result for Breiman's [Mach. Learn. 45 (2001) 5--32] original algorithm in the context of additive regression models. Our analysis also sheds an interesting light on how random forests can nicely adapt to sparsity. 1. Introduction. Random forests are an ensemble learning method for classification and regression that constructs a number of randomized decision trees during the training phase and predicts by averaging the results. Since its publication in the seminal paper of Breiman (2001), the procedure has become a major data analysis tool, that performs well in practice in comparison with many standard methods. What has greatly contributed to the popularity of forests is the fact that they can be applied to a wide range of prediction problems and have few parameters to tune. Aside from being simple to use, the method is generally recognized for its accuracy and its ability to deal with small sample sizes, high-dimensional feature spaces and complex data structures. The random forest methodology has been successfully involved in many practical problems, including air quality prediction (winning code of the EMC data science global hackathon in 2012, see http://www.kaggle.com/c/dsg-hackathon), chemoinformatics [Svetnik et al. (2003)], ecology [Prasad, Iverson and Liaw (2006), Cutler et al. (2007)], 3D

Introduction
Random forests are an ensemble learning method for classification and regression that constructs a number of randomized decision trees during the training phase and predicts by averaging the results. Since its publication in the seminal paper of Breiman (2001), the procedure has become a major data analysis tool, that performs well in practice in comparison with many standard methods. What has greatly contributed to the popularity of forests is the fact that they can be applied to a wide range of prediction problems and have few parameters to tune. Aside from being simple to use, the method is generally recognized for its accuracy and its ability to deal with small sample sizes, high-dimensional feature spaces, and complex data structures. The random forest methodology has been successfully involved in many practical problems, including air quality prediction (winning code of the EMC data science global hackathon in 2012, see http://www.kaggle.com/c/dsg-hackathon), chemoinformatics (Svetnik et al., 2003), ecology (Prasad et al., 2006;Cutler et al., 2007), 3D object recognition (Shotton et al., 2011), and bioinformatics (Díaz-Uriarte and de Andrés, 2006), just to name a few. In addition, many variations on the original algorithm have been proposed to improve the calculation time while maintaining good prediction accuracy (see, e.g., Geurts et al., 2006;Amaratunga et al., 2008). Breiman's forests have also been extended to quantile estimation (Meinshausen, 2006), survival analysis (Ishwaran et al., 2008), and ranking prediction (Clémençon et al., 2013).
On the theoretical side, the story is less conclusive and, regardless of their extensive use in practical settings, little is known about the mathematical properties of random forests. To date, most studies have concentrated on isolated parts or simplified versions of the procedure. The most celebrated theoretical result is that of Breiman (2001), which offers an upper bound on the generalization error of forests in terms of correlation and strength of the individual trees. This was followed by a technical note (Breiman, 2004), that focuses on a stylized version of the original algorithm. A critical step was subsequently taken by Lin and Jeon (2006), who established an interesting connection between random forests and a particular class of nearest neighbor predictors, further explored by Biau and Devroye (2010). In recent years, various theoretical studies (e.g., Biau et al., 2008;Ishwaran and Kogalur, 2010;Biau, 2012;Genuer, 2012;Zhu et al., 2012) have been performed, analyzing consistency of simplified models, and moving ever closer to practice. A recent attempt towards narrowing the gap between theory and practice is by Denil et al. (2013), where the first consistency result for online random forests is presented.
The difficulty to properly analyze random forests can be explained by the black-box nature of the procedure, which is actually a subtle combination of different components it is illusory to analyze separately. Among the forest essential ingredients, both bagging (Breiman, 1996) and the Classification And Regression Trees (CART)-split criterion (Breiman et al., 1984) play a critical role. Bagging (a contraction of bootstrap-aggregating) is a general aggregation scheme which proceeds by generating subsamples from the original data set, constructing a predictor from each resample, and deciding by averaging. It is one of the most effective computationally intensive procedures to improve on unstable estimates, especially for large, high-dimensional data sets where finding a good model in one step is impossible because of the complexity and scale of the problem (Bühlmann and Yu, 2002;Kleiner et al., 2012;Wager et al., 2013). On the other hand, the CART-split selection, originated from the most influential CART algorithm of Breiman et al. (1984), is used in the construction of the individual trees to choose the best cuts perpendicular to the axes. At each node of each tree, the best cut is selected by optimizing the CART-split criterion, based on the notion of Gini impurity (classification) and prediction squared error (regression).
Yet, while bagging and the CART-splitting scheme play a key role in the random forest mechanism, both are difficult to analyze, thereby explaining why theoretical studies have considered so far simplified versions of the original procedure. This is often done by simply ignoring the bagging step and by replacing the CART-split selection by a more elementary cut protocol. Besides, in Breiman's forests, each leaf (that is, a terminal node) of the individual trees contains a fixed pre-specified number of observations (usually small). Since this feature is hardly amenable to a rigorous mathematical investigation, most authors focus on a simplified, data-independent, stopping criterion. All in all, in these toy models, the forest construction is independent of the data, thus creating a gap between theory and practice. Motivated by the above discussion, we study in the present paper some asymptotic properties of Breiman's (2001) algorithm in the context of additive regression models. We prove the L 2 consistency of random forests, which gives a first basic theoretical guarantee of efficiency for this algorithm. Up to our knowledge, this is the first consistency result for Breiman's (2001) original procedure, since most of the previous studies focused on data-independent splitting criteria and cells containing a number of points growing to infinity with the sample size. Our approach rests upon a detailed analysis of the behavior of the cells generated by CART-split selection as the sample size grows. In fact, a good control of the regression function variation inside each cell, together with a proper choice of the resampling rate in bagging are sufficient to ensure the forest consistency in a L 2 sense. It also turns out that our analysis has interesting consequences for the understanding of the forest behavior in a sparse framework, that is, when the ambient dimension p is large but only a smaller number of coordinates carry out information.
The paper is organized as follows. In Section 2, we introduce some notation and describe the random forest method. The main asymptotic results are presented in Section 3 and further discussed in Section 4. Section 5 is devoted to the main proofs, and technical results are postponed to Section 6.

Random forests
The general framework is that of L 2 regression estimation, in which an input random vector X ∈ [0, 1] p is observed, and the goal is to predict the square integrable random response Y ∈ R by estimating the regression func- To this aim, we assume given a training sample D n = (X 1 , Y 1 ), . . . , (X n , Y n ) of [0, 1] p × R-valued independent random variables distributed as the prototype pair (X, Y ). The objective is to use the data set D n to construct an estimate m n : [0, 1] p → R of the function m. In this respect, we say that a regression function estimate m n is L 2 consistent if E[m n (X) − m(X)] 2 → 0 as n → ∞ (where the expectation is over X and D n ).
A random forest is a predictor consisting of a collection of M randomized regression trees. For the m-th tree in the family, the predicted value at the query point x is denoted by m n (x; Θ m , D n ), where Θ 1 , . . . , Θ M are independent random variables, distributed as a generic random variable Θ and independent of the sample D n . In practice, this variable is used to subsample the training set prior to the growing of individual trees and to select the successive candidate directions for splitting. The trees are combined to form the (finite) forest estimate Since in practice we can choose M as large as possible, we study in this paper the property of the infinite forest estimate obtained as the limit of the finite forest estimate when the number of trees M grows to infinity: where E Θ denotes expectation with respect to the random parameter Θ, conditionally on D n . This operation is justified by the law of large numbers, which asserts that, almost surely, conditionally on D n , (see the appendix in Breiman, 2001, for details). In the sequel, to lighten notation, we simply write m n (x) instead of m n (x; D n ).
In Breiman's (2001) original forests, each node of a single tree is associated with a hyper-rectangular cell. At each step of the tree construction, the collection of cells forms a partition of [0, 1] p . The root of the tree is [0, 1] p itself, and each tree is grown as follows: Algorithm 1: Breiman random forest predicted value at x. Input: Training set D n , number of trees M > 0, a n ∈ {1, . . . , n}, m try ∈ {1, . . . , p}, and x ∈ [0, 1] p . Output: Prediction of the random forest at x 1 for j = 1, . . . , M do 2 Select a n points, without replacement, uniformly in D n .  Select the best split in A by optimizing the CART-split criterion along the coordinates in M try (see details below).

7
Cut the cell A according to the best split. Call A L and A R the two resulting cell. Compute the predicted value m n (x; Θ j , D n ) at x equal to the only Y i falling in the cell of x in partition P. 11 end 12 Compute the random forest estimate m M,n (x; Θ 1 , . . . , Θ M , D n ) at the query point x according to (1).
So far, we have not made explicit the CART-split criterion used in Algorithm 1. To properly define it, we let A be a generic cell and N n (A) be the number of data points falling in A. A cut in A is a pair (j, z), where j is a dimension in {1, . . . , p} and z is the position of the cut along the j-th coordinate, within the limits of A. We let C A be the set of all such possible cuts in A. Then, with the notation X i = (X (1) i , . . . , X (p) i ), for any (j, z) ∈ C A , the CART-split criterion (Breiman et al., 1984) takes the form where is the average of the Y i 's belonging to A (resp., A L , A R ), with the convention 0/0 = 0. At each cell A, the best cut (j n , z n ) is finally selected by maximizing L n (j, z) over M try and C A , that is To remove ties, the best cut is always performed along the best cut direction j n , at the middle of two consecutive data points. It should be noted that, in the original algorithm, the resampling step in Algorithm 1 (line 2) is done by bootstrapping, that is by choosing n out of n points with replacement.
Here, we consider a slightly different version where resampling is done by choosing a n out of n points without replacement, where a n < n. Picking data points without replacement is just a convenient hypothesis for the proofs. Considering resampling instead of bootstrapping is an easy way to ensure that the estimation error of the forest can be controlled.

Main results
We consider an additive regression model satisfying the following properties: where X = (X (1) , . . . , X (p) ) is uniformly distributed over [0, 1] p , ε is an independent centered Gaussian noise with finite variance σ 2 > 0, and each component m j is assumed to be continuous.
Additive regression models, which extend linear models, were popularized by Stone (1985) and Hastie and Tibshirani (1986). These models, which decompose the regression function as a sum of univariate functions, are flexible and easy to interpret. They are acknowledged for providing a good tradeoff between model complexity and calculation time, and were accordingly extensively studied for the last thirty years. Additive models also play an important role in the context of high-dimensional data analysis and sparse modelling, where they are successfully involved in procedures such as the Lasso and various aggregation schemes (for an overview, see, e.g., Hastie et al., 2009).
Throughout the document, 1 X Θ ↔X i stands for the indicator that X i falls in the same cell as X in the random tree designed with D n and the random parameter Θ. We denote by P Θ the partition corresponding to such a random tree. The following assumption will be needed for our analysis: Assumption 2. (H2) There exists a sequence (γ n ) n → 0 such that, for all n ∈ N , and for all 1 ≤ i, j ≤ n with j = i, almost surely, where Θ is an independent copy of Θ. Besides, there exists a constant σ 2 > 0 such that, for all 1 ≤ i ≤ n, almost surely, It is stressed that (H2) is satisfied in the ideal case where partitions are independent of the labels Y i 's. Indeed, in that case, the indicators 1 and the sample D n are independent, which implies that, almost surely, for all 1 ≤ i, j ≤ n such that i = j, However, assuming such an independence in the Breiman's forests is by far unrealistic, since CART-splits make an extensive use of the whole sample D n to grow the trees. Thus, assumption (H2) states that the dependency between partitions and a fixed data point is weak. Despite its technical aspect, the first part of (H2) can be easily interpreted by saying that given two indicators 1 (which contain information about partitions P Θ and P Θ ), the pair (X j , Y j ) does not much influence the value Y i of another data point. The two random variables Y i and Y j are independent but, since partitions depend upon the whole training sample, Similarly, the second part of (H2) can be understood by saying that the indicator 1 In that case, this would ensure that the first quantity is bounded above. It is our belief that requirements in (H2) are mild, since partitions based on CART-split criterion are not strongly influenced by single observations. Indeed, splits are decided via quantities involving empirical mean and variance, which are just averages over sets of data points and, as such, do not too much depend upon single values. Thus, knowing the value of one data point does not provide much information about the value of another one.
We are now equipped to state our main result.
Theorem 3.1. Assume that (H1) and (H2) are satisfied. Then, provided a n → ∞ and a n log n/n → 0, random forests are consistent, i.e., we have Up to our knowledge, apart from the fact that bootstrapping is replaced by subsampling, this is the first consistency result for Breiman's (2001) forests. Indeed, models studied so far are designed independently of the sample D n , and this makes them much easier to analyse. However, such models are clearly an unrealistic representation of the true procedure, which uses both the positions X i 's and the values Y i 's to grow the trees. The resulting forest is then highly data-dependent and understanding its behavior deserves a more involved mathematical treatment. This important issue will be thoroughly discussed in Section 4.
Our analysis sheds also some interesting light on the behavior of forests when the ambient dimension p is large but the true underlying dimension of the model is small. To see how, assume that the additive model (H1) satisfies a sparsity constraint of the form where S < p represents the true, but unknown, dimension of the model. Thus, among the p original features, it is assumed that only the first (without loss of generality) S variables are informative. Put differently, Y is assumed to be independent of the last (p − S) variables. In this dimension reduction context, the ambient dimension p can be very large, but we believe that the representation is sparse, i.e., that few components of m are non-zero. As such, the value S characterizes the sparsity of the model: the smaller S, the sparser m.
Proposition 1 below shows that random forests nicely adapt to the sparsity setting by asymptotically performing, with high probability, splits along the S informative variables.
In this proposition, we set m try = p and, for all k, we denote by j 1,n (X), . . . , j k,n (X) the first k cut directions used to construct the cell containing X, with the convention that j q,n (X) = ∞ if the cell has been cut strictly less than q times.
This proposition provides an interesting perspective on why random forests are still able to do a good job in high-dimensional settings. Since the algorithm selects splits mostly along informative variables, everything happens as if data were projected onto the vector space generated by the S informative variables. Therefore, forests are likely to only depend upon these S variables, which, in turn, improves the performance of the method compared to other non-adaptive (i.e., whose construction is independent of the Y i 's) ones. This is in line with the results of Biau (2012), who proved that, for a simplified model, the performance of the method only depends upon the true dimension S and not on the ambient dimension p.

Discussion
At first, it should be mentioned that, contrary to most previous works, there is only one observation per leaf of each individual tree. This implies that the single trees are eventually not consistent, since standard conditions for tree consistency require that the number of observations in the terminal nodes tends to infinity as n grows (see, e.g., Devroye et al., 1996;Györfi et al., 2002). Thus, the random forest algorithm aggregates rough individual tree predictors to build a provably consistent general architecture.
One of the main difficulties in assessing the mathematical properties of Breiman's (2001) forests is that the construction process of the individual trees strongly depends on both the X i 's and the Y i 's. For partitions that are independent of the Y i 's, consistency can be shown by relatively simple means via Stone's (1977) theorem for local averaging estimates (see also Györfi et al., 2002, Chapter 6). However, our partitions and trees depend upon the Y -values in the data. This makes things complicated, but mathematically interesting too. Thus, logically, the proof of Theorem 3.1 starts with an adaptation of Stone's (1977) theorem tailored for random forests. More precisely, the proof relies on two main arguments, both of which stress an important feature of the random forest mechanism.
The first argument is outlined in Proposition 2 below. It states that the variation of the regression function m within a cell of a random tree is small provided n is large enough. To this aim, we define, for any cell A, the variation of m within A as Furthermore, we denote by A n (X, Θ) the cell of a tree built with random parameter Θ that contains the point X.
Proposition 2. Assume that (H1) holds. For all ρ, ξ > 0, there exists N ∈ N such that, for all n > N , It should be noted that one of the main requirements of Stone's theorem applied to Y -independent partitioning estimates is that the diameter of the tree cells tends to zero in probability. Instead of such a geometrical assumption, Proposition 2 ensures that the variation of m inside a cell is small, thereby forcing the approximation error of the forest to asymptotically approach zero.
The second important argument relies on the fact that the subsampling rate a n /n is o(1/ log n) in Theorem 3.1. This guarantees that every single observation (X i , Y i ) is used in the tree construction with a probability that becomes small with n. It also implies that the query point x cannot be connected to the same data point in a high proportion of trees. If not, the predicted value at x would be too much influenced by one single pair (X i , Y i ), making the forest inconsistent. In fact, the proof of Theorem 3.1 reveals that the estimation error of a forest estimate is small as soon as the maximum probability of connection between the query point and all observations is small. Thus, the assumption on the subsampling rate is just a convenient way to control these probabilities, by ensuring that partitions are dissimilar enough. This is the case if x is connected with many data points through the forest. This idea of diversity among trees was introduced by Breiman (2001), but is generally difficult to analyse. In our approach, the subsampling is the key component for imposing tree diversity.

Proof of Theorem 3.1
For the sake of clarity, proofs of the intermediary results are postponed to Section 6. We start with some notations.

Notations
In the sequel, to clarify the notation, we will sometimes write d = (d (1) , d (2) ) to represent a cut (j, z).
Recall that, for any cell A, C A is the set of all possible cuts in A. Thus, with this notation, C [0,1] p is just the set of all possible cuts at the root of the tree, that is, all possible choices d = (d (1) , d (2) ) with d (1) ∈ {1, . . . , p} and d (2) ∈ [0, 1].
More generally, for any x ∈ [0, 1] p , we call A k (x) the collection of all possible k ≥ 1 consecutive cuts used to build the cell containing x. Such a cell is obtained after a sequence of cuts d k = (d 1 , . . . , d k ), where the dependency of d k upon x is understood. Accordingly, for any d k ∈ A k (x), we let A(x, d k ) be the cell containing x built with the particular k-tuple of cuts d k . The proximity between two elements d k and d k in A k (x) will be measured via Remember that A n (X, Θ) denotes the cell of a tree containing X and designed with random parameter Θ. Similarly, A k,n (X, Θ) is the same cell but where only the first k cuts are performed (k ∈ N is a parameter to be chosen later). We also denote byd k,n (X, Θ) = (d 1,n (X, Θ), . . . ,d k,n (X, Θ)) the k cuts used to construct the cell A k,n (X, Θ).
Recall that, for any cell A, the empirical criterion used to split A in the random forest algorithm is defined in (2). For any cut (j, z) ∈ C A , we define the following theoretical version of L n (·, ·): Observe that L (·, ·) does not depend upon the training set and that, by the strong law of large numbers, L n (j, z) → L (j, z) almost surely as n → ∞ for all cuts (j, z) ∈ C A . Therefore, it is natural to define the best theoretical split (j , z ) of the cell A as (j , z ) ∈ arg min (j,z)∈C A j∈Mtry L (j, z).
In view of this criterion, we define the theoretical random forest as before, but with consecutive cuts performed by optimizing L (·, ·) instead of L n (·, ·). We note that this new forest does depend on Θ through M try , but not on the sample D n . In particular, the stopping criterion for dividing cells has to be changed in the theoretical random forest; instead of stopping when a cell has a single training point, we impose that each tree of the theoretical forest is stopped at a fixed level k ∈ N . We also let A k (X, Θ) be a cell of the theoretical random tree at level k, containing X, designed with randomness Θ, and resulting from the k theoretical cuts d k (X, Θ) = (d 1 (X, Θ), . . . , d k (X, Θ)). Since there can exist multiple best cuts at, at least, one node, we call A k (X, Θ) the set of all k-tuples d k (X, Θ) of best theoretical cuts used to build A k (X, Θ).
We are now equipped to prove Proposition 2. For clarity reasons, the proof has been divided in three steps. Firstly, we study in Lemma 1, the theoretical random forest. Then we prove in Lemma 3 (via Lemma 2), that theoretical and empirical cuts are close to each other. Proposition 2 is finally established as a consequence of Lemma 1 and Lemma 3. Proofs of these lemmas are to be found in Section 6.

Proof of Proposition 2
We first need a lemma which states that the variation of m(X) within the cell A k (X, Θ) where X falls, as measured by ∆(m, A k (X, Θ)), tends to zero.
The next step is to show that cuts in theoretical and original forests are close to each other. To this aim, for any x ∈ [0, 1] p and any k-tuple of cuts k }, and where we use the convention 0/0 = 0 when A(x, d k−1 ) is empty. Besides, we let A(x, d 0 ) = [0, 1] p in the previous equation. The quantity L n,k (x, d k ) is nothing but the criterion to maximize in d k to find the best k-th cut in the cell A(x, d k−1 ). Lemma 2 below ensures that L n,k (x, ·) is stochastically equicontinuous, for all x ∈ [0, 1] p . To this aim, for all ξ > 0, and for all x ∈ [0, 1] p , we denote by A ξ k−1 (x) ⊂ A k−1 (x) the set of all (k − 1)-tuples d k−1 such that the cell A(x, d k−1 ) contains a hypercube of edge length ξ. Moreover, we letĀ ξ k (x) = {d k : d k−1 ∈ A ξ k−1 (x)} equipped with the norm d k ∞ .
Using the fact that ∆(m, A) ≤ ∆(m, A ) whenever A ⊂ A , we deduce from (3) and (6) that, for all n ≥ N , This concludes the proof of Proposition 2.
To upper bound I n , we note that Hereafter, to simplify notation, we write 1 Therefore, by assumption (H2), Taking the sum over (i, j) for i = j, we obtain We conclude that, for all n large enough, Consequently, recalling that ε i = Y i − m(X i ), we have, for all n large enough, Now, observe that in the subsampling step, there are exactly an−1 n−1 choices to pick a fixed observation X i . Since x and X i belong to the same cell only if X i is selected in the subsampling step, we see that where P Θ denotes the probability with respect to Θ, conditionally on X and D n . So, Thus, combining inequalities (7) and (8), for all n large enough, The term inside the brackets is the maximum of n χ 2 -squared distributed random variables. Thus, for some positive constant C, (see, e.g., Chapter 1 in Boucheron et al., 2013). We conclude that, for all n large enough, I n ≤ α + C a n log n n ≤ 2α.
Since α was arbitrary, the proof is complete.
6 Technical results 6.1 Proof of Lemma 1 Technical Lemma 1. Assume that (H1) is satisfied and that L ≡ 0 for all cuts in some given cell A. Then the regression function m is constant on A.
Proof of Technical Lemma 1. We start by proving the result in dimension Therefore, since L ≡ 0 on C A by assumption, we obtain, This proves that M (z) is linear in z, and that m is therefore constant on [a, b].
Let us now examine the general multivariate case, where A = Π p j=1 [a j , b j ] ⊂ [0, 1] p . From the univariate analysis, we know that, for all 1 ≤ j ≤ p, there exists a constant C j such that Since m is additive this implies that, for all j and for all x j , which does not depend upon x i . This shows that m is constant on A.
Proof of Lemma 1. Take ξ > 0 and x ∈ [0, 1] p . Let θ be a realization of the random variable Θ. Since m is uniformly continuous, the result is clear if diam(A k (x, θ)) tends to zero as k tends to infinity. Thus, in the sequel, it is assumed that diam(A k (x, θ)) does not tend to zero. In that case, since (A k (x, θ)) k is a decreasing sequence of compact sets, there exist a ∞ (x, θ) = (a (1) Since diam(A k (x, θ)) does not tend to zero, there exists an index j such that a (j ) k (x, θ)] be the cell containing x at level k. If the criterion L is identically zero for all cuts in A ∞ (x, θ) then m is constant on A ∞ (x, θ) according to Lemma 1. This implies that ∆(m, A ∞ (x, θ)) = 0. Thus, in that case, since m is uniformly continuous, lim k→∞ ∆(m, A k (x, θ)) = ∆(m, A ∞ (x, θ)) = 0.
Let us now show by contradiction that L is a.s. necessarily null on the cuts of A ∞ (x, θ). In the rest of the proof, for all k ∈ N , we let L k as the criterion L used in the cell A k (x, θ), that is for all d = (j, z) ∈ C A k (x,θ) . If L ∞ it is not identically zero, then there exists a cut d ∞ (x, θ) in C A ∞ (x,θ) such that L (d ∞ (x, θ)) = c > 0. Fix ξ > 0. By the uniform continuity of m, there exists δ 1 > 0 such that Observe that for all From inequality (9), we deduce that Consequently, there exists a constant C > 0, such that, for all k ≥ k 0 , for all cuts d ∈ C A ∞ (x,θ) , Let k 1 ≥ k 0 be the first level after k 0 at which the direction d ∞ (x, θ) is amongst the m try selected coordinates. With probability 1, k 1 < ∞. Thus, by the definition of d ∞ (x, θ), and inequality (11), which implies that c − Cξ 2 ≤ L k . Hence, using inequality (10), we have which is absurd, since c > 0 is fixed and ξ is arbitrarily small. Thus, by Lemma 1, m is constant on A ∞ (x, θ). This implies that ∆(m, A k (x, Θ)) → 0 as k → ∞.

Proof of Lemma 2
We start by proving Lemma 2 in the case k = 1, i.e., when we perform the first cut at the root of a tree. Since in that case L n,1 (x, ·) does not depend on x, we simply write L n,1 (·) instead of L n,1 (x, ·).
Proof of Lemma 2 in the case k = 1. Fix α, ρ > 0. Observe that if two cuts d 1 , d 2 satisfy d 1 − d 2 ∞ < 1, the cut directions are the same, i.e. d (1) Using this fact and for reasons of symmetry, we just need to prove Lemma 2 when the cuts are performed along the first dimension. In other words, we only need to prove that lim n→∞ P sup Recall that, for all i, The last probability can be upper bounded by using the following standard inequality on Gaussian tail: Consequently, there exists a constant C ρ > 0 and N 1 ∈ N such that, with probability 1 − ρ, for all n > N 1 , Besides, by simple calculations on Gaussian tail, for all n ∈ N , we have, Since there are, at most, n 2 sets of the form {i : X i ∈ [a n , b n ]} for 0 ≤ a n < b n ≤ 1, we deduce that, from the last inequality and using an union bound, there exists N 2 ∈ N such that, with probability 1 − ρ, for all n > N 2 , for all 0 ≤ a n < b n ≤ 1 satisfying N n ([a n , b n ] × [0, 1] p−1 ) > √ n, we have By the Glivenko-Cantelli theorem, there exists N 3 ∈ N such that, with probability 1 − ρ, for all 0 ≤ a < b ≤ 1, for all n > N 3 , Throughout the proof, we assume to be on the event where assertions (13)-(15) hold, which occurs with probability 1 − 3ρ, for all n > N , where N = max(N 1 , N 2 , N 3 ). Take x 1 , x 2 ∈ [0, 1] such that |x 1 − x 2 | ≤ δ and assume, without loss of generality, that x 1 < x 2 . In the remainder of the proof, we will need the following quantities (see Figure 1 for an illustration in dimension two): Similarly, we define Recall that, for any cell A,Ȳ A is the mean of the Y i 's falling in A and N n (A) is the number of data points in A. To prove (12), five cases are to be considered, depending upon the positions of x 1 and x 2 . We repeatedly use the decomposition First case: n for all n > N , we have, according to inequalities (14), Thus, for all n large enough, With respect to J 1 , observe that Since N n (A L,2 ) − N n (A L,1 ) ≤ n(δ + δ 2 ), we obtain for all δ small enough, which implies that Thus, The term J 3 can be bounded with the same arguments.
Finally, by (16) and (17), for all n > N , for all δ small enough, we conclude that Second case: x 1 , x 2 ∈ A L, √ δ . With the same arguments as above, one proves that Consequently, for all n large enough, √ δ } can be treated in the same way. Details are omitted.
Proof of Lemma 2. We proceed similarly as in the proof for the case k = 1. Here, we establish the result for k = 2 and p = 2 only. Extensions are easy and left to the reader. Fix ρ > 0. At first, it should be noted that, there exists N 1 ∈ N such that, with probability 1 − ρ, for all n > N 0 , and, whereσ 2 is a positive constant, depending only on ρ. Inequality (19) is a straightforward consequence of the following inequality (see e.g. Laurent and Massart, 2000), which is valid for all n ∈ N : Throughout the proof, we assume to be on the event where assertions (13), (15), (18)-(19) hold, which occurs with probability 1 − 3ρ, for all n large enough. We also assume that d 1 = (1, x 1 ) and d 2 = (2, x 2 ) (see Figure 2). The other cases can be treated similarly. Let d 1 = (1, x 1 ) and d 2 = (2, x 2 ) be such that Then the CART-split criterion L n,2 writes Clearly, We have ( Figure 2): The term A 1 can be rewritten as A 1 = A 1,1 + A 1,2 + A 1,3 , where

Calculations show that
which implies, with the same arguments as in the proof for k = 1, that A 1,1 → 0 as n tends to infinity. With respect to A 1,2 and A 1,3 , we write Thus, A 1,2 → 0 and A 1,3 → 0 as n → ∞. Collecting bounds, we conclude that A 1 → 0. One proves with similar arguments that B 1 → 0 and, consequently, that

Proof of Lemma 3
We prove by induction that, for all k, with probability 1 − ρ, for all ξ > 0 and for all n large enough, d ∞ (d k,n (X, Θ), A k (X, Θ)) ≤ ξ.
Call this property H k . Fix k > 1 and assume that H k−1 is true. We momentarily keep X fixed. For all d k−1 ∈ A k−1 (X), let where the minimum is evaluated, as usual, over {d k ∈ C A(X,d k−1 ) : d Fix ρ > 0. Observe that the volume of a cell which does not contain a hypercube of edge length ξ is necessarily less than ξ. Thus, the probability to fall in such a cell at level k is, at most, 2 k ξ. Since k is fixed, letting ξ = ρ/2 k , conditionally on D n , with probability 1 − ρ, the cell A k,n (X, Θ) contains a hypercube of edge length ξ. In the rest of the proof, we assume X and Θ to be fixed and that A k,n (X, Θ) satisfies this geometrical property. Moreover, since X and Θ are fixed, we omit the dependence on X and Θ.
Note that, for all d k−1 , (by definition ofd k,n (d k−1 )). Thus, Moreover, LetĀ ξ k = d k : d k−1 ∈ A ξ k−1 . So, taking the supremum on both sides of (20) leads to By Lemma 2, for all ξ > 0, one can find δ > 0 such that, for all n large enough, SinceĀ ξ k is compact, there exists a finite subset X δ = {x 1 , . . . , x p } ⊂Ā ξ k such that, for all d k ∈Ā ξ k , d ∞ (d k , X δ ) ≤ δ. Hence, for all d k ∈Ā ξ k , there is an index j such that, with probability 1 − ρ, for all n large enough, (by inequality (22)) ≤ 3ξ , since, for all x j , L n (x j ) → L (x j ) almost surely, as n tends to infinity. In consequence, with probability 1 − ρ, for all n large enough, sup d k ∈Ā ξ k |L n (d k ) − L (d k )| ≤ 3ξ , and, using inequality (21), we finally obtain that with probability 1 − ρ, for all n large enough, Hereafter, to simplify, we assume that, for any given (k − 1)-tuple of theoretical cuts, there is only one theoretical cut at level k, and leave the general case as an easy adaptation. Thus, we can define unambiguously Fix ξ > 0. From inequality (23), by evoking the equicontinuity of L n and the compactness of A ξ k−1 , we deduce that, with probability 1 − ρ, for all n large enough, In particular, with probability 1 − ρ, for all n large enough, d ∞ d k,n (d k−1,n ), d k (d k−1,n ) → 0. Now, using triangle inequality, Thus, we just have to show that d ∞ (d k (d k−1,n ), A k ) → 0 in probability, as n → ∞, and the proof will be complete.
To avoid confusion, we let d k−1 = {d ,i k−1 : i ∈ I} be the set of best first (k − 1)-th theoretical cuts (which can be either countable or not). With this notation, d k (d ,i k−1 ) is the k-th theoretical cuts given that the (k − 1) previous ones are d ,i k−1 . For simplicity, let L i, (d k ) = L k (d ,i k−1 , d k ) andL (d k ) = L k (d k−1,n , d k ). As before, d k (d ,i k−1 ) ∈ arg min d k L i, (d k ) and d k (d k−1,n ) ∈ arg min d kL (d k ).
Clearly, the result will be proved if we establish that, inf i∈I d ∞ (d k (d k−1,n ), d k (d ,i k−1 )) → 0 in probability, as n → ∞.
Since d k belongs to a compact set, we can find a finite set X = {x 1 , . . . , x m } ⊂ C [0,1] p satisfying d ∞ (d k , X) ≤ ξ. Thus, there is an index j such that, with probability 1 − ρ, for all n large enough, Therefore, as in inequality (21), with probability 1 − ρ, for all i, and for all n large enough, Taking the infimum over all i, we obtain Introduce ω, the modulus of continuity of L k : Observe that, since L k (·) is uniformly continuous, ω(δ) → 0 as δ → 0. Hence, for all n large enough, since, by assumption H k−1 , inf i d k−1,n − d ,i k−1 ∞ → 0. Therefore, combining (24) and (25), with probability 1 − ρ, for all n large enough, inf i |L i, (d k (d k−1,n )) − L i, (d k (d ,i k−1 ))| ≤ 6ξ.
Finally, by Lemma 4 below, H k is true. Property H 1 can be proved in the same way.
Lemma 4. For all δ > 0, there exists ξ > 0 such that made along an informative variable, in the sense that it is performed along one of the first S variables. Consequently, for all X, Θ and for all 1 ≤ j ≤ k, each theoretical cut d j (X, Θ) is made along one of the first S coordinate. The proof is then a consequence of inequality (27).