Die Erfindung betrifft ein Verfahren zur Steigerung von Netzwerkressourcennutzung und Bereitstellung genügender Service-Qualität, QoS, durch Einsatz virtueller Netzwerk-Embedding-Applikationen innerhalb eines physikalischen Netzwerkes, insbesondere eines SDN- Netzwerkes.The invention relates to a method for increasing network resource utilization and providing sufficient service quality, QoS, through the use of virtual network embedding applications within a physical network, particularly an SDN network.
SDN-Netzwerke (Software Defined Industrial Networks) ziehen Nutzen aus der Flexibilität und Programmierbarkeit für ihre Anwendungen innerhalb industrieller Netzwerke. Bei SDN-Netzwerken laufen die Kontrollfunktionen (Control Plane) separat von der Datenebene (Data Plane). Ein SDN-Netzwerk ist skalierbar, flexibel und lässt sich dynamisch an neue Anforderungen anpassen. Ein SDN-Netzwerk bietet eine gute Grundlage für Cloud Computing und bietet die Möglichkeit einer virtualisierten Netzwerkverbindung. Ein SDN-Netzwerk lässt sich relativ einfach verwalten, wobei die zugrunde liegende Hardware nicht mehr manuell konfiguriert werden muss. Zudem wird der gesamte Datenverkehr im SDN-Netzwerk zentral steuerbar. Bei Software Defined Networking, SDN, werden die Datenströme innerhalb des Netzwerkes softwarebasiert von zentraler Stelle in Echtzeit identifiziert und gesteuert. SDN-Netzwerke eignen sich insbesondere für gewachsene und dezentrale Netzwerke.Software Defined Industrial Networks (SDNs) take advantage of the flexibility and programmability of their applications within industrial networks. For SDN networks, the control functions (Control Plane) run separately from the data plane (Data Plane). An SDN network is scalable, flexible and can be dynamically adapted to new requirements. An SDN network provides a good foundation for cloud computing and offers the possibility of a virtualized network connection. An SDN network is relatively easy to manage, with the underlying hardware no longer requiring manual configuration. In addition, the entire data traffic in the SDN network is centrally controlled. In Software Defined Networking (SDN), the data streams within the network are identified and controlled by software in a centralized, real-time, software-based manner. SDN networks are particularly suitable for established and decentralized networks.
Verschiedene Anwendungen bzw. Applikationen können mit unterschiedlichen Service-Qualitätsanforderungen S-QoS um zur Verfügung stehende Netzwerkressourcen in Wettbewerb stehen. Diese Netzwerkressourcen des zugrunde liegenden physikalischen Netzwerkes umfassen beispielsweise Signalbandbreite oder sonstige hierdurch beeinflusste Metriken wie beispielsweise Signalverzögerung und/oder Signaljitter. Beispielsweise sind einige Applikationen wie Video- oder Audioanwendungen bandbreitenzentriert, während andere Anwendungen, beispielsweise Steuerungsanwendungen, verzögerungszentriert sind.Different applications or applications can compete with different service quality requirements S-QoS for available network resources. These network resources of the underlying physical network include, for example, signal bandwidth or other metrics influenced thereby, such as signal delay and / or signal jitter. For example, some applications, such as video or audio applications, are bandwidth-centered, while other applications, such as control applications, are delay-centered.
Die herkömmliche Virtual Network Embedding-Technologie VNE versucht die Netzwerkressourcenallokation in einem komplexen Multiservice-SDN-Netzwerk zu verbessern. Dabei werden in möglichst effizienter Weise physikalische Netzwerkressourcen zwischen verschiedenen virtuellen Netzwerken VN, die virtuelle Knoten und virtuelle Links umfassen, aufgeteilt, um die Anzahl der gleichzeitig existierenden virtuellen Tenant Networks zu maximieren und die Ausnutzung der physikalischen Infrastruktur zu steigern, während gleichzeitig die Erfüllung der Service-Qualitätsanforderungen garantiert wird. Allerdings wird das virtuelle Netzwerk-Embedding verschiedener virtueller Netzwerke innerhalb eines physikalischen Netzwerkes gravierend dadurch erschwert, dass VL-Anfragen bzw. VL-Requests VLR zum Aufbau eines virtuellen Links VL von einem Ausgangsknoten hin zu einem Zielknoten in vielen Anwendungsfällen online bzw. in Echtzeit auftreten. Demzufolge sind die Eigenschaften bzw. Charakteristika der empfangenen VL-Anfragen VLR innerhalb eines virtuellen Netzwerkes VN nicht vorhersehbar. Ein online Traffic Engineering(TE)-Anwendungsfall, für den kein Vorabwissen hinsichtlich der Service-Qualitätsanforderungen QoS der virtuellen Netzwerke VN und deren Empfangsreihenfolge besteht, hat demnach folgende Nachteile. Es kann vorkommen, dass anforderungskritische Anwendungen zurückgewiesen werden und demzufolge niedrige VN-Embedding Rates erzielt werden. Weiterhin kann die zur Verfügung gestellte physikalische Infrastruktur des physikalischen Netzwerkes nicht in ausreichendem Maße ausgenutzt werden aufgrund einer Anhäufung von virtuellen Links mit hohen Service-Qualitätsanforderungen, insbesondere einer verzögerungskritischen Signalbandbreite. Zur Optimierung des Ressourcen-Mappings durch Maximierung der Embedding-Raten und der Netzwerk- bzw. Substratnutzung ist es daher oft erforderlich, dass ein Remapping bzw. Umordnen von bestimmten virtuellen Verbindungen bzw. virtuellen Links VL durchgeführt werden muss, um Raum für kritische Signalverzögerungsanforderungen zu schaffen. Dieser herkömmliche Ansatz eines Remappings von virtuellen Links ist jedoch umständlich und sehr aufwendig hinsichtlich der zur Verfügung stehenden Berechnungsressourcen. Ein anderer herkömmlicher Ansatz zur Optimierung der Embedding-Raten und der Netzwerknutzung besteht in der Verwendung von Offline-Embedding-Prozeduren, bei denen VL-Anfragen zunächst in einer bestimmten Weise vorsortiert werden, damit verzögerungs- bzw. delay-kritische Anforderungen bzw. VL-Anfragen vor bandbreitenzentrierten Anfragen behandelt werden. Allerdings können nicht alle Applikationen bzw. Anwendungen an eine derartige Offline-Embedding-Prozedur angepasst bzw. vorgesehen werden.The traditional Virtual Network Embedding technology VNE Attempts to improve network resource allocation in a complex multi-service SDN network. In doing so, physical network resources between different virtual networks become as efficient as possible VN , which include virtual nodes and virtual links, to maximize the number of simultaneously existing virtual tenant networks and increase the utilization of the physical infrastructure, while at the same time guaranteeing the fulfillment of the service quality requirements. However, virtual network embedding of various virtual networks within a physical network is severely hampered by VL requests or VL requests VLR to build a virtual link VL From an output node to a destination node in many applications occur online or in real time. As a result, the characteristics of the received VL requests are VLR within a virtual network VN unpredictable. An online traffic engineering (TE) application that does not have any prior knowledge of service quality requirements QoS the virtual networks VN and their order of reception is, therefore, has the following disadvantages. It may happen that mission-critical applications are rejected, resulting in low VN embedding rates. Furthermore, the provided physical infrastructure of the physical network can not be sufficiently exploited due to an accumulation of virtual links with high service quality requirements, in particular a delay-critical signal bandwidth. To optimize resource mappings by maximizing embed rates and network / substrate utilization, it is often necessary to remap or reorder certain virtual circuits or virtual links VL must be performed in order to make room for critical signal delay requirements. However, this traditional approach of remapping virtual links is cumbersome and very expensive in terms of available computational resources. Another conventional approach to optimizing embedding rates and network utilization is to use off-line embedding procedures, where VL requests are first pre-sorted in a particular manner to provide delay-or delay-critical requirements. Requests for bandwidth-centric queries are handled. However, not all applications or applications can be adapted or provided for such an offline embedding procedure.
1 veranschaulicht ein der Erfindung zugrunde liegendes Problem. Eine Steuereinheit erhält in Echtzeit eine Folge von VL-Anfragen bzw. Virtual Link Requests VLR von einer auf einem Netzwerkknoten A ausgeführten Applikation oder Anwendung f. Das in 1 dargestellte physikalische Netzwerk PHY-NW umfasst mehrere Netzwerkknoten KN nämlich A, B, C, D, E. Zwischen den verschiedenen Netzwerkknoten KN bestehen physikalische Links bzw. physikalische Verbindungen L. Bei diesen physikalischen Verbindungen L kann es sich um beliebige physikalische Verbindungen handeln, beispielsweise drahtgebundene oder drahtlose Verbindungen. Jede physikalische Verbindung L besitzt verschiedene physikalische Verbindungsparameter bzw. Verbindungsattribute. Beispielsweise besitzt die physikalische Verbindung L zwischen dem Netzwerkknoten A und dem Netzwerkknoten D eine Bandbreite B von 10 und eine Signalverzögerung D mit dem Wert 5. In dem dargestellten Beispiel von 1 besitzen alle physikalischen Verbindungen eine Bandbreite B von 10 und eine Signalverzögerung D von 5. In dem dargestellten Beispiel von 1 erhält die Steuereinrichtung, insbesondere ein SDN-Controller des Netzwerkes, eine erste VL-Anfrage VLR1 zum Aufbau einer virtuellen Netzverbindung zu dem Client g am Netzwerkknoten C. Diese erste VL-Anfrage bzw. VL-Request VLR1 beinhaltet verschiedene Service-Qualitätsanforderungen QoS, nämlich eine Bandbreite B von 10, einen maximalen Delay bzw. maximale Signalverzögerung D von 15, ein Hop Count H von 5 sowie ein maximal zulässiger Signaljitter J von 5. Die zweite VL-Anfrage VLR2 des Clients f am ersten Netzwerkknoten A beinhaltet als Service-Qualitätsanforderung QoS eine Bandbreite B von 10, eine maximale Signalverzögerung D von 15, ein Hop Count H von 5 sowie ein Signaljitter J von 5. Insgesamt sind in 1 vier VL-Anfragen VLR1, VLR2, VLR3, VLR4 dargestellt. Die Anzahl der VL-Anfragen bzw. Virtual Link Requests VLR kann variieren, genauso wie die Anzahl und Art der darin enthaltenen Service-Qualitätsanforderungen QoS. Herkömmliche heuristische Verfahren von MIP-Lösungen resultieren in einem Mapping der ersten VL-Anfrage VLR1 auf das physikalische Link AC und der zweiten VL-Anfrage VLR2 auf die physikalischen Links AB sowie BC, wie auch in 1 mit gestrichelten Linien angedeutet. Falls das Ereignis auftritt, dass eine dritte VL-Anfrage VLR3 und eine vierte VL-Anfrage VLR4 empfangen wird, stehen keine geeigneten Netzwerkressourcen mehr zur Verfügung, welche die Service-Qualitätsanforderungen QoS erfüllen. Demzufolge wird die dritte VL-Anfrage VLR3 und die vierte VL-Anfrage VLR4 zurückgewiesen, obwohl noch Bandbreite B auf dem Link AD, DE, EC und auf dem Link DC zur Verfügung steht. Herkömmliche Verfahren ergeben somit eine niedrige Ausnutzung der zur Verfügung stehenden physikalischen Bandbreite sowie eine niedrige Embedding-Rate hinsichtlich VL-Anfragen VLR mit anspruchsvolleren Service-Qualitätsanforderungen QoS und demzufolge eine insgesamt niedrige Embedding-Rate. Bei herkömmlichen Verfahren wird allgemein der beste Signalpfad gesucht, der alle Anforderungen erfüllt. Dann werden die entsprechenden Ressourcen vergeben und sind demzufolge bereits vergeben, wenn später noch VL-Anfragen VLR mit kritischen bzw. hohen Service-Qualitätsanforderungen QoS erfolgen. 1 illustrates a problem underlying the invention. A control unit receives a sequence of VL requests or virtual link requests in real time VLR from one to a network node A executed application or application f. This in 1 represented physical network PHY-northwest includes several network nodes KN namely A . B . C . D . e , Between the different network nodes KN exist physical links or physical connections L , In these physical connections L they can be any physical connections, such as wired or wireless connections. Every physical connection L has different physical connection parameters or connection attributes. For example, the physical connection has L between the network node A and the network node D a bandwidth B from 10 and a signal delay D with the value 5. In the example shown by 1 All physical connections have a bandwidth B of 10 and a signal delay D of 5. In the example shown by 1 the control device, in particular an SDN controller of the network, receives a first VL request VLR1 to establish a virtual network connection to the client G at the network node C , This first VL request or VL request VLR1 includes different service quality requirements QoS namely a bandwidth B of 10, a maximum delay or maximum signal delay D from 15, a hop count H of 5 and a maximum allowable signal jitter J from 5. The second VL request VLR2 of the client f at the first network node A includes as a service quality request QoS a bandwidth B of 10, a maximum signal delay D from 15, a hop count H of 5 as well as a signal jitter J of 5. Overall are in 1 four VL requests VLR1 . VLR2 . VLR3 . VLR4 shown. The number of VL requests or virtual link requests VLR may vary, as well as the number and type of service quality requirements it contains QoS , Conventional heuristics of MIP solutions result in a mapping of the first VL request VLR1 on the physical link AC and the second VL request VLR2 on the physical links FROM such as BC as well as in 1 indicated by dashed lines. If the event occurs, that is a third VL request VLR3 and a fourth VL request VLR4 is received, there are no more suitable network resources available, which are the service quality requirements QoS fulfill. As a result, the third VL request VLR3 and the fourth VL request VLR4 rejected, although still bandwidth B on the link AD . DE . EC and on the link DC is available. Conventional methods thus result in a low utilization of the available physical bandwidth and a low embedding rate in terms of VL requests VLR with more demanding service quality requirements QoS and consequently an overall low embedding rate. Conventional methods generally seek the best signal path that meets all requirements. Then the corresponding resources are assigned and are therefore already taken, if later VL requests VLR with critical or high service quality requirements QoS respectively.
Hinsichtlich des in 1 beispielhaft dargestellten Problems für ein beispielhaftes Netzwerk werden bei herkömmlichen Verfahren zum Teil Offline-Ansätze verwendet. Derartige Ansätze können zur Verbesserung führen, unter der Annahme, dass die Charakteristika und die Empfangsreihenfolge der VL-Anfragen bzw. VL-Requests VLR bekannt sind und folglich in der Art und Weise umsortiert werden können, dass diejenigen VL-Anfragen mit kritischeren bzw. höheren Anforderungen vor denjenigen VL-Anfragen bedient werden, welche weniger strikte Service-Qualitätsanforderungen QoS aufweisen. Jedoch sind bei allen Echtzeitanwendungsszenarien die Empfangsreihenfolge und die Charakteristika bzw. Eigenschaften der VL-Requests unvorhersehbar, sodass eine Umsortierung der empfangenen VL-Anfragen VLR nicht möglich ist. Bei einem herkömmlichen Offline-Ansatz würde die Reihenfolge der VL-Anfragen, wie sie in 1 oben dargestellt sind, derart umsortiert bzw. umarrangiert werden, dass die dritte VL-Anfrage VLR3 und die vierte VL-Anfrage VLR4, die eine höhere Service-Qualitätsanforderung QoS hinsichtlich Signalverzögerung D besitzen, nämlich eine geforderte Signalverzögerung von 6 anstatt 15 zuerst behandelt und erfüllt werden, indem man das physikalische Link AC zwischen dem ersten Knoten A und dem dritten Knoten C benutzt. Dieses physikalische Link L hat eine Signalbandbreite B von 10 und erfüllt somit die Bandbreitenanforderungen der dritten VL-Anfrage VLR3 (B = 5) und der vierten VL-Anfrage VLR4, die ebenfalls eine Bandbreite B von 5 fordert. Zudem ist die Signalverzögerung D der physikalischen Verbindung AC D = 5 geringer als die zulässige Signalverzögerung von 6 der dritten VL-Anfrage VLR3 und der vierten VL-Anfrage VLR4. Anschließend wird bei dem herkömmlichen Offline-Ansatz die zweite VL-Anfrage VLR2 auf die physikalischen Verbindungen AB, BC embedded bzw. gemappt und schließlich die erste VL-Anfrage VLR1 entweder auf die physikalischen Verbindungen (AD, DC) oder (AD, DE, EC). Eine derartige Vorgehensweise ist allerdings bei Echtzeitanwendungen nicht möglich.Regarding the in 1 For an exemplary network, as illustrated by way of example, conventional methods sometimes use off-line approaches. Such approaches may lead to improvement, assuming that the characteristics and reception order of the VL requests VLR and thus can be re-sorted in such a way that those VL requests with more critical or higher requirements are served before those VL requests which have less stringent service quality requirements QoS respectively. However, in all real-time application scenarios, the reception order and characteristics of the VL requests are unpredictable, thus resorting the received VL requests VLR not possible. In a traditional off-line approach, the order of the VL requests, as in 1 are re-sorted or rearranged so that the third VL request VLR3 and the fourth VL request VLR4 that have a higher quality service requirement QoS in terms of signal delay D namely, a required signal delay of 6 instead of 15 must first be treated and fulfilled by the physical link AC between the first node A and the third node C used. This physical link L has a signal bandwidth B of 10 and thus satisfies the bandwidth requirements of the third VL request VLR3 (B = 5) and the fourth VL request VLR4 which also has a bandwidth B of 5 calls. In addition, the signal delay D the physical connection AC D = 5 less than the allowable signal delay of 6 of the third VL request VLR3 and the fourth VL request VLR4 , Subsequently, in the conventional offline approach, the second VL request VLR2 on the physical connections FROM . BC embedded or mapped and finally the first VL request VLR1 either on the physical connections ( AD . DC ) or ( AD . DE . EC ). However, such a procedure is not possible in real-time applications.
Bei Online- bzw. Echtzeit-Embedding erfolgt herkömmlicherweise eine Rekonfiguration bzw. ein Remapping. Dabei wird ein virtueller Link-Embedding in Echtzeitanwendungsszenarien realisiert, wobei keine Annahmen hinsichtlich der Reihenfolge getroffen werden, in der VL-Anforderungen VLR eintreffen. Bei diesem herkömmlichen Ansatz werden die bereits behandelten virtuellen Links VL mit weniger schwerwiegenden Service-Qualitätsanforderungen umgemappt, um Raum für neue virtuelle Links mit höheren bzw. strikteren Service-Qualitätsanforderungen QoS zu schaffen. Dieser Umkonfigurations- bzw. Remapping-Ansatz erfordert jedoch zusätzliche Rechenkapazitäten und Berechnungszeiten und ist daher insbesondere bei größeren Netzwerken nicht einsetzbar. Bei dem in 1 dargestellten beispielhaften Netzwerk wird gemäß einem herkömmlichen Rekonfigurationsansatz zunächst die erste VL-Anfrage VLR1 auf die physikalischen Verbindungen (AD, DC) oder (AD, DE, EC) umgemappt, um freie Ressourcen auf der physikalischen Verbindung AC zu schaffen. Allerdings resultiert hier die Bestimmung, welcher bereits behandelte Request VLR umgemappt werden muss, in einem zusätzlichen Bearbeitungsoverhead. Darüber hinaus verwenden herkömmliche Verfahren komplexe Kostenfunktionen. Die meisten dieser Kostenfunktionen zielen darauf ab, verstopfte bzw. überforderte physikalische Links L zu vermeiden. Diese Kostenfunktionen konzentrieren sich darauf, frühzeitig Engpässe zu vermeiden, stellen jedoch nicht sicher, dass eine Anwendung mit den richtigen bzw. geeigneten Netzwerkressourcen versorgt werden. Darüber hinaus berücksichtigen herkömmliche Kostenfunktionen meist nur eine Art von Service-Qualitätsanforderungen S-QoS zur Berechnung einer optimalen Lösung.For online or real-time embedding conventionally, a reconfiguration or a remapping is done. This implements virtual link embedding in real-time application scenarios, with no assumptions about the order in which VL requests are made VLR arrive. This traditional approach uses the already-discussed virtual links VL Rescheduled with less serious service quality requirements to make room for new virtual links with higher or stricter service quality requirements QoS to accomplish. However, this reconfiguration or remapping approach requires additional computing capacity and calculation times and therefore can not be used, especially for larger networks. At the in 1 The exemplary network shown above first becomes the first VL request in accordance with a conventional reconfiguration approach VLR1 on the physical connections ( AD . DC ) or ( AD . DE . EC ) remapped to free resources on the physical connection AC to accomplish. However, the determination of which already handled request results here VLR has to be repackaged in an additional processing overhead. In addition, use conventional procedures complex cost functions. Most of these cost functions are designed to help clogged or overwhelmed physical links L to avoid. These cost functions focus on avoiding bottlenecks at an early stage, but do not ensure that an application is provided with the right or appropriate network resources. In addition, traditional cost functions usually only consider one type of service quality requirement S-QoS to calculate an optimal solution.
Es ist daher eine Aufgabe der vorliegenden Erfindung, ein Verfahren zur Nutzungssteigerung von Netzwerkressourcen durch Anwendungen bei einem virtuellen Netzwerk-Embedding innerhalb eines physikalischen Netzwerkes zu schaffen, das sich auch für Echtzeitanwendungen eignet und eine Rekonfiguration bzw. ein Ummappen zur Verringerung von Berechnungszeiten und Overhead vermeidet.It is therefore an object of the present invention to provide a network resource utilization method by virtual network embedding applications within a physical network that is also suitable for real-time applications and avoids reconfiguration to reduce computation times and overhead ,
Diese Aufgabe wird gemäß einem ersten Aspekt der vorliegenden Erfindung durch ein Verfahren mit den in Patentanspruch 1 angegebenen Merkmalen gelöst.This object is achieved according to a first aspect of the present invention by a method having the features specified in claim 1.
Die Erfindung schafft gemäß einem ersten Aspekt ein Verfahren zur Steigerung einer Netzwerkressourcennutzung und Bereitstellung genügender Servicequalität, QoS, durch virtuelle Netzwerk-Embedding-Applikationen innerhalb eines physikalischen Netzwerkes, mit den folgenden Schritten: Empfangen einer VL-Anfrage, VLR, von einer resourcennachfragekritischen Applikation in Echtzeit zum Aufbau eines virtuellen Links, VL, von einem ersten Netzwerkknoten, KN1, zu einem zweiten Netzwerkknoten, KN2, des physikalischen Netzwerkes, PHY-NW,
wobei die VL-Anfrage, VLR, Service-Qualitätsanforderungen, S-QoS, beinhaltet, die an das virtuelle Link, VL, gestellt werden,
Ermitteln möglicher Kandidaten-Signalpfade, K-SP, zwischen dem ersten Netzwerkknoten, KN1, und dem zweiten Netzwerkknoten, KN2, innerhalb des physikalischen Netzwerkes, PHY-NW, welche die Service-Qualitätsanforderungen, S-QoS, erfüllen, Selektieren desjenigen Signalpfades, SP, aus den ermittelten Kandidaten-Signalpfaden, K-SP, als geeignetsten bzw. optimalen Signalpfad, SPopt , welcher die Abweichungen zwischen den an das virtuelle Link, VL, gestellten Service-Qualitätsanforderungen, S-QoS, und einer berechneten Service-qualität (QoS) entlang des Kandidaten-Signalpfades minimiert, und
Aufbauen des virtuellen Links, VL, zwischen dem ersten Netzwerkknoten, KN1, und dem zweiten Netzwerkknoten, KN2, des physikalischen Netzwerkes, PHY-NW, über den in Bezug auf die Service-Qualitätsanforderungen, S-QoS, der VL-Anfrage selektierten geeignetsten Signalpfad, SPopt .The invention according to a first aspect provides a method for increasing network resource utilization and providing sufficient quality of service. QoS by virtual network embedding applications within a physical network, comprising the steps of: receiving a VL request, VLR , by a resource-critical application in real time to build a virtual link, VL from a first network node, KN1 to a second network node, KN2 , the physical network, PHY-northwest .
where the VL request, VLR , Service quality requirements, S-QoS , that links to the virtual link, VL to be asked
Determining possible candidate signal paths, K-SP between the first network node, KN1 , and the second network node, KN2 within the physical network, PHY-northwest which the service quality requirements, S-QoS , selecting, selecting that signal path, SP, from the determined candidate signal paths, K-SP , as the most suitable or optimal signal path, SP opt that the deviations between the to the virtual link, VL , set service quality requirements, S-QoS , and a calculated service quality ( QoS ) along the candidate signal path, and
Building the virtual link, VL between the first network node, KN1 , and the second network node, KN2 , the physical network, PHY-northwest about which in terms of service quality requirements, S-QoS , the VL request selected the most appropriate signal path, SP opt ,
Bei einer möglichen Ausführungsform des erfindungsgemäßen Verfahrens umfassen die Service-Qualitätsanforderungen, S-QoS, der VL-Anfrage, VLR, additive Netzwerkressourcenanforderungen (H, D, J) und nicht-additive Netzwerkressourcenanforderungen (B, Buffer), die an physikalischen Netzwerkressourcen des Netzwerkes entlang des virtuellen Links, VL, gestellt werden.In one possible embodiment of the method according to the invention, the service quality requirements include S-QoS , the VL request, VLR , Additive Network Resource Requirements ( H . D . J ) and non-additive network resource requirements ( B , Buffers) connected to physical network resources of the network along the virtual link, VL to be asked.
Bei einer möglichen Ausführungsform des erfindungsgemäßen Verfahrens beziehen sich die additiven Netzwerkressourcenanforderungen auf Service-Qualitätsanforderungen, S-QoS, der VL-Anfrage, VLR, die durch physikalische Netzwerkressourcen entlang des Signalpfades, SP, des virtuellen Links, VL, aggregiert zu erfüllen sind.In one possible embodiment of the method according to the invention, the additive network resource requirements relate to service quality requirements, S-QoS , the VL request, VLR generated by physical network resources along the signal path, SP , the virtual link, VL to be aggregated.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens weisen die additiven Netzwerkressourcenanforderungen eine Anzahl, H, von Netzwerkknoten, KN, zwischen dem ersten Netzwerkknoten, KN1, am Anfang des virtuellen Links, VL, und dem zweiten Netzwerkknoten, KN2, am Ende des virtuellen Links, VL, entlang eines Signalpfades, SP, des physikalischen Netzwerkes auf.In a further possible embodiment of the method according to the invention, the additive network resource requests have a number H , from network nodes, KN between the first network node, KN1 , at the beginning of the virtual link, VL , and the second network node, KN2 , at the end of the virtual link, VL , along a signal path, SP , the physical network.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens weisen die additiven Netzwerkressourcenanforderungen eine maximal zulässige Signalverzögerung, D, zwischen dem ersten Netzwerkknoten, KN1, am Anfang des virtuellen Links, VL, und dem zweiten Netzwerkknoten, KN2, am Ende des virtuellen Links, VL, entsprechend der Signalverzögerung entlang eines Signalpfades, SP, des physikalischen Netzwerkes auf.In a further possible embodiment of the method according to the invention, the additive network resource requirements have a maximum permissible signal delay, D between the first network node, KN1 , at the beginning of the virtual link, VL , and the second network node, KN2 , at the end of the virtual link, VL , according to the signal delay along a signal path, SP , the physical network.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens weisen die additiven Netzwerkressourcenanforderungen einen maximal zulässigen Signaljitter, J, bzw. Signalverzögerungsvariation des von dem ersten Netzwerkknoten, KN1, am Anfang des virtuellen Links, VL, zu dem zweiten Netzwerkknoten, KN2, am Ende des virtuellen Links, VL, übertragenen Signals auf.In a further possible embodiment of the method according to the invention, the additive network resource requirements have a maximum permissible signal jitter, J or signal delay variation of the signal from the first network node, KN1 , at the beginning of the virtual link, VL to the second network node, KN2 , at the end of the virtual link, VL , transmitted signal.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens beziehen sich die nicht-additiven Netzwerkressourcenanforderungen auf Service-Qualitätsanforderungen, S-QoS, der VL-Anfrage, VLR, die durch physikalische Netzwerkressourcen entlang des Signalpfades, SP, des virtuellen Links, VL, jeweils individuell zu erfüllen sind.In another possible embodiment of the method according to the invention, the non-additive network resource requirements relate to service quality requirements, S-QoS , the VL request, VLR generated by physical network resources along the signal path, SP , the virtual link, VL , are to be fulfilled individually.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens weisen die nicht-additiven Netzwerkressourcenanforderungen eine minimal geforderte Signalbandbreite jeder physikalischen Verbindung zwischen Netzwerkknoten, KN, entlang des Signalpfades, SP, des virtuellen Links, VL, auf.In another possible embodiment of the inventive method, the non-additive network resource requirements include a minimum required signal bandwidth of each physical connection Network nodes, KN , along the signal path, SP , the virtual link, VL , on.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens weisen die nicht-additiven Netzwerkressourcenanforderungen eine maximale Verbindungsverlustwahrscheinlichkeit auf.In a further possible embodiment of the method according to the invention, the non-additive network resource requirements have a maximum connection loss probability.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens weisen die nicht-additiven Netzwerkressourcenanforderungen eine maximal zulässige Signalverarbeitungsenergie eines Netzwerkknotens, KN, entlang des Signalpfades, SP, des virtuellen Links, VL, auf.In another possible embodiment of the method according to the invention, the non-additive network resource requirements have a maximum allowable signal processing energy of a network node, KN , along the signal path, SP , the virtual link, VL , on.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens werden die VL-Anfragen, VLRs, zum Aufbauen von virtuellen Links, VLs, in Echtzeit von Applikationen empfangen und basierend auf ihren Service-Qualitätsanforderungen, S-QoS, mögliche Kandidaten-Signalpfade sowie der geeignetste Signalpfad, SPopt , in Echtzeit ermittelt, wobei der geeignetste Signalpfad, SPopt , derjenige Signalpfad ist, der die Abweichungen zu den Signal-Qualitätsanforderungen, S-QoS, des virtuellen Links, VL, minimiert.In another possible embodiment of the method according to the invention, the VL requests, VLR , for building virtual links, VLs Received in real-time from applications and based on their service quality requirements, S-QoS , possible candidate signal paths as well as the most suitable signal path, SP opt determined in real time, with the most appropriate signal path, SP opt , which is the signal path that determines the deviations from the signal quality requirements, S-QoS , the virtual link, VL , minimized.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens werden die möglichen Kandidaten-Signalpfade, welche die Service-Qualitätsanforderungen, S-QoS, erfüllen, mittels eines QoS-Datenmodells ermittelt.In another possible embodiment of the method according to the invention, the possible candidate signal paths, which are the service quality requirements, S-QoS satisfy, determined by means of a QoS data model.
Bei einer weiteren möglichen Ausführungsform des erfindungsgemäßen Verfahrens wird die VL-Anfrage, VLR, zum Aufbau eines virtuellen Links, VL, durch eine auf dem ersten Netzwerkknoten, KN1, ausgeführte resourcennachfragekritische Applikation generiert.In another possible embodiment of the method according to the invention, the VL request, VLR , to build a virtual link, VL by one on the first network node, KN1 , executed resource request critical application generated.
Die Erfindung schafft ferner gemäß einem weiteren Aspekt einen Netzwerk-Controller mit den in Patentanspruch 14 angegebenen Merkmalen.The invention further provides, in another aspect, a network controller having the features set forth in claim 14.
Die Erfindung schafft demnach einen Netzwerk-Controller, insbesondere SDN-Netzwerk-Controller mit einem Prozessor zur Durchführung eines Verfahrens zur Nutzungssteigerung von Netzwerkressourcen mit den in Patentanspruch 1 angegebenen Merkmalen.The invention accordingly provides a network controller, in particular SDN network controller with a processor for carrying out a method for increasing the use of network resources with the features specified in claim 1.
Die Erfindung schafft ferner gemäß einem weiteren Aspekt ein Netzwerk mit den in Patentanspruch 15 angegebenen Merkmalen.The invention further provides, in another aspect, a network having the features specified in claim 15.
Die Erfindung schafft demnach ein Netzwerk mit mindestens einem Netzwerk-Controller gemäß dem zweiten Aspekt der Erfindung, welcher die Merkmale des Patentanspruchs 14 beinhaltet.The invention thus provides a network with at least one network controller according to the second aspect of the invention, which includes the features of claim 14.
Im Weiteren werden mögliche Ausführungsformen des erfindungsgemäßen Erfahrens und des erfindungsgemäßen Netzwerkes sowie des erfindungsgemäßen Netzwerk-Controllers unter Bezugnahme auf die beigefügten Figuren näher erläutert.In the following, possible embodiments of the invention and the network according to the invention as well as the network controller according to the invention will be explained in more detail with reference to the attached figures.
Es zeigen:
- 1 einen Graphen eines beispielhaften Netzwerkes zur Erläuterung des der Erfindung zugrunde liegenden Problems;
- 2 ein Ablaufdiagramm zur Darstellung einer möglichen Ausführungsform des erfindungsgemäßen Verfahrens zur Nutzungssteigerung von Netzwerkressourcen;
- 3 Graphen zur Erläuterung des erfindungsgemäßen Verfahrens;
- 4 ein Ablaufdiagramm zur Darstellung einer möglichen Ausführungsform des erfindungsgemäßen Verfahrens zur Nutzungssteigerung von Netzwerkressourcen;
- 5 ein Diagramm zur Darstellung eines Link-Scheduler-Queue-Modells zur Erläuterung der Ermittlung von bereitgestellten Netzwerkressourcen.
Show it: - 1 a graph of an exemplary network for explaining the problem underlying the invention;
- 2 a flow diagram illustrating a possible embodiment of the method according to the invention for increasing the use of network resources;
- 3 Graphs for explaining the method according to the invention;
- 4 a flow diagram illustrating a possible embodiment of the method according to the invention for increasing the use of network resources;
- 5 a diagram illustrating a link scheduler queue model explaining the discovery of network resources deployed.
Wie man aus 2 erkennen kann, umfasst das Verfahren gemäß dem ersten Aspekt der Erfindung bei einer möglichen Ausführungsform mehrere Hauptschritte SA bis SD . Bei dem in 2 dargestellten Ausführungsbeispiel umfasst das Verfahren zur Nutzungssteigerung von Netzwerkressourcen und zur Bereitstellung einer genügenden bzw. ausreichenden Servicequalität, QoS, durch virtuelle Netzwerk-Embedding-Applikationen bzw. - Anwendungen innerhalb eines physikalischen Netzwerkes vier Hauptschritte.How to get out 2 In one possible embodiment, the method according to the first aspect of the invention comprises a plurality of main steps S A to S D , At the in 2 The exemplary embodiment illustrated comprises the method for increasing the use of network resources and for providing a sufficient quality of service. QoS , four main steps through virtual network embedding applications or applications within a physical network.
In einem ersten Schritt SA wird eine VL-Anfrage bzw. ein VL-Request VLR von einer resourcennachfragekritischen Applikation zum Aufbau eines virtuellen Links bzw. einer virtuellen Verbindung VL von einem ersten Netzwerkknoten KN1 zu einem zweiten Netzwerkknoten KN2 innerhalb des physikalischen Netzwerkes empfangen. Die VL-Anfrage bzw. der VL-Request VLR beinhaltet dabei Service-Qualitätsanforderungen S-QoS, die an das virtuelle Link bzw. die virtuelle Verbindung VL gestellt werden. Die VL-Anfrage wird online bzw. in Echtzeit empfangen werden. Bei einer möglichen Ausführungsform wird die VL-Anfrage im Schritt SA durch einen SDN-Controller des Netzwerkes von dem ersten Netzwerkknoten KN1 empfangen. Bei einer möglichen Ausführungsform wird die VL-Anfrage durch eine Applikation, insbesondere eine Echtzeitapplikation, generiert. Diese Echtzeitapplikation kann bei einer möglichen Ausführungsform auf dem ersten Netzwerkknoten KN1 selbst oder auf einem mit dem ersten Netzwerkknoten KN1 verbundenen Clientknoten ausgeführt werden.In a first step S A becomes a VL request or a VL request VLR from a resource-critical application for building a virtual link or a virtual connection VL from a first network node KN1 to a second network node KN2 received within the physical network. The VL request or the VL request VLR includes service quality requirements S-QoS to the virtual link or virtual connection VL be put. The VL request will be received online or in real time. In one possible embodiment, the VL request is in step S A by an SDN controller of the network from the first network node KN1 receive. In one possible embodiment, the VL request is generated by an application, in particular a real-time application. This real-time application may, in one possible embodiment, be on the first network node KN1 yourself or on one with the first Network nodes KN1 connected client nodes.
In einem zweiten Schritt SB werden mögliche Kandidaten-Signalpfade K-SP zwischen dem ersten Netzwerkknoten KN1 und dem zweiten Netzwerkknoten KN2 innerhalb des physikalischen Netzwerkes PHY-NW ermittelt, wobei die möglichen Kandidaten-Signalpfade K-SP die gestellten Service-Qualitätsanforderungen S-QoS erfüllen bzw. ihnen genügen. Es werden alle Kandidaten-Signalpfade zwischen dem ersten Netzwerkknoten KN1 und dem zweiten Netzwerkknoten KN2 berechnet, welche die Servicequalitätsanforderungen S-QoS der empfangenen VL-Anfrage VLR erfüllen. Dabei wird beispielsweise eine Liste von Kandidaten-Signalpfaden K-SP erzeugt, welche alle die geforderten Service-Qualitätsanforderungen S-QoS erfüllen. Die Ermittlung der Kandidaten-Signalpfade K-SP erfolgt beispielsweise durch einen SDN-Controller des Netzwerkes, welcher die VL-Anfrage VLR von der resourcennachfragekritischen Applikation im Schritt SA erhalten hat.In a second step S B become possible candidate signal paths K-SP between the first network node KN1 and the second network node KN2 within the physical network PHY-northwest determines the possible candidate signal paths K-SP the set service quality requirements S-QoS meet or satisfy them. All candidate signal paths between the first network node KN1 and the second network node KN2 calculated the service quality requirements S-QoS the received VL request VLR fulfill. Here, for example, a list of candidate signal paths K-SP which all meet the required service quality requirements S-QoS fulfill. The determination of the candidate signal paths K-SP is done for example by an SDN controller of the network which polls the VL VLR from the resource-critical application in step S A had received.
In einem weiteren Schritt Sc wird derjenige Signalpfad SP aus den ermittelten Kandidaten-Signalpfaden als optimaler bzw. geeignetster Signalpfad SPopt selektiert, welcher die Abweichungen zwischen den an das virtuelle Link, VL, gestellten Service-Qualitätsanforderungen S-QoS und einer berechneten Servicequalität, QoS, entlang des Kandidaten-Signalpfades minimiert. So werden beispielsweise aus einer zwischengespeicherten Liste von möglichen Kandidaten-Signalpfaden K-SP derjenige beste bzw. geeignetste Signalpfad SPopt selektiert bzw. ausgewählt, bei welchem die Abweichungen bzw. das Delta zwischen den an das virtuelle Link VL gestellten Service-Qualitätsanforderungen S-QoS und der berechneten Servicequalität QoS, welche der Kandidaten-Signalpfad bietet, am geringsten sind. Der beste Signalpfad SPopt ist somit derjenige Signalpfad, bei dem der Unterschied zwischen den QoS-Anforderungen des VL und der berechneten Servicequalität des Signalpfades am geringsten ist. Der beste Signalpfad SPopt erfüllt somit alle Service-Qualitätsanforderungen S-QoS die gestellt werden, jedoch in möglichst geringem Ausmaß. Hierdurch wird eine Übererfüllung der gestellten Service-Qualitätsanforderungen S-QoS vermieden. Eine in der VL-Anfrage VLR gestellte Service-Qualitätsanforderung S-QoS wird somit möglichst knapp erfüllt, um möglichst wenig der zur Verfügung stehenden Netzwerkressourcen des physikalischen Netzwerkes zu okkupieren bzw. zu verbrauchen, sodass noch möglichst viele Netzwerkressourcen für die Erfüllung nachfolgender bzw. späterer VL-Anfragen VLR zur Verfügung stehen.In a further step S c becomes that signal path SP from the determined candidate signal paths as optimal or most suitable signal path SP opt selects the differences between the links to the virtual link, VL , set service quality requirements S-QoS and a calculated quality of service, QoS , minimized along the candidate signal path. For example, a cached list of candidate candidate signal paths K-SP the best or most suitable signal path SP opt selected or selected, in which the deviations or the delta between the to the virtual link VL Asked service quality requirements S-QoS and the calculated quality of service QoS that the candidate signal path offers are lowest. The best signal path SP opt is thus the signal path where the difference between the QoS requirements of the VL and the calculated service quality of the signal path is lowest. The best signal path SP opt thus fulfills all service quality requirements S-QoS which are made, but to the least extent possible. This will be an overachievement of the set service quality requirements S-QoS avoided. One in the VL request VLR Asked service quality requirement S-QoS is therefore as close as possible to occupy or consume as little as possible of the available network resources of the physical network, so still as many network resources for the fulfillment of subsequent or subsequent VL requests VLR be available.
In einem weiteren Schritt SD wird das virtuelle Link VL bzw. die virtuelle Verbindung zwischen dem ersten Netzwerkknoten KN1 und dem zweiten Netzwerkknoten KN2 über den selektierten in Bezug auf die Service-Qualitätsanforderungen, S-QoS, der VL-Anfrage VLR geeignetsten Signalpfad SPopt aufgebaut. Der Aufbau der virtuellen Verbindung VL erfolgt vorzugsweise gesteuert durch einen Netzwerk-Controller, insbesondere einen SDN-Controller des physikalischen Netzwerkes.In a further step S D becomes the virtual link VL or the virtual connection between the first network node KN1 and the second network node KN2 over the selected in terms of service quality requirements, S-QoS , the VL request VLR most suitable signal path SP opt built up. The construction of the virtual connection VL is preferably controlled by a network controller, in particular an SDN controller of the physical network.
Eine VL-Anfrage bzw. ein Virtual Link Request VLR umfasst mindestens eine Service-Qualitätsanforderung S-QoS. Üblicherweise umfasst eine VL-Anfrage mehrere Service-Qualitätsanforderungen S-QoS bzw. Service-Qualitätsanforderungsattribute. Bei dem erfindungsgemäßen Verfahren kann bei einer möglichen Ausführungsform zwischen zwei unterschiedlichen Arten von Service-Qualitätsanforderungen S-QoS unterschieden werden. Die Service-Qualitätsanforderungen S-QoS umfassen bei dieser Ausführungsform einerseits additive Netzwerkressourcenanforderungen und andererseits nicht-additive Netzwerkressourcenanforderungen, die an die physikalischen Netzwerkressourcen des Netzwerkes entlang des virtuellen Links VL gestellt werden. Die additiven Netzwerkressourcenanforderungen beziehen sich dabei auf Service-Qualitätsanforderungen S-QoS der VL-Anfrage, VLR, die durch verschiedene physikalische Netzwerkressourcen entlang des Signalpfades SP des virtuellen Links VL aggregiert bzw. insgesamt zu erfüllen sind. Diese additiven Netzwerkressourcenanforderungen umfassen beispielsweise einen Hop Count H, eine maximal zulässige Signalverzögerung bzw. Delay D und einen maximal zulässigen Signaljitter J. Der Hop Count H ist dabei die Anzahl der Netzwerkknoten KN zwischen dem ersten Netzwerkknoten KN1 am Anfang des virtuellen Links VL und dem zweiten Netzwerkknoten KN2 am Ende des virtuellen Links VL. Die maximal zulässige Signalverzögerung Dmax umfasst die Summe aller Signalverzögerungen D, die durch Knoten KN oder physikalische Verbindungen innerhalb des Netzwerks entlang des virtuellen Links VL, d. h. zwischen dem ersten Netzwerkknoten KN1 am Anfang des virtuellen Links VL und dem zweiten Netzwerkknoten KN2 am Ende des virtuellen Links VL generiert werden. Die Signalverzögerung D stellt die maximal tolerierbare Signalverzögerung dar, die durch die verteilte Anwendung bzw. Applikationen noch tolerierbar ist. Jenseits der maximal zulässigen Signalverzögerung Dmax kann die Applikation bzw. Anwendung, insbesondere die Echtzeitanwendung, beispielsweise nicht mehr den Inhalt der Datenpakete DP, die über das physikalische Netzwerk übertragen werden, verwenden bzw. berücksichtigen, da die Datenpakete DP als veraltet betrachtet werden.A VL request or a Virtual Link Request VLR includes at least one service quality requirement S-QoS , Typically, a VL request includes multiple service quality requirements S-QoS or service quality requirement attributes. In the method according to the invention, in one possible embodiment, between two different types of service quality requirements S-QoS be differentiated. The service quality requirements S-QoS In this embodiment, on the one hand, there are additive network resource requirements and, on the other hand, non-additive network resource requirements associated with the physical network resources of the network along the virtual link VL be put. The additive network resource requirements refer to service quality requirements S-QoS the VL request, VLR caused by different physical network resources along the signal path SP of the virtual link VL aggregated or to be fulfilled in total. These additive network resource requests include, for example, a hop count H, a maximum allowable signal delay, or delay D and a maximum allowable signal jitter J , The hop count H is the number of network nodes KN between the first network node KN1 at the beginning of the virtual link VL and the second network node KN2 at the end of the virtual link VL , The maximum permissible signal delay D max includes the sum of all signal delays D passing through knots KN or physical connections within the network along the virtual link VL ie between the first network node KN1 at the beginning of the virtual link VL and the second network node KN2 at the end of the virtual link VL to be generated. The signal delay D represents the maximum tolerable signal delay, which is still tolerable by the distributed application or applications. Beyond the maximum allowable signal delay D max the application or application, in particular the real-time application, for example, no longer the content of the data packets DP that are transmitted over the physical network use or consider, as the data packets DP to be considered obsolete.
Der Signaljitter J stellt einen maximal zulässigen Signaljitter Jmax bzw. eine maximal zulässige Signalverzögerungsvariation des von dem ersten Netzwerkknoten KN1 zu dem zweiten Netzwerkknoten KN2 übertragenen Signals dar. Die additive Netzwerkressourcenanforderung hinsichtlich des maximal zulässigen Signaljitters J ist mit der maximal zulässigen Verzögerung und der minimal erlaubten Verzögerung verknüpft. Die minimal zulässige Signalverzögerung muss erfüllt sein, ansonsten wird der empfangene Dateninhalt als zu früh ankommend betrachtet.The signal jitter J provides a maximum allowable signal jitter J max or a maximum allowable signal delay variation of the first network node KN1 to the second network node KN2 transmitted signal. The additive Network resource request for the maximum allowable signal jitter J is linked to the maximum allowable delay and the minimum allowable delay. The minimum allowable signal delay must be met, otherwise the received data content is considered to arrive too early.
Neben den additiven Netzwerkressourcenanforderungen, d. h. Hop Count H, Signalverzögerung D und Signaljitter J, bestehen nicht-additive Netzwerkressourcenanforderungen. Die nicht-additiven Netzwerkressourcenanforderungen beziehen sich auf Service-Qualitätsanforderungen S-QoS, die durch physikalische Netzwerkressourcen entlang des Signalpfades SP des virtuellen Links VL jeweils individuell zu erfüllen sind. Die nicht-additiven Netzwerkressourcenanforderungen weisen bei einer möglichen Ausführungsform eine minimal geforderte Bandbreite B jeder physikalischen Netzwerkverbindung zwischen zwei Netzwerkknoten entlang des Signalpfades SP des virtuellen Links VL auf. Weiterhin weisen die nicht-additiven Netzwerkressourcenanforderungen bei einer möglichen Ausführungsform eine maximale Verbindungsverlustwahrscheinlichkeit (Loss Probability) LP sowie eine maximal zulässige Signalverarbeitungsenergie bzw. Signalverarbeitungsleistung (Processing Power) PP eines Netzwerkknotens KN im Rahmen bzw. entlang des Signalpfades SP des virtuellen Links VL auf.In addition to the additive network resource requirements, ie hop count H , Signal delay D and signal jitter J , there are non-additive network resource requirements. The non-additive network resource requirements relate to service quality requirements S-QoS caused by physical network resources along the signal path SP of the virtual link VL must be fulfilled individually. The non-additive network resource requirements in one possible embodiment have a minimum required bandwidth B every physical network connection between two network nodes along the signal path SP of the virtual link VL on. Furthermore, in one possible embodiment, the non-additive network resource requirements have a maximum connection loss probability (loss probability) LP and a maximum allowable signal processing power or signal processing power (Processing Power) PP a network node KN in the frame or along the signal path SP of the virtual link VL on.
Bei einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens werden die möglichen Kandidaten-Signalpfade K-SP, welche die Service-Qualitätsanforderungen S-QoS erfüllen, mittels eines gespeicherten QoS-Datenmodells ermittelt bzw. berechnet. Die Berechnung der möglichen Kandidaten-Signalpfade K-SP erfolgt dabei vorzugsweise in Echtzeit zur Erzeugung einer Kandidaten-Signalpfadliste im Schritt SB. Das gespeicherte QoS-Datenmodell reflektiert die zur Verfügung gestellten Technologien des Netzwerkes. Das QoS-Datenmodell berücksichtigt die folgenden Aspekte. Das QoS-Datenmodell kann bei einer möglichen Ausführungsform die Kapazität und den Durchsatz eines Netzwerkknotens KN pro Link L und/oder pro Ausgangsport P des Netzwerkknotens KN berücksichtigen. Ferner wird das Schaltverhalten der Netzwerkknoten KN innerhalb des physikalischen Netzwerkes PHY-NW modelliert. Daten bzw. Datenpakete können durch den Netzwerkknoten KN entweder sofort durchgeschaltet werden oder zunächst zwischengespeichert werden und anschließend an einen anderen Netzwerkknoten KN weitergeleitet werden. Weiterhin kann das Datenmodell abbilden, wie viele Queues Q bzw. Warteschlangen an jedem Port P, insbesondere jedem Ausgangsport eines Netzwerkknotens KN, vorgesehen sind und welcher Vorschrift verschiedene Ausgangswarteschlangen folgen, die Zugriff auf einen einzelnen Ausgangsport des Netzwerkknotens KN haben. Beispielsweise kann berücksichtigt werden, wie verschiedene Warteschlangen Q mehrere Datenpakete DP auf ein einzelnes Link L multiplexen. Weiterhin kann das QoS-Datenmodell die Größen der Warteschlangen Q berücksichtigen. Ferner kann die Verfügbarkeit von Schedulern in dem QoS-Datenmodell enthalten sein, welche auf bestimmte Warteschlangen Q wirken. Beispielsweise können sogenannte Credit-based Shapers CBS verwendet werden, um den Anteil einer Bandbreite B, die einer Warteschlange bzw. Queue Q zugewiesen wird, zu begrenzen bzw. zu limitieren. Andererseits kann eine strikte Prioritätsauswahl zwischen den Warteschlangen Q erfolgen, bei der eine Warteschlange Q andere Warteschlangen Q mit niedrigerer Priorität blockieren kann.In a preferred embodiment of the method according to the invention, the possible candidate signal paths K-SP which the service quality requirements S-QoS meet, calculated or calculated by means of a stored QoS data model. The calculation of the possible candidate signal paths K-SP This is preferably done in real time to generate a candidate signal path list in step S B. The stored QoS data model reflects the technologies provided by the network. The QoS data model considers the following aspects. The QoS data model may, in one possible embodiment, increase the capacity and throughput of a network node KN per link L and / or per output port P of the network node KN account. Furthermore, the switching behavior of the network node KN within the physical network PHY-northwest modeled. Data or data packets can through the network node KN either be switched through immediately or be cached first and then to another network node KN to get redirected. Furthermore, the data model can map how many queues Q or queues at each port P , in particular each output port of a network node KN , and which rule is followed by different output queues that access a single output port of the network node KN to have. For example, it may take into account how different queues Q several data packets DP on a single link L multiplex. Furthermore, the QoS data model may be the sizes of the queues Q account. Furthermore, the availability of schedulers may be included in the QoS data model, which depends on particular queues Q Act. For example, so-called credit-based shapers CBS used to be the percentage of a bandwidth B that is a queue or queue Q is assigned, limit or limit. On the other hand, strict priority selection can be made between the queues Q done at which a queue Q other queues Q with lower priority.
Das QoS-Datenmodell berücksichtigt ferner die Verfügbarkeit eines Klassifikationssystems und einer Zugangskontrolle, um sicherzustellen, dass Rahmen bzw. Datenrahmen, die zu einer bestimmten virtuellen Organisation gehören, auf diejenigen Ressourcen und Links L gemappt werden, welche für das virtuelle Netzwerk ausgewählt wurden. Weiter kann die Verfügbarkeit eines Verzögerungsschätzelementes in dem QoS-Modell widergespiegelt werden, welches Teil einer virtuellen Netzwerk-Embedding-Funktionalität bildet und das in der Lage ist, eine maximale Signalverzögerung Dmax zu berechnen, welche nach einer vorgegebenen Anforderung entlang eines bestimmten Knotens KN nach Wahl eines gegebenen Ausgangslinks auftritt und/oder einer vorgegebenen Warteschlange Q auftritt und eine bestimmte Warteschlangen- und Scheduling-Strategie verfolgt. Dieselbe Funktion sollte zur Verfügung stehen, um eine minimale Verzögerung zu berechnen, die in demjenigen Netzwerkknoten auftreten kann, um demzufolge eine maximale Verzögerung D und einen maximalen Signaljitter Jmax zu schätzen, der durch den Netzwerkknoten hervorgerufen wird.The QoS data model also takes into account the availability of a classification system and access control to ensure that frames belonging to a particular virtual organization address those resources and links L be mapped, which were selected for the virtual network. Further, the availability of a delay estimator may be reflected in the QoS model, which forms part of virtual network embedding functionality and which is capable of providing maximum signal delay D max to calculate which one according to a given request along a particular node KN at the option of a given output link occurs and / or a predetermined queue Q occurs and follows a particular queue and scheduling strategy. The same function should be available to calculate a minimum delay that can occur in that network node, hence a maximum delay D and a maximum signal jitter J max appreciated by the network node.
Das Ergebnis des Embedding-Prozesses eines virtuellen Links VL besteht in einem Satz von einigen Ende-zu-Ende (E2E) physikalischen Signalpfaden SP, deren Netzwerkknoten KN und jeweiligen physikalischen Links L selektiert werden können. Zudem kann für jeden physikalischen Link L, d. h. für jedes Ausgangsport eines Netzwerkknotens KN, bei einer möglichen Ausführungsform eine Warteschlange Q selektiert werden. Die finale Ende-zu-Ende-Signalverzögerungsschätzung erfolgt bei einer möglichen Ausführungsform, indem man alle Signalverzögerungen D und alle Signaljitter-Komponenten J entlang der möglichen Signalpfade SP sammelt, um eine Liste von Signalverzögerungen D und Signaljitter J pro virtuellem Ende-zu-Ende-Signalpfad SP bereitzustellen. Es kann eine Funktion vorgesehen werden, um alle Ende-zu-Ende-Embedding-Lösungen zusammenzustreichen bzw. zu beschneiden (prune). Dabei werden die gewählten physikalischen Signalpfade SP derart selektiert, dass sie den angeforderten QoS-Charakteristika der Anforderungen des virtuellen Links VL entsprechen bzw. diese erfüllen.The result of the embedding process of a virtual link VL consists of a set of some end-to-end (E2E) physical signal paths SP , their network nodes KN and respective physical links L can be selected. In addition, for every physical link L ie for each output port of a network node KN in one possible embodiment, a queue Q be selected. The final end-to-end signal delay estimation is done in one possible embodiment by taking all signal delays D and all signal jitter components J along the possible signal paths SP collects a list of signal delays D and signal jitter J per virtual end-to-end signal path SP provide. A function can be provided to prune all end-to-end embedding solutions. In the process, the selected physical signal paths become SP selected so that they requested QoS characteristics of the requirements of the virtual link VL meet or meet this.
Eine VL-Anfrage bzw. ein VL-Request VLR kann bei einer möglichen Ausführungsform übermittelt werden, indem man eine zentralisierte Online-Funktion nutzt, die auf einem SDN-Controller gehostet bzw. implementiert ist. Der SDN-Controller stellt dabei aktuelle physikalische Netzwerkattribute und Fähigkeiten des Netzwerkes bereit, um es der Embedding-Funktion zu ermöglichen, Mapping-Lösungen für die VL-Requests VLRs in Echtzeit zu berechnen. Jeder VL-Request VLR kann als ein Service bzw. eine Dienstleistung betrachtet werden, die auf dem physikalischen Netzwerk PHY-NW konfigurierbar ist, nachdem eine mögliche Mapping-Lösung gefunden bzw. berechnet worden ist.A VL request or a VL request VLR can be communicated in one possible embodiment by using a centralized online function hosted on an SDN controller. The SDN controller provides up-to-date physical network attributes and capabilities of the network to enable the embedding function, mapping solutions for the VL requests VLR to calculate in real time. Every VL request VLR can be considered as a service or service on the physical network PHY-northwest is configurable after a possible mapping solution has been found or calculated.
3 veranschaulicht mögliche Signalpfade SP innerhalb des in 1 dargestellten Graphen eines beispielhaften Netzwerkes PHY-NW. Der erste VL-Request VL1 möchte eine virtuelle Netzwerkverbindung zwischen dem ersten Netzwerkknoten A (Ausgangsknoten KN1) und dem dritten Netzwerkknoten C als Zielknoten (KN2) herstellen und fordert dabei eine Bandbreite B von 10, eine maximale Verzögerung D von 15 und einen maximalen Hop Count H von 5 sowie einen maximalen Signaljitter J von 5. Um diese Service-Qualitätsanforderungen S-QoS zu erfüllen, kommen verschiedene Signalpfade SP in Betracht, nämlich ein erster Signalpfad ABC über den Netzwerkknoten B, einen zweiten direkten Signalpfad AC und einen dritten Signalpfad über den Netzwerkknoten D ABC sowie ein Signalpfad SP über den Netzwerkknoten D und den Netzwerkknoten E ADEC, wie in 3 dargestellt. 3 illustrates possible signal paths SP within the in 1 shown graphs of an exemplary network PHY-northwest , The first VL request VL1 wants a virtual network connection between the first network node A (Output node KN1 ) and the third network node C as destination node ( KN2 ) and demands a bandwidth B out of 10, a maximum delay D of 15 and a maximum hop count H of 5 as well as a maximum signal jitter J of 5. To meet these service quality requirements S-QoS to meet, come different signal paths SP into consideration, namely a first signal path ABC over the network node B , a second direct signal path AC and a third signal path via the network node D ABC and a signal path SP via the network node D and the network node e ADEC , as in 3 shown.
Jeder Signalpfad SP hat in der 3 dargestellten Beispiel die Bedingung zu erfüllen, dass die berechnete Quality of Service QoS minus die in der VLR geforderten Verzögerung D kleiner oder gleich dem Signaljitter J ist (QoS - D ≤ J).Every signal path SP has in the 3 Example shown to fulfill the condition that the calculated Quality of Service QoS minus those in the VLR required delay D less than or equal to the signal jitter J is (QoS - D ≤ J).
Für die zweite VL-Anfrage VL2 kommen die Signalpfade ABC, AC und ADEC in Frage. Für die dritte und vierte VL-Anfrage VL3, VL4 kommt nur der Signalpfad AC in Frage, d. h. die direkte Verbindung zwischen dem Netzwerkknoten A und dem Netzwerkknoten C aufgrund der strikten Anforderung hinsichtlich der Signalverzögerung, nämlich D < 6. Demnach stellen die dritte und vierte VL-Anfrage VL3, VL4 die kritischsten VL-Anfragen dar.For the second VL request VL2 come the signal paths ABC . AC and ADEC in question. For the third and fourth VL request VL3 . VL4 only the signal path comes AC in question, ie the direct connection between the network node A and the network node C due to the strict signal delay requirement, namely D <6. Thus, the third and fourth VL requests VL3 . VL4 the most critical VL requests.
Die Reihenfolge der durch einen Netzwerk-Controller, beispielsweise SDN-Controller, empfangenen VL-Anfragen VLR ist nicht vorhersehbar und erfolgt in Echtzeit online. In dem dargestellten Beispiel erhält der SDN-Controller zunächst die VL-Anfrage VL1. Nach Empfang dieser ersten VL-Anfrage VL1 werden zunächst alle möglichen Signalpfade SP zwischen dem Netzwerkknoten A (Ausgangsknoten KN1) und dem Netzwerkknoten C (Zielknoten KN2) berechnet, die die Service-Signalanforderungen S-QoS dieser ersten VL-Anfrage VL1 hinsichtlich Hop Count H, Verzögerung D, Bandbreite B und Jitter J erfüllen, d. h. Bandbreite B 10, Signalverzögerung D 15, Hop Count H 5 und Jitter J 5. Dann wird derjenige Signalpfad SP ausgewählt bzw. selektiert, bei dem die Differenz der aktuellen Signalpfadverzögerung D zu der Verzögerungsanforderung der VL-Anfrage VL1 minimal ist und der gleichzeitig ein geringeres oder zumindest gleiches Signaljitter J besitzt wie das geforderte Signaljitter J. In einer Situation, bei der der Signaljitter J nicht im Fokus steht, wird lediglich derjenige Signalpfad gewählt, der die minimale Verzögerungsdifferenz D besitzt. In diesem Falle wird für die Anfrage VL1 der Signalpfad ADEC gewählt bzw. selektiert. Anschließend wird derselbe Ansatz bei Ankunft der übrigen VL-Anfragen VL2, VL3 und VL4 verfolgt, wobei dies in den Signalpfaden ABC und AC resultiert, die für die jeweilige VL-Anfrage ausgewählt bzw. selektiert werden.The order of VL requests received by a network controller, such as SDN controllers VLR is unpredictable and takes place online in real time. In the example shown, the SDN controller first receives the VL request VL1 , Upon receipt of this first VL request VL1 First of all all possible signal paths SP between the network node A (Output node KN1 ) and the network node C (destination node KN2 ) which calculates the service signal requirements S-QoS this first VL request VL1 in terms of hop count H, delay D , Bandwidth B and jitter J fulfill, ie bandwidth B 10 , Signal delay D 15 , Hop count H 5 and jitter J 5 , Then that signal path becomes SP selected or selected at which the difference of the current signal path delay D to the delay request of the VL request VL1 is minimal and at the same time a lower or at least the same signal jitter J owns as the required signal jitter J , In a situation where the signal jitter J is not in focus, only that signal path is selected, the minimum delay difference D has. In this case will be for the request VL1 the signal path ADEC selected or selected. Subsequently, the same approach will be used on arrival of the remaining VL requests VL2 . VL3 and VL4 followed, this being in the signal paths ABC and AC results that are selected or selected for the respective VL request.
Mithilfe des erfindungsgemäßen Ansatzes ist es möglich, alle VL-Requests VLRs zu erfüllen und gleichzeitig eine maximale Bandbreite B zu nutzen, welche erforderlich ist, um den Netzwerkknoten A (Ausgangsknoten KN1) und Netzwerkknoten C (Ziel- bzw. Destinationsknoten KN2) in zwei disjunkte Graphen zu trennen, wie es beispielsweise aus der minimalen Schnittmengengraphen-Theorie bekannt ist.Using the approach according to the invention, it is possible to all VL requests VLR to meet and at the same time a maximum bandwidth B to use which is required to the network node A (Output node KN1 ) and network nodes C (Destination or destination node KN2 ) into two disjoint graphs, as is known, for example, from the minimal intersection graph theory.
Bei dem erfindungsgemäßen Verfahren wird zunächst sichergestellt, dass die Endknoten der VL-Anfrage, welche sich innerhalb des physikalischen Graphen des physikalischen Netzwerkes PHY-NW befinden, wie es beispielsweise in 1 dargestellt ist, und die VL-Anfrage im Zusammenhang mit allen Service-Qualitätsanforderungen S-QoS erfüllt werden kann, wobei beispielsweise zusätzliche Nebenbedingungen erfüllt werden können, insbesondere die Datenverarbeitungsleistung eines Netzwerkknotens KN oder dessen Speicherkapazität.In the method according to the invention, it is first ensured that the end nodes of the VL request, which are within the physical graph of the physical network PHY-northwest as it is for example in 1 is shown, and the VL request related to all service quality requirements S-QoS can be met, for example, additional constraints can be met, in particular the data processing performance of a network node KN or its storage capacity.
Anschließend wird bei einer möglichen Ausführungsform die Distanz aller eingehenden Kanten des Knotens KN, der das Ziel der virtuellen Verbindung bzw. des virtuellen Links VL bei demjenigen Knoten ausführt, welcher die Quelle bzw. den Ausgangsknoten des virtuellen Links VL beinhaltet, berechnet und die berechnete Distanz in einer Distance Map gespeichert, wobei die Kante den Schlüssel (key) und der Abstand bzw. Distanz den Wert (value) bildet.Subsequently, in one possible embodiment, the distance of all incoming edges of the node KN , the target of the virtual connection or the virtual link VL at the node that executes the source or output node of the virtual link VL contains, calculates and stores the calculated distance in a distance map, where the edge is the key and the distance is the value.
Durch die Verwendung dieser Minimaldistanz-Map ist es möglich, eine Liste von Kandidaten-Signalpfaden K-SP im Schritt SB des erfindungsgemäßen Verfahrens bei einer möglichen Ausführungsform wie folgt zu berechnen.By using this minimum distance map it is possible to get a list of candidate signal paths K-SP in step S B of inventive method in a possible embodiment to calculate as follows.
Zunächst werden alle Ausgangskanten des Ausgangs- bzw. Quellknotens ermittelt. Für jede Ausgangskante wird geprüft, ob der Zielknoten der Kante gleich demjenigen Knoten ist, welcher das Ziel bzw. die Destination des virtuellen Links VL hostet. Dies ist auch in dem Ablaufdiagramm gemäß 4 dargestellt. Nach einem Startschritt S0 wird in einem Schritt S1 zunächst ein Ausgangs- bzw. Source-Knoten KN1 und der Ziel- bzw. Endknoten KN2 der VL-Anfrage VLR auf physikalische Zielknoten des physikalischen Netzwerkes gemappt. In einem weiteren Schritt S2 wird geprüft, ob das Knoten-Mapping erfolgreich durchgeführt wurde oder nicht. Falls dies nicht der Fall ist, wird in einem Schritt S3 eine Suche durchgeführt und die Distanz-Map DM aller eingehenden Kanten zu dem Zielknoten berechnet. Anschließend werden im Schritt S4 zunächst alle abgehenden Kanten des gesuchten Knotens ermittelt bzw. ausgelesen und für jede Ausgangskante geprüft, ob der Destinationsknoten dem Zielknoten bzw. Destinationsknoten KN2 des virtuellen Links VL entspricht. Im Schritt S5 wird abgefragt, ob die Ausgangskante der Destination des virtuellen Links VL entspricht oder nicht. Falls dies der Fall ist, wird ein Signalpfad SP im Schritt S6 generiert und die Bandbreite B, die Signalverzögerung D sowie der Hop Count H der virtuellen Verbindung VL verifiziert. Im Schritt S7 wird festgestellt, ob alle Verifikationen erfolgreich waren und wenn dies der Fall ist, wird der Signalpfad SP im Schritt S8 einer Liste von vollständigen Kandidaten-Signalpfaden K-SP hinzugefügt. In einem weiteren Schritt S9 wird abgefragt, ob eine Queue unvollständiger Pfade leer ist oder nicht. Man wandert anschließend rückwärts durch die Queue bzw. Warteschlange unvollständiger Signalpfade im Schritt S10, wo man für jeden unvollständigen Signalpfade SP die folgenden Schritte vornimmt. Es wird im S10 zunächst die letzte Kante des Signalpfades gewonnen und anschließend alle abgehenden Kanten des Destinationsknotens der letzten Kante ermittelt. Für jede ausgehende Kante wird geprüft, ob der Destinationsknoten dieser abgehenden Kante der gleiche ist wie der Destinationsknoten des virtuellen Links VL. Dies erfolgt bei dem in 4 dargestellten Ablaufdiagramm im Schritt S11. Falls die Prüfung im Schritt S11 einen wahren Wert ergibt, wird die Kante des unvollständigen Signalpfades hinzugefügt und der Signalpfad als vollständig markiert. Anschließend wird die Bandbreitenanforderung des Signalpfades, der Hop Count H und die Signalverzögerungsanforderung verifiziert. Falls alle Verifikationen erfolgreich sind bzw. gültig, wird der Signalpfad SP einer Liste von vollständigen Kandidaten-Signalpfaden K-SP hinzugeführt und im umgekehrten Fall wird der Signalpfad SP zurückgewiesen. Im umgekehrten Fall, falls die Destination nicht die gleiche ist wie die Destination des virtuellen Links VL wird im Schritt S12 geprüft, ob die Kante sich in der Distance Map DM befindet. Falls dies der Fall ist, wird diese Kante dem unvollständigen Signalpfad im Schritt S13 hinzugefügt und als neuer unvollständiger Signalpfad markiert und die Queue bzw. Warteschlange Q wird den unvollständigen Signalpfaden hinzugefügt. Diese Schritte werden so lange wiederholt, bis keine unvollständigen Signalpfade mehr in der Warteschlange Q vorhanden sind. Anschließend wird die Liste der vollständigen Kandidaten-Signalpfade K-SP zurückgegeben bzw. ausgegeben.First, all output edges of the source or source node are determined. For each exit edge, a check is made as to whether the destination node of the edge is equal to the node that defines the destination or destination of the virtual link VL hosts. This is also in the flowchart according to 4 shown. After a start step S0 gets in one step S1 first an output or source node KN1 and the destination or end node KN2 the VL request VLR mapped to physical destination nodes of the physical network. In a further step S2 it is checked whether the node mapping was successfully completed or not. If this is not the case, in one step S3 carried out a search and the distance map DM all incoming edges to the destination node. Subsequently, in the step S4 First, all outgoing edges of the searched node are determined or read and checked for each exit edge, whether the destination node the destination node or destination node KN2 of the virtual link VL equivalent. In step S5 it is queried whether the exit edge of the destination of the virtual link VL corresponds or not. If so, a signal path is established SP in step S6 generated and the bandwidth B, the signal delay D as well as the hop count H the virtual connection VL Verified. In step S7 it is determined if all verifications were successful and if so, the signal path SP in step S8 a list of complete candidate signal paths K-SP added. In a further step S9 it is queried whether a queue of incomplete paths is empty or not. You then move backwards through the queue or queue of incomplete signal paths in the step S10 where to look for any incomplete signal paths SP take the following steps. It is in the S10 First the last edge of the signal path is obtained and then all outgoing edges of the destination node of the last edge are determined. For each outgoing edge, it is checked whether the destination node of this outgoing edge is the same as the destination node of the virtual link VL , This is done at the in 4 illustrated flowchart in step S11 , If the test in step S11 gives a true value, the edge of the incomplete signal path is added and the signal path marked as complete. Then the bandwidth requirement of the signal path, the Hop Count H and verify the signal delay request. If all verifications succeed or become valid, the signal path becomes SP a list of complete candidate signal paths K-SP added and in the opposite case, the signal path SP rejected. In the opposite case, if the destination is not the same as the destination of the virtual link VL is in the step S12 Check if the edge is in the distance map DM located. If so, this edge becomes the incomplete signal path in step S13 is added and marked as a new incomplete signal path and the queue or queue Q is added to the incomplete signal paths. These steps are repeated until there are no incomplete signal paths in the queue Q available. Subsequently, the list of complete candidate signal paths K-SP returned or issued.
Nachdem man die Liste der vollständigen Kandidaten-Signalpfade K-SP erhalten hat, welche die Anforderungen der VL-Anfrage VLR erfüllen, kann der beste bzw. geeignetste Signalpfad SPopt bei einer möglichen Ausführungsform beispielsweise basierend auf zwei Optimisierungszielen D, J abgeleitet bzw. selektiert werden. Wie in dem Ablaufdiagramm gemäß 4 dargestellt, wird beispielsweise im Schritt S14 für die Liste der Kandidaten-Signalpfade K-SP ein Optimierungsziel selektiert, beispielsweise die Signalverzögerung D oder der Signaljitter J. Im Schritt S15 wird geprüft, welches Optimierungsziel selektiert wurde, nämlich Verzögerung bzw. Delay D oder die Signalverzögerung J. Falls das Optimierungsziel die Signalverzögerung D ist, kann man bei einer möglichen Ausführungsvariante im Schritt S16 wie folgt vorgehen. Es wird ein Minimalabweichungswert gegenüber dem Wert unendlich (infinity) eingestellt, wobei ein optimaler Signalpfad SPopt eine Abweichung von null (Δ = 0) besitzt. Dies bedeutet, dass die verschiedenen Signalpfade SP dementsprechend sortiert bzw. gerankt werden, inwieweit sie die maximale Signalverzögerung D erfüllen. Anschließend wird der schlechteste Signalpfad (mit höchstem Hop Count H) dahingehend geprüft, ob er die Signaljitter-Bedingung bzw. -Beschränkung erfüllt. Für jeden Kandidaten-Signalpfad K-SP wird die Abweichung berechnet. Diese entspricht der Differenz der Verzögerungsanforderung und der Verzögerung des Kandidaten-Signalpfades. Falls die Abweichung kleiner oder gleich ist als die minimale Abweichung, kann die minimale Abweichung auf diese Abweichung eingestellt werden und der optimale Signalpfad wird mit dem Kandidaten-Signalpfad gleichgesetzt. Dieser Schritt S16 wird wiederholt, bis der Kandidaten-Signalpfad K-SP mit der geringsten Abweichung erhalten wird.After getting the list of complete candidate signal paths K-SP has received the requirements of the VL request VLR meet the best or most appropriate signal path SP opt in one possible embodiment, for example, based on two optimization goals D . J derived or selected. As in the flowchart according to 4 is shown, for example, in step S14 for the list of candidate signal paths K-SP an optimization target selected, for example, the signal delay D or the signal jitter J , In step S15 it is checked which optimization target has been selected, namely delay or delay D or the signal delay J , If the optimization goal is the signal delay D is, you can in a possible embodiment in the step S16 proceed as follows. A minimum deviation value is set against infinity, with an optimal signal path SP opt has a deviation of zero (Δ = 0). This means that the different signal paths SP accordingly sorted or ranked, to what extent they the maximum signal delay D fulfill. Then the worst signal path (with highest hop count H ) is checked to see if it satisfies the signal jitter condition or constraint. For each candidate signal path K-SP the deviation is calculated. This corresponds to the difference of the delay request and the delay of the candidate signal path. If the deviation is less than or equal to the minimum deviation, the minimum deviation can be set to this deviation and the optimal signal path is set equal to the candidate signal path. This step S16 is repeated until the candidate signal path K-SP is obtained with the least deviation.
Wird im Schritt S15 festgestellt, dass das Optimierungsziel der Signaljitter J ist, kann bei einer möglichen Ausführungsvariante im Schritt S17 wie folgt vorgegangen werden. Für jeden Kandidaten-Signalpfad K-SP wird der Signaljitter J des Pfades berechnet. Falls der Signaljitter J des Signalpfades SP geringer ist als der Signaljitter, welcher von der VL-Anfrage gefordert wird, wird der Signalpfad SP der neuen Kandidaten-Signalpfadliste hinzugefügt im Schritt S17. Dann wird Schritt S16 auf die verbleibende Kandidaten-Signalpfadliste angewendet.Will in step S15 found that the optimization goal of the signal jitter J is, in a possible embodiment in step S17 proceed as follows. For each candidate signal path K-SP becomes the signal jitter J of the path. If the signal jitter J the signal path SP less than the signal jitter required by the VL request becomes the signal path SP the new candidate signal path list added in step S17 , Then step S16 applied to the remaining candidate signal path list.
Im Schritt S18 wird festgestellt, ob ein optimaler Signalpfad existiert oder nicht. Falls ein optimaler bzw. bester Signalpfad vorliegt, wird der virtuelle Link Request VLR im Schritt S19 embedded und der Prozess endet im Schritt S20.In step S18 it is determined whether an optimal signal path exists or not. If there is an optimal or best signal path, the virtual link request VLR in step S19 embedded and the process ends in a step S20 ,
5 zeigt Möglichkeiten zur Berechnung bereitgestellter Netzwerkressourcen. Die 5 zeigt die Verwendung eines Link Scheduler Queue-Modells eines Tandems eines Schedulers am Ausgang eines Links L. Beispielsweise kann man für ein TSN-VNE den Gebrauch eines Time-Aware-Shapers TAS, eines Credit-Based Shapers CBS oder eines Strict Priority SP Schedulers in Betracht ziehen, wie in 5 dargestellt. 5 zeigt zudem eine einfache Analyse einer Worst-Case-Signalverzögerungsschätzung. 5 shows ways to calculate provided network resources. The 5 shows the use of a link scheduler queue model of a tandem of a scheduler at the output of a link L , For example, one can for one TSN VNE the use of a time-aware shaper TAS , a Credit-Based Shaper CBS or a strict priority SP Consider schedulers, as in 5 shown. 5 also shows a simple analysis of a worst case signal delay estimation.
Eine Ende-zu-Ende-Maximalverzögerung besteht, wenn alle Links L TAS Queues verwenden. Für den Fall eines Store-and-Forward-Mechanismus ist die maximale Queuing- bzw. WarteschlangenVerzögerung pro Hop gleich der neu geforderten Last- bzw. Linkgeschwindigkeit. Die Ende-zu-Ende E2E-Maximalverzögerung ist gleich der Summe der maximalen Warteschlangenverzögerung pro Hop plus der durch Signalverarbeitung hervorgerufenen Verzögerung pro Hop mal der Anzahl der Hops bzw. Netzwerkknoten entlang der Verbindung.An end-to-end maximum delay exists when all links use L TAS queues. In the case of a store-and-forward mechanism, the maximum queuing / queuing delay per hop is equal to the newly requested load or link speed. The end-to-end E2E maximum delay is equal to the sum of the maximum queue delay per hop plus the signal-processing delay per hop times the number of hops or nodes along the connection.
Im Falle eines direkten Weiterleitens (cut-through) ist die Ende-zu-Ende-Maximalverzögerung gleich der angeforderten Last pro Zyklus geteilt durch die Linkgeschwindigkeit V (last) plus der Verarbeitungsverzögerung pro Hop mal Anzahl der Hops.In the case of direct cut-through, the end-to-end maximum delay is equal to the requested load per cycle divided by the link speed V (last) plus the processing delay per hop times the number of hops.
Die Ende-zu-Ende-Maximalverzögerung für den Fall, dass alle Links eine ratengesteuerte CBS-Warteschlange verwenden, ist wie folgt.The end-to-end maximum delay for the case where all links use a rate-driven CBS queue is as follows.
Die maximale Warteschlangenverzögerung pro Hop ist gleich der Summe aller Lastanforderungen, die bereits auf die Warteschlange Q gemappt sind, plus der angeforderten Last geteilt durch die Linkgeschwindigkeit, wobei anschließend die akkumulierte Signalverzögerung von höherrangigen Warteschlangen hinzuaddiert wird.The maximum queue delay per hop is equal to the sum of all load requests already mapped to the queue Q plus the requested load divided by the link speed, and then the accumulated signal delay is added by higher-order queues.
Die Ende-zu-Ende E2E-Maximalverzögerung ist gleich der Summe der maximalen Warteschlangenverzögerung pro Hop entlang aller Hops plus der Datenverarbeitungsverzögerung pro Hop mal Anzahl der Hops.The end-to-end E2E maximum delay is equal to the sum of the maximum queue delay per hop along all hops plus the data processing delay per hop times the number of hops.
Für den Fall, dass eine TAS-Queue eine Verzögerungsvariation pro Hop einführt, die gleich der Clock Drift pro Hop ist, ist die Ende-zu-Ende E2E-Jittersumme (Clock Drift pro Hop für alle Hops) und die Ende-zu-Ende E2E-Minimumverzögerung gleich der Ende-zu-Ende E2E-Maximalverzögerung minus dem E2E-Jitter.In the event that a TAS queue introduces a per-hop delay variation equal to the clock drift per hop, the end-to-end E2E jitter sum is (clock drift per hop for all hops) and end-to-end E2E minimum delay equal to the end-to-end E2E maximum delay minus the E2E jitter.
Im Falle von CBS kann jedes Datenpaket DP des virtuellen Links VL einer Signalverzögerungsvariation pro Hop ausgesetzt sein, die gleich der Warteschlangenverzögerung pro Warteschlange Q entspricht (wobei die Verzögerung durch höherrangige Warteschlangen ignoriert wird) plus der Clock- bzw. Taktsignal-Drift, d. h. pro Hop Jitter = [Summe (aller Lastanforderungen, die bereits auf die Warteschlange gemappt worden sind) plus der neu angeforderten Last]/Linkgeschwindigkeit + Clock Drift. Die Summe aller dieser pro Hop Signaljitter-Werte entlang aller Hops ergibt den Ende-zu-Ende E2E-Signaljitter.In case of CBS can be any data packet DP of the virtual link VL be subject to a signal delay variation per hop equal to the queue delay per queue Q equals (ignoring the higher-order queue delay) plus the clock drift, ie, per-hop jitter = [sum (of all load requests already mapped to the queue) plus the newly requested load] / link speed + Clock drift. The sum of all these per-hop signal jitter values along all hops gives the end-to-end E2E signal jitter.
Das erfindungsgemäße Verfahren bietet verschiedenste Vorteile. Es erhöht die Embedding-Rate von anforderungskritischen Applikationen, insbesondere bei cyberphysikalischen Automations- und Produktionssystemen. Das erfindungsgemäße Verfahren beseitigt die Notwendigkeit für Remapping von bereits verarbeiteten Anforderungen und schafft Platz bzw. Kapazitäten für zukünftige VL-Requests VLR. Darüber hinaus bietet das erfindungsgemäße Verfahren eine optimale Bandbreitenausnutzung. Das Verfahren erhöht zudem die Anzahl von kritischen VL anfordernden Applikationen, die auf dem Netzwerk zugelassen werden. Das Verfahren eignet sich für Echtzeitumgebungen, da die VLR in Echtzeit empfangen werden können. Die Ausführungszeit pro VLR ist ebenfalls gering. Das Verfahren steigert die Ausnutzung bzw. Auslastung des physikalischen Netzwerkes, da mehr virtuelle Links VLs für anforderungskritische Applikationen auf dem Netzwerk zugelassen bzw. aufgebaut werden können.The inventive method offers a variety of advantages. It increases the embedding rate of mission-critical applications, especially in cyber-physical automation and production systems. The method of the invention eliminates the need for remapping already processed requests and provides space or capacity for future VL requests VLR , In addition, the inventive method provides optimum bandwidth utilization. The method also increases the number of critical VL requesting applications that are allowed on the network. The method is suitable for real-time environments because the VLR can be received in real time. The execution time per VLR is also low. The method increases the utilization of the physical network because more virtual links VLs can be approved or set up for request-critical applications on the network.