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
Loading...
Thumbnail Image
Name

IC_TECH_REPORT_199927.pdf

Access type

openaccess

Size

307.06 KB

Format

Adobe PDF

Checksum (MD5)

63c995bd61960a602c6612ffb134650a

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