Subject: [Actn] virtual network mapping/embedding (VNM/VNE) problem

From: Leeyoung <[email-masked]>
Date: Tue, 17 Dec 2013 16:34:19 +0000

Related to the ACTN work, there has been active research termed "virtual network mapping/embedding (VNM/VNE)":

Here's some pointer to key papers:

http://www-bcf.usc.edu/~minlanyu/writeup/CCR08.pdf (VNE with path split and path migration)
http://nsm1.cs.uwaterloo.ca/rboutaba/Papers/Conferences/2010/Muntasir10.pdf (survivable VNE)
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5616527 (Resource Efficient VNE)

The focus of ACTN perhaps does not have a direct bearing with these papers as they are concerned about the VNM/VNE algorithms; however, these bring some key issues and constraints for virtual network path computation. These issues and constraints should be of interest of the ACTN work that may impact on the design, information models and interface/protocol extensions (if necessary).  Some of the issues such as efficiency of algorithm are perhaps better fit to SDN RG,  some of key issues and constraints for virtual network path computation related to VNM/VNE are as follows:

-   Request Processing
This is concerned about whether a set of client requests for VN creation can be dealt with simultaneously or not. This depends on the nature of applications the client support. If the client does not require real-time instantiation of VN creation, the computation engine can process a set of VN creation requests simultaneously to improve network efficiency.

-   Types of Network Resources
When client makes a VN creation request to the substrate network, what kind of network resources is consumed is of concern of both the client and network providers. It depends on the application. For transport network virtualization, the network resource consumed by the client is primarily network bandwidth that the paths would occupy on the physical link. However, there may be other resource types such as CPU and memory that need to be considered for certain applications. These resource types are a part of the client's VN request.

-   Accuracy of Network Resource Representation
As the underlying transport network in itself may consists of layered structure, it is a challenge how to represent these underlying physical network resources and topology into a form that can be reliably used by the computation engine that assigns the client requests into the physical network resource and topology.

-   Resource Efficiency
Related to the accuracy of network resource representation is resource efficiency. As a set of independent client VN is created and mapped onto physical network resources, the overall network resource utilization is of the primary concern of the infrastructure provider.

-   Guarantee of Client Isolation
While network resource sharing across a set of clients for efficient utilization is important aspect of network virtualization, client isolation has to be guaranteed. Admissions of new client requests or any changes of other existing clients' VNs must not affect any particular client in terms of resource guarantee, security constraints, and other performance constraints.

-   Computing Time
Depending on the nature of applications, how quickly a VN is instantiated from the time of request is an important factor. For dynamic applications that require instantaneous VN creation, the computation model/algorithm should support this constraint.

-   Admission Control
To coordinate the request process of multiple clients, an admission control will help maximize an overall efficiency.

-   Path Constraints
There may be some factors of path constraints that can affect the overall efficiency. Path Split can lower VN request blocking if the underlying network can support such capability. Packet-based TE network can support path split while circuit-based transport may have a limitation.  Path migration is a technique that allows changes of nodes or links assignment of the established paths in an effort to accommodate new requests which would not be accepted without path migration. This can improve overall efficiency, yet additional care needs to be applied to avoid any adverse impacts associated with changing the existing paths.
Re-optimization is a global process to re-shuffle all existing path assignment to minimize network resource fragmentation. Again, an extra care needs to be applied for re-optimization.

---

From: Daniele Ceccarelli <[email-masked]>
Date: Fri, 20 Dec 2013 10:30:17 +0000

Hi Young,

Thanks for the pointers and the list of issues.

Please find in line some loud thinking from my side.

BR
Daniele

From: ACTN [mailto:[email-masked]] On Behalf Of Leeyoung
Sent: martedì 17 dicembre 2013 17:34
To: [email-masked]
Cc: [email-masked]
Subject: [Actn] virtual network mapping/embedding (VNM/VNE) problem

-   Request Processing
This is concerned about whether a set of client requests for VN creation can be dealt with simultaneously or not. This depends on the nature of applications the client support. If the client does not require real-time instantiation of VN creation, the computation engine can process a set of VN creation requests simultaneously to improve network efficiency.
[[DC]] I think here we can assume that VN creation requests are non real time. Instantiation of services and bandwidth might be real time (and hence concurrency needs to be managed) but I would say this is not the case of VN creation.

-   Types of Network Resources
When client makes a VN creation request to the substrate network, what kind of network resources is consumed is of concern of both the client and network providers. It depends on the application. For transport network virtualization, the network resource consumed by the client is primarily network bandwidth that the paths would occupy on the physical link. However, there may be other resource types such as CPU and memory that need to be considered for certain applications. These resource types are a part of the client's VN request.
[[DC]] Here the issue is thorny. The point is: a given resource is dedicated to a given VN or shared among different ones? We should start considering network resources partitioning issues...

[[DC]] Damnly true

-   Resource Efficiency
Related to the accuracy of network resource representation is resource efficiency. As a set of independent client VN is created and mapped onto physical network resources, the overall network resource utilization is of the primary concern of the infrastructure provider.
[[DC]] This issue is pretty much linked to the one above (types of network resources)

-   Guarantee of Client Isolation
While network resource sharing across a set of clients for efficient utilization is important aspect of network virtualization, client isolation has to be guaranteed. Admissions of new client requests or any changes of other existing clients' VNs must not affect any particular client in terms of resource guarantee, security constraints, and other performance constraints.
[[DC]] Again linked to issues above. If network resources are dedicated to each VN, this is true, but if they (or part of them) are shared, the instantiation of a service from a given client would impact the VN seen by others. On the other side, aspects like security o performances should not be impacted in any of the two cases.

-   Computing Time
Depending on the nature of applications, how quickly a VN is instantiated from the time of request is an important factor. For dynamic applications that require instantaneous VN creation, the computation model/algorithm should support this constraint.
[[DC]] I would say that timing constraints need to be met for service provisioning (i.e. upon client requests on a given VN) but I think VN instantiation could be also a non real time procedure. I might be wrong...are there use cases for real time and timing constrained VN creation requrests?

-   Admission Control
To coordinate the request process of multiple clients, an admission control will help maximize an overall efficiency.
[[DC]] Yes. To understand where is the best place to do that. Cline control? VNC?

-   Path Constraints
There may be some factors of path constraints that can affect the overall efficiency. Path Split can lower VN request blocking if the underlying network can support such capability. Packet-based TE network can support path split while circuit-based transport may have a limitation.  Path migration is a technique that allows changes of nodes or links assignment of the established paths in an effort to accommodate new requests which would not be accepted without path migration. This can improve overall efficiency, yet additional care needs to be applied to avoid any adverse impacts associated with changing the existing paths.
Re-optimization is a global process to re-shuffle all existing path assignment to minimize network resource fragmentation. Again, an extra care needs to be applied for re-optimization.
[[DC]] True. With path constraints I think we should include something more. When a client needs to setup a service/LSP there might be TE constraints associated to the request. Whan the VN needs to include is not only reachability information but in many cases is should be TE-reachability information. In this case we could leverage on the overlay work being done e.g. in CCAMP and in (http://tools.ietf.org/html/draft-farrel-interconnected-te-info-exchange-02).

---

From: Leeyoung <[email-masked]>
Date: Fri, 20 Dec 2013 19:11:59 +0000

Hi Daniele,

Thanks for your feedback and comments. Please see inline for my reply.

Thanks.
Young

From: Daniele Ceccarelli [mailto:[email-masked]]
Sent: Friday, December 20, 2013 4:30 AM
To: Leeyoung; [email-masked]
Cc: [email-masked]
Subject: RE: [Actn] virtual network mapping/embedding (VNM/VNE) problem

Hi Young,

BR
Daniele

From: ACTN [mailto:[email-masked]] On Behalf Of Leeyoung
Sent: martedì 17 dicembre 2013 17:34
To: [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>
Subject: [Actn] virtual network mapping/embedding (VNM/VNE) problem

-   Request Processing

YOUNG>> Good point.  I was loose on the term 'VN creation".  There are certainly negotiation aspects of VN creation which can be viewed as non-real time as the client endpoints need to be negotiated with network provider(s) before service creation. Yes, in that sense, I agree with you. Here what I meant to say was when there are multiple service requests  to setup virtual connections that need not be instantiated real-time, (in other words, if some request can be queued for a delay scheduling), then a batch processing of multiple requests would be more optimal in general from a network efficiency perspective than sequential processing.

YOUNG>>  A given resource is "virtually" dedicated to a particular client; yet this does not mean a particular client occupies a particular port (say ODU port 1 vs 2).  As long as resource is guaranteed for use to the client, it is fine for the Working Path at least; however for 1:N kind of protection case, there is a level of sharing backup path resource for multiple clients.

-   Resource Efficiency

YOUNG>> Yes.

YOUNG>> Agree.  So I guess we need to be clear on resource partitioning and sharing issue clearly --- I think some application/client requires a hard dedicated resource while for some others it is fluid.

-   Computing Time

YOUNG>>  Again here what I meant was service request. I need to be clear on the terminology.  If we were to define VN creation as the process of negotiation (similar to SLA negotiation), the initial VN creation is always off-line (static and non-real time). Once the initial VN creation negotiation is done, then there might be cases where VN can be re-negotiated on the fly (e.g., changing some b/w or service objectives, or some physical failures such as fiber cut). But this is not VN creation; we need to distinguish this from VN re-negotiation.
-   Admission Control
To coordinate the request process of multiple clients, an admission control will help maximize an overall efficiency.
[[DC]] Yes. To understand where is the best place to do that. Cline control? VNC?

YOUNG>> As there are many clients that the VNC needs to support, I assume VNC has to have admission control module at the least. Client Controller, however, may have its own admission control for supporting multiple applications. We need to recognize a recursive client-server relationship. As long as controller is a server controller of any sort, then admission control function would help to coordinate its clients.

-   Path Constraints

YOUNG>> Yes, if we include non-TE underlying transport as part of the ACTN scope, then  the TE-reacheability needs to be known/advertised by the server network to clients as 'capability' attribute.

---

From: Diego Caviglia <[email-masked]>
Date: Mon, 23 Dec 2013 08:01:48 +0000

Hi all some more thought with some cleaning

BR and Season greetings!

D

-   Request Processing

YOUNG>> Good point.  I was loose on the term 'VN creation".  There are certainly negotiation aspects of VN creation which can be viewed as non-real time as the client endpoints need to be negotiated with network provider(s) before service creation. Yes, in that sense, I agree with you. Here what I meant to say was when there are multiple service requests  to setup virtual connections that need not be instantiated real-time, (in other words, if some request can be queued for a delay scheduling), then a batch processing of multiple requests would be more optimal in general from a network efficiency perspective than sequential processing.
[DC] yes and this is one of the biggest advantage of a centralized approach versus a distributed one, that is the possibility to compute the optimal solution of a bunch of requests

YOUNG>>  A given resource is "virtually" dedicated to a particular client; yet this does not mean a particular client occupies a particular port (say ODU port 1 vs 2).  As long as resource is guaranteed for use to the client, it is fine for the Working Path at least; however for 1:N kind of protection case, there is a level of sharing backup path resource for multiple clients.
[DC] well at least tributary port can't be virtual I need to nail it to a physical numbering to physically connect the HW, for the rest I agree.

-   Accuracy of Network Resource Representation
As the underlying transport network in itself may consists of layered structure, it is a challenge how to represent these underlying physical network resources and topology into a form that can be reliably used by the computation engine that assigns the client requests into the physical network resource and topology.
[[DC]] Damnly true
[DC] I vote for a KISS approach :)

-   Resource Efficiency

YOUNG>> Yes.

YOUNG>> Agree.  So I guess we need to be clear on resource partitioning and sharing issue clearly --- I think some application/client requires a hard dedicated resource while for some others it is fluid.
[DC] yes and this will give to the carriers the possibility to differentiate their service offering, do you want guaranteed bandwidth in case of multiple failures? Then you have to pay more.

-   Computing Time

-   Path Constraints

---

From: Fatai Zhang <[email-masked]>
Date: Mon, 23 Dec 2013 09:14:41 +0000

Open my eyes to look for Diego, but see another [DC], :)

Merry Charismas: My major comment, :)

Best Regards

Fatai

From: sdn [mailto:[email-masked]] On Behalf Of Diego Caviglia
Sent: Monday, December 23, 2013 4:02 PM
To: Leeyoung; Daniele Ceccarelli; [email-masked]
Cc: [email-masked]
Subject: Re: [Sdn] [Actn] virtual network mapping/embedding (VNM/VNE) problem

BR and Season greetings!

D

-   Request Processing

-   Resource Efficiency

YOUNG>> Yes.

-   Computing Time

-   Path Constraints

---

From: "Zhangxian (Xian)" <[email-masked]>
Date: Tue, 31 Dec 2013 09:01:37 +0000

Hi all,

   Some further thoughts on some of the issues.

   BTW, if anyone is interested to see the status quo of VNE research, the following might be a good starting point:

http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/meer/publications/pdf/Fischer2013a.pdf

Happy new year,

Xian

Sent: 2013年12月23日 16:02

BR and Season greetings!

D

-   Request Processing

YOUNG>> Good point.  I was loose on the term ‘VN creation”.  There are certainly negotiation aspects of VN creation which can be viewed as non-real time as the client endpoints need to be negotiated with network provider(s) before service creation. Yes, in that sense, I agree with you. Here what I meant to say was when there are multiple service requests  to setup virtual connections that need not be instantiated real-time, (in other words, if some request can be queued for a delay scheduling), then a batch processing of multiple requests would be more optimal in general from a network efficiency perspective than sequential processing.
[DC] yes and this is one of the biggest advantage of a centralized approach versus a distributed one, that is the possibility to compute the optimal solution of a bunch of requests

[Xian] I think we have a pretty understanding of the issue and as I understand, the points related to ACTN would include at least (1) what information needs to be passed from client to virtual network provider?; (2) what constraints  the client can accept (time might be a constraints).  If there is more, please amend.

-   Types of Network Resources
When client makes a VN creation request to the substrate network, what kind of network resources is consumed is of concern of both the client and network providers. It depends on the application. For transport network virtualization, the network resource consumed by the client is primarily network bandwidth that the paths would occupy on the physical link. However, there may be other resource types such as CPU and memory that need to be considered for certain applications. These resource types are a part of the client’s VN request.
[[DC]] Here the issue is thorny. The point is: a given resource is dedicated to a given VN or shared among different ones? We should start considering network resources partitioning issues…

YOUNG>>  A given resource is “virtually” dedicated to a particular client; yet this does not mean a particular client occupies a particular port (say ODU port 1 vs 2).  As long as resource is guaranteed for use to the client, it is fine for the Working Path at least; however for 1:N kind of protection case, there is a level of sharing backup path resource for multiple clients.
[DC] well at least tributary port can’t be virtual I need to nail it to a physical numbering to physically connect the HW, for the rest I agree.

[Xian] I think Young meant the physical resource can be shared by multiple clients, probably by assigning the same physical numbering to the different clients. The point that worth noting is that whether this kind of sharing can make sure no conflict would arise or if so, whether it is acceptable.

-   Accuracy of Network Resource Representation
As the underlying transport network in itself may consists of layered structure, it is a challenge how to represent these underlying physical network resources and topology into a form that can be reliably used by the computation engine that assigns the client requests into the physical network resource and topology.
[[DC]] Damnly true
[DC] I vote for a KISS approach :)
[Xian]Cannot agree with Diego more, :D.

-   Resource Efficiency

YOUNG>> Yes.
[Xian] This probably is more VNE algorithm related, instead of ACTN, but for sure an important aspect for the overall solution.

-   Guarantee of Client Isolation
While network resource sharing across a set of clients for efficient utilization is important aspect of network virtualization, client isolation has to be guaranteed. Admissions of new client requests or any changes of other existing clients’ VNs must not affect any particular client in terms of resource guarantee, security constraints, and other performance constraints.
[[DC]] Again linked to issues above. If network resources are dedicated to each VN, this is true, but if they (or part of them) are shared, the instantiation of a service from a given client would impact the VN seen by others. On the other side, aspects like security o performances should not be impacted in any of the two cases.

-   Computing Time
Depending on the nature of applications, how quickly a VN is instantiated from the time of request is an important factor. For dynamic applications that require instantaneous VN creation, the computation model/algorithm should support this constraint.
[[DC]] I would say that timing constraints need to be met for service provisioning (i.e. upon client requests on a given VN) but I think VN instantiation could be also a non real time procedure. I might be wrong…are there use cases for real time and timing constrained VN creation requrests?

-   Path Constraints

YOUNG>> Yes, if we include non-TE underlying transport as part of the ACTN scope, then  the TE-reacheability needs to be known/advertised by the server network to clients as ‘capability’ attribute.
[Xian] Have we already confined the scope to TE transport network only?

I think whether the TE information is conveyed to the client depends on the details the client wants to know. From ACTN work point of view, it should be considered as part of the constraints worth considering.

---

From: "Matta, Abraham I" <[email-masked]>
Date: Tue, 31 Dec 2013 16:03:42 +0000

Another survey:

http://www.cs.bu.edu/techreports/pdf/2011-025-slice-embedding.pdf

F. Esposito, I. Matta, and V. Ishakian. Slice Embedding Solutions for

Distributed Service Architectures. ACM Computing Surveys, Accepted

November 2012 (to appear in Volume 46, Issue 1, March 2014).

Best,
ibrahim

From: "Zhangxian (Xian)" <[email-masked]<mailto:[email-masked]>>
Date: Tuesday, December 31, 2013 4:01 AM
To: Diego Caviglia <[email-masked]<mailto:[email-masked]>>, Leeyoung <[email-masked]<mailto:[email-masked]>>, Daniele Ceccarelli <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Sdn] [Actn] virtual network mapping/embedding (VNM/VNE) problem

Hi all,

Happy new year,

Xian

From: sdn [mailto:[email-masked]] On Behalf Of Diego Caviglia
Sent: 2013年12月23日 16:02
To: Leeyoung; Daniele Ceccarelli; [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [Sdn] [Actn] virtual network mapping/embedding (VNM/VNE) problem

BR and Season greetings!

D

-   Request Processing

-   Accuracy of Network Resource Representation
As the underlying transport network in itself may consists of layered structure, it is a challenge how to represent these underlying physical network resources and topology into a form that can be reliably used by the computation engine that assigns the client requests into the physical network resource and topology.
[[DC]] Damnly true
[DC] I vote for a KISS approach ☺
[Xian]Cannot agree with Diego more, :D.

-   Resource Efficiency

YOUNG>> Yes.

-   Computing Time

-   Path Constraints