We consider the placement of jobs inside a data center. Traditionally, this is done by a task orchestrator without taking into account network constraints. According to recent studies, network transfers may account for up to 50% of the completion time of classical jobs. Thus, network resources must be considered when placing jobs in a data center. In this paper, we propose a new scheduling framework, introducing network tasks that need to be executed on network machines alongside traditional (CPU) tasks. The model takes into account the competition between communications for the network resources, which is not considered in the formerly proposed scheduling models with communication. Network transfers inside a data center can be easily modeled in our framework. As we show, classical algorithms do not efficiently handle a limited amount of network bandwidth. We thus propose new provably efficient algorithms with the goal of minimizing the makespan in this framework. We show their efficiency and the importance of taking into consideration network capacity through extensive simulations on workflows built from Google data center traces.

With the advent and the growing usage of Machine Learning as a Service (MLaaS), cloud and network systems are now offering the possibility to deploy ML tasks on heterogeneous clusters. Then, network and cloud operators have to schedule these tasks, determining both when and on which devices to execute them. In parallel, several solutions, such as neural network compression, were proposed to build small models which can run on limited hardware. These solutions allow choosing the model size at inference time for any targeted processing time without having to re-train the network.In this work, we consider the Deadline Scheduling with Compressible Tasks (DSCT) problem: a novel scheduling problem with task deadlines where the tasks can be compressed. Each task can be executed with a certain compression, presenting a trade-off between its compression level (and, its processing time) and its obtained utility. The objective is to maximize the tasks utilities. We propose an approximation algorithm with proved guarantees to solve the problem. We validate its efficiency with extensive simulation, obtaining near optimal results. As application scenario, we study the problem when the tasks are Deep Learning classification jobs, and the objective is to maximize their global accuracy, but we believe that this new framework and solutions apply to a wide range of application cases.

Advancements in cloud computing have boosted Machine Learning as a Service (MLaaS), highlighting the challenge of scheduling tasks under latency and deadline constraints. Neural network compression offers the latency and energy consumption reduction in data centers, aligning with efforts to minimize cloud computing’s carbon footprint, despite some accuracy loss.

We study opinion dynamics in multi-agent networks where agents hold binary opinions and are influenced by their neighbors while being biased towards one of the two opinions, called the superior opinion. The dynamics is modeled by the following process: at each round, a randomly selected agent chooses the superior opinion with some probability α, and with probability 1-α it conforms to the opinion manifested by the majority of its neighbors. In this work, we exhibit classes of network topologies for which we prove that the expected time for consensus on the superior opinion can be exponential. This answers an open conjecture in the literature. In contrast, we show that in all cubic graphs, convergence occurs after a polynomial number of rounds for every α. We rely on new structural graph properties by characterizing the opinion formation in terms of multiple domination, stable and decreasing structures in graphs, providing an interplay between bias, consensus and network structure. Finally, we provide both theoretical and experimental evidence for the existence of decreasing structures and relate it to the rich behavior observed on the expected convergence time of the opinion diffusion model.

In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determine the eternal domination number $$\gamma ^{\infty }_{all}$$ of a graph, which is the minimum number of guards required to defend against an infinite sequence of attacks. This paper first continues the study of the eternal domination game on strong grids $$P_n\boxtimes P_m$$ . Cartesian grids $$P_n \square P_m$$ have been vastly studied with tight bounds existing for small grids such as $$k\times n$$ grids for $$k\in \{2,3,4,5\}$$ . It was recently proven that $$\gamma ^{\infty }_{all}(P_n \square P_m)=\gamma (P_n \square P_m)+O(n+m)$$ where $$\gamma (P_n \square P_m)$$ is the domination number of $$P_n \square P_m$$ which lower bounds the eternal domination number [Lamprou et al. Eternally dominating large grids. Theoretical Computer Science, 794:27–46, 2019]. We prove that, for all $$n,m\in \mathbb {N^*}$$ such that $$m\ge n$$ , $$\lfloor \frac{n}{3} \rfloor \lfloor \frac{m}{3} \rfloor +\Omega (n+m)=\gamma _{all}^{\infty } (P_{n}\boxtimes P_{m})=\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil + O(m\sqrt{n})$$ (note that $$\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil$$ is the domination number of $$P_n\boxtimes P_m$$ ). We then generalise our technique to prove that $$\gamma _{all}^{\infty }(G)=\gamma (G)+o(\gamma (G))$$ for all graphs $$G\in {\mathcal {F}}$$ , where $${\mathcal {F}}$$ is a large family of D-dimensional grids which are supergraphs of the D-dimensional Cartesian grid and subgraphs of the D-dimensional strong grid. In particular, $${\mathcal {F}}$$ includes both the D-dimensional Cartesian grid and the D-dimensional strong grid.

We consider the placement of jobs inside a data center. Traditionally, this is done by a task orchestrator without taking into account network constraints. According to recent studies, network transfers represent up to 50% of the completion time of classical jobs. Thus, network resources must be considered when placing jobs in a data center. In this paper, we propose a new scheduling framework, introducing network tasks that need to be executed on network machines alongside traditional (CPU) tasks. The model takes into account the competition between communications for the network resources, which is not considered in the formerly proposed scheduling models with communication. Network transfers inside a data center can be easily modeled in our framework. As we show, classical algorithms do not efficiently handle a limited amount of network bandwidth. We thus propose new provably efficient algorithms with the goal of minimizing the makespan in this framework. We show their efficiency and the importance of taking into consideration network capacity through extensive simulations on workflows built from Google data center traces.

ISP networks are taking a leap forward thanks to emerging technologies such as Software Defined Networking (SDN) and Network Function Virtualization (NFV). Efficient algorithms considered too hard to be put in practice on legacy networks now have a second chance to be considered again. In this context, we rethink the ISP network dimensioning problem with protection against Shared Risk Link Group (SLRG) failures. We consider a path-based protection scheme with a global rerouting strategy in which, for each failure situation, we may have a new routing of all the demands. Our optimization task is to minimize the needed amount of bandwidth. We develop a scalable mathematical model that we handle using the Column Generation technique. We show the effectiveness of our methods and demonstrate the feasibility of our approach using Mininet.

A Service Function Chain (SFC) is an ordered sequence of network functions, such as load balancing, content filtering, and firewall. With the Network Function Virtualization (NFV) paradigm, network functions can be deployed as pieces of software on generic hardware, leading to a flexibility of network service composition. Along with its benefits, NFV brings several challenges to network operators, such as the placement of virtual network functions. In this paper, we study the problem of how to optimally place the network functions within the network in order to satisfy all the SFC requirements of the flows. Our optimization task is to minimize the total deployment cost. We show that the problem can be seen as an instance of the Set Cover Problem, even in the case of ordered sequences of network functions. It allows us to propose two logarithmic factor approximation algorithms which have the best possible asymptotic factor. Further, we devise an optimal algorithm for tree topologies. Finally, we evaluate the performances of our proposed algorithms through extensive simulations. We demonstrate that near-optimal solutions can be found with our approach.

In the Spy Game played on a graph G, a single spy travels the ertices of G at speed s, while multiple slow guards strive to have, at all times, one of them within distance d of that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strategies it yields for the guards. We then show the equivalence of fractional and integral strategies in trees. This allows us to design a polynomial-time algorithm for computing an optimal strategy in this class of graphs. Using duality in Linear Programming, we also provide non-trivial bounds on the fractional guardnumber of grids and torus. We believe that the approach using fractional relaxation and Linear Programming is promising to obtain new results in the field of combinatorial games.

In telecommunication networks, packets are carried from a source to a destination on a path determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from to follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore, the routing protocol must determine how the traffic from to is distributed among the shortest paths. In the protocol called Open Shortest Path First‐Equal Cost Multiple Path (ospf‐ecmp) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities. In this work, we show that the problem of maximizing even a single commodity flow for the ospf‐ecmp protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial‐time approximations and an exponential‐time exact algorithm. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 344–352 2015

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu (1997) defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. Max Coloring Problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes, in particular, there exists a PTAS for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The Exponential Time Hypothesis (ETH) states that 3-SAT cannot be solved in sub-exponential time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n O(log(n)). Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components.

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu defined the weighted chromatic number of a vertex-weighted graph $G$ as the smallest weight of a proper coloring of $G$. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. the max coloring problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes; in particular, there exists a polynomial-time approximation scheme for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The exponential time hypothesis (ETH) states that 3-SAT cannot be solved in subexponential time. We show that, assuming the ETH, the best algorithm to compute the weighted chromatic number of $n$-node trees has time-complexity $n^{\Theta(\log n)}$. Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph $G$, it is hard to combine colorings of its connected components.

Distributed and peer-to-peer storage systems are foreseen as an alternative to the traditional data centers and in-house backup solutions. In the past few years many peer-to- peer storage systems have been proposed. Most of them rely on the use of erasure codes to introduce redundancy to the data. This kind of system depends on many parameters that need to be well tuned, such as the factor of redundancy, the frequency of data repair and the size of a data block. In this paper we give closed-form mathematical expressions that estimate the system average behavior. These expressions are derived from a Markov chain. Our contribution is a guideline to system designers and administrators to choose the best set of parameters. That is, how to tune the system parameters to obtain a desired level of reliability under a given constraint of bandwidth consumption. We confirm that a lazy repair strategy can be employed to amortize the repairing cost. Moreover, we propose a formula to calculate the optimal threshold value that minimizes the bandwidth consumption. Finally, we additionally discuss the impact of different system characteristics on the performance metrics, such as the number of peers, the amount of stored data, and the disk failure rate. To the best of our knowledge this is the first work to give close-form formulas to estimate the bandwidth consumption for a lazy repair, and the loss rate taking into account the repair time.

In this article, we study a combinatorial optimization problem arising from on-board networks in satellites. In these kinds of networks, the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four available links. The paths connecting inputs to outputs should be link-disjoint. More formally, we call a (p, λ, k)-network an undirected graph with p + λ inputs, p + k outputs, and internal vertices of degree four. A (p, λ, k)-network is valid if it is tolerant to a restricted number of faults in the network, i.e., if, for any choice of at most λ faulty inputs and k faulty outputs, there exist p edge-disjoint paths from the remaining inputs to the remaining outputs. Our optimization problem consists of determining N(p, λ, k), the minimum number of vertices in a valid (p, λ, k)-network. We present validity certificates and a quasi-partitioning technique from which we derive lower bounds for N(p, λ, k). We also provide constructions, and hence upper bounds, based on expanders. The problem is shown to be sensitive to the order of λ and k. For instance, when λ and k are small compared with p, the question reduces to the avoidance of some forbidden local configurations. For larger values of λ and k, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called α-robustness. We use α-robustness to generalize our constructions for larger values of k and λ. In many cases, we provide asymptotically tight bounds for N(p, λ, k). © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. To achieve high durability, such P2P systems encode the user data in a set of redundant fragments and distribute them among the peers. In this paper, we study the impact of different data placement strategies on the system performance when using erasure codes redundancy schemes. We compare three policies: two of them local, in which the data are stored in logical neighbors, and the other one global, in which the data are spread randomly in the whole system. We focus on the study of the probability to lose a data block and the bandwidth consumption to maintain enough redundancy. We use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the local policies. When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. Finally, we propose a new external reconstruction strategy and a suitable degree of locality that could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement.

Peer-to-peer storage systems aim to provide a reliable long-term storage at low cost. In such systems, peers fail continuously, hence, the necessity of self-repairing mechanisms to achieve high durability. In this paper, we propose and study analytical models that assess the bandwidth consumption and the probability to lose data of storage systems that use erasure coded redundancy. We show by simulations that the classical stochastic approach found in the literature, that models each block independently, gives a correct approximation of the system average behavior, but fails to capture its variations over time. These variations are caused by the simultaneous loss of multiple data blocks that results from a peer failing (or leaving the system). We then propose a new stochastic model based on a fluid approximation that better captures the system behavior. In addition to its expectation, it gives a correct estimation of its standard deviation. This new model is validated by simulations.

We present a result concerning the relation between the path-width of a plane graph and the path-width of its dual. We prove that for a 3-connected planar graph G, ${\rm pw}(G)\leq3{\rm pw}(G^*)+2$. For 4-connected planar graphs, and more generally for Hamiltonian planar graphs, we prove a stronger bound ${\rm pw}(G^*)\leq2~{\rm pw}(G)+c$. The best previously known bound was obtained by Fomin and Thilikos who proved that ${\rm pw}(G^*)\leq6~{\rm pw}(G)+c$. Our proof is based on a transformation which, given a fixed spanning tree of G, sends any given decomposition of G into one of $G^*$. The ratio of the corresponding parameters is bounded by the maximum degree of the spanning tree.

In the broadcasting problem, one node needs to broadcast a message to all other nodes in a network. If nodes can only communicate with one neighbor at a time, broadcasting takes at least $\lceil \log_2 N \rceil$ rounds in a network of N nodes. In the neighborhood broadcasting problem, the node that is broadcasting needs to inform only its neighbors. In a binary hypercube with N nodes, each node has $\log_2 N$ neighbors, so neighborhood broadcasting takes at least $\lceil \log_2 \log_2 (N+1) \rceil$ rounds. In this paper, we present asymptotically optimal neighborhood broadcast protocols for binary hypercubes.

In this paper we extend the technique provided in [M. Flammini and S. Pérennès, Inform. and Comput., to appear] to allow the determination of lower bounds on the broadcasting and gossiping time required by the so-called restricted protocols. Informally, a protocol is {\small $({\cal I}, {\cal O})$}-restricted if at every processor each outgoing activation of an arc depends on at most ${\cal I}$ previous incoming activations and any incoming activation influences at most ${\cal O}$ successive outgoing activations. Examples of restricted protocols are systolic ones and those running on bounded degree networks. Thus, under the basic whispering model, we provide the first general lower bound on the gossiping time of d-bounded degree networks in the directed and half-duplex cases. Moreover, significantly improved broadcasting and gossiping lower bounds are obtained for well-known networks such as butterfly, de Bruijn, and Kautz graphs. All the results are also extended to other communication models such as the c-port and/or postal one.

We develop traffic grooming algorithms for WDM networks with multi-layer switches. We consider a node as an N-layer switch, in which a given layer k is an aggregated set of elements of layer k-1. Typical examples of layers are wavelengths, bands and fibers. The cost of a given node depends on the number of input and output ports of each layer. Assuming this model and a traffic matrix - with unity elements in layer 0 - minimizing the cost of the network consists of grooming traffic in such a way that as much traffic as possible is switched in the highest possible layer (fibers in our example). When some traffic is switched along a path in the network within the same layer, we represent it with a pipe. Each pipe has an associated linear cost depending on the current layer and on the number of nodes crossed in that pipe. In the case of a two layers model the problem was considered in Gerstel et al. (2000) for rings or in Cinker et al. (2000) for general topologies. We present an integer linear programming formulation for this model that aims to minimize the overall cost of the network for a given input traffic matrix. We ran experiments using the CPLEX optimization package on various topologies such as actual networks like the Pan-European all optical network (Batchelor et al. (1999)) as well as rings and meshes of various sizes.

Abstract The de Bruijn digraph B(d, D) has degree d, diameter D, dD vertices, and dD+1 arcs. It is usually defined by words of size D on an alphabet of cardinality d, through a cyclic left‐shift permutation on the words, after which the rightmost symbol is changed. In this paper, we show that any digraph defined on words of a given size, through an arbitrary permutation on the alphabet and an arbitrary permutation on the word indices, is isomorphic to the de Bruijn digraph, provided that this latter permutation is cyclic. We use this result to improve from O(dD+1) to $\Theta(\sqrt{d^{D+1}})$ the number of lenses required for the implementation of B(d, D) by the Optical Transpose Interconnection System proposed by Marsden et al. [Opt Lett 18 (1993), 1083–1085]. © 2002 Wiley Periodicals, Inc.

Abstract We consider the problem of disseminating messages in networks. We are interested in information dissemination algorithms in which machines operate independently without any knowledge of the network topology or size. Three communication tasks of increasing difficulty are studied. In blind broadcasting (BB), the goal is to communicate the source message to all nodes. In acknowledged blind broadcasting (ABB), the goal is to achieve BB and inform the source about it. Finally, in full synchronization (FS), all nodes must simultaneously enter the state terminated after receiving the source message. The algorithms should be efficient both in terms of the time required and the communication overhead they put on the network. We limit the latter by allowing every node to send a message to at most one neighbor in each round. We show that BB is achieved in time at most 2n in any n‐node network and show networks in which time 2n − o(n) is needed. For ABB, we show algorithms working in time (2 + ϵ)n, for any fixed positive constant ϵ and sufficiently large n. Thus, for both BB and ABB, our algorithms are close to optimal. Finally, we show a simple algorithm for FS working in time 3n and a more complicated algorithm which works in time 2.9n. The optimal time of full synchronization remains an open problem. © 2001 John Wiley & Sons, Inc.

In this paper we show that many general lower bounds on the broadcasting and gossiping time are optimal. In particular, let b(G) be the broadcasting time of a network G under the basic one-port model. The only lower bound on b(G) holding for every n vertices graph G is max$(\log_2 n, Diam(G))$, but the $\log_2 n$ factor cannot be achieved in bounded degree networks. In fact, let the parameter d be defined in undirected graphs as the maximum degree minus one and for directed graphs as the maximum out-degree. Then, in [ SIAM J. Discrete Math., 1 (1998), pp. 531--540; SIAM J. Discrete Math., 5 (1992), pp. 10--24] it has been proved that, for any graph G of parameter d, b(G) \geq \frac{\log_2 n}{\log_2 \xi}$, where $\xi$ is the largest real number such that $\xi^{d} -\xi^{d-1} - \xi^{d-2} -\cdots - \xi-1=0$. Since then many papers have proposed constructions of bounded degree networks having a small broadcast time [Proceedings of the 2nd International Euro-Par Conference (EUROPAR), Lecture Notes in Comput. Sci. 1123, Springer-Verlag, New York, 1996, pp. 313--324; IEEE Trans. Comput., 33 (1984), pp. 190--194], but so far the optimality of [SIAM J. Discrete Math., 1 (1998), pp. 531--540; {SIAM J. Discrete Math.}, 5 (1992), pp. 10--24] was still an open question. In this paper we prove that the above lower bound is tight, improving all the existing upper bounds by means of probabilistic methods. Namely, we show that for n arbitrarily large there exist families of n vertices graphs in which a uniformly drawn graph has broadcasting time as predicted by [SIAM J. Discrete Math., 1 (1998), pp. 531--540; SIAM J. Discrete Math., 5 (1992), pp. 10--24] with probability converging to 1. Moreover, we show that [SIAM J. Discrete Math., 1 (1998), pp. 531--540; SIAM J. Discrete Math., 5 (1992), pp. 10--24] is attained even in the case of gossiping and systolic gossiping in the full-duplex mode. Finally, new upper bounds on bounded-degree and systolic gossiping are also determined in the directed and half-duplex modes. While the systolic construction is tight and matches the lower bound of [Inform and Comput., to appear], we strongly conjecture that the bounded-degree result is optimal and that a corresponding matching lower bound is still to be proven.

In this paper we propose a method which enables us to construct almost optimal broadcast schemes on an n-dimensional hypercube in the circuit switched, /spl Delta/-port model. In this model, an initiator must inform all the nodes of the network in a sequence of rounds. During a round, vertices communicate along arc-disjoint dipaths. Our construction is based on particular sequences of nested binary codes having the property that each code can inform the next one in a single round. This last property is insured by a flow technique and results about symmetric flow networks. We apply the method to design new schemes improving and generalizing the previous results. Our schemes are the best possible algebraic schemes, and they are optimal in the case n=2/sup p/-1.

The de Bruijn digraph B(d, D) is usually defined by words of size D on an alphabet of cardinality d, through a cyclic left shift permutation on the words, after which the rightmost symbol is changed. In this paper we show that any digraph defined on words and alphabets of the same size, through an arbitrary permutation on the alphabet and an arbitrary permutation on the word indices, is isomorphic to the de Bruijn, provided that this latter permutation is cyclic. This work is motivated by the next application. It is known that the optical transpose interconnection system from UCSD can implement the de Bruijn interconnections for n nodes, for a fixed d, with O(n) lenses. We show here how to improve this hardware requirement to /spl Theta/(/spl radic/n).

We consider the task of distributedly assigning distinct labels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology or the size of the network (unknown network). They execute identical algorithms, apart from a distinguished node, called the source, which starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms.

A tree of rings is an undirected graph obtained from the union of rings, which intersect two by two in at most one node, such that any two nodes are connected by exactly two edge-disjoint paths. In this paper, we consider symmetric directed trees of rings with weighted nodes. A routing for a weighted digraph is a collection of directed paths (dipaths), such that for each ordered pair of nodes (x_1,x_2) with respective weights w_1 and w_2, there are w_1w_2 dipaths (possibly not distinct) from x_1 to x_2. Motivated by the Wavelength Division Multiplexing (WDM) technology in all-optical networks, we study the problem of finding a routing which can be colored by the fewest number of colors so that dipaths of the same color are arc-disjo- int. We prove that this minimum number of colors (wavelengths) is equal to the maximum number of dipaths that share one arc (load), minimized over all routings. The problem can be efficiently solved (dipaths found and colored) using cut properties.

In this paper, we deal with the compact routing problem on distributed networks, that is implementing routing schemes that use a minimum memory size on each node.We prove that for every shortest path routing scheme, for any constant e, O < c < 1, and for every integer d such that 3 ~d < En, there exists a n-node network of maximum degree d that locally requires @(n log d) bits of memory on El(n) nodes.This optimal lower bound means that whatever you choose the routing scheme (interval routing, boolean routing, prefix routing, ...).there exists a network on which one can not do better than routing tables.

This paper presents a new decomposition technique for hierarchical Cayley graphs. This technique yields a very easy implementation of the divide and conquer paradigm for some problems on very complex architectures as the star graph or the pancake. As applications, we introduce algorithms for broadcasting and prefix-like operations that improve the best known bounds for these problems. We also give the first nontrivial optimal gossiping algorithms for these networks. In star-graphs and pancakes with N=n! processors, our algorithms take less than [log N]+1.5n steps.