NA6

CIS679: Absolute DiffServ: 

CIS679: Absolute DiffServ Review of Last Lecture Absolute DiffServ

Review of last lecture: 

Review of last lecture 2-bit DiffServ Simple However no hard guarantees

Absolute Diff-Serv: 

Absolute Diff-Serv DPS approach Rate-based scheduler More state information from core router to the packet header Utilization-based admission control approach Static priority driven scheduler Pre-configure the resource based pre-computing the end-to-end delay

Comparison of two approaches: 

Comparison of two approaches Rate-based Priority-based Not Scalable Data Plane Not Scalable Scalable Scalable Control Plane Upon a new request, the delay of all existing flows need re-computing Core-router need keep per-flow information

Utilization-based admission control approach: 

Utilization-based admission control approach Packet forwarding control Admission control Utilization bound verification

Slide6: 

Packet Forwarding Control Static Priority scheduler is adopted Class-based scheduler well-supported Mechanism of Static Priority Scheduler In a router, packets are transmitted according to their priorities; within the same priority, packets are served in FIFO order.

Slide7: 

Utilization-based Admission Control (UBAC) Key Idea Employ a utilization (bandwidth) bound: If the utilization values of links < the bound value, the end-to-end deadline requirement can be met. How does it Work? The admission control admits a new flow if the utilization values of links are no more than the bound.

Slide8: 

Utilization Bound Verification Objective: Verify whether the end-to-end delay bound in each feasible path satisfies the deadline requirement given the pre-define utilization bound. Key Idea: Compute the end-to-end delay on each feasible path under the given bound at configuration time.

Slide9: 

Utilization bound verification The Workflow Verification of Safe Utilization Delay Computation for Path Delay d α is safe α is not safe Yes No d<D Network parameters, traffic pattern (α: the utilization bound, D = Deadline) At Configuration Time Packet Forwarding with Static Priority Scheduler Utilization-based Admission Control

Slide10: 

Challenges Delay analysis at configuration time Delay computation needs dynamic flow information, which is not available at configuration time.

Flow-Population-Insensitive Delay Computation: 

Flow-Population-Insensitive Delay Computation The General Delay Formula Derivation of the New Delay Formula Extension Experimental Evaluation

Slide12: 

The General Delay Formula According to Cruz [1991], the worst case delay at link server k can be computed as: Specifically, Observation: the delay depends on dynamic flow information: the individual arrival constraint traffic function, i.e. Hk,j, m(I). the number of arriving flows, i.e. nk,j etc.

Slide13: 

Backup: Traffic Model H_in(I) = σ + r*I Leaky Bucket Any traffic H (I) = min{C*I, σ+ρ*I} I Size of token bucket C r H (I) σ

Slide14: 

Backup: Service Curve and Arrival Curve I dk, C

Slide15: 

Derivation of the New Delay Formula Basic Idea: Remove the dependence of the general delay formula on the dynamic flow information: individual traffic constraint functions use the constraint function of the flow with the maximum of the worst case queuing delay to replace other individual flows’ function. the number of flows an intuitive idea: when the flows distribute evenly among the input links, the delay of the server will be maximized.

Slide16: 

The New Delay Formula 2 Priorities, Links with the same capacity, 2 classes traffic, …... Observation: it does not depend on dynamic status information!

Slide17: 

What is Yk? db dk dc dd da df de If da+db > dc+dd, then Yk = da+db Yk: the maximum of the worst case queuing delay suffered by any flow in real-time class before arriving at Server k

Slide18: 

Remaining Issues in the New Delay Formula Path dependent, Yk Multiple priority,and multiple classes, links with different capacities, etc.

Slide19: 

Extension: Path Independent Assume d* is the maximum worst case delay of any link server in network D, h is the diameter of G: The formula does not depend on Yk The resulting delay will be larger than the former one. The formula still depends on h Observation:

Slide20: 

Extension: the General Case Multiple Priorities, multiple classes traffic Links with different capacity, etc.

Slide21: 

Performance Metrics: The Maximum Utilization Bound using delay formula F1 and F2 under different burst situation Evaluated Systems: two-priority scheduler Network: MCI WorldCom Backbone with 100Mbps link capacity Real-time Traffic: Voice over IP traffic <640bit, 32,000bps, 0.1s> Results: Experimental Evaluation

Conclusion: 

Conclusion UBAC approach Flow-population-insensitive delay analysis Formula 1 depends on routes Formula 2 depends on the diameter of networks What we paid? Delay over-estimation: Utilization < 1.0