ICACT20210168 Slide.20
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Thank you for your listening.
|
|
ICACT20210168 Slide.19
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
On our framework of locating high-loss links in OpenFlow-based networks, we have proposed a new route scheme for probing multicast packets.
The BBT route scheme can reduce the number of accesses to switches while keeping a high accuracy with a small number of probe packets.
A benefit of the BBT with multiple measurement host to the previous BBT with a single measurement host, by reducing the lengths of terminal paths while keeping the number of terminal paths, was shown through simulation.
However, in real networks, the possible locations of measurement hosts may be limited, and an additional cost should also be considered.
How to implement multiple measurement hosts at arbitrary locations in a cost-efficient manner remains as future work.
|
|
ICACT20210168 Slide.18
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Figure 12 shows the number of the required accesses from OpenFlow controller to OpenFlow switches until the high-loss link location process ends in the case of 4 high-loss links, depending on the number of probe packets.
Note that the results of the location process are not always correct in case that the number of probe packets is less than about 220 for all schemes as shown in Figure 11.
A small number of probe packets needs a more number of accesses probably due to inaccurately measured packet loss rates.
Furthermore, a route scheme with longer terminal paths likely needs more accesses.
This is because an accumulated loss rate over multiple links in a long segment will accidentally exceed the threshold even if the segment does not include any high-loss link, which leads the OpenFlow controller to mistakenly and unnecessarily seek high-loss links in a wrong segment.
Hence our proposed BBT with multiple measurement hosts scheme with shorter terminal paths can reduce the required accesses.
The comparison between single measurement host cases (c,d,e) and multiple measurement hosts cases (f,g,h) in both Figure suggests that the use of multiple MHs with consideration on the locations and their node degrees benefits to realize an acceptably-high measurement accuracy with less number of probe packets and required accesses to OpenFlow switches.
This is because the use of multiple measurement hosts can control the length of terminal paths more flexibly compared with the use of only a single measurement host, although the use of multiple measurement hosts involves additional operational costs.
|
|
ICACT20210168 Slide.17
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Figure 11 shows the measurement accuracy depending on the number of probe packets.
The measurement accuracy is the ratio of the number of measurements in which all 4 high-loss links are correctly located to the total number of measurements (10,000 in our setting).
We see that a route scheme with longer terminal paths needs a larger number of probe packets to operate accurately.
This is because the losses at upstream links of the long path can degrade the loss measurement at downstream links.
If a small number of probe packets arrives at the upper port of a normal link, its measured packet loss rate can exceed the threshold even by a very small number of losses accidentally happening.
On the other hand, a small number of probe packets may result in the measured packet loss rate of a high-loss link less than the threshold.
|
|
ICACT20210168 Slide.16
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
To evaluate the performance of the proposed route schemes, we investigate the number of required accesses to OpenFlow switches and the measurement accuracy depending on the number of probe packets through simulation.
We use the topology in Figure 9a, and compare six route schemes as Figure 9c-h.
|
|
ICACT20210168 Slide.15
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
To have the light load on the control-plane, we use an appropriate sequential order of access to OpenFlow switches.
First, the OpenFlow controller calculates the packet loss rate of each of the terminal paths with the information at the root port and leaf ports.
if the packet loss rate of a terminal path is less than the threshold value h, this terminal path does not include a high-loss link.
Otherwise, this terminal path is likely to include one or more high-loss links. The correlation among terminal paths in terms of the degree of packet loss can be used to narrow the search scope.
If a terminal path is high-loss but all other terminal paths sharing at least one link with the high-loss terminal path are not, the high-loss links are located within a segment between the leaf port and the nearest branch port of the single high-loss terminal path. The dashed line on the left part in Figure 10 illustrates an example of this case. Then, the binary search algorithm is used to locate all high-loss links by accessing appropriate ports.
On the other hand, if there are multiple high-loss terminal paths, the next port to access is the most commonly port shared by those paths. An example of this case is shown in the right part of Figure 10.
|
|
ICACT20210168 Slide.14
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
As shown in the BBT scheme, we can build one or two backbone paths from a measurement node with a degree of two.
By using more than one measurement nodes, a long Eulerian cycle can be divided into multiple short backbone paths.
A possible option to reduce the length of backbone paths is to place a measurement node at a node with a higher degree.
In general, the degree of measurement node determines the maximum number of backbone paths from this node.
Therefore, by selecting measurement nodes with a degree more than two, we can construct more backbone paths.
If a measurement host can be placed at a high-degree node, we can get the benefit equivalent to using multiple measurement hosts connecting to a low-degree node, that is we can reduce the number of measurement hosts while keeping the number and length of terminal paths.
See the examples in Figure 9e, f, and Figure 9g, h.
|
|
ICACT20210168 Slide.13
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Finally, we integrate additional paths of temporally omitted links into the route tree.
From the common node of the route tree and an omitted path,
this path is integrated into the reverse path or added to the backbone path as an individual branch path.
For an example in Figure 8a, the omitted path B-G-B is integrated into the reverse path C-B-A at Node B and this reverse path becomes the integrated reverse path C-B-G-B-A, see the left branch in Figure 8c.
The omitted path can be added to the backbone path as an individual branch path,
see the right branch, the path C-H-C in Figure 8c.
|
|
ICACT20210168 Slide.12
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
After building the backbone paths, we divide each backbone path into multiple backbone segments with almost the same length.
At the end node of each segment, called the branch node, the reverse direction segment of the route on the backbone path is added as an extension of the route toward the measurement node, called the reverse path.
This is necessary because both directions of each full-duplex link should be traversed by a measurement path.
Each reverse path has the same length with its backbone segment but the opposite direction.
|
|
ICACT20210168 Slide.11
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
After the omitting step, each node in the network has an even degree.
We generate a backbone cycle by using the Eulerian cycle algorithm to cover all remaining undirected links.
Here, there are two options:
BBT T1 has a full Eulerian cycle as the backbone path, see the bold lines in Figure 7.
BBT T2 has two backbone paths that are two reversed halves of the Eulerian cycle.
|
|
ICACT20210168 Slide.10
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Since an Eulerian cycle exists if and only if the graph consists of only even-degree vertices, first we need to remove all links incident to odd-degree vertices (nodes) temporarily, called ``omitted links''.
The general idea of processing odd degree nodes is to omit the links between their couples.
In this way, the degrees of these nodes become zero or even. Note that the number of odd degree nodes is always even. Omitting links should try to keep the network connected and Minimize the number of omitted links.
|
|
ICACT20210168 Slide.09
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
To avoid a concentration of probe packets at links near the measurement host, especially in large networks, each probe packet should traverse each link one and only once. The measurement route avoids a long terminal path because in a long terminal path, when a number of links on a path are not actually lossy but with a light loss rate, an accumulated loss rate over those links will cause a wrong decision to narrow a segment that likely includes actual lossy links, resulting in an unnecessary increase of accesses to OpenFlow switches.
Furthermore, a long terminal path requires a large number of probe packets to operate accurately because an incidental reduction of probe packets in upstream, e.g., due to heavy packet losses at a failure link, will degrade the reliability of measurement results for links in its downstream.
At the same time, the measurement route should keep a small number of terminal paths, i.e., a small number of leaf ports needed to initially access, resulting in a small number of accesses to OpenFlow switches to locate all high-loss links.
Therefore, a newly route scheme called the backbone-and-branch tree route scheme (BBT) is proposed and its flowchart is illustrated in Figure 5.
In the BBT scheme, the Eulerian cycle algorithm is applied to the original undirected graph.
|
|
ICACT20210168 Slide.08
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Our framework is for OpenFlow-based full-duplex networks consisting of the OpenFlow controller and OpenFlow switches,
with the measurement host that sends a series of multicast probe packets traversing all links in the network. A measurement host is directly connected to an OpenFlow switch (called ``measurement node‘’). The input port of the measurement node connecting the measurement host is called ``root port''.
The process begins when the measurement host sends a measurement request to the OpenFlow controller. Then, the OpenFlow controller obtains network topology, calculates probe packet routes, and installs them into OpenFlow switches.
After that, the measurement host starts sending the probe packets.
Each probe packet (or a copy of it as multicasting) starting from the root port travels through each link once and only once (in each direction of a full-duplex link separately) and is discarded at a leaf port (an input port of the last OpenFlow switch of the measurement flow).
A measurement path from the root port to a leaf port is called ``terminal path''. The number of probe packets arriving at an individual input port on each OpenFlow switch is passively recorded as flow-stats at each OpenFlow switch and then, if needed, is collected by the OpenFlow controller.
Finally, the OpenFlow controller calculates the packet loss rate to detect a high-loss link or a high-loss segment. This process is recursively performed until locating all high-loss links.
|
|
ICACT20210168 Slide.07
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Based on those existing work, we propose a new framework of active measurement in cooperation with passive measurement with light traffic load on the data-plane by a multicast route for probe packets, and a light load on the control-plane by an appropriate sequential order of access to OpenFlow switches.
|
|
ICACT20210168 Slide.06
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
In general, monitoring in SDN is classified into two kinds: Passive and Active methods.
Passive methods query the data statistic information from OFSs. This is in-network traffic. Therefore, there is no extra traffic in passive methods.
However, these methods rely on in-network data, these cannot measure when data traffic is less.
Additionally, the accuracy measurement depends on the frequency of querying. It can make extra traffic on the control plane.
And passive methods cannot use on virtual links.
On the other hand, Active methods send and receive probe packets then based on information of these probe packets to monitor a network.
So, these can actively measurement anytime and at any location on the network. And these can use on virtual links.
However, these make extra traffic on the data plane because of probing packets.
|
|
ICACT20210168 Slide.05
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
For example, by getting the statistic information about the number of received packets at OpenFlow switches, the OpenFlow controller can detect which link is a high loss link.
|
|
ICACT20210168 Slide.04
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
OpenFlow is a standard protocol used widely in SDN. It is used for communication between OpenFlow switches and controllers.
An OpenFlow switch contains a flow table included a set of flow entries. Each flow table entry contains main components: match fields, action, statistical counter. Match fields are used to match packet information: MAC address, IP address, etc. Incoming packets are matched, and the corresponding action will be taken. The statistical count will be incremented for all successful matches of flow entry with the arriving packet.
OpenFlow switches (OFS) can distinguish the statistic information of each flow (flow statistic).
The flow statistic can be collected by the controller to monitor the network traffic.
|
|
ICACT20210168 Slide.03
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Software-Defined Networking (SDN) is a network architecture that deploys the control plane and data plane to become more flexible and simpler to design, configure, operate and monitor.
The deployment of services and features in the network is executed by programming on controllers.
On a data-plane, switches forward packets based on rules from controllers.
|
|
ICACT20210168 Slide.02
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Our presentation includes 5 sections. The first section is an introduction about measurement in Software Defined Networking and OpenFlow.
An overview of the measurement framework is presented in the next section.
Section 3 explains our route scheme design including multiple measurement hosts to probe all links.
Section 4 shows the order of accesses to switches to efficiently locate high-loss links. Section 5 provides the simulation results and evaluation.
|
|
ICACT20210168 Slide.01
[Big slide for presentation]
|
Chrome Text-to-Speach Click!! |
 |
Hi everyone, my name Nguyen Minh Tri from Kyushu Institute of Technology, Japan.
Today I present our paper for ICACT 2021. The title is Locating High-loss Links for OpenFlow Networks by Multiple Hosts to Probe Packets
|
