My other Research Topics
My additional research topics include:
Depending on the context and the domain being studied, my research can be grouped into three main categories: multi-constrained routing with uncertainties in inter-domain networks, routing in optical networks, and resource optimization and protection.
With the growing accessibility of the Internet, the number of applications deployed across networks has increased significantly. Applications such as VoIP, online TV, and video conferencing rely on meeting multiple Quality of Service (QoS) parameters, including latency, error rate, and financial cost. In this context, devising an efficient routing strategy capable of meeting (or optimizing) a set of QoS constraints is crucial to ensure the seamless operation of these applications.
Since October 2009, my research has been dedicated to addressing the NP-hard problem of multi-constrained routing in inter-domain networks. This involves finding paths that optimize or satisfy constraints related to K additive metrics (K>1), such as delay, cost, and bandwidth. The complexity stems not only from the inherent difficulty of multi-constrained routing but also from the decentralized nature of inter-domain networks, where topology and metric weights are local to each domain and not shared globally.
Even when path segments within individual domains meet the constraints, determining an end-to-end path across multiple domains remains computationally challenging due to the lack of shared information. To tackle this, my work focuses on developing probabilistic approaches to select subsets of path segments within domains, maximizing the likelihood of constructing an end-to-end path that satisfies the constraints.
Inter-domain networks, QoS, pre-computed paths, polynomial-time approximation algorithms, complexity analysis, discretization, scalability, uncertainties.
Approximation Algorithm for Bottleneck Link Weight (AABLW)
To minimize connection setup delays, each domain can precompute a set of path segments connecting entry nodes to exit nodes while meeting various constraint sets. To streamline the computation process, the solution search interval is often restricted to [Binf, Bsup], where Binf represents the lower bound and Bsup represents the upper bound of optimal solutions. One of the most effective pairs (Binf, Bsup) for reducing this interval is determined by the bottleneck link (congestion link). For example, when calculating an optimal path π that satisfies the constraints of system A, the bottleneck link e enables narrowing the solution search interval to [Binf(e), Bsup(e)], where Bsup(e) equals H multiplied by Binf(e), and H corresponds to the maximum path length.
This result is particularly beneficial when utilizing Fully Polynomial Time Approximation Schemes (FPTAS), as the computational complexity remains unchanged when substituting [Binf, Bsup] with [Bsup(e), Binf(e)].
Hybrid Scale-Based Approximation Algorithm (HSAA) for Enhancing Multi-Constrained Routing
To enable the pre-computation of paths that satisfy and/or optimize various QoS parameters, we proposed the HSAA algorithm. For any constraint value D in system (A), our algorithm can determine a path that is ε-close to optimal.
Our HSAA algorithm combines three concepts: (1) discretization, (2) scaling, and (3) path computation. The first concept reduces complexity by discretizing the real interval of path weights [0, Bsup.(1+ε)] through the selection of r samples (s0, s1, ..., sr-1). At each step of path construction (each time a link is added to a path), the weight of the i-th metric of the path is approximated by the sample that is greater than and closest to it. The values of the different samples are determined by the following algorithm:
The second concept is not necessary for the proper functioning of the HSAA algorithm. It simply avoids divisions at each step of weight approximation by its corresponding sample. The third concept involves applying an exact multi-constrained path computation algorithm by substituting real path weights with their corresponding samples.
The accuracy of the HSAA algorithm is formally proven in this paper. Among the significant results obtained in this context, I highlight:
To meet increasing user demands for bandwidth, optical technology is not only chosen as a solution for core networks but also for many access networks (e.g., Numericable, Free). To maximize the use of this technology, wavelength division multiplexing (WDM) is often adopted. Due to optical constraints and wavelength continuity requirements, resource allocation (particularly wavelengths) and routing in optical networks are often challenging.
During my year as an ATER researcher, I focused on these networks to develop new routing algorithms (point-to-multipoint and multipoint-to-point) aimed at optimizing resource usage (reducing stress and costs) while improving quality of service (minimizing energy consumption to avoid signal distortion).
Optical networks, path computation, point-to-multipoint and multipoint-to-point communications, routing, wavelength allocation.
Stress-Minimizing Multipoint-to-Point Routing (k-Bound Edge Disjoint Path Routing or kBEDPR)
To minimize stress while ensuring routing at worst k times farther from optimality (relative to an additive metric such as cost), we proposed the kBEDPR algorithm. This approach combines different trees composed of disjoint paths at worst k times the optimum to reduce the number of allocated wavelengths. The kBEDPR algorithm is described in detail in this article.
The rapid recovery from failures is increasingly desired with the explosion of real-time applications deployed across networks (e.g., VoIP, TV streaming, online gaming). Various fault-tolerance techniques have been developed to prevent or reduce downtime caused by failures. These techniques aim to determine backup paths capable of receiving and rerouting traffic affected by failures. They can be classified into two categories: restoration (reactive protection) and protection (proactive protection).
Restoration:
With restoration techniques, no backup path computation is performed before a failure occurs. The recovery process triggered after a failure involves determining and configuring new paths bypassing faulty components to route traffic affected by the failure. Restoration has advantages such as reduced maintenance costs and adaptability to topology changes but does not guarantee resource availability after a failure and often has high recovery delays unacceptable for many network applications.
Protection:
Protection techniques significantly reduce recovery delays because backup paths are precomputed and often preconfigured before failures occur. To handle a given failure effectively, traffic affected by the failure can simply be switched to precomputed backup paths.
Local and online communication protection against failures; bandwidth optimization through efficient resource sharing among communications; routing and graphs; SRLG (Shared Risk Link Group); distributed computations; unicast and multicast.
During my thesis work, we developed and proposed various mechanisms enabling distributed computation of local backup paths (point-to-point and point-to-multipoint) within an MPLS-based communication infrastructure. Our proposals have the advantage of being easy to deploy (requiring only lightweight extensions to routing or signaling protocols) while reducing the volume of information transmitted within the network for enabling placement of backup paths. We also proposed a multicast communication protection method and studied the impact of different bandwidth-sharing strategies on performance metrics for placing multicast backup paths.
Our main contributions, most of which have been published in international conferences and journals, are summarized as follows:
TDRA Algorithm
TDRA maximizes bandwidth sharing on links while reducing the amount of information transmitted within the network. To achieve this goal, TDRA performs targeted and optimized distribution (using Kou-Markowsky-Berman trees for distributing required information) for computing distributed backup paths. Implementing this algorithm requires only lightweight extensions to signaling protocols (and minimal extensions to routing protocols).
DBSH Heuristic
DBSH enables the placement of backup paths by disseminating only partial and aggregated information within the network. Using this heuristic, all backup paths protecting against the failure of a given node (or a specific unidirectional link) are computed directly on the node itself (or on the outgoing node of the link). This heuristic significantly reduces the size of information disseminated in the network and is easy to deploy as it requires only minor extensions to routing and signaling protocols.
PLRH Heuristic
PLRH allows for the placement of backup paths by disseminating only partial and aggregated information within the network. With this heuristic, all computations for backup paths are performed by the head routers of these paths. This heuristic has the advantages of being symmetric (all computation entities have access to the same information) and easy to deploy (requiring only very minimal extensions to routing protocols).
Exploiting SRLG Structures for Efficient Backup Path Placement
To improve protection rates and increase resource availability, we proposed leveraging SRLG structures during backup path computation. Observing that certain active backup paths after an SRLG failure cannot carry traffic, we suggested restricting the set of risks protected by a backup path to those whose failure would result in traffic reception.
Multicast Protection Using Dual Forest
To protect multicast communications, we proposed using a backup structure formed by a forest connecting the leaf nodes of the multicast tree. This protection method has the advantage of reducing the size of the backup structure, thereby improving resource availability both before and after a failure.
Impact of Bandwidth Sharing Strategies on Backup Path Placement Performance
We studied how different bandwidth-sharing strategies affect the performance of backup path placement mechanisms. Two strategies were compared: (1) bandwidth sharing among backup paths only, and (2) bandwidth sharing between primary and backup paths. In our study, we employed a shortest-path algorithm based on a static metric (i.e., a fixed metric independent of traffic). Through analytical proofs and simulations, we demonstrated that extending resource sharing to include bandwidth sharing between primary and backup paths results in only a slight reduction in rejection rates for backup path placement requests. In other words, we showed that the number of satisfied backup path placement requests is bounded and depends more on bandwidth sharing among backup paths; the impact of bandwidth sharing between primary and backup paths on reducing blocking rates for backup path placement requests is limited and bounded.
For my publications, click here.