Transcript by Ansari Almas - FSU Computer Science Department

Topology Aggregation and
Routing in Bandwidth-Delay
Sensitive Networks
King-Shan Lui, Klara Nahrstedt
Department of Computer Science
UIUC
Flow of the presentation
•
•
•
•
•
Introduction
Network Models
QoS-Aware Topology Aggregation
Line-Segment Routing Algorithm
Simulation Results
Introduction
• As the network grows larger and larger, it is
impossible to broadcast the whole topology to
every node in the network to do routing because it
takes an enormous amount of bandwidth, time and
space.
• To deal with the scalability problem, topology
aggregation is done.
• Nodes are grouped hierarchically into several
clusters known as peer groups or domains.
• The internal topologies of these domains are
aggregated before broadcasting.
• All aggregation schemes suffer from different
degrees of distortion.
• There are several ways to do aggregation with
bounded distortion when there is only one metric
under consideration.
• It is very difficult to do aggregation with bounded
distortion when 2 or more parameters are under
consideration.
• If there are several paths between source and
target, how does one pick up the best QoS pair?
• This paper proposes an algorithm for topology
aggregation that aggregates a peer group with 2
metrics, delay and bandwidth with corresponding
QoS routing protocol.
Network Models
• The whole network is divided into disjoint peer
groups.
• A peer group(PG) is a set of nodes connected by
links.
• The network and the domains are represented by
directed graphs and the links can be asymmetric.
• Nodes within a PG can see each other but nodes
outside only have an aggregated view.
• Within a PG, some nodes connect to nodes outside
the PG. These are the border nodes.
• One representative topology is the star.
• Border nodes connect via virtual links called
spokes to a virtual nucleus generating a symmetric
star.
• Each link has associated set of QoS parameters.
• A limited no. of inter-border links called bypasses
are allowed.
• Formally a PG is modeled as a tuple (V,B,E)
V – set of nodes
B ( B is a subset of V) – set of border nodes
E – set of directed (physical)links among nodes in
V
(D,W) – QoS parameter of each physical link
(D-delay, W-bandwidth)
• Each pair (D,W) represents a single point
on the delay-bandwidth plane.
• The delay of a path is the sum of all the
delays of the physical links along that path.
• The bandwidth of a path is the minimum of
the bandwidths among all the links.
• The parameter of a physical path is also a
point on the delay-bandwidth plane.
• Hence if there are m physical paths between
2 border nodes, there will be m points on
the delay-bandwidth plane of the logical
link between the 2 border nodes.
• A network consists of PGs and links that
connect them. Denoted as (G,L)
G={gi|gi = (Vi,Bi,Ei), 1<= i <=|G|}
L – set of links between the PGs.
QoS-Aware Topology Aggregation
• The basic principle is: instead of using m points
per logical link on the delay-bandwidth plane, a
line segment to approximate the m points is used,
thereby strongly decreasing the storage space for
the QoS parameters.
• 2 phases in the algorithm:
1. Find a line segment for each logical link in the
mesh of the border nodes.
2. Find a star with bypasses aggregation from this
mesh.
• The parameter of a logical link is the best QoS
parameter among all the physical links between
the 2 nodes of the logical link.
• If we have 2 metrics per link, there exists no
absolute order, however a partial order can be
developed.
• Definition
A point (x,y) is more representative than a point
(x’,y’) if they are not the same and x<=x’ and
y>=y’. Given a set (S) of points in the delaybandwidth plane, (x,y)  S is a representative of
S if there does not exist another point (x’,y’)  S
which is more representative than (x,y), which
means that (x’,y’)  S, x <= x’ or y >=y’.
• Example 1
Let S be a set of delay-bandwidth QoS pairs and
S={(4,5),(7,9),(10,8),(9,5),(2,3),(7,7)}. (2,3) is a
representative of S since its delay is less than all
other pts in S. Another representative is (7,9).
We can plot all points on a delay-bandwidth plane.
• Due to the storage limitation on routers, it is too
expensive to store all the points for every logical
link.
• Store only one point per logical link.
• However no matter which point we pick, much
information is lost.
• To solve this, a line segment that approximates the
staircase (all the points) is found by using the least
square method.
• The shaded area defines the region of supported
services, i.e. any request that falls inside this area
can be supported by some physical path.
• After a line segment is found, all connections
which fall under the line segment can be accepted.
• However not all these connections are supported.
• For e.g. If L1 is chosen then un shaded areas below L1
represent connection requests that are accepted but not
supported by any physical path i.e. crankback will occur.
• On the other hand, we may reject supported QoS by using
a line segment. For e.g. If the connection request is in the
shaded area above the line it will be rejected even though it
can be served.
• Choice of line segment therefore depends on the desired
quality of service.
• In the figure both L1 and L2 are possible line segments. L2
will reject more supported connection request than L1and
L1 will have more crankbacks than L2.
• A line is represented as [(a,b),(c,d)]. The endpoint with
smaller bandwidth is lower endpoint and the other
endpoint is the upper endpoint. So a line is represented as
[lower endpoint, upper endpoint].
• A mesh that consists of b*(b-1) logical links is still
to expensive to be broadcasted.
• Aggregate this mesh into a star with bypasses.
• Let i and j be two border nodes and n be the
nucleus of the star. If there is no bypass between i
and j, the only path from i to j is i->n->j in the star.
• The goal of the aggregation is to find out the QoS
parameters of the links i->n and n->j such that the
delay and the bandwidth of i->n->j in the star is
the same as the delay and bandwidth of i->j in the
mesh.
• We have to split a single link i->j in the mesh into
two links i->n and n->j in the star.
•
•
join operation (+) to find the QoS parameters of
i->n->j given i->n and n->j is used.
Definition
[(a,b),(c,d)] + [(a’,b’),(c’,d’)] =
[(a+a’,min(b,b’)), (c+c’,min(d,d’))]
Now find spokes and bypasses: 3 steps
1. Find the spokes from border nodes to nucleus.
2. Find the spokes from nucleus to border nodes .
3. Find the bypasses between border nodes.
Denotation: lmij – line segment from i to j in mesh.
lsij - line segment from i to j in star.
Spokes incoming to the nucleus
•
To find spokes we have to break line segments in the
mesh.
•
From the definition of join, it is clear that the endpoint
delays of the spokes lsin and lsnj should be smaller than
those in lmij while the endpoint bandwidths should not be
smaller than those in lmij.
•
Let l.lp and l.up denote the lower and upper endpoint of
a line segment l.
•
Let p.d and p.w denote the delay and bandwidth of a
given point p.
•
lsin = [(min_ld,max_lw),(min_ud,max_uw)]
where min_ld=min j  B, i!= j{lmij,lp.d},min_ud = min j B
m
m
, i!= j{l ij,up.d}, min_lw=min j  B, i!= j{l ij,lp.w},min_uw
= minj  B , i!= j{lmij,up.w}.
•
O(b) is time taken to find one spoke to the nucleus.
There are b spokes incoming to n. Total time to find all
spokes to n is O(b2).
Example 2
• Suppose the line segments from node 0 to nodes
1 and 2 are [(9,4) ,(19,6)] and [(3,7),(3,7)]
respectively.
• min_ld=min_ud=3, and max_lw=max_uw=7.
Therefore the line segment from 0 to n
is[(3,7),(3,7)].
Spokes outgoing from the nucleus
•
Upto this point we know mesh (M) and spokes from
borders to nucleus (Sb->n).
•
That is, we know lmij and lsin. We have to find lsnj.
•
We have lsin + lsnj = lmij
•
So lmij – lsin =lsnj
•
Definition
[(a,b),(c,d)] - [(a’,b’),(c’,d’)] = [(a-a’,min(b,b’)), (cc’,min(d,d’))]
•
Referring to the e.g. 2, lm01 = [(9,4),(19,6) and ls0n =
[(3,7),(3,7)] so we get lsn1 as [(6,4),(16,6)]. However we
can also get lsn1 from say lm21 . But in aggregation, we
can have at most one lsn1. This problem is solved by
taking the averages of all the delays and bandwidths of
ideal lsn1’s to be the real lsn1.
Finding Bypasses
• Due to aggregation, lsin + lsnj may no longer be
the same as lmij in the mesh.
• Some deviate only a bit while others might be
quite different.
• In order to make the aggregation more precise,
direct links between border pairs are introduced.
Line-Segment Routing Algorithm
• LSRA is a QoS based source routing algorithm,
integrating modified Dijkstra’s Algorithm(DA)
and the centralized bandwidth-delay routing
algorithm(CBDRA).
• DA is an optimal algorithm when finding the
shortest-delay path when delay is the only metric.
• CBDRA works when there are 2 metrics, delay
and bandwidth. It first prunes all the links that do
not satisfy the bandwidth requirement, and then
applies DA to find the min-delay path in the
residue network.
• In LSRA this idea is augmented to deal with line
segment representation.
• LSRA requires that each node keeps the topology
of its own PG and star aggregations of other PGs.
• There are 2 levels are routing: inter-domain and
intra-domain.
• An inter-domain routing path specifies the border
nodes in different PGs to go through and intradomain routing finds a path within a domain.
• LSRA accordingly has 2 phases:
Inter-Domain Routing
• After obtaining star aggregations from other PGs,
each node can see border nodes of other PGs and
can compute the line segment between any border
pair in an outside PG.
• The network that a node sees is called node-view network
(NVN).
• A modified DA algorithm applying the technique of
CBDRA is used to find the inter-domain path using NVN.
• Similar to DA, a path grows from the source to the target
PG.
• The delay to each node in NVN is kept and each time a
node is reached by the growing path, the delays of its
neighbors are updates according to the links.
• There are 2 types of links in NVN:
-physical links which connect different PGs and nodes in
the source PG.
-logical links which are line segments connecting borders
within the PG obtained from star aggregation.
• Suppose the routing request is (reqd, reqw) and
accumulated delay from source node to another node i in
NVN is d[i]. If there is a link, either physical or logical,
from i to j, LSRA updates the delay of node j (d[j]) as
follows:
• Case I: a physical link with (D,W). If W<reqw means no
feasible path can go through this link, so d[j] is unchanged.
If W>=reqw , d[j] = min{d[j],d[i] +D} as in DA.
• Case II: a logical link l = [(dlp,wlp),(dup,wup)]. If wup < reqw,
d[j] is unchanged, otherwise d[j] = {min d[j],d[i] + dreqw},
where dreqw is the delay-coordinate of the line segment with
bandwidth equal to reqw.
• The process stops when the path reaches one of the
borders, say t, of the target PG. If d[t]<=reqd, then request
is accepted and LSRA goes ahead to do intra-domain
routing. Else request is rejected.
• The running time complexity is the same as DA which is
optimal.
Intra-Domain Routing
• In this phase LSRA finds the route in a distributed fashion.
• A message or a packet is sent from the source to travel
along the inter-domain path found.
• When the border node t of PG g receives the message , and
finds out the next hop in the inter-domain path is another
border node t’ in g, it finds the path going from t to t’ using
CBDRA.
• The message keeps accumulating delay along the path.
• If accumulated delay exceeds reqd, crankback occurs and
the message is forwarded back to the source.
• If the message successfully reaches the target PG, a
feasible path has been found.
• Complexity of CBDRA is same as DA.
Simulation Results
• LSRA is compared to a SP algorithm (centralized modified
Dijktra’s Algorithm).
• LSRA may suffer from crankback if it accepts a request
after finding an inter-domain path but is unable to find a
feasible intra-domain path.
• Also a feasible request may be rejected due to an
inaccurate approximation of dreqw.
• Success ratio = total no. of feasible paths found
total no. of feasible requests
• A good algorithm should have a high success ratio but a
small crankback ratio.
• Simulated network topology consists of 10 domains, each
with 15-35 nodes, a total of 293 nodes. With 3-4 border
nodes per domain.
• LSRA achieves a very good success ratio and performs
better than SP