individually review each of the negative videos to ensure that it really was
not an event video.777777However, Strassel et al. point out that, due to
ongoing changes in the process and target events, HAVIC’s negative set is not
free of accidental positives either (2012). (Again, due to practicalities of
scale.) While we did take other steps to try to screen out possible event
videos, as described in §2.4, it is likely that up to 1.6% of the videos
labeled None of the Above are actually positive instances, near misses, or
related videos—especially for the events most heavily represented in the
YFCC100M (see Table 8). These miscategorized videos will share the
characteristic of not being easy for an English speaker to search for based on
textual metadata (see §4.1.4).787878In addition to the known procedural
differences discussed in this section, there are some potentially biasing
procedural points where we don’t know whether YLI-MED and HAVIC differed. For
example, it is not clear from the published documentation whether HAVIC data
scouts were specifically encouraged to use non-English search terms, as ours
were (though HAVIC certainly includes non-English videos), nor is it clear
whether there were limits on videos per user for the TRECVID MED data.

One area in which both YLI-MED and HAVIC may differ from other corpora is that
the near misses and related videos are separated from the true negatives
(which are completely unrelated to any target event). This necessarily means
that the negatives set contains fewer of these borderline cases, and that
researchers need to decide whether to explicitly include them in a given
training or test run. However, given the relatively small number of near
misses and related videos included in YLI-MED, and the fact that the negatives
have not been exhaustively cleared of such cases, we assume that there are
still many near misses and related videos in the negatives set (especially for
the videos where we did not have to cast as wide a search net to find the
positives). In addition, the fact that the negative sets for both corpora
(mostly) do not include videos with the target events may skew the overall
subject matter of the negatives somewhat away from the domains in which those
events are likely to occur. For example, NIST’s (and thus our) events are less
likely to involve the commercial, military, work, or entertainment domains.

####  4.1.4 Are There Biases No Search Method Can Avoid?

There are some ways in which any event corpus constructed by searching on the
user-supplied metadata for user-generated content would likely be skewed,
i.e., would not reflect the actual distribution of videos depicting those
events along all possible dimensions throughout the source data or in
comparison with all of the online videos in existence.797979The least bias-
inducing method, of course, would be to simply review every video in the
dataset (or every video on the web) to see whether it depicted any of the
target events. This is not feasible to do every time one wants to develop a
new set of event classifiers. However, there are some reasonable compromises:
blanket annotation/tag refinement of a corpus with a rough idea of what it
might be used for can at least provide better searchability than relying
solely on user-supplied metadata. We are therefore moving towards providing a
full set of basic annotations for the YFCC100M: essentially, a Multimedia
Genome Project (see §5.2). These factors will not necessarily make YLI-MED
different from other UGC video corpora (all constructed from such searches),
but some are nonetheless worth noting.

To begin with, such a corpus is not going to include videos where the user
simply did not supply metadata. In addition, it will include (mostly) videos
where at least some of the textual metadata is descriptive of the content of
the video—rather than, for example, descriptions of the camera, reasons for
posting (“Thought this was interesting”), or random unrelated rants (Ulges et
al. 2010). Further research is necessary to discover what the consequences of
these factors may be for corpus composition and distribution, but
possibilities that might be explored include biases against politically
subversive content (which a poster might not want to make directly
searchable), against highly artistic videos (where the aesthetic might be more
noteworthy than what is depicted), or against didactic videos (where the
metadata might reflect the content taught rather than what occurs in the
video).

Even where the textual metadata is descriptive of the video content, the video
will not be found if it doesn’t match the aspect of the video the searcher is
looking for or is not phrased in a way the searcher might expect. For example,
the description “Me and Sasha at Dynamo’s last Friday” is quite specific, but
will not be helpful to someone searching for event examples. Previous research
has shown that Flickr users are more likely to tag people and places than
story content in videos (Rorissa 2010), indicating that events may generally
be one of the less searchable aspects of videos in the first place.

One very speculative possibility is that an event corpus might contain fewer
videos that feature particularly notable places and people, if notability
affects which tags are chosen (and what shows up in titles, etc.), at least by
less voluble uploaders. (If you get a shot of Beyoncé digging her car out of a
snowbank, is your description more likely to feature the stuck vehicle or
Beyoncé? Would it be different for a shot of your neighbor doing the same
thing?) Again, these are all empirical questions, which we hope to explore in
future research.

In addition, videos found through textual metadata may be less likely to be
from batch uploads. For example, if someone is uploading a large batch of
vacation videos without labeling them individually, the tags will more likely
be general descriptors (“Barcelona 2014”) rather than descriptions of specific
activities in the videos. (Though for events like Ev101 Birthday Party that
tend to cover a longer timespan with less unified activities, batch-labeled
videos may be more likely.) It is not known whether batch-labeled videos have
any particular characteristics in common that a search-collected video corpus
would be skewed away from.

As well as the language of the video being familiar to (at least one of) the
corpus-builders, there are other characteristics of videos that might make it
easier to decide whether a target event is occurring, such as explicit
internal descriptions of what’s happening, like narration or titles. Length
may also have an effect on interpretability; the average length for the YLI-
MED positive videos is ~45 seconds, while the average length is ~40 seconds
for YFCC100M as a whole.808080This figure is interesting, but not conclusive,
given that videos of less than 3 seconds were explicitly excluded from the
YLI-MED positives even in those rare cases where they might have been
interpretable to the annotators.

While quantitative testing of these speculations would require an entire
dataset annotated for the relevant features, some preliminary insights can be
gained from the data described in §3.5. For example, post-production text
(like titles and subtitles) did not significantly affect YLI-MED annotators’
stated confidence in their judgments nor agreement between annotators, but
whether or not the language (spoken or text) was English affected both.
Confidence and annotator agreement do not necessarily predict skew in corpus
composition, but may provide an indirect indicator.

Finally, there are some biases that would not be helped even by individually
reviewing every video on the Internet for possible corpus inclusion. The most
obvious is against videos with a low-quality signal in one or both data
streams, making it difficult to determine whether an event is in fact
occurring (especially if there is no supporting metadata). However, while it
is generally helpful for classification algorithms to be able to deal with
somewhat low-quality videos even for consumer applications, if the quality is
so poor that the humans constructing the corpus can’t identify the event, it
is unlikely to be a useful retrieval result in any case.

###  4.2 Intentional Compositional Differences from HAVIC

Some differences between the characteristics of YLI-MED and those of
HAVIC/TRECVID MED were intentional desiderata, not just chance consequences of
procedure or base dataset choice.

For example, HAVIC does not include animated videos/CGI (nor screencasts),
which are always constructed (never natural) and present a different set of
challenges for visual analysis than live recordings. However, HAVIC does
include videos that have no audio track at all, which are, of course, simply
unanalyzable in the audio stream. For YLI-MED, we required that positive
examples (and near misses/related videos) have data in both the audio and
visual streams—i.e., that they be multimedia.818181It is possible that this
choice also introduced unintended differences, in that videos without sound
may be biased in some other direction—towards lower-quality cameraphones,
perhaps—though the effect is likely negligible at the scale of the whole
corpus. However, we did not impose any requirements about the type of data in
either stream, as long as one or the other provided evidence for the
event—i.e., as long as it would likely be considered a good retrieval result
by a user. (Both HAVIC and YLI-MED include videos where the visual track is
live video (or a photo montage) but the audio consists only of a music track.
In such cases, the audio data represents a separate event (i.e., a music
performance) from the original live recording we are targeting, but it is
nonetheless data.)

Similarly, our choice to include videos with non-human protagonists was
intentional. Our goal is to improve video retrieval for the general public,
who might well consider a video depicting robots or anthropomorphized animals
celebrating a birthday to be a perfectly good example of a birthday-party
video. It is not clear what consequences this might have for classification,
though one can imagine some possibilities: for example, the colors and shadows
on a robot’s face reflecting a birthday-candle flame might not be detected in
the same way that a human’s would. However, it should be noted that the events
targeted for YLI-MED Version 1 most often have human protagonists, and thus
the vast majority of the videos do feature humans in the leading roles.

Finally, while it is not a difference in likely corpus composition, it is
worth mentioning here that the additional annotations (beyond the event ID)
chosen for HAVIC and YLI-MED differ according to feasibility and to the
interests of the likely users of the corpora. Most importantly, we include in
YLI-MED explicit annotations for each video about degree of annotator
agreement and about the average annotator confidence in their judgments; we
invite users to experiment with how using this information in various ways
affects classifier performance and human perception of the usefulness of
retrieval results.

###  4.3 In the End, Is YLI-MED Comparable to Similar Corpora?

To get some initial hints about how choice of base dataset and differences in
collection procedures might actually affect research using the two corpora, we
performed some rough experiments comparing YLI-MED Version 1 with the parallel
sets of HAVIC videos used in TRECVID MED 2011 and later evaluations.
Restrictions on the use of HAVIC data prevent us from making a direct
comparison, i.e., training am event-detection system on one set and testing on
the other. However, we can at least compare accuracy results for training and
testing a system on YLI-MED Version 1.2 with parallel results for training and
testing the same system on TRECVID MED data when we participated in the
evaluations that included those events.

The system we chose for the comparison is based on an i-vector approach
initially developed by Dehak et al. (2009), with an improvement by Burget et
al. (2011). It involves training a matrix $T$ to model the total variability
of a set of statistics for each video’s audio track, primarily the first-order
Baum-Welch statistics of the low-level acoustic feature frames (namely, Mel
frequency cepstral coefficients). The i-vectors for each event class are
averaged, so that each class is represented by one i-vector, then a generative
Probabilistic Linear Discriminant Analysis (pLDA) (Ioffe 2006) log-likelihood
ratio is used to obtain a similarity score between each test audio and each
training event class. Full details about the i-vector system and some of our
research using it with the TRECVID MED data may be found in Elizalde et al.
2013.

In addition to the work described in Elizalde et al. 2013, we used the
i-vector approach to provide audio analysis for SRI-Sarnoff’s AURORA
multimedia event detection and retrieval system when it competed in TRECVID in
2012 and 2013 (Cheng et al. 2012; Liu et al. 2013). Table 25 compares the
event-detection performance of the i-vector system trained and tested on the
TRECVID MED 2011 and 2013 data vs. the same system trained and tested on YLI-
MED.828282Cheng et al. 2012 and Liu et al. 2013 do not report individual
results from each of the subcomponents of the AURORA system. The numbers shown
in Table 25 represent the accuracy for the i-vector system alone, when it was
used in the experiments described there. The accuracy data for Attempting a
Board Trick, Feeding an Animal, Landing a Fish, Wedding Ceremony, and Working
on a Woodworking Project are from 2012 experiments that used the TRECVID MED
2011 DEV-T dataset, while the accuracy data for Birthday Party, Flash Mob
Gathering, Getting a Vehicle Unstuck, Parade, and Grooming an Animal are from
2013 experiments that used the TRECVID MED 2013 MEDTest dataset. In each case,
there were two experimental runs, one with negatives and one without
negatives.

Table 25: Accuracy scores for an i-vector event detection system trained and
tested on YLI-MED Version 1.2 vs. the TRECVID MED 2011 and 2013 datasets, and
statistical significance of the differences between scores for each event.
(Colors indicate scaled accuracy rankings within each experimental condition.
Statistically significant differences are shown in boldface italics, with
marginally significant differences in boldface alone.)

It is important to note at the outset that there were many factors at play,
and it is difficult to say how much the results shown in Table 25 tell us
about the audio characteristics of the two datasets as opposed to how much
they tell us about other aspects of the experimental conditions or about the
robustness and generalizability of the i-vector approach. In addition to the
fact that the event sets are (largely) composed of different videos
(determined in part by the factors mentioned in mentioned in §4.1 and §4.2),
they also differ in the total numbers of training and test files for each
event. Other factors were more extrinsic to the event set makeup, such as the
fact that the experiments with the TRECVID MED data involved 15 or 20 events
rather than 10, so the range of possible (mis)classifications was
different.838383This discrepancy in the total number of possible categories
makes it more convenient to present results here in terms of accuracy scores,
which are easier to compare across such different cases than mean average
precision (MAP) or other metrics more often used in the TRECVID community. In
addition, the ratio of negatives to positives is much higher for YLI-MED
Version 1, at around 27:1, as opposed to 7:1 for TRECVID MED.

Given these factors, we cannot use these data to make definitive statements
about the similarity of the two corpora, even within the audio domain.
However, we can at least sketch a few observations. First, the combined
accuracy scores for the ten events were quite similar between the TRECVID and
the YLI-MED runs within each condition (positives only vs. positives and
negatives).848484Note that the overall accuracy scores given for TRECVID
combine the scores for only these ten events, not the overall scores for each
whole run, which included other events.  The small difference between the
scores for the positive-only runs was not at all statistically
significant—though for the runs with both positives and negatives (which
introduced even more differences in the overall experimental conditions), the
difference was on the threshold of significance (Fisher’s exact test, two-
tailed).

However, looking at the individual event accuracies that make up that overall
score, we see a rather different picture. Looking first at the gross accuracy
for each event, we find that detectors trained on the two corpora performed
rather differently (at least when tested on videos from those same corpora).
Those differences meet the threshold for statistical significance for most of
the individual events for the positives-only runs, and for about half of the
events for the runs with both positives and negatives. In addition, even where
the differences do not meet the threshold of significance for assuming the
scientific validity of the apparent effect, the p-values are often still
rather low, i.e., the likelihood is still fairly high that the effect is not
just random chance. (In fact, none of the p-values for individual events
exceed 0.9.)

There is a greater range in accuracy across events for detectors trained and
tested on YLI-MED data than TRECVID data. This wider scatter necessarily
introduces wider differences between the gross accuracies that might obscure
similarities in the overall patterns of which events the system performs
better and worse on when trained and tested on the two datasets. We therefore
also examined the rankings of the accuracy scores for the different events
under each experimental condition; these (scaled) rankings are represented by
shading in Table 25.

For example, the i-vector system did best at detecting birthday parties on
both corpora and under all conditions, while animal grooming was near the
bottom for both—even though the gross accuracy scores for Birthday Party
showed a statistically significantly difference. However, on the whole, the
matches and near-matches in event rankings for the positives-only runs do not
rise above what would be predicted for two randomly ordered lists. For the
runs with both positive and negative videos, the similarities in ranking
patterns are more robust (rising above chance), with three exact rank matches
(Birthday Party, [Person] Attempting a Board Trick, and [Person Hand-]Feeding
an Animal), as well as an additional two events for which the accuracy
rankings are off by only one step and one additional event for which the
ranking is off by two steps. Looking at broad groupings rather than exact
rankings, we find that the accuracy results for the positives-only runs fell
into the same trentile for only three of the events, which would be predicted
for random chance. In the runs with both positives and negatives, accuracies
fell into the same trentile for six events, a bare majority.

Taking all these patterns together, the i-vector system appears to perform
somewhat similarly in terms of which events it is better and worse at
detecting in the two datasets when negative examples are included. When
negatives are not included, there do not seem to be even such weak inter-event
patterns.

Again, without being able to perform a more direct comparison of detectors
trained on the two datasets, it is difficult to determine the sources of
difference.858585We cursorily examined a few obvious potential factors, such
as the numbers of videos in the test sets from the two corpora and the
difficulty of finding videos for those events for YLI-MED, but found no
obvious correlation with similarity in gross accuracy nor similarity in
accuracy rankings. The discussion thus far assumes that the training and test
videos within a given corpus have close to the same distribution of audio
characteristics for each event (though see §3.4). But it is possible that
disparities in performance for the same system learning to detect the same
event on the two different corpora may simply be an effect of there being more
difference between the training and test sets for one corpus than the other.

These i-vector experiments are, of course, only one means of getting at this
question. At the least, it is quite possible that other audio-analysis
approaches would be more or less robust to the differences between corpora,
and detection systems using the visual-stream data from the two corpora might
produce quite different results. However, we can at least tentatively say that
the two corpora, though both relying on UGC and constructed with relatively
similar desiderata, are disparate in ways that affect detection performance.

The general assumption in the multimedia-retrieval community has been that, as
corpora get bigger, the models trained on them will get more generalizable.
However, according to the results described here, we cannot assume that event
models trained on either YLI-MED or TRECVID would be generalizable to other
UGC video corpora. Thus, although we may be making progress on
generalizability, even corpora as large as YLI-MED and TRECVID MED are not yet
sufficient for this task.

We are currently working on a number of additional experiments to quantify the
generalizability of classifiers trained on the YLI-MED, in tandem with testing
the scalability of new classification and detection approaches. The YLI corpus
includes multimedia-analysis tools being created at ICSI and University of
California–Berkeley, including audioCaffe (Ashraf et al. ), a set of audio
content-analysis tools based on the deep neural net (DNN) image-analysis
framework Caffe (Jia et al. 2014). We are training DNNs on the YLI-MED corpus,
using the MFCC audio features (Mel frequency cepstral coefficients), and
comparing them with the i-vector results to explore trade-offs between
accuracy and efficiency (Ashraf et al. )—and meanwhile evaluating the
comparability of YLI-MED and the TRECVID MED data.

##  5 The Bigger Picture for YLI-MED

Here, we discuss how the YLI-MED annotations fit in with other current and
planned efforts to make the YLI corpus a maximally useful resource for a broad
sector of multimedia researchers, including the ongoing extraction of audio
and visual features (§5.1) and future annotation efforts (§5.2).

###  5.1 Feature Computation

The goal of the YLI corpus is to provide researchers with a multitude of pre-
computed data to work with for each of the media files in the Yahoo Flickr
Creative Commons 100 Million, to allow research teams to focus on conducting
experiments rather than on computing statistics and features. Researchers at
Lawrence Livermore National Laboratory and ICSI have been computing visual,
audio, and motion features commonly used in multimedia analysis, using LLNL’s
Cray Catalyst, and making them available to the public. The visual features
span the gamut of global (e.g., Gist), local (e.g., SIFT), and texture (e.g.,
Gabor) descriptors; the audio features include power spectrum (e.g., MFCC) and
frequency (e.g., Kaldi) descriptors; and the motion features will begin with
dense trajectories (Ni et al. 2014).

Audio features and LIRE image features for all of the videos in YFCC100M have
already been released.868686http://www.yli-corpus.org/computed-features Many
more visual and motion features are scheduled to be released over the coming
months; the full list includes:

  * •

Audio features:

    * –

MFCC20s (Mel frequency cepstral coefficients, 19 channels plus energy)

    * –

Kaldi pitch

    * –

SAcC pitch (subband autocorrelation classification)

  * •

Image features on video keyframes:

    * –

Gist features

    * –

LIRE features: auto color correlogram, basic features, CEDD (color and edge
directivity descriptor), color layout, edge histogram, fuzzy color and texture
histogram (FCTH), fuzzy opponent histogram, Gabor features, joint histogram,
joint opponent histogram, scalable color, simple color histogram (RGB), Tamura
texture

    * –

AlexNet features

    * –

SIFT features

  * •

Motion features:

    * –

Dense trajectory features

A subset of the YLI corpus data, including the computed features, was already
used in the MediaEval 2014 Placing Task, and additional YLI data will be added
in 2015 and 2016 (Choi et al. 2014).

We are also releasing convenient bundles of features just for YLI-MED, ahead
of the releases for the full YLI corpus. A first bundle of features, including
Kaldi pitch, SAcC pitch, and MFCCs (audio) and AlexNet and LIRE (image) for
(most of) the positive-example videos in YLI-MED, was released in November
2014 and is available at http://www.yli-corpus.org/the-yli-med-corpus. A full
bundle for those features, covering all of the videos in YLI-MED, will be
available in late spring 2015, with additional features continually being
added.

Details of the YLI feature-computation procedures and technical basis can be
found in Ni et al. 2014 and Choi et al. 2014. While the features for YLI-MED
were computed separately, the organization and rationale mirror that of the
full YLI feature corpus.

###  5.2 Next Steps for YLI-MED

We are currently moving towards launching a full-fledged “Multimedia Genome
Project” (MMGP), in collaboration with Lawrence Livermore National Laboratory.
In the MMGP, we hope to provide reliable human-generated labels for all of the
~800,000 videos in YFCC100M, using a combination of crowdsourcing and expert
annotation. The MMGP will include a heavy emphasis on multimedia event
annotation, including loose annotations for the whole corpus as well as
defined sets of training and test data for specific well-defined events like
those described here. In particular, we hope to add twenty to fifty new events
to the YLI-MED, including new events never seen in TRECVID.

We anticipate that having such a large-scale, open-source annotated corpus of
user-generated videos will truly be a game-changer for multimedia research.
The MMGP will provide a basis for collaboration and exploration that pushes
the boundaries of multimedia analysis and retrieval; for example, it has the
potential to enrich our understanding of the relationship between more high-
level characteristics like multimedia events and more concrete, localizable
characteristics like audio concepts. We hope such a project will lead to new
methods of inquiry that would not otherwise be possible, encourage the
development of new data analysis tools and algorithms, and support students
and new researchers who might not otherwise have access to large, high-quality
video corpora.

We have already received a great deal of interest in the projected MMGP effort
from leaders in event detection as well as other multimedia subfields. In the
long term, it has the potential to become the basis for major collaborative
research and evaluation efforts. The idea is also of interest to commercial
multimedia research and development, and we are already working on developing
collaborations that could support better access to the YLI data, including
YLI-MED.

In the short term, the next step is to develop and release Version 2 of YLI-
MED, with at least five new events. In the first round of annotations, we
chose TRECVID MED events in order to provide a basis for comparison for
researchers in that community. In the second round, we will branch out and
explore an area that TRECVID specifically does not, focusing on events that
prototypically have non-human protagonists. In this second round, we will
likely choose a more closely related set of events within a single conceptual
domain, offering a different set of challenges for classification than more
distantly related events. We will also include new non-event annotations for
additional important video characteristics, such as narration, content text,
and use of static images.

##  6 Acknowledgments

This annotation effort is vitally connected to the work of the researchers at
ICSI and Lawrence Livermore National Laboratory who are computing the audio,
visual, and motion features for the videos in the YLI-MED corpus, including
Jaeyoung Choi (ICSI) and Carmen Carrano, Karl Ni, Roger Pearce, and Doug
Poland (LLNL), in addition to some of the authors.

YLI-MED would not have been possible without the efforts of the researchers at
Yahoo Labs who produced the YFCC100M dataset in the first place, including
Bart Thomee, Li-Jia Li, Nikhil Rasiwasia, and David Ayman Shamma, along with
the Yahoo Webscope and Legal teams.

The YLI-MED annotation project described here was funded by a grant from Cisco
Systems, Inc., for Event Detection for Improved Speaker Diarization and
Meeting Analysis. In addition to Cisco, ICSI’s work on the YLI corpus
(generally) is funded by Lawrence Livermore National Laboratory as part of a
collaborative Laboratory Directed Research and Development project under the
auspices of the U.S. Dept. of Energy (contract DE-AC52-07NA27344) and by the
National Science Foundation as part of SMASH: Scalable Multimedia content
AnalysiS in a High-level language (grant IIS-1251276). Any opinions, findings,
and conclusions or recommendations are those of the authors and do not
necessarily reflect the views of Cisco, LLNL, nor the NSF.

Questions and requests for further information may be directed to jbernd@yli-
corpus.org.

## References

  * [1] Khalid Ashraf, Benjamin Elizalde, Forrest Iandola, Matthew Moskewicz, Julia Bernd, Gerald Friedland, and Kurt Keutzer.  Audio-based multimedia event detection with DNNs and sparse sampling.  Under submission: ICMR 2015.
  * Borth et al. [2013] Damian Borth, Rongrong Ji, Tao Chen, Thomas Breuel, and Shih-Fu Chang.  Large-scale visual sentiment ontology and detectors using adjective noun pairs.  In Proceedings of the 21st ACM International Conference on Multimedia, pages 223–232. Association for Computing Machinery, 2013.
  * Burget et al. [2011] Lukáš Burget, Oldřich Plchot, Sandro Cumani, Ondřej Glembek, Pavel Matějka, and Niko Brümmer.  Discriminatively trained probabilistic Linear Discriminant Analysis for speaker verification.  In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011, May 22–27, 2011, Prague, Czech Republic, 2011.
  * Cheng et al. [2012] Hui Cheng, Jingen Liu, Saad Ali, Omar Javed, Qian Yu, Amir Tamrakar, Ajay Divakaran, Harpreet S. Sawhney, R. Manmatha, James Allan, Alex Hauptmann, Mubarak Shah, Subhabrata Bhattacharya, Afshin Dehghan, Gerald Friedland, Benjamín Martinez Elizalde, Trevor Darrell, Michael Witbrock, and Jon Curtis.  SRI-Sarnoff AURORA system at TRECVID 2012: Multimedia event detection and recounting.  In TREC Video Retrieval Evaluation: Notebook Papers and Slides, 2012.
  * Choi et al. [2014] Jaeyoung Choi, Bart Thomee, Gerald Friedland, Liangliang Cao, Karl Ni, Damian Borth, Benjamin Elizalde, Luke Gottlieb, Carmen Carrano, Roger Pearce, and Doug Poland.  The Placing Task: A large-scale geo-estimation challenge for social-media videos and images.  In Proceedings of the ACM Multimedia 2014 Workshop on Geotagging and Its Applications in Multimedia (GeoMM ’14), Orlando, FL, November 2014. Association for Computing Machinery.
  * Dehak et al. [2009] Najim Dehak, Réda Dehak, Patrick Kenny, Niko Brümmer, Pierre Ouellet, and Pierre Dumouchel.  Support vector machines versus fast scoring in the low-dimensional total variability space for speaker verification.  In Proceedings of INTERSPEECH, UK, 2009.
  * Elizalde et al. [2013] Benjamin Elizalde, Howard Lei, and Gerald Friedland.  An i-vector representation of acoustic environments for audio-based video event detection on user generated content.  In Proceedings of the IEEE International Symposium on Multimedia (ISM 2013), pages 114–117, 2013.
  * Fillmore [1985] Charles J. Fillmore.  Frames and the semantics of understanding.  Quaderni di Semantica, 6(2), 1985.
  * Guy and Tonkin [2006] Marieke Guy and Emma Tonkin.  Folksonomies: Tidying up tags.  D-Lib Magazine, 12(1), 2006.
  * Ioffe [2006] Sergey Ioffe.  Probabilistic linear discriminant analysis.  In ECCV’06: Proceedings of the 9th European conference on Computer Vision, pages 531–542, 2006.
  * Jia et al. [2014] Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey Karayev, Jonathan Long, Ross B. Girshick, Sergio Guadarrama, and Trevor Darrell.  Caffe: Convolutional architecture for fast feature embedding.  CoRR (arXiv.org), abs/1408.5093, 2014.  Preprint.
  * Lakoff [1987] George Lakoff.  Women, Fire, and Dangerous Things: What Categories Reveal about the Mind.  University of Chicago Press, Chicago, 1987.
  * Liu et al. [2013] Jingen Liu, Hui Cheng, Omar Javed, Qian Yu, Ishani Chakraborty, Weiyu Zhang, Ajay Divakaran, Harpreet S. Sawhney, James Allan, R. Manmatha, John Foley, Mubarak Shah, Afshin Dehghan, Michael Witbrock, Jon Curtis, and Gerald Friedland.  SRI-Sarnoff AURORA system at TRECVID 2013: Multimedia event detection and recounting.  In TREC Video Retrieval Evaluation: Notebook Papers and Slides, 2013.
  * Mervis and Rosch [1981] Carolyn Mervis and Eleanor Rosch.  Categorization of natural objects.  Annual Review of Psychology, 32:89–115, 1981.
  * National Institute of Standards and Technology [2011] National Institute of Standards and Technology.  2011 TRECVID multimedia event detection track.  http://www.nist.gov/itl/iad/mig/med11.cfm, August 2011.  Web page.
  * Ni et al. [2014] Karl S. Ni, Carmen C. Carrano, Doug N. Poland, Benjamin M. Elizalde, Gerald Friedland, Luke R. Gottlieb, and Damian S. Borth.  The Yahoo-Livermore-ICSI (YLI) multimedia feature set.  Technical Report LLNL-MI-659231, Lawrence Livermore National Laboratories, August 2014.
  * Over et al. [2012] Paul Over, George Awad, Jonathan Fiscus, Brian Antonishek, Martial Michel, Alan Smeaton, Wessel Kraaij, and Georges Quénot.  TRECVID 2011 - an overview of the goals, tasks, data, evaluation mechanisms, and metrics.  Technical report, National Institute of Standards and Technology, Gaithersburg, MD, May 2012.
  * Petkos et al. [2014] Georgios Petkos, Symeon Papadopoulos, Vasileios Mezaris, Raphael Troncy, Philipp Cimiano, Timo Reuter, and Yiannis Kompatsiaris.  Social Event Detection at MediaEval: a three-year retrospect of tasks and results.  In Proceedings of the ACM ICMR 2014 Workshop on Social Events in Web Multimedia (SEWM), 2014.
  * Rorissa [2010] Abebe Rorissa.  A comparative study of Flickr tags and index terms in a general image collection.  Journal of the American Society for Information Science and Technology, 61(11):2230––2242, 2010.
  * Rosch [1977a] Eleanor Rosch.  Human categorization.  In N. Warren, editor, Studies in Cross-Cultural Psychology. Academic Press, London, 1977.
  * Rosch [1977b] Eleanor Rosch.  Principles of categorization.  In Eleanor Rosch and Barbara B. Lloyd, editors, Cognition and categorization, pages 27–48. Lawrence Erlbaum, Hillsdale, NJ, 1977.
  * Smeaton et al. [2006] Alan F. Smeaton, Paul Over, and Wessel Kraaij.  Evaluation campaigns and TRECVid.  In MIR ’06: Proceedings of the 8th ACM International Workshop on Multimedia Information Retrieval, pages 321–330, New York, NY, 2006. Association for Computing Machinery.
  * Strassel et al. [2012] Stephanie Strassel, Amanda Morris, Jonathan Fiscus, Christopher Caruso, Haejoong Lee, Paul Over, James Fiumara, Barbara Shaw, Brian Antonishek, and Martial Michel.  Creating HAVIC: Heterogeneous audio visual Internet collection.  In Nicoletta Calzolari, Khalid Choukri, Thierry Declerck, Mehmet Uğur Doğan, Bente Maegaard, Joseph Mariani, Jan Odijk, and Stelios Piperidis, editors, Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC ’12), Istanbul, Turkey, May 2012. European Language Resources Association (ELRA).
  * Thomee et al. [2015] Bart Thomee, David A. Shamma, Benjamin Elizalde, Gerald Friedland, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li.  The new data and new challenges in multimedia research.  Communications of the ACM, 2015.  Under submission. Preprint available at http://arxiv.org/abs/1503.01817.
  * Ulges et al. [2010] Adrian Ulges, Damian Borth, and Thomas M Breuel.  Visual concept learning from weakly labeled web videos.  In Dan Schonfeld, Caifeng Shan, Dacheng Tao, and Liang Wang, editors, Video Search and Mining, pages 203–232. Springer, 2010.
  * Ulges et al. [2012] Adrian Ulges, Markus Koch, and Damian Borth.  Linking visual concept detection with viewer demographics.  In Proceedings of the 2nd ACM International Conference on Multimedia Retrieval, page 24. ACM, 2012.
  * Ulges [2009] Adrian Ulges.  Visual Concept Learning from User-Tagged Web Video.  PhD thesis, Universität Kaiserslautern, October 2009.
  * Yahoo Labs [2014] Yahoo Labs.  Yahoo! Webscope dataset YFCC-100M.  http://labs.yahoo.com/Academic_Relations, June 2014.

##  Appendix A Event Definitions for the YLI-MED Corpus

### Introduction for the Corpus-Builders878787This introduction and
definitions were originally intended as instructions for the video collectors
and verifiers who built the YLI-MED corpus. They are framed for that purpose,
and assume a certain amount of background knowledge. Copies of the full
instructions provided to the corpus-builders, as well as definitions for the
five events that were not included in the final corpus, may be obtained by
emailing<EMAIL_ADDRESS>
The event definitions/schemas and decision rubrics in this document are
intended to help you identify positive instances of each type of event. Where
a rubric says something “does not qualify” or “should not be included”, that
means it should not be included as a positive instance; however, it might well
still qualify as a ‘near miss’ or a ‘related video’ for that category. We
assume it will be relatively easy for you to make decisions about the most
prototypical instances of a given event type, and more difficult to make
decisions about the less prototypical instances (at the boundaries of the
category).888888Not required reading, but might be fun:
https://en.wikipedia.org/wiki/Prototype_Theory. The bulk of the decision
rubrics are therefore devoted to what to do with the boundary cases, rather
than the easy cases that will probably be most of what you find.

What’s an event? For the purposes of this task, an event “is a complex
activity occurring at a specific place and time; … consists of a number of …
actions, processes, and activities that are loosely or tightly organized and
that have significant temporal and semantic relationships to the overarching
activity; and is directly observable [via at least one sensory modality]”
(modified from NIST’s definition of an “event” for the TRECVID MED
evaluations898989http://www.nist.gov/itl/iad/mig/med11.cfm).

What’s a person? A “person” for the purposes of these definitions includes not
only humans but also other agentive beings,909090For these purposes, an
agentive being is an animate being or entity—or a being or entity that can be
construed as animate—that is understood as having the capacity to choose its
actions intentionally. if they are obviously intended to be anthropomorphic in
some way. In live video, “people” may include animals or robots, if the
creator of the video and/or the participants are obviously anthropomorphizing
them (this may include animals trained to mimic human behaviors). In an
animated video, “people” may include almost anything, if they have human-like
behavior and speech.

###  Event Name: Birthday Party (Ev101)

Definition: Multiple people gather for a social event whose purpose is to
celebrate someone’s birthday, by engaging in some special activities that are
intended to be enjoyable.

Decision Rubrics/Clarifications:

  * •

A party is a specific type of social gathering where the goal is for everyone
present to enjoy themselves more than they usually would in day-to-day life by
doing something generally viewed as special; this generally involves some
activities that participants wouldn’t engage in every day, or at least some
special spin on regular activities.

  * •

One person does not a party make. (However, one person and one animal might.)

  * •

The prototypical American birthday-party elements like birthday cake with
candles and people singing “Happy Birthday” are not required, as long as the
general definition of a party is fulfilled and it is clear that a birthday is
what is being celebrated.

  * •

It is not necessary for the person whose birthday is being celebrated to be
present, or even alive. The birthday does not have to be that of a human; it
can be an animal’s birthday or even an anniversary of the founding/beginning
of some organization/entity, as long as it is explicitly being treated as a
“birthday” by the participants in the party.

###  Event Name: Flash Mob919191 Video collectors and verifiers were initially
given the name Flash Mob Gathering for this event. (Ev102)

Definition: Multiple people gather in a public place and perform some type of
prearranged coordinated action that is particularly unusual to be performing
in that situation and/or place, generally for the purpose of surprising others
present.

Decision Rubrics/Clarifications:

  * •

The prototypical purpose of a flash mob is to surprise passersby (usually
pleasantly) and give both participants and nonparticipants a break from their
routine, perhaps to shake things up a bit or poke fun at social conventions.
The activity often involves artistic performance (such as dance or music)
and/or some actions that would normally be considered socially inappropriate
for the setting, or at least a mismatch for the setting. However, flash mobs
may also have other purposes like making a political statement or may be part
of a publicity campaign; videos depicting such gatherings should be included
as long as they are prototypical flash mobs in all other dimensions.

  * •

A flash mob may begin in a couple of different ways: the participants suddenly
arrive and gather as a group in the designated place, then begin the
prearranged action, or the participants gradually filter into the designated
place and mingle with the crowd, then suddenly begin the prearranged
coordinated action from their positions interspersed among nonparticipants.
Flash mobs are usually relatively short (on the scale of a few minutes) and
usually end with the participants dispersing quickly, but these are not strict
requirements.

  * •

A flash mob may be organized in a couple of different ways: The participants
may all know each other and may even have practiced the planned action
together before, or they may not know each other, but be summoned to perform
the action by some organization or person who has their information on a
contact list. The participants may know the planned time, location, and/or
activity for the flash mob well ahead of time, or they may receive a message
(text or otherwise) with the information just when it is time for the action
to start, telling them to go immediately if they want to participate.

  * •

Special note: The concept flash mob is a “contested category”, in that
reasonable people frequently disagree about where the boundaries are and what
should count as a “real” flash mob. For the purposes of this task, you can
allow the definition to stretch pretty broadly.

###  Event Name: Getting a Vehicle Unstuck (Ev103)

Definition: A person or persons perform(s) some actions with the goal of
getting some type of vehicle (motorized or unmotorized) out of a situation
where it is stuck, i.e., either cannot move at all or is severely limited in
its movements, into a situation where it can move normally.

Decision Rubrics/Clarifications:

  * •

The attempt does not have to be successful; however, someone must have an
obvious intention to get the vehicle into a position or state where it can be
moved normally.

  * •

A vehicle is any mechanical device (motorized or unmotorized) that can be used
to transport people or objects by means of moving said device. Vehicles that
move people or objects any distance count, from within-building vehicles (like
shopping carts) to intercontinental vehicles (like airplanes).

  * •

The vehicle’s movement may be impeded either because some part of it is
embedded in some substance that is preventing it from operating normally
(usually something that prevents the wheels from turning or from getting
purchase), or because it is situated at an angle with respect to surrounding
objects that makes it impossible for it to exit the space in a normal
trajectory, or any other impeding situation with similar results. A vehicle
does not count as stuck if the impediment is necessary to normal parking or
storage of the vehicle (e.g., getting a bike off a bike hook does not count).

  * •

The activities may involve moving the vehicle itself or may involve moving
other obstacles or impediments.

###  Event Name: Parade (Ev104)

Definition: A group of people moves in a procession formation through a public
space, under their own power or in vehicles, while simultaneously engaging in
special activities or exhibiting special behaviors to signal they are
celebrating something.

Decision Rubrics/Clarifications:

  * •

A parade is organized—or may spontaneously arise—to celebrate something (like
a holiday or an event). Public processions organized for other purposes (such
as protest marches, religious processions, or funeral processions) generally
do not qualify. However, processions with explicit religious, funereal, or
political-oppositional purposes may count if they resemble the prototypical
parade in style and celebratory mood.

  * •

Standard celebration-signaling elements like music and colorful
signs/banners/flags are not required as long as there are some type of obvious
markers that the procession is a special celebratory event.

  * •

Videos showing the participants forming up for the procession, i.e., arranging
themselves into the planned order/configuration, can be included as part of
the parade event, even if the video does not depict the procession itself, as
long as the intention is obvious and clear. (Other preparatory steps do not
qualify, if the procession itself is not depicted.) Videos depicting parade
participants stopping to interact with spectators should be included, but
videos that depict only spectators should not.

###  Event Name: Person Attempting a Board Trick929292Video collectors and
verifiers were initially given the name Attempting a Board Trick for this
event. (Ev105)

Definition: A person or persons attempt(s) to perform a maneuver requiring
special skill or practice, on some type of board-like object designed to allow
a human to move swiftly across a surface, usually under their own power.

Decision Rubrics/Clarifications:

  * •

The attempt does not have to be successful, nor does it have to be
unsuccessful (either way counts). However, there must be an obvious intention
to perform the trick on the part of the performer.

  * •

The attempted maneuver must be a special action requiring skill and/or
practice to precisely control the motion of one’s body and the board to
achieve the intended effect; the sort of thing one might do to surprise,
amuse, or impress an audience (even if there is no audience in the video).

  * •

The prototypical board trick involves a skateboard, snowboard, or surfboard.
Other flat boards may qualify, if they are specially designed to allow a
person (usually one person per board) to move quickly across a surface of some
kind, to which the face of the board would usually be parallel, where the
person could maintain a relatively static body position relative to the board
while it moved; or if they are obviously being used as stand-ins for specially
designed boards. Boards with supplemental (non-human) power sources may
qualify if they are very closely related to the prototypical types of boards
(for example, electric skateboards, or a fantasy equivalent in an animation).
Toy boards that are obviously intended to imitate the prototypical types of
boards may count if the attempted trick resembles a prototypical board trick
in all other dimensions.

###  Event Name: Person Grooming an Animal939393Video collectors and verifiers
were initially given the name Grooming an Animal for this event. (Ev106)

Definition: A person or person(s) performs some type of external body care on
a (nonhuman) animal to make it cleaner and/or to improve its appearance.

Decision Rubrics/Clarifications:

  * •

Grooming prototypically involves caring for an animal’s skin, coat/fur,
feathers, scales, etc., but any type of (external) body care qualifies if its
purpose is to make the animal cleaner and/or neater or more attractive in
appearance (according to some standard set by the groomer).

  * •

Animal care focused on the animal’s skin, fur, etc. that is not for the
purpose of making it cleaner or more attractive (for example, petting or
applying topical medicines) does not count as grooming.

  * •

The grooming must be performed by (a) human(s) or anthropomorphized agent(s).

  * •

In animations, the animals may be invented beasts that do not match any
species in the kingdom Animalia in reality, as long as they have the general
characteristics of nonhuman animals and are obviously intended by the creators
of the video to fit that general category/fulfill a role analogous to the role
of animals on (real) Earth.

###  Event Name: Person Hand-Feeding an Animal949494Video collectors and
verifiers were initially given the name Feeding an Animal for this event.
(Ev107)

Definition: A person or persons intentionally provide(s) food and/or water for
some (nonhuman) animal(s) to eat, by holding the food or water or a container
with food or water in it while the animal eats it.959595It should be noted
that this definition implies that, say, tossing food to fish or birds would
not count, even if the person doing the feeding remains present and engaged
and continues providing food as the animal is eating. This omission was not
corrected explicitly, but some of the corpus-builders did count such videos as
positive instances.

Decision Rubrics/Clarifications:

  * •

The feeding must involve direct interaction between the person doing the
feeding and the animal(s) being fed; putting food somewhere where the animal
will find it does not count.

  * •

Any type of solid or liquid food can be provided (including “treats”), whether
or not it is actually appropriate for the animal’s diet.

  * •

The attempt at feeding does not have to be successful, in that the animal(s)
do(es) not have to actually accept the food in the course of the video, as
long as it is clear that the person doing the feeding intends that the food
should be eaten by the animal(s).

  * •

In animations, the animals may be invented beasts that do not match any
species in the kingdom Animalia in reality, as long as they have the general
characteristics of nonhuman animals and are obviously intended by the creators
of the video to fit that general category/fulfill a role analogous to the role
of animals on (real) Earth.

###  Event Name: Person Landing a Fish969696Video collectors and verifiers
were initially given the name Landing a Fish for this event. (Ev108)

Definition: A person or persons who has/have successfully caught a fish with
some implement use(s) the implement to bring the fish in from the water to
where they are situated.

Decision Rubrics/Clarifications:

  * •

Landing a fish involves not only catching it with the implement (getting
indirect control of it) but also getting it out of the water and into the
immediate proximity/direct control of the fisher (i.e., successfully reeling
it in, for rod fishing). Videos that depict only the fish getting caught on/in
the fishing implement should not be included; they must depict at least an
attempt to bring the fish in from the water.

  * •

The fish does not necessarily have to be brought to dry land; it can be
“landed” on a boat or a dock (or even in the hands of a person standing in the
water), as long as it is in a place where it would not end up back in the
water if it were released from the implement that was used to catch it.

  * •

The fish must be caught from a body of water (aquariums don’t count).

  * •

The fisher must be a human or anthropomorphized agent who is actively involved
in operating the implement to effect the catch and landing (hauling in traps
does not count).

  * •

The prototypical implement is a fishing rod and line, but nets and rodless
lines may be used as long as they can catch only a few fish at a time and the
overall activity is focused on the challenge of catching each individual fish.

###  Event Name: Wedding Ceremony (Ev109)

Definition: Multiple people participate in a ceremony that includes elements
that result in two or more of the participants being considered married
according to some standard (legal, societal, religious, and/or personal).

Decision Rubrics/Clarifications:

  * •

For these purposes, a ceremony is an event in which a person or persons
perform(s) a formal sequence of prescribed actions and/or words that is viewed
by that person or persons as appropriate to and definitional of that event,
usually on the basis of the conventions of a larger community or society.

  * •

The prototypical Western/Judeo-Christian wedding elements like rings, formal
vows, or even an officiant with legal or religious authority are not required,
as long as it is clear that at least some of the participants in the ceremony
believe and intend that their performance of the prescribed words and/or
actions will result in a marriage between two or more humans or
anthropomorphized agents (who may or may not themselves be present at the
ceremony).

###  Event Name: Working on a Woodworking Project (Ev110)

Definition: A person or persons perform(s) steps in the process of making
something out of wood using tools, as part of a specific project.

Decision Rubrics/Clarifications:

  * •

A project is a single unified undertaking with a specific planned result or
end condition. The prototypical woodworking project is undertaken casually, as
a hobby or to fulfill a household need, but a woodworking activity could still
qualify as a project if it were undertaken for pay in some circumstances: if
the woodworker has creative and economic control of the production, or if
their job usually does not involve woodworking. However, woodworking as part
of a daily job with no creative control, as in industrial production or most
construction, does not qualify as a project.

  * •

Woodworking usually refers to making furniture or smaller decorative or
functional objects, or to cabinetry, but videos may be included that depict
someone making wood elements for larger-scale projects such as building
construction, if the process qualifies as a prototypical woodworking project
in all other ways. Videos of someone repairing something made of wood may be
included if it requires specialized knowledge or tools.

  * •

The central aspect of woodworking is using tools to cut and shape wood, but
videos should also be included that depict other steps necessary for producing
an item made out of wood, including measuring wood, staining or decorating
wood, and assembling pieces of wood and other materials together to make a
finished product. (However, planning, design, and acquiring materials do not
count as part of working on the project.)


# Near Optimal VNF Placement in Edge-Enabled 6G Networks

Carlos Ruiz De Mendoza  Universitat Politècnica de Catalunya (UPC)
<EMAIL_ADDRESS>Bahador Bakhshi, Engin Zeydan,
Josep Mangues-Bafalluy This work has been partially funded by the EC H2020
5Growth Project (grant no. 856709). The work by Carlos Ruiz de Mendoza was
done while carrying out the Master Thesis at CTTC.  Centre Tecnològic de
Telecomunicacions de Catalunya (CTTC/CERCA)
{bbakhshi, engin.zeydan<EMAIL_ADDRESS>
###### Abstract

Softwarization and virtualization are key concepts for emerging industries
that require ultra-low latency. This is only possible if computing resources,
traditionally centralized at the core of communication networks, are moved
closer to the user, to the network edge. However, the realization of Edge
Computing (EC) in the sixth generation (6G) of mobile networks requires
efficient resource allocation mechanisms for the placement of the Virtual
Network Functions (VNFs). Machine learning (ML) methods, and more
specifically, Reinforcement Learning (RL), are a promising approach to solve
this problem. The main contributions of this work are twofold: first, we
obtain the theoretical performance bound for VNF placement in EC-enabled 6G
networks by formulating the problem mathematically as a finite Markov Decision
Process (MDP) and solving it using a dynamic programming method called Policy
Iteration (PI). Second, we develop a practical solution to the problem using
RL, where the problem is treated with Q-Learning that considers both
computational and communication resources when placing VNFs in the network.
The simulation results under different settings of the system parameters show
that the performance of the Q-Learning approach is close to the optimal PI
algorithm (without having its restrictive assumptions on service statistics).
This is particularly interesting when the EC resources are scarce and
efficient management of these resources is required.

###### Index Terms:

NFV, EC, Dynamic Programming, MDP, Policy Iteration, Q-Learning, Reinforcement
Learning

##  I Introduction

Future beyond 5G(B5G)/6G networks are expected to bring new improvements over
the previous mobile networks (4G and 5G) and enable new paradigms. This
technological evolution paves the way for endless services tailored to
specific verticals; e.g., e-Health, Industry 4.0, Internet of Things (IoT),
and automotive. More cells and antennas will be deployed in combination with
advanced technologies, such as Virtual Radio Access Network (vRAN), which
enable partial or full virtualization of the network through Network Function
Virtualization (NFV) and Network Slicing. To serve all these needs, current
and future networks heavily rely on the Edge Computing (EC) concept to reduce
the distance between the end user and the computing resources. By placing
Virtual Network Functions (VNF) in proper edge computing centers at the edge
of the network, data is no longer stored or processed in a distant data
center, which translates into a significantly lower latency [1] at the cost of
additional complexity of network management.

B5G/6G technologies are expected to provide an increase in capabilities, all
in a multi-vendor environment, with particular focus on ultra-low latency data
transmission. It is no wonder that B5G/6G networks are expected to become
complex systems, making it difficult to deploy and manage services on them.
The options abundance in terms of offered services makes it even more
difficult to determine an optimal way to deliver them in the future and to
predict the demand in order to deploy in the most efficient way the
infrastructure. Such a complex system requires advanced methods targeting an
optimal use of its resources.

A major issue with managing EC-enabled 6G network is the inter-relation
between the computing and communication resources to provide services—to admit
the user’s request, the corresponding VNF should be placed in a EC center that
has sufficient computing resources as well as sufficient communication
resource to handle the offered traffic load. Therefore, dealing with the edge
cloud and transport Key Performance Indicators (KPIs) simultaneously is the
added complexity for the MNO when purporting to provide scalability. This is
one of the issues that we studied in this paper.

Furthermore, in this paper we also analytically find the optimal performance
bounds of such edge cloud scenarios that, unlike previous work, combine
computing and communication characteristics to take decisions. The scenario is
designed so that it is mathematically tractable. Consequently, the problem is
formulated as a Markov Decision Process (MDP) and its optimal solution is
found through the Policy Iteration (PI) algorithm. After that, this paper
focuses on the design of a practical algorithm that is able to perform as
close as possible to the theoretical bound in terms of rejection ratio. It is
practical in the sense that it does not take any restrictive assumption on
service statistics, hence it can be applied to real networks. And given its
low rejection ratio compared to other approaches, it makes the most out of the
resources of the operator. In this direction, and given their potential, AI/ML
approaches [2], and more specifically, reinforcement learning, is shown to
perform close to optimal under multiple conditions if enough iterations are
run.

###  I-A Related Work

Resource management between network edge nodes has been widely researched and
studied in various domains. The authors in [3] propose a Q-Learning algorithm
to choose optimal offloading among Fog network nodes. To evaluate the
performance of this algorithm, it is compared with existing offloading methods
as: Least-Queue, Nearest Node or Random Node selection. Reference [4]
formulates the resource allocation problem in EC as a minority game, and then
compares the performance of different RL methods to make its agent solve the
game. Akkarit et al. [5] present the automatic adaptation of container
instances under a Q-Learning algorithm and also with the implementation of
neural networks to maintain a certain service quality level without reducing
the cloud computing resources. Yala L. et al. [6] propose an algorithm for
placing VNF using optimization-adapted Genetic Algorithm meta-heuristic which
aims at minimizing latency and maximizing service availability.

Some of the above works differ from this paper in that the evaluation stage of
the proposed algorithms are compared with solutions that do not necessarily
yield the optimal solution which considers both transport and cloud related
parameters. In this paper, Q-Learning is evaluated against a mathematical
solution that allows measuring the performance gap between the two. Moreover,
the problem is posed as a finite MDP and solved by a model-based and a model-
free RL algorithm.

###  I-B Main Contributions

This paper takes the architecture of the H2020 5GPPP 5Growth
project111https://5growth.eu/ [7] as a general reference. The 5Growth project
aims to validate the operation of 5G systems deployed in vertical industries
and incorporates (through open APIs) AI/ML-related algorithms in service
deployment and operation.

In this paper, VNF placement decisions for each service requests are made
according to specific operational requirements (e.g., ensuring an efficient
use of edge resources while maximizing the number of services delivered over
the shared infrastructure). First, the theoretical performance bounds are
calculated through Dynamic Programming (DP) and in the form of a model-based
MDP solved through the PI algorithm. For this, all state transition
probabilities must be computed in advance, as well as all possible valid
states. This is an algorithm that mathematically allows the optimal solution
to be obtained from all possible solutions in the search space. Another
algorithm representing reasonable operation guidelines is best fit, which is
also taken as reference for comparison with theoretical bounds and practical
learning algorithms. This algorithm is inspired in the classic load balancing
algorithm Weighted Round Robin [8], but adapted to the needs of the topic
under consideration. In best fit approach, each EC has a weight based on the
administrators chosen criteria. The EC with the highest weight serves the
request.

Finally, the problem has been approached through a Q-Learning off-policy time
differential algorithm to conceive a deployable algorithm in practice that
performed as close as possible to the optimal bound. In this case, an agent
observes each incoming new VNF request. Based on the network state, the agent
performs an action by assigning it to an optimal EC node to maximize the total
number of processed VNF requests in the system. In summary, the key
contributions of this paper are:

  * •

The optimal VNF placement problem is formulated as a finite MDP and solved
using a model-based algorithm, i.e., PI, considering cloud and transport
network conditions, hence obtaining the optimal performance bounds.

  * •

A practical solution is given for a (near) optimal solution using a model-free
and off-policy algorithm, i.e., Q-Learning, and compared with PI and best fit.

  * •

The simulation results make it clear that Q-Learning works near-optimally when
EC resources must be managed conscientiously.

The rest of the paper is organized as follows. Section II describes the
considered scenario, system model and the problem statement. Section III
presents the problem as an MDP and the PI approach. Section IV introduces both
practical solutions, Q-Learning and best fit algorithms. Section V details
each of the simulations that have been carried out. Finally, section VI draws
the conclusions.

##  II Scenario and System Model

###  II-A Considered Scenario

In this paper, we consider the joint use of cloud and transport KPIs to make
the optimal decision in the placement of VNFs. Fig. 1 shows an example
application scenario of our approach. If only cloud or transport parameters
are considered separately during VNF placement decision making process (i.e.
selecting the most appropriate EC), the requested service cannot be provided
in some cases. For example, consider the utilization of link 1 (poor quality
link) in Fig. 1 for only cloud aware decision making to reach $EC_{3}$ (EC
with high cloud resource) and link 2 (good quality link) for only transport
aware decision making to reach $EC_{2}$ (EC with low cloud resources). In both
conditions, both transport and cloud level service requests cannot be provided
efficiently. For this reason, the selection of a EC center must depend on both
cloud and transport parameters as is done with link 3 (high quality link) to
reach $EC_{1}$ (EC with high cloud resources). More specifically, in [9] the
authors have demonstrated that considering both transport and cloud related
parameters simultaneously, better EC decisions are taken by the previously
trained ML models.

Figure 1: Edge computer nodes across different network regions

###  II-B System Model and Problem Statement

In this paper, we make the following assumptions. The MNO operates a network
with $\mathcal{K}=\\{1,\ldots,K\\}$ ECs, and provides a set
$\mathcal{I}=\\{1,\ldots,I\\}$ of VNFs to users. Each user request asks for an
instance of a VNF $i\in\mathcal{I}$. The requests for VNF type
$i\in\mathcal{I}$ arrive and depart following Poisson processes with rate
$\lambda_{i}$ and $\mu_{i}$, respectively. The problem is assumed to be online
- i.e. the demands arrive into the system one-by-one. The network management
system keeps records of the VNFs served by each network EC node. Each request
$req$ is represented by a vector compounded of the number of CPU cores of the
corresponding VNF and the bandwidth of the required traffic
$[req_{cpu},req_{bw}]$; e.g., $[3,100]$ is a request for a VNF that needs 3
CPU cores and processes 100 Mbps traffic. The requests are represented by the
set $\mathcal{J}=\\{req_{1},req_{2},...,req_{J}\\}$.

Under these assumptions, the problem is to place each given VNF request in a
proper EC, without knowledge of future requests in order to maximize the
acceptance rate. The solution to this problem should consider both the
capacity constraints of the ECs and the bandwidth constraints of the links.

##  III Optimal Solution

In this section we obtain the optimal solution of the problem by formulating
it as a finite MDP then solving it using DP, i.e., the PI algorithm.

###  III-A The MDP Formulation

An MDP [10], models controlled stochastic dynamical systems whose evolution is
subject to random factors and which can be modified by certain decisions. An
MDP provides a mathematical framework for learning sequential decision making,
where actions in each state $s$ provide not only immediate rewards
$\mathcal{R}$, but also the subsequent state $s^{\prime}$. Mathematically, an
MDP is a 5-tuple of
$\langle\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},s_{0}\rangle$, where:

  * •

$\mathcal{S}$: the environment’s finite set of states

  * •

$\mathcal{A}$: the finite set of applicable actions within the environment
states

  * •

$\mathcal{P}$: the state transition probabilities where
$\mathcal{P}(\mathcal{S}_{t+1}=s^{\prime}\,|\,\mathcal{S}_{t}=s,A_{t}=a)$

  * •

$\mathcal{R}(s,a,s^{\prime})$: the immediate reward the agent obtains for
being in state $s$, taking action $a$ and ending up in the subsequent state
$s^{\prime}$.

  * •

$s_{0}$: the initial state at which the agent starts its task

We assume here that the environment is fully observable and the environment
state at time $t$, denoted $s_{t}$, contains all the relevant environment
information to the agent. It reflects not only the network status at time step
$t$, but also the VNF $req_{j}$ arriving into the system at time $t$.

An MDP where all 5-tuple elements are known in advance, is called a model-
based MDP and can be solved by DP methods, such as the PI algorithm. This
allows to obtain the optimal agent’s policy $\pi^{*}(s)$, in order for it to
place as many VNFs as possible.

We define the state $s_{t}$ as a vector of vectors $s_{t}=[[ecs],[d]]$, where
$ecs$ represents as many vectors as there are EC nodes in the system,
$ecs=[[M_{1}],[...],[M_{K}]]$. Each $M_{k}$ vector has size $I$ which is the
total number of different VNF types. The value of the $i$-th element of
$[M_{k}]$ determines the total number of active requests using instances of
VNF type $i\in\mathcal{I}$, otherwise 0. Following the technique presented in
[11], the vector $[d]$ has size $\mathcal{I}$ and only one of its $i$-th
elements can take a value while the remaining elements are $0$; where
$d[i]=+1$ if an incoming request $req$ requests an instance of VNF type $i$,
and $d[i]=-1$ if a request that have been using an instance of VNF type $i$
departs from the network.

The state transition probabilities $\mathcal{P}$ are crucial to compute the
optimal agent’s policy $\pi^{*}(s)$. In this paper, the $\mathcal{P}$ are
computed from the VNF $req$ arrival and departure rates, $\lambda_{i}$ and
$\mu_{i}$ $\forall i\in\mathcal{I}$. To describe the process of computing
$\mathcal{P}$ let us define two subsets of the state space, namely:

  * •

$\mathcal{S}^{+}\subset\mathcal{S}=\text{\\{s}\,|\,\exists i\textbf{ s. t.
}d_{i}=+1\text{\\}}$

  * •

$\mathcal{S}^{-}\subset\mathcal{S}=\text{\\{s}\,|\,\exists i\textbf{ s. t.
}d_{i}=-1\text{\\}}$

Whenever $s\in\mathcal{S}^{+}$, this implies a request $req_{j}$ that can
either be served by a EC node chosen by the agent
$\mathcal{A}(s)\in\\{M_{1},M_{2},...,M_{K}\\}$ or rejected due to insufficient
resources to handle it. The states $s\in\mathcal{S}^{-}$ are completely
transparent to the agent, since it does not perform any action upon departure
of requests; therefore, there is no agent action as such, we could say that
the action is void. Let us illustrate this with an example considering the
following scenario: $\mathcal{I}=\\{1,2\\}$, $\lambda_{1}=2,\lambda_{2}=4$,
and $\mu_{1}=0.25,\mu_{2}=1$.

In Fig. 2, $s_{0}$ reflects the network status where the type 1 request
arrives at $t=0$. The agent chooses $a=M_{1}$, so is allocated on EC 1, which
increments $M_{1}[1]$ by 1. After this action, there are several possible
$s^{\prime}$ that depend on the next event—a new $req$ of type 1 or 2 could
arrive in the system, a departure of the $req$ of type 1 in $M_{1}$ or of type
2 in $M_{2}$ could also happen. Fig. 2 shows how the transition probabilities
are calculated based on the transition rates using the competing exponentials
theorem [12]. The numerator of $\mathcal{P}$ is the rate of the corresponding
event, i.e., $\lambda_{i}$ for the states $s\in\mathcal{S}^{+}$, and for the
departure states $s\in\mathcal{S}^{-}$, it is the total number of active $req$
of type $i$ that are held times the corresponding departure rate, $\mu_{i}$.
The denominator is the total rate of all possible events in this state. Note
that the arrival rates are independent and the departure rates depend on the
total number of active $req$ of each type in the $M_{k}$.

Figure 2: State transition probabilities for an arrival event

In Fig. 3, $s_{0}$ indicates that a $req$ of type 2 is departing from the
system. It could be from $M_{1}$ or $M_{2}$. Fig. 3 shows the state transition
probabilities only for the case where the $req$ is departing from $M_{1}$; for
$M_{2}$, it would be the same procedure as shown here. In this case, the
$\mathcal{P}$ is composed of two terms, ${\mu_{2}}/{2\mu_{2}}$ is the
probability of $req$ of type 2 that is departing from $M_{1}$, considering
$\mu_{2}$ from $M_{1}$ and $M_{2}$. The second term, as shown in Fig. 2, is
obtained by the competing exponentials theorem. Note that the sum of
probabilities $\mathcal{P}(s_{i})$ is equal to $0.5$, since only half of the
possible transitions are represented. In this paper,
$\mathcal{R}(s,a,s^{\prime})=1$ if the given request is deployed in one of the
EC nodes and $\mathcal{R}(s,a,s^{\prime})=0$ if the demands are rejected.

Figure 3: State transition probabilities for a departure event

###  III-B Dynamic Programming

DP is a collection of methods by which it is possible to obtain the optimal
policy of an MDP, as long as all elements of the model are known in advance.
The PI algorithm is one of these methods [13].

As shown in Algorithm 1, PI is divided into two sub-algorithms; Policy
Evaluation and Policy Improvement. The former computes $V_{i}(s)$ $\forall
s\in\mathcal{S}$ for a given policy $\pi_{i}(s)$ . The latter improves the
previously given policy $\pi_{i}(s)$ and obtains a new improved policy
$\pi_{i+1}(s)$.

The state-value function $V(s)$ pairs $s$ to $r$ and determines how good it is
for the agent to be in a given $s$. The $V(s)$ can be expressed in terms of
$\pi(s)$, where $V_{\pi}(s)$ describes how good it was for the agent to follow
its $\pi(s)$ in a particular $s$, take an $a$ and transition to another
$s^{\prime}$. The immediate $\mathcal{R}(s,a,s^{\prime})$ plus the function
$V(s^{\prime})$ of the landed next state $s^{\prime}$ determines how good the
original $s$ was; more precisely, we have

$V_{\pi}(s)=\sum_{a}\pi(a\,|\,s)\sum_{s^{\prime}}\mathcal{P}[\mathcal{R}(s,a,s^{\prime})+\gamma
V(s^{\prime})]$

The discount rate $\gamma\in[0,1]$ prevents the agent from infinitely
returning to a state accumulating rewards. If $\gamma\approx 1$ the agent will
prioritize expected future rewards. In contrast, when $\gamma\approx 0$ the
agent will strongly consider the immediate rewards. Each iteration is
guaranteed to result in an improved new policy until the optimal strategy is
obtained. Since a finite MDP is a finite set of $\mathcal{S}$ and
$\mathcal{A}$, convergence of $V^{*}(s)$ to obtain the $\pi^{*}(s)$ is
achievable in a finite number of iterations. Prior knowledge of all valid $s$,
allows to set $\gamma\approx 1$.

Finally, out of all possible policies, there’s at least one to be better or
equally as good to all other policies achieving the optimal state-value
function $V^{*}(s)$; more specifically:

$V^{*}(s)\leftarrow\max_{\pi}V_{\pi}(s)\ \ \ \ \forall s\in\mathcal{S}.$

Algorithm 1 Policy Iteration

Randomly initialize $V(s)\in\mathbb{R}$ and $\pi(s)\in{\mathcal{A}}(s)$
$\forall s\in{\mathcal{S}}$

while $\Delta>\theta$ do $\triangleright$ The Policy Evaluation loop

$\triangleright$ $\theta$ determines the accuracy of estimation

$\Delta\leftarrow 0$

for $\forall s\in\mathcal{\mathcal{S}}$ do

$v\leftarrow V(s)$

$V(s)\leftarrow\sum_{s^{\prime},r}p(s^{\prime},r\,|\,s,\pi(s))[r+\gamma
V(s^{\prime})]$

$\Delta\leftarrow\text{max}(\Delta,|v-V(s)|)$

$policy_{stable}\leftarrow true$

for $\forall s\in\mathcal{S}$ do $\triangleright$ The Policy Improvement loop

$action_{old}\leftarrow\pi(s)$

$\pi(s)\leftarrow\text{argmax}_{a}\sum_{s^{\prime},r}p(s^{\prime},r\,|\,s,a)[r+\gamma
V(s^{\prime})]$

if $action_{old}\neq\pi(s)$ then

$policy_{stable}\leftarrow false$

if $policy_{stable}$ then

return $\pi^{*}$

else

go to Policy Evaluation loop

##  IV Practical Solutions

In the MDP formulation, we defined a subset $\mathcal{S}^{-}$ to derive the
transition probabilities in the case of departure from a demand, as in Fig. 3.
Since it is not needed in the practical solution, we redefine the state as
follows:

$s=[req_{cpu},req_{bw},M_{1}^{fcpu},...,M_{K}^{fcpu},M_{1}^{fbw},...,M_{K}^{fbw}]$

where $M_{k}^{fcpu}$ is the available CPU units of the $k$-th EC node, and
$M_{k}^{fbw}$ is the available BW connection to reach the $k$-th EC node.

###  IV-A Q-Learning

In cases where not all aspects of the system are known in advance, model-free
reinforcement learning approaches can find the (near) optimal policy. Here,
the agent must learn from its own actions without a given $\pi(s)$; hence, it
is also an off-policy model.

The Q-Learning algorithm [14] drives the agent’s learning by assigning values
to $(s,a)$ pairs. The Q-values define how good an action is in a given state.
They are updated for each interaction with the environment by the following
rule:

$\begin{split}\underbrace{Q(s,a)}_{\text{new
value}}\leftarrow\underbrace{Q(s,a)}_{\text{old
value}}+\underbrace{\alpha}_{\text{learning rate}}\cdot\ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\\ \
\overbrace{{\bigg{(}}\underbrace{\underbrace{\mathcal{R}(s,a,s^{\prime})}_{\text{reward}}+\underbrace{\gamma}_{\text{discount
rate}}\cdot\underbrace{\max_{a^{\prime}}Q(s^{\prime},a^{\prime})}_{\text{estimate
of optimal future value}}}_{\text{new value (temporal difference
target)}}-\underbrace{Q(s,a)}_{\text{old value}}{\bigg{)}}}^{\text{temporal
difference}}\end{split}$

By introducing a learning rate $\alpha\in[0,1]$, it is possible to control the
variation of Q-values, where $\alpha$ defines to what degree the agent
replaces the old data with new ones. A rate $\alpha\approx 1$ forces the agent
to consider the latest information, while $\alpha\approx 0$ causes the agent
to learn nothing. In the update rule of Q-Learning, the new Q-value is the
weighted combination between the old Q-value and the new observation that the
agent must believe. Q-Learning algorithm converges to an optimal Q-value,
$Q^{*}(s,a)$, given sufficient $\alpha$ and exploration over $\mathcal{S}$
that satisfies the Robbins-Monro conditions [15] [16].

A disadvantage of Q-Learning is that the agent can only learn from actions
performed in visited states, otherwise there is no learning. The chain of
successive actions and the resulting states form an episode. This leads to the
exploitation/exploration dilemma. It might be interesting for the agent,
especially at the beginning of its training222There is no training concept as
such in Q-Learning as is exists in other ML domains. Nonetheless, we refer to
training as the initial episodes in which the agent attempts to populate its
Q-Table., adopt an explorer profile to visit as many states and try as many
actions as possible within those states. When the agent’s learning reaches a
certain level, it is more beneficial to exploit the known actions that bring
higher rewards when revisiting the known states. This strategy is known in the
literature as $\epsilon$-greedy [13].

Q-Learning differs from PI in that it cannot be evaluated directly without the
agent having prior experience. That is, it requires knowledge about what to do
when confronted with an $s$, otherwise the agent’s actions would be completely
random according to the $\epsilon$-greedy strategy. Therefore, the Q-Learning
agent is trained with several different VNF $req$ sequences before using its
agent to evaluate. To prevent Q-Learning agent from being confronted with an
unknown state (during the evaluation stage) and failing its attempt to search
for it in Q-Table, the algorithm has been modified to allow it to learn during
the evaluation stage as well.

Algorithm 2 Q-Learning

Set values for: learning rate $\alpha$, discount rate $\gamma$

Randomly initialize $Q[s,a]\in\mathbb{R}$ $\forall s\in{\mathcal{S}}$,
$\forall a\in{\mathcal{A}}(s)$

for each episode do

Initialize $\mathcal{S}$

for each step do

if evaluation then

if $s$ in $Qtable$ then

$a\leftarrow$ $argmax(Q(s,a))$

else

behave as in $not$ evaluation

else

$a\leftarrow$ action from ${\mathcal{A}}(s)$ by $\epsilon$-greedy strategy

Observe $s^{\prime}$

$r\leftarrow\mathcal{R}(s,a,s^{\prime})$

$Q(s,a)\leftarrow
Q(s,a)+\alpha[r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})-Q(s,a)]$

$s\leftarrow s^{\prime}$

Until $S_{T}$

Another important aspect to consider in the present work is that there is no
absorbing/terminal state $S_{T}$ in the VNF placement problem. In episodic
tasks, a $S_{T}$ is reached when the agent reaches its goal or commits an
error that forces the environment to restart. However, in our problem, the
VNFs assignment should be done as long as there are requests. Therefore, in
this work $S_{T}$ is determined by the total number of $req_{j}$ in the VNF
$req$ training files.

###  IV-B Best Fit

In addition to Q-Learning, we develop another practical solution called best
fit which is inspired by a classical Weighted Round Robin load balancing
algorithm. The algorithm assigns the incoming VNF request to the EC that has
the highest network metric value $l$ which is defined as follows,

$l=a\ \frac{M_{k}^{fcpu}}{100}+(1-a)\ \frac{1}{Num_{hops}}$

where $Num_{hops}$ is the number of hops from the BS to the EC node, and
$a={M_{k}^{ubw}}\ /\ ({\text{Total Network BW})}$ where $M_{k}^{ubw}$ is the
BW connection used to reach the $k$-th EC node.

The algorithm best fit first checks if all EC nodes have enough CPU and BW
resources, otherwise a rejection is generated. If there is only one EC with
available resources, the VNF $req$ is assigned to that EC node. If there is
more than one EC node with the same resource availability, the VNF $req$ in
this paper is randomly assigned. If there is more than one EC node with
different resources availability, the VNF $req$ is assigned to the EC node
that is proved to have the highest $l$.

##  V Simulation Results

The following simulations were performed from a theoretical perspective, since
the PI algorithm requires a large amount of computational resources and
execution time. It would be a tedious task to simulate a network with a large
number of entities. For this reason, several BSs demanding $req$ and two EC
nodes were considered to meet the demands. The goal is to measure the
performance of Q-Learning and observe how far it is from a mathematical
solution, a model-based MDP, and how much it can outperform best fit. During
the evaluation stage all three algorithms are run for only one episode over
the same set of VNF requests. Unless otherwise specified, the following
simulations are run with the settings defined in Table I.

TABLE I: Default Simulation Settings Settings | Values
---|---
Initial network status | $[4,12,0,0,1000,400,0,0]$
No. training files | $10$
No. $req$ in training files | $500$
No. episodes in training files | $250$
No. evaluation files | $20$
No. $req$ in evaluation files | $500$
[$\lambda_{1},\lambda_{2}]$ | $[3,2]$
[$\mu_{1},\mu_{2}]$ | $[1,0.5]$
[$req_{1},req_{2}]$ | $[(1,300),(3,50)]$

###  V-A Influence of $\alpha$ and $\gamma$ in Q-Learning algorithm

Continuous tasks, such as the one considered here, force the agent to
compromise by achieving a high reward in the long-run but giving enough
importance to each current state value. The agent must learn to some degree,
but without constantly overriding what it has already learned. Therefore,
$\alpha$ and $\gamma$ must be configured considering the nature of the task
the agent is expected to develop.

(a) $\alpha=0,\gamma=0.001$

(b) $\alpha=0.5,\gamma=0.5$

(c) $\alpha=0.9,\gamma=0.9$

(d) $\alpha=0.5,\gamma=0.9$

Figure 4: Influence of $\alpha$ and $\gamma$ in Q-Learning algorithm

Fig. 4 shows four different Q-Learning simulations representing the average
reward (Y-axis) collected by the agent over the course of 250 episodes
(X-axis) through the same 500 VNF $req$ sequence file. Note that setting
$\alpha$ and $\gamma$ to consider the most recent information and to favor the
long-term reward does not ensure the desired learning convergence, Fig. 4(c).
This is mainly because there is no $S_{T}$ that determines the goal to be
achieved. Setting $\alpha$ and $\gamma$ to $0.5$ have been show to be
satisfactory.

###  V-B Influence of $\epsilon$-greedy parameters in Q-Learning algorithm

(a) $\epsilon_{decay}=0.1$

(b) $\epsilon_{decay}=0.01$

(c) $\epsilon_{decay}=0.001$

(d) $\epsilon_{decay}=0.03$

Figure 5: Influence of $\epsilon$-greedy parameters in Q-Learning algorithm

The Q-Learning $\epsilon$-greedy sub-algorithm that determines how much of an
explorer or exploiter the agent is has certain parameters that define exactly
how long the agent will take on such profiles. The decay rate
($\epsilon_{decay}$) has huge impact on the convergence of the agent’s
learning performance, as shown in Fig. 5.

Depending on the number of episodes, a very small $\epsilon_{decay}$ rate may
mean that the agent can never exploit what it has already learned, as in Fig.
5(c). By leaving a minimum epsilon value $\epsilon_{min}=0.001$ and a
$\epsilon_{max}=1$, the probability that the agent explores from time to time
increases, even towards the end of the training stage. This is the reason why
certain peaks are seen along the performance curve once it has converged Fig.
5(a). Fig. 5(d) shows the same level of convergence and the same average
reward as in Fig. 5 (a) but over the course of 2000 episodes instead of 250
with an $\epsilon_{decay}=0.03$. $\epsilon$ decays after each episode using:
$\epsilon=\epsilon_{min}+(\epsilon_{max}-\epsilon_{min})\cdot
e^{(-\epsilon_{decay}\cdot episode_{i})}$.

###  V-C Rejection ratio with respect to VNF arrival rate

In these simulations, the performance of all three algorithms is evaluated
using different $\lambda_{i}$ rates, as shown in Table II. The goal is to
analyze how the $req_{j}$ arrival rate affects the resources of the EC nodes.
The agent is forced to handle consecutive incoming requests with short and
high arrival rate. The results are shown in Fig. 6, where the X-axis
represents the different factor values by which the VNF arrival rates are
multiplied.

In Simulation 1, the short $\lambda_{2}$ and $\mu_{2}$ ensure that such a
demand arrives and departs in a short time, returning the resources to the EC
center to which they were allocated, and thus becoming available again. As
$req_{j}$ inter-arrival times increases, (Simulations 2 and 3), the MDP
achieves a slightly better policy than Q-Learning. The agent must constantly
learn how to assign the demands among the resources of EC nodes as they are
occupied for longer time steps. This occasionally results in rejections.
Nevertheless, the performance difference is very small, indicating that the
agent behaves optimally when EC centers’ resources are scarce.

TABLE II: Simulation Settings to Analyze Arrival Rate Parameter | Sim. 1 | Sim. 2 | Sim. 3
---|---|---|---
Factor | 0.2 | 1.0 | 2.0
[$\lambda_{1},\lambda_{2}]$ | [0.6, 0.4] | [3, 2] | [6, 4]
[$\mu_{1},\mu_{2}]$ | $[1,0.5]$ | $[1,0.5]$ | $[1,0.5]$
Figure 6: Rejection ratio with respect to VNF arrival rate

###  V-D Rejection ratio with respect to EC and link capacity

TABLE III: Simulation Settings to Analyze EC Resources Parameter | Sim. 1 | Sim. 2 | Sim. 3
---|---|---|---
Factor | 0.8 | 1.0 | 1.2
$[M_{1}^{fcpu},M_{2}^{fcpu}]$ | [4, 8] | [5, 10] | [6, 12]
$[M_{1}^{fbw},M_{2}^{fbw}]$ | [800, 320] | [1000, 400] | [1200, 480]

In these simulations, we evaluate the performance of the algorithms with
different CPU cores and BW link capacities, as shown in Table III. The results
are shown in Fig. 7.

In Fig. 7, for Simulation 1, the scarce available resources, for either
$M_{1}^{fcpu}$ or $M_{2}^{fbw}$, determine the performance difference between
MDP and Q-Learning. The Q-Learning’s policy is better than that of best fit,
but worse than that of MDP. The $M_{1}^{fcpu}$ are used up very quickly, so
the rest of the outcome is somehow deterministic. As the available resources
are increased in each EC, Q-Learning appears to improve its learning and to
closely converge to ideal policy of the MDP. It should be noted that the
randomness of Q-Learning during the exploration stage, determines, to some
extent, the starting point for building the path for the optimal policy. When
the exploitation stage begins, the probabilities of changing what is already
known are less likely.

Figure 7: Rejection ratio with respect to EC and link capacity

###  V-E Rejection ratio with respect to EC resource heterogeneity

In this simulations, we analyze how the agent can effectively reflect the
heterogeneity of EC resources. To this end, in simulations EC 1’s available
resources are fixed, i.e. $[4,1000]$, while EC 2’s CPU cores are increased as
$EC_{2}^{cpu}=\beta\cdot EC_{1}^{cpu}$, and its available BW is decreased as
$EC_{2}^{BW}=\frac{1}{\beta}\cdot EC_{1}^{BW}$. The simulation settings and
corresponding results are shown in Table IV and Fig. 8 respectively.

The first thing that can be observed in all simulations is the small influence
of each resource parameter on the agent’s decision. It is clear that the agent
treats the lack of resources similarly whether it is CPU or BW. It is
noticeable that simulation 1 and 3 show almost the same results in terms of
rejection ratio, and the difference between the two simulations is a factor 3.
Simulation 2 also shows the same dynamics as all previous simulations:
Q-Learning performs slightly worse when the resources are larger and there are
more opportunities to assign $req_{j}$ among the network’s EC centers.

TABLE IV: Simulation Settings to Analyze EC Heterogeneity Parameter | Sim. 1 | Sim. 2 | Sim. 3
---|---|---|---
$\beta$ | 1.0 | 2.5 | 3.0
$M_{2}^{fcpu}$ | [4] | [10] | [12]
$M_{2}^{fbw}$ | [1000] | [400] | [333]
Figure 8: Rejection ratio with respect to EC resource heterogeneity

###  V-F Rejection ratio with respect to VNF demand heterogeneity

TABLE V: $req_{2}$ Demand Settings to Analyze Demand Heterogeneity Parameter | Sim. 1 | Sim. 2 | Sim. 3
---|---|---|---
$\beta$ | 1.5 | 2 | 4
$req_{2}^{CPU}$ | 3 | 4 | 8
$req_{2}^{BW}$ | 200 | 150 | 75

In these simulations, we proceed similarly to the previous one, but with
implications for the VNF demand values. In this case, the $req_{1}$ demands
remain static and the $req_{2}$ values are changed according to the Table V.

For $req_{2}$, as the number of CPU requests increases, $req_{2cpu}=\beta\cdot
req_{1cpu}$, the required link BW is lowered, $req_{2BW}=\frac{1}{\beta}\cdot
req_{1BW}$. The results are shown in Fig. 9. In Fig. 9, for $\beta=1.5$, a
similar agent behavior, when available resources are not critical, can be
seen. Seems to perform worse than MDP. As EC resources begin to be scarce,
Q-Learning approximates the MDP, resulting in similar policies.

Figure 9: Rejection ratio with respect to VNF demand heterogeneity

##  VI Conclusions and Future Work

In this paper, we have studied the problem of VNF placement in EC-enabled 6G
networks, considering both computational and communication resources. We have
developed theoretically optimal and practical solutions to this problem. We
obtained the former by formulating the problem as a finite MDP, solved via PI.
The latter is the model-free reinforcement learning approach. We evaluated the
solutions in a wide range of network parameter settings. It has been shown
that there is a striking performance similarity between Q-Learning and PI,
especially when both algorithms face limited EC resources. Nevertheless, the
MDP needs to know all the environment dynamics in advance, which is an arduous
task in a real world scenario. It has also been shown that Q-Learning performs
better than best fit in all cases and it performs well considering cloud and
transport network parameters, which was the main objective in the problem.

Once near-optimality of learning-based approaches is shown in this paper
thanks to the mathematical tractability of the scenario, future work will be
devoted to extend the proposed practical schemes towards increasingly complex
6G scenarios, e.g., through Deep Q-Networks (DQN).

## References

  * [1] L. Corneo, N. Mohan, A. Zavodovski, W. Wong, C. Rohner, P. Gunningberg, and J. Kangasharju, “(how much) can edge computing change network latency?,” in 2021 IFIP Networking Conference (IFIP Networking), pp. 1–9, IEEE, 2021\.
  * [2] 5G PPP Technology Board, “Ai and ml – enablers for beyond 5g networks,” 2021\.
  * [3] J.-y. Baek, G. Kaddoum, S. Garg, K. Kaur, and V. Gravel, “Managing fog networks using reinforcement learning based load balancing algorithm,” in 2019 IEEE Wireless Communications and Networking Conference (WCNC), pp. 1–7, 2019.
  * [4] S. Ranadheera, S. Maghsudi, and E. Hossain, “Mobile edge computation offloading using game theory and reinforcement learning,” 11 2017.
  * [5] A. Sangpetch, O. Sangpetch, N. Juangmarisakul, and S. Warodom, “Thoth: Automatic resource management with machine learning for container-based cloud platform,” pp. 103–111, 01 2017.
  * [6] L. Yala, P. A. Frangoudis, and A. Ksentini, “Latency and availability driven vnf placement in a mec-nfv environment,” in 2018 IEEE Global Communications Conference (GLOBECOM), pp. 1–7, 2018.
  * [7] X. Li, A. Garcia-Saavedra, X. Costa-Perez, C. J. Bernardos, C. Guimarães, K. Antevski, J. Mangues-Bafalluy, J. Baranda, E. Zeydan, D. Corujo, et al., “5growth: An end-to-end service platform for automated deployment and management of vertical services over 5g networks,” IEEE Communications Magazine, vol. 59, no. 3, pp. 84–90, 2021.
  * [8] V. Hottmar and B. Adamec, “Analytical model of a weighted round robin service system,” Journal of Electrical and Computer Engineering, vol. 2012, 04 2012\.
  * [9] E. Zeydan, J. Mangues, and Y. Turk, “Intelligent service orchestration in edge cloud networks,” IEEE Network Magazine, Interplay between Machine Learning and Networking System (in press), 2021.
  * [10] D. P. Bertsekas, Dynamic Programming and Optimal Control.  Athena Scientific, 2nd ed., 2000.
  * [11] B. Bakhshi, J. Mangues-Bafalluy, and J. Baranda, “R-learning-based admission control for service federation in multi-domain 5g networks,” in IEEE GLOBECOM, 2021.
  * [12] D. Blumenfeld, Operations research calculations handbook.  CRC press, 2001.
  * [13] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction.  MIT press, 2018.
  * [14] C. J. C. H. Watkins, Learning from Delayed Rewards.  PhD thesis, King’s College, Cambridge, UK, May 1989.
  * [15] H. Robbins and S. Monro, “A stochastic approximation method,” The Annals of Mathematical Statistics, vol. 2, no. 3, pp. 400–407, 1951.
  * [16] M. Daswani, P. Sunehag, and M. Hutter, “Q-learning for history-based reinforcement learning,” Journal of Machine Learning Research, vol. 29, pp. 213–228, 2013.