BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
o0o

BÁO CÁO
TIỂU LUẬN MÔN HỌC

LẬP TRÌNH MẠNG NÂNG CAO
ĐỀ SỐ 17

1. Hãy viết chương trình cài đặt thuật toán phân bố tải của mạng IP trong
quá trình định tuyến các gói thông tin.
2. Nghiên cứu thật kỹ quá trình định tuyến trong mạng TCP/IP và chọn 1
trong 2 phương pháp: tỉnh và động.
3. Mô phỏng quá trình chuyển gói giữa một số Server.
4. Lập chương trình Monitoring để giám sát đường di chuyển của các gói.

Giáo viên hướng dẫn: PGS TS Lê Văn Sơn
Học viên : Bùi Tấn Ngọc
Chương 2: Định tuyến thông tin trong mạng TCP/IP và thuật toán phân bố tải của
mạng IP trong quá trình định tuyến các gói thông tin.
Chương 3: Xây dựng chương trình Monitoring giám sát đường đi của các gói theo
phương pháp định tuyến tĩnh.
Để hoàn thành tiểu luận này, tôi xin chân thành cám ơn sự chỉ bảo tận tình của
PGS.TS.Lê Văn Sơn và các bạn học viên trong lớp. Tuy nhiên chắc hẳn vẫn còn nhiều
thiếu sót, kính mong sự góp ý của thầy giáo và các bạn để tôi hoàn thành tốt hơn tiểu
luận này.
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 2

CHƯƠNG 1
NHỮNG VẤN ĐỀ CƠ BẢN VỀ MẠNG VÀ ĐIỀU KHIỂN TẢI
1. Mạng máy tính
Mạng máy tính là tập hợp các máy tính hoặc các thiết bị được nối với nhau bởi
các đường truyền vật lý và theo một kiến trúc nào đó.
Chúng ta có thể phân loại mạng theo qui mô của nó:
Mạng LAN (Local Area Network)-mạng cục bộ: kết nối các nút trên một phạm
vi giới hạn. Phạm vi này có thể là một công ty, hay một tòa nhà.
Mạng WAN (Wide Area Network): nhiều mạng LAN kết nối với nhau tạo
thành mạng WAN.
MAN (Metropolitan Area Network), tương tự như WAN, nó cũng kết nối nhiều
mạng LAN. Tuy nhiên, một mạng MAN có phạm vi là một thành phố hay một
đô thị nhỏ. MAN sử dụng các mạng tốc độ cao để kết nối các mạng LAN của
trường học, chính phủ, công ty, , bằng cách sử dụng các liên kết nhanh tới
từng điểm như cáp quang.
1.1 Thiết bị giao tiếp mạng (Network Interface Thiết bị)
NIC là thiết bị giao tiếp được sử dụng để kết nối một thiết bị với mạng LAN. Nó
cho phép chúng ta gửi và nhận các thông điệp từ mạng. Một NIC có một địa chỉ MAC

Các giao thức định tuyến trạng thái liên kết: Việc tính toán đường đi tốt nhất
của các giao thức định tuyến OSPF và BGP quan tâm đến nhiều yếu tố như tốc
độ, độ tin cậy, và thậm chí là chi phí của đường đi.
Các giao thức định tuyến lai: Các giao thức này sử dụng sự kết hợp việc tính
toán trạng thái liên kết và vectơ khoảng cách.
1.3 Vấn đề tìm đường đi trong mạng
Với cấu hình TCP/IP, một gateway mặc định được thiết lập. Đây là một địa chỉ
IP của cổng bộ định tuyến mà subnet kết nối tới. Bộ định tuyến này được sử dụng khi
một host ở bên ngoài subnet cần được liên lạc.
Ta có thể thấy bảng định tuyến cục bộ trên hệ điều hành Windows bằng cách sử
dụng lệnh ROUTE PRINT trên dòng lệnh. Lệnh này hiển thị các gateway sẽ được sử
dụng cho mỗi liên kết mạng. Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 4

2. Điều khiển tải
Điều khiển tải là làm cho việc lưu thông trên mạng tốt nhất, giảm tối đa tình
trạng quá tải dẫn đến nghẽn mạng và được thể hiện dưới hai phương diện sau đây:
 Điều khiển tải tổng quát: Điều khiển tải tổng quát chịu trách nhiệm giữ nhịp
cho các hoạt động cung cấp tài nguyên.
 Điều khiển tải phân tán: Phân tán tải cho các đối tượng có khả năng cung cấp
như là người điều khiển hợp lý việc phân bố tài nguyên.
2.1 Điều khiển tải tổng quát
Mục tiêu của phương pháp này là tìm cách duy trì tổng số yêu cầu tài nguyên
được lưu chuyển trong mạng luôn nhỏ hơn một giá trị giới hạn (ngưỡng) N nào đó.
Giá trị N sẽ được xác định trước căn cứ vào khả năng tài nguyên và cũng như kinh
nghiệm hoạt động của mạng.

- Cập nhật thông tin định tuyến, tức là thông tin dùng cho chức năng
Có rất nhiều kỹ thuật định tuyến 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 2 chức năng trên. Các yếu tố đó thường là:
(a) Sự phân tán các chức năng định tuyến trên các nút của mạng
(b) sự thích nghi với trạng thái hiện hành của mạng
(c) Các tiêu chuẩn tối ưu để định tuyến
Dựa trên yếu tố (a) ta có kỹ thuật định tuyến tập trung (Centralized Routing) hoặc
phân tán (Distributed Routing).
Dựa trên yếu tố (b) ta có kỹ thuật định tuyến tĩnh (Static hay Fixed Routing) hoặc
thích nghi (Adaptatif Routing)
2. Kỹ thuật định tuyến tập trung và định tuyến phân tán
Kỹ thuật định tuyến tập trung được đặc trưng bởi sự tồn tại của một hoặc vài
trung tâm điều khiển mạng thực hiện việc định tuyến, sau đó gởi các bảng định tuyến
(Routing Table) tới tất cả các nút dọc theo con đường đã được chọn đó. Trong trường
hợp này, thông tin tổng thể của mạng cần dùng cho việc định tuyến chỉ được cất giữ
tại trung tâm điều khiển mạng. Các nút mạng có thể không gởi bất kỳ thông tin trạng
thái nào của chúng tới trung tâm, hoặc gởi theo định kỳ, hoặc gởi khi có sự thay đổi
nào đó. Trung tâm điều khiển sẽ cập nhật các bảng định tuyến dựa trên những thông
tin nhận được từ các trạm gởi lên.
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 6

Với kỹ thuật định tuyến phân tán thì không tồn tại trung tâm điều khiển mạng.
Quyết định định tuyến được thực hiện tại mỗi nút của mạng. Điều này đòi hỏi sự trao
đổi thông tin thường xuyên giữa các nút trong mạng.
3. Kỹ thuật định tuyến tĩnh và định tuyến động
Kỹ thuật định tuyến tĩnh (không thích nghi): có thể tập trung hoặc 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, việc
định tuyến được thực hiện mà không có sự trao đổi thông tin, không đo lường và

Học viên: Bùi Tấn Ngọc 7 Các thành phần trong mạng TCP/IP
Bảng định tuyến (tĩnh) lưu trữ trong Router A:
Entry
Network Address
Netmask
Gateway
Interface
1
192.168.1.0
255.255.255.0
192.168.1.1
192.168.1.1
2
192.168.2.0
255.255.255.0
10.0.1.2
10.0.1.1
3
192.168.3.0
255.255.255.0
10.0.1.2
10.0.1.1
Để chọn lựa phương án triển khai giải quyết vấn đề chuyển gói tin trong
mạng, người ta thường quan tâm hàng đầu đến độ tin cậy, ổn định và chi phí thực
hiện của chúng. Một trong số các phương pháp định tuyến đã được nghiên cứu và
triển khai áp dụng trong quá trình định tuyến trong mạng TCP/IP hiện nay:
- Phương pháp cố định/tĩnh (Fixed Routing)

độ trễ trung bình của các datagram trên các liên kết.
 Đo độ trễ
Độ trễ của một liên kết được đo như sau: Giả sử
dt là độ trễ truyền một gói tin giữa hai nút hai đầu một liên kết
dp là độ trễ truyền dẫn của liên kết (là hằng số đối với mỗi liên kết)
dq là độ trễ xử lý và đợi trong nút gởi (nút nguồn)
Khi đó, độ trễ tổng cộng d được tính như sau:
d = dt + dp + dq
Độ trễ trung bình trên liên kết được tính sau 10 giây một cho tất cả các datagram đi
qua. Nếu độ trễ được tính này khác với độ trễ cũ (quá một ngưỡng cho trước nào đó)
thì nó sẽ gởi đến tất cả các nút khác nhờ các đơn vị dữ liệu điều khiển (thông báo cập
nhật). Ngoài ra, để đảm bảo độ tin cậy của việc cập nhật, một thông báo cập nhật sẽ
luôn được gởi đi:
- Sau một khỏang thời gian T, ngay cả nếu không có sự thay đổi nào; hoặc
- Ngay sau khi có sự thay đổi trạng thái của một liên kết.
 Cập nhật nội dung routing table
Với giải thuật chọn đường mô tả ở trên, trong đó mỗi nút phải biết thông tin tổng
thể của mạng, vấn đề truyền thông tin chọn đường (ở đây là độ trễ) trở nên rất quan
trọng. Các thông báo cập nhật phải được nhận đúng để cho tất cả cơ sở dữ liệu ở các
nút là như nhau (gắn bó dữ liệu).
Phương pháp cập nhật nội dung routing table trong mạng TCP/IP như sau:
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 9

- Mỗi thông báo cập nhật của một nút chứa thông tin về độ trễ của tất cả các liên
kết của nút đó.
- Mỗi nút gởi thông báo cập nhật của mình tới tất cả các nút láng giềng (sau một
khỏang thời gian T hoặc ngay lập tức sau khi có sự thay đổi đối với 1 liên kết).
- Một router láng giềng khi nhận được một broadcast để cập nhật, router này sẽ so

Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 10

Hai thuật toán chọn đường thường được sử dụng phổ biến trong kỹ thuật định
tuyến thích nghi động là:
- Thuật toán định tuyến theo vector khoảng cách (Distance-Vector Routing)
- Thuật toán định tuyến theo trạng thái liên kết (Link -State Routing).
5.2 Thuật toán định tuyến theo vector khoảng cách (Distance-Vector Routing)
Thuật toán định tuyến theo vector khoảng cách (Distance-Vector Routing) nhằm
tính toán con đường ngắn nhất giữa các cặp node (router) trong mạng dựa trên thuật
toán Bellman-Ford. Các node mạng thực hiện quá trình trao đổi thông tin trên cơ sở
của địa chỉ đích, node kế tiếp, và con đường ngắn nhất tới đích.
Với thuật toán này, tại mỗi nút, các Router được giả định biết khoảng cách đến
mỗi nút láng giềng của nó (có thể là độ trễ). Khi từng T msec mỗi Router gởi cho mỗi
láng giềng một danh sách các độ trễ ước tính của nó đến từng nút láng giềng và nó
cũng nhận được một danh sách tương tự từ các nút láng giềng.
Xét một trong các bảng chọn đường đến từ nút láng giềng X, với X
i
là ước tính
thời gian X cần đến Router i. Nếu Router biết độ trễ đến X là m msec thì nó cũng biết
đến router i qua X là (X
i
+ m) msec. Thực hiện phép tính này với mỗi nút láng giềng,
một router có thể tìm ra độ trễ tốt nhất (nhỏ nhất) và nó dùng độ trễ này để cập nhật lại
giá trị đường tương ứng trong bảng chọn đường mới.
Chi tiết của thuật toán Bellman – Ford được mô tả như sau:
Giả thuyết:
- Cho một đồ thị G(V,E) trong đó V là tập đỉnh và E là tập cạnh có trọng số
- Đỉnh nguồn S: S V


j V\{S}
P(S)i = j
- Bước 3: Lặp lại bước 2 cho đến khi không có đường đi mới nào ngắn hơn
đường đi đã được tìm thấy, nghĩa là D(s)i

không có sự thay đổi qua 2 lần chạy liên
tiếp với i V\{S} thì dừng.
- Bước 4: Xác định D(S)i sẽ là giá trị đường đi ngắn nhất từ node S đến nút
i thông qua nút láng giềng là giá trị của P(s)i
.

5.3 Thuật toán định tuyến theo trạng thái liên kết (Link -State Routing)
Link-State Routing dựa trên thuật toán Dijkstra, bình thường nó còn được gọi là
thuật toán Shortest Path First (SPF). Các router chạy một giao thức Link-State liên
quan trực tiếp tới trạng thái (state) của một cổng trên router khác trong hệ thống mạng.
Một Link-State router xây dựng toàn bộ dữ liệu về tất cả các trạng thái từ tất cả các
router trong một vùng. Một nghĩa khác, một Link-State router lấy đủ các thông tin để
chúng có thể vẽ lên một bản đồ của hệ thống mạng.
Mỗi router sau khi chạy thuật toán SPF trong bản đồ do chúng xây dựng, hay dữ
liệu về link-state, để nhận ra một đường đi tốt nhất nhằm thiết lập trong routing table.
Router sẽ quảng bá thông tin Link-State này tới tất cả các router trên mạng. Toàn bộ
quá trình quảng bá này được gọi là Link-state Advertiesements (LSAs).
Không như Distance Vector Routers, Link-State Routers có thể thiết lập những
mỗi quan hệ đặc biệt giữa các router khác để đảm bảo rằng thông tin LSA được truyền
một cách hiệu quả nhất để đảm bảo tất cả các rouer trên mạng đều có cái nhìn giống
nhau về topo mạng.
Hệ thống mạng được xây dựng như một cái cây mà gốc là chính router đó, mỗi
router được coi là gốc của mạng và từ đó nó tìm đường đi ngắn nhất tới các mạng sau
khi xây dựng được bản đồ hệ thống mạng và chạy thuật toán SPF.


- d
ij
: trọng số trên cạnh nối trực tiếp từ node i đến node j
dij = 0 nếu i trùng j hoặc dij = Eij nếu i khác j
Giải thuật:
- Bước 1: Khởi động
M

= {S};
D(S)
I
=d
SI
; I V\M
P(S)
I
={S,I}

Nếu d
SI
∞ hoặc P
I
= {} nếu d
SI
= ∞ - Bước 2: Cập nhật đường đi ngắn nhất
Chọn đỉnh N V sao cho D

D
A
B
E
C
F
2
2
2
1
1
1
3
3
5
5
Router
Khoang cach/
Do tre

Sơ đồ minh họa định tuyến theo vecto khoảng cách
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 14

Xây dựng và cập nhật nội dung routing table tại các nút mạng (router)
Xét tại thời điểm khởi động, nội dung của các routing table tại các nút mạng (router)
như sau:
H1
A

I

P(E)
I

D(F)
I

P(F)
I

A
0
-
2
A
1
A
5
A
∞

∞

B
2
B
0
-
2

D
5
D
E
∞

∞

1
E
1
E
0
-
2
E
F
∞

∞

∞

5
F
2
F
0
-
Sau khi khởi động, các router sẽ tiến hành trao đổi thông tin với nhau và cập nhật

Cập nhật đường đi từ A – C:
- Đi qua B: D(A)
C
= d
AB
+ D(B)
C
= 2 + 2 = 2
- Đi qua C: D(A)
C
= d
AC
+ D(C)
C
= 1 + 0 = 1
- Đi qua D: D(A)
C
= d
AD
+ D(D)
C
= 5 + 3 = 8
Như vậy D(A)
C
= min(2, 1, 8) = 1 và lúc này P(A)
C
= C
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 15

E
= d
AB
+ D(B)
E
= 2 + ∞ = ∞
- Đi qua C: D(A)
E
= d
AC
+ D(C)
E
= 1 + 1 = 2
- Đi qua D: D(A)
E
= d
AD
+ D(D)
E
= 5 + 1 = 6
Như vậy D(A)
E
= min(∞, 2, 6) = 2 và lúc này P(A)
E
= C
Cập nhật đường đi từ A – F:
- Đi qua B: D(A)
F
= d
AB

F
D(A)
I

P(A)
I

D(B)
I

P(B)
I

D(C)
I

P(C)
I

D(D)
I

P(D)
I

D(E)
I

P(E)
I

C
5
E
C
1
C
2
C
0
-
2
E
1
C
3
E
D
4
C
3
D
3
D
0
-
1
D
3
E
E

H3
A
B
C
D
E
F
D(A)
I

P(A)
I

D(B)
I

P(B)
I

D(C)
I

P(C)
I

D(D)
I

P(D)
I

-
2
B
3
B
3
C
5
E
C
1
C
2
C
0
-
2
E
1
C
3
E
D
4
C
3
D
2
E
0

-

H4
A
B
C
D
E
F
D(A)
I

P(A)
I

D(B)
I

P(B)
I

D(C)
I

P(C)
I

D(D)
I


B
0
-
2
B
3
B
3
C
5
E
C
1
C
2
C
0
-
2
E
1
C
3
E
D
3
C
3
D
2

F
0
-
Khi đó đường đi trong quá trình định tuyến gói tin từ router A đến router D sẽ diễn ra
như sau:
- Router A tra bảng routing table của mình và thấy muốn gửi đến D phải đi qua
C nên chuyển gói tin trực tiếp cho Router C.
- Sau khi nhận được, Router C tra bảng routing table của mình và thấy muốn
gửi đến D phải đi qua E nên chuyển gói tin trực tiếp cho Router E.
- Sau khi nhận được, Router E tra bảng routing table của mình và thấy có thể
chuyển trực tiếp đến Router D.
- Router D nhận gói tin, kiểm tra thấy gửi cho mình và tiến hành xử lý.
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 17 A C E D
D(A)
I


A

A
2
C

A
3
E
B
2
B

B
2
B

B
3
C

B
3
B
C
1
C

C
0

E

E
0
-

E
1
E
F
4
C

F
3
E

F
2
F

F
3
E
D
A
B
E
C
F

Trong quá trình vận hành hệ thống, các gói tin được gởi đi từ đâu, đi qua các
Router để đến đích sẽ được theo dõi bởi Monitoring và được hiển thị trên màn hình.
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 19

2. Xây dựng các chương trình của bài toán
Bài toán được tổ chức thành 9 modul, 4 modul đóng vai trò là các Router, 4
modul đóng vai trò là các Host và 1 modul đóng vai trò là Monitoring.
Các Host gởi gói tin đến các Router mà nó đang kết nối, căn cứ vào thông tin
định tuyến tại Router mà các Router sẽ xác định nút kế tiếp để chuyển gói tin đi. Các
Host và Router chuyển gói tin đến đâu sẽ gởi thông tin về cho Monitoring.
Các modul được xây dựng dựa trên cơ chế đa luồng và socket trong Java theo
mô hình truyền thống Client/Server như sau:

Chương trình Java tiêu biểu như sau:
- Host:
import java.io.*;
import java.net.*;
public class HostA
{
public static void main(String args[])
{
System.out.println();
System.out.println("Host A da san sang!");
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 20

try

import java.net.*;
public class Router1
{
public static void main(String arg[])
{
System.out.println();
System.out.println("Router1 da san sang!");
try
{
//Tao Socket tren Router
ServerSocket serverSocket = new ServerSocket(2001);
while(true)
{
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 21

Socket connectToClient = serverSocket.accept();
HandleRouter1 thread = new HandleRouter1(connectToClient);
thread.start();
}
}
catch(IOException ex)
{
System.err.println(ex);
}
}
}
//Dinh nghia lop ke thua tu Thread de xu ly mot ket noi moi
class HandleRouter1 extends Thread

else if(IpDest.equals("193.24.56"))
{
iPort = 2002;
Tiểu luận môn học Lập trình mạng nâng cao

Học viên: Bùi Tấn Ngọc 22

System.out.println("Chuyen den Router2");
}
// Tao socket de ket noi toi Monitoring
Socket connectToMonitor = new Socket("localhost", 2000);
PrintWriter Stm = new
PrintWriter(connectToMonitor.getOutputStream(), true);
String St = "den Router 1 ";
Stm.println(St);
Stm.flush();
try
{
sleep(1000);
}
catch (Exception e)
{
System.out.println("Sleep Error");
}
// Tao socket de ket noi toi Router ke tiep
Socket connectToServer = new Socket("localhost", iPort);
PrintWriter osToServer = new
PrintWriter(connectToServer.getOutputStream(), true);
osToServer.println(inputData);
osToServer.flush();

}
}
catch(IOException ex)
{
System.err.println(ex);
}
}
}
//Dinh nghia lop ke thua tu Thread de xu ly mot ket noi moi
class HandleAClient0 extends Thread
{
private Socket connectToClient;
public HandleAClient0(Socket socket)
{
connectToClient = socket;
}
public void run()
{
try
{
BufferedReader inMnt = new BufferedReader(new
InputStreamReader(connectToClient.getInputStream()));
// Nhan goi tin tu Client
String inputData = inMnt.readLine();
System.out.print(inputData);
if(inputData.equals("den Host C")^inputData.equals("den Host B"))
{
System.out.println();
}
}