Although GPS spoofing of individual devices has been extensively examined, little systematic research on swarm spoofing has been conducted. In general, swarm missions may allow each device to navigate independently for different tasks, and it is much more complicated to build corresponding spoofing signals for such general cases. To address this issue, we formulate a general swarm spoofing method to explore the theoretical capabilities and limitations of common cases. We then propose a basic swarm spoofing model to show that, if we try to spoof each receiver precisely, we can only attack a small number of receivers ($\leq 9$) simultaneously in theory. However, in practice, we often need to deal with many receivers. Therefore, we develop a method that can spoof more receivers with acceptable errors. We present a method to construct spoofing messages and evaluate its effectiveness in practical settings with simulations. Although this work focuses on the GPS system, the proposed ideas can be applied to other GNSSs.

As many mobile devices use Global Navigation Satellite Systems (GNSSs) to determine their locations for control, compromising such systems can result in serious consequences, as shown by existing GPS spoofing attacks. However, most such spoofing attacks focus on the effect of a single spoofer attacking a single receiver. In this paper, we investigate the impacts of a single spoofer on multiple receivers, motivated by research on attacking drone swarms. Our analysis independently shows that, using a single spoofer, multiple receivers at different locations in a spoofing area will see the same location reading. We consider the base case of spoofing four satellites and also the generic case when more satellites are involved in the spoofing attack. More importantly, we conduct real-world experiments to validate our analysis and demonstrate the potential threats to many practical applications. We use off-the-shelf SDR cards for spoofing and consumer GPS receivers for obtaining spoofed location readings. While this method can enable various attacks on mobile devices depending on GPS, it is also applicable to all existing GNSSs, because they use similar principles to determine locations.

IoT devices fundamentally lack built-in security mechanisms to protect themselves from security attacks. Existing works on improving IoT security mostly focus on detecting anomalous behaviors of IoT devices. However, these existing anomaly detection schemes may trigger an overwhelmingly large number of false alerts, rendering them unusable in detecting compromised IoT devices. In this paper we develop an effective and efficient framework, named CUMAD, to detect compromised IoT devices. Instead of directly relying on individual anomalous events, CUMAD aims to accumulate sufficient evidence in detecting compromised IoT devices, by integrating an autoencoder-based anomaly detection subsystem with a sequential probability ratio test (SPRT)-based sequential hypothesis testing subsystem. CUMAD can effectively reduce the number of false alerts in detecting compromised IoT devices, and moreover, it can detect compromised IoT devices quickly. Our evaluation studies based on the public-domain N-BaIoT dataset show that CUMAD can on average reduce the false positive rate from about 3.57% using only the autoencoder-based anomaly detection scheme to about 0.5%; in addition, CUMAD can detect compromised IoT devices quickly, with less than 5 observations on average.

While existing methods can disrupt drone invasions in a protected airspace, none of them is able to accurately guide a drone to a desired location for safe handling. To address this issue, theDrone Position Manipulation (DPM)attack is proposed in this article to explore weaknesses in common navigation algorithms of consumer drones. The main advantage of DPM is that it can accurately redirect an invading drone to a desired location, by carefully crafting the spoofed guidance inputs of the drone to exploit the adjustment of path-following navigation algorithms. Compared with existing methods, this is the first work to achieve such accurate quantitative control. Another main contribution of this work is that it explores three fundamental components (i.e., guidance sensing, state estimation, and navigation control) together to enable the quantitative manipulation of flight paths, different from all existing methods. Furthermore, a formal analysis of the attack range is presented for investigating where a drone can be redirected from its target under given constraints. The evaluation on the Software-in-the-loop (SITL) module ofArduPilotsystem shows that the proposed attack is able to not only accurately lead a drone to a redirected destination but also make it fairly far away from its target. Lastly, the proposed attack can be applied to many autopiloted systems, because it exploits common weaknesses in these systems.

Although some existing counterdrone measures can disrupt the invasion of certain consumer drone, to the best of our knowledge, none of them can accurately redirect it to a given location for defense. In this paper, we proposed a Drone Position Manipulation (DPM) attack to address this issue by utilizing the vulnerabilities of control and navigation algorithms used on consumer drones. As such drones usually depend on GPS for autopiloting, we carefully spoof GPS signals based on where we want to redirect a drone to, such that we indirectly affect its position estimates that are used by its navigation algorithm. By carefully manipulating these states, we make a drone gradually move to a path based on our requirements. This unique attack exploits the entire stack of sensing, state estimation, and navigation control together for quantitative manipulation of flight paths, different from all existing methods. In addition, we have formally analyzed the feasible range of redirected destinations for a given target. Our evaluation on open-source ArduPilot system shows that DPM is able to not only accurately lead a drone to a redirected destination but also achieve a large redirection range.

IoT device identification plays an important role in monitoring and improving the performance and security of IoT devices. Compared to traditional non-IoT devices, IoT devices provide us with both unique challenges and opportunities in detecting the types of IoT devices. Based on critical insights obtained in our previous work on understanding the network traffic characteristics of IoT devices, in this paper we develop an effective machine-learning based IoT device identification scheme, named iotID. In developing iotID, we extract 70 features of TCP flows from three complementary aspects: remote network servers and port numbers, packet-level traffic characteristics such as packet inter-arrival times, and flow-level traffic characteristics such as flow duration. Different from existing work, we take into account the imbalance nature of network traffic generated by various devices in both the learning and evaluation phases of iotID. Our performance studies based on network traffic collected on a typical smart home environment consisting of both IoT and non-IoT devices show that iotID can achieve a balanced accuracy score of above 99%.

Understanding network traffic characteristics of IoT devices plays a critical role in improving both the performance and security of IoT devices, including IoT device identification, classification, and anomaly detection. Although a number of existing research efforts have developed machine-learning based algorithms to help address the challenges in improving the security of IoT devices, none of them have provided detailed studies on the network traffic characteristics of IoT devices. In this paper we collect and analyze the network traffic generated in a typical smart homes environment consisting of a set of common IoT (and non-IoT) devices. We analyze the network traffic characteristics of IoT devices from three complementary aspects: remote network servers and port numbers that IoT devices connect to, flow-level traffic characteristics such as flow duration, and packet-level traffic characteristics such as packet inter-arrival time. Our study provides critical insights into the operational and behavioral characteristics of IoT devices, which can help develop more effective security and performance algorithms for IoT devices.

Freenet is a popular peer to peer anonymous content-sharing network, with the objective to provide the anonymity of both content publishers and retrievers. Despite more than a decade of active development and deployment and the adoption of well-established cryptographic algorithms in Freenet, it remains unanswered how well the anonymity objective of the initial Freenet design has been met. In this paper we develop a traceback attack on Freenet, and show that the originating machine of a content request message in Freenet can be identified; that is, the anonymity of a content retriever can be broken, even if a single request message has been issued by the retriever. We present the design of the traceback attack, and perform both experimental and simulation studies to confirm the feasibility and effectiveness of the attack. For example, with randomly chosen content requesters (and random contents stored in the Freenet testbed), Emulab-based experiments show that, for$24$to$43$percent of the content request messages, we can identify their originating machines. We also briefly discuss potential solutions to address the developed traceback attack. Despite being developed specifically on Freenet, the basic principles of the traceback attack and solutions have important security implications for similar anonymous content-sharing systems.

Abstract Spamming botnets present a critical challenge in the control of spam messages because of the sheer volume and wide spread of the botnet members. In this paper, we advocate the approach for recipient mail servers to filter messages directly delivered from remote end‐user (EU) machines, given that the majority of spamming bots are EU machines. We develop a support vector machine (SVM)‐based classifier to separate EU machines from legitimate mail server (LMS) machines, using a set of machine features that cannot be easily manipulated by spammers. We investigate the efficacy and performance of the SVM‐based classifier using a number of real‐world data sets. Our performance studies show that the SVM‐based classifier is indeed a feasible and effective approach in distinguishing EU machines from LMS machines. For example, training and testing on an aggregated data set containing both EU machines and LMS machines, on average, we found that the SVM‐based classifier can achieve a 99.25 % detection accuracy, with very small false positive rate (0.35%) and false negative rate (1.27%), significantly outperforming eight Domain Name System‐based blacklists widely used today. Copyright © 2012 John Wiley & Sons, Ltd.

Given the large volume of content on the Internet, scalability is one of the critical challenges in the design and development of information-centric network (ICN) architectures. In this paper we develop a scalable name-based inter-domain routing (NIDR) system that can meet the demanding requirement of supporting the large volume of content on the Internet in ICNs. NIDR adopts two critical techniques to improve its scalability. First, NIDR assumes a URL-like hierarchical content naming structure, and routes content-request packets based on only the domain name of content instead of the complete content name. Second, given the large number of domain names on the Internet, only a small subset of Internet domain names are announced at the inter-domain level. Domain names unknown to the NIDR system are first mapped (and routed) to their corresponding attachment point (AP) networks that are in the NIDR system, which is supported by a name resolution service. In addition to presenting the design of the NIDR system, we also evaluate the performance of NIDR and compare it with both BGP and EPIC, an enhancement over BGP. Our simulation studies based on the simBGP simulator show that NIDR can perform comparably with EPIC.

As privacy becomes an increasingly important issue on today's Internet, attacks on anonymous tools gain more attention. In this paper, we investigated countermeasures to a routing table insertion (RTI) attack on Freenet. We analyzed the key factors supporting the RTI attack, and proposed a simple randomized routing method to mitigate the RTI or similar attacks. We implemented the proposed method on the Freenet Thynix simulator. Our results show that the proposed method works well on small world topologies and thus a feasible choice to deal with the RTI attack on Freenet. We are further investigating more effective countermeasures based on these results.

A traceback attack was recently developed on Freenet, which can identify the originating machine of a content request message, even if a single content request message has been issued by a content retriever. The traceback attack exploited a few fine-grained design and development decisions made in Freenet, including the unique identifier (UID) based mechanism to prevent routing loops of content request messages. In this paper we develop a simple yet effective scheme named dynID to thwart the traceback attack on Freenet. In dynID, the UID associated with a content request message is dynamically changed at the beginning portion of the message forwarding path. As a consequence, an attacker can only trace back a content request message to the node where the UID value is last changed; it cannot uniquely determine the originating machine of the message. Importantly, dynID only has negligible impacts on the performance of Freenet in locating content on the network. For example, our simulation studies based on the original Freenet source code show that, for all content requests, we can successfully locate the corresponding requested content.

Freenet is a popular peer to peer anonymous network, with the objective to provide the anonymity of both content publishers and retrievers. Despite more than a decade of active development and deployment and the adoption of well-established cryptographic algorithms in Freenet, it remains unanswered how well the anonymity objective of the initial Freenet design has been met. In this paper we develop a traceback attack on Freenet, and show that the originating machine of a content request message in Freenet can be identified; that is, the anonymity of a content retriever can be broken, even if a single request message has been issued by the retriever. We present the design of the traceback attack, and perform Emulab-based experiments to confirm the feasibility and effectiveness of the attack. With randomly chosen content requesters (and random contents stored in the Freenet testbed), the experiments show that, for 24% to 43% of the content request messages, we can identify their originating machines. We also briefly discuss potential solutions to address the developed traceback attack. Despite being developed specifically on Freenet, the basic principles of the traceback attack and solutions have important security implications for similar anonymous content sharing systems.

Compromised machines are one of the key security threats on the Internet; they are often used to launch various security attacks such as spamming and spreading malware, DDoS, and identity theft. Given that spamming provides a key economic incentive for attackers to recruit the large number of compromised machines, we focus on the detection of the compromised machines in a network that are involved in the spamming activities, commonly known as spam zombies. We develop an effective spam zombie detection system named SPOT by monitoring outgoing messages of a network. SPOT is designed based on a powerful statistical tool called Sequential Probability Ratio Test, which has bounded false positive and false negative error rates. In addition, we also evaluate the performance of the developed SPOT system using a two-month e-mail trace collected in a large US campus network. Our evaluation studies show that SPOT is an effective and efficient system in automatically detecting compromised machines in a network. For example, among the 440 internal IP addresses observed in the e-mail trace, SPOT identifies 132 of them as being associated with compromised machines. Out of the 132 IP addresses identified by SPOT, 126 can be either independently confirmed (110) or highly likely (16) to be compromised. Moreover, only seven internal IP addresses associated with compromised machines in the trace are missed by SPOT. In addition, we also compare the performance of SPOT with two other spam zombie detection algorithms based on the number and percentage of spam messages originated or forwarded by internal machines, respectively, and show that SPOT outperforms these two detection algorithms.

BGP prefix hijacking is a serious security threat on the Internet. In this paper we propose a region-based BGP announcement filtering scheme (RBF) to improve the BGP security. In contrast to existing solutions that indifferently prevent or detect prefix hijacking attacks, RBF enables differentiated AS and prefix filtering treatment and blends prefix hijacking prevention with deterrence. RBF is a light-weight BGP security scheme that provides strong incremental deployment incentive and better prefix hijacking deterrence. Experimental studies based on real Internet numbers allocation information and BGP traces show that RBF is a feasible and effective scheme in improving BGP security. For example, on the days without known BGP prefix hijacking attacks, only a small number of BGP announcements will be flagged as attacks. Importantly, by applying RBF to known BGP prefix hijacking attacks, we show that RBF can detect and filter both large-scale and smallscale BGP prefix hijacking attacks even if only a single prefix is hijacked.

Compromised machines are one of the key security threats on the Internet; they are often used to launch various security attacks such as DDoS, spamming, and identity theft. In this paper we address this issue by investigating effective solutions to automatically identify compromised machines in a network. Given that spamming provides a key economic incentive for attackers to recruit the large number of compromised machines, we focus on the subset of compromised machines that are involved in the spamming activities, commonly known as spam zombies. We develop an effective spam zombie detection system named SPOT by monitoring outgoing messages of a network. SPOT is designed based on a powerful statistical tool called Sequential Probability Ratio Test, which has bounded false positive and false negative error rates. Our evaluation studies based on a two- month email trace collected in a large U.S. campus network show that SPOT is an effective and efficient system in automatically detecting compromised machines in a network. For example, among the 440 internal IP addresses observed in the email trace, SPOT identifies 132 of them as being associated with compromised machines. Out of the 132 IP addresses identified by SPOT, 126 can be either independently confirmed (110) or highly likely (16) to be compromised. Moreover, only 7 internal IP addresses associated with compromised machines in the trace are missed by SPOT.

Round robin based packet schedulers generally have a low complexity and provide long-term fairness. The main limitation of such schemes is that they do not support short-term fairness. In this paper, we propose a new low complexity round robin scheduler, called Fair Round Robin (FRR), that overcomes this limitation. FRR has similar complexity and long-term fairness properties as the stratified round robin scheduler, a recently proposed scheme that arguably provides the best quality-of-service properties among all existing round robin based low complexity packet schedulers. FRR offers better short-term fairness than stratified round robin and other existing round robin schedulers.

To realize a path in an InfiniBand network, an address, known as local identifier (LID) in the InfiniBand specification, must be assigned to the destination of the path and used in the forwarding tables of intermediate switches to direct the traffic following the path. Hence, routing in InfiniBand has two components: (1) computing all paths, and (2) assigning LIDs to destinations and using them in intermediate switches to realize the paths. We refer to the task of computing paths as path computation and the task of assigning LIDs as LID assignment. This paper focuses on the LID assignment component, whose major issue is to minimize the number of LIDs required to support a given set of paths. We prove that the problem of realizing a given set of paths with a minimum number of LIDs is NP-complete, develop an integer linear programming formulation for this problem, design a number of heuristics that are effective and efficient in practical cases, and evaluate the performance of the heuristics through simulation. The experimental results indicate that the performance of our best performing heuristic is very close to optimal.

This paper develops and studies a traffic-aware inter-domain routing (TIDR) protocol, which drastically improves the stability of the BGP-based inter-domain routing system. TIDR is designed based on two important Internet properties-the Internet access non-uniformity and the prevalence of transient failures. In TIDR, a network prefix is classified at an AS as either significant or insignificant from the viewpoint of a neighboring AS, depending on the amount of traffic exchanged between the prefix and the neighbor (including transit traffic). While BGP updates of significant prefixes are propagated with a higher priority, the propagation of updates of insignificant prefixes is aggressively slowed down. In particular, TIDR tries to localize the effect of transient failures on insignificant prefixes instead of propagating it onto the whole Internet. Importantly, TIDR will not create traffic black-holes due to the localization of transient failures. In this paper we present the design of TIDR and perform simulation experiments to study the performance of TIDR. Our simulation results show that TIDR can greatly improve the stability of BGP and also outperforms other existing schemes including Ghost Flushing and EPIC.

The distributed denial-of-service (DDoS) attack is a serious threat to the legitimate use of the Internet. Prevention mechanisms are thwarted by the ability of attackers to forge or spoof the source addresses in IP packets. By employing IP spoofing, attackers can evade detection and put a substantial burden on the destination network for policing attack packets. In this paper, we propose an interdomain packet filter (IDPF) architecture that can mitigate the level of IP spoofing on the Internet. A key feature of our scheme is that it does not require global routing information. IDPFs are constructed from the information implicit in border gateway protocol (BGP) route updates and are deployed in network border routers. We establish the conditions under which the IDPF framework correctly works in that it does not discard packets with valid source addresses. Based on extensive simulation studies, we show that, even with partial deployment on the Internet, IDPFs can proactively limit the spoofing capability of attackers. In addition, they can help localize the origin of an attack packet to a small number of candidate networks.

This paper describes the design and development of a software system to support law enforcement in investigating and prosecuting email based crimes. It focuses on phishing scams which use emails to trick users into revealing personal data. The system described in this paper, called the Undercover Multipurpose Anti-Spoofing Kit (UnMask), will enable investigators to reduce the time and effort needed for digital forensic investigations of email-based crimes. A novel aspect of UnMask is its use of a database to not only store information related to the email and its constituent parts (such as IP addresses, links, domain names), but also to organize a workflow to automatically launch UNIX tools to collect additional information from the Internet. The retrieved information is in turn added to the database. Reports can then be automatically generated according to the needs of the forensic investigator, including correlations across multiple email data stored in the database. UnMask is a working system. To the best of our knowledge, UnMask is the first comprehensive system that can automatically analyze emails and generate forensic reports that can be used for subsequent investigation and prosecution.

Abstract — To realize a path in an InfiniBand network, an address, known as Local IDentifier (LID) in the InfiniBand specification, must be assigned to the destination of the path and used in the forwarding tables of intermediate switches to direct the traffic following the path. Hence, routing in InfiniBand has two components: (1) computing all paths, and (2) assigning LIDs to destinations and using them in intermediate switches to realize the paths. We refer to the task of computing paths as path computation and the task of assigning LIDs as LID assignment. This paper focuses on the LID assignment component, whose major issue is to minimize the number of LIDs required to support a given set of paths. We prove that the problem of realizing a given set of paths with a minimum number of LIDs is NPcomplete, develop an integer linear programming formulation for this problem, design a number of heuristics that are effective and efficient in practical cases, and evaluate the performance of the heuristics through simulation. The experimental results indicate that the performance of our best performing heuristic is very close to optimal. We further demonstrate that by separating path computation from LID assignment and using the schemes that are known to achieve good performance for path computation and LID assignment separately, more effective routing schemes than existing ones can be developed. Index Terms — InfiniBand, LID Assignment, NP-Complete I.

By analyzing a two-month trace of more than 25 million emails received at a large US university campus network, of which more than 18 million are spam messages, we characterize the spammer behavior at both the mail server and the network levels. We also correlate the arrivals of spam with the BGP route updates to study the network reachability properties of spammers. Among others, our significant findings are: (a) the majority of spammers (93% of spam only mail servers and 58% of spam only networks) send only a small number of spam messages (no more than 10); (b) the vast majority of both spam messages (91.7%) and spam only mail servers (91%) are from mixed networks that send both spam and non-spam messages; (c) the majority of both spam messages (68%) and spam mail servers (74%) are from a few regions of the IP address space (top 20 "/8" address spaces); (d) a large portion of spammers (81% of spam only mail servers and 27% of spam only networks) send spam only within a short period of time (no longer than one day out of the two months); and (e) network prefixes for a non-negligible portion of spam only networks (6%) are only visible for a short period of time (within 7 days), coinciding with the spam arrivals from these networks. We discuss the implications of the findings for the current anti-spam efforts, and more importantly, for the design of future email delivery architectures.

Fat-tree based system area networks have been widely adopted in high performance computing clusters. In such systems, the routing is often deterministic and the traffic demand is usually uncertain and changing. In this paper, we study routing performance on fat-tree based system area networks with deterministic routing under the assumption that the traffic demand is uncertain. The performance of a routing algorithm under uncertain traffic demands is characterized by the oblivious performance ratio that bounds the relative performance of the routing algorithm and the optimal routing algorithm for any given traffic demand. We consider both single path routing where the traffic between each source-destination pair follows one path, and multi-path routing where multiple paths can be used for the traffic between a source-destination pair. We derive lower bounds of the oblivious performance ratio of any single path routing scheme for fat-tree topologies and develop single path oblivious routing schemes that achieve the optimal oblivious performance ratio for commonly used fat-tree topologies. These oblivious routing schemes provide the best performance guarantees among all single path routing algorithms under uncertain traffic demands. For multi-path routing, we show that it is possible to obtain a scheme that is optimal for any traffic demand (an oblivious performance ratio of 1) on the fat-tree topology. These results quantitatively demonstrate that single path routing cannot guarantee high routing performance while multi-path routing is very effective in balancing network loads on the fat-tree topology.

Core stateless packet scheduling systems have received considerable attention in recent years because of their scalability in supporting per-flow quality of services guarantees. In such a system core routers do not need to maintain per-flow state and do not need to perform per-flow operations such as per-flow classification, per-flow queueing, and per-flow scheduling. On the other hand, existing core stateless packet schedulers require core routers to sort incoming packets based on their virtual finish times. This sorting operation results in the worst-case runtime complexity of O(log2N), where N is the number of packets in a scheduler. In this paper we propose a bin-based core stateless queueing (BCSQ) algorithm, which achieves constant runtime complexity that is independent of the number of packets in the scheduler. We present the detailed design of BCSQ and derive the worst-case end-to-end delay bounds for packets in a network of BCSQ. In addition, we investigate the effects of the configurable parameters of BCSQ on the performance of BCSQ networks. Simulation studies are also performed to illustrate the efficacy and performance of BCSQ.

a serious threat to the legitimate use of the Internet. Prevention mechanisms are thwarted by the ability of attackers to forge, or spoof, the source addresses in IP packets. By employing IP spoofing, attackers can evade detection and put a substantial burden on the destination network for policing attack packets. In this paper we propose an inter-domain packet filter (IDPF) architecture that can mitigate the level of IP spoofing on the Internet. IDPFs are constructed from the information implicit in BGP route updates and are deployed in network border routers. A key feature of the scheme is that it does not require global routing information. Based on extensive simulation studies, we show that even with partial deployment on the Internet, IDPFs can proactively limit the spoofing capability of attackers. In addition, they can help localize the origin of an attack packet to a small number of candidate networks. I.

In this paper, we propose a hybrid architecture to integrate peer-to-peer (P2P) streaming approaches with content distribution networks (CDNs). We further utilize multiple description (MD) coding in this architecture to address challenging issues in P2P approaches such as low peer upstream bandwidth and low quality assurance. The proposed schemes take advantage of the high availability of CDNs, the flexibility of layered MD, and the high scalability of P2P approaches to better utilize peer upstream bandwidth, reduce server load, and assure service quality. In addition, we evaluate the performance of the proposed approach through analysis and simulation

Slow convergence in the Internet can be directly attributed to the "path exploration" phenomenon, inherent in all path vector protocols. The root cause for path exploration is the dependency among paths propagated through the network. Addressing this problem in BGP is particularly difficult as the AS paths exchanged between BGP routers are highly summarized. In this paper, we describe why path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism - forward edge sequence numbers - to annotate the AS paths with additional "path dependency" information. We then develop an enhanced path vector algorithm, EPIC, shown to limit path exploration and lead to faster convergence. In contrast to other solutions, ours is shown to be correct on a very general model of Internet topology and BGP operation. Using theoretical analysis and simulations, we demonstrate that EPIC can achieve a dramatic improvement in routing convergence, compared to BGP and other existing solutions.

In this paper, we propose an O(1) complexity round robin scheduler, called fair round robin (FRR), that provides good fairness and delay properties. Unlike existing O(1) complexity round robin schedulers that can only achieve long term fairness, FRR not only provides proportional fairness, but also maintains a constant normalized worst-case fair index as defined in Bennett and Zhang's work. This means that FRR guarantees both short term and long term fairness among all backlogged flows.

In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay service. In our study, we consider two classes of aggregate packet scheduling algorithms: the static earliest time first (SETF) and dynamic earliest time first (DETF). Through these two classes of aggregate packet scheduling (and together with the simple FIFO packet scheduling algorithm), we show that, with additional timestamp information encoded in the packet header for scheduling purposes, we can significantly increase the maximum allowable network utilization level, while, at the same time, reducing the worst-case edge-to-edge delay bound. Furthermore, we demonstrate how the number of the bits used to encode the timestamp information affects the trade-off between the maximum allowable network utilization level and the worst-case edge-to-edge delay bound. In addition, the more complex DETF algorithms have far superior performance than the simpler SETF algorithms. These results illustrate the fundamental trade-offs in aggregate packet scheduling algorithms and shed light on their provisioning power in support of guaranteed delay service.

Route flap damping (RFD) is anecdotally considered to be a key contributor in the stability of the inter-domain routing system. It works by suppressing advertisements about persistently flapping routes, which otherwise would propagate throughout the Internet. It was recently shown that relatively stable routes, i.e., routes that fail occasionally, can be incorrectly suppressed by this mechanism for substantially long periods of time. This can be traced back to the complex interaction between BGP path exploration and the mechanism used by RFD to identify route flaps. In this paper we study the distinctive feature that distinguishes the sequence of updates following a single network event from that of persistently unstable routes. Based on this characteristic, we propose a new BGP route flap damping algorithm, RFD+, with the following properties - 1) it can correctly distinguish between route flaps and normal path exploration; 2) it suppresses routes that are frequently and persistently changing; and 3) it does not affect routes that fail occasionally. We present the algorithm and discuss its relevant properties; simulation studies are also conducted to illustrate the performance of our algorithm.

We present a novel bandwidth broker architecture for scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, the QoS reservation states are stored at and managed by a bandwidth broker. There are several advantages of such a bandwidth broker architecture. Among others, it avoids the problem of inconsistent QoS states faced by the conventional hop-by-hop, distributed admission control approach. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed recently. This virtual time reference system provides a unifying framework to characterize, in terms of their abilities to support delay guarantees, both the per-hop behaviors of core routers and the end-to-end properties of their concatenation. We focus on the design of efficient admission control algorithms under the proposed bandwidth broker architecture. We consider both per-flow end-to-end guaranteed delay services and class-based guaranteed delay services with flow aggregation. Using our bandwidth broker architecture, we demonstrate how admission control can be done on a per domain basis instead of on a "hop-by-hop" basis. Such an approach may significantly reduce the complexity of the admission control algorithms. In designing class-based admission control algorithms, we investigate the problem of dynamic flow aggregation in providing guaranteed delay services and devise a new apparatus to effectively circumvent this problem. We conduct detailed analyses to provide theoretical underpinning for our schemes as well as to establish their correctness. Simulations are also performed to demonstrate the efficacy of our schemes.

We advocate the notion of service overlay network (SON) as an effective means to address some of the issues, in particular, end-to-end quality of service (QoS), plaguing the current Internet, and to facilitate the creation and deployment of value-added Internet services such as VoIP, Video-on-Demand, and other emerging QoS-sensitive services. The SON purchases bandwidth with certain QoS guarantees from the individual network domains via bilateral service level agreement (SLA) to build a logical end-to-end service delivery infrastructure on top of the existing data transport networks. Via a service contract, users directly pay the SON for using the value-added services provided by the SON. In this paper, we study the bandwidth provisioning problem for a SON which buys bandwidth from the underlying network domains to provide end-to-end value-added QoS sensitive services such as VoIP and Video-on-Demand. A key problem in the SON deployment is the problem of bandwidth provisioning, which is critical to cost recovery in deploying and operating the value-added services over the SON. The paper is devoted to the study of this problem. We formulate the bandwidth provisioning problem mathematically, taking various factors such as SLA, service QoS, traffic demand distributions, and bandwidth costs. Analytical models and approximate solutions are developed for both static and dynamic bandwidth provisioning. Numerical studies are also performed to illustrate the properties of the proposed solutions and demonstrate the effect of traffic demand distributions and bandwidth costs on SON bandwidth provisioning.

We advocate the notion of service overlay network (SON) as an effective means to address some of the issues, in particular end-to-end QoS, plaguing the current Internet, and to facilitate the creation and deployment of value-added Internet services such as VoIP, video-on-demand, and other emerging QoS-sensitive services. A SON purchases bandwidth with certain QoS guarantees from individual network domains via a bilateral service level agreement (SLA) to build a logical end-to-end service delivery infrastructure on top of existing data transport networks. Via a service contract, users directly pay the SON provider for using the value-added services provided by the SON. We study the bandwidth provisioning problem for a service overlay network which is critical to the cost recovery in deploying and operating value-added services over the SON. We mathematically formulate the bandwidth provisioning problem, taking into account various factors such as SLA, service QoS, traffic demand distributions, and bandwidth costs. Analytical models and approximate solutions are developed for both static and dynamic bandwidth provisioning. Numerical studies are also performed to illustrate the properties of the proposed solutions and demonstrate the effect of traffic demand distributions and bandwidth costs on the bandwidth provisioning of a SON.

In this paper we study the scalability issue in the design of a centralized bandwidth broker model for dynamic control and management of QoS provisioning. We propose and develop a path-oriented, quota-based dynamic bandwidth allocation mechanism for efficient admission control operations under the centralized bandwidth broker model. We demonstrate that this dynamic bandwidth allocation mechanism can significantly reduce the overall number of QoS state accesses/updates, thereby increasing the overall call processing capability of the bandwidth broker. Based on the proposed dynamic bandwidth allocation mechanism, we also extend the centralized architecture with a single bandwidth broker to a hierarchically distributed architecture with multiple bandwidth brokers to further improve its scalability. Our study demonstrates that the bandwidth broker architecture can be designed in such a manner that it scales with the increase in the network capacity.

This paper presents architecture and mechanisms to support multiple QoS under the DiffServ paradigm. On the data plane, we present a node architecture based on the virtual time reference system (VTRS), which is a unifying scheduling framework for scalable support of the guaranteed service. The key building block of our node architecture is the core-stateless virtual clock (CSVC) scheduling algorithm, which, in terms of providing delay guarantee, has the same expressive power as a stateful weighted fair queueing (WFQ) scheduler. Based on the CSVC scheduler, we design a node architecture that is capable of supporting integrated transport of the guaranteed service (GS), the premium service (PS), the assured service (AS), and the traditional best-effort (BE) service. On the control plane, we present a BE architecture to provide flexible resource allocation and QoS provisioning. Simulation results demonstrate that our architecture and mechanisms can provide scalable and flexible transport of integrated traffic of the GS, the PS, the AS, and the BE services.

We investigate the fundamental trade-offs in aggregate packet scheduling for the support of guaranteed delay service. Besides the simple FIFO packet scheduling algorithm, we consider two new classes of aggregate packet scheduling algorithms: the static earliest time first (SETF) and dynamic earliest time first (DETF). Through these two classes of aggregate packet scheduling, we show that, with additional time stamp information encoded in the packet header for scheduling purpose, we can significantly increase the maximum allowable network utilization level, while at the same time reducing the worst-case edge-to-edge delay bound. Furthermore, we demonstrate how the number of the bits used to encode the time stamp information affects the trade-off between the maximum allowable network utilization level and the worst-case edge-to-edge delay bound. In addition, the more complex DETF algorithms have far better performance than the simpler SETF algorithms. These results illustrate the fundamental trade-offs in aggregate packet scheduling algorithms and shed light on their provisioning power in support of guaranteed delay service.

We propose and develop a novel virtual time reference system as a unifying scheduling framework to provide scalable support for guaranteed services. This virtual time reference system is designed as a conceptual framework upon which guaranteed services can be implemented in a scalable manner using the DiffServ paradigm. The key construct in the proposed virtual time reference system is the notion of packet virtual time stamps, whose computation is core stateless, i.e., no per-flow states are required for its computation. We lay the theoretical foundation for the definition and construction of packet virtual time stamps. We describe how per-hop behavior of a core router (or rather its scheduling mechanism) can be characterized via packet virtual time stamps, and based on this characterization establish end-to-end per-flow delay bounds. Consequently, we demonstrate that, in terms of its ability to support guaranteed services, the proposed virtual time reference system has the same expressive power and generality as the IntServ model. Furthermore, we show that the notion of packet virtual time stamps leads to the design of new core stateless scheduling algorithms, especially work-conserving ones. In addition, our framework does not exclude the use of existing scheduling algorithms such as stateful fair queuing algorithms to support guaranteed services.