Página 1 dos resultados de 71 itens digitais encontrados em 0.000 segundos

The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract)

Fiorini, Samuel; Oriolo, Gianpaolo; Sanità, Laura; Theis, Dirk Oliver
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/12/2008
Relevância na Pesquisa
16.66%
The symmetric Virtual Private Network Design (VPND) problem is concerned with buying capacity on links (edges) in a communication network such that certain traffic demands can be met. We investigate a natural generalization of VPND where the cost per unit of capacity may decrease if a larger amount of capacity is reserved (economies of scale principle). The growth of the cost of capacity is modelled by a non-decreasing concave function $f$. We call the problem the concave symmetric Virtual Private Network Design (cVPND) problem. After showing that a generalization of the so-called Pyramidal Routing problem and hence also the cVPND have the so-called tree routing property, we study approximation algorithms for cVPND. For general $f$, using known results on the so-called Single Source Buy at Bulk problem by Grandoni and Italiano, we give a randomized 24.92-approximation algorithm.; Comment: Oberwolfach abstract

An exact algorithm for the bottleneck 2-connected $k$-Steiner network problem in $L_p$ planes

Brazil, Marcus; Ras, Charl; Thomas, Doreen
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.66%
We present the first exact polynomial time algorithm for constructing optimal geometric bottleneck 2-connected Steiner networks containing at most $k$ Steiner points, where $k>2$ is a constant. Given a set of $n$ vertices embedded in an $L_p$ plane, the objective of the problem is to find a 2-connected network, spanning the given vertices and at most $k$ additional vertices, such that the length of the longest edge is minimised. In contrast to the discrete version of this problem the additional vertices may be located anywhere in the plane. The problem is motivated by the modelling of relay-augmentation for the optimisation of energy consumption in wireless ad hoc networks. Our algorithm employs Voronoi diagrams and properties of block-cut-vertex decompositions of graphs to find an optimal solution in $O(n^k\log^{\frac{5k}{2}}n)$ steps when $1

Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes

Thomson, Alison; Zhou, Sanming
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.66%
A Frobenius group is a transitive but not regular permutation group such that only the identity element can fix two points. A finite Frobenius group can be expressed as $G = K \rtimes H$ with $K$ a nilpotent normal subgroup. A first-kind $G$-Frobenius graph is a Cayley graph on $K$ with connection set $S$ an $H$-orbit on $K$ generating $K$, where $H$ is of even order or $S$ consists of involutions. We classify all 6-valent first-kind Frobenius circulant graphs such that the underlying kernel $K$ is cyclic. We give optimal gossiping and routing algorithms for such a circulant and compute its forwarding indices, Wiener indices and minimum gossip time. We also prove that its broadcasting time is equal to its diameter plus two or three. We prove that all 6-valent first-kind Frobenius circulants with cyclic kernels are Eisenstein-Jacobi graphs, the latter being Cayley graphs on quotient rings of the ring of Eisenstein-Jacobi integers. We also prove that larger Eisenstein-Jacobi graphs can be constructed from smaller ones as topological covers, and a similar result holds for 6-valent first-kind Frobenius circulants. As a corollary any Eisenstein-Jacobi graph with order congruent to 1 modulo 6 and underlying Eisenstein-Jacobi integer not an associate of a real integer...

uRbAn: A Multipath Routing based Architecture with Energy and Mobility Management for Quality of Service Support in Mobile Ad hoc Networks

Abbas, Ash Mohammad
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/02/2011
Relevância na Pesquisa
16.66%
Designing a wireless node that supports quality of service (QoS) in a mobile ad hoc network is a challenging task. In this paper, we propose an architecture of a wireless node that may be used to form a mobile ad hoc network that supports QoS. We discuss the core functionalities required for such a node and how those functionalities can be incorporated. A feature of our architecture is that the node has the ability to utilize multiple paths, if available, for the provision of QoS. However, in the absence of multiple paths it can utilize the resources provided by a single path between the source and the destination. We follow a modular approach where each module is expanded iteratively. We compare the features of our architecture with the existing architectures proposed in the literature. Our architecture has provisions of energy and mobility management and it can be customized to design a system-on-chip (SoC).; Comment: 6 pages, 6 figures, 1 table

Time-Domain Large Signal Investigation on Dynamic Responses of the GDCC Quarterly Wavelength Shifted Distributed Feedback Semiconductor Laser

Moumen, Abdelkarim; Zatni, Abdelkarim; Elkaaouachi, Abdelhamid; Elyamani, Abdenabi; Bousseta, Hamza
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/06/2013
Relevância na Pesquisa
16.66%
A numerical investigation on the dynamic large-signal analysis using a time-domain traveling wave model of quarter wave-shifted distributed feedback semiconductor lasers diode with a Gaussian distribution of the coupling coefficient (GDCC) is presented. It is found that the single-mode behavior and the more hole-burning effect corrections of quarter wave-shifted distributed feedback laser with large coupling coefficient can be improved significantly by this new proposed light source.; Comment: 6 pages, 6 figures, http://thesai.org/Downloads/Volume3No9/Paper_24-Time-Domain_Large_Signal_Investigation_on_Dynamic_Responses_of_the_GDCC_Quarterly_Wavelength_Shifted_Distributed_Feedback_Semiconductor_Laser.pdf

On Some Expander Graphs and Algebraic Cayley Graphs

Cao, Xiwang
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.66%
Expander graphs have many interesting applications in communication networks and other areas, and thus these graphs have been extensively studied in theoretic computer sciences and in applied mathematics. In this paper, we use reversible difference sets and generalized difference sets to construct more expander graphs, some of them are Ramanujan graphs. Three classes of elementary constructions of infinite families of Ramanujan graphs are provided. It is proved that for every even integer $k>4$, if $2(k+2)=rs$ for two even numbers $r$ and $s$ with $s\geq 4$ and $2s>r\geq s$, or $r\geq 4$ and $2r>s\geq r$, then there exists an $k$-regular Ramanujan graph. As a consequence, there exists an $k$-regular Ramanujan graph with $k=2t^2-2$ for every integer $t>2$. It is also proved that for every odd integer $m$, there is an $(2^{2m-2}+2^{m-1})$-regular Ramanujan graph. These results partially solved the long hanging open question for the existence of $k$-regular Ramanujan graphs for every positive integer $k$.; Comment: 17 pages

Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges

Wang, Fan; Zhang, Heping
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/01/2013
Relevância na Pesquisa
16.66%
Ruskey and Savage asked the following question: Does every matching of $Q_{n}$ for $n\geq2$ extend to a Hamiltonian cycle of $Q_{n}$? J. Fink showed that the question is true for every perfect matching, and solved the Kreweras' conjecture. In this paper we consider the question in hypercubes with faulty edges. We show that every matching $M$ of at most $2n-1$ edges can be extended to a Hamiltonian cycle of $Q_{n}$ for $n\geq2$. Moreover, we can prove that when $n\geq4$ and $M$ is nonempty this result still holds even if $Q_{n}$ has at most $n-1-\lceil\frac{|M|}{2}\rceil$ faulty edges with one exception.; Comment: 16 pages, 10 figures

Network routing on regular directed graphs from spanning factorizations

Dougherty, Randall; Faber, Vance
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/07/2014
Relevância na Pesquisa
16.66%
Networks with a high degree of symmetry are useful models for parallel processor networks. In earlier papers, we defined several global communication tasks (universal exchange, universal broadcast, universal summation) that can be critical tasks when complex algorithms are mapped to parallel machines. We showed that utilizing the symmetry can make network optimization a tractable problem. In particular, we showed that Cayley graphs have the desirable property that certain routing schemes starting from a single node can be transferred to all nodes in a way that does not introduce conflicts. In this paper, we define the concept of spanning factorizations and show that this property can also be used to transfer routing schemes from a single node to all other nodes. We show that all Cayley graphs and many (perhaps all) vertex transitive graphs have spanning factorizations.; Comment: 21 pages

Transpose on vertex symmetric digraphs

Faber, Vance
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/07/2014
Relevância na Pesquisa
16.66%
We discuss transpose (sometimes called universal exchange or all-to-all) on vertex symmetric networks. We provide a method to compare the efficiency of transpose schemes on two different networks with a cost function based on the number processors and wires needed to complete a given algorithm in a given time.; Comment: 12 pages

A Study on Impacts of RTT Inaccuracy on Dynamic Bandwidth Allocation in PON and Solution

Hong, Son Nguyen; Anh, Hao Nguyen; Trong, Thua Huynh
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/10/2014
Relevância na Pesquisa
16.66%
The circle travelling delay between OLT (Optical Line Terminal) and ONU (Optical Network Unit) is one of most important items in dynamic bandwidth allocation (DBA) algorithms in PON, called RTT (Round Trip Time). The RTT is taken into account when OLT assigns the start times for upstream bandwidth grants. In most case, RTT is estimated before making bandwidth allocation decisions in dynamic bandwidth allocation algorithms. If the estimated RTT is incorrect, the bandwidth allocation decisions are not matched with bandwidth requests of channels. Thus, performance of PON can get worse by deviation of RTT. There are several reasons that cause the RTT to be varying, such as processing delay, distance of OLT and ONU, changing in fiber refractive index resulting from temperature drift, and degree of accuracy of RTT estimation methods. In this paper, we evaluate the impacts of RTT inaccuracy on performance of DBA and identify levels of collision and waste of bandwidth. By this way, we propose a method to remedy the performance degradation encountered by the situation; Comment: 10 pages, 4 figures, IJCNC

Using Information Theory to Study the Efficiency and Capacity of Caching in the Computer Networks

Ryabko, Boris
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 13/10/2013
Relevância na Pesquisa
16.66%
Nowadays computer networks use different kind of memory whose speeds and capacities vary widely. There exist methods of a so-called caching which are intended to use the different kinds of memory in such a way that the frequently used data are stored in the faster memory, wheres the infrequent ones are stored in the slower memory. We address the problems of estimating the caching efficiency and its capacity. We define the efficiency and capacity of the caching and suggest a method for their estimation based on the analysis of kinds of the accessible memory.

A protocol for a message system for the tiles of the heptagrid, in the hyperbolic plane

Margenstern, Maurice
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/03/2011
Relevância na Pesquisa
16.66%
This paper introduces a communication system for the tiles of the heptagrid, a tiling of the hyperbolic plane. The method can be extended to other tilings of this plane. The paper focuses on an actual implementation at the programming stage with a short account of two experiments.; Comment: 30 pages, 5 figures

Riemann-Roch Spaces and Linear Network Codes

Hansen, Johan P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/03/2015
Relevância na Pesquisa
16.66%
We construct linear network codes utilizing algebraic curves over finite fields and certain associated Riemann-Roch spaces and present methods to obtain their parameters. In particular we treat the Hermitian curve and the curves associated with the Suzuki and Ree groups all having the maximal number of points for curves of their respective genera. Linear network coding transmits information in terms of a basis of a vector space and the information is received as a basis of a possibly altered vector space. Ralf Koetter and Frank R. Kschischang %\cite{DBLP:journals/tit/KoetterK08} introduced a metric on the set of vector spaces and showed that a minimal distance decoder for this metric achieves correct decoding if the dimension of the intersection of the transmitted and received vector space is sufficiently large. The vector spaces in our construction have minimal distance bounded from below in the above metric making them suitable for linear network coding.; Comment: 8 pages

On the Performance of P2P Network: An Assortment Method

Zhou, Yuqing
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/09/2011
Relevância na Pesquisa
16.66%
P2P systems have grown dramatically in recent years. The most popular type of P2P systems are file sharing networks, which are used to share various types of content over the Internet. Due to the increase in popularity of P2P systems, the network performance of these systems has become a very important issue in the design and realization of these networks. Hence, the performance of the P2P has been improved. This paper will suggest the following methods for the improvement of the P2P systems: Method-1: Improve the P2P routing by using a sandwich technique. Method-2: Improve the search performance by introducing a new search based on the super peer. Method-3: Improving the search by introducing a ranking algorithm based on the knowledge database. The system demonstrates that the methods introduced here have the improved efficiency compared to the previous methodologies. So, the results show that the performance of the P2P systems have been improved by using the above methods, hence the traffic can be reduced.; Comment: 9 pages

Global communication algorithms for Cayley graphs

Faber, Vance
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.66%
We discuss several combinatorial problems that arise when one looks at computational algorithms for highly symmetric networks of processors. More specifically, we are interested in minimal times associated with four communication tasks (defined more precisely below): universal broadcast, every processor has a vector that it wishes to broadcast to all the others; universal accumulation, every processor wishes to receive the sum of all the vectors being sent to it by all the other processors; universal exchange, every processor wishes to exchange a vector with each other processor; and global summation, every processor wants the sum of the vectors in all the processors; Comment: 25 pages

Virtual Backbone Trees for Most Minimal Energy Consumption and Increasing Network Lifetime In WSNs

Saibharath, S.; Aarthi, J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/02/2014
Relevância na Pesquisa
16.66%
Virtual backbone trees have been used for efficient communication between sink node and any other node in the deployed area. But all the proposed virtual backbone trees are not fully energy efficient and EVBTs have few flaws associated with them. In this paper two such virtual backbones are proposed. The motive behind the first algorithm, Most Minimal Energy Virtual Backbone Tree (MMEVBT), is to minimise the energy consumption when packets are transmitted between sink and a target sensor node. The energy consumption is most minimal and optimal and it is shown why it always has minimal energy consumption during any transfer of packet between every node with the sink node. For every node, route path with most minimal energy consumption is identified and a new tree node is elected only when a better minimal energy consumption route is identified for a node to communicate with the sink and vice versa. By moving sink periodically it is ensured the battery of the nodes near sink is not completely drained out. Another backbone construction algorithm is proposed which maximises the network lifetime by increasing the lifetime of all tree nodes. Simulations are done in NS2 to practically test the algorithms and the results are discussed in detail.; Comment: 10 pages...

Stability of the LCD Model

Hou, Zhenting; Tan, Li; Shi, Dinghua
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/06/2008
Relevância na Pesquisa
16.66%
In this paper, first-passage probability of Markov chains is used to get a strict proof of the existence of degree distribution of the LCD model presented by Bollobas (Random Structures and Algorithms 18(2001)). Also, a precise expression of degree distribution is presented.; Comment: 10 pages

Anarchy is free in network creation

Graham, Ronald; Hamilton, Linus; Levavi, Ariel; Loh, Po-Shen
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 11/07/2013
Relevância na Pesquisa
16.66%
The Internet has emerged as perhaps the most important network in modern computing, but rather miraculously, it was created through the individual actions of a multitude of agents rather than by a central planning authority. This motivates the game theoretic study of network formation, and our paper considers one of the most-well studied models, originally proposed by Fabrikant et al. In it, each of N agents corresponds to a vertex, which can create edges to other vertices at a cost of alpha each, for some parameter alpha. Every edge can be freely used by every vertex, regardless of who paid the creation cost. To reflect the desire to be close to other vertices, each agent's cost function is further augmented by the sum total of all (graph theoretic) distances to all other vertices. Previous research proved that for many regimes of the (alpha, N) parameter space, the total social cost (sum of all agents' costs) of every Nash equilibrium is bounded by at most a constant multiple of the optimal social cost. In algorithmic game theoretic nomenclature, this approximation ratio is called the price of anarchy. In our paper, we significantly sharpen some of those results, proving that for all constant non-integral alpha > 2, the price of anarchy is in fact 1+o(1)...

Cyclotomic graphs and perfect codes

Zhou, Sanming
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.66%
We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of $\mathbb{Z}[\zeta_m]/A$, with connection sets $\{\pm (\zeta_m^i + A): 0 \le i \le m-1\}$ and $\{\pm (\zeta_m^i + A): 0 \le i \le \phi(m) - 1\}$, respectively, where $\zeta_m$ ($m \ge 2$) is an $m$th primitive root of unity, $A$ a nonzero ideal of $\mathbb{Z}[\zeta_m]$, and $\phi$ Euler's totient function. We call them the $m$th cyclotomic graph and the second kind $m$th cyclotomic graph, and denote them by $G_{m}(A)$ and $G^*_{m}(A)$, respectively. We give a necessary and sufficient condition for $D/A$ to be a perfect $t$-code in $G^*_{m}(A)$ and a necessary condition for $D/A$ to be such a code in $G_{m}(A)$, where $t \ge 1$ is an integer and $D$ an ideal of $\mathbb{Z}[\zeta_m]$ containing $A$. In the case when $m = 3, 4$, $G_m((\alpha))$ is known as an Eisenstein-Jacobi or Gaussian network, respectively, and we obtain necessary conditions for $(\beta)/(\alpha)$ to be a perfect $t$-code in $G_m((\alpha))$, where $0 \ne \alpha, \beta \in \mathbb{Z}[\zeta_m]$ with $\beta$ dividing $\alpha$. In the literature such conditions are known to be sufficient when $m=4$ and $m=3$ under an additional condition. We give a classification of all first kind Frobenius circulants of valency $2p$ and prove that they are all $p$th cyclotomic graphs...

Improvement/Extension of Modular Systems as Combinatorial Reengineering (Survey)

Levin, Mark Sh.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 17/04/2013
Relevância na Pesquisa
16.66%
The paper describes development (improvement/extension) approaches for composite (modular) systems (as combinatorial reengineering). The following system improvement/extension actions are considered: (a) improvement of systems component(s) (e.g., improvement of a system component, replacement of a system component); (b) improvement of system component interconnection (compatibility); (c) joint improvement improvement of system components(s) and their interconnection; (d) improvement of system structure (replacement of system part(s), addition of a system part, deletion of a system part, modification of system structure). The study of system improvement approaches involve some crucial issues: (i) scales for evaluation of system components and component compatibility (quantitative scale, ordinal scale, poset-like scale, scale based on interval multiset estimate), (ii) evaluation of integrated system quality, (iii) integration methods to obtain the integrated system quality. The system improvement/extension strategies can be examined as seleciton/combination of the improvement action(s) above and as modification of system structure. The strategies are based on combinatorial optimization problems (e.g., multicriteria selection, knapsack problem...