Transcript Task Title Placed Here - Case Western Reserve University

Intelligent Quality of Service Routing for Terrestrial and
Space Networks
Funda Ergun
Case Western Reserve University
Page 1
Our Goal
Given a space, terrestrial, or hybrid network
consisting of aerospace, near earth and
terrestrial components, design architectures
and protocols which will allow for faster, more
reliable and cost-effective routing with Quality
of Service, with the ability to learn from
experience.
Page 2
Quality of Service
•Network has various components—satellites, terrestrial
routers, PCs, mobile devices. Topology may change in time
•Different transmissions require different parameters
•Existing protocols provide basic service, not much more:
IP/BGP provide policy/shortest path routing. MPLS provides
label switching, supports path allocation/backup paths and
more intelligent path selection, thus is suitable for
incorporating new algorithms.
•Cost is a major issue
Page 3
Example Multicast Routing
Network of 7 multicast, 7 non-multicast nodes and
the multicast tree
Page 4
Problem Model
Unicast: Find best path between two nodes that
respects constraints , minimizing overall cost.
Multicast: Find best tree that goes to all multicast
nodes, respecting constraints, minimizing cost.
Current Internet: find shortest path for unicast.
No good algorithm for multicast.
Page 5
Constraints
We would like our routing to:
•Respect bandwidth, reliability, delay, cost concerns.
•Be adaptable to changes in topology.
•Not require much computational power, allow policy routing.
•Use past experience to make decisions.
Intractable!!! One can resort to heuristics/approximation algorithms. Then,
must check:
Running time with realistic data
How “good” the routing is performed.
Page 6
Solutions and Testing
Techniques:
•Rounding and scaling of data for approximation
•Lagrangian relaxation
•Estimating future resource allocation.
Simulation: Various types, sizes of networks for both multicast
and unicast. Various types of demands considered.
Results compared to best solutions, as well as other known
techniques.
Page 7
Test Results
Simulation Results
If all of desired values stay within bounds, our algorithms find
solutions that cost up to 5% more than the optimal solution in
around 100msec for 50-100 node networks for unicast, up to
15% more for multicast networks.
Finding the optimal multicast routing for a 10-node network takes
a full day; at 12 nodes it cannot be done.
[ESZ], [ESZ2], [WEX].
Page 8
Next Step, Concerns
Building Protocols
•Message passing and data storage requirements: most of the
data is kept in the routers.
•Not all nodes need to have access to all the information. Using
hierarchical routing, data dissemination needs can be minimized.
•Header lengths need not become very long; MPLS-like
structure.
•Routing data can be translated into diffserv-like class system.
Page 9
Papers
F. Ergun, R. Sinha, L. Zhang. Routing with Performance Dependent Costs. Submitted to IEEE/ACM
Transaction on Networks.
F. Ergun, R. Sinha, L. Zhang. An Improved Algorithm for Restricted Shortest Path Routing.
Information Processing Letters, 2002.
F. Ergun, D. Wang, Z. Xu. Unicast and Multicast Routing with Multiple Constraints. Submitted,
available as CWRU Technical Report.
Page 10