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]