Identifying the network-wide forwarding behaviors of a packet is essential for many network management applications, including rule verification, policy enforcement, attack detection, traffic engineering, and fault localization. Current tools that can perform packet behavior identification either incur large time and memory costs or do not support real-time updates. In this paper, we present AP Classifier, a control plane tool for packet behavior identification. AP Classifier is developed based on the concept of atomic predicates, which can be used to characterize the forwarding behaviors of packets. Experiments using the data plane network state of two real networks show that the processing speed of AP Classifier is faster than existing tools by at least an order of magnitude. Furthermore, AP Classifier uses very small memory and is able to support real-time updates.

Packet transformers are widely used in ISPs, datacenter infrastructures, and layer-2 networks. Existing network verification tools do not scale to large networks with transformers (e.g., MPLS, IP-in-IP, and NAT). Toward scalable verification, we conceived a novel packet equivalence relation. For networks with packet transformers, we first present a formal definition of the packet equivalence relation. Our transformer model is general, including most transformers used in real networks. We also present a new definition of atomic predicates that specify the coarsest equivalence classes of packets in the packet space. We designed an algorithm for computing these atomic predicates. We built a verifier, named Atomic Predicates for Transformers, and evaluated its performance using four network data sets with MPLS tunnels, IP-in-IP tunnels, and NATs. For a provider cone data set with 11.6 million forwarding rules, 92 routers, 1920 duplex ports, and 40 MPLS tunnels which use 170 transformers, APT used only 0.065 s, on average, to compute the reachability tree from a source port to all other ports for all packets and perform loop detection as well. For the Stanford and Internet2 data sets with NATs, APT is faster than HSA (Hassel in C implementation) by two to three orders of magnitude. By working with atomic predicates instead of individual packets, APT achieves verification performance gains by orders of magnitude.

We present the architecture and protocols of ROME, a layer-2 network designed to be backwards-compatible with Ethernet and scalable to tens of thousands of switches and millions of end-hosts. Such large-scale networks are needed for emerging applications including data center networks, wide area networks, and metro Ethernet. ROME is based upon a recently developed greedy routing protocol, greedy distance vector (GDV). Protocol design innovations in ROME include a stateless multicast protocol, a Delaunay distributed hash table (DHT), as well as routing and host discovery protocols for a hierarchical network. ROME protocols do not use broadcast and provide both control-plane and data-plane scalability. Extensive experimental results from a packet-level event-driven simulator, in which ROME protocols are implemented in detail, show that ROME protocols are efficient and scalable to metropolitan size. Furthermore, ROME protocols are highly resilient to network dynamics. The routing latency of ROME is only slightly higher than shortest-path latency. To demonstrate scalability, we provide simulation performance results for ROME networks with up to 25 000 switches and 1.25 million hosts.

Greedy routing has been applied to both wireline and wireless networks due to its scalability of routing state and resiliency to network dynamics. In this work, we solve a fundamental problem in applying greedy routing to networks with arbitrary topologies, i.e., how to construct node coordinates such that greedy routing can find near-optimal routing paths for various routing metrics. We propose Greedy Distance Vector (GDV), the first greedy routing protocol designed to optimize end-to-end path costs using any additive routing metric, such as: hop count, latency, ETX, ETT, etc. GDV requires no physical location information. Instead, it relies on a novel virtual positioning protocol, VPoD, which provides network distance embedding. Using VPoD, each node assigns itself a position in a virtual space such that the Euclidean distance between any two nodes in the virtual space is a good estimate of the routing cost between them. Experimental results using both real and synthetic network topologies show that the routing performance of GDV is better than prior geographic routing protocols when hop count is used as metric and much better when ETX is used as metric. As a greedy routing protocol, the routing state of GDV per node remains small as network size increases. We also show that GDV and VPoD are highly resilient to dynamic topology changes.

Network management will benefit from automated tools based upon formal methods. Several such tools have been published in the literature. We present a new formal method for a new tool, Atomic Predicates (AP) Verifier, which is much more time and space efficient than existing tools. Given a set of predicates representing packet filters, AP Verifier computes a set of atomic predicates, which is minimum and unique. The use of atomic predicates dramatically speeds up computation of network reachability. We evaluated the performance of AP Verifier using forwarding tables and ACLs from three large real networks. The atomic predicate sets of these networks were computed very quickly and their sizes are surprisingly small. Real networks are subject to dynamic state changes over time as a result of rule insertion and deletion by protocols and operators, failure and recovery of links and boxes, etc. In a software-defined network, the network state can be observed in real time and thus may be controlled in real time. AP Verifier includes algorithms to process such events and check compliance with network policies and properties in real time. We compare time and space costs of AP Verifier with Header Space and NetPlumber using datasets from the real networks.

Identifying the network-wide forwarding behaviors of a packet is essential for many network management applications, including rule verification, policy enforcement, attack detection, traffic engineering, and fault localization. Current tools that can perform packet behavior identification either incur large time and memory costs or do not support real-time updates. In this paper we present AP Classifier, a control plane tool for packet behavior identification. AP Classifier is developed based on the concept of atomic predicates which can be used to characterize the forwarding behaviors of packets. Experiments using the data plane network state of two real networks show that the processing speed of AP Classifier is faster than existing tools by at least an order of magnitude. Furthermore, AP Classifier uses very small memory and is able to support real-time updates.

To debug reach ability problems, a network operator often asks operators of other networks for help by telephone or email. We present a new protocol, COVE, for automating the exchange of data plane reach ability information between networks in a business relationship. A network deploys COVE in a host (its local verifier) which can construct both forward and reverse reach ability trees in the Internet data plane for the network's provider/customer cone. Each edge in a tree is annotated by a set of packets that can traverse the edge. COVE was designed with partial deployment in mind. Reachable networks that do not deploy COVE are leaf nodes in reach ability trees. Partial trees are useful. We constructed an Internet dataset of 2, 649 ASes and performed experiments in which up to 170 workstations ran COVE as local verifiers to construct forward and reverse provider (also customer) trees for ASes. The results of these experiments demonstrate scalability of COVE to very large ASes in the Internet. We illustrate applications of COVE to solve the following network management problems: evaluating inbound load balancing policies, what-if analysis before adding a new provider, finding additional paths, configuring default routes as backup, black hole detection, and persistent forwarding loop detection.

Network management will benefit from automated tools based upon formal methods. Several such tools have been published in the literature. We present a new formal method for a new tool, Atomic Predicates (AP) Verifier, which is much more time and space efficient than existing tools. Given a set of predicates representing packet filters, AP Verifier computes a set of atomic predicates, which is minimum and unique. The use of atomic predicates dramatically speeds up computation of network reachability. We evaluated the performance of AP Verifier using forwarding tables and ACLs from three large real networks. The atomic predicate sets of these networks were computed very quickly and their sizes are surprisingly small. Real networks are subject to dynamic state changes over time as a result of rule insertion and deletion by protocols and operators, failure and recovery of links and boxes, etc. In a software-defined network, the network state can be observed in real time and thus may be controlled in real time. AP Verifier includes algorithms to process such events and check compliance with network policies and properties in real time. We compare time and space costs of AP Verifier with NetPlumber using datasets from the real networks.

Almost all geographic routing protocols have been designed for 2-D. We present a novel geographic routing protocol, named Multihop Delaunay Triangulation (MDT), for 2-D, 3-D, and higher dimensions with these properties: 1) guaranteed delivery for any connected graph of nodes and physical links, and 2) low routing stretch from efficient forwarding of packets out of local minima. The guaranteed delivery property holds for node locations specified by accurate, inaccurate, or arbitrary coordinates. The MDT protocol suite includes a packet forwarding protocol together with protocols for nodes to construct and maintain a distributed MDT for routing. We present the performance of MDT protocols in 3-D and 4-D as well as performance comparisons of MDT routing versus representative geographic routing protocols for nodes in 2-D and 3-D. Experimental results show that MDT provides the lowest routing stretch in the comparisons. Furthermore, MDT protocols are specially designed to handle churn, i.e., dynamic topology changes due to addition and deletion of nodes and links. Experimental results show that MDT's routing success rate is close to 100% during churn, and node states converge quickly to a correct MDT after churn.

We present the architecture and protocols of ROME, a layer-2 network designed to be backwards compatible with Ethernet and scalable to tens of thousands of switches and millions of end hosts. ROME is based upon a recently developed geographic routing protocol, greedy distance vector (GDV). Switches in ROME do not need any location information. Protocol design innovations in ROME include a stateless multicast protocol, a Delaunay DHT, as well as routing and host discovery protocols for a hierarchical network. ROME protocols do not use broadcast. Extensive experimental results from a packet-level event-driven simulator, in which ROME protocols are implemented in detail, show that ROME protocols are efficient and scalable to metropolitan size. Furthermore, ROME protocols are highly resilient to network dynamics. The routing latency of ROME is only slightly higher than shortest-path latency. To demonstrate scalability, we provide simulation performance results for ROME networks with up to 25,000 switches and 1.25 million hosts.

Greedy Distance Vector (GDV) is the first geographic routing protocol designed to optimize end-to-end path costs using any additive routing metric, such as: hop count, latency, ETX, ETT, etc. GDV requires no node location information. Instead, GDV uses estimated routing costs to destinations which are locally computed from node positions in a virtual space. GDV makes use of VPoD, a new virtual positioning protocol for wireless networks. Prior virtual positioning systems (e.g., Vivaldi and GNP) were designed for Internet hosts and require that each host measures latencies (routing costs) to distant hosts or landmarks. VPoD does not have this requirement and uses only routing costs between directly connected nodes. Experimental results show that the routing performance of GDV is better than prior geographic routing protocols when hop count is used as metric and much better when ETX is used as metric. As a geographic protocol, the storage cost of GDV per node remains low as network size increases. GDV provides guaranteed delivery for nodes placed in 2D, 3D, and higher dimensions. We also show that GDV and VPoD are highly resilient to dynamic topology changes.

Almost all geographic routing protocols have been designed for 2D. We present a novel geographic routing protocol, named MDT, for 2D, 3D, and higher dimensions with these properties: (i) guaranteed delivery for any connected graph of nodes and physical links, and (ii) low routing stretch from efficient forwarding of packets out of local minima. The guaranteed delivery property holds for node locations specified by accurate, inaccurate, or arbitrary coordinates. The MDT protocol suite includes a packet forwarding protocol together with protocols for nodes to construct and maintain a distributed MDT graph for routing. We present the performance of MDT protocols in 3D and 4D as well as performance comparisons of MDT routing versus representative geographic routing protocols for nodes in 2D and 3D. Experimental results show that MDT provides the lowest routing stretch in the comparisons. Furthermore, MDT protocols are specially designed to handle churn, i.e., dynamic topology changes due to addition and deletion of nodes and links. Experimental results show that MDT's routing success rate is close to 100% during churn and node states converge quickly to a correct MDT graph after churn.

We present simulation results of a wireless routing protocol as well as join, leave, failure, and maintenance protocols, for nodes in a d-dimensional Euclidean space (d ≥ 2).

We present a protocol, named RadGRPM, which runs on a distributed Delaunay triangulation of a set of nodes in Euclidean space. Given coordinates of the source node and a radius, RadGRPM multicasts a message to all nodes within the given radius from the source. Since the target nodes are all within a spherical region centered at the source, RadGRPM provides a special kind of geocast, which we call radius geocast. A multicast tree is not explicitly maintained in RadGRPM. Each node determines the next-hop nodes to forward a message solely using local information (the coordinates of its neighbors) together with the radius and coordinates of the center carried in the message. We prove that RadGRPM delivers a message to all nodes within the given radius. RadGRPM is also efficient in the sense that very few nodes within the radius receive duplicate messages, and nodes outside the radius receive no message. Extensive experimental results are presented to investigate the performance and characteristics of RadGRPM. Furthermore, we show that RadGRPM can be combined with unicast greedy routing to provide geocast to any spherical region not centered at the source node.

We design a new suite of protocols for a set of nodes in d-dimension (d > 1) to construct and maintain a distributed Delaunay triangulation (DT) in a dynamic environment. The join, leave, and failure protocols in the suite are proved to be correct for a single join, leave, and failure, respectively. For a system under churn, it is impossible to maintain a correct distributed DT continually. We define an accuracy metric such that accuracy is 100% if and only if the distributed DT is correct. The suite also includes a maintenance protocol designed to recover from incorrect system states and to improve accuracy. In designing the protocols, we make use of two novel observations to substantially improve protocol efficiency. First, in the neighbor discovery process of a node, many replies to the nodepsilas queries contain redundant information. Second, the use of a new failure protocol that employs a proactive approach to recovery is better than the reactive approaches used in prior work. Experimental results show that our new suite of protocols maintains high accuracy for systems under churn and each system converges to 100% accuracy after churning stopped. They are much more efficient than protocols in prior work.

Delaunay triangulation (DT) is a useful geometric structure for networking applications. In this paper we investigate the design of join, leave, and maintenance protocols to construct and maintain a distributed DT dynamically. We define a distributed DT and present a necessary and sufficient condition for a distributed DT to be correct. This condition is used as a guide for protocol design. We present join and leave protocols as well as correctness proofs for serial joins and leaves. In addition, to handle concurrent joins and leaves as well as node failures, we present a maintenance protocol. An accuracy metric is defined for a distributed DT. Experimental results show that our join, leave and maintenance protocols are scalable, and they achieve high accuracy for systems under churn and with node failures. We also present application protocols for greedy routing, clustering, broadcast, and multicast within a radius, and discuss and prove their correctness.

Reliability is critical to a variety of network applications. Unfortunately, due to lack of QoS support across ISP boundaries, it is difficult to achieve even two 9s (99%) reliability in toadyism Internet. In this paper, we propose SmartTunnel, an end-to-end approach to achieving reliability. A SmartTunnel is a logical point-to-point tunnel between two end points that spans multiple physical network paths. It achieves reliability by strategically allocating traffic onto multiple paths and performing FEC coding. Such an end-to-end approach requires no explicit QoS support from intermediate ISPs, and is therefore easy to deploy in today's Internet. To fully realize the potential of SmartTunnel, we analytically derive near-optimal traffic allocation schemes that minimize loss rates. We extensively evaluate our approach using trace-driven simulations, ns-2 simulations, and experiments on PlanetLab. Our results clearly demonstrate that SmartTunnel is effective in achieving high reliability.

Abstract — Internet paths sharing the same bottleneck can be identified using several shared congestion detection techniques. However, all of these techniques have been designed to detect shared congestion between a pair of paths. To cluster N paths by shared congestion, a straightforward approach of using pairwise tests would require O(N 2) time complexity. In this paper, we present a scalable approach to cluster Internet paths based on DCW (Delay Correlation with Wavelet denoising) which does not require a common end point between paths. We present a function to map each path’s measurement data into a point in a multidimensional space such that points are close to each other if and only if the corresponding paths share congestion. Because points in the space are indexed using a tree-like structure, the computational complexity of clustering N paths can be reduced to O(N log N). The indexing overhead can be further improved by reducing dimensionality of the space through wavelet transform. Computation cost is kept low by reusing for dimensionality reduction the same wavelet coefficients obtained in DCW. Our approach is evaluated by simulations and found to be effective for a large N. The tradeoff between dimensionality and clustering accuracy is shown empirically. I.

In secure group communications, there are both rekey and data traffic. We propose to use application-layer multicast to support concurrent rekey and data transport. Rekey traffic is bursty and requires fast delivery. It is desired to reduce rekey bandwidth overhead as much as possible since it competes for bandwidth with data traffic. Towards this goal, we propose a multicast scheme that exploits proximity in the underlying network. We further propose a rekey message splitting scheme to significantly reduce rekey bandwidth overhead at each user access link and network link. We formulate and prove correctness properties for the multicast scheme and rekey message splitting scheme. We have conducted extensive simulations to evaluate our approach. Our simulation results show that our approach can reduce rekey bandwidth overhead from several thousand encrypted new keys (encryptions, in short) to less than ten encryptions for more than 90% of users in a group of 1024 users.

This work presents a comprehensive theoretical framework for memoryless window-based congestion control protocols that are designed to converge to fairness and efficiency. We first derive a necessary and sufficient condition for stepwise convergence to fairness. Using this, we show how fair window increase/decrease policies can be constructed from suitable pairs of monotonically nondecreasing functions. We generalize this to smooth protocols that converge over each congestion epoch. The framework also includes a simple method for incorporating TCP-friendliness. Well-studied congestion control protocols such as TCP, GAIMD, and Binomial congestion control can be constructed using this method. Thus, we provide a common framework for the analysis of such window-based protocols. We also present two new congestion control protocols for streaming media-like applications as examples of protocol design in this framework: The first protocol, LOG, has the objective of reconciling the smoothness requirement of an application with the need for a fast dynamic response to congestion. The second protocol, SIGMOID, guarantees a minimum bandwidth for an application but behaves exactly like TCP for large windows.

The overlay network approach is an emerging technique to satisfy the strict requirements for various real-time multimedia services. However, overlay networks suffer from a shared congestion problem since each unicast flow may interfere with each other in the common underlying links. Most previous techniques to detect shared congestion have limitations when applied as a general solution, since they assume perfect synchronization between probing packets. However, our recent work shows that a technique based on wavelet denoising can overcome the limitations by mitigating the interfering effects such as synchronization offset and the random fluctuations of queueing delay; the proposed technique provides a more robust and accurate detection in the presence of a large amount of synchronization offset In this paper, wavelet denoising is tailored to the characteristics of queueing delay on packet networks. The wavelet denoising based technique is verified through extensive simulations. The efficacy of the proposed approach is demonstrated by the detection accuracy and convergence speed.

Per-flow congestion control helps endpoints fairly and efficiently share network resources. Better utilization of network resources can be achieved, however, if congestion management algorithms can determine when two different flows share a congested link. Such knowledge can be used to implement cooperative congestion control or improve the overlay topology of a P2P system. Previous techniques to detect shared congestion either assume a common source or destination node, drop-tail queueing, or a single point of congestion. We propose in this paper a novel technique, applicable to any pair of paths on the Internet, without such limitations. Our technique employs a signal processing method, wavelet denoising, to separate queueing delay caused by network congestion from various other delay variations. Our wavelet-based technique is evaluated through both simulations and Internet experiments. We show that, when detecting shared congestion of paths with a common endpoint, our technique provides faster convergence and higher accuracy while using fewer packets than previous techniques, and that it also accurately determines when there is no shared congestion. Furthermore, we show that our technique is robust and accurate for paths without a common endpoint or synchronized clocks; more specifically, it can tolerate a synchronization offset of up to one second between two packet flows.

No abstract available.

Measurement studies indicate a high rate of node dynamics in p2p systems. In this paper, we address the question of how high a rate of node dynamics can be supported by structured p2p networks. We confine our study to the hypercube routing scheme used by several structured p2p systems. To improve system robustness and facilitate failure recovery, we introduce the property of K-consistency, K ≥ 1, which generalizes consistency defined previously. (Consistency guarantees connectivity from any node to any other node.) We design and evaluate a failure recovery protocol based upon local information for K-consistent networks. The failure recovery protocol is then integrated with a join protocol that has been proved to construct K-consistent neighbor tables for concurrent joins. The integrated protocols were evaluated by a set of simulation experiments in which nodes joined a 2000-node network and nodes (both old and new) were randomly selected to fail concurrently over 10,000 seconds of simulated time. In each such "churn" experiment, we took a "snapshot" of neighbor tables in the network once every 50 seconds and evaluated connectivity and consistency measures over time as a function of the churn rate, timeout value in failure recovery, and K. Storage and communication overheads were also evaluated. We found our protocols to be effective, efficient, and stable for an average node lifetime as low as 8.3 minutes (the median lifetime measured for Napster and Gnutella was 60 minutes [10]).

In secure group communications, a key server can deliver a group-oriented rekey message [Chung Kei Wong et al., 1998] to a large number of users efficiently using IP multicast. For reliable delivery, Keystone [Chung Kei Wong and Lam, SS, 2000] proposed the use of forward error correction (FEC) in an initial multicast, followed by the use of unicast delivery for users that cannot recover their new keys from the multicast. In this paper, we investigate how to limit unicast recovery to a small fraction /spl gamma/ of the user population. By specifying a very small /spl gamma/, almost all users in the group will receive their new keys within a single multicast round. We present analytic models for deriving /spl gamma/ as a function of the amount of FEC redundant information and the keying interval duration for both Bernoulli and two-state Markov Chain loss models. From our analyses, we conclude that /spl gamma/ decreases roughly at an exponential rate as h increases. we then present a protocol designed to adaptively adjust (h,T) to achieve a specified /spl gamma/. In particular, our protocol chooses from among all feasible (h,T) pairs one with h and T values close to their feasible minima. Our protocol also adapts to an increase in network traffic. Simulation results using ns-2 show that with network congestion our adaptive FEC protocol can still achieve a specified /spl gamma/ by adjusting values of h and T.

Internet radio and television stations require significant bandwidth to support delivery of high quality audio and video streams to a large number of receivers. IP multicast is an appropriate delivery model for these applications. However, widespread deployment of IP multicast on the Internet is unlikely in the near future. An alternative is to build a multicast tree in the application layer Previous studies have addressed tree construction in the application layer However most of them focus on reducing delay. Few systems have been designed to achieve a high throughput for bandwidth-intensive applications. In this paper we present a distributed algorithm to build an application-layer tree. We prove that our algorithm finds a tree such that the average incoming rate of receivers in the tree is maximized (under certain network model assumptions). We also describe protocols that implement the algorithm. For implementation on the Internet, there is a tradeoff between the overhead of available bandwidth measurements and fast convergence to the optimal tree. This tradeoff can be controlled by tuning some parameters in our protocols. Our protocols are also designed to maintain a small number, O(log n), of soft states per node to adapt to network changes and node failures.

In a system proposed by Plaxton, Rajaraman and Richa (PRR), the expected cost of accessing a replicated object was proved to be asymptotically optimal for a static set of nodes and pre-existence of consistent and optimal neighbor tables in nodes [9]. To implement PRR's hypercube routing scheme in a dynamic, distributed environment, such as the Internet, various protocols are needed (for node joining, leaving, table optimization, and failure recovery). In this paper we first present a conceptual foundation, called C-set trees, for protocol design and reasoning about consistency. We then present the detailed specification of a join protocol. In our protocol, only nodes that are joining need to keep extra state information about the join process. We present a rigorous proof that the join protocol generates consistent neighbor tables for an arbitrary number of concurrent joins. The crux of our proof is based upon induction on a C-set tree. Our join protocol can also be used for building consistent neighbor tables for a set of nodes at network initialization time. Lastly, we present both analytic and simulation results on the communication cost of a join in our protocol.

We present the design and specification of a protocol for scalable and reliable group rekeying together with performance evaluation results. The protocol is based upon the use of key trees for secure groups and periodic batch rekeying. At the beginning of each rekey interval, the key server sends a rekey message to all users consisting of encrypted new keys (encryptions, in short) carried in a sequence of packets. We present a scheme for identifying keys, encryptions, and users, and a key assignment algorithm that ensures that the encryptions needed by a user are in the same packet. Our protocol provides reliable delivery of new keys to all users eventually. It also attempts to deliver new keys to all users with a high probability by the end of the rekey interval. For each rekey message, the protocol runs in two steps: a multicast step followed by a unicast step. Proactive forward error correction (FEC) multicast is used to reduce delivery latency. Our experiments show that a small FEC block size can be used to reduce encoding time at the server without increasing server bandwidth overhead. Early transition to unicast, after at most two multicast rounds, further reduces the worst-case delivery latency as well as user bandwidth requirement. The key server adaptively adjusts the proactivity factor based upon past feedback information; our experiments show that the number of NACKs after a multicast round can be effectively controlled around a target number. Throughout the protocol design, we strive to minimize processing and bandwidth requirements for both the key server and users.

We present a comprehensive theoretical framework for window-based congestion control protocols that are designed to converge to fairness and efficiency. We first derive a sufficient condition for convergence to fairness. Using this, we show how fair window increase/decrease policies can be constructed from suitable pairs of monotonically non-decreasing functions. We show that well-studied protocols such as TCP, GAIMD (general additive-increase multiplicative-decrease) and binomial congestion control can be constructed using this method. Thus we provide a common framework for the analysis of such window-based protocols. To validate our approach, we present experimental results for a new TCP-friendly protocol, LOG, designed using this framework with the objective of reconciling the smoothness requirement of streaming media-like applications with the need for a fast dynamic response to congestion.

We investigate the fairness, smoothness, responsiveness, and aggressiveness of TCP and three representative TCP-friendly congestion control protocols: GAIMD, TFRC, and TEAR. The properties are evaluated both analytically and via simulation by studying protocol responses to three network environment changes. The first environment change is the inherent fluctuations in a stationary network environment. Under this scenario, we consider three types of sending rate variations: smoothness, short-term fairness, and long-term fairness. For a stationary environment, we observe that smoothness and fairness are positively correlated. We derive an analytical expression for the sending rate coefficient of variation for each of the four protocols. These analytical results match well with experimental results. The other two environment changes we study are a step increase of network congestion and a step increase of available bandwidth. Protocol responses to these changes reflect their responsiveness and aggressiveness, respectively.

In secure group communications, users of a group share a common group key. A key server sends the group key to authorized new users as well as performs group rekeying for group users whenever the key changes. In this paper, we investigate scalability issues of reliable group rekeying, and provide a performance analysis of our group key management system (called keygem) based upon the use of key trees. Instead of rekeying after each join or leave, we use periodic batch rekeying to improve scalability and alleviate out-of-sync problems among rekey messages as well as between rekey and data messages. Our analyses show that batch rekeying can achieve large performance gains. We then investigate reliable multicast of rekey messages using proactive FEC. We observe that rekey transport has an eventual reliability and a soft real-time requirement, and that the rekey workload has a sparseness property, that is, each group user only needs to receive a small fraction of the packets that carry a rekey message sent by the key server. We also investigate tradeoffs between server and receiver bandwidth requirements versus group rekey interval, and show how to determine the maximum number of group users a key server can support.

Many emerging web and Internet applications are based on a group communications model. Thus, securing group communications is an important Internet design issue. The key graph approach has been proposed for group key management. Key tree and key star are two important types of key graphs. Previous work has been focused on individual rekeying, i.e., rekeying after each join or leave request. In this paper, we first identify two problems with individual rekeying: inefficiency and an out-of-sync problem between keys and data. We then propose the use of periodic batch rekeying which can improve efficiency and alleviate the out-of-sync problem. We devise a marking algorithm to process a batch of join and leave requests. We then analyze the key server's processing cost for batch rekeying. Our results show that batch rekeying, compared to individual rekeying, saves server cost substantially. We also show that when the number of requests in a batch is not large, the best key tree degree is four; otherwise, key star (a special key tree with root degree equal to group size) outperforms small-degree key trees. Keywords: Secure group communications, group key management, rekeying. 1.

Multicast sessions may have a large number of receivers with heterogeneous reception capacities. To accommodate this heterogeneity various multi-rate schemes, based upon the use of layering or replication, have been proposed. We consider the optimal partitioning of receivers into groups for multi-rate schemes. For a general class of utility functions, we formulate the partitioning problem as an optimization problem to maximize the sum of receiver utilities. We present an efficient dynamic programming algorithm to solve the partitioning problem, and prove that the solution it finds is optimal. We also show that the majority of the benefit of a multi-rate scheme can be gained by using a small number of groups (or layers), say 4 to 5. To illustrate our solution approach, we apply it to the case where receiver capacities are determined by multi-rate max-min fair rates. A complete protocol for receiver rates computation, rates collection, optimal receiver partitioning, and receiver adaptation is presented. We then compare our approach with other multi-rate approaches as well as a single-rate approach. Experimental results show that our approach provides substantial performance improvements.

Instead of the increase-by-one decrease-to-half strategy used in TCP for congestion window adjustment, we consider the general case such that the increase value and decrease ratio are parameters. That is, in the congestion avoidance state, the window size is increased by /spl alpha/ per window of packets acknowledged and it is decreased to /spl beta/ of the current value when there is congestion indication. We refer to this window adjustment strategy as general additive increase multiplicative decrease (GAIMD). We present the (mean) sending rate of a GAIMD flow as a function of /spl alpha/, /spl beta/, loss rate, mean round-trip time, mean timeout value, and the number of packets acknowledged by each ACK. We conducted extensive experiments to validate this sending rate formula. We found the formula to be quite accurate for a loss rate of up to 20%. We also present a simple relationship between /spl alpha/ and /spl beta/ for a GAIMD flow to be TCP-friendly, that is, for the GAIMD flow to have approximately the same sending rate as a TCP flow under the same path conditions. We present results from simulations in which TCP-friendly GAIMD flows (/spl alpha/=0.31, /spl beta/=7/8) compete for bandwidth with TCP Reno flows and with TCP SACK flows, on a DropTail link as well as on a RED link. We found that the GAIMD flows were highly, TCP-friendly. Furthermore, with /spl beta/ at 7/8 instead of 1/2, these GAIMD flows have reduced rate fluctuations compared to TCP flows.

Many emerging network applications are based upon a group communications model. As a result, securing group communications, i.e., providing confidentiality, authenticity, and integrity of messages delivered between group members, will become a critical networking issue. We present, in this paper, a novel solution to the scalability problem of group/multicast key management. We formalize the notion of a secure group as a triple (U,K,R) where U denotes a set of users, K a set of keys held by the users, and R a user-key relation. We then introduce key graphs to specify secure groups. For a special class of key graphs, we present three strategies for securely distributing rekey messages after a join/leave and specify protocols for joining and leaving a secure group. The rekeying strategies and join/leave protocols are implemented in a prototype key server we have built. We present measurement results from experiments and discuss performance comparisons. We show that our group key management service, using any of the three rekeying strategies, is scalable to large groups with frequent joins and leaves. In particular, the average measured processing time per join/leave increases linearly with the logarithm of group size.

We present chaining techniques for signing/verifying multiple packets using a single signing/verification operation. We then present flow signing and verification procedures based upon a tree-chaining technique. Since a single signing/verification operation is amortized over many packets, these procedures improve signing and verification rates by one to two orders of magnitude, compared to the approach of signing/verifying packets individually. Our procedures do not depend upon reliable delivery of packets. They also provide delay-bounded signing, and are thus suitable for delay-sensitive flows and multicast applications. To further improve our procedures, we propose several extensions to the Feige-Fiat-Shamir (1987) digital signature scheme to substantially speed up both the signing and verification operations, as well as to allow "adjustable and incremental" verification. The extended scheme, called eFFS, is compared to four other digital signature schemes (RSA, DSA, ElGamal (1985), and Rabin). We compare their signing and verification times, as well as key and signature sizes. We observe that: (1) eFFS is the fastest in signing (by a large margin over any of the other four schemes) and as fast as RSA in verification (tie for a close second behind Rabin (1979)); (2) eFFS allows a tradeoff between memory and signing/verification time; and (3) eFFS allows adjustable and incremental verification by receivers.

We present chaining techniques for signing/verifying multiple packets using a single signing/verification operation. We then present flow signing and verification procedures based upon a tree chaining technique. Since a single signing/verification operation is amortized over many packets, these procedures improve signing and verification rates by one to two orders of magnitude compared to the approach of signing/verifying packets individually. Our procedures do not depend upon reliable delivery of packets, provide delay-bounded signing, and are thus suitable for delay-sensitive flows and multicast applications. To further improve our procedures, we propose several extensions to the Feige-Fiat-Shamir digital signature scheme to speed up both the signing and verification operations, as well as to allow "adjustable and incremental" verification. The extended scheme, called eFFS, is compared to four other digital signature schemes (RSA, DSA, ElGamal, Rabin). We compare their signing and verification times, as well as key and signature sizes. We observe that (i) the signing and verification operations of eFFS are highly efficient compared to the other schemes, (ii) eFFS allows a tradeoff between memory and signing/verification time, and (iii) eFFS allows adjustable and incremental verification by receivers.

We present the design of a distributed authorization service which parallels existing authentication services for distributed systems. Such a service would operate on top of an authentication substrate. There are two distinct ideas underlying our design: (1) the use of a language, called generalized access control list (GACL), as a common representation of authorization requirements; and (2) the use of authenticated delegation to effect authorization offloading from an end server to an authorization server. We present the syntax and semantics of GACL, and illustrate how it can be used to specify authorization requirements that cannot be easily specified by ordinary ACL. We also describe the protocols in our design.

Many emerging applications (e.g., teleconference, real-time information services, pay per view, distributed interactive simulation, and collaborative work) are based upon a group communications model, i.e., they require packet delivery from one or more authorized senders to a very large number of authorized receivers. As a result, securing group communications (i.e., providing confidentiality, integrity, and authenticity of messages delivered between group members) will become a critical networking issue.In this paper, we present a novel solution to the scalability problem of group/multicast key management. We formalize the notion of a secure group as a triple (U,K,R) where U denotes a set of users, K a set of keys held by the users, and R a user-key relation. We then introduce key graphs to specify secure groups. For a special class of key graphs, we present three strategies for securely distributing rekey messages after a join/leave, and specify protocols for joining and leaving a secure group. The rekeying strategies and join/leave protocols are implemented in a prototype group key server we have built. We present measurement results from experiments and discuss performance comparisons. We show that our group key management service, using any of the three rekeying strategies, is scalable to large groups with frequent joins and leaves. In particular, the average measured processing time per join/leave increases linearly with the logarithm of group size.

We have been investigating an end system architecture to support networking with quality of service guarantees. For user level protocol code in our architecture to access the network, we have designed a kernel–user interface. The interface targets three areas for improvement: reduced copying, reduced reliance on explicit kernel–user interactions, and provision of rate-based flow control. In this paper, we present the concept of input–output efficient buffers for reduced copying, the concept of fast system calls for low-latency network access, and the concept of kernel threads for flow control. Also included is a concept called direct media streaming which is suitable for applications that require limited user processing of media data. These concepts have been implemented as an extension to SunOS 5.3 (the operating system component of Solaris 2.3). We report some experimental results on the performance of our current system. © 1998 John Wiley & Sons, Inc.

Most application data units are too large to be carried in a single packet (or cell) and must be segmented for network delivery. To an application, the end-to-end delays and loss rate of its data units are much more relevant performance measures than ones specified for individual packets (or cells). The concept of a burst (or block) was introduced to represent a sequence of packets (or cells) that carry an application data unit. We describe how a real-time variable bit-rate (VBR) service, with quality of service (QoS) parameters for block transfer delay and block loss rate, can be provided by integrating concepts and delay guarantee results from our previous work on burst scheduling, together with ideas from asynchronous transfer mode (ATM) block transfer. Two new contributions are presented herein. First, we design an admission control algorithm to provide the following two classes of service: bounded-delay block transfer with no loss, and bounded-delay block transfer at a specified block loss rate. Secondly, we show how to extend existing end-to-end delay bounds to networks with hierarchical link sharing.

We present an end system architecture designed to support networking with quality of service (QoS) guarantees. The protocol processing component of the architecture, called migrating sockets, has been designed with minimal hidden scheduling which enables accurate determination of the rate requirement of a user application. The end system provides QoS guarantees using: 1) an adaptive rate-controlled scheduler; 2) rate-based flow control on the send side for access to reserved-rate network connections; and 3) a constant overhead active demultiplexing mechanism on the receive side which can be transparently enabled in wide-area TCP/IP internetworking (although it is not restricted to TCP/IP). To achieve efficiency, migrating sockets lets user applications manage network endpoints with minimal system intervention, provides user level protocols read-only access to routing information, and integrates kernel level support previously built for efficient data movement. Migrating sockets is backward compatible with Unix semantics and Berkeley sockets. It has been used to implement Internet protocols such as TCP, UDP, and IP (including IP multicast), and run existing applications such as vic. Migrating sockets has been implemented in Solaris 2.5.1. We discuss our implementation experience, and present performance results of our system running on Sun Sparc and Ultra workstations, as well as Pentium-II desktops.

We present an admission control framework and loss management techniques in support of a guaranteed statistical service. The service is characterized by (i) the loss rate of application data units (ADUs) bounded below a specified value, and (ii) ADU losses distributed evenly among flows subscribing to the service and uniformly over the duration of each flow. Specifically, a flow is modeled as a sequence of bursts, each of which is a sequence of packets that carry the bits of an ADU. The first packet of each burst carries information on the ADU (e.g., its bandwidth requirement). This traffic model enables admission control at the burst level as well as at the flow level. Such a two level admission control approach is very effective in bounding end-to-end ADU loss rates of flows while maintaining high channel utilization in the network. The traffic model also enables simple techniques that can be used at a network channel to distribute ADU losses evenly among flows subscribing to the same statistical service, and to protect high priority ADUs (e.g., 1 frames of MPEG applications).

Migrating Sockets is the protocol processing component of an end system architecture designed for networking with QoS guarantees. The architecture provides: (1) adaptive rate-controlled scheduling of protocol threads in Migrating Sockets, (2) rate-based flow control for reserved rate connections in future integrated services networks, and (3) a constant overhead active demultiplexing mechanism. Migrating Sockets achieves its efficiency by allowing user applications to manage a network endpoint with minimal system intervention, providing user level protocols read-only access to routing information in a "well-known" shared memory region, and integrating efficient kernel level support we previously built. It is backward compatible with Unix semantics and Berkeley sockets, and has been used to implement Internet protocols such as TCP, UDP and IP (including IP multicast). We also show that active demultiplexing supported by Migrating Sockets can be transparently enabled in wide-area TCP/IP internetworking (although it is not restricted to TCP/IP). We have an implementation of Migrating Sockets in Solaris 2.5. We discuss our implementation experience, and present performance results of our system running on the Ultra-1, SPARC 10 and SPARC 20 architectures.

Most application-level data units are too large to be carried in a single packet (or cell) and must be segmented for network delivery. To an application, the end-to-end delays and loss rate of its data units are much more relevant performance measures than ones specified for individual packets (or cells). The concept of a burst (or block) was introduced to represent a sequence of packets (or cells) that carry an application data unit. In this paper, we describe how a real-time VBR service, with quality of service parameters for block transfer delay and block loss rate, can be provided by integrating concepts and delay guarantee results from our previous work on burst scheduling, together with ideas from ATM block transfer. Two new contributions are presented. First, we design an admission control algorithm to provide the following classes of service: bounded-delay block transfer with no loss, and bounded-delay block transfer at a specified block loss rate. Second, we show how to extend existing end-to-end delay bounds to networks with hierarchical link sharing.

We present an end-to-end delay guarantee theorem for a class of guaranteed deadline (GD) servers. The theorem can be instantiated to obtain end-to-end delay bounds for a variety of source control mechanisms and GD servers. We then propose the idea of group priority, and specialize the theorem to a subclass of GD servers that use group priority in packet scheduling. With the use of group priority, the work of packet schedulers can be substantially reduced. We work out a detailed example, for the class of burst scheduling networks, to illustrate how group sizes can be designed such that the worst case end-to-end delay of application data units in a real-time flow is unaffected by the use of group priority. Group priority also can be used in packet schedulers that provide integrated services (best effort as well as real-time services) to achieve statistical performance gains, which we illustrate with empirical results from simulation experiments.

We present a framework for integrated scheduling of continuous media (CM) and other applications. The framework, called ARC scheduling, consists of a rate-controlled on-line CPU scheduler, an admission control interface, a monitoring module, and a rate adaptation interface. ARC scheduling allows threads to reserve CPU time for guaranteed progress. It provides firewall protection between threads such that the progress guarantee to a thread is independent of how other threads actually make scheduling requests. Rate adaptation allows a CM application to adapt its rate to changes in its execution environment. We have implemented the framework as an extension to Solaris 2.3. We present experimental results which show that ARC scheduling is highly effective for integrated scheduling of CM and other applications in a general purpose workstation environment. ARC scheduling is a key component of an end system architecture we have designed and implemented to support networking with quality of service guarantees. In particular, it enables protocol threads to make guaranteed progress.

For many service disciplines that provide delay guarantees, the scheduler of a channel repeatedly searches for the smallest element in a set of priority values (or deadlines). It is required that each search finishes within a time bound. Furthermore, the search algorithm should be highly efficient. To meet these requirements, we have developed a search algorithm based upon a new data structure, called adaptive heap; it behaves like a heap most of the time, but adaptively changes its strategy when necessary to satisfy the time bound. We show that the algorithm has an optimal worst-case time complexity and a good average performance. To further improve the efficiency, the basic algorithm is extended to include the use of group scheduling. We present empirical results on the performance of adaptive heap search with and without group scheduling. We conclude that adoptive heap search performs as intended, and that group scheduling provides a substantial reduction in the scheduler's work when channel utilization is high.

For many applications, the end-to-end delay of an application-specific data unit is a more important performance measure than the end-to-end delays of individual packets within a network. From this observation, we propose the idea of group scheduling. Specifically, consecutive packet arrivals in a flow are partitioned into groups, and the same deadline (called group priority) is assigned to every packet in a group. We first present an end-to-end delay guarantee theorem for a network of guaranteed-deadline (GD) servers. The theorem can be instantiated to obtain end-to-end delay bounds for a variety of source control mechanisms and GD servers. We then specialize the delay guarantee theorem to group scheduling for a subclass of GD servers. We work out a detailed example to demonstrate how to use group scheduling in a particular class of networks. The advantages of group scheduling are discussed and illustrated with empirical results from simulation experiments.

We present a framework for integrated scheduling of continuous media (CM) and other applications.The framework consists of a rate-controlled on-line CPU scheduler, an admission control interface, a monitoring module and a rate adaptation interface.Rate-controlled scheduling allows processes to reserve CPU time to achieve progress guarantees.It provides firewall protection between processes such that the progress guarantee to a process is independent of how other processes actually make scheduling requests.Rate adaptation allows a CM application to adapt its rate to changes in its execution environment.We have implemented the scheduling framework as an extension to Solaris 2.3.We present experimental results which show that our framework is highly effective in scheduling CM and various other applications in a general purpose workstation environment, KEYWORDS: Continuous media, CPU scheduling, adaptive rate control, rate reservation, QoS guarantee, firewall property

Interframe coding techniques, such as those used in MPEG video, give rise to a sequence of encoded pictures whose sizes (in number of bits) differ by a factor of ten or more. Buffering is needed to reduce fluctuations in the rate at which video packets are sent to a network connection. We design and specify a lossless smoothing algorithm, characterized by three parameters: D (delay bound), X (number of pictures with known sizes), and H (lookahead interval). We prove a theorem which guarantees that, if K/spl ges/1, the algorithm finds a solution that satisfies the delay bound. We present the algorithm's performance from a large number of experiments conducted using MPEG video traces. Lastly, we discuss algorithm implementation.

In a packet switching network, each communication channel is statistically shared among many traffic flows that belong to different end-to-end sessions. We present and prove a delay guarantee for the virtual clock service discipline (inspired by time division multiplexing). The guarantee has several desirable properties, including the following firewall property: the guarantee to a flow is unaffected by the behavior of other flows sharing the same server. There is no assumption that sources are flow controlled or well behaved. We first introduce and define the concept of an active flow. The delay guarantee is then formally stated as a theorem. We show how to obtain delay bounds from the delay guarantee of a single server for different specifications.

We present an account of the entire development cycle (i.e., design, specification and verification, and implementation) of a realistic authentication protocol, which is part of a security architecture proposed by us. The protocol's design follows a stepwise refinement process, which we illustrate. Our account of its specification and verification provides a practical demonstration of a proposed formal analysis approach. For its implementation, we adopt the GSS-API standard. We describe the mapping from our protocol to GSS-API, which can serve as a reference for other protocol implementations. We believe that the global perspective presented in this paper would be of great value to protocol designers, verifiers, and implementers, and contribute toward bridging the gap between the theory and practice of authentication protocol design.>

Interframe compression techniques, such as those used in MPEG video, give rise to a coded bit stream where picture sizes differ by a factor of 10 or more. As a result, buffering is needed to reduce (smooth) rate fluctuations of encoder output from one picture to the next; without smoothing, the performance of networks that carry such video traffic would be adversely affected. Various techniques have been suggested for controlling the output rate of a VBR encoder to alleviate network congestion or prevent buffer overflow. Most of these techniques, however, are lossy, and should be used only as a last resort. In this paper, we design and specify an algorithm for lossless smoothing. The algorithm is characterized by three parameters: D (delay bound), K (number of pictures with known sizes), and H (lookahead interval). We present a theorem which guarantees that, if K ≥ 1, the algorithm finds a solution that satisfies the delay bound. (Although the algorithm and theorem were motivated by MPEG video, they are applicable to the smoothing of compressed video in general). To study performance characteristics of the algorithm, we conducted a large number of experiments using statistics from four MPEG video sequences.

We model a system as a directed acyclic graph where nodes represent modules and arcs represent interfaces. At the heart of our theory is a definition of what it means for a module to satisfy a set of interfaces as a service provider for some and as a service consumer for others. Our definition of interface satisfaction is designed to be separable; i.e., interfaces encode adequate information such that each module in a system can be designed and verified separately, and composable; i.e., we have proved a composition theorem for the system model in general.>

The authors present a new approach to the analysis of authentication protocols. The approach consists of several elements: a specification language for formally specifying authentication protocols, a semantic model for characterizing protocol executions, an assertion language for stating secrecy and correspondence properties, and procedures for verifying these properties. The main emphasis of this paper is on the assertion language, its semantics, and verification procedures. In particular, the authors present a set of proof rules. An example is given to illustrate the approach.>

The authors specify authentication protocols as formal objects with precise syntax and semantics, and define a semantic model that characterizes protocol executions. They have identified two basic types of correctness properties, namely, correspondence and secrecy; that underlie the correctness concerns of authentication protocols. Assertions for specifying these properties, and a formal semantics for their satisfaction in the semantic model are defined. The Otway-Rees protocol is used to illustrate the semantic model and the basic correctness properties.>

It is argued that authorization is an independent semantic concept that must be separated from implementation mechanisms and given a precise semantics. A logical approach to representing and evaluating authorization is proposed. Specifically, a language for specifying policy bases is introduced. A policy base encodes a set of authorization requirements and is given a precise semantics based on a formal notion of authorization policy. The semantics is computable, thus providing a basis for authorization evaluation. Two composition operators for policy bases which are appropriate for modeling distributed systems with multiple administrative domains are introduced.>

A stepwise refinement heuristic to construct distributed systems is presented. The heuristic is based on a conditional refinement relation between system specifications, and a “Marking”. It is applied to construct four sliding window protocols that provide reliable data transfer over unreliable communication channels. The protocols use modulo- N sequence numbers. The first protocol is for channels that can only lose messages in transit. By refining this protocol, we obtain three protocols for channels that can lose, reorder, and duplicate messages in transit. The protocols herein are less restrictive and easier to implement than sliding window protocols previously studied in the protocol verification literature.

An overview is given of a theory of modules and interfaces applicable to the specification and verification of systems with a layered architecture. At the heart of this theory is a module composition theorem. The theory is applied to the specification of a distributed system consisting of subjects and objects in different hosts (computers). Formal specifications of a user interface and a network interface are given. Access to objects, both local and remote, offered by the distributed system is proved to be multilevel secure.>

The authors present a model for specifying real-time protocols that execute on broadcast bus networks. Protocol entities interact by sending and receiving binary signals on buses. The actual propagation of these signals is captured in the proposed model by a set of channel axioms. Protocol entities are specified by sequential programs. The semantics of a set of programming constructs, including two level wait constructs, are defined. To illustrate the model and verification method, the authors present a specification of the Expressnet protocol which was designed for collision-free access to a unidirectional bus. A scenario in which collisions can occur in the original Expressnet was discovered. To guarantee collision-freedom, a modification to the protocol is given. The modified protocol is shown to be collision-free. A bound for its access delay is also derived.>

The use of adaptors for protocol conversion in heterogeneous data networks with layered architectures is proposed. An adaptor is a form of protocol converter enabling a peer component of one protocol to simulate a peer of a different protocol. Adaptors have several advantages over other conversion architectures, especially gateway-type converters: they avoid bottlenecks at network boundaries, and a message is translated twice at most on its way from one peer to the other; adaptors are well-suited for conversion among multiple protocols; and the definition of an adaptor as the quotient of known components is simpler than for other converters, making it simpler to compute an adaptor algorithmically or to verify one derived heuristically. The approach is illustrated with an example involving three different connection-management protocols.>

Consideration is given to ways of overcoming a protocol mismatch using protocol conversion. Three different methods for finding a protocol converter are described. Two of these are bottom up in nature, and involve relating the conversion system to existing protocols. The third approach, which is new, is top down: the desired global properties of the conversion system are used in deriving the converter. An example is used to illustrate each method. The authors discuss more general forms of the abstract problem in the context of layered network architectures.>

A relational notation for specifying state transition systems is presented. Several refinement relations between specifications are defined. To illustrate the concepts and methods, three specifications of the alternating-bit protocol are given. The theory is applied to explain auxiliary variables. Other applications of the theory to protocol verification, composition, and conversion are discussed. The approach is compared with previously published approaches.>

A protocol converter mediates the communication between implementations of different protocols, enabling them to achieve some form of useful interaction. The problem of deriving a protocol converter from specifications of the protocols and a desired service can be viewed as the problem of finding the “quotient” of two specifications. We define a class of finite-state specifications and present an algorithm for solving “quotient” problems for the class. The algorithm is applied to an example conversion problem. We also discuss its application in the context of layered network architectures.

For high-speed local area networks that offer integrated services for data, voice, and image traffic, a class of demand-assigned multiple-access protocols have been presented in the literature. These protocols exploit the directionality of signal propagation and enforce time constraints to achieve collision-freedom. A correct implementation of such a protocol requires a careful analysis of time-dependent interactions of event occurrences using a formal method. To date, most protocol verification methods are intended for the analysis of asynchronous communication over point-to-point channels.

Approximate MVA algorithms for separable queueing networks are based upon an iterative solution of a set of modified MVA formulas. Although each iteration has a computational time requirement of O(MK2) or less, many iterations are typically needed for convergence to a solution. (M denotes the number of queues and K the number of closed chains or customer classes.) We present some faster approximate solution algorithms that are noniterative. They are suitable for the analysis and design of communication networks which may require tens to hundreds, perhaps thousands, of closed chains to model flow-controlled virtual channels. Three PAM algorithms of increasing accuracy are presented. Two of them have time and space requirements of O(MK). The third algorithm has a time requirement of O(MK2) and a space requirement of O(MK).

The PROSPEC software environment for designing and verifying communication protocols is described. It integrates several tools that implement methods for protocol verification and construction (i.e., fair reachability analysis, multiphase construction, and protocol projection). The system provides a unified graphical interface to facilitate the application of these methods and creates an interactive environment for specifying, verifying, and designing communication protocols. PROSPEC was used successfully to design and verify versions of BSC, X.21, X.25, and Telnet document transfer protocols.>

The problem of achieving communication between two processes across a network or an internetwork is considered. The notion of logical connectivity between processes in a protocol is formalized. The problem of constructing a protocol converter to achieve interoperability between processes that implement different protocols is addressed. A formal model is presented, based on the theory of protocol projection, for reasoning about the semantics of different protocols and conversions between them. Two kinds of converters are presented: memoryless converters and finite-state converters. The construction of some finite-state converters is illustrated, and examples are given.>

In previously giving a summary of the theory of protocol projection (ibid., vol.14, no.3, p.353-62, Mar. 1988), an incorrect statement was made. A given statement is claimed to be false, and is corrected accordingly.>

A class of demand-assigned multiple-access (DAMA) protocols have been proposed for high-speed local area networks (LAN's) that offer integrated services for data, voice, video, and facsimile traffic. These protocols exploit the directionality of signal propagation and implement stringent real-time constraints to achieve collision-freedom. Correct implementation of DAMA protocols will require a very careful analysis of time-dependent interactions using a formal method. To date, most verification methods have been focused on asynchronous communication over point-to-point links.

Consider the problem of providing a logical channel for message exchange between two user processes in a network environment. When is protocol conversion needed? To answer this question, we first define a model of layered architectures. Specifically, three stepwise refinement rules are given. Any architecture that can be obtained by a sequence of applications of the stepwise refinement rules is said to be well-structured. We show that this class of well-structured architectures has several correctness properties. It is also very general and includes many well-known networking and internetworking architectures in the literature. Logical connectivity in such an architecture is defined recursively. As a result, to determine if a logical channel can be provided between two user processes, it is sufficient to examine peer protocols specified for each level of the architecture's hierarchy of processes one at a time. Thus the original problem reduces to the problem of determining if a set of processes will interoperate.

Many communication protocols can be observed to go through different phases performing a distinct function in each phase. A multiphase model for such protocols is presented. A phase is formally defined to be a network of communicating finite-state machines with certain desirable correctness properties; these include proper termination and freedom from deadlocks and unspecified receptions. A multifunction protocol is constructed by first constructing separate phases to perform its different functions. It is shown how to connect these phases together to realize the multifunction protocol so that the resulting network of communicating finite state machines is also a phase (i.e., it possesses the desirable properties defined for phases). The modularity inherent in multiphase protocols facilitates not only their construction but also their understanding and modification. An abundance of protocols have been found in the literature that can be constructed as multiphase protocols. Three examples are presented here: two versions of IBM's BSC protocol for data link control and a token ring network protocol.

The method of projections is a new approach to reduce the complexity of analyzing nontrivial communication protocols. A protocol system consists of a network of protocol entities and communication channels. Protocol entities interact by exchanging messages through channels; messages in transit may be lost, duplicated as well as reordered. Our method is intended for protocols with several distinguishable functions. We show how to construct image protocols for each function. An image protocol is specified just like a real protocol. An image protocol system is said to be faithful if it preserves all safety and liveness properties of the original protocol system concerning the projected function. An image protocol is smaller than the original protocol and can typically be more easily analyzed. Two protocol examples are employed herein to illustrate our method. An application of this method to verify a version of the high-level data link control (HDLC) protocol is described in a companion paper.

We use an event-driven process model to specify a version of the High-level Data Link Control (HDLC) protocol between two communicating protocol entities. The HDLC protocol is based upon the Asynchronous Response Mode (ARM) of operation, and uses the basic repertoire of HDLC commands and responses (with the exception of the CMDR response). It includes the features of poll/final cycles for connection management and checkpointing, sliding windows for data transfer, and ready/not ready messages for flow control. HDLC has three distinguishable functions: connection management, and one-way data transfers in opposite directions between the protocol entities. Various logical safety properties of the HDLC protocol concerning these functions have been verified using the method of projections.

The convolution algorithm, the mean value analysis (MVA) algorithm, and the LBANC algorithm are major algorithms for the solution of closed product-form queueing networks. For fixed-rate service centers, the efficiency of each algorithm is greatly improved by a recursive solution. We show that the recursive relations in all three algorithms are closely related so that each one can be easily derived from any of the others.

We use an event-driven process model to specify a version of the High-Level Data Link Control (HDLC) protocol between two communicating protocol entities.The protocol is verified using the method of projections.The verification serves as a rigorous exercise to demonstrate the applicability of this method to the analysis of real-life communication protocols.The HDLC protocol has two characteristics found in most real-life communication protocols.First, the HDLC protocol operates under real-time constraints that are important not only for its performance but also for its correct logical behavior.We specify this real-time behavior using time variables and time events.Second, the HDLC protocol has three distinguishable functions: connection management, and one-way data transfers between the protocol entities.For each of these functions, we construct an image protocol using the method of projections.With each image protocol we obtain inductively complete invariant assertions that state various desirable logical safety properties.From the properties of image protocols it follows that these safety properties as proved for the image protocols are also satisfied by the HDLC protocol presented herein.We also suggest a minor modification to HDLC that will make it well-structured.

A sample dynamic scaling technique is shown that avoids both the overflow and underflow problems that are often encountered in the evaluation of normalization constants of closed product-form queuing networks W~th dynamic scaling, normalization constants for very large routing chain population sizes can be evaluated within the bounds of a relauvely small range of numbers.It is shown that the product-form solution possesses a local balance property and the M ~, M property with respect to routing chains.The relationships between normahzaUon constants of closed networks and certain equilibrium aggregate state probabdities in networks that permit external arrivals and departures are examined.The growth behavior of normalization constants is shown to be modeled by a birth-death process traversing over the set of chain population vectors Categories and Subject Descriptors: C 2 4 [Competer-Conununicatinn Networks]:

Packet switching networks with flow controlled virtual channels are modeled by closed multi-chain queueing networks. The tree convolution algorithm for an exact analysis of such models is discussed. The algorithm is very efficient when routing chains have sparseness and locality properties that are typical of communication network models. The accuracy of an approximate model of equivalent open chains was investigated. An optimal routing criterion for adding a virtual channel (with a window size of one) to an existing network is explored.

An experimental study was conducted using a network simulator to investigate the performance of packet communication networks as a function of: the network resource capacities (channels, buffers), the network load (number of virtual channels, virtual channel loads), protocols (flow control, congestion control, routing), and protocol parameters (virtual channel window size, input buffer limits). Performance characteristics are shown and the design of input buffer limits for network congestion control, virtual channel window size, and nodal buffer capacity addressed. Network design strategies for the control of load fluctuations are proposed and discussed.

In packet broadcast networks, users are interconnected via a broadcast channel. The key problem is multiple access of the shared broadcast channel. The performance of the R-ALOHA protocol for multiple access is studied in this paper. Two user models with Poisson message arrivals are analyzed; each message consists of a group of packets with a general probability distribution for group size. In the first model, each user handles one message at a time. In the second model, each user has infinite buffering capacity for queueing. Analytic models are developed for characterizing message delay and channel utilization. Bounds on channel throughput are established for two slightly different protocols. Numerical results from both analysis and simulation are presented to illustrate the accuracy of the analytic models as well as performance characteristics of the R-ALOHA protocol.

Satellite communication systems have traditionally been designed for voice traffic. Multiple access protocols for conflict resolution have typically been channel-oriented with either fixed or demand assignment. Data communications, however, have much more diverse traffic characteristics and transmission requirements than voice communications. We present in this paper an overview of two major categories of packet-oriented multiple access protocols: contention and reservation protocols. A traffic model suitable for the data communications environment is first introduced. A key element in this model is user-specified message delay constraints. Our primary performance measure of a protocol is the channel throughput versus average message delay tradeoff characteristic. The main attributes of the two categories of packet-oriented protocols are discussed. Four specific contention protocols are described and their performance characteristics are examined. Design considerations of the two important components of reservation protocols, reservation channel and distributed global queue, are discussed. Three reservation protocols with distributed control are described. Finally the performance of channel-oriented protocols and the two classes of packet-oriented protocols are compared using a variety of traffic models.

The use of input buffer limits for congestion control of store-and-forward networks is investigated. An analytic model is formulated. Based upon the analytic results, strategies are proposed for the design of input buffer limits to achieve the maximum network throughput as well as to provide a safety margin for uncertainties in traffic assumptions. A useful capacity law is discovered. Major conclusions drawn from the analysis are supported by simulation results for a fournode homogeneous network. These results indicate that input buffer limits which satisfy the capacity law are a simple and effective means of network congestion control. Further simulation studies are underway to investigate methods of implementation in a general network.

It is generally recognized that data traffic has more diverse characteristics and transmission requirements than voice traffic. In particular, data traffic associated with many interactive data processing applications is often characterized to be extremely bursty, which lends support to the choice of Packet (or message) switching over circuit switching in data network design. We introduce in this paper a new measure called bursty factor for characterizing the burstiness of a data traffic source. Unlike the usual measures of peak-to-average ratio and duty cycle, the new measure introduced is independent of a specific network design and dependent only upon the traffic source characteristics and performance requirements. It can therefore be used to guide the direction of an initial network design.

The delay performance of a Time Division Multiple Access (TDMA) channel for transmitting data messages is considered. The channel is assumed to be fixed assigned to a station with unlimited buffer capacity and Poisson message arrivals. Each message gives rise to one or more packets for transmission into fixed-length time slots. The steady-state probability generating function of the queue size is derived. A formula for the expected message delay is given. The analysis is then generalized to a nonpreemptive priority queue discipline; expected message delay formulas are given for the priority classes.

Previous analytic models for packet switching networks have always assumed infinite storage capacity in store-store-and-forward (S/F) nodes. In this paper, we relax this assumption and present a model for a packet switching network in which each node has a finite pool of S/F buffers. A packet arriving at a node in which all S/F buffers are temporarily filled is discarded. The channel transmission control mechanisms of positive acknowledgment and time-out of packets are included in this model. Individual S/F nodes are analyzed separately as queueing networks with different classes of packets. The single node results are interfaced by imposing a continuity of flow constraint. A heuristic algorithm for determining a balanced assignment of nodal S/F buffer capacities is proposed. Numerical results for the performance of a 19 node network are illustrated.

In this paper, the rationale and some advantages for multiaccess broadcast packet communication using satellite and ground radio channels are discussed. A mathematical model is formulated for a "slotted ALOHA" random access system. Using this model, a theory is put forth which gives a coherent qualitative interpretation of the system stability behavior which leads to the definition of a stability measure. Quantitative estimates for the relative instability of unstable channels are obtained. Numerical results are shown illustrating the trading relations among channel stability, throughput, and delay. These results provide tools for the performance evaluation and design of an uncontrolled slotted ALOHA system. Adaptive channel control schemes are studied in a companion paper.

In a companion paper [1], the rationale for multiaccess broadcast packet communication using satellite and ground radio channels has been discussed. Analytic tools for the performance evaluation and design of uncontrolled slotted ALOHA systems have been presented. In this paper, a Markovian decision model is formulated for the dynamic control of unstable slotted ALOHA systems and optimum decision rules are found. Numerical results on the performance of controlled channels are shown for three specific dynamic channel control procedures. Several practical control schemes are also proposed and their performance compared through simulation. These dynamic control procedures have been found to be not only capable of preventing channel saturation for unstable channels but also capable of achieving a throughput-delay channel performance close to the theoretical optimum.