Computer-Networks Compress
Computer-Networks Compress
Michał Sawicki
Grażyna Suchacka
Andrzej Kwiecień (Eds.)
Computer Networks
25th International Conference, CN 2018
Gliwice, Poland, June 19–22, 2018
Proceedings
123
Communications
in Computer and Information Science 860
Commenced Publication in 2007
Founding and Former Series Editors:
Alfredo Cuzzocrea, Xiaoyong Du, Orhun Kara, Ting Liu, Dominik Ślęzak,
and Xiaokang Yang
Editorial Board
Simone Diniz Junqueira Barbosa
Pontifical Catholic University of Rio de Janeiro (PUC-Rio),
Rio de Janeiro, Brazil
Phoebe Chen
La Trobe University, Melbourne, Australia
Joaquim Filipe
Polytechnic Institute of Setúbal, Setúbal, Portugal
Igor Kotenko
St. Petersburg Institute for Informatics and Automation of the Russian
Academy of Sciences, St. Petersburg, Russia
Krishna M. Sivalingam
Indian Institute of Technology Madras, Chennai, India
Takashi Washio
Osaka University, Osaka, Japan
Junsong Yuan
University at Buffalo, The State University of New York, Buffalo, USA
Lizhu Zhou
Tsinghua University, Beijing, China
More information about this series at http://www.springer.com/series/7899
Piotr Gaj Michał Sawicki
•
Computer Networks
25th International Conference, CN 2018
Gliwice, Poland, June 19–22, 2018
Proceedings
123
Editors
Piotr Gaj Grażyna Suchacka
Institute of Informatics University of Opole
Silesian University of Technology Opole
Gliwice Poland
Poland
Andrzej Kwiecień
Michał Sawicki Silesian University of Technology
Silesian University of Technology Gliwice
Gliwice Poland
Poland
This Springer imprint is published by the registered company Springer International Publishing AG
part of Springer Nature
The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
Preface
In 1993, our dear colleague, prof. Andrzej Grzywak, was thinking about how to
integrate the Polish academic community involved in computer networks research and
development. On the one hand, it was a time of great progress in network usage and
application, both in local and wide area network types. On the other hand, at this time
the public Internet was just beginning; it was just started as an open and global network
and its range and availability were incomparable to those of today. Therefore, the
common access to knowledge dissemination and lookups was limited. Moreover, the
number of scientific journals related to computer networks domains and their quality
were not as high as today and access to them was also imperfect. Thus, there was a
need to create an opportunity to exchange knowledge and experiences between people
involved in this area, employed in various business and academic institutions. As a
result, the domestic science conference on Computer Networks (CN) was initiated as an
annual event dedicated to the academic and industry communities in Poland.
The conference was established at the Faculty of Automatic Control, Electronics and
Computer Science at the Silesian University of Technology in Gliwice and the first five
editions of the conference took place in the halls of this faculty. The cycle of these
initial editions was approximately annual but not strictly constant. It depended on
various conditions, e.g., the fact that the event was new and not widely known. From
year to year, the conference grew in popularity and recognition and its range gradually
evolved from local to nationwide. In 1999, the conference was organized as an external
event for the first time. Each of the next editions was organized outside the university.
From the very beginning, for many years, Prof. Andrzej Grzywak together with
Ms. Halina Węgrzyn worked actively on the conference organization, becoming the main
stem of the Organizing Committee. In 2007, Prof. Grzywak retired and Dr. Piotr Gaj
became the chair of the Organizing Committee while Prof. Andrzejń Kwiecie became the
head of the Technical Program Committee. In 2008, the form of the conference was
transformed from domestic into international with English as the official language. This
gave guests from abroad an opportunity to participate in the CN conference.
In 2009, the conference proceedings were published in Springer’s CCIS series for
the first time, as volume 39. Since then, the conference proceedings have been pub-
lished in this series each year.
For many years, among the co-organizers, technical co-sponsors, and partners has
been the Section of Computer Networks and Distributed Systems belonging to the
Committee on Informatics of the Polish Academy of Sciences (PAN), IEEE Poland
Section, and the International Network for Engineering Education and Research
(iNEER).
VI Preface
This year, the 25th edition of the conference took place. Hence, the scientific
conference on Computer Networks has been present on the conference market for a
quarter of a century, giving attendees a chance to meet people, discuss valid and
important issues, as well as disseminate research results in the proceedings published in
a significant and recognized book series. Over the past 25 years of the conference’s
history, all important topics related to computer network development have been dis-
cussed at the conference and major breakthroughs in this area have been deliberated.
Thus, we believe that the event has had a significant contribution to the global pool of
achievements in this domain.
Computer networks are still the main means for transferring data among distributed
nodes of all computer systems currently available. Thus, this area of research and
applications is up to date and very important for current industrial and social activities,
as well as for the needs of the future. Computer network-related techniques and
technologies are not spectacular at their base but without them many spectacular ser-
vices would be unavailable.
For this jubilee edition of the CN conference, almost 90 papers were submitted. To
maintain the high quality of the conference proceedings, only 34 carefully selected
papers have been published in this book. Each paper was reviewed by three inde-
pendent reviewers in a double-blind process. Each of four chapters includes highly
stimulating studies that may interest a wide readership.
– Computer Networks
This chapter contains 12 papers. They refer to general networking issues, such as
architecture design, analyzing, modeling, and programming computer networks,
issues related to networked systems, their operations and management, Internet
networks, cooperative and cognitive networks, issues related to quantum technol-
ogy, as well as multimedia networks.
– Teleinformatics and Telecommunications
This chapter contains five papers related to communication architecture, wireless
systems, sensor and mobile networking, and isochronous communication.
Preface VII
– Queueing Theory
This chapter contains eight papers. The papers refer to the theory of queues and
queuing networks, as well as to network modelling and architecture design from the
queueing theory point of view.
– Cybersecurity and Quality of Service
This chapter contains nine papers that refer to cybersecurity issues in computer
networks, as well as topics related to the quality of service domain and related
innovative solutions.
On behalf of the Program and Organizing Committee of the CN Conference, we
would like to express our gratitude to all authors for sharing their research results and
for their assistance in producing this volume, which we believe is a reliable reference in
the computer networks domain.
We also want to thank the members of the Technical Program Committee and all
reviewers for their involvement and participation in the reviewing process.
If you would like to help us make the CN conference more attractive and interesting,
please send us your opinions and propositions at [email protected].
Executive Committee
All members of the Executive Committee are from the Silesian University of
Technology, Poland.
Co-ordinators
PAN Co-ordinator Tadeusz Czachórski
IEEE PS Co-ordinator Jacek Izydorczyk
iNEER Co-ordinator Win Aung
Program Committee
Program Chair
Andrzej Kwiecień Silesian University of Technology, Poland
Honorary Members
Win Aung iNEER, USA
Adam Czornik Silesian University of Technology, Poland
Bogdan M. Wilamowski Auburn University, USA
X Organization
Referees
Sponsoring Institutions
Technical Partner
Computer Networks
Queueing Theory
1 Introduction
Determining the optimal communication structures is the issue raised in many of
research works focused on improving the reliability, performance, and usability
of transmission systems (multiprocessor systems, military computer networks -
wired and wireless networks of stationary or mobile nodes). A lot of research
focuses on the problems with networks of the hypercube structure and on the
problems with location and relocation of network resources ([1–7]). In the era of
IoT (Internet of Things), results of research on “energy-efficient” communication
structures, prolong the life time of the network with battery-powered nodes, are
particularly important ([8–10]). The work is focused on developing new routing
protocols, effective medium access protocols, selecting of nodes collecting and
processing information from other nodes, constituting the catchment informa-
tion nodes (sink nodes), meeting points nodes (rendezvous points) or acting as
coordinator nodes ([10–14]).
In this paper we introduce a centralized procedure for determining the optimal
communication structure. The result of the procedure is the shortest path tree with
the root in the specific node. We abstract from considering the role this node can
play (server, coordinator, collector of information from other nodes). We assume
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 3–12, 2018.
https://doi.org/10.1007/978-3-319-92459-5_1
4 J. Chudzikiewicz and T. Malinowski
for example, as many articles on the same topic, that indication and use “our” opti-
mal communication structure in a network of wireless nodes, will result in reduc-
ing the number of packets generated by the nodes and exchanged between nodes,
thereby limiting power consumption and increase the life of network.
Our procedure for determining the optimal communication structure is cen-
tralized and we hope that it is universal, on the assumption that we will be able
to assess, based on various parameters (bandwidth of transmission channels,
delays, packets lost, etc.), the functioning of the network (wireless or wired) at
a given moment. We have assumed that we will get information about routing
and quality of communication connections (from sensors testing communication
channels). On this basis, we will be able to give an optimal (probably subop-
timal) communication structure resulting from the use of the best communi-
cation routes (dendrite of the best routes). These routes can then be entered
(distributed) into the configuration files of network devices. In our opinion, a
centrally determined suboptimal communication structure, considering not only
the number of hops from the source to the destination (in our procedure only this
characteristic has been taken into account), but also other important parameters
and regardless of the routing protocol used (whether for wired or wireless net-
works) will have a positive effect on the functioning of the network (minimizing
delays, energy consumption by communication nodes, etc.). We also assumed
that the analyzed network is rather small (cluster of whole network) and in our
assumptions it’s size is limited to ten nodes.
The paper is organized as follows. In Sect. 2, basic definitions were intro-
duced. The calculation of attainability for exemplary structures were presented.
In Sect. 3, the proposal of the method and the algorithm of determining opti-
mal communication structure was presented. In Sect. 4, the results of simulation
tests for proposed method verification were described. In Sect. 5, some conclud-
ing remarks were presented.
Definition 2 [6]. Let ϕ (e |G ) = d (e, e |G ) for e ∈ E (G) be attainability
e ∈E(G)
of the node e in the network G and Φ (G) = ϕ (e |G ) be attainability of
e∈E(G)
the network G.
Definition 3 [7]. Let T = E, U ∗ be the dendrite i.e. such coherent acyclic
partial graph of G that:
Denote by T (e) for e ∈ E(G) the set of all possible dendrites determined for
node e.
min
Let Φmin (T (e)) =t∈T (e) ϕ (e |t ) be the value of minimal attainability
e∈E(t)
for T (e).
The dendrite T is a base to determine the communication structure of G.
The algorithm for determined dendrite T is presented in [7]. The method and
the algorithm for determined the optimal communication structure based on the
dendrites determination is presented in Sect. 3.
The method consists of fourth stages. In the first stage for G, as the first node
min min
we choose a node that r (e |G ) =e ∈E(G) r (e ) or ϕ (e |G ) =e ∈E(G) ϕ (e ). In the
second stage for the chosen node we determine all possible dendrites T (e) for
e ∈ E (G). In the third stage, for each dendrite determined in the second stage,
the value of attainability Φ (T (e)) is calculated. In the fourth stage, based on
the attainability calculated in the third stage, the dendrite T , which is an opti-
mal communication structure satisfying the condition Φmin (T (e)) is determined.
Based on the presented method the algorithm for determining the optimal com-
munication structure was developed.
The algorithm for determining the optimal communication structure.
Step 1. (first stage)
Calculate r (e |G ) and ϕ (e |G ) for e ∈ E (G).
min
Choose a node e∗ ∈ E (G) such that r (e∗ |G ) =e ∈E(G) r (e ) or
6 J. Chudzikiewicz and T. Malinowski
min
ϕ (e∗ |G ) =e ∈E(G) ϕ (e ).
Selected node ei will be a central node of G.
Step 2. (second stage)
For the chosen node e∗ determine set T (e∗ ), wherein r ( e∗ | T ) = r ( e∗ | G) .
Step 3. (third stage)
Calculate Φ (t (e∗ )) for t ∈ T (e∗ ).
Step 4. (fourth stage)
min
Choose a dendrite t such that Φ (t) =t ∈T (e∗ ) Φ (t ).
Step 5.
The end of the algorithm.
For illustrating the algorithm’s operation, consider the following example.
Example 1. Let the structure G1 (presented in Fig. 1) be the basis for deter-
mining the optimal communication structure.
In the first step of the presented algorithm, the radius and the attainability
for each node of G1 must be calculated. In the Table 1 the results of calculating
radius (A) and attainability (B) of G1 ’s nodes are presented.
Table 1. The results of determining the radius (A) and the attainability (B) of G1
A B
e ∈ E (G1 ) r (e |G1 ) e ∈ E (G1 )/d (e, e |G1 ) 1 2 3 4 ϕ (e, G1 )
e0 3 e0 3 3 2 0 15
e1 2 e1 4 4 0 0 12
e2 4 e2 2 3 2 1 18
e3 3 e3 3 3 2 0 15
e4 3 e4 2 3 3 0 14
e5 4 e5 2 3 2 1 18
e6 3 e6 4 3 1 0 13
e7 4 e7 2 4 2 0 16
e8 4 e8 2 4 2 0 16
The Method of Determining 7
Next, the node with a minimal radius or (if nodes with a minimum radius
value is more) the node with a minimal attainability is chosen. In the case of G1 ,
the node with the minimal radius, and minimal attainability is node e1 . In the
next step, for chosen node e1 , the algorithm determines the set T (e1 ) (presented
in Fig. 2) of possible dendrites and calculates the attainability (presented in
Table 2) for all of them.
In Table 3 the results of calculating radius (A) and attainability (B) of TOP T
are presented.
8 J. Chudzikiewicz and T. Malinowski
A B
e ∈ E (TOP T ) r (e |TOP T ) e ∈ E (TOP T ) / d (e, e |TOP T ) 1 2 3 4 ϕ (e, TOP T )
e0 3 e0 1 3 4 0 19
e1 2 e1 4 4 0 0 12
e2 4 e2 1 1 3 3 24
e3 3 e3 2 3 3 0 17
e4 3 e4 1 3 4 0 19
e5 4 e5 1 3 3 1 20
e6 3 e6 4 3 1 0 13
e7 4 e7 1 3 3 1 20
e8 4 e8 1 3 3 1 20
Φ (TOP T ) 164
system with the minimal number of network services. We set the LAN model
with an unspecified shape of network traffic and the selected http service. In
our case, when assessing the impact of the routing method (corresponding to
the chosen subgraph) on how the chosen service works, we decided that it would
be the best solution, with transparent results. Therefore, we only took care of
the homogeneity of links and network devices. What was important for us is
that in the randomness of generating network streams and the randomness of
client-server connections, the simulation results confirm the correctness of the
theoretical arguments.
All dendrites were modeled as computer networks with routers with attached
LAN segment and servers. Routers play a role of a dendrite’s node. For example,
the network topology of the single scenario (single dendrite) was shown in the
Fig. 4.
We used two important characteristics (in our opinion sufficient at this stage
of research). The first of them was global average Number of Hops (representing
an average number of IP hops taken by data packets reaching at a destination
node) and the second, average TCP Delay (representing delay of TCP packets.
This value is measured from the time an application data packet is sent from the
source TCP layer to the time it is received by the TCP layer in the destination
node for all connections).
We knew which communication structure for each set of dendrites is optimal
and we were looking for confirmation of the correctness of calculations performed
earlier. The collected results looked like this from Fig. 5. Figure illustrates aver-
age Number of Hops for the best dendrite t15 (the lowest drawn line) against
results for selected three other dendrites.
Complete results, in the form of a bar chart, for all dendrites from set T (e1 ) are
presented in Fig. 6. The highlighted bar (No 15) refers to the best structure t15 .
Similarly, for all dendrites from the selected set, average TCP Delay was
measured. The results are presented in Fig. 7.
The Method of Determining 11
Results of simulation studies (we expected the lowest values of Average Num-
ber of Hops and Average TCP delay for TCP-based services) confirmed the cor-
rectness of the developed method of determining the optimal communication
structure, determined analytically in section Sect. 3.
5 Summary
Correctness of developed method and its usefulness for determining optimal
communication structure was confirmed by simulation tests. In analytical cal-
culations two essential characteristics, number of hops and attainability, were
used. According to our expectations, in simulation tests you could also use other
characteristics, reflecting real condition of the network (in our study we used
only TCP delay, but it was quite enough to confirm the correctness of analytical
argumentations). The authors believe that the developed method can be used to
determine the optimal structure also in wireless networks (for example to extend
its life or for the efficient collection of information from wireless nodes). In the
nearest future we plan to investigate the impact of such a network monitoring
procedure with a periodically scheduled routing plan on how a specific network
of wireless nodes works.
At this stage, for a small communication structure, complexity of the devel-
oped algorithm was not calculated. Our observations show that the efficiency of
the algorithm depends on the number of nodes, the structure diameter and the
radius of the node for which dendrites were determined. Currently, calculations
are performed on a PC and it does not matter the memory usage and CPU load.
We notice the need to modify the procedure (to be fast and not burdening the
system) if it is going to be implemented by a wireless network node.
References
1. AlBdaiwia, B.F., Bose, B.: On resource placements in 3D tori. J. Parallel Distrib.
Comput. 63, 838–845 (2003)
2. AlBdaiwia, B.F., Bose, B.: Quasi-perfect resource placements for two-dimensional
toroidal networks. J. Parallel Distrib. Comput. 65, 815–831 (2005)
12 J. Chudzikiewicz and T. Malinowski
3. Bae, M.M., Bose, B.: Resource placement in torus-based networks. IEEE Trans.
Comput. 46(10), 1083–1092 (1997)
4. Imani, N., Sarbazi-Azad, H., Zomaya, A.Y.: Resource placement in Cartesian prod-
uct of networks. J. Parallel Distrib. Comput. 70, 481–495 (2010)
5. Moinzadeh, P., Sarbazi-Azad, H., Yazdani, N.: Resource placement in cube-
connected cycles. In: The International Symposium on Parallel Architectures, Algo-
rithms, and Networks, pp. 83–89. IEEE Computer Society (2008)
6. Chudzikiewicz, J., Zieliński, Z.: On some resources placement schemes in the
4-dimensional soft degradable hypercube processors network. In: Zamojski, W.,
Mazurkiewicz, J., Sugier, J., Walkowiak, T., Kacprzyk, J. (eds.) Proceedings of the
Ninth International Conference on Dependability and Complex Systems DepCoS-
RELCOMEX. June 30 – July 4, 2014, Brunów, Poland. AISC, vol. 286, pp. 133–
143. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07013-1 13
7. Chudzikiewicz, J., Malinowski, T., Zieliński, Z.: The method for optimal server
placement in the hypercube networks. In: Proceedings of the 2015 Federated Con-
ference on Computer Science and Information Systems, ACSIS, Vol. 2, pp. 947–954
(2015). https://doi.org/10.15439/2014F159
8. Niewiadomska-Szynkiewicz, E., Kwaśniewski, P., Windyga, I.: Comparative study
of wireless sensor networks energy-efficient. J. Telecommun. Inf. Technol. (2009)
9. Jindal, A., Liu, M.: Networked computing in wireless sensor networks for structural
health monitoring. In: IEEE/ACM Transactions on Networking (TON) (2012)
10. Brindha, L., Muthaiah, U.: Energy efficient mobile sink path selection using a
cluster based approach in WSNs. Int. J. Innov. Res. Comput. Commun. Eng. 3(3)
(2015)
11. Erzin, A.I., Plotnikov, R.V.: Using VNS for the Optimal synthesis of the commu-
nication tree in wireless sensor networks. Electron. Notes Discrete Math. 47, 21–28
(2015)
12. Rekha, G., AjeethaKumari, A.S.: High data aggregation in wireless sensor networks
using Rendezvous-Drina. Int. J. Emerg. Technol. Adv. Eng. 4(6), 139–144 (2014)
13. Ghotra, A., Soni, N.: Performance evaluation of ant colony optimization based
rendezvous leach using for mobile sink based WSNs. Int. J. Eng. Res. Dev. 11(07),
43–49 (2015)
14. Baby, S., Soman, M.: Rendezvous based techniques for energy conservation in
wireless sensor networks - a survey. J. Netw. Commun. Emerg. Technol. (JNCET)
3(3) (2015)
15. Sethi, A.S., Hnatyshin, V.Y.: The Practical OPNET User Guide for Computer
Network Simulation. Chapman and Hall/CRC, Boca Raton (2012)
Researching Measured and Modeled
Traffic with Self-similar Properties
for Ateb-Modeling Method Improvement
1 Introduction
One of the biggest challenges nowadays is the gradual shift from the Internet
of Devices concept to the new Internet of Things concept, given the aspirations
of those who developed these concepts to boost their user-friendliness and the
growing demand for dynamic scalability of networks that differ by scale, type
or functionality. Also, the revolutionary influence on traffic parameters changing
has an alteration of its internal structure. Based on today’s Internet research,
provided by Cisco, mobile traffic on 75% consists of the video traffic [1].
According to the forecasts of the same company, the share of video content
in the future will only be increasing. Another factor that significantly influences
the structure of traffic is the widespread introduction of cloud technologies. The
cloud computing paradigm has become the foundation of the modern economy
by offering subscription-based services anytime, anywhere with services paid by
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 13–25, 2018.
https://doi.org/10.1007/978-3-319-92459-5_2
14 O. Fedevych et al.
(or for different number of successive observation points), which act as a scale
of measurement.
The main difference between R/S estimation method and other existing sta-
tistical methods for analyzing of time series is that this method includes the time
direction in its analysis, while other known methods for this time are invariant.
The Hurst H coefficient is described by the empirical relation
R
= NH (1)
S
where R – the range of deviations values of the series x, S – standard deviation
x, N – number of observations.
Express the Hurst H factor as:
R
log
H= S (2)
log N
1
N
x̄(N ) = x(ti ) (3)
N i=1
t
X(t, N ) = [x(u) − x̄(N )] (5)
u=1
where 1 ≤ t ≤ N .
Calculated deviations (4), (5) are substituted in the formula (1) and there is
a Hurst coefficient.
Two methods for calculating the Hurst parameter are implemented in the
developed software module. Conducted calculations of the Hurst parameter are
implemented for the real traffic values and the modeled traffic values based on
the R/S method and the V/S method described in detail in [11,12].
Researching Traffic with Self-similar Properties 17
Traffic was captured at the point where it had already been merged and sent
(received) from the Internet. The network of the ACS department contains about
20 working computers, loaded on average from 8:30 to 17:30; about 4 computers
are loaded until 21:00, and 3 computer classes with 32 workstations are loaded on
average from 8:30 to 16:00. The measurements were carried out during the month
on each working day from 9.00 to 13.00 o’clock, at an average data transfer rate
of 150 Mbit/sec. However, for visualization of the conducted research, three days
in a row were randomly chosen.
The collected data was analyzed by the developed software solution in terms
of traffic; the results of the analysis are shown in Table 1.
Duration of data collection differs in samples, which may slightly affect the
Hurst coefficient. The simulation time is chosen identically to the time of data
capture on a network.
In the previously proposed method of modeling, the property of the alter-
nating period of the Ateb-functions was used to select modeling parameters.
In [13] is proved that the Ateb-cosine and the Ateb-sine are periodic with
period 2Π(m, n), where Π(m, n) is shown by the formula
1 1
Γ Γ
n+1 m+1
Π(m, n) = (7)
1 1
Γ +
n+1 m+1
where Γ ( n+1
1
), Γ ( m+1
1
) – gamma function.
Researching Traffic with Self-similar Properties 19
For the modeling, the parameters n, m were selected in such a way that the
modeling period corresponded to the period of real traffic. In order to apply
the self-similarity property to improve the traffic behavior modeling, the Hurst
parameter for Ateb-functions in the half-period was calculated by the formula
(7). These calculations are presented in Table 1. Parameter t - modeling time, s.
Not only the proximity of the period of real and modeled traffic, but also the
proximity of the Hurst parameter as the second factor are taken into account
when choosing the values of the parameters n, m, when implementing modeling
in the improved method (Fig. 2).
min |H(m, n) − Htr | → 0 (8)
n,m
where H(m, n) – Hurst parameter for Ateb-function, Htr – Hurst parameter for
real traffic.
The traffic modeling is implemented using the method with the addition of
the delta function after the parameters n, m are chosen with the consideration
of the period and self-similarity using the formula (8).
20 O. Fedevych et al.
Table 2. Hurst parameter calculation results for real traffic using R/S analysis
Hurst parameter value Hurst parameter value Traffic for Hurst parameter
(traffic for 10.05.2017) (traffic for 11.05.2017) value (12.05.2017)
0,776487 0,755443 0,578647
Table 3. Hurst parameter calculation results for modeled traffic using R/S analysis
In Figs. 3 and 4, the first column of the chart corresponds to the selected
data of real traffic sample, the Hurst coefficient values of which are shown in
Tables 3 and 4 in the first line. Comparing the results of calculations for real and
modeled traffic shows a larger spread of computing results for real traffic samples
compared with the model traffic samples. The comparison of the calculations by
Researching Traffic with Self-similar Properties 21
Fig. 3. Hurst parameter values for real and modeled traffic samples using R/S analysis.
Table 4. Hurst parameter calculation results for real traffic using V/S analysis for
k = 100
Table 5. Hurst parameter calculation results for modeled traffic using V/S analysis
for k = 100
Fig. 4. Hurst parameter values for real and modeled traffic samples using V/S analysis
for k = 100
Table 6. Hurst parameter calculation results for real traffic using V/S analysis for
k = 300
Table 7. Hurst parameter calculation results for modeled traffic using V/S analysis
for k = 300
R/S method (Tables 1, 2 and 3, Fig. 3) and the V/S method (Tables 4, 5, 6 and
7, Figs. 4 and 5) shows the higher values of the calculated Hurst coefficient by
about 0.7 according to the R/S method than by the V/S method is about 0.6.
Researching Traffic with Self-similar Properties 23
Fig. 5. Hurst parameter values for real and modeled traffic samples using V/S analysis
for k = 300
Consequently, it can be concluded that for the studied traffic samples, the R/S
method gives higher values of the Hurst coefficient.
The comparison of calculations of the Hurst coefficient for real traffic samples
using the V/S method for different values of the coefficient k (Table 4, k = 100)
and (Table 6, k = 300) shows that an increase of k value corresponds to increasing
of the Hurst coefficient value. On the contrary, for modeled traffic samples, the
increase of k value corresponds to reducing of the Hurst coefficient value (Table 5,
k = 100) and (Table 7, k = 300).
6 Conclusions
New trends in the development of computer networks create the need for new
approaches and strategies for their research, as well as a reappraisal of mod-
els designed to address such issues as scalability, elasticity, reliability, security,
sustainability and application of traffic behavior patterns.
This paper shows improvements in the traffic behavior modeling method
based on the consideration of traffic self-similarity parameters. Two methods for
calculating the Hurst parameter were used: R/S plot method and V /S analysis
method.
Committed studies have shown that for the traffic that is available in the
network of the ACS NULP department, the method that gives the higher value
of the Hurst parameter is the R/S method. This was observed in all cases that
were considered. In addition, this method has a faster computation time com-
pared to the V/S method in 7 times in average. So it can be concluded that
the R/S method can be used for the implementation in the network nodes for
determination of the Hurst parameter to improve the Ateb-modeling method,
developed before.
The selected methods are implemented in the corresponding software. The
work of the methods is illustrated in experimental calculations. The work has a
24 O. Fedevych et al.
practical application for studying the self-similar properties of traffic. The growth
of traffic volumes, transmitted through the network, as well as a significant
increase in the proportion of video files in traffic, causes the use of additional
traffic management tools directly at the nodes of the network. In order to manage
traffic at a network node and redistribute it to reduce delays, it is efficient to use
traffic modeling methods. Thereby, the investigation of self-similarity parameters
of traffic helps to increase the effective traffic management in the nodes of the
network.
References
1. The Zettabyte Era: Trends and Analysis. https://www.cisco.com/c/en/us/solutio
ns/collateral/service-provider/visual-networking-index-vni/vni-hyperconnectivity-
wp.html
2. Gelembe, E.: Steps towards self-aware networks. Commun. ACM 52(7), 66–75
(2009). https://doi.org/10.1109/CIT.2010.508
3. Toral-Cruz, H., Pathan, A.K., Ramirez Pacheco, J.C.: Accurate modeling of VoIP
traffic QoS parameters in current and future networks with multifractal and
Markov models. Math. Comput. Model. 57(11–12), 2832–2845 (2013). https://
doi.org/10.1016/j.mcm.2011.12.007
4. Dronyuk, I., Fedevych, O.: Traffic flows ateb-prediction method with fluctuation
modeling using Dirac functions. Commun. Comput. Inf. Sci. 718, 3–13 (2017).
https://doi.org/10.1007/978-3-319-59767-6 1
5. Mishura, Y., Ral’chenko, K., Seleznev, O., Shevchenko, G.: Asymptotic properties
of drift parameter estimator based on discrete observations of stochastic differen-
tial equation driven by fractional brownian motion. In: Korolyuk, V., Limnios, N.,
Mishura, Y., Sakhno, L., Shevchenko, G. (eds.) Modern Stochastics and Appli-
cations. SOIA, vol. 90, pp. 303–318. Springer, Cham (2014). https://doi.org/10.
1007/978-3-319-03512-3 17
6. Park, K., Willinger, W.: Self-similar network traffic: an overview. In: Self-Similar
Network Traffic and Performance Evaluation. Wiley (2000). https://doi.org/10.
1002/047120644X.ch1
7. Demydov, I., Klymash, M., Kharkhalis, Z., Strykhaliuk, B., Komada, P., She-
dreyeva, I., Targeusizova, A., Iskakova, A.: The research of the availability at
cloud service systems In: Proceedings Volume 10445, Photonics Applications in
Astronomy, Communications, Industry, and High Energy Physics Experiments
2017, 104451V (2017). https://doi.org/10.1117/12.2280885
8. Gnatushenko, V.V., Ali, D.: Studies of self-similar processes traffic based on the
ON/OFF model. In: Bulletin of the National University “Lviv Polytechnic”, Series
of “Computer Science and Information Technologies” - Lviv, No. 751, pp. 87–94
(2013). (in Ukrainian)
9. Ramirez-Pacheco, J.C., Torres-Roman, D., Toral-Cruz, H., Estrada-Vargas, L.: A
high performance tool for the test of long-memory and self-similarity. In: Simulation
Technologies in Networking and Communications: Selecting the Best Tool for the
Test, pp. 93–114. CRC Press, Taylor & Francis Group, USA (2014). https://doi.
org/10.1201/b17650-6
10. Estrada Vargas, L., Torres Romn, D., Toral-Cruz, H.: A study of wavelet analysis
and data extraction from second-order self-similar time series. Math. Probl. Eng.
2013, 1–14 (2013). https://doi.org/10.1155/2013/102834
Researching Traffic with Self-similar Properties 25
11. Cajueiro, D., Tabak, B.: The rescaled variance statistic and the determination of
the Hurst exponent. Math. Comput. Simul. 70, 172–179 (2005). https://doi.org/
10.1016/j.matcom.2005.06.005
12. Mandelbrot, B.B.: The Fractal Geometry of Nature. W. H. Freeman, NewYork
(1982). https://doi.org/10.1119/1.13295. 550 p. 8
13. Senyk, P.: Reversal of incomplete Beta function. Ukrainian Math. J. 3, 325–333
(1969). (in Ukrainian)
A Validation Method of a Real Network
Device Model in the Riverbed Modeler
Simulator
Dagmara Mazur(B)
1 Introduction
The development of the Internet and web applications forces the evolution and
appearance of new protocols and network mechanisms. Development or new
technologies creation can be performed using real networks or simulators. Con-
ducting research in both environments has its advantages and disadvantages.
Modifications of an existing protocol, implementations of a new protocol or a
network mechanism in real network devices involves high costs. The construction
of large real networks also means large financial and time outlays. However,
studies conducted in such networks allow to get accurate and detailed results
that may be observed in the target production environment.
By using simulators one can create only the model of real devices. Such a
model is only an approximate playback of phenomena or behaviours of a given
device. Computer simulation refers to mapping the actual behaviour of the device
through a computer program [1]. Simulators allow only to conduct research in
a virtual and not real environment. On the other hand, simulators have many
advantages [2] and some of them are as follows: possibility to study a very com-
plex phenomena, relatively easy way to change device parameters, a significant
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 26–39, 2018.
https://doi.org/10.1007/978-3-319-92459-5_3
A Validation Method of a Real Network Device Model 27
reduction of financial outlays needed to carry out the research and short time
required for reconfiguration of all devices. There are many simulators available
on the market, some examples are as follows: ns-3 [3], Riverbed Modeler [4],
OMNeT++ [5], REAL [6], NetSim [7], QualNet [8], J-Sim [9], and SSFNet [10].
The aim of this paper is to present a developed method of checking whether
a given real network device model properly reflects this device in the scope
of a tested application. The developed method allows to answer the following
questions: whether the results of tests performed in the simulator coincide with
the results which were obtained in the real environment; whether a given model
of the device can be used for tests carried out on a large scale, without the use
of real devices and a computer network.
2 Related Works
In the literature one can find results of tests carried out using various simula-
tors confronted with results obtained in real networks. The paper [11] focuses on
the comparison of results obtained in the OPNET Modeler simulator (OPNET
Modeler is the previous version of the Riverbed Modeler simulator), the ns-2 sim-
ulator, and the real network. The research concerns the network transmission
study for two types of data streams: the Constant Bit Rate (CBR) and the File
Transfer Protocol (FTP). The another paper [12] also concerns a transmission
of the CBR data stream, but the FTP data stream is not taken into account.
Moreover, the authors compared results obtained in simulators considered in the
previous publication with results obtained in the QualNet simulator. The paper
[13] presents results of research on packets queuing mechanisms in the ns-2 sim-
ulator and compares them with results of testing the same mechanisms in a real
network. Respectively, work described in the paper [14] focuses on model credi-
bility verification for network devices used for military purposes in the OPNET
Modeler simulator. The research concerned packets queuing mechanisms opera-
tion in terms of the performance.
This paper presents research results on the adequacy of queuing mechanisms
operation implemented in the router model in the Riverbed Modeler simulator.
Simulation results are compared to research results achieved during testing the
operation of these mechanisms in a real network. The Riverbed Modeler simu-
lator was chosen for this research due to its popularity in academic, commercial
and industrial environments. The paper expands work presented in [13] and [14]
with different set of selected queuing mechanisms, and focuses on the comparison
of mechanisms behaviour. Additionally, in the developed method assessment, the
accuracy of the device model is performed with the use of statistical inference
method.
Figure 1 shows a scheme of the validation process of the real device model.
The first step in the validation process is to conduct independent research in a
real and simulated environment. In the next step obtained research results are
compared with each other. If the developed device model does not reflect the
real phenomenon in the expected way, attributes of the device model should be
adjusted, and the research should be repeated in the simulated environment.
Then, the comparison of test results should be repeated. The device model
attributes are iteratively adjusted until the developed device model is reflect-
ing the real phenomenon in the expected way.
Fig. 1. Scheme of the developed validation process of the real device model.
4 Completed Research
4.1 Research Environment
Research consist in checking the adequacy of operation of the router model in the
Riverbed Modeler simulator in relation to the operation of the real device. The
router model was validated for the behaviour of selected queuing mechanisms. To
conduct these research two environments should be prepared: real and simulated
ones. The physical topology of the real network is shown in the Fig. 2, and the
topology of the simulated network is shown in Fig. 3.
The real computer network has been equipped with two Cisco 2620 routers:
R1 and R2, two switches: S1 and S2 and traffic generator TG and traffic receiver
TR. The generator and the traffic receiver were realized using application IP
Traffic - Test and Measure [17]. In order to obtain correct research results traffic
generator TG and traffic receiver TR must indicate simultaneously the same
system time. Therefore, their operating system clocks were synchronized with
the clock of the external NTP server [18]. Both switches were connected with
other network elements using ethernet link with the bandwidth of 100 Mb/s, and
both routers were connected using serial link with the bandwidth of 128 kb/s.
This allowed the creation of a so-called bottleneck on the serial link, which is
necessary to observe the characteristic operation of selected queuing mechanisms.
30 D. Mazur
All performed tests A, B, and C were carried out in the real network and in the
Riverbed Modeler simulator. After the first series of tests, it turned out that
the throughput values of traffic streams sent by router R 1 in the simulator are
about 25% smaller than the values received on the router R1 in the real network.
The study of this case revealed the fact that both routers (R1 and R 1) with
configured the queuing mechanism on its interface, automatically reserve only
75% of the interface bandwidth for the needs of defined queues. In turn the real
router was using the remaining 25% of the interface bandwidth when no traffic
exist outside defined queues. The observed behaviour is the first discrepancy
found in the implementation of the router model in relation to the real device.
After customizing the configuration of router model in the Riverbed Modeler
simulator all tests were repeated in the real and simulated network. Adjusting
the configuration of the router model depends on setting the value of 100 in the
field max-reserved-bandwidth on its serial interface [21].
A Validation Method of a Real Network Device Model 33
Data samples received from the real and simulated environment were checked
using the statistical inference method described in Sect. 3. Tests A, B and C were
in the scope of the statistical verification. One can find below the procedure used
for each stage of the mentioned method.
STAGE I: The following research hypotheses were formulated:
The null hypothesis H0 – The average of traffic stream throughput in the real
environment is not significantly statistically different from the average through-
put obtained in the Riverbed Modeler simulator.
The alternative hypothesis H1 – The average of traffic stream throughput
in the real environment is significantly statistically different from the average
throughput obtained in the Riverbed Modeler simulator.
STAGE II: Assumed α = 0, 05 as a level of significance.
STAGE III: Statistical Student’s t-test was selected, because all obtained
results have a normal distribution, sets of traffic stream throughput results in the
real environment and in the Riverbed Modeler simulator have similar numbers,
variances of results obtained in both environments are similar – homogeneous
and this results are measured on interval scale (interval) – samples can be ordered
and have a unit of measure [kb/s].
STAGE IV: A statistical Student’s t-test T value calculation with the follow-
ing equation:
X1 − X2
T = (1)
Sx1 −x2
(n1 − 1) · s21 + (n2 − 1) · s22 1 1
Sx1 −x2 = · + (2)
n1 + n2 − 2 n1 n2
where:
X1 − the average value of the traffic stream throughput in the real envi-
ronment
X2 − the average value of the traffic stream throughput in the Riverbed
Modeler simulator
s21 − the variance of traffic stream throughput in a real environment
s22 − the variance of traffic stream throughput in the Riverbed Modeler
simulator
n1 − the samples number of traffic stream throughput in a real environment
n2 − the samples number of traffic stream throughput in a real Riverbed
Modeler simulator
STAGE V: The critical value t is read from the Student’s t-distribution tables
for the level of significance α = 0, 05 and the number of degrees k of freedom
expressed by the formula:
k = n1 + n2 − 2 (3)
STAGE VI: When the following condition is met:
|T | < t (4)
Acceptance decision on the null hypothesis H0 is making and the alternative
hypothesis is rejecting H1 . Otherwise, the alternative hypothesis H1 is accepted.
34 D. Mazur
PQ mechanism (Figure 5): Packets from traffic stream no. 1 are routed to the
high priority queue, and packets from traffic stream no. 2 are routed to the
medium priority queue; then the scheduling algorithm is putting the packets in
the router’s interface as per the rule: packets from a high priority queue have
priority over packets from other queues.
CQ mechanism (Figure 6): Packets from traffic stream no. 1 are routed to the
first queue, and packets from traffic stream no. 2 are routed to the second queue;
then the Weighted Round Robin algorithm (WRR) is putting packets in the
router’s output interface. Packets from the first queue should be sent as first
until their total number of bits reach the value set for this queue (2/3 of the
serial link bandwidth).
LLQ mechanism (Figure 7): Packets from traffic stream no. 1 are routed to the
first queue – priority queue, and packets from traffic stream no. 2 are routed
to the second queue. Then the packets are scheduled in the router’s output
interface. Packets from the first queue should be sent as first until their total
number of bits reach the value set for this queue (64 kb/s – at the layer 2 level
of the ISO/OSI model).
Fig. 8. Graph of the throughput dependence on the time after conducting the test A.
After usage the statistical inference method, it turned out that for both traf-
fic streams the alternative hypothesis was accepted. The results of the average
throughput of the traffic stream no. 1 and no. 2 in the real environment signifi-
cantly differ statistically from the results of the average throughput of the traffic
stream no. 1 and no. 2 obtained in the simulator. This means a negative result of
the validation of the Cisco 2620 router model in the Riverbed Modeler simulator.
Current implementation of the router model cannot be used for conducting the
research of the PQ mechanism on a large scale network.
A detailed analysis of the code of the implemented PQ mechanism in the
Riverbed Modeler simulator and its impact on the obtained research results will
be the subject of further research.
Test B – Research Results. Figure 9 shows the results of the conducted test
B. The research results shown that the Cisco 2620 router model in the Riverbed
Modeler simulator perfectly reflects the behaviour of the real router for the CQ
mechanism. After 60 s of test B duration, the throughput of the traffic stream
no. 1 is equal to the bandwidth allocated to the first queue (approximately
77 kb/s – 2/3 of the available bandwidth), and the throughput of the traffic
stream no. 2 is equal to the bandwidth allocated to the second queue (approx-
imately 37 kb/s – 2/3 of available bandwidth). The rest of packets from both
streams is discarded.
As a result of usage the statistical inference method, it turned out that for
both traffic streams the zero hypothesis was accepted. The results of the average
throughput of the traffic stream no. 1 and no. 2 in the real environment do
not significantly differ statistically from the results of the average throughput
A Validation Method of a Real Network Device Model 37
of the traffic stream no. 1 and no. 2 obtained in the simulator. This means a
positive result of the validation of the Cisco 2620 router model in the Riverbed
Modeler simulator. Current implementation of the router model can be used for
conducting the research of the CQ mechanism on a large scale network.
Fig. 9. Graph of the throughput dependence on the time after conducting the test B.
Fig. 10. Graph of the throughput dependence on the time after conducting the test C.
38 D. Mazur
Test C – Research Results. Figure 10 shows the results of the conducted test
C. The research results shown that the Cisco 2620 router model in the Riverbed
Modeler simulator does not introduce a bandwidth limitation for the first queue
(priority queue). Therefore, the research results conducted for the LLQ and PQ
mechanisms in the simulated network overlap with each other for both traffic
streams.
Despite such divergent research results, procedures of the statistical inference
method was conducted. The result of the Cisco 2620 router model validation in
the Riverbed Modeler simulator is negative as the null hypothesis was rejected.
Current implementation of the router model cannot be used for conducting the
research of the LLQ mechanism on a large scale network.
5 Summary
The paper describes the validation method of the real device model. In the
developed method assessment of the accuracy of the device model is made with
use of the statistical inference method.
The use of the developed method was demonstrated on the example of val-
idation of the Cisco 2620 router model. The paper presents research results on
the adequacy of operation of the router model in the Riverbed Modeler simulator
in relation to the operation of the real router in the real computer network. The
router model was validated for the behaviour of the PQ, CQ and LLQ mecha-
nisms. Accuracy assessment of the router model was made on the basis of the
throughput parameter.
After the first series of tests, it turned out that throughput values of traffic
streams received in the simulator were about 25% smaller than values received
in the real network. The developed model did not reflect the real phenomenon
in the expected way, so the configuration of the device model in the simulator
was adapted in accordance with the scheme of the validation process shown in
Fig. 1. Then the accuracy research of the model was repeated. For this purpose,
the statistical inference method was used, in which Student’s t-test was selected
to verify the research hypothesis.
After another iteration of the conducted research, the validation of the Cisco
2620 router model received a positive result only for the CQ mechanism. For the
PQ and LLQ mechanisms, the results of the average throughput of the traffic
stream no. 1 and no. 2 in the real environment significantly differ statistically
from the results of the average throughput of the traffic stream no. 1 and no. 2
obtained in the simulator. This involves a negative result of the validation of
the Cisco 2620 router model in the Riverbed Modeler simulator. The current
implementation of the router model cannot be used for conducting a research of
the PQ and LLQ mechanisms on a large scale network. Thus, another validation
of the router model in the field of the PQ and LLQ mechanisms should be
preceded by a modification of the implementation of these mechanisms in the
simulator; and that will be the subject of the further research.
A Validation Method of a Real Network Device Model 39
References
1. Balci, O.: Validation, verification, and testing techniques throughout the life cycle
of a simulation study. In: IEEE Winter Simulation Conference, pp. 215–220 (1994)
2. Breslau, L., Estrin, D., Fall, K., Floyd, S., Heidemann, J., Helmy, A., Huang, P.,
McCanne, S., Varadhan, K., Xu, Y., Yu, H.: Advances in network simulation. IEEE
Comput. Magaz. 33, 59–67 (2000)
3. NS, Discrete Event Network Simulator. http://www.nsnam.org. Accessed 21 Feb
2018
4. Riverbed Modeller, Network Simulator. https://www.riverbed.com/. Accessed 21
Feb 2018
5. OMNeT++, Discrete Event Simulator. https://www.omnetpp.org/. Accessed 21
Feb 2018
6. REAL, Network Simulator. http://www.cs.cornell.edu/skeshav/real/overview.
html. Accessed 21 Feb 2018
7. NetSim, Network Simulation and Emulation Platform. http://www.tetcos.com/
index.html. Accessed 21 Feb 2018
8. QualNet, Network Simulator. www.scalable-networks.com. Accessed 21 Feb 2018
9. J-Sim, Java-based simulation system. http://www.physiome.org/jsim/. Accessed
21 Feb 2018
10. SSFNet. http://www.ssfnet.org/. Accessed 21 Feb 2018
11. Lucio, G.F., Paredes-Farrera, M., Jammeh, E., Fleury, M., Reed, M.J.: OPNET
modeler and NS-2: comparing the accuracy of network simulators for packet level
analysis using a network Testbed. In: ICOSMO, vol. 2, pp. 700–707 (2003)
12. Puneet R., Srinath P., Raghuraman R.: Bridging the gap between the reality and
simulations: an Ethernet case study. In: IEEE 9th International Conference on
Information Technology (ICIT 2006), pp. 52–55 (2006)
13. Andreozzi, S.: Differentiated services: an experimental vs. simulated case study.
In: IEEE Seventh International Symposium on Computers and Communications,
pp. 383–390 (2002)
14. Boltjes, B., Thiele, F., Fernandez Diaz, I.: Credibility and validation of simulation
models for tactical IP networks. In: IEEE Military Communications Conference,
pp. 1–10 (2006)
15. Heidemann, J.: Expanding confidence in network simulations. IEEE Netw. Magaz.
15, 58–63 (2001)
16. Kowalski, L.: Statystyka. Bel Studio, Warsaw (2005)
17. IP Traffic - Test and Measure. https://www.zticommunications.com/iptraffic/.
Accessed 21 Feb 2018
18. RFC 958: Network Time Protocol (NTP). http://tools.ietf.org/html/rfc958.
Accessed 21 Feb 2018
19. Adarshpal, S.S., Vasil, Y.H.: The Practical RiverbedUserR Guide for Computer
Network Simulation. CRC Press, Boca Raton (2013)
20. Odom, W., Cavanaugh, M.: Cisco QOS Exam Certification Guide. Cisco Press,
Indianapolis (2004)
21. Cisco website. http://www.cisco.com/c/en/us/support/docs/quality-of-service-
qos/qos-packet-marking/10100-priorityvsbw.html. Accessed 21 Feb 2018
Energy Efficient MPTCP Transmission
Over Channels with a Common
Bottleneck
1 Introduction
Nowadays, the networking devices, like phones, laptops, or servers, have installed
multiple communication interfaces (NICs), e.g., Ethernet, WiFi, or cellular. How-
ever, the design restrictions of the protocols created in the past permit only one
interface to be actively engaged in serving the application data stream at a time.
The other interfaces are incorporated if the active one fails, or if the applica-
tion dictates a switch according to certain quality measure. Such behavior is no
longer satisfactory owing to the widespread use of radio technologies. Trying to
maintain the ongoing session within a chosen radio channel, with highly vari-
able temporal characteristics (determined by the distance from the access point,
nearby obstacles, node mobility, interferences, etc.), has negative impact on the
user’s experience [1,2]. Instead, one would opt for a communication solution in
which the traffic is dynamically distributed among the available interfaces, with
explicit consideration of their current transfer capabilities.
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 40–51, 2018.
https://doi.org/10.1007/978-3-319-92459-5_4
Energy Efficient MPTCP Transmission 41
The recent proposals, like Multipath TCP (MPTCP) [3–5] promise to ensure
truly parallel and load-balanced traffic distribution. However, the reference
implementation of MPTCP [6] covers only the general protocol issues, leaving
area for further improvements and adjustments. One of such unresolved chal-
lenges – addressed in this work – is formulating a method of MPTCP stream
splitting into multiple sub-streams so that selected performance criteria are sat-
isfied. As the popularity and functional spectrum of mobile computers have out-
grown the progress in battery design, reducing the energy expenditure becomes a
critical factor to consider within the ever more stringent service and environmen-
tal constraints (green networking) [7]. Therefore, in the presented approach, the
emphasis is placed on improving the end user’s experience through better energy
economy while handling the transmission at the communicating terminals.
At a mobile device, the amount of dissipated energy depends both on the
power efficiency of NICs and application level activity, i.e., turning on and off
the display, triggering additional cores, GPU, or external sensors. For instance,
one can observe faster battery depletion when the data is sent though a secure
connection rather than in a plain-text form. The power drain rate also increases
when the information regarding the transferred data is rendered on the screen.
Therefore, in order to reduce the energy expenditure while effectuating the net-
work connectivity, one should shorten the time of data transfer and allow the
user to switch off the screen (and additional hardware components), or put the
application in an idle state. This paper proposes a new load-balancing solution
for the MPTCP scheduler, particularly well-suited for battery-powered devices
equipped with a few independent interfaces. Although addressing similar prob-
lems as in the current literature [8–11], the idea presented here differs both in
the objectives and in the way the traffic is distributed among the interfaces. The
paper focuses on the situation when the sub-streams directed through different
logical interfaces influence each other before reaching the destination, The trans-
mission through independent channels is considered as a special case, only. The
way the MPTCP stream is divided into sub-streams by the scheduler is deter-
mined as a solution of optimization problem set in a mathematical framework of
power dissipation. The performance assessment and comparison with the refer-
ence scheduler is not restricted to simulations but involves public networks and
real networking devices.
SPTCP 1
SPTCP 1
MPTCP controller
MPTCP scheduler
NIC
MPTCP buffer
Channel 1
Applica on
Receiver
SPTCP N
SPTCP N
NIC
Channel n
Fig. 1. MPTCP architecture with local feedback – the current power profile of NIC
and SPTCP internals. Solid line – data, dashed line – acknowledgments.
The specification of MPTCP does not define how the user’s data should be
distributed among the sub-channels. Sometimes, it is appropriate to use only
one path and switch to another only when the quality of service drops below a
predefined level. The primary intention of MPTCP, however, is to employ multi-
ple channels simultaneously. In its reference implementation [6], three schedulers
have been defined:
(a) round-robin – evenly distribute subsequent segments among the sub-
channels (insignificant in practice, serve as a theoretical baseline),
(b) redundant – send the same segment through all the available sub-channels
– results in low latency but leads to increased bandwidth consumption,
(c) default – send the data using the channel with the lowest smoothed round-
trip time (SRTT). Smoothing is performed by the filter typical for the
selected SPTCP dialect.
Solution (c) – proposed to increase the total effective throughput – is strongly
recommended by the authors of implementation [6]. In this paper, this solution is
treated as a reference one. Other schedulers described in the current literature,
e.g., [8–11], have not been adopted in the formal development works. On the
other hand, the default scheduler suffers from a number of disadvantages:
– sticky behavior [12] – when the smoothed round-trip time (SRTT) differs a
little among the active channels, the one with the shortest SRTT value is used
exclusively,
– imprecise SRTT estimates – and thus wrong channel selection – originating
from the buffer bloat (different, but generally large, queue lengths in the
buffers of intermediate devices on the established paths),
– Karn’s algorithm implications,
– spurious acknowledgments – if the channels differ much in their properties,
then the retransmission timeout (RTO) at the MPTCP level can be shorter
than the variance of SRTT in the ‘worse’ ones; then, the MPTCP stack mis-
takenly signals the sender that a segment has been lost;
– head-of-line blocking – if the buffers are too short at the end-points, then
some data cannot be temporary sent via the available channel because there
are unacknowledged data transmitted previously through the ‘worse’ ones.
Energy Efficient MPTCP Transmission 43
is the total energy dissipated by interface i ∈ [1, n], n being the number of
interfaces, pi (t) > 0 is the power necessary to transmit the data through this
interface at time t, Ti is the total transmission time at this interface, and D > 0 is
the power consumed by non-NIC system components (display, additional cores,
sensors, etc.). D can be obtained as a difference between the power consumed
at a given moment and the power drained when the system is in an idle state.
Meanwhile, the transmit power pi (t) [W] is a function of the power efficiency
of NIC – ρi (t) [W/bit], the number of bits sent through channel i – bi , and the
power necessary to keep the NIC in the operational state – wi [W]. It can be
expressed as
– the distance from the end-point to the hub (access point, head-end, or BTS),
– the mode of operation, which includes the selection standard ‘b’, ‘g’, ‘n’, ‘ac’,
band, RTS, or CCA mode in WiFi and band, GPRS, or the revision of the
UMTS class in the case of cellular interfaces,
– interferences level, number of retransmissions at the link layer.
44 M. Morawski and P. Ignaciuk
Due to large number of factors affecting ρi (t) and wi (t), these profiles should
be directly measured by the communication end-point (e.g., such approach is
suggested in [8]). The profile varies with time as a result of node mobility, con-
troller activity, or other terminals behavior. Here, piece-wise constant evolution
is assumed.
4 Analytical Background
Often, the paths established by the MPTCP subsystem are independent, i.e.,
there is no common bottleneck between the communicating peers. An energy-
oriented solution for the independent channels case has been presented in [13].
However, such premise is not always justified. The streams may encounter a
common bottleneck, or interfere through a third-party connection. The mutual
dependency may be persistent or temporary, and may result in network or appli-
cation performance decrease and is both difficult to predict and not necessarily
related to a common protocol framework. In the conducted tests: identical con-
nection end-points, transmission proceeding at the same time, yet using different
protocols; the paths differ significantly in SRTT (ipv4: 40–110 ms and ipv6: 60–
300 ms) and number of hops (ipv4: 9 hops and ipv6: 17 hops). Moreover, as the
ipv6 traffic traverses the potentially congested international backbone, it is more
likely to be exposed to throughput fluctuations.
In this paper, extremum seeking control [14] is used as a basis to find a
solution to problem (1) when the channels cannot be treated as independent
of each other. The idea behind extremum seeking control is to obtain optimal
system performance (according to a chosen measure) for an uncertain, possibly
non-linear dynamic system by probing it through a known excitation injected
into the control input. By observing the system response and the gradient of
performance index it is possible to retrieve the unknown plant properties. In the
typical implementation, the estimate of performance index gradient is obtained
through a periodic excitation applied to linear system representation. Usually,
this signal is much faster than the nominal plant dynamics. The response induced
by the injected perturbation can then be removed by a low-pass filter (Fig. 2).
Owing to the hard non-linearities and delays, the classical extremum seek-
ing approach cannot be directly applied to optimize the MPTCP transmission.
Therefore, in this work, a modified method is elaborated. In the classical app-
roach, by observing the performance index gradient, one estimates the unknown
system parameters. In the method proposed here, the system parameters (path
properties) are determined with high accuracy and thus assumed known, whereas
the gradient measurement is used to decide whether the mutual dependency
among the MPTCP sub-channels occurs, or not. The channels are deemed unre-
lated (independent) if the gradient is zero. Otherwise, an appropriate action
needs to be taken, as illustrated in Fig. 2. In the discussed method, in order
to assess the extent of mutual dependency of the sub-streams, the gradient of
performance index (1) needs to be evaluated. It is assumed that the device estab-
lishes two paths only, as is the most common situation in the considered applica-
tion area. The power efficiency is improved by changing the sub-channels load so
Energy Efficient MPTCP Transmission 45
Gradient es ma on and
Low-pass
+ feedback parameter
filter
adjustment
1 c1
Plant (path 1) with known parameters Unknown ϑ
coupling
2 c2 parameters
Plant (path 2) with known parameters
Gradient es ma on and
Low-pass
feedback parameter
filter
adjustment
Fig. 2. Classical approach to extremum seeking control [14] (above) and the proposed
one (below) with the additional excitation replaced by a legitimate signal from other
channels.
that the gradient ∇ϑ = ϑ̇ ≤ 0. Since the performance index ϑ(t) = f (c1 (t), c2 (t)),
the chain rule applied to (1) leads to
∂ϑ ∂ϑ
ϑ̇ = ċ1 + ċ2 ≤ 0. (4)
∂c1 ∂c2
Assuming pi and D change sufficiently slow, the energy expenditure related
T
to channel i may be approximated as ϑi = 0 i pi (t)dt ≈ pi Ti . Then, rewriting
(1) with Ti ≈ bi /av(ci ) and max Ti ≈ (b1 + b2 )/[av(c1 ) + av(c2 )], one obtains
b1 b2 b1 + b 2
ϑ = ρ1 + ρ2 + Dw , (5)
av(c1 ) av(c2 ) av(c1 ) + av(c2 )
The term ρi bi /av2 (ci ) in (6) can be physically interpreted as the inverse of energy
efficiency of path i and Dw (b1 + b2 )/[av(c1 ) + av(c2 )]2 , as the inverse of energy
efficiency of the communicating device as a whole.
Since by definition ρi , ci , bi , and Dw are all positive and bounded, according
to (6), the gradient follows the changes of the
channel capacity (with reverse sign)
and the energy dissipation decreases with ϑ̇ increasing. Therefore, the minimum
46 M. Morawski and P. Ignaciuk
−ρ1 av2b(c
1
1)
ċ1 − ρ2 av2b(c
2
2)
(7)
−Dw [av(c )+av(cb1
)] 2 (ċ1 + ċ2 ) − Dw
[av(c
b2
2 (ċ1 + ċ2 ) ≤ 0.
1 2 1 )+av(c2 )]
Thus,
otherwise.
In the steady state, when ċi → 0, applying L’Hôpital’s rule to (8) (or (9)),
one obtains
5 Implementation Issues
For the purpose of verification of the developed load-balancing strategies a new
Linux kernel module implementing (8)–(10) has been created. In addition to
this new scheduler, the Linux implementation encompasses the standard path-
manager that establishes the paths along which the data will be directed and
MPTCP master controller that targets the fairness issues. Since the objective of
Energy Efficient MPTCP Transmission 47
this work is to provide a method of stream division, only the scheduler has been
modified with respect to the reference MPTCP implementation [6]. The other
modules are left unaltered with the parameters set at their defaults, i.e., the
path manager operates in the full-mesh mode (the number of sub-streams is the
product of the number of logical interfaces at both peers) and no specific master
control is executed. The standard Linux congestion control algorithm (CUBIC)
supervises the individual SPTCP sub-streams.
In contrast to the default scheduler, in the proposed approach, the previously
selected paths influence the present scheduling decisions. To properly evaluate
(8)–(10), the scheduler uses the internal SPTCP variables (fi and τi ). In addition,
it needs to track variable ci to obtain ċi . For that purpose, a recurrent filter
(typical for the TCP implementations) is used, namely,
where k denotes the subsequent time instants of ċi evaluation. The averaging
coefficient α has been experimentally chosen as 1/16. In order to obtain the
allocation decision, scheduler (8)–(10) performs two iterations per MPTCP seg-
ment (mptcp for each sk loop): the first one provides the sub-stream coefficients
(ċi ), the second one finds the best channel for data transfer. The details of the
kernel module organization and power measurement one can find in [13], where
the case of independent channels has been considered. In the tests described
here in Sect. 6, the following artificially injected patterns have been applied: (a)
constant, (b) linear increase/decrease (simulates moving away, or getting closer
to a link layer hub), (c) stepwise (simulates handover, or getting in or out of
a radio shadow), and (d) oscillatory (simulates channel fading). Consequently,
in addition to already covering a broad spectrum of practical networking situa-
tions, new profiles can be seamlessly introduced into the applied framework for
conducting a variety of tests.
6 Evaluation
The developed scheduling solution has been verified using the setup based on the
general system architecture depicted in Fig. 1. The popular low-end Raspberry
Pi device has been chosen as the MPTCP client and a high-end virtual machine
in the local data center (in the cloud ) as the server, which corresponds to the typ-
ical use pattern in the MPTCP networking. During all the tests the server runs
unmodified, following the standardized MPTCP rules. In all the experiments,
the public network (neither Intranet, nor closed simulations) is employed. While
in such environment a single measurement is hardly repeatable, a large number
of trials allows one to filter the artifacts and gives a sound basis for the pro-
tocol assessment in a realistic rather than artificially created lab environment.
To minimize the influence of channel temporal variations and give statistically
meaningful results, the tests have been repeated multiple times.
48 M. Morawski and P. Ignaciuk
Two channel combinations have been tested. In the first one – scenario 1 –
the probability of a common bottleneck is low, in the second – scenario 2 –
high. The first scenario represents the case of a smartphone, or an IoT device
[16,17], communicating with the server, with one interface connected to a cable
network and the second inter-face connected to an LTE network. The cable and
LTE networks are unrelated. The measured initial SRTT of the cable network
channel varies within 70–85 ms and the segments traverse 7 hops, whereas for
the LTE connection the SRTT fluctuates within 80–400 ms and the segments
encounter 9 hops before reaching the destination. In the second scenario, the
same interface is used by the endpoints, yet the channels differ in the applied
network protocol. Such paths frequently influence each other. During the tests,
the first path consists of 9 hops and the measured SRTT varies in the interval
40–110 ms and the second path covers 17 hops with the SRTT fluctuating in the
range 60–300 ms.
where ϑdefault is the energy dissipated when the default scheduler operates,
whereas ϑproposed refers to the energy expenditure of scheduler (8)–(10).
Selected test results are presented in Table 1. The advantages of using the pro-
posed power-aware scheduler are highlighted when the amount of fluctuations
(congestion incidents, interferences, etc.) in the network grows. The advantages
of the discussed solution are particularly visible during rush hours (7–8 PM).
In scenario 1, the proposed scheduler outperforms the default one in terms of
lower energy expenditure (10–36%), and occasionally in terms of throughput. In
an uncommon situation, when the channel with a shorter SRTT dissipates more
energy (LTE), it is possible to obtain the gain as high as 90%. In scenario 2, the
power-aware scheduler gives 4–10% better results (maximum 12%) with respect
to the reference one.
Energy Efficient MPTCP Transmission 49
During ordinary hours (12 AM–4 PM), in scenario 1, the gain of using the
energy-aware schedulers oscillates between 3% and 25% and differs much in
subsequent test runs. Nevertheless, a case when the gain is negative has not
been observed. In scenario 2, the power saving is smaller gain is smaller than in
rush hours yet still meaningful with respect to the default solution.
When the network traffic is stable and low (e.g. in the early morning – 5–
6 AM) the proposed scheduler provides limited gain. The allocation decisions
are highly influenced by the buffer-bloat phenomenon (BB). While other net-
work users are absent, large buffers in the intermediate devices prohibit the
cwnd reduction at the end-points and SRTT increases. When the default sched-
uler controls the segment-to-path assignment, the energy greedy interface (LTE)
is erroneously chosen over the more economic one if the SRTT, elongated by BB,
exceeds the transfer time in the expensive one. The proposed scheduler is immune
to the BB effects – see also [18]. When the throughput does not undergo signif-
icant variations (ċi ’s are close to zero), then the proposed scheduler operates in
the steady-state conditions according to (10). Except for the segment ordering
there are no substantial differences comparing to the reference solution.
450 250 8
SPTCP#1
400 SPTCP#2 7
350 200
6
Throughput [Mbps]
in-flight data [seg]
300
SRTT [ms]
150
250 5
200 4
100
150
3
100 50 SPTCP#1
SPTCP#1 2 SPTCP#2
50
SPTCP#2 MPTCP
0 0 1
0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10
Time[s] Time[s] Time[s]
As a beneficial side effect, it has been noticed that even if the power coefficients
are not considered in the allocation decisions (ρ1 = ρ2 = 1, D = Dw = 0 in
(8)–(10)), the energy-aware scheduler gives on average a few-percent improve-
ment over the default one. This gain increases with the throughput fluctuations.
It is attributed to the BB reduction (as noticed also in the case of SPTCP in
[18]). Moreover, without any tricky heuristics, or link layer dependency [6], the
jitter is constrained to 2–4 segments and fast response to the channel variability
is obtained. In consequence, the redundant scheduler from the standard imple-
mentation [6] need not be applied, low buffer occupancy is observed, and the
risk of head-of-line blocking is limited. All these favorable characteristics are
obtained at a small computational cost.
References
1. Ignaciuk, P., Bartoszewicz, A.: Congestion Control in Data Transmission Networks:
Sliding Mode and Other Designs. Springer, London (2013). https://doi.org/10.
1007/978-1-4471-4147-1
2. Ignaciuk, P., Karbowańczyk, M.: Active queue management with discrete sliding
modes in TCP networks. Bull. Polish Acad. Sci. Tech. Sci. 62(4), 701–711 (2014)
3. Peng, Q., Walid, A., Hwang, J., Low, S.: Multipath TCP: analysis, design, and
implementation. IEEE/ACM Trans. Netw. 24(1) 596–609 (2016)
4. Xu, C., Zhao, J., Muntean, G.: Congestion control design for multipath transport
protocols: a survey. IEEE Commun. Surv. Tutor. 18(4), 2948–2969 (2016)
5. Ford, A., Raiciu, C., Handley, M., Bonaventure, O.: TCP extensions for multipath
operation with multiple addresses. Technical report 6824, RFC (2013)
6. Barré, S., Paasch, C.: Multipath TCP Linux Kernel implementation. http://www.
multipath-tcp.org
7. Kwak, J., Choi, O., Chong, S., Mohapatra, P.: Processor-network speed scaling
for energy-delay tradeoff in smartphone applications. IEEE Trans. Netw. 24(3),
1647–1660 (2016)
8. Deng, S., Netravali, R., Sivaraman, A., Balakrishnan, H.: WiFi, LTE, or both?
measuring multi-homed wireless internet performance. In: Proceedings on ACM
IMC, Vancouver, Canada, pp. 181–194 (2014)
9. Paasch, C., Ferlin, S., Alay, O., Bonaventure, O.: Experimental evaluation of multi-
path TCP schedulers. In: Proceedings on ACM SIGCOMM CSWS, Chicago, USA,
pp. 27–32 (2014)
10. Hwang, J., Yoo, J.: Packet scheduling for multipath TCP. In: Proceedings on 7th
International Conference on Ubiquitous and Future Networks, Sapporo, Japan, pp.
177–179 (2015)
11. Peng, Q., Walid, A., Chen, M., Low, S.: Energy efficient multipath tCP for mobile
devices. In: Proceedings on 15th ACM International Symposium on Mobile Ad
Hoc Networking and Computing, Philadelphia, Pennsylvania, USA, pp. 257–266
(2014)
12. Arzani, B., Gurney, A., Cheng, S., Guerin, R., Loo, B.: Impact of path charac-
teristics and scheduling policies on MPTCP performance. In: Proceedings on 28th
International Conference on Advanced Information Networking and Applications
Workshops (AINA), Victoria, BC, Canada, pp. 743–748 (2014)
13. Morawski, M., Ignaciuk, P.: On implementation of energy-aware MPTCP sched-
uler. In: Borzemski, L., Światek,
J., Wilimowska, Z. (eds.) ISAT 2017. AISC,
vol. 655, pp. 242–251. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-
67220-5 22
14. Ariyur, K., Krsti, M.: Real-Time Optimization by Extremum-Seeking Control.
Wiley, Hoboken (2003)
15. Kou, L., Liu, J., Hu, M.: A multiple-path TCP congestion control algorithm based
on sub flow correlation matrix. In: Proceedings on International Conference on
Cloud Computing and Internet of Things, Changchun, China, pp. 140–144 (2014)
16. Morawski, M., Ignaciuk, P.: Reducing impact of network induced perturbations in
remote control systems. Control Eng. Pract. 44(10), 127–138 (2016)
17. Morawski, M., Ignaciuk, P.: Network nodes play a game - a routing alternative in
multihop ad-hoc environments. Comput. Netw. 122, 96–104 (2017)
18. Cardwell, N., Cheng, Y., Gunn, C., Yeganeh, S., Jacobson, V.: BBR: congestion-
based congestion control. Commun. ACM 60(2), 58 (2017)
Light-Weight Congestion Control
for the DCCP Protocol for Real-Time
Multimedia Communication
1 Introduction
be window controlled, the stream may not be congestion controlled at all. Such
multimedia streams are called unresponsive, in that they cannot respond to
congestion. If an unresponsive flow meets a congestion controlled (responsive)
flow in the same link, the unresponsive flow shows a tendency to dominate the
transmission in the link. It was observed that in the case of Transmission Control
Protocol (TCP) transmissions, multimedia can overwhelm the traffic for TCP
flows. Lack of TCP-like congestion control was blamed for this effect, so protocols
that implements TCP-like congestion control are called TCP-friendly protocols.
For the last few years, because of a significant amount of multimedia traffic
in overall communication traffic, newly designed protocols are often required to
be TCP-friendly [2,9,16,17]. Nowadays, web browsers that use the Real-Time
Communications (WebRTC) technologies enable congestion control for trans-
mission of multimedia data, based on the TCP-Friendly Rate Control (TFRC)
[7] congestion control mechanism [10].
However, obligatory TCP-friendliness can cause problems in the case of real-
time multimedia transmissions carried out in medium and heavily congested net-
works. The aim of this paper is to analyze a light-weight congestion mechanism
intended for the Datagram Congestion Control Protocol (DCCP) working in the
TFRCs congestion control mode. The mechanism was designed for real-time mul-
timedia communication in medium and heavily congested networks. It is an imple-
mentation of our previous work [1], in which we substitute a linear throughput
equation for the original TFRCs throughput equation in the DCCP protocol.
The paper is organized as follows. The next Section is devoted to the
DCCP protocol. In Sect. 3 we describe the light-weight congestion control mech-
anism implemented for the DCCP protocol that conveyed real-time multimedia.
Section 4 shows the experimental environment that combines real network equip-
ment and an emulation server. Section 5 presents results of the experiments car-
ried out in the mixed, real and emulated environment. Section 6 summarizes our
experiences.
The first method directly implements the mechanism specified in the RFC
2581 [18] document - including the congestion control window, two areas of
probability (low and high probability of congestion increases) associated with
the mechanisms of slow start and exponential window growth, etc. This method
allows applications to maximally utilize available bandwidth and is identified as
mode CCID 2, specified in the RFC 4341 [5].
The second method, typical for TCP-friendly multimedia systems, describes
TCP’s behavior under congestion using the so-called TCP throughput equation,
and sends packets of TCP-friendly protocol according to the rate computed from
this equation. The best known TCP-friendly congestion control module, based
2
The UDP is not error controlled at all. The DCCP assures only reliable negotiation
of options and reliable congestion notification, as well as transmits full signalling
information about packet losses.
Light-Weight Congestion Control for the DCCP Protocol for Real-Time 55
on the throughput equation, is the TFRC [7]. According to the equation used
by the TFRC, the throughput of the TCP connection is a function of a packet
error rate (PER) [1,7]:
M SS
T (P ER) = · C·
RT T
−1
2 3
· · P ER + 12 · P ER · · P ER · 1 + 32 · P ER 2
(1)
3 8
The light-weight congestion control mechanism for the DCCP protocol has
been implemented in an environment of the Linux operating system. The Linux
kernel since version 2.6.x contains the implementation of the DCCP protocol
(stored in branch /net/dccp/) along with congestion control mechanisms imple-
mented for mode CCID 2 and CCID 3 (stored in branch /net/dccp/cids/). The
protocol’s implementation is build as a kernel module (dccp). Depending on the
initial configuration of the Linux kernel, the implementation can be loaded one
of two ways: immediately (loaded by the system during the start of the Linux) or
on demand (loaded by the user). The congestion control CCID 2 and 3 modes are
implemented as a separate modules (dccp ccid2 and dccp ccid3, respectively).
The original DCCP protocol implementation on Linux was written by
Arnaldo C. Melo. It uses standard socket application programming interface
(API). Therefore, the code of user programs, written for server and client, is
similar to the code of a regular TCP application. Some parts of the DCCP
implementation share code with the Linux’s TCP implementation and any other
Linux’s implementation of INET3 transport protocols, such as the Stream Con-
trol Transmission Protocol (SCTP). In the case of the DCCP implementation,
the server initializes a socket, binds it to a port, and waits to accept clients to
connect. The client needs only to initialize a socket and connect to the server.
This model of connection setup is similar to the TCP’s connection setup.
After connection setup, a client and a server are able to exchange data. If
DCCP’s congestion control mechanism recognizes that the sending rate is too
large, the current data packet will be refused before it can be sent to a network.
Thus, the user’s programs that use the DCCP must check the status of each
sending routine.
Our implementation for the new DCCP’s congestion control module has been
created for the Linux 4.4.0 kernel. We built a new Linux kernel module, analogous
to existing modules for CCID 2 and 3 dccp ccid lin. Our implementation included
a base congestion control module (ccid.c), which registers and calls the currently
used congestion control module. Parameters of both the DCCP and congestion
control modules are set by variables exported from the dccp ccid lin module and
the basic dccp module. This method enables (re)configuration of kernel module
parameters at runtime.
The basic data needed for proper working of the dccp lin module are stored
in the ccidlin hc tx sock structure. The structure contains, for example, current
sending rate (tx x), receive rate (tx x recv), current loss event rate (tx p), mean
packet size, expressed in bytes (tx s), estimate of current round trip time (tx rtt),
target bit rate of transmitted multimedia stream (tx tbr).
At the very beginning the current sending rate tx x must be set to the tx tbr
value. The tx tbr can be set as one of the kernel module parameters or by
the additional socket option. During transmission, when the DCCP packet is
processed, the function ccidlin hc tx update x is called. This function updates
the current sending rate tx x. If the transmission is inactive for idle period (more
than 2*RTT or more than an Application-Limited Periods [6]) then the current
3
A group of internet protocols in the Linux system.
Light-Weight Congestion Control for the DCCP Protocol for Real-Time 57
sending rate tx x is set to the initial sending rate. If errors occur, the current
sending rate tx x is modified according to the formula (2).
4 Test Environment
Experiments were carried out using a mixed environment, depicted in Fig. 1,
where real fragments of a test network are combined with the emulated one.
The emulated fragment of the test network is marked in gray in Fig. 1. As the
network emulator, the Berkeleys ns-2 simulator [4] working in emulation mode
was used. The choice of the emulator is guided by its light-weight packet pro-
cessing methodology (only chosen header information is processed in emulated
nodes), which is characteristic of simulators. Fast, light-weight packet processing
allows the ns-2 for emulation of both more network nodes and more high-speed
connections than typical emulators, such as the ns-3, using the same emulation
server. For the emulation server, a dual processor machine, equipped with two
Intel Xeon processors and six Gigabit Ethernet interfaces, was used. The origi-
nal ns-2 software has been supplemented by extension [3,14], which allows the
ns-2 to better emulate real-time multimedia traffic, as well as by extension [15],
designed to use an external switch (switches S1 and S2 in Fig. 1.) as a traf-
fic expander. Standard DCCP protocol, implemented in the Linux kernel, was
extended with improvements described in the Sect. 3, which enable usage of the
linear throughput equation.
– the DCCP with TFRC congestion control (CC) mechanism, in other words
the DCCP working in the standard CCID 3 mode (curves labeled DCCP
TFRC CC in Figs. 2 and 3),
– the DCCP with light-weight congestion control mechanism, which use linear
throughput equation (curves labeled DCCP light-weight CC in Figs. 2 and 3),
– the DCCP with TCPs congestion control mechanism, i.e. the DCCP working
in CCID 2 mode (curves labeled DCCP TCP’s CC in Figs. 2 and 3).
For the sake of comparison, transmissions with the use of typical RTP/UDP
protocol stack also were carried out (curves labeled RTP in Figs. 2 and 3).
As a background traffic, a number of TCP transmissions are carried out with
the use of the iPerf tool [11], also working under the control of the Linux system.
Senders of background traffic (from ST CP1 to ST CPK in Fig. 1) are connected
to the router R1 using the traffic expander S1, and receivers of TCP traffic
(RT CP1 to RT CPK ) are connected to router R3 through the traffic expander S2.
Transmissions are performed between the pair of nodes ST CPi and RT CPi , i =
0, ..., K. If the total number of TCP flows K is close to 0, the network will not
be congested. The growth of number of flows causes growth of congestion.
5 Results
During all of the experiments throughputs achieved for video and bulk data
transmissions were measured and the number of packet drops were recorded.
Light-Weight Congestion Control for the DCCP Protocol for Real-Time 59
The number of background TCP flows were changed from 0 to 10. The number
of foreground video streams was equal to one, but (to avoid the influence of
individual video clips on overall results) the transmitted stream was made of
clips randomly chosen from sequences [19], and the transmission of the currently
chosen clip started from a randomly chosen video frame. Each experiment was
repeated over 10 times and the results were averaged.
Figures 2 and 3 presents throughput of both the foreground video stream and
the background TCP flows as a function of the number of TCP flows K. K equal
to zero denotes that the bottleneck link was dedicated to the video transmission
(the video stream did not have to share this link with any background TCP
flow). Because real-time video transmission is rate-limited (transport protocol
cannot send more data than the amount of data generated in real-time), the
throughput of the video transmission achieved for K = 0, i.e. 63.5 Mbps, is the
maximum.
As is depicted in Fig. 2, the presence of background trafficreduces the
throughput of the video stream transmitted by the RTP protocol working over
the UDP. In conditions as described in the previous Section, one competing
TCP flows reduces mean video throughput by 0.5 Mbps (less than 1%), two
TCP flows by 1.5 Mbps (about 2.5%), three by 3.5 Mbps (more than 5%), and
ten competing TCP flows reduces mean video throughput by 14.5 Mbps (23%).
The mean throughput of the video stream transmitted with the use of the
DCCP protocol heavily depends on the applied method of congestion control.
The DCCP that works in CCID 2 mode (exact implementation of the TCP’s
CC) is typical for the TCP fair bandwidth allocation. The throughput of the
60 R. R. Chodorek and A. Chodorek
bottleneck link is divided amongst all foreground and background flows and
streams that share this link. As a result, the DCCP is not able to preserve the
real-time character of the video stream even in the case of a lightly congested
bottleneck link. Even one competing TCP flow was already enough to reduce
the mean throughput of the video stream by more than 10 Mbps (to 51 Mbps,
which gives 80% of the mean throughput of the video stream in the dedicated
link, K = 0). Two background flows competing for bandwidth with one video
stream reduces the video throughput by another 15 Mbps, and the video stream
achieves throughput of 35.5 Mbps (56% of 63.5 Mbps obtained for K = 0). In
the case of K = 10, the throughput of the video stream collapses to 12.5 Mbps
(20% of value measured for K = 0). It is worth mentioning here that CCID 2 is
not recommended for multimedia, and the results are only comparative.
The DCCP congestion control mode CCID 3, which implements TFRC con-
gestion control, is intended for multimedia transmission. The replacement of
the exact implementation of TCP’s congestion control by the approximation of
its behaviour, given by the formula (1), which causes “reasonable fairness” of
the TFRC competing for bandwidth with TCP flows, improves behaviour of the
DCCP protocol during transmission of video streams. One TCP flow that shares
the bottleneck link with the DCCP working in mode 3 is able to reduce the mean
throughput of the video by only 3.5 Mbps (instead of 12.5 Mbps observed during
the transmission with the use of CCID 2). However, it is still much worse than
in the case of the RTP transmission, where a reduction of 3.5 Mbps was only
seen when K = 3. Initially the rate of the descent of the throughput curve is
smaller than in the case of the CCID 2, but when congestion grows the rate of
descent also grows and curves plotted for CCID 2 and CCID 3 are close to each
other. Generally, the condition of reasonability is satisfied. Throughput of the
video stream observed for CCID 3 is within the range of 1 ∗ T2 (K) to 2 ∗ T2 (K),
with a median of 1.58 ∗ T2 (K = 8) and two mode values (1.48 ∗ T2 (K), K = 2
and K = 9; and 1.64 ∗ T2 (K), K = 3 and K = 10, where T2 (K) is a throughput
of the video stream observed for CCID 2 when the number of competing TCP
flows is K. The biggest difference between throughput of CCID 3 and CCID 2
were observed for K = 4 (the ratio between throughputs of CCID 3 and CCID
2 achieves 1.8), K = 5 (a ratio of 1.73) and K = 6 (a ratio of 1.65).
Video transmissions are rate-limited, and (to achieve real-time conditions of
transmission) videos transfer rates must not exceed their rate limits. Fairness,
as well as reasonable fairness toward competing flows, means that the work in
the real-time regime is only possible to a limited extent. As a result, the DCCP
working in congestion control mode CCID 3 is able to replace the UDP in the
RTP/UDP protocol stack only if a network is lightly congested. Replacement
of the TCP throughput Eq. (1) by the linear RTP’s Eq. (2) allows congestion
control mechanisms to have a more aggressive behaviour and for the resignation
of equality, especially problematic for multimedia.
An effect of the use of the light-weight congestion control based on the linear
throughput Eq. (2) is a flat, quasi-linear curve of video throughput shown in
Fig. 2 (the curve labeled DCCP light-weight CC). In the case of non-congested
Light-Weight Congestion Control for the DCCP Protocol for Real-Time 61
The mean throughput of the transmitted video (Fig. 2) determines the band-
width available for background traffic. Thus, it has a major impact on the over-
all throughput of TCP flows (Fig. 3). As was to be expected, the largest overall
throughput of TCP flows were observed when the classic TCP’s congestion con-
trol mechanism was implemented, with its key feature of fair bandwidth allo-
cation. The overall throughput of the TCP ranges from 40 Mbps (K = 1) to
78.5 Mbps (K = 10). The TCP-friendly DCCP congestion control mode CCID
3 (TFRC) also achieves good results, although (because of its worse, from the
TCP point of view, “reasonable” fairness) not as good as pure TCP congestion
control (CCID 2). If congestion increases, the gap between them closes slowly
62 R. R. Chodorek and A. Chodorek
6 Conclusions
The DCCP protocol works in different congestion control modes, two of which
(CCID 3 and CCID 4) are intended for multimedia. Although DCCP’s CCID 3
is recommended for transmission of large streaming media, such as videos, this
congestion control mode is modelled on the behaviour of the TCP protocol. Thus,
properties of the DCCP working in mode 3 are close to the TCP rather than
to the properties of typical real-time transport protocols, such as the UDP or
RTP/UDP protocol suite. The use of the linear throughput equation, proposed
by the Authors in their previous work, models the DCCP’s congestion control
on the behaviour of the RTP working on top of the UDP.
As was shown in the paper, the linear equation deals with two problematic
issues, which are the protocol’s equality towards competing flows and the result-
ing bandwidth constraints imposed by congestion control mechanism. Real-time
transmission is rate-sensitive and equality enforced at the level of the transport
protocol (instead of, for example, the sending application or codec) and signifi-
cantly and needlessly reduces the bit rate of the transmitted stream. Experiments
shows that our solution of light-weight congestion control for the DCCP, imple-
mented in the Linux kernel, allows the DCCP to send video data in a real-time
regime and kept the sending stream congestion controlled. Throughput of the
video steam was reduced by no more than 5.5% when competing with 10 TCP
flows, and the same reduction of throughput was observed for only 1 stream
transmitted by the DCCP working in standard CCID 3 mode. As a result, the
proposed mechanism is aggressive enough to compete for bandwidth with TCP
flows and not so aggressive as to cause the collapse of the competing TCP traffic.
References
1. Chodorek, A., Chodorek, R.R.: Streaming video over TFRC with linear throughput
equation. Adv. Electron. Telecommun. 1(2), 26–29 (2010)
2. Chodorek, R.R., Chodorek, A.: ECN-capable TCP-friendly layered multicast mul-
timedia delivery. In: Proceedings of UKSim 2009: 11th International Conference
on Computer Modelling and Simulation, 25–27 March 2009, Cambridge, England,
pp. 553–558 (2009)
3. Chodorek, R.R., Chodorek, A.: Expanding the Ns-2 emulation environment with
the use of flexible mapping. In: Gaj, P., Kwiecień, A., Stera, P. (eds.) CN 2016.
CCIS, vol. 608, pp. 22–31. Springer, Cham (2016). https://doi.org/10.1007/978-3-
319-39207-3 2
4. Fall, K., Vradhan, K.: The ns Manual (2014). http://www.isi.edu/nsnam/doc/ns
doc.pdf
5. Floyd, S., Kohler, E.: Profile for datagram congestion control protocol (DCCP)
congestion control ID 2: TCP-like congestion control. RFC 4341 (2006)
6. Floyd, S., Kohler, E., Padhye, J.: Profile for Datagram Congestion Control Protocol
(DCCP) Congestion Control ID 3: TCP-Friendly Rate Control (TFRC). RFC 4342
(2006)
7. Floyd, S., Handley, M., Widmer, J.: TCP Friendly Rate Control (TFRC): Protocol
Specification. IETF RFC 5348 (2008)
8. Floyd, S., Kohler, E.: Profile for datagram congestion control protocol (DCCP)
congestion ID 4: TCP-friendly rate control for small packets (TFRC-SP). RFC
5622 (2009)
9. Fujikawa, T., Takishima, Y., Ujikawa, H., Ogura, K., Katto, J., Izumikawa, H.:
A hybrid TCP-friendly rate control for multimedia streaming. In: Proceedings of
18th International Packet Video Workshop (PV), pp. 134–141 (2010)
10. Holmer, S., et al.: A Google Congestion Control Algorithm for Real-Time Com-
munication. Internet-Draft draft-alvestrand-rmcat-congestion-03 (2015)
11. iPerf - The TCP, UDP and SCTP network bandwidth measurement tool. https://
iperf.fr/. Accessed Mar 2018
12. Parameter values for the HDTV standards for production and international pro-
gramme exchange. Recommendation ITU-R BT.709-6 06/2015 (2015)
13. Kohler, E., Handley, M., Floyd, S.: Datagram Congestion Control Protocol
(DCCP). RFC 4340 (2006)
14. Mahrenholz, D., Svilen, I.: Real-time network emulation with ns-2. In: Proceedings
of the 8th IEEE International Symposium on Distributed Simulation and Real
Time Applications, Budapest, Hungary, pp. 29–36 (2004)
15. Mahrenholz, D., Ivanov, S.: Adjusting the ns-2 emulation mode to a live network.
In: Müller, P., Gotzhein, R., Schmitt, J.B. (eds.) Kommunikation in Verteilten
Systemen (KiVS). Informatik aktuell, pp. 205–217. Springer, Heidelberg (2005).
https://doi.org/10.1007/3-540-27301-8 17
16. Shiang, H.P., van der Schaar, M.: Quality-centric TCP-friendly congestion control
for multimedia transmission. IEEE Trans. Multimedia 14(3), 896–909 (2012)
17. Singhal, N., Sharma, R.M.: Survey on TCP friendly congestion control for unicast
and multicast traffic. Int. J. Comput. Appl. 26(1), 23–30 (2011)
18. Stevens, W., Allman, M., Paxson, S.: TCP congestion control. RFC 2581 (1999)
19. VQEG: VQEG HDTV TIA Source Test Sequences. ftp://vqeg.its.bldrdoc.gov/
HDTV/NTIA source/. Accessed Mar 2018
20. VideoLAN - Official page for VLC media player, the Open Source video framework!
http://www.videolan.org/vlc/. Accessed Mar 2018
On Improving Communication System
Performance in Some Virtual
Private Networks
Abstract. The paper presents the procedure for determining the opti-
mal set of hubs and spokes and thus the collection of tunnels in hub-
and-spoke network. The subject of the study was a multi-departmental
network, with security of transmission requirement, so DMVPN tech-
nology with IPSec-protected tunnels were used. The optimization of the
hub/spoke set was intended to improve inter-departmental communica-
tion efficiency, which was to be confirmed by the analysis of simulation
results. In the simulation studies, the quality of the chosen service (VoIP)
was checked for the different structures of tunnel connections. Simulation
tests were prepared and implemented in Riverbed Modeler environment.
1 Introduction
This task belongs to the wide domain of determining the optimal alloca-
tion of resources and determining the optimal communication structure and is
raised in many research works focused on improving reliability, performance,
and usability of transmission systems (multiprocessor systems, military com-
puter networks - wired and wireless networks of stationary or mobile nodes). A
lot of research focuses on the problems of optimization of the hypercube struc-
ture and on the problems with location and relocation of network resources
([2–8]). In the era of IoT (Internet of Things), results of research on optimal and
“energy-efficient” communication structures, prolonging the life time of the net-
work with battery-powered nodes, are particularly important [9]. The research is
focused on developing new routing protocols, efficient medium access protocols,
selecting of nodes collecting and processing information from other nodes (sink
nodes) and on indicating nodes of the meeting points (rendezvous points) or
nodes acting as coordinators ([9–12]).
In our area of interest, i.e. dynamic tunneling in VPNs, research is focused
on testing of the network performance in cases of utilization of various routing
protocols [13].
In this paper we introduce a procedure for determining the optimal set of hubs
and spokes in specific communication structure. We assume arbitrarily that the
dynamic routing protocol, used for broadcasting of prefixes of branch network
addresses, is OSPF (Open Shortest Path First). The result of the procedure
is the graph of logical VPN connections between departmental border routers.
Based on the graph we will be able to distinguish spoke and hub/spoke routers.
We assumed that such structure of VPN tunnels will enable efficient and secure
exchange of information between branches. We were looking for confirmation of
assumptions in the results of the simulation studies.
This paper firstly presents short description and basic DMVPN problems.
In Sect. 3, the structure of the analyzed network, the assumptions and formal
description of the problem are given. Section 3 also deals with the procedure
for determining the best tunneling structure between the border routers of our
network. The last section shows the model of simulated network and results of
simulation tests.
Fig. 1. DMVP with one HUB (a) and backup NHS server (b)
For reliability DMVPN can contain primary and backup hub (structure b on
Fig. 1). Regardless of DMVPN structure, each spoke has to register itself in the
primary hub or additionally in backup hub, which are called Next Hop Servers
(NHS).
DMVPN technology has many advantages, but in various studies the short-
comings and problems that occur in networks with this solution are signaled. For
example, for spoke-to-spoke communication (DMVPN Phase-3) a hub failure can
directly impact spoke-to-spoke connectivity in those DMVPN networks where
spokes can’t establish direct IPSec sessions (due to NAT or other limitations).
Another example might be the problem discussed in the article [1]. The
authors point out the fact, that the primary condition of successful tunneling is
proper functioning of the spoke in hub registration mechanism, the polling mech-
anism about physical addresses of the final points of tunnels, but also mechanism
of call’s disconnecting in case of hub failure (connection with hub can be tem-
porary loss, hub can be overloaded, hub’s response time can be too long, etc.).
In some cases of tunnel connections protected by IPSec, it is necessary to track
hub’s availability and to remove IPSec session after a period of temporary hub’s
unavailability (cleaning of IPSec Security Associations) [1].
Despite the fact that DMVPN technology is developed and improved over the
years, it is still possible to indicate the situations in which network management
procedures in situations of malfunction are useful.
On Improving Communication System 67
Our considerations will be focused on the VPN and the network structure graph
G1 , shown in the Fig. 2.
jitter, delay, and packet loss. IP SLA has two components: the source and the
target. The source generates packets, and the target functions as responder.
Simple IP SLA probe may look as follows:
ip sla 1
udp-jitter 10.0.0.1 codec g729a
frequency 40
ip sla schedule 5 life forever start-time now
On the recipient’s side, we just turn on the responder using the command:
ip sla responder
Statistics given by the probe is listed below (some lines are omitted).
WA#show ip sla statistics
Latest RTT: 192 milliseconds
Source to Destination Latency Min/Avg/Max: 2/75/244 milliseconds
Destination to Source Latency Min/Avg/Max: 2/214/423 milliseconds
Source to Destination Jitter Min/Avg/Max: 0/13/209 milliseconds
Destination to Source Jitter Min/Avg/Max: 0/23/314 milliseconds
Packet Loss Values:
Loss Source to Destination: 0
Loss Destination to Source: 0
Out Of Sequence: 0 Tail Drop: 19
Packet Late Arrival: 0 Packet Skipped: 1
Voice Score Values:
Calculated Planning Impairment Factor (ICPIF): 14
MOS score: 4.00
We assume that the probes will be running on border routers, that can set up
tunnels as in Fig. 2. The probes will assess the “quality of the tunnel connection”.
This parameter will be the key to determining the best communication structure
of our network.
Because it is communication structure with permanent tunnels (DMVPN
Phase-1), our intent is to choose “optimal minimum set” of hubs and spokes (in
our case, providing the best VoIP service performance).
In general, let d (e, e |G ) be the distance between nodes e and e in a coherent
graph G. This is the length of the shortest chain (in the graph G) connecting
node e with the node e .
max
Nodes of the structure G are characterized by a radius. Let r (e |G ) =e ∈E(G)
d ((e, e ) |G ) be the radius of a node. In the Table 1 radius for all nodes of G1
were presented.
A basis for determining the communication structure is a dendrite, which
provides the minimum number of communication lines.
Let T = <E, U ∗ > be the dendrite i.e. such coherent acyclic partial graph of
G that:
∃ e , e ∈ U ⇒ e , e ∈ U ∗ ⇔ [(d (e∗ , e ) = d (e∗ , e )) ∧ d (e , e ) = 1]
On Improving Communication System 69
e ∈ E (G1 ) r (e |G1 )
e0 3
e1 2
e2 4
e3 3
e4 3
e5 4
e6 3
e7 4
e8 4
for
r (e∗ ) =e∈E(G) r (e)
max
The algorithm for dendrite T determining was presented in [7]. The procedure
described there gives, in the first step, a set of dendrites, illustrated in the Fig. 5.
For simplicity of calculation, it was assumed that distance between e and e ,
which are connected via VPN tunnel, is 1, but you can use all or some of the
characteristics returned by the IP SLA probes and assign a metric according to
your preferences. In a real network environment, we assume continuous (periodic)
checking of various SLA parameters, and using them as a metric of inter-nodes
tunnels.
The optimal structure is a dendrite determined for a node with minimal
radius. For the structure G1 the node e1 (Table 1) has a minimal radius. The
structure TOP T , shown in Fig. 3, was chosen as the optimal communication struc-
ture for the G1 . Thus, the nodes e2 , e5 , e6 , e7 , e8 are spokes, and the nodes
e0 , e1 , e3 , e4 are hubs.
After determining the optimal communication structure, the management
station can perform appropriate reconfiguration of the boundary routers.
There were nine branches attached to the WAN by border routers R0 – R8.
The single branch was modeled as a LAN with 10 workstations and one http
server. Branch workstations can communicate through WAN over VoIP and http
(treated as background traffic). The observed service, as especially important for
us, was VoIP.
The conducted simulation tests certainly do not serve to verify the design
of any network. The tests were to authenticate the procedure for determining
the optimal VPN communication structure. Therefore, we only took care of
the homogeneity of links and network devices. What was important for us is
that in the randomness of generating network streams and the randomness of
client-server connections, the simulation results confirm the correctness of the
theoretical arguments.
We were interested in the value of important VoIP service parameters like
end-to-end delay and delay variation Network services have used the standard
application models, available at Riverbed Modeler (“Heavy Browsing” http
model and “PCM Quality Speech” voice model). Routers were connected to
WAN over T1 links.
Simulation scenarios corresponded to the structures from Fig. 5. It was
expected that the results of the simulations will confirm the choice of optimal
hubs, spokes and tunnels collections (Fig. 2). Some interesting results Voice
On Improving Communication System 71
End-to-End Delay and Voice Delay Variation, confirming the correctness of the
procedure for determining the optimal VPN structure are shown in the figures
below. End-to-End Delay is “average delay in seconds for all network nodes
communicating each other under VoIP” and Voice Delay Variation is “average
variance in seconds (for all voice workstations) among end to end delays for voice
packets. It is measured from the time packet is created to the time it is received”
[14]. Low values of these parameters are desirable.
Complete set of results, in the form of a bar chart, for all G1 ’s dendrites are
presented in Fig. 6. The highlighted bar refers to the best structure t (e1 ) (TOP T
from Fig. 3).
References
1. Malinowski, T., Arciuch, A.: The procedure for monitoring and maintaining a
network of distributed resources. In: Annals of Computer Science and Information
Systems, Proceedings of the 2014 Federated Conference on Computer Science and
Information Systems, vol. 2, 7–10 September 2014, Warsaw, Poland (2014)
2. AlBdaiwia, B.F., Bose, B.: On resource placements in 3D tori. J. Parallel Distrib.
Comput. 63, 838–845 (2003)
3. AlBdaiwia, B.F., Bose, B.: Quasi-perfect resource placements for two-dimensional
toroidal networks. J. Parallel Distrib. Comput. 65, 815–831 (2005)
4. Bae, M.M., Bose, B.: Resource placement in torus-based networks. IEEE Trans.
Comput. 46(10), 1083–1092 (1997)
5. Imani, N., Sarbazi-Azad, H., Zomaya, A.Y.: Resource placement in Cartesian prod-
uct of networks. J. Parallel Distrib. Comput. 70, 481–495 (2010)
6. Moinzadeh, P., Sarbazi-Azad, H., Yazdani, N.: Resource placement in cube-
connected cycles. In: The International Symposium on Parallel Architectures, Algo-
rithms, and Networks, pp. 83–89. IEEE Computer Society (2008)
7. Chudzikiewicz, J., Zieliński, Z.: On some resources placement schemes in the
4-dimensional soft degradable hypercube processors network. In: Zamojski, W.,
Mazurkiewicz, J., Sugier, J., Walkowiak, T., Kacprzyk, J. (eds.) Proceedings of the
Ninth International Conference on Dependability and Complex Systems DepCoS-
RELCOMEX. June 30 – July 4, 2014, Brunów, Poland. AISC, vol. 286, pp. 133–
143. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07013-1 13
8. Chudzikiewicz, J., Malinowski, T., Zieliński, Z.: The method for optimal server
placement in the hypercube networks. In: Proceedings of the 2015 Federated Con-
ference on Computer Science and Information Systems. ACSIS, vol. 2, pp. 947–954
(2015). https://doi.org/10.15439/2014F159
9. Brindha, L., Muthaiah, U.: Energy efficient mobile sink path selection using a
cluster based approach in WSNs. Int. J. Innovative Res. Comput. Commun. Eng.
3(3) (2015)
On Improving Communication System 73
10. Erzin, A.I., Plotnikov, R.V.: Using VNS for the optimal synthesis of the commu-
nication tree in wireless sensor networks. In: Electronic Notes in Discrete Mathe-
matics, vol. 47. Elsevier (2015)
11. Ghotra, A., Soni, N.: Performance evaluation of ant colony optimization based
rendezvous leach using for mobile sink based WSNs. Int. J. Eng. Res. Dev. 11(07)
(2015)
12. Baby, S., Soman, M.: Rendezvous based techniques for energy conservation in
wireless sensor networks - a survey. J. Netw. Commun. Emerg. Technol. (JNCET),
3(3) (2015)
13. Bahnasee, A., Kamoun, N.E.: Study and analysis of a dynamic routing protocols’
scalability over a dynamic multi-point virtual private network. Int. J. Comput.
Appl. (0975-8887), 123(2) (2015)
14. Sethi, A.S., Hnatyshin, V.Y.: The Practical OPNET User Guide for Computer
Network Simulation. Chapman and Hall/CRC (2012)
New SDN-Oriented Authentication
and Access Control Mechanism
1 Introduction
network’s services are abstracted into a separate plane (Application Plane, AP).
In SDN, the centralized controller (representing the network’s operating system),
the switches (network resources) and the applications (network consumers) can
communicate in real-time [3] through the NorthBound Interface (NBI) and the
SouthBound Interface (SBI). The Application Plane utilizes the NBI, which is
a programmable API, to communicate with the Controller. Typically, there are
no standard Northbound Interfaces defined, and the applications should provide
their own APIs. The Controller uses the Southbound Interface (e.g. OpenFlow)
to communicate with the underlying Data Plane. OpenFlow is a standard pro-
tocol (standardized by the Open Networking Foundation (ONF) [4]), widely
used for the Southbound interface in SDN Networks [5]. It is typically used for
the communication between the Controller and the switches under its control.
OpenFlow can provide encrypted communications between the Controller and
the underlying infrastructure, using Transport Layer Security (TLS), which is
considered as an optional feature, and unprotected communications using clear
Transmission Control Protocol (TCP).
The steps of the authentication procedure are the following. The Supplicant
initiates the communication when it detects a change of the link state from down
to up, while the port remains in the unauthorized mode during the authentica-
tion process. The Authenticator sends EAP-Request/Identity frame to the Sup-
plicant, asking for its identity or the credentials. Once the Supplicant receives
the request, it responds with the EAP-Response/Identity frame containing the
credentials. Now, the Authenticator begins its role as a proxy between the Sup-
plicant and the Authentication Server; it passes the EAP frames between them
New SDN-Oriented Authentication and Access Control Mechanism 79
Meeting the need of protecting the SDN networks, recently different dedicated
security solutions have been presented, for instance, IDS [13], IPS [14], State-
less Firewall [15], Stateful Firewall [16], reactive Firewall [17], and Distributed
Firewall [18]. In this section, we give an overview of several known Network
Access Control Systems for SDN networks and then compare them with our
proposed solution. Thus, the Ethan project [19] relies on defining a global pol-
icy for the centralized controller architecture and a strong binding between the
users’ attributes, their machines and their traffic (IP, MAC, and Ports) to pro-
vide network access control system based on user’s identity. Ethane argues that
all users, hosts, and switches must be registered and authenticated before any
communication. The hosts are authenticated by their registered MAC addresses,
the users are authenticated by presenting their usernames and passwords to a
website end of the Kerberos server, and the switches use certificates to authen-
ticate themselves to the controller through an SSL secure channel. Resonance
[20] extends the Ethane to allow the dynamic network policy based on the real-
time monitoring. In Resonance, each device connected to switch has, both, the
“Security Class” that transcribes, how the traffic flows to the resources, and the
“State”, that determines which Security Class should be applied at that time.
Like in Ethan, the user is redirected to a website to submit his credentials to
be authenticated. The solutions presented in [21,22], AuthFlow [23], FlowNAC
[24], and FlowIdentity [25] attempt to provide authentication and access control
systems for SDN networks using IEEE 802.1x with the RADIUS Authentication
Server, but they differ, basically, with how the host/end user is authenticated,
and with how the RADIUS Client is used as the Authenticator. The authors in
[21,22] have proposed a Network Access Control System for an OpenFlow-based
SDN network, which is compatible with the traditional network infrastructure.
In this solution, newly connected hosts are directed to the authentication web-
site with an integrated RADIUS Client to provide their credentials. The website
is ending to RADIUS Authentication Server. Similarly to Ethane [19], their way
of host authentication is based on tight binding the host to the port on the
switch. However, the captive portal is the common background in these propos-
als; it requires Layer 3 configuration (e.g. DHCP) or even ephemeral private IP
address to access the website. Moreover, these approaches require an HTTPS-
capable Web browser installed in the host to be able to authenticate, which is
a problem for virtual machines or some network devices, like printers, scanners,
phones, or even some servers that do not support the web browser. In contrast,
our proposed solution does not utilize a website; instead, it uses a hostapd [26] as
80 F. Nife and Z. Kotulski
Authenticator and adopts the standard 802.1x that does not need an IP address
assignment before the authentication process. AuthFlow [23] authenticates hosts
directly at Layer 2 (based on MAC addresses), then it provides different privi-
leges for users, based on their credentials. AuthFlow extends the RADIUS Client
authenticator hostapd to communicate with the controller through an SSL-based
secure channel. AuthFlow differs with our proposed system; it only provides
the Access Control system for SDN networks, while our solution provides the
Access Control system and introduces a mechanism for the stateless property
limitation of RADIUS protocol, by enforcing the Authenticator to maintain a
local database of the authenticated active users. FlowNAC [24] proposes a Flow-
Based Network Access Control for SDN networks, in which the flows are associ-
ated to services; the services are uniquely identified, and the decisions are based
on, both, the user’s identity and the requested services. FlowNAC enforces the
extended centralized policy (e.g., target service identifier) to be implemented
in a proactive manner. FlowNAC implement IEEE 802.1x standard, however,
to provide the user with the ability to access multiple services simultaneously,
the EAPoL in EAPoL encapsulation has been introduced, which in turn needs
the extension and updating the protocols, entities’ exchanged information, and
data models. FlowIdentity [25] present an SDN authentication solution using
IEEE 802.1x standard with authorization (policy enforcement) through a role-
based firewall. This proposal does not change the traditional 802.1x port-based
authentication; however, the defined policy can be dynamically updated and
directly enforced. Both, FlowNAC and FlowIdentity, argue to provide a service-
based authentication, which differs only in the way that the policy enforcement
is achieved. FlowNAC and FlowIdentity are differing from our solution; they are
implementing the service-based authentication. FlowIdentity differentiates the
service using the role-based firewall, while FlowNAC employs EAPoL in EAPoL
encapsulation and utilizes the predefined rules as a set of rules per service. In con-
trast, our proposed solution is the identity-based authentication, it does not need
any additional supporting protocols or does not require new encapsulation, which
might lead to additional unrequired overhead. In the paper [27], the authors have
suggested SEaaS (Security as a Service) model, which provides mutual authen-
tication mechanism between an application and the controller in SDN networks.
It provides an additional security service for Southbound SDN API (i.e. REST
API), which is not supported by an existing protocol. SEaaS is focused on pro-
viding the authentication between the controller and the applications that run
above it, while our proposed work is identity-based authentication between the
controller and client/users who try to access the network. The authors of [28]
have implemented an authentication and authorization module, which is a net-
work application maintaining a wide-session database. It has been implemented
with two different modes: pass-throw mode and authentication server mode. The
main difference between this solution and our proposed work is the place where
the Authenticator is located. In [28] the Authenticator has been integrated with
the Controller, which may lead to increase the load on the controller and make
the solution vulnerable to attacks on the controller, like SYN flooding, which
New SDN-Oriented Authentication and Access Control Mechanism 81
4 System Architecture
4.1 Architecture Overview
The main objective of this work is to design and develop a network access control
and authorization mechanism for an SDN network. The proposed architecture’s
overview is shown in Fig. 4, in which the 802.1x standard is adopted for SDN
networks, as it does not enforce any changes on the host sides. The architecture
is composed of four components, which are: the OpenFlow-enabled switches,
the Controller, the Authenticator, and the Authentication Server. The policy is
enforced in a reactive mode (based on the first packet), what keeps the data plane
flow table small, instead of filling it with unmatched rules. However, only two
entries should be installed in advance in the switch’s flow table, to enforce the
switch forwarding all EAPOL (Ethernet type set to 0x88E) to the Authenticator,
while dropping all other packets. The Centralized Authenticator is the modified
version of the hostapd. It is separated from the controller for security reasons
(to isolate the controller for protecting the network from presumably the most
extreme threats on SDN networks, where such vulnerabilities and attacks on the
Controller will lead to compromise the whole network, see [29,30]). The Authen-
ticator is implemented as a RADIUS Client. It receives the EAPOL frames from
the switches, decapsulates the EAP frame, compares its contents with a local
database of currently active users and, in case of no match, re-encapsulates it
in the RADIUS frame and forwards it to the RADIUS Authentication Server.
The reply from the Authentication Server, whether it succeeds or fails, is for-
warded to the controller via a secure encrypted channel using SSL 3.0 standard
established between the Controller and the Authenticator. The Authentication
Server (RADIUS) basically performs the actual authentication process by vali-
dating the identity of the Client and notifying the Authenticator if the Client is
authorized to access the network or not.
the Supplicant and the Authenticator starts either when the Supplicant is
sending EAPOL-Start frame to the edge switch, or when the Authenticator
detects state changes in one of its ports and, alternatively, when it receives a
packet on a specific port, with a source MAC address not included in its flow
table, see Fig. 5. The switch is proactively instructed to forward EAPOL-start
frames to the Centralized Authenticator. The Authenticator responds with EAP-
Request/Identity, asking for the Supplicant credentials. The Supplicant answers
with EAP-Response/Identity packet providing its credentials (user name that
uniquely defines this request for the Client). Then, the Authenticator decapsu-
lates the message and compares its contents against a local database of currently
active users. In case the match occurs, the Authenticator informs the Controller
application. Otherwise, it will encapsulate the message and will forward it to
the Authentication Server. The Authentication Server responds with RADIUS
Access/Challenge to be forwarded to the Supplicant. After that, the Suppli-
cant provides its identifying credentials using EAP-Response/Identity. Then the
RADIUS server verifies the received credentials and transmits either an EAP-
Success (Access-Accept) Packet, if the Client is successfully authenticated and
authorized to gain access to the network, or EAP-Reject (Access-Accept) packet
what means the access is denied and the port is kept blocked. The Authenti-
cator will update its active-user database and will forward the final decision to
the Controller, which accordingly may install new entry on the corresponding
switch’s flow table and apply the predefined policy group for that Client.
can access what” in the network. This procedure concerns users, devices, and
network services. So, when the Supplicant is correctly authenticated, the Authen-
tication Server returns an EAP-Success (Access-Accept) Packet, which includes
a list of attribute-value pairs (user privileges) that describes the parameters to
be used for the current session. Then, the modified hostapd authenticator for-
wards these messages to the application running on the top of the Controller to
inform about the success of authentication and the identity of the Supplicant
(its MAC address). Such parameters may include: the service type, the protocol
type, the access list to apply, or just the static route to be installed in the Open-
Flow table. Finally, the application running over the Controller translates these
parameter into flow rules to be installed in the responsible switch and applied
on the corresponding port. In such a way, the switch can easily find correlation
between the Supplicant and its flow.
4.4 Database
A Centralized Database with dynamic capacity is maintained to provide means
for fine-grained network access control system and to keep states of currently
authenticated active users, which leads to limiting the concurrent sessions for each
authenticated user. This Database is located at the Authenticator side and is used
to store information about all currently active users. For each successfully authen-
ticated user, a new entry is added. This Database should be searched first for
every authentication request before fetching information from the Authentication
Server. The port-down event messages sent from the switch to the Controller are
a good sign to remove the corresponding entry from the Database.
84 F. Nife and Z. Kotulski
The Network Access Control solution, proposed in Sect. 4, has been validated
at the functional level. A proof-of-concept solution has been implemented and
several experiments have been designed and performed. In Fig. 6 we present
a draft view of the validation environment that has been used to prove the
functional viability of our proposal. We have built up our testbed that includes
the following virtual machines:
5.2 Validation
To test the correct behavior of our proposed solution and, next, to estimate
its effectiveness, different test and experiment scenarios have been designed and
(partially) implemented. The first test is to show the efficiency of allowing the
authenticated user’s traffic while dropping an unauthorized traffic. For this test,
Client-1 is correctly authenticated and therefore the Controller installs entries in
the switch’s OpenFlow table, which explicitly reflect the client’s privileges. So,
Client-1 can access the network resources, while the other host, Client-2, is an
unauthorized host, so its access request is rejected and no its OpenFlow entries
installed, so the switch refuses all its attempts to access the network resources.
The second experiment is to show “who can access what” in the network. The
simple match-action paradigm offered by the OpenFlow protocol can give a great
New SDN-Oriented Authentication and Access Control Mechanism 85
utility of traffic control by giving an ability to filter packets, based on the proto-
col, source and/or destination IP addresses, and source and/or destination port
numbers. For instance, it blocks an address from the accessing HTTP session of
a specific server, while it allows its other services. In fact, using TCP and UDP
ports makes it possible to support or suppress higher level applications. Gener-
ally, the port numbers are associated with applications, so allowing or denying
the access to a specific port number determines, which application can be used,
and which devices can access the port. This allows setting up the network to
carry only certain types of traffic, for instance, the FTP (File Transfer Protocol)
packets or POP3 mail. In this test, the authenticated Client-1 is allowed to start
an HTTP Sessions, while it is forbidden to access Telnet sessions. So, some of the
entries installed are allowed any request to TCP port (80/8080) and are denied
any request to TCP port equal to 23. The last experiment designed is to validate
the solution for the stateless property of RADIUS by testing the Authenticator
database with two scenarios. In the first scenario, we unlimited the ability to use
the same user’s credentials, in which, both, Client-1 and Client-2 successfully
authenticate themselves using the same credentials. Then (the second scenario),
we limit such a possibility to only one session at a time. Therefore, only the first
authentication request can be verified successfully. The above tests have been
implemented and they confirmed correctness of the protocol, as the protocol
worked according to the proposed scenarios. Now, all these tests must be exten-
sively carried out with different environmental constraints to estimate practical
performance of the protocol and its resistance to external disturbance. After
presentation and discussion of our solution, let us summarize security functions
86 F. Nife and Z. Kotulski
Table 1. Comparison of the proposed approach with other SDN-based Access Control
solutions
In this paper, we have intended to introduce a new authentication and access con-
trol mechanism for OpenFlow-based SDN networks, by adopting the 802.1x stan-
dard. The proposed solution provides authentication and authorization mecha-
nisms for SDN networks in such a way, that it neither enforces changes to the
SDN paradigm in term of the network’s design or behavior, nor it requires any
support of new supplementary protocols or even it needs no additional configu-
ration of hosts and routers. Another advantage of our solution is that it intends
to overcome the stateless property of the 802.1x protocol by maintaining a cen-
tralized active-user database for the fine-grained network access control system,
which keeps records of currently authenticated users and which limits the concur-
rent sessions. In this solution, the security policy is centralized and dynamically
enforced to the switches. We have chosen to implement the proposed solution
with a reactive mode, to gain an advantage of keeping the data plane’s flow tables
small. For the future enhancements, we reclaim to implement, both, reactive and
proactive modes to improve the overall system’s performance. We also plan to
deploy our prototype in a real network environment to confirm its functionality
and its strength against active attackers.
New SDN-Oriented Authentication and Access Control Mechanism 87
References
1. Pujolle, G.: Software Networks Virtualization, SDN, 5G and Security. ISTE Ltd.
and Wiley, London and New York (2015)
2. Kreutz, D., Ramos, F.M.V., Verissimo, P.E., Rothenberg, C.E., Azodolmolky, S.,
Uhlig, S.: Software-defined networking: a comprehensive survey. Proc. IEEE 103,
14–76 (2015)
3. Astuto, B.N., Mendonca, M., Nguyen, X.N., Obraczka, K., Turletti, T.: A survey of
software-defined networking: past, present, and future of programmable networks.
IEEE Comm. Surv. Tutor. 16, 1617–1634 (2014)
4. The Open Networking Foundation, OpenFlow Switch Specification (2015).
https://www.opennetworking.org/wp-content/uploads/2014/10/openflow-switch-
v1.5.1.pdf
5. Hu, F., Hao, Q., Bao, K.: A survey on software-defined network and OpenFlow:
from concept to implementation. IEEE Commun. Surv. Tutor. 16(4), 2181–2206
(2014)
6. Lara, A., Kolasani, A., Ramamurthy, B.: Network innovation using OpenFlow: a
survey. IEEE Comm. Surv. Tutor. 16, 493–512 (2014)
7. Ahmad, I., Namal, S., Ylianttila, M., Gurtov, A.: Security in software defined
networks: a survey. IEEE Commun. Surv. Tutor. 17(4), 2317–2346 (2015)
8. Alsmadi, I., Xu, D.: Security of software defined networks: a survey. Comput. Secur.
53, 79–108 (2015)
9. Local and Metropolitan Area Networks’ Port-Based Network Access Control, IEEE
Standard 802.1x (2010)
10. Aboba, B., Blunk, L., Vollbrecht, J., Carlson, J., Levkowetz, H.: Extensible Authen-
tication Protocol (EAP), RFC 3748 (Proposed Standard) (2004). http://www.ietf.
org/rfc/rfc3748.txt
11. Rigney, C., Willens, S., Rubens, A., Simpson, W.: Remote Authentication Dial In
User Service (RADIUS), RFC 2865 (Draft Standard) (2000). http://www.ietf.org/
rfc/rfc2865.txt
12. Fajardo, V., Arkko, J., Loughney, J., Zorn, G.: Diameter Base Protocol, RFC 6733
(Proposed Standard) (2012). http://www.ietf.org/rfc/rfc6733.txt
13. Jeong, C., Ha, T., Narantuya, J., Lim, H., Kim, J.: scalable network intrusion
detection on virtual SDN environment. In: 2014 IEEE 3rd International Conference
on Cloud Networking (CloudNet), pp. 264–265, Luxembourg (2014)
14. Francois, J., Aib, I., Boutaba, R.: Firecol: a collaborative protection network for the
detection of flooding DDoS attacks. IEEE/ACM Trans. Netw. (TON) 20, 1828–
1841 (2012)
15. Yoon, C., Park, T., Lee, S., Kang, H., Shin, S., Zhang, Z.: Enabling security func-
tions with SDN: a feasibility study. Comput. Netw. 85(1389–1286), 19–35 (2015)
16. Nife, F., Kotulski, Z.: Multi-level stateful firewall mechanism for software defined
networks. In: Gaj, P., Kwiecień, A., Sawicki, M. (eds.) CN 2017. CCIS, vol. 718,
pp. 271–286. Springer, Cham (2017)
17. Zerkane, S., Espes, D., Le Parc, P., Cuppens, F.: Software defined networking
reactive stateful firewall. In: Hoepman, J.-H., Katzenbeisser, S. (eds.) SEC 2016.
IAICT, vol. 471, pp. 119–132. Springer, Cham (2016). https://doi.org/10.1007/
978-3-319-33630-5 9
18. Pena, J.G., Yu, W.E.: Development of a distributed firewall using software defined
networking technology. In: 4th IEEE International Conference on Information Sci-
ence and Technology, pp. 449–452, Shenzhen, China (2014)
88 F. Nife and Z. Kotulski
19. Casado, M., Freedman, M.J., Pettit, J., Luo, J., McKeown, N., Shenker, S.: Ethane:
taking control of the enterprise. In: ACM SIGCOMM, Kyoto, Japan, pp. 1–12
(2007)
20. Nayak, A., Reimers, A., Feamster, N., Clark, R.: Resonance: dynamic access con-
trol for enterprise networks. In: Workshop: Research on Enterprise Networking
(WREN), Barcelona, Spain (2009)
21. Dangovas, V., Kuliesius, F.: SDN-driven authentication and access control sys-
tem. In: The International Conference on Digital Information, Networking, and
Wireless Communications (DINWC). Society of Digital Information and Wireless
Communication, pp. 20–23 (2014)
22. Kuliesius, F., Dangovas, V.: SDN enhanced campus network authentication and
access control system. In: 2016 Eighth International Conference on Ubiquitous and
Future Networks (ICUFN), pp. 894–899 (2016)
23. Mattos, D.M.F., Ferraz, L.H.G., Duarte, O.C.M.B.: AuthFlow: authentication and
access control mechanism for software defined networking. Ann. Telecommun.
71(11), 607–615 (2016). https://doi.org/10.1007/s12243-016-0505-z. ISSN 0003–
4347
24. Matias, J., Garay, J., Mendiola, A., Toledo, N., Jacob, E.: FlowNAC: flow-based
network access control. In: Third European Workshop on Software-Defined Net-
works (EWSDN), Budapest, Hungary, pp. 79–84 (2014)
25. Yakasai, S.T., Guy, C.G.: Flowidentity: software-defined network access control.
In: IEEE Conference on Network Function Virtualization and Software Defined
Network, pp. 115–120 (2015)
26. Malinen, J.: Hostapd: IEEE 802.11 AP, IEEE 802.1x/WPA/WPA2/EAP/RADIUS
Authenticator. https://w1.fi/hostapd/
27. Green, K., Junghyun, A., Keecheon, K.: A study on authentication mechanism in
SEaaS for SDN. In: IMCOM 2017, Beppu, Japan (2017)
28. Hauser, F., Schmidt, M., Menth, M.: Establishing a session database for SDN using
802.1x and multiple authentication resources. In: IEEE ICC 2017 SAC Symposium
SDN & NFV Track, pp. 1–7 (2017)
29. Heller, B. Sherwood, R., McKeown, N.: The controller placement problem. In:
First Workshop on Hot Topics in Software Defined Networks, ser. HotSDN 2012,
pp. 7–12. ACM, New York (2012)
30. Kreutz, D., Ramos, F.M., Verissimo, P.: Towards secure and dependable software-
defined networks. In: Second ACM SIGCOMM Workshop on Hot Topics in Soft-
ware Defined Networking, ser. HotSDN 2013, pp. 55–60. ACM, New York (2013)
31. FreeRADIUS, FreeRADIUS project. https:freeradius.org/
32. POX Controller, POX wiki. https://openflow.stanford.edu/display/ONL/POX+
Wiki
33. Mininet: An Instant Virtual Network on your Laptop (or another PC). http://
mininet.org
34. O.vSwitch, Open vSwitch - Production Quality, Multilayer Open Virtual Switch.
http://openvswitch.org/
Full Network Coverage Monitoring
Solutions – The netBaltic System Case
1 Introduction
Network monitoring is a term used to describe [1] systematic, continuous con-
trol the behavior of the network and all elements included in this network. The
process of monitoring network consists of five logical parts [2]: data collection,
data representation, reporting, data analysis and presentation of the results. Net-
work monitoring is the key process in the implementation of network manage-
ment tasks and supports, among other things like network functioning analysis,
problem and defects identification and the correctness of network configuration
changes verification.
By collecting data more frequently and gathering more and more various
types of data, more problems can be identified, but it also increases the network
load. This problem becomes more significant with the increasing bandwidth con-
sumption, rising IPv6 protocol popularity and the popularity of the Internet in
general [2] due to network traffic growth – and the volume of measurement
data grows with it. New system solutions for network monitoring should evolve
towards better scalability and performance provision [3], and this is why orga-
nizations are still developing better network monitoring systems.
One way to reduce both the consumption of network bandwidth and computa-
tional overhead in management stations (centers) is to increase the intelligence in
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 89–102, 2018.
https://doi.org/10.1007/978-3-319-92459-5_8
90 D. Karpowicz et al.
devices, which gather monitoring data [4–6]. The first concept is to do some pre-
liminary analysis just in the data collecting devices. In this way these devices send
the partially analyzed data to management stations, instead of the entire set of
monitoring information. The increased intelligence refers also to replacing peri-
odical information sending with reporting performed only upon predefined events
occurrence [2].
Along with the mentioned device intelligence increase, changes in the way
of collected data reporting are also being proposed. An example of such a solu-
tion is the method of Intrinsic monitoring [7–9]. Its major feature is that it
can significantly reduce the generated network traffic [7]. The principle of this
method involves the use of an additional IPv6 header and the transfer function-
ality to decide about sending measurement data to network devices. Their task
is to make autonomous decisions in order to send the measurement data, e.g.
through the use of existing traffic (packets) in the network.
Section 2 describes the character of network monitoring, which is carried out
within the framework of netBaltic project [10,11]. The essence of this network
is that wireless links with a relatively low bit rates and high error rate are the
only available. Section 3 contains a description of analyzed solutions about how
to transport the collected monitoring data. In this section also the EHBMPvU
and EHBMPvF methods are presented. Section 4 is devoted to the comparison
of the developed methods and the classic solution to transport monitoring data.
Finally, Sect. 5 presents the results of the analysis along with the indicators when
and in what conditions should the particular method of reporting be used.
Fig. 1. The data structure placed in a package by the monitored node. In parentheses
is the length of the data fields in bits.
– TimeStamp – this field contains the time of transmitted data. Using a 32-bit
the information about the year (12 bits), month (4 bits), day (5 bits), hour
(5 bits) and minutes (6 bits) can be stored;
– Fragment Length – length in bytes of Data field (16 bits);
– Fragment ID – this is a field informing that the Data field carries only part
of the whole monitoring information. The value identifies the number of the
fragment. The value of 0 indicates that the data placed in the structure is not
fragmented (16 bits)
– Data – contains the collected data from a single node.
Along path traversal each such structure is added, successively one after another,
reflecting the order of nodes along the path specified in the header.
Full Network Coverage Monitoring Solutions – The netBaltic System Case 93
where:
P – the required number of monitoring packets,
x – total number of nodes to be monitored (value representing the size of the
routing table TBRP at the root of the tree),
w – the maximum size of payload data in the application layer of a single data-
gram in bytes,
z – the size of data collected from each node in bytes (the size should be shared
by all the nodes).
Collecting data from the nodes in the network using the EHBMPvU monitoring
method involves the use of existing users’ packets as the mean of transport. The
packet have to be addressed to the monitoring center’s IP address. One packet
allows to collect data from a certain number of nodes, depending on the size of
the data itself and available application layer payload space.
The rate of sending data depends on the frequency of nodes’ applications
communication. Monitoring is initiated by each node independently. The princi-
ple of operation in monitoring EHBMPvU is based on an additional new header,
named Monitoring Header, which aims to transport the data required for moni-
toring.
Adding data to the package is possible if and only of the three conditions
are met:
– packet must have a valid recipient. To reach the target data, it can only be
added to a packet, which will meet on its path the monitoring center node;
– the packet have enough space to add an additional header structure either
with the data or the data itself, if the header has been added by some previous
node along route;
– there must be the need to send monitoring data.
Monitoring Header and method of its placement in the packet is shown in Fig. 2.
The proposed Monitoring Header, which is shown in Fig. 2 has the four fol-
lowing fields:
– Next Header – identifies the next header following just after the Monitoring
Header. This field allows for compliance with the mechanism of the additional
headers in IPv6 (8 bits);
– Segments Count – determines the number of nodes, which added data to the
Monitoring Header. When adding data, increase this value (8 bits);
Full Network Coverage Monitoring Solutions – The netBaltic System Case 95
– Reserved – field that was introduced to take into account possible future
modifications to this header. Currently it is being skipped during processing
(16 bits);
– Payload – field in which structure are added – contain data added by the
node, including monitoring data.
Figure 3 shows the data structure which is placed in the Monitoring Header.
Each new structure is included consecutively one by one.
Fig. 3. The structure of the data placed in the Monitoring Header by the node. In
parentheses is the length of the data fields in bits.
The use of just TCP segments ensures that the transfer of packet between
the nodes will be reliable. Finally, the packet reaches the target and monitoring
center receives monitoring data from at least one node. Using the rule of deduc-
tion, it may be concluded that if each node in the network behaves as described
above, full network coverage can be achieved. The worst case scenario requires
using the number of application packets equal to the number of nodes in the
network. The necessary number of packets can be specified as follows:
P ≤x (2)
where:
P – required number of monitoring packets,
x – the number of nodes in the network.
In order to determine the efficiency of two proposed methods for the netBaltic
system, the simulations was performed by using the devoted simulator [14] and
the results were compared to the typical monitoring use case – namely the SNMP
protocol. The latter was assumed to work in the send request and wait for
response mode of operation. Scalability, security and the overhead were taken
under consideration in the evaluation.
Fig. 4. Comparing the amount of data generated by the methods EHBMPvF, EHBM-
PvU and SNMP (classic method).
Full Network Coverage Monitoring Solutions – The netBaltic System Case 97
The experiment was performed on the data collected from the AIS system
by Baltica ship, dated on 6th June, 2014 [15]. The simulation was performed
for snapshots of ships’ positions taken in one hour intervals. Summary, which
provides information about numbers of nodes and links, as well as the sizes of
the root’s arrays of the trees (obtained by the TBRP protocol) for particular
hours, are shown in Table 1. The data for hours 19, 20 and 23 was unavailable,
because the node selected for the root of a tree in TBRP routing, did not contain
any record in its routing table. This is due to the fact that the data collected
by the AIS system by Baltica ship does not necessarily show all the ships in the
Baltic Sea region, because this system has limited range.
For each network snapshot, 15 iterations of the simulation were run during
which data transport methods used for monitoring were analyzed. The results,
which represent the total amount of generated data on all links of the network
are shown in Fig. 4.
Table 1. Hourly summary for number of vessels (nodes in the network) that have been
registered by the AIS.
where:
P (A) – the probability of an event A, the occurrence of the proper packet;
P (Y ) – the empirical probability of (derived from statistical surveys) the event
y, where y event states that the packet is either addressed to the monitoring
center or has it along its route;
p(x) – empirical probability distribution, which specifies the possibility of passing
through or sending the packet by the node, where x is the packet arrival time;
T – time in which the proper packet occurs;
h(z) – empirical probability distribution which define the probability of a packet
that has a specified size of data field of link layer protocol, where z is the size of
the data field;
R – maximum size of the data field, decreased by size of added monitoring data.
The monitoring time in the classic version of the monitoring depends only on
the delay associated with the propagation of data packets from the monitoring
center to a node, and then back to the monitoring center.
The proposed EHBMPvU monitoring mechanism is not transparent to the
devices in the network, as it requires all devices to support the use of the proposed
additional IPv6 header mechanism. If all the nodes in the network have to be moni-
tored, this means that all the nodes must be able to recognize and process the addi-
tional monitoring header. Otherwise the packet is discarded by the router, because
the node will not know what to do with such header. In case of the EHBMPvF
mechanism, these issues looks different, because the Routing Header (Type 0) is
described in IPv6 [16], but for safety reasons, in the year 2007, the Routing Header
(Type 0) was withdrawn and marked by status of disapproval (deprecated) [17].
Therefore, it may not be supported by the routers. This is due to the fact that this
header can be used to perform DoS (Denial of Service) attacks. The issue has been
solved by introducing Routing Header Type II [18].
In the context of the necessary requirements to perform monitoring, one
should keep in mind the resources of devices in the network. The described
monitoring solutions require the ability to parse, process and send monitoring
data, so routers must have sufficient processing power to perform these tasks,
along with the other functions implemented in router. The busiest router is node
which is the monitoring center, because it collects data from all nodes in the
network. In the EHBMPvF method it is also responsible for sending requests
for collecting data. To send such packets, the router must perform additional
calculations associated with the optimization of the number of required packets
and must allocate a list of addresses to visit for each packet. The EHBMPvF
mechanism uses the RM-AODV on demand routing, which generates additional
traffic in the network and load to the nodes.
Hardware requirements for the classic method of monitoring are similar to
what EHBMPvU requires – the processing of monitoring data.
Security of collected data is also important as they should be kept confidential
and integral. To ensure these requirements, the use of IPsec (Internet Protocol
Security [19–21]) security suite is recommended in the netBaltic Project.
100 D. Karpowicz et al.
5 Summary
To summarize the presented characteristics in Table 2, one can come to the
conclusion that the best solution is to use EHBMPvU monitoring, which is well
scalable, provides full coverage in a short time, has small requirements and is
secured by the means for confidentiality and authenticity. The only problem
which may occur is the case when the application traffic characteristics would
a node require to wait long for the correct data packet. In the extreme case
where the traffic would be strictly limited or the total lack of it, the realization
of EHBMPvU monitoring would not be possible.
Knowing the characteristics of the traffic the probability of sending monitor-
ing data by each node can be estimated – after an event triggering this process
(at certain time or in the response to the identified event in the network).
EHBMPvU method should be used in networks where the characteristics of
the existing traffic does not cause unacceptable delays in providing data used for
monitoring. Longer delays may cause that the transmitted data can be regarded
as outdated.
The classic method of monitoring is the best choice if the network to be
monitored has an unacceptable traffic characteristics to use by the EHBMPvU
solution.
Alternatively, you can use a hybrid solution using the classic method of mon-
itoring wherever the characteristics of traffic does not allow for acceptable time
to provide data to the monitoring center and EHBMPvU where the time is
acceptable.
The choice of monitoring method for netBaltic system requires testing the
characteristics of mobility. Then and only then it will be possible to unambigu-
ously identify the best monitoring method for this type of network. However,
yet at this early stage of testing, the EHBMPvF method can be rejected due to
very large overhead related to monitoring.
Acknowledgments. This work has been partially supported by the Applied Research
Program under the Grant: ID PBS3/A3/20/2015, founded by the National Centre for
Research and Development.
References
1. Silvestri, S., Urgaonkar, R., Zafer, M., Ko, B. J.: An online method for minimizing
network monitoring overhead. In: 2015 IEEE 35th International Conference on
Distributed Computing Systems (ICDCS), pp. 268–277. IEEE (2015)
2. Lee, S., Levanti, K., Kim, H.S.: Network monitoring: present and future. Comput.
Netw. 65, 84–98 (2014)
3. Mahkonen, H., Manghirmalani, R., Shirazipour, M., Xia, M., Takacs, A.: Elastic
network monitoring with virtual probes. In: 2015 IEEE Conference on Network
Function Virtualization and Software Defined Network (NFV-SDN), pp. 1–3. IEEE
(2015)
4. Prieto, A.G., Stadler, R.: A-GAP: an adaptive protocol for continuous network
monitoring with accuracy objectives. IEEE Trans. Netw. Serv. Manage. 4(1), 2–12
(2007)
5. Dilman, M., Raz, D.: Efficient reactive monitoring. IEEE J. Sel. Areas Commun.
20(4), 668–676 (2002)
6. Jiao, J., Naqvi, S., Raz, D., Sugla, B.: Toward efficient monitoring. IEEE J. Sel.
Areas Commun. 18(5), 723–732 (2000)
7. Höfig, E., Coşkun, H.: Intrinsic monitoring using behaviour models in IPv6 net-
works. In: Strassner, J.C., Ghamri-Doudane, Y.M. (eds.) MACE 2009. LNCS, vol.
5844, pp. 86–99. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-
05006-0 7
8. Shi, L., Davy, A., Muldowney, D., Davy, S., Höfig, E., Fu, X.: Intrinsic monitoring
within an IPv6 network: mapping node information to network paths. In: 2010
International Conference on Network and Service Management (CNSM), pp. 370–
373. IEEE (2010)
9. Shi, L., Davy, A.: Intrinsic monitoring within an ipv6 network: relating traffic flows
to network paths. In: 2010 IEEE International Conference on Communications
(ICC), pp. 1–6. IEEE (2010)
10. Hoeft, M., Gierlowski, K., Nowicki, K., Rak, J., Woźniak, J.: netBaltic: enabling
non-satellite wireless communications over the baltic sea. IEEE Commun.
Mag. 5 (2016). http://gcn.comsoc.org/netbaltic-enabling-non-satellite-wireless-
communications-over-baltic-sea
11. Woźniak, J., Hoeft, M.: Aim and main research tasks of the netBaltic project (in
Polish). Telecommun. Rev. Telecommun. 12, 1301–1303 (2016)
102 D. Karpowicz et al.
12. Institute of Electrical and Electronics Engineers: Wireless LAN Medium Access
Control (MAC) and Physical Layer (PHY) Specifications. 802.11-2012 (2012)
13. Institute of Electrical and Electronics Engineers: Wireless LAN Medium Access
Control (MAC) and Physical Layer (PHY) Specifications - Amendment 10: Mesh
Networking. 802.11-2011 (2011)
14. Karpowicz, D., Nowicki, K.: Implementation of database API for archival large-
scale AIS data retrieval for netBaltic Project simulation purposes (in Polish). Sci-
entific report, Gdańsk (2016)
15. Lewczuk, M., Hoeft, M., Cichocki, P., Woźniak, J., Nowicki, K.: Systems of AIS
data acquisition, processing and visualization for the netBaltic project (in Polish).
Telecommun. Rev. Telecommun. News 12, 1326–1329 (2016)
16. Deering, S., Hinden, R.: RFC 2460, Internet Protocol, Version 6 (IPv6) Specifica-
tion. Internet Engineering Task Force (1998)
17. Neville-Neil, G., Savola, P., Abley, J.: RFC 5095, Deprecation of Type 0 Routing
Headers in IPv6 (2007)
18. Johnson, D.B., Arkko, J., Perkins, C.E.: RFC 6275, Mobility Support in IPv6
(2015)
19. Seo, K., Kent, S.T.: RFC 4301, Security Architecture for the Internet Protocol
(2005)
20. Kent, S.T.: RFC 4303, IP Encapsulating Security Payload (ESP) (2005)
21. Gierszewski, T.: Transport security mechanisms for netBaltic system (in Polish).
Telecommun. Rev. Telecommun. News 8–9, 813–816 (2017)
A Novel Auction Based Scheduling
Algorithm in Industrial Internet
of Things Networks
Abstract. Enabling low data losses and ensuring reliability are essen-
tial requirements to guarantee Quality of Service in Industrial Internet
of Things (IIoT) applications. This can be achieved by the adoption
of various architectures and standards, the most promising of which is
IEEE 802.15.4 Time Slotted Channel Hopping mode. However, there are
still several open issues, such as providing effective scheduling scheme in
the standard. In this paper, we propose a novel auction based schedul-
ing mechanism that uses a first-price sealed bids auction to solve the
throughput maximizing scheduling problem. We considered a central-
ized IIoT network where the gateway makes frequency allocations and
time slot assignment. Simulation results show that the proposed algo-
rithm yields a very close throughput performance to the optimal one
obtained through CPLEX with a much lower complexity.
1 Introduction
The notion of the Industrial Internet of Things (IIoT) has moved beyond its hype
of becoming the next wave of innovation, and today we are seeing a rapid increase
in deployment of IIoT in many application areas, such as smart farming, smart
grids, building automation. IIoT relies on low-cost, low power wireless sensor
and actuator devices with constrained computational capabilities that are con-
nected to the internet through wireless communication technologies [1,2]. The
deployment of such devices has led to the convergence of operational technolo-
gies (i.e., industrial networks) and information technologies (i.e., internet). The
principle of IIoT has also fostered the concept of Industry 4.0, where it is aimed
to provide automation and information domain for services and people [3].
The increasing usage of wireless technologies in industrial environments has
become appealing to many types of applications. This has introduced flexibil-
ity and a cost-effective solution in the network approach, but has also added
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 103–114, 2018.
https://doi.org/10.1007/978-3-319-92459-5_9
104 M. Ojo et al.
where ASN (Absolute Slot Number) counts the number of time slots since the
beginning of the network operation, FM AP is the mapping function to find the
frequency from a channel lookup table and Nch indicates the number of avail-
able physical channels (e.g., 16 when using IEEE 802.15-4 compliant radios at
2.4 GHz).
Fig. 2. Time Slotted Channel Hopping (TSCH) slot-channel matrix with a simple
topology
and channel offset. A distributed scheduling approach [9] was also proposed to
construct optimum multi-hop schedules based on neighbour-to-neighbour sig-
nalling. Another non-graph approach for scheduling is Orchestra [10], a solution
for autonomous scheduling of TSCH in IPv6 Routing Protocol for Low-Power
and Lossy Networks (RPL). Orchestra runs without any central entity, nor any
negotiation, but allocates the slots in such a way that it can be automatically
installed or removed as the RPL topology evolves. In [11], the authors proposed a
scheduling scheme to maximize the energy efficiency, while [12] addresses latency
issues.
In this paper, we focus on a centralized scheduling method based on auc-
tioning to maximize the total throughput in an interference-aware system, since
a centralized approach have been proven to be more effective in practice [13].
The major novelty of our work is that we provide a much more general and
complete scheduling model that achieves frequency, time slot, data rate alloca-
tion in a heterogeneous multi-user and multi-channel environment. Our auction
procedure uses a first-price sealed-bid mechanism [14] to address the throughput
scheduling problem in IEEE 802.15.4-2015 TSCH networks. In first-price sealed-
bid auctions, all bidders simultaneously submit sealed bids (hidden from other
bidders) to the auctioneer. The bidder with the highest bid wins the auction.
Auction based mechanism have been applied to other networks such as cog-
nitive radio networks [15] cellular networks device to device communication sys-
tems [16] peer to peer networks [17], but to the best of our knowledge, this is
the first work that addresses scheduling in IEEE 802.15.4-2015 TSCH networks
using auction based mechanism.
A Novel Auction Based Scheduling Algorithm in IIoT Networks 107
Fig. 3. Time Slotted Channel Hopping (TSCH) slot-channel matrix where each nk
maintains a link with the gateway (GW ) for both frequency f and time slot t, where
k ∈ {1, ...N }; f ∈ {1, ..., F }, t ∈ {1, ..., T }
At the beginning of the slot frame, each node nk calculates the transmission
capacity of the channel for each available frequency, and transmits this infor-
mation to the gateway in addition to the number of packets in its buffer (Qk ).
In this way, the gateway constructs a matrix U = [Uk,f,t ], where Uk,f,t is the
number of packets that can be transmitted by node k using frequency f . Upon
collection of all state information such as topology information, traffic generated
by each node etc., the scheduler decides on the frequency assignment with the
goal of maximizing the throughput.
Let Ck,f,t denote the Shannon’s capacity of the link between nk and the
gateway GW at frequency f . Ck,f,t is a function of the signal-to-noise ratio
SN Rk,f,t and represents the theoretical upper bound. In the calculation of Ck,f,t ,
only the background noise is considered as we focus on an orthogonal frequency
assignment. The number of packets that can be sent during a slot frame duration,
Mk,f,t , equals Ck,f,t T where T is the slot frame duration. Accordingly, Uk,f,t
becomes min(Mk,f,t , Qk ).
Considering the binary variable Xk,f,t defined as:
⎧
⎨ 1 if node nk transmits using frequency f in time slot t;
Xk,f,t =
⎩
0 otherwise;
x = [Xk,f,t , k ∈ {1, ...N }; f ∈ {1, ...F }; t ∈ {1, ...T }] is the scheduling decision
vector with elements Xk,f,t . Note that Xk,f,t is a function of the information
available to nk . We calculate the total throughput in TSCH network as
N
F
T
C= Uk,f,t Xk,f,t (2)
k=1 f =1 t=1
node, and to avoid any starving node at the end of the algorithm. A starving
node is indicated as the node that has not been assigned any time slot during any
stage of the algorithm. Our proposed scheduling algorithm is explained through
steps 1 to 6 below.
STEP 1: For each frequency f , find the node who transmits the maximum
number of packets using that frequency. Assign the frequency to that node for
all time slots of the slot frame period. In other words, assign f to node k where
k = argmaxk Uk,f . We denote wk the number of frequencies assigned to node k
at the end of step 1.
STEP 2: If every node is assigned at least one F T RP and wk ≤ ak , ∀k, end.
Otherwise, each node that is assigned more than one frequency sorts its frequen-
cies according to their Uk,f values. If any node k has wk greater than ak , go to
step 4 and 5, else go to step 6.
STEP 3: Do we have a starving node? if yes, go to step 4, otherwise go to
step 5.
STEP 4: Any node k whose wk ≥ ak auctions all time slots of wk − ak of
its frequencies which have the smallest Uk,f values. The F T RP s are auctioned
simultaneously. The starving node bids to the F T RP , whose corresponding Uk,f
value is the greatest one. When the starving node gets a F T RP , it is removed
from the auction procedure. The auctions continue until all the starving node
gets a F T RP or when no F T RP remains. At the end of the auctioning proce-
dure, if we still have F T RP that are not assigned to any node, they are auctioned
out to the nodes that have available transceivers. Otherwise, if there still exists
a starving node and all resources are assigned, then go to step 6.
STEP 5: Any node k whose wk ≥ ak takes ak of its frequencies with the largest
Uk,f values. The F T RP s which belong to the remaining wk − ak frequencies are
assigned greedily to the nodes who have available transceivers.
STEP 6: Any node k that is assigned more than one frequency auctions wk − 1
number of its frequencies which have the smallest Uk,f values until either no
starving node remains or the auctioned F T RP run out. When all nodes have
at most a single frequency, if any starving node exists they auction out their
remaining frequencies.
5 Performance Evaluation
A simulation based study was carried out in order to evaluate the performance of
the proposed algorithm. We consider a TSCH network consisting of sensor nodes
randomly placed over a square area of 100 m × 100 m and a gateway located in
the center. The x and y coordinates of each node follow a uniform distribution.
Every node is equipped with a radio that has a transmission range of 30 m. Uk,f
values are different owing to the changing network conditions and are obtained
for 3000 slot frame periods in each set of simulations where the average is consid-
ered. Each slot frame period consists of 30 time slot, where each time slot has a
A Novel Auction Based Scheduling Algorithm in IIoT Networks 111
100
90
F =3
auc
F =3
opt
80 F =9
auc
Throughput (Packets/time-slot)
F =9
opt
F =16
70 auc
F =16
opt
60
50
40
30
20
2 4 6 8 10 12 14 16
Nodes
Fig. 4. Comparison of the proposed scheduling algorithm with the optimum results
obtained through CPLEX simulations
100
90
80
Throughput (Packets/time-slot)
70
a=1 antenna
60 a=2 antenna
a=3 antenna
50
40
30
20
10
2 4 6 8 10 12 14 16
Frequencies (F)
Fig. 5. Average total network throughput for the throughput maximization scheduling
problem by varying the number of antennas and frequencies
A Novel Auction Based Scheduling Algorithm in IIoT Networks 113
6 Conclusions
In this paper, we formulated the throughput maximization scheduling problem
for IIoT-TSCH based networks in a centralized way. In more detail, we proposed
a novel heuristic scheduling algorithm based on first-price sealed bid auction
mechanism to solve the problem. The performance of our sub-optimal scheduler
is close to the optimal one obtained through ILOG-CPLEX. We observed that
having many antennas, (i.e., a > 2) does not increase the average throughput.
Moreover, the computational complexity for the best case scenario is O(N F )
while for the worst case scenario is O((N F ) + N 2 logN ).
In our future work, we plan to design approximation algorithms, which have
theoretically provide performance guarantee for the throughput maximization
scheduling problem.
References
1. Willig, A.: Recent and emerging topics in wireless industrial communications: a
selection. IEEE Trans. Ind. Inf. 4(2), 102–124 (2008). https://doi.org/10.1109/
TII.2008.923194
2. Li, X., Li, D., Wan, J., Vasilakos, A.V., Lai, C.-F., Wang, S.: A review of industrial
wireless networks in the context of industry 4.0. Wirel. Netw. 23(1), 23–41 (2017).
https://doi.org/10.1007/s11276-015-1133-7
3. Kagermann, H., Helbig, J., Hellinger, A., Wahlster, W.: Recommendations for
implementing the strategic initiative INDUSTRIE 4.0: Securing the future of Ger-
man manufacturing industry; final report of the Industrie 4.0 Working Group.
Forschungsunion (2013)
4. IEEE Standard for Low- Rate Wireless Networks: IEEE Std 802.15.4-2015 (Revi-
sion of IEEE Std 802.15.4-2011), April 2016
5. ISA-100.11a-2011: Wireless Systems for Industrial Automation: Process Control
and Related Applications. ISA.100.11a-2011 (2011)
6. Chen, D., Nixon, M., Han, S., Mok, A.K., Zhu, X.: Wirelesshart and IEEE
802.15.4e. In: 2014 IEEE International Conference on Industrial Technology
(ICIT), pp. 760–765. IEEE (2014). https://doi.org/10.1109/ICIT.2014.6895027
7. Ojo, M., Giordano, S.: An efficient centralized scheduling algorithm in IEEE
802.15.4e TSCH networks. In: 2016 IEEE Conference on Standards for Communi-
cations and Networking (CSCN), pp. 1–6. IEEE (2016). https://doi.org/10.1109/
CSCN.2016.7785164
8. Palattella, M.R., Accettura, N., Dohler, M., Grieco, L.A., Boggia, G.: Traffic aware
scheduling algorithm for reliable low- power multi-hop IEEE 802.15.4e networks.
In: 2012 IEEE 23rd International Symposium on Personal Indoor and Mobile Radio
Communications (PIMRC), pp. 327–332. IEEE (2012). https://doi.org/10.1109/
PIMRC.2012.6362805
114 M. Ojo et al.
9. Accettura, N., Palattella, M.R., Boggia, G., Grieco, L.A., Dohler, M.: Decentralized
traffic aware scheduling for multi- hop low power Lossy networks in the Internet
of Things. In: 2013 IEEE 14th International Symposium and Workshops World of
Wireless, Mobile and Multimedia Networks (WoWMoM), pp. 1–6. IEEE (2013).
https://doi.org/10.1109/WoWMoM.2013.6583485
10. Duquennoy, S., Al Nahas, B., Landsiedel, O., Watteyne, T.: Orchestra: robust
mesh networks through autonomously scheduled TSCH. In: Proceedings of the
13th ACM Conference on Embedded Networked Sensor Systems, pp. 337–350.
ACM (2015). https://doi.org/10.1145/2809695.2809714
11. Ojo, M., Giordano, S., Portaluri, G., Adami, D., Pagano, M.: An energy efficient
centralized scheduling scheme in TSCH networks. In: 2017 IEEE International
Conference on Communications Workshops (ICC Workshops), pp. 570–575. IEEE
(2017). https://doi.org/10.1109/ICCW.2017.7962719
12. Hosni, I., Théoleyre, F., Hamdi, N.: Localized scheduling for end-to-end delay
constrained low power Lossy networks with 6TiSCH. In: 2016 IEEE Symposium
on Computers and Communication (ISCC), pp. 507–512. IEEE (2016). https://
doi.org/10.1109/ISCC.2016.7543789
13. Palattella, M.R., Accettura, N., Grieco, L.A., Boggia, G., Dohler, M., Engel, T.: On
optimal scheduling in duty-cycled industrial IOT applications using IEEE802.15.4e
TSCH. IEEE Sens. J. 13(10), 3655–3666 (2013). https://doi.org/10.1109/JSEN.
2013.2266417
14. Krishna, V.: Auction Theory. Academic Press (2009)
15. Dong, M., Sun, G., Wang, X., Zhang, Q.: Combinatorial auction with time-
frequency flexibility in cognitive radio networks. In: INFOCOM, 2012 Proceed-
ings IEEE, pp. 2282–2290. IEEE (2012). https://doi.org/10.1109/INFCOM.2012.
6195615
16. Xu, C., Song, L., Han, Z., Zhao, Q., Wang, X., Cheng, X., Jiao, B.: Efficiency
resource allocation for device-to-device underlay communication systems: a reverse
iterative combinatorial auction based approach. IEEE J. Sel. Areas Commun.
31(9), 348–358 (2013). https://doi.org/10.1109/JSAC.2013.SUP.0513031
17. Shneidman, J., Parkes, D.C.: Rationality and self-interest in peer to peer networks.
In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, pp. 139–148.
Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45172-3 13
18. IBM ILOG CPLEX: V12. 1: Users manual for CPLEX. Int. Bus. Mach. Corpora-
tion 46(53), 157 (2009)
A New Approach for SDN Performance
Enhancement
1 Introduction
The recent trends of data digitization in large scale call for significant changes in
the communication technologies and network platforms. In traditional network,
computing infrastructure, and protocol stack may not be suitable to provide ade-
quate solutions to such growing and heterogeneous demands. This leads towards
a divergent approach in network systems architecture, called Software Defined
Network (SDN). Software Defined Networking is a layered network framework
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 115–129, 2018.
https://doi.org/10.1007/978-3-319-92459-5_10
116 M. Priyadarsini and P. Bera
leads to create a green environment, which we can call as Green ICT. Basically
performance enhancement reduces energy consumption through out the network,
mainly in data centers which leads to a green environment. SDN performance is
evaluated considering following network parameters: Throughput, Latency, Jit-
ter, Bandwidth, Response Time. In this paper, we evaluated the performance
of SDN controllers based on the above mentioned parameters and reported the
applicability of the various controllers in heterogeneous traffic scenarios. This
comparison drives us to design a logical decision making module, called packet
scheduler that schedules the traffic in different controllers with varying require-
ments. The scheduler can be implemented inside the SDN hypervisor. It has
been observed that the performance of controller improves significantly based
on our proposed controller architecture with appropriate inter SDN controller
communication.
The rest of the paper is organized as follows. Section 2 presents the motivation
and objectives of the work. We describe a study of different SDN controllers
like NOX, POX, Beacon, Floodlight along with simulation results without our
proposed packet scheduler algorithm in Sect. 3. Section 4 states about the packet
scheduler inside the hypervisor, its functionality and its communication with the
controller, also inter controller communication between various SDN domains.
We conclude in Sect. 5 with further proceedings.
(1) NOX: It was initially developed side-by-side with OpenFlow and was the first
OpenFlow controller. It uses the concept of single threading and virtualiza-
tion [20]. NOX is the basic level controller for performance enhancement.
NOX’s network view encompasses the switch level topology; the locations
of users, hosts, middleboxes, and other network elements, and the services
(e.g., HTTP or NFS) being granted. It also incorporates all bindings between
names and addresses, but does not include the current state of network traf-
fic. There exists multithreaded successor of NOX which is known as NOX-
MT. NOX-MT uses well-known optimization techniques (e.g., I/O batching)
to promote the threshold performance.
(2) NOX-MT: NOX-MT, a marginally modified multi- threaded successor of
NOX, to show that with simple tease NOX’s throughput and response time
is significantly improved. The techniques used to optimize NOX are utterly
well-known including: I/O batching to minimize the overhead of I/O, port-
ing the I/O handling harness to Boost Asynchronous I/O (ASIO) library
(which simplifies multi-threaded operation), and used a fast multiprocessor-
aware malloc implementation that scales well in a multi-core machine [20]. It
does not address many of NOX’s performance deficiencies, including: heavy
use of dynamic memory allocation and redundant memory copies on a per
request basis. Addressing these issues would significantly improve NOX’s
performance.
(3) POX: POX is an OpenFlow networking software platform written in Python.
POX started life as an OpenFlow controller, but now functions as an Open-
Flow switch, and also be useful for writing networking software. POX pro-
vides OpenFlow interface and reusable components for path selection, topol-
ogy discovery, etc. POX, which enables rapid development and prototyping,
is becoming more commonly used than NOX.
(4) Beacon: Beacon is a fast, cross-platform, Java-based OpenFlow controller
that supports both event-based and threaded operation [18]. Beacon runs on
many platforms, from high end multi-core Linux servers to Android phones.
Beacon architecture includes event handling, reading openflow messages,
writing openflow messages to enhance performance.
A New Approach for SDN Performance Enhancement 119
For the purpose of performance analysis and evaluation, we have simulated four
SDN controllers, namely, NOX, POX, Beacon, Floodlight and represented the
results with necessary recommendations for SDN implementation and deploy-
ment in enterprise network. We have used following environments for our
simulation.
efficiently and enhances the performance of the network than the existing ones.
The proposed SDN architecture is shown in Fig. 5. The scheduler receives open
flow packets from switches (Application Layer) and schedules the traffic to its
appropriate controller. We discussed the performance of different controllers in
the last section in terms of bandwidth, latency, jitter, throughput and response
time. The scheduling algorithm is developed based on the performance result of
the controllers. Whenever packet comes from the OpenFlow network, the module
fetches features of incoming packets and forwards accordingly to the pertinent
controller. It is important that, the presence of packet scheduler is nontranspar-
ent to the controller under consideration.
connections as shown in Fig. 6. The tuple of the packet along with the port is
stored in the ControllerPort Class. First Thread (Thread1) consumes packets
and address of the target controller from the queue and sends it to the speci-
fied controller till the queue is not empty. Second thread (Thread2) reads data
from the shared SocketChannel and writes data into the switch. For creation of
packet scheduler, we used multi-threaded implementation concept of Floodlight
controller (Netty API for network I/O operations). The threads are terminated
as the corresponding switch is disconnected.
The packet scheduler schedules the traffic depending upon following two
metrics.
A New Approach for SDN Performance Enhancement 123
1. Load on the destined controller Lcurrent depends upon two network parame-
ters, total message arrival rate (I) to the controller from switches and round
trip time from each switch to controller (R). The round trip time (R) is mea-
sured by the number of hops present between controller and packet scheduler.
If the load exceeds the predefined threshold (T hr) value, then the packet
scheduler assumes that controller as heavily loaded and calculates load of
other controllers present inside the network. The controller which is lightly
loaded becomes the destination controller for that packet.
Lcurrent = I ÷ R (1)
2. Load on the path λij is considered, depending upon link utilization Uij and
link capacity Cij of each path exists between packet scheduler and the destina-
tion controller. Among all the paths, which ever is having less load, the packet
will follow that path. Packet scheduler sets new destination port Dportnew
according to the traffic type and load of controller and path.
A session must be initiated between two controllers using either BGP (Border
Gateway Protocol) or SIP (Session Initiation Protocol). Here we considered BGP
connection over TCP for our better appliances [15]. Controllers need to exchange
information such as:
Table 2. Network parameter values of different controllers before and after introduc-
tion of packet scheduler
References
1. Salman, O., Elhajj, I.H., Kayssi, A., Chehab, A.: SDN controllers: a compara-
tive study. In: Proceedings of the 18th Mediterranean Electrotechnical Conference
MELECON 2016, Limassol, Cyprus, 18–20 April 2016
2. Chen-xiao, C.: Research on load balance method in SDN. Int. J. Grid. Distrib.
Comput. 9(1), 25–36 (2016)
A New Approach for SDN Performance Enhancement 129
3. Rao, S.: A Guide for Running Multiple Controllers in Software Defined Networks,
An Article on “TheNewStack”, 21 March 2016
4. Bampal, R.: Cbench Data to Graph (2016). https://github.com/Rhnbmpl/cbench-
data-graph
5. Bholebawa, I.Z., Jha, R.K., Dalal, U.D.: Performance analysis of proposed network
architecture: OpenFlow vs. traditional network. Int. J. Comput. Sci. Inf. Secur.
(IJCSIS) 14(3), 943–958 (2016)
6. Hasan, H., et al.: Improvement of performance of EIGRP network by using a
supervisory controller with smart congestion avoidance algorithm. In: International
Conference on Telecommunications and Multimedia (TEMU) (2016)
7. Zhao, Y., Iannone, L., Riguidel, M.: On the performance of SDN controllers: a real-
ity check. In: IEEE Conference on Network Function Virtualization and Software
Defined Network (NFV-SDN) (2015)
8. Samociuk, D.: Secure communication between OpenFlow switches and controllers.
In: The Seventh International Conference on Advances in Future Internet AFIN
(2015)
9. Benamrane, F., Ben mamoun, M., Benaini, R.: Performances of OpenFlow-based
software- defined networks: an overview. J. Netw. 10(6), 329–337 (2015)
10. Ganesh, S., Ranjani S.: Dynamic load balancing using software defined networks.
In: International Conference on Current Trends in Advanced Computing (ICC-
TAC) (2015). Int. J. Comput. Appl
11. Xia, W., Wen, Y., Foh, C.H., Niyato, D., Xie, H.: A survey on software-defined
networking. IEEE Commun. Surv. Tutorials 17(1), 27–51 (2015)
12. Khattak, Z.K., Awais, M., Iqbal, A.: Performance evaluation of OpenDaylight SDN
controller. In: 20th IEEE International Conference on Parallel and Distributed
Systems (ICPADS) (2014)
13. Shin, S., et al.: Rosemary: a Robust, secure, and high-performance network oper-
ating system. In: CCS 2014, Arizona, USA, 3 November 2014
14. Chilwan, A., et al.: On modeling controller-switch interaction in Openflow based
SDN. Int. J. Comput. Netw. Commun. (IJCNC) 6(6) (2014)
15. Jahan, R., Gupta, D.: White Paper Inter-SDN Controller Communica-
tion using BGP (2014). http://docplayer.net/5817317-Telecom-white-paper-inter-
sdncontroller-communication-using-border-gateway-protocol.html. Accessed July
2017
16. Braun, W., Menth, M.: Software-defined networking using openflow: protocols,
applications and architectural design choices. Future Internet 6(2), 302–336 (2014).
https://doi.org/10.3390/fi6020302
17. Shah, S.A., Faiz, J., M., Farooq, J., Shafi, A., Mehdi, S.A.: An architectural evalu-
ation of SDN controllers. IEEE International Conference on Communications, pp.
3504–3508. IEEE (2013)
18. Erickson, D.: The Beacon OpenFlow controller. In: HotSDN 2013, Hong Kong,
China, 16 August 2013
19. Gelberger, A., Yemini, N., Giladi, R.: Performance analysis of software defined
networking (SDN). In: IEEE 21st International Symposium on Modeling, Analysis
and Simulation of Computer and Telecommunication Systems (2013)
20. Gude, N., Koponen, T., Pettit, J., Pfaff, B., Casado, M., McKeown, N., Shenker,
S.: NOX: towards an operating system for networks. ACM SIGCOMM Comput.
Commun. Rev. 38(3), 105–110 (2008)
Quantum Coherence Measures
for Quantum Switch
1 Introduction
may be, for example, verified with use of quantum entanglement phenomenon –
some basic information concerning this method was contained in [4,22]. In this
chapter we suggest utilizing the Coherence measure [3] to evaluate the correct-
ness of switch’s operating. Furthermore, following the results described in [10]
we propose of a quantum circuit that estimates of Coherence measure value for
a quantum switch. It should be stressed that estimating the value of Coherence
measure allows to trace the behavior of quantum system and clearly points out
if it works properly.
The chapter is organized as follows. In Sect. 2 the basic information concern-
ing the quantum switch was presented. This section contains description of the
switch as a Hamiltonian and as a time-dependent unitary operation. There is
also an example of distortions modeled with use of Dzyaloshinskii-Moriya inter-
action [7,19]. Sect. 3 contains definitions of Coherence measure, its properties
and two examples of popular realizations.
A description of measures in context of the switch are presented in Sect. 4. We
showed direct analytical formulas expressing Coherence measure for the switch
during its operating. Conducted numerical experiments demonstrate changes in
value of Coherence measure for systems with and without noise. We calculated
also an analytical formula describing a difference between the values of Coherence
measure for systems without presence of noise and with distortions modeled as
Dzyaloshinskii-Moriya interaction.
The summary and plans for further work are presented in Sect. 5. A list of
references to other works ends this chapter.
2 Quantum Switch
A quantum switch, analyzed in this chapter, is a system of three qubits denoted
as: A, B, C. The states of qubits A and B are unknown:
The state of C is known and preserves only two possible alternatives: |C = |0
or |C = |1.
A main task of the quantum switch is swapping an unknown states between
qubits A and B. This operation is performed conditionally: if the state of qubit
|C is |0 then there is no action; but if the state of qubit |C is |1 then the
values of quantum states are exchanged between qubits A and B:
The quantum switch may be depict as a circuit built of three quantum gates:
two CNOT gates and one Toffoli gate. The conditional swapping of quantum
states, realized by the mentioned circuit, is presented at Fig. 1.
Utilizing the circuit, shown at Fig. 1, we can denote a matrix form (also
shown at Fig. 1 – case (c)) of an operator realizing the operation performed
by the quantum switch describes the complete process of information switching
132 M. Sawerwain and J. Wiśniewska
Fig. 1. An exemplary circuit presenting the action performed by the quantum switch.
If the state of third qubit is |0 (case (a)) the switch does not swap the states of first
two qubits. When the state of the last qubit is expressed as |1 (case (b)) the circuit
swaps states |A and |B. Case (c) depicts the matrix form of unitary operator which
performs action of quantum switch
The operation Uqs (t) causes the change of local phase therefore using the phase-
flip gate allows to obtain operator Ûqs (t) which, naturally, does not introduce
any change of local phase into the system.
Both, shown above, forms of unitary operation Uqs (t) let to trace the process
of switch’s operating according to time t. If the switch acts on a state |AB1 and
Quantum Coherence Measures for Quantum Switch 133
there is no correction of the local phase then the final state is a pure quantum
state: ⎛ ⎞
0
⎜ α0 α1 ⎟
⎜ ⎟
⎜ 0 ⎟
⎜ ⎟
⎜ cos(t)α0 β1 − i sin(t)α1 β0 ⎟
Uqs (t)|Ψqs = |Ψqs
t
=⎜
⎜
⎟,
⎟ (5)
⎜ 0 ⎟
⎜ cos(t)α1 β0 − i sin(t)α0 β1 ⎟
⎜ ⎟
⎝ 0 ⎠
β0 β1
where t ∈ 0, π2 .
And representation of this operation as a density matrix ρ is also given:
†
ρ(t) = Uq s(t)|Ψqs
t
Ψqs
t
|Uqs (t). (6)
where UqsDM
stands for the unitary operation. It should be stressed that for Dz
we obtain the Hamiltonian describing only the quantum switch’s operating.
A state of quantum register including an influence of DM interaction may be
expressed as:
⎛ ⎞
0
⎜ α0 α1 ⎟
⎜ ⎟
⎜ 0 ⎟
⎜ ⎟
⎜ (2Dz −it) sinh(γ)α1 β0 + cosh (γ) α β ⎟
U DM
(t) ⎜ 0 1 ⎟
Uqs
DM
(t)|Ψqs = |Ψqsqs =⎜ γ
⎟ , (9)
⎜ 0 ⎟
⎜ (2Dz +it) sinh(γ)α0 β1 ⎟
⎜ cosh (γ) α1 β0 − ⎟
⎜ γ ⎟
⎝ 0 ⎠
β0 β1
and γ = −4Dz2 − t2 . And also as a density matrix ρ:
where S(·) stands for von Neumann entropy and ρdiag denotes a density matrix
without the off-diagonal elements.
where the states |A and |B are unknown. Utilizing measure (12) and carrying
out some necessary transformations allows to calculate the following formula:
As we can see the value of this measure depends only on time elapsing during
the switch’s operating. Basing on the fact that the quantum state is normalized,
we can directly indicate the constraint concerning the value of Cl1 measure for
the state |A0:
ClDM
1
(ρAB ) = 2 |(ξα1 β0 + ηα0 β1 ) (ζα1 β0 + ξα0 β1 )|
+ 2 |α0 α1 (ζα1 β0 + ξα0 β1 )| + 2 |β0 β1 (ζα1 β0 + ξα0 β1 )|
+ 2 |α0 α1 (ξα1 β0 + ηα0 β1 )| + 2 |β0 β1 (ξα1 β0 + ηα0 β1 )| + 2 |α0 α1 β0 β1 | (20)
Fig. 2. The changes in value of Cl1 measure: (a) for some exemplary states A and B
given in (17); (b) for a generalized case given in (18). Plots (c) and (d) present the
changes in value of Coherence measure Cl1 when the noise, generated by DM interaction
with intensity Dz = 0.5, is present: (c) for some exemplary states A and B given in
(17); (d) for a generalized case given in (18). The changes in value of relative entropy
measure Cre : (e) for some particular states; (f) for states A and B given in Eq. (18).
Plots (g) and (h) show the changes in value of Cre measure when the noise, generated
by DM interaction with intensity Dz = 0.5, is present: (g) for states given in (17); (h)
for states A and B given in (18)
138 M. Sawerwain and J. Wiśniewska
The properties (P1)–(P4) indicate that the values of relative entropy of coher-
ence measure Cre also correctly depict the differences in a system’s operating
without and with presence of the DM interaction. For quantum states given in
Eqs. (17) and (18) values of relative entropy measure Cre are shown at Fig. 2.
Additionally, Fig. 2 demonstrates values of Cre measure with distortions gener-
ated by DM interaction.
Naturally, the Theorem 1 may be also based on relative entropy measure. It
may be observed that the value of this measure is:
2 2 2 2
Cre (ρAA ) = −2 |α0 | |β0 | log |α0 | |β0 |
4 4
+2 |α0 | (log |α0 |) + 2 |β0 | (log |β0 |) , (21)
Fig. 3. The changes in value of absolute difference ClΔ1 : (a) for states given in (17);
(b) for states A and B given in (18). The parameter Dz = 0.5. Figure (c) represents a
quantum circuit for estimation of Coherence measure
5 Conclusions
In this chapter we discussed utilizing the Coherence measure to trace and evalu-
ate the correctness of quantum switch’s operating. First, we described the switch
with use of a Hamiltonian to be able to analyze the evolution of quantum sys-
tem processed by the circuit shown at Fig. 1. We chose the Dzyaloshinskii-Moriya
interaction as a source of noise, which was also modeled as a Hamiltonian. Then
the numerical simulations were performed to evaluate a behavior of the circuit.
As a tool to capture the differences between the switch operating, simulated
140 M. Sawerwain and J. Wiśniewska
with noise or without it, two Coherence measures were used: l1 -norm coherence
(Cl1 ) and relative entropy of coherence (Cre ).
We can observe the difference of Cl1 and Cre values if the system works
with and without a noise. This shows that the Coherence measures allow to
state if the switch operates properly. In addition, an interesting behavior of the
system was observed when the switch worked on an initial state |AA1. The
experiment showed that the value of Cl1 was constant during the simulation –
for other states |AB1, where A = B, the value of measure evaluates in some
characteristic periodic way. This implies that we can also check if the states are
the same with use of Cl1 measure and quantum switch.
Unfortunately, we also observed that for the systems without and with dis-
tortions, modeled as DM interaction, the differences in Coherence measure value
are significant even if their intensity Dz is quite low. It is inconvenient if we would
like to capture the evolution of the system with the different levels of noise.
We presented a quantum circuit which estimates the value of Coherence
measure. Nowadays, technical solutions based on quantum optics [1,2,17] and
also physical implementations of qubits allow to build this kind of circuits with
use of beam splitters, phase shifters and mirrors [14,18].
Acknowledgments. We would like to thank for useful discussions with the Q-INFO
group at the Institute of Control and Computation Engineering (ISSI) of the University
of Zielona Góra, Poland. We would like also to thank to anonymous referees for useful
comments on the preliminary version of this chapter. The numerical results were done
using the hardware and software available at the ”GPU µ-Lab” located at the Institute
of Control and Computation Engineering of the University of Zielona Góra, Poland.
References
1. Abubakar, M.Y., Jung, L.T., Foong, O.M.: Two channel quantum security mod-
elling focusing on quantum key distribution technique. In: 5th International Con-
ference on IT Convergence and Security (ICITCS), Kuala Lumpur, Malaysia, pp.
1–5 (2015)
2. Aguado, A., Lopez, V., Martinez-Mateo, J., Szyrkowiec, T., Autenrieth, A., Peev,
M., Lopez, D., Martin, V.: Hybrid conventional and quantum security for software
defined and virtualized networks. IEEE/OSA J. Opt. Commun. Netw. 9(10), 819–
825 (2017)
3. Baumgratz, T., Cramer, M., Plenio, M.B.: Quantifying coherence. Phys. Rev. Lett.
113, 140401 (2014)
4. Bruß, D., Macchiavello, C.: Multipartite entanglement in quantum algorithms.
Phys. Rev. A 83, 052313 (2011)
5. Cariolaro, G.: Quantum Communications. Springer International Publishing,
Heidelberg (2015)
6. D’Ariano, G.M., Perinotti, P.: Efficient universal programmable quantum measure-
ments. Phys. Rev. Lett. 94, 090401 (2005)
7. Dzyaloshinskii, I.: A thermodynamic theory of “weak” ferromagnetism of antifer-
romagnetics. J. Phys. Chem. Solids 4(4), 241–255 (1958)
Quantum Coherence Measures for Quantum Switch 141
8. Ekert, A.K., Moura Alves, C., Oi, D.K.L.: Direct estimations of linear and nonlinear
functionals of a quantum state. Phys. Rev. Lett. 88, 217901 (2002)
9. Gawron, P., Klamka, J., Winiarczyk, R.: Noise effects in the quantum search algo-
rithm from the viewpoint of computational complexity. Int. J. Appl. Math. Com-
put. Sci. 22(2), 493–499 (2012)
10. Girolami, D.: Observable measure of quantum coherence in finite dimensional sys-
tems. Phys. Rev. Lett. 113, 170401 (2014)
11. Goścień, R., Walkowiak, K.: A column generation technique for routing and spec-
trum allocation in cloud-ready survivable elastic optical networks. Int. J. Appl.
Math. Comput. Sci. 27(3), 591–603 (2017)
12. Imre, S., Gyongyosi, L.: Advanced Quantum Communications: An Engineering
Approach. Wiley, Hoboken (2012)
13. Li, Y.H., Zhou, Z.Y., Xu, Z.H., Xu, L.X., Shi, B.S., Guo, G.C.: Multiplexed entan-
gled photon sources for all fiber quantum networks. Phys. Rev. A 94, 043810 (2016)
14. Lloyd, S.: Any nonlinear gate, with linear gates, suffices for computation. Phys.
Lett. A 167(3), 255–260 (1992)
15. Jozsa, R.: A stronger no-cloning theorem, arXiv: preprint quant-ph/0204153v2
(2002)
16. Markowski, M.: Heuristic algorithms for joint optimization of unicast and anycast
traffic in elastic optical network-based large-scale computing systems. Int. J. Appl.
Math. Comput. Sci. 27(3), 605–622 (2017)
17. Mehic, M., Fazio, P., Voznak, M., Chromy, E.: Toward designing a quantum key
distribution network simulation model. Adv. Electr. Electron. Eng. 14(4), 413–420
(2016)
18. Milburn, G.J.: Quantum optical Fredkin gate. Phys. Rev. Lett. 62(18), 2124–2127
(1989)
19. Moriya, T.: Anisotropic superexchange interaction and weak ferromagnetism. Phys.
Rev. 120(1), 91–98 (1960)
20. Ratan, R., Shukla, M.K., Oruc, A.Y. : Quantum switching networks with clas-
sical routing. In: 41st Annual Conference on Information Sciences and Systems,
Baltimore, pp. 789–793 (2007)
21. Sawerwain, M., Wiśniewska, J.: Quantum circuit for estimation of quantum coher-
ence during work of quantum switch, in preparation
22. Sawerwain, M., Wiśniewska, J.: The entanglement level and the detection of quan-
tum data transfer correctness in short qutrit spin chains. Wirel. Pers. Commun.
96(4), 5437–5452 (2017)
23. Wegrzyn,
S., Bugajski, S., Klamka, J.: Foundation of quantum computing. Part 1
Archiwum Informatyki Teoretycznej i Stosowanej 1(2), 97–142 (2001)
24. Wegrzyn,
S., Bugajski, S., Klamka, J.: Foundation of quantum computing. Part 2
Archiwum Informatyki Teoretycznej i Stosowanej 14(2), 93–106 (2002)
25. van Meter, R.: Quantum Networking. Wiley, Hoboken (2014)
26. Wigner, E.P., Yanase, M.M.: Information contents of distributions. Proc. Natl.
Acad. Sci. USA 49(6), 910–918 (1963)
27. Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299,
802–803 (1982)
Performance Evaluation of Web Sites
Using HTTP/1.1 and HTTP/2
1 Introduction
When designing a website, one can influence how the site will be processed on
the target user’s side through a properly designed structure of HTML, CSS or
JavaScript code, as well as by the proper preparation of the resources that make
up the site in terms of structure as well as location. As a result, an important
aspect of website’s design is its performance.
When designing an efficient website, i.e. one that will be quickly processed
and displayed on the client’s side, it is possible to influence its reception, the
general feeling of smoothness and convenience of using the website. A number
of techniques, or proven methods are helpful here that in a universal way fit
into the concept of shortening the loading times. They are based, inter alia,
on the knowledge of the principles of the HTTP protocol, its limitations and
disadvantages [1].
Currently, however, the use of some techniques is questionable in view of the
increasing share of the new version of the HTTP – HTTP/2 protocol, which
offers improvements resulting from the growing demand for efficient websites [2].
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 142–157, 2018.
https://doi.org/10.1007/978-3-319-92459-5_12
Performance Evaluation of Web Sites Using HTTP/1.1 and HTTP/2 143
Due to the lack of a full understanding of the impact of the techniques used
so far on HTTP/2 performance, there appeared a need to analyse the classic
rules developed for the HTTP/1.1 protocol, in terms of their further relevance
in view of the prospect of a significant increase in the new version of the protocol.
2 Related Works
Liu et al. [3] conducted a study of the effectiveness of the HTTP/2 protocol
in terms of displaying a site on a mobile device. Using copies of the 200 most
popular sites according to the Alexa rankings on the local server, they conducted
a comparative analysis of HTTPS and HTTP/2 protocols for the impact of
factors such as Round-Trip Time (RTT), bandwidth, packet loss rate and size of
resources. The research showed the advantage of the HTTP/2 protocol, among
others in situations when there was a need to download many smaller objects
and the low rate of packet loss. The authors also noted the possible undesirable
effects associated with the use of good practices derived from the previous version
of the protocol, such as domain sharding, concatenation or inlining.
Corbel et al. [4] examined Page Load Time (PLT) using an unencrypted
version of the HTTP/1.1 and HTTP/2 protocols for the prepared “average site”,
consisting of various types of resources stored on several different domains. The
measurement scenarios assumed several separate delay profiles and the loss rate
of the packet. The analysis showed the advantage of the HTTP/2 protocol in
each scenario. The authors stressed the need to extend the research with the
new mechanisms available in the HTTP/2 protocol and scenarios taking into
account the size of the TCP window at the client’s.
de Saxc’e et al. [5] analysed the impact of the HTTP/1.1 protocol change
on the HTTP/2 protocol in the context of web site load performance. The 20
most popular sites according to the Alexa rankings were used for the purposes
of the research and they were adapted to the needs of the local measurement
environment and the environment similar to network realities (a dedicated HTTP
server located outside the local network). PLT was determined as a measure of
the loading performance of the websites. Measuring scenarios took into account
various pre-defined network conditions (including ADSL and 3G). The research
consisted of a number of scenarios using the new HTTP/2 protocol: compression,
multiplexing, server push and prioritization. As a result of the research, the
authors found the advantage of the new version of the protocol. They noted,
however, worse performance in 3G network conditions (significant vulnerability
to packet loss).
Varvello et al. [6] developed a measurement platform to track the use of
the HTTP/2 protocol among the million most popular websites according to
the Alexa ranking. Their research showed, inter alia, that the owners of most
sites that adopted the new version of the protocol retained techniques developed
for the purposes of the HTTP/1.1 protocol. Among those inlining or domain
sharding can be mentioned. About 80% of registered sites supporting the new
version of the protocol obtained better PLT. The best results were recorded for
3G networks in Europe.
144 M. Druzgala and Z. Nowak
Zarifis et al. [7] performed PLT analysis after switching to the new version of
the HTTP protocol. For research, they used data from the Resource Timing API
for approximately 280,000 visits by Akamai CDN users. Based on the modelling
of the HTTP/2 server behaviour, using the collected visits measurements for
Akamai servers (HTTP/1.1), they tried to analyse the theoretical decreases in
PLT times. The authors showed that theoretically, the use of new techniques
offered by HTTP/2 (server push, prioritization) would have a positive impact
on the final loading times of websites.
Stepniak and Nowak [8] examined the impact of the new version of the pro-
tocol on web applications of the Single Page type (SPA) using different types
of techniques to accelerate the loading of the site (concatenation, compression,
minification). In the context of the HTTP/2 protocol use, they also examined
the capabilities of the server push technique. The research showed a significant
advantage of the HTTP/2 protocol in the event of having to download many
smaller resources. The only aspect that had a negative impact on the loading
times of the site was the use of the server push mechanism.
Rosen et al. [9] analysed the potential benefits of using the server push tech-
nique available for the new version of HTTP from the mobile clients’ perspective.
Their research involved 50 sites from among the top 500 of the most popular
according to Alexa’s ranking, adapted to the local conditions. As a result, they
found measurable benefits stemming from the use of the new technique. Still they
pointed to reduced efficiency of the technique for sites that use multiple servers
to store resources, and in the case of a scenario involving a mobile client with a
device inferior in performance, which may negatively affect the final processing
time of the site (longer download times of the HTML file).
Kim et al. [10] carried out research on the efficiency of loading sites that
use multiple domains to store resources in the context of the HTTP/2 protocol.
They performed PLT measurements for typical Korean sites (which usually use
multiple domains in their structure), copied to the local machine to be analysed.
To construct the research environment, they used a server natively supporting
the HTTP/2 protocol. The research showed increased PLT in all the adopted
scenarios.
Seemakhupt and Piromsopa [11] analyzed scenarios in which the use of stream
multiplexing using the HTTP/2 protocol brings the greatest benefits and may
lead to a deterioration in site loading efficiency. They adopted two scenarios in
the research. In the first one, the client individually queried the HTTP server
for the resources of the site. In the other, an additional client was burdening the
link. The results showed that the use of the HTTP/2 protocol using multiplexing
performs better under low load conditions. However, under load conditions, the
new protocol version performs worse than the HTTP/1.1 protocol.
Prokopiuk and Nowak [12] examined the impact of the new version of HTTP
on the performance of the site from the perspective of the end user (User-
Perceived Web Application Performance). They used WebPagetest tool to mea-
sure the performance of the examined websites, installed on the local client
machine. The tool allowed them to acquire a number of measurements that are
Performance Evaluation of Web Sites Using HTTP/1.1 and HTTP/2 145
relevant to the user displaying the site. Network conditions were simulated by
the authors with the help of the Dummynet tool. As a result of the research, the
authors found a beneficial effect of the server push mechanism in almost every
scenario. The greatest benefit came from attaching CSS files and a background
image.
With the introduction of the new version of the protocol, some of the techniques
used for the HTTP/1.1 protocol no longer bring time benefits or – even worse –
negatively affect the total loading times of sites. This section presents problems
resulting from preserving the old solutions after switching to the new version of
the HTTP protocol and suggestions of the new approaches when designing sites
using the HTTP/2 protocol [1,2].
With the development of websites, the need for parallel processing of resources
increased. In the context of the HTTP/1.1 protocol, this meant using additional
TCP connections, even within the same domain. Due to the overhead gener-
ated by additional connections, browser developers established internal limits of
maximum connections within the domain in order to eliminate the risk of pos-
sible overloads of the system. For example, for Google Chrome, the maximum
connection limit is 6. In many cases, the connection limits were too low, which
motivated the creation of a new technique - domain sharding.
The idea of the technique is simple. In order to “cheat” the browser, some
resources are shown in another, additionally created domain, which in fact points
to the same server. Thanks to the use of the technique, it is possible to exceed
the set limits and increase the parallel processing of resources in a browser-
independent manner.
Formulating the Problem. From the perspective of the new mechanism and
message exchange structure for the HTTP/2 protocol, technical improvements
cease to be improvements. The HTTP/2 protocol natively supports full paral-
lelization and multiplexing of messages within a single TCP connection.
The use of domain sharding for the HTTP/2 protocol generates overhead
associated with, among other things, the creation of new TCP connections, while
there is no need to do so. It is not possible either to use the full potential
of mechanisms for prioritizing and controlling the flow of messages due to the
additional TCP connections created. To some extent, the header compression
mechanism also suffers, as it must operate in this situation separately for each
connection, introducing a certain degree of redundancy.
146 M. Druzgala and Z. Nowak
In 2007, the total processing time of the site was only 10÷20%, which included
the time to download the HTML document itself [13]. The remaining time was
devoted to the processing of additional resources appearing as references in the
HTML structure. Due to the growing number of HTTP requests, the overhead
associated with performing an increased number of resource queries became more
and more important from the performance perspective.
A technique of concatenation, i.e. joining resources of one kind in order to
reduce the number of queries, came to the rescue. Merged resources that have
been downloaded must be logically processed to reach their condition from before
the connection. For merged images (sprites) CSS styles are created that “cut”
the one that is needed on the site. There is no need for additional steps for CSS
and JavaScript resources.
Merged resources are readable by the browser in this form. The use of the con-
catenation technique is able to reduce the loading times of sites by up to 50% [13].
Formulating the Problem. In the context of the HTTP/1.1 protocol, the use
of concatenation is beneficial by reducing the problem of simultaneous processing
of many smaller resources. The HTTP/2 protocol reveals its full potential in the
scenario of high resource granulation. The mechanism of multiplexing streams
within a single TCP connection is able to handle single resources in the case of
parallel processing.
The use of the concatenation technique in the context of the HTTP/2 proto-
col creates the problem of a longer wait for a specific resource due to its connec-
tion with others. Another issue is cache management. The smallest change in the
merged resource forces makes it necessary to reprocess the whole (redundancy
of data transfer).
3.4 Minification
[17]. The project was modified to support multiple ports, implementation of the
server push mechanism for explicitly defined resources that were part of the
selected site and implementation of the mechanism for capturing and recording
measurement results.
In order to examine the performance of sites using each protocol individually,
a solution was chosen involving the selection of the protocol version by using
appropriately assigned ports:
Dummynet [18] was used to simulate the established profiles. It is a tool that
allows one to emulate specific network conditions in real time. Originally created
for FreeBSD, it is now also available for Linux, OSX and Windows distributions.
The tool uses ipfw firewall software. Ipfw allows communicating with Dummynet
via the command line and setting traffic restrictions that ultimately are ipfw
firewall rules. Installed as a service on a network card in Windows, it is able to
capture traffic and subject it to various modifications, including bandwidth and
delays.
In order to meet the research assumptions and to ensure precise research results,
a dedicated simulation environment was developed (Fig. 1).
150 M. Druzgala and Z. Nowak
The server software was installed on the computer along with the sites to be
examined. On its network card, the Dummynet and ipfw drivers were installed
and, as a result, it was possible to properly manipulate network conditions from
the level of the desktop console.
The HTTP client was based on the Dell Latitude E6440 laptop with the
following parameters:
On the HTTP client laptop, Google Chrome and Mozilla Firefox were
installed. In both browsers, developer tools and private mode were launched
and activated.
The OnePlus One smartphone was used to examine the mobile version of
Google Chrome using the following parameters:
Concatenation. The main part of the page under investigation for the tech-
nique of concatenation were six resources in the form of images in the PNG
format. As a raw state, six separate resources defined in the HTML code were
determined for the purpose of rendering six images, which involved their com-
plete separation. As a result of such defining the structure of the site, it was
necessary to download each resource separately.
After applying the concatenation technique, the resources were merged into
one larger resource, which was later logically separated on the client’s side into
individual resources using the CSS styles attached to the HTML structure.
Due to the concatenation technique, only one graphic resource was referenced,
and then its logical “cutting” into individual images took place. As a result, the
HTML object code rendered the images by appropriate references to the CSS
classes.
Inlining. Six resources in the form of images in PNG format were reused for
the purposes of the inlining technique. Also, the “raw” state was determined by
the need to download all other additional resources.
Following the application the inlining technique, resources became an integral
part of the HTML document. References to additional resources were replaced
with references to resources encoded directly in the document using Base64
encoding.
With the “raw” version of the site, a solution utilizing the server push mech-
anism, available in the new version of the protocol, was also analysed. Due to the
architecture of the measurement system, an additional version of the site was
created for the purpose of proper site selection on the backend side. On the side
of the HTML document, the structure did not change with respect to the “raw”
version. Additional graphic resources still had to be downloaded. The difference
was due to the use of the server push mechanism on the backend side using the
explicit resource selection.
Domain Sharding. A separate site was prepared for the domain shard-
ing research purposes. It contained in its body references to twenty graphics
resources that constituted components of a certain graphics composition.
152 M. Druzgala and Z. Nowak
4.4 Methodology
Every possible scenario of the user’s visit was subject to a separate measurement
series. The scenario should be understood as a set of the following factors:
– network profile,
– application of the techniques (or the lack thereof),
– protocol version,
– type of browser (along with the type of HTTP client device).
After cleaning the collected data, each case was analysed in detail. His-
tograms of purified data were examined to establish the distribution, which
directly affected the decision regarding the adopted measurements.
As a result of the analysis, it was decided that the median values from the
measurement series would be used as the measure of central tendency for the
representation of the results of individual scenarios. The use of median is justified
due to the fact that most of the histograms of the measurement series for the
determined scenarios had a skewed distribution.
If the majority of users of the site are desktop users with a constant Internet
connection using the Mozilla Firefox browser, it is recommended to continue
using the concatenation technique (17.03% gain PLT for the “raw” version and
21.98% gain for the “active” version).
Otherwise, what is meant by a larger share of mobile clients or using the
Google Chrome browser, it is discouraged to continue using the technique due to
154 M. Druzgala and Z. Nowak
better PLT results without using the technique in the context of the new version
of the protocol (higher gain of the “raw” version compared to the “active” version
by up to 6.15 pp).
Inlining. In the inlining technique, the current trends may also influence the
decision regarding its further use (Table 2).
Minification. The situation with the use of minification is clear (Table 4). It
is strongly recommended to continue using the technique to reduce the size of
resources, which in each scenario yields a positive result in the context of PLT
(gain increase of 79.52 pp compared to the “raw” version for the DSL profile
and 143.97 pp in relation to the “raw” version for the 3G profile).
The domain sharding technique proved to be useful only for a 3G user profile
using the Google Chrome browser. Any other scenario indicated resignation from
the technique as a beneficial step to increase efficiency.
The minification confirmed its “evergreen solution” title. The use of the tech-
nique did not lose its meaning after changing the protocol version to HTTP/2.
To sum up, when planning changes to the site design motivated by the use
of the new version of the HTTP protocol, it is necessary to consider the nature
of the site and who its recipient is, as it can have a significant impact on the
final decision.
In the course of designing the simulation environment, the adoption of find-
ings regarding the method of measuring size, the characteristics of visits, the
interpretation of data, a number of aspects were found that can be subjected to
improvements or changes. After their application, it shall be possible to conduct
even more valuable substantive research and to draw new conclusions from them.
One of the aspects is to move the server environment to the cloud to examine
real conditions. It would be necessary to conduct a larger number of measure-
ments in the longer term, due to the fluctuations associated with the real network
environment.
Another aspect is to examine a greater number of classic techniques that
reveal their properties and benefits only in real network conditions.
The final suggestion for further work would be to further broaden the sce-
narios with new client profiles (browsers, devices) as well as network profiles (for
example 4G, LTE and the like).
References
1. Grigorik, I.: High Performance Browser Networking. What Every Web Devel-
oper Should Know About Networking and Web Performance. O’Reilly Media,
Sebastopol (2013)
2. Grigorik, I.: HTTP/2: A New Excerpt from High Performance Browser Networking.
O’Reilly Media, Sebastopol (2015)
3. Liu, Y., Liu, X., Huang, G.: Can HTTP/2 really help web performance on smart-
phones? In: 2016 IEEE International Conference on Services Computing (2016)
4. Corbel, R., Stephan, E., Omnes, N.: HTTP/1.1 pipelining vs HTTP2 in-the-clear:
performance comparison. In: 3th International Conference on New Technologies
for Distributed Systems (2016)
5. de Saxcé, H., Oprescu, I., Chen, Y.: Is HTTP/2 Really Faster Than HTTP/1.1?
In: 18th IEEE Global Internet Symposium (2015)
6. Varvello, M., Schomp, K., Naylor, D., Blackburn, J., Finamore, A., Papagiannaki,
K.: Is the Web HTTP/2 Yet? In: 17th International Conference Of Passive and
Active Measurement, PAM 2016 (2016)
7. Zarifis, K., Holland, M., Jain, M., Katz-Bassett, E., Govindan, R.: Modeling
HTTP/2 speed from HTTP/1 traces. In: 17th International Conferenceof Passive
and Active Measurement, PAM 2016 (2016)
Performance Evaluation of Web Sites Using HTTP/1.1 and HTTP/2 157
8. Stepniak,
W., Nowak, Z.: Performance analysis of SPA web systems. In: Borzemski,
L., Grzech, A., Światek,
J., Wilimowska, Z. (eds.) Information Systems Architec-
ture and Technology: Proceedings of 37th International Conference on Information
Systems Architecture and Technology – ISAT 2016 – Part I. AISC, vol. 521, pp.
235–247. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-46583-8 19
9. Rosen, S., Han, B., Hao, S., Morley Mao, Z., Qian, F.: Push or request: an inves-
tigation of HTTP/2 server push for improving mobile performance. In: The 26th
International Conference (2017)
10. Kim, H., Lee, J., Park, I., Kim, H., Yi, D., Hur, T.: The upcoming new stan-
dard HTTP/2 and its impact on multi-domain websites. In: Asia-Pacific Network
Operations and Management Symposium (2015)
11. Seemakhupt, K., Piromsopa, K.: When should we use HTTP2 multiplexed stream?
In: 13th International Joint Conference on Computer Science and Software Engi-
neering (2016)
12. Prokopiuk, J., Nowak, Z.: The influence of HTTP/2 on user-perceived Web appli-
cation performance. Studia informatica, vol. 38, no. 3(132). Silesian University of
Technology Press, Gliwice (2017)
13. Souders, S.: High Performance Web Sites. Essential Knowledge for Front-End Engi-
neers. O’Reilly Media, Sebastopol (2007)
14. Ndegwa, A.: What is Page Load Time? MaxCDN One (2016). https://www.
maxcdn.com/one/visual-glossary/page-load-time/
15. Dutton, S.: Measuring page load speed with navigation timing, blog HTML5 rocks
(2011). https://www.html5rocks.com/en/tutorials/webperformance/basics/
16. Grigorik, I.: Measuring network performance with resource timing API, blog
Google developers (2013). https://developers.googleblog.com/2013/12/measuring-
network-performance-with.html
17. Trosien, O.: HTTP2 w/ Spring Boot+Jetty. GitHub (2017). https://github.com/
otrosien/demo-http2
18. Rizzo, L.: The Dummynet Project. University of Pisa (2015). http://info.iet.unipi.
it/∼luigi/dummynet/
Teleinformatics and
Telecommunications
Modified OMP Algorithm
for Compressible Channel Impulse
Response Estimation
1 Introduction
Wireless propagation channel consists of paths that carry signals from transmit-
ter to receiver. Many experimental measurements of the wireless channels show
that the vast majority of signal energy is delivered to the receiver only over a
few isolated propagation paths, which are usually distant from each other in
time [1,2]. This phenomenon can manifest afterwards in the recovered Chan-
nel Impulse Response (CIR) as a sparsity feature. The wider spectrum band-
width of the transmitted signals, the more sparse pattern of the channel impulse
response can be detected in the receiver. In case of the strict sparsity (a frequent
assumption in many simulation analysis [3–6]) only several CIR taps are con-
sidered nonzero, making the Compressive Sensing (CS) processing effective in
their estimation. For example, the greedy methods, such as Orthogonal Matching
c Springer International Publishing AG, part of Springer Nature 2018
P. Gaj et al. (Eds.): CN 2018, CCIS 860, pp. 161–170, 2018.
https://doi.org/10.1007/978-3-319-92459-5_13
162 G. Dziwoki et al.
Pursuit (OMP) [7] and Compressive Sampling Matching Pursuit (CoSaMP) [8]
(both methods with their many modifications), are the popular CS algorithms
that implementation is analyzed in many applications [9]. They work iteratively,
making selection of a single impulse response element (or more in case of the
CoSaMP) in each iteration step. Next, within the same iteration, the selected
impulse response time index is merged with the ones found previously and all
the taps amplitude that correspond to them are estimated by the Least Square
(LS) algorithm simultaneously.
The above assumption about the strict CIR sparsity is quite uncertain in
reality. A band-limited transmission due to the use of electronic filters in the
transceivers, and some synchronization issues disperse the transmitted energy
across the almost all taps of the impulse response. Consequently, many medium-
and low-amplitude elements beside a few main ones appear in CIR. Such a signal
structure, which represents the impulse response, is called compressible according
to the compressed sensing terminology [10].
The channel compressibility reduces efficiency of the classic CS methods.
The positions of nonzero elements, especially those with low amplitude can be
incorrectly determined due to the noise presence and the insufficient number of
measurement samples. Additionally, including a poor effect of the noise averaging
on the CIR amplitude estimation, a final quality of the channel reconstruction
may decrease.
The paper proposes a modification of the OMP method in case of compress-
ible CIR reconstruction. The COST-207 TU6 channel model [1] was picked as
a test environment in the simulation analysis. Channel estimation performance
was evaluated in terms of Minimum Square Error (MSE), whereas transmission
quality as Bit Error Rate (BER). The results obtained by the proposed solution
were compared with the ones by other methods based on the OMP. Efficiency of
the proposed modification in case of strict impulse response sparsity was tested
as well.
The reminder of this paper is organized as follows. A comparison between
sparse and compressible channel impulse responses with an explanation of the
source of the compressibility is presented in Sect. 2. Section 3 depicts the CS
processing with OMP method in relation to channel identification problem with
a description of the proposed modification. Section 4 presents a simulation envi-
ronment and the performance analysis of the proposed solution.
Fig. 1. Sparse channel impulse response (a) vs. compressible channel impulse
response (b)
where a complex function g(t) represents the joint impulse response of the trans-
mitter and receiver linear processing blocks and al denotes complex gain of the
lth propagation path that is delayed by time τl . L is the total number of the
resolvable paths. Because the receiver samples incoming signal with period TS ,
it is more convenient for processing purposes to present the CIR in discrete-time
domain (hk = h(kTS )) using a vector notation:
z = X h + v, (3)
z = X ĥ, (4)
where j is the iteration number and ε(j) is the residual error in the j-th iteration
that is updated according to the formula:
(j)
ε(j) = z − X ĥ . (6)
In every iteration loop the effective size of X is only M × j with M > j because
(j)
K −j elements in the ĥ are zero. In that case the Moore-Penrose pseudoinverse
of X(M ×j) can be determined and the LS estimation of channel impulse response
is:
(j) −1 H
ĥ(j×1) = (X(M
H
×j) X(M ×j) ) X(M ×j) z (7)
(j) (j)
where ĥ(j×1) is a concise representation of ĥ , i.e. only nonzero values of the
estimated channel impulse response are represented in the vector.
The OMP procedure stops after predefined number of iterations (if the spar-
sity S is known) or when a stopping condition is met. The value of ĥ in the
last iteration is the valid estimate of the channel impulse response, which can
be used for further signal processing in the receiver. Detailed description of the
OMP processing steps can be found in [7].
Modied OMP Algorithm for Compressible Channel 165
⎧
⎨ j > Smax , any ε(j) 22 , ε(j) − ε(j−1) 22
STOP if ε < aM σ ,
(j) 2 2
any ε(j) − ε(j−1) 22 (10)
⎩ (j) 2 (j−1) 2
ε −ε 2 < bσ , aM σ 2 ≤ ε(j) 22 < caM σ 2
2
where a, b and c are some scaling factors which should be chosen according to
specific conditions of the recovered channel, j is the current iteration step and
σ 2 is noise power.
The above-mentioned control mechanism works fine for sparse channels (sig-
nals) [13]. But in case of compressible ones, there is a danger that the iterative
procedure can stop too early (see a discussion of the simulation results for details
in the next section) before some crucial taps with medium and low amplitude
are recovered. They are necessary for preserving transmission quality. Their posi-
tions are clearly indicated by the channel compressibility pattern which is related
to g(t). Unfortunately, the classic OMP procedure does not use this knowledge
to control how to select the time index of the next element in the recovered
channel impulse response.
The aim of the paper is to propose a solution that improves quality of CIR
reconstruction by using the compressibility pattern as an additional guideline
to control the OMP algorithm. No information about the shape of g(t) is pro-
vided. The proposed modification combines the two-threshold stopping criterion
166 G. Dziwoki et al.
approach with a block CS processing idea [14]. Two phases can be distinguished
in it. Initially after the start of the estimation procedure, the consecutive CIR
elements are recovered according to the classic OMP. This coarse recovery stage
is valid until the energy of the residual error falls below the predefined threshold.
When the condition ||ε(j) ||22 < caM σ 2 is met, the fine stage of reconstruction
begins. From that moment, new elements of the reconstructed impulse response
are selected in each next iteration step using an additional selection rule besides
the classical one. The OMP algorithm stops ultimately when ||ε(j) ||22 < aM σ 2
or ||ε(j) − ε(j−1) ||22 < bσ 2 .
The detailed description of the iteration step in the fine stage is as follows:
– find a new time index of the CIR element according to Eq. (5);
– supplement the set of the time indices that have been already found in the
current