Fault Management (FM) is a cardinal feature in communication networks. One of the most common FM approaches is to use periodic keepalive messages. Hence, switches and routers are required to transmit a large number of FM messages periodically, requiring a hardware-based packet generator that periodically transmits a set of messages that are stored in an expensive on-chip memory. With the rapid growth of carrier networks, and as 5G technologies emerge, the number of users and the traffic rates are expected to significantly increase over the next few years. Consequently, we expect the on-chip memories used for FM to become a costly component in switch and router chips. We introduce a novel approach in which FM messages are stored in compressed form in the on-chip memory, allowing to significantly reduce the memory size. We present FM-Delta, a simple hardware-friendly delta encoding algorithm that allows FM messages to be compressed by a factor of 2.6. We show that this compression ratio is very close to the results of the zlib compression library, which requires much higher implementation complexity.

This paper addresses the problem of scheduling a single resource to handle requests for time-sensitive periodic services (i.e., data streams) jointly realizing a distributed application. We specifically consider the case, where the demand of each data stream is expressed as a weight relative to a network-wide cyclic schedule. Within this context, we consider the problem of minimizing the schedule length while satisfying the perfect periodicity constraints: the service intervals for the same data stream are fixed and each data stream is cyclically served exactly as many times as its demand. This problem is challenging, as serving a data stream in one time slot might enforce serving it at some specific time slots in the future. As a result, most of the existing solutions have relaxed either the periodicity or the demand constraints of the data streams. In contrast, we study the strict enforcement of both requirements through perfectly periodic schedules. We show that the considered problem is NP-hard and address special cases for which optimal schedules can be derived. We further discuss the more generic instance of the problem represented by an arbitrary number of data streams and demands. Specifically, we provide an approximation algorithm and an efficient greedy solution for such a general case of arbitrary weights. We conduct extensive simulations to evaluate the performance of the proposed solutions. Finally, we show that it is possible to relax the input demands to improve the communication performance at the cost of some other overhead (e.g., in terms of energy consumption).

Pipelines are widely used to increase throughput in multi-core chips by parallelizing packet processing while relying on virtualization. Typically, each packet type is served by a dedicated pipeline with several cores, each implementing a network service. However, with the increase in the number of packet types and their number of required services, there are not enough cores for pipelines. In this paper, we study pipeline sharing, such that a single pipeline can be used to serve several packet types. Pipeline sharing decreases the needed total number of cores, but typically increases pipeline lengths and therefore packet delays. We consider two novel optimization problems of allocating cores between different packet types such that the average or the worst-case delay is minimized. We study the two problems and suggest optimal algorithms that apply under different assumptions on the input. We also present greedy algorithms for the general case. Last, we examine our solutions on synthetic examples as well as on real-life applications and demonstrate that they often achieve close-to-optimal delays.

Stackable Routers, i.e. a class of independent routing units operating together as a single router, constitute an affordable scalable approach for coping with the growing networking requirements of organizations. In this study, we investigate several design problems of stackable routers and develop novel schemes for improving their performance. First, we formalize a mathematical model for optimizing the network topology in terms of throughput and delay, while obeying constraints in the number of ports of each internal routing unit. We then consider the problem of minimizing the diameter of the interconnection topology, as a measure of maximum delay, and establish efficient near-to optimal (explicit) topologies. Furthermore, we also consider the problem of maximizing the throughput of a stackable router. We show its hardness and derive bounds for the optimal solution. While, traditionally, the different routing units of a stackable router are linked together in a ring topology, through simulations we show that a major improvement in the diameter of stackable routers can be accomplished even through the employment of randomly-generated topologies. Finally, we investigate the basic problem of constructing a feasible stackable router and establish some fundamental properties of the required structure of the routing units.

We study a perfectly-periodic scheduling problem of a resource shared among several users. Each user is characterized by a weight describing the number of times it has to use the resource within a cyclic schedule. With the constraint that the resource can be used by at most one user in each time slot, we would like to find a schedule with a minimal time period (number of time slots), in which each user is served once in a fixed number of time slots according to its required total number of times. As many other variants of periodic-scheduling problems, we first prove that the problem is NP-hard. We then describe different cases for which we can calculate the exact value of the optimal time period and present algorithms that obtain optimal schedules. We also study the optimal time period in the case of two users with random weights drawn according to known distributions. We then discuss the general case of arbitrary number of users with general weights and provide approximation algorithms that achieve schedules with guaranteed time periods. Last, we conduct simulations to examine the presented analysis.

With the rise of datacenter virtualization, the number of entries in the forwarding tables of datacenter switches is expected to scale from several thousands to several millions. Unfortunately, such forwarding table sizes would not fit on-chip memory using current implementations. In this paper, we investigate the compressibility of forwarding tables. We first introduce a novel forwarding table architecture with separate encoding in each column. It is designed to keep supporting fast random accesses and fixed-width memory words. Then, we show that although finding the optimal encoding is NP-hard, we can suggest an encoding whose memory requirement per row entry is guaranteed to be within a small additive constant of the optimum. Next, we analyze the common case of two-column forwarding tables, and show that such tables can be presented as bipartite graphs. We deduce graph-theoretical bounds on the encoding size. We also introduce an algorithm for optimal conditional encoding of the second column given an encoding of the first one. In addition, we explain how our architecture can handle table updates. Last, we evaluate our suggested encoding techniques on synthetic forwarding tables as well as on real-life tables.

With the rise of datacenter virtualization, the number of entries in forwarding tables is expected to scale from several thousands to several millions. Unfortunately, such forwarding table sizes can hardly be implemented today in on-chip memory. In this paper, we investigate the compressibility of forwarding tables. We first introduce a novel forwarding table architecture with separate encoding in each column. It is designed to keep supporting fast random accesses and fixed-width memory words. Then, we suggest an encoding whose memory requirement per row entry is guaranteed to be within a small additive constant of the optimum. Next, we analyze the common case of two-column forwarding tables, and show that such tables can be presented as bipartite graphs. We deduce graph-theoretical bounds on the encoding size. We also introduce an algorithm for optimal conditional encoding of the second column given an encoding of the first one. In addition, we explain how our architecture can handle table updates. Last, we evaluate our suggested encoding techniques on synthetic forwarding tables as well as on real-life tables.

Wireless sensor networks represent a new generation of real time traffic communications and high data rate sensor applications such as structural health monitoring and control. In this work we study some problems of data gathering in sensor networks. The information that the sensor collect about their environment must be delivered in timely fashion to collecting central processing system. We prove in this research that finding the optimal schedule in order to minimize the maximal delivery time with restrictions on the total idle time allowed in a general network topology with a single designated destination base station is NP-hard. We also refer to a special case of linear network topology for which we present several optimization algorithms: First we present an algorithm to minimize the number of tardy messages. We then present an algorithm to minimize the maximal lateness. Finally, we present an algorithm to minimize the maximal completion time. All of the scheduling optimization algorithms.