Slide 1

Definition - 100% Throughput

A Characteristic Switch

Maximum Size Matching

Contents

An Example
MSM does not give 100% throughput

Motivation

Questions

Contents

Non Pre-emptive Scheduling … 1
Batch Scheduling

Non Pre-emptive Scheduling … 2
Batch Scheduling

Non Pre-emptive Scheduling … 2
Batch Scheduling

Degree of a Batch

Slide 14

Critical Maximum Size Matching
A sub-class of MSM

Previous Results

Arrival Traffic

Contents

CMSM with Uniform Traffic

Formal Arguments
Outline

Formal Arguments … 1
Bounding the degree of a batch

Formal Arguments … 2
Bounding the deviation of the service time of a batch

Formal Arguments … 3
Bounding the service time of a batch

Formal Arguments …4
Tightening the bound

Formal Arguments …5
Finishing Off..

Formal Arguments …6
Some Final Points..

Contents

CMSM with Non-Uniform Traffic

Contents

Example of a Uniform Graph

MSM with Non-Uniform Traffic

Contents

Conclusions