# Dynamic Reliability: Reliably Sending Unreliable Data

Omar Nassef, Federico Chiariotti, Stephen Johnson, Toktam Mahmoodi Omar Nassef
<EMAIL_ADDRESS>and Toktam Mahmoodi<EMAIL_ADDRESS>are
with the Centre of Telecommunication Research, Kings College London, UK.
Federico Chiariotti<EMAIL_ADDRESS>is with the Department of
Information Engineering, University of Padova, Italy, and with the Department
of Electronic Systems, Aalborg University, Denmark. Stephen Johnson
<EMAIL_ADDRESS>is with British Telecommunications plc, UK. This
project is jointly funded by BT, the UK Engineering and Physical Sciences
Research Council (EPSRC), and King’s College London Centre for Doctoral
Studies (CDS).

###### Abstract

5G and Beyond networks promise low-latency support for applications that need
to deliver mission-critical data with strict deadlines. However, innovations
on the physical and medium access layers are not sufficient. Additional
considerations are needed to support applications under different network
topologies, and while network setting and data paths change. Such support
could be developed at the transport layer, ensuring end-to-end latency in a
dynamic network and connectivity environment. In this paper, we present a
partial reliability framework, which governs per-packet reliability through
bespoke policies at the transport layer. The framework follows a no-ack and
no-retransmit philosophy for unreliable transmission of packets, yet maintains
cooperation with its reliable counterpart for arbitrary use of either
transmission mode. This can then address latency and reliability fluctuations
in a changing network environment, by smartly altering packet reliability. Our
evaluations are conducted using mininet to simulate real-world network
characteristics, while using a video streaming application as a real-time use-
case. The results demonstrate the reduction of session packet volume and
backlogged packets, with little to no effect on the freshness of the packet
updates.

###### Index Terms:

5G, Partial Reliability, QUIC, Age of Information

##  I Introduction

The roll-out of 5G has enabled a plethora of use cases and new applications,
which generally fall under three broad categories: Enhanced Mobile Broadband
(eMBB), Massive Machine Type Communication (mMTC) and Ultra-Reliable Low-
Latency Communication (URLLC) [1]. Most human-generated traffic is eMBB, which
supports higher data rates, mobility and dense connectivity thanks to the
capability of connecting to micro- and nano-cells. Other scenarios that can be
characterized as eMBB include large-scale distributed machine learning [2],
which is expected to generate massive volumes of traffic. On the other hand,
mMTC focuses on high density Internet of Things (IoT) device deployments, and
specifically aims at supporting longer transmission distances and reducing
energy consumption by adopting lower data rates [3]. Finally, URLLC includes
scenarios that require near perfect reliability (i.e., an error probability
below $10^{-5}$) with a maximum latency of $1$ ms. Its use cases extend to
cooperation between autonomous vehicles [4] and the Tactile Internet [5].

The research on adapting the Radio Access Network (RAN) to the new
requirements of these different classes of traffic is extensive, but the RAN
is not the only factor affecting quality of application’s delivery. The
presence of cross-traffic can cause significant delays and congestion, and
even without it, self-queuing delay is a well-known problem in wireless
networks, as probing the connection capacity aggressively can increase the
latency [6] [7].

Additionally, different applications and use-cases expect different levels or
latency and/or reliability. This can make optimization even more complex:
meeting different requirements for several applications, all with independent
adaptation mechanisms, is a significant challenge. Even the nature of the
metrics themselves might be different: one recent example is Age of
Information (AoI), which has currently risen in prominence for several IoT
applications [8], as it can measure the freshness of the data available to the
receiver, incorporating the data generation process as well as network-related
aspects.

An important detail in AoI optimization is that not every packet is needed: if
new updates are frequent enough, the more recent data supersedes the older
information, and a certain level of packet loss is acceptable. This is opposed
to the extreme reliability requirements of URLLC traffic, but there are
several use cases and scenarios where it intuitively makes sense, e.g.,
cooperative autonomous driving: if a car frequently sends information about
its position and direction, the loss of any single sensor reading can be
recovered from [9], keeping in mind that urgent safety messages will be sent
as URLLC traffic, ensuring that mission-critical information, such as
collision warnings, is reliably transmitted.

These real-time, relatively loss-tolerant information flows may not require
end-to-end reliability mechanisms, as retransmissions can increase delay and
traffic on the network: in order to better support the concurrent URLLC and
eMBB flows, which need network resources due to their stricter requirements,
these applications can send data unreliably. In this paper, we introduce
dynamic reliability: a novel idea for partial reliability. Dynamic reliability
permits assignment of per-packet reliability status at the transport layer,
governed by tailored policies, opposed to the traditional application layer
manner. The framework follows a true unreliable transmission philosophy of
removing Acknowledgements (ACKs) and retransmissions. The proposed solution is
a modification of the QUIC protocol [10], which can support concurrent flows
with different reliability requirements, dynamically setting the reliability
of each packet while considering the state of the connection.

The proposed solution is examined in detail with respect to a number of
network topologies and links, considering metrics such as session packet
volume, backlogged packets and AoI, to ascertain the feasibility of dynamic
reliability in real-time scenarios. Furthermore, we explore a number of
governing reliability policies to show the adaptability of dynamic reliability
to different requirements. The contributions of this paper include:

  * •

A dynamic reliability framework that allows per-packet assignment of
reliability at the transport layer, depending on the governing reliability
policies.

  * •

Performance evaluation of a number of reliability policies for dynamic
reliability. The policies explore different logic and complexity for
reliability assignment based on path and network measurements.

  * •

A comparison between the different dynamic reliability logic over wireless
communication using different frequencies, including Millimeter Wave (mmWave),
sub-6GHz and Wi-Fi.

The remainder of this paper is structured as follows: Sec. II showcases the
State of the Art (SOA), informing the reader on QUIC and the different
implementations of partial reliability. Sec. III delves into the system model
and design of dynamic reliability, while Sec. IV analyses the result of
implementing dynamic reliability in simulated network environments. Lastly,
the conclusion and future works are discussed in Sec. V.

##  II State of the Art

Although the transport layer does not consider any RAN parameters directly,
indirect end-to-end measurements such as Round-Trip Time (RTT) are used to
assess the bandwidth, latency and loss rate. QUIC is one protocol of many that
utilises these path properties for end-to-end communication services. QUIC was
designed by Google to circumvent latency issues that were associated with the
traditional Transmission Control Protocol (TCP). More specifically, it allowed
multiplexing a session into different streams between the two endpoints, to
bypass Head of Line Blocking (HoL). Each stream in QUIC is given a Connection
ID and treated as a separate flow, this allows each stream to terminate or
migrate without affecting the rest of the session. Each stream also has its
own packet sequence independently from other streams, maintaining its own in-
order delivery system.

Despite the fact that QUIC runs over User Datagram Protocol (UDP), its
transmission is reliable and in-order for each stream. That being said,
recently a _Datagram Extension_ has been added to QUIC to enable unreliable
transmission of packets as well [11]. A reliable and unreliable stream between
the same end-points can share a single handshake and proceed with transmission
normally, but it is left for the application layer to differentiate between
datagram flows, burdening the application layer with a larger complexity as
well as offering no re-ordering for the datagram packets. Even though datagram
frames are unreliable, they are still ACK-eliciting and their rate is affected
by the congestion window.

In the most general definition, partial reliability allows for a transport
protocol to send reliable and unreliable data when the application deems fit.
While the traditional fully reliable approach has been challenged by transport
protocols such as Stream Control Transmission Protocol (SCTP) [12], Datagram
Congestion Control Protocol (DCCP) [13] and even TCP [14], there is no unified
concept of partial reliability, or a shared technical solution. Each protocol
implements their distinct definition of partial reliability with disparate
design aims. The QUIC datagram extension also goes in this direction, but the
decision on which data should be sent reliably is still an open research
question.

QUICSilver [15] uses predicted deadline awareness to guide the decision making
for sending frames reliably. The aim of QUICSilver is to reduce the occurrence
of stalls in video transmission, which it has managed to achieve compared to
vanilla QUIC, albeit only to only low-quality video transmissions. As stated
by the author, the freshness checks to determine the staleness of the frames
introduce a non-negligible delay which inherently affects the playback of the
video transmission.

Furthermore, ClipStream [16] sends Intra-Frames (i.e., frames that contain
sufficient data to display the whole image) and end-of-stream markers
reliably, while Predicted Frames (i.e., differentially encoded frames based on
the previous I-frame) are sent unreliably. Opportunistic retransmission is
used, sending new data instead of retransmissions for the unreliable streams.
That being said, this work does not take into account the strict playback
delays when considering the retransmission of reliable frames.

Alternatively, QUIC-EST [9] adopts a multi-sensory use case as their variation
of a real-time application. The aim is to reduce the probability of
undelivered frames in blocking fresh content transmission. The design goal is
to have every object sent on its own stream with a priority allocation based
on the value of information that frame induces. When the packets on a single
stream are acknowledged, the stream can be reused for consecutive new objects.
If a packet is lost or excessively delayed, the whole stream is discarded,
opting out of retransmissions. Although the approach can be generalised to
many mission-critical and real-time applications, it requires the application
layer to assign a priority value to objects.

In this work, we consider a new approach for partial reliability. We focus on
per-packet partial reliability at the transport layer piloted by policies,
which emphasises reactivity to fluctuations in network measurements, rather
than the traditional method of partial reliability assignment at the
application layer. We remove the need for ack-elicitation following a true
unreliable philosophy, which has not been explored in the literature.
Additionally, we incorporate “timed reliability” from SCTP [12], but utilise
an occupancy-driven metric rather than time-based: when the buffer reaches a
threshold of packets received, all the packets that have not been sent to the
application layer are discarded.

##  III Architecture and System Model

Although QUIC has already standardised an extension for unreliable packet
sending, the protocol requires ACKs to ensure correct functionality. While ACK
packets assist in loss recovery and congestion control, they defy the true
meaning of unreliable transmission. Furthermore, the receiver is encouraged to
delay sending back ACK frames, which may lead to unpredictable behaviour.
Finally, the co-existing nature of reliable and unreliable frames is non-
existent at the transport layer, relegating all the responsibility and
complexity to the application layer. This behaviour can be sub-optimal,
especially for real-time and AoI-oriented applications.

Therefore, the main novelty of this work is to introduce the concept of
dynamic reliability, which seamlessly enables and disables reliable packet
sending through tailored policies, achieving reduced traffic load when needed
to prioritise transmission of fresh packets. The decision to transmit reliably
or unreliably could depend on the characteristics of network and applications.
Unreliable packets do not elicit an ACK and co-exist with its reliable
counter-part at the transport layer. For example, switching to unreliable mode
will be attractive for real-time, loss-tolerant applications that could yet
still benefit from end-to-end stream multiplexing, security, and other
features of QUIC, as compared to plain UDP.

We examine the performance of the proposed dynamic reliability framework using
Mininet, and simulate both the end-to-end and intermediate nodes, as well as,
the real-world network characteristics, in a setup depicted in Fig. 1. In this
setup, the client live streams an HD video ($\approx 60$ frame-per-second) to
the server with a variable send-rate dependant on the live-stream and network
conditions. Furthermore, the links connecting the nodes are selected from Wi-
Fi, mobile Sub-6GHz and mmWave with properties described in Table I. To
isolate the performance gain of dynamic reliability in the simulation, we
negate the presence of other services, and reduce the load of the network to
only the essential components of the live stream. We also consider bursty loss
scenarios, modeling the connection as a Gilbert-Elliott two-state channel
[17].

Figure 1: Illustration of Dynamic Reliability logic in a mobile network architecture. As the quality of the network improves, unreliable transmission is adopted. The favorability is determined by the reliability policy. TABLE I: Path characteristics for different link technologies [18, 19, 20] Parameter | Technology
---|---
Sub-6GHz | Wi-Fi | mmWave (LoS)
Capacity (Mb/s) | 1100 | 30 | 2500
Delay (ms) | $27.4\pm~{}6.4$ | $20\pm~{}10$ | $2\pm~{}1$
Loss Ratio (Percent) | 0.1 | 0.7 | 0.1

###  III-A Dynamic Reliability

The addition of extra ACK packets can increase congestion during traffic
bursts, reducing the maximum load that a network can support. This has been
observed, e.g. in WiFi connections, in which even short TCP ACK packets on the
uplink can significantly reduce downlink throughput [21] due to the contention
for access to the channel. Furthermore, real-time, AoI-oriented applications
rarely require retransmission of stale frames, opting instead for the latest
frames as they relatively hold much more value. This is a common assumption in
the AoI literature, and intuitively makes sense when we consider the immediate
use of sensor readings [8].

To achieve dynamic reliability, we extend QUIC by adding a new frame type,
which resembles the reliable frame, albeit a different frame type byte. This
new frame flags no-ack and no-retransmit to represent an unreliable packet. It
is important to note that the packet sequencing remains the same with
unreliable and reliable flows, the only difference being that unreliable
packets do no solicit an acknowledgement, and hence, are never retransmitted.

However, as most congestion control mechanisms use ACKs to infer congestion
and measure capacity, the lack of acknowledgements from the unreliable segment
of transmission means that the congestion window may not be strictly accurate.
Despite that, the unreliable transmission will still follow the rate presented
by the congestion window, which places emphasis on fairness of the protocol
with other traffic on the link. At the same time, adhering to a stale
congestion window is sub-optimal, and the reliable segment might not be enough
to get an accurate picture of the channel. We then need to introduce probing
to update the congestion window and path measurements such as RTT, preventing
the use of stale feedback in the transmission of packets.

The features of the proposed dynamic reliability framework are as follows:

  * •

Permitting of per-packet assignment reliability through policies located at
the transport layer.

  * •

Ability to send reliable and unreliable packets concurrently along the same
path, session or stream. This provides further granular control over the
reliability of parallel, multiplexed and distinct traffic type transmissions
an application may adopt through streams;

  * •

No requirement for separate packet sequences between unreliable and reliable
packets. This is the main enabler for unreliable and reliable packets to co-
exist in the same session;

  * •

Unreliable packets do not elicit ACKs, therefore, less network resources are
consumed;

  * •

Loose coupling of congestion control and loss recovery mechanisms; both ACK
and non-ACK based mechanisms can be integrated.

  * •

Maintained inter- and intra- flow fairness by adhering to the congestion
control.

Figure 2: Normalised frequency of transmitted packets with burst and SOA loss
values against the dynamic reliability logic for different network topologies.
Figure 3: Normalised frequency of backlogged packets with burst and SOA loss
values against the dynamic reliability logic for different network topologies.

###  III-B Reliability Policies

The reliability policies can be tailored to fit the application, network or
holistic constraints. Though, it is important to note that the policies
perform at the transport layer and cannot be altered at the application level.
The verdict of the policy is used to set the type byte of the frame to
indicate its reliability status. Since the policy is ingrained in the QUIC
protocol, it has access to a diversity of information available from the
transport protocol e.g. RTT, congestion window and bytes in-flight to name a
few.

A number of reliability policies are explored in this work with varying levels
of complexity and intelligence: the Naive, 20-80 split and 80-20 split
policies use a static unreliability packet ratio, providing a performance
baseline. On the other hand, the Smoothed-RTT (SRTT)-based and loss-aware
policies take into account the state of the network to guide the packet
reliability assignment thus providing a smarter reliability policy. We take
the vanilla implementation of QUIC to be the benchmark for the dynamic
reliability implementation.

Our first scenario follows a naive approach in transmitting packets, with the
purpose of highlighting its inadequacy in obtaining greater performance
optimisation compared to more complex policies. Following its name, the naive
policy randomly flags $50\%$ of packets as reliable. The policies for
subsequent scenarios are detailed below:

####  III-B1 80-20 Split

Similar to the Naive method, packets have an 80% probability of being flagged
as reliable.

####  III-B2 20-80 Split

The polar opposite of 80-20, where packets have a chance of being flagged as
reliable 20% of the time.

####  III-B3 SRTT-Based Logic

Utilises the SRTT as a basis for appraising the network condition. The SRTT is
calculated from reliable packets, adhering to the method used by QUIC to track
the RTT and its derivatives. If the latest RTT is lower than the SRTT, it can
be assumed that the network conditions are acceptable for marking packets as
unreliable.

####  III-B4 Loss-Aware Logic

Curated for bursty loss scenarios, this policy takes into account the
exponentially weighted moving average [22] of the session loss rate. The loss
rate is shown in Eq. 1, while Eq. 2 adopts the exponential smoothing. Let
$P_{s}$ be the packets that are sent, $P_{us}$ be the packets are unreliably
sent and $P_{r}$ be the packets received which are not ACK-eliciting. The
measurements are taken at $i=1$, which serves as the start of the session.

$\lambda=\frac{\sum_{i=1}^{n-1}P_{s}-\sum_{i=1}^{n-1}P_{us}}{\sum_{i=1}^{n-1}P_{r}}$
(1)

$\omega_{t}=\alpha\lambda_{t-1}+(1-\alpha)\omega_{t-1},$ (2)

where $n$ denotes the discrete sending times. $\alpha$ is the weighting
constant $0\leq\alpha\leq 1$, which prescribes the importance of the previous
measurements. In a bursty scenario, the measurements change frequently, and
past recordings hold little relative value. However, in order to detect a
burst, some past measurements are required: as such, we set the discount value
to 0.8. The real-time constraint $RT$ is set at 5%, which is the maximum
tolerable loss rate for a real-time application, where $\omega_{t}\leq RT$
permits unreliable sending.

##  IV Results

Figure 4: The time average peak Age of Information with burst and SOA loss
values against the dynamic reliability logic for different network topologies.

This paper focuses on both transport layer and application layer metrics to
determine the feasibility of dynamic reliability. For this, we have selected
the session packet volume, as transmitted, retransmitted, lost and backlogged
packets as Key Performance Indicators (KPIs) for the transport layer; while
focusing on the AoI for the application layer. The AoI was chosen as a crucial
indicator for the freshness of packets in real-time applications. More
specifically, this work adopts the time average peak AoI equation [23]
depicted in Eq. 3, where $\Delta(r_{i+1})$ is the $i$th update at the time it
was received at the server, for a session time period of $\tau$.

$\lx@glossaries@gls@link{acronym}{aoi}{\leavevmode
AoI}_{\tau}=\frac{1}{n-1}\sum_{i=1}^{n-1}\Delta(r_{i+1})$ (3)

We include a comparison between the vanilla QUIC implementation which does not
enjoy the dynamic reliability extension, with a number of dynamic reliability
policies. The tests were run a number of times for statistical significance,
with the mean value of vanilla implementation used as a baseline for
comparison. The topology utilised both random loss and bursty loss to explore
the bounds of dynamic reliability. The SOA loss in the figures correspond to
the loss values presented in Table. I, for ease of comparison between bursty
and random loss scenarios.

###  IV-A Transport-Layer KPIs

To analyse the performance gain at the transport layer due to dynamic
reliability, the volume of transmitted and backlogged packets is examined. The
figures are in the form of boxplots, which take the vanilla implementation as
a benchmark, depicted as the red dashed line.

As seen in Fig. 2, the loss plays a crucial role in the performance of the
reliability policies. The policies under random loss did incredibly well for
the networks with a larger capacity, namely mmWave and Sub-6 GHz, whereas for
burst loss, the lower network capacities had a larger packet reduction. With
the increase in burst loss, the behaviour of the set split reliable policies
became unpredictable, if a reliable assignment happened to coincide with a
burst loss, the number of transmitted packets increases, and vice versa. On
the other hand, in smarter policies, such as Loss-Aware, the performance
lightly matched the vanilla baseline, as the reliable assignment dominated the
session to compensate for a higher burst loss. Not only that but, the burst
loss also impacted the variance of the transmitted packets for the policies.

Unsurprisingly, the unreliable focused policy, 80-20 split, outperformed other
policies for all topologies in random and bursty loss scenarios, with an
approximate reduction of 80%. That being said, the majority of the policies
reduced the transmitted packets on the link by approximately 70% for random
loss, while the reduction started at $\approx 15\%$ and decreased as the loss
increased for the burst loss scenario.

The retransmitted and lost packets, not shown due to space limitations,
followed the same trend as the transmitted packets for the random loss
scenarios. However, for the burst loss scenarios, the larger capacity networks
had a lower reduction in the retransmitted and lost packets. This can be seen
as a favorable outcome since the lower capacity networks are scarce on
resources. It is important to note that the Loss-Aware policy mimicked the
vanilla approach as the burst loss increased, signifying the overwhelming
appointment of reliable packets in adapting to the harsh burst loss
conditions.

Alternatively, Fig. 3 clearly shows a stark comparison between the policies
and loss scenario in the reduction of the backlogged packets. The Loss-Aware
policy for random loss scenario reduced the backlogged packets by up to 50%,
beating all other policies by approximately 30%. Furthermore, it is clear that
the unreliability focused policies resulted in the lowest backlog for the
session. In comparison, we notice that the burst loss and the backlogged
frequency have a positive correlation, where the maximum reduction of the
backlogged packets for the policies is at most 20%. Much like the transmitted
packets, the probability of a burst loss occurrence plays a vital role in the
number of retransmissions sent and by extension the number of backlogged
packets. Thus, we can conclude that the stress placed on the buffer is a
result of the reliable packets which is tightly coupled with the congestion on
the session. Whereas, unreliable focused policies did not encounter such a
phenomenon regardless if it was experiencing a burst loss.

###  IV-B Application-Layer KPIs

The feasibility of dynamic reliability for real-time applications can be
determined by the AoI, with comparison across different topologies and
policies. If we take a strict approach and consider anything below $10$ ms is
real-time [24], then all the reliability policies passed that requirement,
which is attractive for real-time applications, as shown in Fig. 4. Utilising
the median as an estimate of the runs, the policies in the WLAN and Sub-6 GHz
topology with random loss floated around $4-5$ ms with negligible difference,
while the AoI for mmWave was $\approx 2-3$ ms. It is clear that the AoI and
the network capacity have a negative correlation, as the network capacity
decreases, the AoI increases. The same correlation is extended to the bursty
loss scenarios, where mmWave dominated the other topologies. That being said,
it is crucial to note that the AoI for the reliability policies is often
slightly better than or equal to the AoI of the vanilla implementation,
proving that dynamic reliability reduces the congestion of the session at no
cost to the AoI.

##  V Conclusion

Dynamic reliability can be used to react and cater to varying network
topolgies with fluctuating measurements. Adhering to governing policies in
changing the per-packet reliability status to deal with bandwidth, loss and
delay constraints without deteriorating the AoI. Less resource intensive
requirements can reduce the cost of communication for operators and free
scarce resources for alternative traffic.

Future work will consider a holistic dynamic reliability policy for
interchangeable network conditions whilst focusing on the over all quality of
service from both a user and an operator perspective.

## References

  * [1] A. Ghosh, A. Maeder, M. Baker, and D. Chandramouli, “5g evolution: A view on 5G cellular technology beyond 3GPP Release 15,” _IEEE Access_ , vol. 7, pp. 127 639–127 651, 2019.
  * [2] O. Nassef _et al._ , “A survey: Distributed machine learning for 5G and beyond,” _Computer Networks_ , p. 108820, 2022.
  * [3] L. Feltrin _et al._ , “NB-IoT: Performance estimation and optimal configuration,” in _European Wireless_ , 2018.
  * [4] O. Nassef, L. Sequeira, E. Salam, and T. Mahmoodi, “Building a lane merge coordination for connected vehicles using deep reinforcement learning,” _IEEE Internet of Things Journal_ , vol. 8, no. 4, pp. 2540–2557, 2020.
  * [5] K. Antonakoglou _et al._ , “Towards haptic communications over the 5G Tactile Internet,” _IEEE Comm. Surv. Tut._ , vol. 20, no. 4, pp. 3034–3059, 2018.
  * [6] M. Polese _et al._ , “A survey on recent advances in transport layer protocols,” _IEEE Comm. Surv. Tut._ , vol. 21, no. 4, pp. 3584–3608, 2019\.
  * [7] T. Mahmoodi, V. Friderikos, and H. Aghvami, “Using traffic asymmetry to enhance TCP performance,” _Computer Netw._ , vol. 57, no. 1, pp. 317–329, 2013.
  * [8] R. D. Yates _et al._ , “Age of information: An introduction and survey,” _IEEE J. Sel. Areas Comm._ , vol. 39, no. 5, pp. 1183–1210, 2021.
  * [9] F. Chiariotti _et al._ , “QUIC-EST: A QUIC-enabled scheduling and transmission scheme to maximize VoI with correlated data flows,” _IEEE Comm. Mag._ , vol. 59, no. 4, pp. 30–36, 2021.
  * [10] A. Langley _et al._ , “The QUIC transport protocol: Design and internet-scale deployment,” in _Proc. ACM SIGCOMM_ , 2017.
  * [11] “An Unreliable Datagram Extension to QUIC,” Internet-Draft draft-ietf-quic-datagram-08, Jan. 2022.
  * [12] M. A. Ramalho _et al._ , “Stream Control Transmission Protocol (SCTP) Partial Reliability Extension,” RFC 3758, May 2004.
  * [13] Y.-C. Lai and C.-N. Lai, “DCCP partial reliability extension with sequence number compensation,” _Computer Netw._ , vol. 52, no. 16, pp. 3085–3100, 2008.
  * [14] B. Mukherjee and T. Brecht, “Time-lined TCP for the TCP-friendly delivery of streaming media,” in _Proc. IEEE ICNP_ , 2000, pp. 165–176.
  * [15] V. Band, “QUICsilver: Optimising QUIC for use with real-time multimedia traffic,” Ph.D. dissertation, University of Glasgow, 2019.
  * [16] M. Palmer _et al._ , “The QUIC fix for optimal video streaming,” in _Proc. ACM EPIQ_ , 2018.
  * [17] G. Haßlinger and O. Hohlfeld, “The Gilbert-Elliott model for packet loss in real time services on the Internet,” in _Proc. MMB_ , 2008.
  * [18] D. He, B. Ai, C. Briso-Rodriguez, and Z. Zhong, “Train-to-infrastructure channel modeling and simulation in mmwave band,” _IEEE Comm. Mag._ , vol. 57, no. 9, pp. 44–49, 2019.
  * [19] Y. Ren _et al._ , “A survey on TCP over mmWave,” _Computer Comm._ , vol. 171, pp. 80–88, 2021.
  * [20] H. Wu _et al._ , “Multipath scheduling for 5G networks: Evaluation and outlook,” _IEEE Comm. Mag._ , 2021.
  * [21] M. Zubeldía, A. Ferragut, and F. Paganini, “Averting speed inefficiency in rate-diverse WiFi networks through queueing and aggregation,” in _IEEE GLOBECOM_ , 2012, pp. 5224–5230.
  * [22] S. W. Roberts, “Control chart tests based on geometric moving averages,” _Technometrics_ , vol. 1, no. 3, pp. 239–250, 1959.
  * [23] B. Barakat _et al._ , “How to measure the average and Peak Age of Information in real networks?” in _Proc. European Wireless_ , 2019.
  * [24] S. Kudrle _et al._ , “Fingerprinting for solving A/V synchronization issues within broadcast environments,” _SMPTE Motion Imaging J._ , vol. 120, no. 5, pp. 36–46, 2011.


# MAMRL: Exploiting Multi-agent Meta Reinforcement Learning in WAN Traffic
Engineering ††thanks: Citation: Authors. Title. Pages…. DOI:000000/11111.

Shan Sun
University of California, Riverside
<EMAIL_ADDRESS>
&Mariam Kiran
Lawrence Berkeley National Laboratory
<EMAIL_ADDRESS>
&Wei Ren
University of California, Riverside
<EMAIL_ADDRESS>

###### Abstract

Traffic optimization challenges, such as load balancing, flow scheduling, and
improving packet delivery time, are difficult online decision-making problems
in wide area networks (WAN). Complex heuristics are needed for instance to
find optimal paths that improve packet delivery time and minimize
interruptions which may be caused by link failures or congestion. The recent
success of reinforcement learning (RL) algorithms can provide useful solutions
to build better robust systems that learn from experience in model-free
settings.

In this work, we consider a path optimization problem, specifically for packet
routing, in large complex networks. We develop and evaluate a model-free
approach, applying multi-agent meta reinforcement learning (MAMRL) that can
determine the next-hop of each packet to get it delivered to its destination
with minimum time overall. Specifically, we propose to leverage and compare
deep policy optimization RL algorithms for enabling distributed model-free
control in communication networks and present a novel meta-learning-based
framework, MAMRL, for enabling quick adaptation to topology changes. To
evaluate the proposed framework, we simulate with various WAN topologies. Our
extensive packet-level simulation results show that compared to classical
shortest path and traditional reinforcement learning approaches, MAMRL
significantly reduces the average packet delivery time even when network
demand increases; and compared to a non-meta deep policy optimization
algorithm, our results show the reduction of packet loss in much fewer
episodes when link failures occur while offering comparable average packet
delivery time.

_K_ eywords Traffic engineering, Meta-learning, Multi-agent reinforcement
learning, Packet delivery time, Link failures, Distributed solution

##  1 Introduction

Network providers leverage traffic engineering techniques to optimize
performance over operational IP networks [1]. With the exponential growth in
demand, researchers have experimented with new optimization algorithms that
aim to balance utilization and availability of network resources [2] or
optimize on multiple criteria such as the number of hops, availability, or
path attributes [3]. As wide-area network backbones (WANs) become costly to
maintain and upgrade, software-defined networking (SDN) is being used as a
promising method to maximize routing performance but needs to calculate and
optimize routes globally to users [4, 5].

Optimizing for network performance includes measuring bandwidth, jitter, or
latency over resource links, where a poorly designed infrastructure can lead
to slow performance and potentially increased packet loss. Apart from
meticulously designed heuristics needed to develop an optimization algorithm,
researchers would analyze offline models of the network topology and traffic
demand matrix to infer the best paths between source-destination pairs. This
approach, as a planning tool, leads to many limitations such as (1) difficult
to optimize in few minutes as networks grow from 10s to 100s of routers, and
(2) the dynamic traffic demand matrix would require recalculation every few
days as some links become congested and possibly fail.

Recent breakthroughs in deep learning techniques leveraging data-driven
learning have identified successful and simple solutions to complex online
decision-making problems such as playing games [6], resource management [7]
and learning inherent traffic patterns [8]. Particularly deep reinforcement
learning (RL) uses agents to learn, through interactions with the environment
by trial and error, their optimal actions via experiences and feedback. Here
agents can slowly modify behavior through interactions without knowing the
accurate mathematical model of the environment. In path optimization problems,
RL has a natural application by exploring different routing policies,
gathering statistics about which policies maximize performance functions, and
learning over time the best policy on which route to take. Examples of similar
techniques in path optimization include two main approaches [9] such as
optimizing routing configurations by predicting future traffic conditions
depending on past traffic patterns or optimizing routing configurations based
on the number of feasible traffic scenarios to improve performance parameters.
Modern communication networks have become very challenging mainly due to the
following two reasons [10]. Firstly, communication networks have become very
complicated and highly dynamic, which makes them hard to model and control.
For example, in vehicular and ad hoc networks, nodes frequently move, and link
failures might occur during working hours, which might result in topology
changes [11, 12]. Second, as the scale of networks continue to multiply, a
central controller may be costly to install and slow to configure and be
robust to malicious attacks [13, 14]. Therefore, there is a need to develop
innovative ways in which traffic routing does not rely on accurate
mathematical models and can be managed in a distributed manner. Examples of
distributed path planning such as ant colony optimization and swarm approaches
have shown success in static environments, but still need more learning for
dynamic environments [15].

In this paper, we investigate the above issues and evaluate if deep
reinforcement learning can provide an optimal, adaptable and distributed
solution to path selections as network load increases, and especially if the
topology changes such as link failing or becoming congested. In order to
design an optimal path selection for various network topologies and network
loads, we design a deep policy-based meta-learning algorithm (MAMRL) and
evaluate its performance in various simulated WAN topologies. MAMRL can
optimize multiple objectives packet loss and packet delivery time. Our
preliminary results show that MAMRL can perform better than the shortest
possible route algorithms, especially as network loads increase and congestion
is possible. Modelling the network as a multi-agent complex system,
representing each router as an agent, we can demonstrate that MAMRL can learn
and perform with each router in a distributed manner, allowing future work for
online traffic engineering on devices.

###  1.1 Motivation and Contribution

In this work, we investigate the challenge of how can one build an adaptive
network routing controller that continue to provide optimum network
performance, even when the topology changes. For this we model the challenge
as a path optimization technique that can be adaptive to various network load
and topology changes, via novel deep reinforcement learning. Modern
communication networks are highly dynamic and hard to model and predict,
therefore, we aim to develop a novel _experience-driven_ algorithm that can
learn to select paths from its experience rather than an accurate mathematical
model. Additionally, due to difficulties in gathering information from widely
distributed routers, we design a distributed optimization framework to learn
the local optimal strategy.

Our specific contributions are:

  * •

Policy-based RL learning performs well at high network load. Using a policy-
based deep reinforcement learning method, we train the model at a variety of
network loads and save the optimal neural network. Once deployed, our trained
neural network can perform superiorly at high network load compared to value-
based RL learning.

  * •

Optimizing for multiple criteria. Our neural networks are optimized for multi-
objective optimization for both packet delivery time and packet loss on the
network links. We design an appropriate reward (utility) function, which well
represents the preference of the network controller, to minimize both packet
delivery time and packet loss when link failures occur.

  * •

Quick adaptation to link failures. Our proposed MAMRL framework aims to make
good online decisions under the guidance of powerful Deep Neural Networks
(DNNs). In addition, by leveraging the model-agnostic meta-learning technique
[16], our neural networks can quickly alternate paths to minimize both packet
delivery time and packet loss when link failures occur.

  * •

Calculate optimal packet routes based on limited local observation for future
on-device Traffic Engineering research. Our neural network model is deployed
per multiple agents to represent multiple routers, allowing each router agent
to learn and optimize the traffic routing based on their local information. To
achieve this, we leverage a dynamic consensus estimator [17] to diffuse local
information and estimate global rewards, still achieving the best average
packet delivery time.

We develop a fully distributed multi-agent meta-reinforcement learning (MAMRL)
for a packet routing problem, where each router agent aims to find the correct
adjacent routers to send their packets to minimize the overall average packet
delivery time and avoid packet loss. We demonstrate our results via extensive
packet-level simulations representative of WAN network topologies (ATT, Geant,
B4), showing that MAMRL significantly outperforms several baseline algorithms
in high network load.

##  2 Background

###  2.1 Deep Reinforcement learning

Reinforcement learning is concerned with how an intelligent agent learns a
good strategy from experimental trials and relative feedback received. With
the optimal strategy, the agent is capable to actively adapt to the
environment to maximize cumulative rewards. Almost all the deep RL problems
can be framed as Markov Decision Processes (MDPs), which consists of four key
elements $\langle\mathcal{S},\mathcal{A},P$, $R\rangle$. More specifically, at
each decision epoch $t$, the intelligent agent can stay in state $s_{t}$ that
belongs to the state space $\mathcal{S}$ of the environment, and choose to
take an action $a_{t}$ that belongs to the action space $\mathcal{A}$ to
switches from one state to another. The probability that the process moves
into its new state $s_{t+1}$ is given by the state transition function
$P(s_{t+1}|s_{t},a_{t})$. Once an action is taken, the environment delivers a
reward $r$ as feedback. Figure 1 shows the general process of reinforcement
learning (the definition of policy will be given below).

Figure 1:  A global reinforcement learning agent learning network states.

There are two key functions in RL: policy function $\pi(a_{t}|s_{t})$ and
value function $V_{\pi}(s_{t})/Q_{\pi}(s_{t},a_{t})$. The policy is a mapping
from state $s_{t}$ to action $a_{t}$ and tells the agent which action $a_{t}$
to take in state $s_{t}$. For example, in the path optimizing problem, the
policy is the router’s strategy that finds the best adjacent router to send
out current packets given the current utilization state of the communication
network. The state value function $V_{\pi}(s_{t})$ measures how rewarding a
state is under policy $\pi$ by a prediction of future reward. Similarly, the
action-state value function $Q_{\pi}(s_{t},a_{t})$ tells, for a given policy,
what the expected cumulative reward of taking action $a_{t}$ in state $s_{t}$
is.

The goal of RL is to find the optimal policy that achieves optimal value
functions:
$\pi^{*}=\text{argmax}_{\pi}V_{\pi}(s_{t})=\text{argmax}_{\pi}Q_{\pi}(s_{t},a_{t})$.
Traffic engineering is a natural application of RL by exploring with different
routing policies, gathering statistics about which policies maximize the
utility function, and learning the best policy accordingly.

Value-based algorithms versus Policy-based algorithms: Value-based RL
algorithms attempt to learn the tabular or approximation of the state-action
value $Q_{\pi}(s,a)$ and selects the action based on the maximal value
function of all available actions for a given state. For example, the
Q-routing algorithm enables the routers to restore Q-values as the estimate of
the negative transmission time between that router and the others. To shorten
the average packet delivery time, routers will choose the action with maximal
Q-values. Policy-based RL algorithms instead learn the policy directly with a
parameterized function concerning $\theta$, $\pi_{\theta}(a_{t}|s_{t})$ and
train the policy to maximize the expected cumulative reward function. Policy-
based algorithms can learn stochastic policies. It is worthwhile to note that
stochastic means stochastic in some action-state pairs where it makes sense.
Usually, value-based algorithms, which choose the actions with the maximal
values, can only follow deterministic policies or stochastic policies with
predetermined distributions. That is not quite the same as learning the real
optimal stochastic policy. Since the current communication networks are highly
dynamic and stochastic, we can expect that the policy-based RL algorithms
perform superiorly to the value-based RL algorithms for certain scenarios,
where the optimal policy is stochastic. In Section 2.2, we will introduce more
details about the policy-based RL algorithms.

In this work, to enable high-dimensional state representations (such as action
histories), we consider deep RL algorithms, which adopt deep neural networks
to approximate the policy functions. Here the policy parameters $\theta$ are
the weights of the deep neural networks.

###  2.2 Performance under Partial Observability

Figure 1 shows the general process of reinforcement learning, where the agent
is able to observe the global information of the environment. As stated in
Section 1, in this work, we consider a path optimization problem in the
distributed network environment, indicating that each router only has access
to its own information and the information received from its adjacent routers.
It follows that the path optimization problem can be modeled as a multi-agent
partially observable Markov decision process (POMDP). A POMDP, referred as
$\mathcal{M}$, for $n$ routers is defined by a tuple
$\langle\mathcal{S},\\{\mathcal{O}^{i}\\}_{i\in\mathcal{V}},\\{\mathcal{A}^{i}\\}_{i\in\mathcal{V}},P$,
$\\{R^{i}\\}_{i\in\mathcal{V}}\rangle$, where $S$ and $P$ carry the same
meaning as those in Section 2.1 and $\mathcal{V}$ denotes the set of all
routers. $\mathcal{O}^{i}$, $\mathcal{A}^{i}$, and $R^{i}$ are the local
observation space, local action space and local reward function of router $i$,
respectively. Then we have $\mathcal{A}=\Pi_{i=1}^{n}\mathcal{A}^{i}$ is the
joint action space of all routers. Each router only has access to a private
local observation correlated with the state $o^{i}_{t}$. To choose actions,
each router $i$ uses a stochastic parametric policy
$\pi_{\theta^{i}}^{i}:\mathcal{O}^{i}\times\mathcal{A}^{i}\to[0,1]$, where
$\pi^{i}_{\theta^{i}}(a^{i}_{t}|o^{i}_{t})$ represents the probability of
choosing action $a^{i}_{t}$ at observation $o^{i}_{t}$. Thus, the joint policy
of all routers $\pi_{\theta}:\mathcal{S}\times\mathcal{A}\to[0,1]$ satisfies
$\pi_{\theta}(a_{t}|s_{t})=\Pi_{i=1}^{n}\pi^{i}_{\theta^{i}}(a^{i}_{t}|o^{i}_{t})$.
For a given time horizon $H$ we define the trajectory
$\tau:=(s_{0},a_{0},\cdots,s_{H},a_{H},s_{H+1})$ as the collection of state
action pairs ended at time $t=H$. The probability distribution of the initial
state is denoted by $\rho(s_{0})$. In the path optimization problem
(cooperative multi-agent problem), the collective objective of all the routers
is to collaboratively find policies $\pi_{\theta^{i}}^{i}$ for all
$i\in\mathcal{V}$ that maximize the globally expected trajectory reward over
the whole network. The goal of all routers is as follows,

$\max\limits_{\theta^{i},i\in\mathcal{V}}J(\theta)=\mathbb{E}_{\tau}\left[R(\tau)\right],$
(1)

where

$R(\tau)=\sum\limits_{t=0}^{H}r^{i}_{t}=\sum\limits_{t=0}^{H}\left(\tilde{r}^{i}_{t}+\frac{1}{n}\sum\limits_{i=1}^{n}\hat{r}^{i}_{t}\right),$

and $r^{i}_{t}$ denotes the reward needed by router $i$ at time $t$.
$r^{i}_{t}$ consists of two parts: 1) $\tilde{r}^{i}_{t}$ denotes the reward
signal based solely on individual behavior, and 2)
$\frac{1}{n}\sum_{i=1}^{n}\hat{r}^{i}_{t}$ denotes the reward signal based on
global behavior. Note that only $\tilde{r}^{i}_{t}$ and $\hat{r}^{i}_{t}$ can
be known by router $i$ in a partially observable environment.

As stated in Section 2.1, in this work, we investigate how deep policy
optimization algorithms work in path optimization problems. The main idea is
to directly adjust the parameters $\theta_{i},i\in\mathcal{V}$ of the policies
in order to maximize the objective in (1) by taking steps in the direction of
$\nabla_{\theta_{i}}J(\theta_{i},\cdots,\theta_{n})$. For POMDP, the gradient
of the expected return for router $i$ can be written111The derivation of
Equation (2) is provided in Appendix A. as,

$\nabla_{\theta^{i}}J(\theta^{i})=\mathbb{E}_{\tau}\left[\sum\limits_{t=0}^{H}\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(a^{i}_{t}|o^{i}_{t})R(\tau)\right].$
(2)

Note that with only local information, function $R(\tau)$ cannot be well
estimated since the estimation requires the reward $\hat{r}^{i}$ of all
routers. In this work, we propose to use a dynamic consensus algorithm to
estimate $R(\tau)$ using only local information, described in Section 3.

###  2.3 Model-agnostic Meta-learning

Figure 2: The framework of model-agnostic meta learning.

In this work, we consider path optimization in the presence of link failures.
It follows that, once there is a link failure, the state transition function
of the environment changes accordingly, indicating that a new POMDP occurs.
Let $\mathcal{M}_{0}$ denote the Markov process modeled by the full network
environment (no link failures) and $\mathcal{M}_{k}$, where $k>0$, denote the
Markov process modeled by the network environment with different link failure
scenarios. Suppose that the distribution of all POMDPs follows
$\eta(\mathcal{M})$. To make the routing algorithm adapt to link failures
(different POMDPs) quickly, we leverage the model-agnostic meta-learning [16]
into the policy optimization algorithms. Meta-reinforcement aims to learn an
algorithm that can quickly learn optimal policies in $\mathcal{M}_{k}$ drawn
from a distribution $\eta(\mathcal{M})$ over a set of Markov decision
processes. Our approach trains a well-generalized parametric policy
initialization that is close to all the possible environments (POMDPs), such
that it can quickly improve its performance on a new environment with one or a
few vanilla policy gradient steps (see Figure 2). The meta-learning objective
can be written as:

$\displaystyle\max\limits_{\theta}\quad
E_{\mathcal{M}\sim\eta(\mathcal{M}),\tau\sim
p(\tau|\pi_{\hat{\theta}})}\left[R(\tau)\right]$ (3)
$\displaystyle\text{s.t.}\quad\hat{\theta}=\theta+\alpha\nabla_{\theta}\mathbb{E}_{\tau\sim
p(\tau|\pi_{\theta})}[R(\tau)],$

where $\alpha>0$ is the learning rate and $p(\tau|\pi_{\theta})$ represents
the distribution of trajectory $\tau$ given policy $\pi_{\theta}$. Model-
agnostic meta-learning attempts to learn an initialization $\theta^{*}$ such
that for any environment $\mathcal{M}_{k}$ the policy attains maximum
performance after a few policy gradient steps.

##  3 Design: MAMRL Approach

###  3.1 Model

In the packet routing problem, packets are transmitted from a source to its
destination through intermediate routers and available links. The mathematical
model is given below.

Environment. We consider a possibly time-varying communication network
environment, which is characterized by an undirected graph
$\mathcal{G}_{t}=(\mathcal{V},\mathcal{E}_{t})$, where
$\mathcal{V}=\\{1,\cdots,n\\}$ is a set of routers and
$\mathcal{E}_{t}\subseteq\mathcal{V}\times\mathcal{V}$ are transmission links
between the routers at time $t$. The bandwidth of each link is limited and
packet loss might occur when the size of the packet to be transmitted is
greater than the link’s capacity. The communication network is possibly time
varying since link failures might happen during working hours. When the link
failure happens, the capacity of the link becomes zero. Each router $i$ has a
set of neighbor routers denoted by
$\mathcal{N}_{i}(t)=\\{j\in\mathcal{V}:(i,j)\in\mathcal{E}_{t}\\}$.

Routing. Packets are introduced into the network with a node of origin and
another node of destination. They travel to their destination nodes by hopping
on intermediate nodes. Each router only has one local port/queue used to store
traffic. The queue of routers follows the first-in-first-out (FIFO) criterion.
The node can forward the top packet in its local queue to one of its
neighbors. Once a packet reaches its destination, it is removed from the
network.

Objective. The packet routing problem aims at finding the optimal transmission
path between source and destination routers to minimize the average packet
delivery time, which is the sum of queuing time and transmission time while
preventing packet loss when link failures happen.

###  3.2 RL Formulation

Our standard RL setup consists of multiple router agents interacting with an
environment (communication networks) in discrete decision epochs. We
investigate the deep policy optimization algorithm to address packet routing
in a partially observable network environment. To make the router controllers
adapt to link failures more quickly, we leverage the model-agnostic meta-
learning technique to learn the well-generalized policy initialization.

Figure 3: MAMRL framework.

Figure 3 shows the MAMRL setup (training and testing process) per router. In
the testing process, each router uses the deep policy optimization algorithm
coupled with the dynamic consensus estimator to learn the optimal policy. In
order to let the routers adapt to topology changes quickly, the policy of each
router is initialized using the well-generalized policy initialization, which
is the output of the training process. The training process follows the
traditional model-agnostic meta-reinforcement learning framework. The basic
idea is letting the network controller encounter multiple link failures in the
training process. It can use this experience to learn how to adapt if similar
situations occur while deployed. In Figure 3, $\mathcal{M}_{0}$ denotes the
Markov process modeled by the full network environment (no link failures) and
$\mathcal{M}_{k}$, where $k>0$, denotes the Markov process modeled by the
network environment with link failures. In the training process, the network
controller collects data samples from all possible network environments
according to the distribution $\eta(\mathcal{M})$. However, the traditional
design of model-agnostic meta-learning mainly focuses on single-agent
(centralized) reinforcement learning problems. How to solve a multi-agent RL
problem using model-agnostic meta-learning in a distributed manner is rarely
studied. In this work, we aim to train and execute the network controller in a
distributed manner. As shown in Figure 3, each router has an independent
policy model that is represented by a deep neural network. The core of the
proposed control framework is letting each router run a deep reinforcement
learning algorithm to find the best action at each decision time instant,
using only local information and local interaction. Since the routers aim to
minimize the average packet delivery time of the whole network, each router
needs to feed the global packet delivery time into its policy model as
feedback/reward. To achieve this goal, we leverage the dynamic consensus
algorithm to estimate the global reward function, which is described below,

The policy optimization algorithms aim to find the best policy parameters that
produce the highest long-term expected return using gradient ascent. The
gradient of the long-term expected return for the parameters of each router’s
policy is defined in Equation (2). However, with only local information,
function $R(\tau)$ cannot be well estimated since the estimation requires the
rewards $\hat{r}^{i}$ of all routers $\forall i\in\mathcal{V}$. This motivates
our consensus-based policy gradient algorithm that leverages the communication
network to diffuse the local information, fostering collaboration among
routers. We adapt the following dynamic consensus algorithm [17] into the
policy optimization method.

$\displaystyle x^{i}_{t}$ $\displaystyle=\hat{r}^{i}_{t}-y^{i}_{t},$ (4)
$\displaystyle y^{i}_{t+1}$
$\displaystyle=\beta\sum\limits_{j\in\mathcal{N}_{i}}(x^{i}_{t}-x^{j}_{t})+y_{t}^{i},$

where $0<\beta<1$ is the control gain, $x_{t}^{i}$ and $y_{t}^{i}$ are local
estimators, and $\mathcal{N}_{i}$ denotes the neighbor sets of router $i$. It
can be proved that $x_{t}^{i}$ converges to the vicinity of
$\frac{1}{n}\sum_{i=1}^{n}\hat{r}^{i}_{t}$ within a few time steps. It is
worthy to mention that only local information is used in the designed
estimator Equation (4).

We develop the following policy optimization method for POMDP,

$\nabla_{\theta^{i}}\bar{J}(\theta^{i})=\mathbb{E}_{\tau}\left[\sum\limits_{t=0}^{H}\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(a_{t}^{i}|o_{t}^{i})\bar{R}^{i}(\tau)\right],$
(5)

where

$\bar{R}^{i}(\tau)=\sum\limits_{l=0}^{H}e^{i}_{l}=\sum\limits_{l=0}^{H}\tilde{r}_{l}^{i}+x^{i}_{l}\approx\sum\limits_{l=0}^{H}\left(\tilde{r}_{l}^{i}+\frac{1}{n}\sum\limits_{i=1}^{n}\hat{r}^{i}_{l}\right).$
(6)

Here, $e^{i}_{l}$ denotes the sum of the local reward signal
$\tilde{r}^{i}_{l}$ and global reward estimate $x^{i}_{l}$. And $x^{i}_{l}$ is
obtained by the dynamic consensus estimator designed in Equation (4). Note
that both $\tilde{r}^{i}$ and $x^{i}$ can be obtained locally.

We build the deep neural network with one input layer, five hidden layers of
size 128 with ReLU, and one output layer with Softmax (see Figure 3). As shown
in Figure 3, at each decision epoch $t$, each router $i$ provides the local
observation $o^{i}_{t}$ to the policy model $\pi_{\theta^{i}}$ and gets the
action $a^{i}$ back. Router $i$ performs action $a^{i}_{t}$ and switch to a
new state. Then router $i$ feeds the local reward $\tilde{r}^{i}_{t+1}$ and
global reward estimate $x^{i}_{t+1}$, which is the output of the dynamic
consensus estimator, to the policy model and the policy model
$\pi_{\theta^{i}}$ updates its weights $\theta^{i}$ with respect to the
received reward estimate $e^{i}$. It is worthwhile to mention that to update
the policy in the direction of greater cumulative reward using Equation (5),
only local information $o^{i}_{t}$, $a^{i}_{t}$ and $e^{i}_{t}$ are required.
By integrating model-agnostic meta-learning and the proposed multi-agent
policy optimization algorithm, MAMRL for packet routing problem, where both
training and execution process is distributed. These are shown in Algorithms 1
and 2.

Input: $\eta(\mathcal{M})$: distributions of network environments;

Input: $\alpha$: step size hyper-parameter;

randomly initialize $\theta^{i},i\in\mathcal{V}$;

while  _not done_ do

sample batch of environments $\mathcal{M}_{k}\sim\eta(\mathcal{M})$;

for  _all $\mathcal{M}_{k}$_ do

for  _all routers $i\in\mathcal{V}$_ do

Sample $K$ trajectories
$D^{i}=\\{(o_{0}^{i},a_{0}^{i},e_{0}^{i},\cdots,o^{i}_{H},a^{i}_{H},e^{i}_{H})\\}$
using $\pi_{\theta^{i}}^{i}$ and Equation (4) in $\mathcal{M}_{k}$;

end for

for  _all routers $i\in\mathcal{V}$_ do

Evaluate $\nabla_{\theta^{i}}\bar{J}(\theta)$ using $D^{i}$ based on Equation
(5);

Compute adapted parameters with gradient descent:
$\hat{\theta}^{i}=\theta^{i}-\alpha\nabla_{\theta^{i}}\bar{J}(\theta)$;

end for

for  _all routes $i\in\mathcal{V}$_ do

Sample $K$ trajectories
$\hat{D}^{i}=\\{(o_{0}^{i},a_{0}^{i},e_{0}^{i},\cdots,o^{i}_{H},a^{i}_{H},e^{i}_{H})\\}$
using $\pi_{\hat{\theta}^{i}}^{i}$ and Equation (4) in $\mathcal{M}_{k}$;

end for

end for

for  _all routes $i\in\mathcal{V}$_ do

Evaluate $\nabla_{\hat{\theta}^{i}}\bar{J}(\hat{\theta})$ using
$\\{\hat{D}^{i}\\}_{i\in\mathcal{V}}$ based on Equation (5);

Update $\theta^{i}$ with gradient descent:
$\theta^{i}=\theta^{i}-\alpha\nabla_{\hat{\theta}^{i}}\bar{J}(\hat{\theta})$;

using $\hat{D}^{i}$ based on Equation (5);

end for

end while

Return $\theta^{i},\ i\in\mathcal{V}$ as parameter initialization.

Algorithm 1 Multi-agent meta reinforcement learning algorithm (MAMRL train
time)

Input: A dynamic network environment with possible task distribution
$\eta(\mathcal{M})$;

Input: $\alpha$: step size hyper-parameter;

Input: Learned parameter initialization $\theta^{i},i\in\mathcal{V}$;

while  _not done_ do

if  _Link failure is True_ then

$\theta_{t}^{i}\leftarrow\theta^{i}$, $i\in\mathcal{V}$

end if

for  _all routers $i\in\mathcal{V}$_ do

Sample $K$ trajectories
$D=\\{(o_{0}^{i},a_{0}^{i},e_{0}^{i},\cdots,o^{i}_{H},a^{i}_{H},e^{i}_{H})\\}$
using $\pi_{\theta^{i}}^{i}$ and Equation (4);

end for

Evaluate $\nabla_{\theta^{i}}\bar{J}(\theta^{i})$ using $D$ based on Equation
(5);

for  _all routers $i\in\mathcal{V}$_ do

Compute adapted parameters with gradient descent:
$\theta_{t+1}^{i}=\theta_{t}^{i}-\alpha\nabla_{\theta^{i}}\bar{J}(\theta^{i})$;

end for

end while

Algorithm 2 Multi-agent meta reinforcement learning algorithm (MAMRL test
time)

###  3.3 Design of State, Action space and Rewards

We design the local observation $o^{i}_{t}$, local action $a^{i}_{t}$ and
local estimation of the reward function $e^{i}_{t}$ below,

  * •

Observation of router $i$, $o_{i}$: 1) destination router of first packet in
the local queue; 2) the last ten step actions taken by router $i$; 3) the
address of the router which has the longest queue among all the neighbor
router of router $i$.

  * •

Action of router $i$, $a_{i}$: next hop of current packet in the queue.

  * •

Reward estimate of router $i$, $e^{i}$: sum of $\tilde{r}^{i}$ and $x^{i}$,
where $\tilde{r}^{i}$ is negative number of packet loss occurred at router $i$
and $x^{i}$ is the estimate of $\frac{1}{n}\sum_{j=1}^{n}\hat{r}^{j}$ using
Equation (4). Here, $\hat{r}^{j}$ denotes the negative average delivery time
of all the packets delivered to router $j$.

Note that the design of state space and reward is critical to the success of a
deep reinforcement learning method. Our design of the state space captures key
components of the network environment. For our design of the reward function,
element $\frac{1}{n}\sum_{j=1}^{n}\hat{r}^{j}$ is introduced to minimize the
average packet delivery time of the whole network, element $\tilde{r}^{i}$ is
included to minimize the packet loss occurred at router $i$ in the presence of
link failures. Note that in our design $e^{i}=x^{i}+\tilde{r}^{i}$, where
$\tilde{r}^{i}$ is the negative number of packet loss occurred only at router
$i$ but $x^{i}$ is the estimate of the negative average delivery time of the
whole network environment. The reasons are summarized below.

Optimizing for packet delivery time: To achieve this goal, all the routers
need to collaboratively find the best paths to reroute the traffic. And the
delivery time of the packets that are delivered to router $i$ is determined by
the decisions of all the intermediate routers. That is, packet delivery time
is a signal based on global behavior, it is not enough for router $i$ to only
know the delivery time of the packets delivered to itself.

Optimizing for link failures: Although this goal also involves reading packet
loss in the whole network, the link failures have little effect on the routers
that are not directly connected to the failed links. Therefore, in our design,
we only provide the packet loss that occurred at router $i$ to the policy
$\pi_{\theta^{i}}$ as the feedback.

##  4 Evaluation

We conduct extensive simulations to evaluate the performance of the proposed
MAMRL framework in a path optimization problem with static topologies and
topologies with possibly failed links.

Topology Name | Number of nodes | Number of edges
---|---|---
B4 | 12 | 19
Geant | 21 | 32
ATT | 25 | 56
Table 1: Network topologies used in our evaluations.

We evaluate the results to,

  * •

Benchmark the RL techniques against standard path optimization approaches and
other RL approaches,

  * •

Examine how robust the MAMRL approach is under link failures, and

  * •

Show how quickly MAMRL adapts and reroutes packets to alternate paths
achieving better performance.

###  4.1 Experiment Settings

The simulation runs are performed on three network topologies, B4, Geant, and
ATT network. See Table 1 for a specification of network sizes. The B4 and ATT
topologies (link capacities) and their traffic matrices (packet size) were
obtained from the authors of Teavar [2]. The Geant topology is the European
Research network providing connectivity to science experiments across Europe
and US labs (www.geant.org).

To model the packet arrival, a discrete event network simulator is developed,
based on Open AI gym 222https://github.com/esnet/daphne-
public/tree/master/MAMRL-TE. Packets are introduced into the network with a
node of origin and another node of destination. The packet arrives according
to the Poisson process of rate $\lambda$. They travel to their destination
node by hopping on intermediate nodes. Each router only has a one local
port/queue used to store traffic. The queue of routers follows the FIFO
criterion. In each time unit, the node forwards the top packet in its local
queue to one of its neighbors. Once a packet reaches its destination, it is
removed from the network environment. The bandwidth of each link is limited
and packet loss might occur when the size of the packet to be transmitted is
greater than the link’s capacity. When the link failure happens, the capacity
of the link becomes zero.

In the experiments, we choose the step size $\alpha$ as $0.01$. In addition,
we use trust-region policy optimization (TRPO) [18] as the meta-optimizer and
the standard linear feature baseline [19] is used.

###  4.2 Impact of Increasing Network Load

We first test the MAMRL algorithm with static topologies (no link failures).
We compare with the classical shortest path algorithm and two existing RL-
based routing algorithms:

  * •

Shorted path algorithm (SPA) [20]: a traditional packet routing algorithm.

  * •

Q-routing [21]: a value-based multi-agent reinforcement learning algorithm.

  * •

Policy gradient (PG) [22]: a policy-based multi-agent reinforcement learning
algorithm.

In the experiments, the episodes terminate at the horizon of $H=500$. After
10000 training episodes, we restored the well-trained models to compare their
performance in a new test environment where packets were generated at the
corresponding network load level. Note that the SPA does not need training and
can be applied to test directly. We tested the network on loads ranging from
0.005 to 0.5 and measured the average packet delivery time of several episodes
in the testing process to compare with the results given by the above-
mentioned baseline controllers. The load corresponds to the value of $\lambda$
of the Poisson arrival process for the average number of packets injected per
unit time.

(a) B4.

(b) Geant.

(c) ATT.

Figure 4: Comparing average packet delivery time as load increases.

The average packet delivery time results versus different network load are
shown in Figure 4. Under conditions of low load for all the three topologies,
MAMRL is slightly inferior to Q-routing and SPA. As the load increases, the
MAMRL performs much better than the baseline algorithms. On the B4 topology,
when the traffic load is high (i.e., $\lambda=0.5$), MAMRL reduces the average
packet delivery time by $25\%$, $24\%$, and $14\%$, respectively, compared to
SPA, Q-routing, and policy gradient algorithms. On the Geant topology, when
the traffic load $\lambda=0.5$, MAMRL significantly reduces the average packet
delivery time by $37\%$, $37\%$, and $10\%$, respectively, compared to SPA,
Q-routing, and policy gradient algorithms. And on the ATT topology, when the
traffic load $\lambda=0.5$, MAMRL reduces the average packet delivery time by
$33\%$, $28\%$, and $10\%$, respectively, compared to SPA, Q-routing, and
policy gradient algorithms. The reason is described as follows. Under
conditions of low load, there is no congestion along the route. Therefore, the
deterministic policy learned by Q-routing performs as well as SPA, which is
the optimal routing policy under low load. However, the routing policy learned
by MAMRL is stochastic, which means that not all of the packets are sent down
the optimal link. That is why the performance of MAMRL is slightly inferior to
Q-routing and SPA under low load. As the load increases, the routes are
getting crowded and the length of the queues is getting longer. Due to the
stochastic nature of the communication network environment, the optimal policy
should be stochastic under conditions of high load. This explains why MAMRL
performs much better than the Q-routing and SPA controllers under high load.
The results in [22] also show that policy-based reinforcement learning
algorithm performs better than value-based algorithms, especially on high flow
load. However, the work in [22] only considers a simple policy gradient
algorithm for the packet routing problem. Instead, we investigate a deep
policy optimization algorithm that can take much more information as its
inputs, enlarging the state-action space for better policy making. The results
in Figure 4 indicate that our MAMRL algorithm achieves a shorter delivery time
than a simple policy gradient algorithm.

(a) B4.

(b) Geant.

(c) ATT.

Figure 5: Packet loss results in the presence of link failures.

###  4.3 Impact of Link Failures

We test the MAMRL algorithm in the presence of link failures with network load
$\lambda=0.3$. We let the router train and encounter all possible network
environments (link failure scenarios) according to the distribution
$\eta(\mathcal{M})$ and return policy parameters using Algorithm 1. We
restored the well-trained models in a new test environment where the links get
disconnected according to the distribution $\eta(\mathcal{M})$ (We assume that
only one link gets failed at one time). We compare results of using the
following three controllers: (1) testing the policy from the initialization
parameters obtained by MAMRL, (2) testing the policy from randomly initialized
weights (called random in the following), (3) shortest path algorithm (SPA)
[20], and (4) Q-routing algorithm [21]. Figure 5 show the results of the
packet loss versus episodes and Figure 6 show the results of the average
packet delivery time versus episodes. Also, we show the performance of
reinforcement learning routing algorithms (MAMRL, random, Q-routing) over the
three network topologies during the online learning procedure in terms of the
reward. We present the corresponding simulation results in Figure 7. We can
make the following observations from these results.

  1. 1.

In Figure 5, when there is a link failure, the model-based routing algorithm
(i.e., SPA) witnesses a huge packet loss. The reason is that the SPA algorithm
relies on previous knowledge of the network topology to make decisions. Here
we assume that as the networks grows, it becomes longer to update the
ISIS/OSPF protocols for link failures and update the tables. Both ISIS/OSPF
use the same Dijkstra algorithm for computing the best path through the
network. The other learning algorithms (MAMRL, random, Q-routing) are model-
free controllers and the policy of the model-free controller. When link
failure happens, the packet loss sensor will tell the RL routing controllers
that there are many packet loss at the particular link. Based on our design,
the packet loss hurts the reward of the RL routing controllers. To maximize
the reward function, the RL routing controller will adjust their policies to
improve the reward function and hence reduce the packet loss accordingly.

  2. 2.

Figure 7 shows how the reward value changes during online learning over the
three network topologies. It is seen that when there is a link failure, for
the B4 topology, Q-routing adapts to the link failure (reward values converge
to the stable states) after about 30 episodes, MAMRL (our algorithm) adapts to
the link failure after about 35 episodes and random algorithm (deep policy
optimization with randomly initialized weights) adapts to the link failure
after about 800 episodes. The results for Geant topology and ATT topology are
shown in Table 2. Q-routing is based on a value-based Q-learning algorithm and
is often much faster to learn a policy than policy optimization algorithms
[23]. In this work, we propose the MAMRL algorithm which leverages model-
agnostic meta-learning to help the policy optimization adapt to link failures
quickly. The basic idea of MAMRL is letting the network controller encounter
all possible link failures in the training process. It can then use that
experience to learn how to adapt. MAMRL aims to learn a well-generalized
policy initialization that is close to all possible situations of the
environment. Whenever there are continual packet losses at a particular link,
the MAMRL controller will reinitialize the policy models based on the pre-
trained well-generalized policy initialization. It can be seen from Figure 7,
the MAMRL controller adapts to link failures with a speed that is comparable
to the Q-routing algorithm. However, the normal policy optimization controller
adapts to the link failures much more slowly.

Topology Name | Q-routing | MAMRL | Random
---|---|---|---
B4 | 23 | 25 | 800
Geant | 35 | 35 | 100
ATT | 29 | 30 | 1000
Table 2: Average number of episodes used to adapt to link failures.

(a) B4.

(b) Geant.

(c) ATT.

Figure 6: Average packet delivery time results in the presence of link
failures.

###  4.4 Optimizing for Multiple Objectives

Policy optimization algorithms use gradient descent to optimize an
optimization problem. And traffic engineering aims at finding a solution to
forward the data traffic to maximize a utility function. The utility function
might concern a set of values. In our design, the objective is to minimize the
packet delivery time and packet loss, therefore, the utility function, which
corresponds to the reward function in the RL algorithms, consists of a
function of packet loss and a function of packet delivery.

In future works, we can add multiple objectives such as bandwidth utilization,
latency and more, if we want the RL controller to optimize on a number of
multiple parameters.

(a) B4.

(b) Geant.

(c) ATT.

Figure 7: Reward in the presence of link failures.

##  5 Related work

Routing is the process of selecting a path for traffic in a network from the
source node to a destination node. Routing algorithm selection may depend on
multiple criteria, for example, performance metric (delay, link utilization),
the ability to adapt to changes in topology and traffic, and scalability
(should be able to support a large number of routers). In the following, we
briefly review the traditional routing algorithms and reinforcement learning
routing algorithms based on the above-mentioned criteria. Since in this work,
we propose a kind of multi-agent reinforcement learning algorithm to solve the
packet routing algorithm, a literature review on multi-agent reinforcement
learning algorithms is also included in this section.

###  5.1 Traditional Packet Routing Algorithms

There are multiple routing algorithms in the literature of traditional packet
routing [24, 25, 26]. Among these traditional packet routing algorithms, the
shortest path algorithm is the most commonly used routing algorithm [27]. The
shortest path algorithm aims to find the shortest path between source and
destination nodes and get the packet delivered to the destination node as
quickly as possible. The shortest path algorithm is regarded as the best
routing algorithm on lower network load since packets can be delivered using
the least amount of time along the shortest path between two nodes provided
that there is no congestion along the route. However, when the network load is
high, the shortest path algorithm will cause a serious backlog in busy
routers. Another problem with the shortest path algorithm is that it relies on
having full knowledge of the network topology to design routing algorithms and
hence needs manual adjustment when topology or traffic changes happen.

###  5.2 Reinforcement Learning for Routing

Using reinforcement learning for packet routing has attracted increasing
interest recently. Various reinforcement learning methods have been proposed
to deal with this classical communication network problem and achieved better
performances compared with traditional routing methods.

Applications of traditional RL to solve packet routing problems started in the
early 1990s with the seminal work [21], where Q-routing was proposed.
Q-routing [21] is an adaptive routing approach based on a reinforcement
learning algorithm known as Q-learning. Q-routing routes packets based on the
learned delivery times (Q values) and achieves a much smaller average delivery
time compared with the benchmark shortest-path algorithm [20]. Since then,
several extensions of Q-routing have been proposed, e.g., Dual Q-routing [28],
Predictive Q-routing [29], Full Echo Q-routing [30], Hierarchical Q-routing
[31] and Ant-based Q-routing [32]. However, Q-routing is a value-based RL
algorithm. That is, Q-routing is a deterministic algorithm that might cause
traffic congestion at high loads and does not distribute incoming traffic
across the available links. Due to the drawbacks of a value-based algorithm,
some researchers begin to consider policy-based RL algorithms for packet
routing problems [33, 22]. Since policy-based RL algorithms can explore the
class of stochastic policies, it is natural to expect policy-based algorithms
to be superior for certain types of network topologies and loads, where the
optimal policy is stochastic. In [22], the results show that policy-based RL
algorithms perform better than value-based algorithms, especially on high flow
load. These traditional reinforcement learning routing algorithms use tabular
functions or simple algebraic functions to estimate the Q functions or policy
functions. This is limiting for a large number of states and thus cannot take
full advantage of the network traffic history and dynamics. In this work, we
investigate the policy-based deep reinforcement learning algorithm and use
deep neural networks to approximate the policy function. The combination of
deep learning techniques with reinforcement learning methods can learn useful
representations for the routing problems with high dimensional raw data input
and thus achieve superior performance.

Deep reinforcement learning is the combination of reinforcement learning and
deep learning, which has been able to solve a wide range of complex decision-
making tasks. However, rare works are investigating how deep reinforcement
learning can be leveraged for packet routing problems since the wireless
network is a multi-agent environment and the network environment is non-
stationary from the perspective of any individual router. This prevents the
straightforward use of experience replay, which is crucial for stabilizing
deep Q learning [34]. [35] combines the Q-routing and deep Q-learning to solve
the routing problem. However, the training process of the algorithm proposed
in [35] is in a centralized manner (all the routers need to share parameters),
which might cause issues in real-world large-scale network environments. The
authors in [36] propose to use a deep actor-critic reinforcement learning
algorithm to optimize the performance of the communication network. However,
the training and testing process in [36] are also in a centralized manner.
Recently, distributed Deep Q-routing has been proposed in [37], where deep
recurrent neural network (LSTM) has been utilized to tackle the non-stationary
problem in multi-agent reinforcement learning. However, the assumptions in
[37] are different from those in our work. In [37], it is assumed that the
bandwidth of each link equals the packet size, in which case only a single
packet can be transmitted at a time. However, in our current work, we assume
that the capacity of each link is fixed, in which case many packets can be
transmitted at a time. We believe that our assumption is more realistic.

###  5.3 Multi-agent Deep Reinforcement Learning Approaches

There is a huge body of literature on single-agent deep reinforcement learning
algorithms, where the environment stays largely stationary. Unfortunately,
traditional deep reinforcement learning algorithms are poorly suited to multi-
agent environments, where the environment becomes non-stationary from the
perspective of any individual agent. This might cause divergence for value-
based reinforcement learning and very high variance for policy-based
reinforcement learning algorithms. In the literature, researchers propose
multiple methods to apply reinforcement learning algorithms in multi-agent
settings. To name a few, centralized training and distributed execution [34,
38, 39], distributed training and execution under fully-observable
environments [40], and independent Q-learning [41, 42, 43]. However,
independent Q-learning is a value-based reinforcement learning algorithm, and
in this work, we aim to investigate the policy-based reinforcement learning
routing algorithm. The ideas of centralized training and fully observable
state space work well when there exists a small number of agents in the
communication network. With increasing the number of agents, the volume of the
information might overwhelm the capacity of a single unit. To tackle this
problem, one effective idea to remove the central unit and only allow the
agents to share information with only a subset of agents, to reach a consensus
over a variable with these agents (called neighbors) [44, 45]. In this work,
we also leverage the dynamic consensus algorithm to estimate the global reward
function through interactive communication among routers. Moreover, we
consider packet routing in the presence of link failures, indicating that not
only the local environment from the perspective of any individual router is
non-stationary but also the global environment changes during the working
hours. We propose to use model-agnostic meta-learning to learn a well-
generalized policy initialization that is close to all possible environments
such that the policy can be quickly adapted to different scenarios with a few
gradient steps. This is the first time in the literature that the model-
agnostic meta-learning is applied to a multi-agent reinforcement learning
problem case.

##  6 Discussion and Conclusions

In this work, we propose a novel framework MAMRL that utilizes deep policy
optimization and meta-learning to produce a model-free network routing
controller that can perform better path optimization than standard approaches.
Our experiments show that MAMRL can learn to control the communication
networks from its experience rather than an accurate mathematical model.
Specifically, we use deep policy optimization techniques to find optimal paths
in complex WAN topologies. In order to address the difficulties in gathering
information from widely distributed routers, we design a consensus-based
policy optimization algorithm that can learn the local optimal strategy using
only local information. Additionally, we consider path optimization problems
in the presence of link failures and we leverage the model-agnostic meta-
learning algorithm to make the proposed network controller adapt to link
failures more quickly. We demonstrate how MAMRL improves the learning
efficiency of deep reinforcement learning in multi-agent packet routing in the
presence of link failures. The experiments demonstrate the effectiveness and
efficiency of MAMRL for packet routing problem, compared to some baseline
controllers.

The distributed nature of MAMRL lays foundation for our future work, where we
will experiment with on-device traffic engineering in physical network setups
to see how well the network adapts.

##  7 Acknowledgements

We would like to thank Dr. Manya Ghobadi for providing the data of At&T and B4
network topologies. We would like to express our gratitude to Dr. Bashir
Mohammed for his useful suggestions and critiques of this research work. This
work was supported by the U.S. Department of Energy, Office of Science Early
Career Research Program for ‘Large-scale Deep Learning for Intelligent
Networks’ Contract no FP00006145.

## References

  * [1] D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao.  Overview and principles of internet traffic engineering.  RFC3272, 2002.
  * [2] Jeremy Bogle, Nikhil Bhatia, Manya Ghobadi, Ishai Menache, Nikolaj Bjørner, Asaf Valadarsky, and Michael Schapira.  Teavar: striking the right utilization-availability balance in wan traffic engineering.  In ACM Special Interest Group on Data Communication, pages 29–43. 2019.
  * [3] João Luís Sobrinho and Miguel Alves Ferreira.  Routing on multiple optimality criteria.  In Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication, pages 211–225, 2020.
  * [4] Sushant Jain, Alok Kumar, Subhasree Mandal, Joon Ong, Leon Poutievski, Arjun Singh, Subbaiah Venkata, Jim Wanderer, Junlan Zhou, Min Zhu, et al.  B4: Experience with a globally-deployed software defined wan.  ACM SIGCOMM Computer Communication Review, 43(4):3–14, 2013.
  * [5] Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Vijay Gill, Mohan Nanduri, and Roger Wattenhofer.  Achieving high utilization with software-driven wan.  In ACM SIGCOMM conference, pages 15–26, 2013.
  * [6] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484–489, 2016.
  * [7] Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula.  Resource management with deep reinforcement learning.  In ACM Workshop on Hot Topics in Networks, pages 50–56, 2016.
  * [8] Martin Gregurić, Miroslav Vujić, Charalampos Alexopoulos, and Mladen Miletić.  Application of deep reinforcement learning in traffic signal control: An overview and impact of open traffic data.  Applied Sciences, 10(11):4011, 2020.
  * [9] Asaf Valadarsky, Michael Schapira, Dafna Shahaf, and Aviv Tamar.  Learning to route.  In ACM workshop on hot topics in networks, pages 185–191, 2017\.
  * [10] Raouf Boutaba, Mohammad A Salahuddin, Noura Limam, Sara Ayoubi, Nashid Shahriar, Felipe Estrada-Solano, and Oscar M Caicedo.  A comprehensive survey on machine learning for networking: evolution, applications and research opportunities.  Journal of Internet Services and Applications, 9(1):16, 2018.
  * [11] Ramesh Govindan, Ina Minei, Mahesh Kallahalla, Bikash Koley, and Amin Vahdat.  Evolve or die: High-availability design principles drawn from googles network infrastructure.  In ACM SIGCOMM Conference, pages 58–72, 2016.
  * [12] Chi-Yao Hong, Subhasree Mandal, Mohammad Al-Fares, Min Zhu, Richard Alimi, Chandan Bhagat, Sourabh Jain, Jay Kaimal, Shiyu Liang, Kirill Mendelev, et al.  B4 and after: managing hierarchy, partitioning, and asymmetry for availability and scale in google’s software-defined wan.  In ACM Special Interest Group on Data Communication conference, pages 74–87, 2018.
  * [13] Marcos A Simplício Jr, Paulo SLM Barreto, Cintia B Margi, and Tereza CMB Carvalho.  A survey on key management mechanisms for distributed wireless sensor networks.  Computer networks, 54(15):2591–2612, 2010.
  * [14] Hasan AA Al-Rawi, Ming Ann Ng, and Kok-Lim Alvin Yau.  Application of reinforcement learning to routing in distributed wireless networks: a review.  Artificial Intelligence Review, 43(3):381–416, 2015.
  * [15] Lutz Schönemann.  Evolution strategies in dynamic environments.  In Evolutionary Computation in Dynamic and Uncertain Environments, pages 51–77. Springer, 2007.
  * [16] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  International conference on machine learning, 2017.
  * [17] Solmaz S Kia, Bryan Van Scoy, Jorge Cortes, Randy A Freeman, Kevin M Lynch, and Sonia Martinez.  Tutorial on dynamic average consensus: The problem, its applications, and the algorithms.  IEEE Control Systems Magazine, 39(3):40–72, 2019.
  * [18] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In International conference on machine learning, pages 1889–1897, 2015.
  * [19] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel.  Benchmarking deep reinforcement learning for continuous control.  In International Conference on Machine Learning, pages 1329–1338, 2016.
  * [20] Andrew S Tanenbaum et al.  Computer networks.  New Jersey, 1996.
  * [21] Justin A Boyan and Michael L Littman.  Packet routing in dynamically changing networks: A reinforcement learning approach.  In Advances in neural information processing systems, pages 671–678, 1994.
  * [22] Leonid Peshkin and Virginia Savova.  Reinforcement learning for adaptive routing.  In International Joint Conference on Neural Networks., volume 2, pages 1825–1830. IEEE, 2002.
  * [23] Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans.  Bridging the gap between value and policy based reinforcement learning.  Advances in Neural Information Processing Systems, 30:2775–2785, 2017.
  * [24] Hyojun Lim and Chongkwon Kim.  Flooding in wireless ad hoc networks.  Computer Communications, 24(3-4):353–363, 2001.
  * [25] Donald B Johnson.  A note on dijkstra’s shortest path algorithm.  Journal of the ACM, 20(3):385–388, 1973.
  * [26] Chunhsiang Cheng, Ralph Riley, Srikanta PR Kumar, and Jose J Garcia-Luna-Aceves.  A loop-free extended bellman-ford routing protocol without bouncing effect.  ACM SIGCOMM Computer Communication Review, 19(4):224–236, 1989\.
  * [27] Mehran Abolhasan, Tadeusz Wysocki, and Eryk Dutkiewicz.  A review of routing protocols for mobile ad hoc networks.  Ad hoc networks, 2(1):1–22, 2004.
  * [28] Shailesh Kumar and Risto Miikkulainen.  Dual reinforcement q-routing: An online adaptive routing algorithm.  In International Conference on Artificial Neural Networks Engineering, pages 231–238, 1997.
  * [29] Samuel PM Choi and Dit-Yan Yeung.  Predictive q-routing: A memory-based reinforcement learning approach to adaptive traffic control.  In Advances in Neural Information Processing Systems, pages 945–951, 1996.
  * [30] Maksim Kavalerov, Yuliya Likhacheva, and Yuliya Shilova.  A reinforcement learning approach to network routing based on adaptive learning rates and route memory.  In SoutheastCon, pages 1–6. IEEE, 2017.
  * [31] Antonio Mira Lopez and Douglas R Heisterkamp.  Simulated annealing based hierarchical q-routing: a dynamic routing protocol.  In International Conference on Information Technology: New Generations, pages 791–796. IEEE, 2011.
  * [32] Devika Subramanian, Peter Druschel, and Johnny Chen.  Ants and reinforcement learning: A case study in routing in dynamic networks.  In International Joint Conference on Artificial Intelligence, pages 832–839. Citeseer, 1997.
  * [33] Nigel Tao, Jonathan Baxter, and Lex Weaver.  A multi-agent, policy-gradient approach to network routing.  In International Conference on Machine Learning. Citeseer, 2001\.
  * [34] Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In Advances in neural information processing systems, pages 6379–6390, 2017.
  * [35] Dmitry Mukhutdinov, Andrey Filchenkov, Anatoly Shalyto, and Valeriy Vyatkin.  Multi-agent deep learning for simultaneous optimization for time and energy in distributed routing system.  Future Generation Computer Systems, 94:587–600, 2019.
  * [36] Zhiyuan Xu, Jian Tang, Jingsong Meng, Weiyi Zhang, Yanzhi Wang, Chi Harold Liu, and Dejun Yang.  Experience-driven networking: A deep reinforcement learning based approach.  In INFOCOM Conference on Computer Communications, pages 1871–1879. IEEE, 2018.
  * [37] Xinyu You, Xuanjie Li, Yuedong Xu, Hui Feng, Jin Zhao, and Huaicheng Yan.  Toward packet routing with fully distributed multiagent deep reinforcement learning.  IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020\.
  * [38] Shariq Iqbal and Fei Sha.  Actor-attention-critic for multi-agent reinforcement learning.  In International Conference on Machine Learning, pages 2961–2970. PMLR, 2019.
  * [39] Shihui Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell.  Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient.  In AAAI Conference on Artificial Intelligence, volume 33, pages 4213–4220, 2019.
  * [40] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar.  Networked multi-agent reinforcement learning in continuous spaces.  In International Conference on Decision and Control, pages 2771–2776. IEEE, 2018.
  * [41] Matthew Hausknecht and Peter Stone.  Deep recurrent q-learning for partially observable mdps.  arXiv preprint:1507.06527, 2015.
  * [42] Laëtitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat.  Hysteretic q-learning: an algorithm for decentralized reinforcement learning in cooperative multi-agent teams.  In International Conference on Intelligent Robots and Systems, pages 64–69. IEEE, 2007.
  * [43] Jakob Foerster, Nantas Nardelli, Gregory Farquhar, Triantafyllos Afouras, Philip HS Torr, Pushmeet Kohli, and Shimon Whiteson.  Stabilising experience replay for deep multi-agent reinforcement learning.  In International Conference on Machine Learning, pages 1146–1155, 2017.
  * [44] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong.  Multi-agent reinforcement learning via double averaging primal-dual optimization.  In Advances in Neural Information Processing Systems, pages 9649–9660, 2018.
  * [45] Huaguang Zhang, He Jiang, Yanhong Luo, and Geyang Xiao.  Data-driven optimal consensus control for discrete-time multi-agent systems with unknown dynamics using reinforcement learning method.  IEEE Transactions on Industrial Electronics, 64(5):4091–4100, 2016\.

##  Appendix A Appendix

Here, we provide the derivation of Equation (2). All the notations carry the
same meaning as those in Section 2.2. The probability of a trajectory
$\tau=(s_{0},a_{0},\cdots,s_{H},a_{H},S_{H+1})$ given that actions come from
$\pi_{\theta}$ is,

$\displaystyle P(\tau|\pi_{\theta})$
$\displaystyle=\rho(s_{0})\Pi_{t=0}^{H}P(s_{t+1}|s_{t},a_{t})\pi_{\theta}(a_{t}|s_{t})$
(7)
$\displaystyle=\rho(s_{0})\Pi_{t=0}^{H}P(s_{t+1}|s_{t},a_{t})\Pi_{i=1}^{n}\pi^{i}_{\theta^{i}}(a_{t}^{i}|o_{t}^{i})$

The log-probability of a trajectory is

$\displaystyle\log P(\tau|\pi_{\theta})$
$\displaystyle=\log\rho(s_{0})+\sum_{t=0}^{H}\log\left[P(s_{t+1}|s_{t},a_{t})\Pi_{i=1}^{n}\pi^{i}_{\theta^{i}}(a_{t}^{i}|o_{t}^{i})\right]$
(8)
$\displaystyle=\log\rho(s_{0})+\sum_{t=0}^{H}\log\left[P(s_{t+1}|s_{t},a_{t})\right]$
$\displaystyle\qquad+\sum_{t=0}^{H}\sum_{i=1}^{n}\log\left[\pi^{i}_{\theta^{i}}(a_{t}^{i}|o_{t}^{i})\right].$

The gradient of the log-probability of a trajectory is

$\displaystyle\nabla_{\theta}\log P(\tau|\pi_{\theta})$
$\displaystyle=\nabla_{\theta}\log\rho(s_{0})+\sum_{t=0}^{H}\nabla_{\theta}\log\left[P(s_{t+1}|s_{t},a_{t})\right]$
(9) $\displaystyle\hskip
43.36243pt+\sum_{t=0}^{H}\sum_{i=1}^{n}\nabla_{\theta}\log\left[\pi^{i}_{\theta^{i}}(a_{t}^{i}|o_{t}^{i})\right]$
$\displaystyle=\sum_{t=0}^{H}\sum_{i=1}^{n}\nabla_{\theta}\log\pi^{i}_{\theta^{i}}(a_{t}^{i}|o_{t}^{i}),$

and thus

$\displaystyle\nabla_{\theta^{i}}\log
P(\tau|\pi_{\theta})=\sum_{t=0}^{H}\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(a_{t}^{i}|o_{t}^{i}).$
(10)

Putting the above equations together, we have the following

$\displaystyle\nabla_{\theta^{i}}J(\theta)$
$\displaystyle=\nabla_{\theta^{i}}\mathbb{E}[R(\tau)]$ (11)
$\displaystyle=\nabla_{\theta^{i}}\int_{\tau}P(\tau|\pi_{\theta})R(\tau)=\int_{\tau}\nabla_{\theta^{i}}P(\tau|\pi_{\theta})R(\tau)$
$\displaystyle=\int_{\tau}P(\tau|\pi_{\theta})\nabla_{\theta^{i}}\log
P(\tau|\pi_{\theta})R(\tau)$
$\displaystyle=\mathbb{E}\left[\nabla_{\theta^{i}}\log
P(\tau|\pi_{\theta})R(\tau)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{H}\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(a_{t}^{i}|o_{t}^{i})R(\tau)\right].$