Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs), provides effective and flexible network service management in a cloud computing environment. Due to the vulnerabilities of software-implemented VNFs, existing research has introduced VNF backup servers to achieve the fault-tolerance of VNFs and improve the availability of SFCs. However, they either do not consider the failures of backup servers or do not aim to maximize the availability of the entire SFC. In this paper, we study how to maximize the availability of an SFC, considering that both VNFs and backup servers can fail. We refer to the problem as SAM: service function chaining availability maximization problem. Given an SFC and a set of backup servers placed inside a cloud data center network, the failure probabilities of the VNFs and the backup servers, the goal of SAM is to assign backup servers to VNFs to maximize the availability of the SFC while satisfying the backup capacity constraint of the servers. We design a suite of optimal and efficient algorithms to solve SAM. Via extensive simulations with different network parameters, we show that our work outperforms the existing research by up to 21.7% in SFC availability, demonstrating the effectiveness of our algorithms in achieving high fault tolerance of SFC in cloud data centers.

As software programs, Virtual Network Functions (VNFs) introduce new challenges to network availability due to their potential software failures. Existing models on the availability of VNF networks did not consider all the possible hardware and software failures, making them incapable of analyzing the end-to-end availability of a path. Furthermore, they did not capture the correlation between repeating nodes and links in the path, resulting in inaccurate analytical results. In this paper, we propose a new analytical model, which considers all hardware and software failures as well as the effect of repeating components, to effectively analyze the end-to-end availability of a flow path in VNF networks. On top of the analytical model, we formulate the Highest Availability Path (HAP) problem that finds the flow path with the highest end-to-end availability, and prove its NP-hardness by reduction from the Node-Weighted Steiner Tree problem. Next, we propose two algorithms for HAP: the first one based on a Steiner Tree approximation algorithm, having high time complexity and serving as a performance benchmark; the second one using a dynamic programming approach to search a multi-layer graph in polynomial time. Finally, we present extensive evaluation data to demonstrate the effectiveness of the Layered Search algorithm, which achieves comparable performance as that of the Steiner Tree based algorithm and runs faster by four orders of magnitude.

We propose a new algorithmic framework for traffic-optimal virtual network function (VNF) placement and migration for policy-preserving data centers (PPDCs). As dynamic virtual machine (VM) traffic must traverse a sequence of VNFs in PPDCs, it generates more network traffic, consumes higher bandwidth, and causes additional traffic delays than a traditional data center. We design optimal, approximation, and heuristic traffic-aware VNF placement and migration algorithms to minimize the total network traffic in the PPDC. In particular, we propose the first traffic-aware constant-factor approximation algorithm for VNF placement, a Pareto-optimal solution for VNF migration, and a suite of efficient dynamic-programming (DP)-based heuristics that further improves the approximation solution. At the core of our framework are two new graph-theoretical problems that have not been studied. Using flow characteristics found in production data centers and realistic traffic patterns, we show that a) our VNF migration techniques are effective in mitigating dynamic traffic in PPDCs, reducing the total traffic cost by up to 73%, b) our VNF placement algorithms yield traffic costs 56% to 64% smaller than those by existing techniques, and c) our VNF migration algorithms outperform the state-of-the-art VM migration algorithms by up to 63% in reducing dynamic network traffic.

Network Function Virtualization (NFV) enables flexible implementation of network functions, also called middleboxes, as virtual machines running on standard servers. However, the flexibility also makes it a challenge to optimally place middleboxes, because a middlebox may be hosted by different servers at different locations. The middlebox placement challenge is further complicated by additional constraints, including the capability of middleboxes to change traffic volumes and dependency between them. In this paper, we address the optimal placement challenge of NFV middleboxes for the data plane using a software-defined networking (SDN) approach. First, we formulate the optimization problem to place traffic-changing and interdependent middleboxes. When the flow path is predetermined, we design optimal algorithms to place a non-ordered or totally-ordered middlebox set, and propose a low-complexity solution for the general scenario of a partially-ordered middlebox set after proving its NP-hardness. When the flow path is not predetermined, we show that the problem is NP-hard even for a non-ordered or totally-ordered middlebox set, and propose an efficient traffic and space aware routing algorithm. We have evaluated the proposed algorithms using large scale simulations and a real application based SDN prototype, and present extensive evaluation results to demonstrate the superiority of our design over benchmark solutions.

Network function virtualization enables flexible implementation of network functions, or middleboxes, as virtual machines running on standard servers. However, the flexibility also creates a challenge for efficiently placing such middleboxes, due to the availability of multiple hosting servers, capability of middleboxes to change traffic volumes, and dependency between middleboxes. In this paper, we address the optimal placement challenge of NFV middleboxes, and propose solutions for middleboxes of different traffic changing effects and with different dependency relations. First, we formulate the Traffic Aware Placement of Interdependent Middleboxes problem as a graph optimization problem. When the flow path is predetermined, we design optimal algorithms to place a non-ordered or totally-ordered middlebox set, and propose an efficient heuristic for the general scenario of a partially-ordered middlebox set after proving its NP-hardness. When the flow path is not predetermined, we show that the problem is NP-hard even for a non-ordered middlebox set, and propose a traffic and space aware routing heuristic. We have evaluated the proposed algorithms using large scale simulations and prototype experiments, and present extensive evaluation results to demonstrate the effectiveness of our design.

Network function virtualization (NFV) enables flexible deployment of middleboxes as virtual machines running on general hardware. Since different middleboxes may change the volume of processed traffic in different ways, improper deployment of NFV middleboxes will result in hot spots and congestion. In this paper, we study the traffic changing effects of middleboxes, and propose software-defined networking based middlebox placement solutions to achieve optimal load balancing. We formulate the traffic aware middlebox placement (TAMP) problem as a graph optimization problem with the objective to minimize the maximum link load ratio. First, we solve the TAMP problem when the flow paths are predetermined, such as the case in a tree. For a single flow, we propose the least-first-greatest-last (LFGL) rule and prove its optimality; for multiple flows, we first show the NP-hardness of the problem, and then propose an efficient heuristic. Next, for the general TAMP problem without predetermined flow paths, we prove that it is NP-hard even for a single flow, and propose the LFGL based MinMax routing algorithm by integrating LFGL with MinMax routing. We use a joint emulation and simulation approach to evaluate the proposed solutions, and present extensive experimental and simulation results to demonstrate the effectiveness of our design.

Data centers consume significant amounts of energy. As severs become more energy efficient with various energy saving techniques, the data center network (DCN) has been accounting for 20% or more of the energy consumed by the entire data center. While DCNs are typically provisioned with full bisection bandwidth, DCN traffic demonstrates fluctuating patterns. The objective of this work is to improve the energy efficiency of DCNs during off-peak traffic time by powering off idle devices. Although there exist a number of energy optimization solutions for DCNs, they consider only either the hosts or network, but not both. In this paper, we propose a joint optimization scheme that simultaneously optimizes virtual machine (VM) placement and network flow routing to maximize energy savings, and we also build an OpenFlow based prototype to experimentally demonstrate the effectiveness of our design. First, we formulate the joint optimization problem as an integer linear program, but it is not a practical solution due to high complexity. To practically and effectively combine host and network based optimization, we present a unified representation method that converts the VM placement problem to a routing problem. In addition, to accelerate processing the large number of servers and an even larger number of VMs, we describe a parallelization approach that divides the DCN into clusters for parallel processing. Further, to quickly find efficient paths for flows, we propose a fast topology oriented multipath routing algorithm that uses depth-first search to quickly traverse between hierarchical switch layers and uses the best-fit criterion to maximize flow consolidation. Finally, we have conducted extensive simulations and experiments to compare our design with existing ones. The simulation and experiment results fully demonstrate that our design outperforms existing hostor network-only optimization solutions, and well approximates the ideal linear program.

Flow-level bandwidth provisioning (FBP) achieves fine-grained bandwidth assurance for individual flows. It is especially important for virtualization-based computing environments such as data centers. However, existing flow-level bandwidth provisioning solutions suffer from a number of drawbacks, including high implementation complexity, poor performance guarantees, and inefficiency to process variable length packets. In this paper, we study flow-level bandwidth provisioning for Combined Input Crosspoint Queued (CICQ) switches in the OpenFlow context. First, we propose the Flow-level Bandwidth Provisioning algorithm for CICQ switches, which reduces the switch scheduling problem to multiple instances of fair queuing problems, each utilizing a well-studied fair queuing algorithm. We theoretically prove that FBP can closely emulate the ideal Generalized Processing Sharing model, and accurately guarantee the provisioned bandwidth. Furthermore, we implement FBP in the OpenFlow software switch to obtain realistic performance data by a prototype. Leveraging the capability of OpenFlow to define and manipulate flows, we experimentally demonstrate a practical flow-level bandwidth provisioning solution. Finally, we conduct extensive simulations and experiments to evaluate the design. The simulation data verify the correctness of the analytical results, and show that FBP achieves tight performance guarantees. The experiment results demonstrate that our OpenFlow-based prototype can conveniently and accurately provision bandwidth at the flow level.

Modern data center networks (DCNs) often use multi-rooted topologies, which offer multipath capability, for increased bandwidth and fault tolerance. However, traditional routing algorithms for the Internet have no or limited support for multipath routing, and cannot fully utilize available bandwidth in such DCNs. In this paper, we study the multipath routing problem for DCNs. We first formulate the problem as an integer linear program, but it is not suitable for fast on-the-fly route calculation. For a practical solution, we propose the Depth-First Worst-Fit Search based multipath routing algorithm. The main idea is to use depth-first search to find a sequence of worst-fit links to connect the source and destination of a flow. Since DCN topologies are usually hierarchical, our algorithm uses depth-first search to quickly traverse between hierarchical layers to find a path. When there are multiple links to a neighboring layer, the worst-fit link selection criterion enables the algorithm to make the selection decision with constant time complexity by leveraging the max-heap data structure, and use a small number of selections to find all the links of a path. Further, worst-fit also achieves load balancing, and thus generates low queueing delay, which is a major component of the end-to-end delay. We have evaluated the proposed algorithm by extensive simulations, and compared its average number of link selections and average end-to-end delay with competing solutions. The simulation results fully demonstrate the superiority of our algorithm and validate the effectiveness of our designs.

Virtual machines (VMs) may significantly improve the efficiency of data center infrastructure by sharing resources of physical servers. This benefit relies on an efficient VM placement scheme to minimize the number of required servers. Existing VM placement algorithms usually assume that VMs' demands for resources are deterministic and stable. However, for certain resources, such as network bandwidth, VMs' demands are bursty and time varying, and demonstrate stochastic nature. In this paper, we study efficient VM placement in data centers with multiple deterministic and stochastic resources. First, we formulate the Multidimensional Stochastic VM Placement (MSVP) problem, with the objective to minimize the number of required servers and at the same time satisfy a predefined resource availability guarantee. Then, we show that the problem is NP-hard, and propose a polynomial time algorithm called Max-Min Multidimensional Stochastic Bin Packing (M3SBP). The basic idea is to maximize the minimum utilization ratio of all the resources of a server, while satisfying the demands of VMs for both deterministic and stochastic resources. Next, we conduct simulations to evaluate the performance of M3SBP. The results demonstrate that M3SBP guarantees the availability requirement for stochastic resources, and M3SBP needs the smallest number of servers to provide the guarantee among the benchmark algorithms.

The rapid development in micro-computing has allowed implementations of complex mobile Wireless Sensor Networks (mWSNs). Privacy invasion is becoming an indispensable issue along with the increasing range of applications of mWSNs. Private trajectory information not only indicates the movements of mobile sensors, but also reveals personal preferences and habits of users. In this paper, we propose the distributed Basic Trajectory Privacy (BTPriv) and Secondary Trajectory Privacy (STPriv) preservation algorithms to hide trajectory of data source nodes online. We set up various simulation environments for different applications. The effectiveness of our proposed algorithms is evaluated by the software implementation in simulation experiments.

The imprecision in data streams received at the base station is common in mobile wireless sensor networks. The movement of sensors leads to dynamic spatio-temporal relationships among sensors and invalidates the data cleaning techniques designed for stationary networks. As one of the first methods designed for mobile environments, we introduce a novel online method to clean the imprecise or dirty data in mobile wireless sensor networks. Our method deploys a belief parameter to select the helpful neighboring sensors to clean data. The belief parameter is based on sensor trajectories and the consistency of their streaming data correctly received at the base station. The evaluation over multiple mobility models shows that the proposed method outperforms the existing data cleaning algorithms, especially in sparse environments where the node density in the system is low.

Buffered crossbar switches are a special type of crossbar switches with a small buffer at each crosspoint of the crossbar. Existing research results indicate that they can provide port based performance guarantees with speedup of two, but require significant hardware complexity to provide flow based performance guarantees. In this paper, we present scheduling algorithms for buffered crossbar switches to achieve flow based performance guarantees with speedup of two and one buffer per crosspoint. When there is no crosspoint blocking, only simple and distributed input scheduling and output scheduling are needed. Otherwise, a special urgent matching procedure is necessary to guarantee on-time delivery of crosspoint blocked cells. For urgent matching, we present both sequential and parallel matching algorithms. The parallel version significantly reduces the average number of iterations for convergence, which is verified by simulation. With the proposed algorithms, buffered crossbar switches can provide flow based performance guarantees by emulating push-in-first-out output-queued switches, and we use the counting method to prove the perfect emulation. Finally, we discuss an alternative backup-buffer implementation design to the bypass path, and compare our scheme with existing solutions.

A group of switch schedulers make packet scheduling decisions based on predefined bandwidth allocation for each flow. Allocating bandwidth for best effort flows is challenging due to lack of allocation criteria and fairness principles. In this paper, we propose sequential and parallel algorithms to allocate bandwidth for best effort flows in a switch, to achieve fairness and efficiency. The proposed algorithms use the queue length proportional allocation criterion, which allocates bandwidth to a best effort flow proportional to its queue length, giving more bandwidth to congested flows. In addition, the algorithms adopt the max-min fairness principle, which maximizes bandwidth utilization and maintains fairness among flows. We first formulate the problem based on the allocation criterion and fairness principle. Then, we present a sequential algorithm and prove that it achieves max-min fairness. To accelerate the allocation process, we propose a parallel version of the algorithm, which allows different input ports and output ports to conduct calculation in parallel, resulting in fast convergence. Finally, we present simulation data to demonstrate that the parallel algorithm is effective in reducing the convergence iterations.

The ever increasing demand for more bandwidth at core routers has been a challenge for switch design. To address the challenge, parallel packet switches (PPSs) combine multiple parallel switching fabrics and provide huge aggregate bandwidth. However, most existing PPSs handle only fixed length packets, also called cells, mainly because traditional switching fabrics can process only cells. Since packets in the Internet are of variable length, existing PPSs need segmentation-and-reassembly (SAR) to process such packets, which will introduce padding bits and waste precious bandwidth. In this paper, we propose a PPS to directly handle variable-length packets without SAR. First, we present a simplified 1 × 1 variable-length PPS. We design the packet distribution and collection algorithms, and show that input and output conversion buffers are bounded by 2L, where L is the maximum packet length. Next, we present a general N × N variable-length PPS, and propose the packet scheduling algorithms. We then prove our main result that such a PPS can emulate a first-in-first-out (FIFO) output queued (OQ) switch with speedup of two, i.e. emulating an FIFO OQ switch with bandwidth R by 2K-1 parallel switching fabrics each with bandwidth r, where r=R/K.

Flow level bandwidth provisioning offers fine granularity bandwidth assurance for individual flows. It is especially important for virtual network based experiment environments, to isolate traffic of different experiments or different types, which may be fed to the same switch or router port. Existing flow level bandwidth provisioning solutions suffer from a number of drawbacks, including high implementation complexity, poor performance guarantees, and inefficiency to process variable length packets. In this paper, we study flow level bandwidth provisioning for combined-input-crosspoint-queued switches in the OpenFlow context. We propose the FEBR (Flow lEvel Bandwidth pRovisioning) algorithm, which reduces the switch scheduling problem to multiple instances of fair queueing problems, each employing a well studied fair queueing algorithm. FEBR can tightly emulate the ideal Generalized Processing Sharing model, and accurately guarantee the provisioned bandwidth. Further, we implement FEBR in the OpenFlow version 1.0 software switch. In conjunction with the capability of OpenFlow to flexibly define and manipulate flows, we thus provide a practical flow level bandwidth provisioning solution. Finally, we present extensive simulation and experiment data to validate the analytical results and evaluate our design.

Application-layer overlay networks are receiving considerable popularity due to its flexibility and readily deployable nature thereby providing support for a plethora of Peer-to-Peer (P2P) applications. Currently, the real-world deployment of Internet-scale P2P media streaming systems involve the usage of tracker server for content discovery in on-demand model with asynchronous interactivity. The inherent drawbacks of tracker-server based approach are obvious due to scalability and bottleneck issues, which prompted us to pursue a structured P2P based proposition such as Distributed Hash Tables (DHT) which are already proved to be stable substrates. The challenging issue of accommodating a large number of update operations with the continuous change of user's playing position in DHT-based overlay is addressed in our previous work by the concept of Temporal-DHT which exploits the temporal dynamics of the content to estimate playing position. In this paper, we incorporate the notion of popularity awareness in the Temporal-DHT framework which will help to adapt the query resolution mechanism by addressing the skew ness of content popularity typically found in real multimedia user access patterns. The essential objective of popularity awareness mechanism is to increase the overall performance of Temporal-DHT by optimizing the search cost among the entire content set within the system. We formulate the problem and provide practical solutions with extensive simulation results that demonstrates the effectiveness of popularity-aware Temporal-DHT by achieving optimized query resolution cost and high streaming quality for on-demand systems in a dynamic network environment where user's are free to asynchronously join/leave the system.

Various distributed multi-source applications such as 3D Virtual Immersive Systems (3DVIS), 2D/3D Videoconferencing, Multi-party games, etc. require the construction of a multicast overlay through which the video blocks are streamed from source to receiver. The most general multicast model involves a single source and a set of receiver nodes also known as multicast set with a single stream to each receiver. In this paper, we are interested to investigate a different multicast model consisting of multiple sources and receivers which is quite common in 3DVIS/video conferencing applications where each node serves both as a source and a receiver. The problem of constructing a multicast overlay for multi-source is hard and we are interested to guarantee certain QoS constraints such as end-to-end latency and latency variations. Latency variation constraints are very important in collaborative applications for maintaining realtime interactivity and multi-stream synchronization. We present an efficient heuristic solution for the muti-source multicast construction problem with an economical time-complexity.

Performance guarantees provided by switches can be at different granularity: port level and flow level. As a trade-off, it is usually more expensive to provide performance guarantees at finer granularity. Existing solutions for switches to provide flow level performance guarantees require either expensive hardware support or centralized scheduling algorithms with multiple iterations. In this paper, we present the Flow-level Fair Scheduling (FFS) algorithm to provide flow level performance guarantees for Combined-Input- Crosspoint-Queued (CICQ) switches, which are special crossbar switches with a small exclusive buffer at each crosspoint of the crossbar. FFS uses hierarchical and multidimensional fair queueing to emulate the ideal Generalized Processing Sharing (GPS) model. The main features of FFS include: constant performance guarantees, bounded crosspoint buffer sizes, no speedup requirement, and distributed operation. We theoretically analyze the performance of FFS, and conduct simulations to verify the analytical results.

Buffered crossbar switches are special crossbar switches with an exclusive buffer at each crosspoint. They demonstrate unique advantages over traditional unbuffered crossbar switches, such as asynchronous scheduling and variable length packet handling. However, since crosspoint buffers are expensive on-chip memories, it is desired that each crosspoint has only a small buffer. In this paper, we propose a scheduling algorithm called Fair Asynchronous Segment Scheduling (FASS) for buffered crossbar switches, which reduces the crosspoint buffer size by dividing packets into shorter segments before transmission. FASS also provides tight constant performance guarantees by emulating the ideal Generalized Processor Sharing (GPS) model. Furthermore, FASS requires no speedup for the crossbar, lowering the hardware cost and improving the switch capacity. By theoretical analysis, we prove that FASS is strongly stable and therefore achieves 100% throughput. We also calculate the size bound for the crosspoint buffers. Moreover, we show that FASS provides bounded delay guarantees. Finally, we present simulation data to verify the analytical results.

A parallel packet switch (PPS) provides huge aggregate bandwidth by combining the capacities of multiple switching fabrics. Most existing PPSs use output queued switches as the switching fabrics, which require speedup and result in high implementation cost. In this paper, we present a buffered crossbar based parallel packet switch (BCB- PPS), whose switching fabrics need no speedup. We propose the Batch-WF2Q algorithm to dispatch packets to the parallel switching fabrics, and leverage the sMUX algorithm in to schedule packet transmission for the switching fabrics. Such a design enables a simple round-robin algorithm to efficiently collect packets from the switching fabrics. In addition, our design requires no packet resequencing, and thus needs no buffers at either external or internal outputs. We show that BCB-PPS has tight delay guarantees and bounded buffer sizes. Finally, we present simulation data to verify the analytical results and to evaluate the performance of our design.

Buffered crossbar switches are special crossbar switches with a small exclusive buffer at each crosspoint of the crossbar. They demonstrate unique advantages, such as variable length packet handling and distributed scheduling, over traditional unbuffered crossbar switches. The current main approach for buffered crossbar switches to provide performance guarantees is to emulate push-in-first-out output queued switches. However, such an approach has several drawbacks, and in particular it has difficulty in providing tight constant performance guarantees. To address the issue, we propose in this paper the guaranteed-performance asynchronous packet scheduling (GAPS) algorithm for buffered crossbar switches. GAPS intends to provide tight performance guarantees, and requires no speedup. It directly handles variable length packets without segmentation and reassembly, and makes scheduling decisions in a distributed manner. We show by theoretical analysis that GAPS achieves constant performance guarantees. We also prove that GAPS has a bounded crosspoint buffer size of 3L, where L is the maximum packet length. Finally, we present simulation data to verify the analytical results and show the effectiveness of GAPS.

Traditional crossbar switches use centralized scheduling algorithms with high time complexity. In contrast, buffered crossbar switches are capable of distributed scheduling due to crosspoint buffers, which decouple the dependency between inputs and outputs. However, crosspoint buffers are expensive on-chip memories. To reduce the hardware cost of buffered crossbar switches and make them scalable, we consider partially-buffered crossbar switches, whose crosspoint buffers can be of an arbitrarily small size and store only part of a packet instead of the entire packet. In this paper, we propose the Packet-mode Asynchronous Scheduling Algorithm (PASA) for partially buffered crossbar switches. PASA combines the features of both distributed and centralized scheduling algorithms. It works in an asynchronous mode and can directly handle variable length packets without Segmentation And Reassembly (SAR). We theoretically prove that, with a speedup of two, PASA achieves 100% throughput for any admissible traffic. We also show that outputs in PASA have a large probability to avoid the more time-consuming centralized scheduling process, and thus make fast scheduling decisions. Finally, we present simulation data to verify the analytical results and evaluate the performance of PASA.

Recent development in VLSI technology makes it feasible to integrate on-chip memories to crossbar switching fabrics. Switches using such crossbars are called buffered crossbar switches, in which each crosspoint has a small exclusive buffer. The crosspoint buffers decouple input ports and output ports, and reduce the switch scheduling problem to the fair queueing problem. In this paper, we present the fair queueing based packet scheduling scheme for buffered crossbar switches, which requires no speedup and directly handles variable length packets without segmentation and reassembly (SAR). The presented scheme makes scheduling decisions in a distributed manner, and provides performance guarantees. Given the properties of the actual fair queueing algorithm used in the scheduling scheme, we calculate the crosspoint buffer size bound to avoid overflow, and analyze the fairness and delay guarantees provided by the scheduling scheme. In addition, we use WF2Q, the fair queueing algorithm with the tightest performance guarantees, as a case study, and present simulation data to verify the analytical results.

Buffered crossbar switches are a special type of crossbar switches. In such a switch, besides normal input queues and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crosspoint buffers, output and input contention is eliminated, and the scheduling process for buffered crossbar switches is greatly simplified. Moreover, since different input ports and output ports work independently, the switch can easily schedule and transmit variable length packets. Compared with fixed length packet scheduling, variable length packet scheduling has some unique advantages: higher throughput, shorter packet latency, and lower hardware cost. In this paper, we present a fast and practical scheduling scheme for buffered crossbar switches called Localized Independent Packet Scheduling (LIPS). With LIPS, an input port or output port makes scheduling decisions solely based on the state information of its local crosspoint buffers, i.e., the crosspoint buffers where the input port sends packets to or the output port retrieves packets from. The localization feature makes LIPS suitable for a distributed implementation and thus highly scalable. Since no comparison operation is required in LIPS, scheduling arbiters can be efficiently implemented using priority encoders, which can make arbitration decisions quickly in hardware. Another advantage of LIPS is that each crosspoint needs only L (the maximum packet length) buffer space, which minimizes the hardware cost of the switches. We theoretically analyze the performance of LIPS and, in particular, prove that LIPS achieves 100 percent throughput for any admissible traffic with speedup of two. We also discuss in detail the implementation architecture of LIPS and analyze the packet transmission timing in different scenarios. Finally, simulations are conducted to verify the analytical results and measure the performance of LIPS.

Buffered crossbar switches are a special type of combined input-output queued switches with each crosspoint of the crossbar having small on-chip buffers. The introduction of crosspoint buffers greatly simplifies the scheduling process of buffered crossbar switches, and furthermore enables buffered crossbar switches with speedup of two to easily provide port based performance guarantees. However, recent research results have indicated that, in order to provide flow based performance guarantees, buffered crossbar switches have to either increase the speedup of the crossbar to three or greatly increase the total number of crosspoint buffers, both adding significant hardware complexity. In this paper, we present scheduling algorithms for buffered crossbar switches to achieve flow based performance guarantees with speedup of two and with only one or two buffers at each crosspoint. When there is no crosspoint blocking in a specific time slot, only the simple and distributed input scheduling and output scheduling are necessary. Otherwise, the special urgent matching is introduced to guarantee the on-time delivery of crosspoint blocked cells. With the proposed algorithms, buffered crossbar switches can provide flow based performance guarantees by emulating push-in-first-out output queued switches, and we use the counting method to formally prove the perfect emulation. For the special urgent matching, we present sequential and parallel matching algorithms. Both algorithms converge with N iterations in the worst case, and the latter needs less iterations in the average case. Finally, we discuss an alternative backup-buffer implementation scheme to the bypass path, and compare our algorithms with existing algorithms in the literature.

With the rapid development of broadband applications, the capability of networks to provide quality of service (QoS) has become an important issue. Fair scheduling algorithms are a common approach for switches and routers to support QoS. All fair scheduling algorithms are running based on a bandwidth allocation scheme. The scheme should be feasible in order to be applied in practice, and should be efficient to fully utilize available bandwidth and allocate bandwidth in a fair manner. However, since a single input port or output port of a switch has only the bandwidth information of its local flows (i.e., the flows traversing itself), it is difficult to obtain a globally feasible and efficient bandwidth allocation scheme. In this paper, we show how to fairly allocate bandwidth in packet switches based on the max-min fairness principle. We first formulate the problem, and give the definitions of feasibility and max-min fairness for bandwidth allocation in packet switches. As the first step to solve the problem, we consider the simpler unicast scenarios, and present the max-min fair bandwidth allocation algorithm for unicast traffic. We then extend the analysis to the more general multicast scenarios, and present the max-min fair bandwidth allocation algorithm for multicast traffic. We prove that both algorithms achieve max-min fairness, and analyze their complexity. The proposed algorithms are universally applicable to any type of switches and scheduling algorithms.

Buffered crossbar switches are a special type of crossbar switches. In such a switch, besides normal input queues and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crosspoint buffers, output and input contention is eliminated, and the scheduling process for buffered crossbar switches is greatly simplified. Moreover, crosspoint buffers enable the switch to work in an asynchronous mode and easily schedule and transmit variable length packets. Compared with fixed length packet scheduling or cell scheduling, variable length packet scheduling, or packet scheduling for short, has some unique advantages: higher throughput, shorter packet latency and lower hardware cost. In this paper, we present a fast and practical scheduling scheme for buffered crossbar switches called Localized Asynchronous Packet Scheduling (LAPS). With LAPS, an input port or output port makes scheduling decisions solely based on the state information of its local crosspoint buffers, i.e., the crosspoint buffers where the input port sends packets to or the output port retrieves packets from. The localization property makes LAPS suitable for a distributed implementation and thus highly scalable. Since no comparison operation is required in LAPS, scheduling arbiters can be efficiently implemented using priority encoders, which can make arbitration decisions quickly in hardware. Another advantage of LAPS is that each crosspoint needs only L (the maximum packet length) buffer space, which minimizes the hardware cost of the switches. We also theoretically analyze the performance of LAPS, and in particular we prove that LAPS achieves 100% throughput for any admissible traffic with speedup of two. Finally, simulations are conducted to verify the analytical results and measure the performance of LAPS.

Multicast enables efficient data transmission from one source to multiple destinations, and has been playing an important role in Internet multimedia applications. Although several multicast scheduling schemes for packet switches have been proposed, they usually consider only short delay and high throughput but not bandwidth guarantees. However, fair bandwidth allocation is critical for the quality of service (QoS) of the network, and is necessary to support multicast applications requiring guaranteed performance services, such as online audio and video streaming. This paper addresses the issue of bandwidth guaranteed multicast scheduling on virtual output queued (VOQ) switches. We propose the credit based multicast fair scheduling (CMF) algorithm, which aims at achieving not only short multicast latency but also fair bandwidth allocation. CMF uses a credit/balance based strategy to guarantee the reserved bandwidth of an input port on each output port of the switch. It keeps track of the difference between the reserved bandwidth and actually received bandwidth, and minimizes the difference to ensure fairness. Moreover, CMF supports multicast scheduling by allowing a multicast packet to send transmission requests to multiple output ports simultaneously. As a result, a multicast packet has more chances to be delivered to all its destinations in the same time slot, and thus shortens its multicast latency. Extensive simulations are conducted to compare the performance of CMF with other existing scheduling algorithms, and the results demonstrate that CMF achieves the two design goals: short multicast latency and fair bandwidth allocation.

Many networking/computing applications require high speed switching for multicast traffic at the switch/router level to save network bandwidth. However, existing queuing-based packet switches and scheduling algorithms cannot perform well under multicast traffic. While the speedup requirement makes the output queued switch difficult to scale, the single input queued switch suffers from head of line (HOL) blocking, which severely limits the network throughput. An efficient yet simple buffering strategy to remove the HOL blocking is to use the virtual output queued (VOQ) switch structure, which has been shown to perform well under unicast traffic. However, the traditional VOQ switch is impractical for multicast traffic because a VOQ switch for multicast traffic has to maintain an exponential number of queues in each input port (i.e., 2/sup N/-1 queues for a switch with N output ports). In this paper, we give a novel queue structure for the input buffers of a multicast VOQ switch by separately storing the address information and data information of a packet so that an input port only needs to manage a linear number (N) of queues. In conjunction with the multicast VOQ switch, we present a first-in-first-out based multicast scheduling algorithm, FIFO multicast scheduling (FIFOMS), and conduct extensive simulations to compare FIFOMS with other popular scheduling algorithms. Our results fully demonstrate the superiority of FIFOMS in both multicast latency and queue space requirement.