MỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN VIỆC TÌM ĐƯỜNG

MÔ HÌNH HỆ THỐNG ROUTING TĨNH

I. GIỚI THIỆU :

Để xem xét một hệ thống mạng phục vụ cho việc tìm đường cho truyền
message như thế nào. Ta xây dựng một mô hình mô phỏng cho mạng để nghiên
cứu tính hiệu quả của mạng phục vụ việc truyền nhận các message như thế nào.
Ở đây ta đánh giá thời gian delay trung bình của mỗi message trong hệ thống.
Mô hình hệ thống routing tĩnh giống như mô hình hệ thống mạng hàng, gồm
mỗi hàng đơn là M/M/1. Hệ thống này là một mạng hàng mơ, khách hàng từ
ngoài hệ thống có thể vào bất kỳ Slave nào trên mạng và rời khỏi hệ thống khi
được phục vụ xong. Khách hàng đi trên đường liên lạc của mạng. Đường đi của
khách hàng trong hệ thống được xác định trước theo thuật giải tìm đường
routing tĩnh (xác định qij_xác suất mà khách hàng sau khi phục vụ ở Slave i và
đi đến nút j).
Mỗi trung tâm xử lý i tương ứng với link i của mạng bao gồm một Slave với
tốc độ phục vụ (i và hàng chờ của các message cần gởi trên mạng(có giới hạn).
Hàng được phục vụ theo cơ chế FIFO. Hàng đợi ở mỗi node là có giới hạn vì
thường tài nguyên của mạng đều có giới hạn. Tốc độ đến của khách hàng
(message) vào hệ thống do người đánh giá hệ thống nhập vào .
II. CÁC THÔNG SỐ CỦA HỆ THỐNG :
Tốc độ phục vụ tại Slave i là m i=tốc độ truyền của link i/chiều dài của
message e
Tốc độ đến tại hàng đợi của Slave i là l i =g i + (qji (trong đó e là số đường kết
nối của mạng. j=1
Thời gian đợi trung bình của message là T = N/ g .
trong đó: g là tốc độ đến của khách hàng vào hệ thống.
N là số khách hàng trung bình trong hệ thống.
Hệ thống này được mô phỏng để đánh giá thời gian chờ (delay) trung bình của

hơn. Điều đó có nghĩa là con đường được chọn phải mạnh. Đảm bảo một só
yêu cầu cần thiết trong chức năng đường truyền như thoả mản các tính chất
sau:
 Correctrer and Simplicity ( đúng và đơn giản). Đảm bảo các packet phải
đến được nơi nhận và thuật toán phải dể hiện thực.
 Robustrer (Linh động). Có khả năng hoạt động ngay sau khi thay đổi về
hệ thống.
Thay đổi:
Topology.
Traffic.
Cũng như những sự cố bất thường xãy ra trong một mạng máy tính thường
xuyên.
 Công bằng và tối ưu: Các thuật toán phải đảm bảo công bằng và cố gắng
truyền các packet tới nơi nhận nhanh nhất.
- Sự chọn đường thường dựa vào tiêu chuẩn đơn giản là chọn đường đi ngắn
nhất (một đường thông qua mạng với it1 node nhất ) thông qua mạng. Tiêu
chuẩn chung cho đường ngắn nhất là đường giá trị nhỏ nhất không trong trường
hợp đó, giá trị bao gồm cho tường đường, và đường thông qua mạng bao gồm
tích lũy giá trị bé nhất.
- Để giải quyết các yêu cầu trên người ta đưa ra các giải thuật tìm đường đi
ngắn nhất theo từng trường hợp khác nhau, mà em đi tìm hiểu cũng như đi
phân tích các giải thuật đó.
- Do đó có nhiều kỹ thật tìm đường khác nhau. Sự phân biệt giữa chúng chủ
yếu căn cứ vào các yếu tố liên quan đến hai chức năng trên, đó là:
 Sự phân tán của các chức năng trên các nút của các mạng. (a)
 Sự thích nghi của trạng thái hiện hành của mạng. (b)
 Các tiêu chuẩn tối ưu để chọn đường. (c)
Dựa vào yếu tố (a) ta có kỹ thuật tìm đường tập trung (centralized routing)
hoặc phân tán (Dynamic routing).
Dựa vào yếu tố (b) ta có kỹ thuật tìm đường tĩnh (static routing) hoặc tìm

- Tìm đường phân tán: Không tồn tại các trung tâm điều khiển, quyết định
tìm đường được thực hiện tại mỗi nút của mạng. Điều này đòi hỏi việc trao
đổi thông tin giữa các nút, tuỳ theo mức độ thích nghi của giải thuât5 được
sử dụng.
- Tìm đường tĩnh: Có thể là tập trung hay phân tán nhưng nó không đáp ứng
với mọi sự thay đởi trên mạng. Trong trường hợp này, chọn đường được
thực hiện mà không có sự trao đổi thông tin, khôn g đo lường và không cập
nhật thông tin. Tiêu chuẩn tối ưu để chọn đường và bản thân con đường
được chọn một lần cho toàn cuộc, không hề có sự thay đổi giữa chúng. Các
kỹ thuật tìm đường tĩnh rõ ràng là rất đơn giản, do vậy sử dụng rất rộng rãi,
đaặc biệt trong các mạng tương đối ổi định it1 có thay đổi về topology và
lưu thông trên mạng .
- Tìm đường động: Thu hút sự quan tâm của các nhà thuyết kế mãng do khả
năng thuyết kế đáp ứng đối với các trạng thái khác nhau của mạng, vì đây là
yếu tố quan trọng, đặc biệt đối với các ứng dụng, thời gian thực trong đó
yêu cầu đầu tiên của người sử dụng là mạng phải có khả năng cung cấp
được các con đường khác nhau để dự phòng sự cố và thích nghi nhanh
chóng với các thay đổi trên mạng. Mức độ thích hợp của một kỹ thuật con
đường được đặc trưng bởi trao đổi thông tin chọn đường trên mạng
 Tóm lại: Trong đề tài này em tìm hiểu các giải thuật tìm đường trong lý
thuyết và thực tế đã áp dụng các kỹ thuật tìm đường đã nêu ở trên. Và khi tìm
hiểu các giải thuật tìm đường ứng dụng trong lý thuyết và thực tế để hiểu rỏ
hơn về cách áp dụng được hợp lý.

IV. Bài toán tìm đường đi ngắn nhất (SHORTEST PATH ROUTING) :

Bài toán tìm đường đi ngắn nhất là tìm đượng đi trong một đồ thị có trọng số
(chiều dài) nối hai đỉnh x và y đã cho trước với đặc tính là tổng các trọng số
của tất cả các cạnh là nhỏ nhất trong tất cả các đường đi từ đỉnh x đến đỉnh y.
Nếu tất cả các trọng số đều bằng 1 thì bài toán này trở thành bài toán tìm đường

hai vận tốc khác nhau. Đến một lúc nào đó hai đối tượng này gặp nhau, thì đây
chính là điểm dừng của giải pháp động.
A. Lập trình song song
1. Mục đích:
Mục đích của xử lý song song là thực hiện việc tính toán nhanh hơn hay giải
quyết vấn đề lớn như : điều khiển không lưu, dự báo thời tiết, hệ thống thời
gian thực…
Để giải quyết những vấn đề này người ta phải chia nhỏ vấn đề ra và sử dụng
nhiều processor để tính toán song song. Có hai hệ thống được ứng dụng để giải
quyết vấn đề này.
a) Máy tính song song:
Máy này bao gồm một nhóm các processor cùng loại, được kết nối với nhau
theo một mô hình nào đó để cho phép chúng cùng hoạt động và trao đổi dữ liệu
cho nhau.
b) Hệ thống phân bố:
Là hệ thống gồm nhiều processor có thể có kiễu khác nhau và được phân bố
trên một vùng địa lý rộng (mạng máy tính).
2. Đánh giá hiệu quả của giải thuật song song:
Cách tính 1 :
Lấy B là vấn đề cần tính toán, n là kích thước của bài toán. Độ phức tạp của
giải thuật tuần tự để giải quyết vấn đề là T*(n). với giả sử là không có giải
thuật tuần tự nào tốt hơn giải thuật này. Gọi A là thuật giải song song giải quyết
p trong thời gian Tp(n) trên máy tính song song gồm p processor.
Speedup có được nhờ sử dụng giải thuật song song A được xác định:
Trong đó p là số processor có sẵn trong hệ thống.
Ngoài ra, người ta còn đo hiệu suất của giải thuật song song A bằng độ hiệu
quả Ep(n)
Gọi T¥ (n) là thời gian mà giải thuật không thể chạy nhanh hơn nữa với bất kỳ
số p nào. Vì Tp(n) ³ T¥ (n), do đó:
Độ hiệu quả sẽ giảm nhanh khi p tăng vượt quá T1(n)/T¥ (n).

Xãy ra khi một hoạt động nạp một vị trí nhớ mà vị trí nhớ này cũng được nạp ở
hoạt động sau. trong ví dụ trên, phát biểu (3) phải thực hiện sau phát biểu (1)
nếu không A sẽ chứa dữ liệu sai.
- Sự phụ thuộc điều khiển (control dependence)
loại phụ thuộc này là do dòng điều khiển trong chương trình. Trong ví dụ sau,
phát biểu 2 được thực thi phụ thuộc vào kết quả kiểm tra điều kiện 1.

If (x<0) (1)
A=B+5; (2)
Nếu trong chương trình ta xác định được các biểu thức nào là phụ thuộc và
không phụ thuộc ta sẽ hiện thực cho chúng làm tuần tự hay song song.
- Sự đồng bộ các quá trình
Sự đồng bộ các quá trình đóng vai trò quan trọng trong lập trình song song.
Giải thuật có thành công hay không phụ thuộc rất lớn vào sự đồng bộ.
Có hai phương pháp đồng bộ
•Đồng bộ toàn cục :
Với phương pháp đồng bộ toàn cục, tất cả các proces cần đồng bộ với nhau sử
dụng một sự kiện toàn cục nào đó (ví dụ dùng bộ đếm). Các process sẽ chờ cho
đến khi tất cả sẵn sàng mới làm tiếp các bước kế tiếp các process trong nhóm sẽ
block cho đến khi tất cả đều tham gia vào nhóm.
•Đồng bộ cục bộ :
Các process vẫn thực hiện công việc riêng của mình và chỉ khi có tín hiệu báo
của process khác đến mới xử lý các dữ liệu liên quan đến prcess đồng bộ.
Trong việc sử dụng bộ nhớ dùng chung của các máy tính song song còn có một
vấn đề cần quan tâm đó là sự tranh chấp tài nguyên (đọc ghi vùng nhớ) dẫn đến
kết quả sai. Để giải quyết trường hợp này người ta dùng semaphore.
4. Giới thiệu bài toán tìm đường đi ngắn nhất.
Giả sử có mỗi một process tại mỗi đỉnh và mọi process là đồng bộ. Chúng ta có
một giải thuật tìm đương đi ngắn nhất phân bố theo thời gian O( d.p2) ở đay d
là bậc cực đại của đỉnh .