Transcript RATES

RATES: A Server for MPLS
Traffic Engineering
(Routing And Traffic Engineering Server)
P.Aukia, M.Kodialam, P. V. Koppol, V.
Lakshaham, H. Sarin, B. Suter
Zlatokrilov Haim
Advanced Topics in IP Networks
Tel-Aviv University
5/1/2001
Schedule
Introduction
MPLS Architecture
Traffic engineering
Architecture considerations
On-line routing
On-line routing-RATES approach
RATES software
MPLS
Picture
Playground
Goal:
Make best use on network structure
One of the solutions:
Explicit routing in MPLS
Implementation
RATES
IP Routing
Shortest paths computed using mostly static
(usually traffic characteristic independent) link metrics
Enough for connectivity
Possibly bad use of available network resources
• Unable to use alternate paths
• Potential for better QoS on the same infrastructure
Traffic engineering & MPLS
MPLS ability to control path from Ingress
to Egress can optimize utilization
Offline Routing
All tunnels or LSPs and resources requests
are know at the time the routing is done
Can be very affective
In practice demands may change in time
Problem: accommodate of new requests
Possible solution: rerouting of existing
connections (not desirable)
On-Line Routing
Depends on information from routing
protocols (OSPF IS-IS)
In LSP this link state database could be used
Difficult to obtain delay and buffer usage
RATES: uses only link state and bandwidth
information for path selection
MPLS and Bandwidth guaranteed LSPs
Usage of LSPs as components of an IP VirtualPrivate-Network (VPN) with bandwidth
guaranties to satisfy Service-Level-Agreements
(SLA).
LSP is then a “virtual traffic trunk” for flows with
“Forwarding Equivalence Classes” (FEC)
Classification of traffic (ToS bits, source etc.)
FECs from policy server or other protocols
Enables Traffic Engineering and classification along
with signalling protocol like RSVP CR-LDP
LSPs in RATES
Uses bandwidth guaranteed routes
What about other SLA metrics like: Jitter, Loss,
Latency?
Concentrating on BW because the most common
If other SLA constrains -> convent the SLA to traffic
effective BW ?!
Taking other metric into account is too complicated
(policies etc.)
Architecture Considerations
and Design Choices
Centralized vs. Distributed
implemetation
The algorithms used in RATES use only
information obtainable distributedly via
extensions to routing protocols (OSPF and ISIS extensions for traffic engineering)
“Until the completion of standards distributed
implementation is not desirable” ?!?!?!?!
Maybe it’s just easier…
Obtaining link state information
SNMP (Simple Network Management Protocol)
Standardized MIBs for QoS related link and nodal
attributes
Get link state data as part of protocol operation
(only if extension exists)
RATES – OSPF peering to obtain topology
information and node states (up/down)
GUI for providing parameters as BW etc.
Responsible for all BW allocation, enables keeping
track of reserved and available BW.
LSP Route Computation
Triggered by:
Request from ingress node
Network administrator
LSP path setup is done using on-line routing
algorithm
Re-routing upon link failure
alternate routes for as many LSPs as possible
Policies
Packet classification for redirection of IP
packets to LSPs
Routing tables that use LPS as next hop
RATES provides GUI for administrators to
specify these policies
Installing an LSP route
Hop-by-hop provisioning (like ATM)
Server communicates with source of route
and spawns signalling from source to
destination for route setup (like soft PVC in
ATM)
RATES: second option
No standards
Using COPS
COPS
Common Open Policy Server
PDP & PEP
Framework
COPS vs. SNMP
RATES uses COPS for:
Installing packet classifiers
Installation of LSPs
SCALE
RATES operates on a network within single
OSPF area
Get a complete and not summarized view
(easier for traffic engineering)
LSP Restoration Options
Multiple levels of rerouting by reaction time/BW/
efficiency
Path protected by backups:
Full associated BW reservation
Shared or partially shared BW (requires extensions for
MPLS)
Rerouting decision made by ingress router, no
interaction with RATES needed
Administrative rerouting is possible as well
On-Line Routing
Along path:
Residual BW=link BW–sum of LSP demand
Feasible link: if BW demand < link BW
Feasible network: all feasible paths
Objective: reject as few LSP request as
possible
On-line routing-State of the ART
Min-hop algorithm (least number of feasible
links
Simple
Not taking ingress-egress pair information
Does not adapt routing to increase successful
rerouting
Easy to improve
Other Proposals
Widest Shortest Path algorithm (WSP)
Feasible min-hop path with maximum residual
path bottleneck link capacity
Not taking ingress-egress information into
account
Without min-hop restriction does not work
well
Cont…
Other algorithms:
Taking residual BW on link to influence the
weight
Paths chosen with respect to dynamically changing
weights
Idea: Not to use link capacity completely if alternate
lower loaded path available
Disadvantage: not taking ingress-egress
information, may make long paths
On-line routing-RATES approach
Minimal Interface routing
Route using a shortest path computation on
an appropriately weighted graph
Example
All links with residual BW of 1 unit
Request for LSP between S3 and D3 with BW=1
In min-hop: the route in 1-7-8-5
1-2-3-4-5 is better even though longer
Possible Objectives of on-line
Routing
Key idea: pick paths that do not interfere too much
with optional future LSP set-up requests between
other source-destination pairs
Look for path that maximizes the minimum maxflow between all other ingress-egress pairs
Another possible objective: pick a path that
maximizes a weighted sum of the max-flows
between every other ingress-egress pair
Cont…
“Critical links”link with a property that whenever an LSP is routed the
max-flows values of one or more ingress-egress pairs
decreases
Algorithm for computation of such links
RATES: generating weighted graph where
“critical links” have weights with increasing
function.
The actual route is calculated using shortest path
algorithms
RATES Software Architecture
Work within heterogeneous network
Only requirements: MPLS and RSVP capable
Java and C++ in Unix
Each module is a Unix process
Event driven with message bus
Based on CORBA
Major modules
Features
Definition of constrains
Monitoring the network topology
Provisioning of LSPs
Alert on certain anomalous events
Graphical User Interface
Application Programming Interface
Explicit route computation
Uses network state, policies and user requests
Based on “minimum Interface” algorithm
Easy addition of modules like
specifying SLAs by additional parameters
Addition of path computation algorithms
Restoration of LSPs
Let RATES detect failures, and then
explicitly reroute LSPs if needed
Usage of backup paths
Simultaneous setup with active path
Complete path protection (Sharing of backup
paths)
Single link protection (Better BW usage)
COPS Policy Server
Very little application specific semantics
Allows extensions
Client requests and Server replies and server
asynchronous updates
In RATES:
Extensions for intra-domain traffic engineering
Installation of policies
For those do not support COPS modifications are
required
Network Topology and State Discover
Could be set fed statically
Dynamic data can be accepted using SNMP
Auto discovery of topology by OSPF
protocol entity for topology and state
discovery
Edge Routers Requirements
Designated Ingress and Egress points of
traffic engineering domain
Needs to support:
MPLS tunnels and signalling RSVP+extensions
Filtering at packet route level
COPS with the required extensions
Thanks for the
attention