Internet Engineering Task Force J.P.Wang Internet-Draft Y.P.Zhu Intended status: Informational U.S.T.B Expires: June 21, 2011 December 21, 2010 A Novel Inter-domain Routing Algorithm in Distributed Multi-Domain Optical Network draft-jpwang-ccamp-alg-dis-mul-00 Abstract The routing problem of multi-domain optical network includes intra-domain routing and inter-domain routing.Although the intra-domain routing algorithm has been well studied, the inter-domain routing computation in distributed multi-domain optical network still presents many problems and needs further research. Compared to single domain, the routing computation in multi-domain network needs topology abstraction.In this paper, we first have full-mesh topology abstraction improved, and then present a novel algorithm to calculate the inter-domain routing. By computing the shortest path based on the available wavelengths, the proposed algorithm improves the performance of routing provision. Simulation results show that the new algorithm achieves the satisfactory blocking performance. Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. 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. This Internet-Draft will expire on June 21, 2011. Wang&Zhu Expires - June 21, 2011 [Page 1] Internet-Draft Inter-domain routing algorithm December 2010 Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. Wang&Zhu Expires - June 21, 2011 [Page 2] Internet-Draft Inter-domain routing algorithm December 2010 Table of Contents 1. Introduction...................................................4 2. Topology abstraction...........................................4 2.1 The improved full-mesh abstraction.........................5 3. The novel inter-domain routing algorithm.......................6 3.1 The step of the new algorithm.................................7 4. Analysis of the new algorithm..................................7 5. IANA Considerations............................................8 6. Security Considerations........................................8 7. Acknowledgments................................................8 Author's Addresses................................................8 Wang&Zhu Expires - June 21, 2011 [Page 3] Internet-Draft Inter-domain routing algorithm December 2010 1. Introduction With the development of traditional optical network, the distributed multi-domain optical network or ASON(automatically switched optical network)is becoming the best choice of next generation optical network. Routing issue is a core technology of the optical network, so routing algorithm is a focus of current research. In the distributed multi-domain optical network, routing problem includes intra-domain routing and inter-domain routing. Inter-domain routing problem is divided into two sub-problems: topology abstraction and inter-domain routing algorithm. Topology abstraction is to summarize intra-domain link state information and intra-domain physical topology is transformed into virtual topology, while inter-domain routing algorithm is to calculate a path spanning multiple domains. The specific topology of each domain is invisible to other domains. Nevertheless, the topology abstraction information can be exchanged among different domains, so topology abstraction is used to hide internal state from outside users. When the path is selected, we should allocate the same wavelength for all the links in the path, which is considered as wavelength continuity constraint. Previous works have focused on the inter-domain routing problem, but they all consider shortest path without available wavelengths. Reference defines a hierarchical approach to routing an end-to-end connection that is called Multi-domain Shortest Path First(MSPF), however, available wavelength is not considered here. Meanwhile, in Reference, full-mesh topology abstraction scheme is utilized and the K-shortest path algorithm with no consideration of wavelength is adopted to compute a path. It is evident that business requests spanning several domains block frequently due to wavelength continuity constraint, so the previous schemes are not favorable in multi-domain optical network. More importantly, the improve and extension of these schemes can be achieved by combining the shortest path algorithm with the number of idle wavelengths. It focus on the routing algorithm computing the shortest path based on the available wavelengths. 1.1. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. This document uses terms from [RFC3261]. 2. Topology abstraction Wang&Zhu Expires - June 21, 2011 [Page 4] Internet-Draft Inter-domain routing algorithm December 2010 In multi-domain optical network, topology abstraction summarizes intra-domain link state information and intra-domain physical topology is transformed into virtual topology through topology abstraction. Topology abstraction serves for inter-domain rooting algorithm, so as more topology information as possible is good for rooting computation, but if topology abstraction scheme supply too much information, the abstraction scheme algorithm will be more complicate and confidentiality will be destroyed. In order to reach a balance among them, we should research the topology abstraction scheme depthly. There are three basic topology abstraction schemes [6]: simple node abstraction, full-mesh abstraction and star abstraction. Simple node abstraction scheme is the simplest abstraction scheme, which condenses a domain into a single node without any other information. In full-mesh scheme, the whole domain is abstracted into an auxiliary graph, with all of the border nodes reserved. The direct links between any two border nodes are remain the same, furthermore, virtual links are established to connect any two border nodes having no direct link in practical topology. Compared to simple node abstraction, the full-mesh scheme can provide more information, which is favorable for computing path but is at the cost of excessive routing load. In order to obtain the trade-off between both the above schemes, star abstraction scheme is also adopted. In the star scheme, all of the border nodes are reserved and a new virtual node is introduced into the new topology graph, besides, there is only a simple virtual link between every border node and the virtual node so as to reduce the routing load. 2.1 The improved full-mesh abstraction First, we propose G(V,Q)denotes the physical topology graph of an domain, and V is the set of all nodes, besides, Q is the set of all links. Consider that the number of border nodes is N, and G(V,Q)is changed into H(V1,Q1) through full-mesh topology abstraction, so V1 is the set of border nodes in the topology abstraction graph and there are N members in collection of V1. Q1 is the set of links between border nodes which include physical links and virtual links. L is defined to mark a link in abstraction graph. For any link L in the topology abstraction graph, we define M(L) is the cost of traversing link L, and W(L) represents the number of idle wavelengths of link L. If two border nodes V1 and V2 in one domain have direct link in physical topology graph, the cost of traversing between them is 1, that is to say, the value of M(L) of the link connecting node V1 and node V2 is 1. In summary, we define that the cost of all of the physical links in abstraction graph is 1. The value of W(L)is the same as the number of link L connecting V1 and V2. If two border nodes V1 Wang&Zhu Expires - June 21, 2011 [Page 5] Internet-Draft Inter-domain routing algorithm December 2010 and V2 do not have direct link, we should establish virtual link to connect them in topology abstraction graph. In virtual link, M(L)is determined by the shortest path with available wavelength between the two given nodes. First, we adopt K shortest path algorithm to compute all of the paths connecting V1 and V2, and then we search for the shortest path, and decide if there is any idle wavelength in the shortest path. If there is any available wavelength in the shortest path, the value of M(L) is the hops of the shortest path and the value of W(L) is in line with that of shortest path, or else we search for the second shortest path and decide whether there is any idle wavelength in the second shortest path. We search in accordance with above until we find the shortest path with available wavelength. The value of M(L) equals the hops of the selected path and the value of W(L) is determined by the number of the idle wavelengths of the selected path. 3. The novel inter-domain routing algorithm In multi-domain optical network, routing problem is divided into two sub-problems: intra-domain routing and inter-domain routing. In order to assign a path for business requests which span different domains, we have to first compute a inter-domain loose route, and then compute intra-domain rooting for every domain which the loose route pass through. Previous works have focused on the inter-domain routing algorithm, but they all base on the shortest path algorithm. We know that in multi-domain network the business request often block because there is not any available wavelength to be assigned for the request, so it is unreasonable to only consider the length of path without idle wavelength in selecting loose route, in response to which, we can combine the length of path with the number of available wavelength when choosing loose route. In this draft, we first adopt improved full-mesh abstraction to change the practical topology into a topology abstraction graph, and then compute a loose route in the topology abstraction graph through the novel inter-domain routing algorithm. In order to select a better inter-domain routing, we use a new algorithm to compute a path between source and destination domain border nodes. Suppose L is a link between any two nodes in topology abstraction graph, P is a path from source domain egress node to destination domain ingress node, and K is the collection of paths which is computed by K shortest path algorithm. In addition, O represents the initial number of wavelength in each link. Note that SUM is a fixed path cost, with the value computed by the sum of all link cost M(L) in one path. Wang&Zhu Expires - June 21, 2011 [Page 6] Internet-Draft Inter-domain routing algorithm December 2010 3.1 The step of the new algorithm The novel inter-domain routing algorithm referred processes are just as the followed steps: Step 1: Initiate the fixed weight M(L)of every link and the number of available wavelength W(L)in topology graph. Step 2: Decide the incoming connection request. If it is a link connection request, continue to the next step. But if it is link rejection request, transfer to the step 10. Step 3: Adopt K shortest path algorithm to compute K paths and compute the figure of SUM in every path. Step 4: Compute the max number of available wavelength MAX in every path, which equals to the minimum number of available wavelength of all the links. Step 5: Suppose the number of wavelength of every link in initial state is R. Step 6: Define C(P)is the total cost of a path. C(P)=L+R/MAX. If MAX equals to zero, there is not any available wavelength in the path. This implies that the business request will block in this path because of having no idle wavelength, as a result, we set the value of c(p) is infinite when MAX equals to zero. Step 7: Compute the value of C(P) of every path P. Step 8: Choose the path whose C(P)is the smallest and assign wavelength for the selected optical path. If wavelength is unsuccessful, try the other path whose C(P)is the smallest in the remaining paths until we can assign wavelength for the path. Step 9: Update the value of W(L) and continue to step 2. Step 10: Remove the optical path and the occupied wavelength resources, then update the figure of W(L) and turn to step 2. 4. Analysis of the new algorithm In the new algorithm, MAX is the max number of available wavelength in a path. That is to say, the number of available wavelength in path P is at most MAX or MAX is the number of idle wavelength on their most congested link in a path. As expected, when L and R is fixed, MAX is reversely proportional to C(P). In multi-domain network, if there is not identical idle wavelength, the business request will block because of wavelength continuity constraints. The business requests are more easily to block because of continuity constraints in inter-domain than in intra-domain. The path we select according to the above algorithm is an optimized one, and it has more chance to gain available wavelengths. The new rooting algorithm based on the improved full-mesh topology abstraction scheme. Compared to the shortest path algorithm, the novel scheme combines the shortest path with the number of available wavelength, which is confirmed to have improved the inter-domain blocking performance. As a result, the blocking probability can be reduced. Wang&Zhu Expires - June 21, 2011 [Page 7] Internet-Draft Inter-domain routing algorithm December 2010 5. IANA Considerations This document does not have any implications for IANA. 6. Security Considerations The presence of the Reason header in a response does not affect the treatment of the response. Including such a header by an untrusted entity could adulterate the reactions of the originating entities. E.G. sending back a cause value "87" can cause an announcement within the PSTN/ISDN saying that the call was rejected due to the Closed User Group service. Therefore it is RECOMMENDED to include the Reason header information in Responses only by trusted entities as it is described within [RFC3325][7]. 7. Acknowledgments The research was supported by National High Technology Research and Development Program of P. R. China (No.2009AA01Z217) and National Natural Science Foundation Project of P. R. China(NO.60872047). 8. Normal references [RFC3261] Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M., and E. Schooler, "SIP: Session Initiation Protocol", RFC 3261, June 2002. [RFC4271] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway Protocol 4 (BGP-4)", RFC 4271, January 2006. [RFC4724] Sangli, S., Chen, E., Fernando, R., Scudder, J., and Y. Rekhter, "Graceful Restart Mechanism for BGP", RFC 4724, January 2007. [RFC3325] Jennings, C., Peterson, J., and M. Watson, "Private Extensions to the Session Initiation Protocol (SIP) for Asserted Identity within Trusted Networks", RFC 3325, November 2002. Author's Addresses Jianping Wang University of Science and Technology Beijing NO.30 XueYuan Road, HaiDian, Beijing 100083 P.R China Email: zhuyanping_06@163.com Wang&Zhu Expires - June 21, 2011 [Page 8] Internet-Draft Inter-domain routing algorithm December 2010 ag Internet-Draft Inter-domain routing algorithm April 2010