Abstract: We design and implement a multicost impairment- aware routing and wavelength assignment algorithm for online traffic. In transparent optical networks the quality of a transmission degrades due to physical layer impairments. To serve a connection, the proposed algorithm finds a path and a free wavelength (a lightpath) that has acceptable signal quality performance by estimating a quality of transmission measure, called the Q factor. We take into account channel utilization in the network, which changes as new connections are established or released, in order to calculate the noise variances that correspond to physical impairments on the links. These, along with the time invariant eye impairment penalties of all candidate network paths, form the inputs to the algorithm. The multicost algorithm finds a set of so called non-dominated Q paths from the given source to the given destination. Various objective functions are then evaluated in order to choose the optimal lightpath to serve the connection. The proposed algorithm combines the strength of multicost optimization with low execution time, making it appropriate for serving online connections.
Abstract: Motivated by the wavelength assignment problem in WDM optical networks, we study path coloring problems in graphs. Given a set of paths P on a graph G, the path coloring problem is to color the paths of P so that no two paths traversing the same edge of G are assigned the same color and the total number of colors used is minimized. The problem has been proved to be NP-hard even for trees and rings.
Using optimal solutions to fractional path coloring, a natural relaxation of path coloring, on which we apply a randomized rounding technique combined with existing coloring algorithms, we obtain new upper bounds on the minimum number of colors sufficient to color any set of paths on any graph. The upper bounds are either existential or constructive.
The existential upper bounds significantly improve existing ones provided that the cost of the optimal fractional path coloring is sufficiently large and the dilation of the set of paths is small. Our algorithmic results include improved approximation algorithms for path coloring in rings and in bidirected trees. Our results extend to variations of the original path coloring problem arizing in multifiber WDM optical networks.
Abstract: We design and implement various algorithms for
solving the static RWA problem with the objective of minimizing
the maximum number of requested wavelengths based on LP
relaxation formulations. We present a link formulation, a path
formulation and a heuristic that breaks the problem in the two
constituent subproblems and solves them individually and
sequentially. The flow cost functions that are used in these
formulations result in providing integer optimal solutions despite
the absence of integrality constraints for a large subset of RWA
input instances, while also minimizing the total number of used
wavelengths. We present a random perturbation technique that is
shown to increase the number of instances for which we find
integer solutions, and we also present appropriate iterative fixing
and rounding methods to be used when the algorithms do not yield
integer solutions. We comment on the number of variables and
constraints these formulations require and perform extensive
simulations to compare their performance to that of a typical minmax
congestion formulation.
Abstract: We investigate the existence of optimal tolls for atomic symmetric
network congestion games with unsplittable traffic and arbitrary non-negative and
non-decreasing latency functions.We focus on pure Nash equilibria and a natural
toll mechanism, which we call cost-balancing tolls. A set of cost-balancing tolls
turns every path with positive traffic on its edges into a minimum cost path. Hence
any given configuration is induced as a pure Nash equilibrium of the modified
game with the corresponding cost-balancing tolls. We show how to compute in
linear time a set of cost-balancing tolls for the optimal solution such that the total
amount of tolls paid by any player in any pure Nash equilibrium of the modified
game does not exceed the latency on the maximum latency path in the optimal
solution. Our main result is that for congestion games on series-parallel networks
with increasing latencies, the optimal solution is induced as the unique pure Nash
equilibrium of the game with the corresponding cost-balancing tolls. To the best
of our knowledge, only linear congestion games on parallel links were known to
admit optimal tolls prior to this work. To demonstrate the difficulty of computing
a better set of optimal tolls, we show that even for 2-player linear congestion
games on series-parallel networks, it is NP-hard to decide whether the optimal
solution is the unique pure Nash equilibrium or there is another equilibrium of
total cost at least 6/5 times the optimal cost.
Abstract: Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three facets of direct routing: (i) Algorithms. We present a polynomial time greedy algorithm for arbitrary direct routing problems whch is worst-case optimal, i.e., there exist instances for which no direct routing algorithm is better than the greedy. We apply variants of this algorithm to commonly used network topologies. In particular, we obtain near-optimal routing time using for the tree and d-dimensional mesh, given arbitrary sources and destinations; for the butterfly and the hypercube, the same result holds for random destinations. (ii) Complexity. By a reduction from Vertex Coloring, we show that Direct Routing is inapproximable, unless P=NP. (iii) Lower Bounds for Buffering. We show the existence of routing problems which cannot be solved efficiently with direct routing. To solve these problems, any routing algorithm needs buffers. We give nontrivial lower bounds on such buffering requirements for general routing algorithms.
Abstract: This paper deals with early obstacles recognition in wireless sensor networks under various traffic
patterns. In the presence of obstacles, the efficiency of routing algorithms is increased by voluntarily avoiding some regions in the vicinity of obstacles, areas which we call dead-ends. In this paper, we first propose a fast convergent routing algorithm with proactive dead-end detection together with a formal definition and description of dead-ends. Secondly, we present a generalization of this algorithm which improves performances in all to many and all to all traffic patterns. In a third part we prove that this algorithm produces paths that are optimal up to a
constant factor of 2ð+1. In a fourth part we consider the reactive version of the algorithm which is an extension of a previously known early obstacle detection algorithm. Finally we give experimental results to illustrate the efficiency of our algorithms in different scenarios.
Abstract: We call radiation at a point of a wireless network the total amount of electromagnetic quantity (energy or power density) the point is exposed to. The impact of radiation can be high and we believe it is worth studying and control; towards radiation aware wireless networking we take (for the first time in the study of this aspect) a distributed computing, algorithmic approach. We exemplify this line of research by focusing on sensor networks, studying the minimum radiation path problem of finding the lowest radiation trajectory of a person moving from a source to a destination point in the network region. For this problem, we sketch the main ideas behind a linear program that can provide a tight approximation of the optimal solution, and then we discuss three heuristics that can lead to low radiation paths. We also plan to investigate the impact of diverse node mobility to the heuristics' performance.
Abstract: Intuitively, Braess's paradox states that destroying a part
of a network may improve the common latency of sel sh
ows at Nash
equilibrium. Such a paradox is a pervasive phenomenon in real-world
networks. Any administrator, who wants to improve equilibrium delays
in sel sh networks, is facing some basic questions: (i) Is the network
paradox-ridden? (ii) How can we delete some edges to optimize equilibrium
ow delays? (iii) How can we modify edge latencies to optimize
equilibrium
ow delays?
Unfortunately, such questions lead to NP-hard problems in general. In
this work, we impose some natural restrictions on our networks, e.g.
we assume strictly increasing linear latencies. Our target is to formulate
ecient algorithms for the three questions above.We manage to provide:
{ A polynomial-time algorithm that decides if a network is paradoxridden,
when latencies are linear and strictly increasing.
{ A reduction of the problem of deciding if a network with arbitrary
linear latencies is paradox-ridden to the problem of generating all
optimal basic feasible solutions of a Linear Program that describes
the optimal trac allocations to the edges with constant latency.
{ An algorithm for nding a subnetwork that is almost optimal wrt
equilibrium latency. Our algorithm is subexponential when the number
of paths is polynomial and each path is of polylogarithmic length.
{ A polynomial-time algorithm for the problem of nding the best
subnetwork, which outperforms any known approximation algorithm
for the case of strictly increasing linear latencies.
{ A polynomial-time method that turns the optimal
ow into a Nash
ow by deleting the edges not used by the optimal
ow, and performing
minimal modi cations to the latencies of the remaining ones.
Our results provide a deeper understanding of the computational complexity
of recognizing the Braess's paradox most severe manifestations,
and our techniques show novel ways of using the probabilistic method
and of exploiting convex separable quadratic programs.
Abstract: Intuitively, Braess’s paradox states that destroying a part of a network may improve the common latency of selfish flows at Nash equilibrium. Such a paradox is a pervasive phenomenon in real-world networks. Any administrator who wants to improve equilibrium delays in selfish networks, is facing some basic questions:
– Is the network paradox-ridden?
– How can we delete some edges to optimize equilibrium flow delays?
– How can we modify edge latencies to optimize equilibrium flow delays?
Unfortunately, such questions lead to View the MathML sourceNP-hard problems in general. In this work, we impose some natural restrictions on our networks, e.g. we assume strictly increasing linear latencies. Our target is to formulate efficient algorithms for the three questions above. We manage to provide:
– A polynomial-time algorithm that decides if a network is paradox-ridden, when latencies are linear and strictly increasing.
– A reduction of the problem of deciding if a network with (arbitrary) linear latencies is paradox-ridden to the problem of generating all optimal basic feasible solutions of a Linear Program that describes the optimal traffic allocations to the edges with constant latency.
– An algorithm for finding a subnetwork that is almost optimal wrt equilibrium latency. Our algorithm is subexponential when the number of paths is polynomial and each path is of polylogarithmic length.
– A polynomial-time algorithm for the problem of finding the best subnetwork which outperforms any known approximation for the case of strictly increasing linear latencies.
– A polynomial-time method that turns the optimal flow into a Nash flow by deleting the edges not used by the optimal flow, and performing minimal modifications on the latencies of the remaining ones.
Our results provide a deeper understanding of the computational complexity of recognizing the most severe manifestations of Braess’s paradox, and our techniques show novel ways of using the probabilistic method and of exploiting convex separable quadratic programs.
Abstract: In this work we study energy efficient routing strategies
for wireless ad-hoc networks. In this kind of networks,
energy is a scarce resource and its conservation
and efficient use is a major issue. Our strategy follows
the multi-cost routing approach, according to which a
cost vector of various parameters is assigned to each
link. The parameters of interest are the number of hops
on a path, and the residual energy and the transmission
power of the nodes on the path. These parameters
are combined in various optimization functions,
corresponding to different routing algorithms, for selecting
the optimalpath. We evaluate the routing algorithms
proposed in a number of scenarios, with respect
to energy consumption, throughput and other performance
parameters of interest. From the experiments
conducted we conclude that routing algorithms that take
into account energy related parameters, increase the
lifetime of the network, while achieving better performance
than other approaches, such as minimum hop
routing.
Abstract: Many efforts have been done in the last years to model public transport timetables in order to
find optimal routes. The proposed models can be classified into two types: those representing the
timetable as an array, and those representing it as a graph. The array-based models have been
shown to be very effective in terms of query time, while the graph-based models usually answer
queries by computing shortest paths, and hence they are suitable to be used in combination with
speed-up techniques developed for road networks.
In this paper, we focus on the dynamic behavior of graph-based models considering the case
where transportation systems are subject to delays with respect to the given timetable. We
make three contributions: (i) we give a simplified and optimized update routine for the wellknown
time-expanded model along with an engineered query algorithm; (ii) we propose a new
graph-based model tailored for handling dynamic updates; (iii) we assess the effectiveness of
the proposed models and algorithms by an experimental study, which shows that both models
require negligible update time and a query time which is comparable to that required by some
array-based models.
Abstract: A fundamental approach in finding efficiently best routes or optimal itineraries in traffic information
systems is to reduce the search space (part of graph visited) of the most commonly used
shortest path routine (Dijkstra¢s algorithm) on a suitably defined graph. We investigate reduction
of the search space while simultaneously retaining data structures, created during a preprocessing
phase, of size linear (i.e., optimal) to the size of the graph. We show that the search space of
Dijkstra¢s algorithm can be significantly reduced by extracting geometric information from a given
layout of the graph and by encapsulating precomputed shortest-path information in resulted geometric
objects (containers). We present an extensive experimental study comparing the impact of
different types of geometric containers using test data from real-world traffic networks. We also
present new algorithms as well as an empirical study for the dynamic case of this problem, where
edge weights are subject to change and the geometric containers have to be updated and show that
our new methods are two to three times faster than recomputing everything from scratch. Finally,
in an appendix, we discuss the software framework that we developed to realize the implementations
of all of our variants of Dijkstra¢s algorithm. Such a framework is not trivial to achieve as our
goal was to maintain a common code base that is, at the same time, small, efficient, and flexible,
as we wanted to enhance and combine several variants in any possible way.
Abstract: In this work we study the implementation of multicost rout-
ing in a distributed way in wireless mobile ad hoc networks.
In contrast to traditional single-cost routing, where each
path is characterized by a scalar, in multicost routing a
vector of cost parameters is assigned to each network link,
from which the cost vectors of candidate paths are calcu-
lated. These parameters are combined in various optimiza-
tion functions, corresponding to different routing algorithms,
for selecting the optimalpath. Up until now the performance
of multicost and multi-constrained routing in wireless ad hoc
networks has been evaluated either at a theoretical level or
by assuming that nodes are static and have full knowledge
of the network topology and nodes� state. In the present
paper we assess the performance of multicost routing based
on energy-related parameters in mobile ad hoc networks by
embedding its logic in the Dynamic Source Routing (DSR)
algorithm, which is a well-known fully distributed routing
algorithm. We use simulations to compare the performance
of the multicost-DSR algorithm to that of the original DSR
algorithm and examine their behavior under various node
mobility scenarios. The results confirm that the multicost-
DSR algorithm improves the performance of the network in
comparison to the original DSR algorithm in terms of energy efficiency. The multicost-DSR algorithm enhances the
performance of the network not only by reducing energy
consumption overall in the network, but also by spreading
energy consumption more uniformly across the network, pro
longing the network lifetime and reducing the packet drop
probability. Furthermore the delay suffered by the packets
reaching their destination for the case of the multicost-DSR
algorithm is shown to be lower than in the case of the orig
inal DSR algorithm.
Abstract: The problem of robust line planning requests for a set of
origin-destination paths (lines) along with their frequencies in an underlying
railway network infrastructure, which are robust to
uctuations of
real-time parameters of the solution.
In this work, we investigate a variant of robust line planning stemming
from recent regulations in the railway sector that introduce competition
and free railway markets, and set up a new application scenario: there is
a (potentially large) number of line operators that have their lines xed
and operate as competing entities struggling to exploit the underlying
network infrastructure via frequency requests, while the management of
the infrastructure itself remains the responsibility of a single (typically
governmental) entity, the network operator.
The line operators are typically unwilling to reveal their true incentives.
Nevertheless, the network operator would like to ensure a fair (or, socially
optimal) usage of the infrastructure, e.g., by maximizing the (unknown to
him) aggregate incentives of the line operators. We show that this can be
accomplished in certain situations via a (possibly anonymous) incentivecompatible
pricing scheme for the usage of the shared resources, that is
robust against the unknown incentives and the changes in the demands
of the entities. This brings up a new notion of robustness, which we
call incentive-compatible robustness, that considers as robustness of the
system its tolerance to the entities' unknown incentives and elasticity
of demands, aiming at an eventual stabilization to an equilibrium point
that is as close as possible to the social optimum.
Abstract: In this paper we present a multicost algorithm for the joint
time scheduling of the communication and computation
resources that will be used by a task. The proposed
algorithm selects the computation resource to execute the
task, determines the path to route the input data, and finds
the starting times for the data transmission and the task
execution, performing advance reservations. We initially
present an optimal scheme of non-polynomial complexity
and by appropriately pruning the set of candidate paths we
also give a heuristic algorithm of polynomial complexity. We
evaluate the performance of our algorithm and compare it to
that of algorithms that handle only the computation or
communication part of the problem separately. We show that
in a Grid network where the tasks are CPU- and dataintensive
important performance benefits can be obtained by
jointly optimizing the use of the communication and
computation resources.
Abstract: In this work we study the combination of multicost
routing and adjustable transmission power in wireless
ad hoc networks, so as to obtain dynamic energy- and
interference-efficient routes to optimize network performance.
In multi-cost routing, a vector of cost parameters is
assigned to each network link, from which the cost vectors
of candidate paths are calculated. Only at the end these
parameters are combined in various optimization functions,
corresponding to different routing algorithms, for selecting
the optimalpath. The multi-cost routing problem is a
generalization of the multi-constrained problem, where no
constraints exist, and is also significantly more powerful
than single-cost routing. Since energy is an important
limitation of wireless communications, the cost parameters
considered are the number of hops, the interference caused,
the residual energy and the transmission power of the
nodes on the path; other parameters could also be included,
as desired. We assume that nodes can use power control to
adjust their transmission power to the desired level. The
experiments conducted show that the combination of multicost
routing and adjustable transmission power can lead to
reduced interference and energy consumption, improving
network performance and lifetime.
Abstract: In translucent (or managed reach) WDM optical
networks, regenerators are employed at specific nodes. Some of
the connections in such networks are routed transparently, while
others have to go through a sequence of 3R regenerators that serve
as “refueling stations” to restore their quality of transmission
(QoT). We extend an online multicost algorithm for transparent
networks presented in our previous study [1], to obtain an IA-RWA
algorithm that works in translucent networks and makes use,
when required, of the regenerators present at certain locations
of the network. To characterize a path, the algorithm uses a
multicost formulation with several cost parameters, including the
set of available wavelengths, the length of the path, the number of
regenerators used, and noise variance parameters that account for
the physical layer impairments. Given a new connection request
and the current utilization state of the network, the algorithm calculates
a set of non dominated candidate paths, meaning that any
path in this set is not inferior with respect to all cost parameters
than any other path. This set consists of all the cost-effective (in
terms of the domination relation) and feasible (in terms of QoT)
lightpaths for the given source-destination pair, including all the
possible combinations for the utilization of available regenerators
of the network. An optimization function or policy is then applied
to this set in order to select the optimal lightpath. Different optimization
policies correspond to different IA-RWA algorithms.
We propose and evaluate several optimization policies, such as the
most used wavelength, the best quality of transmission, the least
regeneration usage, or a combination of these rules. Our results
indicate that in a translucent network the employed IA-RWA
algorithm has to consider all problem parameters, namely, the
QoT of the lightpaths, the utilization of wavelengths and the
availability of regenerators, to efficiently serve the online traffic.
Abstract: A key problem in Grid networks is how to efficiently manage the available infrastructure, in order to
satisfy user requirements and maximize resource utilization. This is in large part influenced by the
algorithms responsible for the routing of data and the scheduling of tasks. In this paper,wepresent several
multi-cost algorithms for the joint scheduling of the communication and computation resources that
will be used by a Grid task. We propose a multi-cost scheme of polynomial complexity that performs
immediate reservations and selects the computation resource to execute the task and determines the
path to route the input data. Furthermore, we introduce multi-cost algorithms that perform advance
reservations and thus also find the starting times for the data transmission and the task execution. We
initially present an optimal scheme of non-polynomial complexity and by appropriately pruning the set
of candidate paths we also give a heuristic algorithm of polynomial complexity. Our performance results
indicate that in a Grid network in which tasks are either CPU- or data-intensive (or both), it is beneficial
for the scheduling algorithm to jointly consider the computational and communication problems. A
comparison between immediate and advance reservation schemes shows the trade-offs with respect to
task blocking probability, end-to-end delay and the complexity of the algorithms.
Abstract: We propose a class of novel energy-efficient multi-cost routing algorithms for wireless mesh networks, and evaluate their performance. In multi-cost routing, a vector of cost parameters is assigned to each network link, from which the cost vectors of candidate paths are calculated using appropriate operators. In the end these parameters are combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimalpath. We evaluate the performance of the proposed energy-aware multi-cost routing algorithms under two models. In the network evacuation model, the network starts with a number of packets that have to be transmitted and an amount of energy per node, and the objective is to serve the packets in the smallest number of steps, or serve as many packets as possible before the energy is depleted. In the dynamic one-to-one communication model, new data packets are generated continuously and nodes are capable of recharging their energy periodically, over an infinite time horizon, and we are interested in the maximum achievable steady-state throughput, the packet delay, and the energy consumption. Our results show that energy-aware multi-cost routing increases the lifetime of the network and achieves better overall network performance than other approaches.
Abstract: In this work we study the combination of
multicost routing and adjustable transmission power
in wireless ad-hoc networks, so as to obtain dynamic
energy and interference-efficient routes to optimize network performance. In multi-cost routing, a vector of
cost parameters is assigned to each network link, from
which the cost vectors of candidate paths are calcu-
lated. Only at the end are these parameters combined in
various optimization functions, corresponding to different routing algorithms, for selecting the optimalpath.
The multi-cost routing problem is a generalization of
the multi-constrained problem, where no constraints exist, and is also significantly more powerful than single-
cost routing. Since energy is an important limitation of
wireless communications, the cost parameters consid
ered are the number of hops, the interference caused,
the residual energy and the transmission power of the
nodes on the path; other parameters could also be in
cluded, as desired.We assume that nodes can use power
control to adjust their transmission power to the desired
level. The experiments conducted show that the com
bination of multi-cost routing and adjustable transmis sion power can lead to reduced interference and energy
consumption, improving network performance and life-
time.
Abstract: We provide an improved FPTAS for multiobjective shortest paths—a fundamental (NP-hard) problem in multiobjective optimization—along with a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives. We show how these results can be used to obtain better approximate solutions to three related problems, multiobjective constrained [optimal] path and non-additive shortest path, that have important applications in QoS routing and in traffic optimization. We also show how to obtain a FPTAS to a natural generalization of the weighted multicommodity flow problem with elastic demands and values that models several realistic scenarios in transportation and communication networks.
Abstract: We propose local mechanisms for efficiently marking the broader network region around obstacles, for data propagation to early enough avoid them towards near-optimal routing paths. In particular, our methods perform an online identification of sensors lying near obstacle boundaries,which then appropriately emit beacon messages in the network towards establishing efficient obstacle avoidance paths. We provide a variety of beacon dissemination schemes that satisfy different trade-offs between protocol overhead and performance. Compared to greedy, face routing and trustbased methods in the state of the art, our methods achieve significantly shorter propagation paths, while introducing much lower overhead and converging faster to near-optimality.
Abstract: Geographic routing scales well in sensor networks, mainly
due to its stateless nature. Still, most of the algorithms are
concerned with finding some path, while the optimality of
the path is difficult to achieve. In this paper we are presenting
a novel geographic routing algorithm with obstacle
avoidance properties. It aims at finding the optimalpath
from a source to a destination when some areas of the network
are unavailable for routing due to low local density or
obstacle presence. It locally and gradually with time (but,
as we show, quite fast) evaluates and updates the suitability
of the previously used paths and ignores non optimalpaths
for further routing. By means of extensive simulations, we
are comparing its performance to existing state of the art
protocols, showing that it performs much better in terms of
path length thus minimizing latency, space, overall traffic
and energy consumption.
Abstract: We propose local mechanisms for efficiently marking the
broader network region around obstacles, for data propagation
to early enough avoid them towards near-optimal
routing paths. In particular, our methods perform an online
identification of sensors lying near obstacle boundaries,
which then appropriately emit beacon messages in the network
towards establishing efficient obstacle avoidance paths.
We provide a variety of beacon dissemination schemes that
satisfy different trade-offs between protocol overhead and
performance. Compared to greedy, face routing and trustbased
methods in the state of the art, our methods achieve
significantly shorter propagation paths, while introducing
much lower overhead and converging faster to near-optimality.
Abstract: The non-additive shortest path (NASP) problem asks for
finding an optimalpath that minimizes a certain multi-attribute nonlinear
cost function. In this paper, we consider the case of a non-linear
convex and non-decreasing function on two attributes.We present an efficient
polynomial algorithm for solving a Lagrangian relaxation of NASP.
We also present an exact algorithm that is based on new heuristics we
introduce here, and conduct a comparative experimental study with synthetic
and real-world data that demonstrates the quality of our approach.
Abstract: In routing games, the network performance at equilibrium can be significantly improved if we remove some edges from the network. This counterintuitive fact, widely known as Braess's paradox, gives rise to the (selfish) network design problem, where we seek to recognize routing games suffering from the paradox, and to improve the equilibrium performance by edge removal. In this work, we investigate the computational complexity and the approximability of the network design problem for non-atomic bottleneck routing games, where the individual cost of each player is the bottleneck cost of her path, and the social cost is the bottleneck cost of the network. We first show that bottleneck routing games do not suffer from Braess's paradox either if the network is series-parallel, or if we consider only subpath-optimal Nash flows. On the negative side, we prove that even for games with strictly increasing linear latencies, it is NP-hard not only to recognize instances suffering from the paradox, but also to distinguish between instances for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA is as large as \Omega(n^{0.121}) and cannot improve by edge removal. Thus, the network design problem for such games is NP-hard to approximate within a factor of O(n^{0.121-\eps}), for any constant \eps > 0. On the positive side, we show how to compute an almost optimal subnetwork w.r.t. the bottleneck cost of its worst Nash flow, when the worst Nash flow in the best subnetwork routes a non-negligible amount of flow on all used edges. The running time is determined by the total number of paths, and is quasipolynomial when the number of paths is quasipolynomial.
Abstract: The problem of robust line planning requests for a set of
origin-destination paths (lines) along with their tra±c rates (frequencies)
in an underlying railway network infrastructure, which are robust to
°uctuations of real-time parameters of the solution.
In this work, we investigate a variant of robust line planning stemming
from recent regulations in the railway sector that introduce competition
and free railway markets, and set up a new application scenario: there is
a (potentially large) number of line operators that have their lines ¯xed
and operate as competing entities struggling to exploit the underlying
network infrastructure via frequency requests, while the management of
the infrastructure itself remains the responsibility of a single (typically
governmental) entity, the network operator.
The line operators are typically unwilling to reveal their true incentives.
Nevertheless, the network operator would like to ensure a fair (or, socially
optimal) usage of the infrastructure, e.g., by maximizing the (unknown to
him) aggregate incentives of the line operators. We show that this can be
accomplished in certain situations via a (possibly anonymous) incentive-
compatible pricing scheme for the usage of the shared resources, that is
robust against the unknown incentives and the changes in the demands
of the entities. This brings up a new notion of robustness, which we
call incentive-compatible robustness, that considers as robustness of the
system its tolerance to the entities' unknown incentives and elasticity
of demands, aiming at an eventual stabilization to an equilibrium point
that is as close as possible to the social optimum.
Abstract: A key problem in networks that support advance reservations is the routing and time scheduling of connections with flexible starting time and known data transfer size. In this paper we present a multicost routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the data should start and end transmission at each link so as to minimize the reception time at the destination, or optimize some other performance criterion. The utilization profiles of the network links, the link propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm. We initially present a scheme of non-polynomial complexity to compute a set of so called non-dominated candidate paths, from which the optimalpath can be found. We then propose two mechanisms to appropriately prune the set of candidate paths in order to find multicost routing and scheduling algorithms of polynomial complexity. We examine the performance of the algorithms in the special case of an Optical Burst Switched network. Our results indicate that the proposed polynomial-time algorithms have performance that is very close to that of the optimal algorithm. We also study the effects network propagation delays and link-state update policies have on performance.
Abstract: A key problem in networks that support advance reservations is the routing and time scheduling of
connections with flexible starting time and known data transfer size. In this paper we present a multicost
routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the
data should start and end transmission at each link so as to minimize the reception time at the destination,
or optimize some other performance criterion. The utilization profiles of the network links, the link
propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm.
We initially present a scheme of non-polynomial complexity to compute a set of so-called non-dominated
candidate paths, from which the optimalpath can be found. We then propose two mechanisms to
appropriately prune the set of candidate paths in order to find multicost routing and scheduling algorithms of
polynomial complexity. We examine the performance of the algorithms in the special case of an Optical
Burst Switched network. Our results indicate that the proposed polynomial time algorithms have performance that is very close to that of the optimal algorithm. We also study the effects network
propagation delays and link-state update policies have on performance.
Abstract: A key problem in networks that support advance
reservations is the routing and time scheduling of connections
with flexible starting time. In this paper we present a multicost
routing and scheduling algorithm for selecting the path to be
followed by such a connection and the time the data should start
so as to minimize the reception time at the destination, or some
other QoS requirement. The utilization profiles of the network
links, the link propagation delays, and the parameters of the
connection to be scheduled form the inputs to the algorithm. We
initially present a scheme of non-polynomial complexity to
compute a set of so-called non-dominated candidate paths, from
which the optimalpath can be found. By appropriately pruning
the set of candidate paths using path pseudo-domination
relationships, we also find multicost routing and scheduling
algorithms of polynomial complexity. We examine the
performance of the algorithms in the special case of an Optical
Burst Switched network. Our results indicate that the proposed
polynomial time algorithms have performance that it is very close
to that of the optimal algorithm.
Abstract: One of the most eminent problems in sensor networks is the
routing of data to a central destination in a robust and e±cient manner.
In this work we propose a new scalable protocol for propagating infor-
mation about a sensed event towards a receiving center. Using only local
information and total absence of coordination between sensors our pro-
tocol achieves to propagate the sensed data to a receiving center by ac-
tivating only those nodes that lie very close to the optimalpath between
the source of the event and the destination, resulting in low activation of
the network's sensors. Thus the protocol is very energy e±cient. Further-
more, our protocol is robust as it manages to propagate the information
even when sensors fail with certain probability.
Abstract: We consider the important problem of energy balanced data propagation in wireless sensor networks and we extend and generalize
previous works by allowing adaptive energy assignment. We consider the data gathering problem where data are generated by the sensors and
must be routed toward a unique sink. Sensors route data by either sending the data directly to the sink or in a multi-hop fashion by delivering
the data to a neighbouring sensor. Direct and neighbouring transmissions require different levels of energy consumption. Basically, the protocols balance the energy consumption among the sensors by computing the adequate ratios of direct and neighbouring transmissions. An abstract model of energy dissipation as a random walk is proposed, along with rigorous performance analysis techniques. Two efficient distributed algorithms are presented and analysed, by both rigorous means and simulation.
The first one is easy to implement and fast to execute. The protocol assumes that sensors know a-priori the rate of data they generate.
The sink collects and processes all these information in order to compute the relevant value of the protocol parameter. This value is transmitted
to the sensors which individually compute their optimal ratios of direct and neighbouring transmissions. The second protocol avoids the necessary a-priori knowledge of the data rate generated by sensors by inferring the relevant information from the observation of the data paths.
Furthermore, this algorithm is based on stochastic estimation methods and is adaptive to environmental changes.
Abstract: We give an overview of models and efficient algorithms for
optimally solving timetable information problems like “given a departure
and an arrival station as well as a departure time, which is the
connection that arrives as early as possible at the arrival station?” Two
main approaches that transform the problems into shortest path problems
are reviewed, including issues like the modeling of realistic details
(e.g., train transfers) and further optimization criteria (e.g., the number
of transfers). An important topic is also multi-criteria optimization,
where in general all attractive connections with respect to several criteria
shall be determined. Finally, we discuss the performance of the described
algorithms, which is crucial for their application in a real system.
Abstract: We give an overview of models and efficient algorithms for optimally solving timetable information problems like “given a departure and an arrival station as well as a departure time, which is the connection that arrives as early as possible at the arrival station?” Two main approaches that transform the problems into shortest path problems are reviewed, including issues like the modeling of realistic details (e.g., train transfers) and further optimization criteria (e.g., the number of transfers). An important topic is also multi-criteria optimization, where in general all attractive connections with respect to several criteria shall be determined. Finally, we discuss the performance of the described algorithms, which is crucial for their application in a real system.
Abstract: We study computationally hard combinatorial problems arising from the important engineering question of how to maximize the number of connections that can be simultaneously served in a WDM optical network. In such networks, WDM technology can satisfy a set of connections by computing a route and assigning a wavelength to each connection so that no two connections routed through the same fiber are assigned the same wavelength. Each fiber supports a limited number of w wavelengths and in order to fully exploit the parallelism provided by the technology, one should select a set connections of maximum cardinality which can be satisfied using the available wavelengths. This is known as the maximum routing and path coloring problem (maxRPC).
Our main contribution is a general analysis method for a class of iterative algorithms for a more general coloring problem. A lower bound on the benefit of such an algorithm in terms of the optimal benefit and the number of available wavelengths is given by a benefit-revealing linear program. We apply this method to maxRPC in both undirected and bidirected rings to obtain bounds on the approximability of several algorithms. Our results also apply to the problem maxPC where paths instead of connections are given as part of the input. We also study the profit version of maxPC in rings where each path has a profit and the objective is to satisfy a set of paths of maximum total profit.
