Xem mẫu
- ĐỒ ÁN TỐT NGHIỆP CÔNG NGHỆ PHẦN MỀM “KĨ
THUẬT LƯU LƯƠNG IP/WDM”
CHƯƠNG III TÁI CẤU HÌNH TRONG KĨ THUẬT LƯU
LƯỢNG IP/WDM
3.1 Tái cấu hình mô hình ảo đường đi ngắn nhất
Trong các mạng WDM có khả năng tái cấu hình, liên kết IP được xây dựng
trên các đường đi ngắn nhất WDM đa hop. Một lợi ích về mặt chi phí của mạng
quang WDM là nó có thể hoạt động mà chỉ cần sự hỗ trợ tương đối nhỏ (đặc biệt là
trong mạng đường trục). Điều này có nghĩa là nhiều kết nối IP khác nhau có thể
chia sẻ cùng một tuyến nối vật lí chung và tuyến nối ảo IP sẽ được định tuyến qua
các hop chuyển mạch WDM.
Hình 3.1 mô tả mô hình ảo và định tuyến trong các mạng WDM tái cấu hình
được. Có ba thành phần chính trong sơ đồ:
Định tuyến lưu lượng
Thiết lập cấu hình IP
Định tuyến đường đi ngắn nhất
Định tuyến lưu lượng chính là định tuyến gói tin truyền thống, ví dụ như
OSPF. Thiết lập cấu hình IP sẽ được trình bày trong phần này. Trong khi đó định
tuyến đường đi ngắn nhất cung cấp khả năng ánh xạ từ mô hình IP ảo sang mô
- hình WDM vật lí. Định tuyến đường đi ngắn nhất bao gồm hai mặt liên quan mật
thiết với nhau: chọn đường đi trong sợi và gán bước sóng. Định tuyến đường đi
ngắn nhất có thể được triển khai theo một trong hai cách sau:
Định tuyến đường đi ngắn nhất tĩnh: phương pháp này tính toán trước
và lưu trữ các đường đi định tuyến. Các đường dự phòng thay thế cho
mỗi đường đi chính cũng có thể được tính toán và lưu trữ sẵn. Gán
bước sóng được thực hiện ngay khi có yêu cầu kết nối đường đi ngắn
nhất. Phương pháp này sử dụng các cơ chế gán bước sóng rất đơn giản.
Gán bước sóng có thể thực hiện theo cơ chế ngẫu nhiên hoặc cơ chế
chọn kênh sóng phù hợp đầu tiên.
Định tuyến đường đi ngắn nhất thích ứng : phương pháp này s ử dụng
thuật toán SPF (chọn đường đi ngắn nhất đầu tiên) động để định tuyến.
Thuật toán này đòi hỏi thông tin về trạng thái tuyến nối phải được phổ
biến tới các node. Vì sự xuất hiện của các cơ sở dữ liệu trạng thái tuyến
nối mang tính cục bộ nên gán bước sóng có thể trở nên phức tạp hơn.
Một số cơ chế gán bước sóng là: chọn kênh bước sóng có tải ít nhất,
được sử dụng nhiều nhất hay có tốc độ dữ liệu kết nối phù hợp nhất.
- Hình 3.1 Thiết kế và định tuyến mô hình ảo
Thiết kế mô hình IP và định tuyến đường đi ngắn nhất là các chức năng mặt
phẳng điều khiển trong khi đó định tuyến lưu lượng là thành phần duy nhất được
sử dụng để chuyển tiếp gói tin cũng như định tuyến gói tin.
Vì cả thiết kế mô hình ảo và định tuyến đường đi ngắn nhất là các chức năng
mặt phẳng điều khiển nên hai thành phần này có thể được kết hợp hoặc kết nối rất
gần nhau. Phương pháp kết nối gần nhau dùng cho giải pháp kĩ thuật lưu lượng
IP/WDM chồng lấn trong khi phương pháp kia dùng cho giải pháp kĩ thuật lưu
lượng IP/WDM tích hợp. Trong một ứng dụng kĩ thuật lưu lượng riêng rẽ thì định
tuyến đường đi ngắn nhất dựa trên các điều kiện ràng buộc có thể bổ sung như là
một công cụ đánh giá cho thuật toán thiết kế mô hình. Phương pháp này đảm bảo
rằng mô hình được thiết kế có thể trở thành hiện thực trong tầng WDM với các
dung lượng hiện có.
- Trong mạng IP/WDM chồng lấn, tầng chủ có thể do một nhà cung cấp dịch
vụ truyền dẫn cung cấp. Họ cung cấp cho nhiều máy khách dịch vụ khác nhau,
chẳng hạn như các khách hàng VPN. Với hình thức như thế thì một khách hàng tại
tầng IP sẽ thuê các dịch vụ truyền dẫn từ mạng WDM. Trong hợp đồng dịch vụ,
khách hàng sẽ chỉ rõ một tập các bộ định tuyến IP cố định kết nối trực tiếp với
mạng WDM. Tầng WDM cung cấp các kết nối ngắn nhất giữa các bộ định tuyến
đó. Tuy nhiên, không giống các kết nối đường dây thuê riêng trong các VPN hiện
nay, sự sắp xếp của các kết nối ngắn nhất ảo ấy là không cố định. Trong khi số
lượng các kết nối ngắn nhất ấy là cố định hoặc có giới hạn thì mỗi kết nối đường đi
ngắn nhất có thể được gán lại để kết nối một cặp bộ định tuyến khác nhau, đáp
ứng theo sự thay đổi động các kiểu yêu cầu lưu lượng khác nhau. Điều này đòi hỏi
một thuật toán thiết kế mô hình ảo tại tầng IP. Ở đây, mô hình ảo là một sơ đồ chứa
các node và các tuyến nối. Các node này là các bộ định tuyến trong khi các tuyến
nối là các kết nối đường đi ngắn nhất WDM.
Tiếp theo, đồ án sẽ trình bày về vấn đề này và sau đó chỉ ra một số giải pháp
tại thời điểm hiện tại. Một số thuật toán dựa trên kinh nghiệm để tối ưu hoá thông
lượng mạng và/hoặc khoảng cách hop cũng sẽ được giới thiệu. Các kết luận dựa
trên kinh nghiệm này có thể được sử dụng để phát triển một thuật toán mới đáp
ứng các mục tiêu khác nhau.
3.1.1 Mô hình ảo có quy tắc và bất quy tắc
Mô hình có quy tắc tức là mô hình có các kết nối node theo một kiểu xác định
rõ ràng trong khi mô hình bất quy tắc thường được xây dựng động để tối ưu hoá
các ma trận hiệu năng nhất định. Mô hình có quy tắc được xây dựng và tồn tại dựa
trên các nghiên cứu có tính hệ thống và các khái niệm được chấp nhận rộng rãi.
Định tuyến và quản lí trong mô hình có quy tắc thường đơn giản nhưng bổ sung
- hoặc loại bỏ một node bất kì trong một mô hình có kiến trúc (trong khi vẫn duy tr ì
mô hình đó) là rất khó khăn. Một số ví dụ của mô hình có quy tắc là:
Ring
Shuffle-Net
Manhattan Street Network (MSN hay 2D Torus)
GEMNet
HyperCube
deBruijn Graph
Các mô hình có quy tắc trên thường có độ phức tạp định tuyến thấp và là đối
xứng trong khi sự khác biệt của chúng nằm ở số lượng các bộ thu phát cần thiết,
khả năng mở rộng và khả năng chấp nhận lỗi. Ví dụ như một mạng n–aray
hypercube với N node cần (n-1)lognN bộ thu phát cho mỗi node và sẽ có khoảng
cách hop trung bình là lognN và đường kính mạng là lognN. So với nó thì một
MSN chỉ cần hai bộ thu phát cho một node nhưng cả khoảng cách hop trung bình
và đường kính mạng đều bằng N . Mô hình Shuffle-Net cũng có khoảng cách hop
trung bình nhỏ hơn MSN vì với một bước sóng cho trước, nó có nhiều đường lựa
chọn hơn từ node một đầu cuối tới một node đầu cuối bất kì khác. Tuy nhiên, nó
cần nhiều bộ thu phát cho một node hơn. Cụ thể trong trường hợp này là n cho một
node. Trong phần còn lại, các mô hình bất quy tắc sẽ được xem xét cụ thể vì chúng
có thể được tối ưu hoá để hỗ trợ các kiểu lưu lượng đồng dạng và không đồng dạng
nhất định.
- 3.1.2 Thiết kế mô hình
Khi thiết kế mô hình thì các mục tiêu hiệu năng được lựa chọn là khác nhau.
Các mục tiêu này là nhân tố quyết định và có hai kiểu mục tiêu cơ bản. Một kiểu là
hướng ứng dụng, nghĩa là nó thường liên quan tới tỉ lệ QoS ở mức ứng dụng ví dụ
như trễ từ đầu cuối tới đầu cuối. Kiểu còn lại là hướng mạng, nghĩa là nó thường
có liên quan tới các mức tận dụng tài nguyên mạng, ví dụ như thông lượng tổng.
Thông tin đầu vào của thiết kế mô hình là ma trận nhu cầu lưu lượng. Với một
mạng IP gồm N bộ định tuyến, ma trận lưu lượng là một ma trận T có kích thước N
x N, trong đó phần tử T(i,j) là dòng lưu lượng tổng (đo dưới dạng b/s) từ bộ định
tuyến i tới bộ định tuyến j. Các giá trị của các phần tử có thể đ ược xác định nhờ
các kĩ thuật dự đoán nhất định dựa trên các kết quả đo hiện tại. Phần dự đoán xu
hướng lưu lượng sẽ được xem xét riêng, còn phần này sẽ tập trung đề cập tới các
vấn đề thiết kế mô hình. Do vậy, có thể định nghĩa ma trận nhu cầu lưu lượng,
T(i,j), bằng với các phép đo độ lớn lưu lượng giữa bộ định tuyến i và bộ định tuyến
j trong một cửa sổ thời gian điều khiển được. Thuật toán thiết kế mô hình có thể rút
ra từ các công cụ phần mềm dự đoán cho nhu cầu băng thông dòng lưu lượng IP.
Các điều kiện khởi tạo có mối quan hệ mật thiết với thuật toán và mục tiêu tối
ưu hoá. Thuật toán thiết kế mô hình chấp nhận hai kiểu khởi tạo. Kiểu đầu tiên là
các thông số cảm ứng từ mạng, ví dụ như tình trạng tải tuyến nối là điều kiện cho
thích ứng tự động. Kiểu thứ hai là các quyết định quản trị từ bên ngoài mạng, ví dụ
như sử dụng thuật toán thiết kế mô hình nhờ giám sát dự đoán.
3.1.3 Một số thuật toán dựa trên kinh nghiệm
Thiết kế mô hình có thể sử dụng các thuật toán dựa trên kinh nghiệm. Một
thuận lợi của việc sử dụng các kinh nghiệm trong một thuật toán tối ưu có đòi hỏi
khắt khe trong việc thiết kế mô hình ảo chính là sự mềm dẻo. Trong khi thiết kế
- một thuật toán dựa trên kinh nghiệm, ta có thể tập trung vào một số mặt khác nhau
mà vẫn giảm được chi phí tính toán.
Thuật toán thiết kế mô hình đường đi ngắn nhất dựa trên kết quả điều
tra
Tồn tại ba thuật toán kiểu này: thuật toán thiết kế mô hình dựa trên kinh
nghiệm (HTDA), thuật toán thiết kế mô hình logic trễ tối thiểu (MLDA) và thuật
toán thiết kế mô hình logic không phụ thuộc lưu lượng (TILDA). HTDA cố gắng
tạo ra các đường đi ngắn nhất giữa các cặp node theo trật tự nhu cầu lưu lượng
giảm dần. Khi đã có cấp của node mạng, một đường đi ngắn nhất sẽ được tạo ra để
đáp ứng nhu cầu lưu lượng tối đa chưa được mang. Quá trình này sẽ tiếp tục cho
tới khi không còn tài nguyên mạng nữa. Nếu tất cả nhu cầu lưu lượng đã được ấn
định, phần còn lại của tài nguyên mạng sẽ được lựa chọn ngẫu nhiên để hình thành
các đường đi ngắn nhất cho tới khi các tài nguyên đã cạn kiệt. Ý tưởng cho thuật
toán này xuất phát từ việc nên định tuyến lưu lượng lớn trên một kết nối đơn hop.
MLDA thiết lập các đường đi ngắn nhất giữa cặp node liền kề và sau đó HTDA
được dùng để ấn định các tài nguyên còn lại tuỳ theo các điều kiện ràng buộc. Ở
đây MLDA là một mở rộng của HTDA trong trường hợp cấp mạng logic là cao
hơn cấp mạng vật lí. TILDA không quan tâm tới nhu cầu lưu lượng mà tập trung
vào việc tối thiểu hoá số lượng bước sóng cần sử dụng. TILDA trước tiên sẽ xây
dựng các đường đi ngắn nhất đơn hop và sau đó là các đường đi hai hop. Thuật
toán này sẽ tiếp tục thiết lập các đường đi ngắn nhất cho tới khi các điều kiện ràng
buộc được đáp ứng.
Một thuật toán khác cũng đã được đề xuất gồm hai thuật toán nhỏ hơn: lược
đồ tối đa hoá lưu lượng đơn hop dựa trên LP (OHTMS) và lược đồ ghép thông qua
loại bỏ tuyến nối (LEMS). OHTMS tương tự như HTDA ở điểm nó cố gắng tối đa
hoá tổng lưu lượng đơn hop trong khi vẫn duy trì khả năng kết nối của mô hình ảo.
- LEMS trước tiên sẽ cố gắng tạo một mô hình ảo hoàn toàn kết nối (lược đồ chia
đôi). Trong đó mỗi phần sẽ chứa tất cả các node trong mô hình vật lí. Khối lượng
của các biên được đặt theo nhu cầu lưu lượng. Khối lượng nhỏ nhất phù hợp cho
việc ghép sẽ được xác định cho các biên này. Các biên đã được ghép sẽ bị xoá khỏi
lược đồ và lưu lượng được đẩy sang mô hình mới cập nhật để thực hiện tính toán
lại. Khối lượng các biên được cập nhật và đối với các biên đã bị xoá sẽ được tìm
kiếm và loại bỏ theo cùng phương thức. Quá trình này sẽ tiếp tục cho tới khi đạt
được điều kiện giới hạn ràng buộc.
Một số thuật toán (dựa trên kinh nghiệm) thiết kế mô hình cây mở rộng
Về mặt lí thuyết, thuật toán hướng ‘tối ưu hoá lưu lượng đơn hop’ đã được
chứng minh là cho hiệu năng tốt hơn. Tồn tại một số thuật toán theo xu hướng này.
Các phương pháp này khác nhau ở sự ấn định tài nguyên dư thừa sau khi kết nối
mô hình ảo ban đầu đã được cung cấp.
Các thuật toán này có một số định nghĩa sau:
Mô hình đường đi ngắn nhất tại mức IP được biểu thị bởi trong
đó N là tập các bộ định tuyến và L là tập các kết nối IP, n N và
l L . Trong N thì ni biểu diễn nhận dạng của bộ định tuyến. Một tuyến
nối IP luôn luôn là song hướng do đó hai đường đi ngắn nhất đơn
hướng trong tầng WDM hình thành một tuyến nối ảo tại tầng IP. Trong
L thì lij là nhận dạng tuyến và lij-c biểu diễn băng thông của tuyến.
Trong các thảo luận dưới đây thì không có sự khác nhau giữa lij và lji,
do đó lij-c = lji-c = max(lij-c, lji-c).
- Véc tơ cấp độ node, D, có n phần tử. Mỗi phần tử, d i , i N , là cấp
1
d i cho bất cứ mô hình IP nào.
của node i. Rõ ràng là l
2i
Ma trận nhu cầu lưu lượng được biểu thị bởi T. T là một ma trận n x n
mà các phần tử của nó, T i, j 0, i, j N , là độ lớn dòng lưu lượng
trong một đơn vị thời gian từ bộ định tuyến i tới bộ định tuyến j.
Thông lượng X là một ma trận n x n mà các phần tử X(i,j) của nó là độ
lớn lưu lượng (được đo bằng bit) được truyền dẫn từ bộ định tuyến i tới
bộ định tuyến j trong một khoảng thời gian nhất định.
Các thuật toán này sử dụng các kí hiệu sau:
Ma trận nhu cầu lưu lượng dư thừa, biểu diễn bởi Tr và là một ma trận
nxn được xác định bởi T r T X .
Một vec tơ dòng F được xây dựng từ ma trận nhu cầu lưu lượng T theo
hai bước:
Lấy đối xứng T để có Ts trong đó phần tử của nó:
T s i, j T s ( j , i ) max T (i, j ), T ( j , i ), i, j N .
Sắp xếp các Ts ở trên theo trật tự giảm dần thành một vec tơ để đạt
được F.
Vec tơ hop dòng, Fh, được xác định bởi: F (i, j ) xH (i, j), i, j N
được sắp xếp theo trật tự giảm dần và H(i,j) là khoảng cách hop từ node
i tới node j.
- Ma trận kết nối, G, là một ma trận n x n. Giá trị của các phần tử G(i,j)
là 1 nếu tồn tại một kết nối giữa bộ định tuyến i và bộ định tuyến j và là
0 nếu ngược lại. Do tính chất đối xứng của mô hình ảo IP nên G là một
ma trận đối xứng.
Dựa trên các kí hiệu trên, các thuật toán trên đặc biệt quan tâm tới các thông
số sau:
Thông lượng bình thường hoá,
X (i , j )
T (i, j )
Khoảng cách hop đã tính trọng số trung bình, h
( H (i, j ) xX (i , j ))
T (i, j )
phụ thuộc vào các điều kiện ràng buộc cấp node
G(i, j ) D( j ), j G(i, j ) D( j ), j
và
i i
Thiết kế thuật toán và các đánh giá hiệu năng sau đó đều nhằm nâng cao độ
lợi thông lượng bình thường hoá (NTG-γ). Giá trị này được xác định như sau:
new
1
old
và độ lợi khoảng cách hop đã tính trọng số trung bình (AWG- ) được xác
định theo biểu thức sau:
hnew
hold
trong đó hnew và new là khoảng cách hop trung bình và thông lượng bình
thường hoá hiện thời còn hold và old là hai giá trị cho mô hình cũ hoặc một mô
hình cố định.
- Các thuật toán dựa trên kinh nghiệm được đề xuất này sẽ thiết lập một mô
hình đường đi ngắn nhất tuỳ theo cấp node mạng vật lí của mỗi node. Mô hình kết
quả sẽ cho phép các đường song song giữa cùng một cặp node. Một kết nối đường
đi ngắn nhất là song hướng. Các thuật toán sẽ bắt đầu với một lược đồ gồm n node
rời nhau tương ứng với n bộ định tuyến.
Các thuật toán này có giai đoạn đầu giống nhau. Giai đoạn này sẽ tạo ra một
cây mở rộng (một cây chung mà không nhất thiết là cây nhị phân) sao cho cung
cấp được tối thiểu hoá kết nối. Max [T(i,j)] được sử dụng như là kết quả của cây
mở rộng. Tính kết nối lược đồ ban đầu là quy định của nhu cầu tải. Đối với mỗi
F(i) tương ứng với Ts(p,q), một kết nối sẽ được gán giữa bộ định tuyến p và bộ
định tuyến q nếu như không tồn tại đường nối nào giữa chúng. Không giống như
các thuật toán ‘đơn hop tối ưu hoá lưu lượng’ truyền thống, các thuật toán được đề
xuất ở đây sẽ không chỉ ấn định các kết nối còn lại một cách giản đơn nhờ sử dụng
F. Thay vì thế, các thuật toán này sẽ đánh giá mô hình nguyên thuỷ nhờ sử dụng
một môi trường dựa trên dòng được mô phỏng. Sự khác nhau của chúng là ở
phương pháp ấn định các kết nối còn lại. Cho mạng gồm có n node, mô hình kết
nối ban đầu bao giờ cũng có n-1 kết nối. Trong một mạng đang hoạt động thì làm
cách nào để ấn định các tài nguyên còn lại là vấn đề rất quan trọng. Ba thuật toán
dựa trên kinh nghiệm sẽ được trình bày dưới đây.
Thuật toán dựa trên kinh nghiệm nhu cầu còn lại (RD)
Thuật toán này gồm có các bước sau:
Bước 1. Xây dựng một cây mở rộng để cung cấp kết nối ban đầu giữa
các node theo vec tơ dòng F tuỳ theo các điều kiện ràng buộc cấp node.
Vì F được sắp xếp theo trật tự nhu cầu giảm dần nên cây kết nối ban
đầu được xây dựng để chứa các dòng lưu lượng có nhu cầu lớn nhất của
- lân cận một hop. Có hai kết nối song song giữa cùng một cặp node. Mỗi
kết nối này sử dụng băng thông tối đa đã được xác định trong ma trận
L.
Bước 2. Sử dụng nhu cầu lưu lượng đối với mô hình chưa hoàn thành.
Hai phương pháp cho ấn định lưu lượng đã được xem xét. Một phương
pháp là định tuyến tuyến nối ngắn nhất (SPF) và phương pháp kia triển
khai SPF và một kĩ thuật lệch dòng chẳng hạn như ECMP (đa đường
đồng chi phí) hay OMP (đa đường tối ưu hoá). Phương pháp ấn định
lưu lượng trong thuật toán sẽ thể hiện chính sách định tuyến trong
mạng đang hoạt động. Ví dụ như, một mạng IP truyền thống hỗ trợ SPF
(ví dụ như tính toán định tuyến trong OSPF) một chính sách định tuyến
tối ưu sẽ đòi hỏi cân bằng tải giữa các đường kế tiếp, ví dụ như OSPF-
OMP.
Bước 3. Vì có nhiều giao diện chưa được ấn định nên có khả năng là
không phải tất cả các nhu cầu đều được hỗ trợ bởi mô hình chưa hoàn
thành. Do đó, sẽ tạo ra một vec tơ dòng mới sử dụng ma trận nhu cầu
dư thừa. Vec tơ dòng mới này được lưu trữ theo trật tự giảm dần của
nhu cầu dư thừa.
Bước 4. Tìm kiếm trong vec tơ dòng mới này để tìm ra một dòng mà
một kết nối mới có thể được gán giữa các đầu cuối của nó. Chèn kết nối
mới này vào mô hình và thiết lập kết nối với băng thông tối đa của nó
theo F. Sau đó quay trở lại bước 2. Thuật toán sẽ dừng lại nếu không
thể tìm ra một kết nối mới nào nữa.
Bước 5. Nếu như số lượng các giao diện rỗi là không nhỏ hơn 2 thì ứng
dụng thuật toán kinh nghiệm hội tụ được trình bày dưới đây.
- Vì sự đánh giá các mô hình trung gian dựa trên nhu cầu còn lại nên thuật toá n
này được đặt tên tương ứng là RD. Một biến thể của trạng thái này là xem xét tích
của đếm hop và nhu cầu còn lại. Theo đó, thuật toán tương ứng được gọi là RDHP.
RDHP có xu hướng ưa thích các dòng với các giá trị cao cho tích giữa nhu cầu còn
lại và số đếm hop.
Thuật toán dựa trên kinh nghiệm tích đếm hop và nhu cầu còn lại
(RDHP)
Có bốn bước trong thuật toán này:
Bước 1. Xây dựng một cây mở rộng để cung cấp kết nối ban đầu giữa
các node theo vec tơ dòng F. Bước này giống bước 1 trong RD.
Bước 2. Ứng dụng nhu cầu lưu lượng vào mô hình chưa hoàn thành.
Bước này cũng giống với bước 2 trong RD.
Bước 3. Tính toán khoảng cách hop giữa tất cả các cặp node dựa trên
mô hình chưa hoàn thành.
Bước 4. Tạo ra một vec tơ dòng mới nhờ sử dụng ma trận nhu cầu còn
lại trong đó mỗi phần tử của nó có trọng số bằng với giá trị đếm hop
của nó. Vec tơ dòng này được lưu trữ theo trật tự giảm dần của tích
giữa nhu cầu còn lại và giá trị đếm hop. Tìm kiếm giữa các vec tơ hop-
dòng này để tìm ra một dòng mà một kết nối mới có thể được gán giữa
các đầu cuối của nó. Chèn kết nối mới này vào mô hình và thiết lập kết
nối mới này với giá trị băng thông tối đa của nó theo F. Sau đó quay trở
lại bước 2. Thuật toán sẽ dừng lại khi không tìm thấy kết nối mới nào
nữa. Nếu số lượng các giao diện rỗi không nhỏ hơn 2 thì sử dụng thuật
toán kinh nghiệm hội tụ được trình bày dưới đây.
- Một biến thể khác của trạng thái này là chỉ đơn giản xem xét tích giữa nhu
cầu và số đếm hop. Đây rõ ràng là kết quả của mục tiêu tối ưu hoá toàn cục, nghĩa
là tối thiểu hoá trọng số số đếm hop của mạng. Do vậy, nó đ ược gọi là DHP. DHP
giảm được nhu cầu tính toán xảy ra sau khi mỗi kết nối được bổ sung.
Thuật toán dựa trên kinh nghiệm tích nhu cầu và số đếm hop (DHP)
Thuật toán này gồm có các bước sau:
Bước 1. Xây dựng một cây mở rộng để cung cấp kết nối ban đầu giữa
các node theo vec tơ dòng F. Bước này giống bước 1 trong RD.
Bước 2. Tính toán/tính toán lại khoảng cách hop giữa tất cả các cặp
node dựa trên mô hình chưa hoàn thành.
Bước 3. Tạo một vec tơ dòng mới theo trật tự giảm dần nhờ sử dụng
ma trận nhu cầu trong đó các phần tử của nó có trọng số bằng với giá trị
đếm hop của nó.
Bước 4. Tìm kiếm trong vec tơ hop dòng để tìm ra một dòng mà một
kết nối mới có thể được gán giữa các đầu cuối của nó. Chèn kết nối mới
này vào mô hình và thiết lập kết nối mới này với giá trị băng thông tối
đa của nó theo F. Sau đó quay trở lại bước 2. Thuật toán sẽ dừng lại khi
không tìm thấy kết nối mới nào nữa.
Bước 5. Nếu số lượng các giao diện rỗi không nhỏ hơn 2 thì sử dụng
thuật toán kinh nghiệm hội tụ được trình bày dưới đây.
Các thuật toán được trình bày ở trên có thể dừng lại khi tất cả các giao diện
đều sẵn sàng. Một ví dụ của tình huống như vậy là khi tất cả các giao diện chưa
- được ấn định cùng thuộc về một node. Điều này có thể xảy ra như là kết quả của sự
nhầm lẫn giữa cấp node và nhu cầu lưu lượng. Vì các thuật toán cố gắng cung cấp
cho các nhu cầu lớn các kết nối trực tiếp nên node có lưu lượng thấp hơn có thể kết
thúc với nhiều giao diện rỗi nhưng phần còn lại của mạng là hoàn toàn bị chiếm.
Một thuật toán cho hội tụ đã được cung cấp. Nó bao gồm các bước sau:
Bước 1. Phát hiện node với nhiều giao diện IP mở (lớn hơn hoặc bằng
2).
Bước 2. Ứng dụng nhu cầu lưu lượng cho mô hình hoàn thành một
phần.
Bước 3. Sắp xếp tất cả các kết nối dựa trên mức tận dụng theo trật tự
giảm dần. Mức tận dụng kết nối được thiết lập cao hơn mức tận dụng
tuyến nối của hai tuyến nối đã tạo nên kết nối.
Bước 4. Chọn kết nối tải nhỏ nhất mà không phải là trường hợp node
có các giao diện mở từ trong danh sách sắp xếp. Phá vỡ kết nối này và
tạo ra hai kết nối mới giữa hai giao diện mở đang có. Hai giao diện vừa
được mở mới này có được là nhờ việc phá vỡ kết nối có tải nhỏ nhất.
Bước 5. Trở lại bước 2 nếu như số lượng các giao diện mở vẫn còn lớn
hơn hoặc bằng 2.
Trong một mạng đường trục IP, mỗi node thường có ít nhất vài giao diện.
Điều này dẫn đến tổng số lượng kết nối, l, có thể cung cấp trong mạng là lớn hơn
nhiều so với (n-1) kết nối trong lược đồ cây mở rộng ban đầu. Điều này có nghĩa là
việc thiết lập (l-n+1) kết nối trong thực tế là một thủ tục rất quan trọng trong khi
thiết kế mô hình.
nguon tai.lieu . vn