Internet Draft TE-WG Working Group Heinrich Hummel Internet Draft Siemens AG Expiration Date: October 2000 April 2000 Orchestrally conducted Traffic ( OCT ) draft-hummel-te-oct-02.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This draft proposes to engineer traffic such that we can speak of an Orchestrally Conducted Traffic (OCT): Any traffic stream (given by its source and destination nodes and by a priority class) may use several differently routed LSPs. Each, traffic stream ingress reports, periodically, the currently measured traffic load (in bitrate) to a common TE Conductor (TEC) who evaluates them as to forecast what traffic load change might occur in the immediate time ahead. Accordingly the TEC computes well synchronized likelihood values by which to take which route/LSP. These values will be such that any traffic stream will be served as good as possible, as often as possible, while equally ranked traffic streams are treated fair, higher ranked streams are prioritized and the network thruput is maximized. The TEC sends the likelihood values to the respective ingress node, who will distribute the received packets of the traffic stream to the pertaining LSPs accordingly. Hummel April 2000 [Page 1] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 1. Introduction and summary This draft proposes to engineer traffic such that we can speak of an Orchestrally Conducted Traffic (OCT): Any traffic stream (given by its source and destination nodes and by a priority class) may use several differently routed Label Switched Pathes (LSPs). Each, traffic stream ingress reports, periodically, the currently measured traffic load (=bitrate value) to a common Traffic Engineering Conductor (TEC) who evaluates them as to forecast the immediately upcoming traffic load. Accordingly the TEC computes well synchronized likelihood values by which to take which route/LSP. These values will be such that any traffic stream will be served as good as possible, as often as possible, while equally ranked traffic streams are treated fair, higher ranked streams are prioritized and the network thruput is maximized. The TEC sends the likelihood values to the respective ingress node, who will distribute the received packets of the traffic stream to the pertaining LSPs accordingly. 2. OCT concept in detail 2.1 Goals and Basics The OCT concept is based on a periodic information exchange between the ingress nodes of all traffic streams and a central Traffic Engineering Conductor (TEC). For now, it is assumed that communication channels are established (i.e. special LSPs) to cater this information exchange. It is also assumed that one or several differently routed LSPs per traffic stream are established for carrying the user data. The OCT concept solves the question "by which likelihood should which LSP been taken so that the entire traffic is balanced best onto the given network ?" Best balancing includes many aspects, some of which have already been mentioned: Higher ranked traffic streams shall be prioritized versus lower ranked traffic streams. Equally ranked traffic streams shall be serviced equally fair. The thruput should be maximized. But implicitly there are even more properties of "best balancing": avoiding congestions as best as possible, resolving a congestion without creating a new congestion at just another location. Maximizing the thruput: It means: Among equally ranked traffic streams, give preference nevertheless to that portion of a traffic stream that can be serviced by a shorter LSP (using less hops). Eventually such a preferenced handling is beneficial to all traffic streams (e.g. so that all traffic streams can be completely serviced rather than some are more, some are less deteriorated). Eventually however the traffic streams that use shorter LSPs are indeed better Hummel April 2000 [Page 2] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 serviced than the others. Conclusion: Maximizing the thruput is more important than equal treatment. Let us partition the whole traffic into traffic streams T(i,e,p), each of which is identified by an information-triplet {i-ngress node, e-gress node, p-riority class}. By other words, a traffic stream is the sum of all IP-Micro flows which enter the MPLS network domain at the same node (= ingress node), which will leave the MPLS network domain at the same node (=egress node) and which share the same priority class, based on their DiffServ parameters. For each traffic stream T(i,e,p) there shall be n(i,e,p) pre-established label switched pathes, i.e. LSP-k; k=1,...,n(i,e,p), for transmitting its packets. LSP-1 shall be the most preferrable one, LSP-n(i,e,p) the least preferrable one. An ingress node i knows all traffic streams T(i,e,p) it originates. For each of them it knows all respective n(i,e,p) LSPs, incl. all their link sequences, and measures, continuously, the respective current total traffic load as well as the individual current traffic load share per LSP. Periodically the ingress node i reports the total traffic load (in bitrate) as well as the LSP-specific traffic load shares to the TEC -with respect to all traffic streams it originates. Besides these reports, the TEC shall know the network topology incl. the maximum bandwidth BWj of each network link j. Furthermore it shall know the link sequences of all LSPs for all traffic streams in the network. The sending of the reports to the TEC by all ingress nodes may be slightly jittered, but by neglecting the jitter, the TEC shall receive all reports with respect to the same time of day. It is advisable that any report also contain either the exact time of day it has been sent or that time of day the report is meant for. 2.2 Forecasting traffic load The TEC may apply different mathematical/heuristical methods, algorithms, concepts, theories as to compute / forecast the total traffic load TTL (i,e,p) for each traffic stream T(i,e,p). For example, two methods are shown by the following: Method 1: Make a linear extrapolation based on the youngest traffic load value at time t-1 ("t minus one") in the past and the present traffic load value at time t0 ("t zero"), as to determine the future traffic load at time t1 ("t one"). If total traffic load TTL(i,e,p)(t1) exceeds Hummel April 2000 [Page 3] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 the highest traffic load ever reported for traffic stream T(i,e,p) then replace the extrapolated value by the highest total traffic load ever reported for T(i,e,p). If total traffic load TTL (i,e,p) (t1) turns out negative then replace this value by the value 0 + epsilon. Method 2 (very promising, if upstream from ingress node i* there is a webpage of general interest): Build the average traffic load AVTL (i*,e,p) (t0) out of all currently measured traffic loads TTL (i*,e,p) (t0) and forecast for all traffic streams TTL(i*,e,p) (t1) = AVTL(i*,e,p) (t0). Certainly there will be more methods as to forecast any total traffic load for time t1. Learning from the success: Note that one report-timer-interval later the prognosticated traffic load can be verified, how well it turned out. We can make statistics which method is more often more successful than the other methods. We may apply the more successful method more often ! So we may learn from the success. 2.3 Prosaic description how to compute likelihood values Imagine the TEC as a person sitting in front of a casino table. On the table however, the topology graph of his network is drawn. On each ingress node i the TEC has placed, with respect to traffic stream T(i,e,p), a pile of uniformly sized (traffic load) chips: The height of the pile amounts to the absolut value of the forecasted total traffic load TTL (i,e,p) (t1). Let's call it total traffic load-pile. (Eventually, at the bottom of any such pile, there may be a chip whose size is smaller than the uniformly sized chips.) On any link j of the network there is also a pile of (bandwidth) chips whose height amounts to the maximum bandwidth BWj of that link. Let's call it link-j-bandwidth pile. (Eventually, at the bottom of any link-j-bandwidth pile, there may be a chip whose size is smaller than the uniformly sized chips.) The goal is to distribute the chips of each total traffic load-pile by piling up respective LSP-specific traffic load piles. Eventually, a remainder of the total traffic load-pile cannot be distributed in a way which is shown next. It will reflect that proportion of the Hummel April 2000 [Page 4] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 traffic load which cannot be transmitted. The TEC processes one chip after the other, each time,at least in general, from a different total traffic load-pile: The TEC tries to move the chip to the k-th LSP's pile; (k=1,2,...,n(i,e,p) ). At the beginning k=1. Whenever a traffic load chip is moved to the k-th LSP-specific pile, a (same sized) bandwidth chip is removed from each link-j-bandwidth pile of all those links j which this k-th LSP traverses. If this is not feasable because at least one of these links lacks such a bandwidth chip, the same is tried with the (k+1)st LSP. If it is not feasable with any of the n(i,e,p) LSPs then there will be a remainder total traffic load pile whose (normed) height will indicate the likelihood by which a packet from traffic stream T(i,e,p) shall not be transmitted. The sequence by which the traffic load chips of all total traffic load -piles are handled as described above is very important as to: achieve fairness among equally ranked traffic streams, priortize/discriminate higher/lower ranked traffic streams, and get best thruput: Higher ranked traffic streams will be preferred versus the lower ranked traffic streams by processing ALL their traffic load chips first. Fairness among equally ranked traffic streams will be achieved by processing their traffic load chips alternatingly. However, make also the following exception: Among equally ranked traffic streams process at first those traffic load chips which can be moved to "shorter" LSPs, i.e. to LSPs with fewer hops. When all the traffic load chips have been processed, the heights of the resulting LSP-specific piles and of the remainder pile need to be normed i.e. divided by the sum of all these heights as to get likelihood values. The TEC shall send back to any ingress node i these likelihood values with respect to all traffic streams T(i,e,p) which are originated at that node i. 2.4 Distributing the traffic load onto the LSPs An ingresss node must distribute the received traffic load onto the respective LSPs according to the likelihood values. Ingress node i whichs receives a new IP packet may identify the traffic stream to Hummel April 2000 [Page 5] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 which this packet belongs. I.e. it may identify its egress node based on its IP destination address and may identify its priority class based on its Diffserv parameters. (a): In accordance with the actual likelihood values it will select an appropriate LSP for transmitting this packet, respectively will dishonor its forwarding request: The ingress node may build a hash with respect to the IP source addresses of the IP packets of T(i,e,p). The simplest hash is such that it intersects the entire IP UNICAST address space into n(i,e,p) +1 intervalls. The sizes of these intervalls shall be proportional to the likelihood values. The IP source address of a received IP packet of a particular traffic stream will be examined as to determine from which interval it is part of. If it is from the k-th interval, then it is forwarded along the k-th LSP; k=1,...,n(i,e,p). If it is from the n(i,e,p)+1 st intervall, then it is not forwarded at all. This very simple hash mechanism suits best if the ingress node is fairly in the "center of the internet", i.e. receives IP packets containing any existing IP UNICAST source address. (b): An ingress node i (e.g. of an access network) may know, by means of network management configuration or by learning while operating, the appropriate candidate IP source address range which may be intersected as to form the right hash-intervals. (c): If an ingress node receives IP packets from a fairly limited number of sources, e.g. given by less than 100 different IP source addresses, it may be feasable to queue up information pertaining to all currently active IP micro flows: A queue element may consist of an IP source address and the LSP to be selected. If the first packet of a new IP micro flow is received, i.e. if no queued information can be found that matches the received packet's IP source address then a new queue element must be allocated whose LSP information may be determined by this: Generate a random number which hits/selects any column of a statistical stage function which is built from the likelihood values. The k-th column will select the k-th LSP. It shall be used and also entered in the new queue element. Any succeeding packet of a particular IP micro flow may be sent along the same LSP. Advantage: all packets of the same IP micro flow will arrive in proper sequence at the egress node. A mechanism needs to be added to determine the end of the lifetime of an IP micro flow, i.e. the point in time when a queue element is deleted: Maintain an information in the queue element which is refreshed/incremented by the transmission request of each packet of the IP micro flow. Employ Hummel April 2000 [Page 6] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 a periodic timer. Whenever it expires check all queue elements for all traffic streams originated in this ingress node whether they are aged out. If so, delete them. 3. Further Aspects 3.1 Other traffic load input: The TEC may also receive information about SCHEDULED traffic from other senders than the ingress nodes. Such senders may be a policy agent or a Network Management station/agent. 3.2 Adding/Removing another LSP per traffic stream 3.2.1 Adding an LSP: In the preceding it was assumed that there are some LSPs per traffic stream, without saying when and why an(other) LSP may be added or removed. An obvious reason for establishing another LSP is given, when the TEC determines a considerable likelihood for NOT forwarding some packets of the traffic stream along any of the existing LSPs. Indeed, the TEC may compute the route for another LSP while taking into account the currently available bandwidth in the network due to the present traffic loads and may send to the right ingress node the computed route for the new LSP - as well as the likelihood by which to use it. 3.2.1 Removing a LSP: Over a longer period of time, an ingress node just like the TEC may notice that an LSP is hardly used. It may be aborted. TEC and ingress node must inform each other. 3.3 Delaying instead of dishonoring packet transmission Despite of best traffic balancing and even despite of 3.2 there may be IP packets whose transmission request might be dishonored. Alternatively, their transmission may only be delayed. Further study is required how to do it and what are the consequences with respect to the entire "traffic balancing result". 3.4 On-demand LSPs: Another variation would be to establish LSPs just on demand. The ingress node may have for a traffic stream, instead of a set of existing LSPs, a set of routes to choose from. The described procedure as to determine the right LSP for transmitting an IP packet may be applied analogously however as to determine the explicit route to use when the on-demand LSP is to be established. Hummel April 2000 [Page 7] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 3.5 Long term results Over a longer period of time, while and though the total traffic is orchestrally conducted, the TEC may find out which links are permanently under-utilized resp. over-utilized and may conclude which links should be stocked up by which amount of bandwidth respectively may conclude which links may be removed or used differently by becoming re-configured. Determining to which extent a link is permanently under-utilized: Simplest method: determine the smallest available bandwidth ever of that link. Determining to which extent the bandwidth of a link should be stocked up: After the TEC has computed and sent out the likelihood values for all traffic streams, it may compute likelihood values for a fictitious "should be"-network by the following: In one additional cycle the TEC may process each remainder TTL (i,e,p)-pile like being one big chip and by moving this "big chip" onto its most preferred LSP-1. Hereby substract from each affected link-j-bandwidth pile the size of this "big chip" and do not mind if the height of any link-j-bandwidth pile becomes a negative number. Indeed,after this cycle any resulting negative link-j-bandwidth pile, indicates the absolute amount of bandwidth by which link j should be stocked up. Of course, average values should be built, over a longer period of time, as to determine the permanent over/under-utilization of any link in the network. 3.6 Equally ranked LSPs So far it has been assumed that per traffic stream T(i,e,p) there are n(i,e,p) LSPs and that they are in ranking order: LSP-1 > LSP-2 >....> LSP-n(i,e,p) . LSP-1 ist the most favorable LSP, LSP-n(i,e,p) is the least favorable LSP e.g. in the sense that the more favorable LSP consists of fewer hops than the less favorable LSP. However among the n(i,e,p) LSPs there may be subsets of LSPs which are equally favorable and should be treated as equally ranked. Accordingly, when another traffic load chip shall be distributed to any LSP-specific traffic load pile, we should at first try any LSP from the best ranked subset of LSPs. That LSP should be selected such that an even distribution among the LSPs of this subset is warrented (which is accomplished by proper alternation). Hummel April 2000 [Page 8] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 Proceed analogously with the next ranked subset of LSPs, in case no LSP of the better ranked subset can accommodate this chip. 3.7 Central TEC versus de-centralized solutions This OCT concept operates with a central TEC. There may also be other alternative concepts which operate in a de-centralized fashion. In case the TE-WG is interested in standardizing a protocol according to this OCT concept, I would like to point out one important advantage of the centralized solution, i.e. one associated standardization objective: The ingress nodes have to be provided with some basic initial software - just like the TEC. Later on the TEC may get smarter and smarter by getting newer software versions. At the same time however the ingress nodes can keep their old initial software. 3.8. Standardization - required / not required It is possible to install the OCT concept in a completely proprietary fashon, i.e. without standardizing any new messages , TLVs , codepoints or well-known TCP port number. In a simplest implementation special p2p LSPs are established from each ingress node to the TEC and vice versa for exchanging all relevant information in proprietary syntax. Alternatively the TEC may send out the likelihood values down a spanning tree, which is provided by a tree-structured source routing information called TREE ROUTE TLV, see [3], whereby each node i* will become aware which part of the received info is to forward along which child link and which part is just targetted to itself - which are all likelihood values for all traffic streams T(i*,e,p). It is up to the TE-WG (and maybe others) whether or not to standardize all required protocols and formats with respect to the communication between any ingress node and the TEC, as well as between any Network Management and/or Policy Agent and the TEC. 4. Intellectual Property Considerations Siemens AG may seek patent or other intellectual property protection for some or all of the technologies disclosed in this document. If any standards arising from this document are or become protected by one or more patents assigned to Siemens AG. Siemens AG intend to disclose those patents and license them under openly specified and non-discriminatory terms. 5. References Hummel April 2000 [Page 9] Orchestrally conducted Traffic (OCT) Exp. Oct. 2000 [1] "Traffic Engineering Concept", draft-awduche-mpls-traffic-eng-00.txt, Awduche [2] "Provider Architecture for Differentiated Services and Traffic Engineering (PASTE)", 1/1998, draft-li-paste-00.txt, Li, Rekhter [3] "Explicit Tree Routing",draft-hummel-mpls-tree-route-01.txt, Hummel, Loke 6. Author's Address Heinrich Hummel Siemens AG Hofmannstrasse 51 81379 Munich, Germany Tel: +49 89 722 32057 Email: heinrich.hummel@icn.siemens.de Full Copyright Statement "Copyright (C) The Internet Society (March 2000). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implmentation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. Hummel April 2000 [Page 10]