Xem mẫu
- chương 3: Quá trình chuyển động phân
mảnh Brownian
Quá trình chuyển động phân mảnh Brownian (FBM) là một
quá trình tự tương quan được mô tả bởi ba thông số là: tốc độ đến
trung bình m, tham số dao động a và thông số Hurst, H. Một mạng
IP/WDM có thể mô hình hoá tốc độ đến như FBM để xem xét đến
sự dao động của tổng lưu lượng mịn hoá trong khoảng thời gian
thô. FBM được định nghĩa như sau:
A(t) = mt + am Z(t) trong đó t
Trong đó Z(t) là quá trình chuyển động phân mảnh Brownian
bình thường hoá với các tính chất sau:
Z(t) đồng biến
Z(0) = 0 và E[Z(t)] = 0 với mọi t
E[Z(t)]2 = t 2 H với mọi t
Z(t) có tính liên tục
Z(t) có tính Gauss
Sự biến thiên của Z(t) được thể hiện bởi:
V[A(t)] = am t 2 H
Hãy xem xét một hàng đợi với quá trình đến FBM như trên và
với tốc độ dịch vụ C. Hệ thống này có bốn thông số: m là tốc độ
đến trung bình, a là tham số biến thiên của quá trình đến, H là
thông số tự tương quan và C là tốc độ dịch vụ. Xác xuất tràn dòng
của hàng đợi trên hay chính là P(Q>B) trong đó B là kích thước bộ
đệm được cho bởi công thức gần đúng sau:
- 1
P(Q B) exp( (am) 1 (C m) 2 H H 2 H (1 H ) 2(1 H ) B 2 (1 H ) )
2
Giả thiết rằng người ta cần xác xuất tràn dòng ở trên bị chặn
nghĩa là:
z2
P(Q > B) exp (- )
2
thì biểu thức cho tốc độ dịch vụ của hàng đợi C sẽ có dạng
như sau:
1
21 21 11H 1
C mm 2H z a B
H H
H (1 H ) 1 H
Các nguyên lí tham chiếu lưu lượng
Nguyên lí đầu tiên là băng thông lưu lượng trong khoảng thời
gian kế tiếp phụ thuộc nhiều vào lưu lượng đã thấy trong dòng lưu
lượng của cùng khoảng thời gian đó của tuần trước đó.
Nguyên lí này phản ánh mô hình độ lớn lưu lượng phụ thuộc
lớn vào giờ trong ngày và ngày trong tuần được quan sát thấy trong
các tuyến nối. Do vậy, độ lớn lưu lượng trung bình trong khoảng
thời gian kế tiếp sẽ gần như giống hệt như độ lớn đã xuất hiện
trong cùng thời điểm của ngày, của cùng thứ hôm đó của tuần
trước đó. Và điều này có thể được biểu diễn bởi biểu thức:
F0 F h, d
Trong đó F[h,d] là lưu lượng quan sát thấy tại giờ h của ngày d
trong tuần trước đó. Giả sử rằng tốc độ phát triển của lưu lượng từ
tuần này sang tuần khác được mô hình bởi một hàm có thông số γ.
Cũng giả thiết rằng hàm tăng trưởng này là hàm mũ:
- F1 F0 e F0
Trong đó γ là thông số mô hình được ước lượng từ các phép
đo lưu lượng. Giả thiết rằng W0 và W1 là tổng lưu lượng đo được
trong hai tuần liền trước trong dòng lưu lượng thì có thể xác định γ
từ phương trình sau:
W1 W0 e w 0
Nguyên lí thứ hai là dự đoán băng thông lưu lượng trong
khoảng thời gian kế tiếp sẽ khác với lưu lượng đã được quan sát
thực tế trong cùng một cách mà phép dự đoán trong khoảng thời
gian liền trước đó đã thực hiện.
Cho A(h-1) là độ lớn lưu lượng thực tế đo được trong khoảng
thời gian (h-1). Giả thiết F(h-1) là độ lớn lưu lượng dự đoán cho
khoảng thời gian (h-1) thì:
A(h 1)
F (h 1) (1 )
là tỉ lệ để xem xét sự khác nhau giữa giá trị
dự đoán và giá trị thực tế trong khoảng thời gian liền trước. Do đó:
A(h 1)
F (h 1) (1 )
F2 F1
trong đó ρ có thể được chọn bằng cách làm phù hợp với dữ
liệu đã đo được trước đó. Ví dụ như người ta có thể chọn giá trị ρ
sao cho sai số do tỉ lệ được cho bởi:
A(h) A(h 1)
F (h) F (h 1)
là nhỏ nhất cho dữ liệu trong quá khứ. Nói cách khác, có thể
chọn ρ sao cho tối thiểu hoá giá trị:
- 2
A(h) A(h 1)
E
F ( h) F (h 1)
trong đó E là toán tử dự đoán. Nó sẽ cho kết quả là:
A(h) A(h 1)
E
F (h) F (h 1)
2
A(h 1)
E
F (h 1)
Giả thiết rằng một quá trình đến FBM với tốc độ trung bình
F2, kích thước bộ định tuyến là B và xác xuất tổn thất gói tin sẽ bị
chặn trên bởi thì điều kiện cho dung lượng sẽ được biểu diễn
bởi:
1
F3 F2 F22 H (a, H , B, z )
21H 21H 11H 1
trong đó ( a, H , B, z ) z a B
H (1 H ) 1 H
Dưới đây, đồ án sẽ trình bày hai phương pháp dùng để ước
lượng các thông số a và H từ lưu lượng đo được. Phương pháp đầu
tiên giả định rằng đã có các kết quả đo độ lớn lưu lượng cho mỗi
một trong N khoảng thời gian mịn liên tiếp t. Biểu thị độ lớn lưu
lượng cho mỗi khoảng i là T(i). Khi đó giá trị ước lượng độ lớn lưu
lượng trung bình sẽ là:
N
T (i)
m i 1
N
và giá trị ước lượng của phương sai sẽ là:
- N
(T (i) m) 2
Vt i1
N 1
Các giá trị đo có thể được tổng hợp thành k khối không chồng
lấn với kích thước mỗi khối là kt và có phương sai là Vkt. Khi cho
trước hai giá trị ước lượng phương sai Vt và Vkt thì các giá trị a và
H là hoàn toàn có thể xác định được.
Trong phương pháp thứ hai, thông số H có thể ước lượng từ
các điểm sai khác thời gian như sau. Cho một vệt thời gian Xk, k =
1, 2,…., chúng ta sẽ có một vệt thời gian tổng hợp Xk(m), k = 1,
2,… bằng cách lấy trung bình từ các chuỗi Xk ban đầu nhờ các
khối không chồng lấn có độ lớn m. Nghĩa là:
1
X k( m ) X kmm1 ... X km
m
Sau đó đối với các quá trình phụ thuộc dải dài thì ta sẽ có:
V X ( m ) m 2 (1 H )
Do đó, nếu chúng ta vẽ logV X (m) theo log(m) thì độ dốc của
đồ thị sẽ chính là
2(1 H ) , trong đó H’ là giá trị ước lượng cho H.
Các thông số mô hình
Các thông số sau được định nghĩa cho mô hình dự đoán băng
thông:
Kích thước của thời gian thô: Lược đồ giám sát lưu
lượng cho kết quả là dữ liệu dưới dạng ma trận lưu
lượng. Nó chứa độ lớn lưu lượng trung bình trong một
- khoảng thời gian tinh. Độ lớn của thời gian thô chính là
thời gian sử dụng để tính trung bình lưu lượng trong một
khoảng thời gian thô bằng cách kết hợp các dữ liệu lưu
lượng trong khoảng thời gian tinh lại với nhau.
Kích thước bộ đệm bộ định tuyến: kích thước bộ đệm bộ
định tuyến được dùng trong mô hình để dự đoán độ lớn
của một dòng lưu lượng.
Giới hạn xác suất mất gói: thông số này được dùng để dự
đoán băng thông của một dòng lưu lượng.
Thuật toán định tuyến, mô hình mạng: mô hình mạng và
thuật toán định tuyến giúp xác định dòng lưu lượng nào
được yêu cầu đối với một kết nối dựa trên kết quả của
các phép đo dòng lưu lượng từ các bộ định tuyến biên.
Thông số lưu lượng đo được chính là ma trận lưu lượng tinh từ
bộ định tuyến biên này tới bộ định tuyến biên khác. Từ thông số đo
được này có thể rút ra được tất cả các thông số khác. Các thông số
sau được tính toán cho mục đích tái cấu hình tại thời điểm bắt đầu
của một khoảng thời gian thô:
Trung bình thô cho các dòng lưu lượng của mỗi cặp bộ
định tuyến biên vào ra: được tính toán dựa trên dữ liệu
lưu lượng tinh đã đo được.
Độ phức tạp của tính toán trung bình thô là O(N2) trong
đó N là số lượng bộ định tuyến biên trong mạng.
Các trung bình thô và trung bình tinh của độ lớn lưu
lượng yêu cầu cho mỗi kết nối đơn hướng: độ lớn lưu
lượng yêu cầu cho mỗi tuyến nối có thể tính được cho cả
- khoảng thời gian thô và tinh dựa trên ma trận lưu lượng
từ bộ định tuyến biên này tới bộ định tuyến biên khác,
mô hình mạng và thuật toán định tuyến.
Độ phức tạp tính toán là O(E2) trong đó E là số lượng kết
nối trong mạng.
Các thông số dự đoán lưu lượng F1, F2, F3: đối với mỗi
dòng lưu lượng, các thông số dự đoán băng thông F1, F2,
F3 có thể tính toán từ các phương trình ở trên. Việc tính
toán này được thực hiện ở đầu mỗi khoảng thời gian thô.
Độ phức tạp của phép tính là O(N2) trong đó N là số lượng bộ
định tuyến biên trong mạng.
Vì sự tái cấu hình làm thay đổi cấu hình của mạng IP nên một
vài thông số sẽ cần phải được tính toán lại sau khi cấu hình. Đặc
biệt là trung bình thô và tinh cho các dòng lưu lượng đối với mỗi
tuyến nối sẽ cần tính toán lại sau khi xảy ra tái cấu hình. Các thông
số điều chỉnh a, H, ρ và α được sử dụng trong mô hình dự đoán lưu
lượng và được điều chỉnh phù hợp dựa trên dữ liệu lưu lượng đo
được và dữ liệu lưu lượng tính toán. Sự phù hợp cho mỗi một trong
số các thông số trên cần phải được tính toán lại mỗi khi có tái cấu
hình hoặc theo chu kì (chẳng hạn như một lần một tuần).
nguon tai.lieu . vn
