Transcript Proxy-based Multpath Routing

On Proxy Server based
Multipath Connections
(PSMC)
PhD Proposal
Yu Cai
12/2003
University of Colorado at Colorado Springs
Outline

1. Introduction

2. Related work

3. PSMC algorithms

4. PSMC protocols

5. PSMC applications

6. PSMC security

7. Conclusion
Introduction

Single path connection: most commonly-used
network connection model in today’s network
environment.

Multipath connections: provide potentially multiple
paths between network nodes. The traffic from a
source can be spread over multiple paths and
transmitted in parallel through the network.
Single path connection vs. multipath connections
Why Multipath Connections

Improve the network security by providing alternate paths

Improve the network reliability, stability and availability

Improve the network performance by increasing the
aggregate bandwidth between network nodes

Utilize the network resources more efficiently

Cope well with network congestion, link breakage, burst
traffic and potential attacks

Provide better quality-of-service
Related Works on Multipath Connections

Multipath connections have been studied since 70s.



The IBM Systems Network Architecture (SNA) in 1974
Nicholas F. Maxemchuk in 1975, the dispersity routing
Classification of multipath connections based on OSI
7-layer model.


Physical layer: Multipath Interference; Antenna Array.
Data link layer: Link Aggregation, defined in IEEE 802.3ad.
(requires additional hardware support)
Related Works on Multipath Connections


Network layer: studied extensively as multipath
routing.

Wired network. (requires changes on routers)
 Table-driven routing (link state or distance vector).
MDVA(Multipath distance vector algorithm ) [VG01];
[Chen98]

Wireless ad hoc network. (only for ad hoc network)
 On-demand routing.
SMR(Split Multipath Routing ) [LG00],
 Source Routing.
MSR(Multipath Source Routing ) [ZZS+02]
Transport layer: Linux multipath connections for
multiple ISP connections. (no fail-over mechanism).
Proxy Server based Multipath Connections (PSMC)

Existing multipath connection approaches have
various limitations and drawbacks.

We want new solution:


Must be compatible with current network and don’t require
changes on network infrastructure;

Must be robust and reliable with high performance;

Must be flexible when deployed so more applications can
benefit from it.
We propose to study a new multipath connection
approach: proxy servers based multipath connections
(PSMC).
The Key Idea of PSMC

The key ideas of PSMC is as followings.

By using a set of connection relay proxy servers, we could
set up indirect routes via the proxy servers, and transport
packets over the network through the indirect routes.

By enhancing existing TCP/IP protocols, we could efficiently
distribute and reassemble packets among multiple paths at
two end nodes, and increase end-to-end TCP throughput.

The approach offers applications the ability to improve
network security, reliability, performance, stability, availability
and efficiency.
PSMC Diagram
Three Key Parts in PSMC

The multipath sender: distributes packets over the
selected multiple paths efficiently and adaptively.

The intermediate connection relay proxy servers:
examine the incoming packets and forward them to
the end server.

The multipath receiver: collects the packets from
multiple paths, reassembles them in order and
delivers them to the user.
Why PSMC

Compatibility: Utilizes existing TCP/IP protocols and
network infrastructure. Don’t require changes on
physical network infrastructure.

Flexibility: Can be more conveniently and adaptively
deployed in various network environments.

Usability: A large number of applications in various
categories could benefit from utilizing PSMC.

Reliability: Reliable and robust protocol with high endto-end performance.
Algorithms for PSMC

Proxy server selection is a critical decision in PSMC.
Different server selections result in different
performance.

Needs to solve the following two proxy server
selection problems.
1) Server Selection Problem.
Given the target server and a set of proxy servers, choose the
best proxy server or servers for a client or for a group of clients, to
achieve the maximum aggregate bandwidth.
2) Server Placement Problem.
Given the target server and a set of network nodes, choose the
best node(s) to place the proxy servers, to maximize the
aggregate bandwidth.
Diagram of Sever Selection / Placement Problem
How to avoid joint paths
when selecting proxy
servers? (joint path might
become potential bottleneck)
How to select
geographically diverse
proxy servers?
Server selection problem
Server placement problem
Related Work on Algorithms



Mirror server and cache server selection problem has
been studied recent years.
Formal approach: abstract network model; use graph
theory.
Common assumptions when getting network model:
a) network topology is known,
b) the cost associated with each path is known,
c) single and static network connections.

Algorithms include [QPV01]:
(selecting M replicas among N potential sites)
tree-based
greedy
random
hot spot
O(N3M2)
O(N2M)
O(NM)
N2 + min (NlogN, NM)
Algorithms for Parallel Download Problem


NP-hard problem. We plan to develop heuristic
algorithms, or by loosing the optimal constrains to
simplify the problem to make it solvable in P-time.
We have developed genetic algorithms to choose best
mirror sites for parallel download from multiple mirror
sites. The problem can be viewed as a sub problem of
PSMC.
Parallel Download Algorithm Performance
Performance result of the parallel download algorithms
tested on the simulated network and real-world network
looks promising.
algorithm execution time vs. simulated network size
35
50
45
30
25
35
30
20
25
15
20
15
10
10
5
5
0
20(10)
0
114(11)
150(20)
200(20)
300(30)
500(50)
800(100) 1000(100) 1000(200)
number of simulated network nodes
BF-pds
BF-k-pds
GA-k-pds
GA-pds
GA algorithm execution time
(second)
BF algorithm execution time
(minute)
40
PSMC Protocols: Packets Handling


Protocols need to be designed for packets handling:

Distribute / reassemble packets: add a thin layer between
TCP and IP. Modify the Linux kernel.

Transmit packets: use IP Tunnel or IPSec to enable indirect
routes.
Why adding a thin layer for packets distribution and
reassembling?

Utilize existing TCP protocols, particularly the packets resequencing and re-sending mechanism.

Hide the complexity of multipath connections from end user.

Maintain the high end-to-end TCP throughput.
PSMC Protocols: IP Tunnel



IP tunnel is a technique to encapsulate IP datagram
within IP datagram. This allows datagram destined
for one IP address to be wrapped and redirected to
another IP address.
IPSec is an extension to the IP protocol which
provides security to the IP and the upper-layer
protocols. The IPSec architecture is described in the
RFC2401.
Why IP Tunnel:




IP Tunneling is well developed and widely available.
It is a layer 2 protocol, transparent to higher layer.
IP Tunneling performance is acceptable.
We have investigated other approaches including SOCKS
proxy server and Zebedee, which don’t fit our needs.
Special Issues for PSMC Protocols

Several special issues for PSMC protocols:

Based on the feedback from end server, dynamically adjust
packets distribution.

Outgoing packets might contain redundant information and/or
probing message.

Fail-over mechanism, packets resend and re-sequencing
mechanism, when packets are lost or connections are
broken.
Sticky-connection mechanism: when some packets need to
be sent through a particular path.


Related work:

ATCP (ad hoc TCP) [LS01].

Linux Virtual Server (LVS).

Virtual Private Network (VPN)
IP Tunnel and IPSec
PSMC Diagram
PSMC Applications

Secure Collective Defense (SCOLD) network

PSMC in wireless ad hoc network.

Indirect route / additional bandwidth upon operational
requests.

QoS for video streaming.

Parallel download from multiple mirror sites.
Secure Collective Defense (SCOLD) network

SCOLD tolerates the DDoS attacks through indirect
routes via proxy servers, and improves network
performance by spreading packets through multiple
indirect routes.

SCOLD will incorporate various cyber security
techniques, like secure DNS update, Autonomous
Anti-DDoS network, IDIP(Intrusion Detection and
Isolation Protocol) protocols.

The prototype of SCOLD system version 1.0 is
finished with secure DNS update and indirect route.

We plan to enhance SCOLD for better scalability,
reliability, performance and security.
SCOLD: victim under DDoS attacks
A.com
a
a
A
a ... a
DNS1
B.com
b
b
B
C.com
b ... b
c
DNS2
C
c
c ... c
DNS3
DDoS Attack Traffic
Client Traffic
R
DNS
R3
Victim
R2
R1
Back door: Alternate
Gateways
target.com
Main gateway R under attacks, we want to inform Clients to go through the “back door” - alternate gateways R1R3. We needs to hide IPs of R1-R3, otherwise they are subject to potential attacks too.
how to inform Clients? how to hide IPs of R1-R3?
SCOLD: raise alarm (1) and inform clients (2)
A.com
a
a
A
a ... a
DNS1
B.com
b
b
B
C.com
b ... b
c
DNS2
C
c
c ... c
DNS3
Proxy1
DNS
Reroute
Coordinator
R
R3
target.com
R2
R1
Victim
1. IDS on gateway R detects intrusion, raise alarm to Reroute Coordinator.
2. Coordinator informs clients for new route:
a) inform clients’ DNS; b) inform clients’ network proxy server; c) inform clients directly;
d) inform the proxy servers and ask the proxy server do (a – c).
1: raise alarm
2: inform clients
SCOLD: set up new indirect route (3)
A.com
a
a
A
B.com
a ... a
b
DNS1
b
b ... b
c
DNS2
C
B
Proxy1
C.com
Proxy2
R
R3
R2
R1
target.com
Victim
3. Clients set up new indirect route to target via proxy servers.
c ... c
c
DNS3
3: new route
Proxy3
Reroute
Coordinator
DNS
Proxy servers: equipped with IDS to defend attacks; hide alternate gateway and reroute coordinator; provide potential multiple paths.
SCOLD Testbed
Preliminary result of SCOLD
Table 1: Ping Response Time (on 3 hop route)
No DDoS attack
direct route
DDoS attack
direct route
0.49 ms

225 ms
DDoS attack
indirect route
0.65 ms
0.65 ms
Table 2: SCOLD FTP/HTTP download Test (from client to target)
No DDoS attack,
Doc
FTP
HTTP
direct route
100k
Size 0.11 s 3.8 s
250k 0.28 s 11.3 s
500k 0.65 s 30.8 s
1000k 1.16 s 62.5 s
2000k 2.34 s 121 s

No DDoS attack
indirect route
DDoS attack,
FTP
HTTP
direct route
8.6 s
9.1 s
19.5 s 13.3 s
39 s
59 s
86 s
106 s
167 s
232 s
No DDoS attack,
FTP
HTTP
indirect route
0.14 s 4.6 s
0.31 s 11.6 s
0.66 s 31.1 s
1.15 s 59 s
2.34 s 122 s
Table 3: Time to Set up Indirect Route in SCOLD
Ping
Less than 1 s
HTTP
Less than 1 s
FTP
Less than 1 s
with DDoS attack
FTP
HTTP
indirect route
0.14 s 4.6 s
0.31 s 11.6 s
0.67 s 31.1 s
1.15 s 59 s
2.34 s 123 s
PSMC Applications Evaluation

The performance and overhead of multipath
connections will be evaluated.

PSMC will be compared with other multipath
connection approaches, like source routing, and
Linux multipath connections.

Extensive simulation study on PSMC applications in
virtual network, real network, small scale network and
large scale network will be conducted.
Security Issues Related to PSMC

Potential security issues raised by misusing of
PSMC: how to control aggressive clients?

Potential attacks against PSMC: Tunneling to death?
(similar to ping to death).

How to detect and deal with comprised nodes in
PSMC network?

Study the collective defend mechanism to tie different
organizations with better cooperation and
collaboration.
Research Plan

Will systematically study PSMC in the following
areas:
 Algorithms for server selections
 Protocols for packet handling
 Applications
 Security issues
Thank you!