Estimating the Effects of Multipath Selection on Concurrent Multipath Transfer
Estimating the Effects of Multipath Selection on Concurrent Multipath Transfer
KSII Transactions on Internet and Information Systems (TIIS). 2014. Apr, 8(4): 1406-1423
Copyright © 2014, Korean Society For Internet Information
  • Received : September 25, 2013
  • Accepted : April 03, 2014
  • Published : April 30, 2014
Export by style
Cited by
About the Authors
Jingyu, Wang
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications (BUPT), Beijing, 100876, China
Jianxin, Liao
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications (BUPT), Beijing, 100876, China
Jing, Wang
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications (BUPT), Beijing, 100876, China
Tonghong, Li
Department of Computer Science, Technical University of Madrid, Madrid, 28660, Spain
Qi, Qi
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications (BUPT), Beijing, 100876, China

Multi-mode device which combines multiple access technologies into a device will offer more cost-effective solution than a sole access implementation. Its concurrent multipath transfer (CMT) technology can transmit media flows over multiple end-to-end paths simultaneously, which is essential to select at least two paths from all available paths. At real networks, different paths are likely to overlap each other and even share bottleneck, which can weaken the path diversity gained through CMT. Spurred by this observation, it is necessary to select multiple independent paths as much as possible to avoid underlying shared bottleneck between topologically joint paths. Recent research in this context has shown that different paths with shared bottleneck can weaken the path diversity gained through CMT. In our earlier work, a grouping-based multipath selection (GMS) mechanism is introduced and developed. However, how to estimating the selection is still to be resolved. In this paper, we firstly introduce a Selection Correctness Index (SCI) to evaluate the correctness of selection results in actual CMT experiment. Therefore, this metric is helpful to discuss and validate the accuracy of the output paths. From extensive experiments with a realized prototype, the proposed scheme provides better evaluation tool and criterion in various network conditions.
T he attention on wireless access technologies (WiMAX, WiFi, GPRS, UMTS HSPA and the latest LTE) are rapidly progressing and now it is common to find them not just in laptops, but in various devices as mobile phones, tablets, security cameras and home entertainment equipment. One of the most challenging design goals of next-generation networking architectures [1] [2] [3] be characterized by the collaboration between various access networks. A host with multiple interfaces can connect (potentially through different providers) to multiple networks, and we call this functionality multihoming [4] . When various access networks are nested together, providing a dynamic interface/path selection capability should unlock the potential of multimode devices, as shown in Fig. 1 . For a number of multimedia applications, it is essential that more than one path be selected for concurrent multipath transfer (CMT) [5] [6] to ensure the high-bandwidth requirements can be met effectively. Doing so can provide: (1) more bandwidth and better resiliency for the user, and (2) higher network utilization for network operators. However, current networks base on the IP protocol and therefore are not able to provide multiple disjunctive routes (or parts of the route) towards the same physical host. Classical routing protocols, e.g. OSPF and BGP, allow defining different metrics per route, only, in order to assign each route its special priority. However, this lacks the support of a defined packet scheduling in order to process packets according to round robin scheduling (to increase bandwidth) or packet duplication (to increase robustness).
PPT Slide
Lager Image
Simultaneous use of paths provides Offload and QoS advantages
In general, setting up a good performing end to end multi-path transfer shows a lot of unsolved issues related with the drawbacks of the current layered based protocol stack, where each layer is not aware of the service needs. As demonstrated in [20] , using CMT-SCTP in a multi-path scenario is a hot research topic, where multiple issues have to be solved. Especially the utilization of multiple transport paths through bottlenecks is a big challenge. In CMT simultaneously between a pair of multi-mode devices, a path is expressed as a pair of source-destination (S-D) address for reaching one destination. Essentially, these devices need a mechanism to select suitable number of paths to utilize from all available paths to suit the properties of the fast-speed service such as content sharing.
When a host has multiple parallel paths to send packets to its destinations, it must somehow make a decision of which path(s) to use for which connection(s) on a per-application basis. More specifically, the host needs a mechanism to select the source IP addresses and the destination IP addresses. We consider it a natural requirement that a selection scheme running on an end-host should choose a subset of paths to bear the requirements of upper applications, by providing a good balance between complexity and performance.
The most researches about CMT have the assumption that multiple paths are independent [5] [6] , but this assumption is rarely warranted at real network. For example, two different paths are likely to overlap one or more joint links somewhere in the network, even share bottleneck. So it is necessary to diminish this assumption and take into account the correlation [7] and fairness [8] between paths. Furthermore, the benefits of path diversity depend on whether paths are correlated. Intuitively, we can view the selection of a highly reliable set of end-to-end paths as the problem of maximizing the effect of path diversity for a parallel-series network.
In our earlier work [9] [10] [11] , we introduced a new topic about how to select limited numbers of paths to realise the effect of path diversity in future multihomed networks, and discussed some practical issues on the implementation framework [9] . Second, we propose a probing scheme capable of discovering shared bottlenecks among multiple paths simultaneously [10] . Then, we give the model of path correlation, i.e., any two paths can form one of four logical topologies, and divide multiple available paths into several groups as their correlations, then propose a subsequent Grouping-based Multipath Selection (GMS) strategy [11] . However, they do not fully assess the correctness of selection results. Therefore, we introduce a selection correctness index (SCI) metric to evaluate the correctness of multipath selection results comprehensively. This metric is helpful to and discuss the accuracy in various network conditions. Measuring the accuracy of the output paths is challenging due to the possibility of simultaneous occurrence of the various error types. In addition, different error types should not be treated equally, since they have different effects on performance.
The remainder of this paper is organized as follows. Section 2 summarizes related work.Section 3 states the problem and main intuition. Section 4 explains the proposed SCI, and assesses its pervasiveness. Section 5 presents experimental results to show the correctness of our metric. Section 6 concludes the paper.
2. Related Work
The exploitation of path diversity has attracted much attention recently, and [7] provides a broad overview of the general area. We note that the existence of multiple disjoint paths can result in many benefits including: (1) increased bandwidth, and (2) improved loss characteristics. There are a number of approaches [5] [6] to accomplishing multipath data delivery, the path diversity-based approach is considered.
Multipath routing [12] [13] [14] , especially for wireless ad hoc networks, focuses on how to leverage multiple complete paths through a network. In [12] , Disjoint Pathset Selection Protocol (DPSP) is proposed for selecting a set of paths to achieve the best reliability. Mao et al. [13] further propose a meta-heuristic approach based on Genetic Algorithms to solve the routing selection problem. Wei and Zakhor [14] propose a different method for selection of two node-disjoint paths that takes into account the interference caused by the neighboring links. Other researchers aimed at computing a shortest pair of failure-disjoint paths [15] [16] to solve the flow routing problem closely related to path diversity protection.
Selecting optimal paths in overlay networks has also been an active research area recently [17] [18] [19] . Begen et al. study how to select multiple paths that maximize the video quality at clients on Internet overlay networks [17] . Given information about the underlying network graph, [18] proposes multipath routing heuristics for unicast and multicast scenarios along with a data scheduling algorithm. In [19] , the authors propose to select two paths with minimal correlation for streaming over Internet overlay networks. J. Zhang et al. [20] study the optimal configuration of weighted ECMP, where traffic splitting among the available paths is based on a set of pre-determined ratios. In [21] , authors present Conflux, a dynamic traffic-splitting approach that assigns traffic to an overlay path based on its measured latency.
Multipath selection needs to take advantage of the benefits of path diversity, so discovering the correlation characteristics of multiple paths is the most key problem. It can be done either by internal nodes or by end systems. The aforementioned approaches attempt to learn about single path characteristics, but do not address directly the problem of identifying the correlations between multiple paths. Unlike others, Rubenstein et al. [22] attempt to detect whether two flows share the same bottleneck through end-to-end measurement. However, their goal is only to exploit the relation between two flows. Based on this technique, Younis et al. [23] designed and implemented an efficient on-line approach FlowMate to cluster paths according to shared bottlenecks. When clustering paths, FlowMate maintains a representative path in each cluster, and then applies the shared congestion detection to a new path and the representative of each cluster, instead of every path in the cluster, to reduce computational complexity.
3. Multiple Paths Selection
This section gives some necessary model of multihomed networks and simply introduces the relevant selection approach, which is firstly to classify paths as different groups; then choose the best paths from each group.
- 3.1 Multihomed Network Topology
Consider the multihomed networks are constituted by the multi-mode terminal devices (see Fig. 2 ). The source and the destination are connected via a network of communication links. An end-to-end path is a virtual link directly connecting two IP addresses which come from source and destination device respectively. It can be mapped to the IP path. For example, the Path P12 started from IPs1 and ended with IPd2 consists of the nodes N S , N m , N k , and N D . Characteristics of two end-to-end paths may be correlated because they may share some IP links or nodes. For example, the P12 and P13 share the IP links (N S , N m ) and (N m , N k ).
PPT Slide
Lager Image
Path connectivity graph between a pair of multi-mode devices
An M-by-N multihomed network topology can be abstracted as a directed acyclic graph G =( V,E ) between M source addresses in the source device and N destination addresses in the destination device, along with a given routing policy that maps each source-destination pair to a single routing from the source to the destination. Ignoring the topology and physical links of the network, we let P ij simply denote any one path connecting source address IPsi and destination addresses IPdj , and number the paths as 1, 2, · · ·, M*N.
- 3.2 Grouping Process
When sufficient samples are usable, path correlation computation can be performed for any two paths to determine whether exists shared bottleneck or not. This information is used to classify paths and produce a series of groups with each containing a set of highly correlated paths. The group list is the final output of the classification process.
The grouping process starts with empty group lists and a set of target paths (with sufficient samples) to be grouped. It first selects the first path P 11 in a group. Then the second path P 12 is compared with P 11 to determine whether it should join the group or create a new group. Next for a new path P ij to be grouped, we propose a “representative” path which is the first path in a group.
- 3.3 Selection Process
In the second step, it is necessary to find the best paths [24] within each group firstly. The best path is the path which yields minimum expected transmission time for the requested data given the concurrent transmissions. This path selection just needs to consider the observable performance of the path, not involving the complex routing mechanism. Different from the correlation between paths used for multi-path selection, the intrinsic performance of path is more important for the single path selection within each group. The motivation behind this is to give preference to high-bandwidth low-latency path, for instance we can simply choose it on their bandwidth whose complexity is linear.
4. Selection Correctness Index
This section gives the metric of SCI and discusses the pervasiveness in details.
- 4.1 Requirements
Measuring the correctness of the output paths in a unified manner is challenging. Incorrect selection can be classified into the followings types: omissively choosing the paths that should be selected. We use the term (1) “ missing selection ” to denote it; erroneously choosing the paths that should not be selected. We use the term (2) “ malignant replacement ” and (3) “ benign replacement ” to denote the mistakenly selected paths that have and have not shared bottleneck with other selected paths, respectively; and excessively including the paths that exceeds the required number of paths, which is denoted as (4) “ excessive selection ”. For an actual selection output, these types of incorrect selection are likely to occur simultaneously.
Measuring the accuracy of the output paths in a unified manner is challenging due to the possibility of simultaneous occurrence of the four error types. The four error types have different impacts on the performance of CMT, e.g., malignant replacement is the most severe and benign replacement is the slightest, thus a uniform metric requires considering the severity of each error type (unlike the traditional set similarity metrics [25] which treat all members equally). Our selection correct index (SCI) described below reflects this requirement.
For example, consider a CMT application applied to nine paths, as shown in Fig. 3 . Assume the correct group is four groups with two or three paths each, the output requires at most three paths, and the correct selection is {p1, p3, p4}.
PPT Slide
Lager Image
Example of SCI computation.
Assume that in one instance of “missing selection”, output selections are two paths {p3, p4} instead of three {p1, p3, p4}. Although the two resulting paths belong to different groups individually and haven’t shared bottlenecks indeed in this case, parallel resources cannot be fully exploited. Therefore, consequent performance through CMT is insufficient.
In the second and third instances, both outputs lost p4 and erroneous select another path but the difference is whether to include shared bottleneck. In second case {p1, p3, p6} the malignant replacement path p6 shared bottleneck with p3, the consequent CMT not only can’t achieve resource aggregation, but also cause larger network congestion and affect other paths, which may unnecessarily enter the slow start phase. In contrast, in the third case {p1, p3, p5} the benign replacement path p5 doesn't cause shared bottleneck with p1 or p3, so that the consequent CMT may achieve resource aggregation but not the best choice. Similar cases including {p1, p3, p8}, {p1, p2, p3}, {p2, p3, p4} and so on, where parallel network resources can be fully exploited, are also the acceptable results.
In the last instances {p1, p2, p3, p4}, the output selections are four goes beyond the required number of paths to be selected. This case is likely to increase the cost of consequent CMT, though they may also exploit the path diversity fully.
Their differences between the four cases require the metrics to account for different error types with different weights according to their severity. We believe that malignant replacement and the missing selection is more severe for CMT application. Thus, the second instance in our example is considered less desirable than the others. Secondly, the benign replacement is the most gentle for CMT applications, so the third case is considered the most tolerated. Comparatively, the excessive selection is more efficient than the others, but it does not meet the application demands. In fact, the output selection is likely to include multiple types of errors, which could be analyzed individually and considered integrally. Our selection correct index (SCI) described below reflects these requirements, and the values of SCI in Fig. 3 are consistent with their correctness.
- 4.2 Metric Definition
Let S denote the required number of paths; P c denote the set of correct selection (the number of members in P c is marked as |P c |); P r denote the set of resulting selection (the number of members in P r is marked as |P r |); G n denote the set of correct groups; G c denote the set of groups that the paths of P c belong to ( the number of G c is marked as |G c |); G r denote the set of groups that the paths of P r belong to ( the number of G r is marked as |G r |); S i denote the number of resulting paths included in the group G i of G r ; and N ms denote the number of paths included in P c but missed in P r ; The selection correct index (SCI) is defined as (1):
PPT Slide
Lager Image
In the first item, S i can be computed as follows: firstly map every resulting path in P r to a corresponding group G i of G n , and then S i is the number of resulting paths in each group G i . As the paths in one group share the same bottleneck actually, the number of resulting paths erroneously included in the same group G i is S i -1. The sum of all (S i -1) corresponds to the number of shared bottlenecks caused by malignant replacement or excessive selection . Dividing this sum by the number of resulting paths |P r | can reflect the proportion of errors occurred. Then it is subtracted from 1 expresses the opposite meanings, which shows the probability without these kinds of errors.
The second item reflects the degree of closeness between the resulting groups G r and correct groups G c , where the Abs () denotes the absolute value and Max () denotes the maximum value. The normalized processing is similar to the first item. This group difference is caused by the above three error types except benign replacement , and it is an important macro factor impacting the performance of CMT significantly.
In contrast, the last item is concerned with the missing paths N ms of the resulting selections from the correct selections, which is caused mostly by missing selection or erroneous replacement. The α is proportionality factor (e.g., α =2), which is used to adjust the influence of missing paths. For selecting the free number of paths, |P c | is less than the |G n |, while for the restrained number of paths, |P c | equals to |G n |. Only in calculating the third item, the impact of missing paths and benign replacement are taken into account. Even so, an extra parameter α is introduced to weaken their reduction. This is because benign replacement has fewer undesirable effects than other errors.
Observe that there is the worst case in which none of path is selected. Therefore, the correctness index varies between 0 and 1. For any specific candidate paths, as the number of correct groups increases (decreases), the average number of paths per group decreases (increases). Therefore, the effect of the malignant shared-bottleneck is, on the average, diminished (exacerbated), while the effect of the benign one is exacerbated (diminished). Our SCI considers the fact that the selection of an erroneous path often accompanies with missing paths and erroneous replacement. If the erroneous replacement is malignant replacement , which is likely to cause the changes in shared bottlenecks and groups, then SCI requires prompting two reductions in the first two items respectively. If not, just keep these two items constant, which is because benign replacement has fewer undesirable effects than other errors.
Still consider above example of selecting nine paths where the correct selection is {p1, p3, p4}. If the resulting output is {p3, p4}, then the accuracy index is computed as: 1*(1-1/3)*(1-1/6)=0.56. In this case, one third is deducted for the missing group G1 which path p1 belongs to, and another one sixth is deducted for the missing the path p1. Or if the resulting output is {p1, p3, p6}, then the accuracy index is computed as: (1-1/3)*(1-1/3)*(1-1/6)=0.19. In this case, one third is deducted for one erroneous selection p6 shared bottleneck with p3, another one third is deducted for one missing group G 3 which path p4 belongs to, and one sixth is deducted for one missing the path p1. This is why the selection correct index is 56% (19%) in the first (second) case of Fig. 3 , Table 1 gives additional examples.
Example of Computing the Selection Correct Index (SCI) for Twelve Paths with Three Correct Groups (Gn={p1,p5,p9},{p2,p3,p6,p7},{p4,p8},{p10,p11},{p12}) and Correct Selection (Pc={p1,p3,p4,p12})
PPT Slide
Lager Image
Example of Computing the Selection Correct Index (SCI) for Twelve Paths with Three Correct Groups (Gn={p1,p5,p9},{p2,p3,p6,p7},{p4,p8},{p10,p11},{p12}) and Correct Selection (Pc={p1,p3,p4,p12})
It is important to notice that complexity of the SCI computing algorithm does not exceed quadratic complexity, and often has linear complexity. With respect to the number of paths, we show that SCI computing is low, rendering on-line evaluating feasible.
- 4.3 Pervasiveness for Random Selection
Assume a random selection may output a certain number of paths as required. Observe that, on the average, the random selection will likely result in a number of erroneous paths, in addition to false sharing bottleneck, yielding values typically less than 50% for the accuracy (depending on the number of paths required).
Table 2 gives the average SCI for variable number of candidate paths (random deployment) for a case requires to selecting three paths. Results are congruent with our argument on average accuracy of random selection. Table 3 gives the average SCI for variable number of paths required to select for a case with fixed twelve candidate paths. Results are diminishing with the number of paths required on average accuracy of random selection.
Average SCI over the Number of Candidate Paths when Needs to Select Three Paths (|Pr|=3)
PPT Slide
Lager Image
Average SCI over the Number of Candidate Paths when Needs to Select Three Paths (|Pr|=3)
Average SCI over the Number of Paths Required when There are Twelve Paths with Six Groups (Gn={p1,p2},{p3,p4},{p5,p6},{p7,p8},{p9,p10},{p11,p12})
PPT Slide
Lager Image
Average SCI over the Number of Paths Required when There are Twelve Paths with Six Groups (Gn={p1,p2},{p3,p4},{p5,p6},{p7,p8},{p9,p10},{p11,p12})
Fig. 4 further validates our argument by considering random selections in different cases. We adjust the average number of paths in correct groups (which we refer to as “diversity degree” (dd)) to a certain ratio of the total number of paths required. Such as Gn is {p1,p2,p3}, {p4,p5,p6}, {p7,p8,p9}, {p10,p11,p12}, the average number of path per group is 3, so that the diversity degree is computed as: 3/12=25%. For each diversity degree, a random correct path set is selected. Another random path set is selected as the output, and the SCI is computed. This process is repeated 1000 times and the average SCI is reported. The figure illustrates that the average accuracy for random path set highly depends on the diversity degree. This is intuitive, since a larger number of paths per group yields more malignant shared-bottleneck replacement than benign replacement.
PPT Slide
Lager Image
SCI of random selections with respect to different number of the path required.
5. Evaluation and Numerical Results
- 5.1 Implementation Framework
In order to deploy the proposed multipath selection in the multi-mode device easily, we propose an implementation framework in the end-device system as shown in Fig. 5 . The key elements are a decision point Multipath Selection and an aggregate point Multipath State Management , and other function modules responsible for reporting the information of different levels including the Access Capability , the end-to-end Routing Capability , the non-physical constraints Policy & Preferences of the operator(s) and user, the dynamic end-to-end path capacity through Multipath Flow Control and a series of per-path Congestion Control modules.
PPT Slide
Lager Image
Implementation framework for multipath selection
The basic flow of information is as follows:
* Access Capability detects a number of available accesses that can be used to support the application requirement. These available accesses are pre-filtered based on capabilities of the first hop, and potentially any information about local interface network capabilities.
* The set of remaining potential paths is then passed on to Routing Capability , which interacts with routing functionality to determine capabilities of the possible paths across the network between the source and the destination.
* Multipath Flow Control is responsible for managing the multiple paths uniformly, such as coordinated ARQ and load scheduling. The per-path Congestion Controls are responsible for limiting the transmission rate of each path by controlling its window size independently, and assessing the real-time capabilities of the end-to-end paths. All above functionalities may be implemented by the multipath transport protocol, such as proposed cmpSCTP [26] . The feedback data (e.g. throughput, latency and packet loss rate) can be collected from the current traffic by most of transport control protocols. We can use the feedback information to optimize the multipath selection.
* When an application is initiated, it sends the application requirements and Policy & Preferences information to Multipath Selection . This decision element sends a request for paths towards the given destination to Multipath State Management and receives a list of candidate paths with associated capabilities and their correlations, and then combines with the information to select the most appropriate multiple paths for that application.
- 5.2 Experiment Configuration
In our experiment, the above functions are developed in the multi-mode hand held devices with Open source Linux OS along with SDK. The CMT mechanism is implemented based on the proposed cmpSCTP [26] protocol. With integrated wireless features like W-CDMA and GSM/GPRS (refer to Fig. 6 ), the terminal can be deployed virtually anywhere in the field. G i ven the unique multiplexing techniques used by each technology, each format in a multi-mode device is an individual path.
PPT Slide
Lager Image
General multi-mode mobile block diagram
Three topologies are used in our experiments to imitate complicated networks. The topologies provide a simplified connection of the physical routes which only contains some routers playing the role in branching or joining the paths of network flow. The source is provided with 2 or 3 addresses and the destination with 3 or 4 addresses, so there are 6 or 12 parallel paths between the source and destination host. 6 or 12 concurrent TCP-like flows are generated as foreground traffic, accompanied by the same number of multiplexed Pareto flows generated as background traffic. Our cross-traffic generator is a combination of 10 Pareto sources with an on-off period that takes value in the range [10 msec, 1 sec]. Each experiment ran for 20s where probe flows and background flows start at 0s, and cross-traffic flows start at 3s. Each path’s share of the bottlenecks’ bandwidth is affected by cross-traffic. The capacity and propagation delay of each link are indicated in Fig. 7 , Fig. 8 , and Fig. 9 . Table 3 summarizes the experiment parameters.
PPT Slide
Lager Image
Marginal model experiment configuration
PPT Slide
Lager Image
Central model experiment configuration
PPT Slide
Lager Image
Universal model experiment configuration
Experiment Parameters
PPT Slide
Lager Image
Experiment Parameters
In the first topology ( Marginal model ) as Fig. 7 , the shared bottlenecks occur in the margin of the network. We generate cross traffic with bandwidth 8 Mbps between R1 and R6 to produce the first shared bottleneck SB1. The second shared bottleneck SB2 occurs in R5 due to the minimal capacity of 3Mbs but shared by P13 and P23 . In the second topology ( Central model ) as Fig. 8 , the shared bottlenecks occur in the center of the network. The center shared links have limited bandwidth, while the link on the P12 , P12 , P21 and P22 are congested by high cross-traffic load. These two topologies simulate the environment where the shared bottleneck occurs either in the edge or the core router.
Fig. 9 depicts the third experiment topology ( Universal model ), where the shared bottlenecks can occur in any location of the network including the edge router and the core router. This topology is not as symmetric as the first two, which includes more paths and more complicated path relationships. The 12 paths produce 5 bottlenecks, which involve 4 shared bottlenecks and 1 unshared bottleneck. In these bottlenecks, the SB1 and SB2 are congested by high cross-traffic load, SB3 and SB4 are congested by limited bandwidth, and the only unshared bottleneck between R3 and R7 is possessed by P34 .
- 5.3 Correctness of GMS
In this part, we discuss the results of experiments on the topology in Fig. 7 , Fig. 8 and Fig. 9 . In our first experiment, we compute the SCI on two basic models both with 6 paths as Fig. 7 and Fig. 8 . We then perform an experiment with more universal model as Fig. 9 with 12 paths. Fig. 10 shows the performance for 6 and 12 paths using one TCP probe flow respectively as foreground traffic. To interpret the results more easily, we trigger selecting at fixed intervals and do not trigger it early if sufficient samples are received before T period . Here, the value used for T period is set as 3 seconds. Therefore, the results of the first selecting can be seen at time 3 second, at time 6 second, and so on. Note that we compute the correct index by comparing against a static correct partitioning, even though the background traffic variations entail a dynamic selecting goal. We select this more conservative approach for ease of correct index computation, and to show the worst case index value.
PPT Slide
Lager Image
Three metrics with GMS
Our metric is different from the Accuracy Index (AI) presented in [23] and Cluster Validity Index (CVI) based on Jaccard index presented in [27] . The metric that we present accounts for all types of errors with weights based on their severity (malignant replacement is more severe than benign replacement). In [23] , one metric is proposed for each error type considering their weights based on their severity, but only fits to multiple flows partitioning. Another clustering validity index [27] was presented to be used to measure the similarity of the clustering results associated to two different methods, which treat all members equally.
Then we take an experiment to evaluate the performance of GMS in terms of the SCI/AI/CVI under the above three experiment topologies. To interpret the results more easily, GMS is triggered at fixed interval T period . Here, the value of T period is set as 3s. Therefore, GMS runs at time 3 s, at time 6 s, and so on. We observe in Fig. 10 (a) that in steady state, the performance of SCI is reasonable (SCI >85%). During the initial transient period, which includes the first one or two selecting invocations, sample delay patterns are not unique, so SCI is lower. After the transient period is over, SCI becomes higher: the incorrectness observed is mostly due to a few benign replacements . Fig. 10 (b) illustrates the performance of AI is also reasonably good (AI >75%) in steady state, and if a dynamic accuracy metric (that considers transient bottlenecks) is used, the accuracy index increases. Samples are too few paths are discarded from the partitioning process. Fig. 10 (c) illustrates CVI during the same period causes an abrupt degradation in accuracy, unlike the case where accuracy is enhanced gradually as time goes on.
In the second experiment, we study the impact of T period on the performance of SCI/AI/CVI and their results are shown in Fig. 11 . We have found that the three metrics of T period does not have a profound impact on the results of GMS. Results for T period values between 3 s and 10 s follow almost the same pattern as the results in the previous experiment in which T period is set as 3 s. Below 3 s, samples are few, and many paths are isolated into their respective groups in the grouping process. When the T period is too long (above 10 s), SCI//AI/CVI are not significantly enhanced. From Fig. 11 (a), we have also observed that during under loaded transient periods, the frequency of malignant replacements in the selection process is typically higher than that of benign replacements . This is why the SCI is lower during these periods when errors are mostly due to malignant replacements . Fig. 11 (b) and Fig. 11 (c) shows accuracy is not sensitive enough to select period, though their values are slightly lower.
PPT Slide
Lager Image
Effect of the maximum correlation period
6. Conclusion
In recent years, terminal devices with multi-mode capabilities (i.e. equipped with multiple network interfaces) have gained large scale popularity. This multi-mode capability enables the terminal devices to connect with multiple diverse access networks simultaneously. CMT has been regarded as one of the key properties for service-oriented applications. Thus, how to select these paths for a given application, rather than interfaces or routes, seems to be a very interesting area of research.
Starting from analyzing the result of selection multiple paths, we propose a new metric for estimating the multipath selection mechanism. Furthermore, we propose an approach to validating correction according to the new metric. Experimental studies demonstrate that the new metric and estimation mechanisms can produce a more feasible estimation of multipath selection correction. In our future work, we plan to make a survey on whether the new metric is applicable for any selection strategies. We also plan to extend the data set in the future study.
Jingyu Wang obtained his PhD degree from Beijing University of Posts and Telecommunications in 2008. Now he is an associate professor in Beijing University of Posts and Telecommunications, China. His research interests span broad aspects of performance evaluation for Internet and overlay network, consumer electronic, traffic engineering, image/video coding, multimedia communication over wireless network.
Jianxin Liao obtained his PhD degree at University of Electronics Science and Technology of China in 1996. He is currently the dean of Network Intelligence Research Center and the full professor of State Key laboratory of Networking and Switching Technology in Beijing University of Posts and Telecommunications. He has published hundreds of research papers and several books, and has been granted dozens of patents for inventions. He has won a number of prizes, which include the Premier's Award of Distinguished Young Scientists from National Natural Science Foundation of China in 2005, and the Specially-invited Professor of the “Yangtse River Scholar Award Program” by the China Ministry of Education in 2009. His main creative contributions include mobile intelligent network, service network intelligent, networking architectures and protocols, and multimedia communication. These achievements were conferred the “National Prize for Progress in Science and Technology” twice in 2004 and 2009, respectively.
Jing Wang obtained his PhD degree from Beijing University of Posts and Telecommunications in 2009. Now she is an associate professor in Beijing University of Posts and Telecommunications. Her major is Telecommunications and Information Systems. Her research interests include consumer electronic, network intelligence, mobile internet, and ubiquitous services.
Tonghong Li obtained his PhD degree from Beijing University of Posts and Telecommunications in 1999. He is currently an assistant professor with the department of computer science, Technical University of Madrid, Spain. His main research interests include resource management, distributed system, middleware, wireless networks, and sensor networks.
Qi Qi obtained his PhD degree from Beijing University of Posts and Telecommunications in 2010. Now she is an assistant professor in Beijing University of Posts and Telecommunications. Her research interests include SIP protocol, communications software, Next Generation Network, Ubiquitous services, and multimedia communication.
Benali O. , El-Khazen K. , Garrec D. , Guiraudou M. , Martinez G. 2004 “A framework for an evolutionary path toward 4G by means of cooperation of networks” IEEE Communications Magazine Article (CrossRef Link) 42 (5) 82 - 89    DOI : 10.1109/MCOM.2004.1299347
Hui S. , Yeung K. 2003 “Challenges in the migration to 4G mobile systems” IEEE Communications Magazine Article (CrossRef Link) 41 (12) 54 - 59    DOI : 10.1109/MCOM.2003.1252799
Paul S. , Pan J. , Jain R. 2011 “Architectures for the Future Networks and the Next Generation Internet: A Survey” Computer Communications Article (CrossRef Link) 34 (1) 2 - 42    DOI : 10.1016/j.comcom.2010.08.001
Smith P. 2001 “BGP multihoming techniques” in Proc. of NANOG 23 Oakland, California Oct. [Online]. Available:
Iyengar J. R. , Amer P. , Stewart R. 2006 “Concurrent multipath transfer using SCTP multihoming over independent end-to-end paths” IEEE/ACM Transactions on Networking Article (CrossRef Link) 14 (5) 951 - 964    DOI : 10.1109/TNET.2006.882843
Fashandi S. , Oveisgharan S. , Khandani A.K. 2010 “Path Diversity Over Packet Switched Networks: Performance Analysis and Rate Allocation” IEEE/ACM Transactions on Networking Article (CrossRef Link) 18 (5) 1373 - 1386    DOI : 10.1109/TNET.2010.2043368
Apostolopoulos J. , Trott M. 2004 “Path diversity for enhanced media streaming” IEEE Communications Magazine Article (CrossRef Link) 42 (8) 80 - 87    DOI : 10.1109/MCOM.2004.1321395
Becke M. , Dreibholz T. , Adhari H. , Rathgeb E. P. 2012 “On the Fairness of Transport Protocols in a Multi-Path Environment” in Proc. of IEEE ICC Ottawa, Canada June Article (CrossRef Link)
Liao J. , Wang J. , Li T. , Zhu X. 2011 “Introducing Multipath Selection for Concurrent Multipath Transfer in the Future Internet” Computer Networks Article (CrossRef Link) 55 (4) 1024 - 1035    DOI : 10.1016/j.comnet.2010.12.010
Liao J. , Wang J. , Li T. , X Zhu 2011 “Multipath Probing and Grouping in Multihomed Networks” IEICE Transactions on Information and Systems Article (CrossRef Link) E94.D (3) 710 - 713    DOI : 10.1587/transinf.E94.D.710
Wang J. , Liao J. , Li T. , Zhang P. 2012 “Correlation-aware Multipath Selection to Enhance Path Diversity in Ubiquitous Computing Environment” International Journal of Ad Hoc and Ubiquitous Computing Article (CrossRef Link) 11 (4) 246 - 257    DOI : 10.1504/IJAHUC.2012.050438
Papadimitratos P. , Haas Z.J. , Sirer E.G. 2002 “Path set selection in mobile ad hoc networks” in Proc. of ACM MobiHoc Lausanne, Switzerland Jun. Article (CrossRef Link)
Mao S. , Hou Y. , Cheng X. , Sherali H. , Midkiff S. 2005 “Multipath routing for multiple description video in wireless ad hoc networks” in Proc. of IEEE INFOCOM Miami, FL Mar. Article (CrossRef Link)
Wei W. , Zakhor A. 2006 “Path selection for multi-path streaming in wireless ad-hoc networks” in Proc. of IEEE International Conference on Image Processing (ICIP) Atlanta, Georgia, USA Oct. Article (CrossRef Link)
Zotkiewicz M. , Ben-Ameur W. , Pioro M. 2010 “Finding failure-disjoint paths for path diversity protection in communication networks” IEEE Communications Letters Article (CrossRef Link) 14 (8) 776 - 778    DOI : 10.1109/LCOMM.2010.08.100653
Ben-Ameur W. , Pióro M. , Żotkiewicz M. M. 2012 “Fractional routing using pairs of failure-disjoint paths” Discrete Applied Mathematics Article (CrossRef Link).
Begen A. , Altunbasak Y. , Ergun O. 2003 “Multi-path selection for multiple description encoded video streaming” in Proc. of IEEE ICC Anchorage, Alaska, USA May Article (CrossRef Link) 1583 - 1589
Chan J. , Chen S. , Li V. 2002 “Multi-path routing for video delivery over bandwidth-limited networks” IEEE Journal on Selected Areas in Communications Article (CrossRef Link) 22 (10) 1920 - 1932    DOI : 10.1109/JSAC.2004.836000
Ma Z. , Shao H. , Shen. C. 2004 “A new multi-path selection scheme for video streaming on overlay networks” in Proc. of IEEE ICC Paris, France Jun. Article (CrossRef Link).
Zhang J. , Xi K. , Zhang L. , Jonathon Chao H. 2012 “Optimizing Network Performance using Weighted Multipath Routing” in Proc. of IEEE International Conference on Computer Communications and Networks (ICCCN) Munich, Germany Jul.-Aug. Article (CrossRef Link) 1 - 7
AlSabah M. , Bauer K. , Elahi T. , Goldberg I. 2013 “The Path Less Travelled: Overcoming Tor's Bottlenecks with Traffic Splitting” in Proc. of Privacy Enhancing Technologies Symposium (PETS) Bloomington, Indiana, USA July Article (CrossRef Link)
Rubenstein D. , Kurose J. , Towsley D. 2002 “Detecting shared congestion of flows via end-to-end measurement” IEEE/ACM Transactions on Networking Article (CrossRef Link) 10 (3) 381 - 395    DOI : 10.1109/TNET.2002.1012369
Younis O. , Fahmy S. 2005 “Flowmate: scalable on-line flow clustering” IEEE/ACM Transactions on Networking Article (CrossRef Link) 13 (2) 288 - 301    DOI : 10.1109/TNET.2005.845532
Fracchia R. , Casetti C. , Chiasserini C. , Meo M. 2007 “WiSE: best-path selection in wireless multihoming environments” IEEE Transactions on Mobile Computing Article (CrossRef Link) 6 (10) 1130 - 1141    DOI : 10.1109/TMC.2007.1027
Li M. , Chen X. , Li X. , Ma B. , Vitanyi P. 2004 “The Similarity Metric” IEEE Transactions on Information Theory Article (CrossRef Link) 50 (12) 3250 - 3264    DOI : 10.1109/TIT.2004.838101
Liao J. , Wang J. , Zhu X. 2008 “A multi-path mechanism for reliable VoIP transmission over wireless networks” Computer Networks Article (CrossRef Link) 52 (13) 2450 - 2460    DOI : 10.1016/j.comnet.2008.04.008
Ng K-H , Ho C-K , Phon-Amnuaisuk S 2012 “A Hybrid Distance Measure for Clustering Expressed Sequence Tags Originating from the Same Gene Family” PLoS ONE Article (CrossRef Link) 7 (10)    DOI : 10.1371/journal.pone.0047216