Transcript Constraint-Based Unicast and Multicast: Practical Issues

Constraint-Based Unicast and Multicast:
Practical Issues
Bala Rajagopalan
NEC C&C Research Labs
Princeton, NJ
[email protected]
1
IMIC, 8/30/99
What is Constraint-Based Routing?
• Includes QoS-based routing and policy routing
• New jargon to establish technical territory
• Devised in the context of MPLS LSPs, but applies to microflows also
(generically, “flows”)
Link with bw, delay, loss
properties
Dest
Source
Flow with BW,
Delay, Loss &
Policy
Requirements
2
Inter-domain
routing policies
IMIC, 8/30/99
Network with
bw, delay, loss
properties
A Methodology for IP Network Design
• Constraint-based routing capability results in efficient design and resource utilization
Scheduling &
Buffering Scheme
Node-Pair Traffic
Demands & Initial
Topology
Traffic Flow
on Links
Flow
Routing
Link Capacity
Determination
Topology Optimization
3
IMIC, 8/30/99
Network Topology
& Routing
Traffic Engineering and Constraint Based Routing
•
•
Current TE goal is to map traffic onto the network such that available resources are
utilized efficiently and QoS requirements of traffic is satisfied
MPLS LSPs are envisioned for creating virtual trunks that carry traffic between node
pairs (equivalent of frame-relay or ATM PVCs). LSPs isolate resources for different
flow aggregates
LSP 1
Routing constraints:
• Resource requirement
• Priority & Preemption
LSP 2
• Policy
• Resiliency requirement
Microflows within an LSP
Re-optimization of routing
LSP 3
4
IMIC, 8/30/99
Service Models (1) : VPN
•
•
Customer provides point-to-point demands and QoS requirements
Service provider capacity engineers and establishes virtual trunks (LSPs)
Internet
SP Network
Virtual Trunk
5
IMIC, 8/30/99
Service Model (2) : Diffserv
•
Service provider establishes SLAs with customers
– SLAs indicate service quality based on traffic parameters
– SLAs need not require customer specification of traffic matrix
 Network design is difficult
dest
SLA3
SLA1
SLA4
SP2
SP1
source
SLA2
6
IMIC, 8/30/99
Traffic from source to dest must
receive treatment as per SLA1,
even though it goes through a
foreign SP. Also, dest may not be
known apriori.
Traffic Engineering for Diffserv
•
In principle:
– Derive point-to-point demands from SLAs and traffic measurements
– Determine virtual trunking requirements between node pairs
– Establish trunks using CBR
dest
SLA3
SP1
SLA4
SLA1
SP2
source
SLA2
7
IMIC, 8/30/99
Virtual Trunks
Constraint-Based Routing Model in Summary
• Given: Network topology, resource availability, policy and other
attributes of nodes and links
• Flows: Aggregated microflows or virtual trunks
• Dynamism: Keep track of network state changes; dynamic rerouting of
flows after topological changes; redundant paths and load-balancing?
• Routing architecture: Distributed
• Route computation: Based on apriori notions of optimization of
resource usage, traffic parameters, routing metrics, etc.
• Route computation trigger: By operator using offline mechanisms
• Route maintenance: Based on specified policies
• Multicast: ??
8
IMIC, 8/30/99
Practical Issues
• Scalability: No experience with large-scale state-dependent routing in
the Internet; current proposals limited to intradomain flat networks
• Interdomain Routing: State transfer between domains for CBR?
• Flexibility in Routing: CBR, being a tool for optimization, invites
proprietary solutions. How to accommodate a plurality of solutions?
• Multicast: What is the model?
– Static trees, computed centrally
– Dynamic trees on a per-group basis?
• Integration within a service management framework: Defining the
interfaces to capacity management, provisioning, and offline network
analysis.
9
IMIC, 8/30/99
CBR Approach 1: IGP Extensions (e.g., OSPF)
•
•
Add CBR features to existing IGP s.t. changes are minimal
Some IGPs provide mechanisms for adding new messages, e.g., OSPF transparent LSAs
Area 1
Area 2
New route computation proc.
New update procedures
Flood Resource LSAs
New resource tracking proc.
(only bw defined so far)
Existing DB representation
Only single area considered
10
IMIC, 8/30/99
CBR Approach 2: Proprietary Protocols
•
•
•
Proprietary message formats, update protocols, hierarchy arrangements, database
representation, etc.
Proprietary CBR features: Flow definition, priority, preemption, rerouting features, etc.
Requires homogeneous equipment
Area 2
Proprietary Flooding
Area 1
11
IMIC, 8/30/99
CBR Approach 3: Distributed Overlay
•
•
•
•
Utilize underlying IGP (DV or link state) for reachability computations
Efficient update propagation techniques for scalability (facilitates dynamic routing)
IGP-independent state representation
– State aggregation for hierarchical routing possible
– Metric values not constrained by IGP limitations
Requires only the definition of a standard interface between IGPs and CBR protocols, to be
implemented locally
CBR Protocol
CBR Database
To Peers
Topology Mapping &
Interface Functions
To Peers
Intra-domain LS Protocol
12
IMIC, 8/30/99
LS Database
CBR Overlay: Essential Ideas
•
•
•
CBR protocol utilizes underlying IGP for building an MST of the topology (MST based
on administrative link cost)
State information broadcast on the MST
State information synchronized and maintained as MST changes
– Requires interface function to indicate topology change
To nodes E-I
A
Pt-to-Pt or broadcast link
A: Mcast updates from E-I, request sync.
B: Unicast updates from J-M
C: Unicast updates from N-Q
To nodes N-Q
Router
B
C
To nodes J-M
D
To nodes R-W
Network and MST
CBR sync. on a LAN
13
IMIC, 8/30/99
CBR Overlay on OSPF
•
•
•
•
Hierarchical MST construction; one for each area and one for the backbone
CBR topology database generated from OSPF database using interface functions
Independent representation of network state, including summary state for external areas
Updates sent on backbone MST are propagated on area MSTs
Area 1
Area 1
Backbone Area
Area 2
14
Backbone Area
Area 2
IMIC, 8/30/99
Route Computation
15
IMIC, 8/30/99