The rapid expansion of IoT devices and their real-time applications have driven a growing need for edge computing. To meet this need, efficient and secure solutions are required for running such applications on resource-constrained devices with limited power, CPU, and memory. Unikernel, with its minimalistic design and application-specific approach, offers a promising alternative to traditional virtualization and container technologies in these environments. The existing research does not thoroughly examine the feasibility of using unikernel for edge computing. This paper investigates the potential of unikernel for ARM-powered edge computing by evaluating the performance and efficiency of three prominent unikernel systems such as OSv, Nanos, and Unikraft against Docker container. We experiment with real-world edge computing applications and utilize key metrics such as boot time, execution time, memory usage, CPU overhead, and network performance to determine how unikernel performs under the constraints of edge devices. Our findings reveal the potential advantages of unikernel in terms of reduced resource consumption and faster startup times while highlighting areas where they may need further optimization for edge deployment. This study provides valuable insights for researchers and practitioners considering unikernel as a lightweight, efficient solution for edge computing on ARM architectures.

Container orchestration provides the tools necessary to manage the complexities of edge computing. They ensure efficient, reliable, secure deployment and operation of containerized applications. The orchestrators are also pivotal in influencing the quality and cost-efficiency of service deployment by managing essential tasks like container provisioning, scheduling, scaling, and networking. Edge computing environments are resource-constrained, with limited CPU, memory, and network bandwidth compared to traditional cloud environments. Benchmarking helps identify which container orchestration frameworks perform best under these constraints, ensuring optimal resource utilization and performance. Therefore, a thorough benchmarking of these frameworks is crucial. Despite their importance, there is limited work on benchmarking container orchestration in real-world edge-computing scenarios. This paper introduces a systematic approach that facilitates benchmarking container orchestrators using real-world applications. We benchmark Docker Swarm, K3s, KubeEdge, and Nomad orchestrators using computer vision and data science applications. We designed an evaluation framework to assess container orchestration tools. The evaluation framework includes container provisioning time, receiving time, processing time, resource utilization, and throughput metrics. Additionally, we explore how various container orchestrations optimize resource utilization and compare their efficiency on ARM-based edge devices. The benchmark results indicate that the Nomad orchestrator excels in terms of lower latency and optimal resource utilization. KubeEdge and K3s demonstrate faster provisioning times, whereas Docker Swarm experiences communication overhead between manager and worker nodes.

Beacon evaluates whether an intrinsically interpretable rule learner, Information Lattice Learning (ILL) [1], can offer practical advantages for edge AIoT landuse mapping when trained on the same, leakage-safe, physically grounded features as a tuned Random Forest (RF) [2]. Using stratified learning-curve experiments (10–125 samples per class; five seeds; fivefold CV) across five algorithmic families, XGBoost and Random Forest achieved top performance while ILL produced compact, ecologically coherent rulebooks at a 15–25 percentage-point interpretability tax suitable for audit and expert scrutiny. We summarize the end-to-end pipeline, report statistically rigorous results (Wilson CIs, paired tests with Bonferroni control, Cohen's d), and discuss deployment patterns that pair RF's accuracy with ILL's transparency for on-device audit and rapid expert contestability. Our conclusions are bounded by the Costa Rica domain, fixed hyperparameters, and a single ILL implementation; ongoing work targets expert rule validation, sensitivity analyses, and multitemporal/multimodal inputs. These claims and numbers are drawn from the full Beacon study.

Container-based applications are increasingly favored for their efficiency in software development, deployment, and operation across various platforms. However, the growing number of security and privacy attacks poses significant concerns. Exploiting vulnerabilities within containers may compromise the entire host system, as both share the same operating system. Unfortunately, container defense mechanisms are inadequate due to the ever-evolving and dynamic attack landscape.In this paper, we systematize container attacks and defense mechanisms. We systematically analyze the effectiveness of (i) static container scanning tools proposed for vulnerability detection and reveal their shortcomings, as well as (ii) existing run-time anomaly-based detection approaches. We then establish an evaluation framework and comprehensively re-evaluate cutting-edge anomaly detection techniques tailored for containers using an extensive dataset of 51 real-world vulnerabilities. We emphasize that existing defenses are ineffective in protecting containers against state-of-the-art attacks. While anomaly detection-based approaches show potential in addressing dynamic attack landscapes, their high false positive rates and limited training data hinder practicality. Therefore, our work highlights the urgent need for further research to enhance the security of container-based applications.

Containers provide a better performance, faster deployment than virtual machines and provide near-native performance, with isolation and security drawbacks. Although the security of containers for the Intel architecture has been investigated in more detail, there is limited work on the security of containers for the ARM architecture. In this paper, we address this gap in research and focus on the security of containers designed for the ARM architecture, which is heavily used in IoT devices. Edge computing offers many advantages, including reduced latency and resource requirements at the cloud because data can be processed at the edge before it is sent to the cloud. Using containers at the edge nodes of IoT-Edge-Cloud systems can enhance such advantages at the cost of increasing security vulnerabilities in such systems. Therefore, it is essential to investigate the security of containers designed for the ARM architecture. Accordingly, we obtained official ARM images from DockerHub and used various security tools to scan these ARM images. We found that 72% of all the vulnerabilities show varying severity levels and each tool seems to work best for particular base images. We investigated how each tool detects sub-packages and achieves a different hit ratio while none of them alone can detect at least 80% of all the vulnerabilities. In addition, we also investigated how the Docker images and their vulnerability landscape change over a period of six months by running the scanning tools twice. Finally, we also conducted a dynamic analysis of some of the images on the Raspberry Pi and study their effects. We believe this paper will facilitate the use of ARM containers at the ARM-based edge nodes by addressing security issues.

Software Defined Networking (SDN) has emerged as a promising paradigm with the key idea of separating control and data planes. However, this separation causes various scalability issues (e.g., increased response time, overhead on the controller and core SDN switches) in Wide Area Networks (WANs). While addressing such scalability issues, it is important to maintain the performance gains of the Reactive SDN and also to handle link failures. To jointly address scalability, performance, and link failure issues, we propose a newSource-Path Routing Model (SPRM)by combining the best of proactive and reactive approaches along with a simple packet programming mechanism. Specifically, SPRM pre-calculates and pre-installs multiple paths (proactive part) but then selects/assigns one of these paths for an incoming flow based on the available dynamic network state information (NSI) (reactive part). We also utilize SPRM to effectively cope with the link failures by using multiple paths as backup to each other. Our simulation results show that SPRM performs much better than the pure Reactive SDN in terms of path establishment delay and flow table size while (a) maintaining its performance gains in terms of link utilization and load balancing, and (b) quickly recovering from a link failure without causing extra memory overhead on the data plane.

There are several routing algorithms that can be used in the context of Software Defined Networking (SDN), where a logically centralized controller obtains the global view of the network and network state information, makes the routing decisions, and installs them to the switches in the selected paths. Comparing the performance of the existing routing algorithms under realistic simulation scenarios and understanding the factors that impact their performance are very important for their adaption in practice. Accordingly, we implemented several existing routing algorithms using RYU SDN controller and evaluated their performance on Mininet emulator. We considered three categories of Routing Algorithms with Static Link Cost (RA-SLC), Dynamic Link Cost (RA-DLC), and Dynamic Link cost with Minimum Interference (RA-DLCMI) under both the idealistic case assuming the availability of accurate network state information (NSI) and the practical case where the NSI is collected periodically and has some inaccuracy. Our experimental results showed that both RA-DLC and RA-DLCMI outperformed RA-SLC in terms of throughput and the number of accepted flows while there was no significant difference between RA-DLC and RA-DLCMI. We also observed that periodic collections caused inaccuracies in NSI and negatively affected the performance of all algorithms.

Efficient routing necessitates the underlying path selection algorithms to find a path that can satisfy certain Quality-of-Service (QoS) requirements of a given flow while maximizing throughput and minimizing maximum link-load. In the case of routing multiple flows at the same time, finding such multiple paths even with just the bandwidth constraint is a well-known NP-hard problem and has been widely studied in the literature as the Unsplittable Flow Problem (UFP). Unfortunately, the existing approximation and heuristic solutions suffer from excessive computation time or low performance in maximizing throughput and minimizing maximum link-load. In this paper, we propose a new effective heuristic solution to find multiple paths that can satisfy bandwidth requirements of a given set of unsplittable flows while providing better throughput and load balancing in Software Defined Networks (SDN). We demonstrate the efficiency of our heuristic using simulations.

Routing in Software Defined Networking (SDN) requires the SDN controllers to obtain the current dynamic network state information (NSI) as accurately as possible while reducing protocol overhead. To balance the trade-offs between the accuracy and protocol overhead, the SDN controllers usually implement a periodic NSI collection design where they obtain the dynamic link-state information from each switch at a predetermined rate. To improve the accuracy of NSI while minimizing the protocol overhead and providing better load balancing among multi-controllers, we propose a link-prioritized NSI collection design and compare it against the existing periodic NSI collection design. Using a dynamic routing algorithm on RYU SDN controller and the Mininet emulator, we compare our design against existing periodic NSI collection design. We observe that the proposed link-prioritized NSI collection design significantly reduces the protocol overhead without sacrificing the routing performance in terms of throughput or accepted bandwidth request. Moreover, our design results in better packet loss because it can quickly and accurately obtain NSI.

This paper presents the design and evaluation of a novel project designed to facilitate the learning of memory management concepts and interactions between different components. This project removes the complexity of a full or specific operating system by implementing memory management inside the user space. Evaluation results show that the mean exam scores improved by about 29% to 34%. On average, the total code size is less than 300 lines and time spent working on this project is under 17 hours. Therefore, this project is beneficial in helping students learn memory management while maintaining a reasonable project workload.

Mobility within Wireless Sensor Networks (WSNs) has been widely considered for data collection tasks, where mobile robots physically collect the data from the sensors and return to the base station. Although this approach has proven to be useful in prolonging the lifetime of these networks, it cannot meet the requirements of real-time data collection tasks. For such tasks, we need to utilize mobile robots to create a connected path from the base station to the event, as well as use in-network forwarding through that path. This will provide a longer lifetime while addressing efficiency and scalability issues because mobile robots have a larger and renewable energy reserve, a longer transmission range, and capacity. One of the fundamental problems is how to coordinate robots to establish a connected path from the event location to the base station. We consider this fundamental problem with two objectives, namely minimizing distance traveled by the robots and minimizing hop count (the number of robots used on paths) under the constraints of satisfying the path and/or network connectivity. After mathematically formulating the underlying problems and discussing their NP-hardness, we propose various heuristic solutions. We then demonstrate the efficacy of our proposed solutions through extensive simulations.

Malaria remains one of the most important public health concerns worldwide. It causes nearly half a million deaths every year, and about 40% of the world's population lives in the endemic regions of malaria. A major hurdle in antimalarial development is our limited understanding of the dynamic cellular networks in the malaria parasite. In this study, by coupling RNA-Seq analysis and network mining using a PageRank-based algorithm, we investigated the temporal-specific expression of parasite genes during the 48-hour red blood cycle, and identified genes that may play influential roles in parasite development and invasion. The just-in-time mechanism for gene expression may contribute to a dynamic yet effective adaptive strategy of the malaria parasite.

Mobile robots have been used to collect data in the network in order to reduce the energy consumed when forwarding data. In order to be energy efficient, mobile robots should be deployed and controlled in such a way as to minimize travel distance. To do this, we examined multiple deployment and movement policies and their effects on the performance of a network. We tested three different deployment schemes and analyzed the results. We also analyzed the expected distance to each event to discover what, if any, effects the initial deployment has on that metric and in turn compared this to our results. We then tested three different collection methods and analyzed their performance. Next, we added service times to our model and lastly we changed the distribution of events to examine how these changes affected the network performance. Through our extensive simulations and mathematical analysis, we found a random deployment to be the most effective deployment policy with respect to computation time and network performance. Our proposed location prediction policy was also able to improve network performance, even over the collect and stay policy as shown through our simulations.

Numerous algorithms have been proposed for the well-known multi-constrained shortest path (MCSP) problem, but very few have good practical performance in case of two or more constraints. In this paper, we propose a new Lagrangian relaxation algorithm to solve a generalized version of the MCSP problem where we search for multiple shortest paths subject to multiple constraints. As in some related work, our algorithm first identifies the lower and upper bounds, and then tries to close the gap with a path enumeration procedure. However, our algorithm is based on the recognition that the Lagrange multipliers found by existing methods usually do not give the best search direction for minimizing path enumerations even though they can provide near-optimized lower bounds. We provide a solution to meet both of these goals, and incorporate feasibility checks into a state-of-the-art K-shortest paths algorithm to further reduce path enumerations. Through experiments on various networks including the most challenging benchmark instances, we show that our algorithm can solve a significantly larger number of instances to optimality with less computational cost, often by one or two orders of magnitude, when compared with the best known algorithm in the literature.

Malaria is one of the most deadly infectious diseases in the world. The malaria burden is characterized by 207 million cases and over 627,000 deaths annually. The consistent morbidity and mortality underscore an urgent need for the development of next-generation antimalarials. In this paper, we propose a network mining approach to uncover the protein-protein associations that are implicated in important cellular processes including DNA repair, genome integrity, transcriptional regulation, and pathogenesis.

Mobility within Wireless Sensor Networks (WSNs) has proven to be quite useful in prolonging the lifetime of these networks. This mobility requires intelligent control of the robots in order to efficiently complete tasks within the network. If the tasks required of the network need to send audio-video data back to the base station, then we need to maintain some connectivity with the base station in order to efficiently use the energy within the network. After mathematically formulating our problem, we propose three algorithms to solve these problems and run extensive simulations to test these algorithms. We were able to optimally solve the minimum hop problem and compare that to the heuristics for the minimum distance problems.

Due to the importance of Frequent Pattern Mining (FPM) in bioinformatics, web mining, social networks and so on, researchers have been paying significant attention to FPM and its various forms. In this study, we introduce a new form that we call super-sequence pattern mining. In contrast to frequent sub-sequence pattern mining studied significantly in the literature, frequent super-sequence mining requires to identify super-sequences that may contain sequential parts from different sequences and that have the total support larger than a given threshold. In essence, finding frequent super-sequence patterns turns out to be related to the well-known NP-hard longest path problem in graphs. Accordingly, we transform a given sequential dataset into a sequence graph and formulate the problem as k-hop longest path problem. We then propose a heuristic algorithm using dynamic programming techniques. The running time of our solution is depending on the number of different items in the sequence set but not on the size of the dataset. Through experiments, we demonstrate the effectiveness of the proposed solution. We also illustrate its use on an actual web log dataset and find out some interesting facts based on the identified frequent super-sequences on the web log dataset.

Wireless Multimedia Sensor Networks are a budding topic for researchers which could vastly improve many applications, such as border monitoring networks. The increased amount of data leads to greater issues with energy consumption and decreased network lifetimes. To mitigate these problems, the use of mobile sinks to travel through the network and collect the generated data has been suggested and studied. Consideration has not been given to the abilities of these mobile sinks, such as their ability to turn. We develop an algorithm to create a smooth path, which will allow the use of faster, more turn-constrained mobile sinks, such as a fixed-wing UAV. Our simulations showed our algorithm allowed for faster collection of data than current solutions which can only accommodate slower mobile sinks. When using our algorithm, the performance increases of using a mobile sink are still maintained over in-network data collection.

Researchers have recently exploited the use of mobile sinks in WSN and shown its potential benefits in energy savings. In order to maximize these savings and meet other QoS requirements, the mobile sink should collect all the data from the sensors during its limited contact time. This necessitate the provisioning of appropriate mechanisms to improve packet reception rate (PRR) from sensor nodes to the sink while efficiently utilizing underlying resources. In this paper, we conducted actual experiments to understand the reasons behind failures in packet reception. Accordingly, we exploited the use of multiple receiver radios in mobile sinks. Through actual experiments, we evaluated the performance gains provided by multi-radio mobile sinks. We observed that using multiple receiver radios significantly improves base PRR and achieve required PRR with less number of retransmissions, particularly in critical communication ranges. In turn, minimizing number of transmissions improves other performance metrics including overall delay, efficient use of energy at sensor nodes, network lifetime.

We present a distributed verification algorithm to check the existence of multiple disjoint paths between all nodes in a wireless network. In contrast to the expensive algorithms computing full disjoint paths between nodes, our proposed algorithm distributes the computation across the network and makes statements regarding the interconnectedness of the entire network. Specifically, it allows each node to determine whether segmentation exists between its neighbors and thereby determine if it bottlenecks the network. Verification of disjoint paths would be useful for efficient use of resources and for the applications having intelligent nodes to self-configure the network for better survivability.

Reliable data transfer (RDT) is one of the key issues in wireless sensor networks (WSNs) and can be achieved by using link-level re-transmissions and multi-path routing. Another key issue is the scalability of WSNs. In this paper, we try to better understand and characterize/quantify the relationships between reliability and scalability, and identify possible design options for the future RDT protocols in large-scale WSNs. With this in mind, we first conducted actual experiments to characterize link reliability measures in an actual sensor network setting. We then used these measures and analyze how commonly used RDT mechanisms impact overall path reliability. In general, our analysis shows that the combination of link-level re-transmissions and multi-path routing is a viable solution in small-scale WSNs. However, due to the increased length of paths between sensor nodes and sinks in large-scale WSNs, it becomes costly to sustain the overall reliability at an acceptable level. Therefore, the future RDT protocols should focus on minimizing the path lengths using hierarchical structures in large-scale WSNs. It is also necessary to couple RDT protocols with routing protocols that can take link reliability measures into account.

Digital signatures are mainly used to make the receiver believe that the message was actually sent by the claimed sender. However, since generating digital signatures requires intensive computations, researchers proposed batch signing systems to sign multiple messages at once while having almost the same cost of signing one message. In this paper, we focus on how the batch formation strategies and batch sizes impact the response time of a batch signing system. We show how to minimize response time by selecting appropriate batch sizes and batch formation strategies based on the system parameters and load.

Reputation systems (RS) are designed to detect malicious nodes in a network and thwart their attacks, such as the spreading of viruses or worms, or attacking known vulnerabilities. They do this by collecting information about past transactions of a node and utilizing that to predict its future behavior. Traditionally, RSs have been designed by manually devising specific models or equations that use historical data to defend against certain types of attacks. In this paper, we propose a machine learning based RS that automates the process of devising the RS model and defends against many patterns of attacks. We discuss the merits of this approach and propose using support vector machines as the basis of the RS. We delineated the factors associated with building the SVM based RS and then proposed and evaluated our technique. We compared the performance of our RS with another RS found in the literature, called TrustGuard, and showed that our RS significantly outperforms TrustGuard. Our RS correctly distinguishes between good and malicious nodes with high accuracy, even when the proportion of malicious nodes in the network is very high.

Video streaming over peer-to-peer networks has received significant attention recently. Accordingly, much work is done on video streaming under the assumption that all the peers have the whole movie. However, it is likely that many peers may only store a fraction of the movie due to their resource constraints. Therefore, there is a need to develop appropriate mechanisms to facilitate efficient streaming when each user stores a fraction of the movie. With this in mind, we propose a distributed data structure called PeerGraph in which each peer determines other peers having the previous or subsequent fractions of the movie and maintains pointers to these peers. In our model, a peer has full control on how many segments it wants to store. However, we require it to store consecutive segments. In order to stream, a client first finds a peer that contains the first segment and then uses the proposed PeerGraph to locate subsequent segments. We use extensive simulations to investigate the effect of various parameters. Simulation results support feasibility of the proposed scheme.

We propose a fully distributed MAC-layer priority scheduling mechanism, called LPT-DPS (Lower-Priority-Triggered Distributed Priority Scheduling), for wireless ad hoc networks. LPT-DPS can allocate channel bandwidth to flows with different priorities in such a way that the higher the priority level of the flow, the higher the bandwidth that the flow acquires. Using extensive simulations, we demonstrate the effectiveness of the proposed LPT-DPS in delivering the high priority traffic even when the low priority traffic is overwhelming.

We focus on the algorithmic aspect of selecting a path that minimizes a recently proposed nonlinear path metric (namely, WCETT) for providing high throughput in multi-radio, multihop wireless mesh networks. First, we consider an iterative line search technique and describe how to use it for finding the optimal path in some cases while finding approximately good paths in other cases. We also use the final line search to provide a lower bound on the optimal path. Second, we consider heuristics that might search the concave region of the search space and discover better paths missed by the line search. Specifically, we propose a linearly-guided nonlinear search (LGNS) heuristic. Using simulations, we show the effectiveness of the proposed solutions.

Ethernet over SONET (EoS) is a popular approach for interconnecting geographically distant Ethernet segments using a SONET transport infrastructure. It typically uses virtual concatenation (VC) for dynamic bandwidth management. The aggregate SONET bandwidth that supports a given EoS system is obtained by "concatenating" a number of virtual channels (VCs), which together form a virtually concatenated group (VCG). This aggregate bandwidth can be increased on demand by adding one or more VCs to the existing VCG. The new VC must be selected such that its end-to-end delay is within a certain range that reflects the delays of all existing VCs in the VCG and the available memory buffer of the EoS system. Algorithmically, the problem of selecting such a VC becomes that of finding a path in a graph network that is bounded by an upper and lower bounds. In this paper, we first prove that the TSCP problem is NP-complete. We then propose a new solution for it based on the "backward-forward" search approach. We show that this solution is much more efficient than the previously proposed MLW-KSP algorithm. We then consider the TSCP problem under inaccurate link information, in which the delay and available bandwidth for each link are taken as random variables. The problem is now formulated as that of finding the most probable path that satisfies the upper and lower delay constraints. We consider two cases. In the first case, we assume that the link delays are random but the link bandwidths are exact. We then consider the more general case where both the link delays and bandwidths are random. Heuristic solutions are presented for both cases. Simulations are conducted to evaluate the performance of the proposed algorithms and to demonstrate the advantages of the probabilistic path selection approach over the classic trigger-based approach.

Tracing IP packets to their sources, known as IP traceback, is an important task in defending against IP spoofing and DoS attacks. Log-based IP traceback technique is to log packets at routers in the network and then determine the network paths which packets traversed using data extraction techniques. The biggest advantage of log-based IP traceback is the potential to trace a single packet. Tracing a single packet in the Internet using log-based IP traceback involves cooperation among all autonomous systems (AS) traversed by the packet. The single packet traceback process may not reach the packet origin if some AS on the forwarding path does not support IP traceback. IP traceback mechanisms are deployed within each AS independently. It is not reasonable to assume all ASes begin to support the same IP traceback mechanism in a short period of time. In this paper, we study the effectiveness of log-based IP traceback in tracing a single packet under the environment where not every AS supports log-based IP traceback. We propose a scheme to conduct the single packet traceback process in AS-level partial deployment scenario. We evaluate the performance of single packet IP traceback in AS-level partial deployment scenario based on our scheme through simulation.

This paper focuses on understanding the scale and the distribution of "state overhead'' (briefly load) that is incurred on the routers by various value-added network services, e.g., IP multicast and IP traceback. This understanding is essential to developing appropriate mechanisms and provisioning resources so that the Internet can support such value-added services in an efficient and scalable manner. We mainly consider the number of end-to-end paths or trees intersecting at a router to represent the amount of state overhead at that router. Hence, we analyze the router-level intersection characteristics of end-to-end Internet paths or trees to approximate the state overhead distribution in the Internet. For the reliability of our analysis, a representative, end-to-end router-level Internet map is essential. Although several maps are available, they are at best insufficient for our analysis. Therefore, in the first part of our work, we exert a measurement study to obtain a large size end-to-end router-level map conforming to our constraints. In the second part, we conduct various experiments using our map and shed some light on the scale and distribution of state overhead of value-added Internet services in both unicast and multicast environments.

We introduce a new "state-path decoupled QoS-based routing framework" (SPD-QRF) in which path computation and the dynamics of network state information along the computed paths are considered in a decoupled manner. Basically, SPD-QRF first makes several (potentially feasible) paths be readily available throughout the network(s) by marking the outgoing links of every router as forward, backward, or neutral towards every destination based on some static information. This can be seen as a generalization of the current Internet routing. Once the direction of every link is determined, end nodes explore the readily available paths using a randomized path discovery strategy. Along the explored paths, end-to-end path-state information is determined by accumulating the locally maintained QoS-related information at the routers. Our simulation results show that similar performance results for finding feasible paths under SPC-QRF can be accomplished by using much simpler and scalable solutions under SPD-QRF.

We consider the problem of minimizing the differential delay in a virtually concatenated Ethernet over SONET (EoS) system by suitable path selection. The link capacity adjustment scheme (LCAS) enables network service providers to dynamically add STS-n channels to or drop them from a virtually concatenated group (VCG). A new STS-n channel can be added to the VCG provided that the differential delay between the new STS-n channel and the existing STS-n channels in the VCG is within a certain bound that reflects the available memory buffer supported by the EoS system. We model the problem of finding such a STS-n channel as a constrained path selection problem where the cost of the required (feasible) path is constrained not only by an upper bound but also by a lower bound. We propose two algorithms to find such a path. Algorithm I uses the well-known k-shortest-path algorithm. Algorithm II is based on a modified link metric that linearly combines the original link weight (the link delay) and the inverse of that weight. The theoretical properties of such a metric are studied and used to develop a highly efficient heuristic for path selection. Simulations are conducted to evaluate the performance of both algorithms in terms of the miss rate and the execution time (average computational complexity).

One of the challenging issues in exchanging multimedia information over a network is how to determine a feasible path that satisfies all the quality-of-service (QoS) requirements of multimedia applications while maintaining high utilization of network resources. The latter objective implies the need to impose an additional optimality requirement on the feasibility problem. This can be done through a primary cost function (e.g., administrative weight, hop-count) according to which the selected feasible path is optimal. In general, multiconstrained path selection, with or without optimization, is an NP-complete problem that cannot be exactly solved in polynomial time. Heuristics and approximation algorithms with polynomial- and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions suffer either from excessive computational complexities that cannot be used for online network operation or from low performance. Moreover, they only deal with special cases of the problem (e.g., two constraints without optimization, one constraint with optimization, etc.). For the feasibility problem under multiple constraints, some researchers have recently proposed a nonlinear cost function whose minimization provides a continuous spectrum of solutions ranging from a generalized linear approximation (GLA) to an asymptotically exact solution. In this paper, we propose an efficient heuristic algorithm for the most general form of the problem. We first formalize the theoretical properties of the above nonlinear cost function. We then introduce our heuristic algorithm (H/spl I.bar/MCOP), which attempts to minimize both the nonlinear cost function (for the feasibility part) and the primary cost function (for the optimality part). We prove that H/spl I.bar/MCOP guarantees at least the performance of GLA and often improves upon it. H/spl I.bar/MCOP has the same order of complexity as Dijkstra's algorithm. Using extensive simulations on random graphs and realistic network topologies with correlated and uncorrelated link weights from several distributions including uniform, normal, and exponential, we show the efficiency of H/spl I.bar/MCOP over its (less general) contenders in terms of finding feasible paths and minimizing their costs under the same level of computational complexity.

A key issue in any QoS routing framework is how to compute a path that satisfies given QoS constraints. We focus on the path computation problem subject to bandwidth and delay constraints. This problem can be solved easily if the exact state information is available to the node computing the path. In practice, nodes have only imprecise knowledge of the network state. Reliance on outdated information and treating it as exact can significantly degrade the effectiveness of the path selection. We adopt a probabilistic approach in which the state parameters (available bandwidth and delay) are characterized by random variables. The goal is then to find the most-probable bandwidth-delay-constrained path (MP-BDCP). We provide efficient solutions for the MP-BDCP problem by decomposing it into the most-probable delay-constrained path (MP-DCP) problem and the most-probable bandwidth-constrained path (MP-BCP) problem. MP-DCP by itself is known to be NP-hard, necessitating the use of approximate solutions. We use the central limit theorem and Lagrange relaxation techniques to provide two complementary solutions for MP-DCP. These solutions are highly efficient, requiring on average a few iterations of Dijkstra's shortest path algorithm. As for MP-BCP, it can be easily transformed into a variant of the shortest path problem. Our MP-DCP and MP-BCP solutions are then combined to obtain a set of near-nondominated paths for the MP-BDCP problem. Decision makers can then select one or more of these paths based on a specific utility function. Extensive simulations demonstrate the efficiency of the proposed algorithmic solutions and, more generally, to contrast the probabilistic path selection approach with the standard threshold-based triggered approach.

Current link-state routing protocols (e.g., OSPF) use flooding to disseminate link-state information throughout the network. Despite its simplicity and reliability, flooding incurs unnecessary communications overhead since nodes may receive multiple copies of the same advertisement. This extra overhead becomes an Issue in the context of quality-of-service (QoS) routing, where link state is dynamic and needs to be advertised frequently. The advertisement overhead can be significantly reduced by using tree-based broadcasting approaches. Although several of these approaches have been proposed in the literature, they are not used in practice because of their complexity and/or unreliability. We propose a new link-state dissemination approach that combines the best features of flooding and tree-based broadcasting. Our hybrid approach is particularly suited for "dynamic" link metrics (e.g., available bandwidth). It uses periodic flooding to advertise topology changes and first-time LSAs (link-state advertisements), and uses tree-based broadcasting to disseminate subsequent refresh LSAs. The broadcast trees in our approach are constructed dynamically during the flooding of the first LSA, without the need for the complex algorithms of previous tree-based approaches. Two versions of our dissemination approach are presented, with one being more suitable for networks with frequent topological changes. We prove the correctness of our approach and contrast its communications overhead with flooding and pure tree-based broadcasting. The results indicate that our hybrid approach has a significantly lower overhead than flooding; yet It enjoys the simplicity, reliability, and fast convergence of flooding. Finally, we outline how OSPF can be extended to support the proposed dissemination approach.

Providing quality-of-service (QoS) guarantees in packet networks gives rise to several challenging issues. One of them is how to determine a feasible path that satisfies a set of constraints while maintaining high utilization of network resources. The latter objective implies the need to impose an additional optimality requirement on the feasibility problem. This can be done through a primary cost function (e.g., administrative weight, hop count) according to which the selected feasible path is optimal. In general, multi-constrained path selection, with or without optimization, is an NP-complete problem that cannot be exactly solved in polynomial-time. Heuristics and approximation algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions suffer either from excessive computational complexities that cannot be used for online network operation or from low performance. Moreover, they only deal with special cases of the problem (e.g., two constraints without optimization, one constraint with optimization, etc.). For the feasibility problem under multiple constraints, some researchers have proposed a nonlinear cost function whose minimization provides a continuous spectrum of solutions ranging from a generalized linear approximation (GLA) to an asymptotically exact solution. We propose an efficient heuristic algorithm for the most general form of the problem. We first formalize the theoretical properties of the above nonlinear cost function. We then introduce our heuristic algorithm (H MCOP), which attempts to minimize both the nonlinear cost function (for the feasibility part) and the primary cost function (for the optimality part). We prove that H MCOP guarantees at least the performance of GLA and often improves upon it. H MCOP has the same order of complexity as Dijkstra's algorithm. Using extensive simulations on random graphs with correlated and uncorrelated link weights, we show that under the same level of computational complexity, H MCOP outperforms its (less general) contenders in its success rate in finding feasible paths and in the cost of such paths.

One of the key issues in providing end-to-end quality-of-service guarantees in packet networks is how to determine a feasible route that satisfies a set of constraints while simultaneously maintaining high utilization of network resources. In general, finding a path subject to multiple additive constraints (e.g., delay, delay-jitter) is an NP-complete problem that cannot be exactly solved in polynomial time. Accordingly, heuristics and approximation algorithms are often used to address to this problem. Previously proposed algorithms suffer from either excessive computational cost or low performance. In this paper, we provide an efficient approximation algorithm for finding a path subject to two additive constraints. The worst-case computational complexity of this algorithm is within a logarithmic number of calls to Dijkstra's shortest path algorithm. Its average complexity is much lower than that, as demonstrated by simulation results. The performance of the proposed algorithm is justified via theoretical performance bounds. To achieve further performance improvement, several extensions to the basic algorithm are also provided at low extra computational cost. Extensive simulations are used to demonstrate the high performance of the proposed algorithm and to contrast it with other path selection algorithms.