MỤC LỤC
MỤC LỤC ......................................................................................................................... 1
DANH SÁCH CÁC KÝ HIỆU, CHỮ VIẾT TẮT ......................................................... 4
DANH MỤC CÁC HÌNH ................................................................................................. 5
MỞ ĐẦU ............................................................................................................................ 7
CHƢƠNG 1: TỔNG QUAN ..................................................................................... 8

1.1. Sự tương đồng mạng .............................................................................. 9
1.2. Truyền thông, mạng máy tính và nhà cung cấp mạng ........................... 16
1.3. Khái niệm về lưu lượng và nhu cầu lưu lượng truy cập......................... 20
1.3.1 Lưu lượng trong Internet .......................................................... 21
1.3.2. Lưu lượng trong mạng điện thoại ............................................ 23
1.4. Khái niệm về định tuyến và dòng .......................................................... 23
CHƢƠNG 2: CÁC BÀI TOÁN ĐỊNH VỊ VÀ CẤU TRÚC TOPO ............................. 26

2.1 Bài toán định vị các nút mạng liên kết .................................................... 26
2.2. Định vị nút liên kết chung và bài toán kết nối đường dẫn ..................... 32
2.2.1 Thiết Kế Mạng : Cấp Độ 1........................................................ 33
2.2.2 Xây dựng mô hình hai mức....................................................... 39
CHƢƠNG 3: GIẢI THUẬT DI TRUYỀN ..................................................................... 49

3.1. Giới thiệu chung ..................................................................................... 49
3.2. Nhiễm sắc thể ......................................................................................... 50
3.3. Không gian tìm kiếm............................................................................. 51
3.4. Quần thể ................................................................................................. 52
3.5. Hàm thích nghi ....................................................................................... 52
3.6. Các thông số khác của giải thuật di truyền ............................................ 52
3.7. Giải thuật di truyền đơn giản ................................................................. 53
3.8. Các chiến lược lựa chọn ......................................................................... 54

1

3.8.1. Lựa chọn theo cơ chế quay bánh xe Roulette .......................... 54
3.8.2. Lựa chọn xếp hạng ................................................................... 55
3.8.3. Lựa chọn theo vòng đấu ........................................................... 55
3.8.4. Cơ chế "Elitism" ...................................................................... 56
3.9. Mã hóa.................................................................................................... 56
3.9.1. Mã hoá nhị phân....................................................................... 56
3.9.2. Mã hoá hoán vị......................................................................... 57
3.9.3. Mã hoá theo giá trị ................................................................... 57
3.9.4. Mã hoá theo cây ....................................................................... 58
3.10. Lai ghép và đột biến ............................................................................. 59
3.10.1. Lai ghép và đột biến đối với mã hoá nhị phân....................... 59
3.10.2. Lai ghép và đột biến đối với mã hoá hoán vị ......................... 60
3.10.3. Mã hoá theo giá trị ................................................................. 61
3.10.4. Mã hoá theo cây ..................................................................... 61
CHƢƠNG 4: GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN ĐỊNH VỊ CÁC NÚT
MẠNG LIÊN KẾT............................................................................................................ 63

4.1. Phát biểu bài toán .................................................................................. 63
4.2. Mã hóa.................................................................................................... 63
4.3. Giải mã của thuật toán di truyền ............................................................ 64
4.3.1. Thuật toán di truyền GA1 ........................................................ 65
4.3.1.1. Khởi tạo quần thể ban đầu ......................................... 65
4.3.1.2. Toán tử lai ghép ......................................................... 66
4.3.1.3. Toán tử đột biến ......................................................... 68
4.3.2. Thuật toán di truyền GA2 ........................................................ 69
4.3.2.1. Khởi tạo quần thể ban đầu ......................................... 69
4.3.2.2. Toán tử lai ghép ......................................................... 69
4.3.2.3. Toán tử đột biến ......................................................... 69

4.3.2.4. Thủ tục cải thiện nghiệm Imp_Sol() .......................... 69

2


4.3.3. Thuật toán di truyền GA3 ........................................................ 70
4.3.4. Thuật toán di truyền GA4 ........................................................ 71
4.3.4.1. Thủ tục Init_Pop ........................................................ 72
4.3.4.2. Thủ tục Imp_Sol ........................................................ 75
4.3.4.3. Thủ tục Cros_sol và Mut_Sol .................................... 75
4.3.5. Ví dụ tính toán theo các thuật toán .......................................... 76
4.3.5.1. Dữ liệu của bài toán ................................................... 76
4.3.5.2. Ví dụ tính toán theo thuật toán GA1 .......................... 77
4.3.5.3. Ví dụ tính toán theo thuật toán GA2 .......................... 86
KẾT LUẬN ............................................................................................................... 91
TÀI LIỆU THAM KHẢO ......................................................................................... 92

3


DANH SÁCH CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Chữ viết tắt

Viết đầy đủ

GA

Genetic Algorithm

NST


Nhiễm Sắc Thể

Ý nghĩa
Giải thuật di truyền

4


DANH MỤC CÁC HÌNH
Hình 1.1.a. Mạng điện thoại ..................................................................................... 9
Hình 1.1.b. Mạng đường truyền Web Internet ......................................................... 9
Hình 1.2.a. Mạng điện thoại nhiều người sử dụng................................................... 11
Hình 1.2b. Mạng Internet nhiều người sử dụng ....................................................... 11
Hình 1.3. Mạng đường hàng không ......................................................................... 15
Hình 1.4. Hệ thống các mạng ................................................................................... 17
Hình 1.5. Miền quản trị trong bài toán thiết kế mạng .............................................. 17
Hình 1.6. Ba miền quản trị sử dụng cùng một dịch vụ đường truyền ...................... 19
Hình 1.7. Miền quản trị sử dụng đa đường truyền ................................................... 20
Hình 1.8. Mạng đa dịch vụ sử dụng chung đường truyền........................................ 20
Hình 2.1. Minh họa thiết kế vị trí nút liên kết .......................................................... 32
Hình 2.2. Kết hợp thiết kế liên kết nối mạng trung tâm........................................... 34
Hình 2.3. Thiết kế ( Chi phí phụ thuộc vào khoảng cách - Distance-Based Cost) (A)
D/ONLLC/A: N =15, P =3; (B) D/ONLLC/A: N=15, P= 4; (C) D/ONLLC/A:
N=15, P=5 ................................................................................................................ 44
Hình 2.4. Thiết kế ( Chi phí phụ thuộc vào khoảng cách - Distance-Based Cost) (A)
D/ONLLC/A: N =25, P =5; (B) D/ONLLC/A: N=25, P= 6; (C) D/ONLLC/A:
N=25, P=7 ................................................................................................................ 45
Hình 2.5. Thiết kế sử dụng khoảng cách hình thoi lệch (Design Using Skewed
Distance) - (A) D/ONLLC/A: N =15, P =3; (B) D/ONLLC/A:N=15, P= 4; (C)

D/ONLLC/A: N=15, P = 5 ....................................................................................... 46
Hình 2.6. Thiết kế sử dụng khoảng cách hình thoi lệch ( Design Using Skewed
Distance) - (A) D/ONLLC/A: N =25, P =5; (B) D/ONLLC/A : N=25, P= 6; (c)
D/ONLLC/A : N = 25, P = 7 .................................................................................... 46
Hình 2.7. Thiết kế dựa trên khoảng cách (Design with Distance-Based) (A)
D/ONLLC/B: N =30, P =5; (B) D/ONLLC/B: N=30, P= 6; (C) D/ONLLC/B :
N=30, P=7 ................................................................................................................ 47

5


Hình 2.8. Thiết kế dựa trên khoảng cách hình thoi lệch ( Design with SkewedDistance) - (A) D/ONLLC/B: N =30, P = 5; (B) D/ONLLC/B: N=30, P = 6; (C)
D/ONLLC/B: N = 30, P = 7 ..................................................................................... 48
Hình 3.1. Ví dụ về nhiễm sắc thể được mã hoá nhị phân .........................................56
Hình 3.2. Ví dụ về các nhiễm sắc thể được mã hoá hoán vị .....................................57
Hình 3.3. Ví dụ về các nhiễm sắc thể được mã hoá theo giá trị. ..............................58
Hình 3.4. Ví dụ về các nhiễm sắc thể mã hoá theo cây. ...........................................58
Hình 3.5. Lai ghép 1 điểm cắt với mã hóa nhị phân .................................................59
Hình 3.6. Lai ghép 2 điểm cắt với mã hóa nhị phân .................................................59
Hình 3.7. Lai ghép đồng dạng với mã hóa nhị phân .................................................60
Hình 3.8. Lai ghép số học với mã hóa nhị phân .......................................................60
Hình 3.9. Đột biến với mã hóa nhị phân ...................................................................60
Hình 3.10. Lai ghép theo cây với mã hóa theo cây...................................................62

Hình 4.1. Cấu trúc quần thể là 1 cây bậc 3 hoàn chỉnh với 3 mức ................. 72

6


MỞ ĐẦU

Bài toán "Định vị và thiết kế topo trong thiết kế mạng" là một trong
các lớp bài toán quen thuộc trong lĩnh vực thiết kế mạng. Bài toán này gồm nhiều
bài toán con liên quan như: Bài toán định vị các nút mạng liên kết, bài toán định vị
nút liên kết chung và bài toán kết nối đường dẫn, …
Gần đây một phương pháp đang nổi lên và thu hút được nhiều chú ý trong
việc giải quyết bài toán định vị và thiết kế topo là giải thuật di truyền. Ý tưởng của
giải thuật di truyền xuất phát từ nguyên lý “chọn lọc tự nhiên” trong học thuyết về
sự tiến hóa của Darwin. Giải thuật có sử dụng các thao tác như chọn lọc, lai ghép,
đột biến nhằm tạo ra được lời giải tối ưu.
Với mục đích tìm hiểu về giải thuật di truyền áp dụng cho bài toán định vị
các nút mạng liên kết nói riêng, luận văn được chia làm 4 phần: phần đầu nói về sự
tương đồng mạng và các khái niệm liên quan như: lưu lượng, định tuyến,…Phần
hai, nêu hai bài toán: bài toán định vị các nút mạng liên kết, bài toán định vị nút liên
kết chung và bài toán kết nối đường dẫn. Phần ba nêu về giải thuật di truyền: từ
tổng quan một giải thuật di truyền đến các thao tác, chiến thuật lựa chọn, các thông
số cho giải thuật di truyền, ...; phần bốn nêu giải thuật di truyền và đưa ra ví dụ
minh họa áp dụng giải bài toán định vị các nút liên kết.

7


CHƢƠNG 1
TỔNG QUAN
Mạng lưới truyền thông đã được sinh ra hơn 100 năm trước vào thời điểm
Alexander Graham Bell thực hiện cuộc gọi nổi tiếng của ông tới Thomas A. Watson
và nói “Watson đến đây, tôi muốn bạn!” ngày 10 tháng 3 năm 1876. Gần một thế kỷ
sau đó, một hình thức truyền thông khác xuất hiện khi hai đầu của hệ thống
ARPAnet đã được kết nối giữa máy chủ SDS Sigma 7 tại Đại học California-Los
Angeles và máy chủ SDS 940 tại viện nghiên cứu Stanford, và tin nhắn đầu tiên
được gửi là "Lo!" ngày 29 tháng 10 năm 1969! Như chúng ta biết, cuộc gọi điện

thoại nổi tiếng đó về cơ bản đã sinh ra sự phát triển của mạng điện thoại chuyển
mạch toàn cầu, và tin nhắn đầu tiên đó là điểm khởi đầu cho sự phát triển bùng nổ
của Internet trong một phần tư thế kỷ qua. Nhiều nhà khoa học và kỹ sư đã đóng
góp vào quá trình nhằm đạt được những gì mà chúng ta có ngày hôm nay.
Ngày nay, việc định tuyến một cuộc điện thoại bàn từ người dùng này đến
người dùng khác cần đi thông qua một loạt các thiết bị chuyển mạch điện thoại,
chẳng hạn như phòng trung tâm và mạch chuyển cuộc gọi, để tới được điểm cần đến
(hình 1.1a). Tương tự như vậy, để truy cập vào một trang web trên Internet, một kết
nối ảo phân tầng giao thông được thành lập từ máy tính của người dùng đến các
máy chủ web, nơi mà các gói dữ liệu tạo bởi yêu cầu này cần phải truyền từ máy
tính của người dùng này thông qua một trạm trung chuyển hay bộ định tuyến
(hub/router - đôi khi nhiều cái một lúc) vào máy chủ tại điểm đến (hình 1.1b).
Những hình ảnh được trình bày trong hình 1.1a và 1.1b thích hợp nhất có thể
được xem như là hình ảnh của một người dùng đơn lẻ. Nhưng có hàng triệu kết nối
đang diễn ra đối với các cuộc gọi điện thoại và truyền tín hiệu web; chắc chắn,
chúng không và không thể cùng đi qua cùng một bộ chuyển mạch (đối với các cuộc
gọi điện thoại) và bộ định tuyến (đối với Internet). Điều này là không thể. Theo trực
quan, một cuộc gọi điện thoại từ tác giả thứ hai ở thành phố Kansas, Hoa Kỳ, tới tác
giả thứ nhất tại Warsaw (Vac-sa-va), Ba Lan, sẽ đi qua một bộ chuyển mạch điện
thoại khác so với bộ dùng cho một cuộc gọi từ tác giả thứ hai tại thành phố Kansas
cho tác giả thứ nhất ở Lund, Thụy Điển; chắc chắn rằng, có thể có một số bộ thiết bị

8


chuyển mạch dùng chung trên đường đi. Tương tự như vậy, tác giả thứ nhất, ngồi
trong văn phòng của mình tại trường Đại học công nghệ Warsaw, Ba Lan, và truy
cập vào trang web của tác giả thứ hai tại trường đại học của thành phố Missouri–
Kansas sẽ đi qua các trạm trung chuyển và bộ định tuyến khác với những cái dùng
khi ông ta cố gắng truy cập vào cùng trang web đó nhưng từ văn phòng khác của

ông tại Đại học Lund, Thụy Điển; cũng như vậy, như trong trường hợp của các cuộc
gọi điện thoại, một tập hợp con các trạm trung chuyển và bộ định tuyến có thể sẽ
được dùng chung cho việc truyền tải web. Bây giờ, hãy thử tưởng tượng có hàng
triệu cuộc gọi điện thoại giữa các khu vực khác nhau trên thế giới, hoặc hàng triệu
máy chủ web được truy cập bởi vô số người dùng thông qua các mạng từ khắp nơi
trên thế giới. Bức tranh này trên thực tế khá là khác so với các mô tả hạn hữu trong
hình 1.1a và 1.1b; một cái nhìn ở cấp độ cao tương ứng với số lượng người dùng
lớn, miêu tả một cái nhìn chính xác hơn sẽ được hiển thị trong hình 1.2a cho các
cuộc gọi điện thoại và hình 1.2b cho việc truyền tải web.

Hình 1.1.a. Mạng điện thoại

Hình 1.1.b. Mạng đường truyền Web Internet
1.1. Sự tƣơng đồng mạng
Đây là trường hợp một sự tương đồng đơn giản đối với việc đi lại bằng
đường hàng không có lẽ sẽ hữu ích. Giả sử rằng tác giả thứ hai muốn bay từ thành
phố Kansas đến Warsaw; ông sẽ cần phải đi từ nhà đến sân bay Kansas bằng xe hơi

9


hoặc xe taxi và đáp một số máy bay qua nhiều sân bay (với nhiều giờ di chuyển)
trước khi đến được Warsaw, và sau cùng gặp tác giả thứ nhất tại Warsaw. Bây giờ,
nếu chúng ta chỉ xem xét phần di chuyển giữa các sân bay (cụ thể là bỏ qua thời
gian tác giả thứ hai cần để đi đến sân bay ở thành phố Kansas và từ sân bay Warsaw
đến chỗ tác giả thứ nhất), sau đó chúng ta có thể hình dung một mạng lưới các sân
bay được kết nối bằng các liên kết (trực tiếp và bay suốt) để đi từ một nơi này đến
nơi khác. Trong ví dụ này, nếu hai tác giả bay từ Kansas City đến Detroit, Mỹ, đến
Amsterdam rồi đến Warsaw, thì mạng lưới cần dùng bao gồm bốn sân bay kết nối
bởi ba liên kết: 1) Kansas City đến Detroit, 2) Detroit đến Amsterdam, và 3)

Amsterdam đến Warsaw. Mặt khác, nếu tác giả thứ hai muốn đến gặp tác giả thứ
nhất ở Lund, thì đường bay thực tế là từ Kansas City đến Detroit, đến Amsterdam
rồi đến Copenhagen (Đan Mạch). Từ sân bay Kastrup của Copenhagen, cần bắt xe
lửa kết nối với Malmo, Thụy Điển, để đến được Lund. Có một vài điểm quan trọng
cần quan tâm để tìm ra sự tương đồng: 1) có nhiều phương tiện giao thông cùng
tham gia để hoàn thành toàn bộ chuyến đi – ô tô, máy bay, và đôi khi cả tàu; 2)
phương tiện để đi đến sân bay ở đầu này và đến điểm đến cuối cùng ở đầu bên kia
đòi hỏi một hình thức giao thông tiện lợi – xe hơi và xe lửa trong ví dụ này; và 3)
phần cốt lõi của chuyến đi là di chuyển bằng đường hàng không. Vì vậy, nếu chỉ xét
chuyến đi trong phạm vi các chuyến bay thì chúng ta sẽ có một tập hợp các sân bay
tạo nên một mạng lõi.

Hình 1.2.a. Mạng điện thoại nhiều người sử dụng

10


Hình 1.2b. Mạng Internet nhiều người sử dụng
Những gì chúng ta thấy, trong trường hợp của điện thoại và Internet, về bản
chất là giống như môn hình học tôpô theo hình thức là các mạng lưới kết nối các
điểm hoặc các nút khác nhau đối với các yêu cầu bởi vô số người dùng như được
thể hiện trong hình 1.2a và 1.2b; thực sự, điều này gần với thực tế hơn mô hình
điểm-tới-điểm thể hiện trước đó trong hình 1.1a và 1.1b. Tóm lại, ở đây ta chủ yếu
quan tâm đến phần giữa, nghĩa là phần cốt lõi hoặc mạng xương sống, (tương tự
như phần di chuyển bằng đường hàng không) được thực hiện các bằng bộ định
tuyến và các chuyển mạch, sau khi yêu cầu cuối cùng dời khỏi thiết bị (hoặc người
dùng) cuối cùng và trước khi nó đi đến một thiết bị cuối cùng khác. Nói chung,
những liên kết truy cập có lưu lượng vào (nếu lưu lượng đi vào lõi) và lưu lượng ra
(nếu lưu lượng đi ra từ lõi).
Xem xét lại ví dụ di chuyển bằng hàng không. Có thể hiểu để có một chuyến

bay trực tiếp không ngừng từ Kansas City đến Warsaw. Trong trường hợp này, một
liên kết giữa thành phố Kansas và Warsaw sẽ nằm trong mạng lưới. Có nhiều lý do
tại sao một chuyến bay trực tiếp giữa thành phố Kansas và Warsaw là không mong
muốn - có lẽ lý do quan trọng nhất là không có đủ lưu lượng người giữa Kansas
City và Warsaw để thực hiện một liên kết trực tiếp (tức là, một chuyến bay không
nghỉ giữa đường), do đó, sẽ là kinh tế hơn rất nhiều khi để người dùng kết nối hoặc

11


quá cảnh ở qua sân bay khác thay vì tạo ra một chuyến bay trực tiếp như vậy. Chắc
chắn, người dùng có thể thay đổi các hãng hàng không ở sân bay để tới được điểm
đến của họ. Cũng như vậy, có những điểm tương tự trong các mạng lưới truyền
thông mà lưu lượng được truyền dẫn từ nhà cung cấp mạng này sang nhà cung cấp
mạng khác.
Chúng ta vừa đề cập đến thuật ngữ lưu lượng mà nhiều người có thể hiểu
thông qua việc đi lại bằng đường hàng không (và cả việc đi lại bằng đường bộ).
Trong thực tế, lưu lượng là điểm mấu chốt để mạng điện thoại và Internet. Rõ ràng,
thay đổi lưu lượng truy cập theo thời gian, cho dù là phần triệu giây, phút, giờ,
ngày, tháng, hoặc năm, điều này thường phụ thuộc vào động lực học lưu lượng. Bây
giờ, chúng ta sẽ giả sử rằng lưu lượng là một đại lượng cố định, như số lượng cố
định những người muốn sử dụng máy bay, số lượng cố định của các cuộc gọi điện
thoại, hoặc số lượng cố định của những lượt truy cập Internet (và số lượng dữ liệu
truyền dẫn).
Mục quan trọng tiếp theo là chúng ta có thể sử dụng mô hình tiết kiệm để kết
hợp lưu lượng giữa các điểm khác nhau. Ví dụ, có thể có những hành khách (tương
đương với lưu lượng) cần đi từ St Louis, Mỹ, tới Copenhagen, thông qua lộ trình di
chuyển từ St Louis đến Detroit, đến Amsterdam rồi mới tới Copenhagen. Đường
bay giữa Detroit và Amsterdam là phần chung cho lộ trình từ Kansas City tới
Warsaw và từ St Louis tới Copenhagen. Vì vậy, bạn có thể tưởng tượng rằng những

chiếc máy bay lớn hơn có thể phục vụ tốt hơn cho đường bay giữa Detroit và
Amsterdam do lưu lượng giao thông chung cao, thế nên có thể tận dụng lợi thế của
mô hình tiết kiệm ở đây.
Điều thú vị là các mạng truyền thông và máy tính không phải là quá khác
nhau so với ví dụ về giao thông hàng không chúng ta đã thảo luận. Tương tự như ví
dụ về giao thông hàng không, một cuộc gọi cần phải được kết nối thông qua một
loạt các thiết bị chuyển mạch (đóng vai trò như sân bay); tương tự như vậy, để truy
cập vào trang web của tác giả thứ hai nằm ở Kansas City từ Warsaw, yêu cầu sẽ
được dẫn hướng thông qua một loạt các bộ định tuyến.

12


Đối với sự cần thiết để xử lý toàn bộ lưu lượng di chuyển qua đường hàng
không từ Detroit đến Amsterdam so với những phân khúc khác của ngành vận
chuyển thông qua việc sử dụng những máy bay lớn hơn (với khả năng chở nhiều
khách hơn), các mạng truyền thông và máy tính cũng có thể sử dụng các liên kết với
khả năng tải khác nhau (hoặc băng thông) cho các bộ phận khác nhau của chúng.
Cũng lưu ý rằng nếu một máy bay đã kín chỗ (tức dung lượng của nó đã bão hòa),
không thể chở thêm khách nào nữa (trừ khi có hành khách nào đó muốn bay vào
một thời điểm khác hoặc ngày khác), một tình huống tương tự có thể xảy ra trong
mạng điện thoại, nếu một liên kết không còn khả năng tải thêm dung lượng tại một
điểm cụ thể trong trường hợp đó, một cuộc gọi sẽ không được chấp nhận.
Bây giờ giả sử rằng chiếc máy bay đã thực sự kín chỗ đối với chuyến đi từ
thành phố Kansas đến Detroit. Bạn vẫn có thể muốn biết nếu có một cách khác để đi
từ thành phố Kansas đến Warsaw (vào khoảng thời gian đó). Thực sự điều đó có thể
thực hiện được, hoặc đi từ thành phố Kansas đến Memphis, đến Amsterdam rồi đến
Warsaw, hoặc từ Kansas City đến Chicago, đến London rồi đến Warsaw. Nói cách
khác, chúng ta có ít nhất hai con đường khác có thể từ Kansas City đến Warsaw
(hình 1.3). Nếu trong trường hợp sử dụng đường hàng không, hành khách thường

được yêu cầu tự mình thử (hoặc tìm) một đường bay khác (trừ khi thông qua một
hãng lữ hành), thì trong trường hợp của mạng điện thoại, mạng lưới có khả năng tự
thử những đường dẫn thay thế từ điểm gốc, trước khi thông báo cho người dùng
rằng cuộc gọi không thể được chấp nhận. Đây là một ví dụ mà mạng lưới giao
thông hàng không khác với mạng điện thoại, một phần là do tính chất đặt chỗ trước
trong ngành hàng không so với tính chất tự động hóa thời gian thực của việc định
tuyến cuộc gọi. Bất kể vậy, có một tập hợp các đường dẫn khả thi có thể có giữa hai
thành phố đầu mút, và đó cũng là trường hợp trong các mạng truyền thông. Nếu một
loại hình giao thông cụ thể đòi hỏi chất lượng dịch vụ (QoS), ví dụ, trong các tình
huống liên quan đến sự chậm trễ khi quá cảnh, thì những đường bay theo đó cần
được điều chỉnh cho phù hợp. Trong các trường hợp di chuyển bằng đường hàng
không, có lẽ tương đương để nói rằng bạn muốn xem xét các tuyến đường giữa hai
điểm mà thời gian đi của bạn ít hơn một giá trị nhất định.

13


Bây giờ, ở điểm nào và như thế nào mạng Internet tương tự như cách thức di
chuyển bằng đường hàng không? Trong giao thông hàng không, một khi bạn đã đặt
chỗ, bạn được yêu cầu để đi từ sân bay này đến sân bay khác trước khi đến được
đích của bạn; trong quá trình di chuyển, bạn cần phải chờ đợi hoặc đôi khi tạm nghỉ
tại sân bay trung gian. Khi bạn nghĩ về điều đó, chuyến đi của bạn trông như thể
bạn đang được lưu giữ tại một sân bay trung gian, trước khi được chuyển tiếp –
cách thức vận hành quen thuộc này thường được gọi là mô hình lưu trữ-và-chuyển
tiếp. Trong thực tế, trên Internet, mô hình đó được sử dụng. Có một sự khác biệt.
Khi bạn thực hiện một yêu cầu tải về một trang web, nội dung (cụ thể là trang web)
được chia thành các phần nhỏ, thường được gọi là các gói tin dữ liệu, hoặc đơn giản
là, các gói tin, được truyền dẫn qua mạng. Mỗi gói dữ liệu, giống như hành khách đi
máy bay, được gửi từ bộ định tuyến này đến một bộ định tuyến khác, nơi đó nó
được lưu trữ trong giây lát trước khi được chuyển tiếp đến bộ định tuyến tiếp theo.

Như vậy, Internet về cơ bản hoạt động trên mô hình lưu trữ-và-chuyển tiếp với
khoảng thời gian lưu trữ gần như tức thời (đối với nhận thức con người), và may
mắn là không tệ đến mức như phải chờ đợi tại sân bay. Mô hình này, trong trường
hợp của một mạng truyền dữ liệu theo gói, được gọi là chuyển mạch dạng gói.
Định tuyến thực tế trên Internet cũng có một sự tương đồng với giao thông
đường hàng không (hình 1.3). Có thể là tác giả thứ hai đã được chỉ dẫn ở thành phố
Kansas rằng đường bay từ Kansas City đến Detroit, tới Amsterdam rồi đến Warsaw
là tốt; nhưng sau khi đến ở Detroit tác giả thứ hai phát hiện ra rằng chiếc máy bay từ
Detroit đến Amsterdam đã hết chỗ, và các hành khách nhận được tùy chọn đi từ
Detroit tới Memphis, tới Amsterdam rồi đến Warsaw. Nói cách khác, tuyến đường
có thể thay đổi khi ở tại một nút quá cảnh. Điều này sẽ tương đương với việc nói
rằng sự định tuyến dựa trên phương thức hop-by-hop (từ chặng đường bay này đến
chặng đường bay khác). Trong thực tế, định tuyến trên mạng Internet, theo mặc
định, dựa trên khái niệm hop-by-hop này.

14


Hình 1.3. Mạng đường hàng không
Tất nhiên, có những sự khác biệt cơ bản giữa phương thức đi lại bằng đường
hàng không và mạng Internet hiện tại. Trái với việc di chuyển bằng đường hàng
không, nơi du khách cần đặt chỗ trước khi bay (ít nhất là trong hầu hết các trường
hợp), một gói dữ liệu hiện nay không cần phải đặt trước thời gian để truyền qua
Internet; bởi các gói dữ liệu có thể đi đến một bộ định tuyến tại cùng một thời gian,
vẫn có một sự trễ (ở mức tối thiểu) giữa các gói thông tin liên tiếp đi đến đích do
quy trình xử lý lần lượt từng gói một trong khi trong giao thông đường hàng không,
tất cả hành khách cùng đến đích một lúc.
Để tóm tắt, một mạng lưới thông tin liên lạc cần mang lưu lượng trong
trường hợp nó có các liên kết khác nhau với khả năng tải khác nhau (băng thông);
lưu lượng có thể được đinh tuyến thông qua các đường dẫn khác nhau đến đích.

Chúng ta cần phải có đủ băng thông trong mạng để mang lưu lượng truy cập trong
khi cần giảm tỷ lệ số cuộc gọi bị từ chối, hoặc giảm sự chậm trễ trong việc truyền
dẫn các gói dữ liệu thông thường trên Internet. Trong quá trình này, chúng ta cần
phải tự hỏi: 1) chúng ta có thể tìm thấy các tuyến đường tốt hơn, 2), chỗ nào chúng
ta cần có thêm băng thông mới, 3) ở đâu và khi nào chúng ta cần thêm các nút mới
(liên kết) trong mạng, 4) đặc tính sẵn có của công nghệ mạng hoặc giao thức có thể
ảnh hưởng như thế nào đến việc ra quyết định của chúng ta, và 5) mức độ trừu
tượng nào là thích hợp cho một mạng cụ thể đối với mục đích mô hình hóa để có
thể thu được những kết quả đáng kể? Lưu ý rằng chúng ta cũng có thể rút ra một sự
tương đồng với mạng lưới giao thông hàng không. Ví dụ, độ lớn của một phi đội

15


bay giữa Detroit và Amsterdam (và giữa các thành phố khác) là bao nhiêu để giao
thông có thể được cung cấp mà không phải từ chối nhiều khách hàng. Nói đơn giản,
chúng ta cần tự hỏi làm thế nào để thiết kế các mạng lõi/ xương sống thực sự hiệu
quả về chi phí khi có sự xem xét đến các đặc tính của mạng; hoặc nói tóm lại, làm
thế nào để làm thiết kế mạng.
1.2. Truyền thông, mạng máy tính và nhà cung cấp mạng
Chúng ta sẽ tiếp tục sử dụng ví dụ từ thành phố Kansas đến Warsaw, mà bây
giờ chúng ta giả định môi trường để có một mạng lưới truyền thông thay vì một
mạng lưới hàng không. Chúng ta sẽ thảo luận vấn đề này một cách riêng biệt cho
mạng điện thoại và mạng Internet.
Trong trường hợp của mạng điện thoại, hãy xem xét cuộc gọi có nguồn gốc ở
Kansas City từ văn phòng của tác giả thứ hai, đầu tiên nó sẽ đi vào phòng trung tâm
(tên chuyên ngành cho một chuyển mạch điện thoại) của nhà cung cấp dịch vụ điện
thoại địa phương. Sau đó, dựa trên việc xác định các chữ số đã ấn và xác định các
nhà cung cấp dịch vụ đường dài, các nhà cung cấp dịch vụ chuyển tiếp cuộc gọi đến
bộ chuyển mạch của nhà cung cấp dịch vụ điện thoại đường dài/quốc tế, phía mà

đến lượt mình sẽ thực hiện cuộc gọi này thông qua một số thiết bị chuyển mạch
trong mạng, bao gồm cả việc chuyển đổi mã vùng quốc tế để thực hiện sự kết nối
giữa các châu lục với nhau. Cuối cùng, cuộc gọi sẽ được chuyển giao cho các nhà
cung cấp dịch vụ viễn thông ở Ba Lan để thực hiện trong mạng riêng của họ nhằm
chuyển cuộc gọi đến văn phòng của tác giả thứ nhất đang ở Warsaw. Điểm quan
trọng cần lưu ý ở đây là một cuộc gọi được thực hiện bởi các nhà cung cấp mạng
khác nhau, còn được gọi là các nhà khai thác mạng, đối với các phân đoạn khác
nhau của cuộc gọi. Quá trình kết nối cuộc gọi trong mạng điện thoại sử dụng một
hình thức chuyển đổi, được gọi là chuyển đổi mạch mà ở đó có một mạch chuyên
dụng được thiết lập cho mỗi cuộc gọi điện thoại, ví dụ, cho các cuộc gọi từ tác giả
thứ hai tác giả đầu tiên. Khi nói đến chuyên dụng, chúng ta có ý rằng không có cuộc
gọi điện thoại khác có thể sử dụng mạch này và dung lượng cần thiết cho nó.
Trong trường hợp của yêu cầu truy cập web từ tác giả đầu tiên đến trang web
của tác giả thứ hai, yêu cầu đó sẽ đi qua một loạt các nhà cung cấp mạng khác nhau

16


(thường gọi là nhà cung cấp dịch vụ Internet, hoặc ISP) như sau: WUT-net →
pol34-net → geant-net (DANTE) → ucaid-net → greatplains-net → more-net →
UMKC-net. Trong các thuật ngữ kỹ thuật, mỗi mạng của nhà cung cấp dịch vụ
Internet là một hệ thống độc lập (AS) (mặc dù có thể rằng một nhà cung cấp dịch vụ
Internet được cấu thành bởi nhiều mạng độc lập). Đây là phương thức khá giống với
phương thức gọi điện thoại theo đặc điểm rằng các nhà cung cấp khác nhau có liên
quan đến các phân đoạn khác nhau để truyền đi các lưu lượng dữ liệu nhằm hoàn
thành việc truyền dẫn web. Các gói dữ liệu được tạo ra như là một hồi đáp đối với
yêu cầu đã được phát đi (ví dụ, các gói tin xác nhận) cũng sẽ đi theo cùng một
hướng nhưng theo chiều ngược lại (đây là hình thức phổ biến, trừ khi có một
phương thức chuyển đổi định tuyến khác trong các mạng trung gian). Theo một
trong hai hướng, chuyển mạch gói được sử dụng để định tuyến các gói dữ liệu qua

mạng.

Hình 1.4. Hệ thống các mạng
Một điểm quan trọng để quan sát từ cả hai ví dụ là một yêu cầu (một cuộc
gọi hoặc chuyển tải một trang web) đi qua một loạt các mạng lưới được duy trì bởi
các nhà cung cấp khác nhau (xem hình 1.4 - mỗi mạng được mô tả bằng cách sử
dụng một đám mây), lưu ý rằng các nhà cung cấp sẽ cần phải có thỏa thuận hợp tác
với nhau để thực hiện một yêu cầu như vậy.

Hình 1.5. Miền quản trị trong bài toán thiết kế mạng

17


Sự hợp tác giữa các nhà cung cấp lân cận nhau thường được gọi là sự sắp
xếp tương đương. Bây giờ, trong số chúng mỗi mạng có các thiết bị chuyển mạch
hoặc bộ định tuyến của họ (tùy thuộc vào loại yêu cầu); tại vùng biên hoặc lối vào,
việc truyền tải từ mạng này sang mạng khác được thực hiện. Điều này có nghĩa rằng
nó hoàn toàn phụ thuộc vào cách mỗi mạng định tuyến lưu lượng truy cập trong
phạm vi mạng của họ và/hoặc có bao nhiêu bộ đinh tuyến/thiết bị chuyển mạch họ
có thể sử dụng để thực hiện việc này. Từ thiết lập thực tế này, cần hiểu rõ rằng các
vấn đề liên quan đến thiết kế mạng về cơ bản bị giới hạn trong bản thân nó hoặc
miền quản trị của nó, như thể hiện trong hình 1.5. Ví dụ, mỗi miền tự tối ưu hóa các
tuyến đường của riêng mình mà không cần quan tâm liệu các miền khác kết nối với
nó sẽ hoạt động như thế nào.
Để tóm tắt, trong mỗi mạng, chúng ta có một tập hợp các nút được kết nối
bởi các liên kết. Trong trường hợp của mạng điện thoại, các nút là các chuyển mạch
điện thoại, và các kết nối được gọi là đường dây liên tỉnh (trunk) (hoặc các nhóm
trunk, hoặc trunk kết nối các máy với nhau). Trong trường hợp của Internet, các nút
là các bộ định tuyến, và các kết nối đôi khi được gọi là giao diện, liên kết, hay các

loại trunk. Cụ thể hơn, phần giữa bao gồm một loạt các mạng lưới, mà mỗi mạng
được quản lý bởi một nhà cung cấp khác nhau và mỗi nhà cung cấp chịu trách
nhiệm cho thiết kế phù hợp với mạng riêng của mình. Mạng lưới của các nhà cung
cấp như vậy thường được gọi là mạng đường trục.
Bên cạnh mạng điện thoại và Internet, thực tế còn có các mạng truyền thông
và cơ sở hạ tầng khác. Để giúp cho việc phân biệt, chúng ta sẽ đề cập chung đến
mạng điện thoại hoặc Internet như là các mạng lưới dịch vụ ứng dụng hoặc mạng
lưới giao thông. Ví dụ, có các mạng truyền thông tư nhân được thiết lập (trái ngược
với các mạng công cộng, chẳng hạn như Internet hoặc mạng điện thoại) cho các
công ty và các tập đoàn lớn để truyền tải giọng nói, dữ liệu, và các dịch vụ video
của họ. Trong khi các công ty tư nhân duy trì trong mạng lưới của họ các thiết bị
định tuyến/chuyển đổi riêng, thì trên thực tế họ vẫn cần thuê cơ sở vật chất từ các
nhà cung cấp mạng khác, nói cách khác, các công ty này là "khách hàng" của các
nhà cung cấp thiết bị mạng.

18


Hình 1.6. Ba miền quản trị sử dụng cùng một dịch vụ đường truyền
Những nhà cung cấp cơ sở vật chất để truyền tải dữ liệu cho mạng lưới của
các khách hàng khác nhau thường là nhà cung cấp mạng viễn thông lớn. Một lần
nữa, theo mô hình tiết kiệm, một nhà cung cấp mạng viễn thông có thể kết hợp nhu
cầu truyền tải lưu lượng từ các tuyến riêng khác nhau vào cùng một mạng. Nhìn
chung, các mạng lưới cơ sở vật chất này được xem như các mạng truyền tải và
truyền dẫn mà trong thực tế bao gồm nhiều công nghệ khác nhau, chẳng hạn như
mạng quang đồng bộ (SONET), hệ thống phân tầng kỹ thuật số đồng bộ, công nghệ
ghép kênh bước sóng... Lưu ý rằng các mạng lưới truyền tải cũng có thiết bị chuyển
mạch, thường được gọi là các kết nối chữ thập, được sử dụng để thiết lập các
mạch/đường dây dẫn cho thuê bán vĩnh viễn hoặc vĩnh viễn.
Như vậy, trong ngữ cảnh mạng lưới giao thông, chúng ta có thể thấy rằng

một nhà cung cấp mạng truyền tải có tên miền riêng của mình để đáp ứng yêu cầu
truyền lưu lượng thông qua thiết bị nút và các kết nối mạng lưới. Điều quan trọng là
chỉ ra rằng ba nhà cung cấp dịch vụ Internet khác nhau có khả năng cùng sử dụng
một nhà cung cấp mạng lưới truyền tải như thể hiện trong hình 1.6, hoặc mạng lưới
của một nhà cung cấp dịch vụ Internet có thể được dẫn bởi nhiều nhà cung cấp
mạng lưới truyền tải như thể hiện trong hình 1.7.

19


Hình 1.7. Miền quản trị sử dụng đa đường truyền

Hình 1.8. Mạng đa dịch vụ sử dụng chung đường truyền
Hơn nữa, có thể rằng một nhà cung cấp mạng lưới truyền tải sẽ thực hiện các
yêu cầu của khách hàng cho Internet, mạng điện thoại, các mạng của khách hàng tư
nhân (như thể hiện trong hình 1.8).
Bất kể vậy, cần lưu ý rằng các nhà thiết kế mạng trong mạng lưới riêng của
mình vẫn chịu trách nhiệm cho mỗi nhà cung cấp - là một nhà cung cấp mạng
Internet, nhà cung cấp dịch vụ điện thoại, nhà cung cấp mạng tư nhân, hoặc nhà
cung cấp mạng lưới truyền tải; để đơn giản, chúng ta sẽ sử dụng thuật ngữ chung
nhà cung cấp mạng để tham chiếu cho bất kỳ nhà cung cấp nào.
1.3. Khái niệm về lƣu lƣợng và nhu cầu lƣu lƣợng truy cập
Một nhà cung cấp mạng có kiểm soát về thiết kế và quản lý của mạng lưới
theo tên miền quản trị của mình; do vậy, để làm điều đó, một nhu cầu quan trọng
đối với mỗi nhà cung cấp là xác định được nhu cầu lưu lượng trong mạng riêng của
mình. Xem xét tất cả các điểm đó (hoặc các nút) trong mạng, chúng ta có thể tưởng
tượng rằng mức lưu lượng giữa hai điểm mà tạo thành một ma trận mức lưu lượng

20



truyền tải hay ma trận mức lưu lượng yêu cầu phải được xác định. Để dễ dàng cho
việc thảo luận, trong phần này chúng ta sẽ xem xét một mạng lưới kết nối đơn nơi
mà các điểm cuối có lưu lượng truy cập. Chúng ta sẽ thảo luận về khái niệm lưu
lượng truy cập Internet, mạng điện thoại.
1.3.1 Lƣu lƣợng trong Internet
Khi người dùng sử dụng các ứng dụng như email, mẩu tin tạo ra được chia
nhỏ thành các gói dữ liệu nhỏ hơn để vận chuyển qua Internet. Một phần lớn các
ứng dụng trên Internet sử dụng giao thức ngăn xếp TCP/IP (Transmission Control
Protocol / Internet Protocol). Các máy tính ở hai đầu chịu trách nhiệm chia nhỏ các
mẩu tin của một ứng dụng (ví dụ, các trang web, email) thành các gói nhỏ hơn ở
một đầu này và sau đó lại lắp ráp chúng theo thứ tự ngay tại đầu kia trước khi
chuyển giao nó cho ứng dụng; trong quá trình này, các máy tính ở hai đầu cần phải
đảm bảo rằng nếu một gói tin là tình cờ bị mất tại một nơi nào đó, chúng cần phải
làm việc với nhau để đảm bảo phát hiện ra gói tin bị mất đó và truyền lại nó đến
đúng địa chỉ của ứng dụng. Công việc của mạng lưới là định tuyến các gói dữ liệu
từ đầu này tới đầu khác và, trên thực tế, làm như vậy mà không phải xem xét độ tin
cậy trong việc chuyển giao theo giao thức TCP / IP. Các gói còn được biết đến như
là gói tin IP.
Có nhiều lý do tại sao một gói tin IP có thể không được chuyển giao tới đầu
cuối khác; ví dụ, một lỗi truyền dẫn vật lý có thể đã làm hỏng gói tin trên đường đi
khiến cho nó vô nghĩa để được chuyển tiếp đi xa hơn, một bộ định tuyến khi đang
trong quá trình truyền dữ liệu đã chạy ra khỏi không gian đệm ngay khi gói tin đặc
biệt này đến. Không giống như mạng lưới đường bộ khi bị tắc nghẽn thì bạn phải
xếp hàng đợi và bị chậm trễ, trong Internet sự chậm trễ này chỉ có thể được giải
quyết khi mà khả năng chứa của vùng đệm vẫn còn và tùy thuộc vào khả năng chứa
của bộ đệm tại các bộ định tuyến đến. Theo nguyên tắc cơ bản của giao thức TCP /
IP, dựa trên quyết định định tuyến, công việc của một bộ định tuyến là chuyển tiếp
các gói tin về phía đích mà không nhất thiết phải cân nhắc xem liệu có còn lại bất
kỳ không gian đệm nào tại bộ định tuyến đến; điều này là hoàn toàn chấp nhận được

vì quy tắc giao thức cho phép các máy tính tại hai đầu tái tạo lại bất kỳ gói dữ liệu

21


bị mất. Trong khi giao thức cho phép tốc độ truyền được điều chỉnh do tắc nghẽn hệ
thống đầu cuối, bất kỳ gói dữ liệu nào đang truyền đi vẫn có thể có thể được làm
chậm lại.
Tắc nghẽn lưu lượng có thể xảy ra trong một mạng (hoặc trong các bộ phận
của một mạng), sự chậm trễ là có thể, và các gói tin có thể được làm chậm lại. Vì
vậy, công việc của một nhà thiết kế mạng, một kỹ sư chuyên nghiệp có tay nghề
cao, là thiết kế một mạng mà giữ sự chậm trễ ở một mức tối thiểu có thể chấp nhận
được, và giảm thiểu sự mất mát các gói tin tại các bộ định tuyến (do tắc nghẽn).
Lưu ý rằng tắc nghẽn là một thực tế của cuộc sống, và ta không thể tránh nó hoàn
toàn được bởi giao thông đôi khi không thể dự đoán được. Tuy nhiên, chúng ta có
thể thiết kế một mạng theo cách mà tắc nghẽn không xảy ra tại tất cả các thời điểm,
hoặc đúng hơn, xảy ra không thường xuyên. Về cơ bản, tình huống của chúng ta sẽ
tương đương với điều này: với một đường cao tốc riêng biệt trong mạng lưới đường
bộ, sự chậm trễ thực sự là xấu; chúng ta cần nhiều tuyến đường được xây dựng hơn.
Chính xác theo cùng một cách, trên mạng Internet, chúng ta cần phải có đường
truyền đủ rộng (băng thông hoặc dung lượng) để có thể cung cấp dịch vụ ở một mức
độ chấp nhận được, ngoài ra, chúng ta cần các bộ đệm định tuyến cùng với bộ nhớ
đủ lớn để đối phó với lưu lượng truy cập tăng vọt và lưu lượng thời gian thực nhằm
tối thiểu hóa việc các gói dữ liệu bị làm chậm.
Toàn bộ bức tranh thực sự trở nên phức tạp hơn một chút. Để minh họa điều
này, chúng ta cần phải xem xét khái niệm của lưu lượng và nhu cầu lưu lượng truy
cập. Đầu tiên, chúng ta không biết trước thời gian khi nào một người dùng sẽ đăng
nhập vào máy tính của họ và liệu họ sẽ yêu cầu một trang web (từ đâu?) hoặc gửi
email. Vì vậy, từ quan điểm điểm mạng lưới, chúng ta không có sự lựa chọn nào
khác ngoài việc xem rằng đó là yêu cầu đến một cách ngẫu nhiên, không nhất thiết

theo một cách định trước. Bây giờ, hãy tưởng tượng hàng triệu người dùng ngẫu
nhiên quyết định sử dụng web hoặc gửi email. Các yêu cầu đến một cách ngẫu
nhiên; nói cách khác, điều này có nghĩa việc đến của gói tin trong mạng là ngẫu
nhiên. Các hệ thống đo lường cần được đặt đúng chỗ trong một mạng để nắm bắt số
liệu thống kê, như vậy sự phân phối lưu lượng truy cập đến và mức lưu lượng có thể
được ước tính.

22


1.3.2. Lƣu lƣợng trong mạng điện thoại (Traffic in the Telephone Network)
Tương tự với Internet, mạng điện thoại cũng có mô hình đến ngẫu nhiên.
Trong trường hợp này, dữ liệu đến liên quan đến cuộc gọi. Rõ ràng là, chúng ta
không biết khi nào thì một người sử dụng muốn thực hiện một cuộc gọi và gọi đi
đâu. Do đó, một lần nữa chúng ta gặp phải bài toán dữ liệu đến ngẫu nhiên. Từ thảo
luận về Internet, có thể thấy ngay rằng tương tự với tỷ lệ gói dữ liệu đến, chúng ta
cần phải xem xét việc xác định tỷ lệ cuộc gọi đến trung bình để xác định lượng yêu
cầu.
Một khía cạnh quan trọng về mạng điện thoại là khi bạn thực hiện một cuộc
gọi và bạn đã kết nối vào mạng, mạch âm thanh được tách riêng cho bạn đến khi
bạn dập máy do chức năng chuyển mạch. Nói cách khác, mạch của đường kết nối
của bạn không được đóng lại để người khác sử dụng đến khi bạn nói chuyện xong.
Để đơn giản hóa điều này, chúng tôi sẽ giả định tạm thời là cuộc gọi đến trong một
mô hình có thể xác định được và chúng ta chỉ đang xem xét một mạch thoại đơn.
Miễn là cuộc gọi đến tại thời điểm bắt đầu của một giờ và người sử dụng nói
chuyện trong đúng một giờ. Do đó, người sử dụng này chỉ nói chuyện trong đúng
10 phút và sau đó dập máy. Mạch không được người khác sử dụng trong thời gian
còn lại của 1 giờ. Trong thực tế, nếu một người sử dụng khác đến ngay và chiếm
mạch trong hơn 10 phút, thì người sử dụng thứ ba có thể bắt đầu sử dụng mạch 20
phút đến 1 giờ. Do đó, nếu chúng ta chia độ dài cuộc gọi thành những phần 10 phút

cố định, chúng ta có thể có 6 cuộc gọi; điều này nghĩa là chúng ta có 6 cuộc gọi đến
mỗi giờ (mỗi cuộc gọi mất 10 phút) trái với cuộc gọi đến của mỗi người sử dụng (sử
dụng trong 1 giờ để nói chuyện) trong khi trong trường hợp khác chúng ta chỉ cần
thêm mạch! Điều thực tế này cho thấy là sự gia tăng tỷ lệ cuộc gọi đến không hoàn
toàn nghĩa là chúng ta cần thêm mạch (hoặc thông thường là băng thông) do bài
toán thời gian cuộc gọi trung bình.
1.4. Khái niệm về định tuyến và dòng (Notion of routing and flows)
Khi chúng ta có Đường truyền từ một điểm đến một điểm khác, phải cài đặt
một link trực tiếp càng dài càng có tính thương mại và Đường truyền khả thi. Điều

23


này tương đương với ví dụ về chuyến bay trực tiếp, liên tục từ thành phố Kansas tới
Warsaw. Do chúng ta thấy một vài đường đi từ Thành phố Kansas tới Warsaw bằng
cách chuyển máy bay tại chặng trung chuyển, rõ ràng là điều này không cần phải có
một chuyến bay trực tiếp (hoặc link trực tiếp xét về mạng).
Chúng ta cũng có thể thấy một tình trạng thú vị từ trường hợp, dựa trên
chặng, mà một người bắt dầu từ Thành phố Kansas cần phải thay đổi chuyến bay từ
Detroit để đi qua Memphis thay vì từ Detroit đến Amsterdam. Cố gắng nghĩ từ một
cuộc gọi hoặc một gói dữ liệu, một điểm quan sát trong mạng máy tính và mạng
truyền thông, đường này vẫn là khả thi. Nếu chúng ta cần đủ Đường truyền để
chuyển hướng theo cách đó, chúng ta vẫn có thể xem Thành phố Kansas-DetroitMemphis-Amsterdam-Warsaw là tuyến đường khả thi trong tổng thể, không quan
trọng số người sử dụng tuyến này.
Có thể thấy được từ ví dụ đi lại bằng đường không là có hai tuyến đường có
thể sử dụng định tuyến: 1) những người cụ thể nào có thể đi lại (ví dụ trong trường
hợp khẩn) từ một điểm đến một điểm khác và 2) nói chung, làm thể nào Đường
truyền tổng thể có thể được định tuyến giữa hai điểm tương đương. Trong bối cảnh
này, chúng ta có thể sử dụng thuật ngữ tuyến hoặc định tuyến theo hai cách khác
nhau trong mạng máy tính và mạng truyền thông: 1) để biểu thị điều gì diễn ra xét

về định tuyến một gói hoặc cuộc gọi cụ thể, và 2) xét về việc nếu một lượng Đường
truyền (cuộc gọi hoặc gói dữ liệu) sẽ được định tuyến hoặc tuyến đường thuộc nội
dung mô tả sau này, ví dụ làm thế nào Đường truyền được định tuyến nói chung
trên một đường cụ thể. Điều này đặc biệt quan trọng do trong khi xem xét thiết kế
một mạng thì làm thế nào một gói hoặc cuộc gọi thực tế được định tuyến một cách
đặc biệt không quan trọng do chức năng của mạng/công nghệ/giao thức để cấp cho
cuộc gọi/truyền dữ liệu được nắm bắt một cách thích hợp. Do đó, chúng tôi sẽ sử
dụng khái niệm danh sách đường lựa chọn để chỉ các tuyến đường có thể đi mà có
thể được thực hiện bởi Yêu cầu đường truyền giữa hai điểm. Nếu một tuyến đường
cụ thể được chọn là đường có hiệu lực theo thiết kế mạng, chúng tôi sẽ chỉ định đây
là một tuyến. Một khía cạnh khác chúng ta cần phải chú ý là tổng nhu cầu là bao

24


nhiêu giữa hai điểm được định tuyến (“đi lại”) trên một tuyến nhất định. Do đó,
tổng Đường truyền liên quan đến tuyến có thể được xem là dòng mà là một khía
cạnh quan trọng.

25