Đề tài Mạng IP và vấn đề quản lý bộ đệm

MỤC LỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT LỜI NÓI ĐẦU Chương 1: TỔNG QUAN VỀ IP 1 1.1. KHÁI NIỆM IP 1 1.1.1. Đánh địa chỉ và phân phối 1 1.1.2. Giao thức Internet (IP – Internet Protocol) 2 1.1.3. Các trường tiêu đề IP 3 1.2. ĐỊA CHỈ IP 5 1.2.1. Khái niệm 5 1.2.2. Các lớp D và E 7 1.2.3. Các địa chỉ IP đặc biệt 7 1.2.4. Giao thức phân giải địa chỉ (ARP) 8 1.2.5. Giao thức phân giải địa chỉ ngược (RARP) 9 1.2.6. Phân mạng con trong IP 10 1.3. IP - MỘT HỆ THỐNG PHI KẾT NỐI 13 1.4. LƯU ĐỆM VÀ QUẢN LÝ BỘ ĐỆM TRONG IP 15 1.4.1. Lưu đệm trong các bộ định tuyến IP 15 1.4.2. Quản lý bộ đệm 15Chương 2: ĐIỀU KHIỂN LƯU LƯỢNG VÀ KỸ THUẬT HÀNG ĐỢI 17 2.1. ĐIỀU KHIỂN LƯU LƯỢNG 17 2.2. CÁC VẤN ĐỀ VỚI MẠNG IP 18 2.2.1. Hiệu năng trễ và mất mát 18 2.2.2. Các yêu cầu đa dịch vụ: những hiệu năng khác nhau 18 2.2.3. Vấn đề nhiều loại hình lưu lượng 19 2.3. NGUYÊN TẮC XẾP HÀNG 20 2.3.1. Hệ thống ký hiệu 22 2.3.2. Những mối quan hệ cơ bản 22 2.3.3. Hàng đợi M/M/1 23 2.3.4. Hàng đợi M/D/1/K 26 2.3.5. Trễ trong các hệ thống xếp hàng M/M/1 và M/D/1 27 2.4. CÁC THÔNG SỐ LƯU LƯỢNG 30 2.4.1. Các mức hoạt động lưu lượng 30 2.4.2. Thông tin định thời trong các mẫu nguồn 31 2.4.3. Thời gian giữa những lần đi đến 32 2.4.4. Đếm số lần đi đến 35 2.4.5. Các tốc độ luồng 38Chương 3: QUẢN LÝ BỘ ĐỆM TRONG IP 43 3.1. HOẠT ĐỘNG XẾP HÀNG CỦA CÁC GÓI TRONG  BỘ ĐỊNH TUYẾN IP 43 3.1.1. Những phương trình cân bằng cho lưu đệm gói: Geo/Geo/1 43 3.1.2. Phân tích tốc độ phân rã 47 3.1.3. Phân tích những phương trình cân bằng với lưu đệm gói:  phân tích xếp hàng tốc độ phụ 51 3.1.3.1. Hoạt động xếp hàng về mặt cụm 52 3.1.3.2. M/D/1 tốc độ phụ, với những ứng dụng vào voice-over-IP 55 3.1.3.3. Giải pháp tốc độ phụ cho lưu lượng nỗ lực tốt nhất 64 3.2. QUẢN LÝ BỘ ĐỆM TRONG IP 66 3.2.1. Lưu đệm theo thuật toán FIFO 66 3.2.2. Phát hiện sớm ngẫu nhiên - loại bỏ gói mang tính xác suất 67 3.2.3. Bộ đệm ảo và những thuật toán lập lịch 72 3.2.3.1. Xếp hàng theo quyền ưu tiên 72 3.2.3.2. Xếp hàng trọng số hợp lý 73 3.2.4. Phân vùng không gian bộ đệm 75 3.2.5. Phân tích bộ đệm chia sẻ 79KẾT LUẬN 85TÀI LIỆU THAM KHẢO 86 THUẬT NGỮ VÀ TỪ VIẾT TẮT ARP Address Resolution Protocol Giao thức phân giải địa chỉ ATM Asynchronous Transfer Mode Chế độ truyền tải không đồng bộ CBR Constant Bit-rate Tốc độ bit cố định DiffServ Differentiated Service Các dịch vụ phân biệt DR Decay Rate Tốc độ phân rã ER Excess Rate Tốc độ phụ EWMA Exponentially Weighted Moving Average Trung bình dịch chuyển trọng số theo hàm mũ FIFO First In First Out Vào trước ra trước FTP File Transfer Protocol Giao thức truyền tải file GAPP Geometrically Approximated Poisson Process Quá trình Poisson xấp xỉ hình học GMDP Generally Modulated Deterministic Process Quá trình quyết định điều chế chung IP Internet Protocol Giao thức Internet LAN Local Area Network Mạng cục bộ LP Loss Probability Xác suất mất mát MMDP Markov Modulated Deterministic Process Quá trình quyết định điều chế Markov MPLS Multiprotocol Label Switching Chuyển mạch nhãn đa giao thức OAM Operation Administration Maintainance Vận hành Quản lý Bảo dưỡng QoS Quality of Service Chất lượng dịch vụ RARP Reverse Address Resolution Protocol Giao thức phân giải địa chỉ ngược RED Random Early Detection Phát hiện sớm ngẫu nhiên RSVP Resource Resevation Protocol Giao thức dành trước tài nguyên TCP Transmission Control Protocol Giao thức điều khiển truyền dẫn TLL Time To Live Thời gian sống ToS Type of Service Kiểu dịch vụ UDP User Datagram Protocol Giao thức đơn vị dữ liệu người sử dụng UPC Usage Parameter Control Điều khiển thông số sử dụng VBR Variable Bit – Rate Tốc độ bit thay đổi WFQ Weighted Fair Queuing Xếp hàng trọng số hợp lý LỜI NÓI ĐẦU Sự phát triển của các giao thức Internet khởi đầu từ những năm của thập niên 70 và tiếp tục phát triển vào những năm sau đó. Ngày nay, mạng IP đã thực sự bùng nổ cả về khối lượng lưu lượng cũng như các yêu cầu về chất lượng dịch vụ như: tốc độ truyền dẫn, băng thông, truyền dẫn đa phương tiện,… Công nghệ IP là sự kết hợp hài hòa của các giao thức điều khiển mềm dẻo với phần cứng chuyển mạch ATM. Công nghệ IP đã khắc phục được nhược điểm về tốc độ xử lý chậm của các bộ định tuyến và tính phức tạp của các giao thức báo hiệu trong chuyển mạch ATM. Công nghệ IP đang là điểm tập trung nghiên cứu của các hãng viễn thông nổi tiếng trên thế giới như: Ipsilon, Toshiba, IBM, Cisco,… Tuy nhiên, với lưu lượng IP cùng sự phức tạp trong các yêu cầu mà người sử dụng đòi hỏi, thì những bộ đệm IP đơn giản lại không đủ khả năng xử lý; và cần thiết phải cung cấp được chất lượng dịch vụ như người sử dụng mong muốn, từ đó dẫn đến yêu cầu cấp thiết là phải tìm ra các giải pháp để quản lý bộ đệm IP nhằm làm tăng hiệu năng của hệ thống. Với mục đích gắn quá trình học tập và nghiên cứu để tìm hiểu một công nghệ mới tiên tiến trên cơ sở những kiến thức đã học và nghiên cứu những tài liệu mới. Em đã nhận đề tài đồ án tốt nghiệp của mình là “Mạng IP và vấn đề quản lý bộ đệm”. Đồ án của em gồm ba chương với nội dung chính như sau: Chương 1: Tổng quan về IP Chương 2: Điều khiển lưu lượng và kỹ thuật hàng đợi Chương 3: Quản lý bộ đệm trong IP Nghiên cứu đề tài đồ án em đã có dịp trình bày những hiểu biết của mình về một giải pháp tích cực giúp khắc phục các vấn đề với mạng IP. Tuy nhiên do năng lực còn hạn chế nên đồ án không tránh khỏi thiếu sót, em rất mong có được những đóng góp quý báu của thầy cô và toàn thể các bạn. Em xin chân thành cảm ơn ThS Nguyễn Thị Thanh Kỳ người đã trực tiếp hướng dẫn hoàn thành đồ án tốt nghiệp này. Em cũng xin cảm ơn các thầy cô trong học viện và các bạn đã tận tình giúp đỡ em trong quá trình học tập và nghiên cứu ở Học viện. Sinh viên Nguyễn Cao Cường Chương 1: TỔNG QUAN VỀ IP 1.1. KHÁI NIỆM IP 1.1.1. Đánh địa chỉ và phân phối Một máy tính thông tin với mạng thông qua một thiết bị giao tiếp mạng, như một card tương thích mạng. Thiết bị giao tiếp mạng có một địa chỉ vật lý duy nhất và được thiết kế để nhận dữ liệu gởi đến địa chỉ vật lý đó. Địa chỉ vật lý này được ghi vào card mạng khi nó được chế tạo. Một thiết bị như một card mạng ethernet không biết bất kỳ chi tiết nào của các lớp giao thức bên trên. Nó không biết địa chỉ IP của nó và cũng không biết một khung đến được gửi đến Telnet hay là FTP. Nó chỉ lắng nghe các khung đang tới, chờ một khung có địa chỉ là địa chỉ vật lý của chính nó, và chuyển khung đó ngược lên chồng giao thức. Sự phối hợp địa chỉ vật lý này làm việc rất tốt trên một đoạn LAN riêng biệt. Một mạng chỉ bao gồm một ít máy tính trên một môi trường liên tục có thể hoạt động mà không cần gì khác ngoài các địa chỉ vật lý. Dữ liệu có thể chuyển trực tiếp từ bộ tương thích mạng này đến bộ tương thích mạng kia mà chỉ cần sử dụng các giao thức mức thấp. Không may, trên một mạng định tuyến không thể phân phối dữ liệu bằng địa chỉ vật lý. Các thủ tục tìm ra đích đến dùng cho việc phân phối bằng địa chỉ vật lý lại không hoạt động được thông qua giao tiếp router. Cho dù chúng có thực hiện được thì việc phân phối bằng địa chỉ vật lý sẽ cồng kềnh vì địa chỉ vật lý cố định ghi vào trong thẻ mạng không cho phép chúng ta áp đặt một cấu trúc luận lý trên không gian địa chỉ. Vì thế trong mạng IP sẽ làm cho địa chỉ vật lý trở nên vô hình và thay vào đó nó tổ chức mạng theo một sơ đồ đánh địa chỉ phân cấp và luận lý. Sơ đồ đánh địa chỉ luận lý được duy trì bởi giao thức IP ở lớp Internet của mô hình phân lớp TCP/IP. Địa chỉ luận lý được gọi là địa chỉ IP. Một giao thức lớp Internet khác được gọi là Giao thức phân giải địa chỉ (ARP – Address Resolution Protocol) hình thành tập hợp một bảng ánh xạ các địa chỉ IP vào các địa chỉ vật lý. Bảng ARP này là liên kết giữa địa chỉ IP và địa chỉ vật lý. Trên một bảng định tuyến, chiến lược gửi dữ liệu trên mạng IP là như sau: Nếu địa chỉ đích trên cùng một đoạn mạng với máy tính nguồn, máy tính nguồn gửi gói trực tiếp đến đích. Địa chỉ IP được phân giải sang một địa chỉ vật lý sử dụng ARP và dữ liệu được hướng tới bộ tương thích mạng đích. Nếu địa chỉ đích trên một đoạn mạng khác với máy tính nguồn, các tiến trình sau bắt đầu: Datagram được đưa tới gateway. Gateway là một thiết bị trên đoạn mạng cục bộ mà có thể chuyển tiếp một datagram tới các đoạn mạng khác (một gateway cơ bản là một router). Địa chỉ gateway được phân giải sang địa chỉ vật lý sử dụng ARP, và dữ liệu được gửi đến bộ tương thích mạng của gateway. Datagram được định tuyến qua gateway đến một đoạn mạng mức cao hơn ở đó tiến trình được lặp lại. Nếu địa chỉ đích nằm trên đoạn mạng mới này, dữ liệu được chuyển đến đích của nó. Nếu không, datagram được gửi đến một gateway khác. Datagram đi qua chuỗi các gateway đến đoạn mạng đích, ở đó địa chỉ IP đích được ánh xạ đến một địa chỉ vật lý sử dụng ARP và dữ liệu được hướng đến bộ tương thích mạng đích. 1.1.2. Giao thức Internet (IP) Giao thức Internet (IP – Internet Protocol) cung cấp một hệ thống đánh địa chỉ có phân cấp, độc lập phần cứng và đưa ra các dịch vụ cần thiết cho việc phân phối dữ liệu trên một mạng định tuyến phức tạp. Mỗi bộ tương thích mạng trên một mạng IP có một địa chỉ IP duy nhất. Các địa chỉ IP trên mạng được tổ chức sao cho chúng ta có thể chỉ ra được vị trí của host - mạng hay mạng con nơi host cư trú - bằng cách nhìn vào địa chỉ (Hình 1.1). Ta có thể dễ dàng nhìn vào Hình 1.1 và nói: “Mọi địa chỉ bắt đầu với 192.132.134 phải ở trong toà nhà C”. Tuy nhiên, một máy tính đòi hỏi có sự phân biệt với các máy khác. Địa chỉ IP do đó được chia làm hai phần: Định danh mạng (network ID) Định danh host (host ID) Người sở hữu mạng cũng có thể đặt ra thêm một mức phân cấp địa chỉ bằng cách gán một định danh mạng con (subnet ID) để có thể đạt được nhiều phân mạng hơn. 1.1.3. Các trường tiêu đề IP Mọi datagram IP bắt đầu với một tiêu đề IP. Phần mềm TCP/IP trên máy tính nguồn tạo ra tiêu đề IP. Phần mềm TCP/IP ở đích sử dụng thông tin được gửi trong phần tiêu đề IP để xử lý datagram. Tiêu đề IP chứa một lượng thông tin lớn, bao gồm các địa chỉ IP của những máy tính nguồn và đích, chiều dài của datagram, số phiên bản IP, và các chỉ dẫn đặc biệt cho các router. Kích thước tối thiểu của một tiêu đề IP là 20 byte. Hình 1.2 cho thấy các nội dung bên trong tiêu đề IP. Bao gồm các trường Version (Phiên bản) - Trường 4 bit này xác định phiên bản của IP đang được sử dụng. Phiên bản được sử dụng là IPv4 thì kiểu giá trị nhị phân cho 4 là 0100. Tương tự, nếu phiên bản được sử dụng là IPv6 thì kiểu giá trị nhị phân cho 6 là 0110. IHL (Internet Header Length - chiều dài tiêu đề Internet) - Trường 4 bit này cho biết chiều dài của tiêu đề IP tính theo các từ 32 bit. Chiều dài tiêu đề tối thiểu là 5 từ 32 bit. Mẫu giá trị nhị phân của 5 là 0101. Type of Service (Loại dịch vụ) – IP nguồn có thể chỉ định thông tin định tuyến đặc biệt. Một số router bỏ qua trường Loại dịch vụ này. Mặc dù hiện nay với sự xuất hiện của các công nghệ chất lượng dịch vụ (QoS – Quality of Service), trường này đã được quan tâm nhiều hơn. Mục đích chính của trường 8 bit này là để phân cấp độ ưu tiên của các datagram khi đi qua các router. Hiện trường này thường chỉ được gán toàn bit giá trị 0. Total length (Chiều dài tổng cộng) - Trường 16 bit này xác định chiều dài của datagram IP tính bằng octet (1 octet = 1 byte). Chiều dài này bao gồm tiêu đề IP và vùng tải tin. Identification (Nhận dạng) - Trường 16 bit này là một số tuần tự tăng được gắn vào các thông điệp gửi từ IP nguồn. Khi một thông điệp được gửi đến lớp IP và nó quá lớn so với một datagram, IP phân đoạn thông điệp thành nhiều datagram, đặt vào datagram cùng một số nhận dạng. Số này được sử dụng ở đầu nhận để tập hợp các datagram này lại thành thông điệp ban đầu. Flags (Các cờ) - Trường Flags xác định các khả năng phân đoạn có thể. Bit đầu tiên không được sử dụng và luôn có giá trị bằng 0. Bit tiếp theo được gọi là cờ DF (Don’t Fragment). Cờ DF báo hiệu có cho phân đoạn (giá trị bằng 0) hay không (giá trị bằng 1). Bit tiếp theo là cờ MF (More Fragment), nói với đầu nhận là còn nhiều phân đoạn nữa đang đến (MF gán bằng 1) hay không còn phân đoạn nào cần truyền hoặc datagram chưa bao giờ bị phân đoạn (MF gán bằng 0). Fragment Offset (Độ dời của phân đoạn) - Trường 13 bit này là một giá trị số được gán cho mỗi phân đoạn liên tiếp nhau. IP ở đích sử dụng Fragment Offset để tái hợp các phân đoạn theo thứ tự thích hợp. Giá trị offset tìm thấy ở đây biểu diễn giá trị độ dời là các đơn vị 8 byte. Time to Live (Thời gian sống) - Trường 8 bit này xác định lượng thời gian tính theo giây hay số chặng router hop mà datagram có thể tồn tại hoặc đi qua trước khi bị huỷ. Mỗi router khảo sát và làm giảm trường này ít nhất là 1, hoặc số giây mà datagram bị trì hoãn bên trong router. Datagram bị huỷ khi trường này đạt giá trị bằng 0. Mỗi chặng (hop) hay mỗi chặng router (router hop) tương quan với một router mà một datagram đi qua trên đường đến đích của nó. Nếu một datagram đi qua 5 router trước khi đến đích của nó, thì được coi là cách 5 chặng (hop) hay 5 chặng router (router hop). Protocol (Giao thức) - Trường giao thức 8 bit xác định giao thức sẽ nhận phần tải tin của datagram. Ví dụ một datagram với nhận dạng giao thức là 6 (00000110) được chuyển ngược lên chồng giao thức đến module TCP. Sau đây là một số giá trị giao thức thông dụng: Tên giao thức Nhận dạng giao thức ICMP 1 TCP 6 UDP 17 Header Checksum (Kiểm tra lỗi tiêu đề) - Trường này giữ một giá trị 16 bit được tính toán để kiểm tra tính hợp lệ của riêng phần tiêu đề. Trường này được tính toán lại ở mỗi router khi giảm trường TTL (Time to Live). Source IP Address (Địa chỉ IP nguồn) - Trường 32 bit này giữ địa chỉ nguồn của datagram. Destination IP Address (Địa chỉ IP đích) - Trường 32 bit này giữ địa chỉ đích của datagram. IP Options (Các tuỳ chọn IP) - Trường này hỗ trợ một số thiết lập tiêu đề tuỳ ý sử dụng cho việc kiểm tra, gỡ rối và an toàn. Các tuỳ chọn bao gồm Strict Source Route (một đường đi riêng qua một số router nhất định mà datagram phải theo), Internet Timestamp (một mẫu tin các nhãn thời gian ở mỗi router) và các giới hạn an toàn. Padding (Đệm) - Trường các tuỳ chọn IP có chiều dài không cố định. Trường Padding cung cấp các bit 0 bổ sung để chiều dài tổng cộng của phần tiêu đề là bội số chính xác của 32 bit. (Phần tiêu đề phải kết thúc sau một từ 32 bit bởi vì trường IHL đo chiều dài phần tiêu đề theo các bội số của 32 bit). IP Data Payload - Trường này chứa dữ liệu dự định giao đến TCP hoặc UDP, ICMP hay IGMP. Lượng dữ liệu có thể biến thiên đến hàng ngàn byte. 1.2. ĐỊA CHỈ IP 1.2.1. Khái niệm Một địa chỉ IP là một địa chỉ nhị phân 32 bit. Địa chỉ 32 bit này được phân chia thành 4 đoạn 8 bit được gọi là các octet. Con người không thoải mái khi làm việc với các địa chỉ nhị phân 32 bit hay ngay cả các octet nhị phân 8 bit, vì thế địa chỉ IP hầu như luôn luôn được biểu diễn dưới dạng chấm thập phân. Dưới dạng chấm thập phân, mỗi octet được gán một số thập phân tương ứng. 4 giá trị thập phân (4 × 8 = 32 bit) sau đó được phân biệt bằng các dấu chấm. 8 bit nhị phân có thể đại diện cho bất kỳ số nguyên nào từ 0 đến 255. Một địa chỉ IP chấm thập phân có dạng: 209.121.131.14. Một phần của địa chỉ IP được sử dụng cho định danh mạng, và một phần của địa chỉ được sử dụng cho định danh host. Sự phức tạp của địa chỉ IP là phần định danh mạng biến đổi. Hầu hết các địa chỉ rơi vào các lớp địa chỉ sau: Các địa chỉ lớp A – 8 bit đầu tiên được sử dụng cho định danh mạng. 24 bit cuối cùng được sử dụng cho định danh host. Các địa chỉ lớp B – 16 bit đầu tiên được sử dụng cho định danh mạng. 16 bit cuối cùng được sử dụng cho định danh host. Các địa chỉ lớp C – 24 bit đầu tiên được sử dụng cho định danh mạng. 8 bit cuối cùng được sử dụng cho định danh host. Càng nhiều bit thì số tổ hợp bit sẽ lớn hơn. Ta có thể thấy, định dạng lớp A cung cấp một số lượng nhỏ các định danh mạng và một số lượng lớn các định danh host cho mỗi mạng. Một mạng lớp A có thể hỗ trợ khoảng 224, hay 16777216 host. Ngược lại, một mạng lớp C chỉ có thể cung cấp số định danh host hay số lượng host ít (khoảng 28, hay 256), nhưng nhiều định dạng mạng. Bạn có thể ngạc nhiên làm thế nào một máy tính hay một router biết một địa chỉ IP là địa chỉ lớp A, lớp B hay lớp C. Các nhà thiết kế mạng IP đã đưa ra các luật địa chỉ sao cho có thể nhận biết được lớp của một địa chỉ IP. Một vài bit đầu của địa chỉ nhị phân sẽ cho biết địa chỉ này là một địa chỉ lớp A, lớp B hay lớp C (xem Bảng 1.1). Các luật để nhận dạng địa chỉ như sau: Nếu địa chỉ nhị phân 32 bit bắt đầu với một bit 0, địa chỉ là của lớp A. Nếu địa chỉ nhị phân 32 bit bắt đầu với các bit 10, địa chỉ là của lớp B. Nếu địa chỉ nhị phân 32 bit bắt đầu với các bit 110, địa chỉ là của lớp C Sơ đồ địa chỉ này dễ dàng chuyển sang ký hiệu chấm thập phân bởi vì các luật này có ảnh hưởng đến giới hạn dãy các giá trị địa chỉ cho số hạng đầu tiên trong định dạng dấu chấm thập phân. Ví dụ, vì một địa chỉ lớp A phải có một bit 0 ở tận cùng bên trái trong octet đầu tiên, số hạng đầu tiên trong một địa chỉ chấm thập phân lớp A không thể cao hơn 127. Bảng 1.1 cho thấy các dãy địa chỉ cho các mạng lớp A, B và C. Chú ý rằng một vài dãy địa chỉ IP được sử dụng cho các mục đích đặc biệt. Chúng ta sẽ xem xét nhiều hơn về các địa chỉ IP đặc biệt trong phần sau. 1.2.2. Các lớp D và E Hầu hết các truyền thông trong mạng IP đều là host-to-host (gửi từ một máy tính nguồn đến một máy tính đích) hay quảng bá (broadcast - gửi đến tất cả máy tính trên đoạn mạng hay mạng. Mặt khác, các địa chỉ lớp D được sử dụng cho truyền thông đa hướng (multicast). Một multicast là một thông điệp đơn gửi đến một mạng con của mạng. 4 bit đầu tiên bên trái của một địa chỉ mạng lớp D luôn bắt đầu với dạng nhị phân 1110, tương ứng với các số thập phân từ 224 đến 239. Các mạng lớp E được xem là các mạng thử nghiệm. Thông thường chúng không được dùng trong bất kỳ môi trường sản xuất nào. 5 bit bên trái đầu tiên của mạng lớp E luôn bắt đầu với mẫu nhị phân 11110, tương ứng với các số thập phân từ 240 đến 247. 1.2.3. Các địa chỉ IP đặc biệt Một số địa chỉ IP có ý nghĩa đặc biệt không được gán cho các host riêng biệt. Một định danh host với tất cả các bit bằng 0 nói đến chính mạng đang xét (chuyển đến chính nó). Ví dụ, địa chỉ IP 129.152.0.0 chỉ đến mạng lớp B với định danh mạng là 129.152. Một định danh với tất cả các bit bằng 1 biểu thị một địa chỉ quảng bá – broadcast. Một broadcast là một thông điệp được gửi đến tất cả các host trên mạng. Địa chỉ IP 129.152.255.255 là địa chỉ broadcast của mạng lớp B với định danh mạng 129.152. Địa chỉ 255.255.255.255 cũng có thể được sử dụng để broadcast trên toàn mạng. Các địa chỉ bắt đầu với 127 là các địa chỉ loopback. Một thông điệp được đánh địa chỉ loopback được gửi bởi phần mềm TCP/IP cục bộ đến chính nó. Địa chỉ loopback được dùng để kiểm tra xem phần mềm TCP/IP có hoạt động không. Địa chỉ loopback 127.0.0.1 thường được sử dụng nhất. Người ta cũng dành riêng một vài dãy địa chỉ IP cho các mạng riêng. Với giả định là các dãy địa chỉ riêng này không được kết nối vào Internet, vì thế các địa chỉ này không là duy nhất. Trên thế giới hiện nay, các dãy địa chỉ ẩn này thường được sử dụng cho mạng bảo vệ, nằm sau các thiết bị chuyển đổi mạng: 10.0.0.0 đến 10.255.255.255 172.16.0.0 đến 172.31.255.255 192.168.0.0 đến 192.168.255.255 Bởi vì các dãy địa chỉ riêng này tách biệt với phần địa chỉ còn lại, toàn bộ dãy địa chỉ này có thể được sử dụng trong bất cứ mạng nào mà không sợ trùng lặp địa chỉ giữa các mạng. Một nhà quản lý mạng sử dụng các địa chỉ riêng này sẽ có nhiều không gian địa chỉ để phân chia mạng con hơn, và nhiều địa chỉ có thể gán hơn. 1.2.4. Giao thức phân giải địa chỉ (ARP) Như đã biết ở phần trước, các máy tính trên một mạng cục bộ sử dụng giao thức lớp Internet được gọi là Giao thức phân giải địa chỉ (ARP – Address Resolution Protocol) để ánh xạ các địa chỉ IP vào các địa chỉ vật lý. Một host phải biết địa chỉ vật lý của bộ tương thích mạng đích để gửi bất kỳ dữ liệu nào đến nó. Vì lý do này, ARP là một giao thức rất quan trọng. Tuy nhiên, các mạng IP thực hiện theo cách thức sao cho ARP và tất cả các chi tiết của việc chuyển đổi địa chỉ hầu như vô hình đối với người sử dụng. Bộ tương thích mạng được xác định bởi địa chỉ IP của nó. Địa chỉ IP phải được ánh xạ đến một địa chỉ vật lý để một thông điệp đến đích của nó. Mỗi host trên một đoạn mạng duy trì một bảng trong bộ nhớ được gọi là Bảng ARP hay bộ nhớ nhanh ARP (ARP Cache). ARP liên kết các địa chỉ IP của các host khác trên đoạn mạng với các địa chỉ vật lý (Hình 1.3). Khi một host cần gửi dữ liệu đến một host khác trên đoạn, host kiểm tra bảng ARP để xác định địa chỉ vật lý của nơi nhận. Bảng ARP được hình thành một cách tự động. Nếu địa chỉ nhận dữ liệu hiện không được liệt kê trong bảng ARP, host gửi một broadcast được gọi là một khung yêu cầu ARP. Khung yêu cầu ARP chưa được phân giải. Khung yêu cầu ARP cũng chứa địa chỉ IP và địa chỉ vật lý của host gửi yêu cầu. Các host khác trên đoạn mạng nhận yêu cầu ARP, và host có địa chỉ IP chưa phân giải hồi đáp bằng cách gửi địa chỉ vật lý của nó đến host gửi yêu cầu. Ánh xạ địa chỉ IP và địa chỉ vật lý được thêm vào bảng ARP của host yêu cầu. Thông thường, các mục trong bảng ARP sẽ hết hạn sau một khoảng thời gian định trước. Khi thời gian sống của một mục ARP kết thúc, mục đó sẽ bị loại bỏ khỏi bảng. Tiến trình phân giải bắt đầu lại ở thời điểm kế khi mà host cần gửi dữ liệu đến địa chỉ IP của mục đã bị loại bỏ. 1.2.5. Giao thức phân giải địa chỉ ngược (RARP) RARP là viết tắt của Reverse ARP (Giao thức phân giải địa chỉ ngược). RARP trái ngược với ARP. ARP được sử dụng khi biết địa chỉ IP nhưng không biết địa chỉ vật lý. RARP thì được sử dụng khi biết địa chỉ vật lý nhưng không biết địa chỉ IP. RARP thường được sử dụng kết hợp với giao thức BOOTP để khởi động các trạm làm việc không có ổ đĩa. BOOTP (Boot PROM) - Nhiều bộ tương thích mạng có một khe cắm trống để thêm một mạng tích hợp được gọi là một Rom boot. Chương trình BootPROM bắt đầu ngay khi máy tính được bật nguồn. Nó tải một hệ điều hành vào máy tính bằng cách đọc từ một máy chủ mạng thay vì một ổ đĩa cục bộ. Hệ điều hành được tải tới thiết bị BOOTP được cấu hình trước một địa chỉ IP cụ thể. 1.2.6. Phân mạng con trong IP Hệ thống lớp địa chỉ được mô tả ở trên cho phép tất cả các host có thể xác định định danh mạng trong một địa chỉ IP và gửi một datagram đến đúng mạng. Tuy nhiên, việc xác định một đoạn mạng bằng định danh mạng lớp A, B hay C của nó có một số giới hạn. Giới hạn chính của hệ thống lớp địa chỉ là nó không cung cấp bất kỳ một sự phân chia luận lý nào cho vùng không gian địa chỉ dưới mức mạng. Hình 1.4 cho thấy một mạng lớp A. Như đã mô tả ở phần trước, các datagram đến chính xác gateway và truyền vào không gian địa chỉ 99.0.0.0. Tuy nhiên, vấn đề sẽ trở nên phức tạp hơn khi chúng ta xem xét làm thế nào để phân phối datagram khi nó đi vào không gian địa chỉ 99.0.0.0. Một mạng lớp A có phạm vi trên 16 triệu định danh host. Mạng này có thể bao gồm hàng triệu host, đường đi – đây là một con số rất lớn trong phạm vi một mạng con đơn lẻ. Để phân phối hiệu quả trên một mạng lớn, không gian địa chỉ có thể được phân nhỏ thành các đoạn mạng nhỏ hơn (Hình 1.5). Việc phân đoạn thành các mạng vật lý riêng biệt làm tăng dung lượng toàn bộ của mạng và do đó làm cho mạng có thể sử dụng phần không gian địa chỉ nhiều hơn. Trong trường hợp thông thường, các router phân tách các đoạn trong không gian địa chỉ cần một số chỉ định về nơi phân phối dữ liệu. Chúng không thể dùng định danh mạng vì mỗi datagram gửi đến có cùng định danh mạng (99.0.0.0). Mặc dù có thể tổ chức không gian địa chỉ bằng định danh host, nhưng một giải pháp như vậy sẽ rất cồng kềnh, không mềm dẻo và hoàn toàn không thực tế trên một mạng với 16 triệu host. Giải pháp thực tế duy nhất là phân chia không gian địa chỉ nào đó bên dưới mức định danh mạng để các host và các router có thể dựa trên địa chỉ IP để cho biết đoạn mạng nào có thể nhận phân phối. Các công nghệ trong mạng IP cung cấp một cấp tổ chức luận lý thứ hai bên dưới định danh mạng thông qua một khái niệm được gọi là subnet. Một subnet (mạng con) là một phân chia luận lý không gian địa chỉ mạng. Các router có thể phân phối một datagram đến một địa chỉ subnet trong mạng (thường tương ứng với một đoạn mạng), và một khi datagram đến subnet, nó có thể được phân giải thành một địa chỉ vật lý sử dụng ARP. Vậy địa chỉ subnet này từ đâu, vì tất cả 32 bit của địa chỉ IP được sử dụng cho định danh mạng và định danh host. Câu trả lời là các nhà thiết kế mạng IP cung cấp một phương tiện để mượn một số bit từ định danh host để tạo ra một địa chỉ subnet. Một thông số được gọi là mặt nạ mạng con (subnet mask) cho biết bao nhiêu bit được sử dụng cho định danh subnet và bao nhiêu còn lại cho định danh host thật sự. Giống một địa chỉ IP, một subnet mask là một số nhị phân 32 bit. Các bit của subnet mask được sắp xếp theo một dạng thức cho biết định danh subnet của địa chỉ IP mà mặt nạ này kết hợp. Hình 1.6 cho thấy một cặp địa chỉ IP/subnet mask. Mỗi vị trí bit trong subnet mask đại diện cho một vị trí bit trong địa chỉ IP. Subnet mask sử dụng một bit 1 cho mỗi bit trong địa chỉ IP thuộc định danh mạng và định danh subnet. Subnet mask sử dụng một bit 0 để chỉ định bất kỳ bit nào trong địa chỉ IP thuộc định danh host. Như vậy, có thể xem xét subnet như một bản đồ sử dụng để đọc địa chỉ IP. Hình 1.7 cho thấy sự phân phối các bit địa chỉ trong một mạng được phân mạng con so với một mạng không được phân mạng con. Các bảng định tuyến sử dụng trong các router và các host trên một mạng phân mạng con sẽ chứa thông tin về subnet mask cùng với mỗi địa chỉ IP. Như Hình 1.8 cho thấy, một datagram đang tới được định tuyến đến mạng sử dụng trường định danh mạng xác định bởi lớp địa chỉ. Khi datagram đến mạng này, nó được định tuyến đến phân mạng thích hợp sử dụng định danh subnet. Sau khi đến phân đoạn, định danh host được sử dụng để phân phối datagram đến đúng máy tính. 1.3. IP - MỘT HỆ THỐNG PHI KẾT NỐI Nghiên cứu về lưu lượng Internet cho thấy rằng đa số các luồng là rất ngắn, chỉ bao gồm một vài gói, cho dù phần lớn các gói đều thuộc về một số ít luồng (kích thước luồng dài hơn). Do đó, hầu hết trong các luồng, phần mào đầu của tín hiệu có thể vượt quá phần thông tin người sử dụng được gửi. IP xử lý điều này một cách linh hoạt: nó cung cấp một dịch vụ phi kết nối giữa những người sử dụng kết cuối bằng cách các đơn vị dữ liệu liên tiếp có thể truyền theo những đường khác nhau. Tại một bộ định tuyến, mỗi gói được xử lý độc lập liên quan tới quyết định tuyến đường (dựa trên cơ sở địa chỉ đích trong tiêu đề gói IP) cho bước nhảy kế tiếp theo hướng tới đích. Đây là ý tưởng cho sự truyền dẫn dữ liệu trên các luồng với số lượng gói nhỏ, và cũng hoạt động tốt đối với số lượng gói lớn. Vì vậy, các gói được gửi từ cùng một nguồn tới cùng một đích có thể theo nhiều đường đi khác nhau từ nguồn tới đích. Các tuyến đường trong IP có thể thích ứng nhanh chóng với tình trạng tắc nghẽn và các hỏng hóc thiết bị. Mặc dù nếu quan sát từ phía mỗi gói, dịch vụ thực sự không tin cậy, với sự truyền thông giữa những người sử dụng đầu cuối IP là rất mạnh. Có các giao thức của lớp giao vận, như giao thức điều khiển truyền dẫn (TCP), điều chỉnh sự thiếu tin cậy vốn có của gói truyền trong IP. TCP sắp xếp lại những gói không theo thứ tự, phát hiện và khôi phục lại các gói đã mất (hay trễ quá mức) qua một hệ thống các định thời, các đáp ứng và các chỉ số chuỗi. Nó cũng cung cấp một phương thức điều khiển luồng trên cơ sở tin cậy mà làm biến đổi những sự tắc nghẽn của mạng bằng cách giảm tốc độ tại thời điểm gói được gửi đi. Điều này hiệu quả với lưu lượng thích ứng, tức là lưu lượng như truyền tải thư điện tử hoặc file có thể điều chỉnh với những thay đổi rộng về độ trễ và thông lượng (như dữ liệu cuối cùng mang lại), nhưng không hiệu quả với các luồng lưu lượng, tức là lưu lượng không thích ứng. Dạng lưu lượng thứ hai này đòi hỏi ít nhất một tốc độ bit tối thiểu qua mạng cho bởi giá trị bất kỳ. Âm thoại, tại một tốc độ trung bình 64 kbit/s là một ví dụ (trừ khi có thêm một sự phức tạp khác) đây là tốc độ phải được hỗ trợ nếu không tín hiệu sẽ chịu nhiều mất mát để đáp lại sự khó hiểu (và do vậy mà vô nghĩa) của nó. Những yêu cầu cho lưu lượng không thích ứng là rất khó gặp, và không thể đảm bảo, trong một môi trường có biến động trễ, thông lượng và tắc nghẽn cao. Đây là lý do vì sao chúng thường được mang đi bằng các công nghệ hướng kết nối. Vậy, làm thế nào để một mạng IP có thể xử lý với cả hai loại hình lưu lượng, thích ứng và không thích ứng. Yêu cầu thứ nhất là phải phân vùng lưu lượng vào các nhóm để có thể đưa ra các phương pháp xử lý khác nhau thích hợp cho những đòi hỏi hiệu năng của chúng. Yêu cầu thứ hai là cung cấp các phương thức để thiết lập trạng thái cho các nhu cầu của chúng, và các phương thức để dự phòng tài nguyên riêng biệt cho các nhóm lưu lượng khác nhau đó. Kiến trúc dịch vụ tích hợp (ISA – Intergrated Services Architecture), Giao thức dự phòng tài nguyên (RSVP – Resource Reservation Protocol), Các dịch vụ phân biệt (DiffServ – Differentiated Services), và Chuyển mạch nhãn đa giao thức (MPLS – Multiprotocol Label Switching) là những phương thức khác nhau nhằm đạt được mục tiêu đó. 1.4. LƯU ĐỆM VÀ QUẢN LÝ BỘ ĐỆM TRONG IP 1.4.1. Lưu đệm trong các bộ định tuyến IP Các mạng IP chuyển dữ liệu dưới dạng những đơn vị riêng biệt. Các nút mạng, quản lý những gói IP, kết hợp các luồng lưu lượng từ những nguồn khác nhau và hướng chúng tới các đích khác nhau qua những liên kết truyền dẫn mà lưu lượng chia sẻ cho từng phần của chặng đường. Quá trình xử lý này bao hàm việc lưu trữ tạm thời dữ liệu trong những bộ đệm có kích cỡ giới hạn, kiểu đi đến thực tế của các gói gây lên những hàng đợi làm tăng và giảm bớt kích thước hàng đợi. Do vậy, trong công nghệ mạng IP, các đơn vị dữ liệu cạnh tranh dung lượng truyền dẫn đầu ra, và tạo thành các kiểu hàng đợi trong bộ đệm. Trong thực tế, các bộ đệm này có thể được đặt tại những vị trí khác nhau tuỳ theo các dịch vụ (ví dụ tại các lối vào, các lối ra hay các điểm chuyển mạch) nhưng đây không phải là điều quan trọng nhất. Thời điểm các hàng đợi được định dạng là khi số lượng gói đi đến qua một chu kỳ đã vượt quá con số khởi hành, và do đó nó là mẫu thực tế của các gói đi đến của hầu hết các thông số. Lưu đệm, khi đó, là phương thức thực tế trong IP. Tuy nhiên, những bộ đệm được cung cấp đơn giản lại không phải là một giải pháp đủ tốt; cần phải cung cấp chất lượng dịch vụ (QoS – Quality of Service) mà người sử dụng yêu cầu (và phải trả tiền). Để chắc chắn đảm bảo QoS, các bộ đệm này phải được sử dụng một cách thông minh, và những dự định này cung cấp ra Quản lý bộ đệm. 1.4.2. Quản lý bộ đệm Phương thức quản lý bộ đệm theo đặc trưng IP được thiết kế để nâng cao dung lượng của các mạng. Thực chất, những phương thức này giải quyết việc các gói tăng cường truy cập vào vùng đợi giới hạn của bộ đệm như thế nào, và khi ở trong vùng đợi thì chúng tăng cường truy cập như thế nào vào bộ phục vụ cho quá trình truyền dẫn hướng tới. Trước hết giải quyết cách thức phân vùng không gian bộ đệm, và các chính sách loại bỏ trong hoạt động. Cuối cùng là giải quyết cách thức các gói được sắp xếp và lập lịch cho quá trình phục vụ, và việc phân vùng dung lượng phục vụ. Yêu cầu then chốt là cung cấp các phân vùng, nói cách khác là các bộ đệm ảo, qua những nhóm dung lượng khác nhau có thể được truyền đi. Ở mức độ cao nhất, một bộ đệm ảo được cung cấp cho mỗi luồng IP, và nó có sự cấp phát không gian bộ đệm cùng dung lượng phục vụ của chính nó. Điều này được gọi là xếp hàng theo luồng. Điển hình, những sự xem xét về phương diện ý nghĩa thì lưu lượng, các luồng, phải được quản lý trong tổng số các bộ đệm ảo đi qua, đặc biệt là trong mạng lõi. Thuật ngữ có thể thay đổi (ví dụ, tổng hợp hoạt động trong DiffServ, đường trung kế lưu lượng trong MPLS), nhưng việc nhóm lại có xu hướng tuỳ theo loại lưu lượng, nói cách khác chúng có những yêu cầu về hiệu năng và các đặc trưng lưu lượng tương tự nhau. Các chính sách loại bỏ cung cấp biện pháp để phân biệt giữa các mức độ mất mát gói tương đối và phạm vi cũng như tác động của mất mát trong các luồng của lưu lượng tổng. Trong IP, trường kiểu dịch vụ (ToS) trong IPv4 và trường độ ưu tiên trong IPv6 có các mã chỉ ra các mức khác nhau trong cách xử lý mất mát dùng để phân biệt giữa các mức của “độ ưu tiên không gian”. Một bộ đệm ảo được cho rằng toàn các gói có độ ưu tiên thấp có thể vẫn cho phép các gói có độ ưu tiên cao hơn được truy cập. Hiệu ứng này là để gia tăng khả năng mất mát của các gói có độ ưu tiên thấp so với các gói có độ ưu tiên cao hơn. Thêm vào đó, trong IP có một phương thức loại bỏ gọi là phát hiện sớm ngẫu nhiên (RED – Random Early Detection) giải quyết trước tình trạng tắc nghẽn bằng cách loại bỏ những gói có khả năng trước khi bộ đệm đầy. Các gói bị loại bỏ với xác suất tăng lên khi kích thước hàng đợi trung bình vượt quá một ngưỡng cấu hình. Lý do cơ bản phía sau phương thức RED bắt nguồn từ thách thức đặc biệt của lưu lượng gói nỗ lực tốt nhất trải qua: TCP, trường hợp cụ thể, có thể đưa ra hoạt động không mong muốn khi mạng (hoặc một phần của nó) bị tắc nghẽn. Khi một bộ đệm đầy và phải loại bỏ các gói đi tới từ nhiều kết nối TCP, tất cả chúng sẽ truy cập các pha khởi đầu chậm của chúng. Điều này làm giảm lượng tải trọng qua bộ đệm, nhưng do nó ảnh hưởng nhiều kết nối nên dẫn đến một chu kỳ dưới sử dụng. Khi tất cả các kết nối TCP đó thoát ra khỏi khởi đầu chậm tại cùng thời điểm, thì lưu lượng sẽ bị gia tăng đáng kể, gây ra tình trạng tắc nghẽn trong bộ đệm và nhiều gói bị loại bỏ hơn. Nguyên lý bên dưới RED là nó ứng dụng cách ngăn cản một cách từ từ: trong những tầng trước của tình trạng tắc nghẽn, chỉ một vài kết nối TCP bị ảnh hưởng, và điều này có thể đủ để giảm tải và tránh được bất kỳ sự gia tăng nào được trình bày. Nếu kích cỡ hàng đợi trung bình tiếp tục tăng, thì các gói bị loại bỏ với xác suất tăng lên, và do đó có nhiều kết nối TCP bị ảnh hưởng hơn. Khi kích cỡ hàng đợi trung bình vượt quá một ngưỡng trên, tất cả các gói đi đến đều bị loại bỏ. Ngoài sự chấp nhận điều khiển cho các bộ đệm, IP còn nêu bật khả năng để điều khiển quá trình xử lý dữ liệu của các lối ra đó từ những bộ đệm – phương thức lập lịch bộ đệm. Điều này cung cấp một biện pháp để phân biệt giữa độ trễ, cũng như tốc độ bit, do đó một số cần dung lượng truyền dẫn lớn hơn. Trong IP, các bộ định tuyến có thể thực hiện việc sắp xếp độ ưu tiên thời gian (hàng đợi thứ tự) và các phương pháp như hàng đợi công bằng hoặc hàng đợi round robin, để phân vùng dung lượng dịch vụ giữa các bộ đệm ảo. Chương 2: ĐIỀU KHIỂN LƯU LƯỢNG VÀ KỸ THUẬT HÀNG ĐỢI 2.1. ĐIỀU KHIỂN LƯU LƯỢNG IP cung cấp khả năng lưu trữ tạm thời các gói trong những bộ đệm qua mạng, mô tả các biến động độ trễ, và trong từng thời điểm, là mất mát. Những bộ đệm này bao gồm các phương thức khác nhau để đảm bảo các mạng phục vụ cho những kiểu lưu lượng khác nhau - cả thích ứng và không thích ứng. Như đã lưu ý, một phần của giải pháp cho vấn đề này là sử dụng các chiến lược quản lý bộ đệm: phân vùng và dự phòng thích hợp các tài nguyên - cả không gian bộ đệm và dung lượng dịch vụ. Tuy nhiên, có những phần khác để giải quyết tất cả: điều khiển lưu lượng. Điều này cho phép những người sử dụng xác định trạng thái các nhu cầu truyền thông của họ, và đảm bảo mạng phối hợp cũng như giám sát được quá trình cung cấp tương ứng của nó. Việc thu nhận nhanh chóng một yêu cầu dự phòng (cho một luồng IP), một mạng đánh giá xem nó có thể quản lý được lưu lượng không, thêm vào những gì đã được chấp nhận trong mạng. Quá trình này phức tạp hơn so với chuyển mạch kênh, vì một số yêu cầu dự phòng sẽ đến từ các dịch vụ có tốc độ bit thay đổi (VBR – Variable bit-rate), làm cho tốc độ bit tức thời được đòi hỏi sẽ biến đổi ngẫu nhiên theo thời gian, khi thực sự sẽ có thể thay đổi dung lượng, và khả năng biến đổi dung lượng cũng biến thiên theo thời gian, thì việc quyết định luồng sẽ được chấp nhận không phải là một vấn đề đáng kể. Trong thực tế một hệ thống làm việc theo con đường sau: người sử dụng thông báo các giá trị với một số thông số mô tả hoạt động lưu lượng của luồng được yêu cầu, cũng như yêu cầu hiệu năng trễ và mất mát; mạng khi đó sử dụng các giá trị lưu lượng và hiệu năng này để đưa tới một quyết định chấp nhận/từ chối, và hồi âm cho người sử dụng. Nếu chấp nhận, mạng phải đảm bảo rằng chuỗi các gói tương ứng với các giá trị lưu lượng được thông báo. Toàn bộ quá trình này thực hiện tại tình trạng tắc nghẽn phòng ngừa trong mạng và đảm bảo rằng những yêu cầu hiệu năng được nhìn thấy cho tất cả lưu lượng được mang. Các giá trị lưu lượng và hiệu năng được đồng ý bởi người sử dụng và mạng tạo thành một hợp đồng lưu lượng. Phương thức tạo quyết định chấp nhận/từ chối là khả năng điều khiển chấp nhận, và điều này tập trung trong các bộ định tuyến IP trong mạng. Cần thiết có một phương thức để đảm bảo tuân theo hợp đồng lưu lượng, nói cách khác người sử dụng không nên vượt quá tốc độ đỉnh (hoặc có nghĩa, hoặc tốc độ) đã được đồng ý cho luồng. Phương thức này được gọi là điều khiển thông số sử dụng (UPC – Usage Parameter Control) [TK1.trang 167], và nó thực hiện đo, đánh dấu và huỷ gói. 2.2. CÁC VẤN ĐỀ VỚI MẠNG IP 2.2.1. Trễ và mất mát Trong các mạng gói, hoạt động cơ bản ảnh hưởng đến hiệu năng là hoạt động xếp hàng của các gói truyền qua các bộ đệm trong các router trên đường truyền từ nguồn đến đích qua mạng. Hoạt động xếp hàng này có nghĩa là các gói phải trải qua những biến thiên độ trễ qua một bộ đệm và, nếu độ trễ đó quá lớn, thì sẽ bị mất. Trường hợp đơn giản nhất, một bộ đệm có tốc độ phục vụ cố định, một dung lượng cho việc lưu trữ tạm thời các gói đang chờ được phục vụ, và một quy tắc phục vụ FIFO. Ngay cả trong trường hợp đơn giản này, hoạt động xếp hàng cũng tuỳ thuộc vào kiểu và hỗn hợp lưu lượng đang được ghép qua bộ đệm. 2.2.2. Các yêu cầu đa dịch vụ: đòi hỏi những hiệu năng khác nhau Một nguyên tắc FIFO không cho phép mạng đảm bảo những đòi hỏi hiệu năng khác nhau – trong IP nỗ lực tốt nhất tất cả lưu lượng đều phải trải qua độ trễ và mất mát như nhau. Giải pháp cho vấn đề này là quản lý bộ đệm, cả lối vào và lối ra – điều này bao hàm các chính sách phân vùng và chia sẻ không gian bộ đệm cũng như dung lượng phục vụ (ví dụ như xếp hàng theo luồng), các phương thức loại bỏ gói, và lập lịch hàng đợi (như xếp hàng theo quyền ưu tiên và xếp hàng trọng số hợp lý). Chia sẻ và phân vùng bộ đệm: Với xếp hàng theo luồng và xếp hàng trọng số hợp lý, mỗi bộ đệm ảo có thể được thiết lập mô hình như là có dung lượng phục vụ và không gian bộ đệm của riêng nó – do đó bất kỳ phương thức phân tích cho các hàng đợi FIFO nào cũng có thể được áp dụng, như thích hợp với bối cảnh ghép, và các nguồn lưu lượng. Điển hình, điều này sẽ đưa ra một tốc độ phân rã cho mỗi bộ đệm ảo, khi đó có thể được sử dụng, cùng với yêu cầu hiệu năng, để đánh giá quá trình phân vùng không gian bộ đệm. Việc phân vùng có một ưu điểm rõ ràng là duy trì những đảm bảo hiệu năng khác nhau với các loại hình dịch vụ phong phú đang chia sẻ một cổng lối ra. Tuy nhiên, cái giá của quá trình phân vùng là nó không tối ưu khi xem xét tình trạng mất mát tổng tại một cổng đầu ra: sự mất mát của một gói từ bộ đệm ảo đầy có thể không cần thiết nếu không gian bộ đệm được chia sẻ. Thực sự, không gian bộ đệm có thể được chia sẻ qua nhiều cổng đầu ra. Các phương thức loại bỏ gói: Trong IP, RED cung cấp một phương thức loại bỏ mang tính xác suất với mục đích là làm dịu bớt tình trạng tắc nghẽn, và ngăn ngừa nó nếu có thể – xác định các vấn đề đồng bộ toàn thể kết hợp với các kết nối TCP. RED còn sử dụng một phương thức ngưỡng làm việc kết hợp với kích cỡ hàng đợi trung bình. Các phương thức lập lịch hàng đợi: Trong IP, các phương thức lập lịch hàng đợi bao gồm việc phân vùng dung lượng phục vụ của bộ đệm đầu ra. Xếp hàng trọng số hợp lý chỉ định từng phần bộ phục vụ cụ thể cho mỗi bộ đệm ảo – để phân tích điều này, mỗi bộ đệm có thể được xem xét như một hàng đợi FIFO độc lập với một dung lượng phục vụ cố định bằng với dung lượng được chỉ định của nó. Do vậy bất kỳ phương pháp phân tích nào với các hàng đợi FIFO đều có thể được áp dụng. Xếp hàng theo quyền ưu tiên, tức là ưu tiên thời gian, yêu cầu phân tích cụ thể, bởi vì các phần dung lượng phục vụ giữa những mức ưu tiên khác nhau là không cố định. Dung lượng phục vụ dành cho các mức ưu tiên thấp sẽ phụ thuộc vào việc đã có bao nhiêu dung lượng phục vụ được sử dụng cho các lưu lượng ưu tiên cao hơn. 2.2.3. Vấn đề nhiều loại hình lưu lượng Để cung cấp những đảm bảo hiệu năng end-to-end, các hợp đồng lưu lượng phải được thiết lập, dự phòng tài nguyên, và giám sát các luồng lưu lượng để đảm bảo theo đúng hợp đồng. Tại trung tâm của những chức năng này là sự quyết định kết quả hiệu năng từ những luồng lưu lượng qua các tài nguyên mạng, tức là những định dạng phân tích xếp hàng khác nhau. Các phương thức điều khiển truy cập: Trong IP, một chức năng điều khiển truy cập phải quyết định xem một luồng mới có được truy nhập hay không. Chức năng này phải ghi chép những lời cam kết rằng mạng hiện đang hỗ trợ và các tài nguyên hợp lệ với các luồng mới bất kỳ. Để làm được điều này, cần phải hiểu kiến trúc và cấu hình của các bộ đệm (tức là các phương thức lập lịch loại bỏ và phân vùng), và tạo ra một sự quyết định thích hợp có đảm bảo hiệu năng được yêu cầu hay không. Điều này đòi hỏi phân tích xếp hàng. Các phương thức lập chính sách: Mỗi lần truy nhập, luồng các gói sẽ được giám sát (để đảm bảo theo đúng hợp đồng lưu lượng) bằng chức năng lập chính sách, thường là một gáo dấu hiệu, hoặc gáo rò [TK1.trang 172]. Trong IP, gáo dấu hiệu được tích hợp một cách đặc trưng vào trong phương thức lập lịch hàng đợi. Nó có thể được đánh giá bằng cách sử dụng những kiểu phân tích xếp hàng phong phú, để biết cách thức cấu hình các gáo thích hợp. Quá trình xác định kích thước và cấu hình: Trên phương diện thời gian dài hơn, việc dự phòng, xác định kích thước và cấu hình các tài nguyên mạng (những liên kết truyền dẫn, phân vùng bộ đệm, dung lượng chuyển mạch,…) đều cần thiết để tương thích yêu cầu mà người sử dụng mong muốn. Điều này cũng tạo ra việc sử dụng phân tích xếp hàng để quyết định xác suất nghẽn và tắc tại mức kết nối, hoặc mức kết hợp. 2.3. NGUYÊN TẮC XẾP HÀNG Những phân tích về quá trình xếp hàng là một phần cơ bản của đánh giá hiệu năng, bởi vì các hàng đợi (hay “các đường đợi”) hình thành trong các hệ thống viễn thông mỗi khi các khách hàng tranh chấp những nguồn tài nguyên giới hạn. Trong mạng IP không chỉ thực hiện tranh chấp các kết nối, và có thể tạo ra hàng đợi, mà mỗi kết nối được chấp nhận bao gồm một dòng các gói và chúng còn phải đợi tại những bộ định tuyến khi chúng đi ngang qua mạng. Chúng ta sẽ sử dụng một hàng đợi như một quá trình xử lý toán học nhanh ý tưởng của sự tranh chấp tài nguyên (Hình 2.1): các khách hàng đi đến một hệ thống xếp hàng cần một số lượng dịch vụ xác định, nếu nó không được phép ngay thì chúng sẽ đợi được phục vụ, trong một khu vực lưu giữ (được gọi là một “bộ đệm”, “hàng đợi” hay “đường đợi”); và chờ đợi một khoảng thời gian xác định, chúng được phục vụ và rời khỏi hệ thống. Chú ý rằng thuật ngữ “khách hàng” là sự mô tả chung mà chúng ta sẽ bắt gặp trong vấn đề nguyên tắc xếp hàng và nó được sử dụng để giải nghĩa “các đường đợi bất kỳ đó”; trong IP, khách hàng có thể là các gói, các cụm, các luồng hoặc các kết nối. Một hệ thống xếp hàng bất kỳ được mô tả bởi những kiểu đi đến của khách hàng, những kiểu dịch vụ của khách hàng, số lượng kênh phục vụ, và dung lượng phục vụ. Kiểu đi đến của các khách hàng là đầu vào tới một hệ thống xếp hàng và đôi khi có thể được chỉ rõ như số lượng trung bình của các gói đi đến trên một đơn vị thời gian (nghĩa là thời gian liên đi đến). Đầu vào đơn giản nhất cho hệ thống xếp hàng bất kỳ có thể có là “quyết định” (deterministic), trong kiểu đi đến là một khách hàng trên mọi t đơn vị thời gian, nói cách khác, tốc độ đi đến là 1/t. Không mất tính tổng quát, chúng ta xem xét một kích cỡ gói IP bằng với một tế bào ATM. Như vậy, với dịch vụ tốc độ bit cố định (CBR) 64 kb/s, khi đó tốc độ gói là 167 gói/s, và thời gian liên đi đến là 6 ms. Nếu kiểu đi đến là “ngẫu nhiên” (tức là nó biến đổi trong một số kiểu ngẫu nhiên theo thời gian), thì yêu cầu một quá trình mô tả sâu hơn, ví dụ sự phân bố xác suất của thời gian giữa những lần đi đến. Những lần đi đến có thể là một nhóm thay vì đơn lẻ, và kích cỡ của những nhóm này có thể biến đổi. Kiểu dịch vụ của khách hàng, như với các kiểu đi đến, có thể được mô tả như tốc độ, µ, của các khách hàng đang được phục vụ, hoặc như một thời gian, s, đòi hỏi để phục vụ một khách hàng. Có một điểm khác biệt quan trọng: thời gian phục vụ hoặc tốc độ phục vụ được đặt điều kiện trên hệ thống là không rỗng. Nếu nó rỗng, trạng thái dịch vụ được gọi là “rỗi”. Tuy nhiên, khi một bộ đệm IP rỗng, một dòng kế tiếp của khe gói rỗng được xuất phát. Do đó, sự phục vụ được đồng bộ và quyết định. Trong phân tích toán học của một bộ đệm IP, quá trình đồng bộ thường bị bỏ quên – do đó một gói được cho rằng truy cập dịch vụ ngay lập tức nhanh chóng tới truy cập vào một bộ đệm rỗng. Đối với một liên kết 155.52 Mb/s, tốc độ khe gói là 366792 gói/s và thời gian phục vụ mỗi gói là 2.726 µs. Tuy nhiên, một trong tổng số 27 khe gói được sử dụng cho vận hành và bảo dưỡng (OAM) các gói cho những nhiệm vụ hiển thị và đo đạc phong phú. Bởi vậy tốc độ khe gói có giá trị cho lưu lượng là gói/s Có thể được lấy gần đúng như một thời gian phục vụ cho mỗi gói bằng 2.831 µs. Số lượng kênh phục vụ nói đến số lượng bộ phục vụ có thể phục vụ lần lượt khách hàng. Những hệ thống đa kênh có thể khác tuỳ theo sự tổ chức của hàng đợi: mỗi bộ phục vụ có thể có hàng đợi riêng, hoặc có thể chỉ một hàng đợi cho tất cả các bộ phục vụ. Đây là trường hợp thú vị đặc biệt khi phân tích các thiết kế chuyển mạch IP khác nhau. Dung lượng hệ thống bao gồm khu vực chờ đợi và số lượng kênh phục vụ, và có thể là giới hạn hoặc vô hạn. Rõ ràng trong một hệ thống thực tế, dung lượng phải là giới hạn. Tuy nhiên giả thiết dung lượng vô hạn có thể đơn giản hoá được quá trình phân tích và vẫn có giá trị trong mô tả hoạt động xếp hàng IP. 2.3.1. Hệ thống ký hiệu Hệ thống ký hiệu Kendall, A/B/X/Y/Z được sử dụng rộng rãi để mô tả các hệ thống xếp hàng: A chỉ ra phân bố thời gian liên đi đến B chỉ ra phân bố thời gian phục vụ X chỉ ra số lượng kênh phục vụ Y chỉ ra dung lượng hệ thống, và Z chỉ ra nguyên tắc hàng đợi Một ví dụ là hàng đợi M/D/1. Ở đây “M” nói đến một quá trình không nhớ (memoryless), hay Markov [TK2.trang 28], nói cách khác là những thời gian liên đi đến với phân bố số mũ âm. “D” nghĩa là thời gian phục vụ luôn tương đương: cố định hoặc “quyết định” (từ giờ là D), và “1” nói đến phục vụ riêng lẻ. Phần Y/Z của hệ thống ký hiệu được bỏ qua khi dung lượng hệ thống bị hạn chế và nguyên tắc hàng đợi là vào trước-phục vụ trước 2.3.2. Những mối quan hệ cơ bản Bảng 3.1 tóm tắt hệ thống ký hiệu được sử dụng chung cho những thành phần khác nhau của tiến trình xếp hàng. Hệ thống ký hiệu này không được chuẩn hoá, vậy cần chú ý… ví dụ, q có thể được sử dụng, hoặc theo nghĩa là số lượng khách hàng trung bình của hệ thống, hoặc là số lượng khách hàng trung bình chờ đợi phục vụ (trừ các trạng thái khác, chúng ta sẽ sử dụng nó theo nghĩa là số lượng khách hàng trung bình trong hệ thống). Thực tế có một số mối quan hệ xếp hàng cơ bản, giả thiết rằng dung lượng hệ thống là “vô hạn”, nhưng không quan tâm tới những kiểu đi đến hay kiểu phục vụ và số lượng kênh hay nguyên tắc hàng đợi. Độ sử dụng, r, là kết quả của tốc độ đi đến có nghĩa và thời gian phục vụ trung bình, tức là r = l. s cho một hàng đợi với bộ phục vụ đơn lẻ. Với 1000 nguồn CBR 64 kb/s, tốc độ đi đến là 166 667 gói/s. Chúng ta đã tính toán được rằng thời gian phục vụ của một gói là 2.831 µs, vậy độ sử dụng, r, là 0.472. Số lượng khách hàng trung bình trong hàng đợi được liên hệ với thời gian trung bình bỏ ra để chờ đợi trong hàng đợi theo một công thức được gọi là công thức của Little (thường viết tắt là L = l.W ) [TK2.trang 43]. Trong bảng ký hiệu của chúng ta, đây là Vậy, nếu thời gian chờ trung bình là 50 µs, thì chiều dài hàng đợi trung bình là 8.333 gói. Quan hệ này cũng áp dụng cho số lượng khách hàng trung bình trong hệ thống Thời gian trung bình trong hệ thống đơn giản bằng tổng của thời gian phục vụ trung bình và thời gian chờ trung bình, tức là Trong thí dụ này, đưa ra một giá trị là 52.831 µs. Số lượng khách hàng trung bình trong một hệ thống bộ phục vụ đơn lẻ được tính bằng đưa ra một giá trị là 8.805 gói. 2.3.3. Hàng đợi M/M/1 Chúng ta có thể tiếp tục với ví dụ của N nguồn CBR cung cấp một bộ đệm IP bằng cách tạo ra hai giả định, nhưng ví dụ ít nhất sẽ đưa ra cho chúng ta một bối cảnh để lựa chọn những giá trị thông số biến đổi. Giả định thứ nhất là kiểu đi đến của gói từ N nguồn CBR có thể được lấy gần đúng bằng những thời gian liên đi đến với số mũ âm. Điều này cũng tương tự khi nói rằng những lần đi đến được mô tả bởi quá trình Poisson [TK2.trang 20]. Quá trình này đã nhìn vào kiểu đi đến từ một bối cảnh khác. Thay vì chỉ rõ một khoảng thời gian, phân bố Poisson đếm số lần đi đến trong một khoảng thời gian. Giả định thứ hai là những thời gian phục vụ của các gói này được mô tả bằng một phân bố số mũ âm. Trong mạng IP với những gói có độ dài không cố định, chúng ta có thể sử dụng ví dụ này để minh hoạ một số điểm quan trọng về các hệ thống xếp hàng. Như vậy, chúng ta nên tạo ra bộ đệm IP lớn như thế nào. Nhớ lại rằng hệ thống xếp hàng M/M/1 giả thiết không gian bộ đệm là vô hạn, nhưng chúng ta có thể có một số ý tưởng bằng cách xem xét số lượng gói trung bình trong hệ thống, được tính bằng Trong ví dụ của chúng ta, kết quả độ sử dụng từ 1000 nguồn CBR là 0.472 đưa ra một kích cỡ hệ thống trung bình là 0.894 gói. Trừ đi độ sử dụng từ đây cho ta không gian đợi trung bình được sử dụng, 0.422 gói. Đây không phải là kết quả quá hữu ích cho việc xác định kích thước của một bộ đệm IP; chúng ta sẽ mong muốn cung cấp không gian chờ vượt quá tối thiểu một gói. Nhưng nếu chúng ta nhìn vào đồ thị (Hình 2.2) của q và r, khi r biến thiên từ 0 đến 1, thì chúng ta có thể vẽ một kết quả rất hữu ích. Đặc trưng then chốt là đoạn uốn cong quanh độ sử dụng 80% đến 90%, đưa ra rằng tốt nhất là vận hành hệ thống dưới 80% (độ sử dụng) để ngăn ngừa những hàng đợi rộng lên. Nhưng chúng ta vẫn chưa có bất kỳ ý tưởng gì về độ rộng của bộ đệm IP. Bước kế tiếp là xem xét sự phân bố của kích cỡ hệ thống như được tính: Pr{kích cỡ hệ thống = x} = (1 – r).rx Hình 2.3 chỉ ra phân bố này cho một phạm vi các giá trị độ sử dụng khác nhau, bao gồm giá trị 0.472 trong ví dụ riêng của chúng ta. Trong trường hợp này chúng ta có thể đọc ra từ đồ thị xác suất được liên kết với một kích cỡ hệ thống 10 gói là 0.0003. Từ đây chúng ta có thể kết luận rằng một độ dài bộ đệm 10 gói sẽ không đủ để đạt được những yêu cầu xác suất mất gói của IP ở mức 10-8. Cho xác suất kích cỡ hệ thống xuống dưới 10-8, kích cỡ hệ thống cần thiết là 24 gói; xác suất thực sự là 7.89 × 10-9. Trong quá trình đưa ra sự diễn dịch này, chúng ta đã tính gần đúng xác suất mất gói bằng xác suất để bộ đệm đạt đến một giới hạn đặc biệt trong kiểu bộ đệm vô hạn của chúng ta. Điều này giả thiết rằng một mẫu bộ đệm vô hạn là một kiểu thích hợp của bộ đệm giới hạn, và Pr{kích cỡ hệ thống = x) là một xấp xỉ hợp lý cho sự mất mát từ một hàng đợi giới hạn có kích cỡ x. Trước khi rời khỏi M/M/1, chúng ta nhìn vào một sự xấp xỉ khác cho tính tổng các xác suất có thể xảy ra cho đến và bao gồm giá trị x, và khi đó lấy 1 trừ đi tổng này (đây là công việc đơn giản hơn so với tính tổng từ x +1 đến ∞). Phương trình cho nó rất đơn giản Pr{kích cỡ hệ thống > x} = rx + 1 Khi x = 24, và r = 0.472, phương trình này sẽ đưa ra kết quả 7.06 × 10-9 rất gần với ước lượng trước đó. Bây giờ nhìn Hình 2.4 so sánh kết quả hai phương pháp xấp xỉ. Pr{kích cỡ hệ thống = x} và Pr{kích cỡ hệ thống ≥ x}, với xác suất mất mát thực tế từ hệ thống M/M/1/K, cho kích cỡ hệ thống là 24 gói, với độ sử dụng biến thiên từ 0 đến 1. Cái chúng ta tìm thấy là tất cả ba phương pháp đưa ra những kết quả giống nhau theo hầu hết các giá trị độ sử dụng là 47.2% (0.472), thì sự khác nhau thực tế là rất ít. Điểm chính cần chú ý ở đây là một hàng đợi vô hạn có thể cung cấp một phương pháp lấy xấp xỉ hiệu quả cho một hàng đợi giới hạn. 2.3.4. Hàng đợi M/D/1/K Vậy bây giờ để chỉnh sửa giả định thứ hai, về những thời gian phục vụ, và thay vì được mô tả bởi một phân bố số mũ âm, chúng ta sẽ xây dựng mô hình các gói. Giả thiết duy nhất chúng ta sẽ đưa ra bây giờ là chúng truy nhập dịch vụ bất cứ khi nào bộ phục vụ rỗi, tốt hơn là chờ đến khe gói tiếp theo. Giả định đầu tiên, về những thời gian đi đến, giữ tương tự như trước. Chúng ta sẽ xử lý trực tiếp với một hàng đợi giới hạn, hơn là coi gần đúng nó như một hàng đợi vô hạn. Điều này, khi đó, được gọi là hệ thống xếp hàng M/D/1/K. Hình 2.5 so sánh độ mất mát gói từ M/D/1/K với ước lượng xác suất mất gói M/M/1, Pr{kích cỡ hệ thống = x}, khi kích cỡ hệ thống là 10. Như trước, phạm vi của độ sử dụng là từ 0 đến 1. Tại độ sử dụng thích hợp, 0.472, sự khác biệt giữa kết quả mất gói là về hai sự sắp xếp mức độ quan trọng. Như vậy chúng ta cần nhớ rằng “những câu trả lời” đánh giá hiệu năng có thể nhạy cảm hơn để lựa chọn mẫu, và biện pháp chúng ta sẽ luôn luôn, với một số phạm vi, mở ra thảo luận. Với xác suất mất gói trong M/D/1/K nhỏ hơn 10-8, kích cỡ hệ thống cần phải ít nhất là 15 gói, và xác suất mất gói thực tế (nếu là 15 gói) bằng 4.34 × 10-9. Vậy, bằng cách sử dụng mẫu hệ thống chính xác hơn (so với M/M/1), chúng ta có thể tiết kiệm được không gian bộ nhớ thiết kế, hoặc như một sự lựa chọn, nếu chúng ta sử dụng một kích cỡ hệ thống là 24 gói, thì độ sử dụng có thể được tăng lên 66.8%, chính xác hơn so với 47.3%. Sự gia tăng này tương ứng với thêm lần lượt là 415 kết nối CBR 64 kb/s. Nó cũng có một chú ý không được tốt trong Hình 2.5 là các xác suất mất gói rất gần nhau khi độ sử dụng cao, có nghĩa là sự khác biệt giữa hai kiểu, với những giả thiết thời gian phục vụ rất khác nhau của chúng trở nên hầu như không đáng kể dưới những điều kiện lưu lượng nghiêm ngặt. 2.3.5. Trễ trong các hệ thống xếp hàng M/M/1 và M/D/1 IP nêu bật cả mất mát gói và trễ gói như những phép đo hiệu năng then chốt, và cho đến nay chúng ta chỉ xem xét được mất mát. Tuy nhiên, độ trễ quan trọng đặc biệt cho các dịch vụ thời gian thực, ví dụ như thoại và video. Kết quả của Little cho phép chúng ta tính toán thời gian chờ trung bình từ số lượng trung bình đang chờ trong hàng đợi và tốc độ đi đến. Nếu chúng ta ứng dụng phân tích này cho ví dụ với 1000 kết nối CBR được ghép cùng nhau, chúng ta sẽ đạt được: Thời gian trung bình trong hệ thống là tq = tw + s = 2.532 + 2.831 = 5.363 µs Cách khác để đạt được cùng kết quả là sử dụng công thức thời gian chờ đợi cho hàng đợi M/M/1. Đó là tw = Với hàng đợi M/D/1, có một công thức thời gian chờ tương tự tw = Trong cả hai trường hợp chúng ta đều cần cộng thêm thời gian phục vụ (thời gian truyền dẫn gói) để đạt được độ trễ tổng qua hệ thống. Nhưng điều chỉnh cần chú ý là thời gian chờ trung bình trong hàng đợi M/D/1 (làm việc ngoài như 1.265 µs trong ví dụ của chúng ta) là bằng “một nửa” của hàng đợi M/M/1. Hình 2.6 chỉ ra thời gian chờ trung bình theo độ sử dụng cho cả hai kiểu hàng đợi. Đường thẳng chỉ ra thời gian phục vụ trung bình. Chú ý cách thức nó vượt độ trễ với độ sử dụng 60%. Chúng ta có thể giữ như một “quy luật lật trang sách” hữu ích mà trễ trung bình phát sinh từ việc xếp hàng qua một mạng sẽ được tính xấp xỉ hai lần tổng của các thời gian phục vụ. Điều này giả thiết, tất nhiên, rằng độ sử dụng trong bất kỳ hàng đợi nào sẽ không lớn hơn 60%. Đối với độ trễ end-to-end cuối cùng, chúng ta phải cộng thêm thời gian nhân lên ở những liên kết truyền dẫn. Những thông số này có giá trị, nhưng nếu giữ ở một mình, thì chúng sẽ là không đầy đủ. Chúng ta nên nhớ rằng chúng là những giá trị trung bình, và các gói sẽ ảnh hưởng trễ thực sự cả lớn hơn và nhỏ hơn. Trễ là đặc biệt quan trọng khi chúng ta xem xét các đặc trưng end-to-end của các kết nối; tất cả các gói trong một kết nối sẽ phải đi qua một chuỗi bộ đệm, mỗi bộ đệm sẽ làm trễ chúng bằng một số ngẫu nhiên tuỳ số lượng gói đã ở trong bộ đệm đi đến. Điều này chắc chắn sẽ làm các gói bị trễ hơn, do đó có thể gọi là trượt trễ, hay biến động trễ. Minh hoạ bằng hình vẽ được chỉ ra ở Hình 2.7. Ở đây, chúng ta chỉ đưa ra các gói của kết nối mà chúng ta giám sát; tất nhiên cũng có lưu lượng khác được đóng góp vào bộ đệm. Gói thứ hai trải qua độ trễ ngắn hơn so với gói đầu tiên và gói thứ ba. Điều này cung cấp một kích thước nhỏ hơn giữa gói 1 và 2, và dài hơn giữa gói 2 và 3. Sự biến thiên độ trễ có thể là một vấn đề đặc biệt cho điều khiển thông số sử dụng [TK1.trang 167]. Vậy để minh hoạ, cho một ví dụ cụ thể. Nếu chúng ta lại sử dụng ví dụ CBR (1000 nguồn CBR 64 kb/s được ghép với nhau), chúng ta có thể sử dụng nhiều nguyên tắc hơn kết hợp với hàng đợi M/D/1 để dự đoán kết quả đi qua của dòng gói này qua một sự thành công của các hàng đợi tương đương, và vẽ đồ thị phân bố thời gian chờ kết quả. Các xác suất kết hợp với một gói trong luồng sẽ bị trễ x khe thời gian đã truyền qua 1, 2, 3 và 10 bộ đệm tương tự được chỉ ra trong Hình 2.8. Để đưa ra được những kết quả này, chúng ta giả thiết rằng mỗi bộ đệm là độc lập với tất cả các bộ đệm còn lại, và chúng được tải tại 0.472. Các kết quả được chỉ ra rõ ràng có xu hướng cho phân bố trễ sẽ san bằng khi số lượng các bộ đệm tăng như bạn có thể mong đợi. Nhiều bộ đệm hơn và nhiều gói đi qua hơn, thì xác suất liên kết với thời gian chờ dài và thời gian chờ ngắn có chiều hướng bằng nhau. 2.4. CÁC THÔNG SỐ LƯU LƯỢNG 2.4.1. Các mức của hoạt động lưu lượng Vậy thì loại hình hoạt động lưu lượng nào mà chúng ta sẽ quan tâm trong IP. Chúng ta có thể thấy trong một mạng IP, thời gian giữa những “gói đi đến” được đưa ra như một phân bố số mũ âm: điều đó để nói rằng, những sự đi đến đã định dạng một quá trình Poisson [TK2.trang 20]. Tuy nhiên mặc dù cùng một mẫu nguồn được sử dụng, nhưng có thể lại là các loại hoạt động khác nhau đang được sử dụng. Người ta xem xét các kiểu hoạt động khác nhau này thông qua bốn khía cạnh thời gian khác nhau của hoạt động được chỉ ra trên Hình 2.9. Calendar (lịch): những sự biến đổi hàng ngày, hàng tuần và theo mùa. Connection (kết nối): thiết lập và giải quyết những sự kiện quy định trong phạm vi khoảng thời gian kết nối, điển hình là trong khoảng 100 đến 1000 giây. Burst (cụm): hoạt động của một người sử dụng phát, điển hình như một tốc độ luồng gói, qua một khoảng thời gian giới hạn từ một phần nhỏ của giây đến một vài giây. Packet (gói): hoạt động của việc phát gói tại mức thấp nhất, liên quan đến khoảng thời gian giữa những sự đi đến. Phân tích hoạt động lưu lượng này giúp ích trong việc phân biệt những mục tiêu chủ yếu của quá trình xác định kích thước và thiết kế hiệu năng. Xác định kích thước tập trung vào việc tổ chức và cung cấp đầy đủ thiết bị trong mạng để thấy sự cần thiết trong các dịch vụ được sử dụng bởi thuê bao (tức là các mức lịch và kết nối); nó đòi hỏi hiểu biết về những đặc trưng dịch vụ, nhưng điều này là trong định dạng tổng và không cần thiết một mức độ chi tiết cao. Thiết kế hiệu năng, tuy nhiên, lại tập trung chi tiết vào các giới hạn của hiệu năng, điều này đòi hỏi quá trình xem xét chi tiết các thông số đặc trưng dịch vụ (chủ yếu tại các mức gói và cụm), cũng như thông tin về hỗn hợp dịch vụ điển hình – bao nhiêu lưu lượng thoại, video và dữ liệu đang được vận chuyển trong liên kết bất kỳ (mà sẽ đạt được từ việc nghiên cứu các dịch vụ sử dụng). Thông tin định thời trong các mẫu nguồn Một mẫu nguồn mô tả cách thức lưu lượng, hoặc các gói, các cụm hoặc các kết nối, xuất phát từ một người sử dụng. Như chúng ta đã thấy, cùng một mẫu nguồn có thể được áp dụng cho những khía cạnh thời gian khác nhau của hoạt động, nhưng quá trình Poisson không chỉ được áp dụng cho IP. Các mẫu nguồn có thể được xếp lớp theo những cách khác nhau: thời gian liên tục hoặc thời gian riêng, thời gian liên đi đến hoặc quá trình đếm, dựa trên trạng thái hoặc dựa theo phân bố. Có một điều đáng chú ý là một số mẫu được liên kết với một phương pháp xây dựng hàng đợi đặc biệt, một ví dụ đang được phân tích luồng không cố định. Một đặc trưng để phân biệt các nguồn là cách trình diễn thông tin định thời. Hình 2.10 chỉ ra ba cách khác nhau với ví dụ một luồng gói IP: như là số lượng khe gói giữa những sự đi đến (những thời gian liên đi đến là 5, 7, 3 và 5 khe trong ví dụ này); như là một quá trình đếm số lượng gói đi đến trong vòng một chu kỳ điển hình (ở đây, là 5 gói trong 25 khe gói); và như một tốc độ gói, trong trường hợp này là 20% của tốc độ khe gói. 2.4.3. Thời gian giữa những lần đi đến Những thời gian liên đi đến có thể được chỉ rõ bằng một giá trị cố định, hoặc một số giá trị phân bố xác suất tuỳ ý, cho thời gian giữa những lần đi đến thành công (các kết nối). Những giá trị này có thể trong thời gian liên tục, tạo ra bất kỳ giá trị thực tế nào, hoặc trong thời gian riêng, ví dụ như một tổ hợp ghép số tự nhiên của một chu kỳ thời gian riêng như thời gian truyền dẫn của một gói, ví dụ 2.831 µs. Một phân bố số mũ âm của thời gian liên đi đến là ví dụ căn bản của một quá trình thời gian liên tục do thuộc tính không nhớ [TK2.trang 28]. Cái tên này xuất hiện từ thực tế rằng, nếu thời gian từ t1 ® t2 là không phụ thuộc vào khoảng cách, dt, từ lần đi đến cuối cùng (Hình 2.11). Thuộc tính này cho phép phát triển một số công thức đơn giản cho hàng đợi. Xác suất để thời gian liên đi đến nhỏ hơn hoặc bằng t được tính theo công thức: Pr{thời gian liên đi đến ≤ t) = F(t) = 1 – e–λ.t với tốc độ đi đến là l. Phân bố này, F(t), được chỉ ra ở Hình 2.12 cho một tải trọng bằng 47.2% (tức là ví dụ nguồn CBR 1000). Tốc độ đi đến là 166 667 gói/s tương ứng với một thời gian liên đi đến bằng 6 µs. Khe gói đi đến còn được chỉ ra tất cả 2.831 µs trên trục thời gian. Thời gian riêng [TK2.trang 275] tương đương với việc có một số phân bố hình học của các khe thời gian giữa những lần đi đến (Hình 2.13), với số lượng đó được đếm từ điểm cuối của gói đầu tiên đến điểm cuối của gói đi đến tiếp theo. Rõ ràng một tốc độ gói bằng 1 gói/khe thời gian có một thời gian liên đi đến là một khe gói, tức là không có khe gói rỗng giữa những lần đi đến. Xác suất để một khe gói chứa một gói là không đổi, và chúng ta có thể gọi là p. Từ đó một khe gói rỗng với xác suất 1 – p. Xác suất để có k khe thời gian giữa những lần đi đến được tính: Pr{k khe thời gian giữa những lần đi đến} = (1 – p)k-1.p tức là k – 1 khe thời gian rỗng, sau đó là một khe thời gian đầy. Đây là phân bố hình học, thời gian riêng tương đương với phân bố số mũ âm. Phân bố hình học [TK2.trang 282] thường được giới thiệu trong những cuốn sách theo kiểu tung súc sắc hay đồng tiền, từ đó nó được nghĩa rằng như có k – 1 “thất bại” (những khe thời gian rỗng), sau đó đến một “thành công” (một lần đi đến của gói). Phân bố có nghĩa là nghịch đảo xác suất thành công, tức là 1/p. Lưu ý rằng phân bố hình học còn có một thuộc tính không nhớ trong đó giá trị p cho khe thời gian n được giữ không đổi tuy có rất nhiều sự đi đến trong n – 1 khe thời gian trước. Hình 2.14 so sánh phân bố hình học và phân bố số mũ âm với tải trọng 47.2% (có nghĩa là cho phân bố hình học, ρ = 0.472, với một cơ sở thời gian bằng 2.831 µs; và cho phân bố số mũ âm, l = 166 667 gói/s, như trước). Chúng sẽ là những phân bố tích luỹ (Hình 2.12), và chúng đưa ra xác suất để thời gian liên đi đến nhỏ hơn hoặc bằng với giá trị xác định trước trên trục thời gian. Trục thời gian này được chia nhỏ vào các khe gói với sự so sánh đơn giản. Phân bố hình học tích luỹ ban đầu tại khe thời gian k = 1 và cộng thêm Pr{k khe thời gian giữa những lần đi đến} cho mỗi giá trị tiếp theo của liên kết Pr{≤ k khe thời gian giữa những lần đi đến} = 1 – (1 – p)k 2.4.4. Đếm số lần đi đến Một cách lựa chọn trình diễn thông tin định thời về một quá trình đi đến là bằng cách đếm số lần đi đến trong một khoảng thời gian được định nghĩa. Ở đây có một sự tương đương với phương thức thời gian liên đi đến trong thời gian liên tục: những thời gian liên đi đến được phân bố số mũ âm tạo thành một quá trình Poisson: Pr{k lần đi đến trong thời gian T} = với l là tốc độ đi đến. Trong thời gian riêng, những thời điểm liên đi đến hình học định dạng một quá trình Bernoulli [TK2.trang 280], với xác suất để một lần đi đến trong một khe thời gian là p và xác suất để không có sự đi đến nào trong khe thời gian là 1 – p. Nếu chúng ta xem xét nhiều hơn một khe thời gian, thì số lượng đi đến trong N khe thời gian được phân bố nhị thức [TK2.trang 284]. Pr{k lần đi đến trong N khe thời gian} = và p là số lần đi đến trung bình trên khe thời gian. Vậy những phân bố này được sử dụng để hình thành các hệ thống IP như thế nào. Xem xét ví dụ về một nguồn IP đang phát những gói đến như một quá trình Poisson; các gói khi đó được lưu đệm, và được phát một cách thường xuyên cho IP – như một dòng gói trong các khe đồng bộ (xem Hình 2.15). Quá trình Poisson trình diễn những gói đi đến từ nguồn tới bộ đệm, tại tốc độ gói là l gói/khe thời gian. Tại đầu ra của bộ đệm, một gói chiếm khe thời gian i với xác suất p như chúng ta đã định nghĩa trước đó cho quá trình Bernoulli. Bây giờ nếu l là tốc độ gói đi đến và p là tốc độ gói đi ra, (cả hai đều trong giới hạn bởi số gói trên khe thời gian), và nếu chúng ta không mất bất kỳ gói nào trong bộ đệm (vô hạn), thì chúng ta phải có l = p. Lưu ý rằng quá trình đầu ra của một bộ đệm IP với độ dài vô hạn, được cung cấp bởi nguồn Poisson “không” thực sự là một quá trình Bernoulli. Nguyên nhân là hàng đợi trình bày phụ thuộc lần lượt từng khe. Nếu như có các gói trong bộ đệm, thì xác suất để không có gói nào được phục vụ tại khe gói kế tiếp là 0, trong khi đối với quá trình Bernoulli nó là 1 – p. Như vậy, mặc dù dòng gói đầu ra không phải là một quá trình không nhớ, quá trình Bernoulli vẫn là một mẫu xấp xỉ hiệu quả, những sự biến đổi được bắt gặp thường xuyên trong kỹ thuật lưu lượng từ xa [TK1.trang 45] cho IP. Hạn chế của những quá trình liên đi đến theo số mũ âm và hình học là chúng không bao gồm tất cả các thông số đặc trưng quan trọng của lưu lượng điển hình. Những dạng cụ thể của phân tích chuyển mạch giả thiết quá trình “đi đến theo nhóm”: ở đây, thay vì một sự đi đến đơn lẻ với xác suất p, chúng ta sẽ có một nhóm, và số lượng trong nhóm có thể có một phân bố bất kỳ. Dạng quá trình đi đến này có thể còn được xem xét trong phạm trù đếm số lần đi đến này. Ví dụ, tại một bộ đệm trong mạng IP, một nhóm đi đến lên tới một vài giá trị cực đại, M, đến từ những phần khác nhau của chuyển mạch trong khoảng một khe thời gian. Điều này có thể được xem xét khi đếm số lần đi đến tương tự như các gói trong nhóm trong khe thời gian đó. Quá trình Bernoulli với đi đến theo nhóm được đặc trưng bởi một số lần đi đến được phân bố độc lập và giống nhau theo chu kỳ thời gian riêng. Điều này được định nghĩa theo hai phần: sự hiện diện của nhóm Pr{có một nhóm đi đến trong một khe thời gian} = p hoặc sự vắng mặt của nhóm Pr{không có sự đi đến nào trong một khe thời gian} = 1 – p Và sự phân bố của số gói trong nhóm: b(k) = Pr{có k gói trong một nhóm được tính ra khi có một nhóm trong x khe thời gian} Lưu ý rằng k > 0. Sự mô tả quá trình đi đến này có thể được sắp xếp lại để đưa ra phân bố tổng của số lần đi đến trên khe, a(k), như sau: a(0) = 1 – p a(1) = p.b(1) a(2) = p.b(2) … a(k) = p.b(k) … a(M) = p.b(M) Trong trường hợp một phân bố đầu vào Poisson, khoảng thời gian T là một khe thời gian, khi đó Với phân bố nhị thức, bây giờ chúng ta mong muốn xác suất có k lần đi đến từ M lối vào mà mỗi đầu vào có một xác suất, p, của quá trình cung cấp một gói đi đến trong khe thời gian bất kỳ. Bởi vậy Và tốc độ đi đến cuối cùng là M.p gói/khe thời gian. Hình 2.16 trình bày điều gì xảy ra khi tốc độ đi đến cuối cùng được cố định tại 0.95 gói/khe thời gian và những số lượng lối vào 10, 20 và 100 (và như vậy p lần lượt là 0.095, 0.045, 0.0095). Phân bố nhị thức có xu hướng gần với phân bố Poisson, và thực tế trong giới hạn khi N ® ∞ và p ® 0 các phân bố là tương tự. 2.4.5. Các tốc độ luồng Dạng nguồn đơn giản nhất sử dụng một sự mô tả tốc độ là dòng đi đến theo chu kỳ. Chúng ta thấy một ví dụ của dạng này trong điện thoại 64 kbit/s, có tốc độ gói là 167 gói/s. Bước tiếp theo là xem xét một nguồn Bật-Tắt, nơi mà quá trình chuyển mạch giữa một trạng thái im lặng, không tạo ra gói, và một trạng thái cung cấp một tốc độ cố định riêng của gói. Những nguồn với những khoảng thời gian (trong các trạng thái Bật và Tắt) được phân bố như số mũ âm được nghiên cứu thường xuyên nhất, và được áp dụng cho lưu lượng dữ liệu, cho lưu lượng thoại gói, và như một mẫu chung cho lưu lượng theo nhóm trong một bộ ghép IP. Hình 2.17 đưa ra một mẫu lưu lượng từ xa điển hình cho một nguồn Bật-Tắt. Trong khoảng thời gian nguồn bật (gọi là “thời gian lưu lại trong trạng thái hoạt động), nguồn phát các gói với tốc độ R. Sau mỗi gói, gói khác được phát với xác suất a, hoặc nguồn chuyển sang trạng thái tắt với xác suất 1 – a. Tương tự, trong trạng thái tắt, nguồn phát khe thời gian rỗng khác với xác suất s hoặc chuyển sang trạng thái hoạt động với xác suất 1 – s. Kiểu nguồn này phát các gói trong những mẫu giống như trong Hình 2.18. Đối với mẫu này, R bằng một nửa của tốc độ khe gói. Lưu ý rằng có các khe rỗng trong khoảng thời gian trạng thái hoạt động; chúng xuất hiện nếu tốc độ đi đến của gói, R, nhỏ hơn tốc độ khe gói, C. Chúng ta có thể quan sát nguồn Bật-Tắt theo cách khác. Thay vì đưa ra quá trình phát gói và quá trình khe thời gian rỗng rõ ràng như quá trình Bernoulli, chúng ta có thể mô tả đơn giản trạng thái hoạt động giống như có một phân bố hình học với số lần đi đến của gói, và trạng thái tắt như có một phân bố hình học số các khe gói. Số các gói có nghĩa là một trạng thái hoạt động, E[on], bằng nghịch đảo của xác suất để thoát khỏi trạng thái hoạt động, tức là 1/(1 – a) gói. Số khe gói có nghĩa là trạng thái im lặng, E[off], bằng 1/(1 – s) khe gói. Tại điểm cuối của một chu kỳ lưu lại trong trạng thái, quá trình chuyển mạch đến một trạng thái khác với xác suất bằng 1. Hình 2.19 chỉ ra sự trình diễn lựa chọn này của mẫu nguồn Bật-Tắt. Một lưu ý quan trọng là các phân bố hình học cho những trạng thái hoạt động và tắt có cơ sở thời gian khác nhau. Đối với trạng thái hoạt động đơn vị thời gian là 1/R, tức là thời gian liên đi đến của một gói. Do vậy khoảng thời gian có nghĩa trong trạng thái hoạt động là Đối với trạng thái tắt, đơn vị thời gian là 1/C, với C là tốc độ khe gói; bởi vậy khoảng thời gian có nghĩa trong trạng thái tắt là Trình diễn lựa chọn của Hình 2.19 khi đó có thể được khái quát hoá bằng cách cho phép các phân bố tuỳ ý đối với các gói được phát trong một chu kỳ hoạt động, và còn đối với số những khe rỗng được phát trong một chu kỳ tắt. Trước khi rời nguồn Bật-Tắt, chúng ta sẽ áp dụng nó vào một ví dụ thực tế: thoại tránh im lặng (không phát gói trong những chu kỳ mà người nói im lặng). Các con số điển hình (tìm được bằng phép đo) đối với những chu kỳ Bật và Tắt có nghĩa lần lượt là 0.96s và 1.69s. Các gói được phát từ nguồn thoại 64 kbit/s tại tốc độ R = 167 gói/s và tốc độ khe gói của một liên kết là 155.52 Mb/s là C = 353208 gói/s. Do đó số gói có nghĩa được cung cấp trong một trạng thái hoạt động là E[on] = R × 0.96 = 160 gói Và số các khe rỗng có nghĩa trong một trạng thái im lặng là E[off] = C × 1.69 = 596921 khe gói Điều này đưa đến mẫu được chỉ ra trong Hình 2.20 Chúng ta còn có thể tính toán các giá trị của những thông số a và s đối với mẫu ở Hình 2.17. Chúng ta biết rằng vậy Và vậy Nguồn Bật-Tắt là một ví dụ cụ thể của một mẫu trên cơ sở trạng thái mà tốc độ đi đến trong một trạng thái là cố định, có hai trạng thái, và chu kỳ thời gian bỏ ra trong một trạng thái (thời gian lưu lại) là phân bố số mũ âm, hình học hoặc tuỳ ý. Chúng ta có thể khái quát hoá điều này tới N trạng thái, với các tốc độ cố định trong mỗi trạng thái. Các mẫu đa trạng thái này (được gọi là “các quá trình quyết định điều chế”) rất hữu ích cho việc tạo ra một số nguồn Bật-Tắt được ghép cùng nhau, hoặc một nguồn lưu lượng đơn lẻ, phức tạp hơn, như video. Nếu chúng ta cho phép thời gian lưu lại có phân bố tuỳ ý, quá trình kết quả sẽ được gọi là một Quá trình Quyết định Điều chế Chung (GMDP – Generally Modulated Deterministic Process). Nếu khoảng thời gian trong trạng thái được phân bố theo số mũ thì quá trình được gọi là Quá trình Quyết định Điều chế Markov (MMDP). Trong trường hợp này, mỗi trạng thái tạo ra một phân bố hình học cho số các gói trong chu kỳ lưu lại bất kỳ. Đó là do, khi đã có phát sự đi đến i, nó phát sự đi đến i + 1 với một xác suất được tính bằng xác suất để thời gian lưu lại không kết thúc trước thời điểm của lần đi đến kế tiếp. Xác suất này không đổi nếu các chu kỳ thời gian lưu lại được phân bố theo số mũ âm bởi vì thuộc tính “không nhớ” của phân bố số mũ âm. Chúng ta không cần hạn chế mẫu để có một tốc độ đi đến không đổi trong mỗi trạng thái: nếu quá trình đi đến trên trạng thái là một quá trình Poisson, và ý nghĩa của phân bố Poisson được quyết định bằng trạng thái của mẫu trong đó, thì chúng ta có một MMDP hữu ích đối với việc trình diễn một quá trình đi đến tổng của gói. Đối với tất cả quá trình trạng thái này, tại điểm cuối của một sự lưu lại trong trạng thái i, tạo ra một sự quá độ sang trạng thái khác j; sự quá độ này được chi phối bởi một ma trận N×N của các xác suất quá độ, p(i,j) i ¹ j. Hình 2.21 minh hoạ một mẫu đa trạng thái, với ba trạng thái, và với các xác suất quá độ từ trạng thái i sang trạng thái j chỉ ra như p(i,j).