On the Design of Virtual Networks (Sébastien Choplin)
The advent of fiber optic media has dramatically changed the classical
views on the role and structure of digital communication networks. Specifically,
the sharp distinction between telephone networks, cable television networks,
and computer networks, has been replaced by a unified approach. Several
communication schemes are achieved on virtual topologies designed on physical
networks (ATM,MPCFS,WDM,...). In this context, we investigate the problem
of designing such topologies, which consists of finding a set of paths
satisfying some constraints in terms of load (the number of paths sharing
a physical link) and hop count (the number of paths used to satisfy a connection).
This problem has been studied in ATM context (,)
but can also be applied to more general communication scheme. This problem
is an extension of the edge forwarding index problem (,,)
(where the hop count is one).
We model the physical network by a graph G(V,E) where
is the set of nodes/vertices and
E is the set of edges/links. We
define a virtual graph H=(V,E') with the same set
of vertices as G and a routing function P which associates
P(e') in G to each edge e' in E'
Given a virtual graph H and a routing function P, the loadl(e)
of an edge
of the physical graph is the number of paths that contain e; namely, .
Given a H and P, the maximal edge load.
Given a graph H, we are looking for a routing function P
which minimizes .
The minimal load of G for H is .
Given a set of requests I, the hop count of a request is
the number of virtual links used to achieved this request and the maximum
hop count is the maximum of the hop counts over all the requests.
Given a graph G and a set of requests, the following problems can
be studied :
In the case of All-to-All set of requests and hop count 1, the problem
which consists in finding P in order to minimize the load is the
index problem (,,)
(in this case, H is the complete graph).
Given a hop count h , find H and P such that the maximal
load is minimized
Given a maximum load, find H and P such that the maximum
hop count is minimized
After giving results on complexity of these problems on general graphs,
we will study particular networks: paths and cycles. For a All-to-All set
of requests, we give tight bounds on the network capacity (the maximum
load of a physical link) as a function of the maximum hop count for each
connection. These results can be found in 
Communications à diamètre fixé dans les réseaux
ATM, DEA, Juin 1999.
Path Layout in ATM Path with Given Hop Count.
In International Conference on Networking, ICN01, volume 2094,
Part II of LNCS, pages 527-537. Springer, 2001.
F. R. K. Chung, E. G. Coffman, M. I. Reiman, and B. Simon.
The Forwarding Index of Communication Networks.
IEEE Trans. on Information Theory, IT-33, 2:224-232, 1987.
Communications Structurées dans les Réseaux.
PhD thesis, Université de Nice - Sophia Antipolis, http://www.inria.fr/RRRT/TU-0631.html
, juin 2000.
J-C. Meyer, M-C. Heydemann, and D. Sotteau.
On Forwarding Indices of Networks.
Discrete Applied Mathematics 23:103-123, 1989.
Complexity of the Forwarding Index Problem.
SIAM Journal on Discrete Mathematics, 6(3):418-427, 1993.
Path Layout in ATM Networks - A Survey.
In Proc, of DIMACS Workshop on Networks in Distributed Computing,
DIMACS Center, Rutgers University, Oct. 1997.