Research On MPLS Network Topology Aggregation Algorithm

MPLS is an integrated transmission technology that combines the switching in layer 2 and routing in layer 3. At the ingress site of MPLS network, the Label Edge Router (LER) maps IP packets into different Forwarding Equivalence Classes (FECs). Then the FEC to which the packet is assigned is encoded as a short fixed length value known as a "label". The label acts as a shim header that is inserted between the network layer header and the data link layer header. The label will be the only index of the packet which is switched along the Label Switching Path (LSP) and forwarded to its next hop. Then a new label replaces the old one and the packet will be sent out till the egress router of the LSP. The characteristics of the label switching of MPLS speed up the switching rate, as well as it faces the problem of scalability. Several difficulties are itemized as follows. 1. MPLS network forwards packets using LSPs. LSP is a logical point-to-point connection which is set up based on the physical links. So, it needs O(n2) LSPs to make point-to-point connections for all the n destinations in the MPLS network. As the network grows, how to realize the LSP aggregation function is an obstacle when implementing MPLS label switching in a scalable manner. 2. FECs match to different class of services and quality of services. For different traffic flows, even they have the same source and destination addresses, they may need different FECs to classify; accordingly, they need the same quantities of labels as the FECS to identify. As the label length is only 20 bits, when the scale of network enlarges, MPLS will face to a severe problem of lack of labels. 3. Unlike the unicast, whose address aggregation can be coupled with hierarchical address allocation, a multicast address corresponds to a logical group and does not convey any information on the location of its members which means the multicast traffics are very difficult to aggregate. On the other hand, the granularities for the multicast stream are much finer than the unicast and accordingly will consume more labels. So, how to realize the aggregation/merging function is an obstacle when implementing MPLS multicast in a scalable manner. To solve the scalability problems addressed above, focusing on the MPLS network topology, a topology aggregation scheme of the physical MPLS network is investigated. The aggregation scheme reduces the amount of the egress nodes when establishing LSPs. As the result, the amount of the LSPs in MPLS networks is reduced accordingly. Further more, the amount of LSRs that can participate in switching is reduced also to decrease the consumption of the labels. After such aggregation scheme, MPLS topology is simplified. The MPLS multicast protocol is introduced based on the topology aggregation scheme. So it can reduce the amount of multicast trees that the MPLS network sets up, accordingly, the labels will be saved. This scheme can not only satisfy the scalability of MPLS network, but also has higher adaptability to different applications. The works in this thesis has been supported by the National Science Foundation of China "Investigation of Wireless Multimedia Techniques based on Multimedia Transmission Property"(No.60202005) Australian Research Council Foundation "Interactive video-on-demand for e-Learning"(No.LX0240468), and also supported by the project of "Design and Development of Hi-speed Broadband Router-AVIA"that cooperated with COMBRIO Inc. The research of this thesis includes: 1. The characteristics and topology aggregation algorithm of MPLS network edge nodes. A method of constructing minimum weighted dominating set based on the constraint of bandwidth or delay is proposed. This method can be used for aggregating the MPLS edge sub-network topology. A parallel approximation algorithm with O(n) computation complexity and O(Δn) message complexity was designed. This algorithm can generate a weighted dominating set based on single constraint object. It considers the bandwidth between the dominator and dominates. Using the weight, the dominating set has the optimal weighted feature and can satisfy the demands for certain constraints. 2. The aggregation algorithm and its performance of MPLS core network. AFixed-Edge Connected Dominating Set (FECDS) algorithm is designed to aggregate the MPLS core sub-network topology. This algorithm considers the aggregated topology of MPLS edge sub-network. Running the algorithm can generate a connected dominating set of the core sub-network without ignoring the characteristics of the edge sub-network. The resulted whole aggregated topology of MPLS network is a connected entity while keeping the aggregating features of the edge nodes and core node respectively. 3. MPLS overall topology aggregation algorithm. Based on the topology algorithms above, the whole MPLS aggregation strategy is discussed. And the research is focus on the multicast algorithm in aggregated MPLS topology. In order to improve the scalability and reduce the label consumption of MPLS multicast, an Aggregated Topology Hierarchical Multicast (ATHM) protocol is proposed. It constructs the multicast trees based on the aggregation topology achieved in former chapters. The ATHM protocol divides the MPLS area into different sub-areas to form 2-layer hierarchical multicast area according to the dominators and dominatees in the generated aggregated topology. At the same time, the label stack is used to save the label space. 4. The implementation of aggregatable MPLS model in high-speed broadband router based on embedded Linux. Cooperating with the project "Design and Development of Hi-speed Broadband Router-AVIA", the MPLS topology aggregation scheme modules are designed and implemented in Linux platform.