Kyu-Han Kim and Kang G. Shin
Department of Electrical Engineering and Computer Science
The University of Michigan, Ann Arbor
{kyuhkim,kgshin}@eecs.umich.edu
In this paper, we first describe the need for such a mobile collaborative community, or a community, in which multi-homed mobile hosts exploit the diversity of WWAN connections to improve a user-perceived bandwidth and network utilization. Then, we show that existing one-to-one communication protocols like TCP suffer significant performance degradation due to frequent packet reordering and heterogeneity of WWAN links in the community.
To address the above TCP problem, we propose a proxy-based inverse multiplexer, called PRISM, that enables TCP to efficiently utilize the community members' WWAN connections. PRISM runs at a proxy's network layer as a routing component and stripes each TCP flow over multiple WWAN links by exploiting the transport-layer feedback information. Moreover, it masks variety of adverse effects specific to each WWAN link via intelligent ACK-control mechanism. Finally, PRISM includes a sender-side enhancement of congestion control, enabling TCP to respond correctly to dynamically-changing network states.
We have evaluated the PRISM protocol using both experimentation and ns-2-based simulation. Our experimental evaluation has shown PRISM to improve TCP's performance by up to 310% even with two collaborative mobile hosts. Our in-depth simulation study also shows that PRISM delivers a near-optimal aggregated bandwidth in the community formed by heterogeneous mobile hosts, and improves network utilization significantly.
It is important to note that collaboration among multi-homed mobile hosts significantly improves both user-perceived bandwidth and overall wireless network utilization. Mobile hosts in close proximity can spontaneously form a ``community,'' connected via a high-speed WLAN interface, and share their WWAN link bandwidths with other members in the community. Possible applications of this include (i) contents sharing where each host with same interests receives a subset of contents from an Internet server and share the contents with other hosts, and (ii) bandwidth sharing where one host in a community needs more bandwidth than its own WWAN link for applications like video-on-demand or Hi-Definition TV live cast.
We, therefore, advocate formation of a mobile collaborative community that is a user-initiated network service model and that allows bandwidth sharing/pooling among multi-homed mobile users to make the best of their diverse WWAN links. The mobile community is different from a current WWAN service model, which forces a mobile host to use a single WWAN link at a time, causing capacity, coverage, and hardware limitations. By contrast, the community helps mobile users initiate new virtual WWANs that overcome such limitations by sharing their WWAN interfaces. Moreover, by adopting an inverse multiplexer [10], the mobile community effectively aggregates its members' WWAN bandwidths.
However, the existing transport protocols, such as the Transmission Control Protocol (TCP), are not aware of existence of multiple and parallel intermediate links, and thus, cannot exploit multiple available WWAN links in the community. Even with the help of a multi-path routing protocol, frequent out-of-order packet delivery due to the heterogeneity of WWAN links significantly degrades TCP's performance.
There are several transport-layer solutions for bandwidth aggregation of a single multi-homed mobile host such as those in [13,12,14], but their basic design considers aggregation of the interfaces of only a single host or user, and requires support from the network layer to route traffic to/from a group of multi-homed mobile hosts. Furthermore, the development and deployment of a whole new transport protocol requires significant efforts on both content servers and mobile clients, and also incurs a high computational overhead to resource-scarce mobile hosts.
To solve these problems, we propose a proxy-based inverse multiplexer, called PRISM, that enables each TCP connection to utilize the entire community's aggregate bandwidth. As a TCP's complementary protocol, PRISM consists of (i) an inverse multiplexer (PRISM-IMUX) that handles TCP's data and acknowledgment (ACK) traffic at a proxy, and (ii) a new congestion control mechanism (TCP-PRISM) that effectively handles, at a sender side, packet losses over the community's WWAN links.
The first component stripes TCP traffic intelligently over multiple WWAN links using up-to-date link utilization information and each packet's expected time of arrival at a receiver. Also, it masks the effects of out-of-order delivery by identifying spurious duplicate ACKs and re-sequencing them so that a TCP sender receives correctly-sequenced ACKs.
The second component in PRISM is a sender-side congestion control mechanism (TCP-PRISM) that reduces the loss recovery time and accurately adjusts a congestion window size of TCP by using the loss information provided by PRISM-IMUX. It immediately dis-ambiguates real packet losses from out-of-order deliveries through negative loss information, and reduces the loss recovery time. Its proportional adjustment strategy of the congestion window size further improves link utilization by minimizing the effects of partial congestion on un-congested links.
We evaluate the performance of PRISM using both experimentation and ns-2-based simulation. PRISM is implemented as a Linux kernel loadable module and extensively evaluated on a testbed. Our experimental evaluation has shown PRISM to improve TCP's performance by 208% to 310% even with two collaborative mobile hosts with heterogeneous link delays, loss rates and bandwidths. Moreover, our simulation study shows that PRISM effectively reduces the need for packet reordering and delivers the near-optimal aggregated bandwidth in the community that is composed of heterogeneous mobile hosts.
The rest of this paper is organized as follows. Section 2 presents the motivation and the contributions of this work, and Section 3 provides an overview of the PRISM architecture. Sections 4-6 give detailed accounts of PRISM. Section 7 describes our implementation and experimentation experiences. Section 8 evaluates the performance of PRISM using ns-2-based simulation. Related work is discussed in Section 9. Finally, Section 10 discusses a few remaining issues with PRISM and concludes the paper.
Although there exist many choices (i.e., different ISPs, technologies, and channels) in the current wireless network environment, they are not utilized efficiently due to the current ISP-centric service model. That is, most mobile users should use the same network, technology, or a single frequency channel to get a common service. As a result, they suffer from various service limitations as follows.
Let us consider the following scenario to have a feel for the above limitations. Sam is waiting at an airport for his flight, and wants to download his favorite movies to watch during his flight. First, he tries to use his own WWAN interface, but finds that it will take longer than his waiting time for the flight (capacity limitation). Next, he decides to use his WLAN interface. However, the nearest WLAN hot-spot is too far away for him to return in time for the flight (coverage limitation). Finally, he finds another access network with high capacity, but his device does not support the access network's technology (hardware limitation). Therefore, Sam will not be able to watch the movies. Instead, Sam searches other nearby mobile users who are willing to share their interfaces for certain ``rewards.'' He finds several mobile hosts whose interfaces have capacity, use different frequency channels, or support a high-rate wireless technology like IEEE 802.16. With the help of other mobile hosts, Sam can download movie files in time, and enjoy them during his flight.
![\includegraphics[width=4in]{figure/arche_h.eps}](img10.png)
|
To realize a scenario like this, we construct a user-initiated
collaborative wireless network model, called a mobile
collaborative community (MC
).
As shown in Figure 2.1, the community is composed
of multi-homed mobile hosts in physical proximity.
Community members are connected to
the Internet via different WWAN ISPs (
) or different
channels2 of the same ISP (
),
and forward packets via WLAN interfaces in ad-hoc mode.
A somewhat related debate is underway with regard to ``forwarding incentives'' in ad hoc network routing[7,9,19,24]. In ad hoc networks, the communication between end-points outside of the radio transmission range relies on intermediate nodes on the path to forward packets for them. Some researchers suggest use of credit-based, or reputation-based, schemes to stimulate cooperation [7,15,24]. Game-theoretic arguments have been used to show that collaboration on packet forwarding among all participating nodes will yield maximum network throughput.
Forwarding in ad hoc networks, however, is somewhat different from the collaboration we consider here. In ad hoc networks, nodes rely on each other to communicate amongst themselves. In a mobile community, nodes rely on each other not for basic connectivity, but for performance improvements. As we will see in Section 3, a node completely controls access to its shared communication resources, and revokes access if its communication needs are not met by the community. Ultimately, it is the ability to opt-in to achieve better performance and the ability to opt-out when necessary, making link sharing a viable option.
Then, an issue is where to put the inverse multiplexer. The inverse multiplexer can be placed at a performance-enhancing proxy by a network access provider, a wireless telecommunication service provider, or a content distribution network operator. Furthermore, it can be placed in a network layer as one routing component with an efficient traffic filtering function as in the Network Address Translation (NAT) service. On the other hand, the inverse multiplexer might run as an application like in an overlay network. However, multiplexing inherently requires responsive network state information, and additional packet processing overheads at the application layer limit the performance of the inverse multiplexer [13].
's Use of TCP
, we enable one-to-many-to-one
communication for a TCP connection to achieve high-speed
Internet access. While traditional one-to-one communication
of TCP limits its bandwidth to a single link's capacity,
in an MC,
we enable a TCP connection to achieve the members' aggregate
bandwidth by
inverse-multiplexing its packets over all available links.
In this communication model, however, we encounter several challenges. First, scheduling traffic over wireless links requires exact link state information such as data rate and delay, which varies with time and is usually expensive to obtain in mobile environments. Second, because WWAN links suffer from high and variable round trip times (RTTs), burstiness and outages, the large number of out-of-order packet deliveries, which generate spurious duplicate ACKs, degrade TCP's end-to-end performance significantly. Finally, TCP's congestion control mechanism does not fully utilize multiple links' bandwidths because it interprets a packet loss as the overall links' congestion, making over-reduction of its congestion window size. Also, frequent spurious duplicate ACKs with positive ACKs cause the sender to delay loss detection/recovery.
The rest of this paper provides a detailed account of PRISM. The following assumptions are made for the basic design of PRISM and mobile community: (i) each mobile host has multiple (especially WWAN and WLAN) interfaces that can be used simultaneously for a single application connection; (ii) a mobile community is formed via an application-layer daemon; (iii) GRE is enabled as a default; and (iv) all hosts support TCP-SACK.
![\includegraphics[width=6in]{figure/protocole_h.eps}](img13.png)
|
![\includegraphics[width=6in]{figure/schedulee_h.eps}](img14.png)
|
ADAS is a new packet-scheduling algorithm that is adaptive to dynamic input/output rates, and is flexible enough to deal with the lack of rate information. ADAS maintains up-to-date links state which is inexpensively obtained by RPC (see Section 5), and adaptively schedules traffic over the best available links using the state information. Also, it uses packets' expected arrival times over each link not only to reduce out-of-order packet deliveries, but also to increase the end-to-end throughput. Finally, ADAS adaptively reacts to a link's congestion via a TCP's AIMD-like traffic control mechanism.
).
Under Rule.3,
if there are more than two links with the same utilization,
then ADAS picks the link that has the smallest expected
arrival time (
).
)
is derived
from the Weighted Round Robin (WRR) scheduling for its
fairness. WRR divides the time into a round,
in each of which packets are assigned to a link
based on its proportional bandwidth (or weight), and thus,
all links are utilized fairly.
Likewise, ADAS uses the link-weight for fair link utilization,
thus achieving long-term fairness as WRR does.
However, ADAS uses a different definition of link utilization;
while WRR keeps track of how many packets have been
scheduled so far on each outgoing link, ADAS considers how many
packets are currently in-flight on the link.
Because existing static scheduling algorithms (e.g., WRR) assume
accurate and stable links state information, the link utilization
based on the algorithm might not be accurate due to network
dynamics.
ADAS exploits the actual number of in-flight packets, which
can be derived from scheduled packets' information and
ACK-control information, and which automatically reflect unexpected
delay or loss of a link, in order to determine the utilization
of each link.
Therefore, we define ``link utilization'' as
,
where 
is the number of in-flight packets over link 
,
and 
(link weight) is the ratio of the link bandwidth
to the least common denominator/factor of all links' bandwidths.
Let's consider Case A in Figure 3 to see
the effectiveness of 
.
The ratio of the weight of link 
to that of
link 
is assumed to be 1:2.
ADAS schedules the third packet (
)
on because when arrives at the proxy,
ADAS knows from an ACK packet (
) that 
has left ,
so still has more available bandwidth than .
In case of WRR, it assigns to because the quantum
of has already exhausted by 
and , wasting
available bandwidth of .
)
)
along with to further improve overall link utilization
and minimize the need for packet reordering.
When more than one link (
)
have the same lowest link utilization, ADAS selects the link
that has the smallest expected arrival time
in that subset of links (Rule.3).
Due to a WWAN link's varying
transmission delay or forwarding nodes' unexpected
processing delay, links with similar utilization might
experience different short-term rates or delay fluctuations
which might not be immediately reflected into .
Using ensures that ADAS transmits packets
on the fastest link in a greedy fashion,
and thus, not only increases the overall short-term links
utilization, but also reduce out-of-order packet deliveries
at a receiver.
Let's consider Case B in Figure 3 to illustrate
the effectiveness of .
Until 
, ADAS has packets scheduled on each link with
the same sequence as WRR does.
However, at 
, of increases and at the
point of scheduling 
, the expected arrival time of via
becomes longer than that via .
Besides, since the values of both links are same,
ADAS schedules on . If the packet is scheduled
on as WRR does, then might arrive later than 
,
and could waste its bandwidth until
the transmission of begins.
becomes larger, and new packets
are not assigned to the link until it recovers from the
congestion.
This link weight increases additively each time an ACK arrives
on that link, without exceeding the original weight.
This way, ADAS adaptively reacts to partial links' congestion
and controls the amount of traffic to be allocated to each link
without requiring expensive instantaneous bandwidth information.
Case C in Figure 3 depicts ADAS's reaction
to both delay fluctuations and packet losses.
When 
is scheduled at 
, experiences an
increased . However, ADAS schedules on
based on to maintain maximum network utilization
even though it might cause packet reordering.
On the other hand, right before scheduling 
,
ADAS identifies a packet loss on . It adaptively reduces
the 's weight, and assigns to
based on the new computed link utilization.
time
complexity where 
is the number of available links. Usually,
is less than 10, so its overhead is not significant.
ADAS requires constant space complexity.
ADAS maintains a link-state table as shown in
Figure 3.
It independently stores per-link information which includes
only four variables (i.e., , 
, and ).
The Reverse Path Controller (RPC) is an intelligent ACK-control mechanism that hides the adverse effects of out-of-order packet deliveries to the receiver. RPC exploits TCP's control information which is carried by ACKs, to determine the meaning of duplicate ACKs and correct them, if necessary. Moreover, along with the scheduling history, RPC also infers the link condition such as its packet loss, delay, and rate. Finally, because RPC maintains each link's state information (including loss and instantaneous capacity), it provides such information to the sender's congestion-control mechanism so as to prevent one pipe from stalling other uncongested pipes, thus enhancing network utilization.
Figure 4 shows a series of snapshots that describe the two schemes of identifying a sequence number. For example, the snapshot I, II, and IV show the SACK block matching scheme. The snapshot III and V illustrate how cumulative ACK numbers are scanned. Each snapshot contains the circular buffer representing the meta-state of the receiver buffer.
![\includegraphics[width=4in]{figure/ackide_h.eps}](img38.png)
|
If arrived ACK packets are duplicates (line 8),
then RPC re-sequences them in two different ways.
First, if there is not any congested link
(i.e., all links are in NORMAL state), then RPC holds
the ACK packet in the slot of the wrapped-around re-sequence
number (
) in the circular ACK buffer.
Since RPC knows the meaning of an ACK, it corrects the
cumulative ACK sequence number with the identified
number of the ACK packet and stores it in the buffer.
Second, if RPC is in the LOSS state, it releases
ACKs-on-hold in their original form
because duplicate ACKs have really resulted from packet loss(es),
and because released duplicate ACKs can help the sender
calculate the number of packets that have left the network.
, 
). However, if there are duplicate ACKs
resulting from either out-of-order delivery or a packet loss,
then RPC needs to figure out (compute) the ACK's
sequence number and space to re-sequence ACKs.
Given duplicate ACKs, RPC only requires constant time complexity
and 3KB space complexity per connection in the worst case.
The most computation-intensive mechanism in RPC is ACK
identification
which requires extensive sequence comparison.
However, this overhead can be minimized using such optimization
techniques as a bit-operation, and thus requires constant
time complexity.
RPC may have to store all ACKs of a flow in the worst
case. Since the number of ACKs is limited by the number of
outstanding packets in the network,
is the maximum required ACK
re-sequencing buffer size.
For example, assuming that an aggregated bandwidth and
average RTT are 5 Mbps and 120 ms, respectively, and 
is 1.5 KB and the size of ACK (
) is 60 bytes,
a maximum space requirement is 3 KB.
PRISM addresses these problems by using two mechanisms. The first mechanism provides exact loss/congestion information in a negative form to a TCP sender. The second is a sender-side congestion control mechanism (TCP-PRISM), which understands negative ACK information from networks and expedites loss recovery upon congestion of a link in one of multiple paths.
![\includegraphics[width=4in]{figure/statemachinee_h.eps}](img45.png)
|
RPC provides loss information to the sender that includes:
(i) which data packet is lost, (ii) which channel is congested
to adjust the congestion window size, and (iii) how many packets
have left the network. Once a packet loss is detected,
RPC sends the lost packet's sequence number to the sender
in the form of negative ACK. In addition,
RPC ships the congested link's bandwidth
information which can be computed by
where is the congested channel ID, 
the bandwidth
of channel 
, and the total number of active channels.
Finally, after sending loss information, RPC begins
releasing ACKs-on-hold, if any, so that the sender
can calculate the exact in-flight packet number, inflate
the congestion window size, and send more data packets
via other uncongested links.
Second, it makes fast recovery accurately
react to congestion, and thus, improves network utilization.
TCP-PRISM reduces the congestion window size only by
the proportion (
) of congested link's bandwidth over
total bandwidth--we call this adjustment
Additive Increase and Proportional Decrease.
This adjusted window size allows the sender to
transmit more data via uncongested links.
If there are other congested links,
TCP-PRISM performs the same procedure as the first
reduction step.
Other than the above two enhancements, TCP-PRISM works
exactly same as the way vanilla-TCP does.
Within the network layer, there are three places for the PRISM-IMUX filter to be registered (at entrance, NF_IP_PRE_ROUTING; in the middle, NF_IP_LOCAL_OUT; and at exit, NF_IP_POST_ROUTING), and it is registered at the layer's exit because this placement minimizes the number of functions that PRISM-IMUX should incorporate, and avoids any need for system modification. When it transmits multiple packets stored in its buffer, PRISM-IMUX can make a direct call to an interface function of the link layer, and thus, it need not go through all the remaining network-layer functions.
Finally, there is a case where the agent of the filter needs to store packets, and thus stop the remaining packet processing chain in the network layer. There are two options (NF_DROP and NF_STOLEN) from Netfilter to silently store a packet, and PRISM-IMUX uses NF_STOLEN because it does not incur any overhead such as buffer-copy which is required in NF_DROP.
For the Internet infrastructure, we use one server (Pentium-IV 1.64 GHz CPU with 512 MB memory), one proxy, one WWAN emulator (both are a Pentium-III 865 MHz CPU with 256 MB memory), and one Ethernet switch. The server and the proxy have TCP-PRISM and PRISM-IMUX installed, respectively. The emulator has NISTnet [2] to emulate WWAN networks (the proxy and the emulator each have two Ethernet interfaces to construct different networks). The Ethernet switch works as WWAN access networks and splits traffic from the emulator to each community member. The server, the proxy, the emulator, and the switch in a row are connected via 100 Mbps Ethernet cables between successive components.
For the mobile community, we use three Dell latitude laptops (Pentium-III 865 MHz CPU with 256 MB memory) which have both built-in Ethernet interfaces (Realtek) and IEEE 802.11b interfaces (Orinoco). Each Ethernet interface is connected to Ethernet switch's 100 Mbps cables and is used as WWAN links. A WLAN interface in ad-hoc mode is used for communication within the community.
All machines in the testbed use Redhat 9.0, and an ftp application between a server and a receiver is used to measure end-to-end throughput by transferring a 14MB file.
![\includegraphics[width=4in]{figure/delay_tolerance_h.eps}](img49.png)
|
PRISM effectively masks the delay disparity of WWAN links and provides an aggregated bandwidth through RPC's re-sequencing mechanism. Figure 6 shows that PRISM achieves 95% throughput of total aggregate link capacity when the delay disparity is less than 400 ms. Beyond that point, it shows a little degradation because of deep-buffering for increasing duplicate ACKs. Vanilla-TCP suffers significant performance degradation due to spurious duplicate ACKs. Furthermore, vanilla-TCP with SACK shows worse performance than that without SACK because detailed SACK information delivered to a sender causes significant false retransmissions.
![\includegraphics[width=4in]{figure/loss_tolerance_h.eps}](img50.png)
|
The fast-recovery mechanism in PRISM indeed expedites loss recovery and increases link utilization even at a high loss-rate. As shown in Figure 7, PRISM provides 94% throughput of the total links capacity when loss rates are less than 0.8%. At the point of 0.8% or higher, PRISM's throughput decreases because the achievable link throughput also degrades due to frequent packet losses. Vanilla-TCP, however, experiences a severer performance degradation. Even though it shows relatively good performance (i.e., 90%) at a low loss rate, vanilla-TCP immediately shows degraded performance as the loss-rate increases because of the long loss-recovery time for one congested link, blocking the uncongested link.
![\includegraphics[width=4in]{figure/sce_prism_h.eps}](img51.png)
|
PRISM achieves the aggregated bandwidth of all WWAN links even in case of heterogeneous link characteristics. Figure 7.3.3 shows the sequence number progression of a sender's transport layer for both PRISM and vanilla-TCP. As shown in the figure, PRISM can achieve 310% more throughput than vanilla TCP in the presence of both loss-rate and delay disparities (from 0s to 40s) thanks to its fast loss-recovery mechanism (see the magnified graph in Figure 7.3.3). Furthermore, PRISM yields 208% better performance than TCP in case of a large bandwidth disparity (ranging from 60s to 90s) from its effective scheduling mechanism and ACK re-sequencing mechanism.
), a proxy,
and other hosts (
) for background traffic.
The bandwidth between hosts and their edge router is
20 Mbps, and the bandwidth between routers is 10 Mbps.
![\includegraphics[width=4in]{figure/testtopologye_h.eps}](img53.png)
|
For WWANs, we use the Universal Mobile Telecommunication
System (UMTS) ns-2 extension [5].
is a base-station node that
has support for WWAN links.
For WLANs, we use the IEEE 802.11b implementation in ns-2,
and add NOAH [22] routing protocol
to simulate peer-to-peer communication
among community members. For each community member, we
use an ns-2 mobile node with extension for
supporting multiple wireless interfaces.
We set up a PRISM flow(s) between a sender(s) and a receiver(s), and measure the end-to-end throughput between them. We implement TCP-PRISM (an extension of TCP SACK) for the sender's transport layer, and place PRISM-IMUX at the proxy. We run an FTP application between the sender and the receiver for 150-500 seconds.
links, we randomly choose
each link bandwidth between 400 Kbps and 2.4 Mbps.
We first run an FTP application between a server (
) and
a receiver (
) for 300 seconds under PRISM, and then
run the same experiment without the proxy (`No Proxy').
For better comparison, we also run the same experiment
under a weighted-round-robin (WRR) striping agent
without an ACK-control mechanism.
PRISM achieves the aggregated bandwidth that reaches the sum of link bandwidths, and its performance scales well with the community size. Figure 10 plots the bandwidth aggregation gain by PRISM and confirms the performance gain and scalability with up to five community members.5 By contrast, using the WRR striping agent, TCP performance degrades to the one that is worse than a single community member's throughput due to frequent out-of-order packet deliveries. Note that the ``Ideal'' case is defined as the sum of vanilla-TCP's throughputs achieved in each WWAN link.
)
increases from 0% to 70%, and measure the achieved aggregate
throughput. We initialize the WWAN bandwidth
of all members to 1.4 Mbps. Then, we increase one member's
bandwidth by % of 1.4 Mbps
and decrease the bandwidth of one of the remaining members by
the same percentage. We disable RPC to isolate the
performance benefits of ADAS, and run PRISM with other
existing scheduling mechanisms as well as ADAS for comparison.
![\includegraphics[width=4in]{figure/reorder_gain_h.eps}](img59.png)
|
ADAS reduces out-of-order packet deliveries
by sensing bandwidth disparity, and improves links
utilization. Figure 11 shows
the performance gains on reducing the need for packet
reordering under various scheduling mechanisms.
The 
axis represents the bandwidth disparity,
and the 
axis is an
achieved throughput which is normalized by the ideal total bandwidth
of WWAN links. Although the maximum ratio is below
the half of ideal bandwidth due to the absence of RPC,
the figure shows that the throughput by ADAS improves as the
bandwidth disparity increases by selectively using high-bandwidth
link bandwidth, meaning that ADAS reduces out-of-order deliveries.
On the other hand, since other scheduling mechanisms such as WRR and RR blindly assign packets to all available links without being aware of bandwidth disparity, their performance is degraded by the use of low-bandwidth links, which causes significant out-of-order deliveries.
![\includegraphics[width=4in]{figure/adaptive_on_bg_h.eps}](img62.png)
|
ADAS adapts to the rate/delay fluctuation of WWAN links and reduces the need for packet reordering. As we will see in Section 8.4.2, reduced out-of-order packet deliveries makes an end-to-end throughput improvement, so we measured the throughput achieved by several scheduling algorithms while increasing rate/delay fluctuations. As shown in Figure 12, ADAS outperforms the other scheduling mechanisms by 12% to 47% in the presence of maximum background traffic.
On the other hand, WRR performs worse than random
scheduling in the presence of large fluctuations.
-only scheduling exhibits worse performance than the others because the fast but low-bandwidth link
limits the overall performance by dropping most of packets.
A utility-only scheduling algorithm provides
similar performance to ADAS under stable links state.
However, as the rate/delay fluctuates more, the -only
scheduling becomes less responsive to short-term fluctuations
than ADAS which adapts itself to the fluctuations by using RTT,
and thus achieves only 88% of ADAS's throughput.
RPC achieves maximum network utilization by which PRISM can deliver almost ideal aggregated bandwidth. Figure 13 shows the performance gains achieved by RPC. PRISM with the full RPC indeed achieves maximum network utilization even in the presence of large bandwidth disparities. On the other hand, PRISM's performance without RPC shows less than 50% of ideal bandwidth. PRISM with a partial RPC yields, on average, only a 50% performance improvement since it should depend only on timeouts for packet-loss recovery.
ADAS reduces traffic burstiness by minimizing out-of-order deliveries, and thus improves overall network utilization. Figure 14 shows the progression of the re-sequencing buffer size which is defined as the distance between left and highest of the re-sequencing buffer. The average buffer size required by ADAS in the lower figure is 1.5 times less than that by WRR, meaning that ADAS generates less out-of-order packet deliveries than WRR. Also, the ADAS's smaller buffer size requirement implies a reduced chance for bursty traffic because PRISM-IMUX releases only a small number of stored ACKs to the sender. Our experimental results show that the throughput (2.9 Mbps) for less bursty traffic (scheduled by ADAS) improves up to 16% over the throughput (2.5 Mpbs) for bursty traffic (scheduled by WRR).
CP [12] are
transport-layer approaches to achieving aggregated
bandwidth. They make a transport protocol
have multiple states so that the transport layer can open
multiple connections through multiple interfaces in a single mobile host.
MOPED [8] is a framework to enable group
mobility such that a single user's set of personal devices appear
as a single mobile entity connected to the Internet.
Packet reordering is a major problem in multi-path routing environments. DSACK [23] in TCP is a detection mechanism of spurious retransmissions on packet reordering based on the information from a receiver via DSACK block. TCP-Door [21] is another scheme for detecting packet reordering in a MANET environment. This approach uses additional information, called TCP packet sequence number, to detect out-of-order packets. However, these mechanisms can solve occasional (but not persistent) out-of-order packet arrivals. TCP-PR [6] addresses this problem using a timeout as an indication of packet loss instead of duplicate ACKs, but it may still suffer from false timeouts that result from large RTT fluctuations.
Scheduling packets across multiple links is
a well-known problem, and there are three approaches:
Round-Robin (RR), fair-queuing, and hybrid.
First, the RR scheduling guarantees
long-term fairness, and is of low complexity [4].
However, RR inherently causes traffic
burstiness which may require a large re-sequencing buffer.
Second, the fair queuing attempts to approximate the
Generalized Process Sharing (GPS) to achieve fairness
(e.g., PGPS, WFQ, WFQ). However,
these approaches assume that the exact bandwidths of each input
and output link are known, which is expensive for
resource-limited mobile hosts to obtain.
Finally, a hybrid approach (e.g., [17])
removes the complexity of the fair-queuing approach,
but it also assumes the known/fixed service rate.
We also consider two different security-related issues: (i) what if the packet header is encrypted? and (ii) what if a community member behaves maliciously? Since PRISM exploits TCP information, it is critical for PRISM to extract the header information from each packet. As was done in [19], if we consider the proxy as a trusted party and let it hold the secret key for each connection, then the proxy can extract the header information from encrypted packets. This mechanism also helps prevent members' malicious behaviors from tampering with, or extracting data from, a packet. The other approach to the members' malicious behavior problem is to have a reputation and punishment system as in [7] to discourage such behaviors.
To remedy these problems, we proposed a proxy-based inverse multiplexer, called PRISM, that effectively stripes a TCP connection over multiple WWAN links at the proxy's network layer, masking adverse effects of out-of-order packet deliveries by exploiting the transport-layer information from ACKs. PRISM also includes a new congestion control mechanism that helps TCP accurately respond to the heterogeneous network conditions identified by PRISM.
Through experimental evaluation on a testbed and in-depth simulations, PRISM is shown to opportunistically minimize the need for packet reordering, effectively achieve the optimal aggregate bandwidth, and significantly improve wireless links utilization.
![\begin{algorithm}
% latex2html id marker 295
[t]
\begin{small}
\caption{ADAS\_Sc...
...$}
\STATE \textbf{return} $l_{next}$
\end{algorithmic}\end{small}\end{algorithm}](img15.png)
![\begin{algorithm}
% latex2html id marker 651
[t]
\begin{small}
\caption{ACK re-s...
...k}
\STATE \textbf{end switch}
\ENDIF
\end{algorithmic}\end{small}\end{algorithm}](img40.png)
(background traffic generator), a Proxy,
(community members), and 
(receiver)![\includegraphics[width=4in]{figure/total_gain.eps}](img57.png)
![\includegraphics[width=4in]{figure/rpc_gainse_h.eps}](img63.png)
![\includegraphics[width=4in]{figure/reseq_distance.eps}](img64.png)