Architecture for dynamic and fair distribution of bandwidth

The problem of fair distribution of available bandwidth among traffic flows or aggregates remains an essential issue in computer networks. This paper introduces a novel approach, called the E x act B andwidth D istribution S cheme (X‐BDS), for dynamic and fair distribution of available bandwidth among individual flows. In this approach, the edge routers keep per‐flow information, while the core routers maintain the aggregate flow requirements. The X‐BDS approach employs a distributed message exchange protocol for providing network feedback and for distributing aggregate flow requirements among the nodes in the network. Based on the obtained feedback, the edge routers employ the X‐BDS resource management unit to dynamically distribute available bandwidth among individual flows. The X‐BDS admission control and resource management units are responsible for fair resource allocation that supports minimum bandwidth guarantees of individual flows. This paper evaluates the Bandwidth Distribution Scheme through simulation and shows that the X‐BDS is capable of supporting per‐flow bandwidth guarantees in a dynamically changing network environment. Copyright © 2006 John Wiley & Sons, Ltd.     

Monitoring and controlling QoS network domains

Increased performance, fairness, and security remain important goals for service providers. In this work, we design an integrated distributed monitoring, traffic conditioning, and flow control system for higher performance and security of network domains. Edge routers monitor (using tomography techniques) a network domain to detect quality of service (QoS) violations—possibly caused by underprovisioning—as well as bandwidth theft attacks. To bound the monitoring overhead, a router only verifies service level agreement (SLA) parameters such as delay, loss, and throughput when anomalies are detected. The marking component of the edge router uses TCP flow characteristics to protect ‘fragile’ flows. Edge routers may also regulate unresponsive flows, and may propagate congestion information to upstream domains. Simulation results indicate that this design increases application‐level throughput of data applications such as large FTP transfers; achieves low packet delays and response times for Telnet and WWW traffic; and detects bandwidth theft attacks and service violations. Copyright © 2004 John Wiley & Sons, Ltd.     

Approximate fair bandwidth sharing in high-speed multimedia networks

Existing fair-queuing algorithms use complicated flow management mechanisms, thus making them expensive to deploy in current high-bandwidth networks. In this paper we propose a scalable SCORE (stateless core) approach to provide fair bandwidth sharing for a traffic environment composed of TCP and UDP flows. At an edge router, the arrival rates of each flow are estimated, each packet then being labelled with this estimate. The outgoing link’s fair share at a router is estimated based on UDP traffic. Probabilistic dropping is used to regulate those flows that send more than the fair share. At a core router, all the functions performed by an edge router are repeated, excluding the flow rate estimation. The simulation results show that the degree of fairness achieved by the proposed solution is comparable to that of other algorithms, but with a lower implementation cost.     

Core-stateless fair queueing: a scalable architecture to approximate fair bandwidth allocations in high-speed networks

Router mechanisms designed to achieve fair bandwidth allocations, such as fair queueing, have many desirable properties for congestion control in the Internet. However, such mechanisms usually need to maintain state, manage buffers, and/or perform packet scheduling on a per-flow basis, and this complexity may prevent them from being cost-effectively implemented and widely deployed. We propose an architecture that significantly reduces this implementation complexity yet still achieves approximately fair bandwidth allocations. We apply this approach to an island of routers - that is, a contiguous region of the network - and we distinguish between edge routers and core routers. Edge routers maintain per-flow state; they estimate the incoming rate of each flow and insert a label into each packet based on this estimate. Core routers maintain no per-flow state; they use first-in-first-out packet scheduling augmented by a probabilistic dropping algorithm that uses the packet labels and an estimate of the aggregate traffic at the router. We call the scheme core-stateless fair queueing. We present simulations and analysis on the performance of this approach.     

Implicit admission control

Internet protocols currently use packet-level mechanisms to detect and react to congestion. Although these controls are essential to ensure fair sharing of the available resource between multiple flows, in some cases they are insufficient to ensure overall network stability. We believe that it is also necessary to take account of higher level concepts, such as connections, flows, and sessions when controlling network congestion. This becomes of increasing importance as more real-time traffic is carried on the Internet, since this traffic is less elastic in nature than traditional Web traffic. We argue that, in order to achieve better utility of the network as a whole, higher level congestion controls are required. By way of example, we present a simple connection admission control (CAC) scheme which can significantly improve the overall performance. This paper discusses our motivation for the use of admission control in the Internet, focusing specifically on control for TCP flows. The technique is not TCP specific, and can be applied to any type of flow in a modern IP infrastructure. Simulation results are used to show that it can drastically improve the performance of TCP over bottleneck links. We go on to describe an implementation of our algorithm for a router running the Linux 2.2.9 operating system. We show that by giving routers at bottlenecks the ability to intelligently deny admission to TCP connections, the goodput of existing connections can be significantly increased. Furthermore, the fairness of the resource allocation achieved by TCP is improved     

基于区分服务的边缘路由器的服务质量

Internet real-time multimedia communication brings a further challenge to Quality of Service （QoS）. A higher QoS in communication is required increasingly. As a new framework for providing QoS services, Differentiated Services （DiffServ） is undergoing a speedily standardization process at the IETF. DiffServ not only can offer classified level of services, but also can provide guaranteed QoS in a certain extent. In order to provide QoS, DiffServ must be properly configured. The traditional DiffServ mechanism provides classifier for edge router to mark the different traffic streams, and then the core router uses different Drop Packet Mechanisms to drop packets or transmit data packets according to these classified markers. When multiple edge routers or other core routers transmit data packets high speedily to a single core router, the core router will emerge bottleneck bandwidth. The most valid solution to this problem is that the edge router adopts drop packet mechanism. This paper proposes an Modified Edge Router Mechanism that let the edge router achieve marking, dropping and transmitting packets of hybrid traffic streams based on DiffServ in a given bandwidth, the core router will only transmits packets but won＇t drop packets. By the simulation of ns2, the modified mechanism ensure the QoS of high priority traffics and simplify the core router, it is a valid method to solve the congestion of the core router.     

BiLink: A high performance NoC router architecture using bi-directional link with double data rate

This paper presents a novel high performance Network-on-Chip (NoC) router architecture design using a bi-directional link with double data rate (BiLink). Ideally, it can provide as high as 2 times speed-up compared with the conventional NoC router. BiLink utilizes an extra link stage between routers and transmits two flits in one link per cycle using phase pipelining if both routers require to use the current link. To further increase the effective bandwidth, the direction of each link can be configured in every clock cycle to cater for different traffic loads from each side. Therefore, the data rate can be as high as 4 times compared with conventional NoC routers under uneven traffic. Centralized mode control scheme is implemented using a finite state machine (FSM) approach. Cycle-accurate simulations are carried out on both synthetic traffic patterns as well as real application benchmarks. Simulation results show that BiLink can provide as high as 90% and 250% speedup compared with conventional NoC routers for even and uneven traffic, respectively. 2X and 3X gains in throughput are obtained under even and uneven traffic, respectively, when compared with the conventional NoC router for the virtual channel flow control. The BiLink router architecture is synthesized using TSMC 65 nm process technology and it is shown that an area overhead of 28% over state-of-the-art bi-directional NoC is introduced while the critical path is about 9% higher than that of the conventional routers. Despite the overhead in critical path and power consumption, a 47.45% improvement of Energy-Delay-Product (EDP) is achieved by BiLink under high injection rate traffic.     

Core‐stateless fair rate estimation fair queuing

Core‐stateless mechanisms, such as core‐stateless fair queuing (CSFQ), reduce the complexity of fair queuing, which usually need to maintain states, manage buffers, and perform flow scheduling on a per‐flow basis. However, they require executing label rewriting and dropping decision on a per‐packet basis, thus preventing them from being widely deployed. In this paper, we propose a novel architecture based on CSFQ without per‐packet labelling. Similarly, we distinguish between edge routers and core routers. Edge routers maintain the per‐flow state by employing a fair queuing mechanism to allocate each flow a fair bandwidth share locally and a token bucket mechanism to regulate those flows with feedback packets sent from egress edge routers. Core routers do not maintain per‐flow state; they use FIFO packet scheduling extended by a fare rate alarm mechanism by estimating the arrival rate and the number of flows using a matching–mismatching algorithm. The novel scheme is called core‐stateless fair rate estimation fair queuing (CSFREFQ). CSFREFQ is proven to be capable of achieving max–min fairness. Furthermore, we present and discuss simulations and experiments on the performance under different traffic scenarios. Copyright © 2005 John Wiley & Sons, Ltd.     

Providing absolute differentiated services for real-time applications in static-priority scheduling networks

In this paper, we propose and analyze a methodology for providing absolute differentiated services for real-time applications. We develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and, hence, is scalable to large systems. We assume the underlying network to use static-priority schedulers. We design and analyze several priority assignment algorithms and investigate their ability to achieve higher utilization bounds. Traditionally, schedulers in differentiated services networks assign priorities on a class-by-class basis, with the same priority for each class on each router. In this paper, we show that relaxing this requirement, that is, allowing different routers to assign different priorities to classes, achieves significantly higher utilization bounds.     

New Architecture and Algorithms for Fast Construction of Hose-Model VPNs

Hose-model virtual private networks (VPNs) provide customers with more flexibility in specifying bandwidth requirements than pipe-model VPNs. Many hose-model VPN provisioning algorithms have been proposed, and they focus on the bandwidth efficiency in the construction of a single hose-model VPN. In practice, however, VPNs come and go and the dynamics will affect the performance of these VPN provisioning algorithms. If the frequency of adding and deleting VPNs is high, these algorithms will have a scalability problem. We propose in this paper a new network architecture for dynamic VPN construction. In the proposed architecture, adding a new VPN is much simpler and faster, and all that is required is to check if the edge routers have enough bandwidth. There is no need to check the bandwidth left on each internal link because the architecture guarantees that as long as the edge routers have enough capacities to accept the VPN, the internal links will never experience overflow caused by adding the new VPN. We present a linear programming formulation for finding the optimal routing that maximizes the amount of admissible VPN traffic in the network. We then exploit the underlying network flow structure and convert the linear programming problem into a subgradient iterative search problem. The resulting solution is significantly faster than the linear programming approach.     

Deficit round-robin scheduling for input-queued switches

We address the problem of fair scheduling of packets in Internet routers with input-queued switches. The goal is to ensure that packets of different flows leave a router in proportion to their reservations under heavy traffic. First, we examine the problem when fair queuing is applied only at output link of a router, and verify that this approach is ineffective. Second, we propose a flow-based iterative deficit-round-robin (iDRR) fair scheduling algorithm for the crossbar switch that supports fair bandwidth distribution among flows, and achieves asymptotically 100% throughput under uniform traffic. Since the flow-based algorithm is hard to implement in hardware, we finally propose a port-based version of iDRR (called iPDRR) and describe its hardware implementation.     

An active queue management scheme based on a capture-recapture model

One of the challenges in the design of switches/routers is the efficient and fair use of the shared bottleneck bandwidth among different Internet flows. In particular, various active queue management (AQM) schemes have been developed to regulate transmission control protocol traffic in response to router congestion. In addition, in order to provide fair bandwidth sharing, these AQM must protect the well-behaved flows from the misbehaving flows. However, most of the existing AQM schemes cannot provide accurate fair bandwidth sharing while being scalable. The key to the scalability and fairness of the AQM schemes is the accurate estimation of certain network resources without keeping too much state information. We propose a novel technique to estimate two network resource parameters: the number of flows in the buffer and the data source rate of a flow by using a capture-recapture (CR) model. The CR model depends on simply the random capturing/recapturing of the incoming packets, and as a result, it provides a good approximation tool with low time/space complexity. These network resource parameters are then used to provide fair bandwidth sharing among the Internet flows. Our experiments and analysis will demonstrate that this new technique outperforms the existing mechanisms and closely approximates the "ideal" case, where full state information is needed.     

Adaptive provisioning of differentiated services networks based on reinforcement learning

The issue of bandwidth provisioning for Per Hop Behavior (PHB) aggregates in Differentiated Services (DiffServ) networks has received a lot of attention from researchers. However, most proposed methods need to determine the amount of bandwidth to provision at the time of connection admission. This assumes that traffic in admitted flows always conforms to predefined specifications, which would need some form of traffic shaping or admission control before reaching the ingress of the domain. This paper proposes an adaptive provisioning mechanism based on reinforcement-learning principles, which determines at regular intervals the amount of bandwidth to provision to each PHB aggregate. The mechanism adjusts to maximize the amount of revenue earned from a usage-based pricing model. The novel use of a continuous-space, gradient-based learning algorithm, enables the mechanism to require neither accurate traffic specifications nor rigid admission control. Using ns-2 simulations, we demonstrate using Weighted Fair Queuing, how our mechanism can be implemented in a DiffServ network.     

A guaranteed minimum throughput service for TCP flows using measurement‐based admission control

We propose a new scheme for a network service that guarantees a minimum throughput to flows accepted by admission control (AC). The whole scheme only uses a small set of packet classes in a core‐stateless network. At the ingress of the network each flow packet is marked into one of the sets of classes, and within the network, each class is assigned a different discarding priority. The AC method is based on edge‐to‐edge per‐flow throughput measurements using the first packets of the flow, and it requires flows to send with a minimum rate. We evaluate the scheme through simulations in a simple bottleneck topology with different traffic loads consisting of TCP flows that carry files of varying sizes. We use a modified TCP source with a new algorithm that forces the source to send with a minimum rate. We compare our scheme with the best‐effort service and we study the influence of the measurement duration on the scheme's performance. The results prove that the scheme guarantees the requested throughput to accepted flows and achieves a high utilization of network resources. Copyright © 2006 John Wiley & Sons, Ltd.     

Comparative study of two CPU router time management algorithms in cellular IP networks

Providing good quality of service (QoS) in cellular IP networks is an important requirement for performance improvement of the cellular IP network. Resource reservation is one of the methods used in achieving this goal and is proven to be effective. The main resources to be reserved in a cellular IP network are bandwidth, buffer and central processing unit (CPU) cycles. Router CPU cycle is the time taken by the router to process the packet of the flow before forwarding it to the next router (hop). This paper proposes a model for CPU cycle optimization of routers for real‐time flows in a cellular IP network. The model applies both genetic algorithm (GA) and particle swarm optimization (PSO) as soft computing tools to optimize the CPU cycles and reduces the flow processing time at each router in the route taken by a flow. Simulation experiments illustrate a comparative study of the model.     

Multistage Switching Architectures for Software Routers

Software routers based on personal computer (PC) architectures are becoming an important alternative to proprietary and expensive network devices. However, software routers suffer from many limitations of the PC architecture, including, among others, limited bus and central processing unit (CPU) bandwidth, high memory access latency, limited scalability in terms of number of network interface cards, and lack of resilience mechanisms. Multistage PC-based architectures can be an interesting alternative since they permit us to i) increase the performance of single- software routers, ii) scale router size, iii) distribute packet-manipulation and control functionality, iv) recover from single-component failures, and v) incrementally upgrade router performance. We propose a specific multistage architecture, exploiting PC-based routers as switching elements, to build a high-speed, large-size, scalable, and reliable software router. A small-scale prototype of the multistage router is currently up and running in our labs, and performance evaluation is under way.     

On wavelength-converted optical routers employing flow routing

Optical networks have been extensively investigated in recent years to provide high capacity for the Internet traffic. Among them the optical packet-switching network deploying buffering, wavelength conversion and multipath routing could be the most suitable one. It cannot only provide high capacity transport for Internet traffic but also achieve high utilization of the network resources. However due to the packet-oriented routing and switching, such a network can result in a large amount of packets out-of-order, packet loss and/or with various delays upon arriving at end systems, causing TCP flows that comprise those packets corrupted. Large amount of corrupted flows can increase the burstiness of the Internet traffic and cause higher-layer protocol to malfunction. This paper presents a novel routing and switching method for optical IP networks-flow routing. Without using a complicate control mechanism flow routing deals with packet-flows to reduce the amount of corrupted flows. The performance of the wavelength-converted optical flow router is investigated, based on a novel analytical model. A performance metric, i.e., good-throughput, is used, measuring the ratio of the amount of packets comprised in the noncorrupted flows to total amount of packets. Comparing with optical packet-switching routers, a remarkable improvement of good-throughput can be obtained by using optical flow routers. More important, using wavelength conversion can greatly improve the good-throughput of optical flow routers.     

The structure and management of service level agreements innetworks

The paper proposes a structure for quality-of-service (QoS)-centered service level agreements (SLA), and a framework for their real-time management in multiservice packet networks. The SLA is structured to be fair to both parties, the service provider and their customer. The SLA considered here are for QoS assured delivery of aggregate bandwidth from ingress to egress nodes; however, the control and signaling is for the more granular flows or calls. A SLA monitoring scheme is presented in which revenue is generated by the admission of flows into the network, and penalty incurred when flows are lost in periods when the service provider is not SLA compliant. In the SLA management scheme proposed, the results of a prior off-line design are used, in conjunction with measurements taken locally at ingress nodes, to classify the loading status of routes. The routing and resource management are based on virtual partitioning and its supporting mechanism of bandwidth protection. The effectiveness of SLA management is measured by the robustness in performance in the presence of substantial diversity in actual traffic conditions. A simulation testbed called D'ARTAGNAN has been built from which we report numerical results for a case study. The results show that the SLA management scheme is robust, fair and efficient over a broad range of traffic conditions     

Entropy Based Adaptive Flow Aggregation

Internet traffic flow measurement is vitally important for network management, accounting and performance studies. Cisco's NetFlow is a widely deployed flow measurement solution that uses a configurable static sampling rate to control processor and memory usage on the router and the amount of reporting flow records generated. But during flooding attacks the memory and network bandwidth consumed by flow records can increase beyond what is available. Currently available countermeasures have their own problems: 1) reject new flows when the cache is full - some legitimate new flows will not be counted; 2) export not-terminated flows to make room for new ones - this will exhaust the export bandwidth; and 3) adapt the sampling rate to traffic rate - this will reduce the overall accuracy of accounting, including legitimate flows. In this paper, we propose an entropy based adaptive flow aggregation algorithm. Relying on information-theoretic techniques, the algorithm efficiently identifies the clusters of attack flows in real time and aggregates those large number of short attack flows into a few metaflows. Compared to currently available solutions, our solution not only alleviates the problem in memory and export bandwidth, but also significantly improves the accuracy of legitimate flows. Finally, we evaluate our system using both synthetic trace file and real trace files from the Internet.