Network Working Group Jun Kyun Choi (ICU) Internet Draft Dipnarayan Guha (ICU) Category: Standards Track Jin Ho Hahm (ETRI) Expires: April 2005 October 2004 Path Computation Element Metric Protocol (PCEMP) draft-choi-pce-metric-protocol-00.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. By submitting this Internet-Draft, we certify that any applicable patent or other IPR claims of which we are aware have been disclosed, and any of which we become aware will be disclosed, in accordance with RFC 3668. Abstract In this draft, we propose an analysis of a Path Computation Element Metric Protocol (PCEMP) that acts as a generic computation model for path based metrics in large multi-domain or multi-layer networks. The mechanism that is described in this draft is generic and can serve as an application path computation framework for any Path Computation Element (PCE) This draft proposes to elucidate protocol independent metrics defining path quality measurement criteria, algorithm complexity and scalability criteria related to path computation techniques through the PCEMP and is in line with the PCE WG Charter. Choi, Guha et al. Standards Track [Page 1] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 Table of Contents 1 Terminology ................................................. 3 2 Introduction ................................................ 4 3 Key features of PCEMP ....................................... 4 3.1 Other features of PCEMP ................................. 4 3.2 Cost of the protocol metrics ............................ 6 4 Overview of Soft Memory and Path Computing Unit requirements................................................. 7 4.1 Protocol level hierarchy architecture on the control plane......................................................... 7 4.2 PCE unit architecture as seen by the PCEMP protocol...... 9 5 The Path Computing Element Metric Protocol Data Structure (PCEMP DS)................................................... 9 6 Implementation considerations of the PCEMP protocol architecture................................................. 10 6.1 PCEMP State Machines Design.............................. 11 6.2 Functional Parameters for PCEMP DS processing of long sequence data................................................ 11 6.3 Realization of fast path computing unit architecture using PCEMP.................................................. 11 6.4 Fundamentals of the PCEMP Algorithm as a function of CPCA ........................................................ 12 6.5 PCEMP FSM Diagrams ...................................... 13 6.5.1 PCEMP Events ..................................... 14 6.5.2 Changing data vector profile PCEMP FSM ........... 15 6.5.3 Static data vector profile PCEMP FSM ............. 16 6.6 Flow Logic of the PCEMP FSM and design considerations ... 17 7 Analysis of the PCEMP metrics in terms of protocol cost ..... 17 7.1 Link Bandwidth ......................................... 17 7.2 Router memory .......................................... 18 7.3 Router CPU usage ....................................... 19 7.4 Role of CC and SPC ..................................... 19 8 Conclusion .................................................. 20 9 Security Considerations ..................................... 20 10 IANA Considerations ......................................... 20 11 Acknowledgements ............................................ 21 12 Intellectual Property Considerations ........................ 21 13 Normative References ........................................ 22 14 Informational References .................................... 22 15 Authors' Addresses .......................................... 23 16 Full Copyright Statement .................................... 23 Choi, Guha et al. Standards Track [Page 2] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 1. Terminology This memo makes use of the following terms: 1. Path Computation Element (PCE): an entity that is responsible for computing/finding inter/intra domain LSPs. This entity can simultaneously act as a client and a server. Several PCEs can be deployed in a given Autonomous System (AS). 2. Path Computation Element node (PCE Node): a network processing unit comprising of a PCE unit. This can be embedded in a router or a switch. 3. Domain: Denotes an Autonomous system (AS) within the scope of this draft. Choi, Guha et al. Standards Track [Page 3] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 2. Introduction This draft addresses the metric definition and analysis requirements of PCE models set forth by the PCE WG Charter for an internet routing protocol. Some of these requirements are stated as follows. The next sections of this draft go on to show how PCEMP can be a satisfactory answer to efficient intra and inter domain path computation and routing. -> Key algorithm feature of the proposed protocol mechanism -> PCE controller memory and controller CPU cycle costs of protocol -> Scalability of the algorithm and protocol metrics in large multi domain and multi-layer networks. -> Limits of protocol metrics -> Adaptibility of algorithm for different centralized and distributed path computation scenarios -> Genericness of the mechanism and easy integrability with current PCEs and router hardwares 3. Key features of PCEMP This section summarizes the key features of the PCEMP protocol. PCEMP is a generic domain routing and path computation protocol that runs on any PCE unit that is capable of computing a path based on an ordered graph. PCEMP uses data vector techniques for path computation. Individual link state advertisements (LSAs) are mapped onto the computation units directly at TE-LSP setup time. Each PCE unit maintains this mapping information through the controller unit [1] and the mapping synchronization of the Link State Databases (LSDBs) are performed using PCEMP finite state machines. From this central controller sub-units, each PCE constructs a routing table by calculating a shortest data vector tree, the root being the calculating PCE node itself. 3.1 Other features of PCEMP The other features of the PCEMP protocol are: 1. Central Controller (CC). The central controller acts as the Choi, Guha et al. Standards Track [Page 4] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 originator of the network's local information environment. The controller also acts in the global scenario of inter domain PCEs and inter layer networks. It serves as the key functional point of the data vector driven algorithm for all PCE information and link state synchronizations by co-ordinating LSP advertisements from other PCEs and LSRs (All PCE peers). 2. Soft PCE Controller (SPC). A Soft PCE Controller is an entity designed primarily for protection and fast route establishment in conjunction with the Central Controller. The SPC's primary functionality is to provide a robust and real-time path computation adjacency without crossover delays for the data driven algorithm mechanism. Also, this enables the LSP state and path computation state retention in case of nodal faults and hardware failures. 3. Support for peer adjacency through non-participating interior nodes. PCEMP treats these nodes opaquely and is able to maintain the PCE adjacencies over inter-domains and inter-layer networks. The protocol is generic and can be easily carried over existing routing mechanisms over non-supporting network clouds. There is no necessity for any additional configuration updates for PCEs attached to such networks for initial discovery as the data driven mechanism is flow based. 4. PCE domain areas (PCEDA). PCEMP allows the formation of distinct PCE domain areas in a specific domain for end-to-end peer participations. This is useful for several reasons. This is in line with the protocol architecture that provides a granularity of data protection within an autonomous system and isolation of data to local branches of the tree. This is also helpful for the design of the PCE units using soft memory techniques and reduces the algorithm operation costs. 5. Data driven mapping of external routing information. In PCEMP, each external route is imported into the PCE domain area in separate data driven computation strategies. This reduces the amount of instantaneous re-computation of routing traffic data. It also enables partial controller database updates when there is a partial external route change. 6. Three level functional control hierarchy. PCEMP has a three level controller hierarchy, intra-PCE-domain, inter-PCE-domain and external-PCE-domain. This is discussed in the context of the Centralized Controller [1]. Choi, Guha et al. Standards Track [Page 5] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 7. Virtual link mapping. This is done via the real-time configuration of logical local links based on the data-driven strategy of the algorithm. The mechanism is thus made topology independent and generic. 8. Soft Computation Memory (SCM). This is a novel feature in terms of path computation in the CC and SPC. It helps split the tree into a combination of sparse subtrees for fast computation. SCM can be used to assign metrics of path computation as well as compute data-driven flow based mappings in the PCE. 9. Data-driven routing metric. In PCEMP, the computation metrics are assigned to the outbound router interfaces and the soft memory cycles in the PCE controller unit. The cost of a path is then the weighted sum of the path's component interfaces and the soft memory cycles. The routing and external path metrics can be assigned externally. 10. Flow-based routing. Separate sets of paths can be computed for each type of service. This is done by assigning flow-based metrics to each outgoing router interface. 3.2 Cost of the protocol metrics This section analyzes the metrics that build up the PCEMP protocol metrics 1. Link Bandwidth. In PCEMP, the link state synchronizations are done using a data-driven strategy scheduling mechanism as will be shown later on in this draft. There is still backward compatibility with existing mechanisms like OSPF that physically advertise using reliable flooding schemes. Synchronization of link state databases reduces to a degeneration of individual link state machines' management in the CCs. This fits in well to the case where size of the TE-LSDB (Traffic Engineering Link State Database) increases and there is practically no change in the amount of link bandwidth used. Choi, Guha et al. Standards Track [Page 6] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 2. Router hardware memory and CPU usage. To consider the constraints of router hardware memory, PCEMP uses finite state machines in the SCM model for path computation. Still, this can be an imposing constraint even in the presence of many external LSAs. Dividing the path computation domain into multiple PCEDA can reduce this to a large extent. The length of time it takes to run PCEMP is a function of the finite state machine tree alignment on a given CC and SPC. Once the end-to-end peer PCE systems are determined, this becomes independent of the number of participating entities. 3. Role of the CC and SPC. The CC is responsible for handling data vectors and synchronization of different link states. The SPC acts a fast path computation mechanism in case of crossover and faults. This conjunction makes the PCE's functioning much more efficient. 4. Overview of Soft Memory and Path Computing Unit requirements This draft describes the architecture of the PCEMP protocol using soft memory concepts in the context of path computing block requirements. The network graph is constructed and analyzed real time inside the core of the PCE node with the aid of soft decision algebraic polynomial algorithms. The system is robust and guarantees efficient path computation for large scale data vectors and handles efficient segmentation of inter-domains and inter-layer networks into PCEDAs during path computation. It also reduces computational complexity of data intensive processing. We define a structure called the Path Computing Element Metric Protocol Data Structure (PCEMP DS) that makes up the system map for PCEMP state machines. The CC and SPC executes transforms as core computational units where the path computing algorithms for handling the entire data vector is processed, thereby reducing the computational complexity to a large extent. This draft addresses the requirements of a PCE unit block that helps to ease computationally intensive data processing for integrated provisioning in inter-domain and inter-layer networks. The PCEMP along with the CC and SPC as part of the PCE unit enables an integrated network architecture where each network layer can freely exchange topology and resource information. This allows network performance to be globally optimized across all layers. In addition, a single control plane and the central controller that manages all network layers greatly simplifies network management tasks. 4.1 Protocol level hierarchy architecture on the control plane In an integrated control plane, three levels of functional control hierarchy are mapped into one PCE node in the core of the Network Processing engine and implemented as a single unit. PCEMP thus has a three level controller hierarchy, intra-PCE-domain, inter-PCE-domain and external-PCE-domain. Choi, Guha et al. Standards Track [Page 7] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 The functional blocks involved in the PCE node are: the network processor (the network management system with extended functionalities), the domain processor (the network element management system with extended functionalities), and the node processor. These are invoked by the PCEMP state machines and comprise the fundamental protocol level hierarchies on the control plane. In the first level, the network processor acts as an interface between users and all sub-network domains. Its' main functionality is to oversee the provisioning of new connections across multiple sub-networks and to maintain the network-wide topological view by reducing the computational domains to PCEDAs. The domain processor supervises tasks within a sub-network domain, such as service provisioning and network status monitoring. It handles requests for connection setup and teardown, and computes explicit paths that meet the SLA of each request. The network monitor observes the overall network health and detects failure and repair events. The databases maintained by the domain processor include the domain topology, the domain link state database gathered via the LSA protocol within its domain, and the domain connection database which keeps track of all established connections in the domain. The node processor manages specific functionalities that can be done in a distributed manner at each node, such as overload handling, failure recovery, and status monitoring. It also detects sudden link overloads, conducts a countermeasure and provides rapid protection and restoration capability in times of failure. The databases maintained by the node processor are the local link state and the local connection databases. The local link state is obtained automatically via the neighbor discovery protocol, while the list of local connections is obtained from all connections that traverse the node. These are implemented using soft memory concepts and synchronized using PCEMP. For the purpose of establishing a guaranteed a disjoint backup path and fast restoration techniques in the participating PCEDAs, it is essential that the large scale data processing in the CC and SPC have minimum overhead and processing delay. The CC manages the entire domain network, as discussed before. In this architecture, backup paths can be easily established end-to-end using the logical configuration in the SPCs using PCEMP. Based on the data driven routing metric table, which is configured at each PCE node by the CC, one can make a robust real-time path between a source node and a destination node and many intermediate nodes between the two. This is done using soft decision PCEMP algorithms. Choi, Guha et al. Standards Track [Page 8] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 4.2 PCE unit architecture as seen by the PCEMP protocol These are the PCE unit architectures as seen by the PCEMP protocol state machines during path computation: 1. A matrix and parallel vector arithmetic unit that provides parallel data processing capabilities on the commonly used matrix and vector mathematical data types. Performance of this unit is independent of the size of the data vector under computation. This is implemented in the CC and SPC. 2. The processing core that provides the ease of programming and flexibility to address changing algorithms and standards. There exists a one-to-one map from the transform computed by the core to the high-level code generated by the PCE application. This is implemented using soft memory techniques in the CC, SPC and SCM. 3. A high-speed I/O system that allows complex, adaptive algorithms to be partitioned cost-effectively across multiple sub PCE unit blocks by providing dual ports. These ports are logically indistinguishable across the ordered pair of a data vector and the corresponding transform that is executed. These units are images of the PCE computing unit that are mapped onto the PCEMP state machines. 5. The Path Computing Element Metric Protocol Data Structure (PCEMP DS) This data structure is ideally a multidimensional array of ordered pairs of a data vector S, a transform T, and a mapping * to the system computing code. The description of the PCE unit block and memory architecture is in terms of this fundamental unit of computation. There are unique maps that exist between the PCEMP DS and the transform library that forms part of the PCE unit core. The elements of the vector S is again thought of as a key-record pair R (k,t) where k is the pointer of the components of the data vector S and t is the associated structure or a pointer to the structure to the corresponding executable transform T. Choi, Guha et al. Standards Track [Page 9] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 Investigations into the methods to achieve parallelism of operations in different protocol engine architectures comprise solutions in form of machine architectures designed to execute transforms effectively; and of algorithms that allow concurrent accesses to search PCEMP DS'. If a complex transform is executed by a number of multiprocessors in the engine in parallel, then the best speed-up possible is logarithmic in the number of processors. The suggestion is therefore to increase the total throughput in the executing transforms and operations by increasing the number of instructions that can be handled by the protocol state machine at the same time rather than the speed-up of individual instructions. This is what makes the processing of large sequence data vectors so effective with a high degree of parallelism in the context of Path Computing. 6. Implementation considerations of the PCEMP protocol architecture This section discusses about the architecture of the PCEMP DS, outlay and mapping of protocol iterator instantiates to PCE unit blocks. -> Protocol System Architecture: PCEMP DS decoder architecture and path computing core that interfaces with the network processing engines in the PCE nodes. -> Protocol System Specifications: An efficient algorithm for running in the computing core of the PCE units, called the Combinatorial Path Computing Algorithm (CPCA). This algorithm is the fundamental block that co-ordinates the PCEMP state machines and describes the decoder that processes arbitrarily large input data sequences using SCM. The memory structure of the protocol processing engine is implemented in terms of these soft decoder algorithms. The method reduces hardware and path computing complexity considerably. -> Protocol System Requirements: High Level Path Computing Transform Library Choi, Guha et al. Standards Track [Page 10] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 6.1 PCEMP State Machines Design Definition: A unifying concept that ties together the CPCA and protocol level processing. These mathematical programs are selected on the PCE node block structure by the PCEMP DS based on the input data sequence real-time and implemented as a dynamic data driven tree partitioning. Concept: A function that is mapped onto the CPCA and PCE computation (PCEC) classes and outputs the path computation unit length. This parameter is benchmarked for performance in processing time and computational complexity of the PCE unit and invoked CC and SPC metrics. Iterator Self-Reflection of Types Design: The ONP DS is a general framework supporting CPCA and PCEC modes of computation in the PCE unit. Self-reflection of type instantiates two iterators that share a common constructor class. The iterator types are of type CPCA and PCEC, and called during compile-time to generate the necessary control structure output. This helps in implementing the data-driven strategy for path computing real-time and forms the basis of PCEMP State Machines design. 6.2 Functional Parameters for PCEMP DS processing of long sequence data The input data sequence is arranged into an ordered set called the Input Data Type (IDT) which is a subset of the input vector S and a function of the control transform to be computed T. A State Subset is a member of the cardinal product of S and T. It is shown to be isomorphic with the logical decoder outputs. The IDS invokes the hardware for computing across the partitioned kernel in the PCE nodes. Input: IDT Tj, State Subsets Sl and Sm, Integers l and m, Label Lb, Semi-Ring R; Output: Flow metric/measure p(A,B) 6.3 Realization of fast path computing unit architecture using PCEMP Concept: Iterative applications of the PCEMP DS. Two or more IDT encoders separated by an interleaver (respectively CC and SPC). This structure suggests a decoding strategy based on the iterative passing of soft-computing information between two decoding algorithms. This is equivalent to dynamically partitioning the path computing engine core into sub-units that are linked together real-time based on the input data and the protocol handler. Basic Computation: Configure PCEMP DS to compute soft-decisions in terms of measures. An assigned measure is given to each branch of the IDT. This algorithm makes the data intensive path computing much easier and reduces overhead and complexity and is incorporated in the computing core. It also guarantees disjoint path computation that enables fast end-to-end backup and protections. Choi, Guha et al. Standards Track [Page 11] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 6.4 Fundamentals of the PCEMP Algorithm as a function of CPCA Let A belong to Sm and B belong to Sl. A and B are thus sets of states with m and l. Initialization: For each s in Sm, r(Sj,s) = 1 when s is in A else 0 xt(0) =1, xt(m) = 0, m is not zero Loop: /* For Decoder i to Decoder k, CC and SPC */ /* For j = m+1, m+2,...,l, for each s2 in Si, */ /* Label branch bout with input m and three outputs (c0,c1,x1); */ /* c0 = common symbols between the two encoders, CC and SPC */ /* c1,x1 = PCE unit inputs */ call decoder_private; /* populates decoder specific private data*/ /* This is populated by data driven mapping of external routing */ /* information. In PCEMP, each external route is imported into */ /* the PCE domain area in separate data driven computation */ /* strategies */ u(y|c0) = load file_channel; /* populates PCE unit kernel */ /* specific data */ /* This is populated by the peer-to-peer information exchange */ /* by the functional blocks involved in the PCE node. i.e. the */ /* network processor, the domain processor and the node */ /* processor */ u(y|m) = rel (u(y|c0), u(c1,x1|c0,y); /* This is SCM specific kernel computation that involves a data- */ /* driven partitioning of the ordered graph based on iterator */ /* instantiates */ assign p = probability(c0); /* This is the probability that the PCE computing is actually */ /* invoked for computing upon data vectors that show a significant */ /* change in the data profile sequence, else it is just buffered */ /* and tagged for decision making. */ /* This reduces computational overhead and unnecessary kernel */ /* calls for data intensive path computing */ assign y = u(c0).u(y|c0).decoder_private; log p(Si, xj) = log sum (si, xj-1) + log sum (zj) over all b in Bi, y(b) = u(m).u(y|m).decoder_private; invoke Fast_Decoding_Procedure; /* This procedure has been described in the context of iterator */ /* self-reflection types in Section 5.1 */ Choi, Guha et al. Standards Track [Page 12] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 /* This essentially means this: */ /* for m to l all the state indices, */ /* for all the branches on the corresponding graph of the PCEMP DS */ /* IDT, obtain the sum of the logarithms of the corresponding */ /* weights and optimize it for choosing the correct points on */ /* the graph. This a continuous, cumulative and dynamic process */ /* which involves minimum computation overhead and provides a */ /* guaranteed fast crossover for path computation and backup */ /* protection */ Stop: p(si,xj) = min log (sum (si, xj -1) /* Store the sums obtained in the Loop and then equate to the */ /* final sum */ /* Fast path computing procedure for large sequence input data: */ /* 1. Setup: Use the received kernel data to compute the common */ /* and private soft channel information */ /* 2. Iterate: Repeatedly update, for the outer and inner decoder, */ /* the iterative information by updating u(c0) and u(m). The */ /* computation involves a forward and backward application of the */ /* PCEMP DS with the complete branch measure. */ /* The extracted measure for the common symbol is computed based on */ /* (x,y1,z) using the private branch measure */ /* 3. Conclude: The extracted measure for the control symbol m is */ /* computed based on (x,y1,z) using the complete branch measure z */ 6.5 PCEMP FSM Diagrams Based on the above algorithm and analysis, we can consider two distinct finite state machine diagrams of the PCEMP protocol architecture: 1. The case where the PCE unit block is invoked for constantly changing data profiles within the time of test of goodness of fit (MAX_PCE_TIME_FIT) 2. The case where the PCE unit block is invoked only once for a variable data profile and then the data is tagged (tags) within the time of test of goodness of fit (MAX_PCE_TIME_FIT). max tags is an important parameter to determine the computing potential within MAX_PCE_TIME_FIT Choi, Guha et al. Standards Track [Page 13] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 6.5.1 PCEMP Events PCEMP events are generated by the protocol processing routine iterators and by the state machines of the associated TE-LSP links. Every event has its number and a symbolic name. Here is a possible description of PCEMP events: 1 :PCEStart: This is when the PCE node receives a request from an adjacent peer 2 :PCEEnd: This is when the PCE node receives a request from its adjacent peer that the path computation has ended and the exchanged metrics acknowledged 3 :PCETest: This is an event that signifies the formation of PCEDAs and invokes the exchange of data vectors over the link. 4 :PCEResponse: This is an internal PCE unit kernel event that listens for the received data vectors. 5 :PCETestACK: The initial information exchange between a pair of adjacent PCE peers has been successful and acknowledged. (a) This event indicates the CPCA and PCEC classes have been instantiated by the initial exchange of information and the data driven mapping of external routing information is complete. (b) This event indicates the PCE unit is ready for path computation, but the ACK has not been explicitly taken into account. This is done to minimize unnecessary packet overhead during path computation information exchange. Tags are sufficient to convey this information. 6 :PCEMPTest: Data vector was successfully received over the designated port and a PCEMP Fast_Decoding_Procedure has been invoked and the message sent to the peer. 7 :PCEMPFail: This is when there is a protocol error in processing the PCEMP fast decode output messages or when there is a failure message received from the PCE peer. Choi, Guha et al. Standards Track [Page 14] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 8 :PCEMPDetectFail: This indicates that a PCEMP fast decode output failed to compute within the specified alive timer. 9 :PCECompute: The CC and SPC have been invoked in the PCE node. 10:PCEDeCompute: The CC and SPC have been released in the PCE node. 11:PCEMPRetransmit: The peer sends another refresh message to the PCE node 12:PCELocalFail: Port and/or interface mismatches with the data vectors and output written metrics 13:PCEDataFail: There is a local fault related to the receiving of the data vectors and this is taken into consideration while assigning the measures to the output graph. 14:PCEDataDown: The data vector stream has terminated 6.5.2. Changing data vector profile PCEMP FSM Figure 1 illustrates the FSM transition diagram in this case. +------+ | |<-------+ +--------->| Down | | | +----| End |<-----+ | | | +------+ | | | |5b 3| ^ | | | | | |7 | | | | v | | | | | +------+ | | | | |PCEMP |<-+ | | | | |Test | |11 | | | | |Resp. |--+ | | | | +------+ | | | | 5a| 3^ | | | | | | | | | | v | | | |12 | +---------+ | | | +-->| |14 | | | | Start/ |----+ | +---------| Compute | | +---------+ | 9| ^ | | | | v |10 | +---------+ | | |13 | |Compute/ |------+ |DeCompute| +---------+ Figure 1: Changing data vector profile PCEMP FSM Choi, Guha et al. Standards Track [Page 15] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 6.5.3 Static data vector profile PCEMP FSM Figure 2 illustrates the FSM transition diagram in this case. +------+ | |<------+ +---------->| Down | | | +-----| End |<----+ | | | +------+ | | | |5b 4| ^ | | | | | |8 | | | | v | | | | | +----------+ | | | | | PCEMPTest| | | | | | Resp. | | | | | +----------+ | | | | 6| 4^ | | | | | | | | | | v | | | |12 | +---------+ | | | +--->| Start/ |14 | | | | Compute |---+ | +----------| | | +---------+ | 9| ^ | | | | v |10 | +---------+ | | |13 | |Compute/ |-----+ |DeCompute| +---------+ Figure 2: Static data vector profile PCEMP FSM Choi, Guha et al. Standards Track [Page 16] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 6.6 Flow Logic of the PCEMP FSM and design considerations This shows the flow logic of the PCEMP FSM and the design considerations on the PCE node Data --> CC and SPC ---> (Network Processor, dynamic data (PCE Domain Processor,:: fitness peer1) Node Processor) function | | v < Test goodness of fit ---> Execute : compare data profile FSM for | static data | > profile ** | v Instantiate PCE unit kernel threads with data driven strategy | | | v Send PCE descriptor ID | | v optimize data driven strategy for path computation | (PCE | peer2) v Data <-- CC and SPC** <--Execute FSM for changing data profile Figure 3: PCEMP FSM implementations on the PCE nodes 7. Analysis of the PCEMP metrics in terms of protocol cost: 7.1 Link Bandwidth In PCEMP, we have shown that the link state synchronizations are done using a data-driven strategy scheduling mechanism which minimizes kernel calls and invokes the computation unit only when there is a significant change in the data profile within the time of goodness of fit. Wastage of link bandwidth by ACKs and soft-state preservation messages are minimized. Synchronization of link state databases reduces to a degeneration of individual link state machines' management in the CCs and SPCs. This fits in well to the case where size of the TE-LSDB increases and there is practically no change in the amount of link bandwidth used. Choi, Guha et al. Standards Track [Page 17] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 7.2 Router memory Memory requirements in PCEMP are a function of the SCM realizations of the CC and SPC. External LSAs comprise the majority of peer advertisements. The PCEMP DS processing application benefits from an architecture consisting of multiple register files in the PCE unit, each conforming to the following properties: 1. Each register file supports a number of multiple read/write ports that is at least equal to the number of states in the IDT sequence. Typical numbers range from 4096 to 65536. 2. The memory access pattern of the register file highly structured. Data is alternatively written in the forward and backward directions. The same applies to the read pattern. There will be 128 read accesses for every written data. 3. In-place storage and single cycle read/write, where data is read during the first half cycle, followed by a write during the second half. The structured access pattern makes it redundant to implement an address decoder that is commonly found in register file and general purpose embedded memory designs of routers. Our architecture that implements the address decode utilizes this functionality in the PCE node. The CPCA algorithm indicates that the size of memory is of order ~ O (N x D x B), where N = Number of states in the IDT, D = Depth of the trace forward/backward path, B = Number of bits in the fixed-point algorithm. The states of the IDT can be drawn from any arbitrary number of permutations of the input data sequence. Typical values of N range from 1024 to 4096 .Values of D are expected to be between 512 and 1024. Bit resolution B is set at 4 or less. CPCA time execution = 0.5 s for N 1024 and D 512 with B 4 A database can thus support 100,000 external LSAs with a router memory block of 512K bytes. This can be extended in the hardware architecture of the PCE unit as per configuration. Choi, Guha et al. Standards Track [Page 18] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 7.3 Router CPU usage As the size of the PCEDA grows, the number of interfaces per router stays bounded. Thus the order of computation is order (n * log (n)), where n is the number of routers in the routing domain. The approach in PCEMP is to achieve parallelism of operations in different protocol engine architectures comprising of solutions in form of machine architectures designed to execute transforms effectively. If a complex transform is executed by a number of multiprocessors in the engine in parallel, then the best speed-up possible is logarithmic in the number of processors. The suggestion is therefore to increase the total throughput in the executing transforms and operations by increasing the number of instructions that can be handled by the protocol state machine at the same time rather than the speed-up of individual instructions. This is what makes the processing of large sequence data vectors so effective with a high degree of parallelism in the context of Path Computing. 7.4 Role of CC and SPC The CC is responsible for handling data vectors and synchronization of different link states. The SPC acts a fast path computation mechanism in case of crossover and faults. This conjunction makes the PCE unit's functioning much more efficient. This has the same implications as the LSA protocol used for peer advertisement and topology discovery. A significant improvement by using PCEMP is that the number of routers that can be attached to a single PCEDA is quite arbitrary. As traffic increases, the SPC eases the stringency of backup path computation and the CC-SPC combination guarantees a disjoint alternate path calculation with the minimum crossover time. This follows from Section 4.1 Choi, Guha et al. Standards Track [Page 19] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 8. Conclusion In summary, we have proposed an algorithm and protocol metrics for an efficient Path Computation model that does away the obvious limitation about the size of the computing hardware system with respect to physical memory requirements. This method utilizes pipelined access by the PCE units to the PCEMP DS by distributing the levels among the multiprocessors in the array of invoked computing logic in the CC and SPC. The objectives achieved in this method, are, firstly, achieving a coarse grained transform engine with a small number of multiprocessors connected in a simple topology of a linear array. The accesses are highly localized within the structure topology. Secondly, performing load balancing among the computing units along with the execution of transforms increases the pipeline interval only by a constant. This helps in automatic buffering and synchronization of individual scalar elements of the input data vector across adjacent PCE peers, which is a big plus for reducing computational complexity and overhead. A number of issues related to the PCEMP DS tree restructuring operations and data redistribution for load balancing thus get resolved in a much simpler and more efficient manner in this architecture, which effectively means that there is greater possibility of increasing the number of scalar points in the input data vector for path computation. The algorithm is generic and can easily be integrated onto existing network processing engines and routers. There might not be physical hardware requirement for PCEMP support, it can be soft configured on the participating PCE peers. 9. Security Considerations The impact of the use of the PCEMP architecture is relatively much secure as the PCEDA are computed and distributed internal to the PCE unit. An increase in inter-domain information flows and the facilitation of inter-domain path establishment through PCEMP does not increase the existing vulnerability to security attacks. It should be remembered that PCEMP works by an invoked logic scheme local to each participating PCE unit, and the protocol invoke is brought into play only when there is a significant change in the data profile within the time of goodness of fit. However, it is expected that the PCE solutions will address security issues mentioned in [Ash] in details using authentication and security techniques. 10. IANA Considerations This document makes no requests for IANA action. Choi, Guha et al. Standards Track [Page 20] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 11. Acknowledgements This work was supported in part by the Korea Science and Engineering Foundation (KOSEF) through the Ministry of Science and Technology (MOST) and the Institute of Information Technology Assessment (IITA) through the Ministry of Information and Communications (MIC), Republic of Korea. 12. Intellectual Property Considerations The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Choi, Guha et al. Standards Track [Page 21] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 13. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC3667] Bradner, S., "IETF Rights in Contributions", BCP 78, RFC 3667, February 2004. [RFC3668] Bradner, S., "Intellectual Property Rights in IETF Technology", BCP 79, RFC 3668, February 2004. 14. Informational References [1] Choi, J.K., et al., "Fast End-to-End Restoration Mechanism with SRLG using Centralized Control", draft-choi-pce-e2e-centralized- -restoration-srlg-00.txt, August 2004 (work in progress) [RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell and J. McManus, "Requirements for Traffic Engineering over MPLS", RFC 2702, September 1999. [RFC3209] Awduche, D., et. al., "Extensions to RSVP for LSP Tunnels", RFC 3209, December 2001. [RFC3473] Berger, L., et. al., "Generalized Multi-Protocol Label Switching (GMPLS) Signaling - Resource ReserVation Protocol-Traffic Engineering (RSVP-TE) Extensions", RFC 3473, January 2003. [INTER-AREA] Le Roux, J., Vasseur, JP, Boyle, J., "Requirements for Support of Inter-Area and Inter-AS MPLS Traffic Engineering", draft-ietf-tewg- interarea-mpls-te-req-00.txt, March 2004 (work in progress). [INTER-AS] Zhang, R., Vasseur, JP., et. al., "MPLS Inter-AS Traffic Engineering requirements", draft-ietf-tewg-interas-mpls-te-req-06.txt, January 2004 (work in progress). [MRN] Papadimitriou, D., et. al., "Generalized MPLS Architecture for Multi-Region Networks,"draft-vigoureux-shiomoto-ccamp-gmpls-mrn-04.txt, February 2004 (work in progress). [Ash] Farrel, A., Vasseur, JP., and Ash, J., "Path Computation Element (PCE) Architecture", draft-ash-pce-architecture-00.txt, September 2004 (work in progress) Choi, Guha et al. Standards Track [Page 22] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 15. Authors' Addresses Jun Kyun Choi Information and Communications University (ICU) 103-6 Munji-Dong, Yuseong-gu, Daejeon, 305-732, Republic of Korea Phone: +82-42-866-6122 Email: jkchoi@icu.ac.kr Dipnarayan Guha Information and Communications University (ICU) 103-6 Munji-Dong, Yuseong-gu, Daejeon, 305-732, Republic of Korea Phone: +82-42-866-6282 Email: dip@icu.ac.kr Jin Ho Hahm Electronics and Telecommunications Research Institute (ETRI) 161 Gajeong-Dong, Yuseong-gu, Daejeon, 305-350, Republic of Korea Phone: +82-42-860-6048 E-mail: jhhahm@etri.re.kr 16. Full Copyright Statement Copyright (C) The Internet Society (2004). All Rights Reserved. This document is subject to the rights, licenses and restrictions contained in BCP 78 and except as set forth therein, the authors retain all their rights. 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 implementation 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. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Choi, Guha et al. Standards Track [Page 23] Internet Draft draft-choi-pce-metric-protocol-00.txt October 2004 co