  Communication networks are used today everywhere and on every scale: starting
from small Internet of Things (IoT) networks at home, via campus and enterprise
networks, and up to tier-one networks of Internet providers. Accordingly,
network devices should support a plethora of tasks with highly heterogeneous
characteristics in terms of processing time, bandwidth energy consumption,
deadlines and so on. Evaluating these characteristics and the amount of
currently available resources for handling them requires analyzing all the
arriving inputs, gathering information from numerous remote devices, and
integrating all this information. Performing all these tasks in real time is
very challenging in today's networking environments, which are characterized by
tight bounds on the latency, and always-increasing data rates. Hence, network
algorithms should typically make decisions under uncertainty.
  This work addresses optimizing performance in heterogeneous and uncertain
networking environments. We begin by detailing the sources of heterogeneity and
uncertainty and show that uncertainty appears in all layers of network design,
including the time required to perform a task; the amount of available
resources; and the expected gain from successfully completing a task. Next, we
survey current solutions and show their limitations. Based on these insights we
develop general design concepts to tackle heterogeneity and uncertainty, and
then use these concepts to design practical algorithms. For each of our
algorithms, we provide rigorous mathematical analysis, thus showing worst-case
performance guarantees. Finally, we implement and run the suggested algorithms
on various input traces, thus obtaining further insights as to our algorithmic
design principles.
