-
L. Addario-Berry,
R. E. L. Aldred,
K. Dalal,
and B. Reed.
Vertex colouring edge partitions.
J. Combin. Theory Ser. B,
94(2):237--244,
2005.
@article {MR2145514,
AUTHOR = {Addario-Berry, L. and Aldred, R. E. L. and Dalal, K. and Reed, B.},
TITLE = {Vertex colouring edge partitions},
JOURNAL = {J. Combin. Theory Ser. B},
VOLUME = {94},
YEAR = {2005},
NUMBER = {2},
PAGES = {237--244},
}
-
D. Avis,
C. De Simone,
and B. Reed.
On the fractional chromatic index of a graph and its complement.
Oper. Res. Lett.,
33(4):385--388,
2005.
@article {MR2127410,
AUTHOR = {Avis, D. and De Simone, C. and Reed, B.},
TITLE = {On the fractional chromatic index of a graph and its complement},
JOURNAL = {Oper. Res. Lett.},
VOLUME = {33},
YEAR = {2005},
NUMBER = {4},
PAGES = {385--388},
}
-
R. Bayon,
N. Lygeros,
and J.-S. Sereni.
New progress in enumeration of mixed models.
Applied Mathematics E-Notes,
5:60--65,
2005.
[WWW
] [PDF
]
@Article{BLS05,
author={R. Bayon and N. Lygeros and J.-S. Sereni},
title ={New progress in enumeration of mixed models},
journal={Applied Mathematics E-Notes},
volume={5},
year={2005},
pages={60--65},
URL={http://www.math.nthu.edu.tw/~amen/},
PDF={http://kam.mff.cuni.cz/~sereni/Articles/BLS05.pdf},
}
-
J-C. Bermond,
C. Colbourn,
D. Coudert,
G. Ge,
A. Ling,
and X. Muñoz.
Traffic Grooming in Unidirectional WDM Rings With Grooming Ratio C=6.
SIAM Journal on Discrete Mathematics,
19(2):523-542,
2005.
[PDF
]
| Abstract: |
|
SONET/WDM networks using wavelength add-drop multiplexing can be constructed using certain graph decompositions used to form a grooming, consisting of unions of primitive rings. The cost of such a decomposition is the sum, over all graphs in the decompositio n, of the number of vertices of nonzero degree in the graph. The existence of such decompositions with minimum cost, when every pair of sites employs no mo re than $\frac{1}{6}$~of the wavelength capacity, is determined with a finite number of possible exceptions. Indeed, when the number $N$ of sites satisfies $N \equiv 1 \pmod{3}$, the determination is complete, and when $N \equiv 2 \pmod{3}$, the only value le ft undetermined is $N = 17$. When $N \equiv 0 \pmod{3}$, a finite number of values of $N$ remain, the largest being $N = 2580$. The techniques developed rely heavily on tools from combinatorial design theory. |
@ARTICLE{BCC+05,
author = {J-C. Bermond and C. Colbourn and D. Coudert and G. Ge and A. Ling and X. Mu{\~n}oz},
title = {Traffic Grooming in Unidirectional {WDM} Rings With Grooming Ratio {C=6}},
journal = {SIAM Journal on Discrete Mathematics},
year = {2005},
volume = {19},
pages = {523-542},
number = {2},
abstract = {SONET/WDM networks using wavelength add-drop multiplexing can be constructed using certain graph decompositions used to form a grooming, consisting of unions of primitive rings. The cost of such a decomposition is the sum, over all graphs in the decompositio n, of the number of vertices of nonzero degree in the graph. The existence of such decompositions with minimum cost, when every pair of sites employs no mo re than $\frac{1}{6}$~of the wavelength capacity, is determined with a finite number of possible exceptions. Indeed, when the number $N$ of sites satisfies $N \equiv 1 \pmod{3}$, the determination is complete, and when $N \equiv 2 \pmod{3}$, the only value le ft undetermined is $N = 17$. When $N \equiv 0 \pmod{3}$, a finite number of values of $N$ remain, the largest being $N = 2580$. The techniques developed rely heavily on tools from combinatorial design theory.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCC+-DM05.pdf}
}
-
S. Choplin,
A. Jarry,
and S. Pérennes.
Virtual network embedding in the cycle.
Discrete Applied Mathematics,
145(3):368--375,
2005.
@article{CJP05,
author={S. Choplin and A. Jarry and S. P\'erennes},
title={Virtual network embedding in the cycle},
journal={Discrete Applied Mathematics},
volume={145},
number={3},
pages={368--375},
year={2005},
}
-
C. Cooper,
R. Klasing,
and M. Zito.
Lower Bounds and Algorithms for Dominating Sets in Web Graphs.
Internet Mathematics,
2(3):275--300,
2005.
@Article{CKZ05a,
title = { Lower Bounds and Algorithms for Dominating Sets in Web Graphs },
author = { C. Cooper and R. Klasing and M. Zito },
year = { 2005 },
journal = { Internet Mathematics },
volume = {2},
number={3},
pages={275--300},
}
-
D. J. Dougherty,
P. Lescanne,
L. Liquori,
and F. Lang.
Addressed Term Rewriting Systems: Syntax, Semantics, and Pragmatics: Extended Abstract.
TERMGRAPH: International Workshop on Computing with Terms and Graphs. Electr. Notes Theor. Comput. Sci.,
127(5):57--82,
2005.
[POSTSCRIPT
]
@article{DLLL05,
author = {D. J. Dougherty and P. Lescanne and L. Liquori and F. Lang},
title = {Addressed Term Rewriting Systems: Syntax, Semantics, and Pragmatics: Extended Abstract},
journal = {TERMGRAPH: International Workshop on Computing with Terms and Graphs. Electr. Notes Theor. Comput. Sci.},
volume = {127},
number = {5},
year = {2005},
pages = {57--82},
POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/termgraph-04.ps.gz}
}
-
H. Everett,
C. M. H. de Figueiredo,
S. Klein,
and B. Reed.
The perfection and recognition of bull-reducible Berge graphs.
Theor. Inform. Appl.,
39(1):145--160,
2005.
@article {MR2132584,
AUTHOR = {Everett, H. and de Figueiredo, C. M. H. and Klein, S. and Reed, B.},
TITLE = {The perfection and recognition of bull-reducible {B}erge graphs},
JOURNAL = {Theor. Inform. Appl.},
VOLUME = {39},
YEAR = {2005},
NUMBER = {1},
PAGES = {145--160},
}
-
B. Farzad,
M. Molloy,
and B. Reed.
$(\Delta-k)$-critical graphs.
J. Combin. Theory Ser. B,
93(2):173--185,
2005.
@article {MR2117935,
AUTHOR = {Farzad, B. and Molloy, M. and Reed, B.},
TITLE = {{$(\Delta-k)$}-critical graphs},
JOURNAL = {J. Combin. Theory Ser. B},
VOLUME = {93},
YEAR = {2005},
NUMBER = {2},
PAGES = {173--185},
}
-
M. Flammini and S. Pérennes.
Lower bounds on systolic gossip.
Information and Computation,
196(2):71--94,
2005.
@article{FlPe05,
AUTHOR = {Flammini, M. and P\'erennes, S.},
TITLE = {Lower bounds on systolic gossip},
JOURNAL = {Information and Computation},
VOLUME = {196},
YEAR = {2005},
NUMBER = {2},
PAGES = {71--94},
ISSN = {0890-5401},
}
-
L. Liquori and S. Ronchi Della Rocca.
Towards an Intersection Typed System it à la Church.
ITRS: Workshop on Intersection Types and Related Systems. Electr. Notes Theor. Comput. Sci.,
136:43--56,
2005.
[POSTSCRIPT
]
@article{LiRo05,
author = {L. Liquori and S. Ronchi Della Rocca},
title = {Towards an Intersection Typed System {\it \`a la} {C}hurch},
journal = {ITRS: Workshop on Intersection Types and Related Systems. Electr. Notes Theor. Comput. Sci.},
volume = {136},
year = {2005},
pages = {43--56},
POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/itrs-04.ps.gz}
}
-
L. Liquori and B. Wack.
The Polymorphic Rewriting-calculus: [Type Checking vs. Type Inference].
WRLA: International Workshop on Rewriting Logic and its Applications. Electr. Notes Theor. Comput. Sci.,
117:89--111,
2005.
[POSTSCRIPT
]
@article{LiWa05,
author = {L. Liquori and B. Wack},
title = {The Polymorphic Rewriting-calculus: [Type Checking vs. Type Inference]},
journal = {WRLA: International Workshop on Rewriting Logic and its Applications. Electr. Notes Theor. Comput. Sci.},
volume = {117},
year = {2005},
pages = {89--111},
POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/wrla-04.ps.gz}
}
-
B. Reed and B. Sudakov.
List colouring when the chromatic number is close to the order of the graph.
Combinatorica,
25(1):117--123,
2005.
@article {MR2109199,
AUTHOR = {Reed, B. and Sudakov, B.},
TITLE = {List colouring when the chromatic number is close to the order of the graph},
JOURNAL = {Combinatorica},
VOLUME = {25},
YEAR = {2005},
NUMBER = {1},
PAGES = {117--123},
}
-
L. Addario-Berry,
K. Dalal,
and B. Reed.
Degree constrained subgraphs.
In Proceedings of GRACO2005,
volume 19 of Electron. Notes Discrete Math.,
Amsterdam,
pages 257--263 (electronic),
2005.
Elsevier.
@inproceedings {MR2173795,
AUTHOR = {Addario-Berry, L. and Dalal, K. and Reed, B.},
TITLE = {Degree constrained subgraphs},
BOOKTITLE = {Proceedings of GRACO2005},
SERIES = {Electron. Notes Discrete Math.},
VOLUME = {19},
PAGES = {257--263 (electronic)},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2005},
}
-
S. Alouf,
E. Altman,
J. Galtier,
J.-F. Lalande,
and C. Touati.
Quasi-optimal bandwidth allocation for multi-spot MFTDMA satellites.
In IEEE INFOCOM 2005,
Miami, FL,
pages 71--94,
March 2005.
[WWW
] [PDF
] [POSTSCRIPT
]
@Inproceedings{AAG+05,
author = {S. Alouf and E. Altman and J. Galtier and J.-F. Lalande and C. Touati},
title = {Quasi-optimal bandwidth allocation for multi-spot {MFTDMA} satellites},
booktitle = {{IEEE} {INFOCOM} 2005},
year = {2005},
address = {Miami, FL},
month = {March},
pages={71--94},
POSTSCRIPT={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Francois.Lalande/articles/quasi-optimal_bandwidth_allocation_for_multi-spot_mftdma_satellites.ps.gz},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Francois.Lalande/articles/quasi-optimal_bandwidth_allocation_for_multi-spot_mftdma_satellites.pdf},
URL={http://www.ieee-infocom.org/2005/index.htm},
}
-
J-C. Bermond,
L. Braud,
and D. Coudert.
Traffic Grooming on the Path.
In 12th International Colloquium on Structural Information and Communication Complexity -- SIROCCO,
Le Mont Saint-Michel, France,
pages 34-48,
May 24-26 2005.
LNCS 3499.
[PDF
] [POSTSCRIPT
]
| Abstract: |
|
In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most $1/C$ of the bandwidth of the wavelength, we will say that the grooming factor is $C$. That means that on a given edge of the network we can groom (group) at most $C$ requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexer (shortly ADM) used in the network (related to the cost of the nodes).Here we consider the case where the network is a path on $N$ nodes, $P_N$. Thus the routing is unique. For a given grooming factor $C$ minimizing the number of wavelengths is an easy problem, well known and related to the load problem.But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where $C=2$ and where we have a static uniform all-to-all traffic (requests being all pairs of vertices). |
@INPROCEEDINGS{BBC05,
author = {J-C. Bermond and L. Braud and D. Coudert},
title = {Traffic Grooming on the Path},
booktitle = {12th International Colloquium on Structural Information and Communication Complexity -- SIROCCO},
year = {2005},
pages = {34-48},
address = {Le Mont Saint-Michel, France},
month = {May 24-26},
publisher = {LNCS 3499},
abstract = {In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most $1/C$ of the bandwidth of the wavelength, we will say that the grooming factor is $C$. That means that on a given edge of the network we can groom (group) at most $C$ requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexer (shortly ADM) used in the network (related to the cost of the nodes).Here we consider the case where the network is a path on $N$ nodes, $P_N$. Thus the routing is unique. For a given grooming factor $C$ minimizing the number of wavelengths is an easy problem, well known and related to the load problem.But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where $C=2$ and where we have a static uniform all-to-all traffic (requests being all pairs of vertices).},
optnote = {accepted},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BBC-Sirocco05.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BBC-Sirocco05.ps.gz}
}
-
J-C. Bermond and J. Peters.
Efficient Gathering in Radio Grids with Interference.
In Septièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05),
Presqu'île de Giens,
pages 103--106,
May 2005.
[PDF
]
@InProceedings{BePe05,
author = {J-C. Bermond and J. Peters},
title={Efficient Gathering in Radio Grids with Interference},
booktitle={Septi\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'05)},
year={2005},
address={Presqu'\^ile de Giens},
month={May},
pages={103--106},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BePe05.pdf},
}
-
C. Chaudet,
E. Fleury,
I. Guérin-Lassous,
H. Rivano,
and M.-E. Voge.
Surveillance passive dans l'Internet.
In Septièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05),
Presqu'île de Giens,
pages 121--124,
May 2005.
[WWW
] [PDF
]
| Abstract: |
|
Afin d'obtenir les informations nécessaires à une bonne gestion des ressources de leur réseau, les opérateurs placent des sondes passives sur les liens de leurs points de présence. Dans cet article, nous donnons des écritures en programmes linéaires mixtes des problèmes de placement de sondes simples ou avec échantillonnage, et donnons une stratégie pour la maintenance de la surveillance partielle de trafics dynamiques dans un point de présence. Ces formulations améliorent les résultats de deux articles récents de la littérature. |
@INPROCEEDINGS{CFGR+05,
author = {C. Chaudet and E. Fleury and I. Guérin-Lassous and H. Rivano and M.-E. Voge},
title = {Surveillance passive dans l'Internet},
booktitle = {Septièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05)},
year = {2005},
pages = {121--124},
address = {Presqu'île de Giens},
month = {May},
abstract = {Afin d'obtenir les informations nécessaires à une bonne gestion des ressources de leur réseau, les opérateurs placent des sondes passives sur les liens de leurs points de présence. Dans cet article, nous donnons des écritures en programmes linéaires mixtes des problèmes de placement de sondes simples ou avec échantillonnage, et donnons une stratégie pour la maintenance de la surveillance partielle de trafics dynamiques dans un point de présence. Ces formulations améliorent les résultats de deux articles récents de la littérature.},
pdf = {http://www-sop.inria.fr/mascotte/Algotel2005/Actes/26.pdf},
url = {http://www-sop.inria.fr/mascotte/Algotel2005/}
}
-
C. Chaudet,
E. Fleury,
I. Guérin-Lassous,
H. Rivano,
and M.-E. Voge.
Optimal positioning of active and passive monitoring devices.
In CoNEXT 2005,
Toulouse, France,
October 2005.
[WWW
] [PDF
]
| Abstract: |
|
Network measurement is essential for assessing performance issues, identifying and locating problems. Two common strategies are the passive approach that attaches specific devices to links in order to monitor the traffic that passes through the network and the active approach that generates explicit control packets in the network for measurements. One of the key issues in this domain is to minimize the overhead in terms of hardware, software, maintenance cost and additional traffic. In this paper, we study the problem of assigning tap devices for passive monitoring and beacons for active monitoring. Minimizing the number of devices and finding optimal strategic locations is a key issue, mandatory for deploying scalable monitoring platforms. In this article, we present a combinatorial view of the problem from which we derive complexity and approximability results, as well as efficient and versatile Mixed Integer Programming (MIP) formulations. |
@INPROCEEDINGS{CFGR+05b,
author = {C. Chaudet and E. Fleury and I. Guérin-Lassous and H. Rivano and M.-E. Voge},
title = {Optimal positioning of active and passive monitoring devices},
booktitle = {CoNEXT 2005},
year = {2005},
address = {Toulouse, France},
month = {October},
abstract = {Network measurement is essential for assessing performance issues, identifying and locating problems. Two common strategies are the passive approach that attaches specific devices to links in order to monitor the traffic that passes through the network and the active approach that generates explicit control packets in the network for measurements. One of the key issues in this domain is to minimize the overhead in terms of hardware, software, maintenance cost and additional traffic. In this paper, we study the problem of assigning tap devices for passive monitoring and beacons for active monitoring. Minimizing the number of devices and finding optimal strategic locations is a key issue, mandatory for deploying scalable monitoring platforms. In this article, we present a combinatorial view of the problem from which we derive complexity and approximability results, as well as efficient and versatile Mixed Integer Programming (MIP) formulations.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/cfgr05b.pdf},
url = {http://dmi.ensica.fr/conext/}
}
-
D. Coudert,
S. Perennes,
Q-C. Pham,
and J-S. Sereni.
Rerouting requests in WDM networks.
In AlgoTel'05,
Presqu'île de Giens, France,
pages 17-20,
mai 2005.
[PDF
]
| Abstract: |
|
We model a problem related to routing reconfiguration in WDM networks. We establish some similarities and differences with two other known problems: the pathwidth and the pursuit problem. We then present a distributed linear-time algorithm to solve the problem on trees. Last we give the solutions for some classes of graphs, in particular complete $d$-ary trees and grids. |
@INPROCEEDINGS{CPPS05,
author = {D. Coudert and S. Perennes and Q-C. Pham and J-S. Sereni},
title = {Rerouting requests in WDM networks},
booktitle = {AlgoTel'05},
year = {2005},
pages = {17-20},
address = {Presqu'île de Giens, France},
month = mai,
abstract = {We model a problem related to routing reconfiguration in WDM networks. We establish some similarities and differences with two other known problems: the pathwidth and the pursuit problem. We then present a distributed linear-time algorithm to solve the problem on trees. Last we give the solutions for some classes of graphs, in particular complete $d$-ary trees and grids.},
optpostscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCLR-AlgoTel03.ps.gz},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CPPS-AlgoTel05.pdf}
}
-
S. Fiorini,
N. Hardy,
B. Reed,
and A. Vetta.
Approximate min-max relations for odd cycles in planar graphs.
In Integer programming and combinatorial optimization,
volume 3509 of Lecture Notes in Comput. Sci.,
Berlin,
pages 35--50,
2005.
Springer.
@inproceedings{MR2210011,
AUTHOR = {Fiorini, S. and Hardy, N. and Reed, B. and Vetta, A.},
TITLE = {Approximate min-max relations for odd cycles in planar graphs},
BOOKTITLE = {Integer programming and combinatorial optimization},
SERIES = {Lecture Notes in Comput. Sci.},
VOLUME = {3509},
PAGES = {35--50},
PUBLISHER = {Springer},
ADDRESS = {Berlin},
YEAR = {2005},
}
-
S. Fiorini,
N. Hardy,
B. Reed,
and A. Vetta.
Planar graph bipartization in linear time.
In Proceedings of GRACO2005,
volume 19 of Electron. Notes Discrete Math.,
Amsterdam,
pages 265--271 (electronic),
2005.
Elsevier.
@inproceedings {MR2173796,
AUTHOR = {Fiorini, S. and Hardy, N. and Reed, B. and Vetta, A.},
TITLE = {Planar graph bipartization in linear time},
BOOKTITLE = {Proceedings of GRACO2005},
SERIES = {Electron. Notes Discrete Math.},
VOLUME = {19},
PAGES = {265--271 (electronic)},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2005},
}
-
M. Flammini,
L. Moscardelli,
A. Navarra,
and S. Pérennes.
Asymptotically Optimal Solutions for Small World Graphs.
In Proceedings of the 19th International Symposium on Distributed Computing, (DISC 2005),
volume 3724 of Lecture Notes in Computer Science,
pages 414--428,
September 2005.
Springer Verlag.
[WWW
]
@InProceedings{FMNP05,
author={M. Flammini and L. Moscardelli and A. Navarra and S. P\'erennes},
title={Asymptotically Optimal Solutions for Small World Graphs},
booktitle={Proceedings of the 19th International Symposium on Distributed Computing, (DISC 2005)},
series={Lecture Notes in Computer Science},
year={2005},
month={September},
publisher={Springer Verlag},
volume={3724},
pages={414--428},
URL={http://www.mimuw.edu.pl/~disc2005/},
}
-
M. Flammini,
A. Navarra,
and S. Pérennes.
The Real approximation factor of the MST heuristic for the Minimum Energy Broadcasting.
In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms, (WEA 2005),
volume 3503 of Lecture Notes in Computer Science,
pages 22--31,
May 2005.
Springer Verlag.
[WWW
]
@InProceedings{FNP05,
author={M. Flammini and A. Navarra and S. P\'erennes},
title={The "Real" approximation factor of the MST heuristic for the Minimum Energy Broadcasting},
booktitle={Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms, (WEA 2005)},
series={Lecture Notes in Computer Science},
year={2005},
month={May},
publisher={Springer Verlag},
volume={3503},
pages={22--31},
URL={http://ru1.cti.gr/wea05/},
}
-
F. V. Fomin,
P. Fraigniaud,
and N. Nisse.
Nondeterministic Graph Searching: From Pathwidth to Treewidth.
In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS),
pages 364-375,
2005.
[WWW
] [PDF
]
| Abstract: |
|
We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers. |
@inproceedings{FFN05,
author = {F. V. Fomin and P. Fraigniaud and N. Nisse},
title = {Nondeterministic Graph Searching: From Pathwidth to Treewidth},
booktitle = {Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS)},
year = {2005},
pages = {364-375},
abstract = {We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.},
url = {http://www.informatik.uni-trier.de/~ley/db/conf/mfcs/mfcs2005.shtml},
pdf={http://www-sop.inria.fr/members/Nicolas.Nisse/publications/MFCS2005.ps}
}
-
P. Fraigniaud and N. Nisse.
Stratégies d'encerclement connexes dans un réseau.
In 7èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 13-16,
2005.
[WWW
] [PDF
]
| Abstract: |
|
Le probl\`eme de l'encerclement dans les r\'eseaux a \'et\'e introduit par Parson (1976)~: \'etant donn\'e un r\'eseau "contamin\'e" (par exemple dans lequel un intrus s'est introduit), l'\emph{encerclement} du r\'eseau est le nombre minimum d'agents n\'ecessaires pour "nettoyer" le r\'eseau (c'est-\`a-dire capturer l'intrus). Une strat\'egie d'encerclement est dite connexe si \`a chaque \'etape de la strat\'egie, l'ensemble des liens nettoy\'es induit un sous-r\'eseau connexe. Les strat\'egies d'encerclement connexes sont essentielles si l'on souhaite assurer des communications s\^ures entre les agents. Dans le cas des r\'eseaux en arbres, Barri\`ere {\sl et al.} (2002, 2003) ont prouv\'e que le rapport entre l'encerclement connexe et l'encerclement est major\'e par 2, et que cette borne est optimale. Dans cet article, nous donnons une borne pour ce rapport dans le cas des r\'eseaux arbitraires. Pour cela nous utilisons une notion cruciale de th\'eorie des graphes~: la largeur arborescente. L'\'egalit\'e entre la largeur arborescente connexe d'un graphe et sa largeur arborescente d\'ecoule du th\'eor\`eme de Parra et Scheffler (1995). Nous donnons ici une preuve constructive de cette \'egalit\'e. Plus pr\'ecisemment, nous proposons un algorithme qui \'etant donn\'es un graphe $G$ de $n$ sommets et une d\'ecomposition arborescente de largeur $k$ de $G$, calcule en temps $O(n~k^3)$ une d\'ecomposition arborescente connexe de largeur $\leq k$ de $G$. Une cons\'equence importante de notre r\'esultat est qu'il permet de borner par $\lceil\log{n}\rceil+1$ le rapport entre encerclement connexe et encerclement d'un r\'eseau de $n$ n{\oe}uds. |
@InProceedings{FrNi05,
sorte = "conf-nat",
author = {P. Fraigniaud and N. Nisse},
title = {Strat\'egies d'encerclement connexes dans un r\'eseau},
booktitle = {7\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},
year = {2005},
pages = {13-16},
url = {http://www-sop.inria.fr/mascotte/Algotel2005/},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Algotel2005.ps},
abstract = {Le probl\`eme de l'encerclement dans les r\'eseaux a \'et\'e introduit par Parson (1976)~: \'etant donn\'e un r\'eseau "contamin\'e" (par exemple dans lequel un intrus s'est introduit), l'\emph{encerclement} du r\'eseau est le nombre minimum d'agents n\'ecessaires pour "nettoyer" le r\'eseau (c'est-\`a-dire capturer l'intrus). Une strat\'egie d'encerclement est dite connexe si \`a chaque \'etape de la strat\'egie, l'ensemble des liens nettoy\'es induit un sous-r\'eseau connexe. Les strat\'egies d'encerclement connexes sont essentielles si l'on souhaite assurer des communications s\^ures entre les agents. Dans le cas des r\'eseaux en arbres, Barri\`ere {\sl et al.} (2002, 2003) ont prouv\'e que le rapport entre l'encerclement connexe et l'encerclement est major\'e par 2, et que cette borne est optimale. Dans cet article, nous donnons une borne pour ce rapport dans le cas des r\'eseaux arbitraires. Pour cela nous utilisons une notion cruciale de th\'eorie des graphes~: la largeur arborescente. L'\'egalit\'e entre la largeur arborescente connexe d'un graphe et sa largeur arborescente d\'ecoule du th\'eor\`eme de Parra et Scheffler (1995). Nous donnons ici une preuve constructive de cette \'egalit\'e. Plus pr\'ecisemment, nous proposons un algorithme qui \'etant donn\'es un graphe $G$ de $n$ sommets et une d\'ecomposition arborescente de largeur $k$ de $G$, calcule en temps $O(n~k^3)$ une d\'ecomposition arborescente connexe de largeur $\leq k$ de $G$. Une cons\'equence importante de notre r\'esultat est qu'il permet de borner par $\lceil\log{n}\rceil+1$ le rapport entre encerclement connexe et encerclement d'un r\'eseau de $n$ n{\oe}uds.},
}
-
J. Galtier,
A. Laugier,
and P. Pons.
Algorithms to evaluate the reliability of a network.
In The 5th International Workshop on Design of Reliable Communication Networks,
pages 93--100,
2005.
[WWW
] [PDF
]
@InProceedings{GLP05,
author = {J. Galtier and A. Laugier and P. Pons},
title = {Algorithms to evaluate the reliability of a network},
booktitle = {The 5th International Workshop on Design of Reliable Communication Networks},
year = {2005},
pages= {93--100},
URL={http://drcn2005.telecomitalialab.com/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GLP05.pdf},
}
-
F. Giroire.
Order statistics and estimating cardinalities of massive data sets.
In Conrado MartÃnez, editor,
2005 International Conference on Analysis of Algorithms,
volume AD of DMTCS Proceedings,
pages 157-166,
2005.
Discrete Mathematics and Theoretical Computer Science.
[WWW
] [PDF
]
| Abstract: |
|
We introduce a new class of algorithms to estimate the cardinality of very large multisets using constant memory and doi ng only one pass on the data. It is based on order statistics rather that on bit patterns in binary representations of numbers. We analyse three families of estimators. They attain a standard error of $\frac 1{\sqrt M}$ using $M$ unit s of storage, which places them in the same class as the best known algorithms so far. They have a very simple internal loop, which g ives them an advantage in term of processing speed. The algorithms are validated on internet traffic traces. |
@inproceedings{Gir05,
author = {F. Giroire},
title = {Order statistics and estimating cardinalities of massive data sets},
booktitle = {2005 International Conference on Analysis of Algorithms},
year = {2005},
editor = {Conrado MartÃnez},
publisher = {Discrete Mathematics and Theoretical Computer Science},
volume = {AD},
series = {DMTCS Proceedings},
pages = {157-166},
url = {http://www.dmtcs.org/proceedings/html/dmAD0115.abs.shtml},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/Gir05.pdf},
abstract = {We introduce a new class of algorithms to estimate the cardinality of very large multisets using constant memory and doi ng only one pass on the data. It is based on order statistics rather that on bit patterns in binary representations of numbers. We analyse three families of estimators. They attain a standard error of $\frac 1{\sqrt M}$ using $M$ unit s of storage, which places them in the same class as the best known algorithms so far. They have a very simple internal loop, which g ives them an advantage in term of processing speed. The algorithms are validated on internet traffic traces.},
}
-
C. Gomes and G. Robson Mateus.
Low-Cost Design Approach to WDM Mesh Networks.
In 4th International Conference on Networking (ICN),
pages 60-67,
2005.
@INPROCEEDINGS{GM05,
AUTHOR = {C. Gomes and G. {Robson Mateus}},
TITLE = {Low-Cost Design Approach to WDM Mesh Networks},
BOOKTITLE = {4th International Conference on Networking (ICN)},
SCHOOL = {Reunion Island},
YEAR = {2005},
PAGES = {60-67},
}
-
A. Guitton and J. Moulierac.
Scalable Tree Aggregation for Multicast.
In 8th International Conference on Telecommunications (ConTEL),
pages 129--134,
June 2005.
Note: Best Student Paper Award.
[PDF
]
| Abstract: |
|
IP multicast is not widely deployed yet over Internet. This is mainly due to the forwarding entries scalability and control explosion problems. In this paper, we propose an algorithm called STA (Scalable Tree Aggregation) which reduces the number of trees by allowing several groups to be aggregated to the same tree: the less trees, the less forwarding entries and the less control messages to maintain trees. STA performs faster aggregations than previous aggregation algorithms by evaluating fewer trees for each group, while keeping the same performance. We show the scalability and the fastness of STA by extensive simulations and we compare its performance to the previous algorithm. |
@inproceedings{GM05,
author= {A. Guitton and J. Moulierac},
title= {{S}calable {T}ree {A}ggregation for {M}ulticast},
booktitle= {8th International Conference on Telecommunications ({ConTEL})},
year= {2005},
month= {June},
pages= {129--134},
note= {Best Student Paper Award},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/guitton05scalable.pdf},
ABSTRACT={IP multicast is not widely deployed yet over Internet. This is mainly due to the forwarding entries scalability and control explosion problems. In this paper, we propose an algorithm called STA (Scalable Tree Aggregation) which reduces the number of trees by allowing several groups to be aggregated to the same tree: the less trees, the less forwarding entries and the less control messages to maintain trees. STA performs faster aggregations than previous aggregation algorithms by evaluating fewer trees for each group, while keeping the same performance. We show the scalability and the fastness of STA by extensive simulations and we compare its performance to the previous algorithm.}
}
-
F. Havet,
R. J. Kang,
and J.-S. Sereni.
Improper colouring of unit disk graphs.
In Proceedings of the 7th International Conference on Graph Theory (ICGT'05),
volume 22 of Electronic Notes in Discrete Mathematics,
pages 123--128,
September 2005.
Elsevier.
[WWW
] [PDF
]
@InProceedings{HKS05,
author ={F. Havet and R. J. Kang and J.-S. Sereni},
booktitle={Proceedings of the 7th International Conference on Graph Theory (ICGT'05)},
month={September},
pages={123--128},
publisher={Elsevier},
series={Electronic Notes in Discrete Mathematics},
title={Improper colouring of unit disk graphs},
year={2005},
volume={22},
PDF={http://kam.mff.cuni.cz/~sereni/Articles/HKS05.pdf},
URL={http://www-sop.inria.fr/mascotte/ICGT05/},
}
-
F. Havet and J.-S. Sereni.
Channel assignment and improper choosability of graphs.
In Proceedings of the 31st Workshop on Graph-Theoretic Concepts in Computer Science (WG'05),
volume 3787 of Lecture Notes in Computer Science,
pages 81--90,
June 2005.
Springer Verlag.
[WWW
] [PDF
]
@InProceedings{HaSe05,
author = {F. Havet and J.-S. Sereni},
booktitle = {Proceedings of the 31st Workshop on Graph-Theoretic Concepts in Computer Science (WG'05)},
month = {June},
pages = {81--90},
publisher = {Springer Verlag},
series = {Lecture Notes in Computer Science},
title = {Channel assignment and improper choosability of graphs},
volume = {3787},
year = {2005},
PDF={http://kam.mff.cuni.cz/~sereni/Articles/HaSe05.pdf},
URL={http://lita.sciences.univ-metz.fr/~wg2005/},
}
-
G. Huiban and G. Robson Mateus.
A MILP model for the reconfiguration problem in multi-fiber WDM networks.
In SBRC Simpósio Brasileiro de Redes de Computadores,
May 2005.
[WWW
] [PDF
]
| Abstract: |
|
We address the reconfiguration problem in multi-fiber WDM networks. It consists of finding out which adaptations should be made to the virtual topology and the routing when the traffic evolves. We propose a Mixed Integer Linear Programming (MILP) model solving the problem for different objective functions. We tried to make a concise model in relations with the number of variables and restrictions, to reduce the memory occupation during the optimization process. We also add some cuts to the model. We make some experiments with this model and compare the results obtained with a simple greedy algorithm and with an algorithm from the literature |
@InProceedings{HuRo05b,
author = {G. Huiban and G. {Robson Mateus}},
title = {A {MILP} model for the reconfiguration problem in multi-fiber {WDM} networks},
booktitle = {SBRC Simpósio Brasileiro de Redes de Computadores},
year = {2005},
month = {May},
OPTnote = {ISBN: 85-7669-021-7},
url = {http://www.sbrc2005.ufc.br/},
PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/HuRo05b.pdf},
abstract = {We address the reconfiguration problem in multi-fiber WDM networks. It consists of finding out which adaptations should be made to the virtual topology and the routing when the traffic evolves. We propose a Mixed Integer Linear Programming (MILP) model solving the problem for different objective functions. We tried to make a concise model in relations with the number of variables and restrictions, to reduce the memory occupation during the optimization process. We also add some cuts to the model. We make some experiments with this model and compare the results obtained with a simple greedy algorithm and with an algorithm from the literature}
}
-
G. Huiban and G. Robson Mateus.
A multiobjective approach of the virtual topology design and routing problem in WDM networks.
In ICT International Conference on Telecommunications,
May 2005.
IEEE Computer Society Press.
[WWW
] [PDF
]
| Abstract: |
|
We deal with the classical virtual topology design and routing problems in optical WDM (Wavelength Division Multiplexing) networks. We propose a multiobjective based algorithm to compute the Pareto set of solutions of the problem. Although the computational cost may be high, such approach permits the decision maker to have a better perception of the gain and the loss of choosing any given solution. We describe briefly the treated problem, and the MILP (Mixed Integer Linear Programing) model used. We present the method applied to obtain the Pareto set. We report some computational results and they fully justify the interest of carrying out a multiobjective study. |
@InProceedings{HuRo05a,
author = {G. Huiban and G. {Robson Mateus}},
title = {A multiobjective approach of the virtual topology design and routing problem in {WDM} networks},
booktitle = {ICT International Conference on Telecommunications},
year = {2005},
month = {May},
publisher = {IEEE Computer Society Press},
OPTnote = {ISBN: 0-9584901-3-9},
url = {http://www.ee.up.ac.za/~ieee/ict2005/},
PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/HuRo05a.pdf},
abstract = {We deal with the classical virtual topology design and routing problems in optical WDM (Wavelength Division Multiplexing) networks. We propose a multiobjective based algorithm to compute the Pareto set of solutions of the problem. Although the computational cost may be high, such approach permits the decision maker to have a better perception of the gain and the loss of choosing any given solution. We describe briefly the treated problem, and the MILP (Mixed Integer Linear Programing) model used. We present the method applied to obtain the Pareto set. We report some computational results and they fully justify the interest of carrying out a multiobjective study.}
}
-
R. J. Kang,
T. Müller,
and J.-S. Sereni.
Improper colouring of (random) unit disk graphs.
In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2005),
Discrete Mathematics and Theoretical Computer Science,
pages 193--198,
September 2005.
[WWW
] [PDF
]
@InProceedings{KMS05a,
author={R. J. Kang and T. M\"uller and J.-S. Sereni},
booktitle={Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2005)},
month={September},
pages={193--198},
series={Discrete Mathematics and Theoretical Computer Science},
title={Improper colouring of (random) unit disk graphs},
year={2005},
URL={http://www.math.tu-berlin.de/EuroComb05/},
PDF={http://kam.mff.cuni.cz/~sereni/Articles/KMS05a.pdf},
}
-
R. Klasing,
Z. Lotker,
A. Navarra,
and S. Pérennes.
From Balls and Bins to Points and Vertices.
In Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005),
volume 3827 of Lecture Notes in Computer Science,
pages 757--766,
December 2005.
Springer Verlag.
[WWW
] [PDF
]
@InProceedings{KLNP05,
author={R. Klasing and Z. Lotker and A. Navarra and S. P\'erennes},
title={From Balls and Bins to Points and Vertices},
booktitle={Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005)},
series={Lecture Notes in Computer Science},
publisher={Springer Verlag},
volume={3827},
month={December},
year={2005},
URL={http://www.cs.cityu.edu.hk/~isaac2005/},
pages={757--766},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/KLNP05.pdf},
}
-
R. Klasing,
E. Markou,
T. Radzik,
and F. Sarracco.
Hardness and approximation results for black hole search in arbitrary graphs.
In Proceedings of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO 2005),
volume 3499 of Lecture Notes in Computer Science,
pages 200--215,
May 2005.
Springer Verlag.
[WWW
]
@InProceedings{KMRS05a,
author={R. Klasing and E. Markou and T. Radzik and F. Sarracco},
title={Hardness and approximation results for black hole search in arbitrary graphs},
booktitle={Proceedings of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO 2005)},
series={Lecture Notes in Computer Science},
publisher={Springer Verlag},
volume={3499},
month={May},
year={2005},
URL={http://sirocco.informatika.sk/},
PDF={},
pages={200--215},
}
-
R. Klasing,
E. Markou,
T. Radzik,
and F. Sarracco.
Approximation bounds for Black Hole Search problems.
In Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS 2005),
volume 3974 of Lecture Notes in Computer Science,
December 2005.
Springer Verlag.
[WWW
]
@InProceedings{KMRS05b,
author={R. Klasing and E. Markou and T. Radzik and F. Sarracco},
title={Approximation bounds for Black Hole Search problems},
booktitle={Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS 2005)},
series={Lecture Notes in Computer Science},
publisher={Springer Verlag},
volume={3974},
month={December},
year={2005},
URL={http://www.di.unipi.it/OPODIS2005/},
}
-
J.-F. Lalande,
M. Syska,
and Y. Verhoeven.
Arrondi aléatoire et protection des réseaux WDM.
In Ecole Polytechnique de l'Université de Tours, editor,
ROADEF,
number 6,
Tours, France,
pages 241--242,
2005.
[WWW
] [PDF
] [POSTSCRIPT
]
@InProceedings{LSV05,
author = {J.-F. Lalande and M. Syska and Y. Verhoeven},
title = {Arrondi aléatoire et protection des réseaux {WDM}},
booktitle = {ROADEF},
OPTcrossref = {},
OPTkey = {},
pages = {241--242},
year = {2005},
editor = {Ecole Polytechnique de l'Université de Tours},
OPTvolume = {},
number = {6},
address = {Tours, France},
OPTmonth = {Février},
OPTorganization = {},
OPTpublisher = {},
OPTnote = {},
OPTannote = {},
POSTSCRIPT={ftp://ftp-sop.inria.fr/mascotte/Jean-Francois.Lalande/articles/arrondi_aleatoire_et_protection_des_reseaux_wdm.ps.gz},
PDF={ftp://ftp-sop.inria.fr/mascotte/Jean-Francois.Lalande/articles/arrondi_aleatoire_et_protection_des_reseaux_wdm.pdf},
URL={http://www.ocea.li.univ-tours.fr/roadef05/},
}
-
A. Laugier and S. Raymond.
Recherche de graphes expansifs dans le graphe du Web.
In Roadef,
2005.
[WWW
]
@InProceedings{LaRa05,
author = {A. Laugier and S. Raymond},
title = {Recherche de graphes expansifs dans le graphe du Web},
booktitle = {Roadef},
year = {2005},
URL={http://www.ocea.li.univ-tours.fr/roadef05/},
}
-
Z. Li and B. Reed.
Heap building bounds.
In Algorithms and data structures,
volume 3608 of Lecture Notes in Comput. Sci.,
Berlin,
pages 14--23,
2005.
Springer.
@inproceedings{MR2200308,
AUTHOR = {Li, Z. and Reed, B.},
TITLE = {Heap building bounds},
BOOKTITLE = {Algorithms and data structures},
SERIES = {Lecture Notes in Comput. Sci.},
VOLUME = {3608},
PAGES = {14--23},
PUBLISHER = {Springer},
ADDRESS = {Berlin},
YEAR = {2005},
}
-
C. Meagher and B. Reed.
Fractionally total colouring $G\sb {n,p}$.
In Proceedings of GRACO2005,
volume 19 of Electron. Notes Discrete Math.,
Amsterdam,
pages 297--303 (electronic),
2005.
Elsevier.
@inproceedings {MR2173800,
AUTHOR = {Meagher, C. and Reed, B.},
TITLE = {Fractionally total colouring {$G\sb {n,p}$}},
BOOKTITLE = {Proceedings of GRACO2005},
SERIES = {Electron. Notes Discrete Math.},
VOLUME = {19},
PAGES = {297--303 (electronic)},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2005},
}
-
J. Moulierac and A. Guitton.
QoS Scalable Tree Aggregation.
In IFIP Networking,
number 3462 of LNCS,
pages 1405--1408,
May 2005.
[PDF
]
| Abstract: |
|
Some of the main reasons which prevents the deployment of IP multicast are forwarding state scalability and control explosion prob- lems. In this paper, we propose an algorithm called Q-STA (QoS Scalable Tree Aggregation) which reduces the number of forwarding states by al- lowing several groups to share the same tree. Q-STA accepts groups only if there is enough available bandwidth. Q-STA accepts much more groups and performs faster aggregations than previous algorithms. |
@inproceedings{MG05b,
author= {J. Moulierac and A. Guitton},
title= {{Q}o{S} {S}calable {T}ree {A}ggregation},
booktitle= {IFIP Networking},
year= {2005},
pages = {1405--1408},
number= {3462},
series= {LNCS},
month= {May},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/moulierac05qos.pdf},
ABSTRACT={Some of the main reasons which prevents the deployment of IP multicast are forwarding state scalability and control explosion prob- lems. In this paper, we propose an algorithm called Q-STA (QoS Scalable Tree Aggregation) which reduces the number of forwarding states by al- lowing several groups to share the same tree. Q-STA accepts groups only if there is enough available bandwidth. Q-STA accepts much more groups and performs faster aggregations than previous algorithms.}
}
-
S. Petat and M.-E. Voge.
Groupage sur un chemin orienté.
In Septièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05),
Presqu'île de Giens,
pages 21--24,
May 2005.
[PDF
]
@InProceedings{PeVo05,
author = {S. Petat and M.-E. Voge},
title={Groupage sur un chemin orient\'e},
booktitle={Septi\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'05)},
year={2005},
address={Presqu'\^ile de Giens},
month={May},
pages={21--24},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/PeVo05.pdf},
}
-
H. Rivano,
F. Théoleyre,
and F. Valois.
Influence de l'auto-organisation sur la capacité des réseaux ad hoc.
In Septièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05),
Presqu'île de Giens,
pages 53--56,
May 2005.
[WWW
] [PDF
]
| Abstract: |
|
Les réseaux ad hoc tirent parti de la collaboration des noeuds pour acheminer des informations. Si de nombreuses approches ont vu le jour, la problématique du routage demeure un point crucial. Deux approches se détachent : une première résidant dans une vision à plat du réseau et une seconde, plus récente, où le routage repose sur une auto-organisation du réseau. Il s'agit de fournir une solution d'organisation afin de tirer parti des propriétés structurelles et d'améliorer des services tels que le routage. Les performances obtenues sont intéressantes bien que les auto-organisations réduisent le nombre de liens radio effectivement utilisés. Nous proposons donc ici de quantifier les changements, en terme de bande passante disponible, entre un réseau à plat et un réseau structuré. |
@INPROCEEDINGS{RTV05,
author = {H. Rivano and F. Théoleyre and F. Valois},
title = {Influence de l'auto-organisation sur la capacité des réseaux ad hoc},
booktitle = {Septièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05)},
year = {2005},
pages = {53--56},
address = {Presqu'île de Giens},
month = {May},
abstract = {Les réseaux ad hoc tirent parti de la collaboration des noeuds pour acheminer des informations. Si de nombreuses approches ont vu le jour, la problématique du routage demeure un point crucial. Deux approches se détachent : une première résidant dans une vision à plat du réseau et une seconde, plus récente, où le routage repose sur une auto-organisation du réseau. Il s'agit de fournir une solution d'organisation afin de tirer parti des propriétés structurelles et d'améliorer des services tels que le routage. Les performances obtenues sont intéressantes bien que les auto-organisations réduisent le nombre de liens radio effectivement utilisés. Nous proposons donc ici de quantifier les changements, en terme de bande passante disponible, entre un réseau à plat et un réseau structuré.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/rtv05.pdf},
url = {http://www-sop.inria.fr/mascotte/Algotel2005/}
}
-
L. Addario-Berry,
F. Havet,
and S. Thomassé.
Paths with two blocks in $n$-chromatic digraphs.
Research report,
INRIA Research Report 5688 and I3S Research Report I3S/RR-2005-27-FR,
2005.
[WWW
] [PDF
] [POSTSCRIPT
]
@TechReport{AHT05,
author = {L. Addario-Berry and F.~Havet and S.~Thomass\'e},
title = {Paths with two blocks in $n$-chromatic digraphs},
institution = {INRIA Research Report 5688 and I3S Research Report I3S/RR-2005-27-FR},
year = {2005},
POSTSCRIPT={ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5688.ps.gz},
PDF={ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5688.pdf},
URL={http://www.inria.fr/rrrt/rr-5688.shtml},
type = {Research report},
}
-
J-C. Bermond,
L. Braud,
and D. Coudert.
Traffic Grooming on the Path.
Technical report,
INRIA Research Report 5645 (.ps.gz) and I3S Research Report I3S/RR-2005-20-FR (.pdf),
2005.
[PDF
] [POSTSCRIPT
]
| Abstract: |
|
In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most $1/C$ of the bandwidth of the wavelength, we will say that the grooming factor is $C$. That means that on a given edge of the network we can groom (group) at most $C$ requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexer (shortly ADM) used in the network (related to the cost of the nodes).Here we consider the case where the network is a path on $N$ nodes, $P_N$. Thus the routing is unique. For a given grooming factor $C$ minimizing the number of wavelengths is an easy problem, well known and related to the load problem.But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where $C=2$ and where we have a static uniform all-to-all traffic (requests being all pairs of vertices). |
@TECHREPORT{BBC05b,
author = {J-C. Bermond and L. Braud and D. Coudert},
title = {Traffic Grooming on the Path},
institution = {INRIA Research Report 5645 (.ps.gz) and I3S Research Report I3S/RR-2005-20-FR (.pdf)},
year = {2005},
abstract = {In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most $1/C$ of the bandwidth of the wavelength, we will say that the grooming factor is $C$. That means that on a given edge of the network we can groom (group) at most $C$ requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexer (shortly ADM) used in the network (related to the cost of the nodes).Here we consider the case where the network is a path on $N$ nodes, $P_N$. Thus the routing is unique. For a given grooming factor $C$ minimizing the number of wavelengths is an easy problem, well known and related to the load problem.But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where $C=2$ and where we have a static uniform all-to-all traffic (requests being all pairs of vertices).},
optnote = {Final version submitted to TCS},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/I3SRR-2005-20-FR.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/RR-5645.ps.gz}
}
-
J-C. Bermond,
M. Cosnard,
D. Coudert,
and S. Perennes.
Optimal Solution of the Maximum All Request Path Grooming Problem.
Technical report,
INRIA Research Report 5627 (.ps.gz) and I3S Research Report I3S/RR-2005-18-FR (.pdf),
2005.
[PDF
] [POSTSCRIPT
]
| Abstract: |
|
We give an optimal solution to the Maximum All Request Path Grooming (MARPG) problem motivated by a traffic grooming application. The MARPG problem consists in finding the maximum number of connections which can be established in a path of size $N$, where each arc has a capacity or bandwidth $C$ (grooming factor). We present a greedy algorithm to solve the problem and an explicit formula for the maximum number of requests that can be groomed. In particular, if $C = s(s 1)/2$ and $N > s(s-1)$, an optimal solution is obtained by taking all the requests of smallest length, that is of length 1 to $s$. However this is not true in general since anomalies can exist. We give a complete analysis and the exact number of such anomalies. |
@TECHREPORT{BCCP05,
author = {J-C. Bermond and M. Cosnard and D. Coudert and S. Perennes},
title = {Optimal Solution of the Maximum All Request Path Grooming Problem},
institution = {INRIA Research Report 5627 (.ps.gz) and I3S Research Report I3S/RR-2005-18-FR (.pdf)},
year = {2005},
abstract = {We give an optimal solution to the Maximum All Request Path Grooming (MARPG) problem motivated by a traffic grooming application. The MARPG problem consists in finding the maximum number of connections which can be established in a path of size $N$, where each arc has a capacity or bandwidth $C$ (grooming factor). We present a greedy algorithm to solve the problem and an explicit formula for the maximum number of requests that can be groomed. In particular, if $C = s(s 1)/2$ and $N > s(s-1)$, an optimal solution is obtained by taking all the requests of smallest length, that is of length 1 to $s$. However this is not true in general since anomalies can exist. We give a complete analysis and the exact number of such anomalies.},
optnote = {Accepted to AICT 06},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/I3SRR-2005-18-FR.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/RR-5627.ps.gz}
}
-
C. Cooper,
R. Klasing,
and M. Zito.
Lower Bounds and Algorithms for Dominating Sets in Web Graphs.
Technical report,
INRIA Research Report RR-5529 and I3S Research Report I3S/RR-2005-09-FR,
2005.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
In this paper we study the size of dominating sets, and their generalizations, in two graph processes which are widely used to model aspects of the world-wide web. In these processes each new vertex connects to the existing graph by a constant number, $m$, of edges. The terminal vertices of these edges are chosen uniformly at random or by preferential attachment depending on the process. We show that almost all such graph processes have minimal dominating sets linear in the size of the graph and give bounds for this size as a function of $m$. We obtain the upper bounds from simple on-line algorithms for dominating sets. The lower bounds are obtained by proving that the lexicographically first set of a given size is the most likely to dominate. |
@TechReport{CKZ05b,
author = {C. Cooper and R. Klasing and M. Zito},
title = {Lower Bounds and Algorithms for Dominating Sets in Web Graphs},
institution = {INRIA Research Report RR-5529 and I3S Research Report I3S/RR-2005-09-FR},
year = {2005},
OPTkey = {},
OPTtype = {},
OPTnumber = {},
OPTaddress = {},
OPTmonth = {},
OPTnote = {},
OPTannote = {},
PDF = {http://www.i3s.unice.fr/~mh/RR/2005/RR-05.09-R.KLASING.pdf},
POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5529.ps.gz},
url = {http://hal.inria.fr/inria-00070478/fr/},
abstract = {In this paper we study the size of dominating sets, and their generalizations, in two graph processes which are widely used to model aspects of the world-wide web. In these processes each new vertex connects to the existing graph by a constant number, $m$, of edges. The terminal vertices of these edges are chosen uniformly at random or by preferential attachment depending on the process. We show that almost all such graph processes have minimal dominating sets linear in the size of the graph and give bounds for this size as a function of $m$. We obtain the upper bounds from simple on-line algorithms for dominating sets. The lower bounds are obtained by proving that the lexicographically first set of a given size is the most likely to dominate.},
}
-
D. Coudert,
P. Datta,
H. Rivano,
and M.-E. Voge.
Minimum Color Problems and Shared Risk Resource Group in Multilayer Networks.
Research Report,
I3S Research Report I3S/RR-2005-37-FR,
2005.
[WWW
] [PDF
]
@TECHREPORT{CDRV05,
author = {D. Coudert and P. Datta and H. Rivano and M.-E. Voge},
title = {Minimum Color Problems and Shared Risk Resource Group in Multilayer Networks},
institution = {I3S Research Report I3S/RR-2005-37-FR},
year = {2005},
type = {Research Report},
pdf = {http://www.i3s.unice.fr/~mh/RR/2005/RR-05.37-M-E.VOGE.pdf},
url = {http://www.i3s.unice.fr/~mh/RR/2005/liste-2005.shtml}
}
-
C. Gomes and H. Rivano.
WDM Mesh Networks with Dynamic Traffic.
Research report,
INRIA Research Report 5713,
2005.
[WWW
]
| Abstract: |
|
This article presents a mathematical model that results in a low-cost network design to satisfy a set of point-to-point demands that arrive and leave the network along of time. It considers the problem of routing working traffic and assigning wavelengths in an all-optical network avoiding if possible that wavelengths assignment changes and flow rerouting. The model allows to know when a reconfiguration/expansion is needed. The model provides a physical network configuration selecting a lowest cost set of components of the network (subnetworks and OXCs) with sufficient capacities to attend the demands and the required wavelengths in all time. |
@TECHREPORT{GoRi05,
author = {C. Gomes and H. Rivano},
title = {WDM Mesh Networks with Dynamic Traffic},
institution = {INRIA Research Report 5713},
year = {2005},
type = {Research report},
abstract = {This article presents a mathematical model that results in a low-cost network design to satisfy a set of point-to-point demands that arrive and leave the network along of time. It considers the problem of routing working traffic and assigning wavelengths in an all-optical network avoiding if possible that wavelengths assignment changes and flow rerouting. The model allows to know when a reconfiguration/expansion is needed. The model provides a physical network configuration selecting a lowest cost set of components of the network (subnetworks and OXCs) with sufficient capacities to attend the demands and the required wavelengths in all time.},
url = {http://hal.inria.fr/inria-00070304}
}
-
F. Havet.
Repartitors, selectors and superselectors.
Research report,
INRIA Research Report 5686,
2005.
[WWW
] [PDF
] [POSTSCRIPT
]
@TechReport{Hav05,
author = {F.~Havet},
title = {Repartitors, selectors and superselectors},
institution = {INRIA Research Report 5686},
year = {2005},
POSTSCRIPT={ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5686.ps.gz},
PDF={ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5686.pdf},
URL={http://www.inria.fr/rrrt/rr-5686.shtml},
type = {Research report},
}
-
G. Huiban and P. Datta.
Virtual topology reconfiguration issues in evolution of WDM optical networks.
Research report 5711,
INRIA,
2005.
[WWW
] [PDF
]
| Abstract: |
|
We consider the reconfiguration problem in multi-fiber WDM optical networks. In a real-time network as the traffic evolves with time: the virtual topology may not remain optimal for the evolving traffic, leading to a degradation of network performance. However, adapting the virtual topology to the changing traffic may lead to service disruption. This optimization problem hence captures the trade-off between network performance and number of reconfigurations applied to the virtual topology. The above problem is solved through a Mixed Integer Linear Programming formulation with a multivariate objective function, that captures both these parameters. However the problem is NP-hard and such an approach is unable to solve large problem instances in a reasonable time. In this paper, we also propose a simulated annealing based heuristic algorithm for solving problems of higher complexity. We compare the performance and the computation time of the MILP model and the heuristic algorithm considering different tests instances. Our results indicate that simulated annealing obtains results within 5\0f the optimal solution, thus making it a viable approach in large scale networks. |
@TechReport{HuDa05,
author = {G. Huiban and P. Datta},
title = {Virtual topology reconfiguration issues in evolution of {WDM} optical networks},
institution = {INRIA},
year = {2005},
type = {Research report},
number = {5711},
pdf = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5711.pdf},
url = {http://www.inria.fr/rrrt/rr-5711.shtml},
abstract = {We consider the reconfiguration problem in multi-fiber WDM optical networks. In a real-time network as the traffic evolves with time: the virtual topology may not remain optimal for the evolving traffic, leading to a degradation of network performance. However, adapting the virtual topology to the changing traffic may lead to service disruption. This optimization problem hence captures the trade-off between network performance and number of reconfigurations applied to the virtual topology. The above problem is solved through a Mixed Integer Linear Programming formulation with a multivariate objective function, that captures both these parameters. However the problem is NP-hard and such an approach is unable to solve large problem instances in a reasonable time. In this paper, we also propose a simulated annealing based heuristic algorithm for solving problems of higher complexity. We compare the performance and the computation time of the MILP model and the heuristic algorithm considering different tests instances. Our results indicate that simulated annealing obtains results within 5\0f the optimal solution, thus making it a viable approach in large scale networks. }
}
-
G. Huiban and G. Robson Mateus.
Optimization aspects of the reconfiguration problem in WDM networks.
Research report,
INRIA Research Report 5730 and I3S Research Report I3S/RR-2005-33-FR,
2005.
[WWW
] [PDF
]
| Abstract: |
|
We propose an in-depth study of the reconfiguration problem in multi-fiber WDM networks. It consists in defining how to adapt the optical layer to changing traffic patterns. Our objective is to treat the problem globally. We consider arbitrary mesh topology, all-to-all traffic and multi-hop routing. However, we restrict ourselves to prevision: the traffic evolutions are foreseen. We propose a compact Mixed Integer Linear Programming model, allowing to solve medium instances. We define many metrics to evaluate the performance of a solution. We also propose some mathematical cuts and a lower bound for the problem. We make extensive experiments based on this model, in order to find out the influence of different parameters, such as the metric chosen or the cut formulation. To do so, many instances were solved with different networks. |
@TechReport{HuRo05c,
author = {G. Huiban and G. {Robson Mateus}},
title = {Optimization aspects of the reconfiguration problem in {WDM} networks},
institution = {INRIA Research Report 5730 and I3S Research Report I3S/RR-2005-33-FR},
year = {2005},
type = {Research report},
PDF = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5730.pdf},
URL={http://www.inria.fr/rrrt/rr-5730.shtml},
abstract = {We propose an in-depth study of the reconfiguration problem in multi-fiber WDM networks. It consists in defining how to adapt the optical layer to changing traffic patterns. Our objective is to treat the problem globally. We consider arbitrary mesh topology, all-to-all traffic and multi-hop routing. However, we restrict ourselves to prevision: the traffic evolutions are foreseen. We propose a compact Mixed Integer Linear Programming model, allowing to solve medium instances. We define many metrics to evaluate the performance of a solution. We also propose some mathematical cuts and a lower bound for the problem. We make extensive experiments based on this model, in order to find out the influence of different parameters, such as the metric chosen or the cut formulation. To do so, many instances were solved with different networks.}
}
-
R. J. Kang,
T. Müller,
and J.-S. Sereni.
Improper colouring of (random) unit disk graphs.
Research report,
INRIA Research Report 5761 and I3S Research Report I3S/RR-2005-35-FR,
November 2005.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
For any graph $G$, the $k$-improper chromatic number $\chi^k(G)$ is the smallest number of colours used in a colouring of $G$ such that each colour class induces a subgraph of maximum degree $k$. We investigate the ratio of the $k$-improper chromatic number to the clique number for unit disk graphs and random unit disk graphs to generalise results where only proper colouring was considered. |
@TechReport{KMS05b,
author = {R. J. Kang and T. M\"uller and J.-S. Sereni},
title = {Improper colouring of (random) unit disk graphs},
institution = {INRIA Research Report 5761 and I3S Research Report I3S/RR-2005-35-FR},
year = {2005},
month={November},
PDF={ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5761.pdf},
POSTSCRIPT={ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5761.ps.gz},
URL={http://hal.inria.fr/inria-00070259/fr/},
type = {Research report},
abstract = {For any graph $G$, the $k$-improper chromatic number $\chi^k(G)$ is the smallest number of colours used in a colouring of $G$ such that each colour class induces a subgraph of maximum degree $k$. We investigate the ratio of the $k$-improper chromatic number to the clique number for unit disk graphs and random unit disk graphs to generalise results where only proper colouring was considered.},
}
-
R. Klasing,
C. Laforest,
J. Peters,
and N. Thibault.
Constructing Incremental Sequences in Graphs.
Research Report,
INRIA Research Report RR-5648 and I3S Research Report I3S/RR-2005-22-FR,
2005.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
Given a weighted graph $G=(V,E,w)$, we investigate the problem of constructing a sequence of $n=|V|$ subsets of vertices $M_1,...,M_n$ (called groups) with small diameters, where the diameter of a group is calculated using distances in $G$. The constraint on these $n$ groups is that they must be incremental: $M_1\subsetM_2 \subset...\subsetM_n=V$. The cost of a sequence is the maximum ratio between the diameter of each group $M_i$ and the diameter of a group $N_i^*$ with $i$ vertices and minimum diameter: $\max_2 \leqi \leqn \left{ \fracD(M_i)D(N_i^*) \right}$. This quantity captures the impact of the incremental constraint on the diameters of the groups in a sequence. We give general bounds on the value of this ratio and we prove that the problem of constructing an optimal incremental sequence cannot be solved approximately in polynomial time with an approximation ratio less than 2 unless $P = NP$. Finally, we give a 4-approximation algorithm and we show that the analysis of our algorithm is tight. |
@TechReport{KLPT05,
author = {R. Klasing and C. Laforest and J. Peters and N. Thibault},
title = {Constructing Incremental Sequences in Graphs},
institution = {INRIA Research Report RR-5648 and I3S Research Report I3S/RR-2005-22-FR},
type = {Research Report},
year = {2005},
OPTkey = {},
OPTtype = {},
OPTnumber = {},
OPTaddress = {},
OPTmonth = {},
OPTnote = {},
OPTannote = {},
PDF = {http://www.i3s.unice.fr/~mh/RR/2005/RR-05.22-R.KLASING.pdf},
POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5648.ps.gz},
url = {http://hal.inria.fr/inria-00070361/fr/},
abstract = {Given a weighted graph $G=(V,E,w)$, we investigate the problem of constructing a sequence of $n=|V|$ subsets of vertices $M_1,...,M_n$ (called groups) with small diameters, where the diameter of a group is calculated using distances in $G$. The constraint on these $n$ groups is that they must be incremental: $M_1\subsetM_2 \subset...\subsetM_n=V$. The cost of a sequence is the maximum ratio between the diameter of each group $M_i$ and the diameter of a group $N_i^*$ with $i$ vertices and minimum diameter: $\max_2 \leqi \leqn \left{ \fracD(M_i)D(N_i^*) \right}$. This quantity captures the impact of the incremental constraint on the diameters of the groups in a sequence. We give general bounds on the value of this ratio and we prove that the problem of constructing an optimal incremental sequence cannot be solved approximately in polynomial time with an approximation ratio less than 2 unless $P = NP$. Finally, we give a 4-approximation algorithm and we show that the analysis of our algorithm is tight.},
}
-
R. Klasing,
E. Markou,
T. Radzik,
and F. Sarracco.
Approximation Results for Black Hole Search in Arbitrary Networks.
Research Report,
INRIA Research Report RR-5659 and I3S Research Report I3S/RR-2005-23-FR,
2005.
[PDF
] [POSTSCRIPT
]
@TechReport{KMRS05c,
author = {R. Klasing and E. Markou and T. Radzik and F. Sarracco},
title = {Approximation Results for Black Hole Search in Arbitrary Networks},
institution = {INRIA Research Report RR-5659 and I3S Research Report I3S/RR-2005-23-FR},
type = {Research Report},
year = {2005},
OPTkey = {},
OPTtype = {},
OPTnumber = {},
OPTaddress = {},
OPTmonth = {},
OPTnote = {},
OPTannote = {},
PDF = {http://www.i3s.unice.fr/~mh/RR/2005/RR-05.23-R.KLASING.pdf},
POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5659.ps.gz},
}
-
J. Moulierac and A. Guitton.
Distributed Multicast Tree Aggregation.
Technical report 5636,
Inria,
July 2005.
[PDF
]
| Abstract: |
|
Multicast is not scalable mainly due to the number of forwarding states and control overhead required to maintain trees. Tree aggregation reduces the number of multicast forwarding states and the tree maintenance overhead by allowing several multicast groups to share the same delivery tree. In this paper, we exhibit several drawbacks of the existing protocols: the latency to manage group dynamics is high, the managers are critical points of failures and some group-specific entries are stored unnecessarily. Then, we propose a new distributed protocol that significantly reduces the number of control messages and limits the number of trees within a domain. By simulations, we show that our protocol achieves good performance and outperforms the previous known distributed algorithm. |
@techreport{MG05a,
author = {J. Moulierac and A. Guitton},
title = {{Distributed Multicast Tree Aggregation}},
institution = {Inria},
year = {2005},
number = {5636},
month = {July},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/RR-5636.pdf},
ABSTRACT={Multicast is not scalable mainly due to the number of forwarding states and control overhead required to maintain trees. Tree aggregation reduces the number of multicast forwarding states and the tree maintenance overhead by allowing several multicast groups to share the same delivery tree. In this paper, we exhibit several drawbacks of the existing protocols: the latency to manage group dynamics is high, the managers are critical points of failures and some group-specific entries are stored unnecessarily. Then, we propose a new distributed protocol that significantly reduces the number of control messages and limits the number of trees within a domain. By simulations, we show that our protocol achieves good performance and outperforms the previous known distributed algorithm.}
}
-
J. Moulierac and M. Molnàr.
Active monitoring of delays with asymmetric routes.
Technical report 5635,
Inria,
July 2005.
[PDF
]
| Abstract: |
|
There is an increasing interest in network monitoring recently. Indeed, knowledge of link characteristics is of significant importance in order to provide efficient routing. In this paper, we consider active network monitoring of link delays in a Service Provider or Enterprise IP network using round trip delays. Our proposition guarantees that all links are monitored contrary to previous propositions. Indeed, previous propositions assume symmetric routing in networks when placing the monitoring stations. With this assumption, round trips may be different when routes are asymmetric and link delays are not significant. We say that links are not monitored in this case. Previous propositions do not monitor 5.76\0f links in average and 10\ 144878418n worst cases during our simulations while we monitor always 100\0f links. Moreover, in our proposition, the amount of traffic is reduced and the measures are more precise since the distance from a monitoring station (beacon) to the edges is limited by a given bound. Indeed, probe messages use short paths, traverse less routers and less links with our proposition. Finally, the number of beacons is not increased compared to the previous heuristic and so the installation and maintenance costs are minimized. |
@techreport{MM05,
author = {J. Moulierac and M. Moln\`ar},
title = {{Active monitoring of delays with asymmetric routes}},
institution = {Inria},
year = {2005},
number = {5635},
month = {July},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/RR-5635.pdf},
ABSTRACT={There is an increasing interest in network monitoring recently. Indeed, knowledge of link characteristics is of significant importance in order to provide efficient routing. In this paper, we consider active network monitoring of link delays in a Service Provider or Enterprise IP network using round trip delays. Our proposition guarantees that all links are monitored contrary to previous propositions. Indeed, previous propositions assume symmetric routing in networks when placing the monitoring stations. With this assumption, round trips may be different when routes are asymmetric and link delays are not significant. We say that links are not monitored in this case. Previous propositions do not monitor 5.76\0f links in average and 10\ 144878418n worst cases during our simulations while we monitor always 100\0f links. Moreover, in our proposition, the amount of traffic is reduced and the measures are more precise since the distance from a monitoring station (beacon) to the edges is limited by a given bound. Indeed, probe messages use short paths, traverse less routers and less links with our proposition. Finally, the number of beacons is not increased compared to the previous heuristic and so the installation and maintenance costs are minimized.}
}
