Virtual Network Partitioning

Guaranteed quality-of-service (QoS) has been the focus of recent literature in high-speed networking.  The worst-case design approach to network provisioning has been utilized in the literature as a means to restrain the network operation into a region which is bounded by a set of circumscribed behaviors. Specifically, a worst-case network designer models a source by a function moving over a bounded region usually selected so as to reflect the least favorable behavior of the source. The main results, reported in the literature, quantify the worst-case network performance by investigating the maximum delay and/or the maximum backlog, the scheduling strategy in the nodes, and the parameters of prescribed regulators --- usually located at the network boundaries for shaping and/or filtering the injected traffic into the network.

Recent research of Internet engineering Task Force (IETF) on QoS provisioning spans two disciplines: Integrated Services (IntServ) and Differentiated Services (DiffServ). IntServ along with a resource reservation protocol (RSVP) constitute a framework for service guarantees inside a network. IntServ uses RSVP to reserve an appropriate amount of network resources for each input traffic. Per-flow resource allocation is a tedious task in core networks where the number of flows is large and therefore IntServ does not scale well to such networks.  DiffServ solves this problem by aggregating several smaller flows into larger flow. The aggregated flow is then assigned to a certain behaviour aggregate (BA) of DiffServ standard. Research on DiffServ proceeds in two different directions: absolute service differentiation and relative service differentiation. In absolute service differentiation, network resources are provisioned to guarantee a certain level of performance for each behaviour aggregate --- the guarantee of per-flow performance is not, however, prescribed. In relative service differentiation, network resources are distributed on the DiffServ classes so as to satisfy a relative QoS ordering.

Our research in virtual network partitioning in WIRLab focuses on assuring a guaranteed QoS for input traffics. The network is provisioned to guarantee  maximum delay and  maximum backlog for projected traffics. We use these parameters to specify the requested QoS and to measure the performance in the presence of greedy sources.  As a means to classify the injected traffic into several behaviour aggregates, a virtual network partitioning has been proposed. We emphasize a ``virtual'' partitioning since the classified traffics are not totally segregated into isolated subnetworks. We have proposed a nested network partitioning in which the aggregates of input traffics are treated in a hierarchical manner; unused resources in a higher class can be utilized by a lower hierarchy. This approach is useful for the DiffServ standard.  

This research uses the min-plus algebra. Min-plus algebra  has been used in the recent literature to instrument a network calculus. In min-plus algebra, the addition operator of the regular algebra is replaced by minimization and the multiplication is replaced by addition. The min-plus algebra provides a systematic approach to traffic regulation and service curve formulation by devising a complying filtering theory. The filtering theory in min-plus algebra imitates its counterpart in the classical signal processing and creates a structured framework for network calculus.

Further Reading:

[1] S. Valaee, “A Methodology for Virtual Network Provisioning: The Deterministic Approach”, preprint. [pdf]