While secure efficient operation of computer networks requires cost-effective line-rate packet classification, network programmability strengthens this need. A promising approach is to transform a packet classifier to a semantically equivalent representation that supports more effective classification. This paper explores transformation of ternary classifiers to equivalent prefix representations so that classification can benefit from efficient Longest Prefix Match solutions. We propose the property of prefix disjointness and design PREDICAT, a method that leverages this new property in combination with a variety of existing techniques to convert an arbitrary ternary classifier to an equivalent prefix representation. The paper analyzes prefix disjointness and evaluates PREDICAT against state-of-the-art transformation alternatives on a packet classification benchmark in regard to the number of lookups. The evaluation shows that PREDICAT outperforms a ternary-to-binary method by up to an order of magnitude, improves on another ternary-to-prefix solution by up to a factor of 5, and performs similarly to a ternary-to-ternary approach that requires costly power-hungry Ternary Content-Addressable Memories to efficiently handle the resulting ternary representation.

In-band real-time telemetry is a promising direction for management of modern programmable networks. While network noise in the form of packet reordering and loss affects inband collection of distributed state, there is a need to compute telemetry functions on the collected state correctly despite the network noise. To address this common need, we propose TeleNoise that equips each packet with few sync bits and offers primitives of group affiliation and group completion to support noise-resilient computation of per-group telemetry functions. This paper gives real-world examples of such functions, elaborates on the role of TeleNoise in a modular in-band telemetry architecture, and presents algorithms for the two TeleNoise primitives. We derive analytical guarantees on correctness and performance of the algorithms and report a trace-driven evaluation that corroborates the effective low-overhead profile of TeleNoise, e.g., the assuredly correct operation and at most 1.6 packets of the average measurement lag for 12-packet groups and 3 sync bits.

Unrelenting traffic growth, device heterogeneity, and load unevenness create scalability challenges for traffic monitoring. In this paper, we propose Robust Distributed Computation (RoDiC), a new approach that addresses these challenges by shifting a portion of the monitoring-task execution from an overloaded network element to another element that has spare resources. Moving the entire execution of the task away from the overloaded element might be infeasible because execution on multiple elements is inherent in the task or requires at least partial participation by the designated overloaded element. Furthermore, distributed execution of a stateful task has to be resilient to network noise in the form of packet reordering and loss. The RoDiC approach relies on two main principles of packet grouping and state overlap to support exact robust distributed monitoring of traffic flows under network noise. RoDiC uses an open-loop paradigm that does not add any control packets, communicates flow state in-band by appending few control bits to packets of monitored flows, and keeps measurement latency low. We apply RoDiC to the problem of flow-size computation and discuss how to instantiate our general technique for real-time packet-loss telemetry. The paper develops robust algorithms, proves their correctness and performance properties, and reports an evaluation driven by realistic traffic traces. The RoDiC algorithms successfully distribute the monitoring-task load while keeping the memory and computation overhead low.

Content delivery networks (CDNs) distribute much of the Internet content by caching and serving the objects requested by users. A major goal of a CDN is to maximize the hit rates of its caches, thereby enabling faster content downloads to the users. Content caching involves two components: an admission algorithm to decide whether to cache an object and an eviction algorithm to determine which object to evict from the cache when it is full. In this paper, we focus on cache admission and propose a novel algorithm called RL-Cache that uses model-free reinforcement learning (RL) to decide whether or not to admit a requested object into the CDN's cache. Unlike prior approaches that use a small set of criteria for decision making, RL-Cache weights a large set of features that include the object size, recency, and frequency of access. We develop a publicly available implementation of RL-Cache and perform an evaluation using production traces for the image, video, and web traffic classes from Akamai's CDN. The evaluation shows that RL-Cache improves the hit rate in comparison with the state of the art and imposes only a modest resource overhead on the CDN servers. Further, RL-Cache is robust enough that it can be trained in one location and executed on request traces of the same or different traffic classes in other locations of the same geographic region. The paper also reports extensive analyses of the RL-Cache sensitivity to its features and hyperparameter values. The analyses validate the made design choices and reveal interesting insights into the RL-Cache behavior.

Scalable monitoring of traffic flows faces challenges posed by unrelenting traffic growth, device heterogeneity, and load unevenness. We explore an approach that tackles these challenges by shifting a portion of the monitoring-task execution from an overloaded network element to another element that has spare resources. Moving the entire execution of the task to a lightly loaded element might be infeasible because execution on multiple elements is inherent in the task or requires at least partial participation by the particular overloaded element (e.g., flow-size computation at the ingress element for billing purposes). Distributed execution of a stateful traffic-monitoring task has to be robust against packet reordering or loss, i.e., network noise. This paper designs robust traffic monitoring where the goal is to determine a flow metric for each flow exactly in spite of network noise. We follow the open-loop paradigm that does not add any control packets, communicates flow state in-band by appending few (on the order of 2 or 4) control bits to packets of the monitored flows, and keeps latency low. We consider the task of flow-size computation, analytically derive conditions assuring correct operation of the designed algorithms, and evaluate the algorithms on realistic traffic traces. The algorithms successfully distribute the monitoring-task load without imposing significant computation or storage overhead.

Faced with the unrelenting traffic growth and rising costs, access ISPs (Internet Service Providers) realize that their traditional revenue model of flat subscription fees is unsustainable. Regulatory concerns, e.g., about content-specific charging, constrain the ISPs' search for new revenue sources. This paper analyzes a revenue model where an access ISP acts as a publisher of ads to users who explicitly opt for an ad-sponsored access plan of the ISP. First, we conduct a survey showing a substantial interest of users in ad-sponsored Internet access. Then, we mathematically characterize the advertising revenue model and asses its economic feasibility based on real data from two access ISPs and an ad publisher. While the ad revenues are tangible, they do not completely cover the costs of the access ISPs. Even in relative terms, a larger access ISP benefits more from the advertising, with the ad revenues covering up to 50% of the ISP's capital expenditure. Complementing the subscription fees, the access ISPs can leverage the ad revenues to meaningfully incentivize the users with better Internet connectivity, such as 6-9 Mbps in extra data rates or 12-20 GB in extra data caps for the two considered ISPs.

The trend toward more peering between networks is commonly conflated with the trend of Internet flattening, i.e., reduction in the number of intermediary organizations on Internet paths. Indeed, direct peering interconnections bypass layer-3 transit providers and make the Internet flatter. This paper studies an emerging phenomenon that separates the two trends: we present the first systematic study of remote peering, an interconnection where remote networks peer via a layer-2 provider. Our measurements reveal significant presence of remote peering at IXPs (Internet eXchange Points) worldwide. Based on ground truth traffic, we also show that remote peering has a substantial potential to offload transit traffic. Generalizing the empirical results, we analytically derive conditions for economic viability of remote peering versus transit and direct peering. Because remote-peering services are provided on layer 2, our results challenge the traditional reliance on layer-3 topologies in modeling the Internet economic structure. We also discuss broader implications of remote peering for reliability, security, accountability, and other aspects of Internet research.

Content delivery networks (CDNs) deploy globally distributed systems of caches in a large number of autonomous systems (ASes). It is important for a CDN operator to satisfy the performance requirements of end users, while minimizing the cache deployment cost. In this paper, we study the cache deployment optimization (CaDeOp) problem of determining how much server, energy, and bandwidth resources to provision in each cache AS, i.e., each AS chosen for cache deployment. The CaDeOp objective is to minimize the total cost incurred by the CDN, subject to meeting the end-user performance requirements. We formulate the CaDeOp problem as a mixed integer program (MIP) and solve it for realistic AS-level topologies, traffic demands, and non-linear energy and bandwidth costs. We also evaluate the sensitivity of the results to our parametric assumptions. When the end-user performance requirements become more stringent, the CDN footprint rapidly expands, requiring cache deployments in additional ASes and geographical regions. Also, the CDN cost increases several times, with the cost balance shifting toward bandwidth and energy costs. On the other hand, the traffic distribution among the cache ASes stays relatively even, with the top 20% of the cache ASes serving around 30% of the overall traffic.

Internet transit is an economy where providers sell traffic-delivery services. Traffic attraction refers to BGP (Border Gateway Protocol) techniques enabling an AS (Autonomous System) to receive traffic that would otherwise flow elsewhere. Unlike prior studies that present security perspectives on traffic attraction or deal with economic considerations in game-theoretic settings, this paper focuses on the economics of customer-traffic attraction by transit providers and report extensive simulations in an Internet-scale model configured with realistic data on traffic, topology, and pricing. We consider traffic attraction by tier-1 tier-2, and tier-3 networks with 3 types of reactions by other net-works: filtering, customer-disconnections, and attempts of losing ASes to attract traffic to themselves. Our results demonstrate that transit providers can derive substantial financial benefits from attracting customer traffic, with tier-1 networks being in the strongest position to do so. The traffic attraction remains effective despite the countermeasures unless participation in them is broad.

A majority of Internet service providers (ISPs) support connectivity to the entire Internet by transiting their traffic via other providers. Although the transit prices per megabit per second (Mbps) decline steadily, the overall transit costs of these ISPs remain high or even increase due to the traffic growth. The discontent of the ISPs with the high transit costs has yielded notable innovations such as peering, content distribution networks, multicast, and peer-to-peer localization. While the above solutions tackle the problem by reducing the transit traffic, this paper explores a novel approach that reduces the transit costs without altering the traffic. In the proposed Cooperative IP Transit (CIPT), multiple ISPs cooperate to jointly purchase Internet Protocol (IP) transit in bulk. The aggregate transit costs decrease due to the economies-of-scale effect of typical subadditive pricing as well as burstable billing: Not all ISPs transit their peak traffic during the same period. To distribute the aggregate savings among the CIPT partners, we propose Shapley-value sharing of the CIPT transit costs. Using public data about IP traffic and transit prices, we quantitatively evaluate CIPT and show that significant savings can be achieved, both in relative and absolute terms. We also discuss the organizational embodiment, relationship with transit providers, traffic confidentiality, and other aspects of CIPT.

This paper presents an economic perspective on traffic attraction and countermeasures. The results demonstrate that tier-1, tier-2, and tier-3 networks have significant financial incentives to attract traffic. In comparison to ASes from the lower tiers, the tier-1 networks are in a stronger position to benefit from traffic attraction with respect to: (a) the degree of the attainable gain, (b) impact on other networks, and (c) preserving their own gain when multiple ASes attract traffic. The traffic attraction remains effective despite countermeasures unless other ASes participate in the countermeasures broadly. The disconnection by losing customers is ineffective unless a large portion of them terminate their business relationships with the attractor.

On behalf of the entire WoWMoM 2013 Organizing Committee, I welcome you to Madrid, Spain where the Fourteenth IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (IEEE WoWMoM 2013) meets from the 4thto 7thof June 2013! IEEE WoWMoM 2013 begins with a day of 8 workshops AOC, CONWIRE, CORAL, D-SPAN, HOTMESH, IoT-SoS, SCUCA, and VIDEV that deal with a broad range of hot research topics such as autonomic and opportunistic communications, wireless-system convergence, cognitive radio, wireless data security and privacy, mesh networking, Internet of things, smart cities, and ubiquitous video. The subsequent 3 days are dedicated to the main conference.

In explicit or delay-driven congestion control, a common objective is to sustain high throughput without long queues and large losses at the bottleneck link of the network path. Congestion control protocols strive to achieve this goal by transmitting smoothly in the steady state. The discovery of the appropriate steady-state transmission rates is a challenging task in itself and typically introduces additional queuing and losses. Seeking insights into the steady-state profiles of queuing and loss achievable by real protocols, this paper presents an AIST (Asynchronous arrivals with Ideally Smooth Transmission) model that abstracts away transient queuing and losses related to discovering the path capacity and redistributing it fairly among the packet flows on the bottleneck link. In AIST, the flows arrive asynchronously but transmit their packets at the same constant rate in the steady state. For the link with an overprovisioned buffer, our queuing-theoretic analysis and simulations for different smooth distributions of packet interarrival times agree that queuing under AIST with the target utilization of 1 is on the order of the square root of N, where N is the number of flows. With small buffers, our simulations of AIST show an ability to provide bounded loss rates regardless of the number of flows.

Internet routing depends on economic relationships between ASes (Autonomous Systems). Despite extensive prior research of these relationships, their characterization remains imprecise. In this paper, we focus on provider-free ASes that reach the entire Internet without paying anyone for the traffic delivery. While the ground truth about PFS (set of the provider-free ASes) lies outside the public domain, we use trustworthy non-verifiable sources as a baseline for result validation. Straightforward extraction of PFS from public datasets of inter-AS economic relationships yields poor results. Then, we develop a more sophisticated Temporal Cone (TC) algorithm that relies on topological statistics (customer cones of ASes) and exploits the temporal diversity of the datasets. Our evaluation shows that the TC algorithm infers PFS from the same public datasets with a significantly higher accuracy. We also assess the sensitivity of the TC algorithm to its parameters.

A majority of ISPs (Internet Service Providers) support connectivity to the entire Internet by transiting their traffic via other providers. Although the transit prices per Mbps decline steadily, the overall transit costs of these ISPs remain high or even increase, due to the traffic growth. The discontent of the ISPs with the high transit costs has yielded notable innovations such as peering, content distribution networks, multicast, and peer-to-peer localization. While the above solutions tackle the problem by reducing the transit traffic, this paper explores a novel approach that reduces the transit costs without altering the traffic. In the proposed CIPT (Cooperative IP Transit), multiple ISPs cooperate to jointly purchase IP (Internet Protocol) transit in bulk. The aggregate transit costs decrease due to the economies-of-scale effect of typical subadditive pricing as well as burstable billing: not all ISPs transit their peak traffic during the same period. To distribute the aggregate savings among the CIPT partners, we propose Shapley-value sharing of the CIPT transit costs. Using public data about IP traffic of 264 ISPs and transit prices, we quantitatively evaluate CIPT and show that significant savings can be achieved, both in relative and absolute terms. We also discuss the organizational embodiment, relationship with transit providers, traffic confidentiality, and other aspects of CIPT.

The single best-effort service of the Internet struggles to accommodate divergent needs of different distributed applications. Numerous alternative network architectures have been proposed to offer diversified network services. These innovative solutions failed to gain wide deployment primarily due to economic and legacy issues rather than technical shortcomings. Our paper presents a new simple paradigm for network service differentiation that accounts explicitly for the multiplicity of Internet service providers and users as well as their economic interests in environments with partly deployed new services. Our key idea is to base the service differentiation on performance itself, rather than price. We design RD (Rate-Delay) network services that give a user an opportunity to choose between a higher transmission rate or low queuing delay at a congested network link. To support the two services, an RD router maintains two queues per output link and achieves the intended rate-delay differentiation through simple link scheduling and dynamic buffer sizing. We evaluate the performance, deployment, and security properties of the RD network services in various network topologies and traffic scenarios including delay-sensitive VoIP (Voice over Internet Protocol) applications.

Multicast is attracting a resurgence of interest because it has a potential to address the explosively growing need for efficient streaming of large-volume Internet content. However, to realize the potential, large-scale multicast distribution requires effective congestion control. In this paper, we design SIM, a protocol that combines three distinct mechanisms (Selective participation, Intra-group transmission adjustment, and Menu adaptation) to provide a general solution for efficient fair scalable privacy-preserving multicast congestion control with heterogeneous receivers. Whereas the individual mechanisms have appeared in earlier multicast protocols, our main contribution lies in the cohesive integration of the techniques. SIM achieves such integration by operating the three mechanisms at different timescales and distributing the responsibility for control to different entities in the network. Besides, to instantiate and integrate the three control mechanisms, SIM employs several novel techniques of independent interest. Our extensive evaluation confirms the salient properties of SIM in diverse settings where receiving capabilities are highly heterogeneous, bottleneck capacities fluctuate, bottlenecks migrate, and session membership is dynamic.

With the Internet offering a single best-effort service, there have been numerous proposals of diversified network services that align better with the divergent needs of different distributed applications. The failure of these innovative architectures to gain wide deployment is primarily due to economic and legacy issues, rather than technical shortcomings. We propose a new paradigm for network service differentiation where design principles account explicitly for the multiplicity of Internet service providers and users as well as their economic interests in environments with partly deployed new services. Our key idea is to base the service differentiation on performance itself, rather than price. The proposed RD (Rate-Delay) services enable a user to choose between a higher transmission rate or low queuing delay at a congested network link. An RD router supports the two services by maintaining two queues per output link and achieves the intended rate-delay differentiation through simple link scheduling and dynamic buffer sizing. After analytically deriving specific rules for RD router operation, we conduct extensive simulations that confirm effectiveness of the RD services geared for incremental deployment in the Internet.

Virtual laboratories are a potential replacement for standard laboratory facilities. Use of these virtual resources can reduce cost and maintenance overheads for teaching institutions while still ensuring that students have access to real equipment. Previous work indicates that students respond well to such environments, but one important operational aspect has been overlooked. In this work, we consider instructor overhead by comparing the amount of work required to teach courses with and without the use of a virtual laboratory. In particular, we examine two graduate computer networking courses, each taught with the standard software-only approach and then taught later with the Open Network Laboratory. Our data show that the effort required by the instructor to use a virtual laboratory is not much more than in a software-only environment, and that the increased interaction between student and instructor can be beneficial as the student questions are primarily focused on fundamental networking concepts.

File transfer, web download, and many other applications are primarily interested in minimal delay achievable for their messages. In this paper, we investigate allocating the bottleneck link capacity to transmit messages efficiently but fairly. While SRPT (Shortest Remaining Processing Time) is an optimally efficient algorithm that minimizes average delay of messages, large messages might starve under SRPT in heavy load conditions. PS (Processor Sharing) and ViFi (Virtual Finish Time First) are fair but yield higher average delays than under SRPT. We explore the class of fair algorithms further and prove that no online algorithm in this class is optimally efficient. Then, we derive a fair algorithm SFS (Shortest Fair Sojourn) and report extensive experimental evidence that SFS is consistently more efficient than PS and even ViFi during either temporal overload or steady-state operation, with largest benefits achieved when average load is around the bottleneck link capacity. Furthermore, average delay under the fair SFS remains close to the minimum attained under the unfair SRPT.

In this paper, we present a model for investigating lower bounds on queuing under smooth congestion control with overprovisioned buffers. We consider an idealized protocol where all flows always transmit at equal rates. The ideally smooth transmission does not eliminate queuing altogether because packets of different flows might arrive to a node simultaneously due to asynchronous arrivals of the flows, which is intrinsic to computer networks. A prominent feature of our model is its simplicity, making analysis tractable and experiments scalable. Our results reveal steady-state queues of at least O(radicN) packets, where N is the number of flows. Hence, no congestion control protocol is able to avoid losses at a fully utilized link with a constant buffer shared by arbitrarily many flows.

To discover an efficient fair sending rate for a flow, Transmission Control Protocol (TCP) saturates the bottleneck link and its buffer until the router discards a packet. Such TCP-caused queuing is detrimental for interactive and other delay-sensitive applications. In this paper, we present Multimodal Control Protocol (MCP) which strives to maintain low queues and avoid congestion losses at network links. The multimodal MCP engages routers and hosts in limited explicit communication. A distinguishing property of MCP is stable transmission after converging to efficient fair states. To ensure convergence to fairness, MCP incorporates an innovative mechanism that enables a flow to urge all flows sharing its bottleneck links to operate in a fairing mode, dedicated to fairness improvement. To make the stable fair rates independent of round-trip times and packet sizes, MCP employs rate-based control and uniform timing of adjustments.

Interactive and other delay-sensitive applications are interested in keeping end-to-end delays of their packets minimal. Unfortunately, congestion control offered by transmission control protocol (TCP) and other existing protocols inflates the end-to-end delays by building up queues at bottleneck links. In this paper, we investigate multimodal control protocol (MCP) designed to maintain low queues after converging to the stable state where MCP flows utilize shared bottleneck links efficiently and fairly. To achieve this goal, MCP incorporates multiple modes of operation and allocates few bits in each packet header for explicit communication between hosts and routers. An innovative aspect of the explicit communication mechanism is an ability of a flow to urge all flows on its bottleneck links to switch temporarily into a fairing mode and thereby improve fairness of the bottleneck sharing. To make the fair sharing independent of round-trip times and packet sizes, MCP uses the sending bitrate as a control parameter and employs uniform adjustment timing for all flows. Our evaluation of MCP demonstrates its efficient fair operation and significantly shorter stable-state queues than under existing congestion control protocols.

Fair Queuing (FQ) algorithms provide isolation between packet flows, allowing max-min fair sharing of a link even when flows misbehave. However, fairness comes at the expense of per-flow state. To keep the memory requirement independent of the flow count, the router can isolate aggregates of flows, rather than individual flows. We investigate the feasibility of protecting individual flows under such aggregate isolation in the context of Multiple Queue Fair Queuing (MQFQ), where the router maintains a fixed number of queues and allows each flow to access multiple queues. MQFQ places packets into the shortest queue associated with their flow. The extra queues protect the flow against congestion caused by a misbehaving flow in a shared queue. However, multiple per-flow queues also enable the misbehaving flow to increase its unfairly acquired fraction of the link capacity. We discuss avoidance of packet reordering within a flow and compare MQFQ with prior schemes for aggregate scheduling.

The Open Network Laboratory (ONL) is an Internet-accessible virtual laboratory facility that can deliver a high quality laboratory experience in advanced networking [3,7]. Our experience with ONL indicates that it has potential to improve student understanding of fundamental networking concepts and increase enthusiasm for experimentation with complex technology. Furthermore, these benefits can be delivered with less effort from the instructor than using a traditional approach of socket programming and ns-2 simulation exercises. The system is built around a set of high-performance, extendible routers which connect personal computers acting as end systems. Users configure their virtual network through the Remote Laboratory Interface (RLI), an intuitive graphical interface. The RLI's real-time charts and user data facility make it easy to directly view the effect of system parameters on traffic behavior. These features can enhance learning by providing users with multiple representations of network phenomena. We describe how the ONL facilities have improved our ability to meet instructional objectives and discuss some approaches to improving the laboratory experience.

Instantaneous fair sharing (IFS) is a traditional network ideal prescribing to share the network capacity among competing applications fairly during any infinitesimal time interval. In this paper, we argue that IFS is an inappropriate ideal for the application of massive data transfers where the primary goal is to minimize message transfer times. We propose an alternative paradigm of virtual finish time first (ViFi) scheduling that dedicates the entire capacity to one message at a time in the order of message finish times under IFS. Unlike shortest remaining time first and other earlier algorithms for dedicated scheduling, ViFi provides a remarkable guarantee of delivering each message no later than under IFS. Our analysis and simulations show the dedicated ViFi scheduling offers significant reductions in the average transfer time. The above properties make ViFi a promising approach for resource allocation in emerging dedicated-channel networks that enable advance reservation of end-to-end channels between hosts.

We revisit the question of how much buffer an IP router should allocate for its droptail FIFO link. For a long time, setting the buffer size to the bitrate-delay product has been regarded as reasonable. Recent studies of interaction between queueing at IP routers and TCP congestion control offered alternative guidelines. First, we explore and reconcile contradictions between the existing rules. Then, we argue that the problem of link buffer sizing needs a new formulation: design a buffer sizing algorithm that accommodates needs of all Internet applications without engaging IP routers in any additional signaling. Our solution keeps network queues short: set the buffer size to 2L datagrams, where L is the number of input links. We also explain how end systems can utilize the network effectively despite such small buffering at routers.

Group subscription is a useful mechanism for multicast congestion control: RLM, RLC, FLID-DL, and WEBRC form a promising line of multi-group protocols where receivers provide no feedback to the sender but control congestion via group membership regulation. Unfortunately, the group subscription mechanism also o#ers receivers an opportunity to elicit self-beneficial bandwidth allocations. In particular, a misbehaving receiver can ignore guidelines for group subscription and choose an unfairly high subscription level in a multi-group multicast session. This poses a serious threat to fairness of bandwidth allocation. In this paper, we present the first solution for the problem of inflated subscription. Our design guards access to multicast groups with dynamic keys and consists of two independent components: DELTA (Distribution of ELigibility To Access) -- a novel method for in-band distribution of group keys to receivers that are eligible to access the groups according to the congestion control protocol, and SIGMA (Secure Internet Group Management Architecture) -- a generic architecture for key-based group access at edge routers.

No abstract available.

Abstract — Layered multicast is a common approach for dissemination of audio and video in heterogeneous network environments. Layered multicast schemes can be classified into two categories – feedback-based and feedback-free – depending on whether or not the scheme delivers feedback to the sender of the multicast session. Advocates of feedback-based schemes claim that the feedback is necessary to match the heterogeneous receiver capabilities efficiently. Supporters of feedbackfree schemes believe that feedback introduces significant complexity and that a moderate amount of additional layers can balance any benefit the feedback provides. Surprisingly, there has been no systematic evaluation of these claims. This paper compares feedback-based and feedback-free schemes quantitatively with respect to their abilities to align the provided service to the capabilities of the heterogeneous receivers. We believe that such an evaluation supplies valuable insights and guidelines to the designers of future multicast congestion control protocols. 1

Traffic reshaping and its impact on providing deterministic guarantees of timely data delivery in a packet-switched virtual-circuit fixed-packet network are investigated. Two types of traffic smoothing are considered: global reshaping (when traffic on all network connections is smoothed) and local reshaping (when the traffic specification is changed only for a single connection). The conditions when reshaping is beneficial are derived and the optimal values of traffic model parameters are obtained. In particular, it is shown that, when one tries to minimize end-to-end delay bounds for leaky bucket constrained traffic, the traffic either should be made constant bit rate (CBR) or should not be reshaped at all. It is proven that changing the leaky bucket specification to the dual leaky bucket specification is always able to yield better timeliness guarantees and utilisation of network resources. Finally, local reshaping for the dual leaky bucket model is studied.

A general model for traffic flows on packet-switched, virtual-circuit based, fixed-packet networks is introduced, and an exact schedulability test is obtained for systems of such flows. Rules are derived that make the evaluation of this schedulability test feasible and efficient under certain circumstances. The practical relevance of this approach is demonstrated by applying it to a number of standard traffic models.