We discuss an algorithm for generating all permutations of numbers between 1 and N .The algorithm is short and efficient, yet its behavior is not obvious from the code, mostly owing to the recursion.The discussion touches upon a few interesting methodological issues and brings in an educational case study in recursion.

The low-powered transmissions in a wireless sensor network (WSN) are highly susceptible to interference from external sources. Our work is a step towards enabling WSN devices to better understand the interference in their environment so that they can adapt to it and communicate more efficiently. We extend our previous work in which we collected received signal strength traces using mote-class synchronized receivers at sample rates that are, to the best of our knowledge, higher than previously described in the literature. These traces contain distinct interference patterns, each with a different potential for being exploited by cognitive radio strategies. In order to exploit a pattern, however, a node must first recognize it. Given the energy and space constraints of a node, we explore succinct decision tree classifiers for the two most disruptive patterns. We expand on a basic feature set to incorporate attributes based on the dip statistic and the Lomb periodogram, both of which address specific, empirically observed behaviour, and we show their positive impact on both the decision tree structure and the overall classification performance. Moreover, we present an approximation of the periodogram that makes its construction feasible for mote-class devices, and we describe the simplification's impact on classification performance.

We present a beacon-based clustering algorithm aimed at prolonging the cluster lifetime in VANETs. We use a new aggregate local mobility criterion to decide upon cluster re-organisation. The scheme incorporates a contention method to avoid triggering frequent re-organisations when two clusterheads encounter each other for a short period of time. Simulation results show a significant improvement of cluster lifetime and reduced node state/role changes compared to previous popular clustering algorithms.

Medium access in ad-hoc wireless networks must be performed in a distributed fashion due to lack of coordination between nodes. Specifically, when nodes are capable of receiving more than one transmission simultaneously, the design of distributed medium-access mechanisms that efficiently exploit the receiver's capability becomes more challenging. Adaptive probabilistic medium access for ad-hoc wireless networks is proposed in this paper. Nodes with data packets to transmit perform an announcement process in order to inform other nodes of their intended traffic. The acquired information through this process about other potential transmitters in the vicinity is then used by the nodes to choose a transmission probability with which they transmit their data packets. The performance of a multi-packet reception capable ad-hoc wireless network under the proposed protocol is analyzed and evaluated numerically and via simulations, and compared with Aloha-type random access.

We discuss the issue of reliable transmission of bounded streams of data samples over simple wireless channels offered by low-end RF modules. Traditional solutions, i.e., window-based ARQ schemes, applied to such channels tend to waste bandwidth, because of the need to maintain duplex communication. Our case study shows how one can overcome the inherent limitations of low-bandwidth unstructured wireless channels and claim most of their capacity for transmitting useful data.

Many protocols for ad-hoc wireless networks perform poorly in situations when node cooperation cannot be enforced. This may happen because of the lack of global authority over the nodes, or because of the environmental hostility. The net outcome of such scenarios is what we call a selfish behavior of nodes, which may spontaneously refuse to forward some packets. While unicast communication has been studied in this context, little has been done to improve the reliability of broadcasting in the face of limited trustworthiness of nodes. In this paper, we propose two enhancements of the popular broadcasting algorithms based on dominant pruning, which significantly improve the reachability of nodes in an unreliable ad-hoc wireless network. The improvement can be viewed as an enhancement of the network's fault tolerance, as it applies to most scenarios in which a node may fail to carry out its forwarding duties.

The primary performance objective of a broadcast scheme in an ad-hoc wireless network is to reduce the total number of retransmissions needed to reach all nodes. Another (less appreciated) measure of interest is the broadcast latency, i.e., the amount of time required to complete the operation. We point out the tradeoff between the two measures and show how to significantly reduce the broadcast latency in networks whose MAC schemes are derivatives of IEEE 802.11.

Packet scheduling in parallel forwarding systems is a hard problem. Two major goals of a scheduler that distributes incoming packets to multiple forwarding engines are to achieve high system utilization (by balancing the load evenly among the multiple engines) and to maintain packet ordering within individual flows. Additionally, from the viewpoint of the overall performance, the system should exhibit a good cache behavior by preserving temporal locality in the workload of each forwarding engine. In this paper, we show how the burstiness in Internet flows can be exploited to improve the performance of the scheduler. Specifically, TCP flows, which contribute to over 90 percent of the Internet traffic, transmit in bursts with relatively large delays in between. We propose a load balancing scheme based on this insight to achieve the scheduling goals. Our design is verified by simulations driven by real-world traces.

We consider the power control problem in ad-hoc wireless networks. Local decisions regarding the transmission power level induce a subgraph of the maximum powered graph, G/sub max/, in which edges represent direct reachability at maximum power. We propose a new algorithm for constructing minimum-energy path-preserving subgraphs of G/sub max/. Its superiority over previous solutions demonstrates once again that strict protocol layering in wireless networks tends to be detrimental to performance.

We consider the problem of anonymous file exchange in wireless ad-hoc networks. We propose a new protocol, dubbed RASH (roam and share), to address the problem. RASH is a peer-to-peer (P2P) protocol which fulfills three objectives: (a) protection of user privacy (understood as the confidentiality of their interests), (b) support for a high degree of file authentication and integrity (to reduce or eliminate false downloads and spoofs), and (c) enforcement of reciprocity (to remove freeloaders from the system). The environment of our scheme is purely ad-hoc, in that it does not assume pre-established trust, fixed-infrastructure, or the existence of specialized nodes

Workload distribution is critical to the performance of network processor based parallel forwarding systems. Scheduling schemes that operate at the packet level, e.g., round-robin, cannot preserve packet-ordering within individual TCP connections. Moreover, these schemes create duplicate information in processor caches and therefore are inefficient in resource utilization. Hashing operates at the flow level and is naturally able to maintain per-connection packet ordering; besides, it does not pollute caches. A pure hash-based system, however, cannot balance processor load in the face of highly skewed flow-size distributions in the Internet; usually, adaptive methods are needed. In this paper, based on measurements of Internet traffic, we examine the sources of load imbalance in hash-based scheduling schemes. We prove that under certain Zipf-like flow-size distributions, hashing alone is not able to balance workload. We introduce a new metric to quantify the effects of adaptive load balancing on overall forwarding performance. To achieve both load balancing and efficient system resource utilization, we propose a scheduling scheme that classifies Internet flows into two categories: the aggressive and the normal, and applies different scheduling policies to the two classes of flows. Compared with most state-of-the-art parallel forwarding schemes, our work exploits flow-level Internet traffic characteristics.

We present an effective method of eliminating unsolicited electronic mail (so-called spam ) and discuss its publicly accessible prototype implementation. A subscriber to our system is able to obtain an unlimited number of aliases of his/her permanent (protected) E-Mail address to be handed out to parties willing to communicate with the subscriber. It is also possible to set up publishable aliases, which can be used by human correspondents to contact the subscriber, while being useless to harvesting robots and spammers. The validity of an alias can be easily restricted to a specific duration in time, a specific number of received messages, a specific population of senders, and/or in other ways. The system is fully compatible with the existing E-Mail infrastructure and can be immediately accessed via any standard E-Mail client software (MUA). It can be easily deployed at any institution or organization running its private E-Mail server (MTA) with a trivial modification to that server. Our system offers a simple method to salvage the existing population of E-Mail addresses while eliminating all spam aimed at them.

We study a collection of K-shortest path routing schemes and investigate their performance under a diverse set of network topologies and traffic conditions. We subsequently demonstrate that K-shortest path routing offers a lower blocking probability and more balanced link utilisation than other routing methods. With the proposed approach, it is possible to reduce the frequency of link state exchange, and the incurred bandwidth overhead, without sacrificing the overall performance of the network.

We present a TDMA-based scheme intended for carrying traffic with diverse QoS requirements in mobile environments. In contrast to other TDMA protocols for mobile applications, instead of trying to fit the offered traffic to the slot size, our solution adapts the slot size to the offered traffic. In consequence, the proposed scheme is more flexible and incurs lower bandwidth overhead than other TDMA-based solutions.

We investigate experimentally several routing algorithms for asynchronous deflection networks, i.e., ones that operate in an unslotted manner. We determine the impact of an extra input buffer space on the quality of routing decisions. Finally, we compare the performance of asynchronous and synchronous deflection networks.

Multicasting in deflection networks is more difficult than in store-and-forward networks, because of the difficulties in sending multiple copies of the same packet on several output ports. On the other hand, deflected packets stray from their optimal paths and may visit the multicast recipients "accidentally", not necessary in the order envisioned by the sender. We compare a number of simple multicast strategies for deflection networks based on a few simple rules and assumptions. In particular, we never buffer packets that cannot be relayed immediately.

The call admission control schemes for ATM-type networks are based on the concept of effective bandwidth (EB). Most schemes focus on the cell loss rate as the exclusive QoS metric and therefore base their EB on cell-loss rate approximations. We use simulation data to develop regression models for cell loss and cell delay; these estimates can be used to compute effective bandwidths to satisfy both cell loss and delay. We compare the accuracy of the regression models with that of the well-know fluid-flow model by Anick et al. (1982). Our results indicate that the regression models are computationally simple and sufficiently accurate for practical use.

We present a deflection method suitable for Manhattan-street networks (MSN), which, without dropping packets, limits the number of hops travelled by a packet on its way from source to destination. The proposed routing scheme is intended for bidirectional networks-with four incoming and four outgoing links per switch. In terms of average performance measures, our method performs no worse than the best local routing schemes, when the offered load is light or moderate. Unlike other deflection schemes proposed for MSN, our method is inherently asynchronous. This simplifies the switch design and eliminates some problems with the original synchronous approach, like the need to account for slight discrepancies in transmission rates of different switches.

This paper proposes an efficient, fair, and simple capacity-1 protocol replacing FDDI. In the recent years, two network protocols gained predominance in very fast local and in metropolitan area networks: FDDI and DQDB. The FDDI ring-protocol combination is well-suited for large local ("campus") area networks. However, for larger networks, FDDI users suffer excessive access delays, even under very light traffic. Moreover, FDDI achieves full capacity only in special circumstances, and heavy load is not a sufficient condition for achieving it. We propose a network topology that is very similar to the dual ring and a token-passing protocol that yield a true capacity-1 network even for modest values of the TTRT. Its additional properties include total fairness and very small access delays under light load. This makes the proposed protocol a reasonable option to use in combination with the dual counter-rotating ring. The proposed network should not be difficult to implement using standard FDDI components.>

The authors present a simple MAC-level protocol for high-speed ring networks. The protocol is fair and its maximum achievable throughput does not deteriorate with the increasing propagation length of the ring. The proposed protocol operates on the so-called 'spiral ring' topology, including the single-segment regular ring as a special case. It accommodates synchronous traffic automatically, without any bandwidth preallocation or similar special efforts, yet with an arbitrarily low jitter and without packet loss.>

A token ring protocol which restricts the transmission rights to the station possessing the token is not a good candidate for driving a gigabit network. As the network's transmission rate becomes higher, the impact of the token transition time (which is idle) becomes more pronounced and the effective throughput of the network becomes a smaller and smaller fraction of the nominal channel capacity. The authors present a family of token passing protocols for ring networks which are devoid of this unpleasant property. The protocols are simple and inexpensive, yet they possess a number of advantageous properties: high capacity (similar to METARING and independent of the propagation length of the ring), fairness, and natural accommodation of synchronous and isochronous traffic.>

A new MAN/WAN medium-access control (MAC) protocol called CBRMA++/SR is introduced. It is suitable for a folded bus topology with optical fiber used as the transmission medium. The eminent features of CBRMA++/SR are total fairness and full bandwidth utilization. The preemptive approach employed in bandwidth allocation enables CBRMA+++/SR not to suffer from the deficiencies of DQDB, which stem mostly from the inconsistency of the distributed queue at a given instant. The protocol is based on the concept of fair share, which also provides a solid ground to support connection-oriented services. A powerful slot-reuse scheme complements the protocol.>

The authors propose an efficient, fair, and simple capacity-1 protocol that outperforms both fiber distributed data interface (FDDI) and distributed queue dual bus (DQDB). In the recent years, two network protocols gained predominance in very fast local and in metropolitan area networks: FDDI (using a single or dual ring) and DQDB (using a dual bus). The authors propose a network topology that is very similar to the dual ring of FDDI and a token-passing protocol suitable for this topology. Their solution yields a true capacity-1 network with zero access delay under light load. Moreover, it naturally accommodates synchronous traffic and is absolutely fair. The proposed protocol has a much better performance than FDDI; it also outperforms DQDB for sufficiently fast (or long) networks.>

A possible network architecture suitable for a next-generation follow-up to FDDI Is presented. The solution can be scaled-up to arbitrary transmission rates (limited only by the technological barriers) and arbitrarily long networks. The protocol allows every station to transmit when the ring is silent, even when the station is not in possession of the token. The resulting token-passing protocol yields a capacity-1 network irrespective of the value of TTRT. Additionally, stations endure a very small access delay under light load. The need to single out synchronous traffic is eliminated, guaranteeing each station the right to transmit at fixed intervals. This modification allows graceful station insertion and deletion; moreover, the recovery of a lost token can be done on the fly without disrupting the operation of the network.>

The paper demonstrates that the performance of MAC-level protocols is not very meaningful, when considered alone. The true object of performance analysis should be the pair (T,P), where T stands for network topology, and P for MAC-level protocol. The paper examines the performance of two MAC-level protocols: DQDB and LCSMA-CD/U/P. As both of them are capacity-1 protocols, they achieve the same maximum throughput; thus, the focus is on the packet access time and on fairness. The investigation shows that either protocol can be shown as greatly unfair or totally fair, depending on the topology that it operates on. As a byproduct, it is shown that the UU-BUS topology is quite interesting and merits further studies.>

Abstract LANSF is a software package that was originally designed as a tool to investigate the behaviour of medium access control (MAC) level protocols. These protocols form an interesting class of distributed computations: timing of events is the key factor in them. The protocol definition language of LANSF is based on C, and protocols are specified (programmed) as collections of communicating, interrupt‐driven processes. These specifications are executable: an event‐driven emulator of MAC‐level communication phenomena forms the foundation of the implementation. Some tools for debugging, testing, and validation of protocol specifications are provided. We present key features of LANSF at the syntactic level, comment informally on the semantics of these features, and highlight some implementation issues. A complete example of a LANSF application is discussed in the Appendix.

A collision protocol called piggyback Ethernet which is applicable for fast bus-type networks based on single, uniform, unsegmented, broadcast-type carriers is presented. Although piggyback Ethernet assumes that each station possesses certain global knowledge about the geometry of the network, it is argued that this knowledge can be acquired automatically at a reasonably small expense. The performance of the protocol for very heavy traffic is not worse than the performance of other protocols operating in a completely synchronized manner. The advantage this solution is its very good performance for light loads which is, for practical purposes, not worse than the performance of Ethernet. Moreover, compared to other protocols for fast networks, piggyback Ethernet has quite modest hardware requirements. The network is based on a straightforward bidirectional cable, each station has only one connection to the bus, and the actual length of the carrier is not bigger than the maximum distance between two stations.>

A formal semantics of a model for a communication channel is given. The model is the foundation of a simulation package which can be used for modeling of communication phenomena in distributed physical systems. The software system based on the model can be viewed as an emulator for LAN-type communication networks. The approach is centered around a formal model of s single CSMA/CD communication channel. The proposed model reflects all relevant elements of a real channel at the medium access control level.>

The performance of the ENET II protocol is discussed and compared to the performance of the commercial Ethernet. Linear network topologies with various number of stations uniformly distributed along the bus are considered. The comparison is based on extensive simulation studies and a recently published performance analysis of ENET II by Y.-C. Liu and G.L. Wise (1987). The experimental results agree with the analysis by Liu and Wise, but they do not confirm the results of M.K. Molloy (1985).>