home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Internet Info 1997 December
/
Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso
/
drafts
/
draft_n_r
/
draft-ohta-rsvp-friendly-hop-path-00.txt
< prev
next >
Wrap
Text File
|
1996-11-18
|
15KB
|
390 lines
INTERNET DRAFT M. Ohta
draft-ohta-rsvp-friendly-hop-path-00.txt Tokyo Institute of Technology
Y. Goto
Institute of Systems & Information Technologies/KYUSHU
and Kyushu University
November 1996
Path QoS Collection for RSVP-friendly Hop-by-hop QoS Routing
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as ``work in progress.''
To learn the current status of any Internet-Draft, please check the
``1id-abstracts.txt'' listing contained in the Internet- Drafts
Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
Abstract
QoS routing needs some stabilization mechanism to prevent a delayed
negative feedback on the link QoS information by the routed traffic.
So far, route pinning was the only known way of the stabilization.
But, as RSVP merges multiple RESV messages to create a new one,
pinned route computed elsewhere for different QoS requirement is not
useful after the merge.
That is, we need a sticky hop-by-hop QoS routing algorithm.
Path QoS Collection is such an algorithm to collect true upstream
link QoS in PATH messages to correct the link QoS information
distributed by QoS routing protocols.
1. Introduction
Path QoS Collection is a fully distributed soft state mechanism for
QoS routing to accumulate QoS information of links in Path_msg of
M. Ohta Expires on May 20, 1997 [Page 1]
INTERNET DRAFT Path QoS Collection November 1996
RSVP (Resource Reservation Protocol). Using link state information
distributed with a QoS routing protocol along with the Path QoS
Collection, receivers and intermediate routers can stably choose the
best route with the required QoS hop-by-hop in a distributed and
scalable manner for unicast and multicast communications over the
Internet.
With RSVP, resource reservations are initiated by receivers with
Resv_msgs toward the sender because the QoS requirements may be
different receiver by receiver and only receivers know their
requirement. To avoid that Resv_msgs concentrate at the sender,
RSVP-capable routers merge incoming Resv_msgs to form a new Resv_msg
and send it toward the sender. To merge Resv_msgs with different QoS
requirements, the largest requirement is chosen to form a merged
Resv_msg. Since RSVP does not adopt QoS routing protocol yet, a
sender sends a Path_msg to receivers so that intermediate routers can
know the direction of Reverse Path Forwarding of Resv_msgs. But,
without QoS routing, we may not be able to use available resource.
For example, in Figure-1, the shortest path between R1 and S is S-C-
B-R1. So, with a simple shortest path routing, a bandwidth
requirement of 15 can not be warranted, even though a longer path S-
F-E-D-A-B-R1 can satisfy the requirement.
+--+
+--+R1|
20| +--+
+--+ +---+ 25 +-+-+ 10 +---+ 10 +---+
|R0|----| A |-----+ B +------+ C |-----| S | A,B,C,D,E,F: Router
+--+ 30 +-+-+ +---+ +---+ +-+-+ S: Sender
| +---+ +---+ +---+ | R0, R1: Receiver
+----+ D |----+ E |----+ F |---+ Number: Available
18 +---+ 20 +---+ 30 +---+ 20 Bandwidth
Figure-1
Therefore, some QoS routing protocol, which distributes information
to routers and receivers about which path to follow, is necessary for
RSVP. To quickly reflect the changes of the state of the network such
as available bandwidth, which changes a lot more often than binary
up/down state of a link, QoS routing protocol should adopt Link State
Routing Algorithm such as OSPF.
But, simple-minded QoS routing has a stability problem. In Figure-1,
if R0 requires QoS of Bandwidth 9, a path S-C-B-A-R0 will be chosen.
The link state of Figure-1 changes into that of Figure-2. That is,
link S-C and C-B have Bandwidth of only 1. Unless R0 knows that the
link state has changed because of the flow of its own request, R0
will think that the only path that satisfy the Bandwidth requirement
M. Ohta Expires on May 20, 1997 [Page 2]
INTERNET DRAFT Path QoS Collection November 1996
of the flow is S-F-E-D-A-R0 and stop using the path S-C-B-A-R0. But,
then, link state on the path S-C-B-A turns back to link state of
Figure-1, and R0 will select the path S-C-B-A-R0 again. And such
route flapping is repeated forever resulting in an unstable routing.
+--+
+--+R1| A,B,C,D,E,F: Router
20| +--+ S: Sender
+--+ +---+ 16 +-+-+ 1 +---+ 1 +---+ R0, R1: Receiver
|R0|----| A |-----+ B +------+ C |-----| S | Number: Available
+--+ 21 +-+-+ +---+ +---+ +-+-+ Bandwidth
| |
| +---+ +---+ +---+ |
+----+ D |----+ E |----+ F |---+
18 +---+ 20 +---+ 30 +---+ 20
Figure-2
Route Pinning is an existing method to stabilize routing. A receiver
finds the best path, notifies it to routers on the path, and the
routers use the specified path. In Figure-1, as the receiver knows
that the path S-C-B-A-R0 is used by its own flow, it can cancel the
effect of the flow from the advertised link state of Figure-2 to
reconstruct the original link state of Figure-1.
The problem of Route Pinning is that it's not good for multicast. For
example, in Figure-1, if R0 requests a path S-C-B-A-R0 of bandwidth 9
and R1 requests a path S-F-E-D-A-B-R1 of bandwidth 15, it is not
naturally possible to merge Resv_msgs with different path
specifications. That is, there will be two redundant data streams. If
Resv_msgs are forcibly merged on the router B, then a new path should
be computed by the router B. As a result, the path S-F-E-D-A-R0 would
be selected which contradicts with R0's idea of the flow.
2. Path QoS Collection and Path QoS Correction
To solve the problem, path recomputation at the multicast merge
points is seemingly inevitable.
That is, we must have a sticky hop-by-hop QoS routing algorithm.
If a QoS routing protocol distributes detailed link state about which
flow consumes how much resource on each link, each hop can fully
reconstruct a real resource usage and we can have a sticky QoS
routing. But, obviously, such a routing protocol distributes too much
routing information to be scalable.
But, looking closely at the feedback problem, the feedback loop is
M. Ohta Expires on May 20, 1997 [Page 3]
INTERNET DRAFT Path QoS Collection November 1996
formed through upstream resource consumption. That is, to make
routing sticky, we don't have to resonctruct downstream resource
consumption.
For the correction of upstream information only, Path_msgs can,
naturally, carry upstream resource consumption information to break
the loop for sticky QoS routing.
That is, Path QoS Collection stabilizes fully distributed hop-by-hop
route computation.
The simple hop-by-hop method is unstable because the receivers and
the intermediate routers can't know which link state information is
affected by their own flow. With Path QoS Collection, QoS information
on links from the ender to the receivers are collected in a Path_msg.
Thus, even if the link state information of Figure 2 is distributed
through some QoS routing protocol, the receivers and the intermediate
routers can reconstruct state of Figure 1, for the upstream links
toward the sender. For example, between S and R0, Resv_msgs are added
the amount of QoS consumed by the flow on each link. The router C
receives ({S-C},9), the router B ({S-C,9}, {C-B,9}), the router A
({S-C,9}, {C-B,9}, {B-A,9}) and the receiver R0 ({S-C,9}, {C-B,9},
{B-A,9}, {A-R0,9}).
Then, the forwarding direction of Resv_msg is decided distributedly
by individual routers and receivers with the corrected link state.
It should be noted that hop-by-hop QoS routing solves the killer
reservation problem. As individual routers know which Resv_msg can't
be satisfied, killer reservations are bounced before being merged by
satisfyable reservations.
Figure-3 illustrates the router B's view of the corrected QoS
information.
+--+
+--+R1| A,B,C,D,E,F: Router
20| +--+ S: Sender
+--+ +---+ 16 +-+-+ 10 +---+ 10 +---+ R0, R1: Receiver
|R0|----| A |-----+ B +------+ C |-----| S | Number: Available
+--+ 21 +-+-+ +---+ +---+ +-+-+ Bandwidth
| |
| +---+ +---+ +---+ |
+----+ D |----+ E |----+ F |---+
18 +---+ 20 +---+ 30 +---+ 20
Figure-3
M. Ohta Expires on May 20, 1997 [Page 4]
INTERNET DRAFT Path QoS Collection November 1996
Router B knows that, without the flow, the path S-C-B has bandwidth
of 10, not 1.
While the QoS information on downstream links R0-A-B is not
corrected, it increases the stability of the route and is not a
problem.
The amount of the collected Path QoS Collection information in a
Path_msg is proportional to the length of the path. That is, only as
much as the amount of the information necessary for Route Pinning in
Resv_msg and is not a problem.
3. Multicasting with Path QoS Collection
Merged Resv_msg for multicast, of course, is not an exception and
forwarded toward the sender over a path that satisfies the new QoS
requirement.
Suppose that, R0 wants bandwidth of 9 and R1 12.
Then, Resv_msg from R0 (intended to follow a path R0-A-B-C-S) and
Resv_msg from R1 (intendet to follow a path R1-B-A-D-E-F-S) is merged
on Router A to be a bandwidth requirement of 12.
Then, router A locally decides that the merged Resv_msg should follow
a path A-D-E-F-S.
Figure-4 illustrate such an situation.
Note that the receiver R0 will receive Path QoS Collection
information of ({S-F,12}, {F-E,12), {E-D,12}, {D-A,12}, {A-R0,9}).
+--+
+--+R1| A,B,C,D,E,F: Router
8| +--+ S: Sender
+--+ +---+ 13 +-+-+ 10 +---+ 10 +---+ R0, R1: Receiver
|R0|----| A |-----+ B +------+ C |-----| S | Number: Available
+--+ 12 +-+-+ +---+ +---+ +-+-+ Bandwidth
| |
| +---+ +---+ +---+ |
+----+ D |----+ E |----+ F |---+
6 +---+ 8 +---+ 18 +---+ 8
Figure-4
4. Protocol Extensions
First of all, we need a new field, "Path QoS", in Path_msg.
M. Ohta Expires on May 20, 1997 [Page 5]
INTERNET DRAFT Path QoS Collection November 1996
Secondly, Resv_msg shouldn't follow reverse path established by
Path_msg. Instead, Path_msgs should follow forward path established
by Resv_msg. Resv_msg should work something like PIM_join.
Exact details of what and how QoS information should be collected
needs further discussion.
For example, it may be better to collect corrected link QoS state on
each link than to collect consumed QoS and correct it on each router.
For hierarchical routing, QoS may still be collected hop-by-hop or
QoS information in a lower hierarchy may be aggregated in upper
hierarchy.
Path QoS field and QoS routing protocol should have common time stamp
(local to the router which originate the information) to suppress
race conditions.
5. Requirement and Suggestions for Routing Protocol
As Path QoS correction is performed on link state information,
unicast routing protocol must be that of link state type.
Moreover, to suppress unnecessarily frequent link state updates, new
link state should be advertised only when the amount of available
resource is below the current advertised value, considerably above
the current advertised value or long enough time has passed since the
last update.
It is suggested that, when the amount of available resource is
reducing, the advertised value should be a little less than the
exactly available amount.
Any multicast routing protocol may be used to forward Resv_msgs.
Path_msgs and data streams should be forwarded to the reverse
direction to that established by the Resv_msgs.
6. References
[PIM]
[RSVP]
7. Security Considerations
(to be provided)
M. Ohta Expires on May 20, 1997 [Page 6]
INTERNET DRAFT Path QoS Collection November 1996
8. Authors' Addresses
Masataka Ohta
Computer Center
Tokyo Institute of Technology
2-12-1, O-okayama, Meguro-ku
Tokyo 152, JAPAN
Phone: +81-3-5734-3299
Fax: +81-3-5734-3415
EMail: mohta@necom830.hpcl.titech.ac.jp
Yukinori GOTO
Institute of Systems & Information Technologies/KYUSHU
and Kyushu University.
Fukuoka SRP Center Building 7F
2-1-22-707, Momochihama ,
Sawara-ku, Fukuoka City 814, JAPAN
Phone: +81-92-852-3460
Fax: +81-92-852-3465
E-mail: yuki@k-isit.or.jp
M. Ohta Expires on May 20, 1997 [Page 7]