Probabilistic flooding is an efficient information dissemination policy capable of spreading information to the network nodes by sending information messages according to a fixed forwarding probability in a per-hop manner starting from an initiator node. It is a suitable approach, especially in topologies where the number of information messages sent under traditional approaches is significantly increased. The analysis presented in this paper considers graph spectra properties such as the largest eigenvalue$\lambda _{1}$of the adjacency matrix, and the eigenvector centrality. Both are analytically investigated and$\frac {4}{\lambda _{1}}$is derived as a lower bound of the forwarding probability that allows for global coverage, i.e., all network nodes receive the information message, under certain conditions also investigated here (e.g., the condition of the binomial approximation). It is shown that for any value of the forwarding probability equal to or larger than$\frac {4}{\lambda _{1}}$: (i) coverage is proportional to the initiator node’s eigenvector centrality; (ii) the probability a node receives the information message is proportional to the node’s eigenvector centrality; (iii) termination time decreases as the initiator node’s eigenvector centrality increases. If knowledge of$\lambda _{1}$is not available, then the average node degree$\bar {d}$can be used for ensuring global coverage. If knowledge of both$\lambda _{1}$and$\bar {d}$is not available, a dissemination policy is proposed that forwards messages to$m$(randomly selected) neighbor nodes. It is analytically shown that any value of$m \geq 4$allows for global coverage. Simulation results demonstrate the effectiveness of the considered analytical approach and the introduced policy.

Network traffic anomalies can have a detrimental effect on end-to-end network performance and reliability, compromising severely (demanding) services and applications, such as those offered by the fifth-generation (5G) mobile networks and beyond. To prevent the network drift towards increasingly inefficient operating modes, such traffic anomalies need to be detected first, so that the proper actions be taken to avoid such undesirable network drift. This paper proposes a novel framework focusing on proactively detecting such traffic anomalies, that is, predicting upcoming network traffic anomalies before they actually occur. To this end, two mechanisms are developed: a mechanism aiming at identifying different network traffic behaviors in an automated manner; and a mechanism for predicting network traffic behaviors for the next time interval spanning several seconds. The automated network traffic anomaly identification is realized via the application of clustering and decision tree-based learning. A time series model (specifically, a Bidirectional Long Short Term Memory (BiLSTM) Autoencoder) is employed for the proactive detection of forthcoming network traffic behaviors. Evaluation results are derived showing a prediction accuracy of up to 90.02%, demonstrating the effectiveness and viability of the proposed framework, as well as its potential for higher effectiveness compared to a state-of-the-art solution.

In the era of Industrial Internet of Things (IIoT) and Industry 4.0, an immense volume of heterogeneous network devices will coexist and contend for shared network resources, in order to satisfy the very challenging IIoT applications, requiring ultra-reliable and ultra-low latency communications. Although novel key enablers, such as Network Slicing, Software Defined Networking (SDN) and Network Function Virtualization (NFV) have already offered significant advantages towards more efficient and flexible network and resource management approaches, the particular characteristics of IIoT applications pose additional burdens, mainly due to the complex wireless environments, high number of heterogeneous network devices, sensors, user equipments (UEs), etc., which may stochastically demand and contend for the - often scarce - computing and communication resources of industrial environments. To this end, this paper introduces PRIMATE, a novel, Artificial Intelligence (AI)-driven framework for the profiling of the networking behavior of such UEs, devices, users and things, which is able to operate in conjunction with already standardized or forthcoming, AI-based network resource management processes towards further gains. The novelty and potential of the proposed work lies on the fact that instead of attempting to either predict raw network metrics in a reactive manner, or predict the behavior of specific network entities/devices in an isolated manner, a big data-driven classification approach is introduced, which models the behavior of any network device/user from both a macroscopic, as well as service-specific perspective. The extended evaluation at the last part of this work shows the validity and viability of the proposed framework.

The recent technological evolution of drones along with the constantly growing maturity of its commercialization, has led to the emergence of novel drone-based applications within the field of wireless sensor networks for information collection purposes. In such settings, especially when deployed in outdoor environments with limited external control, energy consumption and robustness are challenging problems for the system’s operation. In the present paper, a drone-assisted wireless sensor network is studied, the aim being to coordinate the routing of information (among the ground nodes and its propagation to the drone), investigating several drone trajectories or route shapes and examining their impact on information collection (the aim being to minimize transmissions and consequently, energy consumption). The main contribution lies on the proposed algorithms that coordinate the communication between (terrestrial) sensor nodes and the drone that may follow different route shapes. It is shown through simulations using soft random geometric graphs that the number of transmitted messages for each drone route shape depends on the rotational symmetry around the center of each shape. An interesting result is that the higher the order of symmetry, the lower the number of transmitted messages for data collection. Contrary, for those cases that the order of symmetry is the same, even for different route shapes, similar number of messages is transmitted. In addition to the simulation results, an experimental demonstration, using spatial data from grit bin locations, further validates the proposed solution under real-world conditions, demonstrating the applicability of the proposed approach.

Advanced Driver Assistance Systems require a tremendous amount of sensor information to support the driver's comfort and safety. In particular, systems that provide (good) route options to a vehicle rely on information, such as traffic jams and road blockages, which is sensed by other (possibly distant) vehicles and distributed by a central server. This information is clearly dynamic and may be invalid by the time the vehicle arrives at the affected location. In this work, we develop an innovative approach to determine optimal routes (minimizing the costs like travel-time to their destination) for vehicles whose original route is adversely impacted by a (severe) road event. A set of recursive equations is developed that yields the optimal decision for each vehicle at each decision-point. Simulations show that our approach adapts to the considered event and finds routes of similar quality as a full-knowledge approach with limited communication overhead.

In this special issue, we have collected and presented recent works on innovative approaches and emerged technologies for coping with dynamicity, heterogeneity, and the scale, which have been central to (or even enablers of) recent advances in communications and networking technologies. At a time of an ever-increasing demand for networking resources and a larger scale, communication networks have faced challenges due to the heterogeneity of the demands, the diversity of communication mechanisms, the high dynamicity of the environments, the virtualization of functions, and the stringent and dynamic quality requirements. In recent years, there have been notable advancements in research and development of concepts and methods for highly adaptive and scalable communication networks.This special issue focuses on recent advances in the field of adaptive and scalable communications.

Several critical operations such as, data collection, routing, service discovery, etc., employ various types of information dissemination in order to be carried out. To avoid costly flooding-based solutions reaching out to all nodes, it is frequently sufficient that only a proper subset of the nodes (or backbone network) be involved, i.e., the one ensuring that every other node will be at most d hops away from a node belonging to the said subset of nodes. Finding this subset is equivalent to the construction of a d-hop Connected Dominating Set (d-CDS). Given the high complexity (non-polynomial) and the requirement of global information for constructing a Minimum d-CDS (d-MCDS), in this paper a distributed algorithm that relies on local information (i.e., d hops away) to construct an approximation of the d-MCDS is developed. The proposed algorithm is studied and compared against a centralized one that is an approximate solution for the minimum d-MCDS problem, and a recently proposed distributed one. It is shown that the size of the constructed d-CDS under the proposed algorithm is (i) close and sometimes smaller than that under the recently proposed one; and (ii) close to the centralized one. In addition, the number of transmitted messages is significantly reduced under the proposed algorithm, which is important for preserving energy resources in wireless sensor networks.

Information dissemination plays a crucial role in modern network environments being an integral part of various vital processes (e.g., service discovery, data collection, routing). Probabilistic flooding has been proposed as a suitable alternative to blind flooding in order to reduce unnecessary transmissions and save valuable network resources. Under probabilistic flooding, an information message, initially located at some network node (i.e., the initiator node), is transmitted to neighbor nodes according to a forwarding probability attempting to reach all network nodes. This paper employs elements from algebraic graph theory to model probabilistic flooding behavior and derive analytical results regarding coverage (i.e., the number of nodes that have received the information message) and a lower bound of the forwarding probability allowing for global network outreach. It is also shown here, that for any value of the forwarding probability larger than this lower bound, (i) coverage under probabilistic flooding, is proportional to the initiator's node eigenvector centrality; and (ii) the probability for a node to receive the information message is proportional to the particular node's eigenvector centrality. Simulations performed for various topologies demonstrate the effectiveness of the proposed analytical model and support the analytical results.

As a step towards fully autonomous driving, Advanced Driver Assistance Systems provide convenience-and safety-related functions to drivers. In addition to data gathered by local sensors, these systems rely on events generated by other vehicles that need to be disseminated to a potentially large audience. Today, this geocast-functionality relies either on subscriptions covering certain areas (e.g., cities) or on individual route-based subscriptions. While the former exhibits suboptimal precision in filtering, the latter introduces significant complexity and assume that routes are known in advance. We propose a prediction-based assessment of the relevance of events without requiring prior route knowledge. Relevance is modeled based on the street network and spatio-temporal characteristics of events. We evaluate our approach in a realistic city setting, relying on the SUMO vehicular mobility simulator. Our first results show that relevance-aware information dissemination reduces the communication overhead by 68%, while at the same time achieving near perfect recall compared to route-based subscrintions.

Mobile applications increasingly rely on frequent and accurate position updates-e.g., with GPS-or Wi-Fi-assisted localization techniques-to provide for functionality to their users. The service quality and acceptance of the application depend strongly on the localization accuracy and the introduced costs, in form of the resource consumption, of the used localization technique. Current mechanisms for location retrieval, however, are limited to non-mobile scenarios or still introduce high costs while obtaining the location. In this work, we propose a collaborative location retrieval service for location-based services in mobile scenarios that combines the location information of a subset of users with the connectivity information between users to enable accurate and cost-efficient location estimations. We evaluate a prototype of our solution to study the impact of service compositions in changing environments and to assess the potential of our proposed service compared to the current state-of-the-art used within location-based services. Our results reveal that, depending on the localization technique, the costs can be reduced significantly while the achieved sensing accuracy and fairness among users improves strongly at the same time.

In order to tackle the energy hole problem in wireless sensor networks, various recharging policies have been proposed attempting to keep the average energy level high and the recharging distance (i.e., the distance covered by a mobile recharger) low. As shown in the literature, the recharging distance is minimized when the basis of the mobile recharger is located at the solution of a median problem that takes into account both distance and traffic demands. In this paper, a novel on-demand recharging policy is proposed based on local information, where the mobile recharger moves-upon request-to a target node of reduced energy level and replenishes its battery. Under the proposed policy, the mobile recharger moves in a hop-by-hop manner to the neighbor nodes of the lowest energy level, starting from the target node. The effectiveness of this policy is investigated here using simulation results and compared against an existing well-known on-demand recharging policy that exploits global knowledge (i.e., knowledge of both the energy level of all nodes and the network topology). It is shown that the proposed policy, even though based on local information, maintain the average energy level and termination time higher than that under the existing one that exploits global knowledge. Furthermore, it is observed that the network's lifetime is maximized when the basis of the mobile recharger is located at the solution of the mentioned median problem for all studied policies.

The tremendous growth of urbanization calls for several interventions for the efficient and environmentally sustainable management of various urban processes, including the road traffic management. Indeed, transportation engineers need to be able to understand how drivers decide their route to effectively address the plethora of challenges for alleviating the congestion phenomena in city areas. In this paper, we model drivers' decision-making with respect to the parking space search, which has been regarded as one of the major causes of traffic congestion. We view the parking search as an instance of sequential search problems and present a game-theoretic investigation of the efficiency of heuristic parking search strategies to locate available parking spot at minimum walking and driving overhead. The analytical study concludes by drawing similarities between the parking game and well-known archetypal games that the Game Theory examines.

Our paper investigates normative abstractions for the way drivers pursue parking space and respond to pricing policies about public and private parking facilities. The drivers are viewed as strategic agents who make rational decisions while attempting to minimize the cost of the acquired parking spots. We propose auction-based systems for realizing centralized parking allocation schemes, whereby drivers bid for public parking space and a central authority coordinates the parking assignments and payments. These are compared against the conventional uncoordinated parking search practice under fixed parking service cost, formulated as a resource selection game instance. In line with intuition, the auctioning system increases the revenue of the public parking operator exploiting the drivers' differentiated interest in parking. Less intuitively, the auction-based mechanism does not necessarily induce higher cost for the drivers: by avoiding the uncoordinated search and thus, eliminating the cruising cost, it turns out to be a preferable option for both the operator and the drivers under various combinations of parking demand and pricing policies.

Micro-blogging services have recently been experiencing increasing success among Web users. Different to traditional online social applications, micro-blogs are lightweight, require small cognitive effort and help share real-time information about personal activities and interests. In this article, we explore scalable pushing protocols that are particularly suited for the delivery of this type of service in a mobile pervasive environment. Here, micro-blog updates are generated and carried by mobile (smart-phone type) devices and are exchanged through opportunistic encounters. We enhance primitive push mechanisms using social information concerning the interests of network nodes as well as the frequency of encounters with them. This information is collected and shared dynamically, as nodes initially encounter each other and exchange their preferences, and directs the forwarding of micro-blog updates across the network. Also incorporated is the spatiotemporal scope of the updates, which is only partially considered in current Internet services. We introduce several new protocol variants that differentiate the forwarding strategy towards interest-similar and frequently encountered nodes, as well as the amount of updates forwarded upon each encounter. In all cases, the proposed scheme outperforms the basic flooding dissemination mechanism in delivering high numbers of micro-blog updates to the nodes interested in them. Our extensive evaluation highlights how use can be made of different amounts of social information to trade performance with complexity and computational effort. However, hard performance bounds appear to be set by the level of coincidence between interest-similar node communities and meeting groups emerging due to the mobility patterns of the nodes.

The effectiveness of service provisioning in large-scale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving the uncapacitated k-median (UKM) problem (if the requested number of facilities is fixed- k) or the uncapacitated facility location (UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: “How can we determine in a distributed and scalable manner the number and location of service facilities?” In this paper, we develop a scalable and distributed approach that answers our key question through an iterative reoptimization of the location and the number of facilities within network neighborhoods. We propose an innovative approach to migrate, add, or remove servers within limited-scope network neighborhoods by utilizing only local information about the topology and demand. We show that even with limited information about the network topology and demand, within one or two hops, our distributed approach achieves performance, under various synthetic and real Internet topologies and workloads, that is comparable to that of optimal, centralized approaches requiring full topology and demand information. We also show that it is responsive to volatile demand. Our approach leverages recent advances in virtualization technology toward an automated placement of services on the Internet.

The optimal placement of service facilities largely determines the capability of a data network to efficiently support its users' service demands. As centralized solutions over large-scale distributed environments are extremely expensive, inefficient or even infeasible, distributed approaches that rely on partial topology and demand information are the only credible approaches to the service placement problem, even at the expense of non-guaranteed optimality. In this paper, we propose a distributed service migration heuristic that iteratively solves instances of the 1-median problem pushing progressively the service to more cost-effective locations. Key to our algorithm is a traffic-aware centrality metric, called weighted conditional betweenness centrality (wCBC), that captures the ability of a node to act as service demand concentrator and is employed in both selecting the nodes and setting their weights for the 1-median problem instance. The assessment of our heuristic proceeds in two steps. First, assuming (ideal) knowledge of the invoked wCBC metric, we carry out a proof-of-concept study that demonstrates the effectiveness of the heuristic over synthetic and real-world topologies as well as its advantages against comparable local-search-like migration schemes. Next, we devise practical protocol implementations that approximate the heuristic using local measurements of transit traffic and preserve the excellent accuracy and fast convergence properties of the algorithm for different routing policies. Our solution applies to a broad range of networking scenarios, and is very relevant to the emerging trends for in-network storage and involvement of the end-user in the creation and distribution of lightweight (autonomic) service facilities.

This paper explores how the degree of similarity within a social group can dictate the behavior of the individual nodes, so as to best tradeoff the individual with the social benefit. More specifically, we investigate the impact of social similarity on the effectiveness of content placement and dissemination. We consider three schemes that represent well the spectrum of behavior-shaped content storage strategies: the selfish, the self-aware cooperative, and the optimally altruistic ones. Our study shows that when the social group is tight (high degree of similarity), the optimally altruistic behavior yields the best performance for both the entire group (by definition) and the individual nodes (contrary to typical expectations). When the group is made up of members with almost no similarity, altruism or cooperation cannot bring much benefit to either the group or the individuals and thus, selfish behavior emerges as the preferable choice due to its simplicity. Notably, from a theoretical point of view, our “similarity favors cooperation” argument is inline with sociological interpretations of human altruistic behavior. On a more practical note, the self-aware cooperative behavior could be adopted as an easy to implement distributed alternative to the optimally altruistic one; it has close to the optimal performance for tight social groups and the additional advantage of not allowing mistreatment of any node, i.e., its induced content retrieval cost is always smaller than the cost of the selfish strategy.

Summary form only given. Social metrics have recently been considered to capture the degree of similarity in interests of the nodes as well as their “standing” within a community or network. In this talk some recent works-examples are briefly presented showing the potential benefits from incorporating social metrics in content replication, forwarding and placement. More specifically, a framework for assessing interest similarity is presented and applied to illustrate how similarity affects the effectiveness of content replication and forwarding. In addition, the widely adopted Betweenness Centrality metric is revisited and issues associated with its computation and appropriateness for content forwarding are discussed. Then, modifications and easily computable variants are introduced and their effectiveness is illustrated.

Authentication in 3G encompasses a mechanism, which ensures that the authentication vectors (AVs) are used only once. To achieve this, the employed mechanism maintains counters at both sides (mobile station and network) and verifies that the provided AVs are among the last α generated. However, there are many cases in which the mobile station receives AVs that have not been previously used, but the employed mechanism rejects them as outdated. This phenomenon, called false synchronization, causes signaling overhead and delays, and increases the cost of the network use. False synchronizations are more frequent in 3G-WLAN integrated networks. The frequency of false synchronizations decreases with α, while at the same time the risk of a replay attack increases. This paper aims at analytically determining an appropriate value of α, which balances effectively in 3G-WLANs the tradeoff between the rate of false synchronizations and exposure to adversaries exploiting compromised AVs. This is done by determining a threshold value of α beyond which the further reduction in false synchronizations is marginal, while the potential for a replay attack is constantly increasing and substantial. To this end, an analytical model based on a four dimensional Markov chain is developed whose accuracy is verified through simulations.

This paper explores how the degree of similarity within a social group can be exploited in order to dictate the behavior of the individual nodes, so as to best accommodate the typically non-coinciding individual and social benefit maximization. More specifically, this paper investigates the impact of social similarity on the effectiveness of content dissemination, as implemented through three classes representing well the spectrum of behavior-shaped content storage strategies: the selfish, the self-aware cooperative and the optimally altruistic ones. This study shows that when the social group is tight (high degree of similarity), the optimally altruistic behavior yields the best performance for both the entire group (by definition) and the individual nodes (contrary to typical expectations). When the group is made up of foreigners with almost no similarity, altruism or cooperation cannot bring much benefits to either the group or the individuals and thus, a selfish behavior would make sense due to its simplicity. Finally, the self-aware cooperative behavior could be adopted as an easy to implement distributed scheme — compared to the optimally altruistic one — that has close to the optimal performance for tight social groups, and has the additional advantage of not allowing mistreatment to any node (i.e., the content retrieval cost become larger compared to the cost of the selfish strategy).

Service placement is a key problem in communication networks as it determines how efficiently the user service demands are supported. This problem has been traditionally approached through the formulation and resolution of large optimization problems requiring global knowledge and a continuous recalculation of the solution in case of network changes. Such approaches are not suitable for large-scale and dynamic network environments. In this paper, the problem of determining the optimal location of a service facility is revisited and addressed in a way that is both scalable and deals inherently with network dynamicity. In particular, service migration which enables service facilities to move between neighbor nodes towards more communication cost-effective positions, is based on local information. The migration policies proposed in this work are analytically shown to be capable of moving a service facility between neighbor nodes in a way that the cost of service provision is reduced and - under certain conditions - the service facility reaches the optimal (cost minimizing) location, and locks in there as long as the environment does not change; as network conditions change, the migration process is automatically resumed, thus, naturally responding to network dynamicity under certain conditions. The analytical findings of this work are also supported by simulation results that shed some additional light on the behavior and effectiveness of the proposed policies.

Random Walks (RWs) have been considered for information dissemination in large scale, dynamic and unstructured environments, as they are scalable, robust to topology changes and do not require topology information. Nevertheless, they are relatively slow in reaching out to the network nodes, particularly when applied to wireless networks (such as Wireless Sensor Networks (WSNs)), where the steps of the walk are of limited range, they reach only physically-close neighbours and are unable to move the walker far away from just covered area; as a consequence, time and resources are wasted in revisits of already covered nodes. In this paper we develop an innovative mechanism (referred to as the Jumping Random Walk (J-RW)) that alleviates drastically the aforementioned problems and is shown to improve substantially (compared to the RW) the cover time/overhead or coverage of WSNs modelled as a random geometric graph.

We present OnMove, a protocol for content distribution in wireless delay tolerant networks for use by handheld devices. To improve content distribution, OnMove exploits social characteristics (social similarities and physical encounters) between individuals. We motivate the problem and describe a content sharing protocol based on a ranking algorithm that exploits the social and networking characteristics of individuals.

Service placement has typically been studied through the formulation and solution of a 1-median problem that is known to be complex and require global information. As such approaches are clearly not scalable in dynamic and large-scale environments, a more reasonable approach to service placement for large, ad hoc and autonomic environments would be through service migration. Such a migration policy has recently been proposed for tree topologies. The focus of the present paper is to devise effective service migration policies for general topologies with equal weight links. The proposed strategy - that incorporates a 2-phase polling mechanism of local scope and, consequently, induces in general a certain overhead - is shown to out-perform the previous one (i.e., getting closer to the optimal placement) for such general topologies. Finally, a hybrid migration policy (combining the present and the past ones) is considered and shown through simulations to be capable of reducing significantly the overhead effects of the afore-mentioned polling mechanism.

The effectiveness of service provisioning in large-scale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving theuncapacitated k-median(UKM) problem (if the requested number of facilities is fixed), or theuncapacitated facility location(UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: "How can we determine in a distributed and scalable manner thenumberandlocationof service facilities?" We propose an innovative approach in which topology and demand information is limited to neighborhoods, or balls of small radius around selected facilities, whereas demand information is captured implicitly for the remaining (remote) clients outside these neighborhoods, by mapping them to clients on the edge of the neighborhood; the ball radius regulates the trade-off between scalability and performance. We develop a scalable, distributed approach that answers our key question through an iterative re-optimization of the location and the number of facilities within such balls. We show that even for small values of the radius (1 or 2), our distributed approach achieves performance under various synthetic and real Internet topologies that is comparable to that of optimal, centralized approaches requiring full topology and demand information.

Probabilistic flooding (parameterized by a forwarding probability) has frequently been considered in the past, as a means of limiting the large message overhead associated with traditional (full) flooding approaches that are used to disseminate globally information in unstructured peer-to-peer and other networks. A key challenge in using probabilistic flooding is the determination of the forwarding probability so that global network outreach is achieved while keeping the message overhead as low as possible. By showing that a probabilistic flooding network generated by applying probabilistic flooding to a connected random graph network can be bounded by properly parameterized random graph networks and invoking random graph theory results, bounds on the value of the forwarding probability are derived guaranteeing global network outreach with high probability, while significantly reducing the message overhead. Bounds on the average number of messages - as well as asymptotic expressions - and on the average time required to complete network outreach are also derived, illustrating the benefits of the properly parameterized probabilistic flooding scheme.

Although cooperation generally increases the amount of resources available to a community of nodes, thus improving individual and collective performance, it also allows for the appearance of potential mistreatment problems through the exposition of one node's resources to others. We study such concerns by considering a group of independent, rational, self-aware nodes that cooperate using online caching algorithms, where the exposed resource is the storage at each node. Motivated by content networking applications - including Web caching, content delivery networks (CDNs), and peer-to-peer (P2P) - this paper extends our previous work on the offline version of the problem, which was conducted under a game-theoretic framework and limited to object replication. We identify and investigate two causes of mistreatment: 1) cache state interactions (due to the cooperative servicing of requests) and 2) the adoption of a common scheme for cache management policies. Using analytic models, numerical solutions of these models, and simulation experiments, we show that online cooperation schemes using caching are fairly robust to mistreatment caused by state interactions. To appear in a substantial manner, the interaction through the exchange of miss streams has to be very intense, making it feasible for the mistreated nodes to detect and react to exploitation. This robustness ceases to exist when nodes fetch and store objects in response to remote requests, that is, when they operate as level-2 caches (or proxies) for other nodes. Regarding mistreatment due to a common scheme, we show that this can easily take place when the "outlier" characteristics of some of the nodes get overlooked. This finding underscores the importance of allowing cooperative caching nodes the flexibility of choosing from a diverse set of schemes to fit the peculiarities of individual nodes. To that end, we outline an emulation-based framework for the development of mistreatment-resilient distributed selfish caching schemes.

In this paper we examine the impact of the adopted playout policy on the overall performance of a P2P streaming system. It is argued and showed that adopting (popular) playout policies that result in a divergence of the playout points drastically deteriorates the performance of P2P streaming and that policies that keep these points near-in-time should be adopted.

Abstract — Although cooperation generally increases the amount of resources available to a community of nodes, thus improving individual and collective performance, it also allows for the appearance of potential mistreatment problems through the exposition of one node’s resources to others. We study such concerns by considering a group of independent, rational, self-aware nodes that cooperate using on-line caching algorithms, where the exposed resource is the storage of each node. Motivated by content networking applications – including web caching, CDNs, and P2P – this paper extends our previous work on the off-line version of the problem, which was limited to object replication and was conducted under a game-theoretic framework. We identify and investigate two causes of mistreatment: (1) cache state interactions (due to the cooperative servicing of requests) and (2) the adoption of a common scheme for cache replacement/redirection/admission policies. Using analytic models, numerical solutions of these models, as well as simulation experiments, we show that online cooperation schemes using caching are fairly robust to mistreatment caused by state interactions. When this becomes possible, the interaction through the exchange of miss-streams has to be very intense, making it feasible for the mistreated nodes to detect and react to the exploitation. This robustness ceases to exist when nodes fetch and store objects in response to remote requests, i.e., when they operate as Level-2 caches (or proxies) for other nodes. Regarding mistreatment due to a common scheme, we show that this can easily take place when the “outlier ” characteristics of some of the nodes get overlooked. This finding underscores the importance of allowing cooperative caching nodes the flexibility of choosing from a diverse set of schemes to fit the peculiarities of individual nodes. To that end, we outline an emulation-based framework for the development of mistreatment-resilient distributed selfish caching schemes.

Wireless sensor networks are typically bound to operate autonomously on a field, under severe energy constraints and without any centralized control. It is thus essential to develop self organization protocols/algorithms which enable the autonomous, distributed and energy efficient network self organization. Budget based clustering approaches have recently been proposed for this purpose, by specifying rules for distributing a given budget of tokens to neighbors. In this paper, two strictly localized, budget based clustering algorithms are pro posed: the directed budget based (DBB) and directed budget based with random delays (DBB-RD). The basic, innovative idea is to utilize clustering status information that can be readily available (e.g. through the HELLO exchanges) to reduce or eliminate token distribution contentions (both intra and inter cluster) that severely limit the effectiveness of earlier budget based approaches. Simulation results are presented demonstrating a substantial improvement over the earlier approaches with respect to the achieved cluster sizes and time to complete network decomposition

A commonly employed abstraction for studying the object placement problem for the purpose of Internet content distribution is that of a distributed replication group. In this work, the initial model of the distributed replication group of Leff et al. [CHECK END OF SENTENCE] is extended to the case that individual nodes act selfishly, i.e., cater to the optimization of their individual local utilities. Our main contribution is the derivation of equilibrium object placement strategies that 1) can guarantee improved local utilities for all nodes concurrently as compared to the corresponding local utilities under greedy local object placement, 2) do not suffer from potential mistreatment problems, inherent to centralized strategies that aim at optimizing the social utility, and 3) do not require the existence of complete information at all nodes. We develop a baseline computationally efficient algorithm for obtaining the aforementioned equilibrium strategies and then extend it to improve its performance with respect to fairness. Both algorithms are realizable, in practice, through a distributed protocol that requires only a limited exchange of information.

No abstract available.

Recent advances in wireless technology make high data rate communication in short ranges feasible. The network instances of short-range paths that may achieve high data rates are defined as network flashes in this paper. The characteristics and the efficiency of network flashes are discussed here.

Large scale hierarchical caches for Web content have been deployed widely in an attempt to reduce delivery delays and bandwidth consumption and also to improve the scalability of content dissemination through the World Wide Web. Irrespective of the specific replacement algorithm employed in each cache, a de facto characteristic of contemporary hierarchical caches is that a hit for a document at an l-level cache leads to the caching of the document in all intermediate caches (levels l-1,..., 1) on the path towards the leaf cache that received the initial request. This paper presents various algorithms that revises this standard behavior and attempts to be more selective in choosing the caches that gets to store a local copy of the requested document. As these algorithms operate independently of the actual replacement algorithm running in each individual cache, they are referred to as meta algorithms. Three new meta algorithms are proposed and compared against the de facto one and a recently proposed one by means of synthetic and trace-driven simulations. The best of the new meta algorithms appears to be leading to improved performance under most simulated scenarios, especially under a low availability of storage. The latter observation makes the presented meta algorithms particularly favorable for the handling of large data objects such as stored music files or short video clips. Additionally, a simple load balancing algorithm that is based on the concept of meta algorithms is proposed and evaluated. The algorithm is shown to be able to provide for an effective balancing of load thus possibly addressing the recently discovered "filtering-effect" in hierarchical Web caches.

The design of an efficient medium access control (MAC) for ad hoc networks is challenging. Topology-unaware time-division multiple-access-based schemes, suitable for ad hoc networks, that guarantee a minimum throughput, have already been proposed. These schemes consider a deterministic policy for the utilization of the assigned scheduling time slots that never utilizes nonassigned slots although in such slots collision-free transmissions are possible even under heavy traffic conditions. A simple probabilistic policy, capable of utilizing the nonassigned slots according to an access probability, fixed for all users in the network, is introduced and analyzed here. The conditions under which the system throughput under the probabilistic policy is higher than that under the deterministic policy are derived analytically. Further analysis of the system throughput is shown to be difficult or impossible for the general case and certain approximations have been considered whose accuracy is also investigated. The approximate analysis determines the value for the access probability that maximizes the system throughput, as well as simplified lower and upper bounds that depend only on a topology density metric. Simulation results demonstrate the comparative advantage of the probabilistic policy over the deterministic policy and show that the approximate analysis successfully determines the range of values for the access probability for which the system throughput under the probabilistic policy is not only higher than that under the deterministic policy, but it is also close to the maximum.

The problem of call admission control (CAC) is considered for leaky bucket constrained sessions with deterministic service guarantees (zero loss and finite delay bound) served by a generalized processor sharing scheduler at a single node in the presence of best effort traffic. Based on an optimization process, a CAC algorithm capable of determining the (unique) optimal solution is derived. The derived algorithm is also applicable, under a slight modification, in a system where the best effort traffic is absent and is capable of guaranteeing that if it does not find a solution to the CAC problem, then a solution does not exist. The numerical results indicate that the CAC algorithm can achieve a significant improvement on bandwidth utilization as compared to a (deterministic) effective bandwidth-based CAC scheme.

In ad-hoc networks, where a user can enter, leave or move inside the network with no need for prior configuration, the support of multimedia applications that require very high bit-rates, is a challenging problem. Here, a centralized ad-hoc network architecture (CANA) is proposed, capable of efficiently supporting those applications in low mobility environments, while at the same time a standard wireless LAN environment is maintained for fast moving users. CANA is based on an enhanced HiperLAN/2 protocol architecture [ETR0230002 V0.2.0, 1999-04] [Johnsson, M., 1999], (even though this is not mandatory) that supports a dual mode of operation at 5 GHz and 60 GHz. In this system architecture, several ad-hoc specific functionalities are included, such as neighborhood discovery, clustering and routing. Among them, switching between different modes of operation has a large impact on the achievable performance of CANA.

A novel framework is presented for the study of scalability in ad hoc networks. Using this framework, the first asymptotic analysis is provided with respect to network size, mobility, and traffic for each fundamental class of ad hoc routing algorithms. Protocols studied include the following: plain flooding (PF), standard link state (SLS), dynamic source routing (DSR), hierarchical link state (HierLS), zone routing protocol (ZRP), and hazy sighted link state (HSLS). It is shown that PF and ZRP scale better with mobility, SIJS and ZRP scale better with respect to traffic, and HSLS scales better with respect to network size. The analysis provides deeper understanding of the limits and trade-offs inherent in mobile ad hoc network routing. Our analysis is complemented with a simulation experiment comparing HSLS and HierLS. An important contribution of this paper is that HSLS is an scalable, easy-to-implement, alternative to hierarchical approaches for large ad hoc networks.

In this paper, an efficient scheme is proposed based on the introduced deadline-credit-based (DC) policy. This scheme is appropriate for any prerecorded media, but is particularly relevant for prerecorded semisoft continuous media (CM) applications. Semisoft are applications with very small initial delay tolerance and, thus, for which very small amount of content may be sent in advance. The proposed policy pushes content toward the end user during the session by taking advantage of any bandwidth underutilization periods, exploiting available storage, and building up fairly a deadline credit to be consumed during periods of overutilization. The scheduling policy is studied for the single-hop case (applicable to the server of the content), as well as for the multihop case (applicable to the server and network nodes). The derived results demonstrate the ability of the proposed scheme to decrease the amount of required bandwidth (or equivalently induced losses) with respect to alternative schemes without requiring large initial delay, which is not acceptable for semisoft CM applications.

Due to random delay variations in current best effort networks, packet video applications rely on end-system buffering and playout adaptation to reduce the effects of disruptions on the required smooth stream presentation. To study the effect of buffering and playout adaptation, we present an analytical model based on the M/G/1 queueing system with finite buffer capacity, and traffic intensity equal to or greater than unity. This model fits well a range of new applications that have limited buffer resources for the reception of incoming frames. We introduce the variance of distortion of playout (VDoP), a new metric that accounts for the overall presentation disruption caused by buffer underflows, intentionally introduced gaps during slowdown periods and data loss from overflows. VDoP is an elegant and fair metric for the estimation of playout quality and will hopefully assist the development of better adaptation algorithms. Furthermore, the effect of finite buffer capacity is examined in relation to stream continuity revealing a system behavior not previously accounted for. The sensitivity of the system to the variance of the arrival process is also examined by means of simulation. Finally, an online algorithm is presented for the exploitation of our study on implemented systems.

In this paper, we introduce a class of approaches that attempt to scale link-state routing by limiting the scope of link state update dissemination in space and over time. We present the first fundamental analysis of this generic class, which we call "Fuzzy Sighted Link State routing". Using a novel perspective on the "overhead"of a protocol that includes not only the overhead due to control messages but also due to route sub-optimality, we formulate an analytical model whose solution automatically leads to the best algorithm in this class. This algorithm is shown to have nearly the best possible asymptotic overhead for any routing algorithm -proactive or reactive. Simulation results are presented that compare the performance or several algorithms in this class

Typical rate-based traffic management schemes for real-time applications attempt to allocate resources by controlling the packet delivery to the resource arbitrator (scheduler). This control is typically based only on the characteristics of the particular (tagged) traffic stream and would fail to optimally adjust to non-nominal network conditions such as overload. In this paper, a dynamic regulation and scheduling (dynamic-R&S) scheme is proposed whose regulation function is modulated by both the tagged stream's characteristics and information capturing the state of the coexisting applications as provided by the scheduler. The performance of the proposed scheme-versus an equivalent static one-is investigated under both underload and overload traffic conditions. The substantially better throughput/jitter characteristics of the dynamic-R&S scheme are established.

The problem of traffic load estimation in a shared-medium contention-based network is investigated and applied to a hybrid fiber coaxial (HFC) cable network. In particular, an estimator that utilizes channel feedback to estimate network traffic load is presented. The performance of this estimator is investigated and is enhanced by introducing modifications which provide for a better reaction to load variations.

A new feedback based flow control scheme (proactive feedback) is introduced which can deliver better QoS to ABR applications than under the classical schemes, as well as guarantee a predefined level of QoS by setting properly the link utilization factor. The proactive feedback based flow control scheme can eliminate the reaction time of the ABR source rate adjustments to the network bandwidth usage changes through cooperation between the VBR sources and the network nodes. In addition to supporting 'stringent' ABR applications, the PF scheme can also support UBR applications and/or co-exist with classical schemes supporting 'less stringent' (or standard) ABR applications.

Traditional routing protocols for MANET networks are usually designed with a particular environment in mind and fail to adapt to the wide range of environments present in a MANET network. Because of the wide diversity of the conditions that may be encountered in a MANET network it seems that it would be difficult to effectively route information by engaging a single type of protocol. Instead, a multi-mode protocol should be developed which applies the appropriate "mode" or protocol that is determined to be effective at a given point in time and for the appropriate subset of the network. In this paper, two algorithms: the limited link state (LLS) and self-organizing (SO), that adapt to any MANET network condition-from small networks with nodes with low mobility to large networks with highly mobile nodes to an heterogeneous network with different classes of users-in order to make the most efficient routing decisions are discussed. These algorithms employ new metrics that capture the mobility and traffic pattern of (subsets of) the network, along with some attributes considered in the past (e.g. link stability). Once the instantaneous structure of the network is determined, the multi-mode routing protocol may select its 'mode' of operation.

In this work, the region of achievable quality-of-service (QoS) is precisely described for a system of real-time heterogeneous variable bit rate (VBR) sources competing for slots (packet transmission times) of a time division multiple access (TDMA) frame. The QoS for each application is defined in terms of a maximum tolerable packet-dropping probability. Packets may be dropped due to delay violations and channel induced errors. The region of achievable QoS is precisely described for an interference/resource limited network by considering the underlying TDMA-multiple access control (TDMA-MAC) structure and the physical channel. A simple QoS-sensitive error-control protocol that combats the effects of the wireless channel while satisfying the real-time requirements is proposed and its impact on the region of achievable QoS is evaluated. The results presented here clearly illustrate the negative impact of a poor channel and the positive impact of the employed error-control protocol on the achievable QoS. The region of achievable QoS vectors is central to the call admission problem, and in this work, it is used to identify a class of scheduling policies capable of delivering any achievable performance.

The objective of this paper is to determine the minimum system dropping rate (or, equivalently, dropping probability) induced by time division multiple access (TDMA) schemes supporting time-constrained applications with common maximum cell delay tolerance. Expressions are derived for the induced system dropping rate for various TDMA schemes with different overhead and the maximum number of users than can be admitted in the network without violating the maximum dropping rate constraint is determined. The system dropping rate achieved by suboptimal TDMA schemes is compared against the optimal (although ideal) TDMA scheme performance. The performance limiting factors associated with the suboptimal schemes are identified, and the magnitude of their (negative) impact is evaluated. Based on this information it is possible to point to performance improving modifications which should be pursued to the extent permitted by technological constraints. Finally, based on this derivations a network designer may choose the best TDMA scheme-among realizable variations of those considered here-to use in a particular situation.

The focus of this paper is on determining the call admission region and scheduling policies for a time-division multiple-access (wireless) system supporting heterogeneous real-time variable bit rate applications with distinct quality of service (QoS) requirements and traffic characteristics. The QoS is defined in terms of a maximum tolerable packet delay and dropping probability. A packet is dropped if it experiences excess delay. The call admission region is established for policies that are work-conserving (WC) and that satisfy the earliest due date (EDD) service criterion (WC-EDD policies). Such policies are known to optimize the overall system performance. In addition to the determination of the call admission region, this study leads also to the construction of scheduling policies that deliver any performance in the region established for WC-EDD policies. Finally, an upper bound on the call admission region that can be achieved under any policy (not limited to the WC-EDD policies) is determined.

In Wireless ATM networks transmission resources are shared among geographically disperse applications with diverse Quality of Service (QoS) requirements and traffic characteristics. To provide QoS guarantees and use the bandwidth efficiently, call admission and scheduling functions are necessary. These functions should ensure the delivery of the target QoS to the supported applications while achieving statistical multiplexing gains, without explicit and continuous exchange of information between sources and scheduler. In this paper the problem of sharing resources (slots of an up-link TDMA frame) among heterogeneous Variable Bit Rate (VBR) applications with diverse QoS requirements is addressed. The QoS requirements for each application is defined in terms of a maximum tolerable packet delay and dropping probability; a packet is dropped if it experiences excess delay. The region of achievable QoS vectors is established for policies that are work-conserving and satisfy the earliest due ...

In this paper, the modification of a tagged traffic stream due to statistical multiplexing is studied by presenting a numerical approach for the calculation of the tagged delay jitter and interdeparture processes. Both the single- and multiple-node cases are considered. Unlike the past work, the developed approach is applicable under both the standard first come first served (FCFS) policy and a peak-rate enforcing multiplexing policy. The latter policy can be adopted to reshape the tagged traffic stream within the network. Restoring a shaped traffic profile within the network may be necessary to obtain some of the benefits for which the original shaping is carried out at the network edge. This study also provides results and insight regarding the potential gains of reregulation within the network.

One of the most challenging problems in ATM network design is providing diversified quality of service (QoS) to applications with distinct characteristics. A flexible priority service policy for two applications (classes) with strict-and in general distinct-deadlines and different deadline violation rates (loss rates) is studied. The proposed policy is a generalization of the shortest time to extinction (STE) policy (or the early-due-date policy which discards expired cells). The relationship of this policy to other standard ones is also discussed. Performance measures such as cell loss, mean cell-delay and the tail of the cell-delay probability distribution are derived for each class. Numerical results illustrate the effectiveness of the studied priority scheme. Finally, a low-complexity implementation scheme is proposed, which does not require time-stamp-based sorting.

Traffic streams-originally shaped to comply with desired traffic descriptors-may suffer substantial distortion within an ATM network due to statistical multiplexing. As a consequence, traffic re-shaping within the network may be necessary. In this work the modification of a tagged traffic stream due to a series of multiplexing operations is studied. The standard FCFS service policy, as well as a peak-rate enforcing multiplexing discipline, are considered. Tagged cell delay, jitter and inter-departure processes are considered for the characterization of the tagged traffic stream.

A very flexible analysis approach is developed for the exact analysis of a non-gated TDM scheme, supporting time critical (TC) and time non- critical (TNC) packetized information. Correlations in the TNC traffic and spreading of the TC traffic over the entire frame can be accommodated, unlike in the past work.>

This paper considers the multiplexing of nondeterministic periodic traffic sources which deliver packets periodically according to an arbitrary i.i.d. batch arrival process. The proposed traffic sources are representative of the packet-stream periodicities commonly found in high-speed packet networks such as ATM. An exact analytical technique, which entails the solution of Markov chains whose dimensions are independent of the periods associated with the input sources, is presented for the study of a finite-capacity multiplexer fed by N of the proposed traffic models. Numerical results indicate that the source periodicities have a significant impact on the multiplexers performance. In fact, for some regions of operating conditions, even a Poisson traffic assumption is shown to provide an extremely pessimistic estimate of the queue performance measured in terms of packet-loss probabilities.>

A random, conflict-free slot assignment policy is adopted for the allocation of a common channel between two (non-communicating) stations. Although this policy is inferior to the optimal periodic, fixed slot assignment policy, it is shown than it achieves the performance of that optimal policy as the variance of the packet arrival process increases. The main advantage of the random, conflict-free slot assignment policy is that it is simple and always feasible unlike the optimal, periodic, fixed slot assignment policy. Furthermore, the proposed policy is easily implemented in a dynamically changing environment; the optimal such policy is derived and a simple strategy based on a threshold test is developed for the identification of the optimal such policy, when estimates of the traffic parameters are available. No such strategy is known for the adaptation of the parameters of the optimal periodic, fixed slot assignment policy. The developed analysis approach can be applied, to a great extent, to a system with more than two stations.>

A discrete-time queueing system operating under a two-level, consistent priority service policy is studied. The consistency of the policy guarantees that no low priority customer will be served before a previously (or simultaneously) arrived high priority one. Unlike the well known head of the line priority policy (which is consistent), the considered policy provides for limited service to low priority customers, even in the presence of high priority ones. The proposed policy may be viewed as a consistent version of the straightforward gated/limited service priority policy. It may also be viewed as a compromise between the head of the line priority policy and the straightforward gated/limited priority service policy. The customer service time is assumed to be deterministic and equal to one time unit, which makes the queueing model applicable to a packet communication network environment; potential relevant applications are presented. Based on renewal arguments, the theory of infinite dimensional linear equations and a work-conservation law, a general methodology is developed for the derivation of arbitrarily tight bounds on the induced mean packet delay.>

Some new traffic regulation schemes are defined in terms of a relief-spacing (or spacing of the allowance for cell delivery to the network) function. The class of open-loop traffic regulators (TR's) is defined in terms of relief-spacing functions which depend on some user-state; this class may be viewed as an extension of the Spacer-Controller defined in terms of some constant (user-state independent) relief-function. The optimal open-loop TR's are derived by formulating proper optimization problems and applying a Markov decision approach. Numerical results illustrate the improved performance of the optimal open-loop TR over that of the (constant relief-spacing) Spacer-Controller. Finally, the class of closed-loop TR's is defined in terms of relief-spacing functions which depend on both some user- and some network-state information and its optimal element is derived. The improved performance under the optimal closed-loop TR over that of the optimal open-loop TR is illustrated and their difference determines the performance gain if feedback information can become available on time.>

A discrete-time priority queuing policy is presented and analyzed. The three-queue system provides distinct service strategies, namely, the consistent-gated (c-G), 1-limited (L), and head-of-line (HoL), to each of the queues. The proposed service policy is potentially applicable to the modeling of network resource allocating policies in integrated services communication networks. In particular, it is shown that this queuing system provides an accurate analytical model for a distributed-queue dual-bus (DQDB) station, as well as a means for an appropriate evaluation of the correlation associated with key traffic processes in that network.>

The queue occupancy distribution of the distributed queue-dual-bus (DQDB) station is derived through the formulation and exact analysis of a queuing model with the following characteristic: the packet service time requirements depends on the state of an underlying Markov-structured process at the time when the packet is forwarded to the server (head of the queue). Numerical results are presented and compared with simulation results to evaluate the accuracy of the involved approximations.>

A discrete-time, single server, 3-queue system is presented and analyzed. A distinct service strategy, namely the consistent-gated (c-G), 1-limited (L) and head-of-line (HoL), is applied to each of the queues (c-G/L/HoL policy). It is shown that this queueing system provides for an accurate analytical model for a DQDB station, as well as a means for an approximate evaluation of the correlation associated with key traffic processes in that network. In addition, the developed queueing system could be useful for the modeling of the queueing behavior of an ATM link shared by high-priority, low priority and control traffic. Through an asymptotic analysis under heavy low-priority traffic, the worst case performance for the high priority traffic is determined. Furthermore, it is illustrated that the asymptotic analysis provides for a potentially tight delay bounding technique. Finally, the delay performance of the developed queueing system is compared to that of a similar system in which one of the queues receives 1-limited service and the other two exhaustive (HoL/sup -//L/HoL/sup +/ policy).>

A discrete-time queuing system supporting two classes of customers (packets of information) with different priorities is analyzed. Unlike the head-of-the-line priority policy, the priority policy considered provides for limited service to the low-priority class, even in the presence of high-priority customers (considerate system). At the same time, it guarantees that no low-priority customer will be served before a previously arrived high-priority one (guaranteed policy fairness). The proposed policy can be seen as a compromise between the head-of-the-line priority policy and the classical gated/limited service priority policy. A general methodology is developed for the analysis of this policy.>

The problem of multiplexing time-critical (TC) and time-non-critical (TNC) packetized information in an integrated services digital network (ISDN) is considered. An appropriate time division multiplexing (TDM) scheme is adopted to accommodate the strict delay requirements for the TC traffic. The resulting system is different from those previously considered in at least two aspects. First, the TNC traffic is assumed to exhibit correlation between consecutive slots. Second, the TC traffic is not necessarily accommodated in a contiguous subframe, but it may be spread over the whole frame according to any pattern. The nongated service policy is adopted for the service of the TNC traffic, unlike most of the past work. A very flexible approach is developed for the exact analysis of the proposed TDM scheme. Numerical results are derived for the case of TC traffic generated by voice sources.>

A Markov modulated process is developed for the exact characterization of the output process of a class of random access networks (C-RANs) and the mean packet delay induced by the central node of a star interconnecting scheme is calculated. The latter is obtained through an approximate analysis of an appropriate queueing system under Markov modulated arrivals. It is shown that the ALOHA network is a C-RAN. ALOHA networks interconnected according to a star topology are studied and delay results are obtained. These results are compared with those obtained under Bernoulli approximation on the network output processes and simulations.>

Two non-communicating stations are considered that share a time-slotted communication channel on a random slot assignment basis. The optimal assignment policy is derived, and a simple strategy, based on a threshold test, is developed for the implementation of the optimal policy in a dynamically changing environment. Although the random slot assignment policy is inferior to the optimal periodic, fixed slot assignment policy, it is shown that it achieves the performance of that policy as the variance of the packet arrival process increases; the optimal periodic, fixed slot assignment policy is not, in general, implementable and it is very difficult for it to adapt to the conditions of a dynamically changing environment.>

Simple models are developed for the description of a first-order Markovian (bursty) process modulated by merging and/or (independent or correlated) splitting operations. The models can be adopted for the packet traffic description in large networking structures, supporting multimedia packet traffic. This is due to the fact that the complexity of these models does not change as the number of points of transformation increases. The bursty traffic model is capable of describing a variety of packet sources. The induced packet delay at the merging points is evaluated. A queuing system is studied for this purpose under a general class of arrival processes, which include the adopted packet traffic models. Numerical results are obtained and are compared with simulations whenever approximations are involved.>

A binary feedback collision resolution algorithm is developed for a multiuser random access communication system with nonhomogeneous user population. The user population is split into two classes with different priorities. The throughput and delay analysis of the proposed algorithm are performed, and numerical results are obtained.>

A certain class of multiuser communication networks interconnected according to a star topology is analyzed. A type of Markov modulated Bernoulli model is developed for the exact characterization of their output processes, and the mean packet delay induced by the interconnected scheme is obtained through an approximate analysis of the queueing system, which is formulated in the central node of the star topology. It is shown that Aloha multiuser communication networks belong in the investigated class of networks. Delay analysis of Aloha networks interconnected according to a star topology is carried out, and some numerical results are obtained. These results and those obtained under Bernoulli approximation on the network output processes are compared with simulations.>

The queueing behavior of a statistical multiplexer with a finite number of input lines is studied. Each input line is assumed to deliver fixed-length packets of information according to a generally distributed process whose parameters depend on the state of an underlying finite-state Markov chain associated with each of the input lines. A method for the derivation of the moments of the buffer occupancy is developed, and the first and second moments are derived. The mean packet delay introduced by the statistical multiplexer is derived through Little's theorem. The applicability of the analyzed multiplexer in packet communication systems is illustrated through a simple example, and numerical results are provided for this case.>

Bernoulli and first-order Markov processes are used to approximate the output process of a class of slotted multiuser random-access communication networks. The output process is defined as the process of the successfully transmitted packets within the network. The parameters of the approximating processes are analytically calculated for a network operating under a specific random access algorithm. The applied methods are general and can be used to calculate these parameters in the case of any random access algorithm within a class. To evaluate the accuracy of the approximations, a star topology of interconnected multiuser random-access communication networks is considered. The mean time that a packet spends in the central node of the star topology is calculated under the proposed approximations of the output processes of the interconnected networks. The results are compared to simulation results of the actual system. It turns out that the memoryless approximation gives satisfactory results up to a certain per network traffic load. Beyond that per network traffic load, the first-order Markov process performs better.>

The concept of approximating the output process of slotted multiuser random-access communication networks (i.e. the process of the successfully transmitted packets within the networks) by a second-order Markov process is introduced. A method is developed for analytically calculating the parameters of the approximating process for a class of random-access algorithms. The method is illustrated by considering a specific random-access algorithm from that class. The mean time that a packet spends in the central node of a star topology of interconnected networks is incorporated in the evaluation of the accuracy of the proposed approximation. This quantity is calculated under the proposed approximation on the output processes of the interconnected networks and is compared to simulation results from the actual system. Results showing the accuracy of the proposed approximation for networks operating under a specific random-access algorithm are presented.>

A protocol for a multiuser packet radio communication channel is proposed. The basic functions of this protocol are determined by a modified stack-type limited sensing collision resolution algorithm. The protocol is a hybrid of a pure random-access scheme and a reservation scheme. A message consists of a number of packets that are capable of revealing the current activity of the channel. The performance of the system is investigated in terms of throughput and average message delay and analytical results are provided.>

Bernoulli and first-order Markov processes are used to approximate the output process of a class of slotted multiuser random-access communication networks. The parameters of the approximating processes are analytically calculated for a network operating under a specific random-access algorithm. The mean time that a packet spends in the central node of the star topology is calculated under the proposed approximations of the output processes of the interconnected networks. The results are compared with simulation results of the actual system. It turns out that the memoryless approximation gives satisfactory results up to a certain per-network-traffic load. Beyond that point, the first-order Markov processes performs better.>