We propose a MAC protocol for use in multihop wireless networks that deploy an underlying UWB (ultra wide band)-based physical layer. We consider a multiband approach to better utilize the available spectrum, where each transmitter sends longer pulses in one of many narrower frequency bands. The motivation comes from the observation that, in the absence of a sophisticated equalizer, the size of a slot for transmitting a UWB pulse is typically dictated by the delay spread of the channel. Therefore, using a wider frequency band to shorten the transmission time for each pulse does not increase the data rate in proportion to the available bandwidth. Our approach allows data transmissions to be contiguous and practically interference free, and, thus, highly efficient. For practicality, we ensure the conformance of our approach to FCC-imposed emission limits. We evaluate our approach via extensive simulations, and our results demonstrate the significant advantages of our approach over single-band solutions: the throughput increases significantly and the number of collisions decreases considerably. Finally, we analyze the behavior of our MAC protocol in a single-hop setting in terms of its efficiency in utilizing the multiple bands

We consider the path-determination problem in Internet core routers that distribute flows across alternate paths leading to the same destination. We assume that the remainder of the network transit delay beyond this router are different for the two paths, so a good routing policy can reduce the end-to-end delay by favoring the faster path. Thus, we propose and solve the optimal path-determination problem for a router, which minimizes the average network transit delay for a flow by dynamically assigning each packet to one of the available output ports based on their respective instantaneous queue lengths and on the average network transit delay for the associated path. We assume that all outgoing link speeds at the router are equal, but we generalize the model to allow each output port to serve a link group (such as an optical fiber using WDM) that consists of multiple physical channels running in parallel. By formulating path-selection as a Markov Decision Problem, we show that the optimal algorithm is a threshold-type policy that we call JSQ + b.

Efficient routing protocols can provide significant benefits to mobile ad hoc networks, in terms of both performance and reliability. Many routing protocols for such networks have been proposed so far. Amongst the most popular ones are dynamic source routing (DSR), ad hoc on-demand distance vector (AODV), temporally-ordered routing algorithm (TORA) and location-aided routing (LAR). Despite the popularity of those protocols, research efforts have not focused in evaluating their performance when applied to large-scale wireless networks. Such networks are comprised of hundreds of nodes, connected via long routes. This greatly affects the network efficiency, since it necessitates frequent exchange of routing information. In this paper we present our observations regarding the behavior of the above protocols, in large-scale mobile ad hoc networks (MANETs). We consider wireless mobile terminals spread over a large geographical area, and we perform extensive simulations, using the QualNet and NS-2 simulators. The results of the simulations yield some interesting conclusions: AODV suffers in terms of packet delivery fraction (PDF) but scales very well in terms of end-to-end delay. DSR on the other hand scales well in terms of packet delivery fraction but suffers an important increase of end-to-end delay, as compared to its performance achieved in small-scale topologies. Also, the effect of maximum connections is severe on TORA, which seems unable to route large amounts of traffic. LAR, seems to scale very well, in terms of all metrics employed

Abstract Ultra wide band (UWB) technology offers a promising high capacity solution for short‐range wireless ad hoc networks, as in home networks or in wearable ad hoc networks. In this paper, we propose a novel multi‐band MAC protocol for use in small ad hoc networks that deploy an underlying UWB based physical layer. In our approach, we divide the available UWB bandwidth into multiple simultaneously usable bands. In the absence of a sophisticated equalizer, the size of a slot for transmitting a UWB pulse is typically dictated by thedelay spreadof the channel. Therefore, using a wider frequency band to shorten the transmission time for each pulse does not increase the data rate in proportion to the available bandwidth. A multi‐band approach that uses a plurality of bands that adhere to FCC specifications, with slightly elongated pulse durations, provides a solution that can effectively utilize the UWB spectrum. Our approach is based on the idea of conflict resolution using binary ‘something’/‘nothing’ feedback, which has not been widely studied in wireless and specifically in UWB networks. Our protocol unites binary conflict resolution and multi‐band utilization to effectively utilize the available bandwidth. To ensure that our proposed approach is tightly knit with the underlying physical layer, we discuss physical–layer dependencies and the conformance to FCC‐imposed emission limits. We evaluate our approach via extensive simulations. Our simulation results demonstrate the significant advantages of our approach over single‐band solutions: the throughput increases significantly, and the number of collisions decreases considerably. Copyright © 2006 John Wiley & Sons, Ltd.

Like it or not, unsolicited bulk commercial Email (aka "spam") has become a regular menu item on the Internet information diet. Every day, millions of people find their Email in-boxes clogged with vast quantities of spam. Moreover, the daily replenishment of all those in-boxes with new spam also consumes significant amount of network bandwidth. Dealing with spam is like fighting a battle against a large army; the most effective approach is to employ multiple tactics. However, almost all spam control methods that have been proposed and implemented follow the same basic theme of establishing a "front line" of defense at the end-user level. Thus, in this paper we propose a method for blocking the supply lines. More specifically, we identify spam at the router level and control it via rate limiting. Spam identification is done in two phases. In the first phase, we identify the bulk stream of Email messages and in second phase we apply Bayesian classifier to identify whether it is a spam. If a bulk Email stream is classified as a spam then we rate limit it (e.g. no more than one copy per minute). Our proposed method exploits the short timespan delivery and bulkiness of spam Emails. We use publicly available spam corpus to evaluate our proposed scheme and in the other set of experiments, we work on one month sanitized log of our department Emails to provide the representative results.

Abstract — Ultra Wide Band (UWB) technology offers a promising high capacity solution for wireless networks with short-range links. However, MAC and higher-layer ad hoc network protocols that exploit the UWB technology are yet to mature. In this paper, we propose a MAC protocol for use in multi-hop wireless networks that deploy an underlying UWB based physical layer. We adopt a multi-band approach wherein we divide the available UWB bandwidth into multiple simultaneously usable bands. The motivation comes from the following observation: in the absence of a sophisticated equalizer, the size of a slot for transmitting a UWB pulse is typically dictated by the delay spread of the channel. Therefore, using a wider frequency band to shorten the transmission time for each pulse may not increase the data rate in proportion to the available bandwidth. Thus, we consider a multi-band approach to better utilize the available spectrum, where each transmitter sends longer pulses in one of many narrower frequency bands. Unlike previous single hopped schemes that rely on timehopping, our approach allows data transmissions to be contiguous, and thus, highly efficient. The approach also ensures that data communications are practically interference free and are only subject to thermal noise effects. To ensure that our proposed approach is tightly knit with the underlying physical layer, we discuss physical-layer dependencies and the conformance of our approach to FCC-imposed emission limits. We evaluate our approach via extensive simulations. Our simulation results demonstrate the significant advantages of our approach over single-band solutions: the throughput increases significantly, and the number of collisions decreases considerably.

Since the identification of long-range dependence in network traffic ten years ago, its consistent appearance across numerous measurement studies has largely discredited Poisson-based models. However, since that original data set was collected, both link speeds and the number of Internet-connected hosts have increased by more than three orders of magnitude. Thus, we now revisit the Poisson assumption, by studying a combination of historical traces and new measurements obtained from a major backbone link belonging to a Tier 1 ISP. We show that unlike the older data sets, current network traffic can be well represented by the Poisson model for sub-second time scales. At multisecond scales, we find a distinctive piecewise-linear nonstationarity, together with evidence of long-range dependence. Combining our observations across both time scales leads to a time-dependent Poisson characterization of network traffic that, when viewed across very long time scales, exhibits the observed long-range dependence. This traffic characterization reconciliates the seemingly contradicting observations of Poisson and long-memory traffic characteristics. It also seems to be in general agreement with recent theoretical models for large-scale traffic aggregation

We propose an application-based secure VLAN (S-VLAN) architecture, which is one of the infrastructure-based active security mechanisms, for switched LANs connected to the Internet. S-VLAN is suitable for hot spots, universities and enterprises LANs and can efficiently prevent insider security problems from interrupting secured applications.

We present a novel switched full-duplex LAN architecture which can greatly simplify the cabling requirements in areas that must support high port densities and/or are subject to frequent changes. Instead of providing a separate cable to connect each host to a dedicated port on a monolithic switch behind the wall, we emulate the shared bus topology from the early days of Ethernet by daisy-chaining a series of small network-powered "slave" bridge modules called Ethernet Splitters from a single port on the "master" switch. Our partitioned switch architecture enforces network privacy throughout the entire splitter chain, so no host can view any traffic belonging to another host. The splitters also authenticate the point of origin for every frame, independent of the value contained in its source address field thus providing the same level of security as a monolithic switch under the 802.1x port based access control protocol.

The full-duplex repeater (FDR) has previously been proposed as an alternative to half-duplex operation using CSMA/CD for controlling shared access to Gigabit Ethernet. In this paper, the basic FDR architecture is described and two extensions for traffic control are introduced. Using simulation methods, the performance of the Gigabit FDR is studied under different topologies and population sizes for a range of offered load. It is shown that the FDR provides a dramatic performance improvement over CSMA/CD (using both BEB and BLAM arbitration) at high load. The Gigabit FDR is also compared with switched Ethernet in the context of medical image retrieval. It is shown that for medical image retrieval, the performance of the Gigabit FDR is much better than 100/100 or 1000/100-Mbps switched Ethernet, and equivalent to 1000/1000-Mbps switched Ethernet for low levels of non-image background traffic.

We propose a new parallel topology discovery algorithm for irregular, mesh-connected networks with unidirectional links and wormhole routing. An algorithm of this type was developed for the ATOMIC high speed local area network to avoid the need for manually updating routing tables. Similar needs may arise in wireless networks where channels may be unidirectional because of limited transmission power, multipath, and similar effects. Like the ATOMIC topology discovery algorithm, our algorithm accumulates a map of the network at a distinguished node called the address consultant. However, our algorithm is much faster. In addition, our algorithm is more general, because it can correctly resolve topologies that contain multiply connected nodes. We implemented both algorithms in a concurrent simulation environment, and tested them on a variety of topologies.

In Gigabit Ethernet, the round-trip propagation delay can be much greater than the transmission time for a minimum length frame. The authors describe some changes to the Ethernet CSMA/CD medium access control algorithm that allow CSMA/CD to be used in this case. First, carrier extension is used to increase the slot time without requiring a corresponding increase in the minimum frame length. Second, frame bursting is introduced so that a host may transmit more than one frame without releasing control of the channel, in a manner that increases the efficiency for small frames without changing its one-frame-at-a-time service interface. Using simulation, they show that CSMA/CD with carrier extension and frame bursting operating on 1 Gb/s links provides a significant performance increase over 100 Mb/s fast Ethernet. These changes are being adopted by the IEEE 802.32 task force, which is currently defining the standard for Gigabit Ethernet.

A half duplex repeater is the cheapest method for connecting multiple hosts to an IEEE 802.3 Ethernet LAN. However, if we increase the data rate from 10 Mb/s Ethernet to 100 Mb/s Fast Ethernet, shared access via CSMA/CD becomes less efficient because of the resulting increase in size of the collision fragments. For example, in a typical star wired single repeater network with a diameter of 200 meters, upgrading from 10BASE-T to 100BASE-T increases the round trip delay from about 100 bit times to almost 500 bit times. Moreover, a further upgrade to 1000 Mb/s Gigabit Ethernet would increase the round trip delay to about 4000 bit times. We introduce a simple change to the handling of incoming signals at the repeater ports known as collision truncation, and show that it reduces the average duration of a collision by more than 50% for networks with large round trip delays. For the standard BEB Ethernet protocol operating at moderate load, collision truncation reduces the mean end to end network delay by more than 25% for 100 Mb/s Fast Ethernet and by more than 50% for 1000 Mb/s Gigabit Ethernet. For BLAM, collision truncation increases the maximum throughput by more than 10%, and reduces the mean end to end delay substantially under high load. Collision truncation requires no changes to the host network adapters, and its use is completely transparent to the hosts. The only behavioral change that is visible to the attached hosts is the illusion that the network diameter appears to have been reduced. The relative cost of adding collision truncation to a repeater is very small compared to upgrading to a frame level device, such as a bridge.

Since Gallager, Humblet and Spira first introduced the distributed Minimum Spanning Tree problem, many authors have suggested ways to enhance their basic algorithm to improve its performance. Most of these improved algorithms have even been shown to be very efficient in terms of reducing their worst-case communications and/or time complexity measures. In this paper, however, we take a different approach, basing our comparisons on measurements of the actual running times, numbers of messages sent, etc., when various algorithms are run on large numbers of test networks. We also propose the Distributed Information idea, that yields several new techniques for performance improvement. Simulation results show that contrary to the theoretical analysis, some of the techniques in the literature degrade the performance. Moreover, a simple technique that we propose seems to achieve the best time and message complexity among several algorithms tested.

Queue inferencing algorithms are used to derive estimates of queue lengths and/or customer waiting times from a priori information about the customer arrival process and the observed sequence of times at which each customer enters and leaves service. In this paper, we extend these techniques by decoupling the arrival time constraints from the customer departure times, which allows us to handle additional features like server vacations. We then show how these techniques can be used to monitor a single station in a polling system, or in a shared medium local area network such as Ethernet, token ring and FDDI. Using these results, passive, non-intrusive network monitoring tools could be developed to estimate waiting times and queue lengths for any host on the network by observing only the packet departure times from the nodes.

It is well known that the Ethernet medium access control protocol can cause significant short-term unfairness through a mechanism known as the Capture Effect, and that this unfairness condition is worst in heavily loaded Ethernets with a small number of active nodes. Recently, Ramakrishnan and Yang proposed Capture Avoidance Binary Exponential Backoff (CABEB) to provide 1-packet-per-turn round robin service in the important special case of a 2-node collision domain. In this paper, we introduce an equal time round-robin scheme, in which only one node needs to be modified. In our scheme, the modified node maintains a local copy of the attempts counter of the other node. It uses this information to trigger switching its medium access policy between the two extremes of aggressively persistent and completely passive. As a result, the modified node can control the actions of the other node in such a way that both enjoy fair, low delay, round-robin access to the shared channel. 1 Introductio...

In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree (MST) problems that achieved optimal time and message complexity through the introduction of several advanced features. In this paper, we show that there are some cases where his algorithm can create cycles or fail to achieve optimal time complexity. We then show how to modify the algorithm to avoid these problems, and demonstrate both the correctness and optimality of the revised algorithm. 1 Introduction Given an undirected graph G with N nodes and E edges, with weights assigned to each edge, we want to find a spanning tree for which the combined weight of all its edges is minimized, denoted an MST in the sequel. Furthermore, we want to use a distributed algorithm to find that MST by placing a processor at each node and treating each edge as a bidirectional and error-free communication channel, over which the nodes can exchange messages among themselves. We assume that ini...

We consider the problem of allocating bandwidth fairly to each node in a shared, unidirectional bus network. We focus on the p/sub i/ persistent protocol, since these are open loop policies designed to operate well in high speed networks, which have a very large bandwidth-delay product and feedback in the upstream direction is not available in a timely manner. First, we introduce an improvement to the basic p/sub i/ persistent protocol, in which we replace random coin tosses with a deterministic counting algorithm, and thereby reduce the delays for all nodes for any given choice of {p/sub i/}. We then describe an exact method for calculating average packet delays and queue lengths in both the p/sub i/ persistent and our new deterministic n out of m protocols, based on the regenerative approach of Georgiades et al. (1987). These delay results, together with simulation measurements, show that both of these protocols still waste some bandwidth. After presenting a lower bounding argument to show that some wasted bandwidth is inevitable in all such distributed access control schemes, assuming a passive bus without feedback in the upstream direction, we show that changing the bus to unidirectional point-to-point links between (very simple) active interfaces at each node allows us to construct distributed access schemes that require no upstream feedback and are both work conserving and fair. To illustrate how this can be done, we introduce the p/sub i/ preemptive protocol, in which each node randomly inserts its own packets into the traffic arriving from upstream. We derive a simple and effective heuristic for calculating the preemption probability for each node, and use simulation to show how well it equalizes the delays at each node.>

The authors apply their queuing-theoretic delay analysis methodology to several variations of the FCFS 0.487 conflict resolution algorithm. In this approach, the main component of the packet delay is viewed as a queuing problem in which each window selected by the channel access algorithm is a customer requiring conflict resolution as its service. The authors' methodology is extended to handle all the features of the full FCFS 0.487 algorithm, including variable-size windows, arrival-time addressing (and hence true FCFS scheduling), and biased interval splitting. Some of these extensions involve approximations, but they make it possible to obtain the Laplace transform and moments of the packet delay. The authors also present an exact analysis for the three-cell algorithm, which is the 0.487 algorithm with a few modifications to satisfy the separability condition that reduces its capacity to 0.48. Comparisons made with other analyses (which provide bounds on the mean delay) and with extensive simulations show that the present results for both the mean and the variance of the packet delay are extremely accurate.>

The prioritized-virtual-time carrier sense multiple access (PVT-CSMA) protocol is a media access algorithm for cable- and radio-based local area networks that incorporates message-based priority classes. PVT-CSMA implements the head-of-the-line (HOL) priority queuing discipline, in which higher priority messages are always transmitted in preference to lower priority messages, and messages are transmitted first-come-first-served within each priority class. Expressions are obtained for both throughput as a function of offered load and mean delay as a function of throughput for asynchronous (unslotted) PVT-CSMA, which are easily solvable for any number of priority classes and for class-dependent message lengths, arrival rates, retransmission rates, etc. Specialization of the delay analysis to the single class case yields a substantial improvement over previous results for asynchronous virtual-time CSMA. Comparisons are made between this analysis and simulations of PVT-CSMA, and with simulations of Tobagi's P-CSMA (1982) protocol.>

Let p/sup 0/ be the minimum Bernoulli probability for which pairwise enabling is an optimal group testing algorithm under a Bernoulli arrival sequence model. In a previous work, it was shown that 0.430>

An access rule for token ring local-area networks called the helical-window token-ring protocol is introduced. It features the use of a window that limits the allowable messages a token-holding station can send. With the window, the operation of the protocol approaches that of a central single-server queuing system in the sense that messages are delivered in near first-come-first-served order on a network-wide basis. The introduction of the window also makes analysis of the networks tractable. Exact analytical formulas for the capacity and for the mean, variance, and moment-generating function of the message waiting time are derived. Numerical simulation is used to verify the results. Comparisons with continuous polling systems show that the imposition of the windowed access rule can lead to significant reductions in the delay variance (at the cost of increasing the mean system time) when the traffic is heavy and/or the message transmission time is large with respect to the walk time of the ring.>

Expressions are found for the throughput and delay performance of a Tree Conflict Resolution Algorithm that is used in a Local Area Network with carrier sensing (and possibly also collision detection). We assume that Massey's constant size window algorithm is used to control access to the channel, and that the resulting conflicts (if any) are resolved using a Capetanakis-like preorder traversal tree algorithm with d-ary splitting. We develop and solve functional equations for various performance metrics of the system and apply the “Moving Server” technique to calculate the main component of the delay. Our results compare very favorably with those for CSMA protocols, which are commonly used in Local Area Networks that support sensing.

Carrier sense multiple-access (CSMA) protocols are widely used in local area networks (LAN's) to control access to a shared communications channel such as a coaxial cable or radio frequency band. CSMA protocols are designed to exploit the property that the signal propagation time across the LAN is much smaller than the packet transmission time. Consequently, their performance depends on the exact timing of a sequence of asynchronous events originating at different points in the network. Previous models of CSMA protocols have not captured this essential space-time characteristic. Instead, the system has been reduced to a 1-dimensional model (i.e., a sequence of events on a single time line) by assuming either that events are synchronous (i.e., "slotted" operation of the protocol) or that all stations are mutually equidistant (so it can be assumed that each station's time line is identical). The novelty in our work is to describe the system state in terms of an (N + 1)-dimensional "ribbon" of space-time, allowing us to faithfully model the exact timings of events for LAN's where the stations are distributed over a fully connected region inN-space. For example, an Ethernet-like "bus" network can be viewed as a 1-dimensional LAN, a terrestrial packet radio network can be viewed as a 2dimensional LAN, and so on. First we highlight some of the key properties exhibited by such a model in the general case, including the notion of an embedded Markovian sequence of "idle points," and the decomposition of the space-time ribbon into cycles (each of which can be further decomposed into a number of "regions"). Then we present extensive results for the interesting special case of a 1-dimensional LAN, i.e., an Ethernet-like "bus" network. Our results show that previous models of bus LAN's can significantly underestimate their performance.

Multiple-access protocols control access to a broadcast communication channel. Tree conflict resolution algorithms are the heart of some distributed multiple-access protocols with nice properties like stability, high capacity, and low delay under light load. We consider a random access protocol based on a tree conflict resolution algorithm similar to one first proposed by Capetanakis, but in which constant size windows on the arrival time axis are used to admit packets into the algorithm instead of the more common "free" or "blocked" access methods. We obtain exact recursive relationships for the (steady-state) distribution of packet delay, and thus, the exact throughput-delay curve for any finite (in general, nonhomogeneous) configuration under a Bernoulli-per-window arrival model. Then, we consider the address assignment problem. We show that by choosing an appropriate addressing scheme, we can improve the performance of the algorithm with respect to both mean delay and maximum throughput.

We present a brief and simple analysis of asynchronous (unslotted) 1-Persistent CSMA protocols in the worst-case star topology. The purpose is two-fold. First, we give a simple approach based on an embedded Markov chain at the beginning of subbusy periods that greatly simplifies the analysis. And second, using the above approach we give the correct analysis for 1-Persistent CSMA with collision detection, since the only available analysis of the present model [1] is in error.

A new carrier sense multiple access (CSMA) algorithm, called virtual time CSMA, is described and analyzed. This algorithm uses a novel approach to granting access to the shared broadcast channel based on variable-rate clocks. Unlike other CSMA algorithms, the operation of virtual time CSMA reduces to the ideal case in the zero propagation time limit: a work-conserving, first-come first-servedM/G/1queueing system. The algorithm does not appear to be difficult to implement, but offers better throughput-delay performance than existing CSMA algorithms. A simple closed form technique for estimating the mean message delay is presented. This technique is of independent interest because of its applicability to certain "sliding window" tree conflict resolution algorithms. Extensive numerical results for the algorithm are presented, including comparisons with simulation and with other CSMA algorithms.

Random access protocols allow large numbers of low duty cycle stations to exchange messages over a shared communications channel under distributed control. Recently, a new class of random access protocols called 'tree algorithms' has emerged. Tree algorithms offer several performance advantages over other random access protocols (e.g. ALOHA and CSMA), namely higher capacity and inherently stable operation. However, only synchronous (slotted) tree algorithms have so far been defined. Any practical implementation of a synchronous protocol is complicated by the need for stations to perform the steps of the algorithm synchronously. Thus asynchronous (unslotted) protocols are of greater practical importance, especially for local networks. Here we show how to construct asynchronous versions of several well-known tree algorithms, and describe some of the performance limitations that result from asynchronous operation.

We present bounds on the maximum channel utilization (with finite average delay) of synchronous multiple access communications protocols serving an infinite population of homogeneous stations. Messages arrive to the system as a series of independent Bernoulli trials in discrete time, with probability p of an arrival at each arrival point (the Poisson limit is explicitly included) and are then randomly distributed among the stations. Pippenger showed that the channel utilization cannot exceed\xi_{p}, where\xi_{l}=1and\lim_{p \rightarrow 0} \xi_{p} \approx 0.744. Using a "helpful genie" argument, we find the exact capacity for allp \geq 0.568(where we find optimal protocols that obey first-come first-served); for smaller values of p, we present an improved upper bound that decreases monotonically to\approx 0.6731in the Poisson limit asp \rightarrow 0.

A conventional ALOHA satellite link uses a transponder which blindly echoes all up-channel traffic on the down-channel. An ALOHA channel can never be fully utilized, so an intelligent satellite could statistically multiplex the successful packets from several slotted ALOHA up-channels onto a single down-channel to conserve bandwidth, and hence reduce cost. We refer to this as a concentrated ALOHA system. Throughput, delay and stability effects are considered, varying the number of up-channels per down-channel and the satellite buffer size. Up- and down-channel bandwidths are assigned independent linear costs, and all performance comparisons are between constant cost systems. It is shown that the marginal increase in system performance drops off so quickly that a small number of up-channels maximizes throughput if up-channel bandwidth has a non-zero cost. This small number is a function of the buffer size and the relative cost of up- to down-channel bandwidth. It is also shown that, even if satellite buffer space is free, a small buffer minimizes average delay for some previously studied protocols of this type. A new protocol which improves performance and allows a large buffer to be used effectively is introduced and analyzed. Solving for throughput and delay in concentrated ALOHA systems provides new analytic and numeric results for the G/D/I queue with rest period equal to the service time.