Lý thuyết lập trình căn bản - Chương 6: Mạng chuyển mạch gói (Packet switching)

Chương 6: Mạng chuyển mạch gói (Packet switching) bvhieu@cse.hcmut.edu.vn Bộ môn Kỹ thuật máy tính Khoa Khoa Nội dung  Giới thiệu mạng chuyển mạch gói  Tìm đường  X.25 Bộ môn Kỹ thuật máy tính Khoa Khoa Nội dung  Giới thiệu mạng chuyển mạch gói  Tìm đường  X.25 Bộ môn Kỹ thuật máy tính Khoa Khoa Hạn chế của chuyển mạch mạch  Các tài nguyên được dành riêng cho cuộc gọi  Hầu hết thời gian kết nối đường truyền rảnh  Tốc độ dữ liệu cố định  Thiết bị ở hai đầu phải chạy cùng tốc độ Bộ môn Kỹ thuật máy tính Khoa Khoa Nguyên lý chuyển mạch gói  Dữ liệu được truyền thành các gói nhỏ  Thông thường là 1000 byte  Dữ liệu lớn được chia thành chuỗi các gói nhỏ để truyền  Mỗi gói gồm dữ liệu cộng thêm thông tin điều khiển  Các gói được nhận, lưu tạm thời và truyền cho node kế tiếp (store and forward) Bộ môn Kỹ thuật máy tính Khoa Khoa Ưu điểm chuyển mạch gói  Tăng hiệu suất đường truyền  Một kết nối node-node có thể dùng chung bởi nhiều gói  Các gói xếp hàng và truyền đi nhanh nhất có thể  Chuyển đổi tốc độ dữ liệu  Mỗi trạm kết nối với node cục bộ bằng tốc độ của trạm  Các node đệm dữ liệu nếu cần thiết để cân bằng tốc độ  Các gói được nhận ngay khi mạng đang bận  Việc phát có thể chậm lại  Có thể phân độ ưu tiên cho các thông báo Bộ môn Kỹ thuật máy tính Khoa Khoa Kỹ thuật chuyển mạch  Trạm chia thông báo dài thành nhiều gói nhỏ  Từng gói được gởi lần lượt vào mạng  Các gói được xử lý theo 2 cách  Datagram  Virtual circuit Bộ môn Kỹ thuật máy tính Khoa Khoa Datagram  Mỗi gói được xử lý độc lập  Các gói có thể đi theo bất cứ đường thích hợp nào  Các gói có thể đến đích không theo thứ tự gởi  Các gói có thể thất lạc trên đường đi  Bên nhận phải sắp xếp lại các gói mất trật tự và khôi phục các gói thất lạc Bộ môn Kỹ thuật máy tính Khoa Khoa Minh họa Datagram 2 1 3 2 1 3 (c) 3 1 2 (b) (a) (d) (e) 2 1 3 3 2 1 Bộ môn Kỹ thuật máy tính Khoa Khoa Virtual circuit  Đường đi được tạo trước khi gởi các gói dữ liệu  Các gói yêu cầu cuộc gọi và chấp nhận cuộc gọi được dùng để tạo kết nối (handshake)  Mỗi đường đi được gán một số ID  Mỗi gói chứa ID của đường đi thay vì địa chỉ máy đích  Không cần tìm đường cho từng gói  Đường đi không dành riêng Bộ môn Kỹ thuật máy tính Khoa Khoa Minh họa Virtual circuit 2 1 3 2 3 2 1 3 (c) 1 3 (b) (a) (d) (e) 2 1 3 2 1 Bộ môn Kỹ thuật máy tính Khoa Khoa So sánh Virtual Circuit Datagram  Sự trình tự và điều khiển lỗi ?  Thời gian trễ đễ truyền được một gói ?  Thời gian trễ đễ truyền các gói sau gói đầu tiên ?  Khả năng chịu lỗi ?  Tính linh động về đường đi ? Bộ môn Kỹ thuật máy tính Khoa Khoa Vấn đề kích thước gói 1 Data 1 Data Header (a) 1-packet message (b) 2-packet message (c) 5-packet message (d) 10-packet message Data Data Data 2 Data 1 Data 2 Data 1 Data 2 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 2 3 4 5 1 2 3 4 5 1 2 3 4 5 Figure 10.14 Effect of Packet Size on Transmission Time X a b Y X a b Y X a b Y X a b Y T im e Bộ môn Kỹ thuật máy tính Khoa Khoa Circuit vs. Packet Switching Người gởi được thông báo nếu các gói không được phân phát Người gởi có thể được thông báo nếu các gói không được phân phát Tín hiệu bận nếu bên nhận không sẵn sàng Trễ do quá trình thiết lập, trễ truyền các gói Trễ truyền các góiTrễ do quá trình thiết lập, nhưng thời gian trễ trong quá trình truyền không đáng kể Đường đi được thiết lập cho toàn bộ quá trình trao đổi Đường đi được thiết lập cho mỗi gói Đường truyền dẫn được thiết lập cho toàn bộ quá trình trao đổi Thông báo được lưu trữ cho đến khi đến phân phát Thông báo có thể được lưu trữ cho đến khi đến phân phát Thông báo không được lưu trữ Đủ nhanh cho ứng dụng tương tác Đủ nhanh cho ứng dụng tương tác Đủ nhanh cho ứng dụng tương tác Dữ liệu truyền theo góiDữ liệu truyền theo góiDữ liệu truyền liên tục Đường truyền dẫn không dành riêng Đường truyền dẫn không dành riêng Đường truyền dẫn dành riêng Virtual Circuit PacketsDatagram PacketsCircuit Switching Bộ môn Kỹ thuật máy tính Khoa Khoa Circuit vs. Packet Switching (tt) Tốn kém dữ liệu cho mỗi gói Tốn kém dữ liệu cho mỗi gói Không tốn chi phí dữ liệu sau khi thiết lập Linh động sử dụng băng thông Linh động sử dụng băng thông Truyền dẫn băng thông cố định Chuyển đổi tốc độ và bảng mã Chuyển đổi tốc độ và bảng mã Thường không cần chuyển đổi tốc độ và bảng mã Mạng có thể sẽ chịu trách nhiệm cho chuỗi các gói Mạng có thể sẽ chịu trách nhiệm cho các gói đơn lẻ User chịu trách nhiệm khi các thông báo bị thất lạc Node chuyển mạch nhỏNode chuyển mạch nhỏChuyển mạch cơ điện hoặc được điều khiển bởi máy tính Quá tải có thể khóa việc thiết lập; tăng thời gian trễ của gói Quá tải sẽ tăng thời gian trễ của gói Quá tải sẽ khóa việc thiết lập; không trễ khi đường truyền đã được thiết lập Virtual Circuit PacketsDatagram PacketsCircuit Switching Bộ môn Kỹ thuật máy tính Khoa Khoa Hoạt động bên ngoài – bên trong  Giao tiếp giữa các node mạng (bên trong)  Datagrams hoặc virtual circuits  Giao tiếp giữa trạm và node mạng (bên ngoài)  Kết nối (Connection oriented)  Trạm yêu cầu kết nối luận lý (virtual circuit)  Tất cả các gói được đánh dấu thuộc về kết nối đó và được đánh số thứ tự  Mạng phân phát các gói theo thứ tự  Dịch vụ mạch ảo bên ngoài  Không kết nối (Connectionless)  Các gói được xử lý độc lập  Dịch vụ datagram bên ngoài Bộ môn Kỹ thuật máy tính Khoa Khoa External Virtual Circuit and External Datagram Bộ môn Kỹ thuật máy tính Khoa Khoa Internal Virtual Circuit and Internal Datagram Bộ môn Kỹ thuật máy tính Khoa Khoa Tổ hợp các công nghệ  External virtual circuit, internal virtual circuit  Đường dành riêng thông qua mạng  External virtual circuit, internal datagram  Mạng xử lý mỗi gói riêng biệt  Mạng lưu trữ các gói tại node đích để sắp xếp lại thứ tự  External datagram, internal datagram  Các gói được đối xử một cách độc lập bởi cả mạng và trạm  External datagram, internal virtual circuit  Không được sử dụng Bộ môn Kỹ thuật máy tính Khoa Khoa Nội dung  Giới thiệu mạng chuyển mạch gói  Tìm đường  X.25 Bộ môn Kỹ thuật máy tính Khoa Khoa Tìm đường trong Circuit switching  Mạng chuyển mạch công cộng có cấu trúc cây  Đường đi tĩnh (không thay đổi theo thời gian)  Có thể cải tiến bằng Alternate routing  Thêm các đường kết nối giữa các trung tâm chuyển mạch  Liệt kê các đường đi có thể  Đường đi được chọn theo độ ưu tiên (tốc độ, chi phí, thời điểm...) Bộ môn Kỹ thuật máy tính Khoa Khoa Tìm đường trong Packet switching  Phức tạp, rất quan trọng  Các đặc tính yêu cầu  Chính xác (correctness)  Đơn giản (simplicity)  Mạnh mẽ (robustness)  Ổn định (stability)  Công bằng (fairness)  Tối ưu (optimality)  Hiệu quả (efficiency) Bộ môn Kỹ thuật máy tính Khoa Khoa Tiêu chuẩn đo tính hiểu quả  Được dùng đánh giá đường đi tốt  Số chặng đường (hop) là tối thiểu  Đơn giản  Không chính xác  Chi phí (cost) tối thiểu  Các yếu tố băng thông, tải hiện tại... được lượng hóa thành chi phí  Phức tạp hơn  Chính xác hơn  Được dùng chủ yếu hiện nay Bộ môn Kỹ thuật máy tính Khoa Khoa Yếu tố quyết định chiến thuật tìm đường  Thời điểm quyết định  Mạch ảo hay theo từng gói (packet)  Nơi quyết định  Phân tán (Distributed)  Được thực hiện tại từng node  Tập trung (Centralized)  Được thực hiện tại một node chuyên biệt  Tại nguồn gởi (Source)  Được thực hiện tại node gửi Bộ môn Kỹ thuật máy tính Khoa Khoa Yếu tố quyết định chiến thuật tìm đường  Nguồn thông tin về mạng  Quyết định tìm đường thông thường (không phải luôn luôn) được dựa trên các thông tin về mạng  Tìm đường phân tán (Distributed routing)  Node sử dụng các thông tin cục bộ  Có thể thu thập thông tin từ các node kế cận  Có thể thu thập thông tin từ các node trên đường tiềm năng  Tìm đường tập trung (Central routing)  Thu thập thông tin từ tất cả các node Bộ môn Kỹ thuật máy tính Khoa Khoa Yếu tố quyết định chiến thuật tìm đường  Thời điểm cập nhật thông tin  Khi nào thông tin sẽ được cập nhật  Tìm đường cố định: không được cập nhật  Tìm đường động (adaptive): cập nhật sau một khoảng thời gian ấn định trước  Thời gian này nên lớn hay nên nhỏ ? Bộ môn Kỹ thuật máy tính Khoa Khoa Các chiến thuật tìm đường  Fixed routing  Flooding routing  Random routing  Adaptive routing Bộ môn Kỹ thuật máy tính Khoa Khoa Fixed Routing  Đường đi cố định, không thay đổi  Đường đi được xác định dùng giải thuật chi phí tối thiểu  Đường đi có thể thay đổi nếu có sự thay đổi cấu hình mạng Bộ môn Kỹ thuật máy tính Khoa Khoa Fixed routing - Hiện thực Figure 12.2 Example Packet-Switching Network 8 5 2 2 23 3 3 3 1 1 1 1 1 7 6 5 8 2 4 1 4 5 6 32 CENTRAL ROUTING DIRECTORY From Node 1 2 3 4 5 6 1 — 1 5 2 4 5 2 2 — 5 2 4 5 3 4 3 — 5 3 5 4 4 4 5 — 4 5 5 4 4 5 5 — 5 To Node 6 4 4 5 5 6 — Node 1 Directory Destination Next Node 2 2 3 4 4 4 5 4 6 4 Node 4 Directory Destination Next Node 1 2 2 2 3 5 5 5 6 5 Node 2 Directory Destination Next Node 1 1 3 3 4 4 5 4 6 4 Node 5 Directory Destination Next Node 1 4 2 4 3 3 4 4 6 6 Node 3 Directory Destination Next Node 1 5 2 5 4 5 5 5 6 5 Node 6 Directory Destination Next Node 1 5 2 5 3 5 4 5 5 5 Figure 12.3 Fixed Routing (using Figure 12.2) CENTRAL ROUTING DIRECTORY From Node 1 2 3 4 5 6 1 — 1 5 2 4 5 2 2 — 5 2 4 5 3 4 3 — 5 3 5 4 4 4 5 — 4 5 5 4 4 5 5 — 5 To Node 6 4 4 5 5 6 — Node 1 Directory Destination Next Node 2 2 3 4 4 4 5 4 6 4 Node 4 Directory Destination Next Node 1 2 2 2 3 5 5 5 6 5 Node 2 Directory Destination Next Node 1 1 3 3 4 4 5 4 6 4 Node 5 Directory Destination Next Node 1 4 2 4 3 3 4 4 6 6 Node 3 Directory Destination Next Node 1 5 2 5 4 5 5 5 6 5 Node 6 Directory Destination Next Node 1 5 2 5 3 5 4 5 5 5 Figure 12.3 Fixed Routing (using Figure 12.2) Bộ môn Kỹ thuật máy tính Khoa Khoa Flooding Routing  Không cần thông tin mạng  Node gởi các gói tới mọi node kề  Các gói nhận được sẽ được truyền trên tất cả các kết nối ngoại trừ kết nối gói đến  Cuối cùng sẽ có một số copy của gói sẽ đến đích  Gói đến đầu tiên là đi trên đường tốt nhất (a) First hop Figure 12.4 Flooding Example (hop count = 3) 1 2 4 3 5 6 (b) Second hop 1 2 4 3 5 6 (c) Third hop 1 2 4 3 5 6 (a) First hop Figure 12.4 Flooding Example (hop count = 3) 1 2 4 3 5 6 (b) Second hop 1 2 4 3 5 6 (c) Third hop 1 2 4 3 5 6 (a) First hop Figure 12.4 Flooding Example (hop count = 3) 1 2 4 3 5 6 (b) Second hop 1 2 4 3 5 6 (c) Third hop 1 2 4 3 5 6 Bộ môn Kỹ thuật máy tính Khoa Khoa Làm sao dừng việc phát tán  Mỗi gói được đánh số duy nhất  Node có thể ghi nhớ các gói đã đi qua  Loại bỏ các node đã đi qua  Gói chứa số chặng đường tối đa  Mỗi khi truyền, số chặng đường giảm đi một  Dừng phát tán khi số chặng đường bằng 0 Bộ môn Kỹ thuật máy tính Khoa Khoa  Tất cả các lộ trình đều được thử  Rất mạnh mẽ (robust)  Ít nhất sẽ có một gói đi theo lộ trình với số chặng ít nhất  Có thể được dùng để thiết lập đường mạch ảo  Tất cả các node đều nhận được packet  Thích hợp trong phát tán thông tin Đánh giá Bộ môn Kỹ thuật máy tính Khoa Khoa  Tư tưởng: dựa trên Flooding routing  Node sẽ chọn một đường liên kết ra để truyền đi các gói nhận được thay vì gửi ra tất cả các liên kết  Việc chọn lựa có thể là ngẫu nhiên hoặc xoay vòng (round robin)  Có thể chọn đường liên kết ra dựa trên việc tính toán xác suất  Đặc điểm: lộ trình tìm được thông thường không phải là đường có chi phí tối thiểu hoặc số chặng nhỏ nhất Random Routing Bộ môn Kỹ thuật máy tính Khoa Khoa  Tư tưởng: dựa trên Flooding routing  Node sẽ chọn một đường liên kết ra để truyền đi các gói nhận được thay vì gửi ra tất cả các liên kết  Việc chọn lựa có thể là ngẫu nhiên hoặc xoay vòng (round robin)  Có thể chọn đường liên kết ra dựa trên việc tính toán xác suất  Đặc điểm: lộ trình tìm được thông thường không phải là đường có chi phí tối thiểu hoặc số chặng nhỏ nhất Random Routing Bộ môn Kỹ thuật máy tính Khoa Khoa Adaptive Routing  Được sử dụng bởi hầu hết các mạng chuyển mạch gói  Quyết định tìm đường thay đổi khi các điều kiện trên mạng thay đổi  Đường kết nối hoặc node trung gian hư  Tình trạng ngẽn mạch thay đổi  Cần biết các thông tin về mạng  Quyết định tìm đường phức tạp  Tradeoff giữa chất lượng của thông tin mạng và chi phí để truyền thông tin này Bộ môn Kỹ thuật máy tính Khoa Khoa Nhận xét  Ưu điểm  Hiệu suất được cải thiện  Trợ giúp điều khiển nghẽn mạng  Hạn chế  Quyết định tìm đường phức tạp  Tăng tải Bộ môn Kỹ thuật máy tính Khoa Khoa Adaptive Routing – Phân loại  Dựa trên nguồn thông tin về mạng  Cục bộ (isolated)  Các node kề (distributed)  Tất cả các node (centralized) Bộ môn Kỹ thuật máy tính Khoa Khoa Isolated Adaptive Routing  Mỗi node trong mạng tự cập nhật bảng tìm đường của mình dựa vào các thông tin về mạng mà node đó học hỏi được  Không trao đổi thông tin tìm đường với các node khác  Một trong những phương pháp đơn giản nhất của tìm đường động  Ít dùng (không dùng thông tin có sẵn)  Phù hợp với các mạng có kích thước nhỏ và hoạt động tương đối ổn định Bộ môn Kỹ thuật máy tính Khoa Khoa Distributed adaptive Routing  Thông tin về tình trạng hiện hành của mạng sẽ được định kỳ trao đổi, cập nhật giữa các node  Sau đó thông tin này sẽ được phân bố về lại các node trong mạng hay một số node trong mạng làm nhiệm vụ tìm đường  Các node này cập nhật lại bảng routing  Phương pháp này đáp ứng được với những thay đổi trạng thái của mạng, nhưng đồng thời cũng làm tăng lưu lượng thông tin trong mạng Bộ môn Kỹ thuật máy tính Khoa Khoa Centralized adaptive routing  Thông tin về tình trạng hiện hành của mạng sẽ được định kỳ trao đổi, cập nhật giữa các node trong toàn mạng.  Sau đó thông tin này sẽ được tập trung về một máy chủ trong mạng làm nhiệm vụ routing  Đáp ứng được với những thay đổi tức thời trong mạng  Nhược điểm là thông tin routing trong toàn mạng tập trung về một máy nên khi máy này không hoạt động thì toàn mạng sẽ không hoạt động được Bộ môn Kỹ thuật máy tính Khoa Khoa Bài toán tìm đường đi ngắn nhất  Cho một đồ thị có trọng số  Tìm đường đi ngắn nhất từ một node đến các node khác Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Dijkstra  Input  Đồ thị G(V, E) trong đó V là tập đỉnh, E là tập cạnh có trọng số không âm  Đỉnh nguồn S: S 㱨 V  Output  Đường đi ngắn nhất từ đỉnh nguồn S đến tất cả các đỉnh còn lại Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Dijkstra  Ký hiệu  Di : đường đi ngắn nhất từ node nguồn S đến node i tại bước chạy hiện hành của giải thuật  M: tập các đỉnh đã xét tại bước chạy hiện hành của giải thuật  dij : trọng số trên cạnh nối từ node i đến node j  dij = 0 nếu i trùng j  dij = Eij nếu i khác j Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Dijkstra  Bước 1: khởi động  M = {S}  Di = dSI  Bước 2: cập nhật đường đi ngắn nhất  Chọn đỉnh N 㱨 V sao cho: DN = min {Di} 㱼i 㱨 V \M  M = M 㱮 {N}  Dj = min {Dj, DN + dNj } 㱼j 㱨 V\M  Bước 3: lặp lại bước 2 cho đến khi M=V  Kết quả Di sẽ là đường đi ngắn nhất từ node nguồn S đến node i Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Dijkstra  Tìm đường đi ngắn nhất từ node nguồn 1 đến tất cả các node còn lại 1 2 4 3 5 6 1 1 2 1 3 2 2 3 5 5 Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Dijkstra Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Bellman - Ford  Input  Đồ thị G(V, E) trong đó V là tập đỉnh, E là tập cạnh có trọng số  Đỉnh nguồn S: S 㱨 V  Output  Đồ thị có chu trình âm → không tồn tại đường đi ngắn nhất  Đường đi ngắn nhất từ đỉnh nguồn S đến tất cả các đỉnh còn lại Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Bellman - Ford  Ký hiệu  D(h)i : đường đi ngắn nhất từ node nguồn S đến node i có tối đa h đoạn (link).  dij: trọng số trên cạnh nối từ node i đến node j  dij = 0 nếu i trùng j  dij = Eij nếu i khác j Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Bellman – Ford  Bước 1: khởi động  D(1)N = dSN, 㱼N 㱨 V\{S}  Bước 2: cập nhật đường đi ngắn nhất  D(h+1)N = min {D(h)j + djN} 㱼j 㱨 V\{S}  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 được tìm thấy thì dừng  Kết quả D(h)N sẽ là đường đi ngắn nhất từ node nguồn S đến node N Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Bellman – Ford  Tìm đường đi ngắn nhất từ node nguồn 1 đến tất cả các node còn lại 1 2 4 3 5 6 1 1 2 1 3 2 2 3 5 5 Bộ môn Kỹ thuật máy tính Khoa Khoa Giải thuật Bellman – Ford Bộ môn Kỹ thuật máy tính Khoa Khoa Bài tập  Tìm đường ngắn nhất từ node 1 đến các node còn lại  Theo giải thuật Dijkstra  Theo giải thuật Bellman – Ford 1 2 3 4 5 6 7 1 3 4 2 1 1 2 3 3 5 4 3 Bộ môn Kỹ thuật máy tính Khoa Khoa Bài tập  Tìm đường ngắn nhất từ node 1 đến các node còn lại  Theo giải thuật Dijkstra  Theo giải thuật Bellman – Ford E G H D K J F C BA1 1 1 11 1 1 1 2 3 1 4 5 Bộ môn Kỹ thuật máy tính Khoa Khoa Đánh giá  Phụ thuộc vào thời gian xử lý của các giải thuật  Phụ thuộc vào lượng thông tin yêu cầu từ các node khác  Phụ thuộc vào việc hiện thực  Cùng hội tụ về một lời giải dưới điều kiện topology tĩnh và chi phí không thay đổi  Nếu chi phí liên kết thay đổi, các giải thuật sẽ tính lại để theo kịp sự thay đổi Bộ môn Kỹ thuật máy tính Khoa Khoa Tìm đường trong ARPANET (tự đọc)  Thế hệ đầu tiên  1969  Distributed adaptive  Dùng thời gian trễ ước tính làm tiêu chuẩn đánh giá hiệu quả  Dùng giải thuật tìm đường Bellman-Ford  Các node trao đổi thông tin (các vector thời gian trễ) với các node kề  Cập nhật bảng tìm đường dựa trên thông tin đến  Không quan tâm đến tốc độ đường truyền, chỉ quan tâm chiều dài hàng đợi tại các node  Chiều dài hàng đợi không phải là cách đo chính xác của thời gian trễ  Đáp ứng chậm với nghẽn mạch Bộ môn Kỹ thuật máy tính Khoa Khoa ARPANET – Tìm đường  Thế hệ thứ 2  1979  Dùng thời gian trễ làm tiêu chuẩn đánh giá hiệu quả  Thời gian trễ được đo trực tiếp  Dùng giải thuật tìm đường Dijkstra  Thích hợp cho mạng có tải trung bình hoặc nhẹ  Khi mạng tải nặng, có ít tương quan giữa thời gian trễ đo được và thời gian trễ gặp phải Bộ môn Kỹ thuật máy tính Khoa Khoa ARPANET – Tìm đường  Thế hệ thứ 3  1987  Việc tính toán chi phí của liên kết đã được thay đổi  Thời gian trễ trung bình được đo trong 10 giây cuối  Bình thường hóa dựa trên giá trị hiện tại và kết quả trước đó Bộ môn Kỹ thuật máy tính Khoa Khoa Nội dung  Giới thiệu mạng chuyển mạch gói  Tìm đường  X.25 Bộ môn Kỹ thuật máy tính Khoa Khoa  1976, CCITT  Giao tiếp giữa trạm và mạng chuyển mạch gói  Phổ biến trong các mạng chuyển mạch gói và chuyển mạch gói của mạng ISDN  Định nghĩa 3 lớp  Vật lý  Liên kết  Gói Mạng truyền số liệu X.25 Bộ môn Kỹ thuật máy tính Khoa Khoa Lớp vật lý  Giao tiếp giữa trạm và liên kết kết nối trạm với node mạng  DTE: thiết bị của người dùng  DCE: node mạng  Dùng đặc tả lớp vật lý X.21 (đôi khi thay thế bằng EIA-232)  Truyền dữ liệu tin cậy thông qua liên kết vật lý  Cung cấp tuần tự của các frame Bộ môn Kỹ thuật máy tính Khoa Khoa Lớp liên kết  Link Access Protocol Balanced (LAPB)  Tập con của nghi thức HDLC  Xem thêm tài liệu Bộ môn Kỹ thuật máy tính Khoa Khoa Lớp gói (packet)  External virtual circuits  Kết nối luận lý (virtual circuits) giữa các thuê bao Bộ môn Kỹ thuật máy tính Khoa Khoa Dịch vụ mạch ảo  Cho phép kết nối luận lý giữa hai trạm  Mạch ảo bên ngoài  Xác định đường đi thông qua mạng  Mạch ảo bên trong  Thường có mối quan hệ 1-1 giữa mạch ảo bên ngoài và mạch ảo bên trong  Có thể sử dụng X25 với mạng kiểu datagram  Mạch ảo bên ngoài yêu cầu kênh luận lý riêng Bộ môn Kỹ thuật máy tính Khoa Khoa Các dịch vụ mạch ảo  Virtual Call (SVC – Switched Virtual Circuit)  Virtual circuit được tạo động cho mỗi giao dịch  Permanent virtual circuit  Virtual circuit được gán trước cố định  Không cần thiết lập và xóa kết nối  Fast Select call  Dùng để truyền thông báo/lệnh nhỏ (<128 octet) trong quá trình thiết lập/xóa kết nối Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Định dạng gói Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Gói dữ liệu  Số VC (12 bits)  4 bit logical group number  + 8 bit logical channel number.  Thông thường 2 trường này được xem như một  Dùng để chỉ thị loại kết nối hoặc kênh giữa các DTE  Các loại kết nối khác nhau cho phép nhiều phiên giao dịch giữa cùng một cặp DTE  Có thể lên đến 4095 kênh luận lý trên cùng một đường giao tiếp vật lý Bộ môn Kỹ thuật máy tính Khoa Khoa X25- Gói dữ liệu  Q bit (Qualifier bit)  Không được định nghĩa trong chuẩn  Thường phân biệt các gói chứa dữ liệu (Q=0) và các gói chứa thông tin điều khiển (Q=1)  D bit  Bằng 0 khi gói này là một phần của gói bị phân mảnh  Cũng được dùng để điều khiển dòng  Khi D=0, điều khiển dòng được thực hiện cục bộ (giữa DTE và cục bộ DCE)  Khi D=1, điều khiển dòng được thực hiện giữa DTE và DTE ở xa  M bit (More bit)  Gói dữ liệu lớn được phân thành nhiều gói  Ngoại trừ gói cuối cùng, các gói sẽ có bit M bằng 1  P(R) – chỉ số nhận tuần tự  P(S) – chỉ số gởi tuần tự Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Gói điều khiển  6 nhóm:  Thiết lập kết nối  Điều khiển dòng  Giám sát  Xác nhận  Chuẩn đoán  Ngắt quãng Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Gói điều khiển  Gói thiết lập kết nối  4 loại: Call Request, Incoming Call, Call Accepted, và Call Connected  Được dùng trong giai đoạn thiết lập mạch ảo  Gói điều khiển dòng  3 loại: Receive Ready (RR), Receive Not Ready (RNR), và Reject (REJ)  Được dùng trong giai đoạn truyền dữ liệu (các gói đều chứa P(R)) Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Gói điều khiển  Gói giám sát  Bao gồm: Restart Request/Indication, Clear Request/Indication, Reset Request/Indication  Restart Request được dùng trong tình huống xấu (host crash) để xóa VC do DTE này đang giữ  Clear Request dùng để xóa VC (được chỉ ra trong VC number)  Reset Request được dùng để reset chỉ số nhận/ gởi tuần tự về 0 trong chế độ truyền dữ liệu Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Gói điều khiển  Gói xác nhận  Dùng để xác nhận các yêu cầu trước đó (cho Restart, Clear, Reset, và Interrupt)  Gói chuẩn đoán  Do mạng tạo ra cho mục đích chuẩn đoán lỗi  Gói ngắt quãng  Được truyền trong quá trình truyền dữ liệu, và không chứa chỉ số gởi/nhận tuần tự.  Các gói ngắt quãng được truyền tới DTE đích với độ ưu tiên cao hơn các gói dữ liệu Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Set và Reset  Reset  Khởi tạo lại virtual circuit  Số tuần tự được đặt bằng 0  Các gói đang quá cảnh bị mất  Tùy vào các protocol cấp cao để khôi phục lại các gói bị mất  Kích hoạt bởi việc mất các gói, sai số tuần tự, nghẽn mạch, mất internal virtual circuit  Restart  Tương đương với yêu cầu xóa tất cả các virtual circuit  E.g. mất tạm thời việc truy cập mạng Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Thủ tục thiết lập kết nối  DTEa 㱻 DCEa 㱻 PSN 㱻 DCEb 㱻 DTEb (DTEa muốn kết nối với DTEb)  DTEa nhận một virtual circuit number (VCN)  DTEa gởi gói call-request cho DTEb (chứa VCN, địa chỉ DTEa, địa chỉ DTEb)  DCEa tìm đường đi băng qua mạng PSN cho gói này đến DCEb  DCEb nhận một VCN mới và gởi gói incoming-call đến DTEb (gói chứa VCN mới và các thông tin địa chỉ nguồn/đích)  DTEb chấp nhận kết nối bằng cách gởi gói call- accepted qua DCEb để đến DCEa  DCEa nhận được gói call-accepted và gởi gói call- connected tới DTEa  Sau quá trình này, DTEa và DTEb có thể gởi các gói dữ liệu qua lại Bộ môn Kỹ thuật máy tính Khoa Khoa X.25 – Thủ tục giải phóng kết nối  DTEa 㱻 DCEa 㱻 PSN 㱻 DCEb 㱻 DTEb (DTEa muốn xóa kết nối với DTEb)  DTEa gởi gói clear-request tới DCEa  DCEa gởi gói clear-indication tới DTEb (thông qua DCEb)  DTEb gởi clear-indication tới DTEa (thông qua các DCEb và DCEa) Bộ môn Kỹ thuật máy tính Khoa Khoa Virtual Call Bộ môn Kỹ thuật máy tính Khoa Khoa X.25  Điều khiển dòng và điều khiển sai  HDLC (chương 5)  Chuỗi các gói  Chuỗi đầy đủ