Nätverkskalkyl

Nätverkskalkyl är "en uppsättning matematiska resultat som ger insikter i konstgjorda system som samtidiga program , digitala kretsar och kommunikationsnätverk ." Nätverkskalkyl ger ett teoretiskt ramverk för att analysera prestandagarantier i datornätverk . När trafik flyter genom ett nätverk är den föremål för begränsningar som åläggs av systemkomponenterna, till exempel:

länkkapacitet _
trafikformare ( läckande hinkar )
trängselkontroll
bakgrundstrafik

Dessa begränsningar kan uttryckas och analyseras med nätverkskalkylmetoder. Begränsningskurvor kan kombineras med hjälp av faltning under min-plus algebra . Nätverkskalkyl kan också användas för att uttrycka trafikens ankomst- och avgångsfunktioner samt servicekurvor.

Kalkylen använder "alternativa algebror ... för att omvandla komplexa icke-linjära nätverkssystem till analytiskt handhavbara linjära system."

För närvarande finns det två grenar i nätverkskalkyl: en som hanterar deterministiska gränser och en som hanterar stokastiska gränser.

Systemmodellering

Modellering av flöde och server

I nätverkskalkyl modelleras ett flöde som kumulativa funktioner $A$ , där $A(t)$ representerar mängden data (till exempel antal bitar) som skickas av flödet i intervallet $[0,t)$ . Sådana funktioner är icke-negativa och icke-minskande. Tidsdomänen är ofta uppsättningen av icke-negativa reals.

Ankomst- och avgångskurva vid in- och utgång från en server.

$A:\mathbb {R} ^{+}\rightarrow \mathbb {R} ^{+}$

$\forall u,t\in \mathbb {R} ^{+}:u<t\implicerar A(u) \leq A(t)$

En server kan vara en länk, en schemaläggare, en trafikformare eller ett helt nätverk. Den är helt enkelt modellerad som en relation mellan någon kumulativ ankomstkurva $A$ och någon kumulativ avgångskurva $D$ . Det krävs att $A \geq D$ , för att modellera det faktum att avgången av vissa data inte kan inträffa före dess ankomst.

Modellering eftersläpning och fördröjning

Givet viss ankomst- och avgångskurva $A$ och $D$ , kan eftersläpningen vid varje ögonblick $t$ , betecknad $b(A,D,t)$ definieras som skillnaden mellan $A$ och $D$ . Fördröjningen vid $t$ , $d(A,D,t)$ definieras som den minimala tidsperioden så att avgångsfunktionen nådde ankomstfunktionen. När man beaktar hela flödena används det högsta av dessa värden.

Horisontell och vertikal avvikelse mellan kumulativa ankomst- och avgångskurvor

$b(A,D,t):=A(t)-D(t)$

$d(A,D,t):=\inf \left\{d\in \mathbb {R} ^{+}~st~D(t+ d)\geq A(t)\right\}$

$b(A,D):=\sup _{t\geq 0}\left\{A(t) -D(t)\right\}$

$d(A,D):=\sup _{t\geq 0}\left\{\inf \left\{d\in \mathbb {R } ^{+}~st~D(t+d)\geq A(t)\right\}\right\}$

I allmänhet är flödena inte exakt kända, och endast vissa begränsningar på flöden och servrar är kända (som det maximala antalet paket som skickas under en period, den maximala storleken på paket, den minimala länkbandbredden). Syftet med nätverkskalkyl är att beräkna övre gränser för fördröjning och eftersläpning, baserat på dessa begränsningar. För att göra det använder nätverkskalkylen min-plus-algebra.

Min-plus algebra

I filterteori och linjärsystemteori definieras faltningen av två funktioner $f$ och ${\displaystyle g} som$

$(f\ast g)(t):=\int _{0}^{t}f (\tau )\cdot g(t-\tau )d\tau$

I min - plus algebra ersätts summan av den lägsta respektive infimum operatorn och produkten ersätts med summan . Så min-plus faltningen av två funktioner $f$ och $g$ blir

$(f\otimes g)(t):=\inf _{0\leq \ tau \leq t}\left\{f(\tau )+g(t-\tau )\right\}$

se t.ex. definitionen av tjänstekurvor. Konvolution och min-plus faltning delar många algebraiska egenskaper. I synnerhet är båda kommutativa och associativa.

En så kallad min-plus de-faltningsoperation definieras som

$(f\oslash g)(t):=\sup _{\tau \geq 0} \left\{f(t+\tau )-g(\tau )\right\}$

t.ex. som används i definitionen av trafikkuvert.

De vertikala och horisontella avvikelserna kan uttryckas i termer av min-plus-operatorer.

$b(f,g)=(f\oslash g)(0)$

$d(f,g)=\inf\{w:(f\oslash g)(-w)\leq 0\}$

Trafikkuvert

Kumulativa kurvor är verkliga beteenden, okända vid designtillfället. Det som är känt är en viss begränsning. Nätverkskalkyl använder begreppet trafikenvelopp, även känd som ankomstkurvor.

En kumulativ funktion $A$ sägs överensstämma med en envelopp $E$ (även kallad ankomstkurva och betecknad $α$ ), om det för allt $gäller$ att

$E(t)\geq \sup _{\tau \geq 0}\{A(t+\tau )-A(\tau )\}=(A\oslash A)(t).$

Två likvärdiga definitioner kan ges

$\forall t,d\in \mathbb {R} ^{+}:A(t+d) -A(t)\leq E(d)$

()

$A\leq A\otimes E$

()

Således sätter $E$ en övre begränsning på flödet $A$ . En sådan funktion $E$ kan ses som en envelopp som specificerar en övre gräns för antalet flödesbitar sett i varje intervall av längden $d$ som börjar vid ett godtyckligt $t$ , jfr. ekv. ( 1 ).

Servicekurvor

För att tillhandahålla prestandagarantier till trafikflöden är det nödvändigt att specificera en viss minimal prestanda för servern (beroende på reservationer i nätverket, eller schemaläggningspolicy, etc.). Tjänstekurvor ger ett sätt att uttrycka resurstillgänglighet. Det finns flera typer av tjänstekurvor, som svagt strikta noder med variabel kapacitet, etc. Se för en översikt.

Minimal service

Låt $A$ vara ett ankomstflöde, som anländer till ingången av en server, och $D$ vara flödet som avgår vid utgången. Systemet sägs tillhandahålla en enkel minimal tjänstekurva $S$ till paret $(A,B)$ $D(t)\geq (A\otimes S)(t).$ för allt $t$ gäller att

Strikt minimal service

Låt $A$ vara ett ankomstflöde, som anländer till ingången av en server, och $D$ vara flödet som avgår vid utgången. En eftersläpningsperiod är ett intervall $I$ så att, på valfri $t \in I$ , $A(t)>D(t)$ .

Systemet sägs ge en strikt minimal servicekurva $S$ till paret $(A,B)$ iff, $\forall s,t\in \mathbb {R} ^{+}$ , så att $s\leq t$ , om $(s,t]$ är en eftersläpningsperiod, då $D(t)-D(s)\geq S(ts)$ .

Om en server erbjuder en strikt minimal tjänst av kurva $S$ , erbjuder den också en enkel minimal tjänst av kurva $S.$

Grundläggande resultat: Prestandagränser och envelopepropagation

Från trafikkuvert och servicekurvor kan vissa gränser för förseningen och eftersläpningen och ett kuvert för avgångsflödet beräknas.

Låt $A$ vara ett ankomstflöde, som anländer till ingången av en server, och $D$ vara flödet som avgår vid utgången. Om flödet som ett trafikenvelopp $E$ och servern ger en minimal tjänst av kurva $S$ , kan eftersläpningen och fördröjningen begränsas:

$b(A,D)\leq b(E,S)$

$d(A,D)\leq d(E,S)$

Dessutom har avgångskurvan envelopp $E'=E\oslash S$ .

Dessutom är dessa gränser snäva , dvs med tanke på något $E ,$ och $S$ , kan man bygga en ankomst och avgång så att $b(A,D)$ = $b(E,S)$ och $v(A,D)$ = $v(E,S)$ .

Sammankoppling / PBOO

Betrakta en sekvens av två servrar, när utgången från den första är ingången från den andra. Denna sekvens kan ses som en ny server, byggd som sammanlänkningen av de två andra.

Sedan, om den första (resp. andra) servern erbjuder en enkel minimal tjänst $S_{1}$ (resp. $S_{2}$ ), då erbjuder sammanlänkningen av båda en enkel minimal tjänst $S_{e2e}=S_{1}\otimes S_{2}$ .

Sekvens av två servrar

Beviset gör iterativ tillämpning av definitionen av tjänstekurvor $X\geq A\otimes S_{1}$ , $D\geq X\otimes S_{2 }$ och några egenskaper för faltning, isotonicitet ( ${\displaystyle D\geq (X\otimes S_{2})\otimes S_{1}})$ och associativitet ( ${\displaystyle D\geq X\otimes (S_{2}\otimes S_{1})})$ .

Intresset för detta resultat är att fördröjningsgränsen från ände till ände inte är större än summan av lokala fördröjningar: $d(E,S_{2}\otimes S_{1})\leq d(E,S_{1})+d(E\oslash S_{1},S_{2})$ .

Detta resultat kallas Pay burst only once (PBOO).

Verktyg

Det finns flera verktyg baserade på nätverkskalkyl. En jämförelse finns i.

Min-plus beräkning

Det finns flera verktyg och bibliotek ägnade åt min-plus algebra.

Nätverkskalkyltolken är en onlinetolk (min,+) .
Nancy är ett C#-bibliotek som implementerar min-plus- och max-plus-operationer.
MIN-plus ExpRession VERification (Minerve) är ett Coq-bibliotek som används för att kontrollera giltigheten av min-plus-operationer.

Alla dessa verktyg och bibliotek är baserade på de algoritmer som presenteras i.

Nätverksanalysverktyg

DiscoDNC är en akademisk Java-implementering av nätverkskalkylramverket .
RTC Toolbox är en akademisk Java/ MATLAB -implementering av ramverket för realtidskalkyl, en teori som nästan motsvarar nätverkskalkyl.
CyNC - verktyget är en akademisk MATLAB /Symulink-verktygslåda, baserad på toppen av RTC Toolbox . Verktyget utvecklades 2004-2008 och används för närvarande för undervisning vid Aalborg universitet .
RTaW -PEGASE är ett industriverktyg ägnat åt tidsanalysverktyg för switchade Ethernet-nätverk (AFDX, industriellt och fordons-Ethernet), baserat på nätverkskalkyl.
WOPANets är ett akademiskt verktyg som kombinerar nätverkskalkylbaserad analys och optimeringsanalys .
DelayLyzer är ett industriverktyg utformat för att beräkna gränser för Profinet-nätverk.
DEBORAH är ett akademiskt verktyg ägnat åt FIFO-nätverk.
NetCalBounds är ett akademiskt verktyg ägnat åt blinda och FIFO-tandemnätverk.
NCBounds är ett nätverkskalkylverktyg i Python, publicerat under BSD 3-Clause License. Den tar hänsyn till servrar med hastighetsfördröjning och ankomstkurvor för token-bucket. Den hanterar vilken topologi som helst, inklusive cyklisk sådan.
Siemens Network Planner ( SINETPLAN ) använder nätverkskalkyl (bland andra metoder) för att hjälpa till med utformningen av ett PROFINET -nätverk.
experimentell modulär TFA (xTFA) är en Python-kod, stöd för doktorsavhandlingen av Ludovic Thomas

evenemang

WoNeCa workshop är en Workshop on Network Ca lculus . Det arrangeras vartannat år för att samla forskare med intresse för teorin om nätverkskalkyl samt de som vill tillämpa befintliga resultat i nya tillämpningar. Workshopen tjänar också till att främja nätverkskalkylteorin för forskare med intresse för tillämpade kömodeller.

WoNeCa6 , värd av EPFL , är planerad till den 8 och 9 september 2022 i Lausanne, Schweiz. Ring för presentation här .
WoNeCa5 hölls praktiskt taget på grund av covid-19-pandemin den 9 oktober 2020.
WoNeCa4 anordnades i samband med den 19:e internationella GI/ITG-konferensen om mätning, modellering och utvärdering av datorsystem (MMB2018) den 28 februari 2018 i Erlangen, Tyskland.
WoNeCa3 hölls som en del av konferensen MMB & DFT 2016 den 6 april 2016 i Müster, Tyskland.
WoNeCa2 hölls under konferensen MMB & DFT 2014 den 19 mars 2014 i Bamberg, Tyskland.
WoNeCa1 var värd av University of Kaiserslautern och hölls som en del av MMB2012 den 21 mars 2012 i Kaiserslautern, Tyskland.

2018 hölls International Workshop on Network Calculus and Applications (NetCal 2018) i Wien, Österrike som en del av den 30: e internationella teletrafikkongressen (ITC 30).

Böcker, undersökningar och handledningar om nätverkskalkyl

C.-S. Chang: Performance Guarantees in Communications Networks , Springer, 2000.
J.-Y. Le Boudec och P. Thiran: Network Calculus: A Theory of Deterministic Queuing Systems for the Internet , Springer, LNCS, 2001 (tillgänglig online).
A. Bouillard, M. Boyer, E. Le Corronc: Deterministic Network Calculus: From Theory to Practical Implementation , Wiley-ISTE, 2018
Y. Jiang och Y. Liu: Stochastic Network Calculus , Springer, 2008.
A. Kumar, D. Manjunath och J. Kuri: Communication Networking: An Analytical Approach , Elsevier, 2004.
S. Mao och S. Panwar: En undersökning av envelope-processer och deras tillämpningar i kvaliteten på tillhandahållande av tjänster, IEEE Communications Surveys and Tutorials, 8(3):2-20, juli 2006.
M. Fidler: Undersökning av deterministiska och stokastiska tjänstekurvor i nätverkskalkylen , IEEE Communications Surveys and Tutorials, 12(1):59-86, januari 2010.
C. Lin, Y. Deng och Y. Jiang: On application stochastic network calculus , Frontiers Computer Science, 7(6): 924-942, 2013
M. Fidler och A. Rizk: A guide to the stochastic network calculus , IEEE Communications Surveys and Tutorials, 17(1):92-105, mars 2015.
L. Maile, K. Hielscher och R. German: Network Calculus Results for TSN: An Introduction , IEEE Information Communication Technologies Conference(1): 131-140, maj 2020.

Relaterade böcker om max-plus algebra eller om konvex minimering

RT Rockafellar : Convex analysis , Princeton University Press, 1972.
F. Baccelli, G. Cohen, GJ Olsder och J.-P. Quadrat: Synchronization and Linearity: An Algebra for Discrete Event Systems , Wiley, 1992.
VN Kolokol'tsov, Victor P. Maslov: Idempotent Analysis and Its Applications , Springer, 1997. ISBN 0792345096 .

Deterministisk nätverkskalkyl

RL Cruz: A Calculus for Network Delay. Del I: Nätverkselement i isolering och Del II: Nätverksanalys , IEEE Transactions on Information Theory, 37(1):114-141, Jan. 1991.
AK Parekh och RG Gallager: A Generalized Processor Sharing Approach to Flow Control: The Multiple Node Case , IEEE Transactions on Networking, 2 (2):137-150, april 1994.
C.-S. Chang: Stabilitet, kölängd och fördröjning av deterministiska och stokastiska könätverk , IEEE Transactions on Automatic Control, 39(5):913-931, maj 1994.
DE Wrege, EW Knightly, H. Zhang och J. Liebeherr: Deterministiska fördröjningsgränser för VBR-video i paketväxlande nätverk: Grundläggande gränser och praktiska avvägningar , IEEE/ACM Transactions on Networking, 4(3):352-362, jun. 1996.
RL Cruz: SCED+: Efficient Management of Quality of Service Guarantees , IEEE INFOCOM, s. 625–634, mars 1998.
J.-Y. Le Boudec: Application of Network Calculus to Guaranteed Service Networks , IEEE Transactions on Information Theory, 44(3):1087-1096, maj 1998.
C.-S. Chang: On Deterministic Traffic Regulation and Service Guarantees: A Systematic Approach by Filtering , IEEE Transactions on Information Theory, 44(3):1097-1110, maj 1998.
R. Agrawal, RL Cruz, C. Okino och R. Rajan: Performance Bounds for Flow Control Protocols , IEEE/ACM Transactions on Networking, 7(3):310-323, juni 1999.
J.-Y. Le Boudec: Vissa egenskaper hos paketformare med variabel längd , IEEE/ACM Transactions on Networking, 10(3):329-337, juni 2002.
C.-S. Chang, RL Cruz, J.-Y. Le Boudec och P. Thiran: A Min, + System Theory for Constrained Traffic Regulation and Dynamic Service Guarantees , IEEE/ACM Transactions on Networking, 10(6):805-817, dec. 2002.
Y. Jiang: Relationship between garanterad rate server och latens rate server , Computer Networks 43(3): 307-315, 2003.
M. Fidler och S. Recker: Conjugate network calculus: A dual approach som tillämpar Legendre-transformen , Computer Networks, 50(8):1026-1039, juni 2006.
Eitan Altman, Kostya Avrachenkov och Chadi Barakat: TCP-nätverkskalkyl: Fallet med produkt med stor bandbreddsfördröjning , i förfarandet av IEEE INFOCOM, NY, juni 2002.
J. Liebeherr: Duality of the Max-Plus and Min-Plus Network Calculus , Foundations and Trends in Networking 11(3-4): 139-282, 2017.

Nätverkstopologier, feed-forward-nätverk

A. Charny och J.-Y. Le Boudec: Delay Bounds in a Network with Aggregate Scheduling , QoFIS, s. 1–13, sep. 2000.
D. Starobinski, M. Karpovsky och L. Zakrevski: Application of Network Calculus to General Topologies using Turn-Prohibition , IEEE/ACM Transactions on Networking, 11(3):411-421, juni 2003.
M. Fidler: A parameter based admission control for differentiated services networks , Computer Networks, 44(4):463-479, mars 2004.
L. Lenzini, L. Martorini, E. Mingozzi och G. Stea: Tight end-to-end per-flow fördröjningsgränser i FIFO multiplexing sink-tree networks, Performance Evaluation, 63(9-10):956-987, oktober 2006.
J. Schmitt, F. Zdarsky och M. Fidler: Fördröjningsgränser under godtycklig multiplexering: när nätverkskalkyl lämnar dig i sticket ... , Prof. IEEE Infocom, april 2008.
A. Bouillard, L. Jouhet och E. Thierry: Snäva prestationsgränser i den värsta analysen av feed-forward-nätverk, Proc. IEEE Infocom, april 2010.

Mätbaserad systemidentifiering

C. Cetinkaya, V. Kanodia och EW Knightly: Scalable services via egress admission control , IEEE Transactions on Multimedia, 3(1):69-81, mars 2001.
S. Valaee och B. Li: Distribuerad samtalstillträdeskontroll för ad hoc-nätverk, Proc. av IEEE VTC, sid. 1244–1248, 2002.
A. Undheim, Y. Jiang och PJ Emstad. Network Calculus Approach to Router Modeling with External Measures , Proc. av IEEE andra internationella konferensen om kommunikation och nätverk i Kina (Chinacom), augusti 2007.
J. Liebeherr, M. Fidler och S. Valaee: A system-theoretic approach to bandwidth estimering , IEEE Transactions on Networking, 18(4):1040-1053, augusti 2010.
M. Bredel, Z. Bozakov och Y. Jiang: Analysera routerprestanda med hjälp av nätverkskalkyl med externa mätningar, Proc. IEEE IWQoS, juni 2010.
R. Lubben, M. Fidler och J. Liebeherr: Stokastisk bandbreddsuppskattning i nätverk med slumpmässig tjänst , IEEE Transactions on Networking, 22(2):484-497, april 2014.

Stokastisk nätverkskalkyl

O. Yaron och M. Sidi: Performance and Stability of Communication Networks via Robust Exponential Bounds , IEEE/ACM Transactions on Networking, 1(3):372-385, juni 1993.
D. Starobinski och M. Sidi: Stochastically Bounded Burstiness for Communication Networks , IEEE Transactions on Information Theory, 46(1):206-212, Jan. 2000.
C.-S. Chang: Stabilitet, kölängd och fördröjning av deterministiska och stokastiska könätverk, IEEE Transactions on Automatic Control, 39(5):913-931, maj 1994.
R.-R. Boorstyn, A. Burchard, J. Liebeherr och C. Oottamakorn: Statistical Service Assurances for Traffic Scheduling Algorithms , IEEE Journal on Selected Areas in Communications, 18(12):2651-2664, dec. 2000.
Q. Yin, Y. Jiang, S. Jiang och PY Kong: Analys av generaliserad stokastiskt avgränsad bursty trafik för kommunikationsnätverk, IEEE LCN, s. 141–149, nov. 2002.
C. Li, A. Burchard och J. Liebeherr: A Network Calculus with Effective Bandwidth , University of Virginia, teknisk rapport CS-2003-20, nov. 2003.
Y. Jiang: En grundläggande stokastisk nätverkskalkyl , ACM SIGCOMM 2006.
A. Burchard, J. Liebeherr och SD Patek: A Min-Plus Calculus for End-to-end Statistical Service Guarantees, IEEE Transactions on Information Theory, 52(9):4105–4114, sep. 2006.
F. Ciucu, A. Burchard och J. Liebeherr: A Network Service Curve Approach for the Stokastic Analysis of Networks , IEEE/ACM Transactions on Networking, 52(6):2300–2312, juni 2006.
M. Fidler: An End-to-End Probabilistic Network Calculus with Moment Generating Functions , IEEE IWQoS, juni 2006.
Y. Liu, C.-K. Tham och Y. Jiang: A calculus for stochastic QoS analysis , Performance Evaluation, 64(6): 547-572, 2007.
Y. Jiang och Y. Liu: Stochastic Network Calculus , Springer, 2008.

Kalkyl för trådlöst nätverk

M. Fidler: A Network Calculus Approach to Probabilistic Quality of Service Analysis of Fading Channels, Proc. IEEE Globecom, november 2006.
K. Mahmood, A. Rizk och Y. Jiang: På flödesnivåfördröjningen av en spatial multiplexerande MIMO trådlös kanal, Proc. IEEE ICC, juni 2011.
K. Mahmood, M. Vehkaperä och Y. Jiang: Analys av fördröjd begränsad genomströmning av en korrelerad MIMO trådlös kanal, Proc. IEEE ICCCN, 2011.
K. Mahmood, M. Vehkaperä och Y. Jiang: Fördröjningsbegränsad genomströmningsanalys av CDMA med användning av stokastisk nätverkskalkyl, Proc. IEEE ICON, 2011.
K. Mahmood, M. Vehkaperä och Y. Jiang: Prestanda för CDMA-mottagare för flera användare med bursty trafik och fördröjningsbegränsningar, Proc. ICNC, 2012.
Y. Zhang och Y. Jiang: Prestanda för dataöverföring över en Gaussisk kanal med dispersion, Proc. ISWCS, 2012.
H. Al-Zubaidy, J. Liebeherr och A. Burchard: En (min, ×) nätverkskalkyl för multi-hop-fading-kanaler, Proc. IEEE Infocom, s. 1833–1841, april 2013.
K. Zheng, F. Liu, L. Lei, C. Lin och Y. Jiang: Stochastic Performance Analysis of a Wireless Finite-State Markov Channel, IEEE Trans. Wireless Communications 12(2): 782-793, 2013.
J.-w. Cho och Y. Jiang: Fundamentals of the Backoff Process in 802.11: Dichotomy of the Aggregation, IEEE Trans. Information Theory 61(4): 1687-1701, 2015.
M. Fidler, R. Lubben och N. Becker: Capacity–Delay–Error Boundaries: A Composable Model of Sources and Systems , Transactions on Wireless Communications, 14(3):1280-1294, mars 2015.
F. Sun och Y. Jiang: A Statistical Property of Wireless Channel Capacity: Theory and Application , Proc. IFIP Performance, 2017.