35

hàng đợi và cũng từ đó ảnh hưởng tới QoS của các loại dịch vụ cung
cấp trên mạng.
Các thông số của hàng đợi được xác định thông qua lý thuyết xác suất
thống kê, định lý Little, qui tắc duy trì hàng đợi Kleinrock và quan trọng
hơn cả là các tiến trình đi - đến của khách hàng là các tiến trình
Poisson với phân bố hàm mũ cùng với thuật toán xếp hàng của nó.
Xác định các thông số hàng đợi như: chiều dài hàng đợi ở các thời
điểm bất kỳ hoặc ngay cả khi có khách hàng, … qua đó đưa ra các
phương án điều khiển lưu lượng trên mạng cho phù hợp nhằm giảm
thiểu các sự cố trên mạng đánh giá được hiệu suất sử dụng tài nguyên
đồng thời xác định được cấp QoS mà có thể cung cấp trên mạng, đó
là cơ sở cho việc thiết kế các mạng hệ thống viễn thông sau này.
2.7. Bài tập (Pending) 36Chương 3 Mạng hàng đợi

3.1. Mạng nối tiếp


V={v
i
| i=1,2, N}
Trong đó N là số lượng nút. Tương tự E được biểu diễn:
E={e
i
| i=1,2, M}
Một liên kết, ej, tương ứng một kết nối giữa một cặp nút. Có thể biểu
diễn một liên kết ej giữa nút i và k bởi

38

e
j
=(v
i
,v
k
)
hoặc bởi
e
j
=(i,k)
Một liên kết gọi là đi tới một nút nếu nút đó là một trong hai điểm
cuối của liên kết. Nút i và k gọi là kề nhau nếu tồn tại một liên kết (i, k)
giữa chúng. Những nút như vậy được xem là các nút láng giềng.
Bậc của nút là số lượng liên kết đi tới nút hay là số lượng nút láng

việc lập mô hình cho mạng lẫn quá trình hoạt động bên trong của các
thuật toán, vì vậy sự khác nhau cần phải luôn được phân biệt rõ ràng.
Về mặt hình học các liên kết là các đường thẳng kết nối các cặp nút
còn các cung là các đường thẳng có mũi tên ở một đầu, biểu diễn
chiều của cung.
Một graph có các liên kết gọi là graph vô hướng, tuy nhiên một
graph có các cung gọi là graph hữu hướng. Một graph hữu hướng
có thể có cả các liên kết vô hướng. Thông thường , các graph được
giả sử là vô hướng, hoặc sự phân biệt đó là không có ý nghĩa.
Có thể có khả năng xảy ra hiện tượng xuất hiện nhiều hơn một liên kết
giữa cùng một cặp nút (điều này tương ứng với việc có nhiều kênh
thông tin giữa hai chuyển mạch). Những liên kết như vậy được gọi là
các liên kết song song. Một graph có liên kết song song gọi là một
multigraph.

39

Cũng có khả năng xuất hiện các liên kết giữa một nút nào đó và chính
nút đó. Những liên kết đó được gọi là các self loop. Chúng ít khi xuất
hiện và thường xuất hiện do việc xem hai nút như là một nút trong quá
trình lập mô hình graph cho một mạng hoặc phát sinh trong quá trình
thực hiện một thuật toán có việc hợp nhất các nút. Hình 4.2 minh hoạ
một graph có các liên kết song song và các self loop. Một graph không
có các liên kết song song hoặc các self loop gọi là một graph đơn
giản. Việc biểu diễn và vận dụng các graph đơn giản là tương đối dễ
dàng, vì vậy giả thiết rằng các graph được xem xét là các graph đơn
giản. Nếu có sự khác biệt với giả thiết này, chúng sẽ được chỉ ra.

 Trong những ứng dụng cơ sở dữ liệu phân bố, đôi khi cần thiết
phải cập nhật tất cả cơ sở dữ liệu. Trong trường hợp đó sử dụng
lan tràn gói là cần thiết. Ví dụ sự dụng lan tràn gói để gửi cập nhật
bản định tuyến bởi vì cập nhật không dựa trên độ chính xác của
bảng định tuyến.

40

 Phương pháp lan tràn gói có thể được dùng như là đơn vị để so
sánh phương thức định tuyến khác. Lan tràn gói luôn luôn chọn
đường ngắn nhất. Điều đó dẫn đến không có giải thuật nào có thể
tìm được độ trễ ngắn hơn.
Một biến đổi của phương pháp lan tràn gói là lan tràn gói có chọn lọc.
Trong giải thuật này, router chỉ gửi gói đi ra trên các đường mà đi theo
hướng đích. Điều đó có nghĩa là không gửi gói đến những đường mà
rõ rang nằm trên hướng sai.
4.2.2. Định tuyến bước ngẫu nhiên (random walk)
Trong phương pháp định tuyến này, router sẽ chuyển gói đi đến trên
một đường đầu ra được chọn một cách ngẫu nhiên. Mục tiêu của
phương pháp này là các gói lang thang trong mạng cuối cùng cũng
đến đích. Với phương pháp này giúp cho quá trình cân bằng tải giữa
các đường. Cũng giống như phương pháp định tuyến lan tràn gói,
phương pháp này luôn đảm bảo là gói cuối cùng sẽ đến đích. So với
phương pháp trước thì sự nhân rộng gói trong mạng sẽ ít hơn. Nhược
điểm của phương pháp này là đường từ nguồn đến đích có thể dài
hơn đường ngắn nhất. Do đó trễ đường truyền sẽ dài hơn sẽ trễ ngắn
nhất thực sự tồn tại trong mạng.

xếp các đường theo trọng số tĩnh của nó và sau đó lại sắp xếp theo độ
dài hàng chờ của nó. Sau đó sẽ chọn đường có tổng vị trí sắp xếp là
nhỏ nhất. Dù giải thuật nào được chọn đi chăng nữa cũng có đặc tính
là khi ít tải thì đường có trọng số cao nhất sẽ được chọn, nhưng sẽ
làm cho hàng chờ cho đường này tăng lên. Sau đó một số lưu lượng
sẽ được chuyển sang đường ít tải hơn.
4.2.4. Định tuyến nguồn (source routing) và mô hình cây (spanning tree)
Chúng ta sẽ xét một số thuật toán cơ bản dùng cho việc tìm kiếm các
cây được sử dụng để thiết kế và phân tích mạng. Một cây là một graph
không có các vòng; bất kỳ một cặp nút nào cũng chỉ có duy nhất một
đường đi. ở đây chủ yếu xem xét các graph vô hướng, những graph
đó có các liên kết được sử dụng cả hai chiều trong quá trình tạo ra các
đường đi.
Vì một số lý do, các cây rất hữu dụng và được sử dụng như là graph
cơ bản cho các thuật toán và các kỹ thuật phân tích và thiết kế mạng.
Thứ nhất, các cây là mạng tối thiểu; cung cấp một sự kết nối mà không
một liên kết nào là không cần thiết. Thứ hai, do việc chỉ cung cấp duy
nhất một đường đi giữa một cặp nút bất kỳ, các cây giải quyết các vần
đề về định tuyến (nghĩa là quyết định việc chuyển lưu lượng giữa hai
nút). Điều đó làm đơn giản mạng và dạng của nó. Tuy nhiên, vì các
cây liên thông tối thiểu nên cũng đơn giản và có độ tin cậy tối thiểu. Đó
là nguyên nhân tại sao các mạng thực tế thường có tính liên thông cao
hơn. Chính vì vậy, việc thiết kế một mạng thường bắt đầu bằng một
cây.
4.2.5. Duyệt cây
Cho trước một cây nào đó, chúng ta có thể đi tới mọi nút của nó. Quá
trình đó gọi là một quá trình duyệt cây. Trong quá trình thực hiện, các
cạnh trong cây được duyệt hai lần, mỗi lần theo một hướng khác
nhau. Có nhiều cách duyệt khác nhau. Đầu tiên, chỉ ra một nút của cây
làm nút gốc. Việc duyệt được thực hiện xoay quanh nút đó. Có một số

void <-BfsTree ( n, root, n_adj_list ):
dcl n_adj_list [n, list ]
scan_queue [queue ]

InitializeQueue (scan_queue )
Enqueue( root, scan_queue )
while (NotEmpty(scan_queue))
node <- Dequeue (scan_queue)
Visit(node )
for each (neighbor , n_adj_list [node ])
Enqueue(neighbor, scan_queue) 43

Visit là một thủ tục trong đó thực hiện một số quá trình nào đó đối với
mỗi nút (chẳng hạn như in lên màn hình các thông tin của mỗi nút .v.v).
Thuật toán này được thực hiện cùng một hàng đợi. Hàng đợi là một
FIFO; trong đó các phần tử được thêm vào từ phía sau hàng đợi và
chuyển ra từ phía trước. Các thủ tục InitializeQueue, Enqueue,
Dequeue, NotEmpty làm việc trên các hàng đợi. InitializeQueue
thiết lập một hàng đợi rỗng. Enqueue, Dequeue là các thủ tục để thêm
một phần tử vào cuối hàng đợi và chuyển một phần tử ra từ đầu
hàng đợi. Hàm NotEmpty trả về TRUE hoặc FALSE tuỳ thuộc vào
hàng đợi có rỗng hay không.
n_adj_list là một chuỗi mà mỗi phần tử của chuỗi là một danh
sách. n_adj_list[n] là một danh sách các nút kề cận nút n. Như

Visit(root)
for each(neighbor, n_adj_list[node])

44

DfsTree(n, neighbor, n_adj-list)

Quá trình tìm kiếm này sẽ được thực hiện với sự trợ giúp của một
ngăn xếp theo kiểu LIFO, nghĩa là phần tử được thêm vào và chuyển
ra từ đỉnh ngăn xếp. Trong trường hợp này, chúng ta thường gọi đệ
quy DfsTree, thực tế chúng ta đã sử dụng ngăn xếp hệ thống, nghĩa
là sử dụng loại ngăn xếp mà hệ thống sử dụng để lưu giữ các lời gọi
hàm và đối số.
Cả hai loại duyệt trình bày ở trên đều là quá trình duyệt thuận (nghĩa là
các quá trình này duyệt một nút rồi sau đó duyệt tới nút tiếp theo của
nút đó). Quá trình duyệt ngược đôi khi cũng rất cần thiết, trong quá
trình duyệt ngược một nút được duyệt sau khi đã duyệt nút tiếp của
nút đó. Dĩ nhiên, cũng có thể thành lập một danh sách thuận và sau đó
đảo ngược danh sách đó. Cũng có thể thay thế trật tự tìm kiếm một
cách trực tiếp như thủ tục sau:
void <- PostorderDfsTree(n, root, n_adj_list):
dcl n_adj_list [n, list]

for each(neighbor, n_adj_list[node])
PostorderDfsTree(n, neighbor,
n_adj_list)
Visit (root)

Dfs nên DfsLoop có thể truy cập tới visited và n_adj_list (Lưu ý
rằng cách dễ nhất để đọc các giả mã cho các hàm có dạng hàm Dfs ở
trên là trước tiên hãy đọc thân của hàm chính rồi quay trở lại đọc thân
của các hàm nhúng như hàm DfsLoop).
Chú ý rằng trong quá trình duyệt chúng ta đã ngầm kiểm tra tất cả các
cạnh trong graph, một lần cho mỗi đầu cuối của mỗi cạnh. Cụ thể, với
mỗi cạnh (i, j) của graph thì j là một phần tử của n_adj_list[i] và i
là một thành phần trong n_adj_list[j]. Thực tế, có thể đưa chính
các cạnh đó vào các danh sách kề cận của nó và sau đó tìm nút ở
điểm cuối khác của cạnh đó bằng hàm:
node <- OtherEnd(node1, edge)
Hàm này sẽ trả về một điểm cuối của edge khác với node1. Điều đó
làm phức tạp quá trình thực hiện đôi chút. Có thể dễ dàng thấy rằng độ
phức tạp của các thuật toán duyệt cây này bằng O(E), với E là số
lượng cạnh trong graph.
Bây giờ chúng ta có thể tìm được các thành phần liên thông của một
graph vô hướng bằng cách duyệt mỗi thành phần. Chúng ta sẽ đánh
dấu mỗi nút bằng một chỉ số thành phần khi chúng ta tiến hành. Các
biến n_component sẽ theo dõi bất kỳ thành phần nào mà chúng ta đi
tới
void <- LabelComponent (n, n_adj_list):
dcl n_component_number [n],
n_adj_list[n,list]

void <- Visit [node]
n_component_number [node]<- ncomponents

n_component_number<-0
ncomponent<-0
for each(node, node_set)

Cây bắc cầu tối thiểu (Minimum Spanning Tree)
Có thể sử dụng Dfs để tìm một cây bắc cầu nếu có một cây bắc cầu
tồn tại. Cây tìm được thường là cây vô hướng. Việc tìm cây "tốt nhất"
thường rất quan trọng . Chính vì vậy, chúng ta có thể gắn một "độ dài"
cho mỗi cạnh trong graph và đặt ra yêu cầu tìm một cây có độ dài tối
thiểu. Thực tế, "độ dài" có thể là khoảng cách, giá, hoặc là một đại
lượng đánh giá độ trễ hoặc độ tin cậy. Một cây có tổng giá là tối thiểu
được gọi là cây bắc cầu tối thiểu.
Nói chung, nếu graph là một graph không liên thông, chúng ta có thể
tìm được một rừng bắc cầu tối thiểu. Một rừng bắc cầu tối thiểu là một
tập hợp các cạnh nối đến graph một cách tối đa có tổng độ dài là tối
thiểu. Bài toán này có thể được xem như là việc lựa chọn một graph
con của graph gốc chứa tất cả các nút của graph gốc và các cạnh
được lựa chọn. Đầu tiên, tạo một graph có n nút, n thành phần và
không có cạnh nào cả. Mỗi lần, chúng ta chọn một cạnh để thêm vào
graph này hai thành phần liên thông trước đó chưa được kết nối được
liên kết lại với nhau tạo ra một thành phần liên thông mới (chứ không
chọn các cạnh thêm vào một thành phần liên thông trước đó và tạo ra
một vòng). Vì vậy, tại bất kỳ giai đoạn nào của thuật toán, quan hệ:
n=c+e

47

luôn được duy trì, ở đây n là số lượng nút trong graph, e là số cạnh
được lựa chọn tính cho tới thời điểm xét và c là số lượng thành phần
trong graph tính cho tới thời điểm xét. Ở cuối thuật toán, e bằng n trừ
đi số thành phần trong graph gốc; nếu graph gốc là liên thông, chúng

Các yêu cầu các khả năng sau:
 So sánh giá trị của các phần tử để xác định phần tử nào là "tốt
nhất"
 Kiểm tra tính khả thi của một tập các phần tử
Khái niệm "tốt nhất" liên quan đến mục đích của bài toán. Nếu mục
đích là tối thiểu, "tốt nhất" nghĩa là bé nhất. Ngược lại, "tốt nhất" nghĩa
là lớn nhất.

48

Thường thường, mỗi giá trị gắn liền với một phần tử, và giá trị gắn liền
với một tập đơn giản chỉ là tổng các giá trị đi cùng của các phần tử
trong tập đó. Đó là trường hợp cho bài toán cây bắc cầu tối thiểu được
xét trong phần này. Tuy nhiên, đó không phải là trường hợp chung.
Chẳng hạn, thay cho việc tối thiểu tổng độ dài của tất cả các cạnh
trong một cây, mục đích của bài toán là tối thiểu hoá độ dài các cạnh
dài nhất trong cây. Trong trường hợp đó, giá trị của một cạnh là độ dài
của cạnh đó và giá trị của một tập sẽ là độ dài của cạnh dài nhất nằm
trong tập.
Muốn tìm được cạnh "tốt nhất" để bổ sung, hãy đánh giá các cạnh
theo độ ảnh hưởng về giá trị của nó tới giá trị của tập. Giả sử V(S) là
giá trị của tập S và v(e,S) là giá trị của một phần tử e thì v(e,S) có quan
hệ với tập S bởi công thức
v(e,S)= V(S

e) - V(S)
Trong trường hợp tối thiểu độ dài của cạnh dài nhất trong một cây.