BANDWIDTH CALENDARING IN SDN

TECHNICAL FIELD The present invention relates to an apparatus and method for reserving resources over time and space in a communication network, and in particular to an apparatus and method for bandwidth calendaring in software-defined networking.

BACKGROUND Conventionally, carrier network operators lease their network resources to their customers through contractual long term reservations. To do so, the required bandwidth, the duration of the reservation and the price are agreed beforehand, which prejudicially renders this approach rather rigid and may result in a su boptimal use of the network resources.

Moreover, conventional distributed routing and traffic engineering (TE) mechanisms, such as constrained shortest path first (CSPF) and multiprotocol label switching (MPLS)-TE, have the disadvantage to be sub-optimal because each network node makes independent decisions based on a partial and outdated knowledge of the network state.

By contrast, the global network view available at a software-defined networking (SDN) controller enables the system administrator to optimally use the network resources, the SDN being a networking paradigm that decouples network control and forwarding functions. Contemporary SDN implementations support the bandwidth-on-demand (BoD) services, a new networking paradigm in which the enterprises dynamically adjust the requested bandwidth according to their needs. Thus, they have to pay only for the network resources being actually used. However, this introduces uncertainty from the network operator standpoint. To circumvent such an issue, existing BoD approaches, as disclosed, for example, in the documents WO2014169289 Al and US8363562 B2, consider the demands arising over time in an online fashion, i.e., one by one, thereby leading to a suboptimal use of the network resources. In particular, the document WO2014169289 Al proposes an architecture in which a final user can flexibly purchase a BoD by issuing requests by means of an application through desktop, cloud, smartphone or tablet. Upon receipt of a request, the BoD provider dynamically computes the optimal end-to-end path that best suits the user's needs. Then, it translates the computed optimal path into flow commands, which are dynamically pushed down toward the controller agents in order to provision the BoD network path in real-time so that the admission decision and the flow allocation are decided simultaneously.

In order to use the network resources more efficiently, solutions have been proposed based on monitoring the state of data connections, providing more capacity or opportunistically satisfying new requests. In particular, the document WO2014081766 Al provides a system adapted to monitor an existing communication tunnel between two devices, adapted to determine whether an additional bandwidth is required for the communication between the two devices, adapted to determine whether the provision of such an additional bandwidth would exceed the available bandwidth for the existing communication tunnel, and adapted to establish the additional bandwidth between two network devices. In the document WO2004095160 A2, the disclosed system enables an internet service provider to monitor its available bandwidth and to offer an excess bandwidth at varying rates to users with the aim of filling the backbone when unused. The decision as to whether to increase the bandwidth is then left to the final user, i.e., the customer, such that the customer needs may be not met even when enough network resources are available. Thus, although the two documents WO2014081766 Al and WO2004095160 A2 allow the data transfer of alive connections to be speeded up when the backbone is not completely used, they cannot however be used for bandwidth calendaring (BC) services, in which a specific traffic profile has to be accommodated.

Furthermore, the time dimension of the TE mechanism over SDN can be explicitly considered in, for example, the document US 20150264135 Al, in which the problem of an optimal allocation of current and future bandwidth resources is studied for an inter-DC traffic. The objective is to maximize the minimum fraction of each demand that is satisfied by its deadline. An online algorithm is devised in such a manner that it iteratively updates the multipath flow allocations based on the previously derived solution. However, such an approach is not directly applicable to cases, such as carrier networks, in which a single path usually has to be used by the flows and the network reconfiguration due to change in the flow path is not possible.

The documents CN102946443B and US9438508 Bl disclose methods as to decide whether to admit a demand in the future, when to schedule the data transfer and over which network paths. Both documents provide a calendar of time-varying demands to be scheduled in the future with the aim of optimizing data transfers using the available bandwidth collected from the network. However, the admission of the demand and the commitment of scheduling and routing decisions are

simultaneously achieved, thereby leading to a suboptimal use of the network resources.

SUMMARY

It is therefore an object of the present invention to provide an apparatus and method for reserving, in response to a request, resources over time and space in a communication network, by means of which the use of network resources over all known requests can be optimally achieved through the decomposition of the control of admission of the request and the actual resource reservation as to delay the time at which the actual resource reservation is committed.

The object is achieved by the features of the independent claims. Further embodiments of the invention are apparent from the dependent claims, the description and the figures.

According to a first aspect, the invention relates to an apparatus for reserving resources over time and space in a communication network. The apparatus comprises an admission control (AC) module adapted to control an admission of at least one request for an upcoming resource reservation over time and space by calculating an initial allocation of resources for each request and making a realtime final decision as to whether to admit or reject the at least one request based on the initial allocation of resources, a memory adapted to store, for each admitted request, an information about the resources initially allocated by the AC module, a calendar module adapted to build a calendar for the upcoming period based on each admitted request from the AC module and/or based on each resource allocation request admitted in advance through a day-ahead market, a resource allocation module adapted to receive the calendar of admitted requests, calculate a final allocation of resources for all the admitted requests in the calendar, update the information stored in the memory for all the admitted requests, and reserve the resources from the final allocation only for the upcoming admitted request amongst all the admitted requests in the calendar, and an interface adapted to communicate through a plurality of signals with at least one user at respective different times, the at least one user requesting the upcoming resource reservation over time and space through the at least one request, and wherein the upcoming admitted request is removed from the calendar after reserving the resources from the final allocation. By admitting early but committing later the requested resources, the decomposition of the admission control and the actual resource reservation can be carried out through the construction of the calendar. Thus, although the admission decisions are made in real time and the users, such as the end users and the applications, requesting the resource reservation are at once notified of the admission decisions, the actual reservation of the requested resources is postponed until a later time at which the requested resources will be indeed used. Moreover, the corresponding delay in the actual resource reservation with respect to the decision-making on admission allows to receive in the meantime some additional resource requests and hence to acquire more relevant resource information provided by these additional resource requests. Thus, although a request or demand has been admitted, the system has still the possibility to change its mind regarding the realization of the requested resources (e.g., path, scheduling). In this way, the use of the network resources can then be optimized. As regards the calendar, it can be constructed on the fly based on each resource allocation request being admitted by the AC module or well in advance through, for example, a day- ahead market in which the users explicitly announce their resource requests (e.g., their bandwidth requests) for the following day.

According to a first implementation of the apparatus according to the first aspect, the at least one user is forthwith notified of the final decision made by the AC module through a first signal amongst the plurality of signals.

Thereby, an adequate signaling can be obtained between the apparatus and the user requesting the resource reservation so that the user can be immediately informed of whether its request has been admitted or rejected.

According to a second implementation of the apparatus according to the first aspect or the first implementation of the first aspect, the at least one user is notified of the reserved resources for its upcoming admitted request through a second signal amongst the plurality of signals.

Thereby, an adequate signaling can be obtained between the apparatus and the user requesting the resource reservation so that the user can be informed in advance of, for example, the actual starting time of the request and its path to be used. According to a third implementation of the apparatus according to the first aspect or any one of the preceding implementations of the first aspect, the at least one user is notified to initiate a use of the reserved resources through a third signal amongst the plurality of signals.

Thereby, an adequate signaling can be obtained between the apparatus and the user requesting the resource reservation so that the user can be informed of the actual reservation related to its request.

According to a fourth implementation of the apparatus according to the first aspect or any one of the preceding implementations of the first aspect, the apparatus comprises a traffic prediction module adapted to derive an information about the residual capacity of the communication network.

Thereby, an information about traffic prediction can be rendered available.

According to a fifth implementation of the apparatus according to the fourth implementation of the first aspect, the apparatus comprises a network controller adapted to retrieve and store the information about the residual capacity of the communication network.

Thereby, the information about the traffic prediction, and in particular about the residual capacity of the communication network, can be hold over time.

According to a sixth implementation of the apparatus according to the fourth or fifth implementation of the first aspect, the AC module and the resource allocation module are each adapted to retrieve over time the information about the residual capacity of the communication network.

Thereby, the information about the traffic prediction, and in particular about the residual capacity of the communication network, can be used at any time by the AC module and the resource allocation module in order to optimize the calculation of their respective initial and final allocations of resources. According to a seventh implementation of the apparatus according to the first aspect or any one of the preceding implementations of the first aspect, the resource allocation module is a bandwidth calendar module comprising a scheduling module and a routing module.

Thereby, a bandwidth reservation can be performed by setting the starting time and the path of the upcoming admitted request.

The above object is also solved in accordance with a second aspect.

According to the second aspect, the invention relates to a method for reserving resources over time and space in a communication network. The method comprises the steps of controlling an admission of at least one request for an upcoming resource reservation over time and space by calculating an initial allocation of resources for each request and making a real-time final decision as to whether to admit or reject the at least one request based on the initial allocation of resources, storing, for each admitted request, an information about the resources initially allocated, building a calendar for the upcoming period based on each admitted request and/or based on each resource allocation request admitted in advance through a day-ahead market, receiving the calendar of admitted requests, calculating a final allocation of resources for all the admitted requests in the calendar, updating the stored information for all the admitted requests, reserving the resources from the final allocation only for the upcoming admitted request amongst all the admitted requests in the calendar, and communicating through a plurality of signals with at least one user at respective different times, the at least one user requesting the upcoming resource reservation over time and space through the at least one request, and wherein the upcoming admitted request is removed from the calendar after reserving the resources from the final allocation.

According to a first implementation of the method according to the second aspect, the method comprises the step of deriving an information about the residual capacity of the communication network. According to a second implementation of the method according to the first implementation of the second aspect, the step of retrieving and storing the information a bout the residual capacity of the communication network.

The above object is also solved in accordance with a third aspect.

According to the third aspect, the invention relates to a computer program comprising a program code for performing the method according to the second aspect or any one of the implementations of the second aspect when executed on a computer.

Thereby, the method can be performed in an automatic and repeatable manner.

The computer program can be performed by the above apparatus. The apparatus can be

programmably arranged to perform the computer program.

More specifically, it should be noted that the above apparatus may be implemented based on a discrete hardware circuitry with discrete hardware components, integrated chips or arrangements of chip modules, or based on a signal processing device or chip controlled by a software routine or program stored in a memory, written on a computer-readable medium or downloaded from a network such as the internet.

It shall further be understood that a preferred embodiment of the invention can also be any combination of the dependent claims or above embodiments with the respective independent claim.

These and other aspects of the invention will be apparent and elucidated with reference to the embodiments described hereinafter. BRIEF DESCRIPTION OF THE DRAWINGS

In the following detailed portion of the present disclosure, the invention will be explained in more detail with reference to the exemplary embodiments shown in the drawings, in which:

shows a schematic diagram depicting a bandwidth reservation request versus time in the case of (a): a flexible demand with a time-varying bandwidth and (b): a rigid deman with a time-varying bandwidth;

shows a schematic block diagram of an apparatus 100 for reserving resources over time and space in response to a request for an upcoming resource reservation according to an embodiment of the present invention;

shows a flow diagram for reserving resources over time and space in response to a request for an upcoming resource reservation according to an embodiment of the present invention;

shows a schematic diagram illustrating the decomposition of the control of the admission of a demand and the actual resource reservation according to an embodiment of the present invention;

Fig. 5 shows a schematic diagram illustrating the benefits of the proposed BC approach in the case of (b): a rigid/non-flexible bandwidth reservation and (c): a flexible bandwidth reservation with respect to (a): a conventional BoD approach, according to an embodiment of the present invention;

Fig. 6 shows a schematic block diagram of an apparatus 200 for reserving resources over time and space in response to a request for an upcoming resource reservation in the illustrative case of a carrier network scenario, according to an embodiment of the present invention; Fig. 7 shows a flow diagram for controlling an admission of a demand through the AC module

(Ml) in the illustrative case of a carrier network scenario, according to an embodiment of the present invention;

Fig. 8 shows a flow diagram for determining a starting time and a path for a demand through the bandwidth calendar (BWC) module (M4) in the illustrative case of a carrier network scenario, according to an embodiment of the present invention;

Fig. 9 shows a flow diagram for scheduling a demand through the scheduling module (M41) of the bandwidth calendar (BWC) module (M4) in the illustrative case of a carrier network scenario, according to an embodiment of the present invention;

Fig. 10 shows a flow diagram for routing a demand through the routing module (M42) of the bandwidth calendar (BWC) module (M4) in the illustrative case of a carrier network scenario, according to an embodiment of the present invention.

Identical reference signs are used for identical or at least functionally equivalent features.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

Referring to the bandwidth calendaring (BC) of Fig. 1, customers such as over-the-top (OTT) enterprises (e.g., Netflix) issue requests or demands through an application for future bandwidth reservations, which may be either flexible and time-varying, as depicted in Fig. 1(a) where the time- varying bandwidth reservation is scheduled to start at any time within a scheduling window, or rigid and time-varying, as depicted in Fig. 1(b) where the time-varying bandwidth reservation is scheduled to start and end at a respective fixed time. Then, the operator such as a telecom operator has to reply whether the demand should be admitted, and based on the collected information, it constructs a calendar and decides which path(s) should be used and when a demand should be scheduled within the scheduling window in the case of a flexible request. Referring to Fig. 1(b), the rigid demands can be generated by enterprises that, due to their internal communication processes and the typical diurnal nature of traffic, have time-varying bandwidth requirements. More specifically, their bandwidth reservation may be related, for example, to the broadcasting of a soccer match. In such a case, a large number of cameras is covering the event and all the captured data need to be forwarded to a distant editing room for post-processing and retransmission. To that extent, a bandwidth reservation of several hundreds of Mbps need to be made between the stadium premises and the editing room. However, during pre-game and post- game, the bandwidth requirements are much smaller with respect to the duration of the game since fewer cameras are used.

Referring to Fig. 1(a), numerous bandwidth-hungry tasks are delay-tolerant and hence flexible. Background nightly domain controller (DC) backups and synchronization of distributed databases are representative of such examples that involve bulky data transfers. Such non-real-time applications typically have the flexibility to be executed within a scheduling window as long as a deadline for the completion of the whole process has been met. Thus, the corresponding bandwidth reservations exhibit some inherent flexibility over time.

In the following embodiments, the present invention will be specifically described in the context of software-defined networks (SDN). It should be noted however that the context of the present invention can be extended to any stateful path computation element (PCE)-based architecture.

Fig. 2 shows a schematic block diagram of the proposed apparatus 100 for reserving resources over time and space in response to a request for an upcoming resource reservation according to an embodiment of the present invention.

As can be gathered therein, the proposed apparatus 100 comprises an admission control (AC) module (Ml), a memory (M2), a calendar module (M3), a resource allocation module (M4) and an interface (API).

At least one user (M0), such as an end user or an application, requests an upcoming resource reservation over time and space through, for example, a request or demand for a future bandwidth (step SI). The admission control (AC) module (Ml) receives each arising request, calculates an initial allocation of resources for each of them (step S2), and makes an individual real-time final decision as to whether to admit or reject the request based on the calculated initial allocation of resources (step S3). The at least one user (MO) is forthwith notified of the final decision by receiving a first control signal (Sgl) from the proposed apparatus 100 through the interface, e.g., a northbound applications programming interface (API). At the same time and in the case of an admitted request, the proposed apparatus 100 sends a first command signal (CI) towards the network routing devices through the interface, e.g., a southbound API, in order to esta blish a virtual communication tunnel (step S3). More specifically, the first command signal (CI) enables a configuration of the ingress-egress routers in order to support the establishment of the respective path for each admitted request.

For each admitted request, an information about the resources initially allocated by the AC module (Ml), for example, an information about the starting time and the path, is stored in the memory (M2) (step S4).

Each admitted request from the AC module (Ml) is provided to the calendar module (M3) in order to be added to a calendar, so that the calendar module (M3) is adapted to build the calendar for the upcoming period based on each admitted request from the AC module (Ml) and/or based on each resource allocation request admitted in advance through a day-ahead market (step S5). Thus, the present invention can construct a calendar on the fly and/or make use of a calendar being explicitly announced. At this process step, it should be noted that no resource reservation has yet been made.

The resource allocation module (M4) receives the calendar of the admitted requests and a milestone of the resource reservation process starts. The resource allocation module (M4) calculates a final allocation of resources for all the admitted requests in the calendar (step S6), updates the information stored in the memory (M2) for all the admitted requests and reserves the resources from the final allocation only for the upcoming admitted request amongst all the admitted requests in the calendar (step S7). The at least one user (M0) is notified of the reserved resources, e.g., the actual starting time and the path, for its upcoming admitted request by receiving a second control signal (Sg2) from the proposed apparatus 100 through the interface, e.g., the northbound applications programming interface (API). At the same time and in the case of an admitted request, the proposed apparatus 100 sends a second command signal (C2) towards the network routing devices through the interface, e.g., the southbound API, in order to achieve the actual bandwidth reservation only for the upcoming admitted request.

After reserving the resources from the final allocation, the upcoming admitted request is removed from the calendar (step S8).

Eventually, the at least one user (MO) is notified to initiate a use of the reserved resources, e.g., the actual starting time and the path, for its upcoming admitted request by receiving a third control signal (Sg3) from the proposed apparatus 100 through the interface, e.g., the northbound applications programming interface (API) and thereby the transmission starts (step S9).

Referring to the above and the specific steps SI to S9, Fig. 3 shows a flow diagram for reserving resources over time and space in response to a request (denoted therein as demand k) for an upcoming resource reservation.

Fig. 4 shows a schematic diagram illustrating the decomposition of the control of the admission of a demand or request and the actual resource reservation. As can be gathered therefrom, a plurality of demands (D1-D4) are sequentially admitted (as denoted by A1-A4) at a respective time (T1-T4), whereas the demand D5 is refused (as denoted by R5) at a later time (T5). After its admission (Al) at Tl, the necessary resources for demand Dl are not immediately reserved. A side benefit is that the user (M0) has still the opportunity to modify its demand prior to reaching the start of transmission of the demand Dl. However, the main advantage is that by postponing the actual resource reservation, the problem of resource allocation for Dl, D2 and D3 can be jointly solved during the corresponding timeframe by considering the joint resource requirements from the subsequent demands D2 and D3. The demand Dl is removed from the calendar after calculating its final resource allocation and the final resource allocation of the subsequent demands D2 and D3, and after reserving its actual resources. The same applies to the next demand D2 that is removed from the calendar after calculating its final resource allocation and the final resource allocation of the subsequent demands D3 and D4, and after reserving its actual resources. The proposed apparatus 100 can further comprise a traffic prediction module (M5) and a network controller (M6).

The traffic prediction module (M5) is adapted to derive an information about the residual capacity of the communication network. In general, the traffic can be divided in two categories: a traffic that is a priori known and hence amenable to calendaring, and another type of traffic such as (a): on the fly traffic and/or (b): long-term traffic demands arriving at the network through the traditional reservation channels. The traffic prediction module (M5) focuses on the second category of traffic. Long-term leases operate in much larger time-scales than the calendar period (e.g., in a time-scale of one day through the day-ahead market) examined in the present invention, so that we consider that their routing is known and can be subtracted from the capacity of the network, thereby forming the residual capacity. On the other hand, on the fly BoD traffic must be estimated and also subtracted from the residual capacity of the graph. To achieve this purpose of predicting on the fly traffic, several forecasting techniques can be utilized as these found, for example, in: Will E. Leland et al., "On the self-similar nature of Ethernet traffic", ACM SIGCOMM Computer Communication Review, Vol. 23, No. 4, ACM, 1993. Moreover, the traffic prediction module (M5) can support both the short and long term traffic prediction using time series models based, for example, on the Autoregressive integrated moving average (ARIMA) and the neural networks.

The network controller (M6) is adapted to retrieve and store the information about the residual capacity of the communication network that is derived from the traffic prediction module (M5). Monitoring protocols can then be used by the present invention in order to keep track of the residual capacity. For example, the protocol OpenFlow or the Path Computation Element (PCE)

Communication Protocol (PCEP) can be used by the network controller (M6) to retrieve, periodically or occasionally, statistics about the utilization of links. Alternatively, traditional protocols like the internet protocol flow information export (IPFIX) protocol could be used by the network controller (M6) for this purpose.

The AC module (Ml) and the resource allocation module (M4) are each adapted to retrieve over time the information about the residual capacity of the communication network that is derived from the traffic prediction module (M5) and stored in the network controller (M6), in order to optimize the calculation of their respective initial and final allocations of resources. By jointly designing the admission process, the calendar construction and the actual resource reservation through the resource allocation module (M4) and their interactions, the present invention ensures a fast admission response to the requests, an optimized resource allocation without any network reconfiguration and a support for time-varying bandwidth reservations.

Fig. 5 shows a schematic diagram illustrating the benefits of the proposed BC approach in the case of (b): a rigid or non-flexible bandwidth reservation and (c): a flexible bandwidth reservation with respect to (a): a conventional BoD approach. Existing BoD approaches consider the demands arising over time in an online fashion and perform the admission control and the resource reservation at the same time unlike the proposed BC approach that decomposes the admission control and the resource reservation through the construction of a calendar. In Fig. 5, the arrival times of the demands 1 and 2 are respectively denoted tai and ta ₂ , and at each link between the nodes A, B and C forming the paths (A->B), (B->C) and (A->C) corresponds a cost denoted by the letter c. The bandwidth requirement (d ² ) of the demand 2 is assumed to be equal to twice the bandwidth requirement (d ¹ ) of the demand 1 as to verify the relationship: d ² =2d ¹ .

Conventional traffic requests are usually rigid and long-term leases and are routed offline via multiprotocol label switching traffic engineering (MPLS-TE).

On top of this traffic, BoD services allocate network resources in an online fashion. At each time instance, a single demand is considered and the optimal path to reach the node C starting from the node A is myopically selected. Thus, as depicted in Fig. 5a), the low cost path (i.e., A->C) will be allocated to the first demand d ¹ , whereas the demand d ² , which is the bigger demand in term of bandwidth requirement, will be given the costly path (i.e., A->B and B->C). The total cost will be then equal to: cd ² (A->B) + cd ² (B->C) + cd ¹ (A->C) = 2cd ^x (A->B) + 2cd ^x (B->C) + cd ¹ (A->C) = 5cd\ namely equal to five times the cost (c) of the demand 1.

By contrast, the BC approach jointly considers and optimizes the path allocations for all the calendared demands. Thus, it enables the network operator to optimally utilize the network over time. As depicted in Fig. 5b), the low cost path (i.e., A->C) will be allocated to the demand d ² , which is the bigger demand in term of bandwidth requirement, whereas the demand d ¹ will be given the costly path (i.e., A->B and B->C). The total cost will be then equal to: cd ¹ (A->B) + cd ¹ (B->C) + cd ² (A- ) = cd ¹ (A->B) + cd ¹ (B->C) + Zed ¹ (A->C) = 4cd ¹ , namely equal to four times the cost of the demand

In addition, the flexibility of demands over time can be exploited by the network operator to further improve the utilization of the network. Fig. 5c) depicts the allocation under the assumption that the demand d ² can be postponed until later with respect to the time ta2. In that case, both demands d ¹ and d ² can be accommodated in the low cost path (i.e., A->C). The total cost will be then equal to: cd ¹ (A->C) + cd ² (A->C) = cd ¹ (A->C) + 2cd ^x (A->C) = 3cd\ namely equal to thrice the cost of the demand 1. In return, the operator can reward the customers that admit such a time flexibility by offering lower prices for the service provisioning. At the same time, by supporting time-varying bandwidth reservations, the reserved bandwidth can be effectively reduced in the network. This allows to facilitate a better packing of demands and to reduce the total cost for the customers since they only pay for the resources they will actually use.

Fig. 6 shows a schematic block diagram of an apparatus 200 for reserving resources over time and space in response to a request for an upcoming resource reservation in the illustrative case of a carrier network scenario, according to an embodiment of the present invention.

Even though the bandwidth calendaring (BC) has successfully leveraged the flexibility of demands in data center (DC) interconnection networks by getting significant cost savings, the BC targeted towards carrier networks nevertheless introduces some additional flow requirements related in particular to single-path routing and limited reconfigurations. Indeed, contrary to DC interconnection scenarios where multipath routing is possible, the carrier networks use routing protocols, such as intermediate system to intermediate system ( IS- IS) and open shortest path first (OSPF), in order to create a single path per demand based on live metrics. Moreover, in a carrier network scenario, the dynamic reconfiguration of the network is a challenging and time-consuming process by entailing the solution of a large-scale problem and the update of all the involved network devices, and may also interrupt or degrade the performance of ongoing data transmissions, Thus, changing the path of a flow during an operation may lead to an undesirable reduction of quality, so that the flows are not reconfigured on the fly in most carrier networks unless a failure event occurs. In addition, while the goal in DC scenarios is to transfer data before a deadline, the carrier networks deal with bandwidth reservations of specific profile and tight performance requirements. Thus, an important amount of traffic cannot be delayed. As flexible and rigid (or non-flexible) traffics coexist, the network operator must jointly consider them in the resource allocation process.

In this context, for such a carrier network scenario, any knowledge about the future can be used to optimize the resource allocations over time. To that extent, a calendar of future demands may be constructed well in advance, e.g., through a day-ahead market in which customers explicitly announce their bandwidth requests for the following day. Alternatively, the calendar may be constructed on the fly through the admission control decisions. As can be gathered from Fig. 6, the apparatus 200 comprises an admission control (AC) module (Ml), a memory (M2), a calendar module (M3) and a bandwidth calendar (BWC) module (M4) adapted to serve a bandwidth calendaring service through a scheduling module (M41) and a routing module (M42). The apparatus 200 is adapted to decompose in space and time the admission control procedure from the scheduling and routing procedures. When demands or requests for bandwidth reservation arise, an admission decision needs to be made by the AC module (Ml), which can further retrieve over time any traffic prediction information about the residual capacity. Then, the AC module (Ml) provides, for each admitted demand, an information about an initial allocation of bandwidth towards the memory (M2) and the calendar module (M3).

Fig. 7 shows a flow diagram for controlling an admission of a demand through the AC module (Ml) in the illustrative case of a carrier network scenario according to an embodiment of the present invention.

At the step Input, the residual capacity over time is initialized as the capacity of the links for all time instances or as the residual capacity over time provided by the previous call of the bandwidth calendaring module. The demand k is described as a tuplet defined by: <source (s ^k ), destination (t ^k ), earliest starting time (a ^k ), latest finish time ( ^k ), duration (q ^k ), traffic (vector of length duration) (d )>.

At the step S1.0, the AC module (Ml) initializes the feasible cost matrix. Each element of this time- expanded matrix is equal to the cost of the edge, if this edge has enough capacity to serve the demand for its whole duration, and the time instance δ indicates the candidate starting time. At the step Sl. l, for the candidate starting time δ, the module uses the Dijkstra algorithm to calculate the minimum cost path a nd the candidate starting time δ is increased by one.

At the step SI.2, the module checks whether all possible starting times have been considered. If not the case, the AC module (M l) returns to step Sl. l, otherwise it goes to next step SI.3.

At the step SI.3, the AC module (M l) finds the candidate starting time δ with the minimum path cost.

At the step SI.4, the AC module (M l) checks whether the cost of the minimum cost path is finite, i.e., whether there is at least one path that has enough capacity to serve the dema nd k for its whole du ration. If not the case, the AC module (M l) sends a negative ad mission control signal to the demand k, otherwise it goes to next step SI.5.

At the step SI.5, the AC module (M l) updates the residual capacity over time graph by removing the traffic for this demand k from the links and time instances during which this demand k is active, and sends a positive admission control signal to the demand k.

Fig. 8 shows a flow d iagra m for determining a starting time a nd a path for a demand through the bandwidth calendar (BWC) module (M4) in the illustrative case of a carrier network scenario, according to an embodiment of the present invention.

Here, the BC problem is further decomposed into a scheduling process and a routing process. The former selects the time from which a demand should be served, a nd the latter selects the path that should be used to route a nd serve the demand.

At the step input, the residual capacity over time is initialized as the capacity of the links for a ll time instances or as the resid ual capacity over time provided by the previous call of the bandwidth calendaring module. The set of demands K includes all the demands that have been admitted after the previous call of the BWC module (M4).

At the step S2.0, an iterator and a dummy cost value are initialized.

At the step S2.1, the BWC module (M4) calls the scheduling module (M41), which orders the demands and fixes their starting time.

At the step S2.2, the BWC module (M4) calls the routing module (M42), which defines the path over which each demand is routed.

At the step S2.3, the BWC module (M4) calculates the overall cost of the allocations.

At the step S2.4, if the cost is less than the previous iteration, the BWC module (M4) increases the iterator and returns to step S2.1, otherwise it goes to next step S2.5.

At the step S2.5, the BWC module (M4) applies the scheduling and routing decisions of the previous iteration, updates the residual capacity over time as affected by these decisions, and informs the admitted demands about their decided starting times and, if needed, about their paths.

Fig. 9 shows a flow diagram for scheduling a demand through the scheduling module (M41) of the bandwidth calendar (BWC) module (M4) in the illustrative case of a carrier network scenario, according to an embodiment of the present invention.

At the step Input, the scheduling module (M41) takes as input the residual capacity over time matrix, the set of the demands K and the paths for each demand in the set, if any. At the step S3.0, the scheduling module (M41) sorts the demands in a descending order of their total volume over the scheduling window. It initializes an iterator over the demands and the load of each link over time is set to zero.

At the step S3.1, the scheduling module (M41) selects as starting time for the demand under consideration the candidate starting time that minimizes the maximum load over the links over which the demand is routed, and the time instances during which the demand will be active.

Subsequently, the module updates the load on these links and the time instances by adding the fraction of capacity used by the demand under consideration. It also increases the iterator of the demands.

At the step S3.2, the scheduling module (M41) checks whether all the demands have been scheduled. If not the case, the scheduling module (M41) returns to step S3.1, otherwise it goes to step Output.

At the step Output, the scheduling module (M41) returns the ordered set of demands and the updated starting times for each demand.

Fig. 10 shows a flow diagram for routing a demand through the routing module (M42) of the bandwidth calendar (BWC) module (M4) in the illustrative case of a carrier network scenario, according to an embodiment of the present invention.

At the step Input, the routing module (M42) takes as input the residual capacity over time, the ordered set of demands and the starting time decided by the scheduling module (M41).

At the step S4.0, the routing module (M42) initializes an iterator over the demands and the local copy of the residual capacity over time.

At the step S4.1, the AC module (Ml) initializes the feasible cost matrix. Each element of this time- expanded matrix is equal to the cost of the edge, if this edge has enough capacity to serve the demand for its whole duration. The routing module (M42) computes the minimum cost path for this demand using the Dijkstra algorithm on the feasible cost matrix. The routing module (M42) updates the local copy of the residual capacity over time and increases the iterator.

At the step S4.2, the routing module (M42) checks whether all the demands have been examined. If not the case, it returns to step S4.2, otherwise it terminates.

In summary, the present invention relates to an apparatus and method for reserving resources over time and space in a communication network. The admission of at least one request for an upcoming resource reservation is controlled through a calculation of a respective initial allocation of resources and a real-time final decision to admit or reject the at least one request based on the initial allocation of resources. An information about the resources initially allocated is stored and a calendar for the upcoming period is then built based on each request admitted on the fly and/or in advance through a day-ahead market. A final allocation of resources is calculated for all the admitted requests in the calendar and the stored information is updated for all the admitted requests. Eventually, the resources from the final allocation are reserved but only for the upcoming admitted request, which is afterwards removed from the calendar.

While the invention has been illustrated and described in detail in the drawings and the foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive. The invention is not limited to the disclosed embodiments. From reading the present disclosure, other modifications will be apparent to a person skilled in the art. Such modifications may involve other features, which are already known in the art and may be used instead of or in addition to features already described herein.

The invention has been described in conjunction with various embodiments herein. However, other variations to the disclosed embodiments can be understood and effected by those skilled in the art in practicing the claimed invention, from a study of the drawings, the disclosure and the appended claims. In the claims, the word "comprising" does not exclude other elements or steps, and the indefinite article "a" or "an" does not exclude a plurality. A single processor or other unit may fulfill the functions of several items recited in the claims. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage. A computer program may be stored/distributed on a suitable medium, such as an optical storage medium or a solid-state medium supplied together with or as part of other hardware, but may also be distributed in other forms, such as via the Internet or other wired or wireless telecommunication systems.

Although the present invention has been described with reference to specific features and embodiments thereof, it is evident that various modifications and combinations can be made thereto without departing from the spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded simply as an illustration of the invention as defined by the appended claims, and are contemplated to cover any and all modifications, variations, combinations or equivalents that fall within the scope of the present invention.