Transcript Slides

Dynamic routing – QoS routing
• Load sensitive routing
• QoS routing
Load sensitive routing
• In what we have seen in this class so far costs are
static
– Administrator configures them
• Why not try to adapt to the conditions of the
network?
– Use less loaded links
– Use links with less delay
– Use links that have less loss
• Two problems:
– Need to know the condition of the links
– Can have positive feedback
• Oscillations
In the very early days
• In ARPANET, from 1969
– Delay SPF: compute shortest paths based on the delay on a link
• Use the queue length to estimate it
– Delay values where exchanged each time they changed
significantly
• But (usually under heavy load):
–
–
–
–
–
A link that has low delay may become too attractive
Traffic will start using it
Delay will increase, will become less attractive
Traffic will stop using it and so on…
Oscillation
• Oscillations cause too many advertisements, too much
CPU load on routers, and low utilization of some of the
links
Improvements
• The “revised” Internet Metric
– Metric advertised should be relative to other links and
not just the queue length
• If average link cost is 10 advertise 20 when link is overloaded
• 20 is almost like two links
• Some traffic will start using paths that are 1 hop longer
– Have a lot of damping in the advertisements of metrics
– Result in more gradual changes in traffic and link
utilization
• There will still be oscillations
– Smaller magnitude
– Better overall network utilization under heavy load
But only a single metric
• SPF can have only a single cost value per link
– SPF can not compute paths that minimize two metrics
– Unless I do a linear combination of all into a single
value
• Example
– EIGRP from Cisco allows to advertise dynamic
information and select paths using it
– Combines multiple performance metrics into a single
per-link value
• Load sensitive routing is mostly abandoned today
– Oscillations are very undesirable
ToS routing
• What we have today is Type of Service (ToS)
routing
– Even than is not really used
• IP packets have 4 bits of ToS in their header
– Some combinations have pre-assigned meaning
• 0100 = max throughput
• 1000 = min delay
• Etc…
• In principle routers compute different routes for
each of these bits
– Links may have different costs for each ToS value
– OSPF can advertise different link costs for each ToS
Oscillations revisited
• Oscillations happen because traffic can shift
around
• What happens if I could “pin” traffic on a
certain path?
– Using source route, MSPL LSP, or some other
explicit routing technology?
– No more oscillations
• Now I need to find good paths for traffic
– From source S to destination D
– Satisfying one or more QoS constraints
– This is “QoS Routing”
Quality of Service (QoS)
• Quantitative metrics that express how well
my traffic is treated
• Most common
– Delay (end-end or per link)
• Queuing delay
• Propagation delay (hop length related)
– Loss
– Jitter (delay variation)
– Available bandwidth
• A QoS guarantee tells me that one of the
above metrics will have a bounded value
How to achieve QoS
• Need to schedule resources in each
router/link
– Link transmission slots
• To ensure available bandwidth
– Queue lengths and entries
• To ensure that a packet will not be delayed by
queuing too much
– Buffers
• To ensure low loss rates
• Huge body of work on resource scheduling
for QoS
Reservations
• Assume I found a path that satisfies the
requirements
• To ensure I get the requested service I will need to
reserve resources on the path
– Reserve the 100 Mbit/sec bandwidth
– Reserve queue entries and link scheduling resources to
limit my latency, loss and jitter
• After reservation, less resources are available to
other traffic
– Admission control
– New traffic may be rejected if there are not enough
resources available
Signaling
• Combine path pinning and resource
reservation in a single signaling step
• Not unlike setting up an LSP with RSVPTE
• Two pass
– Forward pass:
• send the request
• perform admission control
• Initial reservation
– Reverse pass:
• Fine tune reservations
QoS routing
• Find a path to destination D with end-end
delay=20 msec, loss rate < 1% and available
bandwidth 200 Mbit/sec
• How to find the path?
– Need to have an algorithm to compute a path
that satisfies all these constrains
– Need to have up to date information about what
happens in all links and nodes in the network
Metric types
• Additive metrics:
– The metric for the path is the sum of the metric for the
links of the path
– Delay, jitter
• Multiplicative metrics:
– The metric for the path is the product of the metrics for
the links of the path
– Loss rate
• Bottleneck metrics:
– The metric for the path is the largest (or smaller) of the
metrics for the links of the path
– available bandwidth
Constrained path computation
• How to find a path that optimizes multiple
metrics?
– E.g a min delay and min loss path?
• How to find bounded paths?
– E.g. a path that has delay < 50 msec and available
bandwidth > 100 Mbit/sec
• Well I can not [Wang, Crowcroft 1996]
– More than 1 additive and/or multiplicative metrics is
NP-complete
• 1 additive + 1 multiplicative, 2 additive, 2 multiplicative: all
NP-complete
• 1 additive, 1 multiplicative: OK
All is not lost
• Available bandwidth allows some flexibility
– Find paths that have at least B bottleneck
bandwidth and satisfy 1 more condition is
possible
• Prune all links that have less than B available
bandwidth
• And then compute the best path for the second
metric
– E.g delay and bandwidth, bandwidth and loss,
bandwidth and jitter are all possible
Example
• Delay and bandwidth: path with bandwidth
100 Mbit/sec and delay < 10 msec
– Prune all the links with less than 100 Mbit/sec
available bandwidth
– Run SPF to find the least delay path to
destination
– If least delay > 10 msec no path exists
– If delay <= 10 msec found my path
Pre-computing QoS routes
• I may have a lot of incoming requests for QoS
routes
– Computation of routes may become an issue
– Pre-compute routes
• But for pre-computed routes I do not know the
QoS requirements of the requests
– Compute a range of paths for all possible requests
• More storage
• E.g. compute paths with 10, 100, 1000 Mbit/sec available
capacity and 10, 20, 40 msec delay
• When a request comes, fit it in the appropriate path
– Compute the “widest” paths for different hop lengths
and use the shortest one where the request can fit in
• “shortest-widest” path
A “good” routing algorithm?
• What is the optimization goal?
– To fit as much traffic as possible in the network
• Increases utilization of resources
• Increases revenue
– A request is blocked when it can not find a path with
the QoS it needs
– Reduce the blocking
• Number of requests blocked
– Requests have different bandwidth requirements
• Sum of bandwidth of the blocked requests
• Routing algorithm A is better than B if:
– for a given set of requests A can achieve less blocking
that B
Hard to evaluate
• Needs simulation
• Traffic models are not known
– What kind of QoS traffic will want
– How big/small are the bandwidth requests
• Relative to the link sizes
• Topology has a very large effect
• Traffic patterns too
– Hot-spot vs. uniform load
– Overall load in the network
• No standards exist for QoS routing performance
evaluation
Why QoS routing works
• Conventional routing uses only the shortest
path(s) (maybe more than one)
– Resources on other links are underutilized
• QoS routing can switch traffic to longer
(alternate) paths when the shortest paths fill
up
– Better network resource utilization
– Less blocking
• Only if there are unloaded alternate paths
– If network is heavily loaded and all paths are
full QoS routing can not do much
Problem
• QoS routing works on-line
– Given a set of requests I find a route and
establish it one by one
– The path I find for a route will affect the
availability of paths for future requests
– Picking a bad route now may result in blocking
many future requests
– EXAMPLE
• How can I ever optimize for requests that
do not know yet
– Have to rely on heuristics
Optimization heuristics
• Longer or shorter paths?
– Shorter paths use less resources in the network
– Avoid completely very long paths
• Best or worse fit?
– If I fit request too tightly on a link I cause bandwidth
fragmentation
• May cause blocking later on
• Trunk reservation
– Traffic on alternate paths may starve traffic that could
use the shortest paths
– Reserve some amount of resources on the shortest paths
Amount of update traffic
• When conditions change on a link send an update
• In an IGP updates are flooded
– If conditions on a link change very frequently there will
be a lot of updates
– A lot of bandwidth and CPU will be lost
• Must limit the rate of updates
– But then link state information will not be accurate
anymore
• “stale” state
• Fundamental trade-off
– Accuracy of routing vs. cost of updates
– How can I get good routings even if state information is
stale?
Limiting the update rate
• Update threshold
– Generate an update when link information
changes more than t% since last advertisement
• E.g available bandwidth changes more than 10%
– More accurate when available bandwidth is
small
• This is good we need more accuracy then
• Clamp down timer
– Do not send more than x updates per second
More limiting
• Divide the link bandwidth in regions
– Equal sizes
– Exponential sizes
• When available bandwidth moves to a
different region since last advertisement
send a new one
– Can advertise the region and not the exact value
of available bandwidth
• Many links will have same available bandwidth
• More availability of equal bandwidth paths to
choose from
Routing with stale values
• Randomized routing
– Do not believe the information we have
– Add some randomness in the path selection
decisions