Transcript Routing

New IP Routing Algorithms
숙명여자대학교 : 최 종원
이화여자대학교 : 이 미정
2000. 2. 14
목차
• 인터넷 라우팅
• What needed in New IP routing
– Qos routing
– routing table convergence
• 결론
Internet Routing
5
2
A
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
B
2
1
D
3
C
3
1
5
F
1
E
2
• “good” path:
– typically means
minimum cost path
– other def’s possible
Routing Algorithm classification
Global or decentralized
information?
Global:
• all routers have complete
topology, link cost info
• “link state” algorithms
Decentralized:
• router knows physicallyconnected neighbors, link
costs to neighbors
• iterative process of
computation, exchange of
info with neighbors
Static or dynamic?
Static:
• routes change slowly over
time
Dynamic:
• routes change more
quickly
– periodic update
– in response to link cost
changes
Comparison of LS and DV algorithms
Speed of Convergence
• LS:
– may have oscillations
• DV:
– convergence time varies
– may be routing loops
– count-to-infinity problem
Robustness: what happens
if router malfunctions?
LS:
– node can advertise
incorrect link cost
– each node computes
only its own table
DV:
– DV node can advertise
incorrect path cost
– each node’s table used
by others
• error propagate thru
Routing in the Internet
• The Global Internet consists of Autonomous Systems
(AS) interconnected with each other:
– Stub AS: small corporation
– Multihomed AS: large corporation (no transit)
– Transit AS: provider
• Two-level routing:
– Intra-AS: administrator is responsible for choice
– Inter-AS: unique standard
Intra-AS Routing
• Also known as Interior Gateway Protocols (IGP)
• Most common IGPs:
– RIP: Routing Information Protocol
– OSPF: Open Shortest Path First
– IGRP: Interior Gateway Routing Protocol
(Cisco propr.)
Inter-AS routing
• BGP (Border Gateway Protocol): the de facto
standard
• Path Vector protocol: and extension of Distance
Vector
• Each Border Gateway broadcast to neighbors
(peers) the entire path (ie, sequence of ASs) to
destination
Why different Intra- and Inter-AS routing ?
• Policy: Inter is concerned with policies (which
provider we must select/avoid, etc). Intra is contained
in a single organization, so, no policy decisions
necessary
• Scale: Inter provides an extra level of routing table
size and routing update traffic reduction above the
Intra layer
• Performance: Intra is focused on performance
metrics; needs to keep costs low. In Inter it is difficult
to propagate performance metrics efficiently (latency,
privacy etc). Besides, policy related information is
more meaningful.
We need BOTH!
What needed in New IP Routing
• QoS Routing
– E.Crawley, R.Nair, B.Rajagopalan and H.Sandick, “A
Framework for QoS-based Routing in the Internet,” RFC
2386, Aug. 1998
– G.Apostolopoulos, R.Guerin, and S.Kamat, A.Orda, “QoS
Routing Mechanisms and OSPF Extensions,” RFC 2676,
Aug. 1999
– S.Chen and K.Nahrstedt, “An Overview of Quality of
Service Routing for Next-Generation High-Speed Networks:
Problems and Solutions,” IEEE Network Nov. 1998
• Convergence Time Consideration
– C. Labovitz, “Delayed Internet Routing Convergence”,
SIGCOMM, Aug. 2000
– T. Griffin, “An Analysis of BGP Convergence Properties”,
SIGCOMM, Aug. 1999
Objectives of QoS-based Routing
• Dynamic determination of feasible paths
– Select a path that has a good chance of
accommodating the QoS of the given flow
– May be subject to policy constraints such as
path cost, provider selection
• Optimization of resource usage
– Network state dependent routing
• Graceful performance degradation
– Compensate for transient inadequacies in
network engineering
Issues raised in QoS-based Routing
• How to determine the QoS capability of each
outgoing link and reserve link resources?
• What is the granularity of routing decision?
• What routing metrics are used?
• How are QoS-accommodating paths computed?
• What are the admission control issues?
• What factors affect the routing overheads?
• How is scalability achieved?
Difficulties of QoS Routing
• Diverse QoS constraints
– Two or more independent additive constraints
make the problem NP-complete
• Carry both QoS and best-effort traffic
– Hard to determine best operating point for both
traffic
• Network state changes dynamically
– Performance of a QoS routing algorithm can be
seriously degraded if the state information used
is outdated
Two Tasks of QoS Routing
• Collecting state information
• Computing a feasible path
Collecting state information
• Metrics are more dynamic
– Requires more frequent exchange of state
information
– Induce more frequent path computation
overhead
• Inaccurate
– Non negligible propagation delay
– In order to reduce overhead of local state
information broadcasting
Collecting state information
(cont’d)
• Need to find an optimal compromise
between the performance and overheads of
the QoS routing
– Triggers for network state updates
– Triggers for path selection computations
• Overhead is proportional to the size of
network and frequency of broadcasting
local states
– Hierarchical routing
Classification of QoS Routing Algorithms
• Routing classes
– Unicast routing
– Multicast routing
• Routing strategies
– Source routing algorithms
– Distributed routing algorithms
– Hierarchical routing algorithms
When to Invoke a Routing Algorithm
Computation?
• On-demand
– For each new request
– Computationally extensive
– Use the most up to date network state information
• Pre-computation and caching
– Amortizes the computational cost over multiple
requests
– Each computation instance is usually more expensive
– Accuracy of the selected paths may be lower
– Periodic pre-computation or after a given number of
updates
Implementation Experiment
• RFC 2676
– Apostolopoulos, Williams, Kamat, Guerin,
Orda, Przygienda
– Proposed experimental protocol extending
OSPF for QoS routing
– Implemented the proposed extensions and
performed performance measurements
• BW-constrained cost-optimization
Implementation Experiment
(cont’d)
• QoS routing extensions to OSPF
demonstrated in RFC 2676 are fairly
straightforward to implement
• By measuring the performance of the real
system, it was demonstrated that the
overheads associated with QoS routing are
not excessive, and within the capabilities of
modern processor
Future Research Should Focus On
• Efficient heuristic algorithms for the NPcomplete routing problems
• State aggregation with multiple QoS metrics
• Hierarchical routing with imprecise
information
• Multipath routing
– Search multiple paths for a feasible one
– Select a set of paths instead of a single one for a
connection
Future Research Should Focus On
(cont’d)
• Integration of QoS routing and best-effort
routing
• Rerouting
– To adapt to changing network state
• Efficient routing algorithms based on
specific network models such as the ratebased scheduling network
Internet Routing Convergence
Problem
Background
BGP exhibits poor convergence behavior:
–
–
Measured convergence times of up to 20 minutes
for BGP path changes/failures
Factorial (N!) theoretic upper bound on BGP
convergence complexity (explore all paths of all
possible lengths)
BGP route table
-- http://www.telstra.net/ops/bgp.html
Open question: In practice, what topological and
policy factors impact convergence delay ?
Goal: Understand BGP convergence behavior under
real topologies/policies
– Given a physical topology and ISP policies, can we
estimate the time required for convergence?
– Do convergence behaviors of ISPs differ?
– How does steady-state topology compare to paths
explored during failure?
– Can we change policies/topology to improve BGP
convergence times?
Experiments
• Analyzed secondary paths between between 20
source/destination AS pairs
– Inject and monitor BGP faults
– Survey providers to determine policies behind paths
• To provide intuition, we will focus on faults
injected into three ISPs at Mae-West
– Observed faults via fourth ISP (in Japan)
– Three ISPs roughly map onto tier1, tier2, tier3
providers
– Results from these three ISPs representative of all data
Why we should care about convergence!
• Routing reliability/fault-tolerance on small
time scale(minutes) not previously a priority
• Emerging transaction oriented and
interactive applications(e.g. Internet
Telephony) will require higher leverls of
end2end network reliability
• How well does the Internet routing
infrastructure tolerate faults?
Conventional Wisdom
• “Restoral is not an issue in the IP world”
– Just reroute around in a few milliseconds or
whatever
•
•
•
•
BGP convergence takes only a few minutes
“Bad news travels fast”
BGP has great convergence properties
Enough bandwidth will solve anything
The Purpose
• Most of the conventional wisdom about
routing convergence is not accurate
Instrument the Internet
• Inject routes into geographically and topologically
diverse provider BGP peering sessions(Mae-West,
Japan, Michigan, London)
• Periodically fail and change these routes(I.e. send
withdraws or new attributes)
• Time envents using ICMP echos and NTP
synchronized BGP “routeviess” monitoring
mahines
• wait two years (and 250,000 faults)
Fault Secnarios
• Tup - A new route is advertised (route repair)
• Tdown - A route is withdrawn (route failure)
• Tshort - Advertised a shorter/better ASPath
(route repair and fail over)
• Tlong - Advertised a longer/worse ASPath
(route failure and failover)
Major Convergence Results
• Routing convergence requires an order of
magnitude longer than expected (10s of
minutes)
• Routes converge more quickly following
Tup/Repair than Tdown/Failure events
(“bad news travels more slowly”)
• Curiously, withdrawals (Tdown) generates
several times the number of announcements
than announcements (Tup)
Comparing ISP Convergence Latencies
• CDF of faults injected into three Mae-West providers and
observed at Japanese ISP
• Significant variations between providers
• Not related to geography
Failures, Failovers and Repairs
• Bad news does not travel fast…
• Repairs (Tup) exhibit similar convergence
properties as long-short ASPath failover
• Failures (Tdown) and short-long failovers
also similar
– slower than Tup
– 60% take longer than two minutes
Delayed Convergence
why does this happen?
• Well known that distance vector protocls
exhibit poor convergence behaviors
– counting to infinity, looping, bouncing problem
• RIP redefines infinity and adds split-horizon,
poison reverse, etc.
– Still, slow convergence and not scalable
• BGP avertises ASPaths instead of distance
– Sloves counting to infinity and RIP looping
problem, but...
Towards Millisecond BGP Convergence
Three possible solutions
• Entirely new protocol
• Turn off MinRouteAdver timer
• “Tag” BGP updates
–
Provide hint so nodes can detect bogus state
information
결 론
• QoS Routing Issues
• An experimental implementation is done with
OSPF extensions for QoS
• Tradeoffs between performance and overhead of
QoS routing are studied
• convergence delays may grow exponentially in the
worst case
• Need a fast convergence method
참고문헌
• C. Labovitz, “Delayed Internet Routing Convergence”,
SIGCOMM, Aug. 2000, pp. 175-187
• R.Guerin and A.Orda, ”QoS-based Routing in Networks
with Inaccurate Information: Theory and Algorithms,”
IEEE INFOCOM’97, Japan, Apr. 1997
• Z.Wang and J.Crowcroft, ”QoS Routing for supporting
Resource Reservation,” IEEE JSAC, Sept. 1996
• S.Chen and K.Nahrstedt, ”On Finding Multi-Constrained
Paths,” IEEE ICC’98, June 1998
• Q.Ma and P.Steenkiste, “Quality-of-Service Routing with
Performance Guarantees,” Proc. 4th Int’l. IFIP Wksp. QoS,
may 1997
참고문헌 (계속)
• K.G.Shin and C.C.Chou, “ A distributed Route-Selection
Scheme for Establishing Real-Time Channel,” 6th IFIP
Int’l. Conf. High Perf. Networking, Sept. 1995, pp. 31929
• J.Behrens and J.J.Garcia-Luna-Aceves, “Hierarchical
Routing Using Link Vectors,” IEEE INFOCOM’98, Mar.
1998
• D.H.Lorenz and A.Orda, “QoS Routing in Networks
with Uncertain Parameters,” IEEE INFOCOM’98, Mar.
1998
• B.Awerbuch et al., “Throughput-Competitive On-line
Routing,” 34th Annual Symp. Foundations of Comp. Sci.,
Palo alto, CA, Nov. 1993
참고문헌 (계속)
• J.-Y.Le Boudec and T.Przygienda, “A Route PreComputation Algorithm for Integrated Services
Networks,” J. Network and Sys. Mgmt., vol.3, no.4,
1995, pp. 427-49
• A.Iwata et al., “PNNI Routing Algorithms for
Multimedia ATM Internet,” NEC R&D, vol.38, 1997
• M.Peyravian and A.D.Kshemkalyani, “Network Path
Caching: Issues, Algorithms and A Simulation Study,”
Comp. Commun. Rev., vol.20, 1997, pp. 605-14
• A.Shaikh, J.Rexford, and K.Shin, “Efficient
precomputation of qulity-of-service routes,” Wksh.
Network and Op. Sys. Support for Digital Audio and
Video, July 1998
참고문헌 (계속)
• S.Chen and K.Nahrstedt, “Distributed QoS routing with
Imprecise State Information,” ICCCN’98, Oct. 1998
• A.Banerjea, “Simulation Study of the Capacity Effects
of Dispersity Routing for Fault Tolerant Realtime
Channels,” ACM SIGCOM’96, Aug. 1996
• N.S.V.Rao and S.G.Batsell, “QoS Routing Via Multiple
Paths Using Bandwidth Reservation,” IEEE
INFOCOM’98, San Francisco, CA, Mar. 1998
• C.Parris, H.Zhang, and D.Ferrari, “ A Mechanism for
Dynamic Re-routing of Real-time Channels,” Tech. Rep.
TR-92-053, Int’l. Comp. Sci. Inst., Berkeley, CA, Apr.
1992
참고문헌 (계속)
• G.Apostolopoulos and S.K.Tripathi, “On Reducing the
Processing Cost of On-Demand QoS Path Computation,”
Proc. Of ICNP’98, Oct. 1998
• G.Apostolopoulos, R.Guerin, and S.Kamat,
“Implementation and Performance Measurement of QoS
Routing Extensions to OSPF,” Proc. of INFOCOM’99,
Mar. 1999
• G.Apostolopoulos, R.Guerin, and S.Kamat, S.K.Tripathi,
“QoS Routing: A Performance Perspective,” Proc. of
ACM SIGCOMM’98
• R.Guerin, A.Orda, and D.Williams, “QoS Routing
Mechanisms and OSPF Extensions,” Proc. of the 2nd
IEEE Global Internet Mini-Conference, Nov. 1997
참고문헌 (계속)
• E.Crawley, R.Nair, B.Rajagopalan and H.Sandick,
“A Framework for QoS-based Routing in the
Internet,” RFC 2386, Aug. 1998
• G.Apostolopoulos, R.Guerin, and S.Kamat, A.Orda,
“QoS Routing Mechanisms and OSPF Extensions,”
RFC 2676, Aug. 1999
• S.Chen and K.Nahrstedt, “An Overview of Quality
of Service Routing for Next-Generation High-Speed
Networks: Problems and Solutions,” IEEE Network
Nov. 1998
• I. Cidon, R.Rom and Y.Shavitt, “Multi-Path Routing
Combined with Resource Reservation,” IEEE
INFOCOM’97, Japan, Apr.1997, pp. 92-100