Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. A Min-Plus System Theory for Constrained Traffic Regulation and Dynamic Service Guarantees
 
report

A Min-Plus System Theory for Constrained Traffic Regulation and Dynamic Service Guarantees

Chang, Cheng-Shang
•
Cruz, Rene L.
•
Le Boudec, Jean-Yves  
Show more
1999

By extending the system theory under the (min,+)-algebra to the time varying setting, we solve the problem of constrained traffic regulation and develop a calculus for dynamic service guarantees. For a constrained traffic regulation problem with maximum tolerable delay d and maximum buffer size q, the optimal regulator that generates the output traffic conforming to a subadditive envelope f and minimizes the number of discarded packets is a concatenation of the g-clipper with g(t) = min[f(t+d), f(t)+q] and the maximal f-regulator. The g-clipper is a bufferless device which optimally drops packets as necessary in order that its output be conformant to an envelope g. The maximal f-regulator is a {\em buffered} device that delays packets as necessary in order that its output be conformant to an envelope f. The maximal f-regulator is a linear time invariant filter with impulse response f, under the (min +)-algebra. To provide dynamic service guarantees in a network, we develop the concept of a dynamic server as a basic network element. Dynamic servers can be joined by concatenation, filter bank summation,'' and feedback to form a composite dynamic server. We also show that dynamic service guarantees for multiple input streams sharing a work conserving link can be achieved by a dynamic SCED (Service Curve Earliest Deadline) scheduling algorithm, if an appropriate admission control is enforced. To model more general network elements, such as routers and packetizers, we extend the time varying system theory to a general system theory, where the mapping from the input to the output is required to be sigma-additive under the (min,+)-algebra. Analogous to dynamic servers, network elements with the sigma-additive property can also be joined by concatenation, filter bank summation,'' and feedback to form a composite network element.

  • Files
  • Details
  • Metrics
Type
report
Author(s)
Chang, Cheng-Shang
Cruz, Rene L.
Le Boudec, Jean-Yves  
Thiran, Patrick  
Date Issued

1999

Subjects

Network Calculus

Written at

EPFL

EPFL units
INDY2  
LCA2  
LCA  
Available on Infoscience
July 13, 2005
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/214410
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés