Search

Opportunistic multihop networks with mobile relays recently have drawn much attention from researchers across the globe due to their wide applications in various challenging environments. However, because of their peculiar intrinsic features like lack of continuous connectivity, network partitioning, highly dynamic behavior, and long delays, it is very arduous to model and effectively capture the temporal variations of such networks with the help of classical graph models. In this work, we utilize an evolving graph to model the dynamic network and propose a matrix-based algorithm to generate all minimal path sets between every node pair of such network. We show that these time-stamped-minimal-path sets (TS-MPS) between each given source-destination node pair can be used, by utilizing the well-known Sum-of-Disjoint Products technique, to generate various reliability metrics of dynamic networks, ie, two-terminal reliability of dynamic network and its related metrics, ie, two-terminal reliabilities of the foremost, shortest, and fastest TS-MPS, and Expected Hop Count. We also introduce and compute a new network performance metric-Expected Slot Count. We use two illustrative examples of dynamic networks, one of four nodes, and the other of five nodes, to show the salient features of our technique to generate TS-MPS and reliability metrics.

OAPA One approach to improve network capacity in future wireless networks is to deploy Access Points (APs) in a dense manner and employ a controller to manage these APs. Another innovation is to equip nodes with an In-Band Full- Duplex (IBFD) radio, which allows them to transmit and receive simultaneously over the same frequency band. A key challenge, however, is interference. To this end, a link scheduler plays a critical role in ensuring the benefits of dense APs deployment and IBFD are not negated by severe interference. Henceforth, this paper proposes three centralized algorithms that aim to drain a given set of packets from links in minimum time. We have compared these algorithms against a schedule where links transmit independently, and an algorithm that schedules links at slot boundaries. We studied the impact of varying node densities, transmission power and Signal-to-Interference-plus-Noise Ratio (SINR) thresholds on the link schedule. Our results show the overall completion time can be reduced by 68% as compared to scheduling links individually. Moreover, our algorithms reduce the completion time by 13% as compared to scheduling links on a slot-by-slot basis.

This paper exposes and explore the practical issues with the usability of log artefacts for digital forensics in cloud computing. Logs, providing detailed events of actions on a time scale have been a prime forensic artefact. However collection of logs for analysis, from a cloud computing environment is complex and challenging task, primarily due to the volatility, multi-tenancy, authenticity and physical storage locations of logs, which often results in jurisdictional challenges too. Diverse nature of logs, such as network logs, system logs, database logs and application logs produces additional complexity in the collection and analysis for investigative purposes. In addition there is no commonality in log architecture between cloud service providers, nor the log information fully meets the specific needs of forensic practitioners. In this paper we present a practical log architecture framework, analyse it from the perspective and business needs of forensic practitioners. We prove the framework on an ownCloud - a widely used open source platform. The log architecture has been assessed by validating it against the Association of Chief Police Officers Good Practice Guide for Computer-Based Electronic Evidence guidelines. Further validation has been done against the National Institute of Standards and Technology published report on Cloud Computing Forensic Challenges, i.e., NISTIR 8006. Our work helps the forensic examiners and law enforcement agencies in establishing confidence in log artefacts and easy interpretation of logs by presenting it in a user friendly way. Our work also helps the investigators to build a collective chain of evidence as well as the Cloud Service Providers to provision forensics enabled logging.

Network reliability evaluation of Delay Tolerant Networks (DTNs) is a challenging task due to their inherent features like node mobility, dynamically changing network topology and existence of highly disruptive environmental conditions etc. The research so far on such time-evolving dynamic networks mainly focusses on topology control, routing and information propagation with a little attention paid towards computing their overall network reliability. In this paper, we model DTNs by using Time Aggregated Graph and propose the notion of time-stamped-minimal path sets between a given source-destination pair of nodes, besides, providing a simple yet novel method to enumerate them. Further, by employing Multiple Variable Inversion-Sum of Disjoint Products algorithm, we obtain disjointed time-stamped-minimal path sets, which have a one-to-one mapping with the overall reliability expression of such time evolving networks. For obtaining instances of a DTN during an operational period, we resort to Monte Carlo Simulation to simulate the dynamically changing topology and other probabilistically varying network aspects. The simulation results demonstrate the efficacy of our proposal. At the end, we also present some initial investigation and insight on the time-stamped-minimal cut sets and problem in enumerating them, and infer that the usual notion of cut sets seems inapplicable for dynamic networks.

It has been previously determined that SYN packet inter arrival times are conformant with Benford’s law, which predicts the frequency of the leading digits in naturally occurring collections of numbers, and suggested that conformity or non-conformity to Benford’s law could be used to detect network anomalies. This paper expands upon that suggestion by making three contributions. First, we verify that conformity to Benford’s law of inter arrival times is also true for certain types of both TCP and UDP packets. Second, we discover that packet length could also be another alternative to inter arrival times, with the advantage that it follows both Benford’s and Zipf’s laws, implying its reliability in detecting network traffic anomaly. Finally, we explore the potential application of power laws in the specific detection of denial-of-service (DoS) attacks using both inter arrival times and packet length. Extensive experiments on the MAWI benchmark dataset and two additional datasets support our claims and demonstrate that whilst Benfordian analysis of inter arrival times can identify DoS attacks, the combination of Benfordian and Zipfian analysis of packet length gives more reliable detection.

© 2013 IEEE. This paper considers the problem of deriving a time-division multiple-access (TDMA) schedule for multi-hop wireless networks that allow nodes to perform multiple transmissions/receptions to/from all of their neighbors simultaneously over the same frequency. To date, there are a number of link schedulers for the networks in question but they do not consider flow rate or any notion of fairness when deriving a TDMA schedule. Henceforth, we address this critical gap by proposing a link scheduler, called Algo-Fair, that, in addition to maximizing the number of links in each slot, also provides fairness among flows. In addition, it uses a novel augmentation step to distribute spare capacity fairly among flows. We believe this step is general and can be applied readily in other forms of wireless networks. Apart from that, Algo-Fair generates a schedule directly while yielding a fair rate allocation. This is different from existing methods that first use a flow contention graph to compute a fair share before deriving the corresponding schedule, which may not exist. Numerical results show Algo-Fair has higher fairness, minimum rate, and average total throughput than competing approaches, and low end-to-end delay.

IEEE In a rechargeable Wireless Sensor Network (rWSN), the amount of data forwarded by source nodes to one or more sinks is bounded by the energy harvesting rate of sensor nodes. To improve sensing quality, we consider a novel approach whereby we place a finite number of Auxiliary Chargers (ACs) with Wireless Power Transfer (WPT) and energy harvesting ability to boost the energy harvesting rate of some sensor nodes. We formulate a Mixed Integer Linear Program (MILP) to determine the subset of nodes that if upgraded will maximize the minimum source rate. We also propose two heuristic algorithms to place ACs in large scale rWSNs: (i) GND, which checks every non-upgraded sensor node and parks an AC next to the one yielding the highest increase in max-min rate, and (ii) OUED, which uses a relaxed version of the MILP to first share one unit of energy among sensor nodes. It then upgrades the sensor node with the highest one-unit share. Our results show that the max-min rate obtained by GND and OUED is respectively within 99.60% and 97.82% of the max-min rate derived by MILP in small networks with at most 90 nodes. In large networks with 200 nodes, the maximum gap between OUED and GND is only 0.191 kb/s. Lastly, OUED runs at least five times faster than GND.

IEEE A key approach to improve the capacity of Wireless Mesh Networks (WMNs) is to equip routers with multiple transmissions or receptions (MTR) capability. Thus, the resulting MTR WMN has significantly higher network capacity because routers can activate multiple links simultaneously. This, however, requires a MTR link scheduler that maximizes network capacity or equivalently, one that is capable of deriving a short schedule. Henceforth, we propose Period Controlled Pseudo Time Division Multiple Access (PCP-TDMA), a link scheduler that allows nodes to cooperatively reduce an initial link schedule or superframe over time in a distributed manner. Routers are able to adapt the superframe size iteratively using only local information to accommodate any topological changes. This means PCP-TDMA is particularly suited for use in large-scale MTR WMNs. We have evaluated PCP-TDMA in various network topologies, and compared it against ALGO-2, a centralized algorithm that uses global topological information to derive a schedule and thus serves as a benchmark. We also compare PCP-TDMA against two distributed approaches: JazzyMAC and ROMA. The results show that PCP-TDMA achieves similar performance with the centralized algorithm in all scenarios, and outperforms the distributed approaches significantly. Specifically, in a fully connected network, the resulting superframe length of PCP-TDMA is less than 1/3 and 1/2 of JazzyMAC and ROMA, respectively.

This paper considers the problem of deriving a Time Division Multiple Access (TDMA) link schedule for a single-channel, Multi-Transmit or Receive (MTR) Wireless Mesh Network (WMN). This problem is significant because a short schedule means the WMN has a higher network capacity. We first show that an existing solution, called Directed Edge Coloring (DEC), to channel assignment developed for WMNs with multiple transmit and receive capability is isomorphic to a TDMA schedule. This allows us to develop an efficient algorithm called DEC-MTR that derives a TDMA schedule or superframe for use in single-channel MTR WMNs. In addition, we propose a method to increase the number of links activated in each slot. We compare DEC-MTR against four state-of-the-art schedulers: DEC, Algo-1, HWF and MDF. Experiment results show that DEC-MTR produces equal superframe lengths with up to 23% higher capacity as compared to DEC, and up to 50% shorter superframe lengths as compared to Algo-1, HWF, and MDF with up to 58% higher capacity.

This letter considers a two-tiered multi-hop RF-harvesting network comprising of wireless routers and so called eh-nodes that harvest energy from RF emitted by the said routers. Our aim is to derive the shortest possible superframe or time division multiple access schedule for use by routers, which are responsible for meeting flow and energy demands. We present a linear program to derive the optimal schedule whilst satisfying the said demands. We also outline a heuristic algorithm called Algo-TS to generate transmission sets. Our results show Algo-TS produces superframes that are at most 2% longer than the optimal solution in all tested scenarios.

In rechargeable or energy harvesting wireless sensor networks (WSNs), a key concern is the max flow or data rate at one or more sinks. However, this data rate is constrained by the available energy at each node as well as link capacity. To date, in order to increase the amount of data extracted from a WSN, past works have considered routing approaches or they optimize the location of sinks. In contrast, we take a novel approach whereby we aim to 'upgrade' the recharging rate of a finite number of 'bottleneck' nodes using the so called auxiliary chargers (ACs) equipped with wireless power transfer capability. We formulate a mixed integer linear program (MILP) for the NP-hard problem at hand and propose three novel solutions to place ACs: 1) Path, which preferentially upgrades nodes on the shortest path among paths from sources to sinks, 2) Tabu, a meta-heuristic that first uses Path as the initial solution. It then searches for a neighboring solution that yields a higher max flow rate, and 3) LagOP, which approximates the said MILP using Lagrangian and sub-gradient optimization. Our results show that Tabu has the best performance, where it is able to achieve 99.40% of the max flow rate derived by MILP in tested scenarios.

This paper proposes a novel, iterative, distributed Medium Access Control (MAC) for Multi-Transmit-Receive (MTR) Wireless Mesh Networks (WMNs). The MAC called PCP- TDMA aims to construct the shortest possible schedule that allows nodes to transmit to or receive from all their neighbors simultaneously over the same frequency. Compared to the state- of-the-art, namely a centralized algorithm called ALGO-2, and two distributed approaches, namely JazzyMAC and ROMA, the results show that PCP-TDMA achieves similar performance to ALGO-2, and outperforms JazzyMAC and ROMA significantly. Specifically, in a fully connected network, the superframe pro- duced by PCP-TDMA is respectively only 1/3 and 1/2 the length of that generated by JazzyMAC and ROMA.

Multi-transmit-receive capability is fast becoming a significant feature of next-generation wireless mesh networks. It enables routers to transmit or receive distinct packets from multiple neighbors simultaneously. A key problem, however, is designing a distributed link-scheduling algorithm that ensures high network capacity. In this paper, we propose dMaxQ, which is a novel queue-length-aware distributed link scheduler that requires only one-hop neighbors' queue information and uses the celebrated max-weight policy in a distributed manner. We have evaluated the performance of dMaxQ in different network topologies for both single-hop and multihop traffic models and compared it against other approaches, including two queue-length-aware centralized algorithms and state-of-the-art distributed approaches: JazzyMAC and receive-oriented multiple access. The results show that for single-hop and multihop traffic scenarios, dMaxQ obtains, respectively, 100% and 90% of the throughput achieved by the theoretical centralized policy. Other distributed algorithms, such as JazzyMAC, only managed 25% of the theoretical throughput.

A key problem in wireless mesh networks is forwarding packets to/from one or more gateways with connectivity to the Internet. In this respect, a short link schedule, which determines the transmission time of links, is critical. To date, existing link schedulers do not consider routers that incorporate advances in multiple input multiple output communications, i.e., interference cancellation and spatial multiplexing. In particular, these routers are able to transmit or receive distinct packets on all their links concurrently as well as deliver multiple packets to a neighbor simultaneously. To this end, we consider the problem of deriving a time division multiple access schedule that forwards packets to their respective destination quickly. We first consider the personalized broadcast problem, which assumes a single gateway and present Algo-PB, a solution that produces a schedule that is within 34.5% of the lower bound, and is 45.5% shorter than those computed by the state-of-the-art algorithms. We then extend the problem to consider multiple gateways. This so-called forest construction problem is modeled as an integer linear program (ILP). We then outline Algo-FC, a novel heuristic that generates a balanced forest by repeatedly picking a node from the heaviest tree and migrating it to another tree if doing so reduces the overall load. Experiment results show that the resulting forest generated by Algo-FC is within 9.1% of the ILP solution.

Current network infrastructures are over-provisioned and thus exhibit poor power efficiency at low traffic load. We consider networks consisting of bundled links, whereby each link has one or more physical cables that can be switched off independently. The problem at hand is to switch off redundant nodes and cables during off-peak periods, while retaining the quality of services provided to existing traffic demands. Unfortunately, the problem to maximally shutdown redundant nodes and cables is Non-deterministic Polynomial-time (NP)-complete. Henceforth, we design a fast heuristic, called Multiple Paths by Shortest Path First (MSPF), that aims to maximise the number of switched-off nodes and cables subject to satisfying maximum link utilisation (MLU) and path length (PL) constraints. We have extensively evaluated the performance of MSPF on both real and synthetic topologies and traffic demands. Further, we have compared its performance against two state-of-the-art techniques: GreenTE, usable when each link has one cable, and Fast Greedy Heuristic (FGH), which supports bundled links but only for networks without MLU and PL constraints. On the Sprint network, MSPF can save on average 5% more power as compared to GreenTE while incurring only 1% of GreenTE's running time. While yielding equivalent power savings, MSPF requires only 0.35% of FGH's running time. Finally, setting MLU to at most 50% and PL to no longer than the network diameter, MSPF reduces the power usage of the GÉANT topology by up to 91% for links consisting of 10 cables. For experiments on synthetic topologies with bundle size of 30, MSPF yields a power saving of 89.81%. In this paper, we propose a new approach, that is, Multiple Paths by Shortest Path First, to find the minimum set of operational devices, that is, routers and cables, which can be used to route a given set of traffic demands while satisfying users' maximum link utilization and path length constraints. Simulation results show that Multipl

A key advance in enabling higher wireless mesh network capacity is allowing routers to transmit or receive (MTR) from multiple neighbors simultaneously over the same frequency. Achieving this capacity, however, is predicated on a link scheduler that is able to capitalize on the MTR capability of nodes to activate the maximum number of active links, and also to derive the shortest schedule that ensures all links are activated at least once. To date, existing schedulers do not consider the transmission or air-time of packet(s). Henceforth, this paper fills this gap and propose to derive the shortest superframe length, defined as the end time of the last transmitting link. Our scheduler, called A-TxRx, greedily adds links whenever a link finishes its transmission. As a result, unlike previous schedulers, links can start transmitting/receiving as soon as there is no conflict. We have evaluated the performance of A-TxRx in various network configurations, and compared it against two state-of-the-art approaches: 2P and JazzyMAC. The results show A-TxRx outperforming these algorithms significantly, especially when the network becomes denser. Specifically, the superframe length of A-TxRx is typically less than half of 2P and JazzyMAC, with 60 % more concurrently transmitting links.

Multiple transmit or receive (MTR) capability is a promising approach that significantly improves the capacity of Wireless Mesh Networks (WMNs). A fundamental problem is deriving a minimal link schedule or superframe that satisfies traffic demands. Existing MTR link schedulers or works that jointly consider routing and scheduling in wireless networks assume traffic demands are known in advance and are fixed. However, in practice, traffic demands are likely to be uncertain. Consequently, any computed solution will lead to either idle slots or congestion. Moreover, uncertain demands may cause a network operator to compute and install a new routing and superframe frequently; this is likely to incur high signaling overheads, especially in large scale multi-hop WMNs. Henceforth, in this paper, we consider random traffic demands characterized by a polyhedral set. We model the problem as a semi-infinite Linear Program (LP). We then propose a novel heuristic algorithm, called Algo-PolyH, that jointly considers both routing and superframe generation to produce a robust solution that is valid for all random demands that belong to a given polyhedral set. This fact is confirmed in our evaluation of Algo-PolyH in networks with varying number of degrees, number of flows, number of nodes and number of paths.

This paper provides an algorithm to design a communication network topology with minimal cost (C) and maximum (s, t) reliability (R) subject to a pre-defined bandwidth (Bmin) constraint, given (i) locations of the various computer nodes, (ii) their connecting links, (iii) each link’s reliability, cost and bandwidth, and (iv) a minimum bandwidth for the network. The bi-objective optimization problem is known NP-hard; henceforth we call the problem NTD-CR/B. We use the dynamic programming (DP) formulation as the engine in our proposed approach, DPCR/B, to generate the topology for solving NTD-CR/B. Further, we propose three greedy heuristics that enumerate and order only k?n (s, t) paths, where n is the total number of (s, t) paths in the network. Each heuristic allows DPCR/B to obtain the selected paths to form the topology using only k paths, which improves the time complexity while producing near optimal topology. Extensive simulations on large networks with various sizes show that DPCR/B is able to generate 91.2% optimal results while using only 1.37-27% of all paths in the grid networks that typically contain up to 299 paths.

The link schedule of a wireless network must ensure links receive sufficient transmission opportunities or time slots to meet their offered load. To date, existing link schedulers assume fixed link load. In practice, link load is likely to vary, meaning the computed schedule or superframe will have unnecessary idle times. In this letter, we propose to use stochastic programming (SP) to generate a superframe comprising of a Time Division Multiple Access (TDMA) and a random access part. Advantageously, it sizes both parts according to traffic distribution. We show how it can be used to derive a superframe for multi transmit (Tx) or receive (Rx) wireless networks. We show via numerical results the efficacy of our approach in reducing idle times and collisions given random demands.

This paper addresses an NP-hard problem, called NTD-CB/R, whose solution is of importance to applications requiring one or more Quality of Service (QoS). Specifically, the problem calls for a network topology that meets two objectives, i.e., minimal cost and maximum bandwidth, subject to a predefined (s, t) reliability constraint. We approach the problem by converting it into one with a single objective. This is achieved via a ratio, called bcr, between network bandwidth and cost to measure the goodness of each topology, and by applying Lagrange relaxation. Then we propose a dynamic programming (DP) scheme, and propose a heuristic solution, called DPCB/R, to generate each topology using all of its n (s, t) paths. This paper also proposes three heuristic path orders that allow DPCB/R to generate and use only k≤n paths to reduce its time complexity while producing similar results. Extensive simulations using 125 benchmark networks with various sizes show the merits of the path-orders, and effectiveness of our approach. DPCB/R is able to generate 88% optimal results for the networks. Further, its non-optimal results have a bcr ratio, bandwidth, and cost of only up to 1.56%, 0.9%, and, 2.1% off from the optimal, respectively. Further, for a grid network that contains 299 paths it uses only 1.1-27% of the paths while producing a topology that is only 0.92% off from optimal, with respect to bcr metric.

Multiple transmit (Tx) or receive (Rx) capability is a significant advance in wireless communications. This so called MTR capability allows the creation of wireless mesh networks (WMNs) that are ideal for use as a high-speed wireless backbone that spans vast geographical areas. A fundamental problem, however, is deriving a minimal transmission schedule or superframe that yields low end-to-end delays, with the primary constraint that routers are not allowed to Tx and Rx simultaneously. In this paper, we consider a joint routing and link scheduling approach that addresses two fundamental issues that influence end-to-end delays: superframe length and transmission slot order. Shortening the superframe length, in terms of slots, is expected to minimize the inter-link activation time while reordering transmission slots increases the likelihood that links on a path are activated consecutively. We propose two algorithms. The first called JRS-Multi-DEC uses a novel metric to minimize the load of each link while the second, called JRS-BIP, uses a Binary Integer Program approach. Both algorithms aim to minimize the overall delay and use slot re-ordering on the resulting schedule to further reduce delay. Numerical results show both algorithms are able to reduce the average end-to-end delay by approximately 50% as compared to a non joint routing algorithm.

The capacity of wireless mesh networks (WMNs) can be improved significantly using multiple input multiple output (MIMO) technology. The Degree of Freedoms (DoFs) or antenna elements available at each node enable concurrent transmission/reception of multiple independent data streams or can be used to suppress interference. In this paper, we study the problem of minimizing the Time Division Multiple Access (TDMA) superframe length, in terms of slots, of a multi transmit/receive MIMO-based WMN. We propose a novel heuristic algorithm named Algo-MIMO that uses a recently proposed node ordering DoF model for Interference Cancellation (IC). Numerical results show that Algo-MIMO is able to reduce the superframe length by up to 60% as compared to algorithms that use other IC models, and approximately 40% against algorithms that order nodes based on the number of neighbors, node weight or randomly.

© 2015, Ruiz-Rivera et al. To date, significant effort has gone into designing green traffic engineering (TE) techniques that consolidate traffic onto the minimal number of links/switches/routers during off-peak periods. However, little works exist that aim to green Multi-Protocol Label Switching (MPLS) capable networks. Critically, no work has studied the performance of green label switched paths (LSPs) establishment methods in terms of energy savings and acceptance rates. Henceforth, we add to the current state-of-the-art by studying green online and offline (LSP) establishment methods. Online methods rely only on past and current LSP requests while offline ones act as a theoretical benchmark whereby they also have available to them future LSP requests. We introduce a novel metric that takes into account both energy savings and acceptance rates. We also identify a new simpler heuristic that minimizes energy use by routing source–destination demands over paths that contain established links and require the fewest number of new links. Our evaluation of two offline and four online LSP establishment methods over the Abilene and AT&T topologies with random LSP setup requests show that energy savings beyond 20 % are achievable with LSP acceptance rates above 90 %.

Green traffic engineering (TE) solutions play a central role in minimizing the energy expenditure of a network where they seek the minimal links/routers/switches required to support a given traffic demand. A key limitation, however, is that they are not designed to be robust against random traffic demands. To this end, this paper reports the first robust, green TE solution, called Green-PolyH, that considers demands defined by a given polyhedral set. Advantageously, Green-PolyH ensures all such demands do not cause the utilization of links to exceed a given threshold. Our experiments over well-known topologies show that savings above 80% are achievable whilst remaining robust to traffic changes.

We study the problem of deriving the shortest schedule required to forward both uplink and downlink packets in wireless mesh networks (WMNs) with full duplex capability. We derive the theoretical upper and lower bound of the schedule, and propose a novel centralized algorithm, called UDMAC, that greedily generates a schedule on a path-by-path basis and ensures nodes have sufficient antennas for transmissions, receptions, and interference cancellation. Our results show that UDMAC outperforms a state-of-the-art half-duplex scheduling algorithm by at least 60% in terms of schedule length.

A key problem in Rechargeable Wireless Sensor Networks (WSNs) is determining the maximum amount of data that can be collected by a sink over a given time period. This maximum is constrained by link capacity and critically, by the available energy at each node. In this paper, we consider a novel approach to increase the maximum flow rate by exploiting recent advances in Wireless Power Transfer (WPT). Specifically, we deploy a finite number of WPT capable rovers next to bottleneck sensor nodes with the aim to increase the max flow rate of a WSN. We formulate a Mixed Integer Linear Programming (MILP) to determine the routing and the set of sensor nodes that are to be “upgraded” in order to achieve the maximum flow rate. We also outline a novel heuristic, called Path, to place rovers in large scale WSNs. Our results show it is able to attain on average 85.9% of the optimal flow rate.

The personalized broadcast problem calls for a link schedule with the shortest makespan or slots to deliver all data located at a gateway destined for nodes in a multi-hop wireless network. In this paper, we address this fundamental problem with consideration for the multiple transmit or receive capability of nodes as well as their ability to boost the capacity of a link via spatial multiplexing or multiple radios. We derive new makespan bounds for arbitrary tree topologies and propose a new link scheduler called Algo-PB to generate a personalised broadcast schedule with minimal schedule length. Simulation results show that the schedule length generated by Algo-PB outperforms state-of-the-art algorithms by at most 20% and the difference between Algo-PB and the theoretical lower bound is at most 10%.

Recently, researchers have created Wireless Mesh Networks (WMNs) where routers have multiple transmit (Tx) or receive (Rx) capability. A fundamental problem in such WMNs is deriving a transmission schedule that yields minimal end-to-end delays. In this paper, we approach this problem via joint routing and link scheduling. Specifically, we consider twofundamental issues that influence end-to-end delays: super frame length and transmission slot order. We propose two algorithms: JRS-Multi-DEC and JRS-BIP, where the former uses a novel metric to minimize the load of each link whilst the latter uses a binary integer program solver. Both algorithms have the similar aim of minimizing overall delay and to re-order slots such that packets are forwarded quickly along their path. Numerical results show that our algorithms can reduce average delay by approximately 50% as compared to a non joint routing and scheduling algorithm.

Network robustness and throughput can be improved by routing each demand d via two disjoint paths (2DP). However, 2DP routing increases energy usage while providing lower linkutilization and redundancy. In this paper, we address an NP-complete problem, called 2DP-EAR, that aims to switch off redundant nodes and links while guaranteeing two constraints:traffic demands must be afforded 2DP, and maximum link utilization. We design an efficient heuristic, called 2DP by Nodes First (2DP-NF). We have extensively evaluated the performance of 2DP-NF on both real and/or synthetic topologies and traffic demands. As compared to using Shortest Path routing, on the GÉANT network, 2DP-NF can save around 20% energy by switching off links only with negligible effects on path delays and link utilization, even for MLU below 30%. Furthermore, 2DP-NF can obtain 39.7% power savings by switching off both nodes and links on the GÉANT network.

Recently, researchers have developed Wireless Mesh Networks (WMNs) where each router is capable of performing multiple transmissions or receptions concurrently; aka Multi Tx-Rx (MTR) WMNs. Consequently, each node is able to transmit (Tx) or receive (Rx) to/from its neighbors simultaneously. A fundamental problem in such WMNs is to derive a transmission schedule with minimal superframe length to maximize network capacity and minimize end-to-end delays. Unfortunately, deriving a minimal superframe length is equivalent to solving the NP-complete, MAX-CUT problem. To this end, there are a number of centralized schedulers, but only but only one distributed scheduler, called JazzyMAC. Henceforth, in this paper, we add to the state-of-the-art by proposing Algo-d, a novel distributed scheduler that solves the MAX-CUT problem using only local information. Experiment results show Algo-d generates superframes that are 37.5% shorter and it activates 264% more links as compared to JazzyMAC. Lastly, as compared to centralized schedulers, Algo-d schedules 50% more links than Algo-1 and at most 7% fewer links than Algo-2.

Green networking techniques aim to shut down the least utilized links and/or routers during off-peaks hours. In this paper, we show that such techniques negatively impact the operation of the Border Gateway Protocol (BGP). We quantify the impacts of two representative green approaches: (i) GAES, a green technique that modifies link weights, and (ii) ESOL, a green technique that does not involve link weights adjustments. Experiments over the Abilene, AT&T, GEANT and SURFnet topologies show that when using GAES, routing changes and the proportion of rerouted traffic, both of which affect BGP, are in the order of 108% and 141% greater than ESOL. Therefore, we propose Hot Potato Low UtiliZation (HotPLUZ), a greenapproach that takes hot-potato routing into account. HotPLUZ reroutes traffic from lowly utilized links and aggregate said traffic onto highly utilized links, whilst minimizing any changes to the corresponding egress router of a given destination. In addition, HotPLUZ considers link utilization in order to avoid packet loss and high latencies. Our experimental results indicate an overall saving of up to 21% under low network load.