L Avanthey

A Gademer

L Beaudoin

M Roux

⇤ † Esiea

First steps for operational dense and high-resolution mapping of shallow water using dedicated robots

Acquiring dense and high resolution 3D data in operational conditions is a real challenge during exploration of underwater or subaquatic areas for environmental, archaeological, defense and security applications. In order to achieve these goals, the use of small automated robots can be seen as an e cient solution. In this paper, we focus on local areas in shallow water and we present an overview of our devevelopment for seafloor mapping. We introduce a dedicated robot and detail the first steps of the developpement of a dedicated payload: a stereo rig and a 3D reconstruction system. The last part discusses our first operationnal results and future work.

ROBOTS FOR DENSE AND HIGH-RESOLUTION MAPPING IN SHALLOW WATER 1.The underwater and subaquatic areas

Dense mapping of the seafloor (surface and landcover) with a high precision can be critical for many applications such as defense and security [START_REF] Corfield | Defence applications for Unmanned Underwater Vehicles[END_REF], industry [Danson, 2003], environment [START_REF] Gademer | Réalité Terrain Étendue: une nouvelle approche pour l'extraction de paramètres de surface biophysiques et géophysiques à l'échelle des individus[END_REF] or archeology [START_REF] Warren | Deepwater Archaeology With Autonomous Underwater Vehicle Technology[END_REF]]. Yet those represent very large areas as both oceans and seas cover about 70,8% of the Earth's surface [START_REF] Christ | The ROV Manual: A User Guide For Observation Class Remotely Operated Vehicles[END_REF] and in addition, the task of acquiring data underwater is more di cult than in the air. Indeed, the main issues come directly from the restriction of electromagnetic waves propagation due to the nature of the medium [START_REF] Rives | Chenz et Christian Pétron : La prise de vue sous-marine[END_REF]. Refraction, absorption, di↵usion, added to the distance and a dependance on the air / water interface make it di cult for spatial altimetry or aerial bathymetry to give highly accurate data. So, in order to acquire more accurate and dense data of a local area we have to perform in situ remote sensing.

However underwater environment is rather hostil. In situ limitations are related to high pressure and salt corrosion which are particularly problematic to both human and material [START_REF] Christ | The ROV Manual: A User Guide For Observation Class Remotely Operated Vehicles[END_REF]. Indeed, pressure increases with depth by about 1 bar (one kilogram per square centimeter) every ten meters. At the bottom of oceans, a square centimeter has to support a pressure force around 200 kilograms and it can be up to 1 ton in ocean trenches. As for salt, by transforming the water into an electrolyte, it activates corrosion: some materials can therefore be damaged in a short time and that can easily lead to leaks or mechanical malfunctions.

The restriction of electromagnetic waves propagation also causes in situ problems as it results in poor visibility (less than 15 meters most of the time, made worse by turbidity, often blurred) and in colors alteration but also and more importantly in low rate communication (if wireless) and in imprecise localisation (due to the inability to directly use global positioning methods such as GPS).

Last but not least, the fact that it is a natural environment is a di culty in itself for acquisition. Currents, waves and tides make it impossible to stand still, unless to land at the bottom and be anchored there. These events also promote the sudden changes of the environment properties. Indeed the underwater environment is not homogeneous and strongly depends on the balance between temperature, salinity and pressure.

It is also inhabited by fauna and flora. This adds a lot of movements in the study areas: independent movements for wildlife or movements following the motion of the medium for plants like the leaves of a tree in the wind. Added to the imprecise mouvements of the acquisition vector itself, this can lead to inaccurate measurements.

Acquiring 3D Data

On the other hand the density of the water medium improves the propagation of sound waves comparing to air, that is why acoustic based sensors (such as sonar) are traditionally used for mapping the seabed. But these sensors are mainly dedicated to recover the distance from the sensor to the sea bottom and they therefore essentially produce contour lines. Thus, to achieve dense and high-resolution mapping of sea bottom and landcover, we can not rely solely on these sensors. To overcome this, we can use optical sensors, but because of the limited visibility, it is necessary to be very close to the studied surface. This constraint significantly increase the time requiered to achieve the cartography of undersea areas.

The use of robots

These missions of data acquisition can be qualified as 3D jobs (Dull, Dirty and Dangerous), where the dull part essentially takes place in the vastness of the areas to meticulously observe and in the temporal repetition. As to the dirty & dangerous part, it takes place in the di cult and dangerous accesses to some study areas where the pressure is huge or the path steep.

Thus, the use of underwater robots appears to be an e cient and promising solution for these missions, especially as they allow the automation of certain tasks and the use of dedicated payload.

In this article, we will focus on dense and high-resolution mapping of local areas in shallow water (less than 100 meters deep). In the first place, we will present the dedicated robot developped specifically to be easily operated, customizabled, and readily reproductible. Then we will detail the dedicated hardware stereo payload. Once the data acquired, the next section will deal with the 3D reconstruction system in the very specific case of underwater imagery. The last section will discuss the first operationnal results and perspectives.

Small underwater robots for scientific missions

The choice of the robot is very important for the operational side of data acquisition: it must be easily reconfigurable depending on the mission, easy to carry on the study areas, have su cient autonomy and maneuverability, and be a↵ordable in order to multiply the units for spare or collaboration squad.

Sizes and prices of robots on the market are quite substantial, involving a significant operational cost of transport (truck, etc.), handling (cranes, boats, etc.) and maintenance (advanced technology, expensive specialized equipment, etc.). The technical choices related to this issues impose constraints on which payload can be installed (compatibility with the existing connections) as well as their disposition on the robots (size, weight, place, orientation, etc.). Among the few small robots (< 20 kg) that are available at low cost nowadays, very few are dedicated to perform scientific missions: they rarely exceed 30 meters depth and have mostly no automation at all. So we decided to design a robot dedicated to mapping missions, called Ryujin [START_REF] Beaudoin | Aquatis and Ryujin projects: first steps to remote sensing of the sea bottom by small homemade Autonomous Underwater Vehicles[END_REF], illustrated in figures 1(a) and 3(a).

2 A DEDICATED HYBRID UNMANED UNDERWATER VEHICLE (UUV)

Main technical features of the development of the robot

Inspired by the philosophy of the MIT's Seaperch project [START_REF] Bohm | Build Your Own Underwater Robot and Other Wet Projects[END_REF]Sea, 2011], we have developped a small lightweight platform with cheap materials and simple mechanics.

The watertight compartment consists of a PVC tube with two PMMA transparent caps, machined with a CNC. The whole is held by clamps, thus no specific tools are required to open or close the compartment as illustrated in figure 1(c)).

The inner frame, shown in figure 1(b), holds the intelligence and power parts. Ryujin fully benefits of the decrease of electronics components size and cost for its homemade control and power boards as well as for critical sensors like pressure sensors that provide information on the depth of the vehicle or attitude and heading reference systems (AHRSs). As for the embedded computer used to perform high-level tasks such as images processing, we nowadays have acces to both small and cheap units (about one or two times the size of a stick of gum, < 50 g, < 120 e) presenting quite good performances (> 600 MHz, > 256 Mo RAM) like the well-known Raspberry Pi or other like the UG802 (an android TV dongle) we are using and on which we installed a linux. But most runs on ARM architecture, which often causes problems concerning drivers as they are not always ported. Moreover the ease of interfacing with other systems di↵er greatly from a model to the other.

The Fischer connectors on the rear cap allow the communication between the embedded units and the submerged blocks that are mounted on the outer frame. Made of PVC pipes and fittings that interlock, the outer frame is totally immersed and can easily take di↵erent configurations. We sealed the connectors with resin and the wet connections are carefully made with hot glue and heat shrink (so that we can change them, unlike resin which is definitive).

One of the outer blocks is crucial in the design of the robot as it concerns the propulsion system. Most of the cheaper sealed motors are fairly large which consequently constrains the size of the robot. To solve this problem we diverted brushless motors to make them run in total immersion in salt water [START_REF] Avanthey | Ryujin AUV: SAUC'E 2011 Journal Paper. International Student Autonomous Underwater Vehicle Challenge[END_REF]. By removing this size constraint, we were able to design the robot exactly with the size we wanted. We use almost the same brushless motors as those of our Unmanned Aerial Vehicles [Gademer et al., 2010a,b], except that they have a higher torque (more appropriate to water environment). Without protection, the motor we tested ran for a hundred hours in fresh water before seizing up and another one stopped working after only 10 hours of immersion in salt water (about 40 g/L).

To marinise the system, we have changed some parts like the screws and we covered the other sensitive parts with marine varnishes like the stator (previously surfaced to give room), the coil, the magnets and parts of the cage. The most important step was the replacement of the ball-bearings guiding the shaft by a home-made POM bearing. This process is illustrated in figure 1(d). It is a crucial part in the motor system but also the most fragile one when exposed to water and salt.

After these modifications, we have run a motor again in salt water and stopped the test after 200 hours as the engine showed no signs of wear. The marinization of brushless motors is rather convincing and we use them since, either in pool or in seawater, without encountering any problems. As these motors are powerful, we restrain them at about 20% of their power, which is more than enough.

Ryujin: an hybrid underwater prototype

The resulting prototypes have a size of 20 ⇥ 20 ⇥ 30 cm, weight about 9 kg and present an autonomy of about two hours and a theorical pressure resistance up to 11 bars (100 meters, tested up to 15 meters) for a very low cost (about 1200 e to build one). They are highly customizable and can be equipped with a payload fitting the mission.

Ryujin is an hybrid robot, that means it can be used in Autonomous Underwater Vehicle (AUV) mode as well as in Remotely Operated Vehicle (ROV) mode.

In AUV mode, the robot has an automatic depth (relative to pressure) and course (relative to the magnetic north) control. These control loops are based on PID controllers, described by equation 1. They must allow the vehicle to not only reach the given order but to keep by it whatever disturbances encountered in the environment (current, density change, buoyancy, etc.). The depth control loop has been tested in a diving pool with more or less strong human disturbances by contact to ensure that the robot returns to its position within a reasonable time with minimal oscillations around the setpoint [START_REF] Avanthey | AUV Ryujin 2013 -Tests en Fosse de Plongée[END_REF]. The depth logs are presented in figure 3(c). Unlike UAVs which operate in the air at a very fast speed and therefore strongly depend on the proportional (K P ), we observed that in water, this coe cient is almost neglected in favor of the integration coe cient (K I ), mostly because of the density of the medium and the resulting inertia. As for the derivative coe cient (K D ), it is equally important. Concerning the other parameters, neutral is the constant thrust to sustain the vehicle and " is the di↵erence between the measure and the targeted set point.

Order = neutral + K P ⇥ " K D ⇥ " dt + K I ⇥ Z "dt (1)
For the time being, the AUV mission plans use dead reckoning processes and the robot does not dispose of sonic modem communication. Therefore, when in AUV mode, it is possible to communicate with it only when it is on the surface. The communication with the low-level unit (control and sensors) is done via ZigBee protocol and we use the WiFi protocol with the high-level unit (vision). We will add more automation in the future such as vision or accoustic based navigation.

When in ROV mode, the robot is controlled by a ground operator which communicates with the robot through a cable which transmits the data. The end of the ROV cable can be anchored to the ground but to improve flexibility it can also be anchored on a surface vehicle that stay right above the robot.

All data are centralized on a ground station which distributes them to the di↵erent actors. The information from the robot (as the current depth, the battery level, etc.), passes through the cable and is received via the ZigBee protocol by the station which displays it in real-time in the control interface. Similarly, orders from the operator by either the control handle (FAST RF) either directly by the control interface, are transmitted in real time to the robot.

When performing data acquisition, the distance to the observed area is important as we will see later, and so it is necessary to maintain a stable depth. Since it is di cult to maintain manually a constant depth, especially when disposing of an indirect view of the scene, the ROV mode is often semiautomated to assist the human operator. Thereby it can borrow on demand the automatic depth or course control of the AUV mode. To keep a certain maneuverability the operator can at any time regain control of these automated functions.

A DEDICATED STEREO RIG AND 3D

RECONSTRUCTION SYSTEM

Features of a stereo rig adapted to underwater environment

The next step concerns the acquisition and processing of the optical images. Since years, a lot of works have been done to extract 3D information from images [R. et A., 2000]. But classical reconstruction systems are typically used on fixed scenes (objects) or rather rigid areas (indoor area, urban area, etc.). Therefore those systems often find themselves in trouble dealing with outdoor scenes [START_REF] Kramm | Production de cartes éparses de profondeur avec un système de stéréovision embarqué non-aligné[END_REF] due to the dynamics of the observed environnement or of the camera, alteration of colors, turbidity, blur, etc.. Amongst them, the synchronized stereo system seems the most robust to these constraints. Synchronisation is a key element to reconstruct dynamic scenes [START_REF] Hogue | Underwater 3D Mapping: Experiences and Lessons learned[END_REF]. Indeed, the majority of reconstruction algorithms relies on the fact that the left view corresponds strictly to the same scene as seen by the right image. If the images are not taken simultaneously, then this a priori become false. To be e↵ective, the synchronization must be done at two levels (same acquisition start and same acquisition duration) and must be accompanied with a precise datation to combine it with other data that can help the accurate repositioning of the acquisition in the relative space.

It is impossible to have a real perfect synchronisation in practice but what is important is that the higher shift that can occured in the area during the synchronisation time should be lower than one pixel.

Many analog cameras have the ability to be precisely synchronized (line by line during the acquisition). However, it is very di cult for the majority of the models to precisely date the frames. Digital cameras, on the other hand, can have a level of dating very interesting but it is harder to get a good synchronisation level with them. Indeed, only rely on electrically triggering the acquisition (an often used process) is not enough for full synchronization, even if the clocks are synchronized (figure 4). At least, to reach the two levels of synchronisation we mentioned, it takes in addition a fixed starting time of acquisition after the reception of the trigger (time to prepare the camera), a fixed exposure time and if possible a transfer time roughly equivalent for each camera of the rig as summarized in equation 2. The latter is mainly used to calculate the maximum frequency of shots. It is a parameter that will influence the speed of the vector (to obtain a certain overlap rate) as well as the exposition time (to prevent motion blur). The camera must also allow to disable all the automatic functions (white balance, auto-shutter, etc.) that could influence these durations or di↵erentiate the quality of the images in a stereo pair [START_REF] Matthews | Aerial and Close-Range Photogrammetric Technology: Providing Resource Documentation, Interpretation, and Preservation[END_REF].

T acq = T preparation + T exposure + T transf er max (2)
It is possible to estimate the level of synchronization of the system experimentally. The simplest test, which also allows to measure the accuracy of the acquisition frequency is to take pictures of a digital counter (at least to the hundredth of a second, if possible thousandth).

As seen in figure 5, other tests like taking pictures of a falling ball, of color blades turned by hand, of a flash that spreads on a flat surface, of a light that moves in the dark, of a flag in the wind or of water propulsion, are based on position. So they require to minimize as much as possible the disparity that will disturbs the comparaison of the two views. Then we must use the smallest base possible (distance between the two cameras) and be far enough from the observed scene. It is more advisable to use graduate targets to help the measurement.

Two other important criteria relate to the base and the height to the target. They will be constrained by the choice of the GSD (Ground Sample Distance, GSD mm ). Following the methodology of Extended Ground Truth [START_REF] Gademer | Application of the Extended Ground Thruth concept for risk anticipation concerning ecosystems[END_REF], the choice of GSD will allow (with the parameters of the camera: resolution R pix , focal length f mm , width of the optical chamber L mm ) to calculate the maximum height (H mm ) relative to the target (equation 3). The maximum height will then constrain the maximum base of the system in order to obtain an overlap of at least 60% (equation 4), a classic and recommanded choice in stereoscopy. Then these two parameters can be adjusted given the desired depth accuracy and the desired travel speed which influences the time needed to cover an area, the global overlap and the motion blur.

Hmm = R pix ⇥ fmm Lmm ⇥ GSDmm (3) Bmm = R pix ⇥ GSDmm ⇥ (1 60) (4)

Hardware part: the stereo rig

Because of the lack of "on the shelf" solutions (waterproof, small, controllable, synchronisable, a↵ordable, etc.), we build our own rig dedicated to the application.

We opted for a static rig to simplify the 3D reconstruction process. It can take images of the study area from nadir: either mount in parallel with the vector to observe sea-bottom and landcovers or right-angle oriented for observing underwater cli↵s, boat hulls, pipelines, wrecks or dams for examples. We build two di↵erent rigs: one with uEye cameras and later the other one with GoPro Hero2 cameras. Both are represented in figure 7.

The uEyes are fully configurable and have a decent resolution (pixel size about 5.3 µm in full resolution), a good synchronisation rate (+/ ten thousandth of a second) and an accurate timing (one-thousandth of a second). However the focus is manual and has no mechanical fixation. In addition the optical we have possesses little depth of field (and thus the focused area is very small).

The uEyes does not have internal storage capacity: to operate they need an embedded computer in order to trigger the shooting and retrieve then save the acquired images. The acquisition program, shown in figure 6, takes into account the reduced computational power of embedded computers. To achieve the best synchronization rate, it uses a thread for each camera while the dsPIC of the motherboard generates the trigger indicating that the next acquisition should start. We can thus acquire a synchronized pair of images every half second. The program is robust to the restart of the robot or to the disconnection of one or both cameras. All automatic settings has been disabled (they are initialized with fixed values that can be changed depending on the mission). Yet, brightness variations in outdoor areas are common (passing clouds, shaded and sunny areas, more or less reflective surfaces, etc.) and often brutal. Therefore, with a fixed exposure time, we may find ourselves with images either overexposed or underexposed. To overcome this, we take a measure of the automatic exposure every five acquisitions to adjust our parameter. Besides, we also observed a color di↵erence between the two sensors, but we have not yet set this problem. That can be embarrassing for the algorithms we are using in the 3D reconstruction system as we shall see in the next section.

We installed both cameras in individual dive housings from Prismatec, equipped with sealed connectors that allow them to communicate with the robot. They use the USB protocol which implies that the sealed cables and all others which are part of the connection must be twisted so that data can transit without loss.

As we have met many technical problems to finalize this rig, we did not had the time to test it during our pool sessions. Therefore, it was prooftested during the acquisition mission with the results we will discuss later.

As for the GoPro cameras, they present a better resolution (pixel size about 1.65 µm in full resolution), a decent synchronisation rate with the synchronisation cable (+/ one hundredth of a second) and an honorable dating (up to a second). However they are not meant to be configured or controlled by a robotic platform. Indeed, some functions are automatic and can not be deactivated (white balance, ISO, etc.) although they can be minimized (it would require to look in the firmware to see if it is possible to completely disable them). The focus changes are really frequent and can be a problem when there

Harris Detector

L_img

List of points Undistort

R_img Undistort

L_img

R_img

Harris Detector

List of points

Matching by correlation

List of matched inliners

Dense matching by propagation

Disparity Map

3D Reprojection

Points Cloud camera parameters is a lot of movements (blur). The di↵erence of color between two cameras is also present even when using the synchronisation cable. In addition, the waterproof case welcoming both cameras have a very small base (3.46 cm) and do not have optical adapted to the underwater environment. It would be therefore necessary to self-made a synchronisation cable and put both cameras in slave mode so that they can be controlled by an electronic card. It would require as well to equip the dive housings with sealed connectors. We have not yet been able to acquire a synchronisation rate up to the original one with this configuration so in this article we have used the GoPro rig as seen in figure 7, without external control and with maximum half a second between both images using the timelaps mode. In addition to monitoring, we will also need to recover the data and meta-data on the embedded computer for processing but this will be for future work.

List of matched points

Supression of outliers

Software part: the 3D reconstruction system

In our operationnal data acquisition schema, we consider the use of two software systems for 3D reconstruction. The first software is meant to be dedicated to produce accurate and dense results once the mission is done. It could essentially rely on existing software in a first phase. As for the second software, it is not meant to be very accurate. Indeed it could be use for providing an accurate feeback in near-real time on the progress of mapping and determine the completeness of data acquired on the area (compliance of the acquisition in terms of coverage and quality). Besides it could also be used to get an idea of the structure of the environment around the robot and help the navigation (positioning, pathways, etc.).

So far for this second software, we have work on a proof of concept based on slightly modified classic algorithms. It has not yet been built and optimized to perform in near-real time.

We use the well known Harris detector to select interest points on a stereo pair. The calculations are relatively fast and we find it quite appropriate to the underwater context as it focuses on really textured objects, unlike SIFT or SURF points that generally seek to spread over the whole image. So we obtain no points in water only areas (despite particles or lighting e↵ect which creates artificial texture) or where the absorption of light is too high (and then cause a near complete visual loss of relief). The use of this detector is also possible due to the rigidity of the stereo rig (no or very little rotation between the two views). We slightly changed the Harris algorithm in order to not set a threshold (to define if a point is of interest) but iteratively adapt this threshold to obtain a number of points in a given interval. So whatever the shooting conditions, we are guaranteed to have the appropriate number of points (not too much, but enough) for the rest of the processing.

We perform a matching by correlation. We made several comparative tests with SURF, SIFT and ASIFT algorithms on underwater images taken under di↵erent conditions and the results we get in terms of inliners over an initial number of interest points are in general as good as those and often even better. This confirms the results presented in [START_REF] Méline | Fusion multimodale pour la cartographie sous-marine[END_REF] about the use of Harris points in the underwater environment.

In addition, we have noticed that the correlation with SSD (which is the less time consumming of the correlation criteria) on rigid submarine views mostly gives better results over ZNSSD or ZNCC. This is true if there is no strong color di↵erence between the views, in which case you must use ZNCC. When the matching is done, we supress the outliers with a simple algorithm that use statistic over the local vector flow (if a vector does not follow the mean local movement then it is likely an outlier).

We have tested the well known epipolar geometry rectification to then perform dense matching, but finally we preferred to avoid this method which is very time consuming. Our images are almost in epipolar geometry because of the rigid rig, so instead we chose to use a spreading method inspired by [START_REF] Lhuillier | Robust Dense Matching using Local and Global Geometric Constraints[END_REF].

The inliners stand as seeds to help spreading the matching: a point next to an inliner should be found in all probability next to the corresponding point on the other image. If its correspondant is found, then the point becomes a new seed. We limit the spreading by a radius around the initial inliners in order to not infer too much on areas with no real texture.

Then we perform reprojection on the obtained disparity map to create the point cloud. The figure 8

FIRST RESULTS AND PERSPECTIVES

We tested our developments in a field mission to collect data (figure 10). It took place at Cap de Nice (Mediterranean Sea), during three days at the end of August 2013. The chosen area for our first underwater field mission allows a rather clear water, a bedrock instead of sand (lots of relief) and an easy access to enough depth (3 to 30 meters) without the need of a boat.

The main objectives of the mission were:

1. to test Ryujin in real conditions. Indeed, so far the robot had worked around fifty hours in a pool since three years (counting leak testing), and twice five days in the port and saltwater pools of La Spezia at Sauc-E competition (2011 and 2012 editions).

2. to test the uEyes stereo rig in real conditions: synchronization, image quality, frequency of the acquisition versus speed of the vector, etc..

3. to acquire stereoscopic pairs to cover an underwater area that ranges between 0 and 15 meters depth. Insofar as possible to acquire synchronized stereoscopic pairs. 4. to acquire the experience to properly demarcate an underwater area (patterns).

For the moment, the egolocalisation capabilities of the robot do not allow an automated movement in a turbulent medium. But to carry it out in ROV mode, it is necessary to have a real-time video feedback that we have not yet been pre-processed (no contrast enhancement and so on) and were proportionally resized to developed. Indeed we have observed that when the pilot on ground is looking at the robot through the surface, it disappears enough to prevent the piloting beyond one meter deep and two to three meters away. We tested some control near the base, but the pressure sensor did not give very consistent values for some reason we do not understand yet and thus it prevent us to safely dive below the turbulent surface. Despite this we were able to do some tests which showed that the robot could move smoothly enough to perform the mapping even in a turbulent medium. In order to collect data we decided for the duration of the mission to lead the robot by hand with the help of a diver in order to cover the entire study area.

As for the uEyes stereo rig, we were able to validate its proper functioning and especially the quality of the synchronization. The first acquisition were not made under favorable conditions: it takes place in the evening and at the surface, so they were little light and a lot of swirl. Because of this the majority of the images were often blurred and sometimes too dark or too light, but they were perfectly synchronized (that is, the blur was perfectly synchronised). Unfortunately one of the cables broke the following morning and we have not been able to fix it. So we were not able to redo the acquisitions in the light of day with a diving cylinder to avoid the movements of the surface neither were we able to perform other tests on the quality of the images according to the settings of parameters.

Therefore, the images we collected were essentially taken with the GoPro stereo rig, and therefore a low synchronization rate, but a very good resolution. By covering the area, we collected about 20, 000 stereo pairs. Figure 11 shows Finally concerning the patterns we used to mark the area, they have many uses: they stand as depth indicator (mesured when we drop them o↵) as well as landmarks when covering the area. But they also are usefull in post analysis: as distance scale and depth reference but also as daymarks for global positionning as they are numbered and oriented (when we see a pair with a pattern, we could know approximately where it was located in the covered area). The pattern must be rigid, weighted and dropped o↵ on di↵erent depth zones as flat as possible towards the robot path.

The patterns we had prepared consist of a white frame and large black tiles with two of di↵erent colors for the orientation of the pattern. The white frame has not proved to be appropriate. Indeed even if it made it easy to spot them by far (even from the surface) it most of the time caused overexposure on images (the tiles on the pattern were even sometimes impossible to see). To us, white seems a color to avoid on underwater patterns with the type of cameras we use (except in ultra clear water), so next we will try a light gray color.

Besides, we plan to add features on the plain tiles of our patterns, inspiring us with the patterns used by [START_REF] Matthews | Aerial and Close-Range Photogrammetric Technology: Providing Resource Documentation, Interpretation, and Preservation[END_REF], because we they can easy seeds for the matching algorithm described in section 3.3.

Finally, we estimate that it 10 patterns for an area of 1, 000 square meters (it increased if the study area presents a lot di↵erent depth plateau).

5

From now, futur work will focus on:

• the improvement of the reconstruction and the validation obtained accuracy.

• aggregation of the local point clouds to obtain a global representation of the study area.

• optimization of the 3D reconstruction system to perform in near real time onboard.

• add a real-time video feedback to allow the control of the robot on studies area. It could be either embedded or from a surface vehicle equipped with an immersed camera. The tests of vision we have performed during the mission show that the robot, with its white frame, stands out very well from the underwater bedrock and is visible from the surface even at 15 meters depth.

• try to create an online database of underwater pairs from both uEyes and GoPros accompanied by land information (weather, water temperature, visibility, etc.) based on an accessible test area. This could not only allow to compare the results on the data (postprocessing or simulation of real-time processing), but also the results of acquisition or even coverage area when comming to the test area.

  Figure 1: Prototypes of the robot and technical parts.

Figure 2 :

 2 Figure 2: Block diagram of the robot.

Figure 3 :

 3 Figure 3: The underwater vehicle in use and its monitoring tools.

Figure 4 :

 4 Figure 4: Cases of synchronisation (high-low mode).

Figure 5 :

 5 Figure 5: Synchronisation estimation with targets.

Figure 6 :

 6 Figure 6: Flowchart of the acquisition process used.

Figure 7 :

 7 Figure 7: Payload for underwater stereo pairs acquisition.

Figure 8 :

 8 Figure 8: Flowchart of the 3D reconstruction process used.

Figure 9 :

 9 Figure 9: Example of the di↵erent steps of the 3D reconstruction software: Harris detector, matching by SSD (vector representation), disparity map by propagation and point cloud. Top: Plage Bleue, bottom: Lac Pavin.

Figure 10 :

 10 Figure 10: Acquisition mission at Cap de Nice (Mediterranean). From left to right : A space view (Google) and a sketch of the study area, ground camp and data acquisition.

Figure 11 :

 11 Figure 11: Examples of data acquired during the mission (left images from stereo pairs). Left: GoPro images, right: uEye images.

  Our resulting point cloud from the stereo pair 12(a) (' 300, 000 points).

Figure 12 :

 12 Figure 12: Examples of point clouds produced from the acquired data (relative to the cameras).

Figure 13 :

 13 Figure 13: Example of the 3D reconstruction of a small object -a shell of abalone (Haliotidae) picked up on the study area (size about 5 ⇥ 3 cm). The inner side is challenging because of the nacre.

Thanks Marc Pierrot-Deseilligny for his with MicMac.

⇤ Thanks to the French Direction Générale de l'Armement (DGA) for the funding of this thesis, to Charenton-le-Pont city for diving and swimming pools access and to Fischer Connectors Society.


Micro-charges utiles dédiées à l'acquisition de données par drone pour l'étude des zones naturelles

Antoine Gademer, Loïca Avanthey, Laurent Beaudoin, Michel J. Roux,

Jean-Paul Rudant

To cite this version:


N Benzaoui

Y Pointurier

T Bonald

J.-C Antona

Impact of the electronic architecture of optical slot switching nodes on latency in ring networks

Keywords: Optical packet switching, Network performance, queuing model

Optical slot switching has formerly been proposed as a flexible solution for metropolitan ring networks to carry data traffic with a sub-wavelength switching granularity and with a good energy efficiency, which is enabled by optical transparency. In this paper, for the first time we propose several architectures for the electronic side of optical slot switching nodes to increase flexibility through the addition of electronic switches, working either at client packet granularity or at slot granularity; such electronic switches can be located at either transmitter side, receiver side, or both sides of a node, thereby decreasing traffic latency, at the expense of increased node cost and/or energy consumption. This paper focuses on the latency aspect. We investigate the impact of a timer that can be used to upper bound the slot insertion time on the medium. We also propose, a novel client packet queuing model in an optical slot switching ring and assess and compare the latency of these node architectures analytically, and with simulations.

I. INTRODUCTION

T he emergence and rapid growth of data traffic sources, such as CDNs (Content Delevery Network), nomad users and mobile applications, make the internet traffic unpredictable and bursty [START_REF] Korotky | Traffic trends: Drivers and measures of cost-effective and energy-efficient technologies and architectures for backbone optical networks[END_REF], especially in the access and metro segments. In this context, optical slot switching technologies were proposed for metro ring networks, to provide sub-wavelength switching flexibility in the optical domain [START_REF] Chiaroni | Packet OADMs for the next generation of ring networks[END_REF]- [START_REF] Deng | A novel optical burst ring network with optical-layer aggregation and flexible bandwidth provisioning[END_REF]. For instance, "POADM" (packet optical add-drop multiplexers) [START_REF] Chiaroni | Packet OADMs for the next generation of ring networks[END_REF] is a Wavelength-Division Multiplexed (WDM) time-slotted ring. It is composed of several (e.g., 40) data channels and one "control channel" which carries all slot headers and is electronically processed at each node. Each node is connected to one or several clients (e.g., an Optical Line Terminal of Passive Optical Network, an Ethernet switch, etc.). Data coming from/going to the clients is encapsulated/decapsulated within fixed-size packets called slots with a duration of few µs that can transit transparently, i.e. they are not converted to the electronic domain at the intermediate nodes [START_REF] Chiaroni | Packet OADMs for the next generation of ring networks[END_REF]. Each node decides whether to drop or to let transit each slot on each wavelength according to the information carried by the control channel. This transparency reduces energy consumption [START_REF] Pointurier | Dimensioning and energy efficiency of multi-rate metro networks[END_REF]. Each POADM node includes one or several burst-mode fixed-wavelength receivers (Rx), making the nodes able to receive data on predefined wavelengths, and one or several fast wavelength-tunable transmitters (Tx), which enable each node to communicate with every other node by tuning to the right wavelength on a per-slot basis [START_REF] Simsarian | Wavelength locking a fast-switching tunable laser[END_REF].

N. Benzaoui, Y. Pointurier and J.-C. Antona are with from Alcatel-Lucent Bell Labs, Nozay, France.

T. Bonald is with Telecom ParisTech and LINCS, Paris, France.

The POADM technology has received much attention in the past: regarding network dimensioning [START_REF] Ušćumlić | Traffic grooming in WDM optical packet rings[END_REF], [START_REF] Ušćumlić | Optimal dimensioning of the WDM unidirectional ECOFRAME optical packet ring[END_REF], energy consumption [START_REF] Pointurier | Dimensioning and energy efficiency of multi-rate metro networks[END_REF], technological issues [START_REF] Simsarian | Wavelength locking a fast-switching tunable laser[END_REF], and MAC, performance and QoS management [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF]- [START_REF] Eido | Packet filling optimization in multiservice slotted optical burst switching MAN networks[END_REF]. However, mapping issues between clients and nodes were never considered. In a plain, basic POADM node, clients are statically mapped to transponders (TRX; a transponder is a Tx and an Rx) or line cards. However, allowing a client to use any Tx or Rx at a given node provides more flexibility to send/receive data, and hence has a significant impact on network dimensioning and performance, measured for instance in terms of latency. Previous performance studies for optical slot switching networks considered client [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF]- [START_REF] Eido | Packet filling optimization in multiservice slotted optical burst switching MAN networks[END_REF] packet aggregation into slots and slot insertion on the medium as separate processes, making assumptions on the latter that are uncorrelated with the aggregation mechanism output. We propose for the first time an end-to-end performance analysis that includes both client packet aggregation and slot insertion.

The contribution of this paper is two-fold. First, we propose several optical slot switching node architectures enabling dynamic client/WDM TRX mapping, at several granularities (client packet or optical slot). Second, we assess the performance of each node architecture, essentially in terms of queuing delay, by analysis and simulation. The analytical performance evaluation is done using a new model based on queuing theory. Note that this paper applies to any WDM slotted ring where nodes are equipped with tunable transmitters and fixed-wavelength receivers; POADM is one possible implementation of this concept. This paper is also applicable to optical slot switching variations of the POADM concept such as [START_REF] Stavdas | Dynamic CANON: A scalable multidomain core network[END_REF]- [START_REF] Deng | A novel optical burst ring network with optical-layer aggregation and flexible bandwidth provisioning[END_REF]. Also, fairness issues, which could be handled by a specific MAC, are out of the scope of this paper. Note that, as shown by [START_REF] Ušćumlić | Network planning and traffic engineering in ecoframe optical packet ring[END_REF], there is no fairness problem as long as the network is correctly dimensioned, i.e. to carry load close to 1 without loss.

This paper is organized as follows. In Section II, we present the basic and alternate architectures of our optical slot switching node. In Section III we describe the optical slot filling and insertion process. Latencies for those architectures are derived analytically in Section IV and validated using simulations in Section V. We give in Section VI the most important conclusions of the performance studies.

II. NODE ARCHITECTURES

A POADM node is able to encapsulate and decapsulate client traffic into fixed-duration optical packets or "slots". In addition, a POADM node can add, drop, and let optical slots transit on an optical ring. Hence, a POADM node consists an optical packet blocking fabric with the relevant controller, and line cards (TRX) directly connected to the metro ring to transmit and receive optical slots. We focus here solely on the client and line cards of POADM nodes, and we propose several solutions to electrically interconnect them within a node. Fig. 1 depicts the reference network for this study and Fig. 2 the investigated node architectures. The network described in Fig. 1 is a ring with 4 POADM nodes (N n , with node index n = 1, . . . , 4) and 2 clients per node (C n,i with node index n and client index i=1 or 2). For the sake of clarity, packet blockers located between the transmitters and the receivers are not depicted, see [START_REF] Chiaroni | Packet OADMs for the next generation of ring networks[END_REF] for details. This ring supports here two wavelengths w 1 and w 2 .

A. Basic node architecture

In the first architecture, each client is mapped via a (L2) client card, to a TRX (line card) as illustrated in Fig. 2a. Recall that, with the tunable Tx on the line side, a client can send its traffic on any wavelength, but the client is always mapped to a predefined wavelength for reception. In Fig. 1, for example, if client C 2,2 on node N 2 is mapped to wavelength w 2 , then C 1,2 must use w 2 to reach client C 2,2 on N 2 . Since each pair (client card, line card) is independent, an optical slot can be formed only with packets from the same source client to the same destination client; thus in the previous example an optical slot carrying traffic from C 1,2 to C 2,2 only contains packets from C 1,2 to C 2,2 .

B. Client packet electronic switch (c-switch)

To enhance the flexibility of the previous architecture and remove the fixed mapping between client and wavelength of the basic architecture, we propose to include, either at transmitter or receiver (or even both) side, an electronic switch working at client packet granularity, further denoted by "cswitch". For instance, if the metro ring carries Ethernet traffic, those switches could be implemented with Ethernet switching fabrics. Note that this enhanced flexibility (and improved performance, as will be seen in Section IV), comes at the cost of adding at each POADM node one or two electronic switches working at the client packet granularity 1 . When a client packet switch is used at the transmitter side (Fig. 2b), the same line card will be shared between several clients (of the same node), such that packets coming from different clients can be encapsulated in the same optical slot, under the condition that these packets have the same (client and node) destination. In this configuration, the electronic client packet switch is placed at receiver (Fig. 2c), such that several clients can receive traffic encapsulated in the same optical slot. In this case, the optical slots are filled with packets coming from a single client on a source node, going to several clients on the destination node.

C. Slot electronic switch (s-switch)

We also propose to consider a less expensive, due to simpler switching fabric, and less energy consuming2 electronic switch operating at slot granularity rather than client packet granularity. This switch is further denoted by "s-switch" and is placed between the client and the line cards as illustrated in Fig. 2d, to ensure a flexible mapping between clients and wavelengths. Note that fast (slot-granularity) wavelength tunability, already present at the Tx side, provides the same functionality as an electronic slot switch, therefore the scenario with an electronic slot switch at Tx is not considered here, and only scenarios where this switch is located at the Rx side are considered. This switch enables the mapping of client cards to line cards at the slot (rather than client packet) granularity: it can be seen as an intermediate scenario between the no-switch case (Section II-A) and the client packet switch case (Section II-B).

D. Combinations of c-switches and s-switches

In addition to the aforementioned scenarios, we can also consider a combination of electronic switches at client packet granularity (at Tx, Fig. 2b; and/or Rx side, Fig. 2c) and at slot granularity (at Rx side, Fig. 2d), resulting in 8 possible node architectures overall.

III. OPTICAL SLOT FORMATION AND INSERTION PROCESS

In this section we describe the mode of working of a POADM ring at a client packet level and take it as a basis for the analytical model in Section IV. We assume that all client packets have the same size (in bits) taking as a reference the benchmarking methodology of [START_REF]RFC2544: Benchmarking Methodology for Network Interconnect Devices[END_REF]. After being sent by the clients the packets are placed in a temporary packet queue waiting for the completion of the optical slot formation process. These client queues are emptied after the arrival of K packets, K being the number of packets necessary to fill an optical slot with:

K = slot size [in bit] packet size [in bit] . (1)
This implies that the first K -1 packets must wait for the arrival of the K th packet before being sent. One of the purposes of this paper is to show the impact of this optical slot filling time denoted by OSFT on the overall optical slot switching network latency.

After their formation the optical slots are queued in an optical slot queue. If there is no switch at the reception side, the optical slot queues are identified by the reception wavelength of the destination client, then by the pair (source node, destination client). Otherwise, if the node encompasses a switch at the reception side (either c-or s-switch) the optical slot queues are identified by the pair (source node, destination node). Indeed, as explained in Section II, the presence of switch at Rx side, in combination with tunable Tx, allows to share the wavelengths over the client sources on a same node and the constraint of having one optical slot queue per wavelength is relaxed. For simplicity, in the following we use the term queue to designate the optical slot queue.

One way to reduce the impact of the optical slot filling time on the latency is to upper bound it using a timer. The timer is initialized at the arrival of the first packet in the temporary packet queue. Its expiration instantly causes the ending of the optical slot formation process. The slot is queued in order to be sent in the channel. Hence the timer triggers the sending of the optical slot even if it is not fully filled. In this case the queue extraction will be done after the arrival of X packets with X depending on the packet arrival process, and 1 ≤ X ≤ K. The timer has the advantage of limiting the latency, but as we will see in Sections IV-B2 and V-B2, it has also the drawback of wasting the offered channel capacity due to unfilled slots.

When several flows are feeding the same optical slot, their superposition is equivalent to a single flow with a mean client packet arrival rate equal to the sum of the packet arrival rate of each flow. The optical slot filling time decreases with the client packet arrival rate increase, helping to better (or even fully) fill the optical slot before the timer expiration. Therefore, the optical slot filling time and ratio depend on the number and the size of flows participating in its filling. This process is called flow aggregation. Flow aggregation capability and hence network performance (queuing delay) strongly depends on the node architecture.

IV. QUEUING MODEL AND ANALYSIS

We define the packet queuing delay as the waiting time elapsed between the sending of packets by the source client and their insertion on the channel. Thanks to transparency (no optoelectronic conversion at intermediate nodes) the end-toend latency can easily be calculated from the queuing delay by adding to it the propagation delay, which is deterministic for a given physical topology. The queuing delay results from the optical slot formation process and the waiting time spent in node buffers. The buffering time is directly related to the congestion of the channels, since the optical slot formation time depends on the source client mean arrival rate λ, and then strongly depends on the node architecture. In this section we describe the queuing model and we present analytical model. we also quantify and discuss the gain on performance brought by each node architecture in presence or not of timer.

A. Queuing model and notation

From the above definition, the Mean Packet Queuing Delay MPQD is the sum of the Mean Optical Slot Filling Time MOSFT , which is the mean time spent in the client queue waiting for the completion of the optical slot formation process, and the Mean Queuing Time M QT , which is the mean time spent in the queue waiting for the insertion of the optical slot on the channel, and hence:

MPQD = M QT + MOSFT.
(

) 2
The model is based on a client to client traffic with Poisson packet arrivals, where the mean packet arrival rate is λ, and a service rate µ, which is equal to the inverse of the fixed optical slot duration. We define D s,i,d,j (in b/s) as the traffic demand of (client-layer) data flow (s,i,d,j) from client i on node s to client j on node d, with λ = D s,i,d,j /packet size.

The optical slot filling process can be simplified as a group of, on average, X packet arrivals before being served (inserted on the channel). The slot arrival process then follows a Gamma distribution with a shape parameter r, where r = X, and a scale parameter 1/λ. This Gamma distribution corresponds to a sum of X independent exponentially distributed random variables. Since the optical slots are sent on a time slotted channel in a deterministic way the corresponding model is then a Gamma/D/1 queue. If X is an integer, then the distribution is an Erlang distribution, which is a special case of the Gamma distribution. In this case the model is an Erlang/D/1 queue.

B. Analysis

In this section we propose to calculate the Mean Packet Queuing Delay by computing each term (Mean Queuing Time and Mean Optical Slot Filling Time) of ( 2), without and with a timer.

1) Without timer: Without timer, the arrivals are grouped into sets of K packets before being served. This description corresponds to an Erlang/D/1 model. In order to get explicit expressions it is necessary to approximate this queue by a more common one. We propose to approximate the Erlang/D/1 queue by an M/D/1 queue with parameter (λ, rµ) 3 . The mean queuing delay 4 for an M/D/1 with parameters (λ, µ) is given by [START_REF] Chan | Pollaczek-Khinchin formula for the M/G/1 queue in discrete time with vacations[END_REF]:

POADM

M QT M/D/1 = 1 2 • 1 µ • ρ 1 -ρ , (3)
with ρ = λ/µ. From (3) and considering that since the channel is time slotted an optical slot has to wait on average half a time slot before being inserted on the channel, we derive the mean queuing time for an Erlang/D/1 as:

M QT ≈ 1 2 • 1 rµ • ρ 1 -ρ + 1 2µ , (4)
where ρ = λ/(rµ), and r = K. Without a timer, an optical slot is formed when it is fully filled (X = K). The Optical Slot Filling Time is then K -1 client packet inter-arrivals times:

OSFT = (K -1) • 1 λ . ( 5
)
Since the first packet waits for time OSFT , the last one for time 0 and the arrivals are uniformly distributed in the interval [0,OSFT ], the mean optical slot filling time is :

MOSFT = OSFT 2 = (K -1) • 1 2λ , (6)
and hence, using (2), ( 4) and ( 6), we have:

MPQD = 1 2 • 1 rµ • ρ 1 -ρ + 1 2µ + K -1 2λ . (7)
2) Using a timer: Using a timer T , the optical slot may no longer be fully filled before it is sent, and its filling ratio is calculated based on the probability of having X arrivals during time T with 1 ≤ X ≤ K. Considering a Poisson packet arrivals, the mean number of arrivals N (T ) during time T is:

N (T ) = ∞ n=0 n • P (N (T ) = n) = ∞ n=0 n • e -λT • (λT ) n n! . (8)
Since an optical slot contains at least one packet which triggers the timer (we are then interested in the probability of having K-1 arrivals during T ), and at most K packets, then we have:

X = E[min(N (T ), K -1)] + 1,
which is equal to:

X = 1 + K-1 n=0 n • e -λT • (λT ) n n! + • • • (K -1) • ∞ n=K e -λT • (λT ) n n! . (9)
After simplification, X is:

X = 1 + (K-1) - K-2 n=0 (K -1-n) • e -λT • (λT ) n n! . ( 10
)
If X is an integer, we are still considering an Erlang/D/1 system queue, and the new parameter r , for the slot departure process, which is the sum of independent exponentially distributed variables during an interval T , is:

r = X. ( 11
)
Otherwise X is not an integer we are no longer in the special case of an Erlang/D/1 queue, the queue model is a Gamma/D/1 with parameter (r ,1/λ). The above formulas are also valid with the Gamma/D/1 queue. When X < K, i.e. the load seen by the network or the emulated load is larger than the clients demand ρ (because of the slots which leave partially filled), this emulated load is:

ρ = ρ • K X , (12)
Hence, using (4), ( 11) and ( 12), we obtain:

M QT = 1 2 • 1 r µ • ρ 1 -ρ + 1 2µ . (13)
The Optical Slot Filling Time can vary when the timer is used. In the paragraphs below we showed how to calculate the mean optical slot filling Time MOSFT . Since the optical slots may be not fully filled (due to the early timer expiration), ( 5) and (6) do not apply every time. The Optical Slot Filling Time is either equal to the timer value or to the Optical Slot Filling Time if the slot is filled before the expiration of the timer. Given that the Optical Slot Filling Time maybe determined by the timer and no longer by the arrival of the K th packet, the last packet arriving in the optical slot before the expiration of the timer may wait for a positive time before the slot is sent. If the slot is sent upon expiration of the timer the first packet in the slot will wait for time T and the other X -1 packets wait, on average, for time T /2, otherwise if the slot is sent because it is full (before the expiration of the timer) all packets in the slot will wait, on average, for OSF T /2. We can express the Mean Optical Slot Filling Time as:

MOSFT = 1 X K-2 n=0 1 + n 2 • T • e -λT • (λT ) n n! + . . . K(K -1) • T 2 ∞ n=K-1 e -λT • (λT ) n n! . ( 14
)
MPQD is the sum of ( 13) and [START_REF] Pantaleo | Dynamic service differentiation in OBS networks[END_REF]. From ( 10) and ( 14) (which are applicable whether a timer is used or not), we can see that the mean optical slot filling time is directly related to the mean packet arrival rate of a client flow. As discussed in Section III when the client packet arrival rate increases the optical slot filling time decreases, as seen in ( 14), and the optical slots are better filled since X/K approaches 1, as seen in [START_REF] Bonald | SWING: Traffic capacity of a simple WDM ring network[END_REF]. The analysis given above confirms that the queuing delay and the usable channel capacity both strongly depend on the node architecture.

C. Validation of queuing and optical slot filling model

In this section we evaluate our analytical model, on a single wavelength POADM ring with 4 nodes and one client per node. Each client sends a single flow with intensity (offered load) β to the client of node 3 as described in Fig. 3. We assume a channel capacity of 10 Gb/s and a slot duration of roughly 8 µs.

Fig. 4a shows the Mean Packet Queuing Delay without a timer and Fig. 4b using a timer, for each node, obtained theoretically using (2), and by simulation using NS3. Recall that transit traffic has priority over the traffic inserted due to the optical transparency. Given that no MAC is used to ensure the fairness, node 2 can access the channel only when β < 1/3, node 1 can access the channel only when β < 1/2 while node 0 has no constraint and can use all the offered capacity. Indeed for β below 1/3, all nodes have equivalent access to the channel; when β approaches 1/3 the segment between node 2 and node 3 saturates because of the traffic sent by node 0 and node 1, and node 2 can no longer access the channel. When β approaches 1/2 the segment between node 1 and node 2 saturates because of the traffic sent by node 0, causing the loss of all client packets of node 2 and 3. High queuing delay and client packet losses are indicators of the limitation of channel exploitation. The aim of these comparisons is to validate the queuing model and to evaluate the accuracy of the MPQD formula (2), whether a timer is used or not. The analytical model fits with simulations with a mean error of 1% for loads ≤ 99%. This result confirms the coherence of the analytical model. In next sub-section, we derive analytical results for the gain brought by the c-switches in terms of slot filling time, or, equivalently, the client packet queuing delay assuming the absence of a timer capping the maximum slot filling time.

D. Performance gains with c-switches 1) No timer:

In the following we derive the gain in latency seen by the client layer thanks to c-switches at Tx, Rx, or both, in different network regimes. For the range of loads where congestion and losses are not significant the Mean Queuing Time is negligible and the Mean Packet Queuing Delay is dominated by the Mean Optical Slot Filling Time. In the absence of timer the queuing delay is given by (2), and can be simplified into:

MPQD ≈ 1 2µ + MOSFT. (15)
For this range of loads and in absence of timer, 1/2µ is negligible compared with MOSFT (MOSFT is considerably larger to 1/2µ), and we can consider:

MPQD ≈ MOSFT. (16)
Denote by GD A s,d the gain in Mean Packet Queuing Delay, using a node architecture A with respect to the basic architecture with no switch, for a flow from node s to d, and GT A s,d the gain in Mean Optical Slot Filling Time, (16) yields:

GD A s,d ≈ GT A s,d , (17)
with

GT A s,d = MOSFT no switch s,d MOSFT A s,d . (18)
In absence of timer the impact of the node architecture on the optical slot filling time is visible only on the queuing delay reduction (without timer there is no impact on load). If we consider a client layer flow (s, i, d, j), with no switch (neither at Tx nor Rx), using (5) the time to form an optical slot is:

OSFT no switch s,i,d,j = (K -1) • PS D s,i,d,j , (19)
where PS is the client packet size (in bit). The average slot filling time between s and d using ( 6) is:

MOSFT no switch s,d = K -1 2 • PS f s,d • i,j 1 D s,i,d,j , (20)
where f s,d is the number of flows from node s to node d. With a c-switch at Tx on node s, i.e. when all flows from all clients of s to some client j of node d are aggregated into a single flow with intensity A s,d,j = i D s,i,d,j , the time to form an optical slot is: OSFT s,d,j (c-switch at Tx) = (K -1) • PS A s,d,j . Let K d be the number of aggregated flows from s to d, i.e. K d is the number of clients on node d. The Mean Optical Slot Filling Time from s to d is then:

MOSFT T x s,d = K -1 2 • PS K d • j 1 A s,d,j . (21)
Hence, using ( 17), ( 20) and ( 21), the gain in queuing delay (during the slot formation process) for flow (s, i, d, j) brought by the presence of a c-switch at Tx side is:

GD T x s,d = MOSFT no switch s,d MOSFT T x s,d = K d f s,d • i,j 1 D s,i,d,j j 1 A s,d,j . (22)
By symmetry, in the scenario with c-switch at Rx, where flows from one source client to several destination clients are aggregated within the same stream of optical slots, the gain is:

GD Rx s,d = MOSFT no switch s,d MOSFT Rx s,d = K d f s,d • i,j 1 D s,i,d,j j 1 B s,i,d , (23)
where

B s,i,d = j D s,i,d,j .
When both source node and destination node are equipped with a c-switch, flows from all clients of a node s to all clients of a node d are aggregated into a single flow with intensity E s,d = i,j D s,i,d,j , the time to form a slot from s to d is:

MOSFT s,d (c-switch at Tx and Rx) = K -1 2 • PS E s,d . (24)
Using ( 17), ( 20) and (24)the gain in slot filling time brought by a c-switch at both Tx and Rx is thus:

GD T x+Rx s,d = E s,d f s,d • 1 i,j 1 D s,i,d,j . (25)
For the range of loads for which congestion occurs on the network and is significant, the Mean Queuing Time MQT is no longer negligible. In this case the simplification done Clients/nodes/wavelengths mapping and traffic demand, n, m = 1 , . . . , 4 , n = m; in previous paragraph is no longer possible, and the gains, only for ρ < 1 such that MQT is finite, must be calculated using (7);

GD A s,d = MQT + MOSFT no switch s,d M QT + MOSFT A s,d . (26)
2) With timer: As seen in ( 12) the use of a timer may cause the sending of optical slots that are not fully filled, hence the client traffic demand perceived by the network is higher then effective offered one. Unlike the case where no timer was used, here, the node architectures intervenes on both Mean Optical Slot Filling Time and Mean Packet Queuing Time but also on the maximum supported load by modifying the mean number of packet arrivals (λ) during an interval of time T . The utilization of c-switches will lead to aggregate flows for filling the same optical slots, which help to increases λ and X, as seen in ( 10) when λ increases X approaches K. The higher the intensity of the resulting aggregated flow, the lower the impact of the timer on exploitable channel capacity will be, thereby keeping the queuing delay under the timer value. For low loads the performance brought by the different node architectures can be negligible GD A s,d ≈ 1, since the use of timer leads to obtain the same MOSFT for all the architectures. for the other load regimes [START_REF] Eido | Packet filling optimization in multiservice slotted optical burst switching MAN networks[END_REF] and (26) are used.

E. Performance impact of s-switches

The s-switch have no impact on flow aggregation, and their impact cannot be measured in terms of latency when the network is not congested. Its usefulness is appreciable in the cases where the load sharing is needed, as seen in the next section.

V. PERFORMANCE STUDIES

A. Simulation scenario description

We evaluate the aforementioned node architectures for network performance (latency) using the analytical model and using a custom-made NS3-based network simulator to validate the analytical model on complex cases. The POADM unidirectional ring (a second direction could be used for protection) consists of 4 nodes, each connected to 2 clients, and 2 wavelengths. As seen in Fig. 1 each node can transmit and receive on the two wavelengths via two transponders (fast tunable Tx + colored receiver Rx); Fig. 5 shows the wavelengths/node/client mappings and the client traffic demand. Each flow (s, i, d, j) is assumed to consist of fixed-size client packets of size

D s,i,d,j 2•W R
where W is the number of wavelengths and R the capacity of each wavelength. Factor 2 comes from the fact that each slot cross on average a distance of 1/2 ring.

B. Performance for uniform traffic

1) Without timer: We evaluate the 8 node architectures resulting from the combinations of a client packet switch (at transmitter and/or receiver) and/or an optical switch at receiver. We assume traffic is uniform, i.e. a = b = c = d in the demand matrix (Fig. 5).

Fig. 6a and Fig. 6b show respectively simulation and analytical results for queuing delay for different loads and for each node architecture. Comparing these two figures, it appears that the analytical model and the simulation results have the same shape, and actually fit with an error of less then 1% for loads below <0.95, the maximum analytical supported load (above which congestion and losses occur, and queuing delay diverges) is in agreement with the simulation results. Due to the symmetry of the traffic matrix, for high loads (>0.96) the ring is in an unstable regime which leads to have a queuing delay slightly higher than the analytical model. At low loads (e.g., load < 0.4), the inter-arrival time of packets at each node is large, leading to a large optical slot filling time, and hence relatively large queuing delay. At medium and high loads (e.g., 0.4 < load < 0.95), the optical slot filling time decreases, reducing the queuing delay. At very high loads ( > 0.95), the buffering time is no longer negligible and queuing delays increase quickly due to the congestion of the network rather than increasing optical slot filling time; in fact the large number of arriving packets per second leads to fast formation of slots.

Impact of s-switch:

In the uniform traffic scenario, the load is balanced on the 2 wavelengths by construction and the addition of an s-switch at reception (which, as will be seen further, enables wavelength load balancing) brings no gain, hence in Figs. 6a and6b the curves with and without s-switch are identical.

Impact of c-switch

Architectures with a c-switch at either Tx or Rx aggregate, respectively, the flows from several clients (on the same source node) to the same destination client (c-switch at Tx, Fig. 2b), or the flows from one client to several clients (on the same destination node) (c-switch at Rx; Fig. 2c). Flows are uniformly distributed over all pairs of clients, hence the packet inter-arrival times for the aggregated flows are equal for both cases (c-switch at either Tx or Rx) resulting in identical queuing delays. In the load regime where queuing delay is dominated by slot filling times (load < 0.95 ) and when cswitch is used at either Tx or Rx, using ( 22) and (23) (for any (s,d) pair) the gain in queuing delay w.r.t the no-switch architecture is GD T x s,d = GD Rx s,d ≈ 2. This can be verified in Figs. 6a and 6b in absence of congestion, for high loads where congestion occurs, the gain can be calculated using (26).

The largest reduction in queuing delay is provided by the architecture with c-switches at both Tx and Rx. This is due to the larger number of aggregated flows, leading a higher reduction of the optical slots filling time, compared to the other architectures, and a better pooling of the network resources (Tx, Rx, wavelengths) across the clients. In this case the gain in latency w.r.t. the no-switch scenario is GD T x+Rx s,d ≈ 4 (see ( 25)). This can be verified in Fig. 6a and Fig. 6b for low and medium loads; for high loads the gain can be calculated using (26).

2) With timer: Fig. 7a presents the simulation results of the same previous simulation scenario, now with a timer value T = 15 slots (i.e. 120 µs). Fig. 7b presents the analytical results. Here again we can see that the analytical model and the simulation results match very closely. We notice, compared with Fig. 6a and Fig. 6b, that the queuing delay is effectively bounded by the slot filling time (=15 slots) for the lower loads, until congestion occurs at higher loads. As discussed in Section IV, the timer can negatively impact the system by causing a waste of capacity. This impact, using a timer value of 15 slots is minimal (reduction of maximum supported load from 0.98 to 0.97) and visible only for node architectures without switches.

The use of a timer of less then 15 slots can results in packet losses; a timer of 15 slots is a reasonable value since there is no loss for loads lower than 0.95. Hence, in all further simulations, we use a timer value of T = 15 slots. In order to refine the node architectures comparison, we modify the traffic matrix; we assume now that a = c and b = d but a << b. In this case the traffic matrix is uniform at the node level (each node sends/receives the same quantity of traffic) but not at the client level, such that the two wavelengths carry a different amount of traffic (traffic sent by each node: 6a on w 1 and 6b on w 2 ). The behavior of the network differs depending on whether a is small or large, as seen below.

Fig. 8a shows the simulation queuing delay results, for each node architecture, for a = 50 Mb/s and b varying between 50 and 1570 Mb/s. Fig. 8b shows the analytical results of the queuing delay. Analytical and simulation curves essentially fit, however some curves in the simulation plot reach a plateau due to the limitation of buffer size while the analytical model assume an infinite buffer size.

Impact of s-switch:

In the absence of a switch at the receiver side, there is no possibility to balance the load over the wavelengths, resulting in a rapid increase of the queuing delay and important losses at load higher than 0.5 (the plateau in Fig. 8a corresponds to the congestion of w 2 , buffers overflows, and important losses, while w 1 is lightly used), corresponding to the maximum capacity supported by a single wavelength. Using an s-switch at Rx enables load balancing and removes the plateau.

Impact of c-switch: Since the traffic is not symmetric, the slot filling time varies depending on whether aggregation of the client flows is enabled by a c-switch at Tx or at Rx. When queuing delay is dominated by slot filling times (0.4 <load < 0.95), when c-switch is used at Tx only, using [START_REF] Ušćumlić | Network planning and traffic engineering in ecoframe optical packet ring[END_REF] (for any (s,d) pair) the gain in Mean Optical Slot Filling Time w.r.t the no-switch architecture is GT T x s,d = 2. This cannot be seen directly on Figs. 8a and8b, since even at these loads the network starts to be congested because of the use of the timer, making M QD no longer negligible and then GD T x s,d = GT T x s,d . The gain in queuing delay must be calculated using (26). However, the absence of a switch at Rx results in a plateau, as explained above.

Using a c-switch at Rx removes the latency plateau (see Section V-D). When queuing delay is dominated by slot filling times, the gain in Mean Optical Slot Filling Time with cswitch at Rx only is larger than with a c-switch at Tx only:

GT Rx s,d = (a + b) 2 /(2ab) > 2.
This tendency is also confirmed for the gain in queuing delay obtained using (26).

When a c-switch is used at both Tx and Rx the timer has no impact and the system is in a stable load regime; MPQD ≈ MOSFT making GD The maximum load supported by the network strongly depends on the node architecture. Figs. 8a and8b show that the highest supported load is below 0.75 using the node architecture without c-switches, 0.86 using the c-switch at Tx, 0.95 using c-switch at Rx and 0.95 with switches at both Tx and Rx. For certain node architectures, enumerated below, queuing delay diverges before load = 1 because the channel capacity is exceeded. Indeed, with a timer (with value T ) the optical slots are not fully filled ( X/K < 1), which leads to have an emulated load seen by the network superior to the real demand as seen in [START_REF] Hacimeroglu | Impacts of packet filling in an optical burst switching architecture[END_REF]. The architectures with no c-switch, do not offer the possibility of client flows aggregation, and it can easily be shown that for T = 15 slots a flow consuming a capacity of 600 Mb/s is generated by the client even if its real demand is below 600 Mb/s. In the presence of c-switches at both Tx and Rx, the slot filling time is always below T and optical slots are always completely filled, ensuring that all channels capacity can be used, leading to a low queuing delays even for loads very close to 1. For the architectures with c-switches at either Tx or Rx, the slot filling time is below T but is larger than the one with c-switch at both Tx and Rx. This allows a higher channel use than with the basic architecture, but lower than with the architecture with both c-switches. D. Performance for non-uniform traffic, with timer,a = b,c = d, a << c

In this case the traffic matrix is again uniform at the node level but not at the client level; however the traffic demand is now uniformly distributed over the two wavelengths. As in Section V-B1, queuing delays relative to the basic architecture and the architecture with s-switch at Rx are the same. Fig. 9a shows the simulation results for a = 50 Mb/s and b = c ∈ [50, 1570] Mb/s. Fig. 9b shows the analytical results. Compared with Section V-C, the delays of the median curves are reversed, i.e. the electronic switch at Tx side significantly reduces latency and decreases the capacity wasted through the use of the timer, w.r.t. the use of electronic switch at Rx side. In the load regime where queuing delay is dominated by slot filling times, when c-switch is used at Rx only, using [START_REF] Ušćumlić | Network planning and traffic engineering in ecoframe optical packet ring[END_REF] no-switch architecture is GT Rx s,d = 2. The gain in Mean Optical Slot Filling Time is larger: GT T x s,d = (a + c) 2 /(2ac) > 2 when a c-switch is used at Tx only; when a c-switch is used at both Tx and Rx the gain is doubled:

GT T x+Rx s,d = (a + c) 2 /(ac).
It is easily verified that the values for the uniform case are obtained for a = b in the expressions above. Following the reasoning given in Section V-C, the gain in queuing delay using a c-switch at Tx or Rx can be calculated using ( 26 Hence, we shown that the impact of the optical slot filling process depends on the absolute value of the resulting data rate of client flow aggregation, and that the optical slot filling process has an impact on network performance even at medium and high loads.

E. Trade-off between queuing delay limitation and optical slot filling ratio

Fig. 10 represents the optical slot filling ratio ( X/K) for different timer values according to the aggregated client flow intensity, i.e. the intensity of the flows after aggregation by the c-switches, if any. Note that Fig. 10 is applicable to all architectures. As expected, for the same timer value, when the aggregated flow intensity increases, the optical slot filling ratio tends to 1 meaning that the load that can be carried in the network also increases. This is because a larger aggregated flow intensity leads to a faster filling of the optical slots as explained in Section IV. Fig. 10 shows that it is possible to find a trade-off between latency limitation and capacity wastage by selecting an adequate timer value and/or an adequate node architecture. Indeed, note that there is a mapping between the network load and the aggregated flow intensity (x-axis in Fig. 10), which depends on the node architecture. For instance, for a given demand, adding c-switches allows the aggregation of client flows leading to larger resulting flow intensity. Hence, for a given demand, the addition of c-switches increases the aggregated flow intensity, which in turn leads to a larger optical slot filling ratio. In other words, for a given latency constraint (a timer value) the addition of a c-switch increases the maximum supported network load, or, equivalently, reduces the capacity waste. Table I summarizes the maximum achievable network load to ensure a queuing delay below 200 µs, for each node architecture. Architectures without any switch at Rx do not support some of the traffic demands (dark grey cells), because of their inability to balance the load, as seen above. The architectures with c-switch at either Tx or Rx (light grey cells) permit to support a higher load (at least 75%), depending to the aggregated traffic. The architectures with c-switch at both sides (white cells) sustain the highest load (more than 95%).

VI. CONCLUSION

In this paper we proposed and compared the performance (in terms of client packet queuing delay and maximum supported load) of different possible electrical architectures for optical slot switching nodes, embedding electrical switches at two possible granularities: client packet and/or slot, at Tx and/or Rx. The comparison was done analytically using a queuing model for optical slot switching ring and by simulation using a custom-made NS3-based network simulator. Architectures without any switch at Rx do not support all traffic scenarios (matrix of traffic demands), because of their inability to balance the load. The architectures with c-switch at either Tx or Rx permit to support a higher load, depending to the aggregated traffic. The architectures with c-switch at both sides sustain the highest load. Although the basic node architecture with no electrical switch presents the worst queuing delay in all simulated scenarios, this worst case never exceeds a relatively low value in the order of magnitude of 100 µs at loads below 75%. This node architecture presents the advantage of lower cost and consumption with respect to the other architectures. However, with small flows, slots are filled slowly and we have to use a timer to bound the queuing delay. With the basic node architecture the timer results in a poorly filled slots and a waste of channel capacity; and in an increase of queuing delays and large packet losses at high loads. The lowest queuing delay is achieved with client packet switches at both Tx and Rx sides. This architecture permits to reduce the time of optical slot formation while ensuring a high optical slot filling rate and hence better use of all network resources (Tx/Rx capacity, channel capacity). The use of a client packet switch at Tx or Rx presents intermediate performance, heavily depending on the number and intensities of the aggregated client flows. The use of an electronic slot switch at Rx enables load balancing. The node architecture with this switch only does not permit flow aggregation and is therefore less efficient than those with client packet switches. In this paper we focused solely on performance analysis and the quantified trade-off in terms of CAPEX (or energy) for the various architectures was not evaluated. Future work will consider joint CAPEX and performance analysis of optical slot switched networks.

Fig. 1 .

 1 Fig. 1. Optical slot switching ring, 4 nodes and 2 clients per node.

Fig. 2 .

 2 Fig. 2. POADM Node Architectures

Fig. 3 .

 3 Fig. 3. A simple 4-node scenario.

Fig. 4 .

 4 Fig. 4. Queuing delay for a simple 4-node scenario. Here Cx,y stands for the flow sent by client x on node y

  Fig. 5.Clients/nodes/wavelengths mapping and traffic demand, n, m = 1 , . . . , 4 , n = m;

  C. Performance for non-uniform traffic, with timer, case:a = c, b = d, a << b

  -switch at both sides Tx and Rx bring a gain even larger than the one with c-switch at either Rx, and GD T x+Rx s,d = (a + b) 2 /(ab).

Fig. 10 .

 10 Fig. 10. Trade-off between flow intensity, timer value and optical slot filling ratio.

  ), with GD Rx s,d > GD T x s,d , and the gain in queuing delay with c-switch at both Tx and Rx is GD x+Rx s,d ≈ GT T x+Rx s,d = (a+b) 2 /(ab).

  PS = 558 5 bytes, which corresponds to a typical average packet size in an IP network[START_REF] Sinha | Internet Packet Size Distributions: Some Observations[END_REF], and client packet arrival for each flow is Poisson 6 . Slots can be electronically buffered once they are formed; at each client a buffer can contain up to 50 slots. The reported queuing delays only account for packets successfully received and client packets lost due to congestion are ignored. In the following we define the network load as the total traffic demand (

		800	No switch			Tx: c-sw.; Rx: no switch	800	(No switch), (Tx: none; Rx: s-sw)
			Tx: no switch; Rx: c-sw.	Tx and Rx: c-sw.				(Tx: c-sw.; Rx: no switch), (Tx: c-sw.; Rx: s-sw.)
		700	Tx: none; Rx: s-sw		Tx: c-sw.; Rx: s-sw.		700	(Tx: no switch; Rx: c-sw.), (Tx: none; Rx: both sw.)
			Tx: none; Rx: both sw.		Tx: c-sw.; Rx: both sw.		(Tx and Rx: c-sw.), (Tx: c-sw.; Rx: both sw.)
	Queuing (µs) Mean Queuing	400 500 600 200 300	No C-Switch No C-Switch C-Switch at either Tx or Rx C-Switch at both Tx and Rx		Queuing delay (µs) Mean Queuing	400 500 600 200 300		No C-Switch No C-Switch C-Switch at either Tx or Rx C-Switch at both Tx and Rx
		100							100
		0							0
		0	0.2	0.4	0.6	0.8	1	Load	0	0.2	0.4	0.6	0.8	1	Load
			(a) Simulation						(b) Analysis
	Fig. 6. Mean packet queuing delay without timer, symmetric demand

s,i,d,j D s,i,d,j ) normalized by twice the network capacity (2W R): load = s,i,d,j

  (for any (s,d) pair) the gain in Mean Optical Filling Time delay w.r.t the

			T=16.11µs (2Tp)	T=32.22µs (4Tp)	T=48.33µs (6Tp)
			T=64.48µs (8Tp)	T=80.56µs (10Tp)	T=96.6µs (12Tp)
			T=113µs (14Tp)	T=120µs (15Tp)	T=201µs (25Tp)
			T=242µs (30Tp)	T=322µs (40Tp)
		1
		0.9
	Filling Ratio Optical Slot Filling	0.6 0.7 0.8 0.1 0.2 0.3 0.4 0.5 0.6
		0		Timer increases
		0	0.2	0.4	0.6	0.8	1
					Flow intensity (Gb/s)

TABLE I MAXIMUM

 I ACHIEVABLE LOAD TO ENSURE A QUEUING DELAY BELOW 200 µS.

		Symmetric	Asymmetric	Asymmetric
		traffic	traffic	traffic
		a=b=c=d	a=c,b=d	a=b,c=d
		(Fig. 6a	(Fig. 8a)	(Fig. 9a)
		Fig. 7a)
	No switch.	>0.95	0.5	0.75
	Tx: c-sw.	>0.95	0.5	>0.95
	Rx: c-sw.	>0.95	>0.95	0.86
	Tx : c-sw. Rx: c-sw.	>0.95	>0.95	>0.95
	Rx: s-sw.	>0.95	0.75	0.75
	Tx: c-sw.; Rx: s-sw.	>0.95	0.86	0.75
	Rx: c-sw + s-sw.	>0.95	>0.95	0.86
	Tx: c-sw.; Rx: c-sw + s-sw.	>0.95	>0.95	>0.95

The introduction of electronic switches increases the energy consumption and the cost of the POADM equipment. Although today, for low data-rates the cost of electronic technology can be neglected compared to the optical technology, it is nevertheless an additional cost to take into account.

The s-switch demands less computational power; the power consumption of electronic switches typically depend on the number of decisions per second, by design a c-switch performs K decisions when an s-switch performs only one decision, where K is the average number of client packets per slot.

We validated this approximation by simulation, not shown here, but the validation of the whole analytical model implicitly validates this approximation.

[START_REF] Yuang | HOPSMAN: An experimental testbed system for a 10-Gb/s optical packet-switched WDM metro ring network[END_REF] The insertion time of the optical slot itself on the channel is not included in the mean queuing delay, and since it is a common fixed duration for all optical slots we consider it as a constant to be added to the propagation delay to calculate the end to end latency

The choice of a 558B packet size comes from the fact that when a network is tested with the smallest or largest size, it would result in stressing a specific capacity. A medium value which is between typical internet packet sizes is an average case for those two extreme capacities. Note that in the analytical model the packet size is only a parameter and can easily be modified.

100 ms-long simulations are run, Typically a simulation corresponds to the generation of a few several hundreds of thousands of client packets. The client-card and line-card rate is set to 10 Gb/s. The slot duration is set to roughly 8 µs, corresponding to 18 client packets.

ACKNOWLEDGMENT

This work was partly supported by the CELTIC+ SASER-SAVENET project.

No switch Tx: c-sw.; Rx: no switch Tx: no switch; Rx: c-sw.

Tx and Rx: c-sw. Tx: none; Rx: s-sw Tx: c-sw.; Rx: s-sw. Tx: none; Rx: both sw.

Tx: c-sw.; Rx: both sw.

Queuing