Physical Sciences and Mathematics Commons^™

Matrix Profile Data Mining For Bgp Anomaly Detection, Ben A. Scott, Michael N. Johnstone, Patryk Szewczyk, Steven Richardson

Research outputs 2022 to 2026

The Border Gateway Protocol (BGP), acting as the communication protocol that binds the Internet, remains vulnerable despite Internet security advancements. This is not surprising, as the Internet was not designed to be resilient to cyber-attacks, therefore the detection of anomalous activity was not of prime importance to the Internet creators. Detection of BGP anomalies can potentially provide network operators with an early warning system to focus on protecting networks, systems, and infrastructure from significant impact, improve security posture and resilience, while ultimately contributing to a secure global Internet environment. In this paper, we present a novel technique for the detection …

Glop: Learning Global Partition And Local Construction For Solving Large-Scale Routing Problems In Real-Time, Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, Fanzhang Li

Research Collection School Of Computing and Information Systems

The recent end-to-end neural solvers have shown promise for small-scale routing problems but suffered from limited real-time scaling-up performance. This paper proposes GLOP (Global and Local Optimization Policies), a unified hierarchical framework that efficiently scales toward large-scale routing problems. GLOP partitions large routing problems into Travelling Salesman Problems (TSPs) and TSPs into Shortest Hamiltonian Path Problems. For the first time, we hybridize non-autoregressive neural heuristics for coarse-grained problem partitions and autoregressive neural heuristics for fine-grained route constructions, leveraging the scalability of the former and the meticulousness of the latter. Experimental results show that GLOP achieves competitive and state-of-the-art real-time performance …

Segac: Sample Efficient Generalized Actor Critic For The Stochastic On-Time Arrival Problem, Honglian Guo, Zhi He, Wenda Sheng, Zhiguang Cao, Yingjie Zhou, Weinan Gao

Research Collection School Of Computing and Information Systems

This paper studies the problem in transportation networks and introduces a novel reinforcement learning-based algorithm, namely. Different from almost all canonical sota solutions, which are usually computationally expensive and lack generalizability to unforeseen destination nodes, segac offers the following appealing characteristics. segac updates the ego vehicle’s navigation policy in a sample efficient manner, reduces the variance of both value network and policy network during training, and is automatically adaptive to new destinations. Furthermore, the pre-trained segac policy network enables its real-time decision-making ability within seconds, outperforming state-of-the-art sota algorithms in simulations across various transportation networks. We also successfully deploy segac …

Towards Machine Learning-Based Fpga Backend Flow: Challenges And Opportunities, Imran Taj, Umer Farooq

All Works

Field-Programmable Gate Array (FPGA) is at the core of System on Chip (SoC) design across various Industry 5.0 digital systems—healthcare devices, farming equipment, autonomous vehicles and aerospace gear to name a few. Given that pre-silicon verification using Computer Aided Design (CAD) accounts for about 70% of the time and money spent on the design of modern digital systems, this paper summarizes the machine learning (ML)-oriented efforts in different FPGA CAD design steps. With the recent breakthrough of machine learning, FPGA CAD tasks—high-level synthesis (HLS), logic synthesis, placement and routing—are seeing a renewed interest in their respective decision-making steps. We focus …

Learning Large Neighborhood Search For Vehicle Routing In Airport Ground Handling, Jianan Zhou, Yaoxin Wu, Zhiguang Cao, Wen Song, Jie Zhang, Zhenghua Chen

Research Collection School Of Computing and Information Systems

Dispatching vehicle fleets to serve flights is a key task in airport ground handling (AGH). Due to the notable growth of flights, it is challenging to simultaneously schedule multiple types of operations (services) for a large number of flights, where each type of operation is performed by one specific vehicle fleet. To tackle this issue, we first represent the operation scheduling as a complex vehicle routing problem and formulate it as a mixed integer linear programming (MILP) model. Then given the graph representation of the MILP model, we propose a learning assisted large neighborhood search (LNS) method using data generated …

Joint Congestion And Contention Avoidance In A Scalable Qos-Aware Opportunistic Routing In Wireless Ad-Hoc Networks, Ali Parsa, Neda Moghim, Sasan Haghani

VMASC Publications

Opportunistic routing (OR) can greatly increase transmission reliability and network throughput in wireless ad-hoc networks by taking advantage of the broadcast nature of the wireless medium. However, network congestion is a barrier in the way of OR's performance improvement, and network congestion control is a challenge in OR algorithms, because only the pure physical channel conditions of the links are considered in forwarding decisions. This paper proposes a new method to control network congestion in OR, considering three types of parameters, namely, the backlogged traffic, the traffic flows' Quality of Service (QoS) level, and the channel occupancy rate. Simulation results …

Energy-Efficient Multi-Rate Opportunistic Routing In Wireless Mesh Networks, Mohammad Ali Mansouri Khah, Neda Moghim, Nasrin Gholami, Sachin Shetty

VMASC Publications

Opportunistic or anypath routing protocols are focused on improving the performance of traditional routing in wireless mesh networks. They do so by leveraging the broadcast nature of the wireless medium and the spatial diversity of the network. Using a set of neighboring nodes, instead of a single specific node, as the next hop forwarder is a crucial aspect of opportunistic routing protocols, and the selection of the forwarder set plays a vital role in their performance. However, most opportunistic routing protocols consider a single transmission rate and power for the nodes, which limits their potential. To address this limitation, this …

Efficient Data Collection In Iot Networks Using Trajectory Encoded With Geometric Shapes, Xiaofei Cao, Sanjay Kumar Madria

Computer Science Faculty Research & Creative Works

The mobile edge computing (MEC) paradigm changes the role of edge devices from data producers and requesters to data consumers and processors. MEC mitigates the bandwidth limitation between the edge server and the remote cloud by directly processing the large amount of data locally generated by the network of the internet of things (IoT) at the edge. An efficient data-gathering scheme is crucial for providing quality of service (QoS) within MEC. To reduce redundant data transmission, this paper proposes a data collection scheme that only gathers the necessary data from IoT devices (like wireless sensors) along a trajectory. Instead of …

Learning Improvement Heuristics For Solving Routing Problems, Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, Andrew Lim

Research Collection School Of Computing and Information Systems

Recent studies in using deep learning to solve routing problems focus on construction heuristics, the solutions of which are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by hand-crafted rules which may limit their performance. In this paper, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention based deep architecture as the policy network to guide the selection of next solution. We apply our method to two important routing problems, i.e. travelling salesman …

Dynamic Path Planning For Unmanned Aerial Vehicles Under Deadline And Sector Capacity Constraints, Sudharsan Vaidhun, Zhishan Guo, Jiang Bian, Haoyi Xiong, Sajal K. Das

Computer Science Faculty Research & Creative Works

The US National Airspace System is currently operating at a level close to its maximum potential. The limitation comes from the workload demand on the air traffic controllers. Currently, the air traffic flow management is based on the flight path requests by the airline operators, whereas the minimum separation assurance between flights is handled strategically by air traffic control personnel. In this paper, we propose a scalable framework that allows path planning for a large number of unmanned aerial vehicles (UAVs) taking into account the deadline and weather constraints. Our proposed solution has a polynomial-time computational complexity that is also …

Heterogeneous Attentions For Solving Pickup And Delivery Problem Via Deep Reinforcement Learning, Jingwen Li, Liang Xin, Zhiguang Cao, Andrew Lim, Wen Song, Jie Zhang

Research Collection School Of Computing and Information Systems

Recently, there is an emerging trend to apply deep reinforcement learning to solve the vehicle routing problem (VRP), where a learnt policy governs the selection of next node for visiting. However, existing methods could not handle well the pairing and precedence relationships in the pickup and delivery problem (PDP), which is a representative variant of VRP. To address this challenging issue, we leverage a novel neural network integrated with a heterogeneous attention mechanism to empower the policy in deep reinforcement learning to automatically select the nodes. In particular, the heterogeneous attention mechanism specifically prescribes attentions for each role of the …

Speeding Up Routing Schedules On Aisle Graphs With Single Access, Francesco Betti Sorbelli, Stefano Carpin, Federico Coro, Sajal K. Das, Alfredo Navarra, Cristina M. Pinotti

Computer Science Faculty Research & Creative Works

In this article, we study the orienteering aisle-graph single-access problem (OASP), a variant of the orienteering problem for a robot moving in a so-called single-access aisle graph, i.e., a graph consisting of a set of rows that can be accessed from one side only. Aisle graphs model, among others, vineyards or warehouses. Each aisle-graph vertex is associated with a reward that a robot obtains when it visits the vertex itself. As the energy of the robot is limited, only a subset of vertices can be visited with a fully charged battery. The objective is to maximize the total reward collected …

Towards Detecting, Characterizing, And Rating Of Road Class Errors In Crowd-Sourced Road Network Databases, Johanna Guth, Sina Keller, Stefan Hinz, Stephan Winter

Journal of Spatial Information Science

OpenStreetMap (OSM), with its global coverage and Open Database License, has recently gained popularity. Its quality is adequate for many applications, but since it is crowd-sourced, errors remain an issue. Errors in associated tags of the road network, for example, are impacting routing applications. Particularly road classification errors often lead to false assumptions about capacity, maximum speed, or road quality, possibly resulting in detours for routing applications. This study aims at finding potential classification errors automatically, which can then be checked and corrected by a human expert. We develop a novel approach to detect road classification errors in OSM by …

Step-Wise Deep Learning Models For Solving Routing Problems, Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang

Research Collection School Of Computing and Information Systems

Routing problems are very important in intelligent transportation systems. Recently, a number of deep learning-based methods are proposed to automatically learn construction heuristics for solving routing problems. However, these methods do not completely follow Bellman's Principle of Optimality since the visited nodes during construction are still included in the following subtasks, resulting in suboptimal policies. In this article, we propose a novel step-wise scheme which explicitly removes the visited nodes in each node selection step. We apply this scheme to two representative deep models for routing problems, pointer network and transformer attention model (TAM), and significantly improve the performance of …

Multi-Decoder Attention Model With Embedding Glimpse For Solving Vehicle Routing Problems, Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang

Research Collection School Of Computing and Information Systems

We present a novel deep reinforcement learning method to learn construction heuristics for vehicle routing problems. In specific, we propose a Multi-Decoder Attention Model (MDAM) to train multiple diverse policies, which effectively increases the chance of finding good solutions compared with existing methods that train only one policy. A customized beam search strategy is designed to fully exploit the diversity of MDAM. In addition, we propose an Embedding Glimpse layer in MDAM based on the recursive nature of construction, which can improve the quality of each policy by providing more informative embeddings. Extensive experiments on six different routing problems show …

Application-Aware Cross-Layer Enrgy-Eficient Routing Scheme, Xu Fang, Hiyin Zhang, Wang Jing, Xu Ning, Zhijong Wang, Deng Min

Journal of System Simulation

Abstract: An aplication- aware cross-layer energy-effcient routing scheme (ACER) was presented to minimize the effect of supplt of terminals in ad hoc network composed of smart mobile devices. Features of energy consumption were sensed by application aware energy model with the application monitor and the remaining energy monitor. Stability of network path was monitored by link stability monitoring module in Data link layer. As the scheme used the idea of cross-layer design, network topology information, application-aware information in application layer and link-stability were utilized synthetically to make routing deisions in network layer;Simulations were crried out on NS2 platform. The …

Preforming A Vulnerability Assessment On A Secured Network, Mathias Sovine

Williams Honors College, Honors Research Projects

A computer network will be built using 3 routers, 1 switch, and 4 computers. The network will be used to simulate the connections between an at home office and the internet. The network will be divided into 3 sub-networks. The routers will be secured using methods like access control lists, changing default admin passwords, and network encryption. The switch will be secured using methods like switchport security and setting access passwords. Once the network is secured, three penetration testing techniques and three exploits will be performed on the network. The results of the exploits and penetration testing techniques will be …

Data And Resource Management In Wireless Networks Via Data Compression, Gps-Free Dissemination, And Learning, Xiaofei Cao

Doctoral Dissertations

“This research proposes several innovative approaches to collect data efficiently from large scale WSNs. First, a Z-compression algorithm has been proposed which exploits the temporal locality of the multi-dimensional sensing data and adapts the Z-order encoding algorithm to map multi-dimensional data to a one-dimensional data stream. The extended version of Z-compression adapts itself to working in low power WSNs running under low power listening (LPL) mode, and comprehensively analyzes its performance compressing both real-world and synthetic datasets. Second, it proposed an efficient geospatial based data collection scheme for IoTs that reduces redundant rebroadcast of up to 95% by only collecting …

Research On Adaptive Routing Algorithm For Wireless Weak-Connection Network, Hua Xiang, Hongjuan Yao, Wang Hai, Wang Zhao, Jietao Zhang, Lili Shu

Journal of System Simulation

Abstract: The wireless weak-connected network has the characteristics of long delay, high dynamic topology, and unstable links. With the lack of continuity from the source end to the destination end of network connection, in order to solve the problem of communication difficulty, the intelligence and adaptability of Physarum polycephalum are introduced, and the adaptive wireless weak-connected network routing algorithm is proposed. A wireless weak-connected network model is build and the mathematical relationships of link capacity is deduced. The next-hop selection strategy and optimal routing strategy is designed to achieve the best-effort delivery of data in wireless weak-connected network environmrnt. Simulation …

Routing Optimization In Heterogeneous Wireless Networks For Space And Mission-Driven Internet Of Things (Iot) Environments, Sara El Alaoui

Department of Electrical and Computer Engineering: Dissertations, Theses, and Student Research

As technological advances have made it possible to build cheap devices with more processing power and storage, and that are capable of continuously generating large amounts of data, the network has to undergo significant changes as well. The rising number of vendors and variety in platforms and wireless communication technologies have introduced heterogeneity to networks compromising the efficiency of existing routing algorithms. Furthermore, most of the existing solutions assume and require connection to the backbone network and involve changes to the infrastructures, which are not always possible -- a 2018 report by the Federal Communications Commission shows that over 31% …

Simulation Of Joint Power Control Routing Algorithm For Interference And Energy Consumption In Crahns, Zhufang Kuang, Zhigang Chen

Journal of System Simulation

Abstract: Problems of interference power to primary user by secondary userand the secondary user's running out of energy under underlay spectrum access model in cognitive radio ad hoc networks (CRAHNs) were investigated. Joint power control, routing and spectrum (channel) allocation algorithm (PRSA) based on particle swarm optimization were proposed. The goal of PRSA was to minimize interference power to primary user and prolong lifetime of CRAHNs. Particle encoding, particle initialization, fitness function, particle flight were included in PRSA. An Adjacency matrix with two-tuples containing allocated channel and power level was designed, and three operation rules for particle were redefined. …

Goods Consumed During Transit In Split Delivery Vehicle Routing Problems: Modeling And Solution, Wenzhe Yang, Di Wang, Wei Pang, Ah-Hwee Tan, You Zhou

Research Collection School Of Computing and Information Systems

This article presents the modeling and solution of an extended type of split delivery vehicle routing problem (SDVRP). In SDVRP, the demands of customers need to be met by efficiently routing a given number of capacitated vehicles, wherein each customer may be served multiple times by more than one vehicle. Furthermore, in many real-world scenarios, consumption of vehicles en route is the same as the goods being delivered to customers, such as food, water and fuel in rescue or replenishment missions in harsh environments. Moreover, the consumption may also be in virtual forms, such as time spent in constrained tasks. …

A Light-Weight Solution For Blackhole Attacks In Wireless Sensor Networks, Bi̇lal Erman Bi̇lgi̇n, Selçuk Baktir

Turkish Journal of Electrical Engineering and Computer Sciences

Wireless sensors, which are smaller and cheaper, have started being used in many different applications. Military applications, health care and industrial monitoring, environmental applications, smart grids, and vehicular ad-hoc networks are some of the best known applications of wireless sensors. In some applications, especially military, environmental, and health care applications, it is required that the communication between sensor nodes be encrypted to achieve privacy and confidentiality. In this work, some modifications have been made to the ad-hoc on-demand distance vector routing protocol, mostly preferred in wireless sensor networks, to make data communications more reliable. The proposed routing protocol is shown …

Implementation Of The Aodv Routing In An Energy-Constrained Mesh Network, Altin Zejnullahu, Zhilbert Tafa

International Journal of Business and Technology

Wireless sensor networks (WSNs) compose the fundamental platform for a number of Internet of Things (IoT) applications, especially those related to the environmental, health, and military surveillance. While being autonomous in power supply, the main challenge in node’s processing and communication architecture design remains the energy efficiency. However, this goal should not limit the main functionality of the system which is often related to the network coverage and connectivity.

This paper shows the implementation of the Ad-hoc On-demand Distance Vector (AODV) routing algorithm in an XBee based platform. As shown, the network can achieve low power consumption per node primarily …

Iterated Local Search Algorithms For Bike Route Generation, Aidan Pieper

Honors Theses

Planning routes for recreational cyclists is challenging because they prefer longer more scenic routes, not the shortest one. This problem can be modeled as an instance of the Arc Orienteering Problem (AOP), a known NP-Hard optimization problem. Because no known algorithms exist to solve this optimization problem efficiently, we solve the AOP using heuristic algorithms which trade accuracy for speed. We implement and evaluate two different Iterated Local Search (ILS) heuristic algorithms using an open source routing engine called GraphHopper and the OpenStreetMap data set. We propose ILS variants which our experimental results show can produce better routes at the …

Multi-Stop Routing Optimization: A Genetic Algorithm Approach, Abbas Hommadi

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

In this research, we investigate and propose new operators to improve Genetic Algorithm’s performance to solve the multi-stop routing problem. In a multi-stop route, a user starts at point x, visits all destinations exactly once, and then return to the same starting point. In this thesis, we are interested in two types of this problem. The first type is when the distance among destinations is fixed. In this case, it is called static traveling salesman problem. The second type is when the cost among destinations is affected by traffic congestion. Thus, the time among destinations changes during the day. In …

An Object Oriented Approach To Modeling And Simulation Of Routing In Large Communication Networks, Armin Mikler, Johnny S. Wong, Vasant Honavar

Johnny Wong

The complexity (number of entities, interactions between entities, and resulting emergent dynamic behavior) of large communication environments which contain hundreds of nodes and links make simulation an important tool for the study of such systems. Given the difficulties associated with complete analytical treatment of complex dynamical systems, it is often the only practical tool that is available. This paper presents an example of a flexible, modular, object-oriented toolbox designed to support modeling and experimental analysis of a large family of heuristic knowledge representation and decision functions for adaptive self-managing communication networks with particular emphasis on routing strategies. It discusses in …

Implementation Of The Aodv Routing In An Energy-Constrained Mesh Network, Altin Zejnullahu, Zhilbert Tafa

UBT International Conference

Wireless sensor networks (WSNs) compose the fundamental platform for a number of Internet of Things (IoT) applications, especially those related to the environmental, health, and military surveillance. While being autonomous in power supply, the main challenge in node’s processing and communication architecture design remains the energy efficiency. However, this goal should not limit the main functionality of the system which is often related to the network coverage and connectivity. This paper shows the implementation of the Ad-hoc On-demand Distance Vector (AODV) routing algorithm in an XBee based platform. As shown, the network can achieve low power consumption per node primarily …

Fuzzy Logic-Based Guaranteed Lifetime Protocol For Real-Time Wireless Sensor Networks, Babar Shah, Farkhund Iqbal, Ali Abbas, Ki Il Kim

All Works

© 2015 by the authors; licensee MDPI, Basel, Switzerland. Few techniques for guaranteeing a network lifetime have been proposed despite its great impact on network management. Moreover, since the existing schemes are mostly dependent on the combination of disparate parameters, they do not provide additional services, such as real-time communications and balanced energy consumption among sensor nodes; thus, the adaptability problems remain unresolved among nodes in wireless sensor networks (WSNs). To solve these problems, we propose a novel fuzzy logic model to provide real-time communication in a guaranteed WSN lifetime. The proposed fuzzy logic controller accepts the input descriptors energy, …

Residual-Based Measurement Of Peer And Link Lifetimes In Gnutella Networks, Xiaoming Wang, Zhongmei Yao, Dmitri Loguinov

Zhongmei Yao

Existing methods of measuring lifetimes in P2P systems usually rely on the so-called create-based method (CBM), which divides a given observation window into two halves and samples users "created" in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we flrst derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent …