Creat membership Creat membership
Sign in

Forgot password?

Confirm
  • Forgot password?
    Sign Up
  • Confirm
    Sign In
home > search

Now showing items 33 - 40 of 40

  • Self-Organization in Large Scale Ad Hoc Networks

    Nathalie Mitton   Anthony Busson   Eric Fleury  

    Flat ad hoc architectures are not scalable. In order to overcome this major drawback; hierarchical routing is introduced since it is found to be more effective. The main challenge in hierarchical routing is to group nodes into clusters. Each cluster is represented by one cluster head. Conventional methods use either the connectivity (degree) or the node Id to perform the cluster head election. Such parameters are not really robust in terms of side effects. In this paper we introduce a novel measure that both forms clusters and performs the cluster head election. Analytical models and simulation results show that this new measure for cluster head election induces less cluster head changes as compared to classical methods.
    Download Collect
  • MultiAspect Graphs: Algebraic Representation and Algorithms

    Klaus Wehmuth   Eric Fleury   Artur Ziviani  

    We present the algebraic representation and basic algorithms of MultiAspect Graphs (MAGs), a structure capable of representing multilayer and time-varying networks while also having the property of being isomorphic to a directed graph. In particular, we show that, as a consequence of the properties associated with the MAG structure, a MAG can be represented in matrix form. Moreover, we also show that any possible MAG function (algorithm) can be obtained from this matrix-based representation. This is an important 1 ar X iv :1 50 4. 07 89 3v 1 [ cs .D M ] 2 9 A pr 2 01 5 theoretical result since it paves the way for adapting well-known graph algorithms for application in MAGs. We present a set of basic MAG algorithms, constructed from well-known graph algorithms, such as degree computing, Breadth First Search (BFS), and Depth First Search (DFS). These algorithms adapted to the MAG context can be used as primitives for building other more sophisticated MAG algorithms. Therefore, such examples can be seen as guidelines on how to properly derive MAG algorithms from basic algorithms on directed graph. We also make available python implementations of all the algorithms presented in this paper.
    Download Collect
  • Shortest-path and Hot-potato Routing on Unbuuered 2-d Tori

    Miltos D. Grammatikakis   Miro Kraetzl   Eric Fleury  

    We probabilistically model dynamic routing on un-buuered 2-dimensional tori. We consider shortest-path routing with packet loss and retransmissions versus a newly proposed all-link busy (ALB) hot-potato routing strategy with packet deeections. Computations of the sustained packet generating rate; node through-put; and average packet latency indicate that the proposed ALB strategy is a much better alternative to a shortest-path routing on unbuuered tori. It achieves an almost optimal sustained packet generating rate; near-optimal latency; and acceptable node throughput.
    Download Collect
  • LCM: A Multicast Core Management Protocol for Link-State Routing Networks

    Yih Huang   Eric Fleury   Philip K. McKinleyy  

    In this paper; we propose solutions to several multicast core management problems; including automatic core selection; core failure handling; and core migration; for use in networks based on link-state routing. The proposed approach uses a central server; called the core binding server (CBS); to manage core-group bindings; accompanied by a network-level leader election protocol in order to achieve robustness. By modeling the selection of the CBS as a leader election problem; this approach can handle any combination of network component failures; including those that partition the network. Further; our simulation results reveal that the central server can sustain extremely high workloads; and demonstrate the eeectiveness of our core selection and core migration methods.
    Download Collect
  • A General Theory for Deadlock Avoidance in Wormhole-Routed Networks

    Eric Fleury   Pierre Fraigniaud  

    Most machines of the last generation of distributed memory parallel computers possess speci c routers which are used to exchange messages between non-neighboring nodes in the network. Among the several technologies, wormhole routing is usually prefered because it allows low channel-setup time, and reduces the dependency between latency and inter-node distance. However, wormhole routing is very susceptible to deadlock because messages are allowed to hold many resources while requesting others. Therefore, designing deadlock-free routing algorithms using few hardware facilities is a major problem for wormhole-routed networks. In this paper, we describe a general theoretical framework for the study of deadlockfree routing functions. We give a general de nition of what can be a routing function. This de nition captures many speci c de nitions of the literature (e.g., vertexdependent, input-dependent, source-dependent, path-dependent, etc.). Using our de nition, we give a necessary and su cient condition which characterizes deadlock-free routing functions. Our theory embraces at a high level most of the theories related to deadlock avoidance in wormhole-routed networks previously derived in the literature. In particular, it applies not only to one-to-one routing, but also to one-to-many routing. The latter paradigm is used to solve the multicast problem with the path-based or tree-based facility.
    Download Collect
  • Performance of STC104 vs. Telegraphos

    Eric Fleury   Miltos D. Grammatikakis   Miro Kraetzl  

    We consider continuous routing on nn switches with various buuering schemes. By extending these models to networks; we analyze two 1024-node; unique-path; butterry-like networks conngured with input-output buuered STC104 32 32 switches; or central buuered Telegraphos 4 4 switches. 0 Introduction Parallel and distributed systems consist of processors communicating over an interconnection network conngured with switches and network interfaces. The n n input buuered switch (IDB) has n FIFO buuers. The packet to be transmitted through an output port is selected from all input buuers in round robin fashion. Any packet directed to a full buuer is stalled. The n n split input buuered switch (SIDB) has n 2 FIFO buuers; one for each input-output port combination. The SIDB switch can preroute a packet to determine if it is directed to a full buuer. If all packets corresponding to a given output port are directed to a full buuer; traac is temporarily stalled. Otherwise; the packet to be transmitted is selected using round robin. The nn output buuered switch (ODB) implements FIFO buuering at the output ports. All packets arriving simultaneously can be wired to the appropriate output buuer(s) within T s clock cycles. The ODB switch also uses prerouting to determine whether packets are directed to a full buuer. Such packets are temporarily stalled. The n n central buuer switch (CDB) provides one dedicated buuer for each source-destination pair in the network. Flow control is per virtual circuit (VC); where VC header information identiies uniquely the packet's source and destination. Round robin is implemented at each output port; for selecting the packet to be transmitted. We assume xed packet size; preventive ow control (no packet loss) and similar switch startup time (T s clock cycles); spent in buuering and prerouting before Supported by ANM and PRS of the French CNRS and EU ESPRIT 6253/SHIPS.
    Download Collect
  • Communities detection and analysis of their dynamics in collaborative networks

    Céline Robardet   Eric Fleury  

    In this paper we propose a new way to identify communities in evolving graphs like collaborative networks. We apply this approach on the Infocom co-authorship network to determine stable collaborations and evolving communities. Finally, we analyse the impact of the co-authorships relation topology on the formation of the program committee board of the conference.
    Download Collect
  • Neighbor Discovery in Multi-hop Wireless Networks: Evaluation and Dimensioning with Interferences Considerations

    Elyes Ben Hamida   Guillaume Chelius   Anthony Busson   Eric Fleury  

    Neighbor discovery in multi-hop wireless networks: evaluation and dimensioning with interferences considerations. HAL is a multidisciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt età la diffusion de documents scientifiques de niveau recherche, publiés ou non, ´ emanant desétablissements d'enseignement et de recherche français oú etrangers, des laboratoires publics ou privés. Neighbor discovery in multi-hop wireless networks: evaluation and dimensioning with interference considerations † In this paper, we study the impact of collisions and interference on a neighbor discovery process in the context of multi-hop wireless networks. We consider three models in which interference and collisions are handled in very different ways. From an ideal channel where simultaneous transmissions do not interfere, we derive an alternate channel where simultaneous transmissions are considered two-by-two under the form of collisions, to finally reach a more realistic channel where simultaneous transmissions are handled under the form of shot-noise interference. In these models, we analytically compute the link probability success between two neighbors as well as the expected number of nodes that correctly receive a Hello packet. Using this analysis, we show that if the neighbor discovery process is asymptotically equivalent in the three models, it offers very different behaviors locally in time. In particular, the scalability of the process is not the same depending on the way interference is handled. Finally, we apply our results to the dimensioning of a Hello protocol parameters. We propose a method to adapt the protocol parameters to meet application constraints on the neighbor discovery process and to minimize the protocol energy consumption.
    Download Collect
1 2 3

Contact

If you have any feedback, Please follow the official account to submit feedback.

Turn on your phone and scan

Submit Feedback