Modélisation macroscopique géométrique des réseaux d'accès en télécommunication Catherine Gloaguen Orange Labs [email protected] Journée

Modélisation macroscopique géométrique des réseaux d'accès en télécommunication

Catherine Gloaguen Orange [email protected]

Journée inaugurale SMAI-MAIRCI, Issy, 19 Mars 2010

Orange LabsGloaguen, Journée SMAI-MAIRCI 19 Mars 2010 – p2

Summary

1. Introduction

2.Network Topology Synthesis (NTS) principle

3. Models for road systems

4. Computation of shortest path length between nodes

5. Validation on real network data (Paris, cities, non denses zones)

6. Potential applications and optimization problems

7. Conclusion

Gloaguen, Journée SMAI-MAIRCI 19 Mars 2010 – p3 Orange Labs

1Introduction


The access network merges in civil engineering

Path of Distribution cables

Side street

Main

road

Approximate scale 200m x 200m

Path of Transport cables

Closest to the customer


Road systems are complex

The morphology of the road system depends on the scale and the type of town


France Telecom needs reliable tools with the ability to : analyze complex large scale networks in a short time compensate for too voluminous or incomplete real data sets address rupture situations in technology or network

architecture

Our approach proposes an explicit separation of the topologies of the territory and the

network analytical models for road systems and access networks

Joint work with Volker Schmidt and Florian VossInstitute of Stochastics, Ulm University, Germany{Volker.Schmidt, Florian.Voss}@uni-unlm.de

NETWORK TOPOLOGY SYNTHESIS (NTS)


2NTS principle illustrated on fixed acces problematic

8Gloaguen, Journée SMAI-MAIRCI 19 Mars 2010 – p8

Dis_DistLH(PLT, 26, 0.043, x)

Analytical formula

Length distribution of connectionsA small part of the access network

NTS is a macroscopic model


Road system

ObjectsReality

Model

Mathematical model for roads


"High" node

Road system

ObjectsReality

Model

Number of "High" nodes sites



"High" node

Action area

Road system

ObjectsReality

Model




"High" node

Action area

Road system

ObjectsReality

Model


Principle Voronoï cell of center H



"High" node

"Low" node

Action area

Road system

ObjectsReality

Model



Number of "Low" nodes sites



"High" node

"Low" node

Action area

Road system

ObjectsReality

Model




Connection Principle shortest path on roads from L to H



"High" node

"Low" node

Action area

Road system

ObjectsReality

Model






Analytical formula


"High" node

"Low" node

Action area

Road system

ObjectsReality

Model






Analytical formula


L'analyse repose sur une vision globale

Quelques règles simples et logiques pour décrire un réseau d'accès fixe

Les noeuds colocalisés (sites) sont situés le long de la voirie La zone d'action d'un noeud H est représentée comme l'ensemble des

points les plus proches de H L'ensemble du territoire est couvert par au moins un des sous réseaux La connexion se fait au plus court chemin sur la voirie

Simplifier la realité en conservant les caractères structurants utiliser la variabilité observée

les ensembles de sous réseaux sont considérés comme échantillons statistiques d'un sous réseau virtuel aléatoire

on décrit les lois de ces sous réseaux

"La science remplace le visible compliqué par de l'invisible simple" (J. Perrin)


3Models for road system


Mathematical models for road system Just throw objects in the plane in a random way to generate a

"tessellation" that can be used as a road system. Several models are available built on stationary Poisson processes

Simple tessellations

Poisson Line

throw lines

PLT PDT PVT

Poisson Delaunay

throw points

relate each points to its neighbors

Poisson Voronoï throw points,

construct Voronoï cells

erase the points


"Best" model choice

A constant defines a stationary simple tessellation The meaning of depends on the tessellation type Theoretical vector of intensities specific for each model

Mean values model → per unit area ↓

PLT [L]-1

PDT [L]-2

PVT [L]-2

Number of nodes (crossings) 2/ 2

Number of edges (street segments) 2 2/ 3 3

Number of cells (quarters) 2/ 2

Total edge length (length streets) 32 √ /(3 ) 2 √


Fitting procedureRaw data Preprocessed

data

+ 133 dead ends



data

+ 133 dead ends

634 crossings1502 street segments 418 quarters 112 km length streets

Unbiased estimators for intensities



data

+ 133 dead ends


Theoretical vector for potential models

Minimization of distance




data

+ 133 dead ends

634 crossings1502 street segments 418 quarters 112 km length streetsBest simple tessellation

PVT = 45.3 km-2






data

+ 133 dead ends





+ 133 dead ends


Best simple tessellationPVT

= 45.3 km-2


More realistic iterated tessellations


Data basis for urban road system in one Excel sheet

Parametric representati

on of the road system


Modélisation de la voirie urbaine (ex Lyon)

PhD thesis (T. Courtat) on town segmentation and morphogenesis

New road models and tools

PLT

21,6 km-1

PVT

45,4 km-2

PVT

20,7 km-2

PVT

20,5 km-2


Why should we bother to construct /use models ? A model captures the structurant features of the real data set

a "good" choice takes into account the history that created the observed data

ex PDT roads system between towns

Statistical characteristics of random models only depend on a few parameters

the real location of roads, crossings, parks is not reproduced …but the relevant (for our purpose) geometrical features of the road system

are reproduced in a global way.

Models allow to proceed with a mathematical analysis (of shortest paths)

final results take into account all possible realizations of the model no simulation is required


4Computation of shortest path length between nodes


Recall on the access network problem

Random equivalent network model Road system : an homogeneous random model 2-level network nodes (LLC and HLC) :randomly located

on the roads Connection rules : logical & physical

What about the distance LLC→HLC? The aim is to provide approximate & reliable analytical

formulas for mean values and distributions

Geographical support Network nodes location Topology of connection

LLCs

HLC


Serving zones The action area of HLC is a Voronoï cell

Every LLC is connected to the nearest HLC, measured in straight line

The serving zones define a Cox-Voronoï tessallation random HLC are located on random tesellations (PLT, PVT, PDT)

and not in the plane


It is representative for all the serving zones that can be observed same probability distribution as the set of cells in the plane or conditional distribution of the cell with a HLC in the origin

Simulation algorithms for the typical zone are specific to the model

Typical serving zone

1 realization of the typical cell by the simulation algorithm

PLCVTPoisson-Line-Cox-Voronoï-

Tessellation

Typical PLCVT cell

infinite number of realizations

all the cells

Distribution of cell perimeter

Point process of HLC

HLC in O


Same probability distribution as the set of the paths in the plane

Typical shortest path length C*

Marked point processthe length of the shortest path to its HLC is associated to every LLC

"Natural" computation Simulate the network in a sequence of

increasing sampling windows Wn

compute all the paths and their lengths

the average of some function of the length is

Point process of HLC

Point process of LLC


Equivalent writings for the typical shortest path length LLC->HLC distribution of the path length from a LLC conditionned in O Neveu exchange formula for marked point processes in the plane

applied to XC (LLC marked by the length) and XH distribution of the path length to a HLC conditionned in O

Alternative computation of C*

Computation in the typical serving zone

HLC in O

length of the path

from a point y to OLinear intensity

of HLC

Typical segment system in

the typical serving zone


Simulate only the typical serving zone and its content

Density estimation the segment system is divided into M line segments Si = [Ai ,Bi ] probability density

estimated by a step function on n simulations

Probability density of C*


Scaling properties no absolute length -> 1/ is chosen as unit length

up to a scale factor, same model for fixed = /(roads/HLC) measures the density of roads in the typical cell


Choice of a parametric family theoretical convergence results to known distributions & limit

values limited number of parameters, but applies to all cases and

values, Truncated Weibull distributions

Parametric density fitting


From extensive simulations made once…. density estimation n=50000, PVT, PDT, PLT: find parameters and for 1< <2000 approximate functions ( ) and ( ) for each type

…. to instantaneous results & explicit morphology of the road system

Library of parametric formulae C*

Maj_DistLH (PLT, 26, 0.043, q)

Road : PLT intensity 26 km-1

Network : HLC intensity 0.043 km-1

Mean length 536 m

with prob. 85% , the length < 827 m

Dis_DistLH(PLT, 26, 0.043, x)

LLC

HLC


5Validation on real network data


Transport (primary)

WCS

ND

ND

SAI

SAIs

Transport (secondary)

SAIs ND

ND

SAI

WCS

Geometrical analysis of the network in Paris

secondary service area interface

Distribution

network interface device

wire center station

service area interface

Distribution

Architecture nodes & logical links

Copper technology

Synthetic spatial view identification of 2-level subnetworks partition of the area in serving zones

for every subnetwork

Large scale

Middle scale

Low scale


C* for larger scale subnetwork Subnetwork WCS-SAI

Mean area of a typical serving zone = total area /(mean number of WCS)

~1000 = (total length of road /area) x (total lenght of road / numbre HLC)

on average 50 km road in a serving zone

WCS

SAI


C* for middle scale subnetwork Subnetwork SAI-SAIs or SAI-ND

Mean area of a typical serving zone = total area /(mean number of SAI)

~ 35, on average 2 km roads in a serving zone ND

SAI

SAIs


C* for lower scale subnetwork Subnetwork SAIs-ND

Mean area of a typical serving zone = total area /(mean number of SAIs)

~ 5, on average 300 m road in a serving zone

ND

SAIs


Straigthforward application to other cities Same formulae

Use the fitted road system(s) on the town under consideraion Right choice of parameters for the network nodes

Ex. of end to end connexions ND-WCS in a middle size French town

PVT 107 km-2

PVT 17 km-2

PVT 40 km-2

PVT 50 km-2


6Potential applications and optimization problems


Most network problems can be described by juxtaposition and/or superposition of 2 level subnetworks suitable choice of random processes for nodes location versus

road system nodes may also ly in the plane

logical connexion rules -> Voronoï cells aggregated cells, connexion to the 2nd, 3rd closest H node…

"physical" connexion rules Euclidian distance or shortest path on roads

The result is obtained by analysing ad hoc functionals of the typical cell

Stochastic geometry is a powerful toolbox


Shortest path lengths for fixed acces networks

Both L and H nodes on roads Connexion : shortest path on roads

Density of L- H distances on roads

Look at the shortest path distance for all points of the typical segment system in the typical

serving zone


Realistic cell description

H nodes on roads

HLC in O

Example of density of cell perimeter

Look at the geometrical charateristic of the typical cell : area, perimeter, number of sides

(neighbouring HLC)…


Euclidian distances

Density of L-H Euclidian distance

H nodes on roads L nodes in the plane Connexion : Euclidian distance

Value of the distribution function in x : look at the area of the intersection of the ball centered

in H with the typical serving zone


Euclidian distances

H and L nodes on roads Connexion : Euclidian distance

Value of the distribution function in x : look at the area of the intersection of the ball centered

in H with the typical segment system in the typical serving zone

Density of L-H Euclidian distance


Cell analysis for mobile networks purpose

Distribution of SINR ratio for point x

H nodes on roads L nodes in the plane Connexion : "propagation"

distance

Current work J.M. Kelif

Analysis on a typical cell and its neigbouring. Propagation parameters and conditions are

included in the functional, the road model and


NTS performance is not sensitive to the number of elements Best to describe huge and complex networks

NTS provides fast and global answers Determination of optimal choices by variyng parametres only in a macroscopic way

Entry point for further fine optimization processes

Optimization and planning


Core network without road dependency What is known

number of levels Mean number of lowest and highest nodes Cost functions (fixed and distance dependant )

Question find the number of middle level nodes that minimizes the cost

An "old" example : hierarchical network

32

21C421B2

10B10A03121

/

,

),,(/


Several technologies are available for optical fibre networks Choice of nodes to be equipped under constraint of eligibility

threshold

Impact of new technologies on QoS


Impact of new technologies on QoS

Upper bound at 95%

Given technology, coupling devices, losses…


7Conclusion


This validates NTS approach NTS allows to address a variety of networks situations

Modular Explicits underlying geometry and technology

Road system MUST be taken into account in specifc problems Cabling trees cannot be obtained without street system

Correction by a coefficient is not sufficient

incoming capacity


F. Baccelli, M. Klein, M. Lebourges, S. Zuyev, "Géométrie aléatoire et architecture de réseaux", Ann. Téléc. 51 n°3-4, 1996.

C. Gloaguen, H. Schmidt, R. Thiedmann, J.-P. Lanquetin and V. Schmidt, " Comparison of Network Trees in Deterministic and Random Settings using Different Connection Rules" Proceedings of SpasWin07, 16 Avril 2007, Limassol, Cyprus

C. Gloaguen, F. Fleischer, H. Schmidt and V. Schmidt "Fitting of stochastic telecommunication network models via distance measures and Monte-Carlo tests" Telecommunications Systems 31, pp.353-377 (2006).

F. Fleischer, C. Gloaguen, H. Schmidt, V. Schmidt and F. Voss. "Simulation of typical Poisson-Voronoi-Cox-Voronoi cells " Journal of Statistical Computation and Simulation, 79, pp. 939-957 (2009)

F. Voss, C. Gloaguen and V. Schmidt, "Palm Calculus for stationary Cox processes on iterated random tessellations", SpaSWIN09, 26 Juin 2009, Séoul, South Korea.

http://www.uni-ulm.de/en/mawi/institute-of-stochastics/research/projekte/telecommunication-networks.html

Documents

Modélisation macroscopique géométrique des réseaux d'accès en télécommunication Catherine Gloaguen Orange Labs [email protected] Journée