Summary Recently, barrier‐coverage in wireless sensor networks is a critical issue because it can be used for various applications (e.g., intrusion detection and border protection). Many existing works for barrier‐coverage assume that an intruder penetrates through two opposite sides such as from top to bottom or from bottom to top and focus on constructing barriers to detect those penetrations. However, in many practical scenarios, it should be desirable to detect an intruder that enters the area of interest through any of its sides and passes through any other of its sides. In this paper, we introduce a new barrier‐coverage problem whose goal is maximizing the network lifetime such that any penetration variation of the attacker is guaranteed to be detected. In order to solve the problem, we create a new type of sensor barriers, which is referred asreinforced barriers, that can sense any movement variation of the intruder. Also, we propose four different approaches to construct reinforced barriers from a given layout of sensors and we compare their relative performances for maximum number of reinforced barriers through extensive simulations by various scenarios. Copyright © 2016 John Wiley & Sons, Ltd.

Rate-guaranteed scheduling protocols ensure that packets from each input flow are forwarded at a rate no less than the rate reserved by the flow. WFQ is the classical example. Many of these protocols, including WFQ, provide both rate and fairness guarantees. In particular, they distribute unused capacity among among the flows in proportion to the reserved rate of each flow. In earlier work, we presented a scheduling algorithm that distributes unused capacity to flows whose reserved rate is the least. However, the per-packet complexity of this algorithm, known as rate-equalization fairness, is linear in the number of flows. Here, we present an algorithm that approximates rate-equalization fairness, but with only logarithmic complexity per packet.

Wireless sensor and actor networks (WSANs) are composed of static sensor nodes and mobile actor nodes. We assume actors have a random initial location in the two-dimensional sensing area. The objective is to move each actor to a location such that every sensor node is within a bounded number of hops from some actor. Because sensor nodes have limited energy, the new actor locations are chosen as to minimize the transmission range required from the sensor nodes. However, actors also have a limited (although larger) power supply, and their movement depletes their resources. It follows that by carefully choosing the new actor locations, the total actor movement can be minimized. In this paper, we study the trade-off between minimizing sensor transmission radius and minimizing actor movement. Due to the complexity of the problem, we introduce an optimal ILP formulation, and compare its results against a proposed heuristic. For the ILP solution to be feasible, we introduce a finite set of potential actor positions such that an optimal solution is guaranteed to be found within this set.

Scheduling protocols that provide both rate and fairness guarantees, such as Weighted Fair Queuing, distribute the unused capacity among the flows in proportion to the reserved rate of the flows. Thus, flows whose reserved rate is the largest will receive a larger share of the unused capacity. We present a scheduling algorithm that first distributes unused capacity to those flows whose reserved rate is the least. This allocation continues until the flows with least reserved rate and the flows with the next-to-least reserved rate are given the same capacity. If enough unused capacity is available, all flows will receive the same capacity, and the scheduler will simply behave like Fair Queuing.

Wireless sensor and actor networks (WSANs) consist of fixed sensor nodes and mobile actor nodes. Data is generated at the sensor nodes, and collected at the more powerful actor nodes. We consider the problem of finding the location for K actor nodes such that every sensor node is within d-hop from an actor node, where K and d are parameters of the problem. Our approach distinguishes itself in obtaining the minimum transmission radius necessary for such coverage to be possible. We provide an exact solution by via an integer-linear- programming formulation (ILP), and evaluate two heuristic approaches.

We consider the design of wireless sensor and actor networks. Sensors are network nodes with a fixed location and limited transmission power. Actors are mobile nodes that may relocate their position to provide coverage to the sensor nodes. We consider the problem of relocating K actors from initial random locations to locations where every sensor node is able to communicate directly with at least one actor node. The new actor locations are chosen to minimize the transmission power that is necessary for the sensor nodes. Also, the pairing of actors to their new locations is such that the cost of relocating the actors is minimized.

Routing is one of the most challenging development issues in delay-tolerant networks (DTNs) because of lack of continuous connection. Existing routing schemes for DTNs provide best effort service, but are unable to optimize QoS and support message priority. In this paper, we present a Look-Ahead Routing and Message Scheduling approach (ALARMS) which exploits more accurate knowledge about various parameters regarding routing to achieve better QoS in the DTN. We assume a variation of the well-known ferry model, in which there are ferry nodes moving along pre-defined routes to exchange messages with the gateway node of each region on the route and also pass to the gateway nodes look-ahead routing information about when it will arrive at each gateway node on the route in the next two rounds and how long it will stay. The gateway nodes use this information to estimate the delivery delay of each message when being delivered by different ferries, and schedule the message to be delivered by the ferry which arrives earliest at the destination. Simulation results show that ALARMS outperforms three existing routing protocols: epidemic routing, spray-and-wait, and spray-and-focus, in terms of delay time, delivery ratio, and overhead. We also discuss three enhancement strategies on ALARMS and how ALARMS can support message priority.

Two techniques have been proposed in the literature to improve the scalability of QoS scheduling in the core of the Internet: flow aggregation and dynamic packet scheduling (DPS). These techniques reduce or eliminate the amount of state maintained by each router in a core network. Flow aggregation combines multiple individual flows into a single aggregate flow (and thus reducing the per-flow state of the routers), while DPS stores in the packet header all the information required to compute the deadline of the packet at each intermediate router (and thus maintains no per-flow state).

We present a protocol for maintaining a spanning tree that is maximal with respect to any given (bounded and monotonic) routing metric. This protocol has two interesting adaptive properties. First, the protocol is stabilizing: starting from any state, the protocol stabilizes to a state where a maximal tree is present. Second, contrary to other approaches, the protocol converges in O(L * deg) time, where deg is the node degree in the network and L the longest network path. This is achieved without nodes assuming an upper bound on L.

Flow aggregation has been proposed as a technique to improve the scalability of QoS scheduling in the core of the Internet, by reducing the amount of per-flow state necessary at a router. This is accomplished by aggregating into a single flow multiple flows that share part of the same path to the destination. In its simplest form, flow aggregation is inherently non-work- conserving, that is, it may temporarily leave the output channel idle even though there are still packets to be forwarded. Work-conserving variations of flow aggregation are more desirable, because they allow flows to temporarily exceed their reserved rate and take advantage of bandwidth unused by other flows. This, however, requires a per-hop delay proportional to the rate reserved for the aggregate flow. Thus, if a lower delay is desired, the aggregate flow must reserve from the network a data rate that is greater than its true rate. In this paper, we explore the conditions under which work- conserving flow aggregation can be performed with rate- independent delay. That is, the aggregate flow is able to choose a per-hop delay that is independent of the data rate it reserved from the network. The price to be paid for this flexibility, however, is a restriction in the choice of packet size and data rates of its constituent flows.

In the effort of reducing or eliminating per-flow state at routers, hence making QoS schedulers scalable in the core Internet, flow aggregation outperforms dynamic packet state by providing better end-to-end delay guarantee. Work-conserving flow aggregation (WCFA) has the advantage of gaining work-conserving property at the cost of an extra per-hop delay. Most research on work-conserving flow aggregation so far has focused on a single level of flow aggregation within a single aggregation domain. In this paper, we investigate the per-hop behavior of flow aggregation over multiple aggregation domains. Moreover, in each aggregation domain, multiple aggregation levels are considered. We show that the aggregating cost happens only once in each aggregation domain over all aggregation levels, and higher level of flow aggregation provides lower per-hop delay guarantee.

The Internet traditionally provides best effort service to all applications. While elastic applications are satisfied by this service, inelastic applications such as interactive audio and video suffer from end-to-end delay guarantees. Although guaranteed rate schedulers were developed to provide such guarantees, their scalability has been a concern because they maintain per-flow state. In an effort to reduce per-flow state, two methods have been proposed: stateless core networks and flow aggregation. Stateless core networks require no per-flow state at the routers, while flow aggregation maintains state for a small number of aggregate flows. Although flow aggregation maintains more state, it provides a lower end-to-end delay bound than stateless core networks. The original proposals of these two techniques did not provide guaranteed throughput, that is, flows could be temporarily denied service if they exceeded their reserved rates at earlier times. Recently, guaranteed throughput has been incorporated into the stateless core model through the reuse of deadlines. This is similar to the deadline reuse found in earlier stateful protocols that provide guaranteed throughput. In this paper, we propose adding deadline reuse to flow aggregation networks. In this way, guaranteed throughput can be achieved while maintaining a lower end-to-end delay bound. In addition, we revise the deadline reuse method for stateless core networks.

In order to improve the scalability of scheduling protocols with bounded end-to-end delay, much effort has focused on reducing the amount of per-flow state at routers. One technique to reduce this state is flow aggregation, in which multiple individual flows are aggregated into a single aggregate flow. In addition to reducing per-flow state, flow aggregation has the advantage of a per-hop delay that is inversely proportional to the rate of the aggregate flow, while in the case of no aggregation, the per-hop delay is inversely proportional to the (smaller) rate of the individual flow. Flow aggregation in general is non-work-conserving. Recently, a work-conserving flow aggregation technique has been proposed. However, it has the disadvantage that the end-to-end delay of an individual flow is related to the burstiness of other flows sharing its aggregate flow. Here, we show how work-conserving flow aggregation may be performed without this drawback, that is, the end-to-end delay of an individual flow is independent of the burstiness of other flows.

The Internet is composed of a collection of interconnected and self-administered autonomous systems (ASms). Inter-AS routing is accomplished by having neighboring ASms exchange reachability information via the border gateway protocol. An AS is said to be a transit AS if it allows traffic from other ASms to cross through it. In particular, transit ASms provide transit services for traffic between customer and provider ASms. In this paper, we focus on maximizing the utilization of resources at transit ASms. In particular, inter-AS links have been shown to be a bottleneck. To make better use of inter-AS links, we consider problem of balancing the load among inter-AS links. We call that problem as balanced-flow assignment problem (B-FAPM). We show that the B-FAPM is NP-hard, and thus, likely intractable. We then present a heuristic protocol, the balanced-flow assignment protocol (B-FAPL), that balances the out-bound traffic loads on inter-AS links. Our solution is distributed and uses random matching to assign in-bound flows to out-bind inter-AS links.

The stable-paths problem is an abstraction of the basic functionality of the Internet's BGP (border gateway protocol) routing protocol. This abstraction has received considerable attention, due to the instabilities observed in BGP. In this abstraction, each node informs its neighboring nodes of its current path to the destination node. From the paths received from its neighbors, each node chooses the best path according to some locally chosen routing policy. However, since routing policies are chosen locally, conflicts may occur between nodes, resulting in unstable behavior. Current solutions either require expensive path histories, or prevent nodes from locally choosing their routing policy. We present a solution with small overhead, and furthermore, each node has the freedom to choose any routing policy. However, to avoid instabilities, the possibility of divergence is measured using an efficient cost metric exchanged between nodes. If the cost metric indicates that divergence is occurring, steps are taken to ensure convergence.

BGP routers within an Autonomous System (AS) exchange their inter-AS routing information via the internal Border Gateway Protocol (iBGP). Within an AS, every BGP router needs to maintain an iBGP peering session with every border BGP router. This peering scheme fails to scale due to the large number of iBGP peering sessions required. Current solutions to this scalability limitation divide the AS into clusters, with a route reflector acting us a representative of the cluster. Clustering, however, introduces routing anomalies. Furthermore, BGP also uses a Multi-Exit Discriminator (MED) to differentiate multiple links connecting the same pair of AS'ms. However, clustering in combination with the use of MED values further aggravates routing anomalies. In this paper, we propose a complete solution that solves both clustering induced anomalies and MED induced anomalies in iBGP. Our solution requires multiple path disseminations between route reflectors and selective single-path dissemination from each route reflector to its client.

The token protocols of FDDI and FDDI-M support both synchronous and asynchronous traffic. However, FDDI suffers from a token-lateness problem, and FDDI-M may starve asynchronous traffic. To remove these two weaknesses, we propose the on-time timed-token protocol. Its main feature is the addition of information to the token that allows a station to determine whether the early arrival of a token is due to unused synchronous bandwidth or unused asynchronous bandwidth. We present a synchronous bandwidth allocation scheme for this protocol, and comparison is made against FDDI and FDDI-M.

Wireless computer networks have properties that differ significantly from traditional wireline networks. One prominent difference is the presence of unidirectional channels. That is, it may be possible for a computer p to send a message to a neighboring computer q, but it may not be possible for computer q to send a message to computer p. This introduces significant changes in routing protocols. In particular, routing protocols that tolerate unidirectional links incur an O(N/sup 2/) message overhead between neighboring nodes, where N is the number of nodes in the network. This is significantly higher than the typical O(N) message overhead in some traditional routing protocols. We present a protocol with an O(N) message overhead even in the presence of unidirectional links. This low overhead comes at the price of not always finding the optimum path. However, the protocol is guaranteed to always find a path between each pair of nodes. Furthermore, the cost of this path is guaranteed not to exceed the cost of the optimal bidirectional path between the nodes.

We investigate how quality of service may be guaranteed to a flow of packets in the presence of flow aggregation. For efficiency, multiple flows, known as the constituent flows, are merged together resulting in a single aggregate flow. After the network node where the aggregation occurs, packet schedulers are aware of the aggregate flow, but are unaware of its constituent flows. In spite of this, we show that quality of service may be guaranteed to the constituent flows, provided the aggregation is performed fairly. When the delay bound of a flow is de-coupled from the flow's reserved rate, flow aggregation preserves the delay bound. When the delay bound of a flow is coupled to the flow's reserved rate, flow aggregation preserves, and in some cases improves, the delay bound.

We consider the problem of finding an optimum path from each node in the network to a destination node in the network. Typically, each edge in the network is assigned a weight value (e.g. bandwidth or delay), and a metric function (e.g. min or +) is applied consecutively to the edges in the path. The result is the metric value of the path. However, some metric functions have conflicts, and prevent all nodes from obtaining an optimum path simultaneously. Conditions to ensure that a metric function is conflict-free have been presented in the literature. In this study, we consider the more general problem where the optimality of the path is not a function of the edge weights but a function of the path itself. We therefore define a path ranking function, and give sufficient conditions for the ranking to be conflict free. Furthermore, a distributed algorithm is presented to obtain the optimum path from each node to the destination.

Two approaches have been proposed to improve the quality of service provided by the Internet: integrated services and differentiated services. Integrated services requires per-flow state at each router On the other hand, differentiated services does not require per-flow state, but provides a lower level of quality of service. We present a protocol which provides quality of service similar to that provided by integrated services, but without maintaining per-flow state. To accomplish this, both the signaling protocol and the packet scheduling protocol must function without per-flow state. Our signaling protocol maintains only a constant amount of state at each router In addition, it is accurate, and it is resilient to process and link failures. Our scheduling protocol is a combination of the dynamic packet state technique and flow aggregation techniques. This approach combines the strengths of both techniques and eliminates their weaknesses. Furthermore, our approach is applicable across multiple domains.

We present a protocol for maintaining multiple paths to each destination in a network of processes. For each destination, each process in the network maintains a set of neighbors which are used as next-hops to reach the destination. This set is known as the successor set. Collectively, the successor sets from all processes in the network with respect to a given destination form a spanning, destination, and acyclic graph, whose only sink is the given destination. The protocol we present has two interesting properties. First the graph is maintained acyclic at all times, even though the successor set is dynamic. Second, the protocol tolerates all types of transient faults, even those which may not be detected. Therefore, if the protocol is started from an arbitrary initial state, it will converge to a normal operating state in which a spanning, directed, and acyclic graph is obtained and subsequently maintained.

Future computer networks are expected to carry bursty real-time traffic with stringent time-delay requirements. Popular shortest-path routing protocols have the disadvantage of causing bottlenecks due to their single-path routing. We propose a real-time routing and scheduling scheme that randomly distributes the traffic load over all available paths to the destination for load balancing and transmits the packet with the most urgency ahead of the other packets at a switch in a packet-switched network with two objectives-minimizing packet loss in the network and maximizing network throughput. Our scheme consists of two components, a routing algorithm and a scheduling algorithm. The routing algorithm randomly distributes data packets over the whole network to remove bottlenecks caused by the single-path routing of shortest-path routing protocols. The end-to-end delay is bounded by the scheduler, which uses a least-laxity scheduling algorithm. Our simulation results indicate that the proposed scheme decreases the number of packets dropped due to deadline miss and due to buffer overflow in transit in a network and increases network throughput. A desirable by-product is that the traffic load on the network tends to get evenly distributed.

The purpose of routing protocols in a computer network is to maximize network throughput. Popular shortest-path routing protocols have the disadvantage of causing bottlenecks due to their single-path routing. That is, the shortest path between a source and a destination may become highly congested even when many other paths have low utilization. In this paper, we propose a routing scheme for hierarchically structured computer networks such as the Internet. The new hierarchical routing algorithm, which we call hierarchical load-balanced routing (HLBR), is based on distance-vector routing algorithms. HLBR randomly balances traffic load over the whole network; therefore, it removes bottlenecks and increases network throughput. For each data message to be sent from a source s to a destination d, the proposed routing protocol chooses randomly each of three intermediate nodes from a selected set of network nodes, and routes the data message along a path from s through the three intermediate nodes to d. This increases the effective bandwidth between each pair of nodes.

We investigate the preservation of quality of service guarantees to a flow of packets in the presence of flow aggregation. For efficiency, multiple flows, known as the constituent flows, are merged together resulting in a single aggregate flow. Packet schedulers located after the network point where the aggregation occurred are aware of the aggregate flow, but are unaware of its constituent flows. In spite of this, we show that quality of service guarantees may still be offered to the constituent flows provided the aggregation is performed fairly. In earlier work, we showed that the end-to-end delay is preserved (and in some cases improved) under flow aggregation, when the packet delay is coupled with the reserved rate of the flow. We go beyond these results by showing that, even when the delay is de-coupled from the reserved rate, the end-to-end delay is preserved under flow aggregation.

We investigate the preservation of quality of service guarantees to a flow of packets in the presence of flow aggregation. In flow aggregation, multiple flows, known as the constituent flows, are merged together resulting in a single aggregate flow. Packet schedulers located after the network point where the aggregation occurred are aware of the aggregate flow, but are unaware of its constituent flows. In spite of this, we show that quality of service may be guaranteed to the constituent flows provided the aggregation is performed fairly. Furthermore, contrary to intuition, the quality of service guarantees of a flow may be better under flow aggregation than in the case where no aggregation is performed.

We present a scheduling protocol, called time-shift scheduling, to forward packets from multiple input flows to a single output channel. Each input flow is guaranteed a predetermined packet rate and an upper bound on packet delay. The protocol is an improvement over existing protocols because it satisfies the properties of rate-proportional delay, fairness, and efficiency, while existing protocols fail to satisfy at least one of these properties. In time-shift scheduling each flow is assigned an increasing timestamp, and the packet chosen for transmission is taken from the flow with the least timestamp. The protocol features the novel technique of time shifting, in which the scheduler's real-time clock is adjusted to prevent flow timestamps from increasing faster than the real-time clock. This bounds the difference between any pair of flow timestamps, thus ensuring the fair scheduling of flows.

The distance vector routing protocol satisfies the following property. If this protocol is used to route a sequence of data messages from a source to a destination, then these data messages will follow the same shortest-distance path from the source to the destination. In this paper, we show how to modify this protocol, without adding new messages, in order to satisfy the following load balancing property. If the modified protocol is used to route a sequence of data messages from a source to a destination, then these messages will be uniformly distributed over all k-monotonic paths from the source to the destination, i.e., over all paths whose distance to the destination never increases at each hop, and may remain constant in at most k hops. In particular, by choosing k to be zero, the modified protocol distributes the data messages over all shortest-distance paths from the source to the destination.

We present a family of group routing protocols for a network of processes. The task of these protocols is to route data messages to each member of a process group. To this end, a tree of processes is constructed in the network, ensuring that each group member is included in the tree. No processing or storage overhead is required for processes not included in the tree. The overhead of processes in the tree consists solely of the periodic exchange of request/reply messages with their parent. To choose the processes that constitute the tree, we take advantage of the existing unicast routing protocol in the network. In addition, our family of group routing protocols distinguishes itself from other group routing protocols in three ways. First, the protocols are proven correct. Second, the protocols preserve the integrity of the group tree as it adapts to changes in the unicast routing tables, even in the presence of temporary unicast routing loops. Third, data messages are propagated along the entire group tree, even while the tree adapts to changes in the unicast routing tables.

We develop a simple theory of flows to study the flow of data in real-time computing networks. Flow theory is based on discrete and nondeterministic mathematics, rather than the customary continuous or probabilistic mathematics. The theory features two types of flows: smooth and uniform, and eight types of flow operators. We prove that, if the input flow to any of these operators is smooth or uniform, then both the internal buffer and delay of that operator are bounded. Linear networks of flow operators are introduced, and their internal buffers and delays are derived from the internal buffers and delays of their constituent operators. We extend flow theory so that it can be used in analyzing cyclic networks and networks of multiflows. Since many rate-reservation protocols can be represented as linear networks of flow operators, we use flow theory to prove that a number of these protocols (stop-and-go, hierarchical round-robin, weighted fair queueing, self-clocking fair queueing, and virtual clock) require bounded buffering and introduce bounded delay.

We present a group routing protocol for a network of processes. The task of the protocol is to route data messages to each member of a process group. To this end, a tree of processes is constructed in the network, ensuring each group member is included in the tree. To build this tree, the group routing protocol relies upon the unicast routing tables of each process. Thus, group routing is a composition of a unicast routing protocol, whose detailed behavior is unknown but its basic properties are given, and a protocol that builds a group tree based upon the unicast routing tables. The design of the group routing protocol is presented in three steps. First, a basic group routing protocol is presented and proven correct. Then, the protocol is refined twice, strengthening its properties with each refinement. The final protocol has the property of adapting the group tree to changes in the unicast routing tables without compromising the integrity of the group tree, even in the presence of unicast routing loops.

We present a scheduling protocol, called time-shift scheduling, to forward data packets from multiple input flows to a single output channel. Each input flow is guaranteed a predetermined forwarding rate and an upper bound on packet delay. The protocol is an improvement over existing protocols because it satisfies the properties of low delay, fairness, and efficiency, while existing protocols fail to satisfy at least one of these properties. In time-shift scheduling, each flow is assigned an increasing timestamp, and the packet chosen for transmission is taken from the flow with the least timestamp. The protocol features the novel technique of time shifting, in which the scheduler's real-time clock is adjusted to prevent flow timestamps from increasing faster than the real-time clock. This bounds the difference between any pair of flow timestamps, thus ensuring the fair scheduling of flows.

We present a new acknowledgment strategy to improve the performance of TCP sessions that originate or terminate in noisy wireless networks for mobile computers. This acknowledgment strategy allows the TCP source to distinguish between losses due to congestion and losses due to corruption. With this distinction, the source can reduce its sending rate when congestion occurs, and quickly retransmit when corruption occurs. Without this distinction, TCP throughput is shown to suffer significantly over a path with a large bandwidth-delay product. The strategy is also appropriate for dealing with losses due to hand-offs of a mobile computer from one wireless cell to another.

In the past decade the United States telecommunications industry has been under much scrutiny as a result of a number of major network outages. These outages, which affected millions of customers, ranged from power and fire related problems to a software error affecting the common channel signaling network. The industry reacted promptly and positively. This paper discusses the actions of the FCC's Network Reliability Council (NRC), including the technical papers produced by this group and its newly re-chartered objectives, as well as the Alliance for Telecommunications Industry Solutions (ATIS) Network Reliability Steering Committee (NRSC) to address this challenge. The NRSC's findings are discussed in detail, including the results of its quarterly and annual reports, which identify trends, areas of concern, and recommended steps to prevent or mitigate outages in the future.

The authors develop a simple theory of flows and show how to use this theory in verifying rate-reservation protocols in computing networks. The theory is based on discrete and nondeterministic mathematics, rather than the customary continuous or probabilistic mathematics. The theory features two types of flows, smooth and uniform, and four types of flow operators, limiters, compactors, expanders, and filters. Many rate-reservation protocols can be represented as linear networks of these flow operators. It is proved that, if the input flow to any of these networks is smooth or uniform, then the internal buffer and the delay in each operator in the network are bounded. This method is used to prove that a number of rate-reservation protocols (for example, stop-and-go, hierarchical round-robin, fair queuing and virtual clock) require bounded buffering and introduce bounded delay.>