Cryptanalytic time-memory trade-offs have been studied for 25 years and have benefited from several improvements since the original work of Hellman. The ensuing variants definitely improve the original trade-off but their real impact has never been evaluated in practice. We fill this lack by analyzing the perfect form of classic tables, distinguished point-based tables, and rainbow tables. We especially provide a thorough analysis of the latter variant, whose performances have never been formally calculated yet. Our analysis leads to the concept of a characteristic that enables to measure the intrinsic quality of a trade-off. We finally introduce a new technique based on checkpoints that still reduces the cryptanalysis time by ruling out false alarms probabilistically. Our analysis yields the exact gain of this approach and establishes its efficiency when applied on rainbow tables.

We consider the multiplexing of several variable bit rate (VBR) connections over one variable bit rate connection where the multiplexing uses a multiplexing buffer of size B. The VBR trunk is itself a connection and has a multidimensional connection descriptor, reflecting peak and sustainable rates. Given a cost function for the VBR trunk and a connection admission control (CAC) method for the input connections, we focus on the problem of finding the VBR trunk connection descriptor that minimizes the cost function and is able to accept set given set of VBR input connections. First, we show that, under reasonable assumptions on the cost function, the optimization problem can be reduced to a simpler one. Then we consider the homogeneous, loss-free case, for which we give an explicit CAC method. In this case, we find that, for all reasonable cost functions, the optimal VBR trunk is either of the CBR type, or is truly VBR, with a burst duration equal to the burst duration of the input connections. We show that the optimal peak cell rate is fixed for a given B (thus for a CBR trunk), and a VBR choice can only be an improvement. Lastly, we take as an example of the cost function the equivalent capacity of the VBR trunk. These results are expected to form the basis for a general method for a connection manager at a multiplexing node in an integrated services packet network.

We present a protocol for controlling a shared ATM multicast tree supporting many-to-many communication. The protocol supports one or several ATM virtual channel connections (VCCs) of the many-to-many type. The number of VCCs is independent of the number of endpoints. The protocol guarantees that there is no interleaving on any VCC of the tree. The protocol also guarantees that the traffic contract associated with the VCCs is respected, thus making it possible to use ordinary VCCs of the constant bit rate (CBR), variable bit rate (VBR), or unspecified bit rate (UBR) class. No resequencing server or cell buffering inside the network is required, and all cell forwarding is performed at the ATM layer. We describe the protocol both informally and formally.

We present a method for the automatic derivation of efficient protocol implementations from a formal specification. Optimized efficient protocol implementation has become an important issue in telecommunications systems engineering as recently network throughput has increased much faster than computer processing power. Efficiency will be attained by two measures. First, the inherent parallelism in protocol specifications will be exploited. Second, the order of execution of the operations involved in the processing of the protocol data will be allowed to differ from the order prescribed in the specification, thus allowing operations to be executed jointly and more efficiently. The method will be defined formally which is useful when implementing it as a tool.

We propose a formalized method that allows one to automatically derive an optimized implementation from the formal specification of a protocol. Our method starts with the SDL specification of a protocol stack. We first derive a data and control flow dependence graph from each SDL process. Then, in order to perform cross-layer optimizations we combine the dependence graphs of different SDL processes. Next, we determine the common path through the multi-layer dependence graph. We then parallelize this graph wherever possible which yields a relaxed dependence graph. Based on this relaxed dependence graph we interpret different optimization concepts that have been suggested in the literature, in particular lazy messages and combination of data manipulation operations. Together with these interpretations the relaxed dependence graph can be used as a foundation for or compile-time schedule on a sequential or parallel machine architecture. The formalization we provide allows our method to be embedded in a more comprehensive protocol engineering methodology.>