[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
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).


   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

   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.

                       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


   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


   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

   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

                         +--+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


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

   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

   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


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

   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



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]