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)

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

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

16.66%

#Mathematics - Metric Geometry#Computer Science - Data Structures and Algorithms#Mathematics - Optimization and Control#68M10, 05C40

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

Link permanente para citações:

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

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...

Link permanente para citações:

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

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

Link permanente para citações:

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

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

Link permanente para citações:

## On Some Expander Graphs and Algebraic Cayley Graphs

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

Link permanente para citações:

## Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 14/01/2013

Relevância na Pesquisa

16.66%

#Mathematics - Combinatorics#Mathematics - Optimization and Control#05C38, 05C45, 05C70, 68M10, 68M15, 68R10

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

Link permanente para citações:

## Network routing on regular directed graphs from spanning factorizations

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

Link permanente para citações:

## Transpose on vertex symmetric digraphs

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

Link permanente para citações:

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

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

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 13/10/2013

Relevância na Pesquisa

16.66%

#Computer Science - Information Theory#Computer Science - Networking and Internet Architecture#68M10 Network design and communication

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.

Link permanente para citações:

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

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

Link permanente para citações:

## Riemann-Roch Spaces and Linear Network Codes

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

Link permanente para citações:

## On the Performance of P2P Network: An Assortment Method

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

Link permanente para citações:

## Global communication algorithms for Cayley graphs

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

Link permanente para citações:

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

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...

Link permanente para citações:

## Stability of the LCD Model

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

Link permanente para citações:

## Anarchy is free in network creation

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 11/07/2013

Relevância na Pesquisa

16.66%

#Mathematics - Combinatorics#Computer Science - Computer Science and Game Theory#05C35, 91A06, 68M10

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)...

Link permanente para citações:

## Cyclotomic graphs and perfect codes

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...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 17/04/2013

Relevância na Pesquisa

16.66%

#Computer Science - Artificial Intelligence#68T20, 68M10, 90B50, 90B40, 90C27, 90C29, 90C59, 93B51#J.6#I.2#I.2.8#A.1#C.2.1

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...

Link permanente para citações: