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 >
Text File  |  1996-11-18  |  15KB  |  390 lines
  1. INTERNET DRAFT                                                   M. Ohta
  2. draft-ohta-rsvp-friendly-hop-path-00.txt   Tokyo Institute of Technology
  3.                                                                  Y. Goto
  4.                   Institute of Systems & Information Technologies/KYUSHU
  5.                                                    and Kyushu University
  6.                                                            November 1996
  7.  
  8.       Path QoS Collection for RSVP-friendly Hop-by-hop QoS Routing
  9.  
  10. Status of this Memo
  11.  
  12.    This document is an Internet-Draft.  Internet-Drafts are working
  13.    documents of the Internet Engineering Task Force (IETF), its areas,
  14.    and its working groups.  Note that other groups may also distribute
  15.    working documents as Internet-Drafts.
  16.  
  17.    Internet-Drafts are draft documents valid for a maximum of six months
  18.    and may be updated, replaced, or obsoleted by other documents at any
  19.    time.  It is inappropriate to use Internet- Drafts as reference
  20.    material or to cite them other than as ``work in progress.''
  21.  
  22.    To learn the current status of any Internet-Draft, please check the
  23.    ``1id-abstracts.txt'' listing contained in the Internet- Drafts
  24.    Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
  25.    munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
  26.    ftp.isi.edu (US West Coast).
  27.  
  28. Abstract
  29.  
  30.    QoS routing needs some stabilization mechanism to prevent a delayed
  31.    negative feedback on the link QoS information by the routed traffic.
  32.  
  33.    So far, route pinning was the only known way of the stabilization.
  34.  
  35.    But, as RSVP merges multiple RESV messages to create a new one,
  36.    pinned route computed elsewhere for different QoS requirement is not
  37.    useful after the merge.
  38.  
  39.    That is, we need a sticky hop-by-hop QoS routing algorithm.
  40.  
  41.    Path QoS Collection is such an algorithm to collect true upstream
  42.    link QoS in PATH messages to correct the link QoS information
  43.    distributed by QoS routing protocols.
  44.  
  45. 1. Introduction
  46.  
  47.    Path QoS Collection is a fully distributed soft state mechanism for
  48.    QoS routing to accumulate QoS information of links in Path_msg of
  49.  
  50.  
  51.  
  52. M. Ohta                 Expires on May 20, 1997                 [Page 1]
  53.  
  54. INTERNET DRAFT            Path QoS Collection              November 1996
  55.  
  56.  
  57.    RSVP (Resource Reservation Protocol). Using link state information
  58.    distributed with a QoS routing protocol along with the Path QoS
  59.    Collection, receivers and intermediate routers can stably choose the
  60.    best route with the required QoS hop-by-hop in a distributed and
  61.    scalable manner for unicast and multicast communications over the
  62.    Internet.
  63.  
  64.    With RSVP, resource reservations are initiated by receivers with
  65.    Resv_msgs toward the sender because the QoS requirements may be
  66.    different receiver by receiver and only receivers know their
  67.    requirement. To avoid that Resv_msgs concentrate at the sender,
  68.    RSVP-capable routers merge incoming Resv_msgs to form a new Resv_msg
  69.    and send it toward the sender. To merge Resv_msgs with different QoS
  70.    requirements, the largest requirement is chosen to form a merged
  71.    Resv_msg. Since RSVP does not adopt QoS routing protocol yet, a
  72.    sender sends a Path_msg to receivers so that intermediate routers can
  73.    know the direction of Reverse Path Forwarding of Resv_msgs. But,
  74.    without QoS routing, we may not be able to use available resource.
  75.    For example, in Figure-1, the shortest path between R1 and S is S-C-
  76.    B-R1. So, with a simple shortest path routing, a bandwidth
  77.    requirement of 15 can not be warranted, even though a longer path S-
  78.    F-E-D-A-B-R1 can satisfy the requirement.
  79.  
  80.                             +--+
  81.                          +--+R1|
  82.                        20|  +--+
  83.      +--+    +---+  25 +-+-+  10  +---+  10 +---+
  84.      |R0|----| A |-----+ B +------+ C |-----| S |  A,B,C,D,E,F: Router
  85.      +--+ 30 +-+-+     +---+      +---+     +-+-+  S: Sender
  86.                |    +---+    +---+    +---+   |    R0, R1: Receiver
  87.                +----+ D |----+ E |----+ F |---+    Number: Available
  88.                  18 +---+ 20 +---+ 30 +---+  20              Bandwidth
  89.  
  90.                               Figure-1
  91.  
  92.    Therefore, some QoS routing protocol, which distributes information
  93.    to routers and receivers about which path to follow, is necessary for
  94.    RSVP. To quickly reflect the changes of the state of the network such
  95.    as available bandwidth, which changes a lot more often than binary
  96.    up/down state of a link, QoS routing protocol should adopt Link State
  97.    Routing Algorithm such as OSPF.
  98.  
  99.    But, simple-minded QoS routing has a stability problem. In Figure-1,
  100.    if R0 requires QoS of Bandwidth 9, a path S-C-B-A-R0 will be chosen.
  101.    The link state of Figure-1 changes into that of Figure-2. That is,
  102.    link S-C and C-B have Bandwidth of only 1. Unless R0 knows that the
  103.    link state has changed because of the flow of its own request, R0
  104.    will think that the only path that satisfy the Bandwidth requirement
  105.  
  106.  
  107.  
  108. M. Ohta                 Expires on May 20, 1997                 [Page 2]
  109.  
  110. INTERNET DRAFT            Path QoS Collection              November 1996
  111.  
  112.  
  113.    of the flow is S-F-E-D-A-R0 and stop using the path S-C-B-A-R0. But,
  114.    then, link state on the path S-C-B-A turns back to link state of
  115.    Figure-1, and R0 will select the path S-C-B-A-R0 again. And such
  116.    route flapping is repeated forever resulting in an unstable routing.
  117.  
  118.                             +--+
  119.                          +--+R1|                   A,B,C,D,E,F: Router
  120.                        20|  +--+                   S: Sender
  121.      +--+    +---+  16 +-+-+  1   +---+  1  +---+  R0, R1: Receiver
  122.      |R0|----| A |-----+ B +------+ C |-----| S |  Number: Available
  123.      +--+ 21 +-+-+     +---+      +---+     +-+-+          Bandwidth
  124.                |                              |
  125.                |    +---+    +---+    +---+   |
  126.                +----+ D |----+ E |----+ F |---+
  127.                  18 +---+ 20 +---+ 30 +---+  20
  128.  
  129.                               Figure-2
  130.  
  131.    Route Pinning is an existing method to stabilize routing. A receiver
  132.    finds the best path, notifies it to routers on the path, and the
  133.    routers use the specified path. In Figure-1, as the receiver knows
  134.    that the path S-C-B-A-R0 is used by its own flow, it can cancel the
  135.    effect of the flow from the advertised link state of Figure-2 to
  136.    reconstruct the original link state of Figure-1.
  137.  
  138.    The problem of Route Pinning is that it's not good for multicast. For
  139.    example, in Figure-1, if R0 requests a path S-C-B-A-R0 of bandwidth 9
  140.    and R1 requests a path S-F-E-D-A-B-R1 of bandwidth 15, it is not
  141.    naturally possible to merge Resv_msgs with different path
  142.    specifications. That is, there will be two redundant data streams. If
  143.    Resv_msgs are forcibly merged on the router B, then a new path should
  144.    be computed by the router B. As a result, the path S-F-E-D-A-R0 would
  145.    be selected which contradicts with R0's idea of the flow.
  146.  
  147. 2.  Path QoS Collection and Path QoS Correction
  148.  
  149.    To solve the problem, path recomputation at the multicast merge
  150.    points is seemingly inevitable.
  151.  
  152.    That is, we must have a sticky hop-by-hop QoS routing algorithm.
  153.  
  154.    If a QoS routing protocol distributes detailed link state about which
  155.    flow consumes how much resource on each link, each hop can fully
  156.    reconstruct a real resource usage and we can have a sticky QoS
  157.    routing. But, obviously, such a routing protocol distributes too much
  158.    routing information to be scalable.
  159.  
  160.    But, looking closely at the feedback problem, the feedback loop is
  161.  
  162.  
  163.  
  164. M. Ohta                 Expires on May 20, 1997                 [Page 3]
  165.  
  166. INTERNET DRAFT            Path QoS Collection              November 1996
  167.  
  168.  
  169.    formed through upstream resource consumption. That is, to make
  170.    routing sticky, we don't have to resonctruct downstream resource
  171.    consumption.
  172.  
  173.    For the correction of upstream information only, Path_msgs can,
  174.    naturally, carry upstream resource consumption information to break
  175.    the loop for sticky QoS routing.
  176.  
  177.    That is, Path QoS Collection stabilizes fully distributed hop-by-hop
  178.    route computation.
  179.  
  180.    The simple hop-by-hop method is unstable because the receivers and
  181.    the intermediate routers can't know which link state information is
  182.    affected by their own flow. With Path QoS Collection, QoS information
  183.    on links from the ender to the receivers are collected in a Path_msg.
  184.    Thus, even if the link state information of Figure 2 is distributed
  185.    through some QoS routing protocol, the receivers and the intermediate
  186.    routers can reconstruct state of Figure 1, for the upstream links
  187.    toward the sender. For example, between S and R0, Resv_msgs are added
  188.    the amount of QoS consumed by the flow on each link. The router C
  189.    receives ({S-C},9), the router B ({S-C,9}, {C-B,9}), the router A
  190.    ({S-C,9}, {C-B,9}, {B-A,9}) and the receiver R0 ({S-C,9}, {C-B,9},
  191.    {B-A,9}, {A-R0,9}).
  192.  
  193.    Then, the forwarding direction of Resv_msg is decided distributedly
  194.    by individual routers and receivers with the corrected link state.
  195.  
  196.    It should be noted that hop-by-hop QoS routing solves the killer
  197.    reservation problem.  As individual routers know which Resv_msg can't
  198.    be satisfied, killer reservations are bounced before being merged by
  199.    satisfyable reservations.
  200.  
  201.    Figure-3 illustrates the router B's view of the corrected QoS
  202.    information.
  203.  
  204.                             +--+
  205.                          +--+R1|                   A,B,C,D,E,F: Router
  206.                        20|  +--+                   S: Sender
  207.      +--+    +---+  16 +-+-+  10  +---+  10 +---+  R0, R1: Receiver
  208.      |R0|----| A |-----+ B +------+ C |-----| S |  Number: Available
  209.      +--+ 21 +-+-+     +---+      +---+     +-+-+          Bandwidth
  210.                |                              |
  211.                |    +---+    +---+    +---+   |
  212.                +----+ D |----+ E |----+ F |---+
  213.                  18 +---+ 20 +---+ 30 +---+  20
  214.  
  215.                               Figure-3
  216.  
  217.  
  218.  
  219.  
  220. M. Ohta                 Expires on May 20, 1997                 [Page 4]
  221.  
  222. INTERNET DRAFT            Path QoS Collection              November 1996
  223.  
  224.  
  225.    Router B knows that, without the flow, the path S-C-B has bandwidth
  226.    of 10, not 1.
  227.  
  228.    While the QoS information on downstream links R0-A-B is not
  229.    corrected, it increases the stability of the route and is not a
  230.    problem.
  231.  
  232.    The amount of the collected Path QoS Collection information in a
  233.    Path_msg is proportional to the length of the path. That is, only as
  234.    much as the amount of the information necessary for Route Pinning in
  235.    Resv_msg and is not a problem.
  236.  
  237. 3. Multicasting with Path QoS Collection
  238.  
  239.    Merged Resv_msg for multicast, of course, is not an exception and
  240.    forwarded toward the sender over a path that satisfies the new QoS
  241.    requirement.
  242.  
  243.    Suppose that, R0 wants bandwidth of 9 and R1 12.
  244.  
  245.    Then, Resv_msg from R0 (intended to follow a path R0-A-B-C-S) and
  246.    Resv_msg from R1 (intendet to follow a path R1-B-A-D-E-F-S) is merged
  247.    on Router A to be a bandwidth requirement of 12.
  248.  
  249.    Then, router A locally decides that the merged Resv_msg should follow
  250.    a path A-D-E-F-S.
  251.  
  252.    Figure-4 illustrate such an situation.
  253.  
  254.    Note that the receiver R0 will receive Path QoS Collection
  255.    information of ({S-F,12}, {F-E,12), {E-D,12}, {D-A,12}, {A-R0,9}).
  256.  
  257.                             +--+
  258.                          +--+R1|                   A,B,C,D,E,F: Router
  259.                         8|  +--+                   S: Sender
  260.      +--+    +---+  13 +-+-+  10  +---+  10 +---+  R0, R1: Receiver
  261.      |R0|----| A |-----+ B +------+ C |-----| S |  Number: Available
  262.      +--+ 12 +-+-+     +---+      +---+     +-+-+          Bandwidth
  263.                |                              |
  264.                |    +---+    +---+    +---+   |
  265.                +----+ D |----+ E |----+ F |---+
  266.                   6 +---+  8 +---+ 18 +---+   8
  267.  
  268.                               Figure-4
  269.  
  270. 4. Protocol Extensions
  271.  
  272.    First of all, we need a new field, "Path QoS", in Path_msg.
  273.  
  274.  
  275.  
  276. M. Ohta                 Expires on May 20, 1997                 [Page 5]
  277.  
  278. INTERNET DRAFT            Path QoS Collection              November 1996
  279.  
  280.  
  281.    Secondly, Resv_msg shouldn't follow reverse path established by
  282.    Path_msg.  Instead, Path_msgs should follow forward path established
  283.    by Resv_msg.  Resv_msg should work something like PIM_join.
  284.  
  285.    Exact details of what and how QoS information should be collected
  286.    needs further discussion.
  287.  
  288.    For example, it may be better to collect corrected link QoS state on
  289.    each link than to collect consumed QoS and correct it on each router.
  290.  
  291.    For hierarchical routing, QoS may still be collected hop-by-hop or
  292.    QoS information in a lower hierarchy may be aggregated in upper
  293.    hierarchy.
  294.  
  295.    Path QoS field and QoS routing protocol should have common time stamp
  296.    (local to the router which originate the information) to suppress
  297.    race conditions.
  298.  
  299. 5. Requirement and Suggestions for Routing Protocol
  300.  
  301.    As Path QoS correction is performed on link state information,
  302.    unicast routing protocol must be that of link state type.
  303.  
  304.    Moreover, to suppress unnecessarily frequent link state updates, new
  305.    link state should be advertised only when the amount of available
  306.    resource is below the current advertised value, considerably above
  307.    the current advertised value or long enough time has passed since the
  308.    last update.
  309.  
  310.    It is suggested that, when the amount of available resource is
  311.    reducing, the advertised value should be a little less than the
  312.    exactly available amount.
  313.  
  314.    Any multicast routing protocol may be used to forward Resv_msgs.
  315.  
  316.    Path_msgs and data streams should be forwarded to the reverse
  317.    direction to that established by the Resv_msgs.
  318.  
  319. 6. References
  320.  
  321.    [PIM]
  322.  
  323.    [RSVP]
  324.  
  325. 7. Security Considerations
  326.  
  327.    (to be provided)
  328.  
  329.  
  330.  
  331.  
  332. M. Ohta                 Expires on May 20, 1997                 [Page 6]
  333.  
  334. INTERNET DRAFT            Path QoS Collection              November 1996
  335.  
  336.  
  337. 8. Authors' Addresses
  338.  
  339.    Masataka Ohta
  340.    Computer Center
  341.    Tokyo Institute of Technology
  342.    2-12-1, O-okayama, Meguro-ku
  343.    Tokyo 152, JAPAN
  344.  
  345.    Phone: +81-3-5734-3299
  346.    Fax: +81-3-5734-3415
  347.    EMail: mohta@necom830.hpcl.titech.ac.jp
  348.  
  349.    Yukinori GOTO
  350.    Institute of Systems & Information Technologies/KYUSHU
  351.    and Kyushu University.
  352.    Fukuoka SRP Center Building 7F
  353.    2-1-22-707, Momochihama ,
  354.    Sawara-ku, Fukuoka City 814, JAPAN
  355.  
  356.    Phone: +81-92-852-3460
  357.    Fax: +81-92-852-3465
  358.    E-mail: yuki@k-isit.or.jp
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388. M. Ohta                 Expires on May 20, 1997                 [Page 7]
  389.  
  390.