Đồ án tốt nghiệp Chương 3: Scheduling
ĐỒ ÁN HỆ THỐNG MẠNG
Đề tài:
NGUYÊN CỨU VÀ ỨNG DỤNG
CHƯƠNG TRÌNH LẬP LỊCH TRONG
MẠNG IP
CHƯƠNG 3
SCHEDULING

3. 2. 2. 11 WF
2
Q Hàng đợi hợp lý theo trọng số trong trường
hợp xấu nhất
Từ kết quả (3. 10) và (3. 11) có thể dễ dàng thấy rằng WFQ và GPS cung
cấp hầu hết tính đúng đắn của một gói Parekh đã cung cấp rằng WFQ không thể
sụp đổ sau GPS ở khía cạnh các dịch vụ cung cấp bởi một gói có kích thước lớn
nhất . Xét hình 3. 14, ở đó 11 phiên được phân thành các liên kết giống nhau.
Trục ngang là thời gian, trục dọc là đường đi đơn giản của mỗi phiên. Để đơn
giản, giả sử tất cả các gói cùng có kích cỡ là 1 và tốc độ là 1. Đặt tốc độ bảo đảm
của phiên 1 là 0. 5 và tốc độ của 10 phiên còn lại là 0. 05
Đồ án tốt nghiệp Chương 3: Scheduling Hình 3. 14 Ví dụ
Phiên 1 gửi 11 gói lặp lại bắt đầu từ thời gian là 0, trong khi mỗi phiên của
10 phiên khác chỉ gửi 1 gói cũng tại thời gian là 0. Nếu dịch vụ là GPS nó sẽ giữ
2 đơn vị thời gian cho gói của phiên 1 và 20 đơn vị thời gian cho các gói của các
phiên còn lại. Còn nếu server là WFQ, tại thời gian 0, tất cả 11 phiên có các gói
gửi đi sẽ được xử lý. Khi gói p
1, 1
(gói đầu tiên của phiên 1) kết thúc tại thời gian

i
+c
s
i
(3. 17)
Đồ án tốt nghiệp Chương 3: Scheduling
Trong đó r
i
là giới hạn băng thông nhỏ nhất của phiên i, Q
i
s
(

) là kích
thước của hàng đợi của phiên i tại thời gian a
i, k
khi gói thứ k của phiên i đến, c
i
s
là hằng số
C’
i
=r
i
c
i
’/r (3. 18)
C’=max{c
i
s

Q+
WF
2
Q cung cấp giới hạn trễ chặt và nhỏ nhất WFI của tất cả các thuật toán
PFQ, nó có thời gian phức tạp giống như trường hợp xấu nhất, O(N), như WFO
vì chúng cần cả hai để tính toán thời gian ảo hay hệ thống thời gian ảo V(t) bằng
dấu hiệu hệ thống GPS lỏng. WF
2
Q+ và SPFQ cho thấy có các đặc tính tương tự
như WF
2
Q nhưng chúng thực hiện đơn giản hơn bằng việc đưa ra hàm thời gian
ảo của hệ thống như sau:
V(t+

)=max


))(( min),( tStV
i


i



(t) (3. 23)
trong đó β(t) là tập hợp các phiên tạm thời trong hệ thống tại thời gian t,
và S
i

(t
-
)} ; đối với gói đến trong trư
ờng hợp 1
(3. 24)
S
i
(t) = F
i
(t
-
) ; đối với gói đến trong trường hợp 2
F
i
(t) = S
i
(t) + L
i
HOL
/r
i

Ở đây, F
i
(t
-
) là thời gian kết thúc của hàng đợi i trước khi cập nhật và
L
i
HOL

i
, cho mỗi phiên. Gọi L
i

và L
max
lần lượt là gói lớn nhất trong phiên i và trong tất cả các phiên của mạng .
Đồ án tốt nghiệp Chương 3: Scheduling
Sau đó xử lý độc lập các phiên khác(nếu chúng không bắt buộc có gáo rò), hàng
đợi end-to-end trường hợp xấu nhất và trễ truyền dẫn D
i
được giới hạn bởi:
D
i
≤σ
i
/r
i
+(K-1)L
i
/r
i
+K. L
max
/r (3. 26)

Hình 3. 15 Giới hạn trễ của nhiều node
Hình 3. 15 minh hoạ việc tính toán độ trễ cực đại, độ trễ lớn nhất của gói
tại node 1, d
1

/r
i
giống như trong dịch vụ GPS. Thời kì tiếp theo của mỗi bộ lập lịch, các
gói khác từ phiên i sẽ nhận được dịch vụ của nó trước khi bị “đuổi bắt”, vì thế
các gói bị đuổi bắt có trễ là L
i
/r
i
. Thời kì thứ 3, xét đến trường hợp đuổi bắt gói
bằng một bộ lập lịch bận, nó phải đợi một khoảng thời gian là L
max
/r trước khi
được phục vụ. Bất đẳng thức (3. 26) có thể dễ dàng mở rộng cho các vị trí chung
với tốc độ kết nối hỗn hợp. Định lý Parekh và Gallager cho rằng, với một bảng
lựa chọn các tham số, bộ lập lịch WFQ của mạng có thể trễ bảo đảm end-to –
end. Phiên j yêu cầu một giới hạn trễ đặc biệt chỉ cần chọn một giá trị r
j
phù hợp.
Đây là ý tưởng cơ bản của việc bảo đảm các dịch vụ IntServ trong mạng Internet
Đồ án tốt nghiệp Chương 3: Scheduling
sử dụng RSVP và cho phép nhận để quyết định các mức băng thông dành riêng
nhằm đạt được giới hạn trễ tốt nhất.
3. 2. 2. 14 Thuật toán lập lịch không lõi
Đặc thù của đồng hồ ảo là thực hiện kết hợp đơn giản việc lập lịch với giá
trị WFI nhỏ nhất như trong WF
2
Q. Trong phần này chúng ta sẽ nghiên cứu một
bộ lập lịch không lõi đơn giản được gọi là thuật toán Core-Stateless Shaped
Virtual Clock (CSSVC) -Thuật toán đồng hồ ảo định dạng không lõi, nó gần
giống với việc xử lý của một mạng đồng hồ ảo được định dạng mà không giữ lại

và V
s
(t) là hệ thống thời gian ảo của node s tại thời gian t. Khi một gói đến tại
thời gian a
k
si,
, S
k
si,
được định nghĩa như sau:
S
k
si,
= max [V
S
(a
k
si,
), F
1
,
k
si
] = max [a
k
si,
, F
1
,
k

r
l
max
+
S
i
r
ll
max,max

(3.
30)
r
s
là tốc độ phục vụ của server s, L
i, max
là độ dài lớn nhất của gói tại phiên i
còn L
max
là độ dài lớn nhất của gói tại server s.
Định lý 3. 2 : Trong một mạng có hai server đồng hồ ảo định dạng, nếu
server 1 và 2 có thể đảm bảo WFI của phiên i là WFI
i, 1
và WFI
i, 2
thì WFI end-
to-end của mạng WFI
i, 1
+ WFI
i, 2

×D
i, s
– σ
i
(3. 31)
WFI
b
si,
= r
i
× WFI
i, s
.
Vì thế (3. 31) trở thành:
WFI
i, s
=D
i, s
–σ
i
/r
i
(3. 32)
thay s = 1 và s = 2 ta có:
D
i, 1
=
i
i
r

= 2x
i
i
r

+ WFI
i, 1
+ WFI
i, 2
(3. 35)
Số hạng đầu trong phương trình trên
i
i
r

sinh ra từ trễ của gáo rò định dạng
và có thể chỉ có một lần trong mạng. Do vậy giới hạn trễ tại điểm cuối của server
2 sẽ là: si
D
,
=
i
D -
i
i
r


i, 1
+D
i, 2
-
i
i
r

-
i
i
r

(3. 38)
Kết hợp (3. 33) và (3. 34) ta có :

i
WFI =WFI
i, 1
+WFI
i, 2
(3. 39)
 Thuật toán đồng hồ ảo định dạng không lõi
Như đã thấy ở (3. 28) và (3. 29) thuật toán đồng hồ ảo định dạng cần hai
trạng thái biến đổi cho mỗi luồng i: tốc độ định trước r
1
và thời gian kết thúc ảo
của gói trước F
1
,

S
1
,
k
si
=a
k
si,
+X
k
si,
 F
1
,
k
si
(3. 40)
Đồ án tốt nghiệp Chương 3: Scheduling
Mục đích của chúng ta là sử dụng mạng CSSVC gần giống với việc xử lý
của một mạng đồng hồ ảo định dạng không giữ lại thông tin trạng thái của luồng
tại các node lõi. Khi gói thứ k của phiên i dến các node biên trong mạng CSSVC
tại thời gian a
k
si,
và xuất phát từ node s tại thời điểm d
k
si,
nó sẽ trải qua các giới
hạn WFI end-to-end, C
i, s

max
(3. 42)
d
k
si,
và d
k
si,
(fluid) lần lượt là thời gian mà gói thứ k của phiên i xuất phát tại
node s dưới dạng gói đồng hồ ảo định dạng và kiểu fluid. Khi chúng ta sử dụng
CSSVC gần giống với việc xử lý của mạng đồng hồ ảo định dạng và (3. 42) sẽ
giữ tại mỗi node CSSVC bao gồm cả node s. Trong khi đó phiên i được phục vụ
tại tốc độ r
i
ở dạng fluid và chúng ta sẽ giữ d
k
si,
(fluid) như sau :
d
k
si,
(fluid)=S
k
si,
+
i
k
i
r
L

-F
k
si,
-a
k
si,

S
r
L
max
-a
k
si,
(3. 46)
Hay :
d
k
si,
-a
k
si,
F
k
si,
+
S
r
L
max

D
,
end-to-end là:

k
Si
D
,
=
S
i
i
i
C
r


(3.
49)
Khi xét đến trễ tuyến (3. 49) trở thành:

k
Si
D
,
=
S
i
i
i


k
Si
D
,
=D
k
i, shaper
+C
i, S
+




1
1
S
h
h
(3. 51)
Đồ án tốt nghiệp Chương 3: Scheduling
Việc thiết lập sự mô tả lưu lượng (R
a
, R
p
, và MBS) trễ của việc định dạng
lưu lượng trong router biên có kết quả là: L
i, max
/R

+




1
1
S
h
h
(3. 52)
Thay F
k
si,
bằng S
k
si,
+
i
k
i
r
L
ta có :
S
k
si,
=a
k
si,

bằng :
S
k
Si 1, 
=a
k
i 1,
-
1
max
S
r
L
+D
k
i, shaper
+C
i, S-1
+




2
1
S
h
h
-
i

S
r
L
max
+
S-1
(3. 55)
Lặp lại phương trình trên ta có:
S
k
si,
=S
k
si,
+C
i, S-1
-WFI
i, S
+
11
max
r
L
-
S
r
L
max
+


Bằng cách sử dụng (3. 56) ta có bất phương trình giữa gói thứ k và k-1 tại
node biên 1 là:
S
k
si,
S
1
1,
k
i
+
i
k
i
r
L
1
(3. 57)
Vế phải của bất phương trình là hiệu của S
k
si,
đảm bảo:S
k
si,
 F
1
,
k
si
. Chúng

=a
k
si,
+X
k
si,
=d
k
si 1, 
+ 
S-1
+ X
k
si,
(3. 59)
Trong đó d
k
si 1, 
là thời gian xuất phát của gói tại node s-1 . Từ (3. 45) :
d
k
si 1, 
 F
k
si 1, 
+
1
max
S
r

k
i
r
L
+
1
max
S
r
L
+
S-1
+X
k
si,
(3. 61)
Để có kết quả chúng ta có thể đặt S
k
si,
là :
S
k
si,
=S
k
si 1, 
+
1S
k
i

L
+
S-1
+X
k
si,
=S
k
Si 1, 
+WFI
i, S
+
1
max
S
r
L
-
S
r
L
max
+
S-1
(3. 63)
Sắp xếp lại các thời kì ta có trạng thái biến đổi :
X
k
si,
=WFI

i
r
L
max,
-
1S
k
i
r
L
-
S
r
L
max

=
i
i
r
L
max,
-
1S
k
i
r
L
-
s

Hình 4. 1 Mô hình mạng Viễn thông thế hệ mới
Trong đó các lớp dưới mạng được xây dựng dựa trên hệ thống mạng cáp
quang và các công nghệ RAS, DSL, Frame Relay cũng như hệ thống truy nhập vô
tuyến thế hệ thứ ba. Các hệ thống này được kết nối lên mạng lõi thông qua hệ
thống tập trung. Phần mạng lõi là sự kết hợp của công nghệ IP và MPLS kết nối
với mạng thoại PSTN thông qua hệ thống Media Gateway. Chuyển mạch dịch vụ
IP và hệ thống Media Gateway sẽ đóng vai trò là cầu nối cho lớp điều khiển dịch
vụ kết nối xuống lớp mạng. Lớp diều khiển dịch vụ gồm hai hệ thống chính là
Server điều khiển dịch vụ và hệ thống chuyển mạch mềm. Trong đó, Server điều
khiển dịch vụ điều khiển các ứng dụng và dịch vụ IP để đảm bảo các yếu tố:
 Chất lượng dịch vụ
 Kiểm tra quyền sử dụng dịch vụ
 Quản lý bảo mật
 Quảng bá dịch vụ
Chuyển mạch mềm sẽ điều khiển các kết nối đa phương tiện bao gồm :
Đồ án tốt nghiệp Chương 3: Scheduling
 Kết nối VoIP và Video
 Điều khiển các đầu cuối IP theo các giao thức H. 323 và SIP
 Điều khiển các Media Gateway ở lớp mạng
Lớp ứng dụng sẽ kết nối xuống các hệ thống Server điều khiển và chuyển
mạch mềm thông qua lớp thích nghi ứng dụng. Các dịch vụ của lớp ứng dụng bao
gồm các ứng dụng thế hệ thứ 3, các ứng dụng tin nhắn và các dịch vụ trên nền
Web.
4. 2. Mạng truyền dẫn
Xây dựng một mạng đường trục có đủ năng lực truyền dẫn tất cả các nhu cầu
trao đổi thông tin của toàn bộ khách hàng luôn là một yêu cầu có tính hàng đầu trong
quá trình phát triển mạng Viễn thông. Hình 4. 2 đưa ra cấu hình mạng truyền dẫn
mục tiêu của nước ta. Trong đó có một sự thống nhất chung là sử dụng cáp sợi
quang và công nghệ DWDM để xây dựng lên một mạng toàn quang có đủ khả năng
để đáp ứng nhu cầu lưu lượng mạng IP đồng thời giảm giá thành băng thông truyền

ChuyÓn m¹ch / bé ®Þnh tuyÕn quang
Bé xen/t¸ch kªnh quang Bé ®Þnh tuyÕn biªn

HÖ thèng ghÐp sãng quang
Nót ®a dÞch vô

Đồ án tốt nghiệp Chương 3: Scheduling
 Nhà cung cấp dịch vụ di động GSM phải nhận định rõ hơn công nghệ
truy nhập mà họ sở hữu và họ sẽ thử triển khai các công nghệ truy nhập
mới.
 Phát triển hình thức truy nhập băng rộng bằng cáp đồng trục theo công
nghệ xDSL.
4. 4. Sự phát triển của các mạng lên NGN
4. 4. 1 Sự hội tụ các mạng

4. 4. 2 Sự tiến hoá của các mạng lên NGN
 Sự phát triển từ PSTN lên NGN
Thoại luôn là dịch vụ được xét đến hàng đầu trong quá trình xây dựng mạng.
Ở đây ta xét một minh hoạ về sự chuyển dịch thoại từ PSTN lên NGN
Mạng PSTN hiện tại :
Đồ án tốt nghiệp Chương 3: Scheduling

Đồ án tốt nghiệp Chương 3: Scheduling
Phát triển lên NGN :