Christoph Schmidt-Hieber
email: christoph.schmidt-hieber@pasteur.fr

Gabija Toleikyte

Laurence Aitchison

Arnd Roth

Beverley A Clark

Tiago Branco

Michael Häusser
email: m.hausser@ucl.ac.uk

Active dendritic integration as a mechanism for robust and precise grid cell firing

Keywords:

Understanding how active dendrites are exploited for behaviorally relevant computations is a fundamental challenge in neuroscience. Grid cells in medial entorhinal cortex represent an attractive model system for addressing this question, as the computation they perform is clear: they convert synaptic inputs into spatially modulated, periodic firing. Whether active dendrites transform synaptic input into the dual temporal and rate codes characteristic of grid cell output is unknown. We show that dendrites of medial entorhinal cortex neurons are highly excitable and exhibit a supralinear input-output function in vitro, while in vivo recordings reveal membrane potential signatures consistent with recruitment of active conductances. By incorporating these nonlinear dynamics into grid cell models, we show that they can sharpen the precision of the temporal code and enhance the robustness of the rate code, thereby supporting a stable, accurate representation of space under varying environmental conditions. Our results suggest that active dendrites may therefore constitute a key cellular mechanism for ensuring reliable spatial navigation.

Active, voltage-dependent conductances in neuronal dendrites transform the relationship between synaptic input and neuronal output 1,2 . The resulting enrichment of the integration capabilities of single neurons has long been suggested as being exploited for computations relevant to behavior 3,4 . However, the details of how specific active-dendritic mechanisms are involved in behavioral computations have proved to be elusive. Recent work has provided evidence that the active properties of dendrites are engaged in somatosensory and visual cortical neurons during sensory processing [5][6][7][8] . Moreover, dendritic nonlinearities also appear to be activated during behavioral tasks involving spatial navigation [9][10][11] . While these studies have provided important correlative evidence that dendritic mechanisms are engaged under

various circumstances, they do not provide a quantitative link for explaining how specific biophysical mechanisms can contribute to behavioral computations.

Grid cells in medial entorhinal cortex (MEC) represent a particularly attractive model system for linking cellular and circuit mechanisms to a behaviorally relevant computation.

Grid cells exhibit a striking spatial code, with firing fields that span the environment of a navigating animal in a periodic hexagonal pattern, and have thus been proposed as representing a neural mechanism for path integration 12 . Moreover, there exist several welldeveloped single-cell and network models of grid cell generation [13][14][15][16][17][18][19] , providing a rigorous quantitative framework for understanding how particular biophysical mechanisms relate to the computation of spatial location. Layer 2 of MEC (MECII) contains the highest proportion of grid cells 20,21 , and stellate cells, which form most of the MECII principal cell population 22 , are likely grid cell candidates 17,18,23,24 . In stellate cells, the correlation between somatically recorded synaptic responses and the dorsoventral gradient in grid spacing in MECII 25,26 has suggested that intrinsic voltage-gated conductances may be important for generating grid cell firing. However, very little is known about whether the dendrites of stellate cells are electrically excitable, and thus their contribution to grid cell firing is unclear.

Here we have combined in vitro two-photon glutamate uncaging and in vivo patchclamp recording with modeling to assess the role of active dendrites in grid cell firing. We show that stellate cells have active dendrites that perform supralinear input-output transformations in vitro. We also identify electrophysiological signatures consistent with active dendritic integration in vivo, including membrane-potential-dependent boosting of excitatory postsynaptic potentials (EPSPs) and plateau potentials. We place our results in the context of single-cell and network models of grid cell firing and use modeling to show that active dendrites can promote the robustness of the grid cell rate code while sharpening the precision of the temporal phase precession code. Thus, dendrites of principal cells in MECII are highly excitable, and these active dendritic properties can enhance the accuracy and stability of the spatial map represented by grid cell firing.

RESULTS

Supralinear integration in dendrites of MECII principal neurons

To assess how grid cells integrate synaptic inputs in single dendritic branches, we performed two-photon glutamate uncaging on dendritic spines of principal neurons in MECII (Fig. 1a).

Activation of individual spines in MECII stellate cells produced glutamate uncaging-evoked

EPSPs comparable to physiological synaptic responses (Fig. 1b and Supplementary Fig. 1).

Activating increasing numbers of spines along a single dendrite or on two nearby dendrites evoked responses that were larger than the arithmetic sum of the corresponding individual responses (65 ± 7% supralinearity for intervals of £ 1 ms; n = 34 dendritic branches; Fig. 1b,c and Supplementary Fig. 2). Since recent data suggest that some MECII pyramidal cells may also display grid cell firing 24,27 , we also carried out experiments on MECII pyramidal cells and obtained similar results (Fig. 1d and Supplementary Fig. 3). The degree of supralinearity in stellate cells did not significantly scale with distance from the soma (Supplementary Fig. 4) but was reduced to 9 ± 9% (n = 6) when the intervals between spine activations were extended to 8 ms, demonstrating that it depends on millisecond timing of the inputs (Fig. 1d).

Dendritic spikes and supralinearity depend on Nav and NMDAR channels

Activation of some dendritic branches produced clear signatures of dendritic spikes detected at the soma 28,29 . Dendritic spikes with fast and slow time-courses and distinct thresholds were observed (Fig. 2a), and application of pharmacological blockers revealed that these were generated by activation of voltage-gated sodium (Nav) channels and NMDA receptors (NMDARs), respectively (Fig. 2b and Supplementary Fig. 5). The NMDA receptor antagonist APV ((2R)-amino-5-phosphonovaleric acid) alone could also abolish fast spikes, indicating that NMDAR current was required to reach the threshold for Nav channel activation and that NMDARs and Nav channels thus acted cooperatively. This is also supported by the fact that a substantial fraction of fast spikes (43%) were followed by a slow spike, and many slow spikes (38%) were preceded by a fast spike. Both NMDAR channels, and to a lesser degree Nav channels, contributed to supralinearity (Fig. 2c).

Testing the contribution of nonlinear dendritic integration under in vivo conditions

To probe the contribution of dendritic nonlinearities in MECII stellate cells during more physiological in vivo-like conditions, we took advantage of the fact that the voltage profile underlying grid cell firing in vivo is represented by a ramp-like membrane potential depolarization 17,18 . We approximated this ramp-like depolarization in vitro by injecting a scaled current waveform that we had obtained from voltage-clamp recordings using the in vivo ramp as a voltage command (Online Methods). This allowed us to examine how in vivolike membrane potential dynamics influenced dendritic integration of synaptic inputs. Both supralinear summation and dendritic spikes were more pronounced when uncaging was performed during the in vivo-like ramps (Supplementary Fig. 6), suggesting that these active events were likely to be engaged in vivo when an animal entered a grid firing field. Taken together, these results reveal that the dendrites of grid cells were highly excitable, exhibiting markedly nonlinear input-output functions in a manner that could transform the integration of synaptic inputs during navigational behavior.

Signatures of active dendrites in stellate cell recordings in vivo

To determine whether active dendritic integration occurs in grid cells in vivo, we searched for the signatures of supralinear dendritic integration, as identified in our slice recordings, in patch-clamp recordings from MECII neurons of mice navigating in virtual reality 18 (Fig. 3).

By examining the differentiated membrane potential traces (dV/dt), we identified large peaks that were below the voltage threshold for action potentials and that were preferentially clustered around the peak of theta membrane potential oscillations (Fig. 3a), at a similar theta phase as action potentials during grid field crossings 17,18 . These dV/dt peaks in vivo were comparable in amplitude to dV/dt peaks of glutamate uncaging-evoked EPSPs exhibiting dendritic spikes in vitro (Fig. 2a and Supplementary Fig. 7). The in vivo dV/dt peaks were correlated with large depolarizations in V m with amplitudes of up to ~6 mV (Fig. 3b), consistent with them being EPSPs that were boosted by activation of voltage-dependent conductances.

To probe the mechanisms underlying these dV/dt signatures in more detail, we used our experimental results to constrain a detailed compartmental model of MECII stellate cells that captures their measured passive, active and synaptic properties (Supplementary Fig. 8).

Simulating grid cell firing in a model incorporating dendritic Nav and NMDAR channels reproduced the experimentally observed dV/dt signatures, including the correlation of dV/dt peak amplitudes with V m (Fig. 3c).When dendritic Nav and NMDAR channels were removed from the model, these signatures were abolished (Fig. 3c). In our in vivo experimental data, the fastest-rising events occurred within the 90° phase-bin preceding the peak of theta membrane potential oscillations (MPOs; Fig. 3d,f). This phase-bin also contained a larger fraction of particularly fast events with maximal rates of rise resembling or exceeding the maximal rates of rise of fast dendritic spikes that we observed during our somatic in vitro recordings (Fig. 3f). These observations could also be faithfully reproduced by the model generating dendritic Na + spikes in the presence of dendritic Nav channels but not in their absence (Fig. 3e,g).

To further quantify the contribution of nonlinear dendritic conductances to grid cell firing, we compared NMDAR activation and dendritic input currents in detailed compartmental models of stellate cells with active or passive dendrites (Supplementary Fig. 9). These simulations showed that during grid cell firing, with V m trajectories representative of our in vivo recordings, NMDARs were substantially recruited (Supplementary Fig. 9a) and dendritic input currents were nonlinearly amplified by active, voltage-dependent conductances (Supplementary Fig. 9b). Furthermore, the membrane potential distributions in putative dendritic recordings in vivo covered the nonlinear range of the NMDAR openprobability curve, implying that NMDARs were nonlinearly engaged in vivo (Supplementary Fig. 10). In summary, we observed clear signatures of active dendritic integration in the membrane potential of MECII principal neurons during navigational behavior in vivo.

Plateau potentials during putative dendritic in vivo stellate cell recordings

Next, we looked for direct evidence for activation of regenerative events in stellate cell dendrites in vivo. Excitable dendrites have been shown to produce long-lasting regenerative plateau potentials in several cell types, such as neocortical pyramidal cells 30 and hippocampal CA1 pyramidal cells in vitro 31 and in vivo 11,32 . We identified similar distinctive signatures of excitable dendrites in putative dendritic patch-clamp recordings from MEC neurons in vivo (Fig. 4 and Supplementary Fig. 11). Dendritic recordings were identified by a range of characteristic features 6,33 such as slower action potential rise times and higher input resistances (Supplementary Fig. 12). Distinct, long-lasting plateau depolarizations could be observed following action potentials in both putative dendritic and somatic recordings (Fig. 4a,b). These plateau potentials occurred either spontaneously (Fig. 4a,b and Supplementary Fig. 13a) or could be evoked by current injection in putative dendritic recordings (Fig. 4b).

We found that both the frequency (the percentage of action potentials followed by plateau potentials) and the duration of evoked plateau potentials were highly correlated with parameters that are also indicative of dendritic recordings (Fig. 4c), suggesting that they could be preferentially evoked in distal dendrites. While the frequency of evoked plateau potentials per action potential was more than an order of magnitude higher in putative dendritic than in somatic recordings from stellate cells in vivo (14.7 ± 7.2% of action potentials followed by plateau potentials in putative dendrites, n = 6, versus 0.4 ± 0.4% in soma, n = 6; P < 0.05), spontaneous plateaus occurred at comparable frequencies (1.9 ± 1.9% in putative dendrites, n = 6, versus 1.0 ± 1.0% in soma, n = 6; P = 0.22; Fig. 4d). Distinct plateau potentials could be evoked by current injections in 4 of 6 putative dendritic recordings but only in 1 of 6 putative somatic recordings (Fig. 4d). The results of these in vivo recordings indicate that plateau potentials could be evoked by strong, localized inputs to dendrites of grid cells and were readily detectable at their site of origin in the dendrite. However, plateau potentials were rarer and less prominent in somatic recordings and appeared to be substantially attenuated as they propagated to the soma from their origin in the dendritic tree. We further probed the biophysical mechanisms underlying dendritic plateau potentials using our active compartmental model of stellate cells. Strong, localized synaptic inputs to a dendrite of the stellate cell model could produce plateau potentials near the site of synaptic input that were similar to those observed in our putative dendritic recordings (Supplementary Fig. 14a).

These dendritic plateau potentials were strongly attenuated as they propagated to other dendrites and to the soma, making them readily detectable only close to the dendritic location of the active synaptic inputs (Supplementary Fig. 14a). To produce a plateau potential detectable at the soma, a large number of simultaneously activated strong synaptic inputs had to be distributed across the dendritic tree (Supplementary Fig. 14b). The rare occurrence of strong, synchronous activation of many synapses, along with the pronounced attenuation of plateau potentials along the dendritic tree, can therefore explain why they were only rarely observed as spontaneously occurring events. Thus, despite their low rate, the presence of dendritic plateau potentials in vivo provides strong evidence that the active dendritic conductances underlying nonlinear integration in vitro can be recruited by synaptic input in vivo.

Slow supralinear integration promotes the robustness of the grid cell rate code

To provide a quantitative framework for understanding the contribution of active dendrites to generating the grid cell rate code, we used a rate-based continuous attractor network (CAN) model. Given that NMDAR activation underpins the various types of dendritic nonlinearities we discovered in grid cells, we implemented NMDARs as a slow, cooperative, supralinear integration mechanism in an existing CAN model of grid cell firing 13 , which allowed us to efficiently explore a large range of parameters and noise amplitudes (Fig. 5 and Supplementary Fig. 9). Adding NMDARs to the CAN model substantially enhanced grid cell firing in the presence of noise, measured by a range of metrics (Fig. 5a-h). Across a wide range of noise amplitudes, NMDARs reduced network drift and improved the network's velocity response, resulting in higher gridness scores (Fig. 5i,j). Simulations in which we independently incorporated either supralinearity or a slow time-constant indicated that both mechanisms must act in concert to improve network performance (Supplementary Fig. 15).

The robustness of these findings was confirmed by a spiking attractor network model consisting of integrate-and-fire neurons 34 , which also produces the best velocity response and the highest gridness scores when both mechanisms are engaged (Supplementary Fig. 16).

Using actual animal trajectories to drive the rate-based model, we found that an NMDAR decay-time constant of ~50 ms produced a minimum in velocity error and a maximum in gridness (Fig. 5j). This optimum is remarkably consistent with the NMDAR decay-time constant we measured experimentally in stellate cells (46 ± 5 ms, n = 4; Supplementary Fig. 17). Simulations using an artificially slowed animal trajectory (Fig. 5j) indicate that the optimum depends on a realistic animal velocity driving the network response. Thus, NMDAR kinetics optimized for animal velocity can produce marked robustness to noise in a CAN model of grid cell firing.

Supralinear integration sharpens the precision of phase precession

Finally, we investigated how the active dendritic conductances we revealed in stellate cells can contribute to the temporal phase precession code of grid cell firing 35 . To determine the precise spike timing produced by oscillatory synaptic inputs, we drove our detailed compartmental MECII stellate cell model (Supplementary Fig. 8) by realistic synaptic input patterns derived from a hybrid oscillatory-interference-CAN model based on in vivo recordings from grid cells 18 (Fig. 6). While the model only produced weak phase precession in the absence of dendritic Nav channels (Fig. 6a-c), phase precession was strikingly precise when Nav channels were present in the dendrites (Fig. 6d-f). While the fast supralinearity provided by Nav channels was sufficient to sharpen phase precession even in the absence of distinct isolated regenerative events, the effect could further be enhanced if the model cell produced full-blown fast dendritic spikes (data not shown). Further analysis showed that dendritic Nav channels can sharpen phase precession by shortening the suprathreshold part of membrane potential oscillations, enabling precisely timed spikes across the full extent of a grid firing field (Supplementary Fig. 18). In agreement with this analysis, adjusting the width of grid fields by increasing excitatory drive in the model without dendritic Nav channels failed to improve phase precession, as more mistimed spikes were produced in the center of the grid field (Supplementary Fig. 19). Thus, our combined modeling results show that active dendritic conductances can both stabilize the rate code and sharpen the temporal code of grid cell firing.

DISCUSSION

We provide evidence that the dendrites of MECII principal cells are electrically excitable and exhibit a range of nonlinear dynamics. Our results reveal that the biophysical origins of dendritic nonlinearities in these cells-dendritic Nav and NMDAR channels-may underpin the two key aspects of the grid cell code. Dendritic Nav channels restrict the time window for action potential generation in an oscillatory-interference model of phase precession, thereby improving the precision of the temporal code. NMDARs in turn improve the robustness of the grid attractor in a rate-based model of grid cell firing. Together, our results provide strong evidence that active dendrites can make a critical contribution to a key behaviorally relevant computation in the mammalian brain. Our simulations also provide a general framework for understanding how active dendritic computations can stabilize attractor networks.

Active dendrites in MECII principal cells

Although principal cells in MECII, which form a large part of the grid cell population, have been shown to exhibit a rich variety of nonlinear excitability in somatic recordings 19,25,36 , there has been no direct information available about the contribution of dendritic excitability to the active properties of grid cells. Our in vitro experiments reveal that the dendrites of both types of principal neurons in MECII, stellate and pyramidal cells, exhibited nonlinear inputoutput functions and could trigger dendritic spikes mediated by both voltage-gated sodium channels and NMDA receptor channels. Moreover, they demonstrate that these nonlinearities could be further enhanced by in vivo-like membrane potential trajectories that underpin grid cell firing.

Our in vivo experiments strengthen and complement our in vitro results and provide multiple signatures of nonlinear dendritic integration in MEC neurons during spatial navigation. First, EPSPs were boosted at the peak of the MPOs when the neuron was depolarized, consistent with our in vitro experiments, as well as with predictions from a model with active dendrites (Fig. 3). Second, comparing a stellate cell model with nonlinear or linear dendritic conductances, we found that dendritic nonlinearities were robustly activated during simulations of grid cell firing (Supplementary Fig. 9). Third, we observed nonlinear plateau potentials in putative dendritic whole-cell recordings from MECII neurons.

We found that plateau potentials frequently occurred with dendritic but not somatic current injections, whereas spontaneous plateaus occurred with similar probability in somatic and dendritic recordings, indicating that the plateaus were of dendritic origin. Plateau potentials have been observed as a signature of dendritic excitability in other cell types 30 , particularly in CA1 pyramidal cells 11,32 , where dendritic plateau potentials can positively modulate existing or induce new place fields 11 . Together, our modeling and experimental data suggest that the dendrites of grid cells are electrically highly excitable and that the resulting nonlinearities can be engaged in vivo during grid cell firing in mice performing a spatial navigation task.

How do active dendrites improve grid cell firing?

Our modeling results show that active dendrites can enhance both the rate and temporal code of grid cell firing. First, we show that incorporating a nonlinear NMDA conductance, with characteristics matching those underpinning the nonlinearities in our in vitro experiments, in a CAN model of grid cell firing can reduce network drift and improve the network's velocity response, resulting in improved gridness. Our simulations show that this enhancement of gridness arises from a synergistic interaction between two cardinal features of the nonlinear NMDAR conductance. First, NMDAR activation depends nonlinearly on the amplitude of the synaptic inputs that a neuron receives, increasing the gain of the neural transfer function preferentially in active neurons receiving strong spatial inputs 37 . Second, the slow decay-time constant of NMDARs allows active neurons to average signals over a longer time (see also refs. 38-40), reducing the contribution of noise 38 and stabilizing the attractor. Notably, the stabilizing effect of NMDARs depends on the noise amplitude (Fig. 5i). Thus, acute blockade of NMDARs in grid cells should most strongly disrupt grid firing in novel environments, where spatial inputs are expected to be imprecise 41 .

Our detailed compartmental model indicates that active dendrites also enhance phase precession, the signature of the temporal code of grid cell firing. Our simulations show that the mechanism underlying this effect operates by curtailing the suprathreshold part of the membrane potential trajectory during membrane potential oscillations. This ensures that spikes can occur only within a narrow time window, sharpening the precision of spike timing and thus the robustness of phase precession across the entire grid firing field. Notably, the effect of active dendrites on phase precession does not require the activation of full-blown dendritic spikes: even a model exhibiting subthreshold recruitment of nonlinearities demonstrates enhanced phase precession. Moreover, the model can reproduce the experimentally observed phase precession of both spikes and theta MPOs 18,19 . The simplicity and robustness of this mechanism suggests that it may generalize to other phase-precession models relying on coincidence of oscillations, such as those that have been proposed for CA1 pyramidal cells [42][43][44] .

Our findings suggest that dendritic nonlinearities are key elements in the creation of a stable grid code and are therefore critical for navigation. This complements recent work proposing that dendritic nonlinear events may contribute to behaviorally relevant computations in single neurons [5][6][7][8] . In hippocampal place cells, in vivo two-photon imaging has revealed dendritic Ca 2+ transients that are correlated with their place field properties 9 , and intracellular recordings from place cells suggest that dendritic nonlinearities may contribute to defining the spatial tuning of a neuron 10,11 . Together with our in vivo results indicating that dendritic nonlinearities may also be engaged in MECII stellate cells during virtual navigation (Figs. 3 and4), this suggests that active dendrites may provide a general mechanism for strengthening spatial representations at the single-cell level. Notably, the stabilizing role that we describe for active dendrites in a CAN may also generalize to other circuits that display attractor dynamics, both in the hippocampus 45,46 and in other brain areas 47 .

Why use active dendrites to enhance circuit computations?

Active dendrites offer several key advantages over alternative mechanisms-such as tuning somatic and axonal excitability, or excitation-inhibition balance-for improving the signalto-noise ratio during grid cell firing. The nonlinear voltage-dependence of NMDAR activation exhibits exquisite sensitivity, being engaged already by a small number of synapses due to the high dendritic-input impedance (Supplementary Fig. 20) 48 . At the same time, since dendritic synapses are electrotonically remote from the axonal site of action potential generation, nonlinear integration can proceed independently of somatic spiking 49,50 . Moreover, by regulating the density of dendritic Nav channels and NMDARs, the threshold for supralinear integration can be widely adjusted over a large range of synaptic input frequencies to maximize the signal-to-noise ratio for grid cell firing. In contrast, changes in somatic and axonal excitability have only small effects on the shape of the input-output transfer function of MECII principal neurons 36 . Furthermore, dendritic nonlinearities provide versatility, permitting a range of flexible transfer functions depending on the combination of dendritic branches that are activated (Supplementary Fig. 2). This allows grid cells to gate relevant inputs and suppress irrelevant inputs (similarly to what has been suggested for place cells 10 ).

Finally, active dendrites may also provide a mechanism for shaping circuit wiring during development: early in the assembly of the entorhinal circuit, synaptic inputs that contact a nonlinear dendritic branch may be strengthened by engaging these nonlinearities and in turn define the grid properties of a neuron. After some recordings (Supplementary Fig. 3), the slices were fixed in 4% paraformaldehyde and immunohistochemical staining was performed using rabbit anticalbindin (ab11426, Abcam) as the primary antibody and donkey F(ab')2 anti-rabbit IgG (Alexa Fluor 488, ab150069, Abcam) as the secondary antibody 51,52 .

Electrophysiology and pharmacology.

Somatic whole-cell patch-clamp recordings were obtained from stellate and pyramidal cells in layer 2 of medial entorhinal cortex. Stellate and pyramidal cells were identified by their somatodendritic morphology and their characteristic electrophysiological properties 19,25,26,36,[53][54][55][56] . Current-clamp recordings were acquired with a MultiClamp 700B

Two-photon imaging and uncaging.

Simultaneous two-photon imaging and dendritic stimulation at single-synapse resolution by uncaging of MNI-caged-L-glutamate was performed with two Ti-sapphire lasers tuned to 810 nm and 720-730 nm for imaging and uncaging, respectively. To visualize dendrites and dendritic spines, cells were loaded with a fluorescent dye (50 µM Alexa Fluor 594) added to the pipette solution. Healthy dendrites close to the surface of the slice were selected for uncaging. MNI-caged-L-glutamate (24 mM, Tocris) was dissolved in a solution containing (in mM): NaCl 125, glucose 25, KCl 2.5, HEPES 10, CaCl 2 2 and MgCl 2 1 and applied locally via a glass pipette (tip diameter ~10 µm). Multiple spines were selected in a randomized manner within a maximal distance of ~50 µm on a single dendritic branch. gluEPSPs were first evoked by stimulating each spine individually at 300-ms intervals. We then stimulated an increasing number of synapses at short time intervals (0.6-8 ms, as indicated), with a 10-s pause between each trial. To estimate the expected linear summation of gluEPSPs, we first shifted individual membrane potential traces according to the corresponding experimental stimulation interval (0.6-8 ms for each trace) before computing the sum. Uncaging laser exposure time was 0.5 ms. The laser power was adjusted to produce gluEPSPs that were comparable to sEPSPs recorded in the same cell (Supplementary Fig. 1). Uncaging timing and location were controlled by custom software written in Matlab. Experiments were terminated if photodamage to the dendrite was observed (for example, swelling of the dendrite) or depolarization of the membrane potential was detected. Recordings from neurons with photodamaged dendrites were excluded from analysis. Recordings were also excluded if the slice exhibited physical drift due to slice swelling or inconsistency of perfusion. This was detected either by imaging or by sudden large changes (usually decreases) in EPSP amplitude.

Data analysis.

Data analysis was performed with custom code written in Python 57 . Nonlinearity, D, of each experiment was quantified by

3 1 100% 2 i n i i M L D n = - = × - å (1)
where M i is the amplitude of the measured EPSP, L i is the amplitude of the EPSP constructed by linear summation of single synapse EPSPs, and n is the maximal number of synapses activated. Slow dendritic spikes were detected if the nonlinearity of the EPSP integral was 33% larger than the nonlinearity of the EPSP amplitude. A fast dendritic spike was defined as a step-like increase (>50%) in a plot of maximal dV/dt against the number of uncaging locations (Fig. 2 and Supplementary Fig. 3).

To examine whether signatures of active dendritic integration can be found in grid cells in vivo, we analyzed in vivo patch-clamp recordings from MECII neurons 18 . The full membrane potential (V m ) recording duration from n = 6 putative grid cells was used for this analysis. Peaks were identified in differentiated V m traces (dV/dt) by detecting local maxima that exceeded 0.1 mV/ms within time windows of 200 µs. The analysis was restricted to subthreshold V m by excluding parts of traces where dV/dt exceeded 5% of the maximal rate of rise of action potentials of each recording. Local V m peaks corresponding to these dV/dt peaks were detected in high-pass-filtered V m traces (f c = 10 Hz) within 5 ms following each dV/dt peak (Fig. 3b,c). dV/dt peaks were binned according to the phase of theta membrane potential oscillations (theta MPOs) during which they occurred. Theta MPOs were obtained by bandpass-filtering V m between 5 and 10 Hz; 0° corresponds to the peak of theta MPOs. For each theta MPO bin with a width of 45° (as indicated), mean and s.d. of all dV/dt peaks were computed for each recording (Fig. 3d-g). Moreover, for each theta MPO bin with a width of 90° (as indicated), dV/dt peaks that exceeded the mean of all dV/dt peaks within a given bin by 1.5 s.d. were computed for each recording (Fig. 3f,g). These particularly fast peaks are indicated by red symbols in Figure 3. According to these criteria, the lowest threshold for these fast peaks was typically a maximal rate of rise of ~0.4 mV/ms (Fig. 3d). Thus, these fast in vivo events were characterized by maximal rates of rise resembling or exceeding the maximal rates of rise of fast dendritic spikes recorded in vitro (typically ~0.4 mV/ms; Fig. 2a).

We analyzed plateau potentials across both somatic 18 and putative dendritic in vivo patch-clamp recordings from MECII neurons. Plateau potentials were defined as sustained depolarizations following action potentials with a full-width-at-half-maximal amplitude exceeding 15 ms. These criteria were chosen to identify plateau potentials that closely resembled published examples (for example, Bittner et al. 11 ). Action potentials were detected when dV/dt exceeded 30 mV/ms. We did not observe any obvious isolated plateau potentials without a preceding action potential in our data set. We analyzed a total of n = 58 recordings that produced trains of action potentials in response to depolarizing 1-s current injections.

Recordings were categorized into putative dendritic and putative somatic recordings according to input resistance (R in ) and 20-80% rise time of action potentials (t 20-80 ) 6 (putative somatic: t 20-80 < 0.2 ms and R in < 80 MW; putative dendritic: t 20-80 > 0.3 ms and R in > 120 MW). The frequency of plateau potentials did not depend on recording parameters such as resting membrane potential or seal resistance (Supplementary Fig. 11), indicating that recording quality did not affect their occurrence. To measure action potential kinetics (Fig. 4 and Supplementary Fig. 12), we used the first action potential that was evoked by the lowest suprathreshold sustained current injection.

Data are presented as mean ± s.e.m., unless stated otherwise. Error bars for dendritic spike proportions represent the s.d. of bootstrap analyses of the experimental data set (1,000 repeats). Statistical significance of continuous data was assessed using two-sided Mann-Whitney U tests and Wilcoxon signed-rank tests for unpaired and paired data, respectively.

Statistical significance of dendritic spike proportions was assessed using Fisher's exact test.

Analyses of variance (ANOVA) were performed when more than two groups were tested.

Differences were considered statistically significant when P < 0.05. No correction for multiple comparisons was applied 58 . No statistical methods were used to predetermine sample sizes, but our sample sizes are similar to those reported in previous publications 11,17,18 . Data collection and analysis were not performed blind to the conditions of the experiments.

Compartmental modeling.

Studying phase precession required us to model the precise timing of action potentials produced by oscillatory synaptic inputs. To achieve realistic predictions of membrane potential trajectories, we therefore decided to use a detailed compartmental model implemented in NEURON 59 (Figs. 3 and6 and Supplementary Figs. 8 and20). We used a reconstructed morphology of a mouse MEC stellate cell 25 and HCN-channel gating kinetics based on experimental data from stellate cells 60 . Voltage-gated potassium (Kv) and sodium (Nav) channel kinetics were adopted from a CA1 pyramidal cell model 61 . Active conductance densities, axial resistivity (R i ), specific membrane resistance (R m ) and capacitance (C m ) were fitted to reproduce the experimentally determined mean f-I relationship, input resistance, sag ratio, sag time-constant, membrane time-constant, resting membrane potential and afterhyperpolarization amplitude using a genetic algorithm (NSGAII) [62][63][64] (Supplementary

Table 1).

Subthreshold synaptic input-output curves (Supplementary Fig. 8b) were produced by first finding all sites on the dendritic tree that were located 175 µm from the soma. We then performed simulations that closely followed our experimental protocol (Fig. 1): at each site, we distributed 20 synaptic conductances within 25 µm. We then activated individual synaptic conductance changes in isolation and computed the linear sums of the individual responses. Next, we stimulated an increasing number of synaptic conductance changes at 1ms intervals and plotted the amplitudes of the measured responses against the amplitudes of the linear sums. This procedure was repeated for each site to yield a set of input-output curves. The analysis of simulated data was identical to that of experimental data.

To determine the effect of dendritic Nav channels on phase precession (Fig. 6 and Supplementary Fig. 19), we used a modeling and analysis strategy similar to one described previously 18 . In brief, we converted the synaptic inputs of rate-based neurons in a CAN model (see below) into discrete events driving synaptic conductance changes in our compartmental stellate cell model. Feedforward excitation was provided by six directional velocity-controlled oscillating (VCO) inputs that were only active when the current running direction matched the VCO's preferred direction ± 90° (ref. 65).

Rate-based modeling (Fig. 5 and Supplementary Fig. 15).

Previous work has suggested that the mechanisms underlying the rate code of grid cell firing are best explained by a continuous attractor network (CAN) model 17,18,66 . We implemented a CAN model in a sheet of 128 × 128 neurons with periodic boundaries building on a previous implementation (courtesy of Y. Burak and I. Fiete 13 ). This rate-based model allowed us to efficiently test the effect of a large range of parameters on network performance, which is essential for exploring the effects of a large range of noise amplitudes. The dynamics of ratebased neurons was defined by for 0 0 for 0

V i i i i k V V s V ³ ì = í < î with (2) ( ) ( )( ) NMDA d 1 0 . 5 d i i i i i i V V k p I B t t x + = + - + + and (3) i i j j j I W s = å (4)
where s i represents the firing rate of neuron i, V i represents the membrane potential of neuron i, t = 10 ms is the integration time constant of the neural response, k NMDA = 0.4 (unless indicated otherwise) is the relative strength of NMDARs, p i is the fraction of open NMDARs in neuron i (equations ( 8) and ( 9)), I i is inhibitory recurrent input to neuron i, B i is excitatory feedforward input to neuron i, W ij is the synaptic weight from neuron j to neuron i, and x i is colored synaptic noise (equations ( 10)-( 12)). By subtracting 0.5 from p i , mean network firing rates were kept approximately constant across simulations. For a threshold-linear implementation of the model without NMDARs, we set k NMDA = 0. The gain of the neural transfer function, k V , was set to 0.88 (unless indicated otherwise), which minimized drift and velocity error for k NMDA = 0. This strategy was chosen to ensure that reductions of drift and velocity error by NMDARs could not be explained by a simple linear gain change. The implementation of NMDARs as a multiplicative term is consistent with predictions of NMDAR recruitment in a compartmental model (Supplementary Fig. 9). B i was defined by ( )

1 ˆ i i B B A f a = + × e v (5)
where ˆi f e is the unit vector pointing along neuron i's preferred direction i f (one of W, N, S or E), v is the animal velocity vector in m s -1 , and a was set to 0.0825. The recurrent weight matrix was purely inhibitory in our implementation:

( )

0 ˆ i ij i j W W l f = -- x x e with (6) ( ) ( ) 2 2 0 x x W W A e e g b - - = - x (7)
where x i is neuron i's location in the neural sheet and ranges from (-64, -64) to (64, 64). In our implementation, we used l = 2, g = 1.02b, b = 3l -2 and l = 13. A B = 10 and A W = 10 are scaling factors that were chosen to compensate for the 'notau' option in the original implementation. As in Burak and Fiete 13 , we computed the animal velocity vector v from an experimentally determined rat trajectory 12 .

It is currently unknown how spatially modulated excitatory and inhibitory inputs are distributed on the dendritic tree of grid cells. To implement a model that applies to a large range of potential synaptic input configurations, we therefore used a generalized approach in which we subject the sum of all synaptic inputs to a single function, which can take a nonlinear form.

The dynamics of NMDAR open probability p i in neuron i was computed as follows:

( ) NMDA d d i i i p p p V t ¥ t + = with (8) ( ) NMDA NMDA 1 1 1 V c m p V e ¥ - = - + (9)
where the steady-state open probability, p ¥ (V), was assumed to be a sigmoid function of membrane potential V with center c NMDA = 0.1 and slope m NMDA = 0.2, yielding a neural transfer function that qualitatively matched the experimentally determined dendritic inputoutput curves. Unless indicated otherwise, t NMDA was set to 50 ms, in agreement with our experimental data (Supplementary Fig. 17).

Synaptic noise, x i , was implemented as an Ornstein-Uhlenbeck process using an exact update rule for an integration time step, h 67,68 :

, exc , inh i i i x x x = - with (10) ( ) ( ) ( ) ( ) exc / , exc exc, 0 ,exc exc,0 exc 1 h i i t h t t e A G t x x x x - + = + - + and (11) ( ) ( ) ( ) ( ) inh /
( ) inh 2 / inh inh inh 1 2 h D A e t t - = - (14)
where D exc and D inh are noise diffusion coefficients. Excitatory and inhibitory noise were assumed to be symmetric in our simulations, with t exc = t inh = 2 ms. Noise diffusion coefficients and average synaptic noise were set as high as possible without disrupting the periodic activity bumps in the CAN when the original simulation parameters from Burak and Fiete 13 were used (x exc,0 = x inh,0 = 1.2, D exc = D inh = 0.04, yielding a ratio similar to x 0 /D, as in Destexhe et al. 67 ).

Publisher: NPGNY; Journal: NN: Nature Neuroscience; Article Type: Article DOI: 10.1038/ Integrate-and-fire neurons (Supplementary Fig. 16).

An implementation of a CAN model using integrate-and-fire neurons was adopted from where g AMPA and g NMDA are the AMPAR and NMDAR conductances, a NMDA = 0.5 defines NMDAR saturation, t NMDA,rise = 2 ms and t NMDA,decay = 100 ms are the rise and decay time constants of NMDAR, and x is the activation gating variable of NMDARs. For each presynaptic spike occurring at time t 1 , the synapse activity was updated from its previous state at time t 0 according to the following equations:

( ) ( ) ( ) 1 0 x t x t wp V ¥ = + and (18) ( ) ( ) AMPA 1 AMPA 0 g t g t w = + (19)
where w = 1 is the synaptic weight and p ¥ (V) is the steady-state open probability of the NMDAR (equation ( 9)). Total synapse conductance was computed as g AMPA + k NMDA g NMDA .

The maximal total conductance was set to 2.3 nS. A version of an AMPAR/NMDAR-type synapse without Mg 2+ block was implemented by setting p ¥ (V) = 1 in equation ( 18).

Spatial rate maps of model neurons were discretized into 1-cm × 1-cm bins. No smoothing of the data was performed. To quantify spatial periodicity ('gridness'), we first calculated the spatial autocorrelation for rate maps of each model neuron 21 . We then selected a centered ring-shaped region of interest from the autocorrelogram that included peaks closest to the center but excluded the central peak. We next rotated this ring in steps of 1° and at each step computed the correlation coefficient of the rotated with the original ring. We then

Figure 1

 1 Figure 1 Supralinear synaptic integration in MEC principal neurons. (a) Two-photon image of a MECII stellate cell filled with Alexa Fluor 594 via somatic patch-clamp recording. Inset shows the selected dendrite and the uncaging locations (red spots). (b) Somatic voltage responses to increasing number of stimulated synapses (indicated in the inset in a). Top traces show arithmetic sums expected from the individual responses; bottom traces show recorded responses (15 spines, 0.6-ms stimulation interval). (c) The amplitudes of somatically recorded glutamate uncaging-evoked EPSPs (gluEPSPs) were markedly larger than the arithmetic sum of the individual responses (dashed line indicates unity). Top, single experiment (as in a and b); bottom, summary of 34 experiments. Grey lines represent individual experiments; the black line connects binned averages across experiments (red). Error bars represent s.e.m.. (d) Nonlinearity depends on the interval between uncaging events (*P < 0.05). No significant difference in the degree of supralinearity was found between stellate cells (SC) and pyramidal cells (PC) of MECII (at £1-ms stimulation intervals). Nonlinearity in stellate cells at different stimulation intervals: 8 ms, 9 ± 9% (n = 6); 4 ms, 54 ± 16% (n = 11); £1 ms, 65 ± 7% (n = 34); one-way ANOVA for different stimulation intervals, P = 0.02, F = 4.22; nonlinearity in pyramidal cells at stimulation intervals; £1 ms: 48 ± 11% (n = 9; Mann-Whitney U test, P = 0.18 compared to stellate cells).

Figure 2

 2 Figure 2 Supralinear integration and dendritic spikes depend on voltage-gated sodium (Nav) and NMDA receptor channels. (a) Left: examples of fast (orange arrows) and slow (blue arrows) dendritic spikes. Right: plots of dV/dt against number of uncaging locations. Fast dendritic spikes cause a step-like increase in dV/dt (arrows). (b) Top: fast dendritic spikes are present in 21 ± 7% (n = 34) of all recordings and abolished when Nav channels are blocked with tetrodotoxin (TTX) and/or when NMDARs are blocked with APV ((2R)-amino-5phosphonovaleric acid). Bottom: slow dendritic spikes are present in 26 ± 7% (n = 34) of all recordings, still present in TTX (29 ± 17%; n = 7; Fisher's exact test, P = 1.0) and abolished when NMDARs are blocked with APV. Uncaging interval £ 1 ms. Individual data points (not indicated in the figure) are either zeroes (no spikes were observed in a recording) or ones (spikes were observed in a recording). Bar graphs indicate the percentage of recordings containing spikes; error bars were calculated by Monte Carlo methods. (c) Application of TTX and APV reduces or abolishes supralinear dendritic integration. Grey dots represent individual recordings. Control: 65 ± 7% (n = 34); TTX: 36 ± 11% (n = 7; Mann-Whitney U test, P = 0.07 compared to control); APV: 11 ± 21% (n = 3; Mann-Whitney U test, P = 0.02 compared to control). TTX+APV: 11 ± 5% (n = 3; Mann-Whitney U test, P = 0.02 compared to control). One-way ANOVA, P = 0.03, F = 3.16.

Figure 3

 3 Figure 3 Engagement of active dendritic conductances in MECII principal neurons in vivo. (a) Left: membrane potential (V m ; top), theta membrane potential oscillations (theta MPOs; middle, green trace) and differentiated membrane potential (dV/dt; bottom) during a firing field crossing in a MECII neuron (experimental data from Schmidt-Hieber and Häusser 18 ). Grey dashed vertical lines indicate peaks (0° phase) of theta MPOs. Right: membrane potentials and differentiated membrane potentials at higher magnification for two episodes corresponding to the horizontal bars at the bottom of the traces on the left. Filled circles on dV/dt traces indicate peaks in dV/dt that are below (black) or above (red) the mean + 1.5 s.d. of all peaks within 90° bins of theta MPO phases. (b) Plot of peaks in membrane potential against corresponding peaks in dV/dt for the recording shown in a. Colors as in a. Green line represents a linear regression (r = 0.49; P < 10 -5 ; n = 8,265 peaks). (c) As in b, for a detailed compartmental model of a MECII stellate cell with active (left; r = 0.45; P < 10 -5 ; n = 14,411 peaks) or passive dendrites (right; r = 0.31; P < 10 -5 ; n = 25,228 peaks). See Online Methods for model details. (d) Plot of peaks in dV/dt against the phase of theta MPOs for the recording shown in a. Colors as in a. Yellow filled circles represent binned averages. (e) As in d, for compartmental model data with active (left) or passive dendrites (right) as in c. (f) Analysis of

Figure 4

 4 Figure 4 Plateau potentials suggest that active dendritic conductances are engaged in vivo. (a) Example of a putative somatic recording from a MEC neuron in vivo. Plateau potentials (arrows) occur spontaneously (left, top trace shows animals speed, bottom trace shows membrane potential) but not during current injections (right, top traces show membrane potential, bottom traces show current injections). (b) Example of a putative dendritic recording from a MEC neuron in vivo. Plateau potentials (arrows) occur both spontaneously (left, top trace shows animals speed, bottom trace shows membrane potential) and upon current injections (right, top traces show membrane potential, bottom traces show current injections). Inset (top right) shows an enlarged view of an evoked plateau potential. (c) Frequency and duration of plateau potentials correlate with parameters that are characteristic of dendritic recordings. Plateau frequencies per action potential (top) and plateau durations (bottom) are significantly correlated with rise times of action potentials (left) and input resistance (right). Black lines represent linear regressions (n = 58 recordings). (d) Summary bar graphs of evoked and spontaneous plateau frequencies per action potential in (left)putative somatic (evoked, 0.4 ± 0.4%; spontaneous, 1.0 ± 1.0%, n = 6) and (right) dendritic recordings (evoked, 14.7 ± 7.2%; spontaneous, 1.9 ± 1.9%, n = 6). Filled gray circles represent individual recordings. Error bars represent s.e.m.

Figure 5

 5 Figure 5 Active dendrites in MECII neurons can enhance the robustness of the rate code of grid cell firing. (a,b) CAN model simulations were performed either in the absence (a) or the presence (b) of a slow supralinear integration mechanism, as provided by NMDARs (t NMDA = 50 ms). (c,d) Left: animal trajectory (blue; data from Hafting et al. 12 ) and CAN network prediction of animal position in the absence (c) (black) or in the presence (d) (red) of NMDARs are superimposed. Right: color-coded spatial rate maps for an example model neuron in the absence (c) or in the presence (d) of NMDARs. (e,f) Left: correlation between rotated autocorrelation maps plotted against the rotation angle. Simulations were performed in the absence (e) or in the presence (f) of NMDARs. Right: autocorrelation matrices of the spatial rate maps shown in c and d, respectively. (g) To quantify network drift, mean squared displacement is plotted as a function of simulation time interval in the absence of velocity

Figure 6

 6 Figure 6 Active dendrites in MECII neurons can promote the precision of the temporal code of grid cell firing. (a,d) A detailed compartmental model of a MECII stellate cell was used to simulate grid cell firing in a hybrid CAN-oscillatory-interference model with passive (a) or active (d) dendrites (see Online Methods for details). Left: voltage-gated sodium conductance density plotted against dendritic distance from soma. Right: color-coded firing rate maps. (b,e) Example traces of simulated somatic membrane potential during a firing field crossing in the model with passive (b) and with active (e) dendrites. Raster plots at top show timings of excitatory velocity-controlled oscillators (VCOs, red) and inhibitory ramp inputs (blue). (c,f) While phase precession degraded in the model with (c) passive dendrites (n = 80 spikes), the model with (f) active dendrites (n = 153 spikes) produced clear phase precession of spikes with reference to the LFP. Red lines represent circular-linear regressions.

  amplifier at a 50-kHz sampling rate using custom software written in Matlab. Patch pipettes of 5-MW resistance were filled with internal solution containing (in mM): KMeSO 4 140, HEPES 10, KCl 7.4, MgCl 2 0.3, EGTA 0.1, NaGTP 0.3, Na 2 ATP 3 and sodium phosphocreatine 1. Alexa Fluor 594 (50 µM) was added to this solution to visualize cell morphology. Series resistance of the recordings was usually less than 30 MW. In some recordings, 50 µM of D-APV and 0.5 µM of TTX were added to the regular ACSF solution to block NMDA receptors and voltage-gated sodium channels, respectively. All extracellular solutions were equilibrated with carbogen (95% O 2 / 5% CO 2 ) and had a pH of 7.3. Miniature EPSPs (mEPSPs; Supplementary Fig.1) were measured in the presence of 0.5 µM TTX in the recording solution. The detection threshold for mEPSPs was when dV/dt exceeded 1 mV/s.To produce membrane potential ramps in vitro that mimicked membrane potential dynamics in vivo (Supplementary Fig.6), we first applied the mean in vivo membrane potential waveform that we had previously recorded from stellate cells during firing field crossings 18 as a voltage clamp command in n = 5 stellate cells in vitro. The resulting clampcurrent waveform was then averaged across recordings and injected as a current-clamp command to produce an in vivo-like voltage ramp. For voltage-clamp recordings (Supplementary Fig.17), pipettes were filled with internal solution containing (in mM): CsMeSO 4 135, HEPES 10, EGTA 10, NaGTP 0.3, Na 2 ATP 2 and MgATP 2. Series resistance was less than 15 MW. EPSCs were evoked by extracellular stimulation in layer I of MEC while holding MECII stellate cells at a potential of +40 mV. NMDAR-mediated EPSCs were isolated by blocking GABA A receptors with SR95531 (20 µM) and AMPA receptors with NBQX (10 µM).

  Publisher: NPGNY; Journal: NN: Nature Neuroscience; Article Type: Article DOI: 10.1038/ determined maximal correlation values at 60° and 120° rotation (r max,60 and r max,120 ) and minimal correlation values at 30°, 90° and 150° rotation (r min,30 , r min,90 and r min,150 ). Gridness was then determined as min(r max,60 , r max,120 ) -max(r min,30 , r min,90 , r min,150 )21 . Mean gridness values were computed for ten randomly selected model neurons. , Toleikyte et al.

Figure 1

 1 Schmidt-Hieber, Toleikyte et al.

  Zhang, K. Representation of spatial orientation by the intrinsic dynamics of the head-direction cell ensemble: a theory. J.Neurosci. 16, 2112-2126 (1996).</jrn> <jrn>47.Goldberg, J.A., Rokni, U. & Sompolinsky, H. Patterns of ongoing activity and the functional architecture of the primary visual cortex.Editorial summaryCombining electrophysiology and computational modeling, the authors show that the dendrites of entorhinal cortex stellate and pyramidal cells are electrically excitable and that this improves the robustness of grid cell firing. The results suggest that active dendrites are critical for spatial navigation, a fundamental computation in the brain.

	<jrn>10.	Lee, D., Lin, B.J. & Lee, A.K. Hippocampal place fields emerge upon single-
	cell manipulation of excitability during behavior. Science 337, 849-853 (2012).</jrn>
	<jrn>11.	Bittner, K.C. et al. Conjunctive input processing drives feature selectivity in
	hippocampal CA1 neurons. Nat. Neurosci. 18, 1133-1142 (2015).</jrn> Neuron 42, 489-500
	<jrn>12. (2004).</jrn> Hafting, T., Fyhn, M., Molden, S., Moser, M.B. & Moser, E.I. Microstructure
	of a spatial map in the entorhinal cortex. Nature 436, 801-806 (2005).</jrn> <jrn>48. Branco, T. & Häusser, M. Synaptic integration gradients in single cortical
	<jrn>13. pyramidal cell dendrites. Neuron 69, 885-892 (2011).</jrn> Burak, Y. & Fiete, I.R. Accurate path integration in continuous attractor
	network models of grid cells. PLOS Comput. Biol. 5, e1000291 (2009).</jrn> <jrn>49. Behabadi, B.F. & Mel, B.W. Mechanisms underlying subunit independence in
	<jrn>14. pyramidal neuron dendrites. Proc. Natl. Acad. Sci. USA 111, 498-503 (2014).</jrn> Burgess, N., Barry, C. & O'Keefe, J. An oscillatory interference model of grid
	cell firing. Hippocampus 17, 801-812 (2007).</jrn> <jrn>50. Häusser, M.
	<jrn>15.
	987-994 (2010).</jrn>
	<jrn>21.	Sargolini, F. et al. Conjunctive representation of position, direction, and
	velocity in entorhinal cortex. Science 312, 758-762 (2006).</jrn>
	<jrn>22.	Gatome, C.W., Slomianka, L., Lipp, H.P. & Amrein, I. Number estimates of
	neuronal phenotypes in layer II of the medial entorhinal cortex of rat and mouse.
	Neuroscience 170, 156-165 (2010).</jrn>
	<jrn>23.

Fuhs, M.C. & Touretzky, D.S. A spin glass model of path integration in rat medial entorhinal cortex. J.

Neurosci. 26, 4266-4276 (2006)

.</jrn> <jrn>16. Kropff, E. & Treves, A. The emergence of grid cells: intelligent design or just adaptation? Hippocampus 18, 1256-1269 (2008).</jrn> <jrn>17. Domnisoru, C., Kinkhabwala, A.A. & Tank, D.W. Membrane potential dynamics of grid cells. Nature 495, 199-204 (2013).</jrn> <jrn>18. Schmidt-Hieber, C. & Häusser, M. Cellular mechanisms of spatial navigation in the medial entorhinal cortex. Nat. Neurosci. 16, 325-331 (2013).</jrn> <jrn>19. Schmidt-Hieber, C. & Häusser, M. How to build a grid cell. Phil. Trans. R. Soc. Lond. B 369, 20120520 (2013).</jrn> <jrn>20. Boccara, C.N. et al. Grid cells in pre-and parasubiculum. Nat. Neurosci. 13, Zhang, S.J. et al. Optogenetic dissection of entorhinal-hippocampal functional connectivity. Science 340, 1232627 (2013).</jrn> <jrn>46. , Major, G. & Stuart, G.J. Differential shunting of EPSPs by action potentials. Science 291, 138-141 (2001).</jrn>

  Pastoll et al. 34 . Topology and connectivity of the model were adopted from the original implementation: the network consisted of 68 × 58 excitatory and 34 × 30 inhibitory neurons

	interconnected in an 'E-surround' configuration 34 . Constant excitatory input currents to the
	excitatory neurons in the original model (Iext_e_const and Iext_e_theta) were replaced by
	mixed AMPAR/NMDAR-type synapses driven by Poisson spike trains at 1 kHz. The
	dynamics of the synapses was defined by
	t	AMPA	AMPA d g d t	+	g	AMPA	=	0	(15)
	d g	NMDA d t	= -	t	NMDA NMDA,decay g	+	a	NMDA	x	( 1	-	g	NMDA	)	and (16)
	t	NMDA,rise	d d x x t + =	0	(17)

ACKNOWLEDGMENTS

We are grateful to P. Latham, A. Packer and S. Turaga for discussions and comments on the manuscript, and to S. Chun for assistance with histology. This work was supported by grants from the Wellcome Trust (M.H.), ERC (StG 678790 NEWRON to C.S.-H. and AdG 695709 DendriteCircuits to M.H.) and Gatsby Charitable Foundation (M.H.). Publisher: NPGNY; Journal: NN: Nature Neuroscience; Article Type: Article DOI: 10.1038/

Code and data availability.

Data analysis and simulation code are available from a private repository on GitHub (https://github.com/neurodroid/SH2017, access available upon request). The data that support the findings of this study are available from the corresponding authors upon reasonable request.

<jrn>51.

COMPETING FINANCIAL INTERESTS

The authors declare no competing financial interests.

Reprints and permissions information is available online at http://www.nature.com/reprints/index.html.

Publisher's note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


Marc Shapiro

Bettina Kemme

Eventual Consistency

Keywords:

Definition

In a replicated database, the consistency level defines whether and how the values of the replicas of a logical object may diverge in the presence of updates. Eventual consistency is the weakest consistency level that guarantees convergence. Informally, it requires that all replicas of an object will eventually reach the same final value, assuming that no new updates are submitted to the object.

Formal Definition and Usage

Eventual consistency is an important correctness criterion in systems with a lazy, updateanywhere strategy, also referred to as optimistic replication. Update operations can be submitted and executed on any node, and the propagation of updates occurs lazily after they are committed. Conflict resolution and reconciliation must ensure that all replicas (copies) of a logical object eventually converge to the same value. Different objects are considered independent. Especially in wide-area settings, also referred to as geo-replication, and mobile computing environments, eventual consistency is popular, as it allows individual replicas to serve client requests and provide a response before coordinating with other replicas. Conflict-free replicated data types (CRDTs) were invented to encapsulate and hide the complexity of managing eventual consistency. 1

In a system where updates are continuously submitted, eventual consistency can be defined by a weak form of schedule equivalence [START_REF] Saito | Optimistic replication[END_REF]. A schedule S x n describes the sequence of update operations that a node n performs on its replica of object x. An element of the schedule of the form w i represents the execution of an update to object x, submitted by some user. S x n contains an element of the form w i , if the update w i was received by n, but either not executed, or aborted due to conflict resolution.

Typically, two schedules are defined equivalent by restricting how the order of operations in the two schedules may differ. However, for eventual consistency, only the final convergence of object values matters. Thus, equivalence is defined by comparing the final state of the replicas. Two schedules are said state equivalent when, starting from the same initial state, they produce the same final state. For instance, (i) schedules S = w 1 w 2 and S 0 = w 2 w 1 are state-equivalent if w 1 and w 2 commute; (ii) schedules S = w 1 w 2 and S = w 2 are state-equivalent if w 2 overwrites the state of the object to a completely new value (e.g., x := 2). Eventual consistency of a replicated object x is defined by the following conditions, which must hold at all times, at any node n with a replica of x [START_REF] Saito | Optimistic replication[END_REF]. It is assumed that all replicas have the same initial state:

• There is a prefix of the schedule S x n that is state equivalent to a prefix of the schedule S x n of any other node n holding a replica of x. Such a prefix is called a committed prefix of S x n . • The committed prefix of S x n grows monotonically over time, i.e., the set of operations and their relative order remain unchanged.

• For every operation w i submitted by a user, either w i or w i eventually appears in the committed prefix of S x n (but not both and not more than once). • An operation of the form w i in the committed prefix satisfies all its preconditions (e.g., the state of the object immediately before the execution of the operation fulfills certain conditions).

As an example, assume operation w 1 sets x to 2, and w 2 sets it to 5. Operation w 1 is submitted and executed at node n 1 , while w 2 is first executed at n 2 . At this time, the local schedules are S 1 = w 1 and S 2 = w 2 and the committed prefix at both nodes is the empty schedule. Now w 1 is propagated to n 2 , and w 2 is propagated to n 1 . When n 1 receives w 2 , it detects that w 1 and w 2 are concurrent and conflict. Say that conflict reconciliation prioritizes one of the operations, e.g., w 1 . Then, w 2 is simply not executed and the new schedule is S x 1 = w 1 w 2 . At n 2 , when w 1 arrives, the conflict is also detected, w 2 is undone, w 1 is executed and the final schedule is S 2 = w 2 w 1 . At this time, S 1 and S 2 are themselves the committed prefixes. Note that further concurrent operations on x might move the schedules further, but the extensions would still be tentative and only become committed once they are reconciled at all replicas.

Cross-References

• Consistency Models for Replicated Data


Christelle Al Hasrouty
email: alhasrouty@labri.fr

Cristian Olariu
email: cristian.olariu@ucd.ie

Vincent Autefage
email: autefage@labri.fr

Damien Magoni
email: magoni@labri.fr

John Murphy
email: j.murphy@ucd.ie

SVC Videoconferencing Call Adaptation and Bandwidth Usage in SDN Networks

Videoconferencing applications have strong latency requirements and consume large portions of a network's bandwidth. Current videoconferencing solutions are not efficiently implemented as they often rely on a central server and do not leverage network layering services. In this paper, we investigate the impact of using Scalable Video Coding and Software Defined Networking techniques on videoconferencing. Specifically we propose an algorithm capable of reducing the bandwidth consumed by videoconferencing using Software Defined Networking to compute and deploy multicast trees, as well as taking advantage of the Scalable Video Coding layering feature that allows to sacrifice video quality for usability purposes. We show that by smartly dropping video layers at specific locations in the network, the overall bandwidth usage by videoconferencing decreases, and in a separate capacity study we show that our solution allows networks to support more videoconferencing calls as compared to existing solutions.

I. INTRODUCTION

Videoconferencing enables live video communication between three or more participants in different locations, each possibly equipped with different devices. The development of free applications and low cost devices has popularized the use of videoconferencing among both individuals and businesses. However, the widespread use of mobile devices implies wireless network constraints, such as bandwidth availability and latency which makes it harder to maintain a high Quality of Service (QoS) for all users. Two general methods exist for connecting all participants together. In the first one, typically used in standalone conference systems, a central control device is used to connect multiple heterogeneous participants in a video-conference call. This centralized control device, usually called Multipoint Control Unit (MCU), acts as a bridge for these participants and adapts their channels. The MCU is located in a premise providing large and stable network bandwidth. Inside the MCU, a multipoint media processor is used to re-encode the audio/video stream in order to match the other participants' video requirements. This operation requires significant processing power. In the second method, each participant directly connects to every other participant with a point-to-point connection. Video adaptation is done in the devices of the participants. To overcome the re-encoding problem, videoconferencing systems have started to use Scalable Video Coding [START_REF] Schwarz | Overview of the scalable video coding extension of the h. 264/avc standard[END_REF] (SVC). SVC is a layerbased video compression technique which allows a video stream bitrate to be reduced by removing some layers of it without preventing the stream to be decoded. Thus, SVC avoids any re-encoding and streams can easily be degraded to limit bandwidth consumption. While SVC allows a better control over the stream bitrate, the layers' selection is only done at the endpoints or in the MCU and remains unchanged inside the core of the network. In order to adapt the streams inside the network, we have defined in this paper an algorithm leveraging SDN (Software Defined Networking) for building multicast distribution trees and dropping video layers at certain network locations leading to optimized network usage. Our algorithm is able to define where inside the network, and how many video layers, should be dropped in order to adapt the streams to the bandwidth capacities of the receiving devices. Our solution is targeted at network operators and providers where the SDN-capable network is managed by a single entity.

Section II presents a brief state of the art on videoconferencing and SDN technologies. Section III details the model and assumptions of our proposal and describes an example scenario. It also provides a thorough description of our algorithm for setting up video-conference calls. Finally, Section IV details the methodology and parameters used in our simulations and provides results related to the bandwidth usage and latency values of calls related to parameters such as network topology type, network size and number of participants. It also provides results concerning the call capacity of the network.

II. RELATED WORK

In recent years, many efforts have been made on videoconferencing systems in order to improve the QoS for users while saving network resources. In order to cope with encoding/decoding complexity and network dynamics on video transmitted over a network, the ITU has defined the Annex G of the H.264 standard, called Scalable Video Coding [START_REF] Schwarz | Overview of the scalable video coding extension of the h. 264/avc standard[END_REF] in 2007. SVC allows the bitrate adjustment of video streams without re-encoding and is currently implemented in many hardware devices.Using IP multicast is a logical approach for optimizing IP-based multiparty calls but network operators have always been reluctant to deploy it because of the need to store much state information in the routers. Only broadcast services, such as IPTV, have been partially supported by IP multicast on some ISP networks. Constructing multicast trees for multi-layered video has been studied as early as 1999 in [START_REF] De Amorim | Single-loop packet merging for receiver-oriented multicast multi-layered video[END_REF], however, video layers could only be managed at the endpoints. Indeed, in traditional networks (i.e., non-SDN), data packets can not be modified in the routers on a per-communication basis. Thus, SDN is the only possible way for implementing multicast and modifying packets on the fly inside the switches. In 2000, Wang and Hou have classified multicast routing problems according to their optimization functions and performance constraints [START_REF] Wang | Multicast routing and its qos extension: problems, algorithms, and protocols[END_REF]. In their classification, our proposal targets the "link and tree constrained tree optimization" problem aka the "constrained Steiner tree" problem which has been proved to be NP-complete. Zhao et al. have used a multicast approach over a SDN network [START_REF] Zhao | Software defined networkenabled multicast for multi-party video conferencing systems[END_REF]. In their proposal, SDN is used to centralize a full view of the network and to apply an efficient selection and distribution of video streams. Their solution achieves higher video stream bitrates with a slight increase on delays. Unfortunately, this study does not intend to maximize streams quality since all users receive video flows at the same bitrate. Moreover, their experimentations do not provide any results on global bandwidth consumption and only focuses on small-scale networks (under 150 nodes). Laga et al. study the benefits of using a SDN/SVC based solution in order to optimize delivery paths of each SVC layer [START_REF] Laga | Optimizing scalable video delivery through openflow layer-based routing[END_REF]. Their approach significantly reduces the amount of video freezes even in a congested network. Those results validate the benefit of SDN in the context of a video delivery system. Nevertheless, their work only focuses on a video delivery from a single source to a single destination. Furthermore, they only provide results on video freezes on a small-scale network (under 10 nodes). A recent videoconferencing system combining a multicast distribution, a SDN network and SVC streams has been proposed [START_REF] Yang | A video conferencing system based on sdn-enabled svc multicast[END_REF]. Similarly to our proposal, the SDN controller is used to manage and adjust the distribution of video layers in order to both optimize the QoS of each participant and reduce the network usage compared to a classic MCU approach. Contrary to our study, their solution primarily focuses on reducing bandwidth consumption on core network links to the detriment of the flow quality received by the users. Besides, participants' capability relies on the screen size and not on the network access links properties. Finally, their evaluation has only been performed on a small-scale grid topology as opposed to our experiment which relies on realistic large-scale network topologies.

III. SYSTEM MODEL AND ALGORITHM

In this section, we describe the model of our system as well as the algorithm for setting up video-conference calls. To the best of our knowledge, no network operator deploys IP multicast protocols for video conferences. Thus, using a SDN network is the only way of duplicating and modifying the streams inside the network. Application-layer multicast can only be deployed at endpoints and is not currently leveraged by video conferencing applications.

A. Videoconferencing Model

When a video-conference is set between a number of users, these users are called participants. A participant is, at the same time, a sender of its video stream and a receiver of the video streams of all other participants. The participants are placed randomly in the network by being connected to any node of the network. Many participants can be connected to the same node. Participants are considered to be connected wirelessly to their node by a 4G cellular technology such as LTE. Each node of the network is supposed to provide a wireless access function (such as an eNode-B) and an SDN switching function. As the network is SDN-enabled, we assume that all nodes within the network contain OpenFlow switches and can communicate with an SDN controller which is responsible for the management of the calls. All switches are able to adapt SVC streams by dropping layers on specific paths indicated by the controller, starting with the most enhanced layer first. In this work, we have considered that the number of participants in a call can vary between 3 to 12. For scenarios with larger values (above 6), we assume that participants have appropriate devices for conferencing (e.g., large tablets, laptops, mobile A/V systems). As discussed in the previous section, SVC streams are structured in layers, all built upon a base layer. In our case, we consider that the SVC layers consist of a base layer L1, and three enhanced layers L2, L3, and L4. In addition, a given layer can be used only if all the lower layers are also received. Each participant accepts the highest number of layers allowable by its downlink capacity. With only the base layer, the participant will receive the lowest video quality. If the participant's downlink capacity falls below what is required to receive the base layer, it can still remain in the conference if it can at least receive an audio-only stream of 32kbps. If any participant can not receive the audio stream, the conference call is rejected. Four SVC profiles and one fallback audio-only profile are used in the following simulations. The indicated bitrates include network headers' overhead and audio streams (for SVC profiles):

• Audio-only, ~32kbps The audio-only profile enables receivers with very low access link bandwidth to participate in the call. Access links are wireless, which make them subject to variable communication channel conditions. This randomness in access bandwidth availability can lead to a large heterogeneity of bandwidth between the participants. Therefore, during a video call, each participant sends the maximum bitrate stream that can be consumed by at least one receiver, and this stream is then degraded (i.e., higher layers are dropped) to adapt to the participants with lower downlink bandwidth capacity. After discovering the network topology and channel conditions using SDN's capability to provide a global view of the state of the network, it is significantly easier to identify the locations of the switches where it is necessary to degrade SVC streams as compared to the situation when SDN is not used. Figure 1 shows a call scenario example with 6 participants. The D i values represent the available downlink bandwidth for each access link of each participant. The uplink bandwidth of each participant is assumed to be higher than the highest quality video stream (i.e., above 1Mbps). The d i values indicate the SVC stream bitrate received per participant. Thus, at any participant i, 5 × d i < D i . Each video stream harbors the color of its sender. Each arrow points to the direction of the video stream and is labeled by the number of layers sent. For instance, an arrow labeled 3 represents a video stream containing layers 1 to 3. A stream can be degraded by removing layers at any switch but it can never be upgraded in quality inside a switch. It must be noted that our solution does not preclude the use of encrypted datagram connections (such as DTLS). By sending each layer on a different UDP destination port, the switches can drop the layers just by looking at the IP addresses and UDP port numbers, without the need to decrypt the DTLS payload.

B. Algorithm for Setting up a Videoconference Call

The algorithm, executed in the SDN controller for setting up a videoconferencing call, builds a multicast tree from each participant (sender) to all the others (receivers) and relies on several assumptions:

• For n participants, n source-rooted multicast trees will be built. • For optimal synchronization, all SVC layers belonging to the video stream emitted by one sender, follow the same paths. There is one tree per video stream, and branches of the tree carry all or only a subset of the video layers. • Access downlink bandwidth is chosen randomly for each participant from a range of plausible 4G data rates and does not vary over the duration of the call in one simulation instance. To introduce variability, we run 100 simulations for each scenario with a different seed. We plan for future work to add bandwidth variations on the access links' characteristics during a call, which will trigger a rerun of the algorithm below. • Core links are supposed to all have the same bandwidth dedicated for this type of A/V traffic (set between 100Mbps to 1Gbps depending on the scenario). This means that links may have different bandwidth capacities but they all reserve the same amount of bandwidth for the videoconferencing calls. We assume the SDN network to be WAN-sized (i.e., from 500 to 4000 nodes). • The SDN controller knows the complete topology of the network, the available bandwidth on each core link, the position of the participants as well as their available uplink and downlink access bandwidth. • Any SDN switch can degrade (i.e., drop higher quality layers) any SVC stream.

The optimization goal of our proposed scheme is to minimize the total bandwidth used by a call, while maximizing the bitrates received by each participant. Furthermore, our scheme is link constrained (i.e., the sum of the streams on any link can not exceed its bandwidth capacity), and tree constrained (i.e., the sum of the delays over any path can not exceed a given threshold). Thus, for the Wang and Hou classification [START_REF] Wang | Multicast routing and its qos extension: problems, algorithms, and protocols[END_REF], our proposed scheme targets the link and tree constrained tree optimization problem aka the constrained Steiner tree problem which is NP-complete. The algorithm 1 proposed for constructing the videoconference call is based on a single source/sender approach. It is a non optimal heuristic that builds the tree backwards from each receiver to a given sender and then reiterates the procedure for every sender. It is composed of four main steps:

1) Collecting the downlink bandwidth for each participant (line 1). 2) Computing the receiving and sending bitrates for each participant (lines 2-3). 3) Building a multicast tree from each participant to all the others if capacity permits (lines 4-25). 4) Checking the latencies over all paths between participants.

The following algorithm will build the video stream distribution tree for each sender, and if no solution is found, the call is rejected. This can happen when bandwidth capacity is reached, or end-to-end latency is higher than a threshold. Only an accepted call will trigger the SDN controller to setup the routing rules in the switches. In step 1, the controller retrieves the downlink bandwidth value of each participant by polling its network access switch. In step 2, the receiving bitrate of each participant is calculated by first dividing its downlink bandwidth by the number of participants excluding itself, and then by picking the highest bitrate level lower or equal to this computed value (line 2). This means that any given receiver will ask for the same bitrate from all the senders (optimizing reception with different bitrates would increase the algorithm's complexity and is left for future work). The sending bitrate is then defined as the maximum received bitrate level found among all participants, noted B l (line 3). As the uplink bandwidth is considered to be always higher than the highest bitrate level B 1 , the sending bitrate B l is thus the same for each participant. It may be lower than the highest quality bitrate B 1 if no receiver can receive B 1 .

In step 3, each sending participant builds a multicast tree to all its receivers (line 4). The bitrate levels are sorted from the highest B 1 to the lowest B m (line 6). The receivers R j are sorted by decreasing downlink bitrates and, at any given bitrate, by increasing distances (in hops) to the sender (line 7). For the highest bitrate B l and the first receiver nearest to the sender, a shortest path is built to the sender (line 12). Then, for the other receivers at the same bitrate B l , two modes are defined for connecting to the sender:

• Minimizing Spanning Tree (MST): a shortest path is built up to the closest switch belonging to the tree, thus making a spanning tree which minimizes bandwidth usage in the network (line 16). It is a heuristic which does not necessarily provide a mininum spanning tree, hence the term minimizing. • Shortest Path Tree (SPT): a shortest path is built up to the sender, potentially stopping at the first switch belonging to the tree, thus making a shortest path tree which minimizes latency between participants (line 20).

If no path is found by function BuildShortestPath, due to saturated links, the call is rejected. The algorithm is stopped and the SDN controller doesn't need to operate changes on the network. If a path is found, the stream is then duplicated at the junction switch found by one of the above methods (line 24). After all the receivers having the highest bitrate B l are connected to the sender, they form a tree T i = F i,l . The next highest receiving bitrate B k is then chosen and receivers having this bitrate, again sorted by their closeness to the source, connect to the T i tree by one of the two modes described earlier. In step 4, each path is checked against the maximum acceptable latency. If the latency is higher, the call is rejected (latencies between participants can be computed when building the trees). The variables used in this algorithm are defined in Table I.

Algorithm 1: Setup of the Videoconference Call BuildVideoCall() return Bool 1 SC collects all D i 2 SC computes all d i = max 1≤k≤m (B k ) | B k ≤ D i /(p -1) 3 SC computes all u i = max 1≤i≤p (d i ) = B l 4 foreach S i , i ∈ 1, p do 5 T i ← {0} 6 foreach B k , k ∈ l, m | ∀ 0 < k < m, B k > B k+1 do 7 foreach R j , j ∈ 1, p | R j = S i ∧ d j = B k ∧ dist(R j , S i ) ≤ dist(R j , S i ) ∀ j > j do 8 P j ← {∅} 9 N ← {∅} 10 if B k = B l then 11 if j = 1 then 12 P j ← BuildShortestPath(R j , S i ) 13 if P j = {∅}
T i = T i ∪ P j 38 foreach S i , i ∈ 1, p do 39 foreach R j , j ∈ 1, p | R j = S i do 40 if latency(S i , R j ) > M

C. Computational Complexity

In order to obtain the shortest paths needed by our algorithm, we need to compute the Dijkstra algorithm for all nodes in the network. The complexity of Dijkstra on a sparse graph of size n (i.e., the number of edges is in O(n)) is O(n 2 × log n) with a Fibonacci heap implementation. If the graph is dense (i.e., the number of edges is in O(n 2 )), the complexity becomes O(n 3 ). These path computations can be done upfront and results can be stored in a multidimensional array. Obtaining a shortest path from this structure takes at most O(n) steps. If we define p as the number of participants in the call and k the number of video layers, then the complexity of our algorithm is O(p 2 × k × n). Given that both p and k are very small and independent of n, the complexity of our algorithm becomes O(n). The final complexity is thus equal to the one required by Dijkstra for computing all shortest paths.

IV. EVALUATION

This section presents the evaluation of our videoconferencing call setup algorithm compared to a typical unicast approach. The results presented here have been obtained by simulations in order to study large network topologies. We have developed a static simulator in Python implementing our algorithm. Because we do not consider time in our simulations, network dynamics such as packet loss have not been taken into account. The code is open-source 1 and can be easily ported to a Python SDN controller such as POX or Ryu. SVC streams have been simulated following their bitrate requirements as indicated in section III-A.

A. Parameters

For evaluating our solution, we need to know the topologies of some network operators. As this information is quite difficult to obtain, we have generated synthetic maps of various sizes by using the Erdös-Rényi model (ER) [START_REF] Erdös | On random graphs i[END_REF], as well as our Magoni-Pansiot model (MP) [START_REF] Magoni | Internet topology modeler based on map sampling[END_REF] where the degree distribution follows a power law (as observed in the Internet and in large communication networks). This will enable us to assess the impact of the topology on our solution. The presented results are thus limited by the validity of these topologies compared to real ones. We compare the results from the three types of connection modes, namely i) SPT, ii) MST and iii) unicast. See Section III for SPT and MST details. In our simulations, the access downlink capacity between a participant and its access switch is randomly selected from 4 Mbps to 14Mbps and the uplink bandwidth is set to 1.5Mbps, which are conservative real-life values observed in current 4G LTE networks [START_REF] Buenestado | Analysis of throughput performance statistics for benchmarking lte networks[END_REF]. The core links are supposed to have a dedicated and limited bandwidth for live A/V communications such as videoconferencing (the value is indicated in the figure captions). Access links delays are set to 30 ms (a typical average value as shown in [START_REF] Laner | Latency analysis of 3g network components[END_REF]) and core link delays are set to 10 ms (as observed in [START_REF] Hoerdt | Cartographie distribuée du coeur de l'internet[END_REF]). The maximum latency authorized over any path is set to 250ms. Most of our results are obtained by instantiating each network topology type 100 times, a different instance every time, for every network size. For each of this network instance, the position of the participants in the network and their access link capacity is changed 100 times, each time in a different simulation. This is achieved using a different seed for the random number generator. Thus, each point on the following plots is the average of the values obtained from 10,000 simulations. For some results, this number has been lowered in order to reduce computation time. In this case, the number of runs is indicated in the captions.

B. Results

As the relative errors, measured at 95% confidence level, were always below 5% in figures 2 to 5, the error bars were not depicted. The error bars are shown for all the other figures. Figure 2 shows the impact of the number of participants on the total bandwidth used by a video call. The total bandwidth is defined as the sum of the call bitrates on every used link. While not meaningful in itself, this value is helpful for comparing the three approaches. As expected, for both topologies, the MST mode is the least bandwidth consuming, closely followed by the SPT mode. They both exhibit a sub-linear relationship between the number of participants and the bandwidth consumption. The unicast mode, on the other hand, exhibits a polynomial relationship and consumes much more bandwidth. This is due to the redundancy of the streams on the shared links. With 8 participants, each of the two multicast modes roughly consumes up to 70% of the bandwidth used by the unicast mode and at 12 participants, this ratio drops to 40%. The bandwidth gain of our solution increases with the number of participants until it is bounded by the maximum possible number of participants. Figure 3 shows the influence of the network topology and size on the total bandwidth used by a call. The bandwidth used slowly increases with the network size because average distances, and thus paths taken by the video streams, do also marginally increase with the network size. From 500-node to 4k-node sizes, the largest increase is around 25% for unicast and 30% for SPT. The network size has a significant influence on the bandwidth used by a call, although smaller than the number of participants. Figure 4 shows the impact of the number of participants on the maximum latency of a call. The maximum latency of a call is defined as the maximum latency measured over all paths between all participant pairs. The latency is exactly the same for the SPT and unicast modes, as expected, and increases marginally with the number of participants (e.g., +15% between 3 and 12 participants in MP topologies). The MST mode, however, has an important impact on the latency which increases with the number of participants (+60% between 3 and 12 participants in ER topologies). This is expected as the participants will optimize their paths to the tree but not to the source thus leading to longer paths. Latency values remain acceptable however, for live interactive communications, except for MST mode on ER topologies which results in latencies above the commonly accepted 250ms limit. Figure 5 shows the influence of the network size on the maximum latency of a call. As with Figure 4, we observe that the network size has a bigger influence on the latency in the MST mode. This is expected as this mode is more likely to select longer alternate paths whose number increases when the network size increases. SPT and unicast modes are not much influenced by the network size, especially over MP topologies. This is also expected as MP topologies are power-law type graphs whose average distance and diameter does not increase when the network size increases. Figure 6 shows the impact of the network size on the network call capacity. The network call capacity is determined as follows: calls are randomly generated (i.e., participants' position and access bandwidth capacity) and added on the network one after the other. At some point, the BuildVideoCall function defined in Section III will return false, indicating that the call could not be setup because one or more links involved in the call were saturated (i.e., filled at the maximum of their bandwidth capacity). In this case, the call is rejected and the network call capacity is considered reached. As our algorithm is a non optimal heuristic, the number of supported calls thus depends on the sequence of construction of all the calls which are themselves randomly generated.

For each experiment, the network capacity will thus slightly vary. As the process of calculating the call capacity is very time consuming, we have performed only 100 experiments on MP networks only (as MP topologies are more realistic than ER ones) with core link bandwidth set to 500Mbps (instead of 1Gbps). On this figure, as well as on Figure 7, points show the average capacity of the 100 experiments, while the error bars show the standard error of the mean. The error bars are significant because of the limited number of values used (i.e., 100). For any mode, the call capacity does not increase linearly with the network size but flattens when the size increases. This is due to the fact that some links are much more used than others, given their strategic position in the network (especially in MP power-law type topologies), and they become bottlenecks. To leverage the network size, bigger bandwidth shall thus be used in those links if possible. For 4k-node networks, and assuming that each core link of the network has 500Mbps of dedicated bandwidth for A/V call traffic, we can see that our MST mode enables more than 1050 simultaneous calls while the standard unicast approach supports around 730 calls, translating in a 43% improvement. The gain is smaller for lower network sizes such as 500-node networks where a 35% is improvement is observed. The MST mode enables more simultaneous calls than the SPT mode but the gap is much smaller than compared to unicast.

V. CONCLUSION

Improving videoconferencing systems can lead to large bandwidth savings for network operators and can increase their ability to serve a larger number of customers. In this paper, we have proposed a videoconferencing system leveraging the SDN architecture. Our solution provides adaptive SVC layers to each participant by adapting them inside the network at the most appropriate place. In addition, it uses multicast for eliminating stream redundancy. Our results show that a videoconference call based on our MST mode uses only a fraction of the bandwidth of a unicast-based videoconference system (70% at 8 participants and 40% at 12 on a 2knode network) while increasing the average path latency by 25% at 12 participants, but still remaining under 150 ms. Regarding the call capacity of the network, our results show an increase of 35% to 49% more calls (depending on the network size, at a given core link bandwidth) for our SDN-based solution compared to a typical unicast approach with stream adaptation on the edge switches. Results also exhibit call capacity gains from 80% to 36% when varying the bandwidth of the core links in networks of a given size. Thus, our solution enables SDN-ready telco operators to significantly increase the call capacity of their networks. Our system is designed to dynamically adapt to time-evolving bandwidth capacity for the user's access link, however testing this capability is the object of a future work, together with evaluating a prototype implementation over a virtual network for re-assessing our current results obtained by simulations.

Fig. 1 .

 1 Fig. 1. Video-conference example

  1 http://www.labri.fr/perso/magoni/cemeqacs

Fig. 2 .

 2 Fig. 2. Bandwidth consumption per call vs modes used and participants (2knode network size, 1Gbps core links)

Fig. 3 .

 3 Fig. 3. Bandwidth consumption per call vs modes used and network type/size (6 participants, 1Gbps core links)

Fig. 6 .

 6 Fig.6. Call capacity vs network size (6 participants, 500Mbps core links)

Fig. 7 .

 7 Fig. 7. Call capacity vs core link bandwidth (2k-node, 6 participants)

ACKNOWLEDGMENT

This work was supported, in part, by SFI grant 13/RC/2094 to Lero -the Irish Software Research Centre, and in part by ANR grant 10IDEX-03-02 to the University of Bordeaux.