Widest Shortest Path GVHD: Hoàng Trọng Minh
chính vì thế mà vấn đề tối ưu hoá định tuyến luôn được đặt ra trong thời gian triển
khai mạng, nhất là sự đối lập về quan điểm người sử dụng dịch vụ và nhà khai
thác dịch vụ mạng
II. Giải thuật định tuyến
Giải thuật định tuyến (routing algorithm) là giải thuật tìm đường đi cho các gói
từ một máy nguồn đến một máy đích, trong hầu hết các mạng thì các gói sẽ cần
đến nhiều bước nhảy (nghĩa là phải chuyển qua nhiều bộ định tuyến) để hoàn tất
cuộc hành trình. Giải thuật định tuyến có nhiệm vụ quyết định đường dây ra nào
mà một gói đến có thể được truyền trên nó. Có hai quá trình xảy ra trong một bộ
định tuyến, đó là một quá trình quản lí mỗi một gói khi gói này đến, tìm kiếm
đường ra cho gói này ở trong các bảng định tuyến, quá trình này gọi là quá trình
truyền tiếp. Quá trình còn lại có nhiệm vụ cập nhật và điền vào các bảng định
tuyến, đó là nơi mà giải thuật định tuyến bắt đầu có hiệu lực.
2.1. Yêu cầu của giải thuật định tuyến
Các thuộc tính cần phải có trong giải thuật định tuyến là:
. Chính xác (exactitude)
. Đơn giản (simple)
. Có khả năng thay đổi cấu hình và đường vận chuyển để không phải khởi
động lại mạng khi có một nút hỏng hoặc phải ngừng hoạt động của các máy
ở trạm
. Ổn định vì có những thuật toán không bao giờ hội tụ về trạng thái cân đối
ổn định
. Tối ưu
Các giải thuật định tuyến có thể được nhóm thành hai loại chính: không thích
nghi và thích nghi
Các quyết định của giải thuật định tuyến không thích nghi không phụ thuộc vào
các phép đo hoặc ước lượng của lưu lượng hiện hành và cấu trúc liên kết (topo)
mạng. Thay vào đó, việc lựa chọn tuyến sử dụng để đi từ nguồn đến đích được
tính toán trước và được tải xuống các bộ định tuyến khi mạng được khởi động
Giải thuật thích nghi thay đổi các quyết định định tuyến để phản ánh sự thay đổi
trong cấu trúc liên kết mạng và thường là cả lưu lượng. Các giải thuật thích nghi
khác nhau ở nơi nào chúng lấy thông tin (chẳng hạn như có tính cục bộ, từ các bộ
định tuyến gần nhất hoặc từ tất cả các bộ định tuyến ), khi nào các giải thuật này
Sinh Viên : Nguyễn Thị Nghĩa
5
Widest Shortest Path GVHD: Hoàng Trọng Minh
thay đổi các tuyến (chẳng hạn như mỗi một ΔT giây, khi tải thay đổi hay cấu trúc
liên kết mạng thay đổi ), và số đo nào được sử dụng cho sự tối ưu (chẳng hạn như
khoảng cách, số bước nhảy hay thời gian chuyển tiếp được ước lượng) và ở đoạn
tiếp giải thuật định tuyến đường đi ngắn nhất và rộng nhất (WSP).
2.2. Giải thuật tìm đường đi ngắn nhất và rộng nhất ( WSP )
Thuật toán tìm đường đi ngắn nhất và rộng nhất (WSP)[1] là thuật toán được
nâng cấp từ thuật toán bước nhảy tối thiểu,WSP cố gắng cân bằng tải trọng của
lưu lượng mạng. Trên thực tế thì WSP chọn một đường dẫn khả thi nhất cùng với
số bước nhảy bé nhất và nếu có nhiều hơn một đường dẫn khả thi cùng với số
bước nhảy như vậy thì một đường dẫn sẽ được chọn ra cùng với độ dư băng thông
lớn nhất, như vậy sẽ làm giảm liên kết tải trọng nặng. Mục tiêu của thuật toán
WSP là để chọn một con đường ngắn nhất mà là một con đường có tính khả thi
theo sự rằng buộc về băng thông của lưu lượng. Số đo chính trong thuật toán
WSP là số bước nhảy và số đo thứ 2 là băng thông sẵn có (còn dư), trong giai
đoạn một tồn tại tất cả các con đường ngắn nhất giữa mỗi nguồn và tất cả các đích
trong mạng là một sự tính toán. Trong giai đoạn 2 băng thông được sử dụng. WSP
có thể tính toán bằng phiên bản sửa đổi của Bellman-Ford hoặc thuật toán
Dijkstra. Sự mở rộng để thuật toán Dijkstra thay thế cho sự tính toán của WSP.
Mục đích chính của WSP là để giảm tải chi phí cho mạng. Từ đó sự duy trì tài
nguyên mạng là đặc biệt quan trọng khi mạng bị tắc nghẽn, kiểu thuật toán này
mang lại hiệu quả cao khi mạng có tải trọng cao. WSP thực thi tốt bởi vì tài
nguyên được bảo vệ đồng thời bằng cách chọn con đường ngắn và cân băng tải
trọng bằng cách chọn con đường rộng giữa các con đường có độ dài như nhau
Trong phần sau chúng ta sẽ đi sâu vào tìm hiểu về QoS (quality of service) để biết
được giải thuật WSP hỗ trợ cho định tuyến QoS như thế nào
III. Giới thiệu về QoS (quality of service)
3.1. Định nghĩa về QoS (chất lượng dịch vụ)
Chất lượng dịch vụ QoS [2] là khả năng của mạng để cung cấp dịch vụ tốt cho
lưu lượng mạng xác định qua nhiều công nghệ lớp dưới như Frame-Relay, ATM,
IP và các mạng định tuyến… nói cách khác nó là đặc tính của mạng cho phép
phân biệt giữa các lớp lưu lượng khác nhau và sử lý chúng một cách khác nhau
Sinh Viên : Nguyễn Thị Nghĩa
6
Widest Shortest Path GVHD: Hoàng Trọng Minh
Một vài ứng dụng tổng quát và độ chính xác của các yếu cầu được liệt kê trong
bảng sau.
Bảng 3.1 Các yêu cầu về chất lượng dich vụ
3.2. Mô hình trạng thái QoS
Một mô hình trạng thái mạng QoS thường được biểu diễn dưới dạng một đồ thị
G(V,E). Trong đó V thể hiện cho các nút và E là các liên kết. Lưu lượng vào mạng
qua nút v
i
và ra qua nút v
j
. Mỗi liên kết (i,j) có 2 đặc tính : C
i,j
là dung lượng liên
kết và f
i,j
là lưu lượng thực tế. Gọi R
i,j
= (C
i,j
– f
i,j
) là băng thông dư. Một kết nối có
yêu cầu băng thông là d
k
thì một liên kết được gọi là khả dụng khi R
i,j
≥ d
k
. Một
kết nối mới có thể được chấp thuận nếu ít nhất tồn tại một đường dẫn khả dụng
giữa v
i
và v
j
.
Sinh Viên : Nguyễn Thị Nghĩa
Hội nghị truyền hình
Âm nhạc theo yêu cầu
Cao
Thấp
Thấp
Thấp
Ứng dụng
Độ tin cậy
Thời gian trì hoãn
Trượt Băng thông
Thư điện tử
Truyền tập tin
Điện thoại
Đăng nhập từ xa
Truy cập Web
Cao
Cao
Cao
Cao
Cao
Cao
Cao
Cao
Cao
Thấp
Thấp
Thấp
Thấp
Thấp
Thấp
Thấp
Thấp
Thấp
Trung bình
Trung bình
Trung bình
Trung bình
Trung bìnhTrung bình
7
i
k m
n
lj
C
ij
F
ij
V0
V1
C
jl
F
jl
C
ln
F
ln
C
mn
F
mn
C
km
F
kmm
C
jk
F
jk
C
kl
F
kl
C
jm
F
jm
v
n
Widest Shortest Path GVHD: Hoàng Trọng Minh
Hình 3.2 Mô hình trạng thái mạng QoS
Một đường đi (path) trên đồ thị là một dãy tuần tự các đỉnh v
1,
v
2
v
n,
sao cho
(v
i
,v
i+1
) là một cung của đồ thị (i=1…n-1). Đường đi này là đường đi từ đỉnh v
1
đến
đỉnh v
n
đi qua các đỉnh v
1,
v
2
v
n-1
, đỉnh v
1
được gọi là đỉnh đầu của đường đi, đỉnh
v
n
được gọi là đỉnh cối của đường đi, độ dài của đường đi là n-1(bằng số cạnh trên
đường đi ). Một liên kết a thuộc E từ nốt v
i
đến v
i+1
hay gọi là liên kết (vi,v
i+1
). Mỗi
một liên kết a thuộc E có tải trọng wi(a). w(v
i
,v
i+1
) là tải trọng tương ứng với liên
kết ( vi,v
i+1
) trên đường dẫn P = ( v
1,
v
2
v
n-1
) và W(P) là tải trọng trên toàn bộ
đường truyền
3.3. Mục tiêu định tuyến QoS
Vai trò của định tuyến là tính toán đường dẫn thích hợp cho các kiểu lưu lượng
khác nhau, khi sự tận dụng của tài nguyên mạng lớn, việc đáp ứng mục tiêu phụ
thuộc vào sự phát triển của thuật toán để tìm đường dẫn dựa vào sự tính toán trạng
thái của mạng và lưu lượng yêu cầu, cụ thể là, cần tính đến độ trễ, độ trượt, tỉ lệ
mất mát và băng thông còn dư.
Mục tiêu của định tuyến QoS là để chọn đường dẫn phù hợp theo yêu cầu thông
lượng căn cứ trên thông tin về tất cả các trạng thái của mạng . Sự tận dụng tài
nguyên mạng cũng là mục tiêu quan trọng của định tuyến QoS. Kế hoạch định
tuyến QoS cần phải đưa ra giải pháp cho kĩ thuật phân phối số đo và thuật toán
chọn đường dẫn.
Một số đề xuất phối hợp định tuyến QoS thường phụ thuộc vào sự trao đổi
giữa các thông tin trạng thái QoS các bộ định tuyến, và xử lý phần đầu tại trung
tâm các bộ định tuyến. Để đơn giản hóa việc trao đổi thông tin trong mạng, chúng
ta tập trung phối hợp định tuyến khoanh vùng tại biên (edge) các bộ định tuyến và
như vậy để giải quyết đường đi chỉ cần sử dụng thông tin cục bộ (local).
Định tuyến căn cứ trên dung lượng ảo (vcr virtual capacity based routing) là sự
phối hợp trên lí thuyết căn cứ trên khái niệm dung lượng ảo của một bộ định
tuyến. Chúng ta tập trung phối hợp định tuyến QoS khoanh vùng tại biên (edge)
các bộ định tuyến để giải quyết đường đi chỉ sử dụng thông tin cục bộ ”local” và
như vậy thì giảm tải phần đầu tại trung các tâm bộ định tuyến
3.4. các tham số QoS.
Sinh Viên : Nguyễn Thị Nghĩa
8
Widest Shortest Path GVHD: Hoàng Trọng Minh
Các tham số rằng buộc về QoS của kết nối thường được đánh giá qua mức độ
đảm bảo băng thông tối thiểu, độ trễ/trượt và tỉ lệ mất thông tin. Mục tiêu cơ bản
của kỹ thuật định tuyến QoS là tìm ra một đường có khả năng đảm bảo các điều
kiện rằng buộc của đấu nối và thậm chí chỉ để loại bỏ một số đấu nối khác.
Hình 3.4 Độ trễ và mất mát gói tin trong mạng
+ Việc quản lý băng thông hiệu quả để chuyển các gói qua một mạng gói dựa
trên các thông số sau
- Latency –Trễ khi chuyển một gói tin qua mạng.
- Jitter – Trượt.
- Loss – Phần trăm mất gói.
- roughput –Thông lượng của mạng.
- vailability - network uptime-tính sẵn sàng của mạng.
+ Các tham số sau đây là cơ sở để định lượng bất kỳ một dịch vụ nào:
- one-way delay -độ trễ một chiều.
- one-way packet delay variation-mức độ thay đổi độ trễ gói tin theo một
chiều.
- capacity- dung lượng.
Sinh Viên : Nguyễn Thị Nghĩa
9
Widest Shortest Path GVHD: Hoàng Trọng Minh
- packet loss- độ mất mát gói tin.
Ngoài danh sách này,có một vài yêu cầu cơ bản cho hoạt động mạng mà ảnh
hưởng lớn đến toàn bộ chất lượng của bất kỳ dịch vụ nào.
- Tỉ số lỗi bít.
- Sự ổn định của lớp vật lý và liên kết số liệu.
- Sự ổn định định tuyến.
- Hiệu năng phần cứng toàn mạng.
- Kiểm tra và thời gian cần để giải quyết sự cố .
Bảng 2.2: Phạm vi các tham số
3.5 Các giao thức và tiêu chuẩn liên quan đến QoS
Trong phần này sẽ đề cập và xem xét hai mô hình hỗ trợ QoS trong mạng IP
là : Integrated Services (các dịch vụ tích hợp) và Differentiated Services (các dịch
Sinh Viên : Nguyễn Thị Nghĩa
lớp QoS
1
2
3
4
5
0
ứng dụng
(ví dụ)
kĩ thuật nút
phương pháp kĩ
thuạt mạng
thời gian thực,
Jitter sensitive,
tương tác
cao(VoIP,VTC)
thời gian thực, Jitter
sensitive, tương tác
(VoIP,VTC)
Truyền vận dữ
liệu,tương tác
cao(signaling)
Truyền vận dữ
liệu,tương tác
chỉ tổn thất nhỏ(các
vận chuyển ngắn,
kích thước dữ liệu)
ứng dụng truyền thống
của các mạng default
IP
Tách rời hàng đợi cùng với
độ ưu tiên, nhóm lưu
lượng
tách rời hàng đợi
độ ưu tiên giảm
hàng đợi dài,
độ ưu tiên giảm
Tách rời hàng đợi
(ưu tiên mức
thấp nhất)
rằng buộc định
tuyến và
khoảng cách
rằng buộc định tuyến
ở mức độ nhỏ hơn và
khoảng cách
rằng buộc định
tuyến và
khoảng cách
rằng buộc định tuyến
ở mức độ nhỏ hơn và
khoảng cách
bất cứ bộ định
tuyến/đường dẫn
bất cứ bộ định
tuyến/đường dẫn
10
Widest Shortest Path GVHD: Hoàng Trọng Minh
vụ sai biệt ). Cả hai mô hình đều hỗ trợ cho việc điều khiển mạng và mang lại khả
năng phát triển mạng tốt hơn
Kĩ thuật Intserv được hiểu một cách tổng quan như sau
- Mỗi node mạng (router) được phân chia thành 2 phần: Xử lý cơ bản và
chuyển tiếp lưu lượng.
- Xử lý cơ bản đảm nhận các chức năng như: định tuyến, thiết lập và duy trì
tài nguyên mạng và điều khiển quản lý.
- Xử lý trong chuyển tiếp lưu lượng: dựa trên thông tin trong cơ sở dữ liệu
để phân loại lưu lượng và đưa lưu lượng vào hàng đợi.
Kĩ thuật Intserv (dịch vụ tích hợp), sử dụng giao thức RSVP- (giao thức dự trữ
trước tài nguyên-Source Reservation Protocol) để dành trước tài nguyên trước khi
truyền dữ liệu
Hình 3.5. RSVP
RSVP cho phép nhiều bộ định tuyến truyền thông tin đến nhiều bộ định
tuyến cho phép các bộ định tuyến tối ưu hóa trong việc sử dụng băng thông đồng
thời với việc loại bỏ nghẽn mạch. Để dành trước tài nguyên phía gửi sử dụng
RSVP để gửi một bản tin PATH tới phía nhận để xác định các thuộc tính của lưu
lượng sẽ gửi. Mỗi node trung gian sẽ chuyển tiếp bộ bản tin PATH tới các node kế
tiếp. Khi nhận được bản tin PATH bên nhận sẽ gửi bản tin RESV để yêu cầu tài
nguyên cho luồng. Các node trung gian trên đường đi có thể chấp nhận hay từ chối
các yêu cầu chứa trong bản tin RESV, nếu yêu cầu bị từ chối, bộ định tuyến sẽ gửi
bản tin báo lỗi cho phía nhận, quá trình báo hiệu kết thúc. Nếu yêu cầu được chấp
nhận, tài nguyên được dành riêng cho luồng và các trạng thái liên quan của luồng
sẽ được cài đặt vào bộ định tuyến. RSVP khó khăn trong việc thực hiện vì việc
Sinh Viên : Nguyễn Thị Nghĩa
R1
Path
R3
R2
Path
Path Path Rx
Resv
Resv Resv
Resv
S
11
Widest Shortest Path GVHD: Hoàng Trọng Minh
chuyển tiếp các gói dựa trên trạng thái của gói tại mỗi node, các quyết định này
yêu cầu các gói RSVP phải mang một số thông tin “tóm tắt” để định phiên làm
việc của chúng. Các bộ định tuyến trung gian phải có một bảng định tuyến động
chứa phương pháp sử lí các thông tin “tóm tắt” đó và thông tin về việc “dành trước
tài nguyên”. Khi một bộ định tuyến nhận được một gói thuộc phiên làm việc
RSVP nó phải tham chiếu vào bảng để biết cách phải xử lí gói như thế nào.
Trong mô hình tích hợp dịch vụ sử dụng giao thức RSVP có thể đảm bảo
QoS từ đầu cuối đến đầu cuối trên cơ sở mỗi luồng thông qua báo hiệu QoS trên
từng chặng. Các bộ định tuyến dọc theo đường truyền phải duy trì trạng thái cho
mỗi luồng thông tin. Vì vậy tối ưu về sử dụng tài nguyên mạng, nhưng kéo theo đó
là gánh nặng xử lý và tăng kích cỡ mạng
Trong mô hình dịch vụ sai biệt chỉ đảm bảo QoS trên từng chặng thông qua việc
ấn định tài nguyên phần cứng. Gánh nặng xử lý của các bộ định tuyến nhẹ hơn và
đơn giản hơn, nhưng không đảm bảo về QoS từ đầu cuối đến đầu cuối
Hình mô hình tích hợp dịch vụ sử dụng RSVP
VI. Các vấn đề về số đo
4.1 Số đo ( Metric)
Thuật toán chọn đường có mức độ phức tạp được quyết định bởi nhiều yếu tố
khác nhau. Thuật toán chọn đường chọn các đường dẫn khả thi trong một tập
Sinh Viên : Nguyễn Thị Nghĩa
12
Pat
h
Pat
h
Resv
Resv
Bảng định tuyến
Dữ liệu
Điều khiển
path
vào
Hàng đợi
ra
Tổ chức điều
khiển
Bộ phận
đk
Tác nhân
định tuyến
Phân
loại
Lập lịch trình
Thiết lập
dành riêng
Điều khiển cơ sở
dữ liệu
Tác
nhân đk
RSVP
Widest Shortest Path GVHD: Hoàng Trọng Minh
đường dẫn. Mặc dù vậy, việc tính toán được quyết định trên nguyên tắc của kết
cấu số đo
Giá trị của số đo dọc theo đường dẫn, căn cứ trên giá trị của mỗi bước nhảy
được quyết định trên bản chất của số đo. Việc thêm vào thành phần số đo có nghĩa
là giá trị của số đo trên khắp đường dẫn là sự cộng gộp giá trị của mỗi bước nhảy (
độ trễ và số bước nhảy tương đương với các số đo cộng vào). Với các số đo được
nhân lên thì giá trị của số đo trên con đường là tích số của các giá trị đó trong mỗi
bước nhảy (độ tin cậy). Giá trị của số đo lõm (concave) trên đường truyền phù hợp
để tuân theo giá trị trong tất cả các bước nhảy của đường truyền ấy (băng thông là
ví dụ phổ biến của số đo lõm )
Các số đo sử dụng phổ biến trên định tuyến QoS và rằng buộc định tuyến căn bản
được tách ra thành 3 loại
Được gọi là các quy tắc cấu tạo hành phần các số đo
- Tính cộng thêm nếu
W(P) = w( u1, u2 ) + w ( u3 , u4 ) +…+ w(ul-1,ul)
- Tính nhân lên nếu
W(P) = w( u1, u2 )
.
w ( u3 , u4 )
.
…
.
w(ul-1,ul)
- Tính lõm nếu
W(P) = min( w( u1, u2 ), w ( u3 , u4 ) ,…, w(ul-1,ul) )
W(P) là tải trọng trên đường truyền, w(ui , uj) là tải trọng của một liên kết trên
đường truyền
4.2. Phân phối số đo ( Metrics Distribution)
Trạng thái của mạng có thể miếu tả bằng một tập hơp số đo, bao gồm băng
thông sẵn có, độ trễ, độ trượt, và mức độ tắc nghẽn. Thông tin về tất cả trạng thái
của mạng cần được phân phối, và giữ lại cập nhật, ở tất cả hoặc một vài bộ định
tuyến trong mạng. Sự phân phối cần được thực hiện thường xuyên hơn trong bộ
định tuyến để cập nhật trạng thái động của mạng. Nhưng nếu thường xuyên cập
nhật thông tin thì nó sẽ gây ra tiêu thụ băng thông nhiều, có thể xảy ra nguy hiểm
cho mạng.
4.3 Thứ tự số đo (Metric Ordering )
Thứ tự số đo phụ thuộc sự xác định của số đo mà có độ ưu tiên cao và có sự
tính toán tương đối tốt nhất theo số đo này. Trong thuật toán WSP thì số đo được
ưu tiên tính toán đầu tiên là số bước nhảy, số đo thứ hai căn cứ trên băng thông
Sinh Viên : Nguyễn Thị Nghĩa
13
Widest Shortest Path GVHD: Hoàng Trọng Minh
Tuật toán WSP chọn từ các con đường ngắn nhất cùng với số bước nhảy như
nhau, cùng với độ dư băng thông lớn. Thuật toán WSP sử dụng thuật toán
bellman-ford để tính toán đường dẫn rộng nhất ngắn nhất. Thuật toán Dijkstra
cũng có thể được sử dụng để tính toán đường ngắn nhất và rộng nhất. Trong
trường hợp này được sử dụng 2 hàm, đầu tiên là liên quan đến số bước nhảy, và
thứ 2 là độ dư băng thông lớn nhất. Tại mỗi lần lặp thuật toán tính toán chọn một
node cùng với số bước nhảy nhỏ. Nếu có nhiều hơn một node có số bước nhảy
như vậy thì nó sẽ chọn một node cùng với độ dư băng thông lớn nhất.
Thuật toán WSP có mục đích định ra giới hạn sử dụng tài nguyên, chúng cũng
cho phép đi đến cân bằng tải trọng. Từ đó sự duy trì tài nguyên là quan trọng nhất
khi mạng bị tắc nghẽn, và kiểu thuật toán này góp phần để duy trì tài nguyên, nó
cho thấy kết quả tốt khi tải trọng cao. Thuật toán WSP cũng cho thấy cách giao
tiếp tốt khi giải quyết định tuyến dựa trên thông tin của trạng thái mạng.
Độ rộng băng thông được dùng như một số đo cho định tuyến QoS, một hoặc
kết hợp cùng với các số đo khác, ví dụ như độ trễ hoặc số các bước nhảy.
Hình 4.3 Thông lượng, băng thông sẵn có
V. Kĩ thuật lưu lượng
Sinh Viên : Nguyễn Thị Nghĩa
14
Không có nhận xét nào:
Đăng nhận xét