# Presentation: 424070

## Bandwidth Scheduling and Provisioning in Access and Wide Area Networks

*Bin Wang*
*Department of Computer Science and Engineering*
*Wright State University*
*Dayton, OH 45435*

- 11/15/2004

## Outline

- Bandwidth scheduling in Ethernet Passive Optical Network (EPON)
- Sliding scheduled traffic model
- Bandwidth scheduling over a point-to-point WDM link
- Bandwidth provisioning in WDM networks
- Look-ahead scheduling of a set of demands
- Dynamic scheduling of a demand
- Summary

- 11/15/2004

**Notes:**
Bandwidth scheduling in Ethernet passive optical networks (EPON)
A new flexible traffic model
Under this model, we examine the bandwidth scheduling problem over a point-to-point WDM link (which can be an access link, for example)
We then present look-ahead scheduling of a set of demands and scheduling of a dynamically arrived demand.

## Access Network - Passive Optical Networks

- A single fiber is used to support multiple customers – 20km
- No active equipment in the path  highly reliable
- Optical line terminal (OLT) in central office, which connected to the rest of the Internet
- Optical network unit (ONU) on customer premises
- Both upstream and downstream traffic on ONE fiber (1490nm down, 1310nm up)
- EPON: Ethernet based PON draft designed by IEEE 802.3ah
- 1000 Mbps downstream and 1000 Mbps upstream

**Rest of Internet**

- 11/15/2004

**Notes:**
Briefly introduce passive optical networks and Ethernet PON
OLT and ONUs are connected through optical splitter and combiner

## PON Topologies

- 11/15/2004

**Notes:**
Different PON topologies are possible;
We’ll focus on tree topology in which ONUs cannot communicate with each other directly due to the directional property of optical combiner.
Other topologies may require more fibers, devices, and redeploy fibers

Trunk can be protected using redundant link

## Why PON?

- Reduced OpEx: passive network
- High reliability
- Reduced power expenses
- Shorter installation times
- Reduced CapEx:
- 16-128 customers per fiber
- 1 Fiber + *N* transceivers
- Scalable
- CO equipment shared  new customers can be added easily as the network grows
- Bandwidth is shared  existing customer bandwidth can be changed on demand

- 11/15/2004

**Notes:**
The advantages of PON are many:
Operation expenditure
Capital expenditure

## Downstream Traffic - Broadcast

- 11/15/2004

**Notes:**
Downstream traffic is broadcast to all ONUs; individual ONU received frames according to their mac address

## Upstream Traffic -Shared

- 11/15/2004

**Notes:**
Upstream bandwidth is shared; No communications between ONUs; collisions are possible
 therefore, proper bandwidth scheduling algorithm is needed
In addition, round trip times between OLT and different ONUs are different;
Guard time is needed between a burst of frames from one ONUs and another ONU

## Bandwidth Scheduling - Upstream

- TDMA – a frame consists of *N* time slots
*N* ONUs
- Each ONU is assigned a dedicated time slot
- Traffic arriving to ONU is buffered till correct time slot for this ONU arrives
- Traffic will be sent at full link speed upstream

- 11/15/2004

**Notes:**
Simple TMDA scheme
Ethernet frames need to be buffered at individual ONU

## Pros and Cons

- Pros
- simple
- Dedicated bandwidth
- Cons
- Fixed frame (*N* time slots)
- Potential long delay
- No statistical sharing – low utilization
- Loss due to buffer overflow; using a larger buffer increases delay

- 11/15/2004

**Notes:**
Pros and Cons of simple TDMA scheme

## Dynamic Polling-based Bandwidth Scheduling

- Use OLT polling ONUs to deliver data encapsulated in Ethernet frames from ONUs to OLT
- To avoid walk times associated with polling (due to large RTT), polling requests and data transmission need to be properly scheduled
- Interleaved polling with adaptive transmission cycle time

- 11/15/2004

**Notes:**
Why a polling scheme makes sense?
CSMA does not work since ONUs do not talk to each directly; OLT can determine collision but RTT is large compared with transmission time.
Using CSMA results in low performance
The drawback of a polling scheme is the walk time (overhead); need to hide the overhead
The scheme we look at next combines interleaved polling with adaptive transmission cycle time (variable transmission cycle depending on traffic conditions in the network)

## Dynamic Polling-based Bandwidth Scheduling

- OLT maintains polling table
- # of bytes in ONU’s buffer
- requested transmission window
- RTT to each ONU
- OLT issue *Grant* message to ONU
- Granted transmission window
- ONU transmits *up to* the granted transmission window
- At the end of transmission, ONU issues a Request to OLT
- # of bytes in ONU’s buffer

**grant**

**request**

- 11/15/2004

**Notes:**
The OLT maintains a polling table, one entry of the table is for one ONU; 
# of bytes is the requested transmission window from an ONU in a previous polling 
RTT is the round trip time between OLT and the ONU under consideration

This scheme can be implemented using Gate and Report messages in multi-point control protocol (MPCP)

## Dynamic Polling-based Bandwidth Scheduling

- OLT properly *times* the sending of next Grant message to ONU BEFORE receiving transmission from ONU, given
- RTT to ONUs
- Transmission window of previous Grant
- Guard time needed
- Such that
- The next transmission from ONU is received by OLT right AFTER the receipt of the last bit of previous ONU transmission

**grant**

**grant**

- 11/15/2004

**Notes:**
OLT knows the size of ONU transmission, RTTs, plus guard time needed for next ONU transmission, 
therefore OLT knows when the last bit of the ONU data transmission will be received. 
It can then schedule the Grant message (for next ONU transmission) such that the next transmission from ONU is received by OLT right after the receipt of the last bit of the previous ONU transmission + some guard time.

## Dynamic Polling-based Bandwidth Scheduling

- Upon receipt of transmission from ONU, OLT
- Updates RTT to ONU
- Updates # of bytes requested

- 11/15/2004

**Notes:**
RTT times are updated constantly
If requested window size is zero, Grant is still sent; ONU does not send data, but sent a request for next transmission window

## Dynamic Polling-based Bandwidth Scheduling

- The next transmission from ONU is received by OLT is right AFTER the receipt of the last bit of previous ONU transmission + some guard time

- 11/15/2004

## Maximum Transmission Window Size (Wimax)

- Fixed: based on SLA for each ONU
- Dynamic: based network conditions
*W**i**max* determines
- guaranteed bandwidth available to ONU-i
- max polling cycle
- Large cycle  increased delay for all packets
- Small cycle  more bandwidth wasted by guard time
- polling cycle is variable depending on requested window sizes or network traffic condition
- excessive bandwidth distributed to highly loaded ONUs

- 11/15/2004

**Notes:**
Assignment of max transmission window size;
Even distributed of excessive bandwidth in the long term

## Maximum Transmission Window Size (Wimax)

- Fixed service
- Ignore the requested window size and always grants the max window  TDMA
- Limited service
- Grants the requested # of bytes, but no more than *W**max*
- Constant credit
- Add a constant credit to the requested window size
- Granted window size = requested window size + x
- Reduce average delay
- Linear credit
- Granted window size = requested window size + credit
- Size of credit proportional to the requested window
- Longer burst in last cycle is likely to continue in the next cycle

- 11/15/2004

**Notes:**
Fixed service is the same as TDMA

Limited: is the most conservative scheme and has the shortest cycle of all scheme, 
exhibits the best performance in terms of average packet delay and average queue size; guarantees minimum bandwidth required

Credit: allows additional frames buffered at ONUs to be transmitted without waiting for the next grant

## Other Scheduling Algorithms for EPON

- Differentiated services
- QoS for multiple classes of services (voice, data, video, etc)

- 11/15/2004

**Notes:**
Other scheduling algorithms exist for providing differentiated services; quality of service in terms of 
Bandwidth, delay, jitter,
Integrated services
Differentiated services

## Traffic Models

- Following traffic models in open literature:
- static traffic model
- all demands are known in advance and do not change over time
- dynamic random traffic model
-  a demand is assumed to arrive at a random time and last for a random amount of time
- admissible set model
- demands are from some prescribed traffic matrices
- incremental traffic model
- demands arrive sequentially. Once the demand is accommodated, the demand remains in the network indefinitely

- 11/15/2004

**Notes:**
Sliding scheduled traffic model; 
Briefly about existing models

## Motivation

- Many US DOE large-scale science applications must deliver Gbps throughput *at scheduled time durations*
*These applications require provisioning of scheduled dedicated channels or bandwidth pipes **at a specific time with certain duration*
- Bandwidth leasing market
*Customers need bandwidth only for a limited period of time*
*Limited-time leasing of bandwidth possible in the future*
- These scheduled capacity demands are dynamic
- demands only last during the specified intervals
- they are not entirely random
* *

- 11/15/2004

**Notes:**
Motivation

## New -- Sliding Scheduled Traffic Model

- A demand (*s, d, n, **l**, r*,  )
*s*: source
*d*: destination (or a destination set)
*n*: capacity requirement
-   : duration, or lasting time
- [*l*, *r*]: time window during which demand of duration  must be satisfied
- Example: (*s*, *d*, 1, 10:00, 13:00, 60 minutes)

*l*

*r*

- 11/15/2004

**Notes:**
Provide flexibility in specifying demands by users; allows ISP to better optimize network resource when provisioning demands
Look-ahead scheduling: a set of demands

- Bandwidth scheduling over a point-to-point WDM link under sliding scheduled traffic model

- 11/15/2004

**Notes:**
A p2p link can be an access link for example

## Problem Settings

- A single fiber link with *W *wavelengths
- Time is slotted with *T *time slots over a day:
*0, 1, ..., T-1*
- Demands require lightpaths periodically
- repeated every day
- denoted by (*a, b, L*) – a discrete version of sliding scheduled model
- starts in [*a, b*] and lasts *L *time slots (*L<T*)
- demand satisfied in [*a, b+L*]
- time flexibility defined as |[*a,b*]|-*1*
- Lightpath service (*w, s, L*): wavelength *w *is used for a duration of *L *time slots start from *s *per day (*L<T*)

- 11/15/2004

**Notes:**
Talk about a discrete version of the sliding scheduled traffic model;
b+L is the last possible time slot for the demand

## Problem definition

- Given a batch of lightpath demands, assign them lightpath services so that at any time there is at most one lightpath service per wavelength
*W*=2; *T*=8; Demands = (4,6,4) (3,3,2) (7,1,3) (1,3,4)

- 11/15/2004

**Notes:**
An example of scheduling a set of demands
Wrap around at the end [0, T-1] for demand 1

## Traffic Constraint for Schedulability Conditions

*Virtual Packet (VP) *model
- treat a demand (*a, b, L*) as a virtual packet that “arrives” at *a* and has a “transmission duration” or (work) of *L*
- (σ, ρ): ρ is a measure of the average traffic (demand) rate, and σ is a measure of the traffic (demand) burstiness
- ρ ≤ *W *
*A(t):** *work of virtual packets that arrive at time *t*
- (σ, ρ) constrained traffic, total work in [*x, y*]

- 11/15/2004

**Notes:**
VP model is used to characterize a set of demands; similar to leaky bucket model, to some degree
We refer to the sum of durations of a set of light requests as the work of for the set

## Theorem 1: Schedulability Condition when no lightpath wraps around at the end of [0, T-1]

- Suppose the batch of lightpath requests are (σ, ρ) constrained, *L**max* is the max lasting time, and let:
- And *A(t) = *0 for all
*(i.e., **there is no virtual packet arrival in the last*
*time slots**)*
- Then there is an assignment for the lightpath requests if their time flexibility is at least *f*

- 11/15/2004

**Notes:**
We are able to accommodate all demands on a link with W wavelengths and T time slots if the condition holds;
Assume that lightpaths do not wrap around at the end of [0, T-1]

## Theorem 2: General Schedulability Condition

- Suppose the batch of lightpath requests are (σ, ρ) constrained, and
- Let
- Then there is an assignment for the lightpath request if their time flexibility is at least *f*

- 11/15/2004

**Notes:**
There is a constraint on the total amount of work
We are able to accommodate all demands on a link with W wavelengths and T time slots if the condition holds; even with lightpath wrap around at the end of [0, T]

## Heuristic Scheduling Algorithms

- First Come First Serve (FCFS)
- Lowest valued wavelengths are used first
- Demands with earlier arrival times are scheduled first, ties are broken randomly
- Earliest Deadline First (EDF)
- Lowest valued wavelengths are used first
- Demands with the earliest deadline, *b+L*, is scheduled first
*b+L* is the last possible time slot for the end of the lightpath
- Both schemes tend to assign lightpaths close to time 0 which creates peak bandwidth demand at time 0

- 11/15/2004

**Notes:**
Need to elaborate on the heuristic scheduling algorithms
Deadline: b+L the last feasible time slot for the end of a lightpath

## Heuristic Scheduling Algorithms

- Lowest wavelength, maximum duration (LWMD)
- Wavelengths are filled with lightpath requests one wavelength at a time starting from wavelength 0
- When filling wavelength *k*, demands that have longer durations are scheduled first, ties broken randomly
- (*a, b, L*): start times are considered in the start interval [*a, b*] beginning with *a*

- 11/15/2004

**Notes:**
Need to elaborate on the heuristic scheduling algorithm

## Heuristic Scheduling Algorithms

- Lowest wavelength, Fixed (LWFixed)
- Wavelengths are filled with lightpath requests one wavelength at a time starting from wavelength 0
- Wavelength *k* is filled starting from time = 0
- Choose the longest unassigned request (*a, b, L*) that could start at time *t* and assign it starting from *t*
- Continue to fill the wavelength from *t+L*
- If no such request, then continue filling the wavelength from time *t+1*
- May create peak bandwidth demand at time 0

- 11/15/2004

**Notes:**
Need to elaborate on the heuristic scheduling algorithm

## Heuristic Scheduling Algorithms

- Lowest wavelength, Continuous (LWCont)
- Wavelengths are filled with lightpath requests one wavelength at a time starting from wavelength 0
- Wavelength *k* >0 is filled by starting at a time *t* that depends on how wavelength *k-1* was filled
- If wavelength *k-1*’s last request was assigned time slots [*x,y*], then wavelength *k* is filled starting from *y+1*

- 11/15/2004

**Notes:**
Need to elaborate on the heuristic scheduling algorithm
Try to spread out demand assignment

## Simulation

- Call blocking rate
- Ratio of # of calls blocked over # of calls
- Traffic blocking rate
- Ratio of the work of blocked lightpath requests over the work of all lightpath requests
- Scenarios:
- request duration evenly distributed in [1,31]
- expected duration of lightpaths = 16
- Earliest start time for a demand randomly distributed
- Blocking scenario
- 	*W=30,T=64*, 114 requests
- Nonblocking scenario
- 	*W* not limited, *T=64*, 128 requests

- 11/15/2004

**Notes:**
Time flexibility f is the same for all demand; f increases
For nonblocking case, try to find the minimal # of wavelengths that accommodate all demands;

## Blocking scenario - call

- FCFS, EDF high blocking rates
- LWCont has about the lowest blocking rates over all flexibility times
- Blocking rates decreases as time flexibility increases

- 11/15/2004

**Notes:**
Functions of the time flexibility f
FCFS and EDF have high blocking rates
LWCont has about the lowest blocking rates over all flexibility times
Blocking rates decreases as time flexibility increases except for LWFixed when the time flexibility is around 32

## Blocking scenario - traffic

- FCFS, EDF high blocking rates
- LWCont has about the lowest blocking rates over all flexibility times
- Blocking rates decreases as time flexibility increases

- 11/15/2004

## Nonblocking scenario

- Minimal # of wavelengths needed so that there is no blocking
- (Cmin=          , a lower bound on the # of wavelengths needed, *M* is work of the lightpath requests

- 11/15/2004

**Notes:**
LWMD and LWCont require minimal number of wavelengths;
Cmin is a lower bound on the # of wavelengths needed

## Result Summary

- Functions of the time flexibility *f*
- FCFS and EDF have high blocking rates
- LWCont has about the lowest blocking rates over all flexibility times
- Blocking rates decreases as time flexibility increases except for LWFixed when the time flexibility is around 32
- LWMD and LWCont require minimal number of wavelengths
- LWCont performs the best

- 11/15/2004

## Summary of Scheduling in P2P Link

- Scheduling over a single WDM link under a flexible traffic model
- Assigning periodic lightpath services which allow some time flexibility
- Schedulability conditions for a set of demands
- Heuristic scheduling algorithms

- 11/15/2004

- Bandwidth provisioning in WDM networks
- Look-ahead scheduling of a set of demands with sub-wavelength capacity *under sliding scheduled traffic model*

- 11/15/2004

**Notes:**
Will look at scheduling of a dynamic demand at the end

## Space-Time Traffic Grooming Problem

- Given a set of sliding scheduled traffic demands *M,*
- properly place demands within their time windows,
- route and groom (by finding a route and assigning a proper wavelength to each demand in *M*) such that
***non-blocking****** case***
- network has enough resources to accommodate all the demands in *M* to meet their specifications (i.e., capacity and schedule requirements)
- goal is to minimize total network resources used

- 11/15/2004

**Notes:**
Refresh the sliding scheduled traffic model
Need to place demands within their time windows
Route and groom a set of demands
The problem is NP-complete; formal proof is needed.

Two step approach

## Space-Time Traffic Grooming Problem

***blocking case***
- network does not have enough resources to accommodate all the demands as specified
- goal is
- to minimize the number of demands to be *rearranged* (i.e., to minimize the subset of demands that may have their starting time changed in order to have all the demands in the set *M* accommodated
- to minimize of total network resources used
*demand priority can also be considered if necessary*

- 11/15/2004

**Notes:**
To minimize the subset of demands that may have their starting time changed
Priority of demands may be considered

## Time Conflict & Resource Conflicts

- Temporal conflicts: Time conflicts of a set of scheduled demands *M*
- Demands may overlap in time
- Demands that are disjoint in time allow resource reuse
- Spatial conflicts: Resource conflicts
- Routes of demands may overlap
- If not enough resources are available, conflicts result
- Some demands may not be schedulable because of lack of resources

- 11/15/2004

**Notes:**
Observations
Some demands may not be schedulable as a result of either type of conflict

## Interval Graph Modeling of Time Conflict Reduction

**Tight node:  ****2 x 8 > 10**

**Strong edge**

**Weak Edge**

**Loose node:**
**2 x 5 < 25**

- 11/15/2004

**Notes:**
Describe our work using an example
Use interval graphs to model the time conflicts among demands; a demand  a node; time conflict between a pair of demands  an edge between a pair of nodes
Tight nodes
Loose nodes
Strong edges; loose edges
Strong edges cannot be between two loose edges;

*Lemma*: no strong edge connects two loose nodes.
*Theorem*: let *v* be a loose node, *A*(*v*) be the set of nodes connected to *v* with strong edges, then all nodes in *A*(*v*) are tight nodes and are connected by strong edges pair wise.

- 11/15/2004

**Notes:**
There is only one loose node among a set of nodes connected by strong edges.

## Time Conflict Reduction Algorithm

- Use an interval graph to model time conflicts among scheduled demands
- Identify time conflicts that can be avoided
- Remove time conflicts in a greedy manner to obtain proper placement of demand intervals within their allowed time windows

- 11/15/2004

## Time Conflict Reduction Algorithm

- 11/15/2004

**Notes:**
skip

## Performance of Time Conflict Reduction Algorithm

- Demand length 10-90% of time window size
- Weak time correlation among demands

- 11/15/2004

**Notes:**
Define time correlation: for time windows
Demand length is 10-90% of time window for weak time correlation
More conflicts are resolved when demand length is smaller w.r.t time window size
Overall 40-close to 100% of conflicts resolved

## Performance of Time Conflict Reduction Algorithm

- Demand length 10-90% of time window size
- Medium time correlation among demands

- 11/15/2004

**Notes:**
Demand length is 10-90% of time window for medium time correlation
As time correlation becomes stronger, lower percentage of conflicts is resolved

## Performance of Time Conflict Reduction Algorithm

- Demand length 10-90% of time window size
- Strong time correlation among demands

- 11/15/2004

**Notes:**
Demand length is 10-90% of time window for strong time correlation
As time correlation becomes stronger, lower percentage of conflicts is resolved

## Performance of Time Conflict Reduction Algorithm

- Demand length 10-100%
- of time window size

- Demand length 10-100% of time window size
- Different time correlation among demands

- 11/15/2004

**Notes:**
Demand length is randomly selected w.r.t time window for different time correlation (for time windows); demand length from 10% to 100% of time windows;
Overall, about 50% or more conflicts can be resolved

## Time Window Based Routing and Grooming Algorithm

- Divide a set of scheduled demands into subsets called *time windows*
- Demands in a time window have time conflicts pair wise
- Schedule demands in a time window according to demands’ decreasing resource requirements
- Using a modified Dijkstra’s algorithm on a wavelength layered graph
- If a demand is blocked due to unavailability of resources, *rearrange* the schedule of the demand
- Schedule the demand *earlier or later in time* when the required resources are available

- 11/15/2004

**Notes:**
Straddling demands

## Demand Set Division

- 11/15/2004

**Notes:**
Straddling demands

## Time Window Based Grooming Algorithm

*D**S*** : set of straddling demands**
*TW**i ***: set of demands in a time window *****i***
*D**R ***: set of demands need to be rearranged**
**Space Time RWA Algorithm** (*G*, *M*)
- run *Time Window Division** Algorithm* (*M*);
- run *Greedy Time Window Grooming** Algorithm* (*G*, *D**S*);
- run *Greedy Time Window Grooming** Algorithm* (*G*, *TW**i*) for all *TW**i*;
- if (*D**R**  not empty*), run *Rearrange RWA** Algorithm* (*D**R*);

- 11/15/2004

**Notes:**
More details about algorithms

## Performance Evaluation

- Time correlation of a demand set after time conflict reduction
- characterize the extent of conflicts among demands in the time domain
- weak, medium, strong
- Demand sets contain 50-400 scheduled bidirectional demands
- 30 wavelengths per link

- 11/15/2004

**Notes:**
Wavelength continuous case
TWA: time-window based scheduling

## NSFNET

- 11/15/2004

**Notes:**
Numbers are distance units

## Traffic Grooming: Results - I

- Grooming factor *g* varies from 4 to 32
- Given a grooming factor *g*, capacity units of a demand drawn from [1, 2], [1, 4], ..., [1, *g*]
- Metric: Total # of wavelength-links and max # of wavelengths used on a link increase
- when # of demands increases
- when average demand capacity increases
- Grooming is more effective when average demand capacity is smaller relative to grooming factor
- Stronger time correlation negatively impacts effectiveness of grooming

- 11/15/2004

**Notes:**
Grooming factor is the granularity of a wavelength channel

## Traffic Grooming: Results - II

- When grooming factor *g* increases, the amount of resources used decreases and levels off when *g *becomes large
- The decrease in resources used is more significant when the demand time correlation is stronger

- 11/15/2004

**Notes:**
Tabu search g=4, demand capacity drawn [1,2]

## Total number of wavelength-links vs number of demands, weak correlation

- Grooming factor *g* = 16
- Given a grooming factor *g*, capacity units of a demand drawn from [1, 2], [1, 4], ..., [1, *g*]
- Total # of wavelength-links used increase
- when # of demands increases
- when average demand capacity increases

- 11/15/2004

**Notes:**
g=16
[1,g]

## Total number of wavelength-links vs number of demands, medium correlation

- Grooming factor *g* = 16
- Given a grooming factor *g*, capacity units of a demand drawn from [1, 2], [1, 4], ..., [1, *g*]
- Total # of wavelength-links used increase
- when # of demands increases
- when average demand capacity increases

- 11/15/2004

**Notes:**
g=16
[1,g]

## Total number of wavelength-links vs number of demands, strong correlation

- Grooming factor *g* = 16
- Given a grooming factor *g*, capacity units of a demand drawn from [1, 2], [1, 4], ..., [1, *g*]
- Total # of wavelength-links used increase
- when # of demands increases
- when average demand capacity increases

- 11/15/2004

**Notes:**
g=16
[1,g]

## Max number of wavelengths vs number of demands, weak correlation

- Grooming factor *g* = 16
- Given a grooming factor *g*, capacity units of a demand drawn from [1, 2], [1, 4], ..., [1, *g*]
- Max # of wavelengths used on a link increase
- when # of demands increases
- when average demand capacity increases

- 11/15/2004

**Notes:**
g=16
[1,g]

## Max number of wavelengths vs number of demands, medium correlation

- Grooming factor *g* = 16
- Given a grooming factor *g*, capacity units of a demand drawn from [1, 2], [1, 4], ..., [1, *g*]
- Max # of wavelengths used on a link increase
- when # of demands increases
- when average demand capacity increases

- 11/15/2004

**Notes:**
g=16
[1,g]

## Max number of wavelengths vs number of demands, strong correlation

- Grooming factor *g* = 16
- Given a grooming factor *g*, capacity units of a demand drawn from [1, 2], [1, 4], ..., [1, *g*]
- Max # of wavelengths used on a link increase
- when # of demands increases
- when average demand capacity increases

- 11/15/2004

**Notes:**
g=16
[1,g]

## Total number of wavelength-links vs Grooming factor

- # of demands = 350
- Grooming factor *g= 1, 4, 8, ... 32*
- Total # of wavelength-links used decrease
- when grooming factor *g* increases
- levels off when *g* becomes large
- The decrease in resources used is more significant when the demand time correlation is stronger

- 11/15/2004

**Notes:**
g is varied

## Max number of wavelengths vs Grooming factor

- # of demands = 350
- Grooming factor *g= 1, 4,.. 32*
- Max # of wavelengths used on a link decrease
- when grooming factor *g* increases
- levels off when *g* becomes large
- The decrease in resources used is more significant when the demand time correlation is stronger

- 11/15/2004

**Notes:**
g is varied

- Dynamic scheduling of a demand under the sliding scheduled traffic model

- 11/15/2004

## Problem

- Given a demand (*s, d, n, **l**, r*,  ), find a route that has at least *n* units of bandwidth in a time interval of length at least    in [*l, r*]

- 11/15/2004

## Dynamic Scheduling Algorithm

- Divide time into time slots
- Consider time intervals of length * * in [*l, **r*] starting from *l: *
- [*l, l+  *], [*l+1, l+  +1*], [*l+2, l+  +2*], ...
- Within a time interval, find a shortest path with at least *n* units of bandwidth given current network resource state info
*h*-hop optimal routing algorithm:
- A modified Bellman-Ford algorithm
- Find the maximum available bandwidth path with at most *h* hops
- If such a path is not found, try next time interval

- 11/15/2004

**Notes:**
Discretize time

## Summary

- Bandwidth scheduling in EPON
- Sliding scheduled traffic model
- Bandwidth scheduling over a point-to-point WDM link
- Bandwidth provisioning in WDM networks
- Look-ahead scheduling of a set of demands
- Dynamic scheduling of a demand

- 11/15/2004