WO2013003327A1

WO2013003327A1 - Dynamic advance reservation with delayed allocation

Info

Publication number: WO2013003327A1
Application number: PCT/US2012/044162
Authority: WO
Inventors: Vinod VOKKARANE; Arun Somani
Original assignee: University Of Massachusetts; Iowa State University Research Foundation, Inc.
Priority date: 2011-06-27
Filing date: 2012-06-26
Publication date: 2013-01-03
Also published as: US20120327953A1; US8902920B2

Abstract

A method of scheduling data transmissions from a source to a destination, includes the steps of: providing a communication system having a number of channels and a number of paths, each of the channels having a plurality of designated time slots; receiving two or more data transmission requests; provisioning the transmission of the data; receiving data corresponding to at least one of the two or more data transmission requests; waiting until an earliest requested start time Ts; allocating at the current time each of the two or more data transmission requests; transmitting the data; and repeating the steps of waiting, allocating, and transmitting until each of the two or more data transmission requests that have been provisioned for a transmission of data is satisfied. A system to perform the method of scheduling data transmissions is also described.

Description

DYNAMIC ADVANCE RESERVATION WITH DELAYED ALLOCATION

CROSS-REFERENCE TO RELATED APPLICATIONS

[0001] This application claims priority to and the benefit of co-pending U.S.

provisional patent application Serial No. 61 /501 ,665, filed June 27,201 1 , which application is incorporated herein by reference in its entirety.

STATEMENT REGARDING FEDERALLY FUNDED RESEARCH OR DEVELOPMENT

[0002] The invention described herein was made in the performance of work under

Department of Energy Grant DE-SC0004909, and is subject to the provisions of Public Law 96-517 (35 U.S.C. §202) in which the Contractor has elected to retain title.

FIELD OF THE INVENTION

[0003] The invention relates to scheduling multiple tasks given finite resources to perform the tasks in general and more particularly to scheduling data transmission on a communication network having fixed bandwidth resources.

BACKGROUND OF THE INVENTION

[0004] A Grid network is a collection of geographically distributed resources, such as storage nodes, super computers, and scientific equipment that are accessible to users over a network. These networks often deal with the transfer of large amounts of data (e.g., in the terabytes to petabytes range). A common traffic model used for such application is the dynamic traffic model. Requests are assumed to arrive sequentially, according to a stochastic process, and have finite holding times. The goal of the routing process is to minimize request blocking, where a user's request is primarily denied only due to lack of resources.

Traditional ly, the data transmission for an immediate reservation (I R) demand starts right after arrival of the request and the holding time is typically unknown. In contrast, an advance reservation (AR) typically specifies a data transmission start time that is sometime in the future and also specifies the desired holding time.

[0005] Advance reservation methods were originally proposed for electronic networks followed by optical networks such as the AR method described by J. Zheng, et. al. in "Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks," Proceedings, IEEE International Conference on Communications, vol. 5, 2002, pp. 2722-2726 (2002). Since then, a number of continuous routing and wavelength assignment (RWA) heuristics based on static route computation have been proposed. These heuristics generally use the same basic structure, differing only in how they select the segment. They scan possible starting timeslots over all available lightpaths and choose a segment according to some criteria. Path switching for flexible advance reservation in electronic networks has also been proposed.

[0006] There is a need for a more efficient routing system and routing method for large data transfers over Grid networks

SUMMARY OF THE INVENTION

[0007] According to one aspect, the invention features a method of scheduling data transmissions from a source to a destination, including the steps of: providing: a

communication system having a number of channels and a number of paths, each of the channels having a plurality of designated time slots, and a bandwidth defined as the number of channels multiplied by the number of paths, and a bandwidth capacity defined as the bandwidth multiplied by the number of designated time slots; receiving two or more data transmission requests, each of the two or more data transmission requests designating a transmission of data from a source to a destination, each of the two or more data transmission requests including a requested start time Ts of transmission and a requested number of time slots for the transmission of the data; provisioning the transmission of the data corresponding to each of the two or more data transmission requests via the communication bandwidth without designating a channel of the number of channels and without designating a path of the number of paths; receiving data corresponding to at least one of the two or more data transmission requests; waiting until a current time within a time interval t of an earliest requested start time Ts of the two or more data transmission requests; allocating at the current time each of the two or more data transmission requests to a channel of the number of channels and to a path of the number of paths in a way which optimizes a use of the bandwidth capacity; transmitting the data corresponding to the at least one of the two or more data transmission requests that has been allocated on the allocated channel and the allocated path; and repeating the steps of waiting, allocating, and transmitting until each of the two or more data transmission requests that have been provisioned for a transmission of data is satisfied.

(0008] In one embodiment, the step of provisioning the transmission includes provisioning the transmission of the data during a request provisioning phase.

[0009] In another embodiment, the step of allocating includes allocating at least one of the two or more data transmission requests during a request allocation phase.

[0010] In yet another embodiment, the step of providing a communication bandwidth is performed using an optical communication network.

[0011] In yet another embodiment, the step of providing an optical communication network is performed using an optical communication network having wavelength division multiplexed transmission capability.

[0012] According to one aspect, the invention features a system for provisioning data transmission from a source to a destination which includes a communication system having a number of channels and a number of paths. Each of the channels having a plurality of designated time slots, in which a communication bandwidth is defined as the product of the number of channels times the number of paths and a bandwidth capacity is defined as the product of the bandwidth times the number of designated time slots. A processor has instructions provided on a machine readable medium. The processor is configured to perform the following steps when the instructions are operative: determining the communication bandwidth and the bandwidth capacity; receiving two or more data transmission requests, each of the two or more data transmission requests designating a transmission of data from a source to a destination, each of the two or more data transmission requests including a requested start time Ts of transmission and a requested number of time slots for the transmission of the data; provisioning the transmission of the data corresponding to each of the two or more data transmission requests via the communication bandwidth without designating a channel of the number of channels and without designating a path of the number of paths; receiving data corresponding to at least one of the two or more data transmission requests; waiting until a current time within a time interval t of an earliest requested start time Ts of the two or more data transmission requests; allocating at the current time each of the two or more data transmission requests to a channel of the number of channels and to a path of the number of paths in a way which optimizes a use of the bandwidth capacity; transmitting the data corresponding to the at least one of the two or more data transmission requests that has been allocated on the allocated channel and the allocated path; and repeating the steps of waiting, allocating, and transmitting until each of the two or more data transmission requests that have been provisioned for a transmission of data is satisfied.

[0013] The foregoing and other objects, aspects, features, and advantages of the invention will become more apparent from the following description and from the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

[0014] The objects and features of the invention can be better understood with reference to the drawings described below, and the claims. The drawings are not necessarily to scale, emphasis instead generally being placed upon illustrating the principles of the invention. In the drawings, like numerals are used to indicate like parts throughout the various views.

[0015] FIG. 1 shows a flow chart of a generalized view of the single slot reservation method according to the invention. FIG. 2 shows an overview block diagram of a system suitable to perform the inventive method.

[0016] FIG. 3A to FIG. 3D show time-slot time-lines and provisioning and allocation examples for the ASAR and the SSAR methods.

[0017] FIG. 4A to FIG. 4D show time-slot time-line diagrams of a single-slot advance reservation for two paths (P I , P2) where each path includes two channels (λι and λ2).

[0018] FIG. 5 shows one example of pseudo code suitable for performing channel allocation according to principles of the invention.

[0019] FIG. 6A shows a graph of average blocking probability for the SSAR and the

ASAR methods vs. load for constant book-ahead times.

[0020] FIG. 6B shows a graph of average blocking probability for the SSAR and the

ASAR methods vs. load for uniformly distributed book-ahead times.

[0021] FIG. 7 shows a schematic illustration of a Unicast embodiment of a SSAR system and method according to the invention.

[0022] FIG. 8 shows a schematic illustration of a Multicast SSAR system and method according to the invention.

[0023] FIG. 9 shows a schematic illustration of a Anycast embodiment of a SSAR system and method according to the invention. [0024J FIG. 10 shows a schematic illustration of a Manycast SSAR system and method according to the invention.

(0025) FIG. 1 1 shows a schematic illustration of a network where each of the nodes can transmit on any channel and where a request can be from one or more source nodes to one or more destination nodes.

DETAILED DESCRIPTION

[0026] We describe hereinbelow, a new continuous advance reservation process that checks all of the possible slots (e.g., time-slots) in a requests's horizon. This description presents a new approach to the all-slots advanced reservation (ASAR) process such as was described by Charbonneau, et. al. in "Dynamic Non-Continuous Advance Reservation over Wavelength-Routed Networks," University of Massachusetts Dartmouth. Computer Science, Master's Thesis, September, 2010.

[0027] A data transmission time is typically time slotted and each dynamic request typically uses multiple contiguous time slots on the same wavelength path. Traditional advance reservation can lead to resource fragmentation where small gaps in wavelength usage cannot be utilized. Our new system and method does not create any fragmentation as a result of delayed resource allocation. If a gap is created, it is because there is no request to use a particular time slot. We overcome unnecessary blocking by allocating a "channel" (e.g. a wavelength path or light path), by using a two step process in which the channel is allocated, typically at a later time, when the request is actually being served. We refer to the new system and method according to invention as a single slot advance reservation (SSAR) system and method. As described in more detail hereinbelow, SSAR simplifies control of the process. We also describe hereinbelow how the SSAR system and method out-performs existing ASAR methods and the associated continuous flexible advance reservation heuristics.

SINGLE SLOT ADVANCE RESERVATION (SSAR) SYSTEM AND METHOD

GENERAL APPROACH

[0028] FIG. 1 shows a flow chart of a generalized view of the single slot reservation method according to the invention. The generalized SSAR method of schedul ing data transmissions from a source to a destination, includes the steps of providing a communication system ( 101 ) having a number of channels and a number of paths, each of the channels having a plurality of designated time slots, and a bandwidth defined as the number of channels multiplied by the number of paths, and a bandwidth capacity defined as the bandwidth multiplied by the number of designated time slots; receiving two or more data transmission requests ( 103), each of the two or more data transmission requests designating a transmission of data from a source to a destination, each of the two or more data transmission requests including a requested start time Ts of transmission and a requested number of time slots for the transmission of the data; provisioning the transmission of the data ( 105) corresponding to each of the two or more data transmission requests via the communication bandwidth without designating a channel of the number of channels and without designating a path of the number of paths; receiving the data ( 107) corresponding to at least one of the two or more data transmission requests; waiting until a current time within a time interval t of an earliest requested start time Ts ( 109) of the two or more data transmission requests; allocating at the current time ( 1 1 1 ) each of the two or more data transmission requests to a channel of the number of channels and to a path of the number of paths in a way which optimizes a use of the bandwidth capacity; transmitting the data ( 1 13) corresponding to the at least one of the two or more data transmission requests that has been allocated on the allocated channel and the allocated path; and repeating the steps of waiting, allocating, and transmitting ( 1 1 5) until each of the two or more data transmission requests that have been provisioned for a transmission of data is satisfied.

(0029J In the description which follows hereinbelow, the step of provisioning the transmission generally takes place during a "request provisioning phase" (RPP), and the step of allocating general ly takes place in a "request allocation phase" (RAP).

[0030] While the method is believed to be generally applicable to any type of scheduled multiple activities, in the context of data transmission, it is believed to be advantageous particularly in the field of optical communication, such as pertains to data transmission over an optical network. Such optical networks typically use a multiplexing scheme to afford more channels than the number of optical fibers present in any given fiber optic cable. For example, one such multiplexed optical network scheme which is suitable to provide additional channels per optical fiber for the inventive method is an optical communication network having wavelength division multiplexed (WDM) transmission capability.

[0031] FIG. 2 shows an overview block diagram of a system suitable to perform the inventive method. A system for provisioning data transmission from a source to a destination, using the SSAR method typically includes a communication system (201 ) having a number of channels and a number of paths (not shown in FIG. 2), each of the channels has a plurality of designated time slots, in which a communication bandwidth is defined as the product of the number of channels times the number of paths and a bandwidth capacity is defined as the product of the bandwidth times the number of designated time slots. A processor (203) has instructions provided on a machine readable medium. The processor is configured to perform the following steps when the instructions are operative: determining the communication bandwidth and the bandwidth capacity; receiving two or more data transmission requests, each of the two or more data transmission requests designating a transmission of data from a source (e.g., 205) to a destination (e.g. 207), each of the two or more data transmission requests including a requested start time Ts of transmission and a requested number of time slots for the transmission of the data. The generalized SSAR steps are as described hereinabove, provisioning the transmission of the data corresponding to each of the two or more data transmission requests via the communication bandwidth without designating a channel of the number of channels and without designating a path of the number of paths; receiving data corresponding to at least one of the two or more data transmission requests; waiting until a current time within a time interval t of an earliest requested start time Ts of the two or more data transmission requests; allocating at the current time each of the two or more data transmission requests to a channel of the number of channels and to a path of the number of paths in a way which optimizes a use of the bandwidth capacity; transmitting the data corresponding to the at least one of the two or more data transmission requests that has been allocated on the allocated channel and the allocated path; and repeating the steps of waiting, allocating, and transmitting until each of the two or more data transmission requests that have been provisioned for a transmission of data is satisfied. COMPARISON OF SSAR WITH ALL-SLOTS ADVANCE RESERVATION (ASAR) .

[0032] Next, we discuss issues related to the prior art ASAR process and then compare a prior art ASAR method to an SSAR system and method according to the invention.

Exemplary embodiments of a SSAR control process and the corresponding exemplar)' data structures suitable for use in an SSAR system and method according to the invention are described. Also, the performance of the inventive SSAR system and method is compared to the performance of an ASAR process of the prior art.

ASAR

[0033] An all-slots advance reservation (ASAR) process of the prior art assumes that a fixed number of precomputed wavelength paths exist between a source and a destination. Each pre-computed path is assigned a route and a wavelength and is referred to as a channel. Each channel is divided into time slots that are time synchronized with each respect to each other. An incoming request is assumed to use a set of contiguous slots. Thus a cross product of all pre-computed channels (paths) and future time-slots form the total available resource pool. The ASAR process keeps track of channels-time slots for the advance reservation period.

[0034] Upon arrival of a request for service, the ASAR process checks the availability of the requested time slots for all channels starting with the requested start time slot. It chooses a channel that fits the best for the request in hand. Given all starting time and channel combinations, there may be multiple potential channels to select from. ASAR methods use a Best-Fit approach. If time slots are available, then it immediately books/reserves the entire duration of the request and notifies the source that the request is accepted by returning a valid non-empty schedule. The reserved time slots on the selected channel are also reserved. I f the time slots are not available then the source is notified that the request is blocked.

|0035] Checking the availability of time slots on wavelengths and scheduling reservations are intertwined. The controller needs to check all existing schedules to accept/reject a request and then to schedule the channel for the new reservation request. Thus, the ASAR methods use relatively complex processes. ASAR performs well if the book-ahead time is a constant, such as when a request must arrive, say k slots in advance of the requested slot. However, if the requests arrive with variable book-ahead times, then the ASAR method may lead to higher blocking. The higher blocking is a direct result of preallocation of the channel. The single-slot advance reservation (SSAR) system and method described herein solves the problem of blocking caused by channel preallocation.

[0036] Before describing the SSAR process in more formal terms, we first use examples to demonstrate the shortcoming of the ASAR process. The following examples illustrate the problems of blocking (e.g., blocking using ASAR methods of the prior art) as related to preallocation.

PROBLEM WITH PREALLOCATION OF CHANNELS IN ASAR

[0037] Suppose the requests (e.g. for data transmission) are denoted by using a 3-tuple,

<number, starting slot, # of slots>, where number is the dynamic request identifier, starting slot is the earliest slot that the request can use in the future, and # of slots is the request duration in units of slots. Note that the book-ahead time (in terms of slots) for each request can be computed implicitly as request starting slot - arrival slot.

[0038] FIG. 3A to FIG. 3D show time slot time lines and provisioning and allocation examples for the ASAR and the SSAR methods. For example, consider a case where there are two channels (e.g., λ| and λ2) and the system state is currently prior to time slot 0 (¾). A request number 1 arrives with starting slot number 3 and number of slots requested 2, or < 1 ,3,2>. Suppose, for example, that channel 1 is allocated (FIG. 3 A). Next, a second request <2, 1 , 1 > ("R2" - second request, starting slot 1 , 1 slot to be used) arrives. There are two cases. Suppose, the second request is allocated channel 2 (FIG. 3A). In this case, if a third request <3,0,4> arrives (FIG. 3A, right side), it is blocked as shown in FIG. 3A. Without preal location the third request would not have been blocked, as two channels are at most needed in any slots and there are two channels. Alternately, suppose now that request 2 is allocated channel 1 (FIG. 3B). In this latter case, suppose a third request <3,2,3> arrives using the SSAR method (FIG. 3B). The third request can now be allocated on channel 2.

[0039] Now, turning to FIG. 3C and FIG. 3D, suppose a fourth request "R4" <4,0,3> arrives. As shown in FIG. 3C, according to the ASAR method of the prior art, the fourth request would have to be blocked. However, using the inventive SSAR method without preallocation (FIG. 3D), the fourth request ^!'R4" would not be blocked. Thus, a delayed allocation of the channel using SSAR according to the invention, leads to an efficient solution and solves the problem of blocking as related to preallocation. In the simpler case where the book-ahead time for all the requests is constant, the ASAR process can work well, but never better than the SSAR method.

SINGLE-SLOT ADVANCE RESERVATION (SSAR)

[0040] We have developed a new two-phase resource provisioning and allocation process called single-slot advance reservation (SSAR). The inventive process solves the problem of blocking as related to preallocation by the use two phases: 1 ) a request provisioning phase (RPP) and 2) a request allocation phase (RAP). To demonstrate the process, we consider the same scenario which was described hereinabove with regard to ASAR. As before, requests are assigned one of the many wavelength paths available between a source and a destination and each of these paths is time slotted. An incoming request specifies how many (multiple) time slots are needed, starting with a specific time slot. The corresponding data transmission which eventually follows preferably should use the same wavelength path during the entire duration of the request. A request is either accepted if the necessary resources (e.g. a starting slot and a number of slots for a transmission of data) are available or is blocked if the resources needed to fulfill a particular request are not available.

[0041] In the request provisioning phase, the SSAR system and method only checks whether or not the request can be provisioned without doing any actual resource allocation. I f the request can be provisioned, then when as the clock advances towards the request's start time, a single time-slot is reserved for this request, while keeping the future time slots open for reservation. The SSAR approach of separating the provisioning step from the allocation step can be used to guarantee that a request continues on the same channel. An exemplary SSAR controller data structure and process suitable to perform the SSAR method is described in more detail hereinbelow.

[0042] FIG. 4A to FIG. 4D show time slot "time line diagrams" of a single-slot advance reservation for two paths (P I , P2) where each path includes two channels (λι and λ2). FIG. 4A to FIG. 4D depict how the slot assignment process performs as time progresses (i.e., from time slot to to time slot 13). The blocks represent either time slots available or time slots reserved. The example uses three requests < 1 ,4, 1 > ("R l " - request one, start time slot 4, one slot needed), "R2" - <2,2,2>, and ^i:R3" - <3,3, 13>. Each request is successively routed onto a separate channel one at a time and continued on that same channel. Using the same approach as in the first example, the requests will be routed so that requests 2 and request 1 are routed on channel 1 (FIG. 4B, FIG. 4C) and request 3 is routed on channel 2 (FIG. 4D). Note that FIG. 4D ends at time slot t3, and the remaining 1 2 contiguous time slots of the 1 3 slot "R3" request are not shown in the figures.

[0043] Thus, it can be seen that the SSAR system and method performs better in comparison to ASAR. It also reduces the complexity of the scheduler. SSAR keeps track of the number of channels available in all time slots in the first phase and allocates resources on a single-slot reservation basis in the second phase. A system using this inventive separation of the provisioning and allocation steps has less scheduler control complexity and can accommodate more requests. Such a centralized scheduler implementation is more scalable. Also, since signaling is performed only when a request is started and terminated, the SSAR method does not increase signaling needs.

SSAR CENTRALIZED SCHEDULER

[0044] The controls for the resource provisioning phase (RPP) and for the resource allocation phase (RAP) for a request are independent of each other. The RPP only considers if a channel is available in all requested slots to serve the request as needed. Then at a later time, RAP allocates the actual channel to be used. RAP also guarantees that each request is allocated the same channel throughout its contiguous lifetime.

[0045] We now define a few terms and relationships used in the description which follows hereinbelow. The current slot number is numbered 0. The starting time of a reservation is maintained with respect to the current time slot. Thus as time advances, the relative starting time of a request approaches 0, and when it becomes 0, the request is served in that slot. The control system keeps a global slot counter which is set to zero at the starting of the system. A request is made using the start time value synchronized with the global slot counter. For the purpose of control, the system converts the start time to relative time with respect to current slot (0). To illustrate this conversion, suppose the global slot time counter has a value of t_g. An incoming request r arrives with a start time, t_r and the number of slots needed, s_r. Then the relative start time for this request would be set to t_r - t_g. The request wi ll be active from slot number t_r - t_g to slot number t_r - t_g + s_r - 1 . The request numbers (modulo some large number) may be assigned by the system to an incoming request to keep track of other parameters of the requests. We only keep track of the request number. For simpl icity, other information which does not impact the centralized scheduling process is left out of the description which follows.

DATA STRUCTURES AND RATIONALE

[0046] In order to implement RPP, the centralized scheduler has to maintain the following data structures:

Slot occupancy counters (SOC)

[0047] The process defines a number N of them, where N is the horizon or the number of slots for which reservation can be made currently. The first slot or the current slot is referred to as to and next N-l slots are referred to as /_/ to The maximum value any SOC can store is same as the maximum number of channels available. For example, for M channels, log M bit counters would be sufficient. Logical slot numbers automatically advance (go down) as the global slot counter increases (since the current slot is always numbered 0).

Reservation table (or reservation lists)

[0048] Al l reservations are stored in a request table that may store several parameters associated with the request. However, for the purpose of the control, we maintain one reservation list (assumed to be a linked list) for each slot, i.e., to to t^-i, each with up to M entries, where M is the number of channels available for allocation. In reality, the number of entries in the list is no more than the total number of outstanding reservation for that slot (see hereinbelow for more explanation). This number of entries is large enough to avoid blocking due to the lack of space in the reservation table. Each entry stores the requests that are to start in that slot.

[0049] The format of each entry in the list is Reservation-number, sub-resen>ation- number, #of slots, allocated-channet>. Whenever a new reservation <r, t_r, s,> is made, the reservation-number is set to r, the sub-reservation-number is set to 0, the reservation-starting- time is not stored, but the entry is stored in the list t_r - t_s (recall t_r > t_g), and number-of-slots is set to s_r. When a channel is allocated to this request, the channel-number-allocated is set.

[0050] Since the logical slot number advances automatically, the reservation lists are automatically renamed. Since we do not keep track of reservation list of logical slot numbers prior to to, the list for slot 0 is updated to carry forward all continuing requests. The process to carry out this task is described hereinbelow in more detail.

[0051] The table can either be maintained in the order of starting times or in the order of arrival of the AR requests. In the first case, it is easier to identify requests that need to be scheduled in the next time slot. In the latter case, all table entries are scanned to identify which requests need to be scheduled. In either case all table entries are updated. The way we choose is typically closer to the first way, as it not only identifies request starting in that slot but also makes updating easier. First we do not need to update the starting time as the relative slot number is automatically updated with the global slot counter. Therefore an implied sorted order offers this particular advantage. In some embodiments, we can also maintain table entries as a linked list. Each new entry is appended at the end of the list as it does not matter in what order channels are allocated, since all accepted requests wi ll be allocated a channel. Each time a request is completed, the request entry is dropped. Entries in the tables/lists are updated in every slot as described.

Channel-Status

[0052] For each channel, a status of channel is set to be free or in-use. If the channel is in-use, then additional information about the request, e.g., sub-request, etc., is also maintained. In some embodiments, this information can be kept in two lists. One list can be in an array form Channel-Status [M], where information about each channel, i.e.. in use or free, request and sub-request number being served on the channel, and when it will become free is stored. The last piece of information is redundant and is kept for monitoring purposes only. The second list can be a linked list of free channels, Free-Channels. When a channel is released, its number is added in the list. A Channel-Status array can also be updated as free. A channel allocation process picks up one of the free channels, removes it from Free-Channels, and then allocates it for communication and updates Channel-Status array appropriately.

Advance Reservation Requests

[0053] Requests can be of the following three types: (a) a simple request r asking for .v_r contiguous slots starting at slot t_r (b) a multiple slot request /·„, asking for m channels for

_Si .

'^r in contiguous slots starting at slot ^rm ; and (c) a non-contiguous request r„ asking for one channel for S ^TL slots starting at slot >> ^r n and finish before end slot 6 ' n. [0054] A simple request of type (a) will be handled in the way as described below under resource provisioning and resource allocation paragraphs. The request is accepted only i a slot can be made available to it from slot number t_r - l_g to slot number t_r - t_g + s_r - 1 .

[0055] The request of type (b) will be accepted only if m channels can be allocated to it from slot number t_r - t_g to slot number t_r - t_g + s_r - \ . Otherwise, the request is rejected. The control system checks for availability of m slots instead of one slot, as would be the case for a request of type (a). If the request is accepted, this request will be sub-divided into m sub- requests and inserted in the reservation list as such. The sub-reservation-number field is assigned values of 1 to m, respectively, to distinguish among them.

[0056] The request of type (c) can also be handled in the same way. except that the control system will consider slots from . n. to slot e ^r n and accept the request if and only

S

if it can find ' vzslots in that interval that are available. These slots can be selected in more than one way, such as by using the first available slots, using the least-used slots, or by using the last available slots. Search processes suitable for use in all of these cases are well known in the art, and therefore are not discussed here. After the slots that are to be used are determined, the request is sub-divided into multiple sub-requests. The sum of the slots used for all sub- requests equals T^'n. Each sub-request has a different starting slot number that corresponds to the available slot location identified in the previous step. To illustrate the process, suppose a request r calls for 5 slots starting with slot location 2 and completion before slot number 1 1 (i.e. the time frame of slot 2 to slot 10). Suppose the slot finding process identifies that slots 3,4,6,7, and 9 are free. Then this request is subdivided into three sub requests <r,3,2>, </·,6,2>, and <r,9, l > with sub-request numbers, l , 2, and 3, respectively. If less than 5 slots were available, then the request would have been rejected.

[0057] Notice that the process to handle all reservation therefore becomes equivalent to handling a request of type (a). Therefore in the following description, we assume that all requests are of type (a). RESOURCE PROVIS IONING PHASE

[0058] When an AR request <r, t_r, s_r > arrives, (or other requests are converted to such requests), SOCs (slot occupancy counters) starting from ' -9 to .9 '

|0059] are checked to see that each of them has at least one channel free in the RPP. If so, the request is accepted, is included in the request list t_r - t_g, where /_g is the global slot counter. Recall that this is the relative slot number. SOCs for slots ^•t_r ~t_g to '^' 9 ' ^7" are incremented by one (for type (b) requests SOCs will be updated for each sub-request or can be updated by value m in one shot while each sub-request is included in the reservations lists. If channels are not available, the request is rejected. Notice that channel-number-allocated is set to null as no channel is allocated to the request yet.

RESOURCE ALLOCATION (AND DEALLOCATION) PHASE

[0060] The channel allocation process is carried out for one slot at a time in the RAP.

Thus when the requests are being serviced in current time slot (in), the channel allocation process is carried out for slot (/_/), which will be renamed as to at the end of the slot. Al l other slots also are renumbered. Thus we describe the process only with respect to slot to and /_/ and the process is repeated after each slot.

[0061] There are three kinds of requests that need to be handled in the channel allocation/deallocation.

1 . Request that are continuing in slot /_/.

2. Request that are terminating after t₀.

3. Request that are starting in slot /_/.

[0062] The first two sets of request are in a reservation list of to. The third set of requests is in a reservation list of slot /_/. FIG. 5 shows one exemplary method using pseudo code suitable for performing channel allocation. The process will continue the on-going requests on the same channel, remove completing requests from the lists, and then allocate new channels to requests starting in the next slot. A free channel is guaranteed to be available as the number of requests accepted for any slot is no more than the number of channels (SOC < M). PERFORMANCE EVALUATION

[0063] We now turn to a description of simulation results comparing the SSAR method according to the invention to a prior art ASAR method. We used the following parameters: the arrival process was a Poisson process with an exponentially distributed holding time, the book- ahead times of the AR requests were considered to be either constant ( 1440 slots) and were uniformly distributed. The horizon was relatively large (equal to 2000 timeslots). We choose a mean value of 15 time-slots for our request duration. We then simulated 1 0⁶ AR requests and took the average of 20 runs. We used k precomputed paths between each source-destination pair. We evaluated our heuristics on the 14-node NSFnet.

[0064] FIG. 6A and FIG. 6B depict some initial results with k= l path with constant and uniformly distributed book-ahead times. FIG. 6A shows a graph average blocking probability plotted versus load (Erlangs) comparing SSAR according to the invention to the ASAR method of the prior art for constant book-ahead times. FIG. 6B shows a graph average blocking probability plotted versus load (Erlangs) comparing SSAR according to the invention to the ASAR method of the prior art for uniformly distributed book-ahead times. It can be concluded from these results that the SSAR system and method performs well in comparison to the prior art ASAR method. In fact with SSAR, capacity blocking is the only reason for blocking.

[0065] In this description, we addressed the problem of scheduler scalabil ity, signaling and response time by introducing a novel two-phase approach in solving the dynamic advance reservation routing, slot, and the wavelength assignment problem. By comparing SSAR methods according to the invention, to the ASAR method of the prior art, we conclude that SSAR process as described herein is better than the baseline heuristic. The SSAR method keeps the scheduler simple and avoids pre-allocation of bandwidth. The SSAR method according to the invention is optimal and therefore better than prior art methods for provisioning lightpaths for AR requests over WDM networks in terms of efficient scheduler state management, reduced signaling, faster response times to user requests in terms of whether requests were accepted or rejected, and centralized scheduler scalability at higher loads and for large networks. It is also contemplated that the inventive SSAR method can be extended to non-continuous advance reservation techniques. SSAR WITH TIME FLEXIB ILITY

[0066] Demands that specify a start time and duration are denoted STSD. In some embodiments, for STSD requests with flexibility, we can implement the resource provisioning phase (RPP) and the resource allocation phase (RAP) similar to the STSD requests with fixed time. The difference is that in the RPP, the centralized scheduler tries all possible starting times in the sliding window using a first-fit mechanism. If the request finds the necessary bandwidth, the RAP phase is called at the starting time of the request.

[0067] The SSAR method can be applied to several different kinds of communication requests as described hereinbelow in a system in which several parallel channels are set between possible sources and destinations. One such exemplar)' system is shown in FIG. 1 1 where channels are set up in a network, such as an optical network (i.e., by Finding the right paths in network). In this exemplary embodiment, each of the nodes can transmit on any channel (i.e., can use one or more channels), and a request is from one or more nodes to one or more destinations. Any node can act as a source or as a destination.

Unicast SSAR

[0068] FIG. 7 shows a conceptual illustration of a Unicast embodiment of a SSAR system and method according to the invention. In unicasl communication data is transmitted from a single source to a single destination. Our basic SSAR method supports provisioning and allocation of unicast advance reservation requests.

Multicast SSAR

[0069] FIG. 8 shows a conceptual illustration of a Multicast SSAR system and method according to the invention. Multicast is a communication paradigm in which data is transmitted from a source to a set of destinations. In this embodiment, the SSAR process is implemented for each tree from the source to all the destinations. The final communication tree (e.g. a light-tree) (route + wavelength + slots) is set up between the source and all of the multicast destinations. Anycast SSA

[0070] FIG. 9 shows a conceptual illustration of an Anycast embodiment of a SSAR system and method according to the invention. Anycast is a communication paradigm that can provide an intelligent selection of a destination node for distributed applications. Anycast refers to a transmission of data from a source to any one destination out of a set of candidate destinations. In this embodiment, the SSAR method is repeated from each source to candidate destination. The communication (e.g., light path) is set up between the source and the best destination.

Manycast SSAR

[0071] FIG. 10 shows a conceptual illustration of a Manycast SSAR system and method according to the invention. Manycasting is a more generic version (of Anycasting), which supports communication from a sender to any k out of m (k<m) candidate destinations where the candidate destination set, |D_c|=m, is a subset of nodes in the network. If we change the parameters of the manycast request, we can also perform unicast (k=m= l ). multicast (k=m> l ), and anycast (k= l <m). The difference between multicast and manycast is that in multicast, the destinations are specified ahead of time, whereas in manycast the destinations are chosen. This flexibility results in network resources being utilized efficiently. From an energy perspective, the energy consumption (in manycasting) can be lowered in the following ways: a source node can select the "best" destinations from the candidate destination set, thus using less transmission power. The choice of destination nodes selected can also be based on the energy of the source (renewable/non-renewable). In this context, we promote manycasting as an energy-efficient variation of multicasting.

[0072] Manycast is a communication paradigm in which data is transmitted from a source to a set of candidate destinations. In this embodiment, the SSAR process is implemented for each tree from the source to all the destinations. The final communication tree (e.g. the light-tree of an optical network) (route + wavelength + slots) is set up between the source and the all the multicast destinations. Peer-to-Peer (P2P) SSAR

[0073] In a P2P communication paradigm, one or more sources can transmit data to one or more destinations. A P2P request is from one (or more nodes) to one or more destinations. In this embodiment, the SSAR process is implemented for each tree from one or more sources to one or more destinations. The final communication tree (e.g. the light-tree or a light-trail of an optical network) (route + wavelength + slots) is set up connecting all the sources and destinations for a given connection request.

DEFINITIONS

[0074] CHANNEL: A channel as used herein refers to a data transmission media. One example of a channel is a single wavelength range of a wavelength division multiplexed (WDM) optical communication system. For example, a single fiber of a bundle of fibers in an optical communication system typically has a number of designated wavelength ranges, each wavelength range providing a unique channel as defined herein. A channel also includes a RF frequency (e.g. a RF carrier having some RF bandwidth) and a RF transmission having subcarriers, each subcarrier having a RF bandwidth.

[0075] PATH: A path includes a transmission path from a source to a destination

(generally a geographic source and destination). In an optical communication system, a path can include, for example, one continuous fiber, or any number of fibers including active and/or passive switching and/or another suitable signal splicing techniques. There can be multiple paths between a given source and destination. The paths can be substantially co-located (e.g. parallel fiber cables) or can run through completely different physical paths (e.g. optical fiber cables run through different cities).

[0076] Recording the results from an operation or data acquisition, such as for example, recording results of a particular data transmission scheduling method is understood to mean and is defined herein as writing output data in a non-transitory manner to a storage element, to a machine-readable storage medium, or to a storage device. Non-transitory machine-readable storage media that can be used in the invention include electronic, magnetic and/or optical storage media, such as magnetic floppy disks and hard disks; a DVD drive, a CD drive that in some embodiments can employ DVD disks, any of CD-ROM disks (i.e., read-only optical storage disks), CD-R disks (i.e., write-once, read-many optical storage disks), and CD- RW disks (i.e., rewriteable optical storage disks); and electronic storage media, such as RAM, ROM, EPROM, Compact Flash cards, PCMCIA cards, or alternatively SD or SDIO memory; and the electronic components (e.g., floppy disk drive, DVD drive, CD/CD-R/CD-RW drive, or Compact Flash/PCMCIA/SD adapter) that accommodate and read from and/or write to the storage media. Unless otherwise explicitly recited, any reference herein to "record" or "recording" is understood to refer to a non-transitory record or a non-transitory recording.

[0077] As is known to those of skill in the machine-readable storage media arts, new media and formats for data storage are continually being devised, and any convenient, commercially available storage medium and corresponding read/write device that may become available in the future is likely to be appropriate for use, especially i f it provides any of a greater storage capacity, a higher access speed, a smaller size, and a lower cost per bit of stored information. Well known older machine-readable media are also avai lable for use under certain conditions, such as punched paper tape or cards, magnetic recording on tape or wire, optical or magnetic reading of printed characters (e.g., OCR and magnetically encoded symbols) and machine-readable symbols such as one and two dimensional bar codes.

Recording data transmission scheduling data for later use (e.g., writing data transmission scheduling data to memory or to digital memory) can be performed to enable the use of the recorded information as output, as data for display to a user, or as data to be made avai lable for later use. Such digital memory elements or chips can be standalone memory devices, or can be incorporated within a device of interest. "Writing output data" or "writing data transmission scheduling data to memory" is defined herein as including writing transformed data to registers within a microcomputer.

[0078] "Microcomputer" is defined herein as synonymous with microprocessor, microcontroller, and digital signal processor ("DSP"). It is understood that memory used by the microcomputer, including for example instructions for data processing coded as "firmware" can reside in memory physically inside of a microcomputer chip or in memory external to the microcomputer or in a combination of internal and external memory. Similarly, analog signals can be digitized by a standalone analog to digital converter ("ADC") or one or more ADCs or multiplexed ADC channels can reside within a microcomputer package. It is also understood that field programmable array ("FPGA") chips or application specific integrated circuits ("ASIC") chips can perform microcomputer functions, either in hardware logic, software emulation of a microcomputer, or by a combination of the two. Apparatus having any of the inventive features described herein can operate entirely on one microcomputer or can include more than one microcomputer.

[0079] General purpose programmable computers useful for control ling

instrumentation, recording signals and analyzing signals or data according to the present description can be any of a personal computer (PC), a microprocessor based computer, a portable computer, or other type of processing device. The general purpose programmable computer typically comprises a central processing unit, a storage or memory unit that can record and read information and programs using machine-readable storage media, a communication terminal such as a wired communication device or a wireless communication device, an output device such as a display terminal, and an input device such as a keyboard. The display terminal can be a touch screen display, in which case it can function as both a display device and an input device. Different and/or additional input devices can be present such as a pointing device, such as a mouse or a joystick, and di fferent or additional output devices can be present such as an enunciator, for example a speaker, a second display, or a printer. The computer can run any one of a variety of operating systems, such as for example, any one of several versions of Windows, or of MacOS, or of UN IX, or of Linux.

Computational results obtained in the operation of the general purpose computer can be stored for later use, and/or can be displayed to a user. At the very least, each microprocessor-based general purpose computer has registers that store the results of each computational step within the microprocessor, which results are then commonly stored in cache memory for later use.

[0080] Many functions of electrical and electronic apparatus can be implemented in hardware (for example, hard-wired logic), in software (for example, logic encoded in a program operating on a general purpose processor), and in firmware (for example, logic encoded in a non-volatile memory that is invoked for operation on a processor as required). The present invention contemplates the substitution of one implementation of hardware, firmware and software for another implementation of the equivalent functionality using a different one of hardware, firmware and software. To the extent that an implementation can be represented mathematical ly by a transfer function, that is, a specified response is generated at an output terminal for a specific excitation applied to an input terminal of a "black box^" exhibiting the transfer function, any implementation of the transfer function, including any combination of hardware, firmware and software implementations of portions or segments of the transfer function, is contemplated herein, so long as at least some of the implementation is performed in hardware.

THEORETICAL DISCUSSION

[00811 Although the theoretical description given herein is thought to be correct, the operation of the devices described and claimed herein does not depend upon the accuracy or validity of the theoretical description. That is, later theoretical developments that may explain the observed results on a basis different from the theory presented herein will not detract from the inventions described herein.

[0082] Any patent, patent application, or publication identified in the specification is hereby incorporated by reference herein in its entirety. Any material, or portion thereof, that is said to be incorporated by reference herein, but which conflicts with existing definitions, statements, or other disclosure material explicitly set forth herein is only incorporated to the extent that no conflict arises between that incorporated material and the present disclosure material. In the event of a conflict, the conflict is to be resolved in favor of the present disclosure as the preferred disclosure.

[0083] While the present invention has been particularly shown and described with reference to the preferred mode as illustrated in the drawing, it will be understood by one skilled in the art that various changes in detail may be affected therein without departing from the spirit and scope of the invention as defined by the claims.

Claims

What is claimed is:

1. A method of scheduling data transmissions from a source to a destination, comprising the steps of: providing: a communication system having a number of channels and a number of paths, each of said channels having a plurality of designated time slots, and a bandwidth defined as said number of channels multiplied by said number of paths, and a bandwidth capacity defined as said bandwidth multiplied by said number of designated time slots; receiving two or more data transmission requests, each of said two or more data transmission requests designating a transmission of data from a source to a destination, each of said two or more data transmission requests including a requested start time TS of transmission and a requested number of time slots for said transmission of said data; provisioning said transmission of said data corresponding to each of said two or more data transmission requests via said communication bandwidth without designating a channel of said number of channels and without designating a path of said number of paths; receiving data corresponding to at least one of said two or more data transmission requests; waiting until a current time within a time interval t of an earliest requested start time TS of said two or more data transmission requests; allocating at said current time each of said two or more data transmission requests to a channel of said number of channels and to a path of said number of paths in a way which optimizes a use of said bandwidth capacity; transmitting said data corresponding to said at least one of said two or more data transmission requests that has been allocated on said allocated channel and said allocated path; and repeating said steps of waiting, allocating, and transmitting until each of said two or more data transmission requests that have been provisioned for a transmission of data is satisfied.

2. The method of scheduling data transmissions from a source to a destination of claim 1, wherein said step of provisioning said transmission comprises provisioning said transmission of said data during a request provisioning phase.

3. The method of scheduling data transmissions from a source to a destination of claim 1, wherein said step of allocating comprises allocating at least one of said two or more data transmission requests during a request allocation phase.

4. The method of scheduling data transmissions from a source to a destination of claim 1 , wherein said step of providing a communication bandwidth is performed using an optical communication network.

5. The method of scheduling data transmissions from a source to a destination of claim 4, wherein said step of providing an optical communication network is performed using an optical communication network having wavelength division multiplexed transmission capability.

6. A system for provisioning data transmission from a source to a destination, comprising: a communication system having a number of channels and a number of paths, each of said channels having a plurality of designated time slots, in which a communication bandwidth is defined as the product of said number of channels times said number of paths and a bandwidth capacity is defined as the product of said bandwidth times said number of designated time slots; and a processor having instructions provided on a machine readable medium, said processor configured to perform the following steps when said instructions are operative: determining said communication bandwidth and said bandwidth capacity; receiving two or more data transmission requests, each of said two or more data transmission requests designating a transmission of data from a source to a destination, each of said two or more data transmission requests including a requested start time TS of transmission and a requested number of time slots for said transmission of said data; provisioning said transmission of said data corresponding to each of said two or more data transmission requests via said communication bandwidth without designating a channel of said number of channels and without designating a path of said number of paths; receiving data corresponding to at least one of said two or more data transmission requests; waiting until a current time within a time interval t of an earliest requested start time TS of said two or more data transmission requests; allocating at said current time each of said two or more data transmission requests to a channel of said number of channels and to a path of said number of paths in a way which optimizes a use of said bandwidth capacity; transmitting said data corresponding to said at least one of said two or more data transmission requests that has been allocated on said allocated channel and said allocated path; and repeating said steps of waiting, allocating, and transmitting until each of said two or more data transmission requests that have been provisioned for a transmission of data is satisfied.