Wyznaczanie tras i sterowanie
przepływem

Plan prezentacji



Zasoby w sieciach pakietowych



Wyznaczanie tras a sterowanie przepływem



Zadanie wyznaczania optymalnych tras



Zadanie sterowania przepływem



Łączne zadanie wyznaczania tras i

sterowania przepływem



Równoważność zadań



Funkcje kary



Przykład zadania

Rozdział zasobów w sieciach
pakietowych

 Mechanizmy odpowiedzialne w systemie teleinformatycznym za

rozdział oraz wykorzystanie współdzielonych i ograniczonych

zasobów systemu są zaliczane do trzech grup mechanizmów:

 wyznaczania tras,

 przeciwdziałania przeciążeniom,

 sterowania przepływem.

 Mechanizmy należące do wymienionych trzech grup charakteryzuje

różna funkcjonalność oraz komplementarność.

 Różna

funkcjonalność

wynika

z tego,

że

uaktywnianie

poszczególnych mechanizmów zależy zarówno od sposobu

zarządzania jakością usług w systemie, jak i od stanu sieci oraz

stopnia wykorzystania jej zasobów.



Komplementarność omawianych mechanizmów oznacza, że

warunkiem skutecznego zarządzanie jakością usług w systemie

teleinformatycznym

jest

współistnienie

i

współdziałanie

mechanizmów z omawianych trzech grup.

Sterowanie przepływem i
przeciwdziałanie przeciążeniom

 Zadania przeciwdziałania przeciążeniom i sterowania przepływem

są często łączone, to znaczy że rozwiązanie zadania

przeciwdziałania przeciążeniom definiuje warunki realizacji zadania

sterowania przepływem.

 Sterowanie przepływem, w szerszym rozumieniu, obejmuje

zagadnienia definiowania warunków powstawania przeciążeń oraz

ograniczania ilości ruchu przyjmowanego do obsługi w sieci lub

wybranym jej fragmencie.

 Dlatego też często spotyka się rozwiązania, w których np.

mechanizmy sterowania przepływem pośrednio przeciwdziałają

powstawaniu przeciążeń lub mechanizmy przeciwdziałania

przeciążeniom

pośrednio

spełniają

funkcje

mechanizmów

sterowania przepływem.

 Podobnie

pośrednim

efektem

stosowania

mechanizmów

wyznaczania tras jest zwiększenie odporności sieci na

przeciążenia.

Zadania wyznaczania tras
i przepływów

 Zadania wyznaczania tras i sterowania przepływem na ogół są

rozłączne w tym znaczeniu, że:

 wyznaczanie tras zwykle dotyczy wymiarowania sieci i

udostępniania jej zasobów,

 zadanie sterowania przepływem jest związane z efektywnym

wykorzystaniem zasobów udostępnianych w sieci.

 Rozłączność omawianych zadań jest wyrazista w sieciach, w których

jako kryteria wyboru tras stosowane są proste miary odległości

węzłów sieci.

 W takich przypadkach zmiany optymalnych tras w sieci są

powodowane zmianami struktury topologicznej sieci albo w wyniku

awarii elementów sieci, albo zmian w niej ilości zasobów. Z tego

punktu widzenia częstość wywoływania algorytmów wyznaczania

tras i sterowania przepływami jest bardzo różna.

 Zadania wyznaczania optymalnych tras są formułowane zarówno

jako zadania projektowania sieci, jak i zadania inżynierii ruchu.

J akkolwiek sformułowania tych zadań są podobne, są to jednak

zadania różne.

Zadania wyznaczania tras

Zadania wyznaczania tras w procesie projektowania dotyczą

wymiarowania sieci.

Zadanie wyznaczania tras na potrzeby zarządzania ruchem w

sieci dotyczy takiego wyboru tras, których zastosowanie do

przekazywania ruchu w sieci prowadzi do zwiększenia

stopnia wykorzystania zasobów.

W sieciach, w których są realizowane różne koncepcje

dostarczania jakości usług, procedury wyboru tras i

wyznaczania na nich przepływów są wywoływane jednakowo

często.

W takich przypadkach rozdzielanie omawianych zadań nie

jest ani oczywiste, ani zasadne.

Zadania wyznaczania tras
i przepływów

 Sposoby formułowania zadań wyznaczania optymalnych tras oraz

sterowania przepływem (wyznaczania przepływu), mimo różnej

funkcjonalności, są zbliżone.

 Podobieństwo sformułowań wynika z faktu, że zadania te dotyczą

alokacji zasobów dla przepływów przyjmowanych do obsługi lub

obsługiwanych w systemie.

 Różnice sformułowań wynikają z tego, że:

 celem zadania wyznaczania tras jest optymalna alokacja

zasobów dla znanego ruchu generowanego przez źródła,

 celem zadania sterowania przepływem oraz przeciwdziałania

przeciążeniom jest definiowanie warunków, w których konieczne

jest ograniczanie ilości ruchu, a w razie konieczności

ograniczenia (dławienia) ilości wprowadzanego i obsługiwanego

ruchu taki sposób alokacji ograniczonych zasobów, który

gwarantuje zadany poziom jakości obsługi ruchu.

Zadanie wyznaczania tras

  W i ę k s z o ś ć k l a s y c z n y c h , j e d n o k r y t e r i a l n y c h z a d a ń o p t y m a l i z a c j i w

s i e c i a c h f o r m u ł u j e s i ę d l a k r y t e r i u m p o s t a c i

,

1

)

(

)

,

(

)

,

(

)

,

(

ij

ij

Γ

j

i

ij

ij

ij

j

i

ij

Γ

j

i

ij

ij

f

f

C

f

f

f

d

d





















w k t ó r y m :

d

i j

– m o n o t o n i c z n i e m a l e j ą c a f u n k c j a p r z e p ł y w u f

i j

,

C

i j

– p o j e m n o ś ć ł ą c z a ( i , j ) w y r a ż o n a w j e d n o s t k a c h p r z e p ł y w u ,



i j

f

i j

– o p ó ź n i e n i e p r z e t w a r z a n i a i p r o p a g a c j i w n o s z o n e p r z e z ł ą c z e ( i , j )

d l a p r z e p ł y w u f

i j

.

  Z g o d n i e z p o d a n y m w y r a ż e n i e m w a r t o ś ć ś r e d n i e g o o p ó ź n i e n i a d

z a l e ż y o d w s z y s t k i c h p r z e p ł y w ó w w ł ą c z a c h f

i j

i p o j e m n o ś c i

w s z y s t k i c h ł ą c z y C

i j

w s i e c i .

  Ś r e d n i e o p ó ź n i e n i e m o ż n a i n t e r p r e t o w a ć j a k o s u m ę ś r e d n i c h c z a s ó w

o c z e k i w a n i a w s z y s t k i c h j e d n o s t e k d a n y c h ( p a k i e t ó w ) n a o b s ł u g ę w

k o l e j k a c h , p r z y z a ł o ż e n i u , ż e k o l e j k i w w ę z ł a c h s ą t y p u M / M / 1 , g d z i e

f

i j

j e s t i n t e n s y w n o ś c i ą n a p ł y w u z g ł o s z e ń , a C

i j

– i n t e n s y w n o ś c i ą

o b s ł u g i z g ł o s z e ń .

Zadanie wyznaczania tras

  O m a w i a n e w y r a ż e n i e j e s t d o g o d n ą i p r a k t y c z n ą m i a r ą p r z e c i ą ż e n i a ,

z e w z g l ę d u n a t o , ż e d e fi n i u j e p r z e c i ą ż e n i a ł ą c z y s i e c i j a k o s t a n y ,

w k t ó r y c h w a r t o ś c i p r z e p ł y w ó w f

i j

r o s n ą d o w a r t o ś c i b l i s k i c h

p o j e m n o ś c i o m ł ą c z y C

i j

: d

i j

( f

i j

)   , j e ż e l i f

i j

 C

i j

.

  W a r t o ś ć d m o ż e b y ć s t o s o w a n a d o w y z n a c z e n i a ś r e d n i e g o

o p ó ź n i e n i a j e d n o s t e k d a n y c h w s i e c i

d

~

:

,

1

)

(

1

1

~

)

,

(

)

,

(

ij

ij

Γ

j

i

ij

ij

ij

Γ

j

i

ij

ij

f

f

C

f

f

d

d

d



























g d z i e  j e s t s u m a r y c z n ą i n t e n s y w n o ś c i ą n a p ł y w u j e d n o s t e k d a n y c h .

  W a r t o ś ć  j e s t s u m ą w s z y s t k i c h e l e m e n t ó w m a c i e r z y r u c h u

( w y m a g a ń ) ( a n g . r e q u i r e m e n t m a t r i x ) , k t ó r y m i s ą i n t e n s y w n o ś c i

s t r u m i e n i j e d n o s t e k d a n y c h w p r o w a d z a n y c h d o s i e c i w e w s z y s t k i c h

w ę z ł a c h w e j ś c i o w y c h s i e c i , t j . i n t e n s y w n o ś c i p r z e p ł y w ó w v

i j

p o m i ę d z y

w s z y s t k i m i p a r a m i w ę z ł ó w ź r ó d ł o – u j ś c i e :

.

,













Ν

i

j

i

Ν

j

ij

v



Zadanie wyznaczania
optymalnych tras

  Z a d a n ie w y z n a c z a n ia o p ty m a ln y c h tr a s w s ie c i p o le g a n a ta k im

p o d z ia le r u c h u , g e n e r o w a n e g o p r z e z ź r ó d ła , p o m ię d z y w ie le tr a s o d

ź r ó d e ł d o u jś ć , k tó r y m in im a liz u je f u n k c ję k r y te r ia ln ą .

  O z n a c z e n ia :

w = ( s , t) – p a r a ź r ó d ło – u jś c ie ,

v

w

– s ta ła s z y b k o ś ć n a p ły w u p a k ie tó w d o s ie c i w s - ty m w ę ź le i

w y p r o w a d z a n y c h z s ie c i w t- ty m w ę ź le , c h a r a k te r y z u ją c a p a r ę

w ę z łó w w = ( i, j) ,

W

– z b ió r w s z y s tk ic h p a r ź r ó d ło – u jś c ie w s ie c i,

P

w

– z b ió r w s z y s tk ic h tr a s s k ie r o w a n y c h d la p a r y w = ( s , t) , tj. z b ió r

w s z y s tk ic h tr a s łą c z ą c y c h s - ty w ę z e ł ź r ó d ło w y z t- ty m w ę z łe m

u jś c io w y m ,

x

p

– p r z e p ły w n a tr a s ie p ,

  Z b ió r w s z y s tk ic h p r z e p ły w ó w n a tr a s a c h p o m ię d z y w s z y s tk im i p a r a m i

w ę z łó w s ie c i s p e łn ia o g r a n ic z e n ia :







w

P

p

w

p

v

x

d la k a ż d e g o

W

w 

o r a z

0



p

x

d la k a ż d e g o

w

P

p 

i

.

W

w 

Zadanie wyznaczania
optymalnych tras

  S u m a r y c z n y p rz e p ły w w łą c z u ( i, j) je s t s u m ą p rz e p ły w ó w p o

w s z y s tk ic h tr a s a c h , k tó r e z a w ie r a ją łą c z e ( i, j) :

,

)

,

(











W

w

P

p

p

ij

j

i

w

x

f

g d z ie P

w ( ij)

je s t z b io r e m w s z y s tk ic h tr a s w z b io r z e P

w

z a w ie r a ją c y c h

łą c z e ( i, j) .

  W y b ó r o p ty m a ln y c h tr a s , p o le g a n a w y z n a c z e n iu z b io r u p r z e p ły w ó w

n a tr a s a c h {x

p

}, m in im a liz u ją c y c h w a r to ś ć fu n k c ji k r y te r ia ln e j:





,

min

)

,

(

}

{

*

)

,

(















Γ

j

i

W

w

P

p

p

ij

x

j

i

w

p

x

d

d

p r z y o g r a n ic z e n ia c h :







w

P

p

w

p

v

x

d la k a ż d e g o

W

w 

, x

p

 0 d la k a ż d e g o p  P

w

i w  W .

  Z a d a n ie w y z n a c z a n ia o p ty m a ln y c h tr a s , w p o d a n y m s fo r m u ło w a n iu ,

m a p o s ta ć u m o ż liw ia ją c ą o tr z y m a n ie r o z w ią z a ń a n a lity c z n y c h w

w y n ik u d z ia ła n ia r o z p r o s z o n y c h a lg o r y tm ó w . T a fu n k c ja k r y te r ia ln a

n ie je s t w r a ż liw a n a w a r ia n c je , k o r e la c je c z a s ó w p o m ię d z y

z g ło s z e n ia m i k o le jn y c h p a k ie tó w i c z a s y ic h tr a n s m is ji.

Zadanie wyznaczania
optymalnych tras - rozwiązanie

 Rozwiązanie zadania wyznaczania optymalnych tras w sieci, dla

danego zbioru przepływów generowanych dla wszystkich par źródło–

ujście najczęściej uwzględnienia pojęcie najkrótszej trasy.

 Rozwiązanie jest charakteryzowane za pomocą właściwości funkcji

d

ij

oraz pochodnych funkcji d

ij

, spełniających warunki:

 d

ij

jest podwójnie różniczkowalną funkcją sumarycznego

przepływu w łączu f

ij

,

 d

ij

jest funkcją zdefiniowaną w przedziale [0, C

ij

), gdzie C

ij

jest

liczbą dodatnią (zwykle określającą pojemność łącza) lub liczbą

równą nieskończoności,

 d

ij

( f

ij

)   wtedy, gdy f

ij

 C

ij

,

 pierwsza i druga pochodne funkcji d

ij

są dodatnie dla wszystkich

wartości f

ij

z przedziału [0, C

ij

).

 Spełniająca te warunki funkcja d

ij

jest wypukłą i monotonicznie

rosnącą funkcją f

ij

w przedziale [0, C

ij

). Ponieważ sumaryczny

przepływ f

ij

w łączu jest funkcją liniową przepływów na trasach x

p

,

funkcja kryterialna zadania ze względu na przepływy na trasach {x

p

}

jest funkcją wypukłą, podwójnie różniczkowalną, a zbiór ograniczeń

jest zbiorem wypukłym.

Zadanie wyznaczania
optymalnych tras – rozwiązanie
optymalne

  C h a r a k te r y s ty k a o p ty m a ln e g o r o z w ią z a n ia z a d a n ia w y z n a c z a n ia tr a s

w s ie c i je s t p o d a w a n a w p o s ta c i o g ó ln y c h w a r u n k ó w k o n ie c z n y c h i

w y s t a r c z a ją c y c h o p t y m a ln o ś c i, w y n ik a ją c y c h z n a s tę p u ją c e g o

le m a tu :

L e m a t :
J e ż e li f je s t r ó ż n ic z k o w a ln ą i w y p u k łą f u n k c ją n - w y m ia r o w e g o

w e k to r a x = [x

1

, x

2

, … , x

n

] , k tó r y c h z b ió r X je s t z b io r e m w y p u k ły m , to

w e k to r x

*

( x

*

 X ) je s t o p ty m a ln y m r o z w ią z a n ie m z a d a n ia m in im a liz a c ji

f u n k c ji f ( x ) d la x  X w te d y i ty lk o w t e d y , g d y :

0

)

(

)

(

*

1

*













i

i

n

i

i

x

x

x

f x

d la k a ż d e g o x  X ,

g d z ie  f ( x

*

) /  x

i

je s t w a r to ś c ią p ie r w s z e j p o c h o d n e j f u n k c ji f z e w z g lę d u

n a w s p ó łr z ę d n ą x

i

, o b lic z a n ą d la w e k to r a x

*

.

Zadanie wyznaczania
optymalnych tras – rozwiązanie
optymalne

P o w p r o w a d z e n iu o z n a c z e ń :





,

)

(

)

,

(

)

,

(















Γ

j

i

W

w

P

p

p

ij

j

i

w

x

d

D x











p

l

k

kl

p

d

x

D

)}

,

{(

)

( x

,

D ( x )

– fu n k c ja k r y te r ia ln a ,

x

– w e k to r , k tó r e g o e le m e n ty s ą p r z e p ły w a m i n a w s z y s tk ic h

tr a s a c h n a le ż ą c y c h d o z b io r u P

w

d la w s z y s tk ic h p a r

ź r ó d ło – u jś c ie z e z b io r u p a r W ,

{( k , l ) }

p

– z b ió r w s z y s tk ic h łą c z y n a le ż ą c y c h d o tr a s y p ,

 D ( x ) / x

p

– w a r to ś ć p o c h o d n e j c z ą s tk o w e j D ( x ) z e w z g lę d u n a x

p

o b lic z a n a d la p r z e p ły w ó w o d p o w ia d a ją c y c h w e k to r o w i x ,

w a r to ś ć p o c h o d n e j c z ą s tk o w e j  D ( x ) / x

p

je s t d łu g o ś c ią tr a s y p w te d y ,

g d y d łu g o ś ć k a ż d e g o łą c z a ( k , l ) , n a le ż ą c e g o d o z b io r u {( k , l ) }

p

, je s t

w a r to ś c ią p ie r w s z e j p o c h o d n e j d ?

k l

o b lic z o n e j d la w e k to r a p r z e p ły w ó w x .

Zadanie wyznaczania
optymalnych tras – rozwiązanie
optymalne

Z g o d n ie z le m a te m , w e k to r p rz e p ły w ó w

}

{

*

*

p

x



x

je s t o p ty m a ln y , g d y

s p e łn ia o g ra n ic z e n ia z a d a n ia w y z n a c z a n ia o p ty m a ln y c h tra s o ra z

w a ru n e k k o n ie c z n y i w y s ta rc z a ją c y o p ty m a ln o ś c i (w y n ik a ją c y z le m a tu ):

0

)

(

)

(

*

*

















p

p

W

w

P

p

p

x

x

x

D

w

x

,

d la w s z y s tk ic h x

p

, s p e łn ia ją c y c h n a s tę p u ją c e o g ra n ic z e n ia :







w

P

p

w

p

v

x

o ra z

0



p

x

d la w s z y s tk ic h

w

P

p 

i

.

W

w 

Zadanie wyznaczania
optymalnych tras – rozwiązanie
optymalne

P o p r z y j ę c i u , d l a u s t a l o n e j p a r y ź r ó d ł o – u j ś c i e w ( w  W ) , ż e r ó w n o ś ć

*

p

p

x

x 

z a c h o d z i d l a w s z y s t k i c h p o z o s t a ł y c h p a r ź r ó d ł o – u j ś c i e u ( u 

W – { w } ) , t z n . :

0

)

(

)

(

)

(

)

(

*

*

*

*





























p

p

P

p

p

p

p

W

w

P

p

p

x

x

x

D

x

x

x

D

w

w

x

x

,

w a r u n k i o p t y m a l n o ś c i w e k t o r a

}

{

*

*

p

x



x

d l a k a ż d e j p a r y ź r ó d ł o – u j ś c i e

w ( w  W ) m o g ą b y ć p r z e d s t a w i o n e n a s t ę p u j ą c o :

0

)

(

)

(

*

*













p

p

P

p

p

x

x

x

D

w

x

d l a w s z y s t k i c h x

p

 0 t a k i c h , ż e :

.







w

P

p

w

p

v

x

Zadanie wyznaczania
optymalnych tras – rozwiązanie
optymalne

  W arunek ten jest równoważny z warunkiem spełnianym dla każdej

pary źródło– ujście w (w  W ):

0

*



p

x

tylko wtedy, gdy

p

p

x

D

x

D













)

(

)

(

*

*

x

x

dla wszystkich

w

P

p 



.

  W arunek ten można interpretować w następujący sposób: zbiór

przepływów na trasach jest optymalny wtedy i tylko wtedy, gdy

przepływy są dodatnie tylko na trasach o minimalnej wartości

pierwszych pochodnych.

Zadanie sterowania przepływem

 Rozwiązywanie zadania sterowania przepływem na ogół jest

konieczne wtedy, gdy zachodzi potrzeba ograniczania szybkości

generowania strumienia zgłoszeń przez źródło, powodowana

ograniczonymi zasobami komunikacyjnymi pomiędzy węzłami sieci

lub zasobami przetwarzania w węzłach sieci.

 Procedury sterowania przepływem mogą być implementowane na

różnych poziomach agregacji przepływów i różnych poziomach

ogólności.

 Każda z procedur sterowania przepływem zawiera dwa moduły

funkcjonalne:

 identyfikacji aktualnego stanu tras (stopnia wykorzystania

zasobów) w sieci,

 aktualizacji wartości parametrów przepływów na trasach sieci

jako funkcji aktualnego stopnia wykorzystania zasobów sieci.

 Procedury sterowania przepływem mogą być implementowane w

wersji scentralizowanej (ang. centralized flow control) lub

zdecentralizowanej (ang. decentralized flow control). Implementacja

procedury zdecentralizowanej oznacza, że każdy z użytkowników

sieci wyznacza wartości parametrów przepływu niezależnie od

innych.

Cele procedur sterowania
przepływem

 Cele stawiane procedurom sterowania przepływem dotyczą:

 znalezienia rozwiązania będącego kompromisem pomiędzy

poziomem dławienia (blokowania) szybkości generowania

zgłoszeń przez użytkowników sieci oraz utrzymywania wartości

średnich opóźnienia zgłoszeń na pewnym, możliwym do

zaakceptowania przez użytkowników sieci, poziomie,

 sprawiedliwego

podziału

zasobów,

polegającego

na

umożliwianiu

dostępu

do

zasobów

sieci

każdemu

użytkownikowi, niezależnie od różnicy całkowitego ruchu w sieci

generowanego przez źródła i ruchu nieprzyjmowanego do

obsługi w sieci ze względu na jej ograniczone zasoby, tzn.

równomiernego rozkładu ruchu przyjmowanego do obsługi w

sieci pomiędzy wszystkich jej użytkowników,

 przeciwdziałania degradacji przepustowości i powstawaniu

wąskich gardeł powodowanych przepełnieniem pamięci

buforowych.

Procedury sterowania
przepływem
- jakość usług sieci

 Podstawowym kryterium jakości usług w sieci komputerowej jest

opóźnienie jednostki danych właściwej dla poziomu (warstwy)

architektury sieci, w której implementowany jest mechanizm

sterowania przepływem.

 Małe wartości średniego opóźnienia są oczekiwane i pożądane przez

praktycznie każdą aplikację obsługiwaną w sieci.

 Uzupełnianie zbioru kryteriów jakości usług o inne, oprócz

opóźnienia, kryteria jest najczęściej powodowane tym, że pozwalają

one wyróżniać klasy ruchu o różnej wrażliwości na opóźnienia i jego

zakresy zmienności.

 Implementacja dowolnej procedury sterowania przepływem

praktycznie w żadnym przypadku nie powoduje zmniejszenia

opóźnienia jednostek danych użytkowników sieci.

 Procedura sterowania przepływem przesuwa opóźnienie z poziomu

(warstwy), na którym jest implementowana, na poziomy wyższe,

nadrzędne dla poziomu implementacji procedury (np. zmniejszenie

średniego opóźnienia pakietów w warstwie sieciowej odbywa się

kosztem wydłużenia czasu oczekiwania w warstwie transportowej).

Procedury sterowania
przepływem
- retransmisje

 Głównym zadaniem sterowania przepływem jest przeciwdziałanie

natłokom w sieci lub jej wybranych fragmentach, zagrażających

jakości usług świadczonych wszystkim użytkownikom.

 Sterowanie przepływem jest sposobem reglamentacji zasobów sieci,

zwłaszcza wtedy, gdy chwilowe zapotrzebowanie na zasoby jest

większe od ilości dostępnych zasobów.

 Poprawa jakości usług dla użytkowników sieci to: zwiększanie jej

zasobów, poprawa algorytmów ich udostępniania lub ograniczanie

liczby użytkowników sieci.

 Zasadniczym powodem utrzymywania wartości opóźnień na niskim

poziomie raczej w sieci niż poza nią, jest ochrona zasobów przed ich

marnotrawieniem, powodowanym retransmisjami pakietów.

 Przyczyny retransmisji pakietów są dwojakie:

 zwiększony napływ pakietów do sieci to wzrost zajętości pamięci

buforowych i wartości prawdopodobieństwa przepełnienia, tzn.

wzrost liczby odrzucanych pakietów wymagających retransmisji,

 zwiększenie opóźnień pakietów oznacza wzrost opóźnień

potwierdzeń pakietów i tym samym wartości prawdopodobieństwa

przekroczenia limitu czasu oczekiwania na potwierdzenie pakietu;

konsekwencją jest zwiększenie liczby retransmisji pakietów.

Procedury sterowania
przepływem
- opóźnienia

Sformułowanie zadania

 Do sformułowania zadania jednoczesnego wyznaczania tras i

sterowania przepływem w sieci można użyć modelu przepływów

zbliżonego do modelu stosowanego w zadaniu wyznaczania

optymalnych tras w sieci.

 W modelu przepływów w sieci v

w

jest szybkością przepływu pakietów

pomiędzy parą węzłów w = (s, t), gdzie s-ty węzeł jest węzłem

źródłowym, a t-ty – ujściowym.

 Interpretacja optymalnej wartości szybkości przepływu v

w

może być

różna i zależy od aplikacji generującej przepływ – np. transmisja:

 pojedynczych jednostek danych - optymalna wartość v

w

jest

średnią szybkością przepływu, mierzoną we względnie długim

przedziale czasu; celem sterowania jest transmitowanie nie więcej

(nie mniej) niż v

w

T jednostek danych w przedziale czasu T,

 w łączu wirtualnym - optymalna wartość v

w

jest stałą szybkością

przepływu; celem sterowania jest utrzymanie stałej szybkości przez

blokowanie lub akceptację nowych żądań przepływów,

 ruchu aplikacji czasu rzeczywistego - optymalna wartość v

w

jest

chwilową

szybkością

przepływu;

celem

sterowania

jest

transmitowanie jednostek danych zgodnie z szybkością ich

generowania przez źródło.

Zadanie jednoczesnego
wyznaczania tras i przepływu

J e d n o c z e s n e w y z n a c z a n ie tr a s i s z y b k o ś c i p r z e p ły w ó w d la p a r ź r ó d ło –

u jś c ie w y m a g a m o d y fi k a c ji z a d a n ia w y z n a c z a n ia o p ty m a ln y c h tr a s ,

je d n o c z e s n a b o w ie m m in im a liz a c ja fu n k c ji k r y te r ia ln e j w z a d a n iu

w y z n a c z a n ia o p ty m a ln y c h tr a s , z e w z g lę d u n a s z y b k o ś c i p r z e p ły w ó w
n a tr a s a c h

}

{

p

x

o r a z s z y b k o ś c i n a p ły w u d o s ie c i

}

{

w

v

, tz n . :

















Γ

j

i

W

w

P

p

p

ij

v

x

j

i

w

w

p

x

d

)

,

(

}

{

},

{

)

,

(

min

,

p r z y o g r a n ic z e n ia c h :







w

P

p

w

p

v

x

d la k a ż d e g o

,

W

w 

0



p

x

d la k a ż d e g o

w

P

p 

i

W

w 

p r o w a d z i d o r o z w ią z a n ia :

0



p

x

o r a z

0



w

v

d la k a ż d e g o

w

P

p 

i

.

W

w 

Modyfikacja zadania
wyznaczania tras

  M o d y fi k a c ja z a d a n ia w y z n a c z a n ia tra s p o le g a n a m o d y fi k a c ji fu n k c ji

k ry te ria ln e j p rz e z w p ro w a d z e n ie d o n ie j w y ra ż e n ia o k re ś la ją c e g o

k a rę z a o g ra n ic z a n ie (z m n ie js z a n ie ) p rz e z p ro c e d u rę s te ro w a n ia

s z y b k o ś c i p rz e p ły w u v

w

o fe ro w a n e j p rz e z ź ró d ło , tz n . fu n k c ji k a ry

)

(

w

w

v

h

, g d z ie

w

v je s t rz e c z y w is tą (z a a k c e p to w a n ą ) s z y b k o ś c ią

p rz e p ły w u .

  W p ro w a d z e n ie fu n k c ji k a ry p ro w a d z i d o s fo rm u ło w a n ia z a d a n ia

je d n o c z e s n e g o w y z n a c z a n ia tra s i p rz e p ły w ó w w p o s ta c i:









,

)

(

min

)

,

(

}

{

},

{

*

)

,

(





















W

w

w

w

Γ

j

i

W

w

P

p

p

ij

v

x

v

h

x

d

d

j

i

w

w

p

p rz y o g ra n ic z e n ia c h :
 







w

P

p

w

p

v

x

d la k a ż d e g o

,

W

w 

 

0



p

x

d la k a ż d e g o

w

P

p 

i

,

W

w 

 

w

w

v

v 



0

d la k a ż d e g o

W

w 

 

g d z ie

)

(

w

w

v

h

je s t fu n k c ją k a ry z a z w ię k s z e n ie ró ż n ic y o fe ro w a n e j i

a k c e p to w a n e j s z y b k o ś c i p rz e p ły w u (z a o d rz u c a n ie je d n o s te k

d a n y c h p rz e p ły w u ).

Zadanie jednoczesnego wyznaczania
tras i przepływu – funkcja kary

Funkcja kary, stosowana w om

awianych zadaniach, jest funkcją

wypukłą, m

onotonicznie m

alejącą w przedziale (0, ) oraz

spełniającą warunki:






)

(

w

w

v

h

gdy

0



w

v

,



0

)

(



w

w

v

h

gdy





w

v

,

pierwsza –

w

h i druga –

w

h



 pochodne istnieją w przedziale

)

,

0

( ,

a ich wartości zawsze są – odpowiednio – ujem

ne i dodatnie.

Szczególne właściwości m

a klasa funkcji kary, których pierwsza

pochodna m

a postać:

,

)

(

w

b

w

w

w

w

v

a

v

h



















gdzie a

w

i b

w

są danym

i wartościam

i stałym

i.

Wybór wartości stałych a

w

i b

w

m

a wpływ na optym

alną szybkość

przepływu

w

v oraz priorytet przepływu pom

iędzy parą węzłów sieci w

=

(s, t).

Zadanie jednoczesnego wyznaczania
tras i przepływu – przypadki

Najprostszym

przypadkiem

sform

ułow

anego zadania jest takie, w

którym

zbiory P

w

są jednoelem

entow

e – dla każdej pary w =

(s, t)

istnieje tylko jedna trasa.

Wówczas jednoczesne wyznaczanie tras i przepływów redukuje się

do zadania w

yznaczania przepływ

ów

, tzn. optym

alnych w

artości

w

spółczynników

będących ilorazem

szybkości generow

anych

przepływ

ów

(szybkości przepływ

ów

oferow

anych przez źródło) v

w

oraz szybkości przepływ

ów

przyjm

ow

anych do sieci

w

v .

Podane sform

ułow

anie zadania jednoczesnego wyznaczania tras i

przepływów m

oże być rozszerzone na przypadek, gdy parę w =

(s,

t) interpretuje się jako klasę użytkow

ników sieci w

spółdzielących ten

sam

zbiór tras P

w

.

Taka interpretacja przepływu dla pary w =

(s, t) pozw

ala na

ustanawianie różnych priorytetów ( przez wprowadzanie różnych

funkcji kar h

w

) dla różnych klas użytkowników

, w

tym

dla

użytkowników

w

spółdzielących tę sam

ą trasę. Form

alnie zadanie

łącznego wyznaczania tras i przepływów w

sieci jest rów

now

ażne

zadaniu wyznaczania tras w sieci.

Równoważność zadań

  W

c e l u

w y k a z a n i a

r ó w n o w a ż n o ś c i

z a d a n i a

w y z n a c z a n i a

o p t y m a l n y c h t r a s o r a z z a d a n i a j e d n o c z e s n e g o w y z n a c z a n i a

o p t y m a l n y c h t r a s i p r z e p ł y w ó w w p r o w a d z a s i ę d o d a t k o w ą z m i e n n ą
y

w

, k t ó r a – d l a k a ż d e j p a r y w ę z ł ó w w  W – j e s t w a r t o ś c i ą r ó ż n i c y

o f e r o w a n e j i r z e c z y w i s t e j s z y b k o ś c i p r z e p ł y w ó w , t z n .

,)

...

(

2

1

w

m

p

p

p

w

w

w

w

x

x

x

v

v

v

y















g d z i e :

j

p

x

– s z y b k o ś ć p r z e p ł y w u n a t r a s i e p

j





w

m

j

P

p

p

p

p

w





}

...,

,

,

{

2

1

p o m i ę d z y p a r ą w ę z ł ó w w = ( s , t ) ,

m

w

– l i c z b a w s z y s t k i c h r ó ż n y c h t r a s d l a p a r y ź r ó d ł o – u j ś c i e w .

  W a r t o ś ć y

w

j e s t t ą c z ę ś c i ą s z y b k o ś c i p r z e p ł y w u v

w

, k t ó r a j e s t

b l o k o w a n a n a w e j ś c i u d o s i e c i - z p u n k t u w i d z e n i a s i e c i w a r t o ś ć

z m i e n n e j y

w

m o ż n a i n t e r p r e t o w a ć j a k o p r z e p e ł n i e n i e , c z y l i p r z e p ł y w

w d o d a t k o w o w p r o w a d z a n y m ł ą c z u p r z e p e ł n i e n i a .

Równoważność zadań

Równoważność zadań

P o z d e fi n io w a n iu n o w e j f u n k c ji k a r y d la z m ie n n e j y

w

:

)

(

)

(

w

w

w

w

w

v

v

h

y

H





,

z a d a n ie je d n o c z e s n e g o w y z n a c z a n ia tr a s i p r z e p ły w ó w m a p o s ta ć :









,

)

(

min

~

)

,

(

}

{

},

{

*

)

,

(





















W

w

w

w

Γ

j

i

W

w

P

p

p

ij

y

x

y

H

x

d

d

j

i

w

w

p

g d z ie :

)

(

)

(

w

w

w

w

w

v

v

h

y

H





p r z y o g r a n ic z e n ia c h :









w

P

p

w

w

p

v

y

x

d la k a ż d e g o

,

W

w 

0



p

x

d la k a ż d e g o

w

P

p 

i

,

W

w 

0



w

y

d la k a ż d e g o

.

W

w 

Równoważność zadań

 Zależność pomiędzy funkcjami

)

(

)

(

w

w

w

w

w

v

v

h

y

H





oraz

)

(

w

w

v

h

oznacza, że jeżeli





)

(

w

w

v

h

gdy

0



w

v

(wartość funkcji rośnie do

nieskończoności wtedy, gdy przepływ klasy w jest w całości
odrzucany), to H

w

( y

w

)   - przepełnienie y

w

osiąga maksymalną

wartość równą szybkości przepływu źródła v

w

, tzn. y

w

= v

w

.

 Dla ustalonej szybkości przepływu v

w

spełnione są warunki:



0

)

(



w

w

y

H

wtedy, gdy

,

0

)

(







w

w

w

v

v

y







)

(

w

w

y

H

wtedy, gdy

,

)

(

w

w

w

w

v

v

v

y







i wartość funkcji kary H

w

( y

w

) może więc być interpretowana jako

opóźnienie wnoszone przez łącze przepełnienia, a v

w

jako

pojemność łącza przepełnienia.

 Interpretacja funkcji kary H

w

( y

w

) jako opóźnienia wnoszonego przez

łącze

przepełnienia

oznacza,

że

zadanie

jednoczesnego

wyznaczania tras i przepływów jest równoważne zadaniu

wyznaczania optymalnych tras; każdy zbiór tras P

w

, dla każdej pary

źródło– ujście w (w  W ), jest uzupełniany o dodatkową trasę

1



w

m

p

(trasa jest łączem przepełnienia o pojemności równej szybkości

przepływu generowanego przez źródło v

w

).

Równoważność zadań
- funkcje kar

Równoważność zadań

  R ó w n o w a ż n o ś ć o m a w i a n y c h z a d a ń o z n a c z a , ż e z a r ó w n o w a r u n k i

o p t y m a l n o ś c i r o z w i ą z a n i a z a d a ń , j a k i a l g o r y t m y r o z w i ą z y w a n i a

o m a w i a n y c h z a d a ń s ą i d e n t y c z n e .

  P o w p r o w a d z e n i u o z n a c z e ń :





,)

(

)

~

(

)

,

(

)

,

(





















W

w

w

w

Γ

j

i

W

w

P

p

p

ij

y

H

x

d

D

j

i

w

x

,)

(

)

~

(

)}

,

{(

kl

l

k

kl

p

f

d

x

D

p











x

,)

(

)

(

)

~

(

w

w

w

w

w

w

v

v

h

y

H

y

D

















x

w a r u n k i k o n i e c z n e i w y s t a r c z a j ą c e o p t y m a l n o ś c i w e k t o r a p r z e p ł y w ó w

m o g ą b y ć f o r m u ł o w a n e a n a l o g i c z n i e d o w a r u n k ó w o p t y m a l n o ś c i

z a d a n i a w y z n a c z a n i a o p t y m a l n y c h t r a s .

Równoważność zadań

  W e k to r p rz e p ły w ó w

}

~

{

~

*

*

s

x



x

je s t o p ty m a ln y , g d y s p e łn ia

o g ra n ic z e n ia z a d a n ia je d n o c z e s n e g o w y z n a c z a n ia o p ty m a ln y c h tra s

i p rz e p ły w ó w o ra z w a ru n e k k o n ie c z n y i w y s ta rc z a ją c y o p ty m a ln o ś c i:

0

)

~

~

(

~

)

~

(

*

~

*

















s

s

W

w

P

s

s

x

x

x

D

w

x

,

d la w s z y s tk ic h

s

x~ s p e łn ia ją c y c h n a s tę p u ją c e o g ra n ic z e n ia :







w

P

s

w

s

v

x

~

~

o ra z

0

~ 

s

x

d la w s z y s tk ic h

w

P

s

~



i

.

W

w 

  W a ru n k i o p ty m a ln o ś c i p rz e p ły w ó w , fo rm u ło w a n e d la k a ż d e j z p a r w

(w  W ), s ą n a s tę p u ją c e :

,

0

)

~

~

(

~

)

~

(

*

~

*













s

s

P

s

s

x

x

x

x

D

w

je ż e li p rz e p ły w y

s

x~ s ą n ie u je m n e

)

0

~

(



s

x

, a s u m a s z y b k o ś c i

p rz e p ły w ó w n a w s z y s tk ic h tra s a c h d la k a ż d e j p a ry w je s t ró w n a
s z y b k o ś c i g e n e ro w a n ia p rz e p ły w u w w ę ź le ź ró d ło w y m p a ry w (w  W ).

Przykład - zadanie

Z a d a n i e je d n o c z e s n e g o w y z n a c z a n i a t r a s i p r z e p ł y w ó w , g d y p r z e p ł y w
p o m i ę d z y d w o m a w ę z ła m i j e s t o b s łu g i w a n y p r z e z łą c z e o p o j e m n o ś c i

C , j e s t s f o r m u ło w a n e n a s t ę p u j ą c o :

,

min

)]

(

)

(

[

min

)]

(

)

(

[

min

)

(

*

























v

a

v

C

v

y

v

h

v

f

y

H

v

f

v

d

v

v

v

g d z i e :
v

– o f e r o w a n a s z y b k o ś ć p r z e p ły w u ;

y

v

v





,

v

)

0

( 

v

– s z y b k o ś ć p r z e p ły w u p r z y j m o w a n e g o d o o b s łu g i ,

y ( y  0 ) – s z y b k o ś ć p r z e p ły w u o d r z u c a n e g o p r z e z m e c h a n i z m

s t e r o w a n i a p r z e p ły w e m ( c z ę ś ć o f e r o w a n e j s z y b k o ś c i

p r z e p ły w u ) , t z n . k i e r o w a n e g o d o łą c z a p r z e p e ł n ie n i a ,

)

(

)

(

v

C

v

v

f



 /

– o p ó ź n i e n i e w n o s z o n e p r z e z łą c z e o p o j e m n o ś c i C

d l a s z y b k o ś c i p r z e p ł y w u

,

v

)

( y

H

i

)

( v

h

– f u n k c j e k a r y :

)

(

)

(

)

(

y

v

h

v

h

y

H







,

v

a

v

h

/



)

(

– f u n k c j a k a r y ,

a

– s t a ła .

Przykład – zadanie i funkcja kary

Przykład - rozwiązanie

  Z g o d n i e z w a r u n k a m i o p t y m a l n o ś c i b r a k k o n i e c z n o ś c i s t e r o w a n i a

p r z e p ł y w e m , t z n . b r a k p r z e p ł y w u w ł ą c z u p r z e p e ł n i e n i a

)

0

,

(





y

v

v

w y s t ę p u j e g d y p i e r w s z a p o c h o d n a d ł u g o ś c i ł ą c z a r z e c z y w i s t e g o j e s t

m n i e j s z a o d p i e r w s z e j p o c h o d n e j d ł u g o ś c i ł ą c z a p r z e p e ł n i e n i a :

2

2

)

(

v

a

v

C

C





.

  R o z w i ą z a n i e p o w y ż s z e j n i e r ó w n o ś c i :

C

a

a

C

v

v

g







,

o k r e ś l a z a k r e s w a r t o ś c i s z y b k o ś c i o f e r o w a n e g o p r z e p ł y w u , d l a

k t ó r y c h p r z e p ł y w j e s t w c a ł o ś c i o b s ł u g i w a n y p r z e z ł ą c z e .

  W a r u n k i e m k o n i e c z n o ś c i s t e r o w a n i a p r z e p ł y w e m , t j . o d r z u c a n i

c z ę ś c i p r z e p ł y w u

)0

,

(





y

v

v

, j e s t r ó w n o ś ć p i e r w s z y c h p o c h o d n y c h

d ł u g o ś c i ł ą c z y : r z e c z y w i s t e g o i p r z e p e ł n i e n i a , t z n . w t e d y , g d y v > v

g

.

  J e ż e l i s p e ł n i o n y j e s t w a r u n e k v > v

g

, t o p r z e p ł y w w ł ą c z u

r z e c z y w i s t y m w y n o s i ( n i e z a l e ż n i e o d s z y b k o ś c i o f e r o w a n e g o

p r z e p ł y w u v ) :

)

(

C

a

a

C

v





/

Przykład - rozwiązanie

  S z y b k o ś ć p r z e p ły w u z a a k c e p to w a n e g o d o o b s łu g i v je s t r ó w n a

p r z e p u s to w o ś c i o m a w ia n e g o s y s te m u o b s łu g i:

































C

a

a

C

v

C

a

a

C

C

a

a

C

v

v

v

gdy

gdy

.

  W a r to ś ć p r z e p u s to w o ś c i v d la o fe r o w a n e g o p r z e p ły w u v ,

s p e łn ia ją c e g o w a r u n e k :

,

C

a

a

C

v





n ie z a le ż y o d s z y b k o ś c i o fe r o w a n e g o p r z e p ły w u , z a le ż y n a to m ia s t o d

p o je m n o ś c i łą c z a C i w a r to ś c i s ta łe j a – p a r a m e tr u fu n k c ji k a r y .

  Z m ia n a m a k s y m a ln e j p r z e p u s to w o ś c i je s t m o ż liw a p r z e z z m ia n ę

w a r to ś c i a :
  je ż e li





a

, to

C

v 

.

  W z r o s t m a k s y m a ln e j p r z e p u s to w o ś c i p o w o d u je w z r o s t o p ó ź n ie n ia :

  je ż e li

C

v 

, to





)

(

*

v

d

.

Przykład - rozwiązanie