as listed in Table I. In other words, the authors assumed
that time was divided into discrete time intervals. The
key idea underlying this mathematical model was to make
the optimization problems tractable, so that these prob-
lems could be simplified into static optimization problems
(e.g., max-flow or min-cost flow problems). However, in this
model it may be difficult to gain practical insights into how
the network performance changed in the course of the slot-
ted operations, because the requests were given in ad-
vance, and the durations were given as integers for the
numbers of time slots.
To summarize, on the one hand, the fine granular slotted
operations offer significant benefits to networks when serv-
ing short flows, which implies the potential for using
coarser slotted operations to networks where the traffic
is dominated by bulk data flows. On the other hand, the
time-slotted model is a useful mathematical tool for solving
optimization problems, and this model has been widely
used in SnF applications. However, few studies have inves-
tigated the effects of slotted network operations on network
performance in the practical sense or how to adopt time
slots to meet the emerging needs for bulk data traffic.
These observations motivate us to introduce a larger time
slot into SnF and explore its performance.
C. Provisioning Process of SnF
The use of assistive storage greatly mitigates its peak-
hour bandwidth contentions. However, the storage itself
introduces additional complexities into the conventional pro-
visioning process . In that case, a problem of spatial resource
allocation becomes a scheduling problem. To solve this sched-
uling issue, bo th the bandwidth and the storage constraints
must be considered, and both the spatial assignments and
the temporal arrangements must be performed. As was
pointed out in Refs . [6,7,14], this provisioning process is
complicated. Fortunately, the time-shifted multilayer graph
(TS-MLG) [20] provides a useful framework to tackle this
problem, and this framework significantly simplifies the
provisioning process. In this paper, we use a TS-MLG to
study the sSnF OCS network.
1) Overview of TS-MLG: Figure 1 shows a sample TS-
MLG. Basically, a TS-MLG is a multilayer graph built from
a set of snapshots (i.e., layers) of the dynamics in a net-
work. The layers are stacked downward in a time-increas-
ing order. Spatial links connect different nodes within the
same layer, and the connections between the same nodes in
different layers are temporal links. Traversing a spatial
link denotes physical delivery of data from one node to
another. Traversing a temporal link denotes storing the re-
quest on a specified node for a certain period of time. The
capacity of a spatial link refers to the bandwidth of that
link, whereas the capacity of a temporal link refers to
the storage capacity of that node.
Figure 1 also illustrates an example of how routing can
be accomplished with the TS-MLG. A data transfer request
from Node 4 to Node 6 arrives at the network at time t
0
.
At the time of arrival, an end-to-end transmission is not
possible, as the network has insufficient bandwidth. By
performing shortest-path routing (e.g., Dijkstra’s algo-
rithm) on the TS-MLG, an “end-to-end” path, i.e., Path
4–5–5
0
–6
0
, is provided to route this request, where Node
5 is used as an intermediate storage node.
TABLE I
T
IME SLOTS IN STORE-AND-FORWARD TECHNIQUES
Optimization Goal Major Assumptions Size of Time Slot Reason for Choosing the Slot Size
Minimize transmission time [16] Time-slotted model,
limited storage
1 s Typical bulk data transfers last
for minutes or hours
Improve network throughput [8] Time-slotted model,
limited storage
5 s Based on the transfer time of each chunk
Minimize transfer cost [5,14] Time-slotted model,
unlimited storage
5 min Based on the 95th-percentile pricing scheme
Minimize transfer cost [17] Time-slotted model,
unlimited storage
1 h Typical bulk data transfers are expected
to complete within a day
Reduce peak traffic and balance
network traffic [7]
Time-slotted model,
limited storage
1 h Traffic changes follow strong
diurnal patterns
Reduce request blocking [10] Time-slotted model,
unlimited storage
1 time unit N/A
Reduce inter-domain traffic [15] Time-slotted model,
unlimited storage
1 time unit N/A
Minimize delay or maximize
the amount of data delivered [18]
Time-slotted model,
limited storage
1 time unit N/A
time
Temporal Link
Spatial Link with
Available Bandwidth
Spatial Link without
Available Bandwidth
...
Snapshot at t
0
Snapshot at t
1
Snapshot at t
n
23
4
56
4'
5'
6'
1
Fig. 1. Schematic of a time-shifted multilayer graph.
Lin et al. VOL. 9, NO. 7/JULY 2017/J. OPT. COMMUN. NETW. 565